Added brotli enc/ and tools/ directories.

third_party/brotli/enc/backward_references.cc

+/* Copyright 2013 Google Inc. All Rights Reserved.
+
+   Distributed under MIT license.
+   See file LICENSE for detail or copy at https://opensource.org/licenses/MIT
+*/
+
+// Function to find backward reference copies.
+
+#include "./backward_references.h"
+
+#include <algorithm>
+#include <limits>
+#include <vector>
+
+#include "./command.h"
+#include "./fast_log.h"
+#include "./literal_cost.h"
+
+namespace brotli {
+
+// The maximum length for which the zopflification uses distinct distances.
+static const uint16_t kMaxZopfliLen = 325;
+
+// Histogram based cost model for zopflification.
+class ZopfliCostModel {
+ public:
+  ZopfliCostModel(void) : min_cost_cmd_(kInfinity) {}
+
+  void SetFromCommands(size_t num_bytes,
+                       size_t position,
+                       const uint8_t* ringbuffer,
+                       size_t ringbuffer_mask,
+                       const Command* commands,
+                       size_t num_commands,
+                       size_t last_insert_len) {
+    std::vector<uint32_t> histogram_literal(256, 0);
+    std::vector<uint32_t> histogram_cmd(kNumCommandPrefixes, 0);
+    std::vector<uint32_t> histogram_dist(kNumDistancePrefixes, 0);
+
+    size_t pos = position - last_insert_len;
+    for (size_t i = 0; i < num_commands; i++) {
+      size_t inslength = commands[i].insert_len_;
+      size_t copylength = commands[i].copy_len();
+      size_t distcode = commands[i].dist_prefix_;
+      size_t cmdcode = commands[i].cmd_prefix_;
+
+      histogram_cmd[cmdcode]++;
+      if (cmdcode >= 128) histogram_dist[distcode]++;
+
+      for (size_t j = 0; j < inslength; j++) {
+        histogram_literal[ringbuffer[(pos + j) & ringbuffer_mask]]++;
+      }
+
+      pos += inslength + copylength;
+    }
+
+    std::vector<float> cost_literal;
+    Set(histogram_literal, &cost_literal);
+    Set(histogram_cmd, &cost_cmd_);
+    Set(histogram_dist, &cost_dist_);
+
+    for (uint32_t i = 0; i < kNumCommandPrefixes; ++i) {
+      min_cost_cmd_ = std::min(min_cost_cmd_, cost_cmd_[i]);
+    }
+
+    literal_costs_.resize(num_bytes + 1);
+    literal_costs_[0] = 0.0;
+    for (size_t i = 0; i < num_bytes; ++i) {
+      literal_costs_[i + 1] = literal_costs_[i] +
+          cost_literal[ringbuffer[(position + i) & ringbuffer_mask]];
+    }
+  }
+
+  void SetFromLiteralCosts(size_t num_bytes,
+                           size_t position,
+                           const uint8_t* ringbuffer,
+                           size_t ringbuffer_mask) {
+    literal_costs_.resize(num_bytes + 2);
+    EstimateBitCostsForLiterals(position, num_bytes, ringbuffer_mask,
+                                ringbuffer, &literal_costs_[1]);
+    literal_costs_[0] = 0.0;
+    for (size_t i = 0; i < num_bytes; ++i) {
+      literal_costs_[i + 1] += literal_costs_[i];
+    }
+    cost_cmd_.resize(kNumCommandPrefixes);
+    cost_dist_.resize(kNumDistancePrefixes);
+    for (uint32_t i = 0; i < kNumCommandPrefixes; ++i) {
+      cost_cmd_[i] = static_cast<float>(FastLog2(11 + i));
+    }
+    for (uint32_t i = 0; i < kNumDistancePrefixes; ++i) {
+      cost_dist_[i] = static_cast<float>(FastLog2(20 + i));
+    }
+    min_cost_cmd_ = static_cast<float>(FastLog2(11));
+  }
+
+  float GetCommandCost(
+      size_t dist_code, size_t length_code, size_t insert_length) const {
+    uint16_t inscode = GetInsertLengthCode(insert_length);
+    uint16_t copycode = GetCopyLengthCode(length_code);
+    uint16_t cmdcode = CombineLengthCodes(inscode, copycode, dist_code == 0);
+    uint16_t dist_symbol;
+    uint32_t distextra;
+    PrefixEncodeCopyDistance(dist_code, 0, 0, &dist_symbol, &distextra);
+    uint32_t distnumextra = distextra >> 24;
+
+    float result = static_cast<float>(
+        GetInsertExtra(inscode) + GetCopyExtra(copycode) + distnumextra);
+    result += cost_cmd_[cmdcode];
+    if (cmdcode >= 128) result += cost_dist_[dist_symbol];
+    return result;
+  }
+
+  float GetLiteralCosts(size_t from, size_t to) const {
+    return literal_costs_[to] - literal_costs_[from];
+  }
+
+  float GetMinCostCmd(void) const {
+    return min_cost_cmd_;
+  }
+
+ private:
+  void Set(const std::vector<uint32_t>& histogram, std::vector<float>* cost) {
+    cost->resize(histogram.size());
+    size_t sum = 0;
+    for (size_t i = 0; i < histogram.size(); i++) {
+      sum += histogram[i];
+    }
+    float log2sum = static_cast<float>(FastLog2(sum));
+    for (size_t i = 0; i < histogram.size(); i++) {
+      if (histogram[i] == 0) {
+        (*cost)[i] = log2sum + 2;
+        continue;
+      }
+
+      // Shannon bits for this symbol.
+      (*cost)[i] = log2sum - static_cast<float>(FastLog2(histogram[i]));
+
+      // Cannot be coded with less than 1 bit
+      if ((*cost)[i] < 1) (*cost)[i] = 1;
+    }
+  }
+
+  std::vector<float> cost_cmd_;  // The insert and copy length symbols.
+  std::vector<float> cost_dist_;
+  // Cumulative costs of literals per position in the stream.
+  std::vector<float> literal_costs_;
+  float min_cost_cmd_;
+};
+
+inline size_t ComputeDistanceCode(size_t distance,
+                                  size_t max_distance,
+                                  int quality,
+                                  const int* dist_cache) {
+  if (distance <= max_distance) {
+    if (distance == static_cast<size_t>(dist_cache[0])) {
+      return 0;
+    } else if (distance == static_cast<size_t>(dist_cache[1])) {
+      return 1;
+    } else if (distance == static_cast<size_t>(dist_cache[2])) {
+      return 2;
+    } else if (distance == static_cast<size_t>(dist_cache[3])) {
+      return 3;
+    } else if (quality > 3 && distance >= 6) {
+      for (size_t k = 4; k < kNumDistanceShortCodes; ++k) {
+        size_t idx = kDistanceCacheIndex[k];
+        size_t candidate =
+            static_cast<size_t>(dist_cache[idx] + kDistanceCacheOffset[k]);
+        static const size_t kLimits[16] = {  0,  0,  0,  0,
+                                             6,  6, 11, 11,
+                                            11, 11, 11, 11,
+                                            12, 12, 12, 12 };
+        if (distance == candidate && distance >= kLimits[k]) {
+          return k;
+        }
+      }
+    }
+  }
+  return distance + 15;
+}
+
+// REQUIRES: len >= 2, start_pos <= pos
+// REQUIRES: cost < kInfinity, nodes[start_pos].cost < kInfinity
+// Maintains the "ZopfliNode array invariant".
+inline void UpdateZopfliNode(ZopfliNode* nodes, size_t pos, size_t start_pos,
+                             size_t len, size_t len_code, size_t dist,
+                             size_t short_code, float cost) {
+  ZopfliNode& next = nodes[pos + len];
+  next.length = static_cast<uint32_t>(len | ((len + 9u - len_code) << 24));
+  next.distance = static_cast<uint32_t>(dist | (short_code << 25));
+  next.insert_length = static_cast<uint32_t>(pos - start_pos);
+  next.cost = cost;
+}
+
+// Maintains the smallest 2^k cost difference together with their positions
+class StartPosQueue {
+ public:
+  struct PosData {
+    size_t pos;
+    int distance_cache[4];
+    float costdiff;
+  };
+
+  explicit StartPosQueue(int bits)
+      : mask_((1u << bits) - 1), q_(1 << bits), idx_(0) {}
+
+  void Clear(void) {
+    idx_ = 0;
+  }
+
+  void Push(const StartPosQueue::PosData& posdata) {
+    size_t offset = ~idx_ & mask_;
+    ++idx_;
+    size_t len = size();
+    q_[offset] = posdata;
+    /* Restore the sorted order. In the list of |len| items at most |len - 1|
+       adjacent element comparisons / swaps are required. */
+    for (size_t i = 1; i < len; ++i) {
+      if (q_[offset & mask_].costdiff > q_[(offset + 1) & mask_].costdiff) {
+        std::swap(q_[offset & mask_], q_[(offset + 1) & mask_]);
+      }
+      ++offset;
+    }
+  }
+
+  size_t size(void) const { return std::min(idx_, mask_ + 1); }
+
+  const StartPosQueue::PosData& GetStartPosData(size_t k) const {
+    return q_[(k - idx_) & mask_];
+  }
+
+ private:
+  const size_t mask_;
+  std::vector<PosData> q_;
+  size_t idx_;
+};
+
+// Returns the minimum possible copy length that can improve the cost of any
+// future position.
+static size_t ComputeMinimumCopyLength(const StartPosQueue& queue,
+                                       const ZopfliNode* nodes,
+                                       const ZopfliCostModel& model,
+                                       const size_t num_bytes,
+                                       const size_t pos) {
+  // Compute the minimum possible cost of reaching any future position.
+  const size_t start0 = queue.GetStartPosData(0).pos;
+  float min_cost = (nodes[start0].cost +
+                    model.GetLiteralCosts(start0, pos) +
+                    model.GetMinCostCmd());
+  size_t len = 2;
+  size_t next_len_bucket = 4;
+  size_t next_len_offset = 10;
+  while (pos + len <= num_bytes && nodes[pos + len].cost <= min_cost) {
+    // We already reached (pos + len) with no more cost than the minimum
+    // possible cost of reaching anything from this pos, so there is no point in
+    // looking for lengths <= len.
+    ++len;
+    if (len == next_len_offset) {
+      // We reached the next copy length code bucket, so we add one more
+      // extra bit to the minimum cost.
+      min_cost += static_cast<float>(1.0);
+      next_len_offset += next_len_bucket;
+      next_len_bucket *= 2;
+    }
+  }
+  return len;
+}
+
+// Fills in dist_cache[0..3] with the last four distances (as defined by
+// Section 4. of the Spec) that would be used at (block_start + pos) if we
+// used the shortest path of commands from block_start, computed from
+// nodes[0..pos]. The last four distances at block_start are in
+// starting_dist_cach[0..3].
+// REQUIRES: nodes[pos].cost < kInfinity
+// REQUIRES: nodes[0..pos] satisfies that "ZopfliNode array invariant".
+static void ComputeDistanceCache(const size_t block_start,
+                                 const size_t pos,
+                                 const size_t max_backward,
+                                 const int* starting_dist_cache,
+                                 const ZopfliNode* nodes,
+                                 int* dist_cache) {
+  int idx = 0;
+  size_t p = pos;
+  // Because of prerequisite, does at most (pos + 1) / 2 iterations.
+  while (idx < 4 && p > 0) {
+    const size_t clen = nodes[p].copy_length();
+    const size_t ilen = nodes[p].insert_length;
+    const size_t dist = nodes[p].copy_distance();
+    // Since block_start + p is the end position of the command, the copy part
+    // starts from block_start + p - clen. Distances that are greater than this
+    // or greater than max_backward are static dictionary references, and do
+    // not update the last distances. Also distance code 0 (last distance)
+    // does not update the last distances.
+    if (dist + clen <= block_start + p && dist <= max_backward &&
+        nodes[p].distance_code() > 0) {
+      dist_cache[idx++] = static_cast<int>(dist);
+    }
+    // Because of prerequisite, p >= clen + ilen >= 2.
+    p -= clen + ilen;
+  }
+  for (; idx < 4; ++idx) {
+    dist_cache[idx] = *starting_dist_cache++;
+  }
+}
+
+static void UpdateNodes(const size_t num_bytes,
+                        const size_t block_start,
+                        const size_t pos,
+                        const uint8_t* ringbuffer,
+                        const size_t ringbuffer_mask,
+                        const size_t max_backward_limit,
+                        const int* starting_dist_cache,
+                        const size_t num_matches,
+                        const BackwardMatch* matches,
+                        const ZopfliCostModel* model,
+                        StartPosQueue* queue,
+                        ZopfliNode* nodes) {
+  size_t cur_ix = block_start + pos;
+  size_t cur_ix_masked = cur_ix & ringbuffer_mask;
+  size_t max_distance = std::min(cur_ix, max_backward_limit);
+
+  if (nodes[pos].cost <= model->GetLiteralCosts(0, pos)) {
+    StartPosQueue::PosData posdata;
+    posdata.pos = pos;
+    posdata.costdiff = nodes[pos].cost - model->GetLiteralCosts(0, pos);
+    ComputeDistanceCache(block_start, pos, max_backward_limit,
+                         starting_dist_cache, nodes, posdata.distance_cache);
+    queue->Push(posdata);
+  }
+
+  const size_t min_len = ComputeMinimumCopyLength(
+      *queue, nodes, *model, num_bytes, pos);
+
+  // Go over the command starting positions in order of increasing cost
+  // difference.
+  for (size_t k = 0; k < 5 && k < queue->size(); ++k) {
+    const StartPosQueue::PosData& posdata = queue->GetStartPosData(k);
+    const size_t start = posdata.pos;
+    const float start_costdiff = posdata.costdiff;
+
+    // Look for last distance matches using the distance cache from this
+    // starting position.
+    size_t best_len = min_len - 1;
+    for (size_t j = 0; j < kNumDistanceShortCodes; ++j) {
+      const size_t idx = kDistanceCacheIndex[j];
+      const size_t backward = static_cast<size_t>(posdata.distance_cache[idx] +
+                                                  kDistanceCacheOffset[j]);
+      size_t prev_ix = cur_ix - backward;
+      if (prev_ix >= cur_ix) {
+        continue;
+      }
+      if (PREDICT_FALSE(backward > max_distance)) {
+        continue;
+      }
+      prev_ix &= ringbuffer_mask;
+
+      if (cur_ix_masked + best_len > ringbuffer_mask ||
+          prev_ix + best_len > ringbuffer_mask ||
+          ringbuffer[cur_ix_masked + best_len] !=
+          ringbuffer[prev_ix + best_len]) {
+        continue;
+      }
+      const size_t len =
+          FindMatchLengthWithLimit(&ringbuffer[prev_ix],
+                                   &ringbuffer[cur_ix_masked],
+                                   num_bytes - pos);
+      for (size_t l = best_len + 1; l <= len; ++l) {
+        const size_t inslen = pos - start;
+        float cmd_cost = model->GetCommandCost(j, l, inslen);
+        float cost = start_costdiff + cmd_cost + model->GetLiteralCosts(0, pos);
+        if (cost < nodes[pos + l].cost) {
+          UpdateZopfliNode(&nodes[0], pos, start, l, l, backward, j + 1, cost);
+        }
+        best_len = l;
+      }
+    }
+
+    // At higher iterations look only for new last distance matches, since
+    // looking only for new command start positions with the same distances
+    // does not help much.
+    if (k >= 2) continue;
+
+    // Loop through all possible copy lengths at this position.
+    size_t len = min_len;
+    for (size_t j = 0; j < num_matches; ++j) {
+      BackwardMatch match = matches[j];
+      size_t dist = match.distance;
+      bool is_dictionary_match = dist > max_distance;
+      // We already tried all possible last distance matches, so we can use
+      // normal distance code here.
+      size_t dist_code = dist + 15;
+      // Try all copy lengths up until the maximum copy length corresponding
+      // to this distance. If the distance refers to the static dictionary, or
+      // the maximum length is long enough, try only one maximum length.
+      size_t max_len = match.length();
+      if (len < max_len && (is_dictionary_match || max_len > kMaxZopfliLen)) {
+        len = max_len;
+      }
+      for (; len <= max_len; ++len) {
+        size_t len_code = is_dictionary_match ? match.length_code() : len;
+        const size_t inslen = pos - start;
+        float cmd_cost = model->GetCommandCost(dist_code, len_code, inslen);
+        float cost = start_costdiff + cmd_cost + model->GetLiteralCosts(0, pos);
+        if (cost < nodes[pos + len].cost) {
+          UpdateZopfliNode(&nodes[0], pos, start, len, len_code, dist, 0, cost);
+        }
+      }
+    }
+  }
+}
+
+static void ComputeShortestPathFromNodes(size_t num_bytes,
+                                         const ZopfliNode* nodes,
+                                         std::vector<uint32_t>* path) {
+  std::vector<uint32_t> backwards(num_bytes / 2 + 1);
+  size_t index = num_bytes;
+  while (nodes[index].cost == kInfinity) --index;
+  size_t num_commands = 0;
+  while (index != 0) {
+    size_t len = nodes[index].command_length();
+    backwards[num_commands++] = static_cast<uint32_t>(len);
+    index -= len;
+  }
+  path->resize(num_commands);
+  for (size_t i = num_commands, j = 0; i > 0; --i, ++j) {
+    (*path)[j] = backwards[i - 1];
+  }
+}
+
+void ZopfliCreateCommands(const size_t num_bytes,
+                          const size_t block_start,
+                          const size_t max_backward_limit,
+                          const std::vector<uint32_t>& path,
+                          const ZopfliNode* nodes,
+                          int* dist_cache,
+                          size_t* last_insert_len,
+                          Command* commands,
+                          size_t* num_literals) {
+  size_t pos = 0;
+  for (size_t i = 0; i < path.size(); i++) {
+    const ZopfliNode& next = nodes[pos + path[i]];
+    size_t copy_length = next.copy_length();
+    size_t insert_length = next.insert_length;
+    pos += insert_length;
+    if (i == 0) {
+      insert_length += *last_insert_len;
+      *last_insert_len = 0;
+    }
+    size_t distance = next.copy_distance();
+    size_t len_code = next.length_code();
+    size_t max_distance = std::min(block_start + pos, max_backward_limit);
+    bool is_dictionary = (distance > max_distance);
+    size_t dist_code = next.distance_code();
+
+    Command cmd(insert_length, copy_length, len_code, dist_code);
+    commands[i] = cmd;
+
+    if (!is_dictionary && dist_code > 0) {
+      dist_cache[3] = dist_cache[2];
+      dist_cache[2] = dist_cache[1];
+      dist_cache[1] = dist_cache[0];
+      dist_cache[0] = static_cast<int>(distance);
+    }
+
+    *num_literals += insert_length;
+    pos += copy_length;
+  }
+  *last_insert_len += num_bytes - pos;
+}
+
+static void ZopfliIterate(size_t num_bytes,
+                          size_t position,
+                          const uint8_t* ringbuffer,
+                          size_t ringbuffer_mask,
+                          const size_t max_backward_limit,
+                          const int* dist_cache,
+                          const ZopfliCostModel& model,
+                          const std::vector<uint32_t>& num_matches,
+                          const std::vector<BackwardMatch>& matches,
+                          ZopfliNode* nodes,
+                          std::vector<uint32_t>* path) {
+  nodes[0].length = 0;
+  nodes[0].cost = 0;
+  StartPosQueue queue(3);
+  size_t cur_match_pos = 0;
+  for (size_t i = 0; i + 3 < num_bytes; i++) {
+    UpdateNodes(num_bytes, position, i, ringbuffer, ringbuffer_mask,
+                max_backward_limit, dist_cache, num_matches[i],
+                &matches[cur_match_pos], &model, &queue, &nodes[0]);
+    cur_match_pos += num_matches[i];
+    // The zopflification can be too slow in case of very long lengths, so in
+    // such case skip it all, it does not cost a lot of compression ratio.
+    if (num_matches[i] == 1 &&
+        matches[cur_match_pos - 1].length() > kMaxZopfliLen) {
+      i += matches[cur_match_pos - 1].length() - 1;
+      queue.Clear();
+    }
+  }
+  ComputeShortestPathFromNodes(num_bytes, &nodes[0], path);
+}
+
+
+void ZopfliComputeShortestPath(size_t num_bytes,
+                               size_t position,
+                               const uint8_t* ringbuffer,
+                               size_t ringbuffer_mask,
+                               const size_t max_backward_limit,
+                               const int* dist_cache,
+                               Hashers::H10* hasher,
+                               ZopfliNode* nodes,
+                               std::vector<uint32_t>* path) {
+  nodes[0].length = 0;
+  nodes[0].cost = 0;
+  ZopfliCostModel* model = new ZopfliCostModel;
+  model->SetFromLiteralCosts(num_bytes, position,
+                             ringbuffer, ringbuffer_mask);
+  StartPosQueue queue(3);
+  BackwardMatch matches[Hashers::H10::kMaxNumMatches];
+  for (size_t i = 0; i + 3 < num_bytes; i++) {
+    const size_t max_distance = std::min(position + i, max_backward_limit);
+    size_t num_matches = hasher->FindAllMatches(
+        ringbuffer, ringbuffer_mask, position + i, num_bytes - i, max_distance,
+        matches);
+    if (num_matches > 0 &&
+        matches[num_matches - 1].length() > kMaxZopfliLen) {
+      matches[0] = matches[num_matches - 1];
+      num_matches = 1;
+    }
+    UpdateNodes(num_bytes, position, i, ringbuffer, ringbuffer_mask,
+                max_backward_limit, dist_cache, num_matches, matches,
+                model, &queue, nodes);
+    if (num_matches == 1 && matches[0].length() > kMaxZopfliLen) {
+      for (size_t j = 1; j < matches[0].length() && i + 4 < num_bytes; ++j) {
+        ++i;
+        if (matches[0].length() - j < 64 &&
+            num_bytes - i >= kMaxTreeCompLength) {
+          hasher->Store(ringbuffer, ringbuffer_mask, position + i);
+        }
+      }
+      queue.Clear();
+    }
+  }
+  delete model;
+  ComputeShortestPathFromNodes(num_bytes, nodes, path);
+}
+
+template<typename Hasher>
+void CreateBackwardReferences(size_t num_bytes,
+                              size_t position,
+                              bool is_last,
+                              const uint8_t* ringbuffer,
+                              size_t ringbuffer_mask,
+                              const int quality,
+                              const int lgwin,
+                              Hasher* hasher,
+                              int* dist_cache,
+                              size_t* last_insert_len,
+                              Command* commands,
+                              size_t* num_commands,
+                              size_t* num_literals) {
+  // Set maximum distance, see section 9.1. of the spec.
+  const size_t max_backward_limit = (1 << lgwin) - 16;
+
+  // Choose which init method is faster.
+  // memset is about 100 times faster than hasher->InitForData().
+  const size_t kMaxBytesForPartialHashInit = Hasher::kHashMapSize >> 7;
+  if (position == 0 && is_last && num_bytes <= kMaxBytesForPartialHashInit) {
+    hasher->InitForData(ringbuffer, num_bytes);
+  } else {
+    hasher->Init();
+  }
+  if (num_bytes >= 3 && position >= 3) {
+    // Prepare the hashes for three last bytes of the last write.
+    // These could not be calculated before, since they require knowledge
+    // of both the previous and the current block.
+    hasher->Store(&ringbuffer[(position - 3) & ringbuffer_mask],
+                  static_cast<uint32_t>(position - 3));
+    hasher->Store(&ringbuffer[(position - 2) & ringbuffer_mask],
+                  static_cast<uint32_t>(position - 2));
+    hasher->Store(&ringbuffer[(position - 1) & ringbuffer_mask],
+                  static_cast<uint32_t>(position - 1));
+  }
+  const Command * const orig_commands = commands;
+  size_t insert_length = *last_insert_len;
+  size_t i = position & ringbuffer_mask;
+  const size_t i_diff = position - i;
+  const size_t i_end = i + num_bytes;
+
+  // For speed up heuristics for random data.
+  const size_t random_heuristics_window_size = quality < 9 ? 64 : 512;
+  size_t apply_random_heuristics = i + random_heuristics_window_size;
+
+  // Minimum score to accept a backward reference.
+  const double kMinScore = 4.0;
+
+  while (i + Hasher::kHashTypeLength - 1 < i_end) {
+    size_t max_length = i_end - i;
+    size_t max_distance = std::min(i + i_diff, max_backward_limit);
+    size_t best_len = 0;
+    size_t best_len_code = 0;
+    size_t best_dist = 0;
+    double best_score = kMinScore;
+    bool match_found = hasher->FindLongestMatch(
+        ringbuffer, ringbuffer_mask,
+        dist_cache, static_cast<uint32_t>(i + i_diff), max_length, max_distance,
+        &best_len, &best_len_code, &best_dist, &best_score);
+    if (match_found) {
+      // Found a match. Let's look for something even better ahead.
+      int delayed_backward_references_in_row = 0;
+      for (;;) {
+        --max_length;
+        size_t best_len_2 =
+            quality < 5 ? std::min(best_len - 1, max_length) : 0;
+        size_t best_len_code_2 = 0;
+        size_t best_dist_2 = 0;
+        double best_score_2 = kMinScore;
+        max_distance = std::min(i + i_diff + 1, max_backward_limit);
+        match_found = hasher->FindLongestMatch(
+            ringbuffer, ringbuffer_mask,
+            dist_cache, static_cast<uint32_t>(i + i_diff + 1),
+            max_length, max_distance,
+            &best_len_2, &best_len_code_2, &best_dist_2, &best_score_2);
+        double cost_diff_lazy = 7.0;
+        if (match_found && best_score_2 >= best_score + cost_diff_lazy) {
+          // Ok, let's just write one byte for now and start a match from the
+            // next byte.
+          ++i;
+          ++insert_length;
+          best_len = best_len_2;
+          best_len_code = best_len_code_2;
+          best_dist = best_dist_2;
+          best_score = best_score_2;
+          if (++delayed_backward_references_in_row < 4) {
+            continue;
+          }
+        }
+        break;
+      }
+      apply_random_heuristics =
+          i + 2 * best_len + random_heuristics_window_size;
+      max_distance = std::min(i + i_diff, max_backward_limit);
+      // The first 16 codes are special shortcodes, and the minimum offset is 1.
+      size_t distance_code =
+          ComputeDistanceCode(best_dist, max_distance, quality, dist_cache);
+      if (best_dist <= max_distance && distance_code > 0) {
+        dist_cache[3] = dist_cache[2];
+        dist_cache[2] = dist_cache[1];
+        dist_cache[1] = dist_cache[0];
+        dist_cache[0] = static_cast<int>(best_dist);
+      }
+      Command cmd(insert_length, best_len, best_len_code, distance_code);
+      *commands++ = cmd;
+      *num_literals += insert_length;
+      insert_length = 0;
+      // Put the hash keys into the table, if there are enough
+      // bytes left.
+      for (size_t j = 2; j < best_len; ++j) {
+        hasher->Store(&ringbuffer[i + j],
+                      static_cast<uint32_t>(i + i_diff + j));
+      }
+      i += best_len;
+    } else {
+      ++insert_length;
+      ++i;
+      // If we have not seen matches for a long time, we can skip some
+      // match lookups. Unsuccessful match lookups are very very expensive
+      // and this kind of a heuristic speeds up compression quite
+      // a lot.
+      if (i > apply_random_heuristics) {
+        // Going through uncompressible data, jump.
+        if (i > apply_random_heuristics + 4 * random_heuristics_window_size) {
+          // It is quite a long time since we saw a copy, so we assume
+          // that this data is not compressible, and store hashes less
+          // often. Hashes of non compressible data are less likely to
+          // turn out to be useful in the future, too, so we store less of
+          // them to not to flood out the hash table of good compressible
+          // data.
+          size_t i_jump = std::min(i + 16, i_end - 4);
+          for (; i < i_jump; i += 4) {
+            hasher->Store(ringbuffer + i, static_cast<uint32_t>(i + i_diff));
+            insert_length += 4;
+          }
+        } else {
+          size_t i_jump = std::min(i + 8, i_end - 3);
+          for (; i < i_jump; i += 2) {
+            hasher->Store(ringbuffer + i, static_cast<uint32_t>(i + i_diff));
+            insert_length += 2;
+          }
+        }
+      }
+    }
+  }
+  insert_length += i_end - i;
+  *last_insert_len = insert_length;
+  *num_commands += static_cast<size_t>(commands - orig_commands);
+}
+
+void CreateBackwardReferences(size_t num_bytes,
+                              size_t position,
+                              bool is_last,
+                              const uint8_t* ringbuffer,
+                              size_t ringbuffer_mask,
+                              const int quality,
+                              const int lgwin,
+                              Hashers* hashers,
+                              int hash_type,
+                              int* dist_cache,
+                              size_t* last_insert_len,
+                              Command* commands,
+                              size_t* num_commands,
+                              size_t* num_literals) {
+  bool zopflify = quality > 9;
+  if (zopflify) {
+    Hashers::H10* hasher = hashers->hash_h10;
+    hasher->Init(lgwin, position, num_bytes, is_last);
+    hasher->StitchToPreviousBlock(num_bytes, position,
+                                  ringbuffer, ringbuffer_mask);
+    // Set maximum distance, see section 9.1. of the spec.
+    const size_t max_backward_limit = (1 << lgwin) - 16;
+    if (quality == 10) {
+      std::vector<ZopfliNode> nodes(num_bytes + 1);
+      std::vector<uint32_t> path;
+      ZopfliComputeShortestPath(num_bytes, position,
+                                ringbuffer, ringbuffer_mask,
+                                max_backward_limit, dist_cache, hasher,
+                                &nodes[0], &path);
+      ZopfliCreateCommands(num_bytes, position, max_backward_limit, path,
+                           &nodes[0], dist_cache, last_insert_len, commands,
+                           num_literals);
+      *num_commands += path.size();
+      return;
+    }
+    std::vector<uint32_t> num_matches(num_bytes);
+    std::vector<BackwardMatch> matches(4 * num_bytes);
+    size_t cur_match_pos = 0;
+    for (size_t i = 0; i + 3 < num_bytes; ++i) {
+      size_t max_distance = std::min(position + i, max_backward_limit);
+      size_t max_length = num_bytes - i;
+      // Ensure that we have enough free slots.
+      if (matches.size() < cur_match_pos + Hashers::H10::kMaxNumMatches) {
+        matches.resize(cur_match_pos + Hashers::H10::kMaxNumMatches);
+      }
+      size_t num_found_matches = hasher->FindAllMatches(
+          ringbuffer, ringbuffer_mask, position + i, max_length, max_distance,
+          &matches[cur_match_pos]);
+      const size_t cur_match_end = cur_match_pos + num_found_matches;
+      for (size_t j = cur_match_pos; j + 1 < cur_match_end; ++j) {
+        assert(matches[j].length() < matches[j + 1].length());
+        assert(matches[j].distance > max_distance ||
+               matches[j].distance <= matches[j + 1].distance);
+      }
+      num_matches[i] = static_cast<uint32_t>(num_found_matches);
+      if (num_found_matches > 0) {
+        const size_t match_len = matches[cur_match_end - 1].length();
+        if (match_len > kMaxZopfliLen) {
+          matches[cur_match_pos++] = matches[cur_match_end - 1];
+          num_matches[i] = 1;
+          for (size_t j = 1; j < match_len; ++j) {
+            ++i;
+            if (match_len - j < 64 && num_bytes - i >= kMaxTreeCompLength) {
+              hasher->Store(ringbuffer, ringbuffer_mask, position + i);
+            }
+            num_matches[i] = 0;
+          }
+        } else {
+          cur_match_pos = cur_match_end;
+        }
+      }
+    }
+    size_t orig_num_literals = *num_literals;
+    size_t orig_last_insert_len = *last_insert_len;
+    int orig_dist_cache[4] = {
+      dist_cache[0], dist_cache[1], dist_cache[2], dist_cache[3]
+    };
+    size_t orig_num_commands = *num_commands;
+    static const size_t kIterations = 2;
+    for (size_t i = 0; i < kIterations; i++) {
+      ZopfliCostModel model;
+      if (i == 0) {
+        model.SetFromLiteralCosts(num_bytes, position,
+                                  ringbuffer, ringbuffer_mask);
+      } else {
+        model.SetFromCommands(num_bytes, position,
+                              ringbuffer, ringbuffer_mask,
+                              commands, *num_commands - orig_num_commands,
+                              orig_last_insert_len);
+      }
+      *num_commands = orig_num_commands;
+      *num_literals = orig_num_literals;
+      *last_insert_len = orig_last_insert_len;
+      memcpy(dist_cache, orig_dist_cache, 4 * sizeof(dist_cache[0]));
+      std::vector<ZopfliNode> nodes(num_bytes + 1);
+      std::vector<uint32_t> path;
+      ZopfliIterate(num_bytes, position, ringbuffer, ringbuffer_mask,
+                    max_backward_limit, dist_cache, model, num_matches, matches,
+                    &nodes[0], &path);
+      ZopfliCreateCommands(num_bytes, position, max_backward_limit, path,
+                           &nodes[0], dist_cache, last_insert_len, commands,
+                           num_literals);
+      *num_commands += path.size();
+    }
+    return;
+  }
+
+  switch (hash_type) {
+    case 2:
+      CreateBackwardReferences<Hashers::H2>(
+          num_bytes, position, is_last, ringbuffer, ringbuffer_mask,
+          quality, lgwin, hashers->hash_h2, dist_cache,
+          last_insert_len, commands, num_commands, num_literals);
+      break;
+    case 3:
+      CreateBackwardReferences<Hashers::H3>(
+          num_bytes, position, is_last, ringbuffer, ringbuffer_mask,
+          quality, lgwin, hashers->hash_h3, dist_cache,
+          last_insert_len, commands, num_commands, num_literals);
+      break;
+    case 4:
+      CreateBackwardReferences<Hashers::H4>(
+          num_bytes, position, is_last, ringbuffer, ringbuffer_mask,
+          quality, lgwin, hashers->hash_h4, dist_cache,
+          last_insert_len, commands, num_commands, num_literals);
+      break;
+    case 5:
+      CreateBackwardReferences<Hashers::H5>(
+          num_bytes, position, is_last, ringbuffer, ringbuffer_mask,
+          quality, lgwin, hashers->hash_h5, dist_cache,
+          last_insert_len, commands, num_commands, num_literals);
+      break;
+    case 6:
+      CreateBackwardReferences<Hashers::H6>(
+          num_bytes, position, is_last, ringbuffer, ringbuffer_mask,
+          quality, lgwin, hashers->hash_h6, dist_cache,
+          last_insert_len, commands, num_commands, num_literals);
+      break;
+    case 7:
+      CreateBackwardReferences<Hashers::H7>(
+          num_bytes, position, is_last, ringbuffer, ringbuffer_mask,
+          quality, lgwin, hashers->hash_h7, dist_cache,
+          last_insert_len, commands, num_commands, num_literals);
+      break;
+    case 8:
+      CreateBackwardReferences<Hashers::H8>(
+          num_bytes, position, is_last, ringbuffer, ringbuffer_mask,
+          quality, lgwin, hashers->hash_h8, dist_cache,
+          last_insert_len, commands, num_commands, num_literals);
+      break;
+    case 9:
+      CreateBackwardReferences<Hashers::H9>(
+          num_bytes, position, is_last, ringbuffer, ringbuffer_mask,
+          quality, lgwin, hashers->hash_h9, dist_cache,
+          last_insert_len, commands, num_commands, num_literals);
+      break;
+    default:
+      break;
+  }
+}
+
+}  // namespace brotli