BaseTools/Source/C/BrotliCompress/enc/hash.h

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