Class Bzip2HuffmanAllocator
- java.lang.Object
-
- io.netty.handler.codec.compression.Bzip2HuffmanAllocator
-
final class Bzip2HuffmanAllocator extends java.lang.Object
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.
-
-
Constructor Summary
Constructors Modifier Constructor Description private
Bzip2HuffmanAllocator()
-
Method Summary
All Methods Static Methods Concrete Methods Modifier and Type Method Description (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.
-
-
-
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
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))
-
-