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-2011 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 #ifdef Z_SOLO

    70         return Z_STREAM_ERROR;

    71 #else

    72         strm->zalloc = zcalloc;

    73         strm->opaque = (voidpf)0;

    74 #endif

    75     }

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

    77 #ifdef Z_SOLO

    78         return Z_STREAM_ERROR;

    79 #else

    80     strm->zfree = zcfree;

    81 #endif

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

    83                                                sizeof(struct inflate_state));

    84     if (state == Z_NULL) return Z_MEM_ERROR;

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

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

    87     state->dmax = 32768U;

    88     state->wbits = windowBits;

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

    90     state->window = window;

    91     state->wnext = 0;

    92     state->whave = 0;

    93     return Z_OK;

    94 }

    95 

    96 /*

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

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

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

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

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

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

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

   104    may not be thread-safe.

   105  */

   106 local void fixedtables(state)

   107 struct inflate_state FAR *state;

   108 {

   109 #ifdef BUILDFIXED

   110     static int virgin = 1;

   111     static code *lenfix, *distfix;

   112     static code fixed[544];

   113 

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

   115     if (virgin) {

   116         unsigned sym, bits;

   117         static code *next;

   118 

   119         /* literal/length table */

   120         sym = 0;

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

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

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

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

   125         next = fixed;

   126         lenfix = next;

   127         bits = 9;

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

   129 

   130         /* distance table */

   131         sym = 0;

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

   133         distfix = next;

   134         bits = 5;

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

   136 

   137         /* do this just once */

   138         virgin = 0;

   139     }

   140 #else /* !BUILDFIXED */

   141 #   include "inffixed.h"

   142 #endif /* BUILDFIXED */

   143     state->lencode = lenfix;

   144     state->lenbits = 9;

   145     state->distcode = distfix;

   146     state->distbits = 5;

   147 }

   148 

   149 /* Macros for inflateBack(): */

   150 

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

   152 #define LOAD() \

   153     do { \

   154         put = strm->next_out; \

   155         left = strm->avail_out; \

   156         next = strm->next_in; \

   157         have = strm->avail_in; \

   158         hold = state->hold; \

   159         bits = state->bits; \

   160     } while (0)

   161 

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

   163 #define RESTORE() \

   164     do { \

   165         strm->next_out = put; \

   166         strm->avail_out = left; \

   167         strm->next_in = next; \

   168         strm->avail_in = have; \

   169         state->hold = hold; \

   170         state->bits = bits; \

   171     } while (0)

   172 

   173 /* Clear the input bit accumulator */

   174 #define INITBITS() \

   175     do { \

   176         hold = 0; \

   177         bits = 0; \

   178     } while (0)

   179 

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

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

   182 #define PULL() \

   183     do { \

   184         if (have == 0) { \

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

   186             if (have == 0) { \

   187                 next = Z_NULL; \

   188                 ret = Z_BUF_ERROR; \

   189                 goto inf_leave; \

   190             } \

   191         } \

   192     } while (0)

   193 

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

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

   196 #define PULLBYTE() \

   197     do { \

   198         PULL(); \

   199         have--; \

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

   201         bits += 8; \

   202     } while (0)

   203 

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

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

   206    an error. */

   207 #define NEEDBITS(n) \

   208     do { \

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

   210             PULLBYTE(); \

   211     } while (0)

   212 

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

   214 #define BITS(n) \

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

   216 

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

   218 #define DROPBITS(n) \

   219     do { \

   220         hold >>= (n); \

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

   222     } while (0)

   223 

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

   225 #define BYTEBITS() \

   226     do { \

   227         hold >>= bits & 7; \

   228         bits -= bits & 7; \

   229     } while (0)

   230 

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

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

   233    Z_BUF_ERROR. */

   234 #define ROOM() \

   235     do { \

   236         if (left == 0) { \

   237             put = state->window; \

   238             left = state->wsize; \

   239             state->whave = left; \

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

   241                 ret = Z_BUF_ERROR; \

   242                 goto inf_leave; \

   243             } \

   244         } \

   245     } while (0)

   246 

   247 /*

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

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

   250    returns, strm will also provide an error message.

   251 

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

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

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

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

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

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

   258    inflateBack() returns.

   259 

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

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

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

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

   264 

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

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

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

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

   269    returns Z_STREAM_END on success, Z_DATA_ERROR for an deflate format

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

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

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

   273  */

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

   275 z_streamp strm;

   276 in_func in;

   277 void FAR *in_desc;

   278 out_func out;

   279 void FAR *out_desc;

   280 {

   281     struct inflate_state FAR *state;

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

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

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

   285     unsigned long hold;         /* bit buffer */

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

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

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

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

   290     code last;                  /* parent table entry */

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

   292     int ret;                    /* return code */

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

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

   295 

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

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

   298         return Z_STREAM_ERROR;

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

   300 

   301     /* Reset the state */

   302     strm->msg = Z_NULL;

   303     state->mode = TYPE;

   304     state->last = 0;

   305     state->whave = 0;

   306     next = strm->next_in;

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

   308     hold = 0;

   309     bits = 0;

   310     put = state->window;

   311     left = state->wsize;

   312 

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

   314     for (;;)

   315         switch (state->mode) {

   316         case TYPE:

   317             /* determine and dispatch block type */

   318             if (state->last) {

   319                 BYTEBITS();

   320                 state->mode = DONE;

   321                 break;

   322             }

   323             NEEDBITS(3);

   324             state->last = BITS(1);

   325             DROPBITS(1);

   326             switch (BITS(2)) {

   327             case 0:                             /* stored block */

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

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

   330                 state->mode = STORED;

   331                 break;

   332             case 1:                             /* fixed block */

   333                 fixedtables(state);

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

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

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

   337                 break;

   338             case 2:                             /* dynamic block */

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

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

   341                 state->mode = TABLE;

   342                 break;

   343             case 3:

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

   345                 state->mode = BAD;

   346             }

   347             DROPBITS(2);

   348             break;

   349 

   350         case STORED:

   351             /* get and verify stored block length */

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

   353             NEEDBITS(32);

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

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

   356                 state->mode = BAD;

   357                 break;

   358             }

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

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

   361                     state->length));

   362             INITBITS();

   363 

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

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

   366                 copy = state->length;

   367                 PULL();

   368                 ROOM();

   369                 if (copy > have) copy = have;

   370                 if (copy > left) copy = left;

   371                 zmemcpy(put, next, copy);

   372                 have -= copy;

   373                 next += copy;

   374                 left -= copy;

   375                 put += copy;

   376                 state->length -= copy;

   377             }

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

   379             state->mode = TYPE;

   380             break;

   381 

   382         case TABLE:

   383             /* get dynamic table entries descriptor */

   384             NEEDBITS(14);

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

   386             DROPBITS(5);

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

   388             DROPBITS(5);

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

   390             DROPBITS(4);

   391 #ifndef PKZIP_BUG_WORKAROUND

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

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

   394                 state->mode = BAD;

   395                 break;

   396             }

   397 #endif

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

   399 

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

   401             state->have = 0;

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

   403                 NEEDBITS(3);

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

   405                 DROPBITS(3);

   406             }

   407             while (state->have < 19)

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

   409             state->next = state->codes;

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

   411             state->lenbits = 7;

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

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

   414             if (ret) {

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

   416                 state->mode = BAD;

   417                 break;

   418             }

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

   420 

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

   422             state->have = 0;

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

   424                 for (;;) {

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

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

   427                     PULLBYTE();

   428                 }

   429                 if (here.val < 16) {

   430                     DROPBITS(here.bits);

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

   432                 }

   433                 else {

   434                     if (here.val == 16) {

   435                         NEEDBITS(here.bits + 2);

   436                         DROPBITS(here.bits);

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

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

   439                             state->mode = BAD;

   440                             break;

   441                         }

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

   443                         copy = 3 + BITS(2);

   444                         DROPBITS(2);

   445                     }

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

   447                         NEEDBITS(here.bits + 3);

   448                         DROPBITS(here.bits);

   449                         len = 0;

   450                         copy = 3 + BITS(3);

   451                         DROPBITS(3);

   452                     }

   453                     else {

   454                         NEEDBITS(here.bits + 7);

   455                         DROPBITS(here.bits);

   456                         len = 0;

   457                         copy = 11 + BITS(7);

   458                         DROPBITS(7);

   459                     }

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

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

   462                         state->mode = BAD;

   463                         break;

   464                     }

   465                     while (copy--)

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

   467                 }

   468             }

   469 

   470             /* handle error breaks in while */

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

   472 

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

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

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

   476                 state->mode = BAD;

   477                 break;

   478             }

   479 

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

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

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

   483             state->next = state->codes;

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

   485             state->lenbits = 9;

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

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

   488             if (ret) {

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

   490                 state->mode = BAD;

   491                 break;

   492             }

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

   494             state->distbits = 6;

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

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

   497             if (ret) {

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

   499                 state->mode = BAD;

   500                 break;

   501             }

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

   503             state->mode = LEN;

   504 

   505         case LEN:

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

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

   508                 RESTORE();

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

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

   511                 inflate_fast(strm, state->wsize);

   512                 LOAD();

   513                 break;

   514             }

   515 

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

   517             for (;;) {

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

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

   520                 PULLBYTE();

   521             }

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

   523                 last = here;

   524                 for (;;) {

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

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

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

   528                     PULLBYTE();

   529                 }

   530                 DROPBITS(last.bits);

   531             }

   532             DROPBITS(here.bits);

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

   534 

   535             /* process literal */

   536             if (here.op == 0) {

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

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

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

   540                 ROOM();

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

   542                 left--;

   543                 state->mode = LEN;

   544                 break;

   545             }

   546 

   547             /* process end of block */

   548             if (here.op & 32) {

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

   550                 state->mode = TYPE;

   551                 break;

   552             }

   553 

   554             /* invalid code */

   555             if (here.op & 64) {

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

   557                 state->mode = BAD;

   558                 break;

   559             }

   560 

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

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

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

   564                 NEEDBITS(state->extra);

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

   566                 DROPBITS(state->extra);

   567             }

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

   569 

   570             /* get distance code */

   571             for (;;) {

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

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

   574                 PULLBYTE();

   575             }

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

   577                 last = here;

   578                 for (;;) {

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

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

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

   582                     PULLBYTE();

   583                 }

   584                 DROPBITS(last.bits);

   585             }

   586             DROPBITS(here.bits);

   587             if (here.op & 64) {

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

   589                 state->mode = BAD;

   590                 break;

   591             }

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

   593 

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

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

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

   597                 NEEDBITS(state->extra);

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

   599                 DROPBITS(state->extra);

   600             }

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

   602                                                 left : 0)) {

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

   604                 state->mode = BAD;

   605                 break;

   606             }

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

   608 

   609             /* copy match from window to output */

   610             do {

   611                 ROOM();

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

   613                 if (copy < left) {

   614                     from = put + copy;

   615                     copy = left - copy;

   616                 }

   617                 else {

   618                     from = put - state->offset;

   619                     copy = left;

   620                 }

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

   622                 state->length -= copy;

   623                 left -= copy;

   624                 do {

   625                     *put++ = *from++;

   626                 } while (--copy);

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

   628             break;

   629 

   630         case DONE:

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

   632             ret = Z_STREAM_END;

   633             if (left < state->wsize) {

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

   635                     ret = Z_BUF_ERROR;

   636             }

   637             goto inf_leave;

   638 

   639         case BAD:

   640             ret = Z_DATA_ERROR;

   641             goto inf_leave;

   642 

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

   644             ret = Z_STREAM_ERROR;

   645             goto inf_leave;

   646         }

   647 

   648     /* Return unused input */

   649   inf_leave:

   650     strm->next_in = next;

   651     strm->avail_in = have;

   652     return ret;

   653 }

   654 

   655 int ZEXPORT inflateBackEnd(strm)

   656 z_streamp strm;

   657 {

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

   659         return Z_STREAM_ERROR;

   660     ZFREE(strm, strm->state);

   661     strm->state = Z_NULL;

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

   663     return Z_OK;

   664 }