Mercurial > 510Connectbot

comparison src/com/jcraft/jzlib/InfBlocks.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 InfBlocks {
38 static final private int MANY = 1440;
39
40 // And'ing with mask[n] masks the lower n bits
41 static final private int[] inflate_mask = {
42 0x00000000, 0x00000001, 0x00000003, 0x00000007, 0x0000000f,
43 0x0000001f, 0x0000003f, 0x0000007f, 0x000000ff, 0x000001ff,
44 0x000003ff, 0x000007ff, 0x00000fff, 0x00001fff, 0x00003fff,
45 0x00007fff, 0x0000ffff
46 };
47
48 // Table for deflate from PKZIP's appnote.txt.
49 static final int[] border = { // Order of the bit length code lengths
50 16, 17, 18, 0, 8, 7, 9, 6, 10, 5, 11, 4, 12, 3, 13, 2, 14, 1, 15
51 };
52
53 static final private int Z_OK = 0;
54 static final private int Z_STREAM_END = 1;
55 static final private int Z_NEED_DICT = 2;
56 static final private int Z_ERRNO = -1;
57 static final private int Z_STREAM_ERROR = -2;
58 static final private int Z_DATA_ERROR = -3;
59 static final private int Z_MEM_ERROR = -4;
60 static final private int Z_BUF_ERROR = -5;
61 static final private int Z_VERSION_ERROR = -6;
62
63 static final private int TYPE = 0; // get type bits (3, including end bit)
64 static final private int LENS = 1; // get lengths for stored
65 static final private int STORED = 2; // processing stored block
66 static final private int TABLE = 3; // get table lengths
67 static final private int BTREE = 4; // get bit lengths tree for a dynamic block
68 static final private int DTREE = 5; // get length, distance trees for a dynamic block
69 static final private int CODES = 6; // processing fixed or dynamic block
70 static final private int DRY = 7; // output remaining window bytes
71 static final private int DONE = 8; // finished last block, done
72 static final private int BAD = 9; // ot a data error--stuck here
73
74 int mode; // current inflate_block mode
75
76 int left; // if STORED, bytes left to copy
77
78 int table; // table lengths (14 bits)
79 int index; // index into blens (or border)
80 int[] blens; // bit lengths of codes
81 int[] bb = new int[1]; // bit length tree depth
82 int[] tb = new int[1]; // bit length decoding tree
83
84 InfCodes codes = new InfCodes(); // if CODES, current state
85
86 int last; // true if this block is the last block
87
88 // mode independent information
89 int bitk; // bits in bit buffer
90 int bitb; // bit buffer
91 int[] hufts; // single malloc for tree space
92 byte[] window; // sliding window
93 int end; // one byte after sliding window
94 int read; // window read pointer
95 int write; // window write pointer
96 Object checkfn; // check function
97 long check; // check on output
98
99 InfTree inftree = new InfTree();
100
101 InfBlocks(ZStream z, Object checkfn, int w) {
102 hufts = new int[MANY * 3];
103 window = new byte[w];
104 end = w;
105 this.checkfn = checkfn;
106 mode = TYPE;
107 reset(z, null);
108 }
109
110 void reset(ZStream z, long[] c) {
111 if (c != null) c[0] = check;
112
113 if (mode == BTREE || mode == DTREE) {
114 }
115
116 if (mode == CODES) {
117 codes.free(z);
118 }
119
120 mode = TYPE;
121 bitk = 0;
122 bitb = 0;
123 read = write = 0;
124
125 if (checkfn != null)
126 z.adler = check = z._adler.adler32(0L, null, 0, 0);
127 }
128
129 int proc(ZStream z, int r) {
130 int t; // temporary storage
131 int b; // bit buffer
132 int k; // bits in bit buffer
133 int p; // input data pointer
134 int n; // bytes available there
135 int q; // output window write pointer
136 int m; // bytes to end of window or read pointer
137 // copy input/output information to locals (UPDATE macro restores)
138 {p = z.next_in_index; n = z.avail_in; b = bitb; k = bitk;}
139 {q = write; m = (int)(q < read ? read - q - 1 : end - q);}
140
141 // process input based on current state
142 while (true) {
143 switch (mode) {
144 case TYPE:
145 while (k < (3)) {
146 if (n != 0) {
147 r = Z_OK;
148 }
149 else {
150 bitb = b; bitk = k;
151 z.avail_in = n;
152 z.total_in += p - z.next_in_index; z.next_in_index = p;
153 write = q;
154 return inflate_flush(z, r);
155 };
156
157 n--;
158
159 b |= (z.next_in[p++] & 0xff) << k;
160
161 k += 8;
162 }
163
164 t = (int)(b & 7);
165 last = t & 1;
166
167 switch (t >>> 1) {
168 case 0: // stored
169 {b >>>= (3); k -= (3);}
170
171 t = k & 7; // go to byte boundary
172 {b >>>= (t); k -= (t);}
173 mode = LENS; // get length of stored block
174 break;
175
176 case 1: { // fixed
177 int[] bl = new int[1];
178 int[] bd = new int[1];
179 int[][] tl = new int[1][];
180 int[][] td = new int[1][];
181 InfTree.inflate_trees_fixed(bl, bd, tl, td, z);
182 codes.init(bl[0], bd[0], tl[0], 0, td[0], 0, z);
183 }
184
185 {b >>>= (3); k -= (3);}
186
187 mode = CODES;
188 break;
189
190 case 2: // dynamic
191 {b >>>= (3); k -= (3);}
192
193 mode = TABLE;
194 break;
195
196 case 3: // illegal
197 {b >>>= (3); k -= (3);}
198
199 mode = BAD;
200 z.msg = "invalid block type";
201 r = Z_DATA_ERROR;
202 bitb = b; bitk = k;
203 z.avail_in = n; z.total_in += p - z.next_in_index; z.next_in_index = p;
204 write = q;
205 return inflate_flush(z, r);
206 }
207
208 break;
209
210 case LENS:
211 while (k < (32)) {
212 if (n != 0) {
213 r = Z_OK;
214 }
215 else {
216 bitb = b; bitk = k;
217 z.avail_in = n;
218 z.total_in += p - z.next_in_index; z.next_in_index = p;
219 write = q;
220 return inflate_flush(z, r);
221 };
222
223 n--;
224
225 b |= (z.next_in[p++] & 0xff) << k;
226
227 k += 8;
228 }
229
230 if ((((~b) >>> 16) & 0xffff) != (b & 0xffff)) {
231 mode = BAD;
232 z.msg = "invalid stored block lengths";
233 r = Z_DATA_ERROR;
234 bitb = b; bitk = k;
235 z.avail_in = n; z.total_in += p - z.next_in_index; z.next_in_index = p;
236 write = q;
237 return inflate_flush(z, r);
238 }
239
240 left = (b & 0xffff);
241 b = k = 0; // dump bits
242 mode = left != 0 ? STORED : (last != 0 ? DRY : TYPE);
243 break;
244
245 case STORED:
246 if (n == 0) {
247 bitb = b; bitk = k;
248 z.avail_in = n; z.total_in += p - z.next_in_index; z.next_in_index = p;
249 write = q;
250 return inflate_flush(z, r);
251 }
252
253 if (m == 0) {
254 if (q == end && read != 0) {
255 q = 0; m = (int)(q < read ? read - q - 1 : end - q);
256 }
257
258 if (m == 0) {
259 write = q;
260 r = inflate_flush(z, r);
261 q = write; m = (int)(q < read ? read - q - 1 : end - q);
262
263 if (q == end && read != 0) {
264 q = 0; m = (int)(q < read ? read - q - 1 : end - q);
265 }
266
267 if (m == 0) {
268 bitb = b; bitk = k;
269 z.avail_in = n; z.total_in += p - z.next_in_index; z.next_in_index = p;
270 write = q;
271 return inflate_flush(z, r);
272 }
273 }
274 }
275
276 r = Z_OK;
277 t = left;
278
279 if (t > n) t = n;
280
281 if (t > m) t = m;
282
283 System.arraycopy(z.next_in, p, window, q, t);
284 p += t; n -= t;
285 q += t; m -= t;
286
287 if ((left -= t) != 0)
288 break;
289
290 mode = last != 0 ? DRY : TYPE;
291 break;
292
293 case TABLE:
294 while (k < (14)) {
295 if (n != 0) {
296 r = Z_OK;
297 }
298 else {
299 bitb = b; bitk = k;
300 z.avail_in = n;
301 z.total_in += p - z.next_in_index; z.next_in_index = p;
302 write = q;
303 return inflate_flush(z, r);
304 };
305
306 n--;
307
308 b |= (z.next_in[p++] & 0xff) << k;
309
310 k += 8;
311 }
312
313 table = t = (b & 0x3fff);
314
315 if ((t & 0x1f) > 29 || ((t >> 5) & 0x1f) > 29) {
316 mode = BAD;
317 z.msg = "too many length or distance symbols";
318 r = Z_DATA_ERROR;
319 bitb = b; bitk = k;
320 z.avail_in = n; z.total_in += p - z.next_in_index; z.next_in_index = p;
321 write = q;
322 return inflate_flush(z, r);
323 }
324
325 t = 258 + (t & 0x1f) + ((t >> 5) & 0x1f);
326
327 if (blens == null || blens.length < t) {
328 blens = new int[t];
329 }
330 else {
331 for (int i = 0; i < t; i++) {blens[i] = 0;}
332 }
333
334 {b >>>= (14); k -= (14);}
335
336 index = 0;
337 mode = BTREE;
338
339 case BTREE:
340 while (index < 4 + (table >>> 10)) {
341 while (k < (3)) {
342 if (n != 0) {
343 r = Z_OK;
344 }
345 else {
346 bitb = b; bitk = k;
347 z.avail_in = n;
348 z.total_in += p - z.next_in_index; z.next_in_index = p;
349 write = q;
350 return inflate_flush(z, r);
351 };
352
353 n--;
354
355 b |= (z.next_in[p++] & 0xff) << k;
356
357 k += 8;
358 }
359
360 blens[border[index++]] = b & 7;
361 {b >>>= (3); k -= (3);}
362 }
363
364 while (index < 19) {
365 blens[border[index++]] = 0;
366 }
367
368 bb[0] = 7;
369 t = inftree.inflate_trees_bits(blens, bb, tb, hufts, z);
370
371 if (t != Z_OK) {
372 r = t;
373
374 if (r == Z_DATA_ERROR) {
375 blens = null;
376 mode = BAD;
377 }
378
379 bitb = b; bitk = k;
380 z.avail_in = n; z.total_in += p - z.next_in_index; z.next_in_index = p;
381 write = q;
382 return inflate_flush(z, r);
383 }
384
385 index = 0;
386 mode = DTREE;
387
388 case DTREE:
389 while (true) {
390 t = table;
391
392 if (!(index < 258 + (t & 0x1f) + ((t >> 5) & 0x1f))) {
393 break;
394 }
395
396 int[] h;
397 int i, j, c;
398 t = bb[0];
399
400 while (k < (t)) {
401 if (n != 0) {
402 r = Z_OK;
403 }
404 else {
405 bitb = b; bitk = k;
406 z.avail_in = n;
407 z.total_in += p - z.next_in_index; z.next_in_index = p;
408 write = q;
409 return inflate_flush(z, r);
410 };
411
412 n--;
413
414 b |= (z.next_in[p++] & 0xff) << k;
415
416 k += 8;
417 }
418
419 if (tb[0] == -1) {
420 //System.err.println("null...");
421 }
422
423 t = hufts[(tb[0] + (b & inflate_mask[t])) * 3 + 1];
424 c = hufts[(tb[0] + (b & inflate_mask[t])) * 3 + 2];
425
426 if (c < 16) {
427 b >>>= (t); k -= (t);
428 blens[index++] = c;
429 }
430 else { // c == 16..18
431 i = c == 18 ? 7 : c - 14;
432 j = c == 18 ? 11 : 3;
433
434 while (k < (t + i)) {
435 if (n != 0) {
436 r = Z_OK;
437 }
438 else {
439 bitb = b; bitk = k;
440 z.avail_in = n;
441 z.total_in += p - z.next_in_index; z.next_in_index = p;
442 write = q;
443 return inflate_flush(z, r);
444 };
445
446 n--;
447
448 b |= (z.next_in[p++] & 0xff) << k;
449
450 k += 8;
451 }
452
453 b >>>= (t); k -= (t);
454 j += (b & inflate_mask[i]);
455 b >>>= (i); k -= (i);
456 i = index;
457 t = table;
458
459 if (i + j > 258 + (t & 0x1f) + ((t >> 5) & 0x1f) ||
460 (c == 16 && i < 1)) {
461 blens = null;
462 mode = BAD;
463 z.msg = "invalid bit length repeat";
464 r = Z_DATA_ERROR;
465 bitb = b; bitk = k;
466 z.avail_in = n; z.total_in += p - z.next_in_index; z.next_in_index = p;
467 write = q;
468 return inflate_flush(z, r);
469 }
470
471 c = c == 16 ? blens[i - 1] : 0;
472
473 do {
474 blens[i++] = c;
475 }
476 while (--j != 0);
477
478 index = i;
479 }
480 }
481
482 tb[0] = -1;
483 {
484 int[] bl = new int[1];
485 int[] bd = new int[1];
486 int[] tl = new int[1];
487 int[] td = new int[1];
488 bl[0] = 9; // must be <= 9 for lookahead assumptions
489 bd[0] = 6; // must be <= 9 for lookahead assumptions
490 t = table;
491 t = inftree.inflate_trees_dynamic(257 + (t & 0x1f),
492 1 + ((t >> 5) & 0x1f),
493 blens, bl, bd, tl, td, hufts, z);
494
495 if (t != Z_OK) {
496 if (t == Z_DATA_ERROR) {
497 blens = null;
498 mode = BAD;
499 }
500
501 r = t;
502 bitb = b; bitk = k;
503 z.avail_in = n; z.total_in += p - z.next_in_index; z.next_in_index = p;
504 write = q;
505 return inflate_flush(z, r);
506 }
507
508 codes.init(bl[0], bd[0], hufts, tl[0], hufts, td[0], z);
509 }
510 mode = CODES;
511
512 case CODES:
513 bitb = b; bitk = k;
514 z.avail_in = n; z.total_in += p - z.next_in_index; z.next_in_index = p;
515 write = q;
516
517 if ((r = codes.proc(this, z, r)) != Z_STREAM_END) {
518 return inflate_flush(z, r);
519 }
520
521 r = Z_OK;
522 codes.free(z);
523 p = z.next_in_index; n = z.avail_in; b = bitb; k = bitk;
524 q = write; m = (int)(q < read ? read - q - 1 : end - q);
525
526 if (last == 0) {
527 mode = TYPE;
528 break;
529 }
530
531 mode = DRY;
532
533 case DRY:
534 write = q;
535 r = inflate_flush(z, r);
536 q = write; m = (int)(q < read ? read - q - 1 : end - q);
537
538 if (read != write) {
539 bitb = b; bitk = k;
540 z.avail_in = n; z.total_in += p - z.next_in_index; z.next_in_index = p;
541 write = q;
542 return inflate_flush(z, r);
543 }
544
545 mode = DONE;
546
547 case DONE:
548 r = Z_STREAM_END;
549 bitb = b; bitk = k;
550 z.avail_in = n; z.total_in += p - z.next_in_index; z.next_in_index = p;
551 write = q;
552 return inflate_flush(z, r);
553
554 case BAD:
555 r = Z_DATA_ERROR;
556 bitb = b; bitk = k;
557 z.avail_in = n; z.total_in += p - z.next_in_index; z.next_in_index = p;
558 write = q;
559 return inflate_flush(z, r);
560
561 default:
562 r = Z_STREAM_ERROR;
563 bitb = b; bitk = k;
564 z.avail_in = n; z.total_in += p - z.next_in_index; z.next_in_index = p;
565 write = q;
566 return inflate_flush(z, r);
567 }
568 }
569 }
570
571 void free(ZStream z) {
572 reset(z, null);
573 window = null;
574 hufts = null;
575 //ZFREE(z, s);
576 }
577
578 void set_dictionary(byte[] d, int start, int n) {
579 System.arraycopy(d, start, window, 0, n);
580 read = write = n;
581 }
582
583 // Returns true if inflate is currently at the end of a block generated
584 // by Z_SYNC_FLUSH or Z_FULL_FLUSH.
585 int sync_point() {
586 return mode == LENS ? 1 : 0;
587 }
588
589 // copy as much as possible from the sliding window to the output area
590 int inflate_flush(ZStream z, int r) {
591 int n;
592 int p;
593 int q;
594 // local copies of source and destination pointers
595 p = z.next_out_index;
596 q = read;
597 // compute number of bytes to copy as far as end of window
598 n = (int)((q <= write ? write : end) - q);
599
600 if (n > z.avail_out) n = z.avail_out;
601
602 if (n != 0 && r == Z_BUF_ERROR) r = Z_OK;
603
604 // update counters
605 z.avail_out -= n;
606 z.total_out += n;
607
608 // update check information
609 if (checkfn != null)
610 z.adler = check = z._adler.adler32(check, window, q, n);
611
612 // copy as far as end of window
613 System.arraycopy(window, q, z.next_out, p, n);
614 p += n;
615 q += n;
616
617 // see if more to copy at beginning of window
618 if (q == end) {
619 // wrap pointers
620 q = 0;
621
622 if (write == end)
623 write = 0;
624
625 // compute bytes to copy
626 n = write - q;
627
628 if (n > z.avail_out) n = z.avail_out;
629
630 if (n != 0 && r == Z_BUF_ERROR) r = Z_OK;
631
632 // update counters
633 z.avail_out -= n;
634 z.total_out += n;
635
636 // update check information
637 if (checkfn != null)
638 z.adler = check = z._adler.adler32(check, window, q, n);
639
640 // copy
641 System.arraycopy(window, q, z.next_out, p, n);
642 p += n;
643 q += n;
644 }
645
646 // update pointers
647 z.next_out_index = p;
648 read = q;
649 // done
650 return r;
651 }
652 }