diff options
Diffstat (limited to 'modules/brotli/enc/entropy_encode.c')
| -rw-r--r-- | modules/brotli/enc/entropy_encode.c | 503 |
1 files changed, 503 insertions, 0 deletions
diff --git a/modules/brotli/enc/entropy_encode.c b/modules/brotli/enc/entropy_encode.c new file mode 100644 index 0000000000..b50ccb5d1f --- /dev/null +++ b/modules/brotli/enc/entropy_encode.c @@ -0,0 +1,503 @@ +/* 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 <string.h> /* memset */ + +#include "../common/constants.h" +#include "../common/platform.h" +#include <brotli/types.h> + +#if defined(__cplusplus) || defined(c_plusplus) +extern "C" { +#endif + +const size_t kBrotliShellGaps[] = {132, 57, 23, 10, 4, 1}; + +BROTLI_BOOL BrotliSetDepth( + int p0, HuffmanTree* pool, uint8_t* depth, int max_depth) { + int stack[16]; + int level = 0; + int p = p0; + BROTLI_DCHECK(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 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 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 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; + size_t i; + size_t j; + size_t k; + for (i = length; i != 0;) { + --i; + if (data[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. */ + break; + } + + 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. */ + tree[n] = sentinel; + tree[n + 1] = sentinel; + + 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; + ++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_ = (int16_t)left; + tree[j_end].index_right_or_value_ = (int16_t)right; + + /* Add back the last sentinel node. */ + tree[j_end + 1] = sentinel; + } + } + 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; + } + } +} + +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 BrotliWriteHuffmanTreeRepetitions( + const uint8_t previous_value, + const uint8_t value, + size_t repetitions, + size_t* tree_size, + uint8_t* tree, + uint8_t* extra_bits_data) { + BROTLI_DCHECK(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) { + size_t i; + for (i = 0; i < repetitions; ++i) { + tree[*tree_size] = value; + extra_bits_data[*tree_size] = 0; + ++(*tree_size); + } + } else { + size_t start = *tree_size; + repetitions -= 3; + while (BROTLI_TRUE) { + tree[*tree_size] = BROTLI_REPEAT_PREVIOUS_CODE_LENGTH; + 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 BrotliWriteHuffmanTreeRepetitionsZeros( + 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) { + size_t i; + for (i = 0; i < repetitions; ++i) { + tree[*tree_size] = 0; + extra_bits_data[*tree_size] = 0; + ++(*tree_size); + } + } else { + size_t start = *tree_size; + repetitions -= 3; + while (BROTLI_TRUE) { + tree[*tree_size] = BROTLI_REPEAT_ZERO_CODE_LENGTH; + 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 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. */ + 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; + } + 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) { + 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] = (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, + 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; + size_t i; + for (i = 0; i < length;) { + const uint8_t value = depth[i]; + size_t reps = 1; + size_t k; + for (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 = + 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 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. */ + size_t new_length = length; + for (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. */ + 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 (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)) { + size_t k; + for (k = i + 1; k < new_length && depth[k] == value; ++k) { + ++reps; + } + } + if (value == 0) { + BrotliWriteHuffmanTreeRepetitionsZeros( + reps, tree_size, tree, extra_bits_data); + } else { + BrotliWriteHuffmanTreeRepetitions(previous_value, + value, reps, tree_size, + tree, extra_bits_data); + previous_value = value; + } + i += reps; + } +} + +static uint16_t BrotliReverseBits(size_t num_bits, uint16_t bits) { + static const size_t kLut[16] = { /* Pre-reversed 4-bit values. */ + 0x00, 0x08, 0x04, 0x0C, 0x02, 0x0A, 0x06, 0x0E, + 0x01, 0x09, 0x05, 0x0D, 0x03, 0x0B, 0x07, 0x0F + }; + size_t retval = kLut[bits & 0x0F]; + size_t i; + for (i = 4; i < num_bits; i += 4) { + retval <<= 4; + bits = (uint16_t)(bits >> 4); + retval |= kLut[bits & 0x0F]; + } + retval >>= ((0 - num_bits) & 0x03); + return (uint16_t)retval; +} + +/* 0..15 are values for bits */ +#define MAX_HUFFMAN_BITS 16 + +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]]; + } + bl_count[0] = 0; + next_code[0] = 0; + for (i = 1; i < MAX_HUFFMAN_BITS; ++i) { + code = (code + bl_count[i - 1]) << 1; + next_code[i] = (uint16_t)code; + } + for (i = 0; i < len; ++i) { + if (depth[i]) { + bits[i] = BrotliReverseBits(depth[i], next_code[depth[i]]++); + } + } +} + +#if defined(__cplusplus) || defined(c_plusplus) +} /* extern "C" */ +#endif |