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

Cache object: 92cca0f4d5cfa866e80220b81deda9a3


[ 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.