inflate.c revision 1.4
1/* $OpenBSD: inflate.c,v 1.4 2003/12/16 22:33:02 henning 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 strm->msg = (char *)"incorrect header check"; 591 state->mode = BAD; 592 break; 593 } 594 if (BITS(4) != Z_DEFLATED) { 595 strm->msg = (char *)"unknown compression method"; 596 state->mode = BAD; 597 break; 598 } 599 DROPBITS(4); 600 if (BITS(4) + 8 > state->wbits) { 601 strm->msg = (char *)"invalid window size"; 602 state->mode = BAD; 603 break; 604 } 605 Tracev((stderr, "inflate: zlib header ok\n")); 606 strm->adler = state->check = adler32(0L, Z_NULL, 0); 607 state->mode = hold & 0x200 ? DICTID : TYPE; 608 INITBITS(); 609 break; 610#ifdef GUNZIP 611 case FLAGS: 612 NEEDBITS(16); 613 state->flags = (int)(hold); 614 if ((state->flags & 0xff) != Z_DEFLATED) { 615 strm->msg = (char *)"unknown compression method"; 616 state->mode = BAD; 617 break; 618 } 619 if (state->flags & 0xe000) { 620 strm->msg = (char *)"unknown header flags set"; 621 state->mode = BAD; 622 break; 623 } 624 if (state->flags & 0x0200) CRC2(state->check, hold); 625 INITBITS(); 626 state->mode = TIME; 627 case TIME: 628 NEEDBITS(32); 629 if (state->flags & 0x0200) CRC4(state->check, hold); 630 INITBITS(); 631 state->mode = OS; 632 case OS: 633 NEEDBITS(16); 634 if (state->flags & 0x0200) CRC2(state->check, hold); 635 INITBITS(); 636 state->mode = EXLEN; 637 case EXLEN: 638 if (state->flags & 0x0400) { 639 NEEDBITS(16); 640 state->length = (unsigned)(hold); 641 if (state->flags & 0x0200) CRC2(state->check, hold); 642 INITBITS(); 643 } 644 state->mode = EXTRA; 645 case EXTRA: 646 if (state->flags & 0x0400) { 647 copy = state->length; 648 if (copy > have) copy = have; 649 if (copy) { 650 if (state->flags & 0x0200) 651 state->check = crc32(state->check, next, copy); 652 have -= copy; 653 next += copy; 654 state->length -= copy; 655 } 656 if (state->length) goto inf_leave; 657 } 658 state->mode = NAME; 659 case NAME: 660 if (state->flags & 0x0800) { 661 if (have == 0) goto inf_leave; 662 copy = 0; 663 do { 664 len = (unsigned)(next[copy++]); 665 } while (len && copy < have); 666 if (state->flags & 0x02000) 667 state->check = crc32(state->check, next, copy); 668 have -= copy; 669 next += copy; 670 if (len) goto inf_leave; 671 } 672 state->mode = COMMENT; 673 case COMMENT: 674 if (state->flags & 0x1000) { 675 if (have == 0) goto inf_leave; 676 copy = 0; 677 do { 678 len = (unsigned)(next[copy++]); 679 } while (len && copy < have); 680 if (state->flags & 0x02000) 681 state->check = crc32(state->check, next, copy); 682 have -= copy; 683 next += copy; 684 if (len) goto inf_leave; 685 } 686 state->mode = HCRC; 687 case HCRC: 688 if (state->flags & 0x0200) { 689 NEEDBITS(16); 690 if (hold != (state->check & 0xffff)) { 691 strm->msg = (char *)"header crc mismatch"; 692 state->mode = BAD; 693 break; 694 } 695 INITBITS(); 696 } 697 strm->adler = state->check = crc32(0L, Z_NULL, 0); 698 state->mode = TYPE; 699 break; 700#endif 701 case DICTID: 702 NEEDBITS(32); 703 strm->adler = state->check = REVERSE(hold); 704 INITBITS(); 705 state->mode = DICT; 706 case DICT: 707 if (state->havedict == 0) { 708 RESTORE(); 709 return Z_NEED_DICT; 710 } 711 strm->adler = state->check = adler32(0L, Z_NULL, 0); 712 state->mode = TYPE; 713 case TYPE: 714 if (flush == Z_BLOCK) goto inf_leave; 715 case TYPEDO: 716 if (state->last) { 717 BYTEBITS(); 718 state->mode = CHECK; 719 break; 720 } 721 NEEDBITS(3); 722 state->last = BITS(1); 723 DROPBITS(1); 724 switch (BITS(2)) { 725 case 0: /* stored block */ 726 Tracev((stderr, "inflate: stored block%s\n", 727 state->last ? " (last)" : "")); 728 state->mode = STORED; 729 break; 730 case 1: /* fixed block */ 731 fixedtables(state); 732 Tracev((stderr, "inflate: fixed codes block%s\n", 733 state->last ? " (last)" : "")); 734 state->mode = LEN; /* decode codes */ 735 break; 736 case 2: /* dynamic block */ 737 Tracev((stderr, "inflate: dynamic codes block%s\n", 738 state->last ? " (last)" : "")); 739 state->mode = TABLE; 740 break; 741 case 3: 742 strm->msg = (char *)"invalid block type"; 743 state->mode = BAD; 744 } 745 DROPBITS(2); 746 break; 747 case STORED: 748 BYTEBITS(); /* go to byte boundary */ 749 NEEDBITS(32); 750 if ((hold & 0xffff) != ((hold >> 16) ^ 0xffff)) { 751 strm->msg = (char *)"invalid stored block lengths"; 752 state->mode = BAD; 753 break; 754 } 755 state->length = (unsigned)hold & 0xffff; 756 Tracev((stderr, "inflate: stored length %u\n", 757 state->length)); 758 INITBITS(); 759 state->mode = COPY; 760 case COPY: 761 copy = state->length; 762 if (copy) { 763 if (copy > have) copy = have; 764 if (copy > left) copy = left; 765 if (copy == 0) goto inf_leave; 766 zmemcpy(put, next, copy); 767 have -= copy; 768 next += copy; 769 left -= copy; 770 put += copy; 771 state->length -= copy; 772 break; 773 } 774 Tracev((stderr, "inflate: stored end\n")); 775 state->mode = TYPE; 776 break; 777 case TABLE: 778 NEEDBITS(14); 779 state->nlen = BITS(5) + 257; 780 DROPBITS(5); 781 state->ndist = BITS(5) + 1; 782 DROPBITS(5); 783 state->ncode = BITS(4) + 4; 784 DROPBITS(4); 785#ifndef PKZIP_BUG_WORKAROUND 786 if (state->nlen > 286 || state->ndist > 30) { 787 strm->msg = (char *)"too many length or distance symbols"; 788 state->mode = BAD; 789 break; 790 } 791#endif 792 Tracev((stderr, "inflate: table sizes ok\n")); 793 state->have = 0; 794 state->mode = LENLENS; 795 case LENLENS: 796 while (state->have < state->ncode) { 797 NEEDBITS(3); 798 state->lens[order[state->have++]] = (unsigned short)BITS(3); 799 DROPBITS(3); 800 } 801 while (state->have < 19) 802 state->lens[order[state->have++]] = 0; 803 state->next = state->codes; 804 state->lencode = (code const FAR *)(state->next); 805 state->lenbits = 7; 806 ret = inflate_table(CODES, state->lens, 19, &(state->next), 807 &(state->lenbits), state->work); 808 if (ret) { 809 strm->msg = (char *)"invalid code lengths set"; 810 state->mode = BAD; 811 break; 812 } 813 Tracev((stderr, "inflate: code lengths ok\n")); 814 state->have = 0; 815 state->mode = CODELENS; 816 case CODELENS: 817 while (state->have < state->nlen + state->ndist) { 818 for (;;) { 819 this = state->lencode[BITS(state->lenbits)]; 820 if ((unsigned)(this.bits) <= bits) break; 821 PULLBYTE(); 822 } 823 if (this.val < 16) { 824 NEEDBITS(this.bits); 825 DROPBITS(this.bits); 826 state->lens[state->have++] = this.val; 827 } 828 else { 829 if (this.val == 16) { 830 NEEDBITS(this.bits + 2); 831 DROPBITS(this.bits); 832 if (state->have == 0) { 833 strm->msg = (char *)"invalid bit length repeat"; 834 state->mode = BAD; 835 break; 836 } 837 len = state->lens[state->have - 1]; 838 copy = 3 + BITS(2); 839 DROPBITS(2); 840 } 841 else if (this.val == 17) { 842 NEEDBITS(this.bits + 3); 843 DROPBITS(this.bits); 844 len = 0; 845 copy = 3 + BITS(3); 846 DROPBITS(3); 847 } 848 else { 849 NEEDBITS(this.bits + 7); 850 DROPBITS(this.bits); 851 len = 0; 852 copy = 11 + BITS(7); 853 DROPBITS(7); 854 } 855 if (state->have + copy > state->nlen + state->ndist) { 856 strm->msg = (char *)"invalid bit length repeat"; 857 state->mode = BAD; 858 break; 859 } 860 while (copy--) 861 state->lens[state->have++] = (unsigned short)len; 862 } 863 } 864 865 /* build code tables */ 866 state->next = state->codes; 867 state->lencode = (code const FAR *)(state->next); 868 state->lenbits = 9; 869 ret = inflate_table(LENS, state->lens, state->nlen, &(state->next), 870 &(state->lenbits), state->work); 871 if (ret) { 872 strm->msg = (char *)"invalid literal/lengths set"; 873 state->mode = BAD; 874 break; 875 } 876 state->distcode = (code const FAR *)(state->next); 877 state->distbits = 6; 878 ret = inflate_table(DISTS, state->lens + state->nlen, state->ndist, 879 &(state->next), &(state->distbits), state->work); 880 if (ret) { 881 strm->msg = (char *)"invalid distances set"; 882 state->mode = BAD; 883 break; 884 } 885 Tracev((stderr, "inflate: codes ok\n")); 886 state->mode = LEN; 887 case LEN: 888 if (have >= 6 && left >= 258) { 889 RESTORE(); 890 inflate_fast(strm, out); 891 LOAD(); 892 break; 893 } 894 for (;;) { 895 this = state->lencode[BITS(state->lenbits)]; 896 if ((unsigned)(this.bits) <= bits) break; 897 PULLBYTE(); 898 } 899 if (this.op && (this.op & 0xf0) == 0) { 900 last = this; 901 for (;;) { 902 this = state->lencode[last.val + 903 (BITS(last.bits + last.op) >> last.bits)]; 904 if ((unsigned)(last.bits + this.bits) <= bits) break; 905 PULLBYTE(); 906 } 907 DROPBITS(last.bits); 908 } 909 DROPBITS(this.bits); 910 state->length = (unsigned)this.val; 911 if ((int)(this.op) == 0) { 912 Tracevv((stderr, this.val >= 0x20 && this.val < 0x7f ? 913 "inflate: literal '%c'\n" : 914 "inflate: literal 0x%02x\n", this.val)); 915 state->mode = LIT; 916 break; 917 } 918 if (this.op & 32) { 919 Tracevv((stderr, "inflate: end of block\n")); 920 state->mode = TYPE; 921 break; 922 } 923 if (this.op & 64) { 924 strm->msg = (char *)"invalid literal/length code"; 925 state->mode = BAD; 926 break; 927 } 928 state->extra = (unsigned)(this.op) & 15; 929 state->mode = LENEXT; 930 case LENEXT: 931 if (state->extra) { 932 NEEDBITS(state->extra); 933 state->length += BITS(state->extra); 934 DROPBITS(state->extra); 935 } 936 Tracevv((stderr, "inflate: length %u\n", state->length)); 937 state->mode = DIST; 938 case DIST: 939 for (;;) { 940 this = state->distcode[BITS(state->distbits)]; 941 if ((unsigned)(this.bits) <= bits) break; 942 PULLBYTE(); 943 } 944 if ((this.op & 0xf0) == 0) { 945 last = this; 946 for (;;) { 947 this = state->distcode[last.val + 948 (BITS(last.bits + last.op) >> last.bits)]; 949 if ((unsigned)(last.bits + this.bits) <= bits) break; 950 PULLBYTE(); 951 } 952 DROPBITS(last.bits); 953 } 954 DROPBITS(this.bits); 955 if (this.op & 64) { 956 strm->msg = (char *)"invalid distance code"; 957 state->mode = BAD; 958 break; 959 } 960 state->offset = (unsigned)this.val; 961 state->extra = (unsigned)(this.op) & 15; 962 state->mode = DISTEXT; 963 case DISTEXT: 964 if (state->extra) { 965 NEEDBITS(state->extra); 966 state->offset += BITS(state->extra); 967 DROPBITS(state->extra); 968 } 969 if (state->offset > state->whave + out - left) { 970 strm->msg = (char *)"invalid distance too far back"; 971 state->mode = BAD; 972 break; 973 } 974 Tracevv((stderr, "inflate: distance %u\n", state->offset)); 975 state->mode = MATCH; 976 case MATCH: 977 if (left == 0) goto inf_leave; 978 copy = out - left; 979 if (state->offset > copy) { /* copy from window */ 980 copy = state->offset - copy; 981 if (copy > state->write) { 982 copy -= state->write; 983 from = state->window + (state->wsize - copy); 984 } 985 else 986 from = state->window + (state->write - copy); 987 if (copy > state->length) copy = state->length; 988 } 989 else { /* copy from output */ 990 from = put - state->offset; 991 copy = state->length; 992 } 993 if (copy > left) copy = left; 994 left -= copy; 995 state->length -= copy; 996 do { 997 *put++ = *from++; 998 } while (--copy); 999 if (state->length == 0) state->mode = LEN; 1000 break; 1001 case LIT: 1002 if (left == 0) goto inf_leave; 1003 *put++ = (unsigned char)(state->length); 1004 left--; 1005 state->mode = LEN; 1006 break; 1007 case CHECK: 1008 if (state->wrap) { 1009 NEEDBITS(32); 1010 out -= left; 1011 strm->total_out += out; 1012 state->total += out; 1013 if (out) 1014 strm->adler = state->check = 1015 UPDATE(state->check, put - out, out); 1016 out = left; 1017 if (( 1018#ifdef GUNZIP 1019 state->flags ? hold : 1020#endif 1021 REVERSE(hold)) != state->check) { 1022 strm->msg = (char *)"incorrect data check"; 1023 state->mode = BAD; 1024 break; 1025 } 1026 INITBITS(); 1027 Tracev((stderr, "inflate: check matches trailer\n")); 1028 } 1029#ifdef GUNZIP 1030 state->mode = LENGTH; 1031 case LENGTH: 1032 if (state->wrap && state->flags) { 1033 NEEDBITS(32); 1034 if (hold != (state->total & 0xffffffffUL)) { 1035 strm->msg = (char *)"incorrect length check"; 1036 state->mode = BAD; 1037 break; 1038 } 1039 INITBITS(); 1040 Tracev((stderr, "inflate: length matches trailer\n")); 1041 } 1042#endif 1043 state->mode = DONE; 1044 case DONE: 1045 ret = Z_STREAM_END; 1046 goto inf_leave; 1047 case BAD: 1048 ret = Z_DATA_ERROR; 1049 goto inf_leave; 1050 case MEM: 1051 return Z_MEM_ERROR; 1052 case SYNC: 1053 default: 1054 return Z_STREAM_ERROR; 1055 } 1056 1057 /* 1058 Return from inflate(), updating the total counts and the check value. 1059 If there was no progress during the inflate() call, return a buffer 1060 error. Call updatewindow() to create and/or update the window state. 1061 Note: a memory error from inflate() is non-recoverable. 1062 */ 1063 inf_leave: 1064 RESTORE(); 1065 if (state->wsize || (state->mode < CHECK && out != strm->avail_out)) 1066 if (updatewindow(strm, out)) { 1067 state->mode = MEM; 1068 return Z_MEM_ERROR; 1069 } 1070 in -= strm->avail_in; 1071 out -= strm->avail_out; 1072 strm->total_in += in; 1073 strm->total_out += out; 1074 state->total += out; 1075 if (state->wrap && out) 1076 strm->adler = state->check = 1077 UPDATE(state->check, strm->next_out - out, out); 1078 strm->data_type = state->bits + (state->last ? 64 : 0) + 1079 (state->mode == TYPE ? 128 : 0); 1080 if (((in == 0 && out == 0) || flush == Z_FINISH) && ret == Z_OK) 1081 ret = Z_BUF_ERROR; 1082 return ret; 1083} 1084 1085int ZEXPORT inflateEnd(strm) 1086z_streamp strm; 1087{ 1088 struct inflate_state FAR *state; 1089 if (strm == Z_NULL || strm->state == Z_NULL || strm->zfree == (free_func)0) 1090 return Z_STREAM_ERROR; 1091 state = (struct inflate_state FAR *)strm->state; 1092 if (state->window != Z_NULL) ZFREE(strm, state->window); 1093 ZFREE(strm, strm->state); 1094 strm->state = Z_NULL; 1095 Tracev((stderr, "inflate: end\n")); 1096 return Z_OK; 1097} 1098 1099int ZEXPORT inflateSetDictionary(strm, dictionary, dictLength) 1100z_streamp strm; 1101const Bytef *dictionary; 1102uInt dictLength; 1103{ 1104 struct inflate_state FAR *state; 1105 unsigned long id; 1106 1107 /* check state */ 1108 if (strm == Z_NULL || strm->state == Z_NULL) return Z_STREAM_ERROR; 1109 state = (struct inflate_state FAR *)strm->state; 1110 if (state->mode != DICT) return Z_STREAM_ERROR; 1111 1112 /* check for correct dictionary id */ 1113 id = adler32(0L, Z_NULL, 0); 1114 id = adler32(id, dictionary, dictLength); 1115 if (id != state->check) return Z_DATA_ERROR; 1116 1117 /* copy dictionary to window */ 1118 if (updatewindow(strm, strm->avail_out)) { 1119 state->mode = MEM; 1120 return Z_MEM_ERROR; 1121 } 1122 if (dictLength > state->wsize) { 1123 zmemcpy(state->window, dictionary + dictLength - state->wsize, 1124 state->wsize); 1125 state->whave = state->wsize; 1126 } 1127 else { 1128 zmemcpy(state->window + state->wsize - dictLength, dictionary, 1129 dictLength); 1130 state->whave = dictLength; 1131 } 1132 state->havedict = 1; 1133 Tracev((stderr, "inflate: dictionary set\n")); 1134 return Z_OK; 1135} 1136 1137/* 1138 Search buf[0..len-1] for the pattern: 0, 0, 0xff, 0xff. Return when found 1139 or when out of input. When called, *have is the number of pattern bytes 1140 found in order so far, in 0..3. On return *have is updated to the new 1141 state. If on return *have equals four, then the pattern was found and the 1142 return value is how many bytes were read including the last byte of the 1143 pattern. If *have is less than four, then the pattern has not been found 1144 yet and the return value is len. In the latter case, syncsearch() can be 1145 called again with more data and the *have state. *have is initialized to 1146 zero for the first call. 1147 */ 1148local unsigned syncsearch(have, buf, len) 1149unsigned FAR *have; 1150unsigned char FAR *buf; 1151unsigned len; 1152{ 1153 unsigned got; 1154 unsigned next; 1155 1156 got = *have; 1157 next = 0; 1158 while (next < len && got < 4) { 1159 if ((int)(buf[next]) == (got < 2 ? 0 : 0xff)) 1160 got++; 1161 else if (buf[next]) 1162 got = 0; 1163 else 1164 got = 4 - got; 1165 next++; 1166 } 1167 *have = got; 1168 return next; 1169} 1170 1171int ZEXPORT inflateSync(strm) 1172z_streamp strm; 1173{ 1174 unsigned len; /* number of bytes to look at or looked at */ 1175 unsigned long in, out; /* temporary to save total_in and total_out */ 1176 unsigned char buf[4]; /* to restore bit buffer to byte string */ 1177 struct inflate_state FAR *state; 1178 1179 /* check parameters */ 1180 if (strm == Z_NULL || strm->state == Z_NULL) return Z_STREAM_ERROR; 1181 state = (struct inflate_state FAR *)strm->state; 1182 if (strm->avail_in == 0 && state->bits < 8) return Z_BUF_ERROR; 1183 1184 /* if first time, start search in bit buffer */ 1185 if (state->mode != SYNC) { 1186 state->mode = SYNC; 1187 state->hold <<= state->bits & 7; 1188 state->bits -= state->bits & 7; 1189 len = 0; 1190 while (state->bits >= 8) { 1191 buf[len++] = (unsigned char)(state->hold); 1192 state->hold >>= 8; 1193 state->bits -= 8; 1194 } 1195 state->have = 0; 1196 syncsearch(&(state->have), buf, len); 1197 } 1198 1199 /* search available input */ 1200 len = syncsearch(&(state->have), strm->next_in, strm->avail_in); 1201 strm->avail_in -= len; 1202 strm->next_in += len; 1203 strm->total_in += len; 1204 1205 /* return no joy or set up to restart inflate() on a new block */ 1206 if (state->have != 4) return Z_DATA_ERROR; 1207 in = strm->total_in; out = strm->total_out; 1208 inflateReset(strm); 1209 strm->total_in = in; strm->total_out = out; 1210 state->mode = TYPE; 1211 return Z_OK; 1212} 1213 1214/* 1215 Returns true if inflate is currently at the end of a block generated by 1216 Z_SYNC_FLUSH or Z_FULL_FLUSH. This function is used by one PPP 1217 implementation to provide an additional safety check. PPP uses 1218 Z_SYNC_FLUSH but removes the length bytes of the resulting empty stored 1219 block. When decompressing, PPP checks that at the end of input packet, 1220 inflate is waiting for these length bytes. 1221 */ 1222int ZEXPORT inflateSyncPoint(strm) 1223z_streamp strm; 1224{ 1225 struct inflate_state FAR *state; 1226 1227 if (strm == Z_NULL || strm->state == Z_NULL) return Z_STREAM_ERROR; 1228 state = (struct inflate_state FAR *)strm->state; 1229 return state->mode == STORED && state->bits == 0; 1230} 1231 1232int ZEXPORT inflateCopy(dest, source) 1233z_streamp dest; 1234z_streamp source; 1235{ 1236 struct inflate_state FAR *state; 1237 struct inflate_state FAR *copy; 1238 unsigned char FAR *window; 1239 1240 /* check input */ 1241 if (dest == Z_NULL || source == Z_NULL || source->state == Z_NULL || 1242 source->zalloc == (alloc_func)0 || source->zfree == (free_func)0) 1243 return Z_STREAM_ERROR; 1244 state = (struct inflate_state FAR *)source->state; 1245 1246 /* allocate space */ 1247 copy = (struct inflate_state FAR *) 1248 ZALLOC(source, 1, sizeof(struct inflate_state)); 1249 if (copy == Z_NULL) return Z_MEM_ERROR; 1250 window = Z_NULL; 1251 if (state->window != Z_NULL) { 1252 window = (unsigned char FAR *) 1253 ZALLOC(source, 1U << state->wbits, sizeof(unsigned char)); 1254 if (window == Z_NULL) { 1255 ZFREE(source, copy); 1256 return Z_MEM_ERROR; 1257 } 1258 } 1259 1260 /* copy state */ 1261 *dest = *source; 1262 *copy = *state; 1263 copy->lencode = copy->codes + (state->lencode - state->codes); 1264 copy->distcode = copy->codes + (state->distcode - state->codes); 1265 copy->next = copy->codes + (state->next - state->codes); 1266 if (window != Z_NULL) 1267 zmemcpy(window, state->window, 1U << state->wbits); 1268 copy->window = window; 1269 dest->state = (voidpf)copy; 1270 return Z_OK; 1271} 1272