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