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                             state->head->extra_max) {
 746                         zmemcpy(state->head->extra + len, next,
 747                                 len + copy > state->head->extra_max ?
 748                                 state->head->extra_max - len : copy);
 749                     }
 750                     if (state->flags & 0x0200)
 751                         state->check = crc32(state->check, next, copy);
 752                     have -= copy;
 753                     next += copy;
 754                     state->length -= copy;
 755                 }
 756                 if (state->length) goto inf_leave;
 757             }
 758             state->length = 0;
 759             state->mode = NAME;
 760             /* FALL THROUGH */
 761         case NAME:
 762             if (state->flags & 0x0800) {
 763                 if (have == 0) goto inf_leave;
 764                 copy = 0;
 765                 do {
 766                     len = (unsigned)(next[copy++]);
 767                     if (state->head != Z_NULL &&
 768                             state->head->name != Z_NULL &&
 769                             state->length < state->head->name_max)
 770                         state->head->name[state->length++] = len;
 771                 } while (len && copy < have);
 772                 if (state->flags & 0x0200)
 773                     state->check = crc32(state->check, next, copy);
 774                 have -= copy;
 775                 next += copy;
 776                 if (len) goto inf_leave;
 777             }
 778             else if (state->head != Z_NULL)
 779                 state->head->name = Z_NULL;
 780             state->length = 0;
 781             state->mode = COMMENT;
 782             /* FALL THROUGH */
 783         case COMMENT:
 784             if (state->flags & 0x1000) {
 785                 if (have == 0) goto inf_leave;
 786                 copy = 0;
 787                 do {
 788                     len = (unsigned)(next[copy++]);
 789                     if (state->head != Z_NULL &&
 790                             state->head->comment != Z_NULL &&
 791                             state->length < state->head->comm_max)
 792                         state->head->comment[state->length++] = len;
 793                 } while (len && copy < have);
 794                 if (state->flags & 0x0200)
 795                     state->check = crc32(state->check, next, copy);
 796                 have -= copy;
 797                 next += copy;
 798                 if (len) goto inf_leave;
 799             }
 800             else if (state->head != Z_NULL)
 801                 state->head->comment = Z_NULL;
 802             state->mode = HCRC;
 803             /* FALL THROUGH */
 804         case HCRC:
 805             if (state->flags & 0x0200) {
 806                 NEEDBITS(16);
 807                 if (hold != (state->check & 0xffff)) {
 808                     strm->msg = (char *)"header crc mismatch";
 809                     state->mode = BAD;
 810                     break;
 811                 }
 812                 INITBITS();
 813             }
 814             if (state->head != Z_NULL) {
 815                 state->head->hcrc = (int)((state->flags >> 9) & 1);
 816                 state->head->done = 1;
 817             }
 818             strm->adler = state->check = crc32(0L, Z_NULL, 0);
 819             state->mode = TYPE;
 820             break;
 821 #endif
 822         case DICTID:
 823             NEEDBITS(32);
 824             strm->adler = state->check = ZSWAP32(hold);
 825             INITBITS();
 826             state->mode = DICT;
 827             /* FALL THROUGH */
 828         case DICT:
 829             if (state->havedict == 0) {
 830                 RESTORE();
 831                 return Z_NEED_DICT;
 832             }
 833             strm->adler = state->check = adler32(0L, Z_NULL, 0);
 834             state->mode = TYPE;
 835             /* FALL THROUGH */
 836         case TYPE:
 837             if (flush == Z_BLOCK || flush == Z_TREES) goto inf_leave;
 838             /* FALL THROUGH */
 839         case TYPEDO:
 840             if (state->last) {
 841                 BYTEBITS();
 842                 state->mode = CHECK;
 843                 break;
 844             }
 845             NEEDBITS(3);
 846             state->last = BITS(1);
 847             DROPBITS(1);
 848             switch (BITS(2)) {
 849             case 0:                             /* stored block */
 850                 Tracev((stderr, "inflate:     stored block%s\n",
 851                         state->last ? " (last)" : ""));
 852                 state->mode = STORED;
 853                 break;
 854             case 1:                             /* fixed block */
 855                 fixedtables(state);
 856                 Tracev((stderr, "inflate:     fixed codes block%s\n",
 857                         state->last ? " (last)" : ""));
 858                 state->mode = LEN_;             /* decode codes */
 859                 if (flush == Z_TREES) {
 860                     DROPBITS(2);
 861                     goto inf_leave;
 862                 }
 863                 break;
 864             case 2:                             /* dynamic block */
 865                 Tracev((stderr, "inflate:     dynamic codes block%s\n",
 866                         state->last ? " (last)" : ""));
 867                 state->mode = TABLE;
 868                 break;
 869             case 3:
 870                 strm->msg = (char *)"invalid block type";
 871                 state->mode = BAD;
 872             }
 873             DROPBITS(2);
 874             break;
 875         case STORED:
 876             BYTEBITS();                         /* go to byte boundary */
 877             NEEDBITS(32);
 878             if ((hold & 0xffff) != ((hold >> 16) ^ 0xffff)) {
 879                 strm->msg = (char *)"invalid stored block lengths";
 880                 state->mode = BAD;
 881                 break;
 882             }
 883             state->length = (unsigned)hold & 0xffff;
 884             Tracev((stderr, "inflate:       stored length %u\n",
 885                     state->length));
 886             INITBITS();
 887             state->mode = COPY_;
 888             if (flush == Z_TREES) goto inf_leave;
 889             /* FALLTHROUGH */
 890         case COPY_:
 891             state->mode = COPY;
 892             /* FALLTHROUGH */
 893         case COPY:
 894             copy = state->length;
 895             if (copy) {
 896                 if (copy > have) copy = have;
 897                 if (copy > left) copy = left;
 898                 if (copy == 0) goto inf_leave;
 899                 zmemcpy(put, next, copy);
 900                 have -= copy;
 901                 next += copy;
 902                 left -= copy;
 903                 put += copy;
 904                 state->length -= copy;
 905                 break;
 906             }
 907             Tracev((stderr, "inflate:       stored end\n"));
 908             state->mode = TYPE;
 909             break;
 910         case TABLE:
 911             NEEDBITS(14);
 912             state->nlen = BITS(5) + 257;
 913             DROPBITS(5);
 914             state->ndist = BITS(5) + 1;
 915             DROPBITS(5);
 916             state->ncode = BITS(4) + 4;
 917             DROPBITS(4);
 918 #ifndef PKZIP_BUG_WORKAROUND
 919             if (state->nlen > 286 || state->ndist > 30) {
 920                 strm->msg = (char *)"too many length or distance symbols";
 921                 state->mode = BAD;
 922                 break;
 923             }
 924 #endif
 925             Tracev((stderr, "inflate:       table sizes ok\n"));
 926             state->have = 0;
 927             state->mode = LENLENS;
 928             /* FALL THROUGH */
 929         case LENLENS:
 930             while (state->have < state->ncode) {
 931                 NEEDBITS(3);
 932                 state->lens[order[state->have++]] = (unsigned short)BITS(3);
 933                 DROPBITS(3);
 934             }
 935             while (state->have < 19)
 936                 state->lens[order[state->have++]] = 0;
 937             state->next = state->codes;
 938             state->lencode = (const code FAR *)(state->next);
 939             state->lenbits = 7;
 940             ret = inflate_table(CODES, state->lens, 19, &(state->next),
 941                                 &(state->lenbits), state->work);
 942             if (ret) {
 943                 strm->msg = (char *)"invalid code lengths set";
 944                 state->mode = BAD;
 945                 break;
 946             }
 947             Tracev((stderr, "inflate:       code lengths ok\n"));
 948             state->have = 0;
 949             state->mode = CODELENS;
 950             /* FALL THROUGH */
 951         case CODELENS:
 952             while (state->have < state->nlen + state->ndist) {
 953                 for (;;) {
 954                     here = state->lencode[BITS(state->lenbits)];
 955                     if ((unsigned)(here.bits) <= bits) break;
 956                     PULLBYTE();
 957                 }
 958                 if (here.val < 16) {
 959                     DROPBITS(here.bits);
 960                     state->lens[state->have++] = here.val;
 961                 }
 962                 else {
 963                     if (here.val == 16) {
 964                         NEEDBITS(here.bits + 2);
 965                         DROPBITS(here.bits);
 966                         if (state->have == 0) {
 967                             strm->msg = (char *)"invalid bit length repeat";
 968                             state->mode = BAD;
 969                             break;
 970                         }
 971                         len = state->lens[state->have - 1];
 972                         copy = 3 + BITS(2);
 973                         DROPBITS(2);
 974                     }
 975                     else if (here.val == 17) {
 976                         NEEDBITS(here.bits + 3);
 977                         DROPBITS(here.bits);
 978                         len = 0;
 979                         copy = 3 + BITS(3);
 980                         DROPBITS(3);
 981                     }
 982                     else {
 983                         NEEDBITS(here.bits + 7);
 984                         DROPBITS(here.bits);
 985                         len = 0;
 986                         copy = 11 + BITS(7);
 987                         DROPBITS(7);
 988                     }
 989                     if (state->have + copy > state->nlen + state->ndist) {
 990                         strm->msg = (char *)"invalid bit length repeat";
 991                         state->mode = BAD;
 992                         break;
 993                     }
 994                     while (copy--)
 995                         state->lens[state->have++] = (unsigned short)len;
 996                 }
 997             }
 998
 999             /* handle error breaks in while */
