root/lib/libz/infback.c

DEFINITIONS

1. inflateBackInit_
2. fixedtables
3. inflateBack
4. inflateBackEnd

    1 /* infback.c -- inflate using a call-back interface
    2  * Copyright (C) 1995-2005 Mark Adler
    3  * For conditions of distribution and use, see copyright notice in zlib.h
    4  */
    6 /*
    7    This code is largely copied from inflate.c.  Normally either infback.o or
    8    inflate.o would be linked into an application--not both.  The interface
    9    with inffast.c is retained so that optimized assembler-coded versions of
   10    inflate_fast() can be used with either inflate.c or infback.c.
   11  */
   13 #include "zutil.h"
   14 #include "inftrees.h"
   15 #include "inflate.h"
   16 #include "inffast.h"
   18 /* function prototypes */
local void fixedtables OF((struct inflate_state FAR *state));
   21 /*
   22    strm provides memory allocation functions in zalloc and zfree, or
   23    Z_NULL to use the library memory allocation functions.
   24 
   25    windowBits is in the range 8..15, and window is a user-supplied
   26    window and output buffer that is 2**windowBits bytes.
   27  */
   28 int ZEXPORT inflateBackInit_(strm, windowBits, window, version, stream_size)
z_streamp strm;
   30 int windowBits;
   31 unsigned char FAR *window;
   32 const char *version;
   33 int stream_size;
   34 {
   35     struct inflate_state FAR *state;
   37     if (version == Z_NULL || version[0] != ZLIB_VERSION[0] ||
stream_size != (int)(sizeof(z_stream)))
   39         return Z_VERSION_ERROR;
   40     if (strm == Z_NULL || window == Z_NULL ||
windowBits < 8 || windowBits > 15)
   42         return Z_STREAM_ERROR;
strm->msg = Z_NULL;                 /* in case we return an error */
   44     if (strm->zalloc == (alloc_func)0) {
strm->zalloc = zcalloc;
strm->opaque = (voidpf)0;
   47     }
   48     if (strm->zfree == (free_func)0) strm->zfree = zcfree;
state = (struct inflate_state FAR *)ZALLOC(strm, 1,
   50                                                sizeof(struct inflate_state));
   51     if (state == Z_NULL) return Z_MEM_ERROR;
Tracev((stderr, "inflate: allocated\n"));
strm->state = (struct internal_state FAR *)state;
state->dmax = 32768U;
state->wbits = windowBits;
state->wsize = 1U << windowBits;
state->window = window;
state->write = 0;
state->whave = 0;
   60     return Z_OK;
   61 }
   63 /*
   64    Return state with length and distance decoding tables and index sizes set to
   65    fixed code decoding.  Normally this returns fixed tables from inffixed.h.
   66    If BUILDFIXED is defined, then instead this routine builds the tables the
   67    first time it's called, and returns those tables the first time and
   68    thereafter.  This reduces the size of the code by about 2K bytes, in
   69    exchange for a little execution time.  However, BUILDFIXED should not be
   70    used for threaded applications, since the rewriting of the tables and virgin
   71    may not be thread-safe.
   72  */
