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