src/com/jcraft/jzlib/InfBlocks.java

   1 /* -*-mode:java; c-basic-offset:2; -*- */
   2 /*
   3 Copyright (c) 2000,2001,2002,2003 ymnk, JCraft,Inc. All rights reserved.
   4
   5 Redistribution and use in source and binary forms, with or without
   6 modification, are permitted provided that the following conditions are met:
   7
   8   1. Redistributions of source code must retain the above copyright notice,
   9      this list of conditions and the following disclaimer.
  10
  11   2. Redistributions in binary form must reproduce the above copyright
  12      notice, this list of conditions and the following disclaimer in
  13      the documentation and/or other materials provided with the distribution.
  14
  15   3. The names of the authors may not be used to endorse or promote products
  16      derived from this software without specific prior written permission.
  17
  18 THIS SOFTWARE IS PROVIDED ``AS IS'' AND ANY EXPRESSED OR IMPLIED WARRANTIES,
  19 INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND
  20 FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL JCRAFT,
  21 INC. OR ANY CONTRIBUTORS TO THIS SOFTWARE BE LIABLE FOR ANY DIRECT, INDIRECT,
  22 INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
  23 LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA,
  24 OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF
  25 LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
  26 NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE,
  27 EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
  28  */
  29 /*
  30  * This program is based on zlib-1.1.3, so all credit should go authors
  31  * Jean-loup Gailly(jloup@gzip.org) and Mark Adler(madler@alumni.caltech.edu)
  32  * and contributors of zlib.
  33  */
  34
  35 package com.jcraft.jzlib;
  36
  37 final class InfBlocks{
  38   static final private int MANY=1440;
  39
  40   // And'ing with mask[n] masks the lower n bits
  41   static final private int[] inflate_mask = {
  42     0x00000000, 0x00000001, 0x00000003, 0x00000007, 0x0000000f,
  43     0x0000001f, 0x0000003f, 0x0000007f, 0x000000ff, 0x000001ff,
  44     0x000003ff, 0x000007ff, 0x00000fff, 0x00001fff, 0x00003fff,
  45     0x00007fff, 0x0000ffff
  46   };
  47
  48   // Table for deflate from PKZIP's appnote.txt.
  49   static final int[] border = { // Order of the bit length code lengths
  50     16, 17, 18, 0, 8, 7, 9, 6, 10, 5, 11, 4, 12, 3, 13, 2, 14, 1, 15
  51   };
  52
  53   static final private int Z_OK=0;
  54   static final private int Z_STREAM_END=1;
  55   static final private int Z_NEED_DICT=2;
  56   static final private int Z_ERRNO=-1;
  57   static final private int Z_STREAM_ERROR=-2;
  58   static final private int Z_DATA_ERROR=-3;
  59   static final private int Z_MEM_ERROR=-4;
  60   static final private int Z_BUF_ERROR=-5;
  61   static final private int Z_VERSION_ERROR=-6;
  62
  63   static final private int TYPE=0;  // get type bits (3, including end bit)
  64   static final private int LENS=1;  // get lengths for stored
  65   static final private int STORED=2;// processing stored block
  66   static final private int TABLE=3; // get table lengths
  67   static final private int BTREE=4; // get bit lengths tree for a dynamic block
  68   static final private int DTREE=5; // get length, distance trees for a dynamic block
  69   static final private int CODES=6; // processing fixed or dynamic block
  70   static final private int DRY=7;   // output remaining window bytes
  71   static final private int DONE=8;  // finished last block, done
  72   static final private int BAD=9;   // ot a data error--stuck here
  73
  74   int mode;            // current inflate_block mode
  75
  76   int left;            // if STORED, bytes left to copy
  77
  78   int table;           // table lengths (14 bits)
  79   int index;           // index into blens (or border)
  80   int[] blens;         // bit lengths of codes
  81   int[] bb=new int[1]; // bit length tree depth
  82   int[] tb=new int[1]; // bit length decoding tree
  83
  84   InfCodes codes=new InfCodes();      // if CODES, current state
  85
  86   int last;            // true if this block is the last block
  87
  88   // mode independent information
  89   int bitk;            // bits in bit buffer
  90   int bitb;            // bit buffer
  91   int[] hufts;         // single malloc for tree space
  92   byte[] window;       // sliding window
  93   int end;             // one byte after sliding window
  94   int read;            // window read pointer
  95   int write;           // window write pointer
  96   Object checkfn;      // check function
  97   long check;          // check on output
  98
  99   InfTree inftree=new InfTree();
 100
 101   InfBlocks(ZStream z, Object checkfn, int w){
 102     hufts=new int[MANY*3];
 103     window=new byte[w];
 104     end=w;
 105     this.checkfn = checkfn;
 106     mode = TYPE;
 107     reset(z, null);
 108   }
 109
 110   void reset(ZStream z, long[] c){
 111     if(c!=null) c[0]=check;
 112     if(mode==BTREE || mode==DTREE){
 113     }
 114     if(mode==CODES){
 115       codes.free(z);
 116     }
 117     mode=TYPE;
 118     bitk=0;
 119     bitb=0;
 120     read=write=0;
 121
 122     if(checkfn != null)
 123       z.adler=check=z._adler.adler32(0L, null, 0, 0);
 124   }
 125
 126   int proc(ZStream z, int r){
 127     int t;              // temporary storage
 128     int b;              // bit buffer
 129     int k;              // bits in bit buffer
 130     int p;              // input data pointer
 131     int n;              // bytes available there
 132     int q;              // output window write pointer
 133     int m;              // bytes to end of window or read pointer
 134
 135     // copy input/output information to locals (UPDATE macro restores)
 136     {p=z.next_in_index;n=z.avail_in;b=bitb;k=bitk;}
 137     {q=write;m=(int)(q<read?read-q-1:end-q);}
 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=Z_OK;
 147           }
 148           else{
 149             bitb=b; bitk=k;
 150             z.avail_in=n;
 151             z.total_in+=p-z.next_in_index;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 = (int)(b & 7);
 160         last = t & 1;
 161
 162         switch (t >>> 1){
 163         case 0:                         // stored
 164           {b>>>=(3);k-=(3);}
 165           t = k & 7;                    // go to byte boundary
 166
 167           {b>>>=(t);k-=(t);}
 168           mode = LENS;                  // get length of stored block
 169           break;
 170         case 1:                         // fixed
 171           {
 172             int[] bl=new int[1];
 173             int[] bd=new int[1];
 174             int[][] tl=new int[1][];
 175             int[][] td=new int[1][];
 176
 177             InfTree.inflate_trees_fixed(bl, bd, tl, td, z);
 178             codes.init(bl[0], bd[0], tl[0], 0, td[0], 0, z);
 179           }
 180
 181           {b>>>=(3);k-=(3);}
 182
 183           mode = CODES;
 184           break;
 185         case 2:                         // dynamic
 186
 187           {b>>>=(3);k-=(3);}
 188
 189           mode = TABLE;
 190           break;
 191         case 3:                         // illegal
 192
 193           {b>>>=(3);k-=(3);}
 194           mode = BAD;
 195           z.msg = "invalid block type";
 196           r = Z_DATA_ERROR;
 197
 198           bitb=b; bitk=k;
 199           z.avail_in=n;z.total_in+=p-z.next_in_index;z.next_in_index=p;
 200           write=q;
 201           return inflate_flush(z,r);
 202         }
 203         break;
 204       case LENS:
 205
 206         while(k<(32)){
 207           if(n!=0){
 208             r=Z_OK;
 209           }
 210           else{
 211             bitb=b; bitk=k;
 212             z.avail_in=n;
 213             z.total_in+=p-z.next_in_index;z.next_in_index=p;
 214             write=q;
 215             return inflate_flush(z,r);
 216           };
 217           n--;
 218           b|=(z.next_in[p++]&0xff)<<k;
 219           k+=8;
 220         }
 221
 222         if ((((~b) >>> 16) & 0xffff) != (b & 0xffff)){
 223           mode = BAD;
 224           z.msg = "invalid stored block lengths";
 225           r = Z_DATA_ERROR;
 226
 227           bitb=b; bitk=k;
 228           z.avail_in=n;z.total_in+=p-z.next_in_index;z.next_in_index=p;
 229           write=q;
 230           return inflate_flush(z,r);
 231         }
 232         left = (b & 0xffff);
 233         b = k = 0;                       // dump bits
 234         mode = left!=0 ? STORED : (last!=0 ? DRY : TYPE);
 235         break;
 236       case STORED:
 237         if (n == 0){
 238           bitb=b; bitk=k;
 239           z.avail_in=n;z.total_in+=p-z.next_in_index;z.next_in_index=p;
 240           write=q;
 241           return inflate_flush(z,r);
 242         }
 243
 244         if(m==0){
 245           if(q==end&&read!=0){
 246             q=0; m=(int)(q<read?read-q-1:end-q);
 247           }
 248           if(m==0){
 249             write=q;
 250             r=inflate_flush(z,r);
 251             q=write;m=(int)(q<read?read-q-1:end-q);
 252             if(q==end&&read!=0){
 253               q=0; m=(int)(q<read?read-q-1:end-q);
 254             }
 255             if(m==0){
 256               bitb=b; bitk=k;
 257               z.avail_in=n;z.total_in+=p-z.next_in_index;z.next_in_index=p;
 258               write=q;
 259               return inflate_flush(z,r);
 260             }
 261           }
 262         }
 263         r=Z_OK;
 264
 265         t = left;
 266         if(t>n) t = n;
 267         if(t>m) t = m;
 268         System.arraycopy(z.next_in, p, window, q, t);
 269         p += t;  n -= t;
 270         q += t;  m -= t;
 271         if ((left -= t) != 0)
 272           break;
 273         mode = last!=0 ? DRY : TYPE;
 274         break;
 275       case TABLE:
 276
 277         while(k<(14)){
 278           if(n!=0){
 279             r=Z_OK;
 280           }
 281           else{
 282             bitb=b; bitk=k;
 283             z.avail_in=n;
 284             z.total_in+=p-z.next_in_index;z.next_in_index=p;
 285             write=q;
 286             return inflate_flush(z,r);
 287           };
 288           n--;
 289           b|=(z.next_in[p++]&0xff)<<k;
 290           k+=8;
 291         }
 292
 293         table = t = (b & 0x3fff);
 294         if ((t & 0x1f) > 29 || ((t >> 5) & 0x1f) > 29)
 295           {
 296             mode = BAD;
 297             z.msg = "too many length or distance symbols";
 298             r = Z_DATA_ERROR;
 299
 300             bitb=b; bitk=k;
 301             z.avail_in=n;z.total_in+=p-z.next_in_index;z.next_in_index=p;
 302             write=q;
 303             return inflate_flush(z,r);
 304           }
 305         t = 258 + (t & 0x1f) + ((t >> 5) & 0x1f);
 306         if(blens==null || blens.length<t){
 307           blens=new int[t];
 308         }
 309         else{
 310           for(int i=0; i<t; i++){blens[i]=0;}
 311         }
 312
 313         {b>>>=(14);k-=(14);}
 314
 315         index = 0;
 316         mode = BTREE;
 317       case BTREE:
 318         while (index < 4 + (table >>> 10)){
 319           while(k<(3)){
 320             if(n!=0){
 321               r=Z_OK;
 322             }
 323             else{
 324               bitb=b; bitk=k;
 325               z.avail_in=n;
 326               z.total_in+=p-z.next_in_index;z.next_in_index=p;
 327               write=q;
 328               return inflate_flush(z,r);
 329             };
 330             n--;
 331             b|=(z.next_in[p++]&0xff)<<k;
 332             k+=8;
 333           }
 334
 335           blens[border[index++]] = b&7;
 336
 337           {b>>>=(3);k-=(3);}
 338         }
 339
 340         while(index < 19){
 341           blens[border[index++]] = 0;
 342         }
 343
 344         bb[0] = 7;
 345         t = inftree.inflate_trees_bits(blens, bb, tb, hufts, z);
 346         if (t != Z_OK){
 347           r = t;
 348           if (r == Z_DATA_ERROR){
 349             blens=null;
 350             mode = BAD;
 351           }
 352
 353           bitb=b; bitk=k;
 354           z.avail_in=n;z.total_in+=p-z.next_in_index;z.next_in_index=p;
 355           write=q;
 356           return inflate_flush(z,r);
 357         }
 358
 359         index = 0;
 360         mode = DTREE;
 361       case DTREE:
 362         while (true){
 363           t = table;
 364           if(!(index < 258 + (t & 0x1f) + ((t >> 5) & 0x1f))){
 365             break;
 366           }
 367
 368           int[] h;
 369           int i, j, c;
 370
 371           t = bb[0];
 372
 373           while(k<(t)){
 374             if(n!=0){
 375               r=Z_OK;
 376             }
 377             else{
 378               bitb=b; bitk=k;
 379               z.avail_in=n;
 380               z.total_in+=p-z.next_in_index;z.next_in_index=p;
 381               write=q;
 382               return inflate_flush(z,r);
 383             };
 384             n--;
 385             b|=(z.next_in[p++]&0xff)<<k;
 386             k+=8;
 387           }
 388
 389           if(tb[0]==-1){
 390             //System.err.println("null...");
 391           }
 392
 393           t=hufts[(tb[0]+(b&inflate_mask[t]))*3+1];
 394           c=hufts[(tb[0]+(b&inflate_mask[t]))*3+2];
 395
 396           if (c < 16){
 397             b>>>=(t);k-=(t);
 398             blens[index++] = c;
 399           }
 400           else { // c == 16..18
 401             i = c == 18 ? 7 : c - 14;
 402             j = c == 18 ? 11 : 3;
 403
 404             while(k<(t+i)){
 405               if(n!=0){
 406                 r=Z_OK;
 407               }
 408               else{
 409                 bitb=b; bitk=k;
 410                 z.avail_in=n;
 411                 z.total_in+=p-z.next_in_index;z.next_in_index=p;
 412                 write=q;
 413                 return inflate_flush(z,r);
 414               };
 415               n--;
 416               b|=(z.next_in[p++]&0xff)<<k;
 417               k+=8;
 418             }
 419
 420             b>>>=(t);k-=(t);
 421
 422             j += (b & inflate_mask[i]);
 423
 424             b>>>=(i);k-=(i);
 425
 426             i = index;
 427             t = table;
 428             if (i + j > 258 + (t & 0x1f) + ((t >> 5) & 0x1f) ||
 429                 (c == 16 && i < 1)){
 430               blens=null;
 431               mode = BAD;
 432               z.msg = "invalid bit length repeat";
 433               r = Z_DATA_ERROR;
 434
 435               bitb=b; bitk=k;
 436               z.avail_in=n;z.total_in+=p-z.next_in_index;z.next_in_index=p;
 437               write=q;
 438               return inflate_flush(z,r);
 439             }
 440
 441             c = c == 16 ? blens[i-1] : 0;
 442             do{
 443               blens[i++] = c;
 444             }
 445             while (--j!=0);
 446             index = i;
 447           }
 448         }
 449
 450         tb[0]=-1;
 451         {
 452           int[] bl=new int[1];
 453           int[] bd=new int[1];
 454           int[] tl=new int[1];
 455           int[] td=new int[1];
 456           bl[0] = 9;         // must be <= 9 for lookahead assumptions
 457           bd[0] = 6;         // must be <= 9 for lookahead assumptions
 458
 459           t = table;
 460           t = inftree.inflate_trees_dynamic(257 + (t & 0x1f),
 461                                             1 + ((t >> 5) & 0x1f),
 462                                             blens, bl, bd, tl, td, hufts, z);
 463
 464           if (t != Z_OK){
 465             if (t == Z_DATA_ERROR){
 466               blens=null;
 467               mode = BAD;
 468             }
 469             r = t;
 470
 471             bitb=b; bitk=k;
 472             z.avail_in=n;z.total_in+=p-z.next_in_index;z.next_in_index=p;
 473             write=q;
 474             return inflate_flush(z,r);
 475           }
 476           codes.init(bl[0], bd[0], hufts, tl[0], hufts, td[0], z);
 477         }
 478         mode = CODES;
 479       case CODES:
 480         bitb=b; bitk=k;
 481         z.avail_in=n; z.total_in+=p-z.next_in_index;z.next_in_index=p;
 482         write=q;
 483
 484         if ((r = codes.proc(this, z, r)) != Z_STREAM_END){
 485           return inflate_flush(z, r);
 486         }
 487         r = Z_OK;
 488         codes.free(z);
 489
 490         p=z.next_in_index; n=z.avail_in;b=bitb;k=bitk;
 491         q=write;m=(int)(q<read?read-q-1:end-q);
 492
 493         if (last==0){
 494           mode = TYPE;
 495           break;
 496         }
 497         mode = DRY;
 498       case DRY:
 499         write=q;
 500         r=inflate_flush(z, r);
 501         q=write; m=(int)(q<read?read-q-1:end-q);
 502         if (read != write){
 503           bitb=b; bitk=k;
 504           z.avail_in=n;z.total_in+=p-z.next_in_index;z.next_in_index=p;
 505           write=q;
 506           return inflate_flush(z, r);
 507         }
 508         mode = DONE;
 509       case DONE:
 510         r = Z_STREAM_END;
 511
 512         bitb=b; bitk=k;
 513         z.avail_in=n;z.total_in+=p-z.next_in_index;z.next_in_index=p;
 514         write=q;
 515         return inflate_flush(z, r);
 516       case BAD:
 517         r = Z_DATA_ERROR;
 518
 519         bitb=b; bitk=k;
 520         z.avail_in=n;z.total_in+=p-z.next_in_index;z.next_in_index=p;
 521         write=q;
 522         return inflate_flush(z, r);
 523
 524       default:
 525         r = Z_STREAM_ERROR;
 526
 527         bitb=b; bitk=k;
 528         z.avail_in=n;z.total_in+=p-z.next_in_index;z.next_in_index=p;
 529         write=q;
 530         return inflate_flush(z, r);
 531       }
 532     }
 533   }
 534
 535   void free(ZStream z){
 536     reset(z, null);
 537     window=null;
 538     hufts=null;
 539     //ZFREE(z, s);
 540   }
 541
 542   void set_dictionary(byte[] d, int start, int n){
 543     System.arraycopy(d, start, window, 0, n);
 544     read = write = n;
 545   }
 546
 547   // Returns true if inflate is currently at the end of a block generated
 548   // by Z_SYNC_FLUSH or Z_FULL_FLUSH.
 549   int sync_point(){
 550     return mode == LENS ? 1 : 0;
 551   }
 552
 553   // copy as much as possible from the sliding window to the output area
 554   int inflate_flush(ZStream z, int r){
 555     int n;
 556     int p;
 557     int q;
 558
 559     // local copies of source and destination pointers
 560     p = z.next_out_index;
 561     q = read;
 562
 563     // compute number of bytes to copy as far as end of window
 564     n = (int)((q <= write ? write : end) - q);
 565     if (n > z.avail_out) n = z.avail_out;
 566     if (n!=0 && r == Z_BUF_ERROR) r = Z_OK;
 567
 568     // update counters
 569     z.avail_out -= n;
 570     z.total_out += n;
 571
 572     // update check information
 573     if(checkfn != null)
 574       z.adler=check=z._adler.adler32(check, window, q, n);
 575
 576     // copy as far as end of window
 577     System.arraycopy(window, q, z.next_out, p, n);
 578     p += n;
 579     q += n;
 580
 581     // see if more to copy at beginning of window
 582     if (q == end){
 583       // wrap pointers
 584       q = 0;
 585       if (write == end)
 586         write = 0;
 587
 588       // compute bytes to copy
 589       n = write - q;
 590       if (n > z.avail_out) n = z.avail_out;
 591       if (n!=0 && r == Z_BUF_ERROR) r = Z_OK;
 592
 593       // update counters
 594       z.avail_out -= n;
 595       z.total_out += n;
 596
 597       // update check information
 598       if(checkfn != null)
 599         z.adler=check=z._adler.adler32(check, window, q, n);
 600
 601       // copy
 602       System.arraycopy(window, q, z.next_out, p, n);
 603       p += n;
 604       q += n;
 605     }
 606
 607     // update pointers
 608     z.next_out_index = p;
 609     read = q;
 610
 611     // done
 612     return r;
 613   }
 614 }