infcodes.c

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