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