/*
 * Copyright 2007 Sun Microsystems, Inc.  All rights reserved.
 * Use is subject to license terms.
 */

/*
 * Updated from zlib-1.0.4 to zlib-1.1.3 by James Carlson.
 *
 * This file is derived from various .h and .c files from the zlib-1.0.4
 * distribution by Jean-loup Gailly and Mark Adler, with some additions
 * by Paul Mackerras to aid in implementing Deflate compression and
 * decompression for PPP packets.  See zlib.h for conditions of
 * distribution and use.
 *
 * Changes that have been made include:
 * - added Z_PACKET_FLUSH (see zlib.h for details)
 * - added inflateIncomp and deflateOutputPending
 * - allow strm->next_out to be NULL, meaning discard the output
 *
 * $Id: zlib.c,v 1.11 1998/09/13 23:37:12 paulus Exp $
 */

/*
 *  ==FILEVERSION 971210==
 *
 * This marker is used by the Linux installation script to determine
 * whether an up-to-date version of this file is already installed.
 */

#define NO_DUMMY_DECL
#define NO_ZCFUNCS
#define MY_ZCALLOC

#if defined(__FreeBSD__) && (defined(KERNEL) || defined(_KERNEL))
#define inflate inflate_ppp     /* FreeBSD already has an inflate :-( */
#endif


/* +++ zutil.h */
/*
 *
 * zutil.h -- internal interface and configuration of the compression library
 * Copyright (C) 1995-1998 Jean-loup Gailly.
 * For conditions of distribution and use, see copyright notice in zlib.h
 */

/*
 * WARNING: this file should *not* be used by applications. It is part
 * of the implementation of the compression library and is subject to
 * change. Applications should only use zlib.h.
 */

/* From: zutil.h,v 1.16 1996/07/24 13:41:13 me Exp $ */

#ifndef _Z_UTIL_H
#define _Z_UTIL_H

#include "zlib.h"

#if defined(KERNEL) || defined(_KERNEL)
/* Assume this is a *BSD or SVR4 kernel */
#include <sys/types.h>
#include <sys/time.h>
#include <sys/systm.h>
#ifdef SOL2
#include <sys/cmn_err.h>
#endif
#define HAVE_MEMCPY
#define memcmp          bcmp

#else
#if defined(__KERNEL__)
/* Assume this is a Linux kernel */
#include <linux/string.h>
#define HAVE_MEMCPY

#else /* not kernel */

#include <stddef.h>
#ifdef NO_ERRNO_H
extern int errno;
#else
#include <errno.h>
#endif
#ifdef STDC
#include <string.h>
#include <stdlib.h>
#endif
#endif /* __KERNEL__ */
#endif /* _KERNEL || KERNEL */

#ifndef local
#define local static
#endif
/* compile with -Dlocal if your debugger can't find static symbols */

typedef unsigned char  uch;
typedef uch FAR uchf;
typedef unsigned short ush;
typedef ush FAR ushf;
typedef unsigned long  ulg;

static const char *z_errmsg[10]; /* indexed by 2-zlib_error */
/* (size given to avoid silly warnings with Visual C++) */

#define ERR_MSG(err) z_errmsg[Z_NEED_DICT-(err)]

#define ERR_RETURN(strm, err) \
        return (strm->msg = ERR_MSG(err), (err))
/* To be used only when the state is known to be valid */

        /* common constants */

#ifndef DEF_WBITS
#define DEF_WBITS MAX_WBITS
#endif
/* default windowBits for decompression. MAX_WBITS is for compression only */

#if MAX_MEM_LEVEL >= 8
#define DEF_MEM_LEVEL 8
#else
#define DEF_MEM_LEVEL  MAX_MEM_LEVEL
#endif
/* default memLevel */

#define STORED_BLOCK 0
#define STATIC_TREES 1
#define DYN_TREES    2
/* The three kinds of block type */

#define MIN_MATCH  3
#define MAX_MATCH  258
/* The minimum and maximum match lengths */

#define PRESET_DICT 0x20 /* preset dictionary flag in zlib header */

        /* target dependencies */

#ifdef MSDOS
#define OS_CODE  0x00
#ifdef __TURBOC__
#include <alloc.h>
#else /* MSC or DJGPP */
#include <malloc.h>
#endif
#endif

#ifdef OS2
#define OS_CODE  0x06
#endif

#ifdef WIN32 /* Window 95 & Windows NT */
#define OS_CODE  0x0b
#endif

#if defined(VAXC) || defined(VMS)
#define OS_CODE  0x02
#define F_OPEN(name, mode) \
        fopen((name), (mode), "mbc=60", "ctx=stm", "rfm=fix", "mrs=512")
#endif

#ifdef AMIGA
#define OS_CODE  0x01
#endif

#if defined(ATARI) || defined(atarist)
#define OS_CODE  0x05
#endif

#ifdef MACOS
#define OS_CODE  0x07
#endif

#ifdef __50SERIES /* Prime/PRIMOS */
#define OS_CODE  0x0F
#endif

#ifdef TOPS20
#define OS_CODE  0x0a
#endif

#if defined(_BEOS_) || defined(RISCOS)
#define fdopen(fd, mode) NULL /* No fdopen() */
#endif

        /* Common defaults */

#ifndef OS_CODE
#define OS_CODE  0x03  /* assume Unix */
#endif

#ifndef F_OPEN
#define F_OPEN(name, mode) fopen((name), (mode))
#endif

        /* functions */

#ifdef HAVE_STRERROR
extern char *strerror OF((int));
#define zstrerror(errnum) strerror(errnum)
#else
#define zstrerror(errnum) ""
#endif

#if defined(pyr)
#define NO_MEMCPY
#endif
#if (defined(M_I86SM) || defined(M_I86MM)) && !defined(_MSC_VER)
/*
 * Use our own functions for small and medium model with MSC <= 5.0.
 * You may have to use the same strategy for Borland C (untested).
 */
#define NO_MEMCPY
#endif
#if defined(STDC) && !defined(HAVE_MEMCPY) && !defined(NO_MEMCPY)
#define HAVE_MEMCPY
#endif
#ifdef HAVE_MEMCPY
#ifdef SMALL_MEDIUM /* MSDOS small or medium model */
#define zmemcpy _fmemcpy
#define zmemcmp _fmemcmp
#define zmemzero(dest, len) _fmemset(dest, 0, len)
#else
#define zmemcpy (void) memcpy
#define zmemcmp memcmp
#define zmemzero(dest, len) (void) memset(dest, 0, len)
#endif
#else
extern void zmemcpy  OF((Bytef* dest, const Bytef* source, uInt len));
extern int  zmemcmp  OF((const Bytef* s1, const Bytef* s2, uInt len));
extern void zmemzero OF((Bytef* dest, uInt len));
#endif

/* Diagnostic functions */
#ifdef DEBUG_ZLIB
#include <stdio.h>
#ifndef verbose
#define verbose 0
#endif
extern void z_error    OF((char *m));
#define Assert(cond, msg) { if (!(cond)) z_error(msg); }
#define Trace(x) {if (z_verbose >= 0) fprintf x; }
#define Tracev(x) {if (z_verbose > 0) fprintf x; }
#define Tracevv(x) {if (z_verbose > 1) fprintf x; }
#define Tracec(c, x) {if (z_verbose > 0 && (c)) fprintf x; }
#define Tracecv(c, x) {if (z_verbose > 1 && (c)) fprintf x; }
#else
#if defined(SOL2) && defined(DEBUG)
#define Assert(cond, msg)       ((cond) ? ((void)0) : panic(msg))
#else
#define Assert(cond, msg)       ((void)0)
#endif
#define Trace(x)        ((void)0)
#define Tracev(x)       ((void)0)
#define Tracevv(x)      ((void)0)
#define Tracec(c, x)    ((void)0)
#define Tracecv(c, x)   ((void)0)
#endif


typedef uLong (*check_func) OF((uLong check, const Bytef *buf, uInt len));

/* voidpf zcalloc OF((voidpf opaque, unsigned items, unsigned size)); */
/* void   zcfree  OF((voidpf opaque, voidpf ptr)); */

#define ZALLOC(strm, items, size) \
        (*((strm)->zalloc))((strm)->opaque, (items), (size))
#define ZFREE(strm, addr)  (*((strm)->zfree))((strm)->opaque, (voidpf)(addr))
#define TRY_FREE(s, p) {if (p) ZFREE(s, p); }

#endif /* _Z_UTIL_H */
/* --- zutil.h */

/* +++ deflate.h */
/*
 * deflate.h -- internal compression state
 * Copyright (C) 1995-1998 Jean-loup Gailly
 * For conditions of distribution and use, see copyright notice in zlib.h
 */

/*
 * WARNING: this file should *not* be used by applications. It is part
 * of the implementation of the compression library and is subject to
 * change. Applications should only use zlib.h.
 */

/* From: deflate.h,v 1.10 1996/07/02 12:41:00 me Exp $ */

#ifndef _DEFLATE_H
#define _DEFLATE_H

/* #include "zutil.h" */

/*
 * ===========================================================================
 * Internal compression state.
 */

#define LENGTH_CODES 29
/* number of length codes, not counting the special END_BLOCK code */

#define LITERALS  256
/* number of literal bytes 0..255 */

#define L_CODES (LITERALS+1+LENGTH_CODES)
/* number of Literal or Length codes, including the END_BLOCK code */

#define D_CODES   30
/* number of distance codes */

#define BL_CODES  19
/* number of codes used to transfer the bit lengths */

#define HEAP_SIZE (2*L_CODES+1)
/* maximum heap size */

#define MAX_BITS 15
/* All codes must not exceed MAX_BITS bits */

#define INIT_STATE    42
#define BUSY_STATE   113
#define FINISH_STATE 666
/* Stream status */


/* Data structure describing a single value and its code string. */
typedef struct ct_data_s {
        union {
                ush freq;       /* frequency count */
                ush code;       /* bit string */
        } fc;
        union {
                ush dad;        /* father node in Huffman tree */
                ush len;        /* length of bit string */
        } dl;
} FAR ct_data;

#define Freq fc.freq
#define Code fc.code
#define Dad  dl.dad
#define Len  dl.len

typedef struct static_tree_desc_s  static_tree_desc;

typedef struct tree_desc_s {
        ct_data *dyn_tree;      /* the dynamic tree */
        int     max_code;       /* largest code with non zero frequency */
        static_tree_desc *stat_desc;    /* the corresponding static tree */
} FAR tree_desc;

typedef ush Pos;
typedef Pos FAR Posf;
typedef unsigned IPos;

/*
 * A Pos is an index in the character window. We use short instead of
 * int to save space in the various tables. IPos is used only for
 * parameter passing.
 */

typedef struct deflate_state {
        z_streamp strm; /* pointer back to this zlib stream */
        int   status;   /* as the name implies */
        Bytef *pending_buf;     /* output still pending */
        ulg   pending_buf_size; /* size of pending_buf */
        Bytef *pending_out;     /* next pending byte to output to the stream */
        int   pending;  /* nb of bytes in the pending buffer */
        int   noheader; /* suppress zlib header and adler32 */
        Byte  data_type;        /* UNKNOWN, BINARY or ASCII */
        Byte  method;   /* STORED (for zip only) or DEFLATED */
        /* value of flush param for previous deflate call */
        int   last_flush;

        /* used by deflate.c: */

        uInt  w_size;   /* LZ77 window size (32K by default) */
        uInt  w_bits;   /* log2(w_size)  (8..16) */
        uInt  w_mask;   /* w_size - 1 */

        Bytef *window;
        /*
         * Sliding window. Input bytes are read into the second half
         * of the window, and move to the first half later to keep a
         * dictionary of at least wSize bytes. With this organization,
         * matches are limited to a distance of wSize-MAX_MATCH bytes,
         * but this ensures that IO is always performed with a length
         * multiple of the block size. Also, it limits the window size
         * to 64K, which is quite useful on MSDOS.  To do: use the
         * user input buffer as sliding window.
         */

        ulg window_size;
        /*
         * Actual size of window: 2*wSize, except when the user input
         * buffer is directly used as sliding window.
         */

        Posf *prev;
        /*
         * Link to older string with same hash index. To limit the
         * size of this array to 64K, this link is maintained only for
         * the last 32K strings.  An index in this array is thus a
         * window index modulo 32K.
         */

        Posf *head;     /* Heads of the hash chains or NIL. */

        uInt  ins_h;    /* hash index of string to be inserted */
        uInt  hash_size;        /* number of elements in hash table */
        uInt  hash_bits;        /* log2(hash_size) */
        uInt  hash_mask;        /* hash_size-1 */

        uInt  hash_shift;
        /*
         * Number of bits by which ins_h must be shifted at each input
         * step. It must be such that after MIN_MATCH steps, the
         * oldest byte no longer takes part in the hash key, that is:
         * hash_shift * MIN_MATCH >= hash_bits
         */

        long block_start;
        /*
         * Window position at the beginning of the current output
         * block. Gets negative when the window is moved backwards.
         */

        uInt match_length;      /* length of best match */
        IPos prev_match;        /* previous match */
        int match_available;    /* set if previous match exists */
        uInt strstart;  /* start of string to insert */
        uInt match_start;       /* start of matching string */
        uInt lookahead; /* number of valid bytes ahead in window */

        uInt prev_length;
        /*
         * Length of the best match at previous step. Matches not
         * greater than this are discarded. This is used in the lazy
         * match evaluation.
         */

        uInt max_chain_length;
        /*
         * To speed up deflation, hash chains are never searched
         * beyond *this length.  A higher limit improves compression
         * ratio but *degrades the speed.
         */

        uInt max_lazy_match;
        /*
         * Attempt to find a better match only when the current match
         * is strictly smaller than this value. This mechanism is used
         * only for compression levels >= 4.
         */
#define max_insert_length  max_lazy_match
        /*
         * Insert new strings in the hash table only if the match
         * length is not greater than this length. This saves time but
         * degrades compression.  max_insert_length is used only for
         * compression levels <= 3.
         */

        int level;      /* compression level (1..9) */
        int strategy;   /* favor or force Huffman coding */

        uInt good_match;
        /* Use a faster search when the previous match is longer than this */

        int nice_match; /* Stop searching when current match exceeds this */

        /* used by trees.c: */
        /* Didn't use ct_data typedef below to supress compiler warning */
        struct ct_data_s dyn_ltree[HEAP_SIZE];  /* literal and length tree */
        struct ct_data_s dyn_dtree[2*D_CODES+1];        /* distance tree */
        /* Huffman tree for bit lengths */
        struct ct_data_s bl_tree[2*BL_CODES+1];

        struct tree_desc_s l_desc;      /* desc. for literal tree */
        struct tree_desc_s d_desc;      /* desc. for distance tree */
        struct tree_desc_s bl_desc;     /* desc. for bit length tree */

        ush bl_count[MAX_BITS+1];
        /* number of codes at each bit length for an optimal tree */

        int heap[2*L_CODES+1];  /* heap used to build the Huffman trees */
        int heap_len;   /* number of elements in the heap */
        int heap_max;   /* element of largest frequency */
        /*
         * The sons of heap[n] are heap[2*n] and heap[2*n+1]. heap[0]
         * is not used.  The same heap array is used to build all
         * trees.
         */

        uch depth[2*L_CODES+1];
        /*
         * Depth of each subtree used as tie breaker for trees of
         * equal frequency
         */

        uchf *l_buf;    /* buffer for literals or lengths */

        uInt lit_bufsize;
        /*
         * Size of match buffer for literals/lengths.  There are 4
         * reasons for limiting lit_bufsize to 64K:
         *
         *   - frequencies can be kept in 16 bit counters
         *
         *   - if compression is not successful for the first block,
         *   all input data is still in the window so we can still
         *   emit a stored block even when input comes from standard
         *   input.  (This can also be done for all blocks if
         *   lit_bufsize is not greater than 32K.)
         *
         *   - if compression is not successful for a file smaller
         *   than 64K, we can even emit a stored file instead of a
         *   stored block (saving 5 bytes).  This is applicable only
         *   for zip (not gzip or zlib).
         *
         *   - creating new Huffman trees less frequently may not
         *   provide fast adaptation to changes in the input data
         *   statistics. (Take for example a binary file with poorly
         *   compressible code followed by a highly compressible
         *   string table.) Smaller buffer sizes give fast adaptation
         *   but have of course the overhead of transmitting trees
         *   more frequently.
         *
         *   - I can't count above 4
         */

        uInt last_lit;  /* running index in l_buf */

        ushf *d_buf;
        /*
         * Buffer for distances. To simplify the code, d_buf and l_buf
         * have the same number of elements. To use different lengths,
         * an extra flag array would be necessary.
         */

        ulg opt_len;    /* bit length of current block with optimal trees */
        ulg static_len; /* bit length of current block with static trees */
        uInt matches;   /* number of string matches in current block */
        int last_eob_len;       /* bit length of EOB code for last block */

        ulg compressed_len;     /* total bit length of compressed file PPP */
#ifdef DEBUG_ZLIB
        ulg bits_sent;  /* bit length of the compressed data */
#endif

        ush bi_buf;
        /*
         * Output buffer. bits are inserted starting at the bottom
         * (least significant bits).
         */
        int bi_valid;
        /*
         * Number of valid bits in bi_buf.  All bits above the last
         * valid bit are always zero.
         */

} FAR deflate_state;

/*
 * Output a byte on the stream.  IN assertion: there is enough room in
 * pending_buf.
 */
#define put_byte(s, c) {s->pending_buf[s->pending++] = (c); }


#define MIN_LOOKAHEAD (MAX_MATCH+MIN_MATCH+1)
/*
 * Minimum amount of lookahead, except at the end of the input file.
 * See deflate.c for comments about the MIN_MATCH+1.
 */

#define MAX_DIST(s)  ((s)->w_size-MIN_LOOKAHEAD)
/*
 * In order to simplify the code, particularly on 16 bit machines,
 * match distances are limited to MAX_DIST instead of WSIZE.
 */

        /* in trees.c */
void _tr_init           OF((deflate_state *s));
int  _tr_tally          OF((deflate_state *s, unsigned dist, unsigned lc));
void  _tr_flush_block   OF((deflate_state *s, charf *buf, ulg stored_len,
    int eof));
void _tr_align          OF((deflate_state *s));
void _tr_stored_block   OF((deflate_state *s, charf *buf, ulg stored_len,
    int eof));
void _tr_stored_type_only OF((deflate_state *));        /* PPP */

#define d_code(dist) \
        ((dist) < 256 ? _dist_code[dist] : _dist_code[256+((dist)>>7)])
/*
 * Mapping from a distance to a distance code. dist is the distance - 1 and
 * must not have side effects. _dist_code[256] and _dist_code[257] are never
 * used.
 */

#ifndef DEBUG_ZLIB
/* Inline versions of _tr_tally for speed: */

local uch _length_code[];
local uch _dist_code[];

#define _tr_tally_lit(s, c, flush) \
        {       uch cc = (c); \
                s->d_buf[s->last_lit] = 0; \
                s->l_buf[s->last_lit++] = cc; \
                s->dyn_ltree[cc].Freq++; \
                flush = (s->last_lit == s->lit_bufsize-1); \
        }
#define _tr_tally_dist(s, distance, length, flush) \
        {       uch len = (length); \
                ush dist = (distance); \
                s->d_buf[s->last_lit] = dist; \
                s->l_buf[s->last_lit++] = len; \
                dist--; \
                s->dyn_ltree[_length_code[len]+LITERALS+1].Freq++; \
                s->dyn_dtree[d_code(dist)].Freq++; \
                flush = (s->last_lit == s->lit_bufsize-1); \
        }
#else
#define _tr_tally_lit(s, c, flush) flush = _tr_tally(s, 0, c)
#define _tr_tally_dist(s, distance, length, flush) \
                flush = _tr_tally(s, distance, length)
#endif

#endif
/* --- deflate.h */

/* +++ deflate.c */
/*
 * deflate.c -- compress data using the deflation algorithm
 * Copyright (C) 1995-1998 Jean-loup Gailly.
 * For conditions of distribution and use, see copyright notice in zlib.h
 */

/*
 *  ALGORITHM
 *
 *      The "deflation" process depends on being able to identify portions
 *      of the input text which are identical to earlier input (within a
 *      sliding window trailing behind the input currently being processed).
 *
 *      The most straightforward technique turns out to be the fastest for
 *      most input files: try all possible matches and select the longest.
 *      The key feature of this algorithm is that insertions into the string
 *      dictionary are very simple and thus fast, and deletions are avoided
 *      completely. Insertions are performed at each input character, whereas
 *      string matches are performed only when the previous match ends. So it
 *      is preferable to spend more time in matches to allow very fast string
 *      insertions and avoid deletions. The matching algorithm for small
 *      strings is inspired from that of Rabin & Karp. A brute force approach
 *      is used to find longer strings when a small match has been found.
 *      A similar algorithm is used in comic (by Jan-Mark Wams) and freeze
 *      (by Leonid Broukhis).
 *         A previous version of this file used a more sophisticated algorithm
 *      (by Fiala and Greene) which is guaranteed to run in linear amortized
 *      time, but has a larger average cost, uses more memory and is patented.
 *      However the F&G algorithm may be faster for some highly redundant
 *      files if the parameter max_chain_length (described below) is too large.
 *
 *  ACKNOWLEDGEMENTS
 *
 *      The idea of lazy evaluation of matches is due to Jan-Mark Wams, and
 *      I found it in 'freeze' written by Leonid Broukhis.
 *      Thanks to many people for bug reports and testing.
 *
 *  REFERENCES
 *
 *      Deutsch, L.P.,"DEFLATE Compressed Data Format Specification".
 *      Available in ftp://ds.internic.net/rfc/rfc1951.txt
 *
 *      A description of the Rabin and Karp algorithm is given in the book
 *         "Algorithms" by R. Sedgewick, Addison-Wesley, p252.
 *
 *      Fiala,E.R., and Greene,D.H.
 *         Data Compression with Finite Windows, Comm.ACM, 32,4 (1989) 490-595
 *
 */

/* From: deflate.c,v 1.15 1996/07/24 13:40:58 me Exp $ */

/* #include "deflate.h" */

const char deflate_copyright[] =
" deflate 1.1.3 Copyright 1995-1998 Jean-loup Gailly ";
/*
 * If you use the zlib library in a product, an acknowledgment is
 * welcome in the documentation of your product. If for some reason
 * you cannot include such an acknowledgment, I would appreciate that
 * you keep this copyright string in the executable of your product.
 */

/*
 * ===========================================================================
 *  Function prototypes.
 */
typedef enum {
        /* block not completed, need more input or more output */
        need_more,
        block_done,     /* block flush performed */
        /* finish started, need only more output at next deflate */
        finish_started,
        finish_done     /* finish done, accept no more input or output */
} block_state;

typedef block_state (*compress_func) OF((deflate_state *s, int flush));
/* Compression function. Returns the block state after the call. */

local void fill_window  OF((deflate_state *s));
local block_state deflate_stored OF((deflate_state *s, int flush));
local block_state deflate_fast  OF((deflate_state *s, int flush));
local block_state deflate_slow  OF((deflate_state *s, int flush));
local void lm_init      OF((deflate_state *s));
local void putShortMSB  OF((deflate_state *s, uInt b));
local void flush_pending        OF((z_streamp strm));
local int read_buf      OF((z_streamp strm, Bytef *buf, unsigned size));
#ifdef ASMV
void match_init OF((void));     /* asm code initialization */
uInt longest_match      OF((deflate_state *s, IPos cur_match));
#else
local uInt longest_match        OF((deflate_state *s, IPos cur_match));
#endif

#ifdef DEBUG_ZLIB
local void check_match OF((deflate_state *s, IPos start, IPos match,
    int length));
#endif

/*
 * ===========================================================================
 * Local data
 */

#define NIL 0
/* Tail of hash chains */

#ifndef TOO_FAR
#define TOO_FAR 4096
#endif
/* Matches of length 3 are discarded if their distance exceeds TOO_FAR */

#define MIN_LOOKAHEAD (MAX_MATCH+MIN_MATCH+1)
/*
 * Minimum amount of lookahead, except at the end of the input file.
 * See deflate.c for comments about the MIN_MATCH+1.
 */

/*
 * Values for max_lazy_match, good_match and max_chain_length,
 * depending on the desired pack level (0..9). The values given below
 * have been tuned to exclude worst case performance for pathological
 * files. Better values may be found for specific files.
 */
typedef struct config_s {
        ush good_length;        /* reduce lazy search above this match length */
        ush max_lazy;   /* do not perform lazy search above this match length */
        ush nice_length;        /* quit search above this match length */
        ush max_chain;
        compress_func func;
} config;

