1 /* inflate.c -- zlib decompression 2 * Copyright (C) 1995-2003 Mark Adler 3 * For conditions of distribution and use, see copyright notice in zlib.h 4 */ 5 6 /* 7 * Change history: 8 * 9 * 1.2.beta0 24 Nov 2002 10 * - First version -- complete rewrite of inflate to simplify code, avoid 11 * creation of window when not needed, minimize use of window when it is 12 * needed, make inffast.c even faster, implement gzip decoding, and to 13 * improve code readability and style over the previous zlib inflate code 14 * 15 * 1.2.beta1 25 Nov 2002 16 * - Use pointers for available input and output checking in inffast.c 17 * - Remove input and output counters in inffast.c 18 * - Change inffast.c entry and loop from avail_in >= 7 to >= 6 19 * - Remove unnecessary second byte pull from length extra in inffast.c 20 * - Unroll direct copy to three copies per loop in inffast.c 21 * 22 * 1.2.beta2 4 Dec 2002 23 * - Change external routine names to reduce potential conflicts 24 * - Correct filename to inffixed.h for fixed tables in inflate.c 25 * - Make hbuf[] unsigned char to match parameter type in inflate.c 26 * - Change strm->next_out[-state->offset] to *(strm->next_out - state->offset) 27 * to avoid negation problem on Alphas (64 bit) in inflate.c 28 * 29 * 1.2.beta3 22 Dec 2002 30 * - Add comments on state->bits assertion in inffast.c 31 * - Add comments on op field in inftrees.h 32 * - Fix bug in reuse of allocated window after inflateReset() 33 * - Remove bit fields--back to byte structure for speed 34 * - Remove distance extra == 0 check in inflate_fast()--only helps for lengths 35 * - Change post-increments to pre-increments in inflate_fast(), PPC biased? 36 * - Add compile time option, POSTINC, to use post-increments instead (Intel?) 37 * - Make MATCH copy in inflate() much faster for when inflate_fast() not used 38 * - Use local copies of stream next and avail values, as well as local bit 39 * buffer and bit count in inflate()--for speed when inflate_fast() not used 40 * 41 * 1.2.beta4 1 Jan 2003 42 * - Split ptr - 257 statements in inflate_table() to avoid compiler warnings 43 * - Move a comment on output buffer sizes from inffast.c to inflate.c 44 * - Add comments in inffast.c to introduce the inflate_fast() routine 45 * - Rearrange window copies in inflate_fast() for speed and simplification 46 * - Unroll last copy for window match in inflate_fast() 47 * - Use local copies of window variables in inflate_fast() for speed 48 * - Pull out common write == 0 case for speed in inflate_fast() 49 * - Make op and len in inflate_fast() unsigned for consistency 50 * - Add FAR to lcode and dcode declarations in inflate_fast() 51 * - Simplified bad distance check in inflate_fast() 52 * - Added inflateBackInit(), inflateBack(), and inflateBackEnd() in new 53 * source file infback.c to provide a call-back interface to inflate for 54 * programs like gzip and unzip -- uses window as output buffer to avoid 55 * window copying 56 * 57 * 1.2.beta5 1 Jan 2003 58 * - Improved inflateBack() interface to allow the caller to provide initial 59 * input in strm. 60 * - Fixed stored blocks bug in inflateBack() 61 * 62 * 1.2.beta6 4 Jan 2003 63 * - Added comments in inffast.c on effectiveness of POSTINC 64 * - Typecasting all around to reduce compiler warnings 65 * - Changed loops from while (1) or do {} while (1) to for (;;), again to 66 * make compilers happy 67 * - Changed type of window in inflateBackInit() to unsigned char * 68 * 69 * 1.2.beta7 27 Jan 2003 70 * - Changed many types to unsigned or unsigned short to avoid warnings 71 * - Added inflateCopy() function 72 * 73 * 1.2.0 9 Mar 2003 74 * - Changed inflateBack() interface to provide separate opaque descriptors 75 * for the in() and out() functions 76 * - Changed inflateBack() argument and in_func typedef to swap the length 77 * and buffer address return values for the input function 78 * - Check next_in and next_out for Z_NULL on entry to inflate() 79 * 80 * The history for versions after 1.2.0 are in ChangeLog in zlib distribution. 81 */ 82 83 #include "zutil.h" 84 #include "inftrees.h" 85 #include "inflate.h" 86 #include "inffast.h" 87 88 #ifdef MAKEFIXED 89 # ifndef BUILDFIXED 90 # define BUILDFIXED 91 # endif 92 #endif 93 94 /* function prototypes */ 95 local void fixedtables OF((struct inflate_state FAR *state)); 96 local int updatewindow OF((z_streamp strm, unsigned out)); 97 #ifdef BUILDFIXED 98 void makefixed OF((void)); 99 #endif 100 local unsigned syncsearch OF((unsigned FAR *have, unsigned char FAR *buf, 101 unsigned len)); 102 103 int ZEXPORT inflateReset(strm) 104 z_streamp strm; 105 90 { 106 90 struct inflate_state FAR *state; 107 108 90 if (strm == Z_NULL || strm->state == Z_NULL) return Z_STREAM_ERROR; 109 90 state = (struct inflate_state FAR *)strm->state; 110 90 strm->total_in = strm->total_out = state->total = 0; 111 90 strm->msg = Z_NULL; 112 90 strm->adler = 1; /* to support ill-conceived Java test suite */ 113 90 state->mode = HEAD; 114 90 state->last = 0; 115 90 state->havedict = 0; 116 90 state->wsize = 0; 117 90 state->whave = 0; 118 90 state->hold = 0; 119 90 state->bits = 0; 120 90 state->lencode = state->distcode = state->next = state->codes; 121 Tracev((stderr, "inflate: reset\n")); 122 90 return Z_OK; 123 } 124 125 int ZEXPORT inflateInit2_(strm, windowBits, version, stream_size) 126 z_streamp strm; 127 int windowBits; 128 const char *version; 129 int stream_size; 130 88 { 131 88 struct inflate_state FAR *state; 132 133 88 if (version == Z_NULL || version[0] != ZLIB_VERSION[0] || 134 stream_size != (int)(sizeof(z_stream))) 135 ###### return Z_VERSION_ERROR; 136 88 if (strm == Z_NULL) return Z_STREAM_ERROR; 137 88 strm->msg = Z_NULL; /* in case we return an error */ 138 88 if (strm->zalloc == (alloc_func)0) { 139 88 strm->zalloc = zcalloc; 140 88 strm->opaque = (voidpf)0; 141 } 142 88 if (strm->zfree == (free_func)0) strm->zfree = zcfree; 143 88 state = (struct inflate_state FAR *) 144 ZALLOC(strm, 1, sizeof(struct inflate_state)); 145 88 if (state == Z_NULL) return Z_MEM_ERROR; 146 Tracev((stderr, "inflate: allocated\n")); 147 88 strm->state = (voidpf)state; 148 88 if (windowBits < 0) { 149 70 state->wrap = 0; 150 70 windowBits = -windowBits; 151 } 152 else { 153 18 state->wrap = (windowBits >> 4) + 1; 154 #ifdef GUNZIP 155 18 if (windowBits < 48) windowBits &= 15; 156 #endif 157 } 158 88 if (windowBits < 8 || windowBits > 15) { 159 ###### ZFREE(strm, state); 160 ###### strm->state = Z_NULL; 161 ###### return Z_STREAM_ERROR; 162 } 163 88 state->wbits = (unsigned)windowBits; 164 88 state->window = Z_NULL; 165 88 return inflateReset(strm); 166 } 167 168 int ZEXPORT inflateInit_(strm, version, stream_size) 169 z_streamp strm; 170 const char *version; 171 int 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 */ 186 local void fixedtables(state) 187 struct inflate_state FAR *state; 188 47 { 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 47 state->lencode = lenfix; 224 47 state->lenbits = 9; 225 47 state->distcode = distfix; 226 47 state->distbits = 5; 227 } 228 229 #ifdef MAKEFIXED 230 #include 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 */ 250 void 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 */ 304 local int updatewindow(strm, out) 305 z_streamp strm; 306 unsigned out; 307 339 { 308 339 struct inflate_state FAR *state; 309 339 unsigned copy, dist; 310 311 339 state = (struct inflate_state FAR *)strm->state; 312 313 /* if it hasn't been done already, allocate space for the window */ 314 339 if (state->window == Z_NULL) { 315 25 state->window = (unsigned char FAR *) 316 ZALLOC(strm, 1U << state->wbits, 317 sizeof(unsigned char)); 318 25 if (state->window == Z_NULL) return 1; 319 } 320 321 /* if window not in use yet, initialize */ 322 339 if (state->wsize == 0) { 323 25 state->wsize = 1U << state->wbits; 324 25 state->write = 0; 325 25 state->whave = 0; 326 } 327 328 /* copy state->wsize or less output bytes into the circular window */ 329 339 copy = out - strm->avail_out; 330 339 if (copy >= state->wsize) { 331 1 zmemcpy(state->window, strm->next_out - state->wsize, state->wsize); 332 1 state->write = 0; 333 1 state->whave = state->wsize; 334 } 335 else { 336 338 dist = state->wsize - state->write; 337 338 if (dist > copy) dist = copy; 338 338 zmemcpy(state->window + state->write, strm->next_out - copy, dist); 339 338 copy -= dist; 340 338 if (copy) { 341 ###### zmemcpy(state->window, strm->next_out - copy, copy); 342 ###### state->write = copy; 343 ###### state->whave = state->wsize; 344 } 345 else { 346 338 state->write += dist; 347 338 if (state->write == state->wsize) state->write = 0; 348 338 if (state->whave < state->wsize) state->whave += dist; 349 } 350 } 351 339 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 535 int ZEXPORT inflate(strm, flush) 536 z_streamp strm; 537 int flush; 538 454 { 539 454 struct inflate_state FAR *state; 540 454 unsigned char FAR *next; /* next input */ 541 454 unsigned char FAR *put; /* next output */ 542 454 unsigned have, left; /* available input and output */ 543 454 unsigned long hold; /* bit buffer */ 544 454 unsigned bits; /* bits in bit buffer */ 545 454 unsigned in, out; /* save starting available input and output */ 546 454 unsigned copy; /* number of stored or match bytes to copy */ 547 454 unsigned char FAR *from; /* where to copy match bytes from */ 548 454 code this; /* current decoding table entry */ 549 454 code last; /* parent table entry */ 550 454 unsigned len; /* length to copy for repeats, bits to drop */ 551 454 int ret; /* return code */ 552 #ifdef GUNZIP 553 454 unsigned char hbuf[4]; /* buffer for gzip header crc calculation */ 554 #endif 555 static const unsigned short order[19] = /* permutation of code lengths */ 556 454 {16, 17, 18, 0, 8, 7, 9, 6, 10, 5, 11, 4, 12, 3, 13, 2, 14, 1, 15}; 557 558 454 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 454 state = (struct inflate_state FAR *)strm->state; 563 454 if (state->mode == TYPE) state->mode = TYPEDO; /* skip check */ 564 454 LOAD(); 565 454 in = have; 566 454 out = left; 567 454 ret = Z_OK; 568 4067 for (;;) 569 3614 switch (state->mode) { 570 case HEAD: 571 74 if (state->wrap == 0) { 572 50 state->mode = TYPEDO; 573 50 break; 574 } 575 58 NEEDBITS(16); 576 #ifdef GUNZIP 577 16 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 16 state->flags = 0; /* expect zlib header */ 585 16 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 16 if (BITS(4) != Z_DEFLATED) { 595 ###### strm->msg = (char *)"unknown compression method"; 596 ###### state->mode = BAD; 597 ###### break; 598 } 599 16 DROPBITS(4); 600 16 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 16 strm->adler = state->check = adler32(0L, Z_NULL, 0); 607 16 state->mode = hold & 0x200 ? DICTID : TYPE; 608 16 INITBITS(); 609 16 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 5 NEEDBITS(32); 703 1 strm->adler = state->check = REVERSE(hold); 704 1 INITBITS(); 705 1 state->mode = DICT; 706 case DICT: 707 2 if (state->havedict == 0) { 708 1 RESTORE(); 709 1 return Z_NEED_DICT; 710 } 711 1 strm->adler = state->check = adler32(0L, Z_NULL, 0); 712 1 state->mode = TYPE; 713 case TYPE: 714 89 if (flush == Z_BLOCK) goto inf_leave; 715 case TYPEDO: 716 147 if (state->last) { 717 67 BYTEBITS(); 718 67 state->mode = CHECK; 719 67 break; 720 } 721 151 NEEDBITS(3); 722 74 state->last = BITS(1); 723 74 DROPBITS(1); 724 74 switch (BITS(2)) { 725 case 0: /* stored block */ 726 Tracev((stderr, "inflate: stored block%s\n", 727 state->last ? " (last)" : "")); 728 7 state->mode = STORED; 729 7 break; 730 case 1: /* fixed block */ 731 47 fixedtables(state); 732 Tracev((stderr, "inflate: fixed codes block%s\n", 733 state->last ? " (last)" : "")); 734 47 state->mode = LEN; /* decode codes */ 735 47 break; 736 case 2: /* dynamic block */ 737 Tracev((stderr, "inflate: dynamic codes block%s\n", 738 state->last ? " (last)" : "")); 739 20 state->mode = TABLE; 740 20 break; 741 case 3: 742 ###### strm->msg = (char *)"invalid block type"; 743 ###### state->mode = BAD; 744 } 745 74 DROPBITS(2); 746 74 break; 747 case STORED: 748 7 BYTEBITS(); /* go to byte boundary */ 749 35 NEEDBITS(32); 750 7 if ((hold & 0xffff) != ((hold >> 16) ^ 0xffff)) { 751 ###### strm->msg = (char *)"invalid stored block lengths"; 752 ###### state->mode = BAD; 753 ###### break; 754 } 755 7 state->length = (unsigned)hold & 0xffff; 756 Tracev((stderr, "inflate: stored length %u\n", 757 state->length)); 758 7 INITBITS(); 759 7 state->mode = COPY; 760 case COPY: 761 19 copy = state->length; 762 19 if (copy) { 763 12 if (copy > have) copy = have; 764 12 if (copy > left) copy = left; 765 12 if (copy == 0) goto inf_leave; 766 9 zmemcpy(put, next, copy); 767 9 have -= copy; 768 9 next += copy; 769 9 left -= copy; 770 9 put += copy; 771 9 state->length -= copy; 772 9 break; 773 } 774 Tracev((stderr, "inflate: stored end\n")); 775 7 state->mode = TYPE; 776 7 break; 777 case TABLE: 778 63 NEEDBITS(14); 779 20 state->nlen = BITS(5) + 257; 780 20 DROPBITS(5); 781 20 state->ndist = BITS(5) + 1; 782 20 DROPBITS(5); 783 20 state->ncode = BITS(4) + 4; 784 20 DROPBITS(4); 785 #ifndef PKZIP_BUG_WORKAROUND 786 20 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 20 state->have = 0; 794 20 state->mode = LENLENS; 795 case LENLENS: 796 354 while (state->have < state->ncode) { 797 449 NEEDBITS(3); 798 322 state->lens[order[state->have++]] = (unsigned short)BITS(3); 799 322 DROPBITS(3); 800 } 801 78 while (state->have < 19) 802 58 state->lens[order[state->have++]] = 0; 803 20 state->next = state->codes; 804 20 state->lencode = (code const FAR *)(state->next); 805 20 state->lenbits = 7; 806 20 ret = inflate_table(CODES, state->lens, 19, &(state->next), 807 &(state->lenbits), state->work); 808 20 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 20 state->have = 0; 815 20 state->mode = CODELENS; 816 case CODELENS: 817 1660 while (state->have < state->nlen + state->ndist) { 818 2906 for (;;) { 819 2273 this = state->lencode[BITS(state->lenbits)]; 820 2273 if ((unsigned)(this.bits) <= bits) break; 821 655 PULLBYTE(); 822 } 823 1618 if (this.val < 16) { 824 1425 NEEDBITS(this.bits); 825 1425 DROPBITS(this.bits); 826 1425 state->lens[state->have++] = this.val; 827 } 828 else { 829 193 if (this.val == 16) { 830 36 NEEDBITS(this.bits + 2); 831 29 DROPBITS(this.bits); 832 29 if (state->have == 0) { 833 ###### strm->msg = (char *)"invalid bit length repeat"; 834 ###### state->mode = BAD; 835 ###### break; 836 } 837 29 len = state->lens[state->have - 1]; 838 29 copy = 3 + BITS(2); 839 29 DROPBITS(2); 840 } 841 164 else if (this.val == 17) { 842 107 NEEDBITS(this.bits + 3); 843 77 DROPBITS(this.bits); 844 77 len = 0; 845 77 copy = 3 + BITS(3); 846 77 DROPBITS(3); 847 } 848 else { 849 146 NEEDBITS(this.bits + 7); 850 75 DROPBITS(this.bits); 851 75 len = 0; 852 75 copy = 11 + BITS(7); 853 75 DROPBITS(7); 854 } 855 181 if (state->have + copy > state->nlen + state->ndist) { 856 ###### strm->msg = (char *)"invalid bit length repeat"; 857 ###### state->mode = BAD; 858 ###### break; 859 } 860 4718 while (copy--) 861 4537 state->lens[state->have++] = (unsigned short)len; 862 } 863 } 864 865 /* handle error breaks in while */ 866 20 if (state->mode == BAD) break; 867 868 /* build code tables */ 869 20 state->next = state->codes; 870 20 state->lencode = (code const FAR *)(state->next); 871 20 state->lenbits = 9; 872 20 ret = inflate_table(LENS, state->lens, state->nlen, &(state->next), 873 &(state->lenbits), state->work); 874 20 if (ret) { 875 ###### strm->msg = (char *)"invalid literal/lengths set"; 876 ###### state->mode = BAD; 877 ###### break; 878 } 879 20 state->distcode = (code const FAR *)(state->next); 880 20 state->distbits = 6; 881 20 ret = inflate_table(DISTS, state->lens + state->nlen, state->ndist, 882 &(state->next), &(state->distbits), state->work); 883 20 if (ret) { 884 ###### strm->msg = (char *)"invalid distances set"; 885 ###### state->mode = BAD; 886 ###### break; 887 } 888 Tracev((stderr, "inflate: codes ok\n")); 889 20 state->mode = LEN; 890 case LEN: 891 2014 if (have >= 6 && left >= 258) { 892 185 RESTORE(); 893 185 inflate_fast(strm, out); 894 185 LOAD(); 895 185 break; 896 } 897 3783 for (;;) { 898 2806 this = state->lencode[BITS(state->lenbits)]; 899 2806 if ((unsigned)(this.bits) <= bits) break; 900 1071 PULLBYTE(); 901 } 902 1735 if (this.op && (this.op & 0xf0) == 0) { 903 21 last = this; 904 39 for (;;) { 905 30 this = state->lencode[last.val + 906 (BITS(last.bits + last.op) >> last.bits)]; 907 30 if ((unsigned)(last.bits + this.bits) <= bits) break; 908 9 PULLBYTE(); 909 } 910 21 DROPBITS(last.bits); 911 } 912 1735 DROPBITS(this.bits); 913 1735 state->length = (unsigned)this.val; 914 1735 if ((int)(this.op) == 0) { 915 Tracevv((stderr, this.val >= 0x20 && this.val < 0x7f ? 916 "inflate: literal '%c'\n" : 917 "inflate: literal 0x%02x\n", this.val)); 918 887 state->mode = LIT; 919 887 break; 920 } 921 848 if (this.op & 32) { 922 Tracevv((stderr, "inflate: end of block\n")); 923 28 state->mode = TYPE; 924 28 break; 925 } 926 820 if (this.op & 64) { 927 ###### strm->msg = (char *)"invalid literal/length code"; 928 ###### state->mode = BAD; 929 ###### break; 930 } 931 820 state->extra = (unsigned)(this.op) & 15; 932 820 state->mode = LENEXT; 933 case LENEXT: 934 820 if (state->extra) { 935 259 NEEDBITS(state->extra); 936 205 state->length += BITS(state->extra); 937 205 DROPBITS(state->extra); 938 } 939 Tracevv((stderr, "inflate: length %u\n", state->length)); 940 820 state->mode = DIST; 941 case DIST: 942 1628 for (;;) { 943 1224 this = state->distcode[BITS(state->distbits)]; 944 1224 if ((unsigned)(this.bits) <= bits) break; 945 404 PULLBYTE(); 946 } 947 820 if ((this.op & 0xf0) == 0) { 948 15 last = this; 949 15 for (;;) { 950 15 this = state->distcode[last.val + 951 (BITS(last.bits + last.op) >> last.bits)]; 952 15 if ((unsigned)(last.bits + this.bits) <= bits) break; 953 ###### PULLBYTE(); 954 } 955 15 DROPBITS(last.bits); 956 } 957 820 DROPBITS(this.bits); 958 820 if (this.op & 64) { 959 ###### strm->msg = (char *)"invalid distance code"; 960 ###### state->mode = BAD; 961 ###### break; 962 } 963 820 state->offset = (unsigned)this.val; 964 820 state->extra = (unsigned)(this.op) & 15; 965 820 state->mode = DISTEXT; 966 case DISTEXT: 967 924 if (state->extra) { 968 1573 NEEDBITS(state->extra); 969 782 state->offset += BITS(state->extra); 970 782 DROPBITS(state->extra); 971 } 972 820 if (state->offset > state->whave + out - left) { 973 ###### strm->msg = (char *)"invalid distance too far back"; 974 ###### state->mode = BAD; 975 ###### break; 976 } 977 Tracevv((stderr, "inflate: distance %u\n", state->offset)); 978 820 state->mode = MATCH; 979 case MATCH: 980 1023 if (left == 0) goto inf_leave; 981 948 copy = out - left; 982 948 if (state->offset > copy) { /* copy from window */ 983 227 copy = state->offset - copy; 984 227 if (copy > state->write) { 985 1 copy -= state->write; 986 1 from = state->window + (state->wsize - copy); 987 } 988 else 989 226 from = state->window + (state->write - copy); 990 227 if (copy > state->length) copy = state->length; 991 } 992 else { /* copy from output */ 993 721 from = put - state->offset; 994 721 copy = state->length; 995 } 996 948 if (copy > left) copy = left; 997 948 left -= copy; 998 948 state->length -= copy; 999 49660 do { 1000 49660 *put++ = *from++; 1001 49660 } while (--copy); 1002 948 if (state->length == 0) state->mode = LEN; 1003 820 break; 1004 case LIT: 1005 909 if (left == 0) goto inf_leave; 1006 887 *put++ = (unsigned char)(state->length); 1007 887 left--; 1008 887 state->mode = LEN; 1009 887 break; 1010 case CHECK: 1011 91 if (state->wrap) { 1012 114 NEEDBITS(32); 1013 18 out -= left; 1014 18 strm->total_out += out; 1015 18 state->total += out; 1016 18 if (out) 1017 15 strm->adler = state->check = 1018 UPDATE(state->check, put - out, out); 1019 18 out = left; 1020 18 if (( 1021 #ifdef GUNZIP 1022 state->flags ? hold : 1023 #endif 1024 REVERSE(hold)) != state->check) { 1025 2 strm->msg = (char *)"incorrect data check"; 1026 2 state->mode = BAD; 1027 2 break; 1028 } 1029 16 INITBITS(); 1030 Tracev((stderr, "inflate: check matches trailer\n")); 1031 } 1032 #ifdef GUNZIP 1033 65 state->mode = LENGTH; 1034 case LENGTH: 1035 65 if (state->wrap && state->flags) { 1036 ###### NEEDBITS(32); 1037 ###### if (hold != (state->total & 0xffffffffUL)) { 1038 ###### strm->msg = (char *)"incorrect length check"; 1039 ###### state->mode = BAD; 1040 ###### break; 1041 } 1042 ###### INITBITS(); 1043 Tracev((stderr, "inflate: length matches trailer\n")); 1044 } 1045 #endif 1046 65 state->mode = DONE; 1047 case DONE: 1048 65 ret = Z_STREAM_END; 1049 65 goto inf_leave; 1050 case BAD: 1051 2 ret = Z_DATA_ERROR; 1052 2 goto inf_leave; 1053 case MEM: 1054 ###### return Z_MEM_ERROR; 1055 case SYNC: 1056 default: 1057 ###### return Z_STREAM_ERROR; 1058 } 1059 1060 /* 1061 Return from inflate(), updating the total counts and the check value. 1062 If there was no progress during the inflate() call, return a buffer 1063 error. Call updatewindow() to create and/or update the window state. 1064 Note: a memory error from inflate() is non-recoverable. 1065 */ 1066 inf_leave: 1067 453 RESTORE(); 1068 453 if (state->wsize || (state->mode < CHECK && out != strm->avail_out)) 1069 338 if (updatewindow(strm, out)) { 1070 ###### state->mode = MEM; 1071 ###### return Z_MEM_ERROR; 1072 } 1073 453 in -= strm->avail_in; 1074 453 out -= strm->avail_out; 1075 453 strm->total_in += in; 1076 453 strm->total_out += out; 1077 453 state->total += out; 1078 453 if (state->wrap && out) 1079 96 strm->adler = state->check = 1080 UPDATE(state->check, strm->next_out - out, out); 1081 453 strm->data_type = state->bits + (state->last ? 64 : 0) + 1082 (state->mode == TYPE ? 128 : 0); 1083 453 if (((in == 0 && out == 0) || flush == Z_FINISH) && ret == Z_OK) 1084 143 ret = Z_BUF_ERROR; 1085 453 return ret; 1086 } 1087 1088 int ZEXPORT inflateEnd(strm) 1089 z_streamp strm; 1090 88 { 1091 88 struct inflate_state FAR *state; 1092 88 if (strm == Z_NULL || strm->state == Z_NULL || strm->zfree == (free_func)0) 1093 ###### return Z_STREAM_ERROR; 1094 88 state = (struct inflate_state FAR *)strm->state; 1095 88 if (state->window != Z_NULL) ZFREE(strm, state->window); 1096 88 ZFREE(strm, strm->state); 1097 88 strm->state = Z_NULL; 1098 Tracev((stderr, "inflate: end\n")); 1099 88 return Z_OK; 1100 } 1101 1102 int ZEXPORT inflateSetDictionary(strm, dictionary, dictLength) 1103 z_streamp strm; 1104 const Bytef *dictionary; 1105 uInt dictLength; 1106 1 { 1107 1 struct inflate_state FAR *state; 1108 1 unsigned long id; 1109 1110 /* check state */ 1111 1 if (strm == Z_NULL || strm->state == Z_NULL) return Z_STREAM_ERROR; 1112 1 state = (struct inflate_state FAR *)strm->state; 1113 1 if (state->mode != DICT) return Z_STREAM_ERROR; 1114 1115 /* check for correct dictionary id */ 1116 1 id = adler32(0L, Z_NULL, 0); 1117 1 id = adler32(id, dictionary, dictLength); 1118 1 if (id != state->check) return Z_DATA_ERROR; 1119 1120 /* copy dictionary to window */ 1121 1 if (updatewindow(strm, strm->avail_out)) { 1122 ###### state->mode = MEM; 1123 ###### return Z_MEM_ERROR; 1124 } 1125 1 if (dictLength > state->wsize) { 1126 ###### zmemcpy(state->window, dictionary + dictLength - state->wsize, 1127 state->wsize); 1128 ###### state->whave = state->wsize; 1129 } 1130 else { 1131 1 zmemcpy(state->window + state->wsize - dictLength, dictionary, 1132 dictLength); 1133 1 state->whave = dictLength; 1134 } 1135 1 state->havedict = 1; 1136 Tracev((stderr, "inflate: dictionary set\n")); 1137 1 return Z_OK; 1138 } 1139 1140 /* 1141 Search buf[0..len-1] for the pattern: 0, 0, 0xff, 0xff. Return when found 1142 or when out of input. When called, *have is the number of pattern bytes 1143 found in order so far, in 0..3. On return *have is updated to the new 1144 state. If on return *have equals four, then the pattern was found and the 1145 return value is how many bytes were read including the last byte of the 1146 pattern. If *have is less than four, then the pattern has not been found 1147 yet and the return value is len. In the latter case, syncsearch() can be 1148 called again with more data and the *have state. *have is initialized to 1149 zero for the first call. 1150 */ 1151 local unsigned syncsearch(have, buf, len) 1152 unsigned FAR *have; 1153 unsigned char FAR *buf; 1154 unsigned len; 1155 171 { 1156 171 unsigned got; 1157 171 unsigned next; 1158 1159 171 got = *have; 1160 171 next = 0; 1161 509 while (next < len && got < 4) { 1162 338 if ((int)(buf[next]) == (got < 2 ? 0 : 0xff)) 1163 8 got++; 1164 330 else if (buf[next]) 1165 330 got = 0; 1166 else 1167 ###### got = 4 - got; 1168 338 next++; 1169 } 1170 171 *have = got; 1171 171 return next; 1172 } 1173 1174 int ZEXPORT inflateSync(strm) 1175 z_streamp strm; 1176 169 { 1177 169 unsigned len; /* number of bytes to look at or looked at */ 1178 169 unsigned long in, out; /* temporary to save total_in and total_out */ 1179 169 unsigned char buf[4]; /* to restore bit buffer to byte string */ 1180 169 struct inflate_state FAR *state; 1181 1182 /* check parameters */ 1183 169 if (strm == Z_NULL || strm->state == Z_NULL) return Z_STREAM_ERROR; 1184 169 state = (struct inflate_state FAR *)strm->state; 1185 169 if (strm->avail_in == 0 && state->bits < 8) return Z_BUF_ERROR; 1186 1187 /* if first time, start search in bit buffer */ 1188 169 if (state->mode != SYNC) { 1189 2 state->mode = SYNC; 1190 2 state->hold <<= state->bits & 7; 1191 2 state->bits -= state->bits & 7; 1192 2 len = 0; 1193 4 while (state->bits >= 8) { 1194 2 buf[len++] = (unsigned char)(state->hold); 1195 2 state->hold >>= 8; 1196 2 state->bits -= 8; 1197 } 1198 2 state->have = 0; 1199 2 syncsearch(&(state->have), buf, len); 1200 } 1201 1202 /* search available input */ 1203 169 len = syncsearch(&(state->have), strm->next_in, strm->avail_in); 1204 169 strm->avail_in -= len; 1205 169 strm->next_in += len; 1206 169 strm->total_in += len; 1207 1208 /* return no joy or set up to restart inflate() on a new block */ 1209 169 if (state->have != 4) return Z_DATA_ERROR; 1210 2 in = strm->total_in; out = strm->total_out; 1211 2 inflateReset(strm); 1212 2 strm->total_in = in; strm->total_out = out; 1213 2 state->mode = TYPE; 1214 2 return Z_OK; 1215 } 1216 1217 /* 1218 Returns true if inflate is currently at the end of a block generated by 1219 Z_SYNC_FLUSH or Z_FULL_FLUSH. This function is used by one PPP 1220 implementation to provide an additional safety check. PPP uses 1221 Z_SYNC_FLUSH but removes the length bytes of the resulting empty stored 1222 block. When decompressing, PPP checks that at the end of input packet, 1223 inflate is waiting for these length bytes. 1224 */ 1225 int ZEXPORT inflateSyncPoint(strm) 1226 z_streamp strm; 1227 ###### { 1228 ###### struct inflate_state FAR *state; 1229 1230 ###### if (strm == Z_NULL || strm->state == Z_NULL) return Z_STREAM_ERROR; 1231 ###### state = (struct inflate_state FAR *)strm->state; 1232 ###### return state->mode == STORED && state->bits == 0; 1233 } 1234 1235 int ZEXPORT inflateCopy(dest, source) 1236 z_streamp dest; 1237 z_streamp source; 1238 ###### { 1239 ###### struct inflate_state FAR *state; 1240 ###### struct inflate_state FAR *copy; 1241 ###### unsigned char FAR *window; 1242 1243 /* check input */ 1244 ###### if (dest == Z_NULL || source == Z_NULL || source->state == Z_NULL || 1245 source->zalloc == (alloc_func)0 || source->zfree == (free_func)0) 1246 ###### return Z_STREAM_ERROR; 1247 ###### state = (struct inflate_state FAR *)source->state; 1248 1249 /* allocate space */ 1250 ###### copy = (struct inflate_state FAR *) 1251 ZALLOC(source, 1, sizeof(struct inflate_state)); 1252 ###### if (copy == Z_NULL) return Z_MEM_ERROR; 1253 ###### window = Z_NULL; 1254 ###### if (state->window != Z_NULL) { 1255 ###### window = (unsigned char FAR *) 1256 ZALLOC(source, 1U << state->wbits, sizeof(unsigned char)); 1257 ###### if (window == Z_NULL) { 1258 ###### ZFREE(source, copy); 1259 ###### return Z_MEM_ERROR; 1260 } 1261 } 1262 1263 /* copy state */ 1264 ###### *dest = *source; 1265 ###### *copy = *state; 1266 ###### copy->lencode = copy->codes + (state->lencode - state->codes); 1267 ###### copy->distcode = copy->codes + (state->distcode - state->codes); 1268 ###### copy->next = copy->codes + (state->next - state->codes); 1269 ###### if (window != Z_NULL) 1270 ###### zmemcpy(window, state->window, 1U << state->wbits); 1271 ###### copy->window = window; 1272 ###### dest->state = (voidpf)copy; 1273 ###### return Z_OK; 1274 }