Mike Fleming | 3933d92 | 2018-04-02 10:53:08 -0700 | [diff] [blame] | 1 | /* Copyright 2010 Google Inc. All Rights Reserved. |
| 2 | |
| 3 | Distributed under MIT license. |
| 4 | See file LICENSE for detail or copy at https://opensource.org/licenses/MIT |
| 5 | */ |
| 6 | |
| 7 | /* Entropy encoding (Huffman) utilities. */ |
| 8 | |
| 9 | #ifndef BROTLI_ENC_ENTROPY_ENCODE_H_ |
| 10 | #define BROTLI_ENC_ENTROPY_ENCODE_H_ |
| 11 | |
| 12 | #include "../common/platform.h" |
| 13 | #include <brotli/types.h> |
| 14 | |
| 15 | #if defined(__cplusplus) || defined(c_plusplus) |
| 16 | extern "C" { |
| 17 | #endif |
| 18 | |
| 19 | /* A node of a Huffman tree. */ |
| 20 | typedef struct HuffmanTree { |
| 21 | uint32_t total_count_; |
| 22 | int16_t index_left_; |
| 23 | int16_t index_right_or_value_; |
| 24 | } HuffmanTree; |
| 25 | |
| 26 | static BROTLI_INLINE void InitHuffmanTree(HuffmanTree* self, uint32_t count, |
| 27 | int16_t left, int16_t right) { |
| 28 | self->total_count_ = count; |
| 29 | self->index_left_ = left; |
| 30 | self->index_right_or_value_ = right; |
| 31 | } |
| 32 | |
| 33 | /* Returns 1 is assignment of depths succeeded, otherwise 0. */ |
| 34 | BROTLI_INTERNAL BROTLI_BOOL BrotliSetDepth( |
| 35 | int p, HuffmanTree* pool, uint8_t* depth, int max_depth); |
| 36 | |
| 37 | /* This function will create a Huffman tree. |
| 38 | |
| 39 | The (data,length) contains the population counts. |
| 40 | The tree_limit is the maximum bit depth of the Huffman codes. |
| 41 | |
| 42 | The depth contains the tree, i.e., how many bits are used for |
| 43 | the symbol. |
| 44 | |
| 45 | The actual Huffman tree is constructed in the tree[] array, which has to |
| 46 | be at least 2 * length + 1 long. |
| 47 | |
| 48 | See http://en.wikipedia.org/wiki/Huffman_coding */ |
| 49 | BROTLI_INTERNAL void BrotliCreateHuffmanTree(const uint32_t *data, |
| 50 | const size_t length, |
| 51 | const int tree_limit, |
| 52 | HuffmanTree* tree, |
| 53 | uint8_t *depth); |
| 54 | |
| 55 | /* Change the population counts in a way that the consequent |
| 56 | Huffman tree compression, especially its RLE-part will be more |
| 57 | likely to compress this data more efficiently. |
| 58 | |
| 59 | length contains the size of the histogram. |
| 60 | counts contains the population counts. |
| 61 | good_for_rle is a buffer of at least length size */ |
| 62 | BROTLI_INTERNAL void BrotliOptimizeHuffmanCountsForRle( |
| 63 | size_t length, uint32_t* counts, uint8_t* good_for_rle); |
| 64 | |
| 65 | /* Write a Huffman tree from bit depths into the bit-stream representation |
| 66 | of a Huffman tree. The generated Huffman tree is to be compressed once |
| 67 | more using a Huffman tree */ |
| 68 | BROTLI_INTERNAL void BrotliWriteHuffmanTree(const uint8_t* depth, |
| 69 | size_t num, |
| 70 | size_t* tree_size, |
| 71 | uint8_t* tree, |
| 72 | uint8_t* extra_bits_data); |
| 73 | |
| 74 | /* Get the actual bit values for a tree of bit depths. */ |
| 75 | BROTLI_INTERNAL void BrotliConvertBitDepthsToSymbols(const uint8_t *depth, |
| 76 | size_t len, |
| 77 | uint16_t *bits); |
| 78 | |
| 79 | /* Input size optimized Shell sort. */ |
| 80 | typedef BROTLI_BOOL (*HuffmanTreeComparator)( |
| 81 | const HuffmanTree*, const HuffmanTree*); |
| 82 | static BROTLI_INLINE void SortHuffmanTreeItems(HuffmanTree* items, |
| 83 | const size_t n, HuffmanTreeComparator comparator) { |
| 84 | static const size_t gaps[] = {132, 57, 23, 10, 4, 1}; |
| 85 | if (n < 13) { |
| 86 | /* Insertion sort. */ |
| 87 | size_t i; |
| 88 | for (i = 1; i < n; ++i) { |
| 89 | HuffmanTree tmp = items[i]; |
| 90 | size_t k = i; |
| 91 | size_t j = i - 1; |
| 92 | while (comparator(&tmp, &items[j])) { |
| 93 | items[k] = items[j]; |
| 94 | k = j; |
| 95 | if (!j--) break; |
| 96 | } |
| 97 | items[k] = tmp; |
| 98 | } |
| 99 | return; |
| 100 | } else { |
| 101 | /* Shell sort. */ |
| 102 | int g = n < 57 ? 2 : 0; |
| 103 | for (; g < 6; ++g) { |
| 104 | size_t gap = gaps[g]; |
| 105 | size_t i; |
| 106 | for (i = gap; i < n; ++i) { |
| 107 | size_t j = i; |
| 108 | HuffmanTree tmp = items[i]; |
| 109 | for (; j >= gap && comparator(&tmp, &items[j - gap]); j -= gap) { |
| 110 | items[j] = items[j - gap]; |
| 111 | } |
| 112 | items[j] = tmp; |
| 113 | } |
| 114 | } |
| 115 | } |
| 116 | } |
| 117 | |
| 118 | #if defined(__cplusplus) || defined(c_plusplus) |
| 119 | } /* extern "C" */ |
| 120 | #endif |
| 121 | |
| 122 | #endif /* BROTLI_ENC_ENTROPY_ENCODE_H_ */ |