Class Bzip2HuffmanAllocator
- java.lang.Object
-
- io.netty.handler.codec.compression.Bzip2HuffmanAllocator
-
final class Bzip2HuffmanAllocator extends java.lang.ObjectAn in-place, length restricted Canonical Huffman code length allocator.
Based on the algorithm proposed by R. L. Milidi'u, A. A. Pessoa and E. S. Laber in In-place Length-Restricted Prefix Coding and incorporating additional ideas from the implementation of shcodec by Simakov Alexander.
-
-
Constructor Summary
Constructors Modifier Constructor Description privateBzip2HuffmanAllocator()
-
Method Summary
All Methods Static Methods Concrete Methods Modifier and Type Method Description (package private) static voidallocateHuffmanCodeLengths(int[] array, int maximumLength)Allocates Canonical Huffman code lengths in place based on a sorted frequency array.private static voidallocateNodeLengths(int[] array)A final allocation pass with no code length limit.private static voidallocateNodeLengthsWithRelocation(int[] array, int nodesToMove, int insertDepth)A final allocation pass that relocates nodes in order to achieve a maximum code length limit.private static intfindNodesToRelocate(int[] array, int maximumLength)Finds the number of nodes to relocate in order to achieve a given code length limit.private static intfirst(int[] array, int i, int nodesToMove)private static voidsetExtendedParentPointers(int[] array)Fills the code array with extended parent pointers.
-
-
-
Method Detail
-
first
private static int first(int[] array, int i, int nodesToMove)- Parameters:
array- The code length arrayi- The input positionnodesToMove- The number of internal nodes to be relocated- Returns:
- The smallest
ksuch thatnodesToMove <= k <= iandi <= (array[k] % array.length)
-
setExtendedParentPointers
private static void setExtendedParentPointers(int[] array)
Fills the code array with extended parent pointers.- Parameters:
array- The code length array
-
findNodesToRelocate
private static int findNodesToRelocate(int[] array, int maximumLength)Finds the number of nodes to relocate in order to achieve a given code length limit.- Parameters:
array- The code length arraymaximumLength- The maximum bit length for the generated codes- Returns:
- The number of nodes to relocate
-
allocateNodeLengths
private static void allocateNodeLengths(int[] array)
A final allocation pass with no code length limit.- Parameters:
array- The code length array
-
allocateNodeLengthsWithRelocation
private static void allocateNodeLengthsWithRelocation(int[] array, int nodesToMove, int insertDepth)A final allocation pass that relocates nodes in order to achieve a maximum code length limit.- Parameters:
array- The code length arraynodesToMove- The number of internal nodes to be relocatedinsertDepth- The depth at which to insert relocated nodes
-
allocateHuffmanCodeLengths
static void allocateHuffmanCodeLengths(int[] array, int maximumLength)Allocates Canonical Huffman code lengths in place based on a sorted frequency array.- Parameters:
array- On input, a sorted array of symbol frequencies; On output, an array of Canonical Huffman code lengthsmaximumLength- The maximum code length. Must be at leastceil(log2(array.length))
-
-