View Javadoc

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