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