local const config configuration_table[10] = {
/*      good lazy nice chain */
/* 0 */ {0,    0,  0,    0, deflate_stored},  /* store only */
/* 1 */ {4,    4,  8,    4, deflate_fast}, /* maximum speed, no lazy matches */
/* 2 */ {4,    5, 16,    8, deflate_fast},
/* 3 */ {4,    6, 32,   32, deflate_fast},

/* 4 */ {4,    4, 16,   16, deflate_slow},  /* lazy matches */
/* 5 */ {8,   16, 32,   32, deflate_slow},
/* 6 */ {8,   16, 128, 128, deflate_slow},
/* 7 */ {8,   32, 128, 256, deflate_slow},
/* 8 */ {32, 128, 258, 1024, deflate_slow},
/* 9 */ {32, 258, 258, 4096, deflate_slow}};    /* maximum compression */

/*
 * Note: the deflate() code requires max_lazy >= MIN_MATCH and max_chain >= 4
 * For deflate_fast() (levels <= 3) good is ignored and lazy has a different
 * meaning.
 */

#define EQUAL 0
/* result of memcmp for equal strings */

#ifndef NO_DUMMY_DECL
struct static_tree_desc_s {int dummy; };        /* for buggy compilers */
#endif

/*
 * ===========================================================================
 * Update a hash value with the given input byte
 * IN  assertion: all calls to to UPDATE_HASH are made with consecutive
 *    input characters, so that a running hash key can be computed from the
 *    previous key instead of complete recalculation each time.
 */
#define UPDATE_HASH(s, h, c) (h = (((h)<<s->hash_shift) ^ (c)) & s->hash_mask)


/*
 * ===========================================================================
 * Insert string str in the dictionary and set match_head to the previous head
 * of the hash chain (the most recent string with same hash key). Return
 * the previous length of the hash chain.
 * If this file is compiled with -DFASTEST, the compression level is forced
 * to 1, and no hash chains are maintained.
 * IN  assertion: all calls to to INSERT_STRING are made with consecutive
 *    input characters and the first MIN_MATCH bytes of str are valid
 *    (except for the last MIN_MATCH-1 bytes of the input file).
 */
#ifdef FASTEST
#define INSERT_STRING(s, str, match_head) \
        (UPDATE_HASH(s, s->ins_h, s->window[(str) + (MIN_MATCH-1)]), \
        match_head = s->head[s->ins_h], \
        s->head[s->ins_h] = (Pos)(str))
#else
#define INSERT_STRING(s, str, match_head) \
        (UPDATE_HASH(s, s->ins_h, s->window[(str) + (MIN_MATCH-1)]), \
        s->prev[(str) & s->w_mask] = match_head = s->head[s->ins_h], \
        s->head[s->ins_h] = (Pos)(str))
#endif

/*
 * ===========================================================================
 * Initialize the hash table (avoiding 64K overflow for 16 bit systems).
 * prev[] will be initialized on the fly.
 */
#define CLEAR_HASH(s) \
    s->head[s->hash_size-1] = NIL; \
    zmemzero((Bytef *)s->head, (unsigned)(s->hash_size-1)*sizeof (*s->head));

/* ========================================================================= */
int
deflateInit_(strm, level, version, stream_size)
    z_streamp strm;
    int level;
    const char *version;
    int stream_size;
{
        (void) deflate_copyright;
        return deflateInit2_(strm, level, Z_DEFLATED, MAX_WBITS, DEF_MEM_LEVEL,
            Z_DEFAULT_STRATEGY, version, stream_size);
        /* To do: ignore strm->next_in if we use it as window */
}

/* ========================================================================= */
int deflateInit2_(strm, level, method, windowBits, memLevel, strategy,
    version, stream_size)
    z_streamp strm;
    int  level;
    int  method;
    int  windowBits;
    int  memLevel;
    int  strategy;
    const char *version;
    int stream_size;
{
        deflate_state *s;
        int noheader = 0;
        static const char *my_version = ZLIB_VERSION;

        ushf *overlay;
        /*
         * We overlay pending_buf and d_buf+l_buf. This works since
         * the average output size for (length, distance) codes is <=
         * 24 bits.
         */

        if (version == Z_NULL || version[0] != my_version[0] ||
            stream_size != sizeof (z_stream)) {
                return (Z_VERSION_ERROR);
        }
        if (strm == Z_NULL)
                return (Z_STREAM_ERROR);

        strm->msg = Z_NULL;
#ifndef NO_ZCFUNCS
        if (strm->zalloc == Z_NULL) {
                strm->zalloc = zcalloc;
                strm->opaque = (voidpf)0;
        }
        if (strm->zfree == Z_NULL) strm->zfree = zcfree;
#endif

        if (level == Z_DEFAULT_COMPRESSION) level = 6;
#ifdef FASTEST
        level = 1;
#endif

        if (windowBits < 0) { /* undocumented feature: suppress zlib header */
                noheader = 1;
                windowBits = -windowBits;
        }
        if (memLevel < 1 || memLevel > MAX_MEM_LEVEL || method != Z_DEFLATED ||
            windowBits <= 8 || windowBits > 15 || level < 0 || level > 9 ||
            strategy < 0 || strategy > Z_HUFFMAN_ONLY) {
                return (Z_STREAM_ERROR);
        }
        s = (deflate_state *) ZALLOC(strm, 1, sizeof (deflate_state));
        if (s == Z_NULL)
                return (Z_MEM_ERROR);
        strm->state = (struct internal_state FAR *)s;
        s->strm = strm;

        s->noheader = noheader;
        s->w_bits = windowBits;
        s->w_size = 1 << s->w_bits;
        s->w_mask = s->w_size - 1;

        s->hash_bits = memLevel + 7;
        s->hash_size = 1 << s->hash_bits;
        s->hash_mask = s->hash_size - 1;
        s->hash_shift =  ((s->hash_bits+MIN_MATCH-1)/MIN_MATCH);

        s->window = (Bytef *) ZALLOC(strm, s->w_size, 2*sizeof (Byte));
        s->prev   = (Posf *)  ZALLOC(strm, s->w_size, sizeof (Pos));
        s->head   = (Posf *)  ZALLOC(strm, s->hash_size, sizeof (Pos));

        s->lit_bufsize = 1 << (memLevel + 6);   /* 16K elements by default */

        overlay = (ushf *) ZALLOC(strm, s->lit_bufsize, sizeof (ush)+2);
        s->pending_buf = (uchf *) overlay;
        s->pending_buf_size = (ulg)s->lit_bufsize * (sizeof (ush)+2L);

        if (s->window == Z_NULL || s->prev == Z_NULL || s->head == Z_NULL ||
            s->pending_buf == Z_NULL) {
                strm->msg = ERR_MSG(Z_MEM_ERROR);
                s->status = INIT_STATE;
                (void) deflateEnd(strm);
                return (Z_MEM_ERROR);
        }
        s->d_buf = overlay + s->lit_bufsize/sizeof (ush);
        s->l_buf = s->pending_buf + (1+sizeof (ush))*s->lit_bufsize;

        s->level = level;
        s->strategy = strategy;
        s->method = (Byte)method;

        return (deflateReset(strm));
}

/* ========================================================================= */
int
deflateSetDictionary(strm, dictionary, dictLength)
    z_streamp strm;
    const Bytef *dictionary;
    uInt  dictLength;
{
        deflate_state *s;
        uInt length = dictLength;
        uInt n;
        IPos hash_head = 0;

        if (strm == Z_NULL || strm->state == Z_NULL || dictionary == Z_NULL)
                return (Z_STREAM_ERROR);

        s = (deflate_state *) strm->state;
        if (s->status != INIT_STATE)
                return (Z_STREAM_ERROR);

        strm->adler = adler32(strm->adler, dictionary, dictLength);

        if (length < MIN_MATCH)
                return (Z_OK);
        if (length > MAX_DIST(s)) {
                length = MAX_DIST(s);
#ifndef USE_DICT_HEAD
                /* use the tail of the dictionary */
                dictionary += dictLength - length;
#endif
        }
        Assert(length <= s->window_size, "dict copy");
        zmemcpy(s->window, dictionary, length);
        s->strstart = length;
        s->block_start = (long)length;

        /*
         * Insert all strings in the hash table (except for the last
         * two bytes).  s->lookahead stays null, so s->ins_h will be
         * recomputed at the next call of fill_window.
         */
        s->ins_h = s->window[0];
        UPDATE_HASH(s, s->ins_h, s->window[1]);
        for (n = 0; n <= length - MIN_MATCH; n++) {
                INSERT_STRING(s, n, hash_head);
        }
        if (hash_head) hash_head = 0;   /* to make compiler happy */
        return (Z_OK);
}

/* ========================================================================= */
int
deflateReset(strm)
    z_streamp strm;
{
        deflate_state *s;

        if (strm == Z_NULL || strm->state == Z_NULL ||
            strm->zalloc == Z_NULL || strm->zfree == Z_NULL)
                return (Z_STREAM_ERROR);

        strm->total_in = strm->total_out = 0;
        /* use zfree if we ever allocate msg dynamically */
        strm->msg = Z_NULL;
        strm->data_type = Z_UNKNOWN;

        s = (deflate_state *)strm->state;
        s->pending = 0;
        s->pending_out = s->pending_buf;

        if (s->noheader < 0) {
                /* was set to -1 by deflate(..., Z_FINISH); */
                s->noheader = 0;
        }
        s->status = s->noheader ? BUSY_STATE : INIT_STATE;
        strm->adler = 1;
        s->last_flush = Z_NO_FLUSH;

        _tr_init(s);
        lm_init(s);

        return (Z_OK);
}

/* ========================================================================= */
int
deflateParams(strm, level, strategy)
    z_streamp strm;
    int level;
    int strategy;
{
        deflate_state *s;
        compress_func func;
        int err = Z_OK;

        if (strm == Z_NULL || strm->state == Z_NULL)
                return (Z_STREAM_ERROR);
        s = (deflate_state *) strm->state;

        if (level == Z_DEFAULT_COMPRESSION) {
                level = 6;
        }
        if (level < 0 || level > 9 || strategy < 0 ||
            strategy > Z_HUFFMAN_ONLY) {
                return (Z_STREAM_ERROR);
        }
        func = configuration_table[s->level].func;

        if (func != configuration_table[level].func && strm->total_in != 0) {
                /* Flush the last buffer: */
                err = deflate(strm, Z_PARTIAL_FLUSH);
        }
        if (s->level != level) {
                s->level = level;
                s->max_lazy_match   = configuration_table[level].max_lazy;
                s->good_match   = configuration_table[level].good_length;
                s->nice_match   = configuration_table[level].nice_length;
                s->max_chain_length = configuration_table[level].max_chain;
        }
        s->strategy = strategy;
        return (err);
}

/*
 * =========================================================================
 * Put a short in the pending buffer. The 16-bit value is put in MSB order.
 * IN assertion: the stream state is correct and there is enough room in
 * pending_buf.
 */
local void
putShortMSB(s, b)
    deflate_state *s;
    uInt b;
{
        put_byte(s, (Byte)(b >> 8));
        put_byte(s, (Byte)(b & 0xff));
}

/*
 * =========================================================================
 * Flush as much pending output as possible. All deflate() output goes
 * through this function so some applications may wish to modify it
 * to avoid allocating a large strm->next_out buffer and copying into it.
 * (See also read_buf()).
 */
local void
flush_pending(strm)
    z_streamp strm;
{
        deflate_state *s = (deflate_state *) strm->state;
        unsigned len = s->pending;

        if (len > strm->avail_out) len = strm->avail_out;
        if (len == 0)
                return;

        if (strm->next_out != Z_NULL) {         /* PPP */
                zmemcpy(strm->next_out, s->pending_out, len);
                strm->next_out += len;
        }                                       /* PPP */
        s->pending_out += len;
        strm->total_out += len;
        strm->avail_out  -= len;
        s->pending -= len;
        if (s->pending == 0) {
                s->pending_out = s->pending_buf;
        }
}

/* ========================================================================= */
int
deflate(strm, flush)
    z_streamp strm;
    int flush;
{
        int old_flush;  /* value of flush param for previous deflate call */
        deflate_state *s;

        if (strm == Z_NULL || strm->state == Z_NULL ||
            flush > Z_FINISH || flush < 0) {
                return (Z_STREAM_ERROR);
        }
        s = (deflate_state *) strm->state;

        if (/* strm->next_out == Z_NULL || --- we allow null --- PPP */
                (strm->next_in == Z_NULL && strm->avail_in != 0) ||
            (s->status == FINISH_STATE && flush != Z_FINISH)) {
                ERR_RETURN(strm, Z_STREAM_ERROR);
        }
        if (strm->avail_out == 0) ERR_RETURN(strm, Z_BUF_ERROR);

        s->strm = strm; /* just in case */
        old_flush = s->last_flush;
        s->last_flush = flush;

        /* Write the zlib header */
        if (s->status == INIT_STATE) {

                uInt header = (Z_DEFLATED + ((s->w_bits-8)<<4)) << 8;
                uInt level_flags = (s->level-1) >> 1;

                if (level_flags > 3) level_flags = 3;
                header |= (level_flags << 6);
                if (s->strstart != 0) header |= PRESET_DICT;
                header += 31 - (header % 31);

                s->status = BUSY_STATE;
                putShortMSB(s, header);

                /* Save the adler32 of the preset dictionary: */
                if (s->strstart != 0) {
                        putShortMSB(s, (uInt)(strm->adler >> 16));
                        putShortMSB(s, (uInt)(strm->adler & 0xffff));
                }
                strm->adler = 1L;
        }

        /* Flush as much pending output as possible */
        if (s->pending != 0) {
                flush_pending(strm);
                if (strm->avail_out == 0) {
                        /*
                         * Since avail_out is 0, deflate will be
                         * called again with more output space, but
                         * possibly with both pending and avail_in
                         * equal to zero. There won't be anything to
                         * do, but this is not an error situation so
                         * make sure we return OK instead of BUF_ERROR
                         * at next call of deflate:
                         */
                        s->last_flush = -1;
                        return (Z_OK);
                }

                /*
                 * Make sure there is something to do and avoid
                 * duplicate consecutive flushes. For repeated and
                 * useless calls with Z_FINISH, we keep returning
                 * Z_STREAM_END instead of Z_BUFF_ERROR.
                 */
        } else if (strm->avail_in == 0 && flush <= old_flush &&
            flush != Z_FINISH) {
                ERR_RETURN(strm, Z_BUF_ERROR);
        }

        /* User must not provide more input after the first FINISH: */
        if (s->status == FINISH_STATE && strm->avail_in != 0) {
                ERR_RETURN(strm, Z_BUF_ERROR);
        }

        /* Start a new block or continue the current one. */
        if (strm->avail_in != 0 || s->lookahead != 0 ||
            (flush != Z_NO_FLUSH && s->status != FINISH_STATE)) {
                block_state bstate;

                bstate = (*(configuration_table[s->level].func))(s, flush);

                if (bstate == finish_started || bstate == finish_done) {
                        s->status = FINISH_STATE;
                }
                if (bstate == need_more || bstate == finish_started) {
                        if (strm->avail_out == 0) {
                                /* avoid BUF_ERROR next call, see above */
                                s->last_flush = -1;
                        }
                        return (Z_OK);
                        /*
                         * If flush != Z_NO_FLUSH && avail_out == 0,
                         * the next call of deflate should use the
                         * same flush parameter to make sure that the
                         * flush is complete. So we don't have to
                         * output an empty block here, this will be
                         * done at next call. This also ensures that
                         * for a very small output buffer, we emit at
                         * most one empty block.
                         */
                }
                if (bstate == block_done) {
                        if (flush == Z_PARTIAL_FLUSH) {
                                _tr_align(s);
                        } else if (flush == Z_PACKET_FLUSH) {   /* PPP */
                                /*
                                 * Output just the 3-bit `stored'
                                 * block type value, but not a zero
                                 * length.  Added for PPP.
                                 */
                                _tr_stored_type_only(s);        /* PPP */
                        } else { /* FULL_FLUSH or SYNC_FLUSH */
                                _tr_stored_block(s, (char *)0, 0L, 0);
                                /*
                                 * For a full flush, this empty block
                                 * will be recognized as a special
                                 * marker by inflate_sync().
                                 */
                                if (flush == Z_FULL_FLUSH) {
                                        CLEAR_HASH(s);  /* forget history */
                                }
                        }
                        flush_pending(strm);
                        if (strm->avail_out == 0) {
                                /* avoid BUF_ERROR at next call, see above */
                                s->last_flush = -1;
                                return (Z_OK);
                        }
                }
        }
        Assert(strm->avail_out > 0, "bug2");

        if (flush != Z_FINISH)
                return (Z_OK);
        if (s->noheader)
                return (Z_STREAM_END);

        /* Write the zlib trailer (adler32) */
        putShortMSB(s, (uInt)(strm->adler >> 16));
        putShortMSB(s, (uInt)(strm->adler & 0xffff));
        flush_pending(strm);
        /*
         * If avail_out is zero, the application will call deflate
         * again to flush the rest.
         */
        s->noheader = -1;       /* write the trailer only once! */
        return (s->pending != 0 ? Z_OK : Z_STREAM_END);
}

/* ========================================================================= */
int
deflateEnd(strm)
    z_streamp strm;
{
        int status;
        deflate_state *s;

        if (strm == Z_NULL || strm->state == Z_NULL)
                return (Z_STREAM_ERROR);
        s = (deflate_state *) strm->state;

        status = s->status;
        if (status != INIT_STATE && status != BUSY_STATE &&
            status != FINISH_STATE) {
                return (Z_STREAM_ERROR);
        }

        /* Deallocate in reverse order of allocations: */
        TRY_FREE(strm, s->pending_buf);
        TRY_FREE(strm, s->head);
        TRY_FREE(strm, s->prev);
        TRY_FREE(strm, s->window);

        ZFREE(strm, s);
        strm->state = Z_NULL;

        return (status == BUSY_STATE ? Z_DATA_ERROR : Z_OK);
}

/*
 * =========================================================================
 * Copy the source state to the destination state.
 * To simplify the source, this is not supported for 16-bit MSDOS (which
 * doesn't have enough memory anyway to duplicate compression states).
 */
int
deflateCopy(dest, source)
    z_streamp dest;
    z_streamp source;
{
#ifdef MAXSEG_64K
        return (Z_STREAM_ERROR);
#else
        deflate_state *ds;
        deflate_state *ss;
        ushf *overlay;

        if (source == Z_NULL || dest == Z_NULL || source->state == Z_NULL)
                return (Z_STREAM_ERROR);
        ss = (deflate_state *) source->state;

        zmemcpy(dest, source, sizeof (*dest));

        ds = (deflate_state *) ZALLOC(dest, 1, sizeof (deflate_state));
        if (ds == Z_NULL)
                return (Z_MEM_ERROR);
        dest->state = (struct internal_state FAR *) ds;
        zmemcpy(ds, ss, sizeof (*ds));
        ds->strm = dest;

        ds->window = (Bytef *) ZALLOC(dest, ds->w_size, 2*sizeof (Byte));
        ds->prev   = (Posf *)  ZALLOC(dest, ds->w_size, sizeof (Pos));
        ds->head   = (Posf *)  ZALLOC(dest, ds->hash_size, sizeof (Pos));
        overlay = (ushf *) ZALLOC(dest, ds->lit_bufsize, sizeof (ush)+2);
        ds->pending_buf = (uchf *) overlay;

        if (ds->window == Z_NULL || ds->prev == Z_NULL || ds->head == Z_NULL ||
            ds->pending_buf == Z_NULL) {
                ds->status = INIT_STATE;
                (void) deflateEnd(dest);
                return (Z_MEM_ERROR);
        }
        /* following zmemcpy doesn't work for 16-bit MSDOS */
        zmemcpy(ds->window, ss->window, ds->w_size * 2 * sizeof (Byte));
        zmemcpy(ds->prev, ss->prev, ds->w_size * sizeof (Pos));
        zmemcpy(ds->head, ss->head, ds->hash_size * sizeof (Pos));
        zmemcpy(ds->pending_buf, ss->pending_buf, (uInt)ds->pending_buf_size);

        ds->pending_out = ds->pending_buf + (ss->pending_out - ss->pending_buf);
        ds->d_buf = overlay + ds->lit_bufsize/sizeof (ush);
        ds->l_buf = ds->pending_buf + (1+sizeof (ush))*ds->lit_bufsize;

        ds->l_desc.dyn_tree = ds->dyn_ltree;
        ds->d_desc.dyn_tree = ds->dyn_dtree;
        ds->bl_desc.dyn_tree = ds->bl_tree;

        return (Z_OK);
#endif
}

/*
 * ===========================================================================
 * Return the number of bytes of output which are immediately available
 * for output from the decompressor.            ---PPP---
 */
int
deflateOutputPending(strm)
    z_streamp strm;
{
        if (strm == Z_NULL || strm->state == Z_NULL)
                return (0);

        return (((deflate_state *)(strm->state))->pending);
}

/*
 * ===========================================================================
 * Read a new buffer from the current input stream, update the adler32
 * and total number of bytes read.  All deflate() input goes through
 * this function so some applications may wish to modify it to avoid
 * allocating a large strm->next_in buffer and copying from it.
 * (See also flush_pending()).
 */
local int
read_buf(strm, buf, size)
    z_streamp strm;
    Bytef *buf;
    unsigned size;
{
        unsigned len = strm->avail_in;

        if (len > size) len = size;
        if (len == 0)
                return (0);

        strm->avail_in  -= len;

        if (!((deflate_state *)(strm->state))->noheader) {
                strm->adler = adler32(strm->adler, strm->next_in, len);
        }
        zmemcpy(buf, strm->next_in, len);
        strm->next_in  += len;
        strm->total_in += len;

        return ((int)len);
}

/*
 * ===========================================================================
 * Initialize the "longest match" routines for a new zlib stream
 */
local void
lm_init(s)
    deflate_state *s;
{
        s->window_size = (ulg)2L*s->w_size;

        CLEAR_HASH(s);

        /* Set the default configuration parameters: */
        s->max_lazy_match   = configuration_table[s->level].max_lazy;
        s->good_match   = configuration_table[s->level].good_length;
        s->nice_match   = configuration_table[s->level].nice_length;
        s->max_chain_length = configuration_table[s->level].max_chain;

        s->strstart = 0;
        s->block_start = 0L;
        s->lookahead = 0;
        s->match_length = s->prev_length = MIN_MATCH-1;
        s->match_available = 0;
        s->ins_h = 0;
#ifdef ASMV
        match_init();   /* initialize the asm code */
#endif
}

/*
 * ===========================================================================
 * Set match_start to the longest match starting at the given string and
 * return its length. Matches shorter or equal to prev_length are discarded,
 * in which case the result is equal to prev_length and match_start is
 * garbage.
 * IN assertions: cur_match is the head of the hash chain for the current
 *   string (strstart) and its distance is <= MAX_DIST, and prev_length >= 1
 * OUT assertion: the match length is not greater than s->lookahead.
 */
#ifndef ASMV
/*
 * For 80x86 and 680x0, an optimized version will be provided in
 * match.asm or match.S. The code will be functionally equivalent.
 */
