inflate.c revision 131377
1/* inflate.c -- zlib decompression 2 * Copyright (C) 1995-2003 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 write == 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 "zutil.h" 84#include "inftrees.h" 85#include "inflate.h" 86#include "inffast.h" 87 88#ifdef MAKEFIXED 89# ifndef BUILDFIXED 90# define BUILDFIXED 91# endif 92#endif 93 94/* function prototypes */ 95local void fixedtables OF((struct inflate_state FAR *state)); 96local int updatewindow OF((z_streamp strm, unsigned out)); 97#ifdef BUILDFIXED 98 void makefixed OF((void)); 99#endif 100local unsigned syncsearch OF((unsigned FAR *have, unsigned char FAR *buf, 101 unsigned len)); 102 103int ZEXPORT inflateReset(strm) 104z_streamp strm; 105{ 106 struct inflate_state FAR *state; 107 108 if (strm == Z_NULL || strm->state == Z_NULL) return Z_STREAM_ERROR; 109 state = (struct inflate_state FAR *)strm->state; 110 strm->total_in = strm->total_out = state->total = 0; 111 strm->msg = Z_NULL; 112 state->mode = HEAD; 113 state->last = 0; 114 state->havedict = 0; 115 state->wsize = 0; 116 state->whave = 0; 117 state->hold = 0; 118 state->bits = 0; 119 state->lencode = state->distcode = state->next = state->codes; 120 Tracev((stderr, "inflate: reset\n")); 121 return Z_OK; 122} 123 124int ZEXPORT inflateInit2_(strm, windowBits, version, stream_size) 125z_streamp strm; 126int windowBits; 127const char *version; 128int stream_size; 129{ 130 struct inflate_state FAR *state; 131 132 if (version == Z_NULL || version[0] != ZLIB_VERSION[0] || 133 stream_size != (int)(sizeof(z_stream))) 134 return Z_VERSION_ERROR; 135 if (strm == Z_NULL) return Z_STREAM_ERROR; 136 strm->msg = Z_NULL; /* in case we return an error */ 137 if (strm->zalloc == (alloc_func)0) { 138 strm->zalloc = zcalloc; 139 strm->opaque = (voidpf)0; 140 } 141 if (strm->zfree == (free_func)0) strm->zfree = zcfree; 142 state = (struct inflate_state FAR *) 143 ZALLOC(strm, 1, sizeof(struct inflate_state)); 144 if (state == Z_NULL) return Z_MEM_ERROR; 145 Tracev((stderr, "inflate: allocated\n")); 146 strm->state = (voidpf)state; 147 if (windowBits < 0) { 148 state->wrap = 0; 149 windowBits = -windowBits; 150 } 151 else { 152 state->wrap = (windowBits >> 4) + 1; 153#ifdef GUNZIP 154 if (windowBits < 48) windowBits &= 15; 155#endif 156 } 157 if (windowBits < 8 || windowBits > 15) { 158 ZFREE(strm, state); 159 strm->state = Z_NULL; 160 return Z_STREAM_ERROR; 161 } 162 state->wbits = (unsigned)windowBits; 163 state->window = Z_NULL; 164 return inflateReset(strm); 165} 166 167int ZEXPORT inflateInit_(strm, version, stream_size) 168z_streamp strm; 169const char *version; 170int stream_size; 171{ 172 return inflateInit2_(strm, DEF_WBITS, version, stream_size); 173} 174 175/* 176 Return state with length and distance decoding tables and index sizes set to 177 fixed code decoding. Normally this returns fixed tables from inffixed.h. 178 If BUILDFIXED is defined, then instead this routine builds the tables the 179 first time it's called, and returns those tables the first time and 180 thereafter. This reduces the size of the code by about 2K bytes, in 181 exchange for a little execution time. However, BUILDFIXED should not be 182 used for threaded applications, since the rewriting of the tables and virgin 183 may not be thread-safe. 184 */ 185local void fixedtables(state) 186struct inflate_state FAR *state; 187{ 188#ifdef BUILDFIXED 189 static int virgin = 1; 190 static code *lenfix, *distfix; 191 static code fixed[544]; 192 193 /* build fixed huffman tables if first call (may not be thread safe) */ 194 if (virgin) { 195 unsigned sym, bits; 196 static code *next; 197 198 /* literal/length table */ 199 sym = 0; 200 while (sym < 144) state->lens[sym++] = 8; 201 while (sym < 256) state->lens[sym++] = 9; 202 while (sym < 280) state->lens[sym++] = 7; 203 while (sym < 288) state->lens[sym++] = 8; 204 next = fixed; 205 lenfix = next; 206 bits = 9; 207 inflate_table(LENS, state->lens, 288, &(next), &(bits), state->work); 208 209 /* distance table */ 210 sym = 0; 211 while (sym < 32) state->lens[sym++] = 5; 212 distfix = next; 213 bits = 5; 214 inflate_table(DISTS, state->lens, 32, &(next), &(bits), state->work); 215 216 /* do this just once */ 217 virgin = 0; 218 } 219#else /* !BUILDFIXED */ 220# include "inffixed.h" 221#endif /* BUILDFIXED */ 222 state->lencode = lenfix; 223 state->lenbits = 9; 224 state->distcode = distfix; 225 state->distbits = 5; 226} 227 228#ifdef MAKEFIXED 229#include <stdio.h> 230 231/* 232 Write out the inffixed.h that is #include'd above. Defining MAKEFIXED also 233 defines BUILDFIXED, so the tables are built on the fly. makefixed() writes 234 those tables to stdout, which would be piped to inffixed.h. A small program 235 can simply call makefixed to do this: 236 237 void makefixed(void); 238 239 int main(void) 240 { 241 makefixed(); 242 return 0; 243 } 244 245 Then that can be linked with zlib built with MAKEFIXED defined and run: 246 247 a.out > inffixed.h 248 */ 249void makefixed() 250{ 251 unsigned low, size; 252 struct inflate_state state; 253 254 fixedtables(&state); 255 puts(" /* inffixed.h -- table for decoding fixed codes"); 256 puts(" * Generated automatically by makefixed()."); 257 puts(" */"); 258 puts(""); 259 puts(" /* WARNING: this file should *not* be used by applications."); 260 puts(" It is part of the implementation of this library and is"); 261 puts(" subject to change. Applications should only use zlib.h."); 262 puts(" */"); 263 puts(""); 264 size = 1U << 9; 265 printf(" static const code lenfix[%u] = {", size); 266 low = 0; 267 for (;;) { 268 if ((low % 7) == 0) printf("\n "); 269 printf("{%u,%u,%d}", state.lencode[low].op, state.lencode[low].bits, 270 state.lencode[low].val); 271 if (++low == size) break; 272 putchar(','); 273 } 274 puts("\n };"); 275 size = 1U << 5; 276 printf("\n static const code distfix[%u] = {", size); 277 low = 0; 278 for (;;) { 279 if ((low % 6) == 0) printf("\n "); 280 printf("{%u,%u,%d}", state.distcode[low].op, state.distcode[low].bits, 281 state.distcode[low].val); 282 if (++low == size) break; 283 putchar(','); 284 } 285 puts("\n };"); 286} 287#endif /* MAKEFIXED */ 288 289/* 290 Update the window with the last wsize (normally 32K) bytes written before 291 returning. If window does not exist yet, create it. This is only called 292 when a window is already in use, or when output has been written during this 293 inflate call, but the end of the deflate stream has not been reached yet. 294 It is also called to create a window for dictionary data when a dictionary 295 is loaded. 296 297 Providing output buffers larger than 32K to inflate() should provide a speed 298 advantage, since only the last 32K of output is copied to the sliding window 299 upon return from inflate(), and since all distances after the first 32K of 300 output will fall in the output data, making match copies simpler and faster. 301 The advantage may be dependent on the size of the processor's data caches. 302 */ 303local int updatewindow(strm, out) 304z_streamp strm; 305unsigned out; 306{ 307 struct inflate_state FAR *state; 308 unsigned copy, dist; 309 310 state = (struct inflate_state FAR *)strm->state; 311 312 /* if it hasn't been done already, allocate space for the window */ 313 if (state->window == Z_NULL) { 314 state->window = (unsigned char FAR *) 315 ZALLOC(strm, 1U << state->wbits, 316 sizeof(unsigned char)); 317 if (state->window == Z_NULL) return 1; 318 } 319 320 /* if window not in use yet, initialize */ 321 if (state->wsize == 0) { 322 state->wsize = 1U << state->wbits; 323 state->write = 0; 324 state->whave = 0; 325 } 326 327 /* copy state->wsize or less output bytes into the circular window */ 328 copy = out - strm->avail_out; 329 if (copy >= state->wsize) { 330 zmemcpy(state->window, strm->next_out - state->wsize, state->wsize); 331 state->write = 0; 332 state->whave = state->wsize; 333 } 334 else { 335 dist = state->wsize - state->write; 336 if (dist > copy) dist = copy; 337 zmemcpy(state->window + state->write, strm->next_out - copy, dist); 338 copy -= dist; 339 if (copy) { 340 zmemcpy(state->window, strm->next_out - copy, copy); 341 state->write = copy; 342 state->whave = state->wsize; 343 } 344 else { 345 state->write += dist; 346 if (state->write == state->wsize) state->write = 0; 347 if (state->whave < state->wsize) state->whave += dist; 348 } 349 } 350 return 0; 351} 352 353/* Macros for inflate(): */ 354 355/* check function to use adler32() for zlib or crc32() for gzip */ 356#ifdef GUNZIP 357# define UPDATE(check, buf, len) \ 358 (state->flags ? crc32(check, buf, len) : adler32(check, buf, len)) 359#else 360# define UPDATE(check, buf, len) adler32(check, buf, len) 361#endif 362 363/* check macros for header crc */ 364#ifdef GUNZIP 365# define CRC2(check, word) \ 366 do { \ 367 hbuf[0] = (unsigned char)(word); \ 368 hbuf[1] = (unsigned char)((word) >> 8); \ 369 check = crc32(check, hbuf, 2); \ 370 } while (0) 371 372# define CRC4(check, word) \ 373 do { \ 374 hbuf[0] = (unsigned char)(word); \ 375 hbuf[1] = (unsigned char)((word) >> 8); \ 376 hbuf[2] = (unsigned char)((word) >> 16); \ 377 hbuf[3] = (unsigned char)((word) >> 24); \ 378 check = crc32(check, hbuf, 4); \ 379 } while (0) 380#endif 381 382/* Load registers with state in inflate() for speed */ 383#define LOAD() \ 384 do { \ 385 put = strm->next_out; \ 386 left = strm->avail_out; \ 387 next = strm->next_in; \ 388 have = strm->avail_in; \ 389 hold = state->hold; \ 390 bits = state->bits; \ 391 } while (0) 392 393/* Restore state from registers in inflate() */ 394#define RESTORE() \ 395 do { \ 396 strm->next_out = put; \ 397 strm->avail_out = left; \ 398 strm->next_in = next; \ 399 strm->avail_in = have; \ 400 state->hold = hold; \ 401 state->bits = bits; \ 402 } while (0) 403 404/* Clear the input bit accumulator */ 405#define INITBITS() \ 406 do { \ 407 hold = 0; \ 408 bits = 0; \ 409 } while (0) 410 411/* Get a byte of input into the bit accumulator, or return from inflate() 412 if there is no input available. */ 413#define PULLBYTE() \ 414 do { \ 415 if (have == 0) goto inf_leave; \ 416 have--; \ 417 hold += (unsigned long)(*next++) << bits; \ 418 bits += 8; \ 419 } while (0) 420 421/* Assure that there are at least n bits in the bit accumulator. If there is 422 not enough available input to do that, then return from inflate(). */ 423#define NEEDBITS(n) \ 424 do { \ 425 while (bits < (unsigned)(n)) \ 426 PULLBYTE(); \ 427 } while (0) 428 429/* Return the low n bits of the bit accumulator (n < 16) */ 430#define BITS(n) \ 431 ((unsigned)hold & ((1U << (n)) - 1)) 432 433/* Remove n bits from the bit accumulator */ 434#define DROPBITS(n) \ 435 do { \ 436 hold >>= (n); \ 437 bits -= (unsigned)(n); \ 438 } while (0) 439 440/* Remove zero to seven bits as needed to go to a byte boundary */ 441#define BYTEBITS() \ 442 do { \ 443 hold >>= bits & 7; \ 444 bits -= bits & 7; \ 445 } while (0) 446 447/* Reverse the bytes in a 32-bit value */ 448#define REVERSE(q) \ 449 ((((q) >> 24) & 0xff) + (((q) >> 8) & 0xff00) + \ 450 (((q) & 0xff00) << 8) + (((q) & 0xff) << 24)) 451 452/* 453 inflate() uses a state machine to process as much input data and generate as 454 much output data as possible before returning. The state machine is 455 structured roughly as follows: 456 457 for (;;) switch (state) { 458 ... 459 case STATEn: 460 if (not enough input data or output space to make progress) 461 return; 462 ... make progress ... 463 state = STATEm; 464 break; 465 ... 466 } 467 468 so when inflate() is called again, the same case is attempted again, and 469 if the appropriate resources are provided, the machine proceeds to the 470 next state. The NEEDBITS() macro is usually the way the state evaluates 471 whether it can proceed or should return. NEEDBITS() does the return if 472 the requested bits are not available. The typical use of the BITS macros 473 is: 474 475 NEEDBITS(n); 476 ... do something with BITS(n) ... 477 DROPBITS(n); 478 479 where NEEDBITS(n) either returns from inflate() if there isn't enough 480 input left to load n bits into the accumulator, or it continues. BITS(n) 481 gives the low n bits in the accumulator. When done, DROPBITS(n) drops 482 the low n bits off the accumulator. INITBITS() clears the accumulator 483 and sets the number of available bits to zero. BYTEBITS() discards just 484 enough bits to put the accumulator on a byte boundary. After BYTEBITS() 485 and a NEEDBITS(8), then BITS(8) would return the next byte in the stream. 486 487 NEEDBITS(n) uses PULLBYTE() to get an available byte of input, or to return 488 if there is no input available. The decoding of variable length codes uses 489 PULLBYTE() directly in order to pull just enough bytes to decode the next 490 code, and no more. 491 492 Some states loop until they get enough input, making sure that enough 493 state information is maintained to continue the loop where it left off 494 if NEEDBITS() returns in the loop. For example, want, need, and keep 495 would all have to actually be part of the saved state in case NEEDBITS() 496 returns: 497 498 case STATEw: 499 while (want < need) { 500 NEEDBITS(n); 501 keep[want++] = BITS(n); 502 DROPBITS(n); 503 } 504 state = STATEx; 505 case STATEx: 506 507 As shown above, if the next state is also the next case, then the break 508 is omitted. 509 510 A state may also return if there is not enough output space available to 511 complete that state. Those states are copying stored data, writing a 512 literal byte, and copying a matching string. 513 514 When returning, a "goto inf_leave" is used to update the total counters, 515 update the check value, and determine whether any progress has been made 516 during that inflate() call in order to return the proper return code. 517 Progress is defined as a change in either strm->avail_in or strm->avail_out. 518 When there is a window, goto inf_leave will update the window with the last 519 output written. If a goto inf_leave occurs in the middle of decompression 520 and there is no window currently, goto inf_leave will create one and copy 521 output to the window for the next call of inflate(). 522 523 In this implementation, the flush parameter of inflate() only affects the 524 return code (per zlib.h). inflate() always writes as much as possible to 525 strm->next_out, given the space available and the provided input--the effect 526 documented in zlib.h of Z_SYNC_FLUSH. Furthermore, inflate() always defers 527 the allocation of and copying into a sliding window until necessary, which 528 provides the effect documented in zlib.h for Z_FINISH when the entire input 529 stream available. So the only thing the flush parameter actually does is: 530 when flush is set to Z_FINISH, inflate() cannot return Z_OK. Instead it 531 will return Z_BUF_ERROR if it has not reached the end of the stream. 532 */ 533 534int ZEXPORT inflate(strm, flush) 535z_streamp strm; 536int flush; 537{ 538 struct inflate_state FAR *state; 539 unsigned char FAR *next; /* next input */ 540 unsigned char FAR *put; /* next output */ 541 unsigned have, left; /* available input and output */ 542 unsigned long hold; /* bit buffer */ 543 unsigned bits; /* bits in bit buffer */ 544 unsigned in, out; /* save starting available input and output */ 545 unsigned copy; /* number of stored or match bytes to copy */ 546 unsigned char FAR *from; /* where to copy match bytes from */ 547 code this; /* current decoding table entry */ 548 code last; /* parent table entry */ 549 unsigned len; /* length to copy for repeats, bits to drop */ 550 int ret; /* return code */ 551#ifdef GUNZIP 552 unsigned char hbuf[4]; /* buffer for gzip header crc calculation */ 553#endif 554 static const unsigned short order[19] = /* permutation of code lengths */ 555 {16, 17, 18, 0, 8, 7, 9, 6, 10, 5, 11, 4, 12, 3, 13, 2, 14, 1, 15}; 556 557 if (strm == Z_NULL || strm->state == Z_NULL || strm->next_out == Z_NULL || 558 (strm->next_in == Z_NULL && strm->avail_in != 0)) 559 return Z_STREAM_ERROR; 560 561 state = (struct inflate_state FAR *)strm->state; 562 if (state->mode == TYPE) state->mode = TYPEDO; /* skip check */ 563 LOAD(); 564 in = have; 565 out = left; 566 ret = Z_OK; 567 for (;;) 568 switch (state->mode) { 569 case HEAD: 570 if (state->wrap == 0) { 571 state->mode = TYPEDO; 572 break; 573 } 574 NEEDBITS(16); 575#ifdef GUNZIP 576 if ((state->wrap & 2) && hold == 0x8b1f) { /* gzip header */ 577 state->check = crc32(0L, Z_NULL, 0); 578 CRC2(state->check, hold); 579 INITBITS(); 580 state->mode = FLAGS; 581 break; 582 } 583 state->flags = 0; /* expect zlib header */ 584 if (!(state->wrap & 1) || /* check if zlib header allowed */ 585#else 586 if ( 587#endif 588 ((BITS(8) << 8) + (hold >> 8)) % 31) { 589 strm->msg = (char *)"incorrect header check"; 590 state->mode = BAD; 591 break; 592 } 593 if (BITS(4) != Z_DEFLATED) { 594 strm->msg = (char *)"unknown compression method"; 595 state->mode = BAD; 596 break; 597 } 598 DROPBITS(4); 599 if (BITS(4) + 8 > state->wbits) { 600 strm->msg = (char *)"invalid window size"; 601 state->mode = BAD; 602 break; 603 } 604 Tracev((stderr, "inflate: zlib header ok\n")); 605 strm->adler = state->check = adler32(0L, Z_NULL, 0); 606 state->mode = hold & 0x200 ? DICTID : TYPE; 607 INITBITS(); 608 break; 609#ifdef GUNZIP 610 case FLAGS: 611 NEEDBITS(16); 612 state->flags = (int)(hold); 613 if ((state->flags & 0xff) != Z_DEFLATED) { 614 strm->msg = (char *)"unknown compression method"; 615 state->mode = BAD; 616 break; 617 } 618 if (state->flags & 0xe000) { 619 strm->msg = (char *)"unknown header flags set"; 620 state->mode = BAD; 621 break; 622 } 623 if (state->flags & 0x0200) CRC2(state->check, hold); 624 INITBITS(); 625 state->mode = TIME; 626 case TIME: 627 NEEDBITS(32); 628 if (state->flags & 0x0200) CRC4(state->check, hold); 629 INITBITS(); 630 state->mode = OS; 631 case OS: 632 NEEDBITS(16); 633 if (state->flags & 0x0200) CRC2(state->check, hold); 634 INITBITS(); 635 state->mode = EXLEN; 636 case EXLEN: 637 if (state->flags & 0x0400) { 638 NEEDBITS(16); 639 state->length = (unsigned)(hold); 640 if (state->flags & 0x0200) CRC2(state->check, hold); 641 INITBITS(); 642 } 643 state->mode = EXTRA; 644 case EXTRA: 645 if (state->flags & 0x0400) { 646 copy = state->length; 647 if (copy > have) copy = have; 648 if (copy) { 649 if (state->flags & 0x0200) 650 state->check = crc32(state->check, next, copy); 651 have -= copy; 652 next += copy; 653 state->length -= copy; 654 } 655 if (state->length) goto inf_leave; 656 } 657 state->mode = NAME; 658 case NAME: 659 if (state->flags & 0x0800) { 660 if (have == 0) goto inf_leave; 661 copy = 0; 662 do { 663 len = (unsigned)(next[copy++]); 664 } while (len && copy < have); 665 if (state->flags & 0x02000) 666 state->check = crc32(state->check, next, copy); 667 have -= copy; 668 next += copy; 669 if (len) goto inf_leave; 670 } 671 state->mode = COMMENT; 672 case COMMENT: 673 if (state->flags & 0x1000) { 674 if (have == 0) goto inf_leave; 675 copy = 0; 676 do { 677 len = (unsigned)(next[copy++]); 678 } while (len && copy < have); 679 if (state->flags & 0x02000) 680 state->check = crc32(state->check, next, copy); 681 have -= copy; 682 next += copy; 683 if (len) goto inf_leave; 684 } 685 state->mode = HCRC; 686 case HCRC: 687 if (state->flags & 0x0200) { 688 NEEDBITS(16); 689 if (hold != (state->check & 0xffff)) { 690 strm->msg = (char *)"header crc mismatch"; 691 state->mode = BAD; 692 break; 693 } 694 INITBITS(); 695 } 696 strm->adler = state->check = crc32(0L, Z_NULL, 0); 697 state->mode = TYPE; 698 break; 699#endif 700 case DICTID: 701 NEEDBITS(32); 702 strm->adler = state->check = REVERSE(hold); 703 INITBITS(); 704 state->mode = DICT; 705 case DICT: 706 if (state->havedict == 0) { 707 RESTORE(); 708 return Z_NEED_DICT; 709 } 710 strm->adler = state->check = adler32(0L, Z_NULL, 0); 711 state->mode = TYPE; 712 case TYPE: 713 if (flush == Z_BLOCK) goto inf_leave; 714 case TYPEDO: 715 if (state->last) { 716 BYTEBITS(); 717 state->mode = CHECK; 718 break; 719 } 720 NEEDBITS(3); 721 state->last = BITS(1); 722 DROPBITS(1); 723 switch (BITS(2)) { 724 case 0: /* stored block */ 725 Tracev((stderr, "inflate: stored block%s\n", 726 state->last ? " (last)" : "")); 727 state->mode = STORED; 728 break; 729 case 1: /* fixed block */ 730 fixedtables(state); 731 Tracev((stderr, "inflate: fixed codes block%s\n", 732 state->last ? " (last)" : "")); 733 state->mode = LEN; /* decode codes */ 734 break; 735 case 2: /* dynamic block */ 736 Tracev((stderr, "inflate: dynamic codes block%s\n", 737 state->last ? " (last)" : "")); 738 state->mode = TABLE; 739 break; 740 case 3: 741 strm->msg = (char *)"invalid block type"; 742 state->mode = BAD; 743 } 744 DROPBITS(2); 745 break; 746 case STORED: 747 BYTEBITS(); /* go to byte boundary */ 748 NEEDBITS(32); 749 if ((hold & 0xffff) != ((hold >> 16) ^ 0xffff)) { 750 strm->msg = (char *)"invalid stored block lengths"; 751 state->mode = BAD; 752 break; 753 } 754 state->length = (unsigned)hold & 0xffff; 755 Tracev((stderr, "inflate: stored length %u\n", 756 state->length)); 757 INITBITS(); 758 state->mode = COPY; 759 case COPY: 760 copy = state->length; 761 if (copy) { 762 if (copy > have) copy = have; 763 if (copy > left) copy = left; 764 if (copy == 0) goto inf_leave; 765 zmemcpy(put, next, copy); 766 have -= copy; 767 next += copy; 768 left -= copy; 769 put += copy; 770 state->length -= copy; 771 break; 772 } 773 Tracev((stderr, "inflate: stored end\n")); 774 state->mode = TYPE; 775 break; 776 case TABLE: 777 NEEDBITS(14); 778 state->nlen = BITS(5) + 257; 779 DROPBITS(5); 780 state->ndist = BITS(5) + 1; 781 DROPBITS(5); 782 state->ncode = BITS(4) + 4; 783 DROPBITS(4); 784#ifndef PKZIP_BUG_WORKAROUND 785 if (state->nlen > 286 || state->ndist > 30) { 786 strm->msg = (char *)"too many length or distance symbols"; 787 state->mode = BAD; 788 break; 789 } 790#endif 791 Tracev((stderr, "inflate: table sizes ok\n")); 792 state->have = 0; 793 state->mode = LENLENS; 794 case LENLENS: 795 while (state->have < state->ncode) { 796 NEEDBITS(3); 797 state->lens[order[state->have++]] = (unsigned short)BITS(3); 798 DROPBITS(3); 799 } 800 while (state->have < 19) 801 state->lens[order[state->have++]] = 0; 802 state->next = state->codes; 803 state->lencode = (code const FAR *)(state->next); 804 state->lenbits = 7; 805 ret = inflate_table(CODES, state->lens, 19, &(state->next), 806 &(state->lenbits), state->work); 807 if (ret) { 808 strm->msg = (char *)"invalid code lengths set"; 809 state->mode = BAD; 810 break; 811 } 812 Tracev((stderr, "inflate: code lengths ok\n")); 813 state->have = 0; 814 state->mode = CODELENS; 815 case CODELENS: 816 while (state->have < state->nlen + state->ndist) { 817 for (;;) { 818 this = state->lencode[BITS(state->lenbits)]; 819 if ((unsigned)(this.bits) <= bits) break; 820 PULLBYTE(); 821 } 822 if (this.val < 16) { 823 NEEDBITS(this.bits); 824 DROPBITS(this.bits); 825 state->lens[state->have++] = this.val; 826 } 827 else { 828 if (this.val == 16) { 829 NEEDBITS(this.bits + 2); 830 DROPBITS(this.bits); 831 if (state->have == 0) { 832 strm->msg = (char *)"invalid bit length repeat"; 833 state->mode = BAD; 834 break; 835 } 836 len = state->lens[state->have - 1]; 837 copy = 3 + BITS(2); 838 DROPBITS(2); 839 } 840 else if (this.val == 17) { 841 NEEDBITS(this.bits + 3); 842 DROPBITS(this.bits); 843 len = 0; 844 copy = 3 + BITS(3); 845 DROPBITS(3); 846 } 847 else { 848 NEEDBITS(this.bits + 7); 849 DROPBITS(this.bits); 850 len = 0; 851 copy = 11 + BITS(7); 852 DROPBITS(7); 853 } 854 if (state->have + copy > state->nlen + state->ndist) { 855 strm->msg = (char *)"invalid bit length repeat"; 856 state->mode = BAD; 857 break; 858 } 859 while (copy--) 860 state->lens[state->have++] = (unsigned short)len; 861 } 862 } 863 864 /* build code tables */ 865 state->next = state->codes; 866 state->lencode = (code const FAR *)(state->next); 867 state->lenbits = 9; 868 ret = inflate_table(LENS, state->lens, state->nlen, &(state->next), 869 &(state->lenbits), state->work); 870 if (ret) { 871 strm->msg = (char *)"invalid literal/lengths set"; 872 state->mode = BAD; 873 break; 874 } 875 state->distcode = (code const FAR *)(state->next); 876 state->distbits = 6; 877 ret = inflate_table(DISTS, state->lens + state->nlen, state->ndist, 878 &(state->next), &(state->distbits), state->work); 879 if (ret) { 880 strm->msg = (char *)"invalid distances set"; 881 state->mode = BAD; 882 break; 883 } 884 Tracev((stderr, "inflate: codes ok\n")); 885 state->mode = LEN; 886 case LEN: 887 if (have >= 6 && left >= 258) { 888 RESTORE(); 889 inflate_fast(strm, out); 890 LOAD(); 891 break; 892 } 893 for (;;) { 894 this = state->lencode[BITS(state->lenbits)]; 895 if ((unsigned)(this.bits) <= bits) break; 896 PULLBYTE(); 897 } 898 if (this.op && (this.op & 0xf0) == 0) { 899 last = this; 900 for (;;) { 901 this = state->lencode[last.val + 902 (BITS(last.bits + last.op) >> last.bits)]; 903 if ((unsigned)(last.bits + this.bits) <= bits) break; 904 PULLBYTE(); 905 } 906 DROPBITS(last.bits); 907 } 908 DROPBITS(this.bits); 909 state->length = (unsigned)this.val; 910 if ((int)(this.op) == 0) { 911 Tracevv((stderr, this.val >= 0x20 && this.val < 0x7f ? 912 "inflate: literal '%c'\n" : 913 "inflate: literal 0x%02x\n", this.val)); 914 state->mode = LIT; 915 break; 916 } 917 if (this.op & 32) { 918 Tracevv((stderr, "inflate: end of block\n")); 919 state->mode = TYPE; 920 break; 921 } 922 if (this.op & 64) { 923 strm->msg = (char *)"invalid literal/length code"; 924 state->mode = BAD; 925 break; 926 } 927 state->extra = (unsigned)(this.op) & 15; 928 state->mode = LENEXT; 929 case LENEXT: 930 if (state->extra) { 931 NEEDBITS(state->extra); 932 state->length += BITS(state->extra); 933 DROPBITS(state->extra); 934 } 935 Tracevv((stderr, "inflate: length %u\n", state->length)); 936 state->mode = DIST; 937 case DIST: 938 for (;;) { 939 this = state->distcode[BITS(state->distbits)]; 940 if ((unsigned)(this.bits) <= bits) break; 941 PULLBYTE(); 942 } 943 if ((this.op & 0xf0) == 0) { 944 last = this; 945 for (;;) { 946 this = state->distcode[last.val + 947 (BITS(last.bits + last.op) >> last.bits)]; 948 if ((unsigned)(last.bits + this.bits) <= bits) break; 949 PULLBYTE(); 950 } 951 DROPBITS(last.bits); 952 } 953 DROPBITS(this.bits); 954 if (this.op & 64) { 955 strm->msg = (char *)"invalid distance code"; 956 state->mode = BAD; 957 break; 958 } 959 state->offset = (unsigned)this.val; 960 state->extra = (unsigned)(this.op) & 15; 961 state->mode = DISTEXT; 962 case DISTEXT: 963 if (state->extra) { 964 NEEDBITS(state->extra); 965 state->offset += BITS(state->extra); 966 DROPBITS(state->extra); 967 } 968 if (state->offset > state->whave + out - left) { 969 strm->msg = (char *)"invalid distance too far back"; 970 state->mode = BAD; 971 break; 972 } 973 Tracevv((stderr, "inflate: distance %u\n", state->offset)); 974 state->mode = MATCH; 975 case MATCH: 976 if (left == 0) goto inf_leave; 977 copy = out - left; 978 if (state->offset > copy) { /* copy from window */ 979 copy = state->offset - copy; 980 if (copy > state->write) { 981 copy -= state->write; 982 from = state->window + (state->wsize - copy); 983 } 984 else 985 from = state->window + (state->write - copy); 986 if (copy > state->length) copy = state->length; 987 } 988 else { /* copy from output */ 989 from = put - state->offset; 990 copy = state->length; 991 } 992 if (copy > left) copy = left; 993 left -= copy; 994 state->length -= copy; 995 do { 996 *put++ = *from++; 997 } while (--copy); 998 if (state->length == 0) state->mode = LEN; 999 break; 1000 case LIT: 1001 if (left == 0) goto inf_leave; 1002 *put++ = (unsigned char)(state->length); 1003 left--; 1004 state->mode = LEN; 1005 break; 1006 case CHECK: 1007 if (state->wrap) { 1008 NEEDBITS(32); 1009 out -= left; 1010 strm->total_out += out; 1011 state->total += out; 1012 if (out) 1013 strm->adler = state->check = 1014 UPDATE(state->check, put - out, out); 1015 out = left; 1016 if (( 1017#ifdef GUNZIP 1018 state->flags ? hold : 1019#endif 1020 REVERSE(hold)) != state->check) { 1021 strm->msg = (char *)"incorrect data check"; 1022 state->mode = BAD; 1023 break; 1024 } 1025 INITBITS(); 1026 Tracev((stderr, "inflate: check matches trailer\n")); 1027 } 1028#ifdef GUNZIP 1029 state->mode = LENGTH; 1030 case LENGTH: 1031 if (state->wrap && state->flags) { 1032 NEEDBITS(32); 1033 if (hold != (state->total & 0xffffffffUL)) { 1034 strm->msg = (char *)"incorrect length check"; 1035 state->mode = BAD; 1036 break; 1037 } 1038 INITBITS(); 1039 Tracev((stderr, "inflate: length matches trailer\n")); 1040 } 1041#endif 1042 state->mode = DONE; 1043 case DONE: 1044 ret = Z_STREAM_END; 1045 goto inf_leave; 1046 case BAD: 1047 ret = Z_DATA_ERROR; 1048 goto inf_leave; 1049 case MEM: 1050 return Z_MEM_ERROR; 1051 case SYNC: 1052 default: 1053 return Z_STREAM_ERROR; 1054 } 1055 1056 /* 1057 Return from inflate(), updating the total counts and the check value. 1058 If there was no progress during the inflate() call, return a buffer 1059 error. Call updatewindow() to create and/or update the window state. 1060 Note: a memory error from inflate() is non-recoverable. 1061 */ 1062 inf_leave: 1063 RESTORE(); 1064 if (state->wsize || (state->mode < CHECK && out != strm->avail_out)) 1065 if (updatewindow(strm, out)) { 1066 state->mode = MEM; 1067 return Z_MEM_ERROR; 1068 } 1069 in -= strm->avail_in; 1070 out -= strm->avail_out; 1071 strm->total_in += in; 1072 strm->total_out += out; 1073 state->total += out; 1074 if (state->wrap && out) 1075 strm->adler = state->check = 1076 UPDATE(state->check, strm->next_out - out, out); 1077 strm->data_type = state->bits + (state->last ? 64 : 0) + 1078 (state->mode == TYPE ? 128 : 0); 1079 if (((in == 0 && out == 0) || flush == Z_FINISH) && ret == Z_OK) 1080 ret = Z_BUF_ERROR; 1081 return ret; 1082} 1083 1084int ZEXPORT inflateEnd(strm) 1085z_streamp strm; 1086{ 1087 struct inflate_state FAR *state; 1088 if (strm == Z_NULL || strm->state == Z_NULL || strm->zfree == (free_func)0) 1089 return Z_STREAM_ERROR; 1090 state = (struct inflate_state FAR *)strm->state; 1091 if (state->window != Z_NULL) ZFREE(strm, state->window); 1092 ZFREE(strm, strm->state); 1093 strm->state = Z_NULL; 1094 Tracev((stderr, "inflate: end\n")); 1095 return Z_OK; 1096} 1097 1098int ZEXPORT inflateSetDictionary(strm, dictionary, dictLength) 1099z_streamp strm; 1100const Bytef *dictionary; 1101uInt dictLength; 1102{ 1103 struct inflate_state FAR *state; 1104 unsigned long id; 1105 1106 /* check state */ 1107 if (strm == Z_NULL || strm->state == Z_NULL) return Z_STREAM_ERROR; 1108 state = (struct inflate_state FAR *)strm->state; 1109 if (state->mode != DICT) return Z_STREAM_ERROR; 1110 1111 /* check for correct dictionary id */ 1112 id = adler32(0L, Z_NULL, 0); 1113 id = adler32(id, dictionary, dictLength); 1114 if (id != state->check) return Z_DATA_ERROR; 1115 1116 /* copy dictionary to window */ 1117 if (updatewindow(strm, strm->avail_out)) { 1118 state->mode = MEM; 1119 return Z_MEM_ERROR; 1120 } 1121 if (dictLength > state->wsize) { 1122 zmemcpy(state->window, dictionary + dictLength - state->wsize, 1123 state->wsize); 1124 state->whave = state->wsize; 1125 } 1126 else { 1127 zmemcpy(state->window + state->wsize - dictLength, dictionary, 1128 dictLength); 1129 state->whave = dictLength; 1130 } 1131 state->havedict = 1; 1132 Tracev((stderr, "inflate: dictionary set\n")); 1133 return Z_OK; 1134} 1135 1136/* 1137 Search buf[0..len-1] for the pattern: 0, 0, 0xff, 0xff. Return when found 1138 or when out of input. When called, *have is the number of pattern bytes 1139 found in order so far, in 0..3. On return *have is updated to the new 1140 state. If on return *have equals four, then the pattern was found and the 1141 return value is how many bytes were read including the last byte of the 1142 pattern. If *have is less than four, then the pattern has not been found 1143 yet and the return value is len. In the latter case, syncsearch() can be 1144 called again with more data and the *have state. *have is initialized to 1145 zero for the first call. 1146 */ 1147local unsigned syncsearch(have, buf, len) 1148unsigned FAR *have; 1149unsigned char FAR *buf; 1150unsigned len; 1151{ 1152 unsigned got; 1153 unsigned next; 1154 1155 got = *have; 1156 next = 0; 1157 while (next < len && got < 4) { 1158 if ((int)(buf[next]) == (got < 2 ? 0 : 0xff)) 1159 got++; 1160 else if (buf[next]) 1161 got = 0; 1162 else 1163 got = 4 - got; 1164 next++; 1165 } 1166 *have = got; 1167 return next; 1168} 1169 1170int ZEXPORT inflateSync(strm) 1171z_streamp strm; 1172{ 1173 unsigned len; /* number of bytes to look at or looked at */ 1174 unsigned long in, out; /* temporary to save total_in and total_out */ 1175 unsigned char buf[4]; /* to restore bit buffer to byte string */ 1176 struct inflate_state FAR *state; 1177 1178 /* check parameters */ 1179 if (strm == Z_NULL || strm->state == Z_NULL) return Z_STREAM_ERROR; 1180 state = (struct inflate_state FAR *)strm->state; 1181 if (strm->avail_in == 0 && state->bits < 8) return Z_BUF_ERROR; 1182 1183 /* if first time, start search in bit buffer */ 1184 if (state->mode != SYNC) { 1185 state->mode = SYNC; 1186 state->hold <<= state->bits & 7; 1187 state->bits -= state->bits & 7; 1188 len = 0; 1189 while (state->bits >= 8) { 1190 buf[len++] = (unsigned char)(state->hold); 1191 state->hold >>= 8; 1192 state->bits -= 8; 1193 } 1194 state->have = 0; 1195 syncsearch(&(state->have), buf, len); 1196 } 1197 1198 /* search available input */ 1199 len = syncsearch(&(state->have), strm->next_in, strm->avail_in); 1200 strm->avail_in -= len; 1201 strm->next_in += len; 1202 strm->total_in += len; 1203 1204 /* return no joy or set up to restart inflate() on a new block */ 1205 if (state->have != 4) return Z_DATA_ERROR; 1206 in = strm->total_in; out = strm->total_out; 1207 inflateReset(strm); 1208 strm->total_in = in; strm->total_out = out; 1209 state->mode = TYPE; 1210 return Z_OK; 1211} 1212 1213/* 1214 Returns true if inflate is currently at the end of a block generated by 1215 Z_SYNC_FLUSH or Z_FULL_FLUSH. This function is used by one PPP 1216 implementation to provide an additional safety check. PPP uses 1217 Z_SYNC_FLUSH but removes the length bytes of the resulting empty stored 1218 block. When decompressing, PPP checks that at the end of input packet, 1219 inflate is waiting for these length bytes. 1220 */ 1221int ZEXPORT inflateSyncPoint(strm) 1222z_streamp strm; 1223{ 1224 struct inflate_state FAR *state; 1225 1226 if (strm == Z_NULL || strm->state == Z_NULL) return Z_STREAM_ERROR; 1227 state = (struct inflate_state FAR *)strm->state; 1228 return state->mode == STORED && state->bits == 0; 1229} 1230 1231int ZEXPORT inflateCopy(dest, source) 1232z_streamp dest; 1233z_streamp source; 1234{ 1235 struct inflate_state FAR *state; 1236 struct inflate_state FAR *copy; 1237 unsigned char FAR *window; 1238 1239 /* check input */ 1240 if (dest == Z_NULL || source == Z_NULL || source->state == Z_NULL || 1241 source->zalloc == (alloc_func)0 || source->zfree == (free_func)0) 1242 return Z_STREAM_ERROR; 1243 state = (struct inflate_state FAR *)source->state; 1244 1245 /* allocate space */ 1246 copy = (struct inflate_state FAR *) 1247 ZALLOC(source, 1, sizeof(struct inflate_state)); 1248 if (copy == Z_NULL) return Z_MEM_ERROR; 1249 window = Z_NULL; 1250 if (state->window != Z_NULL) { 1251 window = (unsigned char FAR *) 1252 ZALLOC(source, 1U << state->wbits, sizeof(unsigned char)); 1253 if (window == Z_NULL) { 1254 ZFREE(source, copy); 1255 return Z_MEM_ERROR; 1256 } 1257 } 1258 1259 /* copy state */ 1260 *dest = *source; 1261 *copy = *state; 1262 copy->lencode = copy->codes + (state->lencode - state->codes); 1263 copy->distcode = copy->codes + (state->distcode - state->codes); 1264 copy->next = copy->codes + (state->next - state->codes); 1265 if (window != Z_NULL) 1266 zmemcpy(window, state->window, 1U << state->wbits); 1267 copy->window = window; 1268 dest->state = (voidpf)copy; 1269 return Z_OK; 1270} 1271