--- /dev/null
+/* NOLINT(build/header_guard) */\r
+/* Copyright 2016 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, MAX_TREE_COMP_LENGTH,\r
+ MAX_TREE_SEARCH_DEPTH */\r
+\r
+/* A (forgetful) hash table where each hash bucket contains a binary tree of\r
+ sequences whose first 4 bytes share the same hash code.\r
+ Each sequence is MAX_TREE_COMP_LENGTH long and is identified by its starting\r
+ position in the input data. The binary tree is sorted by the lexicographic\r
+ order of the sequences, and it is also a max-heap with respect to the\r
+ starting positions. */\r
+\r
+#define HashToBinaryTree HASHER()\r
+\r
+#define BUCKET_SIZE (1 << BUCKET_BITS)\r
+\r
+static BROTLI_INLINE size_t FN(HashTypeLength)(void) { return 4; }\r
+static BROTLI_INLINE size_t FN(StoreLookahead)(void) {\r
+ return MAX_TREE_COMP_LENGTH;\r
+}\r
+\r
+static uint32_t FN(HashBytes)(const uint8_t* data) {\r
+ uint32_t h = BROTLI_UNALIGNED_LOAD32LE(data) * kHashMul32;\r
+ /* The higher bits contain more mixture from the multiplication,\r
+ so we take our results from there. */\r
+ return h >> (32 - BUCKET_BITS);\r
+}\r
+\r
+typedef struct HashToBinaryTree {\r
+ /* The window size minus 1 */\r
+ size_t window_mask_;\r
+\r
+ /* Hash table that maps the 4-byte hashes of the sequence to the last\r
+ position where this hash was found, which is the root of the binary\r
+ tree of sequences that share this hash bucket. */\r
+ uint32_t buckets_[BUCKET_SIZE];\r
+\r
+ /* A position used to mark a non-existent sequence, i.e. a tree is empty if\r
+ its root is at invalid_pos_ and a node is a leaf if both its children\r
+ are at invalid_pos_. */\r
+ uint32_t invalid_pos_;\r
+\r
+ /* --- Dynamic size members --- */\r
+\r
+ /* The union of the binary trees of each hash bucket. The root of the tree\r
+ corresponding to a hash is a sequence starting at buckets_[hash] and\r
+ the left and right children of a sequence starting at pos are\r
+ forest_[2 * pos] and forest_[2 * pos + 1]. */\r
+ /* uint32_t forest[2 * num_nodes] */\r
+} HashToBinaryTree;\r
+\r
+static BROTLI_INLINE HashToBinaryTree* FN(Self)(HasherHandle handle) {\r
+ return (HashToBinaryTree*)&(GetHasherCommon(handle)[1]);\r
+}\r
+\r
+static BROTLI_INLINE uint32_t* FN(Forest)(HashToBinaryTree* self) {\r
+ return (uint32_t*)(&self[1]);\r
+}\r
+\r
+static void FN(Initialize)(\r
+ HasherHandle handle, const BrotliEncoderParams* params) {\r
+ HashToBinaryTree* self = FN(Self)(handle);\r
+ self->window_mask_ = (1u << params->lgwin) - 1u;\r
+ self->invalid_pos_ = (uint32_t)(0 - self->window_mask_);\r
+}\r
+\r
+static void FN(Prepare)(HasherHandle handle, BROTLI_BOOL one_shot,\r
+ size_t input_size, const uint8_t* data) {\r
+ HashToBinaryTree* self = FN(Self)(handle);\r
+ uint32_t invalid_pos = self->invalid_pos_;\r
+ uint32_t i;\r
+ BROTLI_UNUSED(data);\r
+ BROTLI_UNUSED(one_shot);\r
+ BROTLI_UNUSED(input_size);\r
+ for (i = 0; i < BUCKET_SIZE; i++) {\r
+ self->buckets_[i] = invalid_pos;\r
+ }\r
+}\r
+\r
+static BROTLI_INLINE size_t FN(HashMemAllocInBytes)(\r
+ const BrotliEncoderParams* params, BROTLI_BOOL one_shot,\r
+ size_t input_size) {\r
+ size_t num_nodes = (size_t)1 << params->lgwin;\r
+ if (one_shot && input_size < num_nodes) {\r
+ num_nodes = input_size;\r
+ }\r
+ return sizeof(HashToBinaryTree) + 2 * sizeof(uint32_t) * num_nodes;\r
+}\r
+\r
+static BROTLI_INLINE size_t FN(LeftChildIndex)(HashToBinaryTree* self,\r
+ const size_t pos) {\r
+ return 2 * (pos & self->window_mask_);\r
+}\r
+\r
+static BROTLI_INLINE size_t FN(RightChildIndex)(HashToBinaryTree* self,\r
+ const size_t pos) {\r
+ return 2 * (pos & self->window_mask_) + 1;\r
+}\r
+\r
+/* Stores the hash of the next 4 bytes and in a single tree-traversal, the\r
+ hash bucket's binary tree is searched for matches and is re-rooted at the\r
+ current position.\r
+\r
+ If less than MAX_TREE_COMP_LENGTH data is available, the hash bucket of the\r
+ current position is searched for matches, but the state of the hash table\r
+ is not changed, since we can not know the final sorting order of the\r
+ current (incomplete) sequence.\r
+\r
+ This function must be called with increasing cur_ix positions. */\r
+static BROTLI_INLINE BackwardMatch* FN(StoreAndFindMatches)(\r
+ HashToBinaryTree* self, const uint8_t* const BROTLI_RESTRICT data,\r
+ const size_t cur_ix, const size_t ring_buffer_mask, const size_t max_length,\r
+ const size_t max_backward, size_t* const BROTLI_RESTRICT best_len,\r
+ BackwardMatch* BROTLI_RESTRICT matches) {\r
+ const size_t cur_ix_masked = cur_ix & ring_buffer_mask;\r
+ const size_t max_comp_len =\r
+ BROTLI_MIN(size_t, max_length, MAX_TREE_COMP_LENGTH);\r
+ const BROTLI_BOOL should_reroot_tree =\r
+ TO_BROTLI_BOOL(max_length >= MAX_TREE_COMP_LENGTH);\r
+ const uint32_t key = FN(HashBytes)(&data[cur_ix_masked]);\r
+ uint32_t* forest = FN(Forest)(self);\r
+ size_t prev_ix = self->buckets_[key];\r
+ /* The forest index of the rightmost node of the left subtree of the new\r
+ root, updated as we traverse and re-root the tree of the hash bucket. */\r
+ size_t node_left = FN(LeftChildIndex)(self, cur_ix);\r
+ /* The forest index of the leftmost node of the right subtree of the new\r
+ root, updated as we traverse and re-root the tree of the hash bucket. */\r
+ size_t node_right = FN(RightChildIndex)(self, cur_ix);\r
+ /* The match length of the rightmost node of the left subtree of the new\r
+ root, updated as we traverse and re-root the tree of the hash bucket. */\r
+ size_t best_len_left = 0;\r
+ /* The match length of the leftmost node of the right subtree of the new\r
+ root, updated as we traverse and re-root the tree of the hash bucket. */\r
+ size_t best_len_right = 0;\r
+ size_t depth_remaining;\r
+ if (should_reroot_tree) {\r
+ self->buckets_[key] = (uint32_t)cur_ix;\r
+ }\r
+ for (depth_remaining = MAX_TREE_SEARCH_DEPTH; ; --depth_remaining) {\r
+ const size_t backward = cur_ix - prev_ix;\r
+ const size_t prev_ix_masked = prev_ix & ring_buffer_mask;\r
+ if (backward == 0 || backward > max_backward || depth_remaining == 0) {\r
+ if (should_reroot_tree) {\r
+ forest[node_left] = self->invalid_pos_;\r
+ forest[node_right] = self->invalid_pos_;\r
+ }\r
+ break;\r
+ }\r
+ {\r
+ const size_t cur_len = BROTLI_MIN(size_t, best_len_left, best_len_right);\r
+ size_t len;\r
+ BROTLI_DCHECK(cur_len <= MAX_TREE_COMP_LENGTH);\r
+ len = cur_len +\r
+ FindMatchLengthWithLimit(&data[cur_ix_masked + cur_len],\r
+ &data[prev_ix_masked + cur_len],\r
+ max_length - cur_len);\r
+ BROTLI_DCHECK(\r
+ 0 == memcmp(&data[cur_ix_masked], &data[prev_ix_masked], len));\r
+ if (matches && len > *best_len) {\r
+ *best_len = len;\r
+ InitBackwardMatch(matches++, backward, len);\r
+ }\r
+ if (len >= max_comp_len) {\r
+ if (should_reroot_tree) {\r
+ forest[node_left] = forest[FN(LeftChildIndex)(self, prev_ix)];\r
+ forest[node_right] = forest[FN(RightChildIndex)(self, prev_ix)];\r
+ }\r
+ break;\r
+ }\r
+ if (data[cur_ix_masked + len] > data[prev_ix_masked + len]) {\r
+ best_len_left = len;\r
+ if (should_reroot_tree) {\r
+ forest[node_left] = (uint32_t)prev_ix;\r
+ }\r
+ node_left = FN(RightChildIndex)(self, prev_ix);\r
+ prev_ix = forest[node_left];\r
+ } else {\r
+ best_len_right = len;\r
+ if (should_reroot_tree) {\r
+ forest[node_right] = (uint32_t)prev_ix;\r
+ }\r
+ node_right = FN(LeftChildIndex)(self, prev_ix);\r
+ prev_ix = forest[node_right];\r
+ }\r
+ }\r
+ }\r
+ return matches;\r
+}\r
+\r
+/* Finds all backward matches of &data[cur_ix & ring_buffer_mask] up to the\r
+ length of max_length and stores the position cur_ix in the hash table.\r
+\r
+ Sets *num_matches to the number of matches found, and stores the found\r
+ matches in matches[0] to matches[*num_matches - 1]. The matches will be\r
+ sorted by strictly increasing length and (non-strictly) increasing\r
+ distance. */\r
+static BROTLI_INLINE size_t FN(FindAllMatches)(HasherHandle handle,\r
+ const BrotliEncoderDictionary* dictionary, const uint8_t* data,\r
+ const size_t ring_buffer_mask, const size_t cur_ix,\r
+ const size_t max_length, const size_t max_backward, const size_t gap,\r
+ const BrotliEncoderParams* params, BackwardMatch* matches) {\r
+ BackwardMatch* const orig_matches = matches;\r
+ const size_t cur_ix_masked = cur_ix & ring_buffer_mask;\r
+ size_t best_len = 1;\r
+ const size_t short_match_max_backward =\r
+ params->quality != HQ_ZOPFLIFICATION_QUALITY ? 16 : 64;\r
+ size_t stop = cur_ix - short_match_max_backward;\r
+ uint32_t dict_matches[BROTLI_MAX_STATIC_DICTIONARY_MATCH_LEN + 1];\r
+ size_t i;\r
+ if (cur_ix < short_match_max_backward) { stop = 0; }\r
+ for (i = cur_ix - 1; i > stop && best_len <= 2; --i) {\r
+ size_t prev_ix = i;\r
+ const size_t backward = cur_ix - prev_ix;\r
+ if (BROTLI_PREDICT_FALSE(backward > max_backward)) {\r
+ break;\r
+ }\r
+ prev_ix &= ring_buffer_mask;\r
+ if (data[cur_ix_masked] != data[prev_ix] ||\r
+ data[cur_ix_masked + 1] != data[prev_ix + 1]) {\r
+ continue;\r
+ }\r
+ {\r
+ const size_t len =\r
+ FindMatchLengthWithLimit(&data[prev_ix], &data[cur_ix_masked],\r
+ max_length);\r
+ if (len > best_len) {\r
+ best_len = len;\r
+ InitBackwardMatch(matches++, backward, len);\r
+ }\r
+ }\r
+ }\r
+ if (best_len < max_length) {\r
+ matches = FN(StoreAndFindMatches)(FN(Self)(handle), data, cur_ix,\r
+ ring_buffer_mask, max_length, max_backward, &best_len, matches);\r
+ }\r
+ for (i = 0; i <= BROTLI_MAX_STATIC_DICTIONARY_MATCH_LEN; ++i) {\r
+ dict_matches[i] = kInvalidMatch;\r
+ }\r
+ {\r
+ size_t minlen = BROTLI_MAX(size_t, 4, best_len + 1);\r
+ if (BrotliFindAllStaticDictionaryMatches(dictionary,\r
+ &data[cur_ix_masked], minlen, max_length, &dict_matches[0])) {\r
+ size_t maxlen = BROTLI_MIN(\r
+ size_t, BROTLI_MAX_STATIC_DICTIONARY_MATCH_LEN, max_length);\r
+ size_t l;\r
+ for (l = minlen; l <= maxlen; ++l) {\r
+ uint32_t dict_id = dict_matches[l];\r
+ if (dict_id < kInvalidMatch) {\r
+ size_t distance = max_backward + gap + (dict_id >> 5) + 1;\r
+ if (distance <= params->dist.max_distance) {\r
+ InitDictionaryBackwardMatch(matches++, distance, l, dict_id & 31);\r
+ }\r
+ }\r
+ }\r
+ }\r
+ }\r
+ return (size_t)(matches - orig_matches);\r
+}\r
+\r
+/* Stores the hash of the next 4 bytes and re-roots the binary tree at the\r
+ current sequence, without returning any matches.\r
+ REQUIRES: ix + MAX_TREE_COMP_LENGTH <= end-of-current-block */\r
+static BROTLI_INLINE void FN(Store)(HasherHandle handle, const uint8_t* data,\r
+ const size_t mask, const size_t ix) {\r
+ HashToBinaryTree* self = FN(Self)(handle);\r
+ /* Maximum distance is window size - 16, see section 9.1. of the spec. */\r
+ const size_t max_backward = self->window_mask_ - BROTLI_WINDOW_GAP + 1;\r
+ FN(StoreAndFindMatches)(self, data, ix, mask, MAX_TREE_COMP_LENGTH,\r
+ max_backward, NULL, NULL);\r
+}\r
+\r
+static BROTLI_INLINE void FN(StoreRange)(HasherHandle handle,\r
+ const uint8_t* data, const size_t mask, const size_t ix_start,\r
+ const size_t ix_end) {\r
+ size_t i = ix_start;\r
+ size_t j = ix_start;\r
+ if (ix_start + 63 <= ix_end) {\r
+ i = ix_end - 63;\r
+ }\r
+ if (ix_start + 512 <= i) {\r
+ for (; j < i; j += 8) {\r
+ FN(Store)(handle, data, mask, j);\r
+ }\r
+ }\r
+ for (; i < ix_end; ++i) {\r
+ FN(Store)(handle, data, mask, i);\r
+ }\r
+}\r
+\r
+static BROTLI_INLINE void FN(StitchToPreviousBlock)(HasherHandle handle,\r
+ size_t num_bytes, size_t position, const uint8_t* ringbuffer,\r
+ size_t ringbuffer_mask) {\r
+ HashToBinaryTree* self = FN(Self)(handle);\r
+ if (num_bytes >= FN(HashTypeLength)() - 1 &&\r
+ position >= MAX_TREE_COMP_LENGTH) {\r
+ /* Store the last `MAX_TREE_COMP_LENGTH - 1` positions in the hasher.\r
+ These could not be calculated before, since they require knowledge\r
+ of both the previous and the current block. */\r
+ const size_t i_start = position - MAX_TREE_COMP_LENGTH + 1;\r
+ const size_t i_end = BROTLI_MIN(size_t, position, i_start + num_bytes);\r
+ size_t i;\r
+ for (i = i_start; i < i_end; ++i) {\r
+ /* Maximum distance is window size - 16, see section 9.1. of the spec.\r
+ Furthermore, we have to make sure that we don't look further back\r
+ from the start of the next block than the window size, otherwise we\r
+ could access already overwritten areas of the ring-buffer. */\r
+ const size_t max_backward =\r
+ self->window_mask_ - BROTLI_MAX(size_t,\r
+ BROTLI_WINDOW_GAP - 1,\r
+ position - i);\r
+ /* We know that i + MAX_TREE_COMP_LENGTH <= position + num_bytes, i.e. the\r
+ end of the current block and that we have at least\r
+ MAX_TREE_COMP_LENGTH tail in the ring-buffer. */\r
+ FN(StoreAndFindMatches)(self, ringbuffer, i, ringbuffer_mask,\r
+ MAX_TREE_COMP_LENGTH, max_backward, NULL, NULL);\r
+ }\r
+ }\r
+}\r
+\r
+#undef BUCKET_SIZE\r
+\r
+#undef HashToBinaryTree\r
projects / mirror_edk2.git / blobdiff