xref: /titanic_51/usr/src/uts/common/io/ppp/spppcomp/zlib.c (revision cf5b5989488984444a152faba2a8183a71dcf485)
1 /*
2  * Copyright 2007 Sun Microsystems, Inc.  All rights reserved.
3  * Use is subject to license terms.
4  */
5 
6 /*
7  * Updated from zlib-1.0.4 to zlib-1.1.3 by James Carlson.
8  *
9  * This file is derived from various .h and .c files from the zlib-1.0.4
10  * distribution by Jean-loup Gailly and Mark Adler, with some additions
11  * by Paul Mackerras to aid in implementing Deflate compression and
12  * decompression for PPP packets.  See zlib.h for conditions of
13  * distribution and use.
14  *
15  * Changes that have been made include:
16  * - added Z_PACKET_FLUSH (see zlib.h for details)
17  * - added inflateIncomp and deflateOutputPending
18  * - allow strm->next_out to be NULL, meaning discard the output
19  *
20  * $Id: zlib.c,v 1.11 1998/09/13 23:37:12 paulus Exp $
21  */
22 
23 #pragma ident	"%Z%%M%	%I%	%E% SMI"
24 
25 /*
26  *  ==FILEVERSION 971210==
27  *
28  * This marker is used by the Linux installation script to determine
29  * whether an up-to-date version of this file is already installed.
30  */
31 
32 #define	NO_DUMMY_DECL
33 #define	NO_ZCFUNCS
34 #define	MY_ZCALLOC
35 
36 #if defined(__FreeBSD__) && (defined(KERNEL) || defined(_KERNEL))
37 #define	inflate	inflate_ppp	/* FreeBSD already has an inflate :-( */
38 #endif
39 
40 
41 /* +++ zutil.h */
42 /*
43  *
44  * zutil.h -- internal interface and configuration of the compression library
45  * Copyright (C) 1995-1998 Jean-loup Gailly.
46  * For conditions of distribution and use, see copyright notice in zlib.h
47  */
48 
49 /*
50  * WARNING: this file should *not* be used by applications. It is part
51  * of the implementation of the compression library and is subject to
52  * change. Applications should only use zlib.h.
53  */
54 
55 /* From: zutil.h,v 1.16 1996/07/24 13:41:13 me Exp $ */
56 
57 #ifndef _Z_UTIL_H
58 #define	_Z_UTIL_H
59 
60 #include "zlib.h"
61 
62 #if defined(KERNEL) || defined(_KERNEL)
63 /* Assume this is a *BSD or SVR4 kernel */
64 #include <sys/types.h>
65 #include <sys/time.h>
66 #include <sys/systm.h>
67 #ifdef SOL2
68 #include <sys/cmn_err.h>
69 #endif
70 #define	HAVE_MEMCPY
71 #define	memcmp		bcmp
72 
73 #else
74 #if defined(__KERNEL__)
75 /* Assume this is a Linux kernel */
76 #include <linux/string.h>
77 #define	HAVE_MEMCPY
78 
79 #else /* not kernel */
80 
81 #include <stddef.h>
82 #ifdef NO_ERRNO_H
83 extern int errno;
84 #else
85 #include <errno.h>
86 #endif
87 #ifdef STDC
88 #include <string.h>
89 #include <stdlib.h>
90 #endif
91 #endif /* __KERNEL__ */
92 #endif /* _KERNEL || KERNEL */
93 
94 #ifndef local
95 #define	local static
96 #endif
97 /* compile with -Dlocal if your debugger can't find static symbols */
98 
99 typedef unsigned char  uch;
100 typedef uch FAR uchf;
101 typedef unsigned short ush;
102 typedef ush FAR ushf;
103 typedef unsigned long  ulg;
104 
105 static const char *z_errmsg[10]; /* indexed by 2-zlib_error */
106 /* (size given to avoid silly warnings with Visual C++) */
107 
108 #define	ERR_MSG(err) z_errmsg[Z_NEED_DICT-(err)]
109 
110 #define	ERR_RETURN(strm, err) \
111 	return (strm->msg = ERR_MSG(err), (err))
112 /* To be used only when the state is known to be valid */
113 
114 	/* common constants */
115 
116 #ifndef DEF_WBITS
117 #define	DEF_WBITS MAX_WBITS
118 #endif
119 /* default windowBits for decompression. MAX_WBITS is for compression only */
120 
121 #if MAX_MEM_LEVEL >= 8
122 #define	DEF_MEM_LEVEL 8
123 #else
124 #define	DEF_MEM_LEVEL  MAX_MEM_LEVEL
125 #endif
126 /* default memLevel */
127 
128 #define	STORED_BLOCK 0
129 #define	STATIC_TREES 1
130 #define	DYN_TREES    2
131 /* The three kinds of block type */
132 
133 #define	MIN_MATCH  3
134 #define	MAX_MATCH  258
135 /* The minimum and maximum match lengths */
136 
137 #define	PRESET_DICT 0x20 /* preset dictionary flag in zlib header */
138 
139 	/* target dependencies */
140 
141 #ifdef MSDOS
142 #define	OS_CODE  0x00
143 #ifdef __TURBOC__
144 #include <alloc.h>
145 #else /* MSC or DJGPP */
146 #include <malloc.h>
147 #endif
148 #endif
149 
150 #ifdef OS2
151 #define	OS_CODE  0x06
152 #endif
153 
154 #ifdef WIN32 /* Window 95 & Windows NT */
155 #define	OS_CODE  0x0b
156 #endif
157 
158 #if defined(VAXC) || defined(VMS)
159 #define	OS_CODE  0x02
160 #define	F_OPEN(name, mode) \
161 	fopen((name), (mode), "mbc=60", "ctx=stm", "rfm=fix", "mrs=512")
162 #endif
163 
164 #ifdef AMIGA
165 #define	OS_CODE  0x01
166 #endif
167 
168 #if defined(ATARI) || defined(atarist)
169 #define	OS_CODE  0x05
170 #endif
171 
172 #ifdef MACOS
173 #define	OS_CODE  0x07
174 #endif
175 
176 #ifdef __50SERIES /* Prime/PRIMOS */
177 #define	OS_CODE  0x0F
178 #endif
179 
180 #ifdef TOPS20
181 #define	OS_CODE  0x0a
182 #endif
183 
184 #if defined(_BEOS_) || defined(RISCOS)
185 #define	fdopen(fd, mode) NULL /* No fdopen() */
186 #endif
187 
188 	/* Common defaults */
189 
190 #ifndef OS_CODE
191 #define	OS_CODE  0x03  /* assume Unix */
192 #endif
193 
194 #ifndef F_OPEN
195 #define	F_OPEN(name, mode) fopen((name), (mode))
196 #endif
197 
198 	/* functions */
199 
200 #ifdef HAVE_STRERROR
201 extern char *strerror OF((int));
202 #define	zstrerror(errnum) strerror(errnum)
203 #else
204 #define	zstrerror(errnum) ""
205 #endif
206 
207 #if defined(pyr)
208 #define	NO_MEMCPY
209 #endif
210 #if (defined(M_I86SM) || defined(M_I86MM)) && !defined(_MSC_VER)
211 /*
212  * Use our own functions for small and medium model with MSC <= 5.0.
213  * You may have to use the same strategy for Borland C (untested).
214  */
215 #define	NO_MEMCPY
216 #endif
217 #if defined(STDC) && !defined(HAVE_MEMCPY) && !defined(NO_MEMCPY)
218 #define	HAVE_MEMCPY
219 #endif
220 #ifdef HAVE_MEMCPY
221 #ifdef SMALL_MEDIUM /* MSDOS small or medium model */
222 #define	zmemcpy _fmemcpy
223 #define	zmemcmp _fmemcmp
224 #define	zmemzero(dest, len) _fmemset(dest, 0, len)
225 #else
226 #define	zmemcpy (void) memcpy
227 #define	zmemcmp memcmp
228 #define	zmemzero(dest, len) (void) memset(dest, 0, len)
229 #endif
230 #else
231 extern void zmemcpy  OF((Bytef* dest, const Bytef* source, uInt len));
232 extern int  zmemcmp  OF((const Bytef* s1, const Bytef* s2, uInt len));
233 extern void zmemzero OF((Bytef* dest, uInt len));
234 #endif
235 
236 /* Diagnostic functions */
237 #ifdef DEBUG_ZLIB
238 #include <stdio.h>
239 #ifndef verbose
240 #define	verbose 0
241 #endif
242 extern void z_error    OF((char *m));
243 #define	Assert(cond, msg) { if (!(cond)) z_error(msg); }
244 #define	Trace(x) {if (z_verbose >= 0) fprintf x; }
245 #define	Tracev(x) {if (z_verbose > 0) fprintf x; }
246 #define	Tracevv(x) {if (z_verbose > 1) fprintf x; }
247 #define	Tracec(c, x) {if (z_verbose > 0 && (c)) fprintf x; }
248 #define	Tracecv(c, x) {if (z_verbose > 1 && (c)) fprintf x; }
249 #else
250 #if defined(SOL2) && defined(DEBUG)
251 #define	Assert(cond, msg)	((cond) ? ((void)0) : panic(msg))
252 #else
253 #define	Assert(cond, msg)	((void)0)
254 #endif
255 #define	Trace(x)	((void)0)
256 #define	Tracev(x)	((void)0)
257 #define	Tracevv(x)	((void)0)
258 #define	Tracec(c, x)	((void)0)
259 #define	Tracecv(c, x)	((void)0)
260 #endif
261 
262 
263 typedef uLong (*check_func) OF((uLong check, const Bytef *buf, uInt len));
264 
265 /* voidpf zcalloc OF((voidpf opaque, unsigned items, unsigned size)); */
266 /* void   zcfree  OF((voidpf opaque, voidpf ptr)); */
267 
268 #define	ZALLOC(strm, items, size) \
269 	(*((strm)->zalloc))((strm)->opaque, (items), (size))
270 #define	ZFREE(strm, addr)  (*((strm)->zfree))((strm)->opaque, (voidpf)(addr))
271 #define	TRY_FREE(s, p) {if (p) ZFREE(s, p); }
272 
273 #endif /* _Z_UTIL_H */
274 /* --- zutil.h */
275 
276 /* +++ deflate.h */
277 /*
278  * deflate.h -- internal compression state
279  * Copyright (C) 1995-1998 Jean-loup Gailly
280  * For conditions of distribution and use, see copyright notice in zlib.h
281  */
282 
283 /*
284  * WARNING: this file should *not* be used by applications. It is part
285  * of the implementation of the compression library and is subject to
286  * change. Applications should only use zlib.h.
287  */
288 
289 /* From: deflate.h,v 1.10 1996/07/02 12:41:00 me Exp $ */
290 
291 #ifndef _DEFLATE_H
292 #define	_DEFLATE_H
293 
294 /* #include "zutil.h" */
295 
296 /*
297  * ===========================================================================
298  * Internal compression state.
299  */
300 
301 #define	LENGTH_CODES 29
302 /* number of length codes, not counting the special END_BLOCK code */
303 
304 #define	LITERALS  256
305 /* number of literal bytes 0..255 */
306 
307 #define	L_CODES (LITERALS+1+LENGTH_CODES)
308 /* number of Literal or Length codes, including the END_BLOCK code */
309 
310 #define	D_CODES   30
311 /* number of distance codes */
312 
313 #define	BL_CODES  19
314 /* number of codes used to transfer the bit lengths */
315 
316 #define	HEAP_SIZE (2*L_CODES+1)
317 /* maximum heap size */
318 
319 #define	MAX_BITS 15
320 /* All codes must not exceed MAX_BITS bits */
321 
322 #define	INIT_STATE    42
323 #define	BUSY_STATE   113
324 #define	FINISH_STATE 666
325 /* Stream status */
326 
327 
328 /* Data structure describing a single value and its code string. */
329 typedef struct ct_data_s {
330 	union {
331 		ush freq;	/* frequency count */
332 		ush code;	/* bit string */
333 	} fc;
334 	union {
335 		ush dad;	/* father node in Huffman tree */
336 		ush len;	/* length of bit string */
337 	} dl;
338 } FAR ct_data;
339 
340 #define	Freq fc.freq
341 #define	Code fc.code
342 #define	Dad  dl.dad
343 #define	Len  dl.len
344 
345 typedef struct static_tree_desc_s  static_tree_desc;
346 
347 typedef struct tree_desc_s {
348 	ct_data *dyn_tree;	/* the dynamic tree */
349 	int	max_code;	/* largest code with non zero frequency */
350 	static_tree_desc *stat_desc;	/* the corresponding static tree */
351 } FAR tree_desc;
352 
353 typedef ush Pos;
354 typedef Pos FAR Posf;
355 typedef unsigned IPos;
356 
357 /*
358  * A Pos is an index in the character window. We use short instead of
359  * int to save space in the various tables. IPos is used only for
360  * parameter passing.
361  */
362 
363 typedef struct deflate_state {
364 	z_streamp strm;	/* pointer back to this zlib stream */
365 	int   status;	/* as the name implies */
366 	Bytef *pending_buf;	/* output still pending */
367 	ulg   pending_buf_size;	/* size of pending_buf */
368 	Bytef *pending_out;	/* next pending byte to output to the stream */
369 	int   pending;	/* nb of bytes in the pending buffer */
370 	int   noheader;	/* suppress zlib header and adler32 */
371 	Byte  data_type;	/* UNKNOWN, BINARY or ASCII */
372 	Byte  method;	/* STORED (for zip only) or DEFLATED */
373 	/* value of flush param for previous deflate call */
374 	int   last_flush;
375 
376 	/* used by deflate.c: */
377 
378 	uInt  w_size;	/* LZ77 window size (32K by default) */
379 	uInt  w_bits;	/* log2(w_size)  (8..16) */
380 	uInt  w_mask;	/* w_size - 1 */
381 
382 	Bytef *window;
383 	/*
384 	 * Sliding window. Input bytes are read into the second half
385 	 * of the window, and move to the first half later to keep a
386 	 * dictionary of at least wSize bytes. With this organization,
387 	 * matches are limited to a distance of wSize-MAX_MATCH bytes,
388 	 * but this ensures that IO is always performed with a length
389 	 * multiple of the block size. Also, it limits the window size
390 	 * to 64K, which is quite useful on MSDOS.  To do: use the
391 	 * user input buffer as sliding window.
392 	 */
393 
394 	ulg window_size;
395 	/*
396 	 * Actual size of window: 2*wSize, except when the user input
397 	 * buffer is directly used as sliding window.
398 	 */
399 
400 	Posf *prev;
401 	/*
402 	 * Link to older string with same hash index. To limit the
403 	 * size of this array to 64K, this link is maintained only for
404 	 * the last 32K strings.  An index in this array is thus a
405 	 * window index modulo 32K.
406 	 */
407 
408 	Posf *head;	/* Heads of the hash chains or NIL. */
409 
410 	uInt  ins_h;	/* hash index of string to be inserted */
411 	uInt  hash_size;	/* number of elements in hash table */
412 	uInt  hash_bits;	/* log2(hash_size) */
413 	uInt  hash_mask;	/* hash_size-1 */
414 
415 	uInt  hash_shift;
416 	/*
417 	 * Number of bits by which ins_h must be shifted at each input
418 	 * step. It must be such that after MIN_MATCH steps, the
419 	 * oldest byte no longer takes part in the hash key, that is:
420 	 * hash_shift * MIN_MATCH >= hash_bits
421 	 */
422 
423 	long block_start;
424 	/*
425 	 * Window position at the beginning of the current output
426 	 * block. Gets negative when the window is moved backwards.
427 	 */
428 
429 	uInt match_length;	/* length of best match */
430 	IPos prev_match;	/* previous match */
431 	int match_available;	/* set if previous match exists */
432 	uInt strstart;	/* start of string to insert */
433 	uInt match_start;	/* start of matching string */
434 	uInt lookahead;	/* number of valid bytes ahead in window */
435 
436 	uInt prev_length;
437 	/*
438 	 * Length of the best match at previous step. Matches not
439 	 * greater than this are discarded. This is used in the lazy
440 	 * match evaluation.
441 	 */
442 
443 	uInt max_chain_length;
444 	/*
445 	 * To speed up deflation, hash chains are never searched
446 	 * beyond *this length.  A higher limit improves compression
447 	 * ratio but *degrades the speed.
448 	 */
449 
450 	uInt max_lazy_match;
451 	/*
452 	 * Attempt to find a better match only when the current match
453 	 * is strictly smaller than this value. This mechanism is used
454 	 * only for compression levels >= 4.
455 	 */
456 #define	max_insert_length  max_lazy_match
457 	/*
458 	 * Insert new strings in the hash table only if the match
459 	 * length is not greater than this length. This saves time but
460 	 * degrades compression.  max_insert_length is used only for
461 	 * compression levels <= 3.
462 	 */
463 
464 	int level;	/* compression level (1..9) */
465 	int strategy;	/* favor or force Huffman coding */
466 
467 	uInt good_match;
468 	/* Use a faster search when the previous match is longer than this */
469 
470 	int nice_match;	/* Stop searching when current match exceeds this */
471 
472 	/* used by trees.c: */
473 	/* Didn't use ct_data typedef below to supress compiler warning */
474 	struct ct_data_s dyn_ltree[HEAP_SIZE];	/* literal and length tree */
475 	struct ct_data_s dyn_dtree[2*D_CODES+1];	/* distance tree */
476 	/* Huffman tree for bit lengths */
477 	struct ct_data_s bl_tree[2*BL_CODES+1];
478 
479 	struct tree_desc_s l_desc;	/* desc. for literal tree */
480 	struct tree_desc_s d_desc;	/* desc. for distance tree */
481 	struct tree_desc_s bl_desc;	/* desc. for bit length tree */
482 
483 	ush bl_count[MAX_BITS+1];
484 	/* number of codes at each bit length for an optimal tree */
485 
486 	int heap[2*L_CODES+1];	/* heap used to build the Huffman trees */
487 	int heap_len;	/* number of elements in the heap */
488 	int heap_max;	/* element of largest frequency */
489 	/*
490 	 * The sons of heap[n] are heap[2*n] and heap[2*n+1]. heap[0]
491 	 * is not used.  The same heap array is used to build all
492 	 * trees.
493 	 */
494 
495 	uch depth[2*L_CODES+1];
496 	/*
497 	 * Depth of each subtree used as tie breaker for trees of
498 	 * equal frequency
499 	 */
500 
501 	uchf *l_buf;	/* buffer for literals or lengths */
502 
503 	uInt lit_bufsize;
504 	/*
505 	 * Size of match buffer for literals/lengths.  There are 4
506 	 * reasons for limiting lit_bufsize to 64K:
507 	 *
508 	 *   - frequencies can be kept in 16 bit counters
509 	 *
510 	 *   - if compression is not successful for the first block,
511 	 *   all input data is still in the window so we can still
512 	 *   emit a stored block even when input comes from standard
513 	 *   input.  (This can also be done for all blocks if
514 	 *   lit_bufsize is not greater than 32K.)
515 	 *
516 	 *   - if compression is not successful for a file smaller
517 	 *   than 64K, we can even emit a stored file instead of a
518 	 *   stored block (saving 5 bytes).  This is applicable only
519 	 *   for zip (not gzip or zlib).
520 	 *
521 	 *   - creating new Huffman trees less frequently may not
522 	 *   provide fast adaptation to changes in the input data
523 	 *   statistics. (Take for example a binary file with poorly
524 	 *   compressible code followed by a highly compressible
525 	 *   string table.) Smaller buffer sizes give fast adaptation
526 	 *   but have of course the overhead of transmitting trees
527 	 *   more frequently.
528 	 *
529 	 *   - I can't count above 4
530 	 */
531 
532 	uInt last_lit;	/* running index in l_buf */
533 
534 	ushf *d_buf;
535 	/*
536 	 * Buffer for distances. To simplify the code, d_buf and l_buf
537 	 * have the same number of elements. To use different lengths,
538 	 * an extra flag array would be necessary.
539 	 */
540 
541 	ulg opt_len;	/* bit length of current block with optimal trees */
542 	ulg static_len;	/* bit length of current block with static trees */
543 	uInt matches;	/* number of string matches in current block */
544 	int last_eob_len;	/* bit length of EOB code for last block */
545 
546 	ulg compressed_len;	/* total bit length of compressed file PPP */
547 #ifdef DEBUG_ZLIB
548 	ulg bits_sent;	/* bit length of the compressed data */
549 #endif
550 
551 	ush bi_buf;
552 	/*
553 	 * Output buffer. bits are inserted starting at the bottom
554 	 * (least significant bits).
555 	 */
556 	int bi_valid;
557 	/*
558 	 * Number of valid bits in bi_buf.  All bits above the last
559 	 * valid bit are always zero.
560 	 */
561 
562 } FAR deflate_state;
563 
564 /*
565  * Output a byte on the stream.  IN assertion: there is enough room in
566  * pending_buf.
567  */
568 #define	put_byte(s, c) {s->pending_buf[s->pending++] = (c); }
569 
570 
571 #define	MIN_LOOKAHEAD (MAX_MATCH+MIN_MATCH+1)
572 /*
573  * Minimum amount of lookahead, except at the end of the input file.
574  * See deflate.c for comments about the MIN_MATCH+1.
575  */
576 
577 #define	MAX_DIST(s)  ((s)->w_size-MIN_LOOKAHEAD)
578 /*
579  * In order to simplify the code, particularly on 16 bit machines,
580  * match distances are limited to MAX_DIST instead of WSIZE.
581  */
582 
583 	/* in trees.c */
584 void _tr_init		OF((deflate_state *s));
585 int  _tr_tally		OF((deflate_state *s, unsigned dist, unsigned lc));
586 void  _tr_flush_block	OF((deflate_state *s, charf *buf, ulg stored_len,
587     int eof));
588 void _tr_align		OF((deflate_state *s));
589 void _tr_stored_block	OF((deflate_state *s, charf *buf, ulg stored_len,
590     int eof));
591 void _tr_stored_type_only OF((deflate_state *));	/* PPP */
592 
593 #define	d_code(dist) \
594 	((dist) < 256 ? _dist_code[dist] : _dist_code[256+((dist)>>7)])
595 /*
596  * Mapping from a distance to a distance code. dist is the distance - 1 and
597  * must not have side effects. _dist_code[256] and _dist_code[257] are never
598  * used.
599  */
600 
601 #ifndef DEBUG_ZLIB
602 /* Inline versions of _tr_tally for speed: */
603 
604 local uch _length_code[];
605 local uch _dist_code[];
606 
607 #define	_tr_tally_lit(s, c, flush) \
608 	{	uch cc = (c); \
609 		s->d_buf[s->last_lit] = 0; \
610 		s->l_buf[s->last_lit++] = cc; \
611 		s->dyn_ltree[cc].Freq++; \
612 		flush = (s->last_lit == s->lit_bufsize-1); \
613 	}
614 #define	_tr_tally_dist(s, distance, length, flush) \
615 	{	uch len = (length); \
616 		ush dist = (distance); \
617 		s->d_buf[s->last_lit] = dist; \
618 		s->l_buf[s->last_lit++] = len; \
619 		dist--; \
620 		s->dyn_ltree[_length_code[len]+LITERALS+1].Freq++; \
621 		s->dyn_dtree[d_code(dist)].Freq++; \
622 		flush = (s->last_lit == s->lit_bufsize-1); \
623 	}
624 #else
625 #define	_tr_tally_lit(s, c, flush) flush = _tr_tally(s, 0, c)
626 #define	_tr_tally_dist(s, distance, length, flush) \
627 		flush = _tr_tally(s, distance, length)
628 #endif
629 
630 #endif
631 /* --- deflate.h */
632 
633 /* +++ deflate.c */
634 /*
635  * deflate.c -- compress data using the deflation algorithm
636  * Copyright (C) 1995-1998 Jean-loup Gailly.
637  * For conditions of distribution and use, see copyright notice in zlib.h
638  */
639 
640 /*
641  *  ALGORITHM
642  *
643  *      The "deflation" process depends on being able to identify portions
644  *      of the input text which are identical to earlier input (within a
645  *      sliding window trailing behind the input currently being processed).
646  *
647  *      The most straightforward technique turns out to be the fastest for
648  *      most input files: try all possible matches and select the longest.
649  *      The key feature of this algorithm is that insertions into the string
650  *      dictionary are very simple and thus fast, and deletions are avoided
651  *      completely. Insertions are performed at each input character, whereas
652  *      string matches are performed only when the previous match ends. So it
653  *      is preferable to spend more time in matches to allow very fast string
654  *      insertions and avoid deletions. The matching algorithm for small
655  *      strings is inspired from that of Rabin & Karp. A brute force approach
656  *      is used to find longer strings when a small match has been found.
657  *      A similar algorithm is used in comic (by Jan-Mark Wams) and freeze
658  *      (by Leonid Broukhis).
659  *         A previous version of this file used a more sophisticated algorithm
660  *      (by Fiala and Greene) which is guaranteed to run in linear amortized
661  *      time, but has a larger average cost, uses more memory and is patented.
662  *      However the F&G algorithm may be faster for some highly redundant
663  *      files if the parameter max_chain_length (described below) is too large.
664  *
665  *  ACKNOWLEDGEMENTS
666  *
667  *      The idea of lazy evaluation of matches is due to Jan-Mark Wams, and
668  *      I found it in 'freeze' written by Leonid Broukhis.
669  *      Thanks to many people for bug reports and testing.
670  *
671  *  REFERENCES
672  *
673  *      Deutsch, L.P.,"DEFLATE Compressed Data Format Specification".
674  *      Available in ftp://ds.internic.net/rfc/rfc1951.txt
675  *
676  *      A description of the Rabin and Karp algorithm is given in the book
677  *         "Algorithms" by R. Sedgewick, Addison-Wesley, p252.
678  *
679  *      Fiala,E.R., and Greene,D.H.
680  *         Data Compression with Finite Windows, Comm.ACM, 32,4 (1989) 490-595
681  *
682  */
683 
684 /* From: deflate.c,v 1.15 1996/07/24 13:40:58 me Exp $ */
685 
686 /* #include "deflate.h" */
687 
688 const char deflate_copyright[] =
689 " deflate 1.1.3 Copyright 1995-1998 Jean-loup Gailly ";
690 /*
691  * If you use the zlib library in a product, an acknowledgment is
692  * welcome in the documentation of your product. If for some reason
693  * you cannot include such an acknowledgment, I would appreciate that
694  * you keep this copyright string in the executable of your product.
695  */
696 
697 /*
698  * ===========================================================================
699  *  Function prototypes.
700  */
701 typedef enum {
702 	/* block not completed, need more input or more output */
703 	need_more,
704 	block_done,	/* block flush performed */
705 	/* finish started, need only more output at next deflate */
706 	finish_started,
707 	finish_done	/* finish done, accept no more input or output */
708 } block_state;
709 
710 typedef block_state (*compress_func) OF((deflate_state *s, int flush));
711 /* Compression function. Returns the block state after the call. */
712 
713 local void fill_window	OF((deflate_state *s));
714 local block_state deflate_stored OF((deflate_state *s, int flush));
715 local block_state deflate_fast	OF((deflate_state *s, int flush));
716 local block_state deflate_slow	OF((deflate_state *s, int flush));
717 local void lm_init	OF((deflate_state *s));
718 local void putShortMSB	OF((deflate_state *s, uInt b));
719 local void flush_pending	OF((z_streamp strm));
720 local int read_buf	OF((z_streamp strm, Bytef *buf, unsigned size));
721 #ifdef ASMV
722 void match_init	OF((void));	/* asm code initialization */
723 uInt longest_match	OF((deflate_state *s, IPos cur_match));
724 #else
725 local uInt longest_match	OF((deflate_state *s, IPos cur_match));
726 #endif
727 
728 #ifdef DEBUG_ZLIB
729 local void check_match OF((deflate_state *s, IPos start, IPos match,
730     int length));
731 #endif
732 
733 /*
734  * ===========================================================================
735  * Local data
736  */
737 
738 #define	NIL 0
739 /* Tail of hash chains */
740 
741 #ifndef TOO_FAR
742 #define	TOO_FAR 4096
743 #endif
744 /* Matches of length 3 are discarded if their distance exceeds TOO_FAR */
745 
746 #define	MIN_LOOKAHEAD (MAX_MATCH+MIN_MATCH+1)
747 /*
748  * Minimum amount of lookahead, except at the end of the input file.
749  * See deflate.c for comments about the MIN_MATCH+1.
750  */
751 
752 /*
753  * Values for max_lazy_match, good_match and max_chain_length,
754  * depending on the desired pack level (0..9). The values given below
755  * have been tuned to exclude worst case performance for pathological
756  * files. Better values may be found for specific files.
757  */
758 typedef struct config_s {
759 	ush good_length;	/* reduce lazy search above this match length */
760 	ush max_lazy;	/* do not perform lazy search above this match length */
761 	ush nice_length;	/* quit search above this match length */
762 	ush max_chain;
763 	compress_func func;
764 } config;
765 
766 local const config configuration_table[10] = {
767 /*	good lazy nice chain */
768 /* 0 */ {0,    0,  0,    0, deflate_stored},  /* store only */
769 /* 1 */ {4,    4,  8,    4, deflate_fast}, /* maximum speed, no lazy matches */
770 /* 2 */ {4,    5, 16,    8, deflate_fast},
771 /* 3 */ {4,    6, 32,   32, deflate_fast},
772 
773 /* 4 */ {4,    4, 16,   16, deflate_slow},  /* lazy matches */
774 /* 5 */ {8,   16, 32,   32, deflate_slow},
775 /* 6 */ {8,   16, 128, 128, deflate_slow},
776 /* 7 */ {8,   32, 128, 256, deflate_slow},
777 /* 8 */ {32, 128, 258, 1024, deflate_slow},
778 /* 9 */ {32, 258, 258, 4096, deflate_slow}};	/* maximum compression */
779 
780 /*
781  * Note: the deflate() code requires max_lazy >= MIN_MATCH and max_chain >= 4
782  * For deflate_fast() (levels <= 3) good is ignored and lazy has a different
783  * meaning.
784  */
785 
786 #define	EQUAL 0
787 /* result of memcmp for equal strings */
788 
789 #ifndef NO_DUMMY_DECL
790 struct static_tree_desc_s {int dummy; };	/* for buggy compilers */
791 #endif
792 
793 /*
794  * ===========================================================================
795  * Update a hash value with the given input byte
796  * IN  assertion: all calls to to UPDATE_HASH are made with consecutive
797  *    input characters, so that a running hash key can be computed from the
798  *    previous key instead of complete recalculation each time.
799  */
800 #define	UPDATE_HASH(s, h, c) (h = (((h)<<s->hash_shift) ^ (c)) & s->hash_mask)
801 
802 
803 /*
804  * ===========================================================================
805  * Insert string str in the dictionary and set match_head to the previous head
806  * of the hash chain (the most recent string with same hash key). Return
807  * the previous length of the hash chain.
808  * If this file is compiled with -DFASTEST, the compression level is forced
809  * to 1, and no hash chains are maintained.
810  * IN  assertion: all calls to to INSERT_STRING are made with consecutive
811  *    input characters and the first MIN_MATCH bytes of str are valid
812  *    (except for the last MIN_MATCH-1 bytes of the input file).
813  */
814 #ifdef FASTEST
815 #define	INSERT_STRING(s, str, match_head) \
816 	(UPDATE_HASH(s, s->ins_h, s->window[(str) + (MIN_MATCH-1)]), \
817 	match_head = s->head[s->ins_h], \
818 	s->head[s->ins_h] = (Pos)(str))
819 #else
820 #define	INSERT_STRING(s, str, match_head) \
821 	(UPDATE_HASH(s, s->ins_h, s->window[(str) + (MIN_MATCH-1)]), \
822 	s->prev[(str) & s->w_mask] = match_head = s->head[s->ins_h], \
823 	s->head[s->ins_h] = (Pos)(str))
824 #endif
825 
826 /*
827  * ===========================================================================
828  * Initialize the hash table (avoiding 64K overflow for 16 bit systems).
829  * prev[] will be initialized on the fly.
830  */
831 #define	CLEAR_HASH(s) \
832     s->head[s->hash_size-1] = NIL; \
833     zmemzero((Bytef *)s->head, (unsigned)(s->hash_size-1)*sizeof (*s->head));
834 
835 /* ========================================================================= */
836 int
837 deflateInit_(strm, level, version, stream_size)
838     z_streamp strm;
839     int level;
840     const char *version;
841     int stream_size;
842 {
843 	(void) deflate_copyright;
844 	return deflateInit2_(strm, level, Z_DEFLATED, MAX_WBITS, DEF_MEM_LEVEL,
845 	    Z_DEFAULT_STRATEGY, version, stream_size);
846 	/* To do: ignore strm->next_in if we use it as window */
847 }
848 
849 /* ========================================================================= */
850 int deflateInit2_(strm, level, method, windowBits, memLevel, strategy,
851     version, stream_size)
852     z_streamp strm;
853     int  level;
854     int  method;
855     int  windowBits;
856     int  memLevel;
857     int  strategy;
858     const char *version;
859     int stream_size;
860 {
861 	deflate_state *s;
862 	int noheader = 0;
863 	static const char *my_version = ZLIB_VERSION;
864 
865 	ushf *overlay;
866 	/*
867 	 * We overlay pending_buf and d_buf+l_buf. This works since
868 	 * the average output size for (length, distance) codes is <=
869 	 * 24 bits.
870 	 */
871 
872 	if (version == Z_NULL || version[0] != my_version[0] ||
873 	    stream_size != sizeof (z_stream)) {
874 		return (Z_VERSION_ERROR);
875 	}
876 	if (strm == Z_NULL)
877 		return (Z_STREAM_ERROR);
878 
879 	strm->msg = Z_NULL;
880 #ifndef NO_ZCFUNCS
881 	if (strm->zalloc == Z_NULL) {
882 		strm->zalloc = zcalloc;
883 		strm->opaque = (voidpf)0;
884 	}
885 	if (strm->zfree == Z_NULL) strm->zfree = zcfree;
886 #endif
887 
888 	if (level == Z_DEFAULT_COMPRESSION) level = 6;
889 #ifdef FASTEST
890 	level = 1;
891 #endif
892 
893 	if (windowBits < 0) { /* undocumented feature: suppress zlib header */
894 		noheader = 1;
895 		windowBits = -windowBits;
896 	}
897 	if (memLevel < 1 || memLevel > MAX_MEM_LEVEL || method != Z_DEFLATED ||
898 	    windowBits <= 8 || windowBits > 15 || level < 0 || level > 9 ||
899 	    strategy < 0 || strategy > Z_HUFFMAN_ONLY) {
900 		return (Z_STREAM_ERROR);
901 	}
902 	s = (deflate_state *) ZALLOC(strm, 1, sizeof (deflate_state));
903 	if (s == Z_NULL)
904 		return (Z_MEM_ERROR);
905 	strm->state = (struct internal_state FAR *)s;
906 	s->strm = strm;
907 
908 	s->noheader = noheader;
909 	s->w_bits = windowBits;
910 	s->w_size = 1 << s->w_bits;
911 	s->w_mask = s->w_size - 1;
912 
913 	s->hash_bits = memLevel + 7;
914 	s->hash_size = 1 << s->hash_bits;
915 	s->hash_mask = s->hash_size - 1;
916 	s->hash_shift =  ((s->hash_bits+MIN_MATCH-1)/MIN_MATCH);
917 
918 	s->window = (Bytef *) ZALLOC(strm, s->w_size, 2*sizeof (Byte));
919 	s->prev   = (Posf *)  ZALLOC(strm, s->w_size, sizeof (Pos));
920 	s->head   = (Posf *)  ZALLOC(strm, s->hash_size, sizeof (Pos));
921 
922 	s->lit_bufsize = 1 << (memLevel + 6);	/* 16K elements by default */
923 
924 	overlay = (ushf *) ZALLOC(strm, s->lit_bufsize, sizeof (ush)+2);
925 	s->pending_buf = (uchf *) overlay;
926 	s->pending_buf_size = (ulg)s->lit_bufsize * (sizeof (ush)+2L);
927 
928 	if (s->window == Z_NULL || s->prev == Z_NULL || s->head == Z_NULL ||
929 	    s->pending_buf == Z_NULL) {
930 		strm->msg = ERR_MSG(Z_MEM_ERROR);
931 		s->status = INIT_STATE;
932 		(void) deflateEnd(strm);
933 		return (Z_MEM_ERROR);
934 	}
935 	s->d_buf = overlay + s->lit_bufsize/sizeof (ush);
936 	s->l_buf = s->pending_buf + (1+sizeof (ush))*s->lit_bufsize;
937 
938 	s->level = level;
939 	s->strategy = strategy;
940 	s->method = (Byte)method;
941 
942 	return (deflateReset(strm));
943 }
944 
945 /* ========================================================================= */
946 int
947 deflateSetDictionary(strm, dictionary, dictLength)
948     z_streamp strm;
949     const Bytef *dictionary;
950     uInt  dictLength;
951 {
952 	deflate_state *s;
953 	uInt length = dictLength;
954 	uInt n;
955 	IPos hash_head = 0;
956 
957 	if (strm == Z_NULL || strm->state == Z_NULL || dictionary == Z_NULL)
958 		return (Z_STREAM_ERROR);
959 
960 	s = (deflate_state *) strm->state;
961 	if (s->status != INIT_STATE)
962 		return (Z_STREAM_ERROR);
963 
964 	strm->adler = adler32(strm->adler, dictionary, dictLength);
965 
966 	if (length < MIN_MATCH)
967 		return (Z_OK);
968 	if (length > MAX_DIST(s)) {
969 		length = MAX_DIST(s);
970 #ifndef USE_DICT_HEAD
971 		/* use the tail of the dictionary */
972 		dictionary += dictLength - length;
973 #endif
974 	}
975 	Assert(length <= s->window_size, "dict copy");
976 	zmemcpy(s->window, dictionary, length);
977 	s->strstart = length;
978 	s->block_start = (long)length;
979 
980 	/*
981 	 * Insert all strings in the hash table (except for the last
982 	 * two bytes).  s->lookahead stays null, so s->ins_h will be
983 	 * recomputed at the next call of fill_window.
984 	 */
985 	s->ins_h = s->window[0];
986 	UPDATE_HASH(s, s->ins_h, s->window[1]);
987 	for (n = 0; n <= length - MIN_MATCH; n++) {
988 		INSERT_STRING(s, n, hash_head);
989 	}
990 	if (hash_head) hash_head = 0;	/* to make compiler happy */
991 	return (Z_OK);
992 }
993 
994 /* ========================================================================= */
995 int
996 deflateReset(strm)
997     z_streamp strm;
998 {
999 	deflate_state *s;
1000 
1001 	if (strm == Z_NULL || strm->state == Z_NULL ||
1002 	    strm->zalloc == Z_NULL || strm->zfree == Z_NULL)
1003 		return (Z_STREAM_ERROR);
1004 
1005 	strm->total_in = strm->total_out = 0;
1006 	/* use zfree if we ever allocate msg dynamically */
1007 	strm->msg = Z_NULL;
1008 	strm->data_type = Z_UNKNOWN;
1009 
1010 	s = (deflate_state *)strm->state;
1011 	s->pending = 0;
1012 	s->pending_out = s->pending_buf;
1013 
1014 	if (s->noheader < 0) {
1015 		/* was set to -1 by deflate(..., Z_FINISH); */
1016 		s->noheader = 0;
1017 	}
1018 	s->status = s->noheader ? BUSY_STATE : INIT_STATE;
1019 	strm->adler = 1;
1020 	s->last_flush = Z_NO_FLUSH;
1021 
1022 	_tr_init(s);
1023 	lm_init(s);
1024 
1025 	return (Z_OK);
1026 }
1027 
1028 /* ========================================================================= */
1029 int
1030 deflateParams(strm, level, strategy)
1031     z_streamp strm;
1032     int level;
1033     int strategy;
1034 {
1035 	deflate_state *s;
1036 	compress_func func;
1037 	int err = Z_OK;
1038 
1039 	if (strm == Z_NULL || strm->state == Z_NULL)
1040 		return (Z_STREAM_ERROR);
1041 	s = (deflate_state *) strm->state;
1042 
1043 	if (level == Z_DEFAULT_COMPRESSION) {
1044 		level = 6;
1045 	}
1046 	if (level < 0 || level > 9 || strategy < 0 ||
1047 	    strategy > Z_HUFFMAN_ONLY) {
1048 		return (Z_STREAM_ERROR);
1049 	}
1050 	func = configuration_table[s->level].func;
1051 
1052 	if (func != configuration_table[level].func && strm->total_in != 0) {
1053 		/* Flush the last buffer: */
1054 		err = deflate(strm, Z_PARTIAL_FLUSH);
1055 	}
1056 	if (s->level != level) {
1057 		s->level = level;
1058 		s->max_lazy_match   = configuration_table[level].max_lazy;
1059 		s->good_match	= configuration_table[level].good_length;
1060 		s->nice_match	= configuration_table[level].nice_length;
1061 		s->max_chain_length = configuration_table[level].max_chain;
1062 	}
1063 	s->strategy = strategy;
1064 	return (err);
1065 }
1066 
1067 /*
1068  * =========================================================================
1069  * Put a short in the pending buffer. The 16-bit value is put in MSB order.
1070  * IN assertion: the stream state is correct and there is enough room in
1071  * pending_buf.
1072  */
1073 local void
1074 putShortMSB(s, b)
1075     deflate_state *s;
1076     uInt b;
1077 {
1078 	put_byte(s, (Byte)(b >> 8));
1079 	put_byte(s, (Byte)(b & 0xff));
1080 }
1081 
1082 /*
1083  * =========================================================================
1084  * Flush as much pending output as possible. All deflate() output goes
1085  * through this function so some applications may wish to modify it
1086  * to avoid allocating a large strm->next_out buffer and copying into it.
1087  * (See also read_buf()).
1088  */
1089 local void
1090 flush_pending(strm)
1091     z_streamp strm;
1092 {
1093 	deflate_state *s = (deflate_state *) strm->state;
1094 	unsigned len = s->pending;
1095 
1096 	if (len > strm->avail_out) len = strm->avail_out;
1097 	if (len == 0)
1098 		return;
1099 
1100 	if (strm->next_out != Z_NULL) {		/* PPP */
1101 		zmemcpy(strm->next_out, s->pending_out, len);
1102 		strm->next_out += len;
1103 	}					/* PPP */
1104 	s->pending_out += len;
1105 	strm->total_out += len;
1106 	strm->avail_out  -= len;
1107 	s->pending -= len;
1108 	if (s->pending == 0) {
1109 		s->pending_out = s->pending_buf;
1110 	}
1111 }
1112 
1113 /* ========================================================================= */
1114 int
1115 deflate(strm, flush)
1116     z_streamp strm;
1117     int flush;
1118 {
1119 	int old_flush;	/* value of flush param for previous deflate call */
1120 	deflate_state *s;
1121 
1122 	if (strm == Z_NULL || strm->state == Z_NULL ||
1123 	    flush > Z_FINISH || flush < 0) {
1124 		return (Z_STREAM_ERROR);
1125 	}
1126 	s = (deflate_state *) strm->state;
1127 
1128 	if (/* strm->next_out == Z_NULL || --- we allow null --- PPP */
1129 		(strm->next_in == Z_NULL && strm->avail_in != 0) ||
1130 	    (s->status == FINISH_STATE && flush != Z_FINISH)) {
1131 		ERR_RETURN(strm, Z_STREAM_ERROR);
1132 	}
1133 	if (strm->avail_out == 0) ERR_RETURN(strm, Z_BUF_ERROR);
1134 
1135 	s->strm = strm;	/* just in case */
1136 	old_flush = s->last_flush;
1137 	s->last_flush = flush;
1138 
1139 	/* Write the zlib header */
1140 	if (s->status == INIT_STATE) {
1141 
1142 		uInt header = (Z_DEFLATED + ((s->w_bits-8)<<4)) << 8;
1143 		uInt level_flags = (s->level-1) >> 1;
1144 
1145 		if (level_flags > 3) level_flags = 3;
1146 		header |= (level_flags << 6);
1147 		if (s->strstart != 0) header |= PRESET_DICT;
1148 		header += 31 - (header % 31);
1149 
1150 		s->status = BUSY_STATE;
1151 		putShortMSB(s, header);
1152 
1153 		/* Save the adler32 of the preset dictionary: */
1154 		if (s->strstart != 0) {
1155 			putShortMSB(s, (uInt)(strm->adler >> 16));
1156 			putShortMSB(s, (uInt)(strm->adler & 0xffff));
1157 		}
1158 		strm->adler = 1L;
1159 	}
1160 
1161 	/* Flush as much pending output as possible */
1162 	if (s->pending != 0) {
1163 		flush_pending(strm);
1164 		if (strm->avail_out == 0) {
1165 			/*
1166 			 * Since avail_out is 0, deflate will be
1167 			 * called again with more output space, but
1168 			 * possibly with both pending and avail_in
1169 			 * equal to zero. There won't be anything to
1170 			 * do, but this is not an error situation so
1171 			 * make sure we return OK instead of BUF_ERROR
1172 			 * at next call of deflate:
1173 			 */
1174 			s->last_flush = -1;
1175 			return (Z_OK);
1176 		}
1177 
1178 		/*
1179 		 * Make sure there is something to do and avoid
1180 		 * duplicate consecutive flushes. For repeated and
1181 		 * useless calls with Z_FINISH, we keep returning
1182 		 * Z_STREAM_END instead of Z_BUFF_ERROR.
1183 		 */
1184 	} else if (strm->avail_in == 0 && flush <= old_flush &&
1185 	    flush != Z_FINISH) {
1186 		ERR_RETURN(strm, Z_BUF_ERROR);
1187 	}
1188 
1189 	/* User must not provide more input after the first FINISH: */
1190 	if (s->status == FINISH_STATE && strm->avail_in != 0) {
1191 		ERR_RETURN(strm, Z_BUF_ERROR);
1192 	}
1193 
1194 	/* Start a new block or continue the current one. */
1195 	if (strm->avail_in != 0 || s->lookahead != 0 ||
1196 	    (flush != Z_NO_FLUSH && s->status != FINISH_STATE)) {
1197 		block_state bstate;
1198 
1199 		bstate = (*(configuration_table[s->level].func))(s, flush);
1200 
1201 		if (bstate == finish_started || bstate == finish_done) {
1202 			s->status = FINISH_STATE;
1203 		}
1204 		if (bstate == need_more || bstate == finish_started) {
1205 			if (strm->avail_out == 0) {
1206 				/* avoid BUF_ERROR next call, see above */
1207 				s->last_flush = -1;
1208 			}
1209 			return (Z_OK);
1210 			/*
1211 			 * If flush != Z_NO_FLUSH && avail_out == 0,
1212 			 * the next call of deflate should use the
1213 			 * same flush parameter to make sure that the
1214 			 * flush is complete. So we don't have to
1215 			 * output an empty block here, this will be
1216 			 * done at next call. This also ensures that
1217 			 * for a very small output buffer, we emit at
1218 			 * most one empty block.
1219 			 */
1220 		}
1221 		if (bstate == block_done) {
1222 			if (flush == Z_PARTIAL_FLUSH) {
1223 				_tr_align(s);
1224 			} else if (flush == Z_PACKET_FLUSH) {	/* PPP */
1225 				/*
1226 				 * Output just the 3-bit `stored'
1227 				 * block type value, but not a zero
1228 				 * length.  Added for PPP.
1229 				 */
1230 				_tr_stored_type_only(s);	/* PPP */
1231 			} else { /* FULL_FLUSH or SYNC_FLUSH */
1232 				_tr_stored_block(s, (char *)0, 0L, 0);
1233 				/*
1234 				 * For a full flush, this empty block
1235 				 * will be recognized as a special
1236 				 * marker by inflate_sync().
1237 				 */
1238 				if (flush == Z_FULL_FLUSH) {
1239 					CLEAR_HASH(s);	/* forget history */
1240 				}
1241 			}
1242 			flush_pending(strm);
1243 			if (strm->avail_out == 0) {
1244 				/* avoid BUF_ERROR at next call, see above */
1245 				s->last_flush = -1;
1246 				return (Z_OK);
1247 			}
1248 		}
1249 	}
1250 	Assert(strm->avail_out > 0, "bug2");
1251 
1252 	if (flush != Z_FINISH)
1253 		return (Z_OK);
1254 	if (s->noheader)
1255 		return (Z_STREAM_END);
1256 
1257 	/* Write the zlib trailer (adler32) */
1258 	putShortMSB(s, (uInt)(strm->adler >> 16));
1259 	putShortMSB(s, (uInt)(strm->adler & 0xffff));
1260 	flush_pending(strm);
1261 	/*
1262 	 * If avail_out is zero, the application will call deflate
1263 	 * again to flush the rest.
1264 	 */
1265 	s->noheader = -1;	/* write the trailer only once! */
1266 	return (s->pending != 0 ? Z_OK : Z_STREAM_END);
1267 }
1268 
1269 /* ========================================================================= */
1270 int
1271 deflateEnd(strm)
1272     z_streamp strm;
1273 {
1274 	int status;
1275 	deflate_state *s;
1276 
1277 	if (strm == Z_NULL || strm->state == Z_NULL)
1278 		return (Z_STREAM_ERROR);
1279 	s = (deflate_state *) strm->state;
1280 
1281 	status = s->status;
1282 	if (status != INIT_STATE && status != BUSY_STATE &&
1283 	    status != FINISH_STATE) {
1284 		return (Z_STREAM_ERROR);
1285 	}
1286 
1287 	/* Deallocate in reverse order of allocations: */
1288 	TRY_FREE(strm, s->pending_buf);
1289 	TRY_FREE(strm, s->head);
1290 	TRY_FREE(strm, s->prev);
1291 	TRY_FREE(strm, s->window);
1292 
1293 	ZFREE(strm, s);
1294 	strm->state = Z_NULL;
1295 
1296 	return (status == BUSY_STATE ? Z_DATA_ERROR : Z_OK);
1297 }
1298 
1299 /*
1300  * =========================================================================
1301  * Copy the source state to the destination state.
1302  * To simplify the source, this is not supported for 16-bit MSDOS (which
1303  * doesn't have enough memory anyway to duplicate compression states).
1304  */
1305 int
1306 deflateCopy(dest, source)
1307     z_streamp dest;
1308     z_streamp source;
1309 {
1310 #ifdef MAXSEG_64K
1311 	return (Z_STREAM_ERROR);
1312 #else
1313 	deflate_state *ds;
1314 	deflate_state *ss;
1315 	ushf *overlay;
1316 
1317 	if (source == Z_NULL || dest == Z_NULL || source->state == Z_NULL)
1318 		return (Z_STREAM_ERROR);
1319 	ss = (deflate_state *) source->state;
1320 
1321 	zmemcpy(dest, source, sizeof (*dest));
1322 
1323 	ds = (deflate_state *) ZALLOC(dest, 1, sizeof (deflate_state));
1324 	if (ds == Z_NULL)
1325 		return (Z_MEM_ERROR);
1326 	dest->state = (struct internal_state FAR *) ds;
1327 	zmemcpy(ds, ss, sizeof (*ds));
1328 	ds->strm = dest;
1329 
1330 	ds->window = (Bytef *) ZALLOC(dest, ds->w_size, 2*sizeof (Byte));
1331 	ds->prev   = (Posf *)  ZALLOC(dest, ds->w_size, sizeof (Pos));
1332 	ds->head   = (Posf *)  ZALLOC(dest, ds->hash_size, sizeof (Pos));
1333 	overlay = (ushf *) ZALLOC(dest, ds->lit_bufsize, sizeof (ush)+2);
1334 	ds->pending_buf = (uchf *) overlay;
1335 
1336 	if (ds->window == Z_NULL || ds->prev == Z_NULL || ds->head == Z_NULL ||
1337 	    ds->pending_buf == Z_NULL) {
1338 		ds->status = INIT_STATE;
1339 		(void) deflateEnd(dest);
1340 		return (Z_MEM_ERROR);
1341 	}
1342 	/* following zmemcpy doesn't work for 16-bit MSDOS */
1343 	zmemcpy(ds->window, ss->window, ds->w_size * 2 * sizeof (Byte));
1344 	zmemcpy(ds->prev, ss->prev, ds->w_size * sizeof (Pos));
1345 	zmemcpy(ds->head, ss->head, ds->hash_size * sizeof (Pos));
1346 	zmemcpy(ds->pending_buf, ss->pending_buf, (uInt)ds->pending_buf_size);
1347 
1348 	ds->pending_out = ds->pending_buf + (ss->pending_out - ss->pending_buf);
1349 	ds->d_buf = overlay + ds->lit_bufsize/sizeof (ush);
1350 	ds->l_buf = ds->pending_buf + (1+sizeof (ush))*ds->lit_bufsize;
1351 
1352 	ds->l_desc.dyn_tree = ds->dyn_ltree;
1353 	ds->d_desc.dyn_tree = ds->dyn_dtree;
1354 	ds->bl_desc.dyn_tree = ds->bl_tree;
1355 
1356 	return (Z_OK);
1357 #endif
1358 }
1359 
1360 /*
1361  * ===========================================================================
1362  * Return the number of bytes of output which are immediately available
1363  * for output from the decompressor.		---PPP---
1364  */
1365 int
1366 deflateOutputPending(strm)
1367     z_streamp strm;
1368 {
1369 	if (strm == Z_NULL || strm->state == Z_NULL)
1370 		return (0);
1371 
1372 	return (((deflate_state *)(strm->state))->pending);
1373 }
1374 
1375 /*
1376  * ===========================================================================
1377  * Read a new buffer from the current input stream, update the adler32
1378  * and total number of bytes read.  All deflate() input goes through
1379  * this function so some applications may wish to modify it to avoid
1380  * allocating a large strm->next_in buffer and copying from it.
1381  * (See also flush_pending()).
1382  */
1383 local int
1384 read_buf(strm, buf, size)
1385     z_streamp strm;
1386     Bytef *buf;
1387     unsigned size;
1388 {
1389 	unsigned len = strm->avail_in;
1390 
1391 	if (len > size) len = size;
1392 	if (len == 0)
1393 		return (0);
1394 
1395 	strm->avail_in  -= len;
1396 
1397 	if (!((deflate_state *)(strm->state))->noheader) {
1398 		strm->adler = adler32(strm->adler, strm->next_in, len);
1399 	}
1400 	zmemcpy(buf, strm->next_in, len);
1401 	strm->next_in  += len;
1402 	strm->total_in += len;
1403 
1404 	return ((int)len);
1405 }
1406 
1407 /*
1408  * ===========================================================================
1409  * Initialize the "longest match" routines for a new zlib stream
1410  */
1411 local void
1412 lm_init(s)
1413     deflate_state *s;
1414 {
1415 	s->window_size = (ulg)2L*s->w_size;
1416 
1417 	CLEAR_HASH(s);
1418 
1419 	/* Set the default configuration parameters: */
1420 	s->max_lazy_match   = configuration_table[s->level].max_lazy;
1421 	s->good_match	= configuration_table[s->level].good_length;
1422 	s->nice_match	= configuration_table[s->level].nice_length;
1423 	s->max_chain_length = configuration_table[s->level].max_chain;
1424 
1425 	s->strstart = 0;
1426 	s->block_start = 0L;
1427 	s->lookahead = 0;
1428 	s->match_length = s->prev_length = MIN_MATCH-1;
1429 	s->match_available = 0;
1430 	s->ins_h = 0;
1431 #ifdef ASMV
1432 	match_init();	/* initialize the asm code */
1433 #endif
1434 }
1435 
1436 /*
1437  * ===========================================================================
1438  * Set match_start to the longest match starting at the given string and
1439  * return its length. Matches shorter or equal to prev_length are discarded,
1440  * in which case the result is equal to prev_length and match_start is
1441  * garbage.
1442  * IN assertions: cur_match is the head of the hash chain for the current
1443  *   string (strstart) and its distance is <= MAX_DIST, and prev_length >= 1
1444  * OUT assertion: the match length is not greater than s->lookahead.
1445  */
1446 #ifndef ASMV
1447 /*
1448  * For 80x86 and 680x0, an optimized version will be provided in
1449  * match.asm or match.S. The code will be functionally equivalent.
1450  */
1451 #ifndef FASTEST
1452 local uInt
1453 longest_match(s, cur_match)
1454     deflate_state *s;
1455     IPos cur_match;	/* current match */
1456 {
1457 	/* max hash chain length */
1458 	unsigned chain_length = s->max_chain_length;
1459 	register Bytef *scan = s->window + s->strstart;	/* current string */
1460 	register Bytef *match;	/* matched string */
1461 	register int len;	/* length of current match */
1462 	int best_len = s->prev_length;	/* best match length so far */
1463 	int nice_match = s->nice_match;	/* stop if match long enough */
1464 	IPos limit = s->strstart > (IPos)MAX_DIST(s) ?
1465 	    s->strstart - (IPos)MAX_DIST(s) : NIL;
1466 	/*
1467 	 * Stop when cur_match becomes <= limit. To simplify the code,
1468 	 * we prevent matches with the string of window index 0.
1469 	 */
1470 	Posf *prev = s->prev;
1471 	uInt wmask = s->w_mask;
1472 
1473 #ifdef UNALIGNED_OK
1474 	/*
1475 	 * Compare two bytes at a time. Note: this is not always
1476 	 * beneficial.  Try with and without -DUNALIGNED_OK to check.
1477 	 */
1478 	register Bytef *strend = s->window + s->strstart + MAX_MATCH - 1;
1479 	register ush scan_start = *(ushf*)scan;
1480 	register ush scan_end   = *(ushf*)(scan+best_len-1);
1481 #else
1482 	register Bytef *strend = s->window + s->strstart + MAX_MATCH;
1483 	register Byte scan_end1  = scan[best_len-1];
1484 	register Byte scan_end   = scan[best_len];
1485 #endif
1486 
1487 	/*
1488 	 * The code is optimized for HASH_BITS >= 8 and MAX_MATCH-2
1489 	 * multiple of 16.  It is easy to get rid of this optimization
1490 	 * if necessary.
1491 	 */
1492 	Assert(s->hash_bits >= 8 && MAX_MATCH == 258, "Code too clever");
1493 
1494 	/* Do not waste too much time if we already have a good match: */
1495 	if (s->prev_length >= s->good_match) {
1496 		chain_length >>= 2;
1497 	}
1498 	/*
1499 	 * Do not look for matches beyond the end of the input. This
1500 	 * is necessary to make deflate deterministic.
1501 	 */
1502 	if ((uInt)nice_match > s->lookahead) nice_match = s->lookahead;
1503 
1504 	Assert((ulg)s->strstart <= s->window_size-MIN_LOOKAHEAD,
1505 	    "need lookahead");
1506 
1507 	do {
1508 		Assert(cur_match <= s->strstart, "no future");
1509 		match = s->window + cur_match;
1510 
1511 		/*
1512 		 * Skip to next match if the match length cannot
1513 		 * increase or if the match length is less than 2:
1514 		 */
1515 #if (defined(UNALIGNED_OK) && MAX_MATCH == 258)
1516 		/*
1517 		 * This code assumes sizeof (unsigned short) == 2. Do
1518 		 * not use UNALIGNED_OK if your compiler uses a
1519 		 * different size.
1520 		 */
1521 		if (*(ushf*)(match+best_len-1) != scan_end ||
1522 		    *(ushf*)match != scan_start) continue;
1523 
1524 		/*
1525 		 * It is not necessary to compare scan[2] and match[2]
1526 		 * since they are always equal when the other bytes
1527 		 * match, given that the hash keys are equal and that
1528 		 * HASH_BITS >= 8. Compare 2 bytes at a time at
1529 		 * strstart+3, +5, ... up to strstart+257. We check
1530 		 * for insufficient lookahead only every 4th
1531 		 * comparison; the 128th check will be made at
1532 		 * strstart+257. If MAX_MATCH-2 is not a multiple of
1533 		 * 8, it is necessary to put more guard bytes at the
1534 		 * end of the window, or to check more often for
1535 		 * insufficient lookahead.
1536 		 */
1537 		Assert(scan[2] == match[2], "scan[2]?");
1538 		scan++, match++;
1539 		do {
1540 		} while (*(ushf *)(scan += 2) == *(ushf *)(match += 2) &&
1541 		    *(ushf *)(scan += 2) == *(ushf *)(match += 2) &&
1542 		    *(ushf *)(scan += 2) == *(ushf *)(match += 2) &&
1543 		    *(ushf *)(scan += 2) == *(ushf *)(match += 2) &&
1544 		    scan < strend);
1545 		/* The funny "do {}" generates better code on most compilers */
1546 
1547 		/* Here, scan <= window+strstart+257 */
1548 		Assert(scan <= s->window+(unsigned)(s->window_size-1),
1549 		    "wild scan");
1550 		if (*scan == *match) scan++;
1551 
1552 		len = (MAX_MATCH - 1) - (int)(strend-scan);
1553 		scan = strend - (MAX_MATCH-1);
1554 
1555 #else /* UNALIGNED_OK */
1556 
1557 		if (match[best_len]	!= scan_end	||
1558 		    match[best_len-1]	!= scan_end1	||
1559 		    *match		!= *scan	||
1560 		    *++match		!= scan[1])
1561 			continue;
1562 
1563 		/*
1564 		 * The check at best_len-1 can be removed because it
1565 		 * will be made again later. (This heuristic is not
1566 		 * always a win.)  It is not necessary to compare
1567 		 * scan[2] and match[2] since they are always equal
1568 		 * when the other bytes match, given that the hash
1569 		 * keys are equal and that HASH_BITS >= 8.
1570 		 */
1571 		scan += 2, match++;
1572 		Assert(*scan == *match, "match[2]?");
1573 
1574 		/*
1575 		 * We check for insufficient lookahead only every 8th
1576 		 * comparison; the 256th check will be made at
1577 		 * strstart+258.
1578 		 */
1579 		do {
1580 		} while (*++scan == *++match && *++scan == *++match &&
1581 		    *++scan == *++match && *++scan == *++match &&
1582 		    *++scan == *++match && *++scan == *++match &&
1583 		    *++scan == *++match && *++scan == *++match &&
1584 		    scan < strend);
1585 
1586 		Assert(scan <= s->window+(unsigned)(s->window_size-1),
1587 		    "wild scan");
1588 
1589 		len = MAX_MATCH - (int)(strend - scan);
1590 		scan = strend - MAX_MATCH;
1591 
1592 #endif /* UNALIGNED_OK */
1593 
1594 		if (len > best_len) {
1595 			s->match_start = cur_match;
1596 			best_len = len;
1597 			if (len >= nice_match) break;
1598 #ifdef UNALIGNED_OK
1599 			scan_end = *(ushf*)(scan+best_len-1);
1600 #else
1601 			scan_end1  = scan[best_len-1];
1602 			scan_end   = scan[best_len];
1603 #endif
1604 		}
1605 	} while ((cur_match = prev[cur_match & wmask]) > limit &&
1606 	    --chain_length != 0);
1607 
1608 	if ((uInt)best_len <= s->lookahead)
1609 		return (best_len);
1610 	return (s->lookahead);
1611 }
1612 #else /* FASTEST */
1613 /*
1614  * ---------------------------------------------------------------------------
1615  * Optimized version for level == 1 only
1616  */
1617 local uInt
1618 longest_match(s, cur_match)
1619 deflate_state *s;
1620 IPos cur_match;		/* current match */
1621 {
1622 	register Bytef *scan = s->window + s->strstart; /* current string */
1623 	register Bytef *match;		/* matched string */
1624 	register int len;			/* length of current match */
1625 	register Bytef *strend = s->window + s->strstart + MAX_MATCH;
1626 
1627 	/*
1628 	 * The code is optimized for HASH_BITS >= 8 and MAX_MATCH-2
1629 	 * multiple of 16.  It is easy to get rid of this optimization
1630 	 * if necessary.
1631 	 */
1632 	Assert(s->hash_bits >= 8 && MAX_MATCH == 258, "Code too clever");
1633 
1634 	Assert((ulg)s->strstart <= s->window_size-MIN_LOOKAHEAD,
1635 	    "need lookahead");
1636 
1637 	Assert(cur_match <= s->strstart, "no future");
1638 
1639 	match = s->window + cur_match;
1640 
1641 	/* Return failure if the match length is less than 2: */
1642 	if (match[0] != scan[0] || match[1] != scan[1])
1643 		return (MIN_MATCH-1);
1644 
1645 	/*
1646 	 * The check at best_len-1 can be removed because it will be
1647 	 * made again later. (This heuristic is not always a win.)  It
1648 	 * is not necessary to compare scan[2] and match[2] since they
1649 	 * are always equal when the other bytes match, given that the
1650 	 * hash keys are equal and that HASH_BITS >= 8.
1651 	 */
1652 	scan += 2, match += 2;
1653 	Assert(*scan == *match, "match[2]?");
1654 
1655 	/*
1656 	 * We check for insufficient lookahead only every 8th comparison;
1657 	 * the 256th check will be made at strstart+258.
1658 	 */
1659 	do {
1660 	} while (*++scan == *++match && *++scan == *++match &&
1661 	    *++scan == *++match && *++scan == *++match &&
1662 	    *++scan == *++match && *++scan == *++match &&
1663 	    *++scan == *++match && *++scan == *++match &&
1664 	    scan < strend);
1665 
1666 	Assert(scan <= s->window+(unsigned)(s->window_size-1), "wild scan");
1667 
1668 	len = MAX_MATCH - (int)(strend - scan);
1669 
1670 	if (len < MIN_MATCH)
1671 		return (MIN_MATCH - 1);
1672 
1673 	s->match_start = cur_match;
1674 	return (len <= s->lookahead ? len : s->lookahead);
1675 }
1676 #endif /* FASTEST */
1677 #endif /* ASMV */
1678 
1679 #ifdef DEBUG_ZLIB
1680 /*
1681  * ===========================================================================
1682  * Check that the match at match_start is indeed a match.
1683  */
1684 local void
1685 check_match(s, start, match, length)
1686     deflate_state *s;
1687     IPos start, match;
1688     int length;
1689 {
1690 	/* check that the match is indeed a match */
1691 	if (zmemcmp(s->window + match, s->window + start, length) != EQUAL) {
1692 		fprintf(stderr, " start %u, match %u, length %d\n",
1693 		    start, match, length);
1694 		do {
1695 			fprintf(stderr, "%c%c", s->window[match++],
1696 			    s->window[start++]);
1697 		} while (--length != 0);
1698 		z_error("invalid match");
1699 	}
1700 	if (z_verbose > 1) {
1701 		fprintf(stderr, "\\[%d,%d]", start-match, length);
1702 		do { putc(s->window[start++], stderr); } while (--length != 0);
1703 	}
1704 }
1705 #else
1706 #define	check_match(s, start, match, length)
1707 #endif
1708 
1709 /*
1710  * ===========================================================================
1711  * Fill the window when the lookahead becomes insufficient.
1712  * Updates strstart and lookahead.
1713  *
1714  * IN assertion: lookahead < MIN_LOOKAHEAD
1715  * OUT assertions: strstart <= window_size-MIN_LOOKAHEAD
1716  *    At least one byte has been read, or avail_in == 0; reads are
1717  *    performed for at least two bytes (required for the zip translate_eol
1718  *    option -- not supported here).
1719  */
1720 local void
1721 fill_window(s)
1722     deflate_state *s;
1723 {
1724 	register unsigned n, m;
1725 	register Posf *p;
1726 	unsigned more;	/* Amount of free space at the end of the window. */
1727 	uInt wsize = s->w_size;
1728 
1729 	do {
1730 		more = (unsigned)(s->window_size -(ulg)s->lookahead -
1731 		    (ulg)s->strstart);
1732 
1733 		/* Deal with !@#$% 64K limit: */
1734 		if (more == 0 && s->strstart == 0 && s->lookahead == 0) {
1735 			more = wsize;
1736 
1737 		} else if (more == (unsigned)(-1)) {
1738 			/*
1739 			 * Very unlikely, but possible on 16 bit
1740 			 * machine if strstart == 0 and lookahead == 1
1741 			 * (input done one byte at time)
1742 			 */
1743 			more--;
1744 
1745 			/*
1746 			 * If the window is almost full and there is
1747 			 * insufficient lookahead, move the upper half
1748 			 * to the lower one to make room in the upper
1749 			 * half.
1750 			 */
1751 		} else if (s->strstart >= wsize+MAX_DIST(s)) {
1752 
1753 			Assert(wsize+wsize <= s->window_size, "wsize*2");
1754 			zmemcpy(s->window, s->window+wsize, (unsigned)wsize);
1755 			s->match_start -= wsize;
1756 			/* we now have strstart >= MAX_DIST */
1757 			s->strstart    -= wsize;
1758 			s->block_start -= (long)wsize;
1759 
1760 			/*
1761 			 * Slide the hash table (could be avoided with
1762 			 * 32 bit values at the expense of memory
1763 			 * usage). We slide even when level == 0 to
1764 			 * keep the hash table consistent if we switch
1765 			 * back to level > 0 later. (Using level 0
1766 			 * permanently is not an optimal usage of
1767 			 * zlib, so we don't care about this
1768 			 * pathological case.)
1769 			 */
1770 			n = s->hash_size;
1771 			p = &s->head[n];
1772 			do {
1773 				m = *--p;
1774 				*p = (Pos)(m >= wsize ? m-wsize : NIL);
1775 			} while (--n);
1776 
1777 			n = wsize;
1778 #ifndef FASTEST
1779 			p = &s->prev[n];
1780 			do {
1781 				m = *--p;
1782 				*p = (Pos)(m >= wsize ? m-wsize : NIL);
1783 				/*
1784 				 * If n is not on any hash chain,
1785 				 * prev[n] is garbage but its value
1786 				 * will never be used.
1787 				 */
1788 			} while (--n);
1789 #endif
1790 			more += wsize;
1791 		}
1792 		if (s->strm->avail_in == 0)
1793 			return;
1794 
1795 		/*
1796 		 * If there was no sliding:
1797 		 *    strstart <= WSIZE+MAX_DIST-1 &&
1798 		 *	lookahead <= MIN_LOOKAHEAD - 1 &&
1799 		 *    more == window_size - lookahead - strstart
1800 		 * => more >= window_size - (MIN_LOOKAHEAD-1 + WSIZE +
1801 		 *	MAX_DIST-1)
1802 		 * => more >= window_size - 2*WSIZE + 2
1803 		 * In the BIG_MEM or MMAP case (not yet supported),
1804 		 *   window_size == input_size + MIN_LOOKAHEAD  &&
1805 		 *   strstart + s->lookahead <= input_size =>
1806 		 *	more >= MIN_LOOKAHEAD.
1807 		 * Otherwise, window_size == 2*WSIZE so more >= 2.
1808 		 * If there was sliding, more >= WSIZE. So in all cases,
1809 		 * more >= 2.
1810 		 */
1811 		Assert(more >= 2, "more < 2");
1812 		Assert(s->strstart + s->lookahead + more <= s->window_size,
1813 		    "read too much");
1814 
1815 		n = read_buf(s->strm, s->window + s->strstart + s->lookahead,
1816 		    more);
1817 		s->lookahead += n;
1818 
1819 		/* Initialize the hash value now that we have some input: */
1820 		if (s->lookahead >= MIN_MATCH) {
1821 			s->ins_h = s->window[s->strstart];
1822 			UPDATE_HASH(s, s->ins_h, s->window[s->strstart+1]);
1823 #if MIN_MATCH != 3
1824 			Call UPDATE_HASH() MIN_MATCH-3 more times
1825 #endif
1826 			    }
1827 		/*
1828 		 * If the whole input has less than MIN_MATCH bytes,
1829 		 * ins_h is garbage, but this is not important since
1830 		 * only literal bytes will be emitted.
1831 		 */
1832 
1833 	} while (s->lookahead < MIN_LOOKAHEAD && s->strm->avail_in != 0);
1834 }
1835 
1836 /*
1837  * ===========================================================================
1838  * Flush the current block, with given end-of-file flag.
1839  * IN assertion: strstart is set to the end of the current match.
1840  */
1841 #define	FLUSH_BLOCK_ONLY(s, eof) { \
1842 	_tr_flush_block(s, (s->block_start >= 0L ? \
1843 		(charf *)&s->window[(unsigned)s->block_start] : \
1844 		(charf *)Z_NULL), \
1845 		(ulg)((long)s->strstart - s->block_start), \
1846 		(eof)); \
1847 	s->block_start = s->strstart; \
1848 	flush_pending(s->strm); \
1849 	Tracev((stderr, "[FLUSH]")); \
1850 }
1851 
1852 /* Same but force premature exit if necessary. */
1853 #define	FLUSH_BLOCK(s, eof) { \
1854 	FLUSH_BLOCK_ONLY(s, eof); \
1855 	if (s->strm->avail_out == 0) \
1856 		return ((eof) ? finish_started : need_more); \
1857 }
1858 
1859 /*
1860  * ===========================================================================
1861  * Copy without compression as much as possible from the input stream, return
1862  * the current block state.
1863  * This function does not insert new strings in the dictionary since
1864  * uncompressible data is probably not useful. This function is used
1865  * only for the level=0 compression option.
1866  * NOTE: this function should be optimized to avoid extra copying from
1867  * window to pending_buf.
1868  */
1869 local block_state
1870 deflate_stored(s, flush)
1871     deflate_state *s;
1872     int flush;
1873 {
1874 	/*
1875 	 * Stored blocks are limited to 0xffff bytes, pending_buf is
1876 	 * limited to pending_buf_size, and each stored block has a 5
1877 	 * byte header:
1878 	 */
1879 	ulg max_block_size = 0xffff;
1880 	ulg max_start;
1881 
1882 	if (max_block_size > s->pending_buf_size - 5) {
1883 		max_block_size = s->pending_buf_size - 5;
1884 	}
1885 
1886 	/* Copy as much as possible from input to output: */
1887 	for (;;) {
1888 		/* Fill the window as much as possible: */
1889 		if (s->lookahead <= 1) {
1890 
1891 			Assert(s->strstart < s->w_size+MAX_DIST(s) ||
1892 			    s->block_start >= (long)s->w_size,
1893 			    "slide too late");
1894 
1895 			fill_window(s);
1896 			if (s->lookahead == 0 && flush == Z_NO_FLUSH)
1897 				return (need_more);
1898 
1899 			if (s->lookahead == 0)
1900 				break;	/* flush the current block */
1901 		}
1902 		Assert(s->block_start >= 0L, "block gone");
1903 
1904 		s->strstart += s->lookahead;
1905 		s->lookahead = 0;
1906 
1907 		/* Emit a stored block if pending_buf will be full: */
1908 		max_start = s->block_start + max_block_size;
1909 		if (s->strstart == 0 || (ulg)s->strstart >= max_start) {
1910 			/*
1911 			 * strstart == 0 is possible when wraparound
1912 			 * on 16-bit machine
1913 			 */
1914 			s->lookahead = (uInt)(s->strstart - max_start);
1915 			s->strstart = (uInt)max_start;
1916 			FLUSH_BLOCK(s, 0);
1917 		}
1918 		/*
1919 		 * Flush if we may have to slide, otherwise
1920 		 * block_start may become negative and the data will
1921 		 * be gone:
1922 		 */
1923 		if (s->strstart - (uInt)s->block_start >= MAX_DIST(s)) {
1924 			FLUSH_BLOCK(s, 0);
1925 		}
1926 	}
1927 	FLUSH_BLOCK(s, flush == Z_FINISH);
1928 	return (flush == Z_FINISH ? finish_done : block_done);
1929 }
1930 
1931 /*
1932  * ===========================================================================
1933  * Compress as much as possible from the input stream, return the current
1934  * block state.
1935  * This function does not perform lazy evaluation of matches and inserts
1936  * new strings in the dictionary only for unmatched strings or for short
1937  * matches. It is used only for the fast compression options.
1938  */
1939 local block_state
1940 deflate_fast(s, flush)
1941     deflate_state *s;
1942     int flush;
1943 {
1944 	IPos hash_head = NIL;	/* head of the hash chain */
1945 	int bflush;	/* set if current block must be flushed */
1946 
1947 	for (;;) {
1948 		/*
1949 		 * Make sure that we always have enough lookahead,
1950 		 * except at the end of the input file. We need
1951 		 * MAX_MATCH bytes for the next match, plus MIN_MATCH
1952 		 * bytes to insert the string following the next
1953 		 * match.
1954 		 */
1955 		if (s->lookahead < MIN_LOOKAHEAD) {
1956 			fill_window(s);
1957 			if (s->lookahead < MIN_LOOKAHEAD &&
1958 			    flush == Z_NO_FLUSH) {
1959 				return (need_more);
1960 			}
1961 			if (s->lookahead == 0)
1962 				break;	/* flush the current block */
1963 		}
1964 
1965 		/*
1966 		 * Insert the string window[strstart .. strstart+2] in
1967 		 * the dictionary, and set hash_head to the head of
1968 		 * the hash chain:
1969 		 */
1970 		if (s->lookahead >= MIN_MATCH) {
1971 			INSERT_STRING(s, s->strstart, hash_head);
1972 		}
1973 
1974 		/*
1975 		 * Find the longest match, discarding those <=
1976 		 * prev_length.  At this point we have always
1977 		 * match_length < MIN_MATCH
1978 		 */
1979 		if (hash_head != NIL && s->strstart - hash_head <=
1980 		    MAX_DIST(s)) {
1981 			/*
1982 			 * To simplify the code, we prevent matches
1983 			 * with the string of window index 0 (in
1984 			 * particular we have to avoid a match of the
1985 			 * string with itself at the start of the
1986 			 * input file).
1987 			 */
1988 			if (s->strategy != Z_HUFFMAN_ONLY) {
1989 				s->match_length = longest_match(s, hash_head);
1990 			}
1991 			/* longest_match() sets match_start */
1992 		}
1993 		if (s->match_length >= MIN_MATCH) {
1994 			check_match(s, s->strstart, s->match_start,
1995 			    s->match_length);
1996 
1997 			_tr_tally_dist(s, s->strstart - s->match_start,
1998 			    s->match_length - MIN_MATCH, bflush);
1999 
2000 			s->lookahead -= s->match_length;
2001 
2002 			/*
2003 			 * Insert new strings in the hash table only
2004 			 * if the match length is not too large. This
2005 			 * saves time but degrades compression.
2006 			 */
2007 #ifndef FASTEST
2008 			if (s->match_length <= s->max_insert_length &&
2009 			    s->lookahead >= MIN_MATCH) {
2010 				/* string at strstart already in hash table */
2011 				s->match_length--;
2012 				do {
2013 					s->strstart++;
2014 					INSERT_STRING(s, s->strstart,
2015 					    hash_head);
2016 					/*
2017 					 * strstart never exceeds
2018 					 * WSIZE-MAX_MATCH, so there
2019 					 * are always MIN_MATCH bytes
2020 					 * ahead.
2021 					 */
2022 				} while (--s->match_length != 0);
2023 				s->strstart++;
2024 			} else
2025 #endif
2026 			{
2027 				s->strstart += s->match_length;
2028 				s->match_length = 0;
2029 				s->ins_h = s->window[s->strstart];
2030 				UPDATE_HASH(s, s->ins_h,
2031 				    s->window[s->strstart+1]);
2032 #if MIN_MATCH != 3
2033 				Call UPDATE_HASH() MIN_MATCH-3 more times
2034 #endif
2035 				/*
2036 				 * If lookahead < MIN_MATCH, ins_h is
2037 				 * garbage, but it does not matter
2038 				 * since it will be recomputed at next
2039 				 * deflate call.
2040 				 */
2041 			}
2042 		} else {
2043 			/* No match, output a literal byte */
2044 			Tracevv((stderr, "%c", s->window[s->strstart]));
2045 			_tr_tally_lit(s, s->window[s->strstart], bflush);
2046 			s->lookahead--;
2047 			s->strstart++;
2048 		}
2049 		if (bflush) FLUSH_BLOCK(s, 0);
2050 	}
2051 	FLUSH_BLOCK(s, flush == Z_FINISH);
2052 	return (flush == Z_FINISH ? finish_done : block_done);
2053 }
2054 
2055 /*
2056  * ===========================================================================
2057  * Same as above, but achieves better compression. We use a lazy
2058  * evaluation for matches: a match is finally adopted only if there is
2059  * no better match at the next window position.
2060  */
2061 local block_state
2062 deflate_slow(s, flush)
2063     deflate_state *s;
2064     int flush;
2065 {
2066 	IPos hash_head = NIL;	/* head of hash chain */
2067 	int bflush;	/* set if current block must be flushed */
2068 
2069 	/* Process the input block. */
2070 	for (;;) {
2071 		/*
2072 		 * Make sure that we always have enough lookahead,
2073 		 * except at the end of the input file. We need
2074 		 * MAX_MATCH bytes for the next match, plus MIN_MATCH
2075 		 * bytes to insert the string following the next
2076 		 * match.
2077 		 */
2078 		if (s->lookahead < MIN_LOOKAHEAD) {
2079 			fill_window(s);
2080 			if (s->lookahead < MIN_LOOKAHEAD &&
2081 			    flush == Z_NO_FLUSH) {
2082 				return (need_more);
2083 			}
2084 			/* flush the current block */
2085 			if (s->lookahead == 0)
2086 				break;
2087 		}
2088 
2089 		/*
2090 		 * Insert the string window[strstart .. strstart+2] in
2091 		 * the dictionary, and set hash_head to the head of
2092 		 * the hash chain:
2093 		 */
2094 		if (s->lookahead >= MIN_MATCH) {
2095 			INSERT_STRING(s, s->strstart, hash_head);
2096 		}
2097 
2098 		/*
2099 		 * Find the longest match, discarding those <=
2100 		 * prev_length.
2101 		 */
2102 		s->prev_length = s->match_length;
2103 		s->prev_match = s->match_start;
2104 		s->match_length = MIN_MATCH-1;
2105 
2106 		if (hash_head != NIL && s->prev_length < s->max_lazy_match &&
2107 		    s->strstart - hash_head <= MAX_DIST(s)) {
2108 			/*
2109 			 * To simplify the code, we prevent matches
2110 			 * with the string of window index 0 (in
2111 			 * particular we have to avoid a match of the
2112 			 * string with itself at the start of the
2113 			 * input file).
2114 			 */
2115 			if (s->strategy != Z_HUFFMAN_ONLY) {
2116 				s->match_length = longest_match(s, hash_head);
2117 			}
2118 			/* longest_match() sets match_start */
2119 
2120 			if (s->match_length <= 5 &&
2121 			    (s->strategy == Z_FILTERED ||
2122 				(s->match_length == MIN_MATCH &&
2123 				    s->strstart - s->match_start > TOO_FAR))) {
2124 
2125 				/*
2126 				 * If prev_match is also MIN_MATCH,
2127 				 * match_start is garbage but we will
2128 				 * ignore the current match anyway.
2129 				 */
2130 				s->match_length = MIN_MATCH-1;
2131 			}
2132 		}
2133 		/*
2134 		 * If there was a match at the previous step and the
2135 		 * current match is not better, output the previous
2136 		 * match:
2137 		 */
2138 		if (s->prev_length >= MIN_MATCH &&
2139 		    s->match_length <= s->prev_length) {
2140 			uInt max_insert = s->strstart + s->lookahead -
2141 			    MIN_MATCH;
2142 			/* Do not insert strings in hash table beyond this. */
2143 
2144 			check_match(s, s->strstart-1, s->prev_match,
2145 			    s->prev_length);
2146 
2147 			_tr_tally_dist(s, s->strstart -1 - s->prev_match,
2148 			    s->prev_length - MIN_MATCH, bflush);
2149 
2150 			/*
2151 			 * Insert in hash table all strings up to the
2152 			 * end of the match.  strstart-1 and strstart
2153 			 * are already inserted. If there is not
2154 			 * enough lookahead, the last two strings are
2155 			 * not inserted in the hash table.
2156 			 */
2157 			s->lookahead -= s->prev_length-1;
2158 			s->prev_length -= 2;
2159 			do {
2160 				if (++s->strstart <= max_insert) {
2161 					INSERT_STRING(s, s->strstart,
2162 					    hash_head);
2163 				}
2164 			} while (--s->prev_length != 0);
2165 			s->match_available = 0;
2166 			s->match_length = MIN_MATCH-1;
2167 			s->strstart++;
2168 
2169 			if (bflush) FLUSH_BLOCK(s, 0);
2170 
2171 		} else if (s->match_available) {
2172 			/*
2173 			 * If there was no match at the previous
2174 			 * position, output a single literal. If there
2175 			 * was a match but the current match is
2176 			 * longer, truncate the previous match to a
2177 			 * single literal.
2178 			 */
2179 			Tracevv((stderr, "%c", s->window[s->strstart-1]));
2180 			_tr_tally_lit(s, s->window[s->strstart-1], bflush);
2181 			if (bflush) {
2182 				FLUSH_BLOCK_ONLY(s, 0);
2183 			}
2184 			s->strstart++;
2185 			s->lookahead--;
2186 			if (s->strm->avail_out == 0)
2187 				return (need_more);
2188 		} else {
2189 			/*
2190 			 * There is no previous match to compare with,
2191 			 * wait for the next step to decide.
2192 			 */
2193 			s->match_available = 1;
2194 			s->strstart++;
2195 			s->lookahead--;
2196 		}
2197 	}
2198 	Assert(flush != Z_NO_FLUSH, "no flush?");
2199 	if (s->match_available) {
2200 		Tracevv((stderr, "%c", s->window[s->strstart-1]));
2201 		_tr_tally_lit(s, s->window[s->strstart-1], bflush);
2202 		s->match_available = 0;
2203 	}
2204 	FLUSH_BLOCK(s, flush == Z_FINISH);
2205 	return (flush == Z_FINISH ? finish_done : block_done);
2206 }
2207 /* --- deflate.c */
2208 
2209 /* +++ trees.c */
2210 /*
2211  * trees.c -- output deflated data using Huffman coding
2212  * Copyright (C) 1995-1998 Jean-loup Gailly
2213  * For conditions of distribution and use, see copyright notice in zlib.h
2214  */
2215 
2216 /*
2217  *  ALGORITHM
2218  *
2219  *      The "deflation" process uses several Huffman trees. The more
2220  *      common source values are represented by shorter bit sequences.
2221  *
2222  *      Each code tree is stored in a compressed form which is itself
2223  * a Huffman encoding of the lengths of all the code strings (in
2224  * ascending order by source values).  The actual code strings are
2225  * reconstructed from the lengths in the inflate process, as described
2226  * in the deflate specification.
2227  *
2228  *  REFERENCES
2229  *
2230  *      Deutsch, L.P.,"'Deflate' Compressed Data Format Specification".
2231  *      Available in ftp.uu.net:/pub/archiving/zip/doc/deflate-1.1.doc
2232  *
2233  *      Storer, James A.
2234  *          Data Compression:  Methods and Theory, pp. 49-50.
2235  *          Computer Science Press, 1988.  ISBN 0-7167-8156-5.
2236  *
2237  *      Sedgewick, R.
2238  *          Algorithms, p290.
2239  *          Addison-Wesley, 1983. ISBN 0-201-06672-6.
2240  */
2241 
2242 /* From: trees.c,v 1.11 1996/07/24 13:41:06 me Exp $ */
2243 
2244 /* #include "deflate.h" */
2245 
2246 #ifdef DEBUG_ZLIB
2247 #include <ctype.h>
2248 #endif
2249 
2250 /*
2251  * ===========================================================================
2252  * Constants
2253  */
2254 
2255 #define	MAX_BL_BITS 7
2256 /* Bit length codes must not exceed MAX_BL_BITS bits */
2257 
2258 #define	END_BLOCK 256
2259 /* end of block literal code */
2260 
2261 #define	REP_3_6		16
2262 /* repeat previous bit length 3-6 times (2 bits of repeat count) */
2263 
2264 #define	REPZ_3_10	17
2265 /* repeat a zero length 3-10 times  (3 bits of repeat count) */
2266 
2267 #define	REPZ_11_138	18
2268 /* repeat a zero length 11-138 times  (7 bits of repeat count) */
2269 
2270 /* extra bits for each length code */
2271 local const int extra_lbits[LENGTH_CODES] = {
2272 	0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 2, 2, 2, 2, 3, 3, 3, 3, 4,
2273 	4, 4, 4, 5, 5, 5, 5, 0};
2274 
2275 /* extra bits for each distance code */
2276 local const int extra_dbits[D_CODES] = {
2277 	0, 0, 0, 0, 1, 1, 2, 2, 3, 3, 4, 4, 5, 5, 6, 6, 7, 7, 8, 8, 9,
2278 	9, 10, 10, 11, 11, 12, 12, 13, 13};
2279 
2280 /* extra bits for each bit length code */
2281 local const int extra_blbits[BL_CODES] = {
2282 	0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 2, 3, 7};
2283 
2284 local const uch bl_order[BL_CODES] = {
2285 	16, 17, 18, 0, 8, 7, 9, 6, 10, 5, 11, 4, 12, 3, 13, 2, 14, 1, 15};
2286 
2287 /*
2288  * The lengths of the bit length codes are sent in order of decreasing
2289  * probability, to avoid transmitting the lengths for unused bit
2290  * length codes.
2291  */
2292 
2293 #define	Buf_size (8 * 2*sizeof (char))
2294 /*
2295  * Number of bits used within bi_buf. (bi_buf might be implemented on
2296  * more than 16 bits on some systems.)
2297  */
2298 
2299 /*
2300  * ===========================================================================
2301  * Local data. These are initialized only once.
2302  */
2303 #define	DIST_CODE_LEN  512 /* see definition of array dist_code below */
2304 
2305 local ct_data static_ltree[L_CODES+2];
2306 /*
2307  * The static literal tree. Since the bit lengths are imposed, there
2308  * is no need for the L_CODES extra codes used during heap
2309  * construction. However The codes 286 and 287 are needed to build a
2310  * canonical tree (see _tr_init below).
2311  */
2312 
2313 local ct_data static_dtree[D_CODES];
2314 /*
2315  * The static distance tree. (Actually a trivial tree since all codes
2316  * use 5 bits.)
2317  */
2318 
2319 local uch _dist_code[512];
2320 /*
2321  * distance codes. The first 256 values correspond to the distances 3
2322  * .. 258, the last 256 values correspond to the top 8 bits of the 15
2323  * bit distances.
2324  */
2325 
2326 local uch _length_code[MAX_MATCH-MIN_MATCH+1];
2327 /* length code for each normalized match length (0 == MIN_MATCH) */
2328 
2329 local int base_length[LENGTH_CODES];
2330 /* First normalized length for each code (0 = MIN_MATCH) */
2331 
2332 local int base_dist[D_CODES];
2333 /* First normalized distance for each code (0 = distance of 1) */
2334 
2335 struct static_tree_desc_s {
2336 	const ct_data *static_tree;	/* static tree or NULL */
2337 	const intf    *extra_bits;	/* extra bits for each code or NULL */
2338 	int	extra_base;	/* base index for extra_bits */
2339 	int	elems;	/* max number of elements in the tree */
2340 	int	max_length;	/* max bit length for the codes */
2341 };
2342 
2343 local static_tree_desc  static_l_desc = {
2344 	static_ltree, extra_lbits, LITERALS+1,	L_CODES, MAX_BITS};
2345 
2346 local static_tree_desc  static_d_desc = {
2347 	static_dtree, extra_dbits, 0,		D_CODES, MAX_BITS};
2348 
2349 local static_tree_desc  static_bl_desc = {
2350 	(const ct_data *)0, extra_blbits, 0,		BL_CODES, MAX_BL_BITS};
2351 
2352 /*
2353  * ===========================================================================
2354  * Local (static) routines in this file.
2355  */
2356 
2357 local void tr_static_init OF((void));
2358 local void init_block	OF((deflate_state *s));
2359 local void pqdownheap	OF((deflate_state *s, ct_data *tree, int k));
2360 local void gen_bitlen	OF((deflate_state *s, tree_desc *desc));
2361 local void gen_codes	OF((ct_data *tree, int max_code, ushf *bl_count));
2362 local void build_tree	OF((deflate_state *s, tree_desc *desc));
2363 local void scan_tree	OF((deflate_state *s, ct_data *tree, int max_code));
2364 local void send_tree	OF((deflate_state *s, ct_data *tree, int max_code));
2365 local int  build_bl_tree	OF((deflate_state *s));
2366 local void send_all_trees	OF((deflate_state *s, int lcodes, int dcodes,
2367     int blcodes));
2368 local void compress_block OF((deflate_state *s, ct_data *ltree,
2369     ct_data *dtree));
2370 local void set_data_type	OF((deflate_state *s));
2371 local unsigned bi_reverse	OF((unsigned value, int length));
2372 local void bi_windup	OF((deflate_state *s));
2373 local void bi_flush	OF((deflate_state *s));
2374 local void copy_block	OF((deflate_state *s, charf *buf, unsigned len,
2375     int header));
2376 
2377 #ifndef DEBUG_ZLIB
2378 #define	send_code(s, c, tree) send_bits(s, tree[c].Code, tree[c].Len)
2379 /* Send a code of the given tree. c and tree must not have side effects */
2380 
2381 #else /* DEBUG_ZLIB */
2382 #define	send_code(s, c, tree) \
2383 	{ if (z_verbose > 2) fprintf(stderr, "\ncd %3d ", (c)); \
2384 	send_bits(s, tree[c].Code, tree[c].Len); }
2385 #endif
2386 
2387 /*
2388  * ===========================================================================
2389  * Output a short LSB first on the stream.
2390  * IN assertion: there is enough room in pendingBuf.
2391  */
2392 #define	put_short(s, w) { \
2393 	put_byte(s, (uch)((w) & 0xff)); \
2394 	put_byte(s, (uch)((ush)(w) >> 8)); \
2395 }
2396 
2397 /*
2398  * ===========================================================================
2399  * Send a value on a given number of bits.
2400  * IN assertion: length <= 16 and value fits in length bits.
2401  */
2402 #ifdef DEBUG_ZLIB
2403 local void send_bits	OF((deflate_state *s, int value, int length));
2404 
2405 local void
2406 send_bits(s, value, length)
2407     deflate_state *s;
2408     int value;	/* value to send */
2409     int length;	/* number of bits */
2410 {
2411 	Tracevv((stderr, " l %2d v %4x ", length, value));
2412 	Assert(length > 0 && length <= 15, "invalid length");
2413 	s->bits_sent += (ulg)length;
2414 
2415 	/*
2416 	 * If not enough room in bi_buf, use (valid) bits from bi_buf
2417 	 * and (16 - bi_valid) bits from value, leaving (width -
2418 	 * (16-bi_valid)) unused bits in value.
2419 	 */
2420 	if (s->bi_valid > (int)Buf_size - length) {
2421 		s->bi_buf |= (value << s->bi_valid);
2422 		put_short(s, s->bi_buf);
2423 		s->bi_buf = (ush)value >> (Buf_size - s->bi_valid);
2424 		s->bi_valid += length - Buf_size;
2425 	} else {
2426 		s->bi_buf |= value << s->bi_valid;
2427 		s->bi_valid += length;
2428 	}
2429 }
2430 #else /* !DEBUG_ZLIB */
2431 
2432 #define	send_bits(s, value, length) \
2433 {	int len = length; \
2434 	if (s->bi_valid > (int)Buf_size - len) {\
2435 		int val = value; \
2436 		s->bi_buf |= (val << s->bi_valid); \
2437 		put_short(s, s->bi_buf); \
2438 		s->bi_buf = (ush)val >> (Buf_size - s->bi_valid); \
2439 		s->bi_valid += len - Buf_size; \
2440 	} else {\
2441 		s->bi_buf |= (value) << s->bi_valid; \
2442 		s->bi_valid += len; \
2443 	}\
2444 }
2445 #endif /* DEBUG_ZLIB */
2446 
2447 
2448 #define	MAX(a, b) (a >= b ? a : b)
2449 /* the arguments must not have side effects */
2450 
2451 /*
2452  * ===========================================================================
2453  * Initialize the various 'constant' tables. In a multi-threaded environment,
2454  * this function may be called by two threads concurrently, but this is
2455  * harmless since both invocations do exactly the same thing.
2456  */
2457 local void
2458 tr_static_init()
2459 {
2460 	static int static_init_done = 0;
2461 	int n;	/* iterates over tree elements */
2462 	int bits;	/* bit counter */
2463 	int length;	/* length value */
2464 	int code;	/* code value */
2465 	int dist;	/* distance index */
2466 	ush bl_count[MAX_BITS+1];
2467 	/* number of codes at each bit length for an optimal tree */
2468 
2469 	if (static_init_done)
2470 		return;
2471 
2472 	/* For some embedded targets, global variables are not initialized: */
2473 	static_l_desc.static_tree = static_ltree;
2474 	static_l_desc.extra_bits = extra_lbits;
2475 	static_d_desc.static_tree = static_dtree;
2476 	static_d_desc.extra_bits = extra_dbits;
2477 	static_bl_desc.extra_bits = extra_blbits;
2478 
2479 	/* Initialize the mapping length (0..255) -> length code (0..28) */
2480 	length = 0;
2481 	for (code = 0; code < LENGTH_CODES-1; code++) {
2482 		base_length[code] = length;
2483 		for (n = 0; n < (1<<extra_lbits[code]); n++) {
2484 			_length_code[length++] = (uch)code;
2485 		}
2486 	}
2487 	Assert(length == 256, "tr_static_init: length != 256");
2488 	/*
2489 	 * Note that the length 255 (match length 258) can be
2490 	 * represented in two different ways: code 284 + 5 bits or
2491 	 * code 285, so we overwrite _length_code[255] to use the best
2492 	 * encoding:
2493 	 */
2494 	_length_code[length-1] = (uch)code;
2495 
2496 	/* Initialize the mapping dist (0..32K) -> dist code (0..29) */
2497 	dist = 0;
2498 	for (code = 0; code < 16; code++) {
2499 		base_dist[code] = dist;
2500 		for (n = 0; n < (1<<extra_dbits[code]); n++) {
2501 			_dist_code[dist++] = (uch)code;
2502 		}
2503 	}
2504 	Assert(dist == 256, "tr_static_init: dist != 256");
2505 	dist >>= 7;	/* from now on, all distances are divided by 128 */
2506 	for (; code < D_CODES; code++) {
2507 		base_dist[code] = dist << 7;
2508 		for (n = 0; n < (1<<(extra_dbits[code]-7)); n++) {
2509 			_dist_code[256 + dist++] = (uch)code;
2510 		}
2511 	}
2512 	Assert(dist == 256, "tr_static_init: 256+dist != 512");
2513 
2514 	/* Construct the codes of the static literal tree */
2515 	for (bits = 0; bits <= MAX_BITS; bits++) bl_count[bits] = 0;
2516 	n = 0;
2517 	while (n <= 143) static_ltree[n++].Len = 8, bl_count[8]++;
2518 	while (n <= 255) static_ltree[n++].Len = 9, bl_count[9]++;
2519 	while (n <= 279) static_ltree[n++].Len = 7, bl_count[7]++;
2520 	while (n <= 287) static_ltree[n++].Len = 8, bl_count[8]++;
2521 	/*
2522 	 * Codes 286 and 287 do not exist, but we must include them in the
2523 	 * tree construction to get a canonical Huffman tree (longest code
2524 	 * all ones)
2525 	 */
2526 	gen_codes((ct_data *)static_ltree, L_CODES+1, bl_count);
2527 
2528 	/* The static distance tree is trivial: */
2529 	for (n = 0; n < D_CODES; n++) {
2530 		static_dtree[n].Len = 5;
2531 		static_dtree[n].Code = bi_reverse((unsigned)n, 5);
2532 	}
2533 	static_init_done = 1;
2534 }
2535 
2536 /*
2537  * ===========================================================================
2538  * Initialize the tree data structures for a new zlib stream.
2539  */
2540 void
2541 _tr_init(s)
2542     deflate_state *s;
2543 {
2544 	tr_static_init();
2545 
2546 	s->l_desc.dyn_tree = s->dyn_ltree;
2547 	s->l_desc.stat_desc = &static_l_desc;
2548 
2549 	s->d_desc.dyn_tree = s->dyn_dtree;
2550 	s->d_desc.stat_desc = &static_d_desc;
2551 
2552 	s->bl_desc.dyn_tree = s->bl_tree;
2553 	s->bl_desc.stat_desc = &static_bl_desc;
2554 
2555 	s->bi_buf = 0;
2556 	s->bi_valid = 0;
2557 	s->last_eob_len = 8;	/* enough lookahead for inflate */
2558 	s->compressed_len = 0L;		/* PPP */
2559 #ifdef DEBUG_ZLIB
2560 	s->bits_sent = 0L;
2561 #endif
2562 
2563 	/* Initialize the first block of the first file: */
2564 	init_block(s);
2565 }
2566 
2567 /*
2568  * ===========================================================================
2569  * Initialize a new block.
2570  */
2571 local void
2572 init_block(s)
2573     deflate_state *s;
2574 {
2575 	int n;	/* iterates over tree elements */
2576 
2577 	/* Initialize the trees. */
2578 	for (n = 0; n < L_CODES;  n++) s->dyn_ltree[n].Freq = 0;
2579 	for (n = 0; n < D_CODES;  n++) s->dyn_dtree[n].Freq = 0;
2580 	for (n = 0; n < BL_CODES; n++) s->bl_tree[n].Freq = 0;
2581 
2582 	s->dyn_ltree[END_BLOCK].Freq = 1;
2583 	s->opt_len = s->static_len = 0L;
2584 	s->last_lit = s->matches = 0;
2585 }
2586 
2587 #define	SMALLEST 1
2588 /* Index within the heap array of least frequent node in the Huffman tree */
2589 
2590 
2591 /*
2592  * ===========================================================================
2593  * Remove the smallest element from the heap and recreate the heap with
2594  * one less element. Updates heap and heap_len.
2595  */
2596 #define	pqremove(s, tree, top) \
2597 {\
2598 	top = s->heap[SMALLEST]; \
2599 	s->heap[SMALLEST] = s->heap[s->heap_len--]; \
2600 	pqdownheap(s, tree, SMALLEST); \
2601 }
2602 
2603 /*
2604  * ===========================================================================
2605  * Compares to subtrees, using the tree depth as tie breaker when
2606  * the subtrees have equal frequency. This minimizes the worst case length.
2607  */
2608 #define	smaller(tree, n, m, depth) \
2609 	(tree[n].Freq < tree[m].Freq || \
2610 	(tree[n].Freq == tree[m].Freq && depth[n] <= depth[m]))
2611 /*
2612  * ===========================================================================
2613  * Restore the heap property by moving down the tree starting at node k,
2614  * exchanging a node with the smallest of its two sons if necessary, stopping
2615  * when the heap property is re-established (each father smaller than its
2616  * two sons).
2617  */
2618 local void
2619 pqdownheap(s, tree, k)
2620     deflate_state *s;
2621     ct_data *tree;	/* the tree to restore */
2622     int k;	/* node to move down */
2623 {
2624 	int v = s->heap[k];
2625 	int j = k << 1;	/* left son of k */
2626 	while (j <= s->heap_len) {
2627 		/* Set j to the smallest of the two sons: */
2628 		if (j < s->heap_len &&
2629 		    smaller(tree, s->heap[j+1], s->heap[j], s->depth)) {
2630 			j++;
2631 		}
2632 		/* Exit if v is smaller than both sons */
2633 		if (smaller(tree, v, s->heap[j], s->depth)) break;
2634 
2635 		/* Exchange v with the smallest son */
2636 		s->heap[k] = s->heap[j];  k = j;
2637 
2638 		/* And continue down the tree, setting j to the left son of k */
2639 		j <<= 1;
2640 	}
2641 	s->heap[k] = v;
2642 }
2643 
2644 /*
2645  * ===========================================================================
2646  * Compute the optimal bit lengths for a tree and update the total bit length
2647  * for the current block.
2648  * IN assertion: the fields freq and dad are set, heap[heap_max] and
2649  *    above are the tree nodes sorted by increasing frequency.
2650  * OUT assertions: the field len is set to the optimal bit length, the
2651  *     array bl_count contains the frequencies for each bit length.
2652  *     The length opt_len is updated; static_len is also updated if stree is
2653  *     not null.
2654  */
2655 local void
2656 gen_bitlen(s, desc)
2657     deflate_state *s;
2658     tree_desc *desc;	/* the tree descriptor */
2659 {
2660 	ct_data *tree  = desc->dyn_tree;
2661 	int max_code   = desc->max_code;
2662 	const ct_data *stree = desc->stat_desc->static_tree;
2663 	const intf *extra    = desc->stat_desc->extra_bits;
2664 	int base	= desc->stat_desc->extra_base;
2665 	int max_length = desc->stat_desc->max_length;
2666 	int h;	/* heap index */
2667 	int n, m;	/* iterate over the tree elements */
2668 	int bits;	/* bit length */
2669 	int xbits;	/* extra bits */
2670 	ush f;	/* frequency */
2671 	/* number of elements with bit length too large */
2672 	int overflow = 0;
2673 
2674 	for (bits = 0; bits <= MAX_BITS; bits++) s->bl_count[bits] = 0;
2675 
2676 	/*
2677 	 * In a first pass, compute the optimal bit lengths (which may
2678 	 * overflow in the case of the bit length tree).
2679 	 */
2680 	tree[s->heap[s->heap_max]].Len = 0;	/* root of the heap */
2681 
2682 	for (h = s->heap_max+1; h < HEAP_SIZE; h++) {
2683 		n = s->heap[h];
2684 		bits = tree[tree[n].Dad].Len + 1;
2685 		if (bits > max_length) bits = max_length, overflow++;
2686 		tree[n].Len = (ush)bits;
2687 		/* We overwrite tree[n].Dad which is no longer needed */
2688 
2689 		if (n > max_code) continue;	/* not a leaf node */
2690 
2691 		s->bl_count[bits]++;
2692 		xbits = 0;
2693 		if (n >= base) xbits = extra[n-base];
2694 		f = tree[n].Freq;
2695 		s->opt_len += (ulg)f * (bits + xbits);
2696 		if (stree) s->static_len += (ulg)f * (stree[n].Len + xbits);
2697 	}
2698 	if (overflow == 0)
2699 		return;
2700 
2701 	Trace((stderr, "\nbit length overflow\n"));
2702 	/* This happens for example on obj2 and pic of the Calgary corpus */
2703 
2704 	/* Find the first bit length which could increase: */
2705 	do {
2706 		bits = max_length-1;
2707 		while (s->bl_count[bits] == 0) bits--;
2708 		s->bl_count[bits]--;	/* move one leaf down the tree */
2709 		/* move one overflow item as its brother */
2710 		s->bl_count[bits+1] += 2;
2711 		s->bl_count[max_length]--;
2712 		/*
2713 		 * The brother of the overflow item also moves one
2714 		 * step up, but this does not affect
2715 		 * bl_count[max_length]
2716 		 */
2717 		overflow -= 2;
2718 	} while (overflow > 0);
2719 
2720 	/*
2721 	 * Now recompute all bit lengths, scanning in increasing
2722 	 * frequency.  h is still equal to HEAP_SIZE. (It is simpler
2723 	 * to reconstruct all lengths instead of fixing only the wrong
2724 	 * ones. This idea is taken from 'ar' written by Haruhiko
2725 	 * Okumura.)
2726 	 */
2727 	for (bits = max_length; bits != 0; bits--) {
2728 		n = s->bl_count[bits];
2729 		while (n != 0) {
2730 			m = s->heap[--h];
2731 			if (m > max_code) continue;
2732 			if (tree[m].Len != (unsigned)bits) {
2733 				Trace((stderr, "code %d bits %d->%d\n", m,
2734 				    tree[m].Len, bits));
2735 				s->opt_len += ((long)bits - (long)tree[m].Len)
2736 				    *(long)tree[m].Freq;
2737 				tree[m].Len = (ush)bits;
2738 			}
2739 			n--;
2740 		}
2741 	}
2742 }
2743 
2744 /*
2745  * ===========================================================================
2746  * Generate the codes for a given tree and bit counts (which need not be
2747  * optimal).
2748  * IN assertion: the array bl_count contains the bit length statistics for
2749  * the given tree and the field len is set for all tree elements.
2750  * OUT assertion: the field code is set for all tree elements of non
2751  *     zero code length.
2752  */
2753 local void
2754 gen_codes(tree, max_code, bl_count)
2755     ct_data *tree;	/* the tree to decorate */
2756     int max_code;	/* largest code with non zero frequency */
2757     ushf *bl_count;	/* number of codes at each bit length */
2758 {
2759 	/* next code value for each bit length */
2760 	ush next_code[MAX_BITS+1];
2761 	ush code = 0;	/* running code value */
2762 	int bits;	/* bit index */
2763 	int n;	/* code index */
2764 
2765 	/*
2766 	 * The distribution counts are first used to generate the code
2767 	 * values without bit reversal.
2768 	 */
2769 	for (bits = 1; bits <= MAX_BITS; bits++) {
2770 		next_code[bits] = code = (code + bl_count[bits-1]) << 1;
2771 	}
2772 	/*
2773 	 * Check that the bit counts in bl_count are consistent. The
2774 	 * last code must be all ones.
2775 	 */
2776 	Assert(code + bl_count[MAX_BITS]-1 == (1<<MAX_BITS)-1,
2777 	    "inconsistent bit counts");
2778 	Tracev((stderr, "\ngen_codes: max_code %d ", max_code));
2779 
2780 	for (n = 0;  n <= max_code; n++) {
2781 		int len = tree[n].Len;
2782 		if (len == 0) continue;
2783 		/* Now reverse the bits */
2784 		tree[n].Code = bi_reverse(next_code[len]++, len);
2785 
2786 		Tracecv(tree != static_ltree,
2787 		    (stderr, "\nn %3d %c l %2d c %4x (%x) ",
2788 		    n, (isgraph(n) ? n : ' '), len, tree[n].Code,
2789 			next_code[len]-1));
2790 	}
2791 }
2792 
2793 /*
2794  * ===========================================================================
2795  * Construct one Huffman tree and assigns the code bit strings and lengths.
2796  * Update the total bit length for the current block.
2797  * IN assertion: the field freq is set for all tree elements.
2798  * OUT assertions: the fields len and code are set to the optimal bit length
2799  *     and corresponding code. The length opt_len is updated; static_len is
2800  *     also updated if stree is not null. The field max_code is set.
2801  */
2802 local void
2803 build_tree(s, desc)
2804     deflate_state *s;
2805     tree_desc *desc;	/* the tree descriptor */
2806 {
2807 	ct_data *tree   = desc->dyn_tree;
2808 	const ct_data *stree  = desc->stat_desc->static_tree;
2809 	int elems	= desc->stat_desc->elems;
2810 	int n, m;	/* iterate over heap elements */
2811 	int max_code = -1;	/* largest code with non zero frequency */
2812 	int node;	/* new node being created */
2813 
2814 	/*
2815 	 * Construct the initial heap, with least frequent element in
2816 	 * heap[SMALLEST]. The sons of heap[n] are heap[2*n] and
2817 	 * heap[2*n+1].  heap[0] is not used.
2818 	 */
2819 	s->heap_len = 0, s->heap_max = HEAP_SIZE;
2820 
2821 	for (n = 0; n < elems; n++) {
2822 		if (tree[n].Freq != 0) {
2823 			s->heap[++(s->heap_len)] = max_code = n;
2824 			s->depth[n] = 0;
2825 		} else {
2826 			tree[n].Len = 0;
2827 		}
2828 	}
2829 
2830 	/*
2831 	 * The pkzip format requires that at least one distance code
2832 	 * exists, and that at least one bit should be sent even if
2833 	 * there is only one possible code. So to avoid special checks
2834 	 * later on we force at least two codes of non zero frequency.
2835 	 */
2836 	while (s->heap_len < 2) {
2837 		node = s->heap[++(s->heap_len)] = (max_code < 2 ?
2838 		    ++max_code : 0);
2839 		tree[node].Freq = 1;
2840 		s->depth[node] = 0;
2841 		s->opt_len--; if (stree) s->static_len -= stree[node].Len;
2842 		/* node is 0 or 1 so it does not have extra bits */
2843 	}
2844 	desc->max_code = max_code;
2845 
2846 	/*
2847 	 * The elements heap[heap_len/2+1 .. heap_len] are leaves of
2848 	 * the tree, establish sub-heaps of increasing lengths:
2849 	 */
2850 	for (n = s->heap_len/2; n >= 1; n--) pqdownheap(s, tree, n);
2851 
2852 	/*
2853 	 * Construct the Huffman tree by repeatedly combining the
2854 	 * least two frequent nodes.
2855 	 */
2856 	node = elems;	/* next internal node of the tree */
2857 	do {
2858 		pqremove(s, tree, n);	/* n = node of least frequency */
2859 		m = s->heap[SMALLEST];	/* m = node of next least frequency */
2860 
2861 		/* keep the nodes sorted by frequency */
2862 		s->heap[--(s->heap_max)] = n;
2863 		s->heap[--(s->heap_max)] = m;
2864 
2865 		/* Create a new node father of n and m */
2866 		tree[node].Freq = tree[n].Freq + tree[m].Freq;
2867 		s->depth[node] = (uch) (MAX(s->depth[n], s->depth[m]) + 1);
2868 		tree[n].Dad = tree[m].Dad = (ush)node;
2869 #ifdef DUMP_BL_TREE
2870 		if (tree == s->bl_tree) {
2871 			fprintf(stderr, "\nnode %d(%d), sons %d(%d) %d(%d)",
2872 			    node, tree[node].Freq, n, tree[n].Freq, m,
2873 			    tree[m].Freq);
2874 		}
2875 #endif
2876 		/* and insert the new node in the heap */
2877 		s->heap[SMALLEST] = node++;
2878 		pqdownheap(s, tree, SMALLEST);
2879 
2880 	} while (s->heap_len >= 2);
2881 
2882 	s->heap[--(s->heap_max)] = s->heap[SMALLEST];
2883 
2884 	/*
2885 	 * At this point, the fields freq and dad are set. We can now
2886 	 * generate the bit lengths.
2887 	 */
2888 	gen_bitlen(s, (tree_desc *)desc);
2889 
2890 	/* The field len is now set, we can generate the bit codes */
2891 	gen_codes((ct_data *)tree, max_code, s->bl_count);
2892 }
2893 
2894 /*
2895  * ===========================================================================
2896  * Scan a literal or distance tree to determine the frequencies of the codes
2897  * in the bit length tree.
2898  */
2899 local void
2900 scan_tree(s, tree, max_code)
2901     deflate_state *s;
2902     ct_data *tree;	/* the tree to be scanned */
2903     int max_code;	/* and its largest code of non zero frequency */
2904 {
2905 	int n;	/* iterates over all tree elements */
2906 	int prevlen = -1;	/* last emitted length */
2907 	int curlen;	/* length of current code */
2908 	int nextlen = tree[0].Len;	/* length of next code */
2909 	int count = 0;	/* repeat count of the current code */
2910 	int max_count = 7;	/* max repeat count */
2911 	int min_count = 4;	/* min repeat count */
2912 
2913 	if (nextlen == 0) max_count = 138, min_count = 3;
2914 	tree[max_code+1].Len = (ush)0xffff;	/* guard */
2915 
2916 	for (n = 0; n <= max_code; n++) {
2917 		curlen = nextlen; nextlen = tree[n+1].Len;
2918 		if (++count < max_count && curlen == nextlen) {
2919 			continue;
2920 		} else if (count < min_count) {
2921 			s->bl_tree[curlen].Freq += count;
2922 		} else if (curlen != 0) {
2923 			if (curlen != prevlen) s->bl_tree[curlen].Freq++;
2924 			s->bl_tree[REP_3_6].Freq++;
2925 		} else if (count <= 10) {
2926 			s->bl_tree[REPZ_3_10].Freq++;
2927 		} else {
2928 			s->bl_tree[REPZ_11_138].Freq++;
2929 		}
2930 		count = 0; prevlen = curlen;
2931 		if (nextlen == 0) {
2932 			max_count = 138, min_count = 3;
2933 		} else if (curlen == nextlen) {
2934 			max_count = 6, min_count = 3;
2935 		} else {
2936 			max_count = 7, min_count = 4;
2937 		}
2938 	}
2939 }
2940 
2941 /*
2942  * ===========================================================================
2943  * Send a literal or distance tree in compressed form, using the codes in
2944  * bl_tree.
2945  */
2946 local void
2947 send_tree(s, tree, max_code)
2948     deflate_state *s;
2949     ct_data *tree;	/* the tree to be scanned */
2950     int max_code;	/* and its largest code of non zero frequency */
2951 {
2952 	int n;	/* iterates over all tree elements */
2953 	int prevlen = -1;	/* last emitted length */
2954 	int curlen;	/* length of current code */
2955 	int nextlen = tree[0].Len;	/* length of next code */
2956 	int count = 0;	/* repeat count of the current code */
2957 	int max_count = 7;	/* max repeat count */
2958 	int min_count = 4;	/* min repeat count */
2959 
2960 	/* tree[max_code+1].Len = -1; */  /* guard already set */
2961 	if (nextlen == 0) max_count = 138, min_count = 3;
2962 
2963 	for (n = 0; n <= max_code; n++) {
2964 		curlen = nextlen; nextlen = tree[n+1].Len;
2965 		if (++count < max_count && curlen == nextlen) {
2966 			continue;
2967 		} else if (count < min_count) {
2968 			do { send_code(s, curlen, s->bl_tree); }
2969 			while (--count != 0);
2970 
2971 		} else if (curlen != 0) {
2972 			if (curlen != prevlen) {
2973 				send_code(s, curlen, s->bl_tree); count--;
2974 			}
2975 			Assert(count >= 3 && count <= 6, " 3_6?");
2976 			send_code(s, REP_3_6, s->bl_tree);
2977 			send_bits(s, count-3, 2);
2978 
2979 		} else if (count <= 10) {
2980 			send_code(s, REPZ_3_10, s->bl_tree);
2981 			send_bits(s, count-3, 3);
2982 
2983 		} else {
2984 			send_code(s, REPZ_11_138, s->bl_tree);
2985 			send_bits(s, count-11, 7);
2986 		}
2987 		count = 0; prevlen = curlen;
2988 		if (nextlen == 0) {
2989 			max_count = 138, min_count = 3;
2990 		} else if (curlen == nextlen) {
2991 			max_count = 6, min_count = 3;
2992 		} else {
2993 			max_count = 7, min_count = 4;
2994 		}
2995 	}
2996 }
2997 
2998 /*
2999  * ===========================================================================
3000  * Construct the Huffman tree for the bit lengths and return the index in
3001  * bl_order of the last bit length code to send.
3002  */
3003 local int
3004 build_bl_tree(s)
3005     deflate_state *s;
3006 {
3007 	/* index of last bit length code of non zero freq */
3008 	int max_blindex;
3009 
3010 	/*
3011 	 * Determine the bit length frequencies for literal and
3012 	 * distance trees
3013 	 */
3014 	scan_tree(s, (ct_data *)s->dyn_ltree, s->l_desc.max_code);
3015 	scan_tree(s, (ct_data *)s->dyn_dtree, s->d_desc.max_code);
3016 
3017 	/* Build the bit length tree: */
3018 	build_tree(s, (tree_desc *)(&(s->bl_desc)));
3019 	/*
3020 	 * opt_len now includes the length of the tree
3021 	 * representations, except the lengths of the bit lengths
3022 	 * codes and the 5+5+4 bits for the counts.
3023 	 */
3024 
3025 	/*
3026 	 * Determine the number of bit length codes to send. The pkzip
3027 	 * format requires that at least 4 bit length codes be
3028 	 * sent. (appnote.txt says 3 but the actual value used is 4.)
3029 	 */
3030 	for (max_blindex = BL_CODES-1; max_blindex >= 3; max_blindex--) {
3031 		if (s->bl_tree[bl_order[max_blindex]].Len != 0) break;
3032 	}
3033 	/* Update opt_len to include the bit length tree and counts */
3034 	s->opt_len += 3*(max_blindex+1) + 5+5+4;
3035 	Tracev((stderr, "\ndyn trees: dyn %ld, stat %ld",
3036 	    s->opt_len, s->static_len));
3037 
3038 	return (max_blindex);
3039 }
3040 
3041 /*
3042  * ===========================================================================
3043  * Send the header for a block using dynamic Huffman trees: the counts, the
3044  * lengths of the bit length codes, the literal tree and the distance tree.
3045  * IN assertion: lcodes >= 257, dcodes >= 1, blcodes >= 4.
3046  */
3047 local void
3048 send_all_trees(s, lcodes, dcodes, blcodes)
3049     deflate_state *s;
3050     int lcodes, dcodes, blcodes;	/* number of codes for each tree */
3051 {
3052 	int rank;	/* index in bl_order */
3053 
3054 	Assert(lcodes >= 257 && dcodes >= 1 && blcodes >= 4,
3055 	    "not enough codes");
3056 	Assert(lcodes <= L_CODES && dcodes <= D_CODES && blcodes <= BL_CODES,
3057 	    "too many codes");
3058 	Tracev((stderr, "\nbl counts: "));
3059 	send_bits(s, lcodes-257, 5);	/* not +255 as stated in appnote.txt */
3060 	send_bits(s, dcodes-1,   5);
3061 	send_bits(s, blcodes-4,  4);	/* not -3 as stated in appnote.txt */
3062 	for (rank = 0; rank < blcodes; rank++) {
3063 		Tracev((stderr, "\nbl code %2d ", bl_order[rank]));
3064 		send_bits(s, s->bl_tree[bl_order[rank]].Len, 3);
3065 	}
3066 #ifdef DEBUG_ZLIB
3067 	Tracev((stderr, "\nbl tree: sent %ld", s->bits_sent));
3068 #endif
3069 
3070 	/* literal tree */
3071 	send_tree(s, (ct_data *)s->dyn_ltree, lcodes-1);
3072 #ifdef DEBUG_ZLIB
3073 	Tracev((stderr, "\nlit tree: sent %ld", s->bits_sent));
3074 #endif
3075 
3076 	/* distance tree */
3077 	send_tree(s, (ct_data *)s->dyn_dtree, dcodes-1);
3078 #ifdef DEBUG_ZLIB
3079 	Tracev((stderr, "\ndist tree: sent %ld", s->bits_sent));
3080 #endif
3081 }
3082 
3083 /*
3084  * ===========================================================================
3085  * Send a stored block
3086  */
3087 void
3088 _tr_stored_block(s, buf, stored_len, eof)
3089     deflate_state *s;
3090     charf *buf;	/* input block */
3091     ulg stored_len;	/* length of input block */
3092     int eof;	/* true if this is the last block for a file */
3093 {
3094 	send_bits(s, (STORED_BLOCK<<1)+eof, 3);	/* send block type */
3095 	s->compressed_len = (s->compressed_len + 3 + 7) & (ulg)~7L; /* PPP */
3096 	s->compressed_len += (stored_len + 4) << 3;	/* PPP */
3097 
3098 	copy_block(s, buf, (unsigned)stored_len, 1);	/* with header */
3099 }
3100 
3101 /*
3102  * Send just the `stored block' type code without any length bytes or data.
3103  * ---PPP---
3104  */
3105 void
3106 _tr_stored_type_only(s)
3107     deflate_state *s;
3108 {
3109 	send_bits(s, (STORED_BLOCK << 1), 3);
3110 	bi_windup(s);
3111 	s->compressed_len = (s->compressed_len + 3) & ~7L;	/* PPP */
3112 }
3113 
3114 
3115 /*
3116  * ===========================================================================
3117  * Send one empty static block to give enough lookahead for inflate.
3118  * This takes 10 bits, of which 7 may remain in the bit buffer.
3119  * The current inflate code requires 9 bits of lookahead. If the
3120  * last two codes for the previous block (real code plus EOB) were coded
3121  * on 5 bits or less, inflate may have only 5+3 bits of lookahead to decode
3122  * the last real code. In this case we send two empty static blocks instead
3123  * of one. (There are no problems if the previous block is stored or fixed.)
3124  * To simplify the code, we assume the worst case of last real code encoded
3125  * on one bit only.
3126  */
3127 void
3128 _tr_align(s)
3129     deflate_state *s;
3130 {
3131 	send_bits(s, STATIC_TREES<<1, 3);
3132 	send_code(s, END_BLOCK, static_ltree);
3133 	s->compressed_len += 10L;	/* 3 for block type, 7 for EOB */
3134 	bi_flush(s);
3135 	/*
3136 	 * Of the 10 bits for the empty block, we have already sent
3137 	 * (10 - bi_valid) bits. The lookahead for the last real code
3138 	 * (before the EOB of the previous block) was thus at least
3139 	 * one plus the length of the EOB plus what we have just sent
3140 	 * of the empty static block.
3141 	 */
3142 	if (1 + s->last_eob_len + 10 - s->bi_valid < 9) {
3143 		send_bits(s, STATIC_TREES<<1, 3);
3144 		send_code(s, END_BLOCK, static_ltree);
3145 		s->compressed_len += 10L;
3146 		bi_flush(s);
3147 	}
3148 	s->last_eob_len = 7;
3149 }
3150 
3151 /*
3152  * ===========================================================================
3153  * Determine the best encoding for the current block: dynamic trees, static
3154  * trees or store, and output the encoded block to the zip file.
3155  */
3156 void
3157 _tr_flush_block(s, buf, stored_len, eof)
3158     deflate_state *s;
3159     charf *buf;	/* input block, or NULL if too old */
3160     ulg stored_len;	/* length of input block */
3161     int eof;	/* true if this is the last block for a file */
3162 {
3163 	ulg opt_lenb, static_lenb;	/* opt_len and static_len in bytes */
3164 	/* index of last bit length code of non zero freq */
3165 	int max_blindex = 0;
3166 
3167 	/* Build the Huffman trees unless a stored block is forced */
3168 	if (s->level > 0) {
3169 
3170 		/* Check if the file is ascii or binary */
3171 		if (s->data_type == Z_UNKNOWN) set_data_type(s);
3172 
3173 		/* Construct the literal and distance trees */
3174 		build_tree(s, (tree_desc *)(&(s->l_desc)));
3175 		Tracev((stderr, "\nlit data: dyn %ld, stat %ld", s->opt_len,
3176 		    s->static_len));
3177 
3178 		build_tree(s, (tree_desc *)(&(s->d_desc)));
3179 		Tracev((stderr, "\ndist data: dyn %ld, stat %ld", s->opt_len,
3180 		    s->static_len));
3181 		/*
3182 		 * At this point, opt_len and static_len are the total
3183 		 * bit lengths of the compressed block data, excluding
3184 		 * the tree representations.
3185 		 */
3186 
3187 		/*
3188 		 * Build the bit length tree for the above two trees,
3189 		 * and get the index in bl_order of the last bit
3190 		 * length code to send.
3191 		 */
3192 		max_blindex = build_bl_tree(s);
3193 
3194 		/*
3195 		 * Determine the best encoding. Compute first the
3196 		 * block length in bytes
3197 		 */
3198 		opt_lenb = (s->opt_len+3+7)>>3;
3199 		static_lenb = (s->static_len+3+7)>>3;
3200 
3201 		Tracev((stderr,
3202 		    "\nopt %lu(%lu) stat %lu(%lu) stored %lu lit %u ",
3203 		    opt_lenb, s->opt_len, static_lenb, s->static_len,
3204 		    stored_len, s->last_lit));
3205 
3206 		if (static_lenb <= opt_lenb) opt_lenb = static_lenb;
3207 
3208 	} else {
3209 		Assert(buf != (char *)0, "lost buf");
3210 		/* force a stored block */
3211 		opt_lenb = static_lenb = stored_len + 5;
3212 	}
3213 
3214 	/*
3215 	 * If compression failed and this is the first and last block,
3216 	 * and if the .zip file can be seeked (to rewrite the local
3217 	 * header), the whole file is transformed into a stored file:
3218 	 */
3219 #ifdef STORED_FILE_OK
3220 #ifdef FORCE_STORED_FILE
3221 #define	FRC_STR_COND	eof && s->compressed_len == 0L /* force stored file */
3222 #else
3223 #define	FRC_STR_COND	stored_len <= opt_lenb && eof && \
3224 			s->compressed_len == 0L && seekable()
3225 #endif
3226 	if (FRC_STR_COND) {
3227 #undef FRC_STR_COND
3228 		/*
3229 		 * Since LIT_BUFSIZE <= 2*WSIZE, the input data must
3230 		 * be there:
3231 		 */
3232 		if (buf == (charf*)0) error("block vanished");
3233 
3234 		/* without header */
3235 		copy_block(s, buf, (unsigned)stored_len, 0);
3236 		s->compressed_len = stored_len << 3;
3237 		s->method = STORED;
3238 	} else
3239 #endif /* STORED_FILE_OK */
3240 
3241 #ifdef FORCE_STORED
3242 #define	FRC_STR_COND	buf != (char *)0	/* force stored block */
3243 #else
3244 			/* 4: two words for the lengths */
3245 #define	FRC_STR_COND	stored_len+4 <= opt_lenb && buf != (char *)0
3246 #endif
3247 		if (FRC_STR_COND) {
3248 #undef FRC_STR_COND
3249 			/*
3250 			 * The test buf != NULL is only necessary if
3251 			 * LIT_BUFSIZE > WSIZE.  Otherwise we can't
3252 			 * have processed more than WSIZE input bytes
3253 			 * since the last block flush, because
3254 			 * compression would have been successful. If
3255 			 * LIT_BUFSIZE <= WSIZE, it is never too late
3256 			 * to transform a block into a stored block.
3257 			 */
3258 			_tr_stored_block(s, buf, stored_len, eof);
3259 #ifdef FORCE_STATIC
3260 #define	FRC_STAT_COND	static_lenb >= 0 /* force static trees */
3261 #else
3262 #define	FRC_STAT_COND	static_lenb == opt_lenb
3263 #endif
3264 		} else if (FRC_STAT_COND) {
3265 #undef FRC_STAT_COND
3266 			send_bits(s, (STATIC_TREES<<1)+eof, 3);
3267 			compress_block(s, (ct_data *)static_ltree,
3268 			    (ct_data *)static_dtree);
3269 			s->compressed_len += 3 + s->static_len;	/* PPP */
3270 		} else {
3271 			send_bits(s, (DYN_TREES<<1)+eof, 3);
3272 			send_all_trees(s, s->l_desc.max_code+1,
3273 			    s->d_desc.max_code+1,
3274 			    max_blindex+1);
3275 			compress_block(s, (ct_data *)s->dyn_ltree,
3276 			    (ct_data *)s->dyn_dtree);
3277 			s->compressed_len += 3 + s->opt_len;	/* PPP */
3278 		}
3279 #ifdef DEBUG_ZLIB
3280 	Assert(s->compressed_len == s->bits_sent, "bad compressed size");
3281 #endif
3282 	/*
3283 	 * The above check is made mod 2^32, for files larger than 512
3284 	 * MB and uLong implemented on 32 bits.
3285 	 */
3286 	init_block(s);
3287 
3288 	if (eof) {
3289 		bi_windup(s);
3290 		s->compressed_len += 7;	/* align on byte boundary PPP */
3291 	}
3292 	Tracev((stderr, "\ncomprlen %lu(%lu) ", s->compressed_len>>3,
3293 	    s->compressed_len-7*eof));
3294 
3295 	/* return (s->compressed_len >> 3); */
3296 }
3297 
3298 /*
3299  * ===========================================================================
3300  * Save the match info and tally the frequency counts. Return true if
3301  * the current block must be flushed.
3302  */
3303 int
3304 _tr_tally(s, dist, lc)
3305     deflate_state *s;
3306     unsigned dist;	/* distance of matched string */
3307 	/* match length-MIN_MATCH or unmatched char (if dist==0) */
3308     unsigned lc;
3309 {
3310 	s->d_buf[s->last_lit] = (ush)dist;
3311 	s->l_buf[s->last_lit++] = (uch)lc;
3312 	if (dist == 0) {
3313 		/* lc is the unmatched char */
3314 		s->dyn_ltree[lc].Freq++;
3315 	} else {
3316 		s->matches++;
3317 		/* Here, lc is the match length - MIN_MATCH */
3318 		dist--;	/* dist = match distance - 1 */
3319 		Assert((ush)dist < (ush)MAX_DIST(s) &&
3320 		    (ush)lc <= (ush)(MAX_MATCH-MIN_MATCH) &&
3321 		    (ush)d_code(dist) < (ush)D_CODES,  "_tr_tally: bad match");
3322 
3323 		s->dyn_ltree[_length_code[lc]+LITERALS+1].Freq++;
3324 		s->dyn_dtree[d_code(dist)].Freq++;
3325 	}
3326 
3327 #ifdef TRUNCATE_BLOCK
3328 	/* Try to guess if it is profitable to stop the current block here */
3329 	if ((s->last_lit & 0x1fff) == 0 && s->level > 2) {
3330 		/* Compute an upper bound for the compressed length */
3331 		ulg out_length = (ulg)s->last_lit*8L;
3332 		ulg in_length = (ulg)((long)s->strstart - s->block_start);
3333 		int dcode;
3334 		for (dcode = 0; dcode < D_CODES; dcode++) {
3335 			out_length += (ulg)s->dyn_dtree[dcode].Freq *
3336 			    (5L+extra_dbits[dcode]);
3337 		}
3338 		out_length >>= 3;
3339 		Tracev((stderr, "\nlast_lit %u, in %ld, out ~%ld(%ld%%) ",
3340 		    s->last_lit, in_length, out_length,
3341 		    100L - out_length*100L/in_length));
3342 		if (s->matches < s->last_lit/2 && out_length < in_length/2)
3343 			return (1);
3344 	}
3345 #endif
3346 	return (s->last_lit == s->lit_bufsize-1);
3347 	/*
3348 	 * We avoid equality with lit_bufsize because of wraparound at 64K
3349 	 * on 16 bit machines and because stored blocks are restricted to
3350 	 * 64K-1 bytes.
3351 	 */
3352 }
3353 
3354 /*
3355  * ===========================================================================
3356  * Send the block data compressed using the given Huffman trees
3357  */
3358 local void
3359 compress_block(s, ltree, dtree)
3360     deflate_state *s;
3361     ct_data *ltree;	/* literal tree */
3362     ct_data *dtree;	/* distance tree */
3363 {
3364 	unsigned dist;	/* distance of matched string */
3365 	int lc;	/* match length or unmatched char (if dist == 0) */
3366 	unsigned lx = 0;	/* running index in l_buf */
3367 	unsigned code;	/* the code to send */
3368 	int extra;	/* number of extra bits to send */
3369 
3370 	if (s->last_lit != 0) do {
3371 		dist = s->d_buf[lx];
3372 		lc = s->l_buf[lx++];
3373 		if (dist == 0) {
3374 			/* send a literal byte */
3375 			send_code(s, lc, ltree);
3376 			Tracecv(isgraph(lc), (stderr, " '%c' ", lc));
3377 		} else {
3378 			/* Here, lc is the match length - MIN_MATCH */
3379 			code = _length_code[lc];
3380 			/* send the length code */
3381 			send_code(s, code+LITERALS+1, ltree);
3382 			extra = extra_lbits[code];
3383 			if (extra != 0) {
3384 				lc -= base_length[code];
3385 				/* send the extra length bits */
3386 				send_bits(s, lc, extra);
3387 			}
3388 			/* dist is now the match distance - 1 */
3389 			dist--;
3390 			code = d_code(dist);
3391 			Assert(code < D_CODES, "bad d_code");
3392 
3393 			/* send the distance code */
3394 			send_code(s, code, dtree);
3395 			extra = extra_dbits[code];
3396 			if (extra != 0) {
3397 				dist -= base_dist[code];
3398 				/* send the extra distance bits */
3399 				send_bits(s, dist, extra);
3400 			}
3401 		} /* literal or match pair ? */
3402 
3403 		/*
3404 		 * Check that the overlay between pending_buf and
3405 		 * d_buf+l_buf is ok:
3406 		 */
3407 		Assert(s->pending < s->lit_bufsize + 2*lx,
3408 		    "pendingBuf overflow");
3409 
3410 	} while (lx < s->last_lit);
3411 
3412 	send_code(s, END_BLOCK, ltree);
3413 	s->last_eob_len = ltree[END_BLOCK].Len;
3414 }
3415 
3416 /*
3417  * ===========================================================================
3418  * Set the data type to ASCII or BINARY, using a crude approximation:
3419  * binary if more than 20% of the bytes are <= 6 or >= 128, ascii otherwise.
3420  * IN assertion: the fields freq of dyn_ltree are set and the total of all
3421  * frequencies does not exceed 64K (to fit in an int on 16 bit machines).
3422  */
3423 local void
3424 set_data_type(s)
3425     deflate_state *s;
3426 {
3427 	int n = 0;
3428 	unsigned ascii_freq = 0;
3429 	unsigned bin_freq = 0;
3430 	while (n < 7)	bin_freq	+= s->dyn_ltree[n++].Freq;
3431 	while (n < 128)	ascii_freq	+= s->dyn_ltree[n++].Freq;
3432 	while (n < LITERALS) bin_freq	+= s->dyn_ltree[n++].Freq;
3433 	s->data_type = (Byte)(bin_freq > (ascii_freq >> 2) ?
3434 	    Z_BINARY : Z_ASCII);
3435 }
3436 
3437 /*
3438  * ===========================================================================
3439  * Reverse the first len bits of a code, using straightforward code (a faster
3440  * method would use a table)
3441  * IN assertion: 1 <= len <= 15
3442  */
3443 local unsigned
3444 bi_reverse(code, len)
3445     unsigned code;	/* the value to invert */
3446     int len;	/* its bit length */
3447 {
3448 	register unsigned res = 0;
3449 	do {
3450 		res |= code & 1;
3451 		code >>= 1, res <<= 1;
3452 	} while (--len > 0);
3453 	return (res >> 1);
3454 }
3455 
3456 /*
3457  * ===========================================================================
3458  * Flush the bit buffer, keeping at most 7 bits in it.
3459  */
3460 local void
3461 bi_flush(s)
3462     deflate_state *s;
3463 {
3464 	if (s->bi_valid == 16) {
3465 		put_short(s, s->bi_buf);
3466 		s->bi_buf = 0;
3467 		s->bi_valid = 0;
3468 	} else if (s->bi_valid >= 8) {
3469 		put_byte(s, (Byte)s->bi_buf);
3470 		s->bi_buf >>= 8;
3471 		s->bi_valid -= 8;
3472 	}
3473 }
3474 
3475 /*
3476  * ===========================================================================
3477  * Flush the bit buffer and align the output on a byte boundary
3478  */
3479 local void
3480 bi_windup(s)
3481     deflate_state *s;
3482 {
3483 	if (s->bi_valid > 8) {
3484 		put_short(s, s->bi_buf);
3485 	} else if (s->bi_valid > 0) {
3486 		put_byte(s, (Byte)s->bi_buf);
3487 	}
3488 	s->bi_buf = 0;
3489 	s->bi_valid = 0;
3490 #ifdef DEBUG_ZLIB
3491 	s->bits_sent = (s->bits_sent+7) & ~7;
3492 #endif
3493 }
3494 
3495 /*
3496  * ===========================================================================
3497  * Copy a stored block, storing first the length and its
3498  * one's complement if requested.
3499  */
3500 local void
3501 copy_block(s, buf, len, header)
3502     deflate_state *s;
3503     charf    *buf;	/* the input data */
3504     unsigned len;	/* its length */
3505     int	header;	/* true if block header must be written */
3506 {
3507 	bi_windup(s);	/* align on byte boundary */
3508 	s->last_eob_len = 8;	/* enough lookahead for inflate */
3509 
3510 	if (header) {
3511 		put_short(s, (ush)len);
3512 		put_short(s, (ush)~len);
3513 #ifdef DEBUG_ZLIB
3514 		s->bits_sent += 2*16;
3515 #endif
3516 	}
3517 #ifdef DEBUG_ZLIB
3518 	s->bits_sent += (ulg)len<<3;
3519 #endif
3520 	/* bundle up the put_byte(s, *buf++) calls PPP */
3521 	Assert(s->pending + len < s->pending_buf_size, "pending_buf overrun");
3522 	zmemcpy(&s->pending_buf[s->pending], buf, len);	/* PPP */
3523 	s->pending += len;				/* PPP */
3524 }
3525 /* --- trees.c */
3526 
3527 /* +++ inflate.c */
3528 /*
3529  * inflate.c -- zlib interface to inflate modules
3530  * Copyright (C) 1995-1998 Mark Adler
3531  * For conditions of distribution and use, see copyright notice in zlib.h
3532  */
3533 
3534 /* #include "zutil.h" */
3535 
3536 /* +++ infblock.h */
3537 /*
3538  * infblock.h -- header to use infblock.c
3539  * Copyright (C) 1995-1998 Mark Adler
3540  * For conditions of distribution and use, see copyright notice in zlib.h
3541  */
3542 
3543 /*
3544  * WARNING: this file should *not* be used by applications. It is part
3545  * of the implementation of the compression library and is subject to
3546  * change. Applications should only use zlib.h.
3547  */
3548 
3549 struct inflate_blocks_state;
3550 typedef struct inflate_blocks_state FAR inflate_blocks_statef;
3551 
3552 extern inflate_blocks_statef * inflate_blocks_new OF((
3553     z_streamp z,
3554     check_func c,	/* check function */
3555     uInt w));	/* window size */
3556 
3557 extern int inflate_blocks OF((
3558     inflate_blocks_statef *,
3559     z_streamp,
3560     int));	/* initial return code */
3561 
3562 extern void inflate_blocks_reset OF((
3563     inflate_blocks_statef *,
3564     z_streamp,
3565     uLongf *));	/* check value on output */
3566 
3567 extern int inflate_blocks_free OF((
3568     inflate_blocks_statef *,
3569     z_streamp));
3570 
3571 extern void inflate_set_dictionary OF((
3572     inflate_blocks_statef *s,
3573     const Bytef *d,  /* dictionary */
3574     uInt  n));	/* dictionary length */
3575 
3576 extern int inflate_blocks_sync_point OF((
3577     inflate_blocks_statef *s));
3578 
3579 /* PPP -- added function */
3580 extern int inflate_addhistory OF((
3581     inflate_blocks_statef *,
3582     z_streamp));
3583 
3584 /* PPP -- added function */
3585 extern int inflate_packet_flush OF((
3586     inflate_blocks_statef *));
3587 /* --- infblock.h */
3588 
3589 #ifndef NO_DUMMY_DECL
3590 struct inflate_blocks_state {int dummy; };	/* for buggy compilers */
3591 #endif
3592 
3593 /* inflate private state */
3594 struct internal_state {
3595 
3596 	/* mode */
3597 	enum {
3598 		METHOD,	/* waiting for method byte */
3599 		FLAG,	/* waiting for flag byte */
3600 		DICT4,	/* four dictionary check bytes to go */
3601 		DICT3,	/* three dictionary check bytes to go */
3602 		DICT2,	/* two dictionary check bytes to go */
3603 		DICT1,	/* one dictionary check byte to go */
3604 		DICT0,	/* waiting for inflateSetDictionary */
3605 		BLOCKS,	/* decompressing blocks */
3606 		CHECK4,	/* four check bytes to go */
3607 		CHECK3,	/* three check bytes to go */
3608 		CHECK2,	/* two check bytes to go */
3609 		CHECK1,	/* one check byte to go */
3610 		DONE,	/* finished check, done */
3611 		BAD}	/* got an error--stay here */
3612 	mode;	/* current inflate mode */
3613 
3614 	/* mode dependent information */
3615 	union {
3616 		uInt method;	/* if FLAGS, method byte */
3617 		struct {
3618 			uLong was;	/* computed check value */
3619 			uLong need;	/* stream check value */
3620 		} check;	/* if CHECK, check values to compare */
3621 		uInt marker;	/* if BAD, inflateSync's marker bytes count */
3622 	} sub;	/* submode */
3623 
3624 	/* mode independent information */
3625 	int  nowrap;	/* flag for no wrapper */
3626 	uInt wbits;	/* log2(window size)  (8..15, defaults to 15) */
3627 	/* current inflate_blocks state */
3628 	inflate_blocks_statef *blocks;
3629 };
3630 
3631 
3632 int
3633 inflateReset(z)
3634 z_streamp z;
3635 {
3636 	if (z == Z_NULL || z->state == Z_NULL)
3637 		return (Z_STREAM_ERROR);
3638 	z->total_in = z->total_out = 0;
3639 	z->msg = Z_NULL;
3640 	z->state->mode = z->state->nowrap ? BLOCKS : METHOD;
3641 	inflate_blocks_reset(z->state->blocks, z, Z_NULL);
3642 	Trace((stderr, "inflate: reset\n"));
3643 	return (Z_OK);
3644 }
3645 
3646 
3647 int
3648 inflateEnd(z)
3649 z_streamp z;
3650 {
3651 	if (z == Z_NULL || z->state == Z_NULL || z->zfree == Z_NULL)
3652 		return (Z_STREAM_ERROR);
3653 	if (z->state->blocks != Z_NULL) {
3654 		(void) inflate_blocks_free(z->state->blocks, z);
3655 		z->state->blocks = Z_NULL;
3656 	}
3657 	ZFREE(z, z->state);
3658 	z->state = Z_NULL;
3659 	Trace((stderr, "inflate: end\n"));
3660 	return (Z_OK);
3661 }
3662 
3663 
3664 int
3665 inflateInit2_(z, w, version, stream_size)
3666 z_streamp z;
3667 int w;
3668 const char *version;
3669 int stream_size;
3670 {
3671 	if (version == Z_NULL || version[0] != ZLIB_VERSION[0] ||
3672 	    stream_size != sizeof (z_stream))
3673 		return (Z_VERSION_ERROR);
3674 
3675 	/* initialize state */
3676 	if (z == Z_NULL)
3677 		return (Z_STREAM_ERROR);
3678 	z->msg = Z_NULL;
3679 #ifndef NO_ZCFUNCS
3680 	if (z->zalloc == Z_NULL)
3681 	{
3682 		z->zalloc = zcalloc;
3683 		z->opaque = (voidpf)0;
3684 	}
3685 	if (z->zfree == Z_NULL) z->zfree = zcfree;
3686 #endif
3687 	if ((z->state = (struct internal_state FAR *)
3688 	    ZALLOC(z, 1, sizeof (struct internal_state))) == Z_NULL)
3689 		return (Z_MEM_ERROR);
3690 	z->state->blocks = Z_NULL;
3691 
3692 	/* handle undocumented nowrap option (no zlib header or check) */
3693 	z->state->nowrap = 0;
3694 	if (w < 0)
3695 	{
3696 		w = - w;
3697 		z->state->nowrap = 1;
3698 	}
3699 
3700 	/* set window size */
3701 	if (w < 8 || w > 15)
3702 	{
3703 		(void) inflateEnd(z);
3704 		return (Z_STREAM_ERROR);
3705 	}
3706 	z->state->wbits = (uInt)w;
3707 
3708 	/* create inflate_blocks state */
3709 	if ((z->state->blocks =
3710 	    inflate_blocks_new(z, z->state->nowrap ?
3711 		Z_NULL : adler32, (uInt)1 << w))
3712 	    == Z_NULL)
3713 	{
3714 		(void) inflateEnd(z);
3715 		return (Z_MEM_ERROR);
3716 	}
3717 	Trace((stderr, "inflate: allocated\n"));
3718 
3719 	/* reset state */
3720 	(void) inflateReset(z);
3721 	return (Z_OK);
3722 }
3723 
3724 
3725 int
3726 inflateInit_(z, version, stream_size)
3727 z_streamp z;
3728 const char *version;
3729 int stream_size;
3730 {
3731 	return (inflateInit2_(z, DEF_WBITS, version, stream_size));
3732 }
3733 
3734 /* PPP -- added "empty" label and changed f to Z_OK */
3735 #define	NEEDBYTE {if (z->avail_in == 0) goto empty; r = Z_OK; } ((void)0)
3736 #define	NEXTBYTE (z->avail_in--, z->total_in++, *z->next_in++)
3737 
3738 int
3739 inflate(z, f)
3740 z_streamp z;
3741 int f;
3742 {
3743 	int r;
3744 	uInt b;
3745 
3746 	if (z == Z_NULL || z->state == Z_NULL || z->next_in == Z_NULL)
3747 		return (Z_STREAM_ERROR);
3748 	/* f = f == Z_FINISH ? Z_BUF_ERROR : Z_OK; -- PPP; Z_FINISH unused */
3749 	r = Z_BUF_ERROR;
3750 	/* CONSTCOND */
3751 	while (1)
3752 		switch (z->state->mode)
3753 	{
3754 	case METHOD:
3755 		NEEDBYTE;
3756 		if (((z->state->sub.method = NEXTBYTE) & 0xf) != Z_DEFLATED)
3757 		{
3758 			z->state->mode = BAD;
3759 			z->msg = "unknown compression method";
3760 			/* can't try inflateSync */
3761 			z->state->sub.marker = 5;
3762 			break;
3763 		}
3764 		if ((z->state->sub.method >> 4) + 8 > z->state->wbits)
3765 		{
3766 			z->state->mode = BAD;
3767 			z->msg = "invalid window size";
3768 			/* can't try inflateSync */
3769 			z->state->sub.marker = 5;
3770 			break;
3771 		}
3772 		z->state->mode = FLAG;
3773 		/* FALLTHRU */
3774 	case FLAG:
3775 		NEEDBYTE;
3776 		b = NEXTBYTE;
3777 		if (((z->state->sub.method << 8) + b) % 31)
3778 		{
3779 			z->state->mode = BAD;
3780 			z->msg = "incorrect header check";
3781 			/* can't try inflateSync */
3782 			z->state->sub.marker = 5;
3783 			break;
3784 		}
3785 		Trace((stderr, "inflate: zlib header ok\n"));
3786 		if (!(b & PRESET_DICT))
3787 		{
3788 			z->state->mode = BLOCKS;
3789 			break;
3790 		}
3791 		z->state->mode = DICT4;
3792 		/* FALLTHRU */
3793 	case DICT4:
3794 		NEEDBYTE;
3795 		z->state->sub.check.need = (uLong)NEXTBYTE << 24;
3796 		z->state->mode = DICT3;
3797 		/* FALLTHRU */
3798 	case DICT3:
3799 		NEEDBYTE;
3800 		z->state->sub.check.need += (uLong)NEXTBYTE << 16;
3801 		z->state->mode = DICT2;
3802 		/* FALLTHRU */
3803 	case DICT2:
3804 		NEEDBYTE;
3805 		z->state->sub.check.need += (uLong)NEXTBYTE << 8;
3806 		z->state->mode = DICT1;
3807 		/* FALLTHRU */
3808 	case DICT1:
3809 		NEEDBYTE;
3810 		z->state->sub.check.need += (uLong)NEXTBYTE;
3811 		z->adler = z->state->sub.check.need;
3812 		z->state->mode = DICT0;
3813 		return (Z_NEED_DICT);
3814 	case DICT0:
3815 		z->state->mode = BAD;
3816 		z->msg = "need dictionary";
3817 		z->state->sub.marker = 0;	/* can try inflateSync */
3818 		return (Z_STREAM_ERROR);
3819 	case BLOCKS:
3820 		r = inflate_blocks(z->state->blocks, z, r);
3821 		if (f == Z_PACKET_FLUSH && z->avail_in == 0 &&	/* PPP */
3822 		    z->avail_out != 0)				/* PPP */
3823 			r = inflate_packet_flush(z->state->blocks); /* PPP */
3824 		if (r == Z_DATA_ERROR)
3825 		{
3826 			z->state->mode = BAD;
3827 			/* can try inflateSync */
3828 			z->state->sub.marker = 0;
3829 			break;
3830 		}
3831 		/* PPP */
3832 		if (r != Z_STREAM_END)
3833 			return (r);
3834 		r = Z_OK;	/* PPP */
3835 		inflate_blocks_reset(z->state->blocks, z,
3836 		    &z->state->sub.check.was);
3837 		if (z->state->nowrap)
3838 		{
3839 			z->state->mode = DONE;
3840 			break;
3841 		}
3842 		z->state->mode = CHECK4;
3843 		/* FALLTHRU */
3844 	case CHECK4:
3845 		NEEDBYTE;
3846 		z->state->sub.check.need = (uLong)NEXTBYTE << 24;
3847 		z->state->mode = CHECK3;
3848 		/* FALLTHRU */
3849 	case CHECK3:
3850 		NEEDBYTE;
3851 		z->state->sub.check.need += (uLong)NEXTBYTE << 16;
3852 		z->state->mode = CHECK2;
3853 		/* FALLTHRU */
3854 	case CHECK2:
3855 		NEEDBYTE;
3856 		z->state->sub.check.need += (uLong)NEXTBYTE << 8;
3857 		z->state->mode = CHECK1;
3858 		/* FALLTHRU */
3859 	case CHECK1:
3860 		NEEDBYTE;
3861 		z->state->sub.check.need += (uLong)NEXTBYTE;
3862 
3863 		if (z->state->sub.check.was != z->state->sub.check.need)
3864 		{
3865 			z->state->mode = BAD;
3866 			z->msg = "incorrect data check";
3867 			/* can't try inflateSync */
3868 			z->state->sub.marker = 5;
3869 			break;
3870 		}
3871 		Trace((stderr, "inflate: zlib check ok\n"));
3872 		z->state->mode = DONE;
3873 		/* FALLTHRU */
3874 	case DONE:
3875 		return (Z_STREAM_END);
3876 	case BAD:
3877 		return (Z_DATA_ERROR);
3878 	default:
3879 		return (Z_STREAM_ERROR);
3880 	}
3881 
3882 /* PPP -- packet flush handling */
3883 empty:
3884 	if (f != Z_PACKET_FLUSH)
3885 		return (r);
3886 	z->state->mode = BAD;
3887 	z->msg = "need more for packet flush";
3888 	z->state->sub.marker = 0;	/* can try inflateSync */
3889 	return (Z_DATA_ERROR);
3890 }
3891 
3892 
3893 int
3894 inflateSetDictionary(z, dictionary, dictLength)
3895 z_streamp z;
3896 const Bytef *dictionary;
3897 uInt  dictLength;
3898 {
3899 	uInt length = dictLength;
3900 
3901 	if (z == Z_NULL || z->state == Z_NULL || z->state->mode != DICT0)
3902 		return (Z_STREAM_ERROR);
3903 
3904 	if (adler32(1L, dictionary, dictLength) != z->adler)
3905 		return (Z_DATA_ERROR);
3906 	z->adler = 1L;
3907 
3908 	if (length >= ((uInt)1<<z->state->wbits))
3909 	{
3910 		length = (1<<z->state->wbits)-1;
3911 		dictionary += dictLength - length;
3912 	}
3913 	inflate_set_dictionary(z->state->blocks, dictionary, length);
3914 	z->state->mode = BLOCKS;
3915 	return (Z_OK);
3916 }
3917 
3918 /*
3919  * This subroutine adds the data at next_in/avail_in to the output history
3920  * without performing any output.  The output buffer must be "caught up";
3921  * i.e. no pending output (hence s->read equals s->write), and the state must
3922  * be BLOCKS (i.e. we should be willing to see the start of a series of
3923  * BLOCKS).  On exit, the output will also be caught up, and the checksum
3924  * will have been updated if need be.
3925  *
3926  * Added for PPP.
3927  */
3928 
3929 int
3930 inflateIncomp(z)
3931 z_stream *z;
3932 {
3933 	if (z->state->mode != BLOCKS)
3934 		return (Z_DATA_ERROR);
3935 	return (inflate_addhistory(z->state->blocks, z));
3936 }
3937 
3938 
3939 int
3940 inflateSync(z)
3941 z_streamp z;
3942 {
3943 	uInt n;	/* number of bytes to look at */
3944 	Bytef *p;	/* pointer to bytes */
3945 	uInt m;	/* number of marker bytes found in a row */
3946 	uLong r, w;	/* temporaries to save total_in and total_out */
3947 
3948 	/* set up */
3949 	if (z == Z_NULL || z->state == Z_NULL)
3950 		return (Z_STREAM_ERROR);
3951 	if (z->state->mode != BAD)
3952 	{
3953 		z->state->mode = BAD;
3954 		z->state->sub.marker = 0;
3955 	}
3956 	if ((n = z->avail_in) == 0)
3957 		return (Z_BUF_ERROR);
3958 	p = z->next_in;
3959 	m = z->state->sub.marker;
3960 
3961 	/* search */
3962 	while (n && m < 4)
3963 	{
3964 		static const Byte mark[4] = { 0, 0, 0xff, 0xff };
3965 		if (*p == mark[m])
3966 			m++;
3967 		else if (*p)
3968 			m = 0;
3969 		else
3970 			/*
3971 			 * This statement maps 2->2 and 3->1 because a
3972 			 * mismatch with input byte 0x00 on the first
3973 			 * 0xFF in the pattern means that we still
3974 			 * have two contiguous zeros matched (thus
3975 			 * offset 2 is kept), but a mismatch on the
3976 			 * second 0xFF means that only one 0x00 byte
3977 			 * has been matched.  (Boyer-Moore like
3978 			 * search.)
3979 			 */
3980 			m = 4 - m;
3981 		p++, n--;
3982 	}
3983 
3984 	/* restore */
3985 	z->total_in += p - z->next_in;
3986 	z->next_in = p;
3987 	z->avail_in = n;
3988 	z->state->sub.marker = m;
3989 
3990 	/* return no joy or set up to restart on a new block */
3991 	if (m != 4)
3992 		return (Z_DATA_ERROR);
3993 	r = z->total_in;  w = z->total_out;
3994 	(void) inflateReset(z);
3995 	z->total_in = r;  z->total_out = w;
3996 	z->state->mode = BLOCKS;
3997 	return (Z_OK);
3998 }
3999 
4000 /*
4001  * Returns true if inflate is currently at the end of a block
4002  * generated by Z_SYNC_FLUSH or Z_FULL_FLUSH. This function is used by
4003  * one PPP implementation to provide an additional safety check. PPP
4004  * uses Z_SYNC_FLUSH but removes the length bytes of the resulting
4005  * empty stored block. When decompressing, PPP checks that at the end
4006  * of input packet, inflate is waiting for these length bytes.
4007  */
4008 int
4009 inflateSyncPoint(z)
4010 z_streamp z;
4011 {
4012 	if (z == Z_NULL || z->state == Z_NULL || z->state->blocks == Z_NULL)
4013 		return (Z_STREAM_ERROR);
4014 	return (inflate_blocks_sync_point(z->state->blocks));
4015 }
4016 
4017 #undef NEEDBYTE
4018 #undef NEXTBYTE
4019 /* --- inflate.c */
4020 
4021 /* +++ infblock.c */
4022 /*
4023  * infblock.c -- interpret and process block types to last block
4024  * Copyright (C) 1995-1998 Mark Adler
4025  * For conditions of distribution and use, see copyright notice in zlib.h
4026  */
4027 
4028 /* #include "zutil.h" */
4029 /* #include "infblock.h" */
4030 
4031 /* +++ inftrees.h */
4032 /*
4033  * inftrees.h -- header to use inftrees.c
4034  * Copyright (C) 1995-1998 Mark Adler
4035  * For conditions of distribution and use, see copyright notice in zlib.h
4036  */
4037 
4038 /*
4039  * WARNING: this file should *not* be used by applications. It is part
4040  * of the implementation of the compression library and is subject to
4041  * change. Applications should only use zlib.h.
4042  */
4043 
4044 /*
4045  * Huffman code lookup table entry--this entry is four bytes for
4046  * machines that have 16-bit pointers (e.g. PC's in the small or
4047  * medium model).
4048  */
4049 
4050 typedef struct inflate_huft_s FAR inflate_huft;
4051 
4052 struct inflate_huft_s {
4053 	union {
4054 		struct {
4055 			Byte Exop;	/* number of extra bits or operation */
4056 			/* number of bits in this code or subcode */
4057 			Byte Bits;
4058 		} what;
4059 		Bytef *pad;	/* pad structure to a power of 2 (4 bytes for */
4060 	} word;	/*  16-bit, 8 bytes for 32-bit machines) */
4061 	/* literal, length base, distance base, or table offset */
4062 	uInt base;
4063 };
4064 
4065 /*
4066  * Maximum size of dynamic tree.  The maximum found in a long but non-
4067  * exhaustive search was 1004 huft structures (850 for length/literals
4068  * and 154 for distances, the latter actually the result of an
4069  * exhaustive search).  The actual maximum is not known, but the value
4070  * below is more than safe.
4071  */
4072 #define	MANY 1440
4073 
4074 extern int inflate_trees_bits OF((
4075     uIntf *,			/* 19 code lengths */
4076     uIntf *,			/* bits tree desired/actual depth */
4077     inflate_huft * FAR *,	/* bits tree result */
4078     inflate_huft *,		/* space for trees */
4079     z_streamp));	/* for zalloc, zfree functions */
4080 
4081 extern int inflate_trees_dynamic OF((
4082     uInt,	/* number of literal/length codes */
4083     uInt,	/* number of distance codes */
4084     uIntf *,	/* that many (total) code lengths */
4085     uIntf *,	/* literal desired/actual bit depth */
4086     uIntf *,	/* distance desired/actual bit depth */
4087     inflate_huft * FAR *,	/* literal/length tree result */
4088     inflate_huft * FAR *,	/* distance tree result */
4089     inflate_huft *,		/* space for trees */
4090     z_streamp));	/* for zalloc, zfree functions */
4091 
4092 extern int inflate_trees_fixed OF((
4093     uIntf *,	/* literal desired/actual bit depth */
4094     uIntf *,	/* distance desired/actual bit depth */
4095     const inflate_huft * FAR *,	/* literal/length tree result */
4096     const inflate_huft * FAR *,	/* distance tree result */
4097     z_streamp));
4098 
4099 /* --- inftrees.h */
4100 
4101 /* +++ infcodes.h */
4102 /*
4103  * infcodes.h -- header to use infcodes.c
4104  * Copyright (C) 1995-1998 Mark Adler
4105  * For conditions of distribution and use, see copyright notice in zlib.h
4106  */
4107 
4108 /*
4109  * WARNING: this file should *not* be used by applications. It is part
4110  * of the implementation of the compression library and is subject to
4111  * change. Applications should only use zlib.h.
4112  */
4113 
4114 struct inflate_codes_state;
4115 typedef struct inflate_codes_state FAR inflate_codes_statef;
4116 
4117 extern inflate_codes_statef *inflate_codes_new OF((
4118     uInt, uInt,
4119     const inflate_huft *, const inflate_huft *,
4120     z_streamp));
4121 
4122 extern int inflate_codes OF((
4123     inflate_blocks_statef *,
4124     z_streamp,
4125     int));
4126 
4127 extern void inflate_codes_free OF((
4128     inflate_codes_statef *,
4129     z_streamp));
4130 
4131 /* --- infcodes.h */
4132 
4133 /* +++ infutil.h */
4134 /*
4135  * infutil.h -- types and macros common to blocks and codes
4136  * Copyright (C) 1995-1998 Mark Adler
4137  * For conditions of distribution and use, see copyright notice in zlib.h
4138  */
4139 
4140 /*
4141  * WARNING: this file should *not* be used by applications. It is part
4142  * of the implementation of the compression library and is subject to
4143  * change. Applications should only use zlib.h.
4144  */
4145 
4146 #ifndef _INFUTIL_H
4147 #define	_INFUTIL_H
4148 
4149 typedef enum {
4150 	TYPE,	/* get type bits (3, including end bit) */
4151 	LENS,	/* get lengths for stored */
4152 	STORED,	/* processing stored block */
4153 	TABLE,	/* get table lengths */
4154 	BTREE,	/* get bit lengths tree for a dynamic block */
4155 	DTREE,	/* get length, distance trees for a dynamic block */
4156 	CODES,	/* processing fixed or dynamic block */
4157 	DRY,	/* output remaining window bytes */
4158 	DONEB,	/* finished last block, done */
4159 	BADB}	/* got a data error--stuck here */
4160 inflate_block_mode;
4161 
4162 /* inflate blocks semi-private state */
4163 struct inflate_blocks_state {
4164 
4165 	/* mode */
4166 	inflate_block_mode  mode;	/* current inflate_block mode */
4167 
4168 	/* mode dependent information */
4169 	union {
4170 		uInt left;	/* if STORED, bytes left to copy */
4171 		struct {
4172 			uInt table;	/* table lengths (14 bits) */
4173 			uInt index;	/* index into blens (or border) */
4174 			uIntf *blens;	/* bit lengths of codes */
4175 			uInt bb;	/* bit length tree depth */
4176 			inflate_huft *tb;	/* bit length decoding tree */
4177 		} trees;	/* if DTREE, decoding info for trees */
4178 		struct {
4179 			inflate_codes_statef *codes;
4180 		} decode;	/* if CODES, current state */
4181 	} sub;	/* submode */
4182 	uInt last;	/* true if this block is the last block */
4183 
4184 	/* mode independent information */
4185 	uInt bitk;	/* bits in bit buffer */
4186 	uLong bitb;	/* bit buffer */
4187 	inflate_huft *hufts;  /* single malloc for tree space */
4188 	Bytef *window;	/* sliding window */
4189 	Bytef *end;	/* one byte after sliding window */
4190 	Bytef *read;	/* window read pointer */
4191 	Bytef *write;	/* window write pointer */
4192 	check_func checkfn;	/* check function */
4193 	uLong check;	/* check on output */
4194 
4195 };
4196 
4197 
4198 /* defines for inflate input/output */
4199 /*   update pointers and return */
4200 #define	UPDBITS {s->bitb = b; s->bitk = k; }
4201 #define	UPDIN {z->avail_in = n; z->total_in += p-z->next_in; z->next_in = p; }
4202 #define	UPDOUT {s->write = q; }
4203 #define	UPDATE {UPDBITS UPDIN UPDOUT}
4204 #define	LEAVE {UPDATE return (inflate_flush(s, z, r)); }
4205 /*   get bytes and bits */
4206 #define	LOADIN {p = z->next_in; n = z->avail_in; b = s->bitb; k = s->bitk; }
4207 #define	NEEDBYTE { if (n) r = Z_OK; else LEAVE }
4208 #define	NEXTBYTE (n--, *p++)
4209 #define	NEEDBITS(j) { while (k < (j)) { NEEDBYTE; b |= ((uLong)NEXTBYTE)<<k; \
4210 	k += 8; }}
4211 #define	DUMPBITS(j) {b >>= (j); k -= (j); }
4212 /*   output bytes */
4213 #define	WAVAIL (uInt)(q < s->read ? s->read-q-1 : s->end-q)
4214 #define	LOADOUT {q = s->write; m = (uInt)WAVAIL; }
4215 #define	WWRAP {if (q == s->end && s->read != s->window) {q = s->window; \
4216 	m = (uInt)WAVAIL; }}
4217 #define	FLUSH {UPDOUT r = inflate_flush(s, z, r); LOADOUT}
4218 #define	NEEDOUT {if (m == 0) {WWRAP if (m == 0) { FLUSH WWRAP \
4219 	if (m == 0) LEAVE }} r = Z_OK; }
4220 #define	OUTBYTE(a) {*q++ = (Byte)(a); m--; }
4221 /*   load local pointers */
4222 #define	LOAD {LOADIN LOADOUT}
4223 
4224 /* masks for lower bits (size given to avoid silly warnings with Visual C++) */
4225 extern uInt inflate_mask[17];
4226 
4227 /* copy as much as possible from the sliding window to the output area */
4228 extern int inflate_flush OF((
4229     inflate_blocks_statef *,
4230     z_streamp,
4231     int));
4232 
4233 #ifndef NO_DUMMY_DECL
4234 struct internal_state {int dummy; };	/* for buggy compilers */
4235 #endif
4236 
4237 #endif
4238 /* --- infutil.h */
4239 
4240 #ifndef NO_DUMMY_DECL
4241 struct inflate_codes_state {int dummy; };	/* for buggy compilers */
4242 #endif
4243 
4244 /* Table for deflate from PKZIP's appnote.txt. */
4245 local const uInt border[] = { /* Order of the bit length code lengths */
4246 	16, 17, 18, 0, 8, 7, 9, 6, 10, 5, 11, 4, 12, 3, 13, 2, 14, 1, 15};
4247 
4248 /*
4249  * Notes beyond the 1.93a appnote.txt:
4250  *
4251  *   1. Distance pointers never point before the beginning of the output
4252  *      stream.
4253  *   2. Distance pointers can point back across blocks, up to 32k away.
4254  *   3. There is an implied maximum of 7 bits for the bit length table and
4255  *      15 bits for the actual data.
4256  *   4. If only one code exists, then it is encoded using one bit.  (Zero
4257  *      would be more efficient, but perhaps a little confusing.)  If two
4258  *      codes exist, they are coded using one bit each (0 and 1).
4259  *   5. There is no way of sending zero distance codes--a dummy must be
4260  *      sent if there are none.  (History: a pre 2.0 version of PKZIP would
4261  *      store blocks with no distance codes, but this was discovered to be
4262  *      too harsh a criterion.)  Valid only for 1.93a.  2.04c does allow
4263  *      zero distance codes, which is sent as one code of zero bits in
4264  *      length.
4265  *   6. There are up to 286 literal/length codes.  Code 256 represents the
4266  *      end-of-block.  Note however that the static length tree defines
4267  *      288 codes just to fill out the Huffman codes.  Codes 286 and 287
4268  *      cannot be used though, since there is no length base or extra bits
4269  *      defined for them.  Similarily, there are up to 30 distance codes.
4270  *      However, static trees define 32 codes (all 5 bits) to fill out the
4271  *      Huffman codes, but the last two had better not show up in the data.
4272  *   7. Unzip can check dynamic Huffman blocks for complete code sets.
4273  *      The exception is that a single code would not be complete (see #4).
4274  *   8. The five bits following the block type is really the number of
4275  *      literal codes sent minus 257.
4276  *   9. Length codes 8,16,16 are interpreted as 13 length codes of 8 bits
4277  *      (1+6+6).  Therefore, to output three times the length, you output
4278  *      three codes (1+1+1), whereas to output four times the same length,
4279  *      you only need two codes (1+3).  Hmm.
4280  *  10. In the tree reconstruction algorithm, Code = Code + Increment
4281  *      only if BitLength(i) is not zero.  (Pretty obvious.)
4282  *  11. Correction: 4 Bits: #of Bit Length codes - 4     (4 - 19)
4283  *  12. Note: length code 284 can represent 227-258, but length code 285
4284  *      really is 258.  The last length deserves its own, short code
4285  *      since it gets used a lot in very redundant files.  The length
4286  *      258 is special since 258 - 3 (the min match length) is 255.
4287  *  13. The literal/length and distance code bit lengths are read as a
4288  *      single stream of lengths.  It is possible (and advantageous) for
4289  *      a repeat code (16, 17, or 18) to go across the boundary between
4290  *      the two sets of lengths.
4291  */
4292 
4293 
4294 void
4295 inflate_blocks_reset(s, z, c)
4296 inflate_blocks_statef *s;
4297 z_streamp z;
4298 uLongf *c;
4299 {
4300 	if (c != Z_NULL)
4301 		*c = s->check;
4302 	if ((s->mode == BTREE || s->mode == DTREE) &&
4303 	    s->sub.trees.blens != Z_NULL) {
4304 		ZFREE(z, s->sub.trees.blens);
4305 		s->sub.trees.blens = Z_NULL;
4306 	}
4307 	if (s->mode == CODES && s->sub.decode.codes != Z_NULL) {
4308 		(void) inflate_codes_free(s->sub.decode.codes, z);
4309 		s->sub.decode.codes = Z_NULL;
4310 	}
4311 	s->mode = TYPE;
4312 	s->bitk = 0;
4313 	s->bitb = 0;
4314 	s->read = s->write = s->window;
4315 	if (s->checkfn != Z_NULL)
4316 		z->adler = s->check = (*s->checkfn)(0L, Z_NULL, 0);
4317 	Trace((stderr, "inflate:   blocks reset\n"));
4318 }
4319 
4320 inflate_blocks_statef *
4321 inflate_blocks_new(z, c, w)
4322 z_streamp z;
4323 check_func c;
4324 uInt w;
4325 {
4326 	inflate_blocks_statef *s;
4327 
4328 	if ((s = (inflate_blocks_statef *)ZALLOC
4329 	    (z, 1, sizeof (struct inflate_blocks_state))) == Z_NULL)
4330 		return (s);
4331 	s->hufts = (inflate_huft *)ZALLOC(z, MANY, sizeof (inflate_huft));
4332 	if (s->hufts == Z_NULL) {
4333 		ZFREE(z, s);
4334 		return (Z_NULL);
4335 	}
4336 	if ((s->window = (Bytef *)ZALLOC(z, 1, w)) == Z_NULL)
4337 	{
4338 		ZFREE(z, s->hufts);
4339 		ZFREE(z, s);
4340 		return (Z_NULL);
4341 	}
4342 	s->end = s->window + w;
4343 	s->checkfn = c;
4344 	s->mode = TYPE;
4345 	Trace((stderr, "inflate:   blocks allocated\n"));
4346 	inflate_blocks_reset(s, z, Z_NULL);
4347 	return (s);
4348 }
4349 
4350 
4351 int
4352 inflate_blocks(s, z, r)
4353 inflate_blocks_statef *s;
4354 z_streamp z;
4355 int r;
4356 {
4357 	uInt t;	/* temporary storage */
4358 	uLong b;	/* bit buffer */
4359 	uInt k;	/* bits in bit buffer */
4360 	Bytef *p;	/* input data pointer */
4361 	uInt n;	/* bytes available there */
4362 	Bytef *q;	/* output window write pointer */
4363 	uInt m;	/* bytes to end of window or read pointer */
4364 
4365 	/* copy input/output information to locals (UPDATE macro restores) */
4366 	LOAD;
4367 
4368 	/* process input based on current state */
4369 	/* CONSTCOND */
4370 	while (1)
4371 		switch (s->mode)
4372 	{
4373 	case TYPE:
4374 		NEEDBITS(3);
4375 		t = (uInt)b & 7;
4376 		s->last = t & 1;
4377 		switch (t >> 1)
4378 		{
4379 		case 0:			/* stored */
4380 			Trace((stderr, "inflate:     stored block%s\n",
4381 			    s->last ? " (last)" : ""));
4382 			DUMPBITS(3);
4383 			t = k & 7;	/* go to byte boundary */
4384 			DUMPBITS(t);
4385 			s->mode = LENS;	/* get length of stored block */
4386 			break;
4387 		case 1:			/* fixed */
4388 			Trace((stderr, "inflate:     fixed codes block%s\n",
4389 			    s->last ? " (last)" : ""));
4390 			{
4391 				uInt bl, bd;
4392 				const inflate_huft *tl, *td;
4393 
4394 				(void) inflate_trees_fixed(&bl, &bd, &tl, &td,
4395 				    z);
4396 				s->sub.decode.codes = inflate_codes_new(bl,
4397 				    bd, tl, td, z);
4398 				if (s->sub.decode.codes == Z_NULL)
4399 				{
4400 					r = Z_MEM_ERROR;
4401 					LEAVE
4402 				}
4403 			}
4404 			DUMPBITS(3);
4405 			s->mode = CODES;
4406 			break;
4407 		case 2:			/* dynamic */
4408 			Trace((stderr, "inflate:     dynamic codes block%s\n",
4409 			    s->last ? " (last)" : ""));
4410 			DUMPBITS(3);
4411 			s->mode = TABLE;
4412 			break;
4413 		case 3:			/* illegal */
4414 			DUMPBITS(3);
4415 			s->mode = BADB;
4416 			z->msg = "invalid block type";
4417 			r = Z_DATA_ERROR;
4418 			LEAVE
4419 		}
4420 		break;
4421 	case LENS:
4422 		NEEDBITS(32);
4423 		if ((((~b) >> 16) & 0xffff) != (b & 0xffff))
4424 		{
4425 			s->mode = BADB;
4426 			z->msg = "invalid stored block lengths";
4427 			r = Z_DATA_ERROR;
4428 			LEAVE
4429 		}
4430 		s->sub.left = (uInt)b & 0xffff;
4431 		b = k = 0;	/* dump bits */
4432 		Tracev((stderr, "inflate:       stored length %u\n",
4433 		    s->sub.left));
4434 		s->mode = s->sub.left ? STORED : (s->last ? DRY : TYPE);
4435 		break;
4436 	case STORED:
4437 		if (n == 0)
4438 			LEAVE
4439 		NEEDOUT;
4440 		t = s->sub.left;
4441 		if (t > n) t = n;
4442 		if (t > m) t = m;
4443 		zmemcpy(q, p, t);
4444 		p += t;  n -= t;
4445 		q += t;  m -= t;
4446 		if ((s->sub.left -= t) != 0)
4447 			break;
4448 		Tracev((stderr,
4449 		    "inflate:       stored end, %lu total out\n",
4450 		    z->total_out + (q >= s->read ? q - s->read :
4451 			(s->end - s->read) + (q - s->window))));
4452 		s->mode = s->last ? DRY : TYPE;
4453 		break;
4454 	case TABLE:
4455 		NEEDBITS(14);
4456 		s->sub.trees.table = t = (uInt)b & 0x3fff;
4457 #ifndef PKZIP_BUG_WORKAROUND
4458 		if ((t & 0x1f) > 29 || ((t >> 5) & 0x1f) > 29)
4459 		{
4460 			s->mode = BADB;
4461 			z->msg =
4462 			    (char *)"too many length or distance symbols";
4463 			r = Z_DATA_ERROR;
4464 			LEAVE
4465 		}
4466 #endif
4467 		t = 258 + (t & 0x1f) + ((t >> 5) & 0x1f);
4468 		/* if (t < 19) t = 19; */
4469 		if ((s->sub.trees.blens = (uIntf*)ZALLOC(z, t,
4470 		    sizeof (uInt))) == Z_NULL)
4471 		{
4472 			r = Z_MEM_ERROR;
4473 			LEAVE
4474 		}
4475 		DUMPBITS(14);
4476 		s->sub.trees.index = 0;
4477 		Tracev((stderr, "inflate:       table sizes ok\n"));
4478 		s->mode = BTREE;
4479 		/* FALLTHRU */
4480 	case BTREE:
4481 		while (s->sub.trees.index < 4 + (s->sub.trees.table >> 10))
4482 		{
4483 			NEEDBITS(3);
4484 			s->sub.trees.blens[border[s->sub.trees.index++]] =
4485 			    (uInt)b & 7;
4486 			DUMPBITS(3);
4487 		}
4488 		while (s->sub.trees.index < 19)
4489 			s->sub.trees.blens[border[s->sub.trees.index++]] =
4490 			    0;
4491 		s->sub.trees.bb = 7;
4492 		t = inflate_trees_bits(s->sub.trees.blens, &s->sub.trees.bb,
4493 		    &s->sub.trees.tb, s->hufts, z);
4494 		if (t != Z_OK)
4495 		{
4496 			ZFREE(z, s->sub.trees.blens);
4497 			s->sub.trees.blens = Z_NULL;
4498 			r = t;
4499 			if (r == Z_DATA_ERROR)
4500 				s->mode = BADB;
4501 			LEAVE
4502 		}
4503 		s->sub.trees.index = 0;
4504 		Tracev((stderr, "inflate:       bits tree ok\n"));
4505 		s->mode = DTREE;
4506 		/* FALLTHRU */
4507 	case DTREE:
4508 		while (t = s->sub.trees.table,
4509 		    s->sub.trees.index < 258 + (t & 0x1f) +
4510 		    ((t >> 5) & 0x1f))
4511 		{
4512 			inflate_huft *h;
4513 			uInt i, j, c;
4514 
4515 			t = s->sub.trees.bb;
4516 			NEEDBITS(t);
4517 			h = s->sub.trees.tb + ((uInt)b & inflate_mask[t]);
4518 			t = h->word.what.Bits;
4519 			c = h->base;
4520 			if (c < 16)
4521 			{
4522 				DUMPBITS(t);
4523 				s->sub.trees.blens[s->sub.trees.index++] =
4524 				    c;
4525 			} else { /* c == 16..18 */
4526 				i = c == 18 ? 7 : c - 14;
4527 				j = c == 18 ? 11 : 3;
4528 				NEEDBITS(t + i);
4529 				DUMPBITS(t);
4530 				j += (uInt)b & inflate_mask[i];
4531 				DUMPBITS(i);
4532 				i = s->sub.trees.index;
4533 				t = s->sub.trees.table;
4534 				if (i + j > 258 + (t & 0x1f) +
4535 				    ((t >> 5) & 0x1f) ||
4536 				    (c == 16 && i < 1))
4537 				{
4538 					ZFREE(z, s->sub.trees.blens);
4539 					s->sub.trees.blens = Z_NULL;
4540 					s->mode = BADB;
4541 					z->msg = "invalid bit length repeat";
4542 					r = Z_DATA_ERROR;
4543 					LEAVE
4544 				}
4545 				c = c == 16 ? s->sub.trees.blens[i - 1] : 0;
4546 				do {
4547 					s->sub.trees.blens[i++] = c;
4548 				} while (--j);
4549 				s->sub.trees.index = i;
4550 			}
4551 		}
4552 		s->sub.trees.tb = Z_NULL;
4553 		{
4554 			uInt bl, bd;
4555 			inflate_huft *tl, *td;
4556 			inflate_codes_statef *c;
4557 
4558 				/* must be <= 9 for lookahead assumptions */
4559 			bl = 9;
4560 				/* must be <= 9 for lookahead assumptions */
4561 			bd = 6;
4562 			t = s->sub.trees.table;
4563 			t = inflate_trees_dynamic(257 + (t & 0x1f),
4564 			    1 + ((t >> 5) & 0x1f),
4565 			    s->sub.trees.blens, &bl, &bd, &tl, &td,
4566 			    s->hufts, z);
4567 			ZFREE(z, s->sub.trees.blens);
4568 			s->sub.trees.blens = Z_NULL;
4569 			if (t != Z_OK)
4570 			{
4571 				if (t == (uInt)Z_DATA_ERROR)
4572 					s->mode = BADB;
4573 				r = t;
4574 				LEAVE
4575 			}
4576 			Tracev((stderr, "inflate:       trees ok\n"));
4577 			if ((c = inflate_codes_new(bl, bd, tl, td, z)) ==
4578 			    Z_NULL)
4579 			{
4580 				r = Z_MEM_ERROR;
4581 				LEAVE
4582 			}
4583 			s->sub.decode.codes = c;
4584 		}
4585 		s->mode = CODES;
4586 		/* FALLTHRU */
4587 	case CODES:
4588 		UPDATE;
4589 		if ((r = inflate_codes(s, z, r)) != Z_STREAM_END)
4590 			return (inflate_flush(s, z, r));
4591 		r = Z_OK;
4592 		(void) inflate_codes_free(s->sub.decode.codes, z);
4593 		LOAD;
4594 		Tracev((stderr, "inflate:       codes end, %lu total out\n",
4595 		    z->total_out + (q >= s->read ? q - s->read :
4596 			(s->end - s->read) + (q - s->window))));
4597 		if (!s->last)
4598 		{
4599 			s->mode = TYPE;
4600 			break;
4601 		}
4602 		s->mode = DRY;
4603 		/* FALLTHRU */
4604 	case DRY:
4605 		FLUSH;
4606 		if (s->read != s->write)
4607 			LEAVE
4608 		s->mode = DONEB;
4609 		/* FALLTHRU */
4610 	case DONEB:
4611 		r = Z_STREAM_END;
4612 		LEAVE
4613 	case BADB:
4614 		r = Z_DATA_ERROR;
4615 		LEAVE
4616 	default:
4617 		r = Z_STREAM_ERROR;
4618 		LEAVE
4619 	}
4620 	/* NOTREACHED */
4621 	/* otherwise lint complains */
4622 }
4623 
4624 
4625 int
4626 inflate_blocks_free(s, z)
4627 inflate_blocks_statef *s;
4628 z_streamp z;
4629 {
4630 	inflate_blocks_reset(s, z, Z_NULL);
4631 	ZFREE(z, s->window);
4632 	s->window = Z_NULL;
4633 	ZFREE(z, s->hufts);
4634 	s->hufts = Z_NULL;
4635 	ZFREE(z, s);
4636 	Trace((stderr, "inflate:   blocks freed\n"));
4637 	return (Z_OK);
4638 }
4639 
4640 
4641 void
4642 inflate_set_dictionary(s, d, n)
4643 inflate_blocks_statef *s;
4644 const Bytef *d;
4645 uInt  n;
4646 {
4647 	Assert(s->window + n <= s->end, "set dict");
4648 	zmemcpy((charf *)s->window, d, n);
4649 	s->read = s->write = s->window + n;
4650 }
4651 
4652 /*
4653  * Returns true if inflate is currently at the end of a block
4654  * generated by Z_SYNC_FLUSH or Z_FULL_FLUSH.
4655  * IN assertion: s != Z_NULL
4656  */
4657 int
4658 inflate_blocks_sync_point(s)
4659 inflate_blocks_statef *s;
4660 {
4661 	return (s->mode == LENS);
4662 }
4663 
4664 /*
4665  * This subroutine adds the data at next_in/avail_in to the output history
4666  * without performing any output.  The output buffer must be "caught up";
4667  * i.e. no pending output (hence s->read equals s->write), and the state must
4668  * be BLOCKS (i.e. we should be willing to see the start of a series of
4669  * BLOCKS).  On exit, the output will also be caught up, and the checksum
4670  * will have been updated if need be.
4671  */
4672 int
4673 inflate_addhistory(s, z)
4674 inflate_blocks_statef *s;
4675 z_stream *z;
4676 {
4677 	uLong b;	/* bit buffer */  /* NOT USED HERE */
4678 	uInt k;	/* bits in bit buffer */ /* NOT USED HERE */
4679 	uInt t;	/* temporary storage */
4680 	Bytef *p;	/* input data pointer */
4681 	uInt n;	/* bytes available there */
4682 	Bytef *q;	/* output window write pointer */
4683 	uInt m;	/* bytes to end of window or read pointer */
4684 
4685 	if (s->read != s->write)
4686 		return (Z_STREAM_ERROR);
4687 	if (s->mode != TYPE)
4688 		return (Z_DATA_ERROR);
4689 
4690 	/* we're ready to rock */
4691 	LOAD;
4692 	/*
4693 	 * while there is input ready, copy to output buffer, moving
4694 	 * pointers as needed.
4695 	 */
4696 	while (n) {
4697 		t = n;	/* how many to do */
4698 		/* is there room until end of buffer? */
4699 		if (t > m) t = m;
4700 		/* update check information */
4701 		if (s->checkfn != Z_NULL)
4702 			s->check = (*s->checkfn)(s->check, q, t);
4703 		zmemcpy(q, p, t);
4704 		q += t;
4705 		p += t;
4706 		n -= t;
4707 		z->total_out += t;
4708 		s->read = q;	/* drag read pointer forward */
4709 /* WWRAP */	/* expand WWRAP macro by hand to handle s->read */
4710 		if (q == s->end) {
4711 			s->read = q = s->window;
4712 			m = WAVAIL;
4713 		}
4714 	}
4715 	UPDATE;
4716 	return (Z_OK);
4717 }
4718 
4719 
4720 /*
4721  * At the end of a Deflate-compressed PPP packet, we expect to have seen
4722  * a `stored' block type value but not the (zero) length bytes.
4723  */
4724 int
4725 inflate_packet_flush(s)
4726     inflate_blocks_statef *s;
4727 {
4728 	if (s->mode != LENS)
4729 		return (Z_DATA_ERROR);
4730 	s->mode = TYPE;
4731 	return (Z_OK);
4732 }
4733 /* --- infblock.c */
4734 
4735 /* +++ inftrees.c */
4736 /*
4737  * inftrees.c -- generate Huffman trees for efficient decoding
4738  * Copyright (C) 1995-1998 Mark Adler
4739  * For conditions of distribution and use, see copyright notice in zlib.h
4740  */
4741 
4742 /* #include "zutil.h" */
4743 /* #include "inftrees.h" */
4744 
4745 const char inflate_copyright[] =
4746 " inflate 1.1.3 Copyright 1995-1998 Mark Adler ";
4747 /*
4748  * If you use the zlib library in a product, an acknowledgment is
4749  * welcome in the documentation of your product. If for some reason
4750  * you cannot include such an acknowledgment, I would appreciate that
4751  * you keep this copyright string in the executable of your product.
4752  */
4753 
4754 #ifndef NO_DUMMY_DECL
4755 struct internal_state  {int dummy; };	/* for buggy compilers */
4756 #endif
4757 
4758 /* simplify the use of the inflate_huft type with some defines */
4759 #define	exop word.what.Exop
4760 #define	bits word.what.Bits
4761 
4762 
4763 local int huft_build OF((
4764 	uIntf *,	/* code lengths in bits */
4765 	uInt,		/* number of codes */
4766 	uInt,		/* number of "simple" codes */
4767 	const uIntf *,	/* list of base values for non-simple codes */
4768 	const uIntf *,	/* list of extra bits for non-simple codes */
4769 	inflate_huft * FAR*, /* result: starting table */
4770 	uIntf *,	/* maximum lookup bits (returns actual) */
4771 	inflate_huft *hp,	/* space for trees */
4772 	uInt *hn,	/* hufts used in space */
4773 	uIntf *v));	/* working area: values in order of bit length */
4774 
4775 /* Tables for deflate from PKZIP's appnote.txt. */
4776 local const uInt cplens[31] = { /* Copy lengths for literal codes 257..285 */
4777 	3, 4, 5, 6, 7, 8, 9, 10, 11, 13, 15, 17, 19, 23, 27, 31,
4778 	35, 43, 51, 59, 67, 83, 99, 115, 131, 163, 195, 227, 258, 0, 0};
4779 	/* see note #13 above about 258 */
4780 local const uInt cplext[31] = { /* Extra bits for literal codes 257..285 */
4781 	0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 2, 2, 2, 2,
4782 	3, 3, 3, 3, 4, 4, 4, 4, 5, 5, 5, 5, 0, 112, 112};
4783 	/* 112==invalid */
4784 local const uInt cpdist[30] = { /* Copy offsets for distance codes 0..29 */
4785 	1, 2, 3, 4, 5, 7, 9, 13, 17, 25, 33, 49, 65, 97, 129, 193,
4786 	257, 385, 513, 769, 1025, 1537, 2049, 3073, 4097, 6145,
4787 	8193, 12289, 16385, 24577};
4788 local const uInt cpdext[30] = { /* Extra bits for distance codes */
4789 	0, 0, 0, 0, 1, 1, 2, 2, 3, 3, 4, 4, 5, 5, 6, 6,
4790 	7, 7, 8, 8, 9, 9, 10, 10, 11, 11,
4791 	12, 12, 13, 13};
4792 
4793 /*
4794  * Huffman code decoding is performed using a multi-level table
4795  * lookup.  The fastest way to decode is to simply build a lookup
4796  * table whose size is determined by the longest code.  However, the
4797  * time it takes to build this table can also be a factor if the data
4798  * being decoded is not very long.  The most common codes are
4799  * necessarily the shortest codes, so those codes dominate the
4800  * decoding time, and hence the speed.  The idea is you can have a
4801  * shorter table that decodes the shorter, more probable codes, and
4802  * then point to subsidiary tables for the longer codes.  The time it
4803  * costs to decode the longer codes is then traded against the time it
4804  * takes to make longer tables.
4805  *
4806  * This results of this trade are in the variables lbits and dbits
4807  * below.  lbits is the number of bits the first level table for
4808  * literal/ length codes can decode in one step, and dbits is the same
4809  * thing for the distance codes.  Subsequent tables are also less than
4810  * or equal to those sizes.  These values may be adjusted either when
4811  * all of the codes are shorter than that, in which case the longest
4812  * code length in bits is used, or when the shortest code is *longer*
4813  * than the requested table size, in which case the length of the
4814  * shortest code in bits is used.
4815  *
4816  * There are two different values for the two tables, since they code
4817  * a different number of possibilities each.  The literal/length table
4818  * codes 286 possible values, or in a flat code, a little over eight
4819  * bits.  The distance table codes 30 possible values, or a little
4820  * less than five bits, flat.  The optimum values for speed end up
4821  * being about one bit more than those, so lbits is 8+1 and dbits is
4822  * 5+1.  The optimum values may differ though from machine to machine,
4823  * and possibly even between compilers.  Your mileage may vary.
4824  */
4825 
4826 
4827 /* If BMAX needs to be larger than 16, then h and x[] should be uLong. */
4828 #define	BMAX 15		/* maximum bit length of any code */
4829 
4830 
4831 local int
4832 huft_build(b, n, s, d, e, t, m, hp, hn, v)
4833 uIntf *b;	/* code lengths in bits (all assumed <= BMAX) */
4834 uInt n;	/* number of codes (assumed <= 288) */
4835 uInt s;	/* number of simple-valued codes (0..s-1) */
4836 const uIntf *d;	/* list of base values for non-simple codes */
4837 const uIntf *e;	/* list of extra bits for non-simple codes */
4838 inflate_huft * FAR *t;	/* result: starting table */
4839 uIntf *m;	/* maximum lookup bits, returns actual */
4840 inflate_huft *hp;	/* space for trees */
4841 uInt *hn;		/* hufts used in space */
4842 uIntf *v;		/* working area: values in order of bit length */
4843 /*
4844  * Given a list of code lengths and a maximum table size, make a set
4845  * of tables to decode that set of codes.  Return Z_OK on success,
4846  * Z_BUF_ERROR if the given code set is incomplete (the tables are
4847  * still built in this case), Z_DATA_ERROR if the input is invalid (an
4848  * over-subscribed set of lengths), or Z_MEM_ERROR if not enough
4849  * memory.
4850  */
4851 {
4852 
4853 	uInt a;	/* counter for codes of length k */
4854 	uInt c[BMAX+1];	/* bit length count table */
4855 	uInt f;	/* i repeats in table every f entries */
4856 	int g;	/* maximum code length */
4857 	int h;	/* table level */
4858 	register uInt i;	/* counter, current code */
4859 	register uInt j;	/* counter */
4860 	register int k;	/* number of bits in current code */
4861 	int l;	/* bits per table (returned in m) */
4862 	register uIntf *p;	/* pointer into c[], b[], or v[] */
4863 	inflate_huft *q;	/* points to current table */
4864 	struct inflate_huft_s r; /* table entry for structure assignment */
4865 	inflate_huft *u[BMAX];	/* table stack */
4866 	uInt mask;	/* (1 << w) - 1, to avoid cc -O bug on HP */
4867 	register int w;	/* bits before this table == (l * h) */
4868 	uInt x[BMAX+1];	/* bit offsets, then code stack */
4869 	uIntf *xp;	/* pointer into x */
4870 	int y;	/* number of dummy codes added */
4871 	uInt z;	/* number of entries in current table */
4872 
4873 	(void) inflate_copyright;
4874 	/* Generate counts for each bit length */
4875 	p = c;
4876 #define	C0 *p++ = 0;
4877 #define	C2 C0 C0 C0 C0
4878 #define	C4 C2 C2 C2 C2
4879 	C4	/* clear c[]--assume BMAX+1 is 16 */
4880 	    p = b;  i = n;
4881 	do {
4882 		c[*p++]++;	/* assume all entries <= BMAX */
4883 	} while (--i);
4884 	if (c[0] == n)		/* null input--all zero length codes */
4885 	{
4886 		*t = (inflate_huft *)Z_NULL;
4887 		*m = 0;
4888 		return (Z_OK);
4889 	}
4890 
4891 
4892 	/* Find minimum and maximum length, bound *m by those */
4893 	l = *m;
4894 	for (j = 1; j <= BMAX; j++)
4895 		if (c[j])
4896 			break;
4897 	k = j;	/* minimum code length */
4898 	if ((uInt)l < j)
4899 		l = j;
4900 	for (i = BMAX; i; i--)
4901 		if (c[i])
4902 			break;
4903 	g = i;	/* maximum code length */
4904 	if ((uInt)l > i)
4905 		l = i;
4906 	*m = l;
4907 
4908 
4909 	/* Adjust last length count to fill out codes, if needed */
4910 	for (y = 1 << j; j < i; j++, y <<= 1)
4911 		if ((y -= c[j]) < 0)
4912 			return (Z_DATA_ERROR);
4913 	if ((y -= c[i]) < 0)
4914 		return (Z_DATA_ERROR);
4915 	c[i] += y;
4916 
4917 
4918 	/* Generate starting offsets into the value table for each length */
4919 	x[1] = j = 0;
4920 	p = c + 1;  xp = x + 2;
4921 	while (--i) {		/* note that i == g from above */
4922 		*xp++ = (j += *p++);
4923 	}
4924 
4925 
4926 	/* Make a table of values in order of bit lengths */
4927 	p = b;  i = 0;
4928 	do {
4929 		if ((j = *p++) != 0)
4930 			v[x[j]++] = i;
4931 	} while (++i < n);
4932 	n = x[g];	/* set n to length of v */
4933 
4934 
4935 	/* Generate the Huffman codes and for each, make the table entries */
4936 	x[0] = i = 0;	/* first Huffman code is zero */
4937 	p = v;	/* grab values in bit order */
4938 	h = -1;	/* no tables yet--level -1 */
4939 	w = -l;	/* bits decoded == (l * h) */
4940 	u[0] = (inflate_huft *)Z_NULL;	/* just to keep compilers happy */
4941 	q = (inflate_huft *)Z_NULL;	/* ditto */
4942 	z = 0;	/* ditto */
4943 
4944 	/* go through the bit lengths (k already is bits in shortest code) */
4945 	for (; k <= g; k++) {
4946 		a = c[k];
4947 		while (a--) {
4948 			/*
4949 			 * here i is the Huffman code of length k bits
4950 			 * for value *p.  make tables up to required
4951 			 * level.
4952 			 */
4953 			while (k > w + l) {
4954 				h++;
4955 				w += l;	/* previous table always l bits */
4956 
4957 				/*
4958 				 * compute minimum size table less
4959 				 * than or equal to l bits
4960 				 */
4961 				z = g - w;
4962 				/* table size upper limit */
4963 				z = z > (uInt)l ? l : z;
4964 				/* try a k-w bit table */
4965 				if ((f = 1 << (j = k - w)) > a + 1) {
4966 					/* too few codes for k-w bit table */
4967 					/* deduct codes from patterns left */
4968 					f -= a + 1;
4969 					xp = c + k;
4970 					if (j < z)
4971 						/*
4972 						 * try smaller tables
4973 						 * up to z bits
4974 						 */
4975 						while (++j < z) {
4976 							/*
4977 							 * enough
4978 							 * codes to
4979 							 * use up j
4980 							 * bits
4981 							 */
4982 							if ((f <<= 1) <= *++xp)
4983 								break;
4984 							f -= *xp;
4985 							/*
4986 							 * else deduct
4987 							 * codes from
4988 							 * patterns
4989 							 */
4990 						}
4991 				}
4992 				/* table entries for j-bit table */
4993 				z = 1 << j;
4994 
4995 				/* allocate new table */
4996 				/* (note: doesn't matter for fixed) */
4997 				/* not enough memory */
4998 				if (*hn + z > MANY)
4999 					return (Z_MEM_ERROR);
5000 				u[h] = q = hp + *hn;
5001 				*hn += z;
5002 
5003 				/* connect to last table, if there is one */
5004 				if (h) {
5005 					/* save pattern for backing up */
5006 					x[h] = i;
5007 					/* bits to dump before this table */
5008 					r.bits = (Byte)l;
5009 					/* bits in this table */
5010 					r.exop = (Byte)j;
5011 					j = i >> (w - l);
5012 					/* offset to this table */
5013 					r.base = (uInt)(q - u[h-1] - j);
5014 					/* connect to last table */
5015 					u[h-1][j] = r;
5016 				} else
5017 					/* first table is returned result */
5018 					*t = q;
5019 			}
5020 
5021 			/* set up table entry in r */
5022 			r.bits = (Byte)(k - w);
5023 			if (p >= v + n)
5024 				/* out of values--invalid code */
5025 				r.exop = 128 + 64;
5026 			else if (*p < s)
5027 			{
5028 				/* 256 is end-of-block */
5029 				r.exop = (Byte)(*p < 256 ? 0 : 32 + 64);
5030 				/* simple code is just the value */
5031 				r.base = *p++;
5032 			}
5033 			else
5034 			{
5035 				/* non-simple--look up in lists */
5036 				r.exop = (Byte)(e[*p - s] + 16 + 64);
5037 				r.base = d[*p++ - s];
5038 			}
5039 
5040 			/* fill code-like entries with r */
5041 			f = 1 << (k - w);
5042 			for (j = i >> w; j < z; j += f)
5043 				q[j] = r;
5044 
5045 			/* backwards increment the k-bit code i */
5046 			for (j = 1 << (k - 1); i & j; j >>= 1)
5047 				i ^= j;
5048 			i ^= j;
5049 
5050 			/* backup over finished tables */
5051 			mask = (1 << w) - 1;	/* needed on HP, cc -O bug */
5052 			while ((i & mask) != x[h])
5053 			{
5054 				h--;	/* don't need to update q */
5055 				w -= l;
5056 				mask = (1 << w) - 1;
5057 			}
5058 		}
5059 	}
5060 
5061 
5062 	/* Return Z_BUF_ERROR if we were given an incomplete table */
5063 	return (y != 0 && g != 1 ? Z_BUF_ERROR : Z_OK);
5064 }
5065 
5066 
5067 int
5068 inflate_trees_bits(c, bb, tb, hp, z)
5069 uIntf *c;	/* 19 code lengths */
5070 uIntf *bb;	/* bits tree desired/actual depth */
5071 inflate_huft * FAR *tb;	/* bits tree result */
5072 inflate_huft *hp;	/* space for trees */
5073 z_streamp z;	/* for zfree function */
5074 {
5075 	int r;
5076 	uInt hn = 0;		/* hufts used in space */
5077 	uIntf v[19];		/* work area for huft_build */
5078 
5079 	r = huft_build(c, 19, 19, (uIntf*)Z_NULL, (uIntf*)Z_NULL, tb, bb,
5080 	    hp, &hn, v);
5081 	if (r == Z_DATA_ERROR)
5082 		z->msg = "oversubscribed dynamic bit lengths tree";
5083 	else if (r == Z_BUF_ERROR || *bb == 0)
5084 	{
5085 		z->msg = "incomplete dynamic bit lengths tree";
5086 		r = Z_DATA_ERROR;
5087 	}
5088 	return (r);
5089 }
5090 
5091 
5092 int
5093 inflate_trees_dynamic(nl, nd, c, bl, bd, tl, td, hp, z)
5094 uInt nl;	/* number of literal/length codes */
5095 uInt nd;	/* number of distance codes */
5096 uIntf *c;	/* that many (total) code lengths */
5097 uIntf *bl;	/* literal desired/actual bit depth */
5098 uIntf *bd;	/* distance desired/actual bit depth */
5099 inflate_huft * FAR *tl;	/* literal/length tree result */
5100 inflate_huft * FAR *td;	/* distance tree result */
5101 inflate_huft *hp;	/* space for trees */
5102 z_streamp z;	/* for zfree function */
5103 {
5104 	int r;
5105 	uInt hn = 0;		/* hufts used in space */
5106 	uIntf v[288];		/* work area for huft_build */
5107 
5108 	/* build literal/length tree */
5109 	r = huft_build(c, nl, 257, cplens, cplext, tl, bl, hp, &hn, v);
5110 	if (r != Z_OK || *bl == 0)
5111 	{
5112 		if (r == Z_DATA_ERROR)
5113 			z->msg = "oversubscribed literal/length tree";
5114 		else if (r != Z_MEM_ERROR)
5115 		{
5116 			z->msg = "incomplete literal/length tree";
5117 			r = Z_DATA_ERROR;
5118 		}
5119 		return (r);
5120 	}
5121 
5122 	/* build distance tree */
5123 	r = huft_build(c + nl, nd, 0, cpdist, cpdext, td, bd, hp, &hn, v);
5124 	if (r != Z_OK || (*bd == 0 && nl > 257))
5125 	{
5126 		if (r == Z_DATA_ERROR)
5127 			z->msg = "oversubscribed distance tree";
5128 		else if (r == Z_BUF_ERROR) {
5129 #ifdef PKZIP_BUG_WORKAROUND
5130 			r = Z_OK;
5131 #else
5132 			z->msg = "incomplete distance tree";
5133 			r = Z_DATA_ERROR;
5134 		} else if (r != Z_MEM_ERROR) {
5135 			z->msg = "empty distance tree with lengths";
5136 			r = Z_DATA_ERROR;
5137 #endif
5138 		}
5139 		return (r);
5140 	}
5141 
5142 /* done */
5143 	return (Z_OK);
5144 }
5145 
5146 
5147 /* build fixed tables only once--keep them here */
5148 /* #define	BUILDFIXED */
5149 #ifdef BUILDFIXED
5150 local int fixed_built = 0;
5151 #define	FIXEDH 544	/* number of hufts used by fixed tables */
5152 local inflate_huft fixed_mem[FIXEDH];
5153 local uInt fixed_bl;
5154 local uInt fixed_bd;
5155 local inflate_huft *fixed_tl;
5156 local inflate_huft *fixed_td;
5157 #else
5158 #include "inffixed.h"
5159 #endif
5160 
5161 /*ARGSUSED*/
5162 int
5163 inflate_trees_fixed(bl, bd, tl, td, z)
5164 uIntf *bl;	/* literal desired/actual bit depth */
5165 uIntf *bd;	/* distance desired/actual bit depth */
5166 const inflate_huft * FAR *tl;	/* literal/length tree result */
5167 const inflate_huft * FAR *td;	/* distance tree result */
5168 z_streamp z;	/* for memory allocation */
5169 {
5170 #ifdef BUILDFIXED
5171 	/*
5172 	 * build fixed tables if not already (multiple overlapped
5173 	 * executions ok)
5174 	 */
5175 	if (!fixed_built)
5176 	{
5177 		int k;	/* temporary variable */
5178 		uInt f = 0;	/* number of hufts used in fixed_mem */
5179 		uIntf *c;	/* length list for huft_build */
5180 		uIntf *v;
5181 
5182 		/* allocate memory */
5183 		if ((c = (uIntf*)ZALLOC(z, 288, sizeof (uInt))) == Z_NULL)
5184 			return (Z_MEM_ERROR);
5185 		if ((v = (uIntf*)ZALLOC(z, 288, sizeof (uInt))) == Z_NULL)
5186 		{
5187 			ZFREE(z, c);
5188 			return (Z_MEM_ERROR);
5189 		}
5190 		/* literal table */
5191 		for (k = 0; k < 144; k++)
5192 			c[k] = 8;
5193 		for (; k < 256; k++)
5194 			c[k] = 9;
5195 		for (; k < 280; k++)
5196 			c[k] = 7;
5197 		for (; k < 288; k++)
5198 			c[k] = 8;
5199 		fixed_bl = 9;
5200 		(void) huft_build(c, 288, 257, cplens, cplext, &fixed_tl,
5201 		    &fixed_bl, fixed_mem, &f, v);
5202 
5203 		/* distance table */
5204 		for (k = 0; k < 30; k++)
5205 			c[k] = 5;
5206 		fixed_bd = 5;
5207 		(void) huft_build(c, 30, 0, cpdist, cpdext, &fixed_td,
5208 		    &fixed_bd, fixed_mem, &f, v);
5209 
5210 		/* done */
5211 		ZFREE(z, v);
5212 		ZFREE(z, c);
5213 		fixed_built = 1;
5214 	}
5215 #endif
5216 	*bl = fixed_bl;
5217 	*bd = fixed_bd;
5218 	*tl = fixed_tl;
5219 	*td = fixed_td;
5220 	return (Z_OK);
5221 }
5222 /* --- inftrees.c */
5223 
5224 /* +++ infcodes.c */
5225 /*
5226  * infcodes.c -- process literals and length/distance pairs
5227  * Copyright (C) 1995-1998 Mark Adler
5228  * For conditions of distribution and use, see copyright notice in zlib.h
5229  */
5230 
5231 /* #include "zutil.h" */
5232 /* #include "inftrees.h" */
5233 /* #include "infblock.h" */
5234 /* #include "infcodes.h" */
5235 /* #include "infutil.h" */
5236 
5237 /* +++ inffast.h */
5238 /*
5239  * inffast.h -- header to use inffast.c
5240  * Copyright (C) 1995-1998 Mark Adler
5241  * For conditions of distribution and use, see copyright notice in zlib.h
5242  */
5243 
5244 /*
5245  * WARNING: this file should *not* be used by applications. It is part
5246  * of the implementation of the compression library and is subject to
5247  * change. Applications should only use zlib.h.
5248  */
5249 
5250 extern int inflate_fast OF((
5251     uInt,
5252     uInt,
5253     const inflate_huft *,
5254     const inflate_huft *,
5255     inflate_blocks_statef *,
5256     z_streamp));
5257 /* --- inffast.h */
5258 
5259 /* simplify the use of the inflate_huft type with some defines */
5260 #define	exop word.what.Exop
5261 #define	bits word.what.Bits
5262 
5263 /* inflate codes private state */
5264 struct inflate_codes_state {
5265 
5266 	/* mode */
5267 	enum {	/* waiting for "i:"=input, "o:"=output, "x:"=nothing */
5268 		START,	/* x: set up for LEN */
5269 		LEN,	/* i: get length/literal/eob next */
5270 		LENEXT,	/* i: getting length extra (have base) */
5271 		DIST,	/* i: get distance next */
5272 		DISTEXT,	/* i: getting distance extra */
5273 		COPY,	/* o: copying bytes in window, waiting for space */
5274 		LIT,	/* o: got literal, waiting for output space */
5275 		WASH,	/* o: got eob, possibly still output waiting */
5276 		END,	/* x: got eob and all data flushed */
5277 		BADCODE}	/* x: got error */
5278 	mode;	/* current inflate_codes mode */
5279 
5280 	/* mode dependent information */
5281 	uInt len;
5282 	union {
5283 		struct {
5284 			const inflate_huft *tree;	/* pointer into tree */
5285 			uInt need;	/* bits needed */
5286 		} code;	/* if LEN or DIST, where in tree */
5287 		uInt lit;	/* if LIT, literal */
5288 		struct {
5289 			uInt get;	/* bits to get for extra */
5290 			uInt dist;	/* distance back to copy from */
5291 		} copy;	/* if EXT or COPY, where and how much */
5292 	} sub;	/* submode */
5293 
5294 	/* mode independent information */
5295 	Byte lbits;	/* ltree bits decoded per branch */
5296 	Byte dbits;	/* dtree bits decoder per branch */
5297 	const inflate_huft *ltree;	/* literal/length/eob tree */
5298 	const inflate_huft *dtree;	/* distance tree */
5299 
5300 };
5301 
5302 
5303 inflate_codes_statef *
5304 inflate_codes_new(bl, bd, tl, td, z)
5305 uInt bl, bd;
5306 const inflate_huft *tl;
5307 const inflate_huft *td;	/* need separate declaration for Borland C++ */
5308 z_streamp z;
5309 {
5310 	inflate_codes_statef *c;
5311 
5312 	if ((c = (inflate_codes_statef *)
5313 	    ZALLOC(z, 1, sizeof (struct inflate_codes_state))) != Z_NULL)
5314 	{
5315 		c->mode = START;
5316 		c->lbits = (Byte)bl;
5317 		c->dbits = (Byte)bd;
5318 		c->ltree = tl;
5319 		c->dtree = td;
5320 		Tracev((stderr, "inflate:       codes new\n"));
5321 	}
5322 	return (c);
5323 }
5324 
5325 
5326 int
5327 inflate_codes(s, z, r)
5328 inflate_blocks_statef *s;
5329 z_streamp z;
5330 int r;
5331 {
5332 	uInt j;	/* temporary storage */
5333 	const inflate_huft *t;	/* temporary pointer */
5334 	uInt e;	/* extra bits or operation */
5335 	uLong b;	/* bit buffer */
5336 	uInt k;	/* bits in bit buffer */
5337 	Bytef *p;	/* input data pointer */
5338 	uInt n;	/* bytes available there */
5339 	Bytef *q;	/* output window write pointer */
5340 	uInt m;	/* bytes to end of window or read pointer */
5341 	Bytef *f;	/* pointer to copy strings from */
5342 	inflate_codes_statef *c = s->sub.decode.codes;	/* codes state */
5343 
5344 	/* copy input/output information to locals (UPDATE macro restores) */
5345 	LOAD;
5346 
5347 	/* process input and output based on current state */
5348 	/* CONSTCOND */
5349 	while (1)
5350 		/* waiting for "i:"=input, "o:"=output, "x:"=nothing */
5351 		switch (c->mode) {
5352 		case START:	/* x: set up for LEN */
5353 #ifndef SLOW
5354 			if (m >= 258 && n >= 10)
5355 			{
5356 				UPDATE;
5357 				r = inflate_fast(c->lbits, c->dbits,
5358 				    c->ltree, c->dtree, s, z);
5359 				LOAD;
5360 				if (r != Z_OK) {
5361 					c->mode = r == Z_STREAM_END ?
5362 					    WASH : BADCODE;
5363 					break;
5364 				}
5365 			}
5366 #endif /* !SLOW */
5367 			c->sub.code.need = c->lbits;
5368 			c->sub.code.tree = c->ltree;
5369 			c->mode = LEN;
5370 			/* FALLTHRU */
5371 		case LEN:	/* i: get length/literal/eob next */
5372 			j = c->sub.code.need;
5373 			NEEDBITS(j);
5374 			t = c->sub.code.tree +
5375 			    ((uInt)b & inflate_mask[j]);
5376 			DUMPBITS(t->bits);
5377 			e = (uInt)(t->exop);
5378 			if (e == 0) {	/* literal */
5379 				c->sub.lit = t->base;
5380 				Tracevv((stderr, t->base >= 0x20 &&
5381 				    t->base < 0x7f ?
5382 				    "inflate:         literal '%c'\n" :
5383 				    "inflate:         literal 0x%02x\n",
5384 				    t->base));
5385 				c->mode = LIT;
5386 				break;
5387 			}
5388 			if (e & 16) {	/* length */
5389 				c->sub.copy.get = e & 15;
5390 				c->len = t->base;
5391 				c->mode = LENEXT;
5392 				break;
5393 			}
5394 			if ((e & 64) == 0) {	/* next table */
5395 				c->sub.code.need = e;
5396 				c->sub.code.tree = t + t->base;
5397 				break;
5398 			}
5399 			if (e & 32) {	/* end of block */
5400 				Tracevv((stderr,
5401 				    "inflate:         end of block\n"));
5402 				c->mode = WASH;
5403 				break;
5404 			}
5405 			c->mode = BADCODE;	/* invalid code */
5406 			z->msg = "invalid literal/length code";
5407 			r = Z_DATA_ERROR;
5408 			LEAVE
5409 		case LENEXT:	/* i: getting length extra (have base) */
5410 			j = c->sub.copy.get;
5411 			NEEDBITS(j);
5412 			c->len += (uInt)b & inflate_mask[j];
5413 			DUMPBITS(j);
5414 			c->sub.code.need = c->dbits;
5415 			c->sub.code.tree = c->dtree;
5416 			Tracevv((stderr,
5417 			    "inflate:         length %u\n", c->len));
5418 			c->mode = DIST;
5419 			/* FALLTHRU */
5420 		case DIST:	/* i: get distance next */
5421 			j = c->sub.code.need;
5422 			NEEDBITS(j);
5423 			t = c->sub.code.tree + ((uInt)b & inflate_mask[j]);
5424 			DUMPBITS(t->bits);
5425 			e = (uInt)(t->exop);
5426 			if (e & 16) {	/* distance */
5427 				c->sub.copy.get = e & 15;
5428 				c->sub.copy.dist = t->base;
5429 				c->mode = DISTEXT;
5430 				break;
5431 			}
5432 			if ((e & 64) == 0) {	/* next table */
5433 				c->sub.code.need = e;
5434 				c->sub.code.tree = t + t->base;
5435 				break;
5436 			}
5437 			c->mode = BADCODE;	/* invalid code */
5438 			z->msg = "invalid distance code";
5439 			r = Z_DATA_ERROR;
5440 			LEAVE
5441 		case DISTEXT:	/* i: getting distance extra */
5442 			j = c->sub.copy.get;
5443 			NEEDBITS(j);
5444 			c->sub.copy.dist += (uInt)b & inflate_mask[j];
5445 			DUMPBITS(j);
5446 			Tracevv((stderr,
5447 			    "inflate:         distance %u\n",
5448 			    c->sub.copy.dist));
5449 			c->mode = COPY;
5450 			/* FALLTHRU */
5451 		case COPY:
5452 			/* o: copying bytes in window, waiting for space */
5453 #ifndef __TURBOC__ /* Turbo C bug for following expression */
5454 			f = (uInt)(q - s->window) < c->sub.copy.dist ?
5455 			    s->end - (c->sub.copy.dist - (q - s->window)) :
5456 				q - c->sub.copy.dist;
5457 #else
5458 			f = q - c->sub.copy.dist;
5459 			if ((uInt)(q - s->window) < c->sub.copy.dist)
5460 				f = s->end - (c->sub.copy.dist -
5461 				    (uInt)(q - s->window));
5462 #endif
5463 			while (c->len)
5464 			{
5465 				NEEDOUT;
5466 				OUTBYTE(*f++);
5467 				if (f == s->end)
5468 					f = s->window;
5469 				c->len--;
5470 			}
5471 			c->mode = START;
5472 			break;
5473 		case LIT:	/* o: got literal, waiting for output space */
5474 			NEEDOUT;
5475 			OUTBYTE(c->sub.lit);
5476 			c->mode = START;
5477 			break;
5478 		case WASH:	/* o: got eob, possibly more output */
5479 			if (k > 7) {	/* return unused byte, if any */
5480 				Assert(k < 16,
5481 				    "inflate_codes grabbed too many bytes");
5482 				k -= 8;
5483 				n++;
5484 				p--;	/* can always return one */
5485 			}
5486 			FLUSH;
5487 			if (s->read != s->write)
5488 				LEAVE
5489 			c->mode = END;
5490 			/* FALLTHRU */
5491 		case END:
5492 			r = Z_STREAM_END;
5493 			LEAVE
5494 		case BADCODE:	/* x: got error */
5495 			r = Z_DATA_ERROR;
5496 			LEAVE
5497 		default:
5498 			r = Z_STREAM_ERROR;
5499 			LEAVE
5500 		}
5501 	/* NOTREACHED */
5502 	/* otherwise lint complains */
5503 }
5504 
5505 
5506 void
5507 inflate_codes_free(c, z)
5508 inflate_codes_statef *c;
5509 z_streamp z;
5510 {
5511 	ZFREE(z, c);
5512 	Tracev((stderr, "inflate:       codes free\n"));
5513 }
5514 /* --- infcodes.c */
5515 
5516 /* +++ infutil.c */
5517 /*
5518  * inflate_util.c -- data and routines common to blocks and codes
5519  * Copyright (C) 1995-1998 Mark Adler
5520  * For conditions of distribution and use, see copyright notice in zlib.h
5521  */
5522 
5523 /* #include "zutil.h" */
5524 /* #include "infblock.h" */
5525 /* #include "inftrees.h" */
5526 /* #include "infcodes.h" */
5527 /* #include "infutil.h" */
5528 
5529 #ifndef NO_DUMMY_DECL
5530 struct inflate_codes_state {int dummy; };	/* for buggy compilers */
5531 #endif
5532 
5533 /* And'ing with mask[n] masks the lower n bits */
5534 uInt inflate_mask[17] = {
5535 	0x0000,
5536 	0x0001, 0x0003, 0x0007, 0x000f, 0x001f, 0x003f, 0x007f, 0x00ff,
5537 	0x01ff, 0x03ff, 0x07ff, 0x0fff, 0x1fff, 0x3fff, 0x7fff, 0xffff
5538 };
5539 
5540 
5541 /* copy as much as possible from the sliding window to the output area */
5542 int
5543 inflate_flush(s, z, r)
5544 inflate_blocks_statef *s;
5545 z_streamp z;
5546 int r;
5547 {
5548 	uInt n;
5549 	Bytef *p;
5550 	Bytef *q;
5551 
5552 	/* local copies of source and destination pointers */
5553 	p = z->next_out;
5554 	q = s->read;
5555 
5556 	/* compute number of bytes to copy as far as end of window */
5557 	n = (uInt)((q <= s->write ? s->write : s->end) - q);
5558 	if (n > z->avail_out) n = z->avail_out;
5559 	if (n && r == Z_BUF_ERROR) r = Z_OK;
5560 
5561 	/* update counters */
5562 	z->avail_out -= n;
5563 	z->total_out += n;
5564 
5565 	/* update check information */
5566 	if (s->checkfn != Z_NULL)
5567 		z->adler = s->check = (*s->checkfn)(s->check, q, n);
5568 
5569 	/* copy as far as end of window */
5570 	if (p != Z_NULL) {	/* PPP */
5571 		zmemcpy(p, q, n);
5572 		p += n;
5573 	}	/* PPP */
5574 	q += n;
5575 
5576 	/* see if more to copy at beginning of window */
5577 	if (q == s->end)
5578 	{
5579 		/* wrap pointers */
5580 		q = s->window;
5581 		if (s->write == s->end)
5582 			s->write = s->window;
5583 
5584 		/* compute bytes to copy */
5585 		n = (uInt)(s->write - q);
5586 		if (n > z->avail_out) n = z->avail_out;
5587 		if (n && r == Z_BUF_ERROR) r = Z_OK;
5588 
5589 		/* update counters */
5590 		z->avail_out -= n;
5591 		z->total_out += n;
5592 
5593 		/* update check information */
5594 		if (s->checkfn != Z_NULL)
5595 			z->adler = s->check = (*s->checkfn)(s->check, q, n);
5596 
5597 		/* copy */
5598 		if (p != Z_NULL) {	/* PPP */
5599 			zmemcpy(p, q, n);
5600 			p += n;
5601 		}	/* PPP */
5602 		q += n;
5603 	}
5604 
5605 	/* update pointers */
5606 	z->next_out = p;
5607 	s->read = q;
5608 
5609 	/* done */
5610 	return (r);
5611 }
5612 /* --- infutil.c */
5613 
5614 /* +++ inffast.c */
5615 /*
5616  * inffast.c -- process literals and length/distance pairs fast
5617  * Copyright (C) 1995-1998 Mark Adler
5618  * For conditions of distribution and use, see copyright notice in zlib.h
5619  */
5620 
5621 /* #include "zutil.h" */
5622 /* #include "inftrees.h" */
5623 /* #include "infblock.h" */
5624 /* #include "infcodes.h" */
5625 /* #include "infutil.h" */
5626 /* #include "inffast.h" */
5627 
5628 #ifndef NO_DUMMY_DECL
5629 struct inflate_codes_state {int dummy; };	/* for buggy compilers */
5630 #endif
5631 
5632 /* simplify the use of the inflate_huft type with some defines */
5633 #define	exop word.what.Exop
5634 #define	bits word.what.Bits
5635 
5636 /* macros for bit input with no checking and for returning unused bytes */
5637 #define	GRABBITS(j) { while (k < (j)) {b |= ((uLong)NEXTBYTE)<<k; k += 8; }}
5638 #define	UNGRAB {c = z->avail_in-n; c = (k>>3) < c?k>>3:c; n += c; p -= c; \
5639 	k -= c<<3; }
5640 
5641 /*
5642  * Called with number of bytes left to write in window at least 258
5643  * (the maximum string length) and number of input bytes available at
5644  * least ten.  The ten bytes are six bytes for the longest length/
5645  * distance pair plus four bytes for overloading the bit buffer.
5646  */
5647 
5648 int
5649 inflate_fast(bl, bd, tl, td, s, z)
5650 uInt bl, bd;
5651 const inflate_huft *tl;
5652 const inflate_huft *td;	/* need separate declaration for Borland C++ */
5653 inflate_blocks_statef *s;
5654 z_streamp z;
5655 {
5656 	const inflate_huft *t;	/* temporary pointer */
5657 	uInt e;	/* extra bits or operation */
5658 	uLong b;	/* bit buffer */
5659 	uInt k;	/* bits in bit buffer */
5660 	Bytef *p;	/* input data pointer */
5661 	uInt n;	/* bytes available there */
5662 	Bytef *q;	/* output window write pointer */
5663 	uInt m;	/* bytes to end of window or read pointer */
5664 	uInt ml;	/* mask for literal/length tree */
5665 	uInt md;	/* mask for distance tree */
5666 	uInt c;	/* bytes to copy */
5667 	uInt d;	/* distance back to copy from */
5668 	Bytef *r;	/* copy source pointer */
5669 
5670 	/* load input, output, bit values */
5671 	LOAD;
5672 
5673 	/* initialize masks */
5674 	ml = inflate_mask[bl];
5675 	md = inflate_mask[bd];
5676 
5677 	/* do until not enough input or output space for fast loop */
5678 	do {	/* assume called with m >= 258 && n >= 10 */
5679 		/* get literal/length code */
5680 		/* max bits for literal/length code */
5681 		GRABBITS(20);
5682 		if ((e = (t = tl + ((uInt)b & ml))->exop) == 0) {
5683 			DUMPBITS(t->bits);
5684 			Tracevv((stderr, t->base >= 0x20 && t->base < 0x7f ?
5685 			    "inflate:         * literal '%c'\n" :
5686 			    "inflate:         * literal 0x%02x\n", t->base));
5687 			*q++ = (Byte)t->base;
5688 			m--;
5689 			continue;
5690 		}
5691 		do {
5692 			DUMPBITS(t->bits);
5693 			if (e & 16) {
5694 				/* get extra bits for length */
5695 				e &= 15;
5696 				c = t->base + ((uInt)b & inflate_mask[e]);
5697 				DUMPBITS(e);
5698 				Tracevv((stderr,
5699 				    "inflate:         * length %u\n", c));
5700 
5701 				/* decode distance base of block to copy */
5702 				GRABBITS(15);	/* max bits for distance code */
5703 				e = (t = td + ((uInt)b & md))->exop;
5704 				do {
5705 					DUMPBITS(t->bits);
5706 					if (e & 16) {
5707 						/*
5708 						 * get extra bits to
5709 						 * add to distance
5710 						 * base
5711 						 */
5712 						e &= 15;
5713 						/* get extra bits (up to 13) */
5714 						GRABBITS(e);
5715 						d = t->base + ((uInt)b &
5716 						    inflate_mask[e]);
5717 						DUMPBITS(e);
5718 						Tracevv((stderr,
5719 						    "inflate:         * "
5720 						    "distance %u\n", d));
5721 
5722 						/* do the copy */
5723 						m -= c;
5724 						/* offset before dest */
5725 						if ((uInt)(q - s->window) >= d)
5726 							/*  just copy */
5727 						{
5728 							r = q - d;
5729 							/*
5730 							 * minimum
5731 							 * count is
5732 							 * three, so
5733 							 * unroll loop
5734 							 * a little
5735 							 */
5736 							*q++ = *r++;  c--;
5737 							*q++ = *r++;  c--;
5738 						}
5739 					/* else offset after destination */
5740 						else {
5741 	/* bytes from offset to end */
5742 							e = d - (uInt)(q -
5743 							    s->window);
5744 	/* pointer to offset */
5745 							r = s->end - e;
5746 							/* if source crosses */
5747 							if (c > e) {
5748 	/* copy to end of window */
5749 								c -= e;
5750 								do {
5751 									*q++ =
5752 									    *r
5753 									    ++;
5754 								} while (--e);
5755 	/* copy rest from start of window */
5756 								r = s->window;
5757 							}
5758 						}
5759 						/* copy all or what's left */
5760 						do {
5761 							*q++ = *r++;
5762 						} while (--c);
5763 						break;
5764 					} else if ((e & 64) == 0) {
5765 						t += t->base;
5766 						e = (t += ((uInt)b &
5767 						    inflate_mask[e]))->exop;
5768 					} else {
5769 						z->msg =
5770 						    "invalid distance code";
5771 						UNGRAB;
5772 						UPDATE;
5773 						return (Z_DATA_ERROR);
5774 					}
5775 					/* CONSTCOND */
5776 				} while (1);
5777 				break;
5778 			}
5779 			if ((e & 64) == 0)
5780 			{
5781 				t += t->base;
5782 				if ((e = (t += ((uInt)b &
5783 				    inflate_mask[e]))->exop) == 0)
5784 				{
5785 					DUMPBITS(t->bits);
5786 					Tracevv((stderr, t->base >= 0x20 &&
5787 					    t->base < 0x7f ?
5788 					    "inflate:         * literal '%c'\n"
5789 					    :
5790 					    "inflate:         * literal "
5791 					    "0x%02x\n", t->base));
5792 					*q++ = (Byte)t->base;
5793 					m--;
5794 					break;
5795 				}
5796 			} else if (e & 32) {
5797 				Tracevv((stderr,
5798 				    "inflate:         * end of block\n"));
5799 				UNGRAB;
5800 				UPDATE;
5801 				return (Z_STREAM_END);
5802 			} else {
5803 				z->msg = "invalid literal/length code";
5804 				UNGRAB;
5805 				UPDATE;
5806 				return (Z_DATA_ERROR);
5807 			}
5808 			/* CONSTCOND */
5809 		} while (1);
5810 	} while (m >= 258 && n >= 10);
5811 
5812 	/* not enough input or output--restore pointers and return */
5813 	UNGRAB;
5814 	UPDATE;
5815 	return (Z_OK);
5816 }
5817 /* --- inffast.c */
5818 
5819 /* +++ zutil.c */
5820 /*
5821  * zutil.c -- target dependent utility functions for the compression library
5822  * Copyright (C) 1995-1998 Jean-loup Gailly.
5823  * For conditions of distribution and use, see copyright notice in zlib.h
5824  */
5825 
5826 /* From: zutil.c,v 1.17 1996/07/24 13:41:12 me Exp $ */
5827 
5828 #ifdef DEBUG_ZLIB
5829 #include <stdio.h>
5830 #endif
5831 
5832 /* #include "zutil.h" */
5833 
5834 #ifndef NO_DUMMY_DECL
5835 struct internal_state	{int dummy; };	/* for buggy compilers */
5836 #endif
5837 
5838 #ifndef STDC
5839 extern void exit OF((int));
5840 #endif
5841 
5842 static const char *z_errmsg[10] = {
5843 "need dictionary",	/* Z_NEED_DICT		2 */
5844 "stream end",		/* Z_STREAM_END		1 */
5845 "",			/* Z_OK			0 */
5846 "file error",		/* Z_ERRNO		(-1) */
5847 "stream error",		/* Z_STREAM_ERROR	(-2) */
5848 "data error",		/* Z_DATA_ERROR		(-3) */
5849 "insufficient memory",	/* Z_MEM_ERROR		(-4) */
5850 "buffer error",		/* Z_BUF_ERROR		(-5) */
5851 "incompatible version",	/* Z_VERSION_ERROR	(-6) */
5852 ""};
5853 
5854 
5855 const char *
5856 zlibVersion()
5857 {
5858 	return (ZLIB_VERSION);
5859 }
5860 
5861 #ifdef DEBUG_ZLIB
5862 void
5863 z_error(m)
5864     char *m;
5865 {
5866 	fprintf(stderr, "%s\n", m);
5867 	exit(1);
5868 }
5869 #endif
5870 
5871 #ifndef HAVE_MEMCPY
5872 
5873 void
5874 zmemcpy(dest, source, len)
5875     Bytef* dest;
5876     const Bytef* source;
5877     uInt  len;
5878 {
5879 	if (len == 0)
5880 		return;
5881 	do {
5882 		*dest++ = *source++;	/* ??? to be unrolled */
5883 	} while (--len != 0);
5884 }
5885 
5886 int
5887 zmemcmp(s1, s2, len)
5888 const Bytef* s1;
5889 const Bytef* s2;
5890 uInt  len;
5891 {
5892 	uInt j;
5893 
5894 	for (j = 0; j < len; j++) {
5895 		if (s1[j] != s2[j])
5896 			return (2*(s1[j] > s2[j])-1);
5897 	}
5898 	return (0);
5899 }
5900 
5901 void
5902 zmemzero(dest, len)
5903     Bytef* dest;
5904     uInt  len;
5905 {
5906 	if (len == 0)
5907 		return;
5908 	do {
5909 		*dest++ = 0;	/* ??? to be unrolled */
5910 	} while (--len != 0);
5911 }
5912 #endif
5913 
5914 #ifdef __TURBOC__
5915 #if (defined(__BORLANDC__) || !defined(SMALL_MEDIUM)) && !defined(__32BIT__)
5916 /*
5917  * Small and medium model in Turbo C are for now limited to near
5918  * allocation with reduced MAX_WBITS and MAX_MEM_LEVEL
5919  */
5920 #define	MY_ZCALLOC
5921 
5922 /*
5923  * Turbo C malloc() does not allow dynamic allocation of 64K bytes and
5924  * farmalloc(64K) returns a pointer with an offset of 8, so we must
5925  * fix the pointer. Warning: the pointer must be put back to its
5926  * original form in order to free it, use zcfree().
5927  */
5928 
5929 #define	MAX_PTR 10
5930 /* 10*64K = 640K */
5931 
5932 local int next_ptr = 0;
5933 
5934 typedef struct ptr_table_s {
5935 	voidpf org_ptr;
5936 	voidpf new_ptr;
5937 } ptr_table;
5938 
5939 local ptr_table table[MAX_PTR];
5940 /*
5941  * This table is used to remember the original form of pointers to
5942  * large buffers (64K). Such pointers are normalized with a zero
5943  * offset.  Since MSDOS is not a preemptive multitasking OS, this
5944  * table is not protected from concurrent access. This hack doesn't
5945  * work anyway on a protected system like OS/2. Use Microsoft C
5946  * instead.
5947  */
5948 
5949 voidpf
5950 zcalloc(voidpf opaque, unsigned items, unsigned size)
5951 {
5952 	voidpf buf = opaque;	/* just to make some compilers happy */
5953 	ulg bsize = (ulg)items*size;
5954 
5955 	/*
5956 	 * If we allocate less than 65520 bytes, we assume that
5957 	 * farmalloc will return a usable pointer which doesn't have
5958 	 * to be normalized.
5959 	 */
5960 	if (bsize < 65520L) {
5961 		buf = farmalloc(bsize);
5962 		if (*(ush *)&buf != 0)
5963 			return (buf);
5964 	} else {
5965 		buf = farmalloc(bsize + 16L);
5966 	}
5967 	if (buf == NULL || next_ptr >= MAX_PTR)
5968 		return (NULL);
5969 	table[next_ptr].org_ptr = buf;
5970 
5971 	/* Normalize the pointer to seg:0 */
5972 	*((ush *)&buf+1) += ((ush)((uch *)buf-0) + 15) >> 4;
5973 	*(ush *)&buf = 0;
5974 	table[next_ptr++].new_ptr = buf;
5975 	return (buf);
5976 }
5977 
5978 void
5979 zcfree(voidpf opaque, voidpf ptr)
5980 {
5981 	int n;
5982 	if (*(ush*)&ptr != 0) { /* object < 64K */
5983 		farfree(ptr);
5984 		return;
5985 	}
5986 	/* Find the original pointer */
5987 	for (n = 0; n < next_ptr; n++) {
5988 		if (ptr != table[n].new_ptr)
5989 			continue;
5990 
5991 		farfree(table[n].org_ptr);
5992 		while (++n < next_ptr) {
5993 			table[n-1] = table[n];
5994 		}
5995 		next_ptr--;
5996 		return;
5997 	}
5998 	ptr = opaque;	/* just to make some compilers happy */
5999 	Assert(0, "zcfree: ptr not found");
6000 }
6001 #endif
6002 #endif /* __TURBOC__ */
6003 
6004 
6005 #if defined(M_I86) && !defined(__32BIT__)
6006 /* Microsoft C in 16-bit mode */
6007 
6008 #define	MY_ZCALLOC
6009 
6010 #if (!defined(_MSC_VER) || (_MSC_VER <= 600))
6011 #define	_halloc  halloc
6012 #define	_hfree   hfree
6013 #endif
6014 
6015 voidpf
6016 zcalloc(voidpf opaque, unsigned items, unsigned size)
6017 {
6018 	if (opaque) opaque = 0;	/* to make compiler happy */
6019 	return (_halloc((long)items, size));
6020 }
6021 
6022 void
6023 zcfree(voidpf opaque, voidpf ptr)
6024 {
6025 	if (opaque) opaque = 0;	/* to make compiler happy */
6026 	_hfree(ptr);
6027 }
6028 
6029 #endif /* MSC */
6030 
6031 
6032 #ifndef MY_ZCALLOC /* Any system without a special alloc function */
6033 
6034 #ifndef STDC
6035 extern voidp  calloc OF((uInt items, uInt size));
6036 extern void   free   OF((voidpf ptr));
6037 #endif
6038 
6039 voidpf
6040 zcalloc(opaque, items, size)
6041     voidpf opaque;
6042     unsigned items;
6043     unsigned size;
6044 {
6045 	if (opaque) items += size - size;	/* make compiler happy */
6046 	return ((voidpf)calloc(items, size));
6047 }
6048 
6049 /*ARGSUSED*/
6050 void
6051 zcfree(opaque, ptr)
6052     voidpf opaque;
6053     voidpf ptr;
6054 {
6055 	free(ptr);
6056 }
6057 
6058 #endif /* MY_ZCALLOC */
6059 /* --- zutil.c */
6060 
6061 /* +++ adler32.c */
6062 /*
6063  * adler32.c -- compute the Adler-32 checksum of a data stream
6064  * Copyright (C) 1995-1998 Mark Adler
6065  * For conditions of distribution and use, see copyright notice in zlib.h
6066  */
6067 
6068 /* From: adler32.c,v 1.10 1996/05/22 11:52:18 me Exp $ */
6069 
6070 /* #include "zlib.h" */
6071 
6072 #define	BASE 65521L /* largest prime smaller than 65536 */
6073 #define	NMAX 5552
6074 /* NMAX is the largest n such that 255n(n+1)/2 + (n+1)(BASE-1) <= 2^32-1 */
6075 
6076 #define	DO1(buf, i)  {s1 += buf[i]; s2 += s1; }
6077 #define	DO2(buf, i)  DO1(buf, i); DO1(buf, i+1);
6078 #define	DO4(buf, i)  DO2(buf, i); DO2(buf, i+2);
6079 #define	DO8(buf, i)  DO4(buf, i); DO4(buf, i+4);
6080 #define	DO16(buf)   DO8(buf, 0); DO8(buf, 8);
6081 
6082 /* ========================================================================= */
6083 uLong
6084 adler32(adler, buf, len)
6085     uLong adler;
6086     const Bytef *buf;
6087     uInt len;
6088 {
6089 	unsigned long s1 = adler & 0xffff;
6090 	unsigned long s2 = (adler >> 16) & 0xffff;
6091 	int k;
6092 
6093 	if (buf == Z_NULL)
6094 		return (1L);
6095 
6096 	while (len > 0) {
6097 		k = len < NMAX ? len : NMAX;
6098 		len -= k;
6099 		while (k >= 16) {
6100 			DO16(buf);
6101 			buf += 16;
6102 			k -= 16;
6103 		}
6104 		if (k != 0) do {
6105 			s1 += *buf++;
6106 			s2 += s1;
6107 		} while (--k);
6108 		s1 %= BASE;
6109 		s2 %= BASE;
6110 	}
6111 	return ((s2 << 16) | s1);
6112 }
6113 /* --- adler32.c */
6114