1 // Copyright 2010 Google Inc. All Rights Reserved.
2 //
3 // Licensed under the Apache License, Version 2.0 (the "License");
4 // you may not use this file except in compliance with the License.
5 // You may obtain a copy of the License at
6 //
7 // http://www.apache.org/licenses/LICENSE-2.0
8 //
9 // Unless required by applicable law or agreed to in writing, software
10 // distributed under the License is distributed on an "AS IS" BASIS,
11 // WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
12 // See the License for the specific language governing permissions and
13 // limitations under the License.
14 //
15 // Entropy encoding (Huffman) utilities.
16
17 #ifndef BROTLI_ENC_ENTROPY_ENCODE_H_
18 #define BROTLI_ENC_ENTROPY_ENCODE_H_
19
20 #include <stdint.h>
21 #include <string.h>
22 #include "./histogram.h"
23 #include "./prefix.h"
24
25 namespace brotli {
26
27 // This function will create a Huffman tree.
28 //
29 // The (data,length) contains the population counts.
30 // The tree_limit is the maximum bit depth of the Huffman codes.
31 //
32 // The depth contains the tree, i.e., how many bits are used for
33 // the symbol.
34 //
35 // See http://en.wikipedia.org/wiki/Huffman_coding
36 void CreateHuffmanTree(const int *data,
37 const int length,
38 const int tree_limit,
39 uint8_t *depth);
40
41 // Change the population counts in a way that the consequent
42 // Hufmann tree compression, especially its rle-part will be more
43 // likely to compress this data more efficiently.
44 //
45 // length contains the size of the histogram.
46 // counts contains the population counts.
47 int OptimizeHuffmanCountsForRle(int length, int* counts);
48
49
50 // Write a huffman tree from bit depths into the bitstream representation
51 // of a Huffman tree. The generated Huffman tree is to be compressed once
52 // more using a Huffman tree
53 void WriteHuffmanTree(const uint8_t* depth, const int length,
54 uint8_t* tree,
55 uint8_t* extra_bits_data,
56 int* huffman_tree_size);
57
58 // Get the actual bit values for a tree of bit depths.
59 void ConvertBitDepthsToSymbols(const uint8_t *depth, int len, uint16_t *bits);
60
61 template<int kSize>
62 struct EntropyCode {
63 // How many bits for symbol.
64 uint8_t depth_[kSize];
65 // Actual bits used to represent the symbol.
66 uint16_t bits_[kSize];
67 // How many non-zero depth.
68 int count_;
69 // First four symbols with non-zero depth.
70 int symbols_[4];
71 };
72
73 template<int kSize>
BuildEntropyCode(const Histogram<kSize> & histogram,const int tree_limit,const int alphabet_size,EntropyCode<kSize> * code)74 void BuildEntropyCode(const Histogram<kSize>& histogram,
75 const int tree_limit,
76 const int alphabet_size,
77 EntropyCode<kSize>* code) {
78 memset(code->depth_, 0, sizeof(code->depth_));
79 memset(code->bits_, 0, sizeof(code->bits_));
80 memset(code->symbols_, 0, sizeof(code->symbols_));
81 code->count_ = 0;
82 if (histogram.total_count_ == 0) return;
83 for (int i = 0; i < kSize; ++i) {
84 if (histogram.data_[i] > 0) {
85 if (code->count_ < 4) code->symbols_[code->count_] = i;
86 ++code->count_;
87 }
88 }
89 if (alphabet_size >= 50 && code->count_ >= 16) {
90 int counts[kSize];
91 memcpy(counts, &histogram.data_[0], sizeof(counts[0]) * kSize);
92 OptimizeHuffmanCountsForRle(alphabet_size, counts);
93 CreateHuffmanTree(counts, alphabet_size, tree_limit, &code->depth_[0]);
94 } else {
95 CreateHuffmanTree(&histogram.data_[0], alphabet_size, tree_limit,
96 &code->depth_[0]);
97 }
98 ConvertBitDepthsToSymbols(&code->depth_[0], alphabet_size, &code->bits_[0]);
99 }
100
101 static const int kCodeLengthCodes = 18;
102
103 // Literal entropy code.
104 typedef EntropyCode<256> EntropyCodeLiteral;
105 // Prefix entropy codes.
106 typedef EntropyCode<kNumCommandPrefixes> EntropyCodeCommand;
107 typedef EntropyCode<kNumDistancePrefixes> EntropyCodeDistance;
108 typedef EntropyCode<kNumBlockLenPrefixes> EntropyCodeBlockLength;
109 // Context map entropy code, 256 Huffman tree indexes + 16 run length codes.
110 typedef EntropyCode<272> EntropyCodeContextMap;
111 // Block type entropy code, 256 block types + 2 special symbols.
112 typedef EntropyCode<258> EntropyCodeBlockType;
113
114 } // namespace brotli
115
116 #endif // BROTLI_ENC_ENTROPY_ENCODE_H_
117