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