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)
26extern "C" {
27#endif
28
29#define BROTLI_MAX_EFFECTIVE_DISTANCE_ALPHABET_SIZE 544
30
31static const float kInfinity = 1.7e38f; /* ~= 2 ^ 127 */
32
33static const uint32_t kDistanceCacheIndex[] = {
34 0, 1, 2, 3, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1,
35};
36static const int kDistanceCacheOffset[] = {
37 0, 0, 0, 0, -1, 1, -2, 2, -3, 3, -1, 1, -2, 2, -3, 3
38};
39
40void 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
50static BROTLI_INLINE uint32_t ZopfliNodeCopyLength(const ZopfliNode* self) {
51 return self->length & 0x1FFFFFF;
52}
53
54static BROTLI_INLINE uint32_t ZopfliNodeLengthCode(const ZopfliNode* self) {
55 const uint32_t modifier = self->length >> 25;
56 return ZopfliNodeCopyLength(self) + 9u - modifier;
57}
58
59static BROTLI_INLINE uint32_t ZopfliNodeCopyDistance(const ZopfliNode* self) {
60 return self->distance;
61}
62
63static 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
70static 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. */
75typedef 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
86static 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
100static void CleanupZopfliCostModel(MemoryManager* m, ZopfliCostModel* self) {
101 BROTLI_FREE(m, self->literal_costs_);
102 BROTLI_FREE(m, self->cost_dist_);
103}
104
105static 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
137static 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
200static 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
227static BROTLI_INLINE float ZopfliCostModelGetCommandCost(
228 const ZopfliCostModel* self, uint16_t cmdcode) {
229 return self->cost_cmd_[cmdcode];
230}
231
232static BROTLI_INLINE float ZopfliCostModelGetDistanceCost(
233 const ZopfliCostModel* self, size_t distcode) {
234 return self->cost_dist_[distcode];
235}
236
237static 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
242static 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". */
250static 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
261typedef 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 */
269typedef struct StartPosQueue {
270 PosData q_[8];
271 size_t idx_;
272} StartPosQueue;
273
274static BROTLI_INLINE void InitStartPosQueue(StartPosQueue* self) {
275 self->idx_ = 0;
276}
277
278static size_t StartPosQueueSize(const StartPosQueue* self) {
279 return BROTLI_MIN(size_t, self->idx_, 8);
280}
281
282static 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
298static 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. */
304static 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". */
331static 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". */
362static 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. */
383static 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. */
404static 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 distextra;
515 uint32_t distnumextra;
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
551static 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 */
568void 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], &params->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
612static 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 */
652size_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, &params->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 &params->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
712void 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
730void 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 &params->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, &params->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