--- /dev/null
+/* NOLINT(build/header_guard) */\r
+/* Copyright 2010 Google Inc. All Rights Reserved.\r
+\r
+ Distributed under MIT license.\r
+ See file LICENSE for detail or copy at https://opensource.org/licenses/MIT\r
+*/\r
+\r
+/* template parameters: FN, BUCKET_BITS, BUCKET_SWEEP, USE_DICTIONARY */\r
+\r
+#define HashLongestMatchQuickly HASHER()\r
+\r
+#define BUCKET_SIZE (1 << BUCKET_BITS)\r
+\r
+#define HASH_MAP_SIZE (4 << BUCKET_BITS)\r
+\r
+static BROTLI_INLINE size_t FN(HashTypeLength)(void) { return 8; }\r
+static BROTLI_INLINE size_t FN(StoreLookahead)(void) { return 8; }\r
+\r
+/* HashBytes is the function that chooses the bucket to place\r
+ the address in. The HashLongestMatch and HashLongestMatchQuickly\r
+ classes have separate, different implementations of hashing. */\r
+static uint32_t FN(HashBytes)(const uint8_t *data) {\r
+ /* Computing a hash based on 5 bytes works much better for\r
+ qualities 1 and 3, where the next hash value is likely to replace */\r
+ uint64_t h = (BROTLI_UNALIGNED_LOAD64(data) << 24) * kHashMul32;\r
+ /* The higher bits contain more mixture from the multiplication,\r
+ so we take our results from there. */\r
+ return (uint32_t)(h >> (64 - BUCKET_BITS));\r
+}\r
+\r
+/* A (forgetful) hash table to the data seen by the compressor, to\r
+ help create backward references to previous data.\r
+\r
+ This is a hash map of fixed size (BUCKET_SIZE). Starting from the\r
+ given index, BUCKET_SWEEP buckets are used to store values of a key. */\r
+typedef struct HashLongestMatchQuickly {\r
+ uint32_t buckets_[BUCKET_SIZE + BUCKET_SWEEP];\r
+ /* True if buckets_ array needs to be initialized. */\r
+ BROTLI_BOOL is_dirty_;\r
+ DictionarySearchStatictics dict_search_stats_;\r
+} HashLongestMatchQuickly;\r
+\r
+static void FN(Reset)(HashLongestMatchQuickly* self) {\r
+ self->is_dirty_ = BROTLI_TRUE;\r
+ DictionarySearchStaticticsReset(&self->dict_search_stats_);\r
+}\r
+\r
+static void FN(InitEmpty)(HashLongestMatchQuickly* self) {\r
+ if (self->is_dirty_) {\r
+ /* It is not strictly necessary to fill this buffer here, but\r
+ not filling will make the results of the compression stochastic\r
+ (but correct). This is because random data would cause the\r
+ system to find accidentally good backward references here and there. */\r
+ memset(&self->buckets_[0], 0, sizeof(self->buckets_));\r
+ self->is_dirty_ = BROTLI_FALSE;\r
+ }\r
+}\r
+\r
+static void FN(InitForData)(HashLongestMatchQuickly* self, const uint8_t* data,\r
+ size_t num) {\r
+ size_t i;\r
+ for (i = 0; i < num; ++i) {\r
+ const uint32_t key = FN(HashBytes)(&data[i]);\r
+ memset(&self->buckets_[key], 0, BUCKET_SWEEP * sizeof(self->buckets_[0]));\r
+ }\r
+ if (num != 0) {\r
+ self->is_dirty_ = BROTLI_FALSE;\r
+ }\r
+}\r
+\r
+static void FN(Init)(\r
+ MemoryManager* m, HashLongestMatchQuickly* self, const uint8_t* data,\r
+ const BrotliEncoderParams* params, size_t position, size_t bytes,\r
+ BROTLI_BOOL is_last) {\r
+ /* Choose which init method is faster.\r
+ Init() is about 100 times faster than InitForData(). */\r
+ const size_t kMaxBytesForPartialHashInit = HASH_MAP_SIZE >> 7;\r
+ BROTLI_UNUSED(m);\r
+ BROTLI_UNUSED(params);\r
+ if (position == 0 && is_last && bytes <= kMaxBytesForPartialHashInit) {\r
+ FN(InitForData)(self, data, bytes);\r
+ } else {\r
+ FN(InitEmpty)(self);\r
+ }\r
+}\r
+\r
+/* Look at 5 bytes at &data[ix & mask].\r
+ Compute a hash from these, and store the value somewhere within\r
+ [ix .. ix+3]. */\r
+static BROTLI_INLINE void FN(Store)(HashLongestMatchQuickly* self,\r
+ const uint8_t *data, const size_t mask, const size_t ix) {\r
+ const uint32_t key = FN(HashBytes)(&data[ix & mask]);\r
+ /* Wiggle the value with the bucket sweep range. */\r
+ const uint32_t off = (ix >> 3) % BUCKET_SWEEP;\r
+ self->buckets_[key + off] = (uint32_t)ix;\r
+}\r
+\r
+static BROTLI_INLINE void FN(StoreRange)(HashLongestMatchQuickly* self,\r
+ const uint8_t *data, const size_t mask, const size_t ix_start,\r
+ const size_t ix_end) {\r
+ size_t i;\r
+ for (i = ix_start; i < ix_end; ++i) {\r
+ FN(Store)(self, data, mask, i);\r
+ }\r
+}\r
+\r
+static BROTLI_INLINE void FN(StitchToPreviousBlock)(\r
+ HashLongestMatchQuickly* self, size_t num_bytes, size_t position,\r
+ const uint8_t* ringbuffer, size_t ringbuffer_mask) {\r
+ if (num_bytes >= FN(HashTypeLength)() - 1 && position >= 3) {\r
+ /* Prepare the hashes for three last bytes of the last write.\r
+ These could not be calculated before, since they require knowledge\r
+ of both the previous and the current block. */\r
+ FN(Store)(self, ringbuffer, ringbuffer_mask, position - 3);\r
+ FN(Store)(self, ringbuffer, ringbuffer_mask, position - 2);\r
+ FN(Store)(self, ringbuffer, ringbuffer_mask, position - 1);\r
+ }\r
+}\r
+\r
+/* Find a longest backward match of &data[cur_ix & ring_buffer_mask]\r
+ up to the length of max_length and stores the position cur_ix in the\r
+ hash table.\r
+\r
+ Does not look for matches longer than max_length.\r
+ Does not look for matches further away than max_backward.\r
+ Writes the best match into |out|.\r
+ Returns true if match is found, otherwise false. */\r
+static BROTLI_INLINE BROTLI_BOOL FN(FindLongestMatch)(\r
+ HashLongestMatchQuickly* self, const uint8_t* BROTLI_RESTRICT data,\r
+ const size_t ring_buffer_mask, const int* BROTLI_RESTRICT distance_cache,\r
+ const size_t cur_ix, const size_t max_length, const size_t max_backward,\r
+ HasherSearchResult* BROTLI_RESTRICT out) {\r
+ const size_t best_len_in = out->len;\r
+ const size_t cur_ix_masked = cur_ix & ring_buffer_mask;\r
+ const uint32_t key = FN(HashBytes)(&data[cur_ix_masked]);\r
+ int compare_char = data[cur_ix_masked + best_len_in];\r
+ score_t best_score = out->score;\r
+ size_t best_len = best_len_in;\r
+ size_t cached_backward = (size_t)distance_cache[0];\r
+ size_t prev_ix = cur_ix - cached_backward;\r
+ BROTLI_BOOL is_match_found = BROTLI_FALSE;\r
+ out->len_x_code = 0;\r
+ if (prev_ix < cur_ix) {\r
+ prev_ix &= (uint32_t)ring_buffer_mask;\r
+ if (compare_char == data[prev_ix + best_len]) {\r
+ size_t len = FindMatchLengthWithLimit(&data[prev_ix],\r
+ &data[cur_ix_masked],\r
+ max_length);\r
+ if (len >= 4) {\r
+ best_score = BackwardReferenceScoreUsingLastDistance(len, 0);\r
+ best_len = len;\r
+ out->len = len;\r
+ out->distance = cached_backward;\r
+ out->score = best_score;\r
+ compare_char = data[cur_ix_masked + best_len];\r
+ if (BUCKET_SWEEP == 1) {\r
+ self->buckets_[key] = (uint32_t)cur_ix;\r
+ return BROTLI_TRUE;\r
+ } else {\r
+ is_match_found = BROTLI_TRUE;\r
+ }\r
+ }\r
+ }\r
+ }\r
+ if (BUCKET_SWEEP == 1) {\r
+ size_t backward;\r
+ size_t len;\r
+ /* Only one to look for, don't bother to prepare for a loop. */\r
+ prev_ix = self->buckets_[key];\r
+ self->buckets_[key] = (uint32_t)cur_ix;\r
+ backward = cur_ix - prev_ix;\r
+ prev_ix &= (uint32_t)ring_buffer_mask;\r
+ if (compare_char != data[prev_ix + best_len_in]) {\r
+ return BROTLI_FALSE;\r
+ }\r
+ if (PREDICT_FALSE(backward == 0 || backward > max_backward)) {\r
+ return BROTLI_FALSE;\r
+ }\r
+ len = FindMatchLengthWithLimit(&data[prev_ix],\r
+ &data[cur_ix_masked],\r
+ max_length);\r
+ if (len >= 4) {\r
+ out->len = len;\r
+ out->distance = backward;\r
+ out->score = BackwardReferenceScore(len, backward);\r
+ return BROTLI_TRUE;\r
+ }\r
+ } else {\r
+ uint32_t *bucket = self->buckets_ + key;\r
+ int i;\r
+ prev_ix = *bucket++;\r
+ for (i = 0; i < BUCKET_SWEEP; ++i, prev_ix = *bucket++) {\r
+ const size_t backward = cur_ix - prev_ix;\r
+ size_t len;\r
+ prev_ix &= (uint32_t)ring_buffer_mask;\r
+ if (compare_char != data[prev_ix + best_len]) {\r
+ continue;\r
+ }\r
+ if (PREDICT_FALSE(backward == 0 || backward > max_backward)) {\r
+ continue;\r
+ }\r
+ len = FindMatchLengthWithLimit(&data[prev_ix],\r
+ &data[cur_ix_masked],\r
+ max_length);\r
+ if (len >= 4) {\r
+ const score_t score = BackwardReferenceScore(len, backward);\r
+ if (best_score < score) {\r
+ best_score = score;\r
+ best_len = len;\r
+ out->len = best_len;\r
+ out->distance = backward;\r
+ out->score = score;\r
+ compare_char = data[cur_ix_masked + best_len];\r
+ is_match_found = BROTLI_TRUE;\r
+ }\r
+ }\r
+ }\r
+ }\r
+ if (USE_DICTIONARY && !is_match_found) {\r
+ is_match_found = SearchInStaticDictionary(&self->dict_search_stats_,\r
+ &data[cur_ix_masked], max_length, max_backward, out, BROTLI_TRUE);\r
+ }\r
+ self->buckets_[key + ((cur_ix >> 3) % BUCKET_SWEEP)] = (uint32_t)cur_ix;\r
+ return is_match_found;\r
+}\r
+\r
+#undef HASH_MAP_SIZE\r
+#undef BUCKET_SIZE\r
+\r
+#undef HashLongestMatchQuickly\r
projects / mirror_edk2.git / blobdiff