1 /* inflate.cpp -- 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 #ifdef __SYMBIAN32__

   104 EXPORT_C  int inflateReset_r (z_streamp strm)

   105 #else

   106 int ZEXPORT inflateReset(strm)

   107 z_streamp strm;

   108 #endif //__SYMBIAN32__

   109 {

   110     struct inflate_state FAR *state;

   111 

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

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

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

   115     strm->msg = Z_NULL;

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

   117     state->mode = HEAD;

   118     state->last = 0;

   119     state->havedict = 0;

   120     state->dmax = 32768U;

   121     state->head = Z_NULL;

   122     state->wsize = 0;

   123     state->whave = 0;

   124     state->write = 0;

   125     state->hold = 0;

   126     state->bits = 0;

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

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

   129     return Z_OK;

   130 }

   131 

   132 

   133 #ifdef __SYMBIAN32__

   134 EXPORT_C int  inflatePrime_r(z_streamp strm, int bits, int value)

   135 #else

   136 int ZEXPORT inflatePrime(strm, bits, value)

   137 z_streamp strm;

   138 int bits;

   139 int value;

   140 #endif //__SYMBIAN32__

   141 {

   142     struct inflate_state FAR *state;

   143 

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

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

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

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

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

   149     state->bits += bits;

   150     return Z_OK;

   151 }

   152 

   153 #ifdef __SYMBIAN32__

   154 EXPORT_C int inflateInit2__r(z_streamp strm, int windowBits,const char * version,int  stream_size)

   155 #else

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

   157 z_streamp strm;

   158 int windowBits;

   159 const char *version;

   160 int stream_size;

   161 #endif //__SYMBIAN32__

   162 {

   163     struct inflate_state FAR *state;

   164 

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

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

   167         return Z_VERSION_ERROR;

   168     if (strm == Z_NULL) return Z_STREAM_ERROR;

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

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

   171         strm->zalloc = zcalloc;

   172         strm->opaque = (voidpf)0;

   173     }

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

   175     state = (struct inflate_state FAR *)

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

   177     if (state == Z_NULL) return Z_MEM_ERROR;

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

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

   180     if (windowBits < 0) {

   181         state->wrap = 0;

   182         windowBits = -windowBits;

   183     }

   184     else {

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

   186 #ifdef GUNZIP

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

   188 #endif

   189     }

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

   191         ZFREE(strm, state);

   192         strm->state = Z_NULL;

   193         return Z_STREAM_ERROR;

   194     }

   195     state->wbits = (unsigned)windowBits;

   196     state->window = Z_NULL;

   197     return inflateReset_r (strm);

   198 }

   199 

   200 #ifdef __SYMBIAN32__

   201 EXPORT_C  int inflateInit__r (z_streamp strm,const char *  version,int stream_size)

   202 #else

   203 int ZEXPORT inflateInit_(strm, version, stream_size)

   204 z_streamp strm;

   205 const char *version;

   206 int stream_size;

   207 #endif //__SYMBIAN32__

   208 {

   209     return inflateInit2__r(strm, DEF_WBITS, version, stream_size);

   210 }

   211 

   212 

   213 /*

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

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

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

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

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

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

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

   221    may not be thread-safe.

   222  */

   223  

   224 #ifdef __SYMBIAN32__

   225 local void fixedtables(struct inflate_state FAR * state)

   226 #else

   227 local void fixedtables(state)

   228 struct inflate_state FAR *state;

   229 #endif //__SYMBIAN32__

   230 {

   231 #ifdef BUILDFIXED

   232     static int virgin = 1;

   233     static code *lenfix, *distfix;

   234     static code fixed[544];

   235 

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

   237     if (virgin) {

   238         unsigned sym, bits;

   239         static code *next;

   240 

   241         /* literal/length table */

   242         sym = 0;

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

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

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

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

   247         next = fixed;

   248         lenfix = next;

   249         bits = 9;

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

   251 

   252         /* distance table */

   253         sym = 0;

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

   255         distfix = next;

   256         bits = 5;

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

   258 

   259         /* do this just once */

   260         virgin = 0;

   261     }

   262 #else /* !BUILDFIXED */

   263 #   include "inffixed.h"

   264 #endif /* BUILDFIXED */

   265     state->lencode = lenfix;

   266     state->lenbits = 9;

   267     state->distcode = distfix;

   268     state->distbits = 5;

   269 }

   270 

   271 #ifndef SYMBIAN_EZLIB_DEVICE

   272 

   273 #ifdef MAKEFIXED

   274 #include <stdio.h>

   275 

   276 /*

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

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

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

   280    can simply call makefixed to do this:

   281 

   282     void makefixed(void);

   283 

   284     int main(void)

   285     {

   286         makefixed();

   287         return 0;

   288     }

   289 

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

   291 

   292     a.out > inffixed.h

   293  */

   294 void makefixed()

   295 {

   296     unsigned low, size;

   297     struct inflate_state state;

   298 

   299     fixedtables(&state);

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

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

   302     puts("     */");

   303     puts("");

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

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

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

   307     puts("     */");

   308     puts("");

   309     size = 1U << 9;

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

   311     low = 0;

   312     for (;;) {

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

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

   315                state.lencode[low].val);

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

   317         putchar(',');

   318     }

   319     puts("\n    };");

   320     size = 1U << 5;

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

   322     low = 0;

   323     for (;;) {

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

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

   326                state.distcode[low].val);

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

   328         putchar(',');

   329     }

   330     puts("\n    };");

   331 }

   332 #endif /* MAKEFIXED */

   333 

   334 #endif //SYMBIAN_EZLIB_DEVICE

   335 

   336 /*

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

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

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

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

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

   342    is loaded.

   343 

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

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

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

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

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

   349  */

   350  

   351 #ifdef __SYMBIAN32__

   352 local int updatewindow(z_streamp strm,unsigned  out)

   353 #else

   354 local int updatewindow(strm, out)

   355 z_streamp strm;

   356 unsigned out;

   357 #endif //__SYMBIAN32__

   358 {

   359     struct inflate_state FAR *state;

   360     unsigned copy, dist;

   361 

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

   363 

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

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

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

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

   368                                sizeof(unsigned char));

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

   370     }

   371 

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

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

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

   375         state->write = 0;

   376         state->whave = 0;

   377     }

   378 

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

   380     copy = out - strm->avail_out;

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

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

   383         state->write = 0;

   384         state->whave = state->wsize;

   385     }

   386     else {

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

   388         if (dist > copy) dist = copy;

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

   390         copy -= dist;

   391         if (copy) {

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

   393             state->write = copy;

   394             state->whave = state->wsize;

   395         }

   396         else {

   397             state->write += dist;

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

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

   400         }

   401     }

   402     return 0;

   403 }

   404 

   405 

   406 

   407 /* Macros for inflate(): */

   408 

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

   410 #ifdef GUNZIP

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

   412     (state->flags ? crc32_r(check, buf, len) : adler32_r(check, buf, len))

   413 #else

   414 #  define UPDATE(check, buf, len) adler32_r(check, buf, len)

   415 #endif

   416 

   417 /* check macros for header crc */

   418 #ifdef GUNZIP

   419 #  define CRC2(check, word) \

   420     do { \

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

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

   423         check = crc32_r(check, hbuf, 2); \

   424     } while (0)

   425 

   426 #  define CRC4(check, word) \

   427     do { \

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

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

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

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

   432         check = crc32_r(check, hbuf, 4); \

   433     } while (0)

   434 #endif

   435 

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

   437 #define LOAD() \

   438     do { \

   439         put = strm->next_out; \

   440         left = strm->avail_out; \

   441         next = strm->next_in; \

   442         have = strm->avail_in; \

   443         hold = state->hold; \

   444         bits = state->bits; \

   445     } while (0)

   446 

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

   448 #define RESTORE() \

   449     do { \

   450         strm->next_out = put; \

   451         strm->avail_out = left; \

   452         strm->next_in = next; \

   453         strm->avail_in = have; \

   454         state->hold = hold; \

   455         state->bits = bits; \

   456     } while (0)

   457 

   458 /* Clear the input bit accumulator */

   459 #define INITBITS() \

   460     do { \

   461         hold = 0; \

   462         bits = 0; \

   463     } while (0)

   464 

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

   466    if there is no input available. */

   467 #define PULLBYTE() \

   468     do { \

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

   470         have--; \

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

   472         bits += 8; \

   473     } while (0)

   474 

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

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

   477 #define NEEDBITS(n) \

   478     do { \

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

   480             PULLBYTE(); \

   481     } while (0)

   482 

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

   484 #define BITS(n) \

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

   486 

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

   488 #define DROPBITS(n) \

   489     do { \

   490         hold >>= (n); \

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

   492     } while (0)

   493 

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

   495 #define BYTEBITS() \

   496     do { \

   497         hold >>= bits & 7; \

   498         bits -= bits & 7; \

   499     } while (0)

   500 

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

   502 #define REVERSE(q) \

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

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

   505 

   506 

   507 /*

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

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

   510    structured roughly as follows:

   511 

   512     for (;;) switch (state) {

   513     ...

   514     case STATEn:

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

   516             return;

   517         ... make progress ...

   518         state = STATEm;

   519         break;

   520     ...

   521     }

   522 

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

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

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

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

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

   528    is:

   529 

   530         NEEDBITS(n);

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

   532         DROPBITS(n);

   533 

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

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

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

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

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

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

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

   541 

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

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

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

   545    code, and no more.

   546 

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

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

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

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

   551    returns:

   552 

   553     case STATEw:

   554         while (want < need) {

   555             NEEDBITS(n);

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

   557             DROPBITS(n);

   558         }

   559         state = STATEx;

   560     case STATEx:

   561 

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

   563    is omitted.

   564 

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

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

   567    literal byte, and copying a matching string.

   568 

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

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

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

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

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

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

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

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

   577 

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

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

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

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

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

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

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

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

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

   587  */

   588 #ifdef __SYMBIAN32__

   589 EXPORT_C  int inflate_r (z_streamp strm,int  flush)

   590 #else

   591 int ZEXPORT inflate(strm, flush)

   592 z_streamp strm;

   593 int flush;

   594 #endif //__SYMBIAN32__

   595 {

   596     struct inflate_state FAR *state;

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

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

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

   600     unsigned long hold;         /* bit buffer */

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

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

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

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

   605     

   606 /*  Need to replace "this" variable with "current" as "this" is a reserved 

   607  *  keyword in C++ which is prefectly fine for a c code. As this file

   608  *  has been changed to C++ "this" needs to be changed.

   609  */ 

   610 #   define this current   

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

   612     code last;                  /* parent table entry */

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

   614     int ret;                    /* return code */

   615 #ifdef GUNZIP

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

   617 #endif

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

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

   620 

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

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

   623         return Z_STREAM_ERROR;

   624 

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

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

   627     LOAD();

   628     in = have;

   629     out = left;

   630     ret = Z_OK;

   631     for (;;)

   632         switch (state->mode) {

   633         case HEAD:

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

   635                 state->mode = TYPEDO;

   636                 break;

   637             }

   638             NEEDBITS(16);

   639 #ifdef GUNZIP

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

   641                 state->check = crc32_r(0L, Z_NULL, 0);

   642                 CRC2(state->check, hold);

   643                 INITBITS();

   644                 state->mode = FLAGS;

   645                 break;

   646             }

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

   648             if (state->head != Z_NULL)

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

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

   651 #else

   652             if (

   653 #endif

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

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

   656                 state->mode = BAD;

   657                 break;

   658             }

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

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

   661                 state->mode = BAD;

   662                 break;

   663             }

   664             DROPBITS(4);

   665             len = BITS(4) + 8;

   666             if (len > state->wbits) {

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

   668                 state->mode = BAD;

   669                 break;

   670             }

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

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

   673             strm->adler = state->check = adler32_r(0L, Z_NULL, 0);

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

   675             INITBITS();

   676             break;

   677 #ifdef GUNZIP

   678         case FLAGS:

   679             NEEDBITS(16);

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

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

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

   683                 state->mode = BAD;

   684                 break;

   685             }

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

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

   688                 state->mode = BAD;

   689                 break;

   690             }

   691             if (state->head != Z_NULL)

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

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

   694             INITBITS();

   695             state->mode = TIME;

   696         case TIME:

   697             NEEDBITS(32);

   698             if (state->head != Z_NULL)

   699                 state->head->time = hold;

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

   701             INITBITS();

   702             state->mode = OS;

   703         case OS:

   704             NEEDBITS(16);

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

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

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

   708             }

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

   710             INITBITS();

   711             state->mode = EXLEN;

   712         case EXLEN:

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

   714                 NEEDBITS(16);

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

   716                 if (state->head != Z_NULL)

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

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

   719                 INITBITS();

   720             }

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

   722                 state->head->extra = Z_NULL;

   723             state->mode = EXTRA;

   724         case EXTRA:

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

   726                 copy = state->length;

   727                 if (copy > have) copy = have;

   728                 if (copy) {

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

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

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

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

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

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

   735                     }

   736                     if (state->flags & 0x0200)

   737                         state->check = crc32_r(state->check, next, copy);

   738                     have -= copy;

   739                     next += copy;

   740                     state->length -= copy;

   741                 }

   742                 if (state->length) goto inf_leave;

   743             }

   744             state->length = 0;

   745             state->mode = NAME;

   746         case NAME:

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

   748                 if (have == 0) goto inf_leave;

   749                 copy = 0;

   750                 do {

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

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

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

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

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

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

   757                 if (state->flags & 0x0200)

   758                     state->check = crc32_r(state->check, next, copy);

   759                 have -= copy;

   760                 next += copy;

   761                 if (len) goto inf_leave;

   762             }

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

   764                 state->head->name = Z_NULL;

   765             state->length = 0;

   766             state->mode = COMMENT;

   767         case COMMENT:

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

   769                 if (have == 0) goto inf_leave;

   770                 copy = 0;

   771                 do {

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

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

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

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

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

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

   778                 if (state->flags & 0x0200)

   779                     state->check = crc32_r(state->check, next, copy);

   780                 have -= copy;

   781                 next += copy;

   782                 if (len) goto inf_leave;

   783             }

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

   785                 state->head->comment = Z_NULL;

   786             state->mode = HCRC;

   787         case HCRC:

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

   789                 NEEDBITS(16);

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

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

   792                     state->mode = BAD;

   793                     break;

   794                 }

   795                 INITBITS();

   796             }

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

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

   799                 state->head->done = 1;

   800             }

   801             strm->adler = state->check = crc32_r(0L, Z_NULL, 0);

   802             state->mode = TYPE;

   803             break;

   804 #endif

   805         case DICTID:

   806             NEEDBITS(32);

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

   808             INITBITS();

   809             state->mode = DICT;

   810         case DICT:

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

   812                 RESTORE();

   813                 return Z_NEED_DICT;

   814             }

   815             strm->adler = state->check = adler32_r(0L, Z_NULL, 0);

   816             state->mode = TYPE;

   817         case TYPE:

   818             if (flush == Z_BLOCK) goto inf_leave;

   819         case TYPEDO:

   820             if (state->last) {

   821                 BYTEBITS();

   822                 state->mode = CHECK;

   823                 break;

   824             }

   825             NEEDBITS(3);

   826             state->last = BITS(1);

   827             DROPBITS(1);

   828             switch (BITS(2)) {

   829             case 0:                             /* stored block */

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

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

   832                 state->mode = STORED;

   833                 break;

   834             case 1:                             /* fixed block */

   835                 fixedtables(state);

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

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

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

   839                 break;

   840             case 2:                             /* dynamic block */

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

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

   843                 state->mode = TABLE;

   844                 break;

   845             case 3:

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

   847                 state->mode = BAD;

   848             }

   849             DROPBITS(2);

   850             break;

   851         case STORED:

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

   853             NEEDBITS(32);

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

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

   856                 state->mode = BAD;

   857                 break;

   858             }

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

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

   861                     state->length));

   862             INITBITS();

   863             state->mode = COPY;

   864         case COPY:

   865             copy = state->length;

   866             if (copy) {

   867                 if (copy > have) copy = have;

   868                 if (copy > left) copy = left;

   869                 if (copy == 0) goto inf_leave;

   870                 zmemcpy(put, next, copy);

   871                 have -= copy;

   872                 next += copy;

   873                 left -= copy;

   874                 put += copy;

   875                 state->length -= copy;

   876                 break;

   877             }

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

   879             state->mode = TYPE;

   880             break;

   881         case TABLE:

   882             NEEDBITS(14);

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

   884             DROPBITS(5);

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

   886             DROPBITS(5);

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

   888             DROPBITS(4);

   889 #ifndef PKZIP_BUG_WORKAROUND

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

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

   892                 state->mode = BAD;

   893                 break;

   894             }

   895 #endif

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

   897             state->have = 0;

   898             state->mode = LENLENS;

   899         case LENLENS:

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

   901                 NEEDBITS(3);

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

   903                 DROPBITS(3);

   904             }

   905             while (state->have < 19)

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

   907             state->next = state->codes;

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

   909             state->lenbits = 7;

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

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

   912             if (ret) {

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

   914                 state->mode = BAD;

   915                 break;

   916             }

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

   918             state->have = 0;

   919             state->mode = CODELENS;

   920         case CODELENS:

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

   922                 for (;;) {

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

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

   925                     PULLBYTE();

   926                 }

   927                 if (this.val < 16) {

   928                     NEEDBITS(this.bits);

   929                     DROPBITS(this.bits);

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

   931                 }

   932                 else {

   933                     if (this.val == 16) {

   934                         NEEDBITS(this.bits + 2);

   935                         DROPBITS(this.bits);

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

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

   938                             state->mode = BAD;

   939                             break;

   940                         }

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

   942                         copy = 3 + BITS(2);

   943                         DROPBITS(2);

   944                     }

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

   946                         NEEDBITS(this.bits + 3);

   947                         DROPBITS(this.bits);

   948                         len = 0;

   949                         copy = 3 + BITS(3);

   950                         DROPBITS(3);

   951                     }

   952                     else {

   953                         NEEDBITS(this.bits + 7);

   954                         DROPBITS(this.bits);

   955                         len = 0;

   956                         copy = 11 + BITS(7);

   957                         DROPBITS(7);

   958                     }

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

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

   961                         state->mode = BAD;

   962                         break;

   963                     }

   964                     while (copy--)

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

   966                 }

   967             }

   968 

   969             /* handle error breaks in while */

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

   971 

   972             /* build code tables */

   973             state->next = state->codes;

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

   975             state->lenbits = 9;

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

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

   978             if (ret) {

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

   980                 state->mode = BAD;

   981                 break;

   982             }

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

   984             state->distbits = 6;

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

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

   987             if (ret) {

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

   989                 state->mode = BAD;

   990                 break;

   991             }

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

   993             state->mode = LEN;

   994         case LEN:

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

   996                 RESTORE();

   997                 inflate_fast(strm, out);

   998                 LOAD();

   999                 break;

  1000             }

  1001             for (;;) {

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

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

  1004                 PULLBYTE();

  1005             }

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

  1007                 last = this;

  1008                 for (;;) {

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

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

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

  1012                     PULLBYTE();

  1013                 }

  1014                 DROPBITS(last.bits);

  1015             }

  1016             DROPBITS(this.bits);

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

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

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

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

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

  1022                 state->mode = LIT;

  1023                 break;

  1024             }

  1025             if (this.op & 32) {

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

  1027                 state->mode = TYPE;

  1028                 break;

  1029             }

  1030             if (this.op & 64) {

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

  1032                 state->mode = BAD;

  1033                 break;

  1034             }

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

  1036             state->mode = LENEXT;

  1037         case LENEXT:

  1038             if (state->extra) {

  1039                 NEEDBITS(state->extra);

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

  1041                 DROPBITS(state->extra);

  1042             }

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

  1044             state->mode = DIST;

  1045         case DIST:

  1046             for (;;) {

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

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

  1049                 PULLBYTE();

  1050             }

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

  1052                 last = this;

  1053                 for (;;) {

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

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

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

  1057                     PULLBYTE();

  1058                 }

  1059                 DROPBITS(last.bits);

  1060             }

  1061             DROPBITS(this.bits);

  1062             if (this.op & 64) {

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

  1064                 state->mode = BAD;

  1065                 break;

  1066             }

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

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

  1069             state->mode = DISTEXT;

  1070         case DISTEXT:

  1071             if (state->extra) {

  1072                 NEEDBITS(state->extra);

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

  1074                 DROPBITS(state->extra);

  1075             }

  1076 #ifdef INFLATE_STRICT

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

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

  1079                 state->mode = BAD;

  1080                 break;

  1081             }

  1082 #endif

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

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

  1085                 state->mode = BAD;

  1086                 break;

  1087             }

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

  1089             state->mode = MATCH;

  1090         case MATCH:

  1091             if (left == 0) goto inf_leave;

  1092             copy = out - left;

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

  1094                 copy = state->offset - copy;

  1095                 if (copy > state->write) {

  1096                     copy -= state->write;

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

  1098                 }

  1099                 else

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

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

  1102             }

  1103             else {                              /* copy from output */

  1104                 from = put - state->offset;

  1105                 copy = state->length;

  1106             }

  1107             if (copy > left) copy = left;

  1108             left -= copy;

  1109             state->length -= copy;

  1110             do {

  1111                 *put++ = *from++;

  1112             } while (--copy);

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

  1114             break;

  1115         case LIT:

  1116             if (left == 0) goto inf_leave;

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

  1118             left--;

  1119             state->mode = LEN;

  1120             break;

  1121         case CHECK:

  1122             if (state->wrap) {

  1123                 NEEDBITS(32);

  1124                 out -= left;

  1125                 strm->total_out += out;

  1126                 state->total += out;

  1127                 if (out)

  1128                     strm->adler = state->check =

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

  1130                 out = left;

  1131                 if ((

  1132 #ifdef GUNZIP

  1133                      state->flags ? hold :

  1134 #endif

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