1 /* Copyright 2013 Google Inc. All Rights Reserved.
3 Distributed under MIT license.
4 See file LICENSE for detail or copy at https://opensource.org/licenses/MIT
7 /* Function to find backward reference copies. */
9 #include "./backward_references.h"
11 #include <math.h> /* INFINITY */
12 #include <string.h> /* memcpy, memset */
14 #include "../common/constants.h"
15 #include "../common/types.h"
16 #include "./command.h"
17 #include "./fast_log.h"
18 #include "./find_match_length.h"
19 #include "./literal_cost.h"
23 #include "./quality.h"
25 #if defined(__cplusplus) || defined(c_plusplus)
30 static const float kInfinity
= INFINITY
;
32 static const float kInfinity
= 3.4028e38f
;
35 void BrotliInitZopfliNodes(ZopfliNode
* array
, size_t length
) {
40 stub
.insert_length
= 0;
41 stub
.u
.cost
= kInfinity
;
42 for (i
= 0; i
< length
; ++i
) array
[i
] = stub
;
45 static BROTLI_INLINE
uint32_t ZopfliNodeCopyLength(const ZopfliNode
* self
) {
46 return self
->length
& 0xffffff;
49 static BROTLI_INLINE
uint32_t ZopfliNodeLengthCode(const ZopfliNode
* self
) {
50 const uint32_t modifier
= self
->length
>> 24;
51 return ZopfliNodeCopyLength(self
) + 9u - modifier
;
54 static BROTLI_INLINE
uint32_t ZopfliNodeCopyDistance(const ZopfliNode
* self
) {
55 return self
->distance
& 0x1ffffff;
58 static BROTLI_INLINE
uint32_t ZopfliNodeDistanceCode(const ZopfliNode
* self
) {
59 const uint32_t short_code
= self
->distance
>> 25;
60 return short_code
== 0 ? ZopfliNodeCopyDistance(self
) + 15 : short_code
- 1;
63 static BROTLI_INLINE
uint32_t ZopfliNodeCommandLength(const ZopfliNode
* self
) {
64 return ZopfliNodeCopyLength(self
) + self
->insert_length
;
67 /* Histogram based cost model for zopflification. */
68 typedef struct ZopfliCostModel
{
69 /* The insert and copy length symbols. */
70 float cost_cmd_
[BROTLI_NUM_COMMAND_SYMBOLS
];
71 float cost_dist_
[BROTLI_NUM_DISTANCE_SYMBOLS
];
72 /* Cumulative costs of literals per position in the stream. */
73 float* literal_costs_
;
78 static void InitZopfliCostModel(
79 MemoryManager
* m
, ZopfliCostModel
* self
, size_t num_bytes
) {
80 self
->num_bytes_
= num_bytes
;
81 self
->literal_costs_
= BROTLI_ALLOC(m
, float, num_bytes
+ 2);
82 if (BROTLI_IS_OOM(m
)) return;
85 static void CleanupZopfliCostModel(MemoryManager
* m
, ZopfliCostModel
* self
) {
86 BROTLI_FREE(m
, self
->literal_costs_
);
89 static void SetCost(const uint32_t* histogram
, size_t histogram_size
,
94 for (i
= 0; i
< histogram_size
; i
++) {
97 log2sum
= (float)FastLog2(sum
);
98 for (i
= 0; i
< histogram_size
; i
++) {
99 if (histogram
[i
] == 0) {
100 cost
[i
] = log2sum
+ 2;
104 /* Shannon bits for this symbol. */
105 cost
[i
] = log2sum
- (float)FastLog2(histogram
[i
]);
107 /* Cannot be coded with less than 1 bit */
108 if (cost
[i
] < 1) cost
[i
] = 1;
112 static void ZopfliCostModelSetFromCommands(ZopfliCostModel
* self
,
114 const uint8_t* ringbuffer
,
115 size_t ringbuffer_mask
,
116 const Command
* commands
,
118 size_t last_insert_len
) {
119 uint32_t histogram_literal
[BROTLI_NUM_LITERAL_SYMBOLS
];
120 uint32_t histogram_cmd
[BROTLI_NUM_COMMAND_SYMBOLS
];
121 uint32_t histogram_dist
[BROTLI_NUM_DISTANCE_SYMBOLS
];
122 float cost_literal
[BROTLI_NUM_LITERAL_SYMBOLS
];
123 size_t pos
= position
- last_insert_len
;
124 float min_cost_cmd
= kInfinity
;
126 float* cost_cmd
= self
->cost_cmd_
;
128 memset(histogram_literal
, 0, sizeof(histogram_literal
));
129 memset(histogram_cmd
, 0, sizeof(histogram_cmd
));
130 memset(histogram_dist
, 0, sizeof(histogram_dist
));
132 for (i
= 0; i
< num_commands
; i
++) {
133 size_t inslength
= commands
[i
].insert_len_
;
134 size_t copylength
= CommandCopyLen(&commands
[i
]);
135 size_t distcode
= commands
[i
].dist_prefix_
;
136 size_t cmdcode
= commands
[i
].cmd_prefix_
;
139 histogram_cmd
[cmdcode
]++;
140 if (cmdcode
>= 128) histogram_dist
[distcode
]++;
142 for (j
= 0; j
< inslength
; j
++) {
143 histogram_literal
[ringbuffer
[(pos
+ j
) & ringbuffer_mask
]]++;
146 pos
+= inslength
+ copylength
;
149 SetCost(histogram_literal
, BROTLI_NUM_LITERAL_SYMBOLS
, cost_literal
);
150 SetCost(histogram_cmd
, BROTLI_NUM_COMMAND_SYMBOLS
, cost_cmd
);
151 SetCost(histogram_dist
, BROTLI_NUM_DISTANCE_SYMBOLS
, self
->cost_dist_
);
153 for (i
= 0; i
< BROTLI_NUM_COMMAND_SYMBOLS
; ++i
) {
154 min_cost_cmd
= BROTLI_MIN(float, min_cost_cmd
, cost_cmd
[i
]);
156 self
->min_cost_cmd_
= min_cost_cmd
;
159 float* literal_costs
= self
->literal_costs_
;
160 size_t num_bytes
= self
->num_bytes_
;
161 literal_costs
[0] = 0.0;
162 for (i
= 0; i
< num_bytes
; ++i
) {
163 literal_costs
[i
+ 1] = literal_costs
[i
] +
164 cost_literal
[ringbuffer
[(position
+ i
) & ringbuffer_mask
]];
169 static void ZopfliCostModelSetFromLiteralCosts(ZopfliCostModel
* self
,
171 const uint8_t* ringbuffer
,
172 size_t ringbuffer_mask
) {
173 float* literal_costs
= self
->literal_costs_
;
174 float* cost_dist
= self
->cost_dist_
;
175 float* cost_cmd
= self
->cost_cmd_
;
176 size_t num_bytes
= self
->num_bytes_
;
178 BrotliEstimateBitCostsForLiterals(position
, num_bytes
, ringbuffer_mask
,
179 ringbuffer
, &literal_costs
[1]);
180 literal_costs
[0] = 0.0;
181 for (i
= 0; i
< num_bytes
; ++i
) {
182 literal_costs
[i
+ 1] += literal_costs
[i
];
184 for (i
= 0; i
< BROTLI_NUM_COMMAND_SYMBOLS
; ++i
) {
185 cost_cmd
[i
] = (float)FastLog2(11 + (uint32_t)i
);
187 for (i
= 0; i
< BROTLI_NUM_DISTANCE_SYMBOLS
; ++i
) {
188 cost_dist
[i
] = (float)FastLog2(20 + (uint32_t)i
);
190 self
->min_cost_cmd_
= (float)FastLog2(11);
193 static BROTLI_INLINE
float ZopfliCostModelGetCommandCost(
194 const ZopfliCostModel
* self
, uint16_t cmdcode
) {
195 return self
->cost_cmd_
[cmdcode
];
198 static BROTLI_INLINE
float ZopfliCostModelGetDistanceCost(
199 const ZopfliCostModel
* self
, size_t distcode
) {
200 return self
->cost_dist_
[distcode
];
203 static BROTLI_INLINE
float ZopfliCostModelGetLiteralCosts(
204 const ZopfliCostModel
* self
, size_t from
, size_t to
) {
205 return self
->literal_costs_
[to
] - self
->literal_costs_
[from
];
208 static BROTLI_INLINE
float ZopfliCostModelGetMinCostCmd(
209 const ZopfliCostModel
* self
) {
210 return self
->min_cost_cmd_
;
213 static BROTLI_INLINE
size_t ComputeDistanceCode(size_t distance
,
215 const int* dist_cache
) {
216 if (distance
<= max_distance
) {
217 size_t distance_plus_3
= distance
+ 3;
218 size_t offset0
= distance_plus_3
- (size_t)dist_cache
[0];
219 size_t offset1
= distance_plus_3
- (size_t)dist_cache
[1];
220 if (distance
== (size_t)dist_cache
[0]) {
222 } else if (distance
== (size_t)dist_cache
[1]) {
224 } else if (offset0
< 7) {
225 return (0x9750468 >> (4 * offset0
)) & 0xF;
226 } else if (offset1
< 7) {
227 return (0xFDB1ACE >> (4 * offset1
)) & 0xF;
228 } else if (distance
== (size_t)dist_cache
[2]) {
230 } else if (distance
== (size_t)dist_cache
[3]) {
234 return distance
+ 15;
237 /* REQUIRES: len >= 2, start_pos <= pos */
238 /* REQUIRES: cost < kInfinity, nodes[start_pos].cost < kInfinity */
239 /* Maintains the "ZopfliNode array invariant". */
240 static BROTLI_INLINE
void UpdateZopfliNode(ZopfliNode
* nodes
, size_t pos
,
241 size_t start_pos
, size_t len
, size_t len_code
, size_t dist
,
242 size_t short_code
, float cost
) {
243 ZopfliNode
* next
= &nodes
[pos
+ len
];
244 next
->length
= (uint32_t)(len
| ((len
+ 9u - len_code
) << 24));
245 next
->distance
= (uint32_t)(dist
| (short_code
<< 25));
246 next
->insert_length
= (uint32_t)(pos
- start_pos
);
250 typedef struct PosData
{
252 int distance_cache
[4];
257 /* Maintains the smallest 8 cost difference together with their positions */
258 typedef struct StartPosQueue
{
263 static BROTLI_INLINE
void InitStartPosQueue(StartPosQueue
* self
) {
267 static size_t StartPosQueueSize(const StartPosQueue
* self
) {
268 return BROTLI_MIN(size_t, self
->idx_
, 8);
271 static void StartPosQueuePush(StartPosQueue
* self
, const PosData
* posdata
) {
272 size_t offset
= ~(self
->idx_
++) & 7;
273 size_t len
= StartPosQueueSize(self
);
275 PosData
* q
= self
->q_
;
276 q
[offset
] = *posdata
;
277 /* Restore the sorted order. In the list of |len| items at most |len - 1|
278 adjacent element comparisons / swaps are required. */
279 for (i
= 1; i
< len
; ++i
) {
280 if (q
[offset
& 7].costdiff
> q
[(offset
+ 1) & 7].costdiff
) {
281 BROTLI_SWAP(PosData
, q
, offset
& 7, (offset
+ 1) & 7);
287 static const PosData
* StartPosQueueAt(const StartPosQueue
* self
, size_t k
) {
288 return &self
->q_
[(k
- self
->idx_
) & 7];
291 /* Returns the minimum possible copy length that can improve the cost of any */
292 /* future position. */
293 static size_t ComputeMinimumCopyLength(const float start_cost
,
294 const ZopfliNode
* nodes
,
295 const size_t num_bytes
,
297 /* Compute the minimum possible cost of reaching any future position. */
298 float min_cost
= start_cost
;
300 size_t next_len_bucket
= 4;
301 size_t next_len_offset
= 10;
302 while (pos
+ len
<= num_bytes
&& nodes
[pos
+ len
].u
.cost
<= min_cost
) {
303 /* We already reached (pos + len) with no more cost than the minimum
304 possible cost of reaching anything from this pos, so there is no point in
305 looking for lengths <= len. */
307 if (len
== next_len_offset
) {
308 /* We reached the next copy length code bucket, so we add one more
309 extra bit to the minimum cost. */
311 next_len_offset
+= next_len_bucket
;
312 next_len_bucket
*= 2;
318 /* REQUIRES: nodes[pos].cost < kInfinity
319 REQUIRES: nodes[0..pos] satisfies that "ZopfliNode array invariant". */
320 static uint32_t ComputeDistanceShortcut(const size_t block_start
,
322 const size_t max_backward
,
323 const ZopfliNode
* nodes
) {
324 const size_t clen
= ZopfliNodeCopyLength(&nodes
[pos
]);
325 const size_t ilen
= nodes
[pos
].insert_length
;
326 const size_t dist
= ZopfliNodeCopyDistance(&nodes
[pos
]);
327 /* Since |block_start + pos| is the end position of the command, the copy part
328 starts from |block_start + pos - clen|. Distances that are greater than
329 this or greater than |max_backward| are static dictionary references, and
330 do not update the last distances. Also distance code 0 (last distance)
331 does not update the last distances. */
334 } else if (dist
+ clen
<= block_start
+ pos
&&
335 dist
<= max_backward
&&
336 ZopfliNodeDistanceCode(&nodes
[pos
]) > 0) {
337 return (uint32_t)pos
;
339 return nodes
[pos
- clen
- ilen
].u
.shortcut
;
343 /* Fills in dist_cache[0..3] with the last four distances (as defined by
344 Section 4. of the Spec) that would be used at (block_start + pos) if we
345 used the shortest path of commands from block_start, computed from
346 nodes[0..pos]. The last four distances at block_start are in
347 starting_dist_cach[0..3].
348 REQUIRES: nodes[pos].cost < kInfinity
349 REQUIRES: nodes[0..pos] satisfies that "ZopfliNode array invariant". */
350 static void ComputeDistanceCache(const size_t pos
,
351 const int* starting_dist_cache
,
352 const ZopfliNode
* nodes
,
355 size_t p
= nodes
[pos
].u
.shortcut
;
356 while (idx
< 4 && p
> 0) {
357 const size_t ilen
= nodes
[p
].insert_length
;
358 const size_t clen
= ZopfliNodeCopyLength(&nodes
[p
]);
359 const size_t dist
= ZopfliNodeCopyDistance(&nodes
[p
]);
360 dist_cache
[idx
++] = (int)dist
;
361 /* Because of prerequisite, p >= clen + ilen >= 2. */
362 p
= nodes
[p
- clen
- ilen
].u
.shortcut
;
364 for (; idx
< 4; ++idx
) {
365 dist_cache
[idx
] = *starting_dist_cache
++;
369 static void UpdateNodes(const size_t num_bytes
,
370 const size_t block_start
,
372 const uint8_t* ringbuffer
,
373 const size_t ringbuffer_mask
,
374 const BrotliEncoderParams
* params
,
375 const size_t max_backward_limit
,
376 const int* starting_dist_cache
,
377 const size_t num_matches
,
378 const BackwardMatch
* matches
,
379 const ZopfliCostModel
* model
,
380 StartPosQueue
* queue
,
382 const size_t cur_ix
= block_start
+ pos
;
383 const size_t cur_ix_masked
= cur_ix
& ringbuffer_mask
;
384 const size_t max_distance
= BROTLI_MIN(size_t, cur_ix
, max_backward_limit
);
385 const size_t max_len
= num_bytes
- pos
;
386 const size_t max_zopfli_len
= MaxZopfliLen(params
);
387 const size_t max_iters
= MaxZopfliCandidates(params
);
392 /* Save cost, because ComputeDistanceCache invalidates it. */
393 float node_cost
= nodes
[pos
].u
.cost
;
394 nodes
[pos
].u
.shortcut
= ComputeDistanceShortcut(
395 block_start
, pos
, max_backward_limit
, nodes
);
396 if (node_cost
<= ZopfliCostModelGetLiteralCosts(model
, 0, pos
)) {
399 posdata
.cost
= node_cost
;
400 posdata
.costdiff
= node_cost
-
401 ZopfliCostModelGetLiteralCosts(model
, 0, pos
);
402 ComputeDistanceCache(
403 pos
, starting_dist_cache
, nodes
, posdata
.distance_cache
);
404 StartPosQueuePush(queue
, &posdata
);
409 const PosData
* posdata
= StartPosQueueAt(queue
, 0);
410 float min_cost
= (posdata
->cost
+ ZopfliCostModelGetMinCostCmd(model
) +
411 ZopfliCostModelGetLiteralCosts(model
, posdata
->pos
, pos
));
412 min_len
= ComputeMinimumCopyLength(min_cost
, nodes
, num_bytes
, pos
);
415 /* Go over the command starting positions in order of increasing cost
417 for (k
= 0; k
< max_iters
&& k
< StartPosQueueSize(queue
); ++k
) {
418 const PosData
* posdata
= StartPosQueueAt(queue
, k
);
419 const size_t start
= posdata
->pos
;
420 const uint16_t inscode
= GetInsertLengthCode(pos
- start
);
421 const float start_costdiff
= posdata
->costdiff
;
422 const float base_cost
= start_costdiff
+ (float)GetInsertExtra(inscode
) +
423 ZopfliCostModelGetLiteralCosts(model
, 0, pos
);
425 /* Look for last distance matches using the distance cache from this
426 starting position. */
427 size_t best_len
= min_len
- 1;
429 for (; j
< BROTLI_NUM_DISTANCE_SHORT_CODES
&& best_len
< max_len
; ++j
) {
430 const size_t idx
= kDistanceCacheIndex
[j
];
431 const size_t backward
=
432 (size_t)(posdata
->distance_cache
[idx
] + kDistanceCacheOffset
[j
]);
433 size_t prev_ix
= cur_ix
- backward
;
434 if (prev_ix
>= cur_ix
) {
437 if (PREDICT_FALSE(backward
> max_distance
)) {
440 prev_ix
&= ringbuffer_mask
;
442 if (cur_ix_masked
+ best_len
> ringbuffer_mask
||
443 prev_ix
+ best_len
> ringbuffer_mask
||
444 ringbuffer
[cur_ix_masked
+ best_len
] !=
445 ringbuffer
[prev_ix
+ best_len
]) {
450 FindMatchLengthWithLimit(&ringbuffer
[prev_ix
],
451 &ringbuffer
[cur_ix_masked
],
453 const float dist_cost
= base_cost
+
454 ZopfliCostModelGetDistanceCost(model
, j
);
456 for (l
= best_len
+ 1; l
<= len
; ++l
) {
457 const uint16_t copycode
= GetCopyLengthCode(l
);
458 const uint16_t cmdcode
=
459 CombineLengthCodes(inscode
, copycode
, j
== 0);
460 const float cost
= (cmdcode
< 128 ? base_cost
: dist_cost
) +
461 (float)GetCopyExtra(copycode
) +
462 ZopfliCostModelGetCommandCost(model
, cmdcode
);
463 if (cost
< nodes
[pos
+ l
].u
.cost
) {
464 UpdateZopfliNode(nodes
, pos
, start
, l
, l
, backward
, j
+ 1, cost
);
471 /* At higher iterations look only for new last distance matches, since
472 looking only for new command start positions with the same distances
473 does not help much. */
474 if (k
>= 2) continue;
477 /* Loop through all possible copy lengths at this position. */
478 size_t len
= min_len
;
479 for (j
= 0; j
< num_matches
; ++j
) {
480 BackwardMatch match
= matches
[j
];
481 size_t dist
= match
.distance
;
482 BROTLI_BOOL is_dictionary_match
= TO_BROTLI_BOOL(dist
> max_distance
);
483 /* We already tried all possible last distance matches, so we can use
484 normal distance code here. */
485 size_t dist_code
= dist
+ 15;
486 uint16_t dist_symbol
;
488 uint32_t distnumextra
;
490 size_t max_match_len
;
491 PrefixEncodeCopyDistance(dist_code
, 0, 0, &dist_symbol
, &distextra
);
492 distnumextra
= distextra
>> 24;
493 dist_cost
= base_cost
+ (float)distnumextra
+
494 ZopfliCostModelGetDistanceCost(model
, dist_symbol
);
496 /* Try all copy lengths up until the maximum copy length corresponding
497 to this distance. If the distance refers to the static dictionary, or
498 the maximum length is long enough, try only one maximum length. */
499 max_match_len
= BackwardMatchLength(&match
);
500 if (len
< max_match_len
&&
501 (is_dictionary_match
|| max_match_len
> max_zopfli_len
)) {
504 for (; len
<= max_match_len
; ++len
) {
505 const size_t len_code
=
506 is_dictionary_match
? BackwardMatchLengthCode(&match
) : len
;
507 const uint16_t copycode
= GetCopyLengthCode(len_code
);
508 const uint16_t cmdcode
= CombineLengthCodes(inscode
, copycode
, 0);
509 const float cost
= dist_cost
+ (float)GetCopyExtra(copycode
) +
510 ZopfliCostModelGetCommandCost(model
, cmdcode
);
511 if (cost
< nodes
[pos
+ len
].u
.cost
) {
512 UpdateZopfliNode(nodes
, pos
, start
, len
, len_code
, dist
, 0, cost
);
520 static size_t ComputeShortestPathFromNodes(size_t num_bytes
,
522 size_t index
= num_bytes
;
523 size_t num_commands
= 0;
524 while (nodes
[index
].insert_length
== 0 && nodes
[index
].length
== 1) --index
;
525 nodes
[index
].u
.next
= BROTLI_UINT32_MAX
;
527 size_t len
= ZopfliNodeCommandLength(&nodes
[index
]);
529 nodes
[index
].u
.next
= (uint32_t)len
;
535 void BrotliZopfliCreateCommands(const size_t num_bytes
,
536 const size_t block_start
,
537 const size_t max_backward_limit
,
538 const ZopfliNode
* nodes
,
540 size_t* last_insert_len
,
542 size_t* num_literals
) {
544 uint32_t offset
= nodes
[0].u
.next
;
546 for (i
= 0; offset
!= BROTLI_UINT32_MAX
; i
++) {
547 const ZopfliNode
* next
= &nodes
[pos
+ offset
];
548 size_t copy_length
= ZopfliNodeCopyLength(next
);
549 size_t insert_length
= next
->insert_length
;
550 pos
+= insert_length
;
551 offset
= next
->u
.next
;
553 insert_length
+= *last_insert_len
;
554 *last_insert_len
= 0;
557 size_t distance
= ZopfliNodeCopyDistance(next
);
558 size_t len_code
= ZopfliNodeLengthCode(next
);
559 size_t max_distance
=
560 BROTLI_MIN(size_t, block_start
+ pos
, max_backward_limit
);
561 BROTLI_BOOL is_dictionary
= TO_BROTLI_BOOL(distance
> max_distance
);
562 size_t dist_code
= ZopfliNodeDistanceCode(next
);
565 &commands
[i
], insert_length
, copy_length
, len_code
, dist_code
);
567 if (!is_dictionary
&& dist_code
> 0) {
568 dist_cache
[3] = dist_cache
[2];
569 dist_cache
[2] = dist_cache
[1];
570 dist_cache
[1] = dist_cache
[0];
571 dist_cache
[0] = (int)distance
;
575 *num_literals
+= insert_length
;
578 *last_insert_len
+= num_bytes
- pos
;
581 static size_t ZopfliIterate(size_t num_bytes
,
583 const uint8_t* ringbuffer
,
584 size_t ringbuffer_mask
,
585 const BrotliEncoderParams
* params
,
586 const size_t max_backward_limit
,
587 const int* dist_cache
,
588 const ZopfliCostModel
* model
,
589 const uint32_t* num_matches
,
590 const BackwardMatch
* matches
,
592 const size_t max_zopfli_len
= MaxZopfliLen(params
);
594 size_t cur_match_pos
= 0;
598 InitStartPosQueue(&queue
);
599 for (i
= 0; i
+ 3 < num_bytes
; i
++) {
600 UpdateNodes(num_bytes
, position
, i
, ringbuffer
, ringbuffer_mask
,
601 params
, max_backward_limit
, dist_cache
, num_matches
[i
],
602 &matches
[cur_match_pos
], model
, &queue
, nodes
);
603 cur_match_pos
+= num_matches
[i
];
604 /* The zopflification can be too slow in case of very long lengths, so in
605 such case skip it all, it does not cost a lot of compression ratio. */
606 if (num_matches
[i
] == 1 &&
607 BackwardMatchLength(&matches
[cur_match_pos
- 1]) > max_zopfli_len
) {
608 i
+= BackwardMatchLength(&matches
[cur_match_pos
- 1]) - 1;
609 InitStartPosQueue(&queue
);
612 return ComputeShortestPathFromNodes(num_bytes
, nodes
);
616 size_t BrotliZopfliComputeShortestPath(MemoryManager
* m
,
619 const uint8_t* ringbuffer
,
620 size_t ringbuffer_mask
,
621 const BrotliEncoderParams
* params
,
622 const size_t max_backward_limit
,
623 const int* dist_cache
,
626 const size_t max_zopfli_len
= MaxZopfliLen(params
);
627 ZopfliCostModel model
;
629 BackwardMatch matches
[MAX_NUM_MATCHES_H10
];
630 const size_t store_end
= num_bytes
>= StoreLookaheadH10() ?
631 position
+ num_bytes
- StoreLookaheadH10() + 1 : position
;
635 InitZopfliCostModel(m
, &model
, num_bytes
);
636 if (BROTLI_IS_OOM(m
)) return 0;
637 ZopfliCostModelSetFromLiteralCosts(
638 &model
, position
, ringbuffer
, ringbuffer_mask
);
639 InitStartPosQueue(&queue
);
640 for (i
= 0; i
+ HashTypeLengthH10() - 1 < num_bytes
; i
++) {
641 const size_t pos
= position
+ i
;
642 const size_t max_distance
= BROTLI_MIN(size_t, pos
, max_backward_limit
);
643 size_t num_matches
= FindAllMatchesH10(hasher
, ringbuffer
, ringbuffer_mask
,
644 pos
, num_bytes
- i
, max_distance
, params
, matches
);
645 if (num_matches
> 0 &&
646 BackwardMatchLength(&matches
[num_matches
- 1]) > max_zopfli_len
) {
647 matches
[0] = matches
[num_matches
- 1];
650 UpdateNodes(num_bytes
, position
, i
, ringbuffer
, ringbuffer_mask
,
651 params
, max_backward_limit
, dist_cache
, num_matches
, matches
,
652 &model
, &queue
, nodes
);
653 if (num_matches
== 1 && BackwardMatchLength(&matches
[0]) > max_zopfli_len
) {
654 /* Add the tail of the copy to the hasher. */
655 StoreRangeH10(hasher
, ringbuffer
, ringbuffer_mask
, pos
+ 1, BROTLI_MIN(
656 size_t, pos
+ BackwardMatchLength(&matches
[0]), store_end
));
657 i
+= BackwardMatchLength(&matches
[0]) - 1;
658 InitStartPosQueue(&queue
);
661 CleanupZopfliCostModel(m
, &model
);
662 return ComputeShortestPathFromNodes(num_bytes
, nodes
);
665 #define EXPAND_CAT(a, b) CAT(a, b)
666 #define CAT(a, b) a ## b
667 #define FN(X) EXPAND_CAT(X, HASHER())
670 /* NOLINTNEXTLINE(build/include) */
671 #include "./backward_references_inc.h"
675 /* NOLINTNEXTLINE(build/include) */
676 #include "./backward_references_inc.h"
680 /* NOLINTNEXTLINE(build/include) */
681 #include "./backward_references_inc.h"
685 /* NOLINTNEXTLINE(build/include) */
686 #include "./backward_references_inc.h"
690 /* NOLINTNEXTLINE(build/include) */
691 #include "./backward_references_inc.h"
695 /* NOLINTNEXTLINE(build/include) */
696 #include "./backward_references_inc.h"
700 /* NOLINTNEXTLINE(build/include) */
701 #include "./backward_references_inc.h"
705 /* NOLINTNEXTLINE(build/include) */
706 #include "./backward_references_inc.h"
710 /* NOLINTNEXTLINE(build/include) */
711 #include "./backward_references_inc.h"
715 /* NOLINTNEXTLINE(build/include) */
716 #include "./backward_references_inc.h"
720 /* NOLINTNEXTLINE(build/include) */
721 #include "./backward_references_inc.h"
728 static BROTLI_NOINLINE
void CreateZopfliBackwardReferences(
729 MemoryManager
* m
, size_t num_bytes
, size_t position
, BROTLI_BOOL is_last
,
730 const uint8_t* ringbuffer
, size_t ringbuffer_mask
,
731 const BrotliEncoderParams
* params
, H10
* hasher
, int* dist_cache
,
732 size_t* last_insert_len
, Command
* commands
, size_t* num_commands
,
733 size_t* num_literals
) {
734 const size_t max_backward_limit
= MaxBackwardLimit(params
->lgwin
);
736 InitH10(m
, hasher
, ringbuffer
, params
, position
, num_bytes
, is_last
);
737 if (BROTLI_IS_OOM(m
)) return;
738 StitchToPreviousBlockH10(hasher
, num_bytes
, position
,
739 ringbuffer
, ringbuffer_mask
);
740 nodes
= BROTLI_ALLOC(m
, ZopfliNode
, num_bytes
+ 1);
741 if (BROTLI_IS_OOM(m
)) return;
742 BrotliInitZopfliNodes(nodes
, num_bytes
+ 1);
743 *num_commands
+= BrotliZopfliComputeShortestPath(m
, num_bytes
, position
,
744 ringbuffer
, ringbuffer_mask
, params
, max_backward_limit
,
745 dist_cache
, hasher
, nodes
);
746 if (BROTLI_IS_OOM(m
)) return;
747 BrotliZopfliCreateCommands(num_bytes
, position
, max_backward_limit
, nodes
,
748 dist_cache
, last_insert_len
, commands
, num_literals
);
749 BROTLI_FREE(m
, nodes
);
752 static BROTLI_NOINLINE
void CreateHqZopfliBackwardReferences(
753 MemoryManager
* m
, size_t num_bytes
, size_t position
, BROTLI_BOOL is_last
,
754 const uint8_t* ringbuffer
, size_t ringbuffer_mask
,
755 const BrotliEncoderParams
* params
, H10
* hasher
, int* dist_cache
,
756 size_t* last_insert_len
, Command
* commands
, size_t* num_commands
,
757 size_t* num_literals
) {
758 const size_t max_backward_limit
= MaxBackwardLimit(params
->lgwin
);
759 uint32_t* num_matches
= BROTLI_ALLOC(m
, uint32_t, num_bytes
);
760 size_t matches_size
= 4 * num_bytes
;
761 const size_t store_end
= num_bytes
>= StoreLookaheadH10() ?
762 position
+ num_bytes
- StoreLookaheadH10() + 1 : position
;
763 size_t cur_match_pos
= 0;
765 size_t orig_num_literals
;
766 size_t orig_last_insert_len
;
767 int orig_dist_cache
[4];
768 size_t orig_num_commands
;
769 ZopfliCostModel model
;
771 BackwardMatch
* matches
= BROTLI_ALLOC(m
, BackwardMatch
, matches_size
);
772 if (BROTLI_IS_OOM(m
)) return;
773 InitH10(m
, hasher
, ringbuffer
, params
, position
, num_bytes
, is_last
);
774 if (BROTLI_IS_OOM(m
)) return;
775 StitchToPreviousBlockH10(hasher
, num_bytes
, position
,
776 ringbuffer
, ringbuffer_mask
);
777 for (i
= 0; i
+ HashTypeLengthH10() - 1 < num_bytes
; ++i
) {
778 const size_t pos
= position
+ i
;
779 size_t max_distance
= BROTLI_MIN(size_t, pos
, max_backward_limit
);
780 size_t max_length
= num_bytes
- i
;
781 size_t num_found_matches
;
782 size_t cur_match_end
;
784 /* Ensure that we have enough free slots. */
785 BROTLI_ENSURE_CAPACITY(m
, BackwardMatch
, matches
, matches_size
,
786 cur_match_pos
+ MAX_NUM_MATCHES_H10
);
787 if (BROTLI_IS_OOM(m
)) return;
788 num_found_matches
= FindAllMatchesH10(hasher
, ringbuffer
, ringbuffer_mask
,
789 pos
, max_length
, max_distance
, params
, &matches
[cur_match_pos
]);
790 cur_match_end
= cur_match_pos
+ num_found_matches
;
791 for (j
= cur_match_pos
; j
+ 1 < cur_match_end
; ++j
) {
792 assert(BackwardMatchLength(&matches
[j
]) <
793 BackwardMatchLength(&matches
[j
+ 1]));
794 assert(matches
[j
].distance
> max_distance
||
795 matches
[j
].distance
<= matches
[j
+ 1].distance
);
797 num_matches
[i
] = (uint32_t)num_found_matches
;
798 if (num_found_matches
> 0) {
799 const size_t match_len
= BackwardMatchLength(&matches
[cur_match_end
- 1]);
800 if (match_len
> MAX_ZOPFLI_LEN_QUALITY_11
) {
801 const size_t skip
= match_len
- 1;
802 matches
[cur_match_pos
++] = matches
[cur_match_end
- 1];
804 /* Add the tail of the copy to the hasher. */
805 StoreRangeH10(hasher
, ringbuffer
, ringbuffer_mask
, pos
+ 1,
806 BROTLI_MIN(size_t, pos
+ match_len
, store_end
));
807 memset(&num_matches
[i
+ 1], 0, skip
* sizeof(num_matches
[0]));
810 cur_match_pos
= cur_match_end
;
814 orig_num_literals
= *num_literals
;
815 orig_last_insert_len
= *last_insert_len
;
816 memcpy(orig_dist_cache
, dist_cache
, 4 * sizeof(dist_cache
[0]));
817 orig_num_commands
= *num_commands
;
818 nodes
= BROTLI_ALLOC(m
, ZopfliNode
, num_bytes
+ 1);
819 if (BROTLI_IS_OOM(m
)) return;
820 InitZopfliCostModel(m
, &model
, num_bytes
);
821 if (BROTLI_IS_OOM(m
)) return;
822 for (i
= 0; i
< 2; i
++) {
823 BrotliInitZopfliNodes(nodes
, num_bytes
+ 1);
825 ZopfliCostModelSetFromLiteralCosts(
826 &model
, position
, ringbuffer
, ringbuffer_mask
);
828 ZopfliCostModelSetFromCommands(&model
, position
, ringbuffer
,
829 ringbuffer_mask
, commands
, *num_commands
- orig_num_commands
,
830 orig_last_insert_len
);
832 *num_commands
= orig_num_commands
;
833 *num_literals
= orig_num_literals
;
834 *last_insert_len
= orig_last_insert_len
;
835 memcpy(dist_cache
, orig_dist_cache
, 4 * sizeof(dist_cache
[0]));
836 *num_commands
+= ZopfliIterate(num_bytes
, position
, ringbuffer
,
837 ringbuffer_mask
, params
, max_backward_limit
, dist_cache
,
838 &model
, num_matches
, matches
, nodes
);
839 BrotliZopfliCreateCommands(num_bytes
, position
, max_backward_limit
,
840 nodes
, dist_cache
, last_insert_len
, commands
, num_literals
);
842 CleanupZopfliCostModel(m
, &model
);
843 BROTLI_FREE(m
, nodes
);
844 BROTLI_FREE(m
, matches
);
845 BROTLI_FREE(m
, num_matches
);
848 void BrotliCreateBackwardReferences(MemoryManager
* m
,
852 const uint8_t* ringbuffer
,
853 size_t ringbuffer_mask
,
854 const BrotliEncoderParams
* params
,
857 size_t* last_insert_len
,
859 size_t* num_commands
,
860 size_t* num_literals
) {
861 if (params
->quality
== ZOPFLIFICATION_QUALITY
) {
862 CreateZopfliBackwardReferences(
863 m
, num_bytes
, position
, is_last
, ringbuffer
, ringbuffer_mask
,
864 params
, hashers
->h10
, dist_cache
,
865 last_insert_len
, commands
, num_commands
, num_literals
);
867 } else if (params
->quality
== HQ_ZOPFLIFICATION_QUALITY
) {
868 CreateHqZopfliBackwardReferences(
869 m
, num_bytes
, position
, is_last
, ringbuffer
, ringbuffer_mask
,
870 params
, hashers
->h10
, dist_cache
,
871 last_insert_len
, commands
, num_commands
, num_literals
);
875 switch (ChooseHasher(params
)) {
878 CreateBackwardReferencesH ## N(m, num_bytes, position, is_last, \
879 ringbuffer, ringbuffer_mask, params, hashers->h ## N, dist_cache, \
880 last_insert_len, commands, num_commands, num_literals); \
882 FOR_GENERIC_HASHERS(_CASE
)
887 if (BROTLI_IS_OOM(m
)) return;
890 #if defined(__cplusplus) || defined(c_plusplus)