17c478bdstevel@tonic-gate/*
2c9431faahl * Copyright 2007 Sun Microsystems, Inc.  All rights reserved.
37c478bdstevel@tonic-gate * Use is subject to license terms.
47c478bdstevel@tonic-gate */
57c478bdstevel@tonic-gate
67c478bdstevel@tonic-gate/*
77c478bdstevel@tonic-gate * Updated from zlib-1.0.4 to zlib-1.1.3 by James Carlson.
87c478bdstevel@tonic-gate *
97c478bdstevel@tonic-gate * This file is derived from various .h and .c files from the zlib-1.0.4
107c478bdstevel@tonic-gate * distribution by Jean-loup Gailly and Mark Adler, with some additions
117c478bdstevel@tonic-gate * by Paul Mackerras to aid in implementing Deflate compression and
127c478bdstevel@tonic-gate * decompression for PPP packets.  See zlib.h for conditions of
137c478bdstevel@tonic-gate * distribution and use.
147c478bdstevel@tonic-gate *
157c478bdstevel@tonic-gate * Changes that have been made include:
167c478bdstevel@tonic-gate * - added Z_PACKET_FLUSH (see zlib.h for details)
177c478bdstevel@tonic-gate * - added inflateIncomp and deflateOutputPending
187c478bdstevel@tonic-gate * - allow strm->next_out to be NULL, meaning discard the output
197c478bdstevel@tonic-gate *
207c478bdstevel@tonic-gate * $Id: zlib.c,v 1.11 1998/09/13 23:37:12 paulus Exp $
217c478bdstevel@tonic-gate */
227c478bdstevel@tonic-gate
237c478bdstevel@tonic-gate#pragma ident	"%Z%%M%	%I%	%E% SMI"
247c478bdstevel@tonic-gate
257c478bdstevel@tonic-gate/*
267c478bdstevel@tonic-gate *  ==FILEVERSION 971210==
277c478bdstevel@tonic-gate *
287c478bdstevel@tonic-gate * This marker is used by the Linux installation script to determine
297c478bdstevel@tonic-gate * whether an up-to-date version of this file is already installed.
307c478bdstevel@tonic-gate */
317c478bdstevel@tonic-gate
327c478bdstevel@tonic-gate#define	NO_DUMMY_DECL
337c478bdstevel@tonic-gate#define	NO_ZCFUNCS
347c478bdstevel@tonic-gate#define	MY_ZCALLOC
357c478bdstevel@tonic-gate
367c478bdstevel@tonic-gate#if defined(__FreeBSD__) && (defined(KERNEL) || defined(_KERNEL))
377c478bdstevel@tonic-gate#define	inflate	inflate_ppp	/* FreeBSD already has an inflate :-( */
387c478bdstevel@tonic-gate#endif
397c478bdstevel@tonic-gate
407c478bdstevel@tonic-gate
417c478bdstevel@tonic-gate/* +++ zutil.h */
427c478bdstevel@tonic-gate/*
437c478bdstevel@tonic-gate *
447c478bdstevel@tonic-gate * zutil.h -- internal interface and configuration of the compression library
457c478bdstevel@tonic-gate * Copyright (C) 1995-1998 Jean-loup Gailly.
467c478bdstevel@tonic-gate * For conditions of distribution and use, see copyright notice in zlib.h
477c478bdstevel@tonic-gate */
487c478bdstevel@tonic-gate
497c478bdstevel@tonic-gate/*
507c478bdstevel@tonic-gate * WARNING: this file should *not* be used by applications. It is part
517c478bdstevel@tonic-gate * of the implementation of the compression library and is subject to
527c478bdstevel@tonic-gate * change. Applications should only use zlib.h.
537c478bdstevel@tonic-gate */
547c478bdstevel@tonic-gate
557c478bdstevel@tonic-gate/* From: zutil.h,v 1.16 1996/07/24 13:41:13 me Exp $ */
567c478bdstevel@tonic-gate
577c478bdstevel@tonic-gate#ifndef _Z_UTIL_H
587c478bdstevel@tonic-gate#define	_Z_UTIL_H
597c478bdstevel@tonic-gate
607c478bdstevel@tonic-gate#include "zlib.h"
617c478bdstevel@tonic-gate
627c478bdstevel@tonic-gate#if defined(KERNEL) || defined(_KERNEL)
637c478bdstevel@tonic-gate/* Assume this is a *BSD or SVR4 kernel */
647c478bdstevel@tonic-gate#include <sys/types.h>
657c478bdstevel@tonic-gate#include <sys/time.h>
667c478bdstevel@tonic-gate#include <sys/systm.h>
677c478bdstevel@tonic-gate#ifdef SOL2
687c478bdstevel@tonic-gate#include <sys/cmn_err.h>
697c478bdstevel@tonic-gate#endif
707c478bdstevel@tonic-gate#define	HAVE_MEMCPY
717c478bdstevel@tonic-gate#define	memcmp		bcmp
727c478bdstevel@tonic-gate
737c478bdstevel@tonic-gate#else
747c478bdstevel@tonic-gate#if defined(__KERNEL__)
757c478bdstevel@tonic-gate/* Assume this is a Linux kernel */
767c478bdstevel@tonic-gate#include <linux/string.h>
777c478bdstevel@tonic-gate#define	HAVE_MEMCPY
787c478bdstevel@tonic-gate
797c478bdstevel@tonic-gate#else /* not kernel */
807c478bdstevel@tonic-gate
817c478bdstevel@tonic-gate#include <stddef.h>
827c478bdstevel@tonic-gate#ifdef NO_ERRNO_H
837c478bdstevel@tonic-gateextern int errno;
847c478bdstevel@tonic-gate#else
857c478bdstevel@tonic-gate#include <errno.h>
867c478bdstevel@tonic-gate#endif
877c478bdstevel@tonic-gate#ifdef STDC
887c478bdstevel@tonic-gate#include <string.h>
897c478bdstevel@tonic-gate#include <stdlib.h>
907c478bdstevel@tonic-gate#endif
917c478bdstevel@tonic-gate#endif /* __KERNEL__ */
927c478bdstevel@tonic-gate#endif /* _KERNEL || KERNEL */
937c478bdstevel@tonic-gate
947c478bdstevel@tonic-gate#ifndef local
957c478bdstevel@tonic-gate#define	local static
967c478bdstevel@tonic-gate#endif
977c478bdstevel@tonic-gate/* compile with -Dlocal if your debugger can't find static symbols */
987c478bdstevel@tonic-gate
997c478bdstevel@tonic-gatetypedef unsigned char  uch;
1007c478bdstevel@tonic-gatetypedef uch FAR uchf;
1017c478bdstevel@tonic-gatetypedef unsigned short ush;
1027c478bdstevel@tonic-gatetypedef ush FAR ushf;
1037c478bdstevel@tonic-gatetypedef unsigned long  ulg;
1047c478bdstevel@tonic-gate
105c9431faahlstatic const char *z_errmsg[10]; /* indexed by 2-zlib_error */
1067c478bdstevel@tonic-gate/* (size given to avoid silly warnings with Visual C++) */
1077c478bdstevel@tonic-gate
1087c478bdstevel@tonic-gate#define	ERR_MSG(err) z_errmsg[Z_NEED_DICT-(err)]
1097c478bdstevel@tonic-gate
1107c478bdstevel@tonic-gate#define	ERR_RETURN(strm, err) \
1117c478bdstevel@tonic-gate	return (strm->msg = ERR_MSG(err), (err))
1127c478bdstevel@tonic-gate/* To be used only when the state is known to be valid */
1137c478bdstevel@tonic-gate
1147c478bdstevel@tonic-gate	/* common constants */
1157c478bdstevel@tonic-gate
1167c478bdstevel@tonic-gate#ifndef DEF_WBITS
1177c478bdstevel@tonic-gate#define	DEF_WBITS MAX_WBITS
1187c478bdstevel@tonic-gate#endif
1197c478bdstevel@tonic-gate/* default windowBits for decompression. MAX_WBITS is for compression only */
1207c478bdstevel@tonic-gate
1217c478bdstevel@tonic-gate#if MAX_MEM_LEVEL >= 8
1227c478bdstevel@tonic-gate#define	DEF_MEM_LEVEL 8
1237c478bdstevel@tonic-gate#else
1247c478bdstevel@tonic-gate#define	DEF_MEM_LEVEL  MAX_MEM_LEVEL
1257c478bdstevel@tonic-gate#endif
1267c478bdstevel@tonic-gate/* default memLevel */
1277c478bdstevel@tonic-gate
1287c478bdstevel@tonic-gate#define	STORED_BLOCK 0
1297c478bdstevel@tonic-gate#define	STATIC_TREES 1
1307c478bdstevel@tonic-gate#define	DYN_TREES    2
1317c478bdstevel@tonic-gate/* The three kinds of block type */
1327c478bdstevel@tonic-gate
1337c478bdstevel@tonic-gate#define	MIN_MATCH  3
1347c478bdstevel@tonic-gate#define	MAX_MATCH  258
1357c478bdstevel@tonic-gate/* The minimum and maximum match lengths */
1367c478bdstevel@tonic-gate
1377c478bdstevel@tonic-gate#define	PRESET_DICT 0x20 /* preset dictionary flag in zlib header */
1387c478bdstevel@tonic-gate
1397c478bdstevel@tonic-gate	/* target dependencies */
1407c478bdstevel@tonic-gate
1417c478bdstevel@tonic-gate#ifdef MSDOS
1427c478bdstevel@tonic-gate#define	OS_CODE  0x00
1437c478bdstevel@tonic-gate#ifdef __TURBOC__
1447c478bdstevel@tonic-gate#include <alloc.h>
1457c478bdstevel@tonic-gate#else /* MSC or DJGPP */
1467c478bdstevel@tonic-gate#include <malloc.h>
1477c478bdstevel@tonic-gate#endif
1487c478bdstevel@tonic-gate#endif
1497c478bdstevel@tonic-gate
1507c478bdstevel@tonic-gate#ifdef OS2
1517c478bdstevel@tonic-gate#define	OS_CODE  0x06
1527c478bdstevel@tonic-gate#endif
1537c478bdstevel@tonic-gate
1547c478bdstevel@tonic-gate#ifdef WIN32 /* Window 95 & Windows NT */
1557c478bdstevel@tonic-gate#define	OS_CODE  0x0b
1567c478bdstevel@tonic-gate#endif
1577c478bdstevel@tonic-gate
1587c478bdstevel@tonic-gate#if defined(VAXC) || defined(VMS)
1597c478bdstevel@tonic-gate#define	OS_CODE  0x02
1607c478bdstevel@tonic-gate#define	F_OPEN(name, mode) \
1617c478bdstevel@tonic-gate	fopen((name), (mode), "mbc=60", "ctx=stm", "rfm=fix", "mrs=512")
1627c478bdstevel@tonic-gate#endif
1637c478bdstevel@tonic-gate
1647c478bdstevel@tonic-gate#ifdef AMIGA
1657c478bdstevel@tonic-gate#define	OS_CODE  0x01
1667c478bdstevel@tonic-gate#endif
1677c478bdstevel@tonic-gate
1687c478bdstevel@tonic-gate#if defined(ATARI) || defined(atarist)
1697c478bdstevel@tonic-gate#define	OS_CODE  0x05
1707c478bdstevel@tonic-gate#endif
1717c478bdstevel@tonic-gate
1727c478bdstevel@tonic-gate#ifdef MACOS
1737c478bdstevel@tonic-gate#define	OS_CODE  0x07
1747c478bdstevel@tonic-gate#endif
1757c478bdstevel@tonic-gate
1767c478bdstevel@tonic-gate#ifdef __50SERIES /* Prime/PRIMOS */
1777c478bdstevel@tonic-gate#define	OS_CODE  0x0F
1787c478bdstevel@tonic-gate#endif
1797c478bdstevel@tonic-gate
1807c478bdstevel@tonic-gate#ifdef TOPS20
1817c478bdstevel@tonic-gate#define	OS_CODE  0x0a
1827c478bdstevel@tonic-gate#endif
1837c478bdstevel@tonic-gate
1847c478bdstevel@tonic-gate#if defined(_BEOS_) || defined(RISCOS)
1857c478bdstevel@tonic-gate#define	fdopen(fd, mode) NULL /* No fdopen() */
1867c478bdstevel@tonic-gate#endif
1877c478bdstevel@tonic-gate
1887c478bdstevel@tonic-gate	/* Common defaults */
1897c478bdstevel@tonic-gate
1907c478bdstevel@tonic-gate#ifndef OS_CODE
1917c478bdstevel@tonic-gate#define	OS_CODE  0x03  /* assume Unix */
1927c478bdstevel@tonic-gate#endif
1937c478bdstevel@tonic-gate
1947c478bdstevel@tonic-gate#ifndef F_OPEN
1957c478bdstevel@tonic-gate#define	F_OPEN(name, mode) fopen((name), (mode))
1967c478bdstevel@tonic-gate#endif
1977c478bdstevel@tonic-gate
1987c478bdstevel@tonic-gate	/* functions */
1997c478bdstevel@tonic-gate
2007c478bdstevel@tonic-gate#ifdef HAVE_STRERROR
2017c478bdstevel@tonic-gateextern char *strerror OF((int));
2027c478bdstevel@tonic-gate#define	zstrerror(errnum) strerror(errnum)
2037c478bdstevel@tonic-gate#else
2047c478bdstevel@tonic-gate#define	zstrerror(errnum) ""
2057c478bdstevel@tonic-gate#endif
2067c478bdstevel@tonic-gate
2077c478bdstevel@tonic-gate#if defined(pyr)
2087c478bdstevel@tonic-gate#define	NO_MEMCPY
2097c478bdstevel@tonic-gate#endif
2107c478bdstevel@tonic-gate#if (defined(M_I86SM) || defined(M_I86MM)) && !defined(_MSC_VER)
2117c478bdstevel@tonic-gate/*
2127c478bdstevel@tonic-gate * Use our own functions for small and medium model with MSC <= 5.0.
2137c478bdstevel@tonic-gate * You may have to use the same strategy for Borland C (untested).
2147c478bdstevel@tonic-gate */
2157c478bdstevel@tonic-gate#define	NO_MEMCPY
2167c478bdstevel@tonic-gate#endif
2177c478bdstevel@tonic-gate#if defined(STDC) && !defined(HAVE_MEMCPY) && !defined(NO_MEMCPY)
2187c478bdstevel@tonic-gate#define	HAVE_MEMCPY
2197c478bdstevel@tonic-gate#endif
2207c478bdstevel@tonic-gate#ifdef HAVE_MEMCPY
2217c478bdstevel@tonic-gate#ifdef SMALL_MEDIUM /* MSDOS small or medium model */
2227c478bdstevel@tonic-gate#define	zmemcpy _fmemcpy
2237c478bdstevel@tonic-gate#define	zmemcmp _fmemcmp
2247c478bdstevel@tonic-gate#define	zmemzero(dest, len) _fmemset(dest, 0, len)
2257c478bdstevel@tonic-gate#else
2267c478bdstevel@tonic-gate#define	zmemcpy (void) memcpy
2277c478bdstevel@tonic-gate#define	zmemcmp memcmp
2287c478bdstevel@tonic-gate#define	zmemzero(dest, len) (void) memset(dest, 0, len)
2297c478bdstevel@tonic-gate#endif
2307c478bdstevel@tonic-gate#else
2317c478bdstevel@tonic-gateextern void zmemcpy  OF((Bytef* dest, const Bytef* source, uInt len));
2327c478bdstevel@tonic-gateextern int  zmemcmp  OF((const Bytef* s1, const Bytef* s2, uInt len));
2337c478bdstevel@tonic-gateextern void zmemzero OF((Bytef* dest, uInt len));
2347c478bdstevel@tonic-gate#endif
2357c478bdstevel@tonic-gate
2367c478bdstevel@tonic-gate/* Diagnostic functions */
2377c478bdstevel@tonic-gate#ifdef DEBUG_ZLIB
2387c478bdstevel@tonic-gate#include <stdio.h>
2397c478bdstevel@tonic-gate#ifndef verbose
2407c478bdstevel@tonic-gate#define	verbose 0
2417c478bdstevel@tonic-gate#endif
2427c478bdstevel@tonic-gateextern void z_error    OF((char *m));
2437c478bdstevel@tonic-gate#define	Assert(cond, msg) { if (!(cond)) z_error(msg); }
2447c478bdstevel@tonic-gate#define	Trace(x) {if (z_verbose >= 0) fprintf x; }
2457c478bdstevel@tonic-gate#define	Tracev(x) {if (z_verbose > 0) fprintf x; }
2467c478bdstevel@tonic-gate#define	Tracevv(x) {if (z_verbose > 1) fprintf x; }
2477c478bdstevel@tonic-gate#define	Tracec(c, x) {if (z_verbose > 0 && (c)) fprintf x; }
2487c478bdstevel@tonic-gate#define	Tracecv(c, x) {if (z_verbose > 1 && (c)) fprintf x; }
2497c478bdstevel@tonic-gate#else
2507c478bdstevel@tonic-gate#if defined(SOL2) && defined(DEBUG)
2517c478bdstevel@tonic-gate#define	Assert(cond, msg)	((cond) ? ((void)0) : panic(msg))
2527c478bdstevel@tonic-gate#else
2537c478bdstevel@tonic-gate#define	Assert(cond, msg)	((void)0)
2547c478bdstevel@tonic-gate#endif
2557c478bdstevel@tonic-gate#define	Trace(x)	((void)0)
2567c478bdstevel@tonic-gate#define	Tracev(x)	((void)0)
2577c478bdstevel@tonic-gate#define	Tracevv(x)	((void)0)
2587c478bdstevel@tonic-gate#define	Tracec(c, x)	((void)0)
2597c478bdstevel@tonic-gate#define	Tracecv(c, x)	((void)0)
2607c478bdstevel@tonic-gate#endif
2617c478bdstevel@tonic-gate
2627c478bdstevel@tonic-gate
2637c478bdstevel@tonic-gatetypedef uLong (*check_func) OF((uLong check, const Bytef *buf, uInt len));
2647c478bdstevel@tonic-gate
2657c478bdstevel@tonic-gate/* voidpf zcalloc OF((voidpf opaque, unsigned items, unsigned size)); */
2667c478bdstevel@tonic-gate/* void   zcfree  OF((voidpf opaque, voidpf ptr)); */
2677c478bdstevel@tonic-gate
2687c478bdstevel@tonic-gate#define	ZALLOC(strm, items, size) \
2697c478bdstevel@tonic-gate	(*((strm)->zalloc))((strm)->opaque, (items), (size))
2707c478bdstevel@tonic-gate#define	ZFREE(strm, addr)  (*((strm)->zfree))((strm)->opaque, (voidpf)(addr))
2717c478bdstevel@tonic-gate#define	TRY_FREE(s, p) {if (p) ZFREE(s, p); }
2727c478bdstevel@tonic-gate
2737c478bdstevel@tonic-gate#endif /* _Z_UTIL_H */
2747c478bdstevel@tonic-gate/* --- zutil.h */
2757c478bdstevel@tonic-gate
2767c478bdstevel@tonic-gate/* +++ deflate.h */
2777c478bdstevel@tonic-gate/*
2787c478bdstevel@tonic-gate * deflate.h -- internal compression state
2797c478bdstevel@tonic-gate * Copyright (C) 1995-1998 Jean-loup Gailly
2807c478bdstevel@tonic-gate * For conditions of distribution and use, see copyright notice in zlib.h
2817c478bdstevel@tonic-gate */
2827c478bdstevel@tonic-gate
2837c478bdstevel@tonic-gate/*
2847c478bdstevel@tonic-gate * WARNING: this file should *not* be used by applications. It is part
2857c478bdstevel@tonic-gate * of the implementation of the compression library and is subject to
2867c478bdstevel@tonic-gate * change. Applications should only use zlib.h.
2877c478bdstevel@tonic-gate */
2887c478bdstevel@tonic-gate
2897c478bdstevel@tonic-gate/* From: deflate.h,v 1.10 1996/07/02 12:41:00 me Exp $ */
2907c478bdstevel@tonic-gate
2917c478bdstevel@tonic-gate#ifndef _DEFLATE_H
2927c478bdstevel@tonic-gate#define	_DEFLATE_H
2937c478bdstevel@tonic-gate
2947c478bdstevel@tonic-gate/* #include "zutil.h" */
2957c478bdstevel@tonic-gate
2967c478bdstevel@tonic-gate/*
2977c478bdstevel@tonic-gate * ===========================================================================
2987c478bdstevel@tonic-gate * Internal compression state.
2997c478bdstevel@tonic-gate */
3007c478bdstevel@tonic-gate
3017c478bdstevel@tonic-gate#define	LENGTH_CODES 29
3027c478bdstevel@tonic-gate/* number of length codes, not counting the special END_BLOCK code */
3037c478bdstevel@tonic-gate
3047c478bdstevel@tonic-gate#define	LITERALS  256
3057c478bdstevel@tonic-gate/* number of literal bytes 0..255 */
3067c478bdstevel@tonic-gate
3077c478bdstevel@tonic-gate#define	L_CODES (LITERALS+1+LENGTH_CODES)
3087c478bdstevel@tonic-gate/* number of Literal or Length codes, including the END_BLOCK code */
3097c478bdstevel@tonic-gate
3107c478bdstevel@tonic-gate#define	D_CODES   30
3117c478bdstevel@tonic-gate/* number of distance codes */
3127c478bdstevel@tonic-gate
3137c478bdstevel@tonic-gate#define	BL_CODES  19
3147c478bdstevel@tonic-gate/* number of codes used to transfer the bit lengths */
3157c478bdstevel@tonic-gate
3167c478bdstevel@tonic-gate#define	HEAP_SIZE (2*L_CODES+1)
3177c478bdstevel@tonic-gate/* maximum heap size */
3187c478bdstevel@tonic-gate
3197c478bdstevel@tonic-gate#define	MAX_BITS 15
3207c478bdstevel@tonic-gate/* All codes must not exceed MAX_BITS bits */
3217c478bdstevel@tonic-gate
3227c478bdstevel@tonic-gate#define	INIT_STATE    42
3237c478bdstevel@tonic-gate#define	BUSY_STATE   113
3247c478bdstevel@tonic-gate#define	FINISH_STATE 666
3257c478bdstevel@tonic-gate/* Stream status */
3267c478bdstevel@tonic-gate
3277c478bdstevel@tonic-gate
3287c478bdstevel@tonic-gate/* Data structure describing a single value and its code string. */
3297c478bdstevel@tonic-gatetypedef struct ct_data_s {
3307c478bdstevel@tonic-gate	union {
3317c478bdstevel@tonic-gate		ush freq;	/* frequency count */
3327c478bdstevel@tonic-gate		ush code;	/* bit string */
3337c478bdstevel@tonic-gate	} fc;
3347c478bdstevel@tonic-gate	union {
3357c478bdstevel@tonic-gate		ush dad;	/* father node in Huffman tree */
3367c478bdstevel@tonic-gate		ush len;	/* length of bit string */
3377c478bdstevel@tonic-gate	} dl;
3387c478bdstevel@tonic-gate} FAR ct_data;
3397c478bdstevel@tonic-gate
3407c478bdstevel@tonic-gate#define	Freq fc.freq
3417c478bdstevel@tonic-gate#define	Code fc.code
3427c478bdstevel@tonic-gate#define	Dad  dl.dad
3437c478bdstevel@tonic-gate#define	Len  dl.len
3447c478bdstevel@tonic-gate
3457c478bdstevel@tonic-gatetypedef struct static_tree_desc_s  static_tree_desc;
3467c478bdstevel@tonic-gate
3477c478bdstevel@tonic-gatetypedef struct tree_desc_s {
3487c478bdstevel@tonic-gate	ct_data *dyn_tree;	/* the dynamic tree */
3497c478bdstevel@tonic-gate	int	max_code;	/* largest code with non zero frequency */
3507c478bdstevel@tonic-gate	static_tree_desc *stat_desc;	/* the corresponding static tree */
3517c478bdstevel@tonic-gate} FAR tree_desc;
3527c478bdstevel@tonic-gate
3537c478bdstevel@tonic-gatetypedef ush Pos;
3547c478bdstevel@tonic-gatetypedef Pos FAR Posf;
3557c478bdstevel@tonic-gatetypedef unsigned IPos;
3567c478bdstevel@tonic-gate
3577c478bdstevel@tonic-gate/*
3587c478bdstevel@tonic-gate * A Pos is an index in the character window. We use short instead of
3597c478bdstevel@tonic-gate * int to save space in the various tables. IPos is used only for
3607c478bdstevel@tonic-gate * parameter passing.
3617c478bdstevel@tonic-gate */
3627c478bdstevel@tonic-gate
3637c478bdstevel@tonic-gatetypedef struct deflate_state {
3647c478bdstevel@tonic-gate	z_streamp strm;	/* pointer back to this zlib stream */
3657c478bdstevel@tonic-gate	int   status;	/* as the name implies */
3667c478bdstevel@tonic-gate	Bytef *pending_buf;	/* output still pending */
3677c478bdstevel@tonic-gate	ulg   pending_buf_size;	/* size of pending_buf */
3687c478bdstevel@tonic-gate	Bytef *pending_out;	/* next pending byte to output to the stream */
3697c478bdstevel@tonic-gate	int   pending;	/* nb of bytes in the pending buffer */
3707c478bdstevel@tonic-gate	int   noheader;	/* suppress zlib header and adler32 */
3717c478bdstevel@tonic-gate	Byte  data_type;	/* UNKNOWN, BINARY or ASCII */
3727c478bdstevel@tonic-gate	Byte  method;	/* STORED (for zip only) or DEFLATED */
3737c478bdstevel@tonic-gate	/* value of flush param for previous deflate call */
3747c478bdstevel@tonic-gate	int   last_flush;
3757c478bdstevel@tonic-gate
3767c478bdstevel@tonic-gate	/* used by deflate.c: */
3777c478bdstevel@tonic-gate
3787c478bdstevel@tonic-gate	uInt  w_size;	/* LZ77 window size (32K by default) */
3797c478bdstevel@tonic-gate	uInt  w_bits;	/* log2(w_size)  (8..16) */
3807c478bdstevel@tonic-gate	uInt  w_mask;	/* w_size - 1 */
3817c478bdstevel@tonic-gate
3827c478bdstevel@tonic-gate	Bytef *window;
3837c478bdstevel@tonic-gate	/*
3847c478bdstevel@tonic-gate	 * Sliding window. Input bytes are read into the second half
3857c478bdstevel@tonic-gate	 * of the window, and move to the first half later to keep a
3867c478bdstevel@tonic-gate	 * dictionary of at least wSize bytes. With this organization,
3877c478bdstevel@tonic-gate	 * matches are limited to a distance of wSize-MAX_MATCH bytes,
3887c478bdstevel@tonic-gate	 * but this ensures that IO is always performed with a length
3897c478bdstevel@tonic-gate	 * multiple of the block size. Also, it limits the window size
3907c478bdstevel@tonic-gate	 * to 64K, which is quite useful on MSDOS.  To do: use the
3917c478bdstevel@tonic-gate	 * user input buffer as sliding window.
3927c478bdstevel@tonic-gate	 */
3937c478bdstevel@tonic-gate
3947c478bdstevel@tonic-gate	ulg window_size;
3957c478bdstevel@tonic-gate	/*
3967c478bdstevel@tonic-gate	 * Actual size of window: 2*wSize, except when the user input
3977c478bdstevel@tonic-gate	 * buffer is directly used as sliding window.
3987c478bdstevel@tonic-gate	 */
3997c478bdstevel@tonic-gate
4007c478bdstevel@tonic-gate	Posf *prev;
4017c478bdstevel@tonic-gate	/*
4027c478bdstevel@tonic-gate	 * Link to older string with same hash index. To limit the
4037c478bdstevel@tonic-gate	 * size of this array to 64K, this link is maintained only for
4047c478bdstevel@tonic-gate	 * the last 32K strings.  An index in this array is thus a
4057c478bdstevel@tonic-gate	 * window index modulo 32K.
4067c478bdstevel@tonic-gate	 */
4077c478bdstevel@tonic-gate
4087c478bdstevel@tonic-gate	Posf *head;	/* Heads of the hash chains or NIL. */
4097c478bdstevel@tonic-gate
4107c478bdstevel@tonic-gate	uInt  ins_h;	/* hash index of string to be inserted */
4117c478bdstevel@tonic-gate	uInt  hash_size;	/* number of elements in hash table */
4127c478bdstevel@tonic-gate	uInt  hash_bits;	/* log2(hash_size) */
4137c478bdstevel@tonic-gate	uInt  hash_mask;	/* hash_size-1 */
4147c478bdstevel@tonic-gate
4157c478bdstevel@tonic-gate	uInt  hash_shift;
4167c478bdstevel@tonic-gate	/*
4177c478bdstevel@tonic-gate	 * Number of bits by which ins_h must be shifted at each input
4187c478bdstevel@tonic-gate	 * step. It must be such that after MIN_MATCH steps, the
4197c478bdstevel@tonic-gate	 * oldest byte no longer takes part in the hash key, that is:
4207c478bdstevel@tonic-gate	 * hash_shift * MIN_MATCH >= hash_bits
4217c478bdstevel@tonic-gate	 */
4227c478bdstevel@tonic-gate
4237c478bdstevel@tonic-gate	long block_start;
4247c478bdstevel@tonic-gate	/*
4257c478bdstevel@tonic-gate	 * Window position at the beginning of the current output
4267c478bdstevel@tonic-gate	 * block. Gets negative when the window is moved backwards.
4277c478bdstevel@tonic-gate	 */
4287c478bdstevel@tonic-gate
4297c478bdstevel@tonic-gate	uInt match_length;	/* length of best match */
4307c478bdstevel@tonic-gate	IPos prev_match;	/* previous match */
4317c478bdstevel@tonic-gate	int match_available;	/* set if previous match exists */
4327c478bdstevel@tonic-gate	uInt strstart;	/* start of string to insert */
4337c478bdstevel@tonic-gate	uInt match_start;	/* start of matching string */
4347c478bdstevel@tonic-gate	uInt lookahead;	/* number of valid bytes ahead in window */
4357c478bdstevel@tonic-gate
4367c478bdstevel@tonic-gate	uInt prev_length;
4377c478bdstevel@tonic-gate	/*
4387c478bdstevel@tonic-gate	 * Length of the best match at previous step. Matches not
4397c478bdstevel@tonic-gate	 * greater than this are discarded. This is used in the lazy
4407c478bdstevel@tonic-gate	 * match evaluation.
4417c478bdstevel@tonic-gate	 */
4427c478bdstevel@tonic-gate
4437c478bdstevel@tonic-gate	uInt max_chain_length;
4447c478bdstevel@tonic-gate	/*
4457c478bdstevel@tonic-gate	 * To speed up deflation, hash chains are never searched
4467c478bdstevel@tonic-gate	 * beyond *this length.  A higher limit improves compression
4477c478bdstevel@tonic-gate	 * ratio but *degrades the speed.
4487c478bdstevel@tonic-gate	 */
4497c478bdstevel@tonic-gate
4507c478bdstevel@tonic-gate	uInt max_lazy_match;
4517c478bdstevel@tonic-gate	/*
4527c478bdstevel@tonic-gate	 * Attempt to find a better match only when the current match
4537c478bdstevel@tonic-gate	 * is strictly smaller than this value. This mechanism is used
4547c478bdstevel@tonic-gate	 * only for compression levels >= 4.
4557c478bdstevel@tonic-gate	 */
4567c478bdstevel@tonic-gate#define	max_insert_length  max_lazy_match
4577c478bdstevel@tonic-gate	/*
4587c478bdstevel@tonic-gate	 * Insert new strings in the hash table only if the match
4597c478bdstevel@tonic-gate	 * length is not greater than this length. This saves time but
4607c478bdstevel@tonic-gate	 * degrades compression.  max_insert_length is used only for
4617c478bdstevel@tonic-gate	 * compression levels <= 3.
4627c478bdstevel@tonic-gate	 */
4637c478bdstevel@tonic-gate
4647c478bdstevel@tonic-gate	int level;	/* compression level (1..9) */
4657c478bdstevel@tonic-gate	int strategy;	/* favor or force Huffman coding */
4667c478bdstevel@tonic-gate
4677c478bdstevel@tonic-gate	uInt good_match;
4687c478bdstevel@tonic-gate	/* Use a faster search when the previous match is longer than this */
4697c478bdstevel@tonic-gate
4707c478bdstevel@tonic-gate	int nice_match;	/* Stop searching when current match exceeds this */
4717c478bdstevel@tonic-gate
4727c478bdstevel@tonic-gate	/* used by trees.c: */
4737c478bdstevel@tonic-gate	/* Didn't use ct_data typedef below to supress compiler warning */
4747c478bdstevel@tonic-gate	struct ct_data_s dyn_ltree[HEAP_SIZE];	/* literal and length tree */
4757c478bdstevel@tonic-gate	struct ct_data_s dyn_dtree[2*D_CODES+1];	/* distance tree */
4767c478bdstevel@tonic-gate	/* Huffman tree for bit lengths */
4777c478bdstevel@tonic-gate	struct ct_data_s bl_tree[2*BL_CODES+1];
4787c478bdstevel@tonic-gate
4797c478bdstevel@tonic-gate	struct tree_desc_s l_desc;	/* desc. for literal tree */
4807c478bdstevel@tonic-gate	struct tree_desc_s d_desc;	/* desc. for distance tree */
4817c478bdstevel@tonic-gate	struct tree_desc_s bl_desc;	/* desc. for bit length tree */
4827c478bdstevel@tonic-gate
4837c478bdstevel@tonic-gate	ush bl_count[MAX_BITS+1];
4847c478bdstevel@tonic-gate	/* number of codes at each bit length for an optimal tree */
4857c478bdstevel@tonic-gate
4867c478bdstevel@tonic-gate	int heap[2*L_CODES+1];	/* heap used to build the Huffman trees */
4877c478bdstevel@tonic-gate	int heap_len;	/* number of elements in the heap */
4887c478bdstevel@tonic-gate	int heap_max;	/* element of largest frequency */
4897c478bdstevel@tonic-gate	/*
4907c478bdstevel@tonic-gate	 * The sons of heap[n] are heap[2*n] and heap[2*n+1]. heap[0]
4917c478bdstevel@tonic-gate	 * is not used.  The same heap array is used to build all
4927c478bdstevel@tonic-gate	 * trees.
4937c478bdstevel@tonic-gate	 */
4947c478bdstevel@tonic-gate
4957c478bdstevel@tonic-gate	uch depth[2*L_CODES+1];
4967c478bdstevel@tonic-gate	/*
4977c478bdstevel@tonic-gate	 * Depth of each subtree used as tie breaker for trees of
4987c478bdstevel@tonic-gate	 * equal frequency
4997c478bdstevel@tonic-gate	 */
5007c478bdstevel@tonic-gate
5017c478bdstevel@tonic-gate	uchf *l_buf;	/* buffer for literals or lengths */
5027c478bdstevel@tonic-gate
5037c478bdstevel@tonic-gate	uInt lit_bufsize;
5047c478bdstevel@tonic-gate	/*
5057c478bdstevel@tonic-gate	 * Size of match buffer for literals/lengths.  There are 4
5067c478bdstevel@tonic-gate	 * reasons for limiting lit_bufsize to 64K:
5077c478bdstevel@tonic-gate	 *
5087c478bdstevel@tonic-gate	 *   - frequencies can be kept in 16 bit counters
5097c478bdstevel@tonic-gate	 *
5107c478bdstevel@tonic-gate	 *   - if compression is not successful for the first block,
5117c478bdstevel@tonic-gate	 *   all input data is still in the window so we can still
5127c478bdstevel@tonic-gate	 *   emit a stored block even when input comes from standard
5137c478bdstevel@tonic-gate	 *   input.  (This can also be done for all blocks if
5147c478bdstevel@tonic-gate	 *   lit_bufsize is not greater than 32K.)
5157c478bdstevel@tonic-gate	 *
5167c478bdstevel@tonic-gate	 *   - if compression is not successful for a file smaller
5177c478bdstevel@tonic-gate	 *   than 64K, we can even emit a stored file instead of a
5187c478bdstevel@tonic-gate	 *   stored block (saving 5 bytes).  This is applicable only
5197c478bdstevel@tonic-gate	 *   for zip (not gzip or zlib).
5207c478bdstevel@tonic-gate	 *
5217c478bdstevel@tonic-gate	 *   - creating new Huffman trees less frequently may not
5227c478bdstevel@tonic-gate	 *   provide fast adaptation to changes in the input data
5237c478bdstevel@tonic-gate	 *   statistics. (Take for example a binary file with poorly
5247c478bdstevel@tonic-gate	 *   compressible code followed by a highly compressible
5257c478bdstevel@tonic-gate	 *   string table.) Smaller buffer sizes give fast adaptation
5267c478bdstevel@tonic-gate	 *   but have of course the overhead of transmitting trees
5277c478bdstevel@tonic-gate	 *   more frequently.
5287c478bdstevel@tonic-gate	 *
5297c478bdstevel@tonic-gate	 *   - I can't count above 4
5307c478bdstevel@tonic-gate	 */
5317c478bdstevel@tonic-gate
5327c478bdstevel@tonic-gate	uInt last_lit;	/* running index in l_buf */
5337c478bdstevel@tonic-gate
5347c478bdstevel@tonic-gate	ushf *d_buf;
5357c478bdstevel@tonic-gate	/*
5367c478bdstevel@tonic-gate	 * Buffer for distances. To simplify the code, d_buf and l_buf
5377c478bdstevel@tonic-gate	 * have the same number of elements. To use different lengths,
5387c478bdstevel@tonic-gate	 * an extra flag array would be necessary.
5397c478bdstevel@tonic-gate	 */
5407c478bdstevel@tonic-gate
5417c478bdstevel@tonic-gate	ulg opt_len;	/* bit length of current block with optimal trees */
5427c478bdstevel@tonic-gate	ulg static_len;	/* bit length of current block with static trees */
5437c478bdstevel@tonic-gate	uInt matches;	/* number of string matches in current block */
5447c478bdstevel@tonic-gate	int last_eob_len;	/* bit length of EOB code for last block */
5457c478bdstevel@tonic-gate
5467c478bdstevel@tonic-gate	ulg compressed_len;	/* total bit length of compressed file PPP */
5477c478bdstevel@tonic-gate#ifdef DEBUG_ZLIB
5487c478bdstevel@tonic-gate	ulg bits_sent;	/* bit length of the compressed data */
5497c478bdstevel@tonic-gate#endif
5507c478bdstevel@tonic-gate
5517c478bdstevel@tonic-gate	ush bi_buf;
5527c478bdstevel@tonic-gate	/*
5537c478bdstevel@tonic-gate	 * Output buffer. bits are inserted starting at the bottom
5547c478bdstevel@tonic-gate	 * (least significant bits).
5557c478bdstevel@tonic-gate	 */
5567c478bdstevel@tonic-gate	int bi_valid;
5577c478bdstevel@tonic-gate	/*
5587c478bdstevel@tonic-gate	 * Number of valid bits in bi_buf.  All bits above the last
5597c478bdstevel@tonic-gate	 * valid bit are always zero.
5607c478bdstevel@tonic-gate	 */
5617c478bdstevel@tonic-gate
5627c478bdstevel@tonic-gate} FAR deflate_state;
5637c478bdstevel@tonic-gate
5647c478bdstevel@tonic-gate/*
5657c478bdstevel@tonic-gate * Output a byte on the stream.  IN assertion: there is enough room in
5667c478bdstevel@tonic-gate * pending_buf.
5677c478bdstevel@tonic-gate */
5687c478bdstevel@tonic-gate#define	put_byte(s, c) {s->pending_buf[s->pending++] = (c); }
5697c478bdstevel@tonic-gate
5707c478bdstevel@tonic-gate
5717c478bdstevel@tonic-gate#define	MIN_LOOKAHEAD (MAX_MATCH+MIN_MATCH+1)
5727c478bdstevel@tonic-gate/*
5737c478bdstevel@tonic-gate * Minimum amount of lookahead, except at the end of the input file.
5747c478bdstevel@tonic-gate * See deflate.c for comments about the MIN_MATCH+1.
5757c478bdstevel@tonic-gate */
5767c478bdstevel@tonic-gate
5777c478bdstevel@tonic-gate#define	MAX_DIST(s)  ((s)->w_size-MIN_LOOKAHEAD)
5787c478bdstevel@tonic-gate/*
5797c478bdstevel@tonic-gate * In order to simplify the code, particularly on 16 bit machines,
5807c478bdstevel@tonic-gate * match distances are limited to MAX_DIST instead of WSIZE.
5817c478bdstevel@tonic-gate */
5827c478bdstevel@tonic-gate
5837c478bdstevel@tonic-gate	/* in trees.c */
5847c478bdstevel@tonic-gatevoid _tr_init		OF((deflate_state *s));
5857c478bdstevel@tonic-gateint  _tr_tally		OF((deflate_state *s, unsigned dist, unsigned lc));
5867c478bdstevel@tonic-gatevoid  _tr_flush_block	OF((deflate_state *s, charf *buf, ulg stored_len,
5877c478bdstevel@tonic-gate    int eof));
5887c478bdstevel@tonic-gatevoid _tr_align		OF((deflate_state *s));
5897c478bdstevel@tonic-gatevoid _tr_stored_block	OF((deflate_state *s, charf *buf, ulg stored_len,
5907c478bdstevel@tonic-gate    int eof));
5917c478bdstevel@tonic-gatevoid _tr_stored_type_only OF((deflate_state *));	/* PPP */
5927c478bdstevel@tonic-gate
5937c478bdstevel@tonic-gate#define	d_code(dist) \
5947c478bdstevel@tonic-gate	((dist) < 256 ? _dist_code[dist] : _dist_code[256+((dist)>>7)])
5957c478bdstevel@tonic-gate/*
5967c478bdstevel@tonic-gate * Mapping from a distance to a distance code. dist is the distance - 1 and
5977c478bdstevel@tonic-gate * must not have side effects. _dist_code[256] and _dist_code[257] are never
5987c478bdstevel@tonic-gate * used.
5997c478bdstevel@tonic-gate */
6007c478bdstevel@tonic-gate
6017c478bdstevel@tonic-gate#ifndef DEBUG_ZLIB
6027c478bdstevel@tonic-gate/* Inline versions of _tr_tally for speed: */
6037c478bdstevel@tonic-gate
6047c478bdstevel@tonic-gatelocal uch _length_code[];
6057c478bdstevel@tonic-gatelocal uch _dist_code[];
6067c478bdstevel@tonic-gate
6077c478bdstevel@tonic-gate#define	_tr_tally_lit(s, c, flush) \
6087c478bdstevel@tonic-gate	{	uch cc = (c); \
6097c478bdstevel@tonic-gate		s->d_buf[s->last_lit] = 0; \
6107c478bdstevel@tonic-gate		s->l_buf[s->last_lit++] = cc; \
6117c478bdstevel@tonic-gate		s->dyn_ltree[cc].Freq++; \
6127c478bdstevel@tonic-gate		flush = (s->last_lit == s->lit_bufsize-1); \
6137c478bdstevel@tonic-gate	}
6147c478bdstevel@tonic-gate#define	_tr_tally_dist(s, distance, length, flush) \
6157c478bdstevel@tonic-gate	{	uch len = (length); \
6167c478bdstevel@tonic-gate		ush dist = (distance); \
6177c478bdstevel@tonic-gate		s->d_buf[s->last_lit] = dist; \
6187c478bdstevel@tonic-gate		s->l_buf[s->last_lit++] = len; \
6197c478bdstevel@tonic-gate		dist--; \
6207c478bdstevel@tonic-gate		s->dyn_ltree[_length_code[len]+LITERALS+1].Freq++; \
6217c478bdstevel@tonic-gate		s->dyn_dtree[d_code(dist)].Freq++; \
6227c478bdstevel@tonic-gate		flush = (s->last_lit == s->lit_bufsize-1); \
6237c478bdstevel@tonic-gate	}
6247c478bdstevel@tonic-gate#else
6257c478bdstevel@tonic-gate#define	_tr_tally_lit(s, c, flush) flush = _tr_tally(s, 0, c)
6267c478bdstevel@tonic-gate#define	_tr_tally_dist(s, distance, length, flush) \
6277c478bdstevel@tonic-gate		flush = _tr_tally(s, distance, length)
6287c478bdstevel@tonic-gate#endif
6297c478bdstevel@tonic-gate
6307c478bdstevel@tonic-gate#endif
6317c478bdstevel@tonic-gate/* --- deflate.h */
6327c478bdstevel@tonic-gate
6337c478bdstevel@tonic-gate/* +++ deflate.c */
6347c478bdstevel@tonic-gate/*
6357c478bdstevel@tonic-gate * deflate.c -- compress data using the deflation algorithm
6367c478bdstevel@tonic-gate * Copyright (C) 1995-1998 Jean-loup Gailly.
6377c478bdstevel@tonic-gate * For conditions of distribution and use, see copyright notice in zlib.h
6387c478bdstevel@tonic-gate */
6397c478bdstevel@tonic-gate
6407c478bdstevel@tonic-gate/*
6417c478bdstevel@tonic-gate *  ALGORITHM
6427c478bdstevel@tonic-gate *
6437c478bdstevel@tonic-gate *      The "deflation" process depends on being able to identify portions
6447c478bdstevel@tonic-gate *      of the input text which are identical to earlier input (within a
6457c478bdstevel@tonic-gate *      sliding window trailing behind the input currently being processed).
6467c478bdstevel@tonic-gate *
6477c478bdstevel@tonic-gate *      The most straightforward technique turns out to be the fastest for
6487c478bdstevel@tonic-gate *      most input files: try all possible matches and select the longest.
6497c478bdstevel@tonic-gate *      The key feature of this algorithm is that insertions into the string
6507c478bdstevel@tonic-gate *      dictionary are very simple and thus fast, and deletions are avoided
6517c478bdstevel@tonic-gate *      completely. Insertions are performed at each input character, whereas
6527c478bdstevel@tonic-gate *      string matches are performed only when the previous match ends. So it
6537c478bdstevel@tonic-gate *      is preferable to spend more time in matches to allow very fast string
6547c478bdstevel@tonic-gate *      insertions and avoid deletions. The matching algorithm for small
6557c478bdstevel@tonic-gate *      strings is inspired from that of Rabin & Karp. A brute force approach
6567c478bdstevel@tonic-gate *      is used to find longer strings when a small match has been found.
6577c478bdstevel@tonic-gate *      A similar algorithm is used in comic (by Jan-Mark Wams) and freeze
6587c478bdstevel@tonic-gate *      (by Leonid Broukhis).
6597c478bdstevel@tonic-gate *         A previous version of this file used a more sophisticated algorithm
6607c478bdstevel@tonic-gate *      (by Fiala and Greene) which is guaranteed to run in linear amortized
6617c478bdstevel@tonic-gate *      time, but has a larger average cost, uses more memory and is patented.
6627c478bdstevel@tonic-gate *      However the F&G algorithm may be faster for some highly redundant
6637c478bdstevel@tonic-gate *      files if the parameter max_chain_length (described below) is too large.
6647c478bdstevel@tonic-gate *
6657c478bdstevel@tonic-gate *  ACKNOWLEDGEMENTS
6667c478bdstevel@tonic-gate *
6677c478bdstevel@tonic-gate *      The idea of lazy evaluation of matches is due to Jan-Mark Wams, and
6687c478bdstevel@tonic-gate *      I found it in 'freeze' written by Leonid Broukhis.
6697c478bdstevel@tonic-gate *      Thanks to many people for bug reports and testing.
6707c478bdstevel@tonic-gate *
6717c478bdstevel@tonic-gate *  REFERENCES
6727c478bdstevel@tonic-gate *
6737c478bdstevel@tonic-gate *      Deutsch, L.P.,"DEFLATE Compressed Data Format Specification".
6747c478bdstevel@tonic-gate *      Available in ftp://ds.internic.net/rfc/rfc1951.txt
6757c478bdstevel@tonic-gate *
6767c478bdstevel@tonic-gate *      A description of the Rabin and Karp algorithm is given in the book
6777c478bdstevel@tonic-gate *         "Algorithms" by R. Sedgewick, Addison-Wesley, p252.
6787c478bdstevel@tonic-gate *
6797c478bdstevel@tonic-gate *      Fiala,E.R., and Greene,D.H.
6807c478bdstevel@tonic-gate *         Data Compression with Finite Windows, Comm.ACM, 32,4 (1989) 490-595
6817c478bdstevel@tonic-gate *
6827c478bdstevel@tonic-gate */
6837c478bdstevel@tonic-gate
6847c478bdstevel@tonic-gate/* From: deflate.c,v 1.15 1996/07/24 13:40:58 me Exp $ */
6857c478bdstevel@tonic-gate
6867c478bdstevel@tonic-gate/* #include "deflate.h" */
6877c478bdstevel@tonic-gate
6887c478bdstevel@tonic-gateconst char deflate_copyright[] =
6897c478bdstevel@tonic-gate" deflate 1.1.3 Copyright 1995-1998 Jean-loup Gailly ";
6907c478bdstevel@tonic-gate/*
6917c478bdstevel@tonic-gate * If you use the zlib library in a product, an acknowledgment is
6927c478bdstevel@tonic-gate * welcome in the documentation of your product. If for some reason
6937c478bdstevel@tonic-gate * you cannot include such an acknowledgment, I would appreciate that
6947c478bdstevel@tonic-gate * you keep this copyright string in the executable of your product.
6957c478bdstevel@tonic-gate */
6967c478bdstevel@tonic-gate
6977c478bdstevel@tonic-gate/*
6987c478bdstevel@tonic-gate * ===========================================================================
6997c478bdstevel@tonic-gate *  Function prototypes.
7007c478bdstevel@tonic-gate */
7017c478bdstevel@tonic-gatetypedef enum {
7027c478bdstevel@tonic-gate	/* block not completed, need more input or more output */
7037c478bdstevel@tonic-gate	need_more,
7047c478bdstevel@tonic-gate	block_done,	/* block flush performed */
7057c478bdstevel@tonic-gate	/* finish started, need only more output at next deflate */
7067c478bdstevel@tonic-gate	finish_started,
7077c478bdstevel@tonic-gate	finish_done	/* finish done, accept no more input or output */
7087c478bdstevel@tonic-gate} block_state;
7097c478bdstevel@tonic-gate
7107c478bdstevel@tonic-gatetypedef block_state (*compress_func) OF((deflate_state *s, int flush));
7117c478bdstevel@tonic-gate/* Compression function. Returns the block state after the call. */
7127c478bdstevel@tonic-gate
7137c478bdstevel@tonic-gatelocal void fill_window	OF((deflate_state *s));
7147c478bdstevel@tonic-gatelocal block_state deflate_stored OF((deflate_state *s, int flush));
7157c478bdstevel@tonic-gatelocal block_state deflate_fast	OF((deflate_state *s, int flush));
7167c478bdstevel@tonic-gatelocal block_state deflate_slow	OF((deflate_state *s, int flush));
7177c478bdstevel@tonic-gatelocal void lm_init	OF((deflate_state *s));
7187c478bdstevel@tonic-gatelocal void putShortMSB	OF((deflate_state *s, uInt b));
7197c478bdstevel@tonic-gatelocal void flush_pending	OF((z_streamp strm));
7207c478bdstevel@tonic-gatelocal int read_buf	OF((z_streamp strm, Bytef *buf, unsigned size));
7217c478bdstevel@tonic-gate#ifdef ASMV
7227c478bdstevel@tonic-gatevoid match_init	OF((void));	/* asm code initialization */
7237c478bdstevel@tonic-gateuInt longest_match	OF((deflate_state *s, IPos cur_match));
7247c478bdstevel@tonic-gate#else
7257c478bdstevel@tonic-gatelocal uInt longest_match	OF((deflate_state *s, IPos cur_match));
7267c478bdstevel@tonic-gate#endif
7277c478bdstevel@tonic-gate
7287c478bdstevel@tonic-gate#ifdef DEBUG_ZLIB
7297c478bdstevel@tonic-gatelocal void check_match OF((deflate_state *s, IPos start, IPos match,
7307c478bdstevel@tonic-gate    int length));
7317c478bdstevel@tonic-gate#endif
7327c478bdstevel@tonic-gate
7337c478bdstevel@tonic-gate/*
7347c478bdstevel@tonic-gate * ===========================================================================
7357c478bdstevel@tonic-gate * Local data
7367c478bdstevel@tonic-gate */
7377c478bdstevel@tonic-gate
7387c478bdstevel@tonic-gate#define	NIL 0
7397c478bdstevel@tonic-gate/* Tail of hash chains */
7407c478bdstevel@tonic-gate
7417c478bdstevel@tonic-gate#ifndef TOO_FAR
7427c478bdstevel@tonic-gate#define	TOO_FAR 4096
7437c478bdstevel@tonic-gate#endif
7447c478bdstevel@tonic-gate/* Matches of length 3 are discarded if their distance exceeds TOO_FAR */
7457c478bdstevel@tonic-gate
7467c478bdstevel@tonic-gate#define	MIN_LOOKAHEAD (MAX_MATCH+MIN_MATCH+1)
7477c478bdstevel@tonic-gate/*
7487c478bdstevel@tonic-gate * Minimum amount of lookahead, except at the end of the input file.
7497c478bdstevel@tonic-gate * See deflate.c for comments about the MIN_MATCH+1.
7507c478bdstevel@tonic-gate */
7517c478bdstevel@tonic-gate
7527c478bdstevel@tonic-gate/*
7537c478bdstevel@tonic-gate * Values for max_lazy_match, good_match and max_chain_length,
7547c478bdstevel@tonic-gate * depending on the desired pack level (0..9). The values given below
7557c478bdstevel@tonic-gate * have been tuned to exclude worst case performance for pathological
7567c478bdstevel@tonic-gate * files. Better values may be found for specific files.
7577c478bdstevel@tonic-gate */
7587c478bdstevel@tonic-gatetypedef struct config_s {
7597c478bdstevel@tonic-gate	ush good_length;	/* reduce lazy search above this match length */
7607c478bdstevel@tonic-gate	ush max_lazy;	/* do not perform lazy search above this match length */
7617c478bdstevel@tonic-gate	ush nice_length;	/* quit search above this match length */
7627c478bdstevel@tonic-gate	ush max_chain;
7637c478bdstevel@tonic-gate	compress_func func;
7647c478bdstevel@tonic-gate} config;
7657c478bdstevel@tonic-gate
7667c478bdstevel@tonic-gatelocal const config configuration_table[10] = {
7677c478bdstevel@tonic-gate/*	good lazy nice chain */
7687c478bdstevel@tonic-gate/* 0 */ {0,    0,  0,    0, deflate_stored},  /* store only */
7697c478bdstevel@tonic-gate/* 1 */ {4,    4,  8,    4, deflate_fast}, /* maximum speed, no lazy matches */
7707c478bdstevel@tonic-gate/* 2 */ {4,    5, 16,    8, deflate_fast},
7717c478bdstevel@tonic-gate/* 3 */ {4,    6, 32,   32, deflate_fast},
7727c478bdstevel@tonic-gate
7737c478bdstevel@tonic-gate/* 4 */ {4,    4, 16,   16, deflate_slow},  /* lazy matches */
7747c478bdstevel@tonic-gate/* 5 */ {8,   16, 32,   32, deflate_slow},
7757c478bdstevel@tonic-gate/* 6 */ {8,   16, 128, 128, deflate_slow},
7767c478bdstevel@tonic-gate/* 7 */ {8,   32, 128, 256, deflate_slow},
7777c478bdstevel@tonic-gate/* 8 */ {32, 128, 258, 1024, deflate_slow},
7787c478bdstevel@tonic-gate/* 9 */ {32, 258, 258, 4096, deflate_slow}};	/* maximum compression */
7797c478bdstevel@tonic-gate
7807c478bdstevel@tonic-gate/*
7817c478bdstevel@tonic-gate * Note: the deflate() code requires max_lazy >= MIN_MATCH and max_chain >= 4
7827c478bdstevel@tonic-gate * For deflate_fast() (levels <= 3) good is ignored and lazy has a different
7837c478bdstevel@tonic-gate * meaning.
7847c478bdstevel@tonic-gate */
7857c478bdstevel@tonic-gate
7867c478bdstevel@tonic-gate#define	EQUAL 0
7877c478bdstevel@tonic-gate/* result of memcmp for equal strings */
7887c478bdstevel@tonic-gate
7897c478bdstevel@tonic-gate#ifndef NO_DUMMY_DECL
7907c478bdstevel@tonic-gatestruct static_tree_desc_s {int dummy; };	/* for buggy compilers */
7917c478bdstevel@tonic-gate#endif
7927c478bdstevel@tonic-gate
7937c478bdstevel@tonic-gate/*
7947c478bdstevel@tonic-gate * ===========================================================================
7957c478bdstevel@tonic-gate * Update a hash value with the given input byte
7967c478bdstevel@tonic-gate * IN  assertion: all calls to to UPDATE_HASH are made with consecutive
7977c478bdstevel@tonic-gate *    input characters, so that a running hash key can be computed from the
7987c478bdstevel@tonic-gate *    previous key instead of complete recalculation each time.
7997c478bdstevel@tonic-gate */
8007c478bdstevel@tonic-gate#define	UPDATE_HASH(s, h, c) (h = (((h)<<s->hash_shift) ^ (c)) & s->hash_mask)
8017c478bdstevel@tonic-gate
8027c478bdstevel@tonic-gate
8037c478bdstevel@tonic-gate/*
8047c478bdstevel@tonic-gate * ===========================================================================
8057c478bdstevel@tonic-gate * Insert string str in the dictionary and set match_head to the previous head
8067c478bdstevel@tonic-gate * of the hash chain (the most recent string with same hash key). Return
8077c478bdstevel@tonic-gate * the previous length of the hash chain.
8087c478bdstevel@tonic-gate * If this file is compiled with -DFASTEST, the compression level is forced
8097c478bdstevel@tonic-gate * to 1, and no hash chains are maintained.
8107c478bdstevel@tonic-gate * IN  assertion: all calls to to INSERT_STRING are made with consecutive
8117c478bdstevel@tonic-gate *    input characters and the first MIN_MATCH bytes of str are valid
8127c478bdstevel@tonic-gate *    (except for the last MIN_MATCH-1 bytes of the input file).
8137c478bdstevel@tonic-gate */
8147c478bdstevel@tonic-gate#ifdef FASTEST
8157c478bdstevel@tonic-gate#define	INSERT_STRING(s, str, match_head) \
8167c478bdstevel@tonic-gate	(UPDATE_HASH(s, s->ins_h, s->window[(str) + (MIN_MATCH-1)]), \
8177c478bdstevel@tonic-gate	match_head = s->head[s->ins_h], \
8187c478bdstevel@tonic-gate	s->head[s->ins_h] = (Pos)(str))
8197c478bdstevel@tonic-gate#else
8207c478bdstevel@tonic-gate#define	INSERT_STRING(s, str, match_head) \
8217c478bdstevel@tonic-gate	(UPDATE_HASH(s, s->ins_h, s->window[(str) + (MIN_MATCH-1)]), \
8227c478bdstevel@tonic-gate	s->prev[(str) & s->w_mask] = match_head = s->head[s->ins_h], \
8237c478bdstevel@tonic-gate	s->head[s->ins_h] = (Pos)(str))
8247c478bdstevel@tonic-gate#endif
8257c478bdstevel@tonic-gate
8267c478bdstevel@tonic-gate/*
8277c478bdstevel@tonic-gate * ===========================================================================
8287c478bdstevel@tonic-gate * Initialize the hash table (avoiding 64K overflow for 16 bit systems).
8297c478bdstevel@tonic-gate * prev[] will be initialized on the fly.
8307c478bdstevel@tonic-gate */
8317c478bdstevel@tonic-gate#define	CLEAR_HASH(s) \
8327c478bdstevel@tonic-gate    s->head[s->hash_size-1] = NIL; \
8337c478bdstevel@tonic-gate    zmemzero((Bytef *)s->head, (unsigned)(s->hash_size-1)*sizeof (*s->head));
8347c478bdstevel@tonic-gate
8357c478bdstevel@tonic-gate/* ========================================================================= */
8367c478bdstevel@tonic-gateint
8377c478bdstevel@tonic-gatedeflateInit_(strm, level, version, stream_size)
8387c478bdstevel@tonic-gate    z_streamp strm;
8397c478bdstevel@tonic-gate    int level;
8407c478bdstevel@tonic-gate    const char *version;
8417c478bdstevel@tonic-gate    int stream_size;
8427c478bdstevel@tonic-gate{
8437c478bdstevel@tonic-gate	(void) deflate_copyright;
8447c478bdstevel@tonic-gate	return deflateInit2_(strm, level, Z_DEFLATED, MAX_WBITS, DEF_MEM_LEVEL,
8457c478bdstevel@tonic-gate	    Z_DEFAULT_STRATEGY, version, stream_size);
8467c478bdstevel@tonic-gate	/* To do: ignore strm->next_in if we use it as window */
8477c478bdstevel@tonic-gate}
8487c478bdstevel@tonic-gate
8497c478bdstevel@tonic-gate/* ========================================================================= */
8507c478bdstevel@tonic-gateint deflateInit2_(strm, level, method, windowBits, memLevel, strategy,
8517c478bdstevel@tonic-gate    version, stream_size)
8527c478bdstevel@tonic-gate    z_streamp strm;
8537c478bdstevel@tonic-gate    int  level;
8547c478bdstevel@tonic-gate    int  method;
8557c478bdstevel@tonic-gate    int  windowBits;
8567c478bdstevel@tonic-gate    int  memLevel;
8577c478bdstevel@tonic-gate    int  strategy;
8587c478bdstevel@tonic-gate    const char *version;
8597c478bdstevel@tonic-gate    int stream_size;
8607c478bdstevel@tonic-gate{
8617c478bdstevel@tonic-gate	deflate_state *s;
8627c478bdstevel@tonic-gate	int noheader = 0;
8637c478bdstevel@tonic-gate	static const char *my_version = ZLIB_VERSION;
8647c478bdstevel@tonic-gate
8657c478bdstevel@tonic-gate	ushf *overlay;
8667c478bdstevel@tonic-gate	/*
8677c478bdstevel@tonic-gate	 * We overlay pending_buf and d_buf+l_buf. This works since
8687c478bdstevel@tonic-gate	 * the average output size for (length, distance) codes is <=
8697c478bdstevel@tonic-gate	 * 24 bits.
8707c478bdstevel@tonic-gate	 */
8717c478bdstevel@tonic-gate
8727c478bdstevel@tonic-gate	if (version == Z_NULL || version[0] != my_version[0] ||
8737c478bdstevel@tonic-gate	    stream_size != sizeof (z_stream)) {
8747c478bdstevel@tonic-gate		return (Z_VERSION_ERROR);
8757c478bdstevel@tonic-gate	}
8767c478bdstevel@tonic-gate	if (strm == Z_NULL)
8777c478bdstevel@tonic-gate		return (Z_STREAM_ERROR);
8787c478bdstevel@tonic-gate
8797c478bdstevel@tonic-gate	strm->msg = Z_NULL;
8807c478bdstevel@tonic-gate#ifndef NO_ZCFUNCS
8817c478bdstevel@tonic-gate	if (strm->zalloc == Z_NULL) {
8827c478bdstevel@tonic-gate		strm->zalloc = zcalloc;
8837c478bdstevel@tonic-gate		strm->opaque = (voidpf)0;
8847c478bdstevel@tonic-gate	}
8857c478bdstevel@tonic-gate	if (strm->zfree == Z_NULL) strm->zfree = zcfree;
8867c478bdstevel@tonic-gate#endif
8877c478bdstevel@tonic-gate
8887c478bdstevel@tonic-gate	if (level == Z_DEFAULT_COMPRESSION) level = 6;
8897c478bdstevel@tonic-gate#ifdef FASTEST
8907c478bdstevel@tonic-gate	level = 1;
8917c478bdstevel@tonic-gate#endif
8927c478bdstevel@tonic-gate
8937c478bdstevel@tonic-gate	if (windowBits < 0) { /* undocumented feature: suppress zlib header */
8947c478bdstevel@tonic-gate		noheader = 1;
8957c478bdstevel@tonic-gate		windowBits = -windowBits;
8967c478bdstevel@tonic-gate	}
8977c478bdstevel@tonic-gate	if (memLevel < 1 || memLevel > MAX_MEM_LEVEL || method != Z_DEFLATED ||
8987c478bdstevel@tonic-gate	    windowBits <= 8 || windowBits > 15 || level < 0 || level > 9 ||
8997c478bdstevel@tonic-gate	    strategy < 0 || strategy > Z_HUFFMAN_ONLY) {
9007c478bdstevel@tonic-gate		return (Z_STREAM_ERROR);
9017c478bdstevel@tonic-gate	}
9027c478bdstevel@tonic-gate	s = (deflate_state *) ZALLOC(strm, 1, sizeof (deflate_state));
9037c478bdstevel@tonic-gate	if (s == Z_NULL)
9047c478bdstevel@tonic-gate		return (Z_MEM_ERROR);
9057c478bdstevel@tonic-gate	strm->state = (struct internal_state FAR *)s;
9067c478bdstevel@tonic-gate	s->strm = strm;
9077c478bdstevel@tonic-gate
9087c478bdstevel@tonic-gate	s->noheader = noheader;
9097c478bdstevel@tonic-gate	s->w_bits = windowBits;
9107c478bdstevel@tonic-gate	s->w_size = 1 << s->w_bits;
9117c478bdstevel@tonic-gate	s->w_mask = s->w_size - 1;
9127c478bdstevel@tonic-gate
9137c478bdstevel@tonic-gate	s->hash_bits = memLevel + 7;
9147c478bdstevel@tonic-gate	s->hash_size = 1 << s->hash_bits;
9157c478bdstevel@tonic-gate	s->hash_mask = s->hash_size - 1;
9167c478bdstevel@tonic-gate	s->hash_shift =  ((s->hash_bits+MIN_MATCH-1)/MIN_MATCH);
9177c478bdstevel@tonic-gate
9187c478bdstevel@tonic-gate	s->window = (Bytef *) ZALLOC(strm, s->w_size, 2*sizeof (Byte));
9197c478bdstevel@tonic-gate	s->prev   = (Posf *)  ZALLOC(strm, s->w_size, sizeof (Pos));
9207c478bdstevel@tonic-gate	s->head   = (Posf *)  ZALLOC(strm, s->hash_size, sizeof (Pos));
9217c478bdstevel@tonic-gate
9227c478bdstevel@tonic-gate	s->lit_bufsize = 1 << (memLevel + 6);	/* 16K elements by default */
9237c478bdstevel@tonic-gate
9247c478bdstevel@tonic-gate	overlay = (ushf *) ZALLOC(strm, s->lit_bufsize, sizeof (ush)+2);
9257c478bdstevel@tonic-gate	s->pending_buf = (uchf *) overlay;
9267c478bdstevel@tonic-gate	s->pending_buf_size = (ulg)s->lit_bufsize * (sizeof (ush)+2L);
9277c478bdstevel@tonic-gate
9287c478bdstevel@tonic-gate	if (s->window == Z_NULL || s->prev == Z_NULL || s->head == Z_NULL ||
9297c478bdstevel@tonic-gate	    s->pending_buf == Z_NULL) {
9307c478bdstevel@tonic-gate		strm->msg = ERR_MSG(Z_MEM_ERROR);
9317c478bdstevel@tonic-gate		s->status = INIT_STATE;
9327c478bdstevel@tonic-gate		(void) deflateEnd(strm);
9337c478bdstevel@tonic-gate		return (Z_MEM_ERROR);
9347c478bdstevel@tonic-gate	}
9357c478bdstevel@tonic-gate	s->d_buf = overlay + s->lit_bufsize/sizeof (ush);
9367c478bdstevel@tonic-gate	s->l_buf = s->pending_buf + (1+sizeof (ush))*s->lit_bufsize;
9377c478bdstevel@tonic-gate
9387c478bdstevel@tonic-gate	s->level = level;
9397c478bdstevel@tonic-gate	s->strategy = strategy;
9407c478bdstevel@tonic-gate	s->method = (Byte)method;
9417c478bdstevel@tonic-gate
9427c478bdstevel@tonic-gate	return (deflateReset(strm));
9437c478bdstevel@tonic-gate}
9447c478bdstevel@tonic-gate
9457c478bdstevel@tonic-gate/* ========================================================================= */
9467c478bdstevel@tonic-gateint
9477c478bdstevel@tonic-gatedeflateSetDictionary(strm, dictionary, dictLength)
9487c478bdstevel@tonic-gate    z_streamp strm;
9497c478bdstevel@tonic-gate    const Bytef *dictionary;
9507c478bdstevel@tonic-gate    uInt  dictLength;
9517c478bdstevel@tonic-gate{
9527c478bdstevel@tonic-gate	deflate_state *s;
9537c478bdstevel@tonic-gate	uInt length = dictLength;
9547c478bdstevel@tonic-gate	uInt n;
9557c478bdstevel@tonic-gate	IPos hash_head = 0;
9567c478bdstevel@tonic-gate
9577c478bdstevel@tonic-gate	if (strm == Z_NULL || strm->state == Z_NULL || dictionary == Z_NULL)
9587c478bdstevel@tonic-gate		return (Z_STREAM_ERROR);
9597c478bdstevel@tonic-gate
9607c478bdstevel@tonic-gate	s = (deflate_state *) strm->state;
9617c478bdstevel@tonic-gate	if (s->status != INIT_STATE)
9627c478bdstevel@tonic-gate		return (Z_STREAM_ERROR);
9637c478bdstevel@tonic-gate
9647c478bdstevel@tonic-gate	strm->adler = adler32(strm->adler, dictionary, dictLength);
9657c478bdstevel@tonic-gate
9667c478bdstevel@tonic-gate	if (length < MIN_MATCH)
9677c478bdstevel@tonic-gate		return (Z_OK);
9687c478bdstevel@tonic-gate	if (length > MAX_DIST(s)) {
9697c478bdstevel@tonic-gate		length = MAX_DIST(s);
9707c478bdstevel@tonic-gate#ifndef USE_DICT_HEAD
9717c478bdstevel@tonic-gate		/* use the tail of the dictionary */
9727c478bdstevel@tonic-gate		dictionary += dictLength - length;
9737c478bdstevel@tonic-gate#endif
9747c478bdstevel@tonic-gate	}
9757c478bdstevel@tonic-gate	Assert(length <= s->window_size, "dict copy");
9767c478bdstevel@tonic-gate	zmemcpy(s->window, dictionary, length);
9777c478bdstevel@tonic-gate	s->strstart = length;
9787c478bdstevel@tonic-gate	s->block_start = (long)length;
9797c478bdstevel@tonic-gate
9807c478bdstevel@tonic-gate	/*
9817c478bdstevel@tonic-gate	 * Insert all strings in the hash table (except for the last
9827c478bdstevel@tonic-gate	 * two bytes).  s->lookahead stays null, so s->ins_h will be
9837c478bdstevel@tonic-gate	 * recomputed at the next call of fill_window.
9847c478bdstevel@tonic-gate	 */
9857c478bdstevel@tonic-gate	s->ins_h = s->window[0];
9867c478bdstevel@tonic-gate	UPDATE_HASH(s, s->ins_h, s->window[1]);
9877c478bdstevel@tonic-gate	for (n = 0; n <= length - MIN_MATCH; n++) {
9887c478bdstevel@tonic-gate		INSERT_STRING(s, n, hash_head);
9897c478bdstevel@tonic-gate	}
9907c478bdstevel@tonic-gate	if (hash_head) hash_head = 0;	/* to make compiler happy */
9917c478bdstevel@tonic-gate	return (Z_OK);
9927c478bdstevel@tonic-gate}
9937c478bdstevel@tonic-gate
9947c478bdstevel@tonic-gate/* ========================================================================= */
9957c478bdstevel@tonic-gateint
9967c478bdstevel@tonic-gatedeflateReset(strm)
9977c478bdstevel@tonic-gate    z_streamp strm;
9987c478bdstevel@tonic-gate{
9997c478bdstevel@tonic-gate	deflate_state *s;
10007c478bdstevel@tonic-gate
10017c478bdstevel@tonic-gate	if (strm == Z_NULL || strm->state == Z_NULL ||
10027c478bdstevel@tonic-gate	    strm->zalloc == Z_NULL || strm->zfree == Z_NULL)
10037c478bdstevel@tonic-gate		return (Z_STREAM_ERROR);
10047c478bdstevel@tonic-gate
10057c478bdstevel@tonic-gate	strm->total_in = strm->total_out = 0;
10067c478bdstevel@tonic-gate	/* use zfree if we ever allocate msg dynamically */
10077c478bdstevel@tonic-gate	strm->msg = Z_NULL;
10087c478bdstevel@tonic-gate	strm->data_type = Z_UNKNOWN;
10097c478bdstevel@tonic-gate
10107c478bdstevel@tonic-gate	s = (deflate_state *)strm->state;
10117c478bdstevel@tonic-gate	s->pending = 0;
10127c478bdstevel@tonic-gate	s->pending_out = s->pending_buf;
10137c478bdstevel@tonic-gate
10147c478bdstevel@tonic-gate	if (s->noheader < 0) {
10157c478bdstevel@tonic-gate		/* was set to -1 by deflate(..., Z_FINISH); */
10167c478bdstevel@tonic-gate		s->noheader = 0;
10177c478bdstevel@tonic-gate	}
10187c478bdstevel@tonic-gate	s->status = s->noheader ? BUSY_STATE : INIT_STATE;
10197c478bdstevel@tonic-gate	strm->adler = 1;
10207c478bdstevel@tonic-gate	s->last_flush = Z_NO_FLUSH;
10217c478bdstevel@tonic-gate
10227c478bdstevel@tonic-gate	_tr_init(s);
10237c478bdstevel@tonic-gate	lm_init(s);
10247c478bdstevel@tonic-gate
10257c478bdstevel@tonic-gate	return (Z_OK);
10267c478bdstevel@tonic-gate}
10277c478bdstevel@tonic-gate
10287c478bdstevel@tonic-gate/* ========================================================================= */
10297c478bdstevel@tonic-gateint
10307c478bdstevel@tonic-gatedeflateParams(strm, level, strategy)
10317c478bdstevel@tonic-gate    z_streamp strm;
10327c478bdstevel@tonic-gate    int level;
10337c478bdstevel@tonic-gate    int strategy;
10347c478bdstevel@tonic-gate{
10357c478bdstevel@tonic-gate	deflate_state *s;
10367c478bdstevel@tonic-gate	compress_func func;
10377c478bdstevel@tonic-gate	int err = Z_OK;
10387c478bdstevel@tonic-gate
10397c478bdstevel@tonic-gate	if (strm == Z_NULL || strm->state == Z_NULL)
10407c478bdstevel@tonic-gate		return (Z_STREAM_ERROR);
10417c478bdstevel@tonic-gate	s = (deflate_state *) strm->state;
10427c478bdstevel@tonic-gate
10437c478bdstevel@tonic-gate	if (level == Z_DEFAULT_COMPRESSION) {
10447c478bdstevel@tonic-gate		level = 6;
10457c478bdstevel@tonic-gate	}
10467c478bdstevel@tonic-gate	if (level < 0 || level > 9 || strategy < 0 ||
10477c478bdstevel@tonic-gate	    strategy > Z_HUFFMAN_ONLY) {
10487c478bdstevel@tonic-gate		return (Z_STREAM_ERROR);
10497c478bdstevel@tonic-gate	}
10507c478bdstevel@tonic-gate	func = configuration_table[s->level].func;
10517c478bdstevel@tonic-gate
10527c478bdstevel@tonic-gate	if (func != configuration_table[level].func && strm->total_in != 0) {
10537c478bdstevel@tonic-gate		/* Flush the last buffer: */
10547c478bdstevel@tonic-gate		err = deflate(strm, Z_PARTIAL_FLUSH);
10557c478bdstevel@tonic-gate	}
10567c478bdstevel@tonic-gate	if (s->level != level) {
10577c478bdstevel@tonic-gate		s->level = level;
10587c478bdstevel@tonic-gate		s->max_lazy_match   = configuration_table[level].max_lazy;
10597c478bdstevel@tonic-gate		s->good_match	= configuration_table[level].good_length;
10607c478bdstevel@tonic-gate		s->nice_match	= configuration_table[level].nice_length;
10617c478bdstevel@tonic-gate		s->max_chain_length = configuration_table[level].max_chain;
10627c478bdstevel@tonic-gate	}
10637c478bdstevel@tonic-gate	s->strategy = strategy;
10647c478bdstevel@tonic-gate	return (err);
10657c478bdstevel@tonic-gate}
10667c478bdstevel@tonic-gate
10677c478bdstevel@tonic-gate/*
10687c478bdstevel@tonic-gate * =========================================================================
10697c478bdstevel@tonic-gate * Put a short in the pending buffer. The 16-bit value is put in MSB order.
10707c478bdstevel@tonic-gate * IN assertion: the stream state is correct and there is enough room in
10717c478bdstevel@tonic-gate * pending_buf.
10727c478bdstevel@tonic-gate */
10737c478bdstevel@tonic-gatelocal void
10747c478bdstevel@tonic-gateputShortMSB(s, b)
10757c478bdstevel@tonic-gate    deflate_state *s;
10767c478bdstevel@tonic-gate    uInt b;
10777c478bdstevel@tonic-gate{
10787c478bdstevel@tonic-gate	put_byte(s, (Byte)(b >> 8));
10797c478bdstevel@tonic-gate	put_byte(s, (Byte)(b & 0xff));
10807c478bdstevel@tonic-gate}
10817c478bdstevel@tonic-gate
10827c478bdstevel@tonic-gate/*
10837c478bdstevel@tonic-gate * =========================================================================
10847c478bdstevel@tonic-gate * Flush as much pending output as possible. All deflate() output goes
10857c478bdstevel@tonic-gate * through this function so some applications may wish to modify it
10867c478bdstevel@tonic-gate * to avoid allocating a large strm->next_out buffer and copying into it.
10877c478bdstevel@tonic-gate * (See also read_buf()).
10887c478bdstevel@tonic-gate */
10897c478bdstevel@tonic-gatelocal void
10907c478bdstevel@tonic-gateflush_pending(strm)
10917c478bdstevel@tonic-gate    z_streamp strm;
10927c478bdstevel@tonic-gate{
10937c478bdstevel@tonic-gate	deflate_state *s = (deflate_state *) strm->state;
10947c478bdstevel@tonic-gate	unsigned len = s->pending;
10957c478bdstevel@tonic-gate
10967c478bdstevel@tonic-gate	if (len > strm->avail_out) len = strm->avail_out;
10977c478bdstevel@tonic-gate	if (len == 0)
10987c478bdstevel@tonic-gate		return;
10997c478bdstevel@tonic-gate
11007c478bdstevel@tonic-gate	if (strm->next_out != Z_NULL) {		/* PPP */
11017c478bdstevel@tonic-gate		zmemcpy(strm->next_out, s->pending_out, len);
11027c478bdstevel@tonic-gate		strm->next_out += len;
11037c478bdstevel@tonic-gate	}					/* PPP */
11047c478bdstevel@tonic-gate	s->pending_out += len;
11057c478bdstevel@tonic-gate	strm->total_out += len;
11067c478bdstevel@tonic-gate	strm->avail_out  -= len;
11077c478bdstevel@tonic-gate	s->pending -= len;
11087c478bdstevel@tonic-gate	if (s->pending == 0) {
11097c478bdstevel@tonic-gate		s->pending_out = s->pending_buf;
11107c478bdstevel@tonic-gate	}
11117c478bdstevel@tonic-gate}
11127c478bdstevel@tonic-gate
11137c478bdstevel@tonic-gate/* ========================================================================= */
11147c478bdstevel@tonic-gateint
11157c478bdstevel@tonic-gatedeflate(strm, flush)
11167c478bdstevel@tonic-gate    z_streamp strm;
11177c478bdstevel@tonic-gate    int flush;
11187c478bdstevel@tonic-gate{
11197c478bdstevel@tonic-gate	int old_flush;	/* value of flush param for previous deflate call */
11207c478bdstevel@tonic-gate	deflate_state *s;
11217c478bdstevel@tonic-gate
11227c478bdstevel@tonic-gate	if (strm == Z_NULL || strm->state == Z_NULL ||
11237c478bdstevel@tonic-gate	    flush > Z_FINISH || flush < 0) {
11247c478bdstevel@tonic-gate		return (Z_STREAM_ERROR);
11257c478bdstevel@tonic-gate	}
11267c478bdstevel@tonic-gate	s = (deflate_state *) strm->state;
11277c478bdstevel@tonic-gate
11287c478bdstevel@tonic-gate	if (/* strm->next_out == Z_NULL || --- we allow null --- PPP */
11297c478bdstevel@tonic-gate		(strm->next_in == Z_NULL && strm->avail_in != 0) ||
11307c478bdstevel@tonic-gate	    (s->status == FINISH_STATE && flush != Z_FINISH)) {
11317c478bdstevel@tonic-gate		ERR_RETURN(strm, Z_STREAM_ERROR);
11327c478bdstevel@tonic-gate	}
11337c478bdstevel@tonic-gate	if (strm->avail_out == 0) ERR_RETURN(strm, Z_BUF_ERROR);
11347c478bdstevel@tonic-gate
11357c478bdstevel@tonic-gate	s->strm = strm;	/* just in case */
11367c478bdstevel@tonic-gate	old_flush = s->last_flush;
11377c478bdstevel@tonic-gate	s->last_flush = flush;
11387c478bdstevel@tonic-gate
11397c478bdstevel@tonic-gate	/* Write the zlib header */
11407c478bdstevel@tonic-gate	if (s->status == INIT_STATE) {
11417c478bdstevel@tonic-gate
11427c478bdstevel@tonic-gate		uInt header = (Z_DEFLATED + ((s->w_bits-8)<<4)) << 8;
11437c478bdstevel@tonic-gate		uInt level_flags = (s->level-1) >> 1;
11447c478bdstevel@tonic-gate
11457c478bdstevel@tonic-gate		if (level_flags > 3) level_flags = 3;
11467c478bdstevel@tonic-gate		header |= (level_flags << 6);
11477c478bdstevel@tonic-gate		if (s->strstart != 0) header |= PRESET_DICT;
11487c478bdstevel@tonic-gate		header += 31 - (header % 31);
11497c478bdstevel@tonic-gate
11507c478bdstevel@tonic-gate		s->status = BUSY_STATE;
11517c478bdstevel@tonic-gate		putShortMSB(s, header);
11527c478bdstevel@tonic-gate
11537c478bdstevel@tonic-gate		/* Save the adler32 of the preset dictionary: */
11547c478bdstevel@tonic-gate		if (s->strstart != 0) {
11557c478bdstevel@tonic-gate			putShortMSB(s, (uInt)(strm->adler >> 16));
11567c478bdstevel@tonic-gate			putShortMSB(s, (uInt)(strm->adler & 0xffff));
11577c478bdstevel@tonic-gate		}
11587c478bdstevel@tonic-gate		strm->adler = 1L;
11597c478bdstevel@tonic-gate	}
11607c478bdstevel@tonic-gate
11617c478bdstevel@tonic-gate	/* Flush as much pending output as possible */
11627c478bdstevel@tonic-gate	if (s->pending != 0) {
11637c478bdstevel@tonic-gate		flush_pending(strm);
11647c478bdstevel@tonic-gate		if (strm->avail_out == 0) {
11657c478bdstevel@tonic-gate			/*
11667c478bdstevel@tonic-gate			 * Since avail_out is 0, deflate will be
11677c478bdstevel@tonic-gate			 * called again with more output space, but
11687c478bdstevel@tonic-gate			 * possibly with both pending and avail_in
11697c478bdstevel@tonic-gate			 * equal to zero. There won't be anything to
11707c478bdstevel@tonic-gate			 * do, but this is not an error situation so
11717c478bdstevel@tonic-gate			 * make sure we return OK instead of BUF_ERROR
11727c478bdstevel@tonic-gate			 * at next call of deflate:
11737c478bdstevel@tonic-gate			 */
11747c478bdstevel@tonic-gate			s->last_flush = -1;
11757c478bdstevel@tonic-gate			return (Z_OK);
11767c478bdstevel@tonic-gate		}
11777c478bdstevel@tonic-gate
11787c478bdstevel@tonic-gate		/*
11797c478bdstevel@tonic-gate		 * Make sure there is something to do and avoid
11807c478bdstevel@tonic-gate		 * duplicate consecutive flushes. For repeated and
11817c478bdstevel@tonic-gate		 * useless calls with Z_FINISH, we keep returning
11827c478bdstevel@tonic-gate		 * Z_STREAM_END instead of Z_BUFF_ERROR.
11837c478bdstevel@tonic-gate		 */
11847c478bdstevel@tonic-gate	} else if (strm->avail_in == 0 && flush <= old_flush &&
11857c478bdstevel@tonic-gate	    flush != Z_FINISH) {
11867c478bdstevel@tonic-gate		ERR_RETURN(strm, Z_BUF_ERROR);
11877c478bdstevel@tonic-gate	}
11887c478bdstevel@tonic-gate
11897c478bdstevel@tonic-gate	/* User must not provide more input after the first FINISH: */
11907c478bdstevel@tonic-gate	if (s->status == FINISH_STATE && strm->avail_in != 0) {
11917c478bdstevel@tonic-gate		ERR_RETURN(strm, Z_BUF_ERROR);
11927c478bdstevel@tonic-gate	}
11937c478bdstevel@tonic-gate
11947c478bdstevel@tonic-gate	/* Start a new block or continue the current one. */
11957c478bdstevel@tonic-gate	if (strm->avail_in != 0 || s->lookahead != 0 ||
11967c478bdstevel@tonic-gate	    (flush != Z_NO_FLUSH && s->status != FINISH_STATE)) {
11977c478bdstevel@tonic-gate		block_state bstate;
11987c478bdstevel@tonic-gate
11997c478bdstevel@tonic-gate		bstate = (*(configuration_table[s->level].func))(s, flush);
12007c478bdstevel@tonic-gate
12017c478bdstevel@tonic-gate		if (bstate == finish_started || bstate == finish_done) {
12027c478bdstevel@tonic-gate			s->status = FINISH_STATE;
12037c478bdstevel@tonic-gate		}
12047c478bdstevel@tonic-gate		if (bstate == need_more || bstate == finish_started) {
12057c478bdstevel@tonic-gate			if (strm->avail_out == 0) {
12067c478bdstevel@tonic-gate				/* avoid BUF_ERROR next call, see above */
12077c478bdstevel@tonic-gate				s->last_flush = -1;
12087c478bdstevel@tonic-gate			}
12097c478bdstevel@tonic-gate			return (Z_OK);
12107c478bdstevel@tonic-gate			/*
12117c478bdstevel@tonic-gate			 * If flush != Z_NO_FLUSH && avail_out == 0,
12127c478bdstevel@tonic-gate			 * the next call of deflate should use the
12137c478bdstevel@tonic-gate			 * same flush parameter to make sure that the
12147c478bdstevel@tonic-gate			 * flush is complete. So we don't have to
12157c478bdstevel@tonic-gate			 * output an empty block here, this will be
12167c478bdstevel@tonic-gate			 * done at next call. This also ensures that
12177c478bdstevel@tonic-gate			 * for a very small output buffer, we emit at
12187c478bdstevel@tonic-gate			 * most one empty block.
12197c478bdstevel@tonic-gate			 */
12207c478bdstevel@tonic-gate		}
12217c478bdstevel@tonic-gate		if (bstate == block_done) {
12227c478bdstevel@tonic-gate			if (flush == Z_PARTIAL_FLUSH) {
12237c478bdstevel@tonic-gate				_tr_align(s);
12247c478bdstevel@tonic-gate			} else if (flush == Z_PACKET_FLUSH) {	/* PPP */
12257c478bdstevel@tonic-gate				/*
12267c478bdstevel@tonic-gate				 * Output just the 3-bit `stored'
12277c478bdstevel@tonic-gate				 * block type value, but not a zero
12287c478bdstevel@tonic-gate				 * length.  Added for PPP.
12297c478bdstevel@tonic-gate				 */
12307c478bdstevel@tonic-gate				_tr_stored_type_only(s);	/* PPP */
12317c478bdstevel@tonic-gate			} else { /* FULL_FLUSH or SYNC_FLUSH */
12327c478bdstevel@tonic-gate				_tr_stored_block(s, (char *)0, 0L, 0);
12337c478bdstevel@tonic-gate				/*
12347c478bdstevel@tonic-gate				 * For a full flush, this empty block
12357c478bdstevel@tonic-gate				 * will be recognized as a special
12367c478bdstevel@tonic-gate				 * marker by inflate_sync().
12377c478bdstevel@tonic-gate				 */
12387c478bdstevel@tonic-gate				if (flush == Z_FULL_FLUSH) {
12397c478bdstevel@tonic-gate					CLEAR_HASH(s);	/* forget history */
12407c478bdstevel@tonic-gate				}
12417c478bdstevel@tonic-gate			}
12427c478bdstevel@tonic-gate			flush_pending(strm);
12437c478bdstevel@tonic-gate			if (strm->avail_out == 0) {
12447c478bdstevel@tonic-gate				/* avoid BUF_ERROR at next call, see above */
12457c478bdstevel@tonic-gate				s->last_flush = -1;
12467c478bdstevel@tonic-gate				return (Z_OK);
12477c478bdstevel@tonic-gate			}
12487c478bdstevel@tonic-gate		}
12497c478bdstevel@tonic-gate	}
12507c478bdstevel@tonic-gate	Assert(strm->avail_out > 0, "bug2");
12517c478bdstevel@tonic-gate
12527c478bdstevel@tonic-gate	if (flush != Z_FINISH)
12537c478bdstevel@tonic-gate		return (Z_OK);
12547c478bdstevel@tonic-gate	if (s->noheader)
12557c478bdstevel@tonic-gate		return (Z_STREAM_END);
12567c478bdstevel@tonic-gate
12577c478bdstevel@tonic-gate	/* Write the zlib trailer (adler32) */
12587c478bdstevel@tonic-gate	putShortMSB(s, (uInt)(strm->adler >> 16));
12597c478bdstevel@tonic-gate	putShortMSB(s, (uInt)(strm->adler & 0xffff));
12607c478bdstevel@tonic-gate	flush_pending(strm);
12617c478bdstevel@tonic-gate	/*
12627c478bdstevel@tonic-gate	 * If avail_out is zero, the application will call deflate
12637c478bdstevel@tonic-gate	 * again to flush the rest.
12647c478bdstevel@tonic-gate	 */
12657c478bdstevel@tonic-gate	s->noheader = -1;	/* write the trailer only once! */
12667c478bdstevel@tonic-gate	return (s->pending != 0 ? Z_OK : Z_STREAM_END);
12677c478bdstevel@tonic-gate}
12687c478bdstevel@tonic-gate
12697c478bdstevel@tonic-gate/* ========================================================================= */
12707c478bdstevel@tonic-gateint
12717c478bdstevel@tonic-gatedeflateEnd(strm)
12727c478bdstevel@tonic-gate    z_streamp strm;
12737c478bdstevel@tonic-gate{
12747c478bdstevel@tonic-gate	int status;
12757c478bdstevel@tonic-gate	deflate_state *s;
12767c478bdstevel@tonic-gate
12777c478bdstevel@tonic-gate	if (strm == Z_NULL || strm->state == Z_NULL)
12787c478bdstevel@tonic-gate		return (Z_STREAM_ERROR);
12797c478bdstevel@tonic-gate	s = (deflate_state *) strm->state;
12807c478bdstevel@tonic-gate
12817c478bdstevel@tonic-gate	status = s->status;
12827c478bdstevel@tonic-gate	if (status != INIT_STATE && status != BUSY_STATE &&
12837c478bdstevel@tonic-gate	    status != FINISH_STATE) {
12847c478bdstevel@tonic-gate		return (Z_STREAM_ERROR);
12857c478bdstevel@tonic-gate	}
12867c478bdstevel@tonic-gate
12877c478bdstevel@tonic-gate	/* Deallocate in reverse order of allocations: */
12887c478bdstevel@tonic-gate	TRY_FREE(strm, s->pending_buf);
12897c478bdstevel@tonic-gate	TRY_FREE(strm, s->head);
12907c478bdstevel@tonic-gate	TRY_FREE(strm, s->prev);
12917c478bdstevel@tonic-gate	TRY_FREE(strm, s->window);
12927c478bdstevel@tonic-gate
12937c478bdstevel@tonic-gate	ZFREE(strm, s);
12947c478bdstevel@tonic-gate	strm->state = Z_NULL;
12957c478bdstevel@tonic-gate
12967c478bdstevel@tonic-gate	return (status == BUSY_STATE ? Z_DATA_ERROR : Z_OK);
12977c478bdstevel@tonic-gate}
12987c478bdstevel@tonic-gate
12997c478bdstevel@tonic-gate/*
13007c478bdstevel@tonic-gate * =========================================================================
13017c478bdstevel@tonic-gate * Copy the source state to the destination state.
13027c478bdstevel@tonic-gate * To simplify the source, this is not supported for 16-bit MSDOS (which
13037c478bdstevel@tonic-gate * doesn't have enough memory anyway to duplicate compression states).
13047c478bdstevel@tonic-gate */
13057c478bdstevel@tonic-gateint
13067c478bdstevel@tonic-gatedeflateCopy(dest, source)
13077c478bdstevel@tonic-gate    z_streamp dest;
13087c478bdstevel@tonic-gate    z_streamp source;
13097c478bdstevel@tonic-gate{
13107c478bdstevel@tonic-gate#ifdef MAXSEG_64K
13117c478bdstevel@tonic-gate	return (Z_STREAM_ERROR);
13127c478bdstevel@tonic-gate#else
13137c478bdstevel@tonic-gate	deflate_state *ds;
13147c478bdstevel@tonic-gate	deflate_state *ss;
13157c478bdstevel@tonic-gate	ushf *overlay;
13167c478bdstevel@tonic-gate
13177c478bdstevel@tonic-gate	if (source == Z_NULL || dest == Z_NULL || source->state == Z_NULL)
13187c478bdstevel@tonic-gate		return (Z_STREAM_ERROR);
13197c478bdstevel@tonic-gate	ss = (deflate_state *) source->state;
13207c478bdstevel@tonic-gate
13217c478bdstevel@tonic-gate	zmemcpy(dest, source, sizeof (*dest));
13227c478bdstevel@tonic-gate
13237c478bdstevel@tonic-gate	ds = (deflate_state *) ZALLOC(dest, 1, sizeof (deflate_state));
13247c478bdstevel@tonic-gate	if (ds == Z_NULL)
13257c478bdstevel@tonic-gate		return (Z_MEM_ERROR);
13267c478bdstevel@tonic-gate	dest->state = (struct internal_state FAR *) ds;
13277c478bdstevel@tonic-gate	zmemcpy(ds, ss, sizeof (*ds));
13287c478bdstevel@tonic-gate	ds->strm = dest;
13297c478bdstevel@tonic-gate
13307c478bdstevel@tonic-gate	ds->window = (Bytef *) ZALLOC(dest, ds->w_size, 2*sizeof (Byte));
13317c478bdstevel@tonic-gate	ds->prev   = (Posf *)  ZALLOC(dest, ds->w_size, sizeof (Pos));
13327c478bdstevel@tonic-gate	ds->head   = (Posf *)  ZALLOC(dest, ds->hash_size, sizeof (Pos));
13337c478bdstevel@tonic-gate	overlay = (ushf *) ZALLOC(dest, ds->lit_bufsize, sizeof (ush)+2);
13347c478bdstevel@tonic-gate	ds->pending_buf = (uchf *) overlay;
13357c478bdstevel@tonic-gate
13367c478bdstevel@tonic-gate	if (ds->window == Z_NULL || ds->prev == Z_NULL || ds->head == Z_NULL ||
13377c478bdstevel@tonic-gate	    ds->pending_buf == Z_NULL) {
13387c478bdstevel@tonic-gate		ds->status = INIT_STATE;
13397c478bdstevel@tonic-gate		(void) deflateEnd(dest);
13407c478bdstevel@tonic-gate		return (Z_MEM_ERROR);
13417c478bdstevel@tonic-gate	}
13427c478bdstevel@tonic-gate	/* following zmemcpy doesn't work for 16-bit MSDOS */
13437c478bdstevel@tonic-gate	zmemcpy(ds->window, ss->window, ds->w_size * 2 * sizeof (Byte));
13447c478bdstevel@tonic-gate	zmemcpy(ds->prev, ss->prev, ds->w_size * sizeof (Pos));
13457c478bdstevel@tonic-gate	zmemcpy(ds->head, ss->head, ds->hash_size * sizeof (Pos));
13467c478bdstevel@tonic-gate	zmemcpy(ds->pending_buf, ss->pending_buf, (uInt)ds->pending_buf_size);
13477c478bdstevel@tonic-gate
13487c478bdstevel@tonic-gate	ds->pending_out = ds->pending_buf + (ss->pending_out - ss->pending_buf);
13497c478bdstevel@tonic-gate	ds->d_buf = overlay + ds->lit_bufsize/sizeof (ush);
13507c478bdstevel@tonic-gate	ds->l_buf = ds->pending_buf + (1+sizeof (ush))*ds->lit_bufsize;
13517c478bdstevel@tonic-gate
13527c478bdstevel@tonic-gate	ds->l_desc.dyn_tree = ds->dyn_ltree;
13537c478bdstevel@tonic-gate	ds->d_desc.dyn_tree = ds->dyn_dtree;
13547c478bdstevel@tonic-gate	ds->bl_desc.dyn_tree = ds->bl_tree;
13557c478bdstevel@tonic-gate
13567c478bdstevel@tonic-gate	return (Z_OK);
13577c478bdstevel@tonic-gate#endif
13587c478bdstevel@tonic-gate}
13597c478bdstevel@tonic-gate
13607c478bdstevel@tonic-gate/*
13617c478bdstevel@tonic-gate * ===========================================================================
13627c478bdstevel@tonic-gate * Return the number of bytes of output which are immediately available
13637c478bdstevel@tonic-gate * for output from the decompressor.		---PPP---
13647c478bdstevel@tonic-gate */
13657c478bdstevel@tonic-gateint
13667c478bdstevel@tonic-gatedeflateOutputPending(strm)
13677c478bdstevel@tonic-gate    z_streamp strm;
13687c478bdstevel@tonic-gate{
13697c478bdstevel@tonic-gate	if (strm == Z_NULL || strm->state == Z_NULL)
13707c478bdstevel@tonic-gate		return (0);
13717c478bdstevel@tonic-gate
13727c478bdstevel@tonic-gate	return (((deflate_state *)(strm->state))->pending);
13737c478bdstevel@tonic-gate}
13747c478bdstevel@tonic-gate
13757c478bdstevel@tonic-gate/*
13767c478bdstevel@tonic-gate * ===========================================================================
13777c478bdstevel@tonic-gate * Read a new buffer from the current input stream, update the adler32
13787c478bdstevel@tonic-gate * and total number of bytes read.  All deflate() input goes through
13797c478bdstevel@tonic-gate * this function so some applications may wish to modify it to avoid
13807c478bdstevel@tonic-gate * allocating a large strm->next_in buffer and copying from it.
13817c478bdstevel@tonic-gate * (See also flush_pending()).
13827c478bdstevel@tonic-gate */
13837c478bdstevel@tonic-gatelocal int
13847c478bdstevel@tonic-gateread_buf(strm, buf, size)
13857c478bdstevel@tonic-gate    z_streamp strm;
13867c478bdstevel@tonic-gate    Bytef *buf;
13877c478bdstevel@tonic-gate    unsigned size;
13887c478bdstevel@tonic-gate{
13897c478bdstevel@tonic-gate	unsigned len = strm->avail_in;
13907c478bdstevel@tonic-gate
13917c478bdstevel@tonic-gate	if (len > size) len = size;
13927c478bdstevel@tonic-gate	if (len == 0)
13937c478bdstevel@tonic-gate		return (0);
13947c478bdstevel@tonic-gate
13957c478bdstevel@tonic-gate	strm->avail_in  -= len;
13967c478bdstevel@tonic-gate
13977c478bdstevel@tonic-gate	if (!((deflate_state *)(strm->state))->noheader) {
13987c478bdstevel@tonic-gate		strm->adler = adler32(strm->adler, strm->next_in, len);
13997c478bdstevel@tonic-gate	}
14007c478bdstevel@tonic-gate	zmemcpy(buf, strm->next_in, len);
14017c478bdstevel@tonic-gate	strm->next_in  += len;
14027c478bdstevel@tonic-gate	strm->total_in += len;
14037c478bdstevel@tonic-gate
14047c478bdstevel@tonic-gate	return ((int)len);
14057c478bdstevel@tonic-gate}
14067c478bdstevel@tonic-gate
14077c478bdstevel@tonic-gate/*
14087c478bdstevel@tonic-gate * ===========================================================================
14097c478bdstevel@tonic-gate * Initialize the "longest match" routines for a new zlib stream
14107c478bdstevel@tonic-gate */
14117c478bdstevel@tonic-gatelocal void
14127c478bdstevel@tonic-gatelm_init(s)
14137c478bdstevel@tonic-gate    deflate_state *s;
14147c478bdstevel@tonic-gate{
14157c478bdstevel@tonic-gate	s->window_size = (ulg)2L*s->w_size;
14167c478bdstevel@tonic-gate
14177c478bdstevel@tonic-gate	CLEAR_HASH(s);
14187c478bdstevel@tonic-gate
14197c478bdstevel@tonic-gate	/* Set the default configuration parameters: */
14207c478bdstevel@tonic-gate	s->max_lazy_match   = configuration_table[s->level].max_lazy;
14217c478bdstevel@tonic-gate	s->good_match	= configuration_table[s->level].good_length;
14227c478bdstevel@tonic-gate	s->nice_match	= configuration_table[s->level].nice_length;
14237c478bdstevel@tonic-gate	s->max_chain_length = configuration_table[s->level].max_chain;
14247c478bdstevel@tonic-gate
14257c478bdstevel@tonic-gate	s->strstart = 0;
14267c478bdstevel@tonic-gate	s->block_start = 0L;
14277c478bdstevel@tonic-gate	s->lookahead = 0;
14287c478bdstevel@tonic-gate	s->match_length = s->prev_length = MIN_MATCH-1;
14297c478bdstevel@tonic-gate	s->match_available = 0;
14307c478bdstevel@tonic-gate	s->ins_h = 0;
14317c478bdstevel@tonic-gate#ifdef ASMV
14327c478bdstevel@tonic-gate	match_init();	/* initialize the asm code */
14337c478bdstevel@tonic-gate#endif
14347c478bdstevel@tonic-gate}
14357c478bdstevel@tonic-gate
14367c478bdstevel@tonic-gate/*
14377c478bdstevel@tonic-gate * ===========================================================================
14387c478bdstevel@tonic-gate * Set match_start to the longest match starting at the given string and
14397c478bdstevel@tonic-gate * return its length. Matches shorter or equal to prev_length are discarded,
14407c478bdstevel@tonic-gate * in which case the result is equal to prev_length and match_start is
14417c478bdstevel@tonic-gate * garbage.
14427c478bdstevel@tonic-gate * IN assertions: cur_match is the head of the hash chain for the current
14437c478bdstevel@tonic-gate *   string (strstart) and its distance is <= MAX_DIST, and prev_length >= 1
14447c478bdstevel@tonic-gate * OUT assertion: the match length is not greater than s->lookahead.
14457c478bdstevel@tonic-gate */
14467c478bdstevel@tonic-gate#ifndef ASMV
14477c478bdstevel@tonic-gate/*
14487c478bdstevel@tonic-gate * For 80x86 and 680x0, an optimized version will be provided in
14497c478bdstevel@tonic-gate * match.asm or match.S. The code will be functionally equivalent.
14507c478bdstevel@tonic-gate */
14517c478bdstevel@tonic-gate#ifndef FASTEST
14527c478bdstevel@tonic-gatelocal uInt
14537c478bdstevel@tonic-gatelongest_match(s, cur_match)
14547c478bdstevel@tonic-gate    deflate_state *s;
14557c478bdstevel@tonic-gate    IPos cur_match;	/* current match */
14567c478bdstevel@tonic-gate{
14577c478bdstevel@tonic-gate	/* max hash chain length */
14587c478bdstevel@tonic-gate	unsigned chain_length = s->max_chain_length;
14597c478bdstevel@tonic-gate	register Bytef *scan = s->window + s->strstart;	/* current string */
14607c478bdstevel@tonic-gate	register Bytef *match;	/* matched string */
14617c478bdstevel@tonic-gate	register int len;	/* length of current match */
14627c478bdstevel@tonic-gate	int best_len = s->prev_length;	/* best match length so far */
14637c478bdstevel@tonic-gate	int nice_match = s->nice_match;	/* stop if match long enough */
14647c478bdstevel@tonic-gate	IPos limit = s->strstart > (IPos)MAX_DIST(s) ?
14657c478bdstevel@tonic-gate	    s->strstart - (IPos)MAX_DIST(s) : NIL;
14667c478bdstevel@tonic-gate	/*
14677c478bdstevel@tonic-gate	 * Stop when cur_match becomes <= limit. To simplify the code,
14687c478bdstevel@tonic-gate	 * we prevent matches with the string of window index 0.
14697c478bdstevel@tonic-gate	 */
14707c478bdstevel@tonic-gate	Posf *prev = s->prev;
14717c478bdstevel@tonic-gate	uInt wmask = s->w_mask;
14727c478bdstevel@tonic-gate
14737c478bdstevel@tonic-gate#ifdef UNALIGNED_OK
14747c478bdstevel@tonic-gate	/*
14757c478bdstevel@tonic-gate	 * Compare two bytes at a time. Note: this is not always
14767c478bdstevel@tonic-gate	 * beneficial.  Try with and without -DUNALIGNED_OK to check.
14777c478bdstevel@tonic-gate	 */
14787c478bdstevel@tonic-gate	register Bytef *strend = s->window + s->strstart + MAX_MATCH - 1;
14797c478bdstevel@tonic-gate	register ush scan_start = *(ushf*)scan;
14807c478bdstevel@tonic-gate	register ush scan_end   = *(ushf*)(scan+best_len-1);
14817c478bdstevel@tonic-gate#else
14827c478bdstevel@tonic-gate	register Bytef *strend = s->window + s->strstart + MAX_MATCH;
14837c478bdstevel@tonic-gate	register Byte scan_end1  = scan[best_len-1];
14847c478bdstevel@tonic-gate	register Byte scan_end   = scan[best_len];
14857c478bdstevel@tonic-gate#endif
14867c478bdstevel@tonic-gate
14877c478bdstevel@tonic-gate	/*
14887c478bdstevel@tonic-gate	 * The code is optimized for HASH_BITS >= 8 and MAX_MATCH-2
14897c478bdstevel@tonic-gate	 * multiple of 16.  It is easy to get rid of this optimization
14907c478bdstevel@tonic-gate	 * if necessary.
14917c478bdstevel@tonic-gate	 */
14927c478bdstevel@tonic-gate	Assert(s->hash_bits >= 8 && MAX_MATCH == 258, "Code too clever");
14937c478bdstevel@tonic-gate
14947c478bdstevel@tonic-gate	/* Do not waste too much time if we already have a good match: */
14957c478bdstevel@tonic-gate	if (s->prev_length >= s->good_match) {
14967c478bdstevel@tonic-gate		chain_length >>= 2;
14977c478bdstevel@tonic-gate	}
14987c478bdstevel@tonic-gate	/*
14997c478bdstevel@tonic-gate	 * Do not look for matches beyond the end of the input. This
15007c478bdstevel@tonic-gate	 * is necessary to make deflate deterministic.
15017c478bdstevel@tonic-gate	 */
15027c478bdstevel@tonic-gate	if ((uInt)nice_match > s->lookahead) nice_match = s->lookahead;
15037c478bdstevel@tonic-gate
15047c478bdstevel@tonic-gate	Assert((ulg)s->strstart <= s->window_size-MIN_LOOKAHEAD,
15057c478bdstevel@tonic-gate	    "need lookahead");
15067c478bdstevel@tonic-gate
15077c478bdstevel@tonic-gate	do {
15087c478bdstevel@tonic-gate		Assert(cur_match <= s->strstart, "no future");
15097c478bdstevel@tonic-gate		match = s->window + cur_match;
15107c478bdstevel@tonic-gate
15117c478bdstevel@tonic-gate		/*
15127c478bdstevel@tonic-gate		 * Skip to next match if the match length cannot
15137c478bdstevel@tonic-gate		 * increase or if the match length is less than 2:
15147c478bdstevel@tonic-gate		 */
15157c478bdstevel@tonic-gate#if (defined(UNALIGNED_OK) && MAX_MATCH == 258)
15167c478bdstevel@tonic-gate		/*
15177c478bdstevel@tonic-gate		 * This code assumes sizeof (unsigned short) == 2. Do
15187c478bdstevel@tonic-gate		 * not use UNALIGNED_OK if your compiler uses a
15197c478bdstevel@tonic-gate		 * different size.
15207c478bdstevel@tonic-gate		 */
15217c478bdstevel@tonic-gate		if (*(ushf*)(match+best_len-1) != scan_end ||
15227c478bdstevel@tonic-gate		    *(ushf*)match != scan_start) continue;
15237c478bdstevel@tonic-gate
15247c478bdstevel@tonic-gate		/*
15257c478bdstevel@tonic-gate		 * It is not necessary to compare scan[2] and match[2]
15267c478bdstevel@tonic-gate		 * since they are always equal when the other bytes
15277c478bdstevel@tonic-gate		 * match, given that the hash keys are equal and that
15287c478bdstevel@tonic-gate		 * HASH_BITS >= 8. Compare 2 bytes at a time at
15297c478bdstevel@tonic-gate		 * strstart+3, +5, ... up to strstart+257. We check
15307c478bdstevel@tonic-gate		 * for insufficient lookahead only every 4th
15317c478bdstevel@tonic-gate		 * comparison; the 128th check will be made at
15327c478bdstevel@tonic-gate		 * strstart+257. If MAX_MATCH-2 is not a multiple of
15337c478bdstevel@tonic-gate		 * 8, it is necessary to put more guard bytes at the
15347c478bdstevel@tonic-gate		 * end of the window, or to check more often for
15357c478bdstevel@tonic-gate		 * insufficient lookahead.
15367c478bdstevel@tonic-gate		 */
15377c478bdstevel@tonic-gate		Assert(scan[2] == match[2], "scan[2]?");
15387c478bdstevel@tonic-gate		scan++, match++;
15397c478bdstevel@tonic-gate		do {
15407c478bdstevel@tonic-gate		} while (*(ushf *)(scan += 2) == *(ushf *)(match += 2) &&
15417c478bdstevel@tonic-gate		    *(ushf *)(scan += 2) == *(ushf *)(match += 2) &&
15427c478bdstevel@tonic-gate		    *(ushf *)(scan += 2) == *(ushf *)(match += 2) &&
15437c478bdstevel@tonic-gate		    *(ushf *)(scan += 2) == *(ushf *)(match += 2) &&
15447c478bdstevel@tonic-gate		    scan < strend);
15457c478bdstevel@tonic-gate		/* The funny "do {}" generates better code on most compilers */
15467c478bdstevel@tonic-gate
15477c478bdstevel@tonic-gate		/* Here, scan <= window+strstart+257 */
15487c478bdstevel@tonic-gate		Assert(scan <= s->window+(unsigned)(s->window_size-1),
15497c478bdstevel@tonic-gate		    "wild scan");
15507c478bdstevel@tonic-gate		if (*scan == *match) scan++;
15517c478bdstevel@tonic-gate
15527c478bdstevel@tonic-gate		len = (MAX_MATCH - 1) - (int)(strend-scan);
15537c478bdstevel@tonic-gate		scan = strend - (MAX_MATCH-1);
15547c478bdstevel@tonic-gate
15557c478bdstevel@tonic-gate#else /* UNALIGNED_OK */
15567c478bdstevel@tonic-gate
15577c478bdstevel@tonic-gate		if (match[best_len]	!= scan_end	||
15587c478bdstevel@tonic-gate		    match[best_len-1]	!= scan_end1	||
15597c478bdstevel@tonic-gate		    *match		!= *scan	||
15607c478bdstevel@tonic-gate		    *++match		!= scan[1])
15617c478bdstevel@tonic-gate			continue;
15627c478bdstevel@tonic-gate
15637c478bdstevel@tonic-gate		/*
15647c478bdstevel@tonic-gate		 * The check at best_len-1 can be removed because it
15657c478bdstevel@tonic-gate		 * will be made again later. (This heuristic is not
15667c478bdstevel@tonic-gate		 * always a win.)  It is not necessary to compare
15677c478bdstevel@tonic-gate		 * scan[2] and match[2] since they are always equal
15687c478bdstevel@tonic-gate		 * when the other bytes match, given that the hash
15697c478bdstevel@tonic-gate		 * keys are equal and that HASH_BITS >= 8.
15707c478bdstevel@tonic-gate		 */
15717c478bdstevel@tonic-gate		scan += 2, match++;
15727c478bdstevel@tonic-gate		Assert(*scan == *match, "match[2]?");
15737c478bdstevel@tonic-gate
15747c478bdstevel@tonic-gate		/*
15757c478bdstevel@tonic-gate		 * We check for insufficient lookahead only every 8th
15767c478bdstevel@tonic-gate		 * comparison; the 256th check will be made at
15777c478bdstevel@tonic-gate		 * strstart+258.
15787c478bdstevel@tonic-gate		 */
15797c478bdstevel@tonic-gate		do {
15807c478bdstevel@tonic-gate		} while (*++scan == *++match && *++scan == *++match &&
15817c478bdstevel@tonic-gate		    *++scan == *++match && *++scan == *++match &&
15827c478bdstevel@tonic-gate		    *++scan == *++match && *++scan == *++match &&
15837c478bdstevel@tonic-gate		    *++scan == *++match && *++scan == *++match &&
15847c478bdstevel@tonic-gate		    scan < strend);
15857c478bdstevel@tonic-gate
15867c478bdstevel@tonic-gate		Assert(scan <= s->window+(unsigned)(s->window_size-1),
15877c478bdstevel@tonic-gate		    "wild scan");
15887c478bdstevel@tonic-gate
15897c478bdstevel@tonic-gate		len = MAX_MATCH - (int)(strend - scan);
15907c478bdstevel@tonic-gate		scan = strend - MAX_MATCH;
15917c478bdstevel@tonic-gate
15927c478bdstevel@tonic-gate#endif /* UNALIGNED_OK */
15937c478bdstevel@tonic-gate
15947c478bdstevel@tonic-gate		if (len > best_len) {
15957c478bdstevel@tonic-gate			s->match_start = cur_match;
15967c478bdstevel@tonic-gate			best_len = len;
15977c478bdstevel@tonic-gate			if (len >= nice_match) break;
15987c478bdstevel@tonic-gate#ifdef UNALIGNED_OK
15997c478bdstevel@tonic-gate			scan_end = *(ushf*)(scan+best_len-1);
16007c478bdstevel@tonic-gate#else
16017c478bdstevel@tonic-gate			scan_end1  = scan[best_len-1];
16027c478bdstevel@tonic-gate			scan_end   = scan[best_len];
16037c478bdstevel@tonic-gate#endif
16047c478bdstevel@tonic-gate		}
16057c478bdstevel@tonic-gate	} while ((cur_match = prev[cur_match & wmask]) > limit &&
16067c478bdstevel@tonic-gate	    --chain_length != 0);
16077c478bdstevel@tonic-gate
16087c478bdstevel@tonic-gate	if ((uInt)best_len <= s->lookahead)
16097c478bdstevel@tonic-gate		return (best_len);
16107c478bdstevel@tonic-gate	return (s->lookahead);
16117c478bdstevel@tonic-gate}
16127c478bdstevel@tonic-gate#else /* FASTEST */
16137c478bdstevel@tonic-gate/*
16147c478bdstevel@tonic-gate * ---------------------------------------------------------------------------
16157c478bdstevel@tonic-gate * Optimized version for level == 1 only
16167c478bdstevel@tonic-gate */
16177c478bdstevel@tonic-gatelocal uInt
16187c478bdstevel@tonic-gatelongest_match(s, cur_match)
16197c478bdstevel@tonic-gatedeflate_state *s;
16207c478bdstevel@tonic-gateIPos cur_match;		/* current match */
16217c478bdstevel@tonic-gate{
16227c478bdstevel@tonic-gate	register Bytef *scan = s->window + s->strstart; /* current string */
16237c478bdstevel@tonic-gate	register Bytef *match;		/* matched string */
16247c478bdstevel@tonic-gate	register int len;			/* length of current match */
16257c478bdstevel@tonic-gate	register Bytef *strend = s->window + s->strstart + MAX_MATCH;
16267c478bdstevel@tonic-gate
16277c478bdstevel@tonic-gate	/*
16287c478bdstevel@tonic-gate	 * The code is optimized for HASH_BITS >= 8 and MAX_MATCH-2
16297c478bdstevel@tonic-gate	 * multiple of 16.  It is easy to get rid of this optimization
16307c478bdstevel@tonic-gate	 * if necessary.
16317c478bdstevel@tonic-gate	 */
16327c478bdstevel@tonic-gate	Assert(s->hash_bits >= 8 && MAX_MATCH == 258, "Code too clever");
16337c478bdstevel@tonic-gate
16347c478bdstevel@tonic-gate	Assert((ulg)s->strstart <= s->window_size-MIN_LOOKAHEAD,
16357c478bdstevel@tonic-gate	    "need lookahead");
16367c478bdstevel@tonic-gate
16377c478bdstevel@tonic-gate	Assert(cur_match <= s->strstart, "no future");
16387c478bdstevel@tonic-gate
16397c478bdstevel@tonic-gate	match = s->window + cur_match;
16407c478bdstevel@tonic-gate
16417c478bdstevel@tonic-gate	/* Return failure if the match length is less than 2: */
16427c478bdstevel@tonic-gate	if (match[0] != scan[0] || match[1] != scan[1])
16437c478bdstevel@tonic-gate		return (MIN_MATCH-1);
16447c478bdstevel@tonic-gate
16457c478bdstevel@tonic-gate	/*
16467c478bdstevel@tonic-gate	 * The check at best_len-1 can be removed because it will be
16477c478bdstevel@tonic-gate	 * made again later. (This heuristic is not always a win.)  It
16487c478bdstevel@tonic-gate	 * is not necessary to compare scan[2] and match[2] since they
16497c478bdstevel@tonic-gate	 * are always equal when the other bytes match, given that the
16507c478bdstevel@tonic-gate	 * hash keys are equal and that HASH_BITS >= 8.
16517c478bdstevel@tonic-gate	 */
16527c478bdstevel@tonic-gate	scan += 2, match += 2;
16537c478bdstevel@tonic-gate	Assert(*scan == *match, "match[2]?");
16547c478bdstevel@tonic-gate
16557c478bdstevel@tonic-gate	/*
16567c478bdstevel@tonic-gate	 * We check for insufficient lookahead only every 8th comparison;
16577c478bdstevel@tonic-gate	 * the 256th check will be made at strstart+258.
16587c478bdstevel@tonic-gate	 */
16597c478bdstevel@tonic-gate	do {
16607c478bdstevel@tonic-gate	} while (*++scan == *++match && *++scan == *++match &&
16617c478bdstevel@tonic-gate	    *++scan == *++match && *++scan == *++match &&
16627c478bdstevel@tonic-gate	    *++scan == *++match && *++scan == *++match &&
16637c478bdstevel@tonic-gate	    *++scan == *++match && *++scan == *++match &&
16647c478bdstevel@tonic-gate	    scan < strend);
16657c478bdstevel@tonic-gate
16667c478bdstevel@tonic-gate	Assert(scan <= s->window+(unsigned)(s->window_size-1), "wild scan");
16677c478bdstevel@tonic-gate
16687c478bdstevel@tonic-gate	len = MAX_MATCH - (int)(strend - scan);
16697c478bdstevel@tonic-gate
16707c478bdstevel@tonic-gate	if (len < MIN_MATCH)
16717c478bdstevel@tonic-gate		return (MIN_MATCH - 1);
16727c478bdstevel@tonic-gate
16737c478bdstevel@tonic-gate	s->match_start = cur_match;
16747c478bdstevel@tonic-gate	return (len <= s->lookahead ? len : s->lookahead);
16757c478bdstevel@tonic-gate}
16767c478bdstevel@tonic-gate#endif /* FASTEST */
16777c478bdstevel@tonic-gate#endif /* ASMV */
16787c478bdstevel@tonic-gate
16797c478bdstevel@tonic-gate#ifdef DEBUG_ZLIB
16807c478bdstevel@tonic-gate/*
16817c478bdstevel@tonic-gate * ===========================================================================
16827c478bdstevel@tonic-gate * Check that the match at match_start is indeed a match.
16837c478bdstevel@tonic-gate */
16847c478bdstevel@tonic-gatelocal void
16857c478bdstevel@tonic-gatecheck_match(s, start, match, length)
16867c478bdstevel@tonic-gate    deflate_state *s;
16877c478bdstevel@tonic-gate    IPos start, match;
16887c478bdstevel@tonic-gate    int length;
16897c478bdstevel@tonic-gate{
16907c478bdstevel@tonic-gate	/* check that the match is indeed a match */
16917c478bdstevel@tonic-gate	if (zmemcmp(s->window + match, s->window + start, length) != EQUAL) {
16927c478bdstevel@tonic-gate		fprintf(stderr, " start %u, match %u, length %d\n",
16937c478bdstevel@tonic-gate		    start, match, length);
16947c478bdstevel@tonic-gate		do {
16957c478bdstevel@tonic-gate			fprintf(stderr, "%c%c", s->window[match++],
16967c478bdstevel@tonic-gate			    s->window[start++]);
16977c478bdstevel@tonic-gate		} while (--length != 0);
16987c478bdstevel@tonic-gate		z_error("invalid match");
16997c478bdstevel@tonic-gate	}
17007c478bdstevel@tonic-gate	if (z_verbose > 1) {
17017c478bdstevel@tonic-gate		fprintf(stderr, "\\[%d,%d]", start-match, length);
17027c478bdstevel@tonic-gate		do { putc(s->window[start++], stderr); } while (--length != 0);
17037c478bdstevel@tonic-gate	}
17047c478bdstevel@tonic-gate}
17057c478bdstevel@tonic-gate#else
17067c478bdstevel@tonic-gate#define	check_match(s, start, match, length)
17077c478bdstevel@tonic-gate#endif
17087c478bdstevel@tonic-gate
17097c478bdstevel@tonic-gate/*
17107c478bdstevel@tonic-gate * ===========================================================================
17117c478bdstevel@tonic-gate * Fill the window when the lookahead becomes insufficient.
17127c478bdstevel@tonic-gate * Updates strstart and lookahead.
17137c478bdstevel@tonic-gate *
17147c478bdstevel@tonic-gate * IN assertion: lookahead < MIN_LOOKAHEAD
17157c478bdstevel@tonic-gate * OUT assertions: strstart <= window_size-MIN_LOOKAHEAD
17167c478bdstevel@tonic-gate *    At least one byte has been read, or avail_in == 0; reads are
17177c478bdstevel@tonic-gate *    performed for at least two bytes (required for the zip translate_eol
17187c478bdstevel@tonic-gate *    option -- not supported here).
17197c478bdstevel@tonic-gate */
17207c478bdstevel@tonic-gatelocal void
17217c478bdstevel@tonic-gatefill_window(s)
17227c478bdstevel@tonic-gate    deflate_state *s;
17237c478bdstevel@tonic-gate{
17247c478bdstevel@tonic-gate	register unsigned n, m;
17257c478bdstevel@tonic-gate	register Posf *p;
17267c478bdstevel@tonic-gate	unsigned more;	/* Amount of free space at the end of the window. */
17277c478bdstevel@tonic-gate	uInt wsize = s->w_size;
17287c478bdstevel@tonic-gate
17297c478bdstevel@tonic-gate	do {
17307c478bdstevel@tonic-gate		more = (unsigned)(s->window_size -(ulg)s->lookahead -
17317c478bdstevel@tonic-gate		    (ulg)s->strstart);
17327c478bdstevel@tonic-gate
17337c478bdstevel@tonic-gate		/* Deal with !@#$% 64K limit: */
17347c478bdstevel@tonic-gate		if (more == 0 && s->strstart == 0 && s->lookahead == 0) {
17357c478bdstevel@tonic-gate			more = wsize;
17367c478bdstevel@tonic-gate
17377c478bdstevel@tonic-gate		} else if (more == (unsigned)(-1)) {
17387c478bdstevel@tonic-gate			/*
17397c478bdstevel@tonic-gate			 * Very unlikely, but possible on 16 bit
17407c478bdstevel@tonic-gate			 * machine if strstart == 0 and lookahead == 1
17417c478bdstevel@tonic-gate			 * (input done one byte at time)
17427c478bdstevel@tonic-gate			 */
17437c478bdstevel@tonic-gate			more--;
17447c478bdstevel@tonic-gate
17457c478bdstevel@tonic-gate			/*
17467c478bdstevel@tonic-gate			 * If the window is almost full and there is
17477c478bdstevel@tonic-gate			 * insufficient lookahead, move the upper half
17487c478bdstevel@tonic-gate			 * to the lower one to make room in the upper
17497c478bdstevel@tonic-gate			 * half.
17507c478bdstevel@tonic-gate			 */
17517c478bdstevel@tonic-gate		} else if (s->strstart >= wsize+MAX_DIST(s)) {
17527c478bdstevel@tonic-gate
17537c478bdstevel@tonic-gate			Assert(wsize+wsize <= s->window_size, "wsize*2");
17547c478bdstevel@tonic-gate			zmemcpy(s->window, s->window+wsize, (unsigned)wsize);
17557c478bdstevel@tonic-gate			s->match_start -= wsize;
17567c478bdstevel@tonic-gate			/* we now have strstart >= MAX_DIST */
17577c478bdstevel@tonic-gate			s->strstart    -= wsize;
17587c478bdstevel@tonic-gate			s->block_start -= (long)wsize;
17597c478bdstevel@tonic-gate
17607c478bdstevel@tonic-gate			/*
17617c478bdstevel@tonic-gate			 * Slide the hash table (could be avoided with
17627c478bdstevel@tonic-gate			 * 32 bit values at the expense of memory
17637c478bdstevel@tonic-gate			 * usage). We slide even when level == 0 to
17647c478bdstevel@tonic-gate			 * keep the hash table consistent if we switch
17657c478bdstevel@tonic-gate			 * back to level > 0 later. (Using level 0
17667c478bdstevel@tonic-gate			 * permanently is not an optimal usage of
17677c478bdstevel@tonic-gate			 * zlib, so we don't care about this
17687c478bdstevel@tonic-gate			 * pathological case.)
17697c478bdstevel@tonic-gate			 */
17707c478bdstevel@tonic-gate			n = s->hash_size;
17717c478bdstevel@tonic-gate			p = &s->head[n];
17727c478bdstevel@tonic-gate			do {
17737c478bdstevel@tonic-gate				m = *--p;
17747c478bdstevel@tonic-gate				*p = (Pos)(m >= wsize ? m-wsize : NIL);
17757c478bdstevel@tonic-gate			} while (--n);
17767c478bdstevel@tonic-gate
17777c478bdstevel@tonic-gate			n = wsize;
17787c478bdstevel@tonic-gate#ifndef FASTEST
17797c478bdstevel@tonic-gate			p = &s->prev[n];
17807c478bdstevel@tonic-gate			do {
17817c478bdstevel@tonic-gate				m = *--p;
17827c478bdstevel@tonic-gate				*p = (Pos)(m >= wsize ? m-wsize : NIL);
17837c478bdstevel@tonic-gate				/*
17847c478bdstevel@tonic-gate				 * If n is not on any hash chain,
17857c478bdstevel@tonic-gate				 * prev[n] is garbage but its value
17867c478bdstevel@tonic-gate				 * will never be used.
17877c478bdstevel@tonic-gate				 */
17887c478bdstevel@tonic-gate			} while (--n);
17897c478bdstevel@tonic-gate#endif
17907c478bdstevel@tonic-gate			more += wsize;
17917c478bdstevel@tonic-gate		}
17927c478bdstevel@tonic-gate		if (s->strm->avail_in == 0)
17937c478bdstevel@tonic-gate			return;
17947c478bdstevel@tonic-gate
17957c478bdstevel@tonic-gate		/*
17967c478bdstevel@tonic-gate		 * If there was no sliding:
17977c478bdstevel@tonic-gate		 *    strstart <= WSIZE+MAX_DIST-1 &&
17987c478bdstevel@tonic-gate		 *	lookahead <= MIN_LOOKAHEAD - 1 &&
17997c478bdstevel@tonic-gate		 *    more == window_size - lookahead - strstart
18007c478bdstevel@tonic-gate		 * => more >= window_size - (MIN_LOOKAHEAD-1 + WSIZE +
18017c478bdstevel@tonic-gate		 *	MAX_DIST-1)
18027c478bdstevel@tonic-gate		 * => more >= window_size - 2*WSIZE + 2
18037c478bdstevel@tonic-gate		 * In the BIG_MEM or MMAP case (not yet supported),
18047c478bdstevel@tonic-gate		 *   window_size == input_size + MIN_LOOKAHEAD  &&
18057c478bdstevel@tonic-gate		 *   strstart + s->lookahead <= input_size =>
18067c478bdstevel@tonic-gate		 *	more >= MIN_LOOKAHEAD.
18077c478bdstevel@tonic-gate		 * Otherwise, window_size == 2*WSIZE so more >= 2.
18087c478bdstevel@tonic-gate		 * If there was sliding, more >= WSIZE. So in all cases,
18097c478bdstevel@tonic-gate		 * more >= 2.
18107c478bdstevel@tonic-gate		 */
18117c478bdstevel@tonic-gate		Assert(more >= 2, "more < 2");
18127c478bdstevel@tonic-gate		Assert(s->strstart + s->lookahead + more <= s->window_size,
18137c478bdstevel@tonic-gate		    "read too much");
18147c478bdstevel@tonic-gate
18157c478bdstevel@tonic-gate		n = read_buf(s->strm, s->window + s->strstart + s->lookahead,
18167c478bdstevel@tonic-gate		    more);
18177c478bdstevel@tonic-gate		s->lookahead += n;
18187c478bdstevel@tonic-gate
18197c478bdstevel@tonic-gate		/* Initialize the hash value now that we have some input: */
18207c478bdstevel@tonic-gate		if (s->lookahead >= MIN_MATCH) {
18217c478bdstevel@tonic-gate			s->ins_h = s->window[s->strstart];
18227c478bdstevel@tonic-gate			UPDATE_HASH(s, s->ins_h, s->window[s->strstart+1]);
18237c478bdstevel@tonic-gate#if MIN_MATCH != 3
18247c478bdstevel@tonic-gate			Call UPDATE_HASH() MIN_MATCH-3 more times
18257c478bdstevel@tonic-gate#endif
18267c478bdstevel@tonic-gate			    }
18277c478bdstevel@tonic-gate		/*
18287c478bdstevel@tonic-gate		 * If the whole input has less than MIN_MATCH bytes,
18297c478bdstevel@tonic-gate		 * ins_h is garbage, but this is not important since
18307c478bdstevel@tonic-gate		 * only literal bytes will be emitted.
18317c478bdstevel@tonic-gate		 */
18327c478bdstevel@tonic-gate
18337c478bdstevel@tonic-gate	} while (s->lookahead < MIN_LOOKAHEAD && s->strm->avail_in != 0);
18347c478bdstevel@tonic-gate}
18357c478bdstevel@tonic-gate
18367c478bdstevel@tonic-gate/*
18377c478bdstevel@tonic-gate * ===========================================================================
18387c478bdstevel@tonic-gate * Flush the current block, with given end-of-file flag.
18397c478bdstevel@tonic-gate * IN assertion: strstart is set to the end of the current match.
18407c478bdstevel@tonic-gate */
18417c478bdstevel@tonic-gate#define	FLUSH_BLOCK_ONLY(s, eof) { \
18427c478bdstevel@tonic-gate	_tr_flush_block(s, (s->block_start >= 0L ? \
18437c478bdstevel@tonic-gate		(charf *)&s->window[(unsigned)s->block_start] : \
18447c478bdstevel@tonic-gate		(charf *)Z_NULL), \
18457c478bdstevel@tonic-gate		(ulg)((long)s->strstart - s->block_start), \
18467c478bdstevel@tonic-gate		(eof)); \
18477c478bdstevel@tonic-gate	s->block_start = s->strstart; \
18487c478bdstevel@tonic-gate	flush_pending(s->strm); \
18497c478bdstevel@tonic-gate	Tracev((stderr, "[FLUSH]")); \
18507c478bdstevel@tonic-gate}
18517c478bdstevel@tonic-gate
18527c478bdstevel@tonic-gate/* Same but force premature exit if necessary. */
18537c478bdstevel@tonic-gate#define	FLUSH_BLOCK(s, eof) { \
18547c478bdstevel@tonic-gate	FLUSH_BLOCK_ONLY(s, eof); \
18557c478bdstevel@tonic-gate	if (s->strm->avail_out == 0) \
18567c478bdstevel@tonic-gate		return ((eof) ? finish_started : need_more); \
18577c478bdstevel@tonic-gate}
18587c478bdstevel@tonic-gate
18597c478bdstevel@tonic-gate/*
18607c478bdstevel@tonic-gate * ===========================================================================
18617c478bdstevel@tonic-gate * Copy without compression as much as possible from the input stream, return
18627c478bdstevel@tonic-gate * the current block state.
18637c478bdstevel@tonic-gate * This function does not insert new strings in the dictionary since
18647c478bdstevel@tonic-gate * uncompressible data is probably not useful. This function is used
18657c478bdstevel@tonic-gate * only for the level=0 compression option.
18667c478bdstevel@tonic-gate * NOTE: this function should be optimized to avoid extra copying from
18677c478bdstevel@tonic-gate * window to pending_buf.
18687c478bdstevel@tonic-gate */
18697c478bdstevel@tonic-gatelocal block_state
18707c478bdstevel@tonic-gatedeflate_stored(s, flush)
18717c478bdstevel@tonic-gate    deflate_state *s;
18727c478bdstevel@tonic-gate    int flush;
18737c478bdstevel@tonic-gate{
18747c478bdstevel@tonic-gate	/*
18757c478bdstevel@tonic-gate	 * Stored blocks are limited to 0xffff bytes, pending_buf is
18767c478bdstevel@tonic-gate	 * limited to pending_buf_size, and each stored block has a 5
18777c478bdstevel@tonic-gate	 * byte header:
18787c478bdstevel@tonic-gate	 */
18797c478bdstevel@tonic-gate	ulg max_block_size = 0xffff;
18807c478bdstevel@tonic-gate	ulg max_start;
18817c478bdstevel@tonic-gate
18827c478bdstevel@tonic-gate	if (max_block_size > s->pending_buf_size - 5) {
18837c478bdstevel@tonic-gate		max_block_size = s->pending_buf_size - 5;
18847c478bdstevel@tonic-gate	}
18857c478bdstevel@tonic-gate
18867c478bdstevel@tonic-gate	/* Copy as much as possible from input to output: */
18877c478bdstevel@tonic-gate	for (;;) {
18887c478bdstevel@tonic-gate		/* Fill the window as much as possible: */
18897c478bdstevel@tonic-gate		if (s->lookahead <= 1) {
18907c478bdstevel@tonic-gate
18917c478bdstevel@tonic-gate			Assert(s->strstart < s->w_size+MAX_DIST(s) ||
18927c478bdstevel@tonic-gate			    s->block_start >= (long)s->w_size,
18937c478bdstevel@tonic-gate			    "slide too late");
18947c478bdstevel@tonic-gate
18957c478bdstevel@tonic-gate			fill_window(s);
18967c478bdstevel@tonic-gate			if (s->lookahead == 0 && flush == Z_NO_FLUSH)
18977c478bdstevel@tonic-gate				return (need_more);
18987c478bdstevel@tonic-gate
18997c478bdstevel@tonic-gate			if (s->lookahead == 0)
19007c478bdstevel@tonic-gate				break;	/* flush the current block */
19017c478bdstevel@tonic-gate		}
19027c478bdstevel@tonic-gate		Assert(s->block_start >= 0L, "block gone");
19037c478bdstevel@tonic-gate
19047c478bdstevel@tonic-gate		s->strstart += s->lookahead;
19057c478bdstevel@tonic-gate		s->lookahead = 0;
19067c478bdstevel@tonic-gate
19077c478bdstevel@tonic-gate		/* Emit a stored block if pending_buf will be full: */
19087c478bdstevel@tonic-gate		max_start = s->block_start + max_block_size;
19097c478bdstevel@tonic-gate		if (s->strstart == 0 || (ulg)s->strstart >= max_start) {
19107c478bdstevel@tonic-gate			/*
19117c478bdstevel@tonic-gate			 * strstart == 0 is possible when wraparound
19127c478bdstevel@tonic-gate			 * on 16-bit machine
19137c478bdstevel@tonic-gate			 */
19147c478bdstevel@tonic-gate			s->lookahead = (uInt)(s->strstart - max_start);
19157c478bdstevel@tonic-gate			s->strstart = (uInt)max_start;
19167c478bdstevel@tonic-gate			FLUSH_BLOCK(s, 0);
19177c478bdstevel@tonic-gate		}
19187c478bdstevel@tonic-gate		/*
19197c478bdstevel@tonic-gate		 * Flush if we may have to slide, otherwise
19207c478bdstevel@tonic-gate		 * block_start may become negative and the data will
19217c478bdstevel@tonic-gate		 * be gone:
19227c478bdstevel@tonic-gate		 */
19237c478bdstevel@tonic-gate		if (s->strstart - (uInt)s->block_start >= MAX_DIST(s)) {
19247c478bdstevel@tonic-gate			FLUSH_BLOCK(s, 0);
19257c478bdstevel@tonic-gate		}
19267c478bdstevel@tonic-gate	}
19277c478bdstevel@tonic-gate	FLUSH_BLOCK(s, flush == Z_FINISH);
19287c478bdstevel@tonic-gate	return (flush == Z_FINISH ? finish_done : block_done);
19297c478bdstevel@tonic-gate}
19307c478bdstevel@tonic-gate
19317c478bdstevel@tonic-gate/*
19327c478bdstevel@tonic-gate * ===========================================================================
19337c478bdstevel@tonic-gate * Compress as much as possible from the input stream, return the current
19347c478bdstevel@tonic-gate * block state.
19357c478bdstevel@tonic-gate * This function does not perform lazy evaluation of matches and inserts
19367c478bdstevel@tonic-gate * new strings in the dictionary only for unmatched strings or for short
19377c478bdstevel@tonic-gate * matches. It is used only for the fast compression options.
19387c478bdstevel@tonic-gate */
19397c478bdstevel@tonic-gatelocal block_state
19407c478bdstevel@tonic-gatedeflate_fast(s, flush)
19417c478bdstevel@tonic-gate    deflate_state *s;
19427c478bdstevel@tonic-gate    int flush;
19437c478bdstevel@tonic-gate{
19447c478bdstevel@tonic-gate	IPos hash_head = NIL;	/* head of the hash chain */
19457c478bdstevel@tonic-gate	int bflush;	/* set if current block must be flushed */
19467c478bdstevel@tonic-gate
19477c478bdstevel@tonic-gate	for (;;) {
19487c478bdstevel@tonic-gate		/*
19497c478bdstevel@tonic-gate		 * Make sure that we always have enough lookahead,
19507c478bdstevel@tonic-gate		 * except at the end of the input file. We need
19517c478bdstevel@tonic-gate		 * MAX_MATCH bytes for the next match, plus MIN_MATCH
19527c478bdstevel@tonic-gate		 * bytes to insert the string following the next
19537c478bdstevel@tonic-gate		 * match.
19547c478bdstevel@tonic-gate		 */
19557c478bdstevel@tonic-gate		if (s->lookahead < MIN_LOOKAHEAD) {
19567c478bdstevel@tonic-gate			fill_window(s);
19577c478bdstevel@tonic-gate			if (s->lookahead < MIN_LOOKAHEAD &&
19587c478bdstevel@tonic-gate			    flush == Z_NO_FLUSH) {
19597c478bdstevel@tonic-gate				return (need_more);
19607c478bdstevel@tonic-gate			}
19617c478bdstevel@tonic-gate			if (s->lookahead == 0)
19627c478bdstevel@tonic-gate				break;	/* flush the current block */
19637c478bdstevel@tonic-gate		}
19647c478bdstevel@tonic-gate
19657c478bdstevel@tonic-gate		/*
19667c478bdstevel@tonic-gate		 * Insert the string window[strstart .. strstart+2] in
19677c478bdstevel@tonic-gate		 * the dictionary, and set hash_head to the head of
19687c478bdstevel@tonic-gate		 * the hash chain:
19697c478bdstevel@tonic-gate		 */
19707c478bdstevel@tonic-gate		if (s->lookahead >= MIN_MATCH) {
19717c478bdstevel@tonic-gate			INSERT_STRING(s, s->strstart, hash_head);
19727c478bdstevel@tonic-gate		}
19737c478bdstevel@tonic-gate
19747c478bdstevel@tonic-gate		/*
19757c478bdstevel@tonic-gate		 * Find the longest match, discarding those <=
19767c478bdstevel@tonic-gate		 * prev_length.  At this point we have always
19777c478bdstevel@tonic-gate		 * match_length < MIN_MATCH
19787c478bdstevel@tonic-gate		 */
19797c478bdstevel@tonic-gate		if (hash_head != NIL && s->strstart - hash_head <=
19807c478bdstevel@tonic-gate		    MAX_DIST(s)) {
19817c478bdstevel@tonic-gate			/*
19827c478bdstevel@tonic-gate			 * To simplify the code, we prevent matches
19837c478bdstevel@tonic-gate			 * with the string of window index 0 (in
19847c478bdstevel@tonic-gate			 * particular we have to avoid a match of the
19857c478bdstevel@tonic-gate			 * string with itself at the start of the
19867c478bdstevel@tonic-gate			 * input file).
19877c478bdstevel@tonic-gate			 */
19887c478bdstevel@tonic-gate			if (s->strategy != Z_HUFFMAN_ONLY) {
19897c478bdstevel@tonic-gate				s->match_length = longest_match(s, hash_head);
19907c478bdstevel@tonic-gate			}
19917c478bdstevel@tonic-gate			/* longest_match() sets match_start */
19927c478bdstevel@tonic-gate		}
19937c478bdstevel@tonic-gate		if (s->match_length >= MIN_MATCH) {
19947c478bdstevel@tonic-gate			check_match(s, s->strstart, s->match_start,
19957c478bdstevel@tonic-gate			    s->match_length);
19967c478bdstevel@tonic-gate
19977c478bdstevel@tonic-gate			_tr_tally_dist(s, s->strstart - s->match_start,
19987c478bdstevel@tonic-gate			    s->match_length - MIN_MATCH, bflush);
19997c478bdstevel@tonic-gate
20007c478bdstevel@tonic-gate			s->lookahead -= s->match_length;
20017c478bdstevel@tonic-gate
20027c478bdstevel@tonic-gate			/*
20037c478bdstevel@tonic-gate			 * Insert new strings in the hash table only
20047c478bdstevel@tonic-gate			 * if the match length is not too large. This
20057c478bdstevel@tonic-gate			 * saves time but degrades compression.
20067c478bdstevel@tonic-gate			 */
20077c478bdstevel@tonic-gate#ifndef FASTEST
20087c478bdstevel@tonic-gate			if (s->match_length <= s->max_insert_length &&
20097c478bdstevel@tonic-gate			    s->lookahead >= MIN_MATCH) {
20107c478bdstevel@tonic-gate				/* string at strstart already in hash table */
20117c478bdstevel@tonic-gate				s->match_length--;
20127c478bdstevel@tonic-gate				do {
20137c478bdstevel@tonic-gate					s->strstart++;
20147c478bdstevel@tonic-gate					INSERT_STRING(s, s->strstart,
20157c478bdstevel@tonic-gate					    hash_head);
20167c478bdstevel@tonic-gate					/*
20177c478bdstevel@tonic-gate					 * strstart never exceeds
20187c478bdstevel@tonic-gate					 * WSIZE-MAX_MATCH, so there
20197c478bdstevel@tonic-gate					 * are always MIN_MATCH bytes
20207c478bdstevel@tonic-gate					 * ahead.
20217c478bdstevel@tonic-gate					 */
20227c478bdstevel@tonic-gate				} while (--s->match_length != 0);
20237c478bdstevel@tonic-gate				s->strstart++;
20247c478bdstevel@tonic-gate			} else
20257c478bdstevel@tonic-gate#endif
20267c478bdstevel@tonic-gate			{
20277c478bdstevel@tonic-gate				s->strstart += s->match_length;
20287c478bdstevel@tonic-gate				s->match_length = 0;
20297c478bdstevel@tonic-gate				s->ins_h = s->window[s->strstart];
20307c478bdstevel@tonic-gate				UPDATE_HASH(s, s->ins_h,
20317c478bdstevel@tonic-gate				    s->window[s->strstart+1]);
20327c478bdstevel@tonic-gate#if MIN_MATCH != 3
20337c478bdstevel@tonic-gate				Call UPDATE_HASH() MIN_MATCH-3 more times
20347c478bdstevel@tonic-gate#endif
20357c478bdstevel@tonic-gate				/*
20367c478bdstevel@tonic-gate				 * If lookahead < MIN_MATCH, ins_h is
20377c478bdstevel@tonic-gate				 * garbage, but it does not matter
20387c478bdstevel@tonic-gate				 * since it will be recomputed at next
20397c478bdstevel@tonic-gate				 * deflate call.
20407c478bdstevel@tonic-gate				 */
20417c478bdstevel@tonic-gate			}
20427c478bdstevel@tonic-gate		} else {
20437c478bdstevel@tonic-gate			/* No match, output a literal byte */
20447c478bdstevel@tonic-gate			Tracevv((stderr, "%c", s->window[s->strstart]));
20457c478bdstevel@tonic-gate			_tr_tally_lit(s, s->window[s->strstart], bflush);
20467c478bdstevel@tonic-gate			s->lookahead--;
20477c478bdstevel@tonic-gate			s->strstart++;
20487c478bdstevel@tonic-gate		}
20497c478bdstevel@tonic-gate		if (bflush) FLUSH_BLOCK(s, 0);
20507c478bdstevel@tonic-gate	}
20517c478bdstevel@tonic-gate	FLUSH_BLOCK(s, flush == Z_FINISH);
20527c478bdstevel@tonic-gate	return (flush == Z_FINISH ? finish_done : block_done);
20537c478bdstevel@tonic-gate}
20547c478bdstevel@tonic-gate
20557c478bdstevel@tonic-gate/*
20567c478bdstevel@tonic-gate * ===========================================================================
20577c478bdstevel@tonic-gate * Same as above, but achieves better compression. We use a lazy
20587c478bdstevel@tonic-gate * evaluation for matches: a match is finally adopted only if there is
20597c478bdstevel@tonic-gate * no better match at the next window position.
20607c478bdstevel@tonic-gate */
20617c478bdstevel@tonic-gatelocal block_state
20627c478bdstevel@tonic-gatedeflate_slow(s, flush)
20637c478bdstevel@tonic-gate    deflate_state *s;
20647c478bdstevel@tonic-gate    int flush;
20657c478bdstevel@tonic-gate{
20667c478bdstevel@tonic-gate	IPos hash_head = NIL;	/* head of hash chain */
20677c478bdstevel@tonic-gate	int bflush;	/* set if current block must be flushed */
20687c478bdstevel@tonic-gate
20697c478bdstevel@tonic-gate	/* Process the input block. */
20707c478bdstevel@tonic-gate	for (;;) {
20717c478bdstevel@tonic-gate		/*
20727c478bdstevel@tonic-gate		 * Make sure that we always have enough lookahead,
20737c478bdstevel@tonic-gate		 * except at the end of the input file. We need
20747c478bdstevel@tonic-gate		 * MAX_MATCH bytes for the next match, plus MIN_MATCH
20757c478bdstevel@tonic-gate		 * bytes to insert the string following the next
20767c478bdstevel@tonic-gate		 * match.
20777c478bdstevel@tonic-gate		 */
20787c478bdstevel@tonic-gate		if (s->lookahead < MIN_LOOKAHEAD) {
20797c478bdstevel@tonic-gate			fill_window(s);
20807c478bdstevel@tonic-gate			if (s->lookahead < MIN_LOOKAHEAD &&
20817c478bdstevel@tonic-gate			    flush == Z_NO_FLUSH) {
20827c478bdstevel@tonic-gate				return (need_more);
20837c478bdstevel@tonic-gate			}
20847c478bdstevel@tonic-gate			/* flush the current block */
20857c478bdstevel@tonic-gate			if (s->lookahead == 0)
20867c478bdstevel@tonic-gate				break;
20877c478bdstevel@tonic-gate		}
20887c478bdstevel@tonic-gate
20897c478bdstevel@tonic-gate		/*
20907c478bdstevel@tonic-gate		 * Insert the string window[strstart .. strstart+2] in
20917c478bdstevel@tonic-gate		 * the dictionary, and set hash_head to the head of
20927c478bdstevel@tonic-gate		 * the hash chain:
20937c478bdstevel@tonic-gate		 */
20947c478bdstevel@tonic-gate		if (s->lookahead >= MIN_MATCH) {
20957c478bdstevel@tonic-gate			INSERT_STRING(s, s->strstart, hash_head);
20967c478bdstevel@tonic-gate		}
20977c478bdstevel@tonic-gate
20987c478bdstevel@tonic-gate		/*
20997c478bdstevel@tonic-gate		 * Find the longest match, discarding those <=
21007c478bdstevel@tonic-gate		 * prev_length.
21017c478bdstevel@tonic-gate		 */
21027c478bdstevel@tonic-gate		s->prev_length = s->match_length;
21037c478bdstevel@tonic-gate		s->prev_match = s->match_start;
21047c478bdstevel@tonic-gate		s->match_length = MIN_MATCH-1;
21057c478bdstevel@tonic-gate
21067c478bdstevel@tonic-gate		if (hash_head != NIL && s->prev_length < s->max_lazy_match &&
21077c478bdstevel@tonic-gate		    s->strstart - hash_head <= MAX_DIST(s)) {
21087c478bdstevel@tonic-gate			/*
21097c478bdstevel@tonic-gate			 * To simplify the code, we prevent matches
21107c478bdstevel@tonic-gate			 * with the string of window index 0 (in
21117c478bdstevel@tonic-gate			 * particular we have to avoid a match of the
21127c478bdstevel@tonic-gate			 * string with itself at the start of the
21137c478bdstevel@tonic-gate			 * input file).
21147c478bdstevel@tonic-gate			 */
21157c478bdstevel@tonic-gate			if (s->strategy != Z_HUFFMAN_ONLY) {
21167c478bdstevel@tonic-gate				s->match_length = longest_match(s, hash_head);
21177c478bdstevel@tonic-gate			}
21187c478bdstevel@tonic-gate			/* longest_match() sets match_start */
21197c478bdstevel@tonic-gate
21207c478bdstevel@tonic-gate			if (s->match_length <= 5 &&
21217c478bdstevel@tonic-gate			    (s->strategy == Z_FILTERED ||
21227c478bdstevel@tonic-gate				(s->match_length == MIN_MATCH &&
21237c478bdstevel@tonic-gate				    s->strstart - s->match_start > TOO_FAR))) {
21247c478bdstevel@tonic-gate
21257c478bdstevel@tonic-gate				/*
21267c478bdstevel@tonic-gate				 * If prev_match is also MIN_MATCH,
21277c478bdstevel@tonic-gate				 * match_start is garbage but we will
21287c478bdstevel@tonic-gate				 * ignore the current match anyway.
21297c478bdstevel@tonic-gate				 */
21307c478bdstevel@tonic-gate				s->match_length = MIN_MATCH-1;
21317c478bdstevel@tonic-gate			}
21327c478bdstevel@tonic-gate		}
21337c478bdstevel@tonic-gate		/*
21347c478bdstevel@tonic-gate		 * If there was a match at the previous step and the
21357c478bdstevel@tonic-gate		 * current match is not better, output the previous
21367c478bdstevel@tonic-gate		 * match:
21377c478bdstevel@tonic-gate		 */
21387c478bdstevel@tonic-gate		if (s->prev_length >= MIN_MATCH &&
21397c478bdstevel@tonic-gate		    s->match_length <= s->prev_length) {
21407c478bdstevel@tonic-gate			uInt max_insert = s->strstart + s->lookahead -
21417c478bdstevel@tonic-gate			    MIN_MATCH;
21427c478bdstevel@tonic-gate			/* Do not insert strings in hash table beyond this. */
21437c478bdstevel@tonic-gate
21447c478bdstevel@tonic-gate			check_match(s, s->strstart-1, s->prev_match,
21457c478bdstevel@tonic-gate			    s->prev_length);
21467c478bdstevel@tonic-gate
21477c478bdstevel@tonic-gate			_tr_tally_dist(s, s->strstart -1 - s->prev_match,
21487c478bdstevel@tonic-gate			    s->prev_length - MIN_MATCH, bflush);
21497c478bdstevel@tonic-gate
21507c478bdstevel@tonic-gate			/*
21517c478bdstevel@tonic-gate			 * Insert in hash table all strings up to the
21527c478bdstevel@tonic-gate			 * end of the match.  strstart-1 and strstart
21537c478bdstevel@tonic-gate			 * are already inserted. If there is not
21547c478bdstevel@tonic-gate			 * enough lookahead, the last two strings are
21557c478bdstevel@tonic-gate			 * not inserted in the hash table.
21567c478bdstevel@tonic-gate			 */
21577c478bdstevel@tonic-gate			s->lookahead -= s->prev_length-1;
21587c478bdstevel@tonic-gate			s->prev_length -= 2;
21597c478bdstevel@tonic-gate			do {
21607c478bdstevel@tonic-gate				if (++s->strstart <= max_insert) {
21617c478bdstevel@tonic-gate					INSERT_STRING(s, s->strstart,
21627c478bdstevel@tonic-gate					    hash_head);
21637c478bdstevel@tonic-gate				}
21647c478bdstevel@tonic-gate			} while (--s->prev_length != 0);
21657c478bdstevel@tonic-gate			s->match_available = 0;
21667c478bdstevel@tonic-gate			s->match_length = MIN_MATCH-1;
21677c478bdstevel@tonic-gate			s->strstart++;
21687c478bdstevel@tonic-gate
21697c478bdstevel@tonic-gate			if (bflush) FLUSH_BLOCK(s, 0);
21707c478bdstevel@tonic-gate
21717c478bdstevel@tonic-gate		} else if (s->match_available) {
21727c478bdstevel@tonic-gate			/*
21737c478bdstevel@tonic-gate			 * If there was no match at the previous
21747c478bdstevel@tonic-gate			 * position, output a single literal. If there
21757c478bdstevel@tonic-gate			 * was a match but the current match is
21767c478bdstevel@tonic-gate			 * longer, truncate the previous match to a
21777c478bdstevel@tonic-gate			 * single literal.
21787c478bdstevel@tonic-gate			 */
21797c478bdstevel@tonic-gate			Tracevv((stderr, "%c", s->window[s->strstart-1]));
21807c478bdstevel@tonic-gate			_tr_tally_lit(s, s->window[s->strstart-1], bflush);
21817c478bdstevel@tonic-gate			if (bflush) {
21827c478bdstevel@tonic-gate				FLUSH_BLOCK_ONLY(s, 0);
21837c478bdstevel@tonic-gate			}
21847c478bdstevel@tonic-gate			s->strstart++;
21857c478bdstevel@tonic-gate			s->lookahead--;
21867c478bdstevel@tonic-gate			if (s->strm->avail_out == 0)
21877c478bdstevel@tonic-gate				return (need_more);
21887c478bdstevel@tonic-gate		} else {
21897c478bdstevel@tonic-gate			/*
21907c478bdstevel@tonic-gate			 * There is no previous match to compare with,
21917c478bdstevel@tonic-gate			 * wait for the next step to decide.
21927c478bdstevel@tonic-gate			 */
21937c478bdstevel@tonic-gate			s->match_available = 1;
21947c478bdstevel@tonic-gate			s->strstart++;
21957c478bdstevel@tonic-gate			s->lookahead--;
21967c478bdstevel@tonic-gate		}
21977c478bdstevel@tonic-gate	}
21987c478bdstevel@tonic-gate	Assert(flush != Z_NO_FLUSH, "no flush?");
21997c478bdstevel@tonic-gate	if (s->match_available) {
22007c478bdstevel@tonic-gate		Tracevv((stderr, "%c", s->window[s->strstart-1]));
22017c478bdstevel@tonic-gate		_tr_tally_lit(s, s->window[s->strstart-1], bflush);
22027c478bdstevel@tonic-gate		s->match_available = 0;
22037c478bdstevel@tonic-gate	}
22047c478bdstevel@tonic-gate	FLUSH_BLOCK(s, flush == Z_FINISH);
22057c478bdstevel@tonic-gate	return (flush == Z_FINISH ? finish_done : block_done);
22067c478bdstevel@tonic-gate}
22077c478bdstevel@tonic-gate/* --- deflate.c */
22087c478bdstevel@tonic-gate
22097c478bdstevel@tonic-gate/* +++ trees.c */
22107c478bdstevel@tonic-gate/*
22117c478bdstevel@tonic-gate * trees.c -- output deflated data using Huffman coding
22127c478bdstevel@tonic-gate * Copyright (C) 1995-1998 Jean-loup Gailly
22137c478bdstevel@tonic-gate * For conditions of distribution and use, see copyright notice in zlib.h
22147c478bdstevel@tonic-gate */
22157c478bdstevel@tonic-gate
22167c478bdstevel@tonic-gate/*
22177c478bdstevel@tonic-gate *  ALGORITHM
22187c478bdstevel@tonic-gate *
22197c478bdstevel@tonic-gate *      The "deflation" process uses several Huffman trees. The more
22207c478bdstevel@tonic-gate *      common source values are represented by shorter bit sequences.
22217c478bdstevel@tonic-gate *
22227c478bdstevel@tonic-gate *      Each code tree is stored in a compressed form which is itself
22237c478bdstevel@tonic-gate * a Huffman encoding of the lengths of all the code strings (in
22247c478bdstevel@tonic-gate * ascending order by source values).  The actual code strings are
22257c478bdstevel@tonic-gate * reconstructed from the lengths in the inflate process, as described
22267c478bdstevel@tonic-gate * in the deflate specification.
22277c478bdstevel@tonic-gate *
22287c478bdstevel@tonic-gate *  REFERENCES
22297c478bdstevel@tonic-gate *
22307c478bdstevel@tonic-gate *      Deutsch, L.P.,"'Deflate' Compressed Data Format Specification".
22317c478bdstevel@tonic-gate *      Available in ftp.uu.net:/pub/archiving/zip/doc/deflate-1.1.doc
22327c478bdstevel@tonic-gate *
22337c478bdstevel@tonic-gate *      Storer, James A.
22347c478bdstevel@tonic-gate *          Data Compression:  Methods and Theory, pp. 49-50.
22357c478bdstevel@tonic-gate *          Computer Science Press, 1988.  ISBN 0-7167-8156-5.
22367c478bdstevel@tonic-gate *
22377c478bdstevel@tonic-gate *      Sedgewick, R.
22387c478bdstevel@tonic-gate *          Algorithms, p290.
22397c478bdstevel@tonic-gate *          Addison-Wesley, 1983. ISBN 0-201-06672-6.
22407c478bdstevel@tonic-gate */
22417c478bdstevel@tonic-gate
22427c478bdstevel@tonic-gate/* From: trees.c,v 1.11 1996/07/24 13:41:06 me Exp $ */
22437c478bdstevel@tonic-gate
22447c478bdstevel@tonic-gate/* #include "deflate.h" */
22457c478bdstevel@tonic-gate
22467c478bdstevel@tonic-gate#ifdef DEBUG_ZLIB
22477c478bdstevel@tonic-gate#include <ctype.h>
22487c478bdstevel@tonic-gate#endif
22497c478bdstevel@tonic-gate
22507c478bdstevel@tonic-gate/*
22517c478bdstevel@tonic-gate * ===========================================================================
22527c478bdstevel@tonic-gate * Constants
22537c478bdstevel@tonic-gate */
22547c478bdstevel@tonic-gate
22557c478bdstevel@tonic-gate#define	MAX_BL_BITS 7
22567c478bdstevel@tonic-gate/* Bit length codes must not exceed MAX_BL_BITS bits */
22577c478bdstevel@tonic-gate
22587c478bdstevel@tonic-gate#define	END_BLOCK 256
22597c478bdstevel@tonic-gate/* end of block literal code */
22607c478bdstevel@tonic-gate
22617c478bdstevel@tonic-gate#define	REP_3_6		16
22627c478bdstevel@tonic-gate/* repeat previous bit length 3-6 times (2 bits of repeat count) */
22637c478bdstevel@tonic-gate
22647c478bdstevel@tonic-gate#define	REPZ_3_10	17
22657c478bdstevel@tonic-gate/* repeat a zero length 3-10 times  (3 bits of repeat count) */
22667c478bdstevel@tonic-gate
22677c478bdstevel@tonic-gate#define	REPZ_11_138	18
22687c478bdstevel@tonic-gate/* repeat a zero length 11-138 times  (7 bits of repeat count) */
22697c478bdstevel@tonic-gate
22707c478bdstevel@tonic-gate/* extra bits for each length code */
22717c478bdstevel@tonic-gatelocal const int extra_lbits[LENGTH_CODES] = {
22727c478bdstevel@tonic-gate	0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 2, 2, 2, 2, 3, 3, 3, 3, 4,
22737c478bdstevel@tonic-gate	4, 4, 4, 5, 5, 5, 5, 0};
22747c478bdstevel@tonic-gate
22757c478bdstevel@tonic-gate/* extra bits for each distance code */
22767c478bdstevel@tonic-gatelocal const int extra_dbits[D_CODES] = {
22777c478bdstevel@tonic-gate	0, 0, 0, 0, 1, 1, 2, 2, 3, 3, 4, 4, 5, 5, 6, 6, 7, 7, 8, 8, 9,
22787c478bdstevel@tonic-gate	9, 10, 10, 11, 11, 12, 12, 13, 13};
22797c478bdstevel@tonic-gate
22807c478bdstevel@tonic-gate/* extra bits for each bit length code */
22817c478bdstevel@tonic-gatelocal const int extra_blbits[BL_CODES] = {
22827c478bdstevel@tonic-gate	0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 2, 3, 7};
22837c478bdstevel@tonic-gate
22847c478bdstevel@tonic-gatelocal const uch bl_order[BL_CODES] = {
22857c478bdstevel@tonic-gate	16, 17, 18, 0, 8, 7, 9, 6, 10, 5, 11, 4, 12, 3, 13, 2, 14, 1, 15};
22867c478bdstevel@tonic-gate
22877c478bdstevel@tonic-gate/*
22887c478bdstevel@tonic-gate * The lengths of the bit length codes are sent in order of decreasing
22897c478bdstevel@tonic-gate * probability, to avoid transmitting the lengths for unused bit
22907c478bdstevel@tonic-gate * length codes.
22917c478bdstevel@tonic-gate */
22927c478bdstevel@tonic-gate
22937c478bdstevel@tonic-gate#define	Buf_size (8 * 2*sizeof (char))
22947c478bdstevel@tonic-gate/*
22957c478bdstevel@tonic-gate * Number of bits used within bi_buf. (bi_buf might be implemented on
22967c478bdstevel@tonic-gate * more than 16 bits on some systems.)
22977c478bdstevel@tonic-gate */
22987c478bdstevel@tonic-gate
22997c478bdstevel@tonic-gate/*
23007c478bdstevel@tonic-gate * ===========================================================================
23017c478bdstevel@tonic-gate * Local data. These are initialized only once.
23027c478bdstevel@tonic-gate */
23037c478bdstevel@tonic-gate#define	DIST_CODE_LEN  512 /* see definition of array dist_code below */
23047c478bdstevel@tonic-gate
23057c478bdstevel@tonic-gatelocal ct_data static_ltree[L_CODES+2];
23067c478bdstevel@tonic-gate/*
23077c478bdstevel@tonic-gate * The static literal tree. Since the bit lengths are imposed, there
23087c478bdstevel@tonic-gate * is no need for the L_CODES extra codes used during heap
23097c478bdstevel@tonic-gate * construction. However The codes 286 and 287 are needed to build a
23107c478bdstevel@tonic-gate * canonical tree (see _tr_init below).
23117c478bdstevel@tonic-gate */
23127c478bdstevel@tonic-gate
23137c478bdstevel@tonic-gatelocal ct_data static_dtree[D_CODES];
23147c478bdstevel@tonic-gate/*
23157c478bdstevel@tonic-gate * The static distance tree. (Actually a trivial tree since all codes
23167c478bdstevel@tonic-gate * use 5 bits.)
23177c478bdstevel@tonic-gate */
23187c478bdstevel@tonic-gate
23197c478bdstevel@tonic-gatelocal uch _dist_code[512];
23207c478bdstevel@tonic-gate/*
23217c478bdstevel@tonic-gate * distance codes. The first 256 values correspond to the distances 3
23227c478bdstevel@tonic-gate * .. 258, the last 256 values correspond to the top 8 bits of the 15
23237c478bdstevel@tonic-gate * bit distances.
23247c478bdstevel@tonic-gate */
23257c478bdstevel@tonic-gate
23267c478bdstevel@tonic-gatelocal uch _length_code[MAX_MATCH-MIN_MATCH+1];
23277c478bdstevel@tonic-gate/* length code for each normalized match length (0 == MIN_MATCH) */
23287c478bdstevel@tonic-gate
23297c478bdstevel@tonic-gatelocal int base_length[LENGTH_CODES];
23307c478bdstevel@tonic-gate/* First normalized length for each code (0 = MIN_MATCH) */
23317c478bdstevel@tonic-gate
23327c478bdstevel@tonic-gatelocal int base_dist[D_CODES];
23337c478bdstevel@tonic-gate/* First normalized distance for each code (0 = distance of 1) */
23347c478bdstevel@tonic-gate
23357c478bdstevel@tonic-gatestruct static_tree_desc_s {
23367c478bdstevel@tonic-gate	const ct_data *static_tree;	/* static tree or NULL */
23377c478bdstevel@tonic-gate	const intf    *extra_bits;	/* extra bits for each code or NULL */
23387c478bdstevel@tonic-gate	int	extra_base;	/* base index for extra_bits */
23397c478bdstevel@tonic-gate	int	elems;	/* max number of elements in the tree */
23407c478bdstevel@tonic-gate	int	max_length;	/* max bit length for the codes */
23417c478bdstevel@tonic-gate};
23427c478bdstevel@tonic-gate
23437c478bdstevel@tonic-gatelocal static_tree_desc  static_l_desc = {
23447c478bdstevel@tonic-gate	static_ltree, extra_lbits, LITERALS+1,	L_CODES, MAX_BITS};
23457c478bdstevel@tonic-gate
23467c478bdstevel@tonic-gatelocal static_tree_desc  static_d_desc = {
23477c478bdstevel@tonic-gate	static_dtree, extra_dbits, 0,		D_CODES, MAX_BITS};
23487c478bdstevel@tonic-gate
23497c478bdstevel@tonic-gatelocal static_tree_desc  static_bl_desc = {
23507c478bdstevel@tonic-gate	(const ct_data *)0, extra_blbits, 0,		BL_CODES, MAX_BL_BITS};
23517c478bdstevel@tonic-gate
23527c478bdstevel@tonic-gate/*
23537c478bdstevel@tonic-gate * ===========================================================================
23547c478bdstevel@tonic-gate * Local (static) routines in this file.
23557c478bdstevel@tonic-gate */
23567c478bdstevel@tonic-gate
23577c478bdstevel@tonic-gatelocal void tr_static_init OF((void));
23587c478bdstevel@tonic-gatelocal void init_block	OF((deflate_state *s));
23597c478bdstevel@tonic-gatelocal void pqdownheap	OF((deflate_state *s, ct_data *tree, int k));
23607c478bdstevel@tonic-gatelocal void gen_bitlen	OF((deflate_state *s, tree_desc *desc));
23617c478bdstevel@tonic-gatelocal void gen_codes	OF((ct_data *tree, int max_code, ushf *bl_count));
23627c478bdstevel@tonic-gatelocal void build_tree	OF((deflate_state *s, tree_desc *desc));
23637c478bdstevel@tonic-gatelocal void scan_tree	OF((deflate_state *s, ct_data *tree, int max_code));
23647c478bdstevel@tonic-gatelocal void send_tree	OF((deflate_state *s, ct_data *tree, int max_code));
23657c478bdstevel@tonic-gatelocal int  build_bl_tree	OF((deflate_state *s));
23667c478bdstevel@tonic-gatelocal void send_all_trees	OF((deflate_state *s, int lcodes, int dcodes,
23677c478bdstevel@tonic-gate    int blcodes));
23687c478bdstevel@tonic-gatelocal void compress_block OF((deflate_state *s, ct_data *ltree,
23697c478bdstevel@tonic-gate    ct_data *dtree));
23707c478bdstevel@tonic-gatelocal void set_data_type	OF((deflate_state *s));
23717c478bdstevel@tonic-gatelocal unsigned bi_reverse	OF((unsigned value, int length));
23727c478bdstevel@tonic-gatelocal void bi_windup	OF((deflate_state *s));
23737c478bdstevel@tonic-gatelocal void bi_flush	OF((deflate_state *s));
23747c478bdstevel@tonic-gatelocal void copy_block	OF((deflate_state *s, charf *buf, unsigned len,
23757c478bdstevel@tonic-gate    int header));
23767c478bdstevel@tonic-gate
23777c478bdstevel@tonic-gate#ifndef DEBUG_ZLIB
23787c478bdstevel@tonic-gate#define	send_code(s, c, tree) send_bits(s, tree[c].Code, tree[c].Len)
23797c478bdstevel@tonic-gate/* Send a code of the given tree. c and tree must not have side effects */
23807c478bdstevel@tonic-gate
23817c478bdstevel@tonic-gate#else /* DEBUG_ZLIB */
23827c478bdstevel@tonic-gate#define	send_code(s, c, tree) \
23837c478bdstevel@tonic-gate	{ if (z_verbose > 2) fprintf(stderr, "\ncd %3d ", (c)); \
23847c478bdstevel@tonic-gate	send_bits(s, tree[c].Code, tree[c].Len); }
23857c478bdstevel@tonic-gate#endif
23867c478bdstevel@tonic-gate
23877c478bdstevel@tonic-gate/*
23887c478bdstevel@tonic-gate * ===========================================================================
23897c478bdstevel@tonic-gate * Output a short LSB first on the stream.
23907c478bdstevel@tonic-gate * IN assertion: there is enough room in pendingBuf.
23917c478bdstevel@tonic-gate */
23927c478bdstevel@tonic-gate#define	put_short(s, w) { \
23937c478bdstevel@tonic-gate	put_byte(s, (uch)((w) & 0xff)); \
23947c478bdstevel@tonic-gate	put_byte(s, (uch)((ush)(w) >> 8)); \
23957c478bdstevel@tonic-gate}
23967c478bdstevel@tonic-gate
23977c478bdstevel@tonic-gate/*
23987c478bdstevel@tonic-gate * ===========================================================================
23997c478bdstevel@tonic-gate * Send a value on a given number of bits.
24007c478bdstevel@tonic-gate * IN assertion: length <= 16 and value fits in length bits.
24017c478bdstevel@tonic-gate */
24027c478bdstevel@tonic-gate#ifdef DEBUG_ZLIB
24037c478bdstevel@tonic-gatelocal void send_bits	OF((deflate_state *s, int value, int length));
24047c478bdstevel@tonic-gate
24057c478bdstevel@tonic-gatelocal void
24067c478bdstevel@tonic-gatesend_bits(s, value, length)
24077c478bdstevel@tonic-gate    deflate_state *s;
24087c478bdstevel@tonic-gate    int value;	/* value to send */
24097c478bdstevel@tonic-gate    int length;	/* number of bits */
24107c478bdstevel@tonic-gate{
24117c478bdstevel@tonic-gate	Tracevv((stderr, " l %2d v %4x ", length, value));
24127c478bdstevel@tonic-gate	Assert(length > 0 && length <= 15, "invalid length");
24137c478bdstevel@tonic-gate	s->bits_sent += (ulg)length;
24147c478bdstevel@tonic-gate
24157c478bdstevel@tonic-gate	/*
24167c478bdstevel@tonic-gate	 * If not enough room in bi_buf, use (valid) bits from bi_buf
24177c478bdstevel@tonic-gate	 * and (16 - bi_valid) bits from value, leaving (width -
24187c478bdstevel@tonic-gate	 * (16-bi_valid)) unused bits in value.
24197c478bdstevel@tonic-gate	 */
24207c478bdstevel@tonic-gate	if (s->bi_valid > (int)Buf_size - length) {
24217c478bdstevel@tonic-gate		s->bi_buf |= (value << s->bi_valid);
24227c478bdstevel@tonic-gate		put_short(s, s->bi_buf);
24237c478bdstevel@tonic-gate		s->bi_buf = (ush)value >> (Buf_size - s->bi_valid);
24247c478bdstevel@tonic-gate		s->bi_valid += length - Buf_size;
24257c478bdstevel@tonic-gate	} else {
24267c478bdstevel@tonic-gate		s->bi_buf |= value << s->bi_valid;
24277c478bdstevel@tonic-gate		s->bi_valid += length;
24287c478bdstevel@tonic-gate	}
24297c478bdstevel@tonic-gate}
24307c478bdstevel@tonic-gate#else /* !DEBUG_ZLIB */
24317c478bdstevel@tonic-gate
24327c478bdstevel@tonic-gate#define	send_bits(s, value, length) \
24337c478bdstevel@tonic-gate{	int len = length; \
24347c478bdstevel@tonic-gate	if (s->bi_valid > (int)Buf_size - len) {\
24357c478bdstevel@tonic-gate		int val = value; \
24367c478bdstevel@tonic-gate		s->bi_buf |= (val << s->bi_valid); \
24377c478bdstevel@tonic-gate		put_short(s, s->bi_buf); \
24387c478bdstevel@tonic-gate		s->bi_buf = (ush)val >> (Buf_size - s->bi_valid); \
24397c478bdstevel@tonic-gate		s->bi_valid += len - Buf_size; \
24407c478bdstevel@tonic-gate	} else {\
24417c478bdstevel@tonic-gate		s->bi_buf |= (value) << s->bi_valid; \
24427c478bdstevel@tonic-gate		s->bi_valid += len; \
24437c478bdstevel@tonic-gate	}\
24447c478bdstevel@tonic-gate}
24457c478bdstevel@tonic-gate#endif /* DEBUG_ZLIB */
24467c478bdstevel@tonic-gate
24477c478bdstevel@tonic-gate
24487c478bdstevel@tonic-gate#define	MAX(a, b) (a >= b ? a : b)
24497c478bdstevel@tonic-gate/* the arguments must not have side effects */
24507c478bdstevel@tonic-gate
24517c478bdstevel@tonic-gate/*
24527c478bdstevel@tonic-gate * ===========================================================================
24537c478bdstevel@tonic-gate * Initialize the various 'constant' tables. In a multi-threaded environment,
24547c478bdstevel@tonic-gate * this function may be called by two threads concurrently, but this is
24557c478bdstevel@tonic-gate * harmless since both invocations do exactly the same thing.
24567c478bdstevel@tonic-gate */
24577c478bdstevel@tonic-gatelocal void
24587c478bdstevel@tonic-gatetr_static_init()
24597c478bdstevel@tonic-gate{
24607c478bdstevel@tonic-gate	static int static_init_done = 0;
24617c478bdstevel@tonic-gate	int n;	/* iterates over tree elements */
24627c478bdstevel@tonic-gate	int bits;	/* bit counter */
24637c478bdstevel@tonic-gate	int length;	/* length value */
24647c478bdstevel@tonic-gate	int code;	/* code value */
24657c478bdstevel@tonic-gate	int dist;	/* distance index */
24667c478bdstevel@tonic-gate	ush bl_count[MAX_BITS+1];
24677c478bdstevel@tonic-gate	/* number of codes at each bit length for an optimal tree */
24687c478bdstevel@tonic-gate
24697c478bdstevel@tonic-gate	if (static_init_done)
24707c478bdstevel@tonic-gate		return;
24717c478bdstevel@tonic-gate
24727c478bdstevel@tonic-gate	/* For some embedded targets, global variables are not initialized: */
24737c478bdstevel@tonic-gate	static_l_desc.static_tree = static_ltree;
24747c478bdstevel@tonic-gate	static_l_desc.extra_bits = extra_lbits;
24757c478bdstevel@tonic-gate	static_d_desc.static_tree = static_dtree;
24767c478bdstevel@tonic-gate	static_d_desc.extra_bits = extra_dbits;
24777c478bdstevel@tonic-gate	static_bl_desc.extra_bits = extra_blbits;
24787c478bdstevel@tonic-gate
24797c478bdstevel@tonic-gate	/* Initialize the mapping length (0..255) -> length code (0..28) */
24807c478bdstevel@tonic-gate	length = 0;
24817c478bdstevel@tonic-gate	for (code = 0; code < LENGTH_CODES-1; code++) {
24827c478bdstevel@tonic-gate		base_length[code] = length;
24837c478bdstevel@tonic-gate		for (n = 0; n < (1<<extra_lbits[code]); n++) {
24847c478bdstevel@tonic-gate			_length_code[length++] = (uch)code;
24857c478bdstevel@tonic-gate		}
24867c478bdstevel@tonic-gate	}
24877c478bdstevel@tonic-gate	Assert(length == 256, "tr_static_init: length != 256");
24887c478bdstevel@tonic-gate	/*
24897c478bdstevel@tonic-gate	 * Note that the length 255 (match length 258) can be
24907c478bdstevel@tonic-gate	 * represented in two different ways: code 284 + 5 bits or
24917c478bdstevel@tonic-gate	 * code 285, so we overwrite _length_code[255] to use the best
24927c478bdstevel@tonic-gate	 * encoding:
24937c478bdstevel@tonic-gate	 */
24947c478bdstevel@tonic-gate	_length_code[length-1] = (uch)code;
24957c478bdstevel@tonic-gate
24967c478bdstevel@tonic-gate	/* Initialize the mapping dist (0..32K) -> dist code (0..29) */
24977c478bdstevel@tonic-gate	dist = 0;
24987c478bdstevel@tonic-gate	for (code = 0; code < 16; code++) {
24997c478bdstevel@tonic-gate		base_dist[code] = dist;
25007c478bdstevel@tonic-gate		for (n = 0; n < (1<<extra_dbits[code]); n++) {
25017c478bdstevel@tonic-gate			_dist_code[dist++] = (uch)code;
25027c478bdstevel@tonic-gate		}
25037c478bdstevel@tonic-gate	}
25047c478bdstevel@tonic-gate	Assert(dist == 256, "tr_static_init: dist != 256");
25057c478bdstevel@tonic-gate	dist >>= 7;	/* from now on, all distances are divided by 128 */
25067c478bdstevel@tonic-gate	for (; code < D_CODES; code++) {
25077c478bdstevel@tonic-gate		base_dist[code] = dist << 7;
25087c478bdstevel@tonic-gate		for (n = 0; n < (1<<(extra_dbits[code]-7)); n++) {
25097c478bdstevel@tonic-gate			_dist_code[256 + dist++] = (uch)code;
25107c478bdstevel@tonic-gate		}
25117c478bdstevel@tonic-gate	}
25127c478bdstevel@tonic-gate	Assert(dist == 256, "tr_static_init: 256+dist != 512");
25137c478bdstevel@tonic-gate
25147c478bdstevel@tonic-gate	/* Construct the codes of the static literal tree */
25157c478bdstevel@tonic-gate	for (bits = 0; bits <= MAX_BITS; bits++) bl_count[bits] = 0;
25167c478bdstevel@tonic-gate	n = 0;
25177c478bdstevel@tonic-gate	while (n <= 143) static_ltree[n++].Len = 8, bl_count[8]++;
25187c478bdstevel@tonic-gate	while (n <= 255) static_ltree[n++].Len = 9, bl_count[9]++;
25197c478bdstevel@tonic-gate	while (n <= 279) static_ltree[n++].Len = 7, bl_count[7]++;
25207c478bdstevel@tonic-gate	while (n <= 287) static_ltree[n++].Len = 8, bl_count[8]++;
25217c478bdstevel@tonic-gate	/*
25227c478bdstevel@tonic-gate	 * Codes 286 and 287 do not exist, but we must include them in the
25237c478bdstevel@tonic-gate	 * tree construction to get a canonical Huffman tree (longest code
25247c478bdstevel@tonic-gate	 * all ones)
25257c478bdstevel@tonic-gate	 */
25267c478bdstevel@tonic-gate	gen_codes((ct_data *)static_ltree, L_CODES+1, bl_count);
25277c478bdstevel@tonic-gate
25287c478bdstevel@tonic-gate	/* The static distance tree is trivial: */
25297c478bdstevel@tonic-gate	for (n = 0; n < D_CODES; n++) {
25307c478bdstevel@tonic-gate		static_dtree[n].Len = 5;
25317c478bdstevel@tonic-gate		static_dtree[n].Code = bi_reverse((unsigned)n, 5);
25327c478bdstevel@tonic-gate	}
25337c478bdstevel@tonic-gate	static_init_done = 1;
25347c478bdstevel@tonic-gate}
25357c478bdstevel@tonic-gate
25367c478bdstevel@tonic-gate/*
25377c478bdstevel@tonic-gate * ===========================================================================
25387c478bdstevel@tonic-gate * Initialize the tree data structures for a new zlib stream.
25397c478bdstevel@tonic-gate */
25407c478bdstevel@tonic-gatevoid
25417c478bdstevel@tonic-gate_tr_init(s)
25427c478bdstevel@tonic-gate    deflate_state *s;
25437c478bdstevel@tonic-gate{
25447c478bdstevel@tonic-gate	tr_static_init();
25457c478bdstevel@tonic-gate
25467c478bdstevel@tonic-gate	s->l_desc.dyn_tree = s->dyn_ltree;
25477c478bdstevel@tonic-gate	s->l_desc.stat_desc = &static_l_desc;
25487c478bdstevel@tonic-gate
25497c478bdstevel@tonic-gate	s->d_desc.dyn_tree = s->dyn_dtree;
25507c478bdstevel@tonic-gate	s->d_desc.stat_desc = &static_d_desc;
25517c478bdstevel@tonic-gate
25527c478bdstevel@tonic-gate	s->bl_desc.dyn_tree = s->bl_tree;
25537c478bdstevel@tonic-gate	s->bl_desc.stat_desc = &static_bl_desc;
25547c478bdstevel@tonic-gate
25557c478bdstevel@tonic-gate	s->bi_buf = 0;
25567c478bdstevel@tonic-gate	s->bi_valid = 0;
25577c478bdstevel@tonic-gate	s->last_eob_len = 8;	/* enough lookahead for inflate */
25587c478bdstevel@tonic-gate	s->compressed_len = 0L;		/* PPP */
25597c478bdstevel@tonic-gate#ifdef DEBUG_ZLIB
25607c478bdstevel@tonic-gate	s->bits_sent = 0L;
25617c478bdstevel@tonic-gate#endif
25627c478bdstevel@tonic-gate
25637c478bdstevel@tonic-gate	/* Initialize the first block of the first file: */
25647c478bdstevel@tonic-gate	init_block(s);
25657c478bdstevel@tonic-gate}
25667c478bdstevel@tonic-gate
25677c478bdstevel@tonic-gate/*
25687c478bdstevel@tonic-gate * ===========================================================================
25697c478bdstevel@tonic-gate * Initialize a new block.
25707c478bdstevel@tonic-gate */
25717c478bdstevel@tonic-gatelocal void
25727c478bdstevel@tonic-gateinit_block(s)
25737c478bdstevel@tonic-gate    deflate_state *s;
25747c478bdstevel@tonic-gate{
25757c478bdstevel@tonic-gate	int n;	/* iterates over tree elements */
25767c478bdstevel@tonic-gate
25777c478bdstevel@tonic-gate	/* Initialize the trees. */
25787c478bdstevel@tonic-gate	for (n = 0; n < L_CODES;  n++) s->dyn_ltree[n].Freq = 0;
25797c478bdstevel@tonic-gate	for (n = 0; n < D_CODES;  n++) s->dyn_dtree[n].Freq = 0;
25807c478bdstevel@tonic-gate	for (n = 0; n < BL_CODES; n++) s->bl_tree[n].Freq = 0;
25817c478bdstevel@tonic-gate
25827c478bdstevel@tonic-gate	s->dyn_ltree[END_BLOCK].Freq = 1;
25837c478bdstevel@tonic-gate	s->opt_len = s->static_len = 0L;
25847c478bdstevel@tonic-gate	s->last_lit = s->matches = 0;
25857c478bdstevel@tonic-gate}
25867c478bdstevel@tonic-gate
25877c478bdstevel@tonic-gate#define	SMALLEST 1
25887c478bdstevel@tonic-gate/* Index within the heap array of least frequent node in the Huffman tree */
25897c478bdstevel@tonic-gate
25907c478bdstevel@tonic-gate
25917c478bdstevel@tonic-gate/*
25927c478bdstevel@tonic-gate * ===========================================================================
25937c478bdstevel@tonic-gate * Remove the smallest element from the heap and recreate the heap with
25947c478bdstevel@tonic-gate * one less element. Updates heap and heap_len.
25957c478bdstevel@tonic-gate */
25967c478bdstevel@tonic-gate#define	pqremove(s, tree, top) \
25977c478bdstevel@tonic-gate{\
25987c478bdstevel@tonic-gate	top = s->heap[SMALLEST]; \
25997c478bdstevel@tonic-gate	s->heap[SMALLEST] = s->heap[s->heap_len--]; \
26007c478bdstevel@tonic-gate	pqdownheap(s, tree, SMALLEST); \
26017c478bdstevel@tonic-gate}
26027c478bdstevel@tonic-gate
26037c478bdstevel@tonic-gate/*
26047c478bdstevel@tonic-gate * ===========================================================================
26057c478bdstevel@tonic-gate * Compares to subtrees, using the tree depth as tie breaker when
26067c478bdstevel@tonic-gate * the subtrees have equal frequency. This minimizes the worst case length.
26077c478bdstevel@tonic-gate */
26087c478bdstevel@tonic-gate#define	smaller(tree, n, m, depth) \
26097c478bdstevel@tonic-gate	(tree[n].Freq < tree[m].Freq || \
26107c478bdstevel@tonic-gate	(tree[n].Freq == tree[m].Freq && depth[n] <= depth[m]))
26117c478bdstevel@tonic-gate/*
26127c478bdstevel@tonic-gate * ===========================================================================
26137c478bdstevel@tonic-gate * Restore the heap property by moving down the tree starting at node k,
26147c478bdstevel@tonic-gate * exchanging a node with the smallest of its two sons if necessary, stopping
26157c478bdstevel@tonic-gate * when the heap property is re-established (each father smaller than its
26167c478bdstevel@tonic-gate * two sons).
26177c478bdstevel@tonic-gate */
26187c478bdstevel@tonic-gatelocal void
26197c478bdstevel@tonic-gatepqdownheap(s, tree, k)
26207c478bdstevel@tonic-gate    deflate_state *s;
26217c478bdstevel@tonic-gate    ct_data *tree;	/* the tree to restore */
26227c478bdstevel@tonic-gate    int k;	/* node to move down */
26237c478bdstevel@tonic-gate{
26247c478bdstevel@tonic-gate	int v = s->heap[k];
26257c478bdstevel@tonic-gate	int j = k << 1;	/* left son of k */
26267c478bdstevel@tonic-gate	while (j <= s->heap_len) {
26277c478bdstevel@tonic-gate		/* Set j to the smallest of the two sons: */
26287c478bdstevel@tonic-gate		if (j < s->heap_len &&
26297c478bdstevel@tonic-gate		    smaller(tree, s->heap[j+1], s->heap[j], s->depth)) {
26307c478bdstevel@tonic-gate			j++;
26317c478bdstevel@tonic-gate		}
26327c478bdstevel@tonic-gate		/* Exit if v is smaller than both sons */
26337c478bdstevel@tonic-gate		if (smaller(tree, v, s->heap[j], s->depth)) break;
26347c478bdstevel@tonic-gate
26357c478bdstevel@tonic-gate		/* Exchange v with the smallest son */
26367c478bdstevel@tonic-gate		s->heap[k] = s->heap[j];  k = j;
26377c478bdstevel@tonic-gate
26387c478bdstevel@tonic-gate		/* And continue down the tree, setting j to the left son of k */
26397c478bdstevel@tonic-gate		j <<= 1;
26407c478bdstevel@tonic-gate	}
26417c478bdstevel@tonic-gate	s->heap[k] = v;
26427c478bdstevel@tonic-gate}
26437c478bdstevel@tonic-gate
26447c478bdstevel@tonic-gate/*
26457c478bdstevel@tonic-gate * ===========================================================================
26467c478bdstevel@tonic-gate * Compute the optimal bit lengths for a tree and update the total bit length
26477c478bdstevel@tonic-gate * for the current block.
26487c478bdstevel@tonic-gate * IN assertion: the fields freq and dad are set, heap[heap_max] and
26497c478bdstevel@tonic-gate *    above are the tree nodes sorted by increasing frequency.
26507c478bdstevel@tonic-gate * OUT assertions: the field len is set to the optimal bit length, the
26517c478bdstevel@tonic-gate *     array bl_count contains the frequencies for each bit length.
26527c478bdstevel@tonic-gate *     The length opt_len is updated; static_len is also updated if stree is
26537c478bdstevel@tonic-gate *     not null.
26547c478bdstevel@tonic-gate */
26557c478bdstevel@tonic-gatelocal void
26567c478bdstevel@tonic-gategen_bitlen(s, desc)
26577c478bdstevel@tonic-gate    deflate_state *s;
26587c478bdstevel@tonic-gate    tree_desc *desc;	/* the tree descriptor */
26597c478bdstevel@tonic-gate{
26607c478bdstevel@tonic-gate	ct_data *tree  = desc->dyn_tree;
26617c478bdstevel@tonic-gate	int max_code   = desc->max_code;
26627c478bdstevel@tonic-gate	const ct_data *stree = desc->stat_desc->static_tree;
26637c478bdstevel@tonic-gate	const intf *extra    = desc->stat_desc->extra_bits;
26647c478bdstevel@tonic-gate	int base	= desc->stat_desc->extra_base;
26657c478bdstevel@tonic-gate	int max_length = desc->stat_desc->max_length;
26667c478bdstevel@tonic-gate	int h;	/* heap index */
26677c478bdstevel@tonic-gate	int n, m;	/* iterate over the tree elements */
26687c478bdstevel@tonic-gate	int bits;	/* bit length */
26697c478bdstevel@tonic-gate	int xbits;	/* extra bits */
26707c478bdstevel@tonic-gate	ush f;	/* frequency */
26717c478bdstevel@tonic-gate	/* number of elements with bit length too large */
26727c478bdstevel@tonic-gate	int overflow = 0;
26737c478bdstevel@tonic-gate
26747c478bdstevel@tonic-gate	for (bits = 0; bits <= MAX_BITS; bits++) s->bl_count[bits] = 0;
26757c478bdstevel@tonic-gate
26767c478bdstevel@tonic-gate	/*
26777c478bdstevel@tonic-gate	 * In a first pass, compute the optimal bit lengths (which may
26787c478bdstevel@tonic-gate	 * overflow in the case of the bit length tree).
26797c478bdstevel@tonic-gate	 */
26807c478bdstevel@tonic-gate	tree[s->heap[s->heap_max]].Len = 0;	/* root of the heap */
26817c478bdstevel@tonic-gate
26827c478bdstevel@tonic-gate	for (h = s->heap_max+1; h < HEAP_SIZE; h++) {
26837c478bdstevel@tonic-gate		n = s->heap[h];
26847c478bdstevel@tonic-gate		bits = tree[tree[n].Dad].Len + 1;
26857c478bdstevel@tonic-gate		if (bits > max_length) bits = max_length, overflow++;
26867c478bdstevel@tonic-gate		tree[n].Len = (ush)bits;
26877c478bdstevel@tonic-gate		/* We overwrite tree[n].Dad which is no longer needed */
26887c478bdstevel@tonic-gate
26897c478bdstevel@tonic-gate		if (n > max_code) continue;	/* not a leaf node */
26907c478bdstevel@tonic-gate
26917c478bdstevel@tonic-gate		s->bl_count[bits]++;
26927c478bdstevel@tonic-gate		xbits = 0;
26937c478bdstevel@tonic-gate		if (n >= base) xbits = extra[n-base];
26947c478bdstevel@tonic-gate		f = tree[n].Freq;
26957c478bdstevel@tonic-gate		s->opt_len += (ulg)f * (bits + xbits);
26967c478bdstevel@tonic-gate		if (stree) s->static_len += (ulg)f * (stree[n].Len + xbits);
26977c478bdstevel@tonic-gate	}
26987c478bdstevel@tonic-gate	if (overflow == 0)
26997c478bdstevel@tonic-gate		return;
27007c478bdstevel@tonic-gate
27017c478bdstevel@tonic-gate	Trace((stderr, "\nbit length overflow\n"));
27027c478bdstevel@tonic-gate	/* This happens for example on obj2 and pic of the Calgary corpus */
27037c478bdstevel@tonic-gate
27047c478bdstevel@tonic-gate	/* Find the first bit length which could increase: */
27057c478bdstevel@tonic-gate	do {
27067c478bdstevel@tonic-gate		bits = max_length-1;
27077c478bdstevel@tonic-gate		while (s->bl_count[bits] == 0) bits--;
27087c478bdstevel@tonic-gate		s->bl_count[bits]--;	/* move one leaf down the tree */
27097c478bdstevel@tonic-gate		/* move one overflow item as its brother */
27107c478bdstevel@tonic-gate		s->bl_count[bits+1] += 2;
27117c478bdstevel@tonic-gate		s->bl_count[max_length]--;
27127c478bdstevel@tonic-gate		/*
27137c478bdstevel@tonic-gate		 * The brother of the overflow item also moves one
27147c478bdstevel@tonic-gate		 * step up, but this does not affect
27157c478bdstevel@tonic-gate		 * bl_count[max_length]
27167c478bdstevel@tonic-gate		 */
27177c478bdstevel@tonic-gate		overflow -= 2;
27187c478bdstevel@tonic-gate	} while (overflow > 0);
27197c478bdstevel@tonic-gate
27207c478bdstevel@tonic-gate	/*
27217c478bdstevel@tonic-gate	 * Now recompute all bit lengths, scanning in increasing
27227c478bdstevel@tonic-gate	 * frequency.  h is still equal to HEAP_SIZE. (It is simpler
27237c478bdstevel@tonic-gate	 * to reconstruct all lengths instead of fixing only the wrong
27247c478bdstevel@tonic-gate	 * ones. This idea is taken from 'ar' written by Haruhiko
27257c478bdstevel@tonic-gate	 * Okumura.)
27267c478bdstevel@tonic-gate	 */
27277c478bdstevel@tonic-gate	for (bits = max_length; bits != 0; bits--) {
27287c478bdstevel@tonic-gate		n = s->bl_count[bits];
27297c478bdstevel@tonic-gate		while (n != 0) {
27307c478bdstevel@tonic-gate			m = s->heap[--h];
27317c478bdstevel@tonic-gate			if (m > max_code) continue;
27327c478bdstevel@tonic-gate			if (tree[m].Len != (unsigned)bits) {
27337c478bdstevel@tonic-gate				Trace((stderr, "code %d bits %d->%d\n", m,
27347c478bdstevel@tonic-gate				    tree[m].Len, bits));
27357c478bdstevel@tonic-gate				s->opt_len += ((long)bits - (long)tree[m].Len)
27367c478bdstevel@tonic-gate				    *(long)tree[m].Freq;
27377c478bdstevel@tonic-gate				tree[m].Len = (ush)bits;
27387c478bdstevel@tonic-gate			}
27397c478bdstevel@tonic-gate			n--;
27407c478bdstevel@tonic-gate		}
27417c478bdstevel@tonic-gate	}
27427c478bdstevel@tonic-gate}
27437c478bdstevel@tonic-gate
27447c478bdstevel@tonic-gate/*
27457c478bdstevel@tonic-gate * ===========================================================================
27467c478bdstevel@tonic-gate * Generate the codes for a given tree and bit counts (which need not be
27477c478bdstevel@tonic-gate * optimal).
27487c478bdstevel@tonic-gate * IN assertion: the array bl_count contains the bit length statistics for
27497c478bdstevel@tonic-gate * the given tree and the field len is set for all tree elements.
27507c478bdstevel@tonic-gate * OUT assertion: the field code is set for all tree elements of non
27517c478bdstevel@tonic-gate *     zero code length.
27527c478bdstevel@tonic-gate */
27537c478bdstevel@tonic-gatelocal void
27547c478bdstevel@tonic-gategen_codes(tree, max_code, bl_count)
27557c478bdstevel@tonic-gate    ct_data *tree;	/* the tree to decorate */
27567c478bdstevel@tonic-gate    int max_code;	/* largest code with non zero frequency */
27577c478bdstevel@tonic-gate    ushf *bl_count;	/* number of codes at each bit length */
27587c478bdstevel@tonic-gate{
27597c478bdstevel@tonic-gate	/* next code value for each bit length */
27607c478bdstevel@tonic-gate	ush next_code[MAX_BITS+1];
27617c478bdstevel@tonic-gate	ush code = 0;	/* running code value */
2762