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 }