Back to index

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