Mercurial > hgrepos > Python2 > PyMuPDF

comparison mupdf-source/thirdparty/brotli/c/enc/backward_references_hq.c @ 2:b50eed0cc0ef upstream

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