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
46typedef unsigned char  uch;
47typedef uch FAR uchf;
48typedef unsigned short ush;
49typedef ush FAR ushf;
50typedef unsigned long  ulg;
51
52extern 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
121typedef 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. */
184typedef 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
200typedef struct static_tree_desc_s  static_tree_desc;
201
202typedef 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
208typedef ush Pos;
209typedef Pos FAR Posf;
210typedef 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
216typedef 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 */
408local void ct_init       OF((deflate_state *s));
409local int  ct_tally      OF((deflate_state *s, int dist, int lc));
410local ulg ct_flush_block OF((deflate_state *s, charf *buf, ulg stored_len,
411			     int flush));
412local void ct_align      OF((deflate_state *s));
413local void ct_stored_block OF((deflate_state *s, charf *buf, ulg stored_len,
414                          int eof));
415local 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
470local 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
497typedef 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
504local 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
530local void fill_window   OF((deflate_state *s));
531local int  deflate_fast  OF((deflate_state *s, int flush));
532local int  deflate_slow  OF((deflate_state *s, int flush));
533local void lm_init       OF((deflate_state *s));
534local int longest_match  OF((deflate_state *s, IPos cur_match));
535local void putShortMSB   OF((deflate_state *s, uInt b));
536local void flush_pending OF((z_stream *strm));
537local 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
543local  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/* ========================================================================= */
579int 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/* ========================================================================= */
589int 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/* ========================================================================= */
664int 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 */
697local 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 */
708local 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/* ========================================================================= */
731int 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/* ========================================================================= */
854int 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 */
876local 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 */
902local 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 */
939local 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 */
1075local 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 */
1109local 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 */
1226local 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 */
1322local 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
1496local 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
1499local 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
1502local 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
1505local 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
1521local 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
1528local ct_data static_dtree[D_CODES];
1529/* The static distance tree. (Actually a trivial tree since all codes use
1530 * 5 bits.)
1531 */
1532
1533local 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
1539local uch length_code[MAX_MATCH-MIN_MATCH+1];
1540/* length code for each normalized match length (0 == MIN_MATCH) */
1541
1542local int base_length[LENGTH_CODES];
1543/* First normalized length for each code (0 = MIN_MATCH) */
1544
1545local int base_dist[D_CODES];
1546/* First normalized distance for each code (0 = distance of 1) */
1547
1548struct 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
1556local static_tree_desc  static_l_desc =
1557{static_ltree, extra_lbits, LITERALS+1, L_CODES, MAX_BITS};
1558
1559local static_tree_desc  static_d_desc =
1560{static_dtree, extra_dbits, 0,          D_CODES, MAX_BITS};
1561
1562local 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
1569local void ct_static_init OF((void));
1570local void init_block     OF((deflate_state *s));
1571local void pqdownheap     OF((deflate_state *s, ct_data *tree, int k));
1572local void gen_bitlen     OF((deflate_state *s, tree_desc *desc));
1573local void gen_codes      OF((ct_data *tree, int max_code, ushf *bl_count));
1574local void build_tree     OF((deflate_state *s, tree_desc *desc));
1575local void scan_tree      OF((deflate_state *s, ct_data *tree, int max_code));
1576local void send_tree      OF((deflate_state *s, ct_data *tree, int max_code));
1577local int  build_bl_tree  OF((deflate_state *s));
1578local void send_all_trees OF((deflate_state *s, int lcodes, int dcodes,
1579                              int blcodes));
1580local void compress_block OF((deflate_state *s, ct_data *ltree,
1581                              ct_data *dtree));
1582local void set_data_type  OF((deflate_state *s));
1583local unsigned bi_reverse OF((unsigned value, int length));
1584local void bi_windup      OF((deflate_state *s));
1585local void bi_flush       OF((deflate_state *s));
1586local 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
1620local void send_bits      OF((deflate_state *s, int value, int length));
1621
1622local 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 */
1670local 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 */
1736local 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 */
1769local 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 */
1813local 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 */
1848local 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 */
1935local 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 */
1977local 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 */
2064local 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 */
2109local 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 */
2160local 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 */
2195local 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 */
2224local 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 */
2239local 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 */
2256local 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 */
2281local 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 */
2403local 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 */
2451local 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 */
2504local 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 */
2521local 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 */
2536local 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 */
2553local 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 */
2572local 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
2608struct inflate_blocks_state;
2609typedef struct inflate_blocks_state FAR inflate_blocks_statef;
2610
2611local inflate_blocks_statef * inflate_blocks_new OF((
2612    z_stream *z,
2613    check_func c,               /* check function */
2614    uInt w));                   /* window size */
2615
2616local int inflate_blocks OF((
2617    inflate_blocks_statef *,
2618    z_stream *,
2619    int));                      /* initial return code */
2620
2621local void inflate_blocks_reset OF((
2622    inflate_blocks_statef *,
2623    z_stream *,
2624    uLongf *));                  /* check value on output */
2625
2626local int inflate_blocks_free OF((
2627    inflate_blocks_statef *,
2628    z_stream *,
2629    uLongf *));                  /* check value on output */
2630
2631local int inflate_addhistory OF((
2632    inflate_blocks_statef *,
2633    z_stream *));
2634
2635local 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
2652typedef struct inflate_huft_s FAR inflate_huft;
2653
2654struct 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
2673local 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
2679local 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
2689local 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
2695local 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
2711struct inflate_codes_state;
2712typedef struct inflate_codes_state FAR inflate_codes_statef;
2713
2714local inflate_codes_statef *inflate_codes_new OF((
2715    uInt, uInt,
2716    inflate_huft *, inflate_huft *,
2717    z_stream *));
2718
2719local int inflate_codes OF((
2720    inflate_blocks_statef *,
2721    z_stream *,
2722    int));
2723
2724local 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 */
2736struct 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
2770int inflateReset(z)
2771z_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
2786int inflateEnd(z)
2787z_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
2802int inflateInit2(z, w)
2803z_stream *z;
2804int 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
2848int inflateInit(z)
2849z_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
2858int inflate(z, f)
2859z_stream *z;
2860int 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
2982int inflateIncomp(z)
2983z_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
2991int inflateSync(z)
2992z_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 */
3055struct 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 */
3127local 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 */
3134local 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
3150local 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. */
3166local 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
3215local void inflate_blocks_reset(s, z, c)
3216inflate_blocks_statef *s;
3217z_stream *z;
3218uLongf *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
3240local inflate_blocks_statef *inflate_blocks_new(z, c, w)
3241z_stream *z;
3242check_func c;
3243uInt 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  s->mode = TYPE;
3258  Trace((stderr, "inflate:   blocks allocated\n"));
3259  inflate_blocks_reset(s, z, &s->check);
3260  return s;
3261}
3262
3263
3264local int inflate_blocks(s, z, r)
3265inflate_blocks_statef *s;
3266z_stream *z;
3267int r;
3268{
3269  uInt t;               /* temporary storage */
3270  uLong b;              /* bit buffer */
3271  uInt k;               /* bits in bit buffer */
3272  Bytef *p;             /* input data pointer */
3273  uInt n;               /* bytes available there */
3274  Bytef *q;             /* output window write pointer */
3275  uInt m;               /* bytes to end of window or read pointer */
3276
3277  /* copy input/output information to locals (UPDATE macro restores) */
3278  LOAD
3279
3280  /* process input based on current state */
3281  while (1) switch (s->mode)
3282  {
3283    case TYPE:
3284      NEEDBITS(3)
3285      t = (uInt)b & 7;
3286      s->last = t & 1;
3287      switch (t >> 1)
3288      {
3289        case 0:                         /* stored */
3290          Trace((stderr, "inflate:     stored block%s\n",
3291                 s->last ? " (last)" : ""));
3292          DUMPBITS(3)
3293          t = k & 7;                    /* go to byte boundary */
3294          DUMPBITS(t)
3295          s->mode = LENS;               /* get length of stored block */
3296          break;
3297        case 1:                         /* fixed */
3298          Trace((stderr, "inflate:     fixed codes block%s\n",
3299                 s->last ? " (last)" : ""));
3300          {
3301            uInt bl, bd;
3302            inflate_huft *tl, *td;
3303
3304            inflate_trees_fixed(&bl, &bd, &tl, &td);
3305            s->sub.decode.codes = inflate_codes_new(bl, bd, tl, td, z);
3306            if (s->sub.decode.codes == Z_NULL)
3307            {
3308              r = Z_MEM_ERROR;
3309              LEAVE
3310            }
3311            s->sub.decode.tl = Z_NULL;  /* don't try to free these */
3312            s->sub.decode.td = Z_NULL;
3313          }
3314          DUMPBITS(3)
3315          s->mode = CODES;
3316          break;
3317        case 2:                         /* dynamic */
3318          Trace((stderr, "inflate:     dynamic codes block%s\n",
3319                 s->last ? " (last)" : ""));
3320          DUMPBITS(3)
3321          s->mode = TABLE;
3322          break;
3323        case 3:                         /* illegal */
3324          DUMPBITS(3)
3325          s->mode = BADB;
3326          z->msg = "invalid block type";
3327          r = Z_DATA_ERROR;
3328          LEAVE
3329      }
3330      break;
3331    case LENS:
3332      NEEDBITS(32)
3333      if (((~b) >> 16) != (b & 0xffff))
3334      {
3335        s->mode = BADB;
3336        z->msg = "invalid stored block lengths";
3337        r = Z_DATA_ERROR;
3338        LEAVE
3339      }
3340      s->sub.left = (uInt)b & 0xffff;
3341      b = k = 0;                      /* dump bits */
3342      Tracev((stderr, "inflate:       stored length %u\n", s->sub.left));
3343      s->mode = s->sub.left ? STORED : TYPE;
3344      break;
3345    case STORED:
3346      if (n == 0)
3347        LEAVE
3348      NEEDOUT
3349      t = s->sub.left;
3350      if (t > n) t = n;
3351      if (t > m) t = m;
3352      zmemcpy(q, p, t);
3353      p += t;  n -= t;
3354      q += t;  m -= t;
3355      if ((s->sub.left -= t) != 0)
3356        break;
3357      Tracev((stderr, "inflate:       stored end, %lu total out\n",
3358              z->total_out + (q >= s->read ? q - s->read :
3359              (s->end - s->read) + (q - s->window))));
3360      s->mode = s->last ? DRY : TYPE;
3361      break;
3362    case TABLE:
3363      NEEDBITS(14)
3364      s->sub.trees.table = t = (uInt)b & 0x3fff;
3365#ifndef PKZIP_BUG_WORKAROUND
3366      if ((t & 0x1f) > 29 || ((t >> 5) & 0x1f) > 29)
3367      {
3368        s->mode = BADB;
3369        z->msg = "too many length or distance symbols";
3370        r = Z_DATA_ERROR;
3371        LEAVE
3372      }
3373#endif
3374      t = 258 + (t & 0x1f) + ((t >> 5) & 0x1f);
3375      if (t < 19)
3376        t = 19;
3377      if ((s->sub.trees.blens = (uIntf*)ZALLOC(z, t, sizeof(uInt))) == Z_NULL)
3378      {
3379        r = Z_MEM_ERROR;
3380        LEAVE
3381      }
3382      s->sub.trees.nblens = t;
3383      DUMPBITS(14)
3384      s->sub.trees.index = 0;
3385      Tracev((stderr, "inflate:       table sizes ok\n"));
3386      s->mode = BTREE;
3387    case BTREE:
3388      while (s->sub.trees.index < 4 + (s->sub.trees.table >> 10))
3389      {
3390        NEEDBITS(3)
3391        s->sub.trees.blens[border[s->sub.trees.index++]] = (uInt)b & 7;
3392        DUMPBITS(3)
3393      }
3394      while (s->sub.trees.index < 19)
3395        s->sub.trees.blens[border[s->sub.trees.index++]] = 0;
3396      s->sub.trees.bb = 7;
3397      t = inflate_trees_bits(s->sub.trees.blens, &s->sub.trees.bb,
3398                             &s->sub.trees.tb, z);
3399      if (t != Z_OK)
3400      {
3401        r = t;
3402        if (r == Z_DATA_ERROR)
3403          s->mode = BADB;
3404        LEAVE
3405      }
3406      s->sub.trees.index = 0;
3407      Tracev((stderr, "inflate:       bits tree ok\n"));
3408      s->mode = DTREE;
3409    case DTREE:
3410      while (t = s->sub.trees.table,
3411             s->sub.trees.index < 258 + (t & 0x1f) + ((t >> 5) & 0x1f))
3412      {
3413        inflate_huft *h;
3414        uInt i, j, c;
3415
3416        t = s->sub.trees.bb;
3417        NEEDBITS(t)
3418        h = s->sub.trees.tb + ((uInt)b & inflate_mask[t]);
3419        t = h->word.what.Bits;
3420        c = h->more.Base;
3421        if (c < 16)
3422        {
3423          DUMPBITS(t)
3424          s->sub.trees.blens[s->sub.trees.index++] = c;
3425        }
3426        else /* c == 16..18 */
3427        {
3428          i = c == 18 ? 7 : c - 14;
3429          j = c == 18 ? 11 : 3;
3430          NEEDBITS(t + i)
3431          DUMPBITS(t)
3432          j += (uInt)b & inflate_mask[i];
3433          DUMPBITS(i)
3434          i = s->sub.trees.index;
3435          t = s->sub.trees.table;
3436          if (i + j > 258 + (t & 0x1f) + ((t >> 5) & 0x1f) ||
3437              (c == 16 && i < 1))
3438          {
3439            s->mode = BADB;
3440            z->msg = "invalid bit length repeat";
3441            r = Z_DATA_ERROR;
3442            LEAVE
3443          }
3444          c = c == 16 ? s->sub.trees.blens[i - 1] : 0;
3445          do {
3446            s->sub.trees.blens[i++] = c;
3447          } while (--j);
3448          s->sub.trees.index = i;
3449        }
3450      }
3451      inflate_trees_free(s->sub.trees.tb, z);
3452      s->sub.trees.tb = Z_NULL;
3453      {
3454        uInt bl, bd;
3455        inflate_huft *tl, *td;
3456        inflate_codes_statef *c;
3457
3458        bl = 9;         /* must be <= 9 for lookahead assumptions */
3459        bd = 6;         /* must be <= 9 for lookahead assumptions */
3460        t = s->sub.trees.table;
3461        t = inflate_trees_dynamic(257 + (t & 0x1f), 1 + ((t >> 5) & 0x1f),
3462                                  s->sub.trees.blens, &bl, &bd, &tl, &td, z);
3463        if (t != Z_OK)
3464        {
3465          if (t == (uInt)Z_DATA_ERROR)
3466            s->mode = BADB;
3467          r = t;
3468          LEAVE
3469        }
3470        Tracev((stderr, "inflate:       trees ok\n"));
3471        if ((c = inflate_codes_new(bl, bd, tl, td, z)) == Z_NULL)
3472        {
3473          inflate_trees_free(td, z);
3474          inflate_trees_free(tl, z);
3475          r = Z_MEM_ERROR;
3476          LEAVE
3477        }
3478        ZFREE(z, s->sub.trees.blens, s->sub.trees.nblens * sizeof(uInt));
3479        s->sub.decode.codes = c;
3480        s->sub.decode.tl = tl;
3481        s->sub.decode.td = td;
3482      }
3483      s->mode = CODES;
3484      /* FALLTHROUGH */
3485    case CODES:
3486      UPDATE
3487      if ((r = inflate_codes(s, z, r)) != Z_STREAM_END)
3488        return inflate_flush(s, z, r);
3489      r = Z_OK;
3490      inflate_codes_free(s->sub.decode.codes, z);
3491      inflate_trees_free(s->sub.decode.td, z);
3492      inflate_trees_free(s->sub.decode.tl, z);
3493      LOAD
3494      Tracev((stderr, "inflate:       codes end, %lu total out\n",
3495              z->total_out + (q >= s->read ? q - s->read :
3496              (s->end - s->read) + (q - s->window))));
3497      if (!s->last)
3498      {
3499        s->mode = TYPE;
3500        break;
3501      }
3502      if (k > 7)              /* return unused byte, if any */
3503      {
3504        Assert(k < 16, "inflate_codes grabbed too many bytes")
3505        k -= 8;
3506        n++;
3507        p--;                    /* can always return one */
3508      }
3509      s->mode = DRY;
3510      /* FALLTHROUGH */
3511    case DRY:
3512      FLUSH
3513      if (s->read != s->write)
3514        LEAVE
3515      s->mode = DONEB;
3516      /* FALLTHROUGH */
3517    case DONEB:
3518      r = Z_STREAM_END;
3519      LEAVE
3520    case BADB:
3521      r = Z_DATA_ERROR;
3522      LEAVE
3523    default:
3524      r = Z_STREAM_ERROR;
3525      LEAVE
3526  }
3527}
3528
3529
3530local int inflate_blocks_free(s, z, c)
3531inflate_blocks_statef *s;
3532z_stream *z;
3533uLongf *c;
3534{
3535  inflate_blocks_reset(s, z, c);
3536  ZFREE(z, s->window, s->end - s->window);
3537  ZFREE(z, s, sizeof(struct inflate_blocks_state));
3538  Trace((stderr, "inflate:   blocks freed\n"));
3539  return Z_OK;
3540}
3541
3542/*
3543 * This subroutine adds the data at next_in/avail_in to the output history
3544 * without performing any output.  The output buffer must be "caught up";
3545 * i.e. no pending output (hence s->read equals s->write), and the state must
3546 * be BLOCKS (i.e. we should be willing to see the start of a series of
3547 * BLOCKS).  On exit, the output will also be caught up, and the checksum
3548 * will have been updated if need be.
3549 */
3550local int inflate_addhistory(s, z)
3551inflate_blocks_statef *s;
3552z_stream *z;
3553{
3554    uLong b;              /* bit buffer */  /* NOT USED HERE */
3555    uInt k;               /* bits in bit buffer */ /* NOT USED HERE */
3556    uInt t;               /* temporary storage */
3557    Bytef *p;             /* input data pointer */
3558    uInt n;               /* bytes available there */
3559    Bytef *q;             /* output window write pointer */
3560    uInt m;               /* bytes to end of window or read pointer */
3561
3562    if (s->read != s->write)
3563	return Z_STREAM_ERROR;
3564    if (s->mode != TYPE)
3565	return Z_DATA_ERROR;
3566
3567    /* we're ready to rock */
3568    LOAD
3569    /* while there is input ready, copy to output buffer, moving
3570     * pointers as needed.
3571     */
3572    while (n) {
3573	t = n;  /* how many to do */
3574	/* is there room until end of buffer? */
3575	if (t > m) t = m;
3576	/* update check information */
3577	if (s->checkfn != Z_NULL)
3578	    s->check = (*s->checkfn)(s->check, q, t);
3579	zmemcpy(q, p, t);
3580	q += t;
3581	p += t;
3582	n -= t;
3583	z->total_out += t;
3584	s->read = q;    /* drag read pointer forward */
3585/*      WRAP  */ 	/* expand WRAP macro by hand to handle s->read */
3586	if (q == s->end) {
3587	    s->read = q = s->window;
3588	    m = WAVAIL;
3589	}
3590    }
3591    UPDATE
3592    return Z_OK;
3593}
3594
3595
3596/*
3597 * At the end of a Deflate-compressed PPP packet, we expect to have seen
3598 * a `stored' block type value but not the (zero) length bytes.
3599 */
3600local int inflate_packet_flush(s)
3601    inflate_blocks_statef *s;
3602{
3603    if (s->mode != LENS)
3604	return Z_DATA_ERROR;
3605    s->mode = TYPE;
3606    return Z_OK;
3607}
3608
3609
3610/*+++++*/
3611/* inftrees.c -- generate Huffman trees for efficient decoding
3612 * Copyright (C) 1995 Mark Adler
3613 * For conditions of distribution and use, see copyright notice in zlib.h
3614 */
3615
3616/* simplify the use of the inflate_huft type with some defines */
3617#define base more.Base
3618#define next more.Next
3619#define exop word.what.Exop
3620#define bits word.what.Bits
3621
3622
3623local int huft_build OF((
3624    uIntf *,            /* code lengths in bits */
3625    uInt,               /* number of codes */
3626    uInt,               /* number of "simple" codes */
3627    uIntf *,            /* list of base values for non-simple codes */
3628    uIntf *,            /* list of extra bits for non-simple codes */
3629    inflate_huft * FAR*,/* result: starting table */
3630    uIntf *,            /* maximum lookup bits (returns actual) */
3631    z_stream *));       /* for zalloc function */
3632
3633local voidpf falloc OF((
3634    voidpf,             /* opaque pointer (not used) */
3635    uInt,               /* number of items */
3636    uInt));             /* size of item */
3637
3638local void ffree OF((
3639    voidpf q,           /* opaque pointer (not used) */
3640    voidpf p,           /* what to free (not used) */
3641    uInt n));		/* number of bytes (not used) */
3642
3643/* Tables for deflate from PKZIP's appnote.txt. */
3644local uInt cplens[] = { /* Copy lengths for literal codes 257..285 */
3645        3, 4, 5, 6, 7, 8, 9, 10, 11, 13, 15, 17, 19, 23, 27, 31,
3646        35, 43, 51, 59, 67, 83, 99, 115, 131, 163, 195, 227, 258, 0, 0};
3647        /* actually lengths - 2; also see note #13 above about 258 */
3648local uInt cplext[] = { /* Extra bits for literal codes 257..285 */
3649        0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 2, 2, 2, 2,
3650        3, 3, 3, 3, 4, 4, 4, 4, 5, 5, 5, 5, 0, 192, 192}; /* 192==invalid */
3651local uInt cpdist[] = { /* Copy offsets for distance codes 0..29 */
3652        1, 2, 3, 4, 5, 7, 9, 13, 17, 25, 33, 49, 65, 97, 129, 193,
3653        257, 385, 513, 769, 1025, 1537, 2049, 3073, 4097, 6145,
3654        8193, 12289, 16385, 24577};
3655local uInt cpdext[] = { /* Extra bits for distance codes */
3656        0, 0, 0, 0, 1, 1, 2, 2, 3, 3, 4, 4, 5, 5, 6, 6,
3657        7, 7, 8, 8, 9, 9, 10, 10, 11, 11,
3658        12, 12, 13, 13};
3659
3660/*
3661   Huffman code decoding is performed using a multi-level table lookup.
3662   The fastest way to decode is to simply build a lookup table whose
3663   size is determined by the longest code.  However, the time it takes
3664   to build this table can also be a factor if the data being decoded
3665   is not very long.  The most common codes are necessarily the
3666   shortest codes, so those codes dominate the decoding time, and hence
3667   the speed.  The idea is you can have a shorter table that decodes the
3668   shorter, more probable codes, and then point to subsidiary tables for
3669   the longer codes.  The time it costs to decode the longer codes is
3670   then traded against the time it takes to make longer tables.
3671
3672   This results of this trade are in the variables lbits and dbits
3673   below.  lbits is the number of bits the first level table for literal/
3674   length codes can decode in one step, and dbits is the same thing for
3675   the distance codes.  Subsequent tables are also less than or equal to
3676   those sizes.  These values may be adjusted either when all of the
3677   codes are shorter than that, in which case the longest code length in
3678   bits is used, or when the shortest code is *longer* than the requested
3679   table size, in which case the length of the shortest code in bits is
3680   used.
3681
3682   There are two different values for the two tables, since they code a
3683   different number of possibilities each.  The literal/length table
3684   codes 286 possible values, or in a flat code, a little over eight
3685   bits.  The distance table codes 30 possible values, or a little less
3686   than five bits, flat.  The optimum values for speed end up being
3687   about one bit more than those, so lbits is 8+1 and dbits is 5+1.
3688   The optimum values may differ though from machine to machine, and
3689   possibly even between compilers.  Your mileage may vary.
3690 */
3691
3692
3693/* If BMAX needs to be larger than 16, then h and x[] should be uLong. */
3694#define BMAX 15         /* maximum bit length of any code */
3695#define N_MAX 288       /* maximum number of codes in any set */
3696
3697#ifdef DEBUG_ZLIB
3698  uInt inflate_hufts;
3699#endif
3700
3701local int huft_build(b, n, s, d, e, t, m, zs)
3702uIntf *b;               /* code lengths in bits (all assumed <= BMAX) */
3703uInt n;                 /* number of codes (assumed <= N_MAX) */
3704uInt s;                 /* number of simple-valued codes (0..s-1) */
3705uIntf *d;               /* list of base values for non-simple codes */
3706uIntf *e;               /* list of extra bits for non-simple codes */
3707inflate_huft * FAR *t;  /* result: starting table */
3708uIntf *m;               /* maximum lookup bits, returns actual */
3709z_stream *zs;           /* for zalloc function */
3710/* Given a list of code lengths and a maximum table size, make a set of
3711   tables to decode that set of codes.  Return Z_OK on success, Z_BUF_ERROR
3712   if the given code set is incomplete (the tables are still built in this
3713   case), Z_DATA_ERROR if the input is invalid (all zero length codes or an
3714   over-subscribed set of lengths), or Z_MEM_ERROR if not enough memory. */
3715{
3716
3717  uInt a;                       /* counter for codes of length k */
3718  uInt c[BMAX+1];               /* bit length count table */
3719  uInt f;                       /* i repeats in table every f entries */
3720  int g;                        /* maximum code length */
3721  int h;                        /* table level */
3722  register uInt i;              /* counter, current code */
3723  register uInt j;              /* counter */
3724  register int k;               /* number of bits in current code */
3725  int l;                        /* bits per table (returned in m) */
3726  register uIntf *p;            /* pointer into c[], b[], or v[] */
3727  inflate_huft *q;              /* points to current table */
3728  struct inflate_huft_s r;      /* table entry for structure assignment */
3729  inflate_huft *u[BMAX];        /* table stack */
3730  uInt v[N_MAX];                /* values in order of bit length */
3731  register int w;               /* bits before this table == (l * h) */
3732  uInt x[BMAX+1];               /* bit offsets, then code stack */
3733  uIntf *xp;                    /* pointer into x */
3734  int y;                        /* number of dummy codes added */
3735  uInt z;                       /* number of entries in current table */
3736
3737
3738  /* Generate counts for each bit length */
3739  p = c;
3740#define C0 *p++ = 0;
3741#define C2 C0 C0 C0 C0
3742#define C4 C2 C2 C2 C2
3743  C4                            /* clear c[]--assume BMAX+1 is 16 */
3744  p = b;  i = n;
3745  do {
3746    c[*p++]++;                  /* assume all entries <= BMAX */
3747  } while (--i);
3748  if (c[0] == n)                /* null input--all zero length codes */
3749  {
3750    *t = (inflate_huft *)Z_NULL;
3751    *m = 0;
3752    return Z_OK;
3753  }
3754
3755
3756  /* Find minimum and maximum length, bound *m by those */
3757  l = *m;
3758  for (j = 1; j <= BMAX; j++)
3759    if (c[j])
3760      break;
3761  k = j;                        /* minimum code length */
3762  if ((uInt)l < j)
3763    l = j;
3764  for (i = BMAX; i; i--)
3765    if (c[i])
3766      break;
3767  g = i;                        /* maximum code length */
3768  if ((uInt)l > i)
3769    l = i;
3770  *m = l;
3771
3772
3773  /* Adjust last length count to fill out codes, if needed */
3774  for (y = 1 << j; j < i; j++, y <<= 1)
3775    if ((y -= c[j]) < 0)
3776      return Z_DATA_ERROR;
3777  if ((y -= c[i]) < 0)
3778    return Z_DATA_ERROR;
3779  c[i] += y;
3780
3781
3782  /* Generate starting offsets into the value table for each length */
3783  x[1] = j = 0;
3784  p = c + 1;  xp = x + 2;
3785  while (--i) {                 /* note that i == g from above */
3786    *xp++ = (j += *p++);
3787  }
3788
3789
3790  /* Make a table of values in order of bit lengths */
3791  p = b;  i = 0;
3792  do {
3793    if ((j = *p++) != 0)
3794      v[x[j]++] = i;
3795  } while (++i < n);
3796
3797
3798  /* Generate the Huffman codes and for each, make the table entries */
3799  x[0] = i = 0;                 /* first Huffman code is zero */
3800  p = v;                        /* grab values in bit order */
3801  h = -1;                       /* no tables yet--level -1 */
3802  w = -l;                       /* bits decoded == (l * h) */
3803  u[0] = (inflate_huft *)Z_NULL;        /* just to keep compilers happy */
3804  q = (inflate_huft *)Z_NULL;   /* ditto */
3805  z = 0;                        /* ditto */
3806
3807  /* go through the bit lengths (k already is bits in shortest code) */
3808  for (; k <= g; k++)
3809  {
3810    a = c[k];
3811    while (a--)
3812    {
3813      /* here i is the Huffman code of length k bits for value *p */
3814      /* make tables up to required level */
3815      while (k > w + l)
3816      {
3817        h++;
3818        w += l;                 /* previous table always l bits */
3819
3820        /* compute minimum size table less than or equal to l bits */
3821        z = (z = g - w) > (uInt)l ? l : z;      /* table size upper limit */
3822        if ((f = 1 << (j = k - w)) > a + 1)     /* try a k-w bit table */
3823        {                       /* too few codes for k-w bit table */
3824          f -= a + 1;           /* deduct codes from patterns left */
3825          xp = c + k;
3826          if (j < z)
3827            while (++j < z)     /* try smaller tables up to z bits */
3828            {
3829              if ((f <<= 1) <= *++xp)
3830                break;          /* enough codes to use up j bits */
3831              f -= *xp;         /* else deduct codes from patterns */
3832            }
3833        }
3834        z = 1 << j;             /* table entries for j-bit table */
3835
3836        /* allocate and link in new table */
3837        if ((q = (inflate_huft *)ZALLOC
3838             (zs,z + 1,sizeof(inflate_huft))) == Z_NULL)
3839        {
3840          if (h)
3841            inflate_trees_free(u[0], zs);
3842          return Z_MEM_ERROR;   /* not enough memory */
3843        }
3844	q->word.Nalloc = z + 1;
3845#ifdef DEBUG_ZLIB
3846        inflate_hufts += z + 1;
3847#endif
3848        *t = q + 1;             /* link to list for huft_free() */
3849        *(t = &(q->next)) = Z_NULL;
3850        u[h] = ++q;             /* table starts after link */
3851
3852        /* connect to last table, if there is one */
3853        if (h)
3854        {
3855          x[h] = i;             /* save pattern for backing up */
3856          r.bits = (Byte)l;     /* bits to dump before this table */
3857          r.exop = (Byte)j;     /* bits in this table */
3858          r.next = q;           /* pointer to this table */
3859          j = i >> (w - l);     /* (get around Turbo C bug) */
3860          u[h-1][j] = r;        /* connect to last table */
3861        }
3862      }
3863
3864      /* set up table entry in r */
3865      r.bits = (Byte)(k - w);
3866      if (p >= v + n)
3867        r.exop = 128 + 64;      /* out of values--invalid code */
3868      else if (*p < s)
3869      {
3870        r.exop = (Byte)(*p < 256 ? 0 : 32 + 64);     /* 256 is end-of-block */
3871        r.base = *p++;          /* simple code is just the value */
3872      }
3873      else
3874      {
3875        r.exop = (Byte)e[*p - s] + 16 + 64; /* non-simple--look up in lists */
3876        r.base = d[*p++ - s];
3877      }
3878
3879      /* fill code-like entries with r */
3880      f = 1 << (k - w);
3881      for (j = i >> w; j < z; j += f)
3882        q[j] = r;
3883
3884      /* backwards increment the k-bit code i */
3885      for (j = 1 << (k - 1); i & j; j >>= 1)
3886        i ^= j;
3887      i ^= j;
3888
3889      /* backup over finished tables */
3890      while ((i & ((1 << w) - 1)) != x[h])
3891      {
3892        h--;                    /* don't need to update q */
3893        w -= l;
3894      }
3895    }
3896  }
3897
3898
3899  /* Return Z_BUF_ERROR if we were given an incomplete table */
3900  return y != 0 && g != 1 ? Z_BUF_ERROR : Z_OK;
3901}
3902
3903
3904local int inflate_trees_bits(c, bb, tb, z)
3905uIntf *c;               /* 19 code lengths */
3906uIntf *bb;              /* bits tree desired/actual depth */
3907inflate_huft * FAR *tb; /* bits tree result */
3908z_stream *z;            /* for zfree function */
3909{
3910  int r;
3911
3912  r = huft_build(c, 19, 19, (uIntf*)Z_NULL, (uIntf*)Z_NULL, tb, bb, z);
3913  if (r == Z_DATA_ERROR)
3914    z->msg = "oversubscribed dynamic bit lengths tree";
3915  else if (r == Z_BUF_ERROR)
3916  {
3917    inflate_trees_free(*tb, z);
3918    z->msg = "incomplete dynamic bit lengths tree";
3919    r = Z_DATA_ERROR;
3920  }
3921  return r;
3922}
3923
3924
3925local int inflate_trees_dynamic(nl, nd, c, bl, bd, tl, td, z)
3926uInt nl;                /* number of literal/length codes */
3927uInt nd;                /* number of distance codes */
3928uIntf *c;               /* that many (total) code lengths */
3929uIntf *bl;              /* literal desired/actual bit depth */
3930uIntf *bd;              /* distance desired/actual bit depth */
3931inflate_huft * FAR *tl; /* literal/length tree result */
3932inflate_huft * FAR *td; /* distance tree result */
3933z_stream *z;            /* for zfree function */
3934{
3935  int r;
3936
3937  /* build literal/length tree */
3938  if ((r = huft_build(c, nl, 257, cplens, cplext, tl, bl, z)) != Z_OK)
3939  {
3940    if (r == Z_DATA_ERROR)
3941      z->msg = "oversubscribed literal/length tree";
3942    else if (r == Z_BUF_ERROR)
3943    {
3944      inflate_trees_free(*tl, z);
3945      z->msg = "incomplete literal/length tree";
3946      r = Z_DATA_ERROR;
3947    }
3948    return r;
3949  }
3950
3951  /* build distance tree */
3952  if ((r = huft_build(c + nl, nd, 0, cpdist, cpdext, td, bd, z)) != Z_OK)
3953  {
3954    if (r == Z_DATA_ERROR)
3955      z->msg = "oversubscribed literal/length tree";
3956    else if (r == Z_BUF_ERROR) {
3957#ifdef PKZIP_BUG_WORKAROUND
3958      r = Z_OK;
3959    }
3960#else
3961      inflate_trees_free(*td, z);
3962      z->msg = "incomplete literal/length tree";
3963      r = Z_DATA_ERROR;
3964    }
3965    inflate_trees_free(*tl, z);
3966    return r;
3967#endif
3968  }
3969
3970  /* done */
3971  return Z_OK;
3972}
3973
3974
3975/* build fixed tables only once--keep them here */
3976local int fixed_lock = 0;
3977local int fixed_built = 0;
3978#define FIXEDH 530      /* number of hufts used by fixed tables */
3979local uInt fixed_left = FIXEDH;
3980local inflate_huft fixed_mem[FIXEDH];
3981local uInt fixed_bl;
3982local uInt fixed_bd;
3983local inflate_huft *fixed_tl;
3984local inflate_huft *fixed_td;
3985
3986
3987local voidpf falloc(q, n, s)
3988voidpf q;        /* opaque pointer (not used) */
3989uInt n;         /* number of items */
3990uInt s;         /* size of item */
3991{
3992  Assert(s == sizeof(inflate_huft) && n <= fixed_left,
3993         "inflate_trees falloc overflow");
3994  if (q) s++; /* to make some compilers happy */
3995  fixed_left -= n;
3996  return (voidpf)(fixed_mem + fixed_left);
3997}
3998
3999
4000local void ffree(q, p, n)
4001voidpf q;
4002voidpf p;
4003uInt n;
4004{
4005  Assert(0, "inflate_trees ffree called!");
4006  if (q) q = p; /* to make some compilers happy */
4007}
4008
4009
4010local int inflate_trees_fixed(bl, bd, tl, td)
4011uIntf *bl;               /* literal desired/actual bit depth */
4012uIntf *bd;               /* distance desired/actual bit depth */
4013inflate_huft * FAR *tl;  /* literal/length tree result */
4014inflate_huft * FAR *td;  /* distance tree result */
4015{
4016  /* build fixed tables if not built already--lock out other instances */
4017  while (++fixed_lock > 1)
4018    fixed_lock--;
4019  if (!fixed_built)
4020  {
4021    int k;              /* temporary variable */
4022    unsigned c[288];    /* length list for huft_build */
4023    z_stream z;         /* for falloc function */
4024
4025    /* set up fake z_stream for memory routines */
4026    z.zalloc = falloc;
4027    z.zfree = ffree;
4028    z.opaque = Z_NULL;
4029
4030    /* literal table */
4031    for (k = 0; k < 144; k++)
4032      c[k] = 8;
4033    for (; k < 256; k++)
4034      c[k] = 9;
4035    for (; k < 280; k++)
4036      c[k] = 7;
4037    for (; k < 288; k++)
4038      c[k] = 8;
4039    fixed_bl = 7;
4040    huft_build(c, 288, 257, cplens, cplext, &fixed_tl, &fixed_bl, &z);
4041
4042    /* distance table */
4043    for (k = 0; k < 30; k++)
4044      c[k] = 5;
4045    fixed_bd = 5;
4046    huft_build(c, 30, 0, cpdist, cpdext, &fixed_td, &fixed_bd, &z);
4047
4048    /* done */
4049    fixed_built = 1;
4050  }
4051  fixed_lock--;
4052  *bl = fixed_bl;
4053  *bd = fixed_bd;
4054  *tl = fixed_tl;
4055  *td = fixed_td;
4056  return Z_OK;
4057}
4058
4059
4060local int inflate_trees_free(t, z)
4061inflate_huft *t;        /* table to free */
4062z_stream *z;            /* for zfree function */
4063/* Free the malloc'ed tables built by huft_build(), which makes a linked
4064   list of the tables it made, with the links in a dummy first entry of
4065   each table. */
4066{
4067  register inflate_huft *p, *q;
4068
4069  /* Go through linked list, freeing from the malloced (t[-1]) address. */
4070  p = t;
4071  while (p != Z_NULL)
4072  {
4073    q = (--p)->next;
4074    ZFREE(z, p, p->word.Nalloc * sizeof(inflate_huft));
4075    p = q;
4076  }
4077  return Z_OK;
4078}
4079
4080/*+++++*/
4081/* infcodes.c -- process literals and length/distance pairs
4082 * Copyright (C) 1995 Mark Adler
4083 * For conditions of distribution and use, see copyright notice in zlib.h
4084 */
4085
4086/* simplify the use of the inflate_huft type with some defines */
4087#define base more.Base
4088#define next more.Next
4089#define exop word.what.Exop
4090#define bits word.what.Bits
4091
4092/* inflate codes private state */
4093struct inflate_codes_state {
4094
4095  /* mode */
4096  enum {        /* waiting for "i:"=input, "o:"=output, "x:"=nothing */
4097      START,    /* x: set up for LEN */
4098      LEN,      /* i: get length/literal/eob next */
4099      LENEXT,   /* i: getting length extra (have base) */
4100      DIST,     /* i: get distance next */
4101      DISTEXT,  /* i: getting distance extra */
4102      COPY,     /* o: copying bytes in window, waiting for space */
4103      LIT,      /* o: got literal, waiting for output space */
4104      WASH,     /* o: got eob, possibly still output waiting */
4105      END,      /* x: got eob and all data flushed */
4106      BADCODE}  /* x: got error */
4107    mode;               /* current inflate_codes mode */
4108
4109  /* mode dependent information */
4110  uInt len;
4111  union {
4112    struct {
4113      inflate_huft *tree;       /* pointer into tree */
4114      uInt need;                /* bits needed */
4115    } code;             /* if LEN or DIST, where in tree */
4116    uInt lit;           /* if LIT, literal */
4117    struct {
4118      uInt get;                 /* bits to get for extra */
4119      uInt dist;                /* distance back to copy from */
4120    } copy;             /* if EXT or COPY, where and how much */
4121  } sub;                /* submode */
4122
4123  /* mode independent information */
4124  Byte lbits;           /* ltree bits decoded per branch */
4125  Byte dbits;           /* dtree bits decoder per branch */
4126  inflate_huft *ltree;          /* literal/length/eob tree */
4127  inflate_huft *dtree;          /* distance tree */
4128
4129};
4130
4131
4132local inflate_codes_statef *inflate_codes_new(bl, bd, tl, td, z)
4133uInt bl, bd;
4134inflate_huft *tl, *td;
4135z_stream *z;
4136{
4137  inflate_codes_statef *c;
4138
4139  if ((c = (inflate_codes_statef *)
4140       ZALLOC(z,1,sizeof(struct inflate_codes_state))) != Z_NULL)
4141  {
4142    c->mode = START;
4143    c->lbits = (Byte)bl;
4144    c->dbits = (Byte)bd;
4145    c->ltree = tl;
4146    c->dtree = td;
4147    Tracev((stderr, "inflate:       codes new\n"));
4148  }
4149  return c;
4150}
4151
4152
4153local int inflate_codes(s, z, r)
4154inflate_blocks_statef *s;
4155z_stream *z;
4156int r;
4157{
4158  uInt j;               /* temporary storage */
4159  inflate_huft *t;      /* temporary pointer */
4160  uInt e;               /* extra bits or operation */
4161  uLong b;              /* bit buffer */
4162  uInt k;               /* bits in bit buffer */
4163  Bytef *p;             /* input data pointer */
4164  uInt n;               /* bytes available there */
4165  Bytef *q;             /* output window write pointer */
4166  uInt m;               /* bytes to end of window or read pointer */
4167  Bytef *f;             /* pointer to copy strings from */
4168  inflate_codes_statef *c = s->sub.decode.codes;  /* codes state */
4169
4170  /* copy input/output information to locals (UPDATE macro restores) */
4171  LOAD
4172
4173  /* process input and output based on current state */
4174  while (1) switch (c->mode)
4175  {             /* waiting for "i:"=input, "o:"=output, "x:"=nothing */
4176    case START:         /* x: set up for LEN */
4177#ifndef SLOW
4178      if (m >= 258 && n >= 10)
4179      {
4180        UPDATE
4181        r = inflate_fast(c->lbits, c->dbits, c->ltree, c->dtree, s, z);
4182        LOAD
4183        if (r != Z_OK)
4184        {
4185          c->mode = r == Z_STREAM_END ? WASH : BADCODE;
4186          break;
4187        }
4188      }
4189#endif /* !SLOW */
4190      c->sub.code.need = c->lbits;
4191      c->sub.code.tree = c->ltree;
4192      c->mode = LEN;
4193      /* FALLTHROUGH */
4194    case LEN:           /* i: get length/literal/eob next */
4195      j = c->sub.code.need;
4196      NEEDBITS(j)
4197      t = c->sub.code.tree + ((uInt)b & inflate_mask[j]);
4198      DUMPBITS(t->bits)
4199      e = (uInt)(t->exop);
4200      if (e == 0)               /* literal */
4201      {
4202        c->sub.lit = t->base;
4203        Tracevv((stderr, t->base >= 0x20 && t->base < 0x7f ?
4204                 "inflate:         literal '%c'\n" :
4205                 "inflate:         literal 0x%02x\n", t->base));
4206        c->mode = LIT;
4207        break;
4208      }
4209      if (e & 16)               /* length */
4210      {
4211        c->sub.copy.get = e & 15;
4212        c->len = t->base;
4213        c->mode = LENEXT;
4214        break;
4215      }
4216      if ((e & 64) == 0)        /* next table */
4217      {
4218        c->sub.code.need = e;
4219        c->sub.code.tree = t->next;
4220        break;
4221      }
4222      if (e & 32)               /* end of block */
4223      {
4224        Tracevv((stderr, "inflate:         end of block\n"));
4225        c->mode = WASH;
4226        break;
4227      }
4228      c->mode = BADCODE;        /* invalid code */
4229      z->msg = "invalid literal/length code";
4230      r = Z_DATA_ERROR;
4231      LEAVE
4232    case LENEXT:        /* i: getting length extra (have base) */
4233      j = c->sub.copy.get;
4234      NEEDBITS(j)
4235      c->len += (uInt)b & inflate_mask[j];
4236      DUMPBITS(j)
4237      c->sub.code.need = c->dbits;
4238      c->sub.code.tree = c->dtree;
4239      Tracevv((stderr, "inflate:         length %u\n", c->len));
4240      c->mode = DIST;
4241      /* FALLTHROUGH */
4242    case DIST:          /* i: get distance next */
4243      j = c->sub.code.need;
4244      NEEDBITS(j)
4245      t = c->sub.code.tree + ((uInt)b & inflate_mask[j]);
4246      DUMPBITS(t->bits)
4247      e = (uInt)(t->exop);
4248      if (e & 16)               /* distance */
4249      {
4250        c->sub.copy.get = e & 15;
4251        c->sub.copy.dist = t->base;
4252        c->mode = DISTEXT;
4253        break;
4254      }
4255      if ((e & 64) == 0)        /* next table */
4256      {
4257        c->sub.code.need = e;
4258        c->sub.code.tree = t->next;
4259        break;
4260      }
4261      c->mode = BADCODE;        /* invalid code */
4262      z->msg = "invalid distance code";
4263      r = Z_DATA_ERROR;
4264      LEAVE
4265    case DISTEXT:       /* i: getting distance extra */
4266      j = c->sub.copy.get;
4267      NEEDBITS(j)
4268      c->sub.copy.dist += (uInt)b & inflate_mask[j];
4269      DUMPBITS(j)
4270      Tracevv((stderr, "inflate:         distance %u\n", c->sub.copy.dist));
4271      c->mode = COPY;
4272      /* FALLTHROUGH */
4273    case COPY:          /* o: copying bytes in window, waiting for space */
4274#ifndef __TURBOC__ /* Turbo C bug for following expression */
4275      f = (uInt)(q - s->window) < c->sub.copy.dist ?
4276          s->end - (c->sub.copy.dist - (q - s->window)) :
4277          q - c->sub.copy.dist;
4278#else
4279      f = q - c->sub.copy.dist;
4280      if ((uInt)(q - s->window) < c->sub.copy.dist)
4281        f = s->end - (c->sub.copy.dist - (q - s->window));
4282#endif
4283      while (c->len)
4284      {
4285        NEEDOUT
4286        OUTBYTE(*f++)
4287        if (f == s->end)
4288          f = s->window;
4289        c->len--;
4290      }
4291      c->mode = START;
4292      break;
4293    case LIT:           /* o: got literal, waiting for output space */
4294      NEEDOUT
4295      OUTBYTE(c->sub.lit)
4296      c->mode = START;
4297      break;
4298    case WASH:          /* o: got eob, possibly more output */
4299      FLUSH
4300      if (s->read != s->write)
4301        LEAVE
4302      c->mode = END;
4303      /* FALLTHROUGH */
4304    case END:
4305      r = Z_STREAM_END;
4306      LEAVE
4307    case BADCODE:       /* x: got error */
4308      r = Z_DATA_ERROR;
4309      LEAVE
4310    default:
4311      r = Z_STREAM_ERROR;
4312      LEAVE
4313  }
4314}
4315
4316
4317local void inflate_codes_free(c, z)
4318inflate_codes_statef *c;
4319z_stream *z;
4320{
4321  ZFREE(z, c, sizeof(struct inflate_codes_state));
4322  Tracev((stderr, "inflate:       codes free\n"));
4323}
4324
4325/*+++++*/
4326/* inflate_util.c -- data and routines common to blocks and codes
4327 * Copyright (C) 1995 Mark Adler
4328 * For conditions of distribution and use, see copyright notice in zlib.h
4329 */
4330
4331/* copy as much as possible from the sliding window to the output area */
4332local int inflate_flush(s, z, r)
4333inflate_blocks_statef *s;
4334z_stream *z;
4335int r;
4336{
4337  uInt n;
4338  Bytef *p, *q;
4339
4340  /* local copies of source and destination pointers */
4341  p = z->next_out;
4342  q = s->read;
4343
4344  /* compute number of bytes to copy as far as end of window */
4345  n = (uInt)((q <= s->write ? s->write : s->end) - q);
4346  if (n > z->avail_out) n = z->avail_out;
4347  if (n && r == Z_BUF_ERROR) r = Z_OK;
4348
4349  /* update counters */
4350  z->avail_out -= n;
4351  z->total_out += n;
4352
4353  /* update check information */
4354  if (s->checkfn != Z_NULL)
4355    s->check = (*s->checkfn)(s->check, q, n);
4356
4357  /* copy as far as end of window */
4358  if (p != NULL) {
4359    zmemcpy(p, q, n);
4360    p += n;
4361  }
4362  q += n;
4363
4364  /* see if more to copy at beginning of window */
4365  if (q == s->end)
4366  {
4367    /* wrap pointers */
4368    q = s->window;
4369    if (s->write == s->end)
4370      s->write = s->window;
4371
4372    /* compute bytes to copy */
4373    n = (uInt)(s->write - q);
4374    if (n > z->avail_out) n = z->avail_out;
4375    if (n && r == Z_BUF_ERROR) r = Z_OK;
4376
4377    /* update counters */
4378    z->avail_out -= n;
4379    z->total_out += n;
4380
4381    /* update check information */
4382    if (s->checkfn != Z_NULL)
4383      s->check = (*s->checkfn)(s->check, q, n);
4384
4385    /* copy */
4386    if (p != NULL) {
4387      zmemcpy(p, q, n);
4388      p += n;
4389    }
4390    q += n;
4391  }
4392
4393  /* update pointers */
4394  z->next_out = p;
4395  s->read = q;
4396
4397  /* done */
4398  return r;
4399}
4400
4401
4402/*+++++*/
4403/* inffast.c -- process literals and length/distance pairs fast
4404 * Copyright (C) 1995 Mark Adler
4405 * For conditions of distribution and use, see copyright notice in zlib.h
4406 */
4407
4408/* simplify the use of the inflate_huft type with some defines */
4409#define base more.Base
4410#define next more.Next
4411#define exop word.what.Exop
4412#define bits word.what.Bits
4413
4414/* macros for bit input with no checking and for returning unused bytes */
4415#define GRABBITS(j) {while(k<(j)){b|=((uLong)NEXTBYTE)<<k;k+=8;}}
4416#define UNGRAB {n+=(c=k>>3);p-=c;k&=7;}
4417
4418/* Called with number of bytes left to write in window at least 258
4419   (the maximum string length) and number of input bytes available
4420   at least ten.  The ten bytes are six bytes for the longest length/
4421   distance pair plus four bytes for overloading the bit buffer. */
4422
4423local int inflate_fast(bl, bd, tl, td, s, z)
4424uInt bl, bd;
4425inflate_huft *tl, *td;
4426inflate_blocks_statef *s;
4427z_stream *z;
4428{
4429  inflate_huft *t;      /* temporary pointer */
4430  uInt e;               /* extra bits or operation */
4431  uLong b;              /* bit buffer */
4432  uInt k;               /* bits in bit buffer */
4433  Bytef *p;             /* input data pointer */
4434  uInt n;               /* bytes available there */
4435  Bytef *q;             /* output window write pointer */
4436  uInt m;               /* bytes to end of window or read pointer */
4437  uInt ml;              /* mask for literal/length tree */
4438  uInt md;              /* mask for distance tree */
4439  uInt c;               /* bytes to copy */
4440  uInt d;               /* distance back to copy from */
4441  Bytef *r;             /* copy source pointer */
4442
4443  /* load input, output, bit values */
4444  LOAD
4445
4446  /* initialize masks */
4447  ml = inflate_mask[bl];
4448  md = inflate_mask[bd];
4449
4450  /* do until not enough input or output space for fast loop */
4451  do {                          /* assume called with m >= 258 && n >= 10 */
4452    /* get literal/length code */
4453    GRABBITS(20)                /* max bits for literal/length code */
4454    if ((e = (t = tl + ((uInt)b & ml))->exop) == 0)
4455    {
4456      DUMPBITS(t->bits)
4457      Tracevv((stderr, t->base >= 0x20 && t->base < 0x7f ?
4458                "inflate:         * literal '%c'\n" :
4459                "inflate:         * literal 0x%02x\n", t->base));
4460      *q++ = (Byte)t->base;
4461      m--;
4462      continue;
4463    }
4464    do {
4465      DUMPBITS(t->bits)
4466      if (e & 16)
4467      {
4468        /* get extra bits for length */
4469        e &= 15;
4470        c = t->base + ((uInt)b & inflate_mask[e]);
4471        DUMPBITS(e)
4472        Tracevv((stderr, "inflate:         * length %u\n", c));
4473
4474        /* decode distance base of block to copy */
4475        GRABBITS(15);           /* max bits for distance code */
4476        e = (t = td + ((uInt)b & md))->exop;
4477        do {
4478          DUMPBITS(t->bits)
4479          if (e & 16)
4480          {
4481            /* get extra bits to add to distance base */
4482            e &= 15;
4483            GRABBITS(e)         /* get extra bits (up to 13) */
4484            d = t->base + ((uInt)b & inflate_mask[e]);
4485            DUMPBITS(e)
4486            Tracevv((stderr, "inflate:         * distance %u\n", d));
4487
4488            /* do the copy */
4489            m -= c;
4490            if ((uInt)(q - s->window) >= d)     /* offset before dest */
4491            {                                   /*  just copy */
4492              r = q - d;
4493              *q++ = *r++;  c--;        /* minimum count is three, */
4494              *q++ = *r++;  c--;        /*  so unroll loop a little */
4495            }
4496            else                        /* else offset after destination */
4497            {
4498              e = d - (q - s->window);  /* bytes from offset to end */
4499              r = s->end - e;           /* pointer to offset */
4500              if (c > e)                /* if source crosses, */
4501              {
4502                c -= e;                 /* copy to end of window */
4503                do {
4504                  *q++ = *r++;
4505                } while (--e);
4506                r = s->window;          /* copy rest from start of window */
4507              }
4508            }
4509            do {                        /* copy all or what's left */
4510              *q++ = *r++;
4511            } while (--c);
4512            break;
4513          }
4514          else if ((e & 64) == 0)
4515            e = (t = t->next + ((uInt)b & inflate_mask[e]))->exop;
4516          else
4517          {
4518            z->msg = "invalid distance code";
4519            UNGRAB
4520            UPDATE
4521            return Z_DATA_ERROR;
4522          }
4523        } while (1);
4524        break;
4525      }
4526      if ((e & 64) == 0)
4527      {
4528        if ((e = (t = t->next + ((uInt)b & inflate_mask[e]))->exop) == 0)
4529        {
4530          DUMPBITS(t->bits)
4531          Tracevv((stderr, t->base >= 0x20 && t->base < 0x7f ?
4532                    "inflate:         * literal '%c'\n" :
4533                    "inflate:         * literal 0x%02x\n", t->base));
4534          *q++ = (Byte)t->base;
4535          m--;
4536          break;
4537        }
4538      }
4539      else if (e & 32)
4540      {
4541        Tracevv((stderr, "inflate:         * end of block\n"));
4542        UNGRAB
4543        UPDATE
4544        return Z_STREAM_END;
4545      }
4546      else
4547      {
4548        z->msg = "invalid literal/length code";
4549        UNGRAB
4550        UPDATE
4551        return Z_DATA_ERROR;
4552      }
4553    } while (1);
4554  } while (m >= 258 && n >= 10);
4555
4556  /* not enough input or output--restore pointers and return */
4557  UNGRAB
4558  UPDATE
4559  return Z_OK;
4560}
4561
4562
4563/*+++++*/
4564/* zutil.c -- target dependent utility functions for the compression library
4565 * Copyright (C) 1995 Jean-loup Gailly.
4566 * For conditions of distribution and use, see copyright notice in zlib.h
4567 */
4568
4569/* From: zutil.c,v 1.8 1995/05/03 17:27:12 jloup Exp */
4570
4571char *zlib_version = ZLIB_VERSION;
4572
4573char *z_errmsg[] = {
4574"stream end",          /* Z_STREAM_END    1 */
4575"",                    /* Z_OK            0 */
4576"file error",          /* Z_ERRNO        (-1) */
4577"stream error",        /* Z_STREAM_ERROR (-2) */
4578"data error",          /* Z_DATA_ERROR   (-3) */
4579"insufficient memory", /* Z_MEM_ERROR    (-4) */
4580"buffer error",        /* Z_BUF_ERROR    (-5) */
4581""};
4582
4583
4584/*+++++*/
4585/* adler32.c -- compute the Adler-32 checksum of a data stream
4586 * Copyright (C) 1995 Mark Adler
4587 * For conditions of distribution and use, see copyright notice in zlib.h
4588 */
4589
4590/* From: adler32.c,v 1.6 1995/05/03 17:27:08 jloup Exp */
4591
4592#define BASE 65521L /* largest prime smaller than 65536 */
4593#define NMAX 5552
4594/* NMAX is the largest n such that 255n(n+1)/2 + (n+1)(BASE-1) <= 2^32-1 */
4595
4596#define DO1(buf)  {s1 += *buf++; s2 += s1;}
4597#define DO2(buf)  DO1(buf); DO1(buf);
4598#define DO4(buf)  DO2(buf); DO2(buf);
4599#define DO8(buf)  DO4(buf); DO4(buf);
4600#define DO16(buf) DO8(buf); DO8(buf);
4601
4602/* ========================================================================= */
4603uLong adler32(adler, buf, len)
4604    uLong adler;
4605    Bytef *buf;
4606    uInt len;
4607{
4608    unsigned long s1 = adler & 0xffff;
4609    unsigned long s2 = (adler >> 16) & 0xffff;
4610    int k;
4611
4612    if (buf == Z_NULL) return 1L;
4613
4614    while (len > 0) {
4615        k = len < NMAX ? len : NMAX;
4616        len -= k;
4617        while (k >= 16) {
4618            DO16(buf);
4619            k -= 16;
4620        }
4621        if (k != 0) do {
4622            DO1(buf);
4623        } while (--k);
4624        s1 %= BASE;
4625        s2 %= BASE;
4626    }
4627    return (s2 << 16) | s1;
4628}
4629