- Main Page
- Namespaces
- Classes
- Files
- Directories

- File List
- File Members

# infcodes.c

    00001 /* infcodes.c -- process literals and length/distance pairs
    00002  * Copyright (C) 1995-2002 Mark Adler
    00003  * For conditions of distribution and use, see copyright notice in zlib.h
    00004  */
    00005
    00006 #include "zutil.h"
    00007 #include "inftrees.h"
    00008 #include "infblock.h"
    00009 #include "infcodes.h"
    00010 #include "infutil.h"
    00011 #include "inffast.h"
    00012
    00013 /* simplify the use of the inflate_huft type with some defines */
    00014 #define exop word.what.Exop
    00015 #define bits word.what.Bits
    00016
    00017 typedef enum {        /* waiting for "i:"=input, "o:"=output, "x:"=nothing */
    00018       START,    /* x: set up for LEN */
    00019       LEN,      /* i: get length/literal/eob next */
    00020       LENEXT,   /* i: getting length extra (have base) */
    00021       DIST,     /* i: get distance next */
    00022       DISTEXT,  /* i: getting distance extra */
    00023       COPY,     /* o: copying bytes in window, waiting for space */
    00024       LIT,      /* o: got literal, waiting for output space */
    00025       WASH,     /* o: got eob, possibly still output waiting */
    00026       END,      /* x: got eob and all data flushed */
    00027       BADCODE}  /* x: got error */
    00028 inflate_codes_mode;
    00029
    00030 /* inflate codes private state */
    00031 struct inflate_codes_state {
    00032
    00033   /* mode */
    00034   inflate_codes_mode mode;      /* current inflate_codes mode */
    00035
    00036   /* mode dependent information */
    00037   uInt len;
    00038   union {
    00039     struct {
    00040       inflate_huft *tree;       /* pointer into tree */
    00041       uInt need;                /* bits needed */
    00042     } code;             /* if LEN or DIST, where in tree */
    00043     uInt lit;           /* if LIT, literal */
    00044     struct {
    00045       uInt get;                 /* bits to get for extra */
    00046       uInt dist;                /* distance back to copy from */
    00047     } copy;             /* if EXT or COPY, where and how much */
    00048   } sub;                /* submode */
    00049
    00050   /* mode independent information */
    00051   Byte lbits;           /* ltree bits decoded per branch */
    00052   Byte dbits;           /* dtree bits decoder per branch */
    00053   inflate_huft *ltree;          /* literal/length/eob tree */
    00054   inflate_huft *dtree;          /* distance tree */
    00055
    00056 };
    00057
    00058
    00059 inflate_codes_statef *inflate_codes_new(bl, bd, tl, td, z)
    00060 uInt bl, bd;
    00061 inflate_huft *tl;
    00062 inflate_huft *td; /* need separate declaration for Borland C++ */
    00063 z_streamp z;
    00064 {
    00065   inflate_codes_statef *c;
    00066
    00067   if ((c = (inflate_codes_statef *)
    00068        ZALLOC(z,1,sizeof(struct inflate_codes_state))) != Z_NULL)
    00069   {
    00070     c->mode = START;
    00071     c->lbits = (Byte)bl;
    00072     c->dbits = (Byte)bd;
    00073     c->ltree = tl;
    00074     c->dtree = td;
    00075     Tracev((stderr, "inflate:       codes new\n"));
    00076   }
    00077   return c;
    00078 }
    00079
    00080
    00081 int inflate_codes(s, z, r)
    00082 inflate_blocks_statef *s;
    00083 z_streamp z;
    00084 int r;
    00085 {
    00086   uInt j;               /* temporary storage */
    00087   inflate_huft *t;      /* temporary pointer */
    00088   uInt e;               /* extra bits or operation */
    00089   uLong b;              /* bit buffer */
    00090   uInt k;               /* bits in bit buffer */
    00091   Bytef *p;             /* input data pointer */
    00092   uInt n;               /* bytes available there */
    00093   Bytef *q;             /* output window write pointer */
    00094   uInt m;               /* bytes to end of window or read pointer */
    00095   Bytef *f;             /* pointer to copy strings from */
    00096   inflate_codes_statef *c = s->sub.decode.codes;  /* codes state */
    00097
    00098   /* copy input/output information to locals (UPDATE macro restores) */
    00099   LOAD
    00100
    00101   /* process input and output based on current state */
    00102   while (1) switch (c->mode)
    00103   {             /* waiting for "i:"=input, "o:"=output, "x:"=nothing */
    00104     case START:         /* x: set up for LEN */
    00105 #ifndef SLOW
    00106       if (m >= 258 && n >= 10)
    00107       {
    00108         UPDATE
    00109         r = inflate_fast(c->lbits, c->dbits, c->ltree, c->dtree, s, z);
    00110         LOAD
    00111         if (r != Z_OK)
    00112         {
    00113           c->mode = r == Z_STREAM_END ? WASH : BADCODE;
    00114           break;
    00115         }
    00116       }
    00117 #endif /* !SLOW */
    00118       c->sub.code.need = c->lbits;
    00119       c->sub.code.tree = c->ltree;
    00120       c->mode = LEN;
    00121     case LEN:           /* i: get length/literal/eob next */
    00122       j = c->sub.code.need;
    00123       NEEDBITS(j)
    00124       t = c->sub.code.tree + ((uInt)b & inflate_mask[j]);
    00125       DUMPBITS(t->bits)
    00126       e = (uInt)(t->exop);
    00127       if (e == 0)               /* literal */
    00128       {
    00129         c->sub.lit = t->base;
    00130         Tracevv((stderr, t->base >= 0x20 && t->base < 0x7f ?
    00131                  "inflate:         literal '%c'\n" :
    00132                  "inflate:         literal 0x%02x\n", t->base));
    00133         c->mode = LIT;
    00134         break;
    00135       }
    00136       if (e & 16)               /* length */
    00137       {
    00138         c->sub.copy.get = e & 15;
    00139         c->len = t->base;
    00140         c->mode = LENEXT;
    00141         break;
    00142       }
    00143       if ((e & 64) == 0)        /* next table */
    00144       {
    00145         c->sub.code.need = e;
    00146         c->sub.code.tree = t + t->base;
    00147         break;
    00148       }
    00149       if (e & 32)               /* end of block */
    00150       {
    00151         Tracevv((stderr, "inflate:         end of block\n"));
    00152         c->mode = WASH;
    00153         break;
    00154       }
    00155       c->mode = BADCODE;        /* invalid code */
    00156       z->msg = (char*)"invalid literal/length code";
    00157       r = Z_DATA_ERROR;
    00158       LEAVE
    00159     case LENEXT:        /* i: getting length extra (have base) */
    00160       j = c->sub.copy.get;
    00161       NEEDBITS(j)
    00162       c->len += (uInt)b & inflate_mask[j];
    00163       DUMPBITS(j)
    00164       c->sub.code.need = c->dbits;
    00165       c->sub.code.tree = c->dtree;
    00166       Tracevv((stderr, "inflate:         length %u\n", c->len));
    00167       c->mode = DIST;
    00168     case DIST:          /* i: get distance next */
    00169       j = c->sub.code.need;
    00170       NEEDBITS(j)
    00171       t = c->sub.code.tree + ((uInt)b & inflate_mask[j]);
    00172       DUMPBITS(t->bits)
    00173       e = (uInt)(t->exop);
    00174       if (e & 16)               /* distance */
    00175       {
    00176         c->sub.copy.get = e & 15;
    00177         c->sub.copy.dist = t->base;
    00178         c->mode = DISTEXT;
    00179         break;
    00180       }
    00181       if ((e & 64) == 0)        /* next table */
    00182       {
    00183         c->sub.code.need = e;
    00184         c->sub.code.tree = t + t->base;
    00185         break;
    00186       }
    00187       c->mode = BADCODE;        /* invalid code */
    00188       z->msg = (char*)"invalid distance code";
    00189       r = Z_DATA_ERROR;
    00190       LEAVE
    00191     case DISTEXT:       /* i: getting distance extra */
    00192       j = c->sub.copy.get;
    00193       NEEDBITS(j)
    00194       c->sub.copy.dist += (uInt)b & inflate_mask[j];
    00195       DUMPBITS(j)
    00196       Tracevv((stderr, "inflate:         distance %u\n", c->sub.copy.dist));
    00197       c->mode = COPY;
    00198     case COPY:          /* o: copying bytes in window, waiting for space */
    00199       f = q - c->sub.copy.dist;
    00200       while (f < s->window)             /* modulo window size-"while" instead */
    00201         f += s->end - s->window;        /* of "if" handles invalid distances */
    00202       while (c->len)
    00203       {
    00204         NEEDOUT
    00205         OUTBYTE(*f++)
    00206         if (f == s->end)
    00207           f = s->window;
    00208         c->len--;
    00209       }
    00210       c->mode = START;
    00211       break;
    00212     case LIT:           /* o: got literal, waiting for output space */
    00213       NEEDOUT
    00214       OUTBYTE(c->sub.lit)
    00215       c->mode = START;
    00216       break;
    00217     case WASH:          /* o: got eob, possibly more output */
    00218       if (k > 7)        /* return unused byte, if any */
    00219       {
    00220         Assert(k < 16, "inflate_codes grabbed too many bytes")
    00221         k -= 8;
    00222         n++;
    00223         p--;            /* can always return one */
    00224       }
    00225       FLUSH
    00226       if (s->read != s->write)
    00227         LEAVE
    00228       c->mode = END;
    00229     case END:
    00230       r = Z_STREAM_END;
    00231       LEAVE
    00232     case BADCODE:       /* x: got error */
    00233       r = Z_DATA_ERROR;
    00234       LEAVE
    00235     default:
    00236       r = Z_STREAM_ERROR;
    00237       LEAVE
    00238   }
    00239 #ifdef NEED_DUMMY_RETURN
    00240   return Z_STREAM_ERROR;  /* Some dumb compilers complain without this */
    00241 #endif
    00242 }
    00243
    00244
    00245 void inflate_codes_free(c, z)
    00246 inflate_codes_statef *c;
    00247 z_streamp z;
    00248 {
    00249   ZFREE(z, c);
    00250   Tracev((stderr, "inflate:       codes free\n"));
    00251 }