local void fixedtables(state)
   74 struct inflate_state FAR *state;
   75 {
   76 #ifdef BUILDFIXED
   77     static int virgin = 1;
   78     static code *lenfix, *distfix;
   79     static code fixed[544];
   81     /* build fixed huffman tables if first call (may not be thread safe) */
   82     if (virgin) {
   83         unsigned sym, bits;
   84         static code *next;
   86         /* literal/length table */
sym = 0;
   88         while (sym < 144) state->lens[sym++] = 8;
   89         while (sym < 256) state->lens[sym++] = 9;
   90         while (sym < 280) state->lens[sym++] = 7;
   91         while (sym < 288) state->lens[sym++] = 8;
next = fixed;
lenfix = next;
bits = 9;
inflate_table(LENS, state->lens, 288, &(next), &(bits), state->work);
   97         /* distance table */
sym = 0;
   99         while (sym < 32) state->lens[sym++] = 5;
distfix = next;
bits = 5;
inflate_table(DISTS, state->lens, 32, &(next), &(bits), state->work);
  104         /* do this just once */
virgin = 0;
  106     }
  107 #else /* !BUILDFIXED */
  108 #   include "inffixed.h"
  109 #endif /* BUILDFIXED */
state->lencode = lenfix;
state->lenbits = 9;
state->distcode = distfix;
state->distbits = 5;
  114 }
  116 /* Macros for inflateBack(): */
  118 /* Load returned state from inflate_fast() */
  119 #define LOAD() \
  120     do { \
put = strm->next_out; \
left = strm->avail_out; \
next = strm->next_in; \
have = strm->avail_in; \
hold = state->hold; \
bits = state->bits; \
  127     } while (0)
  129 /* Set state from registers for inflate_fast() */
  130 #define RESTORE() \
  131     do { \
strm->next_out = put; \
strm->avail_out = left; \
strm->next_in = next; \
strm->avail_in = have; \
state->hold = hold; \
state->bits = bits; \
  138     } while (0)
  140 /* Clear the input bit accumulator */
  141 #define INITBITS() \
  142     do { \
hold = 0; \
bits = 0; \
  145     } while (0)
  147 /* Assure that some input is available.  If input is requested, but denied,
  148    then return a Z_BUF_ERROR from inflateBack(). */
  149 #define PULL() \
  150     do { \
  151         if (have == 0) { \
have = in(in_desc, &next); \
  153             if (have == 0) { \
next = Z_NULL; \
ret = Z_BUF_ERROR; \
  156                 goto inf_leave; \
  157             } \
  158         } \
  159     } while (0)
  161 /* Get a byte of input into the bit accumulator, or return from inflateBack()
  162    with an error if there is no input available. */
  163 #define PULLBYTE() \
  164     do { \
PULL(); \
have--; \
hold += (unsigned long)(*next++) << bits; \
bits += 8; \
  169     } while (0)
  171 /* Assure that there are at least n bits in the bit accumulator.  If there is
  172    not enough available input to do that, then return from inflateBack() with
  173    an error. */
  174 #define NEEDBITS(n) \
  175     do { \
  176         while (bits < (unsigned)(n)) \
PULLBYTE(); \
  178     } while (0)
  180 /* Return the low n bits of the bit accumulator (n < 16) */
  181 #define BITS(n) \
  182     ((unsigned)hold & ((1U << (n)) - 1))
  184 /* Remove n bits from the bit accumulator */
  185 #define DROPBITS(n) \
  186     do { \
hold >>= (n); \
bits -= (unsigned)(n); \
  189     } while (0)
  191 /* Remove zero to seven bits as needed to go to a byte boundary */
  192 #define BYTEBITS() \
  193     do { \
hold >>= bits & 7; \
bits -= bits & 7; \
  196     } while (0)
  198 /* Assure that some output space is available, by writing out the window
  199    if it's full.  If the write fails, return from inflateBack() with a
  200    Z_BUF_ERROR. */
  201 #define ROOM() \
  202     do { \
  203         if (left == 0) { \
put = state->window; \
left = state->wsize; \
state->whave = left; \
  207             if (out(out_desc, put, left)) { \
ret = Z_BUF_ERROR; \
  209                 goto inf_leave; \
  210             } \
  211         } \
  212     } while (0)
  214 /*
  215    strm provides the memory allocation functions and window buffer on input,
  216    and provides information on the unused input on return.  For Z_DATA_ERROR
  217    returns, strm will also provide an error message.
  218 
  219    in() and out() are the call-back input and output functions.  When
  220    inflateBack() needs more input, it calls in().  When inflateBack() has
  221    filled the window with output, or when it completes with data in the
  222    window, it calls out() to write out the data.  The application must not
  223    change the provided input until in() is called again or inflateBack()
  224    returns.  The application must not change the window/output buffer until
  225    inflateBack() returns.
  226 
  227    in() and out() are called with a descriptor parameter provided in the
  228    inflateBack() call.  This parameter can be a structure that provides the
  229    information required to do the read or write, as well as accumulated
  230    information on the input and output such as totals and check values.
  231 
  232    in() should return zero on failure.  out() should return non-zero on
  233    failure.  If either in() or out() fails, than inflateBack() returns a
  234    Z_BUF_ERROR.  strm->next_in can be checked for Z_NULL to see whether it
  235    was in() or out() that caused in the error.  Otherwise,  inflateBack()
  236    returns Z_STREAM_END on success, Z_DATA_ERROR for an deflate format
  237    error, or Z_MEM_ERROR if it could not allocate memory for the state.
  238    inflateBack() can also return Z_STREAM_ERROR if the input parameters
  239    are not correct, i.e. strm is Z_NULL or the state was not initialized.
  240  */
  241 int ZEXPORT inflateBack(strm, in, in_desc, out, out_desc)
