Class HuffmanTable
- java.lang.Object
-
- com.twelvemonkeys.imageio.plugins.webp.lossless.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 readprivate 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 fromHuffmanTable(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 codeprivate 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
-
-
-
Field Detail
-
LEVEL1_BITS
private static final int LEVEL1_BITS
- See Also:
- Constant Field Values
-
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 fromalphabetSize
- 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 codelength
- the currently valid length- Returns:
reverse(reverse(code, length) + 1, length)
wherereverse(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
-
-