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