win32port/zlib/inflate.c

   1 /* inflate.c -- zlib decompression\r
   2  * Copyright (C) 1995-2010 Mark Adler\r
   3  * For conditions of distribution and use, see copyright notice in zlib.h\r
   4  */\r
   5 \r
   6 /*\r
   7  * Change history:\r
   8  *\r
   9  * 1.2.beta0    24 Nov 2002\r
  10  * - First version -- complete rewrite of inflate to simplify code, avoid\r
  11  *   creation of window when not needed, minimize use of window when it is\r
  12  *   needed, make inffast.c even faster, implement gzip decoding, and to\r
  13  *   improve code readability and style over the previous zlib inflate code\r
  14  *\r
  15  * 1.2.beta1    25 Nov 2002\r
  16  * - Use pointers for available input and output checking in inffast.c\r
  17  * - Remove input and output counters in inffast.c\r
  18  * - Change inffast.c entry and loop from avail_in >= 7 to >= 6\r
  19  * - Remove unnecessary second byte pull from length extra in inffast.c\r
  20  * - Unroll direct copy to three copies per loop in inffast.c\r
  21  *\r
  22  * 1.2.beta2    4 Dec 2002\r
  23  * - Change external routine names to reduce potential conflicts\r
  24  * - Correct filename to inffixed.h for fixed tables in inflate.c\r
  25  * - Make hbuf[] unsigned char to match parameter type in inflate.c\r
  26  * - Change strm->next_out[-state->offset] to *(strm->next_out - state->offset)\r
  27  *   to avoid negation problem on Alphas (64 bit) in inflate.c\r
  28  *\r
  29  * 1.2.beta3    22 Dec 2002\r
  30  * - Add comments on state->bits assertion in inffast.c\r
  31  * - Add comments on op field in inftrees.h\r
  32  * - Fix bug in reuse of allocated window after inflateReset()\r
  33  * - Remove bit fields--back to byte structure for speed\r
  34  * - Remove distance extra == 0 check in inflate_fast()--only helps for lengths\r
  35  * - Change post-increments to pre-increments in inflate_fast(), PPC biased?\r
  36  * - Add compile time option, POSTINC, to use post-increments instead (Intel?)\r
  37  * - Make MATCH copy in inflate() much faster for when inflate_fast() not used\r
  38  * - Use local copies of stream next and avail values, as well as local bit\r
  39  *   buffer and bit count in inflate()--for speed when inflate_fast() not used\r
  40  *\r
  41  * 1.2.beta4    1 Jan 2003\r
  42  * - Split ptr - 257 statements in inflate_table() to avoid compiler warnings\r
  43  * - Move a comment on output buffer sizes from inffast.c to inflate.c\r
  44  * - Add comments in inffast.c to introduce the inflate_fast() routine\r
  45  * - Rearrange window copies in inflate_fast() for speed and simplification\r
  46  * - Unroll last copy for window match in inflate_fast()\r
  47  * - Use local copies of window variables in inflate_fast() for speed\r
  48  * - Pull out common wnext == 0 case for speed in inflate_fast()\r
  49  * - Make op and len in inflate_fast() unsigned for consistency\r
  50  * - Add FAR to lcode and dcode declarations in inflate_fast()\r
  51  * - Simplified bad distance check in inflate_fast()\r
  52  * - Added inflateBackInit(), inflateBack(), and inflateBackEnd() in new\r
  53  *   source file infback.c to provide a call-back interface to inflate for\r
  54  *   programs like gzip and unzip -- uses window as output buffer to avoid\r
  55  *   window copying\r
  56  *\r
  57  * 1.2.beta5    1 Jan 2003\r
  58  * - Improved inflateBack() interface to allow the caller to provide initial\r
  59  *   input in strm.\r
  60  * - Fixed stored blocks bug in inflateBack()\r
  61  *\r
  62  * 1.2.beta6    4 Jan 2003\r
  63  * - Added comments in inffast.c on effectiveness of POSTINC\r
  64  * - Typecasting all around to reduce compiler warnings\r
  65  * - Changed loops from while (1) or do {} while (1) to for (;;), again to\r
  66  *   make compilers happy\r
  67  * - Changed type of window in inflateBackInit() to unsigned char *\r
  68  *\r
  69  * 1.2.beta7    27 Jan 2003\r
  70  * - Changed many types to unsigned or unsigned short to avoid warnings\r
  71  * - Added inflateCopy() function\r
  72  *\r
  73  * 1.2.0        9 Mar 2003\r
  74  * - Changed inflateBack() interface to provide separate opaque descriptors\r
  75  *   for the in() and out() functions\r
  76  * - Changed inflateBack() argument and in_func typedef to swap the length\r
  77  *   and buffer address return values for the input function\r
  78  * - Check next_in and next_out for Z_NULL on entry to inflate()\r
  79  *\r
  80  * The history for versions after 1.2.0 are in ChangeLog in zlib distribution.\r
  81  */\r
  82 \r
  83 #include "zutil.h"\r
  84 #include "inftrees.h"\r
  85 #include "inflate.h"\r
  86 #include "inffast.h"\r
  87 \r
  88 #ifdef MAKEFIXED\r
  89 #  ifndef BUILDFIXED\r
  90 #    define BUILDFIXED\r
  91 #  endif\r
  92 #endif\r
  93 \r
  94 /* function prototypes */\r
  95 local void fixedtables OF((struct inflate_state FAR *state));\r
  96 local int updatewindow OF((z_streamp strm, unsigned out));\r
  97 #ifdef BUILDFIXED\r
  98    void makefixed OF((void));\r
  99 #endif\r
 100 local unsigned syncsearch OF((unsigned FAR *have, unsigned char FAR *buf,\r
 101                               unsigned len));\r
 102 \r
 103 int ZEXPORT inflateReset(strm)\r
 104 z_streamp strm;\r
 105 {\r
 106     struct inflate_state FAR *state;\r
 107 \r
 108     if (strm == Z_NULL || strm->state == Z_NULL) return Z_STREAM_ERROR;\r
 109     state = (struct inflate_state FAR *)strm->state;\r
 110     strm->total_in = strm->total_out = state->total = 0;\r
 111     strm->msg = Z_NULL;\r
 112     strm->adler = 1;        /* to support ill-conceived Java test suite */\r
 113     state->mode = HEAD;\r
 114     state->last = 0;\r
 115     state->havedict = 0;\r
 116     state->dmax = 32768U;\r
 117     state->head = Z_NULL;\r
 118     state->wsize = 0;\r
 119     state->whave = 0;\r
 120     state->wnext = 0;\r
 121     state->hold = 0;\r
 122     state->bits = 0;\r
 123     state->lencode = state->distcode = state->next = state->codes;\r
 124     state->sane = 1;\r
 125     state->back = -1;\r
 126     Tracev((stderr, "inflate: reset\n"));\r
 127     return Z_OK;\r
 128 }\r
 129 \r
 130 int ZEXPORT inflateReset2(strm, windowBits)\r
 131 z_streamp strm;\r
 132 int windowBits;\r
 133 {\r
 134     int wrap;\r
 135     struct inflate_state FAR *state;\r
 136 \r
 137     /* get the state */\r
 138     if (strm == Z_NULL || strm->state == Z_NULL) return Z_STREAM_ERROR;\r
 139     state = (struct inflate_state FAR *)strm->state;\r
 140 \r
 141     /* extract wrap request from windowBits parameter */\r
 142     if (windowBits < 0) {\r
 143         wrap = 0;\r
 144         windowBits = -windowBits;\r
 145     }\r
 146     else {\r
 147         wrap = (windowBits >> 4) + 1;\r
 148 #ifdef GUNZIP\r
 149         if (windowBits < 48)\r
 150             windowBits &= 15;\r
 151 #endif\r
 152     }\r
 153 \r
 154     /* set number of window bits, free window if different */\r
 155     if (windowBits && (windowBits < 8 || windowBits > 15))\r
 156         return Z_STREAM_ERROR;\r
 157     if (state->window != Z_NULL && state->wbits != (unsigned)windowBits) {\r
 158         ZFREE(strm, state->window);\r
 159         state->window = Z_NULL;\r
 160     }\r
 161 \r
 162     /* update state and reset the rest of it */\r
 163     state->wrap = wrap;\r
 164     state->wbits = (unsigned)windowBits;\r
 165     return inflateReset(strm);\r
 166 }\r
 167 \r
 168 int ZEXPORT inflateInit2_(strm, windowBits, version, stream_size)\r
 169 z_streamp strm;\r
 170 int windowBits;\r
 171 const char *version;\r
 172 int stream_size;\r
 173 {\r
 174     int ret;\r
 175     struct inflate_state FAR *state;\r
 176 \r
 177     if (version == Z_NULL || version[0] != ZLIB_VERSION[0] ||\r
 178         stream_size != (int)(sizeof(z_stream)))\r
 179         return Z_VERSION_ERROR;\r
 180     if (strm == Z_NULL) return Z_STREAM_ERROR;\r
 181     strm->msg = Z_NULL;                 /* in case we return an error */\r
 182     if (strm->zalloc == (alloc_func)0) {\r
 183         strm->zalloc = zcalloc;\r
 184         strm->opaque = (voidpf)0;\r
 185     }\r
 186     if (strm->zfree == (free_func)0) strm->zfree = zcfree;\r
 187     state = (struct inflate_state FAR *)\r
 188             ZALLOC(strm, 1, sizeof(struct inflate_state));\r
 189     if (state == Z_NULL) return Z_MEM_ERROR;\r
 190     Tracev((stderr, "inflate: allocated\n"));\r
 191     strm->state = (struct internal_state FAR *)state;\r
 192     state->window = Z_NULL;\r
 193     ret = inflateReset2(strm, windowBits);\r
 194     if (ret != Z_OK) {\r
 195         ZFREE(strm, state);\r
 196         strm->state = Z_NULL;\r
 197     }\r
 198     return ret;\r
 199 }\r
 200 \r
 201 int ZEXPORT inflateInit_(strm, version, stream_size)\r
 202 z_streamp strm;\r
 203 const char *version;\r
 204 int stream_size;\r
 205 {\r
 206     return inflateInit2_(strm, DEF_WBITS, version, stream_size);\r
 207 }\r
 208 \r
 209 int ZEXPORT inflatePrime(strm, bits, value)\r
 210 z_streamp strm;\r
 211 int bits;\r
 212 int value;\r
 213 {\r
 214     struct inflate_state FAR *state;\r
 215 \r
 216     if (strm == Z_NULL || strm->state == Z_NULL) return Z_STREAM_ERROR;\r
 217     state = (struct inflate_state FAR *)strm->state;\r
 218     if (bits < 0) {\r
 219         state->hold = 0;\r
 220         state->bits = 0;\r
 221         return Z_OK;\r
 222     }\r
 223     if (bits > 16 || state->bits + bits > 32) return Z_STREAM_ERROR;\r
 224     value &= (1L << bits) - 1;\r
 225     state->hold += value << state->bits;\r
 226     state->bits += bits;\r
 227     return Z_OK;\r
 228 }\r
 229 \r
 230 /*\r
 231    Return state with length and distance decoding tables and index sizes set to\r
 232    fixed code decoding.  Normally this returns fixed tables from inffixed.h.\r
 233    If BUILDFIXED is defined, then instead this routine builds the tables the\r
 234    first time it's called, and returns those tables the first time and\r
 235    thereafter.  This reduces the size of the code by about 2K bytes, in\r
 236    exchange for a little execution time.  However, BUILDFIXED should not be\r
 237    used for threaded applications, since the rewriting of the tables and virgin\r
 238    may not be thread-safe.\r
 239  */\r
 240 local void fixedtables(state)\r
 241 struct inflate_state FAR *state;\r
 242 {\r
 243 #ifdef BUILDFIXED\r
 244     static int virgin = 1;\r
 245     static code *lenfix, *distfix;\r
 246     static code fixed[544];\r
 247 \r
 248     /* build fixed huffman tables if first call (may not be thread safe) */\r
 249     if (virgin) {\r
 250         unsigned sym, bits;\r
 251         static code *next;\r
 252 \r
 253         /* literal/length table */\r
 254         sym = 0;\r
 255         while (sym < 144) state->lens[sym++] = 8;\r
 256         while (sym < 256) state->lens[sym++] = 9;\r
 257         while (sym < 280) state->lens[sym++] = 7;\r
 258         while (sym < 288) state->lens[sym++] = 8;\r
 259         next = fixed;\r
 260         lenfix = next;\r
 261         bits = 9;\r
 262         inflate_table(LENS, state->lens, 288, &(next), &(bits), state->work);\r
 263 \r
 264         /* distance table */\r
 265         sym = 0;\r
 266         while (sym < 32) state->lens[sym++] = 5;\r
 267         distfix = next;\r
 268         bits = 5;\r
 269         inflate_table(DISTS, state->lens, 32, &(next), &(bits), state->work);\r
 270 \r
 271         /* do this just once */\r
 272         virgin = 0;\r
 273     }\r
 274 #else /* !BUILDFIXED */\r
 275 #   include "inffixed.h"\r
 276 #endif /* BUILDFIXED */\r
 277     state->lencode = lenfix;\r
 278     state->lenbits = 9;\r
 279     state->distcode = distfix;\r
 280     state->distbits = 5;\r
 281 }\r
 282 \r
 283 #ifdef MAKEFIXED\r
 284 #include <stdio.h>\r
 285 \r
 286 /*\r
 287    Write out the inffixed.h that is #include'd above.  Defining MAKEFIXED also\r
 288    defines BUILDFIXED, so the tables are built on the fly.  makefixed() writes\r
 289    those tables to stdout, which would be piped to inffixed.h.  A small program\r
 290    can simply call makefixed to do this:\r
 291 \r
 292     void makefixed(void);\r
 293 \r
 294     int main(void)\r
 295     {\r
 296         makefixed();\r
 297         return 0;\r
 298     }\r
 299 \r
 300    Then that can be linked with zlib built with MAKEFIXED defined and run:\r
 301 \r
 302     a.out > inffixed.h\r
 303  */\r
 304 void makefixed()\r
 305 {\r
 306     unsigned low, size;\r
 307     struct inflate_state state;\r
 308 \r
 309     fixedtables(&state);\r
 310     puts("    /* inffixed.h -- table for decoding fixed codes");\r
 311     puts("     * Generated automatically by makefixed().");\r
 312     puts("     */");\r
 313     puts("");\r
 314     puts("    /* WARNING: this file should *not* be used by applications.");\r
 315     puts("       It is part of the implementation of this library and is");\r
 316     puts("       subject to change. Applications should only use zlib.h.");\r
 317     puts("     */");\r
 318     puts("");\r
 319     size = 1U << 9;\r
 320     printf("    static const code lenfix[%u] = {", size);\r
 321     low = 0;\r
 322     for (;;) {\r
 323         if ((low % 7) == 0) printf("\n        ");\r
 324         printf("{%u,%u,%d}", state.lencode[low].op, state.lencode[low].bits,\r
 325                state.lencode[low].val);\r
 326         if (++low == size) break;\r
 327         putchar(',');\r
 328     }\r
 329     puts("\n    };");\r
 330     size = 1U << 5;\r
 331     printf("\n    static const code distfix[%u] = {", size);\r
 332     low = 0;\r
 333     for (;;) {\r
 334         if ((low % 6) == 0) printf("\n        ");\r
 335         printf("{%u,%u,%d}", state.distcode[low].op, state.distcode[low].bits,\r
 336                state.distcode[low].val);\r
 337         if (++low == size) break;\r
 338         putchar(',');\r
 339     }\r
 340     puts("\n    };");\r
 341 }\r
 342 #endif /* MAKEFIXED */\r
 343 \r
 344 /*\r
 345    Update the window with the last wsize (normally 32K) bytes written before\r
 346    returning.  If window does not exist yet, create it.  This is only called\r
 347    when a window is already in use, or when output has been written during this\r
 348    inflate call, but the end of the deflate stream has not been reached yet.\r
 349    It is also called to create a window for dictionary data when a dictionary\r
 350    is loaded.\r
 351 \r
 352    Providing output buffers larger than 32K to inflate() should provide a speed\r
 353    advantage, since only the last 32K of output is copied to the sliding window\r
 354    upon return from inflate(), and since all distances after the first 32K of\r
 355    output will fall in the output data, making match copies simpler and faster.\r
 356    The advantage may be dependent on the size of the processor's data caches.\r
 357  */\r
 358 local int updatewindow(strm, out)\r
 359 z_streamp strm;\r
 360 unsigned out;\r
 361 {\r
 362     struct inflate_state FAR *state;\r
 363     unsigned copy, dist;\r
 364 \r
 365     state = (struct inflate_state FAR *)strm->state;\r
 366 \r
 367     /* if it hasn't been done already, allocate space for the window */\r
 368     if (state->window == Z_NULL) {\r
 369         state->window = (unsigned char FAR *)\r
 370                         ZALLOC(strm, 1U << state->wbits,\r
 371                                sizeof(unsigned char));\r
 372         if (state->window == Z_NULL) return 1;\r
 373     }\r
 374 \r
 375     /* if window not in use yet, initialize */\r
 376     if (state->wsize == 0) {\r
 377         state->wsize = 1U << state->wbits;\r
 378         state->wnext = 0;\r
 379         state->whave = 0;\r
 380     }\r
 381 \r
 382     /* copy state->wsize or less output bytes into the circular window */\r
 383     copy = out - strm->avail_out;\r
 384     if (copy >= state->wsize) {\r
 385         zmemcpy(state->window, strm->next_out - state->wsize, state->wsize);\r
 386         state->wnext = 0;\r
 387         state->whave = state->wsize;\r
 388     }\r
 389     else {\r
 390         dist = state->wsize - state->wnext;\r
 391         if (dist > copy) dist = copy;\r
 392         zmemcpy(state->window + state->wnext, strm->next_out - copy, dist);\r
 393         copy -= dist;\r
 394         if (copy) {\r
 395             zmemcpy(state->window, strm->next_out - copy, copy);\r
 396             state->wnext = copy;\r
 397             state->whave = state->wsize;\r
 398         }\r
 399         else {\r
 400             state->wnext += dist;\r
 401             if (state->wnext == state->wsize) state->wnext = 0;\r
 402             if (state->whave < state->wsize) state->whave += dist;\r
 403         }\r
 404     }\r
 405     return 0;\r
 406 }\r
 407 \r
 408 /* Macros for inflate(): */\r
 409 \r
 410 /* check function to use adler32() for zlib or crc32() for gzip */\r
 411 #ifdef GUNZIP\r
 412 #  define UPDATE(check, buf, len) \\r
 413     (state->flags ? crc32(check, buf, len) : adler32(check, buf, len))\r
 414 #else\r
 415 #  define UPDATE(check, buf, len) adler32(check, buf, len)\r
 416 #endif\r
 417 \r
 418 /* check macros for header crc */\r
 419 #ifdef GUNZIP\r
 420 #  define CRC2(check, word) \\r
 421     do { \\r
 422         hbuf[0] = (unsigned char)(word); \\r
 423         hbuf[1] = (unsigned char)((word) >> 8); \\r
 424         check = crc32(check, hbuf, 2); \\r
 425     } while (0)\r
 426 \r
 427 #  define CRC4(check, word) \\r
 428     do { \\r
 429         hbuf[0] = (unsigned char)(word); \\r
 430         hbuf[1] = (unsigned char)((word) >> 8); \\r
 431         hbuf[2] = (unsigned char)((word) >> 16); \\r
 432         hbuf[3] = (unsigned char)((word) >> 24); \\r
 433         check = crc32(check, hbuf, 4); \\r
 434     } while (0)\r
 435 #endif\r
 436 \r
 437 /* Load registers with state in inflate() for speed */\r
 438 #define LOAD() \\r
 439     do { \\r
 440         put = strm->next_out; \\r
 441         left = strm->avail_out; \\r
 442         next = strm->next_in; \\r
 443         have = strm->avail_in; \\r
 444         hold = state->hold; \\r
 445         bits = state->bits; \\r
 446     } while (0)\r
 447 \r
 448 /* Restore state from registers in inflate() */\r
 449 #define RESTORE() \\r
 450     do { \\r
 451         strm->next_out = put; \\r
 452         strm->avail_out = left; \\r
 453         strm->next_in = next; \\r
 454         strm->avail_in = have; \\r
 455         state->hold = hold; \\r
 456         state->bits = bits; \\r
 457     } while (0)\r
 458 \r
 459 /* Clear the input bit accumulator */\r
 460 #define INITBITS() \\r
 461     do { \\r
 462         hold = 0; \\r
 463         bits = 0; \\r
 464     } while (0)\r
 465 \r
 466 /* Get a byte of input into the bit accumulator, or return from inflate()\r
 467    if there is no input available. */\r
 468 #define PULLBYTE() \\r
 469     do { \\r
 470         if (have == 0) goto inf_leave; \\r
 471         have--; \\r
 472         hold += (unsigned long)(*next++) << bits; \\r
 473         bits += 8; \\r
 474     } while (0)\r
 475 \r
 476 /* Assure that there are at least n bits in the bit accumulator.  If there is\r
 477    not enough available input to do that, then return from inflate(). */\r
 478 #define NEEDBITS(n) \\r
 479     do { \\r
 480         while (bits < (unsigned)(n)) \\r
 481             PULLBYTE(); \\r
 482     } while (0)\r
 483 \r
 484 /* Return the low n bits of the bit accumulator (n < 16) */\r
 485 #define BITS(n) \\r
 486     ((unsigned)hold & ((1U << (n)) - 1))\r
 487 \r
 488 /* Remove n bits from the bit accumulator */\r
 489 #define DROPBITS(n) \\r
 490     do { \\r
 491         hold >>= (n); \\r
 492         bits -= (unsigned)(n); \\r
 493     } while (0)\r
 494 \r
 495 /* Remove zero to seven bits as needed to go to a byte boundary */\r
 496 #define BYTEBITS() \\r
 497     do { \\r
 498         hold >>= bits & 7; \\r
 499         bits -= bits & 7; \\r
 500     } while (0)\r
 501 \r
 502 /* Reverse the bytes in a 32-bit value */\r
 503 #define REVERSE(q) \\r
 504     ((((q) >> 24) & 0xff) + (((q) >> 8) & 0xff00) + \\r
 505      (((q) & 0xff00) << 8) + (((q) & 0xff) << 24))\r
 506 \r
 507 /*\r
 508    inflate() uses a state machine to process as much input data and generate as\r
 509    much output data as possible before returning.  The state machine is\r
 510    structured roughly as follows:\r
 511 \r
 512     for (;;) switch (state) {\r
 513     ...\r
 514     case STATEn:\r
 515         if (not enough input data or output space to make progress)\r
 516             return;\r
 517         ... make progress ...\r
 518         state = STATEm;\r
 519         break;\r
 520     ...\r
 521     }\r
 522 \r
 523    so when inflate() is called again, the same case is attempted again, and\r
 524    if the appropriate resources are provided, the machine proceeds to the\r
 525    next state.  The NEEDBITS() macro is usually the way the state evaluates\r
 526    whether it can proceed or should return.  NEEDBITS() does the return if\r
 527    the requested bits are not available.  The typical use of the BITS macros\r
 528    is:\r
 529 \r
 530         NEEDBITS(n);\r
 531         ... do something with BITS(n) ...\r
 532         DROPBITS(n);\r
 533 \r
 534    where NEEDBITS(n) either returns from inflate() if there isn't enough\r
 535    input left to load n bits into the accumulator, or it continues.  BITS(n)\r
 536    gives the low n bits in the accumulator.  When done, DROPBITS(n) drops\r
 537    the low n bits off the accumulator.  INITBITS() clears the accumulator\r
 538    and sets the number of available bits to zero.  BYTEBITS() discards just\r
 539    enough bits to put the accumulator on a byte boundary.  After BYTEBITS()\r
 540    and a NEEDBITS(8), then BITS(8) would return the next byte in the stream.\r
 541 \r
 542    NEEDBITS(n) uses PULLBYTE() to get an available byte of input, or to return\r
 543    if there is no input available.  The decoding of variable length codes uses\r
 544    PULLBYTE() directly in order to pull just enough bytes to decode the next\r
 545    code, and no more.\r
 546 \r
 547    Some states loop until they get enough input, making sure that enough\r
 548    state information is maintained to continue the loop where it left off\r
 549    if NEEDBITS() returns in the loop.  For example, want, need, and keep\r
 550    would all have to actually be part of the saved state in case NEEDBITS()\r
 551    returns:\r
 552 \r
 553     case STATEw:\r
 554         while (want < need) {\r
 555             NEEDBITS(n);\r
 556             keep[want++] = BITS(n);\r
 557             DROPBITS(n);\r
 558         }\r
 559         state = STATEx;\r
 560     case STATEx:\r
 561 \r
 562    As shown above, if the next state is also the next case, then the break\r
 563    is omitted.\r
 564 \r
 565    A state may also return if there is not enough output space available to\r
 566    complete that state.  Those states are copying stored data, writing a\r
 567    literal byte, and copying a matching string.\r
 568 \r
 569    When returning, a "goto inf_leave" is used to update the total counters,\r
 570    update the check value, and determine whether any progress has been made\r
 571    during that inflate() call in order to return the proper return code.\r
 572    Progress is defined as a change in either strm->avail_in or strm->avail_out.\r
 573    When there is a window, goto inf_leave will update the window with the last\r
 574    output written.  If a goto inf_leave occurs in the middle of decompression\r
 575    and there is no window currently, goto inf_leave will create one and copy\r
 576    output to the window for the next call of inflate().\r
 577 \r
 578    In this implementation, the flush parameter of inflate() only affects the\r
 579    return code (per zlib.h).  inflate() always writes as much as possible to\r
 580    strm->next_out, given the space available and the provided input--the effect\r
 581    documented in zlib.h of Z_SYNC_FLUSH.  Furthermore, inflate() always defers\r
 582    the allocation of and copying into a sliding window until necessary, which\r
 583    provides the effect documented in zlib.h for Z_FINISH when the entire input\r
 584    stream available.  So the only thing the flush parameter actually does is:\r
 585    when flush is set to Z_FINISH, inflate() cannot return Z_OK.  Instead it\r
 586    will return Z_BUF_ERROR if it has not reached the end of the stream.\r
 587  */\r
 588 \r
 589 int ZEXPORT inflate(strm, flush)\r
 590 z_streamp strm;\r
 591 int flush;\r
 592 {\r
 593     struct inflate_state FAR *state;\r
 594     unsigned char FAR *next;    /* next input */\r
 595     unsigned char FAR *put;     /* next output */\r
 596     unsigned have, left;        /* available input and output */\r
 597     unsigned long hold;         /* bit buffer */\r
 598     unsigned bits;              /* bits in bit buffer */\r
 599     unsigned in, out;           /* save starting available input and output */\r
 600     unsigned copy;              /* number of stored or match bytes to copy */\r
 601     unsigned char FAR *from;    /* where to copy match bytes from */\r
 602     code here;                  /* current decoding table entry */\r
 603     code last;                  /* parent table entry */\r
 604     unsigned len;               /* length to copy for repeats, bits to drop */\r
 605     int ret;                    /* return code */\r
 606 #ifdef GUNZIP\r
 607     unsigned char hbuf[4];      /* buffer for gzip header crc calculation */\r
 608 #endif\r
 609     static const unsigned short order[19] = /* permutation of code lengths */\r
 610         {16, 17, 18, 0, 8, 7, 9, 6, 10, 5, 11, 4, 12, 3, 13, 2, 14, 1, 15};\r
 611 \r
 612     if (strm == Z_NULL || strm->state == Z_NULL || strm->next_out == Z_NULL ||\r
 613         (strm->next_in == Z_NULL && strm->avail_in != 0))\r
 614         return Z_STREAM_ERROR;\r
 615 \r
 616     state = (struct inflate_state FAR *)strm->state;\r
 617     if (state->mode == TYPE) state->mode = TYPEDO;      /* skip check */\r
 618     LOAD();\r
 619     in = have;\r
 620     out = left;\r
 621     ret = Z_OK;\r
 622     for (;;)\r
 623         switch (state->mode) {\r
 624         case HEAD:\r
 625             if (state->wrap == 0) {\r
 626                 state->mode = TYPEDO;\r
 627                 break;\r
 628             }\r
 629             NEEDBITS(16);\r
 630 #ifdef GUNZIP\r
 631             if ((state->wrap & 2) && hold == 0x8b1f) {  /* gzip header */\r
 632                 state->check = crc32(0L, Z_NULL, 0);\r
 633                 CRC2(state->check, hold);\r
 634                 INITBITS();\r
 635                 state->mode = FLAGS;\r
 636                 break;\r
 637             }\r
 638             state->flags = 0;           /* expect zlib header */\r
 639             if (state->head != Z_NULL)\r
 640                 state->head->done = -1;\r
 641             if (!(state->wrap & 1) ||   /* check if zlib header allowed */\r
 642 #else\r
 643             if (\r
 644 #endif\r
 645                 ((BITS(8) << 8) + (hold >> 8)) % 31) {\r
 646                 strm->msg = (char *)"incorrect header check";\r
 647                 state->mode = BAD;\r
 648                 break;\r
 649             }\r
 650             if (BITS(4) != Z_DEFLATED) {\r
 651                 strm->msg = (char *)"unknown compression method";\r
 652                 state->mode = BAD;\r
 653                 break;\r
 654             }\r
 655             DROPBITS(4);\r
 656             len = BITS(4) + 8;\r
 657             if (state->wbits == 0)\r
 658                 state->wbits = len;\r
 659             else if (len > state->wbits) {\r
 660                 strm->msg = (char *)"invalid window size";\r
 661                 state->mode = BAD;\r
 662                 break;\r
 663             }\r
 664             state->dmax = 1U << len;\r
 665             Tracev((stderr, "inflate:   zlib header ok\n"));\r
 666             strm->adler = state->check = adler32(0L, Z_NULL, 0);\r
 667             state->mode = hold & 0x200 ? DICTID : TYPE;\r
 668             INITBITS();\r
 669             break;\r
 670 #ifdef GUNZIP\r
 671         case FLAGS:\r
 672             NEEDBITS(16);\r
 673             state->flags = (int)(hold);\r
 674             if ((state->flags & 0xff) != Z_DEFLATED) {\r
 675                 strm->msg = (char *)"unknown compression method";\r
 676                 state->mode = BAD;\r
 677                 break;\r
 678             }\r
 679             if (state->flags & 0xe000) {\r
 680                 strm->msg = (char *)"unknown header flags set";\r
 681                 state->mode = BAD;\r
 682                 break;\r
 683             }\r
 684             if (state->head != Z_NULL)\r
 685                 state->head->text = (int)((hold >> 8) & 1);\r
 686             if (state->flags & 0x0200) CRC2(state->check, hold);\r
 687             INITBITS();\r
 688             state->mode = TIME;\r
 689         case TIME:\r
 690             NEEDBITS(32);\r
 691             if (state->head != Z_NULL)\r
 692                 state->head->time = hold;\r
 693             if (state->flags & 0x0200) CRC4(state->check, hold);\r
 694             INITBITS();\r
 695             state->mode = OS;\r
 696         case OS:\r
 697             NEEDBITS(16);\r
 698             if (state->head != Z_NULL) {\r
 699                 state->head->xflags = (int)(hold & 0xff);\r
 700                 state->head->os = (int)(hold >> 8);\r
 701             }\r
 702             if (state->flags & 0x0200) CRC2(state->check, hold);\r
 703             INITBITS();\r
 704             state->mode = EXLEN;\r
 705         case EXLEN:\r
 706             if (state->flags & 0x0400) {\r
 707                 NEEDBITS(16);\r
 708                 state->length = (unsigned)(hold);\r
 709                 if (state->head != Z_NULL)\r
 710                     state->head->extra_len = (unsigned)hold;\r
 711                 if (state->flags & 0x0200) CRC2(state->check, hold);\r
 712                 INITBITS();\r
 713             }\r
 714             else if (state->head != Z_NULL)\r
 715                 state->head->extra = Z_NULL;\r
 716             state->mode = EXTRA;\r
 717         case EXTRA:\r
 718             if (state->flags & 0x0400) {\r
 719                 copy = state->length;\r
 720                 if (copy > have) copy = have;\r
 721                 if (copy) {\r
 722                     if (state->head != Z_NULL &&\r
 723                         state->head->extra != Z_NULL) {\r
 724                         len = state->head->extra_len - state->length;\r
 725                         zmemcpy(state->head->extra + len, next,\r
 726                                 len + copy > state->head->extra_max ?\r
 727                                 state->head->extra_max - len : copy);\r
 728                     }\r
 729                     if (state->flags & 0x0200)\r
 730                         state->check = crc32(state->check, next, copy);\r
 731                     have -= copy;\r
 732                     next += copy;\r
 733                     state->length -= copy;\r
 734                 }\r
 735                 if (state->length) goto inf_leave;\r
 736             }\r
 737             state->length = 0;\r
 738             state->mode = NAME;\r
 739         case NAME:\r
 740             if (state->flags & 0x0800) {\r
 741                 if (have == 0) goto inf_leave;\r
 742                 copy = 0;\r
 743                 do {\r
 744                     len = (unsigned)(next[copy++]);\r
 745                     if (state->head != Z_NULL &&\r
 746                             state->head->name != Z_NULL &&\r
 747                             state->length < state->head->name_max)\r
 748                         state->head->name[state->length++] = len;\r
 749                 } while (len && copy < have);\r
 750                 if (state->flags & 0x0200)\r
 751                     state->check = crc32(state->check, next, copy);\r
 752                 have -= copy;\r
 753                 next += copy;\r
 754                 if (len) goto inf_leave;\r
 755             }\r
 756             else if (state->head != Z_NULL)\r
 757                 state->head->name = Z_NULL;\r
 758             state->length = 0;\r
 759             state->mode = COMMENT;\r
 760         case COMMENT:\r
 761             if (state->flags & 0x1000) {\r
 762                 if (have == 0) goto inf_leave;\r
 763                 copy = 0;\r
 764                 do {\r
 765                     len = (unsigned)(next[copy++]);\r
 766                     if (state->head != Z_NULL &&\r
 767                             state->head->comment != Z_NULL &&\r
 768                             state->length < state->head->comm_max)\r
 769                         state->head->comment[state->length++] = len;\r
 770                 } while (len && copy < have);\r
 771                 if (state->flags & 0x0200)\r
 772                     state->check = crc32(state->check, next, copy);\r
 773                 have -= copy;\r
 774                 next += copy;\r
 775                 if (len) goto inf_leave;\r
 776             }\r
 777             else if (state->head != Z_NULL)\r
 778                 state->head->comment = Z_NULL;\r
 779             state->mode = HCRC;\r
 780         case HCRC:\r
 781             if (state->flags & 0x0200) {\r
 782                 NEEDBITS(16);\r
 783                 if (hold != (state->check & 0xffff)) {\r
 784                     strm->msg = (char *)"header crc mismatch";\r
 785                     state->mode = BAD;\r
 786                     break;\r
 787                 }\r
 788                 INITBITS();\r
 789             }\r
 790             if (state->head != Z_NULL) {\r
 791                 state->head->hcrc = (int)((state->flags >> 9) & 1);\r
 792                 state->head->done = 1;\r
 793             }\r
 794             strm->adler = state->check = crc32(0L, Z_NULL, 0);\r
 795             state->mode = TYPE;\r
 796             break;\r
 797 #endif\r
 798         case DICTID:\r
 799             NEEDBITS(32);\r
 800             strm->adler = state->check = REVERSE(hold);\r
 801             INITBITS();\r
 802             state->mode = DICT;\r
 803         case DICT:\r
 804             if (state->havedict == 0) {\r
 805                 RESTORE();\r
 806                 return Z_NEED_DICT;\r
 807             }\r
 808             strm->adler = state->check = adler32(0L, Z_NULL, 0);\r
 809             state->mode = TYPE;\r
 810         case TYPE:\r
 811             if (flush == Z_BLOCK || flush == Z_TREES) goto inf_leave;\r
 812         case TYPEDO:\r
 813             if (state->last) {\r
 814                 BYTEBITS();\r
 815                 state->mode = CHECK;\r
 816                 break;\r
 817             }\r
 818             NEEDBITS(3);\r
 819             state->last = BITS(1);\r
 820             DROPBITS(1);\r
 821             switch (BITS(2)) {\r
 822             case 0:                             /* stored block */\r
 823                 Tracev((stderr, "inflate:     stored block%s\n",\r
 824                         state->last ? " (last)" : ""));\r
 825                 state->mode = STORED;\r
 826                 break;\r
 827             case 1:                             /* fixed block */\r
 828                 fixedtables(state);\r
 829                 Tracev((stderr, "inflate:     fixed codes block%s\n",\r
 830                         state->last ? " (last)" : ""));\r
 831                 state->mode = LEN_;             /* decode codes */\r
 832                 if (flush == Z_TREES) {\r
 833                     DROPBITS(2);\r
 834                     goto inf_leave;\r
 835                 }\r
 836                 break;\r
 837             case 2:                             /* dynamic block */\r
 838                 Tracev((stderr, "inflate:     dynamic codes block%s\n",\r
 839                         state->last ? " (last)" : ""));\r
 840                 state->mode = TABLE;\r
 841                 break;\r
 842             case 3:\r
 843                 strm->msg = (char *)"invalid block type";\r
 844                 state->mode = BAD;\r
 845             }\r
 846             DROPBITS(2);\r
 847             break;\r
 848         case STORED:\r
 849             BYTEBITS();                         /* go to byte boundary */\r
 850             NEEDBITS(32);\r
 851             if ((hold & 0xffff) != ((hold >> 16) ^ 0xffff)) {\r
 852                 strm->msg = (char *)"invalid stored block lengths";\r
 853                 state->mode = BAD;\r
 854                 break;\r
 855             }\r
 856             state->length = (unsigned)hold & 0xffff;\r
 857             Tracev((stderr, "inflate:       stored length %u\n",\r
 858                     state->length));\r
 859             INITBITS();\r
 860             state->mode = COPY_;\r
 861             if (flush == Z_TREES) goto inf_leave;\r
 862         case COPY_:\r
 863             state->mode = COPY;\r
 864         case COPY:\r
 865             copy = state->length;\r
 866             if (copy) {\r
 867                 if (copy > have) copy = have;\r
 868                 if (copy > left) copy = left;\r
 869                 if (copy == 0) goto inf_leave;\r
 870                 zmemcpy(put, next, copy);\r
 871                 have -= copy;\r
 872                 next += copy;\r
 873                 left -= copy;\r
 874                 put += copy;\r
 875                 state->length -= copy;\r
 876                 break;\r
 877             }\r
 878             Tracev((stderr, "inflate:       stored end\n"));\r
 879             state->mode = TYPE;\r
 880             break;\r
 881         case TABLE:\r
 882             NEEDBITS(14);\r
 883             state->nlen = BITS(5) + 257;\r
 884             DROPBITS(5);\r
 885             state->ndist = BITS(5) + 1;\r
 886             DROPBITS(5);\r
 887             state->ncode = BITS(4) + 4;\r
 888             DROPBITS(4);\r
 889 #ifndef PKZIP_BUG_WORKAROUND\r
 890             if (state->nlen > 286 || state->ndist > 30) {\r
 891                 strm->msg = (char *)"too many length or distance symbols";\r
 892                 state->mode = BAD;\r
 893                 break;\r
 894             }\r
 895 #endif\r
 896             Tracev((stderr, "inflate:       table sizes ok\n"));\r
 897             state->have = 0;\r
 898             state->mode = LENLENS;\r
 899         case LENLENS:\r
 900             while (state->have < state->ncode) {\r
 901                 NEEDBITS(3);\r
 902                 state->lens[order[state->have++]] = (unsigned short)BITS(3);\r
 903                 DROPBITS(3);\r
 904             }\r
 905             while (state->have < 19)\r
 906                 state->lens[order[state->have++]] = 0;\r
 907             state->next = state->codes;\r
 908             state->lencode = (code const FAR *)(state->next);\r
 909             state->lenbits = 7;\r
 910             ret = inflate_table(CODES, state->lens, 19, &(state->next),\r
 911                                 &(state->lenbits), state->work);\r
 912             if (ret) {\r
 913                 strm->msg = (char *)"invalid code lengths set";\r
 914                 state->mode = BAD;\r
 915                 break;\r
 916             }\r
 917             Tracev((stderr, "inflate:       code lengths ok\n"));\r
 918             state->have = 0;\r
 919             state->mode = CODELENS;\r
 920         case CODELENS:\r
 921             while (state->have < state->nlen + state->ndist) {\r
 922                 for (;;) {\r
 923                     here = state->lencode[BITS(state->lenbits)];\r
 924                     if ((unsigned)(here.bits) <= bits) break;\r
 925                     PULLBYTE();\r
 926                 }\r
 927                 if (here.val < 16) {\r
 928                     NEEDBITS(here.bits);\r
 929                     DROPBITS(here.bits);\r
 930                     state->lens[state->have++] = here.val;\r
 931                 }\r
 932                 else {\r
 933                     if (here.val == 16) {\r
 934                         NEEDBITS(here.bits + 2);\r
 935                         DROPBITS(here.bits);\r
 936                         if (state->have == 0) {\r
 937                             strm->msg = (char *)"invalid bit length repeat";\r
 938                             state->mode = BAD;\r
 939                             break;\r
 940                         }\r
 941                         len = state->lens[state->have - 1];\r
 942                         copy = 3 + BITS(2);\r
 943                         DROPBITS(2);\r
 944                     }\r
 945                     else if (here.val == 17) {\r
 946                         NEEDBITS(here.bits + 3);\r
 947                         DROPBITS(here.bits);\r
 948                         len = 0;\r
 949                         copy = 3 + BITS(3);\r
 950                         DROPBITS(3);\r
 951                     }\r
 952                     else {\r
 953                         NEEDBITS(here.bits + 7);\r
 954                         DROPBITS(here.bits);\r
 955                         len = 0;\r
 956                         copy = 11 + BITS(7);\r
 957                         DROPBITS(7);\r
 958                     }\r
 959                     if (state->have + copy > state->nlen + state->ndist) {\r
 960                         strm->msg = (char *)"invalid bit length repeat";\r
 961                         state->mode = BAD;\r
 962                         break;\r
 963                     }\r
 964                     while (copy--)\r
 965                         state->lens[state->have++] = (unsigned short)len;\r
 966                 }\r
 967             }\r
 968 \r
 969             /* handle error breaks in while */\r
 970             if (state->mode == BAD) break;\r
 971 \r
 972             /* check for end-of-block code (better have one) */\r
 973             if (state->lens[256] == 0) {\r
 974                 strm->msg = (char *)"invalid code -- missing end-of-block";\r
 975                 state->mode = BAD;\r
 976                 break;\r
 977             }\r
 978 \r
 979             /* build code tables -- note: do not change the lenbits or distbits\r
 980                values here (9 and 6) without reading the comments in inftrees.h\r
 981                concerning the ENOUGH constants, which depend on those values */\r
 982             state->next = state->codes;\r
 983             state->lencode = (code const FAR *)(state->next);\r
 984             state->lenbits = 9;\r
 985             ret = inflate_table(LENS, state->lens, state->nlen, &(state->next),\r
 986                                 &(state->lenbits), state->work);\r
 987             if (ret) {\r
 988                 strm->msg = (char *)"invalid literal/lengths set";\r
 989                 state->mode = BAD;\r
 990                 break;\r
 991             }\r
 992             state->distcode = (code const FAR *)(state->next);\r
 993             state->distbits = 6;\r
 994             ret = inflate_table(DISTS, state->lens + state->nlen, state->ndist,\r
 995                             &(state->next), &(state->distbits), state->work);\r
 996             if (ret) {\r
 997                 strm->msg = (char *)"invalid distances set";\r
 998                 state->mode = BAD;\r
 999                 break;\r
1000             }\r
1001             Tracev((stderr, "inflate:       codes ok\n"));\r
1002             state->mode = LEN_;\r
1003             if (flush == Z_TREES) goto inf_leave;\r
1004         case LEN_:\r
1005             state->mode = LEN;\r
1006         case LEN:\r
1007             if (have >= 6 && left >= 258) {\r
1008                 RESTORE();\r
1009                 inflate_fast(strm, out);\r
1010                 LOAD();\r
1011                 if (state->mode == TYPE)\r
1012                     state->back = -1;\r
1013                 break;\r
1014             }\r
1015             state->back = 0;\r
1016             for (;;) {\r
1017                 here = state->lencode[BITS(state->lenbits)];\r
1018                 if ((unsigned)(here.bits) <= bits) break;\r
1019                 PULLBYTE();\r
1020             }\r
1021             if (here.op && (here.op & 0xf0) == 0) {\r
1022                 last = here;\r
1023                 for (;;) {\r
1024                     here = state->lencode[last.val +\r
1025                             (BITS(last.bits + last.op) >> last.bits)];\r
1026                     if ((unsigned)(last.bits + here.bits) <= bits) break;\r
1027                     PULLBYTE();\r
1028                 }\r
1029                 DROPBITS(last.bits);\r
1030                 state->back += last.bits;\r
1031             }\r
1032             DROPBITS(here.bits);\r
1033             state->back += here.bits;\r
1034             state->length = (unsigned)here.val;\r
1035             if ((int)(here.op) == 0) {\r
1036                 Tracevv((stderr, here.val >= 0x20 && here.val < 0x7f ?\r
1037                         "inflate:         literal '%c'\n" :\r
1038                         "inflate:         literal 0x%02x\n", here.val));\r
1039                 state->mode = LIT;\r
1040                 break;\r
1041             }\r
1042             if (here.op & 32) {\r
1043                 Tracevv((stderr, "inflate:         end of block\n"));\r
1044                 state->back = -1;\r
1045                 state->mode = TYPE;\r
1046                 break;\r
1047             }\r
1048             if (here.op & 64) {\r
1049                 strm->msg = (char *)"invalid literal/length code";\r
1050                 state->mode = BAD;\r
1051                 break;\r
1052             }\r
1053             state->extra = (unsigned)(here.op) & 15;\r
1054             state->mode = LENEXT;\r
1055         case LENEXT:\r
1056             if (state->extra) {\r
1057                 NEEDBITS(state->extra);\r
1058                 state->length += BITS(state->extra);\r
1059                 DROPBITS(state->extra);\r
1060                 state->back += state->extra;\r
1061             }\r
1062             Tracevv((stderr, "inflate:         length %u\n", state->length));\r
1063             state->was = state->length;\r
1064             state->mode = DIST;\r
1065         case DIST:\r
1066             for (;;) {\r
1067                 here = state->distcode[BITS(state->distbits)];\r
1068                 if ((unsigned)(here.bits) <= bits) break;\r
1069                 PULLBYTE();\r
1070             }\r
1071             if ((here.op & 0xf0) == 0) {\r
1072                 last = here;\r
1073                 for (;;) {\r
1074                     here = state->distcode[last.val +\r
1075                             (BITS(last.bits + last.op) >> last.bits)];\r
1076                     if ((unsigned)(last.bits + here.bits) <= bits) break;\r
1077                     PULLBYTE();\r
1078                 }\r
1079                 DROPBITS(last.bits);\r
1080                 state->back += last.bits;\r
1081             }\r
1082             DROPBITS(here.bits);\r
1083             state->back += here.bits;\r
1084             if (here.op & 64) {\r
1085                 strm->msg = (char *)"invalid distance code";\r
1086                 state->mode = BAD;\r
1087                 break;\r
1088             }\r
1089             state->offset = (unsigned)here.val;\r
1090             state->extra = (unsigned)(here.op) & 15;\r
1091             state->mode = DISTEXT;\r
1092         case DISTEXT:\r
1093             if (state->extra) {\r
1094                 NEEDBITS(state->extra);\r
1095                 state->offset += BITS(state->extra);\r
1096                 DROPBITS(state->extra);\r
1097                 state->back += state->extra;\r
1098             }\r
1099 #ifdef INFLATE_STRICT\r
1100             if (state->offset > state->dmax) {\r
1101                 strm->msg = (char *)"invalid distance too far back";\r
1102                 state->mode = BAD;\r
1103                 break;\r
1104             }\r
1105 #endif\r
1106             Tracevv((stderr, "inflate:         distance %u\n", state->offset));\r
1107             state->mode = MATCH;\r
1108         case MATCH:\r
1109             if (left == 0) goto inf_leave;\r
1110             copy = out - left;\r
1111             if (state->offset > copy) {         /* copy from window */\r
1112                 copy = state->offset - copy;\r
1113                 if (copy > state->whave) {\r
1114                     if (state->sane) {\r
1115                         strm->msg = (char *)"invalid distance too far back";\r
1116                         state->mode = BAD;\r
1117                         break;\r
1118                     }\r
1119 #ifdef INFLATE_ALLOW_INVALID_DISTANCE_TOOFAR_ARRR\r
1120                     Trace((stderr, "inflate.c too far\n"));\r
1121                     copy -= state->whave;\r
1122                     if (copy > state->length) copy = state->length;\r
1123                     if (copy > left) copy = left;\r
1124                     left -= copy;\r
1125                     state->length -= copy;\r
1126                     do {\r
1127                         *put++ = 0;\r
1128                     } while (--copy);\r
1129                     if (state->length == 0) state->mode = LEN;\r
1130                     break;\r
1131 #endif\r
1132                 }\r
1133                 if (copy > state->wnext) {\r
1134                     copy -= state->wnext;\r
1135                     from = state->window + (state->wsize - copy);\r
1136                 }\r
1137                 else\r
1138                     from = state->window + (state->wnext - copy);\r
1139                 if (copy > state->length) copy = state->length;\r
1140             }\r
1141             else {                              /* copy from output */\r
1142                 from = put - state->offset;\r
1143                 copy = state->length;\r
1144             }\r
1145             if (copy > left) copy = left;\r
1146             left -= copy;\r
1147             state->length -= copy;\r
1148             do {\r
1149                 *put++ = *from++;\r
1150             } while (--copy);\r
1151             if (state->length == 0) state->mode = LEN;\r
1152             break;\r
1153         case LIT:\r
1154             if (left == 0) goto inf_leave;\r
1155             *put++ = (unsigned char)(state->length);\r
1156             left--;\r
1157             state->mode = LEN;\r
1158             break;\r
1159         case CHECK:\r
1160             if (state->wrap) {\r
1161                 NEEDBITS(32);\r
1162                 out -= left;\r
1163                 strm->total_out += out;\r
1164                 state->total += out;\r
1165                 if (out)\r
1166                     strm->adler = state->check =\r
1167                         UPDATE(state->check, put - out, out);\r
1168                 out = left;\r
1169                 if ((\r
1170 #ifdef GUNZIP\r
1171                      state->flags ? hold :\r
1172 #endif\r
1173                      REVERSE(hold)) != state->check) {\r
1174                     strm->msg = (char *)"incorrect data check";\r
1175                     state->mode = BAD;\r
1176                     break;\r
1177                 }\r
1178                 INITBITS();\r
1179                 Tracev((stderr, "inflate:   check matches trailer\n"));\r
1180             }\r
1181 #ifdef GUNZIP\r
1182             state->mode = LENGTH;\r
1183         case LENGTH:\r
1184             if (state->wrap && state->flags) {\r
1185                 NEEDBITS(32);\r
1186                 if (hold != (state->total & 0xffffffffUL)) {\r
1187                     strm->msg = (char *)"incorrect length check";\r
1188                     state->mode = BAD;\r
1189                     break;\r
1190                 }\r
1191                 INITBITS();\r
1192                 Tracev((stderr, "inflate:   length matches trailer\n"));\r
1193             }\r
1194 #endif\r
1195             state->mode = DONE;\r
1196         case DONE:\r
1197             ret = Z_STREAM_END;\r
1198             goto inf_leave;\r
1199         case BAD:\r
1200             ret = Z_DATA_ERROR;\r
1201             goto inf_leave;\r
1202         case MEM:\r
1203             return Z_MEM_ERROR;\r
1204         case SYNC:\r
1205         default:\r
1206             return Z_STREAM_ERROR;\r
1207         }\r
1208 \r
1209     /*\r
1210        Return from inflate(), updating the total counts and the check value.\r
1211        If there was no progress during the inflate() call, return a buffer\r
1212        error.  Call updatewindow() to create and/or update the window state.\r
1213        Note: a memory error from inflate() is non-recoverable.\r
1214      */\r
1215   inf_leave:\r
1216     RESTORE();\r
1217     if (state->wsize || (state->mode < CHECK && out != strm->avail_out))\r
1218         if (updatewindow(strm, out)) {\r
1219             state->mode = MEM;\r
1220             return Z_MEM_ERROR;\r
1221         }\r
1222     in -= strm->avail_in;\r
1223     out -= strm->avail_out;\r
1224     strm->total_in += in;\r
1225     strm->total_out += out;\r
1226     state->total += out;\r
1227     if (state->wrap && out)\r
1228         strm->adler = state->check =\r
1229             UPDATE(state->check, strm->next_out - out, out);\r
1230     strm->data_type = state->bits + (state->last ? 64 : 0) +\r
1231                       (state->mode == TYPE ? 128 : 0) +\r
1232                       (state->mode == LEN_ || state->mode == COPY_ ? 256 : 0);\r
1233     if (((in == 0 && out == 0) || flush == Z_FINISH) && ret == Z_OK)\r
1234         ret = Z_BUF_ERROR;\r
1235     return ret;\r
1236 }\r
1237 \r
1238 int ZEXPORT inflateEnd(strm)\r
1239 z_streamp strm;\r
1240 {\r
1241     struct inflate_state FAR *state;\r
1242     if (strm == Z_NULL || strm->state == Z_NULL || strm->zfree == (free_func)0)\r
1243         return Z_STREAM_ERROR;\r
1244     state = (struct inflate_state FAR *)strm->state;\r
1245     if (state->window != Z_NULL) ZFREE(strm, state->window);\r
1246     ZFREE(strm, strm->state);\r
1247     strm->state = Z_NULL;\r
1248     Tracev((stderr, "inflate: end\n"));\r
1249     return Z_OK;\r
1250 }\r
1251 \r
1252 int ZEXPORT inflateSetDictionary(strm, dictionary, dictLength)\r
1253 z_streamp strm;\r
1254 const Bytef *dictionary;\r
1255 uInt dictLength;\r
1256 {\r
1257     struct inflate_state FAR *state;\r
1258     unsigned long id;\r
1259 \r
1260     /* check state */\r
1261     if (strm == Z_NULL || strm->state == Z_NULL) return Z_STREAM_ERROR;\r
1262     state = (struct inflate_state FAR *)strm->state;\r
1263     if (state->wrap != 0 && state->mode != DICT)\r
1264         return Z_STREAM_ERROR;\r
1265 \r
1266     /* check for correct dictionary id */\r
1267     if (state->mode == DICT) {\r
1268         id = adler32(0L, Z_NULL, 0);\r
1269         id = adler32(id, dictionary, dictLength);\r
1270         if (id != state->check)\r
1271             return Z_DATA_ERROR;\r
1272     }\r
1273 \r
1274     /* copy dictionary to window */\r
1275     if (updatewindow(strm, strm->avail_out)) {\r
1276         state->mode = MEM;\r
1277         return Z_MEM_ERROR;\r
1278     }\r
1279     if (dictLength > state->wsize) {\r
1280         zmemcpy(state->window, dictionary + dictLength - state->wsize,\r
1281                 state->wsize);\r
1282         state->whave = state->wsize;\r
1283     }\r
1284     else {\r
1285         zmemcpy(state->window + state->wsize - dictLength, dictionary,\r
1286                 dictLength);\r
1287         state->whave = dictLength;\r
1288     }\r
1289     state->havedict = 1;\r
1290     Tracev((stderr, "inflate:   dictionary set\n"));\r
1291     return Z_OK;\r
1292 }\r
1293 \r
1294 int ZEXPORT inflateGetHeader(strm, head)\r
1295 z_streamp strm;\r
1296 gz_headerp head;\r
1297 {\r
1298     struct inflate_state FAR *state;\r
1299 \r
1300     /* check state */\r
1301     if (strm == Z_NULL || strm->state == Z_NULL) return Z_STREAM_ERROR;\r
1302     state = (struct inflate_state FAR *)strm->state;\r
1303     if ((state->wrap & 2) == 0) return Z_STREAM_ERROR;\r
1304 \r
1305     /* save header structure */\r
1306     state->head = head;\r
1307     head->done = 0;\r
1308     return Z_OK;\r
1309 }\r
1310 \r
1311 /*\r
1312    Search buf[0..len-1] for the pattern: 0, 0, 0xff, 0xff.  Return when found\r
1313    or when out of input.  When called, *have is the number of pattern bytes\r
1314    found in order so far, in 0..3.  On return *have is updated to the new\r
1315    state.  If on return *have equals four, then the pattern was found and the\r
1316    return value is how many bytes were read including the last byte of the\r
1317    pattern.  If *have is less than four, then the pattern has not been found\r
1318    yet and the return value is len.  In the latter case, syncsearch() can be\r
1319    called again with more data and the *have state.  *have is initialized to\r
1320    zero for the first call.\r
1321  */\r
1322 local unsigned syncsearch(have, buf, len)\r
1323 unsigned FAR *have;\r
1324 unsigned char FAR *buf;\r
1325 unsigned len;\r
1326 {\r
1327     unsigned got;\r
1328     unsigned next;\r
1329 \r
1330     got = *have;\r
1331     next = 0;\r
1332     while (next < len && got < 4) {\r
1333         if ((int)(buf[next]) == (got < 2 ? 0 : 0xff))\r
1334             got++;\r
1335         else if (buf[next])\r
1336             got = 0;\r
1337         else\r
1338             got = 4 - got;\r
1339         next++;\r
1340     }\r
1341     *have = got;\r
1342     return next;\r
1343 }\r
1344 \r
1345 int ZEXPORT inflateSync(strm)\r
1346 z_streamp strm;\r
1347 {\r
1348     unsigned len;               /* number of bytes to look at or looked at */\r
1349     unsigned long in, out;      /* temporary to save total_in and total_out */\r
1350     unsigned char buf[4];       /* to restore bit buffer to byte string */\r
1351     struct inflate_state FAR *state;\r
1352 \r
1353     /* check parameters */\r
1354     if (strm == Z_NULL || strm->state == Z_NULL) return Z_STREAM_ERROR;\r
1355     state = (struct inflate_state FAR *)strm->state;\r
1356     if (strm->avail_in == 0 && state->bits < 8) return Z_BUF_ERROR;\r
1357 \r
1358     /* if first time, start search in bit buffer */\r
1359     if (state->mode != SYNC) {\r
1360         state->mode = SYNC;\r
1361         state->hold <<= state->bits & 7;\r
1362         state->bits -= state->bits & 7;\r
1363         len = 0;\r
1364         while (state->bits >= 8) {\r
1365             buf[len++] = (unsigned char)(state->hold);\r
1366             state->hold >>= 8;\r
1367             state->bits -= 8;\r
1368         }\r
1369         state->have = 0;\r
1370         syncsearch(&(state->have), buf, len);\r
1371     }\r
1372 \r
1373     /* search available input */\r
1374     len = syncsearch(&(state->have), strm->next_in, strm->avail_in);\r
1375     strm->avail_in -= len;\r
1376     strm->next_in += len;\r
1377     strm->total_in += len;\r
1378 \r
1379     /* return no joy or set up to restart inflate() on a new block */\r
1380     if (state->have != 4) return Z_DATA_ERROR;\r
1381     in = strm->total_in;  out = strm->total_out;\r
1382     inflateReset(strm);\r
1383     strm->total_in = in;  strm->total_out = out;\r
1384     state->mode = TYPE;\r
1385     return Z_OK;\r
1386 }\r
1387 \r
1388 /*\r
1389    Returns true if inflate is currently at the end of a block generated by\r
1390    Z_SYNC_FLUSH or Z_FULL_FLUSH. This function is used by one PPP\r
1391    implementation to provide an additional safety check. PPP uses\r
1392    Z_SYNC_FLUSH but removes the length bytes of the resulting empty stored\r
1393    block. When decompressing, PPP checks that at the end of input packet,\r
1394    inflate is waiting for these length bytes.\r
1395  */\r
1396 int ZEXPORT inflateSyncPoint(strm)\r
1397 z_streamp strm;\r
1398 {\r
1399     struct inflate_state FAR *state;\r
1400 \r
1401     if (strm == Z_NULL || strm->state == Z_NULL) return Z_STREAM_ERROR;\r
1402     state = (struct inflate_state FAR *)strm->state;\r
1403     return state->mode == STORED && state->bits == 0;\r
1404 }\r
1405 \r
1406 int ZEXPORT inflateCopy(dest, source)\r
1407 z_streamp dest;\r
1408 z_streamp source;\r
1409 {\r
1410     struct inflate_state FAR *state;\r
1411     struct inflate_state FAR *copy;\r
1412     unsigned char FAR *window;\r
1413     unsigned wsize;\r
1414 \r
1415     /* check input */\r
1416     if (dest == Z_NULL || source == Z_NULL || source->state == Z_NULL ||\r
1417         source->zalloc == (alloc_func)0 || source->zfree == (free_func)0)\r
1418         return Z_STREAM_ERROR;\r
1419     state = (struct inflate_state FAR *)source->state;\r
1420 \r
1421     /* allocate space */\r
1422     copy = (struct inflate_state FAR *)\r
1423            ZALLOC(source, 1, sizeof(struct inflate_state));\r
1424     if (copy == Z_NULL) return Z_MEM_ERROR;\r
1425     window = Z_NULL;\r
1426     if (state->window != Z_NULL) {\r
1427         window = (unsigned char FAR *)\r
1428                  ZALLOC(source, 1U << state->wbits, sizeof(unsigned char));\r
1429         if (window == Z_NULL) {\r
1430             ZFREE(source, copy);\r
1431             return Z_MEM_ERROR;\r
1432         }\r
1433     }\r
1434 \r
1435     /* copy state */\r
1436     zmemcpy(dest, source, sizeof(z_stream));\r
1437     zmemcpy(copy, state, sizeof(struct inflate_state));\r
1438     if (state->lencode >= state->codes &&\r
1439         state->lencode <= state->codes + ENOUGH - 1) {\r
1440         copy->lencode = copy->codes + (state->lencode - state->codes);\r
1441         copy->distcode = copy->codes + (state->distcode - state->codes);\r
1442     }\r
1443     copy->next = copy->codes + (state->next - state->codes);\r
1444     if (window != Z_NULL) {\r
1445         wsize = 1U << state->wbits;\r
1446         zmemcpy(window, state->window, wsize);\r
1447     }\r
1448     copy->window = window;\r
1449     dest->state = (struct internal_state FAR *)copy;\r
1450     return Z_OK;\r
1451 }\r
1452 \r
1453 int ZEXPORT inflateUndermine(strm, subvert)\r
1454 z_streamp strm;\r
1455 int subvert;\r
1456 {\r
1457     struct inflate_state FAR *state;\r
1458 \r
1459     if (strm == Z_NULL || strm->state == Z_NULL) return Z_STREAM_ERROR;\r
1460     state = (struct inflate_state FAR *)strm->state;\r
1461     state->sane = !subvert;\r
1462 #ifdef INFLATE_ALLOW_INVALID_DISTANCE_TOOFAR_ARRR\r
1463     return Z_OK;\r
1464 #else\r
1465     state->sane = 1;\r
1466     return Z_DATA_ERROR;\r
1467 #endif\r
1468 }\r
1469 \r
1470 long ZEXPORT inflateMark(strm)\r
1471 z_streamp strm;\r
1472 {\r
1473     struct inflate_state FAR *state;\r
1474 \r
1475     if (strm == Z_NULL || strm->state == Z_NULL) return -1L << 16;\r
1476     state = (struct inflate_state FAR *)strm->state;\r
1477     return ((long)(state->back) << 16) +\r
1478         (state->mode == COPY ? state->length :\r
1479             (state->mode == MATCH ? state->was - state->length : 0));\r
1480 }\r