#ifndef FASTEST
local uInt
longest_match(s, cur_match)
    deflate_state *s;
    IPos cur_match;     /* current match */
{
        /* max hash chain length */
        unsigned chain_length = s->max_chain_length;
        register Bytef *scan = s->window + s->strstart; /* current string */
        register Bytef *match;  /* matched string */
        register int len;       /* length of current match */
        int best_len = s->prev_length;  /* best match length so far */
        int nice_match = s->nice_match; /* stop if match long enough */
        IPos limit = s->strstart > (IPos)MAX_DIST(s) ?
            s->strstart - (IPos)MAX_DIST(s) : NIL;
        /*
         * Stop when cur_match becomes <= limit. To simplify the code,
         * we prevent matches with the string of window index 0.
         */
        Posf *prev = s->prev;
        uInt wmask = s->w_mask;

#ifdef UNALIGNED_OK
        /*
         * Compare two bytes at a time. Note: this is not always
         * beneficial.  Try with and without -DUNALIGNED_OK to check.
         */
        register Bytef *strend = s->window + s->strstart + MAX_MATCH - 1;
        register ush scan_start = *(ushf*)scan;
        register ush scan_end   = *(ushf*)(scan+best_len-1);
#else
        register Bytef *strend = s->window + s->strstart + MAX_MATCH;
        register Byte scan_end1  = scan[best_len-1];
        register Byte scan_end   = scan[best_len];
#endif

        /*
         * The code is optimized for HASH_BITS >= 8 and MAX_MATCH-2
         * multiple of 16.  It is easy to get rid of this optimization
         * if necessary.
         */
        Assert(s->hash_bits >= 8 && MAX_MATCH == 258, "Code too clever");

        /* Do not waste too much time if we already have a good match: */
        if (s->prev_length >= s->good_match) {
                chain_length >>= 2;
        }
        /*
         * Do not look for matches beyond the end of the input. This
         * is necessary to make deflate deterministic.
         */
        if ((uInt)nice_match > s->lookahead) nice_match = s->lookahead;

        Assert((ulg)s->strstart <= s->window_size-MIN_LOOKAHEAD,
            "need lookahead");

        do {
                Assert(cur_match <= s->strstart, "no future");
                match = s->window + cur_match;

                /*
                 * Skip to next match if the match length cannot
                 * increase or if the match length is less than 2:
                 */
#if (defined(UNALIGNED_OK) && MAX_MATCH == 258)
                /*
                 * This code assumes sizeof (unsigned short) == 2. Do
                 * not use UNALIGNED_OK if your compiler uses a
                 * different size.
                 */
                if (*(ushf*)(match+best_len-1) != scan_end ||
                    *(ushf*)match != scan_start) continue;

                /*
                 * It is not necessary to compare scan[2] and match[2]
                 * since they are always equal when the other bytes
                 * match, given that the hash keys are equal and that
                 * HASH_BITS >= 8. Compare 2 bytes at a time at
                 * strstart+3, +5, ... up to strstart+257. We check
                 * for insufficient lookahead only every 4th
                 * comparison; the 128th check will be made at
                 * strstart+257. If MAX_MATCH-2 is not a multiple of
                 * 8, it is necessary to put more guard bytes at the
                 * end of the window, or to check more often for
                 * insufficient lookahead.
                 */
                Assert(scan[2] == match[2], "scan[2]?");
                scan++, match++;
                do {
                } while (*(ushf *)(scan += 2) == *(ushf *)(match += 2) &&
                    *(ushf *)(scan += 2) == *(ushf *)(match += 2) &&
                    *(ushf *)(scan += 2) == *(ushf *)(match += 2) &&
                    *(ushf *)(scan += 2) == *(ushf *)(match += 2) &&
                    scan < strend);
                /* The funny "do {}" generates better code on most compilers */

                /* Here, scan <= window+strstart+257 */
                Assert(scan <= s->window+(unsigned)(s->window_size-1),
                    "wild scan");
                if (*scan == *match) scan++;

                len = (MAX_MATCH - 1) - (int)(strend-scan);
                scan = strend - (MAX_MATCH-1);

#else /* UNALIGNED_OK */

                if (match[best_len]     != scan_end     ||
                    match[best_len-1]   != scan_end1    ||
                    *match              != *scan        ||
                    *++match            != scan[1])
                        continue;

                /*
                 * The check at best_len-1 can be removed because it
                 * will be made again later. (This heuristic is not
                 * always a win.)  It is not necessary to compare
                 * scan[2] and match[2] since they are always equal
                 * when the other bytes match, given that the hash
                 * keys are equal and that HASH_BITS >= 8.
                 */
                scan += 2, match++;
                Assert(*scan == *match, "match[2]?");

                /*
                 * We check for insufficient lookahead only every 8th
                 * comparison; the 256th check will be made at
                 * strstart+258.
                 */
                do {
                } while (*++scan == *++match && *++scan == *++match &&
                    *++scan == *++match && *++scan == *++match &&
                    *++scan == *++match && *++scan == *++match &&
                    *++scan == *++match && *++scan == *++match &&
                    scan < strend);

                Assert(scan <= s->window+(unsigned)(s->window_size-1),
                    "wild scan");

                len = MAX_MATCH - (int)(strend - scan);
                scan = strend - MAX_MATCH;

#endif /* UNALIGNED_OK */

                if (len > best_len) {
                        s->match_start = cur_match;
                        best_len = len;
                        if (len >= nice_match) break;
#ifdef UNALIGNED_OK
                        scan_end = *(ushf*)(scan+best_len-1);
#else
                        scan_end1  = scan[best_len-1];
                        scan_end   = scan[best_len];
#endif
                }
        } while ((cur_match = prev[cur_match & wmask]) > limit &&
            --chain_length != 0);

        if ((uInt)best_len <= s->lookahead)
                return (best_len);
        return (s->lookahead);
}
#else /* FASTEST */
/*
 * ---------------------------------------------------------------------------
 * Optimized version for level == 1 only
 */
local uInt
longest_match(s, cur_match)
deflate_state *s;
IPos cur_match;         /* current match */
{
        register Bytef *scan = s->window + s->strstart; /* current string */
        register Bytef *match;          /* matched string */
        register int len;                       /* length of current match */
        register Bytef *strend = s->window + s->strstart + MAX_MATCH;

        /*
         * The code is optimized for HASH_BITS >= 8 and MAX_MATCH-2
         * multiple of 16.  It is easy to get rid of this optimization
         * if necessary.
         */
        Assert(s->hash_bits >= 8 && MAX_MATCH == 258, "Code too clever");

        Assert((ulg)s->strstart <= s->window_size-MIN_LOOKAHEAD,
            "need lookahead");

        Assert(cur_match <= s->strstart, "no future");

        match = s->window + cur_match;

        /* Return failure if the match length is less than 2: */
        if (match[0] != scan[0] || match[1] != scan[1])
                return (MIN_MATCH-1);

        /*
         * The check at best_len-1 can be removed because it will be
         * made again later. (This heuristic is not always a win.)  It
         * is not necessary to compare scan[2] and match[2] since they
         * are always equal when the other bytes match, given that the
         * hash keys are equal and that HASH_BITS >= 8.
         */
        scan += 2, match += 2;
        Assert(*scan == *match, "match[2]?");

        /*
         * We check for insufficient lookahead only every 8th comparison;
         * the 256th check will be made at strstart+258.
         */
        do {
        } while (*++scan == *++match && *++scan == *++match &&
            *++scan == *++match && *++scan == *++match &&
            *++scan == *++match && *++scan == *++match &&
            *++scan == *++match && *++scan == *++match &&
            scan < strend);

        Assert(scan <= s->window+(unsigned)(s->window_size-1), "wild scan");

        len = MAX_MATCH - (int)(strend - scan);

        if (len < MIN_MATCH)
                return (MIN_MATCH - 1);

        s->match_start = cur_match;
        return (len <= s->lookahead ? len : s->lookahead);
}
#endif /* FASTEST */
#endif /* ASMV */

#ifdef DEBUG_ZLIB
/*
 * ===========================================================================
 * Check that the match at match_start is indeed a match.
 */
local void
check_match(s, start, match, length)
    deflate_state *s;
    IPos start, match;
    int length;
{
        /* check that the match is indeed a match */
        if (zmemcmp(s->window + match, s->window + start, length) != EQUAL) {
                fprintf(stderr, " start %u, match %u, length %d\n",
                    start, match, length);
                do {
                        fprintf(stderr, "%c%c", s->window[match++],
                            s->window[start++]);
                } while (--length != 0);
                z_error("invalid match");
        }
        if (z_verbose > 1) {
                fprintf(stderr, "\\[%d,%d]", start-match, length);
                do { putc(s->window[start++], stderr); } while (--length != 0);
        }
}
#else
#define check_match(s, start, match, length)
#endif

/*
 * ===========================================================================
 * Fill the window when the lookahead becomes insufficient.
 * Updates strstart and lookahead.
 *
 * IN assertion: lookahead < MIN_LOOKAHEAD
 * OUT assertions: strstart <= window_size-MIN_LOOKAHEAD
 *    At least one byte has been read, or avail_in == 0; reads are
 *    performed for at least two bytes (required for the zip translate_eol
 *    option -- not supported here).
 */
local void
fill_window(s)
    deflate_state *s;
{
        register unsigned n, m;
        register Posf *p;
        unsigned more;  /* Amount of free space at the end of the window. */
        uInt wsize = s->w_size;

        do {
                more = (unsigned)(s->window_size -(ulg)s->lookahead -
                    (ulg)s->strstart);

                /* Deal with !@#$% 64K limit: */
                if (more == 0 && s->strstart == 0 && s->lookahead == 0) {
                        more = wsize;

                } else if (more == (unsigned)(-1)) {
                        /*
                         * Very unlikely, but possible on 16 bit
                         * machine if strstart == 0 and lookahead == 1
                         * (input done one byte at time)
                         */
                        more--;

                        /*
                         * If the window is almost full and there is
                         * insufficient lookahead, move the upper half
                         * to the lower one to make room in the upper
                         * half.
                         */
                } else if (s->strstart >= wsize+MAX_DIST(s)) {

                        Assert(wsize+wsize <= s->window_size, "wsize*2");
                        zmemcpy(s->window, s->window+wsize, (unsigned)wsize);
                        s->match_start -= wsize;
                        /* we now have strstart >= MAX_DIST */
                        s->strstart    -= wsize;
                        s->block_start -= (long)wsize;

                        /*
                         * Slide the hash table (could be avoided with
                         * 32 bit values at the expense of memory
                         * usage). We slide even when level == 0 to
                         * keep the hash table consistent if we switch
                         * back to level > 0 later. (Using level 0
                         * permanently is not an optimal usage of
                         * zlib, so we don't care about this
                         * pathological case.)
                         */
                        n = s->hash_size;
                        p = &s->head[n];
                        do {
                                m = *--p;
                                *p = (Pos)(m >= wsize ? m-wsize : NIL);
                        } while (--n);

                        n = wsize;
#ifndef FASTEST
                        p = &s->prev[n];
                        do {
                                m = *--p;
                                *p = (Pos)(m >= wsize ? m-wsize : NIL);
                                /*
                                 * If n is not on any hash chain,
                                 * prev[n] is garbage but its value
                                 * will never be used.
                                 */
                        } while (--n);
#endif
                        more += wsize;
                }
                if (s->strm->avail_in == 0)
                        return;

                /*
                 * If there was no sliding:
                 *    strstart <= WSIZE+MAX_DIST-1 &&
                 *      lookahead <= MIN_LOOKAHEAD - 1 &&
                 *    more == window_size - lookahead - strstart
                 * => more >= window_size - (MIN_LOOKAHEAD-1 + WSIZE +
                 *      MAX_DIST-1)
                 * => more >= window_size - 2*WSIZE + 2
                 * In the BIG_MEM or MMAP case (not yet supported),
                 *   window_size == input_size + MIN_LOOKAHEAD  &&
                 *   strstart + s->lookahead <= input_size =>
                 *      more >= MIN_LOOKAHEAD.
                 * Otherwise, window_size == 2*WSIZE so more >= 2.
                 * If there was sliding, more >= WSIZE. So in all cases,
                 * more >= 2.
                 */
                Assert(more >= 2, "more < 2");
                Assert(s->strstart + s->lookahead + more <= s->window_size,
                    "read too much");

                n = read_buf(s->strm, s->window + s->strstart + s->lookahead,
                    more);
                s->lookahead += n;

                /* Initialize the hash value now that we have some input: */
                if (s->lookahead >= MIN_MATCH) {
                        s->ins_h = s->window[s->strstart];
                        UPDATE_HASH(s, s->ins_h, s->window[s->strstart+1]);
#if MIN_MATCH != 3
                        Call UPDATE_HASH() MIN_MATCH-3 more times
#endif
                            }
                /*
                 * If the whole input has less than MIN_MATCH bytes,
                 * ins_h is garbage, but this is not important since
                 * only literal bytes will be emitted.
                 */

        } while (s->lookahead < MIN_LOOKAHEAD && s->strm->avail_in != 0);
}

/*
 * ===========================================================================
 * Flush the current block, with given end-of-file flag.
 * IN assertion: strstart is set to the end of the current match.
 */
#define FLUSH_BLOCK_ONLY(s, eof) { \
        _tr_flush_block(s, (s->block_start >= 0L ? \
                (charf *)&s->window[(unsigned)s->block_start] : \
                (charf *)Z_NULL), \
                (ulg)((long)s->strstart - s->block_start), \
                (eof)); \
        s->block_start = s->strstart; \
        flush_pending(s->strm); \
        Tracev((stderr, "[FLUSH]")); \
}

/* Same but force premature exit if necessary. */
#define FLUSH_BLOCK(s, eof) { \
        FLUSH_BLOCK_ONLY(s, eof); \
        if (s->strm->avail_out == 0) \
                return ((eof) ? finish_started : need_more); \
}

/*
 * ===========================================================================
 * Copy without compression as much as possible from the input stream, return
 * the current block state.
 * This function does not insert new strings in the dictionary since
 * uncompressible data is probably not useful. This function is used
 * only for the level=0 compression option.
 * NOTE: this function should be optimized to avoid extra copying from
 * window to pending_buf.
 */
local block_state
deflate_stored(s, flush)
    deflate_state *s;
    int flush;
{
        /*
         * Stored blocks are limited to 0xffff bytes, pending_buf is
         * limited to pending_buf_size, and each stored block has a 5
         * byte header:
         */
        ulg max_block_size = 0xffff;
        ulg max_start;

        if (max_block_size > s->pending_buf_size - 5) {
                max_block_size = s->pending_buf_size - 5;
        }

        /* Copy as much as possible from input to output: */
        for (;;) {
                /* Fill the window as much as possible: */
                if (s->lookahead <= 1) {

                        Assert(s->strstart < s->w_size+MAX_DIST(s) ||
                            s->block_start >= (long)s->w_size,
                            "slide too late");

                        fill_window(s);
                        if (s->lookahead == 0 && flush == Z_NO_FLUSH)
                                return (need_more);

                        if (s->lookahead == 0)
                                break;  /* flush the current block */
                }
                Assert(s->block_start >= 0L, "block gone");

                s->strstart += s->lookahead;
                s->lookahead = 0;

                /* Emit a stored block if pending_buf will be full: */
                max_start = s->block_start + max_block_size;
                if (s->strstart == 0 || (ulg)s->strstart >= max_start) {
                        /*
                         * strstart == 0 is possible when wraparound
                         * on 16-bit machine
                         */
                        s->lookahead = (uInt)(s->strstart - max_start);
                        s->strstart = (uInt)max_start;
                        FLUSH_BLOCK(s, 0);
                }
                /*
                 * Flush if we may have to slide, otherwise
                 * block_start may become negative and the data will
                 * be gone:
                 */
                if (s->strstart - (uInt)s->block_start >= MAX_DIST(s)) {
                        FLUSH_BLOCK(s, 0);
                }
        }
        FLUSH_BLOCK(s, flush == Z_FINISH);
        return (flush == Z_FINISH ? finish_done : block_done);
}

/*
 * ===========================================================================
 * Compress as much as possible from the input stream, return the current
 * block state.
 * This function does not perform lazy evaluation of matches and inserts
 * new strings in the dictionary only for unmatched strings or for short
 * matches. It is used only for the fast compression options.
 */
local block_state
deflate_fast(s, flush)
    deflate_state *s;
    int flush;
{
        IPos hash_head = NIL;   /* head of the hash chain */
        int bflush;     /* set if current block must be flushed */

        for (;;) {
                /*
                 * Make sure that we always have enough lookahead,
                 * except at the end of the input file. We need
                 * MAX_MATCH bytes for the next match, plus MIN_MATCH
                 * bytes to insert the string following the next
                 * match.
                 */
                if (s->lookahead < MIN_LOOKAHEAD) {
                        fill_window(s);
                        if (s->lookahead < MIN_LOOKAHEAD &&
                            flush == Z_NO_FLUSH) {
                                return (need_more);
                        }
                        if (s->lookahead == 0)
                                break;  /* flush the current block */
                }

                /*
                 * Insert the string window[strstart .. strstart+2] in
                 * the dictionary, and set hash_head to the head of
                 * the hash chain:
                 */
                if (s->lookahead >= MIN_MATCH) {
                        INSERT_STRING(s, s->strstart, hash_head);
                }

                /*
                 * Find the longest match, discarding those <=
                 * prev_length.  At this point we have always
                 * match_length < MIN_MATCH
                 */
                if (hash_head != NIL && s->strstart - hash_head <=
                    MAX_DIST(s)) {
                        /*
                         * To simplify the code, we prevent matches
                         * with the string of window index 0 (in
                         * particular we have to avoid a match of the
                         * string with itself at the start of the
                         * input file).
                         */
                        if (s->strategy != Z_HUFFMAN_ONLY) {
                                s->match_length = longest_match(s, hash_head);
                        }
                        /* longest_match() sets match_start */
                }
                if (s->match_length >= MIN_MATCH) {
                        check_match(s, s->strstart, s->match_start,
                            s->match_length);

                        _tr_tally_dist(s, s->strstart - s->match_start,
                            s->match_length - MIN_MATCH, bflush);

                        s->lookahead -= s->match_length;

                        /*
                         * Insert new strings in the hash table only
                         * if the match length is not too large. This
                         * saves time but degrades compression.
                         */
#ifndef FASTEST
                        if (s->match_length <= s->max_insert_length &&
                            s->lookahead >= MIN_MATCH) {
                                /* string at strstart already in hash table */
                                s->match_length--;
                                do {
                                        s->strstart++;
                                        INSERT_STRING(s, s->strstart,
                                            hash_head);
                                        /*
                                         * strstart never exceeds
                                         * WSIZE-MAX_MATCH, so there
                                         * are always MIN_MATCH bytes
                                         * ahead.
                                         */
                                } while (--s->match_length != 0);
                                s->strstart++;
                        } else
#endif
                        {
                                s->strstart += s->match_length;
                                s->match_length = 0;
                                s->ins_h = s->window[s->strstart];
                                UPDATE_HASH(s, s->ins_h,
                                    s->window[s->strstart+1]);
#if MIN_MATCH != 3
                                Call UPDATE_HASH() MIN_MATCH-3 more times
#endif
                                /*
                                 * If lookahead < MIN_MATCH, ins_h is
                                 * garbage, but it does not matter
                                 * since it will be recomputed at next
                                 * deflate call.
                                 */
                        }
                } else {
                        /* No match, output a literal byte */
                        Tracevv((stderr, "%c", s->window[s->strstart]));
                        _tr_tally_lit(s, s->window[s->strstart], bflush);
                        s->lookahead--;
                        s->strstart++;
                }
                if (bflush) FLUSH_BLOCK(s, 0);
        }
        FLUSH_BLOCK(s, flush == Z_FINISH);
        return (flush == Z_FINISH ? finish_done : block_done);
}

/*
 * ===========================================================================
 * Same as above, but achieves better compression. We use a lazy
 * evaluation for matches: a match is finally adopted only if there is
 * no better match at the next window position.
 */
local block_state
deflate_slow(s, flush)
    deflate_state *s;
    int flush;
{
        IPos hash_head = NIL;   /* head of hash chain */
        int bflush;     /* set if current block must be flushed */

        /* Process the input block. */
        for (;;) {
                /*
                 * Make sure that we always have enough lookahead,
                 * except at the end of the input file. We need
                 * MAX_MATCH bytes for the next match, plus MIN_MATCH
                 * bytes to insert the string following the next
                 * match.
                 */
                if (s->lookahead < MIN_LOOKAHEAD) {
                        fill_window(s);
                        if (s->lookahead < MIN_LOOKAHEAD &&
                            flush == Z_NO_FLUSH) {
                                return (need_more);
                        }
                        /* flush the current block */
                        if (s->lookahead == 0)
                                break;
                }

                /*
                 * Insert the string window[strstart .. strstart+2] in
                 * the dictionary, and set hash_head to the head of
                 * the hash chain:
                 */
                if (s->lookahead >= MIN_MATCH) {
                        INSERT_STRING(s, s->strstart, hash_head);
                }

                /*
                 * Find the longest match, discarding those <=
                 * prev_length.
                 */
                s->prev_length = s->match_length;
                s->prev_match = s->match_start;
                s->match_length = MIN_MATCH-1;

                if (hash_head != NIL && s->prev_length < s->max_lazy_match &&
                    s->strstart - hash_head <= MAX_DIST(s)) {
                        /*
                         * To simplify the code, we prevent matches
                         * with the string of window index 0 (in
                         * particular we have to avoid a match of the
                         * string with itself at the start of the
                         * input file).
                         */
                        if (s->strategy != Z_HUFFMAN_ONLY) {
                                s->match_length = longest_match(s, hash_head);
                        }
                        /* longest_match() sets match_start */

                        if (s->match_length <= 5 &&
                            (s->strategy == Z_FILTERED ||
                                (s->match_length == MIN_MATCH &&
                                    s->strstart - s->match_start > TOO_FAR))) {

                                /*
                                 * If prev_match is also MIN_MATCH,
                                 * match_start is garbage but we will
                                 * ignore the current match anyway.
                                 */
                                s->match_length = MIN_MATCH-1;
                        }
                }
                /*
                 * If there was a match at the previous step and the
                 * current match is not better, output the previous
                 * match:
                 */
                if (s->prev_length >= MIN_MATCH &&
                    s->match_length <= s->prev_length) {
                        uInt max_insert = s->strstart + s->lookahead -
                            MIN_MATCH;
                        /* Do not insert strings in hash table beyond this. */

                        check_match(s, s->strstart-1, s->prev_match,
                            s->prev_length);

                        _tr_tally_dist(s, s->strstart -1 - s->prev_match,
                            s->prev_length - MIN_MATCH, bflush);

                        /*
                         * Insert in hash table all strings up to the
                         * end of the match.  strstart-1 and strstart
                         * are already inserted. If there is not
                         * enough lookahead, the last two strings are
                         * not inserted in the hash table.
                         */
                        s->lookahead -= s->prev_length-1;
                        s->prev_length -= 2;
                        do {
                                if (++s->strstart <= max_insert) {
                                        INSERT_STRING(s, s->strstart,
                                            hash_head);
                                }
                        } while (--s->prev_length != 0);
                        s->match_available = 0;
                        s->match_length = MIN_MATCH-1;
                        s->strstart++;

                        if (bflush) FLUSH_BLOCK(s, 0);

                } else if (s->match_available) {
                        /*
                         * If there was no match at the previous
                         * position, output a single literal. If there
                         * was a match but the current match is
                         * longer, truncate the previous match to a
                         * single literal.
                         */
                        Tracevv((stderr, "%c", s->window[s->strstart-1]));
                        _tr_tally_lit(s, s->window[s->strstart-1], bflush);
                        if (bflush) {
                                FLUSH_BLOCK_ONLY(s, 0);
                        }
                        s->strstart++;
                        s->lookahead--;
                        if (s->strm->avail_out == 0)
                                return (need_more);
                } else {
                        /*
                         * There is no previous match to compare with,
                         * wait for the next step to decide.
                         */
                        s->match_available = 1;
                        s->strstart++;
                        s->lookahead--;
                }
        }
        Assert(flush != Z_NO_FLUSH, "no flush?");
        if (s->match_available) {
                Tracevv((stderr, "%c", s->window[s->strstart-1]));
                _tr_tally_lit(s, s->window[s->strstart-1], bflush);
                s->match_available = 0;
        }
        FLUSH_BLOCK(s, flush == Z_FINISH);
        return (flush == Z_FINISH ? finish_done : block_done);
}
/* --- deflate.c */

/* +++ trees.c */
/*
 * trees.c -- output deflated data using Huffman coding
 * Copyright (C) 1995-1998 Jean-loup Gailly
 * For conditions of distribution and use, see copyright notice in zlib.h
 */

/*
 *  ALGORITHM
 *
 *      The "deflation" process uses several Huffman trees. The more
 *      common source values are represented by shorter bit sequences.
 *
 *      Each code tree is stored in a compressed form which is itself
 * a Huffman encoding of the lengths of all the code strings (in
 * ascending order by source values).  The actual code strings are
 * reconstructed from the lengths in the inflate process, as described
 * in the deflate specification.
 *
 *  REFERENCES
 *
 *      Deutsch, L.P.,"'Deflate' Compressed Data Format Specification".
 *      Available in ftp.uu.net:/pub/archiving/zip/doc/deflate-1.1.doc
 *
 *      Storer, James A.
 *          Data Compression:  Methods and Theory, pp. 49-50.
 *          Computer Science Press, 1988.  ISBN 0-7167-8156-5.
 *
 *      Sedgewick, R.
 *          Algorithms, p290.
 *          Addison-Wesley, 1983. ISBN 0-201-06672-6.
 */

/* From: trees.c,v 1.11 1996/07/24 13:41:06 me Exp $ */

/* #include "deflate.h" */

#ifdef DEBUG_ZLIB
#include <ctype.h>
#endif

/*
 * ===========================================================================
 * Constants
 */

#define MAX_BL_BITS 7
/* Bit length codes must not exceed MAX_BL_BITS bits */

#define END_BLOCK 256
/* end of block literal code */

#define REP_3_6         16
/* repeat previous bit length 3-6 times (2 bits of repeat count) */

#define REPZ_3_10       17
/* repeat a zero length 3-10 times  (3 bits of repeat count) */

#define REPZ_11_138     18
/* repeat a zero length 11-138 times  (7 bits of repeat count) */

/* extra bits for each length code */
local const int extra_lbits[LENGTH_CODES] = {
        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};

/* extra bits for each distance code */
local const int extra_dbits[D_CODES] = {
        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};

/* extra bits for each bit length code */
local const int extra_blbits[BL_CODES] = {
        0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 2, 3, 7};

local const uch bl_order[BL_CODES] = {
        16, 17, 18, 0, 8, 7, 9, 6, 10, 5, 11, 4, 12, 3, 13, 2, 14, 1, 15};

/*
 * The lengths of the bit length codes are sent in order of decreasing
 * probability, to avoid transmitting the lengths for unused bit
 * length codes.
 */

