Back to index

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