1 /* deflate.c -- compress data using the deflation algorithm
2 * Copyright (C) 1995-2022 Jean-loup Gailly and Mark Adler
3 * For conditions of distribution and use, see copyright notice in zlib.h
9 * The "deflation" process depends on being able to identify portions
10 * of the input text which are identical to earlier input (within a
11 * sliding window trailing behind the input currently being processed).
13 * The most straightforward technique turns out to be the fastest for
14 * most input files: try all possible matches and select the longest.
15 * The key feature of this algorithm is that insertions into the string
16 * dictionary are very simple and thus fast, and deletions are avoided
17 * completely. Insertions are performed at each input character, whereas
18 * string matches are performed only when the previous match ends. So it
19 * is preferable to spend more time in matches to allow very fast string
20 * insertions and avoid deletions. The matching algorithm for small
21 * strings is inspired from that of Rabin & Karp. A brute force approach
22 * is used to find longer strings when a small match has been found.
23 * A similar algorithm is used in comic (by Jan-Mark Wams) and freeze
24 * (by Leonid Broukhis).
25 * A previous version of this file used a more sophisticated algorithm
26 * (by Fiala and Greene) which is guaranteed to run in linear amortized
27 * time, but has a larger average cost, uses more memory and is patented.
28 * However the F&G algorithm may be faster for some highly redundant
29 * files if the parameter max_chain_length (described below) is too large.
33 * The idea of lazy evaluation of matches is due to Jan-Mark Wams, and
34 * I found it in 'freeze' written by Leonid Broukhis.
35 * Thanks to many people for bug reports and testing.
39 * Deutsch, L.P.,"DEFLATE Compressed Data Format Specification".
40 * Available in http://tools.ietf.org/html/rfc1951
42 * A description of the Rabin and Karp algorithm is given in the book
43 * "Algorithms" by R. Sedgewick, Addison-Wesley, p252.
45 * Fiala,E.R., and Greene,D.H.
46 * Data Compression with Finite Windows, Comm.ACM, 32,4 (1989) 490-595
54 const char deflate_copyright
[] =
55 " deflate 1.2.13 Copyright 1995-2022 Jean-loup Gailly and Mark Adler ";
57 If you use the zlib library in a product, an acknowledgment is welcome
58 in the documentation of your product. If for some reason you cannot
59 include such an acknowledgment, I would appreciate that you keep this
60 copyright string in the executable of your product.
63 /* ===========================================================================
64 * Function prototypes.
67 need_more
, /* block not completed, need more input or more output */
68 block_done
, /* block flush performed */
69 finish_started
, /* finish started, need only more output at next deflate */
70 finish_done
/* finish done, accept no more input or output */
73 typedef block_state (*compress_func
) OF((deflate_state
*s
, int flush
));
74 /* Compression function. Returns the block state after the call. */
76 local
int deflateStateCheck
OF((z_streamp strm
));
77 local
void slide_hash
OF((deflate_state
*s
));
78 local
void fill_window
OF((deflate_state
*s
));
79 local block_state deflate_stored
OF((deflate_state
*s
, int flush
));
80 local block_state deflate_fast
OF((deflate_state
*s
, int flush
));
82 local block_state deflate_slow
OF((deflate_state
*s
, int flush
));
84 local block_state deflate_rle
OF((deflate_state
*s
, int flush
));
85 local block_state deflate_huff
OF((deflate_state
*s
, int flush
));
86 local
void lm_init
OF((deflate_state
*s
));
87 local
void putShortMSB
OF((deflate_state
*s
, uInt b
));
88 local
void flush_pending
OF((z_streamp strm
));
89 local
unsigned read_buf
OF((z_streamp strm
, Bytef
*buf
, unsigned size
));
90 local uInt longest_match
OF((deflate_state
*s
, IPos cur_match
));
93 local
void check_match
OF((deflate_state
*s
, IPos start
, IPos match
,
97 /* ===========================================================================
102 /* Tail of hash chains */
105 # define TOO_FAR 4096
107 /* Matches of length 3 are discarded if their distance exceeds TOO_FAR */
109 /* Values for max_lazy_match, good_match and max_chain_length, depending on
110 * the desired pack level (0..9). The values given below have been tuned to
111 * exclude worst case performance for pathological files. Better values may be
112 * found for specific files.
114 typedef struct config_s
{
115 ush good_length
; /* reduce lazy search above this match length */
116 ush max_lazy
; /* do not perform lazy search above this match length */
117 ush nice_length
; /* quit search above this match length */
123 local
const config configuration_table
[2] = {
124 /* good lazy nice chain */
125 /* 0 */ {0, 0, 0, 0, deflate_stored
}, /* store only */
126 /* 1 */ {4, 4, 8, 4, deflate_fast
}}; /* max speed, no lazy matches */
128 local
const config configuration_table
[10] = {
129 /* good lazy nice chain */
130 /* 0 */ {0, 0, 0, 0, deflate_stored
}, /* store only */
131 /* 1 */ {4, 4, 8, 4, deflate_fast
}, /* max speed, no lazy matches */
132 /* 2 */ {4, 5, 16, 8, deflate_fast
},
133 /* 3 */ {4, 6, 32, 32, deflate_fast
},
135 /* 4 */ {4, 4, 16, 16, deflate_slow
}, /* lazy matches */
136 /* 5 */ {8, 16, 32, 32, deflate_slow
},
137 /* 6 */ {8, 16, 128, 128, deflate_slow
},
138 /* 7 */ {8, 32, 128, 256, deflate_slow
},
139 /* 8 */ {32, 128, 258, 1024, deflate_slow
},
140 /* 9 */ {32, 258, 258, 4096, deflate_slow
}}; /* max compression */
143 /* Note: the deflate() code requires max_lazy >= MIN_MATCH and max_chain >= 4
144 * For deflate_fast() (levels <= 3) good is ignored and lazy has a different
148 /* rank Z_BLOCK between Z_NO_FLUSH and Z_PARTIAL_FLUSH */
149 #define RANK(f) (((f) * 2) - ((f) > 4 ? 9 : 0))
151 /* ===========================================================================
152 * Update a hash value with the given input byte
153 * IN assertion: all calls to UPDATE_HASH are made with consecutive input
154 * characters, so that a running hash key can be computed from the previous
155 * key instead of complete recalculation each time.
157 #define UPDATE_HASH(s,h,c) (h = (((h) << s->hash_shift) ^ (c)) & s->hash_mask)
160 /* ===========================================================================
161 * Insert string str in the dictionary and set match_head to the previous head
162 * of the hash chain (the most recent string with same hash key). Return
163 * the previous length of the hash chain.
164 * If this file is compiled with -DFASTEST, the compression level is forced
165 * to 1, and no hash chains are maintained.
166 * IN assertion: all calls to INSERT_STRING are made with consecutive input
167 * characters and the first MIN_MATCH bytes of str are valid (except for
168 * the last MIN_MATCH-1 bytes of the input file).
171 #define INSERT_STRING(s, str, match_head) \
172 (UPDATE_HASH(s, s->ins_h, s->window[(str) + (MIN_MATCH-1)]), \
173 match_head = s->head[s->ins_h], \
174 s->head[s->ins_h] = (Pos)(str))
176 #define INSERT_STRING(s, str, match_head) \
177 (UPDATE_HASH(s, s->ins_h, s->window[(str) + (MIN_MATCH-1)]), \
178 match_head = s->prev[(str) & s->w_mask] = s->head[s->ins_h], \
179 s->head[s->ins_h] = (Pos)(str))
182 /* ===========================================================================
183 * Initialize the hash table (avoiding 64K overflow for 16 bit systems).
184 * prev[] will be initialized on the fly.
186 #define CLEAR_HASH(s) \
188 s->head[s->hash_size - 1] = NIL; \
189 zmemzero((Bytef *)s->head, \
190 (unsigned)(s->hash_size - 1)*sizeof(*s->head)); \
193 /* ===========================================================================
194 * Slide the hash table when sliding the window down (could be avoided with 32
195 * bit values at the expense of memory usage). We slide even when level == 0 to
196 * keep the hash table consistent if we switch back to level > 0 later.
198 local
void slide_hash(
203 uInt wsize
= s
->w_size
;
209 *p
= (Pos
)(m
>= wsize
? m
- wsize
: NIL
);
216 *p
= (Pos
)(m
>= wsize
? m
- wsize
: NIL
);
217 /* If n is not on any hash chain, prev[n] is garbage but
218 * its value will never be used.
224 /* ========================================================================= */
225 int ZEXPORT
deflateInit_(
231 return deflateInit2_(strm
, level
, Z_DEFLATED
, MAX_WBITS
, DEF_MEM_LEVEL
,
232 Z_DEFAULT_STRATEGY
, version
, stream_size
);
233 /* To do: ignore strm->next_in if we use it as window */
236 /* ========================================================================= */
237 int ZEXPORT
deflateInit2_(
249 static const char my_version
[] = ZLIB_VERSION
;
251 if (version
== Z_NULL
|| version
[0] != my_version
[0] ||
252 stream_size
!= sizeof(z_stream
)) {
253 return Z_VERSION_ERROR
;
255 if (strm
== Z_NULL
) return Z_STREAM_ERROR
;
258 if (strm
->zalloc
== (alloc_func
)0) {
260 return Z_STREAM_ERROR
;
262 strm
->zalloc
= zcalloc
;
263 strm
->opaque
= (voidpf
)0;
266 if (strm
->zfree
== (free_func
)0)
268 return Z_STREAM_ERROR
;
270 strm
->zfree
= zcfree
;
274 if (level
!= 0) level
= 1;
276 if (level
== Z_DEFAULT_COMPRESSION
) level
= 6;
279 if (windowBits
< 0) { /* suppress zlib wrapper */
281 if (windowBits
< -15)
282 return Z_STREAM_ERROR
;
283 windowBits
= -windowBits
;
286 else if (windowBits
> 15) {
287 wrap
= 2; /* write gzip wrapper instead */
291 if (memLevel
< 1 || memLevel
> MAX_MEM_LEVEL
|| method
!= Z_DEFLATED
||
292 windowBits
< 8 || windowBits
> 15 || level
< 0 || level
> 9 ||
293 strategy
< 0 || strategy
> Z_FIXED
|| (windowBits
== 8 && wrap
!= 1)) {
294 return Z_STREAM_ERROR
;
296 if (windowBits
== 8) windowBits
= 9; /* until 256-byte window bug fixed */
297 s
= (deflate_state
*) ZALLOC(strm
, 1, sizeof(deflate_state
));
298 if (s
== Z_NULL
) return Z_MEM_ERROR
;
299 strm
->state
= (struct internal_state FAR
*)s
;
301 s
->status
= INIT_STATE
; /* to pass state test in deflateReset() */
305 s
->w_bits
= (uInt
)windowBits
;
306 s
->w_size
= 1 << s
->w_bits
;
307 s
->w_mask
= s
->w_size
- 1;
309 s
->hash_bits
= (uInt
)memLevel
+ 7;
310 s
->hash_size
= 1 << s
->hash_bits
;
311 s
->hash_mask
= s
->hash_size
- 1;
312 s
->hash_shift
= ((s
->hash_bits
+ MIN_MATCH
-1) / MIN_MATCH
);
314 s
->window
= (Bytef
*) ZALLOC(strm
, s
->w_size
, 2*sizeof(Byte
));
315 s
->prev
= (Posf
*) ZALLOC(strm
, s
->w_size
, sizeof(Pos
));
316 s
->head
= (Posf
*) ZALLOC(strm
, s
->hash_size
, sizeof(Pos
));
318 s
->high_water
= 0; /* nothing written to s->window yet */
320 s
->lit_bufsize
= 1 << (memLevel
+ 6); /* 16K elements by default */
322 /* We overlay pending_buf and sym_buf. This works since the average size
323 * for length/distance pairs over any compressed block is assured to be 31
326 * Analysis: The longest fixed codes are a length code of 8 bits plus 5
327 * extra bits, for lengths 131 to 257. The longest fixed distance codes are
328 * 5 bits plus 13 extra bits, for distances 16385 to 32768. The longest
329 * possible fixed-codes length/distance pair is then 31 bits total.
331 * sym_buf starts one-fourth of the way into pending_buf. So there are
332 * three bytes in sym_buf for every four bytes in pending_buf. Each symbol
333 * in sym_buf is three bytes -- two for the distance and one for the
334 * literal/length. As each symbol is consumed, the pointer to the next
335 * sym_buf value to read moves forward three bytes. From that symbol, up to
336 * 31 bits are written to pending_buf. The closest the written pending_buf
337 * bits gets to the next sym_buf symbol to read is just before the last
338 * code is written. At that time, 31*(n - 2) bits have been written, just
339 * after 24*(n - 2) bits have been consumed from sym_buf. sym_buf starts at
340 * 8*n bits into pending_buf. (Note that the symbol buffer fills when n - 1
341 * symbols are written.) The closest the writing gets to what is unread is
342 * then n + 14 bits. Here n is lit_bufsize, which is 16384 by default, and
343 * can range from 128 to 32768.
345 * Therefore, at a minimum, there are 142 bits of space between what is
346 * written and what is read in the overlain buffers, so the symbols cannot
347 * be overwritten by the compressed data. That space is actually 139 bits,
348 * due to the three-bit fixed-code block header.
350 * That covers the case where either Z_FIXED is specified, forcing fixed
351 * codes, or when the use of fixed codes is chosen, because that choice
352 * results in a smaller compressed block than dynamic codes. That latter
353 * condition then assures that the above analysis also covers all dynamic
354 * blocks. A dynamic-code block will only be chosen to be emitted if it has
355 * fewer bits than a fixed-code block would for the same set of symbols.
356 * Therefore its average symbol length is assured to be less than 31. So
357 * the compressed data for a dynamic block also cannot overwrite the
358 * symbols from which it is being constructed.
361 s
->pending_buf
= (uchf
*) ZALLOC(strm
, s
->lit_bufsize
, 4);
362 s
->pending_buf_size
= (ulg
)s
->lit_bufsize
* 4;
364 if (s
->window
== Z_NULL
|| s
->prev
== Z_NULL
|| s
->head
== Z_NULL
||
365 s
->pending_buf
== Z_NULL
) {
366 s
->status
= FINISH_STATE
;
367 strm
->msg
= ERR_MSG(Z_MEM_ERROR
);
371 s
->sym_buf
= s
->pending_buf
+ s
->lit_bufsize
;
372 s
->sym_end
= (s
->lit_bufsize
- 1) * 3;
373 /* We avoid equality with lit_bufsize*3 because of wraparound at 64K
374 * on 16 bit machines and because stored blocks are restricted to
379 s
->strategy
= strategy
;
380 s
->method
= (Byte
)method
;
382 return deflateReset(strm
);
385 /* =========================================================================
386 * Check for a valid deflate stream state. Return 0 if ok, 1 if not.
388 local
int deflateStateCheck(
392 if (strm
== Z_NULL
||
393 strm
->zalloc
== (alloc_func
)0 || strm
->zfree
== (free_func
)0)
396 if (s
== Z_NULL
|| s
->strm
!= strm
|| (s
->status
!= INIT_STATE
&&
398 s
->status
!= GZIP_STATE
&&
400 s
->status
!= EXTRA_STATE
&&
401 s
->status
!= NAME_STATE
&&
402 s
->status
!= COMMENT_STATE
&&
403 s
->status
!= HCRC_STATE
&&
404 s
->status
!= BUSY_STATE
&&
405 s
->status
!= FINISH_STATE
))
410 /* ========================================================================= */
411 int ZEXPORT
deflateSetDictionary(
413 const Bytef
*dictionary
,
420 z_const
unsigned char *next
;
422 if (deflateStateCheck(strm
) || dictionary
== Z_NULL
)
423 return Z_STREAM_ERROR
;
426 if (wrap
== 2 || (wrap
== 1 && s
->status
!= INIT_STATE
) || s
->lookahead
)
427 return Z_STREAM_ERROR
;
429 /* when using zlib wrappers, compute Adler-32 for provided dictionary */
431 strm
->adler
= adler32(strm
->adler
, dictionary
, dictLength
);
432 s
->wrap
= 0; /* avoid computing Adler-32 in read_buf */
434 /* if dictionary would fill window, just replace the history */
435 if (dictLength
>= s
->w_size
) {
436 if (wrap
== 0) { /* already empty otherwise */
442 dictionary
+= dictLength
- s
->w_size
; /* use the tail */
443 dictLength
= s
->w_size
;
446 /* insert dictionary into window and hash */
447 avail
= strm
->avail_in
;
448 next
= strm
->next_in
;
449 strm
->avail_in
= dictLength
;
450 strm
->next_in
= (z_const Bytef
*)dictionary
;
452 while (s
->lookahead
>= MIN_MATCH
) {
454 n
= s
->lookahead
- (MIN_MATCH
-1);
456 UPDATE_HASH(s
, s
->ins_h
, s
->window
[str
+ MIN_MATCH
-1]);
458 s
->prev
[str
& s
->w_mask
] = s
->head
[s
->ins_h
];
460 s
->head
[s
->ins_h
] = (Pos
)str
;
464 s
->lookahead
= MIN_MATCH
-1;
467 s
->strstart
+= s
->lookahead
;
468 s
->block_start
= (long)s
->strstart
;
469 s
->insert
= s
->lookahead
;
471 s
->match_length
= s
->prev_length
= MIN_MATCH
-1;
472 s
->match_available
= 0;
473 strm
->next_in
= next
;
474 strm
->avail_in
= avail
;
479 /* ========================================================================= */
480 int ZEXPORT
deflateGetDictionary(
488 if (deflateStateCheck(strm
))
489 return Z_STREAM_ERROR
;
491 len
= s
->strstart
+ s
->lookahead
;
494 if (dictionary
!= Z_NULL
&& len
)
495 zmemcpy(dictionary
, s
->window
+ s
->strstart
+ s
->lookahead
- len
, len
);
496 if (dictLength
!= Z_NULL
)
501 /* ========================================================================= */
502 int ZEXPORT
deflateResetKeep(
507 if (deflateStateCheck(strm
)) {
508 return Z_STREAM_ERROR
;
511 strm
->total_in
= strm
->total_out
= 0;
512 strm
->msg
= Z_NULL
; /* use zfree if we ever allocate msg dynamically */
513 strm
->data_type
= Z_UNKNOWN
;
515 s
= (deflate_state
*)strm
->state
;
517 s
->pending_out
= s
->pending_buf
;
520 s
->wrap
= -s
->wrap
; /* was made negative by deflate(..., Z_FINISH); */
524 s
->wrap
== 2 ? GZIP_STATE
:
529 s
->wrap
== 2 ? crc32(0L, Z_NULL
, 0) :
531 adler32(0L, Z_NULL
, 0);
539 /* ========================================================================= */
540 int ZEXPORT
deflateReset(
545 ret
= deflateResetKeep(strm
);
547 lm_init(strm
->state
);
551 /* ========================================================================= */
552 int ZEXPORT
deflateSetHeader(
556 if (deflateStateCheck(strm
) || strm
->state
->wrap
!= 2)
557 return Z_STREAM_ERROR
;
558 strm
->state
->gzhead
= head
;
562 /* ========================================================================= */
563 int ZEXPORT
deflatePending(
568 if (deflateStateCheck(strm
)) return Z_STREAM_ERROR
;
569 if (pending
!= Z_NULL
)
570 *pending
= strm
->state
->pending
;
572 *bits
= strm
->state
->bi_valid
;
576 /* ========================================================================= */
577 int ZEXPORT
deflatePrime(
585 if (deflateStateCheck(strm
)) return Z_STREAM_ERROR
;
587 if (bits
< 0 || bits
> 16 ||
588 s
->sym_buf
< s
->pending_out
+ ((Buf_size
+ 7) >> 3))
591 put
= Buf_size
- s
->bi_valid
;
594 s
->bi_buf
|= (ush
)((value
& ((1 << put
) - 1)) << s
->bi_valid
);
603 /* ========================================================================= */
604 int ZEXPORT
deflateParams(
612 if (deflateStateCheck(strm
)) return Z_STREAM_ERROR
;
616 if (level
!= 0) level
= 1;
618 if (level
== Z_DEFAULT_COMPRESSION
) level
= 6;
620 if (level
< 0 || level
> 9 || strategy
< 0 || strategy
> Z_FIXED
) {
621 return Z_STREAM_ERROR
;
623 func
= configuration_table
[s
->level
].func
;
625 if ((strategy
!= s
->strategy
|| func
!= configuration_table
[level
].func
) &&
626 s
->last_flush
!= -2) {
627 /* Flush the last buffer: */
628 int err
= deflate(strm
, Z_BLOCK
);
629 if (err
== Z_STREAM_ERROR
)
631 if (strm
->avail_in
|| (s
->strstart
- s
->block_start
) + s
->lookahead
)
634 if (s
->level
!= level
) {
635 if (s
->level
== 0 && s
->matches
!= 0) {
643 s
->max_lazy_match
= configuration_table
[level
].max_lazy
;
644 s
->good_match
= configuration_table
[level
].good_length
;
645 s
->nice_match
= configuration_table
[level
].nice_length
;
646 s
->max_chain_length
= configuration_table
[level
].max_chain
;
648 s
->strategy
= strategy
;
652 /* ========================================================================= */
653 int ZEXPORT
deflateTune(
662 if (deflateStateCheck(strm
)) return Z_STREAM_ERROR
;
664 s
->good_match
= (uInt
)good_length
;
665 s
->max_lazy_match
= (uInt
)max_lazy
;
666 s
->nice_match
= nice_length
;
667 s
->max_chain_length
= (uInt
)max_chain
;
671 /* =========================================================================
672 * For the default windowBits of 15 and memLevel of 8, this function returns a
673 * close to exact, as well as small, upper bound on the compressed size. This
674 * is an expansion of ~0.03%, plus a small constant.
676 * For any setting other than those defaults for windowBits and memLevel, one
677 * of two worst case bounds is returned. This is at most an expansion of ~4% or
678 * ~13%, plus a small constant.
680 * Both the 0.03% and 4% derive from the overhead of stored blocks. The first
681 * one is for stored blocks of 16383 bytes (memLevel == 8), whereas the second
682 * is for stored blocks of 127 bytes (the worst case memLevel == 1). The
683 * expansion results from five bytes of header for each stored block.
685 * The larger expansion of 13% results from a window size less than or equal to
686 * the symbols buffer size (windowBits <= memLevel + 7). In that case some of
687 * the data being compressed may have slid out of the sliding window, impeding
688 * a stored block from being emitted. Then the only choice is a fixed or
689 * dynamic block, where a fixed block limits the maximum expansion to 9 bits
690 * per 8-bit byte, plus 10 bits for every block. The smallest block size for
691 * which this can occur is 255 (memLevel == 2).
693 * Shifts are used to approximate divisions, for speed.
695 uLong ZEXPORT
deflateBound(
700 uLong fixedlen
, storelen
, wraplen
;
702 /* upper bound for fixed blocks with 9-bit literals and length 255
703 (memLevel == 2, which is the lowest that may not use stored blocks) --
704 ~13% overhead plus a small constant */
705 fixedlen
= sourceLen
+ (sourceLen
>> 3) + (sourceLen
>> 8) +
706 (sourceLen
>> 9) + 4;
708 /* upper bound for stored blocks with length 127 (memLevel == 1) --
709 ~4% overhead plus a small constant */
710 storelen
= sourceLen
+ (sourceLen
>> 5) + (sourceLen
>> 7) +
711 (sourceLen
>> 11) + 7;
713 /* if can't get parameters, return larger bound plus a zlib wrapper */
714 if (deflateStateCheck(strm
))
715 return (fixedlen
> storelen
? fixedlen
: storelen
) + 6;
717 /* compute wrapper length */
720 case 0: /* raw deflate */
723 case 1: /* zlib wrapper */
724 wraplen
= 6 + (s
->strstart
? 4 : 0);
727 case 2: /* gzip wrapper */
729 if (s
->gzhead
!= Z_NULL
) { /* user-supplied gzip header */
731 if (s
->gzhead
->extra
!= Z_NULL
)
732 wraplen
+= 2 + s
->gzhead
->extra_len
;
733 str
= s
->gzhead
->name
;
738 str
= s
->gzhead
->comment
;
748 default: /* for compiler happiness */
752 /* if not default parameters, return one of the conservative bounds */
753 if (s
->w_bits
!= 15 || s
->hash_bits
!= 8 + 7)
754 return (s
->w_bits
<= s
->hash_bits
? fixedlen
: storelen
) + wraplen
;
756 /* default settings: return tight bound for that case -- ~0.03% overhead
757 plus a small constant */
758 return sourceLen
+ (sourceLen
>> 12) + (sourceLen
>> 14) +
759 (sourceLen
>> 25) + 13 - 6 + wraplen
;
762 /* =========================================================================
763 * Put a short in the pending buffer. The 16-bit value is put in MSB order.
764 * IN assertion: the stream state is correct and there is enough room in
767 local
void putShortMSB(
771 put_byte(s
, (Byte
)(b
>> 8));
772 put_byte(s
, (Byte
)(b
& 0xff));
775 /* =========================================================================
776 * Flush as much pending output as possible. All deflate() output, except for
777 * some deflate_stored() output, goes through this function so some
778 * applications may wish to modify it to avoid allocating a large
779 * strm->next_out buffer and copying into it. (See also read_buf()).
781 local
void flush_pending(
785 deflate_state
*s
= strm
->state
;
789 if (len
> strm
->avail_out
) len
= strm
->avail_out
;
790 if (len
== 0) return;
792 zmemcpy(strm
->next_out
, s
->pending_out
, len
);
793 strm
->next_out
+= len
;
794 s
->pending_out
+= len
;
795 strm
->total_out
+= len
;
796 strm
->avail_out
-= len
;
798 if (s
->pending
== 0) {
799 s
->pending_out
= s
->pending_buf
;
803 /* ===========================================================================
804 * Update the header CRC with the bytes s->pending_buf[beg..s->pending - 1].
806 #define HCRC_UPDATE(beg) \
808 if (s->gzhead->hcrc && s->pending > (beg)) \
809 strm->adler = crc32(strm->adler, s->pending_buf + (beg), \
810 s->pending - (beg)); \
813 /* ========================================================================= */
818 int old_flush
; /* value of flush param for previous deflate call */
821 if (deflateStateCheck(strm
) || flush
> Z_BLOCK
|| flush
< 0) {
822 return Z_STREAM_ERROR
;
826 if (strm
->next_out
== Z_NULL
||
827 (strm
->avail_in
!= 0 && strm
->next_in
== Z_NULL
) ||
828 (s
->status
== FINISH_STATE
&& flush
!= Z_FINISH
)) {
829 ERR_RETURN(strm
, Z_STREAM_ERROR
);
831 if (strm
->avail_out
== 0) ERR_RETURN(strm
, Z_BUF_ERROR
);
833 old_flush
= s
->last_flush
;
834 s
->last_flush
= flush
;
836 /* Flush as much pending output as possible */
837 if (s
->pending
!= 0) {
839 if (strm
->avail_out
== 0) {
840 /* Since avail_out is 0, deflate will be called again with
841 * more output space, but possibly with both pending and
842 * avail_in equal to zero. There won't be anything to do,
843 * but this is not an error situation so make sure we
844 * return OK instead of BUF_ERROR at next call of deflate:
850 /* Make sure there is something to do and avoid duplicate consecutive
851 * flushes. For repeated and useless calls with Z_FINISH, we keep
852 * returning Z_STREAM_END instead of Z_BUF_ERROR.
854 } else if (strm
->avail_in
== 0 && RANK(flush
) <= RANK(old_flush
) &&
856 ERR_RETURN(strm
, Z_BUF_ERROR
);
859 /* User must not provide more input after the first FINISH: */
860 if (s
->status
== FINISH_STATE
&& strm
->avail_in
!= 0) {
861 ERR_RETURN(strm
, Z_BUF_ERROR
);
864 /* Write the header */
865 if (s
->status
== INIT_STATE
&& s
->wrap
== 0)
866 s
->status
= BUSY_STATE
;
867 if (s
->status
== INIT_STATE
) {
869 uInt header
= (Z_DEFLATED
+ ((s
->w_bits
- 8) << 4)) << 8;
872 if (s
->strategy
>= Z_HUFFMAN_ONLY
|| s
->level
< 2)
874 else if (s
->level
< 6)
876 else if (s
->level
== 6)
880 header
|= (level_flags
<< 6);
881 if (s
->strstart
!= 0) header
|= PRESET_DICT
;
882 header
+= 31 - (header
% 31);
884 putShortMSB(s
, header
);
886 /* Save the adler32 of the preset dictionary: */
887 if (s
->strstart
!= 0) {
888 putShortMSB(s
, (uInt
)(strm
->adler
>> 16));
889 putShortMSB(s
, (uInt
)(strm
->adler
& 0xffff));
891 strm
->adler
= adler32(0L, Z_NULL
, 0);
892 s
->status
= BUSY_STATE
;
894 /* Compression must start with an empty pending buffer */
896 if (s
->pending
!= 0) {
902 if (s
->status
== GZIP_STATE
) {
904 strm
->adler
= crc32(0L, Z_NULL
, 0);
908 if (s
->gzhead
== Z_NULL
) {
914 put_byte(s
, s
->level
== 9 ? 2 :
915 (s
->strategy
>= Z_HUFFMAN_ONLY
|| s
->level
< 2 ?
917 put_byte(s
, OS_CODE
);
918 s
->status
= BUSY_STATE
;
920 /* Compression must start with an empty pending buffer */
922 if (s
->pending
!= 0) {
928 put_byte(s
, (s
->gzhead
->text
? 1 : 0) +
929 (s
->gzhead
->hcrc
? 2 : 0) +
930 (s
->gzhead
->extra
== Z_NULL
? 0 : 4) +
931 (s
->gzhead
->name
== Z_NULL
? 0 : 8) +
932 (s
->gzhead
->comment
== Z_NULL
? 0 : 16)
934 put_byte(s
, (Byte
)(s
->gzhead
->time
& 0xff));
935 put_byte(s
, (Byte
)((s
->gzhead
->time
>> 8) & 0xff));
936 put_byte(s
, (Byte
)((s
->gzhead
->time
>> 16) & 0xff));
937 put_byte(s
, (Byte
)((s
->gzhead
->time
>> 24) & 0xff));
938 put_byte(s
, s
->level
== 9 ? 2 :
939 (s
->strategy
>= Z_HUFFMAN_ONLY
|| s
->level
< 2 ?
941 put_byte(s
, s
->gzhead
->os
& 0xff);
942 if (s
->gzhead
->extra
!= Z_NULL
) {
943 put_byte(s
, s
->gzhead
->extra_len
& 0xff);
944 put_byte(s
, (s
->gzhead
->extra_len
>> 8) & 0xff);
947 strm
->adler
= crc32(strm
->adler
, s
->pending_buf
,
950 s
->status
= EXTRA_STATE
;
953 if (s
->status
== EXTRA_STATE
) {
954 if (s
->gzhead
->extra
!= Z_NULL
) {
955 ulg beg
= s
->pending
; /* start of bytes to update crc */
956 uInt left
= (s
->gzhead
->extra_len
& 0xffff) - s
->gzindex
;
957 while (s
->pending
+ left
> s
->pending_buf_size
) {
958 uInt copy
= s
->pending_buf_size
- s
->pending
;
959 zmemcpy(s
->pending_buf
+ s
->pending
,
960 s
->gzhead
->extra
+ s
->gzindex
, copy
);
961 s
->pending
= s
->pending_buf_size
;
965 if (s
->pending
!= 0) {
972 zmemcpy(s
->pending_buf
+ s
->pending
,
973 s
->gzhead
->extra
+ s
->gzindex
, left
);
978 s
->status
= NAME_STATE
;
980 if (s
->status
== NAME_STATE
) {
981 if (s
->gzhead
->name
!= Z_NULL
) {
982 ulg beg
= s
->pending
; /* start of bytes to update crc */
985 if (s
->pending
== s
->pending_buf_size
) {
988 if (s
->pending
!= 0) {
994 val
= s
->gzhead
->name
[s
->gzindex
++];
1000 s
->status
= COMMENT_STATE
;
1002 if (s
->status
== COMMENT_STATE
) {
1003 if (s
->gzhead
->comment
!= Z_NULL
) {
1004 ulg beg
= s
->pending
; /* start of bytes to update crc */
1007 if (s
->pending
== s
->pending_buf_size
) {
1009 flush_pending(strm
);
1010 if (s
->pending
!= 0) {
1016 val
= s
->gzhead
->comment
[s
->gzindex
++];
1021 s
->status
= HCRC_STATE
;
1023 if (s
->status
== HCRC_STATE
) {
1024 if (s
->gzhead
->hcrc
) {
1025 if (s
->pending
+ 2 > s
->pending_buf_size
) {
1026 flush_pending(strm
);
1027 if (s
->pending
!= 0) {
1032 put_byte(s
, (Byte
)(strm
->adler
& 0xff));
1033 put_byte(s
, (Byte
)((strm
->adler
>> 8) & 0xff));
1034 strm
->adler
= crc32(0L, Z_NULL
, 0);
1036 s
->status
= BUSY_STATE
;
1038 /* Compression must start with an empty pending buffer */
1039 flush_pending(strm
);
1040 if (s
->pending
!= 0) {
1047 /* Start a new block or continue the current one.
1049 if (strm
->avail_in
!= 0 || s
->lookahead
!= 0 ||
1050 (flush
!= Z_NO_FLUSH
&& s
->status
!= FINISH_STATE
)) {
1053 bstate
= s
->level
== 0 ? deflate_stored(s
, flush
) :
1054 s
->strategy
== Z_HUFFMAN_ONLY
? deflate_huff(s
, flush
) :
1055 s
->strategy
== Z_RLE
? deflate_rle(s
, flush
) :
1056 (*(configuration_table
[s
->level
].func
))(s
, flush
);
1058 if (bstate
== finish_started
|| bstate
== finish_done
) {
1059 s
->status
= FINISH_STATE
;
1061 if (bstate
== need_more
|| bstate
== finish_started
) {
1062 if (strm
->avail_out
== 0) {
1063 s
->last_flush
= -1; /* avoid BUF_ERROR next call, see above */
1066 /* If flush != Z_NO_FLUSH && avail_out == 0, the next call
1067 * of deflate should use the same flush parameter to make sure
1068 * that the flush is complete. So we don't have to output an
1069 * empty block here, this will be done at next call. This also
1070 * ensures that for a very small output buffer, we emit at most
1074 if (bstate
== block_done
) {
1075 if (flush
== Z_PARTIAL_FLUSH
) {
1077 } else if (flush
!= Z_BLOCK
) { /* FULL_FLUSH or SYNC_FLUSH */
1078 _tr_stored_block(s
, (char*)0, 0L, 0);
1079 /* For a full flush, this empty block will be recognized
1080 * as a special marker by inflate_sync().
1082 if (flush
== Z_FULL_FLUSH
) {
1083 CLEAR_HASH(s
); /* forget history */
1084 if (s
->lookahead
== 0) {
1086 s
->block_start
= 0L;
1091 flush_pending(strm
);
1092 if (strm
->avail_out
== 0) {
1093 s
->last_flush
= -1; /* avoid BUF_ERROR at next call, see above */
1099 if (flush
!= Z_FINISH
) return Z_OK
;
1100 if (s
->wrap
<= 0) return Z_STREAM_END
;
1102 /* Write the trailer */
1105 put_byte(s
, (Byte
)(strm
->adler
& 0xff));
1106 put_byte(s
, (Byte
)((strm
->adler
>> 8) & 0xff));
1107 put_byte(s
, (Byte
)((strm
->adler
>> 16) & 0xff));
1108 put_byte(s
, (Byte
)((strm
->adler
>> 24) & 0xff));
1109 put_byte(s
, (Byte
)(strm
->total_in
& 0xff));
1110 put_byte(s
, (Byte
)((strm
->total_in
>> 8) & 0xff));
1111 put_byte(s
, (Byte
)((strm
->total_in
>> 16) & 0xff));
1112 put_byte(s
, (Byte
)((strm
->total_in
>> 24) & 0xff));
1117 putShortMSB(s
, (uInt
)(strm
->adler
>> 16));
1118 putShortMSB(s
, (uInt
)(strm
->adler
& 0xffff));
1120 flush_pending(strm
);
1121 /* If avail_out is zero, the application will call deflate again
1122 * to flush the rest.
1124 if (s
->wrap
> 0) s
->wrap
= -s
->wrap
; /* write the trailer only once! */
1125 return s
->pending
!= 0 ? Z_OK
: Z_STREAM_END
;
1128 /* ========================================================================= */
1129 int ZEXPORT
deflateEnd(
1134 if (deflateStateCheck(strm
)) return Z_STREAM_ERROR
;
1136 status
= strm
->state
->status
;
1138 /* Deallocate in reverse order of allocations: */
1139 TRY_FREE(strm
, strm
->state
->pending_buf
);
1140 TRY_FREE(strm
, strm
->state
->head
);
1141 TRY_FREE(strm
, strm
->state
->prev
);
1142 TRY_FREE(strm
, strm
->state
->window
);
1144 ZFREE(strm
, strm
->state
);
1145 strm
->state
= Z_NULL
;
1147 return status
== BUSY_STATE
? Z_DATA_ERROR
: Z_OK
;
1150 /* =========================================================================
1151 * Copy the source state to the destination state.
1152 * To simplify the source, this is not supported for 16-bit MSDOS (which
1153 * doesn't have enough memory anyway to duplicate compression states).
1155 int ZEXPORT
deflateCopy(
1160 return Z_STREAM_ERROR
;
1166 if (deflateStateCheck(source
) || dest
== Z_NULL
) {
1167 return Z_STREAM_ERROR
;
1172 zmemcpy((voidpf
)dest
, (voidpf
)source
, sizeof(z_stream
));
1174 ds
= (deflate_state
*) ZALLOC(dest
, 1, sizeof(deflate_state
));
1175 if (ds
== Z_NULL
) return Z_MEM_ERROR
;
1176 dest
->state
= (struct internal_state FAR
*) ds
;
1177 zmemcpy((voidpf
)ds
, (voidpf
)ss
, sizeof(deflate_state
));
1180 ds
->window
= (Bytef
*) ZALLOC(dest
, ds
->w_size
, 2*sizeof(Byte
));
1181 ds
->prev
= (Posf
*) ZALLOC(dest
, ds
->w_size
, sizeof(Pos
));
1182 ds
->head
= (Posf
*) ZALLOC(dest
, ds
->hash_size
, sizeof(Pos
));
1183 ds
->pending_buf
= (uchf
*) ZALLOC(dest
, ds
->lit_bufsize
, 4);
1185 if (ds
->window
== Z_NULL
|| ds
->prev
== Z_NULL
|| ds
->head
== Z_NULL
||
1186 ds
->pending_buf
== Z_NULL
) {
1190 /* following zmemcpy do not work for 16-bit MSDOS */
1191 zmemcpy(ds
->window
, ss
->window
, ds
->w_size
* 2 * sizeof(Byte
));
1192 zmemcpy((voidpf
)ds
->prev
, (voidpf
)ss
->prev
, ds
->w_size
* sizeof(Pos
));
1193 zmemcpy((voidpf
)ds
->head
, (voidpf
)ss
->head
, ds
->hash_size
* sizeof(Pos
));
1194 zmemcpy(ds
->pending_buf
, ss
->pending_buf
, (uInt
)ds
->pending_buf_size
);
1196 ds
->pending_out
= ds
->pending_buf
+ (ss
->pending_out
- ss
->pending_buf
);
1197 ds
->sym_buf
= ds
->pending_buf
+ ds
->lit_bufsize
;
1199 ds
->l_desc
.dyn_tree
= ds
->dyn_ltree
;
1200 ds
->d_desc
.dyn_tree
= ds
->dyn_dtree
;
1201 ds
->bl_desc
.dyn_tree
= ds
->bl_tree
;
1204 #endif /* MAXSEG_64K */
1207 /* ===========================================================================
1208 * Read a new buffer from the current input stream, update the adler32
1209 * and total number of bytes read. All deflate() input goes through
1210 * this function so some applications may wish to modify it to avoid
1211 * allocating a large strm->next_in buffer and copying from it.
1212 * (See also flush_pending()).
1214 local
unsigned read_buf(
1219 unsigned len
= strm
->avail_in
;
1221 if (len
> size
) len
= size
;
1222 if (len
== 0) return 0;
1224 strm
->avail_in
-= len
;
1226 zmemcpy(buf
, strm
->next_in
, len
);
1227 if (strm
->state
->wrap
== 1) {
1228 strm
->adler
= adler32(strm
->adler
, buf
, len
);
1231 else if (strm
->state
->wrap
== 2) {
1232 strm
->adler
= crc32(strm
->adler
, buf
, len
);
1235 strm
->next_in
+= len
;
1236 strm
->total_in
+= len
;
1241 /* ===========================================================================
1242 * Initialize the "longest match" routines for a new zlib stream
1247 s
->window_size
= (ulg
)2L*s
->w_size
;
1251 /* Set the default configuration parameters:
1253 s
->max_lazy_match
= configuration_table
[s
->level
].max_lazy
;
1254 s
->good_match
= configuration_table
[s
->level
].good_length
;
1255 s
->nice_match
= configuration_table
[s
->level
].nice_length
;
1256 s
->max_chain_length
= configuration_table
[s
->level
].max_chain
;
1259 s
->block_start
= 0L;
1262 s
->match_length
= s
->prev_length
= MIN_MATCH
-1;
1263 s
->match_available
= 0;
1268 /* ===========================================================================
1269 * Set match_start to the longest match starting at the given string and
1270 * return its length. Matches shorter or equal to prev_length are discarded,
1271 * in which case the result is equal to prev_length and match_start is
1273 * IN assertions: cur_match is the head of the hash chain for the current
1274 * string (strstart) and its distance is <= MAX_DIST, and prev_length >= 1
1275 * OUT assertion: the match length is not greater than s->lookahead.
1277 local uInt
longest_match(
1281 unsigned chain_length
= s
->max_chain_length
;/* max hash chain length */
1282 register Bytef
*scan
= s
->window
+ s
->strstart
; /* current string */
1283 register Bytef
*match
; /* matched string */
1284 register int len
; /* length of current match */
1285 int best_len
= (int)s
->prev_length
; /* best match length so far */
1286 int nice_match
= s
->nice_match
; /* stop if match long enough */
1287 IPos limit
= s
->strstart
> (IPos
)MAX_DIST(s
) ?
1288 s
->strstart
- (IPos
)MAX_DIST(s
) : NIL
;
1289 /* Stop when cur_match becomes <= limit. To simplify the code,
1290 * we prevent matches with the string of window index 0.
1292 Posf
*prev
= s
->prev
;
1293 uInt wmask
= s
->w_mask
;
1296 /* Compare two bytes at a time. Note: this is not always beneficial.
1297 * Try with and without -DUNALIGNED_OK to check.
1299 register Bytef
*strend
= s
->window
+ s
->strstart
+ MAX_MATCH
- 1;
1300 register ush scan_start
= *(ushf
*)scan
;
1301 register ush scan_end
= *(ushf
*)(scan
+ best_len
- 1);
1303 register Bytef
*strend
= s
->window
+ s
->strstart
+ MAX_MATCH
;
1304 register Byte scan_end1
= scan
[best_len
- 1];
1305 register Byte scan_end
= scan
[best_len
];
1308 /* The code is optimized for HASH_BITS >= 8 and MAX_MATCH-2 multiple of 16.
1309 * It is easy to get rid of this optimization if necessary.
1311 Assert(s
->hash_bits
>= 8 && MAX_MATCH
== 258, "Code too clever");
1313 /* Do not waste too much time if we already have a good match: */
1314 if (s
->prev_length
>= s
->good_match
) {
1317 /* Do not look for matches beyond the end of the input. This is necessary
1318 * to make deflate deterministic.
1320 if ((uInt
)nice_match
> s
->lookahead
) nice_match
= (int)s
->lookahead
;
1322 Assert((ulg
)s
->strstart
<= s
->window_size
- MIN_LOOKAHEAD
,
1326 Assert(cur_match
< s
->strstart
, "no future");
1327 match
= s
->window
+ cur_match
;
1329 /* Skip to next match if the match length cannot increase
1330 * or if the match length is less than 2. Note that the checks below
1331 * for insufficient lookahead only occur occasionally for performance
1332 * reasons. Therefore uninitialized memory will be accessed, and
1333 * conditional jumps will be made that depend on those values.
1334 * However the length of the match is limited to the lookahead, so
1335 * the output of deflate is not affected by the uninitialized values.
1337 #if (defined(UNALIGNED_OK) && MAX_MATCH == 258)
1338 /* This code assumes sizeof(unsigned short) == 2. Do not use
1339 * UNALIGNED_OK if your compiler uses a different size.
1341 if (*(ushf
*)(match
+ best_len
- 1) != scan_end
||
1342 *(ushf
*)match
!= scan_start
) continue;
1344 /* It is not necessary to compare scan[2] and match[2] since they are
1345 * always equal when the other bytes match, given that the hash keys
1346 * are equal and that HASH_BITS >= 8. Compare 2 bytes at a time at
1347 * strstart + 3, + 5, up to strstart + 257. We check for insufficient
1348 * lookahead only every 4th comparison; the 128th check will be made
1349 * at strstart + 257. If MAX_MATCH-2 is not a multiple of 8, it is
1350 * necessary to put more guard bytes at the end of the window, or
1351 * to check more often for insufficient lookahead.
1353 Assert(scan
[2] == match
[2], "scan[2]?");
1356 } while (*(ushf
*)(scan
+= 2) == *(ushf
*)(match
+= 2) &&
1357 *(ushf
*)(scan
+= 2) == *(ushf
*)(match
+= 2) &&
1358 *(ushf
*)(scan
+= 2) == *(ushf
*)(match
+= 2) &&
1359 *(ushf
*)(scan
+= 2) == *(ushf
*)(match
+= 2) &&
1361 /* The funny "do {}" generates better code on most compilers */
1363 /* Here, scan <= window + strstart + 257 */
1364 Assert(scan
<= s
->window
+ (unsigned)(s
->window_size
- 1),
1366 if (*scan
== *match
) scan
++;
1368 len
= (MAX_MATCH
- 1) - (int)(strend
- scan
);
1369 scan
= strend
- (MAX_MATCH
-1);
1371 #else /* UNALIGNED_OK */
1373 if (match
[best_len
] != scan_end
||
1374 match
[best_len
- 1] != scan_end1
||
1376 *++match
!= scan
[1]) continue;
1378 /* The check at best_len - 1 can be removed because it will be made
1379 * again later. (This heuristic is not always a win.)
1380 * It is not necessary to compare scan[2] and match[2] since they
1381 * are always equal when the other bytes match, given that
1382 * the hash keys are equal and that HASH_BITS >= 8.
1385 Assert(*scan
== *match
, "match[2]?");
1387 /* We check for insufficient lookahead only every 8th comparison;
1388 * the 256th check will be made at strstart + 258.
1391 } while (*++scan
== *++match
&& *++scan
== *++match
&&
1392 *++scan
== *++match
&& *++scan
== *++match
&&
1393 *++scan
== *++match
&& *++scan
== *++match
&&
1394 *++scan
== *++match
&& *++scan
== *++match
&&
1397 Assert(scan
<= s
->window
+ (unsigned)(s
->window_size
- 1),
1400 len
= MAX_MATCH
- (int)(strend
- scan
);
1401 scan
= strend
- MAX_MATCH
;
1403 #endif /* UNALIGNED_OK */
1405 if (len
> best_len
) {
1406 s
->match_start
= cur_match
;
1408 if (len
>= nice_match
) break;
1410 scan_end
= *(ushf
*)(scan
+ best_len
- 1);
1412 scan_end1
= scan
[best_len
- 1];
1413 scan_end
= scan
[best_len
];
1416 } while ((cur_match
= prev
[cur_match
& wmask
]) > limit
1417 && --chain_length
!= 0);
1419 if ((uInt
)best_len
<= s
->lookahead
) return (uInt
)best_len
;
1420 return s
->lookahead
;
1425 /* ---------------------------------------------------------------------------
1426 * Optimized version for FASTEST only
1428 local uInt
longest_match(
1432 register Bytef
*scan
= s
->window
+ s
->strstart
; /* current string */
1433 register Bytef
*match
; /* matched string */
1434 register int len
; /* length of current match */
1435 register Bytef
*strend
= s
->window
+ s
->strstart
+ MAX_MATCH
;
1437 /* The code is optimized for HASH_BITS >= 8 and MAX_MATCH-2 multiple of 16.
1438 * It is easy to get rid of this optimization if necessary.
1440 Assert(s
->hash_bits
>= 8 && MAX_MATCH
== 258, "Code too clever");
1442 Assert((ulg
)s
->strstart
<= s
->window_size
- MIN_LOOKAHEAD
,
1445 Assert(cur_match
< s
->strstart
, "no future");
1447 match
= s
->window
+ cur_match
;
1449 /* Return failure if the match length is less than 2:
1451 if (match
[0] != scan
[0] || match
[1] != scan
[1]) return MIN_MATCH
-1;
1453 /* The check at best_len - 1 can be removed because it will be made
1454 * again later. (This heuristic is not always a win.)
1455 * It is not necessary to compare scan[2] and match[2] since they
1456 * are always equal when the other bytes match, given that
1457 * the hash keys are equal and that HASH_BITS >= 8.
1459 scan
+= 2, match
+= 2;
1460 Assert(*scan
== *match
, "match[2]?");
1462 /* We check for insufficient lookahead only every 8th comparison;
1463 * the 256th check will be made at strstart + 258.
1466 } while (*++scan
== *++match
&& *++scan
== *++match
&&
1467 *++scan
== *++match
&& *++scan
== *++match
&&
1468 *++scan
== *++match
&& *++scan
== *++match
&&
1469 *++scan
== *++match
&& *++scan
== *++match
&&
1472 Assert(scan
<= s
->window
+ (unsigned)(s
->window_size
- 1), "wild scan");
1474 len
= MAX_MATCH
- (int)(strend
- scan
);
1476 if (len
< MIN_MATCH
) return MIN_MATCH
- 1;
1478 s
->match_start
= cur_match
;
1479 return (uInt
)len
<= s
->lookahead
? (uInt
)len
: s
->lookahead
;
1482 #endif /* FASTEST */
1487 /* result of memcmp for equal strings */
1489 /* ===========================================================================
1490 * Check that the match at match_start is indeed a match.
1492 local
void check_match(
1498 /* check that the match is indeed a match */
1499 if (zmemcmp(s
->window
+ match
,
1500 s
->window
+ start
, length
) != EQUAL
) {
1501 fprintf(stderr
, " start %u, match %u, length %d\n",
1502 start
, match
, length
);
1504 fprintf(stderr
, "%c%c", s
->window
[match
++], s
->window
[start
++]);
1505 } while (--length
!= 0);
1506 z_error("invalid match");
1508 if (z_verbose
> 1) {
1509 fprintf(stderr
,"\\[%d,%d]", start
- match
, length
);
1510 do { putc(s
->window
[start
++], stderr
); } while (--length
!= 0);
1514 # define check_match(s, start, match, length)
1515 #endif /* ZLIB_DEBUG */
1517 /* ===========================================================================
1518 * Fill the window when the lookahead becomes insufficient.
1519 * Updates strstart and lookahead.
1521 * IN assertion: lookahead < MIN_LOOKAHEAD
1522 * OUT assertions: strstart <= window_size-MIN_LOOKAHEAD
1523 * At least one byte has been read, or avail_in == 0; reads are
1524 * performed for at least two bytes (required for the zip translate_eol
1525 * option -- not supported here).
1527 local
void fill_window(
1531 unsigned more
; /* Amount of free space at the end of the window. */
1532 uInt wsize
= s
->w_size
;
1534 Assert(s
->lookahead
< MIN_LOOKAHEAD
, "already enough lookahead");
1537 more
= (unsigned)(s
->window_size
-(ulg
)s
->lookahead
-(ulg
)s
->strstart
);
1539 /* Deal with !@#$% 64K limit: */
1540 if (sizeof(int) <= 2) {
1541 if (more
== 0 && s
->strstart
== 0 && s
->lookahead
== 0) {
1544 } else if (more
== (unsigned)(-1)) {
1545 /* Very unlikely, but possible on 16 bit machine if
1546 * strstart == 0 && lookahead == 1 (input done a byte at time)
1552 /* If the window is almost full and there is insufficient lookahead,
1553 * move the upper half to the lower one to make room in the upper half.
1555 if (s
->strstart
>= wsize
+ MAX_DIST(s
)) {
1557 zmemcpy(s
->window
, s
->window
+ wsize
, (unsigned)wsize
- more
);
1558 s
->match_start
-= wsize
;
1559 s
->strstart
-= wsize
; /* we now have strstart >= MAX_DIST */
1560 s
->block_start
-= (long) wsize
;
1561 if (s
->insert
> s
->strstart
)
1562 s
->insert
= s
->strstart
;
1566 if (s
->strm
->avail_in
== 0) break;
1568 /* If there was no sliding:
1569 * strstart <= WSIZE+MAX_DIST-1 && lookahead <= MIN_LOOKAHEAD - 1 &&
1570 * more == window_size - lookahead - strstart
1571 * => more >= window_size - (MIN_LOOKAHEAD-1 + WSIZE + MAX_DIST-1)
1572 * => more >= window_size - 2*WSIZE + 2
1573 * In the BIG_MEM or MMAP case (not yet supported),
1574 * window_size == input_size + MIN_LOOKAHEAD &&
1575 * strstart + s->lookahead <= input_size => more >= MIN_LOOKAHEAD.
1576 * Otherwise, window_size == 2*WSIZE so more >= 2.
1577 * If there was sliding, more >= WSIZE. So in all cases, more >= 2.
1579 Assert(more
>= 2, "more < 2");
1581 n
= read_buf(s
->strm
, s
->window
+ s
->strstart
+ s
->lookahead
, more
);
1584 /* Initialize the hash value now that we have some input: */
1585 if (s
->lookahead
+ s
->insert
>= MIN_MATCH
) {
1586 uInt str
= s
->strstart
- s
->insert
;
1587 s
->ins_h
= s
->window
[str
];
1588 UPDATE_HASH(s
, s
->ins_h
, s
->window
[str
+ 1]);
1590 Call
UPDATE_HASH() MIN_MATCH
-3 more times
1593 UPDATE_HASH(s
, s
->ins_h
, s
->window
[str
+ MIN_MATCH
-1]);
1595 s
->prev
[str
& s
->w_mask
] = s
->head
[s
->ins_h
];
1597 s
->head
[s
->ins_h
] = (Pos
)str
;
1600 if (s
->lookahead
+ s
->insert
< MIN_MATCH
)
1604 /* If the whole input has less than MIN_MATCH bytes, ins_h is garbage,
1605 * but this is not important since only literal bytes will be emitted.
1608 } while (s
->lookahead
< MIN_LOOKAHEAD
&& s
->strm
->avail_in
!= 0);
1610 /* If the WIN_INIT bytes after the end of the current data have never been
1611 * written, then zero those bytes in order to avoid memory check reports of
1612 * the use of uninitialized (or uninitialised as Julian writes) bytes by
1613 * the longest match routines. Update the high water mark for the next
1614 * time through here. WIN_INIT is set to MAX_MATCH since the longest match
1615 * routines allow scanning to strstart + MAX_MATCH, ignoring lookahead.
1617 if (s
->high_water
< s
->window_size
) {
1618 ulg curr
= s
->strstart
+ (ulg
)(s
->lookahead
);
1621 if (s
->high_water
< curr
) {
1622 /* Previous high water mark below current data -- zero WIN_INIT
1623 * bytes or up to end of window, whichever is less.
1625 init
= s
->window_size
- curr
;
1626 if (init
> WIN_INIT
)
1628 zmemzero(s
->window
+ curr
, (unsigned)init
);
1629 s
->high_water
= curr
+ init
;
1631 else if (s
->high_water
< (ulg
)curr
+ WIN_INIT
) {
1632 /* High water mark at or above current data, but below current data
1633 * plus WIN_INIT -- zero out to current data plus WIN_INIT, or up
1634 * to end of window, whichever is less.
1636 init
= (ulg
)curr
+ WIN_INIT
- s
->high_water
;
1637 if (init
> s
->window_size
- s
->high_water
)
1638 init
= s
->window_size
- s
->high_water
;
1639 zmemzero(s
->window
+ s
->high_water
, (unsigned)init
);
1640 s
->high_water
+= init
;
1644 Assert((ulg
)s
->strstart
<= s
->window_size
- MIN_LOOKAHEAD
,
1645 "not enough room for search");
1648 /* ===========================================================================
1649 * Flush the current block, with given end-of-file flag.
1650 * IN assertion: strstart is set to the end of the current match.
1652 #define FLUSH_BLOCK_ONLY(s, last) { \
1653 _tr_flush_block(s, (s->block_start >= 0L ? \
1654 (charf *)&s->window[(unsigned)s->block_start] : \
1656 (ulg)((long)s->strstart - s->block_start), \
1658 s->block_start = s->strstart; \
1659 flush_pending(s->strm); \
1660 Tracev((stderr,"[FLUSH]")); \
1663 /* Same but force premature exit if necessary. */
1664 #define FLUSH_BLOCK(s, last) { \
1665 FLUSH_BLOCK_ONLY(s, last); \
1666 if (s->strm->avail_out == 0) return (last) ? finish_started : need_more; \
1669 /* Maximum stored block length in deflate format (not including header). */
1670 #define MAX_STORED 65535
1672 /* Minimum of a and b. */
1673 #define MIN(a, b) ((a) > (b) ? (b) : (a))
1675 /* ===========================================================================
1676 * Copy without compression as much as possible from the input stream, return
1677 * the current block state.
1679 * In case deflateParams() is used to later switch to a non-zero compression
1680 * level, s->matches (otherwise unused when storing) keeps track of the number
1681 * of hash table slides to perform. If s->matches is 1, then one hash table
1682 * slide will be done when switching. If s->matches is 2, the maximum value
1683 * allowed here, then the hash table will be cleared, since two or more slides
1684 * is the same as a clear.
1686 * deflate_stored() is written to minimize the number of times an input byte is
1687 * copied. It is most efficient with large input and output buffers, which
1688 * maximizes the opportunities to have a single copy from next_in to next_out.
1690 local block_state
deflate_stored(
1694 /* Smallest worthy block size when not flushing or finishing. By default
1695 * this is 32K. This can be as small as 507 bytes for memLevel == 1. For
1696 * large input and output buffers, the stored block size will be larger.
1698 unsigned min_block
= MIN(s
->pending_buf_size
- 5, s
->w_size
);
1700 /* Copy as many min_block or larger stored blocks directly to next_out as
1701 * possible. If flushing, copy the remaining available input to next_out as
1702 * stored blocks, if there is enough space.
1704 unsigned len
, left
, have
, last
= 0;
1705 unsigned used
= s
->strm
->avail_in
;
1707 /* Set len to the maximum size block that we can copy directly with the
1708 * available input data and output space. Set left to how much of that
1709 * would be copied from what's left in the window.
1711 len
= MAX_STORED
; /* maximum deflate stored block length */
1712 have
= (s
->bi_valid
+ 42) >> 3; /* number of header bytes */
1713 if (s
->strm
->avail_out
< have
) /* need room for header */
1715 /* maximum stored block length that will fit in avail_out: */
1716 have
= s
->strm
->avail_out
- have
;
1717 left
= s
->strstart
- s
->block_start
; /* bytes left in window */
1718 if (len
> (ulg
)left
+ s
->strm
->avail_in
)
1719 len
= left
+ s
->strm
->avail_in
; /* limit len to the input */
1721 len
= have
; /* limit len to the output */
1723 /* If the stored block would be less than min_block in length, or if
1724 * unable to copy all of the available input when flushing, then try
1725 * copying to the window and the pending buffer instead. Also don't
1726 * write an empty block when flushing -- deflate() does that.
1728 if (len
< min_block
&& ((len
== 0 && flush
!= Z_FINISH
) ||
1729 flush
== Z_NO_FLUSH
||
1730 len
!= left
+ s
->strm
->avail_in
))
1733 /* Make a dummy stored block in pending to get the header bytes,
1734 * including any pending bits. This also updates the debugging counts.
1736 last
= flush
== Z_FINISH
&& len
== left
+ s
->strm
->avail_in
? 1 : 0;
1737 _tr_stored_block(s
, (char *)0, 0L, last
);
1739 /* Replace the lengths in the dummy stored block with len. */
1740 s
->pending_buf
[s
->pending
- 4] = len
;
1741 s
->pending_buf
[s
->pending
- 3] = len
>> 8;
1742 s
->pending_buf
[s
->pending
- 2] = ~len
;
1743 s
->pending_buf
[s
->pending
- 1] = ~len
>> 8;
1745 /* Write the stored block header bytes. */
1746 flush_pending(s
->strm
);
1749 /* Update debugging counts for the data about to be copied. */
1750 s
->compressed_len
+= len
<< 3;
1751 s
->bits_sent
+= len
<< 3;
1754 /* Copy uncompressed bytes from the window to next_out. */
1758 zmemcpy(s
->strm
->next_out
, s
->window
+ s
->block_start
, left
);
1759 s
->strm
->next_out
+= left
;
1760 s
->strm
->avail_out
-= left
;
1761 s
->strm
->total_out
+= left
;
1762 s
->block_start
+= left
;
1766 /* Copy uncompressed bytes directly from next_in to next_out, updating
1770 read_buf(s
->strm
, s
->strm
->next_out
, len
);
1771 s
->strm
->next_out
+= len
;
1772 s
->strm
->avail_out
-= len
;
1773 s
->strm
->total_out
+= len
;
1775 } while (last
== 0);
1777 /* Update the sliding window with the last s->w_size bytes of the copied
1778 * data, or append all of the copied data to the existing window if less
1779 * than s->w_size bytes were copied. Also update the number of bytes to
1780 * insert in the hash tables, in the event that deflateParams() switches to
1781 * a non-zero compression level.
1783 used
-= s
->strm
->avail_in
; /* number of input bytes directly copied */
1785 /* If any input was used, then no unused input remains in the window,
1786 * therefore s->block_start == s->strstart.
1788 if (used
>= s
->w_size
) { /* supplant the previous history */
1789 s
->matches
= 2; /* clear hash */
1790 zmemcpy(s
->window
, s
->strm
->next_in
- s
->w_size
, s
->w_size
);
1791 s
->strstart
= s
->w_size
;
1792 s
->insert
= s
->strstart
;
1795 if (s
->window_size
- s
->strstart
<= used
) {
1796 /* Slide the window down. */
1797 s
->strstart
-= s
->w_size
;
1798 zmemcpy(s
->window
, s
->window
+ s
->w_size
, s
->strstart
);
1800 s
->matches
++; /* add a pending slide_hash() */
1801 if (s
->insert
> s
->strstart
)
1802 s
->insert
= s
->strstart
;
1804 zmemcpy(s
->window
+ s
->strstart
, s
->strm
->next_in
- used
, used
);
1805 s
->strstart
+= used
;
1806 s
->insert
+= MIN(used
, s
->w_size
- s
->insert
);
1808 s
->block_start
= s
->strstart
;
1810 if (s
->high_water
< s
->strstart
)
1811 s
->high_water
= s
->strstart
;
1813 /* If the last block was written to next_out, then done. */
1817 /* If flushing and all input has been consumed, then done. */
1818 if (flush
!= Z_NO_FLUSH
&& flush
!= Z_FINISH
&&
1819 s
->strm
->avail_in
== 0 && (long)s
->strstart
== s
->block_start
)
1822 /* Fill the window with any remaining input. */
1823 have
= s
->window_size
- s
->strstart
;
1824 if (s
->strm
->avail_in
> have
&& s
->block_start
>= (long)s
->w_size
) {
1825 /* Slide the window down. */
1826 s
->block_start
-= s
->w_size
;
1827 s
->strstart
-= s
->w_size
;
1828 zmemcpy(s
->window
, s
->window
+ s
->w_size
, s
->strstart
);
1830 s
->matches
++; /* add a pending slide_hash() */
1831 have
+= s
->w_size
; /* more space now */
1832 if (s
->insert
> s
->strstart
)
1833 s
->insert
= s
->strstart
;
1835 if (have
> s
->strm
->avail_in
)
1836 have
= s
->strm
->avail_in
;
1838 read_buf(s
->strm
, s
->window
+ s
->strstart
, have
);
1839 s
->strstart
+= have
;
1840 s
->insert
+= MIN(have
, s
->w_size
- s
->insert
);
1842 if (s
->high_water
< s
->strstart
)
1843 s
->high_water
= s
->strstart
;
1845 /* There was not enough avail_out to write a complete worthy or flushed
1846 * stored block to next_out. Write a stored block to pending instead, if we
1847 * have enough input for a worthy block, or if flushing and there is enough
1848 * room for the remaining input as a stored block in the pending buffer.
1850 have
= (s
->bi_valid
+ 42) >> 3; /* number of header bytes */
1851 /* maximum stored block length that will fit in pending: */
1852 have
= MIN(s
->pending_buf_size
- have
, MAX_STORED
);
1853 min_block
= MIN(have
, s
->w_size
);
1854 left
= s
->strstart
- s
->block_start
;
1855 if (left
>= min_block
||
1856 ((left
|| flush
== Z_FINISH
) && flush
!= Z_NO_FLUSH
&&
1857 s
->strm
->avail_in
== 0 && left
<= have
)) {
1858 len
= MIN(left
, have
);
1859 last
= flush
== Z_FINISH
&& s
->strm
->avail_in
== 0 &&
1860 len
== left
? 1 : 0;
1861 _tr_stored_block(s
, (charf
*)s
->window
+ s
->block_start
, len
, last
);
1862 s
->block_start
+= len
;
1863 flush_pending(s
->strm
);
1866 /* We've done all we can with the available input and output. */
1867 return last
? finish_started
: need_more
;
1870 /* ===========================================================================
1871 * Compress as much as possible from the input stream, return the current
1873 * This function does not perform lazy evaluation of matches and inserts
1874 * new strings in the dictionary only for unmatched strings or for short
1875 * matches. It is used only for the fast compression options.
1877 local block_state
deflate_fast(
1881 IPos hash_head
; /* head of the hash chain */
1882 int bflush
; /* set if current block must be flushed */
1885 /* Make sure that we always have enough lookahead, except
1886 * at the end of the input file. We need MAX_MATCH bytes
1887 * for the next match, plus MIN_MATCH bytes to insert the
1888 * string following the next match.
1890 if (s
->lookahead
< MIN_LOOKAHEAD
) {
1892 if (s
->lookahead
< MIN_LOOKAHEAD
&& flush
== Z_NO_FLUSH
) {
1895 if (s
->lookahead
== 0) break; /* flush the current block */
1898 /* Insert the string window[strstart .. strstart + 2] in the
1899 * dictionary, and set hash_head to the head of the hash chain:
1902 if (s
->lookahead
>= MIN_MATCH
) {
1903 INSERT_STRING(s
, s
->strstart
, hash_head
);
1906 /* Find the longest match, discarding those <= prev_length.
1907 * At this point we have always match_length < MIN_MATCH
1909 if (hash_head
!= NIL
&& s
->strstart
- hash_head
<= MAX_DIST(s
)) {
1910 /* To simplify the code, we prevent matches with the string
1911 * of window index 0 (in particular we have to avoid a match
1912 * of the string with itself at the start of the input file).
1914 s
->match_length
= longest_match (s
, hash_head
);
1915 /* longest_match() sets match_start */
1917 if (s
->match_length
>= MIN_MATCH
) {
1918 check_match(s
, s
->strstart
, s
->match_start
, s
->match_length
);
1920 _tr_tally_dist(s
, s
->strstart
- s
->match_start
,
1921 s
->match_length
- MIN_MATCH
, bflush
);
1923 s
->lookahead
-= s
->match_length
;
1925 /* Insert new strings in the hash table only if the match length
1926 * is not too large. This saves time but degrades compression.
1929 if (s
->match_length
<= s
->max_insert_length
&&
1930 s
->lookahead
>= MIN_MATCH
) {
1931 s
->match_length
--; /* string at strstart already in table */
1934 INSERT_STRING(s
, s
->strstart
, hash_head
);
1935 /* strstart never exceeds WSIZE-MAX_MATCH, so there are
1936 * always MIN_MATCH bytes ahead.
1938 } while (--s
->match_length
!= 0);
1943 s
->strstart
+= s
->match_length
;
1944 s
->match_length
= 0;
1945 s
->ins_h
= s
->window
[s
->strstart
];
1946 UPDATE_HASH(s
, s
->ins_h
, s
->window
[s
->strstart
+ 1]);
1948 Call
UPDATE_HASH() MIN_MATCH
-3 more times
1950 /* If lookahead < MIN_MATCH, ins_h is garbage, but it does not
1951 * matter since it will be recomputed at next deflate call.
1955 /* No match, output a literal byte */
1956 Tracevv((stderr
,"%c", s
->window
[s
->strstart
]));
1957 _tr_tally_lit(s
, s
->window
[s
->strstart
], bflush
);
1961 if (bflush
) FLUSH_BLOCK(s
, 0);
1963 s
->insert
= s
->strstart
< MIN_MATCH
-1 ? s
->strstart
: MIN_MATCH
-1;
1964 if (flush
== Z_FINISH
) {
1974 /* ===========================================================================
1975 * Same as above, but achieves better compression. We use a lazy
1976 * evaluation for matches: a match is finally adopted only if there is
1977 * no better match at the next window position.
1979 local block_state
deflate_slow(
1983 IPos hash_head
; /* head of hash chain */
1984 int bflush
; /* set if current block must be flushed */
1986 /* Process the input block. */
1988 /* Make sure that we always have enough lookahead, except
1989 * at the end of the input file. We need MAX_MATCH bytes
1990 * for the next match, plus MIN_MATCH bytes to insert the
1991 * string following the next match.
1993 if (s
->lookahead
< MIN_LOOKAHEAD
) {
1995 if (s
->lookahead
< MIN_LOOKAHEAD
&& flush
== Z_NO_FLUSH
) {
1998 if (s
->lookahead
== 0) break; /* flush the current block */
2001 /* Insert the string window[strstart .. strstart + 2] in the
2002 * dictionary, and set hash_head to the head of the hash chain:
2005 if (s
->lookahead
>= MIN_MATCH
) {
2006 INSERT_STRING(s
, s
->strstart
, hash_head
);
2009 /* Find the longest match, discarding those <= prev_length.
2011 s
->prev_length
= s
->match_length
, s
->prev_match
= s
->match_start
;
2012 s
->match_length
= MIN_MATCH
-1;
2014 if (hash_head
!= NIL
&& s
->prev_length
< s
->max_lazy_match
&&
2015 s
->strstart
- hash_head
<= MAX_DIST(s
)) {
2016 /* To simplify the code, we prevent matches with the string
2017 * of window index 0 (in particular we have to avoid a match
2018 * of the string with itself at the start of the input file).
2020 s
->match_length
= longest_match (s
, hash_head
);
2021 /* longest_match() sets match_start */
2023 if (s
->match_length
<= 5 && (s
->strategy
== Z_FILTERED
2024 #if TOO_FAR <= 32767
2025 || (s
->match_length
== MIN_MATCH
&&
2026 s
->strstart
- s
->match_start
> TOO_FAR
)
2030 /* If prev_match is also MIN_MATCH, match_start is garbage
2031 * but we will ignore the current match anyway.
2033 s
->match_length
= MIN_MATCH
-1;
2036 /* If there was a match at the previous step and the current
2037 * match is not better, output the previous match:
2039 if (s
->prev_length
>= MIN_MATCH
&& s
->match_length
<= s
->prev_length
) {
2040 uInt max_insert
= s
->strstart
+ s
->lookahead
- MIN_MATCH
;
2041 /* Do not insert strings in hash table beyond this. */
2043 check_match(s
, s
->strstart
- 1, s
->prev_match
, s
->prev_length
);
2045 _tr_tally_dist(s
, s
->strstart
- 1 - s
->prev_match
,
2046 s
->prev_length
- MIN_MATCH
, bflush
);
2048 /* Insert in hash table all strings up to the end of the match.
2049 * strstart - 1 and strstart are already inserted. If there is not
2050 * enough lookahead, the last two strings are not inserted in
2053 s
->lookahead
-= s
->prev_length
- 1;
2054 s
->prev_length
-= 2;
2056 if (++s
->strstart
<= max_insert
) {
2057 INSERT_STRING(s
, s
->strstart
, hash_head
);
2059 } while (--s
->prev_length
!= 0);
2060 s
->match_available
= 0;
2061 s
->match_length
= MIN_MATCH
-1;
2064 if (bflush
) FLUSH_BLOCK(s
, 0);
2066 } else if (s
->match_available
) {
2067 /* If there was no match at the previous position, output a
2068 * single literal. If there was a match but the current match
2069 * is longer, truncate the previous match to a single literal.
2071 Tracevv((stderr
,"%c", s
->window
[s
->strstart
- 1]));
2072 _tr_tally_lit(s
, s
->window
[s
->strstart
- 1], bflush
);
2074 FLUSH_BLOCK_ONLY(s
, 0);
2078 if (s
->strm
->avail_out
== 0) return need_more
;
2080 /* There is no previous match to compare with, wait for
2081 * the next step to decide.
2083 s
->match_available
= 1;
2088 Assert (flush
!= Z_NO_FLUSH
, "no flush?");
2089 if (s
->match_available
) {
2090 Tracevv((stderr
,"%c", s
->window
[s
->strstart
- 1]));
2091 _tr_tally_lit(s
, s
->window
[s
->strstart
- 1], bflush
);
2092 s
->match_available
= 0;
2094 s
->insert
= s
->strstart
< MIN_MATCH
-1 ? s
->strstart
: MIN_MATCH
-1;
2095 if (flush
== Z_FINISH
) {
2103 #endif /* FASTEST */
2105 /* ===========================================================================
2106 * For Z_RLE, simply look for runs of bytes, generate matches only of distance
2107 * one. Do not maintain a hash table. (It will be regenerated if this run of
2108 * deflate switches away from Z_RLE.)
2110 local block_state
deflate_rle(
2114 int bflush
; /* set if current block must be flushed */
2115 uInt prev
; /* byte at distance one to match */
2116 Bytef
*scan
, *strend
; /* scan goes up to strend for length of run */
2119 /* Make sure that we always have enough lookahead, except
2120 * at the end of the input file. We need MAX_MATCH bytes
2121 * for the longest run, plus one for the unrolled loop.
2123 if (s
->lookahead
<= MAX_MATCH
) {
2125 if (s
->lookahead
<= MAX_MATCH
&& flush
== Z_NO_FLUSH
) {
2128 if (s
->lookahead
== 0) break; /* flush the current block */
2131 /* See how many times the previous byte repeats */
2132 s
->match_length
= 0;
2133 if (s
->lookahead
>= MIN_MATCH
&& s
->strstart
> 0) {
2134 scan
= s
->window
+ s
->strstart
- 1;
2136 if (prev
== *++scan
&& prev
== *++scan
&& prev
== *++scan
) {
2137 strend
= s
->window
+ s
->strstart
+ MAX_MATCH
;
2139 } while (prev
== *++scan
&& prev
== *++scan
&&
2140 prev
== *++scan
&& prev
== *++scan
&&
2141 prev
== *++scan
&& prev
== *++scan
&&
2142 prev
== *++scan
&& prev
== *++scan
&&
2144 s
->match_length
= MAX_MATCH
- (uInt
)(strend
- scan
);
2145 if (s
->match_length
> s
->lookahead
)
2146 s
->match_length
= s
->lookahead
;
2148 Assert(scan
<= s
->window
+ (uInt
)(s
->window_size
- 1),
2152 /* Emit match if have run of MIN_MATCH or longer, else emit literal */
2153 if (s
->match_length
>= MIN_MATCH
) {
2154 check_match(s
, s
->strstart
, s
->strstart
- 1, s
->match_length
);
2156 _tr_tally_dist(s
, 1, s
->match_length
- MIN_MATCH
, bflush
);
2158 s
->lookahead
-= s
->match_length
;
2159 s
->strstart
+= s
->match_length
;
2160 s
->match_length
= 0;
2162 /* No match, output a literal byte */
2163 Tracevv((stderr
,"%c", s
->window
[s
->strstart
]));
2164 _tr_tally_lit(s
, s
->window
[s
->strstart
], bflush
);
2168 if (bflush
) FLUSH_BLOCK(s
, 0);
2171 if (flush
== Z_FINISH
) {
2180 /* ===========================================================================
2181 * For Z_HUFFMAN_ONLY, do not look for matches. Do not maintain a hash table.
2182 * (It will be regenerated if this run of deflate switches away from Huffman.)
2184 local block_state
deflate_huff(
2188 int bflush
; /* set if current block must be flushed */
2191 /* Make sure that we have a literal to write. */
2192 if (s
->lookahead
== 0) {
2194 if (s
->lookahead
== 0) {
2195 if (flush
== Z_NO_FLUSH
)
2197 break; /* flush the current block */
2201 /* Output a literal byte */
2202 s
->match_length
= 0;
2203 Tracevv((stderr
,"%c", s
->window
[s
->strstart
]));
2204 _tr_tally_lit(s
, s
->window
[s
->strstart
], bflush
);
2207 if (bflush
) FLUSH_BLOCK(s
, 0);
2210 if (flush
== Z_FINISH
) {