lib/libz/infcodes.c

   1 /* infcodes.c -- process literals and length/distance pairs
   2  * Copyright (C) 1995-2002 Mark Adler
   3  * For conditions of distribution and use, see copyright notice in zlib.h
   4  *
   5  * $FreeBSD: src/lib/libz/infcodes.c,v 1.1.1.3.6.1 2003/02/01 13:33:12 sobomax Exp $
   6  * $DragonFly: src/lib/libz/Attic/infcodes.c,v 1.2 2003/06/17 04:26:52 dillon Exp $
   7  */
   8
   9 #include "zutil.h"
  10 #include "inftrees.h"
  11 #include "infblock.h"
  12 #include "infcodes.h"
  13 #include "infutil.h"
  14 #include "inffast.h"
  15
  16 /* simplify the use of the inflate_huft type with some defines */
  17 #define exop word.what.Exop
  18 #define bits word.what.Bits
  19
  20 typedef enum {        /* waiting for "i:"=input, "o:"=output, "x:"=nothing */
  21       START,    /* x: set up for LEN */
  22       LEN,      /* i: get length/literal/eob next */
  23       LENEXT,   /* i: getting length extra (have base) */
  24       DIST,     /* i: get distance next */
  25       DISTEXT,  /* i: getting distance extra */
  26       COPY,     /* o: copying bytes in window, waiting for space */
  27       LIT,      /* o: got literal, waiting for output space */
  28       WASH,     /* o: got eob, possibly still output waiting */
  29       END,      /* x: got eob and all data flushed */
  30       BADCODE}  /* x: got error */
  31 inflate_codes_mode;
  32
  33 /* inflate codes private state */
  34 struct inflate_codes_state {
  35
  36   /* mode */
  37   inflate_codes_mode mode;      /* current inflate_codes mode */
  38
  39   /* mode dependent information */
  40   uInt len;
  41   union {
  42     struct {
  43       inflate_huft *tree;       /* pointer into tree */
  44       uInt need;                /* bits needed */
  45     } code;             /* if LEN or DIST, where in tree */
  46     uInt lit;           /* if LIT, literal */
  47     struct {
  48       uInt get;                 /* bits to get for extra */
  49       uInt dist;                /* distance back to copy from */
  50     } copy;             /* if EXT or COPY, where and how much */
  51   } sub;                /* submode */
  52
  53   /* mode independent information */
  54   Byte lbits;           /* ltree bits decoded per branch */
  55   Byte dbits;           /* dtree bits decoder per branch */
  56   inflate_huft *ltree;          /* literal/length/eob tree */
  57   inflate_huft *dtree;          /* distance tree */
  58
  59 };
  60
  61
  62 inflate_codes_statef *inflate_codes_new(bl, bd, tl, td, z)
  63 uInt bl, bd;
  64 inflate_huft *tl;
  65 inflate_huft *td; /* need separate declaration for Borland C++ */
  66 z_streamp z;
  67 {
  68   inflate_codes_statef *c;
  69
  70   if ((c = (inflate_codes_statef *)
  71        ZALLOC(z,1,sizeof(struct inflate_codes_state))) != Z_NULL)
  72   {
  73     c->mode = START;
  74     c->lbits = (Byte)bl;
  75     c->dbits = (Byte)bd;
  76     c->ltree = tl;
  77     c->dtree = td;
  78     Tracev((stderr, "inflate:       codes new\n"));
  79   }
  80   return c;
  81 }
  82
  83
  84 int inflate_codes(s, z, r)
  85 inflate_blocks_statef *s;
  86 z_streamp z;
  87 int r;
  88 {
  89   uInt j;               /* temporary storage */
  90   inflate_huft *t;      /* temporary pointer */
  91   uInt e;               /* extra bits or operation */
  92   uLong b;              /* bit buffer */
  93   uInt k;               /* bits in bit buffer */
  94   Bytef *p;             /* input data pointer */
  95   uInt n;               /* bytes available there */
  96   Bytef *q;             /* output window write pointer */
  97   uInt m;               /* bytes to end of window or read pointer */
  98   Bytef *f;             /* pointer to copy strings from */
  99   inflate_codes_statef *c = s->sub.decode.codes;  /* codes state */
 100
 101   /* copy input/output information to locals (UPDATE macro restores) */
 102   LOAD
 103
 104   /* process input and output based on current state */
 105   while (1) switch (c->mode)
 106   {             /* waiting for "i:"=input, "o:"=output, "x:"=nothing */
 107     case START:         /* x: set up for LEN */
 108 #ifndef SLOW
 109       if (m >= 258 && n >= 10)
 110       {
 111         UPDATE
 112         r = inflate_fast(c->lbits, c->dbits, c->ltree, c->dtree, s, z);
 113         LOAD
 114         if (r != Z_OK)
 115         {
 116           c->mode = r == Z_STREAM_END ? WASH : BADCODE;
 117           break;
 118         }
 119       }
 120 #endif /* !SLOW */
 121       c->sub.code.need = c->lbits;
 122       c->sub.code.tree = c->ltree;
 123       c->mode = LEN;
 124     case LEN:           /* i: get length/literal/eob next */
 125       j = c->sub.code.need;
 126       NEEDBITS(j)
 127       t = c->sub.code.tree + ((uInt)b & inflate_mask[j]);
 128       DUMPBITS(t->bits)
 129       e = (uInt)(t->exop);
 130       if (e == 0)               /* literal */
 131       {
 132         c->sub.lit = t->base;
 133         Tracevv((stderr, t->base >= 0x20 && t->base < 0x7f ?
 134                  "inflate:         literal '%c'\n" :
 135                  "inflate:         literal 0x%02x\n", t->base));
 136         c->mode = LIT;
 137         break;
 138       }
 139       if (e & 16)               /* length */
 140       {
 141         c->sub.copy.get = e & 15;
 142         c->len = t->base;
 143         c->mode = LENEXT;
 144         break;
 145       }
 146       if ((e & 64) == 0)        /* next table */
 147       {
 148         c->sub.code.need = e;
 149         c->sub.code.tree = t + t->base;
 150         break;
 151       }
 152       if (e & 32)               /* end of block */
 153       {
 154         Tracevv((stderr, "inflate:         end of block\n"));
 155         c->mode = WASH;
 156         break;
 157       }
 158       c->mode = BADCODE;        /* invalid code */
 159       z->msg = (char*)"invalid literal/length code";
 160       r = Z_DATA_ERROR;
 161       LEAVE
 162     case LENEXT:        /* i: getting length extra (have base) */
 163       j = c->sub.copy.get;
 164       NEEDBITS(j)
 165       c->len += (uInt)b & inflate_mask[j];
 166       DUMPBITS(j)
 167       c->sub.code.need = c->dbits;
 168       c->sub.code.tree = c->dtree;
 169       Tracevv((stderr, "inflate:         length %u\n", c->len));
 170       c->mode = DIST;
 171     case DIST:          /* i: get distance next */
 172       j = c->sub.code.need;
 173       NEEDBITS(j)
 174       t = c->sub.code.tree + ((uInt)b & inflate_mask[j]);
 175       DUMPBITS(t->bits)
 176       e = (uInt)(t->exop);
 177       if (e & 16)               /* distance */
 178       {
 179         c->sub.copy.get = e & 15;
 180         c->sub.copy.dist = t->base;
 181         c->mode = DISTEXT;
 182         break;
 183       }
 184       if ((e & 64) == 0)        /* next table */
 185       {
 186         c->sub.code.need = e;
 187         c->sub.code.tree = t + t->base;
 188         break;
 189       }
 190       c->mode = BADCODE;        /* invalid code */
 191       z->msg = (char*)"invalid distance code";
 192       r = Z_DATA_ERROR;
 193       LEAVE
 194     case DISTEXT:       /* i: getting distance extra */
 195       j = c->sub.copy.get;
 196       NEEDBITS(j)
 197       c->sub.copy.dist += (uInt)b & inflate_mask[j];
 198       DUMPBITS(j)
 199       Tracevv((stderr, "inflate:         distance %u\n", c->sub.copy.dist));
 200       c->mode = COPY;
 201     case COPY:          /* o: copying bytes in window, waiting for space */
 202       f = q - c->sub.copy.dist;
 203       {
 204       /* XXX work around a gcc bug. */
 205       volatile inflate_blocks_statef *s1 = s;
 206
 207       while (f < s1->window)            /* modulo window size-"while" instead */
 208         f += s1->end - s1->window;      /* of "if" handles invalid distances */
 209       }
 210       while (c->len)
 211       {
 212         NEEDOUT
 213         OUTBYTE(*f++)
 214         if (f == s->end)
 215           f = s->window;
 216         c->len--;
 217       }
 218       c->mode = START;
 219       break;
 220     case LIT:           /* o: got literal, waiting for output space */
 221       NEEDOUT
 222       OUTBYTE(c->sub.lit)
 223       c->mode = START;
 224       break;
 225     case WASH:          /* o: got eob, possibly more output */
 226       if (k > 7)        /* return unused byte, if any */
 227       {
 228         Assert(k < 16, "inflate_codes grabbed too many bytes")
 229         k -= 8;
 230         n++;
 231         p--;            /* can always return one */
 232       }
 233       FLUSH
 234       if (s->read != s->write)
 235         LEAVE
 236       c->mode = END;
 237     case END:
 238       r = Z_STREAM_END;
 239       LEAVE
 240     case BADCODE:       /* x: got error */
 241       r = Z_DATA_ERROR;
 242       LEAVE
 243     default:
 244       r = Z_STREAM_ERROR;
 245       LEAVE
 246   }
 247 #ifdef NEED_DUMMY_RETURN
 248   return Z_STREAM_ERROR;  /* Some dumb compilers complain without this */
 249 #endif
 250 }
 251
 252
 253 void inflate_codes_free(c, z)
 254 inflate_codes_statef *c;
 255 z_streamp z;
 256 {
 257   ZFREE(z, c);
 258   Tracev((stderr, "inflate:       codes free\n"));
 259 }