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 InfCodes {
52
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 // waiting for "i:"=input,
59 // "o:"=output,
60 // "x:"=nothing
61 private static final int START = 0; // x: set up for LEN
62 private static final int LEN = 1; // i: get length/literal/eob next
63 private static final int LENEXT = 2; // i: getting length extra (have base)
64 private static final int DIST = 3; // i: get distance next
65 private static final int DISTEXT = 4; // i: getting distance extra
66 private static final int COPY = 5; // o: copying bytes in window, waiting for space
67 private static final int LIT = 6; // o: got literal, waiting for output space
68 private static final int WASH = 7; // o: got eob, possibly still output waiting
69 private static final int END = 8; // x: got eob and all data flushed
70 private static final int BADCODE = 9; // x: got error
71 private int mode; // current inflate_codes mode
72 // mode dependent information
73 private int len;
74 private int[] tree; // pointer into tree
75 private int tree_index = 0;
76 private int need; // bits needed
77 private int lit;
78 // if EXT or COPY, where and how much
79 private int get; // bits to get for extra
80 private int dist; // distance back to copy from
81 private byte lbits; // ltree bits decoded per branch
82 private byte dbits; // dtree bits decoder per branch
83 private int[] ltree; // literal/length/eob tree
84 private int ltree_index; // literal/length/eob tree
85 private int[] dtree; // distance tree
86 private int dtree_index; // distance tree
87
88 InfCodes() {
89 super();
90 }
91
92 void init(int bl, int bd, int[] tl, int tl_index, int[] td, int td_index) {
93 mode = START;
94 lbits = (byte) bl;
95 dbits = (byte) bd;
96 ltree = tl;
97 ltree_index = tl_index;
98 dtree = td;
99 dtree_index = td_index;
100 tree = null;
101 }
102
103 int proc(InfBlocks s, ZStream z, int r) {
104 int j; // temporary storage
105 int tindex; // temporary pointer
106 int e; // extra bits or operation
107 int b = 0; // bit buffer
108 int k = 0; // bits in bit buffer
109 int p = 0; // input data pointer
110 int n; // bytes available there
111 int q; // output window write pointer
112 int m; // bytes to end of window or read pointer
113 int f; // pointer to copy strings from
114
115 // copy input/output information to locals (UPDATE macro restores)
116 p = z.next_in_index;
117 n = z.avail_in;
118 b = s.bitb;
119 k = s.bitk;
120 q = s.write;
121 m = q < s.read? s.read - q - 1 : s.end - q;
122
123 // process input and output based on current state
124 while (true) {
125 switch (mode) {
126 // waiting for "i:"=input, "o:"=output, "x:"=nothing
127 case START: // x: set up for LEN
128 if (m >= 258 && n >= 10) {
129
130 s.bitb = b;
131 s.bitk = k;
132 z.avail_in = n;
133 z.total_in += p - z.next_in_index;
134 z.next_in_index = p;
135 s.write = q;
136 r = inflate_fast(lbits, dbits, ltree, ltree_index, dtree,
137 dtree_index, s, z);
138
139 p = z.next_in_index;
140 n = z.avail_in;
141 b = s.bitb;
142 k = s.bitk;
143 q = s.write;
144 m = q < s.read? s.read - q - 1 : s.end - q;
145
146 if (r != JZlib.Z_OK) {
147 mode = r == JZlib.Z_STREAM_END? WASH : BADCODE;
148 break;
149 }
150 }
151 need = lbits;
152 tree = ltree;
153 tree_index = ltree_index;
154
155 mode = LEN;
156 case LEN: // i: get length/literal/eob next
157 j = need;
158
159 while (k < j) {
160 if (n != 0) {
161 r = JZlib.Z_OK;
162 } else {
163
164 s.bitb = b;
165 s.bitk = k;
166 z.avail_in = n;
167 z.total_in += p - z.next_in_index;
168 z.next_in_index = p;
169 s.write = q;
170 return s.inflate_flush(z, r);
171 }
172 n --;
173 b |= (z.next_in[p ++] & 0xff) << k;
174 k += 8;
175 }
176
177 tindex = (tree_index + (b & inflate_mask[j])) * 3;
178
179 b >>>= tree[tindex + 1];
180 k -= tree[tindex + 1];
181
182 e = tree[tindex];
183
184 if (e == 0) { // literal
185 lit = tree[tindex + 2];
186 mode = LIT;
187 break;
188 }
189 if ((e & 16) != 0) { // length
190 get = e & 15;
191 len = tree[tindex + 2];
192 mode = LENEXT;
193 break;
194 }
195 if ((e & 64) == 0) { // next table
196 need = e;
197 tree_index = tindex / 3 + tree[tindex + 2];
198 break;
199 }
200 if ((e & 32) != 0) { // end of block
201 mode = WASH;
202 break;
203 }
204 mode = BADCODE; // invalid code
205 z.msg = "invalid literal/length code";
206 r = JZlib.Z_DATA_ERROR;
207
208 s.bitb = b;
209 s.bitk = k;
210 z.avail_in = n;
211 z.total_in += p - z.next_in_index;
212 z.next_in_index = p;
213 s.write = q;
214 return s.inflate_flush(z, r);
215
216 case LENEXT: // i: getting length extra (have base)
217 j = get;
218
219 while (k < j) {
220 if (n != 0) {
221 r = JZlib.Z_OK;
222 } else {
223
224 s.bitb = b;
225 s.bitk = k;
226 z.avail_in = n;
227 z.total_in += p - z.next_in_index;
228 z.next_in_index = p;
229 s.write = q;
230 return s.inflate_flush(z, r);
231 }
232 n --;
233 b |= (z.next_in[p ++] & 0xff) << k;
234 k += 8;
235 }
236
237 len += b & inflate_mask[j];
238
239 b >>= j;
240 k -= j;
241
242 need = dbits;
243 tree = dtree;
244 tree_index = dtree_index;
245 mode = DIST;
246 case DIST: // i: get distance next
247 j = need;
248
249 while (k < j) {
250 if (n != 0) {
251 r = JZlib.Z_OK;
252 } else {
253
254 s.bitb = b;
255 s.bitk = k;
256 z.avail_in = n;
257 z.total_in += p - z.next_in_index;
258 z.next_in_index = p;
259 s.write = q;
260 return s.inflate_flush(z, r);
261 }
262 n --;
263 b |= (z.next_in[p ++] & 0xff) << k;
264 k += 8;
265 }
266
267 tindex = (tree_index + (b & inflate_mask[j])) * 3;
268
269 b >>= tree[tindex + 1];
270 k -= tree[tindex + 1];
271
272 e = tree[tindex];
273 if ((e & 16) != 0) { // distance
274 get = e & 15;
275 dist = tree[tindex + 2];
276 mode = DISTEXT;
277 break;
278 }
279 if ((e & 64) == 0) { // next table
280 need = e;
281 tree_index = tindex / 3 + tree[tindex + 2];
282 break;
283 }
284 mode = BADCODE; // invalid code
285 z.msg = "invalid distance code";
286 r = JZlib.Z_DATA_ERROR;
287
288 s.bitb = b;
289 s.bitk = k;
290 z.avail_in = n;
291 z.total_in += p - z.next_in_index;
292 z.next_in_index = p;
293 s.write = q;
294 return s.inflate_flush(z, r);
295
296 case DISTEXT: // i: getting distance extra
297 j = get;
298
299 while (k < j) {
300 if (n != 0) {
301 r = JZlib.Z_OK;
302 } else {
303
304 s.bitb = b;
305 s.bitk = k;
306 z.avail_in = n;
307 z.total_in += p - z.next_in_index;
308 z.next_in_index = p;
309 s.write = q;
310 return s.inflate_flush(z, r);
311 }
312 n --;
313 b |= (z.next_in[p ++] & 0xff) << k;
314 k += 8;
315 }
316
317 dist += b & inflate_mask[j];
318
319 b >>= j;
320 k -= j;
321
322 mode = COPY;
323 case COPY: // o: copying bytes in window, waiting for space
324 f = q - dist;
325 while (f < 0) { // modulo window size-"while" instead
326 f += s.end; // of "if" handles invalid distances
327 }
328 while (len != 0) {
329
330 if (m == 0) {
331 if (q == s.end && s.read != 0) {
332 q = 0;
333 m = q < s.read? s.read - q - 1 : s.end - q;
334 }
335 if (m == 0) {
336 s.write = q;
337 r = s.inflate_flush(z, r);
338 q = s.write;
339 m = q < s.read? s.read - q - 1 : s.end - q;
340
341 if (q == s.end && s.read != 0) {
342 q = 0;
343 m = q < s.read? s.read - q - 1 : s.end - q;
344 }
345
346 if (m == 0) {
347 s.bitb = b;
348 s.bitk = k;
349 z.avail_in = n;
350 z.total_in += p - z.next_in_index;
351 z.next_in_index = p;
352 s.write = q;
353 return s.inflate_flush(z, r);
354 }
355 }
356 }
357
358 s.window[q ++] = s.window[f ++];
359 m --;
360
361 if (f == s.end) {
362 f = 0;
363 }
364 len --;
365 }
366 mode = START;
367 break;
368 case LIT: // o: got literal, waiting for output space
369 if (m == 0) {
370 if (q == s.end && s.read != 0) {
371 q = 0;
372 m = q < s.read? s.read - q - 1 : s.end - q;
373 }
374 if (m == 0) {
375 s.write = q;
376 r = s.inflate_flush(z, r);
377 q = s.write;
378 m = q < s.read? s.read - q - 1 : s.end - q;
379
380 if (q == s.end && s.read != 0) {
381 q = 0;
382 m = q < s.read? s.read - q - 1 : s.end - q;
383 }
384 if (m == 0) {
385 s.bitb = b;
386 s.bitk = k;
387 z.avail_in = n;
388 z.total_in += p - z.next_in_index;
389 z.next_in_index = p;
390 s.write = q;
391 return s.inflate_flush(z, r);
392 }
393 }
394 }
395 r = JZlib.Z_OK;
396
397 s.window[q ++] = (byte) lit;
398 m --;
399
400 mode = START;
401 break;
402 case WASH: // o: got eob, possibly more output
403 if (k > 7) { // return unused byte, if any
404 k -= 8;
405 n ++;
406 p --; // can always return one
407 }
408
409 s.write = q;
410 r = s.inflate_flush(z, r);
411 q = s.write;
412
413 if (s.read != s.write) {
414 s.bitb = b;
415 s.bitk = k;
416 z.avail_in = n;
417 z.total_in += p - z.next_in_index;
418 z.next_in_index = p;
419 s.write = q;
420 return s.inflate_flush(z, r);
421 }
422 mode = END;
423 case END:
424 r = JZlib.Z_STREAM_END;
425 s.bitb = b;
426 s.bitk = k;
427 z.avail_in = n;
428 z.total_in += p - z.next_in_index;
429 z.next_in_index = p;
430 s.write = q;
431 return s.inflate_flush(z, r);
432
433 case BADCODE: // x: got error
434
435 r = JZlib.Z_DATA_ERROR;
436
437 s.bitb = b;
438 s.bitk = k;
439 z.avail_in = n;
440 z.total_in += p - z.next_in_index;
441 z.next_in_index = p;
442 s.write = q;
443 return s.inflate_flush(z, r);
444
445 default:
446 r = JZlib.Z_STREAM_ERROR;
447
448 s.bitb = b;
449 s.bitk = k;
450 z.avail_in = n;
451 z.total_in += p - z.next_in_index;
452 z.next_in_index = p;
453 s.write = q;
454 return s.inflate_flush(z, r);
455 }
456 }
457 }
458
459 // Called with number of bytes left to write in window at least 258
460 // (the maximum string length) and number of input bytes available
461 // at least ten. The ten bytes are six bytes for the longest length/
462 // distance pair plus four bytes for overloading the bit buffer.
463
464 int inflate_fast(int bl, int bd, int[] tl, int tl_index, int[] td,
465 int td_index, InfBlocks s, ZStream z) {
466 int t; // temporary pointer
467 int[] tp; // temporary pointer
468 int tp_index; // temporary pointer
469 int e; // extra bits or operation
470 int b; // bit buffer
471 int k; // bits in bit buffer
472 int p; // input data pointer
473 int n; // bytes available there
474 int q; // output window write pointer
475 int m; // bytes to end of window or read pointer
476 int ml; // mask for literal/length tree
477 int md; // mask for distance tree
478 int c; // bytes to copy
479 int d; // distance back to copy from
480 int r; // copy source pointer
481
482 int tp_index_t_3; // (tp_index+t)*3
483
484 // load input, output, bit values
485 p = z.next_in_index;
486 n = z.avail_in;
487 b = s.bitb;
488 k = s.bitk;
489 q = s.write;
490 m = q < s.read? s.read - q - 1 : s.end - q;
491
492 // initialize masks
493 ml = inflate_mask[bl];
494 md = inflate_mask[bd];
495
496 // do until not enough input or output space for fast loop
497 do { // assume called with m >= 258 && n >= 10
498 // get literal/length code
499 while (k < 20) { // max bits for literal/length code
500 n --;
501 b |= (z.next_in[p ++] & 0xff) << k;
502 k += 8;
503 }
504
505 t = b & ml;
506 tp = tl;
507 tp_index = tl_index;
508 tp_index_t_3 = (tp_index + t) * 3;
509 if ((e = tp[tp_index_t_3]) == 0) {
510 b >>= tp[tp_index_t_3 + 1];
511 k -= tp[tp_index_t_3 + 1];
512
513 s.window[q ++] = (byte) tp[tp_index_t_3 + 2];
514 m --;
515 continue;
516 }
517 do {
518
519 b >>= tp[tp_index_t_3 + 1];
520 k -= tp[tp_index_t_3 + 1];
521
522 if ((e & 16) != 0) {
523 e &= 15;
524 c = tp[tp_index_t_3 + 2] + (b & inflate_mask[e]);
525
526 b >>= e;
527 k -= e;
528
529 // decode distance base of block to copy
530 while (k < 15) { // max bits for distance code
531 n --;
532 b |= (z.next_in[p ++] & 0xff) << k;
533 k += 8;
534 }
535
536 t = b & md;
537 tp = td;
538 tp_index = td_index;
539 tp_index_t_3 = (tp_index + t) * 3;
540 e = tp[tp_index_t_3];
541
542 do {
543
544 b >>= tp[tp_index_t_3 + 1];
545 k -= tp[tp_index_t_3 + 1];
546
547 if ((e & 16) != 0) {
548 // get extra bits to add to distance base
549 e &= 15;
550 while (k < e) { // get extra bits (up to 13)
551 n --;
552 b |= (z.next_in[p ++] & 0xff) << k;
553 k += 8;
554 }
555
556 d = tp[tp_index_t_3 + 2] + (b & inflate_mask[e]);
557
558 b >>= e;
559 k -= e;
560
561 // do the copy
562 m -= c;
563 if (q >= d) { // offset before dest
564 // just copy
565 r = q - d;
566 if (q - r > 0 && 2 > q - r) {
567 s.window[q ++] = s.window[r ++]; // minimum count is three,
568 s.window[q ++] = s.window[r ++]; // so unroll loop a little
569 c -= 2;
570 } else {
571 System.arraycopy(s.window, r, s.window, q,
572 2);
573 q += 2;
574 r += 2;
575 c -= 2;
576 }
577 } else { // else offset after destination
578 r = q - d;
579 do {
580 r += s.end; // force pointer in window
581 } while (r < 0); // covers invalid distances
582 e = s.end - r;
583 if (c > e) { // if source crosses,
584 c -= e; // wrapped copy
585 if (q - r > 0 && e > q - r) {
586 do {
587 s.window[q ++] = s.window[r ++];
588 } while (-- e != 0);
589 } else {
590 System.arraycopy(s.window, r, s.window,
591 q, e);
592 q += e;
593 r += e;
594 e = 0;
595 }
596 r = 0; // copy rest from start of window
597 }
598
599 }
600
601 // copy all or what's left
602 if (q - r > 0 && c > q - r) {
603 do {
604 s.window[q ++] = s.window[r ++];
605 } while (-- c != 0);
606 } else {
607 System.arraycopy(s.window, r, s.window, q, c);
608 q += c;
609 r += c;
610 c = 0;
611 }
612 break;
613 } else if ((e & 64) == 0) {
614 t += tp[tp_index_t_3 + 2];
615 t += b & inflate_mask[e];
616 tp_index_t_3 = (tp_index + t) * 3;
617 e = tp[tp_index_t_3];
618 } else {
619 z.msg = "invalid distance code";
620
621 c = z.avail_in - n;
622 c = k >> 3 < c? k >> 3 : c;
623 n += c;
624 p -= c;
625 k -= c << 3;
626
627 s.bitb = b;
628 s.bitk = k;
629 z.avail_in = n;
630 z.total_in += p - z.next_in_index;
631 z.next_in_index = p;
632 s.write = q;
633
634 return JZlib.Z_DATA_ERROR;
635 }
636 } while (true);
637 break;
638 }
639
640 if ((e & 64) == 0) {
641 t += tp[tp_index_t_3 + 2];
642 t += b & inflate_mask[e];
643 tp_index_t_3 = (tp_index + t) * 3;
644 if ((e = tp[tp_index_t_3]) == 0) {
645
646 b >>= tp[tp_index_t_3 + 1];
647 k -= tp[tp_index_t_3 + 1];
648
649 s.window[q ++] = (byte) tp[tp_index_t_3 + 2];
650 m --;
651 break;
652 }
653 } else if ((e & 32) != 0) {
654
655 c = z.avail_in - n;
656 c = k >> 3 < c? k >> 3 : c;
657 n += c;
658 p -= c;
659 k -= c << 3;
660
661 s.bitb = b;
662 s.bitk = k;
663 z.avail_in = n;
664 z.total_in += p - z.next_in_index;
665 z.next_in_index = p;
666 s.write = q;
667
668 return JZlib.Z_STREAM_END;
669 } else {
670 z.msg = "invalid literal/length code";
671
672 c = z.avail_in - n;
673 c = k >> 3 < c? k >> 3 : c;
674 n += c;
675 p -= c;
676 k -= c << 3;
677
678 s.bitb = b;
679 s.bitk = k;
680 z.avail_in = n;
681 z.total_in += p - z.next_in_index;
682 z.next_in_index = p;
683 s.write = q;
684
685 return JZlib.Z_DATA_ERROR;
686 }
687 } while (true);
688 } while (m >= 258 && n >= 10);
689
690 // not enough input or output--restore pointers and return
691 c = z.avail_in - n;
692 c = k >> 3 < c? k >> 3 : c;
693 n += c;
694 p -= c;
695 k -= c << 3;
696
697 s.bitb = b;
698 s.bitk = k;
699 z.avail_in = n;
700 z.total_in += p - z.next_in_index;
701 z.next_in_index = p;
702 s.write = q;
703
704 return JZlib.Z_OK;
705 }
706 }