#define Buf_size (8 * 2*sizeof (char))
/*
 * Number of bits used within bi_buf. (bi_buf might be implemented on
 * more than 16 bits on some systems.)
 */

/*
 * ===========================================================================
 * Local data. These are initialized only once.
 */
#define DIST_CODE_LEN  512 /* see definition of array dist_code below */

local ct_data static_ltree[L_CODES+2];
/*
 * The static literal tree. Since the bit lengths are imposed, there
 * is no need for the L_CODES extra codes used during heap
 * construction. However The codes 286 and 287 are needed to build a
 * canonical tree (see _tr_init below).
 */

local ct_data static_dtree[D_CODES];
/*
 * The static distance tree. (Actually a trivial tree since all codes
 * use 5 bits.)
 */

local uch _dist_code[512];
/*
 * distance codes. The first 256 values correspond to the distances 3
 * .. 258, the last 256 values correspond to the top 8 bits of the 15
 * bit distances.
 */

local uch _length_code[MAX_MATCH-MIN_MATCH+1];
/* length code for each normalized match length (0 == MIN_MATCH) */

local int base_length[LENGTH_CODES];
/* First normalized length for each code (0 = MIN_MATCH) */

local int base_dist[D_CODES];
/* First normalized distance for each code (0 = distance of 1) */

struct static_tree_desc_s {
        const ct_data *static_tree;     /* static tree or NULL */
        const intf    *extra_bits;      /* extra bits for each code or NULL */
        int     extra_base;     /* base index for extra_bits */
        int     elems;  /* max number of elements in the tree */
        int     max_length;     /* max bit length for the codes */
};

local static_tree_desc  static_l_desc = {
        static_ltree, extra_lbits, LITERALS+1,  L_CODES, MAX_BITS};

local static_tree_desc  static_d_desc = {
        static_dtree, extra_dbits, 0,           D_CODES, MAX_BITS};

local static_tree_desc  static_bl_desc = {
        (const ct_data *)0, extra_blbits, 0,            BL_CODES, MAX_BL_BITS};

/*
 * ===========================================================================
 * Local (static) routines in this file.
 */

local void tr_static_init OF((void));
local void init_block   OF((deflate_state *s));
local void pqdownheap   OF((deflate_state *s, ct_data *tree, int k));
local void gen_bitlen   OF((deflate_state *s, tree_desc *desc));
local void gen_codes    OF((ct_data *tree, int max_code, ushf *bl_count));
local void build_tree   OF((deflate_state *s, tree_desc *desc));
local void scan_tree    OF((deflate_state *s, ct_data *tree, int max_code));
local void send_tree    OF((deflate_state *s, ct_data *tree, int max_code));
local int  build_bl_tree        OF((deflate_state *s));
local void send_all_trees       OF((deflate_state *s, int lcodes, int dcodes,
    int blcodes));
local void compress_block OF((deflate_state *s, ct_data *ltree,
    ct_data *dtree));
local void set_data_type        OF((deflate_state *s));
local unsigned bi_reverse       OF((unsigned value, int length));
local void bi_windup    OF((deflate_state *s));
local void bi_flush     OF((deflate_state *s));
local void copy_block   OF((deflate_state *s, charf *buf, unsigned len,
    int header));

#ifndef DEBUG_ZLIB
#define send_code(s, c, tree) send_bits(s, tree[c].Code, tree[c].Len)
/* Send a code of the given tree. c and tree must not have side effects */

#else /* DEBUG_ZLIB */
#define send_code(s, c, tree) \
        { if (z_verbose > 2) fprintf(stderr, "\ncd %3d ", (c)); \
        send_bits(s, tree[c].Code, tree[c].Len); }
#endif

/*
 * ===========================================================================
 * Output a short LSB first on the stream.
 * IN assertion: there is enough room in pendingBuf.
 */
#define put_short(s, w) { \
        put_byte(s, (uch)((w) & 0xff)); \
        put_byte(s, (uch)((ush)(w) >> 8)); \
}

/*
 * ===========================================================================
 * Send a value on a given number of bits.
 * IN assertion: length <= 16 and value fits in length bits.
 */
#ifdef DEBUG_ZLIB
local void send_bits    OF((deflate_state *s, int value, int length));

local void
send_bits(s, value, length)
    deflate_state *s;
    int value;  /* value to send */
    int length; /* number of bits */
{
        Tracevv((stderr, " l %2d v %4x ", length, value));
        Assert(length > 0 && length <= 15, "invalid length");
        s->bits_sent += (ulg)length;

        /*
         * If not enough room in bi_buf, use (valid) bits from bi_buf
         * and (16 - bi_valid) bits from value, leaving (width -
         * (16-bi_valid)) unused bits in value.
         */
        if (s->bi_valid > (int)Buf_size - length) {
                s->bi_buf |= (value << s->bi_valid);
                put_short(s, s->bi_buf);
                s->bi_buf = (ush)value >> (Buf_size - s->bi_valid);
                s->bi_valid += length - Buf_size;
        } else {
                s->bi_buf |= value << s->bi_valid;
                s->bi_valid += length;
        }
}
#else /* !DEBUG_ZLIB */

#define send_bits(s, value, length) \
{       int len = length; \
        if (s->bi_valid > (int)Buf_size - len) {\
                int val = value; \
                s->bi_buf |= (val << s->bi_valid); \
                put_short(s, s->bi_buf); \
                s->bi_buf = (ush)val >> (Buf_size - s->bi_valid); \
                s->bi_valid += len - Buf_size; \
        } else {\
                s->bi_buf |= (value) << s->bi_valid; \
                s->bi_valid += len; \
        }\
}
#endif /* DEBUG_ZLIB */


#define MAX(a, b) (a >= b ? a : b)
/* the arguments must not have side effects */

/*
 * ===========================================================================
 * Initialize the various 'constant' tables. In a multi-threaded environment,
 * this function may be called by two threads concurrently, but this is
 * harmless since both invocations do exactly the same thing.
 */
local void
tr_static_init()
{
        static int static_init_done = 0;
        int n;  /* iterates over tree elements */
        int bits;       /* bit counter */
        int length;     /* length value */
        int code;       /* code value */
        int dist;       /* distance index */
        ush bl_count[MAX_BITS+1];
        /* number of codes at each bit length for an optimal tree */

        if (static_init_done)
                return;

        /* For some embedded targets, global variables are not initialized: */
        static_l_desc.static_tree = static_ltree;
        static_l_desc.extra_bits = extra_lbits;
        static_d_desc.static_tree = static_dtree;
        static_d_desc.extra_bits = extra_dbits;
        static_bl_desc.extra_bits = extra_blbits;

        /* Initialize the mapping length (0..255) -> length code (0..28) */
        length = 0;
        for (code = 0; code < LENGTH_CODES-1; code++) {
                base_length[code] = length;
                for (n = 0; n < (1<<extra_lbits[code]); n++) {
                        _length_code[length++] = (uch)code;
                }
        }
        Assert(length == 256, "tr_static_init: length != 256");
        /*
         * Note that the length 255 (match length 258) can be
         * represented in two different ways: code 284 + 5 bits or
         * code 285, so we overwrite _length_code[255] to use the best
         * encoding:
         */
        _length_code[length-1] = (uch)code;

        /* Initialize the mapping dist (0..32K) -> dist code (0..29) */
        dist = 0;
        for (code = 0; code < 16; code++) {
                base_dist[code] = dist;
                for (n = 0; n < (1<<extra_dbits[code]); n++) {
                        _dist_code[dist++] = (uch)code;
                }
        }
        Assert(dist == 256, "tr_static_init: dist != 256");
        dist >>= 7;     /* from now on, all distances are divided by 128 */
        for (; code < D_CODES; code++) {
                base_dist[code] = dist << 7;
                for (n = 0; n < (1<<(extra_dbits[code]-7)); n++) {
                        _dist_code[256 + dist++] = (uch)code;
                }
        }
        Assert(dist == 256, "tr_static_init: 256+dist != 512");

        /* Construct the codes of the static literal tree */
        for (bits = 0; bits <= MAX_BITS; bits++) bl_count[bits] = 0;
        n = 0;
        while (n <= 143) static_ltree[n++].Len = 8, bl_count[8]++;
        while (n <= 255) static_ltree[n++].Len = 9, bl_count[9]++;
        while (n <= 279) static_ltree[n++].Len = 7, bl_count[7]++;
        while (n <= 287) static_ltree[n++].Len = 8, bl_count[8]++;
        /*
         * Codes 286 and 287 do not exist, but we must include them in the
         * tree construction to get a canonical Huffman tree (longest code
         * all ones)
         */
        gen_codes((ct_data *)static_ltree, L_CODES+1, bl_count);

        /* The static distance tree is trivial: */
        for (n = 0; n < D_CODES; n++) {
                static_dtree[n].Len = 5;
                static_dtree[n].Code = bi_reverse((unsigned)n, 5);
        }
        static_init_done = 1;
}

/*
 * ===========================================================================
 * Initialize the tree data structures for a new zlib stream.
 */
void
_tr_init(s)
    deflate_state *s;
{
        tr_static_init();

        s->l_desc.dyn_tree = s->dyn_ltree;
        s->l_desc.stat_desc = &static_l_desc;

        s->d_desc.dyn_tree = s->dyn_dtree;
        s->d_desc.stat_desc = &static_d_desc;

        s->bl_desc.dyn_tree = s->bl_tree;
        s->bl_desc.stat_desc = &static_bl_desc;

        s->bi_buf = 0;
        s->bi_valid = 0;
        s->last_eob_len = 8;    /* enough lookahead for inflate */
        s->compressed_len = 0L;         /* PPP */
#ifdef DEBUG_ZLIB
        s->bits_sent = 0L;
#endif

        /* Initialize the first block of the first file: */
        init_block(s);
}

/*
 * ===========================================================================
 * Initialize a new block.
 */
local void
init_block(s)
    deflate_state *s;
{
        int n;  /* iterates over tree elements */

        /* Initialize the trees. */
        for (n = 0; n < L_CODES;  n++) s->dyn_ltree[n].Freq = 0;
        for (n = 0; n < D_CODES;  n++) s->dyn_dtree[n].Freq = 0;
        for (n = 0; n < BL_CODES; n++) s->bl_tree[n].Freq = 0;

        s->dyn_ltree[END_BLOCK].Freq = 1;
        s->opt_len = s->static_len = 0L;
        s->last_lit = s->matches = 0;
}

#define SMALLEST 1
/* Index within the heap array of least frequent node in the Huffman tree */


/*
 * ===========================================================================
 * Remove the smallest element from the heap and recreate the heap with
 * one less element. Updates heap and heap_len.
 */
#define pqremove(s, tree, top) \
{\
        top = s->heap[SMALLEST]; \
        s->heap[SMALLEST] = s->heap[s->heap_len--]; \
        pqdownheap(s, tree, SMALLEST); \
}

/*
 * ===========================================================================
 * Compares to subtrees, using the tree depth as tie breaker when
 * the subtrees have equal frequency. This minimizes the worst case length.
 */
#define smaller(tree, n, m, depth) \
        (tree[n].Freq < tree[m].Freq || \
        (tree[n].Freq == tree[m].Freq && depth[n] <= depth[m]))
/*
 * ===========================================================================
 * Restore the heap property by moving down the tree starting at node k,
 * exchanging a node with the smallest of its two sons if necessary, stopping
 * when the heap property is re-established (each father smaller than its
 * two sons).
 */
local void
pqdownheap(s, tree, k)
    deflate_state *s;
    ct_data *tree;      /* the tree to restore */
    int k;      /* node to move down */
{
        int v = s->heap[k];
        int j = k << 1; /* left son of k */
        while (j <= s->heap_len) {
                /* Set j to the smallest of the two sons: */
                if (j < s->heap_len &&
                    smaller(tree, s->heap[j+1], s->heap[j], s->depth)) {
                        j++;
                }
                /* Exit if v is smaller than both sons */
                if (smaller(tree, v, s->heap[j], s->depth)) break;

                /* Exchange v with the smallest son */
                s->heap[k] = s->heap[j];  k = j;

                /* And continue down the tree, setting j to the left son of k */
                j <<= 1;
        }
        s->heap[k] = v;
}

/*
 * ===========================================================================
 * Compute the optimal bit lengths for a tree and update the total bit length
 * for the current block.
 * IN assertion: the fields freq and dad are set, heap[heap_max] and
 *    above are the tree nodes sorted by increasing frequency.
 * OUT assertions: the field len is set to the optimal bit length, the
 *     array bl_count contains the frequencies for each bit length.
 *     The length opt_len is updated; static_len is also updated if stree is
 *     not null.
 */
local void
gen_bitlen(s, desc)
    deflate_state *s;
    tree_desc *desc;    /* the tree descriptor */
{
        ct_data *tree  = desc->dyn_tree;
        int max_code   = desc->max_code;
        const ct_data *stree = desc->stat_desc->static_tree;
        const intf *extra    = desc->stat_desc->extra_bits;
        int base        = desc->stat_desc->extra_base;
        int max_length = desc->stat_desc->max_length;
        int h;  /* heap index */
        int n, m;       /* iterate over the tree elements */
        int bits;       /* bit length */
        int xbits;      /* extra bits */
        ush f;  /* frequency */
        /* number of elements with bit length too large */
        int overflow = 0;

        for (bits = 0; bits <= MAX_BITS; bits++) s->bl_count[bits] = 0;

        /*
         * In a first pass, compute the optimal bit lengths (which may
         * overflow in the case of the bit length tree).
         */
        tree[s->heap[s->heap_max]].Len = 0;     /* root of the heap */

        for (h = s->heap_max+1; h < HEAP_SIZE; h++) {
                n = s->heap[h];
                bits = tree[tree[n].Dad].Len + 1;
                if (bits > max_length) bits = max_length, overflow++;
                tree[n].Len = (ush)bits;
                /* We overwrite tree[n].Dad which is no longer needed */

                if (n > max_code) continue;     /* not a leaf node */

                s->bl_count[bits]++;
                xbits = 0;
                if (n >= base) xbits = extra[n-base];
                f = tree[n].Freq;
                s->opt_len += (ulg)f * (bits + xbits);
                if (stree) s->static_len += (ulg)f * (stree[n].Len + xbits);
        }
        if (overflow == 0)
                return;

        Trace((stderr, "\nbit length overflow\n"));
        /* This happens for example on obj2 and pic of the Calgary corpus */

        /* Find the first bit length which could increase: */
        do {
                bits = max_length-1;
                while (s->bl_count[bits] == 0) bits--;
                s->bl_count[bits]--;    /* move one leaf down the tree */
                /* move one overflow item as its brother */
                s->bl_count[bits+1] += 2;
                s->bl_count[max_length]--;
                /*
                 * The brother of the overflow item also moves one
                 * step up, but this does not affect
                 * bl_count[max_length]
                 */
                overflow -= 2;
        } while (overflow > 0);

        /*
         * Now recompute all bit lengths, scanning in increasing
         * frequency.  h is still equal to HEAP_SIZE. (It is simpler
         * to reconstruct all lengths instead of fixing only the wrong
         * ones. This idea is taken from 'ar' written by Haruhiko
         * Okumura.)
         */
        for (bits = max_length; bits != 0; bits--) {
                n = s->bl_count[bits];
                while (n != 0) {
                        m = s->heap[--h];
                        if (m > max_code) continue;
                        if (tree[m].Len != (unsigned)bits) {
                                Trace((stderr, "code %d bits %d->%d\n", m,
                                    tree[m].Len, bits));
                                s->opt_len += ((long)bits - (long)tree[m].Len)
                                    *(long)tree[m].Freq;
                                tree[m].Len = (ush)bits;
                        }
                        n--;
                }
        }
}

/*
 * ===========================================================================
 * Generate the codes for a given tree and bit counts (which need not be
 * optimal).
 * IN assertion: the array bl_count contains the bit length statistics for
 * the given tree and the field len is set for all tree elements.
 * OUT assertion: the field code is set for all tree elements of non
 *     zero code length.
 */
local void
gen_codes(tree, max_code, bl_count)
    ct_data *tree;      /* the tree to decorate */
    int max_code;       /* largest code with non zero frequency */
    ushf *bl_count;     /* number of codes at each bit length */
{
        /* next code value for each bit length */
        ush next_code[MAX_BITS+1];
        ush code = 0;   /* running code value */
        int bits;       /* bit index */
        int n;  /* code index */

        /*
         * The distribution counts are first used to generate the code
         * values without bit reversal.
         */
        for (bits = 1; bits <= MAX_BITS; bits++) {
                next_code[bits] = code = (code + bl_count[bits-1]) << 1;
        }
        /*
         * Check that the bit counts in bl_count are consistent. The
         * last code must be all ones.
         */
        Assert(code + bl_count[MAX_BITS]-1 == (1<<MAX_BITS)-1,
            "inconsistent bit counts");
        Tracev((stderr, "\ngen_codes: max_code %d ", max_code));

        for (n = 0;  n <= max_code; n++) {
                int len = tree[n].Len;
                if (len == 0) continue;
                /* Now reverse the bits */
                tree[n].Code = bi_reverse(next_code[len]++, len);

                Tracecv(tree != static_ltree,
                    (stderr, "\nn %3d %c l %2d c %4x (%x) ",
                    n, (isgraph(n) ? n : ' '), len, tree[n].Code,
                        next_code[len]-1));
        }
}

/*
 * ===========================================================================
 * Construct one Huffman tree and assigns the code bit strings and lengths.
 * Update the total bit length for the current block.
 * IN assertion: the field freq is set for all tree elements.
 * OUT assertions: the fields len and code are set to the optimal bit length
 *     and corresponding code. The length opt_len is updated; static_len is
 *     also updated if stree is not null. The field max_code is set.
 */
local void
build_tree(s, desc)
    deflate_state *s;
    tree_desc *desc;    /* the tree descriptor */
{
        ct_data *tree   = desc->dyn_tree;
        const ct_data *stree  = desc->stat_desc->static_tree;
        int elems       = desc->stat_desc->elems;
        int n, m;       /* iterate over heap elements */
        int max_code = -1;      /* largest code with non zero frequency */
        int node;       /* new node being created */

        /*
         * Construct the initial heap, with least frequent element in
         * heap[SMALLEST]. The sons of heap[n] are heap[2*n] and
         * heap[2*n+1].  heap[0] is not used.
         */
        s->heap_len = 0, s->heap_max = HEAP_SIZE;

        for (n = 0; n < elems; n++) {
                if (tree[n].Freq != 0) {
                        s->heap[++(s->heap_len)] = max_code = n;
                        s->depth[n] = 0;
                } else {
                        tree[n].Len = 0;
                }
        }

        /*
         * The pkzip format requires that at least one distance code
         * exists, and that at least one bit should be sent even if
         * there is only one possible code. So to avoid special checks
         * later on we force at least two codes of non zero frequency.
         */
        while (s->heap_len < 2) {
                node = s->heap[++(s->heap_len)] = (max_code < 2 ?
                    ++max_code : 0);
                tree[node].Freq = 1;
                s->depth[node] = 0;
                s->opt_len--; if (stree) s->static_len -= stree[node].Len;
                /* node is 0 or 1 so it does not have extra bits */
        }
        desc->max_code = max_code;

        /*
         * The elements heap[heap_len/2+1 .. heap_len] are leaves of
         * the tree, establish sub-heaps of increasing lengths:
         */
        for (n = s->heap_len/2; n >= 1; n--) pqdownheap(s, tree, n);

        /*
         * Construct the Huffman tree by repeatedly combining the
         * least two frequent nodes.
         */
        node = elems;   /* next internal node of the tree */
        do {
                pqremove(s, tree, n);   /* n = node of least frequency */
                m = s->heap[SMALLEST];  /* m = node of next least frequency */

                /* keep the nodes sorted by frequency */
                s->heap[--(s->heap_max)] = n;
                s->heap[--(s->heap_max)] = m;

                /* Create a new node father of n and m */
                tree[node].Freq = tree[n].Freq + tree[m].Freq;
                s->depth[node] = (uch) (MAX(s->depth[n], s->depth[m]) + 1);
                tree[n].Dad = tree[m].Dad = (ush)node;
#ifdef DUMP_BL_TREE
                if (tree == s->bl_tree) {
                        fprintf(stderr, "\nnode %d(%d), sons %d(%d) %d(%d)",
                            node, tree[node].Freq, n, tree[n].Freq, m,
                            tree[m].Freq);
                }
#endif
                /* and insert the new node in the heap */
                s->heap[SMALLEST] = node++;
                pqdownheap(s, tree, SMALLEST);

        } while (s->heap_len >= 2);

        s->heap[--(s->heap_max)] = s->heap[SMALLEST];

        /*
         * At this point, the fields freq and dad are set. We can now
         * generate the bit lengths.
         */
        gen_bitlen(s, (tree_desc *)desc);

        /* The field len is now set, we can generate the bit codes */
        gen_codes((ct_data *)tree, max_code, s->bl_count);
}

/*
 * ===========================================================================
 * Scan a literal or distance tree to determine the frequencies of the codes
 * in the bit length tree.
 */
local void
scan_tree(s, tree, max_code)
    deflate_state *s;
    ct_data *tree;      /* the tree to be scanned */
    int max_code;       /* and its largest code of non zero frequency */
{
        int n;  /* iterates over all tree elements */
        int prevlen = -1;       /* last emitted length */
        int curlen;     /* length of current code */
        int nextlen = tree[0].Len;      /* length of next code */
        int count = 0;  /* repeat count of the current code */
        int max_count = 7;      /* max repeat count */
        int min_count = 4;      /* min repeat count */

        if (nextlen == 0) max_count = 138, min_count = 3;
        tree[max_code+1].Len = (ush)0xffff;     /* guard */

        for (n = 0; n <= max_code; n++) {
                curlen = nextlen; nextlen = tree[n+1].Len;
                if (++count < max_count && curlen == nextlen) {
                        continue;
                } else if (count < min_count) {
                        s->bl_tree[curlen].Freq += count;
                } else if (curlen != 0) {
                        if (curlen != prevlen) s->bl_tree[curlen].Freq++;
                        s->bl_tree[REP_3_6].Freq++;
                } else if (count <= 10) {
                        s->bl_tree[REPZ_3_10].Freq++;
                } else {
                        s->bl_tree[REPZ_11_138].Freq++;
                }
                count = 0; prevlen = curlen;
                if (nextlen == 0) {
                        max_count = 138, min_count = 3;
                } else if (curlen == nextlen) {
                        max_count = 6, min_count = 3;
                } else {
                        max_count = 7, min_count = 4;
                }
        }
}

/*
 * ===========================================================================
 * Send a literal or distance tree in compressed form, using the codes in
 * bl_tree.
 */
local void
send_tree(s, tree, max_code)
    deflate_state *s;
    ct_data *tree;      /* the tree to be scanned */
    int max_code;       /* and its largest code of non zero frequency */
{
        int n;  /* iterates over all tree elements */
        int prevlen = -1;       /* last emitted length */
        int curlen;     /* length of current code */
        int nextlen = tree[0].Len;      /* length of next code */
        int count = 0;  /* repeat count of the current code */
        int max_count = 7;      /* max repeat count */
        int min_count = 4;      /* min repeat count */

        /* tree[max_code+1].Len = -1; */  /* guard already set */
        if (nextlen == 0) max_count = 138, min_count = 3;

        for (n = 0; n <= max_code; n++) {
                curlen = nextlen; nextlen = tree[n+1].Len;
                if (++count < max_count && curlen == nextlen) {
                        continue;
                } else if (count < min_count) {
                        do { send_code(s, curlen, s->bl_tree); }
                        while (--count != 0);

                } else if (curlen != 0) {
                        if (curlen != prevlen) {
                                send_code(s, curlen, s->bl_tree); count--;
                        }
                        Assert(count >= 3 && count <= 6, " 3_6?");
                        send_code(s, REP_3_6, s->bl_tree);
                        send_bits(s, count-3, 2);

                } else if (count <= 10) {
                        send_code(s, REPZ_3_10, s->bl_tree);
                        send_bits(s, count-3, 3);

                } else {
                        send_code(s, REPZ_11_138, s->bl_tree);
                        send_bits(s, count-11, 7);
                }
                count = 0; prevlen = curlen;
                if (nextlen == 0) {
                        max_count = 138, min_count = 3;
                } else if (curlen == nextlen) {
                        max_count = 6, min_count = 3;
                } else {
                        max_count = 7, min_count = 4;
                }
        }
}

/*
 * ===========================================================================
 * Construct the Huffman tree for the bit lengths and return the index in
 * bl_order of the last bit length code to send.
 */
