1 | /* Copyright 2013 Google Inc. All Rights Reserved. |
2 | |
3 | Distributed under MIT license. |
4 | See file LICENSE for detail or copy at https://opensource.org/licenses/MIT |
5 | */ |
6 | |
7 | /* Function to find backward reference copies. */ |
8 | |
9 | #include "./backward_references_hq.h" |
10 | |
11 | #include <string.h> /* memcpy, memset */ |
12 | |
13 | #include "../common/constants.h" |
14 | #include "../common/platform.h" |
15 | #include <brotli/types.h> |
16 | #include "./command.h" |
17 | #include "./fast_log.h" |
18 | #include "./find_match_length.h" |
19 | #include "./literal_cost.h" |
20 | #include "./memory.h" |
21 | #include "./params.h" |
22 | #include "./prefix.h" |
23 | #include "./quality.h" |
24 | |
25 | #if defined(__cplusplus) || defined(c_plusplus) |
26 | extern "C" { |
27 | #endif |
28 | |
29 | #define BROTLI_MAX_EFFECTIVE_DISTANCE_ALPHABET_SIZE 544 |
30 | |
31 | static const float kInfinity = 1.7e38f; /* ~= 2 ^ 127 */ |
32 | |
33 | static const uint32_t kDistanceCacheIndex[] = { |
34 | 0, 1, 2, 3, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, |
35 | }; |
36 | static const int kDistanceCacheOffset[] = { |
37 | 0, 0, 0, 0, -1, 1, -2, 2, -3, 3, -1, 1, -2, 2, -3, 3 |
38 | }; |
39 | |
40 | void BrotliInitZopfliNodes(ZopfliNode* array, size_t length) { |
41 | ZopfliNode stub; |
42 | size_t i; |
43 | stub.length = 1; |
44 | stub.distance = 0; |
45 | stub.dcode_insert_length = 0; |
46 | stub.u.cost = kInfinity; |
47 | for (i = 0; i < length; ++i) array[i] = stub; |
48 | } |
49 | |
50 | static BROTLI_INLINE uint32_t ZopfliNodeCopyLength(const ZopfliNode* self) { |
51 | return self->length & 0x1FFFFFF; |
52 | } |
53 | |
54 | static BROTLI_INLINE uint32_t ZopfliNodeLengthCode(const ZopfliNode* self) { |
55 | const uint32_t modifier = self->length >> 25; |
56 | return ZopfliNodeCopyLength(self) + 9u - modifier; |
57 | } |
58 | |
59 | static BROTLI_INLINE uint32_t ZopfliNodeCopyDistance(const ZopfliNode* self) { |
60 | return self->distance; |
61 | } |
62 | |
63 | static BROTLI_INLINE uint32_t ZopfliNodeDistanceCode(const ZopfliNode* self) { |
64 | const uint32_t short_code = self->dcode_insert_length >> 27; |
65 | return short_code == 0 ? |
66 | ZopfliNodeCopyDistance(self) + BROTLI_NUM_DISTANCE_SHORT_CODES - 1 : |
67 | short_code - 1; |
68 | } |
69 | |
70 | static BROTLI_INLINE uint32_t ZopfliNodeCommandLength(const ZopfliNode* self) { |
71 | return ZopfliNodeCopyLength(self) + (self->dcode_insert_length & 0x7FFFFFF); |
72 | } |
73 | |
74 | /* Histogram based cost model for zopflification. */ |
75 | typedef struct ZopfliCostModel { |
76 | /* The insert and copy length symbols. */ |
77 | float cost_cmd_[BROTLI_NUM_COMMAND_SYMBOLS]; |
78 | float* cost_dist_; |
79 | uint32_t distance_histogram_size; |
80 | /* Cumulative costs of literals per position in the stream. */ |
81 | float* literal_costs_; |
82 | float min_cost_cmd_; |
83 | size_t num_bytes_; |
84 | } ZopfliCostModel; |
85 | |
86 | static void InitZopfliCostModel( |
87 | MemoryManager* m, ZopfliCostModel* self, const BrotliDistanceParams* dist, |
88 | size_t num_bytes) { |
89 | uint32_t distance_histogram_size = dist->alphabet_size; |
90 | if (distance_histogram_size > BROTLI_MAX_EFFECTIVE_DISTANCE_ALPHABET_SIZE) { |
91 | distance_histogram_size = BROTLI_MAX_EFFECTIVE_DISTANCE_ALPHABET_SIZE; |
92 | } |
93 | self->num_bytes_ = num_bytes; |
94 | self->literal_costs_ = BROTLI_ALLOC(m, float, num_bytes + 2); |
95 | self->cost_dist_ = BROTLI_ALLOC(m, float, dist->alphabet_size); |
96 | self->distance_histogram_size = distance_histogram_size; |
97 | if (BROTLI_IS_OOM(m)) return; |
98 | } |
99 | |
100 | static void CleanupZopfliCostModel(MemoryManager* m, ZopfliCostModel* self) { |
101 | BROTLI_FREE(m, self->literal_costs_); |
102 | BROTLI_FREE(m, self->cost_dist_); |
103 | } |
104 | |
105 | static void SetCost(const uint32_t* histogram, size_t histogram_size, |
106 | BROTLI_BOOL literal_histogram, float* cost) { |
107 | size_t sum = 0; |
108 | size_t missing_symbol_sum; |
109 | float log2sum; |
110 | float missing_symbol_cost; |
111 | size_t i; |
112 | for (i = 0; i < histogram_size; i++) { |
113 | sum += histogram[i]; |
114 | } |
115 | log2sum = (float)FastLog2(sum); |
116 | missing_symbol_sum = sum; |
117 | if (!literal_histogram) { |
118 | for (i = 0; i < histogram_size; i++) { |
119 | if (histogram[i] == 0) missing_symbol_sum++; |
120 | } |
121 | } |
122 | missing_symbol_cost = (float)FastLog2(missing_symbol_sum) + 2; |
123 | for (i = 0; i < histogram_size; i++) { |
124 | if (histogram[i] == 0) { |
125 | cost[i] = missing_symbol_cost; |
126 | continue; |
127 | } |
128 | |
129 | /* Shannon bits for this symbol. */ |
130 | cost[i] = log2sum - (float)FastLog2(histogram[i]); |
131 | |
132 | /* Cannot be coded with less than 1 bit */ |
133 | if (cost[i] < 1) cost[i] = 1; |
134 | } |
135 | } |
136 | |
137 | static void ZopfliCostModelSetFromCommands(ZopfliCostModel* self, |
138 | size_t position, |
139 | const uint8_t* ringbuffer, |
140 | size_t ringbuffer_mask, |
141 | const Command* commands, |
142 | size_t num_commands, |
143 | size_t last_insert_len) { |
144 | uint32_t histogram_literal[BROTLI_NUM_LITERAL_SYMBOLS]; |
145 | uint32_t histogram_cmd[BROTLI_NUM_COMMAND_SYMBOLS]; |
146 | uint32_t histogram_dist[BROTLI_MAX_EFFECTIVE_DISTANCE_ALPHABET_SIZE]; |
147 | float cost_literal[BROTLI_NUM_LITERAL_SYMBOLS]; |
148 | size_t pos = position - last_insert_len; |
149 | float min_cost_cmd = kInfinity; |
150 | size_t i; |
151 | float* cost_cmd = self->cost_cmd_; |
152 | |
153 | memset(histogram_literal, 0, sizeof(histogram_literal)); |
154 | memset(histogram_cmd, 0, sizeof(histogram_cmd)); |
155 | memset(histogram_dist, 0, sizeof(histogram_dist)); |
156 | |
157 | for (i = 0; i < num_commands; i++) { |
158 | size_t inslength = commands[i].insert_len_; |
159 | size_t copylength = CommandCopyLen(&commands[i]); |
160 | size_t distcode = commands[i].dist_prefix_ & 0x3FF; |
161 | size_t cmdcode = commands[i].cmd_prefix_; |
162 | size_t j; |
163 | |
164 | histogram_cmd[cmdcode]++; |
165 | if (cmdcode >= 128) histogram_dist[distcode]++; |
166 | |
167 | for (j = 0; j < inslength; j++) { |
168 | histogram_literal[ringbuffer[(pos + j) & ringbuffer_mask]]++; |
169 | } |
170 | |
171 | pos += inslength + copylength; |
172 | } |
173 | |
174 | SetCost(histogram_literal, BROTLI_NUM_LITERAL_SYMBOLS, BROTLI_TRUE, |
175 | cost_literal); |
176 | SetCost(histogram_cmd, BROTLI_NUM_COMMAND_SYMBOLS, BROTLI_FALSE, |
177 | cost_cmd); |
178 | SetCost(histogram_dist, self->distance_histogram_size, BROTLI_FALSE, |
179 | self->cost_dist_); |
180 | |
181 | for (i = 0; i < BROTLI_NUM_COMMAND_SYMBOLS; ++i) { |
182 | min_cost_cmd = BROTLI_MIN(float, min_cost_cmd, cost_cmd[i]); |
183 | } |
184 | self->min_cost_cmd_ = min_cost_cmd; |
185 | |
186 | { |
187 | float* literal_costs = self->literal_costs_; |
188 | float literal_carry = 0.0; |
189 | size_t num_bytes = self->num_bytes_; |
190 | literal_costs[0] = 0.0; |
191 | for (i = 0; i < num_bytes; ++i) { |
192 | literal_carry += |
193 | cost_literal[ringbuffer[(position + i) & ringbuffer_mask]]; |
194 | literal_costs[i + 1] = literal_costs[i] + literal_carry; |
195 | literal_carry -= literal_costs[i + 1] - literal_costs[i]; |
196 | } |
197 | } |
198 | } |
199 | |
200 | static void ZopfliCostModelSetFromLiteralCosts(ZopfliCostModel* self, |
201 | size_t position, |
202 | const uint8_t* ringbuffer, |
203 | size_t ringbuffer_mask) { |
204 | float* literal_costs = self->literal_costs_; |
205 | float literal_carry = 0.0; |
206 | float* cost_dist = self->cost_dist_; |
207 | float* cost_cmd = self->cost_cmd_; |
208 | size_t num_bytes = self->num_bytes_; |
209 | size_t i; |
210 | BrotliEstimateBitCostsForLiterals(position, num_bytes, ringbuffer_mask, |
211 | ringbuffer, &literal_costs[1]); |
212 | literal_costs[0] = 0.0; |
213 | for (i = 0; i < num_bytes; ++i) { |
214 | literal_carry += literal_costs[i + 1]; |
215 | literal_costs[i + 1] = literal_costs[i] + literal_carry; |
216 | literal_carry -= literal_costs[i + 1] - literal_costs[i]; |
217 | } |
218 | for (i = 0; i < BROTLI_NUM_COMMAND_SYMBOLS; ++i) { |
219 | cost_cmd[i] = (float)FastLog2(11 + (uint32_t)i); |
220 | } |
221 | for (i = 0; i < self->distance_histogram_size; ++i) { |
222 | cost_dist[i] = (float)FastLog2(20 + (uint32_t)i); |
223 | } |
224 | self->min_cost_cmd_ = (float)FastLog2(11); |
225 | } |
226 | |
227 | static BROTLI_INLINE float ZopfliCostModelGetCommandCost( |
228 | const ZopfliCostModel* self, uint16_t cmdcode) { |
229 | return self->cost_cmd_[cmdcode]; |
230 | } |
231 | |
232 | static BROTLI_INLINE float ZopfliCostModelGetDistanceCost( |
233 | const ZopfliCostModel* self, size_t distcode) { |
234 | return self->cost_dist_[distcode]; |
235 | } |
236 | |
237 | static BROTLI_INLINE float ZopfliCostModelGetLiteralCosts( |
238 | const ZopfliCostModel* self, size_t from, size_t to) { |
239 | return self->literal_costs_[to] - self->literal_costs_[from]; |
240 | } |
241 | |
242 | static BROTLI_INLINE float ZopfliCostModelGetMinCostCmd( |
243 | const ZopfliCostModel* self) { |
244 | return self->min_cost_cmd_; |
245 | } |
246 | |
247 | /* REQUIRES: len >= 2, start_pos <= pos */ |
248 | /* REQUIRES: cost < kInfinity, nodes[start_pos].cost < kInfinity */ |
249 | /* Maintains the "ZopfliNode array invariant". */ |
250 | static BROTLI_INLINE void UpdateZopfliNode(ZopfliNode* nodes, size_t pos, |
251 | size_t start_pos, size_t len, size_t len_code, size_t dist, |
252 | size_t short_code, float cost) { |
253 | ZopfliNode* next = &nodes[pos + len]; |
254 | next->length = (uint32_t)(len | ((len + 9u - len_code) << 25)); |
255 | next->distance = (uint32_t)dist; |
256 | next->dcode_insert_length = (uint32_t)( |
257 | (short_code << 27) | (pos - start_pos)); |
258 | next->u.cost = cost; |
259 | } |
260 | |
261 | typedef struct PosData { |
262 | size_t pos; |
263 | int distance_cache[4]; |
264 | float costdiff; |
265 | float cost; |
266 | } PosData; |
267 | |
268 | /* Maintains the smallest 8 cost difference together with their positions */ |
269 | typedef struct StartPosQueue { |
270 | PosData q_[8]; |
271 | size_t idx_; |
272 | } StartPosQueue; |
273 | |
274 | static BROTLI_INLINE void InitStartPosQueue(StartPosQueue* self) { |
275 | self->idx_ = 0; |
276 | } |
277 | |
278 | static size_t StartPosQueueSize(const StartPosQueue* self) { |
279 | return BROTLI_MIN(size_t, self->idx_, 8); |
280 | } |
281 | |
282 | static void StartPosQueuePush(StartPosQueue* self, const PosData* posdata) { |
283 | size_t offset = ~(self->idx_++) & 7; |
284 | size_t len = StartPosQueueSize(self); |
285 | size_t i; |
286 | PosData* q = self->q_; |
287 | q[offset] = *posdata; |
288 | /* Restore the sorted order. In the list of |len| items at most |len - 1| |
289 | adjacent element comparisons / swaps are required. */ |
290 | for (i = 1; i < len; ++i) { |
291 | if (q[offset & 7].costdiff > q[(offset + 1) & 7].costdiff) { |
292 | BROTLI_SWAP(PosData, q, offset & 7, (offset + 1) & 7); |
293 | } |
294 | ++offset; |
295 | } |
296 | } |
297 | |
298 | static const PosData* StartPosQueueAt(const StartPosQueue* self, size_t k) { |
299 | return &self->q_[(k - self->idx_) & 7]; |
300 | } |
301 | |
302 | /* Returns the minimum possible copy length that can improve the cost of any */ |
303 | /* future position. */ |
304 | static size_t ComputeMinimumCopyLength(const float start_cost, |
305 | const ZopfliNode* nodes, |
306 | const size_t num_bytes, |
307 | const size_t pos) { |
308 | /* Compute the minimum possible cost of reaching any future position. */ |
309 | float min_cost = start_cost; |
310 | size_t len = 2; |
311 | size_t next_len_bucket = 4; |
312 | size_t next_len_offset = 10; |
313 | while (pos + len <= num_bytes && nodes[pos + len].u.cost <= min_cost) { |
314 | /* We already reached (pos + len) with no more cost than the minimum |
315 | possible cost of reaching anything from this pos, so there is no point in |
316 | looking for lengths <= len. */ |
317 | ++len; |
318 | if (len == next_len_offset) { |
319 | /* We reached the next copy length code bucket, so we add one more |
320 | extra bit to the minimum cost. */ |
321 | min_cost += 1.0f; |
322 | next_len_offset += next_len_bucket; |
323 | next_len_bucket *= 2; |
324 | } |
325 | } |
326 | return len; |
327 | } |
328 | |
329 | /* REQUIRES: nodes[pos].cost < kInfinity |
330 | REQUIRES: nodes[0..pos] satisfies that "ZopfliNode array invariant". */ |
331 | static uint32_t ComputeDistanceShortcut(const size_t block_start, |
332 | const size_t pos, |
333 | const size_t max_backward_limit, |
334 | const size_t gap, |
335 | const ZopfliNode* nodes) { |
336 | const size_t clen = ZopfliNodeCopyLength(&nodes[pos]); |
337 | const size_t ilen = nodes[pos].dcode_insert_length & 0x7FFFFFF; |
338 | const size_t dist = ZopfliNodeCopyDistance(&nodes[pos]); |
339 | /* Since |block_start + pos| is the end position of the command, the copy part |
340 | starts from |block_start + pos - clen|. Distances that are greater than |
341 | this or greater than |max_backward_limit| + |gap| are static dictionary |
342 | references, and do not update the last distances. |
343 | Also distance code 0 (last distance) does not update the last distances. */ |
344 | if (pos == 0) { |
345 | return 0; |
346 | } else if (dist + clen <= block_start + pos + gap && |
347 | dist <= max_backward_limit + gap && |
348 | ZopfliNodeDistanceCode(&nodes[pos]) > 0) { |
349 | return (uint32_t)pos; |
350 | } else { |
351 | return nodes[pos - clen - ilen].u.shortcut; |
352 | } |
353 | } |
354 | |
355 | /* Fills in dist_cache[0..3] with the last four distances (as defined by |
356 | Section 4. of the Spec) that would be used at (block_start + pos) if we |
357 | used the shortest path of commands from block_start, computed from |
358 | nodes[0..pos]. The last four distances at block_start are in |
359 | starting_dist_cache[0..3]. |
360 | REQUIRES: nodes[pos].cost < kInfinity |
361 | REQUIRES: nodes[0..pos] satisfies that "ZopfliNode array invariant". */ |
362 | static void ComputeDistanceCache(const size_t pos, |
363 | const int* starting_dist_cache, |
364 | const ZopfliNode* nodes, |
365 | int* dist_cache) { |
366 | int idx = 0; |
367 | size_t p = nodes[pos].u.shortcut; |
368 | while (idx < 4 && p > 0) { |
369 | const size_t ilen = nodes[p].dcode_insert_length & 0x7FFFFFF; |
370 | const size_t clen = ZopfliNodeCopyLength(&nodes[p]); |
371 | const size_t dist = ZopfliNodeCopyDistance(&nodes[p]); |
372 | dist_cache[idx++] = (int)dist; |
373 | /* Because of prerequisite, p >= clen + ilen >= 2. */ |
374 | p = nodes[p - clen - ilen].u.shortcut; |
375 | } |
376 | for (; idx < 4; ++idx) { |
377 | dist_cache[idx] = *starting_dist_cache++; |
378 | } |
379 | } |
380 | |
381 | /* Maintains "ZopfliNode array invariant" and pushes node to the queue, if it |
382 | is eligible. */ |
383 | static void EvaluateNode( |
384 | const size_t block_start, const size_t pos, const size_t max_backward_limit, |
385 | const size_t gap, const int* starting_dist_cache, |
386 | const ZopfliCostModel* model, StartPosQueue* queue, ZopfliNode* nodes) { |
387 | /* Save cost, because ComputeDistanceCache invalidates it. */ |
388 | float node_cost = nodes[pos].u.cost; |
389 | nodes[pos].u.shortcut = ComputeDistanceShortcut( |
390 | block_start, pos, max_backward_limit, gap, nodes); |
391 | if (node_cost <= ZopfliCostModelGetLiteralCosts(model, 0, pos)) { |
392 | PosData posdata; |
393 | posdata.pos = pos; |
394 | posdata.cost = node_cost; |
395 | posdata.costdiff = node_cost - |
396 | ZopfliCostModelGetLiteralCosts(model, 0, pos); |
397 | ComputeDistanceCache( |
398 | pos, starting_dist_cache, nodes, posdata.distance_cache); |
399 | StartPosQueuePush(queue, &posdata); |
400 | } |
401 | } |
402 | |
403 | /* Returns longest copy length. */ |
404 | static size_t UpdateNodes( |
405 | const size_t num_bytes, const size_t block_start, const size_t pos, |
406 | const uint8_t* ringbuffer, const size_t ringbuffer_mask, |
407 | const BrotliEncoderParams* params, const size_t max_backward_limit, |
408 | const int* starting_dist_cache, const size_t num_matches, |
409 | const BackwardMatch* matches, const ZopfliCostModel* model, |
410 | StartPosQueue* queue, ZopfliNode* nodes) { |
411 | const size_t cur_ix = block_start + pos; |
412 | const size_t cur_ix_masked = cur_ix & ringbuffer_mask; |
413 | const size_t max_distance = BROTLI_MIN(size_t, cur_ix, max_backward_limit); |
414 | const size_t max_len = num_bytes - pos; |
415 | const size_t max_zopfli_len = MaxZopfliLen(params); |
416 | const size_t max_iters = MaxZopfliCandidates(params); |
417 | size_t min_len; |
418 | size_t result = 0; |
419 | size_t k; |
420 | size_t gap = 0; |
421 | |
422 | EvaluateNode(block_start, pos, max_backward_limit, gap, |
423 | starting_dist_cache, model, queue, nodes); |
424 | |
425 | { |
426 | const PosData* posdata = StartPosQueueAt(queue, 0); |
427 | float min_cost = (posdata->cost + ZopfliCostModelGetMinCostCmd(model) + |
428 | ZopfliCostModelGetLiteralCosts(model, posdata->pos, pos)); |
429 | min_len = ComputeMinimumCopyLength(min_cost, nodes, num_bytes, pos); |
430 | } |
431 | |
432 | /* Go over the command starting positions in order of increasing cost |
433 | difference. */ |
434 | for (k = 0; k < max_iters && k < StartPosQueueSize(queue); ++k) { |
435 | const PosData* posdata = StartPosQueueAt(queue, k); |
436 | const size_t start = posdata->pos; |
437 | const uint16_t inscode = GetInsertLengthCode(pos - start); |
438 | const float start_costdiff = posdata->costdiff; |
439 | const float base_cost = start_costdiff + (float)GetInsertExtra(inscode) + |
440 | ZopfliCostModelGetLiteralCosts(model, 0, pos); |
441 | |
442 | /* Look for last distance matches using the distance cache from this |
443 | starting position. */ |
444 | size_t best_len = min_len - 1; |
445 | size_t j = 0; |
446 | for (; j < BROTLI_NUM_DISTANCE_SHORT_CODES && best_len < max_len; ++j) { |
447 | const size_t idx = kDistanceCacheIndex[j]; |
448 | const size_t backward = |
449 | (size_t)(posdata->distance_cache[idx] + kDistanceCacheOffset[j]); |
450 | size_t prev_ix = cur_ix - backward; |
451 | size_t len = 0; |
452 | uint8_t continuation = ringbuffer[cur_ix_masked + best_len]; |
453 | if (cur_ix_masked + best_len > ringbuffer_mask) { |
454 | break; |
455 | } |
456 | if (BROTLI_PREDICT_FALSE(backward > max_distance + gap)) { |
457 | /* Word dictionary -> ignore. */ |
458 | continue; |
459 | } |
460 | if (backward <= max_distance) { |
461 | /* Regular backward reference. */ |
462 | if (prev_ix >= cur_ix) { |
463 | continue; |
464 | } |
465 | |
466 | prev_ix &= ringbuffer_mask; |
467 | if (prev_ix + best_len > ringbuffer_mask || |
468 | continuation != ringbuffer[prev_ix + best_len]) { |
469 | continue; |
470 | } |
471 | len = FindMatchLengthWithLimit(&ringbuffer[prev_ix], |
472 | &ringbuffer[cur_ix_masked], |
473 | max_len); |
474 | } else { |
475 | continue; |
476 | } |
477 | { |
478 | const float dist_cost = base_cost + |
479 | ZopfliCostModelGetDistanceCost(model, j); |
480 | size_t l; |
481 | for (l = best_len + 1; l <= len; ++l) { |
482 | const uint16_t copycode = GetCopyLengthCode(l); |
483 | const uint16_t cmdcode = |
484 | CombineLengthCodes(inscode, copycode, j == 0); |
485 | const float cost = (cmdcode < 128 ? base_cost : dist_cost) + |
486 | (float)GetCopyExtra(copycode) + |
487 | ZopfliCostModelGetCommandCost(model, cmdcode); |
488 | if (cost < nodes[pos + l].u.cost) { |
489 | UpdateZopfliNode(nodes, pos, start, l, l, backward, j + 1, cost); |
490 | result = BROTLI_MAX(size_t, result, l); |
491 | } |
492 | best_len = l; |
493 | } |
494 | } |
495 | } |
496 | |
497 | /* At higher iterations look only for new last distance matches, since |
498 | looking only for new command start positions with the same distances |
499 | does not help much. */ |
500 | if (k >= 2) continue; |
501 | |
502 | { |
503 | /* Loop through all possible copy lengths at this position. */ |
504 | size_t len = min_len; |
505 | for (j = 0; j < num_matches; ++j) { |
506 | BackwardMatch match = matches[j]; |
507 | size_t dist = match.distance; |
508 | BROTLI_BOOL is_dictionary_match = |
509 | TO_BROTLI_BOOL(dist > max_distance + gap); |
510 | /* We already tried all possible last distance matches, so we can use |
511 | normal distance code here. */ |
512 | size_t dist_code = dist + BROTLI_NUM_DISTANCE_SHORT_CODES - 1; |
513 | uint16_t dist_symbol; |
514 | uint32_t ; |
515 | uint32_t ; |
516 | float dist_cost; |
517 | size_t max_match_len; |
518 | PrefixEncodeCopyDistance( |
519 | dist_code, params->dist.num_direct_distance_codes, |
520 | params->dist.distance_postfix_bits, &dist_symbol, &distextra); |
521 | distnumextra = dist_symbol >> 10; |
522 | dist_cost = base_cost + (float)distnumextra + |
523 | ZopfliCostModelGetDistanceCost(model, dist_symbol & 0x3FF); |
524 | |
525 | /* Try all copy lengths up until the maximum copy length corresponding |
526 | to this distance. If the distance refers to the static dictionary, or |
527 | the maximum length is long enough, try only one maximum length. */ |
528 | max_match_len = BackwardMatchLength(&match); |
529 | if (len < max_match_len && |
530 | (is_dictionary_match || max_match_len > max_zopfli_len)) { |
531 | len = max_match_len; |
532 | } |
533 | for (; len <= max_match_len; ++len) { |
534 | const size_t len_code = |
535 | is_dictionary_match ? BackwardMatchLengthCode(&match) : len; |
536 | const uint16_t copycode = GetCopyLengthCode(len_code); |
537 | const uint16_t cmdcode = CombineLengthCodes(inscode, copycode, 0); |
538 | const float cost = dist_cost + (float)GetCopyExtra(copycode) + |
539 | ZopfliCostModelGetCommandCost(model, cmdcode); |
540 | if (cost < nodes[pos + len].u.cost) { |
541 | UpdateZopfliNode(nodes, pos, start, len, len_code, dist, 0, cost); |
542 | result = BROTLI_MAX(size_t, result, len); |
543 | } |
544 | } |
545 | } |
546 | } |
547 | } |
548 | return result; |
549 | } |
550 | |
551 | static size_t ComputeShortestPathFromNodes(size_t num_bytes, |
552 | ZopfliNode* nodes) { |
553 | size_t index = num_bytes; |
554 | size_t num_commands = 0; |
555 | while ((nodes[index].dcode_insert_length & 0x7FFFFFF) == 0 && |
556 | nodes[index].length == 1) --index; |
557 | nodes[index].u.next = BROTLI_UINT32_MAX; |
558 | while (index != 0) { |
559 | size_t len = ZopfliNodeCommandLength(&nodes[index]); |
560 | index -= len; |
561 | nodes[index].u.next = (uint32_t)len; |
562 | num_commands++; |
563 | } |
564 | return num_commands; |
565 | } |
566 | |
567 | /* REQUIRES: nodes != NULL and len(nodes) >= num_bytes + 1 */ |
568 | void BrotliZopfliCreateCommands(const size_t num_bytes, |
569 | const size_t block_start, const ZopfliNode* nodes, int* dist_cache, |
570 | size_t* last_insert_len, const BrotliEncoderParams* params, |
571 | Command* commands, size_t* num_literals) { |
572 | const size_t max_backward_limit = BROTLI_MAX_BACKWARD_LIMIT(params->lgwin); |
573 | size_t pos = 0; |
574 | uint32_t offset = nodes[0].u.next; |
575 | size_t i; |
576 | size_t gap = 0; |
577 | for (i = 0; offset != BROTLI_UINT32_MAX; i++) { |
578 | const ZopfliNode* next = &nodes[pos + offset]; |
579 | size_t copy_length = ZopfliNodeCopyLength(next); |
580 | size_t insert_length = next->dcode_insert_length & 0x7FFFFFF; |
581 | pos += insert_length; |
582 | offset = next->u.next; |
583 | if (i == 0) { |
584 | insert_length += *last_insert_len; |
585 | *last_insert_len = 0; |
586 | } |
587 | { |
588 | size_t distance = ZopfliNodeCopyDistance(next); |
589 | size_t len_code = ZopfliNodeLengthCode(next); |
590 | size_t max_distance = BROTLI_MIN(size_t, |
591 | block_start + pos, max_backward_limit); |
592 | BROTLI_BOOL is_dictionary = |
593 | TO_BROTLI_BOOL(distance > max_distance + gap); |
594 | size_t dist_code = ZopfliNodeDistanceCode(next); |
595 | InitCommand(&commands[i], ¶ms->dist, insert_length, |
596 | copy_length, (int)len_code - (int)copy_length, dist_code); |
597 | |
598 | if (!is_dictionary && dist_code > 0) { |
599 | dist_cache[3] = dist_cache[2]; |
600 | dist_cache[2] = dist_cache[1]; |
601 | dist_cache[1] = dist_cache[0]; |
602 | dist_cache[0] = (int)distance; |
603 | } |
604 | } |
605 | |
606 | *num_literals += insert_length; |
607 | pos += copy_length; |
608 | } |
609 | *last_insert_len += num_bytes - pos; |
610 | } |
611 | |
612 | static size_t ZopfliIterate(size_t num_bytes, size_t position, |
613 | const uint8_t* ringbuffer, size_t ringbuffer_mask, |
614 | const BrotliEncoderParams* params, const size_t gap, const int* dist_cache, |
615 | const ZopfliCostModel* model, const uint32_t* num_matches, |
616 | const BackwardMatch* matches, ZopfliNode* nodes) { |
617 | const size_t max_backward_limit = BROTLI_MAX_BACKWARD_LIMIT(params->lgwin); |
618 | const size_t max_zopfli_len = MaxZopfliLen(params); |
619 | StartPosQueue queue; |
620 | size_t cur_match_pos = 0; |
621 | size_t i; |
622 | nodes[0].length = 0; |
623 | nodes[0].u.cost = 0; |
624 | InitStartPosQueue(&queue); |
625 | for (i = 0; i + 3 < num_bytes; i++) { |
626 | size_t skip = UpdateNodes(num_bytes, position, i, ringbuffer, |
627 | ringbuffer_mask, params, max_backward_limit, dist_cache, |
628 | num_matches[i], &matches[cur_match_pos], model, &queue, nodes); |
629 | if (skip < BROTLI_LONG_COPY_QUICK_STEP) skip = 0; |
630 | cur_match_pos += num_matches[i]; |
631 | if (num_matches[i] == 1 && |
632 | BackwardMatchLength(&matches[cur_match_pos - 1]) > max_zopfli_len) { |
633 | skip = BROTLI_MAX(size_t, |
634 | BackwardMatchLength(&matches[cur_match_pos - 1]), skip); |
635 | } |
636 | if (skip > 1) { |
637 | skip--; |
638 | while (skip) { |
639 | i++; |
640 | if (i + 3 >= num_bytes) break; |
641 | EvaluateNode(position, i, max_backward_limit, gap, |
642 | dist_cache, model, &queue, nodes); |
643 | cur_match_pos += num_matches[i]; |
644 | skip--; |
645 | } |
646 | } |
647 | } |
648 | return ComputeShortestPathFromNodes(num_bytes, nodes); |
649 | } |
650 | |
651 | /* REQUIRES: nodes != NULL and len(nodes) >= num_bytes + 1 */ |
652 | size_t BrotliZopfliComputeShortestPath(MemoryManager* m, size_t num_bytes, |
653 | size_t position, const uint8_t* ringbuffer, size_t ringbuffer_mask, |
654 | const BrotliEncoderParams* params, |
655 | const int* dist_cache, HasherHandle hasher, ZopfliNode* nodes) { |
656 | const size_t max_backward_limit = BROTLI_MAX_BACKWARD_LIMIT(params->lgwin); |
657 | const size_t max_zopfli_len = MaxZopfliLen(params); |
658 | ZopfliCostModel model; |
659 | StartPosQueue queue; |
660 | BackwardMatch matches[2 * (MAX_NUM_MATCHES_H10 + 64)]; |
661 | const size_t store_end = num_bytes >= StoreLookaheadH10() ? |
662 | position + num_bytes - StoreLookaheadH10() + 1 : position; |
663 | size_t i; |
664 | size_t gap = 0; |
665 | size_t lz_matches_offset = 0; |
666 | nodes[0].length = 0; |
667 | nodes[0].u.cost = 0; |
668 | InitZopfliCostModel(m, &model, ¶ms->dist, num_bytes); |
669 | if (BROTLI_IS_OOM(m)) return 0; |
670 | ZopfliCostModelSetFromLiteralCosts( |
671 | &model, position, ringbuffer, ringbuffer_mask); |
672 | InitStartPosQueue(&queue); |
673 | for (i = 0; i + HashTypeLengthH10() - 1 < num_bytes; i++) { |
674 | const size_t pos = position + i; |
675 | const size_t max_distance = BROTLI_MIN(size_t, pos, max_backward_limit); |
676 | size_t skip; |
677 | size_t num_matches; |
678 | num_matches = FindAllMatchesH10(hasher, |
679 | ¶ms->dictionary, |
680 | ringbuffer, ringbuffer_mask, pos, num_bytes - i, max_distance, |
681 | gap, params, &matches[lz_matches_offset]); |
682 | if (num_matches > 0 && |
683 | BackwardMatchLength(&matches[num_matches - 1]) > max_zopfli_len) { |
684 | matches[0] = matches[num_matches - 1]; |
685 | num_matches = 1; |
686 | } |
687 | skip = UpdateNodes(num_bytes, position, i, ringbuffer, ringbuffer_mask, |
688 | params, max_backward_limit, dist_cache, num_matches, matches, &model, |
689 | &queue, nodes); |
690 | if (skip < BROTLI_LONG_COPY_QUICK_STEP) skip = 0; |
691 | if (num_matches == 1 && BackwardMatchLength(&matches[0]) > max_zopfli_len) { |
692 | skip = BROTLI_MAX(size_t, BackwardMatchLength(&matches[0]), skip); |
693 | } |
694 | if (skip > 1) { |
695 | /* Add the tail of the copy to the hasher. */ |
696 | StoreRangeH10(hasher, ringbuffer, ringbuffer_mask, pos + 1, BROTLI_MIN( |
697 | size_t, pos + skip, store_end)); |
698 | skip--; |
699 | while (skip) { |
700 | i++; |
701 | if (i + HashTypeLengthH10() - 1 >= num_bytes) break; |
702 | EvaluateNode(position, i, max_backward_limit, gap, |
703 | dist_cache, &model, &queue, nodes); |
704 | skip--; |
705 | } |
706 | } |
707 | } |
708 | CleanupZopfliCostModel(m, &model); |
709 | return ComputeShortestPathFromNodes(num_bytes, nodes); |
710 | } |
711 | |
712 | void BrotliCreateZopfliBackwardReferences(MemoryManager* m, size_t num_bytes, |
713 | size_t position, const uint8_t* ringbuffer, size_t ringbuffer_mask, |
714 | const BrotliEncoderParams* params, |
715 | HasherHandle hasher, int* dist_cache, size_t* last_insert_len, |
716 | Command* commands, size_t* num_commands, size_t* num_literals) { |
717 | ZopfliNode* nodes; |
718 | nodes = BROTLI_ALLOC(m, ZopfliNode, num_bytes + 1); |
719 | if (BROTLI_IS_OOM(m)) return; |
720 | BrotliInitZopfliNodes(nodes, num_bytes + 1); |
721 | *num_commands += BrotliZopfliComputeShortestPath(m, num_bytes, |
722 | position, ringbuffer, ringbuffer_mask, params, |
723 | dist_cache, hasher, nodes); |
724 | if (BROTLI_IS_OOM(m)) return; |
725 | BrotliZopfliCreateCommands(num_bytes, position, nodes, dist_cache, |
726 | last_insert_len, params, commands, num_literals); |
727 | BROTLI_FREE(m, nodes); |
728 | } |
729 | |
730 | void BrotliCreateHqZopfliBackwardReferences(MemoryManager* m, size_t num_bytes, |
731 | size_t position, const uint8_t* ringbuffer, size_t ringbuffer_mask, |
732 | const BrotliEncoderParams* params, |
733 | HasherHandle hasher, int* dist_cache, size_t* last_insert_len, |
734 | Command* commands, size_t* num_commands, size_t* num_literals) { |
735 | const size_t max_backward_limit = BROTLI_MAX_BACKWARD_LIMIT(params->lgwin); |
736 | uint32_t* num_matches = BROTLI_ALLOC(m, uint32_t, num_bytes); |
737 | size_t matches_size = 4 * num_bytes; |
738 | const size_t store_end = num_bytes >= StoreLookaheadH10() ? |
739 | position + num_bytes - StoreLookaheadH10() + 1 : position; |
740 | size_t cur_match_pos = 0; |
741 | size_t i; |
742 | size_t orig_num_literals; |
743 | size_t orig_last_insert_len; |
744 | int orig_dist_cache[4]; |
745 | size_t orig_num_commands; |
746 | ZopfliCostModel model; |
747 | ZopfliNode* nodes; |
748 | BackwardMatch* matches = BROTLI_ALLOC(m, BackwardMatch, matches_size); |
749 | size_t gap = 0; |
750 | size_t shadow_matches = 0; |
751 | if (BROTLI_IS_OOM(m)) return; |
752 | for (i = 0; i + HashTypeLengthH10() - 1 < num_bytes; ++i) { |
753 | const size_t pos = position + i; |
754 | size_t max_distance = BROTLI_MIN(size_t, pos, max_backward_limit); |
755 | size_t max_length = num_bytes - i; |
756 | size_t num_found_matches; |
757 | size_t cur_match_end; |
758 | size_t j; |
759 | /* Ensure that we have enough free slots. */ |
760 | BROTLI_ENSURE_CAPACITY(m, BackwardMatch, matches, matches_size, |
761 | cur_match_pos + MAX_NUM_MATCHES_H10 + shadow_matches); |
762 | if (BROTLI_IS_OOM(m)) return; |
763 | num_found_matches = FindAllMatchesH10(hasher, |
764 | ¶ms->dictionary, |
765 | ringbuffer, ringbuffer_mask, pos, max_length, |
766 | max_distance, gap, params, |
767 | &matches[cur_match_pos + shadow_matches]); |
768 | cur_match_end = cur_match_pos + num_found_matches; |
769 | for (j = cur_match_pos; j + 1 < cur_match_end; ++j) { |
770 | BROTLI_DCHECK(BackwardMatchLength(&matches[j]) <= |
771 | BackwardMatchLength(&matches[j + 1])); |
772 | } |
773 | num_matches[i] = (uint32_t)num_found_matches; |
774 | if (num_found_matches > 0) { |
775 | const size_t match_len = BackwardMatchLength(&matches[cur_match_end - 1]); |
776 | if (match_len > MAX_ZOPFLI_LEN_QUALITY_11) { |
777 | const size_t skip = match_len - 1; |
778 | matches[cur_match_pos++] = matches[cur_match_end - 1]; |
779 | num_matches[i] = 1; |
780 | /* Add the tail of the copy to the hasher. */ |
781 | StoreRangeH10(hasher, ringbuffer, ringbuffer_mask, pos + 1, |
782 | BROTLI_MIN(size_t, pos + match_len, store_end)); |
783 | memset(&num_matches[i + 1], 0, skip * sizeof(num_matches[0])); |
784 | i += skip; |
785 | } else { |
786 | cur_match_pos = cur_match_end; |
787 | } |
788 | } |
789 | } |
790 | orig_num_literals = *num_literals; |
791 | orig_last_insert_len = *last_insert_len; |
792 | memcpy(orig_dist_cache, dist_cache, 4 * sizeof(dist_cache[0])); |
793 | orig_num_commands = *num_commands; |
794 | nodes = BROTLI_ALLOC(m, ZopfliNode, num_bytes + 1); |
795 | if (BROTLI_IS_OOM(m)) return; |
796 | InitZopfliCostModel(m, &model, ¶ms->dist, num_bytes); |
797 | if (BROTLI_IS_OOM(m)) return; |
798 | for (i = 0; i < 2; i++) { |
799 | BrotliInitZopfliNodes(nodes, num_bytes + 1); |
800 | if (i == 0) { |
801 | ZopfliCostModelSetFromLiteralCosts( |
802 | &model, position, ringbuffer, ringbuffer_mask); |
803 | } else { |
804 | ZopfliCostModelSetFromCommands(&model, position, ringbuffer, |
805 | ringbuffer_mask, commands, *num_commands - orig_num_commands, |
806 | orig_last_insert_len); |
807 | } |
808 | *num_commands = orig_num_commands; |
809 | *num_literals = orig_num_literals; |
810 | *last_insert_len = orig_last_insert_len; |
811 | memcpy(dist_cache, orig_dist_cache, 4 * sizeof(dist_cache[0])); |
812 | *num_commands += ZopfliIterate(num_bytes, position, ringbuffer, |
813 | ringbuffer_mask, params, gap, dist_cache, &model, num_matches, matches, |
814 | nodes); |
815 | BrotliZopfliCreateCommands(num_bytes, position, nodes, dist_cache, |
816 | last_insert_len, params, commands, num_literals); |
817 | } |
818 | CleanupZopfliCostModel(m, &model); |
819 | BROTLI_FREE(m, nodes); |
820 | BROTLI_FREE(m, matches); |
821 | BROTLI_FREE(m, num_matches); |
822 | } |
823 | |
824 | #if defined(__cplusplus) || defined(c_plusplus) |
825 | } /* extern "C" */ |
826 | #endif |
827 | |