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.12 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
));
91 # pragma message("Assembler code may have bugs -- use at your own risk")
92 void match_init
OF((void)); /* asm code initialization */
93 uInt longest_match
OF((deflate_state
*s
, IPos cur_match
));
95 local uInt longest_match
OF((deflate_state
*s
, IPos cur_match
));
99 local
void check_match
OF((deflate_state
*s
, IPos start
, IPos match
,
103 /* ===========================================================================
108 /* Tail of hash chains */
111 # define TOO_FAR 4096
113 /* Matches of length 3 are discarded if their distance exceeds TOO_FAR */
115 /* Values for max_lazy_match, good_match and max_chain_length, depending on
116 * the desired pack level (0..9). The values given below have been tuned to
117 * exclude worst case performance for pathological files. Better values may be
118 * found for specific files.
120 typedef struct config_s
{
121 ush good_length
; /* reduce lazy search above this match length */
122 ush max_lazy
; /* do not perform lazy search above this match length */
123 ush nice_length
; /* quit search above this match length */
129 local
const config configuration_table
[2] = {
130 /* good lazy nice chain */
131 /* 0 */ {0, 0, 0, 0, deflate_stored
}, /* store only */
132 /* 1 */ {4, 4, 8, 4, deflate_fast
}}; /* max speed, no lazy matches */
134 local
const config configuration_table
[10] = {
135 /* good lazy nice chain */
136 /* 0 */ {0, 0, 0, 0, deflate_stored
}, /* store only */
137 /* 1 */ {4, 4, 8, 4, deflate_fast
}, /* max speed, no lazy matches */
138 /* 2 */ {4, 5, 16, 8, deflate_fast
},
139 /* 3 */ {4, 6, 32, 32, deflate_fast
},
141 /* 4 */ {4, 4, 16, 16, deflate_slow
}, /* lazy matches */
142 /* 5 */ {8, 16, 32, 32, deflate_slow
},
143 /* 6 */ {8, 16, 128, 128, deflate_slow
},
144 /* 7 */ {8, 32, 128, 256, deflate_slow
},
145 /* 8 */ {32, 128, 258, 1024, deflate_slow
},
146 /* 9 */ {32, 258, 258, 4096, deflate_slow
}}; /* max compression */
149 /* Note: the deflate() code requires max_lazy >= MIN_MATCH and max_chain >= 4
150 * For deflate_fast() (levels <= 3) good is ignored and lazy has a different
154 /* rank Z_BLOCK between Z_NO_FLUSH and Z_PARTIAL_FLUSH */
155 #define RANK(f) (((f) * 2) - ((f) > 4 ? 9 : 0))
157 /* ===========================================================================
158 * Update a hash value with the given input byte
159 * IN assertion: all calls to UPDATE_HASH are made with consecutive input
160 * characters, so that a running hash key can be computed from the previous
161 * key instead of complete recalculation each time.
163 #define UPDATE_HASH(s,h,c) (h = (((h)<<s->hash_shift) ^ (c)) & s->hash_mask)
166 /* ===========================================================================
167 * Insert string str in the dictionary and set match_head to the previous head
168 * of the hash chain (the most recent string with same hash key). Return
169 * the previous length of the hash chain.
170 * If this file is compiled with -DFASTEST, the compression level is forced
171 * to 1, and no hash chains are maintained.
172 * IN assertion: all calls to INSERT_STRING are made with consecutive input
173 * characters and the first MIN_MATCH bytes of str are valid (except for
174 * the last MIN_MATCH-1 bytes of the input file).
177 #define INSERT_STRING(s, str, match_head) \
178 (UPDATE_HASH(s, s->ins_h, s->window[(str) + (MIN_MATCH-1)]), \
179 match_head = s->head[s->ins_h], \
180 s->head[s->ins_h] = (Pos)(str))
182 #define INSERT_STRING(s, str, match_head) \
183 (UPDATE_HASH(s, s->ins_h, s->window[(str) + (MIN_MATCH-1)]), \
184 match_head = s->prev[(str) & s->w_mask] = s->head[s->ins_h], \
185 s->head[s->ins_h] = (Pos)(str))
188 /* ===========================================================================
189 * Initialize the hash table (avoiding 64K overflow for 16 bit systems).
190 * prev[] will be initialized on the fly.
192 #define CLEAR_HASH(s) \
194 s->head[s->hash_size-1] = NIL; \
195 zmemzero((Bytef *)s->head, \
196 (unsigned)(s->hash_size-1)*sizeof(*s->head)); \
199 /* ===========================================================================
200 * Slide the hash table when sliding the window down (could be avoided with 32
201 * bit values at the expense of memory usage). We slide even when level == 0 to
202 * keep the hash table consistent if we switch back to level > 0 later.
204 local
void slide_hash(s
)
209 uInt wsize
= s
->w_size
;
215 *p
= (Pos
)(m
>= wsize
? m
- wsize
: NIL
);
222 *p
= (Pos
)(m
>= wsize
? m
- wsize
: NIL
);
223 /* If n is not on any hash chain, prev[n] is garbage but
224 * its value will never be used.
230 /* ========================================================================= */
231 int ZEXPORT
deflateInit_(strm
, level
, version
, stream_size
)
237 return deflateInit2_(strm
, level
, Z_DEFLATED
, MAX_WBITS
, DEF_MEM_LEVEL
,
238 Z_DEFAULT_STRATEGY
, version
, stream_size
);
239 /* To do: ignore strm->next_in if we use it as window */
242 /* ========================================================================= */
243 int ZEXPORT
deflateInit2_(strm
, level
, method
, windowBits
, memLevel
, strategy
,
244 version
, stream_size
)
256 static const char my_version
[] = ZLIB_VERSION
;
258 if (version
== Z_NULL
|| version
[0] != my_version
[0] ||
259 stream_size
!= sizeof(z_stream
)) {
260 return Z_VERSION_ERROR
;
262 if (strm
== Z_NULL
) return Z_STREAM_ERROR
;
265 if (strm
->zalloc
== (alloc_func
)0) {
267 return Z_STREAM_ERROR
;
269 strm
->zalloc
= zcalloc
;
270 strm
->opaque
= (voidpf
)0;
273 if (strm
->zfree
== (free_func
)0)
275 return Z_STREAM_ERROR
;
277 strm
->zfree
= zcfree
;
281 if (level
!= 0) level
= 1;
283 if (level
== Z_DEFAULT_COMPRESSION
) level
= 6;
286 if (windowBits
< 0) { /* suppress zlib wrapper */
288 windowBits
= -windowBits
;
291 else if (windowBits
> 15) {
292 wrap
= 2; /* write gzip wrapper instead */
296 if (memLevel
< 1 || memLevel
> MAX_MEM_LEVEL
|| method
!= Z_DEFLATED
||
297 windowBits
< 8 || windowBits
> 15 || level
< 0 || level
> 9 ||
298 strategy
< 0 || strategy
> Z_FIXED
|| (windowBits
== 8 && wrap
!= 1)) {
299 return Z_STREAM_ERROR
;
301 if (windowBits
== 8) windowBits
= 9; /* until 256-byte window bug fixed */
302 s
= (deflate_state
*) ZALLOC(strm
, 1, sizeof(deflate_state
));
303 if (s
== Z_NULL
) return Z_MEM_ERROR
;
304 strm
->state
= (struct internal_state FAR
*)s
;
306 s
->status
= INIT_STATE
; /* to pass state test in deflateReset() */
310 s
->w_bits
= (uInt
)windowBits
;
311 s
->w_size
= 1 << s
->w_bits
;
312 s
->w_mask
= s
->w_size
- 1;
314 s
->hash_bits
= (uInt
)memLevel
+ 7;
315 s
->hash_size
= 1 << s
->hash_bits
;
316 s
->hash_mask
= s
->hash_size
- 1;
317 s
->hash_shift
= ((s
->hash_bits
+MIN_MATCH
-1)/MIN_MATCH
);
319 s
->window
= (Bytef
*) ZALLOC(strm
, s
->w_size
, 2*sizeof(Byte
));
320 s
->prev
= (Posf
*) ZALLOC(strm
, s
->w_size
, sizeof(Pos
));
321 s
->head
= (Posf
*) ZALLOC(strm
, s
->hash_size
, sizeof(Pos
));
323 s
->high_water
= 0; /* nothing written to s->window yet */
325 s
->lit_bufsize
= 1 << (memLevel
+ 6); /* 16K elements by default */
327 /* We overlay pending_buf and sym_buf. This works since the average size
328 * for length/distance pairs over any compressed block is assured to be 31
331 * Analysis: The longest fixed codes are a length code of 8 bits plus 5
332 * extra bits, for lengths 131 to 257. The longest fixed distance codes are
333 * 5 bits plus 13 extra bits, for distances 16385 to 32768. The longest
334 * possible fixed-codes length/distance pair is then 31 bits total.
336 * sym_buf starts one-fourth of the way into pending_buf. So there are
337 * three bytes in sym_buf for every four bytes in pending_buf. Each symbol
338 * in sym_buf is three bytes -- two for the distance and one for the
339 * literal/length. As each symbol is consumed, the pointer to the next
340 * sym_buf value to read moves forward three bytes. From that symbol, up to
341 * 31 bits are written to pending_buf. The closest the written pending_buf
342 * bits gets to the next sym_buf symbol to read is just before the last
343 * code is written. At that time, 31*(n-2) bits have been written, just
344 * after 24*(n-2) bits have been consumed from sym_buf. sym_buf starts at
345 * 8*n bits into pending_buf. (Note that the symbol buffer fills when n-1
346 * symbols are written.) The closest the writing gets to what is unread is
347 * then n+14 bits. Here n is lit_bufsize, which is 16384 by default, and
348 * can range from 128 to 32768.
350 * Therefore, at a minimum, there are 142 bits of space between what is
351 * written and what is read in the overlain buffers, so the symbols cannot
352 * be overwritten by the compressed data. That space is actually 139 bits,
353 * due to the three-bit fixed-code block header.
355 * That covers the case where either Z_FIXED is specified, forcing fixed
356 * codes, or when the use of fixed codes is chosen, because that choice
357 * results in a smaller compressed block than dynamic codes. That latter
358 * condition then assures that the above analysis also covers all dynamic
359 * blocks. A dynamic-code block will only be chosen to be emitted if it has
360 * fewer bits than a fixed-code block would for the same set of symbols.
361 * Therefore its average symbol length is assured to be less than 31. So
362 * the compressed data for a dynamic block also cannot overwrite the
363 * symbols from which it is being constructed.
366 s
->pending_buf
= (uchf
*) ZALLOC(strm
, s
->lit_bufsize
, 4);
367 s
->pending_buf_size
= (ulg
)s
->lit_bufsize
* 4;
369 if (s
->window
== Z_NULL
|| s
->prev
== Z_NULL
|| s
->head
== Z_NULL
||
370 s
->pending_buf
== Z_NULL
) {
371 s
->status
= FINISH_STATE
;
372 strm
->msg
= ERR_MSG(Z_MEM_ERROR
);
376 s
->sym_buf
= s
->pending_buf
+ s
->lit_bufsize
;
377 s
->sym_end
= (s
->lit_bufsize
- 1) * 3;
378 /* We avoid equality with lit_bufsize*3 because of wraparound at 64K
379 * on 16 bit machines and because stored blocks are restricted to
384 s
->strategy
= strategy
;
385 s
->method
= (Byte
)method
;
387 return deflateReset(strm
);
390 /* =========================================================================
391 * Check for a valid deflate stream state. Return 0 if ok, 1 if not.
393 local
int deflateStateCheck (strm
)
397 if (strm
== Z_NULL
||
398 strm
->zalloc
== (alloc_func
)0 || strm
->zfree
== (free_func
)0)
401 if (s
== Z_NULL
|| s
->strm
!= strm
|| (s
->status
!= INIT_STATE
&&
403 s
->status
!= GZIP_STATE
&&
405 s
->status
!= EXTRA_STATE
&&
406 s
->status
!= NAME_STATE
&&
407 s
->status
!= COMMENT_STATE
&&
408 s
->status
!= HCRC_STATE
&&
409 s
->status
!= BUSY_STATE
&&
410 s
->status
!= FINISH_STATE
))
415 /* ========================================================================= */
416 int ZEXPORT
deflateSetDictionary (strm
, dictionary
, dictLength
)
418 const Bytef
*dictionary
;
425 z_const
unsigned char *next
;
427 if (deflateStateCheck(strm
) || dictionary
== Z_NULL
)
428 return Z_STREAM_ERROR
;
431 if (wrap
== 2 || (wrap
== 1 && s
->status
!= INIT_STATE
) || s
->lookahead
)
432 return Z_STREAM_ERROR
;
434 /* when using zlib wrappers, compute Adler-32 for provided dictionary */
436 strm
->adler
= adler32(strm
->adler
, dictionary
, dictLength
);
437 s
->wrap
= 0; /* avoid computing Adler-32 in read_buf */
439 /* if dictionary would fill window, just replace the history */
440 if (dictLength
>= s
->w_size
) {
441 if (wrap
== 0) { /* already empty otherwise */
447 dictionary
+= dictLength
- s
->w_size
; /* use the tail */
448 dictLength
= s
->w_size
;
451 /* insert dictionary into window and hash */
452 avail
= strm
->avail_in
;
453 next
= strm
->next_in
;
454 strm
->avail_in
= dictLength
;
455 strm
->next_in
= (z_const Bytef
*)dictionary
;
457 while (s
->lookahead
>= MIN_MATCH
) {
459 n
= s
->lookahead
- (MIN_MATCH
-1);
461 UPDATE_HASH(s
, s
->ins_h
, s
->window
[str
+ MIN_MATCH
-1]);
463 s
->prev
[str
& s
->w_mask
] = s
->head
[s
->ins_h
];
465 s
->head
[s
->ins_h
] = (Pos
)str
;
469 s
->lookahead
= MIN_MATCH
-1;
472 s
->strstart
+= s
->lookahead
;
473 s
->block_start
= (long)s
->strstart
;
474 s
->insert
= s
->lookahead
;
476 s
->match_length
= s
->prev_length
= MIN_MATCH
-1;
477 s
->match_available
= 0;
478 strm
->next_in
= next
;
479 strm
->avail_in
= avail
;
484 /* ========================================================================= */
485 int ZEXPORT
deflateGetDictionary (strm
, dictionary
, dictLength
)
493 if (deflateStateCheck(strm
))
494 return Z_STREAM_ERROR
;
496 len
= s
->strstart
+ s
->lookahead
;
499 if (dictionary
!= Z_NULL
&& len
)
500 zmemcpy(dictionary
, s
->window
+ s
->strstart
+ s
->lookahead
- len
, len
);
501 if (dictLength
!= Z_NULL
)
506 /* ========================================================================= */
507 int ZEXPORT
deflateResetKeep (strm
)
512 if (deflateStateCheck(strm
)) {
513 return Z_STREAM_ERROR
;
516 strm
->total_in
= strm
->total_out
= 0;
517 strm
->msg
= Z_NULL
; /* use zfree if we ever allocate msg dynamically */
518 strm
->data_type
= Z_UNKNOWN
;
520 s
= (deflate_state
*)strm
->state
;
522 s
->pending_out
= s
->pending_buf
;
525 s
->wrap
= -s
->wrap
; /* was made negative by deflate(..., Z_FINISH); */
529 s
->wrap
== 2 ? GZIP_STATE
:
534 s
->wrap
== 2 ? crc32(0L, Z_NULL
, 0) :
536 adler32(0L, Z_NULL
, 0);
544 /* ========================================================================= */
545 int ZEXPORT
deflateReset (strm
)
550 ret
= deflateResetKeep(strm
);
552 lm_init(strm
->state
);
556 /* ========================================================================= */
557 int ZEXPORT
deflateSetHeader (strm
, head
)
561 if (deflateStateCheck(strm
) || strm
->state
->wrap
!= 2)
562 return Z_STREAM_ERROR
;
563 strm
->state
->gzhead
= head
;
567 /* ========================================================================= */
568 int ZEXPORT
deflatePending (strm
, pending
, bits
)
573 if (deflateStateCheck(strm
)) return Z_STREAM_ERROR
;
574 if (pending
!= Z_NULL
)
575 *pending
= strm
->state
->pending
;
577 *bits
= strm
->state
->bi_valid
;
581 /* ========================================================================= */
582 int ZEXPORT
deflatePrime (strm
, bits
, value
)
590 if (deflateStateCheck(strm
)) return Z_STREAM_ERROR
;
592 if (bits
< 0 || bits
> 16 ||
593 s
->sym_buf
< s
->pending_out
+ ((Buf_size
+ 7) >> 3))
596 put
= Buf_size
- s
->bi_valid
;
599 s
->bi_buf
|= (ush
)((value
& ((1 << put
) - 1)) << s
->bi_valid
);
608 /* ========================================================================= */
609 int ZEXPORT
deflateParams(strm
, level
, strategy
)
617 if (deflateStateCheck(strm
)) return Z_STREAM_ERROR
;
621 if (level
!= 0) level
= 1;
623 if (level
== Z_DEFAULT_COMPRESSION
) level
= 6;
625 if (level
< 0 || level
> 9 || strategy
< 0 || strategy
> Z_FIXED
) {
626 return Z_STREAM_ERROR
;
628 func
= configuration_table
[s
->level
].func
;
630 if ((strategy
!= s
->strategy
|| func
!= configuration_table
[level
].func
) &&
631 s
->last_flush
!= -2) {
632 /* Flush the last buffer: */
633 int err
= deflate(strm
, Z_BLOCK
);
634 if (err
== Z_STREAM_ERROR
)
636 if (strm
->avail_in
|| (s
->strstart
- s
->block_start
) + s
->lookahead
)
639 if (s
->level
!= level
) {
640 if (s
->level
== 0 && s
->matches
!= 0) {
648 s
->max_lazy_match
= configuration_table
[level
].max_lazy
;
649 s
->good_match
= configuration_table
[level
].good_length
;
650 s
->nice_match
= configuration_table
[level
].nice_length
;
651 s
->max_chain_length
= configuration_table
[level
].max_chain
;
653 s
->strategy
= strategy
;
657 /* ========================================================================= */
658 int ZEXPORT
deflateTune(strm
, good_length
, max_lazy
, nice_length
, max_chain
)
667 if (deflateStateCheck(strm
)) return Z_STREAM_ERROR
;
669 s
->good_match
= (uInt
)good_length
;
670 s
->max_lazy_match
= (uInt
)max_lazy
;
671 s
->nice_match
= nice_length
;
672 s
->max_chain_length
= (uInt
)max_chain
;
676 /* =========================================================================
677 * For the default windowBits of 15 and memLevel of 8, this function returns
678 * a close to exact, as well as small, upper bound on the compressed size.
679 * They are coded as constants here for a reason--if the #define's are
680 * changed, then this function needs to be changed as well. The return
681 * value for 15 and 8 only works for those exact settings.
683 * For any setting other than those defaults for windowBits and memLevel,
684 * the value returned is a conservative worst case for the maximum expansion
685 * resulting from using fixed blocks instead of stored blocks, which deflate
686 * can emit on compressed data for some combinations of the parameters.
688 * This function could be more sophisticated to provide closer upper bounds for
689 * every combination of windowBits and memLevel. But even the conservative
690 * upper bound of about 14% expansion does not seem onerous for output buffer
693 uLong ZEXPORT
deflateBound(strm
, sourceLen
)
698 uLong complen
, wraplen
;
700 /* conservative upper bound for compressed data */
701 complen
= sourceLen
+
702 ((sourceLen
+ 7) >> 3) + ((sourceLen
+ 63) >> 6) + 5;
704 /* if can't get parameters, return conservative bound plus zlib wrapper */
705 if (deflateStateCheck(strm
))
708 /* compute wrapper length */
711 case 0: /* raw deflate */
714 case 1: /* zlib wrapper */
715 wraplen
= 6 + (s
->strstart
? 4 : 0);
718 case 2: /* gzip wrapper */
720 if (s
->gzhead
!= Z_NULL
) { /* user-supplied gzip header */
722 if (s
->gzhead
->extra
!= Z_NULL
)
723 wraplen
+= 2 + s
->gzhead
->extra_len
;
724 str
= s
->gzhead
->name
;
729 str
= s
->gzhead
->comment
;
739 default: /* for compiler happiness */
743 /* if not default parameters, return conservative bound */
744 if (s
->w_bits
!= 15 || s
->hash_bits
!= 8 + 7)
745 return complen
+ wraplen
;
747 /* default settings: return tight bound for that case */
748 return sourceLen
+ (sourceLen
>> 12) + (sourceLen
>> 14) +
749 (sourceLen
>> 25) + 13 - 6 + wraplen
;
752 /* =========================================================================
753 * Put a short in the pending buffer. The 16-bit value is put in MSB order.
754 * IN assertion: the stream state is correct and there is enough room in
757 local
void putShortMSB (s
, b
)
761 put_byte(s
, (Byte
)(b
>> 8));
762 put_byte(s
, (Byte
)(b
& 0xff));
765 /* =========================================================================
766 * Flush as much pending output as possible. All deflate() output, except for
767 * some deflate_stored() output, goes through this function so some
768 * applications may wish to modify it to avoid allocating a large
769 * strm->next_out buffer and copying into it. (See also read_buf()).
771 local
void flush_pending(strm
)
775 deflate_state
*s
= strm
->state
;
779 if (len
> strm
->avail_out
) len
= strm
->avail_out
;
780 if (len
== 0) return;
782 zmemcpy(strm
->next_out
, s
->pending_out
, len
);
783 strm
->next_out
+= len
;
784 s
->pending_out
+= len
;
785 strm
->total_out
+= len
;
786 strm
->avail_out
-= len
;
788 if (s
->pending
== 0) {
789 s
->pending_out
= s
->pending_buf
;
793 /* ===========================================================================
794 * Update the header CRC with the bytes s->pending_buf[beg..s->pending - 1].
796 #define HCRC_UPDATE(beg) \
798 if (s->gzhead->hcrc && s->pending > (beg)) \
799 strm->adler = crc32(strm->adler, s->pending_buf + (beg), \
800 s->pending - (beg)); \
803 /* ========================================================================= */
804 int ZEXPORT
deflate (strm
, flush
)
808 int old_flush
; /* value of flush param for previous deflate call */
811 if (deflateStateCheck(strm
) || flush
> Z_BLOCK
|| flush
< 0) {
812 return Z_STREAM_ERROR
;
816 if (strm
->next_out
== Z_NULL
||
817 (strm
->avail_in
!= 0 && strm
->next_in
== Z_NULL
) ||
818 (s
->status
== FINISH_STATE
&& flush
!= Z_FINISH
)) {
819 ERR_RETURN(strm
, Z_STREAM_ERROR
);
821 if (strm
->avail_out
== 0) ERR_RETURN(strm
, Z_BUF_ERROR
);
823 old_flush
= s
->last_flush
;
824 s
->last_flush
= flush
;
826 /* Flush as much pending output as possible */
827 if (s
->pending
!= 0) {
829 if (strm
->avail_out
== 0) {
830 /* Since avail_out is 0, deflate will be called again with
831 * more output space, but possibly with both pending and
832 * avail_in equal to zero. There won't be anything to do,
833 * but this is not an error situation so make sure we
834 * return OK instead of BUF_ERROR at next call of deflate:
840 /* Make sure there is something to do and avoid duplicate consecutive
841 * flushes. For repeated and useless calls with Z_FINISH, we keep
842 * returning Z_STREAM_END instead of Z_BUF_ERROR.
844 } else if (strm
->avail_in
== 0 && RANK(flush
) <= RANK(old_flush
) &&
846 ERR_RETURN(strm
, Z_BUF_ERROR
);
849 /* User must not provide more input after the first FINISH: */
850 if (s
->status
== FINISH_STATE
&& strm
->avail_in
!= 0) {
851 ERR_RETURN(strm
, Z_BUF_ERROR
);
854 /* Write the header */
855 if (s
->status
== INIT_STATE
&& s
->wrap
== 0)
856 s
->status
= BUSY_STATE
;
857 if (s
->status
== INIT_STATE
) {
859 uInt header
= (Z_DEFLATED
+ ((s
->w_bits
-8)<<4)) << 8;
862 if (s
->strategy
>= Z_HUFFMAN_ONLY
|| s
->level
< 2)
864 else if (s
->level
< 6)
866 else if (s
->level
== 6)
870 header
|= (level_flags
<< 6);
871 if (s
->strstart
!= 0) header
|= PRESET_DICT
;
872 header
+= 31 - (header
% 31);
874 putShortMSB(s
, header
);
876 /* Save the adler32 of the preset dictionary: */
877 if (s
->strstart
!= 0) {
878 putShortMSB(s
, (uInt
)(strm
->adler
>> 16));
879 putShortMSB(s
, (uInt
)(strm
->adler
& 0xffff));
881 strm
->adler
= adler32(0L, Z_NULL
, 0);
882 s
->status
= BUSY_STATE
;
884 /* Compression must start with an empty pending buffer */
886 if (s
->pending
!= 0) {
892 if (s
->status
== GZIP_STATE
) {
894 strm
->adler
= crc32(0L, Z_NULL
, 0);
898 if (s
->gzhead
== Z_NULL
) {
904 put_byte(s
, s
->level
== 9 ? 2 :
905 (s
->strategy
>= Z_HUFFMAN_ONLY
|| s
->level
< 2 ?
907 put_byte(s
, OS_CODE
);
908 s
->status
= BUSY_STATE
;
910 /* Compression must start with an empty pending buffer */
912 if (s
->pending
!= 0) {
918 put_byte(s
, (s
->gzhead
->text
? 1 : 0) +
919 (s
->gzhead
->hcrc
? 2 : 0) +
920 (s
->gzhead
->extra
== Z_NULL
? 0 : 4) +
921 (s
->gzhead
->name
== Z_NULL
? 0 : 8) +
922 (s
->gzhead
->comment
== Z_NULL
? 0 : 16)
924 put_byte(s
, (Byte
)(s
->gzhead
->time
& 0xff));
925 put_byte(s
, (Byte
)((s
->gzhead
->time
>> 8) & 0xff));
926 put_byte(s
, (Byte
)((s
->gzhead
->time
>> 16) & 0xff));
927 put_byte(s
, (Byte
)((s
->gzhead
->time
>> 24) & 0xff));
928 put_byte(s
, s
->level
== 9 ? 2 :
929 (s
->strategy
>= Z_HUFFMAN_ONLY
|| s
->level
< 2 ?
931 put_byte(s
, s
->gzhead
->os
& 0xff);
932 if (s
->gzhead
->extra
!= Z_NULL
) {
933 put_byte(s
, s
->gzhead
->extra_len
& 0xff);
934 put_byte(s
, (s
->gzhead
->extra_len
>> 8) & 0xff);
937 strm
->adler
= crc32(strm
->adler
, s
->pending_buf
,
940 s
->status
= EXTRA_STATE
;
943 if (s
->status
== EXTRA_STATE
) {
944 if (s
->gzhead
->extra
!= Z_NULL
) {
945 ulg beg
= s
->pending
; /* start of bytes to update crc */
946 uInt left
= (s
->gzhead
->extra_len
& 0xffff) - s
->gzindex
;
947 while (s
->pending
+ left
> s
->pending_buf_size
) {
948 uInt copy
= s
->pending_buf_size
- s
->pending
;
949 zmemcpy(s
->pending_buf
+ s
->pending
,
950 s
->gzhead
->extra
+ s
->gzindex
, copy
);
951 s
->pending
= s
->pending_buf_size
;
955 if (s
->pending
!= 0) {
962 zmemcpy(s
->pending_buf
+ s
->pending
,
963 s
->gzhead
->extra
+ s
->gzindex
, left
);
968 s
->status
= NAME_STATE
;
970 if (s
->status
== NAME_STATE
) {
971 if (s
->gzhead
->name
!= Z_NULL
) {
972 ulg beg
= s
->pending
; /* start of bytes to update crc */
975 if (s
->pending
== s
->pending_buf_size
) {
978 if (s
->pending
!= 0) {
984 val
= s
->gzhead
->name
[s
->gzindex
++];
990 s
->status
= COMMENT_STATE
;
992 if (s
->status
== COMMENT_STATE
) {
993 if (s
->gzhead
->comment
!= Z_NULL
) {
994 ulg beg
= s
->pending
; /* start of bytes to update crc */
997 if (s
->pending
== s
->pending_buf_size
) {
1000 if (s
->pending
!= 0) {
1006 val
= s
->gzhead
->comment
[s
->gzindex
++];
1011 s
->status
= HCRC_STATE
;
1013 if (s
->status
== HCRC_STATE
) {
1014 if (s
->gzhead
->hcrc
) {
1015 if (s
->pending
+ 2 > s
->pending_buf_size
) {
1016 flush_pending(strm
);
1017 if (s
->pending
!= 0) {
1022 put_byte(s
, (Byte
)(strm
->adler
& 0xff));
1023 put_byte(s
, (Byte
)((strm
->adler
>> 8) & 0xff));
1024 strm
->adler
= crc32(0L, Z_NULL
, 0);
1026 s
->status
= BUSY_STATE
;
1028 /* Compression must start with an empty pending buffer */
1029 flush_pending(strm
);
1030 if (s
->pending
!= 0) {
1037 /* Start a new block or continue the current one.
1039 if (strm
->avail_in
!= 0 || s
->lookahead
!= 0 ||
1040 (flush
!= Z_NO_FLUSH
&& s
->status
!= FINISH_STATE
)) {
1043 bstate
= s
->level
== 0 ? deflate_stored(s
, flush
) :
1044 s
->strategy
== Z_HUFFMAN_ONLY
? deflate_huff(s
, flush
) :
1045 s
->strategy
== Z_RLE
? deflate_rle(s
, flush
) :
1046 (*(configuration_table
[s
->level
].func
))(s
, flush
);
1048 if (bstate
== finish_started
|| bstate
== finish_done
) {
1049 s
->status
= FINISH_STATE
;
1051 if (bstate
== need_more
|| bstate
== finish_started
) {
1052 if (strm
->avail_out
== 0) {
1053 s
->last_flush
= -1; /* avoid BUF_ERROR next call, see above */
1056 /* If flush != Z_NO_FLUSH && avail_out == 0, the next call
1057 * of deflate should use the same flush parameter to make sure
1058 * that the flush is complete. So we don't have to output an
1059 * empty block here, this will be done at next call. This also
1060 * ensures that for a very small output buffer, we emit at most
1064 if (bstate
== block_done
) {
1065 if (flush
== Z_PARTIAL_FLUSH
) {
1067 } else if (flush
!= Z_BLOCK
) { /* FULL_FLUSH or SYNC_FLUSH */
1068 _tr_stored_block(s
, (char*)0, 0L, 0);
1069 /* For a full flush, this empty block will be recognized
1070 * as a special marker by inflate_sync().
1072 if (flush
== Z_FULL_FLUSH
) {
1073 CLEAR_HASH(s
); /* forget history */
1074 if (s
->lookahead
== 0) {
1076 s
->block_start
= 0L;
1081 flush_pending(strm
);
1082 if (strm
->avail_out
== 0) {
1083 s
->last_flush
= -1; /* avoid BUF_ERROR at next call, see above */
1089 if (flush
!= Z_FINISH
) return Z_OK
;
1090 if (s
->wrap
<= 0) return Z_STREAM_END
;
1092 /* Write the trailer */
1095 put_byte(s
, (Byte
)(strm
->adler
& 0xff));
1096 put_byte(s
, (Byte
)((strm
->adler
>> 8) & 0xff));
1097 put_byte(s
, (Byte
)((strm
->adler
>> 16) & 0xff));
1098 put_byte(s
, (Byte
)((strm
->adler
>> 24) & 0xff));
1099 put_byte(s
, (Byte
)(strm
->total_in
& 0xff));
1100 put_byte(s
, (Byte
)((strm
->total_in
>> 8) & 0xff));
1101 put_byte(s
, (Byte
)((strm
->total_in
>> 16) & 0xff));
1102 put_byte(s
, (Byte
)((strm
->total_in
>> 24) & 0xff));
1107 putShortMSB(s
, (uInt
)(strm
->adler
>> 16));
1108 putShortMSB(s
, (uInt
)(strm
->adler
& 0xffff));
1110 flush_pending(strm
);
1111 /* If avail_out is zero, the application will call deflate again
1112 * to flush the rest.
1114 if (s
->wrap
> 0) s
->wrap
= -s
->wrap
; /* write the trailer only once! */
1115 return s
->pending
!= 0 ? Z_OK
: Z_STREAM_END
;
1118 /* ========================================================================= */
1119 int ZEXPORT
deflateEnd (strm
)
1124 if (deflateStateCheck(strm
)) return Z_STREAM_ERROR
;
1126 status
= strm
->state
->status
;
1128 /* Deallocate in reverse order of allocations: */
1129 TRY_FREE(strm
, strm
->state
->pending_buf
);
1130 TRY_FREE(strm
, strm
->state
->head
);
1131 TRY_FREE(strm
, strm
->state
->prev
);
1132 TRY_FREE(strm
, strm
->state
->window
);
1134 ZFREE(strm
, strm
->state
);
1135 strm
->state
= Z_NULL
;
1137 return status
== BUSY_STATE
? Z_DATA_ERROR
: Z_OK
;
1140 /* =========================================================================
1141 * Copy the source state to the destination state.
1142 * To simplify the source, this is not supported for 16-bit MSDOS (which
1143 * doesn't have enough memory anyway to duplicate compression states).
1145 int ZEXPORT
deflateCopy (dest
, source
)
1150 return Z_STREAM_ERROR
;
1156 if (deflateStateCheck(source
) || dest
== Z_NULL
) {
1157 return Z_STREAM_ERROR
;
1162 zmemcpy((voidpf
)dest
, (voidpf
)source
, sizeof(z_stream
));
1164 ds
= (deflate_state
*) ZALLOC(dest
, 1, sizeof(deflate_state
));
1165 if (ds
== Z_NULL
) return Z_MEM_ERROR
;
1166 dest
->state
= (struct internal_state FAR
*) ds
;
1167 zmemcpy((voidpf
)ds
, (voidpf
)ss
, sizeof(deflate_state
));
1170 ds
->window
= (Bytef
*) ZALLOC(dest
, ds
->w_size
, 2*sizeof(Byte
));
1171 ds
->prev
= (Posf
*) ZALLOC(dest
, ds
->w_size
, sizeof(Pos
));
1172 ds
->head
= (Posf
*) ZALLOC(dest
, ds
->hash_size
, sizeof(Pos
));
1173 ds
->pending_buf
= (uchf
*) ZALLOC(dest
, ds
->lit_bufsize
, 4);
1175 if (ds
->window
== Z_NULL
|| ds
->prev
== Z_NULL
|| ds
->head
== Z_NULL
||
1176 ds
->pending_buf
== Z_NULL
) {
1180 /* following zmemcpy do not work for 16-bit MSDOS */
1181 zmemcpy(ds
->window
, ss
->window
, ds
->w_size
* 2 * sizeof(Byte
));
1182 zmemcpy((voidpf
)ds
->prev
, (voidpf
)ss
->prev
, ds
->w_size
* sizeof(Pos
));
1183 zmemcpy((voidpf
)ds
->head
, (voidpf
)ss
->head
, ds
->hash_size
* sizeof(Pos
));
1184 zmemcpy(ds
->pending_buf
, ss
->pending_buf
, (uInt
)ds
->pending_buf_size
);
1186 ds
->pending_out
= ds
->pending_buf
+ (ss
->pending_out
- ss
->pending_buf
);
1187 ds
->sym_buf
= ds
->pending_buf
+ ds
->lit_bufsize
;
1189 ds
->l_desc
.dyn_tree
= ds
->dyn_ltree
;
1190 ds
->d_desc
.dyn_tree
= ds
->dyn_dtree
;
1191 ds
->bl_desc
.dyn_tree
= ds
->bl_tree
;
1194 #endif /* MAXSEG_64K */
1197 /* ===========================================================================
1198 * Read a new buffer from the current input stream, update the adler32
1199 * and total number of bytes read. All deflate() input goes through
1200 * this function so some applications may wish to modify it to avoid
1201 * allocating a large strm->next_in buffer and copying from it.
1202 * (See also flush_pending()).
1204 local
unsigned read_buf(strm
, buf
, size
)
1209 unsigned len
= strm
->avail_in
;
1211 if (len
> size
) len
= size
;
1212 if (len
== 0) return 0;
1214 strm
->avail_in
-= len
;
1216 zmemcpy(buf
, strm
->next_in
, len
);
1217 if (strm
->state
->wrap
== 1) {
1218 strm
->adler
= adler32(strm
->adler
, buf
, len
);
1221 else if (strm
->state
->wrap
== 2) {
1222 strm
->adler
= crc32(strm
->adler
, buf
, len
);
1225 strm
->next_in
+= len
;
1226 strm
->total_in
+= len
;
1231 /* ===========================================================================
1232 * Initialize the "longest match" routines for a new zlib stream
1234 local
void lm_init (s
)
1237 s
->window_size
= (ulg
)2L*s
->w_size
;
1241 /* Set the default configuration parameters:
1243 s
->max_lazy_match
= configuration_table
[s
->level
].max_lazy
;
1244 s
->good_match
= configuration_table
[s
->level
].good_length
;
1245 s
->nice_match
= configuration_table
[s
->level
].nice_length
;
1246 s
->max_chain_length
= configuration_table
[s
->level
].max_chain
;
1249 s
->block_start
= 0L;
1252 s
->match_length
= s
->prev_length
= MIN_MATCH
-1;
1253 s
->match_available
= 0;
1257 match_init(); /* initialize the asm code */
1263 /* ===========================================================================
1264 * Set match_start to the longest match starting at the given string and
1265 * return its length. Matches shorter or equal to prev_length are discarded,
1266 * in which case the result is equal to prev_length and match_start is
1268 * IN assertions: cur_match is the head of the hash chain for the current
1269 * string (strstart) and its distance is <= MAX_DIST, and prev_length >= 1
1270 * OUT assertion: the match length is not greater than s->lookahead.
1273 /* For 80x86 and 680x0, an optimized version will be provided in match.asm or
1274 * match.S. The code will be functionally equivalent.
1276 local uInt
longest_match(s
, cur_match
)
1278 IPos cur_match
; /* current match */
1280 unsigned chain_length
= s
->max_chain_length
;/* max hash chain length */
1281 register Bytef
*scan
= s
->window
+ s
->strstart
; /* current string */
1282 register Bytef
*match
; /* matched string */
1283 register int len
; /* length of current match */
1284 int best_len
= (int)s
->prev_length
; /* best match length so far */
1285 int nice_match
= s
->nice_match
; /* stop if match long enough */
1286 IPos limit
= s
->strstart
> (IPos
)MAX_DIST(s
) ?
1287 s
->strstart
- (IPos
)MAX_DIST(s
) : NIL
;
1288 /* Stop when cur_match becomes <= limit. To simplify the code,
1289 * we prevent matches with the string of window index 0.
1291 Posf
*prev
= s
->prev
;
1292 uInt wmask
= s
->w_mask
;
1295 /* Compare two bytes at a time. Note: this is not always beneficial.
1296 * Try with and without -DUNALIGNED_OK to check.
1298 register Bytef
*strend
= s
->window
+ s
->strstart
+ MAX_MATCH
- 1;
1299 register ush scan_start
= *(ushf
*)scan
;
1300 register ush scan_end
= *(ushf
*)(scan
+best_len
-1);
1302 register Bytef
*strend
= s
->window
+ s
->strstart
+ MAX_MATCH
;
1303 register Byte scan_end1
= scan
[best_len
-1];
1304 register Byte scan_end
= scan
[best_len
];
1307 /* The code is optimized for HASH_BITS >= 8 and MAX_MATCH-2 multiple of 16.
1308 * It is easy to get rid of this optimization if necessary.
1310 Assert(s
->hash_bits
>= 8 && MAX_MATCH
== 258, "Code too clever");
1312 /* Do not waste too much time if we already have a good match: */
1313 if (s
->prev_length
>= s
->good_match
) {
1316 /* Do not look for matches beyond the end of the input. This is necessary
1317 * to make deflate deterministic.
1319 if ((uInt
)nice_match
> s
->lookahead
) nice_match
= (int)s
->lookahead
;
1321 Assert((ulg
)s
->strstart
<= s
->window_size
-MIN_LOOKAHEAD
, "need lookahead");
1324 Assert(cur_match
< s
->strstart
, "no future");
1325 match
= s
->window
+ cur_match
;
1327 /* Skip to next match if the match length cannot increase
1328 * or if the match length is less than 2. Note that the checks below
1329 * for insufficient lookahead only occur occasionally for performance
1330 * reasons. Therefore uninitialized memory will be accessed, and
1331 * conditional jumps will be made that depend on those values.
1332 * However the length of the match is limited to the lookahead, so
1333 * the output of deflate is not affected by the uninitialized values.
1335 #if (defined(UNALIGNED_OK) && MAX_MATCH == 258)
1336 /* This code assumes sizeof(unsigned short) == 2. Do not use
1337 * UNALIGNED_OK if your compiler uses a different size.
1339 if (*(ushf
*)(match
+best_len
-1) != scan_end
||
1340 *(ushf
*)match
!= scan_start
) continue;
1342 /* It is not necessary to compare scan[2] and match[2] since they are
1343 * always equal when the other bytes match, given that the hash keys
1344 * are equal and that HASH_BITS >= 8. Compare 2 bytes at a time at
1345 * strstart+3, +5, ... up to strstart+257. We check for insufficient
1346 * lookahead only every 4th comparison; the 128th check will be made
1347 * at strstart+257. If MAX_MATCH-2 is not a multiple of 8, it is
1348 * necessary to put more guard bytes at the end of the window, or
1349 * to check more often for insufficient lookahead.
1351 Assert(scan
[2] == match
[2], "scan[2]?");
1354 } while (*(ushf
*)(scan
+=2) == *(ushf
*)(match
+=2) &&
1355 *(ushf
*)(scan
+=2) == *(ushf
*)(match
+=2) &&
1356 *(ushf
*)(scan
+=2) == *(ushf
*)(match
+=2) &&
1357 *(ushf
*)(scan
+=2) == *(ushf
*)(match
+=2) &&
1359 /* The funny "do {}" generates better code on most compilers */
1361 /* Here, scan <= window+strstart+257 */
1362 Assert(scan
<= s
->window
+(unsigned)(s
->window_size
-1), "wild scan");
1363 if (*scan
== *match
) scan
++;
1365 len
= (MAX_MATCH
- 1) - (int)(strend
-scan
);
1366 scan
= strend
- (MAX_MATCH
-1);
1368 #else /* UNALIGNED_OK */
1370 if (match
[best_len
] != scan_end
||
1371 match
[best_len
-1] != scan_end1
||
1373 *++match
!= scan
[1]) continue;
1375 /* The check at best_len-1 can be removed because it will be made
1376 * again later. (This heuristic is not always a win.)
1377 * It is not necessary to compare scan[2] and match[2] since they
1378 * are always equal when the other bytes match, given that
1379 * the hash keys are equal and that HASH_BITS >= 8.
1382 Assert(*scan
== *match
, "match[2]?");
1384 /* We check for insufficient lookahead only every 8th comparison;
1385 * the 256th check will be made at strstart+258.
1388 } while (*++scan
== *++match
&& *++scan
== *++match
&&
1389 *++scan
== *++match
&& *++scan
== *++match
&&
1390 *++scan
== *++match
&& *++scan
== *++match
&&
1391 *++scan
== *++match
&& *++scan
== *++match
&&
1394 Assert(scan
<= s
->window
+(unsigned)(s
->window_size
-1), "wild scan");
1396 len
= MAX_MATCH
- (int)(strend
- scan
);
1397 scan
= strend
- MAX_MATCH
;
1399 #endif /* UNALIGNED_OK */
1401 if (len
> best_len
) {
1402 s
->match_start
= cur_match
;
1404 if (len
>= nice_match
) break;
1406 scan_end
= *(ushf
*)(scan
+best_len
-1);
1408 scan_end1
= scan
[best_len
-1];
1409 scan_end
= scan
[best_len
];
1412 } while ((cur_match
= prev
[cur_match
& wmask
]) > limit
1413 && --chain_length
!= 0);
1415 if ((uInt
)best_len
<= s
->lookahead
) return (uInt
)best_len
;
1416 return s
->lookahead
;
1422 /* ---------------------------------------------------------------------------
1423 * Optimized version for FASTEST only
1425 local uInt
longest_match(s
, cur_match
)
1427 IPos cur_match
; /* current match */
1429 register Bytef
*scan
= s
->window
+ s
->strstart
; /* current string */
1430 register Bytef
*match
; /* matched string */
1431 register int len
; /* length of current match */
1432 register Bytef
*strend
= s
->window
+ s
->strstart
+ MAX_MATCH
;
1434 /* The code is optimized for HASH_BITS >= 8 and MAX_MATCH-2 multiple of 16.
1435 * It is easy to get rid of this optimization if necessary.
1437 Assert(s
->hash_bits
>= 8 && MAX_MATCH
== 258, "Code too clever");
1439 Assert((ulg
)s
->strstart
<= s
->window_size
-MIN_LOOKAHEAD
, "need lookahead");
1441 Assert(cur_match
< s
->strstart
, "no future");
1443 match
= s
->window
+ cur_match
;
1445 /* Return failure if the match length is less than 2:
1447 if (match
[0] != scan
[0] || match
[1] != scan
[1]) return MIN_MATCH
-1;
1449 /* The check at best_len-1 can be removed because it will be made
1450 * again later. (This heuristic is not always a win.)
1451 * It is not necessary to compare scan[2] and match[2] since they
1452 * are always equal when the other bytes match, given that
1453 * the hash keys are equal and that HASH_BITS >= 8.
1455 scan
+= 2, match
+= 2;
1456 Assert(*scan
== *match
, "match[2]?");
1458 /* We check for insufficient lookahead only every 8th comparison;
1459 * the 256th check will be made at strstart+258.
1462 } while (*++scan
== *++match
&& *++scan
== *++match
&&
1463 *++scan
== *++match
&& *++scan
== *++match
&&
1464 *++scan
== *++match
&& *++scan
== *++match
&&
1465 *++scan
== *++match
&& *++scan
== *++match
&&
1468 Assert(scan
<= s
->window
+(unsigned)(s
->window_size
-1), "wild scan");
1470 len
= MAX_MATCH
- (int)(strend
- scan
);
1472 if (len
< MIN_MATCH
) return MIN_MATCH
- 1;
1474 s
->match_start
= cur_match
;
1475 return (uInt
)len
<= s
->lookahead
? (uInt
)len
: s
->lookahead
;
1478 #endif /* FASTEST */
1483 /* result of memcmp for equal strings */
1485 /* ===========================================================================
1486 * Check that the match at match_start is indeed a match.
1488 local
void check_match(s
, start
, match
, length
)
1493 /* check that the match is indeed a match */
1494 if (zmemcmp(s
->window
+ match
,
1495 s
->window
+ start
, length
) != EQUAL
) {
1496 fprintf(stderr
, " start %u, match %u, length %d\n",
1497 start
, match
, length
);
1499 fprintf(stderr
, "%c%c", s
->window
[match
++], s
->window
[start
++]);
1500 } while (--length
!= 0);
1501 z_error("invalid match");
1503 if (z_verbose
> 1) {
1504 fprintf(stderr
,"\\[%d,%d]", start
-match
, length
);
1505 do { putc(s
->window
[start
++], stderr
); } while (--length
!= 0);
1509 # define check_match(s, start, match, length)
1510 #endif /* ZLIB_DEBUG */
1512 /* ===========================================================================
1513 * Fill the window when the lookahead becomes insufficient.
1514 * Updates strstart and lookahead.
1516 * IN assertion: lookahead < MIN_LOOKAHEAD
1517 * OUT assertions: strstart <= window_size-MIN_LOOKAHEAD
1518 * At least one byte has been read, or avail_in == 0; reads are
1519 * performed for at least two bytes (required for the zip translate_eol
1520 * option -- not supported here).
1522 local
void fill_window(s
)
1526 unsigned more
; /* Amount of free space at the end of the window. */
1527 uInt wsize
= s
->w_size
;
1529 Assert(s
->lookahead
< MIN_LOOKAHEAD
, "already enough lookahead");
1532 more
= (unsigned)(s
->window_size
-(ulg
)s
->lookahead
-(ulg
)s
->strstart
);
1534 /* Deal with !@#$% 64K limit: */
1535 if (sizeof(int) <= 2) {
1536 if (more
== 0 && s
->strstart
== 0 && s
->lookahead
== 0) {
1539 } else if (more
== (unsigned)(-1)) {
1540 /* Very unlikely, but possible on 16 bit machine if
1541 * strstart == 0 && lookahead == 1 (input done a byte at time)
1547 /* If the window is almost full and there is insufficient lookahead,
1548 * move the upper half to the lower one to make room in the upper half.
1550 if (s
->strstart
>= wsize
+MAX_DIST(s
)) {
1552 zmemcpy(s
->window
, s
->window
+wsize
, (unsigned)wsize
- more
);
1553 s
->match_start
-= wsize
;
1554 s
->strstart
-= wsize
; /* we now have strstart >= MAX_DIST */
1555 s
->block_start
-= (long) wsize
;
1556 if (s
->insert
> s
->strstart
)
1557 s
->insert
= s
->strstart
;
1561 if (s
->strm
->avail_in
== 0) break;
1563 /* If there was no sliding:
1564 * strstart <= WSIZE+MAX_DIST-1 && lookahead <= MIN_LOOKAHEAD - 1 &&
1565 * more == window_size - lookahead - strstart
1566 * => more >= window_size - (MIN_LOOKAHEAD-1 + WSIZE + MAX_DIST-1)
1567 * => more >= window_size - 2*WSIZE + 2
1568 * In the BIG_MEM or MMAP case (not yet supported),
1569 * window_size == input_size + MIN_LOOKAHEAD &&
1570 * strstart + s->lookahead <= input_size => more >= MIN_LOOKAHEAD.
1571 * Otherwise, window_size == 2*WSIZE so more >= 2.
1572 * If there was sliding, more >= WSIZE. So in all cases, more >= 2.
1574 Assert(more
>= 2, "more < 2");
1576 n
= read_buf(s
->strm
, s
->window
+ s
->strstart
+ s
->lookahead
, more
);
1579 /* Initialize the hash value now that we have some input: */
1580 if (s
->lookahead
+ s
->insert
>= MIN_MATCH
) {
1581 uInt str
= s
->strstart
- s
->insert
;
1582 s
->ins_h
= s
->window
[str
];
1583 UPDATE_HASH(s
, s
->ins_h
, s
->window
[str
+ 1]);
1585 Call
UPDATE_HASH() MIN_MATCH
-3 more times
1588 UPDATE_HASH(s
, s
->ins_h
, s
->window
[str
+ MIN_MATCH
-1]);
1590 s
->prev
[str
& s
->w_mask
] = s
->head
[s
->ins_h
];
1592 s
->head
[s
->ins_h
] = (Pos
)str
;
1595 if (s
->lookahead
+ s
->insert
< MIN_MATCH
)
1599 /* If the whole input has less than MIN_MATCH bytes, ins_h is garbage,
1600 * but this is not important since only literal bytes will be emitted.
1603 } while (s
->lookahead
< MIN_LOOKAHEAD
&& s
->strm
->avail_in
!= 0);
1605 /* If the WIN_INIT bytes after the end of the current data have never been
1606 * written, then zero those bytes in order to avoid memory check reports of
1607 * the use of uninitialized (or uninitialised as Julian writes) bytes by
1608 * the longest match routines. Update the high water mark for the next
1609 * time through here. WIN_INIT is set to MAX_MATCH since the longest match
1610 * routines allow scanning to strstart + MAX_MATCH, ignoring lookahead.
1612 if (s
->high_water
< s
->window_size
) {
1613 ulg curr
= s
->strstart
+ (ulg
)(s
->lookahead
);
1616 if (s
->high_water
< curr
) {
1617 /* Previous high water mark below current data -- zero WIN_INIT
1618 * bytes or up to end of window, whichever is less.
1620 init
= s
->window_size
- curr
;
1621 if (init
> WIN_INIT
)
1623 zmemzero(s
->window
+ curr
, (unsigned)init
);
1624 s
->high_water
= curr
+ init
;
1626 else if (s
->high_water
< (ulg
)curr
+ WIN_INIT
) {
1627 /* High water mark at or above current data, but below current data
1628 * plus WIN_INIT -- zero out to current data plus WIN_INIT, or up
1629 * to end of window, whichever is less.
1631 init
= (ulg
)curr
+ WIN_INIT
- s
->high_water
;
1632 if (init
> s
->window_size
- s
->high_water
)
1633 init
= s
->window_size
- s
->high_water
;
1634 zmemzero(s
->window
+ s
->high_water
, (unsigned)init
);
1635 s
->high_water
+= init
;
1639 Assert((ulg
)s
->strstart
<= s
->window_size
- MIN_LOOKAHEAD
,
1640 "not enough room for search");
1643 /* ===========================================================================
1644 * Flush the current block, with given end-of-file flag.
1645 * IN assertion: strstart is set to the end of the current match.
1647 #define FLUSH_BLOCK_ONLY(s, last) { \
1648 _tr_flush_block(s, (s->block_start >= 0L ? \
1649 (charf *)&s->window[(unsigned)s->block_start] : \
1651 (ulg)((long)s->strstart - s->block_start), \
1653 s->block_start = s->strstart; \
1654 flush_pending(s->strm); \
1655 Tracev((stderr,"[FLUSH]")); \
1658 /* Same but force premature exit if necessary. */
1659 #define FLUSH_BLOCK(s, last) { \
1660 FLUSH_BLOCK_ONLY(s, last); \
1661 if (s->strm->avail_out == 0) return (last) ? finish_started : need_more; \
1664 /* Maximum stored block length in deflate format (not including header). */
1665 #define MAX_STORED 65535
1667 /* Minimum of a and b. */
1668 #define MIN(a, b) ((a) > (b) ? (b) : (a))
1670 /* ===========================================================================
1671 * Copy without compression as much as possible from the input stream, return
1672 * the current block state.
1674 * In case deflateParams() is used to later switch to a non-zero compression
1675 * level, s->matches (otherwise unused when storing) keeps track of the number
1676 * of hash table slides to perform. If s->matches is 1, then one hash table
1677 * slide will be done when switching. If s->matches is 2, the maximum value
1678 * allowed here, then the hash table will be cleared, since two or more slides
1679 * is the same as a clear.
1681 * deflate_stored() is written to minimize the number of times an input byte is
1682 * copied. It is most efficient with large input and output buffers, which
1683 * maximizes the opportunites to have a single copy from next_in to next_out.
1685 local block_state
deflate_stored(s
, flush
)
1689 /* Smallest worthy block size when not flushing or finishing. By default
1690 * this is 32K. This can be as small as 507 bytes for memLevel == 1. For
1691 * large input and output buffers, the stored block size will be larger.
1693 unsigned min_block
= MIN(s
->pending_buf_size
- 5, s
->w_size
);
1695 /* Copy as many min_block or larger stored blocks directly to next_out as
1696 * possible. If flushing, copy the remaining available input to next_out as
1697 * stored blocks, if there is enough space.
1699 unsigned len
, left
, have
, last
= 0;
1700 unsigned used
= s
->strm
->avail_in
;
1702 /* Set len to the maximum size block that we can copy directly with the
1703 * available input data and output space. Set left to how much of that
1704 * would be copied from what's left in the window.
1706 len
= MAX_STORED
; /* maximum deflate stored block length */
1707 have
= (s
->bi_valid
+ 42) >> 3; /* number of header bytes */
1708 if (s
->strm
->avail_out
< have
) /* need room for header */
1710 /* maximum stored block length that will fit in avail_out: */
1711 have
= s
->strm
->avail_out
- have
;
1712 left
= s
->strstart
- s
->block_start
; /* bytes left in window */
1713 if (len
> (ulg
)left
+ s
->strm
->avail_in
)
1714 len
= left
+ s
->strm
->avail_in
; /* limit len to the input */
1716 len
= have
; /* limit len to the output */
1718 /* If the stored block would be less than min_block in length, or if
1719 * unable to copy all of the available input when flushing, then try
1720 * copying to the window and the pending buffer instead. Also don't
1721 * write an empty block when flushing -- deflate() does that.
1723 if (len
< min_block
&& ((len
== 0 && flush
!= Z_FINISH
) ||
1724 flush
== Z_NO_FLUSH
||
1725 len
!= left
+ s
->strm
->avail_in
))
1728 /* Make a dummy stored block in pending to get the header bytes,
1729 * including any pending bits. This also updates the debugging counts.
1731 last
= flush
== Z_FINISH
&& len
== left
+ s
->strm
->avail_in
? 1 : 0;
1732 _tr_stored_block(s
, (char *)0, 0L, last
);
1734 /* Replace the lengths in the dummy stored block with len. */
1735 s
->pending_buf
[s
->pending
- 4] = len
;
1736 s
->pending_buf
[s
->pending
- 3] = len
>> 8;
1737 s
->pending_buf
[s
->pending
- 2] = ~len
;
1738 s
->pending_buf
[s
->pending
- 1] = ~len
>> 8;
1740 /* Write the stored block header bytes. */
1741 flush_pending(s
->strm
);
1744 /* Update debugging counts for the data about to be copied. */
1745 s
->compressed_len
+= len
<< 3;
1746 s
->bits_sent
+= len
<< 3;
1749 /* Copy uncompressed bytes from the window to next_out. */
1753 zmemcpy(s
->strm
->next_out
, s
->window
+ s
->block_start
, left
);
1754 s
->strm
->next_out
+= left
;
1755 s
->strm
->avail_out
-= left
;
1756 s
->strm
->total_out
+= left
;
1757 s
->block_start
+= left
;
1761 /* Copy uncompressed bytes directly from next_in to next_out, updating
1765 read_buf(s
->strm
, s
->strm
->next_out
, len
);
1766 s
->strm
->next_out
+= len
;
1767 s
->strm
->avail_out
-= len
;
1768 s
->strm
->total_out
+= len
;
1770 } while (last
== 0);
1772 /* Update the sliding window with the last s->w_size bytes of the copied
1773 * data, or append all of the copied data to the existing window if less
1774 * than s->w_size bytes were copied. Also update the number of bytes to
1775 * insert in the hash tables, in the event that deflateParams() switches to
1776 * a non-zero compression level.
1778 used
-= s
->strm
->avail_in
; /* number of input bytes directly copied */
1780 /* If any input was used, then no unused input remains in the window,
1781 * therefore s->block_start == s->strstart.
1783 if (used
>= s
->w_size
) { /* supplant the previous history */
1784 s
->matches
= 2; /* clear hash */
1785 zmemcpy(s
->window
, s
->strm
->next_in
- s
->w_size
, s
->w_size
);
1786 s
->strstart
= s
->w_size
;
1787 s
->insert
= s
->strstart
;
1790 if (s
->window_size
- s
->strstart
<= used
) {
1791 /* Slide the window down. */
1792 s
->strstart
-= s
->w_size
;
1793 zmemcpy(s
->window
, s
->window
+ s
->w_size
, s
->strstart
);
1795 s
->matches
++; /* add a pending slide_hash() */
1796 if (s
->insert
> s
->strstart
)
1797 s
->insert
= s
->strstart
;
1799 zmemcpy(s
->window
+ s
->strstart
, s
->strm
->next_in
- used
, used
);
1800 s
->strstart
+= used
;
1801 s
->insert
+= MIN(used
, s
->w_size
- s
->insert
);
1803 s
->block_start
= s
->strstart
;
1805 if (s
->high_water
< s
->strstart
)
1806 s
->high_water
= s
->strstart
;
1808 /* If the last block was written to next_out, then done. */
1812 /* If flushing and all input has been consumed, then done. */
1813 if (flush
!= Z_NO_FLUSH
&& flush
!= Z_FINISH
&&
1814 s
->strm
->avail_in
== 0 && (long)s
->strstart
== s
->block_start
)
1817 /* Fill the window with any remaining input. */
1818 have
= s
->window_size
- s
->strstart
;
1819 if (s
->strm
->avail_in
> have
&& s
->block_start
>= (long)s
->w_size
) {
1820 /* Slide the window down. */
1821 s
->block_start
-= s
->w_size
;
1822 s
->strstart
-= s
->w_size
;
1823 zmemcpy(s
->window
, s
->window
+ s
->w_size
, s
->strstart
);
1825 s
->matches
++; /* add a pending slide_hash() */
1826 have
+= s
->w_size
; /* more space now */
1827 if (s
->insert
> s
->strstart
)
1828 s
->insert
= s
->strstart
;
1830 if (have
> s
->strm
->avail_in
)
1831 have
= s
->strm
->avail_in
;
1833 read_buf(s
->strm
, s
->window
+ s
->strstart
, have
);
1834 s
->strstart
+= have
;
1835 s
->insert
+= MIN(have
, s
->w_size
- s
->insert
);
1837 if (s
->high_water
< s
->strstart
)
1838 s
->high_water
= s
->strstart
;
1840 /* There was not enough avail_out to write a complete worthy or flushed
1841 * stored block to next_out. Write a stored block to pending instead, if we
1842 * have enough input for a worthy block, or if flushing and there is enough
1843 * room for the remaining input as a stored block in the pending buffer.
1845 have
= (s
->bi_valid
+ 42) >> 3; /* number of header bytes */
1846 /* maximum stored block length that will fit in pending: */
1847 have
= MIN(s
->pending_buf_size
- have
, MAX_STORED
);
1848 min_block
= MIN(have
, s
->w_size
);
1849 left
= s
->strstart
- s
->block_start
;
1850 if (left
>= min_block
||
1851 ((left
|| flush
== Z_FINISH
) && flush
!= Z_NO_FLUSH
&&
1852 s
->strm
->avail_in
== 0 && left
<= have
)) {
1853 len
= MIN(left
, have
);
1854 last
= flush
== Z_FINISH
&& s
->strm
->avail_in
== 0 &&
1855 len
== left
? 1 : 0;
1856 _tr_stored_block(s
, (charf
*)s
->window
+ s
->block_start
, len
, last
);
1857 s
->block_start
+= len
;
1858 flush_pending(s
->strm
);
1861 /* We've done all we can with the available input and output. */
1862 return last
? finish_started
: need_more
;
1865 /* ===========================================================================
1866 * Compress as much as possible from the input stream, return the current
1868 * This function does not perform lazy evaluation of matches and inserts
1869 * new strings in the dictionary only for unmatched strings or for short
1870 * matches. It is used only for the fast compression options.
1872 local block_state
deflate_fast(s
, flush
)
1876 IPos hash_head
; /* head of the hash chain */
1877 int bflush
; /* set if current block must be flushed */
1880 /* Make sure that we always have enough lookahead, except
1881 * at the end of the input file. We need MAX_MATCH bytes
1882 * for the next match, plus MIN_MATCH bytes to insert the
1883 * string following the next match.
1885 if (s
->lookahead
< MIN_LOOKAHEAD
) {
1887 if (s
->lookahead
< MIN_LOOKAHEAD
&& flush
== Z_NO_FLUSH
) {
1890 if (s
->lookahead
== 0) break; /* flush the current block */
1893 /* Insert the string window[strstart .. strstart+2] in the
1894 * dictionary, and set hash_head to the head of the hash chain:
1897 if (s
->lookahead
>= MIN_MATCH
) {
1898 INSERT_STRING(s
, s
->strstart
, hash_head
);
1901 /* Find the longest match, discarding those <= prev_length.
1902 * At this point we have always match_length < MIN_MATCH
1904 if (hash_head
!= NIL
&& s
->strstart
- hash_head
<= MAX_DIST(s
)) {
1905 /* To simplify the code, we prevent matches with the string
1906 * of window index 0 (in particular we have to avoid a match
1907 * of the string with itself at the start of the input file).
1909 s
->match_length
= longest_match (s
, hash_head
);
1910 /* longest_match() sets match_start */
1912 if (s
->match_length
>= MIN_MATCH
) {
1913 check_match(s
, s
->strstart
, s
->match_start
, s
->match_length
);
1915 _tr_tally_dist(s
, s
->strstart
- s
->match_start
,
1916 s
->match_length
- MIN_MATCH
, bflush
);
1918 s
->lookahead
-= s
->match_length
;
1920 /* Insert new strings in the hash table only if the match length
1921 * is not too large. This saves time but degrades compression.
1924 if (s
->match_length
<= s
->max_insert_length
&&
1925 s
->lookahead
>= MIN_MATCH
) {
1926 s
->match_length
--; /* string at strstart already in table */
1929 INSERT_STRING(s
, s
->strstart
, hash_head
);
1930 /* strstart never exceeds WSIZE-MAX_MATCH, so there are
1931 * always MIN_MATCH bytes ahead.
1933 } while (--s
->match_length
!= 0);
1938 s
->strstart
+= s
->match_length
;
1939 s
->match_length
= 0;
1940 s
->ins_h
= s
->window
[s
->strstart
];
1941 UPDATE_HASH(s
, s
->ins_h
, s
->window
[s
->strstart
+1]);
1943 Call
UPDATE_HASH() MIN_MATCH
-3 more times
1945 /* If lookahead < MIN_MATCH, ins_h is garbage, but it does not
1946 * matter since it will be recomputed at next deflate call.
1950 /* No match, output a literal byte */
1951 Tracevv((stderr
,"%c", s
->window
[s
->strstart
]));
1952 _tr_tally_lit (s
, s
->window
[s
->strstart
], bflush
);
1956 if (bflush
) FLUSH_BLOCK(s
, 0);
1958 s
->insert
= s
->strstart
< MIN_MATCH
-1 ? s
->strstart
: MIN_MATCH
-1;
1959 if (flush
== Z_FINISH
) {
1969 /* ===========================================================================
1970 * Same as above, but achieves better compression. We use a lazy
1971 * evaluation for matches: a match is finally adopted only if there is
1972 * no better match at the next window position.
1974 local block_state
deflate_slow(s
, flush
)
1978 IPos hash_head
; /* head of hash chain */
1979 int bflush
; /* set if current block must be flushed */
1981 /* Process the input block. */
1983 /* Make sure that we always have enough lookahead, except
1984 * at the end of the input file. We need MAX_MATCH bytes
1985 * for the next match, plus MIN_MATCH bytes to insert the
1986 * string following the next match.
1988 if (s
->lookahead
< MIN_LOOKAHEAD
) {
1990 if (s
->lookahead
< MIN_LOOKAHEAD
&& flush
== Z_NO_FLUSH
) {
1993 if (s
->lookahead
== 0) break; /* flush the current block */
1996 /* Insert the string window[strstart .. strstart+2] in the
1997 * dictionary, and set hash_head to the head of the hash chain:
2000 if (s
->lookahead
>= MIN_MATCH
) {
2001 INSERT_STRING(s
, s
->strstart
, hash_head
);
2004 /* Find the longest match, discarding those <= prev_length.
2006 s
->prev_length
= s
->match_length
, s
->prev_match
= s
->match_start
;
2007 s
->match_length
= MIN_MATCH
-1;
2009 if (hash_head
!= NIL
&& s
->prev_length
< s
->max_lazy_match
&&
2010 s
->strstart
- hash_head
<= MAX_DIST(s
)) {
2011 /* To simplify the code, we prevent matches with the string
2012 * of window index 0 (in particular we have to avoid a match
2013 * of the string with itself at the start of the input file).
2015 s
->match_length
= longest_match (s
, hash_head
);
2016 /* longest_match() sets match_start */
2018 if (s
->match_length
<= 5 && (s
->strategy
== Z_FILTERED
2019 #if TOO_FAR <= 32767
2020 || (s
->match_length
== MIN_MATCH
&&
2021 s
->strstart
- s
->match_start
> TOO_FAR
)
2025 /* If prev_match is also MIN_MATCH, match_start is garbage
2026 * but we will ignore the current match anyway.
2028 s
->match_length
= MIN_MATCH
-1;
2031 /* If there was a match at the previous step and the current
2032 * match is not better, output the previous match:
2034 if (s
->prev_length
>= MIN_MATCH
&& s
->match_length
<= s
->prev_length
) {
2035 uInt max_insert
= s
->strstart
+ s
->lookahead
- MIN_MATCH
;
2036 /* Do not insert strings in hash table beyond this. */
2038 check_match(s
, s
->strstart
-1, s
->prev_match
, s
->prev_length
);
2040 _tr_tally_dist(s
, s
->strstart
-1 - s
->prev_match
,
2041 s
->prev_length
- MIN_MATCH
, bflush
);
2043 /* Insert in hash table all strings up to the end of the match.
2044 * strstart-1 and strstart are already inserted. If there is not
2045 * enough lookahead, the last two strings are not inserted in
2048 s
->lookahead
-= s
->prev_length
-1;
2049 s
->prev_length
-= 2;
2051 if (++s
->strstart
<= max_insert
) {
2052 INSERT_STRING(s
, s
->strstart
, hash_head
);
2054 } while (--s
->prev_length
!= 0);
2055 s
->match_available
= 0;
2056 s
->match_length
= MIN_MATCH
-1;
2059 if (bflush
) FLUSH_BLOCK(s
, 0);
2061 } else if (s
->match_available
) {
2062 /* If there was no match at the previous position, output a
2063 * single literal. If there was a match but the current match
2064 * is longer, truncate the previous match to a single literal.
2066 Tracevv((stderr
,"%c", s
->window
[s
->strstart
-1]));
2067 _tr_tally_lit(s
, s
->window
[s
->strstart
-1], bflush
);
2069 FLUSH_BLOCK_ONLY(s
, 0);
2073 if (s
->strm
->avail_out
== 0) return need_more
;
2075 /* There is no previous match to compare with, wait for
2076 * the next step to decide.
2078 s
->match_available
= 1;
2083 Assert (flush
!= Z_NO_FLUSH
, "no flush?");
2084 if (s
->match_available
) {
2085 Tracevv((stderr
,"%c", s
->window
[s
->strstart
-1]));
2086 _tr_tally_lit(s
, s
->window
[s
->strstart
-1], bflush
);
2087 s
->match_available
= 0;
2089 s
->insert
= s
->strstart
< MIN_MATCH
-1 ? s
->strstart
: MIN_MATCH
-1;
2090 if (flush
== Z_FINISH
) {
2098 #endif /* FASTEST */
2100 /* ===========================================================================
2101 * For Z_RLE, simply look for runs of bytes, generate matches only of distance
2102 * one. Do not maintain a hash table. (It will be regenerated if this run of
2103 * deflate switches away from Z_RLE.)
2105 local block_state
deflate_rle(s
, flush
)
2109 int bflush
; /* set if current block must be flushed */
2110 uInt prev
; /* byte at distance one to match */
2111 Bytef
*scan
, *strend
; /* scan goes up to strend for length of run */
2114 /* Make sure that we always have enough lookahead, except
2115 * at the end of the input file. We need MAX_MATCH bytes
2116 * for the longest run, plus one for the unrolled loop.
2118 if (s
->lookahead
<= MAX_MATCH
) {
2120 if (s
->lookahead
<= MAX_MATCH
&& flush
== Z_NO_FLUSH
) {
2123 if (s
->lookahead
== 0) break; /* flush the current block */
2126 /* See how many times the previous byte repeats */
2127 s
->match_length
= 0;
2128 if (s
->lookahead
>= MIN_MATCH
&& s
->strstart
> 0) {
2129 scan
= s
->window
+ s
->strstart
- 1;
2131 if (prev
== *++scan
&& prev
== *++scan
&& prev
== *++scan
) {
2132 strend
= s
->window
+ s
->strstart
+ MAX_MATCH
;
2134 } while (prev
== *++scan
&& prev
== *++scan
&&
2135 prev
== *++scan
&& prev
== *++scan
&&
2136 prev
== *++scan
&& prev
== *++scan
&&
2137 prev
== *++scan
&& prev
== *++scan
&&
2139 s
->match_length
= MAX_MATCH
- (uInt
)(strend
- scan
);
2140 if (s
->match_length
> s
->lookahead
)
2141 s
->match_length
= s
->lookahead
;
2143 Assert(scan
<= s
->window
+(uInt
)(s
->window_size
-1), "wild scan");
2146 /* Emit match if have run of MIN_MATCH or longer, else emit literal */
2147 if (s
->match_length
>= MIN_MATCH
) {
2148 check_match(s
, s
->strstart
, s
->strstart
- 1, s
->match_length
);
2150 _tr_tally_dist(s
, 1, s
->match_length
- MIN_MATCH
, bflush
);
2152 s
->lookahead
-= s
->match_length
;
2153 s
->strstart
+= s
->match_length
;
2154 s
->match_length
= 0;
2156 /* No match, output a literal byte */
2157 Tracevv((stderr
,"%c", s
->window
[s
->strstart
]));
2158 _tr_tally_lit (s
, s
->window
[s
->strstart
], bflush
);
2162 if (bflush
) FLUSH_BLOCK(s
, 0);
2165 if (flush
== Z_FINISH
) {
2174 /* ===========================================================================
2175 * For Z_HUFFMAN_ONLY, do not look for matches. Do not maintain a hash table.
2176 * (It will be regenerated if this run of deflate switches away from Huffman.)
2178 local block_state
deflate_huff(s
, flush
)
2182 int bflush
; /* set if current block must be flushed */
2185 /* Make sure that we have a literal to write. */
2186 if (s
->lookahead
== 0) {
2188 if (s
->lookahead
== 0) {
2189 if (flush
== Z_NO_FLUSH
)
2191 break; /* flush the current block */
2195 /* Output a literal byte */
2196 s
->match_length
= 0;
2197 Tracevv((stderr
,"%c", s
->window
[s
->strstart
]));
2198 _tr_tally_lit (s
, s
->window
[s
->strstart
], bflush
);
2201 if (bflush
) FLUSH_BLOCK(s
, 0);
2204 if (flush
== Z_FINISH
) {