enc_huffman_tree.h (1696B)
1 // Copyright (c) the JPEG XL Project Authors. All rights reserved. 2 // 3 // Use of this source code is governed by a BSD-style 4 // license that can be found in the LICENSE file. 5 6 // Library for creating Huffman codes from population counts. 7 8 #ifndef LIB_JXL_HUFFMAN_TREE_H_ 9 #define LIB_JXL_HUFFMAN_TREE_H_ 10 11 #include <stdint.h> 12 #include <stdlib.h> 13 14 namespace jxl { 15 16 // A node of a Huffman tree. 17 struct HuffmanTree { 18 HuffmanTree(uint32_t count, int16_t left, int16_t right) 19 : total_count(count), index_left(left), index_right_or_value(right) {} 20 uint32_t total_count; 21 int16_t index_left; 22 int16_t index_right_or_value; 23 }; 24 25 void SetDepth(const HuffmanTree& p, HuffmanTree* pool, uint8_t* depth, 26 uint8_t level); 27 28 // This function will create a Huffman tree. 29 // 30 // The (data,length) contains the population counts. 31 // The tree_limit is the maximum bit depth of the Huffman codes. 32 // 33 // The depth contains the tree, i.e., how many bits are used for 34 // the symbol. 35 // 36 // See http://en.wikipedia.org/wiki/Huffman_coding 37 void CreateHuffmanTree(const uint32_t* data, size_t length, int tree_limit, 38 uint8_t* depth); 39 40 // Write a Huffman tree from bit depths into the bitstream representation 41 // of a Huffman tree. The generated Huffman tree is to be compressed once 42 // more using a Huffman tree 43 void WriteHuffmanTree(const uint8_t* depth, size_t length, size_t* tree_size, 44 uint8_t* tree, uint8_t* extra_bits_data); 45 46 // Get the actual bit values for a tree of bit depths. 47 void ConvertBitDepthsToSymbols(const uint8_t* depth, size_t len, 48 uint16_t* bits); 49 50 } // namespace jxl 51 52 #endif // LIB_JXL_HUFFMAN_TREE_H_