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