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 /* infback.c -- inflate using a call-back interface

    26  * Copyright (C) 1995-2009 Mark Adler

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

    28  */

    29 

    30 /*

    31    This code is largely copied from inflate.c.  Normally either infback.o or

    32    inflate.o would be linked into an application--not both.  The interface

    33    with inffast.c is retained so that optimized assembler-coded versions of

    34    inflate_fast() can be used with either inflate.c or infback.c.

    35  */

    36 

    37 #include "zutil.h"

    38 #include "inftrees.h"

    39 #include "inflate.h"

    40 #include "inffast.h"

    41 

    42 /* function prototypes */

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

    44 

    45 /*

    46    strm provides memory allocation functions in zalloc and zfree, or

    47    Z_NULL to use the library memory allocation functions.

    48 

    49    windowBits is in the range 8..15, and window is a user-supplied

    50    window and output buffer that is 2**windowBits bytes.

    51  */

    52 int ZEXPORT inflateBackInit_(strm, windowBits, window, version, stream_size)

    53 z_streamp strm;

    54 int windowBits;

    55 unsigned char FAR *window;

    56 const char *version;

    57 int stream_size;

    58 {

    59     struct inflate_state FAR *state;

    60 

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

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

    63         return Z_VERSION_ERROR;

    64     if (strm == Z_NULL || window == Z_NULL ||

    65         windowBits < 8 || windowBits > 15)

    66         return Z_STREAM_ERROR;

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

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

    69         strm->zalloc = zcalloc;

    70         strm->opaque = (voidpf)0;

    71     }

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

    73     state = (struct inflate_state FAR *)ZALLOC(strm, 1,

    74                                                sizeof(struct inflate_state));

    75     if (state == Z_NULL) return Z_MEM_ERROR;

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

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

    78     state->dmax = 32768U;

    79     state->wbits = windowBits;

    80     state->wsize = 1U << windowBits;

    81     state->window = window;

    82     state->wnext = 0;

    83     state->whave = 0;

    84     return Z_OK;

    85 }

    86 

    87 /*

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

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

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

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

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

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

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

    95    may not be thread-safe.

    96  */

    97 local void fixedtables(state)

    98 struct inflate_state FAR *state;

    99 {

   100 #ifdef BUILDFIXED

   101     static int virgin = 1;

   102     static code *lenfix, *distfix;

   103     static code fixed[544];

   104 

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

   106     if (virgin) {

   107         unsigned sym, bits;

   108         static code *next;

   109 

   110         /* literal/length table */

   111         sym = 0;

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

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

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

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

   116         next = fixed;

   117         lenfix = next;

   118         bits = 9;

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

   120 

   121         /* distance table */

   122         sym = 0;

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

   124         distfix = next;

   125         bits = 5;

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

   127 

   128         /* do this just once */

   129         virgin = 0;

   130     }

   131 #else /* !BUILDFIXED */

   132 #   include "inffixed.h"

   133 #endif /* BUILDFIXED */

   134     state->lencode = lenfix;

   135     state->lenbits = 9;

   136     state->distcode = distfix;

   137     state->distbits = 5;

   138 }

   139 

   140 /* Macros for inflateBack(): */

   141 

   142 /* Load returned state from inflate_fast() */

   143 #define LOAD() \

   144     do { \

   145         put = strm->next_out; \

   146         left = strm->avail_out; \

   147         next = strm->next_in; \

   148         have = strm->avail_in; \

   149         hold = state->hold; \

   150         bits = state->bits; \

   151     } while (0)

   152 

   153 /* Set state from registers for inflate_fast() */

   154 #define RESTORE() \

   155     do { \

   156         strm->next_out = put; \

   157         strm->avail_out = left; \

   158         strm->next_in = next; \

   159         strm->avail_in = have; \

   160         state->hold = hold; \

   161         state->bits = bits; \

   162     } while (0)

   163 

   164 /* Clear the input bit accumulator */

   165 #define INITBITS() \

   166     do { \

   167         hold = 0; \

   168         bits = 0; \

   169     } while (0)

   170 

   171 /* Assure that some input is available.  If input is requested, but denied,

   172    then return a Z_BUF_ERROR from inflateBack(). */

   173 #define PULL() \

   174     do { \

   175         if (have == 0) { \

   176             have = in(in_desc, &next); \

   177             if (have == 0) { \

   178                 next = Z_NULL; \

   179                 ret = Z_BUF_ERROR; \

   180                 goto inf_leave; \

   181             } \

   182         } \

   183     } while (0)

   184 

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

   186    with an error if there is no input available. */

   187 #define PULLBYTE() \

   188     do { \

   189         PULL(); \

   190         have--; \

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

   192         bits += 8; \

   193     } while (0)

   194 

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

   196    not enough available input to do that, then return from inflateBack() with

   197    an error. */

   198 #define NEEDBITS(n) \

   199     do { \

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

   201             PULLBYTE(); \

   202     } while (0)

   203 

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

   205 #define BITS(n) \

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

   207 

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

   209 #define DROPBITS(n) \

   210     do { \

   211         hold >>= (n); \

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

   213     } while (0)

   214 

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

   216 #define BYTEBITS() \

   217     do { \

   218         hold >>= bits & 7; \

   219         bits -= bits & 7; \

   220     } while (0)

   221 

   222 /* Assure that some output space is available, by writing out the window

   223    if it's full.  If the write fails, return from inflateBack() with a

   224    Z_BUF_ERROR. */

   225 #define ROOM() \

   226     do { \

   227         if (left == 0) { \

   228             put = state->window; \

   229             left = state->wsize; \

   230             state->whave = left; \

   231             if (out(out_desc, put, left)) { \

   232                 ret = Z_BUF_ERROR; \

   233                 goto inf_leave; \

   234             } \

   235         } \

   236     } while (0)

   237 

   238 /*

   239    strm provides the memory allocation functions and window buffer on input,

   240    and provides information on the unused input on return.  For Z_DATA_ERROR

   241    returns, strm will also provide an error message.

   242 

   243    in() and out() are the call-back input and output functions.  When

   244    inflateBack() needs more input, it calls in().  When inflateBack() has

   245    filled the window with output, or when it completes with data in the

   246    window, it calls out() to write out the data.  The application must not

   247    change the provided input until in() is called again or inflateBack()

   248    returns.  The application must not change the window/output buffer until

   249    inflateBack() returns.

   250 

   251    in() and out() are called with a descriptor parameter provided in the

   252    inflateBack() call.  This parameter can be a structure that provides the

   253    information required to do the read or write, as well as accumulated

   254    information on the input and output such as totals and check values.

   255 

   256    in() should return zero on failure.  out() should return non-zero on

   257    failure.  If either in() or out() fails, than inflateBack() returns a

   258    Z_BUF_ERROR.  strm->next_in can be checked for Z_NULL to see whether it

   259    was in() or out() that caused in the error.  Otherwise,  inflateBack()

   260    returns Z_STREAM_END on success, Z_DATA_ERROR for an deflate format

   261    error, or Z_MEM_ERROR if it could not allocate memory for the state.

   262    inflateBack() can also return Z_STREAM_ERROR if the input parameters

   263    are not correct, i.e. strm is Z_NULL or the state was not initialized.

   264  */

   265 int ZEXPORT inflateBack(strm, in, in_desc, out, out_desc)

   266 z_streamp strm;

   267 in_func in;

   268 void FAR *in_desc;

   269 out_func out;

   270 void FAR *out_desc;

   271 {

   272     struct inflate_state FAR *state;

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

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

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

   276     unsigned long hold;         /* bit buffer */

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

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

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

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

   281     code last;                  /* parent table entry */

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

   283     int ret;                    /* return code */

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

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

   286 

   287     /* Check that the strm exists and that the state was initialized */

   288     if (strm == Z_NULL || strm->state == Z_NULL)

   289         return Z_STREAM_ERROR;

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

   291 

   292     /* Reset the state */

   293     strm->msg = Z_NULL;

   294     state->mode = TYPE;

   295     state->last = 0;

   296     state->whave = 0;

   297     next = strm->next_in;

   298     have = next != Z_NULL ? strm->avail_in : 0;

   299     hold = 0;

   300     bits = 0;

   301     put = state->window;

   302     left = state->wsize;

   303 

   304     /* Inflate until end of block marked as last */

   305     for (;;)

   306         switch (state->mode) {

   307         case TYPE:

   308             /* determine and dispatch block type */

   309             if (state->last) {

   310                 BYTEBITS();

   311                 state->mode = DONE;

   312                 break;

   313             }

   314             NEEDBITS(3);

   315             state->last = BITS(1);

   316             DROPBITS(1);

   317             switch (BITS(2)) {

   318             case 0:                             /* stored block */

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

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

   321                 state->mode = STORED;

   322                 break;

   323             case 1:                             /* fixed block */

   324                 fixedtables(state);

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

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

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

   328                 break;

   329             case 2:                             /* dynamic block */

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

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

   332                 state->mode = TABLE;

   333                 break;

   334             case 3:

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

   336                 state->mode = BAD;

   337             }

   338             DROPBITS(2);

   339             break;

   340 

   341         case STORED:

   342             /* get and verify stored block length */

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

   344             NEEDBITS(32);

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

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

   347                 state->mode = BAD;

   348                 break;

   349             }

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

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

   352                     state->length));

   353             INITBITS();

   354 

   355             /* copy stored block from input to output */

   356             while (state->length != 0) {

   357                 copy = state->length;

   358                 PULL();

   359                 ROOM();

   360                 if (copy > have) copy = have;

   361                 if (copy > left) copy = left;

   362                 zmemcpy(put, next, copy);

   363                 have -= copy;

   364                 next += copy;

   365                 left -= copy;

   366                 put += copy;

   367                 state->length -= copy;

   368             }

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

   370             state->mode = TYPE;

   371             break;

   372 

   373         case TABLE:

   374             /* get dynamic table entries descriptor */

   375             NEEDBITS(14);

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

   377             DROPBITS(5);

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

   379             DROPBITS(5);

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

   381             DROPBITS(4);

   382 #ifndef PKZIP_BUG_WORKAROUND

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

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

   385                 state->mode = BAD;

   386                 break;

   387             }

   388 #endif

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

   390 

   391             /* get code length code lengths (not a typo) */

   392             state->have = 0;

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

   394                 NEEDBITS(3);

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

   396                 DROPBITS(3);

   397             }

   398             while (state->have < 19)

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

   400             state->next = state->codes;

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

   402             state->lenbits = 7;

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

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

   405             if (ret) {

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

   407                 state->mode = BAD;

   408                 break;

   409             }

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

   411 

   412             /* get length and distance code code lengths */

   413             state->have = 0;

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

   415                 for (;;) {

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

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

   418                     PULLBYTE();

   419                 }

   420                 if (here.val < 16) {

   421                     NEEDBITS(here.bits);

   422                     DROPBITS(here.bits);

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

   424                 }

   425                 else {

   426                     if (here.val == 16) {

   427                         NEEDBITS(here.bits + 2);

   428                         DROPBITS(here.bits);

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

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

   431                             state->mode = BAD;

   432                             break;

   433                         }

   434                         len = (unsigned)(state->lens[state->have - 1]);

   435                         copy = 3 + BITS(2);

   436                         DROPBITS(2);

   437                     }

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

   439                         NEEDBITS(here.bits + 3);

   440                         DROPBITS(here.bits);

   441                         len = 0;

   442                         copy = 3 + BITS(3);

   443                         DROPBITS(3);

   444                     }

   445                     else {

   446                         NEEDBITS(here.bits + 7);

   447                         DROPBITS(here.bits);

   448                         len = 0;

   449                         copy = 11 + BITS(7);

   450                         DROPBITS(7);

   451                     }

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

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

   454                         state->mode = BAD;

   455                         break;

   456                     }

   457                     while (copy--)

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

   459                 }

   460             }

   461 

   462             /* handle error breaks in while */

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

   464 

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

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

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

   468                 state->mode = BAD;

   469                 break;

   470             }

   471 

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

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

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

   475             state->next = state->codes;

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

   477             state->lenbits = 9;

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

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

   480             if (ret) {

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

   482                 state->mode = BAD;

   483                 break;

   484             }

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

   486             state->distbits = 6;

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

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

   489             if (ret) {

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

   491                 state->mode = BAD;

   492                 break;

   493             }

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

   495             state->mode = LEN;

   496 

   497         case LEN:

   498             /* use inflate_fast() if we have enough input and output */

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

   500                 RESTORE();

   501                 if (state->whave < state->wsize)

   502                     state->whave = state->wsize - left;

   503                 inflate_fast(strm, state->wsize);

   504                 LOAD();

   505                 break;

   506             }

   507 

   508             /* get a literal, length, or end-of-block code */

   509             for (;;) {

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

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

   512                 PULLBYTE();

   513             }

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

   515                 last = here;

   516                 for (;;) {

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

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

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

   520                     PULLBYTE();

   521                 }

   522                 DROPBITS(last.bits);

   523             }

   524             DROPBITS(here.bits);

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

   526 

   527             /* process literal */

   528             if (here.op == 0) {

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

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

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

   532                 ROOM();

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

   534                 left--;

   535                 state->mode = LEN;

   536                 break;

   537             }

   538 

   539             /* process end of block */

   540             if (here.op & 32) {

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

   542                 state->mode = TYPE;

   543                 break;

   544             }

   545 

   546             /* invalid code */

   547             if (here.op & 64) {

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

   549                 state->mode = BAD;

   550                 break;

   551             }

   552 

   553             /* length code -- get extra bits, if any */

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

   555             if (state->extra != 0) {

   556                 NEEDBITS(state->extra);

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

   558                 DROPBITS(state->extra);

   559             }

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

   561 

   562             /* get distance code */

   563             for (;;) {

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

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

   566                 PULLBYTE();

   567             }

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

   569                 last = here;

   570                 for (;;) {

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

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

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

   574                     PULLBYTE();

   575                 }

   576                 DROPBITS(last.bits);

   577             }

   578             DROPBITS(here.bits);

   579             if (here.op & 64) {

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

   581                 state->mode = BAD;

   582                 break;

   583             }

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

   585 

   586             /* get distance extra bits, if any */

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

   588             if (state->extra != 0) {

   589                 NEEDBITS(state->extra);

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

   591                 DROPBITS(state->extra);

   592             }

   593             if (state->offset > state->wsize - (state->whave < state->wsize ?

   594                                                 left : 0)) {

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

   596                 state->mode = BAD;

   597                 break;

   598             }

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

   600 

   601             /* copy match from window to output */

   602             do {

   603                 ROOM();

   604                 copy = state->wsize - state->offset;

   605                 if (copy < left) {

   606                     from = put + copy;

   607                     copy = left - copy;

   608                 }

   609                 else {

   610                     from = put - state->offset;

   611                     copy = left;

   612                 }

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

   614                 state->length -= copy;

   615                 left -= copy;

   616                 do {

   617                     *put++ = *from++;

   618                 } while (--copy);

   619             } while (state->length != 0);

   620             break;

   621 

   622         case DONE:

   623             /* inflate stream terminated properly -- write leftover output */

   624             ret = Z_STREAM_END;

   625             if (left < state->wsize) {

   626                 if (out(out_desc, state->window, state->wsize - left))

   627                     ret = Z_BUF_ERROR;

   628             }

   629             goto inf_leave;

   630 

   631         case BAD:

   632             ret = Z_DATA_ERROR;

   633             goto inf_leave;

   634 

   635         default:                /* can't happen, but makes compilers happy */

   636             ret = Z_STREAM_ERROR;

   637             goto inf_leave;

   638         }

   639 

   640     /* Return unused input */

   641   inf_leave:

   642     strm->next_in = next;

   643     strm->avail_in = have;

   644     return ret;

   645 }

   646 

   647 int ZEXPORT inflateBackEnd(strm)

   648 z_streamp strm;

   649 {

   650     if (strm == Z_NULL || strm->state == Z_NULL || strm->zfree == (free_func)0)

   651         return Z_STREAM_ERROR;

   652     ZFREE(strm, strm->state);

   653     strm->state = Z_NULL;

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

   655     return Z_OK;

   656 }