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