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