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* ); |
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_ */ |
123 | |