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 size_t gap,
304                                        const ZopfliNode* nodes) {
305  const size_t clen = ZopfliNodeCopyLength(&nodes[pos]);
306  const size_t ilen = nodes[pos].insert_length;
307  const size_t dist = ZopfliNodeCopyDistance(&nodes[pos]);
308  /* Since |block_start + pos| is the end position of the command, the copy part
309     starts from |block_start + pos - clen|. Distances that are greater than
310     this or greater than |max_backward| are static dictionary references, and
311     do not update the last distances. Also distance code 0 (last distance)
312     does not update the last distances. */
313  if (pos == 0) {
314    return 0;
315  } else if (dist + clen <= block_start + pos + gap &&
316             dist <= max_backward + gap &&
317             ZopfliNodeDistanceCode(&nodes[pos]) > 0) {
318    return (uint32_t)pos;
319  } else {
320    return nodes[pos - clen - ilen].u.shortcut;
321  }
322}
323
324/* Fills in dist_cache[0..3] with the last four distances (as defined by
325   Section 4. of the Spec) that would be used at (block_start + pos) if we
326   used the shortest path of commands from block_start, computed from
327   nodes[0..pos]. The last four distances at block_start are in
328   starting_dist_cache[0..3].
329   REQUIRES: nodes[pos].cost < kInfinity
330   REQUIRES: nodes[0..pos] satisfies that "ZopfliNode array invariant". */
331static void ComputeDistanceCache(const size_t pos,
332                                 const int* starting_dist_cache,
333                                 const ZopfliNode* nodes,
334                                 int* dist_cache) {
335  int idx = 0;
336  size_t p = nodes[pos].u.shortcut;
337  while (idx < 4 && p > 0) {
338    const size_t ilen = nodes[p].insert_length;
339    const size_t clen = ZopfliNodeCopyLength(&nodes[p]);
340    const size_t dist = ZopfliNodeCopyDistance(&nodes[p]);
341    dist_cache[idx++] = (int)dist;
342    /* Because of prerequisite, p >= clen + ilen >= 2. */
343    p = nodes[p - clen - ilen].u.shortcut;
344  }
345  for (; idx < 4; ++idx) {
346    dist_cache[idx] = *starting_dist_cache++;
347  }
348}
349
350/* Maintains "ZopfliNode array invariant" and pushes node to the queue, if it
351   is eligible. */
352static void EvaluateNode(
353    const size_t block_start, const size_t pos, const size_t max_backward_limit,
354    const size_t gap, const int* starting_dist_cache,
355    const ZopfliCostModel* model, StartPosQueue* queue, ZopfliNode* nodes) {
356  /* Save cost, because ComputeDistanceCache invalidates it. */
357  float node_cost = nodes[pos].u.cost;
358  nodes[pos].u.shortcut = ComputeDistanceShortcut(
359      block_start, pos, max_backward_limit, gap, nodes);
360  if (node_cost <= ZopfliCostModelGetLiteralCosts(model, 0, pos)) {
361    PosData posdata;
362    posdata.pos = pos;
363    posdata.cost = node_cost;
364    posdata.costdiff = node_cost -
365        ZopfliCostModelGetLiteralCosts(model, 0, pos);
366    ComputeDistanceCache(
367        pos, starting_dist_cache, nodes, posdata.distance_cache);
368    StartPosQueuePush(queue, &posdata);
369  }
370}
371
372/* Returns longest copy length. */
373static size_t UpdateNodes(
374    const size_t num_bytes, const size_t block_start, const size_t pos,
375    const uint8_t* ringbuffer, const size_t ringbuffer_mask,
376    const BrotliEncoderParams* params, const size_t max_backward_limit,
377    const int* starting_dist_cache, const size_t num_matches,
378    const BackwardMatch* matches, const ZopfliCostModel* model,
379    StartPosQueue* queue, ZopfliNode* nodes) {
380  const size_t cur_ix = block_start + pos;
381  const size_t cur_ix_masked = cur_ix & ringbuffer_mask;
382  const size_t max_distance = BROTLI_MIN(size_t, cur_ix, max_backward_limit);
383  const size_t max_len = num_bytes - pos;
384  const size_t max_zopfli_len = MaxZopfliLen(params);
385  const size_t max_iters = MaxZopfliCandidates(params);
386  size_t min_len;
387  size_t result = 0;
388  size_t k;
389  size_t gap = 0;
390
391  EvaluateNode(block_start, pos, max_backward_limit, gap, starting_dist_cache,
392      model, queue, nodes);
393
394  {
395    const PosData* posdata = StartPosQueueAt(queue, 0);
396    float min_cost = (posdata->cost + ZopfliCostModelGetMinCostCmd(model) +
397        ZopfliCostModelGetLiteralCosts(model, posdata->pos, pos));
398    min_len = ComputeMinimumCopyLength(min_cost, nodes, num_bytes, pos);
399  }
400
401  /* Go over the command starting positions in order of increasing cost
402     difference. */
403  for (k = 0; k < max_iters && k < StartPosQueueSize(queue); ++k) {
404    const PosData* posdata = StartPosQueueAt(queue, k);
405    const size_t start = posdata->pos;
406    const uint16_t inscode = GetInsertLengthCode(pos - start);
407    const float start_costdiff = posdata->costdiff;
408    const float base_cost = start_costdiff + (float)GetInsertExtra(inscode) +
409        ZopfliCostModelGetLiteralCosts(model, 0, pos);
410
411    /* Look for last distance matches using the distance cache from this
412       starting position. */
413    size_t best_len = min_len - 1;
414    size_t j = 0;
415    for (; j < BROTLI_NUM_DISTANCE_SHORT_CODES && best_len < max_len; ++j) {
416      const size_t idx = kDistanceCacheIndex[j];
417      const size_t backward =
418          (size_t)(posdata->distance_cache[idx] + kDistanceCacheOffset[j]);
419      size_t prev_ix = cur_ix - backward;
420      size_t len = 0;
421      uint8_t continuation = ringbuffer[cur_ix_masked + best_len];
422      if (cur_ix_masked + best_len > ringbuffer_mask) {
423        break;
424      }
425      if (BROTLI_PREDICT_FALSE(backward > max_distance + gap)) {
426        continue;
427      }
428      if (backward <= max_distance) {
429        if (prev_ix >= cur_ix) {
430          continue;
431        }
432
433        prev_ix &= ringbuffer_mask;
434        if (prev_ix + best_len > ringbuffer_mask ||
435            continuation != ringbuffer[prev_ix + best_len]) {
436          continue;
437        }
438        len = FindMatchLengthWithLimit(&ringbuffer[prev_ix],
439                                       &ringbuffer[cur_ix_masked],
440                                       max_len);
441      } else {
442        continue;
443      }
444      {
445        const float dist_cost = base_cost +
446            ZopfliCostModelGetDistanceCost(model, j);
447        size_t l;
448        for (l = best_len + 1; l <= len; ++l) {
449          const uint16_t copycode = GetCopyLengthCode(l);
450          const uint16_t cmdcode =
451              CombineLengthCodes(inscode, copycode, j == 0);
452          const float cost = (cmdcode < 128 ? base_cost : dist_cost) +
453              (float)GetCopyExtra(copycode) +
454              ZopfliCostModelGetCommandCost(model, cmdcode);
455          if (cost < nodes[pos + l].u.cost) {
456            UpdateZopfliNode(nodes, pos, start, l, l, backward, j + 1, cost);
457            result = BROTLI_MAX(size_t, result, l);
458          }
459          best_len = l;
460        }
461      }
462    }
463
464    /* At higher iterations look only for new last distance matches, since
465       looking only for new command start positions with the same distances
466       does not help much. */
467    if (k >= 2) continue;
468
469    {
470      /* Loop through all possible copy lengths at this position. */
471      size_t len = min_len;
472      for (j = 0; j < num_matches; ++j) {
473        BackwardMatch match = matches[j];
474        size_t dist = match.distance;
475        BROTLI_BOOL is_dictionary_match =
476            TO_BROTLI_BOOL(dist > max_distance + gap);
477        /* We already tried all possible last distance matches, so we can use
478           normal distance code here. */
479        size_t dist_code = dist + BROTLI_NUM_DISTANCE_SHORT_CODES - 1;
480        uint16_t dist_symbol;
481        uint32_t distextra;
482        uint32_t distnumextra;
483        float dist_cost;
484        size_t max_match_len;
485        PrefixEncodeCopyDistance(dist_code, 0, 0, &dist_symbol, &distextra);
486        distnumextra = distextra >> 24;
487        dist_cost = base_cost + (float)distnumextra +
488            ZopfliCostModelGetDistanceCost(model, dist_symbol);
489
490        /* Try all copy lengths up until the maximum copy length corresponding
491           to this distance. If the distance refers to the static dictionary, or
492           the maximum length is long enough, try only one maximum length. */
493        max_match_len = BackwardMatchLength(&match);
494        if (len < max_match_len &&
495            (is_dictionary_match || max_match_len > max_zopfli_len)) {
496          len = max_match_len;
497        }
498        for (; len <= max_match_len; ++len) {
499          const size_t len_code =
500              is_dictionary_match ? BackwardMatchLengthCode(&match) : len;
501          const uint16_t copycode = GetCopyLengthCode(len_code);
502          const uint16_t cmdcode = CombineLengthCodes(inscode, copycode, 0);
503          const float cost = dist_cost + (float)GetCopyExtra(copycode) +
504              ZopfliCostModelGetCommandCost(model, cmdcode);
505          if (cost < nodes[pos + len].u.cost) {
506            UpdateZopfliNode(nodes, pos, start, len, len_code, dist, 0, cost);
507            result = BROTLI_MAX(size_t, result, len);
508          }
509        }
510      }
511    }
512  }
513  return result;
514}
515
516static size_t ComputeShortestPathFromNodes(size_t num_bytes,
517    ZopfliNode* nodes) {
518  size_t index = num_bytes;
519  size_t num_commands = 0;
520  while (nodes[index].insert_length == 0 && nodes[index].length == 1) --index;
521  nodes[index].u.next = BROTLI_UINT32_MAX;
522  while (index != 0) {
523    size_t len = ZopfliNodeCommandLength(&nodes[index]);
524    index -= len;
525    nodes[index].u.next = (uint32_t)len;
526    num_commands++;
527  }
528  return num_commands;
529}
530
531/* REQUIRES: nodes != NULL and len(nodes) >= num_bytes + 1 */
532void BrotliZopfliCreateCommands(const size_t num_bytes,
533                                const size_t block_start,
534                                const size_t max_backward_limit,
535                                const ZopfliNode* nodes,
536                                int* dist_cache,
537                                size_t* last_insert_len,
538                                const BrotliEncoderParams* params,
539                                Command* commands,
540                                size_t* num_literals) {
541  size_t pos = 0;
542  uint32_t offset = nodes[0].u.next;
543  size_t i;
544  size_t gap = 0;
545  BROTLI_UNUSED(params);
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;
552    if (i == 0) {
553      insert_length += *last_insert_len;
554      *last_insert_len = 0;
555    }
556    {
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 + gap);
562      size_t dist_code = ZopfliNodeDistanceCode(next);
563
564      InitCommand(&commands[i], insert_length,
565          copy_length, (int)len_code - (int)copy_length, dist_code);
566
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;
572      }
573    }
574
575    *num_literals += insert_length;
576    pos += copy_length;
577  }
578  *last_insert_len += num_bytes - pos;
579}
580
581static size_t ZopfliIterate(size_t num_bytes,
582                            size_t position,
583                            const uint8_t* ringbuffer,
584                            size_t ringbuffer_mask,
585                            const BrotliEncoderParams* params,
586                            const size_t max_backward_limit,
587                            const size_t gap,
588                            const int* dist_cache,
589                            const ZopfliCostModel* model,
590                            const uint32_t* num_matches,
591                            const BackwardMatch* matches,
592                            ZopfliNode* nodes) {
593  const size_t max_zopfli_len = MaxZopfliLen(params);
594  StartPosQueue queue;
595  size_t cur_match_pos = 0;
596  size_t i;
597  nodes[0].length = 0;
598  nodes[0].u.cost = 0;
599  InitStartPosQueue(&queue);
600  for (i = 0; i + 3 < num_bytes; i++) {
601    size_t skip = UpdateNodes(num_bytes, position, i, ringbuffer,
602        ringbuffer_mask, params, max_backward_limit, dist_cache,
603        num_matches[i], &matches[cur_match_pos], model, &queue, nodes);
604    if (skip < BROTLI_LONG_COPY_QUICK_STEP) skip = 0;
605    cur_match_pos += num_matches[i];
606    if (num_matches[i] == 1 &&
607        BackwardMatchLength(&matches[cur_match_pos - 1]) > max_zopfli_len) {
608      skip = BROTLI_MAX(size_t,
609          BackwardMatchLength(&matches[cur_match_pos - 1]), skip);
610    }
611    if (skip > 1) {
612      skip--;
613      while (skip) {
614        i++;
615        if (i + 3 >= num_bytes) break;
616        EvaluateNode(position, i, max_backward_limit, gap, dist_cache, model,
617            &queue, nodes);
618        cur_match_pos += num_matches[i];
619        skip--;
620      }
621    }
622  }
623  return ComputeShortestPathFromNodes(num_bytes, nodes);
624}
625
626/* REQUIRES: nodes != NULL and len(nodes) >= num_bytes + 1 */
627size_t BrotliZopfliComputeShortestPath(MemoryManager* m,
628                                       const BrotliDictionary* dictionary,
629                                       size_t num_bytes,
630                                       size_t position,
631                                       const uint8_t* ringbuffer,
632                                       size_t ringbuffer_mask,
633                                       const BrotliEncoderParams* params,
634                                       const size_t max_backward_limit,
635                                       const int* dist_cache,
636                                       HasherHandle hasher,
637                                       ZopfliNode* nodes) {
638  const size_t max_zopfli_len = MaxZopfliLen(params);
639  ZopfliCostModel model;
640  StartPosQueue queue;
641  BackwardMatch matches[MAX_NUM_MATCHES_H10];
642  const size_t store_end = num_bytes >= StoreLookaheadH10() ?
643      position + num_bytes - StoreLookaheadH10() + 1 : position;
644  size_t i;
645  size_t gap = 0;
646  nodes[0].length = 0;
647  nodes[0].u.cost = 0;
648  InitZopfliCostModel(m, &model, num_bytes);
649  if (BROTLI_IS_OOM(m)) return 0;
650  ZopfliCostModelSetFromLiteralCosts(
651      &model, position, ringbuffer, ringbuffer_mask);
652  InitStartPosQueue(&queue);
653  for (i = 0; i + HashTypeLengthH10() - 1 < num_bytes; i++) {
654    const size_t pos = position + i;
655    const size_t max_distance = BROTLI_MIN(size_t, pos, max_backward_limit);
656    size_t num_matches = FindAllMatchesH10(hasher, dictionary, ringbuffer,
657        ringbuffer_mask, pos, num_bytes - i, max_distance, gap, params,
658        matches);
659    size_t skip;
660    if (num_matches > 0 &&
661        BackwardMatchLength(&matches[num_matches - 1]) > max_zopfli_len) {
662      matches[0] = matches[num_matches - 1];
663      num_matches = 1;
664    }
665    skip = UpdateNodes(num_bytes, position, i, ringbuffer, ringbuffer_mask,
666        params, max_backward_limit, dist_cache, num_matches, matches, &model,
667        &queue, nodes);
668    if (skip < BROTLI_LONG_COPY_QUICK_STEP) skip = 0;
669    if (num_matches == 1 && BackwardMatchLength(&matches[0]) > max_zopfli_len) {
670      skip = BROTLI_MAX(size_t, BackwardMatchLength(&matches[0]), skip);
671    }
672    if (skip > 1) {
673      /* Add the tail of the copy to the hasher. */
674      StoreRangeH10(hasher, ringbuffer, ringbuffer_mask, pos + 1, BROTLI_MIN(
675          size_t, pos + skip, store_end));
676      skip--;
677      while (skip) {
678        i++;
679        if (i + HashTypeLengthH10() - 1 >= num_bytes) break;
680        EvaluateNode(position, i, max_backward_limit, gap, dist_cache, &model,
681            &queue, nodes);
682        skip--;
683      }
684    }
685  }
686  CleanupZopfliCostModel(m, &model);
687  return ComputeShortestPathFromNodes(num_bytes, nodes);
688}
689
690void BrotliCreateZopfliBackwardReferences(
691    MemoryManager* m, const BrotliDictionary* dictionary, size_t num_bytes,
692    size_t position, const uint8_t* ringbuffer, size_t ringbuffer_mask,
693    const BrotliEncoderParams* params, HasherHandle hasher, int* dist_cache,
694    size_t* last_insert_len, Command* commands, size_t* num_commands,
695    size_t* num_literals) {
696  const size_t max_backward_limit = BROTLI_MAX_BACKWARD_LIMIT(params->lgwin);
697  ZopfliNode* nodes;
698  nodes = BROTLI_ALLOC(m, ZopfliNode, num_bytes + 1);
699  if (BROTLI_IS_OOM(m)) return;
700  BrotliInitZopfliNodes(nodes, num_bytes + 1);
701  *num_commands += BrotliZopfliComputeShortestPath(m, dictionary, num_bytes,
702      position, ringbuffer, ringbuffer_mask, params, max_backward_limit,
703      dist_cache, hasher, nodes);
704  if (BROTLI_IS_OOM(m)) return;
705  BrotliZopfliCreateCommands(num_bytes, position, max_backward_limit, nodes,
706      dist_cache, last_insert_len, params, commands, num_literals);
707  BROTLI_FREE(m, nodes);
708}
709
710void BrotliCreateHqZopfliBackwardReferences(
711    MemoryManager* m, const BrotliDictionary* dictionary, size_t num_bytes,
712    size_t position, const uint8_t* ringbuffer, size_t ringbuffer_mask,
713    const BrotliEncoderParams* params, HasherHandle hasher, int* dist_cache,
714    size_t* last_insert_len, Command* commands, size_t* num_commands,
715    size_t* num_literals) {
716  const size_t max_backward_limit = BROTLI_MAX_BACKWARD_LIMIT(params->lgwin);
717  uint32_t* num_matches = BROTLI_ALLOC(m, uint32_t, num_bytes);
718  size_t matches_size = 4 * num_bytes;
719  const size_t store_end = num_bytes >= StoreLookaheadH10() ?
720      position + num_bytes - StoreLookaheadH10() + 1 : position;
721  size_t cur_match_pos = 0;
722  size_t i;
723  size_t orig_num_literals;
724  size_t orig_last_insert_len;
725  int orig_dist_cache[4];
726  size_t orig_num_commands;
727  ZopfliCostModel model;
728  ZopfliNode* nodes;
729  BackwardMatch* matches = BROTLI_ALLOC(m, BackwardMatch, matches_size);
730  size_t gap = 0;
731  if (BROTLI_IS_OOM(m)) return;
732  for (i = 0; i + HashTypeLengthH10() - 1 < num_bytes; ++i) {
733    const size_t pos = position + i;
734    size_t max_distance = BROTLI_MIN(size_t, pos, max_backward_limit);
735    size_t max_length = num_bytes - i;
736    size_t num_found_matches;
737    size_t cur_match_end;
738    size_t j;
739    /* Ensure that we have enough free slots. */
740    BROTLI_ENSURE_CAPACITY(m, BackwardMatch, matches, matches_size,
741        cur_match_pos + MAX_NUM_MATCHES_H10);
742    if (BROTLI_IS_OOM(m)) return;
743    num_found_matches = FindAllMatchesH10(hasher, dictionary, ringbuffer,
744        ringbuffer_mask, pos, max_length, max_distance, gap, params,
745        &matches[cur_match_pos]);
746    cur_match_end = cur_match_pos + num_found_matches;
747    for (j = cur_match_pos; j + 1 < cur_match_end; ++j) {
748      assert(BackwardMatchLength(&matches[j]) <=
749          BackwardMatchLength(&matches[j + 1]));
750    }
751    num_matches[i] = (uint32_t)num_found_matches;
752    if (num_found_matches > 0) {
753      const size_t match_len = BackwardMatchLength(&matches[cur_match_end - 1]);
754      if (match_len > MAX_ZOPFLI_LEN_QUALITY_11) {
755        const size_t skip = match_len - 1;
756        matches[cur_match_pos++] = matches[cur_match_end - 1];
757        num_matches[i] = 1;
758        /* Add the tail of the copy to the hasher. */
759        StoreRangeH10(hasher, ringbuffer, ringbuffer_mask, pos + 1,
760                      BROTLI_MIN(size_t, pos + match_len, store_end));
761        memset(&num_matches[i + 1], 0, skip * sizeof(num_matches[0]));
762        i += skip;
763      } else {
764        cur_match_pos = cur_match_end;
765      }
766    }
767  }
768  orig_num_literals = *num_literals;
769  orig_last_insert_len = *last_insert_len;
770  memcpy(orig_dist_cache, dist_cache, 4 * sizeof(dist_cache[0]));
771  orig_num_commands = *num_commands;
772  nodes = BROTLI_ALLOC(m, ZopfliNode, num_bytes + 1);
773  if (BROTLI_IS_OOM(m)) return;
774  InitZopfliCostModel(m, &model, num_bytes);
775  if (BROTLI_IS_OOM(m)) return;
776  for (i = 0; i < 2; i++) {
777    BrotliInitZopfliNodes(nodes, num_bytes + 1);
778    if (i == 0) {
779      ZopfliCostModelSetFromLiteralCosts(
780          &model, position, ringbuffer, ringbuffer_mask);
781    } else {
782      ZopfliCostModelSetFromCommands(&model, position, ringbuffer,
783          ringbuffer_mask, commands, *num_commands - orig_num_commands,
784          orig_last_insert_len);
785    }
786    *num_commands = orig_num_commands;
787    *num_literals = orig_num_literals;
788    *last_insert_len = orig_last_insert_len;
789    memcpy(dist_cache, orig_dist_cache, 4 * sizeof(dist_cache[0]));
790    *num_commands += ZopfliIterate(num_bytes, position, ringbuffer,
791        ringbuffer_mask, params, max_backward_limit, gap, dist_cache,
792        &model, num_matches, matches, nodes);
793    BrotliZopfliCreateCommands(num_bytes, position, max_backward_limit,
794        nodes, dist_cache, last_insert_len, params, commands, num_literals);
795  }
796  CleanupZopfliCostModel(m, &model);
797  BROTLI_FREE(m, nodes);
798  BROTLI_FREE(m, matches);
799  BROTLI_FREE(m, num_matches);
800}
801
802#if defined(__cplusplus) || defined(c_plusplus)
803}  /* extern "C" */
804#endif
805