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-2005 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->write = 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 this;                  /* 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                     this = state->lencode[BITS(state->lenbits)];

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

   418                     PULLBYTE();

   419                 }

   420                 if (this.val < 16) {

   421                     NEEDBITS(this.bits);

   422                     DROPBITS(this.bits);

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

   424                 }

   425                 else {

   426                     if (this.val == 16) {

   427                         NEEDBITS(this.bits + 2);

   428                         DROPBITS(this.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 (this.val == 17) {

   439                         NEEDBITS(this.bits + 3);

   440                         DROPBITS(this.bits);

   441                         len = 0;

   442                         copy = 3 + BITS(3);

   443                         DROPBITS(3);

   444                     }

   445                     else {

   446                         NEEDBITS(this.bits + 7);

   447                         DROPBITS(this.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             /* build code tables */

   466             state->next = state->codes;

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

   468             state->lenbits = 9;

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

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

   471             if (ret) {

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

   473                 state->mode = BAD;

   474                 break;

   475             }

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

   477             state->distbits = 6;

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

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

   480             if (ret) {

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

   482                 state->mode = BAD;

   483                 break;

   484             }

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

   486             state->mode = LEN;

   487 

   488         case LEN:

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

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

   491                 RESTORE();

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

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

   494                 inflate_fast(strm, state->wsize);

   495                 LOAD();

   496                 break;

   497             }

   498 

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

   500             for (;;) {

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

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

   503                 PULLBYTE();

   504             }

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

   506                 last = this;

   507                 for (;;) {

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

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

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

   511                     PULLBYTE();

   512                 }

   513                 DROPBITS(last.bits);

   514             }

   515             DROPBITS(this.bits);

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

   517 

   518             /* process literal */

   519             if (this.op == 0) {

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

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

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

   523                 ROOM();

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

   525                 left--;

   526                 state->mode = LEN;

   527                 break;

   528             }

   529 

   530             /* process end of block */

   531             if (this.op & 32) {

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

   533                 state->mode = TYPE;

   534                 break;

   535             }

   536 

   537             /* invalid code */

   538             if (this.op & 64) {

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

   540                 state->mode = BAD;

   541                 break;

   542             }

   543 

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

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

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

   547                 NEEDBITS(state->extra);

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

   549                 DROPBITS(state->extra);

   550             }

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

   552 

   553             /* get distance code */

   554             for (;;) {

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

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

   557                 PULLBYTE();

   558             }

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

   560                 last = this;

   561                 for (;;) {

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

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

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

   565                     PULLBYTE();

   566                 }

   567                 DROPBITS(last.bits);

   568             }

   569             DROPBITS(this.bits);

   570             if (this.op & 64) {

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

   572                 state->mode = BAD;

   573                 break;

   574             }

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

   576 

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

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

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

   580                 NEEDBITS(state->extra);

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

   582                 DROPBITS(state->extra);

   583             }

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

   585                                                 left : 0)) {

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

   587                 state->mode = BAD;

   588                 break;

   589             }

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

   591 

   592             /* copy match from window to output */

   593             do {

   594                 ROOM();

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

   596                 if (copy < left) {

   597                     from = put + copy;

   598                     copy = left - copy;

   599                 }

   600                 else {

   601                     from = put - state->offset;

   602                     copy = left;

   603                 }

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

   605                 state->length -= copy;

   606                 left -= copy;

   607                 do {

   608                     *put++ = *from++;

   609                 } while (--copy);

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

   611             break;

   612 

   613         case DONE:

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

   615             ret = Z_STREAM_END;

   616             if (left < state->wsize) {

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

   618                     ret = Z_BUF_ERROR;

   619             }

   620             goto inf_leave;

   621 

   622         case BAD:

   623             ret = Z_DATA_ERROR;

   624             goto inf_leave;

   625 

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

   627             ret = Z_STREAM_ERROR;

   628             goto inf_leave;

   629         }

   630 

   631     /* Return unused input */

   632   inf_leave:

   633     strm->next_in = next;

   634     strm->avail_in = have;

   635     return ret;

   636 }

   637 

   638 int ZEXPORT inflateBackEnd(strm)

   639 z_streamp strm;

   640 {

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

   642         return Z_STREAM_ERROR;

   643     ZFREE(strm, strm->state);

   644     strm->state = Z_NULL;

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

   646     return Z_OK;

   647 }