local int
build_bl_tree(s)
    deflate_state *s;
{
        /* index of last bit length code of non zero freq */
        int max_blindex;

        /*
         * Determine the bit length frequencies for literal and
         * distance trees
         */
        scan_tree(s, (ct_data *)s->dyn_ltree, s->l_desc.max_code);
        scan_tree(s, (ct_data *)s->dyn_dtree, s->d_desc.max_code);

        /* Build the bit length tree: */
        build_tree(s, (tree_desc *)(&(s->bl_desc)));
        /*
         * opt_len now includes the length of the tree
         * representations, except the lengths of the bit lengths
         * codes and the 5+5+4 bits for the counts.
         */

        /*
         * Determine the number of bit length codes to send. The pkzip
         * format requires that at least 4 bit length codes be
         * sent. (appnote.txt says 3 but the actual value used is 4.)
         */
        for (max_blindex = BL_CODES-1; max_blindex >= 3; max_blindex--) {
                if (s->bl_tree[bl_order[max_blindex]].Len != 0) break;
        }
        /* Update opt_len to include the bit length tree and counts */
        s->opt_len += 3*(max_blindex+1) + 5+5+4;
        Tracev((stderr, "\ndyn trees: dyn %ld, stat %ld",
            s->opt_len, s->static_len));

        return (max_blindex);
}

/*
 * ===========================================================================
 * Send the header for a block using dynamic Huffman trees: the counts, the
 * lengths of the bit length codes, the literal tree and the distance tree.
 * IN assertion: lcodes >= 257, dcodes >= 1, blcodes >= 4.
 */
local void
send_all_trees(s, lcodes, dcodes, blcodes)
    deflate_state *s;
    int lcodes, dcodes, blcodes;        /* number of codes for each tree */
{
        int rank;       /* index in bl_order */

        Assert(lcodes >= 257 && dcodes >= 1 && blcodes >= 4,
            "not enough codes");
        Assert(lcodes <= L_CODES && dcodes <= D_CODES && blcodes <= BL_CODES,
            "too many codes");
        Tracev((stderr, "\nbl counts: "));
        send_bits(s, lcodes-257, 5);    /* not +255 as stated in appnote.txt */
        send_bits(s, dcodes-1,   5);
        send_bits(s, blcodes-4,  4);    /* not -3 as stated in appnote.txt */
        for (rank = 0; rank < blcodes; rank++) {
                Tracev((stderr, "\nbl code %2d ", bl_order[rank]));
                send_bits(s, s->bl_tree[bl_order[rank]].Len, 3);
        }
#ifdef DEBUG_ZLIB
        Tracev((stderr, "\nbl tree: sent %ld", s->bits_sent));
#endif

        /* literal tree */
        send_tree(s, (ct_data *)s->dyn_ltree, lcodes-1);
#ifdef DEBUG_ZLIB
        Tracev((stderr, "\nlit tree: sent %ld", s->bits_sent));
#endif

        /* distance tree */
        send_tree(s, (ct_data *)s->dyn_dtree, dcodes-1);
#ifdef DEBUG_ZLIB
        Tracev((stderr, "\ndist tree: sent %ld", s->bits_sent));
#endif
}

/*
 * ===========================================================================
 * Send a stored block
 */
void
_tr_stored_block(s, buf, stored_len, eof)
    deflate_state *s;
    charf *buf; /* input block */
    ulg stored_len;     /* length of input block */
    int eof;    /* true if this is the last block for a file */
{
        send_bits(s, (STORED_BLOCK<<1)+eof, 3); /* send block type */
        s->compressed_len = (s->compressed_len + 3 + 7) & (ulg)~7L; /* PPP */
        s->compressed_len += (stored_len + 4) << 3;     /* PPP */

        copy_block(s, buf, (unsigned)stored_len, 1);    /* with header */
}

/*
 * Send just the `stored block' type code without any length bytes or data.
 * ---PPP---
 */
void
_tr_stored_type_only(s)
    deflate_state *s;
{
        send_bits(s, (STORED_BLOCK << 1), 3);
        bi_windup(s);
        s->compressed_len = (s->compressed_len + 3) & ~7L;      /* PPP */
}


/*
 * ===========================================================================
 * Send one empty static block to give enough lookahead for inflate.
 * This takes 10 bits, of which 7 may remain in the bit buffer.
 * The current inflate code requires 9 bits of lookahead. If the
 * last two codes for the previous block (real code plus EOB) were coded
 * on 5 bits or less, inflate may have only 5+3 bits of lookahead to decode
 * the last real code. In this case we send two empty static blocks instead
 * of one. (There are no problems if the previous block is stored or fixed.)
 * To simplify the code, we assume the worst case of last real code encoded
 * on one bit only.
 */
void
_tr_align(s)
    deflate_state *s;
{
        send_bits(s, STATIC_TREES<<1, 3);
        send_code(s, END_BLOCK, static_ltree);
        s->compressed_len += 10L;       /* 3 for block type, 7 for EOB */
        bi_flush(s);
        /*
         * Of the 10 bits for the empty block, we have already sent
         * (10 - bi_valid) bits. The lookahead for the last real code
         * (before the EOB of the previous block) was thus at least
         * one plus the length of the EOB plus what we have just sent
         * of the empty static block.
         */
        if (1 + s->last_eob_len + 10 - s->bi_valid < 9) {
                send_bits(s, STATIC_TREES<<1, 3);
                send_code(s, END_BLOCK, static_ltree);
                s->compressed_len += 10L;
                bi_flush(s);
        }
        s->last_eob_len = 7;
}

/*
 * ===========================================================================
 * Determine the best encoding for the current block: dynamic trees, static
 * trees or store, and output the encoded block to the zip file.
 */
void
_tr_flush_block(s, buf, stored_len, eof)
    deflate_state *s;
    charf *buf; /* input block, or NULL if too old */
    ulg stored_len;     /* length of input block */
    int eof;    /* true if this is the last block for a file */
{
        ulg opt_lenb, static_lenb;      /* opt_len and static_len in bytes */
        /* index of last bit length code of non zero freq */
        int max_blindex = 0;

        /* Build the Huffman trees unless a stored block is forced */
        if (s->level > 0) {

                /* Check if the file is ascii or binary */
                if (s->data_type == Z_UNKNOWN) set_data_type(s);

                /* Construct the literal and distance trees */
                build_tree(s, (tree_desc *)(&(s->l_desc)));
                Tracev((stderr, "\nlit data: dyn %ld, stat %ld", s->opt_len,
                    s->static_len));

                build_tree(s, (tree_desc *)(&(s->d_desc)));
                Tracev((stderr, "\ndist data: dyn %ld, stat %ld", s->opt_len,
                    s->static_len));
                /*
                 * At this point, opt_len and static_len are the total
                 * bit lengths of the compressed block data, excluding
                 * the tree representations.
                 */

                /*
                 * Build the bit length tree for the above two trees,
                 * and get the index in bl_order of the last bit
                 * length code to send.
                 */
                max_blindex = build_bl_tree(s);

                /*
                 * Determine the best encoding. Compute first the
                 * block length in bytes
                 */
                opt_lenb = (s->opt_len+3+7)>>3;
                static_lenb = (s->static_len+3+7)>>3;

                Tracev((stderr,
                    "\nopt %lu(%lu) stat %lu(%lu) stored %lu lit %u ",
                    opt_lenb, s->opt_len, static_lenb, s->static_len,
                    stored_len, s->last_lit));

                if (static_lenb <= opt_lenb) opt_lenb = static_lenb;

        } else {
                Assert(buf != (char *)0, "lost buf");
                /* force a stored block */
                opt_lenb = static_lenb = stored_len + 5;
        }

        /*
         * If compression failed and this is the first and last block,
         * and if the .zip file can be seeked (to rewrite the local
         * header), the whole file is transformed into a stored file:
         */
#ifdef STORED_FILE_OK
#ifdef FORCE_STORED_FILE
#define FRC_STR_COND    eof && s->compressed_len == 0L /* force stored file */
#else
#define FRC_STR_COND    stored_len <= opt_lenb && eof && \
                        s->compressed_len == 0L && seekable()
#endif
        if (FRC_STR_COND) {
#undef FRC_STR_COND
                /*
                 * Since LIT_BUFSIZE <= 2*WSIZE, the input data must
                 * be there:
                 */
                if (buf == (charf*)0) error("block vanished");

                /* without header */
                copy_block(s, buf, (unsigned)stored_len, 0);
                s->compressed_len = stored_len << 3;
                s->method = STORED;
        } else
#endif /* STORED_FILE_OK */

#ifdef FORCE_STORED
#define FRC_STR_COND    buf != (char *)0        /* force stored block */
#else
                        /* 4: two words for the lengths */
#define FRC_STR_COND    stored_len+4 <= opt_lenb && buf != (char *)0
#endif
                if (FRC_STR_COND) {
#undef FRC_STR_COND
                        /*
                         * The test buf != NULL is only necessary if
                         * LIT_BUFSIZE > WSIZE.  Otherwise we can't
                         * have processed more than WSIZE input bytes
                         * since the last block flush, because
                         * compression would have been successful. If
                         * LIT_BUFSIZE <= WSIZE, it is never too late
                         * to transform a block into a stored block.
                         */
                        _tr_stored_block(s, buf, stored_len, eof);
#ifdef FORCE_STATIC
#define FRC_STAT_COND   static_lenb >= 0 /* force static trees */
#else
#define FRC_STAT_COND   static_lenb == opt_lenb
#endif
                } else if (FRC_STAT_COND) {
#undef FRC_STAT_COND
                        send_bits(s, (STATIC_TREES<<1)+eof, 3);
                        compress_block(s, (ct_data *)static_ltree,
                            (ct_data *)static_dtree);
                        s->compressed_len += 3 + s->static_len; /* PPP */
                } else {
                        send_bits(s, (DYN_TREES<<1)+eof, 3);
                        send_all_trees(s, s->l_desc.max_code+1,
                            s->d_desc.max_code+1,
                            max_blindex+1);
                        compress_block(s, (ct_data *)s->dyn_ltree,
                            (ct_data *)s->dyn_dtree);
                        s->compressed_len += 3 + s->opt_len;    /* PPP */
                }
#ifdef DEBUG_ZLIB
        Assert(s->compressed_len == s->bits_sent, "bad compressed size");
#endif
        /*
         * The above check is made mod 2^32, for files larger than 512
         * MB and uLong implemented on 32 bits.
         */
        init_block(s);

        if (eof) {
                bi_windup(s);
                s->compressed_len += 7; /* align on byte boundary PPP */
        }
        Tracev((stderr, "\ncomprlen %lu(%lu) ", s->compressed_len>>3,
            s->compressed_len-7*eof));

        /* return (s->compressed_len >> 3); */
}

/*
 * ===========================================================================
 * Save the match info and tally the frequency counts. Return true if
 * the current block must be flushed.
 */
int
_tr_tally(s, dist, lc)
    deflate_state *s;
    unsigned dist;      /* distance of matched string */
        /* match length-MIN_MATCH or unmatched char (if dist==0) */
    unsigned lc;
{
        s->d_buf[s->last_lit] = (ush)dist;
        s->l_buf[s->last_lit++] = (uch)lc;
        if (dist == 0) {
                /* lc is the unmatched char */
                s->dyn_ltree[lc].Freq++;
        } else {
                s->matches++;
                /* Here, lc is the match length - MIN_MATCH */
                dist--; /* dist = match distance - 1 */
                Assert((ush)dist < (ush)MAX_DIST(s) &&
                    (ush)lc <= (ush)(MAX_MATCH-MIN_MATCH) &&
                    (ush)d_code(dist) < (ush)D_CODES,  "_tr_tally: bad match");

                s->dyn_ltree[_length_code[lc]+LITERALS+1].Freq++;
                s->dyn_dtree[d_code(dist)].Freq++;
        }

#ifdef TRUNCATE_BLOCK
        /* Try to guess if it is profitable to stop the current block here */
        if ((s->last_lit & 0x1fff) == 0 && s->level > 2) {
                /* Compute an upper bound for the compressed length */
                ulg out_length = (ulg)s->last_lit*8L;
                ulg in_length = (ulg)((long)s->strstart - s->block_start);
                int dcode;
                for (dcode = 0; dcode < D_CODES; dcode++) {
                        out_length += (ulg)s->dyn_dtree[dcode].Freq *
                            (5L+extra_dbits[dcode]);
                }
                out_length >>= 3;
                Tracev((stderr, "\nlast_lit %u, in %ld, out ~%ld(%ld%%) ",
                    s->last_lit, in_length, out_length,
                    100L - out_length*100L/in_length));
                if (s->matches < s->last_lit/2 && out_length < in_length/2)
                        return (1);
        }
#endif
        return (s->last_lit == s->lit_bufsize-1);
        /*
         * We avoid equality with lit_bufsize because of wraparound at 64K
         * on 16 bit machines and because stored blocks are restricted to
         * 64K-1 bytes.
         */
}

/*
 * ===========================================================================
 * Send the block data compressed using the given Huffman trees
 */
local void
compress_block(s, ltree, dtree)
    deflate_state *s;
    ct_data *ltree;     /* literal tree */
    ct_data *dtree;     /* distance tree */
{
        unsigned dist;  /* distance of matched string */
        int lc; /* match length or unmatched char (if dist == 0) */
        unsigned lx = 0;        /* running index in l_buf */
        unsigned code;  /* the code to send */
        int extra;      /* number of extra bits to send */

        if (s->last_lit != 0) do {
                dist = s->d_buf[lx];
                lc = s->l_buf[lx++];
                if (dist == 0) {
                        /* send a literal byte */
                        send_code(s, lc, ltree);
                        Tracecv(isgraph(lc), (stderr, " '%c' ", lc));
                } else {
                        /* Here, lc is the match length - MIN_MATCH */
                        code = _length_code[lc];
                        /* send the length code */
                        send_code(s, code+LITERALS+1, ltree);
                        extra = extra_lbits[code];
                        if (extra != 0) {
                                lc -= base_length[code];
                                /* send the extra length bits */
                                send_bits(s, lc, extra);
                        }
                        /* dist is now the match distance - 1 */
                        dist--;
                        code = d_code(dist);
                        Assert(code < D_CODES, "bad d_code");

                        /* send the distance code */
                        send_code(s, code, dtree);
                        extra = extra_dbits[code];
                        if (extra != 0) {
                                dist -= base_dist[code];
                                /* send the extra distance bits */
                                send_bits(s, dist, extra);
                        }
                } /* literal or match pair ? */

                /*
                 * Check that the overlay between pending_buf and
                 * d_buf+l_buf is ok:
                 */
                Assert(s->pending < s->lit_bufsize + 2*lx,
                    "pendingBuf overflow");

        } while (lx < s->last_lit);

        send_code(s, END_BLOCK, ltree);
        s->last_eob_len = ltree[END_BLOCK].Len;
}

/*
 * ===========================================================================
 * Set the data type to ASCII or BINARY, using a crude approximation:
 * binary if more than 20% of the bytes are <= 6 or >= 128, ascii otherwise.
 * IN assertion: the fields freq of dyn_ltree are set and the total of all
 * frequencies does not exceed 64K (to fit in an int on 16 bit machines).
 */
local void
set_data_type(s)
    deflate_state *s;
{
        int n = 0;
        unsigned ascii_freq = 0;
        unsigned bin_freq = 0;
        while (n < 7)   bin_freq        += s->dyn_ltree[n++].Freq;
        while (n < 128) ascii_freq      += s->dyn_ltree[n++].Freq;
        while (n < LITERALS) bin_freq   += s->dyn_ltree[n++].Freq;
        s->data_type = (Byte)(bin_freq > (ascii_freq >> 2) ?
            Z_BINARY : Z_ASCII);
}

/*
 * ===========================================================================
 * Reverse the first len bits of a code, using straightforward code (a faster
 * method would use a table)
 * IN assertion: 1 <= len <= 15
 */
local unsigned
bi_reverse(code, len)
    unsigned code;      /* the value to invert */
    int len;    /* its bit length */
{
        register unsigned res = 0;
        do {
                res |= code & 1;
                code >>= 1, res <<= 1;
        } while (--len > 0);
        return (res >> 1);
}

/*
 * ===========================================================================
 * Flush the bit buffer, keeping at most 7 bits in it.
 */
local void
bi_flush(s)
    deflate_state *s;
{
        if (s->bi_valid == 16) {
                put_short(s, s->bi_buf);
                s->bi_buf = 0;
                s->bi_valid = 0;
        } else if (s->bi_valid >= 8) {
                put_byte(s, (Byte)s->bi_buf);
                s->bi_buf >>= 8;
                s->bi_valid -= 8;
        }
}

/*
 * ===========================================================================
 * Flush the bit buffer and align the output on a byte boundary
 */
local void
bi_windup(s)
    deflate_state *s;
{
        if (s->bi_valid > 8) {
                put_short(s, s->bi_buf);
        } else if (s->bi_valid > 0) {
                put_byte(s, (Byte)s->bi_buf);
        }
        s->bi_buf = 0;
        s->bi_valid = 0;
#ifdef DEBUG_ZLIB
        s->bits_sent = (s->bits_sent+7) & ~7;
#endif
}

/*
 * ===========================================================================
 * Copy a stored block, storing first the length and its
 * one's complement if requested.
 */
local void
copy_block(s, buf, len, header)
    deflate_state *s;
    charf    *buf;      /* the input data */
    unsigned len;       /* its length */
    int header; /* true if block header must be written */
{
        bi_windup(s);   /* align on byte boundary */
        s->last_eob_len = 8;    /* enough lookahead for inflate */

        if (header) {
                put_short(s, (ush)len);
                put_short(s, (ush)~len);
#ifdef DEBUG_ZLIB
                s->bits_sent += 2*16;
#endif
        }
#ifdef DEBUG_ZLIB
        s->bits_sent += (ulg)len<<3;
#endif
        /* bundle up the put_byte(s, *buf++) calls PPP */
        Assert(s->pending + len < s->pending_buf_size, "pending_buf overrun");
        zmemcpy(&s->pending_buf[s->pending], buf, len); /* PPP */
        s->pending += len;                              /* PPP */
}
/* --- trees.c */

/* +++ inflate.c */
/*
 * inflate.c -- zlib interface to inflate modules
 * Copyright (C) 1995-1998 Mark Adler
 * For conditions of distribution and use, see copyright notice in zlib.h
 */

/* #include "zutil.h" */

/* +++ infblock.h */
/*
 * infblock.h -- header to use infblock.c
 * Copyright (C) 1995-1998 Mark Adler
 * For conditions of distribution and use, see copyright notice in zlib.h
 */

/*
 * WARNING: this file should *not* be used by applications. It is part
 * of the implementation of the compression library and is subject to
 * change. Applications should only use zlib.h.
 */

struct inflate_blocks_state;
typedef struct inflate_blocks_state FAR inflate_blocks_statef;

extern inflate_blocks_statef * inflate_blocks_new OF((
    z_streamp z,
    check_func c,       /* check function */
    uInt w));   /* window size */

extern int inflate_blocks OF((
    inflate_blocks_statef *,
    z_streamp,
    int));      /* initial return code */

extern void inflate_blocks_reset OF((
    inflate_blocks_statef *,
    z_streamp,
    uLongf *)); /* check value on output */

extern int inflate_blocks_free OF((
    inflate_blocks_statef *,
    z_streamp));

extern void inflate_set_dictionary OF((
    inflate_blocks_statef *s,
    const Bytef *d,  /* dictionary */
    uInt  n));  /* dictionary length */

extern int inflate_blocks_sync_point OF((
    inflate_blocks_statef *s));

/* PPP -- added function */
extern int inflate_addhistory OF((
    inflate_blocks_statef *,
    z_streamp));

/* PPP -- added function */
extern int inflate_packet_flush OF((
    inflate_blocks_statef *));
/* --- infblock.h */

#ifndef NO_DUMMY_DECL
struct inflate_blocks_state {int dummy; };      /* for buggy compilers */
#endif

/* inflate private state */
struct internal_state {

        /* mode */
        enum {
                METHOD, /* waiting for method byte */
                FLAG,   /* waiting for flag byte */
                DICT4,  /* four dictionary check bytes to go */
                DICT3,  /* three dictionary check bytes to go */
                DICT2,  /* two dictionary check bytes to go */
                DICT1,  /* one dictionary check byte to go */
                DICT0,  /* waiting for inflateSetDictionary */
                BLOCKS, /* decompressing blocks */
                CHECK4, /* four check bytes to go */
                CHECK3, /* three check bytes to go */
                CHECK2, /* two check bytes to go */
                CHECK1, /* one check byte to go */
                DONE,   /* finished check, done */
                BAD}    /* got an error--stay here */
        mode;   /* current inflate mode */

        /* mode dependent information */
        union {
                uInt method;    /* if FLAGS, method byte */
                struct {
                        uLong was;      /* computed check value */
                        uLong need;     /* stream check value */
                } check;        /* if CHECK, check values to compare */
                uInt marker;    /* if BAD, inflateSync's marker bytes count */
        } sub;  /* submode */

        /* mode independent information */
        int  nowrap;    /* flag for no wrapper */
        uInt wbits;     /* log2(window size)  (8..15, defaults to 15) */
        /* current inflate_blocks state */
        inflate_blocks_statef *blocks;
};


int
inflateReset(z)
z_streamp z;
{
        if (z == Z_NULL || z->state == Z_NULL)
                return (Z_STREAM_ERROR);
        z->total_in = z->total_out = 0;
        z->msg = Z_NULL;
        z->state->mode = z->state->nowrap ? BLOCKS : METHOD;
        inflate_blocks_reset(z->state->blocks, z, Z_NULL);
        Trace((stderr, "inflate: reset\n"));
        return (Z_OK);
}


int
inflateEnd(z)
z_streamp z;
{
        if (z == Z_NULL || z->state == Z_NULL || z->zfree == Z_NULL)
                return (Z_STREAM_ERROR);
        if (z->state->blocks != Z_NULL) {
                (void) inflate_blocks_free(z->state->blocks, z);
                z->state->blocks = Z_NULL;
        }
        ZFREE(z, z->state);
        z->state = Z_NULL;
        Trace((stderr, "inflate: end\n"));
        return (Z_OK);
}


int
inflateInit2_(z, w, version, stream_size)
z_streamp z;
int w;
const char *version;
int stream_size;
{
        if (version == Z_NULL || version[0] != ZLIB_VERSION[0] ||
            stream_size != sizeof (z_stream))
                return (Z_VERSION_ERROR);

        /* initialize state */
        if (z == Z_NULL)
                return (Z_STREAM_ERROR);
        z->msg = Z_NULL;
#ifndef NO_ZCFUNCS
        if (z->zalloc == Z_NULL)
        {
                z->zalloc = zcalloc;
                z->opaque = (voidpf)0;
        }
        if (z->zfree == Z_NULL) z->zfree = zcfree;
#endif
        if ((z->state = (struct internal_state FAR *)
            ZALLOC(z, 1, sizeof (struct internal_state))) == Z_NULL)
                return (Z_MEM_ERROR);
        z->state->blocks = Z_NULL;

        /* handle undocumented nowrap option (no zlib header or check) */
        z->state->nowrap = 0;
        if (w < 0)
        {
                w = - w;
                z->state->nowrap = 1;
        }

        /* set window size */
        if (w < 8 || w > 15)
        {
                (void) inflateEnd(z);
                return (Z_STREAM_ERROR);
        }
        z->state->wbits = (uInt)w;

        /* create inflate_blocks state */
        if ((z->state->blocks =
            inflate_blocks_new(z, z->state->nowrap ?
                Z_NULL : adler32, (uInt)1 << w))
            == Z_NULL)
        {
                (void) inflateEnd(z);
                return (Z_MEM_ERROR);
        }
        Trace((stderr, "inflate: allocated\n"));

        /* reset state */
        (void) inflateReset(z);
        return (Z_OK);
}


int
inflateInit_(z, version, stream_size)
z_streamp z;
const char *version;
int stream_size;
{
        return (inflateInit2_(z, DEF_WBITS, version, stream_size));
}

/* PPP -- added "empty" label and changed f to Z_OK */
#define NEEDBYTE {if (z->avail_in == 0) goto empty; r = Z_OK; } ((void)0)
#define NEXTBYTE (z->avail_in--, z->total_in++, *z->next_in++)

