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