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.
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
13 * $Id: zlib.c,v 1.11 1998/09/13 23:37:12 paulus Exp $
17 * ==FILEVERSION 971210==
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.
27 #if defined(__FreeBSD__) && (defined(KERNEL) || defined(_KERNEL))
28 #define inflate inflate_ppp /* FreeBSD already has an inflate :-( */
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
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.
43 /* From: zutil.h,v 1.16 1996/07/24 13:41:13 me Exp $ */
50 #if defined(KERNEL) || defined(_KERNEL)
51 /* Assume this is a *BSD or SVR4 kernel */
52 #include <sys/types.h>
54 #include <sys/systm.h>
57 # define memcpy(d, s, n) bcopy((s), (d), (n))
58 # define memset(d, v, n) bzero((d), (n))
62 #if defined(__KERNEL__)
63 /* Assume this is a Linux kernel */
64 #include <linux/string.h>
67 #else /* not kernel */
69 #if defined(MSDOS)||defined(VMS)||defined(CRAY)||defined(WIN32)||defined(RISCOS)
79 #endif /* __KERNEL__ */
80 #endif /* _KERNEL || KERNEL */
85 /* compile with -Dlocal if your debugger can't find static symbols */
87 typedef unsigned char uch;
89 typedef unsigned short ush;
91 typedef unsigned long ulg;
93 extern const char *z_errmsg[10]; /* indexed by 2-zlib_error */
94 /* (size given to avoid silly warnings with Visual C++) */
96 #define ERR_MSG(err) z_errmsg[Z_NEED_DICT-(err)]
98 #define ERR_RETURN(strm,err) \
99 return (strm->msg = (char*)ERR_MSG(err), (err))
100 /* To be used only when the state is known to be valid */
102 /* common constants */
105 # define DEF_WBITS MAX_WBITS
107 /* default windowBits for decompression. MAX_WBITS is for compression only */
109 #if MAX_MEM_LEVEL >= 8
110 # define DEF_MEM_LEVEL 8
112 # define DEF_MEM_LEVEL MAX_MEM_LEVEL
114 /* default memLevel */
116 #define STORED_BLOCK 0
117 #define STATIC_TREES 1
119 /* The three kinds of block type */
122 #define MAX_MATCH 258
123 /* The minimum and maximum match lengths */
125 #define PRESET_DICT 0x20 /* preset dictionary flag in zlib header */
127 /* target dependencies */
130 # define OS_CODE 0x00
133 # else /* MSC or DJGPP */
139 # define OS_CODE 0x06
142 #ifdef WIN32 /* Window 95 & Windows NT */
143 # define OS_CODE 0x0b
146 #if defined(VAXC) || defined(VMS)
147 # define OS_CODE 0x02
148 # define FOPEN(name, mode) \
149 fopen((name), (mode), "mbc=60", "ctx=stm", "rfm=fix", "mrs=512")
153 # define OS_CODE 0x01
156 #if defined(ATARI) || defined(atarist)
157 # define OS_CODE 0x05
161 # define OS_CODE 0x07
164 #ifdef __50SERIES /* Prime/PRIMOS */
165 # define OS_CODE 0x0F
169 # define OS_CODE 0x0a
172 #if defined(_BEOS_) || defined(RISCOS)
173 # define fdopen(fd,mode) NULL /* No fdopen() */
176 /* Common defaults */
179 # define OS_CODE 0x03 /* assume Unix */
183 # define FOPEN(name, mode) fopen((name), (mode))
189 extern char *strerror OF((int));
190 # define zstrerror(errnum) strerror(errnum)
192 # define zstrerror(errnum) ""
198 #if (defined(M_I86SM) || defined(M_I86MM)) && !defined(_MSC_VER)
199 /* Use our own functions for small and medium model with MSC <= 5.0.
200 * You may have to use the same strategy for Borland C (untested).
204 #if defined(STDC) && !defined(HAVE_MEMCPY) && !defined(NO_MEMCPY)
208 # ifdef SMALL_MEDIUM /* MSDOS small or medium model */
209 # define zmemcpy _fmemcpy
210 # define zmemcmp _fmemcmp
211 # define zmemzero(dest, len) _fmemset(dest, 0, len)
213 # define zmemcpy memcpy
214 # define zmemcmp memcmp
215 # define zmemzero(dest, len) memset(dest, 0, len)
218 extern void zmemcpy OF((Bytef* dest, Bytef* source, uInt len));
219 extern int zmemcmp OF((Bytef* s1, Bytef* s2, uInt len));
220 extern void zmemzero OF((Bytef* dest, uInt len));
223 /* Diagnostic functions */
229 extern void z_error OF((char *m));
230 # define Assert(cond,msg) {if(!(cond)) z_error(msg);}
231 # define Trace(x) fprintf x
232 # define Tracev(x) {if (verbose) fprintf x ;}
233 # define Tracevv(x) {if (verbose>1) fprintf x ;}
234 # define Tracec(c,x) {if (verbose && (c)) fprintf x ;}
235 # define Tracecv(c,x) {if (verbose>1 && (c)) fprintf x ;}
237 # define Assert(cond,msg)
242 # define Tracecv(c,x)
246 typedef uLong (*check_func) OF((uLong check, const Bytef *buf, uInt len));
248 voidpf zcalloc OF((voidpf opaque, unsigned items, unsigned size));
249 void zcfree OF((voidpf opaque, voidpf ptr));
251 #define ZALLOC(strm, items, size) \
252 (*((strm)->zalloc))((strm)->opaque, (items), (size))
253 #define ZFREE(strm, addr) (*((strm)->zfree))((strm)->opaque, (voidpf)(addr))
254 #define TRY_FREE(s, p) {if (p) ZFREE(s, p);}
256 #endif /* _Z_UTIL_H */
260 /* deflate.h -- internal compression state
261 * Copyright (C) 1995-1996 Jean-loup Gailly
262 * For conditions of distribution and use, see copyright notice in zlib.h
265 /* WARNING: this file should *not* be used by applications. It is
266 part of the implementation of the compression library and is
267 subject to change. Applications should only use zlib.h.
270 /* From: deflate.h,v 1.10 1996/07/02 12:41:00 me Exp $ */
275 /* #include "zutil.h" */
277 /* ===========================================================================
278 * Internal compression state.
281 #define LENGTH_CODES 29
282 /* number of length codes, not counting the special END_BLOCK code */
285 /* number of literal bytes 0..255 */
287 #define L_CODES (LITERALS+1+LENGTH_CODES)
288 /* number of Literal or Length codes, including the END_BLOCK code */
291 /* number of distance codes */
294 /* number of codes used to transfer the bit lengths */
296 #define HEAP_SIZE (2*L_CODES+1)
297 /* maximum heap size */
300 /* All codes must not exceed MAX_BITS bits */
302 #define INIT_STATE 42
303 #define BUSY_STATE 113
304 #define FINISH_STATE 666
308 /* Data structure describing a single value and its code string. */
309 typedef struct ct_data_s {
311 ush freq; /* frequency count */
312 ush code; /* bit string */
315 ush dad; /* father node in Huffman tree */
316 ush len; /* length of bit string */
325 typedef struct static_tree_desc_s static_tree_desc;
327 typedef struct tree_desc_s {
328 ct_data *dyn_tree; /* the dynamic tree */
329 int max_code; /* largest code with non zero frequency */
330 static_tree_desc *stat_desc; /* the corresponding static tree */
334 typedef Pos FAR Posf;
335 typedef unsigned IPos;
337 /* A Pos is an index in the character window. We use short instead of int to
338 * save space in the various tables. IPos is used only for parameter passing.
341 typedef struct deflate_state {
342 z_streamp strm; /* pointer back to this zlib stream */
343 int status; /* as the name implies */
344 Bytef *pending_buf; /* output still pending */
345 ulg pending_buf_size; /* size of pending_buf */
346 Bytef *pending_out; /* next pending byte to output to the stream */
347 int pending; /* nb of bytes in the pending buffer */
348 int noheader; /* suppress zlib header and adler32 */
349 Byte data_type; /* UNKNOWN, BINARY or ASCII */
350 Byte method; /* STORED (for zip only) or DEFLATED */
351 int last_flush; /* value of flush param for previous deflate call */
353 /* used by deflate.c: */
355 uInt w_size; /* LZ77 window size (32K by default) */
356 uInt w_bits; /* log2(w_size) (8..16) */
357 uInt w_mask; /* w_size - 1 */
360 /* Sliding window. Input bytes are read into the second half of the window,
361 * and move to the first half later to keep a dictionary of at least wSize
362 * bytes. With this organization, matches are limited to a distance of
363 * wSize-MAX_MATCH bytes, but this ensures that IO is always
364 * performed with a length multiple of the block size. Also, it limits
365 * the window size to 64K, which is quite useful on MSDOS.
366 * To do: use the user input buffer as sliding window.
370 /* Actual size of window: 2*wSize, except when the user input buffer
371 * is directly used as sliding window.
375 /* Link to older string with same hash index. To limit the size of this
376 * array to 64K, this link is maintained only for the last 32K strings.
377 * An index in this array is thus a window index modulo 32K.
380 Posf *head; /* Heads of the hash chains or NIL. */
382 uInt ins_h; /* hash index of string to be inserted */
383 uInt hash_size; /* number of elements in hash table */
384 uInt hash_bits; /* log2(hash_size) */
385 uInt hash_mask; /* hash_size-1 */
388 /* Number of bits by which ins_h must be shifted at each input
389 * step. It must be such that after MIN_MATCH steps, the oldest
390 * byte no longer takes part in the hash key, that is:
391 * hash_shift * MIN_MATCH >= hash_bits
395 /* Window position at the beginning of the current output block. Gets
396 * negative when the window is moved backwards.
399 uInt match_length; /* length of best match */
400 IPos prev_match; /* previous match */
401 int match_available; /* set if previous match exists */
402 uInt strstart; /* start of string to insert */
403 uInt match_start; /* start of matching string */
404 uInt lookahead; /* number of valid bytes ahead in window */
407 /* Length of the best match at previous step. Matches not greater than this
408 * are discarded. This is used in the lazy match evaluation.
411 uInt max_chain_length;
412 /* To speed up deflation, hash chains are never searched beyond this
413 * length. A higher limit improves compression ratio but degrades the
418 /* Attempt to find a better match only when the current match is strictly
419 * smaller than this value. This mechanism is used only for compression
422 # define max_insert_length max_lazy_match
423 /* Insert new strings in the hash table only if the match length is not
424 * greater than this length. This saves time but degrades compression.
425 * max_insert_length is used only for compression levels <= 3.
428 int level; /* compression level (1..9) */
429 int strategy; /* favor or force Huffman coding*/
432 /* Use a faster search when the previous match is longer than this */
434 int nice_match; /* Stop searching when current match exceeds this */
436 /* used by trees.c: */
437 /* Didn't use ct_data typedef below to supress compiler warning */
438 struct ct_data_s dyn_ltree[HEAP_SIZE]; /* literal and length tree */
439 struct ct_data_s dyn_dtree[2*D_CODES+1]; /* distance tree */
440 struct ct_data_s bl_tree[2*BL_CODES+1]; /* Huffman tree for bit lengths */
442 struct tree_desc_s l_desc; /* desc. for literal tree */
443 struct tree_desc_s d_desc; /* desc. for distance tree */
444 struct tree_desc_s bl_desc; /* desc. for bit length tree */
446 ush bl_count[MAX_BITS+1];
447 /* number of codes at each bit length for an optimal tree */
449 int heap[2*L_CODES+1]; /* heap used to build the Huffman trees */
450 int heap_len; /* number of elements in the heap */
451 int heap_max; /* element of largest frequency */
452 /* The sons of heap[n] are heap[2*n] and heap[2*n+1]. heap[0] is not used.
453 * The same heap array is used to build all trees.
456 uch depth[2*L_CODES+1];
457 /* Depth of each subtree used as tie breaker for trees of equal frequency
460 uchf *l_buf; /* buffer for literals or lengths */
463 /* Size of match buffer for literals/lengths. There are 4 reasons for
464 * limiting lit_bufsize to 64K:
465 * - frequencies can be kept in 16 bit counters
466 * - if compression is not successful for the first block, all input
467 * data is still in the window so we can still emit a stored block even
468 * when input comes from standard input. (This can also be done for
469 * all blocks if lit_bufsize is not greater than 32K.)
470 * - if compression is not successful for a file smaller than 64K, we can
471 * even emit a stored file instead of a stored block (saving 5 bytes).
472 * This is applicable only for zip (not gzip or zlib).
473 * - creating new Huffman trees less frequently may not provide fast
474 * adaptation to changes in the input data statistics. (Take for
475 * example a binary file with poorly compressible code followed by
476 * a highly compressible string table.) Smaller buffer sizes give
477 * fast adaptation but have of course the overhead of transmitting
478 * trees more frequently.
479 * - I can't count above 4
482 uInt last_lit; /* running index in l_buf */
485 /* Buffer for distances. To simplify the code, d_buf and l_buf have
486 * the same number of elements. To use different lengths, an extra flag
487 * array would be necessary.
490 ulg opt_len; /* bit length of current block with optimal trees */
491 ulg static_len; /* bit length of current block with static trees */
492 ulg compressed_len; /* total bit length of compressed file */
493 uInt matches; /* number of string matches in current block */
494 int last_eob_len; /* bit length of EOB code for last block */
497 ulg bits_sent; /* bit length of the compressed data */
501 /* Output buffer. bits are inserted starting at the bottom (least
505 /* Number of valid bits in bi_buf. All bits above the last valid bit
511 /* Output a byte on the stream.
512 * IN assertion: there is enough room in pending_buf.
514 #define put_byte(s, c) {s->pending_buf[s->pending++] = (c);}
517 #define MIN_LOOKAHEAD (MAX_MATCH+MIN_MATCH+1)
518 /* Minimum amount of lookahead, except at the end of the input file.
519 * See deflate.c for comments about the MIN_MATCH+1.
522 #define MAX_DIST(s) ((s)->w_size-MIN_LOOKAHEAD)
523 /* In order to simplify the code, particularly on 16 bit machines, match
524 * distances are limited to MAX_DIST instead of WSIZE.
528 void _tr_init OF((deflate_state *s));
529 int _tr_tally OF((deflate_state *s, unsigned dist, unsigned lc));
530 ulg _tr_flush_block OF((deflate_state *s, charf *buf, ulg stored_len,
532 void _tr_align OF((deflate_state *s));
533 void _tr_stored_block OF((deflate_state *s, charf *buf, ulg stored_len,
535 void _tr_stored_type_only OF((deflate_state *));
541 /* deflate.c -- compress data using the deflation algorithm
542 * Copyright (C) 1995-1996 Jean-loup Gailly.
543 * For conditions of distribution and use, see copyright notice in zlib.h
549 * The "deflation" process depends on being able to identify portions
550 * of the input text which are identical to earlier input (within a
551 * sliding window trailing behind the input currently being processed).
553 * The most straightforward technique turns out to be the fastest for
554 * most input files: try all possible matches and select the longest.
555 * The key feature of this algorithm is that insertions into the string
556 * dictionary are very simple and thus fast, and deletions are avoided
557 * completely. Insertions are performed at each input character, whereas
558 * string matches are performed only when the previous match ends. So it
559 * is preferable to spend more time in matches to allow very fast string
560 * insertions and avoid deletions. The matching algorithm for small
561 * strings is inspired from that of Rabin & Karp. A brute force approach
562 * is used to find longer strings when a small match has been found.
563 * A similar algorithm is used in comic (by Jan-Mark Wams) and freeze
564 * (by Leonid Broukhis).
565 * A previous version of this file used a more sophisticated algorithm
566 * (by Fiala and Greene) which is guaranteed to run in linear amortized
567 * time, but has a larger average cost, uses more memory and is patented.
568 * However the F&G algorithm may be faster for some highly redundant
569 * files if the parameter max_chain_length (described below) is too large.
573 * The idea of lazy evaluation of matches is due to Jan-Mark Wams, and
574 * I found it in 'freeze' written by Leonid Broukhis.
575 * Thanks to many people for bug reports and testing.
579 * Deutsch, L.P.,"DEFLATE Compressed Data Format Specification".
580 * Available in ftp://ds.internic.net/rfc/rfc1951.txt
582 * A description of the Rabin and Karp algorithm is given in the book
583 * "Algorithms" by R. Sedgewick, Addison-Wesley, p252.
585 * Fiala,E.R., and Greene,D.H.
586 * Data Compression with Finite Windows, Comm.ACM, 32,4 (1989) 490-595
590 /* From: deflate.c,v 1.15 1996/07/24 13:40:58 me Exp $ */
592 /* #include "deflate.h" */
594 char deflate_copyright[] = " deflate 1.0.4 Copyright 1995-1996 Jean-loup Gailly ";
596 If you use the zlib library in a product, an acknowledgment is welcome
597 in the documentation of your product. If for some reason you cannot
598 include such an acknowledgment, I would appreciate that you keep this
599 copyright string in the executable of your product.
602 /* ===========================================================================
603 * Function prototypes.
606 need_more, /* block not completed, need more input or more output */
607 block_done, /* block flush performed */
608 finish_started, /* finish started, need only more output at next deflate */
609 finish_done /* finish done, accept no more input or output */
612 typedef block_state (*compress_func) OF((deflate_state *s, int flush));
613 /* Compression function. Returns the block state after the call. */
615 local void fill_window OF((deflate_state *s));
616 local block_state deflate_stored OF((deflate_state *s, int flush));
617 local block_state deflate_fast OF((deflate_state *s, int flush));
618 local block_state deflate_slow OF((deflate_state *s, int flush));
619 local void lm_init OF((deflate_state *s));
620 local void putShortMSB OF((deflate_state *s, uInt b));
621 local void flush_pending OF((z_streamp strm));
622 local int read_buf OF((z_streamp strm, charf *buf, unsigned size));
624 void match_init OF((void)); /* asm code initialization */
625 uInt longest_match OF((deflate_state *s, IPos cur_match));
627 local uInt longest_match OF((deflate_state *s, IPos cur_match));
631 local void check_match OF((deflate_state *s, IPos start, IPos match,
635 /* ===========================================================================
640 /* Tail of hash chains */
643 # define TOO_FAR 4096
645 /* Matches of length 3 are discarded if their distance exceeds TOO_FAR */
647 #define MIN_LOOKAHEAD (MAX_MATCH+MIN_MATCH+1)
648 /* Minimum amount of lookahead, except at the end of the input file.
649 * See deflate.c for comments about the MIN_MATCH+1.
652 /* Values for max_lazy_match, good_match and max_chain_length, depending on
653 * the desired pack level (0..9). The values given below have been tuned to
654 * exclude worst case performance for pathological files. Better values may be
655 * found for specific files.
657 typedef struct config_s {
658 ush good_length; /* reduce lazy search above this match length */
659 ush max_lazy; /* do not perform lazy search above this match length */
660 ush nice_length; /* quit search above this match length */
665 local config configuration_table[10] = {
666 /* good lazy nice chain */
667 /* 0 */ {0, 0, 0, 0, deflate_stored}, /* store only */
668 /* 1 */ {4, 4, 8, 4, deflate_fast}, /* maximum speed, no lazy matches */
669 /* 2 */ {4, 5, 16, 8, deflate_fast},
670 /* 3 */ {4, 6, 32, 32, deflate_fast},
672 /* 4 */ {4, 4, 16, 16, deflate_slow}, /* lazy matches */
673 /* 5 */ {8, 16, 32, 32, deflate_slow},
674 /* 6 */ {8, 16, 128, 128, deflate_slow},
675 /* 7 */ {8, 32, 128, 256, deflate_slow},
676 /* 8 */ {32, 128, 258, 1024, deflate_slow},
677 /* 9 */ {32, 258, 258, 4096, deflate_slow}}; /* maximum compression */
679 /* Note: the deflate() code requires max_lazy >= MIN_MATCH and max_chain >= 4
680 * For deflate_fast() (levels <= 3) good is ignored and lazy has a different
685 /* result of memcmp for equal strings */
687 #ifndef NO_DUMMY_DECL
688 struct static_tree_desc_s {int dummy;}; /* for buggy compilers */
691 /* ===========================================================================
692 * Update a hash value with the given input byte
693 * IN assertion: all calls to to UPDATE_HASH are made with consecutive
694 * input characters, so that a running hash key can be computed from the
695 * previous key instead of complete recalculation each time.
697 #define UPDATE_HASH(s,h,c) (h = (((h)<<s->hash_shift) ^ (c)) & s->hash_mask)
700 /* ===========================================================================
701 * Insert string str in the dictionary and set match_head to the previous head
702 * of the hash chain (the most recent string with same hash key). Return
703 * the previous length of the hash chain.
704 * IN assertion: all calls to to INSERT_STRING are made with consecutive
705 * input characters and the first MIN_MATCH bytes of str are valid
706 * (except for the last MIN_MATCH-1 bytes of the input file).
708 #define INSERT_STRING(s, str, match_head) \
709 (UPDATE_HASH(s, s->ins_h, s->window[(str) + (MIN_MATCH-1)]), \
710 s->prev[(str) & s->w_mask] = match_head = s->head[s->ins_h], \
711 s->head[s->ins_h] = (Pos)(str))
713 /* ===========================================================================
714 * Initialize the hash table (avoiding 64K overflow for 16 bit systems).
715 * prev[] will be initialized on the fly.
717 #define CLEAR_HASH(s) \
718 s->head[s->hash_size-1] = NIL; \
719 zmemzero((charf *)s->head, (unsigned)(s->hash_size-1)*sizeof(*s->head));
721 /* ========================================================================= */
722 int deflateInit_(strm, level, version, stream_size)
728 return deflateInit2_(strm, level, Z_DEFLATED, MAX_WBITS, DEF_MEM_LEVEL,
729 Z_DEFAULT_STRATEGY, version, stream_size);
730 /* To do: ignore strm->next_in if we use it as window */
733 /* ========================================================================= */
734 int deflateInit2_(strm, level, method, windowBits, memLevel, strategy,
735 version, stream_size)
747 static char* my_version = ZLIB_VERSION;
750 /* We overlay pending_buf and d_buf+l_buf. This works since the average
751 * output size for (length,distance) codes is <= 24 bits.
754 if (version == Z_NULL || version[0] != my_version[0] ||
755 stream_size != sizeof(z_stream)) {
756 return Z_VERSION_ERROR;
758 if (strm == Z_NULL) return Z_STREAM_ERROR;
762 if (strm->zalloc == Z_NULL) {
763 strm->zalloc = zcalloc;
764 strm->opaque = (voidpf)0;
766 if (strm->zfree == Z_NULL) strm->zfree = zcfree;
769 if (level == Z_DEFAULT_COMPRESSION) level = 6;
771 if (windowBits < 0) { /* undocumented feature: suppress zlib header */
773 windowBits = -windowBits;
775 if (memLevel < 1 || memLevel > MAX_MEM_LEVEL || method != Z_DEFLATED ||
776 windowBits < 8 || windowBits > 15 || level < 0 || level > 9 ||
777 strategy < 0 || strategy > Z_HUFFMAN_ONLY) {
778 return Z_STREAM_ERROR;
780 s = (deflate_state *) ZALLOC(strm, 1, sizeof(deflate_state));
781 if (s == Z_NULL) return Z_MEM_ERROR;
782 strm->state = (struct internal_state FAR *)s;
785 s->noheader = noheader;
786 s->w_bits = windowBits;
787 s->w_size = 1 << s->w_bits;
788 s->w_mask = s->w_size - 1;
790 s->hash_bits = memLevel + 7;
791 s->hash_size = 1 << s->hash_bits;
792 s->hash_mask = s->hash_size - 1;
793 s->hash_shift = ((s->hash_bits+MIN_MATCH-1)/MIN_MATCH);
795 s->window = (Bytef *) ZALLOC(strm, s->w_size, 2*sizeof(Byte));
796 s->prev = (Posf *) ZALLOC(strm, s->w_size, sizeof(Pos));
797 s->head = (Posf *) ZALLOC(strm, s->hash_size, sizeof(Pos));
799 s->lit_bufsize = 1 << (memLevel + 6); /* 16K elements by default */
801 overlay = (ushf *) ZALLOC(strm, s->lit_bufsize, sizeof(ush)+2);
802 s->pending_buf = (uchf *) overlay;
803 s->pending_buf_size = (ulg)s->lit_bufsize * (sizeof(ush)+2L);
805 if (s->window == Z_NULL || s->prev == Z_NULL || s->head == Z_NULL ||
806 s->pending_buf == Z_NULL) {
807 strm->msg = (char*)ERR_MSG(Z_MEM_ERROR);
811 s->d_buf = overlay + s->lit_bufsize/sizeof(ush);
812 s->l_buf = s->pending_buf + (1+sizeof(ush))*s->lit_bufsize;
815 s->strategy = strategy;
816 s->method = (Byte)method;
818 return deflateReset(strm);
821 /* ========================================================================= */
822 int deflateSetDictionary (strm, dictionary, dictLength)
824 const Bytef *dictionary;
828 uInt length = dictLength;
832 if (strm == Z_NULL || strm->state == Z_NULL || dictionary == Z_NULL)
833 return Z_STREAM_ERROR;
835 s = (deflate_state *) strm->state;
836 if (s->status != INIT_STATE) return Z_STREAM_ERROR;
838 strm->adler = adler32(strm->adler, dictionary, dictLength);
840 if (length < MIN_MATCH) return Z_OK;
841 if (length > MAX_DIST(s)) {
842 length = MAX_DIST(s);
843 #ifndef USE_DICT_HEAD
844 dictionary += dictLength - length; /* use the tail of the dictionary */
847 zmemcpy((charf *)s->window, dictionary, length);
848 s->strstart = length;
849 s->block_start = (long)length;
851 /* Insert all strings in the hash table (except for the last two bytes).
852 * s->lookahead stays null, so s->ins_h will be recomputed at the next
853 * call of fill_window.
855 s->ins_h = s->window[0];
856 UPDATE_HASH(s, s->ins_h, s->window[1]);
857 for (n = 0; n <= length - MIN_MATCH; n++) {
858 INSERT_STRING(s, n, hash_head);
860 if (hash_head) hash_head = 0; /* to make compiler happy */
864 /* ========================================================================= */
865 int deflateReset (strm)
870 if (strm == Z_NULL || strm->state == Z_NULL ||
871 strm->zalloc == Z_NULL || strm->zfree == Z_NULL) return Z_STREAM_ERROR;
873 strm->total_in = strm->total_out = 0;
874 strm->msg = Z_NULL; /* use zfree if we ever allocate msg dynamically */
875 strm->data_type = Z_UNKNOWN;
877 s = (deflate_state *)strm->state;
879 s->pending_out = s->pending_buf;
881 if (s->noheader < 0) {
882 s->noheader = 0; /* was set to -1 by deflate(..., Z_FINISH); */
884 s->status = s->noheader ? BUSY_STATE : INIT_STATE;
886 s->last_flush = Z_NO_FLUSH;
894 /* ========================================================================= */
895 int deflateParams(strm, level, strategy)
904 if (strm == Z_NULL || strm->state == Z_NULL) return Z_STREAM_ERROR;
905 s = (deflate_state *) strm->state;
907 if (level == Z_DEFAULT_COMPRESSION) {
910 if (level < 0 || level > 9 || strategy < 0 || strategy > Z_HUFFMAN_ONLY) {
911 return Z_STREAM_ERROR;
913 func = configuration_table[s->level].func;
915 if (func != configuration_table[level].func && strm->total_in != 0) {
916 /* Flush the last buffer: */
917 err = deflate(strm, Z_PARTIAL_FLUSH);
919 if (s->level != level) {
921 s->max_lazy_match = configuration_table[level].max_lazy;
922 s->good_match = configuration_table[level].good_length;
923 s->nice_match = configuration_table[level].nice_length;
924 s->max_chain_length = configuration_table[level].max_chain;
926 s->strategy = strategy;
930 /* =========================================================================
931 * Put a short in the pending buffer. The 16-bit value is put in MSB order.
932 * IN assertion: the stream state is correct and there is enough room in
935 local void putShortMSB (s, b)
939 put_byte(s, (Byte)(b >> 8));
940 put_byte(s, (Byte)(b & 0xff));
943 /* =========================================================================
944 * Flush as much pending output as possible. All deflate() output goes
945 * through this function so some applications may wish to modify it
946 * to avoid allocating a large strm->next_out buffer and copying into it.
947 * (See also read_buf()).
949 local void flush_pending(strm)
952 deflate_state *s = (deflate_state *) strm->state;
953 unsigned len = s->pending;
955 if (len > strm->avail_out) len = strm->avail_out;
956 if (len == 0) return;
958 if (strm->next_out != Z_NULL) {
959 zmemcpy(strm->next_out, s->pending_out, len);
960 strm->next_out += len;
962 s->pending_out += len;
963 strm->total_out += len;
964 strm->avail_out -= len;
966 if (s->pending == 0) {
967 s->pending_out = s->pending_buf;
971 /* ========================================================================= */
972 int deflate (strm, flush)
976 int old_flush; /* value of flush param for previous deflate call */
979 if (strm == Z_NULL || strm->state == Z_NULL ||
980 flush > Z_FINISH || flush < 0) {
981 return Z_STREAM_ERROR;
983 s = (deflate_state *) strm->state;
985 if ((strm->next_in == Z_NULL && strm->avail_in != 0) ||
986 (s->status == FINISH_STATE && flush != Z_FINISH)) {
987 ERR_RETURN(strm, Z_STREAM_ERROR);
989 if (strm->avail_out == 0) ERR_RETURN(strm, Z_BUF_ERROR);
991 s->strm = strm; /* just in case */
992 old_flush = s->last_flush;
993 s->last_flush = flush;
995 /* Write the zlib header */
996 if (s->status == INIT_STATE) {
998 uInt header = (Z_DEFLATED + ((s->w_bits-8)<<4)) << 8;
999 uInt level_flags = (s->level-1) >> 1;
1001 if (level_flags > 3) level_flags = 3;
1002 header |= (level_flags << 6);
1003 if (s->strstart != 0) header |= PRESET_DICT;
1004 header += 31 - (header % 31);
1006 s->status = BUSY_STATE;
1007 putShortMSB(s, header);
1009 /* Save the adler32 of the preset dictionary: */
1010 if (s->strstart != 0) {
1011 putShortMSB(s, (uInt)(strm->adler >> 16));
1012 putShortMSB(s, (uInt)(strm->adler & 0xffff));
1017 /* Flush as much pending output as possible */
1018 if (s->pending != 0) {
1019 flush_pending(strm);
1020 if (strm->avail_out == 0) {
1021 /* Since avail_out is 0, deflate will be called again with
1022 * more output space, but possibly with both pending and
1023 * avail_in equal to zero. There won't be anything to do,
1024 * but this is not an error situation so make sure we
1025 * return OK instead of BUF_ERROR at next call of deflate:
1031 /* Make sure there is something to do and avoid duplicate consecutive
1032 * flushes. For repeated and useless calls with Z_FINISH, we keep
1033 * returning Z_STREAM_END instead of Z_BUFF_ERROR.
1035 } else if (strm->avail_in == 0 && flush <= old_flush &&
1036 flush != Z_FINISH) {
1037 ERR_RETURN(strm, Z_BUF_ERROR);
1040 /* User must not provide more input after the first FINISH: */
1041 if (s->status == FINISH_STATE && strm->avail_in != 0) {
1042 ERR_RETURN(strm, Z_BUF_ERROR);
1045 /* Start a new block or continue the current one.
1047 if (strm->avail_in != 0 || s->lookahead != 0 ||
1048 (flush != Z_NO_FLUSH && s->status != FINISH_STATE)) {
1051 bstate = (*(configuration_table[s->level].func))(s, flush);
1053 if (bstate == finish_started || bstate == finish_done) {
1054 s->status = FINISH_STATE;
1056 if (bstate == need_more || bstate == finish_started) {
1057 if (strm->avail_out == 0) {
1058 s->last_flush = -1; /* avoid BUF_ERROR next call, see above */
1061 /* If flush != Z_NO_FLUSH && avail_out == 0, the next call
1062 * of deflate should use the same flush parameter to make sure
1063 * that the flush is complete. So we don't have to output an
1064 * empty block here, this will be done at next call. This also
1065 * ensures that for a very small output buffer, we emit at most
1069 if (bstate == block_done) {
1070 if (flush == Z_PARTIAL_FLUSH) {
1072 } else if (flush == Z_PACKET_FLUSH) {
1073 /* Output just the 3-bit `stored' block type value,
1074 but not a zero length. */
1075 _tr_stored_type_only(s);
1076 } else { /* FULL_FLUSH or SYNC_FLUSH */
1077 _tr_stored_block(s, (char*)0, 0L, 0);
1078 /* For a full flush, this empty block will be recognized
1079 * as a special marker by inflate_sync().
1081 if (flush == Z_FULL_FLUSH) {
1082 CLEAR_HASH(s); /* forget history */
1085 flush_pending(strm);
1086 if (strm->avail_out == 0) {
1087 s->last_flush = -1; /* avoid BUF_ERROR at next call, see above */
1092 Assert(strm->avail_out > 0, "bug2");
1094 if (flush != Z_FINISH) return Z_OK;
1095 if (s->noheader) return Z_STREAM_END;
1097 /* Write the zlib trailer (adler32) */
1098 putShortMSB(s, (uInt)(strm->adler >> 16));
1099 putShortMSB(s, (uInt)(strm->adler & 0xffff));
1100 flush_pending(strm);
1101 /* If avail_out is zero, the application will call deflate again
1102 * to flush the rest.
1104 s->noheader = -1; /* write the trailer only once! */
1105 return s->pending != 0 ? Z_OK : Z_STREAM_END;
1108 /* ========================================================================= */
1109 int deflateEnd (strm)
1115 if (strm == Z_NULL || strm->state == Z_NULL) return Z_STREAM_ERROR;
1116 s = (deflate_state *) strm->state;
1119 if (status != INIT_STATE && status != BUSY_STATE &&
1120 status != FINISH_STATE) {
1121 return Z_STREAM_ERROR;
1124 /* Deallocate in reverse order of allocations: */
1125 TRY_FREE(strm, s->pending_buf);
1126 TRY_FREE(strm, s->head);
1127 TRY_FREE(strm, s->prev);
1128 TRY_FREE(strm, s->window);
1131 strm->state = Z_NULL;
1133 return status == BUSY_STATE ? Z_DATA_ERROR : Z_OK;
1136 /* =========================================================================
1137 * Copy the source state to the destination state.
1139 int deflateCopy (dest, source)
1147 if (source == Z_NULL || dest == Z_NULL || source->state == Z_NULL)
1148 return Z_STREAM_ERROR;
1149 ss = (deflate_state *) source->state;
1151 zmemcpy(dest, source, sizeof(*dest));
1153 ds = (deflate_state *) ZALLOC(dest, 1, sizeof(deflate_state));
1154 if (ds == Z_NULL) return Z_MEM_ERROR;
1155 dest->state = (struct internal_state FAR *) ds;
1156 zmemcpy(ds, ss, sizeof(*ds));
1159 ds->window = (Bytef *) ZALLOC(dest, ds->w_size, 2*sizeof(Byte));
1160 ds->prev = (Posf *) ZALLOC(dest, ds->w_size, sizeof(Pos));
1161 ds->head = (Posf *) ZALLOC(dest, ds->hash_size, sizeof(Pos));
1162 overlay = (ushf *) ZALLOC(dest, ds->lit_bufsize, sizeof(ush)+2);
1163 ds->pending_buf = (uchf *) overlay;
1165 if (ds->window == Z_NULL || ds->prev == Z_NULL || ds->head == Z_NULL ||
1166 ds->pending_buf == Z_NULL) {
1170 /* ??? following zmemcpy doesn't work for 16-bit MSDOS */
1171 zmemcpy(ds->window, ss->window, ds->w_size * 2 * sizeof(Byte));
1172 zmemcpy(ds->prev, ss->prev, ds->w_size * sizeof(Pos));
1173 zmemcpy(ds->head, ss->head, ds->hash_size * sizeof(Pos));
1174 zmemcpy(ds->pending_buf, ss->pending_buf, (uInt)ds->pending_buf_size);
1176 ds->pending_out = ds->pending_buf + (ss->pending_out - ss->pending_buf);
1177 ds->d_buf = overlay + ds->lit_bufsize/sizeof(ush);
1178 ds->l_buf = ds->pending_buf + (1+sizeof(ush))*ds->lit_bufsize;
1180 ds->l_desc.dyn_tree = ds->dyn_ltree;
1181 ds->d_desc.dyn_tree = ds->dyn_dtree;
1182 ds->bl_desc.dyn_tree = ds->bl_tree;
1187 /* ===========================================================================
1188 * Return the number of bytes of output which are immediately available
1189 * for output from the decompressor.
1191 int deflateOutputPending (strm)
1194 if (strm == Z_NULL || strm->state == Z_NULL) return 0;
1196 return ((deflate_state *)(strm->state))->pending;
1199 /* ===========================================================================
1200 * Read a new buffer from the current input stream, update the adler32
1201 * and total number of bytes read. All deflate() input goes through
1202 * this function so some applications may wish to modify it to avoid
1203 * allocating a large strm->next_in buffer and copying from it.
1204 * (See also flush_pending()).
1206 local int read_buf(strm, buf, size)
1211 unsigned len = strm->avail_in;
1213 if (len > size) len = size;
1214 if (len == 0) return 0;
1216 strm->avail_in -= len;
1218 if (!((deflate_state *)(strm->state))->noheader) {
1219 strm->adler = adler32(strm->adler, strm->next_in, len);
1221 zmemcpy(buf, strm->next_in, len);
1222 strm->next_in += len;
1223 strm->total_in += len;
1228 /* ===========================================================================
1229 * Initialize the "longest match" routines for a new zlib stream
1231 local void lm_init (s)
1234 s->window_size = (ulg)2L*s->w_size;
1238 /* Set the default configuration parameters:
1240 s->max_lazy_match = configuration_table[s->level].max_lazy;
1241 s->good_match = configuration_table[s->level].good_length;
1242 s->nice_match = configuration_table[s->level].nice_length;
1243 s->max_chain_length = configuration_table[s->level].max_chain;
1246 s->block_start = 0L;
1248 s->match_length = s->prev_length = MIN_MATCH-1;
1249 s->match_available = 0;
1252 match_init(); /* initialize the asm code */
1256 /* ===========================================================================
1257 * Set match_start to the longest match starting at the given string and
1258 * return its length. Matches shorter or equal to prev_length are discarded,
1259 * in which case the result is equal to prev_length and match_start is
1261 * IN assertions: cur_match is the head of the hash chain for the current
1262 * string (strstart) and its distance is <= MAX_DIST, and prev_length >= 1
1263 * OUT assertion: the match length is not greater than s->lookahead.
1266 /* For 80x86 and 680x0, an optimized version will be provided in match.asm or
1267 * match.S. The code will be functionally equivalent.
1269 local uInt longest_match(s, cur_match)
1271 IPos cur_match; /* current match */
1273 unsigned chain_length = s->max_chain_length;/* max hash chain length */
1274 register Bytef *scan = s->window + s->strstart; /* current string */
1275 register Bytef *match; /* matched string */
1276 register int len; /* length of current match */
1277 int best_len = s->prev_length; /* best match length so far */
1278 int nice_match = s->nice_match; /* stop if match long enough */
1279 IPos limit = s->strstart > (IPos)MAX_DIST(s) ?
1280 s->strstart - (IPos)MAX_DIST(s) : NIL;
1281 /* Stop when cur_match becomes <= limit. To simplify the code,
1282 * we prevent matches with the string of window index 0.
1284 Posf *prev = s->prev;
1285 uInt wmask = s->w_mask;
1288 /* Compare two bytes at a time. Note: this is not always beneficial.
1289 * Try with and without -DUNALIGNED_OK to check.
1291 register Bytef *strend = s->window + s->strstart + MAX_MATCH - 1;
1292 register ush scan_start = *(ushf*)scan;
1293 register ush scan_end = *(ushf*)(scan+best_len-1);
1295 register Bytef *strend = s->window + s->strstart + MAX_MATCH;
1296 register Byte scan_end1 = scan[best_len-1];
1297 register Byte scan_end = scan[best_len];
1300 /* The code is optimized for HASH_BITS >= 8 and MAX_MATCH-2 multiple of 16.
1301 * It is easy to get rid of this optimization if necessary.
1303 Assert(s->hash_bits >= 8 && MAX_MATCH == 258, "Code too clever");
1305 /* Do not waste too much time if we already have a good match: */
1306 if (s->prev_length >= s->good_match) {
1309 /* Do not look for matches beyond the end of the input. This is necessary
1310 * to make deflate deterministic.
1312 if ((uInt)nice_match > s->lookahead) nice_match = s->lookahead;
1314 Assert((ulg)s->strstart <= s->window_size-MIN_LOOKAHEAD, "need lookahead");
1317 Assert(cur_match < s->strstart, "no future");
1318 match = s->window + cur_match;
1320 /* Skip to next match if the match length cannot increase
1321 * or if the match length is less than 2:
1323 #if (defined(UNALIGNED_OK) && MAX_MATCH == 258)
1324 /* This code assumes sizeof(unsigned short) == 2. Do not use
1325 * UNALIGNED_OK if your compiler uses a different size.
1327 if (*(ushf*)(match+best_len-1) != scan_end ||
1328 *(ushf*)match != scan_start) continue;
1330 /* It is not necessary to compare scan[2] and match[2] since they are
1331 * always equal when the other bytes match, given that the hash keys
1332 * are equal and that HASH_BITS >= 8. Compare 2 bytes at a time at
1333 * strstart+3, +5, ... up to strstart+257. We check for insufficient
1334 * lookahead only every 4th comparison; the 128th check will be made
1335 * at strstart+257. If MAX_MATCH-2 is not a multiple of 8, it is
1336 * necessary to put more guard bytes at the end of the window, or
1337 * to check more often for insufficient lookahead.
1339 Assert(scan[2] == match[2], "scan[2]?");
1342 } while (*(ushf*)(scan+=2) == *(ushf*)(match+=2) &&
1343 *(ushf*)(scan+=2) == *(ushf*)(match+=2) &&
1344 *(ushf*)(scan+=2) == *(ushf*)(match+=2) &&
1345 *(ushf*)(scan+=2) == *(ushf*)(match+=2) &&
1347 /* The funny "do {}" generates better code on most compilers */
1349 /* Here, scan <= window+strstart+257 */
1350 Assert(scan <= s->window+(unsigned)(s->window_size-1), "wild scan");
1351 if (*scan == *match) scan++;
1353 len = (MAX_MATCH - 1) - (int)(strend-scan);
1354 scan = strend - (MAX_MATCH-1);
1356 #else /* UNALIGNED_OK */
1358 if (match[best_len] != scan_end ||
1359 match[best_len-1] != scan_end1 ||
1361 *++match != scan[1]) continue;
1363 /* The check at best_len-1 can be removed because it will be made
1364 * again later. (This heuristic is not always a win.)
1365 * It is not necessary to compare scan[2] and match[2] since they
1366 * are always equal when the other bytes match, given that
1367 * the hash keys are equal and that HASH_BITS >= 8.
1370 Assert(*scan == *match, "match[2]?");
1372 /* We check for insufficient lookahead only every 8th comparison;
1373 * the 256th check will be made at strstart+258.
1376 } while (*++scan == *++match && *++scan == *++match &&
1377 *++scan == *++match && *++scan == *++match &&
1378 *++scan == *++match && *++scan == *++match &&
1379 *++scan == *++match && *++scan == *++match &&
1382 Assert(scan <= s->window+(unsigned)(s->window_size-1), "wild scan");
1384 len = MAX_MATCH - (int)(strend - scan);
1385 scan = strend - MAX_MATCH;
1387 #endif /* UNALIGNED_OK */
1389 if (len > best_len) {
1390 s->match_start = cur_match;
1392 if (len >= nice_match) break;
1394 scan_end = *(ushf*)(scan+best_len-1);
1396 scan_end1 = scan[best_len-1];
1397 scan_end = scan[best_len];
1400 } while ((cur_match = prev[cur_match & wmask]) > limit
1401 && --chain_length != 0);
1403 if ((uInt)best_len <= s->lookahead) return best_len;
1404 return s->lookahead;
1409 /* ===========================================================================
1410 * Check that the match at match_start is indeed a match.
1412 local void check_match(s, start, match, length)
1417 /* check that the match is indeed a match */
1418 if (zmemcmp((charf *)s->window + match,
1419 (charf *)s->window + start, length) != EQUAL) {
1420 fprintf(stderr, " start %u, match %u, length %d\n",
1421 start, match, length);
1423 fprintf(stderr, "%c%c", s->window[match++], s->window[start++]);
1424 } while (--length != 0);
1425 z_error("invalid match");
1427 if (z_verbose > 1) {
1428 fprintf(stderr,"\\[%d,%d]", start-match, length);
1429 do { putc(s->window[start++], stderr); } while (--length != 0);
1433 # define check_match(s, start, match, length)
1436 /* ===========================================================================
1437 * Fill the window when the lookahead becomes insufficient.
1438 * Updates strstart and lookahead.
1440 * IN assertion: lookahead < MIN_LOOKAHEAD
1441 * OUT assertions: strstart <= window_size-MIN_LOOKAHEAD
1442 * At least one byte has been read, or avail_in == 0; reads are
1443 * performed for at least two bytes (required for the zip translate_eol
1444 * option -- not supported here).
1446 local void fill_window(s)
1449 register unsigned n, m;
1451 unsigned more; /* Amount of free space at the end of the window. */
1452 uInt wsize = s->w_size;
1455 more = (unsigned)(s->window_size -(ulg)s->lookahead -(ulg)s->strstart);
1457 /* Deal with !@#$% 64K limit: */
1458 if (more == 0 && s->strstart == 0 && s->lookahead == 0) {
1461 } else if (more == (unsigned)(-1)) {
1462 /* Very unlikely, but possible on 16 bit machine if strstart == 0
1463 * and lookahead == 1 (input done one byte at time)
1467 /* If the window is almost full and there is insufficient lookahead,
1468 * move the upper half to the lower one to make room in the upper half.
1470 } else if (s->strstart >= wsize+MAX_DIST(s)) {
1472 zmemcpy((charf *)s->window, (charf *)s->window+wsize,
1474 s->match_start -= wsize;
1475 s->strstart -= wsize; /* we now have strstart >= MAX_DIST */
1476 s->block_start -= (long) wsize;
1478 /* Slide the hash table (could be avoided with 32 bit values
1479 at the expense of memory usage). We slide even when level == 0
1480 to keep the hash table consistent if we switch back to level > 0
1481 later. (Using level 0 permanently is not an optimal usage of
1482 zlib, so we don't care about this pathological case.)
1488 *p = (Pos)(m >= wsize ? m-wsize : NIL);
1495 *p = (Pos)(m >= wsize ? m-wsize : NIL);
1496 /* If n is not on any hash chain, prev[n] is garbage but
1497 * its value will never be used.
1502 if (s->strm->avail_in == 0) return;
1504 /* If there was no sliding:
1505 * strstart <= WSIZE+MAX_DIST-1 && lookahead <= MIN_LOOKAHEAD - 1 &&
1506 * more == window_size - lookahead - strstart
1507 * => more >= window_size - (MIN_LOOKAHEAD-1 + WSIZE + MAX_DIST-1)
1508 * => more >= window_size - 2*WSIZE + 2
1509 * In the BIG_MEM or MMAP case (not yet supported),
1510 * window_size == input_size + MIN_LOOKAHEAD &&
1511 * strstart + s->lookahead <= input_size => more >= MIN_LOOKAHEAD.
1512 * Otherwise, window_size == 2*WSIZE so more >= 2.
1513 * If there was sliding, more >= WSIZE. So in all cases, more >= 2.
1515 Assert(more >= 2, "more < 2");
1517 n = read_buf(s->strm, (charf *)s->window + s->strstart + s->lookahead,
1521 /* Initialize the hash value now that we have some input: */
1522 if (s->lookahead >= MIN_MATCH) {
1523 s->ins_h = s->window[s->strstart];
1524 UPDATE_HASH(s, s->ins_h, s->window[s->strstart+1]);
1526 Call UPDATE_HASH() MIN_MATCH-3 more times
1529 /* If the whole input has less than MIN_MATCH bytes, ins_h is garbage,
1530 * but this is not important since only literal bytes will be emitted.
1533 } while (s->lookahead < MIN_LOOKAHEAD && s->strm->avail_in != 0);
1536 /* ===========================================================================
1537 * Flush the current block, with given end-of-file flag.
1538 * IN assertion: strstart is set to the end of the current match.
1540 #define FLUSH_BLOCK_ONLY(s, eof) { \
1541 _tr_flush_block(s, (s->block_start >= 0L ? \
1542 (charf *)&s->window[(unsigned)s->block_start] : \
1544 (ulg)((long)s->strstart - s->block_start), \
1546 s->block_start = s->strstart; \
1547 flush_pending(s->strm); \
1548 Tracev((stderr,"[FLUSH]")); \
1551 /* Same but force premature exit if necessary. */
1552 #define FLUSH_BLOCK(s, eof) { \
1553 FLUSH_BLOCK_ONLY(s, eof); \
1554 if (s->strm->avail_out == 0) return (eof) ? finish_started : need_more; \
1557 /* ===========================================================================
1558 * Copy without compression as much as possible from the input stream, return
1559 * the current block state.
1560 * This function does not insert new strings in the dictionary since
1561 * uncompressible data is probably not useful. This function is used
1562 * only for the level=0 compression option.
1563 * NOTE: this function should be optimized to avoid extra copying from
1564 * window to pending_buf.
1566 local block_state deflate_stored(s, flush)
1570 /* Stored blocks are limited to 0xffff bytes, pending_buf is limited
1571 * to pending_buf_size, and each stored block has a 5 byte header:
1573 ulg max_block_size = 0xffff;
1576 if (max_block_size > s->pending_buf_size - 5) {
1577 max_block_size = s->pending_buf_size - 5;
1580 /* Copy as much as possible from input to output: */
1582 /* Fill the window as much as possible: */
1583 if (s->lookahead <= 1) {
1585 Assert(s->strstart < s->w_size+MAX_DIST(s) ||
1586 s->block_start >= (long)s->w_size, "slide too late");
1589 if (s->lookahead == 0 && flush == Z_NO_FLUSH) return need_more;
1591 if (s->lookahead == 0) break; /* flush the current block */
1593 Assert(s->block_start >= 0L, "block gone");
1595 s->strstart += s->lookahead;
1598 /* Emit a stored block if pending_buf will be full: */
1599 max_start = s->block_start + max_block_size;
1600 if (s->strstart == 0 || (ulg)s->strstart >= max_start) {
1601 /* strstart == 0 is possible when wraparound on 16-bit machine */
1602 s->lookahead = (uInt)(s->strstart - max_start);
1603 s->strstart = (uInt)max_start;
1606 /* Flush if we may have to slide, otherwise block_start may become
1607 * negative and the data will be gone:
1609 if (s->strstart - (uInt)s->block_start >= MAX_DIST(s)) {
1613 FLUSH_BLOCK(s, flush == Z_FINISH);
1614 return flush == Z_FINISH ? finish_done : block_done;
1617 /* ===========================================================================
1618 * Compress as much as possible from the input stream, return the current
1620 * This function does not perform lazy evaluation of matches and inserts
1621 * new strings in the dictionary only for unmatched strings or for short
1622 * matches. It is used only for the fast compression options.
1624 local block_state deflate_fast(s, flush)
1628 IPos hash_head = NIL; /* head of the hash chain */
1629 int bflush; /* set if current block must be flushed */
1632 /* Make sure that we always have enough lookahead, except
1633 * at the end of the input file. We need MAX_MATCH bytes
1634 * for the next match, plus MIN_MATCH bytes to insert the
1635 * string following the next match.
1637 if (s->lookahead < MIN_LOOKAHEAD) {
1639 if (s->lookahead < MIN_LOOKAHEAD && flush == Z_NO_FLUSH) {
1642 if (s->lookahead == 0) break; /* flush the current block */
1645 /* Insert the string window[strstart .. strstart+2] in the
1646 * dictionary, and set hash_head to the head of the hash chain:
1648 if (s->lookahead >= MIN_MATCH) {
1649 INSERT_STRING(s, s->strstart, hash_head);
1652 /* Find the longest match, discarding those <= prev_length.
1653 * At this point we have always match_length < MIN_MATCH
1655 if (hash_head != NIL && s->strstart - hash_head <= MAX_DIST(s)) {
1656 /* To simplify the code, we prevent matches with the string
1657 * of window index 0 (in particular we have to avoid a match
1658 * of the string with itself at the start of the input file).
1660 if (s->strategy != Z_HUFFMAN_ONLY) {
1661 s->match_length = longest_match (s, hash_head);
1663 /* longest_match() sets match_start */
1665 if (s->match_length >= MIN_MATCH) {
1666 check_match(s, s->strstart, s->match_start, s->match_length);
1668 bflush = _tr_tally(s, s->strstart - s->match_start,
1669 s->match_length - MIN_MATCH);
1671 s->lookahead -= s->match_length;
1673 /* Insert new strings in the hash table only if the match length
1674 * is not too large. This saves time but degrades compression.
1676 if (s->match_length <= s->max_insert_length &&
1677 s->lookahead >= MIN_MATCH) {
1678 s->match_length--; /* string at strstart already in hash table */
1681 INSERT_STRING(s, s->strstart, hash_head);
1682 /* strstart never exceeds WSIZE-MAX_MATCH, so there are
1683 * always MIN_MATCH bytes ahead.
1685 } while (--s->match_length != 0);
1688 s->strstart += s->match_length;
1689 s->match_length = 0;
1690 s->ins_h = s->window[s->strstart];
1691 UPDATE_HASH(s, s->ins_h, s->window[s->strstart+1]);
1693 Call UPDATE_HASH() MIN_MATCH-3 more times
1695 /* If lookahead < MIN_MATCH, ins_h is garbage, but it does not
1696 * matter since it will be recomputed at next deflate call.
1700 /* No match, output a literal byte */
1701 Tracevv((stderr,"%c", s->window[s->strstart]));
1702 bflush = _tr_tally (s, 0, s->window[s->strstart]);
1706 if (bflush) FLUSH_BLOCK(s, 0);
1708 FLUSH_BLOCK(s, flush == Z_FINISH);
1709 return flush == Z_FINISH ? finish_done : block_done;
1712 /* ===========================================================================
1713 * Same as above, but achieves better compression. We use a lazy
1714 * evaluation for matches: a match is finally adopted only if there is
1715 * no better match at the next window position.
1717 local block_state deflate_slow(s, flush)
1721 IPos hash_head = NIL; /* head of hash chain */
1722 int bflush; /* set if current block must be flushed */
1724 /* Process the input block. */
1726 /* Make sure that we always have enough lookahead, except
1727 * at the end of the input file. We need MAX_MATCH bytes
1728 * for the next match, plus MIN_MATCH bytes to insert the
1729 * string following the next match.
1731 if (s->lookahead < MIN_LOOKAHEAD) {
1733 if (s->lookahead < MIN_LOOKAHEAD && flush == Z_NO_FLUSH) {
1736 if (s->lookahead == 0) break; /* flush the current block */
1739 /* Insert the string window[strstart .. strstart+2] in the
1740 * dictionary, and set hash_head to the head of the hash chain:
1742 if (s->lookahead >= MIN_MATCH) {
1743 INSERT_STRING(s, s->strstart, hash_head);
1746 /* Find the longest match, discarding those <= prev_length.
1748 s->prev_length = s->match_length, s->prev_match = s->match_start;
1749 s->match_length = MIN_MATCH-1;
1751 if (hash_head != NIL && s->prev_length < s->max_lazy_match &&
1752 s->strstart - hash_head <= MAX_DIST(s)) {
1753 /* To simplify the code, we prevent matches with the string
1754 * of window index 0 (in particular we have to avoid a match
1755 * of the string with itself at the start of the input file).
1757 if (s->strategy != Z_HUFFMAN_ONLY) {
1758 s->match_length = longest_match (s, hash_head);
1760 /* longest_match() sets match_start */
1762 if (s->match_length <= 5 && (s->strategy == Z_FILTERED ||
1763 (s->match_length == MIN_MATCH &&
1764 s->strstart - s->match_start > TOO_FAR))) {
1766 /* If prev_match is also MIN_MATCH, match_start is garbage
1767 * but we will ignore the current match anyway.
1769 s->match_length = MIN_MATCH-1;
1772 /* If there was a match at the previous step and the current
1773 * match is not better, output the previous match:
1775 if (s->prev_length >= MIN_MATCH && s->match_length <= s->prev_length) {
1776 uInt max_insert = s->strstart + s->lookahead - MIN_MATCH;
1777 /* Do not insert strings in hash table beyond this. */
1779 check_match(s, s->strstart-1, s->prev_match, s->prev_length);
1781 bflush = _tr_tally(s, s->strstart -1 - s->prev_match,
1782 s->prev_length - MIN_MATCH);
1784 /* Insert in hash table all strings up to the end of the match.
1785 * strstart-1 and strstart are already inserted. If there is not
1786 * enough lookahead, the last two strings are not inserted in
1789 s->lookahead -= s->prev_length-1;
1790 s->prev_length -= 2;
1792 if (++s->strstart <= max_insert) {
1793 INSERT_STRING(s, s->strstart, hash_head);
1795 } while (--s->prev_length != 0);
1796 s->match_available = 0;
1797 s->match_length = MIN_MATCH-1;
1800 if (bflush) FLUSH_BLOCK(s, 0);
1802 } else if (s->match_available) {
1803 /* If there was no match at the previous position, output a
1804 * single literal. If there was a match but the current match
1805 * is longer, truncate the previous match to a single literal.
1807 Tracevv((stderr,"%c", s->window[s->strstart-1]));
1808 if (_tr_tally (s, 0, s->window[s->strstart-1])) {
1809 FLUSH_BLOCK_ONLY(s, 0);
1813 if (s->strm->avail_out == 0) return need_more;
1815 /* There is no previous match to compare with, wait for
1816 * the next step to decide.
1818 s->match_available = 1;
1823 Assert (flush != Z_NO_FLUSH, "no flush?");
1824 if (s->match_available) {
1825 Tracevv((stderr,"%c", s->window[s->strstart-1]));
1826 _tr_tally (s, 0, s->window[s->strstart-1]);
1827 s->match_available = 0;
1829 FLUSH_BLOCK(s, flush == Z_FINISH);
1830 return flush == Z_FINISH ? finish_done : block_done;
1835 /* trees.c -- output deflated data using Huffman coding
1836 * Copyright (C) 1995-1996 Jean-loup Gailly
1837 * For conditions of distribution and use, see copyright notice in zlib.h
1843 * The "deflation" process uses several Huffman trees. The more
1844 * common source values are represented by shorter bit sequences.
1846 * Each code tree is stored in a compressed form which is itself
1847 * a Huffman encoding of the lengths of all the code strings (in
1848 * ascending order by source values). The actual code strings are
1849 * reconstructed from the lengths in the inflate process, as described
1850 * in the deflate specification.
1854 * Deutsch, L.P.,"'Deflate' Compressed Data Format Specification".
1855 * Available in ftp.uu.net:/pub/archiving/zip/doc/deflate-1.1.doc
1858 * Data Compression: Methods and Theory, pp. 49-50.
1859 * Computer Science Press, 1988. ISBN 0-7167-8156-5.
1863 * Addison-Wesley, 1983. ISBN 0-201-06672-6.
1866 /* From: trees.c,v 1.11 1996/07/24 13:41:06 me Exp $ */
1868 /* #include "deflate.h" */
1874 /* ===========================================================================
1878 #define MAX_BL_BITS 7
1879 /* Bit length codes must not exceed MAX_BL_BITS bits */
1881 #define END_BLOCK 256
1882 /* end of block literal code */
1885 /* repeat previous bit length 3-6 times (2 bits of repeat count) */
1887 #define REPZ_3_10 17
1888 /* repeat a zero length 3-10 times (3 bits of repeat count) */
1890 #define REPZ_11_138 18
1891 /* repeat a zero length 11-138 times (7 bits of repeat count) */
1893 local int extra_lbits[LENGTH_CODES] /* extra bits for each length code */
1894 = {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};
1896 local int extra_dbits[D_CODES] /* extra bits for each distance code */
1897 = {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};
1899 local int extra_blbits[BL_CODES]/* extra bits for each bit length code */
1900 = {0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,2,3,7};
1902 local uch bl_order[BL_CODES]
1903 = {16,17,18,0,8,7,9,6,10,5,11,4,12,3,13,2,14,1,15};
1904 /* The lengths of the bit length codes are sent in order of decreasing
1905 * probability, to avoid transmitting the lengths for unused bit length codes.
1908 #define Buf_size (8 * 2*sizeof(char))
1909 /* Number of bits used within bi_buf. (bi_buf might be implemented on
1910 * more than 16 bits on some systems.)
1913 /* ===========================================================================
1914 * Local data. These are initialized only once.
1917 local ct_data static_ltree[L_CODES+2];
1918 /* The static literal tree. Since the bit lengths are imposed, there is no
1919 * need for the L_CODES extra codes used during heap construction. However
1920 * The codes 286 and 287 are needed to build a canonical tree (see _tr_init
1924 local ct_data static_dtree[D_CODES];
1925 /* The static distance tree. (Actually a trivial tree since all codes use
1929 local uch dist_code[512];
1930 /* distance codes. The first 256 values correspond to the distances
1931 * 3 .. 258, the last 256 values correspond to the top 8 bits of
1932 * the 15 bit distances.
1935 local uch length_code[MAX_MATCH-MIN_MATCH+1];
1936 /* length code for each normalized match length (0 == MIN_MATCH) */
1938 local int base_length[LENGTH_CODES];
1939 /* First normalized length for each code (0 = MIN_MATCH) */
1941 local int base_dist[D_CODES];
1942 /* First normalized distance for each code (0 = distance of 1) */
1944 struct static_tree_desc_s {
1945 ct_data *static_tree; /* static tree or NULL */
1946 intf *extra_bits; /* extra bits for each code or NULL */
1947 int extra_base; /* base index for extra_bits */
1948 int elems; /* max number of elements in the tree */
1949 int max_length; /* max bit length for the codes */
1952 local static_tree_desc static_l_desc =
1953 {static_ltree, extra_lbits, LITERALS+1, L_CODES, MAX_BITS};
1955 local static_tree_desc static_d_desc =
1956 {static_dtree, extra_dbits, 0, D_CODES, MAX_BITS};
1958 local static_tree_desc static_bl_desc =
1959 {(ct_data *)0, extra_blbits, 0, BL_CODES, MAX_BL_BITS};
1961 /* ===========================================================================
1962 * Local (static) routines in this file.
1965 local void tr_static_init OF((void));
1966 local void init_block OF((deflate_state *s));
1967 local void pqdownheap OF((deflate_state *s, ct_data *tree, int k));
1968 local void gen_bitlen OF((deflate_state *s, tree_desc *desc));
1969 local void gen_codes OF((ct_data *tree, int max_code, ushf *bl_count));
1970 local void build_tree OF((deflate_state *s, tree_desc *desc));
1971 local void scan_tree OF((deflate_state *s, ct_data *tree, int max_code));
1972 local void send_tree OF((deflate_state *s, ct_data *tree, int max_code));
1973 local int build_bl_tree OF((deflate_state *s));
1974 local void send_all_trees OF((deflate_state *s, int lcodes, int dcodes,
1976 local void compress_block OF((deflate_state *s, ct_data *ltree,
1978 local void set_data_type OF((deflate_state *s));
1979 local unsigned bi_reverse OF((unsigned value, int length));
1980 local void bi_windup OF((deflate_state *s));
1981 local void bi_flush OF((deflate_state *s));
1982 local void copy_block OF((deflate_state *s, charf *buf, unsigned len,
1986 # define send_code(s, c, tree) send_bits(s, tree[c].Code, tree[c].Len)
1987 /* Send a code of the given tree. c and tree must not have side effects */
1989 #else /* DEBUG_ZLIB */
1990 # define send_code(s, c, tree) \
1991 { if (verbose>2) fprintf(stderr,"\ncd %3d ",(c)); \
1992 send_bits(s, tree[c].Code, tree[c].Len); }
1995 #define d_code(dist) \
1996 ((dist) < 256 ? dist_code[dist] : dist_code[256+((dist)>>7)])
1997 /* Mapping from a distance to a distance code. dist is the distance - 1 and
1998 * must not have side effects. dist_code[256] and dist_code[257] are never
2002 /* ===========================================================================
2003 * Output a short LSB first on the stream.
2004 * IN assertion: there is enough room in pendingBuf.
2006 #define put_short(s, w) { \
2007 put_byte(s, (uch)((w) & 0xff)); \
2008 put_byte(s, (uch)((ush)(w) >> 8)); \
2011 /* ===========================================================================
2012 * Send a value on a given number of bits.
2013 * IN assertion: length <= 16 and value fits in length bits.
2016 local void send_bits OF((deflate_state *s, int value, int length));
2018 local void send_bits(s, value, length)
2020 int value; /* value to send */
2021 int length; /* number of bits */
2023 Tracevv((stderr," l %2d v %4x ", length, value));
2024 Assert(length > 0 && length <= 15, "invalid length");
2025 s->bits_sent += (ulg)length;
2027 /* If not enough room in bi_buf, use (valid) bits from bi_buf and
2028 * (16 - bi_valid) bits from value, leaving (width - (16-bi_valid))
2029 * unused bits in value.
2031 if (s->bi_valid > (int)Buf_size - length) {
2032 s->bi_buf |= (value << s->bi_valid);
2033 put_short(s, s->bi_buf);
2034 s->bi_buf = (ush)value >> (Buf_size - s->bi_valid);
2035 s->bi_valid += length - Buf_size;
2037 s->bi_buf |= value << s->bi_valid;
2038 s->bi_valid += length;
2041 #else /* !DEBUG_ZLIB */
2043 #define send_bits(s, value, length) \
2044 { int len = length;\
2045 if (s->bi_valid > (int)Buf_size - len) {\
2047 s->bi_buf |= (val << s->bi_valid);\
2048 put_short(s, s->bi_buf);\
2049 s->bi_buf = (ush)val >> (Buf_size - s->bi_valid);\
2050 s->bi_valid += len - Buf_size;\
2052 s->bi_buf |= (value) << s->bi_valid;\
2053 s->bi_valid += len;\
2056 #endif /* DEBUG_ZLIB */
2059 #define MAX(a,b) (a >= b ? a : b)
2060 /* the arguments must not have side effects */
2062 /* ===========================================================================
2063 * Initialize the various 'constant' tables. In a multi-threaded environment,
2064 * this function may be called by two threads concurrently, but this is
2065 * harmless since both invocations do exactly the same thing.
2067 local void tr_static_init()
2069 static int static_init_done = 0;
2070 int n; /* iterates over tree elements */
2071 int bits; /* bit counter */
2072 int length; /* length value */
2073 int code; /* code value */
2074 int dist; /* distance index */
2075 ush bl_count[MAX_BITS+1];
2076 /* number of codes at each bit length for an optimal tree */
2078 if (static_init_done) return;
2080 /* Initialize the mapping length (0..255) -> length code (0..28) */
2082 for (code = 0; code < LENGTH_CODES-1; code++) {
2083 base_length[code] = length;
2084 for (n = 0; n < (1<<extra_lbits[code]); n++) {
2085 length_code[length++] = (uch)code;
2088 Assert (length == 256, "tr_static_init: length != 256");
2089 /* Note that the length 255 (match length 258) can be represented
2090 * in two different ways: code 284 + 5 bits or code 285, so we
2091 * overwrite length_code[255] to use the best encoding:
2093 length_code[length-1] = (uch)code;
2095 /* Initialize the mapping dist (0..32K) -> dist code (0..29) */
2097 for (code = 0 ; code < 16; code++) {
2098 base_dist[code] = dist;
2099 for (n = 0; n < (1<<extra_dbits[code]); n++) {
2100 dist_code[dist++] = (uch)code;
2103 Assert (dist == 256, "tr_static_init: dist != 256");
2104 dist >>= 7; /* from now on, all distances are divided by 128 */
2105 for ( ; code < D_CODES; code++) {
2106 base_dist[code] = dist << 7;
2107 for (n = 0; n < (1<<(extra_dbits[code]-7)); n++) {
2108 dist_code[256 + dist++] = (uch)code;
2111 Assert (dist == 256, "tr_static_init: 256+dist != 512");
2113 /* Construct the codes of the static literal tree */
2114 for (bits = 0; bits <= MAX_BITS; bits++) bl_count[bits] = 0;
2116 while (n <= 143) static_ltree[n++].Len = 8, bl_count[8]++;
2117 while (n <= 255) static_ltree[n++].Len = 9, bl_count[9]++;
2118 while (n <= 279) static_ltree[n++].Len = 7, bl_count[7]++;
2119 while (n <= 287) static_ltree[n++].Len = 8, bl_count[8]++;
2120 /* Codes 286 and 287 do not exist, but we must include them in the
2121 * tree construction to get a canonical Huffman tree (longest code
2124 gen_codes((ct_data *)static_ltree, L_CODES+1, bl_count);
2126 /* The static distance tree is trivial: */
2127 for (n = 0; n < D_CODES; n++) {
2128 static_dtree[n].Len = 5;
2129 static_dtree[n].Code = bi_reverse((unsigned)n, 5);
2131 static_init_done = 1;
2134 /* ===========================================================================
2135 * Initialize the tree data structures for a new zlib stream.
2142 s->compressed_len = 0L;
2144 s->l_desc.dyn_tree = s->dyn_ltree;
2145 s->l_desc.stat_desc = &static_l_desc;
2147 s->d_desc.dyn_tree = s->dyn_dtree;
2148 s->d_desc.stat_desc = &static_d_desc;
2150 s->bl_desc.dyn_tree = s->bl_tree;
2151 s->bl_desc.stat_desc = &static_bl_desc;
2155 s->last_eob_len = 8; /* enough lookahead for inflate */
2160 /* Initialize the first block of the first file: */
2164 /* ===========================================================================
2165 * Initialize a new block.
2167 local void init_block(s)
2170 int n; /* iterates over tree elements */
2172 /* Initialize the trees. */
2173 for (n = 0; n < L_CODES; n++) s->dyn_ltree[n].Freq = 0;
2174 for (n = 0; n < D_CODES; n++) s->dyn_dtree[n].Freq = 0;
2175 for (n = 0; n < BL_CODES; n++) s->bl_tree[n].Freq = 0;
2177 s->dyn_ltree[END_BLOCK].Freq = 1;
2178 s->opt_len = s->static_len = 0L;
2179 s->last_lit = s->matches = 0;
2183 /* Index within the heap array of least frequent node in the Huffman tree */
2186 /* ===========================================================================
2187 * Remove the smallest element from the heap and recreate the heap with
2188 * one less element. Updates heap and heap_len.
2190 #define pqremove(s, tree, top) \
2192 top = s->heap[SMALLEST]; \
2193 s->heap[SMALLEST] = s->heap[s->heap_len--]; \
2194 pqdownheap(s, tree, SMALLEST); \
2197 /* ===========================================================================
2198 * Compares to subtrees, using the tree depth as tie breaker when
2199 * the subtrees have equal frequency. This minimizes the worst case length.
2201 #define smaller(tree, n, m, depth) \
2202 (tree[n].Freq < tree[m].Freq || \
2203 (tree[n].Freq == tree[m].Freq && depth[n] <= depth[m]))
2205 /* ===========================================================================
2206 * Restore the heap property by moving down the tree starting at node k,
2207 * exchanging a node with the smallest of its two sons if necessary, stopping
2208 * when the heap property is re-established (each father smaller than its
2211 local void pqdownheap(s, tree, k)
2213 ct_data *tree; /* the tree to restore */
2214 int k; /* node to move down */
2217 int j = k << 1; /* left son of k */
2218 while (j <= s->heap_len) {
2219 /* Set j to the smallest of the two sons: */
2220 if (j < s->heap_len &&
2221 smaller(tree, s->heap[j+1], s->heap[j], s->depth)) {
2224 /* Exit if v is smaller than both sons */
2225 if (smaller(tree, v, s->heap[j], s->depth)) break;
2227 /* Exchange v with the smallest son */
2228 s->heap[k] = s->heap[j]; k = j;
2230 /* And continue down the tree, setting j to the left son of k */
2236 /* ===========================================================================
2237 * Compute the optimal bit lengths for a tree and update the total bit length
2238 * for the current block.
2239 * IN assertion: the fields freq and dad are set, heap[heap_max] and
2240 * above are the tree nodes sorted by increasing frequency.
2241 * OUT assertions: the field len is set to the optimal bit length, the
2242 * array bl_count contains the frequencies for each bit length.
2243 * The length opt_len is updated; static_len is also updated if stree is
2246 local void gen_bitlen(s, desc)
2248 tree_desc *desc; /* the tree descriptor */
2250 ct_data *tree = desc->dyn_tree;
2251 int max_code = desc->max_code;
2252 ct_data *stree = desc->stat_desc->static_tree;
2253 intf *extra = desc->stat_desc->extra_bits;
2254 int base = desc->stat_desc->extra_base;
2255 int max_length = desc->stat_desc->max_length;
2256 int h; /* heap index */
2257 int n, m; /* iterate over the tree elements */
2258 int bits; /* bit length */
2259 int xbits; /* extra bits */
2260 ush f; /* frequency */
2261 int overflow = 0; /* number of elements with bit length too large */
2263 for (bits = 0; bits <= MAX_BITS; bits++) s->bl_count[bits] = 0;
2265 /* In a first pass, compute the optimal bit lengths (which may
2266 * overflow in the case of the bit length tree).
2268 tree[s->heap[s->heap_max]].Len = 0; /* root of the heap */
2270 for (h = s->heap_max+1; h < HEAP_SIZE; h++) {
2272 bits = tree[tree[n].Dad].Len + 1;
2273 if (bits > max_length) bits = max_length, overflow++;
2274 tree[n].Len = (ush)bits;
2275 /* We overwrite tree[n].Dad which is no longer needed */
2277 if (n > max_code) continue; /* not a leaf node */
2279 s->bl_count[bits]++;
2281 if (n >= base) xbits = extra[n-base];
2283 s->opt_len += (ulg)f * (bits + xbits);
2284 if (stree) s->static_len += (ulg)f * (stree[n].Len + xbits);
2286 if (overflow == 0) return;
2288 Trace((stderr,"\nbit length overflow\n"));
2289 /* This happens for example on obj2 and pic of the Calgary corpus */
2291 /* Find the first bit length which could increase: */
2293 bits = max_length-1;
2294 while (s->bl_count[bits] == 0) bits--;
2295 s->bl_count[bits]--; /* move one leaf down the tree */
2296 s->bl_count[bits+1] += 2; /* move one overflow item as its brother */
2297 s->bl_count[max_length]--;
2298 /* The brother of the overflow item also moves one step up,
2299 * but this does not affect bl_count[max_length]
2302 } while (overflow > 0);
2304 /* Now recompute all bit lengths, scanning in increasing frequency.
2305 * h is still equal to HEAP_SIZE. (It is simpler to reconstruct all
2306 * lengths instead of fixing only the wrong ones. This idea is taken
2307 * from 'ar' written by Haruhiko Okumura.)
2309 for (bits = max_length; bits != 0; bits--) {
2310 n = s->bl_count[bits];
2313 if (m > max_code) continue;
2314 if (tree[m].Len != (unsigned) bits) {
2315 Trace((stderr,"code %d bits %d->%d\n", m, tree[m].Len, bits));
2316 s->opt_len += ((long)bits - (long)tree[m].Len)
2317 *(long)tree[m].Freq;
2318 tree[m].Len = (ush)bits;
2325 /* ===========================================================================
2326 * Generate the codes for a given tree and bit counts (which need not be
2328 * IN assertion: the array bl_count contains the bit length statistics for
2329 * the given tree and the field len is set for all tree elements.
2330 * OUT assertion: the field code is set for all tree elements of non
2333 local void gen_codes (tree, max_code, bl_count)
2334 ct_data *tree; /* the tree to decorate */
2335 int max_code; /* largest code with non zero frequency */
2336 ushf *bl_count; /* number of codes at each bit length */
2338 ush next_code[MAX_BITS+1]; /* next code value for each bit length */
2339 ush code = 0; /* running code value */
2340 int bits; /* bit index */
2341 int n; /* code index */
2343 /* The distribution counts are first used to generate the code values
2344 * without bit reversal.
2346 for (bits = 1; bits <= MAX_BITS; bits++) {
2347 next_code[bits] = code = (code + bl_count[bits-1]) << 1;
2349 /* Check that the bit counts in bl_count are consistent. The last code
2352 Assert (code + bl_count[MAX_BITS]-1 == (1<<MAX_BITS)-1,
2353 "inconsistent bit counts");
2354 Tracev((stderr,"\ngen_codes: max_code %d ", max_code));
2356 for (n = 0; n <= max_code; n++) {
2357 int len = tree[n].Len;
2358 if (len == 0) continue;
2359 /* Now reverse the bits */
2360 tree[n].Code = bi_reverse(next_code[len]++, len);
2362 Tracecv(tree != static_ltree, (stderr,"\nn %3d %c l %2d c %4x (%x) ",
2363 n, (isgraph(n) ? n : ' '), len, tree[n].Code, next_code[len]-1));
2367 /* ===========================================================================
2368 * Construct one Huffman tree and assigns the code bit strings and lengths.
2369 * Update the total bit length for the current block.
2370 * IN assertion: the field freq is set for all tree elements.
2371 * OUT assertions: the fields len and code are set to the optimal bit length
2372 * and corresponding code. The length opt_len is updated; static_len is
2373 * also updated if stree is not null. The field max_code is set.
2375 local void build_tree(s, desc)
2377 tree_desc *desc; /* the tree descriptor */
2379 ct_data *tree = desc->dyn_tree;
2380 ct_data *stree = desc->stat_desc->static_tree;
2381 int elems = desc->stat_desc->elems;
2382 int n, m; /* iterate over heap elements */
2383 int max_code = -1; /* largest code with non zero frequency */
2384 int node; /* new node being created */
2386 /* Construct the initial heap, with least frequent element in
2387 * heap[SMALLEST]. The sons of heap[n] are heap[2*n] and heap[2*n+1].
2388 * heap[0] is not used.
2390 s->heap_len = 0, s->heap_max = HEAP_SIZE;
2392 for (n = 0; n < elems; n++) {
2393 if (tree[n].Freq != 0) {
2394 s->heap[++(s->heap_len)] = max_code = n;
2401 /* The pkzip format requires that at least one distance code exists,
2402 * and that at least one bit should be sent even if there is only one
2403 * possible code. So to avoid special checks later on we force at least
2404 * two codes of non zero frequency.
2406 while (s->heap_len < 2) {
2407 node = s->heap[++(s->heap_len)] = (max_code < 2 ? ++max_code : 0);
2408 tree[node].Freq = 1;
2410 s->opt_len--; if (stree) s->static_len -= stree[node].Len;
2411 /* node is 0 or 1 so it does not have extra bits */
2413 desc->max_code = max_code;
2415 /* The elements heap[heap_len/2+1 .. heap_len] are leaves of the tree,
2416 * establish sub-heaps of increasing lengths:
2418 for (n = s->heap_len/2; n >= 1; n--) pqdownheap(s, tree, n);
2420 /* Construct the Huffman tree by repeatedly combining the least two
2423 node = elems; /* next internal node of the tree */
2425 pqremove(s, tree, n); /* n = node of least frequency */
2426 m = s->heap[SMALLEST]; /* m = node of next least frequency */
2428 s->heap[--(s->heap_max)] = n; /* keep the nodes sorted by frequency */
2429 s->heap[--(s->heap_max)] = m;
2431 /* Create a new node father of n and m */
2432 tree[node].Freq = tree[n].Freq + tree[m].Freq;
2433 s->depth[node] = (uch) (MAX(s->depth[n], s->depth[m]) + 1);
2434 tree[n].Dad = tree[m].Dad = (ush)node;
2436 if (tree == s->bl_tree) {
2437 fprintf(stderr,"\nnode %d(%d), sons %d(%d) %d(%d)",
2438 node, tree[node].Freq, n, tree[n].Freq, m, tree[m].Freq);
2441 /* and insert the new node in the heap */
2442 s->heap[SMALLEST] = node++;
2443 pqdownheap(s, tree, SMALLEST);
2445 } while (s->heap_len >= 2);
2447 s->heap[--(s->heap_max)] = s->heap[SMALLEST];
2449 /* At this point, the fields freq and dad are set. We can now
2450 * generate the bit lengths.
2452 gen_bitlen(s, (tree_desc *)desc);
2454 /* The field len is now set, we can generate the bit codes */
2455 gen_codes ((ct_data *)tree, max_code, s->bl_count);
2458 /* ===========================================================================
2459 * Scan a literal or distance tree to determine the frequencies of the codes
2460 * in the bit length tree.
2462 local void scan_tree (s, tree, max_code)
2464 ct_data *tree; /* the tree to be scanned */
2465 int max_code; /* and its largest code of non zero frequency */
2467 int n; /* iterates over all tree elements */
2468 int prevlen = -1; /* last emitted length */
2469 int curlen; /* length of current code */
2470 int nextlen = tree[0].Len; /* length of next code */
2471 int count = 0; /* repeat count of the current code */
2472 int max_count = 7; /* max repeat count */
2473 int min_count = 4; /* min repeat count */
2475 if (nextlen == 0) max_count = 138, min_count = 3;
2476 tree[max_code+1].Len = (ush)0xffff; /* guard */
2478 for (n = 0; n <= max_code; n++) {
2479 curlen = nextlen; nextlen = tree[n+1].Len;
2480 if (++count < max_count && curlen == nextlen) {
2482 } else if (count < min_count) {
2483 s->bl_tree[curlen].Freq += count;
2484 } else if (curlen != 0) {
2485 if (curlen != prevlen) s->bl_tree[curlen].Freq++;
2486 s->bl_tree[REP_3_6].Freq++;
2487 } else if (count <= 10) {
2488 s->bl_tree[REPZ_3_10].Freq++;
2490 s->bl_tree[REPZ_11_138].Freq++;
2492 count = 0; prevlen = curlen;
2494 max_count = 138, min_count = 3;
2495 } else if (curlen == nextlen) {
2496 max_count = 6, min_count = 3;
2498 max_count = 7, min_count = 4;
2503 /* ===========================================================================
2504 * Send a literal or distance tree in compressed form, using the codes in
2507 local void send_tree (s, tree, max_code)
2509 ct_data *tree; /* the tree to be scanned */
2510 int max_code; /* and its largest code of non zero frequency */
2512 int n; /* iterates over all tree elements */
2513 int prevlen = -1; /* last emitted length */
2514 int curlen; /* length of current code */
2515 int nextlen = tree[0].Len; /* length of next code */
2516 int count = 0; /* repeat count of the current code */
2517 int max_count = 7; /* max repeat count */
2518 int min_count = 4; /* min repeat count */
2520 /* tree[max_code+1].Len = -1; */ /* guard already set */
2521 if (nextlen == 0) max_count = 138, min_count = 3;
2523 for (n = 0; n <= max_code; n++) {
2524 curlen = nextlen; nextlen = tree[n+1].Len;
2525 if (++count < max_count && curlen == nextlen) {
2527 } else if (count < min_count) {
2528 do { send_code(s, curlen, s->bl_tree); } while (--count != 0);
2530 } else if (curlen != 0) {
2531 if (curlen != prevlen) {
2532 send_code(s, curlen, s->bl_tree); count--;
2534 Assert(count >= 3 && count <= 6, " 3_6?");
2535 send_code(s, REP_3_6, s->bl_tree); send_bits(s, count-3, 2);
2537 } else if (count <= 10) {
2538 send_code(s, REPZ_3_10, s->bl_tree); send_bits(s, count-3, 3);
2541 send_code(s, REPZ_11_138, s->bl_tree); send_bits(s, count-11, 7);
2543 count = 0; prevlen = curlen;
2545 max_count = 138, min_count = 3;
2546 } else if (curlen == nextlen) {
2547 max_count = 6, min_count = 3;
2549 max_count = 7, min_count = 4;
2554 /* ===========================================================================
2555 * Construct the Huffman tree for the bit lengths and return the index in
2556 * bl_order of the last bit length code to send.
2558 local int build_bl_tree(s)
2561 int max_blindex; /* index of last bit length code of non zero freq */
2563 /* Determine the bit length frequencies for literal and distance trees */
2564 scan_tree(s, (ct_data *)s->dyn_ltree, s->l_desc.max_code);
2565 scan_tree(s, (ct_data *)s->dyn_dtree, s->d_desc.max_code);
2567 /* Build the bit length tree: */
2568 build_tree(s, (tree_desc *)(&(s->bl_desc)));
2569 /* opt_len now includes the length of the tree representations, except
2570 * the lengths of the bit lengths codes and the 5+5+4 bits for the counts.
2573 /* Determine the number of bit length codes to send. The pkzip format
2574 * requires that at least 4 bit length codes be sent. (appnote.txt says
2575 * 3 but the actual value used is 4.)
2577 for (max_blindex = BL_CODES-1; max_blindex >= 3; max_blindex--) {
2578 if (s->bl_tree[bl_order[max_blindex]].Len != 0) break;
2580 /* Update opt_len to include the bit length tree and counts */
2581 s->opt_len += 3*(max_blindex+1) + 5+5+4;
2582 Tracev((stderr, "\ndyn trees: dyn %ld, stat %ld",
2583 s->opt_len, s->static_len));
2588 /* ===========================================================================
2589 * Send the header for a block using dynamic Huffman trees: the counts, the
2590 * lengths of the bit length codes, the literal tree and the distance tree.
2591 * IN assertion: lcodes >= 257, dcodes >= 1, blcodes >= 4.
2593 local void send_all_trees(s, lcodes, dcodes, blcodes)
2595 int lcodes, dcodes, blcodes; /* number of codes for each tree */
2597 int rank; /* index in bl_order */
2599 Assert (lcodes >= 257 && dcodes >= 1 && blcodes >= 4, "not enough codes");
2600 Assert (lcodes <= L_CODES && dcodes <= D_CODES && blcodes <= BL_CODES,
2602 Tracev((stderr, "\nbl counts: "));
2603 send_bits(s, lcodes-257, 5); /* not +255 as stated in appnote.txt */
2604 send_bits(s, dcodes-1, 5);
2605 send_bits(s, blcodes-4, 4); /* not -3 as stated in appnote.txt */
2606 for (rank = 0; rank < blcodes; rank++) {
2607 Tracev((stderr, "\nbl code %2d ", bl_order[rank]));
2608 send_bits(s, s->bl_tree[bl_order[rank]].Len, 3);
2610 Tracev((stderr, "\nbl tree: sent %ld", s->bits_sent));
2612 send_tree(s, (ct_data *)s->dyn_ltree, lcodes-1); /* literal tree */
2613 Tracev((stderr, "\nlit tree: sent %ld", s->bits_sent));
2615 send_tree(s, (ct_data *)s->dyn_dtree, dcodes-1); /* distance tree */
2616 Tracev((stderr, "\ndist tree: sent %ld", s->bits_sent));
2619 /* ===========================================================================
2620 * Send a stored block
2622 void _tr_stored_block(s, buf, stored_len, eof)
2624 charf *buf; /* input block */
2625 ulg stored_len; /* length of input block */
2626 int eof; /* true if this is the last block for a file */
2628 send_bits(s, (STORED_BLOCK<<1)+eof, 3); /* send block type */
2629 s->compressed_len = (s->compressed_len + 3 + 7) & (ulg)~7L;
2630 s->compressed_len += (stored_len + 4) << 3;
2632 copy_block(s, buf, (unsigned)stored_len, 1); /* with header */
2635 /* Send just the `stored block' type code without any length bytes or data.
2637 void _tr_stored_type_only(s)
2640 send_bits(s, (STORED_BLOCK << 1), 3);
2642 s->compressed_len = (s->compressed_len + 3) & ~7L;
2646 /* ===========================================================================
2647 * Send one empty static block to give enough lookahead for inflate.
2648 * This takes 10 bits, of which 7 may remain in the bit buffer.
2649 * The current inflate code requires 9 bits of lookahead. If the
2650 * last two codes for the previous block (real code plus EOB) were coded
2651 * on 5 bits or less, inflate may have only 5+3 bits of lookahead to decode
2652 * the last real code. In this case we send two empty static blocks instead
2653 * of one. (There are no problems if the previous block is stored or fixed.)
2654 * To simplify the code, we assume the worst case of last real code encoded
2660 send_bits(s, STATIC_TREES<<1, 3);
2661 send_code(s, END_BLOCK, static_ltree);
2662 s->compressed_len += 10L; /* 3 for block type, 7 for EOB */
2664 /* Of the 10 bits for the empty block, we have already sent
2665 * (10 - bi_valid) bits. The lookahead for the last real code (before
2666 * the EOB of the previous block) was thus at least one plus the length
2667 * of the EOB plus what we have just sent of the empty static block.
2669 if (1 + s->last_eob_len + 10 - s->bi_valid < 9) {
2670 send_bits(s, STATIC_TREES<<1, 3);
2671 send_code(s, END_BLOCK, static_ltree);
2672 s->compressed_len += 10L;
2675 s->last_eob_len = 7;
2678 /* ===========================================================================
2679 * Determine the best encoding for the current block: dynamic trees, static
2680 * trees or store, and output the encoded block to the zip file. This function
2681 * returns the total compressed length for the file so far.
2683 ulg _tr_flush_block(s, buf, stored_len, eof)
2685 charf *buf; /* input block, or NULL if too old */
2686 ulg stored_len; /* length of input block */
2687 int eof; /* true if this is the last block for a file */
2689 ulg opt_lenb, static_lenb; /* opt_len and static_len in bytes */
2690 int max_blindex = 0; /* index of last bit length code of non zero freq */
2692 /* Build the Huffman trees unless a stored block is forced */
2695 /* Check if the file is ascii or binary */
2696 if (s->data_type == Z_UNKNOWN) set_data_type(s);
2698 /* Construct the literal and distance trees */
2699 build_tree(s, (tree_desc *)(&(s->l_desc)));
2700 Tracev((stderr, "\nlit data: dyn %ld, stat %ld", s->opt_len,
2703 build_tree(s, (tree_desc *)(&(s->d_desc)));
2704 Tracev((stderr, "\ndist data: dyn %ld, stat %ld", s->opt_len,
2706 /* At this point, opt_len and static_len are the total bit lengths of
2707 * the compressed block data, excluding the tree representations.
2710 /* Build the bit length tree for the above two trees, and get the index
2711 * in bl_order of the last bit length code to send.
2713 max_blindex = build_bl_tree(s);
2715 /* Determine the best encoding. Compute first the block length in bytes*/
2716 opt_lenb = (s->opt_len+3+7)>>3;
2717 static_lenb = (s->static_len+3+7)>>3;
2719 Tracev((stderr, "\nopt %lu(%lu) stat %lu(%lu) stored %lu lit %u ",
2720 opt_lenb, s->opt_len, static_lenb, s->static_len, stored_len,
2723 if (static_lenb <= opt_lenb) opt_lenb = static_lenb;
2726 Assert(buf != (char*)0, "lost buf");
2727 opt_lenb = static_lenb = stored_len + 5; /* force a stored block */
2730 /* If compression failed and this is the first and last block,
2731 * and if the .zip file can be seeked (to rewrite the local header),
2732 * the whole file is transformed into a stored file:
2734 #ifdef STORED_FILE_OK
2735 # ifdef FORCE_STORED_FILE
2736 if (eof && s->compressed_len == 0L) { /* force stored file */
2738 if (stored_len <= opt_lenb && eof && s->compressed_len==0L && seekable()) {
2740 /* Since LIT_BUFSIZE <= 2*WSIZE, the input data must be there: */
2741 if (buf == (charf*)0) error ("block vanished");
2743 copy_block(s, buf, (unsigned)stored_len, 0); /* without header */
2744 s->compressed_len = stored_len << 3;
2747 #endif /* STORED_FILE_OK */
2750 if (buf != (char*)0) { /* force stored block */
2752 if (stored_len+4 <= opt_lenb && buf != (char*)0) {
2753 /* 4: two words for the lengths */
2755 /* The test buf != NULL is only necessary if LIT_BUFSIZE > WSIZE.
2756 * Otherwise we can't have processed more than WSIZE input bytes since
2757 * the last block flush, because compression would have been
2758 * successful. If LIT_BUFSIZE <= WSIZE, it is never too late to
2759 * transform a block into a stored block.
2761 _tr_stored_block(s, buf, stored_len, eof);
2764 } else if (static_lenb >= 0) { /* force static trees */
2766 } else if (static_lenb == opt_lenb) {
2768 send_bits(s, (STATIC_TREES<<1)+eof, 3);
2769 compress_block(s, (ct_data *)static_ltree, (ct_data *)static_dtree);
2770 s->compressed_len += 3 + s->static_len;
2772 send_bits(s, (DYN_TREES<<1)+eof, 3);
2773 send_all_trees(s, s->l_desc.max_code+1, s->d_desc.max_code+1,
2775 compress_block(s, (ct_data *)s->dyn_ltree, (ct_data *)s->dyn_dtree);
2776 s->compressed_len += 3 + s->opt_len;
2778 Assert (s->compressed_len == s->bits_sent, "bad compressed size");
2783 s->compressed_len += 7; /* align on byte boundary */
2785 Tracev((stderr,"\ncomprlen %lu(%lu) ", s->compressed_len>>3,
2786 s->compressed_len-7*eof));
2788 return s->compressed_len >> 3;
2791 /* ===========================================================================
2792 * Save the match info and tally the frequency counts. Return true if
2793 * the current block must be flushed.
2795 int _tr_tally (s, dist, lc)
2797 unsigned dist; /* distance of matched string */
2798 unsigned lc; /* match length-MIN_MATCH or unmatched char (if dist==0) */
2800 s->d_buf[s->last_lit] = (ush)dist;
2801 s->l_buf[s->last_lit++] = (uch)lc;
2803 /* lc is the unmatched char */
2804 s->dyn_ltree[lc].Freq++;
2807 /* Here, lc is the match length - MIN_MATCH */
2808 dist--; /* dist = match distance - 1 */
2809 Assert((ush)dist < (ush)MAX_DIST(s) &&
2810 (ush)lc <= (ush)(MAX_MATCH-MIN_MATCH) &&
2811 (ush)d_code(dist) < (ush)D_CODES, "_tr_tally: bad match");
2813 s->dyn_ltree[length_code[lc]+LITERALS+1].Freq++;
2814 s->dyn_dtree[d_code(dist)].Freq++;
2817 /* Try to guess if it is profitable to stop the current block here */
2818 if (s->level > 2 && (s->last_lit & 0xfff) == 0) {
2819 /* Compute an upper bound for the compressed length */
2820 ulg out_length = (ulg)s->last_lit*8L;
2821 ulg in_length = (ulg)((long)s->strstart - s->block_start);
2823 for (dcode = 0; dcode < D_CODES; dcode++) {
2824 out_length += (ulg)s->dyn_dtree[dcode].Freq *
2825 (5L+extra_dbits[dcode]);
2828 Tracev((stderr,"\nlast_lit %u, in %ld, out ~%ld(%ld%%) ",
2829 s->last_lit, in_length, out_length,
2830 100L - out_length*100L/in_length));
2831 if (s->matches < s->last_lit/2 && out_length < in_length/2) return 1;
2833 return (s->last_lit == s->lit_bufsize-1);
2834 /* We avoid equality with lit_bufsize because of wraparound at 64K
2835 * on 16 bit machines and because stored blocks are restricted to
2840 /* ===========================================================================
2841 * Send the block data compressed using the given Huffman trees
2843 local void compress_block(s, ltree, dtree)
2845 ct_data *ltree; /* literal tree */
2846 ct_data *dtree; /* distance tree */
2848 unsigned dist; /* distance of matched string */
2849 int lc; /* match length or unmatched char (if dist == 0) */
2850 unsigned lx = 0; /* running index in l_buf */
2851 unsigned code; /* the code to send */
2852 int extra; /* number of extra bits to send */
2854 if (s->last_lit != 0) do {
2855 dist = s->d_buf[lx];
2856 lc = s->l_buf[lx++];
2858 send_code(s, lc, ltree); /* send a literal byte */
2859 Tracecv(isgraph(lc), (stderr," '%c' ", lc));
2861 /* Here, lc is the match length - MIN_MATCH */
2862 code = length_code[lc];
2863 send_code(s, code+LITERALS+1, ltree); /* send the length code */
2864 extra = extra_lbits[code];
2866 lc -= base_length[code];
2867 send_bits(s, lc, extra); /* send the extra length bits */
2869 dist--; /* dist is now the match distance - 1 */
2870 code = d_code(dist);
2871 Assert (code < D_CODES, "bad d_code");
2873 send_code(s, code, dtree); /* send the distance code */
2874 extra = extra_dbits[code];
2876 dist -= base_dist[code];
2877 send_bits(s, dist, extra); /* send the extra distance bits */
2879 } /* literal or match pair ? */
2881 /* Check that the overlay between pending_buf and d_buf+l_buf is ok: */
2882 Assert(s->pending < s->lit_bufsize + 2*lx, "pendingBuf overflow");
2884 } while (lx < s->last_lit);
2886 send_code(s, END_BLOCK, ltree);
2887 s->last_eob_len = ltree[END_BLOCK].Len;
2890 /* ===========================================================================
2891 * Set the data type to ASCII or BINARY, using a crude approximation:
2892 * binary if more than 20% of the bytes are <= 6 or >= 128, ascii otherwise.
2893 * IN assertion: the fields freq of dyn_ltree are set and the total of all
2894 * frequencies does not exceed 64K (to fit in an int on 16 bit machines).
2896 local void set_data_type(s)
2900 unsigned ascii_freq = 0;
2901 unsigned bin_freq = 0;
2902 while (n < 7) bin_freq += s->dyn_ltree[n++].Freq;
2903 while (n < 128) ascii_freq += s->dyn_ltree[n++].Freq;
2904 while (n < LITERALS) bin_freq += s->dyn_ltree[n++].Freq;
2905 s->data_type = (Byte)(bin_freq > (ascii_freq >> 2) ? Z_BINARY : Z_ASCII);
2908 /* ===========================================================================
2909 * Reverse the first len bits of a code, using straightforward code (a faster
2910 * method would use a table)
2911 * IN assertion: 1 <= len <= 15
2913 local unsigned bi_reverse(code, len)
2914 unsigned code; /* the value to invert */
2915 int len; /* its bit length */
2917 register unsigned res = 0;
2920 code >>= 1, res <<= 1;
2921 } while (--len > 0);
2925 /* ===========================================================================
2926 * Flush the bit buffer, keeping at most 7 bits in it.
2928 local void bi_flush(s)
2931 if (s->bi_valid == 16) {
2932 put_short(s, s->bi_buf);
2935 } else if (s->bi_valid >= 8) {
2936 put_byte(s, (Byte)s->bi_buf);
2942 /* ===========================================================================
2943 * Flush the bit buffer and align the output on a byte boundary
2945 local void bi_windup(s)
2948 if (s->bi_valid > 8) {
2949 put_short(s, s->bi_buf);
2950 } else if (s->bi_valid > 0) {
2951 put_byte(s, (Byte)s->bi_buf);
2956 s->bits_sent = (s->bits_sent+7) & ~7;
2960 /* ===========================================================================
2961 * Copy a stored block, storing first the length and its
2962 * one's complement if requested.
2964 local void copy_block(s, buf, len, header)
2966 charf *buf; /* the input data */
2967 unsigned len; /* its length */
2968 int header; /* true if block header must be written */
2970 bi_windup(s); /* align on byte boundary */
2971 s->last_eob_len = 8; /* enough lookahead for inflate */
2974 put_short(s, (ush)len);
2975 put_short(s, (ush)~len);
2977 s->bits_sent += 2*16;
2981 s->bits_sent += (ulg)len<<3;
2983 /* bundle up the put_byte(s, *buf++) calls */
2984 zmemcpy(&s->pending_buf[s->pending], buf, len);
2990 /* inflate.c -- zlib interface to inflate modules
2991 * Copyright (C) 1995-1996 Mark Adler
2992 * For conditions of distribution and use, see copyright notice in zlib.h
2995 /* #include "zutil.h" */
2997 /* +++ infblock.h */
2998 /* infblock.h -- header to use infblock.c
2999 * Copyright (C) 1995-1996 Mark Adler
3000 * For conditions of distribution and use, see copyright notice in zlib.h
3003 /* WARNING: this file should *not* be used by applications. It is
3004 part of the implementation of the compression library and is
3005 subject to change. Applications should only use zlib.h.
3008 struct inflate_blocks_state;
3009 typedef struct inflate_blocks_state FAR inflate_blocks_statef;
3011 extern inflate_blocks_statef * inflate_blocks_new OF((
3013 check_func c, /* check function */
3014 uInt w)); /* window size */
3016 extern int inflate_blocks OF((
3017 inflate_blocks_statef *,
3019 int)); /* initial return code */
3021 extern void inflate_blocks_reset OF((
3022 inflate_blocks_statef *,
3024 uLongf *)); /* check value on output */
3026 extern int inflate_blocks_free OF((
3027 inflate_blocks_statef *,
3029 uLongf *)); /* check value on output */
3031 extern void inflate_set_dictionary OF((
3032 inflate_blocks_statef *s,
3033 const Bytef *d, /* dictionary */
3034 uInt n)); /* dictionary length */
3036 extern int inflate_addhistory OF((
3037 inflate_blocks_statef *,
3040 extern int inflate_packet_flush OF((
3041 inflate_blocks_statef *));
3042 /* --- infblock.h */
3044 #ifndef NO_DUMMY_DECL
3045 struct inflate_blocks_state {int dummy;}; /* for buggy compilers */
3048 /* inflate private state */
3049 struct internal_state {
3053 METHOD, /* waiting for method byte */
3054 FLAG, /* waiting for flag byte */
3055 DICT4, /* four dictionary check bytes to go */
3056 DICT3, /* three dictionary check bytes to go */
3057 DICT2, /* two dictionary check bytes to go */
3058 DICT1, /* one dictionary check byte to go */
3059 DICT0, /* waiting for inflateSetDictionary */
3060 BLOCKS, /* decompressing blocks */
3061 CHECK4, /* four check bytes to go */
3062 CHECK3, /* three check bytes to go */
3063 CHECK2, /* two check bytes to go */
3064 CHECK1, /* one check byte to go */
3065 DONE, /* finished check, done */
3066 BAD} /* got an error--stay here */
3067 mode; /* current inflate mode */
3069 /* mode dependent information */
3071 uInt method; /* if FLAGS, method byte */
3073 uLong was; /* computed check value */
3074 uLong need; /* stream check value */
3075 } check; /* if CHECK, check values to compare */
3076 uInt marker; /* if BAD, inflateSync's marker bytes count */
3077 } sub; /* submode */
3079 /* mode independent information */
3080 int nowrap; /* flag for no wrapper */
3081 uInt wbits; /* log2(window size) (8..15, defaults to 15) */
3082 inflate_blocks_statef
3083 *blocks; /* current inflate_blocks state */
3093 if (z == Z_NULL || z->state == Z_NULL)
3094 return Z_STREAM_ERROR;
3095 z->total_in = z->total_out = 0;
3097 z->state->mode = z->state->nowrap ? BLOCKS : METHOD;
3098 inflate_blocks_reset(z->state->blocks, z, &c);
3099 Trace((stderr, "inflate: reset\n"));
3109 if (z == Z_NULL || z->state == Z_NULL || z->zfree == Z_NULL)
3110 return Z_STREAM_ERROR;
3111 if (z->state->blocks != Z_NULL)
3112 inflate_blocks_free(z->state->blocks, z, &c);
3115 Trace((stderr, "inflate: end\n"));
3120 int inflateInit2_(z, w, version, stream_size)
3123 const char *version;
3126 if (version == Z_NULL || version[0] != ZLIB_VERSION[0] ||
3127 stream_size != sizeof(z_stream))
3128 return Z_VERSION_ERROR;
3130 /* initialize state */
3132 return Z_STREAM_ERROR;
3135 if (z->zalloc == Z_NULL)
3137 z->zalloc = zcalloc;
3138 z->opaque = (voidpf)0;
3140 if (z->zfree == Z_NULL) z->zfree = zcfree;
3142 if ((z->state = (struct internal_state FAR *)
3143 ZALLOC(z,1,sizeof(struct internal_state))) == Z_NULL)
3145 z->state->blocks = Z_NULL;
3147 /* handle undocumented nowrap option (no zlib header or check) */
3148 z->state->nowrap = 0;
3152 z->state->nowrap = 1;
3155 /* set window size */
3156 if (w < 8 || w > 15)
3159 return Z_STREAM_ERROR;
3161 z->state->wbits = (uInt)w;
3163 /* create inflate_blocks state */
3164 if ((z->state->blocks =
3165 inflate_blocks_new(z, z->state->nowrap ? Z_NULL : adler32, (uInt)1 << w))
3171 Trace((stderr, "inflate: allocated\n"));
3179 int inflateInit_(z, version, stream_size)
3181 const char *version;
3184 return inflateInit2_(z, DEF_WBITS, version, stream_size);
3188 #define NEEDBYTE {if(z->avail_in==0)goto empty;r=Z_OK;}
3189 #define NEXTBYTE (z->avail_in--,z->total_in++,*z->next_in++)
3198 if (z == Z_NULL || z->state == Z_NULL || z->next_in == Z_NULL || f < 0)
3199 return Z_STREAM_ERROR;
3201 while (1) switch (z->state->mode)
3205 if (((z->state->sub.method = NEXTBYTE) & 0xf) != Z_DEFLATED)
3207 z->state->mode = BAD;
3208 z->msg = (char*)"unknown compression method";
3209 z->state->sub.marker = 5; /* can't try inflateSync */
3212 if ((z->state->sub.method >> 4) + 8 > z->state->wbits)
3214 z->state->mode = BAD;
3215 z->msg = (char*)"invalid window size";
3216 z->state->sub.marker = 5; /* can't try inflateSync */
3219 z->state->mode = FLAG;
3223 if (((z->state->sub.method << 8) + b) % 31)
3225 z->state->mode = BAD;
3226 z->msg = (char*)"incorrect header check";
3227 z->state->sub.marker = 5; /* can't try inflateSync */
3230 Trace((stderr, "inflate: zlib header ok\n"));
3231 if (!(b & PRESET_DICT))
3233 z->state->mode = BLOCKS;
3236 z->state->mode = DICT4;
3239 z->state->sub.check.need = (uLong)NEXTBYTE << 24;
3240 z->state->mode = DICT3;
3243 z->state->sub.check.need += (uLong)NEXTBYTE << 16;
3244 z->state->mode = DICT2;
3247 z->state->sub.check.need += (uLong)NEXTBYTE << 8;
3248 z->state->mode = DICT1;
3251 z->state->sub.check.need += (uLong)NEXTBYTE;
3252 z->adler = z->state->sub.check.need;
3253 z->state->mode = DICT0;
3256 z->state->mode = BAD;
3257 z->msg = (char*)"need dictionary";
3258 z->state->sub.marker = 0; /* can try inflateSync */
3259 return Z_STREAM_ERROR;
3261 r = inflate_blocks(z->state->blocks, z, r);
3262 if (f == Z_PACKET_FLUSH && z->avail_in == 0 && z->avail_out != 0)
3263 r = inflate_packet_flush(z->state->blocks);
3264 if (r == Z_DATA_ERROR)
3266 z->state->mode = BAD;
3267 z->state->sub.marker = 0; /* can try inflateSync */
3270 if (r != Z_STREAM_END)
3273 inflate_blocks_reset(z->state->blocks, z, &z->state->sub.check.was);
3274 if (z->state->nowrap)
3276 z->state->mode = DONE;
3279 z->state->mode = CHECK4;
3282 z->state->sub.check.need = (uLong)NEXTBYTE << 24;
3283 z->state->mode = CHECK3;
3286 z->state->sub.check.need += (uLong)NEXTBYTE << 16;
3287 z->state->mode = CHECK2;
3290 z->state->sub.check.need += (uLong)NEXTBYTE << 8;
3291 z->state->mode = CHECK1;
3294 z->state->sub.check.need += (uLong)NEXTBYTE;
3296 if (z->state->sub.check.was != z->state->sub.check.need)
3298 z->state->mode = BAD;
3299 z->msg = (char*)"incorrect data check";
3300 z->state->sub.marker = 5; /* can't try inflateSync */
3303 Trace((stderr, "inflate: zlib check ok\n"));
3304 z->state->mode = DONE;
3306 return Z_STREAM_END;
3308 return Z_DATA_ERROR;
3310 return Z_STREAM_ERROR;
3314 if (f != Z_PACKET_FLUSH)
3316 z->state->mode = BAD;
3317 z->msg = (char *)"need more for packet flush";
3318 z->state->sub.marker = 0; /* can try inflateSync */
3319 return Z_DATA_ERROR;
3323 int inflateSetDictionary(z, dictionary, dictLength)
3325 const Bytef *dictionary;
3328 uInt length = dictLength;
3330 if (z == Z_NULL || z->state == Z_NULL || z->state->mode != DICT0)
3331 return Z_STREAM_ERROR;
3333 if (adler32(1L, dictionary, dictLength) != z->adler) return Z_DATA_ERROR;
3336 if (length >= ((uInt)1<<z->state->wbits))
3338 length = (1<<z->state->wbits)-1;
3339 dictionary += dictLength - length;
3341 inflate_set_dictionary(z->state->blocks, dictionary, length);
3342 z->state->mode = BLOCKS;
3347 * This subroutine adds the data at next_in/avail_in to the output history
3348 * without performing any output. The output buffer must be "caught up";
3349 * i.e. no pending output (hence s->read equals s->write), and the state must
3350 * be BLOCKS (i.e. we should be willing to see the start of a series of
3351 * BLOCKS). On exit, the output will also be caught up, and the checksum
3352 * will have been updated if need be.
3355 int inflateIncomp(z)
3358 if (z->state->mode != BLOCKS)
3359 return Z_DATA_ERROR;
3360 return inflate_addhistory(z->state->blocks, z);
3367 uInt n; /* number of bytes to look at */
3368 Bytef *p; /* pointer to bytes */
3369 uInt m; /* number of marker bytes found in a row */
3370 uLong r, w; /* temporaries to save total_in and total_out */
3373 if (z == Z_NULL || z->state == Z_NULL)
3374 return Z_STREAM_ERROR;
3375 if (z->state->mode != BAD)
3377 z->state->mode = BAD;
3378 z->state->sub.marker = 0;
3380 if ((n = z->avail_in) == 0)
3383 m = z->state->sub.marker;
3388 if (*p == (Byte)(m < 2 ? 0 : 0xff))
3398 z->total_in += p - z->next_in;
3401 z->state->sub.marker = m;
3403 /* return no joy or set up to restart on a new block */
3405 return Z_DATA_ERROR;
3406 r = z->total_in; w = z->total_out;
3408 z->total_in = r; z->total_out = w;
3409 z->state->mode = BLOCKS;
3417 /* +++ infblock.c */
3418 /* infblock.c -- interpret and process block types to last block
3419 * Copyright (C) 1995-1996 Mark Adler
3420 * For conditions of distribution and use, see copyright notice in zlib.h
3423 /* #include "zutil.h" */
3424 /* #include "infblock.h" */
3426 /* +++ inftrees.h */
3427 /* inftrees.h -- header to use inftrees.c
3428 * Copyright (C) 1995-1996 Mark Adler
3429 * For conditions of distribution and use, see copyright notice in zlib.h
3432 /* WARNING: this file should *not* be used by applications. It is
3433 part of the implementation of the compression library and is
3434 subject to change. Applications should only use zlib.h.
3437 /* Huffman code lookup table entry--this entry is four bytes for machines
3438 that have 16-bit pointers (e.g. PC's in the small or medium model). */
3440 typedef struct inflate_huft_s FAR inflate_huft;
3442 struct inflate_huft_s {
3445 Byte Exop; /* number of extra bits or operation */
3446 Byte Bits; /* number of bits in this code or subcode */
3448 Bytef *pad; /* pad structure to a power of 2 (4 bytes for */
3449 } word; /* 16-bit, 8 bytes for 32-bit machines) */
3451 uInt Base; /* literal, length base, or distance base */
3452 inflate_huft *Next; /* pointer to next level of table */
3457 extern uInt inflate_hufts;
3460 extern int inflate_trees_bits OF((
3461 uIntf *, /* 19 code lengths */
3462 uIntf *, /* bits tree desired/actual depth */
3463 inflate_huft * FAR *, /* bits tree result */
3464 z_streamp )); /* for zalloc, zfree functions */
3466 extern int inflate_trees_dynamic OF((
3467 uInt, /* number of literal/length codes */
3468 uInt, /* number of distance codes */
3469 uIntf *, /* that many (total) code lengths */
3470 uIntf *, /* literal desired/actual bit depth */
3471 uIntf *, /* distance desired/actual bit depth */
3472 inflate_huft * FAR *, /* literal/length tree result */
3473 inflate_huft * FAR *, /* distance tree result */
3474 z_streamp )); /* for zalloc, zfree functions */
3476 extern int inflate_trees_fixed OF((
3477 uIntf *, /* literal desired/actual bit depth */
3478 uIntf *, /* distance desired/actual bit depth */
3479 inflate_huft * FAR *, /* literal/length tree result */
3480 inflate_huft * FAR *)); /* distance tree result */
3482 extern int inflate_trees_free OF((
3483 inflate_huft *, /* tables to free */
3484 z_streamp )); /* for zfree function */
3486 /* --- inftrees.h */
3488 /* +++ infcodes.h */
3489 /* infcodes.h -- header to use infcodes.c
3490 * Copyright (C) 1995-1996 Mark Adler
3491 * For conditions of distribution and use, see copyright notice in zlib.h
3494 /* WARNING: this file should *not* be used by applications. It is
3495 part of the implementation of the compression library and is
3496 subject to change. Applications should only use zlib.h.
3499 struct inflate_codes_state;
3500 typedef struct inflate_codes_state FAR inflate_codes_statef;
3502 extern inflate_codes_statef *inflate_codes_new OF((
3504 inflate_huft *, inflate_huft *,
3507 extern int inflate_codes OF((
3508 inflate_blocks_statef *,
3512 extern void inflate_codes_free OF((
3513 inflate_codes_statef *,
3516 /* --- infcodes.h */
3519 /* infutil.h -- types and macros common to blocks and codes
3520 * Copyright (C) 1995-1996 Mark Adler
3521 * For conditions of distribution and use, see copyright notice in zlib.h
3524 /* WARNING: this file should *not* be used by applications. It is
3525 part of the implementation of the compression library and is
3526 subject to change. Applications should only use zlib.h.
3533 TYPE, /* get type bits (3, including end bit) */
3534 LENS, /* get lengths for stored */
3535 STORED, /* processing stored block */
3536 TABLE, /* get table lengths */
3537 BTREE, /* get bit lengths tree for a dynamic block */
3538 DTREE, /* get length, distance trees for a dynamic block */
3539 CODES, /* processing fixed or dynamic block */
3540 DRY, /* output remaining window bytes */
3541 DONEB, /* finished last block, done */
3542 BADB} /* got a data error--stuck here */
3545 /* inflate blocks semi-private state */
3546 struct inflate_blocks_state {
3549 inflate_block_mode mode; /* current inflate_block mode */
3551 /* mode dependent information */
3553 uInt left; /* if STORED, bytes left to copy */
3555 uInt table; /* table lengths (14 bits) */
3556 uInt index; /* index into blens (or border) */
3557 uIntf *blens; /* bit lengths of codes */
3558 uInt bb; /* bit length tree depth */
3559 inflate_huft *tb; /* bit length decoding tree */
3560 } trees; /* if DTREE, decoding info for trees */
3563 inflate_huft *td; /* trees to free */
3564 inflate_codes_statef
3566 } decode; /* if CODES, current state */
3567 } sub; /* submode */
3568 uInt last; /* true if this block is the last block */
3570 /* mode independent information */
3571 uInt bitk; /* bits in bit buffer */
3572 uLong bitb; /* bit buffer */
3573 Bytef *window; /* sliding window */
3574 Bytef *end; /* one byte after sliding window */
3575 Bytef *read; /* window read pointer */
3576 Bytef *write; /* window write pointer */
3577 check_func checkfn; /* check function */
3578 uLong check; /* check on output */
3583 /* defines for inflate input/output */
3584 /* update pointers and return */
3585 #define UPDBITS {s->bitb=b;s->bitk=k;}
3586 #define UPDIN {z->avail_in=n;z->total_in+=p-z->next_in;z->next_in=p;}
3587 #define UPDOUT {s->write=q;}
3588 #define UPDATE {UPDBITS UPDIN UPDOUT}
3589 #define LEAVE {UPDATE return inflate_flush(s,z,r);}
3590 /* get bytes and bits */
3591 #define LOADIN {p=z->next_in;n=z->avail_in;b=s->bitb;k=s->bitk;}
3592 #define NEEDBYTE {if(n)r=Z_OK;else LEAVE}
3593 #define NEXTBYTE (n--,*p++)
3594 #define NEEDBITS(j) {while(k<(j)){NEEDBYTE;b|=((uLong)NEXTBYTE)<<k;k+=8;}}
3595 #define DUMPBITS(j) {b>>=(j);k-=(j);}
3597 #define WAVAIL (uInt)(q<s->read?s->read-q-1:s->end-q)
3598 #define LOADOUT {q=s->write;m=(uInt)WAVAIL;}
3599 #define WWRAP {if(q==s->end&&s->read!=s->window){q=s->window;m=(uInt)WAVAIL;}}
3600 #define FLUSH {UPDOUT r=inflate_flush(s,z,r); LOADOUT}
3601 #define NEEDOUT {if(m==0){WWRAP if(m==0){FLUSH WWRAP if(m==0) LEAVE}}r=Z_OK;}
3602 #define OUTBYTE(a) {*q++=(Byte)(a);m--;}
3603 /* load local pointers */
3604 #define LOAD {LOADIN LOADOUT}
3606 /* masks for lower bits (size given to avoid silly warnings with Visual C++) */
3607 extern uInt inflate_mask[17];
3609 /* copy as much as possible from the sliding window to the output area */
3610 extern int inflate_flush OF((
3611 inflate_blocks_statef *,
3615 #ifndef NO_DUMMY_DECL
3616 struct internal_state {int dummy;}; /* for buggy compilers */
3622 #ifndef NO_DUMMY_DECL
3623 struct inflate_codes_state {int dummy;}; /* for buggy compilers */
3626 /* Table for deflate from PKZIP's appnote.txt. */
3627 local const uInt border[] = { /* Order of the bit length code lengths */
3628 16, 17, 18, 0, 8, 7, 9, 6, 10, 5, 11, 4, 12, 3, 13, 2, 14, 1, 15};
3631 Notes beyond the 1.93a appnote.txt:
3633 1. Distance pointers never point before the beginning of the output
3635 2. Distance pointers can point back across blocks, up to 32k away.
3636 3. There is an implied maximum of 7 bits for the bit length table and
3637 15 bits for the actual data.
3638 4. If only one code exists, then it is encoded using one bit. (Zero
3639 would be more efficient, but perhaps a little confusing.) If two
3640 codes exist, they are coded using one bit each (0 and 1).
3641 5. There is no way of sending zero distance codes--a dummy must be
3642 sent if there are none. (History: a pre 2.0 version of PKZIP would
3643 store blocks with no distance codes, but this was discovered to be
3644 too harsh a criterion.) Valid only for 1.93a. 2.04c does allow
3645 zero distance codes, which is sent as one code of zero bits in
3647 6. There are up to 286 literal/length codes. Code 256 represents the
3648 end-of-block. Note however that the static length tree defines
3649 288 codes just to fill out the Huffman codes. Codes 286 and 287
3650 cannot be used though, since there is no length base or extra bits
3651 defined for them. Similarily, there are up to 30 distance codes.
3652 However, static trees define 32 codes (all 5 bits) to fill out the
3653 Huffman codes, but the last two had better not show up in the data.
3654 7. Unzip can check dynamic Huffman blocks for complete code sets.
3655 The exception is that a single code would not be complete (see #4).
3656 8. The five bits following the block type is really the number of
3657 literal codes sent minus 257.
3658 9. Length codes 8,16,16 are interpreted as 13 length codes of 8 bits
3659 (1+6+6). Therefore, to output three times the length, you output
3660 three codes (1+1+1), whereas to output four times the same length,
3661 you only need two codes (1+3). Hmm.
3662 10. In the tree reconstruction algorithm, Code = Code + Increment
3663 only if BitLength(i) is not zero. (Pretty obvious.)
3664 11. Correction: 4 Bits: # of Bit Length codes - 4 (4 - 19)
3665 12. Note: length code 284 can represent 227-258, but length code 285
3666 really is 258. The last length deserves its own, short code
3667 since it gets used a lot in very redundant files. The length
3668 258 is special since 258 - 3 (the min match length) is 255.
3669 13. The literal/length and distance code bit lengths are read as a
3670 single stream of lengths. It is possible (and advantageous) for
3671 a repeat code (16, 17, or 18) to go across the boundary between
3672 the two sets of lengths.
3676 void inflate_blocks_reset(s, z, c)
3677 inflate_blocks_statef *s;
3681 if (s->checkfn != Z_NULL)
3683 if (s->mode == BTREE || s->mode == DTREE)
3684 ZFREE(z, s->sub.trees.blens);
3685 if (s->mode == CODES)
3687 inflate_codes_free(s->sub.decode.codes, z);
3688 inflate_trees_free(s->sub.decode.td, z);
3689 inflate_trees_free(s->sub.decode.tl, z);
3694 s->read = s->write = s->window;
3695 if (s->checkfn != Z_NULL)
3696 z->adler = s->check = (*s->checkfn)(0L, Z_NULL, 0);
3697 Trace((stderr, "inflate: blocks reset\n"));
3701 inflate_blocks_statef *inflate_blocks_new(z, c, w)
3706 inflate_blocks_statef *s;
3708 if ((s = (inflate_blocks_statef *)ZALLOC
3709 (z,1,sizeof(struct inflate_blocks_state))) == Z_NULL)
3711 if ((s->window = (Bytef *)ZALLOC(z, 1, w)) == Z_NULL)
3716 s->end = s->window + w;
3719 Trace((stderr, "inflate: blocks allocated\n"));
3720 inflate_blocks_reset(s, z, &s->check);
3726 extern uInt inflate_hufts;
3728 int inflate_blocks(s, z, r)
3729 inflate_blocks_statef *s;
3733 uInt t; /* temporary storage */
3734 uLong b; /* bit buffer */
3735 uInt k; /* bits in bit buffer */
3736 Bytef *p; /* input data pointer */
3737 uInt n; /* bytes available there */
3738 Bytef *q; /* output window write pointer */
3739 uInt m; /* bytes to end of window or read pointer */
3741 /* copy input/output information to locals (UPDATE macro restores) */
3744 /* process input based on current state */
3745 while (1) switch (s->mode)
3753 case 0: /* stored */
3754 Trace((stderr, "inflate: stored block%s\n",
3755 s->last ? " (last)" : ""));
3757 t = k & 7; /* go to byte boundary */
3759 s->mode = LENS; /* get length of stored block */
3762 Trace((stderr, "inflate: fixed codes block%s\n",
3763 s->last ? " (last)" : ""));
3766 inflate_huft *tl, *td;
3768 inflate_trees_fixed(&bl, &bd, &tl, &td);
3769 s->sub.decode.codes = inflate_codes_new(bl, bd, tl, td, z);
3770 if (s->sub.decode.codes == Z_NULL)
3775 s->sub.decode.tl = Z_NULL; /* don't try to free these */
3776 s->sub.decode.td = Z_NULL;
3781 case 2: /* dynamic */
3782 Trace((stderr, "inflate: dynamic codes block%s\n",
3783 s->last ? " (last)" : ""));
3787 case 3: /* illegal */
3790 z->msg = (char*)"invalid block type";
3797 if ((((~b) >> 16) & 0xffff) != (b & 0xffff))
3800 z->msg = (char*)"invalid stored block lengths";
3804 s->sub.left = (uInt)b & 0xffff;
3805 b = k = 0; /* dump bits */
3806 Tracev((stderr, "inflate: stored length %u\n", s->sub.left));
3807 s->mode = s->sub.left ? STORED : (s->last ? DRY : TYPE);
3819 if ((s->sub.left -= t) != 0)
3821 Tracev((stderr, "inflate: stored end, %lu total out\n",
3822 z->total_out + (q >= s->read ? q - s->read :
3823 (s->end - s->read) + (q - s->window))));
3824 s->mode = s->last ? DRY : TYPE;
3828 s->sub.trees.table = t = (uInt)b & 0x3fff;
3829 #ifndef PKZIP_BUG_WORKAROUND
3830 if ((t & 0x1f) > 29 || ((t >> 5) & 0x1f) > 29)
3833 z->msg = (char*)"too many length or distance symbols";
3838 t = 258 + (t & 0x1f) + ((t >> 5) & 0x1f);
3841 if ((s->sub.trees.blens = (uIntf*)ZALLOC(z, t, sizeof(uInt))) == Z_NULL)
3847 s->sub.trees.index = 0;
3848 Tracev((stderr, "inflate: table sizes ok\n"));
3851 while (s->sub.trees.index < 4 + (s->sub.trees.table >> 10))
3854 s->sub.trees.blens[border[s->sub.trees.index++]] = (uInt)b & 7;
3857 while (s->sub.trees.index < 19)
3858 s->sub.trees.blens[border[s->sub.trees.index++]] = 0;
3859 s->sub.trees.bb = 7;
3860 t = inflate_trees_bits(s->sub.trees.blens, &s->sub.trees.bb,
3861 &s->sub.trees.tb, z);
3864 ZFREE(z, s->sub.trees.blens);
3866 if (r == Z_DATA_ERROR)
3870 s->sub.trees.index = 0;
3871 Tracev((stderr, "inflate: bits tree ok\n"));
3874 while (t = s->sub.trees.table,
3875 s->sub.trees.index < 258 + (t & 0x1f) + ((t >> 5) & 0x1f))
3880 t = s->sub.trees.bb;
3882 h = s->sub.trees.tb + ((uInt)b & inflate_mask[t]);
3883 t = h->word.what.Bits;
3888 s->sub.trees.blens[s->sub.trees.index++] = c;
3890 else /* c == 16..18 */
3892 i = c == 18 ? 7 : c - 14;
3893 j = c == 18 ? 11 : 3;
3896 j += (uInt)b & inflate_mask[i];
3898 i = s->sub.trees.index;
3899 t = s->sub.trees.table;
3900 if (i + j > 258 + (t & 0x1f) + ((t >> 5) & 0x1f) ||
3903 inflate_trees_free(s->sub.trees.tb, z);
3904 ZFREE(z, s->sub.trees.blens);
3906 z->msg = (char*)"invalid bit length repeat";
3910 c = c == 16 ? s->sub.trees.blens[i - 1] : 0;
3912 s->sub.trees.blens[i++] = c;
3914 s->sub.trees.index = i;
3917 inflate_trees_free(s->sub.trees.tb, z);
3918 s->sub.trees.tb = Z_NULL;
3921 inflate_huft *tl, *td;
3922 inflate_codes_statef *c;
3924 bl = 9; /* must be <= 9 for lookahead assumptions */
3925 bd = 6; /* must be <= 9 for lookahead assumptions */
3926 t = s->sub.trees.table;
3930 t = inflate_trees_dynamic(257 + (t & 0x1f), 1 + ((t >> 5) & 0x1f),
3931 s->sub.trees.blens, &bl, &bd, &tl, &td, z);
3932 ZFREE(z, s->sub.trees.blens);
3935 if (t == (uInt)Z_DATA_ERROR)
3940 Tracev((stderr, "inflate: trees ok, %d * %d bytes used\n",
3941 inflate_hufts, sizeof(inflate_huft)));
3942 if ((c = inflate_codes_new(bl, bd, tl, td, z)) == Z_NULL)
3944 inflate_trees_free(td, z);
3945 inflate_trees_free(tl, z);
3949 s->sub.decode.codes = c;
3950 s->sub.decode.tl = tl;
3951 s->sub.decode.td = td;
3956 if ((r = inflate_codes(s, z, r)) != Z_STREAM_END)
3957 return inflate_flush(s, z, r);
3959 inflate_codes_free(s->sub.decode.codes, z);
3960 inflate_trees_free(s->sub.decode.td, z);
3961 inflate_trees_free(s->sub.decode.tl, z);
3963 Tracev((stderr, "inflate: codes end, %lu total out\n",
3964 z->total_out + (q >= s->read ? q - s->read :
3965 (s->end - s->read) + (q - s->window))));
3971 if (k > 7) /* return unused byte, if any */
3973 Assert(k < 16, "inflate_codes grabbed too many bytes")
3976 p--; /* can always return one */
3981 if (s->read != s->write)
3997 int inflate_blocks_free(s, z, c)
3998 inflate_blocks_statef *s;
4002 inflate_blocks_reset(s, z, c);
4003 ZFREE(z, s->window);
4005 Trace((stderr, "inflate: blocks freed\n"));
4010 void inflate_set_dictionary(s, d, n)
4011 inflate_blocks_statef *s;
4015 zmemcpy((charf *)s->window, d, n);
4016 s->read = s->write = s->window + n;
4020 * This subroutine adds the data at next_in/avail_in to the output history
4021 * without performing any output. The output buffer must be "caught up";
4022 * i.e. no pending output (hence s->read equals s->write), and the state must
4023 * be BLOCKS (i.e. we should be willing to see the start of a series of
4024 * BLOCKS). On exit, the output will also be caught up, and the checksum
4025 * will have been updated if need be.
4027 int inflate_addhistory(s, z)
4028 inflate_blocks_statef *s;
4031 uLong b; /* bit buffer */ /* NOT USED HERE */
4032 uInt k; /* bits in bit buffer */ /* NOT USED HERE */
4033 uInt t; /* temporary storage */
4034 Bytef *p; /* input data pointer */
4035 uInt n; /* bytes available there */
4036 Bytef *q; /* output window write pointer */
4037 uInt m; /* bytes to end of window or read pointer */
4039 if (s->read != s->write)
4040 return Z_STREAM_ERROR;
4041 if (s->mode != TYPE)
4042 return Z_DATA_ERROR;
4044 /* we're ready to rock */
4046 /* while there is input ready, copy to output buffer, moving
4047 * pointers as needed.
4050 t = n; /* how many to do */
4051 /* is there room until end of buffer? */
4053 /* update check information */
4054 if (s->checkfn != Z_NULL)
4055 s->check = (*s->checkfn)(s->check, q, t);
4061 s->read = q; /* drag read pointer forward */
4062 /* WWRAP */ /* expand WWRAP macro by hand to handle s->read */
4064 s->read = q = s->window;
4074 * At the end of a Deflate-compressed PPP packet, we expect to have seen
4075 * a `stored' block type value but not the (zero) length bytes.
4077 int inflate_packet_flush(s)
4078 inflate_blocks_statef *s;
4080 if (s->mode != LENS)
4081 return Z_DATA_ERROR;
4085 /* --- infblock.c */
4087 /* +++ inftrees.c */
4088 /* inftrees.c -- generate Huffman trees for efficient decoding
4089 * Copyright (C) 1995-1996 Mark Adler
4090 * For conditions of distribution and use, see copyright notice in zlib.h
4093 /* #include "zutil.h" */
4094 /* #include "inftrees.h" */
4096 char inflate_copyright[] = " inflate 1.0.4 Copyright 1995-1996 Mark Adler ";
4098 If you use the zlib library in a product, an acknowledgment is welcome
4099 in the documentation of your product. If for some reason you cannot
4100 include such an acknowledgment, I would appreciate that you keep this
4101 copyright string in the executable of your product.
4104 #ifndef NO_DUMMY_DECL
4105 struct internal_state {int dummy;}; /* for buggy compilers */
4108 /* simplify the use of the inflate_huft type with some defines */
4109 #define base more.Base
4110 #define next more.Next
4111 #define exop word.what.Exop
4112 #define bits word.what.Bits
4115 local int huft_build OF((
4116 uIntf *, /* code lengths in bits */
4117 uInt, /* number of codes */
4118 uInt, /* number of "simple" codes */
4119 const uIntf *, /* list of base values for non-simple codes */
4120 const uIntf *, /* list of extra bits for non-simple codes */
4121 inflate_huft * FAR*,/* result: starting table */
4122 uIntf *, /* maximum lookup bits (returns actual) */
4123 z_streamp )); /* for zalloc function */
4125 local voidpf falloc OF((
4126 voidpf, /* opaque pointer (not used) */
4127 uInt, /* number of items */
4128 uInt)); /* size of item */
4130 /* Tables for deflate from PKZIP's appnote.txt. */
4131 local const uInt cplens[31] = { /* Copy lengths for literal codes 257..285 */
4132 3, 4, 5, 6, 7, 8, 9, 10, 11, 13, 15, 17, 19, 23, 27, 31,
4133 35, 43, 51, 59, 67, 83, 99, 115, 131, 163, 195, 227, 258, 0, 0};
4134 /* see note #13 above about 258 */
4135 local const uInt cplext[31] = { /* Extra bits for literal codes 257..285 */
4136 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 2, 2, 2, 2,
4137 3, 3, 3, 3, 4, 4, 4, 4, 5, 5, 5, 5, 0, 112, 112}; /* 112==invalid */
4138 local const uInt cpdist[30] = { /* Copy offsets for distance codes 0..29 */
4139 1, 2, 3, 4, 5, 7, 9, 13, 17, 25, 33, 49, 65, 97, 129, 193,
4140 257, 385, 513, 769, 1025, 1537, 2049, 3073, 4097, 6145,
4141 8193, 12289, 16385, 24577};
4142 local const uInt cpdext[30] = { /* Extra bits for distance codes */
4143 0, 0, 0, 0, 1, 1, 2, 2, 3, 3, 4, 4, 5, 5, 6, 6,
4144 7, 7, 8, 8, 9, 9, 10, 10, 11, 11,
4148 Huffman code decoding is performed using a multi-level table lookup.
4149 The fastest way to decode is to simply build a lookup table whose
4150 size is determined by the longest code. However, the time it takes
4151 to build this table can also be a factor if the data being decoded
4152 is not very long. The most common codes are necessarily the
4153 shortest codes, so those codes dominate the decoding time, and hence
4154 the speed. The idea is you can have a shorter table that decodes the
4155 shorter, more probable codes, and then point to subsidiary tables for
4156 the longer codes. The time it costs to decode the longer codes is
4157 then traded against the time it takes to make longer tables.
4159 This results of this trade are in the variables lbits and dbits
4160 below. lbits is the number of bits the first level table for literal/
4161 length codes can decode in one step, and dbits is the same thing for
4162 the distance codes. Subsequent tables are also less than or equal to
4163 those sizes. These values may be adjusted either when all of the
4164 codes are shorter than that, in which case the longest code length in
4165 bits is used, or when the shortest code is *longer* than the requested
4166 table size, in which case the length of the shortest code in bits is
4169 There are two different values for the two tables, since they code a
4170 different number of possibilities each. The literal/length table
4171 codes 286 possible values, or in a flat code, a little over eight
4172 bits. The distance table codes 30 possible values, or a little less
4173 than five bits, flat. The optimum values for speed end up being
4174 about one bit more than those, so lbits is 8+1 and dbits is 5+1.
4175 The optimum values may differ though from machine to machine, and
4176 possibly even between compilers. Your mileage may vary.
4180 /* If BMAX needs to be larger than 16, then h and x[] should be uLong. */
4181 #define BMAX 15 /* maximum bit length of any code */
4182 #define N_MAX 288 /* maximum number of codes in any set */
4188 local int huft_build(b, n, s, d, e, t, m, zs)
4189 uIntf *b; /* code lengths in bits (all assumed <= BMAX) */
4190 uInt n; /* number of codes (assumed <= N_MAX) */
4191 uInt s; /* number of simple-valued codes (0..s-1) */
4192 const uIntf *d; /* list of base values for non-simple codes */
4193 const uIntf *e; /* list of extra bits for non-simple codes */
4194 inflate_huft * FAR *t; /* result: starting table */
4195 uIntf *m; /* maximum lookup bits, returns actual */
4196 z_streamp zs; /* for zalloc function */
4197 /* Given a list of code lengths and a maximum table size, make a set of
4198 tables to decode that set of codes. Return Z_OK on success, Z_BUF_ERROR
4199 if the given code set is incomplete (the tables are still built in this
4200 case), Z_DATA_ERROR if the input is invalid (an over-subscribed set of
4201 lengths), or Z_MEM_ERROR if not enough memory. */
4204 uInt a; /* counter for codes of length k */
4205 uInt c[BMAX+1]; /* bit length count table */
4206 uInt f; /* i repeats in table every f entries */
4207 int g; /* maximum code length */
4208 int h; /* table level */
4209 register uInt i; /* counter, current code */
4210 register uInt j; /* counter */
4211 register int k; /* number of bits in current code */
4212 int l; /* bits per table (returned in m) */
4213 register uIntf *p; /* pointer into c[], b[], or v[] */
4214 inflate_huft *q; /* points to current table */
4215 struct inflate_huft_s r; /* table entry for structure assignment */
4216 inflate_huft *u[BMAX]; /* table stack */
4217 uInt v[N_MAX]; /* values in order of bit length */
4218 register int w; /* bits before this table == (l * h) */
4219 uInt x[BMAX+1]; /* bit offsets, then code stack */
4220 uIntf *xp; /* pointer into x */
4221 int y; /* number of dummy codes added */
4222 uInt z; /* number of entries in current table */
4225 /* Generate counts for each bit length */
4227 #define C0 *p++ = 0;
4228 #define C2 C0 C0 C0 C0
4229 #define C4 C2 C2 C2 C2
4230 C4 /* clear c[]--assume BMAX+1 is 16 */
4233 c[*p++]++; /* assume all entries <= BMAX */
4235 if (c[0] == n) /* null input--all zero length codes */
4237 *t = (inflate_huft *)Z_NULL;
4243 /* Find minimum and maximum length, bound *m by those */
4245 for (j = 1; j <= BMAX; j++)
4248 k = j; /* minimum code length */
4251 for (i = BMAX; i; i--)
4254 g = i; /* maximum code length */
4260 /* Adjust last length count to fill out codes, if needed */
4261 for (y = 1 << j; j < i; j++, y <<= 1)
4262 if ((y -= c[j]) < 0)
4263 return Z_DATA_ERROR;
4264 if ((y -= c[i]) < 0)
4265 return Z_DATA_ERROR;
4269 /* Generate starting offsets into the value table for each length */
4271 p = c + 1; xp = x + 2;
4272 while (--i) { /* note that i == g from above */
4273 *xp++ = (j += *p++);
4277 /* Make a table of values in order of bit lengths */
4280 if ((j = *p++) != 0)
4283 n = x[g]; /* set n to length of v */
4286 /* Generate the Huffman codes and for each, make the table entries */
4287 x[0] = i = 0; /* first Huffman code is zero */
4288 p = v; /* grab values in bit order */
4289 h = -1; /* no tables yet--level -1 */
4290 w = -l; /* bits decoded == (l * h) */
4291 u[0] = (inflate_huft *)Z_NULL; /* just to keep compilers happy */
4292 q = (inflate_huft *)Z_NULL; /* ditto */
4295 /* go through the bit lengths (k already is bits in shortest code) */
4301 /* here i is the Huffman code of length k bits for value *p */
4302 /* make tables up to required level */
4306 w += l; /* previous table always l bits */
4308 /* compute minimum size table less than or equal to l bits */
4310 z = z > (uInt)l ? l : z; /* table size upper limit */
4311 if ((f = 1 << (j = k - w)) > a + 1) /* try a k-w bit table */
4312 { /* too few codes for k-w bit table */
4313 f -= a + 1; /* deduct codes from patterns left */
4316 while (++j < z) /* try smaller tables up to z bits */
4318 if ((f <<= 1) <= *++xp)
4319 break; /* enough codes to use up j bits */
4320 f -= *xp; /* else deduct codes from patterns */
4323 z = 1 << j; /* table entries for j-bit table */
4325 /* allocate and link in new table */
4326 if ((q = (inflate_huft *)ZALLOC
4327 (zs,z + 1,sizeof(inflate_huft))) == Z_NULL)
4330 inflate_trees_free(u[0], zs);
4331 return Z_MEM_ERROR; /* not enough memory */
4334 inflate_hufts += z + 1;
4336 *t = q + 1; /* link to list for huft_free() */
4337 *(t = &(q->next)) = Z_NULL;
4338 u[h] = ++q; /* table starts after link */
4340 /* connect to last table, if there is one */
4343 x[h] = i; /* save pattern for backing up */
4344 r.bits = (Byte)l; /* bits to dump before this table */
4345 r.exop = (Byte)j; /* bits in this table */
4346 r.next = q; /* pointer to this table */
4347 j = i >> (w - l); /* (get around Turbo C bug) */
4348 u[h-1][j] = r; /* connect to last table */
4352 /* set up table entry in r */
4353 r.bits = (Byte)(k - w);
4355 r.exop = 128 + 64; /* out of values--invalid code */
4358 r.exop = (Byte)(*p < 256 ? 0 : 32 + 64); /* 256 is end-of-block */
4359 r.base = *p++; /* simple code is just the value */
4363 r.exop = (Byte)(e[*p - s] + 16 + 64);/* non-simple--look up in lists */
4364 r.base = d[*p++ - s];
4367 /* fill code-like entries with r */
4369 for (j = i >> w; j < z; j += f)
4372 /* backwards increment the k-bit code i */
4373 for (j = 1 << (k - 1); i & j; j >>= 1)
4377 /* backup over finished tables */
4378 while ((i & ((1 << w) - 1)) != x[h])
4380 h--; /* don't need to update q */
4387 /* Return Z_BUF_ERROR if we were given an incomplete table */
4388 return y != 0 && g != 1 ? Z_BUF_ERROR : Z_OK;
4392 int inflate_trees_bits(c, bb, tb, z)
4393 uIntf *c; /* 19 code lengths */
4394 uIntf *bb; /* bits tree desired/actual depth */
4395 inflate_huft * FAR *tb; /* bits tree result */
4396 z_streamp z; /* for zfree function */
4400 r = huft_build(c, 19, 19, (uIntf*)Z_NULL, (uIntf*)Z_NULL, tb, bb, z);
4401 if (r == Z_DATA_ERROR)
4402 z->msg = (char*)"oversubscribed dynamic bit lengths tree";
4403 else if (r == Z_BUF_ERROR || *bb == 0)
4405 inflate_trees_free(*tb, z);
4406 z->msg = (char*)"incomplete dynamic bit lengths tree";
4413 int inflate_trees_dynamic(nl, nd, c, bl, bd, tl, td, z)
4414 uInt nl; /* number of literal/length codes */
4415 uInt nd; /* number of distance codes */
4416 uIntf *c; /* that many (total) code lengths */
4417 uIntf *bl; /* literal desired/actual bit depth */
4418 uIntf *bd; /* distance desired/actual bit depth */
4419 inflate_huft * FAR *tl; /* literal/length tree result */
4420 inflate_huft * FAR *td; /* distance tree result */
4421 z_streamp z; /* for zfree function */
4425 /* build literal/length tree */
4426 r = huft_build(c, nl, 257, cplens, cplext, tl, bl, z);
4427 if (r != Z_OK || *bl == 0)
4429 if (r == Z_DATA_ERROR)
4430 z->msg = (char*)"oversubscribed literal/length tree";
4431 else if (r != Z_MEM_ERROR)
4433 inflate_trees_free(*tl, z);
4434 z->msg = (char*)"incomplete literal/length tree";
4440 /* build distance tree */
4441 r = huft_build(c + nl, nd, 0, cpdist, cpdext, td, bd, z);
4442 if (r != Z_OK || (*bd == 0 && nl > 257))
4444 if (r == Z_DATA_ERROR)
4445 z->msg = (char*)"oversubscribed distance tree";
4446 else if (r == Z_BUF_ERROR) {
4447 #ifdef PKZIP_BUG_WORKAROUND
4451 inflate_trees_free(*td, z);
4452 z->msg = (char*)"incomplete distance tree";
4455 else if (r != Z_MEM_ERROR)
4457 z->msg = (char*)"empty distance tree with lengths";
4460 inflate_trees_free(*tl, z);
4470 /* build fixed tables only once--keep them here */
4471 local int fixed_built = 0;
4472 #define FIXEDH 530 /* number of hufts used by fixed tables */
4473 local inflate_huft fixed_mem[FIXEDH];
4474 local uInt fixed_bl;
4475 local uInt fixed_bd;
4476 local inflate_huft *fixed_tl;
4477 local inflate_huft *fixed_td;
4480 local voidpf falloc(q, n, s)
4481 voidpf q; /* opaque pointer */
4482 uInt n; /* number of items */
4483 uInt s; /* size of item */
4485 Assert(s == sizeof(inflate_huft) && n <= *(intf *)q,
4486 "inflate_trees falloc overflow");
4487 *(intf *)q -= n+s-s; /* s-s to avoid warning */
4488 return (voidpf)(fixed_mem + *(intf *)q);
4492 int inflate_trees_fixed(bl, bd, tl, td)
4493 uIntf *bl; /* literal desired/actual bit depth */
4494 uIntf *bd; /* distance desired/actual bit depth */
4495 inflate_huft * FAR *tl; /* literal/length tree result */
4496 inflate_huft * FAR *td; /* distance tree result */
4498 /* build fixed tables if not already (multiple overlapped executions ok) */
4501 int k; /* temporary variable */
4502 unsigned c[288]; /* length list for huft_build */
4503 z_stream z; /* for falloc function */
4504 int f = FIXEDH; /* number of hufts left in fixed_mem */
4506 /* set up fake z_stream for memory routines */
4509 z.opaque = (voidpf)&f;
4512 for (k = 0; k < 144; k++)
4514 for (; k < 256; k++)
4516 for (; k < 280; k++)
4518 for (; k < 288; k++)
4521 huft_build(c, 288, 257, cplens, cplext, &fixed_tl, &fixed_bl, &z);
4523 /* distance table */
4524 for (k = 0; k < 30; k++)
4527 huft_build(c, 30, 0, cpdist, cpdext, &fixed_td, &fixed_bd, &z);
4530 Assert(f == 0, "invalid build of fixed tables");
4541 int inflate_trees_free(t, z)
4542 inflate_huft *t; /* table to free */
4543 z_streamp z; /* for zfree function */
4544 /* Free the malloc'ed tables built by huft_build(), which makes a linked
4545 list of the tables it made, with the links in a dummy first entry of
4548 register inflate_huft *p, *q, *r;
4550 /* Reverse linked list */
4560 /* Go through linked list, freeing from the malloced (t[-1]) address. */
4569 /* --- inftrees.c */
4571 /* +++ infcodes.c */
4572 /* infcodes.c -- process literals and length/distance pairs
4573 * Copyright (C) 1995-1996 Mark Adler
4574 * For conditions of distribution and use, see copyright notice in zlib.h
4577 /* #include "zutil.h" */
4578 /* #include "inftrees.h" */
4579 /* #include "infblock.h" */
4580 /* #include "infcodes.h" */
4581 /* #include "infutil.h" */
4584 /* inffast.h -- header to use inffast.c
4585 * Copyright (C) 1995-1996 Mark Adler
4586 * For conditions of distribution and use, see copyright notice in zlib.h
4589 /* WARNING: this file should *not* be used by applications. It is
4590 part of the implementation of the compression library and is
4591 subject to change. Applications should only use zlib.h.
4594 extern int inflate_fast OF((
4599 inflate_blocks_statef *,
4603 /* simplify the use of the inflate_huft type with some defines */
4604 #define base more.Base
4605 #define next more.Next
4606 #define exop word.what.Exop
4607 #define bits word.what.Bits
4609 /* inflate codes private state */
4610 struct inflate_codes_state {
4613 enum { /* waiting for "i:"=input, "o:"=output, "x:"=nothing */
4614 START, /* x: set up for LEN */
4615 LEN, /* i: get length/literal/eob next */
4616 LENEXT, /* i: getting length extra (have base) */
4617 DIST, /* i: get distance next */
4618 DISTEXT, /* i: getting distance extra */
4619 COPY, /* o: copying bytes in window, waiting for space */
4620 LIT, /* o: got literal, waiting for output space */
4621 WASH, /* o: got eob, possibly still output waiting */
4622 END, /* x: got eob and all data flushed */
4623 BADCODE} /* x: got error */
4624 mode; /* current inflate_codes mode */
4626 /* mode dependent information */
4630 inflate_huft *tree; /* pointer into tree */
4631 uInt need; /* bits needed */
4632 } code; /* if LEN or DIST, where in tree */
4633 uInt lit; /* if LIT, literal */
4635 uInt get; /* bits to get for extra */
4636 uInt dist; /* distance back to copy from */
4637 } copy; /* if EXT or COPY, where and how much */
4638 } sub; /* submode */
4640 /* mode independent information */
4641 Byte lbits; /* ltree bits decoded per branch */
4642 Byte dbits; /* dtree bits decoder per branch */
4643 inflate_huft *ltree; /* literal/length/eob tree */
4644 inflate_huft *dtree; /* distance tree */
4649 inflate_codes_statef *inflate_codes_new(bl, bd, tl, td, z)
4652 inflate_huft *td; /* need separate declaration for Borland C++ */
4655 inflate_codes_statef *c;
4657 if ((c = (inflate_codes_statef *)
4658 ZALLOC(z,1,sizeof(struct inflate_codes_state))) != Z_NULL)
4661 c->lbits = (Byte)bl;
4662 c->dbits = (Byte)bd;
4665 Tracev((stderr, "inflate: codes new\n"));
4671 int inflate_codes(s, z, r)
4672 inflate_blocks_statef *s;
4676 uInt j; /* temporary storage */
4677 inflate_huft *t; /* temporary pointer */
4678 uInt e; /* extra bits or operation */
4679 uLong b; /* bit buffer */
4680 uInt k; /* bits in bit buffer */
4681 Bytef *p; /* input data pointer */
4682 uInt n; /* bytes available there */
4683 Bytef *q; /* output window write pointer */
4684 uInt m; /* bytes to end of window or read pointer */
4685 Bytef *f; /* pointer to copy strings from */
4686 inflate_codes_statef *c = s->sub.decode.codes; /* codes state */
4688 /* copy input/output information to locals (UPDATE macro restores) */
4691 /* process input and output based on current state */
4692 while (1) switch (c->mode)
4693 { /* waiting for "i:"=input, "o:"=output, "x:"=nothing */
4694 case START: /* x: set up for LEN */
4696 if (m >= 258 && n >= 10)
4699 r = inflate_fast(c->lbits, c->dbits, c->ltree, c->dtree, s, z);
4703 c->mode = r == Z_STREAM_END ? WASH : BADCODE;
4708 c->sub.code.need = c->lbits;
4709 c->sub.code.tree = c->ltree;
4711 case LEN: /* i: get length/literal/eob next */
4712 j = c->sub.code.need;
4714 t = c->sub.code.tree + ((uInt)b & inflate_mask[j]);
4716 e = (uInt)(t->exop);
4717 if (e == 0) /* literal */
4719 c->sub.lit = t->base;
4720 Tracevv((stderr, t->base >= 0x20 && t->base < 0x7f ?
4721 "inflate: literal '%c'\n" :
4722 "inflate: literal 0x%02x\n", t->base));
4726 if (e & 16) /* length */
4728 c->sub.copy.get = e & 15;
4733 if ((e & 64) == 0) /* next table */
4735 c->sub.code.need = e;
4736 c->sub.code.tree = t->next;
4739 if (e & 32) /* end of block */
4741 Tracevv((stderr, "inflate: end of block\n"));
4745 c->mode = BADCODE; /* invalid code */
4746 z->msg = (char*)"invalid literal/length code";
4749 case LENEXT: /* i: getting length extra (have base) */
4750 j = c->sub.copy.get;
4752 c->len += (uInt)b & inflate_mask[j];
4754 c->sub.code.need = c->dbits;
4755 c->sub.code.tree = c->dtree;
4756 Tracevv((stderr, "inflate: length %u\n", c->len));
4758 case DIST: /* i: get distance next */
4759 j = c->sub.code.need;
4761 t = c->sub.code.tree + ((uInt)b & inflate_mask[j]);
4763 e = (uInt)(t->exop);
4764 if (e & 16) /* distance */
4766 c->sub.copy.get = e & 15;
4767 c->sub.copy.dist = t->base;
4771 if ((e & 64) == 0) /* next table */
4773 c->sub.code.need = e;
4774 c->sub.code.tree = t->next;
4777 c->mode = BADCODE; /* invalid code */
4778 z->msg = (char*)"invalid distance code";
4781 case DISTEXT: /* i: getting distance extra */
4782 j = c->sub.copy.get;
4784 c->sub.copy.dist += (uInt)b & inflate_mask[j];
4786 Tracevv((stderr, "inflate: distance %u\n", c->sub.copy.dist));
4788 case COPY: /* o: copying bytes in window, waiting for space */
4789 #ifndef __TURBOC__ /* Turbo C bug for following expression */
4790 f = (uInt)(q - s->window) < c->sub.copy.dist ?
4791 s->end - (c->sub.copy.dist - (q - s->window)) :
4792 q - c->sub.copy.dist;
4794 f = q - c->sub.copy.dist;
4795 if ((uInt)(q - s->window) < c->sub.copy.dist)
4796 f = s->end - (c->sub.copy.dist - (uInt)(q - s->window));
4808 case LIT: /* o: got literal, waiting for output space */
4813 case WASH: /* o: got eob, possibly more output */
4815 if (s->read != s->write)
4821 case BADCODE: /* x: got error */
4831 void inflate_codes_free(c, z)
4832 inflate_codes_statef *c;
4836 Tracev((stderr, "inflate: codes free\n"));
4838 /* --- infcodes.c */
4841 /* inflate_util.c -- data and routines common to blocks and codes
4842 * Copyright (C) 1995-1996 Mark Adler
4843 * For conditions of distribution and use, see copyright notice in zlib.h
4846 /* #include "zutil.h" */
4847 /* #include "infblock.h" */
4848 /* #include "inftrees.h" */
4849 /* #include "infcodes.h" */
4850 /* #include "infutil.h" */
4852 #ifndef NO_DUMMY_DECL
4853 struct inflate_codes_state {int dummy;}; /* for buggy compilers */
4856 /* And'ing with mask[n] masks the lower n bits */
4857 uInt inflate_mask[17] = {
4859 0x0001, 0x0003, 0x0007, 0x000f, 0x001f, 0x003f, 0x007f, 0x00ff,
4860 0x01ff, 0x03ff, 0x07ff, 0x0fff, 0x1fff, 0x3fff, 0x7fff, 0xffff
4864 /* copy as much as possible from the sliding window to the output area */
4865 int inflate_flush(s, z, r)
4866 inflate_blocks_statef *s;
4874 /* local copies of source and destination pointers */
4878 /* compute number of bytes to copy as far as end of window */
4879 n = (uInt)((q <= s->write ? s->write : s->end) - q);
4880 if (n > z->avail_out) n = z->avail_out;
4881 if (n && r == Z_BUF_ERROR) r = Z_OK;
4883 /* update counters */
4887 /* update check information */
4888 if (s->checkfn != Z_NULL)
4889 z->adler = s->check = (*s->checkfn)(s->check, q, n);
4891 /* copy as far as end of window */
4898 /* see if more to copy at beginning of window */
4903 if (s->write == s->end)
4904 s->write = s->window;
4906 /* compute bytes to copy */
4907 n = (uInt)(s->write - q);
4908 if (n > z->avail_out) n = z->avail_out;
4909 if (n && r == Z_BUF_ERROR) r = Z_OK;
4911 /* update counters */
4915 /* update check information */
4916 if (s->checkfn != Z_NULL)
4917 z->adler = s->check = (*s->checkfn)(s->check, q, n);
4927 /* update pointers */
4937 /* inffast.c -- process literals and length/distance pairs fast
4938 * Copyright (C) 1995-1996 Mark Adler
4939 * For conditions of distribution and use, see copyright notice in zlib.h
4942 /* #include "zutil.h" */
4943 /* #include "inftrees.h" */
4944 /* #include "infblock.h" */
4945 /* #include "infcodes.h" */
4946 /* #include "infutil.h" */
4947 /* #include "inffast.h" */
4949 #ifndef NO_DUMMY_DECL
4950 struct inflate_codes_state {int dummy;}; /* for buggy compilers */
4953 /* simplify the use of the inflate_huft type with some defines */
4954 #define base more.Base
4955 #define next more.Next
4956 #define exop word.what.Exop
4957 #define bits word.what.Bits
4959 /* macros for bit input with no checking and for returning unused bytes */
4960 #define GRABBITS(j) {while(k<(j)){b|=((uLong)NEXTBYTE)<<k;k+=8;}}
4961 #define UNGRAB {n+=(c=k>>3);p-=c;k&=7;}
4963 /* Called with number of bytes left to write in window at least 258
4964 (the maximum string length) and number of input bytes available
4965 at least ten. The ten bytes are six bytes for the longest length/
4966 distance pair plus four bytes for overloading the bit buffer. */
4968 int inflate_fast(bl, bd, tl, td, s, z)
4971 inflate_huft *td; /* need separate declaration for Borland C++ */
4972 inflate_blocks_statef *s;
4975 inflate_huft *t; /* temporary pointer */
4976 uInt e; /* extra bits or operation */
4977 uLong b; /* bit buffer */
4978 uInt k; /* bits in bit buffer */
4979 Bytef *p; /* input data pointer */
4980 uInt n; /* bytes available there */
4981 Bytef *q; /* output window write pointer */
4982 uInt m; /* bytes to end of window or read pointer */
4983 uInt ml; /* mask for literal/length tree */
4984 uInt md; /* mask for distance tree */
4985 uInt c; /* bytes to copy */
4986 uInt d; /* distance back to copy from */
4987 Bytef *r; /* copy source pointer */
4989 /* load input, output, bit values */
4992 /* initialize masks */
4993 ml = inflate_mask[bl];
4994 md = inflate_mask[bd];
4996 /* do until not enough input or output space for fast loop */
4997 do { /* assume called with m >= 258 && n >= 10 */
4998 /* get literal/length code */
4999 GRABBITS(20) /* max bits for literal/length code */
5000 if ((e = (t = tl + ((uInt)b & ml))->exop) == 0)
5003 Tracevv((stderr, t->base >= 0x20 && t->base < 0x7f ?
5004 "inflate: * literal '%c'\n" :
5005 "inflate: * literal 0x%02x\n", t->base));
5006 *q++ = (Byte)t->base;
5014 /* get extra bits for length */
5016 c = t->base + ((uInt)b & inflate_mask[e]);
5018 Tracevv((stderr, "inflate: * length %u\n", c));
5020 /* decode distance base of block to copy */
5021 GRABBITS(15); /* max bits for distance code */
5022 e = (t = td + ((uInt)b & md))->exop;
5027 /* get extra bits to add to distance base */
5029 GRABBITS(e) /* get extra bits (up to 13) */
5030 d = t->base + ((uInt)b & inflate_mask[e]);
5032 Tracevv((stderr, "inflate: * distance %u\n", d));
5036 if ((uInt)(q - s->window) >= d) /* offset before dest */
5039 *q++ = *r++; c--; /* minimum count is three, */
5040 *q++ = *r++; c--; /* so unroll loop a little */
5042 else /* else offset after destination */
5044 e = d - (uInt)(q - s->window); /* bytes from offset to end */
5045 r = s->end - e; /* pointer to offset */
5046 if (c > e) /* if source crosses, */
5048 c -= e; /* copy to end of window */
5052 r = s->window; /* copy rest from start of window */
5055 do { /* copy all or what's left */
5060 else if ((e & 64) == 0)
5061 e = (t = t->next + ((uInt)b & inflate_mask[e]))->exop;
5064 z->msg = (char*)"invalid distance code";
5067 return Z_DATA_ERROR;
5074 if ((e = (t = t->next + ((uInt)b & inflate_mask[e]))->exop) == 0)
5077 Tracevv((stderr, t->base >= 0x20 && t->base < 0x7f ?
5078 "inflate: * literal '%c'\n" :
5079 "inflate: * literal 0x%02x\n", t->base));
5080 *q++ = (Byte)t->base;
5087 Tracevv((stderr, "inflate: * end of block\n"));
5090 return Z_STREAM_END;
5094 z->msg = (char*)"invalid literal/length code";
5097 return Z_DATA_ERROR;
5100 } while (m >= 258 && n >= 10);
5102 /* not enough input or output--restore pointers and return */
5110 /* zutil.c -- target dependent utility functions for the compression library
5111 * Copyright (C) 1995-1996 Jean-loup Gailly.
5112 * For conditions of distribution and use, see copyright notice in zlib.h
5115 /* From: zutil.c,v 1.17 1996/07/24 13:41:12 me Exp $ */
5121 /* #include "zutil.h" */
5123 #ifndef NO_DUMMY_DECL
5124 struct internal_state {int dummy;}; /* for buggy compilers */
5128 extern void exit OF((int));
5131 const char *z_errmsg[10] = {
5132 "need dictionary", /* Z_NEED_DICT 2 */
5133 "stream end", /* Z_STREAM_END 1 */
5135 "file error", /* Z_ERRNO (-1) */
5136 "stream error", /* Z_STREAM_ERROR (-2) */
5137 "data error", /* Z_DATA_ERROR (-3) */
5138 "insufficient memory", /* Z_MEM_ERROR (-4) */
5139 "buffer error", /* Z_BUF_ERROR (-5) */
5140 "incompatible version",/* Z_VERSION_ERROR (-6) */
5144 const char *zlibVersion()
5146 return ZLIB_VERSION;
5153 fprintf(stderr, "%s\n", m);
5160 void zmemcpy(dest, source, len)
5165 if (len == 0) return;
5167 *dest++ = *source++; /* ??? to be unrolled */
5168 } while (--len != 0);
5171 int zmemcmp(s1, s2, len)
5178 for (j = 0; j < len; j++) {
5179 if (s1[j] != s2[j]) return 2*(s1[j] > s2[j])-1;
5184 void zmemzero(dest, len)
5188 if (len == 0) return;
5190 *dest++ = 0; /* ??? to be unrolled */
5191 } while (--len != 0);
5196 #if (defined( __BORLANDC__) || !defined(SMALL_MEDIUM)) && !defined(__32BIT__)
5197 /* Small and medium model in Turbo C are for now limited to near allocation
5198 * with reduced MAX_WBITS and MAX_MEM_LEVEL
5202 /* Turbo C malloc() does not allow dynamic allocation of 64K bytes
5203 * and farmalloc(64K) returns a pointer with an offset of 8, so we
5204 * must fix the pointer. Warning: the pointer must be put back to its
5205 * original form in order to free it, use zcfree().
5211 local int next_ptr = 0;
5213 typedef struct ptr_table_s {
5218 local ptr_table table[MAX_PTR];
5219 /* This table is used to remember the original form of pointers
5220 * to large buffers (64K). Such pointers are normalized with a zero offset.
5221 * Since MSDOS is not a preemptive multitasking OS, this table is not
5222 * protected from concurrent access. This hack doesn't work anyway on
5223 * a protected system like OS/2. Use Microsoft C instead.
5226 voidpf zcalloc (voidpf opaque, unsigned items, unsigned size)
5228 voidpf buf = opaque; /* just to make some compilers happy */
5229 ulg bsize = (ulg)items*size;
5231 /* If we allocate less than 65520 bytes, we assume that farmalloc
5232 * will return a usable pointer which doesn't have to be normalized.
5234 if (bsize < 65520L) {
5235 buf = farmalloc(bsize);
5236 if (*(ush*)&buf != 0) return buf;
5238 buf = farmalloc(bsize + 16L);
5240 if (buf == NULL || next_ptr >= MAX_PTR) return NULL;
5241 table[next_ptr].org_ptr = buf;
5243 /* Normalize the pointer to seg:0 */
5244 *((ush*)&buf+1) += ((ush)((uch*)buf-0) + 15) >> 4;
5246 table[next_ptr++].new_ptr = buf;
5250 void zcfree (voidpf opaque, voidpf ptr)
5253 if (*(ush*)&ptr != 0) { /* object < 64K */
5257 /* Find the original pointer */
5258 for (n = 0; n < next_ptr; n++) {
5259 if (ptr != table[n].new_ptr) continue;
5261 farfree(table[n].org_ptr);
5262 while (++n < next_ptr) {
5263 table[n-1] = table[n];
5268 ptr = opaque; /* just to make some compilers happy */
5269 Assert(0, "zcfree: ptr not found");
5272 #endif /* __TURBOC__ */
5275 #if defined(M_I86) && !defined(__32BIT__)
5276 /* Microsoft C in 16-bit mode */
5280 #if (!defined(_MSC_VER) || (_MSC_VER < 600))
5281 # define _halloc halloc
5282 # define _hfree hfree
5285 voidpf zcalloc (voidpf opaque, unsigned items, unsigned size)
5287 if (opaque) opaque = 0; /* to make compiler happy */
5288 return _halloc((long)items, size);
5291 void zcfree (voidpf opaque, voidpf ptr)
5293 if (opaque) opaque = 0; /* to make compiler happy */
5300 #ifndef MY_ZCALLOC /* Any system without a special alloc function */
5303 extern voidp calloc OF((uInt items, uInt size));
5304 extern void free OF((voidpf ptr));
5307 voidpf zcalloc (opaque, items, size)
5312 if (opaque) items += size - size; /* make compiler happy */
5313 return (voidpf)calloc(items, size);
5316 void zcfree (opaque, ptr)
5321 if (opaque) return; /* make compiler happy */
5324 #endif /* MY_ZCALLOC */
5328 /* adler32.c -- compute the Adler-32 checksum of a data stream
5329 * Copyright (C) 1995-1996 Mark Adler
5330 * For conditions of distribution and use, see copyright notice in zlib.h
5333 /* From: adler32.c,v 1.10 1996/05/22 11:52:18 me Exp $ */
5335 /* #include "zlib.h" */
5337 #define BASE 65521L /* largest prime smaller than 65536 */
5339 /* NMAX is the largest n such that 255n(n+1)/2 + (n+1)(BASE-1) <= 2^32-1 */
5341 #define DO1(buf,i) {s1 += buf[i]; s2 += s1;}
5342 #define DO2(buf,i) DO1(buf,i); DO1(buf,i+1);
5343 #define DO4(buf,i) DO2(buf,i); DO2(buf,i+2);
5344 #define DO8(buf,i) DO4(buf,i); DO4(buf,i+4);
5345 #define DO16(buf) DO8(buf,0); DO8(buf,8);
5347 /* ========================================================================= */
5348 uLong adler32(adler, buf, len)
5353 unsigned long s1 = adler & 0xffff;
5354 unsigned long s2 = (adler >> 16) & 0xffff;
5357 if (buf == Z_NULL) return 1L;
5360 k = len < NMAX ? len : NMAX;
5374 return (s2 << 16) | s1;