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 25namespace 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 36void 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. 47int 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 53void 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. 59void ConvertBitDepthsToSymbols(const uint8_t *depth, int len, uint16_t *bits); 60 61template<int kSize> 62struct 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 73template<int kSize> 74void 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 101static const int kCodeLengthCodes = 18; 102 103// Literal entropy code. 104typedef EntropyCode<256> EntropyCodeLiteral; 105// Prefix entropy codes. 106typedef EntropyCode<kNumCommandPrefixes> EntropyCodeCommand; 107typedef EntropyCode<kNumDistancePrefixes> EntropyCodeDistance; 108typedef EntropyCode<kNumBlockLenPrefixes> EntropyCodeBlockLength; 109// Context map entropy code, 256 Huffman tree indexes + 16 run length codes. 110typedef EntropyCode<272> EntropyCodeContextMap; 111// Block type entropy code, 256 block types + 2 special symbols. 112typedef EntropyCode<258> EntropyCodeBlockType; 113 114} // namespace brotli 115 116#endif // BROTLI_ENC_ENTROPY_ENCODE_H_ 117