1 /*

     2  * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.

     3  *

     4  * This code is free software; you can redistribute it and/or modify it

     5  * under the terms of the GNU General Public License version 2 only, as

     6  * published by the Free Software Foundation.  Oracle designates this

     7  * particular file as subject to the "Classpath" exception as provided

     8  * by Oracle in the LICENSE file that accompanied this code.

     9  *

    10  * This code is distributed in the hope that it will be useful, but WITHOUT

    11  * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or

    12  * FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License

    13  * version 2 for more details (a copy is included in the LICENSE file that

    14  * accompanied this code).

    15  *

    16  * You should have received a copy of the GNU General Public License version

    17  * 2 along with this work; if not, write to the Free Software Foundation,

    18  * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.

    19  *

    20  * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA

    21  * or visit www.oracle.com if you need additional information or have any

    22  * questions.

    23  */

    24 

    25 /* inflate.c -- zlib decompression

    26  * Copyright (C) 1995-2012 Mark Adler

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

    28  */

    29 

    30 /*

    31  * Change history:

    32  *

    33  * 1.2.beta0    24 Nov 2002

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

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

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

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

    38  *

    39  * 1.2.beta1    25 Nov 2002

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

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

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

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

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

    45  *

    46  * 1.2.beta2    4 Dec 2002

    47  * - Change external routine names to reduce potential conflicts

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

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

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

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

    52  *

    53  * 1.2.beta3    22 Dec 2002

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

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

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

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

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

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

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

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

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

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

    64  *

    65  * 1.2.beta4    1 Jan 2003

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

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

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

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

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

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

    72  * - Pull out common wnext == 0 case for speed in inflate_fast()

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

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

    75  * - Simplified bad distance check in inflate_fast()

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

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

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

    79  *   window copying

    80  *

    81  * 1.2.beta5    1 Jan 2003

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

    83  *   input in strm.

    84  * - Fixed stored blocks bug in inflateBack()

    85  *

    86  * 1.2.beta6    4 Jan 2003

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

    88  * - Typecasting all around to reduce compiler warnings

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

    90  *   make compilers happy

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

    92  *

    93  * 1.2.beta7    27 Jan 2003

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

    95  * - Added inflateCopy() function

    96  *

    97  * 1.2.0        9 Mar 2003

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

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

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

   101  *   and buffer address return values for the input function

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

   103  *

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

   105  */

   106 

   107 #include "zutil.h"

   108 #include "inftrees.h"

   109 #include "inflate.h"

   110 #include "inffast.h"

   111 

   112 #ifdef MAKEFIXED

   113 #  ifndef BUILDFIXED

   114 #    define BUILDFIXED

   115 #  endif

   116 #endif

   117 

   118 /* function prototypes */

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

   120 local int updatewindow OF((z_streamp strm, const unsigned char FAR *end,

   121                            unsigned copy));

   122 #ifdef BUILDFIXED

   123    void makefixed OF((void));

   124 #endif

   125 local unsigned syncsearch OF((unsigned FAR *have, const unsigned char FAR *buf,

   126                               unsigned len));

   127 

   128 int ZEXPORT inflateResetKeep(strm)

   129 z_streamp strm;

   130 {

   131     struct inflate_state FAR *state;

   132 

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

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

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

   136     strm->msg = Z_NULL;

   137     if (state->wrap)        /* to support ill-conceived Java test suite */

   138         strm->adler = state->wrap & 1;

   139     state->mode = HEAD;

   140     state->last = 0;

   141     state->havedict = 0;

   142     state->dmax = 32768U;

   143     state->head = Z_NULL;

   144     state->hold = 0;

   145     state->bits = 0;

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

   147     state->sane = 1;

   148     state->back = -1;

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

   150     return Z_OK;

   151 }

   152 

   153 int ZEXPORT inflateReset(strm)

   154 z_streamp strm;

   155 {

   156     struct inflate_state FAR *state;

   157 

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

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

   160     state->wsize = 0;

   161     state->whave = 0;

   162     state->wnext = 0;

   163     return inflateResetKeep(strm);

   164 }

   165 

   166 int ZEXPORT inflateReset2(strm, windowBits)

   167 z_streamp strm;

   168 int windowBits;

   169 {

   170     int wrap;

   171     struct inflate_state FAR *state;

   172 

   173     /* get the state */

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

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

   176 

   177     /* extract wrap request from windowBits parameter */

   178     if (windowBits < 0) {

   179         wrap = 0;

   180         windowBits = -windowBits;

   181     }

   182     else {

   183         wrap = (windowBits >> 4) + 1;

   184 #ifdef GUNZIP

   185         if (windowBits < 48)

   186             windowBits &= 15;

   187 #endif

   188     }

   189 

   190     /* set number of window bits, free window if different */

   191     if (windowBits && (windowBits < 8 || windowBits > 15))

   192         return Z_STREAM_ERROR;

   193     if (state->window != Z_NULL && state->wbits != (unsigned)windowBits) {

   194         ZFREE(strm, state->window);

   195         state->window = Z_NULL;

   196     }

   197 

   198     /* update state and reset the rest of it */

   199     state->wrap = wrap;

   200     state->wbits = (unsigned)windowBits;

   201     return inflateReset(strm);

   202 }

   203 

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

   205 z_streamp strm;

   206 int windowBits;

   207 const char *version;

   208 int stream_size;

   209 {

   210     int ret;

   211     struct inflate_state FAR *state;

   212 

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

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

   215         return Z_VERSION_ERROR;

   216     if (strm == Z_NULL) return Z_STREAM_ERROR;

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

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

   219 #ifdef Z_SOLO

   220         return Z_STREAM_ERROR;

   221 #else

   222         strm->zalloc = zcalloc;

   223         strm->opaque = (voidpf)0;

   224 #endif

   225     }

   226     if (strm->zfree == (free_func)0)

   227 #ifdef Z_SOLO

   228         return Z_STREAM_ERROR;

   229 #else

   230         strm->zfree = zcfree;

   231 #endif

   232     state = (struct inflate_state FAR *)

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

   234     if (state == Z_NULL) return Z_MEM_ERROR;

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

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

   237     state->window = Z_NULL;

   238     ret = inflateReset2(strm, windowBits);

   239     if (ret != Z_OK) {

   240         ZFREE(strm, state);

   241         strm->state = Z_NULL;

   242     }

   243     return ret;

   244 }

   245 

   246 int ZEXPORT inflateInit_(strm, version, stream_size)

   247 z_streamp strm;

   248 const char *version;

   249 int stream_size;

   250 {

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

   252 }

   253 

   254 int ZEXPORT inflatePrime(strm, bits, value)

   255 z_streamp strm;

   256 int bits;

   257 int value;

   258 {

   259     struct inflate_state FAR *state;

   260 

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

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

   263     if (bits < 0) {

   264         state->hold = 0;

   265         state->bits = 0;

   266         return Z_OK;

   267     }

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

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

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

   271     state->bits += bits;

   272     return Z_OK;

   273 }

   274 

   275 /*

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

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

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

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

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

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

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

   283    may not be thread-safe.

   284  */

   285 local void fixedtables(state)

   286 struct inflate_state FAR *state;

   287 {

   288 #ifdef BUILDFIXED

   289     static int virgin = 1;

   290     static code *lenfix, *distfix;

   291     static code fixed[544];

   292 

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

   294     if (virgin) {

   295         unsigned sym, bits;

   296         static code *next;

   297 

   298         /* literal/length table */

   299         sym = 0;

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

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

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

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

   304         next = fixed;

   305         lenfix = next;

   306         bits = 9;

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

   308 

   309         /* distance table */

   310         sym = 0;

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

   312         distfix = next;

   313         bits = 5;

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

   315 

   316         /* do this just once */

   317         virgin = 0;

   318     }

   319 #else /* !BUILDFIXED */

   320 #   include "inffixed.h"

   321 #endif /* BUILDFIXED */

   322     state->lencode = lenfix;

   323     state->lenbits = 9;

   324     state->distcode = distfix;

   325     state->distbits = 5;

   326 }

   327 

   328 #ifdef MAKEFIXED

   329 #include <stdio.h>

   330 

   331 /*

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

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

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

   335    can simply call makefixed to do this:

   336 

   337     void makefixed(void);

   338 

   339     int main(void)

   340     {

   341         makefixed();

   342         return 0;

   343     }

   344 

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

   346 

   347     a.out > inffixed.h

   348  */

   349 void makefixed()

   350 {

   351     unsigned low, size;

   352     struct inflate_state state;

   353 

   354     fixedtables(&state);

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

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

   357     puts("     */");

   358     puts("");

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

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

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

   362     puts("     */");

   363     puts("");

   364     size = 1U << 9;

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

   366     low = 0;

   367     for (;;) {

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

   369         printf("{%u,%u,%d}", (low & 127) == 99 ? 64 : state.lencode[low].op,

   370                state.lencode[low].bits, state.lencode[low].val);

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

   372         putchar(',');

   373     }

   374     puts("\n    };");

   375     size = 1U << 5;

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

   377     low = 0;

   378     for (;;) {

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

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

   381                state.distcode[low].val);

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

   383         putchar(',');

   384     }

   385     puts("\n    };");

   386 }

   387 #endif /* MAKEFIXED */

   388 

   389 /*

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

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

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

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

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

   395    is loaded.

   396 

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

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

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

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

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

   402  */

   403 local int updatewindow(strm, end, copy)

   404 z_streamp strm;

   405 const Bytef *end;

   406 unsigned copy;

   407 {

   408     struct inflate_state FAR *state;

   409     unsigned dist;

   410 

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

   412 

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

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

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

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

   417                                sizeof(unsigned char));

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

   419     }

   420 

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

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

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

   424         state->wnext = 0;

   425         state->whave = 0;

   426     }

   427 

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

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

   430         zmemcpy(state->window, end - state->wsize, state->wsize);

   431         state->wnext = 0;

   432         state->whave = state->wsize;

   433     }

   434     else {

   435         dist = state->wsize - state->wnext;

   436         if (dist > copy) dist = copy;

   437         zmemcpy(state->window + state->wnext, end - copy, dist);

   438         copy -= dist;

   439         if (copy) {

   440             zmemcpy(state->window, end - copy, copy);

   441             state->wnext = copy;

   442             state->whave = state->wsize;

   443         }

   444         else {

   445             state->wnext += dist;

   446             if (state->wnext == state->wsize) state->wnext = 0;

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

   448         }

   449     }

   450     return 0;

   451 }

   452 

   453 /* Macros for inflate(): */

   454 

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

   456 #ifdef GUNZIP

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

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

   459 #else

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

   461 #endif

   462 

   463 /* check macros for header crc */

   464 #ifdef GUNZIP

   465 #  define CRC2(check, word) \

   466     do { \

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

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

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

   470     } while (0)

   471 

   472 #  define CRC4(check, word) \

   473     do { \

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

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

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

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

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

   479     } while (0)

   480 #endif

   481 

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

   483 #define LOAD() \

   484     do { \

   485         put = strm->next_out; \

   486         left = strm->avail_out; \

   487         next = strm->next_in; \

   488         have = strm->avail_in; \

   489         hold = state->hold; \

   490         bits = state->bits; \

   491     } while (0)

   492 

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

   494 #define RESTORE() \

   495     do { \

   496         strm->next_out = put; \

   497         strm->avail_out = left; \

   498         strm->next_in = next; \

   499         strm->avail_in = have; \

   500         state->hold = hold; \

   501         state->bits = bits; \

   502     } while (0)

   503 

   504 /* Clear the input bit accumulator */

   505 #define INITBITS() \

   506     do { \

   507         hold = 0; \

   508         bits = 0; \

   509     } while (0)

   510 

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

   512    if there is no input available. */

   513 #define PULLBYTE() \

   514     do { \

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

   516         have--; \

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

   518         bits += 8; \

   519     } while (0)

   520 

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

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

   523 #define NEEDBITS(n) \

   524     do { \

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

   526             PULLBYTE(); \

   527     } while (0)

   528 

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

   530 #define BITS(n) \

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

   532 

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

   534 #define DROPBITS(n) \

   535     do { \

   536         hold >>= (n); \

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

   538     } while (0)

   539 

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

   541 #define BYTEBITS() \

   542     do { \

   543         hold >>= bits & 7; \

   544         bits -= bits & 7; \

   545     } while (0)

   546 

   547 /*

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

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

   550    structured roughly as follows:

   551 

   552     for (;;) switch (state) {

   553     ...

   554     case STATEn:

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

   556             return;

   557         ... make progress ...

   558         state = STATEm;

   559         break;

   560     ...

   561     }

   562 

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

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

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

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

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

   568    is:

   569 

   570         NEEDBITS(n);

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

   572         DROPBITS(n);

   573 

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

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

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

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

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

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

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

   581 

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

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

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

   585    code, and no more.

   586 

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

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

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

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

   591    returns:

   592 

   593     case STATEw:

   594         while (want < need) {

   595             NEEDBITS(n);

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

   597             DROPBITS(n);

   598         }

   599         state = STATEx;

   600     case STATEx:

   601 

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

   603    is omitted.

   604 

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

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

   607    literal byte, and copying a matching string.

   608 

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

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

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

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

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

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

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

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

   617 

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

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

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

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

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

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

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

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

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

   627  */

   628 

   629 int ZEXPORT inflate(strm, flush)

   630 z_streamp strm;

   631 int flush;

   632 {

   633     struct inflate_state FAR *state;

   634     z_const unsigned char FAR *next;    /* next input */

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

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

   637     unsigned long hold;         /* bit buffer */

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

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

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

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

   642     code here;                  /* current decoding table entry */

   643     code last;                  /* parent table entry */

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

   645     int ret;                    /* return code */

   646 #ifdef GUNZIP

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

   648 #endif

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

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

   651 

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

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

   654         return Z_STREAM_ERROR;

   655 

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

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

   658     LOAD();

   659     in = have;

   660     out = left;

   661     ret = Z_OK;

   662     for (;;)

   663         switch (state->mode) {

   664         case HEAD:

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

   666                 state->mode = TYPEDO;

   667                 break;

   668             }

   669             NEEDBITS(16);

   670 #ifdef GUNZIP

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

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

   673                 CRC2(state->check, hold);

   674                 INITBITS();

   675                 state->mode = FLAGS;

   676                 break;

   677             }

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

   679             if (state->head != Z_NULL)

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

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

   682 #else

   683             if (

   684 #endif

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

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

   687                 state->mode = BAD;

   688                 break;

   689             }

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

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

   692                 state->mode = BAD;

   693                 break;

   694             }

   695             DROPBITS(4);

   696             len = BITS(4) + 8;

   697             if (state->wbits == 0)

   698                 state->wbits = len;

   699             else if (len > state->wbits) {

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

   701                 state->mode = BAD;

   702                 break;

   703             }

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

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

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

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

   708             INITBITS();

   709             break;

   710 #ifdef GUNZIP

   711         case FLAGS:

   712             NEEDBITS(16);

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

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

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

   716                 state->mode = BAD;

   717                 break;

   718             }

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

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

   721                 state->mode = BAD;

   722                 break;

   723             }

   724             if (state->head != Z_NULL)

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

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

   727             INITBITS();

   728             state->mode = TIME;

   729         case TIME:

   730             NEEDBITS(32);

   731             if (state->head != Z_NULL)

   732                 state->head->time = hold;

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

   734             INITBITS();

   735             state->mode = OS;

   736         case OS:

   737             NEEDBITS(16);

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

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

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

   741             }

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

   743             INITBITS();

   744             state->mode = EXLEN;

   745         case EXLEN:

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

   747                 NEEDBITS(16);

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

   749                 if (state->head != Z_NULL)

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

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

   752                 INITBITS();

   753             }

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

   755                 state->head->extra = Z_NULL;

   756             state->mode = EXTRA;

   757         case EXTRA:

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

   759                 copy = state->length;

   760                 if (copy > have) copy = have;

   761                 if (copy) {

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

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

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

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

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

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

   768                     }

   769                     if (state->flags & 0x0200)

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

   771                     have -= copy;

   772                     next += copy;

   773                     state->length -= copy;

   774                 }

   775                 if (state->length) goto inf_leave;

   776             }

   777             state->length = 0;

   778             state->mode = NAME;

   779         case NAME:

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

   781                 if (have == 0) goto inf_leave;

   782                 copy = 0;

   783                 do {

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

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

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

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

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

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

   790                 if (state->flags & 0x0200)

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

   792                 have -= copy;

   793                 next += copy;

   794                 if (len) goto inf_leave;

   795             }

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

   797                 state->head->name = Z_NULL;

   798             state->length = 0;

   799             state->mode = COMMENT;

   800         case COMMENT:

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

   802                 if (have == 0) goto inf_leave;

   803                 copy = 0;

   804                 do {

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

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

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

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

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

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

   811                 if (state->flags & 0x0200)

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

   813                 have -= copy;

   814                 next += copy;

   815                 if (len) goto inf_leave;

   816             }

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

   818                 state->head->comment = Z_NULL;

   819             state->mode = HCRC;

   820         case HCRC:

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

   822                 NEEDBITS(16);

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

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

   825                     state->mode = BAD;

   826                     break;

   827                 }

   828                 INITBITS();

   829             }

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

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

   832                 state->head->done = 1;

   833             }

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

   835             state->mode = TYPE;

   836             break;

   837 #endif

   838         case DICTID:

   839             NEEDBITS(32);

   840             strm->adler = state->check = ZSWAP32(hold);

   841             INITBITS();

   842             state->mode = DICT;

   843         case DICT:

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

   845                 RESTORE();

   846                 return Z_NEED_DICT;

   847             }

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

   849             state->mode = TYPE;

   850         case TYPE:

   851             if (flush == Z_BLOCK || flush == Z_TREES) goto inf_leave;

   852         case TYPEDO:

   853             if (state->last) {

   854                 BYTEBITS();

   855                 state->mode = CHECK;

   856                 break;

   857             }

   858             NEEDBITS(3);

   859             state->last = BITS(1);

   860             DROPBITS(1);

   861             switch (BITS(2)) {

   862             case 0:                             /* stored block */

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

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

   865                 state->mode = STORED;

   866                 break;

   867             case 1:                             /* fixed block */

   868                 fixedtables(state);

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

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

   871                 state->mode = LEN_;             /* decode codes */

   872                 if (flush == Z_TREES) {

   873                     DROPBITS(2);

   874                     goto inf_leave;

   875                 }

   876                 break;

   877             case 2:                             /* dynamic block */

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

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

   880                 state->mode = TABLE;

   881                 break;

   882             case 3:

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

   884                 state->mode = BAD;

   885             }

   886             DROPBITS(2);

   887             break;

   888         case STORED:

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

   890             NEEDBITS(32);

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

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

   893                 state->mode = BAD;

   894                 break;

   895             }

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

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

   898                     state->length));

   899             INITBITS();

   900             state->mode = COPY_;

   901             if (flush == Z_TREES) goto inf_leave;

   902         case COPY_:

   903             state->mode = COPY;

   904         case COPY:

   905             copy = state->length;

   906             if (copy) {

   907                 if (copy > have) copy = have;

   908                 if (copy > left) copy = left;

   909                 if (copy == 0) goto inf_leave;

   910                 zmemcpy(put, next, copy);

   911                 have -= copy;

   912                 next += copy;

   913                 left -= copy;

   914                 put += copy;

   915                 state->length -= copy;

   916                 break;

   917             }

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

   919             state->mode = TYPE;

   920             break;

   921         case TABLE:

   922             NEEDBITS(14);

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

   924             DROPBITS(5);

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

   926             DROPBITS(5);

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

   928             DROPBITS(4);

   929 #ifndef PKZIP_BUG_WORKAROUND

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

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

   932                 state->mode = BAD;

   933                 break;

   934             }

   935 #endif

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

   937             state->have = 0;

   938             state->mode = LENLENS;

   939         case LENLENS:

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

   941                 NEEDBITS(3);

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

   943                 DROPBITS(3);

   944             }

   945             while (state->have < 19)

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

   947             state->next = state->codes;

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

   949             state->lenbits = 7;

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

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

   952             if (ret) {

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

   954                 state->mode = BAD;

   955                 break;

   956             }

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

   958             state->have = 0;

   959             state->mode = CODELENS;

   960         case CODELENS:

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

   962                 for (;;) {

   963                     here = state->lencode[BITS(state->lenbits)];

   964                     if ((unsigned)(here.bits) <= bits) break;

   965                     PULLBYTE();

   966                 }

   967                 if (here.val < 16) {

   968                     DROPBITS(here.bits);

   969                     state->lens[state->have++] = here.val;

   970                 }

   971                 else {

   972                     if (here.val == 16) {

   973                         NEEDBITS(here.bits + 2);

   974                         DROPBITS(here.bits);

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

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

   977                             state->mode = BAD;

   978                             break;

   979                         }

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

   981                         copy = 3 + BITS(2);

   982                         DROPBITS(2);

   983                     }

   984                     else if (here.val == 17) {

   985                         NEEDBITS(here.bits + 3);

   986                         DROPBITS(here.bits);

   987                         len = 0;

   988                         copy = 3 + BITS(3);

   989                         DROPBITS(3);

   990                     }

   991                     else {

   992                         NEEDBITS(here.bits + 7);

   993                         DROPBITS(here.bits);

   994                         len = 0;

   995                         copy = 11 + BITS(7);

   996                         DROPBITS(7);

   997                     }

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

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

  1000                         state->mode = BAD;

  1001                         break;

  1002                     }

  1003                     while (copy--)

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

  1005                 }

  1006             }

  1007 

  1008             /* handle error breaks in while */

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

  1010 

  1011             /* check for end-of-block code (better have one) */

  1012             if (state->lens[256] == 0) {

  1013                 strm->msg = (char *)"invalid code -- missing end-of-block";

  1014                 state->mode = BAD;

  1015                 break;

  1016             }

  1017 

  1018             /* build code tables -- note: do not change the lenbits or distbits

  1019                values here (9 and 6) without reading the comments in inftrees.h

  1020                concerning the ENOUGH constants, which depend on those values */

  1021             state->next = state->codes;

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

  1023             state->lenbits = 9;

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

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

  1026             if (ret) {

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

  1028                 state->mode = BAD;

  1029                 break;

  1030             }

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

  1032             state->distbits = 6;

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

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

  1035             if (ret) {

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

  1037                 state->mode = BAD;

  1038                 break;

  1039             }

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

  1041             state->mode = LEN_;

  1042             if (flush == Z_TREES) goto inf_leave;

  1043         case LEN_:

  1044             state->mode = LEN;

  1045         case LEN:

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

  1047                 RESTORE();

  1048                 inflate_fast(strm, out);

  1049                 LOAD();

  1050                 if (state->mode == TYPE)

  1051                     state->back = -1;

  1052                 break;

  1053             }

  1054             state->back = 0;

  1055             for (;;) {

  1056                 here = state->lencode[BITS(state->lenbits)];

  1057                 if ((unsigned)(here.bits) <= bits) break;

  1058                 PULLBYTE();

  1059             }

  1060             if (here.op && (here.op & 0xf0) == 0) {

  1061                 last = here;

  1062                 for (;;) {

  1063                     here = state->lencode[last.val +

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

  1065                     if ((unsigned)(last.bits + here.bits) <= bits) break;

  1066                     PULLBYTE();

  1067                 }

  1068                 DROPBITS(last.bits);

  1069                 state->back += last.bits;

  1070             }

  1071             DROPBITS(here.bits);

  1072             state->back += here.bits;

  1073             state->length = (unsigned)here.val;

  1074             if ((int)(here.op) == 0) {

  1075                 Tracevv((stderr, here.val >= 0x20 && here.val < 0x7f ?

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

  1077                         "inflate:         literal 0x%02x\n", here.val));

  1078                 state->mode = LIT;

  1079                 break;

  1080             }

  1081             if (here.op & 32) {

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

  1083                 state->back = -1;

  1084                 state->mode = TYPE;

  1085                 break;

  1086             }

  1087             if (here.op & 64) {

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

  1089                 state->mode = BAD;

  1090                 break;

  1091             }

  1092             state->extra = (unsigned)(here.op) & 15;

  1093             state->mode = LENEXT;

  1094         case LENEXT:

  1095             if (state->extra) {

  1096                 NEEDBITS(state->extra);

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

  1098                 DROPBITS(state->extra);

  1099                 state->back += state->extra;

  1100             }

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

  1102             state->was = state->length;

  1103             state->mode = DIST;

  1104         case DIST:

  1105             for (;;) {

  1106                 here = state->distcode[BITS(state->distbits)];

  1107                 if ((unsigned)(here.bits) <= bits) break;

  1108                 PULLBYTE();

  1109             }

  1110             if ((here.op & 0xf0) == 0) {

  1111                 last = here;

  1112                 for (;;) {

  1113                     here = state->distcode[last.val +

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

  1115                     if ((unsigned)(last.bits + here.bits) <= bits) break;

  1116                     PULLBYTE();

  1117                 }

  1118                 DROPBITS(last.bits);

  1119                 state->back += last.bits;

  1120             }

  1121             DROPBITS(here.bits);

  1122             state->back += here.bits;

  1123             if (here.op & 64) {

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

  1125                 state->mode = BAD;

  1126                 break;

  1127             }

  1128             state->offset = (unsigned)here.val;

  1129             state->extra = (unsigned)(here.op) & 15;

  1130             state->mode = DISTEXT;

  1131         case DISTEXT:

  1132             if (state->extra) {

  1133                 NEEDBITS(state->extra);

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