BinaryTree.java
/*
* Licensed to the Apache Software Foundation (ASF) under one
* or more contributor license agreements. See the NOTICE file
* distributed with this work for additional information
* regarding copyright ownership. The ASF 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 org.apache.commons.compress.archivers.zip;
import java.io.EOFException;
import java.io.IOException;
import java.io.InputStream;
import org.apache.commons.compress.utils.IOUtils;
import org.apache.commons.lang3.ArrayFill;
/**
* Binary tree of positive values.
*
* @since 1.7
*/
final class BinaryTree {
/** Value in the array indicating an undefined node */
private static final int UNDEFINED = -1;
/** Value in the array indicating a non leaf node */
private static final int NODE = -2;
/**
* Decodes the packed binary tree from the specified stream.
*/
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 += 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;
}
/**
* The array representing the binary tree. The root is at index 0, the left children are at 2*i+1 and the right children at 2*i+2.
*/
private final int[] tree;
BinaryTree(final int depth) {
if (depth < 0 || depth > 30) {
throw new IllegalArgumentException("depth must be bigger than 0 and not bigger than 30" + " but is " + depth);
}
tree = ArrayFill.fill(new int[(int) ((1L << depth + 1) - 1)], UNDEFINED);
}
/**
* Adds a leaf to the tree.
*
* @param node the index of the node where the path is appended
* @param path the path to the leaf (bits are parsed from the right to the left)
* @param depth the number of nodes in the path
* @param value the value of the leaf (must be positive)
*/
public void addLeaf(final int node, final int path, final int depth, final int value) {
if (depth == 0) {
// end of the path reached, add the value to the current node
if (tree[node] != UNDEFINED) {
throw new IllegalArgumentException("Tree value at index " + node + " has already been assigned (" + tree[node] + ")");
}
tree[node] = value;
} else {
// mark the current node as a non leaf node
tree[node] = NODE;
// move down the path recursively
final int nextChild = 2 * node + 1 + (path & 1);
addLeaf(nextChild, path >>> 1, depth - 1, value);
}
}
/**
* Reads a value from the specified bit stream.
*
* @param stream
* @return the value decoded, or -1 if the end of the stream is reached
* @throws IOException on error.
*/
public int read(final BitStream stream) throws IOException {
int currentIndex = 0;
while (true) {
final int bit = stream.nextBit();
if (bit == -1) {
return -1;
}
final int childIndex = 2 * currentIndex + 1 + bit;
final int value = tree[childIndex];
if (value == NODE) {
// consume the next bit
currentIndex = childIndex;
} else if (value != UNDEFINED) {
return value;
} else {
throw new IOException("The child " + bit + " of node at index " + currentIndex + " is not defined");
}
}
}
}