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 InfCodes{ 38 39 static final private int[] inflate_mask = { 40 0x00000000, 0x00000001, 0x00000003, 0x00000007, 0x0000000f, 41 0x0000001f, 0x0000003f, 0x0000007f, 0x000000ff, 0x000001ff, 42 0x000003ff, 0x000007ff, 0x00000fff, 0x00001fff, 0x00003fff, 43 0x00007fff, 0x0000ffff 44 }; 45 46 static final private int Z_OK=0; 47 static final private int Z_STREAM_END=1; 48 static final private int Z_NEED_DICT=2; 49 static final private int Z_ERRNO=-1; 50 static final private int Z_STREAM_ERROR=-2; 51 static final private int Z_DATA_ERROR=-3; 52 static final private int Z_MEM_ERROR=-4; 53 static final private int Z_BUF_ERROR=-5; 54 static final private int Z_VERSION_ERROR=-6; 55 56 // waiting for "i:"=input, 57 // "o:"=output, 58 // "x:"=nothing 59 static final private int START=0; // x: set up for LEN 60 static final private int LEN=1; // i: get length/literal/eob next 61 static final private int LENEXT=2; // i: getting length extra (have base) 62 static final private int DIST=3; // i: get distance next 63 static final private int DISTEXT=4;// i: getting distance extra 64 static final private int COPY=5; // o: copying bytes in window, waiting for space 65 static final private int LIT=6; // o: got literal, waiting for output space 66 static final private int WASH=7; // o: got eob, possibly still output waiting 67 static final private int END=8; // x: got eob and all data flushed 68 static final private int BADCODE=9;// x: got error 69 70 int mode; // current inflate_codes mode 71 72 // mode dependent information 73 int len; 74 75 int[] tree; // pointer into tree 76 int tree_index=0; 77 int need; // bits needed 78 79 int lit; 80 81 // if EXT or COPY, where and how much 82 int get; // bits to get for extra 83 int dist; // distance back to copy from 84 85 byte lbits; // ltree bits decoded per branch 86 byte dbits; // dtree bits decoder per branch 87 int[] ltree; // literal/length/eob tree 88 int ltree_index; // literal/length/eob tree 89 int[] dtree; // distance tree 90 int dtree_index; // distance tree 91 92 private final ZStream z; 93 private final InfBlocks s; InfCodes(ZStream z, InfBlocks s)94 InfCodes(ZStream z, InfBlocks s){ 95 this.z=z; 96 this.s=s; 97 } 98 init(int bl, int bd, int[] tl, int tl_index, int[] td, int td_index)99 void init(int bl, int bd, 100 int[] tl, int tl_index, 101 int[] td, int td_index){ 102 mode=START; 103 lbits=(byte)bl; 104 dbits=(byte)bd; 105 ltree=tl; 106 ltree_index=tl_index; 107 dtree = td; 108 dtree_index=td_index; 109 tree=null; 110 } 111 proc(int r)112 int proc(int r){ 113 int j; // temporary storage 114 int[] t; // temporary pointer 115 int tindex; // temporary pointer 116 int e; // extra bits or operation 117 int b=0; // bit buffer 118 int k=0; // bits in bit buffer 119 int p=0; // input data pointer 120 int n; // bytes available there 121 int q; // output window write pointer 122 int m; // bytes to end of window or read pointer 123 int f; // pointer to copy strings from 124 125 // copy input/output information to locals (UPDATE macro restores) 126 p=z.next_in_index;n=z.avail_in;b=s.bitb;k=s.bitk; 127 q=s.write;m=q<s.read?s.read-q-1:s.end-q; 128 129 // process input and output based on current state 130 while (true){ 131 switch (mode){ 132 // waiting for "i:"=input, "o:"=output, "x:"=nothing 133 case START: // x: set up for LEN 134 if (m >= 258 && n >= 10){ 135 136 s.bitb=b;s.bitk=k; 137 z.avail_in=n;z.total_in+=p-z.next_in_index;z.next_in_index=p; 138 s.write=q; 139 r = inflate_fast(lbits, dbits, 140 ltree, ltree_index, 141 dtree, dtree_index, 142 s, z); 143 144 p=z.next_in_index;n=z.avail_in;b=s.bitb;k=s.bitk; 145 q=s.write;m=q<s.read?s.read-q-1:s.end-q; 146 147 if (r != Z_OK){ 148 mode = r == Z_STREAM_END ? WASH : BADCODE; 149 break; 150 } 151 } 152 need = lbits; 153 tree = ltree; 154 tree_index=ltree_index; 155 156 mode = LEN; 157 case LEN: // i: get length/literal/eob next 158 j = need; 159 160 while(k<(j)){ 161 if(n!=0)r=Z_OK; 162 else{ 163 164 s.bitb=b;s.bitk=k; 165 z.avail_in=n;z.total_in+=p-z.next_in_index;z.next_in_index=p; 166 s.write=q; 167 return s.inflate_flush(r); 168 } 169 n--; 170 b|=(z.next_in[p++]&0xff)<<k; 171 k+=8; 172 } 173 174 tindex=(tree_index+(b&inflate_mask[j]))*3; 175 176 b>>>=(tree[tindex+1]); 177 k-=(tree[tindex+1]); 178 179 e=tree[tindex]; 180 181 if(e == 0){ // literal 182 lit = tree[tindex+2]; 183 mode = LIT; 184 break; 185 } 186 if((e & 16)!=0 ){ // length 187 get = e & 15; 188 len = tree[tindex+2]; 189 mode = LENEXT; 190 break; 191 } 192 if ((e & 64) == 0){ // next table 193 need = e; 194 tree_index = tindex/3+tree[tindex+2]; 195 break; 196 } 197 if ((e & 32)!=0){ // end of block 198 mode = WASH; 199 break; 200 } 201 mode = BADCODE; // invalid code 202 z.msg = "invalid literal/length code"; 203 r = Z_DATA_ERROR; 204 205 s.bitb=b;s.bitk=k; 206 z.avail_in=n;z.total_in+=p-z.next_in_index;z.next_in_index=p; 207 s.write=q; 208 return s.inflate_flush(r); 209 210 case LENEXT: // i: getting length extra (have base) 211 j = get; 212 213 while(k<(j)){ 214 if(n!=0)r=Z_OK; 215 else{ 216 217 s.bitb=b;s.bitk=k; 218 z.avail_in=n;z.total_in+=p-z.next_in_index;z.next_in_index=p; 219 s.write=q; 220 return s.inflate_flush(r); 221 } 222 n--; b|=(z.next_in[p++]&0xff)<<k; 223 k+=8; 224 } 225 226 len += (b & inflate_mask[j]); 227 228 b>>=j; 229 k-=j; 230 231 need = dbits; 232 tree = dtree; 233 tree_index=dtree_index; 234 mode = DIST; 235 case DIST: // i: get distance next 236 j = need; 237 238 while(k<(j)){ 239 if(n!=0)r=Z_OK; 240 else{ 241 242 s.bitb=b;s.bitk=k; 243 z.avail_in=n;z.total_in+=p-z.next_in_index;z.next_in_index=p; 244 s.write=q; 245 return s.inflate_flush(r); 246 } 247 n--; b|=(z.next_in[p++]&0xff)<<k; 248 k+=8; 249 } 250 251 tindex=(tree_index+(b & inflate_mask[j]))*3; 252 253 b>>=tree[tindex+1]; 254 k-=tree[tindex+1]; 255 256 e = (tree[tindex]); 257 if((e & 16)!=0){ // distance 258 get = e & 15; 259 dist = tree[tindex+2]; 260 mode = DISTEXT; 261 break; 262 } 263 if ((e & 64) == 0){ // next table 264 need = e; 265 tree_index = tindex/3 + tree[tindex+2]; 266 break; 267 } 268 mode = BADCODE; // invalid code 269 z.msg = "invalid distance code"; 270 r = Z_DATA_ERROR; 271 272 s.bitb=b;s.bitk=k; 273 z.avail_in=n;z.total_in+=p-z.next_in_index;z.next_in_index=p; 274 s.write=q; 275 return s.inflate_flush(r); 276 277 case DISTEXT: // i: getting distance extra 278 j = get; 279 280 while(k<(j)){ 281 if(n!=0)r=Z_OK; 282 else{ 283 284 s.bitb=b;s.bitk=k; 285 z.avail_in=n;z.total_in+=p-z.next_in_index;z.next_in_index=p; 286 s.write=q; 287 return s.inflate_flush(r); 288 } 289 n--; b|=(z.next_in[p++]&0xff)<<k; 290 k+=8; 291 } 292 293 dist += (b & inflate_mask[j]); 294 295 b>>=j; 296 k-=j; 297 298 mode = COPY; 299 case COPY: // o: copying bytes in window, waiting for space 300 f = q - dist; 301 while(f < 0){ // modulo window size-"while" instead 302 f += s.end; // of "if" handles invalid distances 303 } 304 while (len!=0){ 305 306 if(m==0){ 307 if(q==s.end&&s.read!=0){q=0;m=q<s.read?s.read-q-1:s.end-q;} 308 if(m==0){ 309 s.write=q; r=s.inflate_flush(r); 310 q=s.write;m=q<s.read?s.read-q-1:s.end-q; 311 312 if(q==s.end&&s.read!=0){q=0;m=q<s.read?s.read-q-1:s.end-q;} 313 314 if(m==0){ 315 s.bitb=b;s.bitk=k; 316 z.avail_in=n;z.total_in+=p-z.next_in_index;z.next_in_index=p; 317 s.write=q; 318 return s.inflate_flush(r); 319 } 320 } 321 } 322 323 s.window[q++]=s.window[f++]; m--; 324 325 if (f == s.end) 326 f = 0; 327 len--; 328 } 329 mode = START; 330 break; 331 case LIT: // o: got literal, waiting for output space 332 if(m==0){ 333 if(q==s.end&&s.read!=0){q=0;m=q<s.read?s.read-q-1:s.end-q;} 334 if(m==0){ 335 s.write=q; r=s.inflate_flush(r); 336 q=s.write;m=q<s.read?s.read-q-1:s.end-q; 337 338 if(q==s.end&&s.read!=0){q=0;m=q<s.read?s.read-q-1:s.end-q;} 339 if(m==0){ 340 s.bitb=b;s.bitk=k; 341 z.avail_in=n;z.total_in+=p-z.next_in_index;z.next_in_index=p; 342 s.write=q; 343 return s.inflate_flush(r); 344 } 345 } 346 } 347 r=Z_OK; 348 349 s.window[q++]=(byte)lit; m--; 350 351 mode = START; 352 break; 353 case WASH: // o: got eob, possibly more output 354 if (k > 7){ // return unused byte, if any 355 k -= 8; 356 n++; 357 p--; // can always return one 358 } 359 360 s.write=q; r=s.inflate_flush(r); 361 q=s.write;m=q<s.read?s.read-q-1:s.end-q; 362 363 if (s.read != s.write){ 364 s.bitb=b;s.bitk=k; 365 z.avail_in=n;z.total_in+=p-z.next_in_index;z.next_in_index=p; 366 s.write=q; 367 return s.inflate_flush(r); 368 } 369 mode = END; 370 case END: 371 r = Z_STREAM_END; 372 s.bitb=b;s.bitk=k; 373 z.avail_in=n;z.total_in+=p-z.next_in_index;z.next_in_index=p; 374 s.write=q; 375 return s.inflate_flush(r); 376 377 case BADCODE: // x: got error 378 379 r = Z_DATA_ERROR; 380 381 s.bitb=b;s.bitk=k; 382 z.avail_in=n;z.total_in+=p-z.next_in_index;z.next_in_index=p; 383 s.write=q; 384 return s.inflate_flush(r); 385 386 default: 387 r = Z_STREAM_ERROR; 388 389 s.bitb=b;s.bitk=k; 390 z.avail_in=n;z.total_in+=p-z.next_in_index;z.next_in_index=p; 391 s.write=q; 392 return s.inflate_flush(r); 393 } 394 } 395 } 396 397 void free(ZStream z){ 398 // ZFREE(z, c); 399 } 400 401 // Called with number of bytes left to write in window at least 258 402 // (the maximum string length) and number of input bytes available 403 // at least ten. The ten bytes are six bytes for the longest length/ 404 // distance pair plus four bytes for overloading the bit buffer. 405 406 int inflate_fast(int bl, int bd, 407 int[] tl, int tl_index, 408 int[] td, int td_index, 409 InfBlocks s, ZStream z){ 410 int t; // temporary pointer 411 int[] tp; // temporary pointer 412 int tp_index; // temporary pointer 413 int e; // extra bits or operation 414 int b; // bit buffer 415 int k; // bits in bit buffer 416 int p; // input data pointer 417 int n; // bytes available there 418 int q; // output window write pointer 419 int m; // bytes to end of window or read pointer 420 int ml; // mask for literal/length tree 421 int md; // mask for distance tree 422 int c; // bytes to copy 423 int d; // distance back to copy from 424 int r; // copy source pointer 425 426 int tp_index_t_3; // (tp_index+t)*3 427 428 // load input, output, bit values 429 p=z.next_in_index;n=z.avail_in;b=s.bitb;k=s.bitk; 430 q=s.write;m=q<s.read?s.read-q-1:s.end-q; 431 432 // initialize masks 433 ml = inflate_mask[bl]; 434 md = inflate_mask[bd]; 435 436 // do until not enough input or output space for fast loop 437 do { // assume called with m >= 258 && n >= 10 438 // get literal/length code 439 while(k<(20)){ // max bits for literal/length code 440 n--; 441 b|=(z.next_in[p++]&0xff)<<k;k+=8; 442 } 443 444 t= b&ml; 445 tp=tl; 446 tp_index=tl_index; 447 tp_index_t_3=(tp_index+t)*3; 448 if ((e = tp[tp_index_t_3]) == 0){ 449 b>>=(tp[tp_index_t_3+1]); k-=(tp[tp_index_t_3+1]); 450 451 s.window[q++] = (byte)tp[tp_index_t_3+2]; 452 m--; 453 continue; 454 } 455 do { 456 457 b>>=(tp[tp_index_t_3+1]); k-=(tp[tp_index_t_3+1]); 458 459 if((e&16)!=0){ 460 e &= 15; 461 c = tp[tp_index_t_3+2] + ((int)b & inflate_mask[e]); 462 463 b>>=e; k-=e; 464 465 // decode distance base of block to copy 466 while(k<(15)){ // max bits for distance code 467 n--; 468 b|=(z.next_in[p++]&0xff)<<k;k+=8; 469 } 470 471 t= b&md; 472 tp=td; 473 tp_index=td_index; 474 tp_index_t_3=(tp_index+t)*3; 475 e = tp[tp_index_t_3]; 476 477 do { 478 479 b>>=(tp[tp_index_t_3+1]); k-=(tp[tp_index_t_3+1]); 480 481 if((e&16)!=0){ 482 // get extra bits to add to distance base 483 e &= 15; 484 while(k<(e)){ // get extra bits (up to 13) 485 n--; 486 b|=(z.next_in[p++]&0xff)<<k;k+=8; 487 } 488 489 d = tp[tp_index_t_3+2] + (b&inflate_mask[e]); 490 491 b>>=(e); k-=(e); 492 493 // do the copy 494 m -= c; 495 if (q >= d){ // offset before dest 496 // just copy 497 r=q-d; 498 if(q-r>0 && 2>(q-r)){ 499 s.window[q++]=s.window[r++]; // minimum count is three, 500 s.window[q++]=s.window[r++]; // so unroll loop a little 501 c-=2; 502 } 503 else{ 504 System.arraycopy(s.window, r, s.window, q, 2); 505 q+=2; r+=2; c-=2; 506 } 507 } 508 else{ // else offset after destination 509 r=q-d; 510 do{ 511 r+=s.end; // force pointer in window 512 }while(r<0); // covers invalid distances 513 e=s.end-r; 514 if(c>e){ // if source crosses, 515 c-=e; // wrapped copy 516 if(q-r>0 && e>(q-r)){ 517 do{s.window[q++] = s.window[r++];} 518 while(--e!=0); 519 } 520 else{ 521 System.arraycopy(s.window, r, s.window, q, e); 522 q+=e; r+=e; e=0; 523 } 524 r = 0; // copy rest from start of window 525 } 526 527 } 528 529 // copy all or what's left 530 if(q-r>0 && c>(q-r)){ 531 do{s.window[q++] = s.window[r++];} 532 while(--c!=0); 533 } 534 else{ 535 System.arraycopy(s.window, r, s.window, q, c); 536 q+=c; r+=c; c=0; 537 } 538 break; 539 } 540 else if((e&64)==0){ 541 t+=tp[tp_index_t_3+2]; 542 t+=(b&inflate_mask[e]); 543 tp_index_t_3=(tp_index+t)*3; 544 e=tp[tp_index_t_3]; 545 } 546 else{ 547 z.msg = "invalid distance code"; 548 549 c=z.avail_in-n;c=(k>>3)<c?k>>3:c;n+=c;p-=c;k-=c<<3; 550 551 s.bitb=b;s.bitk=k; 552 z.avail_in=n;z.total_in+=p-z.next_in_index;z.next_in_index=p; 553 s.write=q; 554 555 return Z_DATA_ERROR; 556 } 557 } 558 while(true); 559 break; 560 } 561 562 if((e&64)==0){ 563 t+=tp[tp_index_t_3+2]; 564 t+=(b&inflate_mask[e]); 565 tp_index_t_3=(tp_index+t)*3; 566 if((e=tp[tp_index_t_3])==0){ 567 568 b>>=(tp[tp_index_t_3+1]); k-=(tp[tp_index_t_3+1]); 569 570 s.window[q++]=(byte)tp[tp_index_t_3+2]; 571 m--; 572 break; 573 } 574 } 575 else if((e&32)!=0){ 576 577 c=z.avail_in-n;c=(k>>3)<c?k>>3:c;n+=c;p-=c;k-=c<<3; 578 579 s.bitb=b;s.bitk=k; 580 z.avail_in=n;z.total_in+=p-z.next_in_index;z.next_in_index=p; 581 s.write=q; 582 583 return Z_STREAM_END; 584 } 585 else{ 586 z.msg="invalid literal/length code"; 587 588 c=z.avail_in-n;c=(k>>3)<c?k>>3:c;n+=c;p-=c;k-=c<<3; 589 590 s.bitb=b;s.bitk=k; 591 z.avail_in=n;z.total_in+=p-z.next_in_index;z.next_in_index=p; 592 s.write=q; 593 594 return Z_DATA_ERROR; 595 } 596 } 597 while(true); 598 } 599 while(m>=258 && n>= 10); 600 601 // not enough input or output--restore pointers and return 602 c=z.avail_in-n;c=(k>>3)<c?k>>3:c;n+=c;p-=c;k-=c<<3; 603 604 s.bitb=b;s.bitk=k; 605 z.avail_in=n;z.total_in+=p-z.next_in_index;z.next_in_index=p; 606 s.write=q; 607 608 return Z_OK; 609 } 610 } 611