java.lang.Object
com.twelvemonkeys.imageio.plugins.webp.lossless.HuffmanTable

final class HuffmanTable extends Object
Represents a single huffman tree as a table.

Decoding a symbol just involves reading bits from the input stream and using that read value to index into the lookup table.

Code length and the corresponding symbol are packed into one array element (int). This is done to avoid the overhead and the fragmentation over the whole heap involved with creating objects of a custom class. The upper 16 bits of each element are the code length and lower 16 bits are the symbol.

The max allowed code length by the WEBP specification is 15, therefore this would mean the table needs to have 2^15 elements. To keep a reasonable memory usage, instead the lookup table only directly holds symbols with code length up to LEVEL1_BITS (Currently 8 bits). For longer codes the lookup table stores a reference to a second level lookup table. This reference consists of an element with length as the max length of the level 2 table and value as the index of the table in the list of level 2 tables.

Reading bits from the input is done in a least significant bit first way (LSB) way, therefore the prefix of the read value of length i is the lowest i bits in inverse order. The lookup table is directly indexed by the LEVEL1_BITS next bits read from the input (i.e. the bits corresponding to next code are inverse suffix of the read value/index). So for a code length of l all values with the lowest l bits the same need to decode to the same symbol regardless of the (LEVEL1_BITS - l) higher bits. So the lookup table needs to have the entry of this symbol repeated every 2^(l + 1) spots starting from the bitwise inverse of the code.

  • Field Summary

    Fields
    Modifier and Type
    Field
    Description
    private static final int[]
    Symbols of the L-code in the order they need to be read
    private final int[]
     
    private static final int
     
    private final List<int[]>
     
  • Constructor Summary

    Constructors
    Modifier
    Constructor
    Description
    private
    HuffmanTable(short[] codeLengths, int numPosCodeLens)
    Builds a Huffman table by using already given code lengths to generate the codes from
     
    HuffmanTable(LSBBitReader lsbBitReader, int alphabetSize)
    Build a Huffman table by reading the encoded symbol lengths from the reader
  • Method Summary

    Modifier and Type
    Method
    Description
    private void
    buildFromLengths(short[] codeLengths)
     
    private void
    buildFromLengths(short[] codeLengths, int numPosCodeLens)
     
    private int
    nextCode(int code, int length)
    Computes the next code
    private static short[]
    readCodeLengths(LSBBitReader lsbBitReader, short[] aCodeLengths, int alphabetSize, int numPosCodeLens)
     
    short
    readSymbol(LSBBitReader lsbBitReader)
    Reads the next code symbol from the streaming and decode it using the Huffman table

    Methods inherited from class java.lang.Object

    clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait
  • Field Details

    • LEVEL1_BITS

      private static final int LEVEL1_BITS
      See Also:
    • L_CODE_ORDER

      private static final int[] L_CODE_ORDER
      Symbols of the L-code in the order they need to be read
    • level1

      private final int[] level1
    • level2

      private final List<int[]> level2
  • Constructor Details

    • HuffmanTable

      public HuffmanTable(LSBBitReader lsbBitReader, int alphabetSize) throws IOException
      Build a Huffman table by reading the encoded symbol lengths from the reader
      Parameters:
      lsbBitReader - the reader to read from
      alphabetSize - the number of symbols in the alphabet to be decoded by this huffman table
      Throws:
      IOException - when reading produces an exception
    • HuffmanTable

      private HuffmanTable(short[] codeLengths, int numPosCodeLens)
      Builds a Huffman table by using already given code lengths to generate the codes from
      Parameters:
      codeLengths - the array specifying the bit length of the code for a symbol (i.e. codeLengths[i] is the bit length of the code for the symbol i)
      numPosCodeLens - the number of positive (i.e. non-zero) codeLengths in the array (allows more efficient table generation)
  • Method Details

    • buildFromLengths

      private void buildFromLengths(short[] codeLengths)
    • buildFromLengths

      private void buildFromLengths(short[] codeLengths, int numPosCodeLens)
    • nextCode

      private int nextCode(int code, int length)
      Computes the next code
      Parameters:
      code - the current code
      length - the currently valid length
      Returns:
      reverse(reverse(code, length) + 1, length) where reverse(a, b) is the lowest b bits of a in inverted order
    • readCodeLengths

      private static short[] readCodeLengths(LSBBitReader lsbBitReader, short[] aCodeLengths, int alphabetSize, int numPosCodeLens) throws IOException
      Throws:
      IOException
    • readSymbol

      public short readSymbol(LSBBitReader lsbBitReader) throws IOException
      Reads the next code symbol from the streaming and decode it using the Huffman table
      Parameters:
      lsbBitReader - the reader to read a symbol from (will be advanced accordingly)
      Returns:
      the decoded symbol
      Throws:
      IOException - when the reader throws one reading a symbol