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