mods to separate allocations during initialization and operation
[ppp.git] / common / zlib.c
1 /*
2  * This file is derived from various .h and .c files from the zlib-0.95
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  * - changed functions not used outside this file to "local"
10  * - added minCompression parameter to deflateInit2
11  * - added Z_PACKET_FLUSH (see zlib.h for details)
12  * - added inflateIncomp
13  *
14  * $Id: zlib.c,v 1.6 1997/04/30 05:41:19 paulus Exp $
15  */
16
17 /* 
18  *  ==FILEVERSION 970421==
19  *
20  * This marker is used by the Linux installation script to determine
21  * whether an up-to-date version of this file is already installed.
22  */
23
24 /*+++++*/
25 /* zutil.h -- internal interface and configuration of the compression library
26  * Copyright (C) 1995 Jean-loup Gailly.
27  * For conditions of distribution and use, see copyright notice in zlib.h
28  */
29
30 /* WARNING: this file should *not* be used by applications. It is
31    part of the implementation of the compression library and is
32    subject to change. Applications should only use zlib.h.
33  */
34
35 /* From: zutil.h,v 1.9 1995/05/03 17:27:12 jloup Exp */
36
37 #define _Z_UTIL_H
38
39 #include "zlib.h"
40
41 #ifndef local
42 #  define local static
43 #endif
44 /* compile with -Dlocal if your debugger can't find static symbols */
45
46 #define FAR
47
48 typedef unsigned char  uch;
49 typedef uch FAR uchf;
50 typedef unsigned short ush;
51 typedef ush FAR ushf;
52 typedef unsigned long  ulg;
53
54 extern char *z_errmsg[]; /* indexed by 1-zlib_error */
55
56 #define ERR_RETURN(strm,err) return (strm->msg=z_errmsg[1-err], err)
57 /* To be used only when the state is known to be valid */
58
59 #ifndef NULL
60 #define NULL    ((void *) 0)
61 #endif
62
63         /* common constants */
64
65 #define DEFLATED   8
66
67 #ifndef DEF_WBITS
68 #  define DEF_WBITS MAX_WBITS
69 #endif
70 /* default windowBits for decompression. MAX_WBITS is for compression only */
71
72 #if MAX_MEM_LEVEL >= 8
73 #  define DEF_MEM_LEVEL 8
74 #else
75 #  define DEF_MEM_LEVEL  MAX_MEM_LEVEL
76 #endif
77 /* default memLevel */
78
79 #define STORED_BLOCK 0
80 #define STATIC_TREES 1
81 #define DYN_TREES    2
82 /* The three kinds of block type */
83
84 #define MIN_MATCH  3
85 #define MAX_MATCH  258
86 /* The minimum and maximum match lengths */
87
88          /* functions */
89
90 #if defined(KERNEL) || defined(_KERNEL)
91 #include <sys/types.h>
92 #include <sys/time.h>
93 #include <sys/systm.h>
94 #  define zmemcpy(d, s, n)      bcopy((s), (d), (n))
95 #  define zmemzero              bzero
96
97 #else
98 #if defined(__KERNEL__)
99 /* Assume this is Linux */
100 #include <linux/string.h>
101 #define zmemcpy memcpy
102 #define zmemzero(dest, len)     memset(dest, 0, len)
103
104 #else /* not kernel */
105 #if defined(STDC) && !defined(HAVE_MEMCPY) && !defined(NO_MEMCPY)
106 #  define HAVE_MEMCPY
107 #endif
108 #ifdef HAVE_MEMCPY
109 #    define zmemcpy memcpy
110 #    define zmemzero(dest, len) memset(dest, 0, len)
111 #else
112    extern void zmemcpy  OF((Bytef* dest, Bytef* source, uInt len));
113    extern void zmemzero OF((Bytef* dest, uInt len));
114 #endif
115 #endif  /* __KERNEL__ */
116 #endif  /* KERNEL */
117
118 /* Diagnostic functions */
119 #ifdef DEBUG_ZLIB
120 #  include <stdio.h>
121 #  ifndef verbose
122 #    define verbose 0
123 #  endif
124 #  define Assert(cond,msg) {if(!(cond)) z_error(msg);}
125 #  define Trace(x) fprintf x
126 #  define Tracev(x) {if (verbose) fprintf x ;}
127 #  define Tracevv(x) {if (verbose>1) fprintf x ;}
128 #  define Tracec(c,x) {if (verbose && (c)) fprintf x ;}
129 #  define Tracecv(c,x) {if (verbose>1 && (c)) fprintf x ;}
130 #else
131 #  define Assert(cond,msg)
132 #  define Trace(x)
133 #  define Tracev(x)
134 #  define Tracevv(x)
135 #  define Tracec(c,x)
136 #  define Tracecv(c,x)
137 #endif
138
139
140 typedef uLong (*check_func) OF((uLong check, Bytef *buf, uInt len));
141
142 /* voidpf zcalloc OF((voidpf opaque, unsigned items, unsigned size)); */
143 /* void   zcfree  OF((voidpf opaque, voidpf ptr)); */
144
145 #define ZALLOC(strm, items, size) \
146            (*((strm)->zalloc))((strm)->opaque, (items), (size))
147 #define ZALLOC_INIT(strm, items, size) \
148            (*((strm)->zalloc_init))((strm)->opaque, (items), (size))
149 #define ZFREE(strm, addr, size) \
150            (*((strm)->zfree))((strm)->opaque, (voidpf)(addr), (size))
151 #define TRY_FREE(s, p, n) {if (p) ZFREE(s, p, n);}
152
153 /* deflate.h -- internal compression state
154  * Copyright (C) 1995 Jean-loup Gailly
155  * For conditions of distribution and use, see copyright notice in zlib.h 
156  */
157
158 /* WARNING: this file should *not* be used by applications. It is
159    part of the implementation of the compression library and is
160    subject to change. Applications should only use zlib.h.
161  */
162
163
164 /*+++++*/
165 /* From: deflate.h,v 1.5 1995/05/03 17:27:09 jloup Exp */
166
167 /* ===========================================================================
168  * Internal compression state.
169  */
170
171 /* Data type */
172 #define Z_BINARY  0
173 #define ASCII   1
174 #define UNKNOWN 2
175
176 #define LENGTH_CODES 29
177 /* number of length codes, not counting the special END_BLOCK code */
178
179 #define LITERALS  256
180 /* number of literal bytes 0..255 */
181
182 #define L_CODES (LITERALS+1+LENGTH_CODES)
183 /* number of Literal or Length codes, including the END_BLOCK code */
184
185 #define D_CODES   30
186 /* number of distance codes */
187
188 #define BL_CODES  19
189 /* number of codes used to transfer the bit lengths */
190
191 #define HEAP_SIZE (2*L_CODES+1)
192 /* maximum heap size */
193
194 #define MAX_BITS 15
195 /* All codes must not exceed MAX_BITS bits */
196
197 #define INIT_STATE    42
198 #define BUSY_STATE   113
199 #define FLUSH_STATE  124
200 #define FINISH_STATE 666
201 /* Stream status */
202
203
204 /* Data structure describing a single value and its code string. */
205 typedef struct ct_data_s {
206     union {
207         ush  freq;       /* frequency count */
208         ush  code;       /* bit string */
209     } fc;
210     union {
211         ush  dad;        /* father node in Huffman tree */
212         ush  len;        /* length of bit string */
213     } dl;
214 } FAR ct_data;
215
216 #define Freq fc.freq
217 #define Code fc.code
218 #define Dad  dl.dad
219 #define Len  dl.len
220
221 typedef struct static_tree_desc_s  static_tree_desc;
222
223 typedef struct tree_desc_s {
224     ct_data *dyn_tree;           /* the dynamic tree */
225     int     max_code;            /* largest code with non zero frequency */
226     static_tree_desc *stat_desc; /* the corresponding static tree */
227 } FAR tree_desc;
228
229 typedef ush Pos;
230 typedef Pos FAR Posf;
231 typedef unsigned IPos;
232
233 /* A Pos is an index in the character window. We use short instead of int to
234  * save space in the various tables. IPos is used only for parameter passing.
235  */
236
237 typedef struct deflate_state {
238     z_stream *strm;      /* pointer back to this zlib stream */
239     int   status;        /* as the name implies */
240     Bytef *pending_buf;  /* output still pending */
241     Bytef *pending_out;  /* next pending byte to output to the stream */
242     int   pending;       /* nb of bytes in the pending buffer */
243     uLong adler;         /* adler32 of uncompressed data */
244     int   noheader;      /* suppress zlib header and adler32 */
245     Byte  data_type;     /* UNKNOWN, Z_BINARY or ASCII */
246     Byte  method;        /* STORED (for zip only) or DEFLATED */
247     int   minCompr;      /* min size decrease for Z_FLUSH_NOSTORE */
248
249                 /* used by deflate.c: */
250
251     uInt  w_size;        /* LZ77 window size (32K by default) */
252     uInt  w_bits;        /* log2(w_size)  (8..16) */
253     uInt  w_mask;        /* w_size - 1 */
254
255     Bytef *window;
256     /* Sliding window. Input bytes are read into the second half of the window,
257      * and move to the first half later to keep a dictionary of at least wSize
258      * bytes. With this organization, matches are limited to a distance of
259      * wSize-MAX_MATCH bytes, but this ensures that IO is always
260      * performed with a length multiple of the block size. Also, it limits
261      * the window size to 64K, which is quite useful on MSDOS.
262      * To do: use the user input buffer as sliding window.
263      */
264
265     ulg window_size;
266     /* Actual size of window: 2*wSize, except when the user input buffer
267      * is directly used as sliding window.
268      */
269
270     Posf *prev;
271     /* Link to older string with same hash index. To limit the size of this
272      * array to 64K, this link is maintained only for the last 32K strings.
273      * An index in this array is thus a window index modulo 32K.
274      */
275
276     Posf *head; /* Heads of the hash chains or NIL. */
277
278     uInt  ins_h;          /* hash index of string to be inserted */
279     uInt  hash_size;      /* number of elements in hash table */
280     uInt  hash_bits;      /* log2(hash_size) */
281     uInt  hash_mask;      /* hash_size-1 */
282
283     uInt  hash_shift;
284     /* Number of bits by which ins_h must be shifted at each input
285      * step. It must be such that after MIN_MATCH steps, the oldest
286      * byte no longer takes part in the hash key, that is:
287      *   hash_shift * MIN_MATCH >= hash_bits
288      */
289
290     long block_start;
291     /* Window position at the beginning of the current output block. Gets
292      * negative when the window is moved backwards.
293      */
294
295     uInt match_length;           /* length of best match */
296     IPos prev_match;             /* previous match */
297     int match_available;         /* set if previous match exists */
298     uInt strstart;               /* start of string to insert */
299     uInt match_start;            /* start of matching string */
300     uInt lookahead;              /* number of valid bytes ahead in window */
301
302     uInt prev_length;
303     /* Length of the best match at previous step. Matches not greater than this
304      * are discarded. This is used in the lazy match evaluation.
305      */
306
307     uInt max_chain_length;
308     /* To speed up deflation, hash chains are never searched beyond this
309      * length.  A higher limit improves compression ratio but degrades the
310      * speed.
311      */
312
313     uInt max_lazy_match;
314     /* Attempt to find a better match only when the current match is strictly
315      * smaller than this value. This mechanism is used only for compression
316      * levels >= 4.
317      */
318 #   define max_insert_length  max_lazy_match
319     /* Insert new strings in the hash table only if the match length is not
320      * greater than this length. This saves time but degrades compression.
321      * max_insert_length is used only for compression levels <= 3.
322      */
323
324     int level;    /* compression level (1..9) */
325     int strategy; /* favor or force Huffman coding*/
326
327     uInt good_match;
328     /* Use a faster search when the previous match is longer than this */
329
330      int nice_match; /* Stop searching when current match exceeds this */
331
332                 /* used by trees.c: */
333     /* Didn't use ct_data typedef below to supress compiler warning */
334     struct ct_data_s dyn_ltree[HEAP_SIZE];   /* literal and length tree */
335     struct ct_data_s dyn_dtree[2*D_CODES+1]; /* distance tree */
336     struct ct_data_s bl_tree[2*BL_CODES+1];  /* Huffman tree for bit lengths */
337
338     struct tree_desc_s l_desc;               /* desc. for literal tree */
339     struct tree_desc_s d_desc;               /* desc. for distance tree */
340     struct tree_desc_s bl_desc;              /* desc. for bit length tree */
341
342     ush bl_count[MAX_BITS+1];
343     /* number of codes at each bit length for an optimal tree */
344
345     int heap[2*L_CODES+1];      /* heap used to build the Huffman trees */
346     int heap_len;               /* number of elements in the heap */
347     int heap_max;               /* element of largest frequency */
348     /* The sons of heap[n] are heap[2*n] and heap[2*n+1]. heap[0] is not used.
349      * The same heap array is used to build all trees.
350      */
351
352     uch depth[2*L_CODES+1];
353     /* Depth of each subtree used as tie breaker for trees of equal frequency
354      */
355
356     uchf *l_buf;          /* buffer for literals or lengths */
357
358     uInt  lit_bufsize;
359     /* Size of match buffer for literals/lengths.  There are 4 reasons for
360      * limiting lit_bufsize to 64K:
361      *   - frequencies can be kept in 16 bit counters
362      *   - if compression is not successful for the first block, all input
363      *     data is still in the window so we can still emit a stored block even
364      *     when input comes from standard input.  (This can also be done for
365      *     all blocks if lit_bufsize is not greater than 32K.)
366      *   - if compression is not successful for a file smaller than 64K, we can
367      *     even emit a stored file instead of a stored block (saving 5 bytes).
368      *     This is applicable only for zip (not gzip or zlib).
369      *   - creating new Huffman trees less frequently may not provide fast
370      *     adaptation to changes in the input data statistics. (Take for
371      *     example a binary file with poorly compressible code followed by
372      *     a highly compressible string table.) Smaller buffer sizes give
373      *     fast adaptation but have of course the overhead of transmitting
374      *     trees more frequently.
375      *   - I can't count above 4
376      */
377
378     uInt last_lit;      /* running index in l_buf */
379
380     ushf *d_buf;
381     /* Buffer for distances. To simplify the code, d_buf and l_buf have
382      * the same number of elements. To use different lengths, an extra flag
383      * array would be necessary.
384      */
385
386     ulg opt_len;        /* bit length of current block with optimal trees */
387     ulg static_len;     /* bit length of current block with static trees */
388     ulg compressed_len; /* total bit length of compressed file */
389     uInt matches;       /* number of string matches in current block */
390     int last_eob_len;   /* bit length of EOB code for last block */
391
392 #ifdef DEBUG_ZLIB
393     ulg bits_sent;      /* bit length of the compressed data */
394 #endif
395
396     ush bi_buf;
397     /* Output buffer. bits are inserted starting at the bottom (least
398      * significant bits).
399      */
400     int bi_valid;
401     /* Number of valid bits in bi_buf.  All bits above the last valid bit
402      * are always zero.
403      */
404
405     uInt blocks_in_packet;
406     /* Number of blocks produced since the last time Z_PACKET_FLUSH
407      * was used.
408      */
409
410 } FAR deflate_state;
411
412 /* Output a byte on the stream.
413  * IN assertion: there is enough room in pending_buf.
414  */
415 #define put_byte(s, c) {s->pending_buf[s->pending++] = (c);}
416
417
418 #define MIN_LOOKAHEAD (MAX_MATCH+MIN_MATCH+1)
419 /* Minimum amount of lookahead, except at the end of the input file.
420  * See deflate.c for comments about the MIN_MATCH+1.
421  */
422
423 #define MAX_DIST(s)  ((s)->w_size-MIN_LOOKAHEAD)
424 /* In order to simplify the code, particularly on 16 bit machines, match
425  * distances are limited to MAX_DIST instead of WSIZE.
426  */
427
428         /* in trees.c */
429 local void ct_init       OF((deflate_state *s));
430 local int  ct_tally      OF((deflate_state *s, int dist, int lc));
431 local ulg ct_flush_block OF((deflate_state *s, charf *buf, ulg stored_len,
432                              int flush));
433 local void ct_align      OF((deflate_state *s));
434 local void ct_stored_block OF((deflate_state *s, charf *buf, ulg stored_len,
435                           int eof));
436 local void ct_stored_type_only OF((deflate_state *s));
437
438
439 /*+++++*/
440 /* deflate.c -- compress data using the deflation algorithm
441  * Copyright (C) 1995 Jean-loup Gailly.
442  * For conditions of distribution and use, see copyright notice in zlib.h 
443  */
444
445 /*
446  *  ALGORITHM
447  *
448  *      The "deflation" process depends on being able to identify portions
449  *      of the input text which are identical to earlier input (within a
450  *      sliding window trailing behind the input currently being processed).
451  *
452  *      The most straightforward technique turns out to be the fastest for
453  *      most input files: try all possible matches and select the longest.
454  *      The key feature of this algorithm is that insertions into the string
455  *      dictionary are very simple and thus fast, and deletions are avoided
456  *      completely. Insertions are performed at each input character, whereas
457  *      string matches are performed only when the previous match ends. So it
458  *      is preferable to spend more time in matches to allow very fast string
459  *      insertions and avoid deletions. The matching algorithm for small
460  *      strings is inspired from that of Rabin & Karp. A brute force approach
461  *      is used to find longer strings when a small match has been found.
462  *      A similar algorithm is used in comic (by Jan-Mark Wams) and freeze
463  *      (by Leonid Broukhis).
464  *         A previous version of this file used a more sophisticated algorithm
465  *      (by Fiala and Greene) which is guaranteed to run in linear amortized
466  *      time, but has a larger average cost, uses more memory and is patented.
467  *      However the F&G algorithm may be faster for some highly redundant
468  *      files if the parameter max_chain_length (described below) is too large.
469  *
470  *  ACKNOWLEDGEMENTS
471  *
472  *      The idea of lazy evaluation of matches is due to Jan-Mark Wams, and
473  *      I found it in 'freeze' written by Leonid Broukhis.
474  *      Thanks to many people for bug reports and testing.
475  *
476  *  REFERENCES
477  *
478  *      Deutsch, L.P.,"'Deflate' Compressed Data Format Specification".
479  *      Available in ftp.uu.net:/pub/archiving/zip/doc/deflate-1.1.doc
480  *
481  *      A description of the Rabin and Karp algorithm is given in the book
482  *         "Algorithms" by R. Sedgewick, Addison-Wesley, p252.
483  *
484  *      Fiala,E.R., and Greene,D.H.
485  *         Data Compression with Finite Windows, Comm.ACM, 32,4 (1989) 490-595
486  *
487  */
488
489 /* From: deflate.c,v 1.8 1995/05/03 17:27:08 jloup Exp */
490
491 local char zlib_copyright[] = " deflate Copyright 1995 Jean-loup Gailly ";
492 /*
493   If you use the zlib library in a product, an acknowledgment is welcome
494   in the documentation of your product. If for some reason you cannot
495   include such an acknowledgment, I would appreciate that you keep this
496   copyright string in the executable of your product.
497  */
498
499 #define NIL 0
500 /* Tail of hash chains */
501
502 #ifndef TOO_FAR
503 #  define TOO_FAR 4096
504 #endif
505 /* Matches of length 3 are discarded if their distance exceeds TOO_FAR */
506
507 #define MIN_LOOKAHEAD (MAX_MATCH+MIN_MATCH+1)
508 /* Minimum amount of lookahead, except at the end of the input file.
509  * See deflate.c for comments about the MIN_MATCH+1.
510  */
511
512 /* Values for max_lazy_match, good_match and max_chain_length, depending on
513  * the desired pack level (0..9). The values given below have been tuned to
514  * exclude worst case performance for pathological files. Better values may be
515  * found for specific files.
516  */
517
518 typedef struct config_s {
519    ush good_length; /* reduce lazy search above this match length */
520    ush max_lazy;    /* do not perform lazy search above this match length */
521    ush nice_length; /* quit search above this match length */
522    ush max_chain;
523 } config;
524
525 local config configuration_table[10] = {
526 /*      good lazy nice chain */
527 /* 0 */ {0,    0,  0,    0},  /* store only */
528 /* 1 */ {4,    4,  8,    4},  /* maximum speed, no lazy matches */
529 /* 2 */ {4,    5, 16,    8},
530 /* 3 */ {4,    6, 32,   32},
531
532 /* 4 */ {4,    4, 16,   16},  /* lazy matches */
533 /* 5 */ {8,   16, 32,   32},
534 /* 6 */ {8,   16, 128, 128},
535 /* 7 */ {8,   32, 128, 256},
536 /* 8 */ {32, 128, 258, 1024},
537 /* 9 */ {32, 258, 258, 4096}}; /* maximum compression */
538
539 /* Note: the deflate() code requires max_lazy >= MIN_MATCH and max_chain >= 4
540  * For deflate_fast() (levels <= 3) good is ignored and lazy has a different
541  * meaning.
542  */
543
544 #define EQUAL 0
545 /* result of memcmp for equal strings */
546
547 /* ===========================================================================
548  *  Prototypes for local functions.
549  */
550
551 local void fill_window   OF((deflate_state *s));
552 local int  deflate_fast  OF((deflate_state *s, int flush));
553 local int  deflate_slow  OF((deflate_state *s, int flush));
554 local void lm_init       OF((deflate_state *s));
555 local int longest_match  OF((deflate_state *s, IPos cur_match));
556 local void putShortMSB   OF((deflate_state *s, uInt b));
557 local void flush_pending OF((z_stream *strm));
558 local int read_buf       OF((z_stream *strm, charf *buf, unsigned size));
559 #ifdef ASMV
560       void match_init OF((void)); /* asm code initialization */
561 #endif
562
563 #ifdef DEBUG_ZLIB
564 local  void check_match OF((deflate_state *s, IPos start, IPos match,
565                             int length));
566 #endif
567
568
569 /* ===========================================================================
570  * Update a hash value with the given input byte
571  * IN  assertion: all calls to to UPDATE_HASH are made with consecutive
572  *    input characters, so that a running hash key can be computed from the
573  *    previous key instead of complete recalculation each time.
574  */
575 #define UPDATE_HASH(s,h,c) (h = (((h)<<s->hash_shift) ^ (c)) & s->hash_mask)
576
577
578 /* ===========================================================================
579  * Insert string str in the dictionary and set match_head to the previous head
580  * of the hash chain (the most recent string with same hash key). Return
581  * the previous length of the hash chain.
582  * IN  assertion: all calls to to INSERT_STRING are made with consecutive
583  *    input characters and the first MIN_MATCH bytes of str are valid
584  *    (except for the last MIN_MATCH-1 bytes of the input file).
585  */
586 #define INSERT_STRING(s, str, match_head) \
587    (UPDATE_HASH(s, s->ins_h, s->window[(str) + (MIN_MATCH-1)]), \
588     s->prev[(str) & s->w_mask] = match_head = s->head[s->ins_h], \
589     s->head[s->ins_h] = (str))
590
591 /* ===========================================================================
592  * Initialize the hash table (avoiding 64K overflow for 16 bit systems).
593  * prev[] will be initialized on the fly.
594  */
595 #define CLEAR_HASH(s) \
596     s->head[s->hash_size-1] = NIL; \
597     zmemzero((charf *)s->head, (unsigned)(s->hash_size-1)*sizeof(*s->head));
598
599 /* ========================================================================= */
600 int deflateInit (strm, level)
601     z_stream *strm;
602     int level;
603 {
604     return deflateInit2 (strm, level, DEFLATED, MAX_WBITS, DEF_MEM_LEVEL,
605                          0, 0);
606     /* To do: ignore strm->next_in if we use it as window */
607 }
608
609 /* ========================================================================= */
610 int deflateInit2 (strm, level, method, windowBits, memLevel,
611                   strategy, minCompression)
612     z_stream *strm;
613     int  level;
614     int  method;
615     int  windowBits;
616     int  memLevel;
617     int  strategy;
618     int  minCompression;
619 {
620     deflate_state *s;
621     int noheader = 0;
622
623     if (strm == Z_NULL) return Z_STREAM_ERROR;
624
625     strm->msg = Z_NULL;
626 /*    if (strm->zalloc == Z_NULL) strm->zalloc = zcalloc; */
627 /*    if (strm->zfree == Z_NULL) strm->zfree = zcfree; */
628
629     if (level == Z_DEFAULT_COMPRESSION) level = 6;
630
631     if (windowBits < 0) { /* undocumented feature: suppress zlib header */
632         noheader = 1;
633         windowBits = -windowBits;
634     }
635     if (memLevel < 1 || memLevel > MAX_MEM_LEVEL || method != DEFLATED ||
636         windowBits < 8 || windowBits > 15 || level < 1 || level > 9) {
637         return Z_STREAM_ERROR;
638     }
639     s = (deflate_state *) ZALLOC_INIT(strm, 1, sizeof(deflate_state));
640     if (s == Z_NULL) return Z_MEM_ERROR;
641     strm->state = (struct internal_state FAR *)s;
642     s->strm = strm;
643
644     s->noheader = noheader;
645     s->w_bits = windowBits;
646     s->w_size = 1 << s->w_bits;
647     s->w_mask = s->w_size - 1;
648
649     s->hash_bits = memLevel + 7;
650     s->hash_size = 1 << s->hash_bits;
651     s->hash_mask = s->hash_size - 1;
652     s->hash_shift =  ((s->hash_bits+MIN_MATCH-1)/MIN_MATCH);
653
654     s->window = (Bytef *) ZALLOC_INIT(strm, s->w_size, 2*sizeof(Byte));
655     s->prev   = (Posf *)  ZALLOC_INIT(strm, s->w_size, sizeof(Pos));
656     s->head   = (Posf *)  ZALLOC_INIT(strm, s->hash_size, sizeof(Pos));
657
658     s->lit_bufsize = 1 << (memLevel + 6); /* 16K elements by default */
659
660     s->pending_buf = (uchf *) ZALLOC_INIT(strm, s->lit_bufsize, 2*sizeof(ush));
661
662     if (s->window == Z_NULL || s->prev == Z_NULL || s->head == Z_NULL ||
663         s->pending_buf == Z_NULL) {
664         strm->msg = z_errmsg[1-Z_MEM_ERROR];
665         deflateEnd (strm);
666         return Z_MEM_ERROR;
667     }
668     s->d_buf = (ushf *) &(s->pending_buf[s->lit_bufsize]);
669     s->l_buf = (uchf *) &(s->pending_buf[3*s->lit_bufsize]);
670     /* We overlay pending_buf and d_buf+l_buf. This works since the average
671      * output size for (length,distance) codes is <= 32 bits (worst case
672      * is 15+15+13=33).
673      */
674
675     s->level = level;
676     s->strategy = strategy;
677     s->method = (Byte)method;
678     s->minCompr = minCompression;
679     s->blocks_in_packet = 0;
680
681     return deflateReset(strm);
682 }
683
684 /* ========================================================================= */
685 int deflateReset (strm)
686     z_stream *strm;
687 {
688     deflate_state *s;
689     
690     if (strm == Z_NULL || strm->state == Z_NULL ||
691         strm->zalloc == Z_NULL || strm->zfree == Z_NULL ||
692         strm->zalloc_init == Z_NULL) return Z_STREAM_ERROR;
693
694     strm->total_in = strm->total_out = 0;
695     strm->msg = Z_NULL; /* use zfree if we ever allocate msg dynamically */
696     strm->data_type = Z_UNKNOWN;
697
698     s = (deflate_state *)strm->state;
699     s->pending = 0;
700     s->pending_out = s->pending_buf;
701
702     if (s->noheader < 0) {
703         s->noheader = 0; /* was set to -1 by deflate(..., Z_FINISH); */
704     }
705     s->status = s->noheader ? BUSY_STATE : INIT_STATE;
706     s->adler = 1;
707
708     ct_init(s);
709     lm_init(s);
710
711     return Z_OK;
712 }
713
714 /* =========================================================================
715  * Put a short in the pending buffer. The 16-bit value is put in MSB order.
716  * IN assertion: the stream state is correct and there is enough room in
717  * pending_buf.
718  */
719 local void putShortMSB (s, b)
720     deflate_state *s;
721     uInt b;
722 {
723     put_byte(s, (Byte)(b >> 8));
724     put_byte(s, (Byte)(b & 0xff));
725 }   
726
727 /* =========================================================================
728  * Flush as much pending output as possible.
729  */
730 local void flush_pending(strm)
731     z_stream *strm;
732 {
733     deflate_state *state = (deflate_state *) strm->state;
734     unsigned len = state->pending;
735
736     if (len > strm->avail_out) len = strm->avail_out;
737     if (len == 0) return;
738
739     if (strm->next_out != NULL) {
740         zmemcpy(strm->next_out, state->pending_out, len);
741         strm->next_out += len;
742     }
743     state->pending_out += len;
744     strm->total_out += len;
745     strm->avail_out -= len;
746     state->pending -= len;
747     if (state->pending == 0) {
748         state->pending_out = state->pending_buf;
749     }
750 }
751
752 /* ========================================================================= */
753 int deflate (strm, flush)
754     z_stream *strm;
755     int flush;
756 {
757     deflate_state *state = (deflate_state *) strm->state;
758
759     if (strm == Z_NULL || state == Z_NULL) return Z_STREAM_ERROR;
760     
761     if (strm->next_in == Z_NULL && strm->avail_in != 0) {
762         ERR_RETURN(strm, Z_STREAM_ERROR);
763     }
764     if (strm->avail_out == 0) ERR_RETURN(strm, Z_BUF_ERROR);
765
766     state->strm = strm; /* just in case */
767
768     /* Write the zlib header */
769     if (state->status == INIT_STATE) {
770
771         uInt header = (DEFLATED + ((state->w_bits-8)<<4)) << 8;
772         uInt level_flags = (state->level-1) >> 1;
773
774         if (level_flags > 3) level_flags = 3;
775         header |= (level_flags << 6);
776         header += 31 - (header % 31);
777
778         state->status = BUSY_STATE;
779         putShortMSB(state, header);
780     }
781
782     /* Flush as much pending output as possible */
783     if (state->pending != 0) {
784         flush_pending(strm);
785         if (strm->avail_out == 0) return Z_OK;
786     }
787
788     /* If we came back in here to get the last output from
789      * a previous flush, we're done for now.
790      */
791     if (state->status == FLUSH_STATE) {
792         state->status = BUSY_STATE;
793         if (flush != Z_NO_FLUSH && flush != Z_FINISH)
794             return Z_OK;
795     }
796
797     /* User must not provide more input after the first FINISH: */
798     if (state->status == FINISH_STATE && strm->avail_in != 0) {
799         ERR_RETURN(strm, Z_BUF_ERROR);
800     }
801
802     /* Start a new block or continue the current one.
803      */
804     if (strm->avail_in != 0 || state->lookahead != 0 ||
805         (flush == Z_FINISH && state->status != FINISH_STATE)) {
806         int quit;
807
808         if (flush == Z_FINISH) {
809             state->status = FINISH_STATE;
810         }
811         if (state->level <= 3) {
812             quit = deflate_fast(state, flush);
813         } else {
814             quit = deflate_slow(state, flush);
815         }
816         if (quit || strm->avail_out == 0)
817             return Z_OK;
818         /* If flush != Z_NO_FLUSH && avail_out == 0, the next call
819          * of deflate should use the same flush parameter to make sure
820          * that the flush is complete. So we don't have to output an
821          * empty block here, this will be done at next call. This also
822          * ensures that for a very small output buffer, we emit at most
823          * one empty block.
824          */
825     }
826
827     /* If a flush was requested, we have a little more to output now. */
828     if (flush != Z_NO_FLUSH && flush != Z_FINISH
829         && state->status != FINISH_STATE) {
830         switch (flush) {
831         case Z_PARTIAL_FLUSH:
832             ct_align(state);
833             break;
834         case Z_PACKET_FLUSH:
835             /* Output just the 3-bit `stored' block type value,
836                but not a zero length. */
837             ct_stored_type_only(state);
838             break;
839         default:
840             ct_stored_block(state, (char*)0, 0L, 0);
841             /* For a full flush, this empty block will be recognized
842              * as a special marker by inflate_sync().
843              */
844             if (flush == Z_FULL_FLUSH) {
845                 CLEAR_HASH(state);             /* forget history */
846             }
847         }
848         flush_pending(strm);
849         if (strm->avail_out == 0) {
850             /* We'll have to come back to get the rest of the output;
851              * this ensures we don't output a second zero-length stored
852              * block (or whatever).
853              */
854             state->status = FLUSH_STATE;
855             return Z_OK;
856         }
857     }
858
859     Assert(strm->avail_out > 0, "bug2");
860
861     if (flush != Z_FINISH) return Z_OK;
862     if (state->noheader) return Z_STREAM_END;
863
864     /* Write the zlib trailer (adler32) */
865     putShortMSB(state, (uInt)(state->adler >> 16));
866     putShortMSB(state, (uInt)(state->adler & 0xffff));
867     flush_pending(strm);
868     /* If avail_out is zero, the application will call deflate again
869      * to flush the rest.
870      */
871     state->noheader = -1; /* write the trailer only once! */
872     return state->pending != 0 ? Z_OK : Z_STREAM_END;
873 }
874
875 /* ========================================================================= */
876 int deflateEnd (strm)
877     z_stream *strm;
878 {
879     deflate_state *state = (deflate_state *) strm->state;
880
881     if (strm == Z_NULL || state == Z_NULL) return Z_STREAM_ERROR;
882
883     TRY_FREE(strm, state->window, state->w_size * 2 * sizeof(Byte));
884     TRY_FREE(strm, state->prev, state->w_size * sizeof(Pos));
885     TRY_FREE(strm, state->head, state->hash_size * sizeof(Pos));
886     TRY_FREE(strm, state->pending_buf, state->lit_bufsize * 2 * sizeof(ush));
887
888     ZFREE(strm, state, sizeof(deflate_state));
889     strm->state = Z_NULL;
890
891     return Z_OK;
892 }
893
894 /* ===========================================================================
895  * Read a new buffer from the current input stream, update the adler32
896  * and total number of bytes read.
897  */
898 local int read_buf(strm, buf, size)
899     z_stream *strm;
900     charf *buf;
901     unsigned size;
902 {
903     unsigned len = strm->avail_in;
904     deflate_state *state = (deflate_state *) strm->state;
905
906     if (len > size) len = size;
907     if (len == 0) return 0;
908
909     strm->avail_in  -= len;
910
911     if (!state->noheader) {
912         state->adler = adler32(state->adler, strm->next_in, len);
913     }
914     zmemcpy(buf, strm->next_in, len);
915     strm->next_in  += len;
916     strm->total_in += len;
917
918     return (int)len;
919 }
920
921 /* ===========================================================================
922  * Initialize the "longest match" routines for a new zlib stream
923  */
924 local void lm_init (s)
925     deflate_state *s;
926 {
927     s->window_size = (ulg)2L*s->w_size;
928
929     CLEAR_HASH(s);
930
931     /* Set the default configuration parameters:
932      */
933     s->max_lazy_match   = configuration_table[s->level].max_lazy;
934     s->good_match       = configuration_table[s->level].good_length;
935     s->nice_match       = configuration_table[s->level].nice_length;
936     s->max_chain_length = configuration_table[s->level].max_chain;
937
938     s->strstart = 0;
939     s->block_start = 0L;
940     s->lookahead = 0;
941     s->match_length = MIN_MATCH-1;
942     s->match_available = 0;
943     s->ins_h = 0;
944 #ifdef ASMV
945     match_init(); /* initialize the asm code */
946 #endif
947 }
948
949 /* ===========================================================================
950  * Set match_start to the longest match starting at the given string and
951  * return its length. Matches shorter or equal to prev_length are discarded,
952  * in which case the result is equal to prev_length and match_start is
953  * garbage.
954  * IN assertions: cur_match is the head of the hash chain for the current
955  *   string (strstart) and its distance is <= MAX_DIST, and prev_length >= 1
956  */
957 #ifndef ASMV
958 /* For 80x86 and 680x0, an optimized version will be provided in match.asm or
959  * match.S. The code will be functionally equivalent.
960  */
961 local int longest_match(s, cur_match)
962     deflate_state *s;
963     IPos cur_match;                             /* current match */
964 {
965     unsigned chain_length = s->max_chain_length;/* max hash chain length */
966     register Bytef *scan = s->window + s->strstart; /* current string */
967     register Bytef *match;                       /* matched string */
968     register int len;                           /* length of current match */
969     int best_len = s->prev_length;              /* best match length so far */
970     IPos limit = s->strstart > (IPos)MAX_DIST(s) ?
971         s->strstart - (IPos)MAX_DIST(s) : NIL;
972     /* Stop when cur_match becomes <= limit. To simplify the code,
973      * we prevent matches with the string of window index 0.
974      */
975     Posf *prev = s->prev;
976     uInt wmask = s->w_mask;
977
978 #ifdef UNALIGNED_OK
979     /* Compare two bytes at a time. Note: this is not always beneficial.
980      * Try with and without -DUNALIGNED_OK to check.
981      */
982     register Bytef *strend = s->window + s->strstart + MAX_MATCH - 1;
983     register ush scan_start = *(ushf*)scan;
984     register ush scan_end   = *(ushf*)(scan+best_len-1);
985 #else
986     register Bytef *strend = s->window + s->strstart + MAX_MATCH;
987     register Byte scan_end1  = scan[best_len-1];
988     register Byte scan_end   = scan[best_len];
989 #endif
990
991     /* The code is optimized for HASH_BITS >= 8 and MAX_MATCH-2 multiple of 16.
992      * It is easy to get rid of this optimization if necessary.
993      */
994     Assert(s->hash_bits >= 8 && MAX_MATCH == 258, "Code too clever");
995
996     /* Do not waste too much time if we already have a good match: */
997     if (s->prev_length >= s->good_match) {
998         chain_length >>= 2;
999     }
1000     Assert((ulg)s->strstart <= s->window_size-MIN_LOOKAHEAD, "need lookahead");
1001
1002     do {
1003         Assert(cur_match < s->strstart, "no future");
1004         match = s->window + cur_match;
1005
1006         /* Skip to next match if the match length cannot increase
1007          * or if the match length is less than 2:
1008          */
1009 #if (defined(UNALIGNED_OK) && MAX_MATCH == 258)
1010         /* This code assumes sizeof(unsigned short) == 2. Do not use
1011          * UNALIGNED_OK if your compiler uses a different size.
1012          */
1013         if (*(ushf*)(match+best_len-1) != scan_end ||
1014             *(ushf*)match != scan_start) continue;
1015
1016         /* It is not necessary to compare scan[2] and match[2] since they are
1017          * always equal when the other bytes match, given that the hash keys
1018          * are equal and that HASH_BITS >= 8. Compare 2 bytes at a time at
1019          * strstart+3, +5, ... up to strstart+257. We check for insufficient
1020          * lookahead only every 4th comparison; the 128th check will be made
1021          * at strstart+257. If MAX_MATCH-2 is not a multiple of 8, it is
1022          * necessary to put more guard bytes at the end of the window, or
1023          * to check more often for insufficient lookahead.
1024          */
1025         Assert(scan[2] == match[2], "scan[2]?");
1026         scan++, match++;
1027         do {
1028         } while (*(ushf*)(scan+=2) == *(ushf*)(match+=2) &&
1029                  *(ushf*)(scan+=2) == *(ushf*)(match+=2) &&
1030                  *(ushf*)(scan+=2) == *(ushf*)(match+=2) &&
1031                  *(ushf*)(scan+=2) == *(ushf*)(match+=2) &&
1032                  scan < strend);
1033         /* The funny "do {}" generates better code on most compilers */
1034
1035         /* Here, scan <= window+strstart+257 */
1036         Assert(scan <= s->window+(unsigned)(s->window_size-1), "wild scan");
1037         if (*scan == *match) scan++;
1038
1039         len = (MAX_MATCH - 1) - (int)(strend-scan);
1040         scan = strend - (MAX_MATCH-1);
1041
1042 #else /* UNALIGNED_OK */
1043
1044         if (match[best_len]   != scan_end  ||
1045             match[best_len-1] != scan_end1 ||
1046             *match            != *scan     ||
1047             *++match          != scan[1])      continue;
1048
1049         /* The check at best_len-1 can be removed because it will be made
1050          * again later. (This heuristic is not always a win.)
1051          * It is not necessary to compare scan[2] and match[2] since they
1052          * are always equal when the other bytes match, given that
1053          * the hash keys are equal and that HASH_BITS >= 8.
1054          */
1055         scan += 2, match++;
1056         Assert(*scan == *match, "match[2]?");
1057
1058         /* We check for insufficient lookahead only every 8th comparison;
1059          * the 256th check will be made at strstart+258.
1060          */
1061         do {
1062         } while (*++scan == *++match && *++scan == *++match &&
1063                  *++scan == *++match && *++scan == *++match &&
1064                  *++scan == *++match && *++scan == *++match &&
1065                  *++scan == *++match && *++scan == *++match &&
1066                  scan < strend);
1067
1068         Assert(scan <= s->window+(unsigned)(s->window_size-1), "wild scan");
1069
1070         len = MAX_MATCH - (int)(strend - scan);
1071         scan = strend - MAX_MATCH;
1072
1073 #endif /* UNALIGNED_OK */
1074
1075         if (len > best_len) {
1076             s->match_start = cur_match;
1077             best_len = len;
1078             if (len >= s->nice_match) break;
1079 #ifdef UNALIGNED_OK
1080             scan_end = *(ushf*)(scan+best_len-1);
1081 #else
1082             scan_end1  = scan[best_len-1];
1083             scan_end   = scan[best_len];
1084 #endif
1085         }
1086     } while ((cur_match = prev[cur_match & wmask]) > limit
1087              && --chain_length != 0);
1088
1089     return best_len;
1090 }
1091 #endif /* ASMV */
1092
1093 #ifdef DEBUG_ZLIB
1094 /* ===========================================================================
1095  * Check that the match at match_start is indeed a match.
1096  */
1097 local void check_match(s, start, match, length)
1098     deflate_state *s;
1099     IPos start, match;
1100     int length;
1101 {
1102     /* check that the match is indeed a match */
1103     if (memcmp((charf *)s->window + match,
1104                 (charf *)s->window + start, length) != EQUAL) {
1105         fprintf(stderr,
1106             " start %u, match %u, length %d\n",
1107             start, match, length);
1108         do { fprintf(stderr, "%c%c", s->window[match++],
1109                      s->window[start++]); } while (--length != 0);
1110         z_error("invalid match");
1111     }
1112     if (verbose > 1) {
1113         fprintf(stderr,"\\[%d,%d]", start-match, length);
1114         do { putc(s->window[start++], stderr); } while (--length != 0);
1115     }
1116 }
1117 #else
1118 #  define check_match(s, start, match, length)
1119 #endif
1120
1121 /* ===========================================================================
1122  * Fill the window when the lookahead becomes insufficient.
1123  * Updates strstart and lookahead.
1124  *
1125  * IN assertion: lookahead < MIN_LOOKAHEAD
1126  * OUT assertions: strstart <= window_size-MIN_LOOKAHEAD
1127  *    At least one byte has been read, or avail_in == 0; reads are
1128  *    performed for at least two bytes (required for the zip translate_eol
1129  *    option -- not supported here).
1130  */
1131 local void fill_window(s)
1132     deflate_state *s;
1133 {
1134     register unsigned n, m;
1135     register Posf *p;
1136     unsigned more;    /* Amount of free space at the end of the window. */
1137     uInt wsize = s->w_size;
1138
1139     do {
1140         more = (unsigned)(s->window_size -(ulg)s->lookahead -(ulg)s->strstart);
1141
1142         /* Deal with !@#$% 64K limit: */
1143         if (more == 0 && s->strstart == 0 && s->lookahead == 0) {
1144             more = wsize;
1145         } else if (more == (unsigned)(-1)) {
1146             /* Very unlikely, but possible on 16 bit machine if strstart == 0
1147              * and lookahead == 1 (input done one byte at time)
1148              */
1149             more--;
1150
1151         /* If the window is almost full and there is insufficient lookahead,
1152          * move the upper half to the lower one to make room in the upper half.
1153          */
1154         } else if (s->strstart >= wsize+MAX_DIST(s)) {
1155
1156             /* By the IN assertion, the window is not empty so we can't confuse
1157              * more == 0 with more == 64K on a 16 bit machine.
1158              */
1159             zmemcpy((charf *)s->window, (charf *)s->window+wsize,
1160                    (unsigned)wsize);
1161             s->match_start -= wsize;
1162             s->strstart    -= wsize; /* we now have strstart >= MAX_DIST */
1163
1164             s->block_start -= (long) wsize;
1165
1166             /* Slide the hash table (could be avoided with 32 bit values
1167                at the expense of memory usage):
1168              */
1169             n = s->hash_size;
1170             p = &s->head[n];
1171             do {
1172                 m = *--p;
1173                 *p = (Pos)(m >= wsize ? m-wsize : NIL);
1174             } while (--n);
1175
1176             n = wsize;
1177             p = &s->prev[n];
1178             do {
1179                 m = *--p;
1180                 *p = (Pos)(m >= wsize ? m-wsize : NIL);
1181                 /* If n is not on any hash chain, prev[n] is garbage but
1182                  * its value will never be used.
1183                  */
1184             } while (--n);
1185
1186             more += wsize;
1187         }
1188         if (s->strm->avail_in == 0) return;
1189
1190         /* If there was no sliding:
1191          *    strstart <= WSIZE+MAX_DIST-1 && lookahead <= MIN_LOOKAHEAD - 1 &&
1192          *    more == window_size - lookahead - strstart
1193          * => more >= window_size - (MIN_LOOKAHEAD-1 + WSIZE + MAX_DIST-1)
1194          * => more >= window_size - 2*WSIZE + 2
1195          * In the BIG_MEM or MMAP case (not yet supported),
1196          *   window_size == input_size + MIN_LOOKAHEAD  &&
1197          *   strstart + s->lookahead <= input_size => more >= MIN_LOOKAHEAD.
1198          * Otherwise, window_size == 2*WSIZE so more >= 2.
1199          * If there was sliding, more >= WSIZE. So in all cases, more >= 2.
1200          */
1201         Assert(more >= 2, "more < 2");
1202
1203         n = read_buf(s->strm, (charf *)s->window + s->strstart + s->lookahead,
1204                      more);
1205         s->lookahead += n;
1206
1207         /* Initialize the hash value now that we have some input: */
1208         if (s->lookahead >= MIN_MATCH) {
1209             s->ins_h = s->window[s->strstart];
1210             UPDATE_HASH(s, s->ins_h, s->window[s->strstart+1]);
1211 #if MIN_MATCH != 3
1212             Call UPDATE_HASH() MIN_MATCH-3 more times
1213 #endif
1214         }
1215         /* If the whole input has less than MIN_MATCH bytes, ins_h is garbage,
1216          * but this is not important since only literal bytes will be emitted.
1217          */
1218
1219     } while (s->lookahead < MIN_LOOKAHEAD && s->strm->avail_in != 0);
1220 }
1221
1222 /* ===========================================================================
1223  * Flush the current block, with given end-of-file flag.
1224  * IN assertion: strstart is set to the end of the current match.
1225  */
1226 #define FLUSH_BLOCK_ONLY(s, flush) { \
1227    ct_flush_block(s, (s->block_start >= 0L ? \
1228            (charf *)&s->window[(unsigned)s->block_start] : \
1229            (charf *)Z_NULL), (long)s->strstart - s->block_start, (flush)); \
1230    s->block_start = s->strstart; \
1231    flush_pending(s->strm); \
1232    Tracev((stderr,"[FLUSH]")); \
1233 }
1234
1235 /* Same but force premature exit if necessary. */
1236 #define FLUSH_BLOCK(s, flush) { \
1237    FLUSH_BLOCK_ONLY(s, flush); \
1238    if (s->strm->avail_out == 0) return 1; \
1239 }
1240
1241 /* ===========================================================================
1242  * Compress as much as possible from the input stream, return true if
1243  * processing was terminated prematurely (no more input or output space).
1244  * This function does not perform lazy evaluationof matches and inserts
1245  * new strings in the dictionary only for unmatched strings or for short
1246  * matches. It is used only for the fast compression options.
1247  */
1248 local int deflate_fast(s, flush)
1249     deflate_state *s;
1250     int flush;
1251 {
1252     IPos hash_head = NIL; /* head of the hash chain */
1253     int bflush;     /* set if current block must be flushed */
1254
1255     s->prev_length = MIN_MATCH-1;
1256
1257     for (;;) {
1258         /* Make sure that we always have enough lookahead, except
1259          * at the end of the input file. We need MAX_MATCH bytes
1260          * for the next match, plus MIN_MATCH bytes to insert the
1261          * string following the next match.
1262          */
1263         if (s->lookahead < MIN_LOOKAHEAD) {
1264             fill_window(s);
1265             if (s->lookahead < MIN_LOOKAHEAD && flush == Z_NO_FLUSH) return 1;
1266
1267             if (s->lookahead == 0) break; /* flush the current block */
1268         }
1269
1270         /* Insert the string window[strstart .. strstart+2] in the
1271          * dictionary, and set hash_head to the head of the hash chain:
1272          */
1273         if (s->lookahead >= MIN_MATCH) {
1274             INSERT_STRING(s, s->strstart, hash_head);
1275         }
1276
1277         /* Find the longest match, discarding those <= prev_length.
1278          * At this point we have always match_length < MIN_MATCH
1279          */
1280         if (hash_head != NIL && s->strstart - hash_head <= MAX_DIST(s)) {
1281             /* To simplify the code, we prevent matches with the string
1282              * of window index 0 (in particular we have to avoid a match
1283              * of the string with itself at the start of the input file).
1284              */
1285             if (s->strategy != Z_HUFFMAN_ONLY) {
1286                 s->match_length = longest_match (s, hash_head);
1287             }
1288             /* longest_match() sets match_start */
1289
1290             if (s->match_length > s->lookahead) s->match_length = s->lookahead;
1291         }
1292         if (s->match_length >= MIN_MATCH) {
1293             check_match(s, s->strstart, s->match_start, s->match_length);
1294
1295             bflush = ct_tally(s, s->strstart - s->match_start,
1296                               s->match_length - MIN_MATCH);
1297
1298             s->lookahead -= s->match_length;
1299
1300             /* Insert new strings in the hash table only if the match length
1301              * is not too large. This saves time but degrades compression.
1302              */
1303             if (s->match_length <= s->max_insert_length &&
1304                 s->lookahead >= MIN_MATCH) {
1305                 s->match_length--; /* string at strstart already in hash table */
1306                 do {
1307                     s->strstart++;
1308                     INSERT_STRING(s, s->strstart, hash_head);
1309                     /* strstart never exceeds WSIZE-MAX_MATCH, so there are
1310                      * always MIN_MATCH bytes ahead.
1311                      */
1312                 } while (--s->match_length != 0);
1313                 s->strstart++; 
1314             } else {
1315                 s->strstart += s->match_length;
1316                 s->match_length = 0;
1317                 s->ins_h = s->window[s->strstart];
1318                 UPDATE_HASH(s, s->ins_h, s->window[s->strstart+1]);
1319 #if MIN_MATCH != 3
1320                 Call UPDATE_HASH() MIN_MATCH-3 more times
1321 #endif
1322                 /* If lookahead < MIN_MATCH, ins_h is garbage, but it does not
1323                  * matter since it will be recomputed at next deflate call.
1324                  */
1325             }
1326         } else {
1327             /* No match, output a literal byte */
1328             Tracevv((stderr,"%c", s->window[s->strstart]));
1329             bflush = ct_tally (s, 0, s->window[s->strstart]);
1330             s->lookahead--;
1331             s->strstart++; 
1332         }
1333         if (bflush) FLUSH_BLOCK(s, Z_NO_FLUSH);
1334     }
1335     FLUSH_BLOCK(s, flush);
1336     return 0; /* normal exit */
1337 }
1338
1339 /* ===========================================================================
1340  * Same as above, but achieves better compression. We use a lazy
1341  * evaluation for matches: a match is finally adopted only if there is
1342  * no better match at the next window position.
1343  */
1344 local int deflate_slow(s, flush)
1345     deflate_state *s;
1346     int flush;
1347 {
1348     IPos hash_head = NIL;    /* head of hash chain */
1349     int bflush;              /* set if current block must be flushed */
1350
1351     /* Process the input block. */
1352     for (;;) {
1353         /* Make sure that we always have enough lookahead, except
1354          * at the end of the input file. We need MAX_MATCH bytes
1355          * for the next match, plus MIN_MATCH bytes to insert the
1356          * string following the next match.
1357          */
1358         if (s->lookahead < MIN_LOOKAHEAD) {
1359             fill_window(s);
1360             if (s->lookahead < MIN_LOOKAHEAD && flush == Z_NO_FLUSH) return 1;
1361
1362             if (s->lookahead == 0) break; /* flush the current block */
1363         }
1364
1365         /* Insert the string window[strstart .. strstart+2] in the
1366          * dictionary, and set hash_head to the head of the hash chain:
1367          */
1368         if (s->lookahead >= MIN_MATCH) {
1369             INSERT_STRING(s, s->strstart, hash_head);
1370         }
1371
1372         /* Find the longest match, discarding those <= prev_length.
1373          */
1374         s->prev_length = s->match_length, s->prev_match = s->match_start;
1375         s->match_length = MIN_MATCH-1;
1376
1377         if (hash_head != NIL && s->prev_length < s->max_lazy_match &&
1378             s->strstart - hash_head <= MAX_DIST(s)) {
1379             /* To simplify the code, we prevent matches with the string
1380              * of window index 0 (in particular we have to avoid a match
1381              * of the string with itself at the start of the input file).
1382              */
1383             if (s->strategy != Z_HUFFMAN_ONLY) {
1384                 s->match_length = longest_match (s, hash_head);
1385             }
1386             /* longest_match() sets match_start */
1387             if (s->match_length > s->lookahead) s->match_length = s->lookahead;
1388
1389             if (s->match_length <= 5 && (s->strategy == Z_FILTERED ||
1390                  (s->match_length == MIN_MATCH &&
1391                   s->strstart - s->match_start > TOO_FAR))) {
1392
1393                 /* If prev_match is also MIN_MATCH, match_start is garbage
1394                  * but we will ignore the current match anyway.
1395                  */
1396                 s->match_length = MIN_MATCH-1;
1397             }
1398         }
1399         /* If there was a match at the previous step and the current
1400          * match is not better, output the previous match:
1401          */
1402         if (s->prev_length >= MIN_MATCH && s->match_length <= s->prev_length) {
1403             uInt max_insert = s->strstart + s->lookahead - MIN_MATCH;
1404             /* Do not insert strings in hash table beyond this. */
1405
1406             check_match(s, s->strstart-1, s->prev_match, s->prev_length);
1407
1408             bflush = ct_tally(s, s->strstart -1 - s->prev_match,
1409                               s->prev_length - MIN_MATCH);
1410
1411             /* Insert in hash table all strings up to the end of the match.
1412              * strstart-1 and strstart are already inserted. If there is not
1413              * enough lookahead, the last two strings are not inserted in
1414              * the hash table.
1415              */
1416             s->lookahead -= s->prev_length-1;
1417             s->prev_length -= 2;
1418             do {
1419                 if (++s->strstart <= max_insert) {
1420                     INSERT_STRING(s, s->strstart, hash_head);
1421                 }
1422             } while (--s->prev_length != 0);
1423             s->match_available = 0;
1424             s->match_length = MIN_MATCH-1;
1425             s->strstart++;
1426
1427             if (bflush) FLUSH_BLOCK(s, Z_NO_FLUSH);
1428
1429         } else if (s->match_available) {
1430             /* If there was no match at the previous position, output a
1431              * single literal. If there was a match but the current match
1432              * is longer, truncate the previous match to a single literal.
1433              */
1434             Tracevv((stderr,"%c", s->window[s->strstart-1]));
1435             if (ct_tally (s, 0, s->window[s->strstart-1])) {
1436                 FLUSH_BLOCK_ONLY(s, Z_NO_FLUSH);
1437             }
1438             s->strstart++;
1439             s->lookahead--;
1440             if (s->strm->avail_out == 0) return 1;
1441         } else {
1442             /* There is no previous match to compare with, wait for
1443              * the next step to decide.
1444              */
1445             s->match_available = 1;
1446             s->strstart++;
1447             s->lookahead--;
1448         }
1449     }
1450     Assert (flush != Z_NO_FLUSH, "no flush?");
1451     if (s->match_available) {
1452         Tracevv((stderr,"%c", s->window[s->strstart-1]));
1453         ct_tally (s, 0, s->window[s->strstart-1]);
1454         s->match_available = 0;
1455     }
1456     FLUSH_BLOCK(s, flush);
1457     return 0;
1458 }
1459
1460
1461 /*+++++*/
1462 /* trees.c -- output deflated data using Huffman coding
1463  * Copyright (C) 1995 Jean-loup Gailly
1464  * For conditions of distribution and use, see copyright notice in zlib.h 
1465  */
1466
1467 /*
1468  *  ALGORITHM
1469  *
1470  *      The "deflation" process uses several Huffman trees. The more
1471  *      common source values are represented by shorter bit sequences.
1472  *
1473  *      Each code tree is stored in a compressed form which is itself
1474  * a Huffman encoding of the lengths of all the code strings (in
1475  * ascending order by source values).  The actual code strings are
1476  * reconstructed from the lengths in the inflate process, as described
1477  * in the deflate specification.
1478  *
1479  *  REFERENCES
1480  *
1481  *      Deutsch, L.P.,"'Deflate' Compressed Data Format Specification".
1482  *      Available in ftp.uu.net:/pub/archiving/zip/doc/deflate-1.1.doc
1483  *
1484  *      Storer, James A.
1485  *          Data Compression:  Methods and Theory, pp. 49-50.
1486  *          Computer Science Press, 1988.  ISBN 0-7167-8156-5.
1487  *
1488  *      Sedgewick, R.
1489  *          Algorithms, p290.
1490  *          Addison-Wesley, 1983. ISBN 0-201-06672-6.
1491  */
1492
1493 /* From: trees.c,v 1.5 1995/05/03 17:27:12 jloup Exp */
1494
1495 #ifdef DEBUG_ZLIB
1496 #  include <ctype.h>
1497 #endif
1498
1499 /* ===========================================================================
1500  * Constants
1501  */
1502
1503 #define MAX_BL_BITS 7
1504 /* Bit length codes must not exceed MAX_BL_BITS bits */
1505
1506 #define END_BLOCK 256
1507 /* end of block literal code */
1508
1509 #define REP_3_6      16
1510 /* repeat previous bit length 3-6 times (2 bits of repeat count) */
1511
1512 #define REPZ_3_10    17
1513 /* repeat a zero length 3-10 times  (3 bits of repeat count) */
1514
1515 #define REPZ_11_138  18
1516 /* repeat a zero length 11-138 times  (7 bits of repeat count) */
1517
1518 local int extra_lbits[LENGTH_CODES] /* extra bits for each length code */
1519    = {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};
1520
1521 local int extra_dbits[D_CODES] /* extra bits for each distance code */
1522    = {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};
1523
1524 local int extra_blbits[BL_CODES]/* extra bits for each bit length code */
1525    = {0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,2,3,7};
1526
1527 local uch bl_order[BL_CODES]
1528    = {16,17,18,0,8,7,9,6,10,5,11,4,12,3,13,2,14,1,15};
1529 /* The lengths of the bit length codes are sent in order of decreasing
1530  * probability, to avoid transmitting the lengths for unused bit length codes.
1531  */
1532
1533 #define Buf_size (8 * 2*sizeof(char))
1534 /* Number of bits used within bi_buf. (bi_buf might be implemented on
1535  * more than 16 bits on some systems.)
1536  */
1537
1538 /* ===========================================================================
1539  * Local data. These are initialized only once.
1540  * To do: initialize at compile time to be completely reentrant. ???
1541  */
1542
1543 local ct_data static_ltree[L_CODES+2];
1544 /* The static literal tree. Since the bit lengths are imposed, there is no
1545  * need for the L_CODES extra codes used during heap construction. However
1546  * The codes 286 and 287 are needed to build a canonical tree (see ct_init
1547  * below).
1548  */
1549
1550 local ct_data static_dtree[D_CODES];
1551 /* The static distance tree. (Actually a trivial tree since all codes use
1552  * 5 bits.)
1553  */
1554
1555 local uch dist_code[512];
1556 /* distance codes. The first 256 values correspond to the distances
1557  * 3 .. 258, the last 256 values correspond to the top 8 bits of
1558  * the 15 bit distances.
1559  */
1560
1561 local uch length_code[MAX_MATCH-MIN_MATCH+1];
1562 /* length code for each normalized match length (0 == MIN_MATCH) */
1563
1564 local int base_length[LENGTH_CODES];
1565 /* First normalized length for each code (0 = MIN_MATCH) */
1566
1567 local int base_dist[D_CODES];
1568 /* First normalized distance for each code (0 = distance of 1) */
1569
1570 struct static_tree_desc_s {
1571     ct_data *static_tree;        /* static tree or NULL */
1572     intf    *extra_bits;         /* extra bits for each code or NULL */
1573     int     extra_base;          /* base index for extra_bits */
1574     int     elems;               /* max number of elements in the tree */
1575     int     max_length;          /* max bit length for the codes */
1576 };
1577
1578 local static_tree_desc  static_l_desc =
1579 {static_ltree, extra_lbits, LITERALS+1, L_CODES, MAX_BITS};
1580
1581 local static_tree_desc  static_d_desc =
1582 {static_dtree, extra_dbits, 0,          D_CODES, MAX_BITS};
1583
1584 local static_tree_desc  static_bl_desc =
1585 {(ct_data *)0, extra_blbits, 0,      BL_CODES, MAX_BL_BITS};
1586
1587 /* ===========================================================================
1588  * Local (static) routines in this file.
1589  */
1590
1591 local void ct_static_init OF((void));
1592 local void init_block     OF((deflate_state *s));
1593 local void pqdownheap     OF((deflate_state *s, ct_data *tree, int k));
1594 local void gen_bitlen     OF((deflate_state *s, tree_desc *desc));
1595 local void gen_codes      OF((ct_data *tree, int max_code, ushf *bl_count));
1596 local void build_tree     OF((deflate_state *s, tree_desc *desc));
1597 local void scan_tree      OF((deflate_state *s, ct_data *tree, int max_code));
1598 local void send_tree      OF((deflate_state *s, ct_data *tree, int max_code));
1599 local int  build_bl_tree  OF((deflate_state *s));
1600 local void send_all_trees OF((deflate_state *s, int lcodes, int dcodes,
1601                               int blcodes));
1602 local void compress_block OF((deflate_state *s, ct_data *ltree,
1603                               ct_data *dtree));
1604 local void set_data_type  OF((deflate_state *s));
1605 local unsigned bi_reverse OF((unsigned value, int length));
1606 local void bi_windup      OF((deflate_state *s));
1607 local void bi_flush       OF((deflate_state *s));
1608 local void copy_block     OF((deflate_state *s, charf *buf, unsigned len,
1609                               int header));
1610
1611 #ifndef DEBUG_ZLIB
1612 #  define send_code(s, c, tree) send_bits(s, tree[c].Code, tree[c].Len)
1613    /* Send a code of the given tree. c and tree must not have side effects */
1614
1615 #else /* DEBUG_ZLIB */
1616 #  define send_code(s, c, tree) \
1617      { if (verbose>1) fprintf(stderr,"\ncd %3d ",(c)); \
1618        send_bits(s, tree[c].Code, tree[c].Len); }
1619 #endif
1620
1621 #define d_code(dist) \
1622    ((dist) < 256 ? dist_code[dist] : dist_code[256+((dist)>>7)])
1623 /* Mapping from a distance to a distance code. dist is the distance - 1 and
1624  * must not have side effects. dist_code[256] and dist_code[257] are never
1625  * used.
1626  */
1627
1628 /* ===========================================================================
1629  * Output a short LSB first on the stream.
1630  * IN assertion: there is enough room in pendingBuf.
1631  */
1632 #define put_short(s, w) { \
1633     put_byte(s, (uch)((w) & 0xff)); \
1634     put_byte(s, (uch)((ush)(w) >> 8)); \
1635 }
1636
1637 /* ===========================================================================
1638  * Send a value on a given number of bits.
1639  * IN assertion: length <= 16 and value fits in length bits.
1640  */
1641 #ifdef DEBUG_ZLIB
1642 local void send_bits      OF((deflate_state *s, int value, int length));
1643
1644 local void send_bits(s, value, length)
1645     deflate_state *s;
1646     int value;  /* value to send */
1647     int length; /* number of bits */
1648 {
1649     Tracev((stderr," l %2d v %4x ", length, value));
1650     Assert(length > 0 && length <= 15, "invalid length");
1651     s->bits_sent += (ulg)length;
1652
1653     /* If not enough room in bi_buf, use (valid) bits from bi_buf and
1654      * (16 - bi_valid) bits from value, leaving (width - (16-bi_valid))
1655      * unused bits in value.
1656      */
1657     if (s->bi_valid > (int)Buf_size - length) {
1658         s->bi_buf |= (value << s->bi_valid);
1659         put_short(s, s->bi_buf);
1660         s->bi_buf = (ush)value >> (Buf_size - s->bi_valid);
1661         s->bi_valid += length - Buf_size;
1662     } else {
1663         s->bi_buf |= value << s->bi_valid;
1664         s->bi_valid += length;
1665     }
1666 }
1667 #else /* !DEBUG_ZLIB */
1668
1669 #define send_bits(s, value, length) \
1670 { int len = length;\
1671   if (s->bi_valid > (int)Buf_size - len) {\
1672     int val = value;\
1673     s->bi_buf |= (val << s->bi_valid);\
1674     put_short(s, s->bi_buf);\
1675     s->bi_buf = (ush)val >> (Buf_size - s->bi_valid);\
1676     s->bi_valid += len - Buf_size;\
1677   } else {\
1678     s->bi_buf |= (value) << s->bi_valid;\
1679     s->bi_valid += len;\
1680   }\
1681 }
1682 #endif /* DEBUG_ZLIB */
1683
1684
1685 #define MAX(a,b) (a >= b ? a : b)
1686 /* the arguments must not have side effects */
1687
1688 /* ===========================================================================
1689  * Initialize the various 'constant' tables.
1690  * To do: do this at compile time.
1691  */
1692 local void ct_static_init()
1693 {
1694     int n;        /* iterates over tree elements */
1695     int bits;     /* bit counter */
1696     int length;   /* length value */
1697     int code;     /* code value */
1698     int dist;     /* distance index */
1699     ush bl_count[MAX_BITS+1];
1700     /* number of codes at each bit length for an optimal tree */
1701
1702     /* Initialize the mapping length (0..255) -> length code (0..28) */
1703     length = 0;
1704     for (code = 0; code < LENGTH_CODES-1; code++) {
1705         base_length[code] = length;
1706         for (n = 0; n < (1<<extra_lbits[code]); n++) {
1707             length_code[length++] = (uch)code;
1708         }
1709     }
1710     Assert (length == 256, "ct_static_init: length != 256");
1711     /* Note that the length 255 (match length 258) can be represented
1712      * in two different ways: code 284 + 5 bits or code 285, so we
1713      * overwrite length_code[255] to use the best encoding:
1714      */
1715     length_code[length-1] = (uch)code;
1716
1717     /* Initialize the mapping dist (0..32K) -> dist code (0..29) */
1718     dist = 0;
1719     for (code = 0 ; code < 16; code++) {
1720         base_dist[code] = dist;
1721         for (n = 0; n < (1<<extra_dbits[code]); n++) {
1722             dist_code[dist++] = (uch)code;
1723         }
1724     }
1725     Assert (dist == 256, "ct_static_init: dist != 256");
1726     dist >>= 7; /* from now on, all distances are divided by 128 */
1727     for ( ; code < D_CODES; code++) {
1728         base_dist[code] = dist << 7;
1729         for (n = 0; n < (1<<(extra_dbits[code]-7)); n++) {
1730             dist_code[256 + dist++] = (uch)code;
1731         }
1732     }
1733     Assert (dist == 256, "ct_static_init: 256+dist != 512");
1734
1735     /* Construct the codes of the static literal tree */
1736     for (bits = 0; bits <= MAX_BITS; bits++) bl_count[bits] = 0;
1737     n = 0;
1738     while (n <= 143) static_ltree[n++].Len = 8, bl_count[8]++;
1739     while (n <= 255) static_ltree[n++].Len = 9, bl_count[9]++;
1740     while (n <= 279) static_ltree[n++].Len = 7, bl_count[7]++;
1741     while (n <= 287) static_ltree[n++].Len = 8, bl_count[8]++;
1742     /* Codes 286 and 287 do not exist, but we must include them in the
1743      * tree construction to get a canonical Huffman tree (longest code
1744      * all ones)
1745      */
1746     gen_codes((ct_data *)static_ltree, L_CODES+1, bl_count);
1747
1748     /* The static distance tree is trivial: */
1749     for (n = 0; n < D_CODES; n++) {
1750         static_dtree[n].Len = 5;
1751         static_dtree[n].Code = bi_reverse(n, 5);
1752     }
1753 }
1754
1755 /* ===========================================================================
1756  * Initialize the tree data structures for a new zlib stream.
1757  */
1758 local void ct_init(s)
1759     deflate_state *s;
1760 {
1761     if (static_dtree[0].Len == 0) {
1762         ct_static_init();              /* To do: at compile time */
1763     }
1764
1765     s->compressed_len = 0L;
1766
1767     s->l_desc.dyn_tree = s->dyn_ltree;
1768     s->l_desc.stat_desc = &static_l_desc;
1769
1770     s->d_desc.dyn_tree = s->dyn_dtree;
1771     s->d_desc.stat_desc = &static_d_desc;
1772
1773     s->bl_desc.dyn_tree = s->bl_tree;
1774     s->bl_desc.stat_desc = &static_bl_desc;
1775
1776     s->bi_buf = 0;
1777     s->bi_valid = 0;
1778     s->last_eob_len = 8; /* enough lookahead for inflate */
1779 #ifdef DEBUG_ZLIB
1780     s->bits_sent = 0L;
1781 #endif
1782     s->blocks_in_packet = 0;
1783
1784     /* Initialize the first block of the first file: */
1785     init_block(s);
1786 }
1787
1788 /* ===========================================================================
1789  * Initialize a new block.
1790  */
1791 local void init_block(s)
1792     deflate_state *s;
1793 {
1794     int n; /* iterates over tree elements */
1795
1796     /* Initialize the trees. */
1797     for (n = 0; n < L_CODES;  n++) s->dyn_ltree[n].Freq = 0;
1798     for (n = 0; n < D_CODES;  n++) s->dyn_dtree[n].Freq = 0;
1799     for (n = 0; n < BL_CODES; n++) s->bl_tree[n].Freq = 0;
1800
1801     s->dyn_ltree[END_BLOCK].Freq = 1;
1802     s->opt_len = s->static_len = 0L;
1803     s->last_lit = s->matches = 0;
1804 }
1805
1806 #define SMALLEST 1
1807 /* Index within the heap array of least frequent node in the Huffman tree */
1808
1809
1810 /* ===========================================================================
1811  * Remove the smallest element from the heap and recreate the heap with
1812  * one less element. Updates heap and heap_len.
1813  */
1814 #define pqremove(s, tree, top) \
1815 {\
1816     top = s->heap[SMALLEST]; \
1817     s->heap[SMALLEST] = s->heap[s->heap_len--]; \
1818     pqdownheap(s, tree, SMALLEST); \
1819 }
1820
1821 /* ===========================================================================
1822  * Compares to subtrees, using the tree depth as tie breaker when
1823  * the subtrees have equal frequency. This minimizes the worst case length.
1824  */
1825 #define smaller(tree, n, m, depth) \
1826    (tree[n].Freq < tree[m].Freq || \
1827    (tree[n].Freq == tree[m].Freq && depth[n] <= depth[m]))
1828
1829 /* ===========================================================================
1830  * Restore the heap property by moving down the tree starting at node k,
1831  * exchanging a node with the smallest of its two sons if necessary, stopping
1832  * when the heap property is re-established (each father smaller than its
1833  * two sons).
1834  */
1835 local void pqdownheap(s, tree, k)
1836     deflate_state *s;
1837     ct_data *tree;  /* the tree to restore */
1838     int k;               /* node to move down */
1839 {
1840     int v = s->heap[k];
1841     int j = k << 1;  /* left son of k */
1842     while (j <= s->heap_len) {
1843         /* Set j to the smallest of the two sons: */
1844         if (j < s->heap_len &&
1845             smaller(tree, s->heap[j+1], s->heap[j], s->depth)) {
1846             j++;
1847         }
1848         /* Exit if v is smaller than both sons */
1849         if (smaller(tree, v, s->heap[j], s->depth)) break;
1850
1851         /* Exchange v with the smallest son */
1852         s->heap[k] = s->heap[j];  k = j;
1853
1854         /* And continue down the tree, setting j to the left son of k */
1855         j <<= 1;
1856     }
1857     s->heap[k] = v;
1858 }
1859
1860 /* ===========================================================================
1861  * Compute the optimal bit lengths for a tree and update the total bit length
1862  * for the current block.
1863  * IN assertion: the fields freq and dad are set, heap[heap_max] and
1864  *    above are the tree nodes sorted by increasing frequency.
1865  * OUT assertions: the field len is set to the optimal bit length, the
1866  *     array bl_count contains the frequencies for each bit length.
1867  *     The length opt_len is updated; static_len is also updated if stree is
1868  *     not null.
1869  */
1870 local void gen_bitlen(s, desc)
1871     deflate_state *s;
1872     tree_desc *desc;    /* the tree descriptor */
1873 {
1874     ct_data *tree  = desc->dyn_tree;
1875     int max_code   = desc->max_code;
1876     ct_data *stree = desc->stat_desc->static_tree;
1877     intf *extra    = desc->stat_desc->extra_bits;
1878     int base       = desc->stat_desc->extra_base;
1879     int max_length = desc->stat_desc->max_length;
1880     int h;              /* heap index */
1881     int n, m;           /* iterate over the tree elements */
1882     int bits;           /* bit length */
1883     int xbits;          /* extra bits */
1884     ush f;              /* frequency */
1885     int overflow = 0;   /* number of elements with bit length too large */
1886
1887     for (bits = 0; bits <= MAX_BITS; bits++) s->bl_count[bits] = 0;
1888
1889     /* In a first pass, compute the optimal bit lengths (which may
1890      * overflow in the case of the bit length tree).
1891      */
1892     tree[s->heap[s->heap_max]].Len = 0; /* root of the heap */
1893
1894     for (h = s->heap_max+1; h < HEAP_SIZE; h++) {
1895         n = s->heap[h];
1896         bits = tree[tree[n].Dad].Len + 1;
1897         if (bits > max_length) bits = max_length, overflow++;
1898         tree[n].Len = (ush)bits;
1899         /* We overwrite tree[n].Dad which is no longer needed */
1900
1901         if (n > max_code) continue; /* not a leaf node */
1902
1903         s->bl_count[bits]++;
1904         xbits = 0;
1905         if (n >= base) xbits = extra[n-base];
1906         f = tree[n].Freq;
1907         s->opt_len += (ulg)f * (bits + xbits);
1908         if (stree) s->static_len += (ulg)f * (stree[n].Len + xbits);
1909     }
1910     if (overflow == 0) return;
1911
1912     Trace((stderr,"\nbit length overflow\n"));
1913     /* This happens for example on obj2 and pic of the Calgary corpus */
1914
1915     /* Find the first bit length which could increase: */
1916     do {
1917         bits = max_length-1;
1918         while (s->bl_count[bits] == 0) bits--;
1919         s->bl_count[bits]--;      /* move one leaf down the tree */
1920         s->bl_count[bits+1] += 2; /* move one overflow item as its brother */
1921         s->bl_count[max_length]--;
1922         /* The brother of the overflow item also moves one step up,
1923          * but this does not affect bl_count[max_length]
1924          */
1925         overflow -= 2;
1926     } while (overflow > 0);
1927
1928     /* Now recompute all bit lengths, scanning in increasing frequency.
1929      * h is still equal to HEAP_SIZE. (It is simpler to reconstruct all
1930      * lengths instead of fixing only the wrong ones. This idea is taken
1931      * from 'ar' written by Haruhiko Okumura.)
1932      */
1933     for (bits = max_length; bits != 0; bits--) {
1934         n = s->bl_count[bits];
1935         while (n != 0) {
1936             m = s->heap[--h];
1937             if (m > max_code) continue;
1938             if (tree[m].Len != (unsigned) bits) {
1939                 Trace((stderr,"code %d bits %d->%d\n", m, tree[m].Len, bits));
1940                 s->opt_len += ((long)bits - (long)tree[m].Len)
1941                               *(long)tree[m].Freq;
1942                 tree[m].Len = (ush)bits;
1943             }
1944             n--;
1945         }
1946     }
1947 }
1948
1949 /* ===========================================================================
1950  * Generate the codes for a given tree and bit counts (which need not be
1951  * optimal).
1952  * IN assertion: the array bl_count contains the bit length statistics for
1953  * the given tree and the field len is set for all tree elements.
1954  * OUT assertion: the field code is set for all tree elements of non
1955  *     zero code length.
1956  */
1957 local void gen_codes (tree, max_code, bl_count)
1958     ct_data *tree;             /* the tree to decorate */
1959     int max_code;              /* largest code with non zero frequency */
1960     ushf *bl_count;            /* number of codes at each bit length */
1961 {
1962     ush next_code[MAX_BITS+1]; /* next code value for each bit length */
1963     ush code = 0;              /* running code value */
1964     int bits;                  /* bit index */
1965     int n;                     /* code index */
1966
1967     /* The distribution counts are first used to generate the code values
1968      * without bit reversal.
1969      */
1970     for (bits = 1; bits <= MAX_BITS; bits++) {
1971         next_code[bits] = code = (code + bl_count[bits-1]) << 1;
1972     }
1973     /* Check that the bit counts in bl_count are consistent. The last code
1974      * must be all ones.
1975      */
1976     Assert (code + bl_count[MAX_BITS]-1 == (1<<MAX_BITS)-1,
1977             "inconsistent bit counts");
1978     Tracev((stderr,"\ngen_codes: max_code %d ", max_code));
1979
1980     for (n = 0;  n <= max_code; n++) {
1981         int len = tree[n].Len;
1982         if (len == 0) continue;
1983         /* Now reverse the bits */
1984         tree[n].Code = bi_reverse(next_code[len]++, len);
1985
1986         Tracec(tree != static_ltree, (stderr,"\nn %3d %c l %2d c %4x (%x) ",
1987              n, (isgraph(n) ? n : ' '), len, tree[n].Code, next_code[len]-1));
1988     }
1989 }
1990
1991 /* ===========================================================================
1992  * Construct one Huffman tree and assigns the code bit strings and lengths.
1993  * Update the total bit length for the current block.
1994  * IN assertion: the field freq is set for all tree elements.
1995  * OUT assertions: the fields len and code are set to the optimal bit length
1996  *     and corresponding code. The length opt_len is updated; static_len is
1997  *     also updated if stree is not null. The field max_code is set.
1998  */
1999 local void build_tree(s, desc)
2000     deflate_state *s;
2001     tree_desc *desc; /* the tree descriptor */
2002 {
2003     ct_data *tree   = desc->dyn_tree;
2004     ct_data *stree  = desc->stat_desc->static_tree;
2005     int elems       = desc->stat_desc->elems;
2006     int n, m;          /* iterate over heap elements */
2007     int max_code = -1; /* largest code with non zero frequency */
2008     int node;          /* new node being created */
2009
2010     /* Construct the initial heap, with least frequent element in
2011      * heap[SMALLEST]. The sons of heap[n] are heap[2*n] and heap[2*n+1].
2012      * heap[0] is not used.
2013      */
2014     s->heap_len = 0, s->heap_max = HEAP_SIZE;
2015
2016     for (n = 0; n < elems; n++) {
2017         if (tree[n].Freq != 0) {
2018             s->heap[++(s->heap_len)] = max_code = n;
2019             s->depth[n] = 0;
2020         } else {
2021             tree[n].Len = 0;
2022         }
2023     }
2024
2025     /* The pkzip format requires that at least one distance code exists,
2026      * and that at least one bit should be sent even if there is only one
2027      * possible code. So to avoid special checks later on we force at least
2028      * two codes of non zero frequency.
2029      */
2030     while (s->heap_len < 2) {
2031         node = s->heap[++(s->heap_len)] = (max_code < 2 ? ++max_code : 0);
2032         tree[node].Freq = 1;
2033         s->depth[node] = 0;
2034         s->opt_len--; if (stree) s->static_len -= stree[node].Len;
2035         /* node is 0 or 1 so it does not have extra bits */
2036     }
2037     desc->max_code = max_code;
2038
2039     /* The elements heap[heap_len/2+1 .. heap_len] are leaves of the tree,
2040      * establish sub-heaps of increasing lengths:
2041      */
2042     for (n = s->heap_len/2; n >= 1; n--) pqdownheap(s, tree, n);
2043
2044     /* Construct the Huffman tree by repeatedly combining the least two
2045      * frequent nodes.
2046      */
2047     node = elems;              /* next internal node of the tree */
2048     do {
2049         pqremove(s, tree, n);  /* n = node of least frequency */
2050         m = s->heap[SMALLEST]; /* m = node of next least frequency */
2051
2052         s->heap[--(s->heap_max)] = n; /* keep the nodes sorted by frequency */
2053         s->heap[--(s->heap_max)] = m;
2054
2055         /* Create a new node father of n and m */
2056         tree[node].Freq = tree[n].Freq + tree[m].Freq;
2057         s->depth[node] = (uch) (MAX(s->depth[n], s->depth[m]) + 1);
2058         tree[n].Dad = tree[m].Dad = (ush)node;
2059 #ifdef DUMP_BL_TREE
2060         if (tree == s->bl_tree) {
2061             fprintf(stderr,"\nnode %d(%d), sons %d(%d) %d(%d)",
2062                     node, tree[node].Freq, n, tree[n].Freq, m, tree[m].Freq);
2063         }
2064 #endif
2065         /* and insert the new node in the heap */
2066         s->heap[SMALLEST] = node++;
2067         pqdownheap(s, tree, SMALLEST);
2068
2069     } while (s->heap_len >= 2);
2070
2071     s->heap[--(s->heap_max)] = s->heap[SMALLEST];
2072
2073     /* At this point, the fields freq and dad are set. We can now
2074      * generate the bit lengths.
2075      */
2076     gen_bitlen(s, (tree_desc *)desc);
2077
2078     /* The field len is now set, we can generate the bit codes */
2079     gen_codes ((ct_data *)tree, max_code, s->bl_count);
2080 }
2081
2082 /* ===========================================================================
2083  * Scan a literal or distance tree to determine the frequencies of the codes
2084  * in the bit length tree.
2085  */
2086 local void scan_tree (s, tree, max_code)
2087     deflate_state *s;
2088     ct_data *tree;   /* the tree to be scanned */
2089     int max_code;    /* and its largest code of non zero frequency */
2090 {
2091     int n;                     /* iterates over all tree elements */
2092     int prevlen = -1;          /* last emitted length */
2093     int curlen;                /* length of current code */
2094     int nextlen = tree[0].Len; /* length of next code */
2095     int count = 0;             /* repeat count of the current code */
2096     int max_count = 7;         /* max repeat count */
2097     int min_count = 4;         /* min repeat count */
2098
2099     if (nextlen == 0) max_count = 138, min_count = 3;
2100     tree[max_code+1].Len = (ush)0xffff; /* guard */
2101
2102     for (n = 0; n <= max_code; n++) {
2103         curlen = nextlen; nextlen = tree[n+1].Len;
2104         if (++count < max_count && curlen == nextlen) {
2105             continue;
2106         } else if (count < min_count) {
2107             s->bl_tree[curlen].Freq += count;
2108         } else if (curlen != 0) {
2109             if (curlen != prevlen) s->bl_tree[curlen].Freq++;
2110             s->bl_tree[REP_3_6].Freq++;
2111         } else if (count <= 10) {
2112             s->bl_tree[REPZ_3_10].Freq++;
2113         } else {
2114             s->bl_tree[REPZ_11_138].Freq++;
2115         }
2116         count = 0; prevlen = curlen;
2117         if (nextlen == 0) {
2118             max_count = 138, min_count = 3;
2119         } else if (curlen == nextlen) {
2120             max_count = 6, min_count = 3;
2121         } else {
2122             max_count = 7, min_count = 4;
2123         }
2124     }
2125 }
2126
2127 /* ===========================================================================
2128  * Send a literal or distance tree in compressed form, using the codes in
2129  * bl_tree.
2130  */
2131 local void send_tree (s, tree, max_code)
2132     deflate_state *s;
2133     ct_data *tree; /* the tree to be scanned */
2134     int max_code;       /* and its largest code of non zero frequency */
2135 {
2136     int n;                     /* iterates over all tree elements */
2137     int prevlen = -1;          /* last emitted length */
2138     int curlen;                /* length of current code */
2139     int nextlen = tree[0].Len; /* length of next code */
2140     int count = 0;             /* repeat count of the current code */
2141     int max_count = 7;         /* max repeat count */
2142     int min_count = 4;         /* min repeat count */
2143
2144     /* tree[max_code+1].Len = -1; */  /* guard already set */
2145     if (nextlen == 0) max_count = 138, min_count = 3;
2146
2147     for (n = 0; n <= max_code; n++) {
2148         curlen = nextlen; nextlen = tree[n+1].Len;
2149         if (++count < max_count && curlen == nextlen) {
2150             continue;
2151         } else if (count < min_count) {
2152             do { send_code(s, curlen, s->bl_tree); } while (--count != 0);
2153
2154         } else if (curlen != 0) {
2155             if (curlen != prevlen) {
2156                 send_code(s, curlen, s->bl_tree); count--;
2157             }
2158             Assert(count >= 3 && count <= 6, " 3_6?");
2159             send_code(s, REP_3_6, s->bl_tree); send_bits(s, count-3, 2);
2160
2161         } else if (count <= 10) {
2162             send_code(s, REPZ_3_10, s->bl_tree); send_bits(s, count-3, 3);
2163
2164         } else {
2165             send_code(s, REPZ_11_138, s->bl_tree); send_bits(s, count-11, 7);
2166         }
2167         count = 0; prevlen = curlen;
2168         if (nextlen == 0) {
2169             max_count = 138, min_count = 3;
2170         } else if (curlen == nextlen) {
2171             max_count = 6, min_count = 3;
2172         } else {
2173             max_count = 7, min_count = 4;
2174         }
2175     }
2176 }
2177
2178 /* ===========================================================================
2179  * Construct the Huffman tree for the bit lengths and return the index in
2180  * bl_order of the last bit length code to send.
2181  */
2182 local int build_bl_tree(s)
2183     deflate_state *s;
2184 {
2185     int max_blindex;  /* index of last bit length code of non zero freq */
2186
2187     /* Determine the bit length frequencies for literal and distance trees */
2188     scan_tree(s, (ct_data *)s->dyn_ltree, s->l_desc.max_code);
2189     scan_tree(s, (ct_data *)s->dyn_dtree, s->d_desc.max_code);
2190
2191     /* Build the bit length tree: */
2192     build_tree(s, (tree_desc *)(&(s->bl_desc)));
2193     /* opt_len now includes the length of the tree representations, except
2194      * the lengths of the bit lengths codes and the 5+5+4 bits for the counts.
2195      */
2196
2197     /* Determine the number of bit length codes to send. The pkzip format
2198      * requires that at least 4 bit length codes be sent. (appnote.txt says
2199      * 3 but the actual value used is 4.)
2200      */
2201     for (max_blindex = BL_CODES-1; max_blindex >= 3; max_blindex--) {
2202         if (s->bl_tree[bl_order[max_blindex]].Len != 0) break;
2203     }
2204     /* Update opt_len to include the bit length tree and counts */
2205     s->opt_len += 3*(max_blindex+1) + 5+5+4;
2206     Tracev((stderr, "\ndyn trees: dyn %ld, stat %ld",
2207             s->opt_len, s->static_len));
2208
2209     return max_blindex;
2210 }
2211
2212 /* ===========================================================================
2213  * Send the header for a block using dynamic Huffman trees: the counts, the
2214  * lengths of the bit length codes, the literal tree and the distance tree.
2215  * IN assertion: lcodes >= 257, dcodes >= 1, blcodes >= 4.
2216  */
2217 local void send_all_trees(s, lcodes, dcodes, blcodes)
2218     deflate_state *s;
2219     int lcodes, dcodes, blcodes; /* number of codes for each tree */
2220 {
2221     int rank;                    /* index in bl_order */
2222
2223     Assert (lcodes >= 257 && dcodes >= 1 && blcodes >= 4, "not enough codes");
2224     Assert (lcodes <= L_CODES && dcodes <= D_CODES && blcodes <= BL_CODES,
2225             "too many codes");
2226     Tracev((stderr, "\nbl counts: "));
2227     send_bits(s, lcodes-257, 5); /* not +255 as stated in appnote.txt */
2228     send_bits(s, dcodes-1,   5);
2229     send_bits(s, blcodes-4,  4); /* not -3 as stated in appnote.txt */
2230     for (rank = 0; rank < blcodes; rank++) {
2231         Tracev((stderr, "\nbl code %2d ", bl_order[rank]));
2232         send_bits(s, s->bl_tree[bl_order[rank]].Len, 3);
2233     }
2234     Tracev((stderr, "\nbl tree: sent %ld", s->bits_sent));
2235
2236     send_tree(s, (ct_data *)s->dyn_ltree, lcodes-1); /* literal tree */
2237     Tracev((stderr, "\nlit tree: sent %ld", s->bits_sent));
2238
2239     send_tree(s, (ct_data *)s->dyn_dtree, dcodes-1); /* distance tree */
2240     Tracev((stderr, "\ndist tree: sent %ld", s->bits_sent));
2241 }
2242
2243 /* ===========================================================================
2244  * Send a stored block
2245  */
2246 local void ct_stored_block(s, buf, stored_len, eof)
2247     deflate_state *s;
2248     charf *buf;       /* input block */
2249     ulg stored_len;   /* length of input block */
2250     int eof;          /* true if this is the last block for a file */
2251 {
2252     send_bits(s, (STORED_BLOCK<<1)+eof, 3);  /* send block type */
2253     s->compressed_len = (s->compressed_len + 3 + 7) & ~7L;
2254     s->compressed_len += (stored_len + 4) << 3;
2255
2256     copy_block(s, buf, (unsigned)stored_len, 1); /* with header */
2257 }
2258
2259 /* Send just the `stored block' type code without any length bytes or data.
2260  */
2261 local void ct_stored_type_only(s)
2262     deflate_state *s;
2263 {
2264     send_bits(s, (STORED_BLOCK << 1), 3);
2265     bi_windup(s);
2266     s->compressed_len = (s->compressed_len + 3) & ~7L;
2267 }
2268
2269
2270 /* ===========================================================================
2271  * Send one empty static block to give enough lookahead for inflate.
2272  * This takes 10 bits, of which 7 may remain in the bit buffer.
2273  * The current inflate code requires 9 bits of lookahead. If the EOB
2274  * code for the previous block was coded on 5 bits or less, inflate
2275  * may have only 5+3 bits of lookahead to decode this EOB.
2276  * (There are no problems if the previous block is stored or fixed.)
2277  */
2278 local void ct_align(s)
2279     deflate_state *s;
2280 {
2281     send_bits(s, STATIC_TREES<<1, 3);
2282     send_code(s, END_BLOCK, static_ltree);
2283     s->compressed_len += 10L; /* 3 for block type, 7 for EOB */
2284     bi_flush(s);
2285     /* Of the 10 bits for the empty block, we have already sent
2286      * (10 - bi_valid) bits. The lookahead for the EOB of the previous
2287      * block was thus its length plus what we have just sent.
2288      */
2289     if (s->last_eob_len + 10 - s->bi_valid < 9) {
2290         send_bits(s, STATIC_TREES<<1, 3);
2291         send_code(s, END_BLOCK, static_ltree);
2292         s->compressed_len += 10L;
2293         bi_flush(s);
2294     }
2295     s->last_eob_len = 7;
2296 }
2297
2298 /* ===========================================================================
2299  * Determine the best encoding for the current block: dynamic trees, static
2300  * trees or store, and output the encoded block to the zip file. This function
2301  * returns the total compressed length for the file so far.
2302  */
2303 local ulg ct_flush_block(s, buf, stored_len, flush)
2304     deflate_state *s;
2305     charf *buf;       /* input block, or NULL if too old */
2306     ulg stored_len;   /* length of input block */
2307     int flush;        /* Z_FINISH if this is the last block for a file */
2308 {
2309     ulg opt_lenb, static_lenb; /* opt_len and static_len in bytes */
2310     int max_blindex;  /* index of last bit length code of non zero freq */
2311     int eof = flush == Z_FINISH;
2312
2313     ++s->blocks_in_packet;
2314
2315     /* Check if the file is ascii or binary */
2316     if (s->data_type == UNKNOWN) set_data_type(s);
2317
2318     /* Construct the literal and distance trees */
2319     build_tree(s, (tree_desc *)(&(s->l_desc)));
2320     Tracev((stderr, "\nlit data: dyn %ld, stat %ld", s->opt_len,
2321             s->static_len));
2322
2323     build_tree(s, (tree_desc *)(&(s->d_desc)));
2324     Tracev((stderr, "\ndist data: dyn %ld, stat %ld", s->opt_len,
2325             s->static_len));
2326     /* At this point, opt_len and static_len are the total bit lengths of
2327      * the compressed block data, excluding the tree representations.
2328      */
2329
2330     /* Build the bit length tree for the above two trees, and get the index
2331      * in bl_order of the last bit length code to send.
2332      */
2333     max_blindex = build_bl_tree(s);
2334
2335     /* Determine the best encoding. Compute first the block length in bytes */
2336     opt_lenb = (s->opt_len+3+7)>>3;
2337     static_lenb = (s->static_len+3+7)>>3;
2338
2339     Tracev((stderr, "\nopt %lu(%lu) stat %lu(%lu) stored %lu lit %u ",
2340             opt_lenb, s->opt_len, static_lenb, s->static_len, stored_len,
2341             s->last_lit));
2342
2343     if (static_lenb <= opt_lenb) opt_lenb = static_lenb;
2344
2345     /* If compression failed and this is the first and last block,
2346      * and if the .zip file can be seeked (to rewrite the local header),
2347      * the whole file is transformed into a stored file:
2348      */
2349 #ifdef STORED_FILE_OK
2350 #  ifdef FORCE_STORED_FILE
2351     if (eof && compressed_len == 0L) /* force stored file */
2352 #  else
2353     if (stored_len <= opt_lenb && eof && s->compressed_len==0L && seekable())
2354 #  endif
2355     {
2356         /* Since LIT_BUFSIZE <= 2*WSIZE, the input data must be there: */
2357         if (buf == (charf*)0) error ("block vanished");
2358
2359         copy_block(buf, (unsigned)stored_len, 0); /* without header */
2360         s->compressed_len = stored_len << 3;
2361         s->method = STORED;
2362     } else
2363 #endif /* STORED_FILE_OK */
2364
2365     /* For Z_PACKET_FLUSH, if we don't achieve the required minimum
2366      * compression, and this block contains all the data since the last
2367      * time we used Z_PACKET_FLUSH, then just omit this block completely
2368      * from the output.
2369      */
2370     if (flush == Z_PACKET_FLUSH && s->blocks_in_packet == 1
2371         && opt_lenb > stored_len - s->minCompr) {
2372         s->blocks_in_packet = 0;
2373         /* output nothing */
2374     } else
2375
2376 #ifdef FORCE_STORED
2377     if (buf != (char*)0) /* force stored block */
2378 #else
2379     if (stored_len+4 <= opt_lenb && buf != (char*)0)
2380                        /* 4: two words for the lengths */
2381 #endif
2382     {
2383         /* The test buf != NULL is only necessary if LIT_BUFSIZE > WSIZE.
2384          * Otherwise we can't have processed more than WSIZE input bytes since
2385          * the last block flush, because compression would have been
2386          * successful. If LIT_BUFSIZE <= WSIZE, it is never too late to
2387          * transform a block into a stored block.
2388          */
2389         ct_stored_block(s, buf, stored_len, eof);
2390     } else
2391
2392 #ifdef FORCE_STATIC
2393     if (static_lenb >= 0) /* force static trees */
2394 #else
2395     if (static_lenb == opt_lenb)
2396 #endif
2397     {
2398         send_bits(s, (STATIC_TREES<<1)+eof, 3);
2399         compress_block(s, (ct_data *)static_ltree, (ct_data *)static_dtree);
2400         s->compressed_len += 3 + s->static_len;
2401     } else {
2402         send_bits(s, (DYN_TREES<<1)+eof, 3);
2403         send_all_trees(s, s->l_desc.max_code+1, s->d_desc.max_code+1,
2404                        max_blindex+1);
2405         compress_block(s, (ct_data *)s->dyn_ltree, (ct_data *)s->dyn_dtree);
2406         s->compressed_len += 3 + s->opt_len;
2407     }
2408     Assert (s->compressed_len == s->bits_sent, "bad compressed size");
2409     init_block(s);
2410
2411     if (eof) {
2412         bi_windup(s);
2413         s->compressed_len += 7;  /* align on byte boundary */
2414     }
2415     Tracev((stderr,"\ncomprlen %lu(%lu) ", s->compressed_len>>3,
2416            s->compressed_len-7*eof));
2417
2418     return s->compressed_len >> 3;
2419 }
2420
2421 /* ===========================================================================
2422  * Save the match info and tally the frequency counts. Return true if
2423  * the current block must be flushed.
2424  */
2425 local int ct_tally (s, dist, lc)
2426     deflate_state *s;
2427     int dist;  /* distance of matched string */
2428     int lc;    /* match length-MIN_MATCH or unmatched char (if dist==0) */
2429 {
2430     s->d_buf[s->last_lit] = (ush)dist;
2431     s->l_buf[s->last_lit++] = (uch)lc;
2432     if (dist == 0) {
2433         /* lc is the unmatched char */
2434         s->dyn_ltree[lc].Freq++;
2435     } else {
2436         s->matches++;
2437         /* Here, lc is the match length - MIN_MATCH */
2438         dist--;             /* dist = match distance - 1 */
2439         Assert((ush)dist < (ush)MAX_DIST(s) &&
2440                (ush)lc <= (ush)(MAX_MATCH-MIN_MATCH) &&
2441                (ush)d_code(dist) < (ush)D_CODES,  "ct_tally: bad match");
2442
2443         s->dyn_ltree[length_code[lc]+LITERALS+1].Freq++;
2444         s->dyn_dtree[d_code(dist)].Freq++;
2445     }
2446
2447     /* Try to guess if it is profitable to stop the current block here */
2448     if (s->level > 2 && (s->last_lit & 0xfff) == 0) {
2449         /* Compute an upper bound for the compressed length */
2450         ulg out_length = (ulg)s->last_lit*8L;
2451         ulg in_length = (ulg)s->strstart - s->block_start;
2452         int dcode;
2453         for (dcode = 0; dcode < D_CODES; dcode++) {
2454             out_length += (ulg)s->dyn_dtree[dcode].Freq *
2455                 (5L+extra_dbits[dcode]);
2456         }
2457         out_length >>= 3;
2458         Tracev((stderr,"\nlast_lit %u, in %ld, out ~%ld(%ld%%) ",
2459                s->last_lit, in_length, out_length,
2460                100L - out_length*100L/in_length));
2461         if (s->matches < s->last_lit/2 && out_length < in_length/2) return 1;
2462     }
2463     return (s->last_lit == s->lit_bufsize-1);
2464     /* We avoid equality with lit_bufsize because of wraparound at 64K
2465      * on 16 bit machines and because stored blocks are restricted to
2466      * 64K-1 bytes.
2467      */
2468 }
2469
2470 /* ===========================================================================
2471  * Send the block data compressed using the given Huffman trees
2472  */
2473 local void compress_block(s, ltree, dtree)
2474     deflate_state *s;
2475     ct_data *ltree; /* literal tree */
2476     ct_data *dtree; /* distance tree */
2477 {
2478     unsigned dist;      /* distance of matched string */
2479     int lc;             /* match length or unmatched char (if dist == 0) */
2480     unsigned lx = 0;    /* running index in l_buf */
2481     unsigned code;      /* the code to send */
2482     int extra;          /* number of extra bits to send */
2483
2484     if (s->last_lit != 0) do {
2485         dist = s->d_buf[lx];
2486         lc = s->l_buf[lx++];
2487         if (dist == 0) {
2488             send_code(s, lc, ltree); /* send a literal byte */
2489             Tracecv(isgraph(lc), (stderr," '%c' ", lc));
2490         } else {
2491             /* Here, lc is the match length - MIN_MATCH */
2492             code = length_code[lc];
2493             send_code(s, code+LITERALS+1, ltree); /* send the length code */
2494             extra = extra_lbits[code];
2495             if (extra != 0) {
2496                 lc -= base_length[code];
2497                 send_bits(s, lc, extra);       /* send the extra length bits */
2498             }
2499             dist--; /* dist is now the match distance - 1 */
2500             code = d_code(dist);
2501             Assert (code < D_CODES, "bad d_code");
2502
2503             send_code(s, code, dtree);       /* send the distance code */
2504             extra = extra_dbits[code];
2505             if (extra != 0) {
2506                 dist -= base_dist[code];
2507                 send_bits(s, dist, extra);   /* send the extra distance bits */
2508             }
2509         } /* literal or match pair ? */
2510
2511         /* Check that the overlay between pending_buf and d_buf+l_buf is ok: */
2512         Assert(s->pending < s->lit_bufsize + 2*lx, "pendingBuf overflow");
2513
2514     } while (lx < s->last_lit);
2515
2516     send_code(s, END_BLOCK, ltree);
2517     s->last_eob_len = ltree[END_BLOCK].Len;
2518 }
2519
2520 /* ===========================================================================
2521  * Set the data type to ASCII or Z_BINARY, using a crude approximation:
2522  * binary if more than 20% of the bytes are <= 6 or >= 128, ascii otherwise.
2523  * IN assertion: the fields freq of dyn_ltree are set and the total of all
2524  * frequencies does not exceed 64K (to fit in an int on 16 bit machines).
2525  */
2526 local void set_data_type(s)
2527     deflate_state *s;
2528 {
2529     int n = 0;
2530     unsigned ascii_freq = 0;
2531     unsigned bin_freq = 0;
2532     while (n < 7)        bin_freq += s->dyn_ltree[n++].Freq;
2533     while (n < 128)    ascii_freq += s->dyn_ltree[n++].Freq;
2534     while (n < LITERALS) bin_freq += s->dyn_ltree[n++].Freq;
2535     s->data_type = (Byte)(bin_freq > (ascii_freq >> 2) ? Z_BINARY : ASCII);
2536 }
2537
2538 /* ===========================================================================
2539  * Reverse the first len bits of a code, using straightforward code (a faster
2540  * method would use a table)
2541  * IN assertion: 1 <= len <= 15
2542  */
2543 local unsigned bi_reverse(code, len)
2544     unsigned code; /* the value to invert */
2545     int len;       /* its bit length */
2546 {
2547     register unsigned res = 0;
2548     do {
2549         res |= code & 1;
2550         code >>= 1, res <<= 1;
2551     } while (--len > 0);
2552     return res >> 1;
2553 }
2554
2555 /* ===========================================================================
2556  * Flush the bit buffer, keeping at most 7 bits in it.
2557  */
2558 local void bi_flush(s)
2559     deflate_state *s;
2560 {
2561     if (s->bi_valid == 16) {
2562         put_short(s, s->bi_buf);
2563         s->bi_buf = 0;
2564         s->bi_valid = 0;
2565     } else if (s->bi_valid >= 8) {
2566         put_byte(s, (Byte)s->bi_buf);
2567         s->bi_buf >>= 8;
2568         s->bi_valid -= 8;
2569     }
2570 }
2571
2572 /* ===========================================================================
2573  * Flush the bit buffer and align the output on a byte boundary
2574  */
2575 local void bi_windup(s)
2576     deflate_state *s;
2577 {
2578     if (s->bi_valid > 8) {
2579         put_short(s, s->bi_buf);
2580     } else if (s->bi_valid > 0) {
2581         put_byte(s, (Byte)s->bi_buf);
2582     }
2583     s->bi_buf = 0;
2584     s->bi_valid = 0;
2585 #ifdef DEBUG_ZLIB
2586     s->bits_sent = (s->bits_sent+7) & ~7;
2587 #endif
2588 }
2589
2590 /* ===========================================================================
2591  * Copy a stored block, storing first the length and its
2592  * one's complement if requested.
2593  */
2594 local void copy_block(s, buf, len, header)
2595     deflate_state *s;
2596     charf    *buf;    /* the input data */
2597     unsigned len;     /* its length */
2598     int      header;  /* true if block header must be written */
2599 {
2600     bi_windup(s);        /* align on byte boundary */
2601     s->last_eob_len = 8; /* enough lookahead for inflate */
2602
2603     if (header) {
2604         put_short(s, (ush)len);   
2605         put_short(s, (ush)~len);
2606 #ifdef DEBUG_ZLIB
2607         s->bits_sent += 2*16;
2608 #endif
2609     }
2610 #ifdef DEBUG_ZLIB
2611     s->bits_sent += (ulg)len<<3;
2612 #endif
2613     while (len--) {
2614         put_byte(s, *buf++);
2615     }
2616 }
2617
2618
2619 /*+++++*/
2620 /* infblock.h -- header to use infblock.c
2621  * Copyright (C) 1995 Mark Adler
2622  * For conditions of distribution and use, see copyright notice in zlib.h 
2623  */
2624
2625 /* WARNING: this file should *not* be used by applications. It is
2626    part of the implementation of the compression library and is
2627    subject to change. Applications should only use zlib.h.
2628  */
2629
2630 struct inflate_blocks_state;
2631 typedef struct inflate_blocks_state FAR inflate_blocks_statef;
2632
2633 local inflate_blocks_statef * inflate_blocks_new OF((
2634     z_stream *z,
2635     check_func c,               /* check function */
2636     uInt w));                   /* window size */
2637
2638 local int inflate_blocks OF((
2639     inflate_blocks_statef *,
2640     z_stream *,
2641     int));                      /* initial return code */
2642
2643 local void inflate_blocks_reset OF((
2644     inflate_blocks_statef *,
2645     z_stream *,
2646     uLongf *));                  /* check value on output */
2647
2648 local int inflate_blocks_free OF((
2649     inflate_blocks_statef *,
2650     z_stream *,
2651     uLongf *));                  /* check value on output */
2652
2653 local int inflate_addhistory OF((
2654     inflate_blocks_statef *,
2655     z_stream *));
2656
2657 local int inflate_packet_flush OF((
2658     inflate_blocks_statef *));
2659
2660 /*+++++*/
2661 /* inftrees.h -- header to use inftrees.c
2662  * Copyright (C) 1995 Mark Adler
2663  * For conditions of distribution and use, see copyright notice in zlib.h 
2664  */
2665
2666 /* WARNING: this file should *not* be used by applications. It is
2667    part of the implementation of the compression library and is
2668    subject to change. Applications should only use zlib.h.
2669  */
2670
2671 /* Huffman code lookup table entry--this entry is four bytes for machines
2672    that have 16-bit pointers (e.g. PC's in the small or medium model). */
2673
2674 typedef struct inflate_huft_s FAR inflate_huft;
2675
2676 struct inflate_huft_s {
2677   union {
2678     struct {
2679       Byte Exop;        /* number of extra bits or operation */
2680       Byte Bits;        /* number of bits in this code or subcode */
2681     } what;
2682     uInt Nalloc;        /* number of these allocated here */
2683     Bytef *pad;         /* pad structure to a power of 2 (4 bytes for */
2684   } word;               /*  16-bit, 8 bytes for 32-bit machines) */
2685   union {
2686     uInt Base;          /* literal, length base, or distance base */
2687     inflate_huft *Next; /* pointer to next level of table */
2688   } more;
2689 };
2690
2691 #ifdef DEBUG_ZLIB
2692   local uInt inflate_hufts;
2693 #endif
2694
2695 local int inflate_trees_bits OF((
2696     uIntf *,                    /* 19 code lengths */
2697     uIntf *,                    /* bits tree desired/actual depth */
2698     inflate_huft * FAR *,       /* bits tree result */
2699     z_stream *));               /* for zalloc, zfree functions */
2700
2701 local int inflate_trees_dynamic OF((
2702     uInt,                       /* number of literal/length codes */
2703     uInt,                       /* number of distance codes */
2704     uIntf *,                    /* that many (total) code lengths */
2705     uIntf *,                    /* literal desired/actual bit depth */
2706     uIntf *,                    /* distance desired/actual bit depth */
2707     inflate_huft * FAR *,       /* literal/length tree result */
2708     inflate_huft * FAR *,       /* distance tree result */
2709     z_stream *));               /* for zalloc, zfree functions */
2710
2711 local int inflate_trees_fixed OF((
2712     uIntf *,                    /* literal desired/actual bit depth */
2713     uIntf *,                    /* distance desired/actual bit depth */
2714     inflate_huft * FAR *,       /* literal/length tree result */
2715     inflate_huft * FAR *));     /* distance tree result */
2716
2717 local int inflate_trees_free OF((
2718     inflate_huft *,             /* tables to free */
2719     z_stream *));               /* for zfree function */
2720
2721
2722 /*+++++*/
2723 /* infcodes.h -- header to use infcodes.c
2724  * Copyright (C) 1995 Mark Adler
2725  * For conditions of distribution and use, see copyright notice in zlib.h 
2726  */
2727
2728 /* WARNING: this file should *not* be used by applications. It is
2729    part of the implementation of the compression library and is
2730    subject to change. Applications should only use zlib.h.
2731  */
2732
2733 struct inflate_codes_state;
2734 typedef struct inflate_codes_state FAR inflate_codes_statef;
2735
2736 local inflate_codes_statef *inflate_codes_new OF((
2737     uInt, uInt,
2738     inflate_huft *, inflate_huft *,
2739     z_stream *));
2740
2741 local int inflate_codes OF((
2742     inflate_blocks_statef *,
2743     z_stream *,
2744     int));
2745
2746 local void inflate_codes_free OF((
2747     inflate_codes_statef *,
2748     z_stream *));
2749
2750
2751 /*+++++*/
2752 /* inflate.c -- zlib interface to inflate modules
2753  * Copyright (C) 1995 Mark Adler
2754  * For conditions of distribution and use, see copyright notice in zlib.h 
2755  */
2756
2757 /* inflate private state */
2758 struct internal_state {
2759
2760   /* mode */
2761   enum {
2762       METHOD,   /* waiting for method byte */
2763       FLAG,     /* waiting for flag byte */
2764       BLOCKS,   /* decompressing blocks */
2765       CHECK4,   /* four check bytes to go */
2766       CHECK3,   /* three check bytes to go */
2767       CHECK2,   /* two check bytes to go */
2768       CHECK1,   /* one check byte to go */
2769       DONE,     /* finished check, done */
2770       BAD}      /* got an error--stay here */
2771     mode;               /* current inflate mode */
2772
2773   /* mode dependent information */
2774   union {
2775     uInt method;        /* if FLAGS, method byte */
2776     struct {
2777       uLong was;                /* computed check value */
2778       uLong need;               /* stream check value */
2779     } check;            /* if CHECK, check values to compare */
2780     uInt marker;        /* if BAD, inflateSync's marker bytes count */
2781   } sub;        /* submode */
2782
2783   /* mode independent information */
2784   int  nowrap;          /* flag for no wrapper */
2785   uInt wbits;           /* log2(window size)  (8..15, defaults to 15) */
2786   inflate_blocks_statef 
2787     *blocks;            /* current inflate_blocks state */
2788
2789 };
2790
2791
2792 int inflateReset(z)
2793 z_stream *z;
2794 {
2795   uLong c;
2796
2797   if (z == Z_NULL || z->state == Z_NULL)
2798     return Z_STREAM_ERROR;
2799   z->total_in = z->total_out = 0;
2800   z->msg = Z_NULL;
2801   z->state->mode = z->state->nowrap ? BLOCKS : METHOD;
2802   inflate_blocks_reset(z->state->blocks, z, &c);
2803   Trace((stderr, "inflate: reset\n"));
2804   return Z_OK;
2805 }
2806
2807
2808 int inflateEnd(z)
2809 z_stream *z;
2810 {
2811   uLong c;
2812
2813   if (z == Z_NULL || z->state == Z_NULL || z->zfree == Z_NULL)
2814     return Z_STREAM_ERROR;
2815   if (z->state->blocks != Z_NULL)
2816     inflate_blocks_free(z->state->blocks, z, &c);
2817   ZFREE(z, z->state, sizeof(struct internal_state));
2818   z->state = Z_NULL;
2819   Trace((stderr, "inflate: end\n"));
2820   return Z_OK;
2821 }
2822
2823
2824 int inflateInit2(z, w)
2825 z_stream *z;
2826 int w;
2827 {
2828   /* initialize state */
2829   if (z == Z_NULL)
2830     return Z_STREAM_ERROR;
2831 /*  if (z->zalloc == Z_NULL) z->zalloc = zcalloc; */
2832 /*  if (z->zfree == Z_NULL) z->zfree = zcfree; */
2833   if ((z->state = (struct internal_state FAR *)
2834        ZALLOC_INIT(z,1,sizeof(struct internal_state))) == Z_NULL)
2835     return Z_MEM_ERROR;
2836   z->state->blocks = Z_NULL;
2837
2838   /* handle undocumented nowrap option (no zlib header or check) */
2839   z->state->nowrap = 0;
2840   if (w < 0)
2841   {
2842     w = - w;
2843     z->state->nowrap = 1;
2844   }
2845
2846   /* set window size */
2847   if (w < 8 || w > 15)
2848   {
2849     inflateEnd(z);
2850     return Z_STREAM_ERROR;
2851   }
2852   z->state->wbits = (uInt)w;
2853
2854   /* create inflate_blocks state */
2855   if ((z->state->blocks =
2856        inflate_blocks_new(z, z->state->nowrap ? Z_NULL : adler32, 1 << w))
2857       == Z_NULL)
2858   {
2859     inflateEnd(z);
2860     return Z_MEM_ERROR;
2861   }
2862   Trace((stderr, "inflate: allocated\n"));
2863
2864   /* reset state */
2865   inflateReset(z);
2866   return Z_OK;
2867 }
2868
2869
2870 int inflateInit(z)
2871 z_stream *z;
2872 {
2873   return inflateInit2(z, DEF_WBITS);
2874 }
2875
2876
2877 #define NEEDBYTE {if(z->avail_in==0)goto empty;r=Z_OK;}
2878 #define NEXTBYTE (z->avail_in--,z->total_in++,*z->next_in++)
2879
2880 int inflate(z, f)
2881 z_stream *z;
2882 int f;
2883 {
2884   int r;
2885   uInt b;
2886
2887   if (z == Z_NULL || z->next_in == Z_NULL)
2888     return Z_STREAM_ERROR;
2889   r = Z_BUF_ERROR;
2890   while (1) switch (z->state->mode)
2891   {
2892     case METHOD:
2893       NEEDBYTE
2894       if (((z->state->sub.method = NEXTBYTE) & 0xf) != DEFLATED)
2895       {
2896         z->state->mode = BAD;
2897         z->msg = "unknown compression method";
2898         z->state->sub.marker = 5;       /* can't try inflateSync */
2899         break;
2900       }
2901       if ((z->state->sub.method >> 4) + 8 > z->state->wbits)
2902       {
2903         z->state->mode = BAD;
2904         z->msg = "invalid window size";
2905         z->state->sub.marker = 5;       /* can't try inflateSync */
2906         break;
2907       }
2908       z->state->mode = FLAG;
2909     case FLAG:
2910       NEEDBYTE
2911       if ((b = NEXTBYTE) & 0x20)
2912       {
2913         z->state->mode = BAD;
2914         z->msg = "invalid reserved bit";
2915         z->state->sub.marker = 5;       /* can't try inflateSync */
2916         break;
2917       }
2918       if (((z->state->sub.method << 8) + b) % 31)
2919       {
2920         z->state->mode = BAD;
2921         z->msg = "incorrect header check";
2922         z->state->sub.marker = 5;       /* can't try inflateSync */
2923         break;
2924       }
2925       Trace((stderr, "inflate: zlib header ok\n"));
2926       z->state->mode = BLOCKS;
2927     case BLOCKS:
2928       r = inflate_blocks(z->state->blocks, z, r);
2929       if (f == Z_PACKET_FLUSH && z->avail_in == 0 && z->avail_out != 0)
2930           r = inflate_packet_flush(z->state->blocks);
2931       if (r == Z_DATA_ERROR)
2932       {
2933         z->state->mode = BAD;
2934         z->state->sub.marker = 0;       /* can try inflateSync */
2935         break;
2936       }
2937       if (r != Z_STREAM_END)
2938         return r;
2939       r = Z_OK;
2940       inflate_blocks_reset(z->state->blocks, z, &z->state->sub.check.was);
2941       if (z->state->nowrap)
2942       {
2943         z->state->mode = DONE;
2944         break;
2945       }
2946       z->state->mode = CHECK4;
2947     case CHECK4:
2948       NEEDBYTE
2949       z->state->sub.check.need = (uLong)NEXTBYTE << 24;
2950       z->state->mode = CHECK3;
2951     case CHECK3:
2952       NEEDBYTE
2953       z->state->sub.check.need += (uLong)NEXTBYTE << 16;
2954       z->state->mode = CHECK2;
2955     case CHECK2:
2956       NEEDBYTE
2957       z->state->sub.check.need += (uLong)NEXTBYTE << 8;
2958       z->state->mode = CHECK1;
2959     case CHECK1:
2960       NEEDBYTE
2961       z->state->sub.check.need += (uLong)NEXTBYTE;
2962
2963       if (z->state->sub.check.was != z->state->sub.check.need)
2964       {
2965         z->state->mode = BAD;
2966         z->msg = "incorrect data check";
2967         z->state->sub.marker = 5;       /* can't try inflateSync */
2968         break;
2969       }
2970       Trace((stderr, "inflate: zlib check ok\n"));
2971       z->state->mode = DONE;
2972     case DONE:
2973       return Z_STREAM_END;
2974     case BAD:
2975       return Z_DATA_ERROR;
2976     default:
2977       return Z_STREAM_ERROR;
2978   }
2979
2980  empty:
2981   if (f != Z_PACKET_FLUSH)
2982     return r;
2983   z->state->mode = BAD;
2984   z->state->sub.marker = 0;       /* can try inflateSync */
2985   return Z_DATA_ERROR;
2986 }
2987
2988 /*
2989  * This subroutine adds the data at next_in/avail_in to the output history
2990  * without performing any output.  The output buffer must be "caught up";
2991  * i.e. no pending output (hence s->read equals s->write), and the state must
2992  * be BLOCKS (i.e. we should be willing to see the start of a series of
2993  * BLOCKS).  On exit, the output will also be caught up, and the checksum
2994  * will have been updated if need be.
2995  */
2996
2997 int inflateIncomp(z)
2998 z_stream *z;
2999 {
3000     if (z->state->mode != BLOCKS)
3001         return Z_DATA_ERROR;
3002     return inflate_addhistory(z->state->blocks, z);
3003 }
3004
3005
3006 int inflateSync(z)
3007 z_stream *z;
3008 {
3009   uInt n;       /* number of bytes to look at */
3010   Bytef *p;     /* pointer to bytes */
3011   uInt m;       /* number of marker bytes found in a row */
3012   uLong r, w;   /* temporaries to save total_in and total_out */
3013
3014   /* set up */
3015   if (z == Z_NULL || z->state == Z_NULL)
3016     return Z_STREAM_ERROR;
3017   if (z->state->mode != BAD)
3018   {
3019     z->state->mode = BAD;
3020     z->state->sub.marker = 0;
3021   }
3022   if ((n = z->avail_in) == 0)
3023     return Z_BUF_ERROR;
3024   p = z->next_in;
3025   m = z->state->sub.marker;
3026
3027   /* search */
3028   while (n && m < 4)
3029   {
3030     if (*p == (Byte)(m < 2 ? 0 : 0xff))
3031       m++;
3032     else if (*p)
3033       m = 0;
3034     else
3035       m = 4 - m;
3036     p++, n--;
3037   }
3038
3039   /* restore */
3040   z->total_in += p - z->next_in;
3041   z->next_in = p;
3042   z->avail_in = n;
3043   z->state->sub.marker = m;
3044
3045   /* return no joy or set up to restart on a new block */
3046   if (m != 4)
3047     return Z_DATA_ERROR;
3048   r = z->total_in;  w = z->total_out;
3049   inflateReset(z);
3050   z->total_in = r;  z->total_out = w;
3051   z->state->mode = BLOCKS;
3052   return Z_OK;
3053 }
3054
3055 #undef NEEDBYTE
3056 #undef NEXTBYTE
3057
3058 /*+++++*/
3059 /* infutil.h -- types and macros common to blocks and codes
3060  * Copyright (C) 1995 Mark Adler
3061  * For conditions of distribution and use, see copyright notice in zlib.h 
3062  */
3063
3064 /* WARNING: this file should *not* be used by applications. It is
3065    part of the implementation of the compression library and is
3066    subject to change. Applications should only use zlib.h.
3067  */
3068
3069 /* inflate blocks semi-private state */
3070 struct inflate_blocks_state {
3071
3072   /* mode */
3073   enum {
3074       TYPE,     /* get type bits (3, including end bit) */
3075       LENS,     /* get lengths for stored */
3076       STORED,   /* processing stored block */
3077       TABLE,    /* get table lengths */
3078       BTREE,    /* get bit lengths tree for a dynamic block */
3079       DTREE,    /* get length, distance trees for a dynamic block */
3080       CODES,    /* processing fixed or dynamic block */
3081       DRY,      /* output remaining window bytes */
3082       DONEB,     /* finished last block, done */
3083       BADB}      /* got a data error--stuck here */
3084     mode;               /* current inflate_block mode */
3085
3086   /* mode dependent information */
3087   union {
3088     uInt left;          /* if STORED, bytes left to copy */
3089     struct {
3090       uInt table;               /* table lengths (14 bits) */
3091       uInt index;               /* index into blens (or border) */
3092       uIntf *blens;             /* bit lengths of codes */
3093       uInt bb;                  /* bit length tree depth */
3094       inflate_huft *tb;         /* bit length decoding tree */
3095       int nblens;               /* # elements allocated at blens */
3096     } trees;            /* if DTREE, decoding info for trees */
3097     struct {
3098       inflate_huft *tl, *td;    /* trees to free */
3099       inflate_codes_statef 
3100          *codes;
3101     } decode;           /* if CODES, current state */
3102   } sub;                /* submode */
3103   uInt last;            /* true if this block is the last block */
3104
3105   /* mode independent information */
3106   uInt bitk;            /* bits in bit buffer */
3107   uLong bitb;           /* bit buffer */
3108   Bytef *window;        /* sliding window */
3109   Bytef *end;           /* one byte after sliding window */
3110   Bytef *read;          /* window read pointer */
3111   Bytef *write;         /* window write pointer */
3112   check_func checkfn;   /* check function */
3113   uLong check;          /* check on output */
3114
3115 };
3116
3117
3118 /* defines for inflate input/output */
3119 /*   update pointers and return */
3120 #define UPDBITS {s->bitb=b;s->bitk=k;}
3121 #define UPDIN {z->avail_in=n;z->total_in+=p-z->next_in;z->next_in=p;}
3122 #define UPDOUT {s->write=q;}
3123 #define UPDATE {UPDBITS UPDIN UPDOUT}
3124 #define LEAVE {UPDATE return inflate_flush(s,z,r);}
3125 /*   get bytes and bits */
3126 #define LOADIN {p=z->next_in;n=z->avail_in;b=s->bitb;k=s->bitk;}
3127 #define NEEDBYTE {if(n)r=Z_OK;else LEAVE}
3128 #define NEXTBYTE (n--,*p++)
3129 #define NEEDBITS(j) {while(k<(j)){NEEDBYTE;b|=((uLong)NEXTBYTE)<<k;k+=8;}}
3130 #define DUMPBITS(j) {b>>=(j);k-=(j);}
3131 /*   output bytes */
3132 #define WAVAIL (q<s->read?s->read-q-1:s->end-q)
3133 #define LOADOUT {q=s->write;m=WAVAIL;}
3134 #define WRAP {if(q==s->end&&s->read!=s->window){q=s->window;m=WAVAIL;}}
3135 #define FLUSH {UPDOUT r=inflate_flush(s,z,r); LOADOUT}
3136 #define NEEDOUT {if(m==0){WRAP if(m==0){FLUSH WRAP if(m==0) LEAVE}}r=Z_OK;}
3137 #define OUTBYTE(a) {*q++=(Byte)(a);m--;}
3138 /*   load local pointers */
3139 #define LOAD {LOADIN LOADOUT}
3140
3141 /* And'ing with mask[n] masks the lower n bits */
3142 local uInt inflate_mask[] = {
3143     0x0000,
3144     0x0001, 0x0003, 0x0007, 0x000f, 0x001f, 0x003f, 0x007f, 0x00ff,
3145     0x01ff, 0x03ff, 0x07ff, 0x0fff, 0x1fff, 0x3fff, 0x7fff, 0xffff
3146 };
3147
3148 /* copy as much as possible from the sliding window to the output area */
3149 local int inflate_flush OF((
3150     inflate_blocks_statef *,
3151     z_stream *,
3152     int));
3153
3154 /*+++++*/
3155 /* inffast.h -- header to use inffast.c
3156  * Copyright (C) 1995 Mark Adler
3157  * For conditions of distribution and use, see copyright notice in zlib.h 
3158  */
3159
3160 /* WARNING: this file should *not* be used by applications. It is
3161    part of the implementation of the compression library and is
3162    subject to change. Applications should only use zlib.h.
3163  */
3164
3165 local int inflate_fast OF((
3166     uInt,
3167     uInt,
3168     inflate_huft *,
3169     inflate_huft *,
3170     inflate_blocks_statef *,
3171     z_stream *));
3172
3173
3174 /*+++++*/
3175 /* infblock.c -- interpret and process block types to last block
3176  * Copyright (C) 1995 Mark Adler
3177  * For conditions of distribution and use, see copyright notice in zlib.h 
3178  */
3179
3180 /* Table for deflate from PKZIP's appnote.txt. */
3181 local uInt border[] = { /* Order of the bit length code lengths */
3182         16, 17, 18, 0, 8, 7, 9, 6, 10, 5, 11, 4, 12, 3, 13, 2, 14, 1, 15};
3183
3184 /*
3185    Notes beyond the 1.93a appnote.txt:
3186
3187    1. Distance pointers never point before the beginning of the output
3188       stream.
3189    2. Distance pointers can point back across blocks, up to 32k away.
3190    3. There is an implied maximum of 7 bits for the bit length table and
3191       15 bits for the actual data.
3192    4. If only one code exists, then it is encoded using one bit.  (Zero
3193       would be more efficient, but perhaps a little confusing.)  If two
3194       codes exist, they are coded using one bit each (0 and 1).
3195    5. There is no way of sending zero distance codes--a dummy must be
3196       sent if there are none.  (History: a pre 2.0 version of PKZIP would
3197       store blocks with no distance codes, but this was discovered to be
3198       too harsh a criterion.)  Valid only for 1.93a.  2.04c does allow
3199       zero distance codes, which is sent as one code of zero bits in
3200       length.
3201    6. There are up to 286 literal/length codes.  Code 256 represents the
3202       end-of-block.  Note however that the static length tree defines
3203       288 codes just to fill out the Huffman codes.  Codes 286 and 287
3204       cannot be used though, since there is no length base or extra bits
3205       defined for them.  Similarily, there are up to 30 distance codes.
3206       However, static trees define 32 codes (all 5 bits) to fill out the
3207       Huffman codes, but the last two had better not show up in the data.
3208    7. Unzip can check dynamic Huffman blocks for complete code sets.
3209       The exception is that a single code would not be complete (see #4).
3210    8. The five bits following the block type is really the number of
3211       literal codes sent minus 257.
3212    9. Length codes 8,16,16 are interpreted as 13 length codes of 8 bits
3213       (1+6+6).  Therefore, to output three times the length, you output
3214       three codes (1+1+1), whereas to output four times the same length,
3215       you only need two codes (1+3).  Hmm.
3216   10. In the tree reconstruction algorithm, Code = Code + Increment
3217       only if BitLength(i) is not zero.  (Pretty obvious.)
3218   11. Correction: 4 Bits: # of Bit Length codes - 4     (4 - 19)
3219   12. Note: length code 284 can represent 227-258, but length code 285
3220       really is 258.  The last length deserves its own, short code
3221       since it gets used a lot in very redundant files.  The length
3222       258 is special since 258 - 3 (the min match length) is 255.
3223   13. The literal/length and distance code bit lengths are read as a
3224       single stream of lengths.  It is possible (and advantageous) for
3225       a repeat code (16, 17, or 18) to go across the boundary between
3226       the two sets of lengths.
3227  */
3228
3229
3230 local void inflate_blocks_reset(s, z, c)
3231 inflate_blocks_statef *s;
3232 z_stream *z;
3233 uLongf *c;
3234 {
3235   if (s->checkfn != Z_NULL)
3236     *c = s->check;
3237   if (s->mode == BTREE || s->mode == DTREE)
3238     ZFREE(z, s->sub.trees.blens, s->sub.trees.nblens * sizeof(uInt));
3239   if (s->mode == CODES)
3240   {
3241     inflate_codes_free(s->sub.decode.codes, z);
3242     inflate_trees_free(s->sub.decode.td, z);
3243     inflate_trees_free(s->sub.decode.tl, z);
3244   }
3245   s->mode = TYPE;
3246   s->bitk = 0;
3247   s->bitb = 0;
3248   s->read = s->write = s->window;
3249   if (s->checkfn != Z_NULL)
3250     s->check = (*s->checkfn)(0L, Z_NULL, 0);
3251   Trace((stderr, "inflate:   blocks reset\n"));
3252 }
3253
3254
3255 local inflate_blocks_statef *inflate_blocks_new(z, c, w)
3256 z_stream *z;
3257 check_func c;
3258 uInt w;
3259 {
3260   inflate_blocks_statef *s;
3261
3262   if ((s = (inflate_blocks_statef *)ZALLOC_INIT
3263        (z,1,sizeof(struct inflate_blocks_state))) == Z_NULL)
3264     return s;
3265   if ((s->window = (Bytef *)ZALLOC_INIT(z, 1, w)) == Z_NULL)
3266   {
3267     ZFREE(z, s, sizeof(struct inflate_blocks_state));
3268     return Z_NULL;
3269   }
3270   s->end = s->window + w;
3271   s->checkfn = c;
3272   s->mode = TYPE;
3273   Trace((stderr, "inflate:   blocks allocated\n"));
3274   inflate_blocks_reset(s, z, &s->check);
3275   return s;
3276 }
3277
3278
3279 local int inflate_blocks(s, z, r)
3280 inflate_blocks_statef *s;
3281 z_stream *z;
3282 int r;
3283 {
3284   uInt t;               /* temporary storage */
3285   uLong b;              /* bit buffer */
3286   uInt k;               /* bits in bit buffer */
3287   Bytef *p;             /* input data pointer */
3288   uInt n;               /* bytes available there */
3289   Bytef *q;             /* output window write pointer */
3290   uInt m;               /* bytes to end of window or read pointer */
3291
3292   /* copy input/output information to locals (UPDATE macro restores) */
3293   LOAD
3294
3295   /* process input based on current state */
3296   while (1) switch (s->mode)
3297   {
3298     case TYPE:
3299       NEEDBITS(3)
3300       t = (uInt)b & 7;
3301       s->last = t & 1;
3302       switch (t >> 1)
3303       {
3304         case 0:                         /* stored */
3305           Trace((stderr, "inflate:     stored block%s\n",
3306                  s->last ? " (last)" : ""));
3307           DUMPBITS(3)
3308           t = k & 7;                    /* go to byte boundary */
3309           DUMPBITS(t)
3310           s->mode = LENS;               /* get length of stored block */
3311           break;
3312         case 1:                         /* fixed */
3313           Trace((stderr, "inflate:     fixed codes block%s\n",
3314                  s->last ? " (last)" : ""));
3315           {
3316             uInt bl, bd;
3317             inflate_huft *tl, *td;
3318
3319             inflate_trees_fixed(&bl, &bd, &tl, &td);
3320             s->sub.decode.codes = inflate_codes_new(bl, bd, tl, td, z);
3321             if (s->sub.decode.codes == Z_NULL)
3322             {
3323               r = Z_MEM_ERROR;
3324               LEAVE
3325             }
3326             s->sub.decode.tl = Z_NULL;  /* don't try to free these */
3327             s->sub.decode.td = Z_NULL;
3328           }
3329           DUMPBITS(3)
3330           s->mode = CODES;
3331           break;
3332         case 2:                         /* dynamic */
3333           Trace((stderr, "inflate:     dynamic codes block%s\n",
3334                  s->last ? " (last)" : ""));
3335           DUMPBITS(3)
3336           s->mode = TABLE;
3337           break;
3338         case 3:                         /* illegal */
3339           DUMPBITS(3)
3340           s->mode = BADB;
3341           z->msg = "invalid block type";
3342           r = Z_DATA_ERROR;
3343           LEAVE
3344       }
3345       break;
3346     case LENS:
3347       NEEDBITS(32)
3348       if (((~b) >> 16) != (b & 0xffff))
3349       {
3350         s->mode = BADB;
3351         z->msg = "invalid stored block lengths";
3352         r = Z_DATA_ERROR;
3353         LEAVE
3354       }
3355       s->sub.left = (uInt)b & 0xffff;
3356       b = k = 0;                      /* dump bits */
3357       Tracev((stderr, "inflate:       stored length %u\n", s->sub.left));
3358       s->mode = s->sub.left ? STORED : TYPE;
3359       break;
3360     case STORED:
3361       if (n == 0)
3362         LEAVE
3363       NEEDOUT
3364       t = s->sub.left;
3365       if (t > n) t = n;
3366       if (t > m) t = m;
3367       zmemcpy(q, p, t);
3368       p += t;  n -= t;
3369       q += t;  m -= t;
3370       if ((s->sub.left -= t) != 0)
3371         break;
3372       Tracev((stderr, "inflate:       stored end, %lu total out\n",
3373               z->total_out + (q >= s->read ? q - s->read :
3374               (s->end - s->read) + (q - s->window))));
3375       s->mode = s->last ? DRY : TYPE;
3376       break;
3377     case TABLE:
3378       NEEDBITS(14)
3379       s->sub.trees.table = t = (uInt)b & 0x3fff;
3380 #ifndef PKZIP_BUG_WORKAROUND
3381       if ((t & 0x1f) > 29 || ((t >> 5) & 0x1f) > 29)
3382       {
3383         s->mode = BADB;
3384         z->msg = "too many length or distance symbols";
3385         r = Z_DATA_ERROR;
3386         LEAVE
3387       }
3388 #endif
3389       t = 258 + (t & 0x1f) + ((t >> 5) & 0x1f);
3390       if (t < 19)
3391         t = 19;
3392       if ((s->sub.trees.blens = (uIntf*)ZALLOC(z, t, sizeof(uInt))) == Z_NULL)
3393       {
3394         r = Z_MEM_ERROR;
3395         LEAVE
3396       }
3397       s->sub.trees.nblens = t;
3398       DUMPBITS(14)
3399       s->sub.trees.index = 0;
3400       Tracev((stderr, "inflate:       table sizes ok\n"));
3401       s->mode = BTREE;
3402     case BTREE:
3403       while (s->sub.trees.index < 4 + (s->sub.trees.table >> 10))
3404       {
3405         NEEDBITS(3)
3406         s->sub.trees.blens[border[s->sub.trees.index++]] = (uInt)b & 7;
3407         DUMPBITS(3)
3408       }
3409       while (s->sub.trees.index < 19)
3410         s->sub.trees.blens[border[s->sub.trees.index++]] = 0;
3411       s->sub.trees.bb = 7;
3412       t = inflate_trees_bits(s->sub.trees.blens, &s->sub.trees.bb,
3413                              &s->sub.trees.tb, z);
3414       if (t != Z_OK)
3415       {
3416         r = t;
3417         if (r == Z_DATA_ERROR)
3418           s->mode = BADB;
3419         LEAVE
3420       }
3421       s->sub.trees.index = 0;
3422       Tracev((stderr, "inflate:       bits tree ok\n"));
3423       s->mode = DTREE;
3424     case DTREE:
3425       while (t = s->sub.trees.table,
3426              s->sub.trees.index < 258 + (t & 0x1f) + ((t >> 5) & 0x1f))
3427       {
3428         inflate_huft *h;
3429         uInt i, j, c;
3430
3431         t = s->sub.trees.bb;
3432         NEEDBITS(t)
3433         h = s->sub.trees.tb + ((uInt)b & inflate_mask[t]);
3434         t = h->word.what.Bits;
3435         c = h->more.Base;
3436         if (c < 16)
3437         {
3438           DUMPBITS(t)
3439           s->sub.trees.blens[s->sub.trees.index++] = c;
3440         }
3441         else /* c == 16..18 */
3442         {
3443           i = c == 18 ? 7 : c - 14;
3444           j = c == 18 ? 11 : 3;
3445           NEEDBITS(t + i)
3446           DUMPBITS(t)
3447           j += (uInt)b & inflate_mask[i];
3448           DUMPBITS(i)
3449           i = s->sub.trees.index;
3450           t = s->sub.trees.table;
3451           if (i + j > 258 + (t & 0x1f) + ((t >> 5) & 0x1f) ||
3452               (c == 16 && i < 1))
3453           {
3454             s->mode = BADB;
3455             z->msg = "invalid bit length repeat";
3456             r = Z_DATA_ERROR;
3457             LEAVE
3458           }
3459           c = c == 16 ? s->sub.trees.blens[i - 1] : 0;
3460           do {
3461             s->sub.trees.blens[i++] = c;
3462           } while (--j);
3463           s->sub.trees.index = i;
3464         }
3465       }
3466       inflate_trees_free(s->sub.trees.tb, z);
3467       s->sub.trees.tb = Z_NULL;
3468       {
3469         uInt bl, bd;
3470         inflate_huft *tl, *td;
3471         inflate_codes_statef *c;
3472
3473         bl = 9;         /* must be <= 9 for lookahead assumptions */
3474         bd = 6;         /* must be <= 9 for lookahead assumptions */
3475         t = s->sub.trees.table;
3476         t = inflate_trees_dynamic(257 + (t & 0x1f), 1 + ((t >> 5) & 0x1f),
3477                                   s->sub.trees.blens, &bl, &bd, &tl, &td, z);
3478         if (t != Z_OK)
3479         {
3480           if (t == (uInt)Z_DATA_ERROR)
3481             s->mode = BADB;
3482           r = t;
3483           LEAVE
3484         }
3485         Tracev((stderr, "inflate:       trees ok\n"));
3486         if ((c = inflate_codes_new(bl, bd, tl, td, z)) == Z_NULL)
3487         {
3488           inflate_trees_free(td, z);
3489           inflate_trees_free(tl, z);
3490           r = Z_MEM_ERROR;
3491           LEAVE
3492         }
3493         ZFREE(z, s->sub.trees.blens, s->sub.trees.nblens * sizeof(uInt));
3494         s->sub.decode.codes = c;
3495         s->sub.decode.tl = tl;
3496         s->sub.decode.td = td;
3497       }
3498       s->mode = CODES;
3499     case CODES:
3500       UPDATE
3501       if ((r = inflate_codes(s, z, r)) != Z_STREAM_END)
3502         return inflate_flush(s, z, r);
3503       r = Z_OK;
3504       inflate_codes_free(s->sub.decode.codes, z);
3505       inflate_trees_free(s->sub.decode.td, z);
3506       inflate_trees_free(s->sub.decode.tl, z);
3507       LOAD
3508       Tracev((stderr, "inflate:       codes end, %lu total out\n",
3509               z->total_out + (q >= s->read ? q - s->read :
3510               (s->end - s->read) + (q - s->window))));
3511       if (!s->last)
3512       {
3513         s->mode = TYPE;
3514         break;
3515       }
3516       if (k > 7)              /* return unused byte, if any */
3517       {
3518         Assert(k < 16, "inflate_codes grabbed too many bytes")
3519         k -= 8;
3520         n++;
3521         p--;                    /* can always return one */
3522       }
3523       s->mode = DRY;
3524     case DRY:
3525       FLUSH
3526       if (s->read != s->write)
3527         LEAVE
3528       s->mode = DONEB;
3529     case DONEB:
3530       r = Z_STREAM_END;
3531       LEAVE
3532     case BADB:
3533       r = Z_DATA_ERROR;
3534       LEAVE
3535     default:
3536       r = Z_STREAM_ERROR;
3537       LEAVE
3538   }
3539 }
3540
3541
3542 local int inflate_blocks_free(s, z, c)
3543 inflate_blocks_statef *s;
3544 z_stream *z;
3545 uLongf *c;
3546 {
3547   inflate_blocks_reset(s, z, c);
3548   ZFREE(z, s->window, s->end - s->window);
3549   ZFREE(z, s, sizeof(struct inflate_blocks_state));
3550   Trace((stderr, "inflate:   blocks freed\n"));
3551   return Z_OK;
3552 }
3553
3554 /*
3555  * This subroutine adds the data at next_in/avail_in to the output history
3556  * without performing any output.  The output buffer must be "caught up";
3557  * i.e. no pending output (hence s->read equals s->write), and the state must
3558  * be BLOCKS (i.e. we should be willing to see the start of a series of
3559  * BLOCKS).  On exit, the output will also be caught up, and the checksum
3560  * will have been updated if need be.
3561  */
3562 local int inflate_addhistory(s, z)
3563 inflate_blocks_statef *s;
3564 z_stream *z;
3565 {
3566     uLong b;              /* bit buffer */  /* NOT USED HERE */
3567     uInt k;               /* bits in bit buffer */ /* NOT USED HERE */
3568     uInt t;               /* temporary storage */
3569     Bytef *p;             /* input data pointer */
3570     uInt n;               /* bytes available there */
3571     Bytef *q;             /* output window write pointer */
3572     uInt m;               /* bytes to end of window or read pointer */
3573
3574     if (s->read != s->write)
3575         return Z_STREAM_ERROR;
3576     if (s->mode != TYPE)
3577         return Z_DATA_ERROR;
3578
3579     /* we're ready to rock */
3580     LOAD
3581     /* while there is input ready, copy to output buffer, moving
3582      * pointers as needed.
3583      */
3584     while (n) {
3585         t = n;  /* how many to do */
3586         /* is there room until end of buffer? */
3587         if (t > m) t = m;
3588         /* update check information */
3589         if (s->checkfn != Z_NULL)
3590             s->check = (*s->checkfn)(s->check, q, t);
3591         zmemcpy(q, p, t);
3592         q += t;
3593         p += t;
3594         n -= t;
3595         z->total_out += t;
3596         s->read = q;    /* drag read pointer forward */
3597 /*      WRAP  */        /* expand WRAP macro by hand to handle s->read */
3598         if (q == s->end) {
3599             s->read = q = s->window;
3600             m = WAVAIL;
3601         }
3602     }
3603     UPDATE
3604     return Z_OK;
3605 }
3606
3607
3608 /*
3609  * At the end of a Deflate-compressed PPP packet, we expect to have seen
3610  * a `stored' block type value but not the (zero) length bytes.
3611  */
3612 local int inflate_packet_flush(s)
3613     inflate_blocks_statef *s;
3614 {
3615     if (s->mode != LENS)
3616         return Z_DATA_ERROR;
3617     s->mode = TYPE;
3618     return Z_OK;
3619 }
3620
3621
3622 /*+++++*/
3623 /* inftrees.c -- generate Huffman trees for efficient decoding
3624  * Copyright (C) 1995 Mark Adler
3625  * For conditions of distribution and use, see copyright notice in zlib.h 
3626  */
3627
3628 /* simplify the use of the inflate_huft type with some defines */
3629 #define base more.Base
3630 #define next more.Next
3631 #define exop word.what.Exop
3632 #define bits word.what.Bits
3633
3634
3635 local int huft_build OF((
3636     uIntf *,            /* code lengths in bits */
3637     uInt,               /* number of codes */
3638     uInt,               /* number of "simple" codes */
3639     uIntf *,            /* list of base values for non-simple codes */
3640     uIntf *,            /* list of extra bits for non-simple codes */
3641     inflate_huft * FAR*,/* result: starting table */
3642     uIntf *,            /* maximum lookup bits (returns actual) */
3643     z_stream *));       /* for zalloc function */
3644
3645 local voidpf falloc OF((
3646     voidpf,             /* opaque pointer (not used) */
3647     uInt,               /* number of items */
3648     uInt));             /* size of item */
3649
3650 local void ffree OF((
3651     voidpf q,           /* opaque pointer (not used) */
3652     voidpf p,           /* what to free (not used) */
3653     uInt n));           /* number of bytes (not used) */
3654
3655 /* Tables for deflate from PKZIP's appnote.txt. */
3656 local uInt cplens[] = { /* Copy lengths for literal codes 257..285 */
3657         3, 4, 5, 6, 7, 8, 9, 10, 11, 13, 15, 17, 19, 23, 27, 31,
3658         35, 43, 51, 59, 67, 83, 99, 115, 131, 163, 195, 227, 258, 0, 0};
3659         /* actually lengths - 2; also see note #13 above about 258 */
3660 local uInt cplext[] = { /* Extra bits for literal codes 257..285 */
3661         0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 2, 2, 2, 2,
3662         3, 3, 3, 3, 4, 4, 4, 4, 5, 5, 5, 5, 0, 192, 192}; /* 192==invalid */
3663 local uInt cpdist[] = { /* Copy offsets for distance codes 0..29 */
3664         1, 2, 3, 4, 5, 7, 9, 13, 17, 25, 33, 49, 65, 97, 129, 193,
3665         257, 385, 513, 769, 1025, 1537, 2049, 3073, 4097, 6145,
3666         8193, 12289, 16385, 24577};
3667 local uInt cpdext[] = { /* Extra bits for distance codes */
3668         0, 0, 0, 0, 1, 1, 2, 2, 3, 3, 4, 4, 5, 5, 6, 6,
3669         7, 7, 8, 8, 9, 9, 10, 10, 11, 11,
3670         12, 12, 13, 13};
3671
3672 /*
3673    Huffman code decoding is performed using a multi-level table lookup.
3674    The fastest way to decode is to simply build a lookup table whose
3675    size is determined by the longest code.  However, the time it takes
3676    to build this table can also be a factor if the data being decoded
3677    is not very long.  The most common codes are necessarily the
3678    shortest codes, so those codes dominate the decoding time, and hence
3679    the speed.  The idea is you can have a shorter table that decodes the
3680    shorter, more probable codes, and then point to subsidiary tables for
3681    the longer codes.  The time it costs to decode the longer codes is
3682    then traded against the time it takes to make longer tables.
3683
3684    This results of this trade are in the variables lbits and dbits
3685    below.  lbits is the number of bits the first level table for literal/
3686    length codes can decode in one step, and dbits is the same thing for
3687    the distance codes.  Subsequent tables are also less than or equal to
3688    those sizes.  These values may be adjusted either when all of the
3689    codes are shorter than that, in which case the longest code length in
3690    bits is used, or when the shortest code is *longer* than the requested
3691    table size, in which case the length of the shortest code in bits is
3692    used.
3693
3694    There are two different values for the two tables, since they code a
3695    different number of possibilities each.  The literal/length table
3696    codes 286 possible values, or in a flat code, a little over eight
3697    bits.  The distance table codes 30 possible values, or a little less
3698    than five bits, flat.  The optimum values for speed end up being
3699    about one bit more than those, so lbits is 8+1 and dbits is 5+1.
3700    The optimum values may differ though from machine to machine, and
3701    possibly even between compilers.  Your mileage may vary.
3702  */
3703
3704
3705 /* If BMAX needs to be larger than 16, then h and x[] should be uLong. */
3706 #define BMAX 15         /* maximum bit length of any code */
3707 #define N_MAX 288       /* maximum number of codes in any set */
3708
3709 #ifdef DEBUG_ZLIB
3710   uInt inflate_hufts;
3711 #endif
3712
3713 local int huft_build(b, n, s, d, e, t, m, zs)
3714 uIntf *b;               /* code lengths in bits (all assumed <= BMAX) */
3715 uInt n;                 /* number of codes (assumed <= N_MAX) */
3716 uInt s;                 /* number of simple-valued codes (0..s-1) */
3717 uIntf *d;               /* list of base values for non-simple codes */
3718 uIntf *e;               /* list of extra bits for non-simple codes */  
3719 inflate_huft * FAR *t;  /* result: starting table */
3720 uIntf *m;               /* maximum lookup bits, returns actual */
3721 z_stream *zs;           /* for zalloc function */
3722 /* Given a list of code lengths and a maximum table size, make a set of
3723    tables to decode that set of codes.  Return Z_OK on success, Z_BUF_ERROR
3724    if the given code set is incomplete (the tables are still built in this
3725    case), Z_DATA_ERROR if the input is invalid (all zero length codes or an
3726    over-subscribed set of lengths), or Z_MEM_ERROR if not enough memory. */
3727 {
3728
3729   uInt a;                       /* counter for codes of length k */
3730   uInt c[BMAX+1];               /* bit length count table */
3731   uInt f;                       /* i repeats in table every f entries */
3732   int g;                        /* maximum code length */
3733   int h;                        /* table level */
3734   register uInt i;              /* counter, current code */
3735   register uInt j;              /* counter */
3736   register int k;               /* number of bits in current code */
3737   int l;                        /* bits per table (returned in m) */
3738   register uIntf *p;            /* pointer into c[], b[], or v[] */
3739   inflate_huft *q;              /* points to current table */
3740   struct inflate_huft_s r;      /* table entry for structure assignment */
3741   inflate_huft *u[BMAX];        /* table stack */
3742   uInt v[N_MAX];                /* values in order of bit length */
3743   register int w;               /* bits before this table == (l * h) */
3744   uInt x[BMAX+1];               /* bit offsets, then code stack */
3745   uIntf *xp;                    /* pointer into x */
3746   int y;                        /* number of dummy codes added */
3747   uInt z;                       /* number of entries in current table */
3748
3749
3750   /* Generate counts for each bit length */
3751   p = c;
3752 #define C0 *p++ = 0;
3753 #define C2 C0 C0 C0 C0
3754 #define C4 C2 C2 C2 C2
3755   C4                            /* clear c[]--assume BMAX+1 is 16 */
3756   p = b;  i = n;
3757   do {
3758     c[*p++]++;                  /* assume all entries <= BMAX */
3759   } while (--i);
3760   if (c[0] == n)                /* null input--all zero length codes */
3761   {
3762     *t = (inflate_huft *)Z_NULL;
3763     *m = 0;
3764     return Z_OK;
3765   }
3766
3767
3768   /* Find minimum and maximum length, bound *m by those */
3769   l = *m;
3770   for (j = 1; j <= BMAX; j++)
3771     if (c[j])
3772       break;
3773   k = j;                        /* minimum code length */
3774   if ((uInt)l < j)
3775     l = j;
3776   for (i = BMAX; i; i--)
3777     if (c[i])
3778       break;
3779   g = i;                        /* maximum code length */
3780   if ((uInt)l > i)