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