View Javadoc

1   /*
2    * Copyright 2012 The Netty Project
3    *
4    * The Netty Project licenses this file to you under the Apache License,
5    * version 2.0 (the "License"); you may not use this file except in compliance
6    * with the 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([email protected]) and Mark Adler([email protected])
46   * and contributors of zlib.
47   */
48  package org.jboss.netty.util.internal.jzlib;
49  
50  final class Tree {
51      // extra bits for each length code
52      static final int[] extra_lbits = { 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 2,
53              2, 2, 2, 3, 3, 3, 3, 4, 4, 4, 4, 5, 5, 5, 5, 0 };
54  
55      // extra bits for each distance code
56      static final int[] extra_dbits = { 0, 0, 0, 0, 1, 1, 2, 2, 3, 3, 4, 4, 5,
57              5, 6, 6, 7, 7, 8, 8, 9, 9, 10, 10, 11, 11, 12, 12, 13, 13 };
58  
59      // extra bits for each bit length code
60      static final int[] extra_blbits = { 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
61              0, 0, 0, 2, 3, 7 };
62  
63      static final byte[] bl_order = { 16, 17, 18, 0, 8, 7, 9, 6, 10, 5, 11, 4,
64              12, 3, 13, 2, 14, 1, 15 };
65  
66      static final byte[] _dist_code = { 0, 1, 2, 3, 4, 4, 5, 5, 6, 6, 6, 6, 7,
67              7, 7, 7, 8, 8, 8, 8, 8, 8, 8, 8, 9, 9, 9, 9, 9, 9, 9, 9, 10, 10,
68              10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 11, 11, 11,
69              11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 12, 12, 12, 12,
70              12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12,
71              12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 13, 13, 13, 13, 13, 13,
72              13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13,
73              13, 13, 13, 13, 13, 13, 13, 13, 13, 14, 14, 14, 14, 14, 14, 14, 14,
74              14, 14, 14, 14, 14, 14, 14, 14, 14, 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, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15,
78              15, 15, 15, 15, 15, 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, 0, 0, 16, 17, 18, 18, 19, 19, 20, 20, 20, 20, 21, 21, 21, 21,
82              22, 22, 22, 22, 22, 22, 22, 22, 23, 23, 23, 23, 23, 23, 23, 23, 24,
83              24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 25, 25,
84              25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 26, 26, 26,
85              26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26,
86              26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 27, 27, 27, 27, 27,
87              27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27,
88              27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 28, 28, 28, 28, 28, 28, 28,
89              28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 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, 29, 29, 29, 29, 29, 29, 29, 29, 29, 29, 29,
93              29, 29, 29, 29, 29, 29, 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 };
97  
98      static final byte[] _length_code = { 0, 1, 2, 3, 4, 5, 6, 7, 8, 8, 9, 9,
99              10, 10, 11, 11, 12, 12, 12, 12, 13, 13, 13, 13, 14, 14, 14, 14, 15,
100             15, 15, 15, 16, 16, 16, 16, 16, 16, 16, 16, 17, 17, 17, 17, 17, 17,
101             17, 17, 18, 18, 18, 18, 18, 18, 18, 18, 19, 19, 19, 19, 19, 19, 19,
102             19, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20,
103             21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 22,
104             22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 23, 23,
105             23, 23, 23, 23, 23, 23, 23, 23, 23, 23, 23, 23, 23, 23, 24, 24, 24,
106             24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24,
107             24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 25, 25, 25, 25, 25,
108             25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25,
109             25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 26, 26, 26, 26, 26, 26, 26,
110             26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26,
111             26, 26, 26, 26, 26, 26, 26, 26, 27, 27, 27, 27, 27, 27, 27, 27, 27,
112             27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27,
113             27, 27, 27, 27, 27, 28 };
114 
115     static final int[] base_length = { 0, 1, 2, 3, 4, 5, 6, 7, 8, 10, 12, 14,
116             16, 20, 24, 28, 32, 40, 48, 56, 64, 80, 96, 112, 128, 160, 192,
117             224, 0 };
118 
119     static final int[] base_dist = { 0, 1, 2, 3, 4, 6, 8, 12, 16, 24, 32, 48,
120             64, 96, 128, 192, 256, 384, 512, 768, 1024, 1536, 2048, 3072, 4096,
121             6144, 8192, 12288, 16384, 24576 };
122 
123     // Mapping from a distance to a distance code. dist is the distance - 1 and
124     // must not have side effects. _dist_code[256] and _dist_code[257] are never
125     // used.
126     static int d_code(int dist) {
127         return dist < 256? _dist_code[dist] : _dist_code[256 + (dist >>> 7)];
128     }
129 
130     short[] dyn_tree; // the dynamic tree
131     int max_code; // largest code with non zero frequency
132     StaticTree stat_desc; // the corresponding static tree
133 
134     // Compute the optimal bit lengths for a tree and update the total bit length
135     // for the current block.
136     // IN assertion: the fields freq and dad are set, heap[heap_max] and
137     //    above are the tree nodes sorted by increasing frequency.
138     // OUT assertions: the field len is set to the optimal bit length, the
139     //     array bl_count contains the frequencies for each bit length.
140     //     The length opt_len is updated; static_len is also updated if stree is
141     //     not null.
142     private void gen_bitlen(Deflate s) {
143         short[] tree = dyn_tree;
144         short[] stree = stat_desc.static_tree;
145         int[] extra = stat_desc.extra_bits;
146         int base = stat_desc.extra_base;
147         int max_length = stat_desc.max_length;
148         int h; // heap index
149         int n, m; // iterate over the tree elements
150         int bits; // bit length
151         int xbits; // extra bits
152         short f; // frequency
153         int overflow = 0; // number of elements with bit length too large
154 
155         for (bits = 0; bits <= JZlib.MAX_BITS; bits ++) {
156             s.bl_count[bits] = 0;
157         }
158 
159         // In a first pass, compute the optimal bit lengths (which may
160         // overflow in the case of the bit length tree).
161         tree[s.heap[s.heap_max] * 2 + 1] = 0; // root of the heap
162 
163         for (h = s.heap_max + 1; h < JZlib.HEAP_SIZE; h ++) {
164             n = s.heap[h];
165             bits = tree[tree[n * 2 + 1] * 2 + 1] + 1;
166             if (bits > max_length) {
167                 bits = max_length;
168                 overflow ++;
169             }
170             tree[n * 2 + 1] = (short) bits;
171             // We overwrite tree[n*2+1] which is no longer needed
172 
173             if (n > max_code) {
174                 continue; // not a leaf node
175             }
176 
177             s.bl_count[bits] ++;
178             xbits = 0;
179             if (n >= base) {
180                 xbits = extra[n - base];
181             }
182             f = tree[n * 2];
183             s.opt_len += f * (bits + xbits);
184             if (stree != null) {
185                 s.static_len += f * (stree[n * 2 + 1] + xbits);
186             }
187         }
188         if (overflow == 0) {
189             return;
190         }
191 
192         // This happens for example on obj2 and pic of the Calgary corpus
193         // Find the first bit length which could increase:
194         do {
195             bits = max_length - 1;
196             while (s.bl_count[bits] == 0) {
197                 bits --;
198             }
199             s.bl_count[bits] --; // move one leaf down the tree
200             s.bl_count[bits + 1] += 2; // move one overflow item as its brother
201             s.bl_count[max_length] --;
202             // The brother of the overflow item also moves one step up,
203             // but this does not affect bl_count[max_length]
204             overflow -= 2;
205         } while (overflow > 0);
206 
207         for (bits = max_length; bits != 0; bits --) {
208             n = s.bl_count[bits];
209             while (n != 0) {
210                 m = s.heap[-- h];
211                 if (m > max_code) {
212                     continue;
213                 }
214                 if (tree[m * 2 + 1] != bits) {
215                     s.opt_len += ((long) bits - (long) tree[m * 2 + 1]) *
216                             tree[m * 2];
217                     tree[m * 2 + 1] = (short) bits;
218                 }
219                 n --;
220             }
221         }
222     }
223 
224     // Construct one Huffman tree and assigns the code bit strings and lengths.
225     // Update the total bit length for the current block.
226     // IN assertion: the field freq is set for all tree elements.
227     // OUT assertions: the fields len and code are set to the optimal bit length
228     //     and corresponding code. The length opt_len is updated; static_len is
229     //     also updated if stree is not null. The field max_code is set.
230     void build_tree(Deflate s) {
231         short[] tree = dyn_tree;
232         short[] stree = stat_desc.static_tree;
233         int elems = stat_desc.elems;
234         int n, m; // iterate over heap elements
235         int max_code = -1; // largest code with non zero frequency
236         int node; // new node being created
237 
238         // Construct the initial heap, with least frequent element in
239         // heap[1]. The sons of heap[n] are heap[2*n] and heap[2*n+1].
240         // heap[0] is not used.
241         s.heap_len = 0;
242         s.heap_max = JZlib.HEAP_SIZE;
243 
244         for (n = 0; n < elems; n ++) {
245             if (tree[n * 2] != 0) {
246                 s.heap[++ s.heap_len] = max_code = n;
247                 s.depth[n] = 0;
248             } else {
249                 tree[n * 2 + 1] = 0;
250             }
251         }
252 
253         // The pkzip format requires that at least one distance code exists,
254         // and that at least one bit should be sent even if there is only one
255         // possible code. So to avoid special checks later on we force at least
256         // two codes of non zero frequency.
257         while (s.heap_len < 2) {
258             node = s.heap[++ s.heap_len] = max_code < 2? ++ max_code : 0;
259             tree[node * 2] = 1;
260             s.depth[node] = 0;
261             s.opt_len --;
262             if (stree != null) {
263                 s.static_len -= stree[node * 2 + 1];
264                 // node is 0 or 1 so it does not have extra bits
265             }
266         }
267         this.max_code = max_code;
268 
269         // The elements heap[heap_len/2+1 .. heap_len] are leaves of the tree,
270         // establish sub-heaps of increasing lengths:
271 
272         for (n = s.heap_len / 2; n >= 1; n --) {
273             s.pqdownheap(tree, n);
274         }
275 
276         // Construct the Huffman tree by repeatedly combining the least two
277         // frequent nodes.
278 
279         node = elems; // next internal node of the tree
280         do {
281             // n = node of least frequency
282             n = s.heap[1];
283             s.heap[1] = s.heap[s.heap_len --];
284             s.pqdownheap(tree, 1);
285             m = s.heap[1]; // m = node of next least frequency
286 
287             s.heap[-- s.heap_max] = n; // keep the nodes sorted by frequency
288             s.heap[-- s.heap_max] = m;
289 
290             // Create a new node father of n and m
291             tree[node * 2] = (short) (tree[n * 2] + tree[m * 2]);
292             s.depth[node] = (byte) (Math.max(s.depth[n], s.depth[m]) + 1);
293             tree[n * 2 + 1] = tree[m * 2 + 1] = (short) node;
294 
295             // and insert the new node in the heap
296             s.heap[1] = node ++;
297             s.pqdownheap(tree, 1);
298         } while (s.heap_len >= 2);
299 
300         s.heap[-- s.heap_max] = s.heap[1];
301 
302         // At this point, the fields freq and dad are set. We can now
303         // generate the bit lengths.
304 
305         gen_bitlen(s);
306 
307         // The field len is now set, we can generate the bit codes
308         gen_codes(tree, max_code, s.bl_count);
309     }
310 
311     // Generate the codes for a given tree and bit counts (which need not be
312     // optimal).
313     // IN assertion: the array bl_count contains the bit length statistics for
314     // the given tree and the field len is set for all tree elements.
315     // OUT assertion: the field code is set for all tree elements of non
316     //     zero code length.
317     private static void gen_codes(short[] tree, // the tree to decorate
318             int max_code, // largest code with non zero frequency
319             short[] bl_count // number of codes at each bit length
320     ) {
321         short[] next_code = new short[JZlib.MAX_BITS + 1]; // next code value for each bit length
322         short code = 0; // running code value
323         int bits; // bit index
324         int n; // code index
325 
326         // The distribution counts are first used to generate the code values
327         // without bit reversal.
328         for (bits = 1; bits <= JZlib.MAX_BITS; bits ++) {
329             next_code[bits] = code = (short) (code + bl_count[bits - 1] << 1);
330         }
331 
332         // Check that the bit counts in bl_count are consistent. The last code
333         // must be all ones.
334         //Assert (code + bl_count[MAX_BITS]-1 == (1<<MAX_BITS)-1,
335         //        "inconsistent bit counts");
336         //Tracev((stderr,"\ngen_codes: max_code %d ", max_code));
337 
338         for (n = 0; n <= max_code; n ++) {
339             int len = tree[n * 2 + 1];
340             if (len == 0) {
341                 continue;
342             }
343             // Now reverse the bits
344             tree[n * 2] = (short) bi_reverse(next_code[len] ++, len);
345         }
346     }
347 
348     // Reverse the first len bits of a code, using straightforward code (a faster
349     // method would use a table)
350     // IN assertion: 1 <= len <= 15
351     private static int bi_reverse(int code, // the value to invert
352             int len // its bit length
353     ) {
354         int res = 0;
355         do {
356             res |= code & 1;
357             code >>>= 1;
358             res <<= 1;
359         } while (-- len > 0);
360         return res >>> 1;
361     }
362 }