Update brotli to v1.0.0-snapshot.

third_party/brotli/enc/entropy_encode.cc

Index: third_party/brotli/enc/entropy_encode.cc
diff --git a/third_party/brotli/enc/entropy_encode.cc b/third_party/brotli/enc/entropy_encode.cc
deleted file mode 100644
index f18355d88db5a3cf7a1b85ea500210b59765ef85..0000000000000000000000000000000000000000
--- a/third_party/brotli/enc/entropy_encode.cc
+++ /dev/null
@@ -1,480 +0,0 @@
-/* Copyright 2010 Google Inc. All Rights Reserved.
-
-   Distributed under MIT license.
-   See file LICENSE for detail or copy at https://opensource.org/licenses/MIT
-*/
-
-// Entropy encoding (Huffman) utilities.
-
-#include "./entropy_encode.h"
-
-#include <algorithm>
-#include <limits>
-#include <cstdlib>
-
-#include "./histogram.h"
-#include "./port.h"
-#include "./types.h"
-
-namespace brotli {
-
-void SetDepth(const HuffmanTree &p,
-              HuffmanTree *pool,
-              uint8_t *depth,
-              uint8_t level) {
-  if (p.index_left_ >= 0) {
-    ++level;
-    SetDepth(pool[p.index_left_], pool, depth, level);
-    SetDepth(pool[p.index_right_or_value_], pool, depth, level);
-  } else {
-    depth[p.index_right_or_value_] = level;
-  }
-}
-
-// Sort the root nodes, least popular first.
-static inline bool SortHuffmanTree(const HuffmanTree& v0,
-                                   const HuffmanTree& v1) {
-  if (v0.total_count_ != v1.total_count_) {
-    return v0.total_count_ < v1.total_count_;
-  }
-  return v0.index_right_or_value_ > v1.index_right_or_value_;
-}
-
-// This function will create a Huffman tree.
-//
-// The catch here is that the tree cannot be arbitrarily deep.
-// Brotli specifies a maximum depth of 15 bits for "code trees"
-// and 7 bits for "code length code trees."
-//
-// count_limit is the value that is to be faked as the minimum value
-// and this minimum value is raised until the tree matches the
-// maximum length requirement.
-//
-// This algorithm is not of excellent performance for very long data blocks,
-// especially when population counts are longer than 2**tree_limit, but
-// we are not planning to use this with extremely long blocks.
-//
-// See http://en.wikipedia.org/wiki/Huffman_coding
-void CreateHuffmanTree(const uint32_t *data,
-                       const size_t length,
-                       const int tree_limit,
-                       HuffmanTree* tree,
-                       uint8_t *depth) {
-  // For block sizes below 64 kB, we never need to do a second iteration
-  // of this loop. Probably all of our block sizes will be smaller than
-  // that, so this loop is mostly of academic interest. If we actually
-  // would need this, we would be better off with the Katajainen algorithm.
-  for (uint32_t count_limit = 1; ; count_limit *= 2) {
-    size_t n = 0;
-    for (size_t i = length; i != 0;) {
-      --i;
-      if (data[i]) {
-        const uint32_t count = std::max(data[i], count_limit);
-        tree[n++] = HuffmanTree(count, -1, static_cast<int16_t>(i));
-      }
-    }
-
-    if (n == 1) {
-      depth[tree[0].index_right_or_value_] = 1;      // Only one element.
-      break;
-    }
-
-    std::sort(tree, tree + n, SortHuffmanTree);
-
-    // The nodes are:
-    // [0, n): the sorted leaf nodes that we start with.
-    // [n]: we add a sentinel here.
-    // [n + 1, 2n): new parent nodes are added here, starting from
-    //              (n+1). These are naturally in ascending order.
-    // [2n]: we add a sentinel at the end as well.
-    // There will be (2n+1) elements at the end.
-    const HuffmanTree sentinel(std::numeric_limits<uint32_t>::max(), -1, -1);
-    tree[n] = sentinel;
-    tree[n + 1] = sentinel;
-
-    size_t i = 0;      // Points to the next leaf node.
-    size_t j = n + 1;  // Points to the next non-leaf node.
-    for (size_t k = n - 1; k != 0; --k) {
-      size_t left, right;
-      if (tree[i].total_count_ <= tree[j].total_count_) {
-        left = i;
-        ++i;
-      } else {
-        left = j;
-        ++j;
-      }
-      if (tree[i].total_count_ <= tree[j].total_count_) {
-        right = i;
-        ++i;
-      } else {
-        right = j;
-        ++j;
-      }
-
-      // The sentinel node becomes the parent node.
-      size_t j_end = 2 * n - k;
-      tree[j_end].total_count_ =
-          tree[left].total_count_ + tree[right].total_count_;
-      tree[j_end].index_left_ = static_cast<int16_t>(left);
-      tree[j_end].index_right_or_value_ = static_cast<int16_t>(right);
-
-      // Add back the last sentinel node.
-      tree[j_end + 1] = sentinel;
-    }
-    SetDepth(tree[2 * n - 1], &tree[0], depth, 0);
-
-    // We need to pack the Huffman tree in tree_limit bits.
-    // If this was not successful, add fake entities to the lowest values
-    // and retry.
-    if (*std::max_element(&depth[0], &depth[length]) <= tree_limit) {
-      break;
-    }
-  }
-}
-
-static void Reverse(uint8_t* v, size_t start, size_t end) {
-  --end;
-  while (start < end) {
-    uint8_t tmp = v[start];
-    v[start] = v[end];
-    v[end] = tmp;
-    ++start;
-    --end;
-  }
-}
-
-static void WriteHuffmanTreeRepetitions(
-    const uint8_t previous_value,
-    const uint8_t value,
-    size_t repetitions,
-    size_t* tree_size,
-    uint8_t* tree,
-    uint8_t* extra_bits_data) {
-  assert(repetitions > 0);
-  if (previous_value != value) {
-    tree[*tree_size] = value;
-    extra_bits_data[*tree_size] = 0;
-    ++(*tree_size);
-    --repetitions;
-  }
-  if (repetitions == 7) {
-    tree[*tree_size] = value;
-    extra_bits_data[*tree_size] = 0;
-    ++(*tree_size);
-    --repetitions;
-  }
-  if (repetitions < 3) {
-    for (size_t i = 0; i < repetitions; ++i) {
-      tree[*tree_size] = value;
-      extra_bits_data[*tree_size] = 0;
-      ++(*tree_size);
-    }
-  } else {
-    repetitions -= 3;
-    size_t start = *tree_size;
-    while (true) {
-      tree[*tree_size] = 16;
-      extra_bits_data[*tree_size] = repetitions & 0x3;
-      ++(*tree_size);
-      repetitions >>= 2;
-      if (repetitions == 0) {
-        break;
-      }
-      --repetitions;
-    }
-    Reverse(tree, start, *tree_size);
-    Reverse(extra_bits_data, start, *tree_size);
-  }
-}
-
-static void WriteHuffmanTreeRepetitionsZeros(
-    size_t repetitions,
-    size_t* tree_size,
-    uint8_t* tree,
-    uint8_t* extra_bits_data) {
-  if (repetitions == 11) {
-    tree[*tree_size] = 0;
-    extra_bits_data[*tree_size] = 0;
-    ++(*tree_size);
-    --repetitions;
-  }
-  if (repetitions < 3) {
-    for (size_t i = 0; i < repetitions; ++i) {
-      tree[*tree_size] = 0;
-      extra_bits_data[*tree_size] = 0;
-      ++(*tree_size);
-    }
-  } else {
-    repetitions -= 3;
-    size_t start = *tree_size;
-    while (true) {
-      tree[*tree_size] = 17;
-      extra_bits_data[*tree_size] = repetitions & 0x7;
-      ++(*tree_size);
-      repetitions >>= 3;
-      if (repetitions == 0) {
-        break;
-      }
-      --repetitions;
-    }
-    Reverse(tree, start, *tree_size);
-    Reverse(extra_bits_data, start, *tree_size);
-  }
-}
-
-void OptimizeHuffmanCountsForRle(size_t length, uint32_t* counts,
-                                 uint8_t* good_for_rle) {
-  size_t nonzero_count = 0;
-  size_t stride;
-  size_t limit;
-  size_t sum;
-  const size_t streak_limit = 1240;
-  // Let's make the Huffman code more compatible with rle encoding.
-  size_t i;
-  for (i = 0; i < length; i++) {
-    if (counts[i]) {
-      ++nonzero_count;
-    }
-  }
-  if (nonzero_count < 16) {
-    return;
-  }
-  while (length != 0 && counts[length - 1] == 0) {
-    --length;
-  }
-  if (length == 0) {
-    return;  // All zeros.
-  }
-  // Now counts[0..length - 1] does not have trailing zeros.
-  {
-    size_t nonzeros = 0;
-    uint32_t smallest_nonzero = 1 << 30;
-    for (i = 0; i < length; ++i) {
-      if (counts[i] != 0) {
-        ++nonzeros;
-        if (smallest_nonzero > counts[i]) {
-          smallest_nonzero = counts[i];
-        }
-      }
-    }
-    if (nonzeros < 5) {
-      // Small histogram will model it well.
-      return;
-    }
-    size_t zeros = length - nonzeros;
-    if (smallest_nonzero < 4) {
-      if (zeros < 6) {
-        for (i = 1; i < length - 1; ++i) {
-          if (counts[i - 1] != 0 && counts[i] == 0 && counts[i + 1] != 0) {
-            counts[i] = 1;
-          }
-        }
-      }
-    }
-    if (nonzeros < 28) {
-      return;
-    }
-  }
-  // 2) Let's mark all population counts that already can be encoded
-  // with an rle code.
-  memset(good_for_rle, 0, length);
-  {
-    // Let's not spoil any of the existing good rle codes.
-    // Mark any seq of 0's that is longer as 5 as a good_for_rle.
-    // Mark any seq of non-0's that is longer as 7 as a good_for_rle.
-    uint32_t symbol = counts[0];
-    size_t step = 0;
-    for (i = 0; i <= length; ++i) {
-      if (i == length || counts[i] != symbol) {
-        if ((symbol == 0 && step >= 5) ||
-            (symbol != 0 && step >= 7)) {
-          size_t k;
-          for (k = 0; k < step; ++k) {
-            good_for_rle[i - k - 1] = 1;
-          }
-        }
-        step = 1;
-        if (i != length) {
-          symbol = counts[i];
-        }
-      } else {
-        ++step;
-      }
-    }
-  }
-  // 3) Let's replace those population counts that lead to more rle codes.
-  // Math here is in 24.8 fixed point representation.
-  stride = 0;
-  limit = 256 * (counts[0] + counts[1] + counts[2]) / 3 + 420;
-  sum = 0;
-  for (i = 0; i <= length; ++i) {
-    if (i == length || good_for_rle[i] ||
-        (i != 0 && good_for_rle[i - 1]) ||
-        (256 * counts[i] - limit + streak_limit) >= 2 * streak_limit) {
-      if (stride >= 4 || (stride >= 3 && sum == 0)) {
-        size_t k;
-        // The stride must end, collapse what we have, if we have enough (4).
-        size_t count = (sum + stride / 2) / stride;
-        if (count == 0) {
-          count = 1;
-        }
-        if (sum == 0) {
-          // Don't make an all zeros stride to be upgraded to ones.
-          count = 0;
-        }
-        for (k = 0; k < stride; ++k) {
-          // We don't want to change value at counts[i],
-          // that is already belonging to the next stride. Thus - 1.
-          counts[i - k - 1] = static_cast<uint32_t>(count);
-        }
-      }
-      stride = 0;
-      sum = 0;
-      if (i < length - 2) {
-        // All interesting strides have a count of at least 4,
-        // at least when non-zeros.
-        limit = 256 * (counts[i] + counts[i + 1] + counts[i + 2]) / 3 + 420;
-      } else if (i < length) {
-        limit = 256 * counts[i];
-      } else {
-        limit = 0;
-      }
-    }
-    ++stride;
-    if (i != length) {
-      sum += counts[i];
-      if (stride >= 4) {
-        limit = (256 * sum + stride / 2) / stride;
-      }
-      if (stride == 4) {
-        limit += 120;
-      }
-    }
-  }
-}
-
-static void DecideOverRleUse(const uint8_t* depth, const size_t length,
-                             bool *use_rle_for_non_zero,
-                             bool *use_rle_for_zero) {
-  size_t total_reps_zero = 0;
-  size_t total_reps_non_zero = 0;
-  size_t count_reps_zero = 1;
-  size_t count_reps_non_zero = 1;
-  for (size_t i = 0; i < length;) {
-    const uint8_t value = depth[i];
-    size_t reps = 1;
-    for (size_t k = i + 1; k < length && depth[k] == value; ++k) {
-      ++reps;
-    }
-    if (reps >= 3 && value == 0) {
-      total_reps_zero += reps;
-      ++count_reps_zero;
-    }
-    if (reps >= 4 && value != 0) {
-      total_reps_non_zero += reps;
-      ++count_reps_non_zero;
-    }
-    i += reps;
-  }
-  *use_rle_for_non_zero = total_reps_non_zero > count_reps_non_zero * 2;
-  *use_rle_for_zero = total_reps_zero > count_reps_zero * 2;
-}
-
-void WriteHuffmanTree(const uint8_t* depth,
-                      size_t length,
-                      size_t* tree_size,
-                      uint8_t* tree,
-                      uint8_t* extra_bits_data) {
-  uint8_t previous_value = 8;
-
-  // Throw away trailing zeros.
-  size_t new_length = length;
-  for (size_t i = 0; i < length; ++i) {
-    if (depth[length - i - 1] == 0) {
-      --new_length;
-    } else {
-      break;
-    }
-  }
-
-  // First gather statistics on if it is a good idea to do rle.
-  bool use_rle_for_non_zero = false;
-  bool use_rle_for_zero = false;
-  if (length > 50) {
-    // Find rle coding for longer codes.
-    // Shorter codes seem not to benefit from rle.
-    DecideOverRleUse(depth, new_length,
-                     &use_rle_for_non_zero, &use_rle_for_zero);
-  }
-
-  // Actual rle coding.
-  for (size_t i = 0; i < new_length;) {
-    const uint8_t value = depth[i];
-    size_t reps = 1;
-    if ((value != 0 && use_rle_for_non_zero) ||
-        (value == 0 && use_rle_for_zero)) {
-      for (size_t k = i + 1; k < new_length && depth[k] == value; ++k) {
-        ++reps;
-      }
-    }
-    if (value == 0) {
-      WriteHuffmanTreeRepetitionsZeros(reps, tree_size, tree, extra_bits_data);
-    } else {
-      WriteHuffmanTreeRepetitions(previous_value,
-                                  value, reps, tree_size,
-                                  tree, extra_bits_data);
-      previous_value = value;
-    }
-    i += reps;
-  }
-}
-
-namespace {
-
-uint16_t ReverseBits(int num_bits, uint16_t bits) {
-  static const size_t kLut[16] = {  // Pre-reversed 4-bit values.
-    0x0, 0x8, 0x4, 0xc, 0x2, 0xa, 0x6, 0xe,
-    0x1, 0x9, 0x5, 0xd, 0x3, 0xb, 0x7, 0xf
-  };
-  size_t retval = kLut[bits & 0xf];
-  for (int i = 4; i < num_bits; i += 4) {
-    retval <<= 4;
-    bits = static_cast<uint16_t>(bits >> 4);
-    retval |= kLut[bits & 0xf];
-  }
-  retval >>= (-num_bits & 0x3);
-  return static_cast<uint16_t>(retval);
-}
-
-}  // namespace
-
-void ConvertBitDepthsToSymbols(const uint8_t *depth,
-                               size_t len,
-                               uint16_t *bits) {
-  // In Brotli, all bit depths are [1..15]
-  // 0 bit depth means that the symbol does not exist.
-  const int kMaxBits = 16;  // 0..15 are values for bits
-  uint16_t bl_count[kMaxBits] = { 0 };
-  {
-    for (size_t i = 0; i < len; ++i) {
-      ++bl_count[depth[i]];
-    }
-    bl_count[0] = 0;
-  }
-  uint16_t next_code[kMaxBits];
-  next_code[0] = 0;
-  {
-    int code = 0;
-    for (int bits = 1; bits < kMaxBits; ++bits) {
-      code = (code + bl_count[bits - 1]) << 1;
-      next_code[bits] = static_cast<uint16_t>(code);
-    }
-  }
-  for (size_t i = 0; i < len; ++i) {
-    if (depth[i]) {
-      bits[i] = ReverseBits(depth[i], next_code[depth[i]]++);
-    }
-  }
-}
-
-}  // namespace brotli