Index: third_party/brotli/enc/entropy_encode.c |
diff --git a/third_party/brotli/enc/entropy_encode.cc b/third_party/brotli/enc/entropy_encode.c |
similarity index 44% |
rename from third_party/brotli/enc/entropy_encode.cc |
rename to third_party/brotli/enc/entropy_encode.c |
index f18355d88db5a3cf7a1b85ea500210b59765ef85..41ea9483d19e966855d83466831abf6fd937e554 100644 |
--- a/third_party/brotli/enc/entropy_encode.cc |
+++ b/third_party/brotli/enc/entropy_encode.c |
@@ -4,97 +4,113 @@ |
See file LICENSE for detail or copy at https://opensource.org/licenses/MIT |
*/ |
-// Entropy encoding (Huffman) utilities. |
+/* Entropy encoding (Huffman) utilities. */ |
#include "./entropy_encode.h" |
-#include <algorithm> |
-#include <limits> |
-#include <cstdlib> |
+#include <string.h> /* memset */ |
-#include "./histogram.h" |
+#include "../common/constants.h" |
+#include <brotli/types.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; |
+ |
+#if defined(__cplusplus) || defined(c_plusplus) |
+extern "C" { |
+#endif |
+ |
+BROTLI_BOOL BrotliSetDepth( |
+ int p0, HuffmanTree* pool, uint8_t* depth, int max_depth) { |
+ int stack[16]; |
+ int level = 0; |
+ int p = p0; |
+ assert(max_depth <= 15); |
+ stack[0] = -1; |
+ while (BROTLI_TRUE) { |
+ if (pool[p].index_left_ >= 0) { |
+ level++; |
+ if (level > max_depth) return BROTLI_FALSE; |
+ stack[level] = pool[p].index_right_or_value_; |
+ p = pool[p].index_left_; |
+ continue; |
+ } else { |
+ depth[pool[p].index_right_or_value_] = (uint8_t)level; |
+ } |
+ while (level >= 0 && stack[level] == -1) level--; |
+ if (level < 0) return BROTLI_TRUE; |
+ p = stack[level]; |
+ stack[level] = -1; |
} |
} |
-// 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_; |
+/* Sort the root nodes, least popular first. */ |
+static BROTLI_INLINE BROTLI_BOOL SortHuffmanTree( |
+ const HuffmanTree* v0, const HuffmanTree* v1) { |
+ if (v0->total_count_ != v1->total_count_) { |
+ return TO_BROTLI_BOOL(v0->total_count_ < v1->total_count_); |
} |
- return v0.index_right_or_value_ > v1.index_right_or_value_; |
+ return TO_BROTLI_BOOL(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) { |
+/* 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 BrotliCreateHuffmanTree(const uint32_t *data, |
+ const size_t length, |
+ const int tree_limit, |
+ HuffmanTree* tree, |
+ uint8_t *depth) { |
+ uint32_t count_limit; |
+ HuffmanTree sentinel; |
+ InitHuffmanTree(&sentinel, BROTLI_UINT32_MAX, -1, -1); |
+ /* 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 (count_limit = 1; ; count_limit *= 2) { |
size_t n = 0; |
- for (size_t i = length; i != 0;) { |
+ size_t i; |
+ size_t j; |
+ size_t k; |
+ for (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)); |
+ const uint32_t count = BROTLI_MAX(uint32_t, data[i], count_limit); |
+ InitHuffmanTree(&tree[n++], count, -1, (int16_t)i); |
} |
} |
if (n == 1) { |
- depth[tree[0].index_right_or_value_] = 1; // Only one element. |
+ depth[tree[0].index_right_or_value_] = 1; /* Only one element. */ |
break; |
} |
- std::sort(tree, tree + n, SortHuffmanTree); |
+ SortHuffmanTreeItems(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); |
+ /* 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. */ |
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) { |
+ i = 0; /* Points to the next leaf node. */ |
+ j = n + 1; /* Points to the next non-leaf node. */ |
+ for (k = n - 1; k != 0; --k) { |
size_t left, right; |
if (tree[i].total_count_ <= tree[j].total_count_) { |
left = i; |
@@ -111,22 +127,21 @@ void CreateHuffmanTree(const uint32_t *data, |
++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); |
+ { |
+ /* 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_ = (int16_t)left; |
+ tree[j_end].index_right_or_value_ = (int16_t)right; |
- // Add back the last sentinel node. |
- tree[j_end + 1] = sentinel; |
+ /* 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) { |
+ if (BrotliSetDepth((int)(2 * n - 1), &tree[0], depth, tree_limit)) { |
+ /* 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. */ |
break; |
} |
} |
@@ -143,7 +158,7 @@ static void Reverse(uint8_t* v, size_t start, size_t end) { |
} |
} |
-static void WriteHuffmanTreeRepetitions( |
+static void BrotliWriteHuffmanTreeRepetitions( |
const uint8_t previous_value, |
const uint8_t value, |
size_t repetitions, |
@@ -164,16 +179,17 @@ static void WriteHuffmanTreeRepetitions( |
--repetitions; |
} |
if (repetitions < 3) { |
- for (size_t i = 0; i < repetitions; ++i) { |
+ size_t i; |
+ for (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; |
+ repetitions -= 3; |
+ while (BROTLI_TRUE) { |
+ tree[*tree_size] = BROTLI_REPEAT_PREVIOUS_CODE_LENGTH; |
extra_bits_data[*tree_size] = repetitions & 0x3; |
++(*tree_size); |
repetitions >>= 2; |
@@ -187,7 +203,7 @@ static void WriteHuffmanTreeRepetitions( |
} |
} |
-static void WriteHuffmanTreeRepetitionsZeros( |
+static void BrotliWriteHuffmanTreeRepetitionsZeros( |
size_t repetitions, |
size_t* tree_size, |
uint8_t* tree, |
@@ -199,16 +215,17 @@ static void WriteHuffmanTreeRepetitionsZeros( |
--repetitions; |
} |
if (repetitions < 3) { |
- for (size_t i = 0; i < repetitions; ++i) { |
+ size_t i; |
+ for (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; |
+ repetitions -= 3; |
+ while (BROTLI_TRUE) { |
+ tree[*tree_size] = BROTLI_REPEAT_ZERO_CODE_LENGTH; |
extra_bits_data[*tree_size] = repetitions & 0x7; |
++(*tree_size); |
repetitions >>= 3; |
@@ -222,14 +239,14 @@ static void WriteHuffmanTreeRepetitionsZeros( |
} |
} |
-void OptimizeHuffmanCountsForRle(size_t length, uint32_t* counts, |
- uint8_t* good_for_rle) { |
+void BrotliOptimizeHuffmanCountsForRle(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. |
+ /* Let's make the Huffman code more compatible with RLE encoding. */ |
size_t i; |
for (i = 0; i < length; i++) { |
if (counts[i]) { |
@@ -243,9 +260,9 @@ void OptimizeHuffmanCountsForRle(size_t length, uint32_t* counts, |
--length; |
} |
if (length == 0) { |
- return; // All zeros. |
+ return; /* All zeros. */ |
} |
- // Now counts[0..length - 1] does not have trailing zeros. |
+ /* Now counts[0..length - 1] does not have trailing zeros. */ |
{ |
size_t nonzeros = 0; |
uint32_t smallest_nonzero = 1 << 30; |
@@ -258,11 +275,11 @@ void OptimizeHuffmanCountsForRle(size_t length, uint32_t* counts, |
} |
} |
if (nonzeros < 5) { |
- // Small histogram will model it well. |
+ /* Small histogram will model it well. */ |
return; |
} |
- size_t zeros = length - nonzeros; |
if (smallest_nonzero < 4) { |
+ size_t zeros = length - nonzeros; |
if (zeros < 6) { |
for (i = 1; i < length - 1; ++i) { |
if (counts[i - 1] != 0 && counts[i] == 0 && counts[i + 1] != 0) { |
@@ -275,13 +292,13 @@ void OptimizeHuffmanCountsForRle(size_t length, uint32_t* counts, |
return; |
} |
} |
- // 2) Let's mark all population counts that already can be encoded |
- // with an rle code. |
+ /* 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. |
+ /* 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) { |
@@ -302,8 +319,8 @@ void OptimizeHuffmanCountsForRle(size_t length, uint32_t* counts, |
} |
} |
} |
- // 3) Let's replace those population counts that lead to more rle codes. |
- // Math here is in 24.8 fixed point representation. |
+ /* 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; |
@@ -313,26 +330,26 @@ void OptimizeHuffmanCountsForRle(size_t length, uint32_t* counts, |
(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). |
+ /* 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. |
+ /* 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); |
+ /* We don't want to change value at counts[i], |
+ that is already belonging to the next stride. Thus - 1. */ |
+ counts[i - k - 1] = (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. |
+ /* 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]; |
@@ -354,16 +371,18 @@ void OptimizeHuffmanCountsForRle(size_t length, uint32_t* counts, |
} |
static void DecideOverRleUse(const uint8_t* depth, const size_t length, |
- bool *use_rle_for_non_zero, |
- bool *use_rle_for_zero) { |
+ BROTLI_BOOL *use_rle_for_non_zero, |
+ BROTLI_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;) { |
+ size_t i; |
+ for (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) { |
+ size_t k; |
+ for (k = i + 1; k < length && depth[k] == value; ++k) { |
++reps; |
} |
if (reps >= 3 && value == 0) { |
@@ -376,20 +395,24 @@ static void DecideOverRleUse(const uint8_t* depth, const size_t length, |
} |
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; |
+ *use_rle_for_non_zero = |
+ TO_BROTLI_BOOL(total_reps_non_zero > count_reps_non_zero * 2); |
+ *use_rle_for_zero = TO_BROTLI_BOOL(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; |
+void BrotliWriteHuffmanTree(const uint8_t* depth, |
+ size_t length, |
+ size_t* tree_size, |
+ uint8_t* tree, |
+ uint8_t* extra_bits_data) { |
+ uint8_t previous_value = BROTLI_INITIAL_REPEATED_CODE_LENGTH; |
+ size_t i; |
+ BROTLI_BOOL use_rle_for_non_zero = BROTLI_FALSE; |
+ BROTLI_BOOL use_rle_for_zero = BROTLI_FALSE; |
- // Throw away trailing zeros. |
+ /* Throw away trailing zeros. */ |
size_t new_length = length; |
- for (size_t i = 0; i < length; ++i) { |
+ for (i = 0; i < length; ++i) { |
if (depth[length - i - 1] == 0) { |
--new_length; |
} else { |
@@ -397,84 +420,82 @@ void WriteHuffmanTree(const uint8_t* depth, |
} |
} |
- // 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; |
+ /* First gather statistics on if it is a good idea to do RLE. */ |
if (length > 50) { |
- // Find rle coding for longer codes. |
- // Shorter codes seem not to benefit from rle. |
+ /* 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;) { |
+ /* Actual RLE coding. */ |
+ for (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) { |
+ size_t k; |
+ for (k = i + 1; k < new_length && depth[k] == value; ++k) { |
++reps; |
} |
} |
if (value == 0) { |
- WriteHuffmanTreeRepetitionsZeros(reps, tree_size, tree, extra_bits_data); |
+ BrotliWriteHuffmanTreeRepetitionsZeros( |
+ reps, tree_size, tree, extra_bits_data); |
} else { |
- WriteHuffmanTreeRepetitions(previous_value, |
- value, reps, tree_size, |
- tree, extra_bits_data); |
+ BrotliWriteHuffmanTreeRepetitions(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. |
+static uint16_t BrotliReverseBits(size_t 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) { |
+ size_t i; |
+ for (i = 4; i < num_bits; i += 4) { |
retval <<= 4; |
- bits = static_cast<uint16_t>(bits >> 4); |
+ bits = (uint16_t)(bits >> 4); |
retval |= kLut[bits & 0xf]; |
} |
- retval >>= (-num_bits & 0x3); |
- return static_cast<uint16_t>(retval); |
+ retval >>= ((0 - num_bits) & 0x3); |
+ return (uint16_t)retval; |
} |
-} // namespace |
+/* 0..15 are values for bits */ |
+#define MAX_HUFFMAN_BITS 16 |
-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; |
+void BrotliConvertBitDepthsToSymbols(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. */ |
+ uint16_t bl_count[MAX_HUFFMAN_BITS] = { 0 }; |
+ uint16_t next_code[MAX_HUFFMAN_BITS]; |
+ size_t i; |
+ int code = 0; |
+ for (i = 0; i < len; ++i) { |
+ ++bl_count[depth[i]]; |
} |
- uint16_t next_code[kMaxBits]; |
+ bl_count[0] = 0; |
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 (i = 1; i < MAX_HUFFMAN_BITS; ++i) { |
+ code = (code + bl_count[i - 1]) << 1; |
+ next_code[i] = (uint16_t)code; |
} |
- for (size_t i = 0; i < len; ++i) { |
+ for (i = 0; i < len; ++i) { |
if (depth[i]) { |
- bits[i] = ReverseBits(depth[i], next_code[depth[i]]++); |
+ bits[i] = BrotliReverseBits(depth[i], next_code[depth[i]]++); |
} |
} |
} |
-} // namespace brotli |
+#if defined(__cplusplus) || defined(c_plusplus) |
+} /* extern "C" */ |
+#endif |