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