2 * BK Id: SCCS/s.zlib.c 1.13 03/21/02 14:35:03 trini
5 * This file is derived from various .h and .c files from the zlib-0.95
6 * distribution by Jean-loup Gailly and Mark Adler, with some additions
7 * by Paul Mackerras to aid in implementing Deflate compression and
8 * decompression for PPP packets. See zlib.h for conditions of
9 * distribution and use.
11 * Changes that have been made include:
12 * - changed functions not used outside this file to "local"
13 * - added minCompression parameter to deflateInit2
14 * - added Z_PACKET_FLUSH (see zlib.h for details)
15 * - added inflateIncomp
20 /* zutil.h -- internal interface and configuration of the compression library
21 * Copyright (C) 1995 Jean-loup Gailly.
22 * For conditions of distribution and use, see copyright notice in zlib.h
25 /* WARNING: this file should *not* be used by applications. It is
26 part of the implementation of the compression library and is
27 subject to change. Applications should only use zlib.h.
30 /* From: zutil.h,v 1.9 1995/05/03 17:27:12 jloup Exp */
39 /* compile with -Dlocal if your debugger can't find static symbols */
43 typedef unsigned char uch;
45 typedef unsigned short ush;
47 typedef unsigned long ulg;
49 extern char *z_errmsg[]; /* indexed by 1-zlib_error */
51 #define ERR_RETURN(strm,err) return (strm->msg=z_errmsg[1-err], err)
52 /* To be used only when the state is known to be valid */
55 #define NULL ((void *) 0)
58 /* common constants */
63 # define DEF_WBITS MAX_WBITS
65 /* default windowBits for decompression. MAX_WBITS is for compression only */
67 #if MAX_MEM_LEVEL >= 8
68 # define DEF_MEM_LEVEL 8
70 # define DEF_MEM_LEVEL MAX_MEM_LEVEL
72 /* default memLevel */
74 #define STORED_BLOCK 0
75 #define STATIC_TREES 1
77 /* The three kinds of block type */
81 /* The minimum and maximum match lengths */
85 #include <linux/string.h>
86 #define zmemcpy memcpy
87 #define zmemzero(dest, len) memset(dest, 0, len)
89 /* Diagnostic functions */
95 # define Assert(cond,msg) {if(!(cond)) z_error(msg);}
96 # define Trace(x) fprintf x
97 # define Tracev(x) {if (verbose) fprintf x ;}
98 # define Tracevv(x) {if (verbose>1) fprintf x ;}
99 # define Tracec(c,x) {if (verbose && (c)) fprintf x ;}
100 # define Tracecv(c,x) {if (verbose>1 && (c)) fprintf x ;}
102 # define Assert(cond,msg)
107 # define Tracecv(c,x)
111 typedef uLong (*check_func) OF((uLong check, Bytef *buf, uInt len));
113 /* voidpf zcalloc OF((voidpf opaque, unsigned items, unsigned size)); */
114 /* void zcfree OF((voidpf opaque, voidpf ptr)); */
116 #define ZALLOC(strm, items, size) \
117 (*((strm)->zalloc))((strm)->opaque, (items), (size))
118 #define ZFREE(strm, addr, size) \
119 (*((strm)->zfree))((strm)->opaque, (voidpf)(addr), (size))
120 #define TRY_FREE(s, p, n) {if (p) ZFREE(s, p, n);}
122 /* deflate.h -- internal compression state
123 * Copyright (C) 1995 Jean-loup Gailly
124 * For conditions of distribution and use, see copyright notice in zlib.h
127 /* WARNING: this file should *not* be used by applications. It is
128 part of the implementation of the compression library and is
129 subject to change. Applications should only use zlib.h.
133 /* infblock.h -- header to use infblock.c
134 * Copyright (C) 1995 Mark Adler
135 * For conditions of distribution and use, see copyright notice in zlib.h
138 /* WARNING: this file should *not* be used by applications. It is
139 part of the implementation of the compression library and is
140 subject to change. Applications should only use zlib.h.
143 struct inflate_blocks_state;
144 typedef struct inflate_blocks_state FAR inflate_blocks_statef;
146 local inflate_blocks_statef * inflate_blocks_new OF((
148 check_func c, /* check function */
149 uInt w)); /* window size */
151 local int inflate_blocks OF((
152 inflate_blocks_statef *,
154 int)); /* initial return code */
156 local void inflate_blocks_reset OF((
157 inflate_blocks_statef *,
159 uLongf *)); /* check value on output */
161 local int inflate_blocks_free OF((
162 inflate_blocks_statef *,
164 uLongf *)); /* check value on output */
166 local int inflate_addhistory OF((
167 inflate_blocks_statef *,
170 local int inflate_packet_flush OF((
171 inflate_blocks_statef *));
174 /* inftrees.h -- header to use inftrees.c
175 * Copyright (C) 1995 Mark Adler
176 * For conditions of distribution and use, see copyright notice in zlib.h
179 /* WARNING: this file should *not* be used by applications. It is
180 part of the implementation of the compression library and is
181 subject to change. Applications should only use zlib.h.
184 /* Huffman code lookup table entry--this entry is four bytes for machines
185 that have 16-bit pointers (e.g. PC's in the small or medium model). */
187 typedef struct inflate_huft_s FAR inflate_huft;
189 struct inflate_huft_s {
192 Byte Exop; /* number of extra bits or operation */
193 Byte Bits; /* number of bits in this code or subcode */
195 uInt Nalloc; /* number of these allocated here */
196 Bytef *pad; /* pad structure to a power of 2 (4 bytes for */
197 } word; /* 16-bit, 8 bytes for 32-bit machines) */
199 uInt Base; /* literal, length base, or distance base */
200 inflate_huft *Next; /* pointer to next level of table */
205 local uInt inflate_hufts;
208 local int inflate_trees_bits OF((
209 uIntf *, /* 19 code lengths */
210 uIntf *, /* bits tree desired/actual depth */
211 inflate_huft * FAR *, /* bits tree result */
212 z_stream *)); /* for zalloc, zfree functions */
214 local int inflate_trees_dynamic OF((
215 uInt, /* number of literal/length codes */
216 uInt, /* number of distance codes */
217 uIntf *, /* that many (total) code lengths */
218 uIntf *, /* literal desired/actual bit depth */
219 uIntf *, /* distance desired/actual bit depth */
220 inflate_huft * FAR *, /* literal/length tree result */
221 inflate_huft * FAR *, /* distance tree result */
222 z_stream *)); /* for zalloc, zfree functions */
224 local int inflate_trees_fixed OF((
225 uIntf *, /* literal desired/actual bit depth */
226 uIntf *, /* distance desired/actual bit depth */
227 inflate_huft * FAR *, /* literal/length tree result */
228 inflate_huft * FAR *)); /* distance tree result */
230 local int inflate_trees_free OF((
231 inflate_huft *, /* tables to free */
232 z_stream *)); /* for zfree function */
236 /* infcodes.h -- header to use infcodes.c
237 * Copyright (C) 1995 Mark Adler
238 * For conditions of distribution and use, see copyright notice in zlib.h
241 /* WARNING: this file should *not* be used by applications. It is
242 part of the implementation of the compression library and is
243 subject to change. Applications should only use zlib.h.
246 struct inflate_codes_state;
247 typedef struct inflate_codes_state FAR inflate_codes_statef;
249 local inflate_codes_statef *inflate_codes_new OF((
251 inflate_huft *, inflate_huft *,
254 local int inflate_codes OF((
255 inflate_blocks_statef *,
259 local void inflate_codes_free OF((
260 inflate_codes_statef *,
265 /* inflate.c -- zlib interface to inflate modules
266 * Copyright (C) 1995 Mark Adler
267 * For conditions of distribution and use, see copyright notice in zlib.h
270 /* inflate private state */
271 struct internal_state {
275 METHOD, /* waiting for method byte */
276 FLAG, /* waiting for flag byte */
277 BLOCKS, /* decompressing blocks */
278 CHECK4, /* four check bytes to go */
279 CHECK3, /* three check bytes to go */
280 CHECK2, /* two check bytes to go */
281 CHECK1, /* one check byte to go */
282 DONE, /* finished check, done */
283 BAD} /* got an error--stay here */
284 mode; /* current inflate mode */
286 /* mode dependent information */
288 uInt method; /* if FLAGS, method byte */
290 uLong was; /* computed check value */
291 uLong need; /* stream check value */
292 } check; /* if CHECK, check values to compare */
293 uInt marker; /* if BAD, inflateSync's marker bytes count */
296 /* mode independent information */
297 int nowrap; /* flag for no wrapper */
298 uInt wbits; /* log2(window size) (8..15, defaults to 15) */
299 inflate_blocks_statef
300 *blocks; /* current inflate_blocks state */
310 if (z == Z_NULL || z->state == Z_NULL)
311 return Z_STREAM_ERROR;
312 z->total_in = z->total_out = 0;
314 z->state->mode = z->state->nowrap ? BLOCKS : METHOD;
315 inflate_blocks_reset(z->state->blocks, z, &c);
316 Trace((stderr, "inflate: reset\n"));
326 if (z == Z_NULL || z->state == Z_NULL || z->zfree == Z_NULL)
327 return Z_STREAM_ERROR;
328 if (z->state->blocks != Z_NULL)
329 inflate_blocks_free(z->state->blocks, z, &c);
330 ZFREE(z, z->state, sizeof(struct internal_state));
332 Trace((stderr, "inflate: end\n"));
337 int inflateInit2(z, w)
341 /* initialize state */
343 return Z_STREAM_ERROR;
344 /* if (z->zalloc == Z_NULL) z->zalloc = zcalloc; */
345 /* if (z->zfree == Z_NULL) z->zfree = zcfree; */
346 if ((z->state = (struct internal_state FAR *)
347 ZALLOC(z,1,sizeof(struct internal_state))) == Z_NULL)
349 z->state->blocks = Z_NULL;
351 /* handle undocumented nowrap option (no zlib header or check) */
352 z->state->nowrap = 0;
356 z->state->nowrap = 1;
359 /* set window size */
363 return Z_STREAM_ERROR;
365 z->state->wbits = (uInt)w;
367 /* create inflate_blocks state */
368 if ((z->state->blocks =
369 inflate_blocks_new(z, z->state->nowrap ? Z_NULL : adler32, 1 << w))
375 Trace((stderr, "inflate: allocated\n"));
386 return inflateInit2(z, DEF_WBITS);
390 #define NEEDBYTE {if(z->avail_in==0)goto empty;r=Z_OK;}
391 #define NEXTBYTE (z->avail_in--,z->total_in++,*z->next_in++)
400 if (z == Z_NULL || z->next_in == Z_NULL)
401 return Z_STREAM_ERROR;
403 while (1) switch (z->state->mode)
407 if (((z->state->sub.method = NEXTBYTE) & 0xf) != DEFLATED)
409 z->state->mode = BAD;
410 z->msg = "unknown compression method";
411 z->state->sub.marker = 5; /* can't try inflateSync */
414 if ((z->state->sub.method >> 4) + 8 > z->state->wbits)
416 z->state->mode = BAD;
417 z->msg = "invalid window size";
418 z->state->sub.marker = 5; /* can't try inflateSync */
421 z->state->mode = FLAG;
424 if ((b = NEXTBYTE) & 0x20)
426 z->state->mode = BAD;
427 z->msg = "invalid reserved bit";
428 z->state->sub.marker = 5; /* can't try inflateSync */
431 if (((z->state->sub.method << 8) + b) % 31)
433 z->state->mode = BAD;
434 z->msg = "incorrect header check";
435 z->state->sub.marker = 5; /* can't try inflateSync */
438 Trace((stderr, "inflate: zlib header ok\n"));
439 z->state->mode = BLOCKS;
441 r = inflate_blocks(z->state->blocks, z, r);
442 if (f == Z_PACKET_FLUSH && z->avail_in == 0 && z->avail_out != 0)
443 r = inflate_packet_flush(z->state->blocks);
444 if (r == Z_DATA_ERROR)
446 z->state->mode = BAD;
447 z->state->sub.marker = 0; /* can try inflateSync */
450 if (r != Z_STREAM_END)
453 inflate_blocks_reset(z->state->blocks, z, &z->state->sub.check.was);
454 if (z->state->nowrap)
456 z->state->mode = DONE;
459 z->state->mode = CHECK4;
462 z->state->sub.check.need = (uLong)NEXTBYTE << 24;
463 z->state->mode = CHECK3;
466 z->state->sub.check.need += (uLong)NEXTBYTE << 16;
467 z->state->mode = CHECK2;
470 z->state->sub.check.need += (uLong)NEXTBYTE << 8;
471 z->state->mode = CHECK1;
474 z->state->sub.check.need += (uLong)NEXTBYTE;
476 if (z->state->sub.check.was != z->state->sub.check.need)
478 z->state->mode = BAD;
479 z->msg = "incorrect data check";
480 z->state->sub.marker = 5; /* can't try inflateSync */
483 Trace((stderr, "inflate: zlib check ok\n"));
484 z->state->mode = DONE;
490 return Z_STREAM_ERROR;
494 if (f != Z_PACKET_FLUSH)
496 z->state->mode = BAD;
497 z->state->sub.marker = 0; /* can try inflateSync */
502 * This subroutine adds the data at next_in/avail_in to the output history
503 * without performing any output. The output buffer must be "caught up";
504 * i.e. no pending output (hence s->read equals s->write), and the state must
505 * be BLOCKS (i.e. we should be willing to see the start of a series of
506 * BLOCKS). On exit, the output will also be caught up, and the checksum
507 * will have been updated if need be.
513 if (z->state->mode != BLOCKS)
515 return inflate_addhistory(z->state->blocks, z);
522 uInt n; /* number of bytes to look at */
523 Bytef *p; /* pointer to bytes */
524 uInt m; /* number of marker bytes found in a row */
525 uLong r, w; /* temporaries to save total_in and total_out */
528 if (z == Z_NULL || z->state == Z_NULL)
529 return Z_STREAM_ERROR;
530 if (z->state->mode != BAD)
532 z->state->mode = BAD;
533 z->state->sub.marker = 0;
535 if ((n = z->avail_in) == 0)
538 m = z->state->sub.marker;
543 if (*p == (Byte)(m < 2 ? 0 : 0xff))
553 z->total_in += p - z->next_in;
556 z->state->sub.marker = m;
558 /* return no joy or set up to restart on a new block */
561 r = z->total_in; w = z->total_out;
563 z->total_in = r; z->total_out = w;
564 z->state->mode = BLOCKS;
572 /* infutil.h -- types and macros common to blocks and codes
573 * Copyright (C) 1995 Mark Adler
574 * For conditions of distribution and use, see copyright notice in zlib.h
577 /* WARNING: this file should *not* be used by applications. It is
578 part of the implementation of the compression library and is
579 subject to change. Applications should only use zlib.h.
582 /* inflate blocks semi-private state */
583 struct inflate_blocks_state {
587 TYPE, /* get type bits (3, including end bit) */
588 LENS, /* get lengths for stored */
589 STORED, /* processing stored block */
590 TABLE, /* get table lengths */
591 BTREE, /* get bit lengths tree for a dynamic block */
592 DTREE, /* get length, distance trees for a dynamic block */
593 CODES, /* processing fixed or dynamic block */
594 DRY, /* output remaining window bytes */
595 DONEB, /* finished last block, done */
596 BADB} /* got a data error--stuck here */
597 mode; /* current inflate_block mode */
599 /* mode dependent information */
601 uInt left; /* if STORED, bytes left to copy */
603 uInt table; /* table lengths (14 bits) */
604 uInt index; /* index into blens (or border) */
605 uIntf *blens; /* bit lengths of codes */
606 uInt bb; /* bit length tree depth */
607 inflate_huft *tb; /* bit length decoding tree */
608 int nblens; /* # elements allocated at blens */
609 } trees; /* if DTREE, decoding info for trees */
611 inflate_huft *tl, *td; /* trees to free */
614 } decode; /* if CODES, current state */
616 uInt last; /* true if this block is the last block */
618 /* mode independent information */
619 uInt bitk; /* bits in bit buffer */
620 uLong bitb; /* bit buffer */
621 Bytef *window; /* sliding window */
622 Bytef *end; /* one byte after sliding window */
623 Bytef *read; /* window read pointer */
624 Bytef *write; /* window write pointer */
625 check_func checkfn; /* check function */
626 uLong check; /* check on output */
631 /* defines for inflate input/output */
632 /* update pointers and return */
633 #define UPDBITS {s->bitb=b;s->bitk=k;}
634 #define UPDIN {z->avail_in=n;z->total_in+=p-z->next_in;z->next_in=p;}
635 #define UPDOUT {s->write=q;}
636 #define UPDATE {UPDBITS UPDIN UPDOUT}
637 #define LEAVE {UPDATE return inflate_flush(s,z,r);}
638 /* get bytes and bits */
639 #define LOADIN {p=z->next_in;n=z->avail_in;b=s->bitb;k=s->bitk;}
640 #define NEEDBYTE {if(n)r=Z_OK;else LEAVE}
641 #define NEXTBYTE (n--,*p++)
642 #define NEEDBITS(j) {while(k<(j)){NEEDBYTE;b|=((uLong)NEXTBYTE)<<k;k+=8;}}
643 #define DUMPBITS(j) {b>>=(j);k-=(j);}
645 #define WAVAIL (q<s->read?s->read-q-1:s->end-q)
646 #define LOADOUT {q=s->write;m=WAVAIL;}
647 #define WRAP {if(q==s->end&&s->read!=s->window){q=s->window;m=WAVAIL;}}
648 #define FLUSH {UPDOUT r=inflate_flush(s,z,r); LOADOUT}
649 #define NEEDOUT {if(m==0){WRAP if(m==0){FLUSH WRAP if(m==0) LEAVE}}r=Z_OK;}
650 #define OUTBYTE(a) {*q++=(Byte)(a);m--;}
651 /* load local pointers */
652 #define LOAD {LOADIN LOADOUT}
654 /* And'ing with mask[n] masks the lower n bits */
655 local uInt inflate_mask[] = {
657 0x0001, 0x0003, 0x0007, 0x000f, 0x001f, 0x003f, 0x007f, 0x00ff,
658 0x01ff, 0x03ff, 0x07ff, 0x0fff, 0x1fff, 0x3fff, 0x7fff, 0xffff
661 /* copy as much as possible from the sliding window to the output area */
662 local int inflate_flush OF((
663 inflate_blocks_statef *,
668 /* inffast.h -- header to use inffast.c
669 * Copyright (C) 1995 Mark Adler
670 * For conditions of distribution and use, see copyright notice in zlib.h
673 /* WARNING: this file should *not* be used by applications. It is
674 part of the implementation of the compression library and is
675 subject to change. Applications should only use zlib.h.
678 local int inflate_fast OF((
683 inflate_blocks_statef *,
688 /* infblock.c -- interpret and process block types to last block
689 * Copyright (C) 1995 Mark Adler
690 * For conditions of distribution and use, see copyright notice in zlib.h
693 /* Table for deflate from PKZIP's appnote.txt. */
694 local uInt border[] = { /* Order of the bit length code lengths */
695 16, 17, 18, 0, 8, 7, 9, 6, 10, 5, 11, 4, 12, 3, 13, 2, 14, 1, 15};
698 Notes beyond the 1.93a appnote.txt:
700 1. Distance pointers never point before the beginning of the output
702 2. Distance pointers can point back across blocks, up to 32k away.
703 3. There is an implied maximum of 7 bits for the bit length table and
704 15 bits for the actual data.
705 4. If only one code exists, then it is encoded using one bit. (Zero
706 would be more efficient, but perhaps a little confusing.) If two
707 codes exist, they are coded using one bit each (0 and 1).
708 5. There is no way of sending zero distance codes--a dummy must be
709 sent if there are none. (History: a pre 2.0 version of PKZIP would
710 store blocks with no distance codes, but this was discovered to be
711 too harsh a criterion.) Valid only for 1.93a. 2.04c does allow
712 zero distance codes, which is sent as one code of zero bits in
714 6. There are up to 286 literal/length codes. Code 256 represents the
715 end-of-block. Note however that the static length tree defines
716 288 codes just to fill out the Huffman codes. Codes 286 and 287
717 cannot be used though, since there is no length base or extra bits
718 defined for them. Similarily, there are up to 30 distance codes.
719 However, static trees define 32 codes (all 5 bits) to fill out the
720 Huffman codes, but the last two had better not show up in the data.
721 7. Unzip can check dynamic Huffman blocks for complete code sets.
722 The exception is that a single code would not be complete (see #4).
723 8. The five bits following the block type is really the number of
724 literal codes sent minus 257.
725 9. Length codes 8,16,16 are interpreted as 13 length codes of 8 bits
726 (1+6+6). Therefore, to output three times the length, you output
727 three codes (1+1+1), whereas to output four times the same length,
728 you only need two codes (1+3). Hmm.
729 10. In the tree reconstruction algorithm, Code = Code + Increment
730 only if BitLength(i) is not zero. (Pretty obvious.)
731 11. Correction: 4 Bits: # of Bit Length codes - 4 (4 - 19)
732 12. Note: length code 284 can represent 227-258, but length code 285
733 really is 258. The last length deserves its own, short code
734 since it gets used a lot in very redundant files. The length
735 258 is special since 258 - 3 (the min match length) is 255.
736 13. The literal/length and distance code bit lengths are read as a
737 single stream of lengths. It is possible (and advantageous) for
738 a repeat code (16, 17, or 18) to go across the boundary between
739 the two sets of lengths.
743 local void inflate_blocks_reset(s, z, c)
744 inflate_blocks_statef *s;
748 if (s->checkfn != Z_NULL)
750 if (s->mode == BTREE || s->mode == DTREE)
751 ZFREE(z, s->sub.trees.blens, s->sub.trees.nblens * sizeof(uInt));
752 if (s->mode == CODES)
754 inflate_codes_free(s->sub.decode.codes, z);
755 inflate_trees_free(s->sub.decode.td, z);
756 inflate_trees_free(s->sub.decode.tl, z);
761 s->read = s->write = s->window;
762 if (s->checkfn != Z_NULL)
763 s->check = (*s->checkfn)(0L, Z_NULL, 0);
764 Trace((stderr, "inflate: blocks reset\n"));
768 local inflate_blocks_statef *inflate_blocks_new(z, c, w)
773 inflate_blocks_statef *s;
775 if ((s = (inflate_blocks_statef *)ZALLOC
776 (z,1,sizeof(struct inflate_blocks_state))) == Z_NULL)
778 if ((s->window = (Bytef *)ZALLOC(z, 1, w)) == Z_NULL)
780 ZFREE(z, s, sizeof(struct inflate_blocks_state));
783 s->end = s->window + w;
786 Trace((stderr, "inflate: blocks allocated\n"));
787 inflate_blocks_reset(s, z, &s->check);
792 local int inflate_blocks(s, z, r)
793 inflate_blocks_statef *s;
797 uInt t; /* temporary storage */
798 uLong b; /* bit buffer */
799 uInt k; /* bits in bit buffer */
800 Bytef *p; /* input data pointer */
801 uInt n; /* bytes available there */
802 Bytef *q; /* output window write pointer */
803 uInt m; /* bytes to end of window or read pointer */
805 /* copy input/output information to locals (UPDATE macro restores) */
808 /* process input based on current state */
809 while (1) switch (s->mode)
818 Trace((stderr, "inflate: stored block%s\n",
819 s->last ? " (last)" : ""));
821 t = k & 7; /* go to byte boundary */
823 s->mode = LENS; /* get length of stored block */
826 Trace((stderr, "inflate: fixed codes block%s\n",
827 s->last ? " (last)" : ""));
830 inflate_huft *tl, *td;
832 inflate_trees_fixed(&bl, &bd, &tl, &td);
833 s->sub.decode.codes = inflate_codes_new(bl, bd, tl, td, z);
834 if (s->sub.decode.codes == Z_NULL)
839 s->sub.decode.tl = Z_NULL; /* don't try to free these */
840 s->sub.decode.td = Z_NULL;
845 case 2: /* dynamic */
846 Trace((stderr, "inflate: dynamic codes block%s\n",
847 s->last ? " (last)" : ""));
851 case 3: /* illegal */
854 z->msg = "invalid block type";
861 if (((~b) >> 16) != (b & 0xffff))
864 z->msg = "invalid stored block lengths";
868 s->sub.left = (uInt)b & 0xffff;
869 b = k = 0; /* dump bits */
870 Tracev((stderr, "inflate: stored length %u\n", s->sub.left));
871 s->mode = s->sub.left ? STORED : TYPE;
883 if ((s->sub.left -= t) != 0)
885 Tracev((stderr, "inflate: stored end, %lu total out\n",
886 z->total_out + (q >= s->read ? q - s->read :
887 (s->end - s->read) + (q - s->window))));
888 s->mode = s->last ? DRY : TYPE;
892 s->sub.trees.table = t = (uInt)b & 0x3fff;
893 #ifndef PKZIP_BUG_WORKAROUND
894 if ((t & 0x1f) > 29 || ((t >> 5) & 0x1f) > 29)
897 z->msg = "too many length or distance symbols";
902 t = 258 + (t & 0x1f) + ((t >> 5) & 0x1f);
905 if ((s->sub.trees.blens = (uIntf*)ZALLOC(z, t, sizeof(uInt))) == Z_NULL)
910 s->sub.trees.nblens = t;
912 s->sub.trees.index = 0;
913 Tracev((stderr, "inflate: table sizes ok\n"));
916 while (s->sub.trees.index < 4 + (s->sub.trees.table >> 10))
919 s->sub.trees.blens[border[s->sub.trees.index++]] = (uInt)b & 7;
922 while (s->sub.trees.index < 19)
923 s->sub.trees.blens[border[s->sub.trees.index++]] = 0;
925 t = inflate_trees_bits(s->sub.trees.blens, &s->sub.trees.bb,
926 &s->sub.trees.tb, z);
930 if (r == Z_DATA_ERROR)
932 ZFREE(z, s->sub.trees.blens, s->sub.trees.nblens * sizeof(uInt));
937 s->sub.trees.index = 0;
938 Tracev((stderr, "inflate: bits tree ok\n"));
941 while (t = s->sub.trees.table,
942 s->sub.trees.index < 258 + (t & 0x1f) + ((t >> 5) & 0x1f))
949 h = s->sub.trees.tb + ((uInt)b & inflate_mask[t]);
950 t = h->word.what.Bits;
955 s->sub.trees.blens[s->sub.trees.index++] = c;
957 else /* c == 16..18 */
959 i = c == 18 ? 7 : c - 14;
960 j = c == 18 ? 11 : 3;
963 j += (uInt)b & inflate_mask[i];
965 i = s->sub.trees.index;
966 t = s->sub.trees.table;
967 if (i + j > 258 + (t & 0x1f) + ((t >> 5) & 0x1f) ||
970 ZFREE(z, s->sub.trees.blens, s->sub.trees.nblens * sizeof(uInt));
972 z->msg = "invalid bit length repeat";
976 c = c == 16 ? s->sub.trees.blens[i - 1] : 0;
978 s->sub.trees.blens[i++] = c;
980 s->sub.trees.index = i;
983 inflate_trees_free(s->sub.trees.tb, z);
984 s->sub.trees.tb = Z_NULL;
987 inflate_huft *tl, *td;
988 inflate_codes_statef *c;
990 bl = 9; /* must be <= 9 for lookahead assumptions */
991 bd = 6; /* must be <= 9 for lookahead assumptions */
992 t = s->sub.trees.table;
993 t = inflate_trees_dynamic(257 + (t & 0x1f), 1 + ((t >> 5) & 0x1f),
994 s->sub.trees.blens, &bl, &bd, &tl, &td, z);
997 if (t == (uInt)Z_DATA_ERROR)
999 ZFREE(z, s->sub.trees.blens, s->sub.trees.nblens * sizeof(uInt));
1005 Tracev((stderr, "inflate: trees ok\n"));
1006 if ((c = inflate_codes_new(bl, bd, tl, td, z)) == Z_NULL)
1008 inflate_trees_free(td, z);
1009 inflate_trees_free(tl, z);
1013 ZFREE(z, s->sub.trees.blens, s->sub.trees.nblens * sizeof(uInt));
1014 s->sub.decode.codes = c;
1015 s->sub.decode.tl = tl;
1016 s->sub.decode.td = td;
1021 if ((r = inflate_codes(s, z, r)) != Z_STREAM_END)
1022 return inflate_flush(s, z, r);
1024 inflate_codes_free(s->sub.decode.codes, z);
1025 inflate_trees_free(s->sub.decode.td, z);
1026 inflate_trees_free(s->sub.decode.tl, z);
1028 Tracev((stderr, "inflate: codes end, %lu total out\n",
1029 z->total_out + (q >= s->read ? q - s->read :
1030 (s->end - s->read) + (q - s->window))));
1036 if (k > 7) /* return unused byte, if any */
1038 Assert(k < 16, "inflate_codes grabbed too many bytes")
1041 p--; /* can always return one */
1046 if (s->read != s->write)
1062 local int inflate_blocks_free(s, z, c)
1063 inflate_blocks_statef *s;
1067 inflate_blocks_reset(s, z, c);
1068 ZFREE(z, s->window, s->end - s->window);
1069 ZFREE(z, s, sizeof(struct inflate_blocks_state));
1070 Trace((stderr, "inflate: blocks freed\n"));
1075 * This subroutine adds the data at next_in/avail_in to the output history
1076 * without performing any output. The output buffer must be "caught up";
1077 * i.e. no pending output (hence s->read equals s->write), and the state must
1078 * be BLOCKS (i.e. we should be willing to see the start of a series of
1079 * BLOCKS). On exit, the output will also be caught up, and the checksum
1080 * will have been updated if need be.
1082 local int inflate_addhistory(s, z)
1083 inflate_blocks_statef *s;
1086 uLong b; /* bit buffer */ /* NOT USED HERE */
1087 uInt k; /* bits in bit buffer */ /* NOT USED HERE */
1088 uInt t; /* temporary storage */
1089 Bytef *p; /* input data pointer */
1090 uInt n; /* bytes available there */
1091 Bytef *q; /* output window write pointer */
1092 uInt m; /* bytes to end of window or read pointer */
1094 if (s->read != s->write)
1095 return Z_STREAM_ERROR;
1096 if (s->mode != TYPE)
1097 return Z_DATA_ERROR;
1099 /* we're ready to rock */
1101 /* while there is input ready, copy to output buffer, moving
1102 * pointers as needed.
1105 t = n; /* how many to do */
1106 /* is there room until end of buffer? */
1108 /* update check information */
1109 if (s->checkfn != Z_NULL)
1110 s->check = (*s->checkfn)(s->check, q, t);
1116 s->read = q; /* drag read pointer forward */
1117 /* WRAP */ /* expand WRAP macro by hand to handle s->read */
1119 s->read = q = s->window;
1129 * At the end of a Deflate-compressed PPP packet, we expect to have seen
1130 * a `stored' block type value but not the (zero) length bytes.
1132 local int inflate_packet_flush(s)
1133 inflate_blocks_statef *s;
1135 if (s->mode != LENS)
1136 return Z_DATA_ERROR;
1143 /* inftrees.c -- generate Huffman trees for efficient decoding
1144 * Copyright (C) 1995 Mark Adler
1145 * For conditions of distribution and use, see copyright notice in zlib.h
1148 /* simplify the use of the inflate_huft type with some defines */
1149 #define base more.Base
1150 #define next more.Next
1151 #define exop word.what.Exop
1152 #define bits word.what.Bits
1155 local int huft_build OF((
1156 uIntf *, /* code lengths in bits */
1157 uInt, /* number of codes */
1158 uInt, /* number of "simple" codes */
1159 uIntf *, /* list of base values for non-simple codes */
1160 uIntf *, /* list of extra bits for non-simple codes */
1161 inflate_huft * FAR*,/* result: starting table */
1162 uIntf *, /* maximum lookup bits (returns actual) */
1163 z_stream *)); /* for zalloc function */
1165 local voidpf falloc OF((
1166 voidpf, /* opaque pointer (not used) */
1167 uInt, /* number of items */
1168 uInt)); /* size of item */
1170 local void ffree OF((
1171 voidpf q, /* opaque pointer (not used) */
1172 voidpf p, /* what to free (not used) */
1173 uInt n)); /* number of bytes (not used) */
1175 /* Tables for deflate from PKZIP's appnote.txt. */
1176 local uInt cplens[] = { /* Copy lengths for literal codes 257..285 */
1177 3, 4, 5, 6, 7, 8, 9, 10, 11, 13, 15, 17, 19, 23, 27, 31,
1178 35, 43, 51, 59, 67, 83, 99, 115, 131, 163, 195, 227, 258, 0, 0};
1179 /* actually lengths - 2; also see note #13 above about 258 */
1180 local uInt cplext[] = { /* Extra bits for literal codes 257..285 */
1181 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 2, 2, 2, 2,
1182 3, 3, 3, 3, 4, 4, 4, 4, 5, 5, 5, 5, 0, 192, 192}; /* 192==invalid */
1183 local uInt cpdist[] = { /* Copy offsets for distance codes 0..29 */
1184 1, 2, 3, 4, 5, 7, 9, 13, 17, 25, 33, 49, 65, 97, 129, 193,
1185 257, 385, 513, 769, 1025, 1537, 2049, 3073, 4097, 6145,
1186 8193, 12289, 16385, 24577};
1187 local uInt cpdext[] = { /* Extra bits for distance codes */
1188 0, 0, 0, 0, 1, 1, 2, 2, 3, 3, 4, 4, 5, 5, 6, 6,
1189 7, 7, 8, 8, 9, 9, 10, 10, 11, 11,
1193 Huffman code decoding is performed using a multi-level table lookup.
1194 The fastest way to decode is to simply build a lookup table whose
1195 size is determined by the longest code. However, the time it takes
1196 to build this table can also be a factor if the data being decoded
1197 is not very long. The most common codes are necessarily the
1198 shortest codes, so those codes dominate the decoding time, and hence
1199 the speed. The idea is you can have a shorter table that decodes the
1200 shorter, more probable codes, and then point to subsidiary tables for
1201 the longer codes. The time it costs to decode the longer codes is
1202 then traded against the time it takes to make longer tables.
1204 This results of this trade are in the variables lbits and dbits
1205 below. lbits is the number of bits the first level table for literal/
1206 length codes can decode in one step, and dbits is the same thing for
1207 the distance codes. Subsequent tables are also less than or equal to
1208 those sizes. These values may be adjusted either when all of the
1209 codes are shorter than that, in which case the longest code length in
1210 bits is used, or when the shortest code is *longer* than the requested
1211 table size, in which case the length of the shortest code in bits is
1214 There are two different values for the two tables, since they code a
1215 different number of possibilities each. The literal/length table
1216 codes 286 possible values, or in a flat code, a little over eight
1217 bits. The distance table codes 30 possible values, or a little less
1218 than five bits, flat. The optimum values for speed end up being
1219 about one bit more than those, so lbits is 8+1 and dbits is 5+1.
1220 The optimum values may differ though from machine to machine, and
1221 possibly even between compilers. Your mileage may vary.
1225 /* If BMAX needs to be larger than 16, then h and x[] should be uLong. */
1226 #define BMAX 15 /* maximum bit length of any code */
1227 #define N_MAX 288 /* maximum number of codes in any set */
1233 local int huft_build(b, n, s, d, e, t, m, zs)
1234 uIntf *b; /* code lengths in bits (all assumed <= BMAX) */
1235 uInt n; /* number of codes (assumed <= N_MAX) */
1236 uInt s; /* number of simple-valued codes (0..s-1) */
1237 uIntf *d; /* list of base values for non-simple codes */
1238 uIntf *e; /* list of extra bits for non-simple codes */
1239 inflate_huft * FAR *t; /* result: starting table */
1240 uIntf *m; /* maximum lookup bits, returns actual */
1241 z_stream *zs; /* for zalloc function */
1242 /* Given a list of code lengths and a maximum table size, make a set of
1243 tables to decode that set of codes. Return Z_OK on success, Z_BUF_ERROR
1244 if the given code set is incomplete (the tables are still built in this
1245 case), Z_DATA_ERROR if the input is invalid (all zero length codes or an
1246 over-subscribed set of lengths), or Z_MEM_ERROR if not enough memory. */
1249 uInt a; /* counter for codes of length k */
1250 uInt c[BMAX+1]; /* bit length count table */
1251 uInt f; /* i repeats in table every f entries */
1252 int g; /* maximum code length */
1253 int h; /* table level */
1254 register uInt i; /* counter, current code */
1255 register uInt j; /* counter */
1256 register int k; /* number of bits in current code */
1257 int l; /* bits per table (returned in m) */
1258 register uIntf *p; /* pointer into c[], b[], or v[] */
1259 inflate_huft *q; /* points to current table */
1260 struct inflate_huft_s r; /* table entry for structure assignment */
1261 inflate_huft *u[BMAX]; /* table stack */
1262 uInt v[N_MAX]; /* values in order of bit length */
1263 register int w; /* bits before this table == (l * h) */
1264 uInt x[BMAX+1]; /* bit offsets, then code stack */
1265 uIntf *xp; /* pointer into x */
1266 int y; /* number of dummy codes added */
1267 uInt z; /* number of entries in current table */
1270 /* Generate counts for each bit length */
1272 #define C0 *p++ = 0;
1273 #define C2 C0 C0 C0 C0
1274 #define C4 C2 C2 C2 C2
1275 C4 /* clear c[]--assume BMAX+1 is 16 */
1278 c[*p++]++; /* assume all entries <= BMAX */
1280 if (c[0] == n) /* null input--all zero length codes */
1282 *t = (inflate_huft *)Z_NULL;
1288 /* Find minimum and maximum length, bound *m by those */
1290 for (j = 1; j <= BMAX; j++)
1293 k = j; /* minimum code length */
1296 for (i = BMAX; i; i--)
1299 g = i; /* maximum code length */
1305 /* Adjust last length count to fill out codes, if needed */
1306 for (y = 1 << j; j < i; j++, y <<= 1)
1307 if ((y -= c[j]) < 0)
1308 return Z_DATA_ERROR;
1309 if ((y -= c[i]) < 0)
1310 return Z_DATA_ERROR;
1314 /* Generate starting offsets into the value table for each length */
1316 p = c + 1; xp = x + 2;
1317 while (--i) { /* note that i == g from above */
1318 *xp++ = (j += *p++);
1322 /* Make a table of values in order of bit lengths */
1325 if ((j = *p++) != 0)
1330 /* Generate the Huffman codes and for each, make the table entries */
1331 x[0] = i = 0; /* first Huffman code is zero */
1332 p = v; /* grab values in bit order */
1333 h = -1; /* no tables yet--level -1 */
1334 w = -l; /* bits decoded == (l * h) */
1335 u[0] = (inflate_huft *)Z_NULL; /* just to keep compilers happy */
1336 q = (inflate_huft *)Z_NULL; /* ditto */
1339 /* go through the bit lengths (k already is bits in shortest code) */
1345 /* here i is the Huffman code of length k bits for value *p */
1346 /* make tables up to required level */
1350 w += l; /* previous table always l bits */
1352 /* compute minimum size table less than or equal to l bits */
1353 z = (z = g - w) > (uInt)l ? l : z; /* table size upper limit */
1354 if ((f = 1 << (j = k - w)) > a + 1) /* try a k-w bit table */
1355 { /* too few codes for k-w bit table */
1356 f -= a + 1; /* deduct codes from patterns left */
1359 while (++j < z) /* try smaller tables up to z bits */
1361 if ((f <<= 1) <= *++xp)
1362 break; /* enough codes to use up j bits */
1363 f -= *xp; /* else deduct codes from patterns */
1366 z = 1 << j; /* table entries for j-bit table */
1368 /* allocate and link in new table */
1369 if ((q = (inflate_huft *)ZALLOC
1370 (zs,z + 1,sizeof(inflate_huft))) == Z_NULL)
1373 inflate_trees_free(u[0], zs);
1374 return Z_MEM_ERROR; /* not enough memory */
1376 q->word.Nalloc = z + 1;
1378 inflate_hufts += z + 1;
1380 *t = q + 1; /* link to list for huft_free() */
1381 *(t = &(q->next)) = Z_NULL;
1382 u[h] = ++q; /* table starts after link */
1384 /* connect to last table, if there is one */
1387 x[h] = i; /* save pattern for backing up */
1388 r.bits = (Byte)l; /* bits to dump before this table */
1389 r.exop = (Byte)j; /* bits in this table */
1390 r.next = q; /* pointer to this table */
1391 j = i >> (w - l); /* (get around Turbo C bug) */
1392 u[h-1][j] = r; /* connect to last table */
1396 /* set up table entry in r */
1397 r.bits = (Byte)(k - w);
1399 r.exop = 128 + 64; /* out of values--invalid code */
1402 r.exop = (Byte)(*p < 256 ? 0 : 32 + 64); /* 256 is end-of-block */
1403 r.base = *p++; /* simple code is just the value */
1407 r.exop = (Byte)e[*p - s] + 16 + 64; /* non-simple--look up in lists */
1408 r.base = d[*p++ - s];
1411 /* fill code-like entries with r */
1413 for (j = i >> w; j < z; j += f)
1416 /* backwards increment the k-bit code i */
1417 for (j = 1 << (k - 1); i & j; j >>= 1)
1421 /* backup over finished tables */
1422 while ((i & ((1 << w) - 1)) != x[h])
1424 h--; /* don't need to update q */
1431 /* Return Z_BUF_ERROR if we were given an incomplete table */
1432 return y != 0 && g != 1 ? Z_BUF_ERROR : Z_OK;
1436 local int inflate_trees_bits(c, bb, tb, z)
1437 uIntf *c; /* 19 code lengths */
1438 uIntf *bb; /* bits tree desired/actual depth */
1439 inflate_huft * FAR *tb; /* bits tree result */
1440 z_stream *z; /* for zfree function */
1444 r = huft_build(c, 19, 19, (uIntf*)Z_NULL, (uIntf*)Z_NULL, tb, bb, z);
1445 if (r == Z_DATA_ERROR)
1446 z->msg = "oversubscribed dynamic bit lengths tree";
1447 else if (r == Z_BUF_ERROR)
1449 inflate_trees_free(*tb, z);
1450 z->msg = "incomplete dynamic bit lengths tree";
1457 local int inflate_trees_dynamic(nl, nd, c, bl, bd, tl, td, z)
1458 uInt nl; /* number of literal/length codes */
1459 uInt nd; /* number of distance codes */
1460 uIntf *c; /* that many (total) code lengths */
1461 uIntf *bl; /* literal desired/actual bit depth */
1462 uIntf *bd; /* distance desired/actual bit depth */
1463 inflate_huft * FAR *tl; /* literal/length tree result */
1464 inflate_huft * FAR *td; /* distance tree result */
1465 z_stream *z; /* for zfree function */
1469 /* build literal/length tree */
1470 if ((r = huft_build(c, nl, 257, cplens, cplext, tl, bl, z)) != Z_OK)
1472 if (r == Z_DATA_ERROR)
1473 z->msg = "oversubscribed literal/length tree";
1474 else if (r == Z_BUF_ERROR)
1476 inflate_trees_free(*tl, z);
1477 z->msg = "incomplete literal/length tree";
1483 /* build distance tree */
1484 if ((r = huft_build(c + nl, nd, 0, cpdist, cpdext, td, bd, z)) != Z_OK)
1486 if (r == Z_DATA_ERROR)
1487 z->msg = "oversubscribed literal/length tree";
1488 else if (r == Z_BUF_ERROR) {
1489 #ifdef PKZIP_BUG_WORKAROUND
1493 inflate_trees_free(*td, z);
1494 z->msg = "incomplete literal/length tree";
1497 inflate_trees_free(*tl, z);
1507 /* build fixed tables only once--keep them here */
1508 local int fixed_lock = 0;
1509 local int fixed_built = 0;
1510 #define FIXEDH 530 /* number of hufts used by fixed tables */
1511 local uInt fixed_left = FIXEDH;
1512 local inflate_huft fixed_mem[FIXEDH];
1513 local uInt fixed_bl;
1514 local uInt fixed_bd;
1515 local inflate_huft *fixed_tl;
1516 local inflate_huft *fixed_td;
1519 local voidpf falloc(q, n, s)
1520 voidpf q; /* opaque pointer (not used) */
1521 uInt n; /* number of items */
1522 uInt s; /* size of item */
1524 Assert(s == sizeof(inflate_huft) && n <= fixed_left,
1525 "inflate_trees falloc overflow");
1526 if (q) s++; /* to make some compilers happy */
1528 return (voidpf)(fixed_mem + fixed_left);
1532 local void ffree(q, p, n)
1537 Assert(0, "inflate_trees ffree called!");
1538 if (q) q = p; /* to make some compilers happy */
1542 local int inflate_trees_fixed(bl, bd, tl, td)
1543 uIntf *bl; /* literal desired/actual bit depth */
1544 uIntf *bd; /* distance desired/actual bit depth */
1545 inflate_huft * FAR *tl; /* literal/length tree result */
1546 inflate_huft * FAR *td; /* distance tree result */
1548 /* build fixed tables if not built already--lock out other instances */
1549 while (++fixed_lock > 1)
1553 int k; /* temporary variable */
1554 unsigned c[288]; /* length list for huft_build */
1555 z_stream z; /* for falloc function */
1557 /* set up fake z_stream for memory routines */
1563 for (k = 0; k < 144; k++)
1565 for (; k < 256; k++)
1567 for (; k < 280; k++)
1569 for (; k < 288; k++)
1572 huft_build(c, 288, 257, cplens, cplext, &fixed_tl, &fixed_bl, &z);
1574 /* distance table */
1575 for (k = 0; k < 30; k++)
1578 huft_build(c, 30, 0, cpdist, cpdext, &fixed_td, &fixed_bd, &z);
1592 local int inflate_trees_free(t, z)
1593 inflate_huft *t; /* table to free */
1594 z_stream *z; /* for zfree function */
1595 /* Free the malloc'ed tables built by huft_build(), which makes a linked
1596 list of the tables it made, with the links in a dummy first entry of
1599 register inflate_huft *p, *q;
1601 /* Go through linked list, freeing from the malloced (t[-1]) address. */
1606 ZFREE(z, p, p->word.Nalloc * sizeof(inflate_huft));
1613 /* infcodes.c -- process literals and length/distance pairs
1614 * Copyright (C) 1995 Mark Adler
1615 * For conditions of distribution and use, see copyright notice in zlib.h
1618 /* simplify the use of the inflate_huft type with some defines */
1619 #define base more.Base
1620 #define next more.Next
1621 #define exop word.what.Exop
1622 #define bits word.what.Bits
1624 /* inflate codes private state */
1625 struct inflate_codes_state {
1628 enum { /* waiting for "i:"=input, "o:"=output, "x:"=nothing */
1629 START, /* x: set up for LEN */
1630 LEN, /* i: get length/literal/eob next */
1631 LENEXT, /* i: getting length extra (have base) */
1632 DIST, /* i: get distance next */
1633 DISTEXT, /* i: getting distance extra */
1634 COPY, /* o: copying bytes in window, waiting for space */
1635 LIT, /* o: got literal, waiting for output space */
1636 WASH, /* o: got eob, possibly still output waiting */
1637 END, /* x: got eob and all data flushed */
1638 BADCODE} /* x: got error */
1639 mode; /* current inflate_codes mode */
1641 /* mode dependent information */
1645 inflate_huft *tree; /* pointer into tree */
1646 uInt need; /* bits needed */
1647 } code; /* if LEN or DIST, where in tree */
1648 uInt lit; /* if LIT, literal */
1650 uInt get; /* bits to get for extra */
1651 uInt dist; /* distance back to copy from */
1652 } copy; /* if EXT or COPY, where and how much */
1653 } sub; /* submode */
1655 /* mode independent information */
1656 Byte lbits; /* ltree bits decoded per branch */
1657 Byte dbits; /* dtree bits decoder per branch */
1658 inflate_huft *ltree; /* literal/length/eob tree */
1659 inflate_huft *dtree; /* distance tree */
1664 local inflate_codes_statef *inflate_codes_new(bl, bd, tl, td, z)
1666 inflate_huft *tl, *td;
1669 inflate_codes_statef *c;
1671 if ((c = (inflate_codes_statef *)
1672 ZALLOC(z,1,sizeof(struct inflate_codes_state))) != Z_NULL)
1675 c->lbits = (Byte)bl;
1676 c->dbits = (Byte)bd;
1679 Tracev((stderr, "inflate: codes new\n"));
1685 local int inflate_codes(s, z, r)
1686 inflate_blocks_statef *s;
1690 uInt j; /* temporary storage */
1691 inflate_huft *t; /* temporary pointer */
1692 uInt e; /* extra bits or operation */
1693 uLong b; /* bit buffer */
1694 uInt k; /* bits in bit buffer */
1695 Bytef *p; /* input data pointer */
1696 uInt n; /* bytes available there */
1697 Bytef *q; /* output window write pointer */
1698 uInt m; /* bytes to end of window or read pointer */
1699 Bytef *f; /* pointer to copy strings from */
1700 inflate_codes_statef *c = s->sub.decode.codes; /* codes state */
1702 /* copy input/output information to locals (UPDATE macro restores) */
1705 /* process input and output based on current state */
1706 while (1) switch (c->mode)
1707 { /* waiting for "i:"=input, "o:"=output, "x:"=nothing */
1708 case START: /* x: set up for LEN */
1710 if (m >= 258 && n >= 10)
1713 r = inflate_fast(c->lbits, c->dbits, c->ltree, c->dtree, s, z);
1717 c->mode = r == Z_STREAM_END ? WASH : BADCODE;
1722 c->sub.code.need = c->lbits;
1723 c->sub.code.tree = c->ltree;
1725 case LEN: /* i: get length/literal/eob next */
1726 j = c->sub.code.need;
1728 t = c->sub.code.tree + ((uInt)b & inflate_mask[j]);
1730 e = (uInt)(t->exop);
1731 if (e == 0) /* literal */
1733 c->sub.lit = t->base;
1734 Tracevv((stderr, t->base >= 0x20 && t->base < 0x7f ?
1735 "inflate: literal '%c'\n" :
1736 "inflate: literal 0x%02x\n", t->base));
1740 if (e & 16) /* length */
1742 c->sub.copy.get = e & 15;
1747 if ((e & 64) == 0) /* next table */
1749 c->sub.code.need = e;
1750 c->sub.code.tree = t->next;
1753 if (e & 32) /* end of block */
1755 Tracevv((stderr, "inflate: end of block\n"));
1759 c->mode = BADCODE; /* invalid code */
1760 z->msg = "invalid literal/length code";
1763 case LENEXT: /* i: getting length extra (have base) */
1764 j = c->sub.copy.get;
1766 c->len += (uInt)b & inflate_mask[j];
1768 c->sub.code.need = c->dbits;
1769 c->sub.code.tree = c->dtree;
1770 Tracevv((stderr, "inflate: length %u\n", c->len));
1772 case DIST: /* i: get distance next */
1773 j = c->sub.code.need;
1775 t = c->sub.code.tree + ((uInt)b & inflate_mask[j]);
1777 e = (uInt)(t->exop);
1778 if (e & 16) /* distance */
1780 c->sub.copy.get = e & 15;
1781 c->sub.copy.dist = t->base;
1785 if ((e & 64) == 0) /* next table */
1787 c->sub.code.need = e;
1788 c->sub.code.tree = t->next;
1791 c->mode = BADCODE; /* invalid code */
1792 z->msg = "invalid distance code";
1795 case DISTEXT: /* i: getting distance extra */
1796 j = c->sub.copy.get;
1798 c->sub.copy.dist += (uInt)b & inflate_mask[j];
1800 Tracevv((stderr, "inflate: distance %u\n", c->sub.copy.dist));
1802 case COPY: /* o: copying bytes in window, waiting for space */
1803 #ifndef __TURBOC__ /* Turbo C bug for following expression */
1804 f = (uInt)(q - s->window) < c->sub.copy.dist ?
1805 s->end - (c->sub.copy.dist - (q - s->window)) :
1806 q - c->sub.copy.dist;
1808 f = q - c->sub.copy.dist;
1809 if ((uInt)(q - s->window) < c->sub.copy.dist)
1810 f = s->end - (c->sub.copy.dist - (q - s->window));
1822 case LIT: /* o: got literal, waiting for output space */
1827 case WASH: /* o: got eob, possibly more output */
1829 if (s->read != s->write)
1835 case BADCODE: /* x: got error */
1845 local void inflate_codes_free(c, z)
1846 inflate_codes_statef *c;
1849 ZFREE(z, c, sizeof(struct inflate_codes_state));
1850 Tracev((stderr, "inflate: codes free\n"));
1854 /* inflate_util.c -- data and routines common to blocks and codes
1855 * Copyright (C) 1995 Mark Adler
1856 * For conditions of distribution and use, see copyright notice in zlib.h
1859 /* copy as much as possible from the sliding window to the output area */
1860 local int inflate_flush(s, z, r)
1861 inflate_blocks_statef *s;
1868 /* local copies of source and destination pointers */
1872 /* compute number of bytes to copy as far as end of window */
1873 n = (uInt)((q <= s->write ? s->write : s->end) - q);
1874 if (n > z->avail_out) n = z->avail_out;
1875 if (n && r == Z_BUF_ERROR) r = Z_OK;
1877 /* update counters */
1881 /* update check information */
1882 if (s->checkfn != Z_NULL)
1883 s->check = (*s->checkfn)(s->check, q, n);
1885 /* copy as far as end of window */
1890 /* see if more to copy at beginning of window */
1895 if (s->write == s->end)
1896 s->write = s->window;
1898 /* compute bytes to copy */
1899 n = (uInt)(s->write - q);
1900 if (n > z->avail_out) n = z->avail_out;
1901 if (n && r == Z_BUF_ERROR) r = Z_OK;
1903 /* update counters */
1907 /* update check information */
1908 if (s->checkfn != Z_NULL)
1909 s->check = (*s->checkfn)(s->check, q, n);
1917 /* update pointers */
1927 /* inffast.c -- process literals and length/distance pairs fast
1928 * Copyright (C) 1995 Mark Adler
1929 * For conditions of distribution and use, see copyright notice in zlib.h
1932 /* simplify the use of the inflate_huft type with some defines */
1933 #define base more.Base
1934 #define next more.Next
1935 #define exop word.what.Exop
1936 #define bits word.what.Bits
1938 /* macros for bit input with no checking and for returning unused bytes */
1939 #define GRABBITS(j) {while(k<(j)){b|=((uLong)NEXTBYTE)<<k;k+=8;}}
1940 #define UNGRAB {n+=(c=k>>3);p-=c;k&=7;}
1942 /* Called with number of bytes left to write in window at least 258
1943 (the maximum string length) and number of input bytes available
1944 at least ten. The ten bytes are six bytes for the longest length/
1945 distance pair plus four bytes for overloading the bit buffer. */
1947 local int inflate_fast(bl, bd, tl, td, s, z)
1949 inflate_huft *tl, *td;
1950 inflate_blocks_statef *s;
1953 inflate_huft *t; /* temporary pointer */
1954 uInt e; /* extra bits or operation */
1955 uLong b; /* bit buffer */
1956 uInt k; /* bits in bit buffer */
1957 Bytef *p; /* input data pointer */
1958 uInt n; /* bytes available there */
1959 Bytef *q; /* output window write pointer */
1960 uInt m; /* bytes to end of window or read pointer */
1961 uInt ml; /* mask for literal/length tree */
1962 uInt md; /* mask for distance tree */
1963 uInt c; /* bytes to copy */
1964 uInt d; /* distance back to copy from */
1965 Bytef *r; /* copy source pointer */
1967 /* load input, output, bit values */
1970 /* initialize masks */
1971 ml = inflate_mask[bl];
1972 md = inflate_mask[bd];
1974 /* do until not enough input or output space for fast loop */
1975 do { /* assume called with m >= 258 && n >= 10 */
1976 /* get literal/length code */
1977 GRABBITS(20) /* max bits for literal/length code */
1978 if ((e = (t = tl + ((uInt)b & ml))->exop) == 0)
1981 Tracevv((stderr, t->base >= 0x20 && t->base < 0x7f ?
1982 "inflate: * literal '%c'\n" :
1983 "inflate: * literal 0x%02x\n", t->base));
1984 *q++ = (Byte)t->base;
1992 /* get extra bits for length */
1994 c = t->base + ((uInt)b & inflate_mask[e]);
1996 Tracevv((stderr, "inflate: * length %u\n", c));
1998 /* decode distance base of block to copy */
1999 GRABBITS(15); /* max bits for distance code */
2000 e = (t = td + ((uInt)b & md))->exop;
2005 /* get extra bits to add to distance base */
2007 GRABBITS(e) /* get extra bits (up to 13) */
2008 d = t->base + ((uInt)b & inflate_mask[e]);
2010 Tracevv((stderr, "inflate: * distance %u\n", d));
2014 if ((uInt)(q - s->window) >= d) /* offset before dest */
2017 *q++ = *r++; c--; /* minimum count is three, */
2018 *q++ = *r++; c--; /* so unroll loop a little */
2020 else /* else offset after destination */
2022 e = d - (q - s->window); /* bytes from offset to end */
2023 r = s->end - e; /* pointer to offset */
2024 if (c > e) /* if source crosses, */
2026 c -= e; /* copy to end of window */
2030 r = s->window; /* copy rest from start of window */
2033 do { /* copy all or what's left */
2038 else if ((e & 64) == 0)
2039 e = (t = t->next + ((uInt)b & inflate_mask[e]))->exop;
2042 z->msg = "invalid distance code";
2045 return Z_DATA_ERROR;
2052 if ((e = (t = t->next + ((uInt)b & inflate_mask[e]))->exop) == 0)
2055 Tracevv((stderr, t->base >= 0x20 && t->base < 0x7f ?
2056 "inflate: * literal '%c'\n" :
2057 "inflate: * literal 0x%02x\n", t->base));
2058 *q++ = (Byte)t->base;
2065 Tracevv((stderr, "inflate: * end of block\n"));
2068 return Z_STREAM_END;
2072 z->msg = "invalid literal/length code";
2075 return Z_DATA_ERROR;
2078 } while (m >= 258 && n >= 10);
2080 /* not enough input or output--restore pointers and return */
2088 /* zutil.c -- target dependent utility functions for the compression library
2089 * Copyright (C) 1995 Jean-loup Gailly.
2090 * For conditions of distribution and use, see copyright notice in zlib.h
2093 /* From: zutil.c,v 1.8 1995/05/03 17:27:12 jloup Exp */
2095 char *zlib_version = ZLIB_VERSION;
2097 char *z_errmsg[] = {
2098 "stream end", /* Z_STREAM_END 1 */
2100 "file error", /* Z_ERRNO (-1) */
2101 "stream error", /* Z_STREAM_ERROR (-2) */
2102 "data error", /* Z_DATA_ERROR (-3) */
2103 "insufficient memory", /* Z_MEM_ERROR (-4) */
2104 "buffer error", /* Z_BUF_ERROR (-5) */
2109 /* adler32.c -- compute the Adler-32 checksum of a data stream
2110 * Copyright (C) 1995 Mark Adler
2111 * For conditions of distribution and use, see copyright notice in zlib.h
2114 /* From: adler32.c,v 1.6 1995/05/03 17:27:08 jloup Exp */
2116 #define BASE 65521L /* largest prime smaller than 65536 */
2118 /* NMAX is the largest n such that 255n(n+1)/2 + (n+1)(BASE-1) <= 2^32-1 */
2120 #define DO1(buf) {s1 += *buf++; s2 += s1;}
2121 #define DO2(buf) DO1(buf); DO1(buf);
2122 #define DO4(buf) DO2(buf); DO2(buf);
2123 #define DO8(buf) DO4(buf); DO4(buf);
2124 #define DO16(buf) DO8(buf); DO8(buf);
2126 /* ========================================================================= */
2127 uLong adler32(adler, buf, len)
2132 unsigned long s1 = adler & 0xffff;
2133 unsigned long s2 = (adler >> 16) & 0xffff;
2136 if (buf == Z_NULL) return 1L;
2139 k = len < NMAX ? len : NMAX;
2151 return (s2 << 16) | s1;