Class HuffmanTable


  • final class HuffmanTable
    extends java.lang.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 int[] L_CODE_ORDER
      Symbols of the L-code in the order they need to be read
      private int[] level1  
      private static int LEVEL1_BITS  
      private java.util.List<int[]> level2  
    • 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

      All Methods Static Methods Instance Methods Concrete Methods 
      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 Detail

      • 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 java.util.List<int[]> level2
    • Constructor Detail

      • HuffmanTable

        public HuffmanTable​(LSBBitReader lsbBitReader,
                            int alphabetSize)
                     throws java.io.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:
        java.io.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 Detail

      • 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 java.io.IOException
        Throws:
        java.io.IOException
      • readSymbol

        public short readSymbol​(LSBBitReader lsbBitReader)
                         throws java.io.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:
        java.io.IOException - when the reader throws one reading a symbol