1 /* Copyright 2010 Google Inc. All Rights Reserved.
2 
3    Distributed under MIT license.
4    See file LICENSE for detail or copy at https://opensource.org/licenses/MIT
5 */
6 
7 /* A (forgetful) hash table to the data seen by the compressor, to
8    help create backward references to previous data. */
9 
10 #ifndef BROTLI_ENC_HASH_H_
11 #define BROTLI_ENC_HASH_H_
12 
13 #include <string.h>  /* memcmp, memset */
14 
15 #include "../common/constants.h"
16 #include "../common/dictionary.h"
17 #include "../common/platform.h"
18 #include <brotli/types.h>
19 #include "./encoder_dict.h"
20 #include "./fast_log.h"
21 #include "./find_match_length.h"
22 #include "./memory.h"
23 #include "./quality.h"
24 #include "./static_dict.h"
25 
26 #if defined(__cplusplus) || defined(c_plusplus)
27 extern "C" {
28 #endif
29 
30 typedef struct {
31   /* Dynamically allocated area; first member for quickest access. */
32   void* extra;
33 
34   size_t dict_num_lookups;
35   size_t dict_num_matches;
36 
37   BrotliHasherParams params;
38 
39   /* False if hasher needs to be "prepared" before use. */
40   BROTLI_BOOL is_prepared_;
41 } HasherCommon;
42 
43 #define score_t size_t
44 
45 static const uint32_t kCutoffTransformsCount = 10;
46 /*   0,  12,   27,    23,    42,    63,    56,    48,    59,    64 */
47 /* 0+0, 4+8, 8+19, 12+11, 16+26, 20+43, 24+32, 28+20, 32+27, 36+28 */
48 static const uint64_t kCutoffTransforms =
49     BROTLI_MAKE_UINT64_T(0x071B520A, 0xDA2D3200);
50 
51 typedef struct HasherSearchResult {
52   size_t len;
53   size_t distance;
54   score_t score;
55   int len_code_delta; /* == len_code - len */
56 } HasherSearchResult;
57 
58 /* kHashMul32 multiplier has these properties:
59    * The multiplier must be odd. Otherwise we may lose the highest bit.
60    * No long streaks of ones or zeros.
61    * There is no effort to ensure that it is a prime, the oddity is enough
62      for this use.
63    * The number has been tuned heuristically against compression benchmarks. */
64 static const uint32_t kHashMul32 = 0x1E35A7BD;
65 static const uint64_t kHashMul64 = BROTLI_MAKE_UINT64_T(0x1E35A7BD, 0x1E35A7BD);
66 static const uint64_t kHashMul64Long =
67     BROTLI_MAKE_UINT64_T(0x1FE35A7Bu, 0xD3579BD3u);
68 
Hash14(const uint8_t * data)69 static BROTLI_INLINE uint32_t Hash14(const uint8_t* data) {
70   uint32_t h = BROTLI_UNALIGNED_LOAD32LE(data) * kHashMul32;
71   /* The higher bits contain more mixture from the multiplication,
72      so we take our results from there. */
73   return h >> (32 - 14);
74 }
75 
PrepareDistanceCache(int * BROTLI_RESTRICT distance_cache,const int num_distances)76 static BROTLI_INLINE void PrepareDistanceCache(
77     int* BROTLI_RESTRICT distance_cache, const int num_distances) {
78   if (num_distances > 4) {
79     int last_distance = distance_cache[0];
80     distance_cache[4] = last_distance - 1;
81     distance_cache[5] = last_distance + 1;
82     distance_cache[6] = last_distance - 2;
83     distance_cache[7] = last_distance + 2;
84     distance_cache[8] = last_distance - 3;
85     distance_cache[9] = last_distance + 3;
86     if (num_distances > 10) {
87       int next_last_distance = distance_cache[1];
88       distance_cache[10] = next_last_distance - 1;
89       distance_cache[11] = next_last_distance + 1;
90       distance_cache[12] = next_last_distance - 2;
91       distance_cache[13] = next_last_distance + 2;
92       distance_cache[14] = next_last_distance - 3;
93       distance_cache[15] = next_last_distance + 3;
94     }
95   }
96 }
97 
98 #define BROTLI_LITERAL_BYTE_SCORE 135
99 #define BROTLI_DISTANCE_BIT_PENALTY 30
100 /* Score must be positive after applying maximal penalty. */
101 #define BROTLI_SCORE_BASE (BROTLI_DISTANCE_BIT_PENALTY * 8 * sizeof(size_t))
102 
103 /* Usually, we always choose the longest backward reference. This function
104    allows for the exception of that rule.
105 
106    If we choose a backward reference that is further away, it will
107    usually be coded with more bits. We approximate this by assuming
108    log2(distance). If the distance can be expressed in terms of the
109    last four distances, we use some heuristic constants to estimate
110    the bits cost. For the first up to four literals we use the bit
111    cost of the literals from the literal cost model, after that we
112    use the average bit cost of the cost model.
113 
114    This function is used to sometimes discard a longer backward reference
115    when it is not much longer and the bit cost for encoding it is more
116    than the saved literals.
117 
118    backward_reference_offset MUST be positive. */
BackwardReferenceScore(size_t copy_length,size_t backward_reference_offset)119 static BROTLI_INLINE score_t BackwardReferenceScore(
120     size_t copy_length, size_t backward_reference_offset) {
121   return BROTLI_SCORE_BASE + BROTLI_LITERAL_BYTE_SCORE * (score_t)copy_length -
122       BROTLI_DISTANCE_BIT_PENALTY * Log2FloorNonZero(backward_reference_offset);
123 }
124 
BackwardReferenceScoreUsingLastDistance(size_t copy_length)125 static BROTLI_INLINE score_t BackwardReferenceScoreUsingLastDistance(
126     size_t copy_length) {
127   return BROTLI_LITERAL_BYTE_SCORE * (score_t)copy_length +
128       BROTLI_SCORE_BASE + 15;
129 }
130 
BackwardReferencePenaltyUsingLastDistance(size_t distance_short_code)131 static BROTLI_INLINE score_t BackwardReferencePenaltyUsingLastDistance(
132     size_t distance_short_code) {
133   return (score_t)39 + ((0x1CA10 >> (distance_short_code & 0xE)) & 0xE);
134 }
135 
TestStaticDictionaryItem(const BrotliEncoderDictionary * dictionary,size_t len,size_t word_idx,const uint8_t * data,size_t max_length,size_t max_backward,size_t max_distance,HasherSearchResult * out)136 static BROTLI_INLINE BROTLI_BOOL TestStaticDictionaryItem(
137     const BrotliEncoderDictionary* dictionary, size_t len, size_t word_idx,
138     const uint8_t* data, size_t max_length, size_t max_backward,
139     size_t max_distance, HasherSearchResult* out) {
140   size_t offset;
141   size_t matchlen;
142   size_t backward;
143   score_t score;
144   offset = dictionary->words->offsets_by_length[len] + len * word_idx;
145   if (len > max_length) {
146     return BROTLI_FALSE;
147   }
148 
149   matchlen =
150       FindMatchLengthWithLimit(data, &dictionary->words->data[offset], len);
151   if (matchlen + dictionary->cutoffTransformsCount <= len || matchlen == 0) {
152     return BROTLI_FALSE;
153   }
154   {
155     size_t cut = len - matchlen;
156     size_t transform_id = (cut << 2) +
157         (size_t)((dictionary->cutoffTransforms >> (cut * 6)) & 0x3F);
158     backward = max_backward + 1 + word_idx +
159         (transform_id << dictionary->words->size_bits_by_length[len]);
160   }
161   if (backward > max_distance) {
162     return BROTLI_FALSE;
163   }
164   score = BackwardReferenceScore(matchlen, backward);
165   if (score < out->score) {
166     return BROTLI_FALSE;
167   }
168   out->len = matchlen;
169   out->len_code_delta = (int)len - (int)matchlen;
170   out->distance = backward;
171   out->score = score;
172   return BROTLI_TRUE;
173 }
174 
SearchInStaticDictionary(const BrotliEncoderDictionary * dictionary,HasherCommon * common,const uint8_t * data,size_t max_length,size_t max_backward,size_t max_distance,HasherSearchResult * out,BROTLI_BOOL shallow)175 static BROTLI_INLINE void SearchInStaticDictionary(
176     const BrotliEncoderDictionary* dictionary,
177     HasherCommon* common, const uint8_t* data, size_t max_length,
178     size_t max_backward, size_t max_distance,
179     HasherSearchResult* out, BROTLI_BOOL shallow) {
180   size_t key;
181   size_t i;
182   if (common->dict_num_matches < (common->dict_num_lookups >> 7)) {
183     return;
184   }
185   key = Hash14(data) << 1;
186   for (i = 0; i < (shallow ? 1u : 2u); ++i, ++key) {
187     common->dict_num_lookups++;
188     if (dictionary->hash_table_lengths[key] != 0) {
189       BROTLI_BOOL item_matches = TestStaticDictionaryItem(
190           dictionary, dictionary->hash_table_lengths[key],
191           dictionary->hash_table_words[key], data,
192           max_length, max_backward, max_distance, out);
193       if (item_matches) {
194         common->dict_num_matches++;
195       }
196     }
197   }
198 }
199 
200 typedef struct BackwardMatch {
201   uint32_t distance;
202   uint32_t length_and_code;
203 } BackwardMatch;
204 
InitBackwardMatch(BackwardMatch * self,size_t dist,size_t len)205 static BROTLI_INLINE void InitBackwardMatch(BackwardMatch* self,
206     size_t dist, size_t len) {
207   self->distance = (uint32_t)dist;
208   self->length_and_code = (uint32_t)(len << 5);
209 }
210 
InitDictionaryBackwardMatch(BackwardMatch * self,size_t dist,size_t len,size_t len_code)211 static BROTLI_INLINE void InitDictionaryBackwardMatch(BackwardMatch* self,
212     size_t dist, size_t len, size_t len_code) {
213   self->distance = (uint32_t)dist;
214   self->length_and_code =
215       (uint32_t)((len << 5) | (len == len_code ? 0 : len_code));
216 }
217 
BackwardMatchLength(const BackwardMatch * self)218 static BROTLI_INLINE size_t BackwardMatchLength(const BackwardMatch* self) {
219   return self->length_and_code >> 5;
220 }
221 
BackwardMatchLengthCode(const BackwardMatch * self)222 static BROTLI_INLINE size_t BackwardMatchLengthCode(const BackwardMatch* self) {
223   size_t code = self->length_and_code & 31;
224   return code ? code : BackwardMatchLength(self);
225 }
226 
227 #define EXPAND_CAT(a, b) CAT(a, b)
228 #define CAT(a, b) a ## b
229 #define FN(X) EXPAND_CAT(X, HASHER())
230 
231 #define HASHER() H10
232 #define BUCKET_BITS 17
233 #define MAX_TREE_SEARCH_DEPTH 64
234 #define MAX_TREE_COMP_LENGTH 128
235 #include "./hash_to_binary_tree_inc.h"  /* NOLINT(build/include) */
236 #undef MAX_TREE_SEARCH_DEPTH
237 #undef MAX_TREE_COMP_LENGTH
238 #undef BUCKET_BITS
239 #undef HASHER
240 /* MAX_NUM_MATCHES == 64 + MAX_TREE_SEARCH_DEPTH */
241 #define MAX_NUM_MATCHES_H10 128
242 
243 /* For BUCKET_SWEEP_BITS == 0, enabling the dictionary lookup makes compression
244    a little faster (0.5% - 1%) and it compresses 0.15% better on small text
245    and HTML inputs. */
246 
247 #define HASHER() H2
248 #define BUCKET_BITS 16
249 #define BUCKET_SWEEP_BITS 0
250 #define HASH_LEN 5
251 #define USE_DICTIONARY 1
252 #include "./hash_longest_match_quickly_inc.h"  /* NOLINT(build/include) */
253 #undef BUCKET_SWEEP_BITS
254 #undef USE_DICTIONARY
255 #undef HASHER
256 
257 #define HASHER() H3
258 #define BUCKET_SWEEP_BITS 1
259 #define USE_DICTIONARY 0
260 #include "./hash_longest_match_quickly_inc.h"  /* NOLINT(build/include) */
261 #undef USE_DICTIONARY
262 #undef BUCKET_SWEEP_BITS
263 #undef BUCKET_BITS
264 #undef HASHER
265 
266 #define HASHER() H4
267 #define BUCKET_BITS 17
268 #define BUCKET_SWEEP_BITS 2
269 #define USE_DICTIONARY 1
270 #include "./hash_longest_match_quickly_inc.h"  /* NOLINT(build/include) */
271 #undef USE_DICTIONARY
272 #undef HASH_LEN
273 #undef BUCKET_SWEEP_BITS
274 #undef BUCKET_BITS
275 #undef HASHER
276 
277 #define HASHER() H5
278 #include "./hash_longest_match_inc.h"  /* NOLINT(build/include) */
279 #undef HASHER
280 
281 #define HASHER() H6
282 #include "./hash_longest_match64_inc.h"  /* NOLINT(build/include) */
283 #undef HASHER
284 
285 #define BUCKET_BITS 15
286 
287 #define NUM_LAST_DISTANCES_TO_CHECK 4
288 #define NUM_BANKS 1
289 #define BANK_BITS 16
290 #define HASHER() H40
291 #include "./hash_forgetful_chain_inc.h"  /* NOLINT(build/include) */
292 #undef HASHER
293 #undef NUM_LAST_DISTANCES_TO_CHECK
294 
295 #define NUM_LAST_DISTANCES_TO_CHECK 10
296 #define HASHER() H41
297 #include "./hash_forgetful_chain_inc.h"  /* NOLINT(build/include) */
298 #undef HASHER
299 #undef NUM_LAST_DISTANCES_TO_CHECK
300 #undef NUM_BANKS
301 #undef BANK_BITS
302 
303 #define NUM_LAST_DISTANCES_TO_CHECK 16
304 #define NUM_BANKS 512
305 #define BANK_BITS 9
306 #define HASHER() H42
307 #include "./hash_forgetful_chain_inc.h"  /* NOLINT(build/include) */
308 #undef HASHER
309 #undef NUM_LAST_DISTANCES_TO_CHECK
310 #undef NUM_BANKS
311 #undef BANK_BITS
312 
313 #undef BUCKET_BITS
314 
315 #define HASHER() H54
316 #define BUCKET_BITS 20
317 #define BUCKET_SWEEP_BITS 2
318 #define HASH_LEN 7
319 #define USE_DICTIONARY 0
320 #include "./hash_longest_match_quickly_inc.h"  /* NOLINT(build/include) */
321 #undef USE_DICTIONARY
322 #undef HASH_LEN
323 #undef BUCKET_SWEEP_BITS
324 #undef BUCKET_BITS
325 #undef HASHER
326 
327 /* fast large window hashers */
328 
329 #define HASHER() HROLLING_FAST
330 #define CHUNKLEN 32
331 #define JUMP 4
332 #define NUMBUCKETS 16777216
333 #define MASK ((NUMBUCKETS * 64) - 1)
334 #include "./hash_rolling_inc.h"  /* NOLINT(build/include) */
335 #undef JUMP
336 #undef HASHER
337 
338 
339 #define HASHER() HROLLING
340 #define JUMP 1
341 #include "./hash_rolling_inc.h"  /* NOLINT(build/include) */
342 #undef MASK
343 #undef NUMBUCKETS
344 #undef JUMP
345 #undef CHUNKLEN
346 #undef HASHER
347 
348 #define HASHER() H35
349 #define HASHER_A H3
350 #define HASHER_B HROLLING_FAST
351 #include "./hash_composite_inc.h"  /* NOLINT(build/include) */
352 #undef HASHER_A
353 #undef HASHER_B
354 #undef HASHER
355 
356 #define HASHER() H55
357 #define HASHER_A H54
358 #define HASHER_B HROLLING_FAST
359 #include "./hash_composite_inc.h"  /* NOLINT(build/include) */
360 #undef HASHER_A
361 #undef HASHER_B
362 #undef HASHER
363 
364 #define HASHER() H65
365 #define HASHER_A H6
366 #define HASHER_B HROLLING
367 #include "./hash_composite_inc.h"  /* NOLINT(build/include) */
368 #undef HASHER_A
369 #undef HASHER_B
370 #undef HASHER
371 
372 #undef FN
373 #undef CAT
374 #undef EXPAND_CAT
375 
376 #define FOR_SIMPLE_HASHERS(H) H(2) H(3) H(4) H(5) H(6) H(40) H(41) H(42) H(54)
377 #define FOR_COMPOSITE_HASHERS(H) H(35) H(55) H(65)
378 #define FOR_GENERIC_HASHERS(H) FOR_SIMPLE_HASHERS(H) FOR_COMPOSITE_HASHERS(H)
379 #define FOR_ALL_HASHERS(H) FOR_GENERIC_HASHERS(H) H(10)
380 
381 typedef struct {
382   HasherCommon common;
383 
384   union {
385 #define MEMBER_(N) \
386     H ## N _H ## N;
387     FOR_ALL_HASHERS(MEMBER_)
388 #undef MEMBER_
389   } privat;
390 } Hasher;
391 
392 /* MUST be invoked before any other method. */
HasherInit(Hasher * hasher)393 static BROTLI_INLINE void HasherInit(Hasher* hasher) {
394   hasher->common.extra = NULL;
395 }
396 
DestroyHasher(MemoryManager * m,Hasher * hasher)397 static BROTLI_INLINE void DestroyHasher(MemoryManager* m, Hasher* hasher) {
398   if (hasher->common.extra == NULL) return;
399   BROTLI_FREE(m, hasher->common.extra);
400 }
401 
HasherReset(Hasher * hasher)402 static BROTLI_INLINE void HasherReset(Hasher* hasher) {
403   hasher->common.is_prepared_ = BROTLI_FALSE;
404 }
405 
HasherSize(const BrotliEncoderParams * params,BROTLI_BOOL one_shot,const size_t input_size)406 static BROTLI_INLINE size_t HasherSize(const BrotliEncoderParams* params,
407     BROTLI_BOOL one_shot, const size_t input_size) {
408   switch (params->hasher.type) {
409 #define SIZE_(N)                                                      \
410     case N:                                                           \
411       return HashMemAllocInBytesH ## N(params, one_shot, input_size);
412     FOR_ALL_HASHERS(SIZE_)
413 #undef SIZE_
414     default:
415       break;
416   }
417   return 0;  /* Default case. */
418 }
419 
HasherSetup(MemoryManager * m,Hasher * hasher,BrotliEncoderParams * params,const uint8_t * data,size_t position,size_t input_size,BROTLI_BOOL is_last)420 static BROTLI_INLINE void HasherSetup(MemoryManager* m, Hasher* hasher,
421     BrotliEncoderParams* params, const uint8_t* data, size_t position,
422     size_t input_size, BROTLI_BOOL is_last) {
423   BROTLI_BOOL one_shot = (position == 0 && is_last);
424   if (hasher->common.extra == NULL) {
425     size_t alloc_size;
426     ChooseHasher(params, &params->hasher);
427     alloc_size = HasherSize(params, one_shot, input_size);
428     hasher->common.extra = BROTLI_ALLOC(m, uint8_t, alloc_size);
429     if (BROTLI_IS_OOM(m) || BROTLI_IS_NULL(hasher->common.extra)) return;
430     hasher->common.params = params->hasher;
431     switch (hasher->common.params.type) {
432 #define INITIALIZE_(N)                        \
433       case N:                                 \
434         InitializeH ## N(&hasher->common,     \
435             &hasher->privat._H ## N, params); \
436         break;
437       FOR_ALL_HASHERS(INITIALIZE_);
438 #undef INITIALIZE_
439       default:
440         break;
441     }
442     HasherReset(hasher);
443   }
444 
445   if (!hasher->common.is_prepared_) {
446     switch (hasher->common.params.type) {
447 #define PREPARE_(N)                      \
448       case N:                            \
449         PrepareH ## N(                   \
450             &hasher->privat._H ## N,     \
451             one_shot, input_size, data); \
452         break;
453       FOR_ALL_HASHERS(PREPARE_)
454 #undef PREPARE_
455       default: break;
456     }
457     if (position == 0) {
458       hasher->common.dict_num_lookups = 0;
459       hasher->common.dict_num_matches = 0;
460     }
461     hasher->common.is_prepared_ = BROTLI_TRUE;
462   }
463 }
464 
InitOrStitchToPreviousBlock(MemoryManager * m,Hasher * hasher,const uint8_t * data,size_t mask,BrotliEncoderParams * params,size_t position,size_t input_size,BROTLI_BOOL is_last)465 static BROTLI_INLINE void InitOrStitchToPreviousBlock(
466     MemoryManager* m, Hasher* hasher, const uint8_t* data, size_t mask,
467     BrotliEncoderParams* params, size_t position, size_t input_size,
468     BROTLI_BOOL is_last) {
469   HasherSetup(m, hasher, params, data, position, input_size, is_last);
470   if (BROTLI_IS_OOM(m)) return;
471   switch (hasher->common.params.type) {
472 #define INIT_(N)                             \
473     case N:                                  \
474       StitchToPreviousBlockH ## N(           \
475           &hasher->privat._H ## N,           \
476           input_size, position, data, mask); \
477     break;
478     FOR_ALL_HASHERS(INIT_)
479 #undef INIT_
480     default: break;
481   }
482 }
483 
484 #if defined(__cplusplus) || defined(c_plusplus)
485 }  /* extern "C" */
486 #endif
487 
488 #endif  /* BROTLI_ENC_HASH_H_ */
489