deps/inflate.c

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