Changeset 2182


Ignore:
Timestamp:
Apr 5, 2011, 5:13:03 PM (4 years ago)
Author:
tooch
Message:

Infrastructure - Replace the wrapper's gzip compression library with zlib.
Zlib is under active development, and is unencumbered by GPL or
patents, hence a better choice for implementations allergic to those issues.
The zlib files have not been modified, primarily to ease future porting.
The conversion from a zlib-format deflated buffer to a gzip-deflated buffer
is done in the wrapper.

Files:
10 added
5 deleted
10 edited

Legend:

Unmodified
Added
Removed
  • cpu/arm/Linux/Makefile

    r1998 r2182  
    1010ZIPDIR = ${BP}/${ZIPTAIL}
    1111
    12 ZIPOBJS = zipmem.o deflate.o trees.o bits.o util.o inflate.o
     12ZIPOBJS = adler32.o compress.o crc32.o deflate.o inflate.o trees.o zutil.o
    1313
    1414OBJS = wrapper.o logger.o ${ZIPOBJS}
  • cpu/mips/Linux/makefile

    r1201 r2182  
    1010ZIPDIR = ${WRDIR}/zip
    1111
    12 ZIPOBJS = zipmem.o deflate.o trees.o bits.o util.o inflate.o
     12ZIPOBJS = adler32.o compress.o crc32.o deflate.o inflate.o trees.o zutil.o
    1313
    1414OBJS = wrapper.o logger.o ${ZIPOBJS}
  • cpu/ppc/Linux/Makefile

    r761 r2182  
    1313ZIPDIR = ${WRDIR}/zip
    1414
    15 ZIPOBJS = zipmem.o deflate.o trees.o bits.o util.o inflate.o
     15ZIPOBJS = adler32.o compress.o crc32.o deflate.o inflate.o trees.o zutil.o
    1616
    1717OBJS = wrapper.o logger.o ${ZIPOBJS}
  • cpu/x86/Darwin/Makefile

    r2129 r2182  
    2626ZIPDIR = ${BP}/${ZIPTAIL}
    2727
    28 ZIPOBJS = zipmem.o deflate.o trees.o bits.o util.o inflate.o
    29 INFLATEBIN = ../../build/inflate.bin
     28ZIPOBJS = adler32.o compress.o crc32.o deflate.o inflate.o trees.o zutil.o
     29INFLATEBIN = ../build/inflate.bin
    3030
    3131# Compile with -O0 because with GCC4, higher optimization levels cause the
  • cpu/x86/Linux/Makefile

    r2129 r2182  
    2828ZIPDIR = ${BP}/${ZIPTAIL}
    2929
    30 ZIPOBJS = zipmem.o deflate.o trees.o bits.o util.o inflate.o
     30ZIPOBJS = adler32.o compress.o crc32.o deflate.o inflate.o trees.o zutil.o
    3131
    3232endif
  • cpu/x86/Linux/Makefile.ppcforth

    r761 r2182  
    1313SIMDIR = ${BP}/cpu/ppc/ppcsim
    1414
    15 ZIPOBJS = zipmem.o deflate.o trees.o bits.o util.o inflate.o
     15ZIPOBJS = adler32.o compress.o crc32.o deflate.o inflate.o trees.o zutil.o
    1616
    1717OBJS = wrapsim.o ppcsim.o logger.o ${ZIPOBJS}
  • forth/wrapper/wrapper.c

    r2126 r2182  
    6565/* zlib externs */
    6666extern int inflate();
    67 extern int zip_memory();
     67extern int compress();
     68extern long crc32();
    6869
    6970#ifdef __linux__
     
    23632364     long inadr;
    23642365{
    2365      return((long)zip_memory((void *)inadr, (int)inlen,
    2366                              (void *)outadr, (int)outlen));
     2366     /*
     2367      * Zlib compress() returns a buffer in zlib format (see RFC1950).
     2368      * The buffer is formatted as
     2369      *   Header[2]  Compressed_data[outlen-6] Adler32[4]
     2370      * Our inflate() routine expects gzip format (RFC1952):
     2371      *   Header[10] Compressed_data[outlen-6] CRC32[4] inlen[4]
     2372      * The conversion is simple so let's just do it here.
     2373      * Note the CRC32 and inlen fields are little-endian by spec.
     2374      * Note the overlapping copy requires memmove() or equivalent.
     2375      * Is the outbuf big enough to handle pathological cases?
     2376      */
     2377     unsigned char *outbuf = (unsigned char *)outadr;  /* type convenience */
     2378     unsigned long datalen;
     2379     unsigned char gzip_hdr[] = {
     2380        0x1f, 0x8b, 0x08, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x03
     2381     };
     2382     unsigned long crc = crc32(0, inadr, inlen);
     2383     int err = compress(outbuf, &outlen, (void *)inadr, inlen);
     2384     if (err) return 0;
     2385
     2386     datalen = outlen - 6;
     2387     memmove(&outbuf[10], &outbuf[2], datalen);
     2388     memmove(&outbuf[0], gzip_hdr, 10);
     2389#ifndef HOST_LITTLE_ENDIAN
     2390     crc = lbflip(crc);
     2391     inlen = lbflip(inlen);
     2392#endif
     2393     *(unsigned long *)&outbuf[10 + datalen + 0] = crc;
     2394     *(unsigned long *)&outbuf[10 + datalen + 4] = inlen;
     2395     return (10 + datalen + 8);
    23672396}
    23682397
  • forth/wrapper/zip/deflate.c

    r1 r2182  
    11/* deflate.c -- compress data using the deflation algorithm
    2  * Copyright (C) 1992-1993 Jean-loup Gailly
    3  * This is free software; you can redistribute it and/or modify it under the
    4  * terms of the GNU General Public License, see the file COPYING.
     2 * Copyright (C) 1995-2010 Jean-loup Gailly and Mark Adler
     3 * For conditions of distribution and use, see copyright notice in zlib.h
    54 */
    65
    76/*
    8  *  PURPOSE
    9  *
    10  *      Identify new text as repetitions of old text within a fixed-
    11  *      length sliding window trailing behind the new text.
    12  *
    13  *  DISCUSSION
     7 *  ALGORITHM
    148 *
    159 *      The "deflation" process depends on being able to identify portions
     
    3933 *      The idea of lazy evaluation of matches is due to Jan-Mark Wams, and
    4034 *      I found it in 'freeze' written by Leonid Broukhis.
    41  *      Thanks to many info-zippers for bug reports and testing.
     35 *      Thanks to many people for bug reports and testing.
    4236 *
    4337 *  REFERENCES
    4438 *
    45  *      APPNOTE.TXT documentation file in PKZIP 1.93a distribution.
     39 *      Deutsch, L.P.,"DEFLATE Compressed Data Format Specification".
     40 *      Available in http://www.ietf.org/rfc/rfc1951.txt
    4641 *
    4742 *      A description of the Rabin and Karp algorithm is given in the book
     
    5146 *         Data Compression with Finite Windows, Comm.ACM, 32,4 (1989) 490-595
    5247 *
    53  *  INTERFACE
    54  *
    55  *      void lm_init (int pack_level, ush *flags)
    56  *          Initialize the "longest match" routines for a new file
    57  *
    58  *      ulg deflate (void)
    59  *          Processes a new input file and return its compressed length. Sets
    60  *          the compressed length, crc, deflate flags and internal file
    61  *          attributes.
    62  */
    63 
    64 #include <stdio.h>
    65 
    66 #include "tailor.h"
    67 #include "gzip.h"
    68 #ifdef FWnotdef
    69 #include "lzw.h" /* just for consistency checking */
    70 #endif
    71 
    72 #ifdef RCSID
    73 static char rcsid[] = "$Id: deflate.c,v 1.1 1997/01/08 08:30:15 wmb Exp $";
    74 #endif
     48 */
     49
     50/* @(#) $Id$ */
     51
     52#include "deflate.h"
     53
     54const char deflate_copyright[] =
     55   " deflate 1.2.5 Copyright 1995-2010 Jean-loup Gailly and Mark Adler ";
     56/*
     57  If you use the zlib library in a product, an acknowledgment is welcome
     58  in the documentation of your product. If for some reason you cannot
     59  include such an acknowledgment, I would appreciate that you keep this
     60  copyright string in the executable of your product.
     61 */
    7562
    7663/* ===========================================================================
    77  * Configuration parameters
    78  */
    79 
    80 /* Compile with MEDIUM_MEM to reduce the memory requirements or
    81  * with SMALL_MEM to use as little memory as possible. Use BIG_MEM if the
    82  * entire input file can be held in memory (not possible on 16 bit systems).
    83  * Warning: defining these symbols affects HASH_BITS (see below) and thus
    84  * affects the compression ratio. The compressed output
    85  * is still correct, and might even be smaller in some cases.
    86  */
    87 
    88 #ifdef SMALL_MEM
    89 #   define HASH_BITS  13  /* Number of bits used to hash strings */
    90 #endif
    91 #ifdef MEDIUM_MEM
    92 #   define HASH_BITS  14
    93 #endif
    94 #ifndef HASH_BITS
    95 #   define HASH_BITS  15
    96    /* For portability to 16 bit machines, do not use values above 15. */
    97 #endif
    98 
    99 #ifdef FWnotdef
    100 /* To save space (see unlzw.c), we overlay prev+head with tab_prefix and
    101  * window with tab_suffix. Check that we can do this:
    102  */
    103 #if (WSIZE<<1) > (1<<BITS)
    104    error: cannot overlay window with tab_suffix and prev with tab_prefix0
    105 #endif
    106 #if HASH_BITS > BITS-1
    107    error: cannot overlay head with tab_prefix1
    108 #endif
    109 #endif
    110 
    111 #define HASH_SIZE (unsigned)(1<<HASH_BITS)
    112 #define HASH_MASK (HASH_SIZE-1)
    113 #define WMASK     (WSIZE-1)
    114 /* HASH_SIZE and WSIZE must be powers of two */
     64 *  Function prototypes.
     65 */
     66typedef enum {
     67    need_more,      /* block not completed, need more input or more output */
     68    block_done,     /* block flush performed */
     69    finish_started, /* finish started, need only more output at next deflate */
     70    finish_done     /* finish done, accept no more input or output */
     71} block_state;
     72
     73typedef block_state (*compress_func) OF((deflate_state *s, int flush));
     74/* Compression function. Returns the block state after the call. */
     75
     76local void fill_window    OF((deflate_state *s));
     77local block_state deflate_stored OF((deflate_state *s, int flush));
     78local block_state deflate_fast   OF((deflate_state *s, int flush));
     79#ifndef FASTEST
     80local block_state deflate_slow   OF((deflate_state *s, int flush));
     81#endif
     82local block_state deflate_rle    OF((deflate_state *s, int flush));
     83local block_state deflate_huff   OF((deflate_state *s, int flush));
     84local void lm_init        OF((deflate_state *s));
     85local void putShortMSB    OF((deflate_state *s, uInt b));
     86local void flush_pending  OF((z_streamp strm));
     87local int read_buf        OF((z_streamp strm, Bytef *buf, unsigned size));
     88#ifdef ASMV
     89      void match_init OF((void)); /* asm code initialization */
     90      uInt longest_match  OF((deflate_state *s, IPos cur_match));
     91#else
     92local uInt longest_match  OF((deflate_state *s, IPos cur_match));
     93#endif
     94
     95#ifdef DEBUG
     96local  void check_match OF((deflate_state *s, IPos start, IPos match,
     97                            int length));
     98#endif
     99
     100/* ===========================================================================
     101 * Local data
     102 */
    115103
    116104#define NIL 0
    117105/* Tail of hash chains */
    118106
    119 #define FAST 4
    120 #define SLOW 2
    121 /* speed options for the general purpose bit flag */
    122 
    123107#ifndef TOO_FAR
    124108#  define TOO_FAR 4096
    125109#endif
    126110/* Matches of length 3 are discarded if their distance exceeds TOO_FAR */
    127 
    128 /* ===========================================================================
    129  * Local data used by the "longest match" routines.
    130  */
    131 
    132 typedef ush Pos;
    133 typedef unsigned IPos;
    134 /* A Pos is an index in the character window. We use short instead of int to
    135  * save space in the various tables. IPos is used only for parameter passing.
    136  */
    137 
    138 /* DECLARE(uch, window, 2L*WSIZE); */
    139 /* Sliding window. Input bytes are read into the second half of the window,
    140  * and move to the first half later to keep a dictionary of at least WSIZE
    141  * bytes. With this organization, matches are limited to a distance of
    142  * WSIZE-MAX_MATCH bytes, but this ensures that IO is always
    143  * performed with a length multiple of the block size. Also, it limits
    144  * the window size to 64K, which is quite useful on MSDOS.
    145  * To do: limit the window size to WSIZE+BSZ if SMALL_MEM (the code would
    146  * be less efficient).
    147  */
    148 
    149 /* DECLARE(Pos, prev, WSIZE); */
    150 /* Link to older string with same hash index. To limit the size of this
    151  * array to 64K, this link is maintained only for the last 32K strings.
    152  * An index in this array is thus a window index modulo 32K.
    153  */
    154 
    155 /* DECLARE(Pos, head, 1<<HASH_BITS); */
    156 /* Heads of the hash chains or NIL. */
    157 
    158 ulg window_size = (ulg)2*WSIZE;
    159 /* window size, 2*WSIZE except for MMAP or BIG_MEM, where it is the
    160  * input file length plus MIN_LOOKAHEAD.
    161  */
    162 
    163 long block_start;
    164 /* window position at the beginning of the current output block. Gets
    165  * negative when the window is moved backwards.
    166  */
    167 
    168 local unsigned ins_h;  /* hash index of string to be inserted */
    169 
    170 #define H_SHIFT  ((HASH_BITS+MIN_MATCH-1)/MIN_MATCH)
    171 /* Number of bits by which ins_h and del_h must be shifted at each
    172  * input step. It must be such that after MIN_MATCH steps, the oldest
    173  * byte no longer takes part in the hash key, that is:
    174  *   H_SHIFT * MIN_MATCH >= HASH_BITS
    175  */
    176 
    177 unsigned int near prev_length;
    178 /* Length of the best match at previous step. Matches not greater than this
    179  * are discarded. This is used in the lazy match evaluation.
    180  */
    181 
    182       unsigned near strstart;      /* start of string to insert */
    183       unsigned near match_start;   /* start of matching string */
    184 local int           eofile;        /* flag set at end of input file */
    185 local unsigned      lookahead;     /* number of valid bytes ahead in window */
    186 
    187 unsigned near max_chain_length;
    188 /* To speed up deflation, hash chains are never searched beyond this length.
    189  * A higher limit improves compression ratio but degrades the speed.
    190  */
    191 
    192 local unsigned int max_lazy_match;
    193 /* Attempt to find a better match only when the current match is strictly
    194  * smaller than this value. This mechanism is used only for compression
    195  * levels >= 4.
    196  */
    197 #define max_insert_length  max_lazy_match
    198 /* Insert new strings in the hash table only if the match length
    199  * is not greater than this length. This saves time but degrades compression.
    200  * max_insert_length is used only for compression levels <= 3.
    201  */
    202 
    203 local int compr_level;
    204 /* compression level (1..9) */
    205 
    206 unsigned near good_match;
    207 /* Use a faster search when the previous match is longer than this */
    208 
    209111
    210112/* Values for max_lazy_match, good_match and max_chain_length, depending on
     
    213115 * found for specific files.
    214116 */
    215 
    216 typedef struct config {
     117typedef struct config_s {
    217118   ush good_length; /* reduce lazy search above this match length */
    218119   ush max_lazy;    /* do not perform lazy search above this match length */
    219120   ush nice_length; /* quit search above this match length */
    220121   ush max_chain;
     122   compress_func func;
    221123} config;
    222124
    223 #ifdef  FULL_SEARCH
    224 # define nice_match MAX_MATCH
     125#ifdef FASTEST
     126local const config configuration_table[2] = {
     127/*      good lazy nice chain */
     128/* 0 */ {0,    0,  0,    0, deflate_stored},  /* store only */
     129/* 1 */ {4,    4,  8,    4, deflate_fast}}; /* max speed, no lazy matches */
    225130#else
    226   int near nice_match; /* Stop searching when current match exceeds this */
    227 #endif
    228 
    229 local config configuration_table[10] = {
     131local const config configuration_table[10] = {
    230132/*      good lazy nice chain */
    231 /* 0 */ {0,    0,  0,    0},  /* store only */
    232 /* 1 */ {4,    4,  8,    4},  /* maximum speed, no lazy matches */
    233 /* 2 */ {4,    5, 16,    8},
    234 /* 3 */ {4,    6, 32,   32},
    235 
    236 /* 4 */ {4,    4, 16,   16},  /* lazy matches */
    237 /* 5 */ {8,   16, 32,   32},
    238 /* 6 */ {8,   16, 128, 128},
    239 /* 7 */ {8,   32, 128, 256},
    240 /* 8 */ {32, 128, 258, 1024},
    241 /* 9 */ {32, 258, 258, 4096}}; /* maximum compression */
     133/* 0 */ {0,    0,  0,    0, deflate_stored},  /* store only */
     134/* 1 */ {4,    4,  8,    4, deflate_fast}, /* max speed, no lazy matches */
     135/* 2 */ {4,    5, 16,    8, deflate_fast},
     136/* 3 */ {4,    6, 32,   32, deflate_fast},
     137
     138/* 4 */ {4,    4, 16,   16, deflate_slow},  /* lazy matches */
     139/* 5 */ {8,   16, 32,   32, deflate_slow},
     140/* 6 */ {8,   16, 128, 128, deflate_slow},
     141/* 7 */ {8,   32, 128, 256, deflate_slow},
     142/* 8 */ {32, 128, 258, 1024, deflate_slow},
     143/* 9 */ {32, 258, 258, 4096, deflate_slow}}; /* max compression */
     144#endif
    242145
    243146/* Note: the deflate() code requires max_lazy >= MIN_MATCH and max_chain >= 4
     
    249152/* result of memcmp for equal strings */
    250153
    251 /* ===========================================================================
    252  *  Prototypes for local functions.
    253  */
    254 local void fill_window   OF((void));
    255 local ulg deflate_fast   OF((void));
    256 
    257       int  longest_match OF((IPos cur_match));
    258 #ifdef ASMV
    259       void match_init OF((void)); /* asm code initialization */
    260 #endif
    261 
    262 #ifdef DEBUG
    263 local  void check_match OF((IPos start, IPos match, int length));
     154#ifndef NO_DUMMY_DECL
     155struct static_tree_desc_s {int dummy;}; /* for buggy compilers */
    264156#endif
    265157
     
    270162 *    previous key instead of complete recalculation each time.
    271163 */
    272 #define UPDATE_HASH(h,c) (h = (((h)<<H_SHIFT) ^ (c)) & HASH_MASK)
     164#define UPDATE_HASH(s,h,c) (h = (((h)<<s->hash_shift) ^ (c)) & s->hash_mask)
     165
    273166
    274167/* ===========================================================================
    275  * Insert string s in the dictionary and set match_head to the previous head
     168 * Insert string str in the dictionary and set match_head to the previous head
    276169 * of the hash chain (the most recent string with same hash key). Return
    277170 * the previous length of the hash chain.
     171 * If this file is compiled with -DFASTEST, the compression level is forced
     172 * to 1, and no hash chains are maintained.
    278173 * IN  assertion: all calls to to INSERT_STRING are made with consecutive
    279  *    input characters and the first MIN_MATCH bytes of s are valid
     174 *    input characters and the first MIN_MATCH bytes of str are valid
    280175 *    (except for the last MIN_MATCH-1 bytes of the input file).
    281176 */
    282 #define INSERT_STRING(s, match_head) \
    283    (UPDATE_HASH(ins_h, window[(s) + MIN_MATCH-1]), \
    284     prev[(s) & WMASK] = match_head = head[ins_h], \
    285     head[ins_h] = (s))
     177#ifdef FASTEST
     178#define INSERT_STRING(s, str, match_head) \
     179   (UPDATE_HASH(s, s->ins_h, s->window[(str) + (MIN_MATCH-1)]), \
     180    match_head = s->head[s->ins_h], \
     181    s->head[s->ins_h] = (Pos)(str))
     182#else
     183#define INSERT_STRING(s, str, match_head) \
     184   (UPDATE_HASH(s, s->ins_h, s->window[(str) + (MIN_MATCH-1)]), \
     185    match_head = s->prev[(str) & s->w_mask] = s->head[s->ins_h], \
     186    s->head[s->ins_h] = (Pos)(str))
     187#endif
    286188
    287189/* ===========================================================================
    288  * Initialize the "longest match" routines for a new file
    289  */
    290 void lm_init (pack_level, flags)
    291     int pack_level; /* 0: store, 1: best speed, 9: best compression */
    292     ush *flags;     /* general purpose bit flag */
    293 {
    294     register unsigned j;
    295 
    296     if (pack_level < 1 || pack_level > 9) error("bad pack level");
    297     compr_level = pack_level;
    298 
    299     /* Initialize the hash table. */
    300 #if defined(MAXSEG_64K) && HASH_BITS == 15
    301     for (j = 0;  j < HASH_SIZE; j++) head[j] = NIL;
     190 * Initialize the hash table (avoiding 64K overflow for 16 bit systems).
     191 * prev[] will be initialized on the fly.
     192 */
     193#define CLEAR_HASH(s) \
     194    s->head[s->hash_size-1] = NIL; \
     195    zmemzero((Bytef *)s->head, (unsigned)(s->hash_size-1)*sizeof(*s->head));
     196
     197/* ========================================================================= */
     198int ZEXPORT deflateInit_(strm, level, version, stream_size)
     199    z_streamp strm;
     200    int level;
     201    const char *version;
     202    int stream_size;
     203{
     204    return deflateInit2_(strm, level, Z_DEFLATED, MAX_WBITS, DEF_MEM_LEVEL,
     205                         Z_DEFAULT_STRATEGY, version, stream_size);
     206    /* To do: ignore strm->next_in if we use it as window */
     207}
     208
     209/* ========================================================================= */
     210int ZEXPORT deflateInit2_(strm, level, method, windowBits, memLevel, strategy,
     211                  version, stream_size)
     212    z_streamp strm;
     213    int  level;
     214    int  method;
     215    int  windowBits;
     216    int  memLevel;
     217    int  strategy;
     218    const char *version;
     219    int stream_size;
     220{
     221    deflate_state *s;
     222    int wrap = 1;
     223    static const char my_version[] = ZLIB_VERSION;
     224
     225    ushf *overlay;
     226    /* We overlay pending_buf and d_buf+l_buf. This works since the average
     227     * output size for (length,distance) codes is <= 24 bits.
     228     */
     229
     230    if (version == Z_NULL || version[0] != my_version[0] ||
     231        stream_size != sizeof(z_stream)) {
     232        return Z_VERSION_ERROR;
     233    }
     234    if (strm == Z_NULL) return Z_STREAM_ERROR;
     235
     236    strm->msg = Z_NULL;
     237    if (strm->zalloc == (alloc_func)0) {
     238        strm->zalloc = zcalloc;
     239        strm->opaque = (voidpf)0;
     240    }
     241    if (strm->zfree == (free_func)0) strm->zfree = zcfree;
     242
     243#ifdef FASTEST
     244    if (level != 0) level = 1;
    302245#else
    303     memzero((char*)head, HASH_SIZE*sizeof(*head));
    304 #endif
    305     /* prev will be initialized on the fly */
     246    if (level == Z_DEFAULT_COMPRESSION) level = 6;
     247#endif
     248
     249    if (windowBits < 0) { /* suppress zlib wrapper */
     250        wrap = 0;
     251        windowBits = -windowBits;
     252    }
     253#ifdef GZIP
     254    else if (windowBits > 15) {
     255        wrap = 2;       /* write gzip wrapper instead */
     256        windowBits -= 16;
     257    }
     258#endif
     259    if (memLevel < 1 || memLevel > MAX_MEM_LEVEL || method != Z_DEFLATED ||
     260        windowBits < 8 || windowBits > 15 || level < 0 || level > 9 ||
     261        strategy < 0 || strategy > Z_FIXED) {
     262        return Z_STREAM_ERROR;
     263    }
     264    if (windowBits == 8) windowBits = 9;  /* until 256-byte window bug fixed */
     265    s = (deflate_state *) ZALLOC(strm, 1, sizeof(deflate_state));
     266    if (s == Z_NULL) return Z_MEM_ERROR;
     267    strm->state = (struct internal_state FAR *)s;
     268    s->strm = strm;
     269
     270    s->wrap = wrap;
     271    s->gzhead = Z_NULL;
     272    s->w_bits = windowBits;
     273    s->w_size = 1 << s->w_bits;
     274    s->w_mask = s->w_size - 1;
     275
     276    s->hash_bits = memLevel + 7;
     277    s->hash_size = 1 << s->hash_bits;
     278    s->hash_mask = s->hash_size - 1;
     279    s->hash_shift =  ((s->hash_bits+MIN_MATCH-1)/MIN_MATCH);
     280
     281    s->window = (Bytef *) ZALLOC(strm, s->w_size, 2*sizeof(Byte));
     282    s->prev   = (Posf *)  ZALLOC(strm, s->w_size, sizeof(Pos));
     283    s->head   = (Posf *)  ZALLOC(strm, s->hash_size, sizeof(Pos));
     284
     285    s->high_water = 0;      /* nothing written to s->window yet */
     286
     287    s->lit_bufsize = 1 << (memLevel + 6); /* 16K elements by default */
     288
     289    overlay = (ushf *) ZALLOC(strm, s->lit_bufsize, sizeof(ush)+2);
     290    s->pending_buf = (uchf *) overlay;
     291    s->pending_buf_size = (ulg)s->lit_bufsize * (sizeof(ush)+2L);
     292
     293    if (s->window == Z_NULL || s->prev == Z_NULL || s->head == Z_NULL ||
     294        s->pending_buf == Z_NULL) {
     295        s->status = FINISH_STATE;
     296        strm->msg = (char*)ERR_MSG(Z_MEM_ERROR);
     297        deflateEnd (strm);
     298        return Z_MEM_ERROR;
     299    }
     300    s->d_buf = overlay + s->lit_bufsize/sizeof(ush);
     301    s->l_buf = s->pending_buf + (1+sizeof(ush))*s->lit_bufsize;
     302
     303    s->level = level;
     304    s->strategy = strategy;
     305    s->method = (Byte)method;
     306
     307    return deflateReset(strm);
     308}
     309
     310/* ========================================================================= */
     311int ZEXPORT deflateSetDictionary (strm, dictionary, dictLength)
     312    z_streamp strm;
     313    const Bytef *dictionary;
     314    uInt  dictLength;
     315{
     316    deflate_state *s;
     317    uInt length = dictLength;
     318    uInt n;
     319    IPos hash_head = 0;
     320
     321    if (strm == Z_NULL || strm->state == Z_NULL || dictionary == Z_NULL ||
     322        strm->state->wrap == 2 ||
     323        (strm->state->wrap == 1 && strm->state->status != INIT_STATE))
     324        return Z_STREAM_ERROR;
     325
     326    s = strm->state;
     327    if (s->wrap)
     328        strm->adler = adler32(strm->adler, dictionary, dictLength);
     329
     330    if (length < MIN_MATCH) return Z_OK;
     331    if (length > s->w_size) {
     332        length = s->w_size;
     333        dictionary += dictLength - length; /* use the tail of the dictionary */
     334    }
     335    zmemcpy(s->window, dictionary, length);
     336    s->strstart = length;
     337    s->block_start = (long)length;
     338
     339    /* Insert all strings in the hash table (except for the last two bytes).
     340     * s->lookahead stays null, so s->ins_h will be recomputed at the next
     341     * call of fill_window.
     342     */
     343    s->ins_h = s->window[0];
     344    UPDATE_HASH(s, s->ins_h, s->window[1]);
     345    for (n = 0; n <= length - MIN_MATCH; n++) {
     346        INSERT_STRING(s, n, hash_head);
     347    }
     348    if (hash_head) hash_head = 0;  /* to make compiler happy */
     349    return Z_OK;
     350}
     351
     352/* ========================================================================= */
     353int ZEXPORT deflateReset (strm)
     354    z_streamp strm;
     355{
     356    deflate_state *s;
     357
     358    if (strm == Z_NULL || strm->state == Z_NULL ||
     359        strm->zalloc == (alloc_func)0 || strm->zfree == (free_func)0) {
     360        return Z_STREAM_ERROR;
     361    }
     362
     363    strm->total_in = strm->total_out = 0;
     364    strm->msg = Z_NULL; /* use zfree if we ever allocate msg dynamically */
     365    strm->data_type = Z_UNKNOWN;
     366
     367    s = (deflate_state *)strm->state;
     368    s->pending = 0;
     369    s->pending_out = s->pending_buf;
     370
     371    if (s->wrap < 0) {
     372        s->wrap = -s->wrap; /* was made negative by deflate(..., Z_FINISH); */
     373    }
     374    s->status = s->wrap ? INIT_STATE : BUSY_STATE;
     375    strm->adler =
     376#ifdef GZIP
     377        s->wrap == 2 ? crc32(0L, Z_NULL, 0) :
     378#endif
     379        adler32(0L, Z_NULL, 0);
     380    s->last_flush = Z_NO_FLUSH;
     381
     382    _tr_init(s);
     383    lm_init(s);
     384
     385    return Z_OK;
     386}
     387
     388/* ========================================================================= */
     389int ZEXPORT deflateSetHeader (strm, head)
     390    z_streamp strm;
     391    gz_headerp head;
     392{
     393    if (strm == Z_NULL || strm->state == Z_NULL) return Z_STREAM_ERROR;
     394    if (strm->state->wrap != 2) return Z_STREAM_ERROR;
     395    strm->state->gzhead = head;
     396    return Z_OK;
     397}
     398
     399/* ========================================================================= */
     400int ZEXPORT deflatePrime (strm, bits, value)
     401    z_streamp strm;
     402    int bits;
     403    int value;
     404{
     405    if (strm == Z_NULL || strm->state == Z_NULL) return Z_STREAM_ERROR;
     406    strm->state->bi_valid = bits;
     407    strm->state->bi_buf = (ush)(value & ((1 << bits) - 1));
     408    return Z_OK;
     409}
     410
     411/* ========================================================================= */
     412int ZEXPORT deflateParams(strm, level, strategy)
     413    z_streamp strm;
     414    int level;
     415    int strategy;
     416{
     417    deflate_state *s;
     418    compress_func func;
     419    int err = Z_OK;
     420
     421    if (strm == Z_NULL || strm->state == Z_NULL) return Z_STREAM_ERROR;
     422    s = strm->state;
     423
     424#ifdef FASTEST
     425    if (level != 0) level = 1;
     426#else
     427    if (level == Z_DEFAULT_COMPRESSION) level = 6;
     428#endif
     429    if (level < 0 || level > 9 || strategy < 0 || strategy > Z_FIXED) {
     430        return Z_STREAM_ERROR;
     431    }
     432    func = configuration_table[s->level].func;
     433
     434    if ((strategy != s->strategy || func != configuration_table[level].func) &&
     435        strm->total_in != 0) {
     436        /* Flush the last buffer: */
     437        err = deflate(strm, Z_BLOCK);
     438    }
     439    if (s->level != level) {
     440        s->level = level;
     441        s->max_lazy_match   = configuration_table[level].max_lazy;
     442        s->good_match       = configuration_table[level].good_length;
     443        s->nice_match       = configuration_table[level].nice_length;
     444        s->max_chain_length = configuration_table[level].max_chain;
     445    }
     446    s->strategy = strategy;
     447    return err;
     448}
     449
     450/* ========================================================================= */
     451int ZEXPORT deflateTune(strm, good_length, max_lazy, nice_length, max_chain)
     452    z_streamp strm;
     453    int good_length;
     454    int max_lazy;
     455    int nice_length;
     456    int max_chain;
     457{
     458    deflate_state *s;
     459
     460    if (strm == Z_NULL || strm->state == Z_NULL) return Z_STREAM_ERROR;
     461    s = strm->state;
     462    s->good_match = good_length;
     463    s->max_lazy_match = max_lazy;
     464    s->nice_match = nice_length;
     465    s->max_chain_length = max_chain;
     466    return Z_OK;
     467}
     468
     469/* =========================================================================
     470 * For the default windowBits of 15 and memLevel of 8, this function returns
     471 * a close to exact, as well as small, upper bound on the compressed size.
     472 * They are coded as constants here for a reason--if the #define's are
     473 * changed, then this function needs to be changed as well.  The return
     474 * value for 15 and 8 only works for those exact settings.
     475 *
     476 * For any setting other than those defaults for windowBits and memLevel,
     477 * the value returned is a conservative worst case for the maximum expansion
     478 * resulting from using fixed blocks instead of stored blocks, which deflate
     479 * can emit on compressed data for some combinations of the parameters.
     480 *
     481 * This function could be more sophisticated to provide closer upper bounds for
     482 * every combination of windowBits and memLevel.  But even the conservative
     483 * upper bound of about 14% expansion does not seem onerous for output buffer
     484 * allocation.
     485 */
     486uLong ZEXPORT deflateBound(strm, sourceLen)
     487    z_streamp strm;
     488    uLong sourceLen;
     489{
     490    deflate_state *s;
     491    uLong complen, wraplen;
     492    Bytef *str;
     493
     494    /* conservative upper bound for compressed data */
     495    complen = sourceLen +
     496              ((sourceLen + 7) >> 3) + ((sourceLen + 63) >> 6) + 5;
     497
     498    /* if can't get parameters, return conservative bound plus zlib wrapper */
     499    if (strm == Z_NULL || strm->state == Z_NULL)
     500        return complen + 6;
     501
     502    /* compute wrapper length */
     503    s = strm->state;
     504    switch (s->wrap) {
     505    case 0:                                 /* raw deflate */
     506        wraplen = 0;
     507        break;
     508    case 1:                                 /* zlib wrapper */
     509        wraplen = 6 + (s->strstart ? 4 : 0);
     510        break;
     511    case 2:                                 /* gzip wrapper */
     512        wraplen = 18;
     513        if (s->gzhead != Z_NULL) {          /* user-supplied gzip header */
     514            if (s->gzhead->extra != Z_NULL)
     515                wraplen += 2 + s->gzhead->extra_len;
     516            str = s->gzhead->name;
     517            if (str != Z_NULL)
     518                do {
     519                    wraplen++;
     520                } while (*str++);
     521            str = s->gzhead->comment;
     522            if (str != Z_NULL)
     523                do {
     524                    wraplen++;
     525                } while (*str++);
     526            if (s->gzhead->hcrc)
     527                wraplen += 2;
     528        }
     529        break;
     530    default:                                /* for compiler happiness */
     531        wraplen = 6;
     532    }
     533
     534    /* if not default parameters, return conservative bound */
     535    if (s->w_bits != 15 || s->hash_bits != 8 + 7)
     536        return complen + wraplen;
     537
     538    /* default settings: return tight bound for that case */
     539    return sourceLen + (sourceLen >> 12) + (sourceLen >> 14) +
     540           (sourceLen >> 25) + 13 - 6 + wraplen;
     541}
     542
     543/* =========================================================================
     544 * Put a short in the pending buffer. The 16-bit value is put in MSB order.
     545 * IN assertion: the stream state is correct and there is enough room in
     546 * pending_buf.
     547 */
     548local void putShortMSB (s, b)
     549    deflate_state *s;
     550    uInt b;
     551{
     552    put_byte(s, (Byte)(b >> 8));
     553    put_byte(s, (Byte)(b & 0xff));
     554}
     555
     556/* =========================================================================
     557 * Flush as much pending output as possible. All deflate() output goes
     558 * through this function so some applications may wish to modify it
     559 * to avoid allocating a large strm->next_out buffer and copying into it.
     560 * (See also read_buf()).
     561 */
     562local void flush_pending(strm)
     563    z_streamp strm;
     564{
     565    unsigned len = strm->state->pending;
     566
     567    if (len > strm->avail_out) len = strm->avail_out;
     568    if (len == 0) return;
     569
     570    zmemcpy(strm->next_out, strm->state->pending_out, len);
     571    strm->next_out  += len;
     572    strm->state->pending_out  += len;
     573    strm->total_out += len;
     574    strm->avail_out  -= len;
     575    strm->state->pending -= len;
     576    if (strm->state->pending == 0) {
     577        strm->state->pending_out = strm->state->pending_buf;
     578    }
     579}
     580
     581/* ========================================================================= */
     582int ZEXPORT deflate (strm, flush)
     583    z_streamp strm;
     584    int flush;
     585{
     586    int old_flush; /* value of flush param for previous deflate call */
     587    deflate_state *s;
     588
     589    if (strm == Z_NULL || strm->state == Z_NULL ||
     590        flush > Z_BLOCK || flush < 0) {
     591        return Z_STREAM_ERROR;
     592    }
     593    s = strm->state;
     594
     595    if (strm->next_out == Z_NULL ||
     596        (strm->next_in == Z_NULL && strm->avail_in != 0) ||
     597        (s->status == FINISH_STATE && flush != Z_FINISH)) {
     598        ERR_RETURN(strm, Z_STREAM_ERROR);
     599    }
     600    if (strm->avail_out == 0) ERR_RETURN(strm, Z_BUF_ERROR);
     601
     602    s->strm = strm; /* just in case */
     603    old_flush = s->last_flush;
     604    s->last_flush = flush;
     605
     606    /* Write the header */
     607    if (s->status == INIT_STATE) {
     608#ifdef GZIP
     609        if (s->wrap == 2) {
     610            strm->adler = crc32(0L, Z_NULL, 0);
     611            put_byte(s, 31);
     612            put_byte(s, 139);
     613            put_byte(s, 8);
     614            if (s->gzhead == Z_NULL) {
     615                put_byte(s, 0);
     616                put_byte(s, 0);
     617                put_byte(s, 0);
     618                put_byte(s, 0);
     619                put_byte(s, 0);
     620                put_byte(s, s->level == 9 ? 2 :
     621                            (s->strategy >= Z_HUFFMAN_ONLY || s->level < 2 ?
     622                             4 : 0));
     623                put_byte(s, OS_CODE);
     624                s->status = BUSY_STATE;
     625            }
     626            else {
     627                put_byte(s, (s->gzhead->text ? 1 : 0) +
     628                            (s->gzhead->hcrc ? 2 : 0) +
     629                            (s->gzhead->extra == Z_NULL ? 0 : 4) +
     630                            (s->gzhead->name == Z_NULL ? 0 : 8) +
     631                            (s->gzhead->comment == Z_NULL ? 0 : 16)
     632                        );
     633                put_byte(s, (Byte)(s->gzhead->time & 0xff));
     634                put_byte(s, (Byte)((s->gzhead->time >> 8) & 0xff));
     635                put_byte(s, (Byte)((s->gzhead->time >> 16) & 0xff));
     636                put_byte(s, (Byte)((s->gzhead->time >> 24) & 0xff));
     637                put_byte(s, s->level == 9 ? 2 :
     638                            (s->strategy >= Z_HUFFMAN_ONLY || s->level < 2 ?
     639                             4 : 0));
     640                put_byte(s, s->gzhead->os & 0xff);
     641                if (s->gzhead->extra != Z_NULL) {
     642                    put_byte(s, s->gzhead->extra_len & 0xff);
     643                    put_byte(s, (s->gzhead->extra_len >> 8) & 0xff);
     644                }
     645                if (s->gzhead->hcrc)
     646                    strm->adler = crc32(strm->adler, s->pending_buf,
     647                                        s->pending);
     648                s->gzindex = 0;
     649                s->status = EXTRA_STATE;
     650            }
     651        }
     652        else
     653#endif
     654        {
     655            uInt header = (Z_DEFLATED + ((s->w_bits-8)<<4)) << 8;
     656            uInt level_flags;
     657
     658            if (s->strategy >= Z_HUFFMAN_ONLY || s->level < 2)
     659                level_flags = 0;
     660            else if (s->level < 6)
     661                level_flags = 1;
     662            else if (s->level == 6)
     663                level_flags = 2;
     664            else
     665                level_flags = 3;
     666            header |= (level_flags << 6);
     667            if (s->strstart != 0) header |= PRESET_DICT;
     668            header += 31 - (header % 31);
     669
     670            s->status = BUSY_STATE;
     671            putShortMSB(s, header);
     672
     673            /* Save the adler32 of the preset dictionary: */
     674            if (s->strstart != 0) {
     675                putShortMSB(s, (uInt)(strm->adler >> 16));
     676                putShortMSB(s, (uInt)(strm->adler & 0xffff));
     677            }
     678            strm->adler = adler32(0L, Z_NULL, 0);
     679        }
     680    }
     681#ifdef GZIP
     682    if (s->status == EXTRA_STATE) {
     683        if (s->gzhead->extra != Z_NULL) {
     684            uInt beg = s->pending;  /* start of bytes to update crc */
     685
     686            while (s->gzindex < (s->gzhead->extra_len & 0xffff)) {
     687                if (s->pending == s->pending_buf_size) {
     688                    if (s->gzhead->hcrc && s->pending > beg)
     689                        strm->adler = crc32(strm->adler, s->pending_buf + beg,
     690                                            s->pending - beg);
     691                    flush_pending(strm);
     692                    beg = s->pending;
     693                    if (s->pending == s->pending_buf_size)
     694                        break;
     695                }
     696                put_byte(s, s->gzhead->extra[s->gzindex]);
     697                s->gzindex++;
     698            }
     699            if (s->gzhead->hcrc && s->pending > beg)
     700                strm->adler = crc32(strm->adler, s->pending_buf + beg,
     701                                    s->pending - beg);
     702            if (s->gzindex == s->gzhead->extra_len) {
     703                s->gzindex = 0;
     704                s->status = NAME_STATE;
     705            }
     706        }
     707        else
     708            s->status = NAME_STATE;
     709    }
     710    if (s->status == NAME_STATE) {
     711        if (s->gzhead->name != Z_NULL) {
     712            uInt beg = s->pending;  /* start of bytes to update crc */
     713            int val;
     714
     715            do {
     716                if (s->pending == s->pending_buf_size) {
     717                    if (s->gzhead->hcrc && s->pending > beg)
     718                        strm->adler = crc32(strm->adler, s->pending_buf + beg,
     719                                            s->pending - beg);
     720                    flush_pending(strm);
     721                    beg = s->pending;
     722                    if (s->pending == s->pending_buf_size) {
     723                        val = 1;
     724                        break;
     725                    }
     726                }
     727                val = s->gzhead->name[s->gzindex++];
     728                put_byte(s, val);
     729            } while (val != 0);
     730            if (s->gzhead->hcrc && s->pending > beg)
     731                strm->adler = crc32(strm->adler, s->pending_buf + beg,
     732                                    s->pending - beg);
     733            if (val == 0) {
     734                s->gzindex = 0;
     735                s->status = COMMENT_STATE;
     736            }
     737        }
     738        else
     739            s->status = COMMENT_STATE;
     740    }
     741    if (s->status == COMMENT_STATE) {
     742        if (s->gzhead->comment != Z_NULL) {
     743            uInt beg = s->pending;  /* start of bytes to update crc */
     744            int val;
     745
     746            do {
     747                if (s->pending == s->pending_buf_size) {
     748                    if (s->gzhead->hcrc && s->pending > beg)
     749                        strm->adler = crc32(strm->adler, s->pending_buf + beg,
     750                                            s->pending - beg);
     751                    flush_pending(strm);
     752                    beg = s->pending;
     753                    if (s->pending == s->pending_buf_size) {
     754                        val = 1;
     755                        break;
     756                    }
     757                }
     758                val = s->gzhead->comment[s->gzindex++];
     759                put_byte(s, val);
     760            } while (val != 0);
     761            if (s->gzhead->hcrc && s->pending > beg)
     762                strm->adler = crc32(strm->adler, s->pending_buf + beg,
     763                                    s->pending - beg);
     764            if (val == 0)
     765                s->status = HCRC_STATE;
     766        }
     767        else
     768            s->status = HCRC_STATE;
     769    }
     770    if (s->status == HCRC_STATE) {
     771        if (s->gzhead->hcrc) {
     772            if (s->pending + 2 > s->pending_buf_size)
     773                flush_pending(strm);
     774            if (s->pending + 2 <= s->pending_buf_size) {
     775                put_byte(s, (Byte)(strm->adler & 0xff));
     776                put_byte(s, (Byte)((strm->adler >> 8) & 0xff));
     777                strm->adler = crc32(0L, Z_NULL, 0);
     778                s->status = BUSY_STATE;
     779            }
     780        }
     781        else
     782            s->status = BUSY_STATE;
     783    }
     784#endif
     785
     786    /* Flush as much pending output as possible */
     787    if (s->pending != 0) {
     788        flush_pending(strm);
     789        if (strm->avail_out == 0) {
     790            /* Since avail_out is 0, deflate will be called again with
     791             * more output space, but possibly with both pending and
     792             * avail_in equal to zero. There won't be anything to do,
     793             * but this is not an error situation so make sure we
     794             * return OK instead of BUF_ERROR at next call of deflate:
     795             */
     796            s->last_flush = -1;
     797            return Z_OK;
     798        }
     799
     800    /* Make sure there is something to do and avoid duplicate consecutive
     801     * flushes. For repeated and useless calls with Z_FINISH, we keep
     802     * returning Z_STREAM_END instead of Z_BUF_ERROR.
     803     */
     804    } else if (strm->avail_in == 0 && flush <= old_flush &&
     805               flush != Z_FINISH) {
     806        ERR_RETURN(strm, Z_BUF_ERROR);
     807    }
     808
     809    /* User must not provide more input after the first FINISH: */
     810    if (s->status == FINISH_STATE && strm->avail_in != 0) {
     811        ERR_RETURN(strm, Z_BUF_ERROR);
     812    }
     813
     814    /* Start a new block or continue the current one.
     815     */
     816    if (strm->avail_in != 0 || s->lookahead != 0 ||
     817        (flush != Z_NO_FLUSH && s->status != FINISH_STATE)) {
     818        block_state bstate;
     819
     820        bstate = s->strategy == Z_HUFFMAN_ONLY ? deflate_huff(s, flush) :
     821                    (s->strategy == Z_RLE ? deflate_rle(s, flush) :
     822                        (*(configuration_table[s->level].func))(s, flush));
     823
     824        if (bstate == finish_started || bstate == finish_done) {
     825            s->status = FINISH_STATE;
     826        }
     827        if (bstate == need_more || bstate == finish_started) {
     828            if (strm->avail_out == 0) {
     829                s->last_flush = -1; /* avoid BUF_ERROR next call, see above */
     830            }
     831            return Z_OK;
     832            /* If flush != Z_NO_FLUSH && avail_out == 0, the next call
     833             * of deflate should use the same flush parameter to make sure
     834             * that the flush is complete. So we don't have to output an
     835             * empty block here, this will be done at next call. This also
     836             * ensures that for a very small output buffer, we emit at most
     837             * one empty block.
     838             */
     839        }
     840        if (bstate == block_done) {
     841            if (flush == Z_PARTIAL_FLUSH) {
     842                _tr_align(s);
     843            } else if (flush != Z_BLOCK) { /* FULL_FLUSH or SYNC_FLUSH */
     844                _tr_stored_block(s, (char*)0, 0L, 0);
     845                /* For a full flush, this empty block will be recognized
     846                 * as a special marker by inflate_sync().
     847                 */
     848                if (flush == Z_FULL_FLUSH) {
     849                    CLEAR_HASH(s);             /* forget history */
     850                    if (s->lookahead == 0) {
     851                        s->strstart = 0;
     852                        s->block_start = 0L;
     853                    }
     854                }
     855            }
     856            flush_pending(strm);
     857            if (strm->avail_out == 0) {
     858              s->last_flush = -1; /* avoid BUF_ERROR at next call, see above */
     859              return Z_OK;
     860            }
     861        }
     862    }
     863    Assert(strm->avail_out > 0, "bug2");
     864
     865    if (flush != Z_FINISH) return Z_OK;
     866    if (s->wrap <= 0) return Z_STREAM_END;
     867
     868    /* Write the trailer */
     869#ifdef GZIP
     870    if (s->wrap == 2) {
     871        put_byte(s, (Byte)(strm->adler & 0xff));
     872        put_byte(s, (Byte)((strm->adler >> 8) & 0xff));
     873        put_byte(s, (Byte)((strm->adler >> 16) & 0xff));
     874        put_byte(s, (Byte)((strm->adler >> 24) & 0xff));
     875        put_byte(s, (Byte)(strm->total_in & 0xff));
     876        put_byte(s, (Byte)((strm->total_in >> 8) & 0xff));
     877        put_byte(s, (Byte)((strm->total_in >> 16) & 0xff));
     878        put_byte(s, (Byte)((strm->total_in >> 24) & 0xff));
     879    }
     880    else
     881#endif
     882    {
     883        putShortMSB(s, (uInt)(strm->adler >> 16));
     884        putShortMSB(s, (uInt)(strm->adler & 0xffff));
     885    }
     886    flush_pending(strm);
     887    /* If avail_out is zero, the application will call deflate again
     888     * to flush the rest.
     889     */
     890    if (s->wrap > 0) s->wrap = -s->wrap; /* write the trailer only once! */
     891    return s->pending != 0 ? Z_OK : Z_STREAM_END;
     892}
     893
     894/* ========================================================================= */
     895int ZEXPORT deflateEnd (strm)
     896    z_streamp strm;
     897{
     898    int status;
     899
     900    if (strm == Z_NULL || strm->state == Z_NULL) return Z_STREAM_ERROR;
     901
     902    status = strm->state->status;
     903    if (status != INIT_STATE &&
     904        status != EXTRA_STATE &&
     905        status != NAME_STATE &&
     906        status != COMMENT_STATE &&
     907        status != HCRC_STATE &&
     908        status != BUSY_STATE &&
     909        status != FINISH_STATE) {
     910      return Z_STREAM_ERROR;
     911    }
     912
     913    /* Deallocate in reverse order of allocations: */
     914    TRY_FREE(strm, strm->state->pending_buf);
     915    TRY_FREE(strm, strm->state->head);
     916    TRY_FREE(strm, strm->state->prev);
     917    TRY_FREE(strm, strm->state->window);
     918
     919    ZFREE(strm, strm->state);
     920    strm->state = Z_NULL;
     921
     922    return status == BUSY_STATE ? Z_DATA_ERROR : Z_OK;
     923}
     924
     925/* =========================================================================
     926 * Copy the source state to the destination state.
     927 * To simplify the source, this is not supported for 16-bit MSDOS (which
     928 * doesn't have enough memory anyway to duplicate compression states).
     929 */
     930int ZEXPORT deflateCopy (dest, source)
     931    z_streamp dest;
     932    z_streamp source;
     933{
     934#ifdef MAXSEG_64K
     935    return Z_STREAM_ERROR;
     936#else
     937    deflate_state *ds;
     938    deflate_state *ss;
     939    ushf *overlay;
     940
     941
     942    if (source == Z_NULL || dest == Z_NULL || source->state == Z_NULL) {
     943        return Z_STREAM_ERROR;
     944    }
     945
     946    ss = source->state;
     947
     948    zmemcpy(dest, source, sizeof(z_stream));
     949
     950    ds = (deflate_state *) ZALLOC(dest, 1, sizeof(deflate_state));
     951    if (ds == Z_NULL) return Z_MEM_ERROR;
     952    dest->state = (struct internal_state FAR *) ds;
     953    zmemcpy(ds, ss, sizeof(deflate_state));
     954    ds->strm = dest;
     955
     956    ds->window = (Bytef *) ZALLOC(dest, ds->w_size, 2*sizeof(Byte));
     957    ds->prev   = (Posf *)  ZALLOC(dest, ds->w_size, sizeof(Pos));
     958    ds->head   = (Posf *)  ZALLOC(dest, ds->hash_size, sizeof(Pos));
     959    overlay = (ushf *) ZALLOC(dest, ds->lit_bufsize, sizeof(ush)+2);
     960    ds->pending_buf = (uchf *) overlay;
     961
     962    if (ds->window == Z_NULL || ds->prev == Z_NULL || ds->head == Z_NULL ||
     963        ds->pending_buf == Z_NULL) {
     964        deflateEnd (dest);
     965        return Z_MEM_ERROR;
     966    }
     967    /* following zmemcpy do not work for 16-bit MSDOS */
     968    zmemcpy(ds->window, ss->window, ds->w_size * 2 * sizeof(Byte));
     969    zmemcpy(ds->prev, ss->prev, ds->w_size * sizeof(Pos));
     970    zmemcpy(ds->head, ss->head, ds->hash_size * sizeof(Pos));
     971    zmemcpy(ds->pending_buf, ss->pending_buf, (uInt)ds->pending_buf_size);
     972
     973    ds->pending_out = ds->pending_buf + (ss->pending_out - ss->pending_buf);
     974    ds->d_buf = overlay + ds->lit_bufsize/sizeof(ush);
     975    ds->l_buf = ds->pending_buf + (1+sizeof(ush))*ds->lit_bufsize;
     976
     977    ds->l_desc.dyn_tree = ds->dyn_ltree;
     978    ds->d_desc.dyn_tree = ds->dyn_dtree;
     979    ds->bl_desc.dyn_tree = ds->bl_tree;
     980
     981    return Z_OK;
     982#endif /* MAXSEG_64K */
     983}
     984
     985/* ===========================================================================
     986 * Read a new buffer from the current input stream, update the adler32
     987 * and total number of bytes read.  All deflate() input goes through
     988 * this function so some applications may wish to modify it to avoid
     989 * allocating a large strm->next_in buffer and copying from it.
     990 * (See also flush_pending()).
     991 */
     992local int read_buf(strm, buf, size)
     993    z_streamp strm;
     994    Bytef *buf;
     995    unsigned size;
     996{
     997    unsigned len = strm->avail_in;
     998
     999    if (len > size) len = size;
     1000    if (len == 0) return 0;
     1001
     1002    strm->avail_in  -= len;
     1003
     1004    if (strm->state->wrap == 1) {
     1005        strm->adler = adler32(strm->adler, strm->next_in, len);
     1006    }
     1007#ifdef GZIP
     1008    else if (strm->state->wrap == 2) {
     1009        strm->adler = crc32(strm->adler, strm->next_in, len);
     1010    }
     1011#endif
     1012    zmemcpy(buf, strm->next_in, len);
     1013    strm->next_in  += len;
     1014    strm->total_in += len;
     1015
     1016    return (int)len;
     1017}
     1018
     1019/* ===========================================================================
     1020 * Initialize the "longest match" routines for a new zlib stream
     1021 */
     1022local void lm_init (s)
     1023    deflate_state *s;
     1024{
     1025    s->window_size = (ulg)2L*s->w_size;
     1026
     1027    CLEAR_HASH(s);
    3061028
    3071029    /* Set the default configuration parameters:
    3081030     */
    309     max_lazy_match   = configuration_table[pack_level].max_lazy;
    310     good_match       = configuration_table[pack_level].good_length;
    311 #ifndef FULL_SEARCH
    312     nice_match       = configuration_table[pack_level].nice_length;
    313 #endif
    314     max_chain_length = configuration_table[pack_level].max_chain;
    315     if (pack_level == 1) {
    316        *flags |= FAST;
    317     } else if (pack_level == 9) {
    318        *flags |= SLOW;
    319     }
    320     /* ??? reduce max_chain_length for binary files */
    321 
    322     strstart = 0;
    323     block_start = 0L;
     1031    s->max_lazy_match   = configuration_table[s->level].max_lazy;
     1032    s->good_match       = configuration_table[s->level].good_length;
     1033    s->nice_match       = configuration_table[s->level].nice_length;
     1034    s->max_chain_length = configuration_table[s->level].max_chain;
     1035
     1036    s->strstart = 0;
     1037    s->block_start = 0L;
     1038    s->lookahead = 0;
     1039    s->match_length = s->prev_length = MIN_MATCH-1;
     1040    s->match_available = 0;
     1041    s->ins_h = 0;
     1042#ifndef FASTEST
    3241043#ifdef ASMV
    3251044    match_init(); /* initialize the asm code */
    3261045#endif
    327 
    328     lookahead = read_buf((char*)window,
    329                          sizeof(int) <= 2 ? (unsigned)WSIZE : 2*WSIZE);
    330 
    331     if (lookahead == 0 || lookahead == (unsigned)EOF) {
    332        eofile = 1, lookahead = 0;
    333        return;
    334     }
    335     eofile = 0;
    336     /* Make sure that we always have enough lookahead. This is important
    337      * if input comes from a device such as a tty.
    338      */
    339     while (lookahead < MIN_LOOKAHEAD && !eofile) fill_window();
    340 
    341     ins_h = 0;
    342     for (j=0; j<MIN_MATCH-1; j++) UPDATE_HASH(ins_h, window[j]);
    343     /* If lookahead < MIN_MATCH, ins_h is garbage, but this is
    344      * not important since only literal bytes will be emitted.
    345      */
    346 }
    347 
     1046#endif
     1047}
     1048
     1049#ifndef FASTEST
    3481050/* ===========================================================================
    3491051 * Set match_start to the longest match starting at the given string and
     
    3531055 * IN assertions: cur_match is the head of the hash chain for the current
    3541056 *   string (strstart) and its distance is <= MAX_DIST, and prev_length >= 1
     1057 * OUT assertion: the match length is not greater than s->lookahead.
    3551058 */
    3561059#ifndef ASMV
    357 /* For MSDOS, OS/2 and 386 Unix, an optimized version is in match.asm or
    358  * match.s. The code is functionally equivalent, so you can use the C version
    359  * if desired.
    360  */
    361 int longest_match(cur_match)
     1060/* For 80x86 and 680x0, an optimized version will be provided in match.asm or
     1061 * match.S. The code will be functionally equivalent.
     1062 */
     1063local uInt longest_match(s, cur_match)
     1064    deflate_state *s;
    3621065    IPos cur_match;                             /* current match */
    3631066{
    364     unsigned chain_length = max_chain_length;   /* max hash chain length */
    365     register uch *scan = window + strstart;    /* current string */
    366     register uch *match;                        /* matched string */
     1067    unsigned chain_length = s->max_chain_length;/* max hash chain length */
     1068    register Bytef *scan = s->window + s->strstart; /* current string */
     1069    register Bytef *match;                       /* matched string */
    3671070    register int len;                           /* length of current match */
    368     int best_len = prev_length;                 /* best match length so far */
    369     IPos limit = strstart > (IPos)MAX_DIST ? strstart - (IPos)MAX_DIST : NIL;
     1071    int best_len = s->prev_length;              /* best match length so far */
     1072    int nice_match = s->nice_match;             /* stop if match long enough */
     1073    IPos limit = s->strstart > (IPos)MAX_DIST(s) ?
     1074        s->strstart - (IPos)MAX_DIST(s) : NIL;
    3701075    /* Stop when cur_match becomes <= limit. To simplify the code,
    3711076     * we prevent matches with the string of window index 0.
    3721077     */
    373 
    374 /* The code is optimized for HASH_BITS >= 8 and MAX_MATCH-2 multiple of 16.
    375  * It is easy to get rid of this optimization if necessary.
    376  */
    377 #if HASH_BITS < 8 || MAX_MATCH != 258
    378    error: Code too clever
    379 #endif
     1078    Posf *prev = s->prev;
     1079    uInt wmask = s->w_mask;
    3801080
    3811081#ifdef UNALIGNED_OK
     
    3831083     * Try with and without -DUNALIGNED_OK to check.
    3841084     */
    385     register uch *strend = window + strstart + MAX_MATCH - 1;
    386     register ush scan_start = *(ush*)scan;
    387     register ush scan_end   = *(ush*)(scan+best_len-1);
     1085    register Bytef *strend = s->window + s->strstart + MAX_MATCH - 1;
     1086    register ush scan_start = *(ushf*)scan;
     1087    register ush scan_end   = *(ushf*)(scan+best_len-1);
    3881088#else
    389     register uch *strend = window + strstart + MAX_MATCH;
    390     register uch scan_end1  = scan[best_len-1];
    391     register uch scan_end   = scan[best_len];
    392 #endif
     1089    register Bytef *strend = s->window + s->strstart + MAX_MATCH;
     1090    register Byte scan_end1  = scan[best_len-1];
     1091    register Byte scan_end   = scan[best_len];
     1092#endif
     1093
     1094    /* The code is optimized for HASH_BITS >= 8 and MAX_MATCH-2 multiple of 16.
     1095     * It is easy to get rid of this optimization if necessary.
     1096     */
     1097    Assert(s->hash_bits >= 8 && MAX_MATCH == 258, "Code too clever");
    3931098
    3941099    /* Do not waste too much time if we already have a good match: */
    395     if (prev_length >= good_match) {
     1100    if (s->prev_length >= s->good_match) {
    3961101        chain_length >>= 2;
    3971102    }
    398     Assert(strstart <= window_size-MIN_LOOKAHEAD, "insufficient lookahead");
     1103    /* Do not look for matches beyond the end of the input. This is necessary
     1104     * to make deflate deterministic.
     1105     */
     1106    if ((uInt)nice_match > s->lookahead) nice_match = s->lookahead;
     1107
     1108    Assert((ulg)s->strstart <= s->window_size-MIN_LOOKAHEAD, "need lookahead");
    3991109
    4001110    do {
    401         Assert(cur_match < strstart, "no future");
    402         match = window + cur_match;
     1111        Assert(cur_match < s->strstart, "no future");
     1112        match = s->window + cur_match;
    4031113
    4041114        /* Skip to next match if the match length cannot increase
    405          * or if the match length is less than 2:
     1115         * or if the match length is less than 2.  Note that the checks below
     1116         * for insufficient lookahead only occur occasionally for performance
     1117         * reasons.  Therefore uninitialized memory will be accessed, and
     1118         * conditional jumps will be made that depend on those values.
     1119         * However the length of the match is limited to the lookahead, so
     1120         * the output of deflate is not affected by the uninitialized values.
    4061121         */
    4071122#if (defined(UNALIGNED_OK) && MAX_MATCH == 258)
     
    4091124         * UNALIGNED_OK if your compiler uses a different size.
    4101125         */
    411         if (*(ush*)(match+best_len-1) != scan_end ||
    412             *(ush*)match != scan_start) continue;
     1126        if (*(ushf*)(match+best_len-1) != scan_end ||
     1127            *(ushf*)match != scan_start) continue;
    4131128
    4141129        /* It is not necessary to compare scan[2] and match[2] since they are
     
    4211136         * to check more often for insufficient lookahead.
    4221137         */
     1138        Assert(scan[2] == match[2], "scan[2]?");
    4231139        scan++, match++;
    4241140        do {
    425         } while (*(ush*)(scan+=2) == *(ush*)(match+=2) &&
    426                  *(ush*)(scan+=2) == *(ush*)(match+=2) &&
    427                  *(ush*)(scan+=2) == *(ush*)(match+=2) &&
    428                  *(ush*)(scan+=2) == *(ush*)(match+=2) &&
     1141        } while (*(ushf*)(scan+=2) == *(ushf*)(match+=2) &&
     1142                 *(ushf*)(scan+=2) == *(ushf*)(match+=2) &&
     1143                 *(ushf*)(scan+=2) == *(ushf*)(match+=2) &&
     1144                 *(ushf*)(scan+=2) == *(ushf*)(match+=2) &&
    4291145                 scan < strend);
    4301146        /* The funny "do {}" generates better code on most compilers */
    4311147
    4321148        /* Here, scan <= window+strstart+257 */
    433         Assert(scan <= window+(unsigned)(window_size-1), "wild scan");
     1149        Assert(scan <= s->window+(unsigned)(s->window_size-1), "wild scan");
    4341150        if (*scan == *match) scan++;
    4351151
     
    4511167         */
    4521168        scan += 2, match++;
     1169        Assert(*scan == *match, "match[2]?");
    4531170
    4541171        /* We check for insufficient lookahead only every 8th comparison;
     
    4621179                 scan < strend);
    4631180
     1181        Assert(scan <= s->window+(unsigned)(s->window_size-1), "wild scan");
     1182
    4641183        len = MAX_MATCH - (int)(strend - scan);
    4651184        scan = strend - MAX_MATCH;
     
    4681187
    4691188        if (len > best_len) {
    470             match_start = cur_match;
     1189            s->match_start = cur_match;
    4711190            best_len = len;
    4721191            if (len >= nice_match) break;
    4731192#ifdef UNALIGNED_OK
    474             scan_end = *(ush*)(scan+best_len-1);
     1193            scan_end = *(ushf*)(scan+best_len-1);
    4751194#else
    4761195            scan_end1  = scan[best_len-1];
     
    4781197#endif
    4791198        }
    480     } while ((cur_match = prev[cur_match & WMASK]) > limit
    481              && --chain_length != 0);
    482 
    483     return best_len;
     1199    } while ((cur_match = prev[cur_match & wmask]) > limit
     1200             && --chain_length != 0);
     1201
     1202    if ((uInt)best_len <= s->lookahead) return (uInt)best_len;
     1203    return s->lookahead;
    4841204}
    4851205#endif /* ASMV */
     1206
     1207#else /* FASTEST */
     1208
     1209/* ---------------------------------------------------------------------------
     1210 * Optimized version for FASTEST only
     1211 */
     1212local uInt longest_match(s, cur_match)
     1213    deflate_state *s;
     1214    IPos cur_match;                             /* current match */
     1215{
     1216    register Bytef *scan = s->window + s->strstart; /* current string */
     1217    register Bytef *match;                       /* matched string */
     1218    register int len;                           /* length of current match */
     1219    register Bytef *strend = s->window + s->strstart + MAX_MATCH;
     1220
     1221    /* The code is optimized for HASH_BITS >= 8 and MAX_MATCH-2 multiple of 16.
     1222     * It is easy to get rid of this optimization if necessary.
     1223     */
     1224    Assert(s->hash_bits >= 8 && MAX_MATCH == 258, "Code too clever");
     1225
     1226    Assert((ulg)s->strstart <= s->window_size-MIN_LOOKAHEAD, "need lookahead");
     1227
     1228    Assert(cur_match < s->strstart, "no future");
     1229
     1230    match = s->window + cur_match;
     1231
     1232    /* Return failure if the match length is less than 2:
     1233     */
     1234    if (match[0] != scan[0] || match[1] != scan[1]) return MIN_MATCH-1;
     1235
     1236    /* The check at best_len-1 can be removed because it will be made
     1237     * again later. (This heuristic is not always a win.)
     1238     * It is not necessary to compare scan[2] and match[2] since they
     1239     * are always equal when the other bytes match, given that
     1240     * the hash keys are equal and that HASH_BITS >= 8.
     1241     */
     1242    scan += 2, match += 2;
     1243    Assert(*scan == *match, "match[2]?");
     1244
     1245    /* We check for insufficient lookahead only every 8th comparison;
     1246     * the 256th check will be made at strstart+258.
     1247     */
     1248    do {
     1249    } while (*++scan == *++match && *++scan == *++match &&
     1250             *++scan == *++match && *++scan == *++match &&
     1251             *++scan == *++match && *++scan == *++match &&
     1252             *++scan == *++match && *++scan == *++match &&
     1253             scan < strend);
     1254
     1255    Assert(scan <= s->window+(unsigned)(s->window_size-1), "wild scan");
     1256
     1257    len = MAX_MATCH - (int)(strend - scan);
     1258
     1259    if (len < MIN_MATCH) return MIN_MATCH - 1;
     1260
     1261    s->match_start = cur_match;
     1262    return (uInt)len <= s->lookahead ? (uInt)len : s->lookahead;
     1263}
     1264
     1265#endif /* FASTEST */
    4861266
    4871267#ifdef DEBUG
     
    4891269 * Check that the match at match_start is indeed a match.
    4901270 */
    491 local void check_match(start, match, length)
     1271local void check_match(s, start, match, length)
     1272    deflate_state *s;
    4921273    IPos start, match;
    4931274    int length;
    4941275{
    4951276    /* check that the match is indeed a match */
    496     if (memcmp((char*)window + match,
    497                 (char*)window + start, length) != EQUAL) {
    498         fprintf(stderr,
    499             " start %d, match %d, length %d\n",
    500             start, match, length);
    501         error("invalid match");
    502     }
    503     if (verbose > 1) {
     1277    if (zmemcmp(s->window + match,
     1278                s->window + start, length) != EQUAL) {
     1279        fprintf(stderr, " start %u, match %u, length %d\n",
     1280                start, match, length);
     1281        do {
     1282            fprintf(stderr, "%c%c", s->window[match++], s->window[start++]);
     1283        } while (--length != 0);
     1284        z_error("invalid match");
     1285    }
     1286    if (z_verbose > 1) {
    5041287        fprintf(stderr,"\\[%d,%d]", start-match, length);
    505         do { putc(window[start++], stderr); } while (--length != 0);
     1288        do { putc(s->window[start++], stderr); } while (--length != 0);
    5061289    }
    5071290}
    5081291#else
    509 #  define check_match(start, match, length)
    510 #endif
     1292#  define check_match(s, start, match, length)
     1293#endif /* DEBUG */
    5111294
    5121295/* ===========================================================================
    5131296 * Fill the window when the lookahead becomes insufficient.
    514  * Updates strstart and lookahead, and sets eofile if end of input file.
    515  * IN assertion: lookahead < MIN_LOOKAHEAD && strstart + lookahead > 0
    516  * OUT assertions: at least one byte has been read, or eofile is set;
    517  *    file reads are performed for at least two bytes (required for the
    518  *    translate_eol option).
    519  */
    520 local void fill_window()
     1297 * Updates strstart and lookahead.
     1298 *
     1299 * IN assertion: lookahead < MIN_LOOKAHEAD
     1300 * OUT assertions: strstart <= window_size-MIN_LOOKAHEAD
     1301 *    At least one byte has been read, or avail_in == 0; reads are
     1302 *    performed for at least two bytes (required for the zip translate_eol
     1303 *    option -- not supported here).
     1304 */
     1305local void fill_window(s)
     1306    deflate_state *s;
    5211307{
    5221308    register unsigned n, m;
    523     unsigned more = (unsigned)(window_size - (ulg)lookahead - (ulg)strstart);
    524     /* Amount of free space at the end of the window. */
    525 
    526     /* If the window is almost full and there is insufficient lookahead,
    527      * move the upper half to the lower one to make room in the upper half.
     1309    register Posf *p;
     1310    unsigned more;    /* Amount of free space at the end of the window. */
     1311    uInt wsize = s->w_size;
     1312
     1313    do {
     1314        more = (unsigned)(s->window_size -(ulg)s->lookahead -(ulg)s->strstart);
     1315
     1316        /* Deal with !@#$% 64K limit: */
     1317        if (sizeof(int) <= 2) {
     1318            if (more == 0 && s->strstart == 0 && s->lookahead == 0) {
     1319                more = wsize;
     1320
     1321            } else if (more == (unsigned)(-1)) {
     1322                /* Very unlikely, but possible on 16 bit machine if
     1323                 * strstart == 0 && lookahead == 1 (input done a byte at time)
     1324                 */
     1325                more--;
     1326            }
     1327        }
     1328
     1329        /* If the window is almost full and there is insufficient lookahead,
     1330         * move the upper half to the lower one to make room in the upper half.
     1331         */
     1332        if (s->strstart >= wsize+MAX_DIST(s)) {
     1333
     1334            zmemcpy(s->window, s->window+wsize, (unsigned)wsize);
     1335            s->match_start -= wsize;
     1336            s->strstart    -= wsize; /* we now have strstart >= MAX_DIST */
     1337            s->block_start -= (long) wsize;
     1338
     1339            /* Slide the hash table (could be avoided with 32 bit values
     1340               at the expense of memory usage). We slide even when level == 0
     1341               to keep the hash table consistent if we switch back to level > 0
     1342               later. (Using level 0 permanently is not an optimal usage of
     1343               zlib, so we don't care about this pathological case.)
     1344             */
     1345            n = s->hash_size;
     1346            p = &s->head[n];
     1347            do {
     1348                m = *--p;
     1349                *p = (Pos)(m >= wsize ? m-wsize : NIL);
     1350            } while (--n);
     1351
     1352            n = wsize;
     1353#ifndef FASTEST
     1354            p = &s->prev[n];
     1355            do {
     1356                m = *--p;
     1357                *p = (Pos)(m >= wsize ? m-wsize : NIL);
     1358                /* If n is not on any hash chain, prev[n] is garbage but
     1359                 * its value will never be used.
     1360                 */
     1361            } while (--n);
     1362#endif
     1363            more += wsize;
     1364        }
     1365        if (s->strm->avail_in == 0) return;
     1366
     1367        /* If there was no sliding:
     1368         *    strstart <= WSIZE+MAX_DIST-1 && lookahead <= MIN_LOOKAHEAD - 1 &&
     1369         *    more == window_size - lookahead - strstart
     1370         * => more >= window_size - (MIN_LOOKAHEAD-1 + WSIZE + MAX_DIST-1)
     1371         * => more >= window_size - 2*WSIZE + 2
     1372         * In the BIG_MEM or MMAP case (not yet supported),
     1373         *   window_size == input_size + MIN_LOOKAHEAD  &&
     1374         *   strstart + s->lookahead <= input_size => more >= MIN_LOOKAHEAD.
     1375         * Otherwise, window_size == 2*WSIZE so more >= 2.
     1376         * If there was sliding, more >= WSIZE. So in all cases, more >= 2.
     1377         */
     1378        Assert(more >= 2, "more < 2");
     1379
     1380        n = read_buf(s->strm, s->window + s->strstart + s->lookahead, more);
     1381        s->lookahead += n;
     1382
     1383        /* Initialize the hash value now that we have some input: */
     1384        if (s->lookahead >= MIN_MATCH) {
     1385            s->ins_h = s->window[s->strstart];
     1386            UPDATE_HASH(s, s->ins_h, s->window[s->strstart+1]);
     1387#if MIN_MATCH != 3
     1388            Call UPDATE_HASH() MIN_MATCH-3 more times
     1389#endif
     1390        }
     1391        /* If the whole input has less than MIN_MATCH bytes, ins_h is garbage,
     1392         * but this is not important since only literal bytes will be emitted.
     1393         */
     1394
     1395    } while (s->lookahead < MIN_LOOKAHEAD && s->strm->avail_in != 0);
     1396
     1397    /* If the WIN_INIT bytes after the end of the current data have never been
     1398     * written, then zero those bytes in order to avoid memory check reports of
     1399     * the use of uninitialized (or uninitialised as Julian writes) bytes by
     1400     * the longest match routines.  Update the high water mark for the next
     1401     * time through here.  WIN_INIT is set to MAX_MATCH since the longest match
     1402     * routines allow scanning to strstart + MAX_MATCH, ignoring lookahead.
    5281403     */
    529     if (more == (unsigned)EOF) {
    530         /* Very unlikely, but possible on 16 bit machine if strstart == 0
    531          * and lookahead == 1 (input done one byte at time)
    532          */
    533         more--;
    534     } else if (strstart >= WSIZE+MAX_DIST) {
    535         /* By the IN assertion, the window is not empty so we can't confuse
    536          * more == 0 with more == 64K on a 16 bit machine.
    537          */
    538         Assert(window_size == (ulg)2*WSIZE, "no sliding with BIG_MEM");
    539 
    540         memcpy((char*)window, (char*)window+WSIZE, (unsigned)WSIZE);
    541         match_start -= WSIZE;
    542         strstart    -= WSIZE; /* we now have strstart >= MAX_DIST: */
    543 
    544         block_start -= (long) WSIZE;
    545 
    546         for (n = 0; n < HASH_SIZE; n++) {
    547             m = head[n];
    548             head[n] = (Pos)(m >= WSIZE ? m-WSIZE : NIL);
    549         }
    550         for (n = 0; n < WSIZE; n++) {
    551             m = prev[n];
    552             prev[n] = (Pos)(m >= WSIZE ? m-WSIZE : NIL);
    553             /* If n is not on any hash chain, prev[n] is garbage but
    554              * its value will never be used.
     1404    if (s->high_water < s->window_size) {
     1405        ulg curr = s->strstart + (ulg)(s->lookahead);
     1406        ulg init;
     1407
     1408        if (s->high_water < curr) {
     1409            /* Previous high water mark below current data -- zero WIN_INIT
     1410             * bytes or up to end of window, whichever is less.
    5551411             */
    556         }
    557         more += WSIZE;
    558     }
    559     /* At this point, more >= 2 */
    560     if (!eofile) {
    561         n = read_buf((char*)window+strstart+lookahead, more);
    562         if (n == 0 || n == (unsigned)EOF) {
    563             eofile = 1;
    564         } else {
    565             lookahead += n;
     1412            init = s->window_size - curr;
     1413            if (init > WIN_INIT)
     1414                init = WIN_INIT;
     1415            zmemzero(s->window + curr, (unsigned)init);
     1416            s->high_water = curr + init;
     1417        }
     1418        else if (s->high_water < (ulg)curr + WIN_INIT) {
     1419            /* High water mark at or above current data, but below current data
     1420             * plus WIN_INIT -- zero out to current data plus WIN_INIT, or up
     1421             * to end of window, whichever is less.
     1422             */
     1423            init = (ulg)curr + WIN_INIT - s->high_water;
     1424            if (init > s->window_size - s->high_water)
     1425                init = s->window_size - s->high_water;
     1426            zmemzero(s->window + s->high_water, (unsigned)init);
     1427            s->high_water += init;
    5661428        }
    5671429    }
     
    5721434 * IN assertion: strstart is set to the end of the current match.
    5731435 */
    574 #define FLUSH_BLOCK(eof) \
    575    flush_block(block_start >= 0L ? (char*)&window[(unsigned)block_start] : \
    576                 (char*)NULL, (long)strstart - block_start, (eof))
     1436#define FLUSH_BLOCK_ONLY(s, last) { \
     1437   _tr_flush_block(s, (s->block_start >= 0L ? \
     1438                   (charf *)&s->window[(unsigned)s->block_start] : \
     1439                   (charf *)Z_NULL), \
     1440                (ulg)((long)s->strstart - s->block_start), \
     1441                (last)); \
     1442   s->block_start = s->strstart; \
     1443   flush_pending(s->strm); \
     1444   Tracev((stderr,"[FLUSH]")); \
     1445}
     1446
     1447/* Same but force premature exit if necessary. */
     1448#define FLUSH_BLOCK(s, last) { \
     1449   FLUSH_BLOCK_ONLY(s, last); \
     1450   if (s->strm->avail_out == 0) return (last) ? finish_started : need_more; \
     1451}
    5771452
    5781453/* ===========================================================================
    579  * Processes a new input file and return its compressed length. This
    580  * function does not perform lazy evaluationof matches and inserts
     1454 * Copy without compression as much as possible from the input stream, return
     1455 * the current block state.
     1456 * This function does not insert new strings in the dictionary since
     1457 * uncompressible data is probably not useful. This function is used
     1458 * only for the level=0 compression option.
     1459 * NOTE: this function should be optimized to avoid extra copying from
     1460 * window to pending_buf.
     1461 */
     1462local block_state deflate_stored(s, flush)
     1463    deflate_state *s;
     1464    int flush;
     1465{
     1466    /* Stored blocks are limited to 0xffff bytes, pending_buf is limited
     1467     * to pending_buf_size, and each stored block has a 5 byte header:
     1468     */
     1469    ulg max_block_size = 0xffff;
     1470    ulg max_start;
     1471
     1472    if (max_block_size > s->pending_buf_size - 5) {
     1473        max_block_size = s->pending_buf_size - 5;
     1474    }
     1475
     1476    /* Copy as much as possible from input to output: */
     1477    for (;;) {
     1478        /* Fill the window as much as possible: */
     1479        if (s->lookahead <= 1) {
     1480
     1481            Assert(s->strstart < s->w_size+MAX_DIST(s) ||
     1482                   s->block_start >= (long)s->w_size, "slide too late");
     1483
     1484            fill_window(s);
     1485            if (s->lookahead == 0 && flush == Z_NO_FLUSH) return need_more;
     1486
     1487            if (s->lookahead == 0) break; /* flush the current block */
     1488        }
     1489        Assert(s->block_start >= 0L, "block gone");
     1490
     1491        s->strstart += s->lookahead;
     1492        s->lookahead = 0;
     1493
     1494        /* Emit a stored block if pending_buf will be full: */
     1495        max_start = s->block_start + max_block_size;
     1496        if (s->strstart == 0 || (ulg)s->strstart >= max_start) {
     1497            /* strstart == 0 is possible when wraparound on 16-bit machine */
     1498            s->lookahead = (uInt)(s->strstart - max_start);
     1499            s->strstart = (uInt)max_start;
     1500            FLUSH_BLOCK(s, 0);
     1501        }
     1502        /* Flush if we may have to slide, otherwise block_start may become
     1503         * negative and the data will be gone:
     1504         */
     1505        if (s->strstart - (uInt)s->block_start >= MAX_DIST(s)) {
     1506            FLUSH_BLOCK(s, 0);
     1507        }
     1508    }
     1509    FLUSH_BLOCK(s, flush == Z_FINISH);
     1510    return flush == Z_FINISH ? finish_done : block_done;
     1511}
     1512
     1513/* ===========================================================================
     1514 * Compress as much as possible from the input stream, return the current
     1515 * block state.
     1516 * This function does not perform lazy evaluation of matches and inserts
    5811517 * new strings in the dictionary only for unmatched strings or for short
    5821518 * matches. It is used only for the fast compression options.
    5831519 */
    584 local ulg deflate_fast()
    585 {
    586     IPos hash_head; /* head of the hash chain */
    587     int flush;      /* set if current block must be flushed */
    588     unsigned match_length = 0;  /* length of best match */
    589 
    590     prev_length = MIN_MATCH-1;
    591     while (lookahead != 0) {
    592         /* Insert the string window[strstart .. strstart+2] in the
    593          * dictionary, and set hash_head to the head of the hash chain:
    594          */
    595         INSERT_STRING(strstart, hash_head);
    596 
    597         /* Find the longest match, discarding those <= prev_length.
    598          * At this point we have always match_length < MIN_MATCH
    599          */
    600         if (hash_head != NIL && strstart - hash_head <= MAX_DIST) {
    601             /* To simplify the code, we prevent matches with the string
    602              * of window index 0 (in particular we have to avoid a match
    603              * of the string with itself at the start of the input file).
    604              */
    605             match_length = longest_match (hash_head);
    606             /* longest_match() sets match_start */
    607             if (match_length > lookahead) match_length = lookahead;
    608         }
    609         if (match_length >= MIN_MATCH) {
    610             check_match(strstart, match_start, match_length);
    611 
    612             flush = ct_tally(strstart-match_start, match_length - MIN_MATCH);
    613 
    614             lookahead -= match_length;
    615 
    616             /* Insert new strings in the hash table only if the match length
    617              * is not too large. This saves time but degrades compression.
    618              */
    619             if (match_length <= max_insert_length) {
    620                 match_length--; /* string at strstart already in hash table */
    621                 do {
    622                     strstart++;
    623                     INSERT_STRING(strstart, hash_head);
    624                     /* strstart never exceeds WSIZE-MAX_MATCH, so there are
    625                      * always MIN_MATCH bytes ahead. If lookahead < MIN_MATCH
    626                      * these bytes are garbage, but it does not matter since
    627                      * the next lookahead bytes will be emitted as literals.
    628                      */
    629                 } while (--match_length != 0);
    630                 strstart++;
    631             } else {
    632                 strstart += match_length;
    633                 match_length = 0;
    634                 ins_h = window[strstart];
    635                 UPDATE_HASH(ins_h, window[strstart+1]);
    636 #if MIN_MATCH != 3
    637                 Call UPDATE_HASH() MIN_MATCH-3 more times
    638 #endif
    639             }
    640         } else {
    641             /* No match, output a literal byte */
    642             Tracevv((stderr,"%c",window[strstart]));
    643             flush = ct_tally (0, window[strstart]);
    644             lookahead--;
    645             strstart++;
    646         }
    647         if (flush) FLUSH_BLOCK(0), block_start = strstart;
    648 
     1520local block_state deflate_fast(s, flush)
     1521    deflate_state *s;
     1522    int flush;
     1523{
     1524    IPos hash_head;       /* head of the hash chain */
     1525    int bflush;           /* set if current block must be flushed */
     1526
     1527    for (;;) {
    6491528        /* Make sure that we always have enough lookahead, except
    6501529         * at the end of the input file. We need MAX_MATCH bytes
     
    6521531         * string following the next match.
    6531532         */
    654         while (lookahead < MIN_LOOKAHEAD && !eofile) fill_window();
    655 
    656     }
    657     return FLUSH_BLOCK(1); /* eof */
    658 }
    659 
     1533        if (s->lookahead < MIN_LOOKAHEAD) {
     1534            fill_window(s);
     1535            if (s->lookahead < MIN_LOOKAHEAD && flush == Z_NO_FLUSH) {
     1536                return need_more;
     1537            }
     1538            if (s->lookahead == 0) break; /* flush the current block */
     1539        }
     1540
     1541        /* Insert the string window[strstart .. strstart+2] in the
     1542         * dictionary, and set hash_head to the head of the hash chain:
     1543         */
     1544        hash_head = NIL;
     1545        if (s->lookahead >= MIN_MATCH) {
     1546            INSERT_STRING(s, s->strstart, hash_head);
     1547        }
     1548
     1549        /* Find the longest match, discarding those <= prev_length.
     1550         * At this point we have always match_length < MIN_MATCH
     1551         */
     1552        if (hash_head != NIL && s->strstart - hash_head <= MAX_DIST(s)) {
     1553            /* To simplify the code, we prevent matches with the string
     1554             * of window index 0 (in particular we have to avoid a match
     1555             * of the string with itself at the start of the input file).
     1556             */
     1557            s->match_length = longest_match (s, hash_head);
     1558            /* longest_match() sets match_start */
     1559        }
     1560        if (s->match_length >= MIN_MATCH) {
     1561            check_match(s, s->strstart, s->match_start, s->match_length);
     1562
     1563            _tr_tally_dist(s, s->strstart - s->match_start,
     1564                           s->match_length - MIN_MATCH, bflush);
     1565
     1566            s->lookahead -= s->match_length;
     1567
     1568            /* Insert new strings in the hash table only if the match length
     1569             * is not too large. This saves time but degrades compression.
     1570             */
     1571#ifndef FASTEST
     1572            if (s->match_length <= s->max_insert_length &&
     1573                s->lookahead >= MIN_MATCH) {
     1574                s->match_length--; /* string at strstart already in table */
     1575                do {
     1576                    s->strstart++;
     1577                    INSERT_STRING(s, s->strstart, hash_head);
     1578                    /* strstart never exceeds WSIZE-MAX_MATCH, so there are
     1579                     * always MIN_MATCH bytes ahead.
     1580                     */
     1581                } while (--s->match_length != 0);
     1582                s->strstart++;
     1583            } else
     1584#endif
     1585            {
     1586                s->strstart += s->match_length;
     1587                s->match_length = 0;
     1588                s->ins_h = s->window[s->strstart];
     1589                UPDATE_HASH(s, s->ins_h, s->window[s->strstart+1]);
     1590#if MIN_MATCH != 3
     1591                Call UPDATE_HASH() MIN_MATCH-3 more times
     1592#endif
     1593                /* If lookahead < MIN_MATCH, ins_h is garbage, but it does not
     1594                 * matter since it will be recomputed at next deflate call.
     1595                 */
     1596            }
     1597        } else {
     1598            /* No match, output a literal byte */
     1599            Tracevv((stderr,"%c", s->window[s->strstart]));
     1600            _tr_tally_lit (s, s->window[s->strstart], bflush);
     1601            s->lookahead--;
     1602            s->strstart++;
     1603        }
     1604        if (bflush) FLUSH_BLOCK(s, 0);
     1605    }
     1606    FLUSH_BLOCK(s, flush == Z_FINISH);
     1607    return flush == Z_FINISH ? finish_done : block_done;
     1608}
     1609
     1610#ifndef FASTEST
    6601611/* ===========================================================================
    6611612 * Same as above, but achieves better compression. We use a lazy
     
    6631614 * no better match at the next window position.
    6641615 */
    665 ulg deflate()
     1616local block_state deflate_slow(s, flush)
     1617    deflate_state *s;
     1618    int flush;
    6661619{
    6671620    IPos hash_head;          /* head of hash chain */
    668     IPos prev_match;         /* previous match */
    669     int flush;               /* set if current block must be flushed */
    670     int match_available = 0; /* set if previous match exists */
    671     register unsigned match_length = MIN_MATCH-1; /* length of best match */
    672 #ifdef DEBUG
    673     extern long isize;        /* byte length of input file, for debug only */
    674 #endif
    675 
    676     if (compr_level <= 3) return deflate_fast(); /* optimized for speed */
     1621    int bflush;              /* set if current block must be flushed */
    6771622
    6781623    /* Process the input block. */
    679     while (lookahead != 0) {
    680         /* Insert the string window[strstart .. strstart+2] in the
    681          * dictionary, and set hash_head to the head of the hash chain:
    682          */
    683         INSERT_STRING(strstart, hash_head);
    684 
    685         /* Find the longest match, discarding those <= prev_length.
    686          */
    687         prev_length = match_length, prev_match = match_start;
    688         match_length = MIN_MATCH-1;
    689 
    690         if (hash_head != NIL && prev_length < max_lazy_match &&
    691             strstart - hash_head <= MAX_DIST) {
    692             /* To simplify the code, we prevent matches with the string
    693              * of window index 0 (in particular we have to avoid a match
    694              * of the string with itself at the start of the input file).
    695              */
    696             match_length = longest_match (hash_head);
    697             /* longest_match() sets match_start */
    698             if (match_length > lookahead) match_length = lookahead;
    699 
    700             /* Ignore a length 3 match if it is too distant: */
    701             if (match_length == MIN_MATCH && strstart-match_start > TOO_FAR){
    702                 /* If prev_match is also MIN_MATCH, match_start is garbage
    703                  * but we will ignore the current match anyway.
    704                  */
    705                 match_length--;
    706             }
    707         }
    708         /* If there was a match at the previous step and the current
    709          * match is not better, output the previous match:
    710          */
    711         if (prev_length >= MIN_MATCH && match_length <= prev_length) {
    712 
    713             check_match(strstart-1, prev_match, prev_length);
    714 
    715             flush = ct_tally(strstart-1-prev_match, prev_length - MIN_MATCH);
    716 
    717             /* Insert in hash table all strings up to the end of the match.
    718              * strstart-1 and strstart are already inserted.
    719              */
    720             lookahead -= prev_length-1;
    721             prev_length -= 2;
    722             do {
    723                 strstart++;
    724                 INSERT_STRING(strstart, hash_head);
    725                 /* strstart never exceeds WSIZE-MAX_MATCH, so there are
    726                  * always MIN_MATCH bytes ahead. If lookahead < MIN_MATCH
    727                  * these bytes are garbage, but it does not matter since the
    728                  * next lookahead bytes will always be emitted as literals.
    729                  */
    730             } while (--prev_length != 0);
    731             match_available = 0;
    732             match_length = MIN_MATCH-1;
    733             strstart++;
    734             if (flush) FLUSH_BLOCK(0), block_start = strstart;
    735 
    736         } else if (match_available) {
    737             /* If there was no match at the previous position, output a
    738              * single literal. If there was a match but the current match
    739              * is longer, truncate the previous match to a single literal.
    740              */
    741             Tracevv((stderr,"%c",window[strstart-1]));
    742             if (ct_tally (0, window[strstart-1])) {
    743                 FLUSH_BLOCK(0), block_start = strstart;
    744             }
    745             strstart++;
    746             lookahead--;
    747         } else {
    748             /* There is no previous match to compare with, wait for
    749              * the next step to decide.
    750              */
    751             match_available = 1;
    752             strstart++;
    753             lookahead--;
    754         }
    755         Assert (strstart <= isize && lookahead <= isize, "a bit too far");
    756 
     1624    for (;;) {
    7571625        /* Make sure that we always have enough lookahead, except
    7581626         * at the end of the input file. We need MAX_MATCH bytes
     
    7601628         * string following the next match.
    7611629         */
    762         while (lookahead < MIN_LOOKAHEAD && !eofile) fill_window();
    763     }
    764     if (match_available) ct_tally (0, window[strstart-1]);
    765 
    766     return FLUSH_BLOCK(1); /* eof */
    767 }
     1630        if (s->lookahead < MIN_LOOKAHEAD) {
     1631            fill_window(s);
     1632            if (s->lookahead < MIN_LOOKAHEAD && flush == Z_NO_FLUSH) {
     1633                return need_more;
     1634            }
     1635            if (s->lookahead == 0) break; /* flush the current block */
     1636        }
     1637
     1638        /* Insert the string window[strstart .. strstart+2] in the
     1639         * dictionary, and set hash_head to the head of the hash chain:
     1640         */
     1641        hash_head = NIL;
     1642        if (s->lookahead >= MIN_MATCH) {
     1643            INSERT_STRING(s, s->strstart, hash_head);
     1644        }
     1645
     1646        /* Find the longest match, discarding those <= prev_length.
     1647         */
     1648        s->prev_length = s->match_length, s->prev_match = s->match_start;
     1649        s->match_length = MIN_MATCH-1;
     1650
     1651        if (hash_head != NIL && s->prev_length < s->max_lazy_match &&
     1652            s->strstart - hash_head <= MAX_DIST(s)) {
     1653            /* To simplify the code, we prevent matches with the string
     1654             * of window index 0 (in particular we have to avoid a match
     1655             * of the string with itself at the start of the input file).
     1656             */
     1657            s->match_length = longest_match (s, hash_head);
     1658            /* longest_match() sets match_start */
     1659
     1660            if (s->match_length <= 5 && (s->strategy == Z_FILTERED
     1661#if TOO_FAR <= 32767
     1662                || (s->match_length == MIN_MATCH &&
     1663                    s->strstart - s->match_start > TOO_FAR)
     1664#endif
     1665                )) {
     1666
     1667                /* If prev_match is also MIN_MATCH, match_start is garbage
     1668                 * but we will ignore the current match anyway.
     1669                 */
     1670                s->match_length = MIN_MATCH-1;
     1671            }
     1672        }
     1673        /* If there was a match at the previous step and the current
     1674         * match is not better, output the previous match:
     1675         */
     1676        if (s->prev_length >= MIN_MATCH && s->match_length <= s->prev_length) {
     1677            uInt max_insert = s->strstart + s->lookahead - MIN_MATCH;
     1678            /* Do not insert strings in hash table beyond this. */
     1679
     1680            check_match(s, s->strstart-1, s->prev_match, s->prev_length);
     1681
     1682            _tr_tally_dist(s, s->strstart -1 - s->prev_match,
     1683                           s->prev_length - MIN_MATCH, bflush);
     1684
     1685            /* Insert in hash table all strings up to the end of the match.
     1686             * strstart-1 and strstart are already inserted. If there is not
     1687             * enough lookahead, the last two strings are not inserted in
     1688             * the hash table.
     1689             */
     1690            s->lookahead -= s->prev_length-1;
     1691            s->prev_length -= 2;
     1692            do {
     1693                if (++s->strstart <= max_insert) {
     1694                    INSERT_STRING(s, s->strstart, hash_head);
     1695                }
     1696            } while (--s->prev_length != 0);
     1697            s->match_available = 0;
     1698            s->match_length = MIN_MATCH-1;
     1699            s->strstart++;
     1700
     1701            if (bflush) FLUSH_BLOCK(s, 0);
     1702
     1703        } else if (s->match_available) {
     1704            /* If there was no match at the previous position, output a
     1705             * single literal. If there was a match but the current match
     1706             * is longer, truncate the previous match to a single literal.
     1707             */
     1708            Tracevv((stderr,"%c", s->window[s->strstart-1]));
     1709            _tr_tally_lit(s, s->window[s->strstart-1], bflush);
     1710            if (bflush) {
     1711                FLUSH_BLOCK_ONLY(s, 0);
     1712            }
     1713            s->strstart++;
     1714            s->lookahead--;
     1715            if (s->strm->avail_out == 0) return need_more;
     1716        } else {
     1717            /* There is no previous match to compare with, wait for
     1718             * the next step to decide.
     1719             */
     1720            s->match_available = 1;
     1721            s->strstart++;
     1722            s->lookahead--;
     1723        }
     1724    }
     1725    Assert (flush != Z_NO_FLUSH, "no flush?");
     1726    if (s->match_available) {
     1727        Tracevv((stderr,"%c", s->window[s->strstart-1]));
     1728        _tr_tally_lit(s, s->window[s->strstart-1], bflush);
     1729        s->match_available = 0;
     1730    }
     1731    FLUSH_BLOCK(s, flush == Z_FINISH);
     1732    return flush == Z_FINISH ? finish_done : block_done;
     1733}
     1734#endif /* FASTEST */
     1735
     1736/* ===========================================================================
     1737 * For Z_RLE, simply look for runs of bytes, generate matches only of distance
     1738 * one.  Do not maintain a hash table.  (It will be regenerated if this run of
     1739 * deflate switches away from Z_RLE.)
     1740 */
     1741local block_state deflate_rle(s, flush)
     1742    deflate_state *s;
     1743    int flush;
     1744{
     1745    int bflush;             /* set if current block must be flushed */
     1746    uInt prev;              /* byte at distance one to match */
     1747    Bytef *scan, *strend;   /* scan goes up to strend for length of run */
     1748
     1749    for (;;) {
     1750        /* Make sure that we always have enough lookahead, except
     1751         * at the end of the input file. We need MAX_MATCH bytes
     1752         * for the longest encodable run.
     1753         */
     1754        if (s->lookahead < MAX_MATCH) {
     1755            fill_window(s);
     1756            if (s->lookahead < MAX_MATCH && flush == Z_NO_FLUSH) {
     1757                return need_more;
     1758            }
     1759            if (s->lookahead == 0) break; /* flush the current block */
     1760        }
     1761
     1762        /* See how many times the previous byte repeats */
     1763        s->match_length = 0;
     1764        if (s->lookahead >= MIN_MATCH && s->strstart > 0) {
     1765            scan = s->window + s->strstart - 1;
     1766            prev = *scan;
     1767            if (prev == *++scan && prev == *++scan && prev == *++scan) {
     1768                strend = s->window + s->strstart + MAX_MATCH;
     1769                do {
     1770                } while (prev == *++scan && prev == *++scan &&
     1771                         prev == *++scan && prev == *++scan &&
     1772                         prev == *++scan && prev == *++scan &&
     1773                         prev == *++scan && prev == *++scan &&
     1774                         scan < strend);
     1775                s->match_length = MAX_MATCH - (int)(strend - scan);
     1776                if (s->match_length > s->lookahead)
     1777                    s->match_length = s->lookahead;
     1778            }
     1779        }
     1780
     1781        /* Emit match if have run of MIN_MATCH or longer, else emit literal */
     1782        if (s->match_length >= MIN_MATCH) {
     1783            check_match(s, s->strstart, s->strstart - 1, s->match_length);
     1784
     1785            _tr_tally_dist(s, 1, s->match_length - MIN_MATCH, bflush);
     1786
     1787            s->lookahead -= s->match_length;
     1788            s->strstart += s->match_length;
     1789            s->match_length = 0;
     1790        } else {
     1791            /* No match, output a literal byte */
     1792            Tracevv((stderr,"%c", s->window[s->strstart]));
     1793            _tr_tally_lit (s, s->window[s->strstart], bflush);
     1794            s->lookahead--;
     1795            s->strstart++;
     1796        }
     1797        if (bflush) FLUSH_BLOCK(s, 0);
     1798    }
     1799    FLUSH_BLOCK(s, flush == Z_FINISH);
     1800    return flush == Z_FINISH ? finish_done : block_done;
     1801}
     1802
     1803/* ===========================================================================
     1804 * For Z_HUFFMAN_ONLY, do not look for matches.  Do not maintain a hash table.
     1805 * (It will be regenerated if this run of deflate switches away from Huffman.)
     1806 */
     1807local block_state deflate_huff(s, flush)
     1808    deflate_state *s;
     1809    int flush;
     1810{
     1811    int bflush;             /* set if current block must be flushed */
     1812
     1813    for (;;) {
     1814        /* Make sure that we have a literal to write. */
     1815        if (s->lookahead == 0) {
     1816            fill_window(s);
     1817            if (s->lookahead == 0) {
     1818                if (flush == Z_NO_FLUSH)
     1819                    return need_more;
     1820                break;      /* flush the current block */
     1821            }
     1822        }
     1823
     1824        /* Output a literal byte */
     1825        s->match_length = 0;
     1826        Tracevv((stderr,"%c", s->window[s->strstart]));
     1827        _tr_tally_lit (s, s->window[s->strstart], bflush);
     1828        s->lookahead--;
     1829        s->strstart++;
     1830        if (bflush) FLUSH_BLOCK(s, 0);
     1831    }
     1832    FLUSH_BLOCK(s, flush == Z_FINISH);
     1833    return flush == Z_FINISH ? finish_done : block_done;
     1834}
  • forth/wrapper/zip/readme

    r1 r2182  
    44
    55The files in this directory were derived from the source code
    6 for gzip 1.2.4 as follows:
     6for zlib 1.2.5, released 19 April 2010 by Jean-loup Gailly and
     7Mark Adler (www.zlib.net). The README for zlib, including
     8copyright and licensing information, is appended below the heading
     9"ZLIB DATA COMPRESSION LIBRARY."
    710
    8         deflate.c       From gzip deflate.c, essentially verbatim
    9         trees.c         From gzip trees.c, essentially verbatim
    10         bits.c          From gzip bits.c, essentially verbatim
    11         gzip.h          From gzip gzip.h, essentially verbatim
     11This directory contains a subset of the zlib code necessary only to compress
     12a source memory region to a destination memory region, i.e. the compress()
     13entry point. The files used are unchanged from the zlib distribution.
    1214
    13         zipmem.c        From gzip gzip.c and zip.c, but both files
    14                         were gutted and only a small fraction of
    15                         the code was extracted to form zipmem.c.
     15This directory also contains the source for a memory-to-memory inflater.
     16The inflater is derived from an older (1993) version of the GZIP library and
     17was also written by Mark Adler. The inflater has been modified to run
     18as a pure text routine, i.e. from ROM. This routine is compiled and
     19embedded both in the wrapper and in the actual ROM (e.g. for uncompressing
     20drop-in packages).
    1621
    17         util.c          From gzip util.c.  About half or more of the
    18                         file was discarded, and the rest was barely
    19                         touched.
     22All the software in this library is the copyrighted intellectual property of
     23Jean-loup Gailly and Mark Adler, and is unencumbered by software licenses
     24or patents. See below.
    2025
    21         tailor.h        From gzip tailor.h, but massively gutted,
    22                         leaving only a few defines.
     26ZLIB DATA COMPRESSION LIBRARY
    2327
    24 The "essentially verbatim" files, to the extent that they were modified
    25 at all, were modified by commenting-out irrelevant sections of the
    26 files with "#ifdef FWnotdef ... #endif".
     28zlib 1.2.5 is a general purpose data compression library.  All the code is
     29thread safe.  The data format used by the zlib library is described by RFCs
     30(Request for Comments) 1950 to 1952 in the files
     31http://www.ietf.org/rfc/rfc1950.txt (zlib format), rfc1951.txt (deflate format)
     32and rfc1952.txt (gzip format).
    2733
    28 A lot of the gzip code is concerned with handling files and their
    29 modes and attributes, command line arguments, decompressing, and
    30 handling multiple compression methods.  The code in this directory
    31 is concerned solely with the problem of compressing from memory to
    32 memory, using only the ZIP "deflate" method.
     34All functions of the compression library are documented in the file zlib.h
     35(volunteer to write man pages welcome, contact zlib@gzip.org).  A usage example
     36of the library is given in the file example.c which also tests that the library
     37is working correctly.  Another example is given in the file minigzip.c.  The
     38compression library itself is composed of all source files except example.c and
     39minigzip.c.
     40
     41To compile all files and run the test program, follow the instructions given at
     42the top of Makefile.in.  In short "./configure; make test", and if that goes
     43well, "make install" should work for most flavors of Unix.  For Windows, use one
     44of the special makefiles in win32/ or contrib/vstudio/ .  For VMS, use
     45make_vms.com.
     46
     47Questions about zlib should be sent to <zlib@gzip.org>, or to Gilles Vollant
     48<info@winimage.com> for the Windows DLL version.  The zlib home page is
     49http://zlib.net/ .  Before reporting a problem, please check this site to
     50verify that you have the latest version of zlib; otherwise get the latest
     51version and check whether the problem still exists or not.
     52
     53PLEASE read the zlib FAQ http://zlib.net/zlib_faq.html before asking for help.
     54
     55Mark Nelson <markn@ieee.org> wrote an article about zlib for the Jan.  1997
     56issue of Dr.  Dobb's Journal; a copy of the article is available at
     57http://marknelson.us/1997/01/01/zlib-engine/ .
     58
     59The changes made in version 1.2.5 are documented in the file ChangeLog.
     60
     61Unsupported third party contributions are provided in directory contrib/ .
     62
     63zlib is available in Java using the java.util.zip package, documented at
     64http://java.sun.com/developer/technicalArticles/Programming/compression/ .
     65
     66A Perl interface to zlib written by Paul Marquess <pmqs@cpan.org> is available
     67at CPAN (Comprehensive Perl Archive Network) sites, including
     68http://search.cpan.org/~pmqs/IO-Compress-Zlib/ .
     69
     70A Python interface to zlib written by A.M. Kuchling <amk@amk.ca> is
     71available in Python 1.5 and later versions, see
     72http://www.python.org/doc/lib/module-zlib.html .
     73
     74zlib is built into tcl: http://wiki.tcl.tk/4610 .
     75
     76An experimental package to read and write files in .zip format, written on top
     77of zlib by Gilles Vollant <info@winimage.com>, is available in the
     78contrib/minizip directory of zlib.
     79
     80
     81Notes for some targets:
     82
     83- For Windows DLL versions, please see win32/DLL_FAQ.txt
     84
     85- For 64-bit Irix, deflate.c must be compiled without any optimization. With
     86  -O, one libpng test fails. The test works in 32 bit mode (with the -n32
     87  compiler flag). The compiler bug has been reported to SGI.
     88
     89- zlib doesn't work with gcc 2.6.3 on a DEC 3000/300LX under OSF/1 2.1 it works
     90  when compiled with cc.
     91
     92- On Digital Unix 4.0D (formely OSF/1) on AlphaServer, the cc option -std1 is
     93  necessary to get gzprintf working correctly. This is done by configure.
     94
     95- zlib doesn't work on HP-UX 9.05 with some versions of /bin/cc. It works with
     96  other compilers. Use "make test" to check your compiler.
     97
     98- gzdopen is not supported on RISCOS or BEOS.
     99
     100- For PalmOs, see http://palmzlib.sourceforge.net/
     101
     102
     103Acknowledgments:
     104
     105  The deflate format used by zlib was defined by Phil Katz.  The deflate and
     106  zlib specifications were written by L.  Peter Deutsch.  Thanks to all the
     107  people who reported problems and suggested various improvements in zlib; they
     108  are too numerous to cite here.
     109
     110Copyright notice:
     111
     112 (C) 1995-2010 Jean-loup Gailly and Mark Adler
     113
     114  This software is provided 'as-is', without any express or implied
     115  warranty.  In no event will the authors be held liable for any damages
     116  arising from the use of this software.
     117
     118  Permission is granted to anyone to use this software for any purpose,
     119  including commercial applications, and to alter it and redistribute it
     120  freely, subject to the following restrictions:
     121
     122  1. The origin of this software must not be misrepresented; you must not
     123     claim that you wrote the original software. If you use this software
     124     in a product, an acknowledgment in the product documentation would be
     125     appreciated but is not required.
     126  2. Altered source versions must be plainly marked as such, and must not be
     127     misrepresented as being the original software.
     128  3. This notice may not be removed or altered from any source distribution.
     129
     130  Jean-loup Gailly        Mark Adler
     131  jloup@gzip.org          madler@alumni.caltech.edu
     132
     133If you use the zlib library in a product, we would appreciate *not* receiving
     134lengthy legal documents to sign.  The sources are provided for free but without
     135warranty of any kind.  The library has been entirely written by Jean-loup
     136Gailly and Mark Adler; it does not include third-party code.
     137
     138If you redistribute modified sources, we would appreciate that you include in
     139the file ChangeLog history information documenting your changes.  Please read
     140the FAQ for more information on the distribution of modified source versions.
  • forth/wrapper/zip/trees.c

    r1 r2182  
    11/* trees.c -- output deflated data using Huffman coding
    2  * Copyright (C) 1992-1993 Jean-loup Gailly
    3  * This is free software; you can redistribute it and/or modify it under the
    4  * terms of the GNU General Public License, see the file COPYING.
     2 * Copyright (C) 1995-2010 Jean-loup Gailly
     3 * detect_data_type() function provided freely by Cosmin Truta, 2006
     4 * For conditions of distribution and use, see copyright notice in zlib.h
    55 */
    66
    77/*
    8  *  PURPOSE
     8 *  ALGORITHM
    99 *
    10  *      Encode various sets of source values using variable-length
    11  *      binary code trees.
    12  *
    13  *  DISCUSSION
    14  *
    15  *      The PKZIP "deflation" process uses several Huffman trees. The more
     10 *      The "deflation" process uses several Huffman trees. The more
    1611 *      common source values are represented by shorter bit sequences.
    1712 *
    18  *      Each code tree is stored in the ZIP file in a compressed form
    19  *      which is itself a Huffman encoding of the lengths of
    20  *      all the code strings (in ascending order by source values).
    21  *      The actual code strings are reconstructed from the lengths in
    22  *      the UNZIP process, as described in the "application note"
    23  *      (APPNOTE.TXT) distributed as part of PKWARE's PKZIP program.
     13 *      Each code tree is stored in a compressed form which is itself
     14 * a Huffman encoding of the lengths of all the code strings (in
     15 * ascending order by source values).  The actual code strings are
     16 * reconstructed from the lengths in the inflate process, as described
     17 * in the deflate specification.
    2418 *
    2519 *  REFERENCES
    2620 *
    27  *      Lynch, Thomas J.
    28  *          Data Compression:  Techniques and Applications, pp. 53-55.
    29  *          Lifetime Learning Publications, 1985.  ISBN 0-534-03418-7.
     21 *      Deutsch, L.P.,"'Deflate' Compressed Data Format Specification".
     22 *      Available in ftp.uu.net:/pub/archiving/zip/doc/deflate-1.1.doc
    3023 *
    3124 *      Storer, James A.
     
    3629 *          Algorithms, p290.
    3730 *          Addison-Wesley, 1983. ISBN 0-201-06672-6.
    38  *
    39  *  INTERFACE
    40  *
    41  *      void ct_init (ush *attr, int *methodp)
    42  *          Allocate the match buffer, initialize the various tables and save
    43  *          the location of the internal file attribute (ascii/binary) and
    44  *          method (DEFLATE/STORE)
    45  *
    46  *      void ct_tally (int dist, int lc);
    47  *          Save the match info and tally the frequency counts.
    48  *
    49  *      long flush_block (char *buf, ulg stored_len, int eof)
    50  *          Determine the best encoding for the current block: dynamic trees,
    51  *          static trees or store, and output the encoded block to the zip
    52  *          file. Returns the total compressed length for the file so far.
    53  *
    54  */
    55 
    56 #include <ctype.h>
    57 
    58 #include "tailor.h"
    59 #include "gzip.h"
    60 
    61 #ifdef RCSID
    62 static char rcsid[] = "$Id: trees.c,v 1.1 1997/01/08 08:30:21 wmb Exp $";
     31 */
     32
     33/* @(#) $Id$ */
     34
     35/* #define GEN_TREES_H */
     36
     37#include "deflate.h"
     38
     39#ifdef DEBUG
     40#  include <ctype.h>
    6341#endif
    6442
     
    6644 * Constants
    6745 */
    68 
    69 #define MAX_BITS 15
    70 /* All codes must not exceed MAX_BITS bits */
    7146
    7247#define MAX_BL_BITS 7
    7348/* Bit length codes must not exceed MAX_BL_BITS bits */
    7449
    75 #define LENGTH_CODES 29
    76 /* number of length codes, not counting the special END_BLOCK code */
    77 
    78 #define LITERALS  256
    79 /* number of literal bytes 0..255 */
    80 
    8150#define END_BLOCK 256
    8251/* end of block literal code */
    8352
    84 #define L_CODES (LITERALS+1+LENGTH_CODES)
    85 /* number of Literal or Length codes, including the END_BLOCK code */
    86 
    87 #define D_CODES   30
    88 /* number of distance codes */
    89 
    90 #define BL_CODES  19
    91 /* number of codes used to transfer the bit lengths */
    92 
    93 
    94 local int near extra_lbits[LENGTH_CODES] /* extra bits for each length code */
    95    = {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};
    96 
    97 local int near extra_dbits[D_CODES] /* extra bits for each distance code */
    98    = {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};
    99 
    100 local int near extra_blbits[BL_CODES]/* extra bits for each bit length code */
    101    = {0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,2,3,7};
    102 
    103 #define STORED_BLOCK 0
    104 #define STATIC_TREES 1
    105 #define DYN_TREES    2
    106 /* The three kinds of block type */
    107 
    108 #ifndef LIT_BUFSIZE
    109 #  ifdef SMALL_MEM
    110 #    define LIT_BUFSIZE  0x2000
    111 #  else
    112 #  ifdef MEDIUM_MEM
    113 #    define LIT_BUFSIZE  0x4000
    114 #  else
    115 #    define LIT_BUFSIZE  0x8000
    116 #  endif
    117 #  endif
    118 #endif
    119 #ifndef DIST_BUFSIZE
    120 #  define DIST_BUFSIZE  LIT_BUFSIZE
    121 #endif
    122 /* Sizes of match buffers for literals/lengths and distances.  There are
    123  * 4 reasons for limiting LIT_BUFSIZE to 64K:
    124  *   - frequencies can be kept in 16 bit counters
    125  *   - if compression is not successful for the first block, all input data is
    126  *     still in the window so we can still emit a stored block even when input
    127  *     comes from standard input.  (This can also be done for all blocks if
    128  *     LIT_BUFSIZE is not greater than 32K.)
    129  *   - if compression is not successful for a file smaller than 64K, we can
    130  *     even emit a stored file instead of a stored block (saving 5 bytes).
    131  *   - creating new Huffman trees less frequently may not provide fast
    132  *     adaptation to changes in the input data statistics. (Take for
    133  *     example a binary file with poorly compressible code followed by
    134  *     a highly compressible string table.) Smaller buffer sizes give
    135  *     fast adaptation but have of course the overhead of transmitting trees
    136  *     more frequently.
    137  *   - I can't count above 4
    138  * The current code is general and allows DIST_BUFSIZE < LIT_BUFSIZE (to save
    139  * memory at the expense of compression). Some optimizations would be possible
    140  * if we rely on DIST_BUFSIZE == LIT_BUFSIZE.
    141  */
    142 #if LIT_BUFSIZE > INBUFSIZ
    143     error cannot overlay l_buf and inbuf
    144 #endif
    145 
    14653#define REP_3_6      16
    14754/* repeat previous bit length 3-6 times (2 bits of repeat count) */
     
    15360/* repeat a zero length 11-138 times  (7 bits of repeat count) */
    15461
    155 /* ===========================================================================
    156  * Local data
    157  */
    158 
    159 /* Data structure describing a single value and its code string. */
    160 typedef struct ct_data {
    161     union {
    162         ush  freq;       /* frequency count */
    163         ush  code;       /* bit string */
    164     } fc;
    165     union {
    166         ush  dad;        /* father node in Huffman tree */
    167         ush  len;        /* length of bit string */
    168     } dl;
    169 } ct_data;
    170 
    171 #define Freq fc.freq
    172 #define Code fc.code
    173 #define Dad  dl.dad
    174 #define Len  dl.len
    175 
    176 #define HEAP_SIZE (2*L_CODES+1)
    177 /* maximum heap size */
    178 
    179 local ct_data near dyn_ltree[HEAP_SIZE];   /* literal and length tree */
    180 local ct_data near dyn_dtree[2*D_CODES+1]; /* distance tree */
    181 
    182 local ct_data near static_ltree[L_CODES+2];
     62local const int extra_lbits[LENGTH_CODES] /* extra bits for each length code */
     63   = {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};
     64
     65local const int extra_dbits[D_CODES] /* extra bits for each distance code */
     66   = {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};
     67
     68local const int extra_blbits[BL_CODES]/* extra bits for each bit length code */
     69   = {0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,2,3,7};
     70
     71local const uch bl_order[BL_CODES]
     72   = {16,17,18,0,8,7,9,6,10,5,11,4,12,3,13,2,14,1,15};
     73/* The lengths of the bit length codes are sent in order of decreasing
     74 * probability, to avoid transmitting the lengths for unused bit length codes.
     75 */
     76
     77#define Buf_size (8 * 2*sizeof(char))
     78/* Number of bits used within bi_buf. (bi_buf might be implemented on
     79 * more than 16 bits on some systems.)
     80 */
     81
     82/* ===========================================================================
     83 * Local data. These are initialized only once.
     84 */
     85
     86#define DIST_CODE_LEN  512 /* see definition of array dist_code below */
     87
     88#if defined(GEN_TREES_H) || !defined(STDC)
     89/* non ANSI compilers may not accept trees.h */
     90
     91local ct_data static_ltree[L_CODES+2];
    18392/* The static literal tree. Since the bit lengths are imposed, there is no
    18493 * need for the L_CODES extra codes used during heap construction. However
    185  * The codes 286 and 287 are needed to build a canonical tree (see ct_init
     94 * The codes 286 and 287 are needed to build a canonical tree (see _tr_init
    18695 * below).
    18796 */
    18897
    189 local ct_data near static_dtree[D_CODES];
     98local ct_data static_dtree[D_CODES];
    19099/* The static distance tree. (Actually a trivial tree since all codes use
    191100 * 5 bits.)
    192101 */
    193102
    194 local ct_data near bl_tree[2*BL_CODES+1];
    195 /* Huffman tree for the bit lengths */
    196 
    197 typedef struct tree_desc {
    198     ct_data near *dyn_tree;      /* the dynamic tree */
    199     ct_data near *static_tree;   /* corresponding static tree or NULL */
    200     int     near *extra_bits;    /* extra bits for each code or NULL */
     103uch _dist_code[DIST_CODE_LEN];
     104/* Distance codes. The first 256 values correspond to the distances
     105 * 3 .. 258, the last 256 values correspond to the top 8 bits of
     106 * the 15 bit distances.
     107 */
     108
     109uch _length_code[MAX_MATCH-MIN_MATCH+1];
     110/* length code for each normalized match length (0 == MIN_MATCH) */
     111
     112local int base_length[LENGTH_CODES];
     113/* First normalized length for each code (0 = MIN_MATCH) */
     114
     115local int base_dist[D_CODES];
     116/* First normalized distance for each code (0 = distance of 1) */
     117
     118#else
     119#  include "trees.h"
     120#endif /* GEN_TREES_H */
     121
     122struct static_tree_desc_s {
     123    const ct_data *static_tree;  /* static tree or NULL */
     124    const intf *extra_bits;      /* extra bits for each code or NULL */
    201125    int     extra_base;          /* base index for extra_bits */
    202126    int     elems;               /* max number of elements in the tree */
    203127    int     max_length;          /* max bit length for the codes */
    204     int     max_code;            /* largest code with non zero frequency */
    205 } tree_desc;
    206 
    207 local tree_desc near l_desc =
    208 {dyn_ltree, static_ltree, extra_lbits, LITERALS+1, L_CODES, MAX_BITS, 0};
    209 
    210 local tree_desc near d_desc =
    211 {dyn_dtree, static_dtree, extra_dbits, 0,          D_CODES, MAX_BITS, 0};
    212 
    213 local tree_desc near bl_desc =
    214 {bl_tree, (ct_data near *)0, extra_blbits, 0,      BL_CODES, MAX_BL_BITS, 0};
    215 
    216 
    217 local ush near bl_count[MAX_BITS+1];
    218 /* number of codes at each bit length for an optimal tree */
    219 
    220 local uch near bl_order[BL_CODES]
    221    = {16,17,18,0,8,7,9,6,10,5,11,4,12,3,13,2,14,1,15};
    222 /* The lengths of the bit length codes are sent in order of decreasing
    223  * probability, to avoid transmitting the lengths for unused bit length codes.
    224  */
    225 
    226 local int near heap[2*L_CODES+1]; /* heap used to build the Huffman trees */
    227 local int heap_len;               /* number of elements in the heap */
    228 local int heap_max;               /* element of largest frequency */
    229 /* The sons of heap[n] are heap[2*n] and heap[2*n+1]. heap[0] is not used.
    230  * The same heap array is used to build all trees.
    231  */
    232 
    233 local uch near depth[2*L_CODES+1];
    234 /* Depth of each subtree used as tie breaker for trees of equal frequency */
    235 
    236 local uch length_code[MAX_MATCH-MIN_MATCH+1];
    237 /* length code for each normalized match length (0 == MIN_MATCH) */
    238 
    239 local uch dist_code[512];
    240 /* distance codes. The first 256 values correspond to the distances
    241  * 3 .. 258, the last 256 values correspond to the top 8 bits of
    242  * the 15 bit distances.
    243  */
    244 
    245 local int near base_length[LENGTH_CODES];
    246 /* First normalized length for each code (0 = MIN_MATCH) */
    247 
    248 local int near base_dist[D_CODES];
    249 /* First normalized distance for each code (0 = distance of 1) */
    250 
    251 #define l_buf inbuf
    252 /* DECLARE(uch, l_buf, LIT_BUFSIZE);  buffer for literals or lengths */
    253 
    254 /* DECLARE(ush, d_buf, DIST_BUFSIZE); buffer for distances */
    255 
    256 local uch near flag_buf[(LIT_BUFSIZE/8)];
    257 /* flag_buf is a bit array distinguishing literals from lengths in
    258  * l_buf, thus indicating the presence or absence of a distance.
    259  */
    260 
    261 local unsigned last_lit;    /* running index in l_buf */
    262 local unsigned last_dist;   /* running index in d_buf */
    263 local unsigned last_flags;  /* running index in flag_buf */
    264 local uch flags;            /* current flags not yet saved in flag_buf */
    265 local uch flag_bit;         /* current bit used in flags */
    266 /* bits are filled in flags starting at bit 0 (least significant).
    267  * Note: these flags are overkill in the current code since we don't
    268  * take advantage of DIST_BUFSIZE == LIT_BUFSIZE.
    269  */
    270 
    271 local ulg opt_len;        /* bit length of current block with optimal trees */
    272 local ulg static_len;     /* bit length of current block with static trees */
    273 
    274 local ulg compressed_len; /* total bit length of compressed file */
    275 
    276 local ulg input_len;      /* total byte length of input file */
    277 /* input_len is for debugging only since we can get it by other means. */
    278 
    279 ush *file_type;        /* pointer to UNKNOWN, BINARY or ASCII */
    280 int *file_method;      /* pointer to DEFLATE or STORE */
    281 
     128};
     129
     130local static_tree_desc  static_l_desc =
     131{static_ltree, extra_lbits, LITERALS+1, L_CODES, MAX_BITS};
     132
     133local static_tree_desc  static_d_desc =
     134{static_dtree, extra_dbits, 0,          D_CODES, MAX_BITS};
     135
     136local static_tree_desc  static_bl_desc =
     137{(const ct_data *)0, extra_blbits, 0,   BL_CODES, MAX_BL_BITS};
     138
     139/* ===========================================================================
     140 * Local (static) routines in this file.
     141 */
     142
     143local void tr_static_init OF((void));
     144local void init_block     OF((deflate_state *s));
     145local void pqdownheap     OF((deflate_state *s, ct_data *tree, int k));
     146local void gen_bitlen     OF((deflate_state *s, tree_desc *desc));
     147local void gen_codes      OF((ct_data *tree, int max_code, ushf *bl_count));
     148local void build_tree     OF((deflate_state *s, tree_desc *desc));
     149local void scan_tree      OF((deflate_state *s, ct_data *tree, int max_code));
     150local void send_tree      OF((deflate_state *s, ct_data *tree, int max_code));
     151local int  build_bl_tree  OF((deflate_state *s));
     152local void send_all_trees OF((deflate_state *s, int lcodes, int dcodes,
     153                              int blcodes));
     154local void compress_block OF((deflate_state *s, ct_data *ltree,
     155                              ct_data *dtree));
     156local int  detect_data_type OF((deflate_state *s));
     157local unsigned bi_reverse OF((unsigned value, int length));
     158local void bi_windup      OF((deflate_state *s));
     159local void bi_flush       OF((deflate_state *s));
     160local void copy_block     OF((deflate_state *s, charf *buf, unsigned len,
     161                              int header));
     162
     163#ifdef GEN_TREES_H
     164local void gen_trees_header OF((void));
     165#endif
     166
     167#ifndef DEBUG
     168#  define send_code(s, c, tree) send_bits(s, tree[c].Code, tree[c].Len)
     169   /* Send a code of the given tree. c and tree must not have side effects */
     170
     171#else /* DEBUG */
     172#  define send_code(s, c, tree) \
     173     { if (z_verbose>2) fprintf(stderr,"\ncd %3d ",(c)); \
     174       send_bits(s, tree[c].Code, tree[c].Len); }
     175#endif
     176
     177/* ===========================================================================
     178 * Output a short LSB first on the stream.
     179 * IN assertion: there is enough room in pendingBuf.
     180 */
     181#define put_short(s, w) { \
     182    put_byte(s, (uch)((w) & 0xff)); \
     183    put_byte(s, (uch)((ush)(w) >> 8)); \
     184}
     185
     186/* ===========================================================================
     187 * Send a value on a given number of bits.
     188 * IN assertion: length <= 16 and value fits in length bits.
     189 */
    282190#ifdef DEBUG
    283 extern ulg bits_sent;  /* bit length of the compressed data */
    284 extern long isize;     /* byte length of input file */
    285 #endif
    286 
    287 extern long block_start;       /* window offset of current block */
    288 extern unsigned near strstart; /* window offset of current string */
    289 
    290 /* ===========================================================================
    291  * Local (static) routines in this file.
    292  */
    293 
    294 local void init_block     OF((void));
    295 local void pqdownheap     OF((ct_data near *tree, int k));
    296 local void gen_bitlen     OF((tree_desc near *desc));
    297 local void gen_codes      OF((ct_data near *tree, int max_code));
    298 local void build_tree     OF((tree_desc near *desc));
    299 local void scan_tree      OF((ct_data near *tree, int max_code));
    300 local void send_tree      OF((ct_data near *tree, int max_code));
    301 local int  build_bl_tree  OF((void));
    302 local void send_all_trees OF((int lcodes, int dcodes, int blcodes));
    303 local void compress_block OF((ct_data near *ltree, ct_data near *dtree));
    304 local void set_file_type  OF((void));
    305 
    306 
    307 #ifndef DEBUG
    308 #  define send_code(c, tree) send_bits(tree[c].Code, tree[c].Len)
    309    /* Send a code of the given tree. c and tree must not have side effects */
    310 
    311 #else /* DEBUG */
    312 #  define send_code(c, tree) \
    313      { if (verbose>1) fprintf(stderr,"\ncd %3d ",(c)); \
    314        send_bits(tree[c].Code, tree[c].Len); }
    315 #endif
    316 
    317 #define d_code(dist) \
    318    ((dist) < 256 ? dist_code[dist] : dist_code[256+((dist)>>7)])
    319 /* Mapping from a distance to a distance code. dist is the distance - 1 and
    320  * must not have side effects. dist_code[256] and dist_code[257] are never
    321  * used.
    322  */
    323 
    324 #define MAX(a,b) (a >= b ? a : b)
     191local void send_bits      OF((deflate_state *s, int value, int length));
     192
     193local void send_bits(s, value, length)
     194    deflate_state *s;
     195    int value;  /* value to send */
     196    int length; /* number of bits */
     197{
     198    Tracevv((stderr," l %2d v %4x ", length, value));
     199    Assert(length > 0 && length <= 15, "invalid length");
     200    s->bits_sent += (ulg)length;
     201
     202    /* If not enough room in bi_buf, use (valid) bits from bi_buf and
     203     * (16 - bi_valid) bits from value, leaving (width - (16-bi_valid))
     204     * unused bits in value.
     205     */
     206    if (s->bi_valid > (int)Buf_size - length) {
     207        s->bi_buf |= (ush)value << s->bi_valid;
     208        put_short(s, s->bi_buf);
     209        s->bi_buf = (ush)value >> (Buf_size - s->bi_valid);
     210        s->bi_valid += length - Buf_size;
     211    } else {
     212        s->bi_buf |= (ush)value << s->bi_valid;
     213        s->bi_valid += length;
     214    }
     215}
     216#else /* !DEBUG */
     217
     218#define send_bits(s, value, length) \
     219{ int len = length;\
     220  if (s->bi_valid > (int)Buf_size - len) {\
     221    int val = value;\
     222    s->bi_buf |= (ush)val << s->bi_valid;\
     223    put_short(s, s->bi_buf);\
     224    s->bi_buf = (ush)val >> (Buf_size - s->bi_valid);\
     225    s->bi_valid += len - Buf_size;\
     226  } else {\
     227    s->bi_buf |= (ush)(value) << s->bi_valid;\
     228    s->bi_valid += len;\
     229  }\
     230}
     231#endif /* DEBUG */
     232
     233
    325234/* the arguments must not have side effects */
    326235
    327236/* ===========================================================================
    328  * Allocate the match buffer, initialize the various tables and save the
    329  * location of the internal file attribute (ascii/binary) and method
    330  * (DEFLATE/STORE).
    331  */
    332 void ct_init(attr, methodp)
    333     ush  *attr;   /* pointer to internal file attribute */
    334     int  *methodp; /* pointer to compression method */
    335 {
     237 * Initialize the various 'constant' tables.
     238 */
     239local void tr_static_init()
     240{
     241#if defined(GEN_TREES_H) || !defined(STDC)
     242    static int static_init_done = 0;
    336243    int n;        /* iterates over tree elements */
    337244    int bits;     /* bit counter */
     
    339246    int code;     /* code value */
    340247    int dist;     /* distance index */
    341 
    342     file_type = attr;
    343     file_method = methodp;
    344     compressed_len = input_len = 0L;
    345        
    346     if (static_dtree[0].Len != 0) return; /* ct_init already called */
     248    ush bl_count[MAX_BITS+1];
     249    /* number of codes at each bit length for an optimal tree */
     250
     251    if (static_init_done) return;
     252
     253    /* For some embedded targets, global variables are not initialized: */
     254#ifdef NO_INIT_GLOBAL_POINTERS
     255    static_l_desc.static_tree = static_ltree;
     256    static_l_desc.extra_bits = extra_lbits;
     257    static_d_desc.static_tree = static_dtree;
     258    static_d_desc.extra_bits = extra_dbits;
     259    static_bl_desc.extra_bits = extra_blbits;
     260#endif
    347261
    348262    /* Initialize the mapping length (0..255) -> length code (0..28) */
     
    351265        base_length[code] = length;
    352266        for (n = 0; n < (1<<extra_lbits[code]); n++) {
    353             length_code[length++] = (uch)code;
     267            _length_code[length++] = (uch)code;
    354268        }
    355269    }
    356     Assert (length == 256, "ct_init: length != 256");
     270    Assert (length == 256, "tr_static_init: length != 256");
    357271    /* Note that the length 255 (match length 258) can be represented
    358272     * in two different ways: code 284 + 5 bits or code 285, so we
    359273     * overwrite length_code[255] to use the best encoding:
    360274     */
    361     length_code[length-1] = (uch)code;
     275    _length_code[length-1] = (uch)code;
    362276
    363277    /* Initialize the mapping dist (0..32K) -> dist code (0..29) */
     
    366280        base_dist[code] = dist;
    367281        for (n = 0; n < (1<<extra_dbits[code]); n++) {
    368             dist_code[dist++] = (uch)code;
     282            _dist_code[dist++] = (uch)code;
    369283        }
    370284    }
    371     Assert (dist == 256, "ct_init: dist != 256");
     285    Assert (dist == 256, "tr_static_init: dist != 256");
    372286    dist >>= 7; /* from now on, all distances are divided by 128 */
    373287    for ( ; code < D_CODES; code++) {
    374288        base_dist[code] = dist << 7;
    375289        for (n = 0; n < (1<<(extra_dbits[code]-7)); n++) {
    376             dist_code[256 + dist++] = (uch)code;
     290            _dist_code[256 + dist++] = (uch)code;
    377291        }
    378292    }
    379     Assert (dist == 256, "ct_init: 256+dist != 512");
     293    Assert (dist == 256, "tr_static_init: 256+dist != 512");
    380294
    381295    /* Construct the codes of the static literal tree */
     
    390304     * all ones)
    391305     */
    392     gen_codes((ct_data near *)static_ltree, L_CODES+1);
     306    gen_codes((ct_data *)static_ltree, L_CODES+1, bl_count);
    393307
    394308    /* The static distance tree is trivial: */
    395309    for (n = 0; n < D_CODES; n++) {
    396310        static_dtree[n].Len = 5;
    397         static_dtree[n].Code = bi_reverse(n, 5);
    398     }
     311        static_dtree[n].Code = bi_reverse((unsigned)n, 5);
     312    }
     313    static_init_done = 1;
     314
     315#  ifdef GEN_TREES_H
     316    gen_trees_header();
     317#  endif
     318#endif /* defined(GEN_TREES_H) || !defined(STDC) */
     319}
     320
     321/* ===========================================================================
     322 * Genererate the file trees.h describing the static trees.
     323 */
     324#ifdef GEN_TREES_H
     325#  ifndef DEBUG
     326#    include <stdio.h>
     327#  endif
     328
     329#  define SEPARATOR(i, last, width) \
     330      ((i) == (last)? "\n};\n\n" :    \
     331       ((i) % (width) == (width)-1 ? ",\n" : ", "))
     332
     333void gen_trees_header()
     334{
     335    FILE *header = fopen("trees.h", "w");
     336    int i;
     337
     338    Assert (header != NULL, "Can't open trees.h");
     339    fprintf(header,
     340            "/* header created automatically with -DGEN_TREES_H */\n\n");
     341
     342    fprintf(header, "local const ct_data static_ltree[L_CODES+2] = {\n");
     343    for (i = 0; i < L_CODES+2; i++) {
     344        fprintf(header, "{{%3u},{%3u}}%s", static_ltree[i].Code,
     345                static_ltree[i].Len, SEPARATOR(i, L_CODES+1, 5));
     346    }
     347
     348    fprintf(header, "local const ct_data static_dtree[D_CODES] = {\n");
     349    for (i = 0; i < D_CODES; i++) {
     350        fprintf(header, "{{%2u},{%2u}}%s", static_dtree[i].Code,
     351                static_dtree[i].Len, SEPARATOR(i, D_CODES-1, 5));
     352    }
     353
     354    fprintf(header, "const uch ZLIB_INTERNAL _dist_code[DIST_CODE_LEN] = {\n");
     355    for (i = 0; i < DIST_CODE_LEN; i++) {
     356        fprintf(header, "%2u%s", _dist_code[i],
     357                SEPARATOR(i, DIST_CODE_LEN-1, 20));
     358    }
     359
     360    fprintf(header,
     361        "const uch ZLIB_INTERNAL _length_code[MAX_MATCH-MIN_MATCH+1]= {\n");
     362    for (i = 0; i < MAX_MATCH-MIN_MATCH+1; i++) {
     363        fprintf(header, "%2u%s", _length_code[i],
     364                SEPARATOR(i, MAX_MATCH-MIN_MATCH, 20));
     365    }
     366
     367    fprintf(header, "local const int base_length[LENGTH_CODES] = {\n");
     368    for (i = 0; i < LENGTH_CODES; i++) {
     369        fprintf(header, "%1u%s", base_length[i],
     370                SEPARATOR(i, LENGTH_CODES-1, 20));
     371    }
     372
     373    fprintf(header, "local const int base_dist[D_CODES] = {\n");
     374    for (i = 0; i < D_CODES; i++) {
     375        fprintf(header, "%5u%s", base_dist[i],
     376                SEPARATOR(i, D_CODES-1, 10));
     377    }
     378
     379    fclose(header);
     380}
     381#endif /* GEN_TREES_H */
     382
     383/* ===========================================================================
     384 * Initialize the tree data structures for a new zlib stream.
     385 */
     386void ZLIB_INTERNAL _tr_init(s)
     387    deflate_state *s;
     388{
     389    tr_static_init();
     390
     391    s->l_desc.dyn_tree = s->dyn_ltree;
     392    s->l_desc.stat_desc = &static_l_desc;
     393
     394    s->d_desc.dyn_tree = s->dyn_dtree;
     395    s->d_desc.stat_desc = &static_d_desc;
     396
     397    s->bl_desc.dyn_tree = s->bl_tree;
     398    s->bl_desc.stat_desc = &static_bl_desc;
     399
     400    s->bi_buf = 0;
     401    s->bi_valid = 0;
     402    s->last_eob_len = 8; /* enough lookahead for inflate */
     403#ifdef DEBUG
     404    s->compressed_len = 0L;
     405    s->bits_sent = 0L;
     406#endif
    399407
    400408    /* Initialize the first block of the first file: */
    401     init_block();
     409    init_block(s);
    402410}
    403411
     
    405413 * Initialize a new block.
    406414 */
    407 local void init_block()
     415local void init_block(s)
     416    deflate_state *s;
    408417{
    409418    int n; /* iterates over tree elements */
    410419
    411420    /* Initialize the trees. */
    412     for (n = 0; n < L_CODES;  n++) dyn_ltree[n].Freq = 0;
    413     for (n = 0; n < D_CODES;  n++) dyn_dtree[n].Freq = 0;
    414     for (n = 0; n < BL_CODES; n++) bl_tree[n].Freq = 0;
    415 
    416     dyn_ltree[END_BLOCK].Freq = 1;
    417     opt_len = static_len = 0L;
    418     last_lit = last_dist = last_flags = 0;
    419     flags = 0; flag_bit = 1;
     421    for (n = 0; n < L_CODES;  n++) s->dyn_ltree[n].Freq = 0;
     422    for (n = 0; n < D_CODES;  n++) s->dyn_dtree[n].Freq = 0;
     423    for (n = 0; n < BL_CODES; n++) s->bl_tree[n].Freq = 0;
     424
     425    s->dyn_ltree[END_BLOCK].Freq = 1;
     426    s->opt_len = s->static_len = 0L;
     427    s->last_lit = s->matches = 0;
    420428}
    421429
     
    428436 * one less element. Updates heap and heap_len.
    429437 */
    430 #define pqremove(tree, top) \
     438#define pqremove(s, tree, top) \
    431439{\
    432     top = heap[SMALLEST]; \
    433     heap[SMALLEST] = heap[heap_len--]; \
    434     pqdownheap(tree, SMALLEST); \
     440    top = s->heap[SMALLEST]; \
     441    s->heap[SMALLEST] = s->heap[s->heap_len--]; \
     442    pqdownheap(s, tree, SMALLEST); \
    435443}
    436444
     
    439447 * the subtrees have equal frequency. This minimizes the worst case length.
    440448 */
    441 #define smaller(tree, n, m) \
     449#define smaller(tree, n, m, depth) \
    442450   (tree[n].Freq < tree[m].Freq || \
    443451   (tree[n].Freq == tree[m].Freq && depth[n] <= depth[m]))
     
    449457 * two sons).
    450458 */
    451 local void pqdownheap(tree, k)
    452     ct_data near *tree;  /* the tree to restore */
     459local void pqdownheap(s, tree, k)
     460    deflate_state *s;
     461    ct_data *tree;  /* the tree to restore */
    453462    int k;               /* node to move down */
    454463{
    455     int v = heap[k];
     464    int v = s->heap[k];
    456465    int j = k << 1;  /* left son of k */
    457     while (j <= heap_len) {
     466    while (j <= s->heap_len) {
    458467        /* Set j to the smallest of the two sons: */
    459         if (j < heap_len && smaller(tree, heap[j+1], heap[j])) j++;
    460 
     468        if (j < s->heap_len &&
     469            smaller(tree, s->heap[j+1], s->heap[j], s->depth)) {
     470            j++;
     471        }
    461472        /* Exit if v is smaller than both sons */
    462         if (smaller(tree, v, heap[j])) break;
     473        if (smaller(tree, v, s->heap[j], s->depth)) break;
    463474
    464475        /* Exchange v with the smallest son */
    465         heap[k] = heap[j];  k = j;
     476        s->heap[k] = s->heap[j];  k = j;
    466477
    467478        /* And continue down the tree, setting j to the left son of k */
    468479        j <<= 1;
    469480    }
    470     heap[k] = v;
     481    s->heap[k] = v;
    471482}
    472483
     
    481492 *     not null.
    482493 */
    483 local void gen_bitlen(desc)
    484     tree_desc near *desc; /* the tree descriptor */
    485 {
    486     ct_data near *tree  = desc->dyn_tree;
    487     int near *extra     = desc->extra_bits;
    488     int base            = desc->extra_base;
    489     int max_code        = desc->max_code;
    490     int max_length      = desc->max_length;
    491     ct_data near *stree = desc->static_tree;
     494local void gen_bitlen(s, desc)
     495    deflate_state *s;
     496    tree_desc *desc;    /* the tree descriptor */
     497{
     498    ct_data *tree        = desc->dyn_tree;
     499    int max_code         = desc->max_code;
     500    const ct_data *stree = desc->stat_desc->static_tree;
     501    const intf *extra    = desc->stat_desc->extra_bits;
     502    int base             = desc->stat_desc->extra_base;
     503    int max_length       = desc->stat_desc->max_length;
    492504    int h;              /* heap index */
    493505    int n, m;           /* iterate over the tree elements */
     
    497509    int overflow = 0;   /* number of elements with bit length too large */
    498510
    499     for (bits = 0; bits <= MAX_BITS; bits++) bl_count[bits] = 0;
     511    for (bits = 0; bits <= MAX_BITS; bits++) s->bl_count[bits] = 0;
    500512
    501513    /* In a first pass, compute the optimal bit lengths (which may
    502514     * overflow in the case of the bit length tree).
    503515     */
    504     tree[heap[heap_max]].Len = 0; /* root of the heap */
    505 
    506     for (h = heap_max+1; h < HEAP_SIZE; h++) {
    507         n = heap[h];
     516    tree[s->heap[s->heap_max]].Len = 0; /* root of the heap */
     517
     518    for (h = s->heap_max+1; h < HEAP_SIZE; h++) {
     519        n = s->heap[h];
    508520        bits = tree[tree[n].Dad].Len + 1;
    509521        if (bits > max_length) bits = max_length, overflow++;
     
    513525        if (n > max_code) continue; /* not a leaf node */
    514526
    515         bl_count[bits]++;
     527        s->bl_count[bits]++;
    516528        xbits = 0;
    517529        if (n >= base) xbits = extra[n-base];
    518530        f = tree[n].Freq;
    519         opt_len += (ulg)f * (bits + xbits);
    520         if (stree) static_len += (ulg)f * (stree[n].Len + xbits);
     531        s->opt_len += (ulg)f * (bits + xbits);
     532        if (stree) s->static_len += (ulg)f * (stree[n].Len + xbits);
    521533    }
    522534    if (overflow == 0) return;
     
    528540    do {
    529541        bits = max_length-1;
    530         while (bl_count[bits] == 0) bits--;
    531         bl_count[bits]--;      /* move one leaf down the tree */
    532         bl_count[bits+1] += 2; /* move one overflow item as its brother */
    533         bl_count[max_length]--;
     542        while (s->bl_count[bits] == 0) bits--;
     543        s->bl_count[bits]--;      /* move one leaf down the tree */
     544        s->bl_count[bits+1] += 2; /* move one overflow item as its brother */
     545        s->bl_count[max_length]--;
    534546        /* The brother of the overflow item also moves one step up,
    535547         * but this does not affect bl_count[max_length]
     
    544556     */
    545557    for (bits = max_length; bits != 0; bits--) {
    546         n = bl_count[bits];
     558        n = s->bl_count[bits];
    547559        while (n != 0) {
    548             m = heap[--h];
     560            m = s->heap[--h];
    549561            if (m > max_code) continue;
    550             if (tree[m].Len != (unsigned) bits) {
     562            if ((unsigned) tree[m].Len != (unsigned) bits) {
    551563                Trace((stderr,"code %d bits %d->%d\n", m, tree[m].Len, bits));
    552                 opt_len += ((long)bits-(long)tree[m].Len)*(long)tree[m].Freq;
     564                s->opt_len += ((long)bits - (long)tree[m].Len)
     565                              *(long)tree[m].Freq;
    553566                tree[m].Len = (ush)bits;
    554567            }
     
    566579 *     zero code length.
    567580 */
    568 local void gen_codes (tree, max_code)
    569     ct_data near *tree;        /* the tree to decorate */
     581local void gen_codes (tree, max_code, bl_count)
     582    ct_data *tree;             /* the tree to decorate */
    570583    int max_code;              /* largest code with non zero frequency */
     584    ushf *bl_count;            /* number of codes at each bit length */
    571585{
    572586    ush next_code[MAX_BITS+1]; /* next code value for each bit length */
     
    594608        tree[n].Code = bi_reverse(next_code[len]++, len);
    595609
    596         Tracec(tree != static_ltree, (stderr,"\nn %3d %c l %2d c %4x (%x) ",
     610        Tracecv(tree != static_ltree, (stderr,"\nn %3d %c l %2d c %4x (%x) ",
    597611             n, (isgraph(n) ? n : ' '), len, tree[n].Code, next_code[len]-1));
    598612    }
     
    607621 *     also updated if stree is not null. The field max_code is set.
    608622 */
    609 local void build_tree(desc)
    610     tree_desc near *desc; /* the tree descriptor */
    611 {
    612     ct_data near *tree   = desc->dyn_tree;
    613     ct_data near *stree  = desc->static_tree;
    614     int elems            = desc->elems;
     623local void build_tree(s, desc)
     624    deflate_state *s;
     625    tree_desc *desc; /* the tree descriptor */
     626{
     627    ct_data *tree         = desc->dyn_tree;
     628    const ct_data *stree  = desc->stat_desc->static_tree;
     629    int elems             = desc->stat_desc->elems;
    615630    int n, m;          /* iterate over heap elements */
    616631    int max_code = -1; /* largest code with non zero frequency */
    617     int node = elems;  /* next internal node of the tree */
     632    int node;          /* new node being created */
    618633
    619634    /* Construct the initial heap, with least frequent element in
     
    621636     * heap[0] is not used.
    622637     */
    623     heap_len = 0, heap_max = HEAP_SIZE;
     638    s->heap_len = 0, s->heap_max = HEAP_SIZE;
    624639
    625640    for (n = 0; n < elems; n++) {
    626641        if (tree[n].Freq != 0) {
    627             heap[++heap_len] = max_code = n;
    628             depth[n] = 0;
     642            s->heap[++(s->heap_len)] = max_code = n;
     643            s->depth[n] = 0;
    629644        } else {
    630645            tree[n].Len = 0;
     
    637652     * two codes of non zero frequency.
    638653     */
    639     while (heap_len < 2) {
    640         int new = heap[++heap_len] = (max_code < 2 ? ++max_code : 0);
    641         tree[new].Freq = 1;
    642         depth[new] = 0;
    643         opt_len--; if (stree) static_len -= stree[new].Len;
    644         /* new is 0 or 1 so it does not have extra bits */
     654    while (s->heap_len < 2) {
     655        node = s->heap[++(s->heap_len)] = (max_code < 2 ? ++max_code : 0);
     656        tree[node].Freq = 1;
     657        s->depth[node] = 0;
     658        s->opt_len--; if (stree) s->static_len -= stree[node].Len;
     659        /* node is 0 or 1 so it does not have extra bits */
    645660    }
    646661    desc->max_code = max_code;
     
    649664     * establish sub-heaps of increasing lengths:
    650665     */
    651     for (n = heap_len/2; n >= 1; n--) pqdownheap(tree, n);
     666    for (n = s->heap_len/2; n >= 1; n--) pqdownheap(s, tree, n);
    652667
    653668    /* Construct the Huffman tree by repeatedly combining the least two
    654669     * frequent nodes.
    655670     */
     671    node = elems;              /* next internal node of the tree */
    656672    do {
    657         pqremove(tree, n);   /* n = node of least frequency */
    658         m = heap[SMALLEST]; /* m = node of next least frequency */
    659 
    660         heap[--heap_max] = n; /* keep the nodes sorted by frequency */
    661         heap[--heap_max] = m;
     673        pqremove(s, tree, n);  /* n = node of least frequency */
     674        m = s->heap[SMALLEST]; /* m = node of next least frequency */
     675
     676        s->heap[--(s->heap_max)] = n; /* keep the nodes sorted by frequency */
     677        s->heap[--(s->heap_max)] = m;
    662678
    663679        /* Create a new node father of n and m */
    664680        tree[node].Freq = tree[n].Freq + tree[m].Freq;
    665         depth[node] = (uch) (MAX(depth[n], depth[m]) + 1);
     681        s->depth[node] = (uch)((s->depth[n] >= s->depth[m] ?
     682                                s->depth[n] : s->depth[m]) + 1);
    666683        tree[n].Dad = tree[m].Dad = (ush)node;
    667684#ifdef DUMP_BL_TREE
    668         if (tree == bl_tree) {
     685        if (tree == s->bl_tree) {
    669686            fprintf(stderr,"\nnode %d(%d), sons %d(%d) %d(%d)",
    670687                    node, tree[node].Freq, n, tree[n].Freq, m, tree[m].Freq);
     
    672689#endif
    673690        /* and insert the new node in the heap */
    674         heap[SMALLEST] = node++;
    675         pqdownheap(tree, SMALLEST);
    676 
    677     } while (heap_len >= 2);
    678 
    679     heap[--heap_max] = heap[SMALLEST];
     691        s->heap[SMALLEST] = node++;
     692        pqdownheap(s, tree, SMALLEST);
     693
     694    } while (s->heap_len >= 2);
     695
     696    s->heap[--(s->heap_max)] = s->heap[SMALLEST];
    680697
    681698    /* At this point, the fields freq and dad are set. We can now
    682699     * generate the bit lengths.
    683700     */
    684     gen_bitlen((tree_desc near *)desc);
     701    gen_bitlen(s, (tree_desc *)desc);
    685702
    686703    /* The field len is now set, we can generate the bit codes */
    687     gen_codes ((ct_data near *)tree, max_code);
     704    gen_codes ((ct_data *)tree, max_code, s->bl_count);
    688705}
    689706
    690707/* ===========================================================================
    691708 * Scan a literal or distance tree to determine the frequencies of the codes
    692  * in the bit length tree. Updates opt_len to take into account the repeat
    693  * counts. (The contribution of the bit length codes will be added later
    694  * during the construction of bl_tree.)
    695  */
    696 local void scan_tree (tree, max_code)
    697     ct_data near *tree; /* the tree to be scanned */
    698     int max_code;       /* and its largest code of non zero frequency */
     709 * in the bit length tree.
     710 */
     711local void scan_tree (s, tree, max_code)
     712    deflate_state *s;
     713    ct_data *tree;   /* the tree to be scanned */
     714    int max_code;    /* and its largest code of non zero frequency */
    699715{
    700716    int n;                     /* iterates over all tree elements */
     
    714730            continue;
    715731        } else if (count < min_count) {
    716             bl_tree[curlen].Freq += count;
     732            s->bl_tree[curlen].Freq += count;
    717733        } else if (curlen != 0) {
    718             if (curlen != prevlen) bl_tree[curlen].Freq++;
    719             bl_tree[REP_3_6].Freq++;
     734            if (curlen != prevlen) s->bl_tree[curlen].Freq++;
     735            s->bl_tree[REP_3_6].Freq++;
    720736        } else if (count <= 10) {
    721             bl_tree[REPZ_3_10].Freq++;
     737            s->bl_tree[REPZ_3_10].Freq++;
    722738        } else {
    723             bl_tree[REPZ_11_138].Freq++;
     739            s->bl_tree[REPZ_11_138].Freq++;
    724740        }
    725741        count = 0; prevlen = curlen;
     
    738754 * bl_tree.
    739755 */
    740 local void send_tree (tree, max_code)
    741     ct_data near *tree; /* the tree to be scanned */
     756local void send_tree (s, tree, max_code)
     757    deflate_state *s;
     758    ct_data *tree; /* the tree to be scanned */
    742759    int max_code;       /* and its largest code of non zero frequency */
    743760{
     
    758775            continue;
    759776        } else if (count < min_count) {
    760             do { send_code(curlen, bl_tree); } while (--count != 0);
     777            do { send_code(s, curlen, s->bl_tree); } while (--count != 0);
    761778
    762779        } else if (curlen != 0) {
    763780            if (curlen != prevlen) {
    764                 send_code(curlen, bl_tree); count--;
     781                send_code(s, curlen, s->bl_tree); count--;
    765782            }
    766783            Assert(count >= 3 && count <= 6, " 3_6?");
    767             send_code(REP_3_6, bl_tree); send_bits(count-3, 2);
     784            send_code(s, REP_3_6, s->bl_tree); send_bits(s, count-3, 2);
    768785
    769786        } else if (count <= 10) {
    770             send_code(REPZ_3_10, bl_tree); send_bits(count-3, 3);
     787            send_code(s, REPZ_3_10, s->bl_tree); send_bits(s, count-3, 3);
    771788
    772789        } else {
    773             send_code(REPZ_11_138, bl_tree); send_bits(count-11, 7);
     790            send_code(s, REPZ_11_138, s->bl_tree); send_bits(s, count-11, 7);
    774791        }
    775792        count = 0; prevlen = curlen;
     
    788805 * bl_order of the last bit length code to send.
    789806 */
    790 local int build_bl_tree()
     807local int build_bl_tree(s)
     808    deflate_state *s;
    791809{
    792810    int max_blindex;  /* index of last bit length code of non zero freq */
    793811
    794812    /* Determine the bit length frequencies for literal and distance trees */
    795     scan_tree((ct_data near *)dyn_ltree, l_desc.max_code);
    796     scan_tree((ct_data near *)dyn_dtree, d_desc.max_code);
     813    scan_tree(s, (ct_data *)s->dyn_ltree, s->l_desc.max_code);
     814    scan_tree(s, (ct_data *)s->dyn_dtree, s->d_desc.max_code);
    797815
    798816    /* Build the bit length tree: */
    799     build_tree((tree_desc near *)(&bl_desc));
     817    build_tree(s, (tree_desc *)(&(s->bl_desc)));
    800818    /* opt_len now includes the length of the tree representations, except
    801819     * the lengths of the bit lengths codes and the 5+5+4 bits for the counts.
     
    807825     */
    808826    for (max_blindex = BL_CODES-1; max_blindex >= 3; max_blindex--) {
    809         if (bl_tree[bl_order[max_blindex]].Len != 0) break;
     827        if (s->bl_tree[bl_order[max_blindex]].Len != 0) break;
    810828    }
    811829    /* Update opt_len to include the bit length tree and counts */
    812     opt_len += 3*(max_blindex+1) + 5+5+4;
    813     Tracev((stderr, "\ndyn trees: dyn %ld, stat %ld", opt_len, static_len));
     830    s->opt_len += 3*(max_blindex+1) + 5+5+4;
     831    Tracev((stderr, "\ndyn trees: dyn %ld, stat %ld",
     832            s->opt_len, s->static_len));
    814833
    815834    return max_blindex;
     
    821840 * IN assertion: lcodes >= 257, dcodes >= 1, blcodes >= 4.
    822841 */
    823 local void send_all_trees(lcodes, dcodes, blcodes)
     842local void send_all_trees(s, lcodes, dcodes, blcodes)
     843    deflate_state *s;
    824844    int lcodes, dcodes, blcodes; /* number of codes for each tree */
    825845{
     
    830850            "too many codes");
    831851    Tracev((stderr, "\nbl counts: "));
    832     send_bits(lcodes-257, 5); /* not +255 as stated in appnote.txt */
    833     send_bits(dcodes-1,   5);
    834     send_bits(blcodes-4,  4); /* not -3 as stated in appnote.txt */
     852    send_bits(s, lcodes-257, 5); /* not +255 as stated in appnote.txt */
     853    send_bits(s, dcodes-1,   5);
     854    send_bits(s, blcodes-4,  4); /* not -3 as stated in appnote.txt */
    835855    for (rank = 0; rank < blcodes; rank++) {
    836856        Tracev((stderr, "\nbl code %2d ", bl_order[rank]));
    837         send_bits(bl_tree[bl_order[rank]].Len, 3);
    838     }
    839     Tracev((stderr, "\nbl tree: sent %ld", bits_sent));
    840 
    841     send_tree((ct_data near *)dyn_ltree, lcodes-1); /* send the literal tree */
    842     Tracev((stderr, "\nlit tree: sent %ld", bits_sent));
    843 
    844     send_tree((ct_data near *)dyn_dtree, dcodes-1); /* send the distance tree */
    845     Tracev((stderr, "\ndist tree: sent %ld", bits_sent));
     857        send_bits(s, s->bl_tree[bl_order[rank]].Len, 3);
     858    }
     859    Tracev((stderr, "\nbl tree: sent %ld", s->bits_sent));
     860
     861    send_tree(s, (ct_data *)s->dyn_ltree, lcodes-1); /* literal tree */
     862    Tracev((stderr, "\nlit tree: sent %ld", s->bits_sent));
     863
     864    send_tree(s, (ct_data *)s->dyn_dtree, dcodes-1); /* distance tree */
     865    Tracev((stderr, "\ndist tree: sent %ld", s->bits_sent));
     866}
     867
     868/* ===========================================================================
     869 * Send a stored block
     870 */
     871void ZLIB_INTERNAL _tr_stored_block(s, buf, stored_len, last)
     872    deflate_state *s;
     873    charf *buf;       /* input block */
     874    ulg stored_len;   /* length of input block */
     875    int last;         /* one if this is the last block for a file */
     876{
     877    send_bits(s, (STORED_BLOCK<<1)+last, 3);    /* send block type */
     878#ifdef DEBUG
     879    s->compressed_len = (s->compressed_len + 3 + 7) & (ulg)~7L;
     880    s->compressed_len += (stored_len + 4) << 3;
     881#endif
     882    copy_block(s, buf, (unsigned)stored_len, 1); /* with header */
     883}
     884
     885/* ===========================================================================
     886 * Send one empty static block to give enough lookahead for inflate.
     887 * This takes 10 bits, of which 7 may remain in the bit buffer.
     888 * The current inflate code requires 9 bits of lookahead. If the
     889 * last two codes for the previous block (real code plus EOB) were coded
     890 * on 5 bits or less, inflate may have only 5+3 bits of lookahead to decode
     891 * the last real code. In this case we send two empty static blocks instead
     892 * of one. (There are no problems if the previous block is stored or fixed.)
     893 * To simplify the code, we assume the worst case of last real code encoded
     894 * on one bit only.
     895 */
     896void ZLIB_INTERNAL _tr_align(s)
     897    deflate_state *s;
     898{
     899    send_bits(s, STATIC_TREES<<1, 3);
     900    send_code(s, END_BLOCK, static_ltree);
     901#ifdef DEBUG
     902    s->compressed_len += 10L; /* 3 for block type, 7 for EOB */
     903#endif
     904    bi_flush(s);
     905    /* Of the 10 bits for the empty block, we have already sent
     906     * (10 - bi_valid) bits. The lookahead for the last real code (before
     907     * the EOB of the previous block) was thus at least one plus the length
     908     * of the EOB plus what we have just sent of the empty static block.
     909     */
     910    if (1 + s->last_eob_len + 10 - s->bi_valid < 9) {
     911        send_bits(s, STATIC_TREES<<1, 3);
     912        send_code(s, END_BLOCK, static_ltree);
     913#ifdef DEBUG
     914        s->compressed_len += 10L;
     915#endif
     916        bi_flush(s);
     917    }
     918    s->last_eob_len = 7;
    846919}
    847920
    848921/* ===========================================================================
    849922 * Determine the best encoding for the current block: dynamic trees, static
    850  * trees or store, and output the encoded block to the zip file. This function
    851  * returns the total compressed length for the file so far.
    852  */
    853 ulg flush_block(buf, stored_len, eof)
    854     char *buf;        /* input block, or NULL if too old */
     923 * trees or store, and output the encoded block to the zip file.
     924 */
     925void ZLIB_INTERNAL _tr_flush_block(s, buf, stored_len, last)
     926    deflate_state *s;
     927    charf *buf;       /* input block, or NULL if too old */
    855928    ulg stored_len;   /* length of input block */
    856     int eof;          /* true if this is the last block for a file */
     929    int last;         /* one if this is the last block for a file */
    857930{
    858931    ulg opt_lenb, static_lenb; /* opt_len and static_len in bytes */
    859     int max_blindex;  /* index of last bit length code of non zero freq */
    860 
    861     flag_buf[last_flags] = flags; /* Save the flags for the last 8 items */
    862 
    863      /* Check if the file is ascii or binary */
    864     if (*file_type == (ush)UNKNOWN) set_file_type();
    865 
    866     /* Construct the literal and distance trees */
    867     build_tree((tree_desc near *)(&l_desc));
    868     Tracev((stderr, "\nlit data: dyn %ld, stat %ld", opt_len, static_len));
    869 
    870     build_tree((tree_desc near *)(&d_desc));
    871     Tracev((stderr, "\ndist data: dyn %ld, stat %ld", opt_len, static_len));
    872     /* At this point, opt_len and static_len are the total bit lengths of
    873      * the compressed block data, excluding the tree representations.
    874      */
    875 
    876     /* Build the bit length tree for the above two trees, and get the index
    877      * in bl_order of the last bit length code to send.
    878      */
    879     max_blindex = build_bl_tree();
    880 
    881     /* Determine the best encoding. Compute first the block length in bytes */
    882     opt_lenb = (opt_len+3+7)>>3;
    883     static_lenb = (static_len+3+7)>>3;
    884     input_len += stored_len; /* for debugging only */
    885 
    886     Trace((stderr, "\nopt %lu(%lu) stat %lu(%lu) stored %lu lit %u dist %u ",
    887             opt_lenb, opt_len, static_lenb, static_len, stored_len,
    888             last_lit, last_dist));
    889 
    890     if (static_lenb <= opt_lenb) opt_lenb = static_lenb;
    891 
    892     /* If compression failed and this is the first and last block,
    893      * and if the zip file can be seeked (to rewrite the local header),
    894      * the whole file is transformed into a stored file:
    895      */
    896 #ifdef FORCE_METHOD
    897     if (level == 1 && eof && compressed_len == 0L) { /* force stored file */
     932    int max_blindex = 0;  /* index of last bit length code of non zero freq */
     933
     934    /* Build the Huffman trees unless a stored block is forced */
     935    if (s->level > 0) {
     936
     937        /* Check if the file is binary or text */
     938        if (s->strm->data_type == Z_UNKNOWN)
     939            s->strm->data_type = detect_data_type(s);
     940
     941        /* Construct the literal and distance trees */
     942        build_tree(s, (tree_desc *)(&(s->l_desc)));
     943        Tracev((stderr, "\nlit data: dyn %ld, stat %ld", s->opt_len,
     944                s->static_len));
     945
     946        build_tree(s, (tree_desc *)(&(s->d_desc)));
     947        Tracev((stderr, "\ndist data: dyn %ld, stat %ld", s->opt_len,
     948                s->static_len));
     949        /* At this point, opt_len and static_len are the total bit lengths of
     950         * the compressed block data, excluding the tree representations.
     951         */
     952
     953        /* Build the bit length tree for the above two trees, and get the index
     954         * in bl_order of the last bit length code to send.
     955         */
     956        max_blindex = build_bl_tree(s);
     957
     958        /* Determine the best encoding. Compute the block lengths in bytes. */
     959        opt_lenb = (s->opt_len+3+7)>>3;
     960        static_lenb = (s->static_len+3+7)>>3;
     961
     962        Tracev((stderr, "\nopt %lu(%lu) stat %lu(%lu) stored %lu lit %u ",
     963                opt_lenb, s->opt_len, static_lenb, s->static_len, stored_len,
     964                s->last_lit));
     965
     966        if (static_lenb <= opt_lenb) opt_lenb = static_lenb;
     967
     968    } else {
     969        Assert(buf != (char*)0, "lost buf");
     970        opt_lenb = static_lenb = stored_len + 5; /* force a stored block */
     971    }
     972
     973#ifdef FORCE_STORED
     974    if (buf != (char*)0) { /* force stored block */
    898975#else
    899     if (stored_len <= opt_lenb && eof && compressed_len == 0L && seekable()) {
    900 #endif
    901         /* Since LIT_BUFSIZE <= 2*WSIZE, the input data must be there: */
    902         if (buf == (char*)0) error ("block vanished");
    903 
    904         copy_block(buf, (unsigned)stored_len, 0); /* without header */
    905         compressed_len = stored_len << 3;
    906         *file_method = STORED;
    907 
    908 #ifdef FORCE_METHOD
    909     } else if (level == 2 && buf != (char*)0) { /* force stored block */
    910 #else
    911     } else if (stored_len+4 <= opt_lenb && buf != (char*)0) {
     976    if (stored_len+4 <= opt_lenb && buf != (char*)0) {
    912977                       /* 4: two words for the lengths */
    913978#endif
     
    918983         * transform a block into a stored block.
    919984         */
    920         send_bits((STORED_BLOCK<<1)+eof, 3);  /* send block type */
    921         compressed_len = (compressed_len + 3 + 7) & ~7L;
    922         compressed_len += (stored_len + 4) << 3;
    923 
    924         copy_block(buf, (unsigned)stored_len, 1); /* with header */
    925 
    926 #ifdef FORCE_METHOD
    927     } else if (level == 3) { /* force static trees */
     985        _tr_stored_block(s, buf, stored_len, last);
     986
     987#ifdef FORCE_STATIC
     988    } else if (static_lenb >= 0) { /* force static trees */
    928989#else
    929     } else if (static_lenb == opt_lenb) {
    930 #endif
    931         send_bits((STATIC_TREES<<1)+eof, 3);
    932         compress_block((ct_data near *)static_ltree, (ct_data near *)static_dtree);
    933         compressed_len += 3 + static_len;
     990    } else if (s->strategy == Z_FIXED || static_lenb == opt_lenb) {
     991#endif
     992        send_bits(s, (STATIC_TREES<<1)+last, 3);
     993        compress_block(s, (ct_data *)static_ltree, (ct_data *)static_dtree);
     994#ifdef DEBUG
     995        s->compressed_len += 3 + s->static_len;
     996#endif
    934997    } else {
    935         send_bits((DYN_TREES<<1)+eof, 3);
    936         send_all_trees(l_desc.max_code+1, d_desc.max_code+1, max_blindex+1);
    937         compress_block((ct_data near *)dyn_ltree, (ct_data near *)dyn_dtree);
    938         compressed_len += 3 + opt_len;
    939     }
    940     Assert (compressed_len == bits_sent, "bad compressed size");
    941     init_block();
    942 
    943     if (eof) {
    944         Assert (input_len == isize, "bad input size");
    945         bi_windup();
    946         compressed_len += 7;  /* align on byte boundary */
    947     }
    948     Tracev((stderr,"\ncomprlen %lu(%lu) ", compressed_len>>3,
    949            compressed_len-7*eof));
    950 
    951     return compressed_len >> 3;
     998        send_bits(s, (DYN_TREES<<1)+last, 3);
     999        send_all_trees(s, s->l_desc.max_code+1, s->d_desc.max_code+1,
     1000                       max_blindex+1);
     1001        compress_block(s, (ct_data *)s->dyn_ltree, (ct_data *)s->dyn_dtree);
     1002#ifdef DEBUG
     1003        s->compressed_len += 3 + s->opt_len;
     1004#endif
     1005    }
     1006    Assert (s->compressed_len == s->bits_sent, "bad compressed size");
     1007    /* The above check is made mod 2^32, for files larger than 512 MB
     1008     * and uLong implemented on 32 bits.
     1009     */
     1010    init_block(s);
     1011
     1012    if (last) {
     1013        bi_windup(s);
     1014#ifdef DEBUG
     1015        s->compressed_len += 7;  /* align on byte boundary */
     1016#endif
     1017    }
     1018    Tracev((stderr,"\ncomprlen %lu(%lu) ", s->compressed_len>>3,
     1019           s->compressed_len-7*last));
    9521020}
    9531021
     
    9561024 * the current block must be flushed.
    9571025 */
    958 int ct_tally (dist, lc)
    959     int dist;  /* distance of matched string */
    960     int lc;    /* match length-MIN_MATCH or unmatched char (if dist==0) */
    961 {
    962     l_buf[last_lit++] = (uch)lc;
     1026int ZLIB_INTERNAL _tr_tally (s, dist, lc)
     1027    deflate_state *s;
     1028    unsigned dist;  /* distance of matched string */
     1029    unsigned lc;    /* match length-MIN_MATCH or unmatched char (if dist==0) */
     1030{
     1031    s->d_buf[s->last_lit] = (ush)dist;
     1032    s->l_buf[s->last_lit++] = (uch)lc;
    9631033    if (dist == 0) {
    9641034        /* lc is the unmatched char */
    965         dyn_ltree[lc].Freq++;
     1035        s->dyn_ltree[lc].Freq++;
    9661036    } else {
     1037        s->matches++;
    9671038        /* Here, lc is the match length - MIN_MATCH */
    9681039        dist--;             /* dist = match distance - 1 */
    969         Assert((ush)dist < (ush)MAX_DIST &&
     1040        Assert((ush)dist < (ush)MAX_DIST(s) &&
    9701041               (ush)lc <= (ush)(MAX_MATCH-MIN_MATCH) &&
    971                (ush)d_code(dist) < (ush)D_CODES,  "ct_tally: bad match");
    972 
    973         dyn_ltree[length_code[lc]+LITERALS+1].Freq++;
    974         dyn_dtree[d_code(dist)].Freq++;
    975 
    976         d_buf[last_dist++] = (ush)dist;
    977         flags |= flag_bit;
    978     }
    979     flag_bit <<= 1;
    980 
    981     /* Output the flags if they fill a byte: */
    982     if ((last_lit & 7) == 0) {
    983         flag_buf[last_flags++] = flags;
    984         flags = 0, flag_bit = 1;
    985     }
     1042               (ush)d_code(dist) < (ush)D_CODES,  "_tr_tally: bad match");
     1043
     1044        s->dyn_ltree[_length_code[lc]+LITERALS+1].Freq++;
     1045        s->dyn_dtree[d_code(dist)].Freq++;
     1046    }
     1047
     1048#ifdef TRUNCATE_BLOCK
    9861049    /* Try to guess if it is profitable to stop the current block here */
    987     if (level > 2 && (last_lit & 0xfff) == 0) {
     1050    if ((s->last_lit & 0x1fff) == 0 && s->level > 2) {
    9881051        /* Compute an upper bound for the compressed length */
    989         ulg out_length = (ulg)last_lit*8L;
    990         ulg in_length = (ulg)strstart-block_start;
     1052        ulg out_length = (ulg)s->last_lit*8L;
     1053        ulg in_length = (ulg)((long)s->strstart - s->block_start);
    9911054        int dcode;
    9921055        for (dcode = 0; dcode < D_CODES; dcode++) {
    993             out_length += (ulg)dyn_dtree[dcode].Freq*(5L+extra_dbits[dcode]);
     1056            out_length += (ulg)s->dyn_dtree[dcode].Freq *
     1057                (5L+extra_dbits[dcode]);
    9941058        }
    9951059        out_length >>= 3;
    996         Trace((stderr,"\nlast_lit %u, last_dist %u, in %ld, out ~%ld(%ld%%) ",
    997                last_lit, last_dist, in_length, out_length,
     1060        Tracev((stderr,"\nlast_lit %u, in %ld, out ~%ld(%ld%%) ",
     1061               s->last_lit, in_length, out_length,
    9981062               100L - out_length*100L/in_length));
    999         if (last_dist < last_lit/2 && out_length < in_length/2) return 1;
    1000     }
    1001     return (last_lit == LIT_BUFSIZE-1 || last_dist == DIST_BUFSIZE);
    1002     /* We avoid equality with LIT_BUFSIZE because of wraparound at 64K
     1063        if (s->matches < s->last_lit/2 && out_length < in_length/2) return 1;
     1064    }
     1065#endif
     1066    return (s->last_lit == s->lit_bufsize-1);
     1067    /* We avoid equality with lit_bufsize because of wraparound at 64K
    10031068     * on 16 bit machines and because stored blocks are restricted to
    10041069     * 64K-1 bytes.
     
    10091074 * Send the block data compressed using the given Huffman trees
    10101075 */
    1011 local void compress_block(ltree, dtree)
    1012     ct_data near *ltree; /* literal tree */
    1013     ct_data near *dtree; /* distance tree */
     1076local void compress_block(s, ltree, dtree)
     1077    deflate_state *s;
     1078    ct_data *ltree; /* literal tree */
     1079    ct_data *dtree; /* distance tree */
    10141080{
    10151081    unsigned dist;      /* distance of matched string */
    10161082    int lc;             /* match length or unmatched char (if dist == 0) */
    10171083    unsigned lx = 0;    /* running index in l_buf */
    1018     unsigned dx = 0;    /* running index in d_buf */
    1019     unsigned fx = 0;    /* running index in flag_buf */
    1020     uch flag = 0;       /* current flags */
    10211084    unsigned code;      /* the code to send */
    10221085    int extra;          /* number of extra bits to send */
    10231086
    1024     if (last_lit != 0) do {
    1025         if ((lx & 7) == 0) flag = flag_buf[fx++];
    1026         lc = l_buf[lx++];
    1027         if ((flag & 1) == 0) {
    1028             send_code(lc, ltree); /* send a literal byte */
     1087    if (s->last_lit != 0) do {
     1088        dist = s->d_buf[lx];
     1089        lc = s->l_buf[lx++];
     1090        if (dist == 0) {
     1091            send_code(s, lc, ltree); /* send a literal byte */
    10291092            Tracecv(isgraph(lc), (stderr," '%c' ", lc));
    10301093        } else {
    10311094            /* Here, lc is the match length - MIN_MATCH */
    1032             code = length_code[lc];
    1033             send_code(code+LITERALS+1, ltree); /* send the length code */
     1095            code = _length_code[lc];
     1096            send_code(s, code+LITERALS+1, ltree); /* send the length code */
    10341097            extra = extra_lbits[code];
    10351098            if (extra != 0) {
    10361099                lc -= base_length[code];
    1037                 send_bits(lc, extra);        /* send the extra length bits */
     1100                send_bits(s, lc, extra);       /* send the extra length bits */
    10381101            }
    1039             dist = d_buf[dx++];
    1040             /* Here, dist is the match distance - 1 */
     1102            dist--; /* dist is now the match distance - 1 */
    10411103            code = d_code(dist);
    10421104            Assert (code < D_CODES, "bad d_code");
    10431105
    1044             send_code(code, dtree);       /* send the distance code */
     1106            send_code(s, code, dtree);       /* send the distance code */
    10451107            extra = extra_dbits[code];
    10461108            if (extra != 0) {
    10471109                dist -= base_dist[code];
    1048                 send_bits(dist, extra);   /* send the extra distance bits */
     1110                send_bits(s, dist, extra);   /* send the extra distance bits */
    10491111            }
    10501112        } /* literal or match pair ? */
    1051         flag >>= 1;
    1052     } while (lx < last_lit);
    1053 
    1054     send_code(END_BLOCK, ltree);
    1055 }
    1056 
    1057 /* ===========================================================================
    1058  * Set the file type to ASCII or BINARY, using a crude approximation:
    1059  * binary if more than 20% of the bytes are <= 6 or >= 128, ascii otherwise.
    1060  * IN assertion: the fields freq of dyn_ltree are set and the total of all
    1061  * frequencies does not exceed 64K (to fit in an int on 16 bit machines).
    1062  */
    1063 local void set_file_type()
    1064 {
    1065     int n = 0;
    1066     unsigned ascii_freq = 0;
    1067     unsigned bin_freq = 0;
    1068     while (n < 7)        bin_freq += dyn_ltree[n++].Freq;
    1069     while (n < 128)    ascii_freq += dyn_ltree[n++].Freq;
    1070     while (n < LITERALS) bin_freq += dyn_ltree[n++].Freq;
    1071     *file_type = bin_freq > (ascii_freq >> 2) ? BINARY : ASCII;
    1072 #ifdef FWnotdef
    1073     if (*file_type == BINARY && translate_eol) {
    1074         warn("-l used on binary file", "");
    1075     }
    1076 #endif
    1077 }
     1113
     1114        /* Check that the overlay between pending_buf and d_buf+l_buf is ok: */
     1115        Assert((uInt)(s->pending) < s->lit_bufsize + 2*lx,
     1116               "pendingBuf overflow");
     1117
     1118    } while (lx < s->last_lit);
     1119
     1120    send_code(s, END_BLOCK, ltree);
     1121    s->last_eob_len = ltree[END_BLOCK].Len;
     1122}
     1123
     1124/* ===========================================================================
     1125 * Check if the data type is TEXT or BINARY, using the following algorithm:
     1126 * - TEXT if the two conditions below are satisfied:
     1127 *    a) There are no non-portable control characters belonging to the
     1128 *       "black list" (0..6, 14..25, 28..31).
     1129 *    b) There is at least one printable character belonging to the
     1130 *       "white list" (9 {TAB}, 10 {LF}, 13 {CR}, 32..255).
     1131 * - BINARY otherwise.
     1132 * - The following partially-portable control characters form a
     1133 *   "gray list" that is ignored in this detection algorithm:
     1134 *   (7 {BEL}, 8 {BS}, 11 {VT}, 12 {FF}, 26 {SUB}, 27 {ESC}).
     1135 * IN assertion: the fields Freq of dyn_ltree are set.
     1136 */
     1137local int detect_data_type(s)
     1138    deflate_state *s;
     1139{
     1140    /* black_mask is the bit mask of black-listed bytes
     1141     * set bits 0..6, 14..25, and 28..31
     1142     * 0xf3ffc07f = binary 11110011111111111100000001111111
     1143     */
     1144    unsigned long black_mask = 0xf3ffc07fUL;
     1145    int n;
     1146
     1147    /* Check for non-textual ("black-listed") bytes. */
     1148    for (n = 0; n <= 31; n++, black_mask >>= 1)
     1149        if ((black_mask & 1) && (s->dyn_ltree[n].Freq != 0))
     1150            return Z_BINARY;
     1151
     1152    /* Check for textual ("white-listed") bytes. */
     1153    if (s->dyn_ltree[9].Freq != 0 || s->dyn_ltree[10].Freq != 0
     1154            || s->dyn_ltree[13].Freq != 0)
     1155        return Z_TEXT;
     1156    for (n = 32; n < LITERALS; n++)
     1157        if (s->dyn_ltree[n].Freq != 0)
     1158            return Z_TEXT;
     1159
     1160    /* There are no "black-listed" or "white-listed" bytes:
     1161     * this stream either is empty or has tolerated ("gray-listed") bytes only.
     1162     */
     1163    return Z_BINARY;
     1164}
     1165
     1166/* ===========================================================================
     1167 * Reverse the first len bits of a code, using straightforward code (a faster
     1168 * method would use a table)
     1169 * IN assertion: 1 <= len <= 15
     1170 */
     1171local unsigned bi_reverse(code, len)
     1172    unsigned code; /* the value to invert */
     1173    int len;       /* its bit length */
     1174{
     1175    register unsigned res = 0;
     1176    do {
     1177        res |= code & 1;
     1178        code >>= 1, res <<= 1;
     1179    } while (--len > 0);
     1180    return res >> 1;
     1181}
     1182
     1183/* ===========================================================================
     1184 * Flush the bit buffer, keeping at most 7 bits in it.
     1185 */
     1186local void bi_flush(s)
     1187    deflate_state *s;
     1188{
     1189    if (s->bi_valid == 16) {
     1190        put_short(s, s->bi_buf);
     1191        s->bi_buf = 0;
     1192        s->bi_valid = 0;
     1193    } else if (s->bi_valid >= 8) {
     1194        put_byte(s, (Byte)s->bi_buf);
     1195        s->bi_buf >>= 8;
     1196        s->bi_valid -= 8;
     1197    }
     1198}
     1199
     1200/* ===========================================================================
     1201 * Flush the bit buffer and align the output on a byte boundary
     1202 */
     1203local void bi_windup(s)
     1204    deflate_state *s;
     1205{
     1206    if (s->bi_valid > 8) {
     1207        put_short(s, s->bi_buf);
     1208    } else if (s->bi_valid > 0) {
     1209        put_byte(s, (Byte)s->bi_buf);
     1210    }
     1211    s->bi_buf = 0;
     1212    s->bi_valid = 0;
     1213#ifdef DEBUG
     1214    s->bits_sent = (s->bits_sent+7) & ~7;
     1215#endif
     1216}
     1217
     1218/* ===========================================================================
     1219 * Copy a stored block, storing first the length and its
     1220 * one's complement if requested.
     1221 */
     1222local void copy_block(s, buf, len, header)
     1223    deflate_state *s;
     1224    charf    *buf;    /* the input data */
     1225    unsigned len;     /* its length */
     1226    int      header;  /* true if block header must be written */
     1227{
     1228    bi_windup(s);        /* align on byte boundary */
     1229    s->last_eob_len = 8; /* enough lookahead for inflate */
     1230
     1231    if (header) {
     1232        put_short(s, (ush)len);
     1233        put_short(s, (ush)~len);
     1234#ifdef DEBUG
     1235        s->bits_sent += 2*16;
     1236#endif
     1237    }
     1238#ifdef DEBUG
     1239    s->bits_sent += (ulg)len<<3;
     1240#endif
     1241    while (len--) {
     1242        put_byte(s, *buf++);
     1243    }
     1244}
Note: See TracChangeset for help on using the changeset viewer.