View Javadoc
1   /*
2    * Licensed to the Apache Software Foundation (ASF) under one
3    * or more contributor license agreements.  See the NOTICE file
4    * distributed with this work for additional information
5    * regarding copyright ownership.  The ASF licenses this file
6    * to you under the Apache License, Version 2.0 (the
7    * "License"); you may not use this file except in compliance
8    * with the License.  You may obtain a copy of the License at
9    *
10   * http://www.apache.org/licenses/LICENSE-2.0
11   *
12   * Unless required by applicable law or agreed to in writing,
13   * software distributed under the License is distributed on an
14   * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
15   * KIND, either express or implied.  See the License for the
16   * specific language governing permissions and limitations
17   * under the License.
18   */
19  
20  package org.apache.commons.compress.archivers.zip;
21  
22  import java.io.EOFException;
23  import java.io.IOException;
24  import java.io.InputStream;
25  import java.util.Arrays;
26  
27  import org.apache.commons.compress.utils.IOUtils;
28  
29  /**
30   * Binary tree of positive values.
31   *
32   * @since 1.7
33   */
34  final class BinaryTree {
35  
36      /** Value in the array indicating an undefined node */
37      private static final int UNDEFINED = -1;
38  
39      /** Value in the array indicating a non leaf node */
40      private static final int NODE = -2;
41  
42      /**
43       * Decodes the packed binary tree from the specified stream.
44       */
45      static BinaryTree decode(final InputStream inputStream, final int totalNumberOfValues) throws IOException {
46          if (totalNumberOfValues < 0) {
47              throw new IllegalArgumentException("totalNumberOfValues must be bigger than 0, is " + totalNumberOfValues);
48          }
49          // the first byte contains the size of the structure minus one
50          final int size = inputStream.read() + 1;
51          if (size == 0) {
52              throw new IOException("Cannot read the size of the encoded tree, unexpected end of stream");
53          }
54  
55          final byte[] encodedTree = IOUtils.readRange(inputStream, size);
56          if (encodedTree.length != size) {
57              throw new EOFException();
58          }
59  
60          /* The maximum bit length for a value (16 or lower) */
61          int maxLength = 0;
62  
63          final int[] originalBitLengths = new int[totalNumberOfValues];
64          int pos = 0;
65          for (final byte b : encodedTree) {
66              // each byte encodes the number of values (upper 4 bits) for a bit length (lower 4 bits)
67              final int numberOfValues = ((b & 0xF0) >> 4) + 1;
68              if (pos + numberOfValues > totalNumberOfValues) {
69                  throw new IOException("Number of values exceeds given total number of values");
70              }
71              final int bitLength = (b & 0x0F) + 1;
72  
73              for (int j = 0; j < numberOfValues; j++) {
74                  originalBitLengths[pos++] = bitLength;
75              }
76  
77              maxLength = Math.max(maxLength, bitLength);
78          }
79  
80          final int oBitLengths = originalBitLengths.length;
81          // sort the array of bit lengths and memorize the permutation used to restore the order of the codes
82          final int[] permutation = new int[oBitLengths];
83          for (int k = 0; k < permutation.length; k++) {
84              permutation[k] = k;
85          }
86  
87          int c = 0;
88          final int[] sortedBitLengths = new int[oBitLengths];
89          for (int k = 0; k < oBitLengths; k++) {
90              // iterate over the values
91              for (int l = 0; l < oBitLengths; l++) {
92                  // look for the value in the original array
93                  if (originalBitLengths[l] == k) {
94                      // put the value at the current position in the sorted array...
95                      sortedBitLengths[c] = k;
96  
97                      // ...and memorize the permutation
98                      permutation[c] = l;
99  
100                     c++;
101                 }
102             }
103         }
104 
105         // decode the values of the tree
106         int code = 0;
107         int codeIncrement = 0;
108         int lastBitLength = 0;
109 
110         final int[] codes = new int[totalNumberOfValues];
111 
112         for (int i = totalNumberOfValues - 1; i >= 0; i--) {
113             code += codeIncrement;
114             if (sortedBitLengths[i] != lastBitLength) {
115                 lastBitLength = sortedBitLengths[i];
116                 codeIncrement = 1 << 16 - lastBitLength;
117             }
118             codes[permutation[i]] = code;
119         }
120 
121         // build the tree
122         final BinaryTree tree = new BinaryTree(maxLength);
123 
124         for (int k = 0; k < codes.length; k++) {
125             final int bitLength = originalBitLengths[k];
126             if (bitLength > 0) {
127                 tree.addLeaf(0, Integer.reverse(codes[k] << 16), bitLength, k);
128             }
129         }
130 
131         return tree;
132     }
133 
134     /**
135      * 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.
136      */
137     private final int[] tree;
138 
139     BinaryTree(final int depth) {
140         if (depth < 0 || depth > 30) {
141             throw new IllegalArgumentException("depth must be bigger than 0 and not bigger than 30" + " but is " + depth);
142         }
143         tree = new int[(int) ((1L << depth + 1) - 1)];
144         Arrays.fill(tree, UNDEFINED);
145     }
146 
147     /**
148      * Adds a leaf to the tree.
149      *
150      * @param node  the index of the node where the path is appended
151      * @param path  the path to the leaf (bits are parsed from the right to the left)
152      * @param depth the number of nodes in the path
153      * @param value the value of the leaf (must be positive)
154      */
155     public void addLeaf(final int node, final int path, final int depth, final int value) {
156         if (depth == 0) {
157             // end of the path reached, add the value to the current node
158             if (tree[node] != UNDEFINED) {
159                 throw new IllegalArgumentException("Tree value at index " + node + " has already been assigned (" + tree[node] + ")");
160             }
161             tree[node] = value;
162         } else {
163             // mark the current node as a non leaf node
164             tree[node] = NODE;
165 
166             // move down the path recursively
167             final int nextChild = 2 * node + 1 + (path & 1);
168             addLeaf(nextChild, path >>> 1, depth - 1, value);
169         }
170     }
171 
172     /**
173      * Reads a value from the specified bit stream.
174      *
175      * @param stream
176      * @return the value decoded, or -1 if the end of the stream is reached
177      * @throws IOException on error.
178      */
179     public int read(final BitStream stream) throws IOException {
180         int currentIndex = 0;
181 
182         while (true) {
183             final int bit = stream.nextBit();
184             if (bit == -1) {
185                 return -1;
186             }
187 
188             final int childIndex = 2 * currentIndex + 1 + bit;
189             final int value = tree[childIndex];
190             if (value == NODE) {
191                 // consume the next bit
192                 currentIndex = childIndex;
193             } else if (value != UNDEFINED) {
194                 return value;
195             } else {
196                 throw new IOException("The child " + bit + " of node at index " + currentIndex + " is not defined");
197             }
198         }
199     }
200 }