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             /* handle error breaks in while */
 865             if (state->mode == BAD) break;
 866
 867             /* build code tables */
 868             state->next = state->codes;
 869             state->lencode = (code const FAR *)(state->next);
 870             state->lenbits = 9;
 871             ret = inflate_table(LENS, state->lens, state->nlen, &(state->next),
 872                                 &(state->lenbits), state->work);
 873             if (ret) {
 874                 strm->msg = (char *)"invalid literal/lengths set";
 875                 state->mode = BAD;
 876                 break;
 877             }
 878             state->distcode = (code const FAR *)(state->next);
 879             state->distbits = 6;
 880             ret = inflate_table(DISTS, state->lens + state->nlen, state->ndist,
 881                             &(state->next), &(state->distbits), state->work);
 882             if (ret) {
 883                 strm->msg = (char *)"invalid distances set";
 884                 state->mode = BAD;
 885                 break;
 886             }
 887             Tracev((stderr, "inflate:       codes ok\n"));
 888             state->mode = LEN;
 889         case LEN:
 890             if (have >= 6 && left >= 258) {
 891                 RESTORE();
 892                 inflate_fast(strm, out);
 893                 LOAD();
 894                 break;
 895             }
 896             for (;;) {
 897                 this = state->lencode[BITS(state->lenbits)];
 898                 if ((unsigned)(this.bits) <= bits) break;
 899                 PULLBYTE();
 900             }
 901             if (this.op && (this.op & 0xf0) == 0) {
 902                 last = this;
 903                 for (;;) {
 904                     this = state->lencode[last.val +
 905                             (BITS(last.bits + last.op) >> last.bits)];
 906                     if ((unsigned)(last.bits + this.bits) <= bits) break;
 907                     PULLBYTE();
 908                 }
 909                 DROPBITS(last.bits);
 910             }
 911             DROPBITS(this.bits);
 912             state->length = (unsigned)this.val;
 913             if ((int)(this.op) == 0) {
 914                 Tracevv((stderr, this.val >= 0x20 && this.val < 0x7f ?
 915                         "inflate:         literal '%c'\n" :
 916                         "inflate:         literal 0x%02x\n", this.val));
 917                 state->mode = LIT;
 918                 break;
 919             }
 920             if (this.op & 32) {
 921                 Tracevv((stderr, "inflate:         end of block\n"));
 922                 state->mode = TYPE;
 923                 break;
 924             }
 925             if (this.op & 64) {
 926                 strm->msg = (char *)"invalid literal/length code";
 927                 state->mode = BAD;
 928                 break;
 929             }
 930             state->extra = (unsigned)(this.op) & 15;
 931             state->mode = LENEXT;
 932         case LENEXT:
 933             if (state->extra) {
 934                 NEEDBITS(state->extra);
 935                 state->length += BITS(state->extra);
 936                 DROPBITS(state->extra);
 937             }
 938             Tracevv((stderr, "inflate:         length %u\n", state->length));
 939             state->mode = DIST;
 940         case DIST:
 941             for (;;) {
 942                 this = state->distcode[BITS(state->distbits)];
 943                 if ((unsigned)(this.bits) <= bits) break;
 944                 PULLBYTE();
 945             }
 946             if ((this.op & 0xf0) == 0) {
 947                 last = this;
 948                 for (;;) {
 949                     this = state->distcode[last.val +
 950                             (BITS(last.bits + last.op) >> last.bits)];
 951                     if ((unsigned)(last.bits + this.bits) <= bits) break;
 952                     PULLBYTE();
 953                 }
 954                 DROPBITS(last.bits);
 955             }
 956             DROPBITS(this.bits);
 957             if (this.op & 64) {
 958                 strm->msg = (char *)"invalid distance code";
 959                 state->mode = BAD;
 960                 break;
 961             }
 962             state->offset = (unsigned)this.val;
 963             state->extra = (unsigned)(this.op) & 15;
 964             state->mode = DISTEXT;
 965         case DISTEXT:
 966             if (state->extra) {
 967                 NEEDBITS(state->extra);
 968                 state->offset += BITS(state->extra);
 969                 DROPBITS(state->extra);
 970             }
 971             if (state->offset > state->whave + out - left) {
 972                 strm->msg = (char *)"invalid distance too far back";
 973                 state->mode = BAD;
 974                 break;
 975             }
 976             Tracevv((stderr, "inflate:         distance %u\n", state->offset));
 977             state->mode = MATCH;
 978         case MATCH:
 979             if (left == 0) goto inf_leave;
 980             copy = out - left;
 981             if (state->offset > copy) {         /* copy from window */
 982                 copy = state->offset - copy;
 983                 if (copy > state->write) {
 984                     copy -= state->write;
 985                     from = state->window + (state->wsize - copy);
 986                 }
 987                 else
 988                     from = state->window + (state->write - copy);
 989                 if (copy > state->length) copy = state->length;
 990             }
 991             else {                              /* copy from output */
 992                 from = put - state->offset;
 993                 copy = state->length;
 994             }
 995             if (copy > left) copy = left;
 996             left -= copy;
 997             state->length -= copy;
 998             do {
 999                 *put++ = *from++;
1000             } while (--copy);
1001             if (state->length == 0) state->mode = LEN;
1002             break;
1003         case LIT:
1004             if (left == 0) goto inf_leave;
1005             *put++ = (unsigned char)(state->length);
1006             left--;
1007             state->mode = LEN;
1008             break;
1009         case CHECK:
1010             if (state->wrap) {
1011                 NEEDBITS(32);
1012                 out -= left;
1013                 strm->total_out += out;
1014                 state->total += out;
1015                 if (out)
1016                     strm->adler = state->check =
1017                         UPDATE(state->check, put - out, out);
1018                 out = left;
1019                 if ((
1020 #ifdef GUNZIP
1021                      state->flags ? hold :
1022 #endif
1023                      REVERSE(hold)) != state->check) {
1024                     strm->msg = (char *)"incorrect data check";
1025                     state->mode = BAD;
1026                     break;
1027                 }
1028                 INITBITS();
1029                 Tracev((stderr, "inflate:   check matches trailer\n"));
1030             }
1031 #ifdef GUNZIP
1032             state->mode = LENGTH;
1033         case LENGTH:
1034             if (state->wrap && state->flags) {
1035                 NEEDBITS(32);
1036                 if (hold != (state->total & 0xffffffffUL)) {
1037                     strm->msg = (char *)"incorrect length check";
1038                     state->mode = BAD;
1039                     break;
1040                 }
1041                 INITBITS();
1042                 Tracev((stderr, "inflate:   length matches trailer\n"));
1043             }
1044 #endif
1045             state->mode = DONE;
1046         case DONE:
1047             ret = Z_STREAM_END;
1048             goto inf_leave;
1049         case BAD:
1050             ret = Z_DATA_ERROR;
1051             goto inf_leave;
1052         case MEM:
1053             return Z_MEM_ERROR;
1054         case SYNC:
1055         default:
1056             return Z_STREAM_ERROR;
1057         }
1058
1059     /*
1060        Return from inflate(), updating the total counts and the check value.
1061        If there was no progress during the inflate() call, return a buffer
1062        error.  Call updatewindow() to create and/or update the window state.
1063        Note: a memory error from inflate() is non-recoverable.
1064      */
1065   inf_leave:
1066     RESTORE();
1067     if (state->wsize || (state->mode < CHECK && out != strm->avail_out))
1068         if (updatewindow(strm, out)) {
1069             state->mode = MEM;
1070             return Z_MEM_ERROR;
1071         }
1072     in -= strm->avail_in;
1073     out -= strm->avail_out;
1074     strm->total_in += in;
1075     strm->total_out += out;
1076     state->total += out;
1077     if (state->wrap && out)
1078         strm->adler = state->check =
1079             UPDATE(state->check, strm->next_out - out, out);
1080     strm->data_type = state->bits + (state->last ? 64 : 0) +
1081                       (state->mode == TYPE ? 128 : 0);
1082     if (((in == 0 && out == 0) || flush == Z_FINISH) && ret == Z_OK)
1083         ret = Z_BUF_ERROR;
1084     return ret;
1085 }
1086
1087 int ZEXPORT inflateEnd(strm)
1088 z_streamp strm;
1089 {
1090     struct inflate_state FAR *state;
1091     if (strm == Z_NULL || strm->state == Z_NULL || strm->zfree == (free_func)0)
1092         return Z_STREAM_ERROR;
1093     state = (struct inflate_state FAR *)strm->state;
1094     if (state->window != Z_NULL) ZFREE(strm, state->window);
1095     ZFREE(strm, strm->state);
1096     strm->state = Z_NULL;
1097     Tracev((stderr, "inflate: end\n"));
1098     return Z_OK;
1099 }
1100
1101 int ZEXPORT inflateSetDictionary(strm, dictionary, dictLength)
1102 z_streamp strm;
1103 const Bytef *dictionary;
1104 uInt dictLength;
1105 {
1106     struct inflate_state FAR *state;
1107     unsigned long id;
1108
1109     /* check state */
1110     if (strm == Z_NULL || strm->state == Z_NULL) return Z_STREAM_ERROR;
1111     state = (struct inflate_state FAR *)strm->state;
1112     if (state->mode != DICT) return Z_STREAM_ERROR;
1113
1114     /* check for correct dictionary id */
1115     id = adler32(0L, Z_NULL, 0);
1116     id = adler32(id, dictionary, dictLength);
1117     if (id != state->check) return Z_DATA_ERROR;
1118
1119     /* copy dictionary to window */
1120     if (updatewindow(strm, strm->avail_out)) {
1121         state->mode = MEM;
1122         return Z_MEM_ERROR;
1123     }
1124     if (dictLength > state->wsize) {
1125         zmemcpy(state->window, dictionary + dictLength - state->wsize,
1126                 state->wsize);
1127         state->whave = state->wsize;
1128     }
1129     else {
1130         zmemcpy(state->window + state->wsize - dictLength, dictionary,
1131                 dictLength);
1132         state->whave = dictLength;
1133     }
1134     state->havedict = 1;
1135     Tracev((stderr, "inflate:   dictionary set\n"));
1136     return Z_OK;
1137 }
1138
1139 /*
1140    Search buf[0..len-1] for the pattern: 0, 0, 0xff, 0xff.  Return when found
1141    or when out of input.  When called, *have is the number of pattern bytes
1142    found in order so far, in 0..3.  On return *have is updated to the new
1143    state.  If on return *have equals four, then the pattern was found and the
1144    return value is how many bytes were read including the last byte of the
1145    pattern.  If *have is less than four, then the pattern has not been found
1146    yet and the return value is len.  In the latter case, syncsearch() can be
1147    called again with more data and the *have state.  *have is initialized to
1148    zero for the first call.
1149  */
1150 local unsigned syncsearch(have, buf, len)
1151 unsigned FAR *have;
1152 unsigned char FAR *buf;
1153 unsigned len;
1154 {
1155     unsigned got;
1156     unsigned next;
1157
1158     got = *have;
1159     next = 0;
1160     while (next < len && got < 4) {
1161         if ((int)(buf[next]) == (got < 2 ? 0 : 0xff))
1162             got++;
1163         else if (buf[next])
1164             got = 0;
1165         else
1166             got = 4 - got;
1167         next++;
1168     }
1169     *have = got;
1170     return next;
1171 }
1172
1173 int ZEXPORT inflateSync(strm)
1174 z_streamp strm;
1175 {
1176     unsigned len;               /* number of bytes to look at or looked at */
1177     unsigned long in, out;      /* temporary to save total_in and total_out */
1178     unsigned char buf[4];       /* to restore bit buffer to byte string */
1179     struct inflate_state FAR *state;
1180
1181     /* check parameters */
1182     if (strm == Z_NULL || strm->state == Z_NULL) return Z_STREAM_ERROR;
1183     state = (struct inflate_state FAR *)strm->state;
1184     if (strm->avail_in == 0 && state->bits < 8) return Z_BUF_ERROR;
1185
1186     /* if first time, start search in bit buffer */
1187     if (state->mode != SYNC) {
1188         state->mode = SYNC;
1189         state->hold <<= state->bits & 7;
1190         state->bits -= state->bits & 7;
1191         len = 0;
1192         while (state->bits >= 8) {
1193             buf[len++] = (unsigned char)(state->hold);
1194             state->hold >>= 8;
1195             state->bits -= 8;
1196         }
1197         state->have = 0;
1198         syncsearch(&(state->have), buf, len);
1199     }
1200
1201     /* search available input */
1202     len = syncsearch(&(state->have), strm->next_in, strm->avail_in);
1203     strm->avail_in -= len;
1204     strm->next_in += len;
1205     strm->total_in += len;
1206
1207     /* return no joy or set up to restart inflate() on a new block */
1208     if (state->have != 4) return Z_DATA_ERROR;
1209     in = strm->total_in;  out = strm->total_out;
1210     inflateReset(strm);
1211     strm->total_in = in;  strm->total_out = out;
1212     state->mode = TYPE;
1213     return Z_OK;
1214 }
1215
1216 /*
1217    Returns true if inflate is currently at the end of a block generated by
1218    Z_SYNC_FLUSH or Z_FULL_FLUSH. This function is used by one PPP
1219    implementation to provide an additional safety check. PPP uses
1220    Z_SYNC_FLUSH but removes the length bytes of the resulting empty stored
1221    block. When decompressing, PPP checks that at the end of input packet,
1222    inflate is waiting for these length bytes.
1223  */
1224 int ZEXPORT inflateSyncPoint(strm)
1225 z_streamp strm;
1226 {
1227     struct inflate_state FAR *state;
1228
1229     if (strm == Z_NULL || strm->state == Z_NULL) return Z_STREAM_ERROR;
1230     state = (struct inflate_state FAR *)strm->state;
1231     return state->mode == STORED && state->bits == 0;
1232 }
1233
1234 int ZEXPORT inflateCopy(dest, source)
1235 z_streamp dest;
1236 z_streamp source;
1237 {
1238     struct inflate_state FAR *state;
1239     struct inflate_state FAR *copy;
1240     unsigned char FAR *window;
1241
1242     /* check input */
1243     if (dest == Z_NULL || source == Z_NULL || source->state == Z_NULL ||
1244         source->zalloc == (alloc_func)0 || source->zfree == (free_func)0)
1245         return Z_STREAM_ERROR;
1246     state = (struct inflate_state FAR *)source->state;
1247
1248     /* allocate space */
1249     copy = (struct inflate_state FAR *)
1250            ZALLOC(source, 1, sizeof(struct inflate_state));
1251     if (copy == Z_NULL) return Z_MEM_ERROR;
1252     window = Z_NULL;
1253     if (state->window != Z_NULL) {
1254         window = (unsigned char FAR *)
1255                  ZALLOC(source, 1U << state->wbits, sizeof(unsigned char));
1256         if (window == Z_NULL) {
1257             ZFREE(source, copy);
1258             return Z_MEM_ERROR;
1259         }
1260     }
1261
1262     /* copy state */
1263     *dest = *source;
1264     *copy = *state;
1265     copy->lencode = copy->codes + (state->lencode - state->codes);
1266     copy->distcode = copy->codes + (state->distcode - state->codes);
1267     copy->next = copy->codes + (state->next - state->codes);
1268     if (window != Z_NULL)
1269         zmemcpy(window, state->window, 1U << state->wbits);
1270     copy->window = window;
1271     dest->state = (voidpf)copy;
1272     return Z_OK;
1273 }