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
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 $
16 /* simplify the use of the inflate_huft type with some defines */
17 #define exop word.what.Exop
18 #define bits word.what.Bits
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 */
33 /* inflate codes private state */
34 struct inflate_codes_state {
37 inflate_codes_mode mode; /* current inflate_codes mode */
39 /* mode dependent information */
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 */
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 */
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 */
62 inflate_codes_statef *inflate_codes_new(bl, bd, tl, td, z)
65 inflate_huft *td; /* need separate declaration for Borland C++ */
68 inflate_codes_statef *c;
70 if ((c = (inflate_codes_statef *)
71 ZALLOC(z,1,sizeof(struct inflate_codes_state))) != Z_NULL)
78 Tracev((stderr, "inflate: codes new\n"));
84 int inflate_codes(s, z, r)
85 inflate_blocks_statef *s;
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 */
101 /* copy input/output information to locals (UPDATE macro restores) */
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 */
109 if (m >= 258 && n >= 10)
112 r = inflate_fast(c->lbits, c->dbits, c->ltree, c->dtree, s, z);
116 c->mode = r == Z_STREAM_END ? WASH : BADCODE;
121 c->sub.code.need = c->lbits;
122 c->sub.code.tree = c->ltree;
124 case LEN: /* i: get length/literal/eob next */
125 j = c->sub.code.need;
127 t = c->sub.code.tree + ((uInt)b & inflate_mask[j]);
130 if (e == 0) /* literal */
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));
139 if (e & 16) /* length */
141 c->sub.copy.get = e & 15;
146 if ((e & 64) == 0) /* next table */
148 c->sub.code.need = e;
149 c->sub.code.tree = t + t->base;
152 if (e & 32) /* end of block */
154 Tracevv((stderr, "inflate: end of block\n"));
158 c->mode = BADCODE; /* invalid code */
159 z->msg = (char*)"invalid literal/length code";
162 case LENEXT: /* i: getting length extra (have base) */
165 c->len += (uInt)b & inflate_mask[j];
167 c->sub.code.need = c->dbits;
168 c->sub.code.tree = c->dtree;
169 Tracevv((stderr, "inflate: length %u\n", c->len));
171 case DIST: /* i: get distance next */
172 j = c->sub.code.need;
174 t = c->sub.code.tree + ((uInt)b & inflate_mask[j]);
177 if (e & 16) /* distance */
179 c->sub.copy.get = e & 15;
180 c->sub.copy.dist = t->base;
184 if ((e & 64) == 0) /* next table */
186 c->sub.code.need = e;
187 c->sub.code.tree = t + t->base;
190 c->mode = BADCODE; /* invalid code */
191 z->msg = (char*)"invalid distance code";
194 case DISTEXT: /* i: getting distance extra */
197 c->sub.copy.dist += (uInt)b & inflate_mask[j];
199 Tracevv((stderr, "inflate: distance %u\n", c->sub.copy.dist));
201 case COPY: /* o: copying bytes in window, waiting for space */
202 f = q - c->sub.copy.dist;
204 /* XXX work around a gcc bug. */
205 volatile inflate_blocks_statef *s1 = s;
207 while (f < s1->window) /* modulo window size-"while" instead */
208 f += s1->end - s1->window; /* of "if" handles invalid distances */
220 case LIT: /* o: got literal, waiting for output space */
225 case WASH: /* o: got eob, possibly more output */
226 if (k > 7) /* return unused byte, if any */
228 Assert(k < 16, "inflate_codes grabbed too many bytes")
231 p--; /* can always return one */
234 if (s->read != s->write)
240 case BADCODE: /* x: got error */
247 #ifdef NEED_DUMMY_RETURN
248 return Z_STREAM_ERROR; /* Some dumb compilers complain without this */
253 void inflate_codes_free(c, z)
254 inflate_codes_statef *c;
258 Tracev((stderr, "inflate: codes free\n"));