generateHuffmanCodeLengths() — netty Function Reference

Source Code

codec-compression/src/main/java/io/netty/handler/codec/compression/Bzip2HuffmanStageEncoder.java lines 123–154

    private static void generateHuffmanCodeLengths(final int alphabetSize,
                                                   final int[] symbolFrequencies, final int[] codeLengths) {

        final int[] mergedFrequenciesAndIndices = new int[alphabetSize];
        final int[] sortedFrequencies = new int[alphabetSize];

        // The Huffman allocator needs its input symbol frequencies to be sorted, but we need to
        // return code lengths in the same order as the corresponding frequencies are passed in.

        // The symbol frequency and index are merged into a single array of
        // integers - frequency in the high 23 bits, index in the low 9 bits.
        //     2^23 = 8,388,608 which is higher than the maximum possible frequency for one symbol in a block
        //     2^9 = 512 which is higher than the maximum possible alphabet size (== 258)
        // Sorting this array simultaneously sorts the frequencies and
        // leaves a lookup that can be used to cheaply invert the sort.
        for (int i = 0; i < alphabetSize; i++) {
            mergedFrequenciesAndIndices[i] = (symbolFrequencies[i] << 9) | i;
        }
        Arrays.sort(mergedFrequenciesAndIndices);
        for (int i = 0; i < alphabetSize; i++) {
            sortedFrequencies[i] = mergedFrequenciesAndIndices[i] >>> 9;
        }

        // Allocate code lengths - the allocation is in place,
        // so the code lengths will be in the sortedFrequencies array afterwards
        Bzip2HuffmanAllocator.allocateHuffmanCodeLengths(sortedFrequencies, HUFFMAN_ENCODE_MAX_CODE_LENGTH);

        // Reverse the sort to place the code lengths in the same order as the symbols whose frequencies were passed in
        for (int i = 0; i < alphabetSize; i++) {
            codeLengths[mergedFrequenciesAndIndices[i] & 0x1ff] = sortedFrequencies[i];
        }
    }