static BinaryTree decode()

in src/main/java/org/apache/commons/compress/archivers/zip/BinaryTree.java [45:133]

• 64 lines of code
• 15 McCabe index (conditional complexity)

    static BinaryTree decode(final InputStream inputStream, final int totalNumberOfValues) throws IOException {
        if (totalNumberOfValues < 0) {
            throw new IllegalArgumentException("totalNumberOfValues must be bigger than 0, is "
                + totalNumberOfValues);
        }
        // the first byte contains the size of the structure minus one
        final int size = inputStream.read() + 1;
        if (size == 0) {
            throw new IOException("Cannot read the size of the encoded tree, unexpected end of stream");
        }

        final byte[] encodedTree = IOUtils.readRange(inputStream, size);
        if (encodedTree.length != size) {
            throw new EOFException();
        }

        /* The maximum bit length for a value (16 or lower) */
        int maxLength = 0;

        final int[] originalBitLengths = new int[totalNumberOfValues];
        int pos = 0;
        for (final byte b : encodedTree) {
            // each byte encodes the number of values (upper 4 bits) for a bit length (lower 4 bits)
            final int numberOfValues = ((b & 0xF0) >> 4) + 1;
            if (pos + numberOfValues > totalNumberOfValues) {
                throw new IOException("Number of values exceeds given total number of values");
            }
            final int bitLength = (b & 0x0F) + 1;

            for (int j = 0; j < numberOfValues; j++) {
                originalBitLengths[pos++] = bitLength;
            }

            maxLength = Math.max(maxLength, bitLength);
        }

        final int oBitLengths = originalBitLengths.length;
        // sort the array of bit lengths and memorize the permutation used to restore the order of the codes
        final int[] permutation = new int[oBitLengths];
        for (int k = 0; k < permutation.length; k++) {
            permutation[k] = k;
        }

        int c = 0;
        final int[] sortedBitLengths = new int[oBitLengths];
        for (int k = 0; k < oBitLengths; k++) {
            // iterate over the values
            for (int l = 0; l < oBitLengths; l++) {
                // look for the value in the original array
                if (originalBitLengths[l] == k) {
                    // put the value at the current position in the sorted array...
                    sortedBitLengths[c] = k;

                    // ...and memorize the permutation
                    permutation[c] = l;

                    c++;
                }
            }
        }

        // decode the values of the tree
        int code = 0;
        int codeIncrement = 0;
        int lastBitLength = 0;

        final int[] codes = new int[totalNumberOfValues];

        for (int i = totalNumberOfValues - 1; i >= 0; i--) {
            code = code + codeIncrement;
            if (sortedBitLengths[i] != lastBitLength) {
                lastBitLength = sortedBitLengths[i];
                codeIncrement = 1 << (16 - lastBitLength);
            }
            codes[permutation[i]] = code;
        }

        // build the tree
        final BinaryTree tree = new BinaryTree(maxLength);

        for (int k = 0; k < codes.length; k++) {
            final int bitLength = originalBitLengths[k];
            if (bitLength > 0) {
                tree.addLeaf(0, Integer.reverse(codes[k] << 16), bitLength, k);
            }
        }

        return tree;
    }