Commit | Line | Data |
---|---|---|
1da177e4 LT |
1 | /* |
2 | * This file is derived from various .h and .c files from the zlib-0.95 | |
3 | * distribution by Jean-loup Gailly and Mark Adler, with some additions | |
4 | * by Paul Mackerras to aid in implementing Deflate compression and | |
5 | * decompression for PPP packets. See zlib.h for conditions of | |
6 | * distribution and use. | |
7 | * | |
8 | * Changes that have been made include: | |
9 | * - changed functions not used outside this file to "local" | |
10 | * - added minCompression parameter to deflateInit2 | |
11 | * - added Z_PACKET_FLUSH (see zlib.h for details) | |
12 | * - added inflateIncomp | |
13 | * | |
14 | Copyright (C) 1995 Jean-loup Gailly and Mark Adler | |
15 | ||
16 | This software is provided 'as-is', without any express or implied | |
17 | warranty. In no event will the authors be held liable for any damages | |
18 | arising from the use of this software. | |
19 | ||
20 | Permission is granted to anyone to use this software for any purpose, | |
21 | including commercial applications, and to alter it and redistribute it | |
22 | freely, subject to the following restrictions: | |
23 | ||
24 | 1. The origin of this software must not be misrepresented; you must not | |
25 | claim that you wrote the original software. If you use this software | |
26 | in a product, an acknowledgment in the product documentation would be | |
27 | appreciated but is not required. | |
28 | 2. Altered source versions must be plainly marked as such, and must not be | |
29 | misrepresented as being the original software. | |
30 | 3. This notice may not be removed or altered from any source distribution. | |
31 | ||
32 | Jean-loup Gailly Mark Adler | |
33 | gzip@prep.ai.mit.edu madler@alumni.caltech.edu | |
34 | ||
35 | * | |
36 | * | |
37 | */ | |
38 | ||
39 | /*+++++*/ | |
40 | /* zutil.h -- internal interface and configuration of the compression library | |
41 | * Copyright (C) 1995 Jean-loup Gailly. | |
42 | * For conditions of distribution and use, see copyright notice in zlib.h | |
43 | */ | |
44 | ||
45 | /* WARNING: this file should *not* be used by applications. It is | |
46 | part of the implementation of the compression library and is | |
47 | subject to change. Applications should only use zlib.h. | |
48 | */ | |
49 | ||
50 | /* From: zutil.h,v 1.9 1995/05/03 17:27:12 jloup Exp */ | |
51 | ||
52 | #define _Z_UTIL_H | |
53 | ||
54 | #include "zlib.h" | |
55 | ||
56 | #ifndef local | |
57 | # define local static | |
58 | #endif | |
59 | /* compile with -Dlocal if your debugger can't find static symbols */ | |
60 | ||
61 | #define FAR | |
62 | ||
63 | typedef unsigned char uch; | |
64 | typedef uch FAR uchf; | |
65 | typedef unsigned short ush; | |
66 | typedef ush FAR ushf; | |
67 | typedef unsigned long ulg; | |
68 | ||
69 | extern char *z_errmsg[]; /* indexed by 1-zlib_error */ | |
70 | ||
71 | #define ERR_RETURN(strm,err) return (strm->msg=z_errmsg[1-err], err) | |
72 | /* To be used only when the state is known to be valid */ | |
73 | ||
74 | #ifndef NULL | |
75 | #define NULL ((void *) 0) | |
76 | #endif | |
77 | ||
78 | /* common constants */ | |
79 | ||
80 | #define DEFLATED 8 | |
81 | ||
82 | #ifndef DEF_WBITS | |
83 | # define DEF_WBITS MAX_WBITS | |
84 | #endif | |
85 | /* default windowBits for decompression. MAX_WBITS is for compression only */ | |
86 | ||
87 | #if MAX_MEM_LEVEL >= 8 | |
88 | # define DEF_MEM_LEVEL 8 | |
89 | #else | |
90 | # define DEF_MEM_LEVEL MAX_MEM_LEVEL | |
91 | #endif | |
92 | /* default memLevel */ | |
93 | ||
94 | #define STORED_BLOCK 0 | |
95 | #define STATIC_TREES 1 | |
96 | #define DYN_TREES 2 | |
97 | /* The three kinds of block type */ | |
98 | ||
99 | #define MIN_MATCH 3 | |
100 | #define MAX_MATCH 258 | |
101 | /* The minimum and maximum match lengths */ | |
102 | ||
103 | /* functions */ | |
104 | ||
105 | extern void *memcpy(void *, const void *, unsigned long); | |
106 | #define zmemcpy memcpy | |
107 | ||
108 | /* Diagnostic functions */ | |
109 | #ifdef DEBUG_ZLIB | |
decd300b | 110 | # include "stdio.h" |
1da177e4 LT |
111 | # ifndef verbose |
112 | # define verbose 0 | |
113 | # endif | |
114 | # define Assert(cond,msg) {if(!(cond)) z_error(msg);} | |
115 | # define Trace(x) fprintf x | |
116 | # define Tracev(x) {if (verbose) fprintf x ;} | |
117 | # define Tracevv(x) {if (verbose>1) fprintf x ;} | |
118 | # define Tracec(c,x) {if (verbose && (c)) fprintf x ;} | |
119 | # define Tracecv(c,x) {if (verbose>1 && (c)) fprintf x ;} | |
120 | #else | |
121 | # define Assert(cond,msg) | |
122 | # define Trace(x) | |
123 | # define Tracev(x) | |
124 | # define Tracevv(x) | |
125 | # define Tracec(c,x) | |
126 | # define Tracecv(c,x) | |
127 | #endif | |
128 | ||
129 | ||
130 | typedef uLong (*check_func) OF((uLong check, Bytef *buf, uInt len)); | |
131 | ||
132 | /* voidpf zcalloc OF((voidpf opaque, unsigned items, unsigned size)); */ | |
133 | /* void zcfree OF((voidpf opaque, voidpf ptr)); */ | |
134 | ||
135 | #define ZALLOC(strm, items, size) \ | |
136 | (*((strm)->zalloc))((strm)->opaque, (items), (size)) | |
137 | #define ZFREE(strm, addr, size) \ | |
138 | (*((strm)->zfree))((strm)->opaque, (voidpf)(addr), (size)) | |
139 | #define TRY_FREE(s, p, n) {if (p) ZFREE(s, p, n);} | |
140 | ||
141 | /* deflate.h -- internal compression state | |
142 | * Copyright (C) 1995 Jean-loup Gailly | |
143 | * For conditions of distribution and use, see copyright notice in zlib.h | |
144 | */ | |
145 | ||
146 | /* WARNING: this file should *not* be used by applications. It is | |
147 | part of the implementation of the compression library and is | |
148 | subject to change. Applications should only use zlib.h. | |
149 | */ | |
150 | ||
151 | /*+++++*/ | |
152 | /* infblock.h -- header to use infblock.c | |
153 | * Copyright (C) 1995 Mark Adler | |
154 | * For conditions of distribution and use, see copyright notice in zlib.h | |
155 | */ | |
156 | ||
157 | /* WARNING: this file should *not* be used by applications. It is | |
158 | part of the implementation of the compression library and is | |
159 | subject to change. Applications should only use zlib.h. | |
160 | */ | |
161 | ||
162 | struct inflate_blocks_state; | |
163 | typedef struct inflate_blocks_state FAR inflate_blocks_statef; | |
164 | ||
165 | local inflate_blocks_statef * inflate_blocks_new OF(( | |
166 | z_stream *z, | |
167 | check_func c, /* check function */ | |
168 | uInt w)); /* window size */ | |
169 | ||
170 | local int inflate_blocks OF(( | |
171 | inflate_blocks_statef *, | |
172 | z_stream *, | |
173 | int)); /* initial return code */ | |
174 | ||
175 | local void inflate_blocks_reset OF(( | |
176 | inflate_blocks_statef *, | |
177 | z_stream *, | |
178 | uLongf *)); /* check value on output */ | |
179 | ||
180 | local int inflate_blocks_free OF(( | |
181 | inflate_blocks_statef *, | |
182 | z_stream *, | |
183 | uLongf *)); /* check value on output */ | |
184 | ||
185 | local int inflate_addhistory OF(( | |
186 | inflate_blocks_statef *, | |
187 | z_stream *)); | |
188 | ||
189 | local int inflate_packet_flush OF(( | |
190 | inflate_blocks_statef *)); | |
191 | ||
192 | /*+++++*/ | |
193 | /* inftrees.h -- header to use inftrees.c | |
194 | * Copyright (C) 1995 Mark Adler | |
195 | * For conditions of distribution and use, see copyright notice in zlib.h | |
196 | */ | |
197 | ||
198 | /* WARNING: this file should *not* be used by applications. It is | |
199 | part of the implementation of the compression library and is | |
200 | subject to change. Applications should only use zlib.h. | |
201 | */ | |
202 | ||
203 | /* Huffman code lookup table entry--this entry is four bytes for machines | |
204 | that have 16-bit pointers (e.g. PC's in the small or medium model). */ | |
205 | ||
206 | typedef struct inflate_huft_s FAR inflate_huft; | |
207 | ||
208 | struct inflate_huft_s { | |
209 | union { | |
210 | struct { | |
211 | Byte Exop; /* number of extra bits or operation */ | |
212 | Byte Bits; /* number of bits in this code or subcode */ | |
213 | } what; | |
214 | uInt Nalloc; /* number of these allocated here */ | |
215 | Bytef *pad; /* pad structure to a power of 2 (4 bytes for */ | |
216 | } word; /* 16-bit, 8 bytes for 32-bit machines) */ | |
217 | union { | |
218 | uInt Base; /* literal, length base, or distance base */ | |
219 | inflate_huft *Next; /* pointer to next level of table */ | |
220 | } more; | |
221 | }; | |
222 | ||
223 | #ifdef DEBUG_ZLIB | |
224 | local uInt inflate_hufts; | |
225 | #endif | |
226 | ||
227 | local int inflate_trees_bits OF(( | |
228 | uIntf *, /* 19 code lengths */ | |
229 | uIntf *, /* bits tree desired/actual depth */ | |
230 | inflate_huft * FAR *, /* bits tree result */ | |
231 | z_stream *)); /* for zalloc, zfree functions */ | |
232 | ||
233 | local int inflate_trees_dynamic OF(( | |
234 | uInt, /* number of literal/length codes */ | |
235 | uInt, /* number of distance codes */ | |
236 | uIntf *, /* that many (total) code lengths */ | |
237 | uIntf *, /* literal desired/actual bit depth */ | |
238 | uIntf *, /* distance desired/actual bit depth */ | |
239 | inflate_huft * FAR *, /* literal/length tree result */ | |
240 | inflate_huft * FAR *, /* distance tree result */ | |
241 | z_stream *)); /* for zalloc, zfree functions */ | |
242 | ||
243 | local int inflate_trees_fixed OF(( | |
244 | uIntf *, /* literal desired/actual bit depth */ | |
245 | uIntf *, /* distance desired/actual bit depth */ | |
246 | inflate_huft * FAR *, /* literal/length tree result */ | |
247 | inflate_huft * FAR *)); /* distance tree result */ | |
248 | ||
249 | local int inflate_trees_free OF(( | |
250 | inflate_huft *, /* tables to free */ | |
251 | z_stream *)); /* for zfree function */ | |
252 | ||
253 | ||
254 | /*+++++*/ | |
255 | /* infcodes.h -- header to use infcodes.c | |
256 | * Copyright (C) 1995 Mark Adler | |
257 | * For conditions of distribution and use, see copyright notice in zlib.h | |
258 | */ | |
259 | ||
260 | /* WARNING: this file should *not* be used by applications. It is | |
261 | part of the implementation of the compression library and is | |
262 | subject to change. Applications should only use zlib.h. | |
263 | */ | |
264 | ||
265 | struct inflate_codes_state; | |
266 | typedef struct inflate_codes_state FAR inflate_codes_statef; | |
267 | ||
268 | local inflate_codes_statef *inflate_codes_new OF(( | |
269 | uInt, uInt, | |
270 | inflate_huft *, inflate_huft *, | |
271 | z_stream *)); | |
272 | ||
273 | local int inflate_codes OF(( | |
274 | inflate_blocks_statef *, | |
275 | z_stream *, | |
276 | int)); | |
277 | ||
278 | local void inflate_codes_free OF(( | |
279 | inflate_codes_statef *, | |
280 | z_stream *)); | |
281 | ||
282 | ||
283 | /*+++++*/ | |
284 | /* inflate.c -- zlib interface to inflate modules | |
285 | * Copyright (C) 1995 Mark Adler | |
286 | * For conditions of distribution and use, see copyright notice in zlib.h | |
287 | */ | |
288 | ||
289 | /* inflate private state */ | |
290 | struct internal_state { | |
291 | ||
292 | /* mode */ | |
293 | enum { | |
294 | METHOD, /* waiting for method byte */ | |
295 | FLAG, /* waiting for flag byte */ | |
296 | BLOCKS, /* decompressing blocks */ | |
297 | CHECK4, /* four check bytes to go */ | |
298 | CHECK3, /* three check bytes to go */ | |
299 | CHECK2, /* two check bytes to go */ | |
300 | CHECK1, /* one check byte to go */ | |
301 | DONE, /* finished check, done */ | |
302 | BAD} /* got an error--stay here */ | |
303 | mode; /* current inflate mode */ | |
304 | ||
305 | /* mode dependent information */ | |
306 | union { | |
307 | uInt method; /* if FLAGS, method byte */ | |
308 | struct { | |
309 | uLong was; /* computed check value */ | |
310 | uLong need; /* stream check value */ | |
311 | } check; /* if CHECK, check values to compare */ | |
312 | uInt marker; /* if BAD, inflateSync's marker bytes count */ | |
313 | } sub; /* submode */ | |
314 | ||
315 | /* mode independent information */ | |
316 | int nowrap; /* flag for no wrapper */ | |
317 | uInt wbits; /* log2(window size) (8..15, defaults to 15) */ | |
318 | inflate_blocks_statef | |
319 | *blocks; /* current inflate_blocks state */ | |
320 | ||
321 | }; | |
322 | ||
323 | ||
324 | int inflateReset( | |
325 | z_stream *z | |
326 | ) | |
327 | { | |
328 | uLong c; | |
329 | ||
330 | if (z == Z_NULL || z->state == Z_NULL) | |
331 | return Z_STREAM_ERROR; | |
332 | z->total_in = z->total_out = 0; | |
333 | z->msg = Z_NULL; | |
334 | z->state->mode = z->state->nowrap ? BLOCKS : METHOD; | |
335 | inflate_blocks_reset(z->state->blocks, z, &c); | |
336 | Trace((stderr, "inflate: reset\n")); | |
337 | return Z_OK; | |
338 | } | |
339 | ||
340 | ||
341 | int inflateEnd( | |
342 | z_stream *z | |
343 | ) | |
344 | { | |
345 | uLong c; | |
346 | ||
347 | if (z == Z_NULL || z->state == Z_NULL || z->zfree == Z_NULL) | |
348 | return Z_STREAM_ERROR; | |
349 | if (z->state->blocks != Z_NULL) | |
350 | inflate_blocks_free(z->state->blocks, z, &c); | |
351 | ZFREE(z, z->state, sizeof(struct internal_state)); | |
352 | z->state = Z_NULL; | |
353 | Trace((stderr, "inflate: end\n")); | |
354 | return Z_OK; | |
355 | } | |
356 | ||
357 | ||
358 | int inflateInit2( | |
359 | z_stream *z, | |
360 | int w | |
361 | ) | |
362 | { | |
363 | /* initialize state */ | |
364 | if (z == Z_NULL) | |
365 | return Z_STREAM_ERROR; | |
366 | /* if (z->zalloc == Z_NULL) z->zalloc = zcalloc; */ | |
367 | /* if (z->zfree == Z_NULL) z->zfree = zcfree; */ | |
368 | if ((z->state = (struct internal_state FAR *) | |
369 | ZALLOC(z,1,sizeof(struct internal_state))) == Z_NULL) | |
370 | return Z_MEM_ERROR; | |
371 | z->state->blocks = Z_NULL; | |
372 | ||
373 | /* handle undocumented nowrap option (no zlib header or check) */ | |
374 | z->state->nowrap = 0; | |
375 | if (w < 0) | |
376 | { | |
377 | w = - w; | |
378 | z->state->nowrap = 1; | |
379 | } | |
380 | ||
381 | /* set window size */ | |
382 | if (w < 8 || w > 15) | |
383 | { | |
384 | inflateEnd(z); | |
385 | return Z_STREAM_ERROR; | |
386 | } | |
387 | z->state->wbits = (uInt)w; | |
388 | ||
389 | /* create inflate_blocks state */ | |
390 | if ((z->state->blocks = | |
391 | inflate_blocks_new(z, z->state->nowrap ? Z_NULL : adler32, 1 << w)) | |
392 | == Z_NULL) | |
393 | { | |
394 | inflateEnd(z); | |
395 | return Z_MEM_ERROR; | |
396 | } | |
397 | Trace((stderr, "inflate: allocated\n")); | |
398 | ||
399 | /* reset state */ | |
400 | inflateReset(z); | |
401 | return Z_OK; | |
402 | } | |
403 | ||
404 | ||
405 | int inflateInit( | |
406 | z_stream *z | |
407 | ) | |
408 | { | |
409 | return inflateInit2(z, DEF_WBITS); | |
410 | } | |
411 | ||
412 | ||
413 | #define NEEDBYTE {if(z->avail_in==0)goto empty;r=Z_OK;} | |
414 | #define NEXTBYTE (z->avail_in--,z->total_in++,*z->next_in++) | |
415 | ||
416 | int inflate( | |
417 | z_stream *z, | |
418 | int f | |
419 | ) | |
420 | { | |
421 | int r; | |
422 | uInt b; | |
423 | ||
424 | if (z == Z_NULL || z->next_in == Z_NULL) | |
425 | return Z_STREAM_ERROR; | |
426 | r = Z_BUF_ERROR; | |
427 | while (1) switch (z->state->mode) | |
428 | { | |
429 | case METHOD: | |
430 | NEEDBYTE | |
431 | if (((z->state->sub.method = NEXTBYTE) & 0xf) != DEFLATED) | |
432 | { | |
433 | z->state->mode = BAD; | |
434 | z->msg = "unknown compression method"; | |
435 | z->state->sub.marker = 5; /* can't try inflateSync */ | |
436 | break; | |
437 | } | |
438 | if ((z->state->sub.method >> 4) + 8 > z->state->wbits) | |
439 | { | |
440 | z->state->mode = BAD; | |
441 | z->msg = "invalid window size"; | |
442 | z->state->sub.marker = 5; /* can't try inflateSync */ | |
443 | break; | |
444 | } | |
445 | z->state->mode = FLAG; | |
446 | case FLAG: | |
447 | NEEDBYTE | |
448 | if ((b = NEXTBYTE) & 0x20) | |
449 | { | |
450 | z->state->mode = BAD; | |
451 | z->msg = "invalid reserved bit"; | |
452 | z->state->sub.marker = 5; /* can't try inflateSync */ | |
453 | break; | |
454 | } | |
455 | if (((z->state->sub.method << 8) + b) % 31) | |
456 | { | |
457 | z->state->mode = BAD; | |
458 | z->msg = "incorrect header check"; | |
459 | z->state->sub.marker = 5; /* can't try inflateSync */ | |
460 | break; | |
461 | } | |
462 | Trace((stderr, "inflate: zlib header ok\n")); | |
463 | z->state->mode = BLOCKS; | |
464 | case BLOCKS: | |
465 | r = inflate_blocks(z->state->blocks, z, r); | |
466 | if (f == Z_PACKET_FLUSH && z->avail_in == 0 && z->avail_out != 0) | |
467 | r = inflate_packet_flush(z->state->blocks); | |
468 | if (r == Z_DATA_ERROR) | |
469 | { | |
470 | z->state->mode = BAD; | |
471 | z->state->sub.marker = 0; /* can try inflateSync */ | |
472 | break; | |
473 | } | |
474 | if (r != Z_STREAM_END) | |
475 | return r; | |
476 | r = Z_OK; | |
477 | inflate_blocks_reset(z->state->blocks, z, &z->state->sub.check.was); | |
478 | if (z->state->nowrap) | |
479 | { | |
480 | z->state->mode = DONE; | |
481 | break; | |
482 | } | |
483 | z->state->mode = CHECK4; | |
484 | case CHECK4: | |
485 | NEEDBYTE | |
486 | z->state->sub.check.need = (uLong)NEXTBYTE << 24; | |
487 | z->state->mode = CHECK3; | |
488 | case CHECK3: | |
489 | NEEDBYTE | |
490 | z->state->sub.check.need += (uLong)NEXTBYTE << 16; | |
491 | z->state->mode = CHECK2; | |
492 | case CHECK2: | |
493 | NEEDBYTE | |
494 | z->state->sub.check.need += (uLong)NEXTBYTE << 8; | |
495 | z->state->mode = CHECK1; | |
496 | case CHECK1: | |
497 | NEEDBYTE | |
498 | z->state->sub.check.need += (uLong)NEXTBYTE; | |
499 | ||
500 | if (z->state->sub.check.was != z->state->sub.check.need) | |
501 | { | |
502 | z->state->mode = BAD; | |
503 | z->msg = "incorrect data check"; | |
504 | z->state->sub.marker = 5; /* can't try inflateSync */ | |
505 | break; | |
506 | } | |
507 | Trace((stderr, "inflate: zlib check ok\n")); | |
508 | z->state->mode = DONE; | |
509 | case DONE: | |
510 | return Z_STREAM_END; | |
511 | case BAD: | |
512 | return Z_DATA_ERROR; | |
513 | default: | |
514 | return Z_STREAM_ERROR; | |
515 | } | |
516 | ||
517 | empty: | |
518 | if (f != Z_PACKET_FLUSH) | |
519 | return r; | |
520 | z->state->mode = BAD; | |
521 | z->state->sub.marker = 0; /* can try inflateSync */ | |
522 | return Z_DATA_ERROR; | |
523 | } | |
524 | ||
525 | /* | |
526 | * This subroutine adds the data at next_in/avail_in to the output history | |
527 | * without performing any output. The output buffer must be "caught up"; | |
528 | * i.e. no pending output (hence s->read equals s->write), and the state must | |
529 | * be BLOCKS (i.e. we should be willing to see the start of a series of | |
530 | * BLOCKS). On exit, the output will also be caught up, and the checksum | |
531 | * will have been updated if need be. | |
532 | */ | |
533 | ||
534 | int inflateIncomp( | |
535 | z_stream *z | |
536 | ) | |
537 | { | |
538 | if (z->state->mode != BLOCKS) | |
539 | return Z_DATA_ERROR; | |
540 | return inflate_addhistory(z->state->blocks, z); | |
541 | } | |
542 | ||
543 | ||
544 | int inflateSync( | |
545 | z_stream *z | |
546 | ) | |
547 | { | |
548 | uInt n; /* number of bytes to look at */ | |
549 | Bytef *p; /* pointer to bytes */ | |
550 | uInt m; /* number of marker bytes found in a row */ | |
551 | uLong r, w; /* temporaries to save total_in and total_out */ | |
552 | ||
553 | /* set up */ | |
554 | if (z == Z_NULL || z->state == Z_NULL) | |
555 | return Z_STREAM_ERROR; | |
556 | if (z->state->mode != BAD) | |
557 | { | |
558 | z->state->mode = BAD; | |
559 | z->state->sub.marker = 0; | |
560 | } | |
561 | if ((n = z->avail_in) == 0) | |
562 | return Z_BUF_ERROR; | |
563 | p = z->next_in; | |
564 | m = z->state->sub.marker; | |
565 | ||
566 | /* search */ | |
567 | while (n && m < 4) | |
568 | { | |
569 | if (*p == (Byte)(m < 2 ? 0 : 0xff)) | |
570 | m++; | |
571 | else if (*p) | |
572 | m = 0; | |
573 | else | |
574 | m = 4 - m; | |
575 | p++, n--; | |
576 | } | |
577 | ||
578 | /* restore */ | |
579 | z->total_in += p - z->next_in; | |
580 | z->next_in = p; | |
581 | z->avail_in = n; | |
582 | z->state->sub.marker = m; | |
583 | ||
584 | /* return no joy or set up to restart on a new block */ | |
585 | if (m != 4) | |
586 | return Z_DATA_ERROR; | |
587 | r = z->total_in; w = z->total_out; | |
588 | inflateReset(z); | |
589 | z->total_in = r; z->total_out = w; | |
590 | z->state->mode = BLOCKS; | |
591 | return Z_OK; | |
592 | } | |
593 | ||
594 | #undef NEEDBYTE | |
595 | #undef NEXTBYTE | |
596 | ||
597 | /*+++++*/ | |
598 | /* infutil.h -- types and macros common to blocks and codes | |
599 | * Copyright (C) 1995 Mark Adler | |
600 | * For conditions of distribution and use, see copyright notice in zlib.h | |
601 | */ | |
602 | ||
603 | /* WARNING: this file should *not* be used by applications. It is | |
604 | part of the implementation of the compression library and is | |
605 | subject to change. Applications should only use zlib.h. | |
606 | */ | |
607 | ||
608 | /* inflate blocks semi-private state */ | |
609 | struct inflate_blocks_state { | |
610 | ||
611 | /* mode */ | |
612 | enum { | |
613 | TYPE, /* get type bits (3, including end bit) */ | |
614 | LENS, /* get lengths for stored */ | |
615 | STORED, /* processing stored block */ | |
616 | TABLE, /* get table lengths */ | |
617 | BTREE, /* get bit lengths tree for a dynamic block */ | |
618 | DTREE, /* get length, distance trees for a dynamic block */ | |
619 | CODES, /* processing fixed or dynamic block */ | |
620 | DRY, /* output remaining window bytes */ | |
621 | DONEB, /* finished last block, done */ | |
622 | BADB} /* got a data error--stuck here */ | |
623 | mode; /* current inflate_block mode */ | |
624 | ||
625 | /* mode dependent information */ | |
626 | union { | |
627 | uInt left; /* if STORED, bytes left to copy */ | |
628 | struct { | |
629 | uInt table; /* table lengths (14 bits) */ | |
630 | uInt index; /* index into blens (or border) */ | |
631 | uIntf *blens; /* bit lengths of codes */ | |
632 | uInt bb; /* bit length tree depth */ | |
633 | inflate_huft *tb; /* bit length decoding tree */ | |
634 | int nblens; /* # elements allocated at blens */ | |
635 | } trees; /* if DTREE, decoding info for trees */ | |
636 | struct { | |
637 | inflate_huft *tl, *td; /* trees to free */ | |
638 | inflate_codes_statef | |
639 | *codes; | |
640 | } decode; /* if CODES, current state */ | |
641 | } sub; /* submode */ | |
642 | uInt last; /* true if this block is the last block */ | |
643 | ||
644 | /* mode independent information */ | |
645 | uInt bitk; /* bits in bit buffer */ | |
646 | uLong bitb; /* bit buffer */ | |
647 | Bytef *window; /* sliding window */ | |
648 | Bytef *end; /* one byte after sliding window */ | |
649 | Bytef *read; /* window read pointer */ | |
650 | Bytef *write; /* window write pointer */ | |
651 | check_func checkfn; /* check function */ | |
652 | uLong check; /* check on output */ | |
653 | ||
654 | }; | |
655 | ||
656 | ||
657 | /* defines for inflate input/output */ | |
658 | /* update pointers and return */ | |
659 | #define UPDBITS {s->bitb=b;s->bitk=k;} | |
660 | #define UPDIN {z->avail_in=n;z->total_in+=p-z->next_in;z->next_in=p;} | |
661 | #define UPDOUT {s->write=q;} | |
662 | #define UPDATE {UPDBITS UPDIN UPDOUT} | |
663 | #define LEAVE {UPDATE return inflate_flush(s,z,r);} | |
664 | /* get bytes and bits */ | |
665 | #define LOADIN {p=z->next_in;n=z->avail_in;b=s->bitb;k=s->bitk;} | |
666 | #define NEEDBYTE {if(n)r=Z_OK;else LEAVE} | |
667 | #define NEXTBYTE (n--,*p++) | |
668 | #define NEEDBITS(j) {while(k<(j)){NEEDBYTE;b|=((uLong)NEXTBYTE)<<k;k+=8;}} | |
669 | #define DUMPBITS(j) {b>>=(j);k-=(j);} | |
670 | /* output bytes */ | |
671 | #define WAVAIL (q<s->read?s->read-q-1:s->end-q) | |
672 | #define LOADOUT {q=s->write;m=WAVAIL;} | |
673 | #define WRAP {if(q==s->end&&s->read!=s->window){q=s->window;m=WAVAIL;}} | |
674 | #define FLUSH {UPDOUT r=inflate_flush(s,z,r); LOADOUT} | |
675 | #define NEEDOUT {if(m==0){WRAP if(m==0){FLUSH WRAP if(m==0) LEAVE}}r=Z_OK;} | |
676 | #define OUTBYTE(a) {*q++=(Byte)(a);m--;} | |
677 | /* load local pointers */ | |
678 | #define LOAD {LOADIN LOADOUT} | |
679 | ||
680 | /* And'ing with mask[n] masks the lower n bits */ | |
681 | local uInt inflate_mask[] = { | |
682 | 0x0000, | |
683 | 0x0001, 0x0003, 0x0007, 0x000f, 0x001f, 0x003f, 0x007f, 0x00ff, | |
684 | 0x01ff, 0x03ff, 0x07ff, 0x0fff, 0x1fff, 0x3fff, 0x7fff, 0xffff | |
685 | }; | |
686 | ||
687 | /* copy as much as possible from the sliding window to the output area */ | |
688 | local int inflate_flush OF(( | |
689 | inflate_blocks_statef *, | |
690 | z_stream *, | |
691 | int)); | |
692 | ||
693 | /*+++++*/ | |
694 | /* inffast.h -- header to use inffast.c | |
695 | * Copyright (C) 1995 Mark Adler | |
696 | * For conditions of distribution and use, see copyright notice in zlib.h | |
697 | */ | |
698 | ||
699 | /* WARNING: this file should *not* be used by applications. It is | |
700 | part of the implementation of the compression library and is | |
701 | subject to change. Applications should only use zlib.h. | |
702 | */ | |
703 | ||
704 | local int inflate_fast OF(( | |
705 | uInt, | |
706 | uInt, | |
707 | inflate_huft *, | |
708 | inflate_huft *, | |
709 | inflate_blocks_statef *, | |
710 | z_stream *)); | |
711 | ||
712 | ||
713 | /*+++++*/ | |
714 | /* infblock.c -- interpret and process block types to last block | |
715 | * Copyright (C) 1995 Mark Adler | |
716 | * For conditions of distribution and use, see copyright notice in zlib.h | |
717 | */ | |
718 | ||
719 | /* Table for deflate from PKZIP's appnote.txt. */ | |
720 | local uInt border[] = { /* Order of the bit length code lengths */ | |
721 | 16, 17, 18, 0, 8, 7, 9, 6, 10, 5, 11, 4, 12, 3, 13, 2, 14, 1, 15}; | |
722 | ||
723 | /* | |
724 | Notes beyond the 1.93a appnote.txt: | |
725 | ||
726 | 1. Distance pointers never point before the beginning of the output | |
727 | stream. | |
728 | 2. Distance pointers can point back across blocks, up to 32k away. | |
729 | 3. There is an implied maximum of 7 bits for the bit length table and | |
730 | 15 bits for the actual data. | |
731 | 4. If only one code exists, then it is encoded using one bit. (Zero | |
732 | would be more efficient, but perhaps a little confusing.) If two | |
733 | codes exist, they are coded using one bit each (0 and 1). | |
734 | 5. There is no way of sending zero distance codes--a dummy must be | |
735 | sent if there are none. (History: a pre 2.0 version of PKZIP would | |
736 | store blocks with no distance codes, but this was discovered to be | |
737 | too harsh a criterion.) Valid only for 1.93a. 2.04c does allow | |
738 | zero distance codes, which is sent as one code of zero bits in | |
739 | length. | |
740 | 6. There are up to 286 literal/length codes. Code 256 represents the | |
741 | end-of-block. Note however that the static length tree defines | |
742 | 288 codes just to fill out the Huffman codes. Codes 286 and 287 | |
743 | cannot be used though, since there is no length base or extra bits | |
744 | defined for them. Similarily, there are up to 30 distance codes. | |
745 | However, static trees define 32 codes (all 5 bits) to fill out the | |
746 | Huffman codes, but the last two had better not show up in the data. | |
747 | 7. Unzip can check dynamic Huffman blocks for complete code sets. | |
748 | The exception is that a single code would not be complete (see #4). | |
749 | 8. The five bits following the block type is really the number of | |
750 | literal codes sent minus 257. | |
751 | 9. Length codes 8,16,16 are interpreted as 13 length codes of 8 bits | |
752 | (1+6+6). Therefore, to output three times the length, you output | |
753 | three codes (1+1+1), whereas to output four times the same length, | |
754 | you only need two codes (1+3). Hmm. | |
755 | 10. In the tree reconstruction algorithm, Code = Code + Increment | |
756 | only if BitLength(i) is not zero. (Pretty obvious.) | |
757 | 11. Correction: 4 Bits: # of Bit Length codes - 4 (4 - 19) | |
758 | 12. Note: length code 284 can represent 227-258, but length code 285 | |
759 | really is 258. The last length deserves its own, short code | |
760 | since it gets used a lot in very redundant files. The length | |
761 | 258 is special since 258 - 3 (the min match length) is 255. | |
762 | 13. The literal/length and distance code bit lengths are read as a | |
763 | single stream of lengths. It is possible (and advantageous) for | |
764 | a repeat code (16, 17, or 18) to go across the boundary between | |
765 | the two sets of lengths. | |
766 | */ | |
767 | ||
768 | ||
769 | local void inflate_blocks_reset( | |
770 | inflate_blocks_statef *s, | |
771 | z_stream *z, | |
772 | uLongf *c | |
773 | ) | |
774 | { | |
775 | if (s->checkfn != Z_NULL) | |
776 | *c = s->check; | |
777 | if (s->mode == BTREE || s->mode == DTREE) | |
778 | ZFREE(z, s->sub.trees.blens, s->sub.trees.nblens * sizeof(uInt)); | |
779 | if (s->mode == CODES) | |
780 | { | |
781 | inflate_codes_free(s->sub.decode.codes, z); | |
782 | inflate_trees_free(s->sub.decode.td, z); | |
783 | inflate_trees_free(s->sub.decode.tl, z); | |
784 | } | |
785 | s->mode = TYPE; | |
786 | s->bitk = 0; | |
787 | s->bitb = 0; | |
788 | s->read = s->write = s->window; | |
789 | if (s->checkfn != Z_NULL) | |
790 | s->check = (*s->checkfn)(0L, Z_NULL, 0); | |
791 | Trace((stderr, "inflate: blocks reset\n")); | |
792 | } | |
793 | ||
794 | ||
795 | local inflate_blocks_statef *inflate_blocks_new( | |
796 | z_stream *z, | |
797 | check_func c, | |
798 | uInt w | |
799 | ) | |
800 | { | |
801 | inflate_blocks_statef *s; | |
802 | ||
803 | if ((s = (inflate_blocks_statef *)ZALLOC | |
804 | (z,1,sizeof(struct inflate_blocks_state))) == Z_NULL) | |
805 | return s; | |
806 | if ((s->window = (Bytef *)ZALLOC(z, 1, w)) == Z_NULL) | |
807 | { | |
808 | ZFREE(z, s, sizeof(struct inflate_blocks_state)); | |
809 | return Z_NULL; | |
810 | } | |
811 | s->end = s->window + w; | |
812 | s->checkfn = c; | |
813 | s->mode = TYPE; | |
814 | Trace((stderr, "inflate: blocks allocated\n")); | |
815 | inflate_blocks_reset(s, z, &s->check); | |
816 | return s; | |
817 | } | |
818 | ||
819 | ||
820 | local int inflate_blocks( | |
821 | inflate_blocks_statef *s, | |
822 | z_stream *z, | |
823 | int r | |
824 | ) | |
825 | { | |
826 | uInt t; /* temporary storage */ | |
827 | uLong b; /* bit buffer */ | |
828 | uInt k; /* bits in bit buffer */ | |
829 | Bytef *p; /* input data pointer */ | |
830 | uInt n; /* bytes available there */ | |
831 | Bytef *q; /* output window write pointer */ | |
832 | uInt m; /* bytes to end of window or read pointer */ | |
833 | ||
834 | /* copy input/output information to locals (UPDATE macro restores) */ | |
835 | LOAD | |
836 | ||
837 | /* process input based on current state */ | |
838 | while (1) switch (s->mode) | |
839 | { | |
840 | case TYPE: | |
841 | NEEDBITS(3) | |
842 | t = (uInt)b & 7; | |
843 | s->last = t & 1; | |
844 | switch (t >> 1) | |
845 | { | |
846 | case 0: /* stored */ | |
847 | Trace((stderr, "inflate: stored block%s\n", | |
848 | s->last ? " (last)" : "")); | |
849 | DUMPBITS(3) | |
850 | t = k & 7; /* go to byte boundary */ | |
851 | DUMPBITS(t) | |
852 | s->mode = LENS; /* get length of stored block */ | |
853 | break; | |
854 | case 1: /* fixed */ | |
855 | Trace((stderr, "inflate: fixed codes block%s\n", | |
856 | s->last ? " (last)" : "")); | |
857 | { | |
858 | uInt bl, bd; | |
859 | inflate_huft *tl, *td; | |
860 | ||
861 | inflate_trees_fixed(&bl, &bd, &tl, &td); | |
862 | s->sub.decode.codes = inflate_codes_new(bl, bd, tl, td, z); | |
863 | if (s->sub.decode.codes == Z_NULL) | |
864 | { | |
865 | r = Z_MEM_ERROR; | |
866 | LEAVE | |
867 | } | |
868 | s->sub.decode.tl = Z_NULL; /* don't try to free these */ | |
869 | s->sub.decode.td = Z_NULL; | |
870 | } | |
871 | DUMPBITS(3) | |
872 | s->mode = CODES; | |
873 | break; | |
874 | case 2: /* dynamic */ | |
875 | Trace((stderr, "inflate: dynamic codes block%s\n", | |
876 | s->last ? " (last)" : "")); | |
877 | DUMPBITS(3) | |
878 | s->mode = TABLE; | |
879 | break; | |
880 | case 3: /* illegal */ | |
881 | DUMPBITS(3) | |
882 | s->mode = BADB; | |
883 | z->msg = "invalid block type"; | |
884 | r = Z_DATA_ERROR; | |
885 | LEAVE | |
886 | } | |
887 | break; | |
888 | case LENS: | |
889 | NEEDBITS(32) | |
890 | if (((~b) >> 16) != (b & 0xffff)) | |
891 | { | |
892 | s->mode = BADB; | |
893 | z->msg = "invalid stored block lengths"; | |
894 | r = Z_DATA_ERROR; | |
895 | LEAVE | |
896 | } | |
897 | s->sub.left = (uInt)b & 0xffff; | |
898 | b = k = 0; /* dump bits */ | |
899 | Tracev((stderr, "inflate: stored length %u\n", s->sub.left)); | |
900 | s->mode = s->sub.left ? STORED : TYPE; | |
901 | break; | |
902 | case STORED: | |
903 | if (n == 0) | |
904 | LEAVE | |
905 | NEEDOUT | |
906 | t = s->sub.left; | |
907 | if (t > n) t = n; | |
908 | if (t > m) t = m; | |
909 | zmemcpy(q, p, t); | |
910 | p += t; n -= t; | |
911 | q += t; m -= t; | |
912 | if ((s->sub.left -= t) != 0) | |
913 | break; | |
914 | Tracev((stderr, "inflate: stored end, %lu total out\n", | |
915 | z->total_out + (q >= s->read ? q - s->read : | |
916 | (s->end - s->read) + (q - s->window)))); | |
917 | s->mode = s->last ? DRY : TYPE; | |
918 | break; | |
919 | case TABLE: | |
920 | NEEDBITS(14) | |
921 | s->sub.trees.table = t = (uInt)b & 0x3fff; | |
922 | #ifndef PKZIP_BUG_WORKAROUND | |
923 | if ((t & 0x1f) > 29 || ((t >> 5) & 0x1f) > 29) | |
924 | { | |
925 | s->mode = BADB; | |
926 | z->msg = "too many length or distance symbols"; | |
927 | r = Z_DATA_ERROR; | |
928 | LEAVE | |
929 | } | |
930 | #endif | |
931 | t = 258 + (t & 0x1f) + ((t >> 5) & 0x1f); | |
932 | if (t < 19) | |
933 | t = 19; | |
934 | if ((s->sub.trees.blens = (uIntf*)ZALLOC(z, t, sizeof(uInt))) == Z_NULL) | |
935 | { | |
936 | r = Z_MEM_ERROR; | |
937 | LEAVE | |
938 | } | |
939 | s->sub.trees.nblens = t; | |
940 | DUMPBITS(14) | |
941 | s->sub.trees.index = 0; | |
942 | Tracev((stderr, "inflate: table sizes ok\n")); | |
943 | s->mode = BTREE; | |
944 | case BTREE: | |
945 | while (s->sub.trees.index < 4 + (s->sub.trees.table >> 10)) | |
946 | { | |
947 | NEEDBITS(3) | |
948 | s->sub.trees.blens[border[s->sub.trees.index++]] = (uInt)b & 7; | |
949 | DUMPBITS(3) | |
950 | } | |
951 | while (s->sub.trees.index < 19) | |
952 | s->sub.trees.blens[border[s->sub.trees.index++]] = 0; | |
953 | s->sub.trees.bb = 7; | |
954 | t = inflate_trees_bits(s->sub.trees.blens, &s->sub.trees.bb, | |
955 | &s->sub.trees.tb, z); | |
956 | if (t != Z_OK) | |
957 | { | |
958 | r = t; | |
959 | if (r == Z_DATA_ERROR) | |
960 | s->mode = BADB; | |
961 | LEAVE | |
962 | } | |
963 | s->sub.trees.index = 0; | |
964 | Tracev((stderr, "inflate: bits tree ok\n")); | |
965 | s->mode = DTREE; | |
966 | case DTREE: | |
967 | while (t = s->sub.trees.table, | |
968 | s->sub.trees.index < 258 + (t & 0x1f) + ((t >> 5) & 0x1f)) | |
969 | { | |
970 | inflate_huft *h; | |
971 | uInt i, j, c; | |
972 | ||
973 | t = s->sub.trees.bb; | |
974 | NEEDBITS(t) | |
975 | h = s->sub.trees.tb + ((uInt)b & inflate_mask[t]); | |
976 | t = h->word.what.Bits; | |
977 | c = h->more.Base; | |
978 | if (c < 16) | |
979 | { | |
980 | DUMPBITS(t) | |
981 | s->sub.trees.blens[s->sub.trees.index++] = c; | |
982 | } | |
983 | else /* c == 16..18 */ | |
984 | { | |
985 | i = c == 18 ? 7 : c - 14; | |
986 | j = c == 18 ? 11 : 3; | |
987 | NEEDBITS(t + i) | |
988 | DUMPBITS(t) | |
989 | j += (uInt)b & inflate_mask[i]; | |
990 | DUMPBITS(i) | |
991 | i = s->sub.trees.index; | |
992 | t = s->sub.trees.table; | |
993 | if (i + j > 258 + (t & 0x1f) + ((t >> 5) & 0x1f) || | |
994 | (c == 16 && i < 1)) | |
995 | { | |
996 | s->mode = BADB; | |
997 | z->msg = "invalid bit length repeat"; | |
998 | r = Z_DATA_ERROR; | |
999 | LEAVE | |
1000 | } | |
1001 | c = c == 16 ? s->sub.trees.blens[i - 1] : 0; | |
1002 | do { | |
1003 | s->sub.trees.blens[i++] = c; | |
1004 | } while (--j); | |
1005 | s->sub.trees.index = i; | |
1006 | } | |
1007 | } | |
1008 | inflate_trees_free(s->sub.trees.tb, z); | |
1009 | s->sub.trees.tb = Z_NULL; | |
1010 | { | |
1011 | uInt bl, bd; | |
1012 | inflate_huft *tl, *td; | |
1013 | inflate_codes_statef *c; | |
1014 | ||
1015 | bl = 9; /* must be <= 9 for lookahead assumptions */ | |
1016 | bd = 6; /* must be <= 9 for lookahead assumptions */ | |
1017 | t = s->sub.trees.table; | |
1018 | t = inflate_trees_dynamic(257 + (t & 0x1f), 1 + ((t >> 5) & 0x1f), | |
1019 | s->sub.trees.blens, &bl, &bd, &tl, &td, z); | |
1020 | if (t != Z_OK) | |
1021 | { | |
1022 | if (t == (uInt)Z_DATA_ERROR) | |
1023 | s->mode = BADB; | |
1024 | r = t; | |
1025 | LEAVE | |
1026 | } | |
1027 | Tracev((stderr, "inflate: trees ok\n")); | |
1028 | if ((c = inflate_codes_new(bl, bd, tl, td, z)) == Z_NULL) | |
1029 | { | |
1030 | inflate_trees_free(td, z); | |
1031 | inflate_trees_free(tl, z); | |
1032 | r = Z_MEM_ERROR; | |
1033 | LEAVE | |
1034 | } | |
1035 | ZFREE(z, s->sub.trees.blens, s->sub.trees.nblens * sizeof(uInt)); | |
1036 | s->sub.decode.codes = c; | |
1037 | s->sub.decode.tl = tl; | |
1038 | s->sub.decode.td = td; | |
1039 | } | |
1040 | s->mode = CODES; | |
1041 | case CODES: | |
1042 | UPDATE | |
1043 | if ((r = inflate_codes(s, z, r)) != Z_STREAM_END) | |
1044 | return inflate_flush(s, z, r); | |
1045 | r = Z_OK; | |
1046 | inflate_codes_free(s->sub.decode.codes, z); | |
1047 | inflate_trees_free(s->sub.decode.td, z); | |
1048 | inflate_trees_free(s->sub.decode.tl, z); | |
1049 | LOAD | |
1050 | Tracev((stderr, "inflate: codes end, %lu total out\n", | |
1051 | z->total_out + (q >= s->read ? q - s->read : | |
1052 | (s->end - s->read) + (q - s->window)))); | |
1053 | if (!s->last) | |
1054 | { | |
1055 | s->mode = TYPE; | |
1056 | break; | |
1057 | } | |
1058 | if (k > 7) /* return unused byte, if any */ | |
1059 | { | |
1060 | Assert(k < 16, "inflate_codes grabbed too many bytes") | |
1061 | k -= 8; | |
1062 | n++; | |
1063 | p--; /* can always return one */ | |
1064 | } | |
1065 | s->mode = DRY; | |
1066 | case DRY: | |
1067 | FLUSH | |
1068 | if (s->read != s->write) | |
1069 | LEAVE | |
1070 | s->mode = DONEB; | |
1071 | case DONEB: | |
1072 | r = Z_STREAM_END; | |
1073 | LEAVE | |
1074 | case BADB: | |
1075 | r = Z_DATA_ERROR; | |
1076 | LEAVE | |
1077 | default: | |
1078 | r = Z_STREAM_ERROR; | |
1079 | LEAVE | |
1080 | } | |
1081 | } | |
1082 | ||
1083 | ||
1084 | local int inflate_blocks_free( | |
1085 | inflate_blocks_statef *s, | |
1086 | z_stream *z, | |
1087 | uLongf *c | |
1088 | ) | |
1089 | { | |
1090 | inflate_blocks_reset(s, z, c); | |
1091 | ZFREE(z, s->window, s->end - s->window); | |
1092 | ZFREE(z, s, sizeof(struct inflate_blocks_state)); | |
1093 | Trace((stderr, "inflate: blocks freed\n")); | |
1094 | return Z_OK; | |
1095 | } | |
1096 | ||
1097 | /* | |
1098 | * This subroutine adds the data at next_in/avail_in to the output history | |
1099 | * without performing any output. The output buffer must be "caught up"; | |
1100 | * i.e. no pending output (hence s->read equals s->write), and the state must | |
1101 | * be BLOCKS (i.e. we should be willing to see the start of a series of | |
1102 | * BLOCKS). On exit, the output will also be caught up, and the checksum | |
1103 | * will have been updated if need be. | |
1104 | */ | |
1105 | local int inflate_addhistory( | |
1106 | inflate_blocks_statef *s, | |
1107 | z_stream *z | |
1108 | ) | |
1109 | { | |
1110 | uLong b; /* bit buffer */ /* NOT USED HERE */ | |
1111 | uInt k; /* bits in bit buffer */ /* NOT USED HERE */ | |
1112 | uInt t; /* temporary storage */ | |
1113 | Bytef *p; /* input data pointer */ | |
1114 | uInt n; /* bytes available there */ | |
1115 | Bytef *q; /* output window write pointer */ | |
1116 | uInt m; /* bytes to end of window or read pointer */ | |
1117 | ||
1118 | if (s->read != s->write) | |
1119 | return Z_STREAM_ERROR; | |
1120 | if (s->mode != TYPE) | |
1121 | return Z_DATA_ERROR; | |
1122 | ||
1123 | /* we're ready to rock */ | |
1124 | LOAD | |
1125 | /* while there is input ready, copy to output buffer, moving | |
1126 | * pointers as needed. | |
1127 | */ | |
1128 | while (n) { | |
1129 | t = n; /* how many to do */ | |
1130 | /* is there room until end of buffer? */ | |
1131 | if (t > m) t = m; | |
1132 | /* update check information */ | |
1133 | if (s->checkfn != Z_NULL) | |
1134 | s->check = (*s->checkfn)(s->check, q, t); | |
1135 | zmemcpy(q, p, t); | |
1136 | q += t; | |
1137 | p += t; | |
1138 | n -= t; | |
1139 | z->total_out += t; | |
1140 | s->read = q; /* drag read pointer forward */ | |
1141 | /* WRAP */ /* expand WRAP macro by hand to handle s->read */ | |
1142 | if (q == s->end) { | |
1143 | s->read = q = s->window; | |
1144 | m = WAVAIL; | |
1145 | } | |
1146 | } | |
1147 | UPDATE | |
1148 | return Z_OK; | |
1149 | } | |
1150 | ||
1151 | ||
1152 | /* | |
1153 | * At the end of a Deflate-compressed PPP packet, we expect to have seen | |
1154 | * a `stored' block type value but not the (zero) length bytes. | |
1155 | */ | |
1156 | local int inflate_packet_flush( | |
1157 | inflate_blocks_statef *s | |
1158 | ) | |
1159 | { | |
1160 | if (s->mode != LENS) | |
1161 | return Z_DATA_ERROR; | |
1162 | s->mode = TYPE; | |
1163 | return Z_OK; | |
1164 | } | |
1165 | ||
1166 | ||
1167 | /*+++++*/ | |
1168 | /* inftrees.c -- generate Huffman trees for efficient decoding | |
1169 | * Copyright (C) 1995 Mark Adler | |
1170 | * For conditions of distribution and use, see copyright notice in zlib.h | |
1171 | */ | |
1172 | ||
1173 | /* simplify the use of the inflate_huft type with some defines */ | |
1174 | #define base more.Base | |
1175 | #define next more.Next | |
1176 | #define exop word.what.Exop | |
1177 | #define bits word.what.Bits | |
1178 | ||
1179 | ||
1180 | local int huft_build OF(( | |
1181 | uIntf *, /* code lengths in bits */ | |
1182 | uInt, /* number of codes */ | |
1183 | uInt, /* number of "simple" codes */ | |
1184 | uIntf *, /* list of base values for non-simple codes */ | |
1185 | uIntf *, /* list of extra bits for non-simple codes */ | |
1186 | inflate_huft * FAR*,/* result: starting table */ | |
1187 | uIntf *, /* maximum lookup bits (returns actual) */ | |
1188 | z_stream *)); /* for zalloc function */ | |
1189 | ||
1190 | local voidpf falloc OF(( | |
1191 | voidpf, /* opaque pointer (not used) */ | |
1192 | uInt, /* number of items */ | |
1193 | uInt)); /* size of item */ | |
1194 | ||
1195 | local void ffree OF(( | |
1196 | voidpf q, /* opaque pointer (not used) */ | |
1197 | voidpf p, /* what to free (not used) */ | |
1198 | uInt n)); /* number of bytes (not used) */ | |
1199 | ||
1200 | /* Tables for deflate from PKZIP's appnote.txt. */ | |
1201 | local uInt cplens[] = { /* Copy lengths for literal codes 257..285 */ | |
1202 | 3, 4, 5, 6, 7, 8, 9, 10, 11, 13, 15, 17, 19, 23, 27, 31, | |
1203 | 35, 43, 51, 59, 67, 83, 99, 115, 131, 163, 195, 227, 258, 0, 0}; | |
1204 | /* actually lengths - 2; also see note #13 above about 258 */ | |
1205 | local uInt cplext[] = { /* Extra bits for literal codes 257..285 */ | |
1206 | 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 2, 2, 2, 2, | |
1207 | 3, 3, 3, 3, 4, 4, 4, 4, 5, 5, 5, 5, 0, 192, 192}; /* 192==invalid */ | |
1208 | local uInt cpdist[] = { /* Copy offsets for distance codes 0..29 */ | |
1209 | 1, 2, 3, 4, 5, 7, 9, 13, 17, 25, 33, 49, 65, 97, 129, 193, | |
1210 | 257, 385, 513, 769, 1025, 1537, 2049, 3073, 4097, 6145, | |
1211 | 8193, 12289, 16385, 24577}; | |
1212 | local uInt cpdext[] = { /* Extra bits for distance codes */ | |
1213 | 0, 0, 0, 0, 1, 1, 2, 2, 3, 3, 4, 4, 5, 5, 6, 6, | |
1214 | 7, 7, 8, 8, 9, 9, 10, 10, 11, 11, | |
1215 | 12, 12, 13, 13}; | |
1216 | ||
1217 | /* | |
1218 | Huffman code decoding is performed using a multi-level table lookup. | |
1219 | The fastest way to decode is to simply build a lookup table whose | |
1220 | size is determined by the longest code. However, the time it takes | |
1221 | to build this table can also be a factor if the data being decoded | |
1222 | is not very long. The most common codes are necessarily the | |
1223 | shortest codes, so those codes dominate the decoding time, and hence | |
1224 | the speed. The idea is you can have a shorter table that decodes the | |
1225 | shorter, more probable codes, and then point to subsidiary tables for | |
1226 | the longer codes. The time it costs to decode the longer codes is | |
1227 | then traded against the time it takes to make longer tables. | |
1228 | ||
1229 | This results of this trade are in the variables lbits and dbits | |
1230 | below. lbits is the number of bits the first level table for literal/ | |
1231 | length codes can decode in one step, and dbits is the same thing for | |
1232 | the distance codes. Subsequent tables are also less than or equal to | |
1233 | those sizes. These values may be adjusted either when all of the | |
1234 | codes are shorter than that, in which case the longest code length in | |
1235 | bits is used, or when the shortest code is *longer* than the requested | |
1236 | table size, in which case the length of the shortest code in bits is | |
1237 | used. | |
1238 | ||
1239 | There are two different values for the two tables, since they code a | |
1240 | different number of possibilities each. The literal/length table | |
1241 | codes 286 possible values, or in a flat code, a little over eight | |
1242 | bits. The distance table codes 30 possible values, or a little less | |
1243 | than five bits, flat. The optimum values for speed end up being | |
1244 | about one bit more than those, so lbits is 8+1 and dbits is 5+1. | |
1245 | The optimum values may differ though from machine to machine, and | |
1246 | possibly even between compilers. Your mileage may vary. | |
1247 | */ | |
1248 | ||
1249 | ||
1250 | /* If BMAX needs to be larger than 16, then h and x[] should be uLong. */ | |
1251 | #define BMAX 15 /* maximum bit length of any code */ | |
1252 | #define N_MAX 288 /* maximum number of codes in any set */ | |
1253 | ||
1254 | #ifdef DEBUG_ZLIB | |
1255 | uInt inflate_hufts; | |
1256 | #endif | |
1257 | ||
1258 | local int huft_build( | |
1259 | uIntf *b, /* code lengths in bits (all assumed <= BMAX) */ | |
1260 | uInt n, /* number of codes (assumed <= N_MAX) */ | |
1261 | uInt s, /* number of simple-valued codes (0..s-1) */ | |
1262 | uIntf *d, /* list of base values for non-simple codes */ | |
1263 | uIntf *e, /* list of extra bits for non-simple codes */ | |
1264 | inflate_huft * FAR *t, /* result: starting table */ | |
1265 | uIntf *m, /* maximum lookup bits, returns actual */ | |
1266 | z_stream *zs /* for zalloc function */ | |
1267 | ) | |
1268 | /* Given a list of code lengths and a maximum table size, make a set of | |
1269 | tables to decode that set of codes. Return Z_OK on success, Z_BUF_ERROR | |
1270 | if the given code set is incomplete (the tables are still built in this | |
1271 | case), Z_DATA_ERROR if the input is invalid (all zero length codes or an | |
1272 | over-subscribed set of lengths), or Z_MEM_ERROR if not enough memory. */ | |
1273 | { | |
1274 | ||
1275 | uInt a; /* counter for codes of length k */ | |
1276 | uInt c[BMAX+1]; /* bit length count table */ | |
1277 | uInt f; /* i repeats in table every f entries */ | |
1278 | int g; /* maximum code length */ | |
1279 | int h; /* table level */ | |
1280 | register uInt i; /* counter, current code */ | |
1281 | register uInt j; /* counter */ | |
1282 | register int k; /* number of bits in current code */ | |
1283 | int l; /* bits per table (returned in m) */ | |
1284 | register uIntf *p; /* pointer into c[], b[], or v[] */ | |
1285 | inflate_huft *q; /* points to current table */ | |
1286 | struct inflate_huft_s r; /* table entry for structure assignment */ | |
1287 | inflate_huft *u[BMAX]; /* table stack */ | |
1288 | uInt v[N_MAX]; /* values in order of bit length */ | |
1289 | register int w; /* bits before this table == (l * h) */ | |
1290 | uInt x[BMAX+1]; /* bit offsets, then code stack */ | |
1291 | uIntf *xp; /* pointer into x */ | |
1292 | int y; /* number of dummy codes added */ | |
1293 | uInt z; /* number of entries in current table */ | |
1294 | ||
1295 | ||
1296 | /* Generate counts for each bit length */ | |
1297 | p = c; | |
1298 | #define C0 *p++ = 0; | |
1299 | #define C2 C0 C0 C0 C0 | |
1300 | #define C4 C2 C2 C2 C2 | |
1301 | C4 /* clear c[]--assume BMAX+1 is 16 */ | |
1302 | p = b; i = n; | |
1303 | do { | |
1304 | c[*p++]++; /* assume all entries <= BMAX */ | |
1305 | } while (--i); | |
1306 | if (c[0] == n) /* null input--all zero length codes */ | |
1307 | { | |
1308 | *t = (inflate_huft *)Z_NULL; | |
1309 | *m = 0; | |
4aad724d | 1310 | return Z_DATA_ERROR; |
1da177e4 LT |
1311 | } |
1312 | ||
1313 | ||
1314 | /* Find minimum and maximum length, bound *m by those */ | |
1315 | l = *m; | |
1316 | for (j = 1; j <= BMAX; j++) | |
1317 | if (c[j]) | |
1318 | break; | |
1319 | k = j; /* minimum code length */ | |
1320 | if ((uInt)l < j) | |
1321 | l = j; | |
1322 | for (i = BMAX; i; i--) | |
1323 | if (c[i]) | |
1324 | break; | |
1325 | g = i; /* maximum code length */ | |
1326 | if ((uInt)l > i) | |
1327 | l = i; | |
1328 | *m = l; | |
1329 | ||
1330 | ||
1331 | /* Adjust last length count to fill out codes, if needed */ | |
1332 | for (y = 1 << j; j < i; j++, y <<= 1) | |
1333 | if ((y -= c[j]) < 0) | |
1334 | return Z_DATA_ERROR; | |
1335 | if ((y -= c[i]) < 0) | |
1336 | return Z_DATA_ERROR; | |
1337 | c[i] += y; | |
1338 | ||
1339 | ||
1340 | /* Generate starting offsets into the value table for each length */ | |
1341 | x[1] = j = 0; | |
1342 | p = c + 1; xp = x + 2; | |
1343 | while (--i) { /* note that i == g from above */ | |
1344 | *xp++ = (j += *p++); | |
1345 | } | |
1346 | ||
1347 | ||
1348 | /* Make a table of values in order of bit lengths */ | |
1349 | p = b; i = 0; | |
1350 | do { | |
1351 | if ((j = *p++) != 0) | |
1352 | v[x[j]++] = i; | |
1353 | } while (++i < n); | |
4aad724d | 1354 | n = x[g]; /* set n to length of v */ |
1da177e4 LT |
1355 | |
1356 | ||
1357 | /* Generate the Huffman codes and for each, make the table entries */ | |
1358 | x[0] = i = 0; /* first Huffman code is zero */ | |
1359 | p = v; /* grab values in bit order */ | |
1360 | h = -1; /* no tables yet--level -1 */ | |
1361 | w = -l; /* bits decoded == (l * h) */ | |
1362 | u[0] = (inflate_huft *)Z_NULL; /* just to keep compilers happy */ | |
1363 | q = (inflate_huft *)Z_NULL; /* ditto */ | |
1364 | z = 0; /* ditto */ | |
1365 | ||
1366 | /* go through the bit lengths (k already is bits in shortest code) */ | |
1367 | for (; k <= g; k++) | |
1368 | { | |
1369 | a = c[k]; | |
1370 | while (a--) | |
1371 | { | |
1372 | /* here i is the Huffman code of length k bits for value *p */ | |
1373 | /* make tables up to required level */ | |
1374 | while (k > w + l) | |
1375 | { | |
1376 | h++; | |
1377 | w += l; /* previous table always l bits */ | |
1378 | ||
1379 | /* compute minimum size table less than or equal to l bits */ | |
1380 | z = (z = g - w) > (uInt)l ? l : z; /* table size upper limit */ | |
1381 | if ((f = 1 << (j = k - w)) > a + 1) /* try a k-w bit table */ | |
1382 | { /* too few codes for k-w bit table */ | |
1383 | f -= a + 1; /* deduct codes from patterns left */ | |
1384 | xp = c + k; | |
1385 | if (j < z) | |
1386 | while (++j < z) /* try smaller tables up to z bits */ | |
1387 | { | |
1388 | if ((f <<= 1) <= *++xp) | |
1389 | break; /* enough codes to use up j bits */ | |
1390 | f -= *xp; /* else deduct codes from patterns */ | |
1391 | } | |
1392 | } | |
1393 | z = 1 << j; /* table entries for j-bit table */ | |
1394 | ||
1395 | /* allocate and link in new table */ | |
1396 | if ((q = (inflate_huft *)ZALLOC | |
1397 | (zs,z + 1,sizeof(inflate_huft))) == Z_NULL) | |
1398 | { | |
1399 | if (h) | |
1400 | inflate_trees_free(u[0], zs); | |
1401 | return Z_MEM_ERROR; /* not enough memory */ | |
1402 | } | |
1403 | q->word.Nalloc = z + 1; | |
1404 | #ifdef DEBUG_ZLIB | |
1405 | inflate_hufts += z + 1; | |
1406 | #endif | |
1407 | *t = q + 1; /* link to list for huft_free() */ | |
1408 | *(t = &(q->next)) = Z_NULL; | |
1409 | u[h] = ++q; /* table starts after link */ | |
1410 | ||
1411 | /* connect to last table, if there is one */ | |
1412 | if (h) | |
1413 | { | |
1414 | x[h] = i; /* save pattern for backing up */ | |
1415 | r.bits = (Byte)l; /* bits to dump before this table */ | |
1416 | r.exop = (Byte)j; /* bits in this table */ | |
1417 | r.next = q; /* pointer to this table */ | |
1418 | j = i >> (w - l); /* (get around Turbo C bug) */ | |
1419 | u[h-1][j] = r; /* connect to last table */ | |
1420 | } | |
1421 | } | |
1422 | ||
1423 | /* set up table entry in r */ | |
1424 | r.bits = (Byte)(k - w); | |
1425 | if (p >= v + n) | |
1426 | r.exop = 128 + 64; /* out of values--invalid code */ | |
1427 | else if (*p < s) | |
1428 | { | |
1429 | r.exop = (Byte)(*p < 256 ? 0 : 32 + 64); /* 256 is end-of-block */ | |
1430 | r.base = *p++; /* simple code is just the value */ | |
1431 | } | |
1432 | else | |
1433 | { | |
1434 | r.exop = (Byte)e[*p - s] + 16 + 64; /* non-simple--look up in lists */ | |
1435 | r.base = d[*p++ - s]; | |
1436 | } | |
1437 | ||
1438 | /* fill code-like entries with r */ | |
1439 | f = 1 << (k - w); | |
1440 | for (j = i >> w; j < z; j += f) | |
1441 | q[j] = r; | |
1442 | ||
1443 | /* backwards increment the k-bit code i */ | |
1444 | for (j = 1 << (k - 1); i & j; j >>= 1) | |
1445 | i ^= j; | |
1446 | i ^= j; | |
1447 | ||
1448 | /* backup over finished tables */ | |
1449 | while ((i & ((1 << w) - 1)) != x[h]) | |
1450 | { | |
1451 | h--; /* don't need to update q */ | |
1452 | w -= l; | |
1453 | } | |
1454 | } | |
1455 | } | |
1456 | ||
1457 | ||
1458 | /* Return Z_BUF_ERROR if we were given an incomplete table */ | |
1459 | return y != 0 && g != 1 ? Z_BUF_ERROR : Z_OK; | |
1460 | } | |
1461 | ||
1462 | ||
1463 | local int inflate_trees_bits( | |
1464 | uIntf *c, /* 19 code lengths */ | |
1465 | uIntf *bb, /* bits tree desired/actual depth */ | |
1466 | inflate_huft * FAR *tb, /* bits tree result */ | |
1467 | z_stream *z /* for zfree function */ | |
1468 | ) | |
1469 | { | |
1470 | int r; | |
1471 | ||
1472 | r = huft_build(c, 19, 19, (uIntf*)Z_NULL, (uIntf*)Z_NULL, tb, bb, z); | |
1473 | if (r == Z_DATA_ERROR) | |
1474 | z->msg = "oversubscribed dynamic bit lengths tree"; | |
1475 | else if (r == Z_BUF_ERROR) | |
1476 | { | |
1477 | inflate_trees_free(*tb, z); | |
1478 | z->msg = "incomplete dynamic bit lengths tree"; | |
1479 | r = Z_DATA_ERROR; | |
1480 | } | |
1481 | return r; | |
1482 | } | |
1483 | ||
1484 | ||
1485 | local int inflate_trees_dynamic( | |
1486 | uInt nl, /* number of literal/length codes */ | |
1487 | uInt nd, /* number of distance codes */ | |
1488 | uIntf *c, /* that many (total) code lengths */ | |
1489 | uIntf *bl, /* literal desired/actual bit depth */ | |
1490 | uIntf *bd, /* distance desired/actual bit depth */ | |
1491 | inflate_huft * FAR *tl, /* literal/length tree result */ | |
1492 | inflate_huft * FAR *td, /* distance tree result */ | |
1493 | z_stream *z /* for zfree function */ | |
1494 | ) | |
1495 | { | |
1496 | int r; | |
1497 | ||
1498 | /* build literal/length tree */ | |
1499 | if ((r = huft_build(c, nl, 257, cplens, cplext, tl, bl, z)) != Z_OK) | |
1500 | { | |
1501 | if (r == Z_DATA_ERROR) | |
1502 | z->msg = "oversubscribed literal/length tree"; | |
1503 | else if (r == Z_BUF_ERROR) | |
1504 | { | |
1505 | inflate_trees_free(*tl, z); | |
1506 | z->msg = "incomplete literal/length tree"; | |
1507 | r = Z_DATA_ERROR; | |
1508 | } | |
1509 | return r; | |
1510 | } | |
1511 | ||
1512 | /* build distance tree */ | |
1513 | if ((r = huft_build(c + nl, nd, 0, cpdist, cpdext, td, bd, z)) != Z_OK) | |
1514 | { | |
1515 | if (r == Z_DATA_ERROR) | |
1516 | z->msg = "oversubscribed literal/length tree"; | |
1517 | else if (r == Z_BUF_ERROR) { | |
1518 | #ifdef PKZIP_BUG_WORKAROUND | |
1519 | r = Z_OK; | |
1520 | } | |
1521 | #else | |
1522 | inflate_trees_free(*td, z); | |
1523 | z->msg = "incomplete literal/length tree"; | |
1524 | r = Z_DATA_ERROR; | |
1525 | } | |
1526 | inflate_trees_free(*tl, z); | |
1527 | return r; | |
1528 | #endif | |
1529 | } | |
1530 | ||
1531 | /* done */ | |
1532 | return Z_OK; | |
1533 | } | |
1534 | ||
1535 | ||
1536 | /* build fixed tables only once--keep them here */ | |
1537 | local int fixed_lock = 0; | |
1538 | local int fixed_built = 0; | |
1539 | #define FIXEDH 530 /* number of hufts used by fixed tables */ | |
1540 | local uInt fixed_left = FIXEDH; | |
1541 | local inflate_huft fixed_mem[FIXEDH]; | |
1542 | local uInt fixed_bl; | |
1543 | local uInt fixed_bd; | |
1544 | local inflate_huft *fixed_tl; | |
1545 | local inflate_huft *fixed_td; | |
1546 | ||
1547 | ||
1548 | local voidpf falloc( | |
1549 | voidpf q, /* opaque pointer (not used) */ | |
1550 | uInt n, /* number of items */ | |
1551 | uInt s /* size of item */ | |
1552 | ) | |
1553 | { | |
1554 | Assert(s == sizeof(inflate_huft) && n <= fixed_left, | |
1555 | "inflate_trees falloc overflow"); | |
1556 | if (q) s++; /* to make some compilers happy */ | |
1557 | fixed_left -= n; | |
1558 | return (voidpf)(fixed_mem + fixed_left); | |
1559 | } | |
1560 | ||
1561 | ||
1562 | local void ffree( | |
1563 | voidpf q, | |
1564 | voidpf p, | |
1565 | uInt n | |
1566 | ) | |
1567 | { | |
1568 | Assert(0, "inflate_trees ffree called!"); | |
1569 | if (q) q = p; /* to make some compilers happy */ | |
1570 | } | |
1571 | ||
1572 | ||
1573 | local int inflate_trees_fixed( | |
1574 | uIntf *bl, /* literal desired/actual bit depth */ | |
1575 | uIntf *bd, /* distance desired/actual bit depth */ | |
1576 | inflate_huft * FAR *tl, /* literal/length tree result */ | |
1577 | inflate_huft * FAR *td /* distance tree result */ | |
1578 | ) | |
1579 | { | |
1580 | /* build fixed tables if not built already--lock out other instances */ | |
1581 | while (++fixed_lock > 1) | |
1582 | fixed_lock--; | |
1583 | if (!fixed_built) | |
1584 | { | |
1585 | int k; /* temporary variable */ | |
1586 | unsigned c[288]; /* length list for huft_build */ | |
1587 | z_stream z; /* for falloc function */ | |
1588 | ||
1589 | /* set up fake z_stream for memory routines */ | |
1590 | z.zalloc = falloc; | |
1591 | z.zfree = ffree; | |
1592 | z.opaque = Z_NULL; | |
1593 | ||
1594 | /* literal table */ | |
1595 | for (k = 0; k < 144; k++) | |
1596 | c[k] = 8; | |
1597 | for (; k < 256; k++) | |
1598 | c[k] = 9; | |
1599 | for (; k < 280; k++) | |
1600 | c[k] = 7; | |
1601 | for (; k < 288; k++) | |
1602 | c[k] = 8; | |
1603 | fixed_bl = 7; | |
1604 | huft_build(c, 288, 257, cplens, cplext, &fixed_tl, &fixed_bl, &z); | |
1605 | ||
1606 | /* distance table */ | |
1607 | for (k = 0; k < 30; k++) | |
1608 | c[k] = 5; | |
1609 | fixed_bd = 5; | |
1610 | huft_build(c, 30, 0, cpdist, cpdext, &fixed_td, &fixed_bd, &z); | |
1611 | ||
1612 | /* done */ | |
1613 | fixed_built = 1; | |
1614 | } | |
1615 | fixed_lock--; | |
1616 | *bl = fixed_bl; | |
1617 | *bd = fixed_bd; | |
1618 | *tl = fixed_tl; | |
1619 | *td = fixed_td; | |
1620 | return Z_OK; | |
1621 | } | |
1622 | ||
1623 | ||
1624 | local int inflate_trees_free( | |
1625 | inflate_huft *t, /* table to free */ | |
1626 | z_stream *z /* for zfree function */ | |
1627 | ) | |
1628 | /* Free the malloc'ed tables built by huft_build(), which makes a linked | |
1629 | list of the tables it made, with the links in a dummy first entry of | |
1630 | each table. */ | |
1631 | { | |
1632 | register inflate_huft *p, *q; | |
1633 | ||
1634 | /* Go through linked list, freeing from the malloced (t[-1]) address. */ | |
1635 | p = t; | |
1636 | while (p != Z_NULL) | |
1637 | { | |
1638 | q = (--p)->next; | |
1639 | ZFREE(z, p, p->word.Nalloc * sizeof(inflate_huft)); | |
1640 | p = q; | |
1641 | } | |
1642 | return Z_OK; | |
1643 | } | |
1644 | ||
1645 | /*+++++*/ | |
1646 | /* infcodes.c -- process literals and length/distance pairs | |
1647 | * Copyright (C) 1995 Mark Adler | |
1648 | * For conditions of distribution and use, see copyright notice in zlib.h | |
1649 | */ | |
1650 | ||
1651 | /* simplify the use of the inflate_huft type with some defines */ | |
1652 | #define base more.Base | |
1653 | #define next more.Next | |
1654 | #define exop word.what.Exop | |
1655 | #define bits word.what.Bits | |
1656 | ||
1657 | /* inflate codes private state */ | |
1658 | struct inflate_codes_state { | |
1659 | ||
1660 | /* mode */ | |
1661 | enum { /* waiting for "i:"=input, "o:"=output, "x:"=nothing */ | |
1662 | START, /* x: set up for LEN */ | |
1663 | LEN, /* i: get length/literal/eob next */ | |
1664 | LENEXT, /* i: getting length extra (have base) */ | |
1665 | DIST, /* i: get distance next */ | |
1666 | DISTEXT, /* i: getting distance extra */ | |
1667 | COPY, /* o: copying bytes in window, waiting for space */ | |
1668 | LIT, /* o: got literal, waiting for output space */ | |
1669 | WASH, /* o: got eob, possibly still output waiting */ | |
1670 | END, /* x: got eob and all data flushed */ | |
1671 | BADCODE} /* x: got error */ | |
1672 | mode; /* current inflate_codes mode */ | |
1673 | ||
1674 | /* mode dependent information */ | |
1675 | uInt len; | |
1676 | union { | |
1677 | struct { | |
1678 | inflate_huft *tree; /* pointer into tree */ | |
1679 | uInt need; /* bits needed */ | |
1680 | } code; /* if LEN or DIST, where in tree */ | |
1681 | uInt lit; /* if LIT, literal */ | |
1682 | struct { | |
1683 | uInt get; /* bits to get for extra */ | |
1684 | uInt dist; /* distance back to copy from */ | |
1685 | } copy; /* if EXT or COPY, where and how much */ | |
1686 | } sub; /* submode */ | |
1687 | ||
1688 | /* mode independent information */ | |
1689 | Byte lbits; /* ltree bits decoded per branch */ | |
1690 | Byte dbits; /* dtree bits decoder per branch */ | |
1691 | inflate_huft *ltree; /* literal/length/eob tree */ | |
1692 | inflate_huft *dtree; /* distance tree */ | |
1693 | ||
1694 | }; | |
1695 | ||
1696 | ||
1697 | local inflate_codes_statef *inflate_codes_new( | |
1698 | uInt bl, | |
1699 | uInt bd, | |
1700 | inflate_huft *tl, | |
1701 | inflate_huft *td, | |
1702 | z_stream *z | |
1703 | ) | |
1704 | { | |
1705 | inflate_codes_statef *c; | |
1706 | ||
1707 | if ((c = (inflate_codes_statef *) | |
1708 | ZALLOC(z,1,sizeof(struct inflate_codes_state))) != Z_NULL) | |
1709 | { | |
1710 | c->mode = START; | |
1711 | c->lbits = (Byte)bl; | |
1712 | c->dbits = (Byte)bd; | |
1713 | c->ltree = tl; | |
1714 | c->dtree = td; | |
1715 | Tracev((stderr, "inflate: codes new\n")); | |
1716 | } | |
1717 | return c; | |
1718 | } | |
1719 | ||
1720 | ||
1721 | local int inflate_codes( | |
1722 | inflate_blocks_statef *s, | |
1723 | z_stream *z, | |
1724 | int r | |
1725 | ) | |
1726 | { | |
1727 | uInt j; /* temporary storage */ | |
1728 | inflate_huft *t; /* temporary pointer */ | |
1729 | uInt e; /* extra bits or operation */ | |
1730 | uLong b; /* bit buffer */ | |
1731 | uInt k; /* bits in bit buffer */ | |
1732 | Bytef *p; /* input data pointer */ | |
1733 | uInt n; /* bytes available there */ | |
1734 | Bytef *q; /* output window write pointer */ | |
1735 | uInt m; /* bytes to end of window or read pointer */ | |
1736 | Bytef *f; /* pointer to copy strings from */ | |
1737 | inflate_codes_statef *c = s->sub.decode.codes; /* codes state */ | |
1738 | ||
1739 | /* copy input/output information to locals (UPDATE macro restores) */ | |
1740 | LOAD | |
1741 | ||
1742 | /* process input and output based on current state */ | |
1743 | while (1) switch (c->mode) | |
1744 | { /* waiting for "i:"=input, "o:"=output, "x:"=nothing */ | |
1745 | case START: /* x: set up for LEN */ | |
1746 | #ifndef SLOW | |
1747 | if (m >= 258 && n >= 10) | |
1748 | { | |
1749 | UPDATE | |
1750 | r = inflate_fast(c->lbits, c->dbits, c->ltree, c->dtree, s, z); | |
1751 | LOAD | |
1752 | if (r != Z_OK) | |
1753 | { | |
1754 | c->mode = r == Z_STREAM_END ? WASH : BADCODE; | |
1755 | break; | |
1756 | } | |
1757 | } | |
1758 | #endif /* !SLOW */ | |
1759 | c->sub.code.need = c->lbits; | |
1760 | c->sub.code.tree = c->ltree; | |
1761 | c->mode = LEN; | |
1762 | case LEN: /* i: get length/literal/eob next */ | |
1763 | j = c->sub.code.need; | |
1764 | NEEDBITS(j) | |
1765 | t = c->sub.code.tree + ((uInt)b & inflate_mask[j]); | |
1766 | DUMPBITS(t->bits) | |
1767 | e = (uInt)(t->exop); | |
1768 | if (e == 0) /* literal */ | |
1769 | { | |
1770 | c->sub.lit = t->base; | |
1771 | Tracevv((stderr, t->base >= 0x20 && t->base < 0x7f ? | |
1772 | "inflate: literal '%c'\n" : | |
1773 | "inflate: literal 0x%02x\n", t->base)); | |
1774 | c->mode = LIT; | |
1775 | break; | |
1776 | } | |
1777 | if (e & 16) /* length */ | |
1778 | { | |
1779 | c->sub.copy.get = e & 15; | |
1780 | c->len = t->base; | |
1781 | c->mode = LENEXT; | |
1782 | break; | |
1783 | } | |
1784 | if ((e & 64) == 0) /* next table */ | |
1785 | { | |
1786 | c->sub.code.need = e; | |
1787 | c->sub.code.tree = t->next; | |
1788 | break; | |
1789 | } | |
1790 | if (e & 32) /* end of block */ | |
1791 | { | |
1792 | Tracevv((stderr, "inflate: end of block\n")); | |
1793 | c->mode = WASH; | |
1794 | break; | |
1795 | } | |
1796 | c->mode = BADCODE; /* invalid code */ | |
1797 | z->msg = "invalid literal/length code"; | |
1798 | r = Z_DATA_ERROR; | |
1799 | LEAVE | |
1800 | case LENEXT: /* i: getting length extra (have base) */ | |
1801 | j = c->sub.copy.get; | |
1802 | NEEDBITS(j) | |
1803 | c->len += (uInt)b & inflate_mask[j]; | |
1804 | DUMPBITS(j) | |
1805 | c->sub.code.need = c->dbits; | |
1806 | c->sub.code.tree = c->dtree; | |
1807 | Tracevv((stderr, "inflate: length %u\n", c->len)); | |
1808 | c->mode = DIST; | |
1809 | case DIST: /* i: get distance next */ | |
1810 | j = c->sub.code.need; | |
1811 | NEEDBITS(j) | |
1812 | t = c->sub.code.tree + ((uInt)b & inflate_mask[j]); | |
1813 | DUMPBITS(t->bits) | |
1814 | e = (uInt)(t->exop); | |
1815 | if (e & 16) /* distance */ | |
1816 | { | |
1817 | c->sub.copy.get = e & 15; | |
1818 | c->sub.copy.dist = t->base; | |
1819 | c->mode = DISTEXT; | |
1820 | break; | |
1821 | } | |
1822 | if ((e & 64) == 0) /* next table */ | |
1823 | { | |
1824 | c->sub.code.need = e; | |
1825 | c->sub.code.tree = t->next; | |
1826 | break; | |
1827 | } | |
1828 | c->mode = BADCODE; /* invalid code */ | |
1829 | z->msg = "invalid distance code"; | |
1830 | r = Z_DATA_ERROR; | |
1831 | LEAVE | |
1832 | case DISTEXT: /* i: getting distance extra */ | |
1833 | j = c->sub.copy.get; | |
1834 | NEEDBITS(j) | |
1835 | c->sub.copy.dist += (uInt)b & inflate_mask[j]; | |
1836 | DUMPBITS(j) | |
1837 | Tracevv((stderr, "inflate: distance %u\n", c->sub.copy.dist)); | |
1838 | c->mode = COPY; | |
1839 | case COPY: /* o: copying bytes in window, waiting for space */ | |
1840 | #ifndef __TURBOC__ /* Turbo C bug for following expression */ | |
1841 | f = (uInt)(q - s->window) < c->sub.copy.dist ? | |
1842 | s->end - (c->sub.copy.dist - (q - s->window)) : | |
1843 | q - c->sub.copy.dist; | |
1844 | #else | |
1845 | f = q - c->sub.copy.dist; | |
1846 | if ((uInt)(q - s->window) < c->sub.copy.dist) | |
1847 | f = s->end - (c->sub.copy.dist - (q - s->window)); | |
1848 | #endif | |
1849 | while (c->len) | |
1850 | { | |
1851 | NEEDOUT | |
1852 | OUTBYTE(*f++) | |
1853 | if (f == s->end) | |
1854 | f = s->window; | |
1855 | c->len--; | |
1856 | } | |
1857 | c->mode = START; | |
1858 | break; | |
1859 | case LIT: /* o: got literal, waiting for output space */ | |
1860 | NEEDOUT | |
1861 | OUTBYTE(c->sub.lit) | |
1862 | c->mode = START; | |
1863 | break; | |
1864 | case WASH: /* o: got eob, possibly more output */ | |
1865 | FLUSH | |
1866 | if (s->read != s->write) | |
1867 | LEAVE | |
1868 | c->mode = END; | |
1869 | case END: | |
1870 | r = Z_STREAM_END; | |
1871 | LEAVE | |
1872 | case BADCODE: /* x: got error */ | |
1873 | r = Z_DATA_ERROR; | |
1874 | LEAVE | |
1875 | default: | |
1876 | r = Z_STREAM_ERROR; | |
1877 | LEAVE | |
1878 | } | |
1879 | } | |
1880 | ||
1881 | ||
1882 | local void inflate_codes_free( | |
1883 | inflate_codes_statef *c, | |
1884 | z_stream *z | |
1885 | ) | |
1886 | { | |
1887 | ZFREE(z, c, sizeof(struct inflate_codes_state)); | |
1888 | Tracev((stderr, "inflate: codes free\n")); | |
1889 | } | |
1890 | ||
1891 | /*+++++*/ | |
1892 | /* inflate_util.c -- data and routines common to blocks and codes | |
1893 | * Copyright (C) 1995 Mark Adler | |
1894 | * For conditions of distribution and use, see copyright notice in zlib.h | |
1895 | */ | |
1896 | ||
1897 | /* copy as much as possible from the sliding window to the output area */ | |
1898 | local int inflate_flush( | |
1899 | inflate_blocks_statef *s, | |
1900 | z_stream *z, | |
1901 | int r | |
1902 | ) | |
1903 | { | |
1904 | uInt n; | |
1905 | Bytef *p, *q; | |
1906 | ||
1907 | /* local copies of source and destination pointers */ | |
1908 | p = z->next_out; | |
1909 | q = s->read; | |
1910 | ||
1911 | /* compute number of bytes to copy as far as end of window */ | |
1912 | n = (uInt)((q <= s->write ? s->write : s->end) - q); | |
1913 | if (n > z->avail_out) n = z->avail_out; | |
1914 | if (n && r == Z_BUF_ERROR) r = Z_OK; | |
1915 | ||
1916 | /* update counters */ | |
1917 | z->avail_out -= n; | |
1918 | z->total_out += n; | |
1919 | ||
1920 | /* update check information */ | |
1921 | if (s->checkfn != Z_NULL) | |
1922 | s->check = (*s->checkfn)(s->check, q, n); | |
1923 | ||
1924 | /* copy as far as end of window */ | |
1925 | zmemcpy(p, q, n); | |
1926 | p += n; | |
1927 | q += n; | |
1928 | ||
1929 | /* see if more to copy at beginning of window */ | |
1930 | if (q == s->end) | |
1931 | { | |
1932 | /* wrap pointers */ | |
1933 | q = s->window; | |
1934 | if (s->write == s->end) | |
1935 | s->write = s->window; | |
1936 | ||
1937 | /* compute bytes to copy */ | |
1938 | n = (uInt)(s->write - q); | |
1939 | if (n > z->avail_out) n = z->avail_out; | |
1940 | if (n && r == Z_BUF_ERROR) r = Z_OK; | |
1941 | ||
1942 | /* update counters */ | |
1943 | z->avail_out -= n; | |
1944 | z->total_out += n; | |
1945 | ||
1946 | /* update check information */ | |
1947 | if (s->checkfn != Z_NULL) | |
1948 | s->check = (*s->checkfn)(s->check, q, n); | |
1949 | ||
1950 | /* copy */ | |
1951 | zmemcpy(p, q, n); | |
1952 | p += n; | |
1953 | q += n; | |
1954 | } | |
1955 | ||
1956 | /* update pointers */ | |
1957 | z->next_out = p; | |
1958 | s->read = q; | |
1959 | ||
1960 | /* done */ | |
1961 | return r; | |
1962 | } | |
1963 | ||
1964 | ||
1965 | /*+++++*/ | |
1966 | /* inffast.c -- process literals and length/distance pairs fast | |
1967 | * Copyright (C) 1995 Mark Adler | |
1968 | * For conditions of distribution and use, see copyright notice in zlib.h | |
1969 | */ | |
1970 | ||
1971 | /* simplify the use of the inflate_huft type with some defines */ | |
1972 | #define base more.Base | |
1973 | #define next more.Next | |
1974 | #define exop word.what.Exop | |
1975 | #define bits word.what.Bits | |
1976 | ||
1977 | /* macros for bit input with no checking and for returning unused bytes */ | |
1978 | #define GRABBITS(j) {while(k<(j)){b|=((uLong)NEXTBYTE)<<k;k+=8;}} | |
1979 | #define UNGRAB {n+=(c=k>>3);p-=c;k&=7;} | |
1980 | ||
1981 | /* Called with number of bytes left to write in window at least 258 | |
1982 | (the maximum string length) and number of input bytes available | |
1983 | at least ten. The ten bytes are six bytes for the longest length/ | |
1984 | distance pair plus four bytes for overloading the bit buffer. */ | |
1985 | ||
1986 | local int inflate_fast( | |
1987 | uInt bl, | |
1988 | uInt bd, | |
1989 | inflate_huft *tl, | |
1990 | inflate_huft *td, | |
1991 | inflate_blocks_statef *s, | |
1992 | z_stream *z | |
1993 | ) | |
1994 | { | |
1995 | inflate_huft *t; /* temporary pointer */ | |
1996 | uInt e; /* extra bits or operation */ | |
1997 | uLong b; /* bit buffer */ | |
1998 | uInt k; /* bits in bit buffer */ | |
1999 | Bytef *p; /* input data pointer */ | |
2000 | uInt n; /* bytes available there */ | |
2001 | Bytef *q; /* output window write pointer */ | |
2002 | uInt m; /* bytes to end of window or read pointer */ | |
2003 | uInt ml; /* mask for literal/length tree */ | |
2004 | uInt md; /* mask for distance tree */ | |
2005 | uInt c; /* bytes to copy */ | |
2006 | uInt d; /* distance back to copy from */ | |
2007 | Bytef *r; /* copy source pointer */ | |
2008 | ||
2009 | /* load input, output, bit values */ | |
2010 | LOAD | |
2011 | ||
2012 | /* initialize masks */ | |
2013 | ml = inflate_mask[bl]; | |
2014 | md = inflate_mask[bd]; | |
2015 | ||
2016 | /* do until not enough input or output space for fast loop */ | |
2017 | do { /* assume called with m >= 258 && n >= 10 */ | |
2018 | /* get literal/length code */ | |
2019 | GRABBITS(20) /* max bits for literal/length code */ | |
2020 | if ((e = (t = tl + ((uInt)b & ml))->exop) == 0) | |
2021 | { | |
2022 | DUMPBITS(t->bits) | |
2023 | Tracevv((stderr, t->base >= 0x20 && t->base < 0x7f ? | |
2024 | "inflate: * literal '%c'\n" : | |
2025 | "inflate: * literal 0x%02x\n", t->base)); | |
2026 | *q++ = (Byte)t->base; | |
2027 | m--; | |
2028 | continue; | |
2029 | } | |
2030 | do { | |
2031 | DUMPBITS(t->bits) | |
2032 | if (e & 16) | |
2033 | { | |
2034 | /* get extra bits for length */ | |
2035 | e &= 15; | |
2036 | c = t->base + ((uInt)b & inflate_mask[e]); | |
2037 | DUMPBITS(e) | |
2038 | Tracevv((stderr, "inflate: * length %u\n", c)); | |
2039 | ||
2040 | /* decode distance base of block to copy */ | |
2041 | GRABBITS(15); /* max bits for distance code */ | |
2042 | e = (t = td + ((uInt)b & md))->exop; | |
2043 | do { | |
2044 | DUMPBITS(t->bits) | |
2045 | if (e & 16) | |
2046 | { | |
2047 | /* get extra bits to add to distance base */ | |
2048 | e &= 15; | |
2049 | GRABBITS(e) /* get extra bits (up to 13) */ | |
2050 | d = t->base + ((uInt)b & inflate_mask[e]); | |
2051 | DUMPBITS(e) | |
2052 | Tracevv((stderr, "inflate: * distance %u\n", d)); | |
2053 | ||
2054 | /* do the copy */ | |
2055 | m -= c; | |
2056 | if ((uInt)(q - s->window) >= d) /* offset before dest */ | |
2057 | { /* just copy */ | |
2058 | r = q - d; | |
2059 | *q++ = *r++; c--; /* minimum count is three, */ | |
2060 | *q++ = *r++; c--; /* so unroll loop a little */ | |
2061 | } | |
2062 | else /* else offset after destination */ | |
2063 | { | |
2064 | e = d - (q - s->window); /* bytes from offset to end */ | |
2065 | r = s->end - e; /* pointer to offset */ | |
2066 | if (c > e) /* if source crosses, */ | |
2067 | { | |
2068 | c -= e; /* copy to end of window */ | |
2069 | do { | |
2070 | *q++ = *r++; | |
2071 | } while (--e); | |
2072 | r = s->window; /* copy rest from start of window */ | |
2073 | } | |
2074 | } | |
2075 | do { /* copy all or what's left */ | |
2076 | *q++ = *r++; | |
2077 | } while (--c); | |
2078 | break; | |
2079 | } | |
2080 | else if ((e & 64) == 0) | |
2081 | e = (t = t->next + ((uInt)b & inflate_mask[e]))->exop; | |
2082 | else | |
2083 | { | |
2084 | z->msg = "invalid distance code"; | |
2085 | UNGRAB | |
2086 | UPDATE | |
2087 | return Z_DATA_ERROR; | |
2088 | } | |
2089 | } while (1); | |
2090 | break; | |
2091 | } | |
2092 | if ((e & 64) == 0) | |
2093 | { | |
2094 | if ((e = (t = t->next + ((uInt)b & inflate_mask[e]))->exop) == 0) | |
2095 | { | |
2096 | DUMPBITS(t->bits) | |
2097 | Tracevv((stderr, t->base >= 0x20 && t->base < 0x7f ? | |
2098 | "inflate: * literal '%c'\n" : | |
2099 | "inflate: * literal 0x%02x\n", t->base)); | |
2100 | *q++ = (Byte)t->base; | |
2101 | m--; | |
2102 | break; | |
2103 | } | |
2104 | } | |
2105 | else if (e & 32) | |
2106 | { | |
2107 | Tracevv((stderr, "inflate: * end of block\n")); | |
2108 | UNGRAB | |
2109 | UPDATE | |
2110 | return Z_STREAM_END; | |
2111 | } | |
2112 | else | |
2113 | { | |
2114 | z->msg = "invalid literal/length code"; | |
2115 | UNGRAB | |
2116 | UPDATE | |
2117 | return Z_DATA_ERROR; | |
2118 | } | |
2119 | } while (1); | |
2120 | } while (m >= 258 && n >= 10); | |
2121 | ||
2122 | /* not enough input or output--restore pointers and return */ | |
2123 | UNGRAB | |
2124 | UPDATE | |
2125 | return Z_OK; | |
2126 | } | |
2127 | ||
2128 | ||
2129 | /*+++++*/ | |
2130 | /* zutil.c -- target dependent utility functions for the compression library | |
2131 | * Copyright (C) 1995 Jean-loup Gailly. | |
2132 | * For conditions of distribution and use, see copyright notice in zlib.h | |
2133 | */ | |
2134 | ||
2135 | /* From: zutil.c,v 1.8 1995/05/03 17:27:12 jloup Exp */ | |
2136 | ||
2137 | char *zlib_version = ZLIB_VERSION; | |
2138 | ||
2139 | char *z_errmsg[] = { | |
2140 | "stream end", /* Z_STREAM_END 1 */ | |
2141 | "", /* Z_OK 0 */ | |
2142 | "file error", /* Z_ERRNO (-1) */ | |
2143 | "stream error", /* Z_STREAM_ERROR (-2) */ | |
2144 | "data error", /* Z_DATA_ERROR (-3) */ | |
2145 | "insufficient memory", /* Z_MEM_ERROR (-4) */ | |
2146 | "buffer error", /* Z_BUF_ERROR (-5) */ | |
2147 | ""}; | |
2148 | ||
2149 | ||
2150 | /*+++++*/ | |
2151 | /* adler32.c -- compute the Adler-32 checksum of a data stream | |
2152 | * Copyright (C) 1995 Mark Adler | |
2153 | * For conditions of distribution and use, see copyright notice in zlib.h | |
2154 | */ | |
2155 | ||
2156 | /* From: adler32.c,v 1.6 1995/05/03 17:27:08 jloup Exp */ | |
2157 | ||
2158 | #define BASE 65521L /* largest prime smaller than 65536 */ | |
2159 | #define NMAX 5552 | |
2160 | /* NMAX is the largest n such that 255n(n+1)/2 + (n+1)(BASE-1) <= 2^32-1 */ | |
2161 | ||
2162 | #define DO1(buf) {s1 += *buf++; s2 += s1;} | |
2163 | #define DO2(buf) DO1(buf); DO1(buf); | |
2164 | #define DO4(buf) DO2(buf); DO2(buf); | |
2165 | #define DO8(buf) DO4(buf); DO4(buf); | |
2166 | #define DO16(buf) DO8(buf); DO8(buf); | |
2167 | ||
2168 | /* ========================================================================= */ | |
2169 | uLong adler32( | |
2170 | uLong adler, | |
2171 | Bytef *buf, | |
2172 | uInt len | |
2173 | ) | |
2174 | { | |
2175 | unsigned long s1 = adler & 0xffff; | |
2176 | unsigned long s2 = (adler >> 16) & 0xffff; | |
2177 | int k; | |
2178 | ||
2179 | if (buf == Z_NULL) return 1L; | |
2180 | ||
2181 | while (len > 0) { | |
2182 | k = len < NMAX ? len : NMAX; | |
2183 | len -= k; | |
2184 | while (k >= 16) { | |
2185 | DO16(buf); | |
2186 | k -= 16; | |
2187 | } | |
2188 | if (k != 0) do { | |
2189 | DO1(buf); | |
2190 | } while (--k); | |
2191 | s1 %= BASE; | |
2192 | s2 %= BASE; | |
2193 | } | |
2194 | return (s2 << 16) | s1; | |
2195 | } |