1000             if (state->mode == BAD) break;
1001
1002             /* check for end-of-block code (better have one) */
1003             if (state->lens[256] == 0) {
1004                 strm->msg = (char *)"invalid code -- missing end-of-block";
1005                 state->mode = BAD;
1006                 break;
1007             }
1008
1009             /* build code tables -- note: do not change the lenbits or distbits
1010                values here (9 and 6) without reading the comments in inftrees.h
1011                concerning the ENOUGH constants, which depend on those values */
1012             state->next = state->codes;
1013             state->lencode = (const code FAR *)(state->next);
1014             state->lenbits = 9;
1015             ret = inflate_table(LENS, state->lens, state->nlen, &(state->next),
1016                                 &(state->lenbits), state->work);
1017             if (ret) {
1018                 strm->msg = (char *)"invalid literal/lengths set";
1019                 state->mode = BAD;
1020                 break;
1021             }
1022             state->distcode = (const code FAR *)(state->next);
1023             state->distbits = 6;
1024             ret = inflate_table(DISTS, state->lens + state->nlen, state->ndist,
1025                             &(state->next), &(state->distbits), state->work);
1026             if (ret) {
1027                 strm->msg = (char *)"invalid distances set";
1028                 state->mode = BAD;
1029                 break;
1030             }
1031             Tracev((stderr, "inflate:       codes ok\n"));
1032             state->mode = LEN_;
1033             if (flush == Z_TREES) goto inf_leave;
1034             /* FALL THROUGH */
1035         case LEN_:
1036             state->mode = LEN;
1037             /* FALL THROUGH */
1038         case LEN:
1039             if (have >= 6 && left >= 258) {
1040                 RESTORE();
1041                 inflate_fast(strm, out);
1042                 LOAD();
1043                 if (state->mode == TYPE)
1044                     state->back = -1;
1045                 break;
1046             }
1047             state->back = 0;
1048             for (;;) {
1049                 here = state->lencode[BITS(state->lenbits)];
1050                 if ((unsigned)(here.bits) <= bits) break;
1051                 PULLBYTE();
1052             }
1053             if (here.op && (here.op & 0xf0) == 0) {
1054                 last = here;
1055                 for (;;) {
1056                     here = state->lencode[last.val +
1057                             (BITS(last.bits + last.op) >> last.bits)];
1058                     if ((unsigned)(last.bits + here.bits) <= bits) break;
1059                     PULLBYTE();
1060                 }
1061                 DROPBITS(last.bits);
1062                 state->back += last.bits;
1063             }
1064             DROPBITS(here.bits);
1065             state->back += here.bits;
1066             state->length = (unsigned)here.val;
1067             if ((int)(here.op) == 0) {
1068                 Tracevv((stderr, here.val >= 0x20 && here.val < 0x7f ?
1069                         "inflate:         literal '%c'\n" :
1070                         "inflate:         literal 0x%02x\n", here.val));
1071                 state->mode = LIT;
1072                 break;
1073             }
1074             if (here.op & 32) {
1075                 Tracevv((stderr, "inflate:         end of block\n"));
1076                 state->back = -1;
1077                 state->mode = TYPE;
1078                 break;
1079             }
1080             if (here.op & 64) {
1081                 strm->msg = (char *)"invalid literal/length code";
1082                 state->mode = BAD;
1083                 break;
1084             }
1085             state->extra = (unsigned)(here.op) & 15;
1086             state->mode = LENEXT;
1087             /* FALL THROUGH */
1088         case LENEXT:
1089             if (state->extra) {
1090                 NEEDBITS(state->extra);
1091                 state->length += BITS(state->extra);
1092                 DROPBITS(state->extra);
1093                 state->back += state->extra;
1094             }
1095             Tracevv((stderr, "inflate:         length %u\n", state->length));
1096             state->was = state->length;
1097             state->mode = DIST;
1098             /* FALL THROUGH */
1099         case DIST:
1100             for (;;) {
1101                 here = state->distcode[BITS(state->distbits)];
1102                 if ((unsigned)(here.bits) <= bits) break;
1103                 PULLBYTE();
1104             }
1105             if ((here.op & 0xf0) == 0) {
1106                 last = here;
1107                 for (;;) {
1108                     here = state->distcode[last.val +
1109                             (BITS(last.bits + last.op) >> last.bits)];
1110                     if ((unsigned)(last.bits + here.bits) <= bits) break;
1111                     PULLBYTE();
1112                 }
1113                 DROPBITS(last.bits);
1114                 state->back += last.bits;
1115             }
1116             DROPBITS(here.bits);
1117             state->back += here.bits;
1118             if (here.op & 64) {
1119                 strm->msg = (char *)"invalid distance code";
1120                 state->mode = BAD;
1121                 break;
1122             }
1123             state->offset = (unsigned)here.val;
1124             state->extra = (unsigned)(here.op) & 15;
1125             state->mode = DISTEXT;
1126             /* FALL THROUGH */
1127         case DISTEXT:
1128             if (state->extra) {
1129                 NEEDBITS(state->extra);
1130                 state->offset += BITS(state->extra);
1131                 DROPBITS(state->extra);
1132                 state->back += state->extra;
1133             }
1134 #ifdef INFLATE_STRICT
1135             if (state->offset > state->dmax) {
1136                 strm->msg = (char *)"invalid distance too far back";
1137                 state->mode = BAD;
1138                 break;
1139             }
1140 #endif
1141             Tracevv((stderr, "inflate:         distance %u\n", state->offset));
1142             state->mode = MATCH;
1143             /* FALL THROUGH */
1144         case MATCH:
1145             if (left == 0) goto inf_leave;
1146             copy = out - left;
1147             if (state->offset > copy) {         /* copy from window */
1148                 copy = state->offset - copy;
1149                 if (copy > state->whave) {
1150                     if (state->sane) {
1151                         strm->msg = (char *)"invalid distance too far back";
1152                         state->mode = BAD;
1153                         break;
1154                     }
1155 #ifdef INFLATE_ALLOW_INVALID_DISTANCE_TOOFAR_ARRR
1156                     Trace((stderr, "inflate.c too far\n"));
1157                     copy -= state->whave;
1158                     if (copy > state->length) copy = state->length;
1159                     if (copy > left) copy = left;
1160                     left -= copy;
1161                     state->length -= copy;
1162                     do {
1163                         *put++ = 0;
1164                     } while (--copy);
1165                     if (state->length == 0) state->mode = LEN;
1166                     break;
1167 #endif
1168                 }
1169                 if (copy > state->wnext) {
1170                     copy -= state->wnext;
1171                     from = state->window + (state->wsize - copy);
1172                 }
1173                 else
1174                     from = state->window + (state->wnext - copy);
1175                 if (copy > state->length) copy = state->length;
1176             }
1177             else {                              /* copy from output */
1178                 from = put - state->offset;
1179                 copy = state->length;
1180             }
1181             if (copy > left) copy = left;
1182             left -= copy;
1183             state->length -= copy;
1184             do {
1185                 *put++ = *from++;
1186             } while (--copy);
1187             if (state->length == 0) state->mode = LEN;
1188             break;
1189         case LIT:
1190             if (left == 0) goto inf_leave;
1191             *put++ = (unsigned char)(state->length);
1192             left--;
1193             state->mode = LEN;
1194             break;
1195         case CHECK:
1196             if (state->wrap) {
1197                 NEEDBITS(32);
1198                 out -= left;
1199                 strm->total_out += out;
1200                 state->total += out;
1201                 if (out)
1202                     strm->adler = state->check =
1203                         UPDATE(state->check, put - out, out);
1204                 out = left;
1205                 if ((
1206 #ifdef GUNZIP
1207                      state->flags ? hold :
1208 #endif
1209                      ZSWAP32(hold)) != state->check) {
1210                     strm->msg = (char *)"incorrect data check";
1211                     state->mode = BAD;
1212                     break;
1213                 }
1214                 INITBITS();
1215                 Tracev((stderr, "inflate:   check matches trailer\n"));
1216             }
1217 #ifdef GUNZIP
1218             state->mode = LENGTH;
1219             /* FALL THROUGH */
1220         case LENGTH:
1221             if (state->wrap && state->flags) {
1222                 NEEDBITS(32);
1223                 if (hold != (state->total & 0xffffffffUL)) {
1224                     strm->msg = (char *)"incorrect length check";
1225                     state->mode = BAD;
1226                     break;
1227                 }
1228                 INITBITS();
1229                 Tracev((stderr, "inflate:   length matches trailer\n"));
1230             }
1231 #endif
1232             state->mode = DONE;
1233             /* FALL THROUGH */
1234         case DONE:
1235             ret = Z_STREAM_END;
1236             goto inf_leave;
1237         case BAD:
1238             ret = Z_DATA_ERROR;
1239             goto inf_leave;
1240         case MEM:
1241             return Z_MEM_ERROR;
1242         case SYNC:
1243         default:
1244             return Z_STREAM_ERROR;
1245         }
1246
1247     /*
1248        Return from inflate(), updating the total counts and the check value.
1249        If there was no progress during the inflate() call, return a buffer
1250        error.  Call updatewindow() to create and/or update the window state.
1251        Note: a memory error from inflate() is non-recoverable.
1252      */
1253   inf_leave:
1254     RESTORE();
1255     if (state->wsize || (out != strm->avail_out && state->mode < BAD &&
1256             (state->mode < CHECK || flush != Z_FINISH)))
1257         if (updatewindow(strm, strm->next_out, out - strm->avail_out)) {
1258             state->mode = MEM;
1259             return Z_MEM_ERROR;
1260         }
1261     in -= strm->avail_in;
1262     out -= strm->avail_out;
1263     strm->total_in += in;
1264     strm->total_out += out;
1265     state->total += out;
1266     if (state->wrap && out)
1267         strm->adler = state->check =
1268             UPDATE(state->check, strm->next_out - out, out);
1269     strm->data_type = state->bits + (state->last ? 64 : 0) +
1270                       (state->mode == TYPE ? 128 : 0) +
1271                       (state->mode == LEN_ || state->mode == COPY_ ? 256 : 0);
1272     if (((in == 0 && out == 0) || flush == Z_FINISH) && ret == Z_OK)
1273         ret = Z_BUF_ERROR;
1274     return ret;
1275 }
1276
1277 int ZEXPORT inflateEnd(strm)
1278 z_streamp strm;
1279 {
1280     struct inflate_state FAR *state;
1281     if (strm == Z_NULL || strm->state == Z_NULL || strm->zfree == (free_func)0)
1282         return Z_STREAM_ERROR;
1283     state = (struct inflate_state FAR *)strm->state;
1284     if (state->window != Z_NULL) ZFREE(strm, state->window);
1285     ZFREE(strm, strm->state);
1286     strm->state = Z_NULL;
1287     Tracev((stderr, "inflate: end\n"));
1288     return Z_OK;
1289 }
1290
1291 int ZEXPORT inflateGetDictionary(strm, dictionary, dictLength)
1292 z_streamp strm;
1293 Bytef *dictionary;
1294 uInt *dictLength;
1295 {
1296     struct inflate_state FAR *state;
1297
1298     /* check state */
1299     if (strm == Z_NULL || strm->state == Z_NULL) return Z_STREAM_ERROR;
1300     state = (struct inflate_state FAR *)strm->state;
1301
1302     /* copy dictionary */
1303     if (state->whave && dictionary != Z_NULL) {
1304         zmemcpy(dictionary, state->window + state->wnext,
1305                 state->whave - state->wnext);
1306         zmemcpy(dictionary + state->whave - state->wnext,
1307                 state->window, state->wnext);
1308     }
1309     if (dictLength != Z_NULL)
1310         *dictLength = state->whave;
1311     return Z_OK;
1312 }
1313
1314 int ZEXPORT inflateSetDictionary(strm, dictionary, dictLength)
1315 z_streamp strm;
1316 const Bytef *dictionary;
1317 uInt dictLength;
1318 {
1319     struct inflate_state FAR *state;
1320     unsigned long dictid;
1321     int ret;
1322
1323     /* check state */
1324     if (strm == Z_NULL || strm->state == Z_NULL) return Z_STREAM_ERROR;
1325     state = (struct inflate_state FAR *)strm->state;
1326     if (state->wrap != 0 && state->mode != DICT)
1327         return Z_STREAM_ERROR;
1328
1329     /* check for correct dictionary identifier */
1330     if (state->mode == DICT) {
1331         dictid = adler32(0L, Z_NULL, 0);
1332         dictid = adler32(dictid, dictionary, dictLength);
1333         if (dictid != state->check)
1334             return Z_DATA_ERROR;
1335     }
1336
1337     /* copy dictionary to window using updatewindow(), which will amend the
1338        existing dictionary if appropriate */
1339     ret = updatewindow(strm, dictionary + dictLength, dictLength);
1340     if (ret) {
1341         state->mode = MEM;
1342         return Z_MEM_ERROR;
1343     }
1344     state->havedict = 1;
1345     Tracev((stderr, "inflate:   dictionary set\n"));
1346     return Z_OK;
1347 }
1348
1349 int ZEXPORT inflateGetHeader(strm, head)
1350 z_streamp strm;
1351 gz_headerp head;
1352 {
1353     struct inflate_state FAR *state;
1354
1355     /* check state */
1356     if (strm == Z_NULL || strm->state == Z_NULL) return Z_STREAM_ERROR;
1357     state = (struct inflate_state FAR *)strm->state;
1358     if ((state->wrap & 2) == 0) return Z_STREAM_ERROR;
1359
1360     /* save header structure */
1361     state->head = head;
1362     head->done = 0;
1363     return Z_OK;
1364 }
1365
1366 /*
1367    Search buf[0..len-1] for the pattern: 0, 0, 0xff, 0xff.  Return when found
1368    or when out of input.  When called, *have is the number of pattern bytes
1369    found in order so far, in 0..3.  On return *have is updated to the new
1370    state.  If on return *have equals four, then the pattern was found and the
1371    return value is how many bytes were read including the last byte of the
1372    pattern.  If *have is less than four, then the pattern has not been found
1373    yet and the return value is len.  In the latter case, syncsearch() can be
1374    called again with more data and the *have state.  *have is initialized to
1375    zero for the first call.
1376  */
1377 local unsigned syncsearch(have, buf, len)
1378 unsigned FAR *have;
1379 const unsigned char FAR *buf;
1380 unsigned len;
1381 {
1382     unsigned got;
1383     unsigned next;
1384
1385     got = *have;
1386     next = 0;
1387     while (next < len && got < 4) {
1388         if ((int)(buf[next]) == (got < 2 ? 0 : 0xff))
1389             got++;
1390         else if (buf[next])
1391             got = 0;
1392         else
1393             got = 4 - got;
1394         next++;
1395     }
1396     *have = got;
1397     return next;
1398 }
1399
1400 int ZEXPORT inflateSync(strm)
1401 z_streamp strm;
1402 {
1403     unsigned len;               /* number of bytes to look at or looked at */
1404     unsigned long in, out;      /* temporary to save total_in and total_out */
1405     unsigned char buf[4];       /* to restore bit buffer to byte string */
1406     struct inflate_state FAR *state;
1407
1408     /* check parameters */
1409     if (strm == Z_NULL || strm->state == Z_NULL) return Z_STREAM_ERROR;
1410     state = (struct inflate_state FAR *)strm->state;
1411     if (strm->avail_in == 0 && state->bits < 8) return Z_BUF_ERROR;
1412
1413     /* if first time, start search in bit buffer */
1414     if (state->mode != SYNC) {
1415         state->mode = SYNC;
1416         state->hold <<= state->bits & 7;
1417         state->bits -= state->bits & 7;
1418         len = 0;
1419         while (state->bits >= 8) {
1420             buf[len++] = (unsigned char)(state->hold);
1421             state->hold >>= 8;
1422             state->bits -= 8;
1423         }
1424         state->have = 0;
1425         syncsearch(&(state->have), buf, len);
1426     }
1427
1428     /* search available input */
1429     len = syncsearch(&(state->have), strm->next_in, strm->avail_in);
1430     strm->avail_in -= len;
1431     strm->next_in += len;
1432     strm->total_in += len;
1433
1434     /* return no joy or set up to restart inflate() on a new block */
1435     if (state->have != 4) return Z_DATA_ERROR;
1436     in = strm->total_in;  out = strm->total_out;
1437     inflateReset(strm);
1438     strm->total_in = in;  strm->total_out = out;
1439     state->mode = TYPE;
1440     return Z_OK;
1441 }
1442
1443 /*
1444    Returns true if inflate is currently at the end of a block generated by
1445    Z_SYNC_FLUSH or Z_FULL_FLUSH. This function is used by one PPP
1446    implementation to provide an additional safety check. PPP uses
1447    Z_SYNC_FLUSH but removes the length bytes of the resulting empty stored
1448    block. When decompressing, PPP checks that at the end of input packet,
1449    inflate is waiting for these length bytes.
1450  */
1451 int ZEXPORT inflateSyncPoint(strm)
1452 z_streamp strm;
1453 {
1454     struct inflate_state FAR *state;
1455
1456     if (strm == Z_NULL || strm->state == Z_NULL) return Z_STREAM_ERROR;
1457     state = (struct inflate_state FAR *)strm->state;
1458     return state->mode == STORED && state->bits == 0;
1459 }
1460
1461 int ZEXPORT inflateCopy(dest, source)
1462 z_streamp dest;
1463 z_streamp source;
1464 {
1465     struct inflate_state FAR *state;
1466     struct inflate_state FAR *copy;
1467     unsigned char FAR *window;
1468     unsigned wsize;
1469
1470     /* check input */
1471     if (dest == Z_NULL || source == Z_NULL || source->state == Z_NULL ||
1472         source->zalloc == (alloc_func)0 || source->zfree == (free_func)0)
1473         return Z_STREAM_ERROR;
1474     state = (struct inflate_state FAR *)source->state;
1475
1476     /* allocate space */
1477     copy = (struct inflate_state FAR *)
1478            ZALLOC(source, 1, sizeof(struct inflate_state));
1479     if (copy == Z_NULL) return Z_MEM_ERROR;
1480     window = Z_NULL;
1481     if (state->window != Z_NULL) {
1482         window = (unsigned char FAR *)
1483                  ZALLOC(source, 1U << state->wbits, sizeof(unsigned char));
1484         if (window == Z_NULL) {
1485             ZFREE(source, copy);
1486             return Z_MEM_ERROR;
1487         }
1488     }
1489
1490     /* copy state */
1491     zmemcpy((voidpf)dest, (voidpf)source, sizeof(z_stream));
1492     zmemcpy((voidpf)copy, (voidpf)state, sizeof(struct inflate_state));
1493     if (state->lencode >= state->codes &&
1494         state->lencode <= state->codes + ENOUGH - 1) {
1495         copy->lencode = copy->codes + (state->lencode - state->codes);
1496         copy->distcode = copy->codes + (state->distcode - state->codes);
1497     }
1498     copy->next = copy->codes + (state->next - state->codes);
1499     if (window != Z_NULL) {
1500         wsize = 1U << state->wbits;
1501         zmemcpy(window, state->window, wsize);
1502     }
1503     copy->window = window;
1504     dest->state = (struct internal_state FAR *)copy;
1505     return Z_OK;
1506 }
1507
1508 int ZEXPORT inflateUndermine(strm, subvert)
1509 z_streamp strm;
1510 int subvert;
1511 {
1512     struct inflate_state FAR *state;
1513
1514     if (strm == Z_NULL || strm->state == Z_NULL) return Z_STREAM_ERROR;
1515     state = (struct inflate_state FAR *)strm->state;
1516     state->sane = !subvert;
1517 #ifdef INFLATE_ALLOW_INVALID_DISTANCE_TOOFAR_ARRR
1518     return Z_OK;
1519 #else
1520     state->sane = 1;
1521     return Z_DATA_ERROR;
1522 #endif
1523 }
1524
1525 long ZEXPORT inflateMark(strm)
1526 z_streamp strm;
1527 {
1528     struct inflate_state FAR *state;
1529
1530     if (strm == Z_NULL || strm->state == Z_NULL)
1531         return (long)(((unsigned long)0 - 1) << 16);
1532     state = (struct inflate_state FAR *)strm->state;
1533     return (long)(((unsigned long)((long)state->back)) << 16) +
1534         (state->mode == COPY ? state->length :
1535             (state->mode == MATCH ? state->was - state->length : 0));
1536 }