huffman.h (2005B)
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 #ifndef LIB_JPEGLI_HUFFMAN_H_ 7 #define LIB_JPEGLI_HUFFMAN_H_ 8 9 #include <stdint.h> 10 #include <stdlib.h> 11 12 #include "lib/jpegli/common_internal.h" 13 14 namespace jpegli { 15 16 constexpr int kJpegHuffmanRootTableBits = 8; 17 // Maximum huffman lookup table size. 18 // Requirements: alphabet of 257 symbols (256 + 1 special symbol for the all 1s 19 // code) and max bit length 16, the root table has 8 bits. 20 // zlib/examples/enough.c works with an assumption that Huffman code is 21 // "complete". Input JPEGs might have this assumption broken, hence the 22 // following sum is used as estimate: 23 // + number of 1-st level cells 24 // + number of symbols 25 // + asymptotic amount of repeated 2nd level cells 26 // The third number is 1 + 3 + ... + 255 i.e. it is assumed that sub-table of 27 // each "size" might be almost completely be filled with repetitions. 28 // Total sum is slightly less than 1024,... 29 constexpr int kJpegHuffmanLutSize = 1024; 30 31 struct HuffmanTableEntry { 32 uint8_t bits; // number of bits used for this symbol 33 uint16_t value; // symbol value or table offset 34 }; 35 36 void BuildJpegHuffmanTable(const uint32_t* count, const uint32_t* symbols, 37 HuffmanTableEntry* lut); 38 39 // This function will create a Huffman tree. 40 // 41 // The (data,length) contains the population counts. 42 // The tree_limit is the maximum bit depth of the Huffman codes. 43 // 44 // The depth contains the tree, i.e., how many bits are used for 45 // the symbol. 46 // 47 // See http://en.wikipedia.org/wiki/Huffman_coding 48 void CreateHuffmanTree(const uint32_t* data, size_t length, int tree_limit, 49 uint8_t* depth); 50 51 void ValidateHuffmanTable(j_common_ptr cinfo, const JHUFF_TBL* table, 52 bool is_dc); 53 54 void AddStandardHuffmanTables(j_common_ptr cinfo, bool is_dc); 55 56 } // namespace jpegli 57 58 #endif // LIB_JPEGLI_HUFFMAN_H_