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 // Utility function for building a Huffman lookup table for the jpeg decoder.
7 
8 #ifndef LIB_JXL_JPEG_ENC_JPEG_HUFFMAN_DECODE_H_
9 #define LIB_JXL_JPEG_ENC_JPEG_HUFFMAN_DECODE_H_
10 
11 #include <stdint.h>
12 
13 namespace jxl {
14 namespace jpeg {
15 
16 constexpr int kJpegHuffmanRootTableBits = 8;
17 // Maximum huffman lookup table size.
18 // According to zlib/examples/enough.c, 758 entries are always enough for
19 // an alphabet of 257 symbols (256 + 1 special symbol for the all 1s code) and
20 // max bit length 16 if the root table has 8 bits.
21 constexpr int kJpegHuffmanLutSize = 758;
22 
23 struct HuffmanTableEntry {
24   // Initialize the value to an invalid symbol so that we can recognize it
25   // when reading the bit stream using a Huffman code with space > 0.
HuffmanTableEntryHuffmanTableEntry26   HuffmanTableEntry() : bits(0), value(0xffff) {}
27 
28   uint8_t bits;    // number of bits used for this symbol
29   uint16_t value;  // symbol value or table offset
30 };
31 
32 // Builds jpeg-style Huffman lookup table from the given symbols.
33 // The symbols are in order of increasing bit lengths. The number of symbols
34 // with bit length n is given in counts[n] for each n >= 1.
35 void BuildJpegHuffmanTable(const uint32_t* counts, const uint32_t* symbols,
36                            HuffmanTableEntry* lut);
37 
38 }  // namespace jpeg
39 }  // namespace jxl
40 
41 #endif  // LIB_JXL_JPEG_ENC_JPEG_HUFFMAN_DECODE_H_
42