z_streamp strm;
in_func in;
  244 void FAR *in_desc;
out_func out;
  246 void FAR *out_desc;
  247 {
  248     struct inflate_state FAR *state;
  249     unsigned char FAR *next;    /* next input */
  250     unsigned char FAR *put;     /* next output */
  251     unsigned have, left;        /* available input and output */
  252     unsigned long hold;         /* bit buffer */
  253     unsigned bits;              /* bits in bit buffer */
  254     unsigned copy;              /* number of stored or match bytes to copy */
  255     unsigned char FAR *from;    /* where to copy match bytes from */
code this;                  /* current decoding table entry */
code last;                  /* parent table entry */
  258     unsigned len;               /* length to copy for repeats, bits to drop */
  259     int ret;                    /* return code */
  260     static const unsigned short order[19] = /* permutation of code lengths */
  261         {16, 17, 18, 0, 8, 7, 9, 6, 10, 5, 11, 4, 12, 3, 13, 2, 14, 1, 15};
  263     /* Check that the strm exists and that the state was initialized */
  264     if (strm == Z_NULL || strm->state == Z_NULL)
  265         return Z_STREAM_ERROR;
state = (struct inflate_state FAR *)strm->state;
  268     /* Reset the state */
strm->msg = Z_NULL;
state->mode = TYPE;
state->last = 0;
state->whave = 0;
next = strm->next_in;
have = next != Z_NULL ? strm->avail_in : 0;
hold = 0;
bits = 0;
put = state->window;
left = state->wsize;
  280     /* Inflate until end of block marked as last */
  281     for (;;)
  282         switch (state->mode) {
  283         case TYPE:
  284             /* determine and dispatch block type */
  285             if (state->last) {
BYTEBITS();
state->mode = DONE;
  288                 break;
  289             }
NEEDBITS(3);
state->last = BITS(1);
DROPBITS(1);
  293             switch (BITS(2)) {
  294             case 0:                             /* stored block */
Tracev((stderr, "inflate:     stored block%s\n",
state->last ? " (last)" : ""));
state->mode = STORED;
  298                 break;
  299             case 1:                             /* fixed block */
fixedtables(state);
Tracev((stderr, "inflate:     fixed codes block%s\n",
state->last ? " (last)" : ""));
state->mode = LEN;              /* decode codes */
  304                 break;
  305             case 2:                             /* dynamic block */
Tracev((stderr, "inflate:     dynamic codes block%s\n",
state->last ? " (last)" : ""));
state->mode = TABLE;
  309                 break;
  310             case 3:
  311 #ifdef SMALL  
strm->msg = "error";
  313 #else
strm->msg = (char *)"invalid block type";
  315 #endif
state->mode = BAD;
  317             }
DROPBITS(2);
  319             break;
  321         case STORED:
  322             /* get and verify stored block length */
BYTEBITS();                         /* go to byte boundary */
NEEDBITS(32);
  325             if ((hold & 0xffff) != ((hold >> 16) ^ 0xffff)) {
  326 #ifdef SMALL  
strm->msg = "error";
  328 #else
strm->msg = (char *)"invalid stored block lengths";
  330 #endif
state->mode = BAD;
  332                 break;
  333             }
state->length = (unsigned)hold & 0xffff;
Tracev((stderr, "inflate:       stored length %u\n",
state->length));
INITBITS();
  339             /* copy stored block from input to output */
  340             while (state->length != 0) {
copy = state->length;
PULL();
ROOM();
  344                 if (copy > have) copy = have;
  345                 if (copy > left) copy = left;
zmemcpy(put, next, copy);
have -= copy;
next += copy;
left -= copy;
put += copy;
state->length -= copy;
  352             }
Tracev((stderr, "inflate:       stored end\n"));
state->mode = TYPE;
  355             break;
  357         case TABLE:
  358             /* get dynamic table entries descriptor */
NEEDBITS(14);
state->nlen = BITS(5) + 257;
DROPBITS(5);
state->ndist = BITS(5) + 1;
DROPBITS(5);
state->ncode = BITS(4) + 4;
DROPBITS(4);
  366 #ifndef PKZIP_BUG_WORKAROUND
  367             if (state->nlen > 286 || state->ndist > 30) {
  368 #ifdef SMALL  
strm->msg = "error";
  370 #else
strm->msg = (char *)"too many length or distance symbols";
  372 #endif
state->mode = BAD;
  374                 break;
  375             }
  376 #endif
Tracev((stderr, "inflate:       table sizes ok\n"));
  379             /* get code length code lengths (not a typo) */
state->have = 0;
  381             while (state->have < state->ncode) {
NEEDBITS(3);
state->lens[order[state->have++]] = (unsigned short)BITS(3);
DROPBITS(3);
  385             }
  386             while (state->have < 19)
state->lens[order[state->have++]] = 0;
state->next = state->codes;
state->lencode = (code const FAR *)(state->next);
state->lenbits = 7;
ret = inflate_table(CODES, state->lens, 19, &(state->next),
  392                                 &(state->lenbits), state->work);
  393             if (ret) {
strm->msg = (char *)"invalid code lengths set";
state->mode = BAD;
  396                 break;
  397             }
Tracev((stderr, "inflate:       code lengths ok\n"));
  400             /* get length and distance code code lengths */
state->have = 0;
  402             while (state->have < state->nlen + state->ndist) {
  403                 for (;;) {
this = state->lencode[BITS(state->lenbits)];
  405                     if ((unsigned)(this.bits) <= bits) break;
PULLBYTE();
  407                 }
  408                 if (this.val < 16) {
NEEDBITS(this.bits);
DROPBITS(this.bits);
state->lens[state->have++] = this.val;
  412                 }
  413                 else {
  414                     if (this.val == 16) {
NEEDBITS(this.bits + 2);
DROPBITS(this.bits);
  417                         if (state->have == 0) {
strm->msg = (char *)"invalid bit length repeat";
state->mode = BAD;
  420                             break;
  421                         }
len = (unsigned)(state->lens[state->have - 1]);
copy = 3 + BITS(2);
DROPBITS(2);
  425                     }
  426                     else if (this.val == 17) {
NEEDBITS(this.bits + 3);
DROPBITS(this.bits);
len = 0;
copy = 3 + BITS(3);
DROPBITS(3);
  432                     }
  433                     else {
NEEDBITS(this.bits + 7);
DROPBITS(this.bits);
len = 0;
copy = 11 + BITS(7);
DROPBITS(7);
  439                     }
  440                     if (state->have + copy > state->nlen + state->ndist) {
strm->msg = (char *)"invalid bit length repeat";
state->mode = BAD;
  443                         break;
  444                     }
  445                     while (copy--)
state->lens[state->have++] = (unsigned short)len;
  447                 }
  448             }
  450             /* handle error breaks in while */
  451             if (state->mode == BAD) break;
  453             /* build code tables */
state->next = state->codes;
state->lencode = (code const FAR *)(state->next);
state->lenbits = 9;
ret = inflate_table(LENS, state->lens, state->nlen, &(state->next),
  458                                 &(state->lenbits), state->work);
  459             if (ret) {
strm->msg = (char *)"invalid literal/lengths set";
state->mode = BAD;
  462                 break;
  463             }
state->distcode = (code const FAR *)(state->next);
state->distbits = 6;
ret = inflate_table(DISTS, state->lens + state->nlen, state->ndist,
  467                             &(state->next), &(state->distbits), state->work);
  468             if (ret) {
strm->msg = (char *)"invalid distances set";
state->mode = BAD;
  471                 break;
  472             }
Tracev((stderr, "inflate:       codes ok\n"));
state->mode = LEN;
  476         case LEN:
  477 #ifndef SLOW
  478             /* use inflate_fast() if we have enough input and output */
  479             if (have >= 6 && left >= 258) {
RESTORE();
  481                 if (state->whave < state->wsize)
state->whave = state->wsize - left;
inflate_fast(strm, state->wsize);
LOAD();
  485                 break;
  486             }
  487 #endif
  489             /* get a literal, length, or end-of-block code */
  490             for (;;) {
this = state->lencode[BITS(state->lenbits)];
  492                 if ((unsigned)(this.bits) <= bits) break;
PULLBYTE();
  494             }
  495             if (this.op && (this.op & 0xf0) == 0) {
last = this;
  497                 for (;;) {
this = state->lencode[last.val +
  499                             (BITS(last.bits + last.op) >> last.bits)];
  500                     if ((unsigned)(last.bits + this.bits) <= bits) break;
PULLBYTE();
  502                 }
DROPBITS(last.bits);
  504             }
DROPBITS(this.bits);
state->length = (unsigned)this.val;
  508             /* process literal */
  509             if (this.op == 0) {
Tracevv((stderr, this.val >= 0x20 && this.val < 0x7f ?
  511                         "inflate:         literal '%c'\n" :
  512                         "inflate:         literal 0x%02x\n", this.val));
ROOM();
  514                 *put++ = (unsigned char)(state->length);
left--;
state->mode = LEN;
  517                 break;
  518             }
  520             /* process end of block */
  521             if (this.op & 32) {
Tracevv((stderr, "inflate:         end of block\n"));
state->mode = TYPE;
  524                 break;
  525             }
  527             /* invalid code */
  528             if (this.op & 64) {
strm->msg = (char *)"invalid literal/length code";
state->mode = BAD;
  531                 break;
  532             }
  534             /* length code -- get extra bits, if any */
state->extra = (unsigned)(this.op) & 15;
  536             if (state->extra != 0) {
NEEDBITS(state->extra);
state->length += BITS(state->extra);
DROPBITS(state->extra);
  540             }
Tracevv((stderr, "inflate:         length %u\n", state->length));
  543             /* get distance code */
  544             for (;;) {
this = state->distcode[BITS(state->distbits)];
  546                 if ((unsigned)(this.bits) <= bits) break;
PULLBYTE();
  548             }
  549             if ((this.op & 0xf0) == 0) {
last = this;
  551                 for (;;) {
this = state->distcode[last.val +
  553                             (BITS(last.bits + last.op) >> last.bits)];
  554                     if ((unsigned)(last.bits + this.bits) <= bits) break;
PULLBYTE();
  556                 }
DROPBITS(last.bits);
  558             }
DROPBITS(this.bits);
  560             if (this.op & 64) {
strm->msg = (char *)"invalid distance code";
state->mode = BAD;
  563                 break;
  564             }
state->offset = (unsigned)this.val;
  567             /* get distance extra bits, if any */
state->extra = (unsigned)(this.op) & 15;
  569             if (state->extra != 0) {
NEEDBITS(state->extra);
state->offset += BITS(state->extra);
DROPBITS(state->extra);
  573             }
  574             if (state->offset > state->wsize - (state->whave < state->wsize ?
left : 0)) {
strm->msg = (char *)"invalid distance too far back";
state->mode = BAD;
  578                 break;
  579             }
Tracevv((stderr, "inflate:         distance %u\n", state->offset));
  582             /* copy match from window to output */
  583             do {
ROOM();
copy = state->wsize - state->offset;
  586                 if (copy < left) {
from = put + copy;
copy = left - copy;
  589                 }
  590                 else {
from = put - state->offset;
copy = left;
  593                 }
  594                 if (copy > state->length) copy = state->length;
state->length -= copy;
left -= copy;
  597                 do {
  598                     *put++ = *from++;
  599                 } while (--copy);
  600             } while (state->length != 0);
  601             break;
  603         case DONE:
  604             /* inflate stream terminated properly -- write leftover output */
ret = Z_STREAM_END;
  606             if (left < state->wsize) {
  607                 if (out(out_desc, state->window, state->wsize - left))
ret = Z_BUF_ERROR;
  609             }
  610             goto inf_leave;
  612         case BAD:
ret = Z_DATA_ERROR;
  614             goto inf_leave;
  616         default:                /* can't happen, but makes compilers happy */
ret = Z_STREAM_ERROR;
  618             goto inf_leave;
  619         }
  621     /* Return unused input */
inf_leave:
strm->next_in = next;
strm->avail_in = have;
  625     return ret;
  626 }
  628 int ZEXPORT inflateBackEnd(strm)
z_streamp strm;
  630 {
  631     if (strm == Z_NULL || strm->state == Z_NULL || strm->zfree == (free_func)0)
  632         return Z_STREAM_ERROR;
ZFREE(strm, strm->state);
strm->state = Z_NULL;
Tracev((stderr, "inflate: end\n"));
  636     return Z_OK;
  637 }