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 - 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 }