+++ /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/platform.h"\r
-#include <brotli/types.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
- BROTLI_DCHECK(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
- BROTLI_DCHECK(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
- 0x00, 0x08, 0x04, 0x0C, 0x02, 0x0A, 0x06, 0x0E,\r
- 0x01, 0x09, 0x05, 0x0D, 0x03, 0x0B, 0x07, 0x0F\r
- };\r
- size_t retval = kLut[bits & 0x0F];\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 & 0x0F];\r
- }\r
- retval >>= ((0 - num_bits) & 0x03);\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