"Fossies" - the Fresh Open Source Software Archive 
Member "zsync-0.6.2/zlib/deflate.c" (16 Sep 2010, 54975 Bytes) of package /linux/privat/old/zsync-0.6.2.tar.gz:
As a special service "Fossies" has tried to format the requested source page into HTML format using (guessed) C and C++ source code syntax highlighting (style:
standard) with prefixed line numbers and
code folding option.
Alternatively you can here
view or
download the uninterpreted source code file.
For more information about "deflate.c" see the
Fossies "Dox" file reference documentation.
1 /* deflate.c -- compress data using the deflation algorithm
2 * Copyright (C) 1995-2003 Jean-loup Gailly.
3 * For conditions of distribution and use, see copyright notice in zlib.h
4 */
5
6 /*
7 * ALGORITHM
8 *
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).
12 *
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.
30 *
31 * ACKNOWLEDGEMENTS
32 *
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.
36 *
37 * REFERENCES
38 *
39 * Deutsch, L.P.,"DEFLATE Compressed Data Format Specification".
40 * Available in http://www.ietf.org/rfc/rfc1951.txt
41 *
42 * A description of the Rabin and Karp algorithm is given in the book
43 * "Algorithms" by R. Sedgewick, Addison-Wesley, p252.
44 *
45 * Fiala,E.R., and Greene,D.H.
46 * Data Compression with Finite Windows, Comm.ACM, 32,4 (1989) 490-595
47 *
48 */
49
50 /* @(#) $Id$ */
51
52 #include "deflate.h"
53
54 const char deflate_copyright[] =
55 " deflate 1.2.1.1 Copyright 1995-2003 Jean-loup Gailly ";
56 /*
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.
61 */
62
63 /* ===========================================================================
64 * Function prototypes.
65 */
66 typedef enum {
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 */
71 } block_state;
72
73 typedef block_state (*compress_func) OF((deflate_state *s, int flush));
74 /* Compression function. Returns the block state after the call. */
75
76 local void fill_window OF((deflate_state *s));
77 local block_state deflate_stored OF((deflate_state *s, int flush));
78 local block_state deflate_fast OF((deflate_state *s, int flush));
79 #ifndef FASTEST
80 local block_state deflate_slow OF((deflate_state *s, int flush));
81 #endif
82 local void lm_init OF((deflate_state *s));
83 local void putShortMSB OF((deflate_state *s, uInt b));
84 local void flush_pending OF((z_streamp strm));
85 local int read_buf OF((z_streamp strm, Bytef *buf, unsigned size));
86 #ifndef FASTEST
87 #ifdef ASMV
88 void match_init OF((void)); /* asm code initialization */
89 uInt longest_match OF((deflate_state *s, IPos cur_match));
90 #else
91 local uInt longest_match OF((deflate_state *s, IPos cur_match));
92 #endif
93 #endif
94 local uInt longest_match_fast OF((deflate_state *s, IPos cur_match));
95
96 #ifdef DEBUG
97 local void check_match OF((deflate_state *s, IPos start, IPos match,
98 int length));
99 #endif
100
101 /* ===========================================================================
102 * Local data
103 */
104
105 #define NIL 0
106 /* Tail of hash chains */
107
108 #ifndef TOO_FAR
109 # define TOO_FAR 4096
110 #endif
111 /* Matches of length 3 are discarded if their distance exceeds TOO_FAR */
112
113 #define MIN_LOOKAHEAD (MAX_MATCH+MIN_MATCH+1)
114 /* Minimum amount of lookahead, except at the end of the input file.
115 * See deflate.c for comments about the MIN_MATCH+1.
116 */
117
118 /* Values for max_lazy_match, good_match and max_chain_length, depending on
119 * the desired pack level (0..9). The values given below have been tuned to
120 * exclude worst case performance for pathological files. Better values may be
121 * found for specific files.
122 */
123 typedef struct config_s {
124 ush good_length; /* reduce lazy search above this match length */
125 ush max_lazy; /* do not perform lazy search above this match length */
126 ush nice_length; /* quit search above this match length */
127 ush max_chain;
128 compress_func func;
129 } config;
130
131 #ifdef FASTEST
132 local const config configuration_table[2] = {
133 /* good lazy nice chain */
134 /* 0 */ {0, 0, 0, 0, deflate_stored}, /* store only */
135 /* 1 */ {4, 4, 8, 4, deflate_fast}}; /* max speed, no lazy matches */
136 #else
137 local const config configuration_table[10] = {
138 /* good lazy nice chain */
139 /* 0 */ {0, 0, 0, 0, deflate_stored}, /* store only */
140 /* 1 */ {4, 4, 8, 4, deflate_fast}, /* max speed, no lazy matches */
141 /* 2 */ {4, 5, 16, 8, deflate_fast},
142 /* 3 */ {4, 6, 32, 32, deflate_fast},
143
144 /* 4 */ {4, 4, 16, 16, deflate_slow}, /* lazy matches */
145 /* 5 */ {8, 16, 32, 32, deflate_slow},
146 /* 6 */ {8, 16, 128, 128, deflate_slow},
147 /* 7 */ {8, 32, 128, 256, deflate_slow},
148 /* 8 */ {32, 128, 258, 1024, deflate_slow},
149 /* 9 */ {32, 258, 258, 4096, deflate_slow}}; /* max compression */
150 #endif
151
152 /* Note: the deflate() code requires max_lazy >= MIN_MATCH and max_chain >= 4
153 * For deflate_fast() (levels <= 3) good is ignored and lazy has a different
154 * meaning.
155 */
156
157 #define EQUAL 0
158 /* result of memcmp for equal strings */
159
160 #ifndef NO_DUMMY_DECL
161 struct static_tree_desc_s {int dummy;}; /* for buggy compilers */
162 #endif
163
164 /* ===========================================================================
165 * Update a hash value with the given input byte
166 * IN assertion: all calls to to UPDATE_HASH are made with consecutive
167 * input characters, so that a running hash key can be computed from the
168 * previous key instead of complete recalculation each time.
169 */
170 #define UPDATE_HASH(s,h,c) (h = (((h)<<s->hash_shift) ^ (c)) & s->hash_mask)
171
172
173 /* ===========================================================================
174 * Insert string str in the dictionary and set match_head to the previous head
175 * of the hash chain (the most recent string with same hash key). Return
176 * the previous length of the hash chain.
177 * If this file is compiled with -DFASTEST, the compression level is forced
178 * to 1, and no hash chains are maintained.
179 * IN assertion: all calls to to INSERT_STRING are made with consecutive
180 * input characters and the first MIN_MATCH bytes of str are valid
181 * (except for the last MIN_MATCH-1 bytes of the input file).
182 */
183 #ifdef FASTEST
184 #define INSERT_STRING(s, str, match_head) \
185 (UPDATE_HASH(s, s->ins_h, s->window[(str) + (MIN_MATCH-1)]), \
186 match_head = s->head[s->ins_h], \
187 s->head[s->ins_h] = (Pos)(str))
188 #else
189 #define INSERT_STRING(s, str, match_head) \
190 (UPDATE_HASH(s, s->ins_h, s->window[(str) + (MIN_MATCH-1)]), \
191 match_head = s->prev[(str) & s->w_mask] = s->head[s->ins_h], \
192 s->head[s->ins_h] = (Pos)(str))
193 #endif
194
195 /* ===========================================================================
196 * Initialize the hash table (avoiding 64K overflow for 16 bit systems).
197 * prev[] will be initialized on the fly.
198 */
199 #define CLEAR_HASH(s) \
200 s->head[s->hash_size-1] = NIL; \
201 zmemzero((Bytef *)s->head, (unsigned)(s->hash_size-1)*sizeof(*s->head));
202
203 /* ========================================================================= */
204 int ZEXPORT deflateInit_(strm, level, version, stream_size)
205 z_streamp strm;
206 int level;
207 const char *version;
208 int stream_size;
209 {
210 return deflateInit2_(strm, level, Z_DEFLATED, MAX_WBITS, DEF_MEM_LEVEL,
211 Z_DEFAULT_STRATEGY, version, stream_size);
212 /* To do: ignore strm->next_in if we use it as window */
213 }
214
215 /* ========================================================================= */
216 int ZEXPORT deflateInit2_(strm, level, method, windowBits, memLevel, strategy,
217 version, stream_size)
218 z_streamp strm;
219 int level;
220 int method;
221 int windowBits;
222 int memLevel;
223 int strategy;
224 const char *version;
225 int stream_size;
226 {
227 deflate_state *s;
228 int wrap = 1;
229 static const char my_version[] = ZLIB_VERSION;
230
231 ushf *overlay;
232 /* We overlay pending_buf and d_buf+l_buf. This works since the average
233 * output size for (length,distance) codes is <= 24 bits.
234 */
235
236 if (version == Z_NULL || version[0] != my_version[0] ||
237 stream_size != sizeof(z_stream)) {
238 return Z_VERSION_ERROR;
239 }
240 if (strm == Z_NULL) return Z_STREAM_ERROR;
241
242 strm->msg = Z_NULL;
243 if (strm->zalloc == (alloc_func)0) {
244 strm->zalloc = zcalloc;
245 strm->opaque = (voidpf)0;
246 }
247 if (strm->zfree == (free_func)0) strm->zfree = zcfree;
248
249 #ifdef FASTEST
250 if (level != 0) level = 1;
251 #else
252 if (level == Z_DEFAULT_COMPRESSION) level = 6;
253 #endif
254
255 if (windowBits < 0) { /* suppress zlib wrapper */
256 wrap = 0;
257 windowBits = -windowBits;
258 }
259 #ifdef GZIP
260 else if (windowBits > 15) {
261 wrap = 2; /* write gzip wrapper instead */
262 windowBits -= 16;
263 }
264 #endif
265 if (memLevel < 1 || memLevel > MAX_MEM_LEVEL || method != Z_DEFLATED ||
266 windowBits < 8 || windowBits > 15 || level < 0 || level > 9 ||
267 strategy < 0 || strategy > Z_RLE) {
268 return Z_STREAM_ERROR;
269 }
270 if (windowBits == 8) windowBits = 9; /* until 256-byte window bug fixed */
271 s = (deflate_state *) ZALLOC(strm, 1, sizeof(deflate_state));
272 if (s == Z_NULL) return Z_MEM_ERROR;
273 strm->state = (struct internal_state FAR *)s;
274 s->strm = strm;
275
276 s->wrap = wrap;
277 s->w_bits = windowBits;
278 s->w_size = 1 << s->w_bits;
279 s->w_mask = s->w_size - 1;
280
281 s->hash_bits = memLevel + 7;
282 s->hash_size = 1 << s->hash_bits;
283 s->hash_mask = s->hash_size - 1;
284 s->hash_shift = ((s->hash_bits+MIN_MATCH-1)/MIN_MATCH);
285
286 s->window = (Bytef *) ZALLOC(strm, s->w_size, 2*sizeof(Byte));
287 s->prev = (Posf *) ZALLOC(strm, s->w_size, sizeof(Pos));
288 s->head = (Posf *) ZALLOC(strm, s->hash_size, sizeof(Pos));
289
290 s->lit_bufsize = 1 << (memLevel + 6); /* 16K elements by default */
291
292 overlay = (ushf *) ZALLOC(strm, s->lit_bufsize, sizeof(ush)+2);
293 s->pending_buf = (uchf *) overlay;
294 s->pending_buf_size = (ulg)s->lit_bufsize * (sizeof(ush)+2L);
295
296 if (s->window == Z_NULL || s->prev == Z_NULL || s->head == Z_NULL ||
297 s->pending_buf == Z_NULL) {
298 s->status = FINISH_STATE;
299 strm->msg = (char*)ERR_MSG(Z_MEM_ERROR);
300 deflateEnd (strm);
301 return Z_MEM_ERROR;
302 }
303 s->d_buf = overlay + s->lit_bufsize/sizeof(ush);
304 s->l_buf = s->pending_buf + (1+sizeof(ush))*s->lit_bufsize;
305
306 s->level = level;
307 s->strategy = strategy;
308 s->method = (Byte)method;
309
310 return deflateReset(strm);
311 }
312
313 /* ========================================================================= */
314 int ZEXPORT deflateSetDictionary (strm, dictionary, dictLength)
315 z_streamp strm;
316 const Bytef *dictionary;
317 uInt dictLength;
318 {
319 deflate_state *s;
320 uInt length = dictLength;
321 uInt n;
322 IPos hash_head = 0;
323
324 if (strm == Z_NULL || strm->state == Z_NULL || dictionary == Z_NULL ||
325 strm->state->wrap == 2 ||
326 (strm->state->wrap == 1 && strm->state->status != INIT_STATE))
327 return Z_STREAM_ERROR;
328
329 s = strm->state;
330 if (s->wrap)
331 strm->adler = adler32(strm->adler, dictionary, dictLength);
332
333 if (length < MIN_MATCH) return Z_OK;
334 if (length > MAX_DIST(s)) {
335 length = MAX_DIST(s);
336 #ifndef USE_DICT_HEAD
337 dictionary += dictLength - length; /* use the tail of the dictionary */
338 #endif
339 }
340 zmemcpy(s->window, dictionary, length);
341 s->strstart = length;
342 s->block_start = (long)length;
343
344 /* Insert all strings in the hash table (except for the last two bytes).
345 * s->lookahead stays null, so s->ins_h will be recomputed at the next
346 * call of fill_window.
347 */
348 s->ins_h = s->window[0];
349 UPDATE_HASH(s, s->ins_h, s->window[1]);
350 for (n = 0; n <= length - MIN_MATCH; n++) {
351 INSERT_STRING(s, n, hash_head);
352 }
353 if (hash_head) hash_head = 0; /* to make compiler happy */
354 return Z_OK;
355 }
356
357 /* ========================================================================= */
358 int ZEXPORT deflateReset (strm)
359 z_streamp strm;
360 {
361 deflate_state *s;
362
363 if (strm == Z_NULL || strm->state == Z_NULL ||
364 strm->zalloc == (alloc_func)0 || strm->zfree == (free_func)0) {
365 return Z_STREAM_ERROR;
366 }
367
368 strm->total_in = strm->total_out = 0;
369 strm->msg = Z_NULL; /* use zfree if we ever allocate msg dynamically */
370 strm->data_type = Z_UNKNOWN;
371
372 s = (deflate_state *)strm->state;
373 s->pending = 0;
374 s->pending_out = s->pending_buf;
375
376 if (s->wrap < 0) {
377 s->wrap = -s->wrap; /* was made negative by deflate(..., Z_FINISH); */
378 }
379 s->status = s->wrap ? INIT_STATE : BUSY_STATE;
380 strm->adler =
381 #ifdef GZIP
382 s->wrap == 2 ? crc32(0L, Z_NULL, 0) :
383 #endif
384 adler32(0L, Z_NULL, 0);
385 s->last_flush = Z_NO_FLUSH;
386
387 _tr_init(s);
388 lm_init(s);
389
390 return Z_OK;
391 }
392
393 /* ========================================================================= */
394 int ZEXPORT deflatePrime (strm, bits, value)
395 z_streamp strm;
396 int bits;
397 int value;
398 {
399 if (strm == Z_NULL || strm->state == Z_NULL) return Z_STREAM_ERROR;
400 strm->state->bi_valid = bits;
401 strm->state->bi_buf = (ush)(value & ((1 << bits) - 1));
402 return Z_OK;
403 }
404
405 /* ========================================================================= */
406 int ZEXPORT deflateParams(strm, level, strategy)
407 z_streamp strm;
408 int level;
409 int strategy;
410 {
411 deflate_state *s;
412 compress_func func;
413 int err = Z_OK;
414
415 if (strm == Z_NULL || strm->state == Z_NULL) return Z_STREAM_ERROR;
416 s = strm->state;
417
418 #ifdef FASTEST
419 if (level != 0) level = 1;
420 #else
421 if (level == Z_DEFAULT_COMPRESSION) level = 6;
422 #endif
423 if (level < 0 || level > 9 || strategy < 0 || strategy > Z_RLE) {
424 return Z_STREAM_ERROR;
425 }
426 func = configuration_table[s->level].func;
427
428 if (func != configuration_table[level].func && strm->total_in != 0) {
429 /* Flush the last buffer: */
430 err = deflate(strm, Z_PARTIAL_FLUSH);
431 }
432 if (s->level != level) {
433 s->level = level;
434 s->max_lazy_match = configuration_table[level].max_lazy;
435 s->good_match = configuration_table[level].good_length;
436 s->nice_match = configuration_table[level].nice_length;
437 s->max_chain_length = configuration_table[level].max_chain;
438 }
439 s->strategy = strategy;
440 return err;
441 }
442
443 /* =========================================================================
444 * For the default windowBits of 15 and memLevel of 8, this function returns
445 * a close to exact, as well as small, upper bound on the compressed size.
446 * They are coded as constants here for a reason--if the #define's are
447 * changed, then this function needs to be changed as well. The return
448 * value for 15 and 8 only works for those exact settings.
449 *
450 * For any setting other than those defaults for windowBits and memLevel,
451 * the value returned is a conservative worst case for the maximum expansion
452 * resulting from using fixed blocks instead of stored blocks, which deflate
453 * can emit on compressed data for some combinations of the parameters.
454 *
455 * This function could be more sophisticated to provide closer upper bounds
456 * for every combination of windowBits and memLevel, as well as wrap.
457 * But even the conservative upper bound of about 14% expansion does not
458 * seem onerous for output buffer allocation.
459 */
460 uLong ZEXPORT deflateBound(strm, sourceLen)
461 z_streamp strm;
462 uLong sourceLen;
463 {
464 deflate_state *s;
465 uLong destLen;
466
467 /* conservative upper bound */
468 destLen = sourceLen +
469 ((sourceLen + 7) >> 3) + ((sourceLen + 63) >> 6) + 11;
470
471 /* if can't get parameters, return conservative bound */
472 if (strm == Z_NULL || strm->state == Z_NULL)
473 return destLen;
474
475 /* if not default parameters, return conservative bound */
476 s = strm->state;
477 if (s->w_bits != 15 || s->hash_bits != 8 + 7)
478 return destLen;
479
480 /* default settings: return tight bound for that case */
481 return compressBound(sourceLen);
482 }
483
484 /* =========================================================================
485 * Put a short in the pending buffer. The 16-bit value is put in MSB order.
486 * IN assertion: the stream state is correct and there is enough room in
487 * pending_buf.
488 */
489 local void putShortMSB (s, b)
490 deflate_state *s;
491 uInt b;
492 {
493 put_byte(s, (Byte)(b >> 8));
494 put_byte(s, (Byte)(b & 0xff));
495 }
496
497 /* =========================================================================
498 * Flush as much pending output as possible. All deflate() output goes
499 * through this function so some applications may wish to modify it
500 * to avoid allocating a large strm->next_out buffer and copying into it.
501 * (See also read_buf()).
502 */
503 local void flush_pending(strm)
504 z_streamp strm;
505 {
506 unsigned len = strm->state->pending;
507
508 if (len > strm->avail_out) len = strm->avail_out;
509 if (len == 0) return;
510
511 zmemcpy(strm->next_out, strm->state->pending_out, len);
512 strm->next_out += len;
513 strm->state->pending_out += len;
514 strm->total_out += len;
515 strm->avail_out -= len;
516 strm->state->pending -= len;
517 if (strm->state->pending == 0) {
518 strm->state->pending_out = strm->state->pending_buf;
519 }
520 }
521
522 /* ========================================================================= */
523 int ZEXPORT deflate (strm, flush)
524 z_streamp strm;
525 int flush;
526 {
527 int old_flush; /* value of flush param for previous deflate call */
528 deflate_state *s;
529
530 if (strm == Z_NULL || strm->state == Z_NULL ||
531 flush > Z_FINISH || flush < 0) {
532 return Z_STREAM_ERROR;
533 }
534 s = strm->state;
535
536 if (strm->next_out == Z_NULL ||
537 (strm->next_in == Z_NULL && strm->avail_in != 0) ||
538 (s->status == FINISH_STATE && flush != Z_FINISH)) {
539 ERR_RETURN(strm, Z_STREAM_ERROR);
540 }
541 if (strm->avail_out == 0) ERR_RETURN(strm, Z_BUF_ERROR);
542
543 s->strm = strm; /* just in case */
544 old_flush = s->last_flush;
545 s->last_flush = flush;
546
547 /* Write the header */
548 if (s->status == INIT_STATE) {
549 #ifdef GZIP
550 if (s->wrap == 2) {
551 put_byte(s, 31);
552 put_byte(s, 139);
553 put_byte(s, 8);
554 put_byte(s, 0);
555 put_byte(s, 0);
556 put_byte(s, 0);
557 put_byte(s, 0);
558 put_byte(s, 0);
559 put_byte(s, s->level == 9 ? 2 :
560 (s->strategy >= Z_HUFFMAN_ONLY || s->level < 2 ?
561 4 : 0));
562 put_byte(s, 255);
563 s->status = BUSY_STATE;
564 strm->adler = crc32(0L, Z_NULL, 0);
565 }
566 else
567 #endif
568 {
569 uInt header = (Z_DEFLATED + ((s->w_bits-8)<<4)) << 8;
570 uInt level_flags;
571
572 if (s->strategy >= Z_HUFFMAN_ONLY || s->level < 2)
573 level_flags = 0;
574 else if (s->level < 6)
575 level_flags = 1;
576 else if (s->level == 6)
577 level_flags = 2;
578 else
579 level_flags = 3;
580 header |= (level_flags << 6);
581 if (s->strstart != 0) header |= PRESET_DICT;
582 header += 31 - (header % 31);
583
584 s->status = BUSY_STATE;
585 putShortMSB(s, header);
586
587 /* Save the adler32 of the preset dictionary: */
588 if (s->strstart != 0) {
589 putShortMSB(s, (uInt)(strm->adler >> 16));
590 putShortMSB(s, (uInt)(strm->adler & 0xffff));
591 }
592 strm->adler = adler32(0L, Z_NULL, 0);
593 }
594 }
595
596 /* Flush as much pending output as possible */
597 if (s->pending != 0) {
598 flush_pending(strm);
599 if (strm->avail_out == 0) {
600 /* Since avail_out is 0, deflate will be called again with
601 * more output space, but possibly with both pending and
602 * avail_in equal to zero. There won't be anything to do,
603 * but this is not an error situation so make sure we
604 * return OK instead of BUF_ERROR at next call of deflate:
605 */
606 s->last_flush = -1;
607 return Z_OK;
608 }
609
610 /* Make sure there is something to do and avoid duplicate consecutive
611 * flushes. For repeated and useless calls with Z_FINISH, we keep
612 * returning Z_STREAM_END instead of Z_BUF_ERROR.
613 */
614 } else if (strm->avail_in == 0 && flush <= old_flush &&
615 flush != Z_FINISH) {
616 ERR_RETURN(strm, Z_BUF_ERROR);
617 }
618
619 /* User must not provide more input after the first FINISH: */
620 if (s->status == FINISH_STATE && strm->avail_in != 0) {
621 ERR_RETURN(strm, Z_BUF_ERROR);
622 }
623
624 /* Start a new block or continue the current one.
625 */
626 if (strm->avail_in != 0 || s->lookahead != 0 ||
627 (flush != Z_NO_FLUSH && s->status != FINISH_STATE)) {
628 block_state bstate;
629
630 bstate = (*(configuration_table[s->level].func))(s, flush);
631
632 if (bstate == finish_started || bstate == finish_done) {
633 s->status = FINISH_STATE;
634 }
635 if (bstate == need_more || bstate == finish_started) {
636 if (strm->avail_out == 0) {
637 s->last_flush = -1; /* avoid BUF_ERROR next call, see above */
638 }
639 return Z_OK;
640 /* If flush != Z_NO_FLUSH && avail_out == 0, the next call
641 * of deflate should use the same flush parameter to make sure
642 * that the flush is complete. So we don't have to output an
643 * empty block here, this will be done at next call. This also
644 * ensures that for a very small output buffer, we emit at most
645 * one empty block.
646 */
647 }
648 if (bstate == block_done) {
649 if (flush == Z_PARTIAL_FLUSH) {
650 // _tr_align(s);
651 } else { /* FULL_FLUSH or SYNC_FLUSH */
652 _tr_stored_block(s, (char*)0, 0L, 0);
653 /* For a full flush, this empty block will be recognized
654 * as a special marker by inflate_sync().
655 */
656 if (flush == Z_FULL_FLUSH) {
657 CLEAR_HASH(s); /* forget history */
658 }
659 }
660 flush_pending(strm);
661 if (strm->avail_out == 0) {
662 s->last_flush = -1; /* avoid BUF_ERROR at next call, see above */
663 return Z_OK;
664 }
665 }
666 }
667 Assert(strm->avail_out > 0, "bug2");
668
669 if (flush != Z_FINISH) return Z_OK;
670 if (s->wrap <= 0) return Z_STREAM_END;
671
672 /* Write the trailer */
673 #ifdef GZIP
674 if (s->wrap == 2) {
675 put_byte(s, (Byte)(strm->adler & 0xff));
676 put_byte(s, (Byte)((strm->adler >> 8) & 0xff));
677 put_byte(s, (Byte)((strm->adler >> 16) & 0xff));
678 put_byte(s, (Byte)((strm->adler >> 24) & 0xff));
679 put_byte(s, (Byte)(strm->total_in & 0xff));
680 put_byte(s, (Byte)((strm->total_in >> 8) & 0xff));
681 put_byte(s, (Byte)((strm->total_in >> 16) & 0xff));
682 put_byte(s, (Byte)((strm->total_in >> 24) & 0xff));
683 }
684 else
685 #endif
686 {
687 putShortMSB(s, (uInt)(strm->adler >> 16));
688 putShortMSB(s, (uInt)(strm->adler & 0xffff));
689 }
690 flush_pending(strm);
691 /* If avail_out is zero, the application will call deflate again
692 * to flush the rest.
693 */
694 if (s->wrap > 0) s->wrap = -s->wrap; /* write the trailer only once! */
695 return s->pending != 0 ? Z_OK : Z_STREAM_END;
696 }
697
698 /* ========================================================================= */
699 int ZEXPORT deflateEnd (strm)
700 z_streamp strm;
701 {
702 int status;
703
704 if (strm == Z_NULL || strm->state == Z_NULL) return Z_STREAM_ERROR;
705
706 status = strm->state->status;
707 if (status != INIT_STATE && status != BUSY_STATE &&
708 status != FINISH_STATE) {
709 return Z_STREAM_ERROR;
710 }
711
712 /* Deallocate in reverse order of allocations: */
713 TRY_FREE(strm, strm->state->pending_buf);
714 TRY_FREE(strm, strm->state->head);
715 TRY_FREE(strm, strm->state->prev);
716 TRY_FREE(strm, strm->state->window);
717
718 ZFREE(strm, strm->state);
719 strm->state = Z_NULL;
720
721 return status == BUSY_STATE ? Z_DATA_ERROR : Z_OK;
722 }
723
724 /* =========================================================================
725 * Copy the source state to the destination state.
726 * To simplify the source, this is not supported for 16-bit MSDOS (which
727 * doesn't have enough memory anyway to duplicate compression states).
728 */
729 int ZEXPORT deflateCopy (dest, source)
730 z_streamp dest;
731 z_streamp source;
732 {
733 #ifdef MAXSEG_64K
734 return Z_STREAM_ERROR;
735 #else
736 deflate_state *ds;
737 deflate_state *ss;
738 ushf *overlay;
739
740
741 if (source == Z_NULL || dest == Z_NULL || source->state == Z_NULL) {
742 return Z_STREAM_ERROR;
743 }
744
745 ss = source->state;
746
747 *dest = *source;
748
749 ds = (deflate_state *) ZALLOC(dest, 1, sizeof(deflate_state));
750 if (ds == Z_NULL) return Z_MEM_ERROR;
751 dest->state = (struct internal_state FAR *) ds;
752 *ds = *ss;
753 ds->strm = dest;
754
755 ds->window = (Bytef *) ZALLOC(dest, ds->w_size, 2*sizeof(Byte));
756 ds->prev = (Posf *) ZALLOC(dest, ds->w_size, sizeof(Pos));
757 ds->head = (Posf *) ZALLOC(dest, ds->hash_size, sizeof(Pos));
758 overlay = (ushf *) ZALLOC(dest, ds->lit_bufsize, sizeof(ush)+2);
759 ds->pending_buf = (uchf *) overlay;
760
761 if (ds->window == Z_NULL || ds->prev == Z_NULL || ds->head == Z_NULL ||
762 ds->pending_buf == Z_NULL) {
763 deflateEnd (dest);
764 return Z_MEM_ERROR;
765 }
766 /* following zmemcpy do not work for 16-bit MSDOS */
767 zmemcpy(ds->window, ss->window, ds->w_size * 2 * sizeof(Byte));
768 zmemcpy(ds->prev, ss->prev, ds->w_size * sizeof(Pos));
769 zmemcpy(ds->head, ss->head, ds->hash_size * sizeof(Pos));
770 zmemcpy(ds->pending_buf, ss->pending_buf, (uInt)ds->pending_buf_size);
771
772 ds->pending_out = ds->pending_buf + (ss->pending_out - ss->pending_buf);
773 ds->d_buf = overlay + ds->lit_bufsize/sizeof(ush);
774 ds->l_buf = ds->pending_buf + (1+sizeof(ush))*ds->lit_bufsize;
775
776 ds->l_desc.dyn_tree = ds->dyn_ltree;
777 ds->d_desc.dyn_tree = ds->dyn_dtree;
778 ds->bl_desc.dyn_tree = ds->bl_tree;
779
780 return Z_OK;
781 #endif /* MAXSEG_64K */
782 }
783
784 /* ===========================================================================
785 * Read a new buffer from the current input stream, update the adler32
786 * and total number of bytes read. All deflate() input goes through
787 * this function so some applications may wish to modify it to avoid
788 * allocating a large strm->next_in buffer and copying from it.
789 * (See also flush_pending()).
790 */
791 local int read_buf(strm, buf, size)
792 z_streamp strm;
793 Bytef *buf;
794 unsigned size;
795 {
796 unsigned len = strm->avail_in;
797
798 if (len > size) len = size;
799 if (len == 0) return 0;
800
801 strm->avail_in -= len;
802
803 if (strm->state->wrap == 1) {
804 strm->adler = adler32(strm->adler, strm->next_in, len);
805 }
806 #ifdef GZIP
807 else if (strm->state->wrap == 2) {
808 strm->adler = crc32(strm->adler, strm->next_in, len);
809 }
810 #endif
811 zmemcpy(buf, strm->next_in, len);
812 strm->next_in += len;
813 strm->total_in += len;
814
815 return (int)len;
816 }
817
818 /* ===========================================================================
819 * Initialize the "longest match" routines for a new zlib stream
820 */
821 local void lm_init (s)
822 deflate_state *s;
823 {
824 s->window_size = (ulg)2L*s->w_size;
825
826 CLEAR_HASH(s);
827
828 /* Set the default configuration parameters:
829 */
830 s->max_lazy_match = configuration_table[s->level].max_lazy;
831 s->good_match = configuration_table[s->level].good_length;
832 s->nice_match = configuration_table[s->level].nice_length;
833 s->max_chain_length = configuration_table[s->level].max_chain;
834
835 s->strstart = 0;
836 s->block_start = 0L;
837 s->lookahead = 0;
838 s->match_length = s->prev_length = MIN_MATCH-1;
839 s->match_available = 0;
840 s->ins_h = 0;
841 #ifdef ASMV
842 match_init(); /* initialize the asm code */
843 #endif
844 }
845
846 #ifndef FASTEST
847 /* ===========================================================================
848 * Set match_start to the longest match starting at the given string and
849 * return its length. Matches shorter or equal to prev_length are discarded,
850 * in which case the result is equal to prev_length and match_start is
851 * garbage.
852 * IN assertions: cur_match is the head of the hash chain for the current
853 * string (strstart) and its distance is <= MAX_DIST, and prev_length >= 1
854 * OUT assertion: the match length is not greater than s->lookahead.
855 */
856 #ifndef ASMV
857 /* For 80x86 and 680x0, an optimized version will be provided in match.asm or
858 * match.S. The code will be functionally equivalent.
859 */
860 local uInt longest_match(s, cur_match)
861 deflate_state *s;
862 IPos cur_match; /* current match */
863 {
864 unsigned chain_length = s->max_chain_length;/* max hash chain length */
865 register Bytef *scan = s->window + s->strstart; /* current string */
866 register Bytef *match; /* matched string */
867 register int len; /* length of current match */
868 int best_len = s->prev_length; /* best match length so far */
869 int nice_match = s->nice_match; /* stop if match long enough */
870 IPos limit = s->strstart > (IPos)MAX_DIST(s) ?
871 s->strstart - (IPos)MAX_DIST(s) : NIL;
872 /* Stop when cur_match becomes <= limit. To simplify the code,
873 * we prevent matches with the string of window index 0.
874 */
875 Posf *prev = s->prev;
876 uInt wmask = s->w_mask;
877
878 #ifdef UNALIGNED_OK
879 /* Compare two bytes at a time. Note: this is not always beneficial.
880 * Try with and without -DUNALIGNED_OK to check.
881 */
882 register Bytef *strend = s->window + s->strstart + MAX_MATCH - 1;
883 register ush scan_start = *(ushf*)scan;
884 register ush scan_end = *(ushf*)(scan+best_len-1);
885 #else
886 register Bytef *strend = s->window + s->strstart + MAX_MATCH;
887 register Byte scan_end1 = scan[best_len-1];
888 register Byte scan_end = scan[best_len];
889 #endif
890
891 /* The code is optimized for HASH_BITS >= 8 and MAX_MATCH-2 multiple of 16.
892 * It is easy to get rid of this optimization if necessary.
893 */
894 Assert(s->hash_bits >= 8 && MAX_MATCH == 258, "Code too clever");
895
896 /* Do not waste too much time if we already have a good match: */
897 if (s->prev_length >= s->good_match) {
898 chain_length >>= 2;
899 }
900 /* Do not look for matches beyond the end of the input. This is necessary
901 * to make deflate deterministic.
902 */
903 if ((uInt)nice_match > s->lookahead) nice_match = s->lookahead;
904
905 Assert((ulg)s->strstart <= s->window_size-MIN_LOOKAHEAD, "need lookahead");
906
907 do {
908 Assert(cur_match < s->strstart, "no future");
909 match = s->window + cur_match;
910
911 /* Skip to next match if the match length cannot increase
912 * or if the match length is less than 2:
913 */
914 #if (defined(UNALIGNED_OK) && MAX_MATCH == 258)
915 /* This code assumes sizeof(unsigned short) == 2. Do not use
916 * UNALIGNED_OK if your compiler uses a different size.
917 */
918 if (*(ushf*)(match+best_len-1) != scan_end ||
919 *(ushf*)match != scan_start) continue;
920
921 /* It is not necessary to compare scan[2] and match[2] since they are
922 * always equal when the other bytes match, given that the hash keys
923 * are equal and that HASH_BITS >= 8. Compare 2 bytes at a time at
924 * strstart+3, +5, ... up to strstart+257. We check for insufficient
925 * lookahead only every 4th comparison; the 128th check will be made
926 * at strstart+257. If MAX_MATCH-2 is not a multiple of 8, it is
927 * necessary to put more guard bytes at the end of the window, or
928 * to check more often for insufficient lookahead.
929 */
930 Assert(scan[2] == match[2], "scan[2]?");
931 scan++, match++;
932 do {
933 } while (*(ushf*)(scan+=2) == *(ushf*)(match+=2) &&
934 *(ushf*)(scan+=2) == *(ushf*)(match+=2) &&
935 *(ushf*)(scan+=2) == *(ushf*)(match+=2) &&
936 *(ushf*)(scan+=2) == *(ushf*)(match+=2) &&
937 scan < strend);
938 /* The funny "do {}" generates better code on most compilers */
939
940 /* Here, scan <= window+strstart+257 */
941 Assert(scan <= s->window+(unsigned)(s->window_size-1), "wild scan");
942 if (*scan == *match) scan++;
943
944 len = (MAX_MATCH - 1) - (int)(strend-scan);
945 scan = strend - (MAX_MATCH-1);
946
947 #else /* UNALIGNED_OK */
948
949 if (match[best_len] != scan_end ||
950 match[best_len-1] != scan_end1 ||
951 *match != *scan ||
952 *++match != scan[1]) continue;
953
954 /* The check at best_len-1 can be removed because it will be made
955 * again later. (This heuristic is not always a win.)
956 * It is not necessary to compare scan[2] and match[2] since they
957 * are always equal when the other bytes match, given that
958 * the hash keys are equal and that HASH_BITS >= 8.
959 */
960 scan += 2, match++;
961 Assert(*scan == *match, "match[2]?");
962
963 /* We check for insufficient lookahead only every 8th comparison;
964 * the 256th check will be made at strstart+258.
965 */
966 do {
967 } while (*++scan == *++match && *++scan == *++match &&
968 *++scan == *++match && *++scan == *++match &&
969 *++scan == *++match && *++scan == *++match &&
970 *++scan == *++match && *++scan == *++match &&
971 scan < strend);
972
973 Assert(scan <= s->window+(unsigned)(s->window_size-1), "wild scan");
974
975 len = MAX_MATCH - (int)(strend - scan);
976 scan = strend - MAX_MATCH;
977
978 #endif /* UNALIGNED_OK */
979
980 if (len > best_len) {
981 s->match_start = cur_match;
982 best_len = len;
983 if (len >= nice_match) break;
984 #ifdef UNALIGNED_OK
985 scan_end = *(ushf*)(scan+best_len-1);
986 #else
987 scan_end1 = scan[best_len-1];
988 scan_end = scan[best_len];
989 #endif
990 }
991 } while ((cur_match = prev[cur_match & wmask]) > limit
992 && --chain_length != 0);
993
994 if ((uInt)best_len <= s->lookahead) return (uInt)best_len;
995 return s->lookahead;
996 }
997 #endif /* ASMV */
998 #endif /* FASTEST */
999
1000 /* ---------------------------------------------------------------------------
1001 * Optimized version for level == 1 or strategy == Z_RLE only
1002 */
1003 local uInt longest_match_fast(s, cur_match)
1004 deflate_state *s;
1005 IPos cur_match; /* current match */
1006 {
1007 register Bytef *scan = s->window + s->strstart; /* current string */
1008 register Bytef *match; /* matched string */
1009 register int len; /* length of current match */
1010 register Bytef *strend = s->window + s->strstart + MAX_MATCH;
1011
1012 /* The code is optimized for HASH_BITS >= 8 and MAX_MATCH-2 multiple of 16.
1013 * It is easy to get rid of this optimization if necessary.
1014 */
1015 Assert(s->hash_bits >= 8 && MAX_MATCH == 258, "Code too clever");
1016
1017 Assert((ulg)s->strstart <= s->window_size-MIN_LOOKAHEAD, "need lookahead");
1018
1019 Assert(cur_match < s->strstart, "no future");
1020
1021 match = s->window + cur_match;
1022
1023 /* Return failure if the match length is less than 2:
1024 */
1025 if (match[0] != scan[0] || match[1] != scan[1]) return MIN_MATCH-1;
1026
1027 /* The check at best_len-1 can be removed because it will be made
1028 * again later. (This heuristic is not always a win.)
1029 * It is not necessary to compare scan[2] and match[2] since they
1030 * are always equal when the other bytes match, given that
1031 * the hash keys are equal and that HASH_BITS >= 8.
1032 */
1033 scan += 2, match += 2;
1034 Assert(*scan == *match, "match[2]?");
1035
1036 /* We check for insufficient lookahead only every 8th comparison;
1037 * the 256th check will be made at strstart+258.
1038 */
1039 do {
1040 } while (*++scan == *++match && *++scan == *++match &&
1041 *++scan == *++match && *++scan == *++match &&
1042 *++scan == *++match && *++scan == *++match &&
1043 *++scan == *++match && *++scan == *++match &&
1044 scan < strend);
1045
1046 Assert(scan <= s->window+(unsigned)(s->window_size-1), "wild scan");
1047
1048 len = MAX_MATCH - (int)(strend - scan);
1049
1050 if (len < MIN_MATCH) return MIN_MATCH - 1;
1051
1052 s->match_start = cur_match;
1053 return (uInt)len <= s->lookahead ? (uInt)len : s->lookahead;
1054 }
1055
1056 #ifdef DEBUG
1057 /* ===========================================================================
1058 * Check that the match at match_start is indeed a match.
1059 */
1060 local void check_match(s, start, match, length)
1061 deflate_state *s;
1062 IPos start, match;
1063 int length;
1064 {
1065 /* check that the match is indeed a match */
1066 if (zmemcmp(s->window + match,
1067 s->window + start, length) != EQUAL) {
1068 fprintf(stderr, " start %u, match %u, length %d\n",
1069 start, match, length);
1070 do {
1071 fprintf(stderr, "%c%c", s->window[match++], s->window[start++]);
1072 } while (--length != 0);
1073 z_error("invalid match");
1074 }
1075 if (z_verbose > 1) {
1076 fprintf(stderr,"\\[%d,%d]", start-match, length);
1077 do { putc(s->window[start++], stderr); } while (--length != 0);
1078 }
1079 }
1080 #else
1081 # define check_match(s, start, match, length)
1082 #endif /* DEBUG */
1083
1084 /* ===========================================================================
1085 * Fill the window when the lookahead becomes insufficient.
1086 * Updates strstart and lookahead.
1087 *
1088 * IN assertion: lookahead < MIN_LOOKAHEAD
1089 * OUT assertions: strstart <= window_size-MIN_LOOKAHEAD
1090 * At least one byte has been read, or avail_in == 0; reads are
1091 * performed for at least two bytes (required for the zip translate_eol
1092 * option -- not supported here).
1093 */
1094 local void fill_window(s)
1095 deflate_state *s;
1096 {
1097 register unsigned n, m;
1098 register Posf *p;
1099 unsigned more; /* Amount of free space at the end of the window. */
1100 uInt wsize = s->w_size;
1101
1102 do {
1103 more = (unsigned)(s->window_size -(ulg)s->lookahead -(ulg)s->strstart);
1104
1105 /* Deal with !@#$% 64K limit: */
1106 if (sizeof(int) <= 2) {
1107 if (more == 0 && s->strstart == 0 && s->lookahead == 0) {
1108 more = wsize;
1109
1110 } else if (more == (unsigned)(-1)) {
1111 /* Very unlikely, but possible on 16 bit machine if
1112 * strstart == 0 && lookahead == 1 (input done a byte at time)
1113 */
1114 more--;
1115 }
1116 }
1117
1118 /* If the window is almost full and there is insufficient lookahead,
1119 * move the upper half to the lower one to make room in the upper half.
1120 */
1121 if (s->strstart >= wsize+MAX_DIST(s)) {
1122
1123 zmemcpy(s->window, s->window+wsize, (unsigned)wsize);
1124 s->match_start -= wsize;
1125 s->strstart -= wsize; /* we now have strstart >= MAX_DIST */
1126 s->block_start -= (long) wsize;
1127
1128 /* Slide the hash table (could be avoided with 32 bit values
1129 at the expense of memory usage). We slide even when level == 0
1130 to keep the hash table consistent if we switch back to level > 0
1131 later. (Using level 0 permanently is not an optimal usage of
1132 zlib, so we don't care about this pathological case.)
1133 */
1134 n = s->hash_size;
1135 p = &s->head[n];
1136 do {
1137 m = *--p;
1138 *p = (Pos)(m >= wsize ? m-wsize : NIL);
1139 } while (--n);
1140
1141 n = wsize;
1142 #ifndef FASTEST
1143 p = &s->prev[n];
1144 do {
1145 m = *--p;
1146 *p = (Pos)(m >= wsize ? m-wsize : NIL);
1147 /* If n is not on any hash chain, prev[n] is garbage but
1148 * its value will never be used.
1149 */
1150 } while (--n);
1151 #endif
1152 more += wsize;
1153 }
1154 if (s->strm->avail_in == 0) return;
1155
1156 /* If there was no sliding:
1157 * strstart <= WSIZE+MAX_DIST-1 && lookahead <= MIN_LOOKAHEAD - 1 &&
1158 * more == window_size - lookahead - strstart
1159 * => more >= window_size - (MIN_LOOKAHEAD-1 + WSIZE + MAX_DIST-1)
1160 * => more >= window_size - 2*WSIZE + 2
1161 * In the BIG_MEM or MMAP case (not yet supported),
1162 * window_size == input_size + MIN_LOOKAHEAD &&
1163 * strstart + s->lookahead <= input_size => more >= MIN_LOOKAHEAD.
1164 * Otherwise, window_size == 2*WSIZE so more >= 2.
1165 * If there was sliding, more >= WSIZE. So in all cases, more >= 2.
1166 */
1167 Assert(more >= 2, "more < 2");
1168
1169 n = read_buf(s->strm, s->window + s->strstart + s->lookahead, more);
1170 s->lookahead += n;
1171
1172 /* Initialize the hash value now that we have some input: */
1173 if (s->lookahead >= MIN_MATCH) {
1174 s->ins_h = s->window[s->strstart];
1175 UPDATE_HASH(s, s->ins_h, s->window[s->strstart+1]);
1176 #if MIN_MATCH != 3
1177 Call UPDATE_HASH() MIN_MATCH-3 more times
1178 #endif
1179 }
1180 /* If the whole input has less than MIN_MATCH bytes, ins_h is garbage,
1181 * but this is not important since only literal bytes will be emitted.
1182 */
1183
1184 } while (s->lookahead < MIN_LOOKAHEAD && s->strm->avail_in != 0);
1185 }
1186
1187 /* ===========================================================================
1188 * Flush the current block, with given end-of-file flag.
1189 * IN assertion: strstart is set to the end of the current match.
1190 */
1191 #define FLUSH_BLOCK_ONLY(s, eof) { \
1192 _tr_flush_block(s, (s->block_start >= 0L ? \
1193 (charf *)&s->window[(unsigned)s->block_start] : \
1194 (charf *)Z_NULL), \
1195 (ulg)((long)s->strstart - s->block_start), \
1196 (eof)); \
1197 s->block_start = s->strstart; \
1198 flush_pending(s->strm); \
1199 Tracev((stderr,"[FLUSH]")); \
1200 }
1201
1202 /* Same but force premature exit if necessary. */
1203 #define FLUSH_BLOCK(s, eof) { \
1204 FLUSH_BLOCK_ONLY(s, eof); \
1205 if (s->strm->avail_out == 0) return (eof) ? finish_started : need_more; \
1206 }
1207
1208 /* ===========================================================================
1209 * Copy without compression as much as possible from the input stream, return
1210 * the current block state.
1211 * This function does not insert new strings in the dictionary since
1212 * uncompressible data is probably not useful. This function is used
1213 * only for the level=0 compression option.
1214 * NOTE: this function should be optimized to avoid extra copying from
1215 * window to pending_buf.
1216 */
1217 local block_state deflate_stored(s, flush)
1218 deflate_state *s;
1219 int flush;
1220 {
1221 /* Stored blocks are limited to 0xffff bytes, pending_buf is limited
1222 * to pending_buf_size, and each stored block has a 5 byte header:
1223 */
1224 ulg max_block_size = 0xffff;
1225 ulg max_start;
1226
1227 if (max_block_size > s->pending_buf_size - 5) {
1228 max_block_size = s->pending_buf_size - 5;
1229 }
1230
1231 /* Copy as much as possible from input to output: */
1232 for (;;) {
1233 /* Fill the window as much as possible: */
1234 if (s->lookahead <= 1) {
1235
1236 Assert(s->strstart < s->w_size+MAX_DIST(s) ||
1237 s->block_start >= (long)s->w_size, "slide too late");
1238
1239 fill_window(s);
1240 if (s->lookahead == 0 && flush == Z_NO_FLUSH) return need_more;
1241
1242 if (s->lookahead == 0) break; /* flush the current block */
1243 }
1244 Assert(s->block_start >= 0L, "block gone");
1245
1246 s->strstart += s->lookahead;
1247 s->lookahead = 0;
1248
1249 /* Emit a stored block if pending_buf will be full: */
1250 max_start = s->block_start + max_block_size;
1251 if (s->strstart == 0 || (ulg)s->strstart >= max_start) {
1252 /* strstart == 0 is possible when wraparound on 16-bit machine */
1253 s->lookahead = (uInt)(s->strstart - max_start);
1254 s->strstart = (uInt)max_start;
1255 FLUSH_BLOCK(s, 0);
1256 }
1257 /* Flush if we may have to slide, otherwise block_start may become
1258 * negative and the data will be gone:
1259 */
1260 if (s->strstart - (uInt)s->block_start >= MAX_DIST(s)) {
1261 FLUSH_BLOCK(s, 0);
1262 }
1263 }
1264 FLUSH_BLOCK(s, flush == Z_FINISH);
1265 return flush == Z_FINISH ? finish_done : block_done;
1266 }
1267
1268 /* ===========================================================================
1269 * Compress as much as possible from the input stream, return the current
1270 * block state.
1271 * This function does not perform lazy evaluation of matches and inserts
1272 * new strings in the dictionary only for unmatched strings or for short
1273 * matches. It is used only for the fast compression options.
1274 */
1275 local block_state deflate_fast(s, flush)
1276 deflate_state *s;
1277 int flush;
1278 {
1279 IPos hash_head = NIL; /* head of the hash chain */
1280 int bflush; /* set if current block must be flushed */
1281
1282 for (;;) {
1283 /* Make sure that we always have enough lookahead, except
1284 * at the end of the input file. We need MAX_MATCH bytes
1285 * for the next match, plus MIN_MATCH bytes to insert the
1286 * string following the next match.
1287 */
1288 if (s->lookahead < MIN_LOOKAHEAD) {
1289 fill_window(s);
1290 if (s->lookahead < MIN_LOOKAHEAD && flush == Z_NO_FLUSH) {
1291 return need_more;
1292 }
1293 if (s->lookahead == 0) break; /* flush the current block */
1294 }
1295
1296 /* Insert the string window[strstart .. strstart+2] in the
1297 * dictionary, and set hash_head to the head of the hash chain:
1298 */
1299 if (s->lookahead >= MIN_MATCH) {
1300 INSERT_STRING(s, s->strstart, hash_head);
1301 }
1302
1303 /* Find the longest match, discarding those <= prev_length.
1304 * At this point we have always match_length < MIN_MATCH
1305 */
1306 if (hash_head != NIL && s->strstart - hash_head <= MAX_DIST(s)) {
1307 /* To simplify the code, we prevent matches with the string
1308 * of window index 0 (in particular we have to avoid a match
1309 * of the string with itself at the start of the input file).
1310 */
1311 #ifdef FASTEST
1312 if ((s->strategy < Z_HUFFMAN_ONLY) ||
1313 (s->strategy == Z_RLE && s->strstart - hash_head == 1)) {
1314 s->match_length = longest_match_fast (s, hash_head);
1315 }
1316 #else
1317 if (s->strategy < Z_HUFFMAN_ONLY) {
1318 s->match_length = longest_match (s, hash_head);
1319 } else if (s->strategy == Z_RLE && s->strstart - hash_head == 1) {
1320 s->match_length = longest_match_fast (s, hash_head);
1321 }
1322 #endif
1323 /* longest_match() or longest_match_fast() sets match_start */
1324 }
1325 if (s->match_length >= MIN_MATCH) {
1326 check_match(s, s->strstart, s->match_start, s->match_length);
1327
1328 _tr_tally_dist(s, s->strstart - s->match_start,
1329 s->match_length - MIN_MATCH, bflush);
1330
1331 s->lookahead -= s->match_length;
1332
1333 /* Insert new strings in the hash table only if the match length
1334 * is not too large. This saves time but degrades compression.
1335 */
1336 #ifndef FASTEST
1337 if (s->match_length <= s->max_insert_length &&
1338 s->lookahead >= MIN_MATCH) {
1339 s->match_length--; /* string at strstart already in table */
1340 do {
1341 s->strstart++;
1342 INSERT_STRING(s, s->strstart, hash_head);
1343 /* strstart never exceeds WSIZE-MAX_MATCH, so there are
1344 * always MIN_MATCH bytes ahead.
1345 */
1346 } while (--s->match_length != 0);
1347 s->strstart++;
1348 } else
1349 #endif
1350 {
1351 s->strstart += s->match_length;
1352 s->match_length = 0;
1353 s->ins_h = s->window[s->strstart];
1354 UPDATE_HASH(s, s->ins_h, s->window[s->strstart+1]);
1355 #if MIN_MATCH != 3
1356 Call UPDATE_HASH() MIN_MATCH-3 more times
1357 #endif
1358 /* If lookahead < MIN_MATCH, ins_h is garbage, but it does not
1359 * matter since it will be recomputed at next deflate call.
1360 */
1361 }
1362 } else {
1363 /* No match, output a literal byte */
1364 Tracevv((stderr,"%c", s->window[s->strstart]));
1365 _tr_tally_lit (s, s->window[s->strstart], bflush);
1366 s->lookahead--;
1367 s->strstart++;
1368 }
1369 if (bflush) FLUSH_BLOCK(s, 0);
1370 }
1371 FLUSH_BLOCK(s, flush == Z_FINISH);
1372 return flush == Z_FINISH ? finish_done : block_done;
1373 }
1374
1375 #ifndef FASTEST
1376 /* ===========================================================================
1377 * Same as above, but achieves better compression. We use a lazy
1378 * evaluation for matches: a match is finally adopted only if there is
1379 * no better match at the next window position.
1380 */
1381 local block_state deflate_slow(s, flush)
1382 deflate_state *s;
1383 int flush;
1384 {
1385 IPos hash_head = NIL; /* head of hash chain */
1386 int bflush; /* set if current block must be flushed */
1387
1388 /* Process the input block. */
1389 for (;;) {
1390 /* Make sure that we always have enough lookahead, except
1391 * at the end of the input file. We need MAX_MATCH bytes
1392 * for the next match, plus MIN_MATCH bytes to insert the
1393 * string following the next match.
1394 */
1395 if (s->lookahead < MIN_LOOKAHEAD) {
1396 fill_window(s);
1397 if (s->lookahead < MIN_LOOKAHEAD && flush == Z_NO_FLUSH) {
1398 return need_more;
1399 }
1400 if (s->lookahead == 0) break; /* flush the current block */
1401 }
1402
1403 /* Insert the string window[strstart .. strstart+2] in the
1404 * dictionary, and set hash_head to the head of the hash chain:
1405 */
1406 if (s->lookahead >= MIN_MATCH) {
1407 INSERT_STRING(s, s->strstart, hash_head);
1408 }
1409
1410 /* Find the longest match, discarding those <= prev_length.
1411 */
1412 s->prev_length = s->match_length, s->prev_match = s->match_start;
1413 s->match_length = MIN_MATCH-1;
1414
1415 if (hash_head != NIL && s->prev_length < s->max_lazy_match &&
1416 s->strstart - hash_head <= MAX_DIST(s)) {
1417 /* To simplify the code, we prevent matches with the string
1418 * of window index 0 (in particular we have to avoid a match
1419 * of the string with itself at the start of the input file).
1420 */
1421 if (s->strategy < Z_HUFFMAN_ONLY) {
1422 s->match_length = longest_match (s, hash_head);
1423 } else if (s->strategy == Z_RLE && s->strstart - hash_head == 1) {
1424 s->match_length = longest_match_fast (s, hash_head);
1425 }
1426 /* longest_match() or longest_match_fast() sets match_start */
1427
1428 if (s->match_length <= 5 && (s->strategy == Z_FILTERED
1429 #if TOO_FAR <= 32767
1430 || (s->match_length == MIN_MATCH &&
1431 s->strstart - s->match_start > TOO_FAR)
1432 #endif
1433 )) {
1434
1435 /* If prev_match is also MIN_MATCH, match_start is garbage
1436 * but we will ignore the current match anyway.
1437 */
1438 s->match_length = MIN_MATCH-1;
1439 }
1440 }
1441 /* If there was a match at the previous step and the current
1442 * match is not better, output the previous match:
1443 */
1444 if (s->prev_length >= MIN_MATCH && s->match_length <= s->prev_length) {
1445 uInt max_insert = s->strstart + s->lookahead - MIN_MATCH;
1446 /* Do not insert strings in hash table beyond this. */
1447
1448 check_match(s, s->strstart-1, s->prev_match, s->prev_length);
1449
1450 _tr_tally_dist(s, s->strstart -1 - s->prev_match,
1451 s->prev_length - MIN_MATCH, bflush);
1452
1453 /* Insert in hash table all strings up to the end of the match.
1454 * strstart-1 and strstart are already inserted. If there is not
1455 * enough lookahead, the last two strings are not inserted in
1456 * the hash table.
1457 */
1458 s->lookahead -= s->prev_length-1;
1459 s->prev_length -= 2;
1460 do {
1461 if (++s->strstart <= max_insert) {
1462 INSERT_STRING(s, s->strstart, hash_head);
1463 }
1464 } while (--s->prev_length != 0);
1465 s->match_available = 0;
1466 s->match_length = MIN_MATCH-1;
1467 s->strstart++;
1468
1469 if (bflush) FLUSH_BLOCK(s, 0);
1470
1471 } else if (s->match_available) {
1472 /* If there was no match at the previous position, output a
1473 * single literal. If there was a match but the current match
1474 * is longer, truncate the previous match to a single literal.
1475 */
1476 Tracevv((stderr,"%c", s->window[s->strstart-1]));
1477 _tr_tally_lit(s, s->window[s->strstart-1], bflush);
1478 if (bflush) {
1479 FLUSH_BLOCK_ONLY(s, 0);
1480 }
1481 s->strstart++;
1482 s->lookahead--;
1483 if (s->strm->avail_out == 0) return need_more;
1484 } else {
1485 /* There is no previous match to compare with, wait for
1486 * the next step to decide.
1487 */
1488 s->match_available = 1;
1489 s->strstart++;
1490 s->lookahead--;
1491 }
1492 }
1493 Assert (flush != Z_NO_FLUSH, "no flush?");
1494 if (s->match_available) {
1495 Tracevv((stderr,"%c", s->window[s->strstart-1]));
1496 _tr_tally_lit(s, s->window[s->strstart-1], bflush);
1497 s->match_available = 0;
1498 }
1499 FLUSH_BLOCK(s, flush == Z_FINISH);
1500 return flush == Z_FINISH ? finish_done : block_done;
1501 }
1502 #endif /* FASTEST */