17c478bd9Sstevel@tonic-gate /*
27c478bd9Sstevel@tonic-gate  * This file is derived from various .h and .c files from the zlib-0.95
37c478bd9Sstevel@tonic-gate  * distribution by Jean-loup Gailly and Mark Adler, with some additions
47c478bd9Sstevel@tonic-gate  * by Paul Mackerras to aid in implementing Deflate compression and
57c478bd9Sstevel@tonic-gate  * decompression for PPP packets.  See zlib.h for conditions of
67c478bd9Sstevel@tonic-gate  * distribution and use.
77c478bd9Sstevel@tonic-gate  *
87c478bd9Sstevel@tonic-gate  * Changes that have been made include:
97c478bd9Sstevel@tonic-gate  * - changed functions not used outside this file to "local"
107c478bd9Sstevel@tonic-gate  * - added minCompression parameter to deflateInit2
117c478bd9Sstevel@tonic-gate  * - added Z_PACKET_FLUSH (see zlib.h for details)
127c478bd9Sstevel@tonic-gate  * - added inflateIncomp
137c478bd9Sstevel@tonic-gate  *
147c478bd9Sstevel@tonic-gate  * $Id: zlib.c,v 1.2 1999/04/01 07:26:30 paulus Exp $
157c478bd9Sstevel@tonic-gate  */
167c478bd9Sstevel@tonic-gate 
177c478bd9Sstevel@tonic-gate 
187c478bd9Sstevel@tonic-gate /*+++++*/
197c478bd9Sstevel@tonic-gate /* zutil.h -- internal interface and configuration of the compression library
207c478bd9Sstevel@tonic-gate  * Copyright (C) 1995 Jean-loup Gailly.
217c478bd9Sstevel@tonic-gate  * For conditions of distribution and use, see copyright notice in zlib.h
227c478bd9Sstevel@tonic-gate  */
237c478bd9Sstevel@tonic-gate 
247c478bd9Sstevel@tonic-gate /* WARNING: this file should *not* be used by applications. It is
257c478bd9Sstevel@tonic-gate    part of the implementation of the compression library and is
267c478bd9Sstevel@tonic-gate    subject to change. Applications should only use zlib.h.
277c478bd9Sstevel@tonic-gate  */
287c478bd9Sstevel@tonic-gate 
297c478bd9Sstevel@tonic-gate /* From: zutil.h,v 1.9 1995/05/03 17:27:12 jloup Exp */
307c478bd9Sstevel@tonic-gate 
317c478bd9Sstevel@tonic-gate #define _Z_UTIL_H
327c478bd9Sstevel@tonic-gate 
337c478bd9Sstevel@tonic-gate #include "zlib.h"
347c478bd9Sstevel@tonic-gate 
357c478bd9Sstevel@tonic-gate #ifdef STDC
367c478bd9Sstevel@tonic-gate #  include <string.h>
377c478bd9Sstevel@tonic-gate #endif
387c478bd9Sstevel@tonic-gate 
397c478bd9Sstevel@tonic-gate #ifndef local
407c478bd9Sstevel@tonic-gate #  define local static
417c478bd9Sstevel@tonic-gate #endif
427c478bd9Sstevel@tonic-gate /* compile with -Dlocal if your debugger can't find static symbols */
437c478bd9Sstevel@tonic-gate 
447c478bd9Sstevel@tonic-gate #define FAR
457c478bd9Sstevel@tonic-gate 
467c478bd9Sstevel@tonic-gate typedef unsigned char  uch;
477c478bd9Sstevel@tonic-gate typedef uch FAR uchf;
487c478bd9Sstevel@tonic-gate typedef unsigned short ush;
497c478bd9Sstevel@tonic-gate typedef ush FAR ushf;
507c478bd9Sstevel@tonic-gate typedef unsigned long  ulg;
517c478bd9Sstevel@tonic-gate 
527c478bd9Sstevel@tonic-gate extern char *z_errmsg[]; /* indexed by 1-zlib_error */
537c478bd9Sstevel@tonic-gate 
547c478bd9Sstevel@tonic-gate #define ERR_RETURN(strm,err) return (strm->msg=z_errmsg[1-err], err)
557c478bd9Sstevel@tonic-gate /* To be used only when the state is known to be valid */
567c478bd9Sstevel@tonic-gate 
577c478bd9Sstevel@tonic-gate #ifndef NULL
587c478bd9Sstevel@tonic-gate #define NULL	((void *) 0)
597c478bd9Sstevel@tonic-gate #endif
607c478bd9Sstevel@tonic-gate 
617c478bd9Sstevel@tonic-gate         /* common constants */
627c478bd9Sstevel@tonic-gate 
637c478bd9Sstevel@tonic-gate #define DEFLATED   8
647c478bd9Sstevel@tonic-gate 
657c478bd9Sstevel@tonic-gate #ifndef DEF_WBITS
667c478bd9Sstevel@tonic-gate #  define DEF_WBITS MAX_WBITS
677c478bd9Sstevel@tonic-gate #endif
687c478bd9Sstevel@tonic-gate /* default windowBits for decompression. MAX_WBITS is for compression only */
697c478bd9Sstevel@tonic-gate 
707c478bd9Sstevel@tonic-gate #if MAX_MEM_LEVEL >= 8
717c478bd9Sstevel@tonic-gate #  define DEF_MEM_LEVEL 8
727c478bd9Sstevel@tonic-gate #else
737c478bd9Sstevel@tonic-gate #  define DEF_MEM_LEVEL  MAX_MEM_LEVEL
747c478bd9Sstevel@tonic-gate #endif
757c478bd9Sstevel@tonic-gate /* default memLevel */
767c478bd9Sstevel@tonic-gate 
777c478bd9Sstevel@tonic-gate #define STORED_BLOCK 0
787c478bd9Sstevel@tonic-gate #define STATIC_TREES 1
797c478bd9Sstevel@tonic-gate #define DYN_TREES    2
807c478bd9Sstevel@tonic-gate /* The three kinds of block type */
817c478bd9Sstevel@tonic-gate 
827c478bd9Sstevel@tonic-gate #define MIN_MATCH  3
837c478bd9Sstevel@tonic-gate #define MAX_MATCH  258
847c478bd9Sstevel@tonic-gate /* The minimum and maximum match lengths */
857c478bd9Sstevel@tonic-gate 
867c478bd9Sstevel@tonic-gate          /* functions */
877c478bd9Sstevel@tonic-gate 
887c478bd9Sstevel@tonic-gate #if defined(STDC) && !defined(HAVE_MEMCPY) && !defined(NO_MEMCPY)
897c478bd9Sstevel@tonic-gate #  define HAVE_MEMCPY
907c478bd9Sstevel@tonic-gate #endif
917c478bd9Sstevel@tonic-gate #ifdef HAVE_MEMCPY
927c478bd9Sstevel@tonic-gate #  define zmemcpy memcpy
937c478bd9Sstevel@tonic-gate #  define zmemzero(dest, len) memset(dest, 0, len)
947c478bd9Sstevel@tonic-gate #else
957c478bd9Sstevel@tonic-gate #  define zmemcpy(d, s, n)	bcopy((s), (d), (n))
967c478bd9Sstevel@tonic-gate #  define zmemzero		bzero
977c478bd9Sstevel@tonic-gate #endif
987c478bd9Sstevel@tonic-gate 
997c478bd9Sstevel@tonic-gate /* Diagnostic functions */
1007c478bd9Sstevel@tonic-gate #ifdef DEBUG_ZLIB
1017c478bd9Sstevel@tonic-gate #  include <stdio.h>
1027c478bd9Sstevel@tonic-gate #  ifndef verbose
1037c478bd9Sstevel@tonic-gate #    define verbose 0
1047c478bd9Sstevel@tonic-gate #  endif
1057c478bd9Sstevel@tonic-gate #  define Assert(cond,msg) {if(!(cond)) z_error(msg);}
1067c478bd9Sstevel@tonic-gate #  define Trace(x) fprintf x
1077c478bd9Sstevel@tonic-gate #  define Tracev(x) {if (verbose) fprintf x ;}
1087c478bd9Sstevel@tonic-gate #  define Tracevv(x) {if (verbose>1) fprintf x ;}
1097c478bd9Sstevel@tonic-gate #  define Tracec(c,x) {if (verbose && (c)) fprintf x ;}
1107c478bd9Sstevel@tonic-gate #  define Tracecv(c,x) {if (verbose>1 && (c)) fprintf x ;}
1117c478bd9Sstevel@tonic-gate #else
1127c478bd9Sstevel@tonic-gate #  define Assert(cond,msg)
1137c478bd9Sstevel@tonic-gate #  define Trace(x)
1147c478bd9Sstevel@tonic-gate #  define Tracev(x)
1157c478bd9Sstevel@tonic-gate #  define Tracevv(x)
1167c478bd9Sstevel@tonic-gate #  define Tracec(c,x)
1177c478bd9Sstevel@tonic-gate #  define Tracecv(c,x)
1187c478bd9Sstevel@tonic-gate #endif
1197c478bd9Sstevel@tonic-gate 
1207c478bd9Sstevel@tonic-gate 
1217c478bd9Sstevel@tonic-gate typedef uLong (*check_func) OF((uLong check, Bytef *buf, uInt len));
1227c478bd9Sstevel@tonic-gate 
1237c478bd9Sstevel@tonic-gate /* voidpf zcalloc OF((voidpf opaque, unsigned items, unsigned size)); */
1247c478bd9Sstevel@tonic-gate /* void   zcfree  OF((voidpf opaque, voidpf ptr)); */
1257c478bd9Sstevel@tonic-gate 
1267c478bd9Sstevel@tonic-gate #define ZALLOC(strm, items, size) \
1277c478bd9Sstevel@tonic-gate            (*((strm)->zalloc))((strm)->opaque, (items), (size))
1287c478bd9Sstevel@tonic-gate #define ZFREE(strm, addr, size)	\
1297c478bd9Sstevel@tonic-gate 	   (*((strm)->zfree))((strm)->opaque, (voidpf)(addr), (size))
1307c478bd9Sstevel@tonic-gate #define TRY_FREE(s, p, n) {if (p) ZFREE(s, p, n);}
1317c478bd9Sstevel@tonic-gate 
1327c478bd9Sstevel@tonic-gate /* deflate.h -- internal compression state
1337c478bd9Sstevel@tonic-gate  * Copyright (C) 1995 Jean-loup Gailly
1347c478bd9Sstevel@tonic-gate  * For conditions of distribution and use, see copyright notice in zlib.h
1357c478bd9Sstevel@tonic-gate  */
1367c478bd9Sstevel@tonic-gate 
1377c478bd9Sstevel@tonic-gate /* WARNING: this file should *not* be used by applications. It is
1387c478bd9Sstevel@tonic-gate    part of the implementation of the compression library and is
1397c478bd9Sstevel@tonic-gate    subject to change. Applications should only use zlib.h.
1407c478bd9Sstevel@tonic-gate  */
1417c478bd9Sstevel@tonic-gate 
1427c478bd9Sstevel@tonic-gate 
1437c478bd9Sstevel@tonic-gate /*+++++*/
1447c478bd9Sstevel@tonic-gate /* From: deflate.h,v 1.5 1995/05/03 17:27:09 jloup Exp */
1457c478bd9Sstevel@tonic-gate 
1467c478bd9Sstevel@tonic-gate /* ===========================================================================
1477c478bd9Sstevel@tonic-gate  * Internal compression state.
1487c478bd9Sstevel@tonic-gate  */
1497c478bd9Sstevel@tonic-gate 
1507c478bd9Sstevel@tonic-gate /* Data type */
1517c478bd9Sstevel@tonic-gate #define BINARY  0
1527c478bd9Sstevel@tonic-gate #define ASCII   1
1537c478bd9Sstevel@tonic-gate #define UNKNOWN 2
1547c478bd9Sstevel@tonic-gate 
1557c478bd9Sstevel@tonic-gate #define LENGTH_CODES 29
1567c478bd9Sstevel@tonic-gate /* number of length codes, not counting the special END_BLOCK code */
1577c478bd9Sstevel@tonic-gate 
1587c478bd9Sstevel@tonic-gate #define LITERALS  256
1597c478bd9Sstevel@tonic-gate /* number of literal bytes 0..255 */
1607c478bd9Sstevel@tonic-gate 
1617c478bd9Sstevel@tonic-gate #define L_CODES (LITERALS+1+LENGTH_CODES)
1627c478bd9Sstevel@tonic-gate /* number of Literal or Length codes, including the END_BLOCK code */
1637c478bd9Sstevel@tonic-gate 
1647c478bd9Sstevel@tonic-gate #define D_CODES   30
1657c478bd9Sstevel@tonic-gate /* number of distance codes */
1667c478bd9Sstevel@tonic-gate 
1677c478bd9Sstevel@tonic-gate #define BL_CODES  19
1687c478bd9Sstevel@tonic-gate /* number of codes used to transfer the bit lengths */
1697c478bd9Sstevel@tonic-gate 
1707c478bd9Sstevel@tonic-gate #define HEAP_SIZE (2*L_CODES+1)
1717c478bd9Sstevel@tonic-gate /* maximum heap size */
1727c478bd9Sstevel@tonic-gate 
1737c478bd9Sstevel@tonic-gate #define MAX_BITS 15
1747c478bd9Sstevel@tonic-gate /* All codes must not exceed MAX_BITS bits */
1757c478bd9Sstevel@tonic-gate 
1767c478bd9Sstevel@tonic-gate #define INIT_STATE    42
1777c478bd9Sstevel@tonic-gate #define BUSY_STATE   113
1787c478bd9Sstevel@tonic-gate #define FLUSH_STATE  124
1797c478bd9Sstevel@tonic-gate #define FINISH_STATE 666
1807c478bd9Sstevel@tonic-gate /* Stream status */
1817c478bd9Sstevel@tonic-gate 
1827c478bd9Sstevel@tonic-gate 
1837c478bd9Sstevel@tonic-gate /* Data structure describing a single value and its code string. */
1847c478bd9Sstevel@tonic-gate typedef struct ct_data_s {
1857c478bd9Sstevel@tonic-gate     union {
1867c478bd9Sstevel@tonic-gate         ush  freq;       /* frequency count */
1877c478bd9Sstevel@tonic-gate         ush  code;       /* bit string */
1887c478bd9Sstevel@tonic-gate     } fc;
1897c478bd9Sstevel@tonic-gate     union {
1907c478bd9Sstevel@tonic-gate         ush  dad;        /* father node in Huffman tree */
1917c478bd9Sstevel@tonic-gate         ush  len;        /* length of bit string */
1927c478bd9Sstevel@tonic-gate     } dl;
1937c478bd9Sstevel@tonic-gate } FAR ct_data;
1947c478bd9Sstevel@tonic-gate 
1957c478bd9Sstevel@tonic-gate #define Freq fc.freq
1967c478bd9Sstevel@tonic-gate #define Code fc.code
1977c478bd9Sstevel@tonic-gate #define Dad  dl.dad
1987c478bd9Sstevel@tonic-gate #define Len  dl.len
1997c478bd9Sstevel@tonic-gate 
2007c478bd9Sstevel@tonic-gate typedef struct static_tree_desc_s  static_tree_desc;
2017c478bd9Sstevel@tonic-gate 
2027c478bd9Sstevel@tonic-gate typedef struct tree_desc_s {
2037c478bd9Sstevel@tonic-gate     ct_data *dyn_tree;           /* the dynamic tree */
2047c478bd9Sstevel@tonic-gate     int     max_code;            /* largest code with non zero frequency */
2057c478bd9Sstevel@tonic-gate     static_tree_desc *stat_desc; /* the corresponding static tree */
2067c478bd9Sstevel@tonic-gate } FAR tree_desc;
2077c478bd9Sstevel@tonic-gate 
2087c478bd9Sstevel@tonic-gate typedef ush Pos;
2097c478bd9Sstevel@tonic-gate typedef Pos FAR Posf;
2107c478bd9Sstevel@tonic-gate typedef unsigned IPos;
2117c478bd9Sstevel@tonic-gate 
2127c478bd9Sstevel@tonic-gate /* A Pos is an index in the character window. We use short instead of int to
2137c478bd9Sstevel@tonic-gate  * save space in the various tables. IPos is used only for parameter passing.
2147c478bd9Sstevel@tonic-gate  */
2157c478bd9Sstevel@tonic-gate 
2167c478bd9Sstevel@tonic-gate typedef struct deflate_state {
2177c478bd9Sstevel@tonic-gate     z_stream *strm;      /* pointer back to this zlib stream */
2187c478bd9Sstevel@tonic-gate     int   status;        /* as the name implies */
2197c478bd9Sstevel@tonic-gate     Bytef *pending_buf;  /* output still pending */
2207c478bd9Sstevel@tonic-gate     Bytef *pending_out;  /* next pending byte to output to the stream */
2217c478bd9Sstevel@tonic-gate     int   pending;       /* nb of bytes in the pending buffer */
2227c478bd9Sstevel@tonic-gate     uLong adler;         /* adler32 of uncompressed data */
2237c478bd9Sstevel@tonic-gate     int   noheader;      /* suppress zlib header and adler32 */
2247c478bd9Sstevel@tonic-gate     Byte  data_type;     /* UNKNOWN, BINARY or ASCII */
2257c478bd9Sstevel@tonic-gate     Byte  method;        /* STORED (for zip only) or DEFLATED */
2267c478bd9Sstevel@tonic-gate     int	  minCompr;	 /* min size decrease for Z_FLUSH_NOSTORE */
2277c478bd9Sstevel@tonic-gate 
2287c478bd9Sstevel@tonic-gate                 /* used by deflate.c: */
2297c478bd9Sstevel@tonic-gate 
2307c478bd9Sstevel@tonic-gate     uInt  w_size;        /* LZ77 window size (32K by default) */
2317c478bd9Sstevel@tonic-gate     uInt  w_bits;        /* log2(w_size)  (8..16) */
2327c478bd9Sstevel@tonic-gate     uInt  w_mask;        /* w_size - 1 */
2337c478bd9Sstevel@tonic-gate 
2347c478bd9Sstevel@tonic-gate     Bytef *window;
2357c478bd9Sstevel@tonic-gate     /* Sliding window. Input bytes are read into the second half of the window,
2367c478bd9Sstevel@tonic-gate      * and move to the first half later to keep a dictionary of at least wSize
2377c478bd9Sstevel@tonic-gate      * bytes. With this organization, matches are limited to a distance of
2387c478bd9Sstevel@tonic-gate      * wSize-MAX_MATCH bytes, but this ensures that IO is always
2397c478bd9Sstevel@tonic-gate      * performed with a length multiple of the block size. Also, it limits
2407c478bd9Sstevel@tonic-gate      * the window size to 64K, which is quite useful on MSDOS.
2417c478bd9Sstevel@tonic-gate      * To do: use the user input buffer as sliding window.
2427c478bd9Sstevel@tonic-gate      */
2437c478bd9Sstevel@tonic-gate 
2447c478bd9Sstevel@tonic-gate     ulg window_size;
2457c478bd9Sstevel@tonic-gate     /* Actual size of window: 2*wSize, except when the user input buffer
2467c478bd9Sstevel@tonic-gate      * is directly used as sliding window.
2477c478bd9Sstevel@tonic-gate      */
2487c478bd9Sstevel@tonic-gate 
2497c478bd9Sstevel@tonic-gate     Posf *prev;
2507c478bd9Sstevel@tonic-gate     /* Link to older string with same hash index. To limit the size of this
2517c478bd9Sstevel@tonic-gate      * array to 64K, this link is maintained only for the last 32K strings.
2527c478bd9Sstevel@tonic-gate      * An index in this array is thus a window index modulo 32K.
2537c478bd9Sstevel@tonic-gate      */
2547c478bd9Sstevel@tonic-gate 
2557c478bd9Sstevel@tonic-gate     Posf *head; /* Heads of the hash chains or NIL. */
2567c478bd9Sstevel@tonic-gate 
2577c478bd9Sstevel@tonic-gate     uInt  ins_h;          /* hash index of string to be inserted */
2587c478bd9Sstevel@tonic-gate     uInt  hash_size;      /* number of elements in hash table */
2597c478bd9Sstevel@tonic-gate     uInt  hash_bits;      /* log2(hash_size) */
2607c478bd9Sstevel@tonic-gate     uInt  hash_mask;      /* hash_size-1 */
2617c478bd9Sstevel@tonic-gate 
2627c478bd9Sstevel@tonic-gate     uInt  hash_shift;
2637c478bd9Sstevel@tonic-gate     /* Number of bits by which ins_h must be shifted at each input
2647c478bd9Sstevel@tonic-gate      * step. It must be such that after MIN_MATCH steps, the oldest
2657c478bd9Sstevel@tonic-gate      * byte no longer takes part in the hash key, that is:
2667c478bd9Sstevel@tonic-gate      *   hash_shift * MIN_MATCH >= hash_bits
2677c478bd9Sstevel@tonic-gate      */
2687c478bd9Sstevel@tonic-gate 
2697c478bd9Sstevel@tonic-gate     long block_start;
2707c478bd9Sstevel@tonic-gate     /* Window position at the beginning of the current output block. Gets
2717c478bd9Sstevel@tonic-gate      * negative when the window is moved backwards.
2727c478bd9Sstevel@tonic-gate      */
2737c478bd9Sstevel@tonic-gate 
2747c478bd9Sstevel@tonic-gate     uInt match_length;           /* length of best match */
2757c478bd9Sstevel@tonic-gate     IPos prev_match;             /* previous match */
2767c478bd9Sstevel@tonic-gate     int match_available;         /* set if previous match exists */
2777c478bd9Sstevel@tonic-gate     uInt strstart;               /* start of string to insert */
2787c478bd9Sstevel@tonic-gate     uInt match_start;            /* start of matching string */
2797c478bd9Sstevel@tonic-gate     uInt lookahead;              /* number of valid bytes ahead in window */
2807c478bd9Sstevel@tonic-gate 
2817c478bd9Sstevel@tonic-gate     uInt prev_length;
2827c478bd9Sstevel@tonic-gate     /* Length of the best match at previous step. Matches not greater than this
2837c478bd9Sstevel@tonic-gate      * are discarded. This is used in the lazy match evaluation.
2847c478bd9Sstevel@tonic-gate      */
2857c478bd9Sstevel@tonic-gate 
2867c478bd9Sstevel@tonic-gate     uInt max_chain_length;
2877c478bd9Sstevel@tonic-gate     /* To speed up deflation, hash chains are never searched beyond this
2887c478bd9Sstevel@tonic-gate      * length.  A higher limit improves compression ratio but degrades the
2897c478bd9Sstevel@tonic-gate      * speed.
2907c478bd9Sstevel@tonic-gate      */
2917c478bd9Sstevel@tonic-gate 
2927c478bd9Sstevel@tonic-gate     uInt max_lazy_match;
2937c478bd9Sstevel@tonic-gate     /* Attempt to find a better match only when the current match is strictly
2947c478bd9Sstevel@tonic-gate      * smaller than this value. This mechanism is used only for compression
2957c478bd9Sstevel@tonic-gate      * levels >= 4.
2967c478bd9Sstevel@tonic-gate      */
2977c478bd9Sstevel@tonic-gate #   define max_insert_length  max_lazy_match
2987c478bd9Sstevel@tonic-gate     /* Insert new strings in the hash table only if the match length is not
2997c478bd9Sstevel@tonic-gate      * greater than this length. This saves time but degrades compression.
3007c478bd9Sstevel@tonic-gate      * max_insert_length is used only for compression levels <= 3.
3017c478bd9Sstevel@tonic-gate      */
3027c478bd9Sstevel@tonic-gate 
3037c478bd9Sstevel@tonic-gate     int level;    /* compression level (1..9) */
3047c478bd9Sstevel@tonic-gate     int strategy; /* favor or force Huffman coding*/
3057c478bd9Sstevel@tonic-gate 
3067c478bd9Sstevel@tonic-gate     uInt good_match;
3077c478bd9Sstevel@tonic-gate     /* Use a faster search when the previous match is longer than this */
3087c478bd9Sstevel@tonic-gate 
3097c478bd9Sstevel@tonic-gate      int nice_match; /* Stop searching when current match exceeds this */
3107c478bd9Sstevel@tonic-gate 
3117c478bd9Sstevel@tonic-gate                 /* used by trees.c: */
3127c478bd9Sstevel@tonic-gate     /* Didn't use ct_data typedef below to supress compiler warning */
3137c478bd9Sstevel@tonic-gate     struct ct_data_s dyn_ltree[HEAP_SIZE];   /* literal and length tree */
3147c478bd9Sstevel@tonic-gate     struct ct_data_s dyn_dtree[2*D_CODES+1]; /* distance tree */
3157c478bd9Sstevel@tonic-gate     struct ct_data_s bl_tree[2*BL_CODES+1];  /* Huffman tree for bit lengths */
3167c478bd9Sstevel@tonic-gate 
3177c478bd9Sstevel@tonic-gate     struct tree_desc_s l_desc;               /* desc. for literal tree */
3187c478bd9Sstevel@tonic-gate     struct tree_desc_s d_desc;               /* desc. for distance tree */
3197c478bd9Sstevel@tonic-gate     struct tree_desc_s bl_desc;              /* desc. for bit length tree */
3207c478bd9Sstevel@tonic-gate 
3217c478bd9Sstevel@tonic-gate     ush bl_count[MAX_BITS+1];
3227c478bd9Sstevel@tonic-gate     /* number of codes at each bit length for an optimal tree */
3237c478bd9Sstevel@tonic-gate 
3247c478bd9Sstevel@tonic-gate     int heap[2*L_CODES+1];      /* heap used to build the Huffman trees */
3257c478bd9Sstevel@tonic-gate     int heap_len;               /* number of elements in the heap */
3267c478bd9Sstevel@tonic-gate     int heap_max;               /* element of largest frequency */
3277c478bd9Sstevel@tonic-gate     /* The sons of heap[n] are heap[2*n] and heap[2*n+1]. heap[0] is not used.
3287c478bd9Sstevel@tonic-gate      * The same heap array is used to build all trees.
3297c478bd9Sstevel@tonic-gate      */
3307c478bd9Sstevel@tonic-gate 
3317c478bd9Sstevel@tonic-gate     uch depth[2*L_CODES+1];
3327c478bd9Sstevel@tonic-gate     /* Depth of each subtree used as tie breaker for trees of equal frequency
3337c478bd9Sstevel@tonic-gate      */
3347c478bd9Sstevel@tonic-gate 
3357c478bd9Sstevel@tonic-gate     uchf *l_buf;          /* buffer for literals or lengths */
3367c478bd9Sstevel@tonic-gate 
3377c478bd9Sstevel@tonic-gate     uInt  lit_bufsize;
3387c478bd9Sstevel@tonic-gate     /* Size of match buffer for literals/lengths.  There are 4 reasons for
3397c478bd9Sstevel@tonic-gate      * limiting lit_bufsize to 64K:
3407c478bd9Sstevel@tonic-gate      *   - frequencies can be kept in 16 bit counters
3417c478bd9Sstevel@tonic-gate      *   - if compression is not successful for the first block, all input
3427c478bd9Sstevel@tonic-gate      *     data is still in the window so we can still emit a stored block even
3437c478bd9Sstevel@tonic-gate      *     when input comes from standard input.  (This can also be done for
3447c478bd9Sstevel@tonic-gate      *     all blocks if lit_bufsize is not greater than 32K.)
3457c478bd9Sstevel@tonic-gate      *   - if compression is not successful for a file smaller than 64K, we can
3467c478bd9Sstevel@tonic-gate      *     even emit a stored file instead of a stored block (saving 5 bytes).
3477c478bd9Sstevel@tonic-gate      *     This is applicable only for zip (not gzip or zlib).
3487c478bd9Sstevel@tonic-gate      *   - creating new Huffman trees less frequently may not provide fast
3497c478bd9Sstevel@tonic-gate      *     adaptation to changes in the input data statistics. (Take for
3507c478bd9Sstevel@tonic-gate      *     example a binary file with poorly compressible code followed by
3517c478bd9Sstevel@tonic-gate      *     a highly compressible string table.) Smaller buffer sizes give
3527c478bd9Sstevel@tonic-gate      *     fast adaptation but have of course the overhead of transmitting
3537c478bd9Sstevel@tonic-gate      *     trees more frequently.
3547c478bd9Sstevel@tonic-gate      *   - I can't count above 4
3557c478bd9Sstevel@tonic-gate      */
3567c478bd9Sstevel@tonic-gate 
3577c478bd9Sstevel@tonic-gate     uInt last_lit;      /* running index in l_buf */
3587c478bd9Sstevel@tonic-gate 
3597c478bd9Sstevel@tonic-gate     ushf *d_buf;
3607c478bd9Sstevel@tonic-gate     /* Buffer for distances. To simplify the code, d_buf and l_buf have
3617c478bd9Sstevel@tonic-gate      * the same number of elements. To use different lengths, an extra flag
3627c478bd9Sstevel@tonic-gate      * array would be necessary.
3637c478bd9Sstevel@tonic-gate      */
3647c478bd9Sstevel@tonic-gate 
3657c478bd9Sstevel@tonic-gate     ulg opt_len;        /* bit length of current block with optimal trees */
3667c478bd9Sstevel@tonic-gate     ulg static_len;     /* bit length of current block with static trees */
3677c478bd9Sstevel@tonic-gate     ulg compressed_len; /* total bit length of compressed file */
3687c478bd9Sstevel@tonic-gate     uInt matches;       /* number of string matches in current block */
3697c478bd9Sstevel@tonic-gate     int last_eob_len;   /* bit length of EOB code for last block */
3707c478bd9Sstevel@tonic-gate 
3717c478bd9Sstevel@tonic-gate #ifdef DEBUG_ZLIB
3727c478bd9Sstevel@tonic-gate     ulg bits_sent;      /* bit length of the compressed data */
3737c478bd9Sstevel@tonic-gate #endif
3747c478bd9Sstevel@tonic-gate 
3757c478bd9Sstevel@tonic-gate     ush bi_buf;
3767c478bd9Sstevel@tonic-gate     /* Output buffer. bits are inserted starting at the bottom (least
3777c478bd9Sstevel@tonic-gate      * significant bits).
3787c478bd9Sstevel@tonic-gate      */
3797c478bd9Sstevel@tonic-gate     int bi_valid;
3807c478bd9Sstevel@tonic-gate     /* Number of valid bits in bi_buf.  All bits above the last valid bit
3817c478bd9Sstevel@tonic-gate      * are always zero.
3827c478bd9Sstevel@tonic-gate      */
3837c478bd9Sstevel@tonic-gate 
3847c478bd9Sstevel@tonic-gate     uInt blocks_in_packet;
3857c478bd9Sstevel@tonic-gate     /* Number of blocks produced since the last time Z_PACKET_FLUSH
3867c478bd9Sstevel@tonic-gate      * was used.
3877c478bd9Sstevel@tonic-gate      */
3887c478bd9Sstevel@tonic-gate 
3897c478bd9Sstevel@tonic-gate } FAR deflate_state;
3907c478bd9Sstevel@tonic-gate 
3917c478bd9Sstevel@tonic-gate /* Output a byte on the stream.
3927c478bd9Sstevel@tonic-gate  * IN assertion: there is enough room in pending_buf.
3937c478bd9Sstevel@tonic-gate  */
3947c478bd9Sstevel@tonic-gate #define put_byte(s, c) {s->pending_buf[s->pending++] = (c);}
3957c478bd9Sstevel@tonic-gate 
3967c478bd9Sstevel@tonic-gate 
3977c478bd9Sstevel@tonic-gate #define MIN_LOOKAHEAD (MAX_MATCH+MIN_MATCH+1)
3987c478bd9Sstevel@tonic-gate /* Minimum amount of lookahead, except at the end of the input file.
3997c478bd9Sstevel@tonic-gate  * See deflate.c for comments about the MIN_MATCH+1.
4007c478bd9Sstevel@tonic-gate  */
4017c478bd9Sstevel@tonic-gate 
4027c478bd9Sstevel@tonic-gate #define MAX_DIST(s)  ((s)->w_size-MIN_LOOKAHEAD)
4037c478bd9Sstevel@tonic-gate /* In order to simplify the code, particularly on 16 bit machines, match
4047c478bd9Sstevel@tonic-gate  * distances are limited to MAX_DIST instead of WSIZE.
4057c478bd9Sstevel@tonic-gate  */
4067c478bd9Sstevel@tonic-gate 
4077c478bd9Sstevel@tonic-gate         /* in trees.c */
4087c478bd9Sstevel@tonic-gate local void ct_init       OF((deflate_state *s));
4097c478bd9Sstevel@tonic-gate local int  ct_tally      OF((deflate_state *s, int dist, int lc));
4107c478bd9Sstevel@tonic-gate local ulg ct_flush_block OF((deflate_state *s, charf *buf, ulg stored_len,
4117c478bd9Sstevel@tonic-gate 			     int flush));
4127c478bd9Sstevel@tonic-gate local void ct_align      OF((deflate_state *s));
4137c478bd9Sstevel@tonic-gate local void ct_stored_block OF((deflate_state *s, charf *buf, ulg stored_len,
4147c478bd9Sstevel@tonic-gate                           int eof));
4157c478bd9Sstevel@tonic-gate local void ct_stored_type_only OF((deflate_state *s));
4167c478bd9Sstevel@tonic-gate 
4177c478bd9Sstevel@tonic-gate 
4187c478bd9Sstevel@tonic-gate /*+++++*/
4197c478bd9Sstevel@tonic-gate /* deflate.c -- compress data using the deflation algorithm
4207c478bd9Sstevel@tonic-gate  * Copyright (C) 1995 Jean-loup Gailly.
4217c478bd9Sstevel@tonic-gate  * For conditions of distribution and use, see copyright notice in zlib.h
4227c478bd9Sstevel@tonic-gate  */
4237c478bd9Sstevel@tonic-gate 
4247c478bd9Sstevel@tonic-gate /*
4257c478bd9Sstevel@tonic-gate  *  ALGORITHM
4267c478bd9Sstevel@tonic-gate  *
4277c478bd9Sstevel@tonic-gate  *      The "deflation" process depends on being able to identify portions
4287c478bd9Sstevel@tonic-gate  *      of the input text which are identical to earlier input (within a
4297c478bd9Sstevel@tonic-gate  *      sliding window trailing behind the input currently being processed).
4307c478bd9Sstevel@tonic-gate  *
4317c478bd9Sstevel@tonic-gate  *      The most straightforward technique turns out to be the fastest for
4327c478bd9Sstevel@tonic-gate  *      most input files: try all possible matches and select the longest.
4337c478bd9Sstevel@tonic-gate  *      The key feature of this algorithm is that insertions into the string
4347c478bd9Sstevel@tonic-gate  *      dictionary are very simple and thus fast, and deletions are avoided
4357c478bd9Sstevel@tonic-gate  *      completely. Insertions are performed at each input character, whereas
4367c478bd9Sstevel@tonic-gate  *      string matches are performed only when the previous match ends. So it
4377c478bd9Sstevel@tonic-gate  *      is preferable to spend more time in matches to allow very fast string
4387c478bd9Sstevel@tonic-gate  *      insertions and avoid deletions. The matching algorithm for small
4397c478bd9Sstevel@tonic-gate  *      strings is inspired from that of Rabin & Karp. A brute force approach
4407c478bd9Sstevel@tonic-gate  *      is used to find longer strings when a small match has been found.
4417c478bd9Sstevel@tonic-gate  *      A similar algorithm is used in comic (by Jan-Mark Wams) and freeze
4427c478bd9Sstevel@tonic-gate  *      (by Leonid Broukhis).
4437c478bd9Sstevel@tonic-gate  *         A previous version of this file used a more sophisticated algorithm
4447c478bd9Sstevel@tonic-gate  *      (by Fiala and Greene) which is guaranteed to run in linear amortized
4457c478bd9Sstevel@tonic-gate  *      time, but has a larger average cost, uses more memory and is patented.
4467c478bd9Sstevel@tonic-gate  *      However the F&G algorithm may be faster for some highly redundant
4477c478bd9Sstevel@tonic-gate  *      files if the parameter max_chain_length (described below) is too large.
4487c478bd9Sstevel@tonic-gate  *
4497c478bd9Sstevel@tonic-gate  *  ACKNOWLEDGEMENTS
4507c478bd9Sstevel@tonic-gate  *
4517c478bd9Sstevel@tonic-gate  *      The idea of lazy evaluation of matches is due to Jan-Mark Wams, and
4527c478bd9Sstevel@tonic-gate  *      I found it in 'freeze' written by Leonid Broukhis.
4537c478bd9Sstevel@tonic-gate  *      Thanks to many people for bug reports and testing.
4547c478bd9Sstevel@tonic-gate  *
4557c478bd9Sstevel@tonic-gate  *  REFERENCES
4567c478bd9Sstevel@tonic-gate  *
4577c478bd9Sstevel@tonic-gate  *      Deutsch, L.P.,"'Deflate' Compressed Data Format Specification".
4587c478bd9Sstevel@tonic-gate  *      Available in ftp.uu.net:/pub/archiving/zip/doc/deflate-1.1.doc
4597c478bd9Sstevel@tonic-gate  *
4607c478bd9Sstevel@tonic-gate  *      A description of the Rabin and Karp algorithm is given in the book
4617c478bd9Sstevel@tonic-gate  *         "Algorithms" by R. Sedgewick, Addison-Wesley, p252.
4627c478bd9Sstevel@tonic-gate  *
4637c478bd9Sstevel@tonic-gate  *      Fiala,E.R., and Greene,D.H.
4647c478bd9Sstevel@tonic-gate  *         Data Compression with Finite Windows, Comm.ACM, 32,4 (1989) 490-595
4657c478bd9Sstevel@tonic-gate  *
4667c478bd9Sstevel@tonic-gate  */
4677c478bd9Sstevel@tonic-gate 
4687c478bd9Sstevel@tonic-gate /* From: deflate.c,v 1.8 1995/05/03 17:27:08 jloup Exp */
4697c478bd9Sstevel@tonic-gate 
4707c478bd9Sstevel@tonic-gate local char zlib_copyright[] = " deflate Copyright 1995 Jean-loup Gailly ";
4717c478bd9Sstevel@tonic-gate /*
4727c478bd9Sstevel@tonic-gate   If you use the zlib library in a product, an acknowledgment is welcome
4737c478bd9Sstevel@tonic-gate   in the documentation of your product. If for some reason you cannot
4747c478bd9Sstevel@tonic-gate   include such an acknowledgment, I would appreciate that you keep this
4757c478bd9Sstevel@tonic-gate   copyright string in the executable of your product.
4767c478bd9Sstevel@tonic-gate  */
4777c478bd9Sstevel@tonic-gate 
4787c478bd9Sstevel@tonic-gate #define NIL 0
4797c478bd9Sstevel@tonic-gate /* Tail of hash chains */
4807c478bd9Sstevel@tonic-gate 
4817c478bd9Sstevel@tonic-gate #ifndef TOO_FAR
4827c478bd9Sstevel@tonic-gate #  define TOO_FAR 4096
4837c478bd9Sstevel@tonic-gate #endif
4847c478bd9Sstevel@tonic-gate /* Matches of length 3 are discarded if their distance exceeds TOO_FAR */
4857c478bd9Sstevel@tonic-gate 
4867c478bd9Sstevel@tonic-gate #define MIN_LOOKAHEAD (MAX_MATCH+MIN_MATCH+1)
4877c478bd9Sstevel@tonic-gate /* Minimum amount of lookahead, except at the end of the input file.
4887c478bd9Sstevel@tonic-gate  * See deflate.c for comments about the MIN_MATCH+1.
4897c478bd9Sstevel@tonic-gate  */
4907c478bd9Sstevel@tonic-gate 
4917c478bd9Sstevel@tonic-gate /* Values for max_lazy_match, good_match and max_chain_length, depending on
4927c478bd9Sstevel@tonic-gate  * the desired pack level (0..9). The values given below have been tuned to
4937c478bd9Sstevel@tonic-gate  * exclude worst case performance for pathological files. Better values may be
4947c478bd9Sstevel@tonic-gate  * found for specific files.
4957c478bd9Sstevel@tonic-gate  */
4967c478bd9Sstevel@tonic-gate 
4977c478bd9Sstevel@tonic-gate typedef struct config_s {
4987c478bd9Sstevel@tonic-gate    ush good_length; /* reduce lazy search above this match length */
4997c478bd9Sstevel@tonic-gate    ush max_lazy;    /* do not perform lazy search above this match length */
5007c478bd9Sstevel@tonic-gate    ush nice_length; /* quit search above this match length */
5017c478bd9Sstevel@tonic-gate    ush max_chain;
5027c478bd9Sstevel@tonic-gate } config;
5037c478bd9Sstevel@tonic-gate 
5047c478bd9Sstevel@tonic-gate local config configuration_table[10] = {
5057c478bd9Sstevel@tonic-gate /*      good lazy nice chain */
5067c478bd9Sstevel@tonic-gate /* 0 */ {0,    0,  0,    0},  /* store only */
5077c478bd9Sstevel@tonic-gate /* 1 */ {4,    4,  8,    4},  /* maximum speed, no lazy matches */
5087c478bd9Sstevel@tonic-gate /* 2 */ {4,    5, 16,    8},
5097c478bd9Sstevel@tonic-gate /* 3 */ {4,    6, 32,   32},
5107c478bd9Sstevel@tonic-gate 
5117c478bd9Sstevel@tonic-gate /* 4 */ {4,    4, 16,   16},  /* lazy matches */
5127c478bd9Sstevel@tonic-gate /* 5 */ {8,   16, 32,   32},
5137c478bd9Sstevel@tonic-gate /* 6 */ {8,   16, 128, 128},
5147c478bd9Sstevel@tonic-gate /* 7 */ {8,   32, 128, 256},
5157c478bd9Sstevel@tonic-gate /* 8 */ {32, 128, 258, 1024},
5167c478bd9Sstevel@tonic-gate /* 9 */ {32, 258, 258, 4096}}; /* maximum compression */
5177c478bd9Sstevel@tonic-gate 
5187c478bd9Sstevel@tonic-gate /* Note: the deflate() code requires max_lazy >= MIN_MATCH and max_chain >= 4
5197c478bd9Sstevel@tonic-gate  * For deflate_fast() (levels <= 3) good is ignored and lazy has a different
5207c478bd9Sstevel@tonic-gate  * meaning.
5217c478bd9Sstevel@tonic-gate  */
5227c478bd9Sstevel@tonic-gate 
5237c478bd9Sstevel@tonic-gate #define EQUAL 0
5247c478bd9Sstevel@tonic-gate /* result of memcmp for equal strings */
5257c478bd9Sstevel@tonic-gate 
5267c478bd9Sstevel@tonic-gate /* ===========================================================================
5277c478bd9Sstevel@tonic-gate  *  Prototypes for local functions.
5287c478bd9Sstevel@tonic-gate  */
5297c478bd9Sstevel@tonic-gate 
5307c478bd9Sstevel@tonic-gate local void fill_window   OF((deflate_state *s));
5317c478bd9Sstevel@tonic-gate local int  deflate_fast  OF((deflate_state *s, int flush));
5327c478bd9Sstevel@tonic-gate local int  deflate_slow  OF((deflate_state *s, int flush));
5337c478bd9Sstevel@tonic-gate local void lm_init       OF((deflate_state *s));
5347c478bd9Sstevel@tonic-gate local int longest_match  OF((deflate_state *s, IPos cur_match));
5357c478bd9Sstevel@tonic-gate local void putShortMSB   OF((deflate_state *s, uInt b));
5367c478bd9Sstevel@tonic-gate local void flush_pending OF((z_stream *strm));
5377c478bd9Sstevel@tonic-gate local int read_buf       OF((z_stream *strm, charf *buf, unsigned size));
5387c478bd9Sstevel@tonic-gate #ifdef ASMV
5397c478bd9Sstevel@tonic-gate       void match_init OF((void)); /* asm code initialization */
5407c478bd9Sstevel@tonic-gate #endif
5417c478bd9Sstevel@tonic-gate 
5427c478bd9Sstevel@tonic-gate #ifdef DEBUG_ZLIB
5437c478bd9Sstevel@tonic-gate local  void check_match OF((deflate_state *s, IPos start, IPos match,
5447c478bd9Sstevel@tonic-gate                             int length));
5457c478bd9Sstevel@tonic-gate #endif
5467c478bd9Sstevel@tonic-gate 
5477c478bd9Sstevel@tonic-gate 
5487c478bd9Sstevel@tonic-gate /* ===========================================================================
5497c478bd9Sstevel@tonic-gate  * Update a hash value with the given input byte
5507c478bd9Sstevel@tonic-gate  * IN  assertion: all calls to to UPDATE_HASH are made with consecutive
5517c478bd9Sstevel@tonic-gate  *    input characters, so that a running hash key can be computed from the
5527c478bd9Sstevel@tonic-gate  *    previous key instead of complete recalculation each time.
5537c478bd9Sstevel@tonic-gate  */
5547c478bd9Sstevel@tonic-gate #define UPDATE_HASH(s,h,c) (h = (((h)<<s->hash_shift) ^ (c)) & s->hash_mask)
5557c478bd9Sstevel@tonic-gate 
5567c478bd9Sstevel@tonic-gate 
5577c478bd9Sstevel@tonic-gate /* ===========================================================================
5587c478bd9Sstevel@tonic-gate  * Insert string str in the dictionary and set match_head to the previous head
5597c478bd9Sstevel@tonic-gate  * of the hash chain (the most recent string with same hash key). Return
5607c478bd9Sstevel@tonic-gate  * the previous length of the hash chain.
5617c478bd9Sstevel@tonic-gate  * IN  assertion: all calls to to INSERT_STRING are made with consecutive
5627c478bd9Sstevel@tonic-gate  *    input characters and the first MIN_MATCH bytes of str are valid
5637c478bd9Sstevel@tonic-gate  *    (except for the last MIN_MATCH-1 bytes of the input file).
5647c478bd9Sstevel@tonic-gate  */
5657c478bd9Sstevel@tonic-gate #define INSERT_STRING(s, str, match_head) \
5667c478bd9Sstevel@tonic-gate    (UPDATE_HASH(s, s->ins_h, s->window[(str) + (MIN_MATCH-1)]), \
5677c478bd9Sstevel@tonic-gate     s->prev[(str) & s->w_mask] = match_head = s->head[s->ins_h], \
5687c478bd9Sstevel@tonic-gate     s->head[s->ins_h] = (str))
5697c478bd9Sstevel@tonic-gate 
5707c478bd9Sstevel@tonic-gate /* ===========================================================================
5717c478bd9Sstevel@tonic-gate  * Initialize the hash table (avoiding 64K overflow for 16 bit systems).
5727c478bd9Sstevel@tonic-gate  * prev[] will be initialized on the fly.
5737c478bd9Sstevel@tonic-gate  */
5747c478bd9Sstevel@tonic-gate #define CLEAR_HASH(s) \
5757c478bd9Sstevel@tonic-gate     s->head[s->hash_size-1] = NIL; \
5767c478bd9Sstevel@tonic-gate     zmemzero((charf *)s->head, (unsigned)(s->hash_size-1)*sizeof(*s->head));
5777c478bd9Sstevel@tonic-gate 
5787c478bd9Sstevel@tonic-gate /* ========================================================================= */
deflateInit(strm,level)5797c478bd9Sstevel@tonic-gate int deflateInit (strm, level)
5807c478bd9Sstevel@tonic-gate     z_stream *strm;
5817c478bd9Sstevel@tonic-gate     int level;
5827c478bd9Sstevel@tonic-gate {
5837c478bd9Sstevel@tonic-gate     return deflateInit2 (strm, level, DEFLATED, MAX_WBITS, DEF_MEM_LEVEL,
5847c478bd9Sstevel@tonic-gate 			 0, 0);
5857c478bd9Sstevel@tonic-gate     /* To do: ignore strm->next_in if we use it as window */
5867c478bd9Sstevel@tonic-gate }
5877c478bd9Sstevel@tonic-gate 
5887c478bd9Sstevel@tonic-gate /* ========================================================================= */
deflateInit2(strm,level,method,windowBits,memLevel,strategy,minCompression)5897c478bd9Sstevel@tonic-gate int deflateInit2 (strm, level, method, windowBits, memLevel,
5907c478bd9Sstevel@tonic-gate 		  strategy, minCompression)
5917c478bd9Sstevel@tonic-gate     z_stream *strm;
5927c478bd9Sstevel@tonic-gate     int  level;
5937c478bd9Sstevel@tonic-gate     int  method;
5947c478bd9Sstevel@tonic-gate     int  windowBits;
5957c478bd9Sstevel@tonic-gate     int  memLevel;
5967c478bd9Sstevel@tonic-gate     int  strategy;
5977c478bd9Sstevel@tonic-gate     int  minCompression;
5987c478bd9Sstevel@tonic-gate {
5997c478bd9Sstevel@tonic-gate     deflate_state *s;
6007c478bd9Sstevel@tonic-gate     int noheader = 0;
6017c478bd9Sstevel@tonic-gate 
6027c478bd9Sstevel@tonic-gate     if (strm == Z_NULL) return Z_STREAM_ERROR;
6037c478bd9Sstevel@tonic-gate 
6047c478bd9Sstevel@tonic-gate     strm->msg = Z_NULL;
6057c478bd9Sstevel@tonic-gate /*    if (strm->zalloc == Z_NULL) strm->zalloc = zcalloc; */
6067c478bd9Sstevel@tonic-gate /*    if (strm->zfree == Z_NULL) strm->zfree = zcfree; */
6077c478bd9Sstevel@tonic-gate 
6087c478bd9Sstevel@tonic-gate     if (level == Z_DEFAULT_COMPRESSION) level = 6;
6097c478bd9Sstevel@tonic-gate 
6107c478bd9Sstevel@tonic-gate     if (windowBits < 0) { /* undocumented feature: suppress zlib header */
6117c478bd9Sstevel@tonic-gate         noheader = 1;
6127c478bd9Sstevel@tonic-gate         windowBits = -windowBits;
6137c478bd9Sstevel@tonic-gate     }
6147c478bd9Sstevel@tonic-gate     if (memLevel < 1 || memLevel > MAX_MEM_LEVEL || method != DEFLATED ||
6157c478bd9Sstevel@tonic-gate         windowBits < 8 || windowBits > 15 || level < 1 || level > 9) {
6167c478bd9Sstevel@tonic-gate         return Z_STREAM_ERROR;
6177c478bd9Sstevel@tonic-gate     }
6187c478bd9Sstevel@tonic-gate     s = (deflate_state *) ZALLOC(strm, 1, sizeof(deflate_state));
6197c478bd9Sstevel@tonic-gate     if (s == Z_NULL) return Z_MEM_ERROR;
6207c478bd9Sstevel@tonic-gate     strm->state = (struct internal_state FAR *)s;
6217c478bd9Sstevel@tonic-gate     s->strm = strm;
6227c478bd9Sstevel@tonic-gate 
6237c478bd9Sstevel@tonic-gate     s->noheader = noheader;
6247c478bd9Sstevel@tonic-gate     s->w_bits = windowBits;
6257c478bd9Sstevel@tonic-gate     s->w_size = 1 << s->w_bits;
6267c478bd9Sstevel@tonic-gate     s->w_mask = s->w_size - 1;
6277c478bd9Sstevel@tonic-gate 
6287c478bd9Sstevel@tonic-gate     s->hash_bits = memLevel + 7;
6297c478bd9Sstevel@tonic-gate     s->hash_size = 1 << s->hash_bits;
6307c478bd9Sstevel@tonic-gate     s->hash_mask = s->hash_size - 1;
6317c478bd9Sstevel@tonic-gate     s->hash_shift =  ((s->hash_bits+MIN_MATCH-1)/MIN_MATCH);
6327c478bd9Sstevel@tonic-gate 
6337c478bd9Sstevel@tonic-gate     s->window = (Bytef *) ZALLOC(strm, s->w_size, 2*sizeof(Byte));
6347c478bd9Sstevel@tonic-gate     s->prev   = (Posf *)  ZALLOC(strm, s->w_size, sizeof(Pos));
6357c478bd9Sstevel@tonic-gate     s->head   = (Posf *)  ZALLOC(strm, s->hash_size, sizeof(Pos));
6367c478bd9Sstevel@tonic-gate 
6377c478bd9Sstevel@tonic-gate     s->lit_bufsize = 1 << (memLevel + 6); /* 16K elements by default */
6387c478bd9Sstevel@tonic-gate 
6397c478bd9Sstevel@tonic-gate     s->pending_buf = (uchf *) ZALLOC(strm, s->lit_bufsize, 2*sizeof(ush));
6407c478bd9Sstevel@tonic-gate 
6417c478bd9Sstevel@tonic-gate     if (s->window == Z_NULL || s->prev == Z_NULL || s->head == Z_NULL ||
6427c478bd9Sstevel@tonic-gate         s->pending_buf == Z_NULL) {
6437c478bd9Sstevel@tonic-gate         strm->msg = z_errmsg[1-Z_MEM_ERROR];
6447c478bd9Sstevel@tonic-gate         deflateEnd (strm);
6457c478bd9Sstevel@tonic-gate         return Z_MEM_ERROR;
6467c478bd9Sstevel@tonic-gate     }
6477c478bd9Sstevel@tonic-gate     s->d_buf = (ushf *) &(s->pending_buf[s->lit_bufsize]);
6487c478bd9Sstevel@tonic-gate     s->l_buf = (uchf *) &(s->pending_buf[3*s->lit_bufsize]);
6497c478bd9Sstevel@tonic-gate     /* We overlay pending_buf and d_buf+l_buf. This works since the average
6507c478bd9Sstevel@tonic-gate      * output size for (length,distance) codes is <= 32 bits (worst case
6517c478bd9Sstevel@tonic-gate      * is 15+15+13=33).
6527c478bd9Sstevel@tonic-gate      */
6537c478bd9Sstevel@tonic-gate 
6547c478bd9Sstevel@tonic-gate     s->level = level;
6557c478bd9Sstevel@tonic-gate     s->strategy = strategy;
6567c478bd9Sstevel@tonic-gate     s->method = (Byte)method;
6577c478bd9Sstevel@tonic-gate     s->minCompr = minCompression;
6587c478bd9Sstevel@tonic-gate     s->blocks_in_packet = 0;
6597c478bd9Sstevel@tonic-gate 
6607c478bd9Sstevel@tonic-gate     return deflateReset(strm);
6617c478bd9Sstevel@tonic-gate }
6627c478bd9Sstevel@tonic-gate 
6637c478bd9Sstevel@tonic-gate /* ========================================================================= */
deflateReset(strm)6647c478bd9Sstevel@tonic-gate int deflateReset (strm)
6657c478bd9Sstevel@tonic-gate     z_stream *strm;
6667c478bd9Sstevel@tonic-gate {
6677c478bd9Sstevel@tonic-gate     deflate_state *s;
6687c478bd9Sstevel@tonic-gate 
6697c478bd9Sstevel@tonic-gate     if (strm == Z_NULL || strm->state == Z_NULL ||
6707c478bd9Sstevel@tonic-gate         strm->zalloc == Z_NULL || strm->zfree == Z_NULL) return Z_STREAM_ERROR;
6717c478bd9Sstevel@tonic-gate 
6727c478bd9Sstevel@tonic-gate     strm->total_in = strm->total_out = 0;
6737c478bd9Sstevel@tonic-gate     strm->msg = Z_NULL; /* use zfree if we ever allocate msg dynamically */
6747c478bd9Sstevel@tonic-gate     strm->data_type = Z_UNKNOWN;
6757c478bd9Sstevel@tonic-gate 
6767c478bd9Sstevel@tonic-gate     s = (deflate_state *)strm->state;
6777c478bd9Sstevel@tonic-gate     s->pending = 0;
6787c478bd9Sstevel@tonic-gate     s->pending_out = s->pending_buf;
6797c478bd9Sstevel@tonic-gate 
6807c478bd9Sstevel@tonic-gate     if (s->noheader < 0) {
6817c478bd9Sstevel@tonic-gate         s->noheader = 0; /* was set to -1 by deflate(..., Z_FINISH); */
6827c478bd9Sstevel@tonic-gate     }
6837c478bd9Sstevel@tonic-gate     s->status = s->noheader ? BUSY_STATE : INIT_STATE;
6847c478bd9Sstevel@tonic-gate     s->adler = 1;
6857c478bd9Sstevel@tonic-gate 
6867c478bd9Sstevel@tonic-gate     ct_init(s);
6877c478bd9Sstevel@tonic-gate     lm_init(s);
6887c478bd9Sstevel@tonic-gate 
6897c478bd9Sstevel@tonic-gate     return Z_OK;
6907c478bd9Sstevel@tonic-gate }
6917c478bd9Sstevel@tonic-gate 
6927c478bd9Sstevel@tonic-gate /* =========================================================================
6937c478bd9Sstevel@tonic-gate  * Put a short in the pending buffer. The 16-bit value is put in MSB order.
6947c478bd9Sstevel@tonic-gate  * IN assertion: the stream state is correct and there is enough room in
6957c478bd9Sstevel@tonic-gate  * pending_buf.
6967c478bd9Sstevel@tonic-gate  */
putShortMSB(s,b)6977c478bd9Sstevel@tonic-gate local void putShortMSB (s, b)
6987c478bd9Sstevel@tonic-gate     deflate_state *s;
6997c478bd9Sstevel@tonic-gate     uInt b;
7007c478bd9Sstevel@tonic-gate {
7017c478bd9Sstevel@tonic-gate     put_byte(s, (Byte)(b >> 8));
7027c478bd9Sstevel@tonic-gate     put_byte(s, (Byte)(b & 0xff));
7037c478bd9Sstevel@tonic-gate }
7047c478bd9Sstevel@tonic-gate 
7057c478bd9Sstevel@tonic-gate /* =========================================================================
7067c478bd9Sstevel@tonic-gate  * Flush as much pending output as possible.
7077c478bd9Sstevel@tonic-gate  */
flush_pending(strm)7087c478bd9Sstevel@tonic-gate local void flush_pending(strm)
7097c478bd9Sstevel@tonic-gate     z_stream *strm;
7107c478bd9Sstevel@tonic-gate {
7117c478bd9Sstevel@tonic-gate     deflate_state *state = (deflate_state *) strm->state;
7127c478bd9Sstevel@tonic-gate     unsigned len = state->pending;
7137c478bd9Sstevel@tonic-gate 
7147c478bd9Sstevel@tonic-gate     if (len > strm->avail_out) len = strm->avail_out;
7157c478bd9Sstevel@tonic-gate     if (len == 0) return;
7167c478bd9Sstevel@tonic-gate 
7177c478bd9Sstevel@tonic-gate     if (strm->next_out != NULL) {
7187c478bd9Sstevel@tonic-gate 	zmemcpy(strm->next_out, state->pending_out, len);
7197c478bd9Sstevel@tonic-gate 	strm->next_out += len;
7207c478bd9Sstevel@tonic-gate     }
7217c478bd9Sstevel@tonic-gate     state->pending_out += len;
7227c478bd9Sstevel@tonic-gate     strm->total_out += len;
7237c478bd9Sstevel@tonic-gate     strm->avail_out -= len;
7247c478bd9Sstevel@tonic-gate     state->pending -= len;
7257c478bd9Sstevel@tonic-gate     if (state->pending == 0) {
7267c478bd9Sstevel@tonic-gate         state->pending_out = state->pending_buf;
7277c478bd9Sstevel@tonic-gate     }
7287c478bd9Sstevel@tonic-gate }
7297c478bd9Sstevel@tonic-gate 
7307c478bd9Sstevel@tonic-gate /* ========================================================================= */
deflate(strm,flush)7317c478bd9Sstevel@tonic-gate int deflate (strm, flush)
7327c478bd9Sstevel@tonic-gate     z_stream *strm;
7337c478bd9Sstevel@tonic-gate     int flush;
7347c478bd9Sstevel@tonic-gate {
7357c478bd9Sstevel@tonic-gate     deflate_state *state = (deflate_state *) strm->state;
7367c478bd9Sstevel@tonic-gate 
7377c478bd9Sstevel@tonic-gate     if (strm == Z_NULL || state == Z_NULL) return Z_STREAM_ERROR;
7387c478bd9Sstevel@tonic-gate 
7397c478bd9Sstevel@tonic-gate     if (strm->next_in == Z_NULL && strm->avail_in != 0) {
7407c478bd9Sstevel@tonic-gate         ERR_RETURN(strm, Z_STREAM_ERROR);
7417c478bd9Sstevel@tonic-gate     }
7427c478bd9Sstevel@tonic-gate     if (strm->avail_out == 0) ERR_RETURN(strm, Z_BUF_ERROR);
7437c478bd9Sstevel@tonic-gate 
7447c478bd9Sstevel@tonic-gate     state->strm = strm; /* just in case */
7457c478bd9Sstevel@tonic-gate 
7467c478bd9Sstevel@tonic-gate     /* Write the zlib header */
7477c478bd9Sstevel@tonic-gate     if (state->status == INIT_STATE) {
7487c478bd9Sstevel@tonic-gate 
7497c478bd9Sstevel@tonic-gate         uInt header = (DEFLATED + ((state->w_bits-8)<<4)) << 8;
7507c478bd9Sstevel@tonic-gate         uInt level_flags = (state->level-1) >> 1;
7517c478bd9Sstevel@tonic-gate 
7527c478bd9Sstevel@tonic-gate         if (level_flags > 3) level_flags = 3;
7537c478bd9Sstevel@tonic-gate         header |= (level_flags << 6);
7547c478bd9Sstevel@tonic-gate         header += 31 - (header % 31);
7557c478bd9Sstevel@tonic-gate 
7567c478bd9Sstevel@tonic-gate         state->status = BUSY_STATE;
7577c478bd9Sstevel@tonic-gate         putShortMSB(state, header);
7587c478bd9Sstevel@tonic-gate     }
7597c478bd9Sstevel@tonic-gate 
7607c478bd9Sstevel@tonic-gate     /* Flush as much pending output as possible */
7617c478bd9Sstevel@tonic-gate     if (state->pending != 0) {
7627c478bd9Sstevel@tonic-gate         flush_pending(strm);
7637c478bd9Sstevel@tonic-gate         if (strm->avail_out == 0) return Z_OK;
7647c478bd9Sstevel@tonic-gate     }
7657c478bd9Sstevel@tonic-gate 
7667c478bd9Sstevel@tonic-gate     /* If we came back in here to get the last output from
7677c478bd9Sstevel@tonic-gate      * a previous flush, we're done for now.
7687c478bd9Sstevel@tonic-gate      */
7697c478bd9Sstevel@tonic-gate     if (state->status == FLUSH_STATE) {
7707c478bd9Sstevel@tonic-gate 	state->status = BUSY_STATE;
7717c478bd9Sstevel@tonic-gate 	if (flush != Z_NO_FLUSH && flush != Z_FINISH)
7727c478bd9Sstevel@tonic-gate 	    return Z_OK;
7737c478bd9Sstevel@tonic-gate     }
7747c478bd9Sstevel@tonic-gate 
7757c478bd9Sstevel@tonic-gate     /* User must not provide more input after the first FINISH: */
7767c478bd9Sstevel@tonic-gate     if (state->status == FINISH_STATE && strm->avail_in != 0) {
7777c478bd9Sstevel@tonic-gate         ERR_RETURN(strm, Z_BUF_ERROR);
7787c478bd9Sstevel@tonic-gate     }
7797c478bd9Sstevel@tonic-gate 
7807c478bd9Sstevel@tonic-gate     /* Start a new block or continue the current one.
7817c478bd9Sstevel@tonic-gate      */
7827c478bd9Sstevel@tonic-gate     if (strm->avail_in != 0 || state->lookahead != 0 ||
7837c478bd9Sstevel@tonic-gate         (flush == Z_FINISH && state->status != FINISH_STATE)) {
7847c478bd9Sstevel@tonic-gate         int quit;
7857c478bd9Sstevel@tonic-gate 
7867c478bd9Sstevel@tonic-gate         if (flush == Z_FINISH) {
7877c478bd9Sstevel@tonic-gate             state->status = FINISH_STATE;
7887c478bd9Sstevel@tonic-gate         }
7897c478bd9Sstevel@tonic-gate         if (state->level <= 3) {
7907c478bd9Sstevel@tonic-gate             quit = deflate_fast(state, flush);
7917c478bd9Sstevel@tonic-gate         } else {
7927c478bd9Sstevel@tonic-gate             quit = deflate_slow(state, flush);
7937c478bd9Sstevel@tonic-gate         }
7947c478bd9Sstevel@tonic-gate         if (quit || strm->avail_out == 0)
7957c478bd9Sstevel@tonic-gate 	    return Z_OK;
7967c478bd9Sstevel@tonic-gate         /* If flush != Z_NO_FLUSH && avail_out == 0, the next call
7977c478bd9Sstevel@tonic-gate          * of deflate should use the same flush parameter to make sure
7987c478bd9Sstevel@tonic-gate          * that the flush is complete. So we don't have to output an
7997c478bd9Sstevel@tonic-gate          * empty block here, this will be done at next call. This also
8007c478bd9Sstevel@tonic-gate          * ensures that for a very small output buffer, we emit at most
8017c478bd9Sstevel@tonic-gate          * one empty block.
8027c478bd9Sstevel@tonic-gate          */
8037c478bd9Sstevel@tonic-gate     }
8047c478bd9Sstevel@tonic-gate 
8057c478bd9Sstevel@tonic-gate     /* If a flush was requested, we have a little more to output now. */
8067c478bd9Sstevel@tonic-gate     if (flush != Z_NO_FLUSH && flush != Z_FINISH
8077c478bd9Sstevel@tonic-gate 	&& state->status != FINISH_STATE) {
8087c478bd9Sstevel@tonic-gate 	switch (flush) {
8097c478bd9Sstevel@tonic-gate 	case Z_PARTIAL_FLUSH:
8107c478bd9Sstevel@tonic-gate 	    ct_align(state);
8117c478bd9Sstevel@tonic-gate 	    break;
8127c478bd9Sstevel@tonic-gate 	case Z_PACKET_FLUSH:
8137c478bd9Sstevel@tonic-gate 	    /* Output just the 3-bit `stored' block type value,
8147c478bd9Sstevel@tonic-gate 	       but not a zero length. */
8157c478bd9Sstevel@tonic-gate 	    ct_stored_type_only(state);
8167c478bd9Sstevel@tonic-gate 	    break;
8177c478bd9Sstevel@tonic-gate 	default:
8187c478bd9Sstevel@tonic-gate 	    ct_stored_block(state, (char*)0, 0L, 0);
8197c478bd9Sstevel@tonic-gate 	    /* For a full flush, this empty block will be recognized
8207c478bd9Sstevel@tonic-gate 	     * as a special marker by inflate_sync().
8217c478bd9Sstevel@tonic-gate 	     */
8227c478bd9Sstevel@tonic-gate 	    if (flush == Z_FULL_FLUSH) {
8237c478bd9Sstevel@tonic-gate 		CLEAR_HASH(state);             /* forget history */
8247c478bd9Sstevel@tonic-gate 	    }
8257c478bd9Sstevel@tonic-gate 	}
8267c478bd9Sstevel@tonic-gate 	flush_pending(strm);
8277c478bd9Sstevel@tonic-gate 	if (strm->avail_out == 0) {
8287c478bd9Sstevel@tonic-gate 	    /* We'll have to come back to get the rest of the output;
8297c478bd9Sstevel@tonic-gate 	     * this ensures we don't output a second zero-length stored
8307c478bd9Sstevel@tonic-gate 	     * block (or whatever).
8317c478bd9Sstevel@tonic-gate 	     */
8327c478bd9Sstevel@tonic-gate 	    state->status = FLUSH_STATE;
8337c478bd9Sstevel@tonic-gate 	    return Z_OK;
8347c478bd9Sstevel@tonic-gate 	}
8357c478bd9Sstevel@tonic-gate     }
8367c478bd9Sstevel@tonic-gate 
8377c478bd9Sstevel@tonic-gate     Assert(strm->avail_out > 0, "bug2");
8387c478bd9Sstevel@tonic-gate 
8397c478bd9Sstevel@tonic-gate     if (flush != Z_FINISH) return Z_OK;
8407c478bd9Sstevel@tonic-gate     if (state->noheader) return Z_STREAM_END;
8417c478bd9Sstevel@tonic-gate 
8427c478bd9Sstevel@tonic-gate     /* Write the zlib trailer (adler32) */
8437c478bd9Sstevel@tonic-gate     putShortMSB(state, (uInt)(state->adler >> 16));
8447c478bd9Sstevel@tonic-gate     putShortMSB(state, (uInt)(state->adler & 0xffff));
8457c478bd9Sstevel@tonic-gate     flush_pending(strm);
8467c478bd9Sstevel@tonic-gate     /* If avail_out is zero, the application will call deflate again
8477c478bd9Sstevel@tonic-gate      * to flush the rest.
8487c478bd9Sstevel@tonic-gate      */
8497c478bd9Sstevel@tonic-gate     state->noheader = -1; /* write the trailer only once! */
8507c478bd9Sstevel@tonic-gate     return state->pending != 0 ? Z_OK : Z_STREAM_END;
8517c478bd9Sstevel@tonic-gate }
8527c478bd9Sstevel@tonic-gate 
8537c478bd9Sstevel@tonic-gate /* ========================================================================= */
deflateEnd(strm)8547c478bd9Sstevel@tonic-gate int deflateEnd (strm)
8557c478bd9Sstevel@tonic-gate     z_stream *strm;
8567c478bd9Sstevel@tonic-gate {
8577c478bd9Sstevel@tonic-gate     deflate_state *state = (deflate_state *) strm->state;
8587c478bd9Sstevel@tonic-gate 
8597c478bd9Sstevel@tonic-gate     if (strm == Z_NULL || state == Z_NULL) return Z_STREAM_ERROR;
8607c478bd9Sstevel@tonic-gate 
8617c478bd9Sstevel@tonic-gate     TRY_FREE(strm, state->window, state->w_size * 2 * sizeof(Byte));
8627c478bd9Sstevel@tonic-gate     TRY_FREE(strm, state->prev, state->w_size * sizeof(Pos));
8637c478bd9Sstevel@tonic-gate     TRY_FREE(strm, state->head, state->hash_size * sizeof(Pos));
8647c478bd9Sstevel@tonic-gate     TRY_FREE(strm, state->pending_buf, state->lit_bufsize * 2 * sizeof(ush));
8657c478bd9Sstevel@tonic-gate 
8667c478bd9Sstevel@tonic-gate     ZFREE(strm, state, sizeof(deflate_state));
8677c478bd9Sstevel@tonic-gate     strm->state = Z_NULL;
8687c478bd9Sstevel@tonic-gate 
8697c478bd9Sstevel@tonic-gate     return Z_OK;
8707c478bd9Sstevel@tonic-gate }
8717c478bd9Sstevel@tonic-gate 
8727c478bd9Sstevel@tonic-gate /* ===========================================================================
8737c478bd9Sstevel@tonic-gate  * Read a new buffer from the current input stream, update the adler32
8747c478bd9Sstevel@tonic-gate  * and total number of bytes read.
8757c478bd9Sstevel@tonic-gate  */
read_buf(strm,buf,size)8767c478bd9Sstevel@tonic-gate local int read_buf(strm, buf, size)
8777c478bd9Sstevel@tonic-gate     z_stream *strm;
8787c478bd9Sstevel@tonic-gate     charf *buf;
8797c478bd9Sstevel@tonic-gate     unsigned size;
8807c478bd9Sstevel@tonic-gate {
8817c478bd9Sstevel@tonic-gate     unsigned len = strm->avail_in;
8827c478bd9Sstevel@tonic-gate     deflate_state *state = (deflate_state *) strm->state;
8837c478bd9Sstevel@tonic-gate 
8847c478bd9Sstevel@tonic-gate     if (len > size) len = size;
8857c478bd9Sstevel@tonic-gate     if (len == 0) return 0;
8867c478bd9Sstevel@tonic-gate 
8877c478bd9Sstevel@tonic-gate     strm->avail_in  -= len;
8887c478bd9Sstevel@tonic-gate 
8897c478bd9Sstevel@tonic-gate     if (!state->noheader) {
8907c478bd9Sstevel@tonic-gate         state->adler = adler32(state->adler, strm->next_in, len);
8917c478bd9Sstevel@tonic-gate     }
8927c478bd9Sstevel@tonic-gate     zmemcpy(buf, strm->next_in, len);
8937c478bd9Sstevel@tonic-gate     strm->next_in  += len;
8947c478bd9Sstevel@tonic-gate     strm->total_in += len;
8957c478bd9Sstevel@tonic-gate 
8967c478bd9Sstevel@tonic-gate     return (int)len;
8977c478bd9Sstevel@tonic-gate }
8987c478bd9Sstevel@tonic-gate 
8997c478bd9Sstevel@tonic-gate /* ===========================================================================
9007c478bd9Sstevel@tonic-gate  * Initialize the "longest match" routines for a new zlib stream
9017c478bd9Sstevel@tonic-gate  */
lm_init(s)9027c478bd9Sstevel@tonic-gate local void lm_init (s)
9037c478bd9Sstevel@tonic-gate     deflate_state *s;
9047c478bd9Sstevel@tonic-gate {
9057c478bd9Sstevel@tonic-gate     s->window_size = (ulg)2L*s->w_size;
9067c478bd9Sstevel@tonic-gate 
9077c478bd9Sstevel@tonic-gate     CLEAR_HASH(s);
9087c478bd9Sstevel@tonic-gate 
9097c478bd9Sstevel@tonic-gate     /* Set the default configuration parameters:
9107c478bd9Sstevel@tonic-gate      */
9117c478bd9Sstevel@tonic-gate     s->max_lazy_match   = configuration_table[s->level].max_lazy;
9127c478bd9Sstevel@tonic-gate     s->good_match       = configuration_table[s->level].good_length;
9137c478bd9Sstevel@tonic-gate     s->nice_match       = configuration_table[s->level].nice_length;
9147c478bd9Sstevel@tonic-gate     s->max_chain_length = configuration_table[s->level].max_chain;
9157c478bd9Sstevel@tonic-gate 
9167c478bd9Sstevel@tonic-gate     s->strstart = 0;
9177c478bd9Sstevel@tonic-gate     s->block_start = 0L;
9187c478bd9Sstevel@tonic-gate     s->lookahead = 0;
9197c478bd9Sstevel@tonic-gate     s->match_length = MIN_MATCH-1;
9207c478bd9Sstevel@tonic-gate     s->match_available = 0;
9217c478bd9Sstevel@tonic-gate     s->ins_h = 0;
9227c478bd9Sstevel@tonic-gate #ifdef ASMV
9237c478bd9Sstevel@tonic-gate     match_init(); /* initialize the asm code */
9247c478bd9Sstevel@tonic-gate #endif
9257c478bd9Sstevel@tonic-gate }
9267c478bd9Sstevel@tonic-gate 
9277c478bd9Sstevel@tonic-gate /* ===========================================================================
9287c478bd9Sstevel@tonic-gate  * Set match_start to the longest match starting at the given string and
9297c478bd9Sstevel@tonic-gate  * return its length. Matches shorter or equal to prev_length are discarded,
9307c478bd9Sstevel@tonic-gate  * in which case the result is equal to prev_length and match_start is
9317c478bd9Sstevel@tonic-gate  * garbage.
9327c478bd9Sstevel@tonic-gate  * IN assertions: cur_match is the head of the hash chain for the current
9337c478bd9Sstevel@tonic-gate  *   string (strstart) and its distance is <= MAX_DIST, and prev_length >= 1
9347c478bd9Sstevel@tonic-gate  */
9357c478bd9Sstevel@tonic-gate #ifndef ASMV
9367c478bd9Sstevel@tonic-gate /* For 80x86 and 680x0, an optimized version will be provided in match.asm or
9377c478bd9Sstevel@tonic-gate  * match.S. The code will be functionally equivalent.
9387c478bd9Sstevel@tonic-gate  */
longest_match(s,cur_match)9397c478bd9Sstevel@tonic-gate local int longest_match(s, cur_match)
9407c478bd9Sstevel@tonic-gate     deflate_state *s;
9417c478bd9Sstevel@tonic-gate     IPos cur_match;                             /* current match */
9427c478bd9Sstevel@tonic-gate {
9437c478bd9Sstevel@tonic-gate     unsigned chain_length = s->max_chain_length;/* max hash chain length */
9447c478bd9Sstevel@tonic-gate     register Bytef *scan = s->window + s->strstart; /* current string */
9457c478bd9Sstevel@tonic-gate     register Bytef *match;                       /* matched string */
9467c478bd9Sstevel@tonic-gate     register int len;                           /* length of current match */
9477c478bd9Sstevel@tonic-gate     int best_len = s->prev_length;              /* best match length so far */
9487c478bd9Sstevel@tonic-gate     IPos limit = s->strstart > (IPos)MAX_DIST(s) ?
9497c478bd9Sstevel@tonic-gate         s->strstart - (IPos)MAX_DIST(s) : NIL;
9507c478bd9Sstevel@tonic-gate     /* Stop when cur_match becomes <= limit. To simplify the code,
9517c478bd9Sstevel@tonic-gate      * we prevent matches with the string of window index 0.
9527c478bd9Sstevel@tonic-gate      */
9537c478bd9Sstevel@tonic-gate     Posf *prev = s->prev;
9547c478bd9Sstevel@tonic-gate     uInt wmask = s->w_mask;
9557c478bd9Sstevel@tonic-gate 
9567c478bd9Sstevel@tonic-gate #ifdef UNALIGNED_OK
9577c478bd9Sstevel@tonic-gate     /* Compare two bytes at a time. Note: this is not always beneficial.
9587c478bd9Sstevel@tonic-gate      * Try with and without -DUNALIGNED_OK to check.
9597c478bd9Sstevel@tonic-gate      */
9607c478bd9Sstevel@tonic-gate     register Bytef *strend = s->window + s->strstart + MAX_MATCH - 1;
9617c478bd9Sstevel@tonic-gate     register ush scan_start = *(ushf*)scan;
9627c478bd9Sstevel@tonic-gate     register ush scan_end   = *(ushf*)(scan+best_len-1);
9637c478bd9Sstevel@tonic-gate #else
9647c478bd9Sstevel@tonic-gate     register Bytef *strend = s->window + s->strstart + MAX_MATCH;
9657c478bd9Sstevel@tonic-gate     register Byte scan_end1  = scan[best_len-1];
9667c478bd9Sstevel@tonic-gate     register Byte scan_end   = scan[best_len];
9677c478bd9Sstevel@tonic-gate #endif
9687c478bd9Sstevel@tonic-gate 
9697c478bd9Sstevel@tonic-gate     /* The code is optimized for HASH_BITS >= 8 and MAX_MATCH-2 multiple of 16.
9707c478bd9Sstevel@tonic-gate      * It is easy to get rid of this optimization if necessary.
9717c478bd9Sstevel@tonic-gate      */
9727c478bd9Sstevel@tonic-gate     Assert(s->hash_bits >= 8 && MAX_MATCH == 258, "Code too clever");
9737c478bd9Sstevel@tonic-gate 
9747c478bd9Sstevel@tonic-gate     /* Do not waste too much time if we already have a good match: */
9757c478bd9Sstevel@tonic-gate     if (s->prev_length >= s->good_match) {
9767c478bd9Sstevel@tonic-gate         chain_length >>= 2;
9777c478bd9Sstevel@tonic-gate     }
9787c478bd9Sstevel@tonic-gate     Assert((ulg)s->strstart <= s->window_size-MIN_LOOKAHEAD, "need lookahead");
9797c478bd9Sstevel@tonic-gate 
9807c478bd9Sstevel@tonic-gate     do {
9817c478bd9Sstevel@tonic-gate         Assert(cur_match < s->strstart, "no future");
9827c478bd9Sstevel@tonic-gate         match = s->window + cur_match;
9837c478bd9Sstevel@tonic-gate 
9847c478bd9Sstevel@tonic-gate         /* Skip to next match if the match length cannot increase
9857c478bd9Sstevel@tonic-gate          * or if the match length is less than 2:
9867c478bd9Sstevel@tonic-gate          */
9877c478bd9Sstevel@tonic-gate #if (defined(UNALIGNED_OK) && MAX_MATCH == 258)
9887c478bd9Sstevel@tonic-gate         /* This code assumes sizeof(unsigned short) == 2. Do not use
9897c478bd9Sstevel@tonic-gate          * UNALIGNED_OK if your compiler uses a different size.
9907c478bd9Sstevel@tonic-gate          */
9917c478bd9Sstevel@tonic-gate         if (*(ushf*)(match+best_len-1) != scan_end ||
9927c478bd9Sstevel@tonic-gate             *(ushf*)match != scan_start) continue;
9937c478bd9Sstevel@tonic-gate 
9947c478bd9Sstevel@tonic-gate         /* It is not necessary to compare scan[2] and match[2] since they are
9957c478bd9Sstevel@tonic-gate          * always equal when the other bytes match, given that the hash keys
9967c478bd9Sstevel@tonic-gate          * are equal and that HASH_BITS >= 8. Compare 2 bytes at a time at
9977c478bd9Sstevel@tonic-gate          * strstart+3, +5, ... up to strstart+257. We check for insufficient
9987c478bd9Sstevel@tonic-gate          * lookahead only every 4th comparison; the 128th check will be made
9997c478bd9Sstevel@tonic-gate          * at strstart+257. If MAX_MATCH-2 is not a multiple of 8, it is
10007c478bd9Sstevel@tonic-gate          * necessary to put more guard bytes at the end of the window, or
10017c478bd9Sstevel@tonic-gate          * to check more often for insufficient lookahead.
10027c478bd9Sstevel@tonic-gate          */
10037c478bd9Sstevel@tonic-gate         Assert(scan[2] == match[2], "scan[2]?");
10047c478bd9Sstevel@tonic-gate         scan++, match++;
10057c478bd9Sstevel@tonic-gate         do {
10067c478bd9Sstevel@tonic-gate         } while (*(ushf*)(scan+=2) == *(ushf*)(match+=2) &&
10077c478bd9Sstevel@tonic-gate                  *(ushf*)(scan+=2) == *(ushf*)(match+=2) &&
10087c478bd9Sstevel@tonic-gate                  *(ushf*)(scan+=2) == *(ushf*)(match+=2) &&
10097c478bd9Sstevel@tonic-gate                  *(ushf*)(scan+=2) == *(ushf*)(match+=2) &&
10107c478bd9Sstevel@tonic-gate                  scan < strend);
10117c478bd9Sstevel@tonic-gate         /* The funny "do {}" generates better code on most compilers */
10127c478bd9Sstevel@tonic-gate 
10137c478bd9Sstevel@tonic-gate         /* Here, scan <= window+strstart+257 */
10147c478bd9Sstevel@tonic-gate         Assert(scan <= s->window+(unsigned)(s->window_size-1), "wild scan");
10157c478bd9Sstevel@tonic-gate         if (*scan == *match) scan++;
10167c478bd9Sstevel@tonic-gate 
10177c478bd9Sstevel@tonic-gate         len = (MAX_MATCH - 1) - (int)(strend-scan);
10187c478bd9Sstevel@tonic-gate         scan = strend - (MAX_MATCH-1);
10197c478bd9Sstevel@tonic-gate 
10207c478bd9Sstevel@tonic-gate #else /* UNALIGNED_OK */
10217c478bd9Sstevel@tonic-gate 
10227c478bd9Sstevel@tonic-gate         if (match[best_len]   != scan_end  ||
10237c478bd9Sstevel@tonic-gate             match[best_len-1] != scan_end1 ||
10247c478bd9Sstevel@tonic-gate             *match            != *scan     ||
10257c478bd9Sstevel@tonic-gate             *++match          != scan[1])      continue;
10267c478bd9Sstevel@tonic-gate 
10277c478bd9Sstevel@tonic-gate         /* The check at best_len-1 can be removed because it will be made
10287c478bd9Sstevel@tonic-gate          * again later. (This heuristic is not always a win.)
10297c478bd9Sstevel@tonic-gate          * It is not necessary to compare scan[2] and match[2] since they
10307c478bd9Sstevel@tonic-gate          * are always equal when the other bytes match, given that
10317c478bd9Sstevel@tonic-gate          * the hash keys are equal and that HASH_BITS >= 8.
10327c478bd9Sstevel@tonic-gate          */
10337c478bd9Sstevel@tonic-gate         scan += 2, match++;
10347c478bd9Sstevel@tonic-gate         Assert(*scan == *match, "match[2]?");
10357c478bd9Sstevel@tonic-gate 
10367c478bd9Sstevel@tonic-gate         /* We check for insufficient lookahead only every 8th comparison;
10377c478bd9Sstevel@tonic-gate          * the 256th check will be made at strstart+258.
10387c478bd9Sstevel@tonic-gate          */
10397c478bd9Sstevel@tonic-gate         do {
10407c478bd9Sstevel@tonic-gate         } while (*++scan == *++match && *++scan == *++match &&
10417c478bd9Sstevel@tonic-gate                  *++scan == *++match && *++scan == *++match &&
10427c478bd9Sstevel@tonic-gate                  *++scan == *++match && *++scan == *++match &&
10437c478bd9Sstevel@tonic-gate                  *++scan == *++match && *++scan == *++match &&
10447c478bd9Sstevel@tonic-gate                  scan < strend);
10457c478bd9Sstevel@tonic-gate 
10467c478bd9Sstevel@tonic-gate         Assert(scan <= s->window+(unsigned)(s->window_size-1), "wild scan");
10477c478bd9Sstevel@tonic-gate 
10487c478bd9Sstevel@tonic-gate         len = MAX_MATCH - (int)(strend - scan);
10497c478bd9Sstevel@tonic-gate         scan = strend - MAX_MATCH;
10507c478bd9Sstevel@tonic-gate 
10517c478bd9Sstevel@tonic-gate #endif /* UNALIGNED_OK */
10527c478bd9Sstevel@tonic-gate 
10537c478bd9Sstevel@tonic-gate         if (len > best_len) {
10547c478bd9Sstevel@tonic-gate             s->match_start = cur_match;
10557c478bd9Sstevel@tonic-gate             best_len = len;
10567c478bd9Sstevel@tonic-gate             if (len >= s->nice_match) break;
10577c478bd9Sstevel@tonic-gate #ifdef UNALIGNED_OK
10587c478bd9Sstevel@tonic-gate             scan_end = *(ushf*)(scan+best_len-1);
10597c478bd9Sstevel@tonic-gate #else
10607c478bd9Sstevel@tonic-gate             scan_end1  = scan[best_len-1];
10617c478bd9Sstevel@tonic-gate             scan_end   = scan[best_len];
10627c478bd9Sstevel@tonic-gate #endif
10637c478bd9Sstevel@tonic-gate         }
10647c478bd9Sstevel@tonic-gate     } while ((cur_match = prev[cur_match & wmask]) > limit
10657c478bd9Sstevel@tonic-gate              && --chain_length != 0);
10667c478bd9Sstevel@tonic-gate 
10677c478bd9Sstevel@tonic-gate     return best_len;
10687c478bd9Sstevel@tonic-gate }
10697c478bd9Sstevel@tonic-gate #endif /* ASMV */
10707c478bd9Sstevel@tonic-gate 
10717c478bd9Sstevel@tonic-gate #ifdef DEBUG_ZLIB
10727c478bd9Sstevel@tonic-gate /* ===========================================================================
10737c478bd9Sstevel@tonic-gate  * Check that the match at match_start is indeed a match.
10747c478bd9Sstevel@tonic-gate  */
check_match(s,start,match,length)10757c478bd9Sstevel@tonic-gate local void check_match(s, start, match, length)
10767c478bd9Sstevel@tonic-gate     deflate_state *s;
10777c478bd9Sstevel@tonic-gate     IPos start, match;
10787c478bd9Sstevel@tonic-gate     int length;
10797c478bd9Sstevel@tonic-gate {
10807c478bd9Sstevel@tonic-gate     /* check that the match is indeed a match */
10817c478bd9Sstevel@tonic-gate     if (memcmp((charf *)s->window + match,
10827c478bd9Sstevel@tonic-gate                 (charf *)s->window + start, length) != EQUAL) {
10837c478bd9Sstevel@tonic-gate         fprintf(stderr,
10847c478bd9Sstevel@tonic-gate             " start %u, match %u, length %d\n",
10857c478bd9Sstevel@tonic-gate             start, match, length);
10867c478bd9Sstevel@tonic-gate         do { fprintf(stderr, "%c%c", s->window[match++],
10877c478bd9Sstevel@tonic-gate                      s->window[start++]); } while (--length != 0);
10887c478bd9Sstevel@tonic-gate         z_error("invalid match");
10897c478bd9Sstevel@tonic-gate     }
10907c478bd9Sstevel@tonic-gate     if (verbose > 1) {
10917c478bd9Sstevel@tonic-gate         fprintf(stderr,"\\[%d,%d]", start-match, length);
10927c478bd9Sstevel@tonic-gate         do { putc(s->window[start++], stderr); } while (--length != 0);
10937c478bd9Sstevel@tonic-gate     }
10947c478bd9Sstevel@tonic-gate }
10957c478bd9Sstevel@tonic-gate #else
10967c478bd9Sstevel@tonic-gate #  define check_match(s, start, match, length)
10977c478bd9Sstevel@tonic-gate #endif
10987c478bd9Sstevel@tonic-gate 
10997c478bd9Sstevel@tonic-gate /* ===========================================================================
11007c478bd9Sstevel@tonic-gate  * Fill the window when the lookahead becomes insufficient.
11017c478bd9Sstevel@tonic-gate  * Updates strstart and lookahead.
11027c478bd9Sstevel@tonic-gate  *
11037c478bd9Sstevel@tonic-gate  * IN assertion: lookahead < MIN_LOOKAHEAD
11047c478bd9Sstevel@tonic-gate  * OUT assertions: strstart <= window_size-MIN_LOOKAHEAD
11057c478bd9Sstevel@tonic-gate  *    At least one byte has been read, or avail_in == 0; reads are
11067c478bd9Sstevel@tonic-gate  *    performed for at least two bytes (required for the zip translate_eol
11077c478bd9Sstevel@tonic-gate  *    option -- not supported here).
11087c478bd9Sstevel@tonic-gate  */
fill_window(s)11097c478bd9Sstevel@tonic-gate local void fill_window(s)
11107c478bd9Sstevel@tonic-gate     deflate_state *s;
11117c478bd9Sstevel@tonic-gate {
11127c478bd9Sstevel@tonic-gate     register unsigned n, m;
11137c478bd9Sstevel@tonic-gate     register Posf *p;
11147c478bd9Sstevel@tonic-gate     unsigned more;    /* Amount of free space at the end of the window. */
11157c478bd9Sstevel@tonic-gate     uInt wsize = s->w_size;
11167c478bd9Sstevel@tonic-gate 
11177c478bd9Sstevel@tonic-gate     do {
11187c478bd9Sstevel@tonic-gate         more = (unsigned)(s->window_size -(ulg)s->lookahead -(ulg)s->strstart);
11197c478bd9Sstevel@tonic-gate 
11207c478bd9Sstevel@tonic-gate         /* Deal with !@#$% 64K limit: */
11217c478bd9Sstevel@tonic-gate         if (more == 0 && s->strstart == 0 && s->lookahead == 0) {
11227c478bd9Sstevel@tonic-gate             more = wsize;
11237c478bd9Sstevel@tonic-gate         } else if (more == (unsigned)(-1)) {
11247c478bd9Sstevel@tonic-gate             /* Very unlikely, but possible on 16 bit machine if strstart == 0
11257c478bd9Sstevel@tonic-gate              * and lookahead == 1 (input done one byte at time)
11267c478bd9Sstevel@tonic-gate              */
11277c478bd9Sstevel@tonic-gate             more--;
11287c478bd9Sstevel@tonic-gate 
11297c478bd9Sstevel@tonic-gate         /* If the window is almost full and there is insufficient lookahead,
11307c478bd9Sstevel@tonic-gate          * move the upper half to the lower one to make room in the upper half.
11317c478bd9Sstevel@tonic-gate          */
11327c478bd9Sstevel@tonic-gate         } else if (s->strstart >= wsize+MAX_DIST(s)) {
11337c478bd9Sstevel@tonic-gate 
11347c478bd9Sstevel@tonic-gate             /* By the IN assertion, the window is not empty so we can't confuse
11357c478bd9Sstevel@tonic-gate              * more == 0 with more == 64K on a 16 bit machine.
11367c478bd9Sstevel@tonic-gate              */
11377c478bd9Sstevel@tonic-gate             zmemcpy((charf *)s->window, (charf *)s->window+wsize,
11387c478bd9Sstevel@tonic-gate                    (unsigned)wsize);
11397c478bd9Sstevel@tonic-gate             s->match_start -= wsize;
11407c478bd9Sstevel@tonic-gate             s->strstart    -= wsize; /* we now have strstart >= MAX_DIST */
11417c478bd9Sstevel@tonic-gate 
11427c478bd9Sstevel@tonic-gate             s->block_start -= (long) wsize;
11437c478bd9Sstevel@tonic-gate 
11447c478bd9Sstevel@tonic-gate             /* Slide the hash table (could be avoided with 32 bit values
11457c478bd9Sstevel@tonic-gate                at the expense of memory usage):
11467c478bd9Sstevel@tonic-gate              */
11477c478bd9Sstevel@tonic-gate             n = s->hash_size;
11487c478bd9Sstevel@tonic-gate             p = &s->head[n];
11497c478bd9Sstevel@tonic-gate             do {
11507c478bd9Sstevel@tonic-gate                 m = *--p;
11517c478bd9Sstevel@tonic-gate                 *p = (Pos)(m >= wsize ? m-wsize : NIL);
11527c478bd9Sstevel@tonic-gate             } while (--n);
11537c478bd9Sstevel@tonic-gate 
11547c478bd9Sstevel@tonic-gate             n = wsize;
11557c478bd9Sstevel@tonic-gate             p = &s->prev[n];
11567c478bd9Sstevel@tonic-gate             do {
11577c478bd9Sstevel@tonic-gate                 m = *--p;
11587c478bd9Sstevel@tonic-gate                 *p = (Pos)(m >= wsize ? m-wsize : NIL);
11597c478bd9Sstevel@tonic-gate                 /* If n is not on any hash chain, prev[n] is garbage but
11607c478bd9Sstevel@tonic-gate                  * its value will never be used.
11617c478bd9Sstevel@tonic-gate                  */
11627c478bd9Sstevel@tonic-gate             } while (--n);
11637c478bd9Sstevel@tonic-gate 
11647c478bd9Sstevel@tonic-gate             more += wsize;
11657c478bd9Sstevel@tonic-gate         }
11667c478bd9Sstevel@tonic-gate         if (s->strm->avail_in == 0) return;
11677c478bd9Sstevel@tonic-gate 
11687c478bd9Sstevel@tonic-gate         /* If there was no sliding:
11697c478bd9Sstevel@tonic-gate          *    strstart <= WSIZE+MAX_DIST-1 && lookahead <= MIN_LOOKAHEAD - 1 &&
11707c478bd9Sstevel@tonic-gate          *    more == window_size - lookahead - strstart
11717c478bd9Sstevel@tonic-gate          * => more >= window_size - (MIN_LOOKAHEAD-1 + WSIZE + MAX_DIST-1)
11727c478bd9Sstevel@tonic-gate          * => more >= window_size - 2*WSIZE + 2
11737c478bd9Sstevel@tonic-gate          * In the BIG_MEM or MMAP case (not yet supported),
11747c478bd9Sstevel@tonic-gate          *   window_size == input_size + MIN_LOOKAHEAD  &&
11757c478bd9Sstevel@tonic-gate          *   strstart + s->lookahead <= input_size => more >= MIN_LOOKAHEAD.
11767c478bd9Sstevel@tonic-gate          * Otherwise, window_size == 2*WSIZE so more >= 2.
11777c478bd9Sstevel@tonic-gate          * If there was sliding, more >= WSIZE. So in all cases, more >= 2.
11787c478bd9Sstevel@tonic-gate          */
11797c478bd9Sstevel@tonic-gate         Assert(