Class Bzip2HuffmanAllocator

java.lang.Object
io.netty.handler.codec.compression.Bzip2HuffmanAllocator

final class Bzip2HuffmanAllocator extends 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
     
  • Method Summary

    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
    Fills the code array with extended parent pointers.

    Methods inherited from class java.lang.Object

    clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait
  • Constructor Details

    • Bzip2HuffmanAllocator

      private Bzip2HuffmanAllocator()
  • Method Details

    • first

      private static int first(int[] array, int i, int nodesToMove)
      Parameters:
      array - The code length array
      i - The input position
      nodesToMove - The number of internal nodes to be relocated
      Returns:
      The smallest k such that nodesToMove <= k <= i and i <= (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 array
      maximumLength - 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 array
      nodesToMove - The number of internal nodes to be relocated
      insertDepth - 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 lengths
      maximumLength - The maximum code length. Must be at least ceil(log2(array.length))