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