|
1 /* infblock.c -- interpret and process block types to last block |
|
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 "infblock.h" |
|
8 #include "inftrees.h" |
|
9 #include "infcodes.h" |
|
10 #include "infutil.h" |
|
11 |
|
12 struct inflate_codes_state {int dummy;}; /* for buggy compilers */ |
|
13 |
|
14 /* simplify the use of the inflate_huft type with some defines */ |
|
15 #define exop word.what.Exop |
|
16 #define bits word.what.Bits |
|
17 |
|
18 /* Table for deflate from PKZIP's appnote.txt. */ |
|
19 local const uInt border[] = { /* Order of the bit length code lengths */ |
|
20 16, 17, 18, 0, 8, 7, 9, 6, 10, 5, 11, 4, 12, 3, 13, 2, 14, 1, 15}; |
|
21 |
|
22 /* |
|
23 Notes beyond the 1.93a appnote.txt: |
|
24 |
|
25 1. Distance pointers never point before the beginning of the output |
|
26 stream. |
|
27 2. Distance pointers can point back across blocks, up to 32k away. |
|
28 3. There is an implied maximum of 7 bits for the bit length table and |
|
29 15 bits for the actual data. |
|
30 4. If only one code exists, then it is encoded using one bit. (Zero |
|
31 would be more efficient, but perhaps a little confusing.) If two |
|
32 codes exist, they are coded using one bit each (0 and 1). |
|
33 5. There is no way of sending zero distance codes--a dummy must be |
|
34 sent if there are none. (History: a pre 2.0 version of PKZIP would |
|
35 store blocks with no distance codes, but this was discovered to be |
|
36 too harsh a criterion.) Valid only for 1.93a. 2.04c does allow |
|
37 zero distance codes, which is sent as one code of zero bits in |
|
38 length. |
|
39 6. There are up to 286 literal/length codes. Code 256 represents the |
|
40 end-of-block. Note however that the static length tree defines |
|
41 288 codes just to fill out the Huffman codes. Codes 286 and 287 |
|
42 cannot be used though, since there is no length base or extra bits |
|
43 defined for them. Similarily, there are up to 30 distance codes. |
|
44 However, static trees define 32 codes (all 5 bits) to fill out the |
|
45 Huffman codes, but the last two had better not show up in the data. |
|
46 7. Unzip can check dynamic Huffman blocks for complete code sets. |
|
47 The exception is that a single code would not be complete (see #4). |
|
48 8. The five bits following the block type is really the number of |
|
49 literal codes sent minus 257. |
|
50 9. Length codes 8,16,16 are interpreted as 13 length codes of 8 bits |
|
51 (1+6+6). Therefore, to output three times the length, you output |
|
52 three codes (1+1+1), whereas to output four times the same length, |
|
53 you only need two codes (1+3). Hmm. |
|
54 10. In the tree reconstruction algorithm, Code = Code + Increment |
|
55 only if BitLength(i) is not zero. (Pretty obvious.) |
|
56 11. Correction: 4 Bits: # of Bit Length codes - 4 (4 - 19) |
|
57 12. Note: length code 284 can represent 227-258, but length code 285 |
|
58 really is 258. The last length deserves its own, short code |
|
59 since it gets used a lot in very redundant files. The length |
|
60 258 is special since 258 - 3 (the min match length) is 255. |
|
61 13. The literal/length and distance code bit lengths are read as a |
|
62 single stream of lengths. It is possible (and advantageous) for |
|
63 a repeat code (16, 17, or 18) to go across the boundary between |
|
64 the two sets of lengths. |
|
65 */ |
|
66 |
|
67 |
|
68 void inflate_blocks_reset( |
|
69 inflate_blocks_statef *s, |
|
70 z_streamp z, |
|
71 uLongf *c) |
|
72 { |
|
73 if (c != Z_NULL) |
|
74 *c = s->check; |
|
75 if (s->mode == BTREE || s->mode == DTREE) |
|
76 ZFREE(z, s->sub.trees.blens); |
|
77 if (s->mode == CODES) |
|
78 inflate_codes_free(s->sub.decode.codes, z); |
|
79 s->mode = TYPE; |
|
80 s->bitk = 0; |
|
81 s->bitb = 0; |
|
82 s->read = s->write = s->window; |
|
83 if (s->checkfn != Z_NULL) |
|
84 z->adler = s->check = (*s->checkfn)(0L, (const Bytef *)Z_NULL, 0); |
|
85 Tracev((stderr, "inflate: blocks reset\n")); |
|
86 } |
|
87 |
|
88 |
|
89 inflate_blocks_statef *inflate_blocks_new( |
|
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 s->checkfn = c; |
|
113 s->mode = TYPE; |
|
114 Tracev((stderr, "inflate: blocks allocated\n")); |
|
115 inflate_blocks_reset(s, z, Z_NULL); |
|
116 return s; |
|
117 } |
|
118 |
|
119 |
|
120 int inflate_blocks( |
|
121 inflate_blocks_statef *s, |
|
122 z_streamp z, |
|
123 int r) |
|
124 { |
|
125 uInt t; /* temporary storage */ |
|
126 uLong b; /* bit buffer */ |
|
127 uInt k; /* bits in bit buffer */ |
|
128 Bytef *p; /* input data pointer */ |
|
129 uInt n; /* bytes available there */ |
|
130 Bytef *q; /* output window write pointer */ |
|
131 uInt m; /* bytes to end of window or read pointer */ |
|
132 |
|
133 /* copy input/output information to locals (UPDATE macro restores) */ |
|
134 LOAD |
|
135 |
|
136 /* process input based on current state */ |
|
137 for (;;) switch (s->mode) |
|
138 { |
|
139 case TYPE: |
|
140 NEEDBITS(3) |
|
141 t = (uInt)b & 7; |
|
142 s->last = t & 1; |
|
143 switch (t >> 1) |
|
144 { |
|
145 case 0: /* stored */ |
|
146 Tracev((stderr, "inflate: stored block%s\n", |
|
147 s->last ? " (last)" : "")); |
|
148 DUMPBITS(3) |
|
149 t = k & 7; /* go to byte boundary */ |
|
150 DUMPBITS(t) |
|
151 s->mode = LENS; /* get length of stored block */ |
|
152 break; |
|
153 case 1: /* fixed */ |
|
154 Tracev((stderr, "inflate: fixed codes block%s\n", |
|
155 s->last ? " (last)" : "")); |
|
156 { |
|
157 uInt bl, bd; |
|
158 const inflate_huft *tl, *td; |
|
159 |
|
160 inflate_trees_fixed(&bl, &bd, &tl, &td, z); |
|
161 s->sub.decode.codes = inflate_codes_new(bl, bd, tl, td, z); |
|
162 if (s->sub.decode.codes == Z_NULL) |
|
163 { |
|
164 r = Z_MEM_ERROR; |
|
165 LEAVE |
|
166 } |
|
167 } |
|
168 DUMPBITS(3) |
|
169 s->mode = CODES; |
|
170 break; |
|
171 case 2: /* dynamic */ |
|
172 Tracev((stderr, "inflate: dynamic codes block%s\n", |
|
173 s->last ? " (last)" : "")); |
|
174 DUMPBITS(3) |
|
175 s->mode = TABLE; |
|
176 break; |
|
177 case 3: /* illegal */ |
|
178 DUMPBITS(3) |
|
179 s->mode = BAD; |
|
180 z->msg = (char*)"invalid block type"; |
|
181 r = Z_DATA_ERROR; |
|
182 LEAVE |
|
183 } |
|
184 break; |
|
185 case LENS: |
|
186 NEEDBITS(32) |
|
187 if ((((~b) >> 16) & 0xffff) != (b & 0xffff)) |
|
188 { |
|
189 s->mode = BAD; |
|
190 z->msg = (char*)"invalid stored block lengths"; |
|
191 r = Z_DATA_ERROR; |
|
192 LEAVE |
|
193 } |
|
194 s->sub.left = (uInt)b & 0xffff; |
|
195 b = k = 0; /* dump bits */ |
|
196 Tracev((stderr, "inflate: stored length %u\n", s->sub.left)); |
|
197 s->mode = s->sub.left ? STORED : (s->last ? DRY : TYPE); |
|
198 break; |
|
199 case STORED: |
|
200 if (n == 0) |
|
201 LEAVE |
|
202 NEEDOUT |
|
203 t = s->sub.left; |
|
204 if (t > n) t = n; |
|
205 if (t > m) t = m; |
|
206 zmemcpy(q, p, t); |
|
207 p += t; n -= t; |
|
208 q += t; m -= t; |
|
209 if ((s->sub.left -= t) != 0) |
|
210 break; |
|
211 Tracev((stderr, "inflate: stored end, %lu total out\n", |
|
212 z->total_out + (q >= s->read ? q - s->read : |
|
213 (s->end - s->read) + (q - s->window)))); |
|
214 s->mode = s->last ? DRY : TYPE; |
|
215 break; |
|
216 case TABLE: |
|
217 NEEDBITS(14) |
|
218 s->sub.trees.table = t = (uInt)b & 0x3fff; |
|
219 #ifndef PKZIP_BUG_WORKAROUND |
|
220 if ((t & 0x1f) > 29 || ((t >> 5) & 0x1f) > 29) |
|
221 { |
|
222 s->mode = BAD; |
|
223 z->msg = (char*)"too many length or distance symbols"; |
|
224 r = Z_DATA_ERROR; |
|
225 LEAVE |
|
226 } |
|
227 #endif |
|
228 t = 258 + (t & 0x1f) + ((t >> 5) & 0x1f); |
|
229 if ((s->sub.trees.blens = (uIntf*)ZALLOC(z, t, sizeof(uInt))) == Z_NULL) |
|
230 { |
|
231 r = Z_MEM_ERROR; |
|
232 LEAVE |
|
233 } |
|
234 DUMPBITS(14) |
|
235 s->sub.trees.index = 0; |
|
236 Tracev((stderr, "inflate: table sizes ok\n")); |
|
237 s->mode = BTREE; |
|
238 case BTREE: |
|
239 while (s->sub.trees.index < 4 + (s->sub.trees.table >> 10)) |
|
240 { |
|
241 NEEDBITS(3) |
|
242 s->sub.trees.blens[border[s->sub.trees.index++]] = (uInt)b & 7; |
|
243 DUMPBITS(3) |
|
244 } |
|
245 while (s->sub.trees.index < 19) |
|
246 s->sub.trees.blens[border[s->sub.trees.index++]] = 0; |
|
247 s->sub.trees.bb = 7; |
|
248 t = inflate_trees_bits(s->sub.trees.blens, &s->sub.trees.bb, |
|
249 &s->sub.trees.tb, s->hufts, z); |
|
250 if (t != Z_OK) |
|
251 { |
|
252 r = t; |
|
253 if (r == Z_DATA_ERROR) |
|
254 { |
|
255 ZFREE(z, s->sub.trees.blens); |
|
256 s->mode = BAD; |
|
257 } |
|
258 LEAVE |
|
259 } |
|
260 s->sub.trees.index = 0; |
|
261 Tracev((stderr, "inflate: bits tree ok\n")); |
|
262 s->mode = DTREE; |
|
263 case DTREE: |
|
264 while (t = s->sub.trees.table, |
|
265 s->sub.trees.index < 258 + (t & 0x1f) + ((t >> 5) & 0x1f)) |
|
266 { |
|
267 inflate_huft *h; |
|
268 uInt i, j, c; |
|
269 |
|
270 t = s->sub.trees.bb; |
|
271 NEEDBITS(t) |
|
272 h = s->sub.trees.tb + ((uInt)b & inflate_mask[t]); |
|
273 t = h->bits; |
|
274 c = h->base; |
|
275 if (c < 16) |
|
276 { |
|
277 DUMPBITS(t) |
|
278 s->sub.trees.blens[s->sub.trees.index++] = c; |
|
279 } |
|
280 else /* c == 16..18 */ |
|
281 { |
|
282 i = c == 18 ? 7 : c - 14; |
|
283 j = c == 18 ? 11 : 3; |
|
284 NEEDBITS(t + i) |
|
285 DUMPBITS(t) |
|
286 j += (uInt)b & inflate_mask[i]; |
|
287 DUMPBITS(i) |
|
288 i = s->sub.trees.index; |
|
289 t = s->sub.trees.table; |
|
290 if (i + j > 258 + (t & 0x1f) + ((t >> 5) & 0x1f) || |
|
291 (c == 16 && i < 1)) |
|
292 { |
|
293 ZFREE(z, s->sub.trees.blens); |
|
294 s->mode = BAD; |
|
295 z->msg = (char*)"invalid bit length repeat"; |
|
296 r = Z_DATA_ERROR; |
|
297 LEAVE |
|
298 } |
|
299 c = c == 16 ? s->sub.trees.blens[i - 1] : 0; |
|
300 do { |
|
301 s->sub.trees.blens[i++] = c; |
|
302 } while (--j); |
|
303 s->sub.trees.index = i; |
|
304 } |
|
305 } |
|
306 s->sub.trees.tb = Z_NULL; |
|
307 { |
|
308 uInt bl, bd; |
|
309 inflate_huft *tl, *td; |
|
310 inflate_codes_statef *c; |
|
311 |
|
312 bl = 9; /* must be <= 9 for lookahead assumptions */ |
|
313 bd = 6; /* must be <= 9 for lookahead assumptions */ |
|
314 t = s->sub.trees.table; |
|
315 t = inflate_trees_dynamic(257 + (t & 0x1f), 1 + ((t >> 5) & 0x1f), |
|
316 s->sub.trees.blens, &bl, &bd, &tl, &td, |
|
317 s->hufts, z); |
|
318 |
|
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( |
|
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 } |
|
384 |
|
385 |
|
386 void inflate_set_dictionary( |
|
387 inflate_blocks_statef *s, |
|
388 const Bytef *d, |
|
389 uInt n) |
|
390 { |
|
391 zmemcpy(s->window, d, n); |
|
392 s->read = s->write = s->window + n; |
|
393 } |
|
394 |
|
395 |
|
396 /* Returns true if inflate is currently at the end of a block generated |
|
397 * by Z_SYNC_FLUSH or Z_FULL_FLUSH. |
|
398 * IN assertion: s != Z_NULL |
|
399 */ |
|
400 int inflate_blocks_sync_point( |
|
401 inflate_blocks_statef *s) |
|
402 { |
|
403 return s->mode == LENS; |
|
404 } |