inflate.c

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