src/gzip/inflate.c

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