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