Bzip2HuffmanAllocator.java — netty Source File

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:
 *
 *   https://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;

/**
 * An in-place, length restricted Canonical Huffman code length allocator.<br>
 * Based on the algorithm proposed by R. L. Milidi'u, A. A. Pessoa and E. S. Laber in
 * <a href="http://www-di.inf.puc-rio.br/~laber/public/spire98.ps">In-place Length-Restricted Prefix Coding</a>
 * and incorporating additional ideas from the implementation of
 * <a href="http://entropyware.info/shcodec/index.html">shcodec</a> by Simakov Alexander.
 */
final class Bzip2HuffmanAllocator {
    /**
     * @param array The code length array
     * @param i The input position
     * @param nodesToMove The number of internal nodes to be relocated
     * @return The smallest {@code k} such that {@code nodesToMove <= k <= i} and
     *         {@code i <= (array[k] % array.length)}
     */
    private static int first(final int[] array, int i, final int nodesToMove) {
        final int length = array.length;
        final int limit = i;
        int k = array.length - 2;

        while (i >= nodesToMove && array[i] % length > limit) {
            k = i;
            i -= limit - i + 1;
        }
        i = Math.max(nodesToMove - 1, i);

        while (k > i + 1) {
            int temp = i + k >>> 1;
            if (array[temp] % length > limit) {
                k = temp;
            } else {
                i = temp;
            }
        }
        return k;
    }

    /**
     * Fills the code array with extended parent pointers.
     * @param array The code length array
     */
    private static void setExtendedParentPointers(final int[] array) {
        final int length = array.length;
// ... (125 more lines)