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

   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 */
   9
  10 /* A (forgetful) hash table to the data seen by the compressor, to
  11    help create backward references to previous data.
  12
  13    This is a hash map of fixed size (bucket_size_) to a ring buffer of
  14    fixed size (block_size_). The ring buffer contains the last block_size_
  15    index positions of the given hash key in the compressed data. */
  16
  17 #define HashLongestMatch HASHER()
  18
  19 static BROTLI_INLINE size_t FN(HashTypeLength)(void) { return 8; }
  20 static BROTLI_INLINE size_t FN(StoreLookahead)(void) { return 8; }
  21
  22 /* HashBytes is the function that chooses the bucket to place the address in. */
  23 static BROTLI_INLINE uint32_t FN(HashBytes)(const uint8_t* data,
  24                                             const uint64_t mask,
  25                                             const int shift) {
  26   const uint64_t h = (BROTLI_UNALIGNED_LOAD64LE(data) & mask) * kHashMul64Long;
  27   /* The higher bits contain more mixture from the multiplication,
  28      so we take our results from there. */
  29   return (uint32_t)(h >> shift);
  30 }
  31
  32 typedef struct HashLongestMatch {
  33   /* Number of hash buckets. */
  34   size_t bucket_size_;
  35   /* Only block_size_ newest backward references are kept,
  36      and the older are forgotten. */
  37   size_t block_size_;
  38   /* Left-shift for computing hash bucket index from hash value. */
  39   int hash_shift_;
  40   /* Mask for selecting the next 4-8 bytes of input */
  41   uint64_t hash_mask_;
  42   /* Mask for accessing entries in a block (in a ring-buffer manner). */
  43   uint32_t block_mask_;
  44
  45   /* --- Dynamic size members --- */
  46
  47   /* Number of entries in a particular bucket. */
  48   /* uint16_t num[bucket_size]; */
  49
  50   /* Buckets containing block_size_ of backward references. */
  51   /* uint32_t* buckets[bucket_size * block_size]; */
  52 } HashLongestMatch;
  53
  54 static BROTLI_INLINE HashLongestMatch* FN(Self)(HasherHandle handle) {
  55   return (HashLongestMatch*)&(GetHasherCommon(handle)[1]);
  56 }
  57
  58 static BROTLI_INLINE uint16_t* FN(Num)(HashLongestMatch* self) {
  59   return (uint16_t*)(&self[1]);
  60 }
  61
  62 static BROTLI_INLINE uint32_t* FN(Buckets)(HashLongestMatch* self) {
  63   return (uint32_t*)(&FN(Num)(self)[self->bucket_size_]);
  64 }
  65
  66 static void FN(Initialize)(
  67     HasherHandle handle, const BrotliEncoderParams* params) {
  68   HasherCommon* common = GetHasherCommon(handle);
  69   HashLongestMatch* self = FN(Self)(handle);
  70   BROTLI_UNUSED(params);
  71   self->hash_shift_ = 64 - common->params.bucket_bits;
  72   self->hash_mask_ = (~((uint64_t)0U)) >> (64 - 8 * common->params.hash_len);
  73   self->bucket_size_ = (size_t)1 << common->params.bucket_bits;
  74   self->block_size_ = (size_t)1 << common->params.block_bits;
  75   self->block_mask_ = (uint32_t)(self->block_size_ - 1);
  76 }
  77
  78 static void FN(Prepare)(HasherHandle handle, BROTLI_BOOL one_shot,
  79     size_t input_size, const uint8_t* data) {
  80   HashLongestMatch* self = FN(Self)(handle);
  81   uint16_t* num = FN(Num)(self);
  82   /* Partial preparation is 100 times slower (per socket). */
  83   size_t partial_prepare_threshold = self->bucket_size_ >> 6;
  84   if (one_shot && input_size <= partial_prepare_threshold) {
  85     size_t i;
  86     for (i = 0; i < input_size; ++i) {
  87       const uint32_t key = FN(HashBytes)(&data[i], self->hash_mask_,
  88                                          self->hash_shift_);
  89       num[key] = 0;
  90     }
  91   } else {
  92     memset(num, 0, self->bucket_size_ * sizeof(num[0]));
  93   }
  94 }
  95
  96 static BROTLI_INLINE size_t FN(HashMemAllocInBytes)(
  97     const BrotliEncoderParams* params, BROTLI_BOOL one_shot,
  98     size_t input_size) {
  99   size_t bucket_size = (size_t)1 << params->hasher.bucket_bits;
 100   size_t block_size = (size_t)1 << params->hasher.block_bits;
 101   BROTLI_UNUSED(one_shot);
 102   BROTLI_UNUSED(input_size);
 103   return sizeof(HashLongestMatch) + bucket_size * (2 + 4 * block_size);
 104 }
 105
 106 /* Look at 4 bytes at &data[ix & mask].
 107    Compute a hash from these, and store the value of ix at that position. */
 108 static BROTLI_INLINE void FN(Store)(HasherHandle handle, const uint8_t* data,
 109     const size_t mask, const size_t ix) {
 110   HashLongestMatch* self = FN(Self)(handle);
 111   uint16_t* num = FN(Num)(self);
 112   const uint32_t key = FN(HashBytes)(&data[ix & mask], self->hash_mask_,
 113                                      self->hash_shift_);
 114   const size_t minor_ix = num[key] & self->block_mask_;
 115   const size_t offset =
 116       minor_ix + (key << GetHasherCommon(handle)->params.block_bits);
 117   FN(Buckets)(self)[offset] = (uint32_t)ix;
 118   ++num[key];
 119 }
 120
 121 static BROTLI_INLINE void FN(StoreRange)(HasherHandle handle,
 122     const uint8_t* data, const size_t mask, const size_t ix_start,
 123     const size_t ix_end) {
 124   size_t i;
 125   for (i = ix_start; i < ix_end; ++i) {
 126     FN(Store)(handle, data, mask, i);
 127   }
 128 }
 129
 130 static BROTLI_INLINE void FN(StitchToPreviousBlock)(HasherHandle handle,
 131     size_t num_bytes, size_t position, const uint8_t* ringbuffer,
 132     size_t ringbuffer_mask) {
 133   if (num_bytes >= FN(HashTypeLength)() - 1 && position >= 3) {
 134     /* Prepare the hashes for three last bytes of the last write.
 135        These could not be calculated before, since they require knowledge
 136        of both the previous and the current block. */
 137     FN(Store)(handle, ringbuffer, ringbuffer_mask, position - 3);
 138     FN(Store)(handle, ringbuffer, ringbuffer_mask, position - 2);
 139     FN(Store)(handle, ringbuffer, ringbuffer_mask, position - 1);
 140   }
 141 }
 142
 143 static BROTLI_INLINE void FN(PrepareDistanceCache)(
 144     HasherHandle handle, int* BROTLI_RESTRICT distance_cache) {
 145   PrepareDistanceCache(distance_cache,
 146       GetHasherCommon(handle)->params.num_last_distances_to_check);
 147 }
 148
 149 /* Find a longest backward match of &data[cur_ix] up to the length of
 150    max_length and stores the position cur_ix in the hash table.
 151
 152    REQUIRES: FN(PrepareDistanceCache) must be invoked for current distance cache
 153              values; if this method is invoked repeatedly with the same distance
 154              cache values, it is enough to invoke FN(PrepareDistanceCache) once.
 155
 156    Does not look for matches longer than max_length.
 157    Does not look for matches further away than max_backward.
 158    Writes the best match into |out|.
 159    |out|->score is updated only if a better match is found. */
 160 static BROTLI_INLINE void FN(FindLongestMatch)(HasherHandle handle,
 161     const BrotliEncoderDictionary* dictionary,
 162     const uint8_t* BROTLI_RESTRICT data, const size_t ring_buffer_mask,
 163     const int* BROTLI_RESTRICT distance_cache, const size_t cur_ix,
 164     const size_t max_length, const size_t max_backward, const size_t gap,
 165     const size_t max_distance, HasherSearchResult* BROTLI_RESTRICT out) {
 166   HasherCommon* common = GetHasherCommon(handle);
 167   HashLongestMatch* self = FN(Self)(handle);
 168   uint16_t* num = FN(Num)(self);
 169   uint32_t* buckets = FN(Buckets)(self);
 170   const size_t cur_ix_masked = cur_ix & ring_buffer_mask;
 171   /* Don't accept a short copy from far away. */
 172   score_t min_score = out->score;
 173   score_t best_score = out->score;
 174   size_t best_len = out->len;
 175   size_t i;
 176   out->len = 0;
 177   out->len_code_delta = 0;
 178   /* Try last distance first. */
 179   for (i = 0; i < (size_t)common->params.num_last_distances_to_check; ++i) {
 180     const size_t backward = (size_t)distance_cache[i];
 181     size_t prev_ix = (size_t)(cur_ix - backward);
 182     if (prev_ix >= cur_ix) {
 183       continue;
 184     }
 185     if (BROTLI_PREDICT_FALSE(backward > max_backward)) {
 186       continue;
 187     }
 188     prev_ix &= ring_buffer_mask;
 189
 190     if (cur_ix_masked + best_len > ring_buffer_mask ||
 191         prev_ix + best_len > ring_buffer_mask ||
 192         data[cur_ix_masked + best_len] != data[prev_ix + best_len]) {
 193       continue;
 194     }
 195     {
 196       const size_t len = FindMatchLengthWithLimit(&data[prev_ix],
 197                                                   &data[cur_ix_masked],
 198                                                   max_length);
 199       if (len >= 3 || (len == 2 && i < 2)) {
 200         /* Comparing for >= 2 does not change the semantics, but just saves for
 201            a few unnecessary binary logarithms in backward reference score,
 202            since we are not interested in such short matches. */
 203         score_t score = BackwardReferenceScoreUsingLastDistance(len);
 204         if (best_score < score) {
 205           if (i != 0) score -= BackwardReferencePenaltyUsingLastDistance(i);
 206           if (best_score < score) {
 207             best_score = score;
 208             best_len = len;
 209             out->len = best_len;
 210             out->distance = backward;
 211             out->score = best_score;
 212           }
 213         }
 214       }
 215     }
 216   }
 217   {
 218     const uint32_t key = FN(HashBytes)(
 219         &data[cur_ix_masked], self->hash_mask_, self->hash_shift_);
 220     uint32_t* BROTLI_RESTRICT bucket =
 221         &buckets[key << common->params.block_bits];
 222     const size_t down =
 223         (num[key] > self->block_size_) ?
 224         (num[key] - self->block_size_) : 0u;
 225     for (i = num[key]; i > down;) {
 226       size_t prev_ix = bucket[--i & self->block_mask_];
 227       const size_t backward = cur_ix - prev_ix;
 228       if (BROTLI_PREDICT_FALSE(backward > max_backward)) {
 229         break;
 230       }
 231       prev_ix &= ring_buffer_mask;
 232       if (cur_ix_masked + best_len > ring_buffer_mask ||
 233           prev_ix + best_len > ring_buffer_mask ||
 234           data[cur_ix_masked + best_len] != data[prev_ix + best_len]) {
 235         continue;
 236       }
 237       {
 238         const size_t len = FindMatchLengthWithLimit(&data[prev_ix],
 239                                                     &data[cur_ix_masked],
 240                                                     max_length);
 241         if (len >= 4) {
 242           /* Comparing for >= 3 does not change the semantics, but just saves
 243              for a few unnecessary binary logarithms in backward reference
 244              score, since we are not interested in such short matches. */
 245           score_t score = BackwardReferenceScore(len, backward);
 246           if (best_score < score) {
 247             best_score = score;
 248             best_len = len;
 249             out->len = best_len;
 250             out->distance = backward;
 251             out->score = best_score;
 252           }
 253         }
 254       }
 255     }
 256     bucket[num[key] & self->block_mask_] = (uint32_t)cur_ix;
 257     ++num[key];
 258   }
 259   if (min_score == out->score) {
 260     SearchInStaticDictionary(dictionary,
 261         handle, &data[cur_ix_masked], max_length, max_backward + gap,
 262         max_distance, out, BROTLI_FALSE);
 263   }
 264 }
 265
 266 #undef HashLongestMatch