Class HuffmanTable
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
FieldsModifier and TypeFieldDescriptionprivate static final int[]
Symbols of the L-code in the order they need to be readprivate final int[]
private static final int
private final List
<int[]> -
Constructor Summary
ConstructorsModifierConstructorDescriptionprivate
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
Modifier and TypeMethodDescriptionprivate 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 Details
-
LEVEL1_BITS
private static final int LEVEL1_BITS- See Also:
-
L_CODE_ORDER
private static final int[] L_CODE_ORDERSymbols of the L-code in the order they need to be read -
level1
private final int[] level1 -
level2
-
-
Constructor Details
-
HuffmanTable
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:
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 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 IOException - Throws:
IOException
-
readSymbol
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
-