1 /* $NetBSD: infblock.c,v 1.6 2003/03/25 22:48:44 mycroft Exp $ */
2
3 /* infblock.c -- interpret and process block types to last block
4 * Copyright (C) 1995-2002 Mark Adler
5 * For conditions of distribution and use, see copyright notice in zlib.h
6 */
7
8 #include "zutil.h"
9 #include "infblock.h"
10 #include "inftrees.h"
11 #include "infcodes.h"
12 #include "infutil.h"
13
14 struct inflate_codes_state {int dummy;}; /* for buggy compilers */
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 /* Table for deflate from PKZIP's appnote.txt. */
21 local const uInt border[] = { /* Order of the bit length code lengths */
22 16, 17, 18, 0, 8, 7, 9, 6, 10, 5, 11, 4, 12, 3, 13, 2, 14, 1, 15};
23
24 /*
25 Notes beyond the 1.93a appnote.txt:
26
27 1. Distance pointers never point before the beginning of the output
28 stream.
29 2. Distance pointers can point back across blocks, up to 32k away.
30 3. There is an implied maximum of 7 bits for the bit length table and
31 15 bits for the actual data.
32 4. If only one code exists, then it is encoded using one bit. (Zero
33 would be more efficient, but perhaps a little confusing.) If two
34 codes exist, they are coded using one bit each (0 and 1).
35 5. There is no way of sending zero distance codes--a dummy must be
36 sent if there are none. (History: a pre 2.0 version of PKZIP would
37 store blocks with no distance codes, but this was discovered to be
38 too harsh a criterion.) Valid only for 1.93a. 2.04c does allow
39 zero distance codes, which is sent as one code of zero bits in
40 length.
41 6. There are up to 286 literal/length codes. Code 256 represents the
42 end-of-block. Note however that the static length tree defines
43 288 codes just to fill out the Huffman codes. Codes 286 and 287
44 cannot be used though, since there is no length base or extra bits
45 defined for them. Similarily, there are up to 30 distance codes.
46 However, static trees define 32 codes (all 5 bits) to fill out the
47 Huffman codes, but the last two had better not show up in the data.
48 7. Unzip can check dynamic Huffman blocks for complete code sets.
49 The exception is that a single code would not be complete (see #4).
50 8. The five bits following the block type is really the number of
51 literal codes sent minus 257.
52 9. Length codes 8,16,16 are interpreted as 13 length codes of 8 bits
53 (1+6+6). Therefore, to output three times the length, you output
54 three codes (1+1+1), whereas to output four times the same length,
55 you only need two codes (1+3). Hmm.
56 10. In the tree reconstruction algorithm, Code = Code + Increment
57 only if BitLength(i) is not zero. (Pretty obvious.)
58 11. Correction: 4 Bits: # of Bit Length codes - 4 (4 - 19)
59 12. Note: length code 284 can represent 227-258, but length code 285
60 really is 258. The last length deserves its own, short code
61 since it gets used a lot in very redundant files. The length
62 258 is special since 258 - 3 (the min match length) is 255.
63 13. The literal/length and distance code bit lengths are read as a
64 single stream of lengths. It is possible (and advantageous) for
65 a repeat code (16, 17, or 18) to go across the boundary between
66 the two sets of lengths.
67 */
68
69
70 void inflate_blocks_reset(s, z, c)
71 inflate_blocks_statef *s;
72 z_streamp z;
73 uLongf *c;
74 {
75 if (c)
76 *c = 0;
77 if (s->mode == BTREE || s->mode == DTREE)
78 ZFREE(z, s->sub.trees.blens);
79 if (s->mode == CODES)
80 inflate_codes_free(s->sub.decode.codes, z);
81 s->mode = TYPE;
82 s->bitk = 0;
83 s->bitb = 0;
84 s->read = s->write = s->window;
85 Tracev((stderr, "inflate: blocks reset\n"));
86 }
87
88
89 inflate_blocks_statef *inflate_blocks_new(z, c, w)
90 z_streamp z;
91 check_func c;
92 uInt w;
93 {
94 inflate_blocks_statef *s;
95
96 if ((s = (inflate_blocks_statef *)ZALLOC
97 (z,1,sizeof(struct inflate_blocks_state))) == Z_NULL)
98 return s;
99 if ((s->hufts =
100 (inflate_huft *)ZALLOC(z, sizeof(inflate_huft), MANY)) == Z_NULL)
101 {
102 ZFREE(z, s);
103 return Z_NULL;
104 }
105 if ((s->window = (Bytef *)ZALLOC(z, 1, w)) == Z_NULL)
106 {
107 ZFREE(z, s->hufts);
108 ZFREE(z, s);
109 return Z_NULL;
110 }
111 s->end = s->window + w;
112 if (c)
113 return Z_NULL;
114 s->mode = TYPE;
115 Tracev((stderr, "inflate: blocks allocated\n"));
116 inflate_blocks_reset(s, z, Z_NULL);
117 return s;
118 }
119
120
121 int inflate_blocks(s, z, r)
122 inflate_blocks_statef *s;
123 z_streamp z;
124 int r;
125 {
126 uInt t; /* temporary storage */
127 uLong b; /* bit buffer */
128 uInt k; /* bits in bit buffer */
129 Bytef *p; /* input data pointer */
130 uInt n; /* bytes available there */
131 Bytef *q; /* output window write pointer */
132 uInt m; /* bytes to end of window or read pointer */
133
134 /* copy input/output information to locals (UPDATE macro restores) */
135 LOAD
136
137 /* process input based on current state */
138 while (1) switch (s->mode)
139 {
140 case TYPE:
141 NEEDBITS(3)
142 t = (uInt)b & 7;
143 s->last = t & 1;
144 switch (t >> 1)
145 {
146 case 0: /* stored */
147 Tracev((stderr, "inflate: stored block%s\n",
148 s->last ? " (last)" : ""));
149 DUMPBITS(3)
150 t = k & 7; /* go to byte boundary */
151 DUMPBITS(t)
152 s->mode = LENS; /* get length of stored block */
153 break;
154 case 1: /* fixed */
155 Tracev((stderr, "inflate: fixed codes block%s\n",
156 s->last ? " (last)" : ""));
157 {
158 uInt bl, bd;
159 const inflate_huft *tl, *td;
160
161 inflate_trees_fixed(&bl, &bd, &tl, &td, z);
162 s->sub.decode.codes = inflate_codes_new(bl, bd, tl, td, z);
163 if (s->sub.decode.codes == Z_NULL)
164 {
165 r = Z_MEM_ERROR;
166 LEAVE
167 }
168 }
169 DUMPBITS(3)
170 s->mode = CODES;
171 break;
172 case 2: /* dynamic */
173 Tracev((stderr, "inflate: dynamic codes block%s\n",
174 s->last ? " (last)" : ""));
175 DUMPBITS(3)
176 s->mode = TABLE;
177 break;
178 case 3: /* illegal */
179 DUMPBITS(3)
180 s->mode = BAD;
181 z->msg = (char*)"invalid block type";
182 r = Z_DATA_ERROR;
183 LEAVE
184 }
185 break;
186 case LENS:
187 NEEDBITS(32)
188 if ((((~b) >> 16) & 0xffff) != (b & 0xffff))
189 {
190 s->mode = BAD;
191 z->msg = (char*)"invalid stored block lengths";
192 r = Z_DATA_ERROR;
193 LEAVE
194 }
195 s->sub.left = (uInt)b & 0xffff;
196 b = k = 0; /* dump bits */
197 Tracev((stderr, "inflate: stored length %u\n", s->sub.left));
198 s->mode = s->sub.left ? STORED : (s->last ? DRY : TYPE);
199 break;
200 case STORED:
201 if (n == 0)
202 LEAVE
203 NEEDOUT
204 t = s->sub.left;
205 if (t > n) t = n;
206 if (t > m) t = m;
207 zmemcpy(q, p, t);
208 p += t; n -= t;
209 q += t; m -= t;
210 if ((s->sub.left -= t) != 0)
211 break;
212 Tracev((stderr, "inflate: stored end, %lu total out\n",
213 z->total_out + (q >= s->read ? q - s->read :
214 (s->end - s->read) + (q - s->window))));
215 s->mode = s->last ? DRY : TYPE;
216 break;
217 case TABLE:
218 NEEDBITS(14)
219 s->sub.trees.table = t = (uInt)b & 0x3fff;
220 #ifndef PKZIP_BUG_WORKAROUND
221 if ((t & 0x1f) > 29 || ((t >> 5) & 0x1f) > 29)
222 {
223 s->mode = BAD;
224 z->msg = (char*)"too many length or distance symbols";
225 r = Z_DATA_ERROR;
226 LEAVE
227 }
228 #endif
229 t = 258 + (t & 0x1f) + ((t >> 5) & 0x1f);
230 if ((s->sub.trees.blens = (uIntf*)ZALLOC(z, t, sizeof(uInt))) == Z_NULL)
231 {
232 r = Z_MEM_ERROR;
233 LEAVE
234 }
235 DUMPBITS(14)
236 s->sub.trees.index = 0;
237 Tracev((stderr, "inflate: table sizes ok\n"));
238 s->mode = BTREE;
239 case BTREE:
240 while (s->sub.trees.index < 4 + (s->sub.trees.table >> 10))
241 {
242 NEEDBITS(3)
243 s->sub.trees.blens[border[s->sub.trees.index++]] = (uInt)b & 7;
244 DUMPBITS(3)
245 }
246 while (s->sub.trees.index < 19)
247 s->sub.trees.blens[border[s->sub.trees.index++]] = 0;
248 s->sub.trees.bb = 7;
249 t = inflate_trees_bits(s->sub.trees.blens, &s->sub.trees.bb,
250 &s->sub.trees.tb, s->hufts, z);
251 if (t != Z_OK)
252 {
253 r = t;
254 if (r == Z_DATA_ERROR)
255 {
256 ZFREE(z, s->sub.trees.blens);
257 s->mode = BAD;
258 }
259 LEAVE
260 }
261 s->sub.trees.index = 0;
262 Tracev((stderr, "inflate: bits tree ok\n"));
263 s->mode = DTREE;
264 case DTREE:
265 while (t = s->sub.trees.table,
266 s->sub.trees.index < 258 + (t & 0x1f) + ((t >> 5) & 0x1f))
267 {
268 inflate_huft *h;
269 uInt i, j, c;
270
271 t = s->sub.trees.bb;
272 NEEDBITS(t)
273 h = s->sub.trees.tb + ((uInt)b & inflate_mask[t]);
274 t = h->bits;
275 c = h->base;
276 if (c < 16)
277 {
278 DUMPBITS(t)
279 s->sub.trees.blens[s->sub.trees.index++] = c;
280 }
281 else /* c == 16..18 */
282 {
283 i = c == 18 ? 7 : c - 14;
284 j = c == 18 ? 11 : 3;
285 NEEDBITS(t + i)
286 DUMPBITS(t)
287 j += (uInt)b & inflate_mask[i];
288 DUMPBITS(i)
289 i = s->sub.trees.index;
290 t = s->sub.trees.table;
291 if (i + j > 258 + (t & 0x1f) + ((t >> 5) & 0x1f) ||
292 (c == 16 && i < 1))
293 {
294 ZFREE(z, s->sub.trees.blens);
295 s->mode = BAD;
296 z->msg = (char*)"invalid bit length repeat";
297 r = Z_DATA_ERROR;
298 LEAVE
299 }
300 c = c == 16 ? s->sub.trees.blens[i - 1] : 0;
301 do {
302 s->sub.trees.blens[i++] = c;
303 } while (--j);
304 s->sub.trees.index = i;
305 }
306 }
307 s->sub.trees.tb = Z_NULL;
308 {
309 uInt bl, bd;
310 inflate_huft *tl, *td;
311 inflate_codes_statef *c;
312
313 bl = 9; /* must be <= 9 for lookahead assumptions */
314 bd = 6; /* must be <= 9 for lookahead assumptions */
315 t = s->sub.trees.table;
316 t = inflate_trees_dynamic(257 + (t & 0x1f), 1 + ((t >> 5) & 0x1f),
317 s->sub.trees.blens, &bl, &bd, &tl, &td,
318 s->hufts, z);
319 if (t != Z_OK)
320 {
321 if (t == (uInt)Z_DATA_ERROR)
322 {
323 ZFREE(z, s->sub.trees.blens);
324 s->mode = BAD;
325 }
326 r = t;
327 LEAVE
328 }
329 Tracev((stderr, "inflate: trees ok\n"));
330 if ((c = inflate_codes_new(bl, bd, tl, td, z)) == Z_NULL)
331 {
332 r = Z_MEM_ERROR;
333 LEAVE
334 }
335 s->sub.decode.codes = c;
336 }
337 ZFREE(z, s->sub.trees.blens);
338 s->mode = CODES;
339 case CODES:
340 UPDATE
341 if ((r = inflate_codes(s, z, r)) != Z_STREAM_END)
342 return inflate_flush(s, z, r);
343 r = Z_OK;
344 inflate_codes_free(s->sub.decode.codes, z);
345 LOAD
346 Tracev((stderr, "inflate: codes end, %lu total out\n",
347 z->total_out + (q >= s->read ? q - s->read :
348 (s->end - s->read) + (q - s->window))));
349 if (!s->last)
350 {
351 s->mode = TYPE;
352 break;
353 }
354 s->mode = DRY;
355 case DRY:
356 FLUSH
357 if (s->read != s->write)
358 LEAVE
359 s->mode = DONE;
360 case DONE:
361 r = Z_STREAM_END;
362 LEAVE
363 case BAD:
364 r = Z_DATA_ERROR;
365 LEAVE
366 default:
367 r = Z_STREAM_ERROR;
368 LEAVE
369 }
370 }
371
372
373 int inflate_blocks_free(s, z)
374 inflate_blocks_statef *s;
375 z_streamp z;
376 {
377 inflate_blocks_reset(s, z, Z_NULL);
378 ZFREE(z, s->window);
379 ZFREE(z, s->hufts);
380 ZFREE(z, s);
381 Tracev((stderr, "inflate: blocks freed\n"));
382 return Z_OK;
383 }
Cache object: ac51a9000296dfe6671aec4879fafaea
|