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