int
inflate(z, f)
z_streamp z;
int f;
{
        int r;
        uInt b;

        if (z == Z_NULL || z->state == Z_NULL || z->next_in == Z_NULL)
                return (Z_STREAM_ERROR);
        /* f = f == Z_FINISH ? Z_BUF_ERROR : Z_OK; -- PPP; Z_FINISH unused */
        r = Z_BUF_ERROR;
        /* CONSTCOND */
        while (1)
                switch (z->state->mode)
        {
        case METHOD:
                NEEDBYTE;
                if (((z->state->sub.method = NEXTBYTE) & 0xf) != Z_DEFLATED)
                {
                        z->state->mode = BAD;
                        z->msg = "unknown compression method";
                        /* can't try inflateSync */
                        z->state->sub.marker = 5;
                        break;
                }
                if ((z->state->sub.method >> 4) + 8 > z->state->wbits)
                {
                        z->state->mode = BAD;
                        z->msg = "invalid window size";
                        /* can't try inflateSync */
                        z->state->sub.marker = 5;
                        break;
                }
                z->state->mode = FLAG;
                /* FALLTHRU */
        case FLAG:
                NEEDBYTE;
                b = NEXTBYTE;
                if (((z->state->sub.method << 8) + b) % 31)
                {
                        z->state->mode = BAD;
                        z->msg = "incorrect header check";
                        /* can't try inflateSync */
                        z->state->sub.marker = 5;
                        break;
                }
                Trace((stderr, "inflate: zlib header ok\n"));
                if (!(b & PRESET_DICT))
                {
                        z->state->mode = BLOCKS;
                        break;
                }
                z->state->mode = DICT4;
                /* FALLTHRU */
        case DICT4:
                NEEDBYTE;
                z->state->sub.check.need = (uLong)NEXTBYTE << 24;
                z->state->mode = DICT3;
                /* FALLTHRU */
        case DICT3:
                NEEDBYTE;
                z->state->sub.check.need += (uLong)NEXTBYTE << 16;
                z->state->mode = DICT2;
                /* FALLTHRU */
        case DICT2:
                NEEDBYTE;
                z->state->sub.check.need += (uLong)NEXTBYTE << 8;
                z->state->mode = DICT1;
                /* FALLTHRU */
        case DICT1:
                NEEDBYTE;
                z->state->sub.check.need += (uLong)NEXTBYTE;
                z->adler = z->state->sub.check.need;
                z->state->mode = DICT0;
                return (Z_NEED_DICT);
        case DICT0:
                z->state->mode = BAD;
                z->msg = "need dictionary";
                z->state->sub.marker = 0;       /* can try inflateSync */
                return (Z_STREAM_ERROR);
        case BLOCKS:
                r = inflate_blocks(z->state->blocks, z, r);
                if (f == Z_PACKET_FLUSH && z->avail_in == 0 &&  /* PPP */
                    z->avail_out != 0)                          /* PPP */
                        r = inflate_packet_flush(z->state->blocks); /* PPP */
                if (r == Z_DATA_ERROR)
                {
                        z->state->mode = BAD;
                        /* can try inflateSync */
                        z->state->sub.marker = 0;
                        break;
                }
                /* PPP */
                if (r != Z_STREAM_END)
                        return (r);
                r = Z_OK;       /* PPP */
                inflate_blocks_reset(z->state->blocks, z,
                    &z->state->sub.check.was);
                if (z->state->nowrap)
                {
                        z->state->mode = DONE;
                        break;
                }
                z->state->mode = CHECK4;
                /* FALLTHRU */
        case CHECK4:
                NEEDBYTE;
                z->state->sub.check.need = (uLong)NEXTBYTE << 24;
                z->state->mode = CHECK3;
                /* FALLTHRU */
        case CHECK3:
                NEEDBYTE;
                z->state->sub.check.need += (uLong)NEXTBYTE << 16;
                z->state->mode = CHECK2;
                /* FALLTHRU */
        case CHECK2:
                NEEDBYTE;
                z->state->sub.check.need += (uLong)NEXTBYTE << 8;
                z->state->mode = CHECK1;
                /* FALLTHRU */
        case CHECK1:
                NEEDBYTE;
                z->state->sub.check.need += (uLong)NEXTBYTE;

                if (z->state->sub.check.was != z->state->sub.check.need)
                {
                        z->state->mode = BAD;
                        z->msg = "incorrect data check";
                        /* can't try inflateSync */
                        z->state->sub.marker = 5;
                        break;
                }
                Trace((stderr, "inflate: zlib check ok\n"));
                z->state->mode = DONE;
                /* FALLTHRU */
        case DONE:
                return (Z_STREAM_END);
        case BAD:
                return (Z_DATA_ERROR);
        default:
                return (Z_STREAM_ERROR);
        }

/* PPP -- packet flush handling */
empty:
        if (f != Z_PACKET_FLUSH)
                return (r);
        z->state->mode = BAD;
        z->msg = "need more for packet flush";
        z->state->sub.marker = 0;       /* can try inflateSync */
        return (Z_DATA_ERROR);
}


int
inflateSetDictionary(z, dictionary, dictLength)
z_streamp z;
const Bytef *dictionary;
uInt  dictLength;
{
        uInt length = dictLength;

        if (z == Z_NULL || z->state == Z_NULL || z->state->mode != DICT0)
                return (Z_STREAM_ERROR);

        if (adler32(1L, dictionary, dictLength) != z->adler)
                return (Z_DATA_ERROR);
        z->adler = 1L;

        if (length >= ((uInt)1<<z->state->wbits))
        {
                length = (1<<z->state->wbits)-1;
                dictionary += dictLength - length;
        }
        inflate_set_dictionary(z->state->blocks, dictionary, length);
        z->state->mode = BLOCKS;
        return (Z_OK);
}

/*
 * This subroutine adds the data at next_in/avail_in to the output history
 * without performing any output.  The output buffer must be "caught up";
 * i.e. no pending output (hence s->read equals s->write), and the state must
 * be BLOCKS (i.e. we should be willing to see the start of a series of
 * BLOCKS).  On exit, the output will also be caught up, and the checksum
 * will have been updated if need be.
 *
 * Added for PPP.
 */

int
inflateIncomp(z)
z_stream *z;
{
        if (z->state->mode != BLOCKS)
                return (Z_DATA_ERROR);
        return (inflate_addhistory(z->state->blocks, z));
}


int
inflateSync(z)
z_streamp z;
{
        uInt n; /* number of bytes to look at */
        Bytef *p;       /* pointer to bytes */
        uInt m; /* number of marker bytes found in a row */
        uLong r, w;     /* temporaries to save total_in and total_out */

        /* set up */
        if (z == Z_NULL || z->state == Z_NULL)
                return (Z_STREAM_ERROR);
        if (z->state->mode != BAD)
        {
                z->state->mode = BAD;
                z->state->sub.marker = 0;
        }
        if ((n = z->avail_in) == 0)
                return (Z_BUF_ERROR);
        p = z->next_in;
        m = z->state->sub.marker;

        /* search */
        while (n && m < 4)
        {
                static const Byte mark[4] = { 0, 0, 0xff, 0xff };
                if (*p == mark[m])
                        m++;
                else if (*p)
                        m = 0;
                else
                        /*
                         * This statement maps 2->2 and 3->1 because a
                         * mismatch with input byte 0x00 on the first
                         * 0xFF in the pattern means that we still
                         * have two contiguous zeros matched (thus
                         * offset 2 is kept), but a mismatch on the
                         * second 0xFF means that only one 0x00 byte
                         * has been matched.  (Boyer-Moore like
                         * search.)
                         */
                        m = 4 - m;
                p++, n--;
        }

        /* restore */
        z->total_in += p - z->next_in;
        z->next_in = p;
        z->avail_in = n;
        z->state->sub.marker = m;

        /* return no joy or set up to restart on a new block */
        if (m != 4)
                return (Z_DATA_ERROR);
        r = z->total_in;  w = z->total_out;
        (void) inflateReset(z);
        z->total_in = r;  z->total_out = w;
        z->state->mode = BLOCKS;
        return (Z_OK);
}

/*
 * Returns true if inflate is currently at the end of a block
 * generated by Z_SYNC_FLUSH or Z_FULL_FLUSH. This function is used by
 * one PPP implementation to provide an additional safety check. PPP
 * uses Z_SYNC_FLUSH but removes the length bytes of the resulting
 * empty stored block. When decompressing, PPP checks that at the end
 * of input packet, inflate is waiting for these length bytes.
 */
int
inflateSyncPoint(z)
z_streamp z;
{
        if (z == Z_NULL || z->state == Z_NULL || z->state->blocks == Z_NULL)
                return (Z_STREAM_ERROR);
        return (inflate_blocks_sync_point(z->state->blocks));
}

#undef NEEDBYTE
#undef NEXTBYTE
/* --- inflate.c */

/* +++ infblock.c */
/*
 * infblock.c -- interpret and process block types to last block
 * Copyright (C) 1995-1998 Mark Adler
 * For conditions of distribution and use, see copyright notice in zlib.h
 */

/* #include "zutil.h" */
/* #include "infblock.h" */

/* +++ inftrees.h */
/*
 * inftrees.h -- header to use inftrees.c
 * Copyright (C) 1995-1998 Mark Adler
 * For conditions of distribution and use, see copyright notice in zlib.h
 */

/*
 * WARNING: this file should *not* be used by applications. It is part
 * of the implementation of the compression library and is subject to
 * change. Applications should only use zlib.h.
 */

/*
 * Huffman code lookup table entry--this entry is four bytes for
 * machines that have 16-bit pointers (e.g. PC's in the small or
 * medium model).
 */

typedef struct inflate_huft_s FAR inflate_huft;

struct inflate_huft_s {
        union {
                struct {
                        Byte Exop;      /* number of extra bits or operation */
                        /* number of bits in this code or subcode */
                        Byte Bits;
                } what;
                Bytef *pad;     /* pad structure to a power of 2 (4 bytes for */
        } word; /*  16-bit, 8 bytes for 32-bit machines) */
        /* literal, length base, distance base, or table offset */
        uInt base;
};

/*
 * Maximum size of dynamic tree.  The maximum found in a long but non-
 * exhaustive search was 1004 huft structures (850 for length/literals
 * and 154 for distances, the latter actually the result of an
 * exhaustive search).  The actual maximum is not known, but the value
 * below is more than safe.
 */
#define MANY 1440

extern int inflate_trees_bits OF((
    uIntf *,                    /* 19 code lengths */
    uIntf *,                    /* bits tree desired/actual depth */
    inflate_huft * FAR *,       /* bits tree result */
    inflate_huft *,             /* space for trees */
    z_streamp));        /* for zalloc, zfree functions */

extern int inflate_trees_dynamic OF((
    uInt,       /* number of literal/length codes */
    uInt,       /* number of distance codes */
    uIntf *,    /* that many (total) code lengths */
    uIntf *,    /* literal desired/actual bit depth */
    uIntf *,    /* distance desired/actual bit depth */
    inflate_huft * FAR *,       /* literal/length tree result */
    inflate_huft * FAR *,       /* distance tree result */
    inflate_huft *,             /* space for trees */
    z_streamp));        /* for zalloc, zfree functions */

extern int inflate_trees_fixed OF((
    uIntf *,    /* literal desired/actual bit depth */
    uIntf *,    /* distance desired/actual bit depth */
    const inflate_huft * FAR *, /* literal/length tree result */
    const inflate_huft * FAR *, /* distance tree result */
    z_streamp));

/* --- inftrees.h */

/* +++ infcodes.h */
/*
 * infcodes.h -- header to use infcodes.c
 * Copyright (C) 1995-1998 Mark Adler
 * For conditions of distribution and use, see copyright notice in zlib.h
 */

/*
 * WARNING: this file should *not* be used by applications. It is part
 * of the implementation of the compression library and is subject to
 * change. Applications should only use zlib.h.
 */

struct inflate_codes_state;
typedef struct inflate_codes_state FAR inflate_codes_statef;

extern inflate_codes_statef *inflate_codes_new OF((
    uInt, uInt,
    const inflate_huft *, const inflate_huft *,
    z_streamp));

extern int inflate_codes OF((
    inflate_blocks_statef *,
    z_streamp,
    int));

extern void inflate_codes_free OF((
    inflate_codes_statef *,
    z_streamp));

/* --- infcodes.h */

/* +++ infutil.h */
/*
 * infutil.h -- types and macros common to blocks and codes
 * Copyright (C) 1995-1998 Mark Adler
 * For conditions of distribution and use, see copyright notice in zlib.h
 */

/*
 * WARNING: this file should *not* be used by applications. It is part
 * of the implementation of the compression library and is subject to
 * change. Applications should only use zlib.h.
 */

#ifndef _INFUTIL_H
#define _INFUTIL_H

typedef enum {
        TYPE,   /* get type bits (3, including end bit) */
        LENS,   /* get lengths for stored */
        STORED, /* processing stored block */
        TABLE,  /* get table lengths */
        BTREE,  /* get bit lengths tree for a dynamic block */
        DTREE,  /* get length, distance trees for a dynamic block */
        CODES,  /* processing fixed or dynamic block */
        DRY,    /* output remaining window bytes */
        DONEB,  /* finished last block, done */
        BADB}   /* got a data error--stuck here */
inflate_block_mode;

/* inflate blocks semi-private state */
struct inflate_blocks_state {

        /* mode */
        inflate_block_mode  mode;       /* current inflate_block mode */

        /* mode dependent information */
        union {
                uInt left;      /* if STORED, bytes left to copy */
                struct {
                        uInt table;     /* table lengths (14 bits) */
                        uInt index;     /* index into blens (or border) */
                        uIntf *blens;   /* bit lengths of codes */
                        uInt bb;        /* bit length tree depth */
                        inflate_huft *tb;       /* bit length decoding tree */
                } trees;        /* if DTREE, decoding info for trees */
                struct {
                        inflate_codes_statef *codes;
                } decode;       /* if CODES, current state */
        } sub;  /* submode */
        uInt last;      /* true if this block is the last block */

        /* mode independent information */
        uInt bitk;      /* bits in bit buffer */
        uLong bitb;     /* bit buffer */
        inflate_huft *hufts;  /* single malloc for tree space */
        Bytef *window;  /* sliding window */
        Bytef *end;     /* one byte after sliding window */
        Bytef *read;    /* window read pointer */
        Bytef *write;   /* window write pointer */
        check_func checkfn;     /* check function */
        uLong check;    /* check on output */

};


/* defines for inflate input/output */
/*   update pointers and return */
#define UPDBITS {s->bitb = b; s->bitk = k; }
#define UPDIN {z->avail_in = n; z->total_in += p-z->next_in; z->next_in = p; }
#define UPDOUT {s->write = q; }
#define UPDATE {UPDBITS UPDIN UPDOUT}
#define LEAVE {UPDATE return (inflate_flush(s, z, r)); }
/*   get bytes and bits */
#define LOADIN {p = z->next_in; n = z->avail_in; b = s->bitb; k = s->bitk; }
#define NEEDBYTE { if (n) r = Z_OK; else LEAVE }
#define NEXTBYTE (n--, *p++)
#define NEEDBITS(j) { while (k < (j)) { NEEDBYTE; b |= ((uLong)NEXTBYTE)<<k; \
        k += 8; }}
#define DUMPBITS(j) {b >>= (j); k -= (j); }
/*   output bytes */
#define WAVAIL (uInt)(q < s->read ? s->read-q-1 : s->end-q)
#define LOADOUT {q = s->write; m = (uInt)WAVAIL; }
#define WWRAP {if (q == s->end && s->read != s->window) {q = s->window; \
        m = (uInt)WAVAIL; }}
#define FLUSH {UPDOUT r = inflate_flush(s, z, r); LOADOUT}
#define NEEDOUT {if (m == 0) {WWRAP if (m == 0) { FLUSH WWRAP \
        if (m == 0) LEAVE }} r = Z_OK; }
#define OUTBYTE(a) {*q++ = (Byte)(a); m--; }
/*   load local pointers */
#define LOAD {LOADIN LOADOUT}

/* masks for lower bits (size given to avoid silly warnings with Visual C++) */
extern uInt inflate_mask[17];

/* copy as much as possible from the sliding window to the output area */
extern int inflate_flush OF((
    inflate_blocks_statef *,
    z_streamp,
    int));

#ifndef NO_DUMMY_DECL
struct internal_state {int dummy; };    /* for buggy compilers */
#endif

#endif
/* --- infutil.h */

#ifndef NO_DUMMY_DECL
struct inflate_codes_state {int dummy; };       /* for buggy compilers */
#endif

/* Table for deflate from PKZIP's appnote.txt. */
local const uInt border[] = { /* Order of the bit length code lengths */
        16, 17, 18, 0, 8, 7, 9, 6, 10, 5, 11, 4, 12, 3, 13, 2, 14, 1, 15};

/*
 * Notes beyond the 1.93a appnote.txt:
 *
 *   1. Distance pointers never point before the beginning of the output
 *      stream.
 *   2. Distance pointers can point back across blocks, up to 32k away.
 *   3. There is an implied maximum of 7 bits for the bit length table and
 *      15 bits for the actual data.
 *   4. If only one code exists, then it is encoded using one bit.  (Zero
 *      would be more efficient, but perhaps a little confusing.)  If two
 *      codes exist, they are coded using one bit each (0 and 1).
 *   5. There is no way of sending zero distance codes--a dummy must be
 *      sent if there are none.  (History: a pre 2.0 version of PKZIP would
 *      store blocks with no distance codes, but this was discovered to be
 *      too harsh a criterion.)  Valid only for 1.93a.  2.04c does allow
 *      zero distance codes, which is sent as one code of zero bits in
 *      length.
 *   6. There are up to 286 literal/length codes.  Code 256 represents the
 *      end-of-block.  Note however that the static length tree defines
 *      288 codes just to fill out the Huffman codes.  Codes 286 and 287
 *      cannot be used though, since there is no length base or extra bits
 *      defined for them.  Similarily, there are up to 30 distance codes.
 *      However, static trees define 32 codes (all 5 bits) to fill out the
 *      Huffman codes, but the last two had better not show up in the data.
 *   7. Unzip can check dynamic Huffman blocks for complete code sets.
 *      The exception is that a single code would not be complete (see #4).
 *   8. The five bits following the block type is really the number of
 *      literal codes sent minus 257.
 *   9. Length codes 8,16,16 are interpreted as 13 length codes of 8 bits
 *      (1+6+6).  Therefore, to output three times the length, you output
 *      three codes (1+1+1), whereas to output four times the same length,
 *      you only need two codes (1+3).  Hmm.
 *  10. In the tree reconstruction algorithm, Code = Code + Increment
 *      only if BitLength(i) is not zero.  (Pretty obvious.)
 *  11. Correction: 4 Bits: #of Bit Length codes - 4     (4 - 19)
 *  12. Note: length code 284 can represent 227-258, but length code 285
 *      really is 258.  The last length deserves its own, short code
 *      since it gets used a lot in very redundant files.  The length
 *      258 is special since 258 - 3 (the min match length) is 255.
 *  13. The literal/length and distance code bit lengths are read as a
 *      single stream of lengths.  It is possible (and advantageous) for
 *      a repeat code (16, 17, or 18) to go across the boundary between
 *      the two sets of lengths.
 */


void
inflate_blocks_reset(s, z, c)
inflate_blocks_statef *s;
z_streamp z;
uLongf *c;
{
        if (c != Z_NULL)
                *c = s->check;
        if ((s->mode == BTREE || s->mode == DTREE) &&
            s->sub.trees.blens != Z_NULL) {
                ZFREE(z, s->sub.trees.blens);
                s->sub.trees.blens = Z_NULL;
        }
        if (s->mode == CODES && s->sub.decode.codes != Z_NULL) {
                (void) inflate_codes_free(s->sub.decode.codes, z);
                s->sub.decode.codes = Z_NULL;
        }
        s->mode = TYPE;
        s->bitk = 0;
        s->bitb = 0;
        s->read = s->write = s->window;
        if (s->checkfn != Z_NULL)
                z->adler = s->check = (*s->checkfn)(0L, Z_NULL, 0);
        Trace((stderr, "inflate:   blocks reset\n"));
}

inflate_blocks_statef *
inflate_blocks_new(z, c, w)
z_streamp z;
check_func c;
uInt w;
{
        inflate_blocks_statef *s;

        if ((s = (inflate_blocks_statef *)ZALLOC
            (z, 1, sizeof (struct inflate_blocks_state))) == Z_NULL)
                return (s);
        s->hufts = (inflate_huft *)ZALLOC(z, MANY, sizeof (inflate_huft));
        if (s->hufts == Z_NULL) {
                ZFREE(z, s);
                return (Z_NULL);
        }
        if ((s->window = (Bytef *)ZALLOC(z, 1, w)) == Z_NULL)
        {
                ZFREE(z, s->hufts);
                ZFREE(z, s);
                return (Z_NULL);
        }
        s->end = s->window + w;
        s->checkfn = c;
        s->mode = TYPE;
        Trace((stderr, "inflate:   blocks allocated\n"));
        inflate_blocks_reset(s, z, Z_NULL);
        return (s);
}


int
inflate_blocks(s, z, r)
inflate_blocks_statef *s;
z_streamp z;
int r;
{
        uInt t; /* temporary storage */
        uLong b;        /* bit buffer */
        uInt k; /* bits in bit buffer */
        Bytef *p;       /* input data pointer */
        uInt n; /* bytes available there */
        Bytef *q;       /* output window write pointer */
        uInt m; /* bytes to end of window or read pointer */

        /* copy input/output information to locals (UPDATE macro restores) */
        LOAD;

        /* process input based on current state */
        /* CONSTCOND */
        while (1)
                switch (s->mode)
        {
        case TYPE:
                NEEDBITS(3);
                t = (uInt)b & 7;
                s->last = t & 1;
                switch (t >> 1)
                {
                case 0:                 /* stored */
                        Trace((stderr, "inflate:     stored block%s\n",
                            s->last ? " (last)" : ""));
                        DUMPBITS(3);
                        t = k & 7;      /* go to byte boundary */
                        DUMPBITS(t);
                        s->mode = LENS; /* get length of stored block */
                        break;
                case 1:                 /* fixed */
                        Trace((stderr, "inflate:     fixed codes block%s\n",
                            s->last ? " (last)" : ""));
                        {
                                uInt bl, bd;
                                const inflate_huft *tl, *td;

                                (void) inflate_trees_fixed(&bl, &bd, &tl, &td,
                                    z);
                                s->sub.decode.codes = inflate_codes_new(bl,
                                    bd, tl, td, z);
                                if (s->sub.decode.codes == Z_NULL)
                                {
                                        r = Z_MEM_ERROR;
                                        LEAVE
                                }
                        }
                        DUMPBITS(3);
                        s->mode = CODES;
                        break;
                case 2:                 /* dynamic */
                        Trace((stderr, "inflate:     dynamic codes block%s\n",
                            s->last ? " (last)" : ""));
                        DUMPBITS(3);
                        s->mode = TABLE;
                        break;
                case 3:                 /* illegal */
                        DUMPBITS(3);
                        s->mode = BADB;
                        z->msg = "invalid block type";
                        r = Z_DATA_ERROR;
                        LEAVE
                }
                break;
        case LENS:
                NEEDBITS(32);
                if ((((~b) >> 16) & 0xffff) != (b & 0xffff))
                {
                        s->mode = BADB;
                        z->msg = "invalid stored block lengths";
                        r = Z_DATA_ERROR;
                        LEAVE
                }
                s->sub.left = (uInt)b & 0xffff;
                b = k = 0;      /* dump bits */
                Tracev((stderr, "inflate:       stored length %u\n",
                    s->sub.left));
                s->mode = s->sub.left ? STORED : (s->last ? DRY : TYPE);
                break;
        case STORED:
                if (n == 0)
                        LEAVE
                NEEDOUT;
                t = s->sub.left;
                if (t > n) t = n;
                if (t > m) t = m;
                zmemcpy(q, p, t);
                p += t;  n -= t;
                q += t;  m -= t;
                if ((s->sub.left -= t) != 0)
                        break;
                Tracev((stderr,
                    "inflate:       stored end, %lu total out\n",
                    z->total_out + (q >= s->read ? q - s->read :
                        (s->end - s->read) + (q - s->window))));
                s->mode = s->last ? DRY : TYPE;
                break;
        case TABLE:
                NEEDBITS(14);
                s->sub.trees.table = t = (uInt)b & 0x3fff;
#ifndef PKZIP_BUG_WORKAROUND
                if ((t & 0x1f) > 29 || ((t >> 5) & 0x1f) > 29)
                {
                        s->mode = BADB;
                        z->msg =
                            (char *)"too many length or distance symbols";
                        r = Z_DATA_ERROR;
                        LEAVE
                }
#endif
                t = 258 + (t & 0x1f) + ((t >> 5) & 0x1f);
                /* if (t < 19) t = 19; */
                if ((s->sub.trees.blens = (uIntf*)ZALLOC(z, t,
                    sizeof (uInt))) == Z_NULL)
                {
                        r = Z_MEM_ERROR;
                        LEAVE
                }
                DUMPBITS(14);
                s->sub.trees.index = 0;
                Tracev((stderr, "inflate:       table sizes ok\n"));
                s->mode = BTREE;
                /* FALLTHRU */
        case BTREE:
                while (s->sub.trees.index < 4 + (s->sub.trees.table >> 10))
                {
                        NEEDBITS(3);
                        s->sub.trees.blens[border[s->sub.trees.index++]] =
                            (uInt)b & 7;
                        DUMPBITS(3);
                }
                while (s->sub.trees.index < 19)
                        s->sub.trees.blens[border[s->sub.trees.index++]] =
                            0;
                s->sub.trees.bb = 7;
                t = inflate_trees_bits(s->sub.trees.blens, &s->sub.trees.bb,
                    &s->sub.trees.tb, s->hufts, z);
                if (t != Z_OK)
                {
                        ZFREE(z, s->sub.trees.blens);
                        s->sub.trees.blens = Z_NULL;
                        r = t;
                        if (r == Z_DATA_ERROR)
                                s->mode = BADB;
                        LEAVE
                }
                s->sub.trees.index = 0;
                Tracev((stderr, "inflate:       bits tree ok\n"));
                s->mode = DTREE;
                /* FALLTHRU */
        case DTREE:
                while (t = s->sub.trees.table,
                    s->sub.trees.index < 258 + (t & 0x1f) +
                    ((t >> 5) & 0x1f))
                {
                        inflate_huft *h;
                        uInt i, j, c;

                        t = s->sub.trees.bb;
                        NEEDBITS(t);
                        h = s->sub.trees.tb + ((uInt)b & inflate_mask[t]);
                        t = h->word.what.Bits;
                        c = h->base;
                        if (c < 16)
                        {
                                DUMPBITS(t);
                                s->sub.trees.blens[s->sub.trees.index++] =
                                    c;
                        } else { /* c == 16..18 */
                                i = c == 18 ? 7 : c - 14;
                                j = c == 18 ? 11 : 3;
                                NEEDBITS(t + i);
                                DUMPBITS(t);
                                j += (uInt)b & inflate_mask[i];
                                DUMPBITS(i);
                                i = s->sub.trees.index;
                                t = s->sub.trees.table;
                                if (i + j > 258 + (t & 0x1f) +
                                    ((t >> 5) & 0x1f) ||
                                    (c == 16 && i < 1))
                                {
                                        ZFREE(z, s->sub.trees.blens);
                                        s->sub.trees.blens = Z_NULL;
                                        s->mode = BADB;
                                        z->msg = "invalid bit length repeat";
                                        r = Z_DATA_ERROR;
                                        LEAVE
                                }
                                c = c == 16 ? s->sub.trees.blens[i - 1] : 0;
                                do {
                                        s->sub.trees.blens[i++] = c;
                                } while (--j);
                                s->sub.trees.index = i;
                        }
                }
                s->sub.trees.tb = Z_NULL;
                {
                        uInt bl, bd;
                        inflate_huft *tl, *td;
                        inflate_codes_statef *c;

                                /* must be <= 9 for lookahead assumptions */
                        bl = 9;
                                /* must be <= 9 for lookahead assumptions */
                        bd = 6;
                        t = s->sub.trees.table;
                        t = inflate_trees_dynamic(257 + (t & 0x1f),
                            1 + ((t >> 5) & 0x1f),
                            s->sub.trees.blens, &bl, &bd, &tl, &td,
                            s->hufts, z);
                        ZFREE(z, s->sub.trees.blens);
                        s->sub.trees.blens = Z_NULL;
                        if (t != Z_OK)
                        {
                                if (t == (uInt)Z_DATA_ERROR)
                                        s->mode = BADB;
                                r = t;
                                LEAVE
                        }
                        Tracev((stderr, "inflate:       trees ok\n"));
                        if ((c = inflate_codes_new(bl, bd, tl, td, z)) ==
                            Z_NULL)
                        {
                                r = Z_MEM_ERROR;
                                LEAVE
                        }
                        s->sub.decode.codes = c;
                }
                s->mode = CODES;
                /* FALLTHRU */
        case CODES:
                UPDATE;
                if ((r = inflate_codes(s, z, r)) != Z_STREAM_END)
                        return (inflate_flush(s, z, r));
                r = Z_OK;
                (void) inflate_codes_free(s->sub.decode.codes, z);
                LOAD;
                Tracev((stderr, "inflate:       codes end, %lu total out\n",
                    z->total_out + (q >= s->read ? q - s->read :
                        (s->end - s->read) + (q - s->window))));
                if (!s->last)
                {
                        s->mode = TYPE;
                        break;
                }
                s->mode = DRY;
                /* FALLTHRU */
        case DRY:
                FLUSH;
                if (s->read != s->write)
                        LEAVE
                s->mode = DONEB;
                /* FALLTHRU */
        case DONEB:
                r = Z_STREAM_END;
                LEAVE
        case BADB:
                r = Z_DATA_ERROR;
                LEAVE
        default:
                r = Z_STREAM_ERROR;
                LEAVE
        }
        /* NOTREACHED */
        /* otherwise lint complains */
}


