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