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> 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
