Back to index

tetex-bin  3.0
inflate.c
Go to the documentation of this file.
00001 /* inflate.c -- zlib decompression
00002  * Copyright (C) 1995-2003 Mark Adler
00003  * For conditions of distribution and use, see copyright notice in zlib.h
00004  */
00005 
00006 /*
00007  * Change history:
00008  *
00009  * 1.2.beta0    24 Nov 2002
00010  * - First version -- complete rewrite of inflate to simplify code, avoid
00011  *   creation of window when not needed, minimize use of window when it is
00012  *   needed, make inffast.c even faster, implement gzip decoding, and to
00013  *   improve code readability and style over the previous zlib inflate code
00014  *
00015  * 1.2.beta1    25 Nov 2002
00016  * - Use pointers for available input and output checking in inffast.c
00017  * - Remove input and output counters in inffast.c
00018  * - Change inffast.c entry and loop from avail_in >= 7 to >= 6
00019  * - Remove unnecessary second byte pull from length extra in inffast.c
00020  * - Unroll direct copy to three copies per loop in inffast.c
00021  *
00022  * 1.2.beta2    4 Dec 2002
00023  * - Change external routine names to reduce potential conflicts
00024  * - Correct filename to inffixed.h for fixed tables in inflate.c
00025  * - Make hbuf[] unsigned char to match parameter type in inflate.c
00026  * - Change strm->next_out[-state->offset] to *(strm->next_out - state->offset)
00027  *   to avoid negation problem on Alphas (64 bit) in inflate.c
00028  *
00029  * 1.2.beta3    22 Dec 2002
00030  * - Add comments on state->bits assertion in inffast.c
00031  * - Add comments on op field in inftrees.h
00032  * - Fix bug in reuse of allocated window after inflateReset()
00033  * - Remove bit fields--back to byte structure for speed
00034  * - Remove distance extra == 0 check in inflate_fast()--only helps for lengths
00035  * - Change post-increments to pre-increments in inflate_fast(), PPC biased?
00036  * - Add compile time option, POSTINC, to use post-increments instead (Intel?)
00037  * - Make MATCH copy in inflate() much faster for when inflate_fast() not used
00038  * - Use local copies of stream next and avail values, as well as local bit
00039  *   buffer and bit count in inflate()--for speed when inflate_fast() not used
00040  *
00041  * 1.2.beta4    1 Jan 2003
00042  * - Split ptr - 257 statements in inflate_table() to avoid compiler warnings
00043  * - Move a comment on output buffer sizes from inffast.c to inflate.c
00044  * - Add comments in inffast.c to introduce the inflate_fast() routine
00045  * - Rearrange window copies in inflate_fast() for speed and simplification
00046  * - Unroll last copy for window match in inflate_fast()
00047  * - Use local copies of window variables in inflate_fast() for speed
00048  * - Pull out common write == 0 case for speed in inflate_fast()
00049  * - Make op and len in inflate_fast() unsigned for consistency
00050  * - Add FAR to lcode and dcode declarations in inflate_fast()
00051  * - Simplified bad distance check in inflate_fast()
00052  * - Added inflateBackInit(), inflateBack(), and inflateBackEnd() in new
00053  *   source file infback.c to provide a call-back interface to inflate for
00054  *   programs like gzip and unzip -- uses window as output buffer to avoid
00055  *   window copying
00056  *
00057  * 1.2.beta5    1 Jan 2003
00058  * - Improved inflateBack() interface to allow the caller to provide initial
00059  *   input in strm.
00060  * - Fixed stored blocks bug in inflateBack()
00061  *
00062  * 1.2.beta6    4 Jan 2003
00063  * - Added comments in inffast.c on effectiveness of POSTINC
00064  * - Typecasting all around to reduce compiler warnings
00065  * - Changed loops from while (1) or do {} while (1) to for (;;), again to
00066  *   make compilers happy
00067  * - Changed type of window in inflateBackInit() to unsigned char *
00068  *
00069  * 1.2.beta7    27 Jan 2003
00070  * - Changed many types to unsigned or unsigned short to avoid warnings
00071  * - Added inflateCopy() function
00072  *
00073  * 1.2.0        9 Mar 2003
00074  * - Changed inflateBack() interface to provide separate opaque descriptors
00075  *   for the in() and out() functions
00076  * - Changed inflateBack() argument and in_func typedef to swap the length
00077  *   and buffer address return values for the input function
00078  * - Check next_in and next_out for Z_NULL on entry to inflate()
00079  *
00080  * The history for versions after 1.2.0 are in ChangeLog in zlib distribution.
00081  */
00082 
00083 #include "zutil.h"
00084 #include "inftrees.h"
00085 #include "inflate.h"
00086 #include "inffast.h"
00087 
00088 #ifdef MAKEFIXED
00089 #  ifndef BUILDFIXED
00090 #    define BUILDFIXED
00091 #  endif
00092 #endif
00093 
00094 /* function prototypes */
00095 local void fixedtables OF((struct inflate_state FAR *state));
00096 local int updatewindow OF((z_streamp strm, unsigned out));
00097 #ifdef BUILDFIXED
00098    void makefixed OF((void));
00099 #endif
00100 local unsigned syncsearch OF((unsigned FAR *have, unsigned char FAR *buf,
00101                               unsigned len));
00102 
00103 int ZEXPORT inflateReset(strm)
00104 z_streamp strm;
00105 {
00106     struct inflate_state FAR *state;
00107 
00108     if (strm == Z_NULL || strm->state == Z_NULL) return Z_STREAM_ERROR;
00109     state = (struct inflate_state FAR *)strm->state;
00110     strm->total_in = strm->total_out = state->total = 0;
00111     strm->msg = Z_NULL;
00112     state->mode = HEAD;
00113     state->last = 0;
00114     state->havedict = 0;
00115     state->wsize = 0;
00116     state->whave = 0;
00117     state->hold = 0;
00118     state->bits = 0;
00119     state->lencode = state->distcode = state->next = state->codes;
00120     Tracev((stderr, "inflate: reset\n"));
00121     return Z_OK;
00122 }
00123 
00124 int ZEXPORT inflateInit2_(strm, windowBits, version, stream_size)
00125 z_streamp strm;
00126 int windowBits;
00127 const char *version;
00128 int stream_size;
00129 {
00130     struct inflate_state FAR *state;
00131 
00132     if (version == Z_NULL || version[0] != ZLIB_VERSION[0] ||
00133         stream_size != (int)(sizeof(z_stream)))
00134         return Z_VERSION_ERROR;
00135     if (strm == Z_NULL) return Z_STREAM_ERROR;
00136     strm->msg = Z_NULL;                 /* in case we return an error */
00137     if (strm->zalloc == (alloc_func)0) {
00138         strm->zalloc = zcalloc;
00139         strm->opaque = (voidpf)0;
00140     }
00141     if (strm->zfree == (free_func)0) strm->zfree = zcfree;
00142     state = (struct inflate_state FAR *)
00143             ZALLOC(strm, 1, sizeof(struct inflate_state));
00144     if (state == Z_NULL) return Z_MEM_ERROR;
00145     Tracev((stderr, "inflate: allocated\n"));
00146     strm->state = (voidpf)state;
00147     if (windowBits < 0) {
00148         state->wrap = 0;
00149         windowBits = -windowBits;
00150     }
00151     else {
00152         state->wrap = (windowBits >> 4) + 1;
00153 #ifdef GUNZIP
00154         if (windowBits < 48) windowBits &= 15;
00155 #endif
00156     }
00157     if (windowBits < 8 || windowBits > 15) {
00158         ZFREE(strm, state);
00159         strm->state = Z_NULL;
00160         return Z_STREAM_ERROR;
00161     }
00162     state->wbits = (unsigned)windowBits;
00163     state->window = Z_NULL;
00164     return inflateReset(strm);
00165 }
00166 
00167 int ZEXPORT inflateInit_(strm, version, stream_size)
00168 z_streamp strm;
00169 const char *version;
00170 int stream_size;
00171 {
00172     return inflateInit2_(strm, DEF_WBITS, version, stream_size);
00173 }
00174 
00175 /*
00176    Return state with length and distance decoding tables and index sizes set to
00177    fixed code decoding.  Normally this returns fixed tables from inffixed.h.
00178    If BUILDFIXED is defined, then instead this routine builds the tables the
00179    first time it's called, and returns those tables the first time and
00180    thereafter.  This reduces the size of the code by about 2K bytes, in
00181    exchange for a little execution time.  However, BUILDFIXED should not be
00182    used for threaded applications, since the rewriting of the tables and virgin
00183    may not be thread-safe.
00184  */
00185 local void fixedtables(state)
00186 struct inflate_state FAR *state;
00187 {
00188 #ifdef BUILDFIXED
00189     static int virgin = 1;
00190     static code *lenfix, *distfix;
00191     static code fixed[544];
00192 
00193     /* build fixed huffman tables if first call (may not be thread safe) */
00194     if (virgin) {
00195         unsigned sym, bits;
00196         static code *next;
00197 
00198         /* literal/length table */
00199         sym = 0;
00200         while (sym < 144) state->lens[sym++] = 8;
00201         while (sym < 256) state->lens[sym++] = 9;
00202         while (sym < 280) state->lens[sym++] = 7;
00203         while (sym < 288) state->lens[sym++] = 8;
00204         next = fixed;
00205         lenfix = next;
00206         bits = 9;
00207         inflate_table(LENS, state->lens, 288, &(next), &(bits), state->work);
00208 
00209         /* distance table */
00210         sym = 0;
00211         while (sym < 32) state->lens[sym++] = 5;
00212         distfix = next;
00213         bits = 5;
00214         inflate_table(DISTS, state->lens, 32, &(next), &(bits), state->work);
00215 
00216         /* do this just once */
00217         virgin = 0;
00218     }
00219 #else /* !BUILDFIXED */
00220 #   include "inffixed.h"
00221 #endif /* BUILDFIXED */
00222     state->lencode = lenfix;
00223     state->lenbits = 9;
00224     state->distcode = distfix;
00225     state->distbits = 5;
00226 }
00227 
00228 #ifdef MAKEFIXED
00229 #include <stdio.h>
00230 
00231 /*
00232    Write out the inffixed.h that is #include'd above.  Defining MAKEFIXED also
00233    defines BUILDFIXED, so the tables are built on the fly.  makefixed() writes
00234    those tables to stdout, which would be piped to inffixed.h.  A small program
00235    can simply call makefixed to do this:
00236 
00237     void makefixed(void);
00238 
00239     int main(void)
00240     {
00241         makefixed();
00242         return 0;
00243     }
00244 
00245    Then that can be linked with zlib built with MAKEFIXED defined and run:
00246 
00247     a.out > inffixed.h
00248  */
00249 void makefixed()
00250 {
00251     unsigned low, size;
00252     struct inflate_state state;
00253 
00254     fixedtables(&state);
00255     puts("    /* inffixed.h -- table for decoding fixed codes");
00256     puts("     * Generated automatically by makefixed().");
00257     puts("     */");
00258     puts("");
00259     puts("    /* WARNING: this file should *not* be used by applications.");
00260     puts("       It is part of the implementation of this library and is");
00261     puts("       subject to change. Applications should only use zlib.h.");
00262     puts("     */");
00263     puts("");
00264     size = 1U << 9;
00265     printf("    static const code lenfix[%u] = {", size);
00266     low = 0;
00267     for (;;) {
00268         if ((low % 7) == 0) printf("\n        ");
00269         printf("{%u,%u,%d}", state.lencode[low].op, state.lencode[low].bits,
00270                state.lencode[low].val);
00271         if (++low == size) break;
00272         putchar(',');
00273     }
00274     puts("\n    };");
00275     size = 1U << 5;
00276     printf("\n    static const code distfix[%u] = {", size);
00277     low = 0;
00278     for (;;) {
00279         if ((low % 6) == 0) printf("\n        ");
00280         printf("{%u,%u,%d}", state.distcode[low].op, state.distcode[low].bits,
00281                state.distcode[low].val);
00282         if (++low == size) break;
00283         putchar(',');
00284     }
00285     puts("\n    };");
00286 }
00287 #endif /* MAKEFIXED */
00288 
00289 /*
00290    Update the window with the last wsize (normally 32K) bytes written before
00291    returning.  If window does not exist yet, create it.  This is only called
00292    when a window is already in use, or when output has been written during this
00293    inflate call, but the end of the deflate stream has not been reached yet.
00294    It is also called to create a window for dictionary data when a dictionary
00295    is loaded.
00296 
00297    Providing output buffers larger than 32K to inflate() should provide a speed
00298    advantage, since only the last 32K of output is copied to the sliding window
00299    upon return from inflate(), and since all distances after the first 32K of
00300    output will fall in the output data, making match copies simpler and faster.
00301    The advantage may be dependent on the size of the processor's data caches.
00302  */
00303 local int updatewindow(strm, out)
00304 z_streamp strm;
00305 unsigned out;
00306 {
00307     struct inflate_state FAR *state;
00308     unsigned copy, dist;
00309 
00310     state = (struct inflate_state FAR *)strm->state;
00311 
00312     /* if it hasn't been done already, allocate space for the window */
00313     if (state->window == Z_NULL) {
00314         state->window = (unsigned char FAR *)
00315                         ZALLOC(strm, 1U << state->wbits,
00316                                sizeof(unsigned char));
00317         if (state->window == Z_NULL) return 1;
00318     }
00319 
00320     /* if window not in use yet, initialize */
00321     if (state->wsize == 0) {
00322         state->wsize = 1U << state->wbits;
00323         state->write = 0;
00324         state->whave = 0;
00325     }
00326 
00327     /* copy state->wsize or less output bytes into the circular window */
00328     copy = out - strm->avail_out;
00329     if (copy >= state->wsize) {
00330         zmemcpy(state->window, strm->next_out - state->wsize, state->wsize);
00331         state->write = 0;
00332         state->whave = state->wsize;
00333     }
00334     else {
00335         dist = state->wsize - state->write;
00336         if (dist > copy) dist = copy;
00337         zmemcpy(state->window + state->write, strm->next_out - copy, dist);
00338         copy -= dist;
00339         if (copy) {
00340             zmemcpy(state->window, strm->next_out - copy, copy);
00341             state->write = copy;
00342             state->whave = state->wsize;
00343         }
00344         else {
00345             state->write += dist;
00346             if (state->write == state->wsize) state->write = 0;
00347             if (state->whave < state->wsize) state->whave += dist;
00348         }
00349     }
00350     return 0;
00351 }
00352 
00353 /* Macros for inflate(): */
00354 
00355 /* check function to use adler32() for zlib or crc32() for gzip */
00356 #ifdef GUNZIP
00357 #  define UPDATE(check, buf, len) \
00358     (state->flags ? crc32(check, buf, len) : adler32(check, buf, len))
00359 #else
00360 #  define UPDATE(check, buf, len) adler32(check, buf, len)
00361 #endif
00362 
00363 /* check macros for header crc */
00364 #ifdef GUNZIP
00365 #  define CRC2(check, word) \
00366     do { \
00367         hbuf[0] = (unsigned char)(word); \
00368         hbuf[1] = (unsigned char)((word) >> 8); \
00369         check = crc32(check, hbuf, 2); \
00370     } while (0)
00371 
00372 #  define CRC4(check, word) \
00373     do { \
00374         hbuf[0] = (unsigned char)(word); \
00375         hbuf[1] = (unsigned char)((word) >> 8); \
00376         hbuf[2] = (unsigned char)((word) >> 16); \
00377         hbuf[3] = (unsigned char)((word) >> 24); \
00378         check = crc32(check, hbuf, 4); \
00379     } while (0)
00380 #endif
00381 
00382 /* Load registers with state in inflate() for speed */
00383 #define LOAD() \
00384     do { \
00385         put = strm->next_out; \
00386         left = strm->avail_out; \
00387         next = strm->next_in; \
00388         have = strm->avail_in; \
00389         hold = state->hold; \
00390         bits = state->bits; \
00391     } while (0)
00392 
00393 /* Restore state from registers in inflate() */
00394 #define RESTORE() \
00395     do { \
00396         strm->next_out = put; \
00397         strm->avail_out = left; \
00398         strm->next_in = next; \
00399         strm->avail_in = have; \
00400         state->hold = hold; \
00401         state->bits = bits; \
00402     } while (0)
00403 
00404 /* Clear the input bit accumulator */
00405 #define INITBITS() \
00406     do { \
00407         hold = 0; \
00408         bits = 0; \
00409     } while (0)
00410 
00411 /* Get a byte of input into the bit accumulator, or return from inflate()
00412    if there is no input available. */
00413 #define PULLBYTE() \
00414     do { \
00415         if (have == 0) goto inf_leave; \
00416         have--; \
00417         hold += (unsigned long)(*next++) << bits; \
00418         bits += 8; \
00419     } while (0)
00420 
00421 /* Assure that there are at least n bits in the bit accumulator.  If there is
00422    not enough available input to do that, then return from inflate(). */
00423 #define NEEDBITS(n) \
00424     do { \
00425         while (bits < (unsigned)(n)) \
00426             PULLBYTE(); \
00427     } while (0)
00428 
00429 /* Return the low n bits of the bit accumulator (n < 16) */
00430 #define BITS(n) \
00431     ((unsigned)hold & ((1U << (n)) - 1))
00432 
00433 /* Remove n bits from the bit accumulator */
00434 #define DROPBITS(n) \
00435     do { \
00436         hold >>= (n); \
00437         bits -= (unsigned)(n); \
00438     } while (0)
00439 
00440 /* Remove zero to seven bits as needed to go to a byte boundary */
00441 #define BYTEBITS() \
00442     do { \
00443         hold >>= bits & 7; \
00444         bits -= bits & 7; \
00445     } while (0)
00446 
00447 /* Reverse the bytes in a 32-bit value */
00448 #define REVERSE(q) \
00449     ((((q) >> 24) & 0xff) + (((q) >> 8) & 0xff00) + \
00450      (((q) & 0xff00) << 8) + (((q) & 0xff) << 24))
00451 
00452 /*
00453    inflate() uses a state machine to process as much input data and generate as
00454    much output data as possible before returning.  The state machine is
00455    structured roughly as follows:
00456 
00457     for (;;) switch (state) {
00458     ...
00459     case STATEn:
00460         if (not enough input data or output space to make progress)
00461             return;
00462         ... make progress ...
00463         state = STATEm;
00464         break;
00465     ...
00466     }
00467 
00468    so when inflate() is called again, the same case is attempted again, and
00469    if the appropriate resources are provided, the machine proceeds to the
00470    next state.  The NEEDBITS() macro is usually the way the state evaluates
00471    whether it can proceed or should return.  NEEDBITS() does the return if
00472    the requested bits are not available.  The typical use of the BITS macros
00473    is:
00474 
00475         NEEDBITS(n);
00476         ... do something with BITS(n) ...
00477         DROPBITS(n);
00478 
00479    where NEEDBITS(n) either returns from inflate() if there isn't enough
00480    input left to load n bits into the accumulator, or it continues.  BITS(n)
00481    gives the low n bits in the accumulator.  When done, DROPBITS(n) drops
00482    the low n bits off the accumulator.  INITBITS() clears the accumulator
00483    and sets the number of available bits to zero.  BYTEBITS() discards just
00484    enough bits to put the accumulator on a byte boundary.  After BYTEBITS()
00485    and a NEEDBITS(8), then BITS(8) would return the next byte in the stream.
00486 
00487    NEEDBITS(n) uses PULLBYTE() to get an available byte of input, or to return
00488    if there is no input available.  The decoding of variable length codes uses
00489    PULLBYTE() directly in order to pull just enough bytes to decode the next
00490    code, and no more.
00491 
00492    Some states loop until they get enough input, making sure that enough
00493    state information is maintained to continue the loop where it left off
00494    if NEEDBITS() returns in the loop.  For example, want, need, and keep
00495    would all have to actually be part of the saved state in case NEEDBITS()
00496    returns:
00497 
00498     case STATEw:
00499         while (want < need) {
00500             NEEDBITS(n);
00501             keep[want++] = BITS(n);
00502             DROPBITS(n);
00503         }
00504         state = STATEx;
00505     case STATEx:
00506 
00507    As shown above, if the next state is also the next case, then the break
00508    is omitted.
00509 
00510    A state may also return if there is not enough output space available to
00511    complete that state.  Those states are copying stored data, writing a
00512    literal byte, and copying a matching string.
00513 
00514    When returning, a "goto inf_leave" is used to update the total counters,
00515    update the check value, and determine whether any progress has been made
00516    during that inflate() call in order to return the proper return code.
00517    Progress is defined as a change in either strm->avail_in or strm->avail_out.
00518    When there is a window, goto inf_leave will update the window with the last
00519    output written.  If a goto inf_leave occurs in the middle of decompression
00520    and there is no window currently, goto inf_leave will create one and copy
00521    output to the window for the next call of inflate().
00522 
00523    In this implementation, the flush parameter of inflate() only affects the
00524    return code (per zlib.h).  inflate() always writes as much as possible to
00525    strm->next_out, given the space available and the provided input--the effect
00526    documented in zlib.h of Z_SYNC_FLUSH.  Furthermore, inflate() always defers
00527    the allocation of and copying into a sliding window until necessary, which
00528    provides the effect documented in zlib.h for Z_FINISH when the entire input
00529    stream available.  So the only thing the flush parameter actually does is:
00530    when flush is set to Z_FINISH, inflate() cannot return Z_OK.  Instead it
00531    will return Z_BUF_ERROR if it has not reached the end of the stream.
00532  */
00533 
00534 int ZEXPORT inflate(strm, flush)
00535 z_streamp strm;
00536 int flush;
00537 {
00538     struct inflate_state FAR *state;
00539     unsigned char FAR *next;    /* next input */
00540     unsigned char FAR *put;     /* next output */
00541     unsigned have, left;        /* available input and output */
00542     unsigned long hold;         /* bit buffer */
00543     unsigned bits;              /* bits in bit buffer */
00544     unsigned in, out;           /* save starting available input and output */
00545     unsigned copy;              /* number of stored or match bytes to copy */
00546     unsigned char FAR *from;    /* where to copy match bytes from */
00547     code this;                  /* current decoding table entry */
00548     code last;                  /* parent table entry */
00549     unsigned len;               /* length to copy for repeats, bits to drop */
00550     int ret;                    /* return code */
00551 #ifdef GUNZIP
00552     unsigned char hbuf[4];      /* buffer for gzip header crc calculation */
00553 #endif
00554     static const unsigned short order[19] = /* permutation of code lengths */
00555         {16, 17, 18, 0, 8, 7, 9, 6, 10, 5, 11, 4, 12, 3, 13, 2, 14, 1, 15};
00556 
00557     if (strm == Z_NULL || strm->state == Z_NULL || strm->next_out == Z_NULL ||
00558         (strm->next_in == Z_NULL && strm->avail_in != 0))
00559         return Z_STREAM_ERROR;
00560 
00561     state = (struct inflate_state FAR *)strm->state;
00562     if (state->mode == TYPE) state->mode = TYPEDO;      /* skip check */
00563     LOAD();
00564     in = have;
00565     out = left;
00566     ret = Z_OK;
00567     for (;;)
00568         switch (state->mode) {
00569         case HEAD:
00570             if (state->wrap == 0) {
00571                 state->mode = TYPEDO;
00572                 break;
00573             }
00574             NEEDBITS(16);
00575 #ifdef GUNZIP
00576             if ((state->wrap & 2) && hold == 0x8b1f) {  /* gzip header */
00577                 state->check = crc32(0L, Z_NULL, 0);
00578                 CRC2(state->check, hold);
00579                 INITBITS();
00580                 state->mode = FLAGS;
00581                 break;
00582             }
00583             state->flags = 0;           /* expect zlib header */
00584             if (!(state->wrap & 1) ||   /* check if zlib header allowed */
00585 #else
00586             if (
00587 #endif
00588                 ((BITS(8) << 8) + (hold >> 8)) % 31) {
00589                 strm->msg = (char *)"incorrect header check";
00590                 state->mode = BAD;
00591                 break;
00592             }
00593             if (BITS(4) != Z_DEFLATED) {
00594                 strm->msg = (char *)"unknown compression method";
00595                 state->mode = BAD;
00596                 break;
00597             }
00598             DROPBITS(4);
00599             if (BITS(4) + 8 > state->wbits) {
00600                 strm->msg = (char *)"invalid window size";
00601                 state->mode = BAD;
00602                 break;
00603             }
00604             Tracev((stderr, "inflate:   zlib header ok\n"));
00605             strm->adler = state->check = adler32(0L, Z_NULL, 0);
00606             state->mode = hold & 0x200 ? DICTID : TYPE;
00607             INITBITS();
00608             break;
00609 #ifdef GUNZIP
00610         case FLAGS:
00611             NEEDBITS(16);
00612             state->flags = (int)(hold);
00613             if ((state->flags & 0xff) != Z_DEFLATED) {
00614                 strm->msg = (char *)"unknown compression method";
00615                 state->mode = BAD;
00616                 break;
00617             }
00618             if (state->flags & 0xe000) {
00619                 strm->msg = (char *)"unknown header flags set";
00620                 state->mode = BAD;
00621                 break;
00622             }
00623             if (state->flags & 0x0200) CRC2(state->check, hold);
00624             INITBITS();
00625             state->mode = TIME;
00626         case TIME:
00627             NEEDBITS(32);
00628             if (state->flags & 0x0200) CRC4(state->check, hold);
00629             INITBITS();
00630             state->mode = OS;
00631         case OS:
00632             NEEDBITS(16);
00633             if (state->flags & 0x0200) CRC2(state->check, hold);
00634             INITBITS();
00635             state->mode = EXLEN;
00636         case EXLEN:
00637             if (state->flags & 0x0400) {
00638                 NEEDBITS(16);
00639                 state->length = (unsigned)(hold);
00640                 if (state->flags & 0x0200) CRC2(state->check, hold);
00641                 INITBITS();
00642             }
00643             state->mode = EXTRA;
00644         case EXTRA:
00645             if (state->flags & 0x0400) {
00646                 copy = state->length;
00647                 if (copy > have) copy = have;
00648                 if (copy) {
00649                     if (state->flags & 0x0200)
00650                         state->check = crc32(state->check, next, copy);
00651                     have -= copy;
00652                     next += copy;
00653                     state->length -= copy;
00654                 }
00655                 if (state->length) goto inf_leave;
00656             }
00657             state->mode = NAME;
00658         case NAME:
00659             if (state->flags & 0x0800) {
00660                 if (have == 0) goto inf_leave;
00661                 copy = 0;
00662                 do {
00663                     len = (unsigned)(next[copy++]);
00664                 } while (len && copy < have);
00665                 if (state->flags & 0x02000)
00666                     state->check = crc32(state->check, next, copy);
00667                 have -= copy;
00668                 next += copy;
00669                 if (len) goto inf_leave;
00670             }
00671             state->mode = COMMENT;
00672         case COMMENT:
00673             if (state->flags & 0x1000) {
00674                 if (have == 0) goto inf_leave;
00675                 copy = 0;
00676                 do {
00677                     len = (unsigned)(next[copy++]);
00678                 } while (len && copy < have);
00679                 if (state->flags & 0x02000)
00680                     state->check = crc32(state->check, next, copy);
00681                 have -= copy;
00682                 next += copy;
00683                 if (len) goto inf_leave;
00684             }
00685             state->mode = HCRC;
00686         case HCRC:
00687             if (state->flags & 0x0200) {
00688                 NEEDBITS(16);
00689                 if (hold != (state->check & 0xffff)) {
00690                     strm->msg = (char *)"header crc mismatch";
00691                     state->mode = BAD;
00692                     break;
00693                 }
00694                 INITBITS();
00695             }
00696             strm->adler = state->check = crc32(0L, Z_NULL, 0);
00697             state->mode = TYPE;
00698             break;
00699 #endif
00700         case DICTID:
00701             NEEDBITS(32);
00702             strm->adler = state->check = REVERSE(hold);
00703             INITBITS();
00704             state->mode = DICT;
00705         case DICT:
00706             if (state->havedict == 0) {
00707                 RESTORE();
00708                 return Z_NEED_DICT;
00709             }
00710             strm->adler = state->check = adler32(0L, Z_NULL, 0);
00711             state->mode = TYPE;
00712         case TYPE:
00713             if (flush == Z_BLOCK) goto inf_leave;
00714         case TYPEDO:
00715             if (state->last) {
00716                 BYTEBITS();
00717                 state->mode = CHECK;
00718                 break;
00719             }
00720             NEEDBITS(3);
00721             state->last = BITS(1);
00722             DROPBITS(1);
00723             switch (BITS(2)) {
00724             case 0:                             /* stored block */
00725                 Tracev((stderr, "inflate:     stored block%s\n",
00726                         state->last ? " (last)" : ""));
00727                 state->mode = STORED;
00728                 break;
00729             case 1:                             /* fixed block */
00730                 fixedtables(state);
00731                 Tracev((stderr, "inflate:     fixed codes block%s\n",
00732                         state->last ? " (last)" : ""));
00733                 state->mode = LEN;              /* decode codes */
00734                 break;
00735             case 2:                             /* dynamic block */
00736                 Tracev((stderr, "inflate:     dynamic codes block%s\n",
00737                         state->last ? " (last)" : ""));
00738                 state->mode = TABLE;
00739                 break;
00740             case 3:
00741                 strm->msg = (char *)"invalid block type";
00742                 state->mode = BAD;
00743             }
00744             DROPBITS(2);
00745             break;
00746         case STORED:
00747             BYTEBITS();                         /* go to byte boundary */
00748             NEEDBITS(32);
00749             if ((hold & 0xffff) != ((hold >> 16) ^ 0xffff)) {
00750                 strm->msg = (char *)"invalid stored block lengths";
00751                 state->mode = BAD;
00752                 break;
00753             }
00754             state->length = (unsigned)hold & 0xffff;
00755             Tracev((stderr, "inflate:       stored length %u\n",
00756                     state->length));
00757             INITBITS();
00758             state->mode = COPY;
00759         case COPY:
00760             copy = state->length;
00761             if (copy) {
00762                 if (copy > have) copy = have;
00763                 if (copy > left) copy = left;
00764                 if (copy == 0) goto inf_leave;
00765                 zmemcpy(put, next, copy);
00766                 have -= copy;
00767                 next += copy;
00768                 left -= copy;
00769                 put += copy;
00770                 state->length -= copy;
00771                 break;
00772             }
00773             Tracev((stderr, "inflate:       stored end\n"));
00774             state->mode = TYPE;
00775             break;
00776         case TABLE:
00777             NEEDBITS(14);
00778             state->nlen = BITS(5) + 257;
00779             DROPBITS(5);
00780             state->ndist = BITS(5) + 1;
00781             DROPBITS(5);
00782             state->ncode = BITS(4) + 4;
00783             DROPBITS(4);
00784 #ifndef PKZIP_BUG_WORKAROUND
00785             if (state->nlen > 286 || state->ndist > 30) {
00786                 strm->msg = (char *)"too many length or distance symbols";
00787                 state->mode = BAD;
00788                 break;
00789             }
00790 #endif
00791             Tracev((stderr, "inflate:       table sizes ok\n"));
00792             state->have = 0;
00793             state->mode = LENLENS;
00794         case LENLENS:
00795             while (state->have < state->ncode) {
00796                 NEEDBITS(3);
00797                 state->lens[order[state->have++]] = (unsigned short)BITS(3);
00798                 DROPBITS(3);
00799             }
00800             while (state->have < 19)
00801                 state->lens[order[state->have++]] = 0;
00802             state->next = state->codes;
00803             state->lencode = (code const FAR *)(state->next);
00804             state->lenbits = 7;
00805             ret = inflate_table(CODES, state->lens, 19, &(state->next),
00806                                 &(state->lenbits), state->work);
00807             if (ret) {
00808                 strm->msg = (char *)"invalid code lengths set";
00809                 state->mode = BAD;
00810                 break;
00811             }
00812             Tracev((stderr, "inflate:       code lengths ok\n"));
00813             state->have = 0;
00814             state->mode = CODELENS;
00815         case CODELENS:
00816             while (state->have < state->nlen + state->ndist) {
00817                 for (;;) {
00818                     this = state->lencode[BITS(state->lenbits)];
00819                     if ((unsigned)(this.bits) <= bits) break;
00820                     PULLBYTE();
00821                 }
00822                 if (this.val < 16) {
00823                     NEEDBITS(this.bits);
00824                     DROPBITS(this.bits);
00825                     state->lens[state->have++] = this.val;
00826                 }
00827                 else {
00828                     if (this.val == 16) {
00829                         NEEDBITS(this.bits + 2);
00830                         DROPBITS(this.bits);
00831                         if (state->have == 0) {
00832                             strm->msg = (char *)"invalid bit length repeat";
00833                             state->mode = BAD;
00834                             break;
00835                         }
00836                         len = state->lens[state->have - 1];
00837                         copy = 3 + BITS(2);
00838                         DROPBITS(2);
00839                     }
00840                     else if (this.val == 17) {
00841                         NEEDBITS(this.bits + 3);
00842                         DROPBITS(this.bits);
00843                         len = 0;
00844                         copy = 3 + BITS(3);
00845                         DROPBITS(3);
00846                     }
00847                     else {
00848                         NEEDBITS(this.bits + 7);
00849                         DROPBITS(this.bits);
00850                         len = 0;
00851                         copy = 11 + BITS(7);
00852                         DROPBITS(7);
00853                     }
00854                     if (state->have + copy > state->nlen + state->ndist) {
00855                         strm->msg = (char *)"invalid bit length repeat";
00856                         state->mode = BAD;
00857                         break;
00858                     }
00859                     while (copy--)
00860                         state->lens[state->have++] = (unsigned short)len;
00861                 }
00862             }
00863 
00864             /* build code tables */
00865             state->next = state->codes;
00866             state->lencode = (code const FAR *)(state->next);
00867             state->lenbits = 9;
00868             ret = inflate_table(LENS, state->lens, state->nlen, &(state->next),
00869                                 &(state->lenbits), state->work);
00870             if (ret) {
00871                 strm->msg = (char *)"invalid literal/lengths set";
00872                 state->mode = BAD;
00873                 break;
00874             }
00875             state->distcode = (code const FAR *)(state->next);
00876             state->distbits = 6;
00877             ret = inflate_table(DISTS, state->lens + state->nlen, state->ndist,
00878                             &(state->next), &(state->distbits), state->work);
00879             if (ret) {
00880                 strm->msg = (char *)"invalid distances set";
00881                 state->mode = BAD;
00882                 break;
00883             }
00884             Tracev((stderr, "inflate:       codes ok\n"));
00885             state->mode = LEN;
00886         case LEN:
00887             if (have >= 6 && left >= 258) {
00888                 RESTORE();
00889                 inflate_fast(strm, out);
00890                 LOAD();
00891                 break;
00892             }
00893             for (;;) {
00894                 this = state->lencode[BITS(state->lenbits)];
00895                 if ((unsigned)(this.bits) <= bits) break;
00896                 PULLBYTE();
00897             }
00898             if (this.op && (this.op & 0xf0) == 0) {
00899                 last = this;
00900                 for (;;) {
00901                     this = state->lencode[last.val +
00902                             (BITS(last.bits + last.op) >> last.bits)];
00903                     if ((unsigned)(last.bits + this.bits) <= bits) break;
00904                     PULLBYTE();
00905                 }
00906                 DROPBITS(last.bits);
00907             }
00908             DROPBITS(this.bits);
00909             state->length = (unsigned)this.val;
00910             if ((int)(this.op) == 0) {
00911                 Tracevv((stderr, this.val >= 0x20 && this.val < 0x7f ?
00912                         "inflate:         literal '%c'\n" :
00913                         "inflate:         literal 0x%02x\n", this.val));
00914                 state->mode = LIT;
00915                 break;
00916             }
00917             if (this.op & 32) {
00918                 Tracevv((stderr, "inflate:         end of block\n"));
00919                 state->mode = TYPE;
00920                 break;
00921             }
00922             if (this.op & 64) {
00923                 strm->msg = (char *)"invalid literal/length code";
00924                 state->mode = BAD;
00925                 break;
00926             }
00927             state->extra = (unsigned)(this.op) & 15;
00928             state->mode = LENEXT;
00929         case LENEXT:
00930             if (state->extra) {
00931                 NEEDBITS(state->extra);
00932                 state->length += BITS(state->extra);
00933                 DROPBITS(state->extra);
00934             }
00935             Tracevv((stderr, "inflate:         length %u\n", state->length));
00936             state->mode = DIST;
00937         case DIST:
00938             for (;;) {
00939                 this = state->distcode[BITS(state->distbits)];
00940                 if ((unsigned)(this.bits) <= bits) break;
00941                 PULLBYTE();
00942             }
00943             if ((this.op & 0xf0) == 0) {
00944                 last = this;
00945                 for (;;) {
00946                     this = state->distcode[last.val +
00947                             (BITS(last.bits + last.op) >> last.bits)];
00948                     if ((unsigned)(last.bits + this.bits) <= bits) break;
00949                     PULLBYTE();
00950                 }
00951                 DROPBITS(last.bits);
00952             }
00953             DROPBITS(this.bits);
00954             if (this.op & 64) {
00955                 strm->msg = (char *)"invalid distance code";
00956                 state->mode = BAD;
00957                 break;
00958             }
00959             state->offset = (unsigned)this.val;
00960             state->extra = (unsigned)(this.op) & 15;
00961             state->mode = DISTEXT;
00962         case DISTEXT:
00963             if (state->extra) {
00964                 NEEDBITS(state->extra);
00965                 state->offset += BITS(state->extra);
00966                 DROPBITS(state->extra);
00967             }
00968             if (state->offset > state->whave + out - left) {
00969                 strm->msg = (char *)"invalid distance too far back";
00970                 state->mode = BAD;
00971                 break;
00972             }
00973             Tracevv((stderr, "inflate:         distance %u\n", state->offset));
00974             state->mode = MATCH;
00975         case MATCH:
00976             if (left == 0) goto inf_leave;
00977             copy = out - left;
00978             if (state->offset > copy) {         /* copy from window */
00979                 copy = state->offset - copy;
00980                 if (copy > state->write) {
00981                     copy -= state->write;
00982                     from = state->window + (state->wsize - copy);
00983                 }
00984                 else
00985                     from = state->window + (state->write - copy);
00986                 if (copy > state->length) copy = state->length;
00987             }
00988             else {                              /* copy from output */
00989                 from = put - state->offset;
00990                 copy = state->length;
00991             }
00992             if (copy > left) copy = left;
00993             left -= copy;
00994             state->length -= copy;
00995             do {
00996                 *put++ = *from++;
00997             } while (--copy);
00998             if (state->length == 0) state->mode = LEN;
00999             break;
01000         case LIT:
01001             if (left == 0) goto inf_leave;
01002             *put++ = (unsigned char)(state->length);
01003             left--;
01004             state->mode = LEN;
01005             break;
01006         case CHECK:
01007             if (state->wrap) {
01008                 NEEDBITS(32);
01009                 out -= left;
01010                 strm->total_out += out;
01011                 state->total += out;
01012                 if (out)
01013                     strm->adler = state->check =
01014                         UPDATE(state->check, put - out, out);
01015                 out = left;
01016                 if ((
01017 #ifdef GUNZIP
01018                      state->flags ? hold :
01019 #endif
01020                      REVERSE(hold)) != state->check) {
01021                     strm->msg = (char *)"incorrect data check";
01022                     state->mode = BAD;
01023                     break;
01024                 }
01025                 INITBITS();
01026                 Tracev((stderr, "inflate:   check matches trailer\n"));
01027             }
01028 #ifdef GUNZIP
01029             state->mode = LENGTH;
01030         case LENGTH:
01031             if (state->wrap && state->flags) {
01032                 NEEDBITS(32);
01033                 if (hold != (state->total & 0xffffffffUL)) {
01034                     strm->msg = (char *)"incorrect length check";
01035                     state->mode = BAD;
01036                     break;
01037                 }
01038                 INITBITS();
01039                 Tracev((stderr, "inflate:   length matches trailer\n"));
01040             }
01041 #endif
01042             state->mode = DONE;
01043         case DONE:
01044             ret = Z_STREAM_END;
01045             goto inf_leave;
01046         case BAD:
01047             ret = Z_DATA_ERROR;
01048             goto inf_leave;
01049         case MEM:
01050             return Z_MEM_ERROR;
01051         case SYNC:
01052         default:
01053             return Z_STREAM_ERROR;
01054         }
01055 
01056     /*
01057        Return from inflate(), updating the total counts and the check value.
01058        If there was no progress during the inflate() call, return a buffer
01059        error.  Call updatewindow() to create and/or update the window state.
01060        Note: a memory error from inflate() is non-recoverable.
01061      */
01062   inf_leave:
01063     RESTORE();
01064     if (state->wsize || (state->mode < CHECK && out != strm->avail_out))
01065         if (updatewindow(strm, out)) {
01066             state->mode = MEM;
01067             return Z_MEM_ERROR;
01068         }
01069     in -= strm->avail_in;
01070     out -= strm->avail_out;
01071     strm->total_in += in;
01072     strm->total_out += out;
01073     state->total += out;
01074     if (state->wrap && out)
01075         strm->adler = state->check =
01076             UPDATE(state->check, strm->next_out - out, out);
01077     strm->data_type = state->bits + (state->last ? 64 : 0) +
01078                       (state->mode == TYPE ? 128 : 0);
01079     if (((in == 0 && out == 0) || flush == Z_FINISH) && ret == Z_OK)
01080         ret = Z_BUF_ERROR;
01081     return ret;
01082 }
01083 
01084 int ZEXPORT inflateEnd(strm)
01085 z_streamp strm;
01086 {
01087     struct inflate_state FAR *state;
01088     if (strm == Z_NULL || strm->state == Z_NULL || strm->zfree == (free_func)0)
01089         return Z_STREAM_ERROR;
01090     state = (struct inflate_state FAR *)strm->state;
01091     if (state->window != Z_NULL) ZFREE(strm, state->window);
01092     ZFREE(strm, strm->state);
01093     strm->state = Z_NULL;
01094     Tracev((stderr, "inflate: end\n"));
01095     return Z_OK;
01096 }
01097 
01098 int ZEXPORT inflateSetDictionary(strm, dictionary, dictLength)
01099 z_streamp strm;
01100 const Bytef *dictionary;
01101 uInt dictLength;
01102 {
01103     struct inflate_state FAR *state;
01104     unsigned long id;
01105 
01106     /* check state */
01107     if (strm == Z_NULL || strm->state == Z_NULL) return Z_STREAM_ERROR;
01108     state = (struct inflate_state FAR *)strm->state;
01109     if (state->mode != DICT) return Z_STREAM_ERROR;
01110 
01111     /* check for correct dictionary id */
01112     id = adler32(0L, Z_NULL, 0);
01113     id = adler32(id, dictionary, dictLength);
01114     if (id != state->check) return Z_DATA_ERROR;
01115 
01116     /* copy dictionary to window */
01117     if (updatewindow(strm, strm->avail_out)) {
01118         state->mode = MEM;
01119         return Z_MEM_ERROR;
01120     }
01121     if (dictLength > state->wsize) {
01122         zmemcpy(state->window, dictionary + dictLength - state->wsize,
01123                 state->wsize);
01124         state->whave = state->wsize;
01125     }
01126     else {
01127         zmemcpy(state->window + state->wsize - dictLength, dictionary,
01128                 dictLength);
01129         state->whave = dictLength;
01130     }
01131     state->havedict = 1;
01132     Tracev((stderr, "inflate:   dictionary set\n"));
01133     return Z_OK;
01134 }
01135 
01136 /*
01137    Search buf[0..len-1] for the pattern: 0, 0, 0xff, 0xff.  Return when found
01138    or when out of input.  When called, *have is the number of pattern bytes
01139    found in order so far, in 0..3.  On return *have is updated to the new
01140    state.  If on return *have equals four, then the pattern was found and the
01141    return value is how many bytes were read including the last byte of the
01142    pattern.  If *have is less than four, then the pattern has not been found
01143    yet and the return value is len.  In the latter case, syncsearch() can be
01144    called again with more data and the *have state.  *have is initialized to
01145    zero for the first call.
01146  */
01147 local unsigned syncsearch(have, buf, len)
01148 unsigned FAR *have;
01149 unsigned char FAR *buf;
01150 unsigned len;
01151 {
01152     unsigned got;
01153     unsigned next;
01154 
01155     got = *have;
01156     next = 0;
01157     while (next < len && got < 4) {
01158         if ((int)(buf[next]) == (got < 2 ? 0 : 0xff))
01159             got++;
01160         else if (buf[next])
01161             got = 0;
01162         else
01163             got = 4 - got;
01164         next++;
01165     }
01166     *have = got;
01167     return next;
01168 }
01169 
01170 int ZEXPORT inflateSync(strm)
01171 z_streamp strm;
01172 {
01173     unsigned len;               /* number of bytes to look at or looked at */
01174     unsigned long in, out;      /* temporary to save total_in and total_out */
01175     unsigned char buf[4];       /* to restore bit buffer to byte string */
01176     struct inflate_state FAR *state;
01177 
01178     /* check parameters */
01179     if (strm == Z_NULL || strm->state == Z_NULL) return Z_STREAM_ERROR;
01180     state = (struct inflate_state FAR *)strm->state;
01181     if (strm->avail_in == 0 && state->bits < 8) return Z_BUF_ERROR;
01182 
01183     /* if first time, start search in bit buffer */
01184     if (state->mode != SYNC) {
01185         state->mode = SYNC;
01186         state->hold <<= state->bits & 7;
01187         state->bits -= state->bits & 7;
01188         len = 0;
01189         while (state->bits >= 8) {
01190             buf[len++] = (unsigned char)(state->hold);
01191             state->hold >>= 8;
01192             state->bits -= 8;
01193         }
01194         state->have = 0;
01195         syncsearch(&(state->have), buf, len);
01196     }
01197 
01198     /* search available input */
01199     len = syncsearch(&(state->have), strm->next_in, strm->avail_in);
01200     strm->avail_in -= len;
01201     strm->next_in += len;
01202     strm->total_in += len;
01203 
01204     /* return no joy or set up to restart inflate() on a new block */
01205     if (state->have != 4) return Z_DATA_ERROR;
01206     in = strm->total_in;  out = strm->total_out;
01207     inflateReset(strm);
01208     strm->total_in = in;  strm->total_out = out;
01209     state->mode = TYPE;
01210     return Z_OK;
01211 }
01212 
01213 /*
01214    Returns true if inflate is currently at the end of a block generated by
01215    Z_SYNC_FLUSH or Z_FULL_FLUSH. This function is used by one PPP
01216    implementation to provide an additional safety check. PPP uses
01217    Z_SYNC_FLUSH but removes the length bytes of the resulting empty stored
01218    block. When decompressing, PPP checks that at the end of input packet,
01219    inflate is waiting for these length bytes.
01220  */
01221 int ZEXPORT inflateSyncPoint(strm)
01222 z_streamp strm;
01223 {
01224     struct inflate_state FAR *state;
01225 
01226     if (strm == Z_NULL || strm->state == Z_NULL) return Z_STREAM_ERROR;
01227     state = (struct inflate_state FAR *)strm->state;
01228     return state->mode == STORED && state->bits == 0;
01229 }
01230 
01231 int ZEXPORT inflateCopy(dest, source)
01232 z_streamp dest;
01233 z_streamp source;
01234 {
01235     struct inflate_state FAR *state;
01236     struct inflate_state FAR *copy;
01237     unsigned char FAR *window;
01238 
01239     /* check input */
01240     if (dest == Z_NULL || source == Z_NULL || source->state == Z_NULL ||
01241         source->zalloc == (alloc_func)0 || source->zfree == (free_func)0)
01242         return Z_STREAM_ERROR;
01243     state = (struct inflate_state FAR *)source->state;
01244 
01245     /* allocate space */
01246     copy = (struct inflate_state FAR *)
01247            ZALLOC(source, 1, sizeof(struct inflate_state));
01248     if (copy == Z_NULL) return Z_MEM_ERROR;
01249     window = Z_NULL;
01250     if (state->window != Z_NULL) {
01251         window = (unsigned char FAR *)
01252                  ZALLOC(source, 1U << state->wbits, sizeof(unsigned char));
01253         if (window == Z_NULL) {
01254             ZFREE(source, copy);
01255             return Z_MEM_ERROR;
01256         }
01257     }
01258 
01259     /* copy state */
01260     *dest = *source;
01261     *copy = *state;
01262     copy->lencode = copy->codes + (state->lencode - state->codes);
01263     copy->distcode = copy->codes + (state->distcode - state->codes);
01264     copy->next = copy->codes + (state->next - state->codes);
01265     if (window != Z_NULL)
01266         zmemcpy(window, state->window, 1U << state->wbits);
01267     copy->window = window;
01268     dest->state = (voidpf)copy;
01269     return Z_OK;
01270 }