inflate.c revision 1.6
1/* $OpenBSD: inflate.c,v 1.6 2003/12/17 00:28:19 millert 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 /* build code tables */ 914 state->next = state->codes; 915 state->lencode = (code const FAR *)(state->next); 916 state->lenbits = 9; 917 ret = inflate_table(LENS, state->lens, state->nlen, &(state->next), 918 &(state->lenbits), state->work); 919 if (ret) { 920#ifdef SMALL 921 strm->msg = "error"; 922#else 923 strm->msg = (char *)"invalid literal/lengths set"; 924#endif 925 state->mode = BAD; 926 break; 927 } 928 state->distcode = (code const FAR *)(state->next); 929 state->distbits = 6; 930 ret = inflate_table(DISTS, state->lens + state->nlen, state->ndist, 931 &(state->next), &(state->distbits), state->work); 932 if (ret) { 933#ifdef SMALL 934 strm->msg = "error"; 935#else 936 strm->msg = (char *)"invalid distances set"; 937#endif 938 state->mode = BAD; 939 break; 940 } 941 Tracev((stderr, "inflate: codes ok\n")); 942 state->mode = LEN; 943 case LEN: 944#ifndef SLOW 945 if (have >= 6 && left >= 258) { 946 RESTORE(); 947 inflate_fast(strm, out); 948 LOAD(); 949 break; 950 } 951#endif 952 for (;;) { 953 this = state->lencode[BITS(state->lenbits)]; 954 if ((unsigned)(this.bits) <= bits) break; 955 PULLBYTE(); 956 } 957 if (this.op && (this.op & 0xf0) == 0) { 958 last = this; 959 for (;;) { 960 this = state->lencode[last.val + 961 (BITS(last.bits + last.op) >> last.bits)]; 962 if ((unsigned)(last.bits + this.bits) <= bits) break; 963 PULLBYTE(); 964 } 965 DROPBITS(last.bits); 966 } 967 DROPBITS(this.bits); 968 state->length = (unsigned)this.val; 969 if ((int)(this.op) == 0) { 970 Tracevv((stderr, this.val >= 0x20 && this.val < 0x7f ? 971 "inflate: literal '%c'\n" : 972 "inflate: literal 0x%02x\n", this.val)); 973 state->mode = LIT; 974 break; 975 } 976 if (this.op & 32) { 977 Tracevv((stderr, "inflate: end of block\n")); 978 state->mode = TYPE; 979 break; 980 } 981 if (this.op & 64) { 982#ifdef SMALL 983 strm->msg = "error"; 984#else 985 strm->msg = (char *)"invalid literal/length code"; 986#endif 987 state->mode = BAD; 988 break; 989 } 990 state->extra = (unsigned)(this.op) & 15; 991 state->mode = LENEXT; 992 case LENEXT: 993 if (state->extra) { 994 NEEDBITS(state->extra); 995 state->length += BITS(state->extra); 996 DROPBITS(state->extra); 997 } 998 Tracevv((stderr, "inflate: length %u\n", state->length)); 999 state->mode = DIST; 1000 case DIST: 1001 for (;;) { 1002 this = state->distcode[BITS(state->distbits)]; 1003 if ((unsigned)(this.bits) <= bits) break; 1004 PULLBYTE(); 1005 } 1006 if ((this.op & 0xf0) == 0) { 1007 last = this; 1008 for (;;) { 1009 this = state->distcode[last.val + 1010 (BITS(last.bits + last.op) >> last.bits)]; 1011 if ((unsigned)(last.bits + this.bits) <= bits) break; 1012 PULLBYTE(); 1013 } 1014 DROPBITS(last.bits); 1015 } 1016 DROPBITS(this.bits); 1017 if (this.op & 64) { 1018#ifdef SMALL 1019 strm->msg = "error"; 1020#else 1021 strm->msg = (char *)"invalid distance code"; 1022#endif 1023 state->mode = BAD; 1024 break; 1025 } 1026 state->offset = (unsigned)this.val; 1027 state->extra = (unsigned)(this.op) & 15; 1028 state->mode = DISTEXT; 1029 case DISTEXT: 1030 if (state->extra) { 1031 NEEDBITS(state->extra); 1032 state->offset += BITS(state->extra); 1033 DROPBITS(state->extra); 1034 } 1035 if (state->offset > state->whave + out - left) { 1036#ifdef SMALL 1037 strm->msg = "error"; 1038#else 1039 strm->msg = (char *)"invalid distance too far back"; 1040#endif 1041 state->mode = BAD; 1042 break; 1043 } 1044 Tracevv((stderr, "inflate: distance %u\n", state->offset)); 1045 state->mode = MATCH; 1046 case MATCH: 1047 if (left == 0) goto inf_leave; 1048 copy = out - left; 1049 if (state->offset > copy) { /* copy from window */ 1050 copy = state->offset - copy; 1051 if (copy > state->write) { 1052 copy -= state->write; 1053 from = state->window + (state->wsize - copy); 1054 } 1055 else 1056 from = state->window + (state->write - copy); 1057 if (copy > state->length) copy = state->length; 1058 } 1059 else { /* copy from output */ 1060 from = put - state->offset; 1061 copy = state->length; 1062 } 1063 if (copy > left) copy = left; 1064 left -= copy; 1065 state->length -= copy; 1066 do { 1067 *put++ = *from++; 1068 } while (--copy); 1069 if (state->length == 0) state->mode = LEN; 1070 break; 1071 case LIT: 1072 if (left == 0) goto inf_leave; 1073 *put++ = (unsigned char)(state->length); 1074 left--; 1075 state->mode = LEN; 1076 break; 1077 case CHECK: 1078 if (state->wrap) { 1079 NEEDBITS(32); 1080 out -= left; 1081 strm->total_out += out; 1082 state->total += out; 1083 if (out) 1084 strm->adler = state->check = 1085 UPDATE(state->check, put - out, out); 1086 out = left; 1087 if (( 1088#ifdef GUNZIP 1089 state->flags ? hold : 1090#endif 1091 REVERSE(hold)) != state->check) { 1092#ifdef SMALL 1093 strm->msg = "error"; 1094#else 1095 strm->msg = (char *)"incorrect data check"; 1096#endif 1097 state->mode = BAD; 1098 break; 1099 } 1100 INITBITS(); 1101 Tracev((stderr, "inflate: check matches trailer\n")); 1102 } 1103#ifdef GUNZIP 1104 state->mode = LENGTH; 1105 case LENGTH: 1106 if (state->wrap && state->flags) { 1107 NEEDBITS(32); 1108 if (hold != (state->total & 0xffffffffUL)) { 1109#ifdef SMALL 1110 strm->msg = "error"; 1111#else 1112 strm->msg = (char *)"incorrect length check"; 1113#endif 1114 state->mode = BAD; 1115 break; 1116 } 1117 INITBITS(); 1118 Tracev((stderr, "inflate: length matches trailer\n")); 1119 } 1120#endif 1121 state->mode = DONE; 1122 case DONE: 1123 ret = Z_STREAM_END; 1124 goto inf_leave; 1125 case BAD: 1126 ret = Z_DATA_ERROR; 1127 goto inf_leave; 1128 case MEM: 1129 return Z_MEM_ERROR; 1130 case SYNC: 1131 default: 1132 return Z_STREAM_ERROR; 1133 } 1134 1135 /* 1136 Return from inflate(), updating the total counts and the check value. 1137 If there was no progress during the inflate() call, return a buffer 1138 error. Call updatewindow() to create and/or update the window state. 1139 Note: a memory error from inflate() is non-recoverable. 1140 */ 1141 inf_leave: 1142 RESTORE(); 1143 if (state->wsize || (state->mode < CHECK && out != strm->avail_out)) 1144 if (updatewindow(strm, out)) { 1145 state->mode = MEM; 1146 return Z_MEM_ERROR; 1147 } 1148 in -= strm->avail_in; 1149 out -= strm->avail_out; 1150 strm->total_in += in; 1151 strm->total_out += out; 1152 state->total += out; 1153 if (state->wrap && out) 1154 strm->adler = state->check = 1155 UPDATE(state->check, strm->next_out - out, out); 1156 strm->data_type = state->bits + (state->last ? 64 : 0) + 1157 (state->mode == TYPE ? 128 : 0); 1158 if (((in == 0 && out == 0) || flush == Z_FINISH) && ret == Z_OK) 1159 ret = Z_BUF_ERROR; 1160 return ret; 1161} 1162 1163int ZEXPORT inflateEnd(strm) 1164z_streamp strm; 1165{ 1166 struct inflate_state FAR *state; 1167 if (strm == Z_NULL || strm->state == Z_NULL || strm->zfree == (free_func)0) 1168 return Z_STREAM_ERROR; 1169 state = (struct inflate_state FAR *)strm->state; 1170 if (state->window != Z_NULL) ZFREE(strm, state->window); 1171 ZFREE(strm, strm->state); 1172 strm->state = Z_NULL; 1173 Tracev((stderr, "inflate: end\n")); 1174 return Z_OK; 1175} 1176 1177int ZEXPORT inflateSetDictionary(strm, dictionary, dictLength) 1178z_streamp strm; 1179const Bytef *dictionary; 1180uInt dictLength; 1181{ 1182 struct inflate_state FAR *state; 1183 unsigned long id; 1184 1185 /* check state */ 1186 if (strm == Z_NULL || strm->state == Z_NULL) return Z_STREAM_ERROR; 1187 state = (struct inflate_state FAR *)strm->state; 1188 if (state->mode != DICT) return Z_STREAM_ERROR; 1189 1190 /* check for correct dictionary id */ 1191 id = adler32(0L, Z_NULL, 0); 1192 id = adler32(id, dictionary, dictLength); 1193 if (id != state->check) return Z_DATA_ERROR; 1194 1195 /* copy dictionary to window */ 1196 if (updatewindow(strm, strm->avail_out)) { 1197 state->mode = MEM; 1198 return Z_MEM_ERROR; 1199 } 1200 if (dictLength > state->wsize) { 1201 zmemcpy(state->window, dictionary + dictLength - state->wsize, 1202 state->wsize); 1203 state->whave = state->wsize; 1204 } 1205 else { 1206 zmemcpy(state->window + state->wsize - dictLength, dictionary, 1207 dictLength); 1208 state->whave = dictLength; 1209 } 1210 state->havedict = 1; 1211 Tracev((stderr, "inflate: dictionary set\n")); 1212 return Z_OK; 1213} 1214 1215/* 1216 Search buf[0..len-1] for the pattern: 0, 0, 0xff, 0xff. Return when found 1217 or when out of input. When called, *have is the number of pattern bytes 1218 found in order so far, in 0..3. On return *have is updated to the new 1219 state. If on return *have equals four, then the pattern was found and the 1220 return value is how many bytes were read including the last byte of the 1221 pattern. If *have is less than four, then the pattern has not been found 1222 yet and the return value is len. In the latter case, syncsearch() can be 1223 called again with more data and the *have state. *have is initialized to 1224 zero for the first call. 1225 */ 1226local unsigned syncsearch(have, buf, len) 1227unsigned FAR *have; 1228unsigned char FAR *buf; 1229unsigned len; 1230{ 1231 unsigned got; 1232 unsigned next; 1233 1234 got = *have; 1235 next = 0; 1236 while (next < len && got < 4) { 1237 if ((int)(buf[next]) == (got < 2 ? 0 : 0xff)) 1238 got++; 1239 else if (buf[next]) 1240 got = 0; 1241 else 1242 got = 4 - got; 1243 next++; 1244 } 1245 *have = got; 1246 return next; 1247} 1248 1249int ZEXPORT inflateSync(strm) 1250z_streamp strm; 1251{ 1252 unsigned len; /* number of bytes to look at or looked at */ 1253 unsigned long in, out; /* temporary to save total_in and total_out */ 1254 unsigned char buf[4]; /* to restore bit buffer to byte string */ 1255 struct inflate_state FAR *state; 1256 1257 /* check parameters */ 1258 if (strm == Z_NULL || strm->state == Z_NULL) return Z_STREAM_ERROR; 1259 state = (struct inflate_state FAR *)strm->state; 1260 if (strm->avail_in == 0 && state->bits < 8) return Z_BUF_ERROR; 1261 1262 /* if first time, start search in bit buffer */ 1263 if (state->mode != SYNC) { 1264 state->mode = SYNC; 1265 state->hold <<= state->bits & 7; 1266 state->bits -= state->bits & 7; 1267 len = 0; 1268 while (state->bits >= 8) { 1269 buf[len++] = (unsigned char)(state->hold); 1270 state->hold >>= 8; 1271 state->bits -= 8; 1272 } 1273 state->have = 0; 1274 syncsearch(&(state->have), buf, len); 1275 } 1276 1277 /* search available input */ 1278 len = syncsearch(&(state->have), strm->next_in, strm->avail_in); 1279 strm->avail_in -= len; 1280 strm->next_in += len; 1281 strm->total_in += len; 1282 1283 /* return no joy or set up to restart inflate() on a new block */ 1284 if (state->have != 4) return Z_DATA_ERROR; 1285 in = strm->total_in; out = strm->total_out; 1286 inflateReset(strm); 1287 strm->total_in = in; strm->total_out = out; 1288 state->mode = TYPE; 1289 return Z_OK; 1290} 1291 1292/* 1293 Returns true if inflate is currently at the end of a block generated by 1294 Z_SYNC_FLUSH or Z_FULL_FLUSH. This function is used by one PPP 1295 implementation to provide an additional safety check. PPP uses 1296 Z_SYNC_FLUSH but removes the length bytes of the resulting empty stored 1297 block. When decompressing, PPP checks that at the end of input packet, 1298 inflate is waiting for these length bytes. 1299 */ 1300int ZEXPORT inflateSyncPoint(strm) 1301z_streamp strm; 1302{ 1303 struct inflate_state FAR *state; 1304 1305 if (strm == Z_NULL || strm->state == Z_NULL) return Z_STREAM_ERROR; 1306 state = (struct inflate_state FAR *)strm->state; 1307 return state->mode == STORED && state->bits == 0; 1308} 1309 1310int ZEXPORT inflateCopy(dest, source) 1311z_streamp dest; 1312z_streamp source; 1313{ 1314 struct inflate_state FAR *state; 1315 struct inflate_state FAR *copy; 1316 unsigned char FAR *window; 1317 1318 /* check input */ 1319 if (dest == Z_NULL || source == Z_NULL || source->state == Z_NULL || 1320 source->zalloc == (alloc_func)0 || source->zfree == (free_func)0) 1321 return Z_STREAM_ERROR; 1322 state = (struct inflate_state FAR *)source->state; 1323 1324 /* allocate space */ 1325 copy = (struct inflate_state FAR *) 1326 ZALLOC(source, 1, sizeof(struct inflate_state)); 1327 if (copy == Z_NULL) return Z_MEM_ERROR; 1328 window = Z_NULL; 1329 if (state->window != Z_NULL) { 1330 window = (unsigned char FAR *) 1331 ZALLOC(source, 1U << state->wbits, sizeof(unsigned char)); 1332 if (window == Z_NULL) { 1333 ZFREE(source, copy); 1334 return Z_MEM_ERROR; 1335 } 1336 } 1337 1338 /* copy state */ 1339 *dest = *source; 1340 *copy = *state; 1341 copy->lencode = copy->codes + (state->lencode - state->codes); 1342 copy->distcode = copy->codes + (state->distcode - state->codes); 1343 copy->next = copy->codes + (state->next - state->codes); 1344 if (window != Z_NULL) 1345 zmemcpy(window, state->window, 1U << state->wbits); 1346 copy->window = window; 1347 dest->state = (voidpf)copy; 1348 return Z_OK; 1349} 1350