1 /* inflate.c -- zlib decompression 2 * Copyright (C) 1995-2012 Mark Adler 3 * For conditions of distribution and use, see copyright notice in zlib.h 4 */ 5 6 /* 7 * Change history: 8 * 9 * 1.2.beta0 24 Nov 2002 10 * - First version -- complete rewrite of inflate to simplify code, avoid 11 * creation of window when not needed, minimize use of window when it is 12 * needed, make inffast.c even faster, implement gzip decoding, and to 13 * improve code readability and style over the previous zlib inflate code 14 * 15 * 1.2.beta1 25 Nov 2002 16 * - Use pointers for available input and output checking in inffast.c 17 * - Remove input and output counters in inffast.c 18 * - Change inffast.c entry and loop from avail_in >= 7 to >= 6 19 * - Remove unnecessary second byte pull from length extra in inffast.c 20 * - Unroll direct copy to three copies per loop in inffast.c 21 * 22 * 1.2.beta2 4 Dec 2002 23 * - Change external routine names to reduce potential conflicts 24 * - Correct filename to inffixed.h for fixed tables in inflate.c 25 * - Make hbuf[] unsigned char to match parameter type in inflate.c 26 * - Change strm->next_out[-state->offset] to *(strm->next_out - state->offset) 27 * to avoid negation problem on Alphas (64 bit) in inflate.c 28 * 29 * 1.2.beta3 22 Dec 2002 30 * - Add comments on state->bits assertion in inffast.c 31 * - Add comments on op field in inftrees.h 32 * - Fix bug in reuse of allocated window after inflateReset() 33 * - Remove bit fields--back to byte structure for speed 34 * - Remove distance extra == 0 check in inflate_fast()--only helps for lengths 35 * - Change post-increments to pre-increments in inflate_fast(), PPC biased? 36 * - Add compile time option, POSTINC, to use post-increments instead (Intel?) 37 * - Make MATCH copy in inflate() much faster for when inflate_fast() not used 38 * - Use local copies of stream next and avail values, as well as local bit 39 * buffer and bit count in inflate()--for speed when inflate_fast() not used 40 * 41 * 1.2.beta4 1 Jan 2003 42 * - Split ptr - 257 statements in inflate_table() to avoid compiler warnings 43 * - Move a comment on output buffer sizes from inffast.c to inflate.c 44 * - Add comments in inffast.c to introduce the inflate_fast() routine 45 * - Rearrange window copies in inflate_fast() for speed and simplification 46 * - Unroll last copy for window match in inflate_fast() 47 * - Use local copies of window variables in inflate_fast() for speed 48 * - Pull out common wnext == 0 case for speed in inflate_fast() 49 * - Make op and len in inflate_fast() unsigned for consistency 50 * - Add FAR to lcode and dcode declarations in inflate_fast() 51 * - Simplified bad distance check in inflate_fast() 52 * - Added inflateBackInit(), inflateBack(), and inflateBackEnd() in new 53 * source file infback.c to provide a call-back interface to inflate for 54 * programs like gzip and unzip -- uses window as output buffer to avoid 55 * window copying 56 * 57 * 1.2.beta5 1 Jan 2003 58 * - Improved inflateBack() interface to allow the caller to provide initial 59 * input in strm. 60 * - Fixed stored blocks bug in inflateBack() 61 * 62 * 1.2.beta6 4 Jan 2003 63 * - Added comments in inffast.c on effectiveness of POSTINC 64 * - Typecasting all around to reduce compiler warnings 65 * - Changed loops from while (1) or do {} while (1) to for (;;), again to 66 * make compilers happy 67 * - Changed type of window in inflateBackInit() to unsigned char * 68 * 69 * 1.2.beta7 27 Jan 2003 70 * - Changed many types to unsigned or unsigned short to avoid warnings 71 * - Added inflateCopy() function 72 * 73 * 1.2.0 9 Mar 2003 74 * - Changed inflateBack() interface to provide separate opaque descriptors 75 * for the in() and out() functions 76 * - Changed inflateBack() argument and in_func typedef to swap the length 77 * and buffer address return values for the input function 78 * - Check next_in and next_out for Z_NULL on entry to inflate() 79 * 80 * The history for versions after 1.2.0 are in ChangeLog in zlib distribution. 81 */ 82 83 #include "hammer2_zlib_zutil.h" 84 #include "hammer2_zlib_inftrees.h" 85 #include "hammer2_zlib_inflate.h" 86 #include "hammer2_zlib_inffast.h" 87 #include "../hammer2.h" 88 89 #ifdef MAKEFIXED 90 # ifndef BUILDFIXED 91 # define BUILDFIXED 92 # endif 93 #endif 94 95 /* function prototypes */ 96 int inflateResetKeep(z_streamp strm); 97 int inflateReset(z_streamp strm); 98 int inflateReset2(z_streamp strm, int windowBits); 99 int inflateInit2_(z_streamp strm, int windowBits, const char *version, 100 int stream_size); 101 int inflatePrime(z_streamp strm, int bits, int value); 102 local void fixedtables(struct inflate_state FAR *state); 103 local int updatewindow(z_streamp strm, const unsigned char FAR *end, 104 unsigned copy); 105 #ifdef BUILDFIXED 106 void makefixed(void); 107 #endif 108 109 int 110 inflateResetKeep(z_streamp strm) 111 { 112 struct inflate_state FAR *state; 113 114 if (strm == Z_NULL || strm->state == Z_NULL) return Z_STREAM_ERROR; 115 state = (struct inflate_state FAR *)strm->state; 116 strm->total_in = strm->total_out = state->total = 0; 117 strm->msg = Z_NULL; 118 if (state->wrap) /* to support ill-conceived Java test suite */ 119 strm->adler = state->wrap & 1; 120 state->mode = HEAD; 121 state->last = 0; 122 state->havedict = 0; 123 state->dmax = 32768U; 124 state->hold = 0; 125 state->bits = 0; 126 state->lencode = state->distcode = state->next = state->codes; 127 state->sane = 1; 128 state->back = -1; 129 Tracev((stderr, "inflate: reset\n")); 130 return Z_OK; 131 } 132 133 int 134 inflateReset(z_streamp strm) 135 { 136 struct inflate_state FAR *state; 137 138 if (strm == Z_NULL || strm->state == Z_NULL) return Z_STREAM_ERROR; 139 state = (struct inflate_state FAR *)strm->state; 140 state->wsize = 0; 141 state->whave = 0; 142 state->wnext = 0; 143 return inflateResetKeep(strm); 144 } 145 146 int 147 inflateReset2(z_streamp strm, int windowBits) 148 { 149 int wrap; 150 struct inflate_state FAR *state; 151 152 /* get the state */ 153 if (strm == Z_NULL || strm->state == Z_NULL) return Z_STREAM_ERROR; 154 state = (struct inflate_state FAR *)strm->state; 155 156 /* extract wrap request from windowBits parameter */ 157 if (windowBits < 0) { 158 wrap = 0; 159 windowBits = -windowBits; 160 } 161 else { 162 wrap = (windowBits >> 4) + 1; 163 } 164 165 /* set number of window bits, free window if different */ 166 if (windowBits && (windowBits < 8 || windowBits > 15)) 167 return Z_STREAM_ERROR; 168 if (state->window != Z_NULL && state->wbits != (unsigned)windowBits) { 169 free(state->window); 170 state->window = Z_NULL; 171 } 172 173 /* update state and reset the rest of it */ 174 state->wrap = wrap; 175 state->wbits = (unsigned)windowBits; 176 return inflateReset(strm); 177 } 178 179 int 180 inflateInit2_(z_streamp strm, int windowBits, const char *version, 181 int stream_size) 182 { 183 int ret; 184 struct inflate_state FAR *state; 185 186 if (version == Z_NULL || version[0] != ZLIB_VERSION[0] || 187 stream_size != (int)(sizeof(z_stream))) 188 return Z_VERSION_ERROR; 189 if (strm == Z_NULL) return Z_STREAM_ERROR; 190 strm->msg = Z_NULL; /* in case we return an error */ 191 state = (struct inflate_state FAR *) malloc(sizeof(struct inflate_state)); 192 if (state == Z_NULL) return Z_MEM_ERROR; 193 Tracev((stderr, "inflate: allocated\n")); 194 strm->state = (struct internal_state FAR *)state; 195 state->window = Z_NULL; 196 ret = inflateReset2(strm, windowBits); 197 if (ret != Z_OK) { 198 free(state); 199 strm->state = Z_NULL; 200 } 201 return ret; 202 } 203 204 int 205 inflateInit_(z_streamp strm, const char *version, int stream_size) 206 { 207 return inflateInit2_(strm, DEF_WBITS, version, stream_size); 208 } 209 210 int 211 inflatePrime(z_streamp strm, int bits, int value) 212 { 213 struct inflate_state FAR *state; 214 215 if (strm == Z_NULL || strm->state == Z_NULL) return Z_STREAM_ERROR; 216 state = (struct inflate_state FAR *)strm->state; 217 if (bits < 0) { 218 state->hold = 0; 219 state->bits = 0; 220 return Z_OK; 221 } 222 if (bits > 16 || state->bits + bits > 32) return Z_STREAM_ERROR; 223 value &= (1L << bits) - 1; 224 state->hold += value << state->bits; 225 state->bits += bits; 226 return Z_OK; 227 } 228 229 /* 230 Return state with length and distance decoding tables and index sizes set to 231 fixed code decoding. Normally this returns fixed tables from inffixed.h. 232 If BUILDFIXED is defined, then instead this routine builds the tables the 233 first time it's called, and returns those tables the first time and 234 thereafter. This reduces the size of the code by about 2K bytes, in 235 exchange for a little execution time. However, BUILDFIXED should not be 236 used for threaded applications, since the rewriting of the tables and virgin 237 may not be thread-safe. 238 */ 239 local 240 void 241 fixedtables(struct inflate_state FAR *state) 242 { 243 #ifdef BUILDFIXED 244 static int virgin = 1; 245 static code *lenfix, *distfix; 246 static code fixed[544]; 247 248 /* build fixed huffman tables if first call (may not be thread safe) */ 249 if (virgin) { 250 unsigned sym, bits; 251 static code *next; 252 253 /* literal/length table */ 254 sym = 0; 255 while (sym < 144) state->lens[sym++] = 8; 256 while (sym < 256) state->lens[sym++] = 9; 257 while (sym < 280) state->lens[sym++] = 7; 258 while (sym < 288) state->lens[sym++] = 8; 259 next = fixed; 260 lenfix = next; 261 bits = 9; 262 inflate_table(LENS, state->lens, 288, &(next), &(bits), state->work); 263 264 /* distance table */ 265 sym = 0; 266 while (sym < 32) state->lens[sym++] = 5; 267 distfix = next; 268 bits = 5; 269 inflate_table(DISTS, state->lens, 32, &(next), &(bits), state->work); 270 271 /* do this just once */ 272 virgin = 0; 273 } 274 #else /* !BUILDFIXED */ 275 # include "hammer2_zlib_inffixed.h" 276 #endif /* BUILDFIXED */ 277 state->lencode = lenfix; 278 state->lenbits = 9; 279 state->distcode = distfix; 280 state->distbits = 5; 281 } 282 283 #ifdef MAKEFIXED 284 #include <stdio.h> 285 286 /* 287 Write out the inffixed.h that is #include'd above. Defining MAKEFIXED also 288 defines BUILDFIXED, so the tables are built on the fly. makefixed() writes 289 those tables to stdout, which would be piped to inffixed.h. A small program 290 can simply call makefixed to do this: 291 292 void makefixed(void); 293 294 int main(void) 295 { 296 makefixed(); 297 return 0; 298 } 299 300 Then that can be linked with zlib built with MAKEFIXED defined and run: 301 302 a.out > inffixed.h 303 */ 304 void 305 makefixed() 306 { 307 unsigned low, size; 308 struct inflate_state state; 309 310 fixedtables(&state); 311 puts(" /* inffixed.h -- table for decoding fixed codes"); 312 puts(" * Generated automatically by makefixed()."); 313 puts(" */"); 314 puts(""); 315 puts(" /* WARNING: this file should *not* be used by applications."); 316 puts(" It is part of the implementation of this library and is"); 317 puts(" subject to change. Applications should only use zlib.h."); 318 puts(" */"); 319 puts(""); 320 size = 1U << 9; 321 printf(" static const code lenfix[%u] = {", size); 322 low = 0; 323 for (;;) { 324 if ((low % 7) == 0) printf("\n "); 325 printf("{%u,%u,%d}", (low & 127) == 99 ? 64 : state.lencode[low].op, 326 state.lencode[low].bits, state.lencode[low].val); 327 if (++low == size) break; 328 putchar(','); 329 } 330 puts("\n };"); 331 size = 1U << 5; 332 printf("\n static const code distfix[%u] = {", size); 333 low = 0; 334 for (;;) { 335 if ((low % 6) == 0) printf("\n "); 336 printf("{%u,%u,%d}", state.distcode[low].op, state.distcode[low].bits, 337 state.distcode[low].val); 338 if (++low == size) break; 339 putchar(','); 340 } 341 puts("\n };"); 342 } 343 #endif /* MAKEFIXED */ 344 345 /* 346 Update the window with the last wsize (normally 32K) bytes written before 347 returning. If window does not exist yet, create it. This is only called 348 when a window is already in use, or when output has been written during this 349 inflate call, but the end of the deflate stream has not been reached yet. 350 It is also called to create a window for dictionary data when a dictionary 351 is loaded. 352 353 Providing output buffers larger than 32K to inflate() should provide a speed 354 advantage, since only the last 32K of output is copied to the sliding window 355 upon return from inflate(), and since all distances after the first 32K of 356 output will fall in the output data, making match copies simpler and faster. 357 The advantage may be dependent on the size of the processor's data caches. 358 */ 359 local 360 int 361 updatewindow(z_streamp strm, const Bytef *end, unsigned copy) 362 { 363 struct inflate_state FAR *state; 364 unsigned dist; 365 366 state = (struct inflate_state FAR *)strm->state; 367 368 /* if window not in use yet, initialize */ 369 if (state->wsize == 0) { 370 state->wsize = 1U << state->wbits; 371 state->wnext = 0; 372 state->whave = 0; 373 } 374 375 /* copy state->wsize or less output bytes into the circular window */ 376 if (copy >= state->wsize) { 377 zmemcpy(state->window, end - state->wsize, state->wsize); 378 state->wnext = 0; 379 state->whave = state->wsize; 380 } 381 else { 382 dist = state->wsize - state->wnext; 383 if (dist > copy) dist = copy; 384 zmemcpy(state->window + state->wnext, end - copy, dist); 385 copy -= dist; 386 if (copy) { 387 zmemcpy(state->window, end - copy, copy); 388 state->wnext = copy; 389 state->whave = state->wsize; 390 } 391 else { 392 state->wnext += dist; 393 if (state->wnext == state->wsize) state->wnext = 0; 394 if (state->whave < state->wsize) state->whave += dist; 395 } 396 } 397 return 0; 398 } 399 400 /* Macros for inflate(): */ 401 #define UPDATE(check, buf, len) adler32(check, buf, len) 402 403 /* Load registers with state in inflate() for speed */ 404 #define LOAD() \ 405 do { \ 406 put = strm->next_out; \ 407 left = strm->avail_out; \ 408 next = strm->next_in; \ 409 have = strm->avail_in; \ 410 hold = state->hold; \ 411 bits = state->bits; \ 412 } while (0) 413 414 /* Restore state from registers in inflate() */ 415 #define RESTORE() \ 416 do { \ 417 strm->next_out = put; \ 418 strm->avail_out = left; \ 419 strm->next_in = next; \ 420 strm->avail_in = have; \ 421 state->hold = hold; \ 422 state->bits = bits; \ 423 } while (0) 424 425 /* Clear the input bit accumulator */ 426 #define INITBITS() \ 427 do { \ 428 hold = 0; \ 429 bits = 0; \ 430 } while (0) 431 432 /* Get a byte of input into the bit accumulator, or return from inflate() 433 if there is no input available. */ 434 #define PULLBYTE() \ 435 do { \ 436 if (have == 0) goto inf_leave; \ 437 have--; \ 438 hold += (unsigned long)(*next++) << bits; \ 439 bits += 8; \ 440 } while (0) 441 442 /* Assure that there are at least n bits in the bit accumulator. If there is 443 not enough available input to do that, then return from inflate(). */ 444 #define NEEDBITS(n) \ 445 do { \ 446 while (bits < (unsigned)(n)) \ 447 PULLBYTE(); \ 448 } while (0) 449 450 /* Return the low n bits of the bit accumulator (n < 16) */ 451 #define BITS(n) \ 452 ((unsigned)hold & ((1U << (n)) - 1)) 453 454 /* Remove n bits from the bit accumulator */ 455 #define DROPBITS(n) \ 456 do { \ 457 hold >>= (n); \ 458 bits -= (unsigned)(n); \ 459 } while (0) 460 461 /* Remove zero to seven bits as needed to go to a byte boundary */ 462 #define BYTEBITS() \ 463 do { \ 464 hold >>= bits & 7; \ 465 bits -= bits & 7; \ 466 } while (0) 467 468 /* 469 inflate() uses a state machine to process as much input data and generate as 470 much output data as possible before returning. The state machine is 471 structured roughly as follows: 472 473 for (;;) switch (state) { 474 ... 475 case STATEn: 476 if (not enough input data or output space to make progress) 477 return; 478 ... make progress ... 479 state = STATEm; 480 break; 481 ... 482 } 483 484 so when inflate() is called again, the same case is attempted again, and 485 if the appropriate resources are provided, the machine proceeds to the 486 next state. The NEEDBITS() macro is usually the way the state evaluates 487 whether it can proceed or should return. NEEDBITS() does the return if 488 the requested bits are not available. The typical use of the BITS macros 489 is: 490 491 NEEDBITS(n); 492 ... do something with BITS(n) ... 493 DROPBITS(n); 494 495 where NEEDBITS(n) either returns from inflate() if there isn't enough 496 input left to load n bits into the accumulator, or it continues. BITS(n) 497 gives the low n bits in the accumulator. When done, DROPBITS(n) drops 498 the low n bits off the accumulator. INITBITS() clears the accumulator 499 and sets the number of available bits to zero. BYTEBITS() discards just 500 enough bits to put the accumulator on a byte boundary. After BYTEBITS() 501 and a NEEDBITS(8), then BITS(8) would return the next byte in the stream. 502 503 NEEDBITS(n) uses PULLBYTE() to get an available byte of input, or to return 504 if there is no input available. The decoding of variable length codes uses 505 PULLBYTE() directly in order to pull just enough bytes to decode the next 506 code, and no more. 507 508 Some states loop until they get enough input, making sure that enough 509 state information is maintained to continue the loop where it left off 510 if NEEDBITS() returns in the loop. For example, want, need, and keep 511 would all have to actually be part of the saved state in case NEEDBITS() 512 returns: 513 514 case STATEw: 515 while (want < need) { 516 NEEDBITS(n); 517 keep[want++] = BITS(n); 518 DROPBITS(n); 519 } 520 state = STATEx; 521 case STATEx: 522 523 As shown above, if the next state is also the next case, then the break 524 is omitted. 525 526 A state may also return if there is not enough output space available to 527 complete that state. Those states are copying stored data, writing a 528 literal byte, and copying a matching string. 529 530 When returning, a "goto inf_leave" is used to update the total counters, 531 update the check value, and determine whether any progress has been made 532 during that inflate() call in order to return the proper return code. 533 Progress is defined as a change in either strm->avail_in or strm->avail_out. 534 When there is a window, goto inf_leave will update the window with the last 535 output written. If a goto inf_leave occurs in the middle of decompression 536 and there is no window currently, goto inf_leave will create one and copy 537 output to the window for the next call of inflate(). 538 539 In this implementation, the flush parameter of inflate() only affects the 540 return code (per zlib.h). inflate() always writes as much as possible to 541 strm->next_out, given the space available and the provided input--the effect 542 documented in zlib.h of Z_SYNC_FLUSH. Furthermore, inflate() always defers 543 the allocation of and copying into a sliding window until necessary, which 544 provides the effect documented in zlib.h for Z_FINISH when the entire input 545 stream available. So the only thing the flush parameter actually does is: 546 when flush is set to Z_FINISH, inflate() cannot return Z_OK. Instead it 547 will return Z_BUF_ERROR if it has not reached the end of the stream. 548 */ 549 550 int 551 inflate(z_streamp strm, int flush) 552 { 553 struct inflate_state FAR *state; 554 z_const unsigned char FAR *next; /* next input */ 555 unsigned char FAR *put; /* next output */ 556 unsigned have, left; /* available input and output */ 557 unsigned long hold; /* bit buffer */ 558 unsigned bits; /* bits in bit buffer */ 559 unsigned in, out; /* save starting available input and output */ 560 unsigned copy; /* number of stored or match bytes to copy */ 561 unsigned char FAR *from; /* where to copy match bytes from */ 562 code here; /* current decoding table entry */ 563 code last; /* parent table entry */ 564 unsigned len; /* length to copy for repeats, bits to drop */ 565 int ret; /* return code */ 566 567 static const unsigned short order[19] = /* permutation of code lengths */ 568 {16, 17, 18, 0, 8, 7, 9, 6, 10, 5, 11, 4, 12, 3, 13, 2, 14, 1, 15}; 569 570 if (strm == Z_NULL || strm->state == Z_NULL || strm->next_out == Z_NULL || 571 (strm->next_in == Z_NULL && strm->avail_in != 0)) 572 return Z_STREAM_ERROR; 573 574 state = (struct inflate_state FAR *)strm->state; 575 if (state->mode == TYPE) state->mode = TYPEDO; /* skip check */ 576 LOAD(); 577 in = have; 578 out = left; 579 ret = Z_OK; 580 for (;;) 581 switch (state->mode) { 582 case HEAD: 583 if (state->wrap == 0) { 584 state->mode = TYPEDO; 585 break; 586 } 587 NEEDBITS(16); 588 if (((BITS(8) << 8) + (hold >> 8)) % 31) { 589 strm->msg = (const char *)"incorrect header check"; 590 state->mode = BAD; 591 break; 592 } 593 if (BITS(4) != Z_DEFLATED) { 594 strm->msg = (const char *)"unknown compression method"; 595 state->mode = BAD; 596 break; 597 } 598 DROPBITS(4); 599 len = BITS(4) + 8; 600 if (state->wbits == 0) 601 state->wbits = len; 602 else if (len > state->wbits) { 603 strm->msg = (const char *)"invalid window size"; 604 state->mode = BAD; 605 break; 606 } 607 state->dmax = 1U << len; 608 Tracev((stderr, "inflate: zlib header ok\n")); 609 strm->adler = state->check = adler32(0L, Z_NULL, 0); 610 state->mode = hold & 0x200 ? DICTID : TYPE; 611 INITBITS(); 612 break; 613 case DICTID: 614 NEEDBITS(32); 615 strm->adler = state->check = ZSWAP32(hold); 616 INITBITS(); 617 state->mode = DICT; 618 /* fall through */ 619 case DICT: 620 if (state->havedict == 0) { 621 RESTORE(); 622 return Z_NEED_DICT; 623 } 624 strm->adler = state->check = adler32(0L, Z_NULL, 0); 625 state->mode = TYPE; 626 /* fall through */ 627 case TYPE: 628 if (flush == Z_BLOCK || flush == Z_TREES) goto inf_leave; 629 /* fall through */ 630 case TYPEDO: 631 if (state->last) { 632 BYTEBITS(); 633 state->mode = CHECK; 634 break; 635 } 636 NEEDBITS(3); 637 state->last = BITS(1); 638 DROPBITS(1); 639 switch (BITS(2)) { 640 case 0: /* stored block */ 641 Tracev((stderr, "inflate: stored block%s\n", 642 state->last ? " (last)" : "")); 643 state->mode = STORED; 644 break; 645 case 1: /* fixed block */ 646 fixedtables(state); 647 Tracev((stderr, "inflate: fixed codes block%s\n", 648 state->last ? " (last)" : "")); 649 state->mode = LEN_; /* decode codes */ 650 if (flush == Z_TREES) { 651 DROPBITS(2); 652 goto inf_leave; 653 } 654 break; 655 case 2: /* dynamic block */ 656 Tracev((stderr, "inflate: dynamic codes block%s\n", 657 state->last ? " (last)" : "")); 658 state->mode = TABLE; 659 break; 660 case 3: 661 strm->msg = (const char *)"invalid block type"; 662 state->mode = BAD; 663 } 664 DROPBITS(2); 665 break; 666 case STORED: 667 BYTEBITS(); /* go to byte boundary */ 668 NEEDBITS(32); 669 if ((hold & 0xffff) != ((hold >> 16) ^ 0xffff)) { 670 strm->msg = (const char *)"invalid stored block lengths"; 671 state->mode = BAD; 672 break; 673 } 674 state->length = (unsigned)hold & 0xffff; 675 Tracev((stderr, "inflate: stored length %u\n", 676 state->length)); 677 INITBITS(); 678 state->mode = COPY_; 679 if (flush == Z_TREES) goto inf_leave; 680 /* fall through */ 681 case COPY_: 682 state->mode = COPY; 683 /* fall through */ 684 case COPY: 685 copy = state->length; 686 if (copy) { 687 if (copy > have) copy = have; 688 if (copy > left) copy = left; 689 if (copy == 0) goto inf_leave; 690 zmemcpy(put, next, copy); 691 have -= copy; 692 next += copy; 693 left -= copy; 694 put += copy; 695 state->length -= copy; 696 break; 697 } 698 Tracev((stderr, "inflate: stored end\n")); 699 state->mode = TYPE; 700 break; 701 case TABLE: 702 NEEDBITS(14); 703 state->nlen = BITS(5) + 257; 704 DROPBITS(5); 705 state->ndist = BITS(5) + 1; 706 DROPBITS(5); 707 state->ncode = BITS(4) + 4; 708 DROPBITS(4); 709 #ifndef PKZIP_BUG_WORKAROUND 710 if (state->nlen > 286 || state->ndist > 30) { 711 strm->msg = (const char *)"too many length or distance symbols"; 712 state->mode = BAD; 713 break; 714 } 715 #endif 716 Tracev((stderr, "inflate: table sizes ok\n")); 717 state->have = 0; 718 state->mode = LENLENS; 719 /* fall through */ 720 case LENLENS: 721 while (state->have < state->ncode) { 722 NEEDBITS(3); 723 state->lens[order[state->have++]] = (unsigned short)BITS(3); 724 DROPBITS(3); 725 } 726 while (state->have < 19) 727 state->lens[order[state->have++]] = 0; 728 state->next = state->codes; 729 state->lencode = (const code FAR *)(state->next); 730 state->lenbits = 7; 731 ret = inflate_table(CODES, state->lens, 19, &(state->next), 732 &(state->lenbits), state->work); 733 if (ret) { 734 strm->msg = (const char *)"invalid code lengths set"; 735 state->mode = BAD; 736 break; 737 } 738 Tracev((stderr, "inflate: code lengths ok\n")); 739 state->have = 0; 740 state->mode = CODELENS; 741 /* fall through */ 742 case CODELENS: 743 while (state->have < state->nlen + state->ndist) { 744 for (;;) { 745 here = state->lencode[BITS(state->lenbits)]; 746 if ((unsigned)(here.bits) <= bits) break; 747 PULLBYTE(); 748 } 749 if (here.val < 16) { 750 DROPBITS(here.bits); 751 state->lens[state->have++] = here.val; 752 } 753 else { 754 if (here.val == 16) { 755 NEEDBITS(here.bits + 2); 756 DROPBITS(here.bits); 757 if (state->have == 0) { 758 strm->msg = (const char *)"invalid bit length repeat"; 759 state->mode = BAD; 760 break; 761 } 762 len = state->lens[state->have - 1]; 763 copy = 3 + BITS(2); 764 DROPBITS(2); 765 } 766 else if (here.val == 17) { 767 NEEDBITS(here.bits + 3); 768 DROPBITS(here.bits); 769 len = 0; 770 copy = 3 + BITS(3); 771 DROPBITS(3); 772 } 773 else { 774 NEEDBITS(here.bits + 7); 775 DROPBITS(here.bits); 776 len = 0; 777 copy = 11 + BITS(7); 778 DROPBITS(7); 779 } 780 if (state->have + copy > state->nlen + state->ndist) { 781 strm->msg = (const char *)"invalid bit length repeat"; 782 state->mode = BAD; 783 break; 784 } 785 while (copy--) 786 state->lens[state->have++] = (unsigned short)len; 787 } 788 } 789 790 /* handle error breaks in while */ 791 if (state->mode == BAD) break; 792 793 /* check for end-of-block code (better have one) */ 794 if (state->lens[256] == 0) { 795 strm->msg = (const char *)"invalid code -- missing end-of-block"; 796 state->mode = BAD; 797 break; 798 } 799 800 /* build code tables -- note: do not change the lenbits or distbits 801 values here (9 and 6) without reading the comments in inftrees.h 802 concerning the ENOUGH constants, which depend on those values */ 803 state->next = state->codes; 804 state->lencode = (const code FAR *)(state->next); 805 state->lenbits = 9; 806 ret = inflate_table(LENS, state->lens, state->nlen, &(state->next), 807 &(state->lenbits), state->work); 808 if (ret) { 809 strm->msg = (const char *)"invalid literal/lengths set"; 810 state->mode = BAD; 811 break; 812 } 813 state->distcode = (const code FAR *)(state->next); 814 state->distbits = 6; 815 ret = inflate_table(DISTS, state->lens + state->nlen, state->ndist, 816 &(state->next), &(state->distbits), state->work); 817 if (ret) { 818 strm->msg = (const char *)"invalid distances set"; 819 state->mode = BAD; 820 break; 821 } 822 Tracev((stderr, "inflate: codes ok\n")); 823 state->mode = LEN_; 824 if (flush == Z_TREES) goto inf_leave; 825 /* fall through */ 826 case LEN_: 827 state->mode = LEN; 828 /* fall through */ 829 case LEN: 830 if (have >= 6 && left >= 258) { 831 RESTORE(); 832 inflate_fast(strm, out); 833 LOAD(); 834 if (state->mode == TYPE) 835 state->back = -1; 836 break; 837 } 838 state->back = 0; 839 for (;;) { 840 here = state->lencode[BITS(state->lenbits)]; 841 if ((unsigned)(here.bits) <= bits) break; 842 PULLBYTE(); 843 } 844 if (here.op && (here.op & 0xf0) == 0) { 845 last = here; 846 for (;;) { 847 here = state->lencode[last.val + 848 (BITS(last.bits + last.op) >> last.bits)]; 849 if ((unsigned)(last.bits + here.bits) <= bits) break; 850 PULLBYTE(); 851 } 852 DROPBITS(last.bits); 853 state->back += last.bits; 854 } 855 DROPBITS(here.bits); 856 state->back += here.bits; 857 state->length = (unsigned)here.val; 858 if ((int)(here.op) == 0) { 859 Tracevv((stderr, here.val >= 0x20 && here.val < 0x7f ? 860 "inflate: literal '%c'\n" : 861 "inflate: literal 0x%02x\n", here.val)); 862 state->mode = LIT; 863 break; 864 } 865 if (here.op & 32) { 866 Tracevv((stderr, "inflate: end of block\n")); 867 state->back = -1; 868 state->mode = TYPE; 869 break; 870 } 871 if (here.op & 64) { 872 strm->msg = (const char *)"invalid literal/length code"; 873 state->mode = BAD; 874 break; 875 } 876 state->extra = (unsigned)(here.op) & 15; 877 state->mode = LENEXT; 878 /* fall through */ 879 case LENEXT: 880 if (state->extra) { 881 NEEDBITS(state->extra); 882 state->length += BITS(state->extra); 883 DROPBITS(state->extra); 884 state->back += state->extra; 885 } 886 Tracevv((stderr, "inflate: length %u\n", state->length)); 887 state->was = state->length; 888 state->mode = DIST; 889 /* fall through */ 890 case DIST: 891 for (;;) { 892 here = state->distcode[BITS(state->distbits)]; 893 if ((unsigned)(here.bits) <= bits) break; 894 PULLBYTE(); 895 } 896 if ((here.op & 0xf0) == 0) { 897 last = here; 898 for (;;) { 899 here = state->distcode[last.val + 900 (BITS(last.bits + last.op) >> last.bits)]; 901 if ((unsigned)(last.bits + here.bits) <= bits) break; 902 PULLBYTE(); 903 } 904 DROPBITS(last.bits); 905 state->back += last.bits; 906 } 907 DROPBITS(here.bits); 908 state->back += here.bits; 909 if (here.op & 64) { 910 strm->msg = (const char *)"invalid distance code"; 911 state->mode = BAD; 912 break; 913 } 914 state->offset = (unsigned)here.val; 915 state->extra = (unsigned)(here.op) & 15; 916 state->mode = DISTEXT; 917 /* fall through */ 918 case DISTEXT: 919 if (state->extra) { 920 NEEDBITS(state->extra); 921 state->offset += BITS(state->extra); 922 DROPBITS(state->extra); 923 state->back += state->extra; 924 } 925 #ifdef INFLATE_STRICT 926 if (state->offset > state->dmax) { 927 strm->msg = (const char *)"invalid distance too far back"; 928 state->mode = BAD; 929 break; 930 } 931 #endif 932 Tracevv((stderr, "inflate: distance %u\n", state->offset)); 933 state->mode = MATCH; 934 /* fall through */ 935 case MATCH: 936 if (left == 0) goto inf_leave; 937 copy = out - left; 938 if (state->offset > copy) { /* copy from window */ 939 copy = state->offset - copy; 940 if (copy > state->whave) { 941 if (state->sane) { 942 strm->msg = (const char *)"invalid distance too far back"; 943 state->mode = BAD; 944 break; 945 } 946 #ifdef INFLATE_ALLOW_INVALID_DISTANCE_TOOFAR_ARRR 947 Trace((stderr, "inflate.c too far\n")); 948 copy -= state->whave; 949 if (copy > state->length) copy = state->length; 950 if (copy > left) copy = left; 951 left -= copy; 952 state->length -= copy; 953 do { 954 *put++ = 0; 955 } while (--copy); 956 if (state->length == 0) state->mode = LEN; 957 break; 958 #endif 959 } 960 if (copy > state->wnext) { 961 copy -= state->wnext; 962 from = state->window + (state->wsize - copy); 963 } 964 else 965 from = state->window + (state->wnext - copy); 966 if (copy > state->length) copy = state->length; 967 } 968 else { /* copy from output */ 969 from = put - state->offset; 970 copy = state->length; 971 } 972 if (copy > left) copy = left; 973 left -= copy; 974 state->length -= copy; 975 do { 976 *put++ = *from++; 977 } while (--copy); 978 if (state->length == 0) state->mode = LEN; 979 break; 980 case LIT: 981 if (left == 0) goto inf_leave; 982 *put++ = (unsigned char)(state->length); 983 left--; 984 state->mode = LEN; 985 break; 986 case CHECK: 987 if (state->wrap) { 988 NEEDBITS(32); 989 out -= left; 990 strm->total_out += out; 991 state->total += out; 992 if (out) 993 strm->adler = state->check = 994 UPDATE(state->check, put - out, out); 995 out = left; 996 if ((ZSWAP32(hold)) != state->check) { 997 strm->msg = (const char *)"incorrect data check"; 998 state->mode = BAD; 999 break; 1000 } 1001 INITBITS(); 1002 Tracev((stderr, "inflate: check matches trailer\n")); 1003 } 1004 state->mode = DONE; 1005 /* fall through */ 1006 case DONE: 1007 ret = Z_STREAM_END; 1008 goto inf_leave; 1009 case BAD: 1010 ret = Z_DATA_ERROR; 1011 goto inf_leave; 1012 case MEM: 1013 return Z_MEM_ERROR; 1014 case SYNC: 1015 default: 1016 return Z_STREAM_ERROR; 1017 } 1018 1019 /* 1020 Return from inflate(), updating the total counts and the check value. 1021 If there was no progress during the inflate() call, return a buffer 1022 error. Call updatewindow() to create and/or update the window state. 1023 Note: a memory error from inflate() is non-recoverable. 1024 */ 1025 inf_leave: 1026 RESTORE(); 1027 if (state->wsize || (out != strm->avail_out && state->mode < BAD && 1028 (state->mode < CHECK || flush != Z_FINISH))) 1029 if (updatewindow(strm, strm->next_out, out - strm->avail_out)) { 1030 state->mode = MEM; 1031 return Z_MEM_ERROR; 1032 } 1033 in -= strm->avail_in; 1034 out -= strm->avail_out; 1035 strm->total_in += in; 1036 strm->total_out += out; 1037 state->total += out; 1038 if (state->wrap && out) 1039 strm->adler = state->check = 1040 UPDATE(state->check, strm->next_out - out, out); 1041 strm->data_type = state->bits + (state->last ? 64 : 0) + 1042 (state->mode == TYPE ? 128 : 0) + 1043 (state->mode == LEN_ || state->mode == COPY_ ? 256 : 0); 1044 if (((in == 0 && out == 0) || flush == Z_FINISH) && ret == Z_OK) 1045 ret = Z_BUF_ERROR; 1046 return ret; 1047 } 1048 1049 int 1050 inflateEnd(z_streamp strm) 1051 { 1052 struct inflate_state FAR *state; 1053 if (strm == Z_NULL || strm->state == Z_NULL) 1054 return Z_STREAM_ERROR; 1055 state = (struct inflate_state FAR *)strm->state; 1056 if (state->window != Z_NULL) free(state->window); 1057 free(strm->state); 1058 strm->state = Z_NULL; 1059 Tracev((stderr, "inflate: end\n")); 1060 return Z_OK; 1061 } 1062