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