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 /* ========================================================================= */
deflateInit(strm,level)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 /* ========================================================================= */
deflateInit2(strm,level,method,windowBits,memLevel,strategy,minCompression)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 /* ========================================================================= */
deflateReset(strm)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  */
putShortMSB(s,b)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  */
flush_pending(strm)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 /* ========================================================================= */
deflate(strm,flush)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 /* ========================================================================= */
deflateEnd(strm)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  */
read_buf(strm,buf,size)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  */
lm_init(s)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  */
longest_match(s,cur_match)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  */
check_match(s,start,match,length)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  */
fill_window(s)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  */
deflate_fast(s,flush)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  */
deflate_slow(s,flush)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 
send_bits(s,value,length)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  */
ct_static_init()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  */
ct_init(s)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  */
init_block(s)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  */
pqdownheap(s,tree,k)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  */
gen_bitlen(s,desc)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  */
gen_codes(tree,max_code,bl_count)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  */
build_tree(s,desc)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  */
scan_tree(s,tree,max_code)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  */
send_tree(s,tree,max_code)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  */
build_bl_tree(s)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  */
send_all_trees(s,lcodes,dcodes,blcodes)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  */
ct_stored_block(s,buf,stored_len,eof)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  */
ct_stored_type_only(s)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  */
ct_align(s)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  */
ct_flush_block(s,buf,stored_len,flush)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  */
ct_tally(s,dist,lc)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  */
compress_block(s,ltree,dtree)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  */
set_data_type(s)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  */
bi_reverse(code,len)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  */
bi_flush(s)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  */
bi_windup(s)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  */
copy_block(s,buf,len,header)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 
inflateReset(z)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 
inflateEnd(z)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 
inflateInit2(z,w)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 
inflateInit(z)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 
inflate(z,f)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       /* FALLTHROUGH */
2888     case FLAG:
2889       NEEDBYTE
2890       if ((b = NEXTBYTE) & 0x20)
2891       {
2892         z->state->mode = BAD;
2893         z->msg = "invalid reserved bit";
2894         z->state->sub.marker = 5;       /* can't try inflateSync */
2895         break;
2896       }
2897       if (((z->state->sub.method << 8) + b) % 31)
2898       {
2899         z->state->mode = BAD;
2900         z->msg = "incorrect header check";
2901         z->state->sub.marker = 5;       /* can't try inflateSync */
2902         break;
2903       }
2904       Trace((stderr, "inflate: zlib header ok\n"));
2905       z->state->mode = BLOCKS;
2906       /* FALLTHROUGH */
2907     case BLOCKS:
2908       r = inflate_blocks(z->state->blocks, z, r);
2909       if (f == Z_PACKET_FLUSH && z->avail_in == 0 && z->avail_out != 0)
2910 	  r = inflate_packet_flush(z->state->blocks);
2911       if (r == Z_DATA_ERROR)
2912       {
2913         z->state->mode = BAD;
2914         z->state->sub.marker = 0;       /* can try inflateSync */
2915         break;
2916       }
2917       if (r != Z_STREAM_END)
2918         return r;
2919       r = Z_OK;
2920       inflate_blocks_reset(z->state->blocks, z, &z->state->sub.check.was);
2921       if (z->state->nowrap)
2922       {
2923         z->state->mode = DONE;
2924         break;
2925       }
2926       z->state->mode = CHECK4;
2927       /* FALLTHROUGH */
2928     case CHECK4:
2929       NEEDBYTE
2930       z->state->sub.check.need = (uLong)NEXTBYTE << 24;
2931       z->state->mode = CHECK3;
2932       /* FALLTHROUGH */
2933     case CHECK3:
2934       NEEDBYTE
2935       z->state->sub.check.need += (uLong)NEXTBYTE << 16;
2936       z->state->mode = CHECK2;
2937       /* FALLTHROUGH */
2938     case CHECK2:
2939       NEEDBYTE
2940       z->state->sub.check.need += (uLong)NEXTBYTE << 8;
2941       z->state->mode = CHECK1;
2942       /* FALLTHROUGH */
2943     case CHECK1:
2944       NEEDBYTE
2945       z->state->sub.check.need += (uLong)NEXTBYTE;
2946 
2947       if (z->state->sub.check.was != z->state->sub.check.need)
2948       {
2949         z->state->mode = BAD;
2950         z->msg = "incorrect data check";
2951         z->state->sub.marker = 5;       /* can't try inflateSync */
2952         break;
2953       }
2954       Trace((stderr, "inflate: zlib check ok\n"));
2955       z->state->mode = DONE;
2956       /* FALLTHROUGH */
2957     case DONE:
2958       return Z_STREAM_END;
2959     case BAD:
2960       return Z_DATA_ERROR;
2961     default:
2962       return Z_STREAM_ERROR;
2963   }
2964 
2965  empty:
2966   if (f != Z_PACKET_FLUSH)
2967     return r;
2968   z->state->mode = BAD;
2969   z->state->sub.marker = 0;       /* can try inflateSync */
2970   return Z_DATA_ERROR;
2971 }
2972 
2973 /*
2974  * This subroutine adds the data at next_in/avail_in to the output history
2975  * without performing any output.  The output buffer must be "caught up";
2976  * i.e. no pending output (hence s->read equals s->write), and the state must
2977  * be BLOCKS (i.e. we should be willing to see the start of a series of
2978  * BLOCKS).  On exit, the output will also be caught up, and the checksum
2979  * will have been updated if need be.
2980  */
2981 
inflateIncomp(z)2982 int inflateIncomp(z)
2983 z_stream *z;
2984 {
2985     if (z->state->mode != BLOCKS)
2986 	return Z_DATA_ERROR;
2987     return inflate_addhistory(z->state->blocks, z);
2988 }
2989 
2990 
inflateSync(z)2991 int inflateSync(z)
2992 z_stream *z;
2993 {
2994   uInt n;       /* number of bytes to look at */
2995   Bytef *p;     /* pointer to bytes */
2996   uInt m;       /* number of marker bytes found in a row */
2997   uLong r, w;   /* temporaries to save total_in and total_out */
2998 
2999   /* set up */
3000   if (z == Z_NULL || z->state == Z_NULL)
3001     return Z_STREAM_ERROR;
3002   if (z->state->mode != BAD)
3003   {
3004     z->state->mode = BAD;
3005     z->state->sub.marker = 0;
3006   }
3007   if ((n = z->avail_in) == 0)
3008     return Z_BUF_ERROR;
3009   p = z->next_in;
3010   m = z->state->sub.marker;
3011 
3012   /* search */
3013   while (n && m < 4)
3014   {
3015     if (*p == (Byte)(m < 2 ? 0 : 0xff))
3016       m++;
3017     else if (*p)
3018       m = 0;
3019     else
3020       m = 4 - m;
3021     p++, n--;
3022   }
3023 
3024   /* restore */
3025   z->total_in += p - z->next_in;
3026   z->next_in = p;
3027   z->avail_in = n;
3028   z->state->sub.marker = m;
3029 
3030   /* return no joy or set up to restart on a new block */
3031   if (m != 4)
3032     return Z_DATA_ERROR;
3033   r = z->total_in;  w = z->total_out;
3034   inflateReset(z);
3035   z->total_in = r;  z->total_out = w;
3036   z->state->mode = BLOCKS;
3037   return Z_OK;
3038 }
3039 
3040 #undef NEEDBYTE
3041 #undef NEXTBYTE
3042 
3043 /*+++++*/
3044 /* infutil.h -- types and macros common to blocks and codes
3045  * Copyright (C) 1995 Mark Adler
3046  * For conditions of distribution and use, see copyright notice in zlib.h
3047  */
3048 
3049 /* WARNING: this file should *not* be used by applications. It is
3050    part of the implementation of the compression library and is
3051    subject to change. Applications should only use zlib.h.
3052  */
3053 
3054 /* inflate blocks semi-private state */
3055 struct inflate_blocks_state {
3056 
3057   /* mode */
3058   enum {
3059       TYPE,     /* get type bits (3, including end bit) */
3060       LENS,     /* get lengths for stored */
3061       STORED,   /* processing stored block */
3062       TABLE,    /* get table lengths */
3063       BTREE,    /* get bit lengths tree for a dynamic block */
3064       DTREE,    /* get length, distance trees for a dynamic block */
3065       CODES,    /* processing fixed or dynamic block */
3066       DRY,      /* output remaining window bytes */
3067       DONEB,     /* finished last block, done */
3068       BADB}      /* got a data error--stuck here */
3069     mode;               /* current inflate_block mode */
3070 
3071   /* mode dependent information */
3072   union {
3073     uInt left;          /* if STORED, bytes left to copy */
3074     struct {
3075       uInt table;               /* table lengths (14 bits) */
3076       uInt index;               /* index into blens (or border) */
3077       uIntf *blens;             /* bit lengths of codes */
3078       uInt bb;                  /* bit length tree depth */
3079       inflate_huft *tb;         /* bit length decoding tree */
3080       int nblens;		/* # elements allocated at blens */
3081     } trees;            /* if DTREE, decoding info for trees */
3082     struct {
3083       inflate_huft *tl, *td;    /* trees to free */
3084       inflate_codes_statef
3085          *codes;
3086     } decode;           /* if CODES, current state */
3087   } sub;                /* submode */
3088   uInt last;            /* true if this block is the last block */
3089 
3090   /* mode independent information */
3091   uInt bitk;            /* bits in bit buffer */
3092   uLong bitb;           /* bit buffer */
3093   Bytef *window;        /* sliding window */
3094   Bytef *end;           /* one byte after sliding window */
3095   Bytef *read;          /* window read pointer */
3096   Bytef *write;         /* window write pointer */
3097   check_func checkfn;   /* check function */
3098   uLong check;          /* check on output */
3099 
3100 };
3101 
3102 
3103 /* defines for inflate input/output */
3104 /*   update pointers and return */
3105 #define UPDBITS {s->bitb=b;s->bitk=k;}
3106 #define UPDIN {z->avail_in=n;z->total_in+=p-z->next_in;z->next_in=p;}
3107 #define UPDOUT {s->write=q;}
3108 #define UPDATE {UPDBITS UPDIN UPDOUT}
3109 #define LEAVE {UPDATE return inflate_flush(s,z,r);}
3110 /*   get bytes and bits */
3111 #define LOADIN {p=z->next_in;n=z->avail_in;b=s->bitb;k=s->bitk;}
3112 #define NEEDBYTE {if(n)r=Z_OK;else LEAVE}
3113 #define NEXTBYTE (n--,*p++)
3114 #define NEEDBITS(j) {while(k<(j)){NEEDBYTE;b|=((uLong)NEXTBYTE)<<k;k+=8;}}
3115 #define DUMPBITS(j) {b>>=(j);k-=(j);}
3116 /*   output bytes */
3117 #define WAVAIL (q<s->read?s->read-q-1:s->end-q)
3118 #define LOADOUT {q=s->write;m=WAVAIL;}
3119 #define WRAP {if(q==s->end&&s->read!=s->window){q=s->window;m=WAVAIL;}}
3120 #define FLUSH {UPDOUT r=inflate_flush(s,z,r); LOADOUT}
3121 #define NEEDOUT {if(m==0){WRAP if(m==0){FLUSH WRAP if(m==0) LEAVE}}r=Z_OK;}
3122 #define OUTBYTE(a) {*q++=(Byte)(a);m--;}
3123 /*   load local pointers */
3124 #define LOAD {LOADIN LOADOUT}
3125 
3126 /* And'ing with mask[n] masks the lower n bits */
3127 local uInt inflate_mask[] = {
3128     0x0000,
3129     0x0001, 0x0003, 0x0007, 0x000f, 0x001f, 0x003f, 0x007f, 0x00ff,
3130     0x01ff, 0x03ff, 0x07ff, 0x0fff, 0x1fff, 0x3fff, 0x7fff, 0xffff
3131 };
3132 
3133 /* copy as much as possible from the sliding window to the output area */
3134 local int inflate_flush OF((
3135     inflate_blocks_statef *,
3136     z_stream *,
3137     int));
3138 
3139 /*+++++*/
3140 /* inffast.h -- header to use inffast.c
3141  * Copyright (C) 1995 Mark Adler
3142  * For conditions of distribution and use, see copyright notice in zlib.h
3143  */
3144 
3145 /* WARNING: this file should *not* be used by applications. It is
3146    part of the implementation of the compression library and is
3147    subject to change. Applications should only use zlib.h.
3148  */
3149 
3150 local int inflate_fast OF((
3151     uInt,
3152     uInt,
3153     inflate_huft *,
3154     inflate_huft *,
3155     inflate_blocks_statef *,
3156     z_stream *));
3157 
3158 
3159 /*+++++*/
3160 /* infblock.c -- interpret and process block types to last block
3161  * Copyright (C) 1995 Mark Adler
3162  * For conditions of distribution and use, see copyright notice in zlib.h
3163  */
3164 
3165 /* Table for deflate from PKZIP's appnote.txt. */
3166 local uInt border[] = { /* Order of the bit length code lengths */
3167         16, 17, 18, 0, 8, 7, 9, 6, 10, 5, 11, 4, 12, 3, 13, 2, 14, 1, 15};
3168 
3169 /*
3170    Notes beyond the 1.93a appnote.txt:
3171 
3172    1. Distance pointers never point before the beginning of the output
3173       stream.
3174    2. Distance pointers can point back across blocks, up to 32k away.
3175    3. There is an implied maximum of 7 bits for the bit length table and
3176       15 bits for the actual data.
3177    4. If only one code exists, then it is encoded using one bit.  (Zero
3178       would be more efficient, but perhaps a little confusing.)  If two
3179       codes exist, they are coded using one bit each (0 and 1).
3180    5. There is no way of sending zero distance codes--a dummy must be
3181       sent if there are none.  (History: a pre 2.0 version of PKZIP would
3182       store blocks with no distance codes, but this was discovered to be
3183       too harsh a criterion.)  Valid only for 1.93a.  2.04c does allow
3184       zero distance codes, which is sent as one code of zero bits in
3185       length.
3186    6. There are up to 286 literal/length codes.  Code 256 represents the
3187       end-of-block.  Note however that the static length tree defines
3188       288 codes just to fill out the Huffman codes.  Codes 286 and 287
3189       cannot be used though, since there is no length base or extra bits
3190       defined for them.  Similarily, there are up to 30 distance codes.
3191       However, static trees define 32 codes (all 5 bits) to fill out the
3192       Huffman codes, but the last two had better not show up in the data.
3193    7. Unzip can check dynamic Huffman blocks for complete code sets.
3194       The exception is that a single code would not be complete (see #4).
3195    8. The five bits following the block type is really the number of
3196       literal codes sent minus 257.
3197    9. Length codes 8,16,16 are interpreted as 13 length codes of 8 bits
3198       (1+6+6).  Therefore, to output three times the length, you output
3199       three codes (1+1+1), whereas to output four times the same length,
3200       you only need two codes (1+3).  Hmm.
3201   10. In the tree reconstruction algorithm, Code = Code + Increment
3202       only if BitLength(i) is not zero.  (Pretty obvious.)
3203   11. Correction: 4 Bits: # of Bit Length codes - 4     (4 - 19)
3204   12. Note: length code 284 can represent 227-258, but length code 285
3205       really is 258.  The last length deserves its own, short code
3206       since it gets used a lot in very redundant files.  The length
3207       258 is special since 258 - 3 (the min match length) is 255.
3208   13. The literal/length and distance code bit lengths are read as a
3209       single stream of lengths.  It is possible (and advantageous) for
3210       a repeat code (16, 17, or 18) to go across the boundary between
3211       the two sets of lengths.
3212  */
3213 
3214 
inflate_blocks_reset(s,z,c)3215 local void inflate_blocks_reset(s, z, c)
3216 inflate_blocks_statef *s;
3217 z_stream *z;
3218 uLongf *c;
3219 {
3220   if (s->checkfn != Z_NULL)
3221     *c = s->check;
3222   if (s->mode == BTREE || s->mode == DTREE)
3223     ZFREE(z, s->sub.trees.blens, s->sub.trees.nblens * sizeof(uInt));
3224   if (s->mode == CODES)
3225   {
3226     inflate_codes_free(s->sub.decode.codes, z);
3227     inflate_trees_free(s->sub.decode.td, z);
3228     inflate_trees_free(s->sub.decode.tl, z);
3229   }
3230   s->mode = TYPE;
3231   s->bitk = 0;
3232   s->bitb = 0;
3233   s->read = s->write = s->window;
3234   if (s->checkfn != Z_NULL)
3235     s->check = (*s->checkfn)(0L, Z_NULL, 0);
3236   Trace((stderr, "inflate:   blocks reset\n"));
3237 }
3238 
3239 
inflate_blocks_new(z,c,w)3240 local inflate_blocks_statef *inflate_blocks_new(z, c, w)
3241 z_stream *z;
3242 check_func c;
3243 uInt w;
3244 {
3245   inflate_blocks_statef *s;
3246 
3247   if ((s = (inflate_blocks_statef *)ZALLOC
3248        (z,1,sizeof(struct inflate_blocks_state))) == Z_NULL)
3249     return s;
3250   if ((s->window = (Bytef *)ZALLOC(z, 1, w)) == Z_NULL)
3251   {
3252     ZFREE(z, s, sizeof(struct inflate_blocks_state));
3253     return Z_NULL;
3254   }
3255   s->end = s->window + w;
3256   s->checkfn = c;
3257