int
inflate_blocks_free(s, z)
inflate_blocks_statef *s;
z_streamp z;
{
        inflate_blocks_reset(s, z, Z_NULL);
        ZFREE(z, s->window);
        s->window = Z_NULL;
        ZFREE(z, s->hufts);
        s->hufts = Z_NULL;
        ZFREE(z, s);
        Trace((stderr, "inflate:   blocks freed\n"));
        return (Z_OK);
}


void
inflate_set_dictionary(s, d, n)
inflate_blocks_statef *s;
const Bytef *d;
uInt  n;
{
        Assert(s->window + n <= s->end, "set dict");
        zmemcpy((charf *)s->window, d, n);
        s->read = s->write = s->window + n;
}

/*
 * Returns true if inflate is currently at the end of a block
 * generated by Z_SYNC_FLUSH or Z_FULL_FLUSH.
 * IN assertion: s != Z_NULL
 */
int
inflate_blocks_sync_point(s)
inflate_blocks_statef *s;
{
        return (s->mode == LENS);
}

/*
 * This subroutine adds the data at next_in/avail_in to the output history
 * without performing any output.  The output buffer must be "caught up";
 * i.e. no pending output (hence s->read equals s->write), and the state must
 * be BLOCKS (i.e. we should be willing to see the start of a series of
 * BLOCKS).  On exit, the output will also be caught up, and the checksum
 * will have been updated if need be.
 */
int
inflate_addhistory(s, z)
inflate_blocks_statef *s;
z_stream *z;
{
        uLong b;        /* bit buffer */  /* NOT USED HERE */
        uInt k; /* bits in bit buffer */ /* NOT USED HERE */
        uInt t; /* temporary storage */
        Bytef *p;       /* input data pointer */
        uInt n; /* bytes available there */
        Bytef *q;       /* output window write pointer */
        uInt m; /* bytes to end of window or read pointer */

        if (s->read != s->write)
                return (Z_STREAM_ERROR);
        if (s->mode != TYPE)
                return (Z_DATA_ERROR);

        /* we're ready to rock */
        LOAD;
        /*
         * while there is input ready, copy to output buffer, moving
         * pointers as needed.
         */
        while (n) {
                t = n;  /* how many to do */
                /* is there room until end of buffer? */
                if (t > m) t = m;
                /* update check information */
                if (s->checkfn != Z_NULL)
                        s->check = (*s->checkfn)(s->check, q, t);
                zmemcpy(q, p, t);
                q += t;
                p += t;
                n -= t;
                z->total_out += t;
                s->read = q;    /* drag read pointer forward */
/* WWRAP */     /* expand WWRAP macro by hand to handle s->read */
                if (q == s->end) {
                        s->read = q = s->window;
                        m = WAVAIL;
                }
        }
        UPDATE;
        return (Z_OK);
}


/*
 * At the end of a Deflate-compressed PPP packet, we expect to have seen
 * a `stored' block type value but not the (zero) length bytes.
 */
int
inflate_packet_flush(s)
    inflate_blocks_statef *s;
{
        if (s->mode != LENS)
                return (Z_DATA_ERROR);
        s->mode = TYPE;
        return (Z_OK);
}
/* --- infblock.c */

/* +++ inftrees.c */
/*
 * inftrees.c -- generate Huffman trees for efficient decoding
 * Copyright (C) 1995-1998 Mark Adler
 * For conditions of distribution and use, see copyright notice in zlib.h
 */

/* #include "zutil.h" */
/* #include "inftrees.h" */

const char inflate_copyright[] =
" inflate 1.1.3 Copyright 1995-1998 Mark Adler ";
/*
 * If you use the zlib library in a product, an acknowledgment is
 * welcome in the documentation of your product. If for some reason
 * you cannot include such an acknowledgment, I would appreciate that
 * you keep this copyright string in the executable of your product.
 */

#ifndef NO_DUMMY_DECL
struct internal_state  {int dummy; };   /* for buggy compilers */
#endif

/* simplify the use of the inflate_huft type with some defines */
#define exop word.what.Exop
#define bits word.what.Bits


local int huft_build OF((
        uIntf *,        /* code lengths in bits */
        uInt,           /* number of codes */
        uInt,           /* number of "simple" codes */
        const uIntf *,  /* list of base values for non-simple codes */
        const uIntf *,  /* list of extra bits for non-simple codes */
        inflate_huft * FAR*, /* result: starting table */
        uIntf *,        /* maximum lookup bits (returns actual) */
        inflate_huft *hp,       /* space for trees */
        uInt *hn,       /* hufts used in space */
        uIntf *v));     /* working area: values in order of bit length */

/* Tables for deflate from PKZIP's appnote.txt. */
local const uInt cplens[31] = { /* Copy lengths for literal codes 257..285 */
        3, 4, 5, 6, 7, 8, 9, 10, 11, 13, 15, 17, 19, 23, 27, 31,
        35, 43, 51, 59, 67, 83, 99, 115, 131, 163, 195, 227, 258, 0, 0};
        /* see note #13 above about 258 */
local const uInt cplext[31] = { /* Extra bits for literal codes 257..285 */
        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, 112, 112};
        /* 112==invalid */
local const uInt cpdist[30] = { /* Copy offsets for distance codes 0..29 */
        1, 2, 3, 4, 5, 7, 9, 13, 17, 25, 33, 49, 65, 97, 129, 193,
        257, 385, 513, 769, 1025, 1537, 2049, 3073, 4097, 6145,
        8193, 12289, 16385, 24577};
local const uInt cpdext[30] = { /* Extra bits for distance codes */
        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};

/*
 * Huffman code decoding is performed using a multi-level table
 * lookup.  The fastest way to decode is to simply build a lookup
 * table whose size is determined by the longest code.  However, the
 * time it takes to build this table can also be a factor if the data
 * being decoded is not very long.  The most common codes are
 * necessarily the shortest codes, so those codes dominate the
 * decoding time, and hence the speed.  The idea is you can have a
 * shorter table that decodes the shorter, more probable codes, and
 * then point to subsidiary tables for the longer codes.  The time it
 * costs to decode the longer codes is then traded against the time it
 * takes to make longer tables.
 *
 * This results of this trade are in the variables lbits and dbits
 * below.  lbits is the number of bits the first level table for
 * literal/ length codes can decode in one step, and dbits is the same
 * thing for the distance codes.  Subsequent tables are also less than
 * or equal to those sizes.  These values may be adjusted either when
 * all of the codes are shorter than that, in which case the longest
 * code length in bits is used, or when the shortest code is *longer*
 * than the requested table size, in which case the length of the
 * shortest code in bits is used.
 *
 * There are two different values for the two tables, since they code
 * a different number of possibilities each.  The literal/length table
 * codes 286 possible values, or in a flat code, a little over eight
 * bits.  The distance table codes 30 possible values, or a little
 * less than five bits, flat.  The optimum values for speed end up
 * being about one bit more than those, so lbits is 8+1 and dbits is
 * 5+1.  The optimum values may differ though from machine to machine,
 * and possibly even between compilers.  Your mileage may vary.
 */


/* If BMAX needs to be larger than 16, then h and x[] should be uLong. */
#define BMAX 15         /* maximum bit length of any code */


local int
huft_build(b, n, s, d, e, t, m, hp, hn, v)
uIntf *b;       /* code lengths in bits (all assumed <= BMAX) */
uInt n; /* number of codes (assumed <= 288) */
uInt s; /* number of simple-valued codes (0..s-1) */
const uIntf *d; /* list of base values for non-simple codes */
const uIntf *e; /* list of extra bits for non-simple codes */
inflate_huft * FAR *t;  /* result: starting table */
uIntf *m;       /* maximum lookup bits, returns actual */
inflate_huft *hp;       /* space for trees */
uInt *hn;               /* hufts used in space */
uIntf *v;               /* working area: values in order of bit length */
/*
 * Given a list of code lengths and a maximum table size, make a set
 * of tables to decode that set of codes.  Return Z_OK on success,
 * Z_BUF_ERROR if the given code set is incomplete (the tables are
 * still built in this case), Z_DATA_ERROR if the input is invalid (an
 * over-subscribed set of lengths), or Z_MEM_ERROR if not enough
 * memory.
 */
{

        uInt a; /* counter for codes of length k */
        uInt c[BMAX+1]; /* bit length count table */
        uInt f; /* i repeats in table every f entries */
        int g;  /* maximum code length */
        int h;  /* table level */
        register uInt i;        /* counter, current code */
        register uInt j;        /* counter */
        register int k; /* number of bits in current code */
        int l;  /* bits per table (returned in m) */
        register uIntf *p;      /* pointer into c[], b[], or v[] */
        inflate_huft *q;        /* points to current table */
        struct inflate_huft_s r; /* table entry for structure assignment */
        inflate_huft *u[BMAX];  /* table stack */
        uInt mask;      /* (1 << w) - 1, to avoid cc -O bug on HP */
        register int w; /* bits before this table == (l * h) */
        uInt x[BMAX+1]; /* bit offsets, then code stack */
        uIntf *xp;      /* pointer into x */
        int y;  /* number of dummy codes added */
        uInt z; /* number of entries in current table */

        (void) inflate_copyright;
        /* Generate counts for each bit length */
        p = c;
#define C0 *p++ = 0;
#define C2 C0 C0 C0 C0
#define C4 C2 C2 C2 C2
        C4      /* clear c[]--assume BMAX+1 is 16 */
            p = b;  i = n;
        do {
                c[*p++]++;      /* assume all entries <= BMAX */
        } while (--i);
        if (c[0] == n)          /* null input--all zero length codes */
        {
                *t = (inflate_huft *)Z_NULL;
                *m = 0;
                return (Z_OK);
        }


        /* Find minimum and maximum length, bound *m by those */
        l = *m;
        for (j = 1; j <= BMAX; j++)
                if (c[j])
                        break;
        k = j;  /* minimum code length */
        if ((uInt)l < j)
                l = j;
        for (i = BMAX; i; i--)
                if (c[i])
                        break;
        g = i;  /* maximum code length */
        if ((uInt)l > i)
                l = i;
        *m = l;


        /* Adjust last length count to fill out codes, if needed */
        for (y = 1 << j; j < i; j++, y <<= 1)
                if ((y -= c[j]) < 0)
                        return (Z_DATA_ERROR);
        if ((y -= c[i]) < 0)
                return (Z_DATA_ERROR);
        c[i] += y;


        /* Generate starting offsets into the value table for each length */
        x[1] = j = 0;
        p = c + 1;  xp = x + 2;
        while (--i) {           /* note that i == g from above */
                *xp++ = (j += *p++);
        }


        /* Make a table of values in order of bit lengths */
        p = b;  i = 0;
        do {
                if ((j = *p++) != 0)
                        v[x[j]++] = i;
        } while (++i < n);
        n = x[g];       /* set n to length of v */


        /* Generate the Huffman codes and for each, make the table entries */
        x[0] = i = 0;   /* first Huffman code is zero */
        p = v;  /* grab values in bit order */
        h = -1; /* no tables yet--level -1 */
        w = -l; /* bits decoded == (l * h) */
        u[0] = (inflate_huft *)Z_NULL;  /* just to keep compilers happy */
        q = (inflate_huft *)Z_NULL;     /* ditto */
        z = 0;  /* ditto */

        /* go through the bit lengths (k already is bits in shortest code) */
        for (; k <= g; k++) {
                a = c[k];
                while (a--) {
                        /*
                         * here i is the Huffman code of length k bits
                         * for value *p.  make tables up to required
                         * level.
                         */
                        while (k > w + l) {
                                h++;
                                w += l; /* previous table always l bits */

                                /*
                                 * compute minimum size table less
                                 * than or equal to l bits
                                 */
                                z = g - w;
                                /* table size upper limit */
                                z = z > (uInt)l ? l : z;
                                /* try a k-w bit table */
                                if ((f = 1 << (j = k - w)) > a + 1) {
                                        /* too few codes for k-w bit table */
                                        /* deduct codes from patterns left */
                                        f -= a + 1;
                                        xp = c + k;
                                        if (j < z)
                                                /*
                                                 * try smaller tables
                                                 * up to z bits
                                                 */
                                                while (++j < z) {
                                                        /*
                                                         * enough
                                                         * codes to
                                                         * use up j
                                                         * bits
                                                         */
                                                        if ((f <<= 1) <= *++xp)
                                                                break;
                                                        f -= *xp;
                                                        /*
                                                         * else deduct
                                                         * codes from
                                                         * patterns
                                                         */
                                                }
                                }
                                /* table entries for j-bit table */
                                z = 1 << j;

                                /* allocate new table */
                                /* (note: doesn't matter for fixed) */
                                /* not enough memory */
                                if (*hn + z > MANY)
                                        return (Z_MEM_ERROR);
                                u[h] = q = hp + *hn;
                                *hn += z;

                                /* connect to last table, if there is one */
                                if (h) {
                                        /* save pattern for backing up */
                                        x[h] = i;
                                        /* bits to dump before this table */
                                        r.bits = (Byte)l;
                                        /* bits in this table */
                                        r.exop = (Byte)j;
                                        j = i >> (w - l);
                                        /* offset to this table */
                                        r.base = (uInt)(q - u[h-1] - j);
                                        /* connect to last table */
                                        u[h-1][j] = r;
                                } else
                                        /* first table is returned result */
                                        *t = q;
                        }

                        /* set up table entry in r */
                        r.bits = (Byte)(k - w);
                        if (p >= v + n)
                                /* out of values--invalid code */
                                r.exop = 128 + 64;
                        else if (*p < s)
                        {
                                /* 256 is end-of-block */
                                r.exop = (Byte)(*p < 256 ? 0 : 32 + 64);
                                /* simple code is just the value */
                                r.base = *p++;
                        }
                        else
                        {
                                /* non-simple--look up in lists */
                                r.exop = (Byte)(e[*p - s] + 16 + 64);
                                r.base = d[*p++ - s];
                        }

                        /* fill code-like entries with r */
                        f = 1 << (k - w);
                        for (j = i >> w; j < z; j += f)
                                q[j] = r;

                        /* backwards increment the k-bit code i */
                        for (j = 1 << (k - 1); i & j; j >>= 1)
                                i ^= j;
                        i ^= j;

                        /* backup over finished tables */
                        mask = (1 << w) - 1;    /* needed on HP, cc -O bug */
                        while ((i & mask) != x[h])
                        {
                                h--;    /* don't need to update q */
                                w -= l;
                                mask = (1 << w) - 1;
                        }
                }
        }


        /* Return Z_BUF_ERROR if we were given an incomplete table */
        return (y != 0 && g != 1 ? Z_BUF_ERROR : Z_OK);
}


int
inflate_trees_bits(c, bb, tb, hp, z)
uIntf *c;       /* 19 code lengths */
uIntf *bb;      /* bits tree desired/actual depth */
inflate_huft * FAR *tb; /* bits tree result */
inflate_huft *hp;       /* space for trees */
z_streamp z;    /* for zfree function */
{
        int r;
        uInt hn = 0;            /* hufts used in space */
        uIntf v[19];            /* work area for huft_build */

        r = huft_build(c, 19, 19, (uIntf*)Z_NULL, (uIntf*)Z_NULL, tb, bb,
            hp, &hn, v);
        if (r == Z_DATA_ERROR)
                z->msg = "oversubscribed dynamic bit lengths tree";
        else if (r == Z_BUF_ERROR || *bb == 0)
        {
                z->msg = "incomplete dynamic bit lengths tree";
                r = Z_DATA_ERROR;
        }
        return (r);
}


int
inflate_trees_dynamic(nl, nd, c, bl, bd, tl, td, hp, z)
uInt nl;        /* number of literal/length codes */
uInt nd;        /* number of distance codes */
uIntf *c;       /* that many (total) code lengths */
uIntf *bl;      /* literal desired/actual bit depth */
uIntf *bd;      /* distance desired/actual bit depth */
inflate_huft * FAR *tl; /* literal/length tree result */
inflate_huft * FAR *td; /* distance tree result */
inflate_huft *hp;       /* space for trees */
z_streamp z;    /* for zfree function */
{
        int r;
        uInt hn = 0;            /* hufts used in space */
        uIntf v[288];           /* work area for huft_build */

        /* build literal/length tree */
        r = huft_build(c, nl, 257, cplens, cplext, tl, bl, hp, &hn, v);
        if (r != Z_OK || *bl == 0)
        {
                if (r == Z_DATA_ERROR)
                        z->msg = "oversubscribed literal/length tree";
                else if (r != Z_MEM_ERROR)
                {
                        z->msg = "incomplete literal/length tree";
                        r = Z_DATA_ERROR;
                }
                return (r);
        }

        /* build distance tree */
        r = huft_build(c + nl, nd, 0, cpdist, cpdext, td, bd, hp, &hn, v);
        if (r != Z_OK || (*bd == 0 && nl > 257))
        {
                if (r == Z_DATA_ERROR)
                        z->msg = "oversubscribed distance tree";
                else if (r == Z_BUF_ERROR) {
#ifdef PKZIP_BUG_WORKAROUND
                        r = Z_OK;
#else
                        z->msg = "incomplete distance tree";
                        r = Z_DATA_ERROR;
                } else if (r != Z_MEM_ERROR) {
                        z->msg = "empty distance tree with lengths";
                        r = Z_DATA_ERROR;
#endif
                }
                return (r);
        }

/* done */
        return (Z_OK);
}


/* build fixed tables only once--keep them here */
/* #define      BUILDFIXED */
#ifdef BUILDFIXED
local int fixed_built = 0;
#define FIXEDH 544      /* number of hufts used by fixed tables */
local inflate_huft fixed_mem[FIXEDH];
local uInt fixed_bl;
local uInt fixed_bd;
local inflate_huft *fixed_tl;
local inflate_huft *fixed_td;
#else
#include "inffixed.h"
#endif

/*ARGSUSED*/
int
inflate_trees_fixed(bl, bd, tl, td, z)
uIntf *bl;      /* literal desired/actual bit depth */
uIntf *bd;      /* distance desired/actual bit depth */
const inflate_huft * FAR *tl;   /* literal/length tree result */
const inflate_huft * FAR *td;   /* distance tree result */
z_streamp z;    /* for memory allocation */
{
#ifdef BUILDFIXED
        /*
         * build fixed tables if not already (multiple overlapped
         * executions ok)
         */
        if (!fixed_built)
        {
                int k;  /* temporary variable */
                uInt f = 0;     /* number of hufts used in fixed_mem */
                uIntf *c;       /* length list for huft_build */
                uIntf *v;

                /* allocate memory */
                if ((c = (uIntf*)ZALLOC(z, 288, sizeof (uInt))) == Z_NULL)
                        return (Z_MEM_ERROR);
                if ((v = (uIntf*)ZALLOC(z, 288, sizeof (uInt))) == Z_NULL)
                {
                        ZFREE(z, c);
                        return (Z_MEM_ERROR);
                }
                /* literal table */
                for (k = 0; k < 144; k++)
                        c[k] = 8;
                for (; k < 256; k++)
                        c[k] = 9;
                for (; k < 280; k++)
                        c[k] = 7;
                for (; k < 288; k++)
                        c[k] = 8;
                fixed_bl = 9;
                (void) huft_build(c, 288, 257, cplens, cplext, &fixed_tl,
                    &fixed_bl, fixed_mem, &f, v);

                /* distance table */
                for (k = 0; k < 30; k++)
                        c[k] = 5;
                fixed_bd = 5;
                (void) huft_build(c, 30, 0, cpdist, cpdext, &fixed_td,
                    &fixed_bd, fixed_mem, &f, v);

                /* done */
                ZFREE(z, v);
                ZFREE(z, c);
                fixed_built = 1;
        }
#endif
        *bl = fixed_bl;
        *bd = fixed_bd;
        *tl = fixed_tl;
        *td = fixed_td;
        return (Z_OK);
}
/* --- inftrees.c */

/* +++ infcodes.c */
/*
 * infcodes.c -- process literals and length/distance pairs
 * Copyright (C) 1995-1998 Mark Adler
 * For conditions of distribution and use, see copyright notice in zlib.h
 */

/* #include "zutil.h" */
/* #include "inftrees.h" */
/* #include "infblock.h" */
/* #include "infcodes.h" */
/* #include "infutil.h" */

/* +++ inffast.h */
/*
 * inffast.h -- header to use inffast.c
 * Copyright (C) 1995-1998 Mark Adler
 * For conditions of distribution and use, see copyright notice in zlib.h
 */

/*
 * WARNING: this file should *not* be used by applications. It is part
 * of the implementation of the compression library and is subject to
 * change. Applications should only use zlib.h.
 */

extern int inflate_fast OF((
    uInt,
    uInt,
    const inflate_huft *,
    const inflate_huft *,
    inflate_blocks_statef *,
    z_streamp));
/* --- inffast.h */

/* simplify the use of the inflate_huft type with some defines */
#define exop word.what.Exop
#define bits word.what.Bits

/* inflate codes private state */
struct inflate_codes_state {

