Commit | Line | Data |
---|---|---|
1da177e4 LT |
1 | /* infblock.c -- interpret and process block types to last block |
2 | * Copyright (C) 1995-1998 Mark Adler | |
3 | * For conditions of distribution and use, see copyright notice in zlib.h | |
4 | */ | |
5 | ||
6 | #include <linux/zutil.h> | |
7 | #include "infblock.h" | |
8 | #include "inftrees.h" | |
9 | #include "infcodes.h" | |
10 | #include "infutil.h" | |
11 | ||
12 | struct inflate_codes_state; | |
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 | static 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 zlib_inflate_blocks_reset( | |
69 | inflate_blocks_statef *s, | |
70 | z_streamp z, | |
71 | uLong *c | |
72 | ) | |
73 | { | |
74 | if (c != NULL) | |
75 | *c = s->check; | |
76 | if (s->mode == CODES) | |
77 | zlib_inflate_codes_free(s->sub.decode.codes, z); | |
78 | s->mode = TYPE; | |
79 | s->bitk = 0; | |
80 | s->bitb = 0; | |
81 | s->read = s->write = s->window; | |
82 | if (s->checkfn != NULL) | |
83 | z->adler = s->check = (*s->checkfn)(0L, NULL, 0); | |
84 | } | |
85 | ||
86 | inflate_blocks_statef *zlib_inflate_blocks_new( | |
87 | z_streamp z, | |
88 | check_func c, | |
89 | uInt w | |
90 | ) | |
91 | { | |
92 | inflate_blocks_statef *s; | |
93 | ||
94 | s = &WS(z)->working_blocks_state; | |
95 | s->hufts = WS(z)->working_hufts; | |
96 | s->window = WS(z)->working_window; | |
97 | s->end = s->window + w; | |
98 | s->checkfn = c; | |
99 | s->mode = TYPE; | |
100 | zlib_inflate_blocks_reset(s, z, NULL); | |
101 | return s; | |
102 | } | |
103 | ||
104 | ||
105 | int zlib_inflate_blocks( | |
106 | inflate_blocks_statef *s, | |
107 | z_streamp z, | |
108 | int r | |
109 | ) | |
110 | { | |
111 | uInt t; /* temporary storage */ | |
112 | uLong b; /* bit buffer */ | |
113 | uInt k; /* bits in bit buffer */ | |
114 | Byte *p; /* input data pointer */ | |
115 | uInt n; /* bytes available there */ | |
116 | Byte *q; /* output window write pointer */ | |
117 | uInt m; /* bytes to end of window or read pointer */ | |
118 | ||
119 | /* copy input/output information to locals (UPDATE macro restores) */ | |
120 | LOAD | |
121 | ||
122 | /* process input based on current state */ | |
123 | while (1) switch (s->mode) | |
124 | { | |
125 | case TYPE: | |
126 | NEEDBITS(3) | |
127 | t = (uInt)b & 7; | |
128 | s->last = t & 1; | |
129 | switch (t >> 1) | |
130 | { | |
131 | case 0: /* stored */ | |
132 | DUMPBITS(3) | |
133 | t = k & 7; /* go to byte boundary */ | |
134 | DUMPBITS(t) | |
135 | s->mode = LENS; /* get length of stored block */ | |
136 | break; | |
137 | case 1: /* fixed */ | |
138 | { | |
139 | uInt bl, bd; | |
140 | inflate_huft *tl, *td; | |
141 | ||
142 | zlib_inflate_trees_fixed(&bl, &bd, &tl, &td, s->hufts, z); | |
143 | s->sub.decode.codes = zlib_inflate_codes_new(bl, bd, tl, td, z); | |
144 | if (s->sub.decode.codes == NULL) | |
145 | { | |
146 | r = Z_MEM_ERROR; | |
147 | LEAVE | |
148 | } | |
149 | } | |
150 | DUMPBITS(3) | |
151 | s->mode = CODES; | |
152 | break; | |
153 | case 2: /* dynamic */ | |
154 | DUMPBITS(3) | |
155 | s->mode = TABLE; | |
156 | break; | |
157 | case 3: /* illegal */ | |
158 | DUMPBITS(3) | |
159 | s->mode = B_BAD; | |
160 | z->msg = (char*)"invalid block type"; | |
161 | r = Z_DATA_ERROR; | |
162 | LEAVE | |
163 | } | |
164 | break; | |
165 | case LENS: | |
166 | NEEDBITS(32) | |
167 | if ((((~b) >> 16) & 0xffff) != (b & 0xffff)) | |
168 | { | |
169 | s->mode = B_BAD; | |
170 | z->msg = (char*)"invalid stored block lengths"; | |
171 | r = Z_DATA_ERROR; | |
172 | LEAVE | |
173 | } | |
174 | s->sub.left = (uInt)b & 0xffff; | |
175 | b = k = 0; /* dump bits */ | |
176 | s->mode = s->sub.left ? STORED : (s->last ? DRY : TYPE); | |
177 | break; | |
178 | case STORED: | |
179 | if (n == 0) | |
180 | LEAVE | |
181 | NEEDOUT | |
182 | t = s->sub.left; | |
183 | if (t > n) t = n; | |
184 | if (t > m) t = m; | |
185 | memcpy(q, p, t); | |
186 | p += t; n -= t; | |
187 | q += t; m -= t; | |
188 | if ((s->sub.left -= t) != 0) | |
189 | break; | |
190 | s->mode = s->last ? DRY : TYPE; | |
191 | break; | |
192 | case TABLE: | |
193 | NEEDBITS(14) | |
194 | s->sub.trees.table = t = (uInt)b & 0x3fff; | |
195 | #ifndef PKZIP_BUG_WORKAROUND | |
196 | if ((t & 0x1f) > 29 || ((t >> 5) & 0x1f) > 29) | |
197 | { | |
198 | s->mode = B_BAD; | |
199 | z->msg = (char*)"too many length or distance symbols"; | |
200 | r = Z_DATA_ERROR; | |
201 | LEAVE | |
202 | } | |
203 | #endif | |
204 | { | |
205 | s->sub.trees.blens = WS(z)->working_blens; | |
206 | } | |
207 | DUMPBITS(14) | |
208 | s->sub.trees.index = 0; | |
209 | s->mode = BTREE; | |
210 | case BTREE: | |
211 | while (s->sub.trees.index < 4 + (s->sub.trees.table >> 10)) | |
212 | { | |
213 | NEEDBITS(3) | |
214 | s->sub.trees.blens[border[s->sub.trees.index++]] = (uInt)b & 7; | |
215 | DUMPBITS(3) | |
216 | } | |
217 | while (s->sub.trees.index < 19) | |
218 | s->sub.trees.blens[border[s->sub.trees.index++]] = 0; | |
219 | s->sub.trees.bb = 7; | |
220 | t = zlib_inflate_trees_bits(s->sub.trees.blens, &s->sub.trees.bb, | |
221 | &s->sub.trees.tb, s->hufts, z); | |
222 | if (t != Z_OK) | |
223 | { | |
224 | r = t; | |
225 | if (r == Z_DATA_ERROR) | |
226 | s->mode = B_BAD; | |
227 | LEAVE | |
228 | } | |
229 | s->sub.trees.index = 0; | |
230 | s->mode = DTREE; | |
231 | case DTREE: | |
232 | while (t = s->sub.trees.table, | |
233 | s->sub.trees.index < 258 + (t & 0x1f) + ((t >> 5) & 0x1f)) | |
234 | { | |
235 | inflate_huft *h; | |
236 | uInt i, j, c; | |
237 | ||
238 | t = s->sub.trees.bb; | |
239 | NEEDBITS(t) | |
240 | h = s->sub.trees.tb + ((uInt)b & zlib_inflate_mask[t]); | |
241 | t = h->bits; | |
242 | c = h->base; | |
243 | if (c < 16) | |
244 | { | |
245 | DUMPBITS(t) | |
246 | s->sub.trees.blens[s->sub.trees.index++] = c; | |
247 | } | |
248 | else /* c == 16..18 */ | |
249 | { | |
250 | i = c == 18 ? 7 : c - 14; | |
251 | j = c == 18 ? 11 : 3; | |
252 | NEEDBITS(t + i) | |
253 | DUMPBITS(t) | |
254 | j += (uInt)b & zlib_inflate_mask[i]; | |
255 | DUMPBITS(i) | |
256 | i = s->sub.trees.index; | |
257 | t = s->sub.trees.table; | |
258 | if (i + j > 258 + (t & 0x1f) + ((t >> 5) & 0x1f) || | |
259 | (c == 16 && i < 1)) | |
260 | { | |
261 | s->mode = B_BAD; | |
262 | z->msg = (char*)"invalid bit length repeat"; | |
263 | r = Z_DATA_ERROR; | |
264 | LEAVE | |
265 | } | |
266 | c = c == 16 ? s->sub.trees.blens[i - 1] : 0; | |
267 | do { | |
268 | s->sub.trees.blens[i++] = c; | |
269 | } while (--j); | |
270 | s->sub.trees.index = i; | |
271 | } | |
272 | } | |
273 | s->sub.trees.tb = NULL; | |
274 | { | |
275 | uInt bl, bd; | |
276 | inflate_huft *tl, *td; | |
277 | inflate_codes_statef *c; | |
278 | ||
279 | bl = 9; /* must be <= 9 for lookahead assumptions */ | |
280 | bd = 6; /* must be <= 9 for lookahead assumptions */ | |
281 | t = s->sub.trees.table; | |
282 | t = zlib_inflate_trees_dynamic(257 + (t & 0x1f), 1 + ((t >> 5) & 0x1f), | |
283 | s->sub.trees.blens, &bl, &bd, &tl, &td, | |
284 | s->hufts, z); | |
285 | if (t != Z_OK) | |
286 | { | |
287 | if (t == (uInt)Z_DATA_ERROR) | |
288 | s->mode = B_BAD; | |
289 | r = t; | |
290 | LEAVE | |
291 | } | |
292 | if ((c = zlib_inflate_codes_new(bl, bd, tl, td, z)) == NULL) | |
293 | { | |
294 | r = Z_MEM_ERROR; | |
295 | LEAVE | |
296 | } | |
297 | s->sub.decode.codes = c; | |
298 | } | |
299 | s->mode = CODES; | |
300 | case CODES: | |
301 | UPDATE | |
302 | if ((r = zlib_inflate_codes(s, z, r)) != Z_STREAM_END) | |
303 | return zlib_inflate_flush(s, z, r); | |
304 | r = Z_OK; | |
305 | zlib_inflate_codes_free(s->sub.decode.codes, z); | |
306 | LOAD | |
307 | if (!s->last) | |
308 | { | |
309 | s->mode = TYPE; | |
310 | break; | |
311 | } | |
312 | s->mode = DRY; | |
313 | case DRY: | |
314 | FLUSH | |
315 | if (s->read != s->write) | |
316 | LEAVE | |
317 | s->mode = B_DONE; | |
318 | case B_DONE: | |
319 | r = Z_STREAM_END; | |
320 | LEAVE | |
321 | case B_BAD: | |
322 | r = Z_DATA_ERROR; | |
323 | LEAVE | |
324 | default: | |
325 | r = Z_STREAM_ERROR; | |
326 | LEAVE | |
327 | } | |
328 | } | |
329 | ||
330 | ||
331 | int zlib_inflate_blocks_free( | |
332 | inflate_blocks_statef *s, | |
333 | z_streamp z | |
334 | ) | |
335 | { | |
336 | zlib_inflate_blocks_reset(s, z, NULL); | |
337 | return Z_OK; | |
338 | } | |
339 | ||
340 | ||
87c2ce3b | 341 | #if 0 |
1da177e4 LT |
342 | void zlib_inflate_set_dictionary( |
343 | inflate_blocks_statef *s, | |
344 | const Byte *d, | |
345 | uInt n | |
346 | ) | |
347 | { | |
348 | memcpy(s->window, d, n); | |
349 | s->read = s->write = s->window + n; | |
350 | } | |
87c2ce3b | 351 | #endif /* 0 */ |
1da177e4 LT |
352 | |
353 | ||
354 | /* Returns true if inflate is currently at the end of a block generated | |
355 | * by Z_SYNC_FLUSH or Z_FULL_FLUSH. | |
356 | * IN assertion: s != NULL | |
357 | */ | |
87c2ce3b | 358 | #if 0 |
1da177e4 LT |
359 | int zlib_inflate_blocks_sync_point( |
360 | inflate_blocks_statef *s | |
361 | ) | |
362 | { | |
363 | return s->mode == LENS; | |
364 | } | |
87c2ce3b | 365 | #endif /* 0 */ |