hash_longest_match_inc.h revision b972c67780f03256a3fbf81dc3350a4bf00aa4ad 
1/* NOLINT(build/header_guard) */
2/* Copyright 2010 Google Inc. All Rights Reserved.
3
4   Distributed under MIT license.
5   See file LICENSE for detail or copy at https://opensource.org/licenses/MIT
6*/
7
8/* template parameters: FN, BUCKET_BITS, BLOCK_BITS,
9                        NUM_LAST_DISTANCES_TO_CHECK */
10
11/* A (forgetful) hash table to the data seen by the compressor, to
12   help create backward references to previous data.
13
14   This is a hash map of fixed size (BUCKET_SIZE) to a ring buffer of
15   fixed size (BLOCK_SIZE). The ring buffer contains the last BLOCK_SIZE
16   index positions of the given hash key in the compressed data. */
17
18#define HashLongestMatch HASHER()
19
20/* Number of hash buckets. */
21#define BUCKET_SIZE (1 << BUCKET_BITS)
22
23/* Only BLOCK_SIZE newest backward references are kept,
24   and the older are forgotten. */
25#define BLOCK_SIZE (1u << BLOCK_BITS)
26
27/* Mask for accessing entries in a block (in a ringbuffer manner). */
28#define BLOCK_MASK ((1 << BLOCK_BITS) - 1)
29
30#define HASH_MAP_SIZE (2 << BUCKET_BITS)
31
32static BROTLI_INLINE size_t FN(HashTypeLength)(void) { return 4; }
33static BROTLI_INLINE size_t FN(StoreLookahead)(void) { return 4; }
34
35/* HashBytes is the function that chooses the bucket to place
36   the address in. The HashLongestMatch and HashLongestMatchQuickly
37   classes have separate, different implementations of hashing. */
38static uint32_t FN(HashBytes)(const uint8_t *data) {
39  uint32_t h = BROTLI_UNALIGNED_LOAD32(data) * kHashMul32;
40  /* The higher bits contain more mixture from the multiplication,
41     so we take our results from there. */
42  return h >> (32 - BUCKET_BITS);
43}
44
45typedef struct HashLongestMatch {
46  /* Number of entries in a particular bucket. */
47  uint16_t num_[BUCKET_SIZE];
48
49  /* Buckets containing BLOCK_SIZE of backward references. */
50  uint32_t buckets_[BLOCK_SIZE << BUCKET_BITS];
51
52  /* True if num_ array needs to be initialized. */
53  int is_dirty_;
54
55  size_t num_dict_lookups_;
56  size_t num_dict_matches_;
57} HashLongestMatch;
58
59static void FN(Reset)(HashLongestMatch* self) {
60  self->is_dirty_ = 1;
61  self->num_dict_lookups_ = 0;
62  self->num_dict_matches_ = 0;
63}
64
65static void FN(InitEmpty)(HashLongestMatch* self) {
66  if (self->is_dirty_) {
67    memset(self->num_, 0, sizeof(self->num_));
68    self->is_dirty_ = 0;
69  }
70}
71
72static void FN(InitForData)(HashLongestMatch* self, const uint8_t* data,
73    size_t num) {
74  size_t i;
75  for (i = 0; i < num; ++i) {
76    const uint32_t key = FN(HashBytes)(&data[i]);
77    self->num_[key] = 0;
78  }
79  if (num != 0) {
80    self->is_dirty_ = 0;
81  }
82}
83
84static void FN(Init)(
85    MemoryManager* m, HashLongestMatch* self, const uint8_t* data, int lgwin,
86    size_t position, size_t bytes, int is_last) {
87  /* Choose which init method is faster.
88     Init() is about 100 times faster than InitForData(). */
89  const size_t kMaxBytesForPartialHashInit = HASH_MAP_SIZE >> 7;
90  BROTLI_UNUSED(m);
91  BROTLI_UNUSED(lgwin);
92  if (position == 0 && is_last && bytes <= kMaxBytesForPartialHashInit) {
93    FN(InitForData)(self, data, bytes);
94  } else {
95    FN(InitEmpty)(self);
96  }
97}
98
99/* Look at 4 bytes at &data[ix & mask].
100   Compute a hash from these, and store the value of ix at that position. */
101static BROTLI_INLINE void FN(Store)(HashLongestMatch* self, const uint8_t *data,
102    const size_t mask, const size_t ix) {
103  const uint32_t key = FN(HashBytes)(&data[ix & mask]);
104  const size_t minor_ix = self->num_[key] & BLOCK_MASK;
105  self->buckets_[minor_ix + (key << BLOCK_BITS)] = (uint32_t)ix;
106  ++self->num_[key];
107}
108
109static BROTLI_INLINE void FN(StoreRange)(HashLongestMatch* self,
110    const uint8_t *data, const size_t mask, const size_t ix_start,
111    const size_t ix_end) {
112  size_t i;
113  for (i = ix_start; i < ix_end; ++i) {
114    FN(Store)(self, data, mask, i);
115  }
116}
117
118static BROTLI_INLINE void FN(StitchToPreviousBlock)(HashLongestMatch* self,
119    size_t num_bytes, size_t position, const uint8_t* ringbuffer,
120    size_t ringbuffer_mask) {
121  if (num_bytes >= FN(HashTypeLength)() - 1 && position >= 3) {
122    /* Prepare the hashes for three last bytes of the last write.
123       These could not be calculated before, since they require knowledge
124       of both the previous and the current block. */
125    FN(Store)(self, ringbuffer, ringbuffer_mask, position - 3);
126    FN(Store)(self, ringbuffer, ringbuffer_mask, position - 2);
127    FN(Store)(self, ringbuffer, ringbuffer_mask, position - 1);
128  }
129}
130
131/* Find a longest backward match of &data[cur_ix] up to the length of
132   max_length and stores the position cur_ix in the hash table.
133
134   Does not look for matches longer than max_length.
135   Does not look for matches further away than max_backward.
136   Writes the best found match length into best_len_out.
137   Writes the index (&data[index]) offset from the start of the best match
138   into best_distance_out.
139   Write the score of the best match into best_score_out.
140   Returns 1 when match is found, otherwise 0. */
141static BROTLI_INLINE int FN(FindLongestMatch)(HashLongestMatch* self,
142    const uint8_t* BROTLI_RESTRICT data, const size_t ring_buffer_mask,
143    const int* BROTLI_RESTRICT distance_cache, const size_t cur_ix,
144    const size_t max_length, const size_t max_backward,
145    size_t* BROTLI_RESTRICT best_len_out,
146    size_t* BROTLI_RESTRICT best_len_code_out,
147    size_t* BROTLI_RESTRICT best_distance_out,
148    double* BROTLI_RESTRICT best_score_out) {
149  const size_t cur_ix_masked = cur_ix & ring_buffer_mask;
150  int is_match_found = 0;
151  /* Don't accept a short copy from far away. */
152  double best_score = *best_score_out;
153  size_t best_len = *best_len_out;
154  size_t i;
155  *best_len_code_out = 0;
156  *best_len_out = 0;
157  /* Try last distance first. */
158  for (i = 0; i < NUM_LAST_DISTANCES_TO_CHECK; ++i) {
159    const size_t idx = kDistanceCacheIndex[i];
160    const size_t backward =
161        (size_t)(distance_cache[idx] + kDistanceCacheOffset[i]);
162    size_t prev_ix = (size_t)(cur_ix - backward);
163    if (prev_ix >= cur_ix) {
164      continue;
165    }
166    if (PREDICT_FALSE(backward > max_backward)) {
167      continue;
168    }
169    prev_ix &= ring_buffer_mask;
170
171    if (cur_ix_masked + best_len > ring_buffer_mask ||
172        prev_ix + best_len > ring_buffer_mask ||
173        data[cur_ix_masked + best_len] != data[prev_ix + best_len]) {
174      continue;
175    }
176    {
177      const size_t len = FindMatchLengthWithLimit(&data[prev_ix],
178                                                  &data[cur_ix_masked],
179                                                  max_length);
180      if (len >= 3 || (len == 2 && i < 2)) {
181        /* Comparing for >= 2 does not change the semantics, but just saves for
182           a few unnecessary binary logarithms in backward reference score,
183           since we are not interested in such short matches. */
184        double score = BackwardReferenceScoreUsingLastDistance(len, i);
185        if (best_score < score) {
186          best_score = score;
187          best_len = len;
188          *best_len_out = best_len;
189          *best_len_code_out = best_len;
190          *best_distance_out = backward;
191          *best_score_out = best_score;
192          is_match_found = 1;
193        }
194      }
195    }
196  }
197  {
198    const uint32_t key = FN(HashBytes)(&data[cur_ix_masked]);
199    const uint32_t * BROTLI_RESTRICT const bucket =
200        &self->buckets_[key << BLOCK_BITS];
201    const size_t down =
202        (self->num_[key] > BLOCK_SIZE) ? (self->num_[key] - BLOCK_SIZE) : 0u;
203    for (i = self->num_[key]; i > down;) {
204      size_t prev_ix = bucket[--i & BLOCK_MASK];
205      const size_t backward = cur_ix - prev_ix;
206      if (PREDICT_FALSE(backward == 0 || backward > max_backward)) {
207        break;
208      }
209      prev_ix &= ring_buffer_mask;
210      if (cur_ix_masked + best_len > ring_buffer_mask ||
211          prev_ix + best_len > ring_buffer_mask ||
212          data[cur_ix_masked + best_len] != data[prev_ix + best_len]) {
213        continue;
214      }
215      {
216        const size_t len = FindMatchLengthWithLimit(&data[prev_ix],
217                                                    &data[cur_ix_masked],
218                                                    max_length);
219        if (len >= 4) {
220          /* Comparing for >= 3 does not change the semantics, but just saves
221             for a few unnecessary binary logarithms in backward reference
222             score, since we are not interested in such short matches. */
223          double score = BackwardReferenceScore(len, backward);
224          if (best_score < score) {
225            best_score = score;
226            best_len = len;
227            *best_len_out = best_len;
228            *best_len_code_out = best_len;
229            *best_distance_out = backward;
230            *best_score_out = best_score;
231            is_match_found = 1;
232          }
233        }
234      }
235    }
236    self->buckets_[(key << BLOCK_BITS) + (self->num_[key] & BLOCK_MASK)] =
237        (uint32_t)cur_ix;
238    ++self->num_[key];
239  }
240  if (!is_match_found &&
241      self->num_dict_matches_ >= (self->num_dict_lookups_ >> 7)) {
242    size_t dict_key = Hash14(&data[cur_ix_masked]) << 1;
243    int k;
244    for (k = 0; k < 2; ++k, ++dict_key) {
245      const uint16_t v = kStaticDictionaryHash[dict_key];
246      ++self->num_dict_lookups_;
247      if (v > 0) {
248        const size_t len = v & 31;
249        const size_t dist = v >> 5;
250        const size_t offset =
251            kBrotliDictionaryOffsetsByLength[len] + len * dist;
252        if (len <= max_length) {
253          const size_t matchlen =
254              FindMatchLengthWithLimit(&data[cur_ix_masked],
255                                       &kBrotliDictionary[offset], len);
256          if (matchlen + kCutoffTransformsCount > len && matchlen > 0) {
257            const size_t transform_id = kCutoffTransforms[len - matchlen];
258            const size_t word_id = dist +
259                transform_id * (1u << kBrotliDictionarySizeBitsByLength[len]);
260            const size_t backward = max_backward + word_id + 1;
261            double score = BackwardReferenceScore(matchlen, backward);
262            if (best_score < score) {
263              ++self->num_dict_matches_;
264              best_score = score;
265              best_len = matchlen;
266              *best_len_out = best_len;
267              *best_len_code_out = len;
268              *best_distance_out = backward;
269              *best_score_out = best_score;
270              is_match_found = 1;
271            }
272          }
273        }
274      }
275    }
276  }
277  return is_match_found;
278}
279
280#undef HASH_MAP_SIZE
281#undef BLOCK_MASK
282#undef BLOCK_SIZE
283#undef BUCKET_SIZE
284
285#undef HashLongestMatch
286