1/* NOLINT(build/header_guard) */
2/* Copyright 2016 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, NUM_BANKS, BANK_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   Hashes are stored in chains which are bucketed to groups. Group of chains
15   share a storage "bank". When more than "bank size" chain nodes are added,
16   oldest nodes are replaced; this way several chains may share a tail. */
17
18#define HashForgetfulChain HASHER()
19
20#define BANK_SIZE (1 << BANK_BITS)
21
22/* Number of hash buckets. */
23#define BUCKET_SIZE (1 << BUCKET_BITS)
24
25#define CAPPED_CHAINS 0
26
27static BROTLI_INLINE size_t FN(HashTypeLength)(void) { return 4; }
28static BROTLI_INLINE size_t FN(StoreLookahead)(void) { return 4; }
29
30/* HashBytes is the function that chooses the bucket to place the address in.*/
31static BROTLI_INLINE size_t FN(HashBytes)(const uint8_t* BROTLI_RESTRICT data) {
32  const uint32_t h = BROTLI_UNALIGNED_LOAD32LE(data) * kHashMul32;
33  /* The higher bits contain more mixture from the multiplication,
34     so we take our results from there. */
35  return h >> (32 - BUCKET_BITS);
36}
37
38typedef struct FN(Slot) {
39  uint16_t delta;
40  uint16_t next;
41} FN(Slot);
42
43typedef struct FN(Bank) {
44  FN(Slot) slots[BANK_SIZE];
45} FN(Bank);
46
47typedef struct HashForgetfulChain {
48  uint16_t free_slot_idx[NUM_BANKS];  /* Up to 1KiB. Move to dynamic? */
49  size_t max_hops;
50
51  /* Shortcuts. */
52  void* extra;
53  HasherCommon* common;
54
55  /* --- Dynamic size members --- */
56
57  /* uint32_t addr[BUCKET_SIZE]; */
58
59  /* uint16_t head[BUCKET_SIZE]; */
60
61  /* Truncated hash used for quick rejection of "distance cache" candidates. */
62  /* uint8_t tiny_hash[65536];*/
63
64  /* FN(Bank) banks[NUM_BANKS]; */
65} HashForgetfulChain;
66
67static uint32_t* FN(Addr)(void* extra) {
68  return (uint32_t*)extra;
69}
70
71static uint16_t* FN(Head)(void* extra) {
72  return (uint16_t*)(&FN(Addr)(extra)[BUCKET_SIZE]);
73}
74
75static uint8_t* FN(TinyHash)(void* extra) {
76  return (uint8_t*)(&FN(Head)(extra)[BUCKET_SIZE]);
77}
78
79static FN(Bank)* FN(Banks)(void* extra) {
80  return (FN(Bank)*)(&FN(TinyHash)(extra)[65536]);
81}
82
83static void FN(Initialize)(
84    HasherCommon* common, HashForgetfulChain* BROTLI_RESTRICT self,
85    const BrotliEncoderParams* params) {
86  self->common = common;
87  self->extra = common->extra;
88
89  self->max_hops = (params->quality > 6 ? 7u : 8u) << (params->quality - 4);
90}
91
92static void FN(Prepare)(
93    HashForgetfulChain* BROTLI_RESTRICT self, BROTLI_BOOL one_shot,
94    size_t input_size, const uint8_t* BROTLI_RESTRICT data) {
95  uint32_t* BROTLI_RESTRICT addr = FN(Addr)(self->extra);
96  uint16_t* BROTLI_RESTRICT head = FN(Head)(self->extra);
97  uint8_t* BROTLI_RESTRICT tiny_hash = FN(TinyHash)(self->extra);
98  /* Partial preparation is 100 times slower (per socket). */
99  size_t partial_prepare_threshold = BUCKET_SIZE >> 6;
100  if (one_shot && input_size <= partial_prepare_threshold) {
101    size_t i;
102    for (i = 0; i < input_size; ++i) {
103      size_t bucket = FN(HashBytes)(&data[i]);
104      /* See InitEmpty comment. */
105      addr[bucket] = 0xCCCCCCCC;
106      head[bucket] = 0xCCCC;
107    }
108  } else {
109    /* Fill |addr| array with 0xCCCCCCCC value. Because of wrapping, position
110       processed by hasher never reaches 3GB + 64M; this makes all new chains
111       to be terminated after the first node. */
112    memset(addr, 0xCC, sizeof(uint32_t) * BUCKET_SIZE);
113    memset(head, 0, sizeof(uint16_t) * BUCKET_SIZE);
114  }
115  memset(tiny_hash, 0, sizeof(uint8_t) * 65536);
116  memset(self->free_slot_idx, 0, sizeof(self->free_slot_idx));
117}
118
119static BROTLI_INLINE size_t FN(HashMemAllocInBytes)(
120    const BrotliEncoderParams* params, BROTLI_BOOL one_shot,
121    size_t input_size) {
122  BROTLI_UNUSED(params);
123  BROTLI_UNUSED(one_shot);
124  BROTLI_UNUSED(input_size);
125  return sizeof(uint32_t) * BUCKET_SIZE + sizeof(uint16_t) * BUCKET_SIZE +
126         sizeof(uint8_t) * 65536 + sizeof(FN(Bank)) * NUM_BANKS;
127}
128
129/* Look at 4 bytes at &data[ix & mask]. Compute a hash from these, and prepend
130   node to corresponding chain; also update tiny_hash for current position. */
131static BROTLI_INLINE void FN(Store)(HashForgetfulChain* BROTLI_RESTRICT self,
132    const uint8_t* BROTLI_RESTRICT data, const size_t mask, const size_t ix) {
133  uint32_t* BROTLI_RESTRICT addr = FN(Addr)(self->extra);
134  uint16_t* BROTLI_RESTRICT head = FN(Head)(self->extra);
135  uint8_t* BROTLI_RESTRICT tiny_hash = FN(TinyHash)(self->extra);
136  FN(Bank)* BROTLI_RESTRICT banks = FN(Banks)(self->extra);
137  const size_t key = FN(HashBytes)(&data[ix & mask]);
138  const size_t bank = key & (NUM_BANKS - 1);
139  const size_t idx = self->free_slot_idx[bank]++ & (BANK_SIZE - 1);
140  size_t delta = ix - addr[key];
141  tiny_hash[(uint16_t)ix] = (uint8_t)key;
142  if (delta > 0xFFFF) delta = CAPPED_CHAINS ? 0 : 0xFFFF;
143  banks[bank].slots[idx].delta = (uint16_t)delta;
144  banks[bank].slots[idx].next = head[key];
145  addr[key] = (uint32_t)ix;
146  head[key] = (uint16_t)idx;
147}
148
149static BROTLI_INLINE void FN(StoreRange)(
150    HashForgetfulChain* BROTLI_RESTRICT self,
151    const uint8_t* BROTLI_RESTRICT data, const size_t mask,
152    const size_t ix_start, const size_t ix_end) {
153  size_t i;
154  for (i = ix_start; i < ix_end; ++i) {
155    FN(Store)(self, data, mask, i);
156  }
157}
158
159static BROTLI_INLINE void FN(StitchToPreviousBlock)(
160    HashForgetfulChain* BROTLI_RESTRICT self,
161    size_t num_bytes, size_t position, const uint8_t* ringbuffer,
162    size_t ring_buffer_mask) {
163  if (num_bytes >= FN(HashTypeLength)() - 1 && position >= 3) {
164    /* Prepare the hashes for three last bytes of the last write.
165       These could not be calculated before, since they require knowledge
166       of both the previous and the current block. */
167    FN(Store)(self, ringbuffer, ring_buffer_mask, position - 3);
168    FN(Store)(self, ringbuffer, ring_buffer_mask, position - 2);
169    FN(Store)(self, ringbuffer, ring_buffer_mask, position - 1);
170  }
171}
172
173static BROTLI_INLINE void FN(PrepareDistanceCache)(
174    HashForgetfulChain* BROTLI_RESTRICT self,
175    int* BROTLI_RESTRICT distance_cache) {
176  BROTLI_UNUSED(self);
177  PrepareDistanceCache(distance_cache, NUM_LAST_DISTANCES_TO_CHECK);
178}
179
180/* Find a longest backward match of &data[cur_ix] up to the length of
181   max_length and stores the position cur_ix in the hash table.
182
183   REQUIRES: FN(PrepareDistanceCache) must be invoked for current distance cache
184             values; if this method is invoked repeatedly with the same distance
185             cache values, it is enough to invoke FN(PrepareDistanceCache) once.
186
187   Does not look for matches longer than max_length.
188   Does not look for matches further away than max_backward.
189   Writes the best match into |out|.
190   |out|->score is updated only if a better match is found. */
191static BROTLI_INLINE void FN(FindLongestMatch)(
192    HashForgetfulChain* BROTLI_RESTRICT self,
193    const BrotliEncoderDictionary* dictionary,
194    const uint8_t* BROTLI_RESTRICT data, const size_t ring_buffer_mask,
195    const int* BROTLI_RESTRICT distance_cache,
196    const size_t cur_ix, const size_t max_length, const size_t max_backward,
197    const size_t dictionary_distance, const size_t max_distance,
198    HasherSearchResult* BROTLI_RESTRICT out) {
199  uint32_t* BROTLI_RESTRICT addr = FN(Addr)(self->extra);
200  uint16_t* BROTLI_RESTRICT head = FN(Head)(self->extra);
201  uint8_t* BROTLI_RESTRICT tiny_hashes = FN(TinyHash)(self->extra);
202  FN(Bank)* BROTLI_RESTRICT banks = FN(Banks)(self->extra);
203  const size_t cur_ix_masked = cur_ix & ring_buffer_mask;
204  /* Don't accept a short copy from far away. */
205  score_t min_score = out->score;
206  score_t best_score = out->score;
207  size_t best_len = out->len;
208  size_t i;
209  const size_t key = FN(HashBytes)(&data[cur_ix_masked]);
210  const uint8_t tiny_hash = (uint8_t)(key);
211  out->len = 0;
212  out->len_code_delta = 0;
213  /* Try last distance first. */
214  for (i = 0; i < NUM_LAST_DISTANCES_TO_CHECK; ++i) {
215    const size_t backward = (size_t)distance_cache[i];
216    size_t prev_ix = (cur_ix - backward);
217    /* For distance code 0 we want to consider 2-byte matches. */
218    if (i > 0 && tiny_hashes[(uint16_t)prev_ix] != tiny_hash) continue;
219    if (prev_ix >= cur_ix || backward > max_backward) {
220      continue;
221    }
222    prev_ix &= ring_buffer_mask;
223    {
224      const size_t len = FindMatchLengthWithLimit(&data[prev_ix],
225                                                  &data[cur_ix_masked],
226                                                  max_length);
227      if (len >= 2) {
228        score_t score = BackwardReferenceScoreUsingLastDistance(len);
229        if (best_score < score) {
230          if (i != 0) score -= BackwardReferencePenaltyUsingLastDistance(i);
231          if (best_score < score) {
232            best_score = score;
233            best_len = len;
234            out->len = best_len;
235            out->distance = backward;
236            out->score = best_score;
237          }
238        }
239      }
240    }
241  }
242  {
243    const size_t bank = key & (NUM_BANKS - 1);
244    size_t backward = 0;
245    size_t hops = self->max_hops;
246    size_t delta = cur_ix - addr[key];
247    size_t slot = head[key];
248    while (hops--) {
249      size_t prev_ix;
250      size_t last = slot;
251      backward += delta;
252      if (backward > max_backward || (CAPPED_CHAINS && !delta)) break;
253      prev_ix = (cur_ix - backward) & ring_buffer_mask;
254      slot = banks[bank].slots[last].next;
255      delta = banks[bank].slots[last].delta;
256      if (cur_ix_masked + best_len > ring_buffer_mask ||
257          prev_ix + best_len > ring_buffer_mask ||
258          data[cur_ix_masked + best_len] != data[prev_ix + best_len]) {
259        continue;
260      }
261      {
262        const size_t len = FindMatchLengthWithLimit(&data[prev_ix],
263                                                    &data[cur_ix_masked],
264                                                    max_length);
265        if (len >= 4) {
266          /* Comparing for >= 3 does not change the semantics, but just saves
267             for a few unnecessary binary logarithms in backward reference
268             score, since we are not interested in such short matches. */
269          score_t score = BackwardReferenceScore(len, backward);
270          if (best_score < score) {
271            best_score = score;
272            best_len = len;
273            out->len = best_len;
274            out->distance = backward;
275            out->score = best_score;
276          }
277        }
278      }
279    }
280    FN(Store)(self, data, ring_buffer_mask, cur_ix);
281  }
282  if (out->score == min_score) {
283    SearchInStaticDictionary(dictionary,
284        self->common, &data[cur_ix_masked], max_length, dictionary_distance,
285        max_distance, out, BROTLI_FALSE);
286  }
287}
288
289#undef BANK_SIZE
290#undef BUCKET_SIZE
291#undef CAPPED_CHAINS
292
293#undef HashForgetfulChain
294