New version of the backward reference search code.

The new	interface of the backward reference search
function makes it possible to use it in	a streaming
manner.

Using the advanced cost model and static dictionary
can be turned on/off by	template parameters.

The distance short codes are now computed as part of
the backward reference search.

Added a	faster version of the Hasher.

1 files changed, 265 insertions, 155 deletions

diff --git a/enc/hash.h b/enc/hash.h
index 7b47e08..c89426c 100644
--- a/enc/hash.h
+++ b/enc/hash.h
@@ -31,10 +31,18 @@
 #include "./fast_log.h"
 #include "./find_match_length.h"
 #include "./port.h"
+#include "./prefix.h"
 #include "./static_dict.h"
 
 namespace brotli {
 
+static const int kDistanceCacheIndex[] = {
+  0, 1, 2, 3, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1,
+};
+static const int kDistanceCacheOffset[] = {
+  0, 0, 0, 0, -1, 1, -2, 2, -3, 3, -1, 1, -2, 2, -3, 3
+};
+
 // kHashMul32 multiplier has these properties:
 // * The multiplier must be odd. Otherwise we may lose the highest bit.
 // * No long streaks of 1s or 0s.
@@ -75,59 +83,194 @@ inline uint32_t Hash(const uint8_t *data) {
 // when it is not much longer and the bit cost for encoding it is more
 // than the saved literals.
 inline double BackwardReferenceScore(double average_cost,
-                                     double start_cost4,
-                                     double start_cost3,
-                                     double start_cost2,
                                      int copy_length,
                                      int backward_reference_offset) {
-  double retval = 0;
-  switch (copy_length) {
-    case 2: retval = start_cost2; break;
-    case 3: retval = start_cost3; break;
-    default: retval = start_cost4 + (copy_length - 4) * average_cost; break;
-  }
-  retval -= 1.20 * Log2Floor(backward_reference_offset);
-  return retval;
+  return (copy_length * average_cost -
+          1.20 * Log2Floor(backward_reference_offset));
 }
 
 inline double BackwardReferenceScoreUsingLastDistance(double average_cost,
-                                                      double start_cost4,
-                                                      double start_cost3,
-                                                      double start_cost2,
                                                       int copy_length,
                                                       int distance_short_code) {
-  double retval = 0;
-  switch (copy_length) {
-    case 2: retval = start_cost2; break;
-    case 3: retval = start_cost3; break;
-    default: retval = start_cost4 + (copy_length - 4) * average_cost; break;
-  }
   static const double kDistanceShortCodeBitCost[16] = {
     -0.6, 0.95, 1.17, 1.27,
     0.93, 0.93, 0.96, 0.96, 0.99, 0.99,
     1.05, 1.05, 1.15, 1.15, 1.25, 1.25
   };
-  retval -= kDistanceShortCodeBitCost[distance_short_code];
-  return retval;
+  return (average_cost * copy_length
+          - kDistanceShortCodeBitCost[distance_short_code]);
 }
 
 // A (forgetful) hash table to the data seen by the compressor, to
 // help create backward references to previous data.
 //
+// This is a hash map of fixed size (kBucketSize). Starting from the
+// given index, kBucketSweep buckets are used to store values of a key.
+template <int kBucketBits, int kBucketSweep>
+class HashLongestMatchQuickly {
+ public:
+  HashLongestMatchQuickly() {
+    Reset();
+  }
+  void Reset() {
+    // It is not strictly necessary to fill this buffer here, but
+    // not filling will make the results of the compression stochastic
+    // (but correct). This is because random data would cause the
+    // system to find accidentally good backward references here and there.
+    std::fill(&buckets_[0],
+              &buckets_[sizeof(buckets_) / sizeof(buckets_[0])],
+              0);
+  }
+  // Look at 4 bytes at data.
+  // Compute a hash from these, and store the value somewhere within
+  // [ix .. ix+3].
+  inline void Store(const uint8_t *data, const int ix) {
+    const uint32_t key = Hash<kBucketBits, 4>(data);
+    // Wiggle the value with the bucket sweep range.
+    const uint32_t off = (static_cast<uint32_t>(ix) >> 3) % kBucketSweep;
+    buckets_[key + off] = ix;
+  }
+
+  // Store hashes for a range of data.
+  void StoreHashes(const uint8_t *data, size_t len, int startix, int mask) {
+    for (int p = 0; p < len; ++p) {
+      Store(&data[p & mask], startix + p);
+    }
+  }
+
+  bool HasStaticDictionary() const { return false; }
+
+  // Find a longest backward match of &ring_buffer[cur_ix & ring_buffer_mask]
+  // up to the length of max_length.
+  //
+  // Does not look for matches longer than max_length.
+  // Does not look for matches further away than max_backward.
+  // Writes the best found match length into best_len_out.
+  // Writes the index (&data[index]) of the start of the best match into
+  // best_distance_out.
+  inline bool FindLongestMatch(const uint8_t * __restrict ring_buffer,
+                               const size_t ring_buffer_mask,
+                               const float* __restrict literal_cost,
+                               const size_t literal_cost_mask,
+                               const double average_cost,
+                               const int* __restrict distance_cache,
+                               const uint32_t cur_ix,
+                               const uint32_t max_length,
+                               const uint32_t max_backward,
+                               int * __restrict best_len_out,
+                               int * __restrict best_len_code_out,
+                               int * __restrict best_distance_out,
+                               double* __restrict best_score_out) {
+    const int best_len_in = *best_len_out;
+    const int cur_ix_masked = cur_ix & ring_buffer_mask;
+    int compare_char = ring_buffer[cur_ix_masked + best_len_in];
+    double best_score = *best_score_out;
+    int best_len = best_len_in;
+    int backward = distance_cache[0];
+    size_t prev_ix = cur_ix - backward;
+    bool match_found = false;
+    if (prev_ix < cur_ix) {
+      prev_ix &= ring_buffer_mask;
+      if (compare_char == ring_buffer[prev_ix + best_len]) {
+        int len = FindMatchLengthWithLimit(&ring_buffer[prev_ix],
+                                           &ring_buffer[cur_ix_masked],
+                                           max_length);
+        if (len >= 4) {
+          best_score = BackwardReferenceScoreUsingLastDistance(average_cost,
+                                                               len, 0);
+          best_len = len;
+          *best_len_out = len;
+          *best_len_code_out = len;
+          *best_distance_out = backward;
+          *best_score_out = best_score;
+          compare_char = ring_buffer[cur_ix_masked + best_len];
+          if (kBucketSweep == 1) {
+            return true;
+          } else {
+            match_found = true;
+          }
+        }
+      }
+    }
+    const uint32_t key = Hash<kBucketBits, 4>(&ring_buffer[cur_ix_masked]);
+    if (kBucketSweep == 1) {
+      // Only one to look for, don't bother to prepare for a loop.
+      prev_ix = buckets_[key];
+      backward = cur_ix - prev_ix;
+      prev_ix &= ring_buffer_mask;
+      if (compare_char != ring_buffer[prev_ix + best_len_in]) {
+        return false;
+      }
+      if (PREDICT_FALSE(backward == 0 || backward > max_backward)) {
+        return false;
+      }
+      const int len = FindMatchLengthWithLimit(&ring_buffer[prev_ix],
+                                               &ring_buffer[cur_ix_masked],
+                                               max_length);
+      if (len >= 4) {
+        *best_len_out = len;
+        *best_len_code_out = len;
+        *best_distance_out = backward;
+        *best_score_out = BackwardReferenceScore(average_cost, len, backward);
+        return true;
+      } else {
+        return false;
+      }
+    } else {
+      uint32_t *bucket = buckets_ + key;
+      prev_ix = *bucket++;
+      for (int i = 0; i < kBucketSweep; ++i, prev_ix = *bucket++) {
+        const int backward = cur_ix - prev_ix;
+        prev_ix &= ring_buffer_mask;
+        if (compare_char != ring_buffer[prev_ix + best_len]) {
+          continue;
+        }
+        if (PREDICT_FALSE(backward == 0 || backward > max_backward)) {
+          continue;
+        }
+        const int len =
+            FindMatchLengthWithLimit(&ring_buffer[prev_ix],
+                                     &ring_buffer[cur_ix_masked],
+                                     max_length);
+        if (len >= 4) {
+          const double score = BackwardReferenceScore(average_cost,
+                                                      len, backward);
+          if (best_score < score) {
+            best_score = score;
+            best_len = len;
+            *best_len_out = best_len;
+            *best_len_code_out = best_len;
+            *best_distance_out = backward;
+            *best_score_out = score;
+            compare_char = ring_buffer[cur_ix_masked + best_len];
+            match_found = true;
+          }
+        }
+      }
+      return match_found;
+    }
+  }
+
+ private:
+  static const uint32_t kBucketSize = 1 << kBucketBits;
+  uint32_t buckets_[kBucketSize + kBucketSweep];
+};
+
+// A (forgetful) hash table to the data seen by the compressor, to
+// help create backward references to previous data.
+//
 // This is a hash map of fixed size (kBucketSize) to a ring buffer of
 // fixed size (kBlockSize). The ring buffer contains the last kBlockSize
 // index positions of the given hash key in the compressed data.
-template <int kBucketBits, int kBlockBits, int kMinLength>
+template <int kBucketBits,
+          int kBlockBits,
+          int kMinLength,
+          int kNumLastDistancesToCheck,
+          bool kUseCostModel,
+          bool kUseDictionary>
 class HashLongestMatch {
  public:
-  HashLongestMatch()
-      : last_distance1_(4),
-        last_distance2_(11),
-        last_distance3_(15),
-        last_distance4_(16),
-        insert_length_(0),
-        average_cost_(5.4),
-        static_dict_(NULL) {
+  HashLongestMatch() : static_dict_(NULL) {
     Reset();
   }
   void Reset() {
@@ -166,73 +309,58 @@ class HashLongestMatch {
   // into best_distance_out.
   // Write the score of the best match into best_score_out.
   bool FindLongestMatch(const uint8_t * __restrict data,
-                        const float * __restrict literal_cost,
                         const size_t ring_buffer_mask,
+                        const float * __restrict literal_cost,
+                        const size_t literal_cost_mask,
+                        const double average_cost,
+                        const int* __restrict distance_cache,
                         const uint32_t cur_ix,
                         uint32_t max_length,
                         const uint32_t max_backward,
-                        size_t * __restrict best_len_out,
-                        size_t * __restrict best_len_code_out,
-                        size_t * __restrict best_distance_out,
-                        double * __restrict best_score_out,
-                        bool * __restrict in_dictionary) {
-    *in_dictionary = true;
+                        int * __restrict best_len_out,
+                        int * __restrict best_len_code_out,
+                        int * __restrict best_distance_out,
+                        double * __restrict best_score_out) {
     *best_len_code_out = 0;
     const size_t cur_ix_masked = cur_ix & ring_buffer_mask;
-    const double start_cost4 = literal_cost == NULL ? 20 :
-        literal_cost[cur_ix_masked] +
-        literal_cost[(cur_ix + 1) & ring_buffer_mask] +
-        literal_cost[(cur_ix + 2) & ring_buffer_mask] +
-        literal_cost[(cur_ix + 3) & ring_buffer_mask];
-    const double start_cost3 = literal_cost == NULL ? 15 :
-        literal_cost[cur_ix_masked] +
-        literal_cost[(cur_ix + 1) & ring_buffer_mask] +
-        literal_cost[(cur_ix + 2) & ring_buffer_mask] + 0.3;
-    double start_cost2 = literal_cost == NULL ? 10 :
-        literal_cost[cur_ix_masked] +
-        literal_cost[(cur_ix + 1) & ring_buffer_mask] + 1.2;
+    double start_cost_diff4 = 0.0;
+    double start_cost_diff3 = 0.0;
+    double start_cost_diff2 = 0.0;
+    if (kUseCostModel) {
+      start_cost_diff4 = literal_cost == NULL ? 0 :
+          literal_cost[cur_ix & literal_cost_mask] +
+          literal_cost[(cur_ix + 1) & literal_cost_mask] +
+          literal_cost[(cur_ix + 2) & literal_cost_mask] +
+          literal_cost[(cur_ix + 3) & literal_cost_mask] -
+          4 * average_cost;
+      start_cost_diff3 = literal_cost == NULL ? 0 :
+          literal_cost[cur_ix & literal_cost_mask] +
+          literal_cost[(cur_ix + 1) & literal_cost_mask] +
+          literal_cost[(cur_ix + 2) & literal_cost_mask] -
+          3 * average_cost + 0.3;
+      start_cost_diff2 = literal_cost == NULL ? 0 :
+          literal_cost[cur_ix & literal_cost_mask] +
+          literal_cost[(cur_ix + 1) & literal_cost_mask] -
+          2 * average_cost + 1.2;
+    }
     bool match_found = false;
     // Don't accept a short copy from far away.
-    double best_score = 8.115;
-    if (insert_length_ < 8) {
-      double cost_diff[8] =
-          { 0.1, 0.038, 0.019, 0.013, 0.001, 0.001, 0.001, 0.001 };
-      best_score += cost_diff[insert_length_];
-    }
-    size_t best_len = *best_len_out;
+    double best_score = *best_score_out;
+    int best_len = *best_len_out;
     *best_len_out = 0;
-    size_t best_ix = 1;
     // Try last distance first.
-    for (int i = 0; i < 16; ++i) {
-      size_t prev_ix = cur_ix;
-      switch(i) {
-        case 0: prev_ix -= last_distance1_; break;
-        case 1: prev_ix -= last_distance2_; break;
-        case 2: prev_ix -= last_distance3_; break;
-        case 3: prev_ix -= last_distance4_; break;
-
-        case 4: prev_ix -= last_distance1_ - 1; break;
-        case 5: prev_ix -= last_distance1_ + 1; break;
-        case 6: prev_ix -= last_distance1_ - 2; break;
-        case 7: prev_ix -= last_distance1_ + 2; break;
-        case 8: prev_ix -= last_distance1_ - 3; break;
-        case 9: prev_ix -= last_distance1_ + 3; break;
-
-        case 10: prev_ix -= last_distance2_ - 1; break;
-        case 11: prev_ix -= last_distance2_ + 1; break;
-        case 12: prev_ix -= last_distance2_ - 2; break;
-        case 13: prev_ix -= last_distance2_ + 2; break;
-        case 14: prev_ix -= last_distance2_ - 3; break;
-        case 15: prev_ix -= last_distance2_ + 3; break;
-      }
+    for (int i = 0; i < kNumLastDistancesToCheck; ++i) {
+      const int idx = kDistanceCacheIndex[i];
+      const int backward = distance_cache[idx] + kDistanceCacheOffset[i];
+      size_t prev_ix = cur_ix - backward;
       if (prev_ix >= cur_ix) {
         continue;
       }
-      const size_t backward = cur_ix - prev_ix;
       if (PREDICT_FALSE(backward > max_backward)) {
         continue;
       }
       prev_ix &= ring_buffer_mask;
+
       if (cur_ix_masked + best_len > ring_buffer_mask ||
           prev_ix + best_len > ring_buffer_mask ||
           data[cur_ix_masked + best_len] != data[prev_ix + best_len]) {
@@ -246,29 +374,30 @@ class HashLongestMatch {
         // Comparing for >= 2 does not change the semantics, but just saves for
         // a few unnecessary binary logarithms in backward reference score,
         // since we are not interested in such short matches.
-        const double score = BackwardReferenceScoreUsingLastDistance(
-            average_cost_,
-            start_cost4,
-            start_cost3,
-            start_cost2,
-            len, i);
+        double score = BackwardReferenceScoreUsingLastDistance(
+            average_cost, len, i);
+        if (kUseCostModel) {
+          switch (len) {
+            case 2: score += start_cost_diff2; break;
+            case 3: score += start_cost_diff3; break;
+            default: score += start_cost_diff4;
+          }
+        }
         if (best_score < score) {
           best_score = score;
           best_len = len;
-          best_ix = backward;
           *best_len_out = best_len;
           *best_len_code_out = best_len;
-          *best_distance_out = best_ix;
+          *best_distance_out = backward;
           *best_score_out = best_score;
           match_found = true;
-          *in_dictionary = backward > max_backward;
         }
       }
     }
     if (kMinLength == 2) {
       int stop = int(cur_ix) - 64;
       if (stop < 0) { stop = 0; }
-      start_cost2 -= 1.0;
+      start_cost_diff2 -= 1.0;
       for (int i = cur_ix - 1; i > stop; --i) {
         size_t prev_ix = i;
         const size_t backward = cur_ix - prev_ix;
@@ -281,15 +410,15 @@ class HashLongestMatch {
           continue;
         }
         int len = 2;
-        const double score = start_cost2 - 2.3 * Log2Floor(backward);
+        const double score =
+            average_cost * 2 - 2.3 * Log2Floor(backward) + start_cost_diff2;
 
         if (best_score < score) {
           best_score = score;
           best_len = len;
-          best_ix = backward;
           *best_len_out = best_len;
           *best_len_code_out = best_len;
-          *best_distance_out = best_ix;
+          *best_distance_out = backward;
           match_found = true;
         }
       }
@@ -317,26 +446,24 @@ class HashLongestMatch {
           // Comparing for >= 3 does not change the semantics, but just saves
           // for a few unnecessary binary logarithms in backward reference
           // score, since we are not interested in such short matches.
-          const double score = BackwardReferenceScore(average_cost_,
-                                                      start_cost4,
-                                                      start_cost3,
-                                                      start_cost2,
-                                                      len, backward);
+          double score = BackwardReferenceScore(average_cost,
+                                                len, backward);
+          if (kUseCostModel) {
+            score += (len >= 4) ? start_cost_diff4 : start_cost_diff3;
+          }
           if (best_score < score) {
             best_score = score;
             best_len = len;
-            best_ix = backward;
             *best_len_out = best_len;
             *best_len_code_out = best_len;
-            *best_distance_out = best_ix;
+            *best_distance_out = backward;
             *best_score_out = best_score;
             match_found = true;
-            *in_dictionary = false;
           }
         }
       }
     }
-    if (static_dict_ != NULL) {
+    if (kUseDictionary && static_dict_ != NULL) {
       // We decide based on first 4 bytes how many bytes to test for.
       int prefix = BROTLI_UNALIGNED_LOAD32(&data[cur_ix_masked]);
       int maxlen = static_dict_->GetLength(prefix);
@@ -347,21 +474,17 @@ class HashLongestMatch {
         int word_id;
         if (static_dict_->Get(snippet, &copy_len_code, &word_id)) {
           const size_t backward = max_backward + word_id + 1;
-          const double score = BackwardReferenceScore(average_cost_,
-                                                      start_cost4,
-                                                      start_cost3,
-                                                      start_cost2,
-                                                      len, backward);
+          const double score = (BackwardReferenceScore(average_cost,
+                                                       len, backward) +
+                                start_cost_diff4);
           if (best_score < score) {
             best_score = score;
             best_len = len;
-            best_ix = backward;
             *best_len_out = best_len;
             *best_len_code_out = copy_len_code;
-            *best_distance_out = best_ix;
+            *best_distance_out = backward;
             *best_score_out = best_score;
             match_found = true;
-            *in_dictionary = true;
           }
         }
       }
@@ -369,21 +492,6 @@ class HashLongestMatch {
     return match_found;
   }
 
-  void set_last_distance(int v) {
-    if (last_distance1_ != v) {
-      last_distance4_ = last_distance3_;
-      last_distance3_ = last_distance2_;
-      last_distance2_ = last_distance1_;
-      last_distance1_ = v;
-    }
-  }
-
-  int last_distance() const { return last_distance1_; }
-
-  void set_insert_length(int v) { insert_length_ = v; }
-
-  void set_average_cost(double v) { average_cost_ = v; }
-
  private:
   // Number of hash buckets.
   static const uint32_t kBucketSize = 1 << kBucketBits;
@@ -401,46 +509,48 @@ class HashLongestMatch {
   // Buckets containing kBlockSize of backward references.
   int buckets_[kBucketSize][kBlockSize];
 
-  int last_distance1_;
-  int last_distance2_;
-  int last_distance3_;
-  int last_distance4_;
-
-  // Cost adjustment for how many literals we are planning to insert
-  // anyway.
-  int insert_length_;
-
-  double average_cost_;
-
   const StaticDictionary *static_dict_;
 };
 
 struct Hashers {
-  enum Type {
-    HASH_15_8_4 = 0,
-    HASH_15_8_2 = 1,
-  };
-
-  void Init(Type type) {
+  typedef HashLongestMatchQuickly<16, 1> H1;
+  typedef HashLongestMatchQuickly<17, 4> H2;
+  typedef HashLongestMatch<14, 4, 4, 4, false, false> H3;
+  typedef HashLongestMatch<14, 5, 4, 4, false, false> H4;
+  typedef HashLongestMatch<15, 6, 4, 10, false, false> H5;
+  typedef HashLongestMatch<15, 7, 4, 10, false, false> H6;
+  typedef HashLongestMatch<15, 8, 4, 16, true, false> H7;
+  typedef HashLongestMatch<15, 8, 4, 16, true, true> H8;
+  typedef HashLongestMatch<15, 8, 2, 16, true, false> H9;
+
+  void Init(int type) {
     switch (type) {
-      case HASH_15_8_4:
-        hash_15_8_4.reset(new HashLongestMatch<15, 8, 4>());
-        break;
-      case HASH_15_8_2:
-        hash_15_8_2.reset(new HashLongestMatch<15, 8, 2>());
-        break;
-      default:
-        break;
+      case 1: hash_h1.reset(new H1); break;
+      case 2: hash_h2.reset(new H2); break;
+      case 3: hash_h3.reset(new H3); break;
+      case 4: hash_h4.reset(new H4); break;
+      case 5: hash_h5.reset(new H5); break;
+      case 6: hash_h6.reset(new H6); break;
+      case 7: hash_h7.reset(new H7); break;
+      case 8: hash_h8.reset(new H8); break;
+      case 9: hash_h9.reset(new H9); break;
+      default: break;
     }
   }
 
   void SetStaticDictionary(const StaticDictionary *dict) {
-    if (hash_15_8_4.get() != NULL) hash_15_8_4->SetStaticDictionary(dict);
-    if (hash_15_8_2.get() != NULL) hash_15_8_2->SetStaticDictionary(dict);
+    if (hash_h8.get() != NULL) hash_h8->SetStaticDictionary(dict);
   }
 
-  std::unique_ptr<HashLongestMatch<15, 8, 4> > hash_15_8_4;
-  std::unique_ptr<HashLongestMatch<15, 8, 2> > hash_15_8_2;
+  std::unique_ptr<H1> hash_h1;
+  std::unique_ptr<H2> hash_h2;
+  std::unique_ptr<H3> hash_h3;
+  std::unique_ptr<H4> hash_h4;
+  std::unique_ptr<H5> hash_h5;
+  std::unique_ptr<H6> hash_h6;
+  std::unique_ptr<H7> hash_h7;
+  std::unique_ptr<H8> hash_h8;
+  std::unique_ptr<H9> hash_h9;
 };
 
 }  // namespace brotli