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