| 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 |
// 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 |
// Initialize the value to an invalid symbol so that we can recognize it |
| 33 |
// when reading the bit stream using a Huffman code with space > 0. |
| 34 |
HuffmanTableEntry() : bits(0), value(0xffff) {} |
| 35 |
|
| 36 |
uint8_t bits; // number of bits used for this symbol |
| 37 |
uint16_t value; // symbol value or table offset |
| 38 |
}; |
| 39 |
|
| 40 |
// Builds jpeg-style Huffman lookup table from the given symbols. |
| 41 |
// The symbols are in order of increasing bit lengths. The number of symbols |
| 42 |
// with bit length n is given in counts[n] for each n >= 1. |
| 43 |
void BuildJpegHuffmanTable(const uint32_t* counts, const uint32_t* symbols, |
| 44 |
HuffmanTableEntry* lut); |
| 45 |
|
| 46 |
} // namespace jpeg |
| 47 |
} // namespace jxl |
| 48 |
|
| 49 |
#endif // LIB_JXL_JPEG_ENC_JPEG_HUFFMAN_DECODE_H_ |