1 /* inflate.c -- zlib decompression

     2  * Copyright (C) 1995-2005 Mark Adler

     3  * For conditions of distribution and use, see copyright notice in zlib.h

     4  */

     5 

     6 /*

     7  * Change history:

     8  *

     9  * 1.2.beta0    24 Nov 2002

    10  * - First version -- complete rewrite of inflate to simplify code, avoid

    11  *   creation of window when not needed, minimize use of window when it is

    12  *   needed, make inffast.c even faster, implement gzip decoding, and to

    13  *   improve code readability and style over the previous zlib inflate code

    14  *

    15  * 1.2.beta1    25 Nov 2002

    16  * - Use pointers for available input and output checking in inffast.c

    17  * - Remove input and output counters in inffast.c

    18  * - Change inffast.c entry and loop from avail_in >= 7 to >= 6

    19  * - Remove unnecessary second byte pull from length extra in inffast.c

    20  * - Unroll direct copy to three copies per loop in inffast.c

    21  *

    22  * 1.2.beta2    4 Dec 2002

    23  * - Change external routine names to reduce potential conflicts

    24  * - Correct filename to inffixed.h for fixed tables in inflate.c

    25  * - Make hbuf[] unsigned char to match parameter type in inflate.c

    26  * - Change strm->next_out[-state->offset] to *(strm->next_out - state->offset)

    27  *   to avoid negation problem on Alphas (64 bit) in inflate.c

    28  *

    29  * 1.2.beta3    22 Dec 2002

    30  * - Add comments on state->bits assertion in inffast.c

    31  * - Add comments on op field in inftrees.h

    32  * - Fix bug in reuse of allocated window after inflateReset()

    33  * - Remove bit fields--back to byte structure for speed

    34  * - Remove distance extra == 0 check in inflate_fast()--only helps for lengths

    35  * - Change post-increments to pre-increments in inflate_fast(), PPC biased?

    36  * - Add compile time option, POSTINC, to use post-increments instead (Intel?)

    37  * - Make MATCH copy in inflate() much faster for when inflate_fast() not used

    38  * - Use local copies of stream next and avail values, as well as local bit

    39  *   buffer and bit count in inflate()--for speed when inflate_fast() not used

    40  *

    41  * 1.2.beta4    1 Jan 2003

    42  * - Split ptr - 257 statements in inflate_table() to avoid compiler warnings

    43  * - Move a comment on output buffer sizes from inffast.c to inflate.c

    44  * - Add comments in inffast.c to introduce the inflate_fast() routine

    45  * - Rearrange window copies in inflate_fast() for speed and simplification

    46  * - Unroll last copy for window match in inflate_fast()

    47  * - Use local copies of window variables in inflate_fast() for speed

    48  * - Pull out common write == 0 case for speed in inflate_fast()

    49  * - Make op and len in inflate_fast() unsigned for consistency

    50  * - Add FAR to lcode and dcode declarations in inflate_fast()

    51  * - Simplified bad distance check in inflate_fast()

    52  * - Added inflateBackInit(), inflateBack(), and inflateBackEnd() in new

    53  *   source file infback.c to provide a call-back interface to inflate for

    54  *   programs like gzip and unzip -- uses window as output buffer to avoid

    55  *   window copying

    56  *

    57  * 1.2.beta5    1 Jan 2003

    58  * - Improved inflateBack() interface to allow the caller to provide initial

    59  *   input in strm.

    60  * - Fixed stored blocks bug in inflateBack()

    61  *

    62  * 1.2.beta6    4 Jan 2003

    63  * - Added comments in inffast.c on effectiveness of POSTINC

    64  * - Typecasting all around to reduce compiler warnings

    65  * - Changed loops from while (1) or do {} while (1) to for (;;), again to

    66  *   make compilers happy

    67  * - Changed type of window in inflateBackInit() to unsigned char *

    68  *

    69  * 1.2.beta7    27 Jan 2003

    70  * - Changed many types to unsigned or unsigned short to avoid warnings

    71  * - Added inflateCopy() function

    72  *

    73  * 1.2.0        9 Mar 2003

    74  * - Changed inflateBack() interface to provide separate opaque descriptors

    75  *   for the in() and out() functions

    76  * - Changed inflateBack() argument and in_func typedef to swap the length

    77  *   and buffer address return values for the input function

    78  * - Check next_in and next_out for Z_NULL on entry to inflate()

    79  *

    80  * The history for versions after 1.2.0 are in ChangeLog in zlib distribution.

    81  */

    82 

    83 #include "zutil.h"

    84 #include "inftrees.h"

    85 #include "inflate.h"

    86 #include "inffast.h"

    87 

    88 #ifdef MAKEFIXED

    89 #  ifndef BUILDFIXED

    90 #    define BUILDFIXED

    91 #  endif

    92 #endif

    93 

    94 /* function prototypes */

    95 local void fixedtables OF((struct inflate_state FAR *state));

    96 local int updatewindow OF((z_streamp strm, unsigned out));

    97 #ifdef BUILDFIXED

    98    void makefixed OF((void));

    99 #endif

   100 local unsigned syncsearch OF((unsigned FAR *have, unsigned char FAR *buf,

   101                               unsigned len));

   102 

   103 int ZEXPORT inflateReset(strm)

   104 z_streamp strm;

   105 {

   106     struct inflate_state FAR *state;

   107 

   108     if (strm == Z_NULL || strm->state == Z_NULL) return Z_STREAM_ERROR;

   109     state = (struct inflate_state FAR *)strm->state;

   110     strm->total_in = strm->total_out = state->total = 0;

   111     strm->msg = Z_NULL;

   112     strm->adler = 1;        /* to support ill-conceived Java test suite */

   113     state->mode = HEAD;

   114     state->last = 0;

   115     state->havedict = 0;

   116     state->dmax = 32768U;

   117     state->head = Z_NULL;

   118     state->wsize = 0;

   119     state->whave = 0;

   120     state->write = 0;

   121     state->hold = 0;

   122     state->bits = 0;

   123     state->lencode = state->distcode = state->next = state->codes;

   124     Tracev((stderr, "inflate: reset\n"));

   125     return Z_OK;

   126 }

   127 

   128 int ZEXPORT inflatePrime(strm, bits, value)

   129 z_streamp strm;

   130 int bits;

   131 int value;

   132 {

   133     struct inflate_state FAR *state;

   134 

   135     if (strm == Z_NULL || strm->state == Z_NULL) return Z_STREAM_ERROR;

   136     state = (struct inflate_state FAR *)strm->state;

   137     if (bits > 16 || state->bits + bits > 32) return Z_STREAM_ERROR;

   138     value &= (1L << bits) - 1;

   139     state->hold += value << state->bits;

   140     state->bits += bits;

   141     return Z_OK;

   142 }

   143 

   144 int ZEXPORT inflateInit2_(strm, windowBits, version, stream_size)

   145 z_streamp strm;

   146 int windowBits;

   147 const char *version;

   148 int stream_size;

   149 {

   150     struct inflate_state FAR *state;

   151 

   152     if (version == Z_NULL || version[0] != ZLIB_VERSION[0] ||

   153         stream_size != (int)(sizeof(z_stream)))

   154         return Z_VERSION_ERROR;

   155     if (strm == Z_NULL) return Z_STREAM_ERROR;

   156     strm->msg = Z_NULL;                 /* in case we return an error */

   157     if (strm->zalloc == (alloc_func)0) {

   158         strm->zalloc = zcalloc;

   159         strm->opaque = (voidpf)0;

   160     }

   161     if (strm->zfree == (free_func)0) strm->zfree = zcfree;

   162     state = (struct inflate_state FAR *)

   163             ZALLOC(strm, 1, sizeof(struct inflate_state));

   164     if (state == Z_NULL) return Z_MEM_ERROR;

   165     Tracev((stderr, "inflate: allocated\n"));

   166     strm->state = (struct internal_state FAR *)state;

   167     if (windowBits < 0) {

   168         state->wrap = 0;

   169         windowBits = -windowBits;

   170     }

   171     else {

   172         state->wrap = (windowBits >> 4) + 1;

   173 #ifdef GUNZIP

   174         if (windowBits < 48) windowBits &= 15;

   175 #endif

   176     }

   177     if (windowBits < 8 || windowBits > 15) {

   178         ZFREE(strm, state);

   179         strm->state = Z_NULL;

   180         return Z_STREAM_ERROR;

   181     }

   182     state->wbits = (unsigned)windowBits;

   183     state->window = Z_NULL;

   184     return inflateReset(strm);

   185 }

   186 

   187 int ZEXPORT inflateInit_(strm, version, stream_size)

   188 z_streamp strm;

   189 const char *version;

   190 int stream_size;

   191 {

   192     return inflateInit2_(strm, DEF_WBITS, version, stream_size);

   193 }

   194 

   195 /*

   196    Return state with length and distance decoding tables and index sizes set to

   197    fixed code decoding.  Normally this returns fixed tables from inffixed.h.

   198    If BUILDFIXED is defined, then instead this routine builds the tables the

   199    first time it's called, and returns those tables the first time and

   200    thereafter.  This reduces the size of the code by about 2K bytes, in

   201    exchange for a little execution time.  However, BUILDFIXED should not be

   202    used for threaded applications, since the rewriting of the tables and virgin

   203    may not be thread-safe.

   204  */

   205 local void fixedtables(state)

   206 struct inflate_state FAR *state;

   207 {

   208 #ifdef BUILDFIXED

   209     static int virgin = 1;

   210     static code *lenfix, *distfix;

   211     static code fixed[544];

   212 

   213     /* build fixed huffman tables if first call (may not be thread safe) */

   214     if (virgin) {

   215         unsigned sym, bits;

   216         static code *next;

   217 

   218         /* literal/length table */

   219         sym = 0;

   220         while (sym < 144) state->lens[sym++] = 8;

   221         while (sym < 256) state->lens[sym++] = 9;

   222         while (sym < 280) state->lens[sym++] = 7;

   223         while (sym < 288) state->lens[sym++] = 8;

   224         next = fixed;

   225         lenfix = next;

   226         bits = 9;

   227         inflate_table(LENS, state->lens, 288, &(next), &(bits), state->work);

   228 

   229         /* distance table */

   230         sym = 0;

   231         while (sym < 32) state->lens[sym++] = 5;

   232         distfix = next;

   233         bits = 5;

   234         inflate_table(DISTS, state->lens, 32, &(next), &(bits), state->work);

   235 

   236         /* do this just once */

   237         virgin = 0;

   238     }

   239 #else /* !BUILDFIXED */

   240 #   include "inffixed.h"

   241 #endif /* BUILDFIXED */

   242     state->lencode = lenfix;

   243     state->lenbits = 9;

   244     state->distcode = distfix;

   245     state->distbits = 5;

   246 }

   247 

   248 #ifdef MAKEFIXED

   249 #include <stdio.h>

   250 

   251 /*

   252    Write out the inffixed.h that is #include'd above.  Defining MAKEFIXED also

   253    defines BUILDFIXED, so the tables are built on the fly.  makefixed() writes

   254    those tables to stdout, which would be piped to inffixed.h.  A small program

   255    can simply call makefixed to do this:

   256 

   257     void makefixed(void);

   258 

   259     int main(void)

   260     {

   261         makefixed();

   262         return 0;

   263     }

   264 

   265    Then that can be linked with zlib built with MAKEFIXED defined and run:

   266 

   267     a.out > inffixed.h

   268  */

   269 void makefixed()

   270 {

   271     unsigned low, size;

   272     struct inflate_state state;

   273 

   274     fixedtables(&state);

   275     puts("    /* inffixed.h -- table for decoding fixed codes");

   276     puts("     * Generated automatically by makefixed().");

   277     puts("     */");

   278     puts("");

   279     puts("    /* WARNING: this file should *not* be used by applications.");

   280     puts("       It is part of the implementation of this library and is");

   281     puts("       subject to change. Applications should only use zlib.h.");

   282     puts("     */");

   283     puts("");

   284     size = 1U << 9;

   285     printf("    static const code lenfix[%u] = {", size);

   286     low = 0;

   287     for (;;) {

   288         if ((low % 7) == 0) printf("\n        ");

   289         printf("{%u,%u,%d}", state.lencode[low].op, state.lencode[low].bits,

   290                state.lencode[low].val);

   291         if (++low == size) break;

   292         putchar(',');

   293     }

   294     puts("\n    };");

   295     size = 1U << 5;

   296     printf("\n    static const code distfix[%u] = {", size);

   297     low = 0;

   298     for (;;) {

   299         if ((low % 6) == 0) printf("\n        ");

   300         printf("{%u,%u,%d}", state.distcode[low].op, state.distcode[low].bits,

   301                state.distcode[low].val);

   302         if (++low == size) break;

   303         putchar(',');

   304     }

   305     puts("\n    };");

   306 }

   307 #endif /* MAKEFIXED */

   308 

   309 /*

   310    Update the window with the last wsize (normally 32K) bytes written before

   311    returning.  If window does not exist yet, create it.  This is only called

   312    when a window is already in use, or when output has been written during this

   313    inflate call, but the end of the deflate stream has not been reached yet.

   314    It is also called to create a window for dictionary data when a dictionary

   315    is loaded.

   316 

   317    Providing output buffers larger than 32K to inflate() should provide a speed

   318    advantage, since only the last 32K of output is copied to the sliding window

   319    upon return from inflate(), and since all distances after the first 32K of

   320    output will fall in the output data, making match copies simpler and faster.

   321    The advantage may be dependent on the size of the processor's data caches.

   322  */

   323 local int updatewindow(strm, out)

   324 z_streamp strm;

   325 unsigned out;

   326 {

   327     struct inflate_state FAR *state;

   328     unsigned copy, dist;

   329 

   330     state = (struct inflate_state FAR *)strm->state;

   331 

   332     /* if it hasn't been done already, allocate space for the window */

   333     if (state->window == Z_NULL) {

   334         state->window = (unsigned char FAR *)

   335                         ZALLOC(strm, 1U << state->wbits,

   336                                sizeof(unsigned char));

   337         if (state->window == Z_NULL) return 1;

   338     }

   339 

   340     /* if window not in use yet, initialize */

   341     if (state->wsize == 0) {

   342         state->wsize = 1U << state->wbits;

   343         state->write = 0;

   344         state->whave = 0;

   345     }

   346 

   347     /* copy state->wsize or less output bytes into the circular window */

   348     copy = out - strm->avail_out;

   349     if (copy >= state->wsize) {

   350         zmemcpy(state->window, strm->next_out - state->wsize, state->wsize);

   351         state->write = 0;

   352         state->whave = state->wsize;

   353     }

   354     else {

   355         dist = state->wsize - state->write;

   356         if (dist > copy) dist = copy;

   357         zmemcpy(state->window + state->write, strm->next_out - copy, dist);

   358         copy -= dist;

   359         if (copy) {

   360             zmemcpy(state->window, strm->next_out - copy, copy);

   361             state->write = copy;

   362             state->whave = state->wsize;

   363         }

   364         else {

   365             state->write += dist;

   366             if (state->write == state->wsize) state->write = 0;

   367             if (state->whave < state->wsize) state->whave += dist;

   368         }

   369     }

   370     return 0;

   371 }

   372 

   373 /* Macros for inflate(): */

   374 

   375 /* check function to use adler32() for zlib or crc32() for gzip */

   376 #ifdef GUNZIP

   377 #  define UPDATE(check, buf, len) \

   378     (state->flags ? crc32(check, buf, len) : adler32(check, buf, len))

   379 #else

   380 #  define UPDATE(check, buf, len) adler32(check, buf, len)

   381 #endif

   382 

   383 /* check macros for header crc */

   384 #ifdef GUNZIP

   385 #  define CRC2(check, word) \

   386     do { \

   387         hbuf[0] = (unsigned char)(word); \

   388         hbuf[1] = (unsigned char)((word) >> 8); \

   389         check = crc32(check, hbuf, 2); \

   390     } while (0)

   391 

   392 #  define CRC4(check, word) \

   393     do { \

   394         hbuf[0] = (unsigned char)(word); \

   395         hbuf[1] = (unsigned char)((word) >> 8); \

   396         hbuf[2] = (unsigned char)((word) >> 16); \

   397         hbuf[3] = (unsigned char)((word) >> 24); \

   398         check = crc32(check, hbuf, 4); \

   399     } while (0)

   400 #endif

   401 

   402 /* Load registers with state in inflate() for speed */

   403 #define LOAD() \

   404     do { \

   405         put = strm->next_out; \

   406         left = strm->avail_out; \

   407         next = strm->next_in; \

   408         have = strm->avail_in; \

   409         hold = state->hold; \

   410         bits = state->bits; \

   411     } while (0)

   412 

   413 /* Restore state from registers in inflate() */

   414 #define RESTORE() \

   415     do { \

   416         strm->next_out = put; \

   417         strm->avail_out = left; \

   418         strm->next_in = next; \

   419         strm->avail_in = have; \

   420         state->hold = hold; \

   421         state->bits = bits; \

   422     } while (0)

   423 

   424 /* Clear the input bit accumulator */

   425 #define INITBITS() \

   426     do { \

   427         hold = 0; \

   428         bits = 0; \

   429     } while (0)

   430 

   431 /* Get a byte of input into the bit accumulator, or return from inflate()

   432    if there is no input available. */

   433 #define PULLBYTE() \

   434     do { \

   435         if (have == 0) goto inf_leave; \

   436         have--; \

   437         hold += (unsigned long)(*next++) << bits; \

   438         bits += 8; \

   439     } while (0)

   440 

   441 /* Assure that there are at least n bits in the bit accumulator.  If there is

   442    not enough available input to do that, then return from inflate(). */

   443 #define NEEDBITS(n) \

   444     do { \

   445         while (bits < (unsigned)(n)) \

   446             PULLBYTE(); \

   447     } while (0)

   448 

   449 /* Return the low n bits of the bit accumulator (n < 16) */

   450 #define BITS(n) \

   451     ((unsigned)hold & ((1U << (n)) - 1))

   452 

   453 /* Remove n bits from the bit accumulator */

   454 #define DROPBITS(n) \

   455     do { \

   456         hold >>= (n); \

   457         bits -= (unsigned)(n); \

   458     } while (0)

   459 

   460 /* Remove zero to seven bits as needed to go to a byte boundary */

   461 #define BYTEBITS() \

   462     do { \

   463         hold >>= bits & 7; \

   464         bits -= bits & 7; \

   465     } while (0)

   466 

   467 /* Reverse the bytes in a 32-bit value */

   468 #define REVERSE(q) \

   469     ((((q) >> 24) & 0xff) + (((q) >> 8) & 0xff00) + \

   470      (((q) & 0xff00) << 8) + (((q) & 0xff) << 24))

   471 

   472 /*

   473    inflate() uses a state machine to process as much input data and generate as

   474    much output data as possible before returning.  The state machine is

   475    structured roughly as follows:

   476 

   477     for (;;) switch (state) {

   478     ...

   479     case STATEn:

   480         if (not enough input data or output space to make progress)

   481             return;

   482         ... make progress ...

   483         state = STATEm;

   484         break;

   485     ...

   486     }

   487 

   488    so when inflate() is called again, the same case is attempted again, and

   489    if the appropriate resources are provided, the machine proceeds to the

   490    next state.  The NEEDBITS() macro is usually the way the state evaluates

   491    whether it can proceed or should return.  NEEDBITS() does the return if

   492    the requested bits are not available.  The typical use of the BITS macros

   493    is:

   494 

   495         NEEDBITS(n);

   496         ... do something with BITS(n) ...

   497         DROPBITS(n);

   498 

   499    where NEEDBITS(n) either returns from inflate() if there isn't enough

   500    input left to load n bits into the accumulator, or it continues.  BITS(n)

   501    gives the low n bits in the accumulator.  When done, DROPBITS(n) drops

   502    the low n bits off the accumulator.  INITBITS() clears the accumulator

   503    and sets the number of available bits to zero.  BYTEBITS() discards just

   504    enough bits to put the accumulator on a byte boundary.  After BYTEBITS()

   505    and a NEEDBITS(8), then BITS(8) would return the next byte in the stream.

   506 

   507    NEEDBITS(n) uses PULLBYTE() to get an available byte of input, or to return

   508    if there is no input available.  The decoding of variable length codes uses

   509    PULLBYTE() directly in order to pull just enough bytes to decode the next

   510    code, and no more.

   511 

   512    Some states loop until they get enough input, making sure that enough

   513    state information is maintained to continue the loop where it left off

   514    if NEEDBITS() returns in the loop.  For example, want, need, and keep

   515    would all have to actually be part of the saved state in case NEEDBITS()

   516    returns:

   517 

   518     case STATEw:

   519         while (want < need) {

   520             NEEDBITS(n);

   521             keep[want++] = BITS(n);

   522             DROPBITS(n);

   523         }

   524         state = STATEx;

   525     case STATEx:

   526 

   527    As shown above, if the next state is also the next case, then the break

   528    is omitted.

   529 

   530    A state may also return if there is not enough output space available to

   531    complete that state.  Those states are copying stored data, writing a

   532    literal byte, and copying a matching string.

   533 

   534    When returning, a "goto inf_leave" is used to update the total counters,

   535    update the check value, and determine whether any progress has been made

   536    during that inflate() call in order to return the proper return code.

   537    Progress is defined as a change in either strm->avail_in or strm->avail_out.

   538    When there is a window, goto inf_leave will update the window with the last

   539    output written.  If a goto inf_leave occurs in the middle of decompression

   540    and there is no window currently, goto inf_leave will create one and copy

   541    output to the window for the next call of inflate().

   542 

   543    In this implementation, the flush parameter of inflate() only affects the

   544    return code (per zlib.h).  inflate() always writes as much as possible to

   545    strm->next_out, given the space available and the provided input--the effect

   546    documented in zlib.h of Z_SYNC_FLUSH.  Furthermore, inflate() always defers

   547    the allocation of and copying into a sliding window until necessary, which

   548    provides the effect documented in zlib.h for Z_FINISH when the entire input

   549    stream available.  So the only thing the flush parameter actually does is:

   550    when flush is set to Z_FINISH, inflate() cannot return Z_OK.  Instead it

   551    will return Z_BUF_ERROR if it has not reached the end of the stream.

   552  */

   553 

   554 int ZEXPORT inflate(strm, flush)

   555 z_streamp strm;

   556 int flush;

   557 {

   558     struct inflate_state FAR *state;

   559     unsigned char FAR *next;    /* next input */

   560     unsigned char FAR *put;     /* next output */

   561     unsigned have, left;        /* available input and output */

   562     unsigned long hold;         /* bit buffer */

   563     unsigned bits;              /* bits in bit buffer */

   564     unsigned in, out;           /* save starting available input and output */

   565     unsigned copy;              /* number of stored or match bytes to copy */

   566     unsigned char FAR *from;    /* where to copy match bytes from */

   567     code this;                  /* current decoding table entry */

   568     code last;                  /* parent table entry */

   569     unsigned len;               /* length to copy for repeats, bits to drop */

   570     int ret;                    /* return code */

   571 #ifdef GUNZIP

   572     unsigned char hbuf[4];      /* buffer for gzip header crc calculation */

   573 #endif

   574     static const unsigned short order[19] = /* permutation of code lengths */

   575         {16, 17, 18, 0, 8, 7, 9, 6, 10, 5, 11, 4, 12, 3, 13, 2, 14, 1, 15};

   576 

   577     if (strm == Z_NULL || strm->state == Z_NULL || strm->next_out == Z_NULL ||

   578         (strm->next_in == Z_NULL && strm->avail_in != 0))

   579         return Z_STREAM_ERROR;

   580 

   581     state = (struct inflate_state FAR *)strm->state;

   582     if (state->mode == TYPE) state->mode = TYPEDO;      /* skip check */

   583     LOAD();

   584     in = have;

   585     out = left;

   586     ret = Z_OK;

   587     for (;;)

   588         switch (state->mode) {

   589         case HEAD:

   590             if (state->wrap == 0) {

   591                 state->mode = TYPEDO;

   592                 break;

   593             }

   594             NEEDBITS(16);

   595 #ifdef GUNZIP

   596             if ((state->wrap & 2) && hold == 0x8b1f) {  /* gzip header */

   597                 state->check = crc32(0L, Z_NULL, 0);

   598                 CRC2(state->check, hold);

   599                 INITBITS();

   600                 state->mode = FLAGS;

   601                 break;

   602             }

   603             state->flags = 0;           /* expect zlib header */

   604             if (state->head != Z_NULL)

   605                 state->head->done = -1;

   606             if (!(state->wrap & 1) ||   /* check if zlib header allowed */

   607 #else

   608             if (

   609 #endif

   610                 ((BITS(8) << 8) + (hold >> 8)) % 31) {

   611                 strm->msg = (char *)"incorrect header check";

   612                 state->mode = BAD;

   613                 break;

   614             }

   615             if (BITS(4) != Z_DEFLATED) {

   616                 strm->msg = (char *)"unknown compression method";

   617                 state->mode = BAD;

   618                 break;

   619             }

   620             DROPBITS(4);

   621             len = BITS(4) + 8;

   622             if (len > state->wbits) {

   623                 strm->msg = (char *)"invalid window size";

   624                 state->mode = BAD;

   625                 break;

   626             }

   627             state->dmax = 1U << len;

   628             Tracev((stderr, "inflate:   zlib header ok\n"));

   629             strm->adler = state->check = adler32(0L, Z_NULL, 0);

   630             state->mode = hold & 0x200 ? DICTID : TYPE;

   631             INITBITS();

   632             break;

   633 #ifdef GUNZIP

   634         case FLAGS:

   635             NEEDBITS(16);

   636             state->flags = (int)(hold);

   637             if ((state->flags & 0xff) != Z_DEFLATED) {

   638                 strm->msg = (char *)"unknown compression method";

   639                 state->mode = BAD;

   640                 break;

   641             }

   642             if (state->flags & 0xe000) {

   643                 strm->msg = (char *)"unknown header flags set";

   644                 state->mode = BAD;

   645                 break;

   646             }

   647             if (state->head != Z_NULL)

   648                 state->head->text = (int)((hold >> 8) & 1);

   649             if (state->flags & 0x0200) CRC2(state->check, hold);

   650             INITBITS();

   651             state->mode = TIME;

   652         case TIME:

   653             NEEDBITS(32);

   654             if (state->head != Z_NULL)

   655                 state->head->time = hold;

   656             if (state->flags & 0x0200) CRC4(state->check, hold);

   657             INITBITS();

   658             state->mode = OS;

   659         case OS:

   660             NEEDBITS(16);

   661             if (state->head != Z_NULL) {

   662                 state->head->xflags = (int)(hold & 0xff);

   663                 state->head->os = (int)(hold >> 8);

   664             }

   665             if (state->flags & 0x0200) CRC2(state->check, hold);

   666             INITBITS();

   667             state->mode = EXLEN;

   668         case EXLEN:

   669             if (state->flags & 0x0400) {

   670                 NEEDBITS(16);

   671                 state->length = (unsigned)(hold);

   672                 if (state->head != Z_NULL)

   673                     state->head->extra_len = (unsigned)hold;

   674                 if (state->flags & 0x0200) CRC2(state->check, hold);

   675                 INITBITS();

   676             }

   677             else if (state->head != Z_NULL)

   678                 state->head->extra = Z_NULL;

   679             state->mode = EXTRA;

   680         case EXTRA:

   681             if (state->flags & 0x0400) {

   682                 copy = state->length;

   683                 if (copy > have) copy = have;

   684                 if (copy) {

   685                     if (state->head != Z_NULL &&

   686                         state->head->extra != Z_NULL) {

   687                         len = state->head->extra_len - state->length;

   688                         zmemcpy(state->head->extra + len, next,

   689                                 len + copy > state->head->extra_max ?

   690                                 state->head->extra_max - len : copy);

   691                     }

   692                     if (state->flags & 0x0200)

   693                         state->check = crc32(state->check, next, copy);

   694                     have -= copy;

   695                     next += copy;

   696                     state->length -= copy;

   697                 }

   698                 if (state->length) goto inf_leave;

   699             }

   700             state->length = 0;

   701             state->mode = NAME;

   702         case NAME:

   703             if (state->flags & 0x0800) {

   704                 if (have == 0) goto inf_leave;

   705                 copy = 0;

   706                 do {

   707                     len = (unsigned)(next[copy++]);

   708                     if (state->head != Z_NULL &&

   709                             state->head->name != Z_NULL &&

   710                             state->length < state->head->name_max)

   711                         state->head->name[state->length++] = len;

   712                 } while (len && copy < have);

   713                 if (state->flags & 0x0200)

   714                     state->check = crc32(state->check, next, copy);

   715                 have -= copy;

   716                 next += copy;

   717                 if (len) goto inf_leave;

   718             }

   719             else if (state->head != Z_NULL)

   720                 state->head->name = Z_NULL;

   721             state->length = 0;

   722             state->mode = COMMENT;

   723         case COMMENT:

   724             if (state->flags & 0x1000) {

   725                 if (have == 0) goto inf_leave;

   726                 copy = 0;

   727                 do {

   728                     len = (unsigned)(next[copy++]);

   729                     if (state->head != Z_NULL &&

   730                             state->head->comment != Z_NULL &&

   731                             state->length < state->head->comm_max)

   732                         state->head->comment[state->length++] = len;

   733                 } while (len && copy < have);

   734                 if (state->flags & 0x0200)

   735                     state->check = crc32(state->check, next, copy);

   736                 have -= copy;

   737                 next += copy;

   738                 if (len) goto inf_leave;

   739             }

   740             else if (state->head != Z_NULL)

   741                 state->head->comment = Z_NULL;

   742             state->mode = HCRC;

   743         case HCRC:

   744             if (state->flags & 0x0200) {

   745                 NEEDBITS(16);

   746                 if (hold != (state->check & 0xffff)) {

   747                     strm->msg = (char *)"header crc mismatch";

   748                     state->mode = BAD;

   749                     break;

   750                 }

   751                 INITBITS();

   752             }

   753             if (state->head != Z_NULL) {

   754                 state->head->hcrc = (int)((state->flags >> 9) & 1);

   755                 state->head->done = 1;

   756             }

   757             strm->adler = state->check = crc32(0L, Z_NULL, 0);

   758             state->mode = TYPE;

   759             break;

   760 #endif

   761         case DICTID:

   762             NEEDBITS(32);

   763             strm->adler = state->check = REVERSE(hold);

   764             INITBITS();

   765             state->mode = DICT;

   766         case DICT:

   767             if (state->havedict == 0) {

   768                 RESTORE();

   769                 return Z_NEED_DICT;

   770             }

   771             strm->adler = state->check = adler32(0L, Z_NULL, 0);

   772             state->mode = TYPE;

   773         case TYPE:

   774             if (flush == Z_BLOCK) goto inf_leave;

   775         case TYPEDO:

   776             if (state->last) {

   777                 BYTEBITS();

   778                 state->mode = CHECK;

   779                 break;

   780             }

   781             NEEDBITS(3);

   782             state->last = BITS(1);

   783             DROPBITS(1);

   784             switch (BITS(2)) {

   785             case 0:                             /* stored block */

   786                 Tracev((stderr, "inflate:     stored block%s\n",

   787                         state->last ? " (last)" : ""));

   788                 state->mode = STORED;

   789                 break;

   790             case 1:                             /* fixed block */

   791                 fixedtables(state);

   792                 Tracev((stderr, "inflate:     fixed codes block%s\n",

   793                         state->last ? " (last)" : ""));

   794                 state->mode = LEN;              /* decode codes */

   795                 break;

   796             case 2:                             /* dynamic block */

   797                 Tracev((stderr, "inflate:     dynamic codes block%s\n",

   798                         state->last ? " (last)" : ""));

   799                 state->mode = TABLE;

   800                 break;

   801             case 3:

   802                 strm->msg = (char *)"invalid block type";

   803                 state->mode = BAD;

   804             }

   805             DROPBITS(2);

   806             break;

   807         case STORED:

   808             BYTEBITS();                         /* go to byte boundary */

   809             NEEDBITS(32);

   810             if ((hold & 0xffff) != ((hold >> 16) ^ 0xffff)) {

   811                 strm->msg = (char *)"invalid stored block lengths";

   812                 state->mode = BAD;

   813                 break;

   814             }

   815             state->length = (unsigned)hold & 0xffff;

   816             Tracev((stderr, "inflate:       stored length %u\n",

   817                     state->length));

   818             INITBITS();

   819             state->mode = COPY;

   820         case COPY:

   821             copy = state->length;

   822             if (copy) {

   823                 if (copy > have) copy = have;

   824                 if (copy > left) copy = left;

   825                 if (copy == 0) goto inf_leave;

   826                 zmemcpy(put, next, copy);

   827                 have -= copy;

   828                 next += copy;

   829                 left -= copy;

   830                 put += copy;

   831                 state->length -= copy;

   832                 break;

   833             }

   834             Tracev((stderr, "inflate:       stored end\n"));

   835             state->mode = TYPE;

   836             break;

   837         case TABLE:

   838             NEEDBITS(14);

   839             state->nlen = BITS(5) + 257;

   840             DROPBITS(5);

   841             state->ndist = BITS(5) + 1;

   842             DROPBITS(5);

   843             state->ncode = BITS(4) + 4;

   844             DROPBITS(4);

   845 #ifndef PKZIP_BUG_WORKAROUND

   846             if (state->nlen > 286 || state->ndist > 30) {

   847                 strm->msg = (char *)"too many length or distance symbols";

   848                 state->mode = BAD;

   849                 break;

   850             }

   851 #endif

   852             Tracev((stderr, "inflate:       table sizes ok\n"));

   853             state->have = 0;

   854             state->mode = LENLENS;

   855         case LENLENS:

   856             while (state->have < state->ncode) {

   857                 NEEDBITS(3);

   858                 state->lens[order[state->have++]] = (unsigned short)BITS(3);

   859                 DROPBITS(3);

   860             }

   861             while (state->have < 19)

   862                 state->lens[order[state->have++]] = 0;

   863             state->next = state->codes;

   864             state->lencode = (code const FAR *)(state->next);

   865             state->lenbits = 7;

   866             ret = inflate_table(CODES, state->lens, 19, &(state->next),

   867                                 &(state->lenbits), state->work);

   868             if (ret) {

   869                 strm->msg = (char *)"invalid code lengths set";

   870                 state->mode = BAD;

   871                 break;

   872             }

   873             Tracev((stderr, "inflate:       code lengths ok\n"));

   874             state->have = 0;

   875             state->mode = CODELENS;

   876         case CODELENS:

   877             while (state->have < state->nlen + state->ndist) {

   878                 for (;;) {

   879                     this = state->lencode[BITS(state->lenbits)];

   880                     if ((unsigned)(this.bits) <= bits) break;

   881                     PULLBYTE();

   882                 }

   883                 if (this.val < 16) {

   884                     NEEDBITS(this.bits);

   885                     DROPBITS(this.bits);

   886                     state->lens[state->have++] = this.val;

   887                 }

   888                 else {

   889                     if (this.val == 16) {

   890                         NEEDBITS(this.bits + 2);

   891                         DROPBITS(this.bits);

   892                         if (state->have == 0) {

   893                             strm->msg = (char *)"invalid bit length repeat";

   894                             state->mode = BAD;

   895                             break;

   896                         }

   897                         len = state->lens[state->have - 1];

   898                         copy = 3 + BITS(2);

   899                         DROPBITS(2);

   900                     }

   901                     else if (this.val == 17) {

   902                         NEEDBITS(this.bits + 3);

   903                         DROPBITS(this.bits);

   904                         len = 0;

   905                         copy = 3 + BITS(3);

   906                         DROPBITS(3);

   907                     }

   908                     else {

   909                         NEEDBITS(this.bits + 7);

   910                         DROPBITS(this.bits);

   911                         len = 0;

   912                         copy = 11 + BITS(7);

   913                         DROPBITS(7);

   914                     }

   915                     if (state->have + copy > state->nlen + state->ndist) {

   916                         strm->msg = (char *)"invalid bit length repeat";

   917                         state->mode = BAD;

   918                         break;

   919                     }

   920                     while (copy--)

   921                         state->lens[state->have++] = (unsigned short)len;

   922                 }

   923             }

   924 

   925             /* handle error breaks in while */

   926             if (state->mode == BAD) break;

   927 

   928             /* build code tables */

   929             state->next = state->codes;

   930             state->lencode = (code const FAR *)(state->next);

   931             state->lenbits = 9;

   932             ret = inflate_table(LENS, state->lens, state->nlen, &(state->next),

   933                                 &(state->lenbits), state->work);

   934             if (ret) {

   935                 strm->msg = (char *)"invalid literal/lengths set";

   936                 state->mode = BAD;

   937                 break;

   938             }

   939             state->distcode = (code const FAR *)(state->next);

   940             state->distbits = 6;

   941             ret = inflate_table(DISTS, state->lens + state->nlen, state->ndist,

   942                             &(state->next), &(state->distbits), state->work);

   943             if (ret) {

   944                 strm->msg = (char *)"invalid distances set";

   945                 state->mode = BAD;

   946                 break;

   947             }

   948             Tracev((stderr, "inflate:       codes ok\n"));

   949             state->mode = LEN;

   950         case LEN:

   951             if (have >= 6 && left >= 258) {

   952                 RESTORE();

   953                 inflate_fast(strm, out);

   954                 LOAD();

   955                 break;

   956             }

   957             for (;;) {

   958                 this = state->lencode[BITS(state->lenbits)];

   959                 if ((unsigned)(this.bits) <= bits) break;

   960                 PULLBYTE();

   961             }

   962             if (this.op && (this.op & 0xf0) == 0) {

   963                 last = this;

   964                 for (;;) {

   965                     this = state->lencode[last.val +

   966                             (BITS(last.bits + last.op) >> last.bits)];

   967                     if ((unsigned)(last.bits + this.bits) <= bits) break;

   968                     PULLBYTE();

   969                 }

   970                 DROPBITS(last.bits);

   971             }

   972             DROPBITS(this.bits);

   973             state->length = (unsigned)this.val;

   974             if ((int)(this.op) == 0) {

   975                 Tracevv((stderr, this.val >= 0x20 && this.val < 0x7f ?

   976                         "inflate:         literal '%c'\n" :

   977                         "inflate:         literal 0x%02x\n", this.val));

   978                 state->mode = LIT;

   979                 break;

   980             }

   981             if (this.op & 32) {

   982                 Tracevv((stderr, "inflate:         end of block\n"));

   983                 state->mode = TYPE;

   984                 break;

   985             }

   986             if (this.op & 64) {

   987                 strm->msg = (char *)"invalid literal/length code";

   988                 state->mode = BAD;

   989                 break;

   990             }

   991             state->extra = (unsigned)(this.op) & 15;

   992             state->mode = LENEXT;

   993         case LENEXT:

   994             if (state->extra) {

   995                 NEEDBITS(state->extra);

   996                 state->length += BITS(state->extra);

   997                 DROPBITS(state->extra);

   998             }

   999             Tracevv((stderr, "inflate:         length %u\n", state->length));

  1000             state->mode = DIST;

  1001         case DIST:

  1002             for (;;) {

  1003                 this = state->distcode[BITS(state->distbits)];

  1004                 if ((unsigned)(this.bits) <= bits) break;

  1005                 PULLBYTE();

  1006             }

  1007             if ((this.op & 0xf0) == 0) {

  1008                 last = this;

  1009                 for (;;) {

  1010                     this = state->distcode[last.val +

  1011                             (BITS(last.bits + last.op) >> last.bits)];

  1012                     if ((unsigned)(last.bits + this.bits) <= bits) break;

  1013                     PULLBYTE();

  1014                 }

  1015                 DROPBITS(last.bits);

  1016             }

  1017             DROPBITS(this.bits);

  1018             if (this.op & 64) {

  1019                 strm->msg = (char *)"invalid distance code";

  1020                 state->mode = BAD;

  1021                 break;

  1022             }

  1023             state->offset = (unsigned)this.val;

  1024             state->extra = (unsigned)(this.op) & 15;

  1025             state->mode = DISTEXT;

  1026         case DISTEXT:

  1027             if (state->extra) {

  1028                 NEEDBITS(state->extra);

  1029                 state->offset += BITS(state->extra);

  1030                 DROPBITS(state->extra);

  1031             }

  1032 #ifdef INFLATE_STRICT

  1033             if (state->offset > state->dmax) {

  1034                 strm->msg = (char *)"invalid distance too far back";

  1035                 state->mode = BAD;

  1036                 break;

  1037             }

  1038 #endif

  1039             if (state->offset > state->whave + out - left) {

  1040                 strm->msg = (char *)"invalid distance too far back";

  1041                 state->mode = BAD;

  1042                 break;

  1043             }

  1044             Tracevv((stderr, "inflate:         distance %u\n", state->offset));

  1045             state->mode = MATCH;

  1046         case MATCH:

  1047             if (left == 0) goto inf_leave;

  1048             copy = out - left;

  1049             if (state->offset > copy) {         /* copy from window */

  1050                 copy = state->offset - copy;

  1051                 if (copy > state->write) {

  1052                     copy -= state->write;

  1053                     from = state->window + (state->wsize - copy);

  1054                 }

  1055                 else

  1056                     from = state->window + (state->write - copy);

  1057                 if (copy > state->length) copy = state->length;

  1058             }

  1059             else {                              /* copy from output */

  1060                 from = put - state->offset;

  1061                 copy = state->length;

  1062             }

  1063             if (copy > left) copy = left;

  1064             left -= copy;

  1065             state->length -= copy;

  1066             do {

  1067                 *put++ = *from++;

  1068             } while (--copy);

  1069             if (state->length == 0) state->mode = LEN;

  1070             break;

  1071         case LIT:

  1072             if (left == 0) goto inf_leave;

  1073             *put++ = (unsigned char)(state->length);

  1074             left--;

  1075             state->mode = LEN;

  1076             break;

  1077         case CHECK:

  1078             if (state->wrap) {

  1079                 NEEDBITS(32);

  1080                 out -= left;

  1081                 strm->total_out += out;

  1082                 state->total += out;

  1083                 if (out)

  1084                     strm->adler = state->check =

  1085                         UPDATE(state->check, put - out, out);

  1086                 out = left;

  1087                 if ((

  1088 #ifdef GUNZIP

  1089                      state->flags ? hold :

  1090 #endif

  1091                      REVERSE(hold)) != state->check) {

  1092                     strm->msg = (char *)"incorrect data check";

  1093                     state->mode = BAD;

  1094                     break;

  1095                 }

  1096                 INITBITS();

  1097                 Tracev((stderr, "inflate:   check matches trailer\n"));

  1098             }

  1099 #ifdef GUNZIP

  1100             state->mode = LENGTH;

  1101         case LENGTH:

  1102             if (state->wrap && state->flags) {

  1103                 NEEDBITS(32);

  1104                 if (hold != (state->total & 0xffffffffUL)) {

  1105                     strm->msg = (char *)"incorrect length check";

  1106                     state->mode = BAD;

  1107                     break;

  1108                 }

  1109                 INITBITS();

  1110                 Tracev((stderr, "inflate:   length matches trailer\n"));

  1111             }

  1112 #endif

  1113             state->mode = DONE;

  1114         case DONE:

  1115             ret = Z_STREAM_END;

  1116             goto inf_leave;

  1117         case BAD:

  1118             ret = Z_DATA_ERROR;

  1119             goto inf_leave;

  1120         case MEM:

  1121             return Z_MEM_ERROR;

  1122         case SYNC:

  1123         default:

  1124             return Z_STREAM_ERROR;

  1125         }

  1126 

  1127     /*

  1128        Return from inflate(), updating the total counts and the check value.

  1129        If there was no progress during the inflate() call, return a buffer

  1130        error.  Call updatewindow() to create and/or update the window state.

  1131        Note: a memory error from inflate() is non-recoverable.

  1132      */

  1133   inf_leave:

  1134     RESTORE();

  1135     if (state->wsize || (state->mode < CHECK && out != strm->avail_out))