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([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 }