blob: 02700a35595abe76697c9861d9e3288e43b1a7fc [file] [log] [blame]
 /* Copyright 2010 Google Inc. All Rights Reserved. Distributed under MIT license. See file LICENSE for detail or copy at https://opensource.org/licenses/MIT */ // Entropy encoding (Huffman) utilities. #ifndef BROTLI_ENC_ENTROPY_ENCODE_H_ #define BROTLI_ENC_ENTROPY_ENCODE_H_ #include #include #include "./histogram.h" #include "./prefix.h" #include "./types.h" namespace brotli { // This function will create a Huffman tree. // // The (data,length) contains the population counts. // The tree_limit is the maximum bit depth of the Huffman codes. // // The depth contains the tree, i.e., how many bits are used for // the symbol. // // See http://en.wikipedia.org/wiki/Huffman_coding void CreateHuffmanTree(const int *data, const int length, const int tree_limit, uint8_t *depth); // Change the population counts in a way that the consequent // Huffman tree compression, especially its rle-part will be more // likely to compress this data more efficiently. // // length contains the size of the histogram. // counts contains the population counts. int OptimizeHuffmanCountsForRle(int length, int* counts); // Write a Huffman tree from bit depths into the bitstream representation // of a Huffman tree. The generated Huffman tree is to be compressed once // more using a Huffman tree void WriteHuffmanTree(const uint8_t* depth, uint32_t num, std::vector *tree, std::vector *extra_bits_data); // Get the actual bit values for a tree of bit depths. void ConvertBitDepthsToSymbols(const uint8_t *depth, int len, uint16_t *bits); template struct EntropyCode { // How many bits for symbol. uint8_t depth_[kSize]; // Actual bits used to represent the symbol. uint16_t bits_[kSize]; // How many non-zero depth. int count_; // First four symbols with non-zero depth. int symbols_[4]; }; static const int kCodeLengthCodes = 18; // Literal entropy code. typedef EntropyCode<256> EntropyCodeLiteral; // Prefix entropy codes. typedef EntropyCode EntropyCodeCommand; typedef EntropyCode EntropyCodeDistance; typedef EntropyCode EntropyCodeBlockLength; // Context map entropy code, 256 Huffman tree indexes + 16 run length codes. typedef EntropyCode<272> EntropyCodeContextMap; // Block type entropy code, 256 block types + 2 special symbols. typedef EntropyCode<258> EntropyCodeBlockType; } // namespace brotli #endif // BROTLI_ENC_ENTROPY_ENCODE_H_