The Design and Implementation of the FreeBSD Operating System, Second Edition
Now available: The Design and Implementation of the FreeBSD Operating System (Second Edition)


[ source navigation ] [ diff markup ] [ identifier search ] [ freetext search ] [ file search ] [ list types ] [ track identifier ]

FreeBSD/Linux Kernel Cross Reference
sys/net/zlib.c

Version: -  FREEBSD  -  FREEBSD-13-STABLE  -  FREEBSD-13-0  -  FREEBSD-12-STABLE  -  FREEBSD-12-0  -  FREEBSD-11-STABLE  -  FREEBSD-11-0  -  FREEBSD-10-STABLE  -  FREEBSD-10-0  -  FREEBSD-9-STABLE  -  FREEBSD-9-0  -  FREEBSD-8-STABLE  -  FREEBSD-8-0  -  FREEBSD-7-STABLE  -  FREEBSD-7-0  -  FREEBSD-6-STABLE  -  FREEBSD-6-0  -  FREEBSD-5-STABLE  -  FREEBSD-5-0  -  FREEBSD-4-STABLE  -  FREEBSD-3-STABLE  -  FREEBSD22  -  l41  -  OPENBSD  -  linux-2.6  -  MK84  -  PLAN9  -  xnu-8792 
SearchContext: -  none  -  3  -  10 

    1 /*
    2  * This file is derived from various .h and .c files from the zlib-1.0.4
    3  * distribution by Jean-loup Gailly and Mark Adler, with some additions
    4  * by Paul Mackerras to aid in implementing Deflate compression and
    5  * decompression for PPP packets.  See zlib.h for conditions of
    6  * distribution and use.
    7  *
    8  * Changes that have been made include:
    9  * - added Z_PACKET_FLUSH (see zlib.h for details)
   10  * - added inflateIncomp and deflateOutputPending
   11  * - allow strm->next_out to be NULL, meaning discard the output
   12  *
   13  * $FreeBSD: releng/5.3/sys/net/zlib.c 136588 2004-10-16 08:43:07Z cvs2svn $
   14  */
   15 
   16 /* 
   17  *  ==FILEVERSION 971210==
   18  *
   19  * This marker is used by the Linux installation script to determine
   20  * whether an up-to-date version of this file is already installed.
   21  */
   22 
   23 #define NO_DUMMY_DECL
   24 #define NO_ZCFUNCS
   25 #define MY_ZCALLOC
   26 
   27 #if defined(__FreeBSD__) && defined(_KERNEL)
   28 #define inflate inflate_ppp     /* FreeBSD already has an inflate :-( */
   29 #endif
   30 
   31 
   32 /* +++ zutil.h */
   33 /* zutil.h -- internal interface and configuration of the compression library
   34  * Copyright (C) 1995-1996 Jean-loup Gailly.
   35  * For conditions of distribution and use, see copyright notice in zlib.h
   36  */
   37 
   38 /* WARNING: this file should *not* be used by applications. It is
   39    part of the implementation of the compression library and is
   40    subject to change. Applications should only use zlib.h.
   41  */
   42 
   43 /* From: zutil.h,v 1.16 1996/07/24 13:41:13 me Exp $ */
   44 
   45 #ifndef _Z_UTIL_H
   46 #define _Z_UTIL_H
   47 
   48 #ifdef _KERNEL
   49 #include <net/zlib.h>
   50 #else
   51 #include "zlib.h"
   52 #endif
   53 
   54 #ifdef _KERNEL
   55 /* Assume this is a *BSD or SVR4 kernel */
   56 #include <sys/types.h>
   57 #include <sys/time.h>
   58 #include <sys/systm.h>
   59 #include <sys/param.h>
   60 #include <sys/kernel.h>
   61 #include <sys/module.h>
   62 #  define HAVE_MEMCPY
   63 
   64 #else
   65 #if defined(__KERNEL__)
   66 /* Assume this is a Linux kernel */
   67 #include <linux/string.h>
   68 #define HAVE_MEMCPY
   69 
   70 #else /* not kernel */
   71 
   72 #if defined(MSDOS)||defined(VMS)||defined(CRAY)||defined(WIN32)||defined(RISCOS)
   73 #   include <stddef.h>
   74 #   include <errno.h>
   75 #else
   76     extern int errno;
   77 #endif
   78 #ifdef STDC
   79 #  include <string.h>
   80 #  include <stdlib.h>
   81 #endif
   82 #endif /* __KERNEL__ */
   83 #endif /* _KERNEL */
   84 
   85 #ifndef local
   86 #  define local static
   87 #endif
   88 /* compile with -Dlocal if your debugger can't find static symbols */
   89 
   90 typedef unsigned char  uch;
   91 typedef uch FAR uchf;
   92 typedef unsigned short ush;
   93 typedef ush FAR ushf;
   94 typedef unsigned long  ulg;
   95 
   96 extern const char *z_errmsg[10]; /* indexed by 2-zlib_error */
   97 /* (size given to avoid silly warnings with Visual C++) */
   98 
   99 #define ERR_MSG(err) z_errmsg[Z_NEED_DICT-(err)]
  100 
  101 #define ERR_RETURN(strm,err) \
  102   return (strm->msg = (const char*)ERR_MSG(err), (err))
  103 /* To be used only when the state is known to be valid */
  104 
  105         /* common constants */
  106 
  107 #ifndef DEF_WBITS
  108 #  define DEF_WBITS MAX_WBITS
  109 #endif
  110 /* default windowBits for decompression. MAX_WBITS is for compression only */
  111 
  112 #if MAX_MEM_LEVEL >= 8
  113 #  define DEF_MEM_LEVEL 8
  114 #else
  115 #  define DEF_MEM_LEVEL  MAX_MEM_LEVEL
  116 #endif
  117 /* default memLevel */
  118 
  119 #define STORED_BLOCK 0
  120 #define STATIC_TREES 1
  121 #define DYN_TREES    2
  122 /* The three kinds of block type */
  123 
  124 #define MIN_MATCH  3
  125 #define MAX_MATCH  258
  126 /* The minimum and maximum match lengths */
  127 
  128 #define PRESET_DICT 0x20 /* preset dictionary flag in zlib header */
  129 
  130         /* target dependencies */
  131 
  132 #ifdef MSDOS
  133 #  define OS_CODE  0x00
  134 #  ifdef __TURBOC__
  135 #    include <alloc.h>
  136 #  else /* MSC or DJGPP */
  137 #    include <malloc.h>
  138 #  endif
  139 #endif
  140 
  141 #ifdef OS2
  142 #  define OS_CODE  0x06
  143 #endif
  144 
  145 #ifdef WIN32 /* Window 95 & Windows NT */
  146 #  define OS_CODE  0x0b
  147 #endif
  148 
  149 #if defined(VAXC) || defined(VMS)
  150 #  define OS_CODE  0x02
  151 #  define FOPEN(name, mode) \
  152      fopen((name), (mode), "mbc=60", "ctx=stm", "rfm=fix", "mrs=512")
  153 #endif
  154 
  155 #ifdef AMIGA
  156 #  define OS_CODE  0x01
  157 #endif
  158 
  159 #if defined(ATARI) || defined(atarist)
  160 #  define OS_CODE  0x05
  161 #endif
  162 
  163 #ifdef MACOS
  164 #  define OS_CODE  0x07
  165 #endif
  166 
  167 #ifdef __50SERIES /* Prime/PRIMOS */
  168 #  define OS_CODE  0x0F
  169 #endif
  170 
  171 #ifdef TOPS20
  172 #  define OS_CODE  0x0a
  173 #endif
  174 
  175 #if defined(_BEOS_) || defined(RISCOS)
  176 #  define fdopen(fd,mode) NULL /* No fdopen() */
  177 #endif
  178 
  179         /* Common defaults */
  180 
  181 #ifndef OS_CODE
  182 #  define OS_CODE  0x03  /* assume Unix */
  183 #endif
  184 
  185 #ifndef FOPEN
  186 #  define FOPEN(name, mode) fopen((name), (mode))
  187 #endif
  188 
  189          /* functions */
  190 
  191 #ifdef HAVE_STRERROR
  192    extern char *strerror OF((int));
  193 #  define zstrerror(errnum) strerror(errnum)
  194 #else
  195 #  define zstrerror(errnum) ""
  196 #endif
  197 
  198 #if defined(pyr)
  199 #  define NO_MEMCPY
  200 #endif
  201 #if (defined(M_I86SM) || defined(M_I86MM)) && !defined(_MSC_VER)
  202  /* Use our own functions for small and medium model with MSC <= 5.0.
  203   * You may have to use the same strategy for Borland C (untested).
  204   */
  205 #  define NO_MEMCPY
  206 #endif
  207 #if defined(STDC) && !defined(HAVE_MEMCPY) && !defined(NO_MEMCPY)
  208 #  define HAVE_MEMCPY
  209 #endif
  210 #ifdef HAVE_MEMCPY
  211 #  ifdef SMALL_MEDIUM /* MSDOS small or medium model */
  212 #    define zmemcpy _fmemcpy
  213 #    define zmemcmp _fmemcmp
  214 #    define zmemzero(dest, len) _fmemset(dest, 0, len)
  215 #  else
  216 #    define zmemcpy memcpy
  217 #    define zmemcmp memcmp
  218 #    define zmemzero(dest, len) memset(dest, 0, len)
  219 #  endif
  220 #else
  221    extern void zmemcpy  OF((Bytef* dest, Bytef* source, uInt len));
  222    extern int  zmemcmp  OF((Bytef* s1,   Bytef* s2, uInt len));
  223    extern void zmemzero OF((Bytef* dest, uInt len));
  224 #endif
  225 
  226 /* Diagnostic functions */
  227 #ifdef DEBUG_ZLIB
  228 #  include <stdio.h>
  229 #  ifndef verbose
  230 #    define verbose 0
  231 #  endif
  232    extern void z_error    OF((char *m));
  233 #  define Assert(cond,msg) {if(!(cond)) z_error(msg);}
  234 #  define Trace(x) fprintf x
  235 #  define Tracev(x) {if (verbose) fprintf x ;}
  236 #  define Tracevv(x) {if (verbose>1) fprintf x ;}
  237 #  define Tracec(c,x) {if (verbose && (c)) fprintf x ;}
  238 #  define Tracecv(c,x) {if (verbose>1 && (c)) fprintf x ;}
  239 #else
  240 #  define Assert(cond,msg)
  241 #  define Trace(x)
  242 #  define Tracev(x)
  243 #  define Tracevv(x)
  244 #  define Tracec(c,x)
  245 #  define Tracecv(c,x)
  246 #endif
  247 
  248 
  249 typedef uLong (*check_func) OF((uLong check, const Bytef *buf, uInt len));
  250 
  251 voidpf zcalloc OF((voidpf opaque, unsigned items, unsigned size));
  252 void   zcfree  OF((voidpf opaque, voidpf ptr));
  253 
  254 #define ZALLOC(strm, items, size) \
  255            (*((strm)->zalloc))((strm)->opaque, (items), (size))
  256 #define ZFREE(strm, addr)  (*((strm)->zfree))((strm)->opaque, (voidpf)(addr))
  257 #define TRY_FREE(s, p) {if (p) ZFREE(s, p);}
  258 
  259 #endif /* _Z_UTIL_H */
  260 /* --- zutil.h */
  261 
  262 /* +++ deflate.h */
  263 /* deflate.h -- internal compression state
  264  * Copyright (C) 1995-1996 Jean-loup Gailly
  265  * For conditions of distribution and use, see copyright notice in zlib.h 
  266  */
  267 
  268 /* WARNING: this file should *not* be used by applications. It is
  269    part of the implementation of the compression library and is
  270    subject to change. Applications should only use zlib.h.
  271  */
  272 
  273 /* From: deflate.h,v 1.10 1996/07/02 12:41:00 me Exp $ */
  274 
  275 #ifndef _DEFLATE_H
  276 #define _DEFLATE_H
  277 
  278 /* #include "zutil.h" */
  279 
  280 /* ===========================================================================
  281  * Internal compression state.
  282  */
  283 
  284 #define LENGTH_CODES 29
  285 /* number of length codes, not counting the special END_BLOCK code */
  286 
  287 #define LITERALS  256
  288 /* number of literal bytes 0..255 */
  289 
  290 #define L_CODES (LITERALS+1+LENGTH_CODES)
  291 /* number of Literal or Length codes, including the END_BLOCK code */
  292 
  293 #define D_CODES   30
  294 /* number of distance codes */
  295 
  296 #define BL_CODES  19
  297 /* number of codes used to transfer the bit lengths */
  298 
  299 #define HEAP_SIZE (2*L_CODES+1)
  300 /* maximum heap size */
  301 
  302 #define MAX_BITS 15
  303 /* All codes must not exceed MAX_BITS bits */
  304 
  305 #define INIT_STATE    42
  306 #define BUSY_STATE   113
  307 #define FINISH_STATE 666
  308 /* Stream status */
  309 
  310 
  311 /* Data structure describing a single value and its code string. */
  312 typedef struct ct_data_s {
  313     union {
  314         ush  freq;       /* frequency count */
  315         ush  code;       /* bit string */
  316     } fc;
  317     union {
  318         ush  dad;        /* father node in Huffman tree */
  319         ush  len;        /* length of bit string */
  320     } dl;
  321 } FAR ct_data;
  322 
  323 #define Freq fc.freq
  324 #define Code fc.code
  325 #define Dad  dl.dad
  326 #define Len  dl.len
  327 
  328 typedef struct static_tree_desc_s  static_tree_desc;
  329 
  330 typedef struct tree_desc_s {
  331     ct_data *dyn_tree;           /* the dynamic tree */
  332     int     max_code;            /* largest code with non zero frequency */
  333     static_tree_desc *stat_desc; /* the corresponding static tree */
  334 } FAR tree_desc;
  335 
  336 typedef ush Pos;
  337 typedef Pos FAR Posf;
  338 typedef unsigned IPos;
  339 
  340 /* A Pos is an index in the character window. We use short instead of int to
  341  * save space in the various tables. IPos is used only for parameter passing.
  342  */
  343 
  344 typedef struct deflate_state {
  345     z_streamp strm;      /* pointer back to this zlib stream */
  346     int   status;        /* as the name implies */
  347     Bytef *pending_buf;  /* output still pending */
  348     ulg   pending_buf_size; /* size of pending_buf */
  349     Bytef *pending_out;  /* next pending byte to output to the stream */
  350     int   pending;       /* nb of bytes in the pending buffer */
  351     int   noheader;      /* suppress zlib header and adler32 */
  352     Byte  data_type;     /* UNKNOWN, BINARY or ASCII */
  353     Byte  method;        /* STORED (for zip only) or DEFLATED */
  354     int   last_flush;    /* value of flush param for previous deflate call */
  355 
  356                 /* used by deflate.c: */
  357 
  358     uInt  w_size;        /* LZ77 window size (32K by default) */
  359     uInt  w_bits;        /* log2(w_size)  (8..16) */
  360     uInt  w_mask;        /* w_size - 1 */
  361 
  362     Bytef *window;
  363     /* Sliding window. Input bytes are read into the second half of the window,
  364      * and move to the first half later to keep a dictionary of at least wSize
  365      * bytes. With this organization, matches are limited to a distance of
  366      * wSize-MAX_MATCH bytes, but this ensures that IO is always
  367      * performed with a length multiple of the block size. Also, it limits
  368      * the window size to 64K, which is quite useful on MSDOS.
  369      * To do: use the user input buffer as sliding window.
  370      */
  371 
  372     ulg window_size;
  373     /* Actual size of window: 2*wSize, except when the user input buffer
  374      * is directly used as sliding window.
  375      */
  376 
  377     Posf *prev;
  378     /* Link to older string with same hash index. To limit the size of this
  379      * array to 64K, this link is maintained only for the last 32K strings.
  380      * An index in this array is thus a window index modulo 32K.
  381      */
  382 
  383     Posf *head; /* Heads of the hash chains or NIL. */
  384 
  385     uInt  ins_h;          /* hash index of string to be inserted */
  386     uInt  hash_size;      /* number of elements in hash table */
  387     uInt  hash_bits;      /* log2(hash_size) */
  388     uInt  hash_mask;      /* hash_size-1 */
  389 
  390     uInt  hash_shift;
  391     /* Number of bits by which ins_h must be shifted at each input
  392      * step. It must be such that after MIN_MATCH steps, the oldest
  393      * byte no longer takes part in the hash key, that is:
  394      *   hash_shift * MIN_MATCH >= hash_bits
  395      */
  396 
  397     long block_start;
  398     /* Window position at the beginning of the current output block. Gets
  399      * negative when the window is moved backwards.
  400      */
  401 
  402     uInt match_length;           /* length of best match */
  403     IPos prev_match;             /* previous match */
  404     int match_available;         /* set if previous match exists */
  405     uInt strstart;               /* start of string to insert */
  406     uInt match_start;            /* start of matching string */
  407     uInt lookahead;              /* number of valid bytes ahead in window */
  408 
  409     uInt prev_length;
  410     /* Length of the best match at previous step. Matches not greater than this
  411      * are discarded. This is used in the lazy match evaluation.
  412      */
  413 
  414     uInt max_chain_length;
  415     /* To speed up deflation, hash chains are never searched beyond this
  416      * length.  A higher limit improves compression ratio but degrades the
  417      * speed.
  418      */
  419 
  420     uInt max_lazy_match;
  421     /* Attempt to find a better match only when the current match is strictly
  422      * smaller than this value. This mechanism is used only for compression
  423      * levels >= 4.
  424      */
  425 #   define max_insert_length  max_lazy_match
  426     /* Insert new strings in the hash table only if the match length is not
  427      * greater than this length. This saves time but degrades compression.
  428      * max_insert_length is used only for compression levels <= 3.
  429      */
  430 
  431     int level;    /* compression level (1..9) */
  432     int strategy; /* favor or force Huffman coding*/
  433 
  434     uInt good_match;
  435     /* Use a faster search when the previous match is longer than this */
  436 
  437     int nice_match; /* Stop searching when current match exceeds this */
  438 
  439                 /* used by trees.c: */
  440     /* Didn't use ct_data typedef below to supress compiler warning */
  441     struct ct_data_s dyn_ltree[HEAP_SIZE];   /* literal and length tree */
  442     struct ct_data_s dyn_dtree[2*D_CODES+1]; /* distance tree */
  443     struct ct_data_s bl_tree[2*BL_CODES+1];  /* Huffman tree for bit lengths */
  444 
  445     struct tree_desc_s l_desc;               /* desc. for literal tree */
  446     struct tree_desc_s d_desc;               /* desc. for distance tree */
  447     struct tree_desc_s bl_desc;              /* desc. for bit length tree */
  448 
  449     ush bl_count[MAX_BITS+1];
  450     /* number of codes at each bit length for an optimal tree */
  451 
  452     int heap[2*L_CODES+1];      /* heap used to build the Huffman trees */
  453     int heap_len;               /* number of elements in the heap */
  454     int heap_max;               /* element of largest frequency */
  455     /* The sons of heap[n] are heap[2*n] and heap[2*n+1]. heap[0] is not used.
  456      * The same heap array is used to build all trees.
  457      */
  458 
  459     uch depth[2*L_CODES+1];
  460     /* Depth of each subtree used as tie breaker for trees of equal frequency
  461      */
  462 
  463     uchf *l_buf;          /* buffer for literals or lengths */
  464 
  465     uInt  lit_bufsize;
  466     /* Size of match buffer for literals/lengths.  There are 4 reasons for
  467      * limiting lit_bufsize to 64K:
  468      *   - frequencies can be kept in 16 bit counters
  469      *   - if compression is not successful for the first block, all input
  470      *     data is still in the window so we can still emit a stored block even
  471      *     when input comes from standard input.  (This can also be done for
  472      *     all blocks if lit_bufsize is not greater than 32K.)
  473      *   - if compression is not successful for a file smaller than 64K, we can
  474      *     even emit a stored file instead of a stored block (saving 5 bytes).
  475      *     This is applicable only for zip (not gzip or zlib).
  476      *   - creating new Huffman trees less frequently may not provide fast
  477      *     adaptation to changes in the input data statistics. (Take for
  478      *     example a binary file with poorly compressible code followed by
  479      *     a highly compressible string table.) Smaller buffer sizes give
  480      *     fast adaptation but have of course the overhead of transmitting
  481      *     trees more frequently.
  482      *   - I can't count above 4
  483      */
  484 
  485     uInt last_lit;      /* running index in l_buf */
  486 
  487     ushf *d_buf;
  488     /* Buffer for distances. To simplify the code, d_buf and l_buf have
  489      * the same number of elements. To use different lengths, an extra flag
  490      * array would be necessary.
  491      */
  492 
  493     ulg opt_len;        /* bit length of current block with optimal trees */
  494     ulg static_len;     /* bit length of current block with static trees */
  495     ulg compressed_len; /* total bit length of compressed file */
  496     uInt matches;       /* number of string matches in current block */
  497     int last_eob_len;   /* bit length of EOB code for last block */
  498 
  499 #ifdef DEBUG_ZLIB
  500     ulg bits_sent;      /* bit length of the compressed data */
  501 #endif
  502 
  503     ush bi_buf;
  504     /* Output buffer. bits are inserted starting at the bottom (least
  505      * significant bits).
  506      */
  507     int bi_valid;
  508     /* Number of valid bits in bi_buf.  All bits above the last valid bit
  509      * are always zero.
  510      */
  511 
  512 } FAR deflate_state;
  513 
  514 /* Output a byte on the stream.
  515  * IN assertion: there is enough room in pending_buf.
  516  */
  517 #define put_byte(s, c) {s->pending_buf[s->pending++] = (c);}
  518 
  519 
  520 #define MIN_LOOKAHEAD (MAX_MATCH+MIN_MATCH+1)
  521 /* Minimum amount of lookahead, except at the end of the input file.
  522  * See deflate.c for comments about the MIN_MATCH+1.
  523  */
  524 
  525 #define MAX_DIST(s)  ((s)->w_size-MIN_LOOKAHEAD)
  526 /* In order to simplify the code, particularly on 16 bit machines, match
  527  * distances are limited to MAX_DIST instead of WSIZE.
  528  */
  529 
  530         /* in trees.c */
  531 void _tr_init         OF((deflate_state *s));
  532 int  _tr_tally        OF((deflate_state *s, unsigned dist, unsigned lc));
  533 ulg  _tr_flush_block  OF((deflate_state *s, charf *buf, ulg stored_len,
  534                           int eof));
  535 void _tr_align        OF((deflate_state *s));
  536 void _tr_stored_block OF((deflate_state *s, charf *buf, ulg stored_len,
  537                           int eof));
  538 void _tr_stored_type_only OF((deflate_state *));
  539 
  540 #endif
  541 /* --- deflate.h */
  542 
  543 /* +++ deflate.c */
  544 /* deflate.c -- compress data using the deflation algorithm
  545  * Copyright (C) 1995-1996 Jean-loup Gailly.
  546  * For conditions of distribution and use, see copyright notice in zlib.h 
  547  */
  548 
  549 /*
  550  *  ALGORITHM
  551  *
  552  *      The "deflation" process depends on being able to identify portions
  553  *      of the input text which are identical to earlier input (within a
  554  *      sliding window trailing behind the input currently being processed).
  555  *
  556  *      The most straightforward technique turns out to be the fastest for
  557  *      most input files: try all possible matches and select the longest.
  558  *      The key feature of this algorithm is that insertions into the string
  559  *      dictionary are very simple and thus fast, and deletions are avoided
  560  *      completely. Insertions are performed at each input character, whereas
  561  *      string matches are performed only when the previous match ends. So it
  562  *      is preferable to spend more time in matches to allow very fast string
  563  *      insertions and avoid deletions. The matching algorithm for small
  564  *      strings is inspired from that of Rabin & Karp. A brute force approach
  565  *      is used to find longer strings when a small match has been found.
  566  *      A similar algorithm is used in comic (by Jan-Mark Wams) and freeze
  567  *      (by Leonid Broukhis).
  568  *         A previous version of this file used a more sophisticated algorithm
  569  *      (by Fiala and Greene) which is guaranteed to run in linear amortized
  570  *      time, but has a larger average cost, uses more memory and is patented.
  571  *      However the F&G algorithm may be faster for some highly redundant
  572  *      files if the parameter max_chain_length (described below) is too large.
  573  *
  574  *  ACKNOWLEDGEMENTS
  575  *
  576  *      The idea of lazy evaluation of matches is due to Jan-Mark Wams, and
  577  *      I found it in 'freeze' written by Leonid Broukhis.
  578  *      Thanks to many people for bug reports and testing.
  579  *
  580  *  REFERENCES
  581  *
  582  *      Deutsch, L.P.,"DEFLATE Compressed Data Format Specification".
  583  *      Available in ftp://ds.internic.net/rfc/rfc1951.txt
  584  *
  585  *      A description of the Rabin and Karp algorithm is given in the book
  586  *         "Algorithms" by R. Sedgewick, Addison-Wesley, p252.
  587  *
  588  *      Fiala,E.R., and Greene,D.H.
  589  *         Data Compression with Finite Windows, Comm.ACM, 32,4 (1989) 490-595
  590  *
  591  */
  592 
  593 /* From: deflate.c,v 1.15 1996/07/24 13:40:58 me Exp $ */
  594 
  595 /* #include "deflate.h" */
  596 
  597 char deflate_copyright[] = " deflate 1.0.4 Copyright 1995-1996 Jean-loup Gailly ";
  598 /*
  599   If you use the zlib library in a product, an acknowledgment is welcome
  600   in the documentation of your product. If for some reason you cannot
  601   include such an acknowledgment, I would appreciate that you keep this
  602   copyright string in the executable of your product.
  603  */
  604 
  605 /* ===========================================================================
  606  *  Function prototypes.
  607  */
  608 typedef enum {
  609     need_more,      /* block not completed, need more input or more output */
  610     block_done,     /* block flush performed */
  611     finish_started, /* finish started, need only more output at next deflate */
  612     finish_done     /* finish done, accept no more input or output */
  613 } block_state;
  614 
  615 typedef block_state (*compress_func) OF((deflate_state *s, int flush));
  616 /* Compression function. Returns the block state after the call. */
  617 
  618 local void fill_window    OF((deflate_state *s));
  619 local block_state deflate_stored OF((deflate_state *s, int flush));
  620 local block_state deflate_fast   OF((deflate_state *s, int flush));
  621 local block_state deflate_slow   OF((deflate_state *s, int flush));
  622 local void lm_init        OF((deflate_state *s));
  623 local void putShortMSB    OF((deflate_state *s, uInt b));
  624 local void flush_pending  OF((z_streamp strm));
  625 local int read_buf        OF((z_streamp strm, charf *buf, unsigned size));
  626 #ifdef ASMV
  627       void match_init OF((void)); /* asm code initialization */
  628       uInt longest_match  OF((deflate_state *s, IPos cur_match));
  629 #else
  630 local uInt longest_match  OF((deflate_state *s, IPos cur_match));
  631 #endif
  632 
  633 #ifdef DEBUG_ZLIB
  634 local  void check_match OF((deflate_state *s, IPos start, IPos match,
  635                             int length));
  636 #endif
  637 
  638 /* ===========================================================================
  639  * Local data
  640  */
  641 
  642 #define NIL 0
  643 /* Tail of hash chains */
  644 
  645 #ifndef TOO_FAR
  646 #  define TOO_FAR 4096
  647 #endif
  648 /* Matches of length 3 are discarded if their distance exceeds TOO_FAR */
  649 
  650 #define MIN_LOOKAHEAD (MAX_MATCH+MIN_MATCH+1)
  651 /* Minimum amount of lookahead, except at the end of the input file.
  652  * See deflate.c for comments about the MIN_MATCH+1.
  653  */
  654 
  655 /* Values for max_lazy_match, good_match and max_chain_length, depending on
  656  * the desired pack level (0..9). The values given below have been tuned to
  657  * exclude worst case performance for pathological files. Better values may be
  658  * found for specific files.
  659  */
  660 typedef struct config_s {
  661    ush good_length; /* reduce lazy search above this match length */
  662    ush max_lazy;    /* do not perform lazy search above this match length */
  663    ush nice_length; /* quit search above this match length */
  664    ush max_chain;
  665    compress_func func;
  666 } config;
  667 
  668 local config configuration_table[10] = {
  669 /*      good lazy nice chain */
  670 /* 0 */ {0,    0,  0,    0, deflate_stored},  /* store only */
  671 /* 1 */ {4,    4,  8,    4, deflate_fast}, /* maximum speed, no lazy matches */
  672 /* 2 */ {4,    5, 16,    8, deflate_fast},
  673 /* 3 */ {4,    6, 32,   32, deflate_fast},
  674 
  675 /* 4 */ {4,    4, 16,   16, deflate_slow},  /* lazy matches */
  676 /* 5 */ {8,   16, 32,   32, deflate_slow},
  677 /* 6 */ {8,   16, 128, 128, deflate_slow},
  678 /* 7 */ {8,   32, 128, 256, deflate_slow},
  679 /* 8 */ {32, 128, 258, 1024, deflate_slow},
  680 /* 9 */ {32, 258, 258, 4096, deflate_slow}}; /* maximum compression */
  681 
  682 /* Note: the deflate() code requires max_lazy >= MIN_MATCH and max_chain >= 4
  683  * For deflate_fast() (levels <= 3) good is ignored and lazy has a different
  684  * meaning.
  685  */
  686 
  687 #define EQUAL 0
  688 /* result of memcmp for equal strings */
  689 
  690 #ifndef NO_DUMMY_DECL
  691 struct static_tree_desc_s {int dummy;}; /* for buggy compilers */
  692 #endif
  693 
  694 /* ===========================================================================
  695  * Update a hash value with the given input byte
  696  * IN  assertion: all calls to to UPDATE_HASH are made with consecutive
  697  *    input characters, so that a running hash key can be computed from the
  698  *    previous key instead of complete recalculation each time.
  699  */
  700 #define UPDATE_HASH(s,h,c) (h = (((h)<<s->hash_shift) ^ (c)) & s->hash_mask)
  701 
  702 
  703 /* ===========================================================================
  704  * Insert string str in the dictionary and set match_head to the previous head
  705  * of the hash chain (the most recent string with same hash key). Return
  706  * the previous length of the hash chain.
  707  * IN  assertion: all calls to to INSERT_STRING are made with consecutive
  708  *    input characters and the first MIN_MATCH bytes of str are valid
  709  *    (except for the last MIN_MATCH-1 bytes of the input file).
  710  */
  711 #define INSERT_STRING(s, str, match_head) \
  712    (UPDATE_HASH(s, s->ins_h, s->window[(str) + (MIN_MATCH-1)]), \
  713     s->prev[(str) & s->w_mask] = match_head = s->head[s->ins_h], \
  714     s->head[s->ins_h] = (Pos)(str))
  715 
  716 /* ===========================================================================
  717  * Initialize the hash table (avoiding 64K overflow for 16 bit systems).
  718  * prev[] will be initialized on the fly.
  719  */
  720 #define CLEAR_HASH(s) \
  721     s->head[s->hash_size-1] = NIL; \
  722     zmemzero((charf *)s->head, (unsigned)(s->hash_size-1)*sizeof(*s->head));
  723 
  724 /* ========================================================================= */
  725 int deflateInit_(strm, level, version, stream_size)
  726     z_streamp strm;
  727     int level;
  728     const char *version;
  729     int stream_size;
  730 {
  731     return deflateInit2_(strm, level, Z_DEFLATED, MAX_WBITS, DEF_MEM_LEVEL,
  732                          Z_DEFAULT_STRATEGY, version, stream_size);
  733     /* To do: ignore strm->next_in if we use it as window */
  734 }
  735 
  736 /* ========================================================================= */
  737 int deflateInit2_(strm, level, method, windowBits, memLevel, strategy,
  738                   version, stream_size)
  739     z_streamp strm;
  740     int  level;
  741     int  method;
  742     int  windowBits;
  743     int  memLevel;
  744     int  strategy;
  745     const char *version;
  746     int stream_size;
  747 {
  748     deflate_state *s;
  749     int noheader = 0;
  750     static char* my_version = ZLIB_VERSION;
  751 
  752     ushf *overlay;
  753     /* We overlay pending_buf and d_buf+l_buf. This works since the average
  754      * output size for (length,distance) codes is <= 24 bits.
  755      */
  756 
  757     if (version == Z_NULL || version[0] != my_version[0] ||
  758         stream_size != sizeof(z_stream)) {
  759         return Z_VERSION_ERROR;
  760     }
  761     if (strm == Z_NULL) return Z_STREAM_ERROR;
  762 
  763     strm->msg = Z_NULL;
  764 #ifndef NO_ZCFUNCS
  765     if (strm->zalloc == Z_NULL) {
  766         strm->zalloc = zcalloc;
  767         strm->opaque = (voidpf)0;
  768     }
  769     if (strm->zfree == Z_NULL) strm->zfree = zcfree;
  770 #endif
  771 
  772     if (level == Z_DEFAULT_COMPRESSION) level = 6;
  773 
  774     if (windowBits < 0) { /* undocumented feature: suppress zlib header */
  775         noheader = 1;
  776         windowBits = -windowBits;
  777     }
  778     if (memLevel < 1 || memLevel > MAX_MEM_LEVEL || method != Z_DEFLATED ||
  779         windowBits < 9 || windowBits > 15 || level < 0 || level > 9 ||
  780         strategy < 0 || strategy > Z_HUFFMAN_ONLY) {
  781         return Z_STREAM_ERROR;
  782     }
  783     s = (deflate_state *) ZALLOC(strm, 1, sizeof(deflate_state));
  784     if (s == Z_NULL) return Z_MEM_ERROR;
  785     strm->state = (struct internal_state FAR *)s;
  786     s->strm = strm;
  787 
  788     s->noheader = noheader;
  789     s->w_bits = windowBits;
  790     s->w_size = 1 << s->w_bits;
  791     s->w_mask = s->w_size - 1;
  792 
  793     s->hash_bits = memLevel + 7;
  794     s->hash_size = 1 << s->hash_bits;
  795     s->hash_mask = s->hash_size - 1;
  796     s->hash_shift =  ((s->hash_bits+MIN_MATCH-1)/MIN_MATCH);
  797 
  798     s->window = (Bytef *) ZALLOC(strm, s->w_size, 2*sizeof(Byte));
  799     s->prev   = (Posf *)  ZALLOC(strm, s->w_size, sizeof(Pos));
  800     s->head   = (Posf *)  ZALLOC(strm, s->hash_size, sizeof(Pos));
  801 
  802     s->lit_bufsize = 1 << (memLevel + 6); /* 16K elements by default */
  803 
  804     overlay = (ushf *) ZALLOC(strm, s->lit_bufsize, sizeof(ush)+2);
  805     s->pending_buf = (uchf *) overlay;
  806     s->pending_buf_size = (ulg)s->lit_bufsize * (sizeof(ush)+2L);
  807 
  808     if (s->window == Z_NULL || s->prev == Z_NULL || s->head == Z_NULL ||
  809         s->pending_buf == Z_NULL) {
  810         strm->msg = (const char*)ERR_MSG(Z_MEM_ERROR);
  811         deflateEnd (strm);
  812         return Z_MEM_ERROR;
  813     }
  814     s->d_buf = overlay + s->lit_bufsize/sizeof(ush);
  815     s->l_buf = s->pending_buf + (1+sizeof(ush))*s->lit_bufsize;
  816 
  817     s->level = level;
  818     s->strategy = strategy;
  819     s->method = (Byte)method;
  820 
  821     return deflateReset(strm);
  822 }
  823 
  824 /* ========================================================================= */
  825 int deflateSetDictionary (strm, dictionary, dictLength)
  826     z_streamp strm;
  827     const Bytef *dictionary;
  828     uInt  dictLength;
  829 {
  830     deflate_state *s;
  831     uInt length = dictLength;
  832     uInt n;
  833     IPos hash_head = 0;
  834 
  835     if (strm == Z_NULL || strm->state == Z_NULL || dictionary == Z_NULL)
  836         return Z_STREAM_ERROR;
  837 
  838     s = (deflate_state *) strm->state;
  839     if (s->status != INIT_STATE) return Z_STREAM_ERROR;
  840 
  841     strm->adler = adler32(strm->adler, dictionary, dictLength);
  842 
  843     if (length < MIN_MATCH) return Z_OK;
  844     if (length > MAX_DIST(s)) {
  845         length = MAX_DIST(s);
  846 #ifndef USE_DICT_HEAD
  847         dictionary += dictLength - length; /* use the tail of the dictionary */
  848 #endif
  849     }
  850     zmemcpy((charf *)s->window, dictionary, length);
  851     s->strstart = length;
  852     s->block_start = (long)length;
  853 
  854     /* Insert all strings in the hash table (except for the last two bytes).
  855      * s->lookahead stays null, so s->ins_h will be recomputed at the next
  856      * call of fill_window.
  857      */
  858     s->ins_h = s->window[0];
  859     UPDATE_HASH(s, s->ins_h, s->window[1]);
  860     for (n = 0; n <= length - MIN_MATCH; n++) {
  861         INSERT_STRING(s, n, hash_head);
  862     }
  863     if (hash_head) hash_head = 0;  /* to make compiler happy */
  864     return Z_OK;
  865 }
  866 
  867 /* ========================================================================= */
  868 int deflateReset (strm)
  869     z_streamp strm;
  870 {
  871     deflate_state *s;
  872     
  873     if (strm == Z_NULL || strm->state == Z_NULL ||
  874         strm->zalloc == Z_NULL || strm->zfree == Z_NULL) return Z_STREAM_ERROR;
  875 
  876     strm->total_in = strm->total_out = 0;
  877     strm->msg = Z_NULL; /* use zfree if we ever allocate msg dynamically */
  878     strm->data_type = Z_UNKNOWN;
  879 
  880     s = (deflate_state *)strm->state;
  881     s->pending = 0;
  882     s->pending_out = s->pending_buf;
  883 
  884     if (s->noheader < 0) {
  885         s->noheader = 0; /* was set to -1 by deflate(..., Z_FINISH); */
  886     }
  887     s->status = s->noheader ? BUSY_STATE : INIT_STATE;
  888     strm->adler = 1;
  889     s->last_flush = Z_NO_FLUSH;
  890 
  891     _tr_init(s);
  892     lm_init(s);
  893 
  894     return Z_OK;
  895 }
  896 
  897 /* ========================================================================= */
  898 int deflateParams(strm, level, strategy)
  899     z_streamp strm;
  900     int level;
  901     int strategy;
  902 {
  903     deflate_state *s;
  904     compress_func func;
  905     int err = Z_OK;
  906 
  907     if (strm == Z_NULL || strm->state == Z_NULL) return Z_STREAM_ERROR;
  908     s = (deflate_state *) strm->state;
  909 
  910     if (level == Z_DEFAULT_COMPRESSION) {
  911         level = 6;
  912     }
  913     if (level < 0 || level > 9 || strategy < 0 || strategy > Z_HUFFMAN_ONLY) {
  914         return Z_STREAM_ERROR;
  915     }
  916     func = configuration_table[s->level].func;
  917 
  918     if (func != configuration_table[level].func && strm->total_in != 0) {
  919         /* Flush the last buffer: */
  920         err = deflate(strm, Z_PARTIAL_FLUSH);
  921     }
  922     if (s->level != level) {
  923         s->level = level;
  924         s->max_lazy_match   = configuration_table[level].max_lazy;
  925         s->good_match       = configuration_table[level].good_length;
  926         s->nice_match       = configuration_table[level].nice_length;
  927         s->max_chain_length = configuration_table[level].max_chain;
  928     }
  929     s->strategy = strategy;
  930     return err;
  931 }
  932 
  933 /* =========================================================================
  934  * Put a short in the pending buffer. The 16-bit value is put in MSB order.
  935  * IN assertion: the stream state is correct and there is enough room in
  936  * pending_buf.
  937  */
  938 local void putShortMSB (s, b)
  939     deflate_state *s;
  940     uInt b;
  941 {
  942     put_byte(s, (Byte)(b >> 8));
  943     put_byte(s, (Byte)(b & 0xff));
  944 }   
  945 
  946 /* =========================================================================
  947  * Flush as much pending output as possible. All deflate() output goes
  948  * through this function so some applications may wish to modify it
  949  * to avoid allocating a large strm->next_out buffer and copying into it.
  950  * (See also read_buf()).
  951  */
  952 local void flush_pending(strm)
  953     z_streamp strm;
  954 {
  955     deflate_state *s = (deflate_state *) strm->state;
  956     unsigned len = s->pending;
  957 
  958     if (len > strm->avail_out) len = strm->avail_out;
  959     if (len == 0) return;
  960 
  961     if (strm->next_out != Z_NULL) {
  962         zmemcpy(strm->next_out, s->pending_out, len);
  963         strm->next_out += len;
  964     }
  965     s->pending_out += len;
  966     strm->total_out += len;
  967     strm->avail_out  -= len;
  968     s->pending -= len;
  969     if (s->pending == 0) {
  970         s->pending_out = s->pending_buf;
  971     }
  972 }
  973 
  974 /* ========================================================================= */
  975 int deflate (strm, flush)
  976     z_streamp strm;
  977     int flush;
  978 {
  979     int old_flush; /* value of flush param for previous deflate call */
  980     deflate_state *s;
  981 
  982     if (strm == Z_NULL || strm->state == Z_NULL ||
  983         flush > Z_FINISH || flush < 0) {
  984         return Z_STREAM_ERROR;
  985     }
  986     s = (deflate_state *) strm->state;
  987 
  988     if ((strm->next_in == Z_NULL && strm->avail_in != 0) ||
  989         (s->status == FINISH_STATE && flush != Z_FINISH)) {
  990         ERR_RETURN(strm, Z_STREAM_ERROR);
  991     }
  992     if (strm->avail_out == 0) ERR_RETURN(strm, Z_BUF_ERROR);
  993 
  994     s->strm = strm; /* just in case */
  995     old_flush = s->last_flush;
  996     s->last_flush = flush;
  997 
  998     /* Write the zlib header */
  999     if (s->status == INIT_STATE) {
 1000 
 1001         uInt header = (Z_DEFLATED + ((s->w_bits-8)<<4)) << 8;
 1002         uInt level_flags = (s->level-1) >> 1;
 1003 
 1004         if (level_flags > 3) level_flags = 3;
 1005         header |= (level_flags << 6);
 1006         if (s->strstart != 0) header |= PRESET_DICT;
 1007         header += 31 - (header % 31);
 1008 
 1009         s->status = BUSY_STATE;
 1010         putShortMSB(s, header);
 1011 
 1012         /* Save the adler32 of the preset dictionary: */
 1013         if (s->strstart != 0) {
 1014             putShortMSB(s, (uInt)(strm->adler >> 16));
 1015             putShortMSB(s, (uInt)(strm->adler & 0xffff));
 1016         }
 1017         strm->adler = 1L;
 1018     }
 1019 
 1020     /* Flush as much pending output as possible */
 1021     if (s->pending != 0) {
 1022         flush_pending(strm);
 1023         if (strm->avail_out == 0) {
 1024             /* Since avail_out is 0, deflate will be called again with
 1025              * more output space, but possibly with both pending and
 1026              * avail_in equal to zero. There won't be anything to do,
 1027              * but this is not an error situation so make sure we
 1028              * return OK instead of BUF_ERROR at next call of deflate:
 1029              */
 1030             s->last_flush = -1;
 1031             return Z_OK;
 1032         }
 1033 
 1034     /* Make sure there is something to do and avoid duplicate consecutive
 1035      * flushes. For repeated and useless calls with Z_FINISH, we keep
 1036      * returning Z_STREAM_END instead of Z_BUFF_ERROR.
 1037      */
 1038     } else if (strm->avail_in == 0 && flush <= old_flush &&
 1039                flush != Z_FINISH) {
 1040         ERR_RETURN(strm, Z_BUF_ERROR);
 1041     }
 1042 
 1043     /* User must not provide more input after the first FINISH: */
 1044     if (s->status == FINISH_STATE && strm->avail_in != 0) {
 1045         ERR_RETURN(strm, Z_BUF_ERROR);
 1046     }
 1047 
 1048     /* Start a new block or continue the current one.
 1049      */
 1050     if (strm->avail_in != 0 || s->lookahead != 0 ||
 1051         (flush != Z_NO_FLUSH && s->status != FINISH_STATE)) {
 1052         block_state bstate;
 1053 
 1054         bstate = (*(configuration_table[s->level].func))(s, flush);
 1055 
 1056         if (bstate == finish_started || bstate == finish_done) {
 1057             s->status = FINISH_STATE;
 1058         }
 1059         if (bstate == need_more || bstate == finish_started) {
 1060             if (strm->avail_out == 0) {
 1061                 s->last_flush = -1; /* avoid BUF_ERROR next call, see above */
 1062             }
 1063             return Z_OK;
 1064             /* If flush != Z_NO_FLUSH && avail_out == 0, the next call
 1065              * of deflate should use the same flush parameter to make sure
 1066              * that the flush is complete. So we don't have to output an
 1067              * empty block here, this will be done at next call. This also
 1068              * ensures that for a very small output buffer, we emit at most
 1069              * one empty block.
 1070              */
 1071         }
 1072         if (bstate == block_done) {
 1073             if (flush == Z_PARTIAL_FLUSH) {
 1074                 _tr_align(s);
 1075             } else if (flush == Z_PACKET_FLUSH) {
 1076                 /* Output just the 3-bit `stored' block type value,
 1077                    but not a zero length. */
 1078                 _tr_stored_type_only(s);
 1079             } else { /* FULL_FLUSH or SYNC_FLUSH */
 1080                 _tr_stored_block(s, (char*)0, 0L, 0);
 1081                 /* For a full flush, this empty block will be recognized
 1082                  * as a special marker by inflate_sync().
 1083                  */
 1084                 if (flush == Z_FULL_FLUSH) {
 1085                     CLEAR_HASH(s);             /* forget history */
 1086                 }
 1087             }
 1088             flush_pending(strm);
 1089             if (strm->avail_out == 0) {
 1090               s->last_flush = -1; /* avoid BUF_ERROR at next call, see above */
 1091               return Z_OK;
 1092             }
 1093         }
 1094     }
 1095     Assert(strm->avail_out > 0, "bug2");
 1096 
 1097     if (flush != Z_FINISH) return Z_OK;
 1098     if (s->noheader) return Z_STREAM_END;
 1099 
 1100     /* Write the zlib trailer (adler32) */
 1101     putShortMSB(s, (uInt)(strm->adler >> 16));
 1102     putShortMSB(s, (uInt)(strm->adler & 0xffff));
 1103     flush_pending(strm);
 1104     /* If avail_out is zero, the application will call deflate again
 1105      * to flush the rest.
 1106      */
 1107     s->noheader = -1; /* write the trailer only once! */
 1108     return s->pending != 0 ? Z_OK : Z_STREAM_END;
 1109 }
 1110 
 1111 /* ========================================================================= */
 1112 int deflateEnd (strm)
 1113     z_streamp strm;
 1114 {
 1115     int status;
 1116     deflate_state *s;
 1117 
 1118     if (strm == Z_NULL || strm->state == Z_NULL) return Z_STREAM_ERROR;
 1119     s = (deflate_state *) strm->state;
 1120 
 1121     status = s->status;
 1122     if (status != INIT_STATE && status != BUSY_STATE &&
 1123         status != FINISH_STATE) {
 1124       return Z_STREAM_ERROR;
 1125     }
 1126 
 1127     /* Deallocate in reverse order of allocations: */
 1128     TRY_FREE(strm, s->pending_buf);
 1129     TRY_FREE(strm, s->head);
 1130     TRY_FREE(strm, s->prev);
 1131     TRY_FREE(strm, s->window);
 1132 
 1133     ZFREE(strm, s);
 1134     strm->state = Z_NULL;
 1135 
 1136     return status == BUSY_STATE ? Z_DATA_ERROR : Z_OK;
 1137 }
 1138 
 1139 /* =========================================================================
 1140  * Copy the source state to the destination state.
 1141  */
 1142 int deflateCopy (dest, source)
 1143     z_streamp dest;
 1144     z_streamp source;
 1145 {
 1146     deflate_state *ds;
 1147     deflate_state *ss;
 1148     ushf *overlay;
 1149 
 1150     if (source == Z_NULL || dest == Z_NULL || source->state == Z_NULL)
 1151         return Z_STREAM_ERROR;
 1152     ss = (deflate_state *) source->state;
 1153 
 1154     zmemcpy(dest, source, sizeof(*dest));
 1155 
 1156     ds = (deflate_state *) ZALLOC(dest, 1, sizeof(deflate_state));
 1157     if (ds == Z_NULL) return Z_MEM_ERROR;
 1158     dest->state = (struct internal_state FAR *) ds;
 1159     zmemcpy(ds, ss, sizeof(*ds));
 1160     ds->strm = dest;
 1161 
 1162     ds->window = (Bytef *) ZALLOC(dest, ds->w_size, 2*sizeof(Byte));
 1163     ds->prev   = (Posf *)  ZALLOC(dest, ds->w_size, sizeof(Pos));
 1164     ds->head   = (Posf *)  ZALLOC(dest, ds->hash_size, sizeof(Pos));
 1165     overlay = (ushf *) ZALLOC(dest, ds->lit_bufsize, sizeof(ush)+2);
 1166     ds->pending_buf = (uchf *) overlay;
 1167 
 1168     if (ds->window == Z_NULL || ds->prev == Z_NULL || ds->head == Z_NULL ||
 1169         ds->pending_buf == Z_NULL) {
 1170         deflateEnd (dest);
 1171         return Z_MEM_ERROR;
 1172     }
 1173     /* ??? following zmemcpy doesn't work for 16-bit MSDOS */
 1174     zmemcpy(ds->window, ss->window, ds->w_size * 2 * sizeof(Byte));
 1175     zmemcpy(ds->prev, ss->prev, ds->w_size * sizeof(Pos));
 1176     zmemcpy(ds->head, ss->head, ds->hash_size * sizeof(Pos));
 1177     zmemcpy(ds->pending_buf, ss->pending_buf, (uInt)ds->pending_buf_size);
 1178 
 1179     ds->pending_out = ds->pending_buf + (ss->pending_out - ss->pending_buf);
 1180     ds->d_buf = overlay + ds->lit_bufsize/sizeof(ush);
 1181     ds->l_buf = ds->pending_buf + (1+sizeof(ush))*ds->lit_bufsize;
 1182 
 1183     ds->l_desc.dyn_tree = ds->dyn_ltree;
 1184     ds->d_desc.dyn_tree = ds->dyn_dtree;
 1185     ds->bl_desc.dyn_tree = ds->bl_tree;
 1186 
 1187     return Z_OK;
 1188 }
 1189 
 1190 /* ===========================================================================
 1191  * Return the number of bytes of output which are immediately available
 1192  * for output from the decompressor.
 1193  */
 1194 int deflateOutputPending (strm)
 1195     z_streamp strm;
 1196 {
 1197     if (strm == Z_NULL || strm->state == Z_NULL) return 0;
 1198     
 1199     return ((deflate_state *)(strm->state))->pending;
 1200 }
 1201 
 1202 /* ===========================================================================
 1203  * Read a new buffer from the current input stream, update the adler32
 1204  * and total number of bytes read.  All deflate() input goes through
 1205  * this function so some applications may wish to modify it to avoid
 1206  * allocating a large strm->next_in buffer and copying from it.
 1207  * (See also flush_pending()).
 1208  */
 1209 local int read_buf(strm, buf, size)
 1210     z_streamp strm;
 1211     charf *buf;
 1212     unsigned size;
 1213 {
 1214     unsigned len = strm->avail_in;
 1215 
 1216     if (len > size) len = size;
 1217     if (len == 0) return 0;
 1218 
 1219     strm->avail_in  -= len;
 1220 
 1221     if (!((deflate_state *)(strm->state))->noheader) {
 1222         strm->adler = adler32(strm->adler, strm->next_in, len);
 1223     }
 1224     zmemcpy(buf, strm->next_in, len);
 1225     strm->next_in  += len;
 1226     strm->total_in += len;
 1227 
 1228     return (int)len;
 1229 }
 1230 
 1231 /* ===========================================================================
 1232  * Initialize the "longest match" routines for a new zlib stream
 1233  */
 1234 local void lm_init (s)
 1235     deflate_state *s;
 1236 {
 1237     s->window_size = (ulg)2L*s->w_size;
 1238 
 1239     CLEAR_HASH(s);
 1240 
 1241     /* Set the default configuration parameters:
 1242      */
 1243     s->max_lazy_match   = configuration_table[s->level].max_lazy;
 1244     s->good_match       = configuration_table[s->level].good_length;
 1245     s->nice_match       = configuration_table[s->level].nice_length;
 1246     s->max_chain_length = configuration_table[s->level].max_chain;
 1247 
 1248     s->strstart = 0;
 1249     s->block_start = 0L;
 1250     s->lookahead = 0;
 1251     s->match_length = s->prev_length = MIN_MATCH-1;
 1252     s->match_available = 0;
 1253     s->ins_h = 0;
 1254 #ifdef ASMV
 1255     match_init(); /* initialize the asm code */
 1256 #endif
 1257 }
 1258 
 1259 /* ===========================================================================
 1260  * Set match_start to the longest match starting at the given string and
 1261  * return its length. Matches shorter or equal to prev_length are discarded,
 1262  * in which case the result is equal to prev_length and match_start is
 1263  * garbage.
 1264  * IN assertions: cur_match is the head of the hash chain for the current
 1265  *   string (strstart) and its distance is <= MAX_DIST, and prev_length >= 1
 1266  * OUT assertion: the match length is not greater than s->lookahead.
 1267  */
 1268 #ifndef ASMV
 1269 /* For 80x86 and 680x0, an optimized version will be provided in match.asm or
 1270  * match.S. The code will be functionally equivalent.
 1271  */
 1272 local uInt longest_match(s, cur_match)
 1273     deflate_state *s;
 1274     IPos cur_match;                             /* current match */
 1275 {
 1276     unsigned chain_length = s->max_chain_length;/* max hash chain length */
 1277     register Bytef *scan = s->window + s->strstart; /* current string */
 1278     register Bytef *match;                       /* matched string */
 1279     register int len;                           /* length of current match */
 1280     int best_len = s->prev_length;              /* best match length so far */
 1281     int nice_match = s->nice_match;             /* stop if match long enough */
 1282     IPos limit = s->strstart > (IPos)MAX_DIST(s) ?
 1283         s->strstart - (IPos)MAX_DIST(s) : NIL;
 1284     /* Stop when cur_match becomes <= limit. To simplify the code,
 1285      * we prevent matches with the string of window index 0.
 1286      */
 1287     Posf *prev = s->prev;
 1288     uInt wmask = s->w_mask;
 1289 
 1290 #ifdef UNALIGNED_OK
 1291     /* Compare two bytes at a time. Note: this is not always beneficial.
 1292      * Try with and without -DUNALIGNED_OK to check.
 1293      */
 1294     register Bytef *strend = s->window + s->strstart + MAX_MATCH - 1;
 1295     register ush scan_start = *(ushf*)scan;
 1296     register ush scan_end   = *(ushf*)(scan+best_len-1);
 1297 #else
 1298     register Bytef *strend = s->window + s->strstart + MAX_MATCH;
 1299     register Byte scan_end1  = scan[best_len-1];
 1300     register Byte scan_end   = scan[best_len];
 1301 #endif
 1302 
 1303     /* The code is optimized for HASH_BITS >= 8 and MAX_MATCH-2 multiple of 16.
 1304      * It is easy to get rid of this optimization if necessary.
 1305      */
 1306     Assert(s->hash_bits >= 8 && MAX_MATCH == 258, "Code too clever");
 1307 
 1308     /* Do not waste too much time if we already have a good match: */
 1309     if (s->prev_length >= s->good_match) {
 1310         chain_length >>= 2;
 1311     }
 1312     /* Do not look for matches beyond the end of the input. This is necessary
 1313      * to make deflate deterministic.
 1314      */
 1315     if ((uInt)nice_match > s->lookahead) nice_match = s->lookahead;
 1316 
 1317     Assert((ulg)s->strstart <= s->window_size-MIN_LOOKAHEAD, "need lookahead");
 1318 
 1319     do {
 1320         Assert(cur_match < s->strstart, "no future");
 1321         match = s->window + cur_match;
 1322 
 1323         /* Skip to next match if the match length cannot increase
 1324          * or if the match length is less than 2:
 1325          */
 1326 #if (defined(UNALIGNED_OK) && MAX_MATCH == 258)
 1327         /* This code assumes sizeof(unsigned short) == 2. Do not use
 1328          * UNALIGNED_OK if your compiler uses a different size.
 1329          */
 1330         if (*(ushf*)(match+best_len-1) != scan_end ||
 1331             *(ushf*)match != scan_start) continue;
 1332 
 1333         /* It is not necessary to compare scan[2] and match[2] since they are
 1334          * always equal when the other bytes match, given that the hash keys
 1335          * are equal and that HASH_BITS >= 8. Compare 2 bytes at a time at
 1336          * strstart+3, +5, ... up to strstart+257. We check for insufficient
 1337          * lookahead only every 4th comparison; the 128th check will be made
 1338          * at strstart+257. If MAX_MATCH-2 is not a multiple of 8, it is
 1339          * necessary to put more guard bytes at the end of the window, or
 1340          * to check more often for insufficient lookahead.
 1341          */
 1342         Assert(scan[2] == match[2], "scan[2]?");
 1343         scan++, match++;
 1344         do {
 1345         } while (*(ushf*)(scan+=2) == *(ushf*)(match+=2) &&
 1346                  *(ushf*)(scan+=2) == *(ushf*)(match+=2) &&
 1347                  *(ushf*)(scan+=2) == *(ushf*)(match+=2) &&
 1348                  *(ushf*)(scan+=2) == *(ushf*)(match+=2) &&
 1349                  scan < strend);
 1350         /* The funny "do {}" generates better code on most compilers */
 1351 
 1352         /* Here, scan <= window+strstart+257 */
 1353         Assert(scan <= s->window+(unsigned)(s->window_size-1), "wild scan");
 1354         if (*scan == *match) scan++;
 1355 
 1356         len = (MAX_MATCH - 1) - (int)(strend-scan);
 1357         scan = strend - (MAX_MATCH-1);
 1358 
 1359 #else /* UNALIGNED_OK */
 1360 
 1361         if (match[best_len]   != scan_end  ||
 1362             match[best_len-1] != scan_end1 ||
 1363             *match            != *scan     ||
 1364             *++match          != scan[1])      continue;
 1365 
 1366         /* The check at best_len-1 can be removed because it will be made
 1367          * again later. (This heuristic is not always a win.)
 1368          * It is not necessary to compare scan[2] and match[2] since they
 1369          * are always equal when the other bytes match, given that
 1370          * the hash keys are equal and that HASH_BITS >= 8.
 1371          */
 1372         scan += 2, match++;
 1373         Assert(*scan == *match, "match[2]?");
 1374 
 1375         /* We check for insufficient lookahead only every 8th comparison;
 1376          * the 256th check will be made at strstart+258.
 1377          */
 1378         do {
 1379         } while (*++scan == *++match && *++scan == *++match &&
 1380                  *++scan == *++match && *++scan == *++match &&
 1381                  *++scan == *++match && *++scan == *++match &&
 1382                  *++scan == *++match && *++scan == *++match &&
 1383                  scan < strend);
 1384 
 1385         Assert(scan <= s->window+(unsigned)(s->window_size-1), "wild scan");
 1386 
 1387         len = MAX_MATCH - (int)(strend - scan);
 1388         scan = strend - MAX_MATCH;
 1389 
 1390 #endif /* UNALIGNED_OK */
 1391 
 1392         if (len > best_len) {
 1393             s->match_start = cur_match;
 1394             best_len = len;
 1395             if (len >= nice_match) break;
 1396 #ifdef UNALIGNED_OK
 1397             scan_end = *(ushf*)(scan+best_len-1);
 1398 #else
 1399             scan_end1  = scan[best_len-1];
 1400             scan_end   = scan[best_len];
 1401 #endif
 1402         }
 1403     } while ((cur_match = prev[cur_match & wmask]) > limit
 1404              && --chain_length != 0);
 1405 
 1406     if ((uInt)best_len <= s->lookahead) return best_len;
 1407     return s->lookahead;
 1408 }
 1409 #endif /* ASMV */
 1410 
 1411 #ifdef DEBUG_ZLIB
 1412 /* ===========================================================================
 1413  * Check that the match at match_start is indeed a match.
 1414  */
 1415 local void check_match(s, start, match, length)
 1416     deflate_state *s;
 1417     IPos start, match;
 1418     int length;
 1419 {
 1420     /* check that the match is indeed a match */
 1421     if (zmemcmp((charf *)s->window + match,
 1422                 (charf *)s->window + start, length) != EQUAL) {
 1423         fprintf(stderr, " start %u, match %u, length %d\n",
 1424                 start, match, length);
 1425         do {
 1426             fprintf(stderr, "%c%c", s->window[match++], s->window[start++]);
 1427         } while (--length != 0);
 1428         z_error("invalid match");
 1429     }
 1430     if (z_verbose > 1) {
 1431         fprintf(stderr,"\\[%d,%d]", start-match, length);
 1432         do { putc(s->window[start++], stderr); } while (--length != 0);
 1433     }
 1434 }
 1435 #else
 1436 #  define check_match(s, start, match, length)
 1437 #endif
 1438 
 1439 /* ===========================================================================
 1440  * Fill the window when the lookahead becomes insufficient.
 1441  * Updates strstart and lookahead.
 1442  *
 1443  * IN assertion: lookahead < MIN_LOOKAHEAD
 1444  * OUT assertions: strstart <= window_size-MIN_LOOKAHEAD
 1445  *    At least one byte has been read, or avail_in == 0; reads are
 1446  *    performed for at least two bytes (required for the zip translate_eol
 1447  *    option -- not supported here).
 1448  */
 1449 local void fill_window(s)
 1450     deflate_state *s;
 1451 {
 1452     register unsigned n, m;
 1453     register Posf *p;
 1454     unsigned more;    /* Amount of free space at the end of the window. */
 1455     uInt wsize = s->w_size;
 1456 
 1457     do {
 1458         more = (unsigned)(s->window_size -(ulg)s->lookahead -(ulg)s->strstart);
 1459 
 1460         /* Deal with !@#$% 64K limit: */
 1461         if (more == 0 && s->strstart == 0 && s->lookahead == 0) {
 1462             more = wsize;
 1463 
 1464         } else if (more == (unsigned)(-1)) {
 1465             /* Very unlikely, but possible on 16 bit machine if strstart == 0
 1466              * and lookahead == 1 (input done one byte at time)
 1467              */
 1468             more--;
 1469 
 1470         /* If the window is almost full and there is insufficient lookahead,
 1471          * move the upper half to the lower one to make room in the upper half.
 1472          */
 1473         } else if (s->strstart >= wsize+MAX_DIST(s)) {
 1474 
 1475             zmemcpy((charf *)s->window, (charf *)s->window+wsize,
 1476                    (unsigned)wsize);
 1477             s->match_start -= wsize;
 1478             s->strstart    -= wsize; /* we now have strstart >= MAX_DIST */
 1479             s->block_start -= (long) wsize;
 1480 
 1481             /* Slide the hash table (could be avoided with 32 bit values
 1482                at the expense of memory usage). We slide even when level == 0
 1483                to keep the hash table consistent if we switch back to level > 0
 1484                later. (Using level 0 permanently is not an optimal usage of
 1485                zlib, so we don't care about this pathological case.)
 1486              */
 1487             n = s->hash_size;
 1488             p = &s->head[n];
 1489             do {
 1490                 m = *--p;
 1491                 *p = (Pos)(m >= wsize ? m-wsize : NIL);
 1492             } while (--n);
 1493 
 1494             n = wsize;
 1495             p = &s->prev[n];
 1496             do {
 1497                 m = *--p;
 1498                 *p = (Pos)(m >= wsize ? m-wsize : NIL);
 1499                 /* If n is not on any hash chain, prev[n] is garbage but
 1500                  * its value will never be used.
 1501                  */
 1502             } while (--n);
 1503             more += wsize;
 1504         }
 1505         if (s->strm->avail_in == 0) return;
 1506 
 1507         /* If there was no sliding:
 1508          *    strstart <= WSIZE+MAX_DIST-1 && lookahead <= MIN_LOOKAHEAD - 1 &&
 1509          *    more == window_size - lookahead - strstart
 1510          * => more >= window_size - (MIN_LOOKAHEAD-1 + WSIZE + MAX_DIST-1)
 1511          * => more >= window_size - 2*WSIZE + 2
 1512          * In the BIG_MEM or MMAP case (not yet supported),
 1513          *   window_size == input_size + MIN_LOOKAHEAD  &&
 1514          *   strstart + s->lookahead <= input_size => more >= MIN_LOOKAHEAD.
 1515          * Otherwise, window_size == 2*WSIZE so more >= 2.
 1516          * If there was sliding, more >= WSIZE. So in all cases, more >= 2.
 1517          */
 1518         Assert(more >= 2, "more < 2");
 1519 
 1520         n = read_buf(s->strm, (charf *)s->window + s->strstart + s->lookahead,
 1521                      more);
 1522         s->lookahead += n;
 1523 
 1524         /* Initialize the hash value now that we have some input: */
 1525         if (s->lookahead >= MIN_MATCH) {
 1526             s->ins_h = s->window[s->strstart];
 1527             UPDATE_HASH(s, s->ins_h, s->window[s->strstart+1]);
 1528 #if MIN_MATCH != 3
 1529             Call UPDATE_HASH() MIN_MATCH-3 more times
 1530 #endif
 1531         }
 1532         /* If the whole input has less than MIN_MATCH bytes, ins_h is garbage,
 1533          * but this is not important since only literal bytes will be emitted.
 1534          */
 1535 
 1536     } while (s->lookahead < MIN_LOOKAHEAD && s->strm->avail_in != 0);
 1537 }
 1538 
 1539 /* ===========================================================================
 1540  * Flush the current block, with given end-of-file flag.
 1541  * IN assertion: strstart is set to the end of the current match.
 1542  */
 1543 #define FLUSH_BLOCK_ONLY(s, eof) { \
 1544    _tr_flush_block(s, (s->block_start >= 0L ? \
 1545                    (charf *)&s->window[(unsigned)s->block_start] : \
 1546                    (charf *)Z_NULL), \
 1547                 (ulg)((long)s->strstart - s->block_start), \
 1548                 (eof)); \
 1549    s->block_start = s->strstart; \
 1550    flush_pending(s->strm); \
 1551    Tracev((stderr,"[FLUSH]")); \
 1552 }
 1553 
 1554 /* Same but force premature exit if necessary. */
 1555 #define FLUSH_BLOCK(s, eof) { \
 1556    FLUSH_BLOCK_ONLY(s, eof); \
 1557    if (s->strm->avail_out == 0) return (eof) ? finish_started : need_more; \
 1558 }
 1559 
 1560 /* ===========================================================================
 1561  * Copy without compression as much as possible from the input stream, return
 1562  * the current block state.
 1563  * This function does not insert new strings in the dictionary since
 1564  * uncompressible data is probably not useful. This function is used
 1565  * only for the level=0 compression option.
 1566  * NOTE: this function should be optimized to avoid extra copying from
 1567  * window to pending_buf.
 1568  */
 1569 local block_state deflate_stored(s, flush)
 1570     deflate_state *s;
 1571     int flush;
 1572 {
 1573     /* Stored blocks are limited to 0xffff bytes, pending_buf is limited
 1574      * to pending_buf_size, and each stored block has a 5 byte header:
 1575      */
 1576     ulg max_block_size = 0xffff;
 1577     ulg max_start;
 1578 
 1579     if (max_block_size > s->pending_buf_size - 5) {
 1580         max_block_size = s->pending_buf_size - 5;
 1581     }
 1582 
 1583     /* Copy as much as possible from input to output: */
 1584     for (;;) {
 1585         /* Fill the window as much as possible: */
 1586         if (s->lookahead <= 1) {
 1587 
 1588             Assert(s->strstart < s->w_size+MAX_DIST(s) ||
 1589                    s->block_start >= (long)s->w_size, "slide too late");
 1590 
 1591             fill_window(s);
 1592             if (s->lookahead == 0 && flush == Z_NO_FLUSH) return need_more;
 1593 
 1594             if (s->lookahead == 0) break; /* flush the current block */
 1595         }
 1596         Assert(s->block_start >= 0L, "block gone");
 1597 
 1598         s->strstart += s->lookahead;
 1599         s->lookahead = 0;
 1600 
 1601         /* Emit a stored block if pending_buf will be full: */
 1602         max_start = s->block_start + max_block_size;
 1603         if (s->strstart == 0 || (ulg)s->strstart >= max_start) {
 1604             /* strstart == 0 is possible when wraparound on 16-bit machine */
 1605             s->lookahead = (uInt)(s->strstart - max_start);
 1606             s->strstart = (uInt)max_start;
 1607             FLUSH_BLOCK(s, 0);
 1608         }
 1609         /* Flush if we may have to slide, otherwise block_start may become
 1610          * negative and the data will be gone:
 1611          */
 1612         if (s->strstart - (uInt)s->block_start >= MAX_DIST(s)) {
 1613             FLUSH_BLOCK(s, 0);
 1614         }
 1615     }
 1616     FLUSH_BLOCK(s, flush == Z_FINISH);
 1617     return flush == Z_FINISH ? finish_done : block_done;
 1618 }
 1619 
 1620 /* ===========================================================================
 1621  * Compress as much as possible from the input stream, return the current
 1622  * block state.
 1623  * This function does not perform lazy evaluation of matches and inserts
 1624  * new strings in the dictionary only for unmatched strings or for short
 1625  * matches. It is used only for the fast compression options.
 1626  */
 1627 local block_state deflate_fast(s, flush)
 1628     deflate_state *s;
 1629     int flush;
 1630 {
 1631     IPos hash_head = NIL; /* head of the hash chain */
 1632     int bflush;           /* set if current block must be flushed */
 1633 
 1634     for (;;) {
 1635         /* Make sure that we always have enough lookahead, except
 1636          * at the end of the input file. We need MAX_MATCH bytes
 1637          * for the next match, plus MIN_MATCH bytes to insert the
 1638          * string following the next match.
 1639          */
 1640         if (s->lookahead < MIN_LOOKAHEAD) {
 1641             fill_window(s);
 1642             if (s->lookahead < MIN_LOOKAHEAD && flush == Z_NO_FLUSH) {
 1643                 return need_more;
 1644             }
 1645             if (s->lookahead == 0) break; /* flush the current block */
 1646         }
 1647 
 1648         /* Insert the string window[strstart .. strstart+2] in the
 1649          * dictionary, and set hash_head to the head of the hash chain:
 1650          */
 1651         if (s->lookahead >= MIN_MATCH) {
 1652             INSERT_STRING(s, s->strstart, hash_head);
 1653         }
 1654 
 1655         /* Find the longest match, discarding those <= prev_length.
 1656          * At this point we have always match_length < MIN_MATCH
 1657          */
 1658         if (hash_head != NIL && s->strstart - hash_head <= MAX_DIST(s)) {
 1659             /* To simplify the code, we prevent matches with the string
 1660              * of window index 0 (in particular we have to avoid a match
 1661              * of the string with itself at the start of the input file).
 1662              */
 1663             if (s->strategy != Z_HUFFMAN_ONLY) {
 1664                 s->match_length = longest_match (s, hash_head);
 1665             }
 1666             /* longest_match() sets match_start */
 1667         }
 1668         if (s->match_length >= MIN_MATCH) {
 1669             check_match(s, s->strstart, s->match_start, s->match_length);
 1670 
 1671             bflush = _tr_tally(s, s->strstart - s->match_start,
 1672                                s->match_length - MIN_MATCH);
 1673 
 1674             s->lookahead -= s->match_length;
 1675 
 1676             /* Insert new strings in the hash table only if the match length
 1677              * is not too large. This saves time but degrades compression.
 1678              */
 1679             if (s->match_length <= s->max_insert_length &&
 1680                 s->lookahead >= MIN_MATCH) {
 1681                 s->match_length--; /* string at strstart already in hash table */
 1682                 do {
 1683                     s->strstart++;
 1684                     INSERT_STRING(s, s->strstart, hash_head);
 1685                     /* strstart never exceeds WSIZE-MAX_MATCH, so there are
 1686                      * always MIN_MATCH bytes ahead.
 1687                      */
 1688                 } while (--s->match_length != 0);
 1689                 s->strstart++; 
 1690             } else {
 1691                 s->strstart += s->match_length;
 1692                 s->match_length = 0;
 1693                 s->ins_h = s->window[s->strstart];
 1694                 UPDATE_HASH(s, s->ins_h, s->window[s->strstart+1]);
 1695 #if MIN_MATCH != 3
 1696                 Call UPDATE_HASH() MIN_MATCH-3 more times
 1697 #endif
 1698                 /* If lookahead < MIN_MATCH, ins_h is garbage, but it does not
 1699                  * matter since it will be recomputed at next deflate call.
 1700                  */
 1701             }
 1702         } else {
 1703             /* No match, output a literal byte */
 1704             Tracevv((stderr,"%c", s->window[s->strstart]));
 1705             bflush = _tr_tally (s, 0, s->window[s->strstart]);
 1706             s->lookahead--;
 1707             s->strstart++; 
 1708         }
 1709         if (bflush) FLUSH_BLOCK(s, 0);
 1710     }
 1711     FLUSH_BLOCK(s, flush == Z_FINISH);
 1712     return flush == Z_FINISH ? finish_done : block_done;
 1713 }
 1714 
 1715 /* ===========================================================================
 1716  * Same as above, but achieves better compression. We use a lazy
 1717  * evaluation for matches: a match is finally adopted only if there is
 1718  * no better match at the next window position.
 1719  */
 1720 local block_state deflate_slow(s, flush)
 1721     deflate_state *s;
 1722     int flush;
 1723 {
 1724     IPos hash_head = NIL;    /* head of hash chain */
 1725     int bflush;              /* set if current block must be flushed */
 1726 
 1727     /* Process the input block. */
 1728     for (;;) {
 1729         /* Make sure that we always have enough lookahead, except
 1730          * at the end of the input file. We need MAX_MATCH bytes
 1731          * for the next match, plus MIN_MATCH bytes to insert the
 1732          * string following the next match.
 1733          */
 1734         if (s->lookahead < MIN_LOOKAHEAD) {
 1735             fill_window(s);
 1736             if (s->lookahead < MIN_LOOKAHEAD && flush == Z_NO_FLUSH) {
 1737                 return need_more;
 1738             }
 1739             if (s->lookahead == 0) break; /* flush the current block */
 1740         }
 1741 
 1742         /* Insert the string window[strstart .. strstart+2] in the
 1743          * dictionary, and set hash_head to the head of the hash chain:
 1744          */
 1745         if (s->lookahead >= MIN_MATCH) {
 1746             INSERT_STRING(s, s->strstart, hash_head);
 1747         }
 1748 
 1749         /* Find the longest match, discarding those <= prev_length.
 1750          */
 1751         s->prev_length = s->match_length, s->prev_match = s->match_start;
 1752         s->match_length = MIN_MATCH-1;
 1753 
 1754         if (hash_head != NIL && s->prev_length < s->max_lazy_match &&
 1755             s->strstart - hash_head <= MAX_DIST(s)) {
 1756             /* To simplify the code, we prevent matches with the string
 1757              * of window index 0 (in particular we have to avoid a match
 1758              * of the string with itself at the start of the input file).
 1759              */
 1760             if (s->strategy != Z_HUFFMAN_ONLY) {
 1761                 s->match_length = longest_match (s, hash_head);
 1762             }
 1763             /* longest_match() sets match_start */
 1764 
 1765             if (s->match_length <= 5 && (s->strategy == Z_FILTERED ||
 1766                  (s->match_length == MIN_MATCH &&
 1767                   s->strstart - s->match_start > TOO_FAR))) {
 1768 
 1769                 /* If prev_match is also MIN_MATCH, match_start is garbage
 1770                  * but we will ignore the current match anyway.
 1771                  */
 1772                 s->match_length = MIN_MATCH-1;
 1773             }
 1774         }
 1775         /* If there was a match at the previous step and the current
 1776          * match is not better, output the previous match:
 1777          */
 1778         if (s->prev_length >= MIN_MATCH && s->match_length <= s->prev_length) {
 1779             uInt max_insert = s->strstart + s->lookahead - MIN_MATCH;
 1780             /* Do not insert strings in hash table beyond this. */
 1781 
 1782             check_match(s, s->strstart-1, s->prev_match, s->prev_length);
 1783 
 1784             bflush = _tr_tally(s, s->strstart -1 - s->prev_match,
 1785                                s->prev_length - MIN_MATCH);
 1786 
 1787             /* Insert in hash table all strings up to the end of the match.
 1788              * strstart-1 and strstart are already inserted. If there is not
 1789              * enough lookahead, the last two strings are not inserted in
 1790              * the hash table.
 1791              */
 1792             s->lookahead -= s->prev_length-1;
 1793             s->prev_length -= 2;
 1794             do {
 1795                 if (++s->strstart <= max_insert) {
 1796                     INSERT_STRING(s, s->strstart, hash_head);
 1797                 }
 1798             } while (--s->prev_length != 0);
 1799             s->match_available = 0;
 1800             s->match_length = MIN_MATCH-1;
 1801             s->strstart++;
 1802 
 1803             if (bflush) FLUSH_BLOCK(s, 0);
 1804 
 1805         } else if (s->match_available) {
 1806             /* If there was no match at the previous position, output a
 1807              * single literal. If there was a match but the current match
 1808              * is longer, truncate the previous match to a single literal.
 1809              */
 1810             Tracevv((stderr,"%c", s->window[s->strstart-1]));
 1811             if (_tr_tally (s, 0, s->window[s->strstart-1])) {
 1812                 FLUSH_BLOCK_ONLY(s, 0);
 1813             }
 1814             s->strstart++;
 1815             s->lookahead--;
 1816             if (s->strm->avail_out == 0) return need_more;
 1817         } else {
 1818             /* There is no previous match to compare with, wait for
 1819              * the next step to decide.
 1820              */
 1821             s->match_available = 1;
 1822             s->strstart++;
 1823             s->lookahead--;
 1824         }
 1825     }
 1826     Assert (flush != Z_NO_FLUSH, "no flush?");
 1827     if (s->match_available) {
 1828         Tracevv((stderr,"%c", s->window[s->strstart-1]));
 1829         _tr_tally (s, 0, s->window[s->strstart-1]);
 1830         s->match_available = 0;
 1831     }
 1832     FLUSH_BLOCK(s, flush == Z_FINISH);
 1833     return flush == Z_FINISH ? finish_done : block_done;
 1834 }
 1835 /* --- deflate.c */
 1836 
 1837 /* +++ trees.c */
 1838 /* trees.c -- output deflated data using Huffman coding
 1839  * Copyright (C) 1995-1996 Jean-loup Gailly
 1840  * For conditions of distribution and use, see copyright notice in zlib.h 
 1841  */
 1842 
 1843 /*
 1844  *  ALGORITHM
 1845  *
 1846  *      The "deflation" process uses several Huffman trees. The more
 1847  *      common source values are represented by shorter bit sequences.
 1848  *
 1849  *      Each code tree is stored in a compressed form which is itself
 1850  * a Huffman encoding of the lengths of all the code strings (in
 1851  * ascending order by source values).  The actual code strings are
 1852  * reconstructed from the lengths in the inflate process, as described
 1853  * in the deflate specification.
 1854  *
 1855  *  REFERENCES
 1856  *
 1857  *      Deutsch, L.P.,"'Deflate' Compressed Data Format Specification".
 1858  *      Available in ftp.uu.net:/pub/archiving/zip/doc/deflate-1.1.doc
 1859  *
 1860  *      Storer, James A.
 1861  *          Data Compression:  Methods and Theory, pp. 49-50.
 1862  *          Computer Science Press, 1988.  ISBN 0-7167-8156-5.
 1863  *
 1864  *      Sedgewick, R.
 1865  *          Algorithms, p290.
 1866  *          Addison-Wesley, 1983. ISBN 0-201-06672-6.
 1867  */
 1868 
 1869 /* From: trees.c,v 1.11 1996/07/24 13:41:06 me Exp $ */
 1870 
 1871 /* #include "deflate.h" */
 1872 
 1873 #ifdef DEBUG_ZLIB
 1874 #  include <ctype.h>
 1875 #endif
 1876 
 1877 /* ===========================================================================
 1878  * Constants
 1879  */
 1880 
 1881 #define MAX_BL_BITS 7
 1882 /* Bit length codes must not exceed MAX_BL_BITS bits */
 1883 
 1884 #define END_BLOCK 256
 1885 /* end of block literal code */
 1886 
 1887 #define REP_3_6      16
 1888 /* repeat previous bit length 3-6 times (2 bits of repeat count) */
 1889 
 1890 #define REPZ_3_10    17
 1891 /* repeat a zero length 3-10 times  (3 bits of repeat count) */
 1892 
 1893 #define REPZ_11_138  18
 1894 /* repeat a zero length 11-138 times  (7 bits of repeat count) */
 1895 
 1896 local int extra_lbits[LENGTH_CODES] /* extra bits for each length code */
 1897    = {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};
 1898 
 1899 local int extra_dbits[D_CODES] /* extra bits for each distance code */
 1900    = {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};
 1901 
 1902 local int extra_blbits[BL_CODES]/* extra bits for each bit length code */
 1903    = {0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,2,3,7};
 1904 
 1905 local uch bl_order[BL_CODES]
 1906    = {16,17,18,0,8,7,9,6,10,5,11,4,12,3,13,2,14,1,15};
 1907 /* The lengths of the bit length codes are sent in order of decreasing
 1908  * probability, to avoid transmitting the lengths for unused bit length codes.
 1909  */
 1910 
 1911 #define Buf_size (8 * 2*sizeof(char))
 1912 /* Number of bits used within bi_buf. (bi_buf might be implemented on
 1913  * more than 16 bits on some systems.)
 1914  */
 1915 
 1916 /* ===========================================================================
 1917  * Local data. These are initialized only once.
 1918  */
 1919 
 1920 local ct_data static_ltree[L_CODES+2];
 1921 /* The static literal tree. Since the bit lengths are imposed, there is no
 1922  * need for the L_CODES extra codes used during heap construction. However
 1923  * The codes 286 and 287 are needed to build a canonical tree (see _tr_init
 1924  * below).
 1925  */
 1926 
 1927 local ct_data static_dtree[D_CODES];
 1928 /* The static distance tree. (Actually a trivial tree since all codes use
 1929  * 5 bits.)
 1930  */
 1931 
 1932 local uch dist_code[512];
 1933 /* distance codes. The first 256 values correspond to the distances
 1934  * 3 .. 258, the last 256 values correspond to the top 8 bits of
 1935  * the 15 bit distances.
 1936  */
 1937 
 1938 local uch length_code[MAX_MATCH-MIN_MATCH+1];
 1939 /* length code for each normalized match length (0 == MIN_MATCH) */
 1940 
 1941 local int base_length[LENGTH_CODES];
 1942 /* First normalized length for each code (0 = MIN_MATCH) */
 1943 
 1944 local int base_dist[D_CODES];
 1945 /* First normalized distance for each code (0 = distance of 1) */
 1946 
 1947 struct static_tree_desc_s {
 1948     ct_data *static_tree;        /* static tree or NULL */
 1949     intf    *extra_bits;         /* extra bits for each code or NULL */
 1950     int     extra_base;          /* base index for extra_bits */
 1951     int     elems;               /* max number of elements in the tree */
 1952     int     max_length;          /* max bit length for the codes */
 1953 };
 1954 
 1955 local static_tree_desc  static_l_desc =
 1956 {static_ltree, extra_lbits, LITERALS+1, L_CODES, MAX_BITS};
 1957 
 1958 local static_tree_desc  static_d_desc =
 1959 {static_dtree, extra_dbits, 0,          D_CODES, MAX_BITS};
 1960 
 1961 local static_tree_desc  static_bl_desc =
 1962 {(ct_data *)0, extra_blbits, 0,      BL_CODES, MAX_BL_BITS};
 1963 
 1964 /* ===========================================================================
 1965  * Local (static) routines in this file.
 1966  */
 1967 
 1968 local void tr_static_init OF((void));
 1969 local void init_block     OF((deflate_state *s));
 1970 local void pqdownheap     OF((deflate_state *s, ct_data *tree, int k));
 1971 local void gen_bitlen     OF((deflate_state *s, tree_desc *desc));
 1972 local void gen_codes      OF((ct_data *tree, int max_code, ushf *bl_count));
 1973 local void build_tree     OF((deflate_state *s, tree_desc *desc));
 1974 local void scan_tree      OF((deflate_state *s, ct_data *tree, int max_code));
 1975 local void send_tree      OF((deflate_state *s, ct_data *tree, int max_code));
 1976 local int  build_bl_tree  OF((deflate_state *s));
 1977 local void send_all_trees OF((deflate_state *s, int lcodes, int dcodes,
 1978                               int blcodes));
 1979 local void compress_block OF((deflate_state *s, ct_data *ltree,
 1980                               ct_data *dtree));
 1981 local void set_data_type  OF((deflate_state *s));
 1982 local unsigned bi_reverse OF((unsigned value, int length));
 1983 local void bi_windup      OF((deflate_state *s));
 1984 local void bi_flush       OF((deflate_state *s));
 1985 local void copy_block     OF((deflate_state *s, charf *buf, unsigned len,
 1986                               int header));
 1987 
 1988 #ifndef DEBUG_ZLIB
 1989 #  define send_code(s, c, tree) send_bits(s, tree[(c)].Code, tree[(c)].Len)
 1990    /* Send a code of the given tree. c and tree must not have side effects */
 1991 
 1992 #else /* DEBUG_ZLIB */
 1993 #  define send_code(s, c, tree) \
 1994      { if (verbose>2) fprintf(stderr,"\ncd %3d ",(c)); \
 1995        send_bits(s, tree[c].Code, tree[c].Len); }
 1996 #endif
 1997 
 1998 #define d_code(dist) \
 1999    ((dist) < 256 ? dist_code[dist] : dist_code[256+((dist)>>7)])
 2000 /* Mapping from a distance to a distance code. dist is the distance - 1 and
 2001  * must not have side effects. dist_code[256] and dist_code[257] are never
 2002  * used.
 2003  */
 2004 
 2005 /* ===========================================================================
 2006  * Output a short LSB first on the stream.
 2007  * IN assertion: there is enough room in pendingBuf.
 2008  */
 2009 #define put_short(s, w) { \
 2010     put_byte(s, (uch)((w) & 0xff)); \
 2011     put_byte(s, (uch)((ush)(w) >> 8)); \
 2012 }
 2013 
 2014 /* ===========================================================================
 2015  * Send a value on a given number of bits.
 2016  * IN assertion: length <= 16 and value fits in length bits.
 2017  */
 2018 #ifdef DEBUG_ZLIB
 2019 local void send_bits      OF((deflate_state *s, int value, int length));
 2020 
 2021 local void send_bits(s, value, length)
 2022     deflate_state *s;
 2023     int value;  /* value to send */
 2024     int length; /* number of bits */
 2025 {
 2026     Tracevv((stderr," l %2d v %4x ", length, value));
 2027     Assert(length > 0 && length <= 15, "invalid length");
 2028     s->bits_sent += (ulg)length;
 2029 
 2030     /* If not enough room in bi_buf, use (valid) bits from bi_buf and
 2031      * (16 - bi_valid) bits from value, leaving (width - (16-bi_valid))
 2032      * unused bits in value.
 2033      */
 2034     if (s->bi_valid > (int)Buf_size - length) {
 2035         s->bi_buf |= (value << s->bi_valid);
 2036         put_short(s, s->bi_buf);
 2037         s->bi_buf = (ush)value >> (Buf_size - s->bi_valid);
 2038         s->bi_valid += length - Buf_size;
 2039     } else {
 2040         s->bi_buf |= value << s->bi_valid;
 2041         s->bi_valid += length;
 2042     }
 2043 }
 2044 #else /* !DEBUG_ZLIB */
 2045 
 2046 #define send_bits(s, value, length) \
 2047 { int len = (length);\
 2048   if ((s)->bi_valid > (int)Buf_size - len) {\
 2049     int val = (value);\
 2050     (s)->bi_buf |= (val << (s)->bi_valid);\
 2051     put_short((s), (s)->bi_buf);\
 2052     (s)->bi_buf = (ush)val >> (Buf_size - (s)->bi_valid);\
 2053     (s)->bi_valid += len - Buf_size;\
 2054   } else {\
 2055     (s)->bi_buf |= (value) << (s)->bi_valid;\
 2056     (s)->bi_valid += len;\
 2057   }\
 2058 }
 2059 #endif /* DEBUG_ZLIB */
 2060 
 2061 /* the arguments must not have side effects */
 2062 
 2063 /* ===========================================================================
 2064  * Initialize the various 'constant' tables. In a multi-threaded environment,
 2065  * this function may be called by two threads concurrently, but this is
 2066  * harmless since both invocations do exactly the same thing.
 2067  */
 2068 local void tr_static_init()
 2069 {
 2070     static int static_init_done = 0;
 2071     int n;        /* iterates over tree elements */
 2072     int bits;     /* bit counter */
 2073     int length;   /* length value */
 2074     int code;     /* code value */
 2075     int dist;     /* distance index */
 2076     ush bl_count[MAX_BITS+1];
 2077     /* number of codes at each bit length for an optimal tree */
 2078 
 2079     if (static_init_done) return;
 2080 
 2081     /* Initialize the mapping length (0..255) -> length code (0..28) */
 2082     length = 0;
 2083     for (code = 0; code < LENGTH_CODES-1; code++) {
 2084         base_length[code] = length;
 2085         for (n = 0; n < (1<<extra_lbits[code]); n++) {
 2086             length_code[length++] = (uch)code;
 2087         }
 2088     }
 2089     Assert (length == 256, "tr_static_init: length != 256");
 2090     /* Note that the length 255 (match length 258) can be represented
 2091      * in two different ways: code 284 + 5 bits or code 285, so we
 2092      * overwrite length_code[255] to use the best encoding:
 2093      */
 2094     length_code[length-1] = (uch)code;
 2095 
 2096     /* Initialize the mapping dist (0..32K) -> dist code (0..29) */
 2097     dist = 0;
 2098     for (code = 0 ; code < 16; code++) {
 2099         base_dist[code] = dist;
 2100         for (n = 0; n < (1<<extra_dbits[code]); n++) {
 2101             dist_code[dist++] = (uch)code;
 2102         }
 2103     }
 2104     Assert (dist == 256, "tr_static_init: dist != 256");
 2105     dist >>= 7; /* from now on, all distances are divided by 128 */
 2106     for ( ; code < D_CODES; code++) {
 2107         base_dist[code] = dist << 7;
 2108         for (n = 0; n < (1<<(extra_dbits[code]-7)); n++) {
 2109             dist_code[256 + dist++] = (uch)code;
 2110         }
 2111     }
 2112     Assert (dist == 256, "tr_static_init: 256+dist != 512");
 2113 
 2114     /* Construct the codes of the static literal tree */
 2115     for (bits = 0; bits <= MAX_BITS; bits++) bl_count[bits] = 0;
 2116     n = 0;
 2117     while (n <= 143) static_ltree[n++].Len = 8, bl_count[8]++;
 2118     while (n <= 255) static_ltree[n++].Len = 9, bl_count[9]++;
 2119     while (n <= 279) static_ltree[n++].Len = 7, bl_count[7]++;
 2120     while (n <= 287) static_ltree[n++].Len = 8, bl_count[8]++;
 2121     /* Codes 286 and 287 do not exist, but we must include them in the
 2122      * tree construction to get a canonical Huffman tree (longest code
 2123      * all ones)
 2124      */
 2125     gen_codes((ct_data *)static_ltree, L_CODES+1, bl_count);
 2126 
 2127     /* The static distance tree is trivial: */
 2128     for (n = 0; n < D_CODES; n++) {
 2129         static_dtree[n].Len = 5;
 2130         static_dtree[n].Code = bi_reverse((unsigned)n, 5);
 2131     }
 2132     static_init_done = 1;
 2133 }
 2134 
 2135 /* ===========================================================================
 2136  * Initialize the tree data structures for a new zlib stream.
 2137  */
 2138 void _tr_init(s)
 2139     deflate_state *s;
 2140 {
 2141     tr_static_init();
 2142 
 2143     s->compressed_len = 0L;
 2144 
 2145     s->l_desc.dyn_tree = s->dyn_ltree;
 2146     s->l_desc.stat_desc = &static_l_desc;
 2147 
 2148     s->d_desc.dyn_tree = s->dyn_dtree;
 2149     s->d_desc.stat_desc = &static_d_desc;
 2150 
 2151     s->bl_desc.dyn_tree = s->bl_tree;
 2152     s->bl_desc.stat_desc = &static_bl_desc;
 2153 
 2154     s->bi_buf = 0;
 2155     s->bi_valid = 0;
 2156     s->last_eob_len = 8; /* enough lookahead for inflate */
 2157 #ifdef DEBUG_ZLIB
 2158     s->bits_sent = 0L;
 2159 #endif
 2160 
 2161     /* Initialize the first block of the first file: */
 2162     init_block(s);
 2163 }
 2164 
 2165 /* ===========================================================================
 2166  * Initialize a new block.
 2167  */
 2168 local void init_block(s)
 2169     deflate_state *s;
 2170 {
 2171     int n; /* iterates over tree elements */
 2172 
 2173     /* Initialize the trees. */
 2174     for (n = 0; n < L_CODES;  n++) s->dyn_ltree[n].Freq = 0;
 2175     for (n = 0; n < D_CODES;  n++) s->dyn_dtree[n].Freq = 0;
 2176     for (n = 0; n < BL_CODES; n++) s->bl_tree[n].Freq = 0;
 2177 
 2178     s->dyn_ltree[END_BLOCK].Freq = 1;
 2179     s->opt_len = s->static_len = 0L;
 2180     s->last_lit = s->matches = 0;
 2181 }
 2182 
 2183 #define SMALLEST 1
 2184 /* Index within the heap array of least frequent node in the Huffman tree */
 2185 
 2186 
 2187 /* ===========================================================================
 2188  * Remove the smallest element from the heap and recreate the heap with
 2189  * one less element. Updates heap and heap_len.
 2190  */
 2191 #define pqremove(s, tree, top) \
 2192 {\
 2193     top = s->heap[SMALLEST]; \
 2194     s->heap[SMALLEST] = s->heap[s->heap_len--]; \
 2195     pqdownheap(s, tree, SMALLEST); \
 2196 }
 2197 
 2198 /* ===========================================================================
 2199  * Compares to subtrees, using the tree depth as tie breaker when
 2200  * the subtrees have equal frequency. This minimizes the worst case length.
 2201  */
 2202 #define smaller(tree, n, m, depth) \
 2203    (tree[n].Freq < tree[m].Freq || \
 2204    (tree[n].Freq == tree[m].Freq && depth[n] <= depth[m]))
 2205 
 2206 /* ===========================================================================
 2207  * Restore the heap property by moving down the tree starting at node k,
 2208  * exchanging a node with the smallest of its two sons if necessary, stopping
 2209  * when the heap property is re-established (each father smaller than its
 2210  * two sons).
 2211  */
 2212 local void pqdownheap(s, tree, k)
 2213     deflate_state *s;
 2214     ct_data *tree;  /* the tree to restore */
 2215     int k;               /* node to move down */
 2216 {
 2217     int v = s->heap[k];
 2218     int j = k << 1;  /* left son of k */
 2219     while (j <= s->heap_len) {
 2220         /* Set j to the smallest of the two sons: */
 2221         if (j < s->heap_len &&
 2222             smaller(tree, s->heap[j+1], s->heap[j], s->depth)) {
 2223             j++;
 2224         }
 2225         /* Exit if v is smaller than both sons */
 2226         if (smaller(tree, v, s->heap[j], s->depth)) break;
 2227 
 2228         /* Exchange v with the smallest son */
 2229         s->heap[k] = s->heap[j];  k = j;
 2230 
 2231         /* And continue down the tree, setting j to the left son of k */
 2232         j <<= 1;
 2233     }
 2234     s->heap[k] = v;
 2235 }
 2236 
 2237 /* ===========================================================================
 2238  * Compute the optimal bit lengths for a tree and update the total bit length
 2239  * for the current block.
 2240  * IN assertion: the fields freq and dad are set, heap[heap_max] and
 2241  *    above are the tree nodes sorted by increasing frequency.
 2242  * OUT assertions: the field len is set to the optimal bit length, the
 2243  *     array bl_count contains the frequencies for each bit length.
 2244  *     The length opt_len is updated; static_len is also updated if stree is
 2245  *     not null.
 2246  */
 2247 local void gen_bitlen(s, desc)
 2248     deflate_state *s;
 2249     tree_desc *desc;    /* the tree descriptor */
 2250 {
 2251     ct_data *tree  = desc->dyn_tree;
 2252     int max_code   = desc->max_code;
 2253     ct_data *stree = desc->stat_desc->static_tree;
 2254     intf *extra    = desc->stat_desc->extra_bits;
 2255     int base       = desc->stat_desc->extra_base;
 2256     int max_length = desc->stat_desc->max_length;
 2257     int h;              /* heap index */
 2258     int n, m;           /* iterate over the tree elements */
 2259     int bits;           /* bit length */
 2260     int xbits;          /* extra bits */
 2261     ush f;              /* frequency */
 2262     int overflow = 0;   /* number of elements with bit length too large */
 2263 
 2264     for (bits = 0; bits <= MAX_BITS; bits++) s->bl_count[bits] = 0;
 2265 
 2266     /* In a first pass, compute the optimal bit lengths (which may
 2267      * overflow in the case of the bit length tree).
 2268      */
 2269     tree[s->heap[s->heap_max]].Len = 0; /* root of the heap */
 2270 
 2271     for (h = s->heap_max+1; h < HEAP_SIZE; h++) {
 2272         n = s->heap[h];
 2273         bits = tree[tree[n].Dad].Len + 1;
 2274         if (bits > max_length) bits = max_length, overflow++;
 2275         tree[n].Len = (ush)bits;
 2276         /* We overwrite tree[n].Dad which is no longer needed */
 2277 
 2278         if (n > max_code) continue; /* not a leaf node */
 2279 
 2280         s->bl_count[bits]++;
 2281         xbits = 0;
 2282         if (n >= base) xbits = extra[n-base];
 2283         f = tree[n].Freq;
 2284         s->opt_len += (ulg)f * (bits + xbits);
 2285         if (stree) s->static_len += (ulg)f * (stree[n].Len + xbits);
 2286     }
 2287     if (overflow == 0) return;
 2288 
 2289     Trace((stderr,"\nbit length overflow\n"));
 2290     /* This happens for example on obj2 and pic of the Calgary corpus */
 2291 
 2292     /* Find the first bit length which could increase: */
 2293     do {
 2294         bits = max_length-1;
 2295         while (s->bl_count[bits] == 0) bits--;
 2296         s->bl_count[bits]--;      /* move one leaf down the tree */
 2297         s->bl_count[bits+1] += 2; /* move one overflow item as its brother */
 2298         s->bl_count[max_length]--;
 2299         /* The brother of the overflow item also moves one step up,
 2300          * but this does not affect bl_count[max_length]
 2301          */
 2302         overflow -= 2;
 2303     } while (overflow > 0);
 2304 
 2305     /* Now recompute all bit lengths, scanning in increasing frequency.
 2306      * h is still equal to HEAP_SIZE. (It is simpler to reconstruct all
 2307      * lengths instead of fixing only the wrong ones. This idea is taken
 2308      * from 'ar' written by Haruhiko Okumura.)
 2309      */
 2310     for (bits = max_length; bits != 0; bits--) {
 2311         n = s->bl_count[bits];
 2312         while (n != 0) {
 2313             m = s->heap[--h];
 2314             if (m > max_code) continue;
 2315             if (tree[m].Len != (unsigned) bits) {
 2316                 Trace((stderr,"code %d bits %d->%d\n", m, tree[m].Len, bits));
 2317                 s->opt_len += ((long)bits - (long)tree[m].Len)
 2318                               *(long)tree[m].Freq;
 2319                 tree[m].Len = (ush)bits;
 2320             }
 2321             n--;
 2322         }
 2323     }
 2324 }
 2325 
 2326 /* ===========================================================================
 2327  * Generate the codes for a given tree and bit counts (which need not be
 2328  * optimal).
 2329  * IN assertion: the array bl_count contains the bit length statistics for
 2330  * the given tree and the field len is set for all tree elements.
 2331  * OUT assertion: the field code is set for all tree elements of non
 2332  *     zero code length.
 2333  */
 2334 local void gen_codes (tree, max_code, bl_count)
 2335     ct_data *tree;             /* the tree to decorate */
 2336     int max_code;              /* largest code with non zero frequency */
 2337     ushf *bl_count;            /* number of codes at each bit length */
 2338 {
 2339     ush next_code[MAX_BITS+1]; /* next code value for each bit length */
 2340     ush code = 0;              /* running code value */
 2341     int bits;                  /* bit index */
 2342     int n;                     /* code index */
 2343 
 2344     /* The distribution counts are first used to generate the code values
 2345      * without bit reversal.
 2346      */
 2347     for (bits = 1; bits <= MAX_BITS; bits++) {
 2348         next_code[bits] = code = (code + bl_count[bits-1]) << 1;
 2349     }
 2350     /* Check that the bit counts in bl_count are consistent. The last code
 2351      * must be all ones.
 2352      */
 2353     Assert (code + bl_count[MAX_BITS]-1 == (1<<MAX_BITS)-1,
 2354             "inconsistent bit counts");
 2355     Tracev((stderr,"\ngen_codes: max_code %d ", max_code));
 2356 
 2357     for (n = 0;  n <= max_code; n++) {
 2358         int len = tree[n].Len;
 2359         if (len == 0) continue;
 2360         /* Now reverse the bits */
 2361         tree[n].Code = bi_reverse(next_code[len]++, len);
 2362 
 2363         Tracecv(tree != static_ltree, (stderr,"\nn %3d %c l %2d c %4x (%x) ",
 2364              n, (isgraph(n) ? n : ' '), len, tree[n].Code, next_code[len]-1));
 2365     }
 2366 }
 2367 
 2368 /* ===========================================================================
 2369  * Construct one Huffman tree and assigns the code bit strings and lengths.
 2370  * Update the total bit length for the current block.
 2371  * IN assertion: the field freq is set for all tree elements.
 2372  * OUT assertions: the fields len and code are set to the optimal bit length
 2373  *     and corresponding code. The length opt_len is updated; static_len is
 2374  *     also updated if stree is not null. The field max_code is set.
 2375  */
 2376 local void build_tree(s, desc)
 2377     deflate_state *s;
 2378     tree_desc *desc; /* the tree descriptor */
 2379 {
 2380     ct_data *tree   = desc->dyn_tree;
 2381     ct_data *stree  = desc->stat_desc->static_tree;
 2382     int elems       = desc->stat_desc->elems;
 2383     int n, m;          /* iterate over heap elements */
 2384     int max_code = -1; /* largest code with non zero frequency */
 2385     int node;          /* new node being created */
 2386 
 2387     /* Construct the initial heap, with least frequent element in
 2388      * heap[SMALLEST]. The sons of heap[n] are heap[2*n] and heap[2*n+1].
 2389      * heap[0] is not used.
 2390      */
 2391     s->heap_len = 0, s->heap_max = HEAP_SIZE;
 2392 
 2393     for (n = 0; n < elems; n++) {
 2394         if (tree[n].Freq != 0) {
 2395             s->heap[++(s->heap_len)] = max_code = n;
 2396             s->depth[n] = 0;
 2397         } else {
 2398             tree[n].Len = 0;
 2399         }
 2400     }
 2401 
 2402     /* The pkzip format requires that at least one distance code exists,
 2403      * and that at least one bit should be sent even if there is only one
 2404      * possible code. So to avoid special checks later on we force at least
 2405      * two codes of non zero frequency.
 2406      */
 2407     while (s->heap_len < 2) {
 2408         node = s->heap[++(s->heap_len)] = (max_code < 2 ? ++max_code : 0);
 2409         tree[node].Freq = 1;
 2410         s->depth[node] = 0;
 2411         s->opt_len--; if (stree) s->static_len -= stree[node].Len;
 2412         /* node is 0 or 1 so it does not have extra bits */
 2413     }
 2414     desc->max_code = max_code;
 2415 
 2416     /* The elements heap[heap_len/2+1 .. heap_len] are leaves of the tree,
 2417      * establish sub-heaps of increasing lengths:
 2418      */
 2419     for (n = s->heap_len/2; n >= 1; n--) pqdownheap(s, tree, n);
 2420 
 2421     /* Construct the Huffman tree by repeatedly combining the least two
 2422      * frequent nodes.
 2423      */
 2424     node = elems;              /* next internal node of the tree */
 2425     do {
 2426         pqremove(s, tree, n);  /* n = node of least frequency */
 2427         m = s->heap[SMALLEST]; /* m = node of next least frequency */
 2428 
 2429         s->heap[--(s->heap_max)] = n; /* keep the nodes sorted by frequency */
 2430         s->heap[--(s->heap_max)] = m;
 2431 
 2432         /* Create a new node father of n and m */
 2433         tree[node].Freq = tree[n].Freq + tree[m].Freq;
 2434         s->depth[node] = (uch) (MAX(s->depth[n], s->depth[m]) + 1);
 2435         tree[n].Dad = tree[m].Dad = (ush)node;
 2436 #ifdef DUMP_BL_TREE
 2437         if (tree == s->bl_tree) {
 2438             fprintf(stderr,"\nnode %d(%d), sons %d(%d) %d(%d)",
 2439                     node, tree[node].Freq, n, tree[n].Freq, m, tree[m].Freq);
 2440         }
 2441 #endif
 2442         /* and insert the new node in the heap */
 2443         s->heap[SMALLEST] = node++;
 2444         pqdownheap(s, tree, SMALLEST);
 2445 
 2446     } while (s->heap_len >= 2);
 2447 
 2448     s->heap[--(s->heap_max)] = s->heap[SMALLEST];
 2449 
 2450     /* At this point, the fields freq and dad are set. We can now
 2451      * generate the bit lengths.
 2452      */
 2453     gen_bitlen(s, (tree_desc *)desc);
 2454 
 2455     /* The field len is now set, we can generate the bit codes */
 2456     gen_codes ((ct_data *)tree, max_code, s->bl_count);
 2457 }
 2458 
 2459 /* ===========================================================================
 2460  * Scan a literal or distance tree to determine the frequencies of the codes
 2461  * in the bit length tree.
 2462  */
 2463 local void scan_tree (s, tree, max_code)
 2464     deflate_state *s;
 2465     ct_data *tree;   /* the tree to be scanned */
 2466     int max_code;    /* and its largest code of non zero frequency */
 2467 {
 2468     int n;                     /* iterates over all tree elements */
 2469     int prevlen = -1;          /* last emitted length */
 2470     int curlen;                /* length of current code */
 2471     int nextlen = tree[0].Len; /* length of next code */
 2472     int count = 0;             /* repeat count of the current code */
 2473     int max_count = 7;         /* max repeat count */
 2474     int min_count = 4;         /* min repeat count */
 2475 
 2476     if (nextlen == 0) max_count = 138, min_count = 3;
 2477     tree[max_code+1].Len = (ush)0xffff; /* guard */
 2478 
 2479     for (n = 0; n <= max_code; n++) {
 2480         curlen = nextlen; nextlen = tree[n+1].Len;
 2481         if (++count < max_count && curlen == nextlen) {
 2482             continue;
 2483         } else if (count < min_count) {
 2484             s->bl_tree[curlen].Freq += count;
 2485         } else if (curlen != 0) {
 2486             if (curlen != prevlen) s->bl_tree[curlen].Freq++;
 2487             s->bl_tree[REP_3_6].Freq++;
 2488         } else if (count <= 10) {
 2489             s->bl_tree[REPZ_3_10].Freq++;
 2490         } else {
 2491             s->bl_tree[REPZ_11_138].Freq++;
 2492         }
 2493         count = 0; prevlen = curlen;
 2494         if (nextlen == 0) {
 2495             max_count = 138, min_count = 3;
 2496         } else if (curlen == nextlen) {
 2497             max_count = 6, min_count = 3;
 2498         } else {
 2499             max_count = 7, min_count = 4;
 2500         }
 2501     }
 2502 }
 2503 
 2504 /* ===========================================================================
 2505  * Send a literal or distance tree in compressed form, using the codes in
 2506  * bl_tree.
 2507  */
 2508 local void send_tree (s, tree, max_code)
 2509     deflate_state *s;
 2510     ct_data *tree; /* the tree to be scanned */
 2511     int max_code;       /* and its largest code of non zero frequency */
 2512 {
 2513     int n;                     /* iterates over all tree elements */
 2514     int prevlen = -1;          /* last emitted length */
 2515     int curlen;                /* length of current code */
 2516     int nextlen = tree[0].Len; /* length of next code */
 2517     int count = 0;             /* repeat count of the current code */
 2518     int max_count = 7;         /* max repeat count */
 2519     int min_count = 4;         /* min repeat count */
 2520 
 2521     /* tree[max_code+1].Len = -1; */  /* guard already set */
 2522     if (nextlen == 0) max_count = 138, min_count = 3;
 2523 
 2524     for (n = 0; n <= max_code; n++) {
 2525         curlen = nextlen; nextlen = tree[n+1].Len;
 2526         if (++count < max_count && curlen == nextlen) {
 2527             continue;
 2528         } else if (count < min_count) {
 2529             do { send_code(s, curlen, s->bl_tree); } while (--count != 0);
 2530 
 2531         } else if (curlen != 0) {
 2532             if (curlen != prevlen) {
 2533                 send_code(s, curlen, s->bl_tree); count--;
 2534             }
 2535             Assert(count >= 3 && count <= 6, " 3_6?");
 2536             send_code(s, REP_3_6, s->bl_tree); send_bits(s, count-3, 2);
 2537 
 2538         } else if (count <= 10) {
 2539             send_code(s, REPZ_3_10, s->bl_tree); send_bits(s, count-3, 3);
 2540 
 2541         } else {
 2542             send_code(s, REPZ_11_138, s->bl_tree); send_bits(s, count-11, 7);
 2543         }
 2544         count = 0; prevlen = curlen;
 2545         if (nextlen == 0) {
 2546             max_count = 138, min_count = 3;
 2547         } else if (curlen == nextlen) {
 2548             max_count = 6, min_count = 3;
 2549         } else {
 2550             max_count = 7, min_count = 4;
 2551         }
 2552     }
 2553 }
 2554 
 2555 /* ===========================================================================
 2556  * Construct the Huffman tree for the bit lengths and return the index in
 2557  * bl_order of the last bit length code to send.
 2558  */
 2559 local int build_bl_tree(s)
 2560     deflate_state *s;
 2561 {
 2562     int max_blindex;  /* index of last bit length code of non zero freq */
 2563 
 2564     /* Determine the bit length frequencies for literal and distance trees */
 2565     scan_tree(s, (ct_data *)s->dyn_ltree, s->l_desc.max_code);
 2566     scan_tree(s, (ct_data *)s->dyn_dtree, s->d_desc.max_code);
 2567 
 2568     /* Build the bit length tree: */
 2569     build_tree(s, (tree_desc *)(&(s->bl_desc)));
 2570     /* opt_len now includes the length of the tree representations, except
 2571      * the lengths of the bit lengths codes and the 5+5+4 bits for the counts.
 2572      */
 2573 
 2574     /* Determine the number of bit length codes to send. The pkzip format
 2575      * requires that at least 4 bit length codes be sent. (appnote.txt says
 2576      * 3 but the actual value used is 4.)
 2577      */
 2578     for (max_blindex = BL_CODES-1; max_blindex >= 3; max_blindex--) {
 2579         if (s->bl_tree[bl_order[max_blindex]].Len != 0) break;
 2580     }
 2581     /* Update opt_len to include the bit length tree and counts */
 2582     s->opt_len += 3*(max_blindex+1) + 5+5+4;
 2583     Tracev((stderr, "\ndyn trees: dyn %ld, stat %ld",
 2584             s->opt_len, s->static_len));
 2585 
 2586     return max_blindex;
 2587 }
 2588 
 2589 /* ===========================================================================
 2590  * Send the header for a block using dynamic Huffman trees: the counts, the
 2591  * lengths of the bit length codes, the literal tree and the distance tree.
 2592  * IN assertion: lcodes >= 257, dcodes >= 1, blcodes >= 4.
 2593  */
 2594 local void send_all_trees(s, lcodes, dcodes, blcodes)
 2595     deflate_state *s;
 2596     int lcodes, dcodes, blcodes; /* number of codes for each tree */
 2597 {
 2598     int rank;                    /* index in bl_order */
 2599 
 2600     Assert (lcodes >= 257 && dcodes >= 1 && blcodes >= 4, "not enough codes");
 2601     Assert (lcodes <= L_CODES && dcodes <= D_CODES && blcodes <= BL_CODES,
 2602             "too many codes");
 2603     Tracev((stderr, "\nbl counts: "));
 2604     send_bits(s, lcodes-257, 5); /* not +255 as stated in appnote.txt */
 2605     send_bits(s, dcodes-1,   5);
 2606     send_bits(s, blcodes-4,  4); /* not -3 as stated in appnote.txt */
 2607     for (rank = 0; rank < blcodes; rank++) {
 2608         Tracev((stderr, "\nbl code %2d ", bl_order[rank]));
 2609         send_bits(s, s->bl_tree[bl_order[rank]].Len, 3);
 2610     }
 2611     Tracev((stderr, "\nbl tree: sent %ld", s->bits_sent));
 2612 
 2613     send_tree(s, (ct_data *)s->dyn_ltree, lcodes-1); /* literal tree */
 2614     Tracev((stderr, "\nlit tree: sent %ld", s->bits_sent));
 2615 
 2616     send_tree(s, (ct_data *)s->dyn_dtree, dcodes-1); /* distance tree */
 2617     Tracev((stderr, "\ndist tree: sent %ld", s->bits_sent));
 2618 }
 2619 
 2620 /* ===========================================================================
 2621  * Send a stored block
 2622  */
 2623 void _tr_stored_block(s, buf, stored_len, eof)
 2624     deflate_state *s;
 2625     charf *buf;       /* input block */
 2626     ulg stored_len;   /* length of input block */
 2627     int eof;          /* true if this is the last block for a file */
 2628 {
 2629     send_bits(s, (STORED_BLOCK<<1)+eof, 3);  /* send block type */
 2630     s->compressed_len = (s->compressed_len + 3 + 7) & (ulg)~7L;
 2631     s->compressed_len += (stored_len + 4) << 3;
 2632 
 2633     copy_block(s, buf, (unsigned)stored_len, 1); /* with header */
 2634 }
 2635 
 2636 /* Send just the `stored block' type code without any length bytes or data.
 2637  */
 2638 void _tr_stored_type_only(s)
 2639     deflate_state *s;
 2640 {
 2641     send_bits(s, (STORED_BLOCK << 1), 3);
 2642     bi_windup(s);
 2643     s->compressed_len = (s->compressed_len + 3) & ~7L;
 2644 }
 2645 
 2646 
 2647 /* ===========================================================================
 2648  * Send one empty static block to give enough lookahead for inflate.
 2649  * This takes 10 bits, of which 7 may remain in the bit buffer.
 2650  * The current inflate code requires 9 bits of lookahead. If the
 2651  * last two codes for the previous block (real code plus EOB) were coded
 2652  * on 5 bits or less, inflate may have only 5+3 bits of lookahead to decode
 2653  * the last real code. In this case we send two empty static blocks instead
 2654  * of one. (There are no problems if the previous block is stored or fixed.)
 2655  * To simplify the code, we assume the worst case of last real code encoded
 2656  * on one bit only.
 2657  */
 2658 void _tr_align(s)
 2659     deflate_state *s;
 2660 {
 2661     send_bits(s, STATIC_TREES<<1, 3);
 2662     send_code(s, END_BLOCK, static_ltree);
 2663     s->compressed_len += 10L; /* 3 for block type, 7 for EOB */
 2664     bi_flush(s);
 2665     /* Of the 10 bits for the empty block, we have already sent
 2666      * (10 - bi_valid) bits. The lookahead for the last real code (before
 2667      * the EOB of the previous block) was thus at least one plus the length
 2668      * of the EOB plus what we have just sent of the empty static block.
 2669      */
 2670     if (1 + s->last_eob_len + 10 - s->bi_valid < 9) {
 2671         send_bits(s, STATIC_TREES<<1, 3);
 2672         send_code(s, END_BLOCK, static_ltree);
 2673         s->compressed_len += 10L;
 2674         bi_flush(s);
 2675     }
 2676     s->last_eob_len = 7;
 2677 }
 2678 
 2679 /* ===========================================================================
 2680  * Determine the best encoding for the current block: dynamic trees, static
 2681  * trees or store, and output the encoded block to the zip file. This function
 2682  * returns the total compressed length for the file so far.
 2683  */
 2684 ulg _tr_flush_block(s, buf, stored_len, eof)
 2685     deflate_state *s;
 2686     charf *buf;       /* input block, or NULL if too old */
 2687     ulg stored_len;   /* length of input block */
 2688     int eof;          /* true if this is the last block for a file */
 2689 {
 2690     ulg opt_lenb, static_lenb; /* opt_len and static_len in bytes */
 2691     int max_blindex = 0;  /* index of last bit length code of non zero freq */
 2692 
 2693     /* Build the Huffman trees unless a stored block is forced */
 2694     if (s->level > 0) {
 2695 
 2696          /* Check if the file is ascii or binary */
 2697         if (s->data_type == Z_UNKNOWN) set_data_type(s);
 2698 
 2699         /* Construct the literal and distance trees */
 2700         build_tree(s, (tree_desc *)(&(s->l_desc)));
 2701         Tracev((stderr, "\nlit data: dyn %ld, stat %ld", s->opt_len,
 2702                 s->static_len));
 2703 
 2704         build_tree(s, (tree_desc *)(&(s->d_desc)));
 2705         Tracev((stderr, "\ndist data: dyn %ld, stat %ld", s->opt_len,
 2706                 s->static_len));
 2707         /* At this point, opt_len and static_len are the total bit lengths of
 2708          * the compressed block data, excluding the tree representations.
 2709          */
 2710 
 2711         /* Build the bit length tree for the above two trees, and get the index
 2712          * in bl_order of the last bit length code to send.
 2713          */
 2714         max_blindex = build_bl_tree(s);
 2715 
 2716         /* Determine the best encoding. Compute first the block length in bytes*/
 2717         opt_lenb = (s->opt_len+3+7)>>3;
 2718         static_lenb = (s->static_len+3+7)>>3;
 2719 
 2720         Tracev((stderr, "\nopt %lu(%lu) stat %lu(%lu) stored %lu lit %u ",
 2721                 opt_lenb, s->opt_len, static_lenb, s->static_len, stored_len,
 2722                 s->last_lit));
 2723 
 2724         if (static_lenb <= opt_lenb) opt_lenb = static_lenb;
 2725 
 2726     } else {
 2727         Assert(buf != (char*)0, "lost buf");
 2728         opt_lenb = static_lenb = stored_len + 5; /* force a stored block */
 2729     }
 2730 
 2731     /* If compression failed and this is the first and last block,
 2732      * and if the .zip file can be seeked (to rewrite the local header),
 2733      * the whole file is transformed into a stored file:
 2734      */
 2735 #ifdef STORED_FILE_OK
 2736 #  ifdef FORCE_STORED_FILE
 2737     if (eof && s->compressed_len == 0L) { /* force stored file */
 2738 #  else
 2739     if (stored_len <= opt_lenb && eof && s->compressed_len==0L && seekable()) {
 2740 #  endif
 2741         /* Since LIT_BUFSIZE <= 2*WSIZE, the input data must be there: */
 2742         if (buf == (charf*)0) error ("block vanished");
 2743 
 2744         copy_block(s, buf, (unsigned)stored_len, 0); /* without header */
 2745         s->compressed_len = stored_len << 3;
 2746         s->method = STORED;
 2747     } else
 2748 #endif /* STORED_FILE_OK */
 2749 
 2750 #ifdef FORCE_STORED
 2751     if (buf != (char*)0) { /* force stored block */
 2752 #else
 2753     if (stored_len+4 <= opt_lenb && buf != (char*)0) {
 2754                        /* 4: two words for the lengths */
 2755 #endif
 2756         /* The test buf != NULL is only necessary if LIT_BUFSIZE > WSIZE.
 2757          * Otherwise we can't have processed more than WSIZE input bytes since
 2758          * the last block flush, because compression would have been
 2759          * successful. If LIT_BUFSIZE <= WSIZE, it is never too late to
 2760          * transform a block into a stored block.
 2761          */
 2762         _tr_stored_block(s, buf, stored_len, eof);
 2763 
 2764 #ifdef FORCE_STATIC
 2765     } else if (static_lenb >= 0) { /* force static trees */
 2766 #else
 2767     } else if (static_lenb == opt_lenb) {
 2768 #endif
 2769         send_bits(s, (STATIC_TREES<<1)+eof, 3);
 2770         compress_block(s, (ct_data *)static_ltree, (ct_data *)static_dtree);
 2771         s->compressed_len += 3 + s->static_len;
 2772     } else {
 2773         send_bits(s, (DYN_TREES<<1)+eof, 3);
 2774         send_all_trees(s, s->l_desc.max_code+1, s->d_desc.max_code+1,
 2775                        max_blindex+1);
 2776         compress_block(s, (ct_data *)s->dyn_ltree, (ct_data *)s->dyn_dtree);
 2777         s->compressed_len += 3 + s->opt_len;
 2778     }
 2779     Assert (s->compressed_len == s->bits_sent, "bad compressed size");
 2780     init_block(s);
 2781 
 2782     if (eof) {
 2783         bi_windup(s);
 2784         s->compressed_len += 7;  /* align on byte boundary */
 2785     }
 2786     Tracev((stderr,"\ncomprlen %lu(%lu) ", s->compressed_len>>3,
 2787            s->compressed_len-7*eof));
 2788 
 2789     return s->compressed_len >> 3;
 2790 }
 2791 
 2792 /* ===========================================================================
 2793  * Save the match info and tally the frequency counts. Return true if
 2794  * the current block must be flushed.
 2795  */
 2796 int _tr_tally (s, dist, lc)
 2797     deflate_state *s;
 2798     unsigned dist;  /* distance of matched string */
 2799     unsigned lc;    /* match length-MIN_MATCH or unmatched char (if dist==0) */
 2800 {
 2801     s->d_buf[s->last_lit] = (ush)dist;
 2802     s->l_buf[s->last_lit++] = (uch)lc;
 2803     if (dist == 0) {
 2804         /* lc is the unmatched char */
 2805         s->dyn_ltree[lc].Freq++;
 2806     } else {
 2807         s->matches++;
 2808         /* Here, lc is the match length - MIN_MATCH */
 2809         dist--;             /* dist = match distance - 1 */
 2810         Assert((ush)dist < (ush)MAX_DIST(s) &&
 2811                (ush)lc <= (ush)(MAX_MATCH-MIN_MATCH) &&
 2812                (ush)d_code(dist) < (ush)D_CODES,  "_tr_tally: bad match");
 2813 
 2814         s->dyn_ltree[length_code[lc]+LITERALS+1].Freq++;
 2815         s->dyn_dtree[d_code(dist)].Freq++;
 2816     }
 2817 
 2818     /* Try to guess if it is profitable to stop the current block here */
 2819     if (s->level > 2 && (s->last_lit & 0xfff) == 0) {
 2820         /* Compute an upper bound for the compressed length */
 2821         ulg out_length = (ulg)s->last_lit*8L;
 2822         ulg in_length = (ulg)((long)s->strstart - s->block_start);
 2823         int dcode;
 2824         for (dcode = 0; dcode < D_CODES; dcode++) {
 2825             out_length += (ulg)s->dyn_dtree[dcode].Freq *
 2826                 (5L+extra_dbits[dcode]);
 2827         }
 2828         out_length >>= 3;
 2829         Tracev((stderr,"\nlast_lit %u, in %ld, out ~%ld(%ld%%) ",
 2830                s->last_lit, in_length, out_length,
 2831                100L - out_length*100L/in_length));
 2832         if (s->matches < s->last_lit/2 && out_length < in_length/2) return 1;
 2833     }
 2834     return (s->last_lit == s->lit_bufsize-1);
 2835     /* We avoid equality with lit_bufsize because of wraparound at 64K
 2836      * on 16 bit machines and because stored blocks are restricted to
 2837      * 64K-1 bytes.
 2838      */
 2839 }
 2840 
 2841 /* ===========================================================================
 2842  * Send the block data compressed using the given Huffman trees
 2843  */
 2844 local void compress_block(s, ltree, dtree)
 2845     deflate_state *s;
 2846     ct_data *ltree; /* literal tree */
 2847     ct_data *dtree; /* distance tree */
 2848 {
 2849     unsigned dist;      /* distance of matched string */
 2850     int lc;             /* match length or unmatched char (if dist == 0) */
 2851     unsigned lx = 0;    /* running index in l_buf */
 2852     unsigned code;      /* the code to send */
 2853     int extra;          /* number of extra bits to send */
 2854 
 2855     if (s->last_lit != 0) do {
 2856         dist = s->d_buf[lx];
 2857         lc = s->l_buf[lx++];
 2858         if (dist == 0) {
 2859             send_code(s, lc, ltree); /* send a literal byte */
 2860             Tracecv(isgraph(lc), (stderr," '%c' ", lc));
 2861         } else {
 2862             /* Here, lc is the match length - MIN_MATCH */
 2863             code = length_code[lc];
 2864             send_code(s, code+LITERALS+1, ltree); /* send the length code */
 2865             extra = extra_lbits[code];
 2866             if (extra != 0) {
 2867                 lc -= base_length[code];
 2868                 send_bits(s, lc, extra);       /* send the extra length bits */
 2869             }
 2870             dist--; /* dist is now the match distance - 1 */
 2871             code = d_code(dist);
 2872             Assert (code < D_CODES, "bad d_code");
 2873 
 2874             send_code(s, code, dtree);       /* send the distance code */
 2875             extra = extra_dbits[code];
 2876             if (extra != 0) {
 2877                 dist -= base_dist[code];
 2878                 send_bits(s, dist, extra);   /* send the extra distance bits */
 2879             }
 2880         } /* literal or match pair ? */
 2881 
 2882         /* Check that the overlay between pending_buf and d_buf+l_buf is ok: */
 2883         Assert(s->pending < s->lit_bufsize + 2*lx, "pendingBuf overflow");
 2884 
 2885     } while (lx < s->last_lit);
 2886 
 2887     send_code(s, END_BLOCK, ltree);
 2888     s->last_eob_len = ltree[END_BLOCK].Len;
 2889 }
 2890 
 2891 /* ===========================================================================
 2892  * Set the data type to ASCII or BINARY, using a crude approximation:
 2893  * binary if more than 20% of the bytes are <= 6 or >= 128, ascii otherwise.
 2894  * IN assertion: the fields freq of dyn_ltree are set and the total of all
 2895  * frequencies does not exceed 64K (to fit in an int on 16 bit machines).
 2896  */
 2897 local void set_data_type(s)
 2898     deflate_state *s;
 2899 {
 2900     int n = 0;
 2901     unsigned ascii_freq = 0;
 2902     unsigned bin_freq = 0;
 2903     while (n < 7)        bin_freq += s->dyn_ltree[n++].Freq;
 2904     while (n < 128)    ascii_freq += s->dyn_ltree[n++].Freq;
 2905     while (n < LITERALS) bin_freq += s->dyn_ltree[n++].Freq;
 2906     s->data_type = (Byte)(bin_freq > (ascii_freq >> 2) ? Z_BINARY : Z_ASCII);
 2907 }
 2908 
 2909 /* ===========================================================================
 2910  * Reverse the first len bits of a code, using straightforward code (a faster
 2911  * method would use a table)
 2912  * IN assertion: 1 <= len <= 15
 2913  */
 2914 local unsigned bi_reverse(code, len)
 2915     unsigned code; /* the value to invert */
 2916     int len;       /* its bit length */
 2917 {
 2918     register unsigned res = 0;
 2919     do {
 2920         res |= code & 1;
 2921         code >>= 1, res <<= 1;
 2922     } while (--len > 0);
 2923     return res >> 1;
 2924 }
 2925 
 2926 /* ===========================================================================
 2927  * Flush the bit buffer, keeping at most 7 bits in it.
 2928  */
 2929 local void bi_flush(s)
 2930     deflate_state *s;
 2931 {
 2932     if (s->bi_valid == 16) {
 2933         put_short(s, s->bi_buf);
 2934         s->bi_buf = 0;
 2935         s->bi_valid = 0;
 2936     } else if (s->bi_valid >= 8) {
 2937         put_byte(s, (Byte)s->bi_buf);
 2938         s->bi_buf >>= 8;
 2939         s->bi_valid -= 8;
 2940     }
 2941 }
 2942 
 2943 /* ===========================================================================
 2944  * Flush the bit buffer and align the output on a byte boundary
 2945  */
 2946 local void bi_windup(s)
 2947     deflate_state *s;
 2948 {
 2949     if (s->bi_valid > 8) {
 2950         put_short(s, s->bi_buf);
 2951     } else if (s->bi_valid > 0) {
 2952         put_byte(s, (Byte)s->bi_buf);
 2953     }
 2954     s->bi_buf = 0;
 2955     s->bi_valid = 0;
 2956 #ifdef DEBUG_ZLIB
 2957     s->bits_sent = (s->bits_sent+7) & ~7;
 2958 #endif
 2959 }
 2960 
 2961 /* ===========================================================================
 2962  * Copy a stored block, storing first the length and its
 2963  * one's complement if requested.
 2964  */
 2965 local void copy_block(s, buf, len, header)
 2966     deflate_state *s;
 2967     charf    *buf;    /* the input data */
 2968     unsigned len;     /* its length */
 2969     int      header;  /* true if block header must be written */
 2970 {
 2971     bi_windup(s);        /* align on byte boundary */
 2972     s->last_eob_len = 8; /* enough lookahead for inflate */
 2973 
 2974     if (header) {
 2975         put_short(s, (ush)len);   
 2976         put_short(s, (ush)~len);
 2977 #ifdef DEBUG_ZLIB
 2978         s->bits_sent += 2*16;
 2979 #endif
 2980     }
 2981 #ifdef DEBUG_ZLIB
 2982     s->bits_sent += (ulg)len<<3;
 2983 #endif
 2984     /* bundle up the put_byte(s, *buf++) calls */
 2985     zmemcpy(&s->pending_buf[s->pending], buf, len);
 2986     s->pending += len;
 2987 }
 2988 /* --- trees.c */
 2989 
 2990 /* +++ inflate.c */
 2991 /* inflate.c -- zlib interface to inflate modules
 2992  * Copyright (C) 1995-1996 Mark Adler
 2993  * For conditions of distribution and use, see copyright notice in zlib.h 
 2994  */
 2995 
 2996 /* #include "zutil.h" */
 2997 
 2998 /* +++ infblock.h */
 2999 /* infblock.h -- header to use infblock.c
 3000  * Copyright (C) 1995-1996 Mark Adler
 3001  * For conditions of distribution and use, see copyright notice in zlib.h 
 3002  */
 3003 
 3004 /* WARNING: this file should *not* be used by applications. It is
 3005    part of the implementation of the compression library and is
 3006    subject to change. Applications should only use zlib.h.
 3007  */
 3008 
 3009 struct inflate_blocks_state;
 3010 typedef struct inflate_blocks_state FAR inflate_blocks_statef;
 3011 
 3012 extern inflate_blocks_statef * inflate_blocks_new OF((
 3013     z_streamp z,
 3014     check_func c,               /* check function */
 3015     uInt w));                   /* window size */
 3016 
 3017 extern int inflate_blocks OF((
 3018     inflate_blocks_statef *,
 3019     z_streamp ,
 3020     int));                      /* initial return code */
 3021 
 3022 extern void inflate_blocks_reset OF((
 3023     inflate_blocks_statef *,
 3024     z_streamp ,
 3025     uLongf *));                  /* check value on output */
 3026 
 3027 extern int inflate_blocks_free OF((
 3028     inflate_blocks_statef *,
 3029     z_streamp ,
 3030     uLongf *));                  /* check value on output */
 3031 
 3032 extern void inflate_set_dictionary OF((
 3033     inflate_blocks_statef *s,
 3034     const Bytef *d,  /* dictionary */
 3035     uInt  n));       /* dictionary length */
 3036 
 3037 extern int inflate_addhistory OF((
 3038     inflate_blocks_statef *,
 3039     z_streamp));
 3040 
 3041 extern int inflate_packet_flush OF((
 3042     inflate_blocks_statef *));
 3043 /* --- infblock.h */
 3044 
 3045 #ifndef NO_DUMMY_DECL
 3046 struct inflate_blocks_state {int dummy;}; /* for buggy compilers */
 3047 #endif
 3048 
 3049 /* inflate private state */
 3050 struct internal_state {
 3051 
 3052   /* mode */
 3053   enum {
 3054       METHOD,   /* waiting for method byte */
 3055       FLAG,     /* waiting for flag byte */
 3056       DICT4,    /* four dictionary check bytes to go */
 3057       DICT3,    /* three dictionary check bytes to go */
 3058       DICT2,    /* two dictionary check bytes to go */
 3059       DICT1,    /* one dictionary check byte to go */
 3060       DICT0,    /* waiting for inflateSetDictionary */
 3061       BLOCKS,   /* decompressing blocks */
 3062       CHECK4,   /* four check bytes to go */
 3063       CHECK3,   /* three check bytes to go */
 3064       CHECK2,   /* two check bytes to go */
 3065       CHECK1,   /* one check byte to go */
 3066       DONE,     /* finished check, done */
 3067       BAD}      /* got an error--stay here */
 3068     mode;               /* current inflate mode */
 3069 
 3070   /* mode dependent information */
 3071   union {
 3072     uInt method;        /* if FLAGS, method byte */
 3073     struct {
 3074       uLong was;                /* computed check value */
 3075       uLong need;               /* stream check value */
 3076     } check;            /* if CHECK, check values to compare */
 3077     uInt marker;        /* if BAD, inflateSync's marker bytes count */
 3078   } sub;        /* submode */
 3079 
 3080   /* mode independent information */
 3081   int  nowrap;          /* flag for no wrapper */
 3082   uInt wbits;           /* log2(window size)  (8..15, defaults to 15) */
 3083   inflate_blocks_statef 
 3084     *blocks;            /* current inflate_blocks state */
 3085 
 3086 };
 3087 
 3088 
 3089 int inflateReset(z)
 3090 z_streamp z;
 3091 {
 3092   uLong c;
 3093 
 3094   if (z == Z_NULL || z->state == Z_NULL)
 3095     return Z_STREAM_ERROR;
 3096   z->total_in = z->total_out = 0;
 3097   z->msg = Z_NULL;
 3098   z->state->mode = z->state->nowrap ? BLOCKS : METHOD;
 3099   inflate_blocks_reset(z->state->blocks, z, &c);
 3100   Trace((stderr, "inflate: reset\n"));
 3101   return Z_OK;
 3102 }
 3103 
 3104 
 3105 int inflateEnd(z)
 3106 z_streamp z;
 3107 {
 3108   uLong c;
 3109 
 3110   if (z == Z_NULL || z->state == Z_NULL || z->zfree == Z_NULL)
 3111     return Z_STREAM_ERROR;
 3112   if (z->state->blocks != Z_NULL)
 3113     inflate_blocks_free(z->state->blocks, z, &c);
 3114   ZFREE(z, z->state);
 3115   z->state = Z_NULL;
 3116   Trace((stderr, "inflate: end\n"));
 3117   return Z_OK;
 3118 }
 3119 
 3120 
 3121 int inflateInit2_(z, w, version, stream_size)
 3122 z_streamp z;
 3123 int w;
 3124 const char *version;
 3125 int stream_size;
 3126 {
 3127   if (version == Z_NULL || version[0] != ZLIB_VERSION[0] ||
 3128       stream_size != sizeof(z_stream))
 3129       return Z_VERSION_ERROR;
 3130 
 3131   /* initialize state */
 3132   if (z == Z_NULL)
 3133     return Z_STREAM_ERROR;
 3134   z->msg = Z_NULL;
 3135 #ifndef NO_ZCFUNCS
 3136   if (z->zalloc == Z_NULL)
 3137   {
 3138     z->zalloc = zcalloc;
 3139     z->opaque = (voidpf)0;
 3140   }
 3141   if (z->zfree == Z_NULL) z->zfree = zcfree;
 3142 #endif
 3143   if ((z->state = (struct internal_state FAR *)
 3144        ZALLOC(z,1,sizeof(struct internal_state))) == Z_NULL)
 3145     return Z_MEM_ERROR;
 3146   z->state->blocks = Z_NULL;
 3147 
 3148   /* handle undocumented nowrap option (no zlib header or check) */
 3149   z->state->nowrap = 0;
 3150   if (w < 0)
 3151   {
 3152     w = - w;
 3153     z->state->nowrap = 1;
 3154   }
 3155 
 3156   /* set window size */
 3157   if (w < 8 || w > 15)
 3158   {
 3159     inflateEnd(z);
 3160     return Z_STREAM_ERROR;
 3161   }
 3162   z->state->wbits = (uInt)w;
 3163 
 3164   /* create inflate_blocks state */
 3165   if ((z->state->blocks =
 3166       inflate_blocks_new(z, z->state->nowrap ? Z_NULL : adler32, (uInt)1 << w))
 3167       == Z_NULL)
 3168   {
 3169     inflateEnd(z);
 3170     return Z_MEM_ERROR;
 3171   }
 3172   Trace((stderr, "inflate: allocated\n"));
 3173 
 3174   /* reset state */
 3175   inflateReset(z);
 3176   return Z_OK;
 3177 }
 3178 
 3179 
 3180 int inflateInit_(z, version, stream_size)
 3181 z_streamp z;
 3182 const char *version;
 3183 int stream_size;
 3184 {
 3185   return inflateInit2_(z, DEF_WBITS, version, stream_size);
 3186 }
 3187 
 3188 
 3189 #define NEEDBYTE {if(z->avail_in==0)goto empty;r=Z_OK;}
 3190 #define NEXTBYTE (z->avail_in--,z->total_in++,*z->next_in++)
 3191 
 3192 int inflate(z, f)
 3193 z_streamp z;
 3194 int f;
 3195 {
 3196   int r;
 3197   uInt b;
 3198 
 3199   if (z == Z_NULL || z->state == Z_NULL || z->next_in == Z_NULL || f < 0)
 3200     return Z_STREAM_ERROR;
 3201   r = Z_BUF_ERROR;
 3202   while (1) switch (z->state->mode)
 3203   {
 3204     case METHOD:
 3205       NEEDBYTE
 3206       if (((z->state->sub.method = NEXTBYTE) & 0xf) != Z_DEFLATED)
 3207       {
 3208         z->state->mode = BAD;
 3209         z->msg = (char*)"unknown compression method";
 3210         z->state->sub.marker = 5;       /* can't try inflateSync */
 3211         break;
 3212       }
 3213       if ((z->state->sub.method >> 4) + 8 > z->state->wbits)
 3214       {
 3215         z->state->mode = BAD;
 3216         z->msg = (char*)"invalid window size";
 3217         z->state->sub.marker = 5;       /* can't try inflateSync */
 3218         break;
 3219       }
 3220       z->state->mode = FLAG;
 3221     case FLAG:
 3222       NEEDBYTE
 3223       b = NEXTBYTE;
 3224       if (((z->state->sub.method << 8) + b) % 31)
 3225       {
 3226         z->state->mode = BAD;
 3227         z->msg = (char*)"incorrect header check";
 3228         z->state->sub.marker = 5;       /* can't try inflateSync */
 3229         break;
 3230       }
 3231       Trace((stderr, "inflate: zlib header ok\n"));
 3232       if (!(b & PRESET_DICT))
 3233       {
 3234         z->state->mode = BLOCKS;
 3235         break;
 3236       }
 3237       z->state->mode = DICT4;
 3238     case DICT4:
 3239       NEEDBYTE
 3240       z->state->sub.check.need = (uLong)NEXTBYTE << 24;
 3241       z->state->mode = DICT3;
 3242     case DICT3:
 3243       NEEDBYTE
 3244       z->state->sub.check.need += (uLong)NEXTBYTE << 16;
 3245       z->state->mode = DICT2;
 3246     case DICT2:
 3247       NEEDBYTE
 3248       z->state->sub.check.need += (uLong)NEXTBYTE << 8;
 3249       z->state->mode = DICT1;
 3250     case DICT1:
 3251       NEEDBYTE
 3252       z->state->sub.check.need += (uLong)NEXTBYTE;
 3253       z->adler = z->state->sub.check.need;
 3254       z->state->mode = DICT0;
 3255       return Z_NEED_DICT;
 3256     case DICT0:
 3257       z->state->mode = BAD;
 3258       z->msg = (char*)"need dictionary";
 3259       z->state->sub.marker = 0;       /* can try inflateSync */
 3260       return Z_STREAM_ERROR;
 3261     case BLOCKS:
 3262       r = inflate_blocks(z->state->blocks, z, r);
 3263       if (f == Z_PACKET_FLUSH && z->avail_in == 0 && z->avail_out != 0)
 3264           r = inflate_packet_flush(z->state->blocks);
 3265       if (r == Z_DATA_ERROR)
 3266       {
 3267         z->state->mode = BAD;
 3268         z->state->sub.marker = 0;       /* can try inflateSync */
 3269         break;
 3270       }
 3271       if (r != Z_STREAM_END)
 3272         return r;
 3273       r = Z_OK;
 3274       inflate_blocks_reset(z->state->blocks, z, &z->state->sub.check.was);
 3275       if (z->state->nowrap)
 3276       {
 3277         z->state->mode = DONE;
 3278         break;
 3279       }
 3280       z->state->mode = CHECK4;
 3281     case CHECK4:
 3282       NEEDBYTE
 3283       z->state->sub.check.need = (uLong)NEXTBYTE << 24;
 3284       z->state->mode = CHECK3;
 3285     case CHECK3:
 3286       NEEDBYTE
 3287       z->state->sub.check.need += (uLong)NEXTBYTE << 16;
 3288       z->state->mode = CHECK2;
 3289     case CHECK2:
 3290       NEEDBYTE
 3291       z->state->sub.check.need += (uLong)NEXTBYTE << 8;
 3292       z->state->mode = CHECK1;
 3293     case CHECK1:
 3294       NEEDBYTE
 3295       z->state->sub.check.need += (uLong)NEXTBYTE;
 3296 
 3297       if (z->state->sub.check.was != z->state->sub.check.need)
 3298       {
 3299         z->state->mode = BAD;
 3300         z->msg = (char*)"incorrect data check";
 3301         z->state->sub.marker = 5;       /* can't try inflateSync */
 3302         break;
 3303       }
 3304       Trace((stderr, "inflate: zlib check ok\n"));
 3305       z->state->mode = DONE;
 3306     case DONE:
 3307       return Z_STREAM_END;
 3308     case BAD:
 3309       return Z_DATA_ERROR;
 3310     default:
 3311       return Z_STREAM_ERROR;
 3312   }
 3313 
 3314  empty:
 3315   if (f != Z_PACKET_FLUSH)
 3316     return r;
 3317   z->state->mode = BAD;
 3318   z->msg = (char *)"need more for packet flush";
 3319   z->state->sub.marker = 0;       /* can try inflateSync */
 3320   return Z_DATA_ERROR;
 3321 }
 3322 
 3323 
 3324 int inflateSetDictionary(z, dictionary, dictLength)
 3325 z_streamp z;
 3326 const Bytef *dictionary;
 3327 uInt  dictLength;
 3328 {
 3329   uInt length = dictLength;
 3330 
 3331   if (z == Z_NULL || z->state == Z_NULL || z->state->mode != DICT0)
 3332     return Z_STREAM_ERROR;
 3333 
 3334   if (adler32(1L, dictionary, dictLength) != z->adler) return Z_DATA_ERROR;
 3335   z->adler = 1L;
 3336 
 3337   if (length >= ((uInt)1<<z->state->wbits))
 3338   {
 3339     length = (1<<z->state->wbits)-1;
 3340     dictionary += dictLength - length;
 3341   }
 3342   inflate_set_dictionary(z->state->blocks, dictionary, length);
 3343   z->state->mode = BLOCKS;
 3344   return Z_OK;
 3345 }
 3346 
 3347 /*
 3348  * This subroutine adds the data at next_in/avail_in to the output history
 3349  * without performing any output.  The output buffer must be "caught up";
 3350  * i.e. no pending output (hence s->read equals s->write), and the state must
 3351  * be BLOCKS (i.e. we should be willing to see the start of a series of
 3352  * BLOCKS).  On exit, the output will also be caught up, and the checksum
 3353  * will have been updated if need be.
 3354  */
 3355 
 3356 int inflateIncomp(z)
 3357 z_stream *z;
 3358 {
 3359     if (z->state->mode != BLOCKS)
 3360         return Z_DATA_ERROR;
 3361     return inflate_addhistory(z->state->blocks, z);
 3362 }
 3363 
 3364 
 3365 int inflateSync(z)
 3366 z_streamp z;
 3367 {
 3368   uInt n;       /* number of bytes to look at */
 3369   Bytef *p;     /* pointer to bytes */
 3370   uInt m;       /* number of marker bytes found in a row */
 3371   uLong r, w;   /* temporaries to save total_in and total_out */
 3372 
 3373   /* set up */
 3374   if (z == Z_NULL || z->state == Z_NULL)
 3375     return Z_STREAM_ERROR;
 3376   if (z->state->mode != BAD)
 3377   {
 3378     z->state->mode = BAD;
 3379     z->state->sub.marker = 0;
 3380   }
 3381   if ((n = z->avail_in) == 0)
 3382     return Z_BUF_ERROR;
 3383   p = z->next_in;
 3384   m = z->state->sub.marker;
 3385 
 3386   /* search */
 3387   while (n && m < 4)
 3388   {
 3389     if (*p == (Byte)(m < 2 ? 0 : 0xff))
 3390       m++;
 3391     else if (*p)
 3392       m = 0;
 3393     else
 3394       m = 4 - m;
 3395     p++, n--;
 3396   }
 3397 
 3398   /* restore */
 3399   z->total_in += p - z->next_in;
 3400   z->next_in = p;
 3401   z->avail_in = n;
 3402   z->state->sub.marker = m;
 3403 
 3404   /* return no joy or set up to restart on a new block */
 3405   if (m != 4)
 3406     return Z_DATA_ERROR;
 3407   r = z->total_in;  w = z->total_out;
 3408   inflateReset(z);
 3409   z->total_in = r;  z->total_out = w;
 3410   z->state->mode = BLOCKS;
 3411   return Z_OK;
 3412 }
 3413 
 3414 #undef NEEDBYTE
 3415 #undef NEXTBYTE
 3416 /* --- inflate.c */
 3417 
 3418 /* +++ infblock.c */
 3419 /* infblock.c -- interpret and process block types to last block
 3420  * Copyright (C) 1995-1996 Mark Adler
 3421  * For conditions of distribution and use, see copyright notice in zlib.h 
 3422  */
 3423 
 3424 /* #include "zutil.h" */
 3425 /* #include "infblock.h" */
 3426 
 3427 /* +++ inftrees.h */
 3428 /* inftrees.h -- header to use inftrees.c
 3429  * Copyright (C) 1995-1996 Mark Adler
 3430  * For conditions of distribution and use, see copyright notice in zlib.h 
 3431  */
 3432 
 3433 /* WARNING: this file should *not* be used by applications. It is
 3434    part of the implementation of the compression library and is
 3435    subject to change. Applications should only use zlib.h.
 3436  */
 3437 
 3438 /* Huffman code lookup table entry--this entry is four bytes for machines
 3439    that have 16-bit pointers (e.g. PC's in the small or medium model). */
 3440 
 3441 typedef struct inflate_huft_s FAR inflate_huft;
 3442 
 3443 struct inflate_huft_s {
 3444   union {
 3445     struct {
 3446       Byte Exop;        /* number of extra bits or operation */
 3447       Byte Bits;        /* number of bits in this code or subcode */
 3448     } what;
 3449     Bytef *pad;         /* pad structure to a power of 2 (4 bytes for */
 3450   } word;               /*  16-bit, 8 bytes for 32-bit machines) */
 3451   union {
 3452     uInt Base;          /* literal, length base, or distance base */
 3453     inflate_huft *Next; /* pointer to next level of table */
 3454   } more;
 3455 };
 3456 
 3457 #ifdef DEBUG_ZLIB
 3458   extern uInt inflate_hufts;
 3459 #endif
 3460 
 3461 extern int inflate_trees_bits OF((
 3462     uIntf *,                    /* 19 code lengths */
 3463     uIntf *,                    /* bits tree desired/actual depth */
 3464     inflate_huft * FAR *,       /* bits tree result */
 3465     z_streamp ));               /* for zalloc, zfree functions */
 3466 
 3467 extern int inflate_trees_dynamic OF((
 3468     uInt,                       /* number of literal/length codes */
 3469     uInt,                       /* number of distance codes */
 3470     uIntf *,                    /* that many (total) code lengths */
 3471     uIntf *,                    /* literal desired/actual bit depth */
 3472     uIntf *,                    /* distance desired/actual bit depth */
 3473     inflate_huft * FAR *,       /* literal/length tree result */
 3474     inflate_huft * FAR *,       /* distance tree result */
 3475     z_streamp ));               /* for zalloc, zfree functions */
 3476 
 3477 extern int inflate_trees_fixed OF((
 3478     uIntf *,                    /* literal desired/actual bit depth */
 3479     uIntf *,                    /* distance desired/actual bit depth */
 3480     inflate_huft * FAR *,       /* literal/length tree result */
 3481     inflate_huft * FAR *));     /* distance tree result */
 3482 
 3483 extern int inflate_trees_free OF((
 3484     inflate_huft *,             /* tables to free */
 3485     z_streamp ));               /* for zfree function */
 3486 
 3487 /* --- inftrees.h */
 3488 
 3489 /* +++ infcodes.h */
 3490 /* infcodes.h -- header to use infcodes.c
 3491  * Copyright (C) 1995-1996 Mark Adler
 3492  * For conditions of distribution and use, see copyright notice in zlib.h 
 3493  */
 3494 
 3495 /* WARNING: this file should *not* be used by applications. It is
 3496    part of the implementation of the compression library and is
 3497    subject to change. Applications should only use zlib.h.
 3498  */
 3499 
 3500 struct inflate_codes_state;
 3501 typedef struct inflate_codes_state FAR inflate_codes_statef;
 3502 
 3503 extern inflate_codes_statef *inflate_codes_new OF((
 3504     uInt, uInt,
 3505     inflate_huft *, inflate_huft *,
 3506     z_streamp ));
 3507 
 3508 extern int inflate_codes OF((
 3509     inflate_blocks_statef *,
 3510     z_streamp ,
 3511     int));
 3512 
 3513 extern void inflate_codes_free OF((
 3514     inflate_codes_statef *,
 3515     z_streamp ));
 3516 
 3517 /* --- infcodes.h */
 3518 
 3519 /* +++ infutil.h */
 3520 /* infutil.h -- types and macros common to blocks and codes
 3521  * Copyright (C) 1995-1996 Mark Adler
 3522  * For conditions of distribution and use, see copyright notice in zlib.h 
 3523  */
 3524 
 3525 /* WARNING: this file should *not* be used by applications. It is
 3526    part of the implementation of the compression library and is
 3527    subject to change. Applications should only use zlib.h.
 3528  */
 3529 
 3530 #ifndef _INFUTIL_H
 3531 #define _INFUTIL_H
 3532 
 3533 typedef enum {
 3534       TYPE,     /* get type bits (3, including end bit) */
 3535       LENS,     /* get lengths for stored */
 3536       STORED,   /* processing stored block */
 3537       TABLE,    /* get table lengths */
 3538       BTREE,    /* get bit lengths tree for a dynamic block */
 3539       DTREE,    /* get length, distance trees for a dynamic block */
 3540       CODES,    /* processing fixed or dynamic block */
 3541       DRY,      /* output remaining window bytes */
 3542       DONEB,    /* finished last block, done */
 3543       BADB}     /* got a data error--stuck here */
 3544 inflate_block_mode;
 3545 
 3546 /* inflate blocks semi-private state */
 3547 struct inflate_blocks_state {
 3548 
 3549   /* mode */
 3550   inflate_block_mode  mode;     /* current inflate_block mode */
 3551 
 3552   /* mode dependent information */
 3553   union {
 3554     uInt left;          /* if STORED, bytes left to copy */
 3555     struct {
 3556       uInt table;               /* table lengths (14 bits) */
 3557       uInt index;               /* index into blens (or border) */
 3558       uIntf *blens;             /* bit lengths of codes */
 3559       uInt bb;                  /* bit length tree depth */
 3560       inflate_huft *tb;         /* bit length decoding tree */
 3561     } trees;            /* if DTREE, decoding info for trees */
 3562     struct {
 3563       inflate_huft *tl;
 3564       inflate_huft *td;         /* trees to free */
 3565       inflate_codes_statef 
 3566          *codes;
 3567     } decode;           /* if CODES, current state */
 3568   } sub;                /* submode */
 3569   uInt last;            /* true if this block is the last block */
 3570 
 3571   /* mode independent information */
 3572   uInt bitk;            /* bits in bit buffer */
 3573   uLong bitb;           /* bit buffer */
 3574   Bytef *window;        /* sliding window */
 3575   Bytef *end;           /* one byte after sliding window */
 3576   Bytef *read;          /* window read pointer */
 3577   Bytef *write;         /* window write pointer */
 3578   check_func checkfn;   /* check function */
 3579   uLong check;          /* check on output */
 3580 
 3581 };
 3582 
 3583 
 3584 /* defines for inflate input/output */
 3585 /*   update pointers and return */
 3586 #define UPDBITS {s->bitb=b;s->bitk=k;}
 3587 #define UPDIN {z->avail_in=n;z->total_in+=p-z->next_in;z->next_in=p;}
 3588 #define UPDOUT {s->write=q;}
 3589 #define UPDATE {UPDBITS UPDIN UPDOUT}
 3590 #define LEAVE {UPDATE return inflate_flush(s,z,r);}
 3591 /*   get bytes and bits */
 3592 #define LOADIN {p=z->next_in;n=z->avail_in;b=s->bitb;k=s->bitk;}
 3593 #define NEEDBYTE {if(n)r=Z_OK;else LEAVE}
 3594 #define NEXTBYTE (n--,*p++)
 3595 #define NEEDBITS(j) {while(k<(j)){NEEDBYTE;b|=((uLong)NEXTBYTE)<<k;k+=8;}}
 3596 #define DUMPBITS(j) {b>>=(j);k-=(j);}
 3597 /*   output bytes */
 3598 #define WAVAIL (uInt)(q<s->read?s->read-q-1:s->end-q)
 3599 #define LOADOUT {q=s->write;m=(uInt)WAVAIL;}
 3600 #define WWRAP {if(q==s->end&&s->read!=s->window){q=s->window;m=(uInt)WAVAIL;}}
 3601 #define FLUSH {UPDOUT r=inflate_flush(s,z,r); LOADOUT}
 3602 #define NEEDOUT {if(m==0){WWRAP if(m==0){FLUSH WWRAP if(m==0) LEAVE}}r=Z_OK;}
 3603 #define OUTBYTE(a) {*q++=(Byte)(a);m--;}
 3604 /*   load local pointers */
 3605 #define LOAD {LOADIN LOADOUT}
 3606 
 3607 /* masks for lower bits (size given to avoid silly warnings with Visual C++) */
 3608 extern uInt inflate_mask[17];
 3609 
 3610 /* copy as much as possible from the sliding window to the output area */
 3611 extern int inflate_flush OF((
 3612     inflate_blocks_statef *,
 3613     z_streamp ,
 3614     int));
 3615 
 3616 #ifndef NO_DUMMY_DECL
 3617 struct internal_state      {int dummy;}; /* for buggy compilers */
 3618 #endif
 3619 
 3620 #endif
 3621 /* --- infutil.h */
 3622 
 3623 #ifndef NO_DUMMY_DECL
 3624 struct inflate_codes_state {int dummy;}; /* for buggy compilers */
 3625 #endif
 3626 
 3627 /* Table for deflate from PKZIP's appnote.txt. */
 3628 local const uInt border[] = { /* Order of the bit length code lengths */
 3629         16, 17, 18, 0, 8, 7, 9, 6, 10, 5, 11, 4, 12, 3, 13, 2, 14, 1, 15};
 3630 
 3631 /*
 3632    Notes beyond the 1.93a appnote.txt:
 3633 
 3634    1. Distance pointers never point before the beginning of the output
 3635       stream.
 3636    2. Distance pointers can point back across blocks, up to 32k away.
 3637    3. There is an implied maximum of 7 bits for the bit length table and
 3638       15 bits for the actual data.
 3639    4. If only one code exists, then it is encoded using one bit.  (Zero
 3640       would be more efficient, but perhaps a little confusing.)  If two
 3641       codes exist, they are coded using one bit each (0 and 1).
 3642    5. There is no way of sending zero distance codes--a dummy must be
 3643       sent if there are none.  (History: a pre 2.0 version of PKZIP would
 3644       store blocks with no distance codes, but this was discovered to be
 3645       too harsh a criterion.)  Valid only for 1.93a.  2.04c does allow
 3646       zero distance codes, which is sent as one code of zero bits in
 3647       length.
 3648    6. There are up to 286 literal/length codes.  Code 256 represents the
 3649       end-of-block.  Note however that the static length tree defines
 3650       288 codes just to fill out the Huffman codes.  Codes 286 and 287
 3651       cannot be used though, since there is no length base or extra bits
 3652       defined for them.  Similarily, there are up to 30 distance codes.
 3653       However, static trees define 32 codes (all 5 bits) to fill out the
 3654       Huffman codes, but the last two had better not show up in the data.
 3655    7. Unzip can check dynamic Huffman blocks for complete code sets.
 3656       The exception is that a single code would not be complete (see #4).
 3657    8. The five bits following the block type is really the number of
 3658       literal codes sent minus 257.
 3659    9. Length codes 8,16,16 are interpreted as 13 length codes of 8 bits
 3660       (1+6+6).  Therefore, to output three times the length, you output
 3661       three codes (1+1+1), whereas to output four times the same length,
 3662       you only need two codes (1+3).  Hmm.
 3663   10. In the tree reconstruction algorithm, Code = Code + Increment
 3664       only if BitLength(i) is not zero.  (Pretty obvious.)
 3665   11. Correction: 4 Bits: # of Bit Length codes - 4     (4 - 19)
 3666   12. Note: length code 284 can represent 227-258, but length code 285
 3667       really is 258.  The last length deserves its own, short code
 3668       since it gets used a lot in very redundant files.  The length
 3669       258 is special since 258 - 3 (the min match length) is 255.
 3670   13. The literal/length and distance code bit lengths are read as a
 3671       single stream of lengths.  It is possible (and advantageous) for
 3672       a repeat code (16, 17, or 18) to go across the boundary between
 3673       the two sets of lengths.
 3674  */
 3675 
 3676 
 3677 void inflate_blocks_reset(s, z, c)
 3678 inflate_blocks_statef *s;
 3679 z_streamp z;
 3680 uLongf *c;
 3681 {
 3682   if (s->checkfn != Z_NULL)
 3683     *c = s->check;
 3684   if (s->mode == BTREE || s->mode == DTREE)
 3685     ZFREE(z, s->sub.trees.blens);
 3686   if (s->mode == CODES)
 3687   {
 3688     inflate_codes_free(s->sub.decode.codes, z);
 3689     inflate_trees_free(s->sub.decode.td, z);
 3690     inflate_trees_free(s->sub.decode.tl, z);
 3691   }
 3692   s->mode = TYPE;
 3693   s->bitk = 0;
 3694   s->bitb = 0;
 3695   s->read = s->write = s->window;
 3696   if (s->checkfn != Z_NULL)
 3697     z->adler = s->check = (*s->checkfn)(0L, Z_NULL, 0);
 3698   Trace((stderr, "inflate:   blocks reset\n"));
 3699 }
 3700 
 3701 
 3702 inflate_blocks_statef *inflate_blocks_new(z, c, w)
 3703 z_streamp z;
 3704 check_func c;
 3705 uInt w;
 3706 {
 3707   inflate_blocks_statef *s;
 3708 
 3709   if ((s = (inflate_blocks_statef *)ZALLOC
 3710        (z,1,sizeof(struct inflate_blocks_state))) == Z_NULL)
 3711     return s;
 3712   if ((s->window = (Bytef *)ZALLOC(z, 1, w)) == Z_NULL)
 3713   {
 3714     ZFREE(z, s);
 3715     return Z_NULL;
 3716   }
 3717   s->end = s->window + w;
 3718   s->checkfn = c;
 3719   s->mode = TYPE;
 3720   Trace((stderr, "inflate:   blocks allocated\n"));
 3721   inflate_blocks_reset(s, z, &s->check);
 3722   return s;
 3723 }
 3724 
 3725 
 3726 #ifdef DEBUG_ZLIB
 3727   extern uInt inflate_hufts;
 3728 #endif
 3729 int inflate_blocks(s, z, r)
 3730 inflate_blocks_statef *s;
 3731 z_streamp z;
 3732 int r;
 3733 {
 3734   uInt t;               /* temporary storage */
 3735   uLong b;              /* bit buffer */
 3736   uInt k;               /* bits in bit buffer */
 3737   Bytef *p;             /* input data pointer */
 3738   uInt n;               /* bytes available there */
 3739   Bytef *q;             /* output window write pointer */
 3740   uInt m;               /* bytes to end of window or read pointer */
 3741 
 3742   /* copy input/output information to locals (UPDATE macro restores) */
 3743   LOAD
 3744 
 3745   /* process input based on current state */
 3746   while (1) switch (s->mode)
 3747   {
 3748     case TYPE:
 3749       NEEDBITS(3)
 3750       t = (uInt)b & 7;
 3751       s->last = t & 1;
 3752       switch (t >> 1)
 3753       {
 3754         case 0:                         /* stored */
 3755           Trace((stderr, "inflate:     stored block%s\n",
 3756                  s->last ? " (last)" : ""));
 3757           DUMPBITS(3)
 3758           t = k & 7;                    /* go to byte boundary */
 3759           DUMPBITS(t)
 3760           s->mode = LENS;               /* get length of stored block */
 3761           break;
 3762         case 1:                         /* fixed */
 3763           Trace((stderr, "inflate:     fixed codes block%s\n",
 3764                  s->last ? " (last)" : ""));
 3765           {
 3766             uInt bl, bd;
 3767             inflate_huft *tl, *td;
 3768 
 3769             inflate_trees_fixed(&bl, &bd, &tl, &td);
 3770             s->sub.decode.codes = inflate_codes_new(bl, bd, tl, td, z);
 3771             if (s->sub.decode.codes == Z_NULL)
 3772             {
 3773               r = Z_MEM_ERROR;
 3774               LEAVE
 3775             }
 3776             s->sub.decode.tl = Z_NULL;  /* don't try to free these */
 3777             s->sub.decode.td = Z_NULL;
 3778           }
 3779           DUMPBITS(3)
 3780           s->mode = CODES;
 3781           break;
 3782         case 2:                         /* dynamic */
 3783           Trace((stderr, "inflate:     dynamic codes block%s\n",
 3784                  s->last ? " (last)" : ""));
 3785           DUMPBITS(3)
 3786           s->mode = TABLE;
 3787           break;
 3788         case 3:                         /* illegal */
 3789           DUMPBITS(3)
 3790           s->mode = BADB;
 3791           z->msg = (char*)"invalid block type";
 3792           r = Z_DATA_ERROR;
 3793           LEAVE
 3794       }
 3795       break;
 3796     case LENS:
 3797       NEEDBITS(32)
 3798       if ((((~b) >> 16) & 0xffff) != (b & 0xffff))
 3799       {
 3800         s->mode = BADB;
 3801         z->msg = (char*)"invalid stored block lengths";
 3802         r = Z_DATA_ERROR;
 3803         LEAVE
 3804       }
 3805       s->sub.left = (uInt)b & 0xffff;
 3806       b = k = 0;                      /* dump bits */
 3807       Tracev((stderr, "inflate:       stored length %u\n", s->sub.left));
 3808       s->mode = s->sub.left ? STORED : (s->last ? DRY : TYPE);
 3809       break;
 3810     case STORED:
 3811       if (n == 0)
 3812         LEAVE
 3813       NEEDOUT
 3814       t = s->sub.left;
 3815       if (t > n) t = n;
 3816       if (t > m) t = m;
 3817       zmemcpy(q, p, t);
 3818       p += t;  n -= t;
 3819       q += t;  m -= t;
 3820       if ((s->sub.left -= t) != 0)
 3821         break;
 3822       Tracev((stderr, "inflate:       stored end, %lu total out\n",
 3823               z->total_out + (q >= s->read ? q - s->read :
 3824               (s->end - s->read) + (q - s->window))));
 3825       s->mode = s->last ? DRY : TYPE;
 3826       break;
 3827     case TABLE:
 3828       NEEDBITS(14)
 3829       s->sub.trees.table = t = (uInt)b & 0x3fff;
 3830 #ifndef PKZIP_BUG_WORKAROUND
 3831       if ((t & 0x1f) > 29 || ((t >> 5) & 0x1f) > 29)
 3832       {
 3833         s->mode = BADB;
 3834         z->msg = (char*)"too many length or distance symbols";
 3835         r = Z_DATA_ERROR;
 3836         LEAVE
 3837       }
 3838 #endif
 3839       t = 258 + (t & 0x1f) + ((t >> 5) & 0x1f);
 3840       if (t < 19)
 3841         t = 19;
 3842       if ((s->sub.trees.blens = (uIntf*)ZALLOC(z, t, sizeof(uInt))) == Z_NULL)
 3843       {
 3844         r = Z_MEM_ERROR;
 3845         LEAVE
 3846       }
 3847       DUMPBITS(14)
 3848       s->sub.trees.index = 0;
 3849       Tracev((stderr, "inflate:       table sizes ok\n"));
 3850       s->mode = BTREE;
 3851     case BTREE:
 3852       while (s->sub.trees.index < 4 + (s->sub.trees.table >> 10))
 3853       {
 3854         NEEDBITS(3)
 3855         s->sub.trees.blens[border[s->sub.trees.index++]] = (uInt)b & 7;
 3856         DUMPBITS(3)
 3857       }
 3858       while (s->sub.trees.index < 19)
 3859         s->sub.trees.blens[border[s->sub.trees.index++]] = 0;
 3860       s->sub.trees.bb = 7;
 3861       t = inflate_trees_bits(s->sub.trees.blens, &s->sub.trees.bb,
 3862                              &s->sub.trees.tb, z);
 3863       if (t != Z_OK)
 3864       {
 3865         r = t;
 3866         if (r == Z_DATA_ERROR) {
 3867           ZFREE(z, s->sub.trees.blens);
 3868           s->mode = BADB;
 3869         }
 3870         LEAVE
 3871       }
 3872       s->sub.trees.index = 0;
 3873       Tracev((stderr, "inflate:       bits tree ok\n"));
 3874       s->mode = DTREE;
 3875     case DTREE:
 3876       while (t = s->sub.trees.table,
 3877              s->sub.trees.index < 258 + (t & 0x1f) + ((t >> 5) & 0x1f))
 3878       {
 3879         inflate_huft *h;
 3880         uInt i, j, c;
 3881 
 3882         t = s->sub.trees.bb;
 3883         NEEDBITS(t)
 3884         h = s->sub.trees.tb + ((uInt)b & inflate_mask[t]);
 3885         t = h->word.what.Bits;
 3886         c = h->more.Base;
 3887         if (c < 16)
 3888         {
 3889           DUMPBITS(t)
 3890           s->sub.trees.blens[s->sub.trees.index++] = c;
 3891         }
 3892         else /* c == 16..18 */
 3893         {
 3894           i = c == 18 ? 7 : c - 14;
 3895           j = c == 18 ? 11 : 3;
 3896           NEEDBITS(t + i)
 3897           DUMPBITS(t)
 3898           j += (uInt)b & inflate_mask[i];
 3899           DUMPBITS(i)
 3900           i = s->sub.trees.index;
 3901           t = s->sub.trees.table;
 3902           if (i + j > 258 + (t & 0x1f) + ((t >> 5) & 0x1f) ||
 3903               (c == 16 && i < 1))
 3904           {
 3905             inflate_trees_free(s->sub.trees.tb, z);
 3906             ZFREE(z, s->sub.trees.blens);
 3907             s->mode = BADB;
 3908             z->msg = (char*)"invalid bit length repeat";
 3909             r = Z_DATA_ERROR;
 3910             LEAVE
 3911           }
 3912           c = c == 16 ? s->sub.trees.blens[i - 1] : 0;
 3913           do {
 3914             s->sub.trees.blens[i++] = c;
 3915           } while (--j);
 3916           s->sub.trees.index = i;
 3917         }
 3918       }
 3919       inflate_trees_free(s->sub.trees.tb, z);
 3920       s->sub.trees.tb = Z_NULL;
 3921       {
 3922         uInt bl, bd;
 3923         inflate_huft *tl, *td;
 3924         inflate_codes_statef *c;
 3925 
 3926         bl = 9;         /* must be <= 9 for lookahead assumptions */
 3927         bd = 6;         /* must be <= 9 for lookahead assumptions */
 3928         t = s->sub.trees.table;
 3929 #ifdef DEBUG_ZLIB
 3930       inflate_hufts = 0;
 3931 #endif
 3932         t = inflate_trees_dynamic(257 + (t & 0x1f), 1 + ((t >> 5) & 0x1f),
 3933                                   s->sub.trees.blens, &bl, &bd, &tl, &td, z);
 3934         if (t != Z_OK)
 3935         {
 3936           if (t == (uInt)Z_DATA_ERROR) {
 3937             ZFREE(z, s->sub.trees.blens);
 3938             s->mode = BADB;
 3939           }
 3940           r = t;
 3941           LEAVE
 3942         }
 3943         Tracev((stderr, "inflate:       trees ok, %d * %d bytes used\n",
 3944               inflate_hufts, sizeof(inflate_huft)));
 3945         if ((c = inflate_codes_new(bl, bd, tl, td, z)) == Z_NULL)
 3946         {
 3947           inflate_trees_free(td, z);
 3948           inflate_trees_free(tl, z);
 3949           r = Z_MEM_ERROR;
 3950           LEAVE
 3951         }
 3952         /*
 3953          * this ZFREE must occur *BEFORE* we mess with sub.decode, because
 3954          * sub.trees is union'd with sub.decode.
 3955          */
 3956         ZFREE(z, s->sub.trees.blens);
 3957         s->sub.decode.codes = c;
 3958         s->sub.decode.tl = tl;
 3959         s->sub.decode.td = td;
 3960       }
 3961       s->mode = CODES;
 3962     case CODES:
 3963       UPDATE
 3964       if ((r = inflate_codes(s, z, r)) != Z_STREAM_END)
 3965         return inflate_flush(s, z, r);
 3966       r = Z_OK;
 3967       inflate_codes_free(s->sub.decode.codes, z);
 3968       inflate_trees_free(s->sub.decode.td, z);
 3969       inflate_trees_free(s->sub.decode.tl, z);
 3970       LOAD
 3971       Tracev((stderr, "inflate:       codes end, %lu total out\n",
 3972               z->total_out + (q >= s->read ? q - s->read :
 3973               (s->end - s->read) + (q - s->window))));
 3974       if (!s->last)
 3975       {
 3976         s->mode = TYPE;
 3977         break;
 3978       }
 3979       if (k > 7)              /* return unused byte, if any */
 3980       {
 3981         Assert(k < 16, "inflate_codes grabbed too many bytes")
 3982         k -= 8;
 3983         n++;
 3984         p--;                    /* can always return one */
 3985       }
 3986       s->mode = DRY;
 3987     case DRY:
 3988       FLUSH
 3989       if (s->read != s->write)
 3990         LEAVE
 3991       s->mode = DONEB;
 3992     case DONEB:
 3993       r = Z_STREAM_END;
 3994       LEAVE
 3995     case BADB:
 3996       r = Z_DATA_ERROR;
 3997       LEAVE
 3998     default:
 3999       r = Z_STREAM_ERROR;
 4000       LEAVE
 4001   }
 4002 }
 4003 
 4004 
 4005 int inflate_blocks_free(s, z, c)
 4006 inflate_blocks_statef *s;
 4007 z_streamp z;
 4008 uLongf *c;
 4009 {
 4010   inflate_blocks_reset(s, z, c);
 4011   ZFREE(z, s->window);
 4012   ZFREE(z, s);
 4013   Trace((stderr, "inflate:   blocks freed\n"));
 4014   return Z_OK;
 4015 }
 4016 
 4017 
 4018 void inflate_set_dictionary(s, d, n)
 4019 inflate_blocks_statef *s;
 4020 const Bytef *d;
 4021 uInt  n;
 4022 {
 4023   zmemcpy((charf *)s->window, d, n);
 4024   s->read = s->write = s->window + n;
 4025 }
 4026 
 4027 /*
 4028  * This subroutine adds the data at next_in/avail_in to the output history
 4029  * without performing any output.  The output buffer must be "caught up";
 4030  * i.e. no pending output (hence s->read equals s->write), and the state must
 4031  * be BLOCKS (i.e. we should be willing to see the start of a series of
 4032  * BLOCKS).  On exit, the output will also be caught up, and the checksum
 4033  * will have been updated if need be.
 4034  */
 4035 int inflate_addhistory(s, z)
 4036 inflate_blocks_statef *s;
 4037 z_stream *z;
 4038 {
 4039     uLong b;              /* bit buffer */  /* NOT USED HERE */
 4040     uInt k;               /* bits in bit buffer */ /* NOT USED HERE */
 4041     uInt t;               /* temporary storage */
 4042     Bytef *p;             /* input data pointer */
 4043     uInt n;               /* bytes available there */
 4044     Bytef *q;             /* output window write pointer */
 4045     uInt m;               /* bytes to end of window or read pointer */
 4046 
 4047     if (s->read != s->write)
 4048         return Z_STREAM_ERROR;
 4049     if (s->mode != TYPE)
 4050         return Z_DATA_ERROR;
 4051 
 4052     /* we're ready to rock */
 4053     LOAD
 4054     /* while there is input ready, copy to output buffer, moving
 4055      * pointers as needed.
 4056      */
 4057     while (n) {
 4058         t = n;  /* how many to do */
 4059         /* is there room until end of buffer? */
 4060         if (t > m) t = m;
 4061         /* update check information */
 4062         if (s->checkfn != Z_NULL)
 4063             s->check = (*s->checkfn)(s->check, q, t);
 4064         zmemcpy(q, p, t);
 4065         q += t;
 4066         p += t;
 4067         n -= t;
 4068         z->total_out += t;
 4069         s->read = q;    /* drag read pointer forward */
 4070 /*      WWRAP  */       /* expand WWRAP macro by hand to handle s->read */
 4071         if (q == s->end) {
 4072             s->read = q = s->window;
 4073             m = WAVAIL;
 4074         }
 4075     }
 4076     UPDATE
 4077     return Z_OK;
 4078 }
 4079 
 4080 
 4081 /*
 4082  * At the end of a Deflate-compressed PPP packet, we expect to have seen
 4083  * a `stored' block type value but not the (zero) length bytes.
 4084  */
 4085 int inflate_packet_flush(s)
 4086     inflate_blocks_statef *s;
 4087 {
 4088     if (s->mode != LENS)
 4089         return Z_DATA_ERROR;
 4090     s->mode = TYPE;
 4091     return Z_OK;
 4092 }
 4093 /* --- infblock.c */
 4094 
 4095 /* +++ inftrees.c */
 4096 /* inftrees.c -- generate Huffman trees for efficient decoding
 4097  * Copyright (C) 1995-1996 Mark Adler
 4098  * For conditions of distribution and use, see copyright notice in zlib.h 
 4099  */
 4100 
 4101 /* #include "zutil.h" */
 4102 /* #include "inftrees.h" */
 4103 
 4104 char inflate_copyright[] = " inflate 1.0.4 Copyright 1995-1996 Mark Adler ";
 4105 /*
 4106   If you use the zlib library in a product, an acknowledgment is welcome
 4107   in the documentation of your product. If for some reason you cannot
 4108   include such an acknowledgment, I would appreciate that you keep this
 4109   copyright string in the executable of your product.
 4110  */
 4111 
 4112 #ifndef NO_DUMMY_DECL
 4113 struct internal_state  {int dummy;}; /* for buggy compilers */
 4114 #endif
 4115 
 4116 /* simplify the use of the inflate_huft type with some defines */
 4117 #define base more.Base
 4118 #define next more.Next
 4119 #define exop word.what.Exop
 4120 #define bits word.what.Bits
 4121 
 4122 
 4123 local int huft_build OF((
 4124     uIntf *,            /* code lengths in bits */
 4125     uInt,               /* number of codes */
 4126     uInt,               /* number of "simple" codes */
 4127     const uIntf *,      /* list of base values for non-simple codes */
 4128     const uIntf *,      /* list of extra bits for non-simple codes */
 4129     inflate_huft * FAR*,/* result: starting table */
 4130     uIntf *,            /* maximum lookup bits (returns actual) */
 4131     z_streamp ));       /* for zalloc function */
 4132 
 4133 local voidpf falloc OF((
 4134     voidpf,             /* opaque pointer (not used) */
 4135     uInt,               /* number of items */
 4136     uInt));             /* size of item */
 4137 
 4138 /* Tables for deflate from PKZIP's appnote.txt. */
 4139 local const uInt cplens[31] = { /* Copy lengths for literal codes 257..285 */
 4140         3, 4, 5, 6, 7, 8, 9, 10, 11, 13, 15, 17, 19, 23, 27, 31,
 4141         35, 43, 51, 59, 67, 83, 99, 115, 131, 163, 195, 227, 258, 0, 0};
 4142         /* see note #13 above about 258 */
 4143 local const uInt cplext[31] = { /* Extra bits for literal codes 257..285 */
 4144         0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 2, 2, 2, 2,
 4145         3, 3, 3, 3, 4, 4, 4, 4, 5, 5, 5, 5, 0, 112, 112}; /* 112==invalid */
 4146 local const uInt cpdist[30] = { /* Copy offsets for distance codes 0..29 */
 4147         1, 2, 3, 4, 5, 7, 9, 13, 17, 25, 33, 49, 65, 97, 129, 193,
 4148         257, 385, 513, 769, 1025, 1537, 2049, 3073, 4097, 6145,
 4149         8193, 12289, 16385, 24577};
 4150 local const uInt cpdext[30] = { /* Extra bits for distance codes */
 4151         0, 0, 0, 0, 1, 1, 2, 2, 3, 3, 4, 4, 5, 5, 6, 6,
 4152         7, 7, 8, 8, 9, 9, 10, 10, 11, 11,
 4153         12, 12, 13, 13};
 4154 
 4155 /*
 4156    Huffman code decoding is performed using a multi-level table lookup.
 4157    The fastest way to decode is to simply build a lookup table whose
 4158    size is determined by the longest code.  However, the time it takes
 4159    to build this table can also be a factor if the data being decoded
 4160    is not very long.  The most common codes are necessarily the
 4161    shortest codes, so those codes dominate the decoding time, and hence
 4162    the speed.  The idea is you can have a shorter table that decodes the
 4163    shorter, more probable codes, and then point to subsidiary tables for
 4164    the longer codes.  The time it costs to decode the longer codes is
 4165    then traded against the time it takes to make longer tables.
 4166 
 4167    This results of this trade are in the variables lbits and dbits
 4168    below.  lbits is the number of bits the first level table for literal/
 4169    length codes can decode in one step, and dbits is the same thing for
 4170    the distance codes.  Subsequent tables are also less than or equal to
 4171    those sizes.  These values may be adjusted either when all of the
 4172    codes are shorter than that, in which case the longest code length in
 4173    bits is used, or when the shortest code is *longer* than the requested
 4174    table size, in which case the length of the shortest code in bits is
 4175    used.
 4176 
 4177    There are two different values for the two tables, since they code a
 4178    different number of possibilities each.  The literal/length table
 4179    codes 286 possible values, or in a flat code, a little over eight
 4180    bits.  The distance table codes 30 possible values, or a little less
 4181    than five bits, flat.  The optimum values for speed end up being
 4182    about one bit more than those, so lbits is 8+1 and dbits is 5+1.
 4183    The optimum values may differ though from machine to machine, and
 4184    possibly even between compilers.  Your mileage may vary.
 4185  */
 4186 
 4187 
 4188 /* If BMAX needs to be larger than 16, then h and x[] should be uLong. */
 4189 #define BMAX 15         /* maximum bit length of any code */
 4190 #define N_MAX 288       /* maximum number of codes in any set */
 4191 
 4192 #ifdef DEBUG_ZLIB
 4193   uInt inflate_hufts;
 4194 #endif
 4195 
 4196 local int huft_build(b, n, s, d, e, t, m, zs)
 4197 uIntf *b;               /* code lengths in bits (all assumed <= BMAX) */
 4198 uInt n;                 /* number of codes (assumed <= N_MAX) */
 4199 uInt s;                 /* number of simple-valued codes (0..s-1) */
 4200 const uIntf *d;         /* list of base values for non-simple codes */
 4201 const uIntf *e;         /* list of extra bits for non-simple codes */
 4202 inflate_huft * FAR *t;  /* result: starting table */
 4203 uIntf *m;               /* maximum lookup bits, returns actual */
 4204 z_streamp zs;           /* for zalloc function */
 4205 /* Given a list of code lengths and a maximum table size, make a set of
 4206    tables to decode that set of codes.  Return Z_OK on success, Z_BUF_ERROR
 4207    if the given code set is incomplete (the tables are still built in this
 4208    case), Z_DATA_ERROR if the input is invalid (an over-subscribed set of
 4209    lengths), or Z_MEM_ERROR if not enough memory. */
 4210 {
 4211 
 4212   uInt a;                       /* counter for codes of length k */
 4213   uInt c[BMAX+1];               /* bit length count table */
 4214   uInt f;                       /* i repeats in table every f entries */
 4215   int g;                        /* maximum code length */
 4216   int h;                        /* table level */
 4217   register uInt i;              /* counter, current code */
 4218   register uInt j;              /* counter */
 4219   register int k;               /* number of bits in current code */
 4220   int l;                        /* bits per table (returned in m) */
 4221   register uIntf *p;            /* pointer into c[], b[], or v[] */
 4222   inflate_huft *q;              /* points to current table */
 4223   struct inflate_huft_s r;      /* table entry for structure assignment */
 4224   inflate_huft *u[BMAX];        /* table stack */
 4225   uInt v[N_MAX];                /* values in order of bit length */
 4226   register int w;               /* bits before this table == (l * h) */
 4227   uInt x[BMAX+1];               /* bit offsets, then code stack */
 4228   uIntf *xp;                    /* pointer into x */
 4229   int y;                        /* number of dummy codes added */
 4230   uInt z;                       /* number of entries in current table */
 4231 
 4232 
 4233   /* Generate counts for each bit length */
 4234   p = c;
 4235 #define C0 *p++ = 0;
 4236 #define C2 C0 C0 C0 C0
 4237 #define C4 C2 C2 C2 C2
 4238   C4                            /* clear c[]--assume BMAX+1 is 16 */
 4239   p = b;  i = n;
 4240   do {
 4241     c[*p++]++;                  /* assume all entries <= BMAX */
 4242   } while (--i);
 4243   if (c[0] == n)                /* null input--all zero length codes */
 4244   {
 4245     *t = (inflate_huft *)Z_NULL;
 4246     *m = 0;
 4247     return Z_OK;
 4248   }
 4249 
 4250 
 4251   /* Find minimum and maximum length, bound *m by those */
 4252   l = *m;
 4253   for (j = 1; j <= BMAX; j++)
 4254     if (c[j])
 4255       break;
 4256   k = j;                        /* minimum code length */
 4257   if ((uInt)l < j)
 4258     l = j;
 4259   for (i = BMAX; i; i--)
 4260     if (c[i])
 4261       break;
 4262   g = i;                        /* maximum code length */
 4263   if ((uInt)l > i)
 4264     l = i;
 4265   *m = l;
 4266 
 4267 
 4268   /* Adjust last length count to fill out codes, if needed */
 4269   for (y = 1 << j; j < i; j++, y <<= 1)
 4270     if ((y -= c[j]) < 0)
 4271       return Z_DATA_ERROR;
 4272   if ((y -= c[i]) < 0)
 4273     return Z_DATA_ERROR;
 4274   c[i] += y;
 4275 
 4276 
 4277   /* Generate starting offsets into the value table for each length */
 4278   x[1] = j = 0;
 4279   p = c + 1;  xp = x + 2;
 4280   while (--i) {                 /* note that i == g from above */
 4281     *xp++ = (j += *p++);
 4282   }
 4283 
 4284 
 4285   /* Make a table of values in order of bit lengths */
 4286   p = b;  i = 0;
 4287   do {
 4288     if ((j = *p++) != 0)
 4289       v[x[j]++] = i;
 4290   } while (++i < n);
 4291   n = x[g];                   /* set n to length of v */
 4292 
 4293 
 4294   /* Generate the Huffman codes and for each, make the table entries */
 4295   x[0] = i = 0;                 /* first Huffman code is zero */
 4296   p = v;                        /* grab values in bit order */
 4297   h = -1;                       /* no tables yet--level -1 */
 4298   w = -l;                       /* bits decoded == (l * h) */
 4299   u[0] = (inflate_huft *)Z_NULL;        /* just to keep compilers happy */
 4300   q = (inflate_huft *)Z_NULL;   /* ditto */
 4301   z = 0;                        /* ditto */
 4302 
 4303   /* go through the bit lengths (k already is bits in shortest code) */
 4304   for (; k <= g; k++)
 4305   {
 4306     a = c[k];
 4307     while (a--)
 4308     {
 4309       /* here i is the Huffman code of length k bits for value *p */
 4310       /* make tables up to required level */
 4311       while (k > w + l)
 4312       {
 4313         h++;
 4314         w += l;                 /* previous table always l bits */
 4315 
 4316         /* compute minimum size table less than or equal to l bits */
 4317         z = g - w;
 4318         z = z > (uInt)l ? l : z;        /* table size upper limit */
 4319         if ((f = 1 << (j = k - w)) > a + 1)     /* try a k-w bit table */
 4320         {                       /* too few codes for k-w bit table */
 4321           f -= a + 1;           /* deduct codes from patterns left */
 4322           xp = c + k;
 4323           if (j < z)
 4324             while (++j < z)     /* try smaller tables up to z bits */
 4325             {
 4326               if ((f <<= 1) <= *++xp)
 4327                 break;          /* enough codes to use up j bits */
 4328               f -= *xp;         /* else deduct codes from patterns */
 4329             }
 4330         }
 4331         z = 1 << j;             /* table entries for j-bit table */
 4332 
 4333         /* allocate and link in new table */
 4334         if ((q = (inflate_huft *)ZALLOC
 4335              (zs,z + 1,sizeof(inflate_huft))) == Z_NULL)
 4336         {
 4337           if (h)
 4338             inflate_trees_free(u[0], zs);
 4339           return Z_MEM_ERROR;   /* not enough memory */
 4340         }
 4341 #ifdef DEBUG_ZLIB
 4342         inflate_hufts += z + 1;
 4343 #endif
 4344         *t = q + 1;             /* link to list for huft_free() */
 4345         *(t = &(q->next)) = Z_NULL;
 4346         u[h] = ++q;             /* table starts after link */
 4347 
 4348         /* connect to last table, if there is one */
 4349         if (h)
 4350         {
 4351           x[h] = i;             /* save pattern for backing up */
 4352           r.bits = (Byte)l;     /* bits to dump before this table */
 4353           r.exop = (Byte)j;     /* bits in this table */
 4354           r.next = q;           /* pointer to this table */
 4355           j = i >> (w - l);     /* (get around Turbo C bug) */
 4356           u[h-1][j] = r;        /* connect to last table */
 4357         }
 4358       }
 4359 
 4360       /* set up table entry in r */
 4361       r.bits = (Byte)(k - w);
 4362       if (p >= v + n)
 4363         r.exop = 128 + 64;      /* out of values--invalid code */
 4364       else if (*p < s)
 4365       {
 4366         r.exop = (Byte)(*p < 256 ? 0 : 32 + 64);     /* 256 is end-of-block */
 4367         r.base = *p++;          /* simple code is just the value */
 4368       }
 4369       else
 4370       {
 4371         r.exop = (Byte)(e[*p - s] + 16 + 64);/* non-simple--look up in lists */
 4372         r.base = d[*p++ - s];
 4373       }
 4374 
 4375       /* fill code-like entries with r */
 4376       f = 1 << (k - w);
 4377       for (j = i >> w; j < z; j += f)
 4378         q[j] = r;
 4379 
 4380       /* backwards increment the k-bit code i */
 4381       for (j = 1 << (k - 1); i & j; j >>= 1)
 4382         i ^= j;
 4383       i ^= j;
 4384 
 4385       /* backup over finished tables */
 4386       while ((i & ((1 << w) - 1)) != x[h])
 4387       {
 4388         h--;                    /* don't need to update q */
 4389         w -= l;
 4390       }
 4391     }
 4392   }
 4393 
 4394 
 4395   /* Return Z_BUF_ERROR if we were given an incomplete table */
 4396   return y != 0 && g != 1 ? Z_BUF_ERROR : Z_OK;
 4397 }
 4398 
 4399 
 4400 int inflate_trees_bits(c, bb, tb, z)
 4401 uIntf *c;               /* 19 code lengths */
 4402 uIntf *bb;              /* bits tree desired/actual depth */
 4403 inflate_huft * FAR *tb; /* bits tree result */
 4404 z_streamp z;            /* for zfree function */
 4405 {
 4406   int r;
 4407 
 4408   r = huft_build(c, 19, 19, (uIntf*)Z_NULL, (uIntf*)Z_NULL, tb, bb, z);
 4409   if (r == Z_DATA_ERROR)
 4410     z->msg = (char*)"oversubscribed dynamic bit lengths tree";
 4411   else if (r == Z_BUF_ERROR || *bb == 0)
 4412   {
 4413     inflate_trees_free(*tb, z);
 4414     z->msg = (char*)"incomplete dynamic bit lengths tree";
 4415     r = Z_DATA_ERROR;
 4416   }
 4417   return r;
 4418 }
 4419 
 4420 
 4421 int inflate_trees_dynamic(nl, nd, c, bl, bd, tl, td, z)
 4422 uInt nl;                /* number of literal/length codes */
 4423 uInt nd;                /* number of distance codes */
 4424 uIntf *c;               /* that many (total) code lengths */
 4425 uIntf *bl;              /* literal desired/actual bit depth */
 4426 uIntf *bd;              /* distance desired/actual bit depth */
 4427 inflate_huft * FAR *tl; /* literal/length tree result */
 4428 inflate_huft * FAR *td; /* distance tree result */
 4429 z_streamp z;            /* for zfree function */
 4430 {
 4431   int r;
 4432 
 4433   /* build literal/length tree */
 4434   r = huft_build(c, nl, 257, cplens, cplext, tl, bl, z);
 4435   if (r != Z_OK || *bl == 0)
 4436   {
 4437     if (r == Z_DATA_ERROR)
 4438       z->msg = (char*)"oversubscribed literal/length tree";
 4439     else if (r != Z_MEM_ERROR)
 4440     {
 4441       inflate_trees_free(*tl, z);
 4442       z->msg = (char*)"incomplete literal/length tree";
 4443       r = Z_DATA_ERROR;
 4444     }
 4445     return r;
 4446   }
 4447 
 4448   /* build distance tree */
 4449   r = huft_build(c + nl, nd, 0, cpdist, cpdext, td, bd, z);
 4450   if (r != Z_OK || (*bd == 0 && nl > 257))
 4451   {
 4452     if (r == Z_DATA_ERROR)
 4453       z->msg = (char*)"oversubscribed distance tree";
 4454     else if (r == Z_BUF_ERROR) {
 4455 #ifdef PKZIP_BUG_WORKAROUND
 4456       r = Z_OK;
 4457     }
 4458 #else
 4459       inflate_trees_free(*td, z);
 4460       z->msg = (char*)"incomplete distance tree";
 4461       r = Z_DATA_ERROR;
 4462     }
 4463     else if (r != Z_MEM_ERROR)
 4464     {
 4465       z->msg = (char*)"empty distance tree with lengths";
 4466       r = Z_DATA_ERROR;
 4467     }
 4468     inflate_trees_free(*tl, z);
 4469     return r;
 4470 #endif
 4471   }
 4472 
 4473   /* done */
 4474   return Z_OK;
 4475 }
 4476 
 4477 
 4478 /* build fixed tables only once--keep them here */
 4479 local int fixed_built = 0;
 4480 #define FIXEDH 530      /* number of hufts used by fixed tables */
 4481 local inflate_huft fixed_mem[FIXEDH];
 4482 local uInt fixed_bl;
 4483 local uInt fixed_bd;
 4484 local inflate_huft *fixed_tl;
 4485 local inflate_huft *fixed_td;
 4486 
 4487 
 4488 local voidpf falloc(q, n, s)
 4489 voidpf q;       /* opaque pointer */
 4490 uInt n;         /* number of items */
 4491 uInt s;         /* size of item */
 4492 {
 4493   Assert(s == sizeof(inflate_huft) && n <= *(intf *)q,
 4494          "inflate_trees falloc overflow");
 4495   *(intf *)q -= n+s-s; /* s-s to avoid warning */
 4496   return (voidpf)(fixed_mem + *(intf *)q);
 4497 }
 4498 
 4499 
 4500 int inflate_trees_fixed(bl, bd, tl, td)
 4501 uIntf *bl;               /* literal desired/actual bit depth */
 4502 uIntf *bd;               /* distance desired/actual bit depth */
 4503 inflate_huft * FAR *tl;  /* literal/length tree result */
 4504 inflate_huft * FAR *td;  /* distance tree result */
 4505 {
 4506   /* build fixed tables if not already (multiple overlapped executions ok) */
 4507   if (!fixed_built)
 4508   {
 4509     int k;              /* temporary variable */
 4510     unsigned c[288];    /* length list for huft_build */
 4511     z_stream z;         /* for falloc function */
 4512     int f = FIXEDH;     /* number of hufts left in fixed_mem */
 4513 
 4514     /* set up fake z_stream for memory routines */
 4515     z.zalloc = falloc;
 4516     z.zfree = Z_NULL;
 4517     z.opaque = (voidpf)&f;
 4518 
 4519     /* literal table */
 4520     for (k = 0; k < 144; k++)
 4521       c[k] = 8;
 4522     for (; k < 256; k++)
 4523       c[k] = 9;
 4524     for (; k < 280; k++)
 4525       c[k] = 7;
 4526     for (; k < 288; k++)
 4527       c[k] = 8;
 4528     fixed_bl = 7;
 4529     huft_build(c, 288, 257, cplens, cplext, &fixed_tl, &fixed_bl, &z);
 4530 
 4531     /* distance table */
 4532     for (k = 0; k < 30; k++)
 4533       c[k] = 5;
 4534     fixed_bd = 5;
 4535     huft_build(c, 30, 0, cpdist, cpdext, &fixed_td, &fixed_bd, &z);
 4536 
 4537     /* done */
 4538     Assert(f == 0, "invalid build of fixed tables");
 4539     fixed_built = 1;
 4540   }
 4541   *bl = fixed_bl;
 4542   *bd = fixed_bd;
 4543   *tl = fixed_tl;
 4544   *td = fixed_td;
 4545   return Z_OK;
 4546 }
 4547 
 4548 
 4549 int inflate_trees_free(t, z)
 4550 inflate_huft *t;        /* table to free */
 4551 z_streamp z;            /* for zfree function */
 4552 /* Free the malloc'ed tables built by huft_build(), which makes a linked
 4553    list of the tables it made, with the links in a dummy first entry of
 4554    each table. */
 4555 {
 4556   register inflate_huft *p, *q, *r;
 4557 
 4558   /* Reverse linked list */
 4559   p = Z_NULL;
 4560   q = t;
 4561   while (q != Z_NULL)
 4562   {
 4563     r = (q - 1)->next;
 4564     (q - 1)->next = p;
 4565     p = q;
 4566     q = r;
 4567   }
 4568   /* Go through linked list, freeing from the malloced (t[-1]) address. */
 4569   while (p != Z_NULL)
 4570   {
 4571     q = (--p)->next;
 4572     ZFREE(z,p);
 4573     p = q;
 4574   } 
 4575   return Z_OK;
 4576 }
 4577 /* --- inftrees.c */
 4578 
 4579 /* +++ infcodes.c */
 4580 /* infcodes.c -- process literals and length/distance pairs
 4581  * Copyright (C) 1995-1996 Mark Adler
 4582  * For conditions of distribution and use, see copyright notice in zlib.h 
 4583  */
 4584 
 4585 /* #include "zutil.h" */
 4586 /* #include "inftrees.h" */
 4587 /* #include "infblock.h" */
 4588 /* #include "infcodes.h" */
 4589 /* #include "infutil.h" */
 4590 
 4591 /* +++ inffast.h */
 4592 /* inffast.h -- header to use inffast.c
 4593  * Copyright (C) 1995-1996 Mark Adler
 4594  * For conditions of distribution and use, see copyright notice in zlib.h 
 4595  */
 4596 
 4597 /* WARNING: this file should *not* be used by applications. It is
 4598    part of the implementation of the compression library and is
 4599    subject to change. Applications should only use zlib.h.
 4600  */
 4601 
 4602 extern int inflate_fast OF((
 4603     uInt,
 4604     uInt,
 4605     inflate_huft *,
 4606     inflate_huft *,
 4607     inflate_blocks_statef *,
 4608     z_streamp ));
 4609 /* --- inffast.h */
 4610 
 4611 /* simplify the use of the inflate_huft type with some defines */
 4612 #define base more.Base
 4613 #define next more.Next
 4614 #define exop word.what.Exop
 4615 #define bits word.what.Bits
 4616 
 4617 /* inflate codes private state */
 4618 struct inflate_codes_state {
 4619 
 4620   /* mode */
 4621   enum {        /* waiting for "i:"=input, "o:"=output, "x:"=nothing */
 4622       START,    /* x: set up for LEN */
 4623       LEN,      /* i: get length/literal/eob next */
 4624       LENEXT,   /* i: getting length extra (have base) */
 4625       DIST,     /* i: get distance next */
 4626       DISTEXT,  /* i: getting distance extra */
 4627       COPY,     /* o: copying bytes in window, waiting for space */
 4628       LIT,      /* o: got literal, waiting for output space */
 4629       WASH,     /* o: got eob, possibly still output waiting */
 4630       END,      /* x: got eob and all data flushed */
 4631       BADCODE}  /* x: got error */
 4632     mode;               /* current inflate_codes mode */
 4633 
 4634   /* mode dependent information */
 4635   uInt len;
 4636   union {
 4637     struct {
 4638       inflate_huft *tree;       /* pointer into tree */
 4639       uInt need;                /* bits needed */
 4640     } code;             /* if LEN or DIST, where in tree */
 4641     uInt lit;           /* if LIT, literal */
 4642     struct {
 4643       uInt get;                 /* bits to get for extra */
 4644       uInt dist;                /* distance back to copy from */
 4645     } copy;             /* if EXT or COPY, where and how much */
 4646   } sub;                /* submode */
 4647 
 4648   /* mode independent information */
 4649   Byte lbits;           /* ltree bits decoded per branch */
 4650   Byte dbits;           /* dtree bits decoder per branch */
 4651   inflate_huft *ltree;          /* literal/length/eob tree */
 4652   inflate_huft *dtree;          /* distance tree */
 4653 
 4654 };
 4655 
 4656 
 4657 inflate_codes_statef *inflate_codes_new(bl, bd, tl, td, z)
 4658 uInt bl, bd;
 4659 inflate_huft *tl;
 4660 inflate_huft *td; /* need separate declaration for Borland C++ */
 4661 z_streamp z;
 4662 {
 4663   inflate_codes_statef *c;
 4664 
 4665   if ((c = (inflate_codes_statef *)
 4666        ZALLOC(z,1,sizeof(struct inflate_codes_state))) != Z_NULL)
 4667   {
 4668     c->mode = START;
 4669     c->lbits = (Byte)bl;
 4670     c->dbits = (Byte)bd;
 4671     c->ltree = tl;
 4672     c->dtree = td;
 4673     Tracev((stderr, "inflate:       codes new\n"));
 4674   }
 4675   return c;
 4676 }
 4677 
 4678 
 4679 int inflate_codes(s, z, r)
 4680 inflate_blocks_statef *s;
 4681 z_streamp z;
 4682 int r;
 4683 {
 4684   uInt j;               /* temporary storage */
 4685   inflate_huft *t;      /* temporary pointer */
 4686   uInt e;               /* extra bits or operation */
 4687   uLong b;              /* bit buffer */
 4688   uInt k;               /* bits in bit buffer */
 4689   Bytef *p;             /* input data pointer */
 4690   uInt n;               /* bytes available there */
 4691   Bytef *q;             /* output window write pointer */
 4692   uInt m;               /* bytes to end of window or read pointer */
 4693   Bytef *f;             /* pointer to copy strings from */
 4694   inflate_codes_statef *c = s->sub.decode.codes;  /* codes state */
 4695 
 4696   /* copy input/output information to locals (UPDATE macro restores) */
 4697   LOAD
 4698 
 4699   /* process input and output based on current state */
 4700   while (1) switch (c->mode)
 4701   {             /* waiting for "i:"=input, "o:"=output, "x:"=nothing */
 4702     case START:         /* x: set up for LEN */
 4703 #ifndef SLOW
 4704       if (m >= 258 && n >= 10)
 4705       {
 4706         UPDATE
 4707         r = inflate_fast(c->lbits, c->dbits, c->ltree, c->dtree, s, z);
 4708         LOAD
 4709         if (r != Z_OK)
 4710         {
 4711           c->mode = r == Z_STREAM_END ? WASH : BADCODE;
 4712           break;
 4713         }
 4714       }
 4715 #endif /* !SLOW */
 4716       c->sub.code.need = c->lbits;
 4717       c->sub.code.tree = c->ltree;
 4718       c->mode = LEN;
 4719     case LEN:           /* i: get length/literal/eob next */
 4720       j = c->sub.code.need;
 4721       NEEDBITS(j)
 4722       t = c->sub.code.tree + ((uInt)b & inflate_mask[j]);
 4723       DUMPBITS(t->bits)
 4724       e = (uInt)(t->exop);
 4725       if (e == 0)               /* literal */
 4726       {
 4727         c->sub.lit = t->base;
 4728         Tracevv((stderr, t->base >= 0x20 && t->base < 0x7f ?
 4729                  "inflate:         literal '%c'\n" :
 4730                  "inflate:         literal 0x%02x\n", t->base));
 4731         c->mode = LIT;
 4732         break;
 4733       }
 4734       if (e & 16)               /* length */
 4735       {
 4736         c->sub.copy.get = e & 15;
 4737         c->len = t->base;
 4738         c->mode = LENEXT;
 4739         break;
 4740       }
 4741       if ((e & 64) == 0)        /* next table */
 4742       {
 4743         c->sub.code.need = e;
 4744         c->sub.code.tree = t->next;
 4745         break;
 4746       }
 4747       if (e & 32)               /* end of block */
 4748       {
 4749         Tracevv((stderr, "inflate:         end of block\n"));
 4750         c->mode = WASH;
 4751         break;
 4752       }
 4753       c->mode = BADCODE;        /* invalid code */
 4754       z->msg = (char*)"invalid literal/length code";
 4755       r = Z_DATA_ERROR;
 4756       LEAVE
 4757     case LENEXT:        /* i: getting length extra (have base) */
 4758       j = c->sub.copy.get;
 4759       NEEDBITS(j)
 4760       c->len += (uInt)b & inflate_mask[j];
 4761       DUMPBITS(j)
 4762       c->sub.code.need = c->dbits;
 4763       c->sub.code.tree = c->dtree;
 4764       Tracevv((stderr, "inflate:         length %u\n", c->len));
 4765       c->mode = DIST;
 4766     case DIST:          /* i: get distance next */
 4767       j = c->sub.code.need;
 4768       NEEDBITS(j)
 4769       t = c->sub.code.tree + ((uInt)b & inflate_mask[j]);
 4770       DUMPBITS(t->bits)
 4771       e = (uInt)(t->exop);
 4772       if (e & 16)               /* distance */
 4773       {
 4774         c->sub.copy.get = e & 15;
 4775         c->sub.copy.dist = t->base;
 4776         c->mode = DISTEXT;
 4777         break;
 4778       }
 4779       if ((e & 64) == 0)        /* next table */
 4780       {
 4781         c->sub.code.need = e;
 4782         c->sub.code.tree = t->next;
 4783         break;
 4784       }
 4785       c->mode = BADCODE;        /* invalid code */
 4786       z->msg = (char*)"invalid distance code";
 4787       r = Z_DATA_ERROR;
 4788       LEAVE
 4789     case DISTEXT:       /* i: getting distance extra */
 4790       j = c->sub.copy.get;
 4791       NEEDBITS(j)
 4792       c->sub.copy.dist += (uInt)b & inflate_mask[j];
 4793       DUMPBITS(j)
 4794       Tracevv((stderr, "inflate:         distance %u\n", c->sub.copy.dist));
 4795       c->mode = COPY;
 4796     case COPY:          /* o: copying bytes in window, waiting for space */
 4797 #ifndef __TURBOC__ /* Turbo C bug for following expression */
 4798       f = (uInt)(q - s->window) < c->sub.copy.dist ?
 4799           s->end - (c->sub.copy.dist - (q - s->window)) :
 4800           q - c->sub.copy.dist;
 4801 #else
 4802       f = q - c->sub.copy.dist;
 4803       if ((uInt)(q - s->window) < c->sub.copy.dist)
 4804         f = s->end - (c->sub.copy.dist - (uInt)(q - s->window));
 4805 #endif
 4806       while (c->len)
 4807       {
 4808         NEEDOUT
 4809         OUTBYTE(*f++)
 4810         if (f == s->end)
 4811           f = s->window;
 4812         c->len--;
 4813       }
 4814       c->mode = START;
 4815       break;
 4816     case LIT:           /* o: got literal, waiting for output space */
 4817       NEEDOUT
 4818       OUTBYTE(c->sub.lit)
 4819       c->mode = START;
 4820       break;
 4821     case WASH:          /* o: got eob, possibly more output */
 4822       FLUSH
 4823       if (s->read != s->write)
 4824         LEAVE
 4825       c->mode = END;
 4826     case END:
 4827       r = Z_STREAM_END;
 4828       LEAVE
 4829     case BADCODE:       /* x: got error */
 4830       r = Z_DATA_ERROR;
 4831       LEAVE
 4832     default:
 4833       r = Z_STREAM_ERROR;
 4834       LEAVE
 4835   }
 4836 }
 4837 
 4838 
 4839 void inflate_codes_free(c, z)
 4840 inflate_codes_statef *c;
 4841 z_streamp z;
 4842 {
 4843   ZFREE(z, c);
 4844   Tracev((stderr, "inflate:       codes free\n"));
 4845 }
 4846 /* --- infcodes.c */
 4847 
 4848 /* +++ infutil.c */
 4849 /* inflate_util.c -- data and routines common to blocks and codes
 4850  * Copyright (C) 1995-1996 Mark Adler
 4851  * For conditions of distribution and use, see copyright notice in zlib.h 
 4852  */
 4853 
 4854 /* #include "zutil.h" */
 4855 /* #include "infblock.h" */
 4856 /* #include "inftrees.h" */
 4857 /* #include "infcodes.h" */
 4858 /* #include "infutil.h" */
 4859 
 4860 #ifndef NO_DUMMY_DECL
 4861 struct inflate_codes_state {int dummy;}; /* for buggy compilers */
 4862 #endif
 4863 
 4864 /* And'ing with mask[n] masks the lower n bits */
 4865 uInt inflate_mask[17] = {
 4866     0x0000,
 4867     0x0001, 0x0003, 0x0007, 0x000f, 0x001f, 0x003f, 0x007f, 0x00ff,
 4868     0x01ff, 0x03ff, 0x07ff, 0x0fff, 0x1fff, 0x3fff, 0x7fff, 0xffff
 4869 };
 4870 
 4871 
 4872 /* copy as much as possible from the sliding window to the output area */
 4873 int inflate_flush(s, z, r)
 4874 inflate_blocks_statef *s;
 4875 z_streamp z;
 4876 int r;
 4877 {
 4878   uInt n;
 4879   Bytef *p;
 4880   Bytef *q;
 4881 
 4882   /* local copies of source and destination pointers */
 4883   p = z->next_out;
 4884   q = s->read;
 4885 
 4886   /* compute number of bytes to copy as far as end of window */
 4887   n = (uInt)((q <= s->write ? s->write : s->end) - q);
 4888   if (n > z->avail_out) n = z->avail_out;
 4889   if (n && r == Z_BUF_ERROR) r = Z_OK;
 4890 
 4891   /* update counters */
 4892   z->avail_out -= n;
 4893   z->total_out += n;
 4894 
 4895   /* update check information */
 4896   if (s->checkfn != Z_NULL)
 4897     z->adler = s->check = (*s->checkfn)(s->check, q, n);
 4898 
 4899   /* copy as far as end of window */
 4900   if (p != Z_NULL) {
 4901     zmemcpy(p, q, n);
 4902     p += n;
 4903   }
 4904   q += n;
 4905 
 4906   /* see if more to copy at beginning of window */
 4907   if (q == s->end)
 4908   {
 4909     /* wrap pointers */
 4910     q = s->window;
 4911     if (s->write == s->end)
 4912       s->write = s->window;
 4913 
 4914     /* compute bytes to copy */
 4915     n = (uInt)(s->write - q);
 4916     if (n > z->avail_out) n = z->avail_out;
 4917     if (n && r == Z_BUF_ERROR) r = Z_OK;
 4918 
 4919     /* update counters */
 4920     z->avail_out -= n;
 4921     z->total_out += n;
 4922 
 4923     /* update check information */
 4924     if (s->checkfn != Z_NULL)
 4925       z->adler = s->check = (*s->checkfn)(s->check, q, n);
 4926 
 4927     /* copy */
 4928     if (p != Z_NULL) {
 4929       zmemcpy(p, q, n);
 4930       p += n;
 4931     }
 4932     q += n;
 4933   }
 4934 
 4935   /* update pointers */
 4936   z->next_out = p;
 4937   s->read = q;
 4938 
 4939   /* done */
 4940   return r;
 4941 }
 4942 /* --- infutil.c */
 4943 
 4944 /* +++ inffast.c */
 4945 /* inffast.c -- process literals and length/distance pairs fast
 4946  * Copyright (C) 1995-1996 Mark Adler
 4947  * For conditions of distribution and use, see copyright notice in zlib.h 
 4948  */
 4949 
 4950 /* #include "zutil.h" */
 4951 /* #include "inftrees.h" */
 4952 /* #include "infblock.h" */
 4953 /* #include "infcodes.h" */
 4954 /* #include "infutil.h" */
 4955 /* #include "inffast.h" */
 4956 
 4957 #ifndef NO_DUMMY_DECL
 4958 struct inflate_codes_state {int dummy;}; /* for buggy compilers */
 4959 #endif
 4960 
 4961 /* simplify the use of the inflate_huft type with some defines */
 4962 #define base more.Base
 4963 #define next more.Next
 4964 #define exop word.what.Exop
 4965 #define bits word.what.Bits
 4966 
 4967 /* macros for bit input with no checking and for returning unused bytes */
 4968 #define GRABBITS(j) {while(k<(j)){b|=((uLong)NEXTBYTE)<<k;k+=8;}}
 4969 #define UNGRAB {n+=(c=k>>3);p-=c;k&=7;}
 4970 
 4971 /* Called with number of bytes left to write in window at least 258
 4972    (the maximum string length) and number of input bytes available
 4973    at least ten.  The ten bytes are six bytes for the longest length/
 4974    distance pair plus four bytes for overloading the bit buffer. */
 4975 
 4976 int inflate_fast(bl, bd, tl, td, s, z)
 4977 uInt bl, bd;
 4978 inflate_huft *tl;
 4979 inflate_huft *td; /* need separate declaration for Borland C++ */
 4980 inflate_blocks_statef *s;
 4981 z_streamp z;
 4982 {
 4983   inflate_huft *t;      /* temporary pointer */
 4984   uInt e;               /* extra bits or operation */
 4985   uLong b;              /* bit buffer */
 4986   uInt k;               /* bits in bit buffer */
 4987   Bytef *p;             /* input data pointer */
 4988   uInt n;               /* bytes available there */
 4989   Bytef *q;             /* output window write pointer */
 4990   uInt m;               /* bytes to end of window or read pointer */
 4991   uInt ml;              /* mask for literal/length tree */
 4992   uInt md;              /* mask for distance tree */
 4993   uInt c;               /* bytes to copy */
 4994   uInt d;               /* distance back to copy from */
 4995   Bytef *r;             /* copy source pointer */
 4996 
 4997   /* load input, output, bit values */
 4998   LOAD
 4999 
 5000   /* initialize masks */
 5001   ml = inflate_mask[bl];
 5002   md = inflate_mask[bd];
 5003 
 5004   /* do until not enough input or output space for fast loop */
 5005   do {                          /* assume called with m >= 258 && n >= 10 */
 5006     /* get literal/length code */
 5007     GRABBITS(20)                /* max bits for literal/length code */
 5008     if ((e = (t = tl + ((uInt)b & ml))->exop) == 0)
 5009     {
 5010       DUMPBITS(t->bits)
 5011       Tracevv((stderr, t->base >= 0x20 && t->base < 0x7f ?
 5012                 "inflate:         * literal '%c'\n" :
 5013                 "inflate:         * literal 0x%02x\n", t->base));
 5014       *q++ = (Byte)t->base;
 5015       m--;
 5016       continue;
 5017     }
 5018     do {
 5019       DUMPBITS(t->bits)
 5020       if (e & 16)
 5021       {
 5022         /* get extra bits for length */
 5023         e &= 15;
 5024         c = t->base + ((uInt)b & inflate_mask[e]);
 5025         DUMPBITS(e)
 5026         Tracevv((stderr, "inflate:         * length %u\n", c));
 5027 
 5028         /* decode distance base of block to copy */
 5029         GRABBITS(15);           /* max bits for distance code */
 5030         e = (t = td + ((uInt)b & md))->exop;
 5031         do {
 5032           DUMPBITS(t->bits)
 5033           if (e & 16)
 5034           {
 5035             /* get extra bits to add to distance base */
 5036             e &= 15;
 5037             GRABBITS(e)         /* get extra bits (up to 13) */
 5038             d = t->base + ((uInt)b & inflate_mask[e]);
 5039             DUMPBITS(e)
 5040             Tracevv((stderr, "inflate:         * distance %u\n", d));
 5041 
 5042             /* do the copy */
 5043             m -= c;
 5044             if ((uInt)(q - s->window) >= d)     /* offset before dest */
 5045             {                                   /*  just copy */
 5046               r = q - d;
 5047               *q++ = *r++;  c--;        /* minimum count is three, */
 5048               *q++ = *r++;  c--;        /*  so unroll loop a little */
 5049             }
 5050             else                        /* else offset after destination */
 5051             {
 5052               e = d - (uInt)(q - s->window); /* bytes from offset to end */
 5053               r = s->end - e;           /* pointer to offset */
 5054               if (c > e)                /* if source crosses, */
 5055               {
 5056                 c -= e;                 /* copy to end of window */
 5057                 do {
 5058                   *q++ = *r++;
 5059                 } while (--e);
 5060                 r = s->window;          /* copy rest from start of window */
 5061               }
 5062             }
 5063             do {                        /* copy all or what's left */
 5064               *q++ = *r++;
 5065             } while (--c);
 5066             break;
 5067           }
 5068           else if ((e & 64) == 0)
 5069             e = (t = t->next + ((uInt)b & inflate_mask[e]))->exop;
 5070           else
 5071           {
 5072             z->msg = (char*)"invalid distance code";
 5073             UNGRAB
 5074             UPDATE
 5075             return Z_DATA_ERROR;
 5076           }
 5077         } while (1);
 5078         break;
 5079       }
 5080       if ((e & 64) == 0)
 5081       {
 5082         if ((e = (t = t->next + ((uInt)b & inflate_mask[e]))->exop) == 0)
 5083         {
 5084           DUMPBITS(t->bits)
 5085           Tracevv((stderr, t->base >= 0x20 && t->base < 0x7f ?
 5086                     "inflate:         * literal '%c'\n" :
 5087                     "inflate:         * literal 0x%02x\n", t->base));
 5088           *q++ = (Byte)t->base;
 5089           m--;
 5090           break;
 5091         }
 5092       }
 5093       else if (e & 32)
 5094       {
 5095         Tracevv((stderr, "inflate:         * end of block\n"));
 5096         UNGRAB
 5097         UPDATE
 5098         return Z_STREAM_END;
 5099       }
 5100       else
 5101       {
 5102         z->msg = (char*)"invalid literal/length code";
 5103         UNGRAB
 5104         UPDATE
 5105         return Z_DATA_ERROR;
 5106       }
 5107     } while (1);
 5108   } while (m >= 258 && n >= 10);
 5109 
 5110   /* not enough input or output--restore pointers and return */
 5111   UNGRAB
 5112   UPDATE
 5113   return Z_OK;
 5114 }
 5115 /* --- inffast.c */
 5116 
 5117 /* +++ zutil.c */
 5118 /* zutil.c -- target dependent utility functions for the compression library
 5119  * Copyright (C) 1995-1996 Jean-loup Gailly.
 5120  * For conditions of distribution and use, see copyright notice in zlib.h 
 5121  */
 5122 
 5123 /* From: zutil.c,v 1.17 1996/07/24 13:41:12 me Exp $ */
 5124 
 5125 #ifdef DEBUG_ZLIB
 5126 #include <stdio.h>
 5127 #endif
 5128 
 5129 /* #include "zutil.h" */
 5130 
 5131 #ifndef NO_DUMMY_DECL
 5132 struct internal_state      {int dummy;}; /* for buggy compilers */
 5133 #endif
 5134 
 5135 #ifndef STDC
 5136 extern void exit OF((int));
 5137 #endif
 5138 
 5139 static const char *z_errmsg[10] = {
 5140 "need dictionary",     /* Z_NEED_DICT       2  */
 5141 "stream end",          /* Z_STREAM_END      1  */
 5142 "",                    /* Z_OK              0  */
 5143 "file error",          /* Z_ERRNO         (-1) */
 5144 "stream error",        /* Z_STREAM_ERROR  (-2) */
 5145 "data error",          /* Z_DATA_ERROR    (-3) */
 5146 "insufficient memory", /* Z_MEM_ERROR     (-4) */
 5147 "buffer error",        /* Z_BUF_ERROR     (-5) */
 5148 "incompatible version",/* Z_VERSION_ERROR (-6) */
 5149 ""};
 5150 
 5151 
 5152 const char *zlibVersion()
 5153 {
 5154     return ZLIB_VERSION;
 5155 }
 5156 
 5157 #ifdef DEBUG_ZLIB
 5158 void z_error (m)
 5159     char *m;
 5160 {
 5161     fprintf(stderr, "%s\n", m);
 5162     exit(1);
 5163 }
 5164 #endif
 5165 
 5166 #ifndef HAVE_MEMCPY
 5167 
 5168 void zmemcpy(dest, source, len)
 5169     Bytef* dest;
 5170     Bytef* source;
 5171     uInt  len;
 5172 {
 5173     if (len == 0) return;
 5174     do {
 5175         *dest++ = *source++; /* ??? to be unrolled */
 5176     } while (--len != 0);
 5177 }
 5178 
 5179 int zmemcmp(s1, s2, len)
 5180     Bytef* s1;
 5181     Bytef* s2;
 5182     uInt  len;
 5183 {
 5184     uInt j;
 5185 
 5186     for (j = 0; j < len; j++) {
 5187         if (s1[j] != s2[j]) return 2*(s1[j] > s2[j])-1;
 5188     }
 5189     return 0;
 5190 }
 5191 
 5192 void zmemzero(dest, len)
 5193     Bytef* dest;
 5194     uInt  len;
 5195 {
 5196     if (len == 0) return;
 5197     do {
 5198         *dest++ = 0;  /* ??? to be unrolled */
 5199     } while (--len != 0);
 5200 }
 5201 #endif
 5202 
 5203 #ifdef __TURBOC__
 5204 #if (defined( __BORLANDC__) || !defined(SMALL_MEDIUM)) && !defined(__32BIT__)
 5205 /* Small and medium model in Turbo C are for now limited to near allocation
 5206  * with reduced MAX_WBITS and MAX_MEM_LEVEL
 5207  */
 5208 #  define MY_ZCALLOC
 5209 
 5210 /* Turbo C malloc() does not allow dynamic allocation of 64K bytes
 5211  * and farmalloc(64K) returns a pointer with an offset of 8, so we
 5212  * must fix the pointer. Warning: the pointer must be put back to its
 5213  * original form in order to free it, use zcfree().
 5214  */
 5215 
 5216 #define MAX_PTR 10
 5217 /* 10*64K = 640K */
 5218 
 5219 local int next_ptr = 0;
 5220 
 5221 typedef struct ptr_table_s {
 5222     voidpf org_ptr;
 5223     voidpf new_ptr;
 5224 } ptr_table;
 5225 
 5226 local ptr_table table[MAX_PTR];
 5227 /* This table is used to remember the original form of pointers
 5228  * to large buffers (64K). Such pointers are normalized with a zero offset.
 5229  * Since MSDOS is not a preemptive multitasking OS, this table is not
 5230  * protected from concurrent access. This hack doesn't work anyway on
 5231  * a protected system like OS/2. Use Microsoft C instead.
 5232  */
 5233 
 5234 voidpf zcalloc (voidpf opaque, unsigned items, unsigned size)
 5235 {
 5236     voidpf buf = opaque; /* just to make some compilers happy */
 5237     ulg bsize = (ulg)items*size;
 5238 
 5239     /* If we allocate less than 65520 bytes, we assume that farmalloc
 5240      * will return a usable pointer which doesn't have to be normalized.
 5241      */
 5242     if (bsize < 65520L) {
 5243         buf = farmalloc(bsize);
 5244         if (*(ush*)&buf != 0) return buf;
 5245     } else {
 5246         buf = farmalloc(bsize + 16L);
 5247     }
 5248     if (buf == NULL || next_ptr >= MAX_PTR) return NULL;
 5249     table[next_ptr].org_ptr = buf;
 5250 
 5251     /* Normalize the pointer to seg:0 */
 5252     *((ush*)&buf+1) += ((ush)((uch*)buf-0) + 15) >> 4;
 5253     *(ush*)&buf = 0;
 5254     table[next_ptr++].new_ptr = buf;
 5255     return buf;
 5256 }
 5257 
 5258 void  zcfree (voidpf opaque, voidpf ptr)
 5259 {
 5260     int n;
 5261     if (*(ush*)&ptr != 0) { /* object < 64K */
 5262         farfree(ptr);
 5263         return;
 5264     }
 5265     /* Find the original pointer */
 5266     for (n = 0; n < next_ptr; n++) {
 5267         if (ptr != table[n].new_ptr) continue;
 5268 
 5269         farfree(table[n].org_ptr);
 5270         while (++n < next_ptr) {
 5271             table[n-1] = table[n];
 5272         }
 5273         next_ptr--;
 5274         return;
 5275     }
 5276     ptr = opaque; /* just to make some compilers happy */
 5277     Assert(0, "zcfree: ptr not found");
 5278 }
 5279 #endif
 5280 #endif /* __TURBOC__ */
 5281 
 5282 
 5283 #if defined(M_I86) && !defined(__32BIT__)
 5284 /* Microsoft C in 16-bit mode */
 5285 
 5286 #  define MY_ZCALLOC
 5287 
 5288 #if (!defined(_MSC_VER) || (_MSC_VER < 600))
 5289 #  define _halloc  halloc
 5290 #  define _hfree   hfree
 5291 #endif
 5292 
 5293 voidpf zcalloc (voidpf opaque, unsigned items, unsigned size)
 5294 {
 5295     if (opaque) opaque = 0; /* to make compiler happy */
 5296     return _halloc((long)items, size);
 5297 }
 5298 
 5299 void  zcfree (voidpf opaque, voidpf ptr)
 5300 {
 5301     if (opaque) opaque = 0; /* to make compiler happy */
 5302     _hfree(ptr);
 5303 }
 5304 
 5305 #endif /* MSC */
 5306 
 5307 
 5308 #ifndef MY_ZCALLOC /* Any system without a special alloc function */
 5309 
 5310 #ifndef STDC
 5311 extern voidp  calloc OF((uInt items, uInt size));
 5312 extern void   free   OF((voidpf ptr));
 5313 #endif
 5314 
 5315 voidpf zcalloc (opaque, items, size)
 5316     voidpf opaque;
 5317     unsigned items;
 5318     unsigned size;
 5319 {
 5320     if (opaque) items += size - size; /* make compiler happy */
 5321     return (voidpf)calloc(items, size);
 5322 }
 5323 
 5324 void  zcfree (opaque, ptr)
 5325     voidpf opaque;
 5326     voidpf ptr;
 5327 {
 5328     free(ptr);
 5329     if (opaque) return; /* make compiler happy */
 5330 }
 5331 
 5332 #endif /* MY_ZCALLOC */
 5333 /* --- zutil.c */
 5334 
 5335 /* +++ adler32.c */
 5336 /* adler32.c -- compute the Adler-32 checksum of a data stream
 5337  * Copyright (C) 1995-1996 Mark Adler
 5338  * For conditions of distribution and use, see copyright notice in zlib.h 
 5339  */
 5340 
 5341 /* From: adler32.c,v 1.10 1996/05/22 11:52:18 me Exp $ */
 5342 
 5343 /* #include "zlib.h" */
 5344 
 5345 #define BASE 65521L /* largest prime smaller than 65536 */
 5346 #define NMAX 5552
 5347 /* NMAX is the largest n such that 255n(n+1)/2 + (n+1)(BASE-1) <= 2^32-1 */
 5348 
 5349 #define DO1(buf,i)  {s1 += buf[(i)]; s2 += s1;}
 5350 #define DO2(buf,i)  DO1(buf,i); DO1(buf,(i)+1);
 5351 #define DO4(buf,i)  DO2(buf,i); DO2(buf,(i)+2);
 5352 #define DO8(buf,i)  DO4(buf,i); DO4(buf,(i)+4);
 5353 #define DO16(buf)   DO8(buf,0); DO8(buf,8);
 5354 
 5355 /* ========================================================================= */
 5356 uLong adler32(adler, buf, len)
 5357     uLong adler;
 5358     const Bytef *buf;
 5359     uInt len;
 5360 {
 5361     unsigned long s1 = adler & 0xffff;
 5362     unsigned long s2 = (adler >> 16) & 0xffff;
 5363     int k;
 5364 
 5365     if (buf == Z_NULL) return 1L;
 5366 
 5367     while (len > 0) {
 5368         k = len < NMAX ? len : NMAX;
 5369         len -= k;
 5370         while (k >= 16) {
 5371             DO16(buf);
 5372             buf += 16;
 5373             k -= 16;
 5374         }
 5375         if (k != 0) do {
 5376             s1 += *buf++;
 5377             s2 += s1;
 5378         } while (--k);
 5379         s1 %= BASE;
 5380         s2 %= BASE;
 5381     }
 5382     return (s2 << 16) | s1;
 5383 }
 5384 /* --- adler32.c */
 5385 
 5386 #ifdef _KERNEL
 5387 static int
 5388 zlib_modevent(module_t mod, int type, void *unused)
 5389 {
 5390         switch (type) {
 5391         case MOD_LOAD:
 5392                 return 0;
 5393         case MOD_UNLOAD:
 5394                 return 0;
 5395         }
 5396         return EINVAL;
 5397 }
 5398 
 5399 static moduledata_t zlib_mod = {
 5400         "zlib",
 5401         zlib_modevent,
 5402         0
 5403 };
 5404 DECLARE_MODULE(zlib, zlib_mod, SI_SUB_DRIVERS, SI_ORDER_FIRST);
 5405 MODULE_VERSION(zlib, 1);
 5406 #endif /* _KERNEL */

Cache object: 57d2a1d0e7ebe32b92bb5158b360904d


[ source navigation ] [ diff markup ] [ identifier search ] [ freetext search ] [ file search ] [ list types ] [ track identifier ]


This page is part of the FreeBSD/Linux Linux Kernel Cross-Reference, and was automatically generated using a modified version of the LXR engine.