Class Bzip2HuffmanAllocator
java.lang.Object
io.netty.handler.codec.compression.Bzip2HuffmanAllocator
An 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.
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 -
Method Summary
Modifier and TypeMethodDescription(package private) static void
allocateHuffmanCodeLengths
(int[] array, int maximumLength) Allocates Canonical Huffman code lengths in place based on a sorted frequency array.private static void
allocateNodeLengths
(int[] array) A final allocation pass with no code length limit.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.private static int
findNodesToRelocate
(int[] array, int maximumLength) Finds the number of nodes to relocate in order to achieve a given code length limit.private static int
first
(int[] array, int i, int nodesToMove) private static void
setExtendedParentPointers
(int[] array) Fills the code array with extended parent pointers.
-
Constructor Details
-
Bzip2HuffmanAllocator
private Bzip2HuffmanAllocator()
-
-
Method Details
-
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
k
such thatnodesToMove <= k <= i
andi <= (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))
-