1 /* inflate.c -- zlib decompression 2 * Copyright (C) 1995-2012 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 wnext == 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 "hammer2_zlib_zutil.h" 84 #include "hammer2_zlib_inftrees.h" 85 #include "hammer2_zlib_inflate.h" 86 #include "hammer2_zlib_inffast.h" 87 #include "../hammer2.h" 88 #include <sys/malloc.h> //for malloc macros 89 90 MALLOC_DECLARE(C_ZLIB_BUFFER_INFLATE); 91 MALLOC_DEFINE(C_ZLIB_BUFFER_INFLATE, "compzlibbufferinflate", 92 "A private buffer used by zlib library for inflate function."); 93 94 #ifdef MAKEFIXED 95 # ifndef BUILDFIXED 96 # define BUILDFIXED 97 # endif 98 #endif 99 100 /* function prototypes */ 101 int inflateResetKeep(z_streamp strm); 102 int inflateReset(z_streamp strm); 103 int inflateReset2(z_streamp strm, int windowBits); 104 int inflateInit2_(z_streamp strm, int windowBits, const char *version, 105 int stream_size); 106 int inflatePrime(z_streamp strm, int bits, int value); 107 local void fixedtables(struct inflate_state FAR *state); 108 local int updatewindow(z_streamp strm, const unsigned char FAR *end, 109 unsigned copy); 110 #ifdef BUILDFIXED 111 void makefixed(void); 112 #endif 113 114 int 115 inflateResetKeep(z_streamp strm) 116 { 117 struct inflate_state FAR *state; 118 119 if (strm == Z_NULL || strm->state == Z_NULL) return Z_STREAM_ERROR; 120 state = (struct inflate_state FAR *)strm->state; 121 strm->total_in = strm->total_out = state->total = 0; 122 strm->msg = Z_NULL; 123 if (state->wrap) /* to support ill-conceived Java test suite */ 124 strm->adler = state->wrap & 1; 125 state->mode = HEAD; 126 state->last = 0; 127 state->havedict = 0; 128 state->dmax = 32768U; 129 state->hold = 0; 130 state->bits = 0; 131 state->lencode = state->distcode = state->next = state->codes; 132 state->sane = 1; 133 state->back = -1; 134 Tracev((stderr, "inflate: reset\n")); 135 return Z_OK; 136 } 137 138 int 139 inflateReset(z_streamp strm) 140 { 141 struct inflate_state FAR *state; 142 143 if (strm == Z_NULL || strm->state == Z_NULL) return Z_STREAM_ERROR; 144 state = (struct inflate_state FAR *)strm->state; 145 state->wsize = 0; 146 state->whave = 0; 147 state->wnext = 0; 148 return inflateResetKeep(strm); 149 } 150 151 int 152 inflateReset2(z_streamp strm, int windowBits) 153 { 154 int wrap; 155 struct inflate_state FAR *state; 156 157 /* get the state */ 158 if (strm == Z_NULL || strm->state == Z_NULL) return Z_STREAM_ERROR; 159 state = (struct inflate_state FAR *)strm->state; 160 161 /* extract wrap request from windowBits parameter */ 162 if (windowBits < 0) { 163 wrap = 0; 164 windowBits = -windowBits; 165 } 166 else { 167 wrap = (windowBits >> 4) + 1; 168 } 169 170 /* set number of window bits, free window if different */ 171 if (windowBits && (windowBits < 8 || windowBits > 15)) 172 return Z_STREAM_ERROR; 173 if (state->window != Z_NULL && state->wbits != (unsigned)windowBits) { 174 kfree(state->window, C_ZLIB_BUFFER_INFLATE); 175 state->window = Z_NULL; 176 } 177 178 /* update state and reset the rest of it */ 179 state->wrap = wrap; 180 state->wbits = (unsigned)windowBits; 181 return inflateReset(strm); 182 } 183 184 int 185 inflateInit2_(z_streamp strm, int windowBits, const char *version, 186 int stream_size) 187 { 188 int ret; 189 struct inflate_state FAR *state; 190 191 if (version == Z_NULL || version[0] != ZLIB_VERSION[0] || 192 stream_size != (int)(sizeof(z_stream))) 193 return Z_VERSION_ERROR; 194 if (strm == Z_NULL) return Z_STREAM_ERROR; 195 strm->msg = Z_NULL; /* in case we return an error */ 196 state = (struct inflate_state FAR *) kmalloc(sizeof(struct inflate_state), C_ZLIB_BUFFER_INFLATE, M_INTWAIT); 197 if (state == Z_NULL) return Z_MEM_ERROR; 198 Tracev((stderr, "inflate: allocated\n")); 199 strm->state = (struct internal_state FAR *)state; 200 state->window = Z_NULL; 201 ret = inflateReset2(strm, windowBits); 202 if (ret != Z_OK) { 203 kfree(state, C_ZLIB_BUFFER_INFLATE); 204 strm->state = Z_NULL; 205 } 206 return ret; 207 } 208 209 int 210 inflateInit_(z_streamp strm, const char *version, int stream_size) 211 { 212 return inflateInit2_(strm, DEF_WBITS, version, stream_size); 213 } 214 215 int 216 inflatePrime(z_streamp strm, int bits, int value) 217 { 218 struct inflate_state FAR *state; 219 220 if (strm == Z_NULL || strm->state == Z_NULL) return Z_STREAM_ERROR; 221 state = (struct inflate_state FAR *)strm->state; 222 if (bits < 0) { 223 state->hold = 0; 224 state->bits = 0; 225 return Z_OK; 226 } 227 if (bits > 16 || state->bits + bits > 32) return Z_STREAM_ERROR; 228 value &= (1L << bits) - 1; 229 state->hold += value << state->bits; 230 state->bits += bits; 231 return Z_OK; 232 } 233 234 /* 235 Return state with length and distance decoding tables and index sizes set to 236 fixed code decoding. Normally this returns fixed tables from inffixed.h. 237 If BUILDFIXED is defined, then instead this routine builds the tables the 238 first time it's called, and returns those tables the first time and 239 thereafter. This reduces the size of the code by about 2K bytes, in 240 exchange for a little execution time. However, BUILDFIXED should not be 241 used for threaded applications, since the rewriting of the tables and virgin 242 may not be thread-safe. 243 */ 244 local 245 void 246 fixedtables(struct inflate_state FAR *state) 247 { 248 #ifdef BUILDFIXED 249 static int virgin = 1; 250 static code *lenfix, *distfix; 251 static code fixed[544]; 252 253 /* build fixed huffman tables if first call (may not be thread safe) */ 254 if (virgin) { 255 unsigned sym, bits; 256 static code *next; 257 258 /* literal/length table */ 259 sym = 0; 260 while (sym < 144) state->lens[sym++] = 8; 261 while (sym < 256) state->lens[sym++] = 9; 262 while (sym < 280) state->lens[sym++] = 7; 263 while (sym < 288) state->lens[sym++] = 8; 264 next = fixed; 265 lenfix = next; 266 bits = 9; 267 inflate_table(LENS, state->lens, 288, &(next), &(bits), state->work); 268 269 /* distance table */ 270 sym = 0; 271 while (sym < 32) state->lens[sym++] = 5; 272 distfix = next; 273 bits = 5; 274 inflate_table(DISTS, state->lens, 32, &(next), &(bits), state->work); 275 276 /* do this just once */ 277 virgin = 0; 278 } 279 #else /* !BUILDFIXED */ 280 # include "hammer2_zlib_inffixed.h" 281 #endif /* BUILDFIXED */ 282 state->lencode = lenfix; 283 state->lenbits = 9; 284 state->distcode = distfix; 285 state->distbits = 5; 286 } 287 288 #ifdef MAKEFIXED 289 #include <stdio.h> 290 291 /* 292 Write out the inffixed.h that is #include'd above. Defining MAKEFIXED also 293 defines BUILDFIXED, so the tables are built on the fly. makefixed() writes 294 those tables to stdout, which would be piped to inffixed.h. A small program 295 can simply call makefixed to do this: 296 297 void makefixed(void); 298 299 int main(void) 300 { 301 makefixed(); 302 return 0; 303 } 304 305 Then that can be linked with zlib built with MAKEFIXED defined and run: 306 307 a.out > inffixed.h 308 */ 309 void 310 makefixed() 311 { 312 unsigned low, size; 313 struct inflate_state state; 314 315 fixedtables(&state); 316 puts(" /* inffixed.h -- table for decoding fixed codes"); 317 puts(" * Generated automatically by makefixed()."); 318 puts(" */"); 319 puts(""); 320 puts(" /* WARNING: this file should *not* be used by applications."); 321 puts(" It is part of the implementation of this library and is"); 322 puts(" subject to change. Applications should only use zlib.h."); 323 puts(" */"); 324 puts(""); 325 size = 1U << 9; 326 printf(" static const code lenfix[%u] = {", size); 327 low = 0; 328 for (;;) { 329 if ((low % 7) == 0) printf("\n "); 330 printf("{%u,%u,%d}", (low & 127) == 99 ? 64 : state.lencode[low].op, 331 state.lencode[low].bits, state.lencode[low].val); 332 if (++low == size) break; 333 putchar(','); 334 } 335 puts("\n };"); 336 size = 1U << 5; 337 printf("\n static const code distfix[%u] = {", size); 338 low = 0; 339 for (;;) { 340 if ((low % 6) == 0) printf("\n "); 341 printf("{%u,%u,%d}", state.distcode[low].op, state.distcode[low].bits, 342 state.distcode[low].val); 343 if (++low == size) break; 344 putchar(','); 345 } 346 puts("\n };"); 347 } 348 #endif /* MAKEFIXED */ 349 350 /* 351 Update the window with the last wsize (normally 32K) bytes written before 352 returning. If window does not exist yet, create it. This is only called 353 when a window is already in use, or when output has been written during this 354 inflate call, but the end of the deflate stream has not been reached yet. 355 It is also called to create a window for dictionary data when a dictionary 356 is loaded. 357 358 Providing output buffers larger than 32K to inflate() should provide a speed 359 advantage, since only the last 32K of output is copied to the sliding window 360 upon return from inflate(), and since all distances after the first 32K of 361 output will fall in the output data, making match copies simpler and faster. 362 The advantage may be dependent on the size of the processor's data caches. 363 */ 364 local 365 int 366 updatewindow(z_streamp strm, const Bytef *end, unsigned copy) 367 { 368 struct inflate_state FAR *state; 369 unsigned dist; 370 371 state = (struct inflate_state FAR *)strm->state; 372 373 /* if window not in use yet, initialize */ 374 if (state->wsize == 0) { 375 state->wsize = 1U << state->wbits; 376 state->wnext = 0; 377 state->whave = 0; 378 } 379 380 /* copy state->wsize or less output bytes into the circular window */ 381 if (copy >= state->wsize) { 382 zmemcpy(state->window, end - state->wsize, state->wsize); 383 state->wnext = 0; 384 state->whave = state->wsize; 385 } 386 else { 387 dist = state->wsize - state->wnext; 388 if (dist > copy) dist = copy; 389 zmemcpy(state->window + state->wnext, end - copy, dist); 390 copy -= dist; 391 if (copy) { 392 zmemcpy(state->window, end - copy, copy); 393 state->wnext = copy; 394 state->whave = state->wsize; 395 } 396 else { 397 state->wnext += dist; 398 if (state->wnext == state->wsize) state->wnext = 0; 399 if (state->whave < state->wsize) state->whave += dist; 400 } 401 } 402 return 0; 403 } 404 405 /* Macros for inflate(): */ 406 #define UPDATE(check, buf, len) adler32(check, buf, len) 407 408 /* Load registers with state in inflate() for speed */ 409 #define LOAD() \ 410 do { \ 411 put = strm->next_out; \ 412 left = strm->avail_out; \ 413 next = strm->next_in; \ 414 have = strm->avail_in; \ 415 hold = state->hold; \ 416 bits = state->bits; \ 417 } while (0) 418 419 /* Restore state from registers in inflate() */ 420 #define RESTORE() \ 421 do { \ 422 strm->next_out = put; \ 423 strm->avail_out = left; \ 424 strm->next_in = next; \ 425 strm->avail_in = have; \ 426 state->hold = hold; \ 427 state->bits = bits; \ 428 } while (0) 429 430 /* Clear the input bit accumulator */ 431 #define INITBITS() \ 432 do { \ 433 hold = 0; \ 434 bits = 0; \ 435 } while (0) 436 437 /* Get a byte of input into the bit accumulator, or return from inflate() 438 if there is no input available. */ 439 #define PULLBYTE() \ 440 do { \ 441 if (have == 0) goto inf_leave; \ 442 have--; \ 443 hold += (unsigned long)(*next++) << bits; \ 444 bits += 8; \ 445 } while (0) 446 447 /* Assure that there are at least n bits in the bit accumulator. If there is 448 not enough available input to do that, then return from inflate(). */ 449 #define NEEDBITS(n) \ 450 do { \ 451 while (bits < (unsigned)(n)) \ 452 PULLBYTE(); \ 453 } while (0) 454 455 /* Return the low n bits of the bit accumulator (n < 16) */ 456 #define BITS(n) \ 457 ((unsigned)hold & ((1U << (n)) - 1)) 458 459 /* Remove n bits from the bit accumulator */ 460 #define DROPBITS(n) \ 461 do { \ 462 hold >>= (n); \ 463 bits -= (unsigned)(n); \ 464 } while (0) 465 466 /* Remove zero to seven bits as needed to go to a byte boundary */ 467 #define BYTEBITS() \ 468 do { \ 469 hold >>= bits & 7; \ 470 bits -= bits & 7; \ 471 } while (0) 472 473 /* 474 inflate() uses a state machine to process as much input data and generate as 475 much output data as possible before returning. The state machine is 476 structured roughly as follows: 477 478 for (;;) switch (state) { 479 ... 480 case STATEn: 481 if (not enough input data or output space to make progress) 482 return; 483 ... make progress ... 484 state = STATEm; 485 break; 486 ... 487 } 488 489 so when inflate() is called again, the same case is attempted again, and 490 if the appropriate resources are provided, the machine proceeds to the 491 next state. The NEEDBITS() macro is usually the way the state evaluates 492 whether it can proceed or should return. NEEDBITS() does the return if 493 the requested bits are not available. The typical use of the BITS macros 494 is: 495 496 NEEDBITS(n); 497 ... do something with BITS(n) ... 498 DROPBITS(n); 499 500 where NEEDBITS(n) either returns from inflate() if there isn't enough 501 input left to load n bits into the accumulator, or it continues. BITS(n) 502 gives the low n bits in the accumulator. When done, DROPBITS(n) drops 503 the low n bits off the accumulator. INITBITS() clears the accumulator 504 and sets the number of available bits to zero. BYTEBITS() discards just 505 enough bits to put the accumulator on a byte boundary. After BYTEBITS() 506 and a NEEDBITS(8), then BITS(8) would return the next byte in the stream. 507 508 NEEDBITS(n) uses PULLBYTE() to get an available byte of input, or to return 509 if there is no input available. The decoding of variable length codes uses 510 PULLBYTE() directly in order to pull just enough bytes to decode the next 511 code, and no more. 512 513 Some states loop until they get enough input, making sure that enough 514 state information is maintained to continue the loop where it left off 515 if NEEDBITS() returns in the loop. For example, want, need, and keep 516 would all have to actually be part of the saved state in case NEEDBITS() 517 returns: 518 519 case STATEw: 520 while (want < need) { 521 NEEDBITS(n); 522 keep[want++] = BITS(n); 523 DROPBITS(n); 524 } 525 state = STATEx; 526 case STATEx: 527 528 As shown above, if the next state is also the next case, then the break 529 is omitted. 530 531 A state may also return if there is not enough output space available to 532 complete that state. Those states are copying stored data, writing a 533 literal byte, and copying a matching string. 534 535 When returning, a "goto inf_leave" is used to update the total counters, 536 update the check value, and determine whether any progress has been made 537 during that inflate() call in order to return the proper return code. 538 Progress is defined as a change in either strm->avail_in or strm->avail_out. 539 When there is a window, goto inf_leave will update the window with the last 540 output written. If a goto inf_leave occurs in the middle of decompression 541 and there is no window currently, goto inf_leave will create one and copy 542 output to the window for the next call of inflate(). 543 544 In this implementation, the flush parameter of inflate() only affects the 545 return code (per zlib.h). inflate() always writes as much as possible to 546 strm->next_out, given the space available and the provided input--the effect 547 documented in zlib.h of Z_SYNC_FLUSH. Furthermore, inflate() always defers 548 the allocation of and copying into a sliding window until necessary, which 549 provides the effect documented in zlib.h for Z_FINISH when the entire input 550 stream available. So the only thing the flush parameter actually does is: 551 when flush is set to Z_FINISH, inflate() cannot return Z_OK. Instead it 552 will return Z_BUF_ERROR if it has not reached the end of the stream. 553 */ 554 555 int 556 inflate(z_streamp strm, int flush) 557 { 558 struct inflate_state FAR *state; 559 z_const unsigned char FAR *next; /* next input */ 560 unsigned char FAR *put; /* next output */ 561 unsigned have, left; /* available input and output */ 562 unsigned long hold; /* bit buffer */ 563 unsigned bits; /* bits in bit buffer */ 564 unsigned in, out; /* save starting available input and output */ 565 unsigned copy; /* number of stored or match bytes to copy */ 566 unsigned char FAR *from; /* where to copy match bytes from */ 567 code here; /* current decoding table entry */ 568 code last; /* parent table entry */ 569 unsigned len; /* length to copy for repeats, bits to drop */ 570 int ret; /* return code */ 571 572 static const unsigned short order[19] = /* permutation of code lengths */ 573 {16, 17, 18, 0, 8, 7, 9, 6, 10, 5, 11, 4, 12, 3, 13, 2, 14, 1, 15}; 574 575 if (strm == Z_NULL || strm->state == Z_NULL || strm->next_out == Z_NULL || 576 (strm->next_in == Z_NULL && strm->avail_in != 0)) 577 return Z_STREAM_ERROR; 578 579 state = (struct inflate_state FAR *)strm->state; 580 if (state->mode == TYPE) state->mode = TYPEDO; /* skip check */ 581 LOAD(); 582 in = have; 583 out = left; 584 ret = Z_OK; 585 for (;;) 586 switch (state->mode) { 587 case HEAD: 588 if (state->wrap == 0) { 589 state->mode = TYPEDO; 590 break; 591 } 592 NEEDBITS(16); 593 if (((BITS(8) << 8) + (hold >> 8)) % 31) { 594 strm->msg = (char *)"incorrect header check"; 595 state->mode = BAD; 596 break; 597 } 598 if (BITS(4) != Z_DEFLATED) { 599 strm->msg = (char *)"unknown compression method"; 600 state->mode = BAD; 601 break; 602 } 603 DROPBITS(4); 604 len = BITS(4) + 8; 605 if (state->wbits == 0) 606 state->wbits = len; 607 else if (len > state->wbits) { 608 strm->msg = (char *)"invalid window size"; 609 state->mode = BAD; 610 break; 611 } 612 state->dmax = 1U << len; 613 Tracev((stderr, "inflate: zlib header ok\n")); 614 strm->adler = state->check = adler32(0L, Z_NULL, 0); 615 state->mode = hold & 0x200 ? DICTID : TYPE; 616 INITBITS(); 617 break; 618 case DICTID: 619 NEEDBITS(32); 620 strm->adler = state->check = ZSWAP32(hold); 621 INITBITS(); 622 state->mode = DICT; 623 case DICT: 624 if (state->havedict == 0) { 625 RESTORE(); 626 return Z_NEED_DICT; 627 } 628 strm->adler = state->check = adler32(0L, Z_NULL, 0); 629 state->mode = TYPE; 630 case TYPE: 631 if (flush == Z_BLOCK || flush == Z_TREES) goto inf_leave; 632 case TYPEDO: 633 if (state->last) { 634 BYTEBITS(); 635 state->mode = CHECK; 636 break; 637 } 638 NEEDBITS(3); 639 state->last = BITS(1); 640 DROPBITS(1); 641 switch (BITS(2)) { 642 case 0: /* stored block */ 643 Tracev((stderr, "inflate: stored block%s\n", 644 state->last ? " (last)" : "")); 645 state->mode = STORED; 646 break; 647 case 1: /* fixed block */ 648 fixedtables(state); 649 Tracev((stderr, "inflate: fixed codes block%s\n", 650 state->last ? " (last)" : "")); 651 state->mode = LEN_; /* decode codes */ 652 if (flush == Z_TREES) { 653 DROPBITS(2); 654 goto inf_leave; 655 } 656 break; 657 case 2: /* dynamic block */ 658 Tracev((stderr, "inflate: dynamic codes block%s\n", 659 state->last ? " (last)" : "")); 660 state->mode = TABLE; 661 break; 662 case 3: 663 strm->msg = (char *)"invalid block type"; 664 state->mode = BAD; 665 } 666 DROPBITS(2); 667 break; 668 case STORED: 669 BYTEBITS(); /* go to byte boundary */ 670 NEEDBITS(32); 671 if ((hold & 0xffff) != ((hold >> 16) ^ 0xffff)) { 672 strm->msg = (char *)"invalid stored block lengths"; 673 state->mode = BAD; 674 break; 675 } 676 state->length = (unsigned)hold & 0xffff; 677 Tracev((stderr, "inflate: stored length %u\n", 678 state->length)); 679 INITBITS(); 680 state->mode = COPY_; 681 if (flush == Z_TREES) goto inf_leave; 682 case COPY_: 683 state->mode = COPY; 684 case COPY: 685 copy = state->length; 686 if (copy) { 687 if (copy > have) copy = have; 688 if (copy > left) copy = left; 689 if (copy == 0) goto inf_leave; 690 zmemcpy(put, next, copy); 691 have -= copy; 692 next += copy; 693 left -= copy; 694 put += copy; 695 state->length -= copy; 696 break; 697 } 698 Tracev((stderr, "inflate: stored end\n")); 699 state->mode = TYPE; 700 break; 701 case TABLE: 702 NEEDBITS(14); 703 state->nlen = BITS(5) + 257; 704 DROPBITS(5); 705 state->ndist = BITS(5) + 1; 706 DROPBITS(5); 707 state->ncode = BITS(4) + 4; 708 DROPBITS(4); 709 #ifndef PKZIP_BUG_WORKAROUND 710 if (state->nlen > 286 || state->ndist > 30) { 711 strm->msg = (char *)"too many length or distance symbols"; 712 state->mode = BAD; 713 break; 714 } 715 #endif 716 Tracev((stderr, "inflate: table sizes ok\n")); 717 state->have = 0; 718 state->mode = LENLENS; 719 case LENLENS: 720 while (state->have < state->ncode) { 721 NEEDBITS(3); 722 state->lens[order[state->have++]] = (unsigned short)BITS(3); 723 DROPBITS(3); 724 } 725 while (state->have < 19) 726 state->lens[order[state->have++]] = 0; 727 state->next = state->codes; 728 state->lencode = (const code FAR *)(state->next); 729 state->lenbits = 7; 730 ret = inflate_table(CODES, state->lens, 19, &(state->next), 731 &(state->lenbits), state->work); 732 if (ret) { 733 strm->msg = (char *)"invalid code lengths set"; 734 state->mode = BAD; 735 break; 736 } 737 Tracev((stderr, "inflate: code lengths ok\n")); 738 state->have = 0; 739 state->mode = CODELENS; 740 case CODELENS: 741 while (state->have < state->nlen + state->ndist) { 742 for (;;) { 743 here = state->lencode[BITS(state->lenbits)]; 744 if ((unsigned)(here.bits) <= bits) break; 745 PULLBYTE(); 746 } 747 if (here.val < 16) { 748 DROPBITS(here.bits); 749 state->lens[state->have++] = here.val; 750 } 751 else { 752 if (here.val == 16) { 753 NEEDBITS(here.bits + 2); 754 DROPBITS(here.bits); 755 if (state->have == 0) { 756 strm->msg = (char *)"invalid bit length repeat"; 757 state->mode = BAD; 758 break; 759 } 760 len = state->lens[state->have - 1]; 761 copy = 3 + BITS(2); 762 DROPBITS(2); 763 } 764 else if (here.val == 17) { 765 NEEDBITS(here.bits + 3); 766 DROPBITS(here.bits); 767 len = 0; 768 copy = 3 + BITS(3); 769 DROPBITS(3); 770 } 771 else { 772 NEEDBITS(here.bits + 7); 773 DROPBITS(here.bits); 774 len = 0; 775 copy = 11 + BITS(7); 776 DROPBITS(7); 777 } 778 if (state->have + copy > state->nlen + state->ndist) { 779 strm->msg = (char *)"invalid bit length repeat"; 780 state->mode = BAD; 781 break; 782 } 783 while (copy--) 784 state->lens[state->have++] = (unsigned short)len; 785 } 786 } 787 788 /* handle error breaks in while */ 789 if (state->mode == BAD) break; 790 791 /* check for end-of-block code (better have one) */ 792 if (state->lens[256] == 0) { 793 strm->msg = (char *)"invalid code -- missing end-of-block"; 794 state->mode = BAD; 795 break; 796 } 797 798 /* build code tables -- note: do not change the lenbits or distbits 799 values here (9 and 6) without reading the comments in inftrees.h 800 concerning the ENOUGH constants, which depend on those values */ 801 state->next = state->codes; 802 state->lencode = (const code FAR *)(state->next); 803 state->lenbits = 9; 804 ret = inflate_table(LENS, state->lens, state->nlen, &(state->next), 805 &(state->lenbits), state->work); 806 if (ret) { 807 strm->msg = (char *)"invalid literal/lengths set"; 808 state->mode = BAD; 809 break; 810 } 811 state->distcode = (const code FAR *)(state->next); 812 state->distbits = 6; 813 ret = inflate_table(DISTS, state->lens + state->nlen, state->ndist, 814 &(state->next), &(state->distbits), state->work); 815 if (ret) { 816 strm->msg = (char *)"invalid distances set"; 817 state->mode = BAD; 818 break; 819 } 820 Tracev((stderr, "inflate: codes ok\n")); 821 state->mode = LEN_; 822 if (flush == Z_TREES) goto inf_leave; 823 case LEN_: 824 state->mode = LEN; 825 case LEN: 826 if (have >= 6 && left >= 258) { 827 RESTORE(); 828 inflate_fast(strm, out); 829 LOAD(); 830 if (state->mode == TYPE) 831 state->back = -1; 832 break; 833 } 834 state->back = 0; 835 for (;;) { 836 here = state->lencode[BITS(state->lenbits)]; 837 if ((unsigned)(here.bits) <= bits) break; 838 PULLBYTE(); 839 } 840 if (here.op && (here.op & 0xf0) == 0) { 841 last = here; 842 for (;;) { 843 here = state->lencode[last.val + 844 (BITS(last.bits + last.op) >> last.bits)]; 845 if ((unsigned)(last.bits + here.bits) <= bits) break; 846 PULLBYTE(); 847 } 848 DROPBITS(last.bits); 849 state->back += last.bits; 850 } 851 DROPBITS(here.bits); 852 state->back += here.bits; 853 state->length = (unsigned)here.val; 854 if ((int)(here.op) == 0) { 855 Tracevv((stderr, here.val >= 0x20 && here.val < 0x7f ? 856 "inflate: literal '%c'\n" : 857 "inflate: literal 0x%02x\n", here.val)); 858 state->mode = LIT; 859 break; 860 } 861 if (here.op & 32) { 862 Tracevv((stderr, "inflate: end of block\n")); 863 state->back = -1; 864 state->mode = TYPE; 865 break; 866 } 867 if (here.op & 64) { 868 strm->msg = (char *)"invalid literal/length code"; 869 state->mode = BAD; 870 break; 871 } 872 state->extra = (unsigned)(here.op) & 15; 873 state->mode = LENEXT; 874 case LENEXT: 875 if (state->extra) { 876 NEEDBITS(state->extra); 877 state->length += BITS(state->extra); 878 DROPBITS(state->extra); 879 state->back += state->extra; 880 } 881 Tracevv((stderr, "inflate: length %u\n", state->length)); 882 state->was = state->length; 883 state->mode = DIST; 884 case DIST: 885 for (;;) { 886 here = state->distcode[BITS(state->distbits)]; 887 if ((unsigned)(here.bits) <= bits) break; 888 PULLBYTE(); 889 } 890 if ((here.op & 0xf0) == 0) { 891 last = here; 892 for (;;) { 893 here = state->distcode[last.val + 894 (BITS(last.bits + last.op) >> last.bits)]; 895 if ((unsigned)(last.bits + here.bits) <= bits) break; 896 PULLBYTE(); 897 } 898 DROPBITS(last.bits); 899 state->back += last.bits; 900 } 901 DROPBITS(here.bits); 902 state->back += here.bits; 903 if (here.op & 64) { 904 strm->msg = (char *)"invalid distance code"; 905 state->mode = BAD; 906 break; 907 } 908 state->offset = (unsigned)here.val; 909 state->extra = (unsigned)(here.op) & 15; 910 state->mode = DISTEXT; 911 case DISTEXT: 912 if (state->extra) { 913 NEEDBITS(state->extra); 914 state->offset += BITS(state->extra); 915 DROPBITS(state->extra); 916 state->back += state->extra; 917 } 918 #ifdef INFLATE_STRICT 919 if (state->offset > state->dmax) { 920 strm->msg = (char *)"invalid distance too far back"; 921 state->mode = BAD; 922 break; 923 } 924 #endif 925 Tracevv((stderr, "inflate: distance %u\n", state->offset)); 926 state->mode = MATCH; 927 case MATCH: 928 if (left == 0) goto inf_leave; 929 copy = out - left; 930 if (state->offset > copy) { /* copy from window */ 931 copy = state->offset - copy; 932 if (copy > state->whave) { 933 if (state->sane) { 934 strm->msg = (char *)"invalid distance too far back"; 935 state->mode = BAD; 936 break; 937 } 938 #ifdef INFLATE_ALLOW_INVALID_DISTANCE_TOOFAR_ARRR 939 Trace((stderr, "inflate.c too far\n")); 940 copy -= state->whave; 941 if (copy > state->length) copy = state->length; 942 if (copy > left) copy = left; 943 left -= copy; 944 state->length -= copy; 945 do { 946 *put++ = 0; 947 } while (--copy); 948 if (state->length == 0) state->mode = LEN; 949 break; 950 #endif 951 } 952 if (copy > state->wnext) { 953 copy -= state->wnext; 954 from = state->window + (state->wsize - copy); 955 } 956 else 957 from = state->window + (state->wnext - copy); 958 if (copy > state->length) copy = state->length; 959 } 960 else { /* copy from output */ 961 from = put - state->offset; 962 copy = state->length; 963 } 964 if (copy > left) copy = left; 965 left -= copy; 966 state->length -= copy; 967 do { 968 *put++ = *from++; 969 } while (--copy); 970 if (state->length == 0) state->mode = LEN; 971 break; 972 case LIT: 973 if (left == 0) goto inf_leave; 974 *put++ = (unsigned char)(state->length); 975 left--; 976 state->mode = LEN; 977 break; 978 case CHECK: 979 if (state->wrap) { 980 NEEDBITS(32); 981 out -= left; 982 strm->total_out += out; 983 state->total += out; 984 if (out) 985 strm->adler = state->check = 986 UPDATE(state->check, put - out, out); 987 out = left; 988 if ((ZSWAP32(hold)) != state->check) { 989 strm->msg = (char *)"incorrect data check"; 990 state->mode = BAD; 991 break; 992 } 993 INITBITS(); 994 Tracev((stderr, "inflate: check matches trailer\n")); 995 } 996 state->mode = DONE; 997 case DONE: 998 ret = Z_STREAM_END; 999 goto inf_leave; 1000 case BAD: 1001 ret = Z_DATA_ERROR; 1002 goto inf_leave; 1003 case MEM: 1004 return Z_MEM_ERROR; 1005 case SYNC: 1006 default: 1007 return Z_STREAM_ERROR; 1008 } 1009 1010 /* 1011 Return from inflate(), updating the total counts and the check value. 1012 If there was no progress during the inflate() call, return a buffer 1013 error. Call updatewindow() to create and/or update the window state. 1014 Note: a memory error from inflate() is non-recoverable. 1015 */ 1016 inf_leave: 1017 RESTORE(); 1018 if (state->wsize || (out != strm->avail_out && state->mode < BAD && 1019 (state->mode < CHECK || flush != Z_FINISH))) 1020 if (updatewindow(strm, strm->next_out, out - strm->avail_out)) { 1021 state->mode = MEM; 1022 return Z_MEM_ERROR; 1023 } 1024 in -= strm->avail_in; 1025 out -= strm->avail_out; 1026 strm->total_in += in; 1027 strm->total_out += out; 1028 state->total += out; 1029 if (state->wrap && out) 1030 strm->adler = state->check = 1031 UPDATE(state->check, strm->next_out - out, out); 1032 strm->data_type = state->bits + (state->last ? 64 : 0) + 1033 (state->mode == TYPE ? 128 : 0) + 1034 (state->mode == LEN_ || state->mode == COPY_ ? 256 : 0); 1035 if (((in == 0 && out == 0) || flush == Z_FINISH) && ret == Z_OK) 1036 ret = Z_BUF_ERROR; 1037 return ret; 1038 } 1039 1040 int 1041 inflateEnd(z_streamp strm) 1042 { 1043 struct inflate_state FAR *state; 1044 if (strm == Z_NULL || strm->state == Z_NULL) 1045 return Z_STREAM_ERROR; 1046 state = (struct inflate_state FAR *)strm->state; 1047 if (state->window != Z_NULL) kfree(state->window, C_ZLIB_BUFFER_INFLATE); 1048 kfree(strm->state, C_ZLIB_BUFFER_INFLATE); 1049 strm->state = Z_NULL; 1050 Tracev((stderr, "inflate: end\n")); 1051 return Z_OK; 1052 } 1053