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