1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49 package org.jboss.netty.util.internal.jzlib;
50
51 final class InfTree {
52
53 static final int fixed_bl = 9;
54 static final int fixed_bd = 5;
55
56 static final int[] fixed_tl = { 96, 7, 256, 0, 8, 80, 0, 8, 16, 84, 8, 115,
57 82, 7, 31, 0, 8, 112, 0, 8, 48, 0, 9, 192, 80, 7, 10, 0, 8, 96, 0,
58 8, 32, 0, 9, 160, 0, 8, 0, 0, 8, 128, 0, 8, 64, 0, 9, 224, 80, 7,
59 6, 0, 8, 88, 0, 8, 24, 0, 9, 144, 83, 7, 59, 0, 8, 120, 0, 8, 56,
60 0, 9, 208, 81, 7, 17, 0, 8, 104, 0, 8, 40, 0, 9, 176, 0, 8, 8, 0,
61 8, 136, 0, 8, 72, 0, 9, 240, 80, 7, 4, 0, 8, 84, 0, 8, 20, 85, 8,
62 227, 83, 7, 43, 0, 8, 116, 0, 8, 52, 0, 9, 200, 81, 7, 13, 0, 8,
63 100, 0, 8, 36, 0, 9, 168, 0, 8, 4, 0, 8, 132, 0, 8, 68, 0, 9, 232,
64 80, 7, 8, 0, 8, 92, 0, 8, 28, 0, 9, 152, 84, 7, 83, 0, 8, 124, 0,
65 8, 60, 0, 9, 216, 82, 7, 23, 0, 8, 108, 0, 8, 44, 0, 9, 184, 0, 8,
66 12, 0, 8, 140, 0, 8, 76, 0, 9, 248, 80, 7, 3, 0, 8, 82, 0, 8, 18,
67 85, 8, 163, 83, 7, 35, 0, 8, 114, 0, 8, 50, 0, 9, 196, 81, 7, 11,
68 0, 8, 98, 0, 8, 34, 0, 9, 164, 0, 8, 2, 0, 8, 130, 0, 8, 66, 0, 9,
69 228, 80, 7, 7, 0, 8, 90, 0, 8, 26, 0, 9, 148, 84, 7, 67, 0, 8, 122,
70 0, 8, 58, 0, 9, 212, 82, 7, 19, 0, 8, 106, 0, 8, 42, 0, 9, 180, 0,
71 8, 10, 0, 8, 138, 0, 8, 74, 0, 9, 244, 80, 7, 5, 0, 8, 86, 0, 8,
72 22, 192, 8, 0, 83, 7, 51, 0, 8, 118, 0, 8, 54, 0, 9, 204, 81, 7,
73 15, 0, 8, 102, 0, 8, 38, 0, 9, 172, 0, 8, 6, 0, 8, 134, 0, 8, 70,
74 0, 9, 236, 80, 7, 9, 0, 8, 94, 0, 8, 30, 0, 9, 156, 84, 7, 99, 0,
75 8, 126, 0, 8, 62, 0, 9, 220, 82, 7, 27, 0, 8, 110, 0, 8, 46, 0, 9,
76 188, 0, 8, 14, 0, 8, 142, 0, 8, 78, 0, 9, 252, 96, 7, 256, 0, 8,
77 81, 0, 8, 17, 85, 8, 131, 82, 7, 31, 0, 8, 113, 0, 8, 49, 0, 9,
78 194, 80, 7, 10, 0, 8, 97, 0, 8, 33, 0, 9, 162, 0, 8, 1, 0, 8, 129,
79 0, 8, 65, 0, 9, 226, 80, 7, 6, 0, 8, 89, 0, 8, 25, 0, 9, 146, 83,
80 7, 59, 0, 8, 121, 0, 8, 57, 0, 9, 210, 81, 7, 17, 0, 8, 105, 0, 8,
81 41, 0, 9, 178, 0, 8, 9, 0, 8, 137, 0, 8, 73, 0, 9, 242, 80, 7, 4,
82 0, 8, 85, 0, 8, 21, 80, 8, 258, 83, 7, 43, 0, 8, 117, 0, 8, 53, 0,
83 9, 202, 81, 7, 13, 0, 8, 101, 0, 8, 37, 0, 9, 170, 0, 8, 5, 0, 8,
84 133, 0, 8, 69, 0, 9, 234, 80, 7, 8, 0, 8, 93, 0, 8, 29, 0, 9, 154,
85 84, 7, 83, 0, 8, 125, 0, 8, 61, 0, 9, 218, 82, 7, 23, 0, 8, 109, 0,
86 8, 45, 0, 9, 186, 0, 8, 13, 0, 8, 141, 0, 8, 77, 0, 9, 250, 80, 7,
87 3, 0, 8, 83, 0, 8, 19, 85, 8, 195, 83, 7, 35, 0, 8, 115, 0, 8, 51,
88 0, 9, 198, 81, 7, 11, 0, 8, 99, 0, 8, 35, 0, 9, 166, 0, 8, 3, 0, 8,
89 131, 0, 8, 67, 0, 9, 230, 80, 7, 7, 0, 8, 91, 0, 8, 27, 0, 9, 150,
90 84, 7, 67, 0, 8, 123, 0, 8, 59, 0, 9, 214, 82, 7, 19, 0, 8, 107, 0,
91 8, 43, 0, 9, 182, 0, 8, 11, 0, 8, 139, 0, 8, 75, 0, 9, 246, 80, 7,
92 5, 0, 8, 87, 0, 8, 23, 192, 8, 0, 83, 7, 51, 0, 8, 119, 0, 8, 55,
93 0, 9, 206, 81, 7, 15, 0, 8, 103, 0, 8, 39, 0, 9, 174, 0, 8, 7, 0,
94 8, 135, 0, 8, 71, 0, 9, 238, 80, 7, 9, 0, 8, 95, 0, 8, 31, 0, 9,
95 158, 84, 7, 99, 0, 8, 127, 0, 8, 63, 0, 9, 222, 82, 7, 27, 0, 8,
96 111, 0, 8, 47, 0, 9, 190, 0, 8, 15, 0, 8, 143, 0, 8, 79, 0, 9, 254,
97 96, 7, 256, 0, 8, 80, 0, 8, 16, 84, 8, 115, 82, 7, 31, 0, 8, 112,
98 0, 8, 48, 0, 9, 193,
99 80, 7, 10, 0, 8, 96, 0, 8, 32, 0, 9, 161, 0, 8, 0, 0, 8, 128, 0, 8,
100 64, 0, 9, 225, 80, 7, 6, 0, 8, 88, 0, 8, 24, 0, 9, 145, 83, 7, 59,
101 0, 8, 120, 0, 8, 56, 0, 9, 209, 81, 7, 17, 0, 8, 104, 0, 8, 40, 0,
102 9, 177, 0, 8, 8, 0, 8, 136, 0, 8, 72, 0, 9, 241, 80, 7, 4, 0, 8,
103 84, 0, 8, 20, 85, 8, 227, 83, 7, 43, 0, 8, 116, 0, 8, 52, 0, 9,
104 201, 81, 7, 13, 0, 8, 100, 0, 8, 36, 0, 9, 169, 0, 8, 4, 0, 8, 132,
105 0, 8, 68, 0, 9, 233, 80, 7, 8, 0, 8, 92, 0, 8, 28, 0, 9, 153, 84,
106 7, 83, 0, 8, 124, 0, 8, 60, 0, 9, 217, 82, 7, 23, 0, 8, 108, 0, 8,
107 44, 0, 9, 185, 0, 8, 12, 0, 8, 140, 0, 8, 76, 0, 9, 249, 80, 7, 3,
108 0, 8, 82, 0, 8, 18, 85, 8, 163, 83, 7, 35, 0, 8, 114, 0, 8, 50, 0,
109 9, 197, 81, 7, 11, 0, 8, 98, 0, 8, 34, 0, 9, 165, 0, 8, 2, 0, 8,
110 130, 0, 8, 66, 0, 9, 229, 80, 7, 7, 0, 8, 90, 0, 8, 26, 0, 9, 149,
111 84, 7, 67, 0, 8, 122, 0, 8, 58, 0, 9, 213, 82, 7, 19, 0, 8, 106, 0,
112 8, 42, 0, 9, 181, 0, 8, 10, 0, 8, 138, 0, 8, 74, 0, 9, 245, 80, 7,
113 5, 0, 8, 86, 0, 8, 22, 192, 8, 0, 83, 7, 51, 0, 8, 118, 0, 8, 54,
114 0, 9, 205, 81, 7, 15, 0, 8, 102, 0, 8, 38, 0, 9, 173, 0, 8, 6, 0,
115 8, 134, 0, 8, 70, 0, 9, 237, 80, 7, 9, 0, 8, 94, 0, 8, 30, 0, 9,
116 157, 84, 7, 99, 0, 8, 126, 0, 8, 62, 0, 9, 221, 82, 7, 27, 0, 8,
117 110, 0, 8, 46, 0, 9, 189, 0, 8, 14, 0, 8, 142, 0, 8, 78, 0, 9, 253,
118 96, 7, 256, 0, 8, 81, 0, 8, 17, 85, 8, 131, 82, 7, 31, 0, 8, 113,
119 0, 8, 49, 0, 9, 195, 80, 7, 10, 0, 8, 97, 0, 8, 33, 0, 9, 163, 0,
120 8, 1, 0, 8, 129, 0, 8, 65, 0, 9, 227, 80, 7, 6, 0, 8, 89, 0, 8, 25,
121 0, 9, 147, 83, 7, 59, 0, 8, 121, 0, 8, 57, 0, 9, 211, 81, 7, 17, 0,
122 8, 105, 0, 8, 41, 0, 9, 179, 0, 8, 9, 0, 8, 137, 0, 8, 73, 0, 9,
123 243, 80, 7, 4, 0, 8, 85, 0, 8, 21, 80, 8, 258, 83, 7, 43, 0, 8,
124 117, 0, 8, 53, 0, 9, 203, 81, 7, 13, 0, 8, 101, 0, 8, 37, 0, 9,
125 171, 0, 8, 5, 0, 8, 133, 0, 8, 69, 0, 9, 235, 80, 7, 8, 0, 8, 93,
126 0, 8, 29, 0, 9, 155, 84, 7, 83, 0, 8, 125, 0, 8, 61, 0, 9, 219, 82,
127 7, 23, 0, 8, 109, 0, 8, 45, 0, 9, 187, 0, 8, 13, 0, 8, 141, 0, 8,
128 77, 0, 9, 251, 80, 7, 3, 0, 8, 83, 0, 8, 19, 85, 8, 195, 83, 7, 35,
129 0, 8, 115, 0, 8, 51, 0, 9, 199, 81, 7, 11, 0, 8, 99, 0, 8, 35, 0,
130 9, 167, 0, 8, 3, 0, 8, 131, 0, 8, 67, 0, 9, 231, 80, 7, 7, 0, 8,
131 91, 0, 8, 27, 0, 9, 151, 84, 7, 67, 0, 8, 123, 0, 8, 59, 0, 9, 215,
132 82, 7, 19, 0, 8, 107, 0, 8, 43, 0, 9, 183, 0, 8, 11, 0, 8, 139, 0,
133 8, 75, 0, 9, 247, 80, 7, 5, 0, 8, 87, 0, 8, 23, 192, 8, 0, 83, 7,
134 51, 0, 8, 119, 0, 8, 55, 0, 9, 207, 81, 7, 15, 0, 8, 103, 0, 8, 39,
135 0, 9, 175, 0, 8, 7, 0, 8, 135, 0, 8, 71, 0, 9, 239, 80, 7, 9, 0, 8,
136 95, 0, 8, 31, 0, 9, 159, 84, 7, 99, 0, 8, 127, 0, 8, 63, 0, 9, 223,
137 82, 7, 27, 0, 8, 111, 0, 8, 47, 0, 9, 191, 0, 8, 15, 0, 8, 143, 0,
138 8, 79, 0, 9, 255 };
139
140 static final int[] fixed_td = { 80, 5, 1, 87, 5, 257, 83, 5, 17, 91, 5,
141 4097, 81, 5, 5, 89, 5, 1025, 85, 5, 65, 93, 5, 16385, 80, 5, 3, 88,
142 5, 513, 84, 5, 33, 92, 5, 8193, 82, 5, 9, 90, 5, 2049, 86, 5, 129,
143 192, 5, 24577, 80, 5, 2, 87, 5, 385, 83, 5, 25, 91, 5, 6145, 81, 5,
144 7, 89, 5, 1537, 85, 5, 97, 93, 5, 24577, 80, 5, 4, 88, 5, 769, 84,
145 5, 49, 92, 5, 12289, 82, 5, 13, 90, 5, 3073, 86, 5, 193, 192, 5,
146 24577 };
147
148
149 static final int[] cplens = {
150 3, 4, 5, 6, 7, 8, 9, 10, 11, 13, 15, 17, 19, 23, 27, 31, 35, 43, 51, 59,
151 67, 83, 99, 115, 131, 163, 195, 227, 258, 0, 0 };
152
153
154 static final int[] cplext = {
155 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,
156 5, 5, 5, 0, 112, 112
157 };
158
159 static final int[] cpdist = {
160 1, 2, 3, 4, 5, 7, 9, 13, 17, 25, 33, 49, 65, 97, 129, 193, 257, 385, 513,
161 769, 1025, 1537, 2049, 3073, 4097, 6145, 8193, 12289, 16385, 24577 };
162
163 static final int[] cpdext = {
164 0, 0, 0, 0, 1, 1, 2, 2, 3, 3, 4, 4, 5, 5, 6, 6, 7, 7, 8, 8, 9, 9, 10, 10,
165 11, 11, 12, 12, 13, 13 };
166
167
168 static final int BMAX = 15;
169
170 private int[] hn;
171 private int[] v;
172 private int[] c;
173 private int[] r;
174 private int[] u;
175 private int[] x;
176
177 private int huft_build(int[] b,
178 int bindex, int n,
179 int s,
180 int[] d,
181 int[] e,
182 int[] t,
183 int[] m,
184 int[] hp,
185 int[] hn,
186 int[] v
187 ) {
188
189
190
191
192
193
194 int a;
195 int f;
196 int g;
197 int h;
198 int i;
199 int j;
200 int k;
201 int l;
202 int mask;
203 int p;
204 int q;
205 int w;
206 int xp;
207 int y;
208 int z;
209
210
211
212 p = 0;
213 i = n;
214 do {
215 c[b[bindex + p]] ++;
216 p ++;
217 i --;
218 } while (i != 0);
219
220 if (c[0] == n) {
221 t[0] = -1;
222 m[0] = 0;
223 return JZlib.Z_OK;
224 }
225
226
227 l = m[0];
228 for (j = 1; j <= BMAX; j ++) {
229 if (c[j] != 0) {
230 break;
231 }
232 }
233 k = j;
234 if (l < j) {
235 l = j;
236 }
237 for (i = BMAX; i != 0; i --) {
238 if (c[i] != 0) {
239 break;
240 }
241 }
242 g = i;
243 if (l > i) {
244 l = i;
245 }
246 m[0] = l;
247
248
249 for (y = 1 << j; j < i; j ++, y <<= 1) {
250 if ((y -= c[j]) < 0) {
251 return JZlib.Z_DATA_ERROR;
252 }
253 }
254 if ((y -= c[i]) < 0) {
255 return JZlib.Z_DATA_ERROR;
256 }
257 c[i] += y;
258
259
260 x[1] = j = 0;
261 p = 1;
262 xp = 2;
263 while (-- i != 0) {
264 x[xp] = j += c[p];
265 xp ++;
266 p ++;
267 }
268
269
270 i = 0;
271 p = 0;
272 do {
273 if ((j = b[bindex + p]) != 0) {
274 v[x[j] ++] = i;
275 }
276 p ++;
277 } while (++ i < n);
278 n = x[g];
279
280
281 x[0] = i = 0;
282 p = 0;
283 h = -1;
284 w = -l;
285 u[0] = 0;
286 q = 0;
287 z = 0;
288
289
290 for (; k <= g; k ++) {
291 a = c[k];
292 while (a -- != 0) {
293
294
295 while (k > w + l) {
296 h ++;
297 w += l;
298
299 z = g - w;
300 z = z > l? l : z;
301 if ((f = 1 << (j = k - w)) > a + 1) {
302
303 f -= a + 1;
304 xp = k;
305 if (j < z) {
306 while (++ j < z) {
307 if ((f <<= 1) <= c[++ xp]) {
308 break;
309 }
310 f -= c[xp];
311 }
312 }
313 }
314 z = 1 << j;
315
316
317 if (hn[0] + z > JZlib.MANY) {
318 return JZlib.Z_DATA_ERROR;
319 }
320 u[h] = q =
321 hn[0] += z;
322
323
324 if (h != 0) {
325 x[h] = i;
326 r[0] = (byte) j;
327 r[1] = (byte) l;
328 j = i >>> w - l;
329 r[2] = q - u[h - 1] - j;
330 System.arraycopy(r, 0, hp, (u[h - 1] + j) * 3, 3);
331 } else {
332 t[0] = q;
333 }
334 }
335
336
337 r[1] = (byte) (k - w);
338 if (p >= n) {
339 r[0] = 128 + 64;
340 } else if (v[p] < s) {
341 r[0] = (byte) (v[p] < 256? 0 : 32 + 64);
342 r[2] = v[p ++];
343 } else {
344 r[0] = (byte) (e[v[p] - s] + 16 + 64);
345 r[2] = d[v[p ++] - s];
346 }
347
348
349 f = 1 << k - w;
350 for (j = i >>> w; j < z; j += f) {
351 System.arraycopy(r, 0, hp, (q + j) * 3, 3);
352 }
353
354
355 for (j = 1 << k - 1; (i & j) != 0; j >>>= 1) {
356 i ^= j;
357 }
358 i ^= j;
359
360
361 mask = (1 << w) - 1;
362 while ((i & mask) != x[h]) {
363 h --;
364 w -= l;
365 mask = (1 << w) - 1;
366 }
367 }
368 }
369
370 return y != 0 && g != 1? JZlib.Z_BUF_ERROR : JZlib.Z_OK;
371 }
372
373 int inflate_trees_bits(int[] c,
374 int[] bb,
375 int[] tb,
376 int[] hp,
377 ZStream z
378 ) {
379 int result;
380 initWorkArea(19);
381 hn[0] = 0;
382 result = huft_build(c, 0, 19, 19, null, null, tb, bb, hp, hn, v);
383
384 if (result == JZlib.Z_DATA_ERROR) {
385 z.msg = "oversubscribed dynamic bit lengths tree";
386 } else if (result == JZlib.Z_BUF_ERROR || bb[0] == 0) {
387 z.msg = "incomplete dynamic bit lengths tree";
388 result = JZlib.Z_DATA_ERROR;
389 }
390 return result;
391 }
392
393 int inflate_trees_dynamic(int nl,
394 int nd,
395 int[] c,
396 int[] bl,
397 int[] bd,
398 int[] tl,
399 int[] td,
400 int[] hp,
401 ZStream z
402 ) {
403 int result;
404
405
406 initWorkArea(288);
407 hn[0] = 0;
408 result = huft_build(c, 0, nl, 257, cplens, cplext, tl, bl, hp, hn, v);
409 if (result != JZlib.Z_OK || bl[0] == 0) {
410 if (result == JZlib.Z_DATA_ERROR) {
411 z.msg = "oversubscribed literal/length tree";
412 } else if (result != JZlib.Z_MEM_ERROR) {
413 z.msg = "incomplete literal/length tree";
414 result = JZlib.Z_DATA_ERROR;
415 }
416 return result;
417 }
418
419
420 initWorkArea(288);
421 result = huft_build(c, nl, nd, 0, cpdist, cpdext, td, bd, hp, hn, v);
422
423 if (result != JZlib.Z_OK || bd[0] == 0 && nl > 257) {
424 if (result == JZlib.Z_DATA_ERROR) {
425 z.msg = "oversubscribed distance tree";
426 } else if (result == JZlib.Z_BUF_ERROR) {
427 z.msg = "incomplete distance tree";
428 result = JZlib.Z_DATA_ERROR;
429 } else if (result != JZlib.Z_MEM_ERROR) {
430 z.msg = "empty distance tree with lengths";
431 result = JZlib.Z_DATA_ERROR;
432 }
433 return result;
434 }
435
436 return JZlib.Z_OK;
437 }
438
439 static int inflate_trees_fixed(int[] bl,
440 int[] bd,
441 int[][] tl,
442 int[][] td
443 ) {
444 bl[0] = fixed_bl;
445 bd[0] = fixed_bd;
446 tl[0] = fixed_tl;
447 td[0] = fixed_td;
448 return JZlib.Z_OK;
449 }
450
451 private void initWorkArea(int vsize) {
452 if (hn == null) {
453 hn = new int[1];
454 v = new int[vsize];
455 c = new int[BMAX + 1];
456 r = new int[3];
457 u = new int[BMAX];
458 x = new int[BMAX + 1];
459 } else {
460 if (v.length < vsize) {
461 v = new int[vsize];
462 } else {
463 for (int i = 0; i < vsize; i ++) {
464 v[i] = 0;
465 }
466 }
467 for (int i = 0; i < BMAX + 1; i ++) {
468 c[i] = 0;
469 }
470 for (int i = 0; i < 3; i ++) {
471 r[i] = 0;
472 }
473
474 System.arraycopy(c, 0, u, 0, BMAX);
475
476 System.arraycopy(c, 0, x, 0, BMAX + 1);
477 }
478 }
479 }