infback.c

00001 /* infback.c -- inflate using a call-back interface
00002  * Copyright (C) 1995-2011 Mark Adler
00003  * For conditions of distribution and use, see copyright notice in zlib.h
00004  */
00005 
00006 /*
00007    This code is largely copied from inflate.c.  Normally either infback.o or
00008    inflate.o would be linked into an application--not both.  The interface
00009    with inffast.c is retained so that optimized assembler-coded versions of
00010    inflate_fast() can be used with either inflate.c or infback.c.
00011  */
00012 
00013 #include "zutil.h"
00014 #include "inftrees.h"
00015 #include "inflate.h"
00016 #include "inffast.h"
00017 
00018 /* function prototypes */
00019 local void fixedtables OF((struct inflate_state FAR *state));
00020 
00021 /*
00022    strm provides memory allocation functions in zalloc and zfree, or
00023    Z_NULL to use the library memory allocation functions.
00024 
00025    windowBits is in the range 8..15, and window is a user-supplied
00026    window and output buffer that is 2**windowBits bytes.
00027  */
00028 int ZEXPORT inflateBackInit_(strm, windowBits, window, version, stream_size)
00029 z_streamp strm;
00030 int windowBits;
00031 unsigned char FAR *window;
00032 const char *version;
00033 int stream_size;
00034 {
00035     struct inflate_state FAR *state;
00036 
00037     if (version == Z_NULL || version[0] != ZLIB_VERSION[0] ||
00038         stream_size != (int)(sizeof(z_stream)))
00039         return Z_VERSION_ERROR;
00040     if (strm == Z_NULL || window == Z_NULL ||
00041         windowBits < 8 || windowBits > 15)
00042         return Z_STREAM_ERROR;
00043     strm->msg = Z_NULL;                 /* in case we return an error */
00044     if (strm->zalloc == (alloc_func)0) {
00045 #ifdef Z_SOLO
00046         return Z_STREAM_ERROR;
00047 #else
00048         strm->zalloc = zcalloc;
00049         strm->opaque = (voidpf)0;
00050 #endif
00051     }
00052     if (strm->zfree == (free_func)0)
00053 #ifdef Z_SOLO
00054         return Z_STREAM_ERROR;
00055 #else
00056     strm->zfree = zcfree;
00057 #endif
00058     state = (struct inflate_state FAR *)ZALLOC(strm, 1,
00059                                                sizeof(struct inflate_state));
00060     if (state == Z_NULL) return Z_MEM_ERROR;
00061     Tracev((stderr, "inflate: allocated\n"));
00062     strm->state = (struct internal_state FAR *)state;
00063     state->dmax = 32768U;
00064     state->wbits = windowBits;
00065     state->wsize = 1U << windowBits;
00066     state->window = window;
00067     state->wnext = 0;
00068     state->whave = 0;
00069     return Z_OK;
00070 }
00071 
00072 /*
00073    Return state with length and distance decoding tables and index sizes set to
00074    fixed code decoding.  Normally this returns fixed tables from inffixed.h.
00075    If BUILDFIXED is defined, then instead this routine builds the tables the
00076    first time it's called, and returns those tables the first time and
00077    thereafter.  This reduces the size of the code by about 2K bytes, in
00078    exchange for a little execution time.  However, BUILDFIXED should not be
00079    used for threaded applications, since the rewriting of the tables and virgin
00080    may not be thread-safe.
00081  */
00082 local void fixedtables(state)
00083 struct inflate_state FAR *state;
00084 {
00085 #ifdef BUILDFIXED
00086     static int virgin = 1;
00087     static code *lenfix, *distfix;
00088     static code fixed[544];
00089 
00090     /* build fixed huffman tables if first call (may not be thread safe) */
00091     if (virgin) {
00092         unsigned sym, bits;
00093         static code *next;
00094 
00095         /* literal/length table */
00096         sym = 0;
00097         while (sym < 144) state->lens[sym++] = 8;
00098         while (sym < 256) state->lens[sym++] = 9;
00099         while (sym < 280) state->lens[sym++] = 7;
00100         while (sym < 288) state->lens[sym++] = 8;
00101         next = fixed;
00102         lenfix = next;
00103         bits = 9;
00104         inflate_table(LENS, state->lens, 288, &(next), &(bits), state->work);
00105 
00106         /* distance table */
00107         sym = 0;
00108         while (sym < 32) state->lens[sym++] = 5;
00109         distfix = next;
00110         bits = 5;
00111         inflate_table(DISTS, state->lens, 32, &(next), &(bits), state->work);
00112 
00113         /* do this just once */
00114         virgin = 0;
00115     }
00116 #else /* !BUILDFIXED */
00117 #   include "inffixed.h"
00118 #endif /* BUILDFIXED */
00119     state->lencode = lenfix;
00120     state->lenbits = 9;
00121     state->distcode = distfix;
00122     state->distbits = 5;
00123 }
00124 
00125 /* Macros for inflateBack(): */
00126 
00127 /* Load returned state from inflate_fast() */
00128 #define LOAD() \
00129     do { \
00130         put = strm->next_out; \
00131         left = strm->avail_out; \
00132         next = strm->next_in; \
00133         have = strm->avail_in; \
00134         hold = state->hold; \
00135         bits = state->bits; \
00136     } while (0)
00137 
00138 /* Set state from registers for inflate_fast() */
00139 #define RESTORE() \
00140     do { \
00141         strm->next_out = put; \
00142         strm->avail_out = left; \
00143         strm->next_in = next; \
00144         strm->avail_in = have; \
00145         state->hold = hold; \
00146         state->bits = bits; \
00147     } while (0)
00148 
00149 /* Clear the input bit accumulator */
00150 #define INITBITS() \
00151     do { \
00152         hold = 0; \
00153         bits = 0; \
00154     } while (0)
00155 
00156 /* Assure that some input is available.  If input is requested, but denied,
00157    then return a Z_BUF_ERROR from inflateBack(). */
00158 #define PULL() \
00159     do { \
00160         if (have == 0) { \
00161             have = in(in_desc, &next); \
00162             if (have == 0) { \
00163                 next = Z_NULL; \
00164                 ret = Z_BUF_ERROR; \
00165                 goto inf_leave; \
00166             } \
00167         } \
00168     } while (0)
00169 
00170 /* Get a byte of input into the bit accumulator, or return from inflateBack()
00171    with an error if there is no input available. */
00172 #define PULLBYTE() \
00173     do { \
00174         PULL(); \
00175         have--; \
00176         hold += (unsigned long)(*next++) << bits; \
00177         bits += 8; \
00178     } while (0)
00179 
00180 /* Assure that there are at least n bits in the bit accumulator.  If there is
00181    not enough available input to do that, then return from inflateBack() with
00182    an error. */
00183 #define NEEDBITS(n) \
00184     do { \
00185         while (bits < (unsigned)(n)) \
00186             PULLBYTE(); \
00187     } while (0)
00188 
00189 /* Return the low n bits of the bit accumulator (n < 16) */
00190 #define BITS(n) \
00191     ((unsigned)hold & ((1U << (n)) - 1))
00192 
00193 /* Remove n bits from the bit accumulator */
00194 #define DROPBITS(n) \
00195     do { \
00196         hold >>= (n); \
00197         bits -= (unsigned)(n); \
00198     } while (0)
00199 
00200 /* Remove zero to seven bits as needed to go to a byte boundary */
00201 #define BYTEBITS() \
00202     do { \
00203         hold >>= bits & 7; \
00204         bits -= bits & 7; \
00205     } while (0)
00206 
00207 /* Assure that some output space is available, by writing out the window
00208    if it's full.  If the write fails, return from inflateBack() with a
00209    Z_BUF_ERROR. */
00210 #define ROOM() \
00211     do { \
00212         if (left == 0) { \
00213             put = state->window; \
00214             left = state->wsize; \
00215             state->whave = left; \
00216             if (out(out_desc, put, left)) { \
00217                 ret = Z_BUF_ERROR; \
00218                 goto inf_leave; \
00219             } \
00220         } \
00221     } while (0)
00222 
00223 /*
00224    strm provides the memory allocation functions and window buffer on input,
00225    and provides information on the unused input on return.  For Z_DATA_ERROR
00226    returns, strm will also provide an error message.
00227 
00228    in() and out() are the call-back input and output functions.  When
00229    inflateBack() needs more input, it calls in().  When inflateBack() has
00230    filled the window with output, or when it completes with data in the
00231    window, it calls out() to write out the data.  The application must not
00232    change the provided input until in() is called again or inflateBack()
00233    returns.  The application must not change the window/output buffer until
00234    inflateBack() returns.
00235 
00236    in() and out() are called with a descriptor parameter provided in the
00237    inflateBack() call.  This parameter can be a structure that provides the
00238    information required to do the read or write, as well as accumulated
00239    information on the input and output such as totals and check values.
00240 
00241    in() should return zero on failure.  out() should return non-zero on
00242    failure.  If either in() or out() fails, than inflateBack() returns a
00243    Z_BUF_ERROR.  strm->next_in can be checked for Z_NULL to see whether it
00244    was in() or out() that caused in the error.  Otherwise,  inflateBack()
00245    returns Z_STREAM_END on success, Z_DATA_ERROR for an deflate format
00246    error, or Z_MEM_ERROR if it could not allocate memory for the state.
00247    inflateBack() can also return Z_STREAM_ERROR if the input parameters
00248    are not correct, i.e. strm is Z_NULL or the state was not initialized.
00249  */
00250 int ZEXPORT inflateBack(strm, in, in_desc, out, out_desc)
00251 z_streamp strm;
00252 in_func in;
00253 void FAR *in_desc;
00254 out_func out;
00255 void FAR *out_desc;
00256 {
00257     struct inflate_state FAR *state;
00258     unsigned char FAR *next;    /* next input */
00259     unsigned char FAR *put;     /* next output */
00260     unsigned have, left;        /* available input and output */
00261     unsigned long hold;         /* bit buffer */
00262     unsigned bits;              /* bits in bit buffer */
00263     unsigned copy;              /* number of stored or match bytes to copy */
00264     unsigned char FAR *from;    /* where to copy match bytes from */
00265     code here;                  /* current decoding table entry */
00266     code last;                  /* parent table entry */
00267     unsigned len;               /* length to copy for repeats, bits to drop */
00268     int ret;                    /* return code */
00269     static const unsigned short order[19] = /* permutation of code lengths */
00270         {16, 17, 18, 0, 8, 7, 9, 6, 10, 5, 11, 4, 12, 3, 13, 2, 14, 1, 15};
00271 
00272     /* Check that the strm exists and that the state was initialized */
00273     if (strm == Z_NULL || strm->state == Z_NULL)
00274         return Z_STREAM_ERROR;
00275     state = (struct inflate_state FAR *)strm->state;
00276 
00277     /* Reset the state */
00278     strm->msg = Z_NULL;
00279     state->mode = TYPE;
00280     state->last = 0;
00281     state->whave = 0;
00282     next = strm->next_in;
00283     have = next != Z_NULL ? strm->avail_in : 0;
00284     hold = 0;
00285     bits = 0;
00286     put = state->window;
00287     left = state->wsize;
00288 
00289     /* Inflate until end of block marked as last */
00290     for (;;)
00291         switch (state->mode) {
00292         case TYPE:
00293             /* determine and dispatch block type */
00294             if (state->last) {
00295                 BYTEBITS();
00296                 state->mode = DONE;
00297                 break;
00298             }
00299             NEEDBITS(3);
00300             state->last = BITS(1);
00301             DROPBITS(1);
00302             switch (BITS(2)) {
00303             case 0:                             /* stored block */
00304                 Tracev((stderr, "inflate:     stored block%s\n",
00305                         state->last ? " (last)" : ""));
00306                 state->mode = STORED;
00307                 break;
00308             case 1:                             /* fixed block */
00309                 fixedtables(state);
00310                 Tracev((stderr, "inflate:     fixed codes block%s\n",
00311                         state->last ? " (last)" : ""));
00312                 state->mode = LEN;              /* decode codes */
00313                 break;
00314             case 2:                             /* dynamic block */
00315                 Tracev((stderr, "inflate:     dynamic codes block%s\n",
00316                         state->last ? " (last)" : ""));
00317                 state->mode = TABLE;
00318                 break;
00319             case 3:
00320                 strm->msg = (char *)"invalid block type";
00321                 state->mode = BAD;
00322             }
00323             DROPBITS(2);
00324             break;
00325 
00326         case STORED:
00327             /* get and verify stored block length */
00328             BYTEBITS();                         /* go to byte boundary */
00329             NEEDBITS(32);
00330             if ((hold & 0xffff) != ((hold >> 16) ^ 0xffff)) {
00331                 strm->msg = (char *)"invalid stored block lengths";
00332                 state->mode = BAD;
00333                 break;
00334             }
00335             state->length = (unsigned)hold & 0xffff;
00336             Tracev((stderr, "inflate:       stored length %u\n",
00337                     state->length));
00338             INITBITS();
00339 
00340             /* copy stored block from input to output */
00341             while (state->length != 0) {
00342                 copy = state->length;
00343                 PULL();
00344                 ROOM();
00345                 if (copy > have) copy = have;
00346                 if (copy > left) copy = left;
00347                 zmemcpy(put, next, copy);
00348                 have -= copy;
00349                 next += copy;
00350                 left -= copy;
00351                 put += copy;
00352                 state->length -= copy;
00353             }
00354             Tracev((stderr, "inflate:       stored end\n"));
00355             state->mode = TYPE;
00356             break;
00357 
00358         case TABLE:
00359             /* get dynamic table entries descriptor */
00360             NEEDBITS(14);
00361             state->nlen = BITS(5) + 257;
00362             DROPBITS(5);
00363             state->ndist = BITS(5) + 1;
00364             DROPBITS(5);
00365             state->ncode = BITS(4) + 4;
00366             DROPBITS(4);
00367 #ifndef PKZIP_BUG_WORKAROUND
00368             if (state->nlen > 286 || state->ndist > 30) {
00369                 strm->msg = (char *)"too many length or distance symbols";
00370                 state->mode = BAD;
00371                 break;
00372             }
00373 #endif
00374             Tracev((stderr, "inflate:       table sizes ok\n"));
00375 
00376             /* get code length code lengths (not a typo) */
00377             state->have = 0;
00378             while (state->have < state->ncode) {
00379                 NEEDBITS(3);
00380                 state->lens[order[state->have++]] = (unsigned short)BITS(3);
00381                 DROPBITS(3);
00382             }
00383             while (state->have < 19)
00384                 state->lens[order[state->have++]] = 0;
00385             state->next = state->codes;
00386             state->lencode = (code const FAR *)(state->next);
00387             state->lenbits = 7;
00388             ret = inflate_table(CODES, state->lens, 19, &(state->next),
00389                                 &(state->lenbits), state->work);
00390             if (ret) {
00391                 strm->msg = (char *)"invalid code lengths set";
00392                 state->mode = BAD;
00393                 break;
00394             }
00395             Tracev((stderr, "inflate:       code lengths ok\n"));
00396 
00397             /* get length and distance code code lengths */
00398             state->have = 0;
00399             while (state->have < state->nlen + state->ndist) {
00400                 for (;;) {
00401                     here = state->lencode[BITS(state->lenbits)];
00402                     if ((unsigned)(here.bits) <= bits) break;
00403                     PULLBYTE();
00404                 }
00405                 if (here.val < 16) {
00406                     DROPBITS(here.bits);
00407                     state->lens[state->have++] = here.val;
00408                 }
00409                 else {
00410                     if (here.val == 16) {
00411                         NEEDBITS(here.bits + 2);
00412                         DROPBITS(here.bits);
00413                         if (state->have == 0) {
00414                             strm->msg = (char *)"invalid bit length repeat";
00415                             state->mode = BAD;
00416                             break;
00417                         }
00418                         len = (unsigned)(state->lens[state->have - 1]);
00419                         copy = 3 + BITS(2);
00420                         DROPBITS(2);
00421                     }
00422                     else if (here.val == 17) {
00423                         NEEDBITS(here.bits + 3);
00424                         DROPBITS(here.bits);
00425                         len = 0;
00426                         copy = 3 + BITS(3);
00427                         DROPBITS(3);
00428                     }
00429                     else {
00430                         NEEDBITS(here.bits + 7);
00431                         DROPBITS(here.bits);
00432                         len = 0;
00433                         copy = 11 + BITS(7);
00434                         DROPBITS(7);
00435                     }
00436                     if (state->have + copy > state->nlen + state->ndist) {
00437                         strm->msg = (char *)"invalid bit length repeat";
00438                         state->mode = BAD;
00439                         break;
00440                     }
00441                     while (copy--)
00442                         state->lens[state->have++] = (unsigned short)len;
00443                 }
00444             }
00445 
00446             /* handle error breaks in while */
00447             if (state->mode == BAD) break;
00448 
00449             /* check for end-of-block code (better have one) */
00450             if (state->lens[256] == 0) {
00451                 strm->msg = (char *)"invalid code -- missing end-of-block";
00452                 state->mode = BAD;
00453                 break;
00454             }
00455 
00456             /* build code tables -- note: do not change the lenbits or distbits
00457                values here (9 and 6) without reading the comments in inftrees.h
00458                concerning the ENOUGH constants, which depend on those values */
00459             state->next = state->codes;
00460             state->lencode = (code const FAR *)(state->next);
00461             state->lenbits = 9;
00462             ret = inflate_table(LENS, state->lens, state->nlen, &(state->next),
00463                                 &(state->lenbits), state->work);
00464             if (ret) {
00465                 strm->msg = (char *)"invalid literal/lengths set";
00466                 state->mode = BAD;
00467                 break;
00468             }
00469             state->distcode = (code const FAR *)(state->next);
00470             state->distbits = 6;
00471             ret = inflate_table(DISTS, state->lens + state->nlen, state->ndist,
00472                             &(state->next), &(state->distbits), state->work);
00473             if (ret) {
00474                 strm->msg = (char *)"invalid distances set";
00475                 state->mode = BAD;
00476                 break;
00477             }
00478             Tracev((stderr, "inflate:       codes ok\n"));
00479             state->mode = LEN;
00480 
00481         case LEN:
00482             /* use inflate_fast() if we have enough input and output */
00483             if (have >= 6 && left >= 258) {
00484                 RESTORE();
00485                 if (state->whave < state->wsize)
00486                     state->whave = state->wsize - left;
00487                 inflate_fast(strm, state->wsize);
00488                 LOAD();
00489                 break;
00490             }
00491 
00492             /* get a literal, length, or end-of-block code */
00493             for (;;) {
00494                 here = state->lencode[BITS(state->lenbits)];
00495                 if ((unsigned)(here.bits) <= bits) break;
00496                 PULLBYTE();
00497             }
00498             if (here.op && (here.op & 0xf0) == 0) {
00499                 last = here;
00500                 for (;;) {
00501                     here = state->lencode[last.val +
00502                             (BITS(last.bits + last.op) >> last.bits)];
00503                     if ((unsigned)(last.bits + here.bits) <= bits) break;
00504                     PULLBYTE();
00505                 }
00506                 DROPBITS(last.bits);
00507             }
00508             DROPBITS(here.bits);
00509             state->length = (unsigned)here.val;
00510 
00511             /* process literal */
00512             if (here.op == 0) {
00513                 Tracevv((stderr, here.val >= 0x20 && here.val < 0x7f ?
00514                         "inflate:         literal '%c'\n" :
00515                         "inflate:         literal 0x%02x\n", here.val));
00516                 ROOM();
00517                 *put++ = (unsigned char)(state->length);
00518                 left--;
00519                 state->mode = LEN;
00520                 break;
00521             }
00522 
00523             /* process end of block */
00524             if (here.op & 32) {
00525                 Tracevv((stderr, "inflate:         end of block\n"));
00526                 state->mode = TYPE;
00527                 break;
00528             }
00529 
00530             /* invalid code */
00531             if (here.op & 64) {
00532                 strm->msg = (char *)"invalid literal/length code";
00533                 state->mode = BAD;
00534                 break;
00535             }
00536 
00537             /* length code -- get extra bits, if any */
00538             state->extra = (unsigned)(here.op) & 15;
00539             if (state->extra != 0) {
00540                 NEEDBITS(state->extra);
00541                 state->length += BITS(state->extra);
00542                 DROPBITS(state->extra);
00543             }
00544             Tracevv((stderr, "inflate:         length %u\n", state->length));
00545 
00546             /* get distance code */
00547             for (;;) {
00548                 here = state->distcode[BITS(state->distbits)];
00549                 if ((unsigned)(here.bits) <= bits) break;
00550                 PULLBYTE();
00551             }
00552             if ((here.op & 0xf0) == 0) {
00553                 last = here;
00554                 for (;;) {
00555                     here = state->distcode[last.val +
00556                             (BITS(last.bits + last.op) >> last.bits)];
00557                     if ((unsigned)(last.bits + here.bits) <= bits) break;
00558                     PULLBYTE();
00559                 }
00560                 DROPBITS(last.bits);
00561             }
00562             DROPBITS(here.bits);
00563             if (here.op & 64) {
00564                 strm->msg = (char *)"invalid distance code";
00565                 state->mode = BAD;
00566                 break;
00567             }
00568             state->offset = (unsigned)here.val;
00569 
00570             /* get distance extra bits, if any */
00571             state->extra = (unsigned)(here.op) & 15;
00572             if (state->extra != 0) {
00573                 NEEDBITS(state->extra);
00574                 state->offset += BITS(state->extra);
00575                 DROPBITS(state->extra);
00576             }
00577             if (state->offset > state->wsize - (state->whave < state->wsize ?
00578                                                 left : 0)) {
00579                 strm->msg = (char *)"invalid distance too far back";
00580                 state->mode = BAD;
00581                 break;
00582             }
00583             Tracevv((stderr, "inflate:         distance %u\n", state->offset));
00584 
00585             /* copy match from window to output */
00586             do {
00587                 ROOM();
00588                 copy = state->wsize - state->offset;
00589                 if (copy < left) {
00590                     from = put + copy;
00591                     copy = left - copy;
00592                 }
00593                 else {
00594                     from = put - state->offset;
00595                     copy = left;
00596                 }
00597                 if (copy > state->length) copy = state->length;
00598                 state->length -= copy;
00599                 left -= copy;
00600                 do {
00601                     *put++ = *from++;
00602                 } while (--copy);
00603             } while (state->length != 0);
00604             break;
00605 
00606         case DONE:
00607             /* inflate stream terminated properly -- write leftover output */
00608             ret = Z_STREAM_END;
00609             if (left < state->wsize) {
00610                 if (out(out_desc, state->window, state->wsize - left))
00611                     ret = Z_BUF_ERROR;
00612             }
00613             goto inf_leave;
00614 
00615         case BAD:
00616             ret = Z_DATA_ERROR;
00617             goto inf_leave;
00618 
00619         default:                /* can't happen, but makes compilers happy */
00620             ret = Z_STREAM_ERROR;
00621             goto inf_leave;
00622         }
00623 
00624     /* Return unused input */
00625   inf_leave:
00626     strm->next_in = next;
00627     strm->avail_in = have;
00628     return ret;
00629 }
00630 
00631 int ZEXPORT inflateBackEnd(strm)
00632 z_streamp strm;
00633 {
00634     if (strm == Z_NULL || strm->state == Z_NULL || strm->zfree == (free_func)0)
00635         return Z_STREAM_ERROR;
00636     ZFREE(strm, strm->state);
00637     strm->state = Z_NULL;
00638     Tracev((stderr, "inflate: end\n"));
00639     return Z_OK;
00640 }