Zoltan Szabadka | 79e99af | 2013-10-23 13:06:13 +0200 | [diff] [blame] | 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_; |
Zoltan Szabadka | 1571db3 | 2013-11-15 19:02:17 +0100 | [diff] [blame] | 69 | // First four symbols with non-zero depth. |
| 70 | int symbols_[4]; |
Zoltan Szabadka | 79e99af | 2013-10-23 13:06:13 +0200 | [diff] [blame] | 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) { |
Zoltan Szabadka | 1571db3 | 2013-11-15 19:02:17 +0100 | [diff] [blame] | 85 | if (code->count_ < 4) code->symbols_[code->count_] = i; |
Zoltan Szabadka | 79e99af | 2013-10-23 13:06:13 +0200 | [diff] [blame] | 86 | ++code->count_; |
| 87 | } |
| 88 | } |
Zoltan Szabadka | cbd5cb5 | 2014-02-14 15:04:23 +0100 | [diff] [blame] | 89 | if (alphabet_size >= 50 && code->count_ >= 16) { |
Zoltan Szabadka | 79e99af | 2013-10-23 13:06:13 +0200 | [diff] [blame] | 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 | |
Zoltan Szabadka | e709491 | 2013-12-12 13:18:04 +0100 | [diff] [blame] | 101 | static const int kCodeLengthCodes = 18; |
Zoltan Szabadka | 79e99af | 2013-10-23 13:06:13 +0200 | [diff] [blame] | 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; |
Zoltan Szabadka | e709491 | 2013-12-12 13:18:04 +0100 | [diff] [blame] | 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; |
Zoltan Szabadka | 79e99af | 2013-10-23 13:06:13 +0200 | [diff] [blame] | 113 | |
| 114 | } // namespace brotli |
| 115 | |
| 116 | #endif // BROTLI_ENC_ENTROPY_ENCODE_H_ |