]>
Commit | Line | Data |
---|---|---|
11b7501a SB |
1 | /* NOLINT(build/header_guard) */\r |
2 | /* Copyright 2016 Google Inc. All Rights Reserved.\r | |
3 | \r | |
4 | Distributed under MIT license.\r | |
5 | See file LICENSE for detail or copy at https://opensource.org/licenses/MIT\r | |
6 | */\r | |
7 | \r | |
8 | /* template parameters: FN, BUCKET_BITS, NUM_BANKS, BANK_BITS,\r | |
9 | NUM_LAST_DISTANCES_TO_CHECK */\r | |
10 | \r | |
11 | /* A (forgetful) hash table to the data seen by the compressor, to\r | |
12 | help create backward references to previous data.\r | |
13 | \r | |
14 | Hashes are stored in chains which are bucketed to groups. Group of chains\r | |
15 | share a storage "bank". When more than "bank size" chain nodes are added,\r | |
16 | oldest nodes are replaced; this way several chains may share a tail. */\r | |
17 | \r | |
18 | #define HashForgetfulChain HASHER()\r | |
19 | \r | |
20 | #define BANK_SIZE (1 << BANK_BITS)\r | |
21 | \r | |
22 | /* Number of hash buckets. */\r | |
23 | #define BUCKET_SIZE (1 << BUCKET_BITS)\r | |
24 | \r | |
25 | #define CAPPED_CHAINS 0\r | |
26 | \r | |
27 | static BROTLI_INLINE size_t FN(HashTypeLength)(void) { return 4; }\r | |
28 | static BROTLI_INLINE size_t FN(StoreLookahead)(void) { return 4; }\r | |
29 | \r | |
30 | /* HashBytes is the function that chooses the bucket to place the address in.*/\r | |
dd4f667e LG |
31 | static BROTLI_INLINE size_t FN(HashBytes)(const uint8_t* data) {\r |
32 | const uint32_t h = BROTLI_UNALIGNED_LOAD32LE(data) * kHashMul32;\r | |
11b7501a SB |
33 | /* The higher bits contain more mixture from the multiplication,\r |
34 | so we take our results from there. */\r | |
35 | return h >> (32 - BUCKET_BITS);\r | |
36 | }\r | |
37 | \r | |
38 | typedef struct FN(Slot) {\r | |
39 | uint16_t delta;\r | |
40 | uint16_t next;\r | |
41 | } FN(Slot);\r | |
42 | \r | |
43 | typedef struct FN(Bank) {\r | |
44 | FN(Slot) slots[BANK_SIZE];\r | |
45 | } FN(Bank);\r | |
46 | \r | |
47 | typedef struct HashForgetfulChain {\r | |
48 | uint32_t addr[BUCKET_SIZE];\r | |
49 | uint16_t head[BUCKET_SIZE];\r | |
50 | /* Truncated hash used for quick rejection of "distance cache" candidates. */\r | |
51 | uint8_t tiny_hash[65536];\r | |
52 | FN(Bank) banks[NUM_BANKS];\r | |
53 | uint16_t free_slot_idx[NUM_BANKS];\r | |
11b7501a SB |
54 | size_t max_hops;\r |
55 | } HashForgetfulChain;\r | |
56 | \r | |
dd4f667e LG |
57 | static BROTLI_INLINE HashForgetfulChain* FN(Self)(HasherHandle handle) {\r |
58 | return (HashForgetfulChain*)&(GetHasherCommon(handle)[1]);\r | |
11b7501a SB |
59 | }\r |
60 | \r | |
dd4f667e LG |
61 | static void FN(Initialize)(\r |
62 | HasherHandle handle, const BrotliEncoderParams* params) {\r | |
63 | FN(Self)(handle)->max_hops =\r | |
64 | (params->quality > 6 ? 7u : 8u) << (params->quality - 4);\r | |
65 | }\r | |
66 | \r | |
67 | static void FN(Prepare)(HasherHandle handle, BROTLI_BOOL one_shot,\r | |
68 | size_t input_size, const uint8_t* data) {\r | |
69 | HashForgetfulChain* self = FN(Self)(handle);\r | |
70 | /* Partial preparation is 100 times slower (per socket). */\r | |
71 | size_t partial_prepare_threshold = BUCKET_SIZE >> 6;\r | |
72 | if (one_shot && input_size <= partial_prepare_threshold) {\r | |
73 | size_t i;\r | |
74 | for (i = 0; i < input_size; ++i) {\r | |
75 | size_t bucket = FN(HashBytes)(&data[i]);\r | |
76 | /* See InitEmpty comment. */\r | |
77 | self->addr[bucket] = 0xCCCCCCCC;\r | |
78 | self->head[bucket] = 0xCCCC;\r | |
79 | }\r | |
80 | } else {\r | |
11b7501a SB |
81 | /* Fill |addr| array with 0xCCCCCCCC value. Because of wrapping, position\r |
82 | processed by hasher never reaches 3GB + 64M; this makes all new chains\r | |
83 | to be terminated after the first node. */\r | |
84 | memset(self->addr, 0xCC, sizeof(self->addr));\r | |
85 | memset(self->head, 0, sizeof(self->head));\r | |
11b7501a SB |
86 | }\r |
87 | memset(self->tiny_hash, 0, sizeof(self->tiny_hash));\r | |
88 | memset(self->free_slot_idx, 0, sizeof(self->free_slot_idx));\r | |
11b7501a SB |
89 | }\r |
90 | \r | |
dd4f667e LG |
91 | static BROTLI_INLINE size_t FN(HashMemAllocInBytes)(\r |
92 | const BrotliEncoderParams* params, BROTLI_BOOL one_shot,\r | |
93 | size_t input_size) {\r | |
94 | BROTLI_UNUSED(params);\r | |
95 | BROTLI_UNUSED(one_shot);\r | |
96 | BROTLI_UNUSED(input_size);\r | |
97 | return sizeof(HashForgetfulChain);\r | |
11b7501a SB |
98 | }\r |
99 | \r | |
100 | /* Look at 4 bytes at &data[ix & mask]. Compute a hash from these, and prepend\r | |
101 | node to corresponding chain; also update tiny_hash for current position. */\r | |
dd4f667e | 102 | static BROTLI_INLINE void FN(Store)(HasherHandle BROTLI_RESTRICT handle,\r |
11b7501a | 103 | const uint8_t* BROTLI_RESTRICT data, const size_t mask, const size_t ix) {\r |
dd4f667e | 104 | HashForgetfulChain* self = FN(Self)(handle);\r |
11b7501a SB |
105 | const size_t key = FN(HashBytes)(&data[ix & mask]);\r |
106 | const size_t bank = key & (NUM_BANKS - 1);\r | |
107 | const size_t idx = self->free_slot_idx[bank]++ & (BANK_SIZE - 1);\r | |
108 | size_t delta = ix - self->addr[key];\r | |
109 | self->tiny_hash[(uint16_t)ix] = (uint8_t)key;\r | |
110 | if (delta > 0xFFFF) delta = CAPPED_CHAINS ? 0 : 0xFFFF;\r | |
111 | self->banks[bank].slots[idx].delta = (uint16_t)delta;\r | |
112 | self->banks[bank].slots[idx].next = self->head[key];\r | |
113 | self->addr[key] = (uint32_t)ix;\r | |
114 | self->head[key] = (uint16_t)idx;\r | |
115 | }\r | |
116 | \r | |
dd4f667e LG |
117 | static BROTLI_INLINE void FN(StoreRange)(HasherHandle handle,\r |
118 | const uint8_t* data, const size_t mask, const size_t ix_start,\r | |
11b7501a SB |
119 | const size_t ix_end) {\r |
120 | size_t i;\r | |
121 | for (i = ix_start; i < ix_end; ++i) {\r | |
dd4f667e | 122 | FN(Store)(handle, data, mask, i);\r |
11b7501a SB |
123 | }\r |
124 | }\r | |
125 | \r | |
dd4f667e | 126 | static BROTLI_INLINE void FN(StitchToPreviousBlock)(HasherHandle handle,\r |
11b7501a SB |
127 | size_t num_bytes, size_t position, const uint8_t* ringbuffer,\r |
128 | size_t ring_buffer_mask) {\r | |
129 | if (num_bytes >= FN(HashTypeLength)() - 1 && position >= 3) {\r | |
130 | /* Prepare the hashes for three last bytes of the last write.\r | |
131 | These could not be calculated before, since they require knowledge\r | |
132 | of both the previous and the current block. */\r | |
dd4f667e LG |
133 | FN(Store)(handle, ringbuffer, ring_buffer_mask, position - 3);\r |
134 | FN(Store)(handle, ringbuffer, ring_buffer_mask, position - 2);\r | |
135 | FN(Store)(handle, ringbuffer, ring_buffer_mask, position - 1);\r | |
11b7501a SB |
136 | }\r |
137 | }\r | |
138 | \r | |
dd4f667e LG |
139 | static BROTLI_INLINE void FN(PrepareDistanceCache)(\r |
140 | HasherHandle handle, int* BROTLI_RESTRICT distance_cache) {\r | |
141 | BROTLI_UNUSED(handle);\r | |
142 | PrepareDistanceCache(distance_cache, NUM_LAST_DISTANCES_TO_CHECK);\r | |
143 | }\r | |
144 | \r | |
11b7501a SB |
145 | /* Find a longest backward match of &data[cur_ix] up to the length of\r |
146 | max_length and stores the position cur_ix in the hash table.\r | |
147 | \r | |
dd4f667e LG |
148 | REQUIRES: FN(PrepareDistanceCache) must be invoked for current distance cache\r |
149 | values; if this method is invoked repeatedly with the same distance\r | |
150 | cache values, it is enough to invoke FN(PrepareDistanceCache) once.\r | |
151 | \r | |
11b7501a SB |
152 | Does not look for matches longer than max_length.\r |
153 | Does not look for matches further away than max_backward.\r | |
154 | Writes the best match into |out|.\r | |
dd4f667e LG |
155 | |out|->score is updated only if a better match is found. */\r |
156 | static BROTLI_INLINE void FN(FindLongestMatch)(HasherHandle handle,\r | |
157 | const BrotliEncoderDictionary* dictionary,\r | |
158 | const uint8_t* BROTLI_RESTRICT data, const size_t ring_buffer_mask,\r | |
159 | const int* BROTLI_RESTRICT distance_cache,\r | |
11b7501a | 160 | const size_t cur_ix, const size_t max_length, const size_t max_backward,\r |
dd4f667e | 161 | const size_t gap, const size_t max_distance,\r |
11b7501a | 162 | HasherSearchResult* BROTLI_RESTRICT out) {\r |
dd4f667e | 163 | HashForgetfulChain* self = FN(Self)(handle);\r |
11b7501a | 164 | const size_t cur_ix_masked = cur_ix & ring_buffer_mask;\r |
11b7501a | 165 | /* Don't accept a short copy from far away. */\r |
dd4f667e | 166 | score_t min_score = out->score;\r |
11b7501a SB |
167 | score_t best_score = out->score;\r |
168 | size_t best_len = out->len;\r | |
169 | size_t i;\r | |
170 | const size_t key = FN(HashBytes)(&data[cur_ix_masked]);\r | |
171 | const uint8_t tiny_hash = (uint8_t)(key);\r | |
172 | out->len = 0;\r | |
dd4f667e | 173 | out->len_code_delta = 0;\r |
11b7501a SB |
174 | /* Try last distance first. */\r |
175 | for (i = 0; i < NUM_LAST_DISTANCES_TO_CHECK; ++i) {\r | |
dd4f667e | 176 | const size_t backward = (size_t)distance_cache[i];\r |
11b7501a | 177 | size_t prev_ix = (cur_ix - backward);\r |
dd4f667e | 178 | /* For distance code 0 we want to consider 2-byte matches. */\r |
11b7501a SB |
179 | if (i > 0 && self->tiny_hash[(uint16_t)prev_ix] != tiny_hash) continue;\r |
180 | if (prev_ix >= cur_ix || backward > max_backward) {\r | |
181 | continue;\r | |
182 | }\r | |
183 | prev_ix &= ring_buffer_mask;\r | |
184 | {\r | |
185 | const size_t len = FindMatchLengthWithLimit(&data[prev_ix],\r | |
186 | &data[cur_ix_masked],\r | |
187 | max_length);\r | |
188 | if (len >= 2) {\r | |
dd4f667e | 189 | score_t score = BackwardReferenceScoreUsingLastDistance(len);\r |
11b7501a | 190 | if (best_score < score) {\r |
dd4f667e LG |
191 | if (i != 0) score -= BackwardReferencePenaltyUsingLastDistance(i);\r |
192 | if (best_score < score) {\r | |
193 | best_score = score;\r | |
194 | best_len = len;\r | |
195 | out->len = best_len;\r | |
196 | out->distance = backward;\r | |
197 | out->score = best_score;\r | |
198 | }\r | |
11b7501a SB |
199 | }\r |
200 | }\r | |
201 | }\r | |
202 | }\r | |
203 | {\r | |
204 | const size_t bank = key & (NUM_BANKS - 1);\r | |
205 | size_t backward = 0;\r | |
206 | size_t hops = self->max_hops;\r | |
207 | size_t delta = cur_ix - self->addr[key];\r | |
208 | size_t slot = self->head[key];\r | |
209 | while (hops--) {\r | |
210 | size_t prev_ix;\r | |
211 | size_t last = slot;\r | |
212 | backward += delta;\r | |
213 | if (backward > max_backward || (CAPPED_CHAINS && !delta)) break;\r | |
214 | prev_ix = (cur_ix - backward) & ring_buffer_mask;\r | |
215 | slot = self->banks[bank].slots[last].next;\r | |
216 | delta = self->banks[bank].slots[last].delta;\r | |
217 | if (cur_ix_masked + best_len > ring_buffer_mask ||\r | |
218 | prev_ix + best_len > ring_buffer_mask ||\r | |
219 | data[cur_ix_masked + best_len] != data[prev_ix + best_len]) {\r | |
220 | continue;\r | |
221 | }\r | |
222 | {\r | |
223 | const size_t len = FindMatchLengthWithLimit(&data[prev_ix],\r | |
224 | &data[cur_ix_masked],\r | |
225 | max_length);\r | |
226 | if (len >= 4) {\r | |
227 | /* Comparing for >= 3 does not change the semantics, but just saves\r | |
228 | for a few unnecessary binary logarithms in backward reference\r | |
229 | score, since we are not interested in such short matches. */\r | |
230 | score_t score = BackwardReferenceScore(len, backward);\r | |
231 | if (best_score < score) {\r | |
232 | best_score = score;\r | |
233 | best_len = len;\r | |
234 | out->len = best_len;\r | |
235 | out->distance = backward;\r | |
236 | out->score = best_score;\r | |
11b7501a SB |
237 | }\r |
238 | }\r | |
239 | }\r | |
240 | }\r | |
dd4f667e | 241 | FN(Store)(handle, data, ring_buffer_mask, cur_ix);\r |
11b7501a | 242 | }\r |
dd4f667e LG |
243 | if (out->score == min_score) {\r |
244 | SearchInStaticDictionary(dictionary,\r | |
245 | handle, &data[cur_ix_masked], max_length, max_backward + gap,\r | |
246 | max_distance, out, BROTLI_FALSE);\r | |
11b7501a | 247 | }\r |
11b7501a SB |
248 | }\r |
249 | \r | |
250 | #undef BANK_SIZE\r | |
251 | #undef BUCKET_SIZE\r | |
252 | #undef CAPPED_CHAINS\r | |
253 | \r | |
254 | #undef HashForgetfulChain\r |