\r
#include "../common/constants.h"\r
#include "../common/dictionary.h"\r
-#include "../common/types.h"\r
-#include "./dictionary_hash.h"\r
+#include "../common/platform.h"\r
+#include <brotli/types.h>\r
+#include "./encoder_dict.h"\r
#include "./fast_log.h"\r
#include "./find_match_length.h"\r
#include "./memory.h"\r
-#include "./port.h"\r
#include "./quality.h"\r
#include "./static_dict.h"\r
\r
extern "C" {\r
#endif\r
\r
-#define MAX_TREE_SEARCH_DEPTH 64\r
-#define MAX_TREE_COMP_LENGTH 128\r
-#define score_t size_t\r
+/* Pointer to hasher data.\r
+ *\r
+ * Excluding initialization and destruction, hasher can be passed as\r
+ * HasherHandle by value.\r
+ *\r
+ * Typically hasher data consists of 3 sections:\r
+ * * HasherCommon structure\r
+ * * private structured hasher data, depending on hasher type\r
+ * * private dynamic hasher data, depending on hasher type and parameters\r
+ *\r
+ * Using "define" instead of "typedef", because on MSVC __restrict does not work\r
+ * on typedef pointer types. */\r
+#define HasherHandle uint8_t*\r
+\r
+typedef struct {\r
+ BrotliHasherParams params;\r
+\r
+ /* False if hasher needs to be "prepared" before use. */\r
+ BROTLI_BOOL is_prepared_;\r
+\r
+ size_t dict_num_lookups;\r
+ size_t dict_num_matches;\r
+} HasherCommon;\r
+\r
+static BROTLI_INLINE HasherCommon* GetHasherCommon(HasherHandle handle) {\r
+ return (HasherCommon*)handle;\r
+}\r
\r
-static const uint32_t kDistanceCacheIndex[] = {\r
- 0, 1, 2, 3, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1,\r
-};\r
-static const int kDistanceCacheOffset[] = {\r
- 0, 0, 0, 0, -1, 1, -2, 2, -3, 3, -1, 1, -2, 2, -3, 3\r
-};\r
+#define score_t size_t\r
\r
static const uint32_t kCutoffTransformsCount = 10;\r
-static const uint8_t kCutoffTransforms[] = {\r
- 0, 12, 27, 23, 42, 63, 56, 48, 59, 64\r
-};\r
+/* 0, 12, 27, 23, 42, 63, 56, 48, 59, 64 */\r
+/* 0+0, 4+8, 8+19, 12+11, 16+26, 20+43, 24+32, 28+20, 32+27, 36+28 */\r
+static const uint64_t kCutoffTransforms =\r
+ BROTLI_MAKE_UINT64_T(0x071B520A, 0xDA2D3200);\r
\r
typedef struct HasherSearchResult {\r
size_t len;\r
- size_t len_x_code; /* == len ^ len_code */\r
size_t distance;\r
score_t score;\r
+ int len_code_delta; /* == len_code - len */\r
} HasherSearchResult;\r
\r
-typedef struct DictionarySearchStatictics {\r
- size_t num_lookups;\r
- size_t num_matches;\r
-} DictionarySearchStatictics;\r
-\r
/* kHashMul32 multiplier has these properties:\r
* The multiplier must be odd. Otherwise we may lose the highest bit.\r
- * No long streaks of 1s or 0s.\r
+ * No long streaks of ones or zeros.\r
* There is no effort to ensure that it is a prime, the oddity is enough\r
for this use.\r
* The number has been tuned heuristically against compression benchmarks. */\r
-static const uint32_t kHashMul32 = 0x1e35a7bd;\r
+static const uint32_t kHashMul32 = 0x1E35A7BD;\r
+static const uint64_t kHashMul64 = BROTLI_MAKE_UINT64_T(0x1E35A7BD, 0x1E35A7BD);\r
+static const uint64_t kHashMul64Long =\r
+ BROTLI_MAKE_UINT64_T(0x1FE35A7Bu, 0xD3579BD3u);\r
\r
static BROTLI_INLINE uint32_t Hash14(const uint8_t* data) {\r
- uint32_t h = BROTLI_UNALIGNED_LOAD32(data) * kHashMul32;\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 - 14);\r
}\r
\r
-#define BROTLI_LITERAL_BYTE_SCORE 540\r
-#define BROTLI_DISTANCE_BIT_PENALTY 120\r
+static BROTLI_INLINE void PrepareDistanceCache(\r
+ int* BROTLI_RESTRICT distance_cache, const int num_distances) {\r
+ if (num_distances > 4) {\r
+ int last_distance = distance_cache[0];\r
+ distance_cache[4] = last_distance - 1;\r
+ distance_cache[5] = last_distance + 1;\r
+ distance_cache[6] = last_distance - 2;\r
+ distance_cache[7] = last_distance + 2;\r
+ distance_cache[8] = last_distance - 3;\r
+ distance_cache[9] = last_distance + 3;\r
+ if (num_distances > 10) {\r
+ int next_last_distance = distance_cache[1];\r
+ distance_cache[10] = next_last_distance - 1;\r
+ distance_cache[11] = next_last_distance + 1;\r
+ distance_cache[12] = next_last_distance - 2;\r
+ distance_cache[13] = next_last_distance + 2;\r
+ distance_cache[14] = next_last_distance - 3;\r
+ distance_cache[15] = next_last_distance + 3;\r
+ }\r
+ }\r
+}\r
+\r
+#define BROTLI_LITERAL_BYTE_SCORE 135\r
+#define BROTLI_DISTANCE_BIT_PENALTY 30\r
/* Score must be positive after applying maximal penalty. */\r
#define BROTLI_SCORE_BASE (BROTLI_DISTANCE_BIT_PENALTY * 8 * sizeof(size_t))\r
\r
BROTLI_DISTANCE_BIT_PENALTY * Log2FloorNonZero(backward_reference_offset);\r
}\r
\r
-static const score_t kDistanceShortCodeCost[BROTLI_NUM_DISTANCE_SHORT_CODES] = {\r
- /* Repeat last */\r
- BROTLI_SCORE_BASE + 60,\r
- /* 2nd, 3rd, 4th last */\r
- BROTLI_SCORE_BASE - 95,\r
- BROTLI_SCORE_BASE - 117,\r
- BROTLI_SCORE_BASE - 127,\r
- /* Last with offset */\r
- BROTLI_SCORE_BASE - 93,\r
- BROTLI_SCORE_BASE - 93,\r
- BROTLI_SCORE_BASE - 96,\r
- BROTLI_SCORE_BASE - 96,\r
- BROTLI_SCORE_BASE - 99,\r
- BROTLI_SCORE_BASE - 99,\r
- /* 2nd last with offset */\r
- BROTLI_SCORE_BASE - 105,\r
- BROTLI_SCORE_BASE - 105,\r
- BROTLI_SCORE_BASE - 115,\r
- BROTLI_SCORE_BASE - 115,\r
- BROTLI_SCORE_BASE - 125,\r
- BROTLI_SCORE_BASE - 125\r
-};\r
-\r
static BROTLI_INLINE score_t BackwardReferenceScoreUsingLastDistance(\r
- size_t copy_length, size_t distance_short_code) {\r
+ size_t copy_length) {\r
return BROTLI_LITERAL_BYTE_SCORE * (score_t)copy_length +\r
- kDistanceShortCodeCost[distance_short_code];\r
+ BROTLI_SCORE_BASE + 15;\r
}\r
\r
-static BROTLI_INLINE void DictionarySearchStaticticsReset(\r
- DictionarySearchStatictics* self) {\r
- self->num_lookups = 0;\r
- self->num_matches = 0;\r
+static BROTLI_INLINE score_t BackwardReferencePenaltyUsingLastDistance(\r
+ size_t distance_short_code) {\r
+ return (score_t)39 + ((0x1CA10 >> (distance_short_code & 0xE)) & 0xE);\r
}\r
\r
static BROTLI_INLINE BROTLI_BOOL TestStaticDictionaryItem(\r
- size_t item, const uint8_t* data, size_t max_length, size_t max_backward,\r
+ const BrotliEncoderDictionary* dictionary, size_t item, const uint8_t* data,\r
+ size_t max_length, size_t max_backward, size_t max_distance,\r
HasherSearchResult* out) {\r
size_t len;\r
- size_t dist;\r
+ size_t word_idx;\r
size_t offset;\r
size_t matchlen;\r
size_t backward;\r
score_t score;\r
- len = item & 31;\r
- dist = item >> 5;\r
- offset = kBrotliDictionaryOffsetsByLength[len] + len * dist;\r
+ len = item & 0x1F;\r
+ word_idx = item >> 5;\r
+ offset = dictionary->words->offsets_by_length[len] + len * word_idx;\r
if (len > max_length) {\r
return BROTLI_FALSE;\r
}\r
\r
- matchlen = FindMatchLengthWithLimit(data, &kBrotliDictionary[offset], len);\r
- if (matchlen + kCutoffTransformsCount <= len || matchlen == 0) {\r
+ matchlen =\r
+ FindMatchLengthWithLimit(data, &dictionary->words->data[offset], len);\r
+ if (matchlen + dictionary->cutoffTransformsCount <= len || matchlen == 0) {\r
return BROTLI_FALSE;\r
}\r
{\r
- size_t transform_id = kCutoffTransforms[len - matchlen];\r
- backward = max_backward + dist + 1 +\r
- (transform_id << kBrotliDictionarySizeBitsByLength[len]);\r
+ size_t cut = len - matchlen;\r
+ size_t transform_id = (cut << 2) +\r
+ (size_t)((dictionary->cutoffTransforms >> (cut * 6)) & 0x3F);\r
+ backward = max_backward + 1 + word_idx +\r
+ (transform_id << dictionary->words->size_bits_by_length[len]);\r
+ }\r
+ if (backward > max_distance) {\r
+ return BROTLI_FALSE;\r
}\r
score = BackwardReferenceScore(matchlen, backward);\r
if (score < out->score) {\r
return BROTLI_FALSE;\r
}\r
out->len = matchlen;\r
- out->len_x_code = len ^ matchlen;\r
+ out->len_code_delta = (int)len - (int)matchlen;\r
out->distance = backward;\r
out->score = score;\r
return BROTLI_TRUE;\r
}\r
\r
-static BROTLI_INLINE BROTLI_BOOL SearchInStaticDictionary(\r
- DictionarySearchStatictics* self, const uint8_t* data, size_t max_length,\r
- size_t max_backward, HasherSearchResult* out, BROTLI_BOOL shallow) {\r
+static BROTLI_INLINE void SearchInStaticDictionary(\r
+ const BrotliEncoderDictionary* dictionary,\r
+ HasherHandle handle, const uint8_t* data, size_t max_length,\r
+ size_t max_backward, size_t max_distance,\r
+ HasherSearchResult* out, BROTLI_BOOL shallow) {\r
size_t key;\r
size_t i;\r
- BROTLI_BOOL is_match_found = BROTLI_FALSE;\r
- if (self->num_matches < (self->num_lookups >> 7)) {\r
- return BROTLI_FALSE;\r
+ HasherCommon* self = GetHasherCommon(handle);\r
+ if (self->dict_num_matches < (self->dict_num_lookups >> 7)) {\r
+ return;\r
}\r
key = Hash14(data) << 1;\r
- for (i = 0; i < (shallow ? 1 : 2); ++i, ++key) {\r
- size_t item = kStaticDictionaryHash[key];\r
- self->num_lookups++;\r
- if (item != 0 &&\r
- TestStaticDictionaryItem(item, data, max_length, max_backward, out)) {\r
- self->num_matches++;\r
- is_match_found = BROTLI_TRUE;\r
+ for (i = 0; i < (shallow ? 1u : 2u); ++i, ++key) {\r
+ size_t item = dictionary->hash_table[key];\r
+ self->dict_num_lookups++;\r
+ if (item != 0) {\r
+ BROTLI_BOOL item_matches = TestStaticDictionaryItem(\r
+ dictionary, item, data, max_length, max_backward, max_distance, out);\r
+ if (item_matches) {\r
+ self->dict_num_matches++;\r
+ }\r
}\r
}\r
- return is_match_found;\r
}\r
\r
typedef struct BackwardMatch {\r
#define CAT(a, b) a ## b\r
#define FN(X) EXPAND_CAT(X, HASHER())\r
\r
-#define MAX_NUM_MATCHES_H10 (64 + MAX_TREE_SEARCH_DEPTH)\r
-\r
#define HASHER() H10\r
-#define HashToBinaryTree HASHER()\r
-\r
#define BUCKET_BITS 17\r
-#define BUCKET_SIZE (1 << BUCKET_BITS)\r
-\r
-static size_t FN(HashTypeLength)(void) { return 4; }\r
-static size_t FN(StoreLookahead)(void) { return MAX_TREE_COMP_LENGTH; }\r
-\r
-static uint32_t FN(HashBytes)(const uint8_t *data) {\r
- uint32_t h = BROTLI_UNALIGNED_LOAD32(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
-/* 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
-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
- /* 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_;\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
- size_t forest_size_;\r
- BROTLI_BOOL is_dirty_;\r
-} HashToBinaryTree;\r
-\r
-static void FN(Reset)(HashToBinaryTree* self) {\r
- self->is_dirty_ = BROTLI_TRUE;\r
-}\r
-\r
-static void FN(Initialize)(HashToBinaryTree* self) {\r
- self->forest_ = NULL;\r
- self->forest_size_ = 0;\r
- FN(Reset)(self);\r
-}\r
-\r
-static void FN(Cleanup)(MemoryManager* m, HashToBinaryTree* self) {\r
- BROTLI_FREE(m, self->forest_);\r
-}\r
-\r
-static void FN(Init)(\r
- MemoryManager* m, HashToBinaryTree* self, const uint8_t* data,\r
- const BrotliEncoderParams* params, size_t position, size_t bytes,\r
- BROTLI_BOOL is_last) {\r
- if (self->is_dirty_) {\r
- uint32_t invalid_pos;\r
- size_t num_nodes;\r
- uint32_t i;\r
- BROTLI_UNUSED(data);\r
- self->window_mask_ = (1u << params->lgwin) - 1u;\r
- invalid_pos = (uint32_t)(0 - self->window_mask_);\r
- self->invalid_pos_ = invalid_pos;\r
- for (i = 0; i < BUCKET_SIZE; i++) {\r
- self->buckets_[i] = invalid_pos;\r
- }\r
- num_nodes = (position == 0 && is_last) ? bytes : self->window_mask_ + 1;\r
- if (num_nodes > self->forest_size_) {\r
- BROTLI_FREE(m, self->forest_);\r
- self->forest_ = BROTLI_ALLOC(m, uint32_t, 2 * num_nodes);\r
- if (BROTLI_IS_OOM(m)) return;\r
- self->forest_size_ = num_nodes;\r
- }\r
- self->is_dirty_ = BROTLI_FALSE;\r
- }\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
- 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 reroot 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 reroot 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 reroot 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 reroot 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
- self->forest_[node_left] = self->invalid_pos_;\r
- self->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
- assert(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
- assert(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
- self->forest_[node_left] =\r
- self->forest_[FN(LeftChildIndex)(self, prev_ix)];\r
- self->forest_[node_right] =\r
- self->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
- self->forest_[node_left] = (uint32_t)prev_ix;\r
- }\r
- node_left = FN(RightChildIndex)(self, prev_ix);\r
- prev_ix = self->forest_[node_left];\r
- } else {\r
- best_len_right = len;\r
- if (should_reroot_tree) {\r
- self->forest_[node_right] = (uint32_t)prev_ix;\r
- }\r
- node_right = FN(LeftChildIndex)(self, prev_ix);\r
- prev_ix = self->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)(HashToBinaryTree* self,\r
- const uint8_t* data, const size_t ring_buffer_mask, const size_t cur_ix,\r
- const size_t max_length, const size_t max_backward,\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 (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)(self, data, cur_ix, ring_buffer_mask,\r
- 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(&data[cur_ix_masked], minlen,\r
- 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
- InitDictionaryBackwardMatch(matches++,\r
- max_backward + (dict_id >> 5) + 1, l, dict_id & 31);\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)(HashToBinaryTree* self, const uint8_t *data,\r
- const size_t mask, const size_t ix) {\r
- /* Maximum distance is window size - 16, see section 9.1. of the spec. */\r
- const size_t max_backward = self->window_mask_ - 15;\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)(HashToBinaryTree* 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 = ix_start + 63 <= ix_end ? ix_end - 63 : ix_start;\r
- for (; i < ix_end; ++i) {\r
- FN(Store)(self, data, mask, i);\r
- }\r
-}\r
-\r
-static BROTLI_INLINE void FN(StitchToPreviousBlock)(HashToBinaryTree* self,\r
- size_t num_bytes, size_t position, const uint8_t* ringbuffer,\r
- size_t ringbuffer_mask) {\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 ringbuffer. */\r
- const size_t max_backward =\r
- self->window_mask_ - BROTLI_MAX(size_t, 15, 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 ringbuffer. */\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
+#define MAX_TREE_SEARCH_DEPTH 64\r
+#define MAX_TREE_COMP_LENGTH 128\r
+#include "./hash_to_binary_tree_inc.h" /* NOLINT(build/include) */\r
+#undef MAX_TREE_SEARCH_DEPTH\r
+#undef MAX_TREE_COMP_LENGTH\r
#undef BUCKET_BITS\r
-\r
#undef HASHER\r
+/* MAX_NUM_MATCHES == 64 + MAX_TREE_SEARCH_DEPTH */\r
+#define MAX_NUM_MATCHES_H10 128\r
\r
/* For BUCKET_SWEEP == 1, enabling the dictionary lookup makes compression\r
a little faster (0.5% - 1%) and it compresses 0.15% better on small text\r
- and html inputs. */\r
+ and HTML inputs. */\r
\r
#define HASHER() H2\r
#define BUCKET_BITS 16\r
#define BUCKET_SWEEP 1\r
+#define HASH_LEN 5\r
#define USE_DICTIONARY 1\r
#include "./hash_longest_match_quickly_inc.h" /* NOLINT(build/include) */\r
#undef BUCKET_SWEEP\r
#define USE_DICTIONARY 1\r
#include "./hash_longest_match_quickly_inc.h" /* NOLINT(build/include) */\r
#undef USE_DICTIONARY\r
+#undef HASH_LEN\r
#undef BUCKET_SWEEP\r
#undef BUCKET_BITS\r
#undef HASHER\r
\r
#define HASHER() H5\r
-#define BUCKET_BITS 14\r
-#define BLOCK_BITS 4\r
-#define NUM_LAST_DISTANCES_TO_CHECK 4\r
#include "./hash_longest_match_inc.h" /* NOLINT(build/include) */\r
-#undef BLOCK_BITS\r
#undef HASHER\r
\r
#define HASHER() H6\r
-#define BLOCK_BITS 5\r
-#include "./hash_longest_match_inc.h" /* NOLINT(build/include) */\r
-#undef NUM_LAST_DISTANCES_TO_CHECK\r
-#undef BLOCK_BITS\r
-#undef BUCKET_BITS\r
-#undef HASHER\r
-\r
-#define HASHER() H7\r
-#define BUCKET_BITS 15\r
-#define BLOCK_BITS 6\r
-#define NUM_LAST_DISTANCES_TO_CHECK 10\r
-#include "./hash_longest_match_inc.h" /* NOLINT(build/include) */\r
-#undef BLOCK_BITS\r
-#undef HASHER\r
-\r
-#define HASHER() H8\r
-#define BLOCK_BITS 7\r
-#include "./hash_longest_match_inc.h" /* NOLINT(build/include) */\r
-#undef NUM_LAST_DISTANCES_TO_CHECK\r
-#undef BLOCK_BITS\r
-#undef HASHER\r
-\r
-#define HASHER() H9\r
-#define BLOCK_BITS 8\r
-#define NUM_LAST_DISTANCES_TO_CHECK 16\r
-#include "./hash_longest_match_inc.h" /* NOLINT(build/include) */\r
-#undef NUM_LAST_DISTANCES_TO_CHECK\r
-#undef BLOCK_BITS\r
-#undef BUCKET_BITS\r
+#include "./hash_longest_match64_inc.h" /* NOLINT(build/include) */\r
#undef HASHER\r
\r
#define BUCKET_BITS 15\r
\r
#undef BUCKET_BITS\r
\r
+#define HASHER() H54\r
+#define BUCKET_BITS 20\r
+#define BUCKET_SWEEP 4\r
+#define HASH_LEN 7\r
+#define USE_DICTIONARY 0\r
+#include "./hash_longest_match_quickly_inc.h" /* NOLINT(build/include) */\r
+#undef USE_DICTIONARY\r
+#undef HASH_LEN\r
+#undef BUCKET_SWEEP\r
+#undef BUCKET_BITS\r
+#undef HASHER\r
+\r
+/* fast large window hashers */\r
+\r
+#define HASHER() HROLLING_FAST\r
+#define CHUNKLEN 32\r
+#define JUMP 4\r
+#define NUMBUCKETS 16777216\r
+#define MASK ((NUMBUCKETS * 64) - 1)\r
+#include "./hash_rolling_inc.h" /* NOLINT(build/include) */\r
+#undef JUMP\r
+#undef HASHER\r
+\r
+\r
+#define HASHER() HROLLING\r
+#define JUMP 1\r
+#include "./hash_rolling_inc.h" /* NOLINT(build/include) */\r
+#undef MASK\r
+#undef NUMBUCKETS\r
+#undef JUMP\r
+#undef CHUNKLEN\r
+#undef HASHER\r
+\r
+#define HASHER() H35\r
+#define HASHER_A H3\r
+#define HASHER_B HROLLING_FAST\r
+#include "./hash_composite_inc.h" /* NOLINT(build/include) */\r
+#undef HASHER_A\r
+#undef HASHER_B\r
+#undef HASHER\r
+\r
+#define HASHER() H55\r
+#define HASHER_A H54\r
+#define HASHER_B HROLLING_FAST\r
+#include "./hash_composite_inc.h" /* NOLINT(build/include) */\r
+#undef HASHER_A\r
+#undef HASHER_B\r
+#undef HASHER\r
+\r
+#define HASHER() H65\r
+#define HASHER_A H6\r
+#define HASHER_B HROLLING\r
+#include "./hash_composite_inc.h" /* NOLINT(build/include) */\r
+#undef HASHER_A\r
+#undef HASHER_B\r
+#undef HASHER\r
+\r
#undef FN\r
#undef CAT\r
#undef EXPAND_CAT\r
\r
-#define FOR_GENERIC_HASHERS(H) H(2) H(3) H(4) H(5) H(6) H(7) H(8) H(9) \\r
- H(40) H(41) H(42)\r
+#define FOR_GENERIC_HASHERS(H) H(2) H(3) H(4) H(5) H(6) H(40) H(41) H(42) H(54)\\r
+ H(35) H(55) H(65)\r
#define FOR_ALL_HASHERS(H) FOR_GENERIC_HASHERS(H) H(10)\r
\r
-typedef struct Hashers {\r
-#define _MEMBER(N) H ## N* h ## N;\r
- FOR_ALL_HASHERS(_MEMBER)\r
-#undef _MEMBER\r
-} Hashers;\r
-\r
-static BROTLI_INLINE void InitHashers(Hashers* self) {\r
-#define _INIT(N) self->h ## N = 0;\r
- FOR_ALL_HASHERS(_INIT)\r
-#undef _INIT\r
+static BROTLI_INLINE void DestroyHasher(\r
+ MemoryManager* m, HasherHandle* handle) {\r
+ if (*handle == NULL) return;\r
+ BROTLI_FREE(m, *handle);\r
}\r
\r
-static BROTLI_INLINE void DestroyHashers(MemoryManager* m, Hashers* self) {\r
- if (self->h10) CleanupH10(m, self->h10);\r
-#define _CLEANUP(N) BROTLI_FREE(m, self->h ## N)\r
- FOR_ALL_HASHERS(_CLEANUP)\r
-#undef _CLEANUP\r
+static BROTLI_INLINE void HasherReset(HasherHandle handle) {\r
+ if (handle == NULL) return;\r
+ GetHasherCommon(handle)->is_prepared_ = BROTLI_FALSE;\r
}\r
\r
-static BROTLI_INLINE void HashersReset(Hashers* self, int type) {\r
- switch (type) {\r
-#define _RESET(N) case N: ResetH ## N(self->h ## N); break;\r
- FOR_ALL_HASHERS(_RESET)\r
-#undef _RESET\r
- default: break;\r
+static BROTLI_INLINE size_t HasherSize(const BrotliEncoderParams* params,\r
+ BROTLI_BOOL one_shot, const size_t input_size) {\r
+ size_t result = sizeof(HasherCommon);\r
+ switch (params->hasher.type) {\r
+#define SIZE_(N) \\r
+ case N: \\r
+ result += HashMemAllocInBytesH ## N(params, one_shot, input_size); \\r
+ break;\r
+ FOR_ALL_HASHERS(SIZE_)\r
+#undef SIZE_\r
+ default:\r
+ break;\r
}\r
+ return result;\r
}\r
\r
-static BROTLI_INLINE void HashersSetup(\r
- MemoryManager* m, Hashers* self, int type) {\r
- switch (type) {\r
-#define _SETUP(N) case N: self->h ## N = BROTLI_ALLOC(m, H ## N, 1); break;\r
- FOR_ALL_HASHERS(_SETUP)\r
-#undef _SETUP\r
- default: break;\r
+static BROTLI_INLINE void HasherSetup(MemoryManager* m, HasherHandle* handle,\r
+ BrotliEncoderParams* params, const uint8_t* data, size_t position,\r
+ size_t input_size, BROTLI_BOOL is_last) {\r
+ HasherHandle self = NULL;\r
+ HasherCommon* common = NULL;\r
+ BROTLI_BOOL one_shot = (position == 0 && is_last);\r
+ if (*handle == NULL) {\r
+ size_t alloc_size;\r
+ ChooseHasher(params, ¶ms->hasher);\r
+ alloc_size = HasherSize(params, one_shot, input_size);\r
+ self = BROTLI_ALLOC(m, uint8_t, alloc_size);\r
+ if (BROTLI_IS_OOM(m)) return;\r
+ *handle = self;\r
+ common = GetHasherCommon(self);\r
+ common->params = params->hasher;\r
+ switch (common->params.type) {\r
+#define INITIALIZE_(N) \\r
+ case N: \\r
+ InitializeH ## N(*handle, params); \\r
+ break;\r
+ FOR_ALL_HASHERS(INITIALIZE_);\r
+#undef INITIALIZE_\r
+ default:\r
+ break;\r
+ }\r
+ HasherReset(*handle);\r
}\r
- if (BROTLI_IS_OOM(m)) return;\r
- if (type == 10) InitializeH10(self->h10);\r
- HashersReset(self, type);\r
-}\r
\r
-#define _WARMUP_HASH(N) \\r
-static BROTLI_INLINE void WarmupHashH ## N(MemoryManager* m, \\r
- const BrotliEncoderParams* params, const size_t size, const uint8_t* dict, \\r
- H ## N* hasher) { \\r
- size_t overlap = (StoreLookaheadH ## N()) - 1; \\r
- size_t i; \\r
- InitH ## N(m, hasher, dict, params, 0, size, BROTLI_FALSE); \\r
- if (BROTLI_IS_OOM(m)) return; \\r
- for (i = 0; i + overlap < size; i++) { \\r
- StoreH ## N(hasher, dict, ~(size_t)0, i); \\r
- } \\r
+ self = *handle;\r
+ common = GetHasherCommon(self);\r
+ if (!common->is_prepared_) {\r
+ switch (common->params.type) {\r
+#define PREPARE_(N) \\r
+ case N: \\r
+ PrepareH ## N(self, one_shot, input_size, data); \\r
+ break;\r
+ FOR_ALL_HASHERS(PREPARE_)\r
+#undef PREPARE_\r
+ default: break;\r
+ }\r
+ if (position == 0) {\r
+ common->dict_num_lookups = 0;\r
+ common->dict_num_matches = 0;\r
+ }\r
+ common->is_prepared_ = BROTLI_TRUE;\r
+ }\r
}\r
-FOR_ALL_HASHERS(_WARMUP_HASH)\r
-#undef _WARMUP_HASH\r
-\r
-/* Custom LZ77 window. */\r
-static BROTLI_INLINE void HashersPrependCustomDictionary(\r
- MemoryManager* m, Hashers* self, const BrotliEncoderParams* params,\r
- const size_t size, const uint8_t* dict) {\r
- int hasher_type = ChooseHasher(params);\r
- switch (hasher_type) {\r
-#define _PREPEND(N) \\r
- case N: WarmupHashH ## N(m, params, size, dict, self->h ## N); break;\r
- FOR_ALL_HASHERS(_PREPEND)\r
-#undef _PREPEND\r
+\r
+static BROTLI_INLINE void InitOrStitchToPreviousBlock(\r
+ MemoryManager* m, HasherHandle* handle, const uint8_t* data, size_t mask,\r
+ BrotliEncoderParams* params, size_t position, size_t input_size,\r
+ BROTLI_BOOL is_last) {\r
+ HasherHandle self;\r
+ HasherSetup(m, handle, params, data, position, input_size, is_last);\r
+ if (BROTLI_IS_OOM(m)) return;\r
+ self = *handle;\r
+ switch (GetHasherCommon(self)->params.type) {\r
+#define INIT_(N) \\r
+ case N: \\r
+ StitchToPreviousBlockH ## N(self, input_size, position, data, mask); \\r
+ break;\r
+ FOR_ALL_HASHERS(INIT_)\r
+#undef INIT_\r
default: break;\r
}\r
- if (BROTLI_IS_OOM(m)) return;\r
}\r
\r
-\r
#if defined(__cplusplus) || defined(c_plusplus)\r
} /* extern "C" */\r
#endif\r
projects / mirror_edk2.git / blobdiff