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