Mercurial > ~darius > hgwebdir.cgi > paradise_client

comparison zlib/infblock.c @ 3:5a977ccbc7a9 default tip

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
Empty changelog
author darius
date Sat, 06 Dec 1997 05:41:29 +0000
parents
children
comparison
equal deleted inserted replaced
2:fba0b6e6cdc7 3:5a977ccbc7a9
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 }