View Javadoc

1   /*
2    * Copyright 2009 Red Hat, Inc.
3    *
4    * Red Hat licenses this file to you under the Apache License, version 2.0
5    * (the "License"); you may not use this file except in compliance with the
6    * License.  You may obtain a copy of the License at:
7    *
8    *    http://www.apache.org/licenses/LICENSE-2.0
9    *
10   * Unless required by applicable law or agreed to in writing, software
11   * distributed under the License is distributed on an "AS IS" BASIS, WITHOUT
12   * WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.  See the
13   * License for the specific language governing permissions and limitations
14   * under the License.
15   */
16  /*
17  Copyright (c) 2000,2001,2002,2003 ymnk, JCraft,Inc. All rights reserved.
18  
19  Redistribution and use in source and binary forms, with or without
20  modification, are permitted provided that the following conditions are met:
21  
22    1. Redistributions of source code must retain the above copyright notice,
23       this list of conditions and the following disclaimer.
24  
25    2. Redistributions in binary form must reproduce the above copyright
26       notice, this list of conditions and the following disclaimer in
27       the documentation and/or other materials provided with the distribution.
28  
29    3. The names of the authors may not be used to endorse or promote products
30       derived from this software without specific prior written permission.
31  
32  THIS SOFTWARE IS PROVIDED ``AS IS'' AND ANY EXPRESSED OR IMPLIED WARRANTIES,
33  INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND
34  FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL JCRAFT,
35  INC. OR ANY CONTRIBUTORS TO THIS SOFTWARE BE LIABLE FOR ANY DIRECT, INDIRECT,
36  INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
37  LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA,
38  OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF
39  LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
40  NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE,
41  EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
42   */
43  /*
44   * This program is based on zlib-1.1.3, so all credit should go authors
45   * Jean-loup Gailly(jloup@gzip.org) and Mark Adler(madler@alumni.caltech.edu)
46   * and contributors of zlib.
47   */
48  
49  package org.jboss.netty.util.internal.jzlib;
50  
51  final class Tree {
52      // extra bits for each length code
53      static final int[] extra_lbits = { 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 2,
54              2, 2, 2, 3, 3, 3, 3, 4, 4, 4, 4, 5, 5, 5, 5, 0 };
55  
56      // extra bits for each distance code
57      static final int[] extra_dbits = { 0, 0, 0, 0, 1, 1, 2, 2, 3, 3, 4, 4, 5,
58              5, 6, 6, 7, 7, 8, 8, 9, 9, 10, 10, 11, 11, 12, 12, 13, 13 };
59  
60      // extra bits for each bit length code
61      static final int[] extra_blbits = { 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
62              0, 0, 0, 2, 3, 7 };
63  
64      static final byte[] bl_order = { 16, 17, 18, 0, 8, 7, 9, 6, 10, 5, 11, 4,
65              12, 3, 13, 2, 14, 1, 15 };
66  
67      static final byte[] _dist_code = { 0, 1, 2, 3, 4, 4, 5, 5, 6, 6, 6, 6, 7,
68              7, 7, 7, 8, 8, 8, 8, 8, 8, 8, 8, 9, 9, 9, 9, 9, 9, 9, 9, 10, 10,
69              10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 11, 11, 11,
70              11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 12, 12, 12, 12,
71              12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12,
72              12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 13, 13, 13, 13, 13, 13,
73              13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13,
74              13, 13, 13, 13, 13, 13, 13, 13, 13, 14, 14, 14, 14, 14, 14, 14, 14,
75              14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14,
76              14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14,
77              14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14,
78              14, 14, 14, 14, 14, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15,
79              15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15,
80              15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15,
81              15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15,
82              15, 0, 0, 16, 17, 18, 18, 19, 19, 20, 20, 20, 20, 21, 21, 21, 21,
83              22, 22, 22, 22, 22, 22, 22, 22, 23, 23, 23, 23, 23, 23, 23, 23, 24,
84              24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 25, 25,
85              25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 26, 26, 26,
86              26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26,
87              26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 27, 27, 27, 27, 27,
88              27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27,
89              27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 28, 28, 28, 28, 28, 28, 28,
90              28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28,
91              28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28,
92              28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28,
93              28, 28, 28, 28, 28, 28, 29, 29, 29, 29, 29, 29, 29, 29, 29, 29, 29,
94              29, 29, 29, 29, 29, 29, 29, 29, 29, 29, 29, 29, 29, 29, 29, 29, 29,
95              29, 29, 29, 29, 29, 29, 29, 29, 29, 29, 29, 29, 29, 29, 29, 29, 29,
96              29, 29, 29, 29, 29, 29, 29, 29, 29, 29, 29, 29, 29, 29, 29, 29, 29,
97              29, 29 };
98  
99      static final byte[] _length_code = { 0, 1, 2, 3, 4, 5, 6, 7, 8, 8, 9, 9,
100             10, 10, 11, 11, 12, 12, 12, 12, 13, 13, 13, 13, 14, 14, 14, 14, 15,
101             15, 15, 15, 16, 16, 16, 16, 16, 16, 16, 16, 17, 17, 17, 17, 17, 17,
102             17, 17, 18, 18, 18, 18, 18, 18, 18, 18, 19, 19, 19, 19, 19, 19, 19,
103             19, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20,
104             21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 22,
105             22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 23, 23,
106             23, 23, 23, 23, 23, 23, 23, 23, 23, 23, 23, 23, 23, 23, 24, 24, 24,
107             24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24,
108             24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 25, 25, 25, 25, 25,
109             25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25,
110             25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 26, 26, 26, 26, 26, 26, 26,
111             26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26,
112             26, 26, 26, 26, 26, 26, 26, 26, 27, 27, 27, 27, 27, 27, 27, 27, 27,
113             27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27,
114             27, 27, 27, 27, 27, 28 };
115 
116     static final int[] base_length = { 0, 1, 2, 3, 4, 5, 6, 7, 8, 10, 12, 14,
117             16, 20, 24, 28, 32, 40, 48, 56, 64, 80, 96, 112, 128, 160, 192,
118             224, 0 };
119 
120     static final int[] base_dist = { 0, 1, 2, 3, 4, 6, 8, 12, 16, 24, 32, 48,
121             64, 96, 128, 192, 256, 384, 512, 768, 1024, 1536, 2048, 3072, 4096,
122             6144, 8192, 12288, 16384, 24576 };
123 
124     // Mapping from a distance to a distance code. dist is the distance - 1 and
125     // must not have side effects. _dist_code[256] and _dist_code[257] are never
126     // used.
127     static int d_code(int dist) {
128         return dist < 256? _dist_code[dist] : _dist_code[256 + (dist >>> 7)];
129     }
130 
131     short[] dyn_tree; // the dynamic tree
132     int max_code; // largest code with non zero frequency
133     StaticTree stat_desc; // the corresponding static tree
134 
135     // Compute the optimal bit lengths for a tree and update the total bit length
136     // for the current block.
137     // IN assertion: the fields freq and dad are set, heap[heap_max] and
138     //    above are the tree nodes sorted by increasing frequency.
139     // OUT assertions: the field len is set to the optimal bit length, the
140     //     array bl_count contains the frequencies for each bit length.
141     //     The length opt_len is updated; static_len is also updated if stree is
142     //     not null.
143     private void gen_bitlen(Deflate s) {
144         short[] tree = dyn_tree;
145         short[] stree = stat_desc.static_tree;
146         int[] extra = stat_desc.extra_bits;
147         int base = stat_desc.extra_base;
148         int max_length = stat_desc.max_length;
149         int h; // heap index
150         int n, m; // iterate over the tree elements
151         int bits; // bit length
152         int xbits; // extra bits
153         short f; // frequency
154         int overflow = 0; // number of elements with bit length too large
155 
156         for (bits = 0; bits <= JZlib.MAX_BITS; bits ++) {
157             s.bl_count[bits] = 0;
158         }
159 
160         // In a first pass, compute the optimal bit lengths (which may
161         // overflow in the case of the bit length tree).
162         tree[s.heap[s.heap_max] * 2 + 1] = 0; // root of the heap
163 
164         for (h = s.heap_max + 1; h < JZlib.HEAP_SIZE; h ++) {
165             n = s.heap[h];
166             bits = tree[tree[n * 2 + 1] * 2 + 1] + 1;
167             if (bits > max_length) {
168                 bits = max_length;
169                 overflow ++;
170             }
171             tree[n * 2 + 1] = (short) bits;
172             // We overwrite tree[n*2+1] which is no longer needed
173 
174             if (n > max_code) {
175                 continue; // not a leaf node
176             }
177 
178             s.bl_count[bits] ++;
179             xbits = 0;
180             if (n >= base) {
181                 xbits = extra[n - base];
182             }
183             f = tree[n * 2];
184             s.opt_len += f * (bits + xbits);
185             if (stree != null) {
186                 s.static_len += f * (stree[n * 2 + 1] + xbits);
187             }
188         }
189         if (overflow == 0) {
190             return;
191         }
192 
193         // This happens for example on obj2 and pic of the Calgary corpus
194         // Find the first bit length which could increase:
195         do {
196             bits = max_length - 1;
197             while (s.bl_count[bits] == 0) {
198                 bits --;
199             }
200             s.bl_count[bits] --; // move one leaf down the tree
201             s.bl_count[bits + 1] += 2; // move one overflow item as its brother
202             s.bl_count[max_length] --;
203             // The brother of the overflow item also moves one step up,
204             // but this does not affect bl_count[max_length]
205             overflow -= 2;
206         } while (overflow > 0);
207 
208         for (bits = max_length; bits != 0; bits --) {
209             n = s.bl_count[bits];
210             while (n != 0) {
211                 m = s.heap[-- h];
212                 if (m > max_code) {
213                     continue;
214                 }
215                 if (tree[m * 2 + 1] != bits) {
216                     s.opt_len += ((long) bits - (long) tree[m * 2 + 1]) *
217                             tree[m * 2];
218                     tree[m * 2 + 1] = (short) bits;
219                 }
220                 n --;
221             }
222         }
223     }
224 
225     // Construct one Huffman tree and assigns the code bit strings and lengths.
226     // Update the total bit length for the current block.
227     // IN assertion: the field freq is set for all tree elements.
228     // OUT assertions: the fields len and code are set to the optimal bit length
229     //     and corresponding code. The length opt_len is updated; static_len is
230     //     also updated if stree is not null. The field max_code is set.
231     void build_tree(Deflate s) {
232         short[] tree = dyn_tree;
233         short[] stree = stat_desc.static_tree;
234         int elems = stat_desc.elems;
235         int n, m; // iterate over heap elements
236         int max_code = -1; // largest code with non zero frequency
237         int node; // new node being created
238 
239         // Construct the initial heap, with least frequent element in
240         // heap[1]. The sons of heap[n] are heap[2*n] and heap[2*n+1].
241         // heap[0] is not used.
242         s.heap_len = 0;
243         s.heap_max = JZlib.HEAP_SIZE;
244 
245         for (n = 0; n < elems; n ++) {
246             if (tree[n * 2] != 0) {
247                 s.heap[++ s.heap_len] = max_code = n;
248                 s.depth[n] = 0;
249             } else {
250                 tree[n * 2 + 1] = 0;
251             }
252         }
253 
254         // The pkzip format requires that at least one distance code exists,
255         // and that at least one bit should be sent even if there is only one
256         // possible code. So to avoid special checks later on we force at least
257         // two codes of non zero frequency.
258         while (s.heap_len < 2) {
259             node = s.heap[++ s.heap_len] = max_code < 2? ++ max_code : 0;
260             tree[node * 2] = 1;
261             s.depth[node] = 0;
262             s.opt_len --;
263             if (stree != null) {
264                 s.static_len -= stree[node * 2 + 1];
265                 // node is 0 or 1 so it does not have extra bits
266             }
267         }
268         this.max_code = max_code;
269 
270         // The elements heap[heap_len/2+1 .. heap_len] are leaves of the tree,
271         // establish sub-heaps of increasing lengths:
272 
273         for (n = s.heap_len / 2; n >= 1; n --) {
274             s.pqdownheap(tree, n);
275         }
276 
277         // Construct the Huffman tree by repeatedly combining the least two
278         // frequent nodes.
279 
280         node = elems; // next internal node of the tree
281         do {
282             // n = node of least frequency
283             n = s.heap[1];
284             s.heap[1] = s.heap[s.heap_len --];
285             s.pqdownheap(tree, 1);
286             m = s.heap[1]; // m = node of next least frequency
287 
288             s.heap[-- s.heap_max] = n; // keep the nodes sorted by frequency
289             s.heap[-- s.heap_max] = m;
290 
291             // Create a new node father of n and m
292             tree[node * 2] = (short) (tree[n * 2] + tree[m * 2]);
293             s.depth[node] = (byte) (Math.max(s.depth[n], s.depth[m]) + 1);
294             tree[n * 2 + 1] = tree[m * 2 + 1] = (short) node;
295 
296             // and insert the new node in the heap
297             s.heap[1] = node ++;
298             s.pqdownheap(tree, 1);
299         } while (s.heap_len >= 2);
300 
301         s.heap[-- s.heap_max] = s.heap[1];
302 
303         // At this point, the fields freq and dad are set. We can now
304         // generate the bit lengths.
305 
306         gen_bitlen(s);
307 
308         // The field len is now set, we can generate the bit codes
309         gen_codes(tree, max_code, s.bl_count);
310     }
311 
312     // Generate the codes for a given tree and bit counts (which need not be
313     // optimal).
314     // IN assertion: the array bl_count contains the bit length statistics for
315     // the given tree and the field len is set for all tree elements.
316     // OUT assertion: the field code is set for all tree elements of non
317     //     zero code length.
318     private static void gen_codes(short[] tree, // the tree to decorate
319             int max_code, // largest code with non zero frequency
320             short[] bl_count // number of codes at each bit length
321     ) {
322         short[] next_code = new short[JZlib.MAX_BITS + 1]; // next code value for each bit length
323         short code = 0; // running code value
324         int bits; // bit index
325         int n; // code index
326 
327         // The distribution counts are first used to generate the code values
328         // without bit reversal.
329         for (bits = 1; bits <= JZlib.MAX_BITS; bits ++) {
330             next_code[bits] = code = (short) (code + bl_count[bits - 1] << 1);
331         }
332 
333         // Check that the bit counts in bl_count are consistent. The last code
334         // must be all ones.
335         //Assert (code + bl_count[MAX_BITS]-1 == (1<<MAX_BITS)-1,
336         //        "inconsistent bit counts");
337         //Tracev((stderr,"\ngen_codes: max_code %d ", max_code));
338 
339         for (n = 0; n <= max_code; n ++) {
340             int len = tree[n * 2 + 1];
341             if (len == 0) {
342                 continue;
343             }
344             // Now reverse the bits
345             tree[n * 2] = (short) bi_reverse(next_code[len] ++, len);
346         }
347     }
348 
349     // Reverse the first len bits of a code, using straightforward code (a faster
350     // method would use a table)
351     // IN assertion: 1 <= len <= 15
352     private static int bi_reverse(int code, // the value to invert
353             int len // its bit length
354     ) {
355         int res = 0;
356         do {
357             res |= code & 1;
358             code >>>= 1;
359             res <<= 1;
360         } while (-- len > 0);
361         return res >>> 1;
362     }
363 }