Mercurial > ~darius > hgwebdir.cgi > paradise_server

comparison zlib/infblock.c @ 10:1040ca591f2e

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
First entry of Paradise Server 2.9 patch 10 Beta
author darius
date Sat, 06 Dec 1997 04:37:18 +0000
parents
children
comparison
equal deleted inserted replaced
9:331055a97a9d 10:1040ca591f2e
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 inflate_blocks_statef *s;
66 z_stream *z;
67 uLongf *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 {
75 inflate_codes_free(s->sub.decode.codes, z);
76 inflate_trees_free(s->sub.decode.td, z);
77 inflate_trees_free(s->sub.decode.tl, z);
78 }
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 s->check = (*s->checkfn)(0L, Z_NULL, 0);
85 Trace((stderr, "inflate: blocks reset\n"));
86 }
87
88
89 inflate_blocks_statef *inflate_blocks_new(z, c, w)
90 z_stream *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->window = (Bytef *)ZALLOC(z, 1, w)) == Z_NULL)
100 {
101 ZFREE(z, s);
102 return Z_NULL;
103 }
104 s->end = s->window + w;
105 s->checkfn = c;
106 s->mode = TYPE;
107 Trace((stderr, "inflate: blocks allocated\n"));
108 inflate_blocks_reset(s, z, &s->check);
109 return s;
110 }
111
112
113 int inflate_blocks(s, z, r)
114 inflate_blocks_statef *s;
115 z_stream *z;
116 int r;
117 {
118 uInt t; /* temporary storage */
119 uLong b; /* bit buffer */
120 uInt k; /* bits in bit buffer */
121 Bytef *p; /* input data pointer */
122 uInt n; /* bytes available there */
123 Bytef *q; /* output window write pointer */
124 uInt m; /* bytes to end of window or read pointer */
125
126 /* copy input/output information to locals (UPDATE macro restores) */
127 LOAD
128
129 /* process input based on current state */
130 while (1) switch (s->mode)
131 {
132 case TYPE:
133 NEEDBITS(3)
134 t = (uInt)b & 7;
135 s->last = t & 1;
136 switch (t >> 1)
137 {
138 case 0: /* stored */
139 Trace((stderr, "inflate: stored block%s\n",
140 s->last ? " (last)" : ""));
141 DUMPBITS(3)
142 t = k & 7; /* go to byte boundary */
143 DUMPBITS(t)
144 s->mode = LENS; /* get length of stored block */
145 break;
146 case 1: /* fixed */
147 Trace((stderr, "inflate: fixed codes block%s\n",
148 s->last ? " (last)" : ""));
149 {
150 uInt bl, bd;
151 inflate_huft *tl, *td;
152
153 inflate_trees_fixed(&bl, &bd, &tl, &td);
154 s->sub.decode.codes = inflate_codes_new(bl, bd, tl, td, z);
155 if (s->sub.decode.codes == Z_NULL)
156 {
157 r = Z_MEM_ERROR;
158 LEAVE
159 }
160 s->sub.decode.tl = Z_NULL; /* don't try to free these */
161 s->sub.decode.td = Z_NULL;
162 }
163 DUMPBITS(3)
164 s->mode = CODES;
165 break;
166 case 2: /* dynamic */
167 Trace((stderr, "inflate: dynamic codes block%s\n",
168 s->last ? " (last)" : ""));
169 DUMPBITS(3)
170 s->mode = TABLE;
171 break;
172 case 3: /* illegal */
173 DUMPBITS(3)
174 s->mode = BAD;
175 z->msg = "invalid block type";
176 r = Z_DATA_ERROR;
177 LEAVE
178 }
179 break;
180 case LENS:
181 NEEDBITS(32)
182 if (((~b) >> 16) != (b & 0xffff))
183 {
184 s->mode = BAD;
185 z->msg = "invalid stored block lengths";
186 r = Z_DATA_ERROR;
187 LEAVE
188 }
189 s->sub.left = (uInt)b & 0xffff;
190 b = k = 0; /* dump bits */
191 Tracev((stderr, "inflate: stored length %u\n", s->sub.left));
192 s->mode = s->sub.left ? STORED : TYPE;
193 break;
194 case STORED:
195 if (n == 0)
196 LEAVE
197 NEEDOUT
198 t = s->sub.left;
199 if (t > n) t = n;
200 if (t > m) t = m;
201 zmemcpy(q, p, t);
202 p += t; n -= t;
203 q += t; m -= t;
204 if ((s->sub.left -= t) != 0)
205 break;
206 Tracev((stderr, "inflate: stored end, %lu total out\n",
207 z->total_out + (q >= s->read ? q - s->read :
208 (s->end - s->read) + (q - s->window))));
209 s->mode = s->last ? DRY : TYPE;
210 break;
211 case TABLE:
212 NEEDBITS(14)
213 s->sub.trees.table = t = (uInt)b & 0x3fff;
214 #ifndef PKZIP_BUG_WORKAROUND
215 if ((t & 0x1f) > 29 || ((t >> 5) & 0x1f) > 29)
216 {
217 s->mode = BAD;
218 z->msg = "too many length or distance symbols";
219 r = Z_DATA_ERROR;
220 LEAVE
221 }
222 #endif
223 t = 258 + (t & 0x1f) + ((t >> 5) & 0x1f);
224 if (t < 19)
225 t = 19;
226 if ((s->sub.trees.blens = (uIntf*)ZALLOC(z, t, sizeof(uInt))) == Z_NULL)
227 {
228 r = Z_MEM_ERROR;
229 LEAVE
230 }
231 DUMPBITS(14)
232 s->sub.trees.index = 0;
233 Tracev((stderr, "inflate: table sizes ok\n"));
234 s->mode = BTREE;
235 case BTREE:
236 while (s->sub.trees.index < 4 + (s->sub.trees.table >> 10))
237 {
238 NEEDBITS(3)
239 s->sub.trees.blens[border[s->sub.trees.index++]] = (uInt)b & 7;
240 DUMPBITS(3)
241 }
242 while (s->sub.trees.index < 19)
243 s->sub.trees.blens[border[s->sub.trees.index++]] = 0;
244 s->sub.trees.bb = 7;
245 t = inflate_trees_bits(s->sub.trees.blens, &s->sub.trees.bb,
246 &s->sub.trees.tb, z);
247 if (t != Z_OK)
248 {
249 r = t;
250 if (r == Z_DATA_ERROR)
251 s->mode = BAD;
252 LEAVE
253 }
254 s->sub.trees.index = 0;
255 Tracev((stderr, "inflate: bits tree ok\n"));
256 s->mode = DTREE;
257 case DTREE:
258 while (t = s->sub.trees.table,
259 s->sub.trees.index < 258 + (t & 0x1f) + ((t >> 5) & 0x1f))
260 {
261 inflate_huft *h;
262 uInt i, j, c;
263
264 t = s->sub.trees.bb;
265 NEEDBITS(t)
266 h = s->sub.trees.tb + ((uInt)b & inflate_mask[t]);
267 t = h->word.what.Bits;
268 c = h->more.Base;
269 if (c < 16)
270 {
271 DUMPBITS(t)
272 s->sub.trees.blens[s->sub.trees.index++] = c;
273 }
274 else /* c == 16..18 */
275 {
276 i = c == 18 ? 7 : c - 14;
277 j = c == 18 ? 11 : 3;
278 NEEDBITS(t + i)
279 DUMPBITS(t)
280 j += (uInt)b & inflate_mask[i];
281 DUMPBITS(i)
282 i = s->sub.trees.index;
283 t = s->sub.trees.table;
284 if (i + j > 258 + (t & 0x1f) + ((t >> 5) & 0x1f) ||
285 (c == 16 && i < 1))
286 {
287 s->mode = BAD;
288 z->msg = "invalid bit length repeat";
289 r = Z_DATA_ERROR;
290 LEAVE
291 }
292 c = c == 16 ? s->sub.trees.blens[i - 1] : 0;
293 do {
294 s->sub.trees.blens[i++] = c;
295 } while (--j);
296 s->sub.trees.index = i;
297 }
298 }
299 inflate_trees_free(s->sub.trees.tb, z);
300 s->sub.trees.tb = Z_NULL;
301 {
302 uInt bl, bd;
303 inflate_huft *tl, *td;
304 inflate_codes_statef *c;
305
306 bl = 9; /* must be <= 9 for lookahead assumptions */
307 bd = 6; /* must be <= 9 for lookahead assumptions */
308 t = s->sub.trees.table;
309 t = inflate_trees_dynamic(257 + (t & 0x1f), 1 + ((t >> 5) & 0x1f),
310 s->sub.trees.blens, &bl, &bd, &tl, &td, z);
311 if (t != Z_OK)
312 {
313 if (t == (uInt)Z_DATA_ERROR)
314 s->mode = BAD;
315 r = t;
316 LEAVE
317 }
318 Tracev((stderr, "inflate: trees ok\n"));
319 if ((c = inflate_codes_new(bl, bd, tl, td, z)) == Z_NULL)
320 {
321 inflate_trees_free(td, z);
322 inflate_trees_free(tl, z);
323 r = Z_MEM_ERROR;
324 LEAVE
325 }
326 ZFREE(z, s->sub.trees.blens);
327 s->sub.decode.codes = c;
328 s->sub.decode.tl = tl;
329 s->sub.decode.td = td;
330 }
331 s->mode = CODES;
332 case CODES:
333 UPDATE
334 if ((r = inflate_codes(s, z, r)) != Z_STREAM_END)
335 return inflate_flush(s, z, r);
336 r = Z_OK;
337 inflate_codes_free(s->sub.decode.codes, z);
338 inflate_trees_free(s->sub.decode.td, z);
339 inflate_trees_free(s->sub.decode.tl, z);
340 LOAD
341 Tracev((stderr, "inflate: codes end, %lu total out\n",
342 z->total_out + (q >= s->read ? q - s->read :
343 (s->end - s->read) + (q - s->window))));
344 if (!s->last)
345 {
346 s->mode = TYPE;
347 break;
348 }
349 if (k > 7) /* return unused byte, if any */
350 {
351 Assert(k < 16, "inflate_codes grabbed too many bytes")
352 k -= 8;
353 n++;
354 p--; /* can always return one */
355 }
356 s->mode = DRY;
357 case DRY:
358 FLUSH
359 if (s->read != s->write)
360 LEAVE
361 s->mode = DONE;
362 case DONE:
363 r = Z_STREAM_END;
364 LEAVE
365 case BAD:
366 r = Z_DATA_ERROR;
367 LEAVE
368 default:
369 r = Z_STREAM_ERROR;
370 LEAVE
371 }
372 }
373
374
375 int inflate_blocks_free(s, z, c)
376 inflate_blocks_statef *s;
377 z_stream *z;
378 uLongf *c;
379 {
380 inflate_blocks_reset(s, z, c);
381 ZFREE(z, s->window);
382 ZFREE(z, s);
383 Trace((stderr, "inflate: blocks freed\n"));
384 return Z_OK;
385 }