zlib/inflate.c

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