Mercurial > 510Connectbot

comparison src/com/jcraft/jzlib/Tree.java @ 0:0ce5cc452d02

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