View Javadoc

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