Back to index

plt-scheme  4.2.1
infcodes.c
Go to the documentation of this file.
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 }