lib/jpegli/huffman.h

   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 // 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   uint8_t bits;    // number of bits used for this symbol
  25   uint16_t value;  // symbol value or table offset
  26 };
  27
  28 void BuildJpegHuffmanTable(const uint32_t* count, const uint32_t* symbols,
  29                            HuffmanTableEntry* lut);
  30
  31 // This function will create a Huffman tree.
  32 //
  33 // The (data,length) contains the population counts.
  34 // The tree_limit is the maximum bit depth of the Huffman codes.
  35 //
  36 // The depth contains the tree, i.e., how many bits are used for
  37 // the symbol.
  38 //
  39 // See http://en.wikipedia.org/wiki/Huffman_coding
  40 void CreateHuffmanTree(const uint32_t* data, size_t length, int tree_limit,
  41                        uint8_t* depth);
  42
  43 void ValidateHuffmanTable(j_common_ptr cinfo, const JHUFF_TBL* table,
  44                           bool is_dc);
  45
  46 void AddStandardHuffmanTables(j_common_ptr cinfo, bool is_dc);
  47
  48 }  // namespace jpegli
  49
  50 #endif  // LIB_JPEGLI_HUFFMAN_H_