1 /* deflate.c -- compress data using the deflation algorithm
2 * Copyright (C) 1995-2017 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
50 /* @(#) $Id: deflate.c,v 1.1.1.2 2002/03/11 21:53:23 tromey Exp $ */
54 const char deflate_copyright
[] =
55 " deflate 1.2.10 Copyright 1995-2017 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) \
193 s->head[s->hash_size-1] = NIL; \
194 zmemzero((Bytef *)s->head, (unsigned)(s->hash_size-1)*sizeof(*s->head));
196 /* ===========================================================================
197 * Slide the hash table when sliding the window down (could be avoided with 32
198 * bit values at the expense of memory usage). We slide even when level == 0 to
199 * keep the hash table consistent if we switch back to level > 0 later.
201 local
void slide_hash(s
)
206 uInt wsize
= s
->w_size
;
212 *p
= (Pos
)(m
>= wsize
? m
- wsize
: NIL
);
219 *p
= (Pos
)(m
>= wsize
? m
- wsize
: NIL
);
220 /* If n is not on any hash chain, prev[n] is garbage but
221 * its value will never be used.
227 /* ========================================================================= */
228 int ZEXPORT
deflateInit_(strm
, level
, version
, stream_size
)
234 return deflateInit2_(strm
, level
, Z_DEFLATED
, MAX_WBITS
, DEF_MEM_LEVEL
,
235 Z_DEFAULT_STRATEGY
, version
, stream_size
);
236 /* To do: ignore strm->next_in if we use it as window */
239 /* ========================================================================= */
240 int ZEXPORT
deflateInit2_(strm
, level
, method
, windowBits
, memLevel
, strategy
,
241 version
, stream_size
)
253 static const char my_version
[] = ZLIB_VERSION
;
256 /* We overlay pending_buf and d_buf+l_buf. This works since the average
257 * output size for (length,distance) codes is <= 24 bits.
260 if (version
== Z_NULL
|| version
[0] != my_version
[0] ||
261 stream_size
!= sizeof(z_stream
)) {
262 return Z_VERSION_ERROR
;
264 if (strm
== Z_NULL
) return Z_STREAM_ERROR
;
267 if (strm
->zalloc
== (alloc_func
)0) {
269 return Z_STREAM_ERROR
;
271 strm
->zalloc
= zcalloc
;
272 strm
->opaque
= (voidpf
)0;
275 if (strm
->zfree
== (free_func
)0)
277 return Z_STREAM_ERROR
;
279 strm
->zfree
= zcfree
;
283 if (level
!= 0) level
= 1;
285 if (level
== Z_DEFAULT_COMPRESSION
) level
= 6;
288 if (windowBits
< 0) { /* suppress zlib wrapper */
290 windowBits
= -windowBits
;
293 else if (windowBits
> 15) {
294 wrap
= 2; /* write gzip wrapper instead */
298 if (memLevel
< 1 || memLevel
> MAX_MEM_LEVEL
|| method
!= Z_DEFLATED
||
299 windowBits
< 8 || windowBits
> 15 || level
< 0 || level
> 9 ||
300 strategy
< 0 || strategy
> Z_FIXED
|| (windowBits
== 8 && wrap
!= 1)) {
301 return Z_STREAM_ERROR
;
303 if (windowBits
== 8) windowBits
= 9; /* until 256-byte window bug fixed */
304 s
= (deflate_state
*) ZALLOC(strm
, 1, sizeof(deflate_state
));
305 if (s
== Z_NULL
) return Z_MEM_ERROR
;
306 strm
->state
= (struct internal_state FAR
*)s
;
308 s
->status
= INIT_STATE
; /* to pass state test in deflateReset() */
312 s
->w_bits
= (uInt
)windowBits
;
313 s
->w_size
= 1 << s
->w_bits
;
314 s
->w_mask
= s
->w_size
- 1;
316 s
->hash_bits
= (uInt
)memLevel
+ 7;
317 s
->hash_size
= 1 << s
->hash_bits
;
318 s
->hash_mask
= s
->hash_size
- 1;
319 s
->hash_shift
= ((s
->hash_bits
+MIN_MATCH
-1)/MIN_MATCH
);
321 s
->window
= (Bytef
*) ZALLOC(strm
, s
->w_size
, 2*sizeof(Byte
));
322 s
->prev
= (Posf
*) ZALLOC(strm
, s
->w_size
, sizeof(Pos
));
323 s
->head
= (Posf
*) ZALLOC(strm
, s
->hash_size
, sizeof(Pos
));
325 s
->high_water
= 0; /* nothing written to s->window yet */
327 s
->lit_bufsize
= 1 << (memLevel
+ 6); /* 16K elements by default */
329 overlay
= (ushf
*) ZALLOC(strm
, s
->lit_bufsize
, sizeof(ush
)+2);
330 s
->pending_buf
= (uchf
*) overlay
;
331 s
->pending_buf_size
= (ulg
)s
->lit_bufsize
* (sizeof(ush
)+2L);
333 if (s
->window
== Z_NULL
|| s
->prev
== Z_NULL
|| s
->head
== Z_NULL
||
334 s
->pending_buf
== Z_NULL
) {
335 s
->status
= FINISH_STATE
;
336 strm
->msg
= ERR_MSG(Z_MEM_ERROR
);
340 s
->d_buf
= overlay
+ s
->lit_bufsize
/sizeof(ush
);
341 s
->l_buf
= s
->pending_buf
+ (1+sizeof(ush
))*s
->lit_bufsize
;
344 s
->strategy
= strategy
;
345 s
->method
= (Byte
)method
;
347 return deflateReset(strm
);
350 /* =========================================================================
351 * Check for a valid deflate stream state. Return 0 if ok, 1 if not.
353 local
int deflateStateCheck (strm
)
357 if (strm
== Z_NULL
||
358 strm
->zalloc
== (alloc_func
)0 || strm
->zfree
== (free_func
)0)
361 if (s
== Z_NULL
|| s
->strm
!= strm
|| (s
->status
!= INIT_STATE
&&
363 s
->status
!= GZIP_STATE
&&
365 s
->status
!= EXTRA_STATE
&&
366 s
->status
!= NAME_STATE
&&
367 s
->status
!= COMMENT_STATE
&&
368 s
->status
!= HCRC_STATE
&&
369 s
->status
!= BUSY_STATE
&&
370 s
->status
!= FINISH_STATE
))
375 /* ========================================================================= */
376 int ZEXPORT
deflateSetDictionary (strm
, dictionary
, dictLength
)
378 const Bytef
*dictionary
;
385 z_const
unsigned char *next
;
387 if (deflateStateCheck(strm
) || dictionary
== Z_NULL
)
388 return Z_STREAM_ERROR
;
391 if (wrap
== 2 || (wrap
== 1 && s
->status
!= INIT_STATE
) || s
->lookahead
)
392 return Z_STREAM_ERROR
;
394 /* when using zlib wrappers, compute Adler-32 for provided dictionary */
396 strm
->adler
= adler32(strm
->adler
, dictionary
, dictLength
);
397 s
->wrap
= 0; /* avoid computing Adler-32 in read_buf */
399 /* if dictionary would fill window, just replace the history */
400 if (dictLength
>= s
->w_size
) {
401 if (wrap
== 0) { /* already empty otherwise */
407 dictionary
+= dictLength
- s
->w_size
; /* use the tail */
408 dictLength
= s
->w_size
;
411 /* insert dictionary into window and hash */
412 avail
= strm
->avail_in
;
413 next
= strm
->next_in
;
414 strm
->avail_in
= dictLength
;
415 strm
->next_in
= (z_const Bytef
*)dictionary
;
417 while (s
->lookahead
>= MIN_MATCH
) {
419 n
= s
->lookahead
- (MIN_MATCH
-1);
421 UPDATE_HASH(s
, s
->ins_h
, s
->window
[str
+ MIN_MATCH
-1]);
423 s
->prev
[str
& s
->w_mask
] = s
->head
[s
->ins_h
];
425 s
->head
[s
->ins_h
] = (Pos
)str
;
429 s
->lookahead
= MIN_MATCH
-1;
432 s
->strstart
+= s
->lookahead
;
433 s
->block_start
= (long)s
->strstart
;
434 s
->insert
= s
->lookahead
;
436 s
->match_length
= s
->prev_length
= MIN_MATCH
-1;
437 s
->match_available
= 0;
438 strm
->next_in
= next
;
439 strm
->avail_in
= avail
;
444 /* ========================================================================= */
445 int ZEXPORT
deflateGetDictionary (strm
, dictionary
, dictLength
)
453 if (deflateStateCheck(strm
))
454 return Z_STREAM_ERROR
;
456 len
= s
->strstart
+ s
->lookahead
;
459 if (dictionary
!= Z_NULL
&& len
)
460 zmemcpy(dictionary
, s
->window
+ s
->strstart
+ s
->lookahead
- len
, len
);
461 if (dictLength
!= Z_NULL
)
466 /* ========================================================================= */
467 int ZEXPORT
deflateResetKeep (strm
)
472 if (deflateStateCheck(strm
)) {
473 return Z_STREAM_ERROR
;
476 strm
->total_in
= strm
->total_out
= 0;
477 strm
->msg
= Z_NULL
; /* use zfree if we ever allocate msg dynamically */
478 strm
->data_type
= Z_UNKNOWN
;
480 s
= (deflate_state
*)strm
->state
;
482 s
->pending_out
= s
->pending_buf
;
485 s
->wrap
= -s
->wrap
; /* was made negative by deflate(..., Z_FINISH); */
489 s
->wrap
== 2 ? GZIP_STATE
:
491 s
->wrap
? INIT_STATE
: BUSY_STATE
;
494 s
->wrap
== 2 ? crc32(0L, Z_NULL
, 0) :
496 adler32(0L, Z_NULL
, 0);
497 s
->last_flush
= Z_NO_FLUSH
;
504 /* ========================================================================= */
505 int ZEXPORT
deflateReset (strm
)
510 ret
= deflateResetKeep(strm
);
512 lm_init(strm
->state
);
516 /* ========================================================================= */
517 int ZEXPORT
deflateSetHeader (strm
, head
)
521 if (deflateStateCheck(strm
) || strm
->state
->wrap
!= 2)
522 return Z_STREAM_ERROR
;
523 strm
->state
->gzhead
= head
;
527 /* ========================================================================= */
528 int ZEXPORT
deflatePending (strm
, pending
, bits
)
533 if (deflateStateCheck(strm
)) return Z_STREAM_ERROR
;
534 if (pending
!= Z_NULL
)
535 *pending
= strm
->state
->pending
;
537 *bits
= strm
->state
->bi_valid
;
541 /* ========================================================================= */
542 int ZEXPORT
deflatePrime (strm
, bits
, value
)
550 if (deflateStateCheck(strm
)) return Z_STREAM_ERROR
;
552 if ((Bytef
*)(s
->d_buf
) < s
->pending_out
+ ((Buf_size
+ 7) >> 3))
555 put
= Buf_size
- s
->bi_valid
;
558 s
->bi_buf
|= (ush
)((value
& ((1 << put
) - 1)) << s
->bi_valid
);
567 /* ========================================================================= */
568 int ZEXPORT
deflateParams(strm
, level
, strategy
)
576 if (deflateStateCheck(strm
)) return Z_STREAM_ERROR
;
580 if (level
!= 0) level
= 1;
582 if (level
== Z_DEFAULT_COMPRESSION
) level
= 6;
584 if (level
< 0 || level
> 9 || strategy
< 0 || strategy
> Z_FIXED
) {
585 return Z_STREAM_ERROR
;
587 func
= configuration_table
[s
->level
].func
;
589 if ((strategy
!= s
->strategy
|| func
!= configuration_table
[level
].func
)) {
590 /* Flush the last buffer: */
591 int err
= deflate(strm
, Z_BLOCK
);
592 if (err
== Z_STREAM_ERROR
)
594 if (strm
->avail_out
== 0)
597 if (s
->level
!= level
) {
598 if (s
->level
== 0 && s
->matches
!= 0) {
606 s
->max_lazy_match
= configuration_table
[level
].max_lazy
;
607 s
->good_match
= configuration_table
[level
].good_length
;
608 s
->nice_match
= configuration_table
[level
].nice_length
;
609 s
->max_chain_length
= configuration_table
[level
].max_chain
;
611 s
->strategy
= strategy
;
615 /* ========================================================================= */
616 int ZEXPORT
deflateTune(strm
, good_length
, max_lazy
, nice_length
, max_chain
)
625 if (deflateStateCheck(strm
)) return Z_STREAM_ERROR
;
627 s
->good_match
= (uInt
)good_length
;
628 s
->max_lazy_match
= (uInt
)max_lazy
;
629 s
->nice_match
= nice_length
;
630 s
->max_chain_length
= (uInt
)max_chain
;
634 /* =========================================================================
635 * For the default windowBits of 15 and memLevel of 8, this function returns
636 * a close to exact, as well as small, upper bound on the compressed size.
637 * They are coded as constants here for a reason--if the #define's are
638 * changed, then this function needs to be changed as well. The return
639 * value for 15 and 8 only works for those exact settings.
641 * For any setting other than those defaults for windowBits and memLevel,
642 * the value returned is a conservative worst case for the maximum expansion
643 * resulting from using fixed blocks instead of stored blocks, which deflate
644 * can emit on compressed data for some combinations of the parameters.
646 * This function could be more sophisticated to provide closer upper bounds for
647 * every combination of windowBits and memLevel. But even the conservative
648 * upper bound of about 14% expansion does not seem onerous for output buffer
651 uLong ZEXPORT
deflateBound(strm
, sourceLen
)
656 uLong complen
, wraplen
;
658 /* conservative upper bound for compressed data */
659 complen
= sourceLen
+
660 ((sourceLen
+ 7) >> 3) + ((sourceLen
+ 63) >> 6) + 5;
662 /* if can't get parameters, return conservative bound plus zlib wrapper */
663 if (deflateStateCheck(strm
))
666 /* compute wrapper length */
669 case 0: /* raw deflate */
672 case 1: /* zlib wrapper */
673 wraplen
= 6 + (s
->strstart
? 4 : 0);
676 case 2: /* gzip wrapper */
678 if (s
->gzhead
!= Z_NULL
) { /* user-supplied gzip header */
680 if (s
->gzhead
->extra
!= Z_NULL
)
681 wraplen
+= 2 + s
->gzhead
->extra_len
;
682 str
= s
->gzhead
->name
;
687 str
= s
->gzhead
->comment
;
697 default: /* for compiler happiness */
701 /* if not default parameters, return conservative bound */
702 if (s
->w_bits
!= 15 || s
->hash_bits
!= 8 + 7)
703 return complen
+ wraplen
;
705 /* default settings: return tight bound for that case */
706 return sourceLen
+ (sourceLen
>> 12) + (sourceLen
>> 14) +
707 (sourceLen
>> 25) + 13 - 6 + wraplen
;
710 /* =========================================================================
711 * Put a short in the pending buffer. The 16-bit value is put in MSB order.
712 * IN assertion: the stream state is correct and there is enough room in
715 local
void putShortMSB (s
, b
)
719 put_byte(s
, (Byte
)(b
>> 8));
720 put_byte(s
, (Byte
)(b
& 0xff));
723 /* =========================================================================
724 * Flush as much pending output as possible. All deflate() output, except for
725 * some deflate_stored() output, goes through this function so some
726 * applications may wish to modify it to avoid allocating a large
727 * strm->next_out buffer and copying into it. (See also read_buf()).
729 local
void flush_pending(strm
)
733 deflate_state
*s
= strm
->state
;
737 if (len
> strm
->avail_out
) len
= strm
->avail_out
;
738 if (len
== 0) return;
740 zmemcpy(strm
->next_out
, s
->pending_out
, len
);
741 strm
->next_out
+= len
;
742 s
->pending_out
+= len
;
743 strm
->total_out
+= len
;
744 strm
->avail_out
-= len
;
746 if (s
->pending
== 0) {
747 s
->pending_out
= s
->pending_buf
;
751 /* ===========================================================================
752 * Update the header CRC with the bytes s->pending_buf[beg..s->pending - 1].
754 #define HCRC_UPDATE(beg) \
756 if (s->gzhead->hcrc && s->pending > (beg)) \
757 strm->adler = crc32(strm->adler, s->pending_buf + (beg), \
758 s->pending - (beg)); \
761 /* ========================================================================= */
762 int ZEXPORT
deflate (strm
, flush
)
766 int old_flush
; /* value of flush param for previous deflate call */
769 if (deflateStateCheck(strm
) || flush
> Z_BLOCK
|| flush
< 0) {
770 return Z_STREAM_ERROR
;
774 if (strm
->next_out
== Z_NULL
||
775 (strm
->avail_in
!= 0 && strm
->next_in
== Z_NULL
) ||
776 (s
->status
== FINISH_STATE
&& flush
!= Z_FINISH
)) {
777 ERR_RETURN(strm
, Z_STREAM_ERROR
);
779 if (strm
->avail_out
== 0) ERR_RETURN(strm
, Z_BUF_ERROR
);
781 old_flush
= s
->last_flush
;
782 s
->last_flush
= flush
;
784 /* Flush as much pending output as possible */
785 if (s
->pending
!= 0) {
787 if (strm
->avail_out
== 0) {
788 /* Since avail_out is 0, deflate will be called again with
789 * more output space, but possibly with both pending and
790 * avail_in equal to zero. There won't be anything to do,
791 * but this is not an error situation so make sure we
792 * return OK instead of BUF_ERROR at next call of deflate:
798 /* Make sure there is something to do and avoid duplicate consecutive
799 * flushes. For repeated and useless calls with Z_FINISH, we keep
800 * returning Z_STREAM_END instead of Z_BUF_ERROR.
802 } else if (strm
->avail_in
== 0 && RANK(flush
) <= RANK(old_flush
) &&
804 ERR_RETURN(strm
, Z_BUF_ERROR
);
807 /* User must not provide more input after the first FINISH: */
808 if (s
->status
== FINISH_STATE
&& strm
->avail_in
!= 0) {
809 ERR_RETURN(strm
, Z_BUF_ERROR
);
812 /* Write the header */
813 if (s
->status
== INIT_STATE
) {
815 uInt header
= (Z_DEFLATED
+ ((s
->w_bits
-8)<<4)) << 8;
818 if (s
->strategy
>= Z_HUFFMAN_ONLY
|| s
->level
< 2)
820 else if (s
->level
< 6)
822 else if (s
->level
== 6)
826 header
|= (level_flags
<< 6);
827 if (s
->strstart
!= 0) header
|= PRESET_DICT
;
828 header
+= 31 - (header
% 31);
830 putShortMSB(s
, header
);
832 /* Save the adler32 of the preset dictionary: */
833 if (s
->strstart
!= 0) {
834 putShortMSB(s
, (uInt
)(strm
->adler
>> 16));
835 putShortMSB(s
, (uInt
)(strm
->adler
& 0xffff));
837 strm
->adler
= adler32(0L, Z_NULL
, 0);
838 s
->status
= BUSY_STATE
;
840 /* Compression must start with an empty pending buffer */
842 if (s
->pending
!= 0) {
848 if (s
->status
== GZIP_STATE
) {
850 strm
->adler
= crc32(0L, Z_NULL
, 0);
854 if (s
->gzhead
== Z_NULL
) {
860 put_byte(s
, s
->level
== 9 ? 2 :
861 (s
->strategy
>= Z_HUFFMAN_ONLY
|| s
->level
< 2 ?
863 put_byte(s
, OS_CODE
);
864 s
->status
= BUSY_STATE
;
866 /* Compression must start with an empty pending buffer */
868 if (s
->pending
!= 0) {
874 put_byte(s
, (s
->gzhead
->text
? 1 : 0) +
875 (s
->gzhead
->hcrc
? 2 : 0) +
876 (s
->gzhead
->extra
== Z_NULL
? 0 : 4) +
877 (s
->gzhead
->name
== Z_NULL
? 0 : 8) +
878 (s
->gzhead
->comment
== Z_NULL
? 0 : 16)
880 put_byte(s
, (Byte
)(s
->gzhead
->time
& 0xff));
881 put_byte(s
, (Byte
)((s
->gzhead
->time
>> 8) & 0xff));
882 put_byte(s
, (Byte
)((s
->gzhead
->time
>> 16) & 0xff));
883 put_byte(s
, (Byte
)((s
->gzhead
->time
>> 24) & 0xff));
884 put_byte(s
, s
->level
== 9 ? 2 :
885 (s
->strategy
>= Z_HUFFMAN_ONLY
|| s
->level
< 2 ?
887 put_byte(s
, s
->gzhead
->os
& 0xff);
888 if (s
->gzhead
->extra
!= Z_NULL
) {
889 put_byte(s
, s
->gzhead
->extra_len
& 0xff);
890 put_byte(s
, (s
->gzhead
->extra_len
>> 8) & 0xff);
893 strm
->adler
= crc32(strm
->adler
, s
->pending_buf
,
896 s
->status
= EXTRA_STATE
;
899 if (s
->status
== EXTRA_STATE
) {
900 if (s
->gzhead
->extra
!= Z_NULL
) {
901 ulg beg
= s
->pending
; /* start of bytes to update crc */
902 uInt left
= (s
->gzhead
->extra_len
& 0xffff) - s
->gzindex
;
903 while (s
->pending
+ left
> s
->pending_buf_size
) {
904 uInt copy
= s
->pending_buf_size
- s
->pending
;
905 zmemcpy(s
->pending_buf
+ s
->pending
,
906 s
->gzhead
->extra
+ s
->gzindex
, copy
);
907 s
->pending
= s
->pending_buf_size
;
911 if (s
->pending
!= 0) {
918 zmemcpy(s
->pending_buf
+ s
->pending
,
919 s
->gzhead
->extra
+ s
->gzindex
, left
);
924 s
->status
= NAME_STATE
;
926 if (s
->status
== NAME_STATE
) {
927 if (s
->gzhead
->name
!= Z_NULL
) {
928 ulg beg
= s
->pending
; /* start of bytes to update crc */
931 if (s
->pending
== s
->pending_buf_size
) {
934 if (s
->pending
!= 0) {
940 val
= s
->gzhead
->name
[s
->gzindex
++];
946 s
->status
= COMMENT_STATE
;
948 if (s
->status
== COMMENT_STATE
) {
949 if (s
->gzhead
->comment
!= Z_NULL
) {
950 ulg beg
= s
->pending
; /* start of bytes to update crc */
953 if (s
->pending
== s
->pending_buf_size
) {
956 if (s
->pending
!= 0) {
962 val
= s
->gzhead
->comment
[s
->gzindex
++];
967 s
->status
= HCRC_STATE
;
969 if (s
->status
== HCRC_STATE
) {
970 if (s
->gzhead
->hcrc
) {
971 if (s
->pending
+ 2 > s
->pending_buf_size
) {
973 if (s
->pending
!= 0) {
978 put_byte(s
, (Byte
)(strm
->adler
& 0xff));
979 put_byte(s
, (Byte
)((strm
->adler
>> 8) & 0xff));
980 strm
->adler
= crc32(0L, Z_NULL
, 0);
982 s
->status
= BUSY_STATE
;
984 /* Compression must start with an empty pending buffer */
986 if (s
->pending
!= 0) {
993 /* Start a new block or continue the current one.
995 if (strm
->avail_in
!= 0 || s
->lookahead
!= 0 ||
996 (flush
!= Z_NO_FLUSH
&& s
->status
!= FINISH_STATE
)) {
999 bstate
= s
->level
== 0 ? deflate_stored(s
, flush
) :
1000 s
->strategy
== Z_HUFFMAN_ONLY
? deflate_huff(s
, flush
) :
1001 s
->strategy
== Z_RLE
? deflate_rle(s
, flush
) :
1002 (*(configuration_table
[s
->level
].func
))(s
, flush
);
1004 if (bstate
== finish_started
|| bstate
== finish_done
) {
1005 s
->status
= FINISH_STATE
;
1007 if (bstate
== need_more
|| bstate
== finish_started
) {
1008 if (strm
->avail_out
== 0) {
1009 s
->last_flush
= -1; /* avoid BUF_ERROR next call, see above */
1012 /* If flush != Z_NO_FLUSH && avail_out == 0, the next call
1013 * of deflate should use the same flush parameter to make sure
1014 * that the flush is complete. So we don't have to output an
1015 * empty block here, this will be done at next call. This also
1016 * ensures that for a very small output buffer, we emit at most
1020 if (bstate
== block_done
) {
1021 if (flush
== Z_PARTIAL_FLUSH
) {
1023 } else if (flush
!= Z_BLOCK
) { /* FULL_FLUSH or SYNC_FLUSH */
1024 _tr_stored_block(s
, (char*)0, 0L, 0);
1025 /* For a full flush, this empty block will be recognized
1026 * as a special marker by inflate_sync().
1028 if (flush
== Z_FULL_FLUSH
) {
1029 CLEAR_HASH(s
); /* forget history */
1030 if (s
->lookahead
== 0) {
1032 s
->block_start
= 0L;
1037 flush_pending(strm
);
1038 if (strm
->avail_out
== 0) {
1039 s
->last_flush
= -1; /* avoid BUF_ERROR at next call, see above */
1045 if (flush
!= Z_FINISH
) return Z_OK
;
1046 if (s
->wrap
<= 0) return Z_STREAM_END
;
1048 /* Write the trailer */
1051 put_byte(s
, (Byte
)(strm
->adler
& 0xff));
1052 put_byte(s
, (Byte
)((strm
->adler
>> 8) & 0xff));
1053 put_byte(s
, (Byte
)((strm
->adler
>> 16) & 0xff));
1054 put_byte(s
, (Byte
)((strm
->adler
>> 24) & 0xff));
1055 put_byte(s
, (Byte
)(strm
->total_in
& 0xff));
1056 put_byte(s
, (Byte
)((strm
->total_in
>> 8) & 0xff));
1057 put_byte(s
, (Byte
)((strm
->total_in
>> 16) & 0xff));
1058 put_byte(s
, (Byte
)((strm
->total_in
>> 24) & 0xff));
1063 putShortMSB(s
, (uInt
)(strm
->adler
>> 16));
1064 putShortMSB(s
, (uInt
)(strm
->adler
& 0xffff));
1066 flush_pending(strm
);
1067 /* If avail_out is zero, the application will call deflate again
1068 * to flush the rest.
1070 if (s
->wrap
> 0) s
->wrap
= -s
->wrap
; /* write the trailer only once! */
1071 return s
->pending
!= 0 ? Z_OK
: Z_STREAM_END
;
1074 /* ========================================================================= */
1075 int ZEXPORT
deflateEnd (strm
)
1080 if (deflateStateCheck(strm
)) return Z_STREAM_ERROR
;
1082 status
= strm
->state
->status
;
1084 /* Deallocate in reverse order of allocations: */
1085 TRY_FREE(strm
, strm
->state
->pending_buf
);
1086 TRY_FREE(strm
, strm
->state
->head
);
1087 TRY_FREE(strm
, strm
->state
->prev
);
1088 TRY_FREE(strm
, strm
->state
->window
);
1090 ZFREE(strm
, strm
->state
);
1091 strm
->state
= Z_NULL
;
1093 return status
== BUSY_STATE
? Z_DATA_ERROR
: Z_OK
;
1096 /* =========================================================================
1097 * Copy the source state to the destination state.
1098 * To simplify the source, this is not supported for 16-bit MSDOS (which
1099 * doesn't have enough memory anyway to duplicate compression states).
1101 int ZEXPORT
deflateCopy (dest
, source
)
1106 return Z_STREAM_ERROR
;
1113 if (deflateStateCheck(source
) || dest
== Z_NULL
) {
1114 return Z_STREAM_ERROR
;
1119 zmemcpy((voidpf
)dest
, (voidpf
)source
, sizeof(z_stream
));
1121 ds
= (deflate_state
*) ZALLOC(dest
, 1, sizeof(deflate_state
));
1122 if (ds
== Z_NULL
) return Z_MEM_ERROR
;
1123 dest
->state
= (struct internal_state FAR
*) ds
;
1124 zmemcpy((voidpf
)ds
, (voidpf
)ss
, sizeof(deflate_state
));
1127 ds
->window
= (Bytef
*) ZALLOC(dest
, ds
->w_size
, 2*sizeof(Byte
));
1128 ds
->prev
= (Posf
*) ZALLOC(dest
, ds
->w_size
, sizeof(Pos
));
1129 ds
->head
= (Posf
*) ZALLOC(dest
, ds
->hash_size
, sizeof(Pos
));
1130 overlay
= (ushf
*) ZALLOC(dest
, ds
->lit_bufsize
, sizeof(ush
)+2);
1131 ds
->pending_buf
= (uchf
*) overlay
;
1133 if (ds
->window
== Z_NULL
|| ds
->prev
== Z_NULL
|| ds
->head
== Z_NULL
||
1134 ds
->pending_buf
== Z_NULL
) {
1138 /* following zmemcpy do not work for 16-bit MSDOS */
1139 zmemcpy(ds
->window
, ss
->window
, ds
->w_size
* 2 * sizeof(Byte
));
1140 zmemcpy((voidpf
)ds
->prev
, (voidpf
)ss
->prev
, ds
->w_size
* sizeof(Pos
));
1141 zmemcpy((voidpf
)ds
->head
, (voidpf
)ss
->head
, ds
->hash_size
* sizeof(Pos
));
1142 zmemcpy(ds
->pending_buf
, ss
->pending_buf
, (uInt
)ds
->pending_buf_size
);
1144 ds
->pending_out
= ds
->pending_buf
+ (ss
->pending_out
- ss
->pending_buf
);
1145 ds
->d_buf
= overlay
+ ds
->lit_bufsize
/sizeof(ush
);
1146 ds
->l_buf
= ds
->pending_buf
+ (1+sizeof(ush
))*ds
->lit_bufsize
;
1148 ds
->l_desc
.dyn_tree
= ds
->dyn_ltree
;
1149 ds
->d_desc
.dyn_tree
= ds
->dyn_dtree
;
1150 ds
->bl_desc
.dyn_tree
= ds
->bl_tree
;
1153 #endif /* MAXSEG_64K */
1156 /* ===========================================================================
1157 * Read a new buffer from the current input stream, update the adler32
1158 * and total number of bytes read. All deflate() input goes through
1159 * this function so some applications may wish to modify it to avoid
1160 * allocating a large strm->next_in buffer and copying from it.
1161 * (See also flush_pending()).
1163 local
unsigned read_buf(strm
, buf
, size
)
1168 unsigned len
= strm
->avail_in
;
1170 if (len
> size
) len
= size
;
1171 if (len
== 0) return 0;
1173 strm
->avail_in
-= len
;
1175 zmemcpy(buf
, strm
->next_in
, len
);
1176 if (strm
->state
->wrap
== 1) {
1177 strm
->adler
= adler32(strm
->adler
, buf
, len
);
1180 else if (strm
->state
->wrap
== 2) {
1181 strm
->adler
= crc32(strm
->adler
, buf
, len
);
1184 strm
->next_in
+= len
;
1185 strm
->total_in
+= len
;
1190 /* ===========================================================================
1191 * Initialize the "longest match" routines for a new zlib stream
1193 local
void lm_init (s
)
1196 s
->window_size
= (ulg
)2L*s
->w_size
;
1200 /* Set the default configuration parameters:
1202 s
->max_lazy_match
= configuration_table
[s
->level
].max_lazy
;
1203 s
->good_match
= configuration_table
[s
->level
].good_length
;
1204 s
->nice_match
= configuration_table
[s
->level
].nice_length
;
1205 s
->max_chain_length
= configuration_table
[s
->level
].max_chain
;
1208 s
->block_start
= 0L;
1211 s
->match_length
= s
->prev_length
= MIN_MATCH
-1;
1212 s
->match_available
= 0;
1216 match_init(); /* initialize the asm code */
1222 /* ===========================================================================
1223 * Set match_start to the longest match starting at the given string and
1224 * return its length. Matches shorter or equal to prev_length are discarded,
1225 * in which case the result is equal to prev_length and match_start is
1227 * IN assertions: cur_match is the head of the hash chain for the current
1228 * string (strstart) and its distance is <= MAX_DIST, and prev_length >= 1
1229 * OUT assertion: the match length is not greater than s->lookahead.
1232 /* For 80x86 and 680x0, an optimized version will be provided in match.asm or
1233 * match.S. The code will be functionally equivalent.
1235 local uInt
longest_match(s
, cur_match
)
1237 IPos cur_match
; /* current match */
1239 unsigned chain_length
= s
->max_chain_length
;/* max hash chain length */
1240 register Bytef
*scan
= s
->window
+ s
->strstart
; /* current string */
1241 register Bytef
*match
; /* matched string */
1242 register int len
; /* length of current match */
1243 int best_len
= (int)s
->prev_length
; /* best match length so far */
1244 int nice_match
= s
->nice_match
; /* stop if match long enough */
1245 IPos limit
= s
->strstart
> (IPos
)MAX_DIST(s
) ?
1246 s
->strstart
- (IPos
)MAX_DIST(s
) : NIL
;
1247 /* Stop when cur_match becomes <= limit. To simplify the code,
1248 * we prevent matches with the string of window index 0.
1250 Posf
*prev
= s
->prev
;
1251 uInt wmask
= s
->w_mask
;
1254 /* Compare two bytes at a time. Note: this is not always beneficial.
1255 * Try with and without -DUNALIGNED_OK to check.
1257 register Bytef
*strend
= s
->window
+ s
->strstart
+ MAX_MATCH
- 1;
1258 register ush scan_start
= *(ushf
*)scan
;
1259 register ush scan_end
= *(ushf
*)(scan
+best_len
-1);
1261 register Bytef
*strend
= s
->window
+ s
->strstart
+ MAX_MATCH
;
1262 register Byte scan_end1
= scan
[best_len
-1];
1263 register Byte scan_end
= scan
[best_len
];
1266 /* The code is optimized for HASH_BITS >= 8 and MAX_MATCH-2 multiple of 16.
1267 * It is easy to get rid of this optimization if necessary.
1269 Assert(s
->hash_bits
>= 8 && MAX_MATCH
== 258, "Code too clever");
1271 /* Do not waste too much time if we already have a good match: */
1272 if (s
->prev_length
>= s
->good_match
) {
1275 /* Do not look for matches beyond the end of the input. This is necessary
1276 * to make deflate deterministic.
1278 if ((uInt
)nice_match
> s
->lookahead
) nice_match
= (int)s
->lookahead
;
1280 Assert((ulg
)s
->strstart
<= s
->window_size
-MIN_LOOKAHEAD
, "need lookahead");
1283 Assert(cur_match
< s
->strstart
, "no future");
1284 match
= s
->window
+ cur_match
;
1286 /* Skip to next match if the match length cannot increase
1287 * or if the match length is less than 2. Note that the checks below
1288 * for insufficient lookahead only occur occasionally for performance
1289 * reasons. Therefore uninitialized memory will be accessed, and
1290 * conditional jumps will be made that depend on those values.
1291 * However the length of the match is limited to the lookahead, so
1292 * the output of deflate is not affected by the uninitialized values.
1294 #if (defined(UNALIGNED_OK) && MAX_MATCH == 258)
1295 /* This code assumes sizeof(unsigned short) == 2. Do not use
1296 * UNALIGNED_OK if your compiler uses a different size.
1298 if (*(ushf
*)(match
+best_len
-1) != scan_end
||
1299 *(ushf
*)match
!= scan_start
) continue;
1301 /* It is not necessary to compare scan[2] and match[2] since they are
1302 * always equal when the other bytes match, given that the hash keys
1303 * are equal and that HASH_BITS >= 8. Compare 2 bytes at a time at
1304 * strstart+3, +5, ... up to strstart+257. We check for insufficient
1305 * lookahead only every 4th comparison; the 128th check will be made
1306 * at strstart+257. If MAX_MATCH-2 is not a multiple of 8, it is
1307 * necessary to put more guard bytes at the end of the window, or
1308 * to check more often for insufficient lookahead.
1310 Assert(scan
[2] == match
[2], "scan[2]?");
1313 } while (*(ushf
*)(scan
+=2) == *(ushf
*)(match
+=2) &&
1314 *(ushf
*)(scan
+=2) == *(ushf
*)(match
+=2) &&
1315 *(ushf
*)(scan
+=2) == *(ushf
*)(match
+=2) &&
1316 *(ushf
*)(scan
+=2) == *(ushf
*)(match
+=2) &&
1318 /* The funny "do {}" generates better code on most compilers */
1320 /* Here, scan <= window+strstart+257 */
1321 Assert(scan
<= s
->window
+(unsigned)(s
->window_size
-1), "wild scan");
1322 if (*scan
== *match
) scan
++;
1324 len
= (MAX_MATCH
- 1) - (int)(strend
-scan
);
1325 scan
= strend
- (MAX_MATCH
-1);
1327 #else /* UNALIGNED_OK */
1329 if (match
[best_len
] != scan_end
||
1330 match
[best_len
-1] != scan_end1
||
1332 *++match
!= scan
[1]) continue;
1334 /* The check at best_len-1 can be removed because it will be made
1335 * again later. (This heuristic is not always a win.)
1336 * It is not necessary to compare scan[2] and match[2] since they
1337 * are always equal when the other bytes match, given that
1338 * the hash keys are equal and that HASH_BITS >= 8.
1341 Assert(*scan
== *match
, "match[2]?");
1343 /* We check for insufficient lookahead only every 8th comparison;
1344 * the 256th check will be made at strstart+258.
1347 } while (*++scan
== *++match
&& *++scan
== *++match
&&
1348 *++scan
== *++match
&& *++scan
== *++match
&&
1349 *++scan
== *++match
&& *++scan
== *++match
&&
1350 *++scan
== *++match
&& *++scan
== *++match
&&
1353 Assert(scan
<= s
->window
+(unsigned)(s
->window_size
-1), "wild scan");
1355 len
= MAX_MATCH
- (int)(strend
- scan
);
1356 scan
= strend
- MAX_MATCH
;
1358 #endif /* UNALIGNED_OK */
1360 if (len
> best_len
) {
1361 s
->match_start
= cur_match
;
1363 if (len
>= nice_match
) break;
1365 scan_end
= *(ushf
*)(scan
+best_len
-1);
1367 scan_end1
= scan
[best_len
-1];
1368 scan_end
= scan
[best_len
];
1371 } while ((cur_match
= prev
[cur_match
& wmask
]) > limit
1372 && --chain_length
!= 0);
1374 if ((uInt
)best_len
<= s
->lookahead
) return (uInt
)best_len
;
1375 return s
->lookahead
;
1381 /* ---------------------------------------------------------------------------
1382 * Optimized version for FASTEST only
1384 local uInt
longest_match(s
, cur_match
)
1386 IPos cur_match
; /* current match */
1388 register Bytef
*scan
= s
->window
+ s
->strstart
; /* current string */
1389 register Bytef
*match
; /* matched string */
1390 register int len
; /* length of current match */
1391 register Bytef
*strend
= s
->window
+ s
->strstart
+ MAX_MATCH
;
1393 /* The code is optimized for HASH_BITS >= 8 and MAX_MATCH-2 multiple of 16.
1394 * It is easy to get rid of this optimization if necessary.
1396 Assert(s
->hash_bits
>= 8 && MAX_MATCH
== 258, "Code too clever");
1398 Assert((ulg
)s
->strstart
<= s
->window_size
-MIN_LOOKAHEAD
, "need lookahead");
1400 Assert(cur_match
< s
->strstart
, "no future");
1402 match
= s
->window
+ cur_match
;
1404 /* Return failure if the match length is less than 2:
1406 if (match
[0] != scan
[0] || match
[1] != scan
[1]) return MIN_MATCH
-1;
1408 /* The check at best_len-1 can be removed because it will be made
1409 * again later. (This heuristic is not always a win.)
1410 * It is not necessary to compare scan[2] and match[2] since they
1411 * are always equal when the other bytes match, given that
1412 * the hash keys are equal and that HASH_BITS >= 8.
1414 scan
+= 2, match
+= 2;
1415 Assert(*scan
== *match
, "match[2]?");
1417 /* We check for insufficient lookahead only every 8th comparison;
1418 * the 256th check will be made at strstart+258.
1421 } while (*++scan
== *++match
&& *++scan
== *++match
&&
1422 *++scan
== *++match
&& *++scan
== *++match
&&
1423 *++scan
== *++match
&& *++scan
== *++match
&&
1424 *++scan
== *++match
&& *++scan
== *++match
&&
1427 Assert(scan
<= s
->window
+(unsigned)(s
->window_size
-1), "wild scan");
1429 len
= MAX_MATCH
- (int)(strend
- scan
);
1431 if (len
< MIN_MATCH
) return MIN_MATCH
- 1;
1433 s
->match_start
= cur_match
;
1434 return (uInt
)len
<= s
->lookahead
? (uInt
)len
: s
->lookahead
;
1437 #endif /* FASTEST */
1442 /* result of memcmp for equal strings */
1444 /* ===========================================================================
1445 * Check that the match at match_start is indeed a match.
1447 local
void check_match(s
, start
, match
, length
)
1452 /* check that the match is indeed a match */
1453 if (zmemcmp(s
->window
+ match
,
1454 s
->window
+ start
, length
) != EQUAL
) {
1455 fprintf(stderr
, " start %u, match %u, length %d\n",
1456 start
, match
, length
);
1458 fprintf(stderr
, "%c%c", s
->window
[match
++], s
->window
[start
++]);
1459 } while (--length
!= 0);
1460 z_error("invalid match");
1462 if (z_verbose
> 1) {
1463 fprintf(stderr
,"\\[%d,%d]", start
-match
, length
);
1464 do { putc(s
->window
[start
++], stderr
); } while (--length
!= 0);
1468 # define check_match(s, start, match, length)
1469 #endif /* ZLIB_DEBUG */
1471 /* ===========================================================================
1472 * Fill the window when the lookahead becomes insufficient.
1473 * Updates strstart and lookahead.
1475 * IN assertion: lookahead < MIN_LOOKAHEAD
1476 * OUT assertions: strstart <= window_size-MIN_LOOKAHEAD
1477 * At least one byte has been read, or avail_in == 0; reads are
1478 * performed for at least two bytes (required for the zip translate_eol
1479 * option -- not supported here).
1481 local
void fill_window(s
)
1485 unsigned more
; /* Amount of free space at the end of the window. */
1486 uInt wsize
= s
->w_size
;
1488 Assert(s
->lookahead
< MIN_LOOKAHEAD
, "already enough lookahead");
1491 more
= (unsigned)(s
->window_size
-(ulg
)s
->lookahead
-(ulg
)s
->strstart
);
1493 /* Deal with !@#$% 64K limit: */
1494 if (sizeof(int) <= 2) {
1495 if (more
== 0 && s
->strstart
== 0 && s
->lookahead
== 0) {
1498 } else if (more
== (unsigned)(-1)) {
1499 /* Very unlikely, but possible on 16 bit machine if
1500 * strstart == 0 && lookahead == 1 (input done a byte at time)
1506 /* If the window is almost full and there is insufficient lookahead,
1507 * move the upper half to the lower one to make room in the upper half.
1509 if (s
->strstart
>= wsize
+MAX_DIST(s
)) {
1511 zmemcpy(s
->window
, s
->window
+wsize
, (unsigned)wsize
- more
);
1512 s
->match_start
-= wsize
;
1513 s
->strstart
-= wsize
; /* we now have strstart >= MAX_DIST */
1514 s
->block_start
-= (long) wsize
;
1518 if (s
->strm
->avail_in
== 0) break;
1520 /* If there was no sliding:
1521 * strstart <= WSIZE+MAX_DIST-1 && lookahead <= MIN_LOOKAHEAD - 1 &&
1522 * more == window_size - lookahead - strstart
1523 * => more >= window_size - (MIN_LOOKAHEAD-1 + WSIZE + MAX_DIST-1)
1524 * => more >= window_size - 2*WSIZE + 2
1525 * In the BIG_MEM or MMAP case (not yet supported),
1526 * window_size == input_size + MIN_LOOKAHEAD &&
1527 * strstart + s->lookahead <= input_size => more >= MIN_LOOKAHEAD.
1528 * Otherwise, window_size == 2*WSIZE so more >= 2.
1529 * If there was sliding, more >= WSIZE. So in all cases, more >= 2.
1531 Assert(more
>= 2, "more < 2");
1533 n
= read_buf(s
->strm
, s
->window
+ s
->strstart
+ s
->lookahead
, more
);
1536 /* Initialize the hash value now that we have some input: */
1537 if (s
->lookahead
+ s
->insert
>= MIN_MATCH
) {
1538 uInt str
= s
->strstart
- s
->insert
;
1539 s
->ins_h
= s
->window
[str
];
1540 UPDATE_HASH(s
, s
->ins_h
, s
->window
[str
+ 1]);
1542 Call
UPDATE_HASH() MIN_MATCH
-3 more times
1545 UPDATE_HASH(s
, s
->ins_h
, s
->window
[str
+ MIN_MATCH
-1]);
1547 s
->prev
[str
& s
->w_mask
] = s
->head
[s
->ins_h
];
1549 s
->head
[s
->ins_h
] = (Pos
)str
;
1552 if (s
->lookahead
+ s
->insert
< MIN_MATCH
)
1556 /* If the whole input has less than MIN_MATCH bytes, ins_h is garbage,
1557 * but this is not important since only literal bytes will be emitted.
1560 } while (s
->lookahead
< MIN_LOOKAHEAD
&& s
->strm
->avail_in
!= 0);
1562 /* If the WIN_INIT bytes after the end of the current data have never been
1563 * written, then zero those bytes in order to avoid memory check reports of
1564 * the use of uninitialized (or uninitialised as Julian writes) bytes by
1565 * the longest match routines. Update the high water mark for the next
1566 * time through here. WIN_INIT is set to MAX_MATCH since the longest match
1567 * routines allow scanning to strstart + MAX_MATCH, ignoring lookahead.
1569 if (s
->high_water
< s
->window_size
) {
1570 ulg curr
= s
->strstart
+ (ulg
)(s
->lookahead
);
1573 if (s
->high_water
< curr
) {
1574 /* Previous high water mark below current data -- zero WIN_INIT
1575 * bytes or up to end of window, whichever is less.
1577 init
= s
->window_size
- curr
;
1578 if (init
> WIN_INIT
)
1580 zmemzero(s
->window
+ curr
, (unsigned)init
);
1581 s
->high_water
= curr
+ init
;
1583 else if (s
->high_water
< (ulg
)curr
+ WIN_INIT
) {
1584 /* High water mark at or above current data, but below current data
1585 * plus WIN_INIT -- zero out to current data plus WIN_INIT, or up
1586 * to end of window, whichever is less.
1588 init
= (ulg
)curr
+ WIN_INIT
- s
->high_water
;
1589 if (init
> s
->window_size
- s
->high_water
)
1590 init
= s
->window_size
- s
->high_water
;
1591 zmemzero(s
->window
+ s
->high_water
, (unsigned)init
);
1592 s
->high_water
+= init
;
1596 Assert((ulg
)s
->strstart
<= s
->window_size
- MIN_LOOKAHEAD
,
1597 "not enough room for search");
1600 /* ===========================================================================
1601 * Flush the current block, with given end-of-file flag.
1602 * IN assertion: strstart is set to the end of the current match.
1604 #define FLUSH_BLOCK_ONLY(s, last) { \
1605 _tr_flush_block(s, (s->block_start >= 0L ? \
1606 (charf *)&s->window[(unsigned)s->block_start] : \
1608 (ulg)((long)s->strstart - s->block_start), \
1610 s->block_start = s->strstart; \
1611 flush_pending(s->strm); \
1612 Tracev((stderr,"[FLUSH]")); \
1615 /* Same but force premature exit if necessary. */
1616 #define FLUSH_BLOCK(s, last) { \
1617 FLUSH_BLOCK_ONLY(s, last); \
1618 if (s->strm->avail_out == 0) return (last) ? finish_started : need_more; \
1621 /* Maximum stored block length in deflate format (not including header). */
1622 #define MAX_STORED 65535
1624 /* Minimum of a and b. */
1625 #define MIN(a, b) ((a) > (b) ? (b) : (a))
1627 /* ===========================================================================
1628 * Copy without compression as much as possible from the input stream, return
1629 * the current block state.
1631 * In case deflateParams() is used to later switch to a non-zero compression
1632 * level, s->matches (otherwise unused when storing) keeps track of the number
1633 * of hash table slides to perform. If s->matches is 1, then one hash table
1634 * slide will be done when switching. If s->matches is 2, the maximum value
1635 * allowed here, then the hash table will be cleared, since two or more slides
1636 * is the same as a clear.
1638 * deflate_stored() is written to minimize the number of times an input byte is
1639 * copied. It is most efficient with large input and output buffers, which
1640 * maximizes the opportunites to have a single copy from next_in to next_out.
1642 local block_state
deflate_stored(s
, flush
)
1646 /* Smallest worthy block size when not flushing or finishing. By default
1647 * this is 32K. This can be as small as 507 bytes for memLevel == 1. For
1648 * large input and output buffers, the stored block size will be larger.
1650 unsigned min_block
= MIN(s
->pending_buf_size
- 5, s
->w_size
);
1652 /* Copy as many min_block or larger stored blocks directly to next_out as
1653 * possible. If flushing, copy the remaining available input to next_out as
1654 * stored blocks, if there is enough space.
1656 unsigned len
, left
, have
, last
= 0;
1657 unsigned used
= s
->strm
->avail_in
;
1659 /* Set len to the maximum size block that we can copy directly with the
1660 * available input data and output space. Set left to how much of that
1661 * would be copied from what's left in the window.
1663 len
= MAX_STORED
; /* maximum deflate stored block length */
1664 have
= (s
->bi_valid
+ 42) >> 3; /* number of header bytes */
1665 if (s
->strm
->avail_out
< have
) /* need room for header */
1667 /* maximum stored block length that will fit in avail_out: */
1668 have
= s
->strm
->avail_out
- have
;
1669 left
= s
->strstart
- s
->block_start
; /* bytes left in window */
1670 if (len
> (ulg
)left
+ s
->strm
->avail_in
)
1671 len
= left
+ s
->strm
->avail_in
; /* limit len to the input */
1673 len
= have
; /* limit len to the output */
1675 left
= len
; /* limit window pull to len */
1677 /* If the stored block would be less than min_block in length, or if
1678 * unable to copy all of the available input when flushing, then try
1679 * copying to the window and the pending buffer instead. Also don't
1680 * write an empty block when flushing -- deflate() does that.
1682 if (len
< min_block
&& ((len
== 0 && flush
!= Z_FINISH
) ||
1683 flush
== Z_NO_FLUSH
||
1684 len
- left
!= s
->strm
->avail_in
))
1687 /* Make a dummy stored block in pending to get the header bytes,
1688 * including any pending bits. This also updates the debugging counts.
1690 last
= flush
== Z_FINISH
&& len
- left
== s
->strm
->avail_in
? 1 : 0;
1691 _tr_stored_block(s
, (char *)0, 0L, last
);
1693 /* Replace the lengths in the dummy stored block with len. */
1694 s
->pending_buf
[s
->pending
- 4] = len
;
1695 s
->pending_buf
[s
->pending
- 3] = len
>> 8;
1696 s
->pending_buf
[s
->pending
- 2] = ~len
;
1697 s
->pending_buf
[s
->pending
- 1] = ~len
>> 8;
1699 /* Write the stored block header bytes. */
1700 flush_pending(s
->strm
);
1702 /* Update debugging counts for the data about to be copied. */
1704 s
->compressed_len
+= len
<< 3;
1705 s
->bits_sent
+= len
<< 3;
1708 /* Copy uncompressed bytes from the window to next_out. */
1710 zmemcpy(s
->strm
->next_out
, s
->window
+ s
->block_start
, left
);
1711 s
->strm
->next_out
+= left
;
1712 s
->strm
->avail_out
-= left
;
1713 s
->strm
->total_out
+= left
;
1714 s
->block_start
+= left
;
1718 /* Copy uncompressed bytes directly from next_in to next_out, updating
1722 read_buf(s
->strm
, s
->strm
->next_out
, len
);
1723 s
->strm
->next_out
+= len
;
1724 s
->strm
->avail_out
-= len
;
1725 s
->strm
->total_out
+= len
;
1727 } while (last
== 0);
1729 /* Update the sliding window with the last s->w_size bytes of the copied
1730 * data, or append all of the copied data to the existing window if less
1731 * than s->w_size bytes were copied. Also update the number of bytes to
1732 * insert in the hash tables, in the event that deflateParams() switches to
1733 * a non-zero compression level.
1735 used
-= s
->strm
->avail_in
; /* number of input bytes directly copied */
1737 /* If any input was used, then no unused input remains in the window,
1738 * therefore s->block_start == s->strstart.
1740 if (used
>= s
->w_size
) { /* supplant the previous history */
1741 s
->matches
= 2; /* clear hash */
1742 zmemcpy(s
->window
, s
->strm
->next_in
- s
->w_size
, s
->w_size
);
1743 s
->strstart
= s
->w_size
;
1746 if (s
->window_size
- s
->strstart
<= used
) {
1747 /* Slide the window down. */
1748 s
->strstart
-= s
->w_size
;
1749 zmemcpy(s
->window
, s
->window
+ s
->w_size
, s
->strstart
);
1751 s
->matches
++; /* add a pending slide_hash() */
1753 zmemcpy(s
->window
+ s
->strstart
, s
->strm
->next_in
- used
, used
);
1754 s
->strstart
+= used
;
1756 s
->block_start
= s
->strstart
;
1757 s
->insert
+= MIN(used
, s
->w_size
- s
->insert
);
1760 /* If the last block was written to next_out, then done. */
1764 /* If flushing and all input has been consumed, then done. */
1765 if (flush
!= Z_NO_FLUSH
&& flush
!= Z_FINISH
&&
1766 s
->strm
->avail_in
== 0 && (long)s
->strstart
== s
->block_start
)
1769 /* Fill the window with any remaining input. */
1770 have
= s
->window_size
- s
->strstart
- 1;
1771 if (s
->strm
->avail_in
> have
&& s
->block_start
>= (long)s
->w_size
) {
1772 /* Slide the window down. */
1773 s
->block_start
-= s
->w_size
;
1774 s
->strstart
-= s
->w_size
;
1775 zmemcpy(s
->window
, s
->window
+ s
->w_size
, s
->strstart
);
1777 s
->matches
++; /* add a pending slide_hash() */
1778 have
+= s
->w_size
; /* more space now */
1780 if (have
> s
->strm
->avail_in
)
1781 have
= s
->strm
->avail_in
;
1783 read_buf(s
->strm
, s
->window
+ s
->strstart
, have
);
1784 s
->strstart
+= have
;
1787 /* There was not enough avail_out to write a complete worthy or flushed
1788 * stored block to next_out. Write a stored block to pending instead, if we
1789 * have enough input for a worthy block, or if flushing and there is enough
1790 * room for the remaining input as a stored block in the pending buffer.
1792 have
= (s
->bi_valid
+ 42) >> 3; /* number of header bytes */
1793 /* maximum stored block length that will fit in pending: */
1794 have
= MIN(s
->pending_buf_size
- have
, MAX_STORED
);
1795 min_block
= MIN(have
, s
->w_size
);
1796 left
= s
->strstart
- s
->block_start
;
1797 if (left
>= min_block
||
1798 ((left
|| flush
== Z_FINISH
) && flush
!= Z_NO_FLUSH
&&
1799 s
->strm
->avail_in
== 0 && left
<= have
)) {
1800 len
= MIN(left
, have
);
1801 last
= flush
== Z_FINISH
&& s
->strm
->avail_in
== 0 &&
1802 len
== left
? 1 : 0;
1803 _tr_stored_block(s
, (charf
*)s
->window
+ s
->block_start
, len
, last
);
1804 s
->block_start
+= len
;
1805 flush_pending(s
->strm
);
1808 /* We've done all we can with the available input and output. */
1809 return last
? finish_started
: need_more
;
1812 /* ===========================================================================
1813 * Compress as much as possible from the input stream, return the current
1815 * This function does not perform lazy evaluation of matches and inserts
1816 * new strings in the dictionary only for unmatched strings or for short
1817 * matches. It is used only for the fast compression options.
1819 local block_state
deflate_fast(s
, flush
)
1823 IPos hash_head
; /* head of the hash chain */
1824 int bflush
; /* set if current block must be flushed */
1827 /* Make sure that we always have enough lookahead, except
1828 * at the end of the input file. We need MAX_MATCH bytes
1829 * for the next match, plus MIN_MATCH bytes to insert the
1830 * string following the next match.
1832 if (s
->lookahead
< MIN_LOOKAHEAD
) {
1834 if (s
->lookahead
< MIN_LOOKAHEAD
&& flush
== Z_NO_FLUSH
) {
1837 if (s
->lookahead
== 0) break; /* flush the current block */
1840 /* Insert the string window[strstart .. strstart+2] in the
1841 * dictionary, and set hash_head to the head of the hash chain:
1844 if (s
->lookahead
>= MIN_MATCH
) {
1845 INSERT_STRING(s
, s
->strstart
, hash_head
);
1848 /* Find the longest match, discarding those <= prev_length.
1849 * At this point we have always match_length < MIN_MATCH
1851 if (hash_head
!= NIL
&& s
->strstart
- hash_head
<= MAX_DIST(s
)) {
1852 /* To simplify the code, we prevent matches with the string
1853 * of window index 0 (in particular we have to avoid a match
1854 * of the string with itself at the start of the input file).
1856 s
->match_length
= longest_match (s
, hash_head
);
1857 /* longest_match() sets match_start */
1859 if (s
->match_length
>= MIN_MATCH
) {
1860 check_match(s
, s
->strstart
, s
->match_start
, s
->match_length
);
1862 _tr_tally_dist(s
, s
->strstart
- s
->match_start
,
1863 s
->match_length
- MIN_MATCH
, bflush
);
1865 s
->lookahead
-= s
->match_length
;
1867 /* Insert new strings in the hash table only if the match length
1868 * is not too large. This saves time but degrades compression.
1871 if (s
->match_length
<= s
->max_insert_length
&&
1872 s
->lookahead
>= MIN_MATCH
) {
1873 s
->match_length
--; /* string at strstart already in table */
1876 INSERT_STRING(s
, s
->strstart
, hash_head
);
1877 /* strstart never exceeds WSIZE-MAX_MATCH, so there are
1878 * always MIN_MATCH bytes ahead.
1880 } while (--s
->match_length
!= 0);
1885 s
->strstart
+= s
->match_length
;
1886 s
->match_length
= 0;
1887 s
->ins_h
= s
->window
[s
->strstart
];
1888 UPDATE_HASH(s
, s
->ins_h
, s
->window
[s
->strstart
+1]);
1890 Call
UPDATE_HASH() MIN_MATCH
-3 more times
1892 /* If lookahead < MIN_MATCH, ins_h is garbage, but it does not
1893 * matter since it will be recomputed at next deflate call.
1897 /* No match, output a literal byte */
1898 Tracevv((stderr
,"%c", s
->window
[s
->strstart
]));
1899 _tr_tally_lit (s
, s
->window
[s
->strstart
], bflush
);
1903 if (bflush
) FLUSH_BLOCK(s
, 0);
1905 s
->insert
= s
->strstart
< MIN_MATCH
-1 ? s
->strstart
: MIN_MATCH
-1;
1906 if (flush
== Z_FINISH
) {
1916 /* ===========================================================================
1917 * Same as above, but achieves better compression. We use a lazy
1918 * evaluation for matches: a match is finally adopted only if there is
1919 * no better match at the next window position.
1921 local block_state
deflate_slow(s
, flush
)
1925 IPos hash_head
; /* head of hash chain */
1926 int bflush
; /* set if current block must be flushed */
1928 /* Process the input block. */
1930 /* Make sure that we always have enough lookahead, except
1931 * at the end of the input file. We need MAX_MATCH bytes
1932 * for the next match, plus MIN_MATCH bytes to insert the
1933 * string following the next match.
1935 if (s
->lookahead
< MIN_LOOKAHEAD
) {
1937 if (s
->lookahead
< MIN_LOOKAHEAD
&& flush
== Z_NO_FLUSH
) {
1940 if (s
->lookahead
== 0) break; /* flush the current block */
1943 /* Insert the string window[strstart .. strstart+2] in the
1944 * dictionary, and set hash_head to the head of the hash chain:
1947 if (s
->lookahead
>= MIN_MATCH
) {
1948 INSERT_STRING(s
, s
->strstart
, hash_head
);
1951 /* Find the longest match, discarding those <= prev_length.
1953 s
->prev_length
= s
->match_length
, s
->prev_match
= s
->match_start
;
1954 s
->match_length
= MIN_MATCH
-1;
1956 if (hash_head
!= NIL
&& s
->prev_length
< s
->max_lazy_match
&&
1957 s
->strstart
- hash_head
<= MAX_DIST(s
)) {
1958 /* To simplify the code, we prevent matches with the string
1959 * of window index 0 (in particular we have to avoid a match
1960 * of the string with itself at the start of the input file).
1962 s
->match_length
= longest_match (s
, hash_head
);
1963 /* longest_match() sets match_start */
1965 if (s
->match_length
<= 5 && (s
->strategy
== Z_FILTERED
1966 #if TOO_FAR <= 32767
1967 || (s
->match_length
== MIN_MATCH
&&
1968 s
->strstart
- s
->match_start
> TOO_FAR
)
1972 /* If prev_match is also MIN_MATCH, match_start is garbage
1973 * but we will ignore the current match anyway.
1975 s
->match_length
= MIN_MATCH
-1;
1978 /* If there was a match at the previous step and the current
1979 * match is not better, output the previous match:
1981 if (s
->prev_length
>= MIN_MATCH
&& s
->match_length
<= s
->prev_length
) {
1982 uInt max_insert
= s
->strstart
+ s
->lookahead
- MIN_MATCH
;
1983 /* Do not insert strings in hash table beyond this. */
1985 check_match(s
, s
->strstart
-1, s
->prev_match
, s
->prev_length
);
1987 _tr_tally_dist(s
, s
->strstart
-1 - s
->prev_match
,
1988 s
->prev_length
- MIN_MATCH
, bflush
);
1990 /* Insert in hash table all strings up to the end of the match.
1991 * strstart-1 and strstart are already inserted. If there is not
1992 * enough lookahead, the last two strings are not inserted in
1995 s
->lookahead
-= s
->prev_length
-1;
1996 s
->prev_length
-= 2;
1998 if (++s
->strstart
<= max_insert
) {
1999 INSERT_STRING(s
, s
->strstart
, hash_head
);
2001 } while (--s
->prev_length
!= 0);
2002 s
->match_available
= 0;
2003 s
->match_length
= MIN_MATCH
-1;
2006 if (bflush
) FLUSH_BLOCK(s
, 0);
2008 } else if (s
->match_available
) {
2009 /* If there was no match at the previous position, output a
2010 * single literal. If there was a match but the current match
2011 * is longer, truncate the previous match to a single literal.
2013 Tracevv((stderr
,"%c", s
->window
[s
->strstart
-1]));
2014 _tr_tally_lit(s
, s
->window
[s
->strstart
-1], bflush
);
2016 FLUSH_BLOCK_ONLY(s
, 0);
2020 if (s
->strm
->avail_out
== 0) return need_more
;
2022 /* There is no previous match to compare with, wait for
2023 * the next step to decide.
2025 s
->match_available
= 1;
2030 Assert (flush
!= Z_NO_FLUSH
, "no flush?");
2031 if (s
->match_available
) {
2032 Tracevv((stderr
,"%c", s
->window
[s
->strstart
-1]));
2033 _tr_tally_lit(s
, s
->window
[s
->strstart
-1], bflush
);
2034 s
->match_available
= 0;
2036 s
->insert
= s
->strstart
< MIN_MATCH
-1 ? s
->strstart
: MIN_MATCH
-1;
2037 if (flush
== Z_FINISH
) {
2045 #endif /* FASTEST */
2047 /* ===========================================================================
2048 * For Z_RLE, simply look for runs of bytes, generate matches only of distance
2049 * one. Do not maintain a hash table. (It will be regenerated if this run of
2050 * deflate switches away from Z_RLE.)
2052 local block_state
deflate_rle(s
, flush
)
2056 int bflush
; /* set if current block must be flushed */
2057 uInt prev
; /* byte at distance one to match */
2058 Bytef
*scan
, *strend
; /* scan goes up to strend for length of run */
2061 /* Make sure that we always have enough lookahead, except
2062 * at the end of the input file. We need MAX_MATCH bytes
2063 * for the longest run, plus one for the unrolled loop.
2065 if (s
->lookahead
<= MAX_MATCH
) {
2067 if (s
->lookahead
<= MAX_MATCH
&& flush
== Z_NO_FLUSH
) {
2070 if (s
->lookahead
== 0) break; /* flush the current block */
2073 /* See how many times the previous byte repeats */
2074 s
->match_length
= 0;
2075 if (s
->lookahead
>= MIN_MATCH
&& s
->strstart
> 0) {
2076 scan
= s
->window
+ s
->strstart
- 1;
2078 if (prev
== *++scan
&& prev
== *++scan
&& prev
== *++scan
) {
2079 strend
= s
->window
+ s
->strstart
+ MAX_MATCH
;
2081 } while (prev
== *++scan
&& prev
== *++scan
&&
2082 prev
== *++scan
&& prev
== *++scan
&&
2083 prev
== *++scan
&& prev
== *++scan
&&
2084 prev
== *++scan
&& prev
== *++scan
&&
2086 s
->match_length
= MAX_MATCH
- (uInt
)(strend
- scan
);
2087 if (s
->match_length
> s
->lookahead
)
2088 s
->match_length
= s
->lookahead
;
2090 Assert(scan
<= s
->window
+(uInt
)(s
->window_size
-1), "wild scan");
2093 /* Emit match if have run of MIN_MATCH or longer, else emit literal */
2094 if (s
->match_length
>= MIN_MATCH
) {
2095 check_match(s
, s
->strstart
, s
->strstart
- 1, s
->match_length
);
2097 _tr_tally_dist(s
, 1, s
->match_length
- MIN_MATCH
, bflush
);
2099 s
->lookahead
-= s
->match_length
;
2100 s
->strstart
+= s
->match_length
;
2101 s
->match_length
= 0;
2103 /* No match, output a literal byte */
2104 Tracevv((stderr
,"%c", s
->window
[s
->strstart
]));
2105 _tr_tally_lit (s
, s
->window
[s
->strstart
], bflush
);
2109 if (bflush
) FLUSH_BLOCK(s
, 0);
2112 if (flush
== Z_FINISH
) {
2121 /* ===========================================================================
2122 * For Z_HUFFMAN_ONLY, do not look for matches. Do not maintain a hash table.
2123 * (It will be regenerated if this run of deflate switches away from Huffman.)
2125 local block_state
deflate_huff(s
, flush
)
2129 int bflush
; /* set if current block must be flushed */
2132 /* Make sure that we have a literal to write. */
2133 if (s
->lookahead
== 0) {
2135 if (s
->lookahead
== 0) {
2136 if (flush
== Z_NO_FLUSH
)
2138 break; /* flush the current block */
2142 /* Output a literal byte */
2143 s
->match_length
= 0;
2144 Tracevv((stderr
,"%c", s
->window
[s
->strstart
]));
2145 _tr_tally_lit (s
, s
->window
[s
->strstart
], bflush
);
2148 if (bflush
) FLUSH_BLOCK(s
, 0);
2151 if (flush
== Z_FINISH
) {