        /* mode */
        enum {  /* waiting for "i:"=input, "o:"=output, "x:"=nothing */
                START,  /* x: set up for LEN */
                LEN,    /* i: get length/literal/eob next */
                LENEXT, /* i: getting length extra (have base) */
                DIST,   /* i: get distance next */
                DISTEXT,        /* i: getting distance extra */
                COPY,   /* o: copying bytes in window, waiting for space */
                LIT,    /* o: got literal, waiting for output space */
                WASH,   /* o: got eob, possibly still output waiting */
                END,    /* x: got eob and all data flushed */
                BADCODE}        /* x: got error */
        mode;   /* current inflate_codes mode */

        /* mode dependent information */
        uInt len;
        union {
                struct {
                        const inflate_huft *tree;       /* pointer into tree */
                        uInt need;      /* bits needed */
                } code; /* if LEN or DIST, where in tree */
                uInt lit;       /* if LIT, literal */
                struct {
                        uInt get;       /* bits to get for extra */
                        uInt dist;      /* distance back to copy from */
                } copy; /* if EXT or COPY, where and how much */
        } sub;  /* submode */

        /* mode independent information */
        Byte lbits;     /* ltree bits decoded per branch */
        Byte dbits;     /* dtree bits decoder per branch */
        const inflate_huft *ltree;      /* literal/length/eob tree */
        const inflate_huft *dtree;      /* distance tree */

};


inflate_codes_statef *
inflate_codes_new(bl, bd, tl, td, z)
uInt bl, bd;
const inflate_huft *tl;
const inflate_huft *td; /* need separate declaration for Borland C++ */
z_streamp z;
{
        inflate_codes_statef *c;

        if ((c = (inflate_codes_statef *)
            ZALLOC(z, 1, sizeof (struct inflate_codes_state))) != Z_NULL)
        {
                c->mode = START;
                c->lbits = (Byte)bl;
                c->dbits = (Byte)bd;
                c->ltree = tl;
                c->dtree = td;
                Tracev((stderr, "inflate:       codes new\n"));
        }
        return (c);
}


int
inflate_codes(s, z, r)
inflate_blocks_statef *s;
z_streamp z;
int r;
{
        uInt j; /* temporary storage */
        const inflate_huft *t;  /* temporary pointer */
        uInt e; /* extra bits or operation */
        uLong b;        /* bit buffer */
        uInt k; /* bits in bit buffer */
        Bytef *p;       /* input data pointer */
        uInt n; /* bytes available there */
        Bytef *q;       /* output window write pointer */
        uInt m; /* bytes to end of window or read pointer */
        Bytef *f;       /* pointer to copy strings from */
        inflate_codes_statef *c = s->sub.decode.codes;  /* codes state */

        /* copy input/output information to locals (UPDATE macro restores) */
        LOAD;

        /* process input and output based on current state */
        /* CONSTCOND */
        while (1)
                /* waiting for "i:"=input, "o:"=output, "x:"=nothing */
                switch (c->mode) {
                case START:     /* x: set up for LEN */
#ifndef SLOW
                        if (m >= 258 && n >= 10)
                        {
                                UPDATE;
                                r = inflate_fast(c->lbits, c->dbits,
                                    c->ltree, c->dtree, s, z);
                                LOAD;
                                if (r != Z_OK) {
                                        c->mode = r == Z_STREAM_END ?
                                            WASH : BADCODE;
                                        break;
                                }
                        }
#endif /* !SLOW */
                        c->sub.code.need = c->lbits;
                        c->sub.code.tree = c->ltree;
                        c->mode = LEN;
                        /* FALLTHRU */
                case LEN:       /* i: get length/literal/eob next */
                        j = c->sub.code.need;
                        NEEDBITS(j);
                        t = c->sub.code.tree +
                            ((uInt)b & inflate_mask[j]);
                        DUMPBITS(t->bits);
                        e = (uInt)(t->exop);
                        if (e == 0) {   /* literal */
                                c->sub.lit = t->base;
                                Tracevv((stderr, t->base >= 0x20 &&
                                    t->base < 0x7f ?
                                    "inflate:         literal '%c'\n" :
                                    "inflate:         literal 0x%02x\n",
                                    t->base));
                                c->mode = LIT;
                                break;
                        }
                        if (e & 16) {   /* length */
                                c->sub.copy.get = e & 15;
                                c->len = t->base;
                                c->mode = LENEXT;
                                break;
                        }
                        if ((e & 64) == 0) {    /* next table */
                                c->sub.code.need = e;
                                c->sub.code.tree = t + t->base;
                                break;
                        }
                        if (e & 32) {   /* end of block */
                                Tracevv((stderr,
                                    "inflate:         end of block\n"));
                                c->mode = WASH;
                                break;
                        }
                        c->mode = BADCODE;      /* invalid code */
                        z->msg = "invalid literal/length code";
                        r = Z_DATA_ERROR;
                        LEAVE
                case LENEXT:    /* i: getting length extra (have base) */
                        j = c->sub.copy.get;
                        NEEDBITS(j);
                        c->len += (uInt)b & inflate_mask[j];
                        DUMPBITS(j);
                        c->sub.code.need = c->dbits;
                        c->sub.code.tree = c->dtree;
                        Tracevv((stderr,
                            "inflate:         length %u\n", c->len));
                        c->mode = DIST;
                        /* FALLTHRU */
                case DIST:      /* i: get distance next */
                        j = c->sub.code.need;
                        NEEDBITS(j);
                        t = c->sub.code.tree + ((uInt)b & inflate_mask[j]);
                        DUMPBITS(t->bits);
                        e = (uInt)(t->exop);
                        if (e & 16) {   /* distance */
                                c->sub.copy.get = e & 15;
                                c->sub.copy.dist = t->base;
                                c->mode = DISTEXT;
                                break;
                        }
                        if ((e & 64) == 0) {    /* next table */
                                c->sub.code.need = e;
                                c->sub.code.tree = t + t->base;
                                break;
                        }
                        c->mode = BADCODE;      /* invalid code */
                        z->msg = "invalid distance code";
                        r = Z_DATA_ERROR;
                        LEAVE
                case DISTEXT:   /* i: getting distance extra */
                        j = c->sub.copy.get;
                        NEEDBITS(j);
                        c->sub.copy.dist += (uInt)b & inflate_mask[j];
                        DUMPBITS(j);
                        Tracevv((stderr,
                            "inflate:         distance %u\n",
                            c->sub.copy.dist));
                        c->mode = COPY;
                        /* FALLTHRU */
                case COPY:
                        /* o: copying bytes in window, waiting for space */
#ifndef __TURBOC__ /* Turbo C bug for following expression */
                        f = (uInt)(q - s->window) < c->sub.copy.dist ?
                            s->end - (c->sub.copy.dist - (q - s->window)) :
                                q - c->sub.copy.dist;
#else
                        f = q - c->sub.copy.dist;
                        if ((uInt)(q - s->window) < c->sub.copy.dist)
                                f = s->end - (c->sub.copy.dist -
                                    (uInt)(q - s->window));
#endif
                        while (c->len)
                        {
                                NEEDOUT;
                                OUTBYTE(*f++);
                                if (f == s->end)
                                        f = s->window;
                                c->len--;
                        }
                        c->mode = START;
                        break;
                case LIT:       /* o: got literal, waiting for output space */
                        NEEDOUT;
                        OUTBYTE(c->sub.lit);
                        c->mode = START;
                        break;
                case WASH:      /* o: got eob, possibly more output */
                        if (k > 7) {    /* return unused byte, if any */
                                Assert(k < 16,
                                    "inflate_codes grabbed too many bytes");
                                k -= 8;
                                n++;
                                p--;    /* can always return one */
                        }
                        FLUSH;
                        if (s->read != s->write)
                                LEAVE
                        c->mode = END;
                        /* FALLTHRU */
                case END:
                        r = Z_STREAM_END;
                        LEAVE
                case BADCODE:   /* x: got error */
                        r = Z_DATA_ERROR;
                        LEAVE
                default:
                        r = Z_STREAM_ERROR;
                        LEAVE
                }
        /* NOTREACHED */
        /* otherwise lint complains */
}


void
inflate_codes_free(c, z)
inflate_codes_statef *c;
z_streamp z;
{
        ZFREE(z, c);
        Tracev((stderr, "inflate:       codes free\n"));
}
/* --- infcodes.c */

/* +++ infutil.c */
/*
 * inflate_util.c -- data and routines common to blocks and codes
 * Copyright (C) 1995-1998 Mark Adler
 * For conditions of distribution and use, see copyright notice in zlib.h
 */

/* #include "zutil.h" */
/* #include "infblock.h" */
/* #include "inftrees.h" */
/* #include "infcodes.h" */
/* #include "infutil.h" */

#ifndef NO_DUMMY_DECL
struct inflate_codes_state {int dummy; };       /* for buggy compilers */
#endif

/* And'ing with mask[n] masks the lower n bits */
uInt inflate_mask[17] = {
        0x0000,
        0x0001, 0x0003, 0x0007, 0x000f, 0x001f, 0x003f, 0x007f, 0x00ff,
        0x01ff, 0x03ff, 0x07ff, 0x0fff, 0x1fff, 0x3fff, 0x7fff, 0xffff
};


/* copy as much as possible from the sliding window to the output area */
int
inflate_flush(s, z, r)
inflate_blocks_statef *s;
z_streamp z;
int r;
{
        uInt n;
        Bytef *p;
        Bytef *q;

        /* local copies of source and destination pointers */
        p = z->next_out;
        q = s->read;

        /* compute number of bytes to copy as far as end of window */
        n = (uInt)((q <= s->write ? s->write : s->end) - q);
        if (n > z->avail_out) n = z->avail_out;
        if (n && r == Z_BUF_ERROR) r = Z_OK;

        /* update counters */
        z->avail_out -= n;
        z->total_out += n;

        /* update check information */
        if (s->checkfn != Z_NULL)
                z->adler = s->check = (*s->checkfn)(s->check, q, n);

        /* copy as far as end of window */
        if (p != Z_NULL) {      /* PPP */
                zmemcpy(p, q, n);
                p += n;
        }       /* PPP */
        q += n;

        /* see if more to copy at beginning of window */
        if (q == s->end)
        {
                /* wrap pointers */
                q = s->window;
                if (s->write == s->end)
                        s->write = s->window;

                /* compute bytes to copy */
                n = (uInt)(s->write - q);
                if (n > z->avail_out) n = z->avail_out;
                if (n && r == Z_BUF_ERROR) r = Z_OK;

                /* update counters */
                z->avail_out -= n;
                z->total_out += n;

                /* update check information */
                if (s->checkfn != Z_NULL)
                        z->adler = s->check = (*s->checkfn)(s->check, q, n);

                /* copy */
                if (p != Z_NULL) {      /* PPP */
                        zmemcpy(p, q, n);
                        p += n;
                }       /* PPP */
                q += n;
        }

        /* update pointers */
        z->next_out = p;
        s->read = q;

        /* done */
        return (r);
}
/* --- infutil.c */

/* +++ inffast.c */
/*
 * inffast.c -- process literals and length/distance pairs fast
 * Copyright (C) 1995-1998 Mark Adler
 * For conditions of distribution and use, see copyright notice in zlib.h
 */

/* #include "zutil.h" */
/* #include "inftrees.h" */
/* #include "infblock.h" */
/* #include "infcodes.h" */
/* #include "infutil.h" */
/* #include "inffast.h" */

#ifndef NO_DUMMY_DECL
struct inflate_codes_state {int dummy; };       /* for buggy compilers */
#endif

/* simplify the use of the inflate_huft type with some defines */
#define exop word.what.Exop
#define bits word.what.Bits

/* macros for bit input with no checking and for returning unused bytes */
#define GRABBITS(j) { while (k < (j)) {b |= ((uLong)NEXTBYTE)<<k; k += 8; }}
#define UNGRAB {c = z->avail_in-n; c = (k>>3) < c?k>>3:c; n += c; p -= c; \
        k -= c<<3; }

/*
 * Called with number of bytes left to write in window at least 258
 * (the maximum string length) and number of input bytes available at
 * least ten.  The ten bytes are six bytes for the longest length/
 * distance pair plus four bytes for overloading the bit buffer.
 */

int
inflate_fast(bl, bd, tl, td, s, z)
uInt bl, bd;
const inflate_huft *tl;
const inflate_huft *td; /* need separate declaration for Borland C++ */
inflate_blocks_statef *s;
z_streamp z;
{
        const inflate_huft *t;  /* temporary pointer */
        uInt e; /* extra bits or operation */
        uLong b;        /* bit buffer */
        uInt k; /* bits in bit buffer */
        Bytef *p;       /* input data pointer */
        uInt n; /* bytes available there */
        Bytef *q;       /* output window write pointer */
        uInt m; /* bytes to end of window or read pointer */
        uInt ml;        /* mask for literal/length tree */
        uInt md;        /* mask for distance tree */
        uInt c; /* bytes to copy */
        uInt d; /* distance back to copy from */
        Bytef *r;       /* copy source pointer */

        /* load input, output, bit values */
        LOAD;

        /* initialize masks */
        ml = inflate_mask[bl];
        md = inflate_mask[bd];

        /* do until not enough input or output space for fast loop */
        do {    /* assume called with m >= 258 && n >= 10 */
                /* get literal/length code */
                /* max bits for literal/length code */
                GRABBITS(20);
                if ((e = (t = tl + ((uInt)b & ml))->exop) == 0) {
                        DUMPBITS(t->bits);
                        Tracevv((stderr, t->base >= 0x20 && t->base < 0x7f ?
                            "inflate:         * literal '%c'\n" :
                            "inflate:         * literal 0x%02x\n", t->base));
                        *q++ = (Byte)t->base;
                        m--;
                        continue;
                }
                do {
                        DUMPBITS(t->bits);
                        if (e & 16) {
                                /* get extra bits for length */
                                e &= 15;
                                c = t->base + ((uInt)b & inflate_mask[e]);
                                DUMPBITS(e);
                                Tracevv((stderr,
                                    "inflate:         * length %u\n", c));

                                /* decode distance base of block to copy */
                                GRABBITS(15);   /* max bits for distance code */
                                e = (t = td + ((uInt)b & md))->exop;
                                do {
                                        DUMPBITS(t->bits);
                                        if (e & 16) {
                                                /*
                                                 * get extra bits to
                                                 * add to distance
                                                 * base
                                                 */
                                                e &= 15;
                                                /* get extra bits (up to 13) */
                                                GRABBITS(e);
                                                d = t->base + ((uInt)b &
                                                    inflate_mask[e]);
                                                DUMPBITS(e);
                                                Tracevv((stderr,
                                                    "inflate:         * "
                                                    "distance %u\n", d));

                                                /* do the copy */
                                                m -= c;
                                                /* offset before dest */
                                                if ((uInt)(q - s->window) >= d)
                                                        /*  just copy */
                                                {
                                                        r = q - d;
                                                        /*
                                                         * minimum
                                                         * count is
                                                         * three, so
                                                         * unroll loop
                                                         * a little
                                                         */
                                                        *q++ = *r++;  c--;
                                                        *q++ = *r++;  c--;
                                                }
                                        /* else offset after destination */
                                                else {
        /* bytes from offset to end */
                                                        e = d - (uInt)(q -
                                                            s->window);
        /* pointer to offset */
                                                        r = s->end - e;
                                                        /* if source crosses */
                                                        if (c > e) {
        /* copy to end of window */
                                                                c -= e;
                                                                do {
                                                                        *q++ =
                                                                            *r
                                                                            ++;
                                                                } while (--e);
        /* copy rest from start of window */
                                                                r = s->window;
                                                        }
                                                }
                                                /* copy all or what's left */
                                                do {
                                                        *q++ = *r++;
                                                } while (--c);
                                                break;
                                        } else if ((e & 64) == 0) {
                                                t += t->base;
                                                e = (t += ((uInt)b &
                                                    inflate_mask[e]))->exop;
                                        } else {
                                                z->msg =
                                                    "invalid distance code";
                                                UNGRAB;
                                                UPDATE;
                                                return (Z_DATA_ERROR);
                                        }
                                        /* CONSTCOND */
                                } while (1);
                                break;
                        }
                        if ((e & 64) == 0)
                        {
                                t += t->base;
                                if ((e = (t += ((uInt)b &
                                    inflate_mask[e]))->exop) == 0)
                                {
                                        DUMPBITS(t->bits);
                                        Tracevv((stderr, t->base >= 0x20 &&
                                            t->base < 0x7f ?
                                            "inflate:         * literal '%c'\n"
                                            :
                                            "inflate:         * literal "
                                            "0x%02x\n", t->base));
                                        *q++ = (Byte)t->base;
                                        m--;
                                        break;
                                }
                        } else if (e & 32) {
                                Tracevv((stderr,
                                    "inflate:         * end of block\n"));
                                UNGRAB;
                                UPDATE;
                                return (Z_STREAM_END);
                        } else {
                                z->msg = "invalid literal/length code";
                                UNGRAB;
                                UPDATE;
                                return (Z_DATA_ERROR);
                        }
                        /* CONSTCOND */
                } while (1);
        } while (m >= 258 && n >= 10);

        /* not enough input or output--restore pointers and return */
        UNGRAB;
        UPDATE;
        return (Z_OK);
}
/* --- inffast.c */

/* +++ zutil.c */
/*
 * zutil.c -- target dependent utility functions for the compression library
 * Copyright (C) 1995-1998 Jean-loup Gailly.
 * For conditions of distribution and use, see copyright notice in zlib.h
 */

/* From: zutil.c,v 1.17 1996/07/24 13:41:12 me Exp $ */

#ifdef DEBUG_ZLIB
#include <stdio.h>
#endif

/* #include "zutil.h" */

#ifndef NO_DUMMY_DECL
struct internal_state   {int dummy; };  /* for buggy compilers */
#endif

#ifndef STDC
extern void exit OF((int));
#endif

static const char *z_errmsg[10] = {
"need dictionary",      /* Z_NEED_DICT          2 */
"stream end",           /* Z_STREAM_END         1 */
"",                     /* Z_OK                 0 */
"file error",           /* Z_ERRNO              (-1) */
"stream error",         /* Z_STREAM_ERROR       (-2) */
"data error",           /* Z_DATA_ERROR         (-3) */
"insufficient memory",  /* Z_MEM_ERROR          (-4) */
"buffer error",         /* Z_BUF_ERROR          (-5) */
"incompatible version", /* Z_VERSION_ERROR      (-6) */
""};


const char *
zlibVersion()
{
        return (ZLIB_VERSION);
}

#ifdef DEBUG_ZLIB
void
z_error(m)
    char *m;
{
        fprintf(stderr, "%s\n", m);
        exit(1);
}
#endif

#ifndef HAVE_MEMCPY

void
zmemcpy(dest, source, len)
    Bytef* dest;
    const Bytef* source;
    uInt  len;
{
        if (len == 0)
                return;
        do {
                *dest++ = *source++;    /* ??? to be unrolled */
        } while (--len != 0);
}

int
zmemcmp(s1, s2, len)
const Bytef* s1;
const Bytef* s2;
uInt  len;
{
        uInt j;

        for (j = 0; j < len; j++) {
                if (s1[j] != s2[j])
                        return (2*(s1[j] > s2[j])-1);
        }
        return (0);
}

void
zmemzero(dest, len)
    Bytef* dest;
    uInt  len;
{
        if (len == 0)
                return;
        do {
                *dest++ = 0;    /* ??? to be unrolled */
        } while (--len != 0);
}
#endif

#ifdef __TURBOC__
#if (defined(__BORLANDC__) || !defined(SMALL_MEDIUM)) && !defined(__32BIT__)
/*
 * Small and medium model in Turbo C are for now limited to near
 * allocation with reduced MAX_WBITS and MAX_MEM_LEVEL
 */
#define MY_ZCALLOC

/*
 * Turbo C malloc() does not allow dynamic allocation of 64K bytes and
 * farmalloc(64K) returns a pointer with an offset of 8, so we must
 * fix the pointer. Warning: the pointer must be put back to its
 * original form in order to free it, use zcfree().
 */

#define MAX_PTR 10
/* 10*64K = 640K */

local int next_ptr = 0;

typedef struct ptr_table_s {
        voidpf org_ptr;
        voidpf new_ptr;
} ptr_table;

local ptr_table table[MAX_PTR];
/*
 * This table is used to remember the original form of pointers to
 * large buffers (64K). Such pointers are normalized with a zero
 * offset.  Since MSDOS is not a preemptive multitasking OS, this
 * table is not protected from concurrent access. This hack doesn't
 * work anyway on a protected system like OS/2. Use Microsoft C
 * instead.
 */

voidpf
zcalloc(voidpf opaque, unsigned items, unsigned size)
{
        voidpf buf = opaque;    /* just to make some compilers happy */
        ulg bsize = (ulg)items*size;

        /*
         * If we allocate less than 65520 bytes, we assume that
         * farmalloc will return a usable pointer which doesn't have
         * to be normalized.
         */
        if (bsize < 65520L) {
                buf = farmalloc(bsize);
                if (*(ush *)&buf != 0)
                        return (buf);
        } else {
                buf = farmalloc(bsize + 16L);
        }
        if (buf == NULL || next_ptr >= MAX_PTR)
                return (NULL);
        table[next_ptr].org_ptr = buf;

        /* Normalize the pointer to seg:0 */
        *((ush *)&buf+1) += ((ush)((uch *)buf-0) + 15) >> 4;
        *(ush *)&buf = 0;
        table[next_ptr++].new_ptr = buf;
        return (buf);
}

void
zcfree(voidpf opaque, voidpf ptr)
{
        int n;
        if (*(ush*)&ptr != 0) { /* object < 64K */
                farfree(ptr);
                return;
        }
        /* Find the original pointer */
        for (n = 0; n < next_ptr; n++) {
                if (ptr != table[n].new_ptr)
                        continue;

                farfree(table[n].org_ptr);
                while (++n < next_ptr) {
                        table[n-1] = table[n];
                }
                next_ptr--;
                return;
        }
        ptr = opaque;   /* just to make some compilers happy */
        Assert(0, "zcfree: ptr not found");
}
#endif
#endif /* __TURBOC__ */


#if defined(M_I86) && !defined(__32BIT__)
/* Microsoft C in 16-bit mode */

#define MY_ZCALLOC

#if (!defined(_MSC_VER) || (_MSC_VER <= 600))
#define _halloc  halloc
#define _hfree   hfree
#endif

voidpf
zcalloc(voidpf opaque, unsigned items, unsigned size)
{
        if (opaque) opaque = 0; /* to make compiler happy */
        return (_halloc((long)items, size));
}

void
zcfree(voidpf opaque, voidpf ptr)
{
        if (opaque) opaque = 0; /* to make compiler happy */
        _hfree(ptr);
}

#endif /* MSC */


#ifndef MY_ZCALLOC /* Any system without a special alloc function */

#ifndef STDC
extern voidp  calloc OF((uInt items, uInt size));
extern void   free   OF((voidpf ptr));
#endif

voidpf
zcalloc(opaque, items, size)
    voidpf opaque;
    unsigned items;
    unsigned size;
{
        if (opaque) items += size - size;       /* make compiler happy */
        return ((voidpf)calloc(items, size));
}

/*ARGSUSED*/
void
zcfree(opaque, ptr)
    voidpf opaque;
    voidpf ptr;
{
        free(ptr);
}

#endif /* MY_ZCALLOC */
/* --- zutil.c */

/* +++ adler32.c */
/*
 * adler32.c -- compute the Adler-32 checksum of a data stream
 * Copyright (C) 1995-1998 Mark Adler
 * For conditions of distribution and use, see copyright notice in zlib.h
 */

/* From: adler32.c,v 1.10 1996/05/22 11:52:18 me Exp $ */

/* #include "zlib.h" */

#define BASE 65521L /* largest prime smaller than 65536 */
#define NMAX 5552
/* NMAX is the largest n such that 255n(n+1)/2 + (n+1)(BASE-1) <= 2^32-1 */

#define DO1(buf, i)  {s1 += buf[i]; s2 += s1; }
#define DO2(buf, i)  DO1(buf, i); DO1(buf, i+1);
#define DO4(buf, i)  DO2(buf, i); DO2(buf, i+2);
#define DO8(buf, i)  DO4(buf, i); DO4(buf, i+4);
#define DO16(buf)   DO8(buf, 0); DO8(buf, 8);

/* ========================================================================= */
uLong
adler32(adler, buf, len)
    uLong adler;
    const Bytef *buf;
    uInt len;
{
        unsigned long s1 = adler & 0xffff;
        unsigned long s2 = (adler >> 16) & 0xffff;
        int k;

        if (buf == Z_NULL)
                return (1L);

        while (len > 0) {
                k = len < NMAX ? len : NMAX;
                len -= k;
                while (k >= 16) {
                        DO16(buf);
                        buf += 16;
                        k -= 16;
                }
                if (k != 0) do {
                        s1 += *buf++;
                        s2 += s1;
                } while (--k);
                s1 %= BASE;
                s2 %= BASE;
        }
        return ((s2 << 16) | s1);
}
/* --- adler32.c */