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