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 }