Java example source code file (Bzip2HuffmanStageDecoder.java)

This example Java source code file (Bzip2HuffmanStageDecoder.java) is included in the alvinalexander.com "Java Source Code Warehouse" project. The intent of this project is to help you "Learn Java by Example" ^TM.

Learn more about this Java project at its project page.

Java - Java tags/keywords

bzip2bitreader, bzip2huffmanstagedecoder, bzip2movetofronttable, decompressionexception, huffman_decode_max_code_length, huffman_group_run_length

The Bzip2HuffmanStageDecoder.java Java example source code

/*
 * Copyright 2014 The Netty Project
 *
 * The Netty Project licenses this file to you under the Apache License,
 * version 2.0 (the "License"); you may not use this file except in compliance
 * with the License. You may obtain a copy of the License at:
 *
 *   http://www.apache.org/licenses/LICENSE-2.0
 *
 * Unless required by applicable law or agreed to in writing, software
 * distributed under the License is distributed on an "AS IS" BASIS, WITHOUT
 * WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. See the
 * License for the specific language governing permissions and limitations
 * under the License.
 */
package io.netty.handler.codec.compression;

import static io.netty.handler.codec.compression.Bzip2Constants.*;

/**
 * A decoder for the Bzip2 Huffman coding stage.
 */
final class Bzip2HuffmanStageDecoder {
    /**
     * A reader that provides bit-level reads.
     */
    private final Bzip2BitReader reader;

    /**
     * The Huffman table number to use for each group of 50 symbols.
     */
    byte[] selectors;

    /**
     * The minimum code length for each Huffman table.
     */
    private final int[] minimumLengths;

    /**
     * An array of values for each Huffman table that must be subtracted from the numerical value of
     * a Huffman code of a given bit length to give its canonical code index.
     */
    private final int[][] codeBases;

    /**
     * An array of values for each Huffman table that gives the highest numerical value of a Huffman
     * code of a given bit length.
     */
    private final int[][] codeLimits;

    /**
     * A mapping for each Huffman table from canonical code index to output symbol.
     */
    private final int[][] codeSymbols;

    /**
     * The Huffman table for the current group.
     */
    private int currentTable;

    /**
     * The index of the current group within the selectors array.
     */
    private int groupIndex = -1;

    /**
     * The byte position within the current group. A new group is selected every 50 decoded bytes.
     */
    private int groupPosition = -1;

    /**
     * Total number of used Huffman tables in range 2..6.
     */
    final int totalTables;

    /**
     * The total number of codes (uniform for each table).
     */
    final int alphabetSize;

    /**
     * Table for Move To Front transformations.
     */
    final Bzip2MoveToFrontTable tableMTF = new Bzip2MoveToFrontTable();

    // For saving state if end of current ByteBuf was reached
    int currentSelector;

    /**
     * The Canonical Huffman code lengths for each table.
     */
    final byte[][] tableCodeLengths;

    // For saving state if end of current ByteBuf was reached
    int currentGroup;
    int currentLength = -1;
    int currentAlpha;
    boolean modifyLength;

    Bzip2HuffmanStageDecoder(final Bzip2BitReader reader, final int totalTables, final int alphabetSize) {
        this.reader = reader;
        this.totalTables = totalTables;
        this.alphabetSize = alphabetSize;

        minimumLengths = new int[totalTables];
        codeBases = new int[totalTables][HUFFMAN_DECODE_MAX_CODE_LENGTH + 2];
        codeLimits = new int[totalTables][HUFFMAN_DECODE_MAX_CODE_LENGTH + 1];
        codeSymbols = new int[totalTables][HUFFMAN_MAX_ALPHABET_SIZE];
        tableCodeLengths = new byte[totalTables][HUFFMAN_MAX_ALPHABET_SIZE];
    }

    /**
     * Constructs Huffman decoding tables from lists of Canonical Huffman code lengths.
     */
    void createHuffmanDecodingTables() {
        final int alphabetSize = this.alphabetSize;

        for (int table = 0; table < tableCodeLengths.length; table++) {
            final int[] tableBases = codeBases[table];
            final int[] tableLimits = codeLimits[table];
            final int[] tableSymbols = codeSymbols[table];
            final byte[] codeLengths = tableCodeLengths[table];

            int minimumLength = HUFFMAN_DECODE_MAX_CODE_LENGTH;
            int maximumLength = 0;

            // Find the minimum and maximum code length for the table
            for (int i = 0; i < alphabetSize; i++) {
                final byte currLength = codeLengths[i];
                maximumLength = Math.max(currLength, maximumLength);
                minimumLength = Math.min(currLength, minimumLength);
            }
            minimumLengths[table] = minimumLength;

            // Calculate the first output symbol for each code length
            for (int i = 0; i < alphabetSize; i++) {
                tableBases[codeLengths[i] + 1]++;
            }
            for (int i = 1, b = tableBases[0]; i < HUFFMAN_DECODE_MAX_CODE_LENGTH + 2; i++) {
                b += tableBases[i];
                tableBases[i] = b;
            }

            // Calculate the first and last Huffman code for each code length (codes at a given
            // length are sequential in value)
            for (int i = minimumLength, code = 0; i <= maximumLength; i++) {
                int base = code;
                code += tableBases[i + 1] - tableBases[i];
                tableBases[i] = base - tableBases[i];
                tableLimits[i] = code - 1;
                code <<= 1;
            }

            // Populate the mapping from canonical code index to output symbol
            for (int bitLength = minimumLength, codeIndex = 0; bitLength <= maximumLength; bitLength++) {
                for (int symbol = 0; symbol < alphabetSize; symbol++) {
                    if (codeLengths[symbol] == bitLength) {
                        tableSymbols[codeIndex++] = symbol;
                    }
                }
            }
        }

        currentTable = selectors[0];
    }

    /**
     * Decodes and returns the next symbol.
     * @return The decoded symbol
     */
    int nextSymbol() {
        // Move to next group selector if required
        if (++groupPosition % HUFFMAN_GROUP_RUN_LENGTH == 0) {
            groupIndex++;
            if (groupIndex == selectors.length) {
                throw new DecompressionException("error decoding block");
            }
            currentTable = selectors[groupIndex] & 0xff;
        }

        final Bzip2BitReader reader = this.reader;
        final int currentTable = this.currentTable;
        final int[] tableLimits = codeLimits[currentTable];
        final int[] tableBases = codeBases[currentTable];
        final int[] tableSymbols = codeSymbols[currentTable];
        int codeLength = minimumLengths[currentTable];

        // Starting with the minimum bit length for the table, read additional bits one at a time
        // until a complete code is recognised
        int codeBits = reader.readBits(codeLength);
        for (; codeLength <= HUFFMAN_DECODE_MAX_CODE_LENGTH; codeLength++) {
            if (codeBits <= tableLimits[codeLength]) {
                // Convert the code to a symbol index and return
                return tableSymbols[codeBits - tableBases[codeLength]];
            }
            codeBits = codeBits << 1 | reader.readBits(1);
        }

        throw new DecompressionException("a valid code was not recognised");
    }
}