Changeset 2182


Ignore:
Timestamp:
Apr 5, 2011, 5:13:03 PM (3 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.