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
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://tools.ietf.org/html/rfc1951
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#include <assert.h>
52#include "deflate.h"
53#include "cpu_features.h"
54#include "contrib/optimizations/insert_string.h"
55
56#if (defined(__ARM_NEON__) || defined(__ARM_NEON))
57#include "contrib/optimizations/slide_hash_neon.h"
58#endif
59#if defined(CRC32_ARMV8_CRC32)
60#include "crc32_simd.h"
61#endif
62
63const char deflate_copyright[] =
64 " deflate 1.2.11 Copyright 1995-2017 Jean-loup Gailly and Mark Adler ";
65/*
66 If you use the zlib library in a product, an acknowledgment is welcome
67 in the documentation of your product. If for some reason you cannot
68 include such an acknowledgment, I would appreciate that you keep this
69 copyright string in the executable of your product.
70 */
71
72/* ===========================================================================
73 * Function prototypes.
74 */
75typedef enum {
76 need_more, /* block not completed, need more input or more output */
77 block_done, /* block flush performed */
78 finish_started, /* finish started, need only more output at next deflate */
79 finish_done /* finish done, accept no more input or output */
80} block_state;
81
82typedef block_state (*compress_func) OF((deflate_state *s, int flush));
83/* Compression function. Returns the block state after the call. */
84
85local int deflateStateCheck OF((z_streamp strm));
86local void slide_hash OF((deflate_state *s));
87local void fill_window OF((deflate_state *s));
88local block_state deflate_stored OF((deflate_state *s, int flush));
89local block_state deflate_fast OF((deflate_state *s, int flush));
90#ifndef FASTEST
91local block_state deflate_slow OF((deflate_state *s, int flush));
92#endif
93local block_state deflate_rle OF((deflate_state *s, int flush));
94local block_state deflate_huff OF((deflate_state *s, int flush));
95local void lm_init OF((deflate_state *s));
96local void putShortMSB OF((deflate_state *s, uInt b));
97local void flush_pending OF((z_streamp strm));
98unsigned ZLIB_INTERNAL deflate_read_buf OF((z_streamp strm, Bytef *buf, unsigned size));
99#ifdef ASMV
100# pragma message("Assembler code may have bugs -- use at your own risk")
101 void match_init OF((void)); /* asm code initialization */
102 uInt longest_match OF((deflate_state *s, IPos cur_match));
103#else
104local uInt longest_match OF((deflate_state *s, IPos cur_match));
105#endif
106
107#ifdef ZLIB_DEBUG
108local void check_match OF((deflate_state *s, IPos start, IPos match,
109 int length));
110#endif
111
112/* From crc32.c */
113extern void ZLIB_INTERNAL crc_reset(deflate_state *const s);
114extern void ZLIB_INTERNAL crc_finalize(deflate_state *const s);
115extern void ZLIB_INTERNAL copy_with_crc(z_streamp strm, Bytef *dst, long size);
116
117/* ===========================================================================
118 * Local data
119 */
120
121#define NIL 0
122/* Tail of hash chains */
123
124#ifndef TOO_FAR
125# define TOO_FAR 4096
126#endif
127/* Matches of length 3 are discarded if their distance exceeds TOO_FAR */
128
129/* Values for max_lazy_match, good_match and max_chain_length, depending on
130 * the desired pack level (0..9). The values given below have been tuned to
131 * exclude worst case performance for pathological files. Better values may be
132 * found for specific files.
133 */
134typedef struct config_s {
135 ush good_length; /* reduce lazy search above this match length */
136 ush max_lazy; /* do not perform lazy search above this match length */
137 ush nice_length; /* quit search above this match length */
138 ush max_chain;
139 compress_func func;
140} config;
141
142#ifdef FASTEST
143local const config configuration_table[2] = {
144/* good lazy nice chain */
145/* 0 */ {0, 0, 0, 0, deflate_stored}, /* store only */
146/* 1 */ {4, 4, 8, 4, deflate_fast}}; /* max speed, no lazy matches */
147#else
148local const config configuration_table[10] = {
149/* good lazy nice chain */
150/* 0 */ {0, 0, 0, 0, deflate_stored}, /* store only */
151/* 1 */ {4, 4, 8, 4, deflate_fast}, /* max speed, no lazy matches */
152/* 2 */ {4, 5, 16, 8, deflate_fast},
153/* 3 */ {4, 6, 32, 32, deflate_fast},
154
155/* 4 */ {4, 4, 16, 16, deflate_slow}, /* lazy matches */
156/* 5 */ {8, 16, 32, 32, deflate_slow},
157/* 6 */ {8, 16, 128, 128, deflate_slow},
158/* 7 */ {8, 32, 128, 256, deflate_slow},
159/* 8 */ {32, 128, 258, 1024, deflate_slow},
160/* 9 */ {32, 258, 258, 4096, deflate_slow}}; /* max compression */
161#endif
162
163/* Note: the deflate() code requires max_lazy >= MIN_MATCH and max_chain >= 4
164 * For deflate_fast() (levels <= 3) good is ignored and lazy has a different
165 * meaning.
166 */
167
168/* rank Z_BLOCK between Z_NO_FLUSH and Z_PARTIAL_FLUSH */
169#define RANK(f) (((f) * 2) - ((f) > 4 ? 9 : 0))
170
171/* ===========================================================================
172 * Initialize the hash table (avoiding 64K overflow for 16 bit systems).
173 * prev[] will be initialized on the fly.
174 */
175#define CLEAR_HASH(s) \
176 s->head[s->hash_size-1] = NIL; \
177 zmemzero((Bytef *)s->head, (unsigned)(s->hash_size-1)*sizeof(*s->head));
178
179/* ===========================================================================
180 * Slide the hash table when sliding the window down (could be avoided with 32
181 * bit values at the expense of memory usage). We slide even when level == 0 to
182 * keep the hash table consistent if we switch back to level > 0 later.
183 */
184local void slide_hash(s)
185 deflate_state *s;
186{
187#if (defined(__ARM_NEON__) || defined(__ARM_NEON))
188 /* NEON based hash table rebase. */
189 return neon_slide_hash(s->head, s->prev, s->w_size, s->hash_size);
190#endif
191 unsigned n, m;
192 Posf *p;
193 uInt wsize = s->w_size;
194
195 n = s->hash_size;
196 p = &s->head[n];
197 do {
198 m = *--p;
199 *p = (Pos)(m >= wsize ? m - wsize : NIL);
200 } while (--n);
201 n = wsize;
202#ifndef FASTEST
203 p = &s->prev[n];
204 do {
205 m = *--p;
206 *p = (Pos)(m >= wsize ? m - wsize : NIL);
207 /* If n is not on any hash chain, prev[n] is garbage but
208 * its value will never be used.
209 */
210 } while (--n);
211#endif
212}
213
214/* ========================================================================= */
215int ZEXPORT deflateInit_(strm, level, version, stream_size)
216 z_streamp strm;
217 int level;
218 const char *version;
219 int stream_size;
220{
221 return deflateInit2_(strm, level, Z_DEFLATED, MAX_WBITS, DEF_MEM_LEVEL,
222 Z_DEFAULT_STRATEGY, version, stream_size);
223 /* To do: ignore strm->next_in if we use it as window */
224}
225
226/* ========================================================================= */
227int ZEXPORT deflateInit2_(strm, level, method, windowBits, memLevel, strategy,
228 version, stream_size)
229 z_streamp strm;
230 int level;
231 int method;
232 int windowBits;
233 int memLevel;
234 int strategy;
235 const char *version;
236 int stream_size;
237{
238 unsigned window_padding = 8;
239 deflate_state *s;
240 int wrap = 1;
241 static const char my_version[] = ZLIB_VERSION;
242
243 // Needed to activate optimized insert_string() that helps compression
244 // for all wrapper formats (e.g. RAW, ZLIB, GZIP).
245 // Feature detection is not triggered while using RAW mode (i.e. we never
246 // call crc32() with a NULL buffer).
247#if defined(CRC32_ARMV8_CRC32) || defined(CRC32_SIMD_SSE42_PCLMUL)
248 cpu_check_features();
249#endif
250
251 if (version == Z_NULL || version[0] != my_version[0] ||
252 stream_size != sizeof(z_stream)) {
253 return Z_VERSION_ERROR;
254 }
255 if (strm == Z_NULL) return Z_STREAM_ERROR;
256
257 strm->msg = Z_NULL;
258 if (strm->zalloc == (alloc_func)0) {
259#ifdef Z_SOLO
260 return Z_STREAM_ERROR;
261#else
262 strm->zalloc = zcalloc;
263 strm->opaque = (voidpf)0;
264#endif
265 }
266 if (strm->zfree == (free_func)0)
267#ifdef Z_SOLO
268 return Z_STREAM_ERROR;
269#else
270 strm->zfree = zcfree;
271#endif
272
273#ifdef FASTEST
274 if (level != 0) level = 1;
275#else
276 if (level == Z_DEFAULT_COMPRESSION) level = 6;
277#endif
278
279 if (windowBits < 0) { /* suppress zlib wrapper */
280 wrap = 0;
281 windowBits = -windowBits;
282 }
283#ifdef GZIP
284 else if (windowBits > 15) {
285 wrap = 2; /* write gzip wrapper instead */
286 windowBits -= 16;
287 }
288#endif
289 if (memLevel < 1 || memLevel > MAX_MEM_LEVEL || method != Z_DEFLATED ||
290 windowBits < 8 || windowBits > 15 || level < 0 || level > 9 ||
291 strategy < 0 || strategy > Z_FIXED || (windowBits == 8 && wrap != 1)) {
292 return Z_STREAM_ERROR;
293 }
294 if (windowBits == 8) windowBits = 9; /* until 256-byte window bug fixed */
295 s = (deflate_state *) ZALLOC(strm, 1, sizeof(deflate_state));
296 if (s == Z_NULL) return Z_MEM_ERROR;
297 strm->state = (struct internal_state FAR *)s;
298 s->strm = strm;
299 s->status = INIT_STATE; /* to pass state test in deflateReset() */
300
301 s->wrap = wrap;
302 s->gzhead = Z_NULL;
303 s->w_bits = (uInt)windowBits;
304 s->w_size = 1 << s->w_bits;
305 s->w_mask = s->w_size - 1;
306
307 if (x86_cpu_enable_simd) {
308 s->hash_bits = 15;
309 } else {
310 s->hash_bits = memLevel + 7;
311 }
312
313 s->hash_size = 1 << s->hash_bits;
314 s->hash_mask = s->hash_size - 1;
315 s->hash_shift = ((s->hash_bits+MIN_MATCH-1)/MIN_MATCH);
316
317 s->window = (Bytef *) ZALLOC(strm,
318 s->w_size + window_padding,
319 2*sizeof(Byte));
320 s->prev = (Posf *) ZALLOC(strm, s->w_size, sizeof(Pos));
321 /* Avoid use of uninitialized value, see:
322 * https://bugs.chromium.org/p/oss-fuzz/issues/detail?id=11360
323 */
324 zmemzero(s->prev, s->w_size * sizeof(Pos));
325 s->head = (Posf *) ZALLOC(strm, s->hash_size, sizeof(Pos));
326
327 s->high_water = 0; /* nothing written to s->window yet */
328
329 s->lit_bufsize = 1 << (memLevel + 6); /* 16K elements by default */
330
331 /* We overlay pending_buf and sym_buf. This works since the average size
332 * for length/distance pairs over any compressed block is assured to be 31
333 * bits or less.
334 *
335 * Analysis: The longest fixed codes are a length code of 8 bits plus 5
336 * extra bits, for lengths 131 to 257. The longest fixed distance codes are
337 * 5 bits plus 13 extra bits, for distances 16385 to 32768. The longest
338 * possible fixed-codes length/distance pair is then 31 bits total.
339 *
340 * sym_buf starts one-fourth of the way into pending_buf. So there are
341 * three bytes in sym_buf for every four bytes in pending_buf. Each symbol
342 * in sym_buf is three bytes -- two for the distance and one for the
343 * literal/length. As each symbol is consumed, the pointer to the next
344 * sym_buf value to read moves forward three bytes. From that symbol, up to
345 * 31 bits are written to pending_buf. The closest the written pending_buf
346 * bits gets to the next sym_buf symbol to read is just before the last
347 * code is written. At that time, 31*(n-2) bits have been written, just
348 * after 24*(n-2) bits have been consumed from sym_buf. sym_buf starts at
349 * 8*n bits into pending_buf. (Note that the symbol buffer fills when n-1
350 * symbols are written.) The closest the writing gets to what is unread is
351 * then n+14 bits. Here n is lit_bufsize, which is 16384 by default, and
352 * can range from 128 to 32768.
353 *
354 * Therefore, at a minimum, there are 142 bits of space between what is
355 * written and what is read in the overlain buffers, so the symbols cannot
356 * be overwritten by the compressed data. That space is actually 139 bits,
357 * due to the three-bit fixed-code block header.
358 *
359 * That covers the case where either Z_FIXED is specified, forcing fixed
360 * codes, or when the use of fixed codes is chosen, because that choice
361 * results in a smaller compressed block than dynamic codes. That latter
362 * condition then assures that the above analysis also covers all dynamic
363 * blocks. A dynamic-code block will only be chosen to be emitted if it has
364 * fewer bits than a fixed-code block would for the same set of symbols.
365 * Therefore its average symbol length is assured to be less than 31. So
366 * the compressed data for a dynamic block also cannot overwrite the
367 * symbols from which it is being constructed.
368 */
369 s->pending_buf = (uchf *) ZALLOC(strm, s->lit_bufsize, 4);
370 s->pending_buf_size = (ulg)s->lit_bufsize * 4;
371
372 if (s->window == Z_NULL || s->prev == Z_NULL || s->head == Z_NULL ||
373 s->pending_buf == Z_NULL) {
374 s->status = FINISH_STATE;
375 strm->msg = ERR_MSG(Z_MEM_ERROR);
376 deflateEnd (strm);
377 return Z_MEM_ERROR;
378 }
379 s->sym_buf = s->pending_buf + s->lit_bufsize;
380 s->sym_end = (s->lit_bufsize - 1) * 3;
381 /* We avoid equality with lit_bufsize*3 because of wraparound at 64K
382 * on 16 bit machines and because stored blocks are restricted to
383 * 64K-1 bytes.
384 */
385
386 s->level = level;
387 s->strategy = strategy;
388 s->method = (Byte)method;
389
390 return deflateReset(strm);
391}
392
393/* =========================================================================
394 * Check for a valid deflate stream state. Return 0 if ok, 1 if not.
395 */
396local int deflateStateCheck (strm)
397 z_streamp strm;
398{
399 deflate_state *s;
400 if (strm == Z_NULL ||
401 strm->zalloc == (alloc_func)0 || strm->zfree == (free_func)0)
402 return 1;
403 s = strm->state;
404 if (s == Z_NULL || s->strm != strm || (s->status != INIT_STATE &&
405#ifdef GZIP
406 s->status != GZIP_STATE &&
407#endif
408 s->status != EXTRA_STATE &&
409 s->status != NAME_STATE &&
410 s->status != COMMENT_STATE &&
411 s->status != HCRC_STATE &&
412 s->status != BUSY_STATE &&
413 s->status != FINISH_STATE))
414 return 1;
415 return 0;
416}
417
418/* ========================================================================= */
419int ZEXPORT deflateSetDictionary (strm, dictionary, dictLength)
420 z_streamp strm;
421 const Bytef *dictionary;
422 uInt dictLength;
423{
424 deflate_state *s;
425 uInt str, n;
426 int wrap;
427 unsigned avail;
428 z_const unsigned char *next;
429
430 if (deflateStateCheck(strm) || dictionary == Z_NULL)
431 return Z_STREAM_ERROR;
432 s = strm->state;
433 wrap = s->wrap;
434 if (wrap == 2 || (wrap == 1 && s->status != INIT_STATE) || s->lookahead)
435 return Z_STREAM_ERROR;
436
437 /* when using zlib wrappers, compute Adler-32 for provided dictionary */
438 if (wrap == 1)
439 strm->adler = adler32(strm->adler, dictionary, dictLength);
440 s->wrap = 0; /* avoid computing Adler-32 in deflate_read_buf */
441
442 /* if dictionary would fill window, just replace the history */
443 if (dictLength >= s->w_size) {
444 if (wrap == 0) { /* already empty otherwise */
445 CLEAR_HASH(s);
446 s->strstart = 0;
447 s->block_start = 0L;
448 s->insert = 0;
449 }
450 dictionary += dictLength - s->w_size; /* use the tail */
451 dictLength = s->w_size;
452 }
453
454 /* insert dictionary into window and hash */
455 avail = strm->avail_in;
456 next = strm->next_in;
457 strm->avail_in = dictLength;
458 strm->next_in = (z_const Bytef *)dictionary;
459 fill_window(s);
460 while (s->lookahead >= MIN_MATCH) {
461 str = s->strstart;
462 n = s->lookahead - (MIN_MATCH-1);
463 do {
464 insert_string(s, str);
465 str++;
466 } while (--n);
467 s->strstart = str;
468 s->lookahead = MIN_MATCH-1;
469 fill_window(s);
470 }
471 s->strstart += s->lookahead;
472 s->block_start = (long)s->strstart;
473 s->insert = s->lookahead;
474 s->lookahead = 0;
475 s->match_length = s->prev_length = MIN_MATCH-1;
476 s->match_available = 0;
477 strm->next_in = next;
478 strm->avail_in = avail;
479 s->wrap = wrap;
480 return Z_OK;
481}
482
483/* ========================================================================= */
484int ZEXPORT deflateGetDictionary (strm, dictionary, dictLength)
485 z_streamp strm;
486 Bytef *dictionary;
487 uInt *dictLength;
488{
489 deflate_state *s;
490 uInt len;
491
492 if (deflateStateCheck(strm))
493 return Z_STREAM_ERROR;
494 s = strm->state;
495 len = s->strstart + s->lookahead;
496 if (len > s->w_size)
497 len = s->w_size;
498 if (dictionary != Z_NULL && len)
499 zmemcpy(dictionary, s->window + s->strstart + s->lookahead - len, len);
500 if (dictLength != Z_NULL)
501 *dictLength = len;
502 return Z_OK;
503}
504
505/* ========================================================================= */
506int ZEXPORT deflateResetKeep (strm)
507 z_streamp strm;
508{
509 deflate_state *s;
510
511 if (deflateStateCheck(strm)) {
512 return Z_STREAM_ERROR;
513 }
514
515 strm->total_in = strm->total_out = 0;
516 strm->msg = Z_NULL; /* use zfree if we ever allocate msg dynamically */
517 strm->data_type = Z_UNKNOWN;
518
519 s = (deflate_state *)strm->state;
520 s->pending = 0;
521 s->pending_out = s->pending_buf;
522
523 if (s->wrap < 0) {
524 s->wrap = -s->wrap; /* was made negative by deflate(..., Z_FINISH); */
525 }
526 s->status =
527#ifdef GZIP
528 s->wrap == 2 ? GZIP_STATE :
529#endif
530 s->wrap ? INIT_STATE : BUSY_STATE;
531 strm->adler =
532#ifdef GZIP
533 s->wrap == 2 ? crc32(0L, Z_NULL, 0) :
534#endif
535 adler32(0L, Z_NULL, 0);
536 s->last_flush = Z_NO_FLUSH;
537
538 _tr_init(s);
539
540 return Z_OK;
541}
542
543/* ========================================================================= */
544int ZEXPORT deflateReset (strm)
545 z_streamp strm;
546{
547 int ret;
548
549 ret = deflateResetKeep(strm);
550 if (ret == Z_OK)
551 lm_init(strm->state);
552 return ret;
553}
554
555/* ========================================================================= */
556int ZEXPORT deflateSetHeader (strm, head)
557 z_streamp strm;
558 gz_headerp head;
559{
560 if (deflateStateCheck(strm) || strm->state->wrap != 2)
561 return Z_STREAM_ERROR;
562 strm->state->gzhead = head;
563 return Z_OK;
564}
565
566/* ========================================================================= */
567int ZEXPORT deflatePending (strm, pending, bits)
568 unsigned *pending;
569 int *bits;
570 z_streamp strm;
571{
572 if (deflateStateCheck(strm)) return Z_STREAM_ERROR;
573 if (pending != Z_NULL)
574 *pending = strm->state->pending;
575 if (bits != Z_NULL)
576 *bits = strm->state->bi_valid;
577 return Z_OK;
578}
579
580/* ========================================================================= */
581int ZEXPORT deflatePrime (strm, bits, value)
582 z_streamp strm;
583 int bits;
584 int value;
585{
586 deflate_state *s;
587 int put;
588
589 if (deflateStateCheck(strm)) return Z_STREAM_ERROR;
590 s = strm->state;
591 if (s->sym_buf < s->pending_out + ((Buf_size + 7) >> 3))
592 return Z_BUF_ERROR;
593 do {
594 put = Buf_size - s->bi_valid;
595 if (put > bits)
596 put = bits;
597 s->bi_buf |= (ush)((value & ((1 << put) - 1)) << s->bi_valid);
598 s->bi_valid += put;
599 _tr_flush_bits(s);
600 value >>= put;
601 bits -= put;
602 } while (bits);
603 return Z_OK;
604}
605
606/* ========================================================================= */
607int ZEXPORT deflateParams(strm, level, strategy)
608 z_streamp strm;
609 int level;
610 int strategy;
611{
612 deflate_state *s;
613 compress_func func;
614
615 if (deflateStateCheck(strm)) return Z_STREAM_ERROR;
616 s = strm->state;
617
618#ifdef FASTEST
619 if (level != 0) level = 1;
620#else
621 if (level == Z_DEFAULT_COMPRESSION) level = 6;
622#endif
623 if (level < 0 || level > 9 || strategy < 0 || strategy > Z_FIXED) {
624 return Z_STREAM_ERROR;
625 }
626 func = configuration_table[s->level].func;
627
628 if ((strategy != s->strategy || func != configuration_table[level].func) &&
629 s->high_water) {
630 /* Flush the last buffer: */
631 int err = deflate(strm, Z_BLOCK);
632 if (err == Z_STREAM_ERROR)
633 return err;
634 if (strm->avail_out == 0)
635 return Z_BUF_ERROR;
636 }
637 if (s->level != level) {
638 if (s->level == 0 && s->matches != 0) {
639 if (s->matches == 1)
640 slide_hash(s);
641 else
642 CLEAR_HASH(s);
643 s->matches = 0;
644 }
645 s->level = level;
646 s->max_lazy_match = configuration_table[level].max_lazy;
647 s->good_match = configuration_table[level].good_length;
648 s->nice_match = configuration_table[level].nice_length;
649 s->max_chain_length = configuration_table[level].max_chain;
650 }
651 s->strategy = strategy;
652 return Z_OK;
653}
654
655/* ========================================================================= */
656int ZEXPORT deflateTune(strm, good_length, max_lazy, nice_length, max_chain)
657 z_streamp strm;
658 int good_length;
659 int max_lazy;
660 int nice_length;
661 int max_chain;
662{
663 deflate_state *s;
664
665 if (deflateStateCheck(strm)) return Z_STREAM_ERROR;
666 s = strm->state;
667 s->good_match = (uInt)good_length;
668 s->max_lazy_match = (uInt)max_lazy;
669 s->nice_match = nice_length;
670 s->max_chain_length = (uInt)max_chain;
671 return Z_OK;
672}
673
674/* =========================================================================
675 * For the default windowBits of 15 and memLevel of 8, this function returns
676 * a close to exact, as well as small, upper bound on the compressed size.
677 * They are coded as constants here for a reason--if the #define's are
678 * changed, then this function needs to be changed as well. The return
679 * value for 15 and 8 only works for those exact settings.
680 *
681 * For any setting other than those defaults for windowBits and memLevel,
682 * the value returned is a conservative worst case for the maximum expansion
683 * resulting from using fixed blocks instead of stored blocks, which deflate
684 * can emit on compressed data for some combinations of the parameters.
685 *
686 * This function could be more sophisticated to provide closer upper bounds for
687 * every combination of windowBits and memLevel. But even the conservative
688 * upper bound of about 14% expansion does not seem onerous for output buffer
689 * allocation.
690 */
691uLong ZEXPORT deflateBound(strm, sourceLen)
692 z_streamp strm;
693 uLong sourceLen;
694{
695 deflate_state *s;
696 uLong complen, wraplen;
697
698 /* conservative upper bound for compressed data */
699 complen = sourceLen +
700 ((sourceLen + 7) >> 3) + ((sourceLen + 63) >> 6) + 5;
701
702 /* if can't get parameters, return conservative bound plus zlib wrapper */
703 if (deflateStateCheck(strm))
704 return complen + 6;
705
706 /* compute wrapper length */
707 s = strm->state;
708 switch (s->wrap) {
709 case 0: /* raw deflate */
710 wraplen = 0;
711 break;
712 case 1: /* zlib wrapper */
713 wraplen = 6 + (s->strstart ? 4 : 0);
714 break;
715#ifdef GZIP
716 case 2: /* gzip wrapper */
717 wraplen = 18;
718 if (s->gzhead != Z_NULL) { /* user-supplied gzip header */
719 Bytef *str;
720 if (s->gzhead->extra != Z_NULL)
721 wraplen += 2 + s->gzhead->extra_len;
722 str = s->gzhead->name;
723 if (str != Z_NULL)
724 do {
725 wraplen++;
726 } while (*str++);
727 str = s->gzhead->comment;
728 if (str != Z_NULL)
729 do {
730 wraplen++;
731 } while (*str++);
732 if (s->gzhead->hcrc)
733 wraplen += 2;
734 }
735 break;
736#endif
737 default: /* for compiler happiness */
738 wraplen = 6;
739 }
740
741 /* if not default parameters, return conservative bound */
742 if (s->w_bits != 15 || s->hash_bits != 8 + 7)
743 return complen + wraplen;
744
745 /* default settings: return tight bound for that case */
746 return sourceLen + (sourceLen >> 12) + (sourceLen >> 14) +
747 (sourceLen >> 25) + 13 - 6 + wraplen;
748}
749
750/* =========================================================================
751 * Put a short in the pending buffer. The 16-bit value is put in MSB order.
752 * IN assertion: the stream state is correct and there is enough room in
753 * pending_buf.
754 */
755local void putShortMSB (s, b)
756 deflate_state *s;
757 uInt b;
758{
759 put_byte(s, (Byte)(b >> 8));
760 put_byte(s, (Byte)(b & 0xff));
761}
762
763/* =========================================================================
764 * Flush as much pending output as possible. All deflate() output, except for
765 * some deflate_stored() output, goes through this function so some
766 * applications may wish to modify it to avoid allocating a large
767 * strm->next_out buffer and copying into it. (See also deflate_read_buf()).
768 */
769local void flush_pending(strm)
770 z_streamp strm;
771{
772 unsigned len;
773 deflate_state *s = strm->state;
774
775 _tr_flush_bits(s);
776 len = s->pending;
777 if (len > strm->avail_out) len = strm->avail_out;
778 if (len == 0) return;
779
780 zmemcpy(strm->next_out, s->pending_out, len);
781 strm->next_out += len;
782 s->pending_out += len;
783 strm->total_out += len;
784 strm->avail_out -= len;
785 s->pending -= len;
786 if (s->pending == 0) {
787 s->pending_out = s->pending_buf;
788 }
789}
790
791/* ===========================================================================
792 * Update the header CRC with the bytes s->pending_buf[beg..s->pending - 1].
793 */
794#define HCRC_UPDATE(beg) \
795 do { \
796 if (s->gzhead->hcrc && s->pending > (beg)) \
797 strm->adler = crc32(strm->adler, s->pending_buf + (beg), \
798 s->pending - (beg)); \
799 } while (0)
800
801/* ========================================================================= */
802int ZEXPORT deflate (strm, flush)
803 z_streamp strm;
804 int flush;
805{
806 int old_flush; /* value of flush param for previous deflate call */
807 deflate_state *s;
808
809 if (deflateStateCheck(strm) || flush > Z_BLOCK || flush < 0) {
810 return Z_STREAM_ERROR;
811 }
812 s = strm->state;
813
814 if (strm->next_out == Z_NULL ||
815 (strm->avail_in != 0 && strm->next_in == Z_NULL) ||
816 (s->status == FINISH_STATE && flush != Z_FINISH)) {
817 ERR_RETURN(strm, Z_STREAM_ERROR);
818 }
819 if (strm->avail_out == 0) ERR_RETURN(strm, Z_BUF_ERROR);
820
821 old_flush = s->last_flush;
822 s->last_flush = flush;
823
824 /* Flush as much pending output as possible */
825 if (s->pending != 0) {
826 flush_pending(strm);
827 if (strm->avail_out == 0) {
828 /* Since avail_out is 0, deflate will be called again with
829 * more output space, but possibly with both pending and
830 * avail_in equal to zero. There won't be anything to do,
831 * but this is not an error situation so make sure we
832 * return OK instead of BUF_ERROR at next call of deflate:
833 */
834 s->last_flush = -1;
835 return Z_OK;
836 }
837
838 /* Make sure there is something to do and avoid duplicate consecutive
839 * flushes. For repeated and useless calls with Z_FINISH, we keep
840 * returning Z_STREAM_END instead of Z_BUF_ERROR.
841 */
842 } else if (strm->avail_in == 0 && RANK(flush) <= RANK(old_flush) &&
843 flush != Z_FINISH) {
844 ERR_RETURN(strm, Z_BUF_ERROR);
845 }
846
847 /* User must not provide more input after the first FINISH: */
848 if (s->status == FINISH_STATE && strm->avail_in != 0) {
849 ERR_RETURN(strm, Z_BUF_ERROR);
850 }
851
852 /* Write the header */
853 if (s->status == INIT_STATE) {
854 /* zlib header */
855 uInt header = (Z_DEFLATED + ((s->w_bits-8)<<4)) << 8;
856 uInt level_flags;
857
858 if (s->strategy >= Z_HUFFMAN_ONLY || s->level < 2)
859 level_flags = 0;
860 else if (s->level < 6)
861 level_flags = 1;
862 else if (s->level == 6)
863 level_flags = 2;
864 else
865 level_flags = 3;
866 header |= (level_flags << 6);
867 if (s->strstart != 0) header |= PRESET_DICT;
868 header += 31 - (header % 31);
869
870 putShortMSB(s, header);
871
872 /* Save the adler32 of the preset dictionary: */
873 if (s->strstart != 0) {
874 putShortMSB(s, (uInt)(strm->adler >> 16));
875 putShortMSB(s, (uInt)(strm->adler & 0xffff));
876 }
877 strm->adler = adler32(0L, Z_NULL, 0);
878 s->status = BUSY_STATE;
879
880 /* Compression must start with an empty pending buffer */
881 flush_pending(strm);
882 if (s->pending != 0) {
883 s->last_flush = -1;
884 return Z_OK;
885 }
886 }
887#ifdef GZIP
888 if (s->status == GZIP_STATE) {
889 /* gzip header */
890 crc_reset(s);
891 put_byte(s, 31);
892 put_byte(s, 139);
893 put_byte(s, 8);
894 if (s->gzhead == Z_NULL) {
895 put_byte(s, 0);
896 put_byte(s, 0);
897 put_byte(s, 0);
898 put_byte(s, 0);
899 put_byte(s, 0);
900 put_byte(s, s->level == 9 ? 2 :
901 (s->strategy >= Z_HUFFMAN_ONLY || s->level < 2 ?
902 4 : 0));
903 put_byte(s, OS_CODE);
904 s->status = BUSY_STATE;
905
906 /* Compression must start with an empty pending buffer */
907 flush_pending(strm);
908 if (s->pending != 0) {
909 s->last_flush = -1;
910 return Z_OK;
911 }
912 }
913 else {
914 put_byte(s, (s->gzhead->text ? 1 : 0) +
915 (s->gzhead->hcrc ? 2 : 0) +
916 (s->gzhead->extra == Z_NULL ? 0 : 4) +
917 (s->gzhead->name == Z_NULL ? 0 : 8) +
918 (s->gzhead->comment == Z_NULL ? 0 : 16)
919 );
920 put_byte(s, (Byte)(s->gzhead->time & 0xff));
921 put_byte(s, (Byte)((s->gzhead->time >> 8) & 0xff));
922 put_byte(s, (Byte)((s->gzhead->time >> 16) & 0xff));
923 put_byte(s, (Byte)((s->gzhead->time >> 24) & 0xff));
924 put_byte(s, s->level == 9 ? 2 :
925 (s->strategy >= Z_HUFFMAN_ONLY || s->level < 2 ?
926 4 : 0));
927 put_byte(s, s->gzhead->os & 0xff);
928 if (s->gzhead->extra != Z_NULL) {
929 put_byte(s, s->gzhead->extra_len & 0xff);
930 put_byte(s, (s->gzhead->extra_len >> 8) & 0xff);
931 }
932 if (s->gzhead->hcrc)
933 strm->adler = crc32(strm->adler, s->pending_buf,
934 s->pending);
935 s->gzindex = 0;
936 s->status = EXTRA_STATE;
937 }
938 }
939 if (s->status == EXTRA_STATE) {
940 if (s->gzhead->extra != Z_NULL) {
941 ulg beg = s->pending; /* start of bytes to update crc */
942 uInt left = (s->gzhead->extra_len & 0xffff) - s->gzindex;
943 while (s->pending + left > s->pending_buf_size) {
944 uInt copy = s->pending_buf_size - s->pending;
945 zmemcpy(s->pending_buf + s->pending,
946 s->gzhead->extra + s->gzindex, copy);
947 s->pending = s->pending_buf_size;
948 HCRC_UPDATE(beg);
949 s->gzindex += copy;
950 flush_pending(strm);
951 if (s->pending != 0) {
952 s->last_flush = -1;
953 return Z_OK;
954 }
955 beg = 0;
956 left -= copy;
957 }
958 zmemcpy(s->pending_buf + s->pending,
959 s->gzhead->extra + s->gzindex, left);
960 s->pending += left;
961 HCRC_UPDATE(beg);
962 s->gzindex = 0;
963 }
964 s->status = NAME_STATE;
965 }
966 if (s->status == NAME_STATE) {
967 if (s->gzhead->name != Z_NULL) {
968 ulg beg = s->pending; /* start of bytes to update crc */
969 int val;
970 do {
971 if (s->pending == s->pending_buf_size) {
972 HCRC_UPDATE(beg);
973 flush_pending(strm);
974 if (s->pending != 0) {
975 s->last_flush = -1;
976 return Z_OK;
977 }
978 beg = 0;
979 }
980 val = s->gzhead->name[s->gzindex++];
981 put_byte(s, val);
982 } while (val != 0);
983 HCRC_UPDATE(beg);
984 s->gzindex = 0;
985 }
986 s->status = COMMENT_STATE;
987 }
988 if (s->status == COMMENT_STATE) {
989 if (s->gzhead->comment != Z_NULL) {
990 ulg beg = s->pending; /* start of bytes to update crc */
991 int val;
992 do {
993 if (s->pending == s->pending_buf_size) {
994 HCRC_UPDATE(beg);
995 flush_pending(strm);
996 if (s->pending != 0) {
997 s->last_flush = -1;
998 return Z_OK;
999 }
1000 beg = 0;
1001 }
1002 val = s->gzhead->comment[s->gzindex++];
1003 put_byte(s, val);
1004 } while (val != 0);
1005 HCRC_UPDATE(beg);
1006 }
1007 s->status = HCRC_STATE;
1008 }
1009 if (s->status == HCRC_STATE) {
1010 if (s->gzhead->hcrc) {
1011 if (s->pending + 2 > s->pending_buf_size) {
1012 flush_pending(strm);
1013 if (s->pending != 0) {
1014 s->last_flush = -1;
1015 return Z_OK;
1016 }
1017 }
1018 put_byte(s, (Byte)(strm->adler & 0xff));
1019 put_byte(s, (Byte)((strm->adler >> 8) & 0xff));
1020 strm->adler = crc32(0L, Z_NULL, 0);
1021 }
1022 s->status = BUSY_STATE;
1023
1024 /* Compression must start with an empty pending buffer */
1025 flush_pending(strm);
1026 if (s->pending != 0) {
1027 s->last_flush = -1;
1028 return Z_OK;
1029 }
1030 }
1031#endif
1032
1033 /* Start a new block or continue the current one.
1034 */
1035 if (strm->avail_in != 0 || s->lookahead != 0 ||
1036 (flush != Z_NO_FLUSH && s->status != FINISH_STATE)) {
1037 block_state bstate;
1038
1039 bstate = s->level == 0 ? deflate_stored(s, flush) :
1040 s->strategy == Z_HUFFMAN_ONLY ? deflate_huff(s, flush) :
1041 s->strategy == Z_RLE ? deflate_rle(s, flush) :
1042 (*(configuration_table[s->level].func))(s, flush);
1043
1044 if (bstate == finish_started || bstate == finish_done) {
1045 s->status = FINISH_STATE;
1046 }
1047 if (bstate == need_more || bstate == finish_started) {
1048 if (strm->avail_out == 0) {
1049 s->last_flush = -1; /* avoid BUF_ERROR next call, see above */
1050 }
1051 return Z_OK;
1052 /* If flush != Z_NO_FLUSH && avail_out == 0, the next call
1053 * of deflate should use the same flush parameter to make sure
1054 * that the flush is complete. So we don't have to output an
1055 * empty block here, this will be done at next call. This also
1056 * ensures that for a very small output buffer, we emit at most
1057 * one empty block.
1058 */
1059 }
1060 if (bstate == block_done) {
1061 if (flush == Z_PARTIAL_FLUSH) {
1062 _tr_align(s);
1063 } else if (flush != Z_BLOCK) { /* FULL_FLUSH or SYNC_FLUSH */
1064 _tr_stored_block(s, (char*)0, 0L, 0);
1065 /* For a full flush, this empty block will be recognized
1066 * as a special marker by inflate_sync().
1067 */
1068 if (flush == Z_FULL_FLUSH) {
1069 CLEAR_HASH(s); /* forget history */
1070 if (s->lookahead == 0) {
1071 s->strstart = 0;
1072 s->block_start = 0L;
1073 s->insert = 0;
1074 }
1075 }
1076 }
1077 flush_pending(strm);
1078 if (strm->avail_out == 0) {
1079 s->last_flush = -1; /* avoid BUF_ERROR at next call, see above */
1080 return Z_OK;
1081 }
1082 }
1083 }
1084
1085 if (flush != Z_FINISH) return Z_OK;
1086 if (s->wrap <= 0) return Z_STREAM_END;
1087
1088 /* Write the trailer */
1089#ifdef GZIP
1090 if (s->wrap == 2) {
1091 crc_finalize(s);
1092 put_byte(s, (Byte)(strm->adler & 0xff));
1093 put_byte(s, (Byte)((strm->adler >> 8) & 0xff));
1094 put_byte(s, (Byte)((strm->adler >> 16) & 0xff));
1095 put_byte(s, (Byte)((strm->adler >> 24) & 0xff));
1096 put_byte(s, (Byte)(strm->total_in & 0xff));
1097 put_byte(s, (Byte)((strm->total_in >> 8) & 0xff));
1098 put_byte(s, (Byte)((strm->total_in >> 16) & 0xff));
1099 put_byte(s, (Byte)((strm->total_in >> 24) & 0xff));
1100 }
1101 else
1102#endif
1103 {
1104 putShortMSB(s, (uInt)(strm->adler >> 16));
1105 putShortMSB(s, (uInt)(strm->adler & 0xffff));
1106 }
1107 flush_pending(strm);
1108 /* If avail_out is zero, the application will call deflate again
1109 * to flush the rest.
1110 */
1111 if (s->wrap > 0) s->wrap = -s->wrap; /* write the trailer only once! */
1112 return s->pending != 0 ? Z_OK : Z_STREAM_END;
1113}
1114
1115/* ========================================================================= */
1116int ZEXPORT deflateEnd (strm)
1117 z_streamp strm;
1118{
1119 int status;
1120
1121 if (deflateStateCheck(strm)) return Z_STREAM_ERROR;
1122
1123 status = strm->state->status;
1124
1125 /* Deallocate in reverse order of allocations: */
1126 TRY_FREE(strm, strm->state->pending_buf);
1127 TRY_FREE(strm, strm->state->head);
1128 TRY_FREE(strm, strm->state->prev);
1129 TRY_FREE(strm, strm->state->window);
1130
1131 ZFREE(strm, strm->state);
1132 strm->state = Z_NULL;
1133
1134 return status == BUSY_STATE ? Z_DATA_ERROR : Z_OK;
1135}
1136
1137/* =========================================================================
1138 * Copy the source state to the destination state.
1139 * To simplify the source, this is not supported for 16-bit MSDOS (which
1140 * doesn't have enough memory anyway to duplicate compression states).
1141 */
1142int ZEXPORT deflateCopy (dest, source)
1143 z_streamp dest;
1144 z_streamp source;
1145{
1146#ifdef MAXSEG_64K
1147 return Z_STREAM_ERROR;
1148#else
1149 deflate_state *ds;
1150 deflate_state *ss;
1151
1152
1153 if (deflateStateCheck(source) || dest == Z_NULL) {
1154 return Z_STREAM_ERROR;
1155 }
1156
1157 ss = source->state;
1158
1159 zmemcpy((voidpf)dest, (voidpf)source, sizeof(z_stream));
1160
1161 ds = (deflate_state *) ZALLOC(dest, 1, sizeof(deflate_state));
1162 if (ds == Z_NULL) return Z_MEM_ERROR;
1163 dest->state = (struct internal_state FAR *) ds;
1164 zmemcpy((voidpf)ds, (voidpf)ss, sizeof(deflate_state));
1165 ds->strm = dest;
1166
1167 ds->window = (Bytef *) ZALLOC(dest, ds->w_size, 2*sizeof(Byte));
1168 ds->prev = (Posf *) ZALLOC(dest, ds->w_size, sizeof(Pos));
1169 ds->head = (Posf *) ZALLOC(dest, ds->hash_size, sizeof(Pos));
1170 ds->pending_buf = (uchf *) ZALLOC(dest, ds->lit_bufsize, 4);
1171
1172 if (ds->window == Z_NULL || ds->prev == Z_NULL || ds->head == Z_NULL ||
1173 ds->pending_buf == Z_NULL) {
1174 deflateEnd (dest);
1175 return Z_MEM_ERROR;
1176 }
1177 /* following zmemcpy do not work for 16-bit MSDOS */
1178 zmemcpy(ds->window, ss->window, ds->w_size * 2 * sizeof(Byte));
1179 zmemcpy((voidpf)ds->prev, (voidpf)ss->prev, ds->w_size * sizeof(Pos));
1180 zmemcpy((voidpf)ds->head, (voidpf)ss->head, ds->hash_size * sizeof(Pos));
1181 zmemcpy(ds->pending_buf, ss->pending_buf, (uInt)ds->pending_buf_size);
1182
1183 ds->pending_out = ds->pending_buf + (ss->pending_out - ss->pending_buf);
1184 ds->sym_buf = ds->pending_buf + ds->lit_bufsize;
1185
1186 ds->l_desc.dyn_tree = ds->dyn_ltree;
1187 ds->d_desc.dyn_tree = ds->dyn_dtree;
1188 ds->bl_desc.dyn_tree = ds->bl_tree;
1189
1190 return Z_OK;
1191#endif /* MAXSEG_64K */
1192}
1193
1194/* ===========================================================================
1195 * Read a new buffer from the current input stream, update the adler32
1196 * and total number of bytes read. All deflate() input goes through
1197 * this function so some applications may wish to modify it to avoid
1198 * allocating a large strm->next_in buffer and copying from it.
1199 * (See also flush_pending()).
1200 */
1201ZLIB_INTERNAL unsigned deflate_read_buf(strm, buf, size)
1202 z_streamp strm;
1203 Bytef *buf;
1204 unsigned size;
1205{
1206 unsigned len = strm->avail_in;
1207
1208 if (len > size) len = size;
1209 if (len == 0) return 0;
1210
1211 strm->avail_in -= len;
1212
1213#ifdef GZIP
1214 if (strm->state->wrap == 2)
1215 copy_with_crc(strm, buf, len);
1216 else
1217#endif
1218 {
1219 zmemcpy(buf, strm->next_in, len);
1220 if (strm->state->wrap == 1)
1221 strm->adler = adler32(strm->adler, buf, len);
1222 }
1223 strm->next_in += len;
1224 strm->total_in += len;
1225
1226 return len;
1227}
1228
1229/* ===========================================================================
1230 * Initialize the "longest match" routines for a new zlib stream
1231 */
1232local void lm_init (s)
1233 deflate_state *s;
1234{
1235 s->window_size = (ulg)2L*s->w_size;
1236
1237 CLEAR_HASH(s);
1238
1239 /* Set the default configuration parameters:
1240 */
1241 s->max_lazy_match = configuration_table[s->level].max_lazy;
1242 s->good_match = configuration_table[s->level].good_length;
1243 s->nice_match = configuration_table[s->level].nice_length;
1244 s->max_chain_length = configuration_table[s->level].max_chain;
1245
1246 s->strstart = 0;
1247 s->block_start = 0L;
1248 s->lookahead = 0;
1249 s->insert = 0;
1250 s->match_length = s->prev_length = MIN_MATCH-1;
1251 s->match_available = 0;
1252 s->ins_h = 0;
1253#ifndef FASTEST
1254#ifdef ASMV
1255 match_init(); /* initialize the asm code */
1256#endif
1257#endif
1258}
1259
1260#ifndef FASTEST
1261/* ===========================================================================
1262 * Set match_start to the longest match starting at the given string and
1263 * return its length. Matches shorter or equal to prev_length are discarded,
1264 * in which case the result is equal to prev_length and match_start is
1265 * garbage.
1266 * IN assertions: cur_match is the head of the hash chain for the current
1267 * string (strstart) and its distance is <= MAX_DIST, and prev_length >= 1
1268 * OUT assertion: the match length is not greater than s->lookahead.
1269 */
1270#ifndef ASMV
1271/* For 80x86 and 680x0, an optimized version will be provided in match.asm or
1272 * match.S. The code will be functionally equivalent.
1273 */
1274local uInt longest_match(s, cur_match)
1275 deflate_state *s;
1276 IPos cur_match; /* current match */
1277{
1278 unsigned chain_length = s->max_chain_length;/* max hash chain length */
1279 register Bytef *scan = s->window + s->strstart; /* current string */
1280 register Bytef *match; /* matched string */
1281 register int len; /* length of current match */
1282 int best_len = (int)s->prev_length; /* best match length so far */
1283 int nice_match = s->nice_match; /* stop if match long enough */
1284 IPos limit = s->strstart > (IPos)MAX_DIST(s) ?
1285 s->strstart - (IPos)MAX_DIST(s) : NIL;
1286 /* Stop when cur_match becomes <= limit. To simplify the code,
1287 * we prevent matches with the string of window index 0.
1288 */
1289 Posf *prev = s->prev;
1290 uInt wmask = s->w_mask;
1291
1292#ifdef UNALIGNED_OK
1293 /* Compare two bytes at a time. Note: this is not always beneficial.
1294 * Try with and without -DUNALIGNED_OK to check.
1295 */
1296 register Bytef *strend = s->window + s->strstart + MAX_MATCH - 1;
1297 register ush scan_start = *(ushf*)scan;
1298 register ush scan_end = *(ushf*)(scan+best_len-1);
1299#else
1300 register Bytef *strend = s->window + s->strstart + MAX_MATCH;
1301 register Byte scan_end1 = scan[best_len-1];
1302 register Byte scan_end = scan[best_len];
1303#endif
1304
1305 /* The code is optimized for HASH_BITS >= 8 and MAX_MATCH-2 multiple of 16.
1306 * It is easy to get rid of this optimization if necessary.
1307 */
1308 Assert(s->hash_bits >= 8 && MAX_MATCH == 258, "Code too clever");
1309
1310 /* Do not waste too much time if we already have a good match: */
1311 if (s->prev_length >= s->good_match) {
1312 chain_length >>= 2;
1313 }
1314 /* Do not look for matches beyond the end of the input. This is necessary
1315 * to make deflate deterministic.
1316 */
1317 if ((uInt)nice_match > s->lookahead) nice_match = (int)s->lookahead;
1318
1319 Assert((ulg)s->strstart <= s->window_size-MIN_LOOKAHEAD, "need lookahead");
1320
1321 do {
1322 Assert(cur_match < s->strstart, "no future");
1323 match = s->window + cur_match;
1324
1325 /* Skip to next match if the match length cannot increase
1326 * or if the match length is less than 2. Note that the checks below
1327 * for insufficient lookahead only occur occasionally for performance
1328 * reasons. Therefore uninitialized memory will be accessed, and
1329 * conditional jumps will be made that depend on those values.
1330 * However the length of the match is limited to the lookahead, so
1331 * the output of deflate is not affected by the uninitialized values.
1332 */
1333#if (defined(UNALIGNED_OK) && MAX_MATCH == 258)
1334 /* This code assumes sizeof(unsigned short) == 2. Do not use
1335 * UNALIGNED_OK if your compiler uses a different size.
1336 */
1337 if (*(ushf*)(match+best_len-1) != scan_end ||
1338 *(ushf*)match != scan_start) continue;
1339
1340 /* It is not necessary to compare scan[2] and match[2] since they are
1341 * always equal when the other bytes match, given that the hash keys
1342 * are equal and that HASH_BITS >= 8. Compare 2 bytes at a time at
1343 * strstart+3, +5, ... up to strstart+257. We check for insufficient
1344 * lookahead only every 4th comparison; the 128th check will be made
1345 * at strstart+257. If MAX_MATCH-2 is not a multiple of 8, it is
1346 * necessary to put more guard bytes at the end of the window, or
1347 * to check more often for insufficient lookahead.
1348 */
1349 Assert(scan[2] == match[2], "scan[2]?");
1350 scan++, match++;
1351 do {
1352 } while (*(ushf*)(scan+=2) == *(ushf*)(match+=2) &&
1353 *(ushf*)(scan+=2) == *(ushf*)(match+=2) &&
1354 *(ushf*)(scan+=2) == *(ushf*)(match+=2) &&
1355 *(ushf*)(scan+=2) == *(ushf*)(match+=2) &&
1356 scan < strend);
1357 /* The funny "do {}" generates better code on most compilers */
1358
1359 /* Here, scan <= window+strstart+257 */
1360 Assert(scan <= s->window+(unsigned)(s->window_size-1), "wild scan");
1361 if (*scan == *match) scan++;
1362
1363 len = (MAX_MATCH - 1) - (int)(strend-scan);
1364 scan = strend - (MAX_MATCH-1);
1365
1366#else /* UNALIGNED_OK */
1367
1368 if (match[best_len] != scan_end ||
1369 match[best_len-1] != scan_end1 ||
1370 *match != *scan ||
1371 *++match != scan[1]) continue;
1372
1373 /* The check at best_len-1 can be removed because it will be made
1374 * again later. (This heuristic is not always a win.)
1375 * It is not necessary to compare scan[2] and match[2] since they
1376 * are always equal when the other bytes match, given that
1377 * the hash keys are equal and that HASH_BITS >= 8.
1378 */
1379 scan += 2, match++;
1380 Assert(*scan == *match, "match[2]?");
1381
1382 /* We check for insufficient lookahead only every 8th comparison;
1383 * the 256th check will be made at strstart+258.
1384 */
1385 do {
1386 } while (*++scan == *++match && *++scan == *++match &&
1387 *++scan == *++match && *++scan == *++match &&
1388 *++scan == *++match && *++scan == *++match &&
1389 *++scan == *++match && *++scan == *++match &&
1390 scan < strend);
1391
1392 Assert(scan <= s->window+(unsigned)(s->window_size-1), "wild scan");
1393
1394 len = MAX_MATCH - (int)(strend - scan);
1395 scan = strend - MAX_MATCH;
1396
1397#endif /* UNALIGNED_OK */
1398
1399 if (len > best_len) {
1400 s->match_start = cur_match;
1401 best_len = len;
1402 if (len >= nice_match) break;
1403#ifdef UNALIGNED_OK
1404 scan_end = *(ushf*)(scan+best_len-1);
1405#else
1406 scan_end1 = scan[best_len-1];
1407 scan_end = scan[best_len];
1408#endif
1409 }
1410 } while ((cur_match = prev[cur_match & wmask]) > limit
1411 && --chain_length != 0);
1412
1413 if ((uInt)best_len <= s->lookahead) return (uInt)best_len;
1414 return s->lookahead;
1415}
1416#endif /* ASMV */
1417
1418#else /* FASTEST */
1419
1420/* ---------------------------------------------------------------------------
1421 * Optimized version for FASTEST only
1422 */
1423local uInt longest_match(s, cur_match)
1424 deflate_state *s;
1425 IPos cur_match; /* current match */
1426{
1427 register Bytef *scan = s->window + s->strstart; /* current string */
1428 register Bytef *match; /* matched string */
1429 register int len; /* length of current match */
1430 register Bytef *strend = s->window + s->strstart + MAX_MATCH;
1431
1432 /* The code is optimized for HASH_BITS >= 8 and MAX_MATCH-2 multiple of 16.
1433 * It is easy to get rid of this optimization if necessary.
1434 */
1435 Assert(s->hash_bits >= 8 && MAX_MATCH == 258, "Code too clever");
1436
1437 Assert((ulg)s->strstart <= s->window_size-MIN_LOOKAHEAD, "need lookahead");
1438
1439 Assert(cur_match < s->strstart, "no future");
1440
1441 match = s->window + cur_match;
1442
1443 /* Return failure if the match length is less than 2:
1444 */
1445 if (match[0] != scan[0] || match[1] != scan[1]) return MIN_MATCH-1;
1446
1447 /* The check at best_len-1 can be removed because it will be made
1448 * again later. (This heuristic is not always a win.)
1449 * It is not necessary to compare scan[2] and match[2] since they
1450 * are always equal when the other bytes match, given that
1451 * the hash keys are equal and that HASH_BITS >= 8.
1452 */
1453 scan += 2, match += 2;
1454 Assert(*scan == *match, "match[2]?");
1455
1456 /* We check for insufficient lookahead only every 8th comparison;
1457 * the 256th check will be made at strstart+258.
1458 */
1459 do {
1460 } while (*++scan == *++match && *++scan == *++match &&
1461 *++scan == *++match && *++scan == *++match &&
1462 *++scan == *++match && *++scan == *++match &&
1463 *++scan == *++match && *++scan == *++match &&
1464 scan < strend);
1465
1466 Assert(scan <= s->window+(unsigned)(s->window_size-1), "wild scan");
1467
1468 len = MAX_MATCH - (int)(strend - scan);
1469
1470 if (len < MIN_MATCH) return MIN_MATCH - 1;
1471
1472 s->match_start = cur_match;
1473 return (uInt)len <= s->lookahead ? (uInt)len : s->lookahead;
1474}
1475
1476#endif /* FASTEST */
1477
1478#ifdef ZLIB_DEBUG
1479
1480#define EQUAL 0
1481/* result of memcmp for equal strings */
1482
1483/* ===========================================================================
1484 * Check that the match at match_start is indeed a match.
1485 */
1486local void check_match(s, start, match, length)
1487 deflate_state *s;
1488 IPos start, match;
1489 int length;
1490{
1491 /* check that the match is indeed a match */
1492 if (zmemcmp(s->window + match,
1493 s->window + start, length) != EQUAL) {
1494 fprintf(stderr, " start %u, match %u, length %d\n",
1495 start, match, length);
1496 do {
1497 fprintf(stderr, "%c%c", s->window[match++], s->window[start++]);
1498 } while (--length != 0);
1499 z_error("invalid match");
1500 }
1501 if (z_verbose > 1) {
1502 fprintf(stderr,"\\[%d,%d]", start-match, length);
1503 do { putc(s->window[start++], stderr); } while (--length != 0);
1504 }
1505}
1506#else
1507# define check_match(s, start, match, length)
1508#endif /* ZLIB_DEBUG */
1509
1510/* ===========================================================================
1511 * Fill the window when the lookahead becomes insufficient.
1512 * Updates strstart and lookahead.
1513 *
1514 * IN assertion: lookahead < MIN_LOOKAHEAD
1515 * OUT assertions: strstart <= window_size-MIN_LOOKAHEAD
1516 * At least one byte has been read, or avail_in == 0; reads are
1517 * performed for at least two bytes (required for the zip translate_eol
1518 * option -- not supported here).
1519 */
1520local void fill_window_c(deflate_state *s);
1521
1522local void fill_window(deflate_state *s)
1523{
1524#ifdef DEFLATE_FILL_WINDOW_SSE2
1525 if (x86_cpu_enable_simd) {
1526 fill_window_sse(s);
1527 return;
1528 }
1529#endif
1530 fill_window_c(s);
1531}
1532
1533local void fill_window_c(s)
1534 deflate_state *s;
1535{
1536 unsigned n;
1537 unsigned more; /* Amount of free space at the end of the window. */
1538 uInt wsize = s->w_size;
1539
1540 Assert(s->lookahead < MIN_LOOKAHEAD, "already enough lookahead");
1541
1542 do {
1543 more = (unsigned)(s->window_size -(ulg)s->lookahead -(ulg)s->strstart);
1544
1545 /* Deal with !@#$% 64K limit: */
1546 if (sizeof(int) <= 2) {
1547 if (more == 0 && s->strstart == 0 && s->lookahead == 0) {
1548 more = wsize;
1549
1550 } else if (more == (unsigned)(-1)) {
1551 /* Very unlikely, but possible on 16 bit machine if
1552 * strstart == 0 && lookahead == 1 (input done a byte at time)
1553 */
1554 more--;
1555 }
1556 }
1557
1558 /* If the window is almost full and there is insufficient lookahead,
1559 * move the upper half to the lower one to make room in the upper half.
1560 */
1561 if (s->strstart >= wsize+MAX_DIST(s)) {
1562
1563 zmemcpy(s->window, s->window+wsize, (unsigned)wsize - more);
1564 s->match_start -= wsize;
1565 s->strstart -= wsize; /* we now have strstart >= MAX_DIST */
1566 s->block_start -= (long) wsize;
1567 slide_hash(s);
1568 more += wsize;
1569 }
1570 if (s->strm->avail_in == 0) break;
1571
1572 /* If there was no sliding:
1573 * strstart <= WSIZE+MAX_DIST-1 && lookahead <= MIN_LOOKAHEAD - 1 &&
1574 * more == window_size - lookahead - strstart
1575 * => more >= window_size - (MIN_LOOKAHEAD-1 + WSIZE + MAX_DIST-1)
1576 * => more >= window_size - 2*WSIZE + 2
1577 * In the BIG_MEM or MMAP case (not yet supported),
1578 * window_size == input_size + MIN_LOOKAHEAD &&
1579 * strstart + s->lookahead <= input_size => more >= MIN_LOOKAHEAD.
1580 * Otherwise, window_size == 2*WSIZE so more >= 2.
1581 * If there was sliding, more >= WSIZE. So in all cases, more >= 2.
1582 */
1583 Assert(more >= 2, "more < 2");
1584
1585 n = deflate_read_buf(s->strm, s->window + s->strstart + s->lookahead, more);
1586 s->lookahead += n;
1587
1588 /* Initialize the hash value now that we have some input: */
1589 if (s->lookahead + s->insert >= MIN_MATCH) {
1590 uInt str = s->strstart - s->insert;
1591 s->ins_h = s->window[str];
1592 UPDATE_HASH(s, s->ins_h, s->window[str + 1]);
1593#if MIN_MATCH != 3
1594 Call UPDATE_HASH() MIN_MATCH-3 more times
1595#endif
1596 while (s->insert) {
1597 UPDATE_HASH(s, s->ins_h, s->window[str + MIN_MATCH-1]);
1598#ifndef FASTEST
1599 s->prev[str & s->w_mask] = s->head[s->ins_h];
1600#endif
1601 s->head[s->ins_h] = (Pos)str;
1602 str++;
1603 s->insert--;
1604 if (s->lookahead + s->insert < MIN_MATCH)
1605 break;
1606 }
1607 }
1608 /* If the whole input has less than MIN_MATCH bytes, ins_h is garbage,
1609 * but this is not important since only literal bytes will be emitted.
1610 */
1611
1612 } while (s->lookahead < MIN_LOOKAHEAD && s->strm->avail_in != 0);
1613
1614 /* If the WIN_INIT bytes after the end of the current data have never been
1615 * written, then zero those bytes in order to avoid memory check reports of
1616 * the use of uninitialized (or uninitialised as Julian writes) bytes by
1617 * the longest match routines. Update the high water mark for the next
1618 * time through here. WIN_INIT is set to MAX_MATCH since the longest match
1619 * routines allow scanning to strstart + MAX_MATCH, ignoring lookahead.
1620 */
1621 if (s->high_water < s->window_size) {
1622 ulg curr = s->strstart + (ulg)(s->lookahead);
1623 ulg init;
1624
1625 if (s->high_water < curr) {
1626 /* Previous high water mark below current data -- zero WIN_INIT
1627 * bytes or up to end of window, whichever is less.
1628 */
1629 init = s->window_size - curr;
1630 if (init > WIN_INIT)
1631 init = WIN_INIT;
1632 zmemzero(s->window + curr, (unsigned)init);
1633 s->high_water = curr + init;
1634 }
1635 else if (s->high_water < (ulg)curr + WIN_INIT) {
1636 /* High water mark at or above current data, but below current data
1637 * plus WIN_INIT -- zero out to current data plus WIN_INIT, or up
1638 * to end of window, whichever is less.
1639 */
1640 init = (ulg)curr + WIN_INIT - s->high_water;
1641 if (init > s->window_size - s->high_water)
1642 init = s->window_size - s->high_water;
1643 zmemzero(s->window + s->high_water, (unsigned)init);
1644 s->high_water += init;
1645 }
1646 }
1647
1648 Assert((ulg)s->strstart <= s->window_size - MIN_LOOKAHEAD,
1649 "not enough room for search");
1650}
1651
1652/* ===========================================================================
1653 * Flush the current block, with given end-of-file flag.
1654 * IN assertion: strstart is set to the end of the current match.
1655 */
1656#define FLUSH_BLOCK_ONLY(s, last) { \
1657 _tr_flush_block(s, (s->block_start >= 0L ? \
1658 (charf *)&s->window[(unsigned)s->block_start] : \
1659 (charf *)Z_NULL), \
1660 (ulg)((long)s->strstart - s->block_start), \
1661 (last)); \
1662 s->block_start = s->strstart; \
1663 flush_pending(s->strm); \
1664 Tracev((stderr,"[FLUSH]")); \
1665}
1666
1667/* Same but force premature exit if necessary. */
1668#define FLUSH_BLOCK(s, last) { \
1669 FLUSH_BLOCK_ONLY(s, last); \
1670 if (s->strm->avail_out == 0) return (last) ? finish_started : need_more; \
1671}
1672
1673/* Maximum stored block length in deflate format (not including header). */
1674#define MAX_STORED 65535
1675
1676/* Minimum of a and b. */
1677#define MIN(a, b) ((a) > (b) ? (b) : (a))
1678
1679/* ===========================================================================
1680 * Copy without compression as much as possible from the input stream, return
1681 * the current block state.
1682 *
1683 * In case deflateParams() is used to later switch to a non-zero compression
1684 * level, s->matches (otherwise unused when storing) keeps track of the number
1685 * of hash table slides to perform. If s->matches is 1, then one hash table
1686 * slide will be done when switching. If s->matches is 2, the maximum value
1687 * allowed here, then the hash table will be cleared, since two or more slides
1688 * is the same as a clear.
1689 *
1690 * deflate_stored() is written to minimize the number of times an input byte is
1691 * copied. It is most efficient with large input and output buffers, which
1692 * maximizes the opportunites to have a single copy from next_in to next_out.
1693 */
1694local block_state deflate_stored(s, flush)
1695 deflate_state *s;
1696 int flush;
1697{
1698 /* Smallest worthy block size when not flushing or finishing. By default
1699 * this is 32K. This can be as small as 507 bytes for memLevel == 1. For
1700 * large input and output buffers, the stored block size will be larger.
1701 */
1702 unsigned min_block = MIN(s->pending_buf_size - 5, s->w_size);
1703
1704 /* Copy as many min_block or larger stored blocks directly to next_out as
1705 * possible. If flushing, copy the remaining available input to next_out as
1706 * stored blocks, if there is enough space.
1707 */
1708 unsigned len, left, have, last = 0;
1709 unsigned used = s->strm->avail_in;
1710 do {
1711 /* Set len to the maximum size block that we can copy directly with the
1712 * available input data and output space. Set left to how much of that
1713 * would be copied from what's left in the window.
1714 */
1715 len = MAX_STORED; /* maximum deflate stored block length */
1716 have = (s->bi_valid + 42) >> 3; /* number of header bytes */
1717 if (s->strm->avail_out < have) /* need room for header */
1718 break;
1719 /* maximum stored block length that will fit in avail_out: */
1720 have = s->strm->avail_out - have;
1721 left = s->strstart - s->block_start; /* bytes left in window */
1722 if (len > (ulg)left + s->strm->avail_in)
1723 len = left + s->strm->avail_in; /* limit len to the input */
1724 if (len > have)
1725 len = have; /* limit len to the output */
1726
1727 /* If the stored block would be less than min_block in length, or if
1728 * unable to copy all of the available input when flushing, then try
1729 * copying to the window and the pending buffer instead. Also don't
1730 * write an empty block when flushing -- deflate() does that.
1731 */
1732 if (len < min_block && ((len == 0 && flush != Z_FINISH) ||
1733 flush == Z_NO_FLUSH ||
1734 len != left + s->strm->avail_in))
1735 break;
1736
1737 /* Make a dummy stored block in pending to get the header bytes,
1738 * including any pending bits. This also updates the debugging counts.
1739 */
1740 last = flush == Z_FINISH && len == left + s->strm->avail_in ? 1 : 0;
1741 _tr_stored_block(s, (char *)0, 0L, last);
1742
1743 /* Replace the lengths in the dummy stored block with len. */
1744 s->pending_buf[s->pending - 4] = len;
1745 s->pending_buf[s->pending - 3] = len >> 8;
1746 s->pending_buf[s->pending - 2] = ~len;
1747 s->pending_buf[s->pending - 1] = ~len >> 8;
1748
1749 /* Write the stored block header bytes. */
1750 flush_pending(s->strm);
1751
1752#ifdef ZLIB_DEBUG
1753 /* Update debugging counts for the data about to be copied. */
1754 s->compressed_len += len << 3;
1755 s->bits_sent += len << 3;
1756#endif
1757
1758 /* Copy uncompressed bytes from the window to next_out. */
1759 if (left) {
1760 if (left > len)
1761 left = len;
1762 zmemcpy(s->strm->next_out, s->window + s->block_start, left);
1763 s->strm->next_out += left;
1764 s->strm->avail_out -= left;
1765 s->strm->total_out += left;
1766 s->block_start += left;
1767 len -= left;
1768 }
1769
1770 /* Copy uncompressed bytes directly from next_in to next_out, updating
1771 * the check value.
1772 */
1773 if (len) {
1774 deflate_read_buf(s->strm, s->strm->next_out, len);
1775 s->strm->next_out += len;
1776 s->strm->avail_out -= len;
1777 s->strm->total_out += len;
1778 }
1779 } while (last == 0);
1780
1781 /* Update the sliding window with the last s->w_size bytes of the copied
1782 * data, or append all of the copied data to the existing window if less
1783 * than s->w_size bytes were copied. Also update the number of bytes to
1784 * insert in the hash tables, in the event that deflateParams() switches to
1785 * a non-zero compression level.
1786 */
1787 used -= s->strm->avail_in; /* number of input bytes directly copied */
1788 if (used) {
1789 /* If any input was used, then no unused input remains in the window,
1790 * therefore s->block_start == s->strstart.
1791 */
1792 if (used >= s->w_size) { /* supplant the previous history */
1793 s->matches = 2; /* clear hash */
1794 zmemcpy(s->window, s->strm->next_in - s->w_size, s->w_size);
1795 s->strstart = s->w_size;
1796 }
1797 else {
1798 if (s->window_size - s->strstart <= used) {
1799 /* Slide the window down. */
1800 s->strstart -= s->w_size;
1801 zmemcpy(s->window, s->window + s->w_size, s->strstart);
1802 if (s->matches < 2)
1803 s->matches++; /* add a pending slide_hash() */
1804 }
1805 zmemcpy(s->window + s->strstart, s->strm->next_in - used, used);
1806 s->strstart += used;
1807 }
1808 s->block_start = s->strstart;
1809 s->insert += MIN(used, s->w_size - s->insert);
1810 }
1811 if (s->high_water < s->strstart)
1812 s->high_water = s->strstart;
1813
1814 /* If the last block was written to next_out, then done. */
1815 if (last)
1816 return finish_done;
1817
1818 /* If flushing and all input has been consumed, then done. */
1819 if (flush != Z_NO_FLUSH && flush != Z_FINISH &&
1820 s->strm->avail_in == 0 && (long)s->strstart == s->block_start)
1821 return block_done;
1822
1823 /* Fill the window with any remaining input. */
1824 have = s->window_size - s->strstart - 1;
1825 if (s->strm->avail_in > have && s->block_start >= (long)s->w_size) {
1826 /* Slide the window down. */
1827 s->block_start -= s->w_size;
1828 s->strstart -= s->w_size;
1829 zmemcpy(s->window, s->window + s->w_size, s->strstart);
1830 if (s->matches < 2)
1831 s->matches++; /* add a pending slide_hash() */
1832 have += s->w_size; /* more space now */
1833 }
1834 if (have > s->strm->avail_in)
1835 have = s->strm->avail_in;
1836 if (have) {
1837 deflate_read_buf(s->strm, s->window + s->strstart, have);
1838 s->strstart += have;
1839 }
1840 if (s->high_water < s->strstart)
1841 s->high_water = s->strstart;
1842
1843 /* There was not enough avail_out to write a complete worthy or flushed
1844 * stored block to next_out. Write a stored block to pending instead, if we
1845 * have enough input for a worthy block, or if flushing and there is enough
1846 * room for the remaining input as a stored block in the pending buffer.
1847 */
1848 have = (s->bi_valid + 42) >> 3; /* number of header bytes */
1849 /* maximum stored block length that will fit in pending: */
1850 have = MIN(s->pending_buf_size - have, MAX_STORED);
1851 min_block = MIN(have, s->w_size);
1852 left = s->strstart - s->block_start;
1853 if (left >= min_block ||
1854 ((left || flush == Z_FINISH) && flush != Z_NO_FLUSH &&
1855 s->strm->avail_in == 0 && left <= have)) {
1856 len = MIN(left, have);
1857 last = flush == Z_FINISH && s->strm->avail_in == 0 &&
1858 len == left ? 1 : 0;
1859 _tr_stored_block(s, (charf *)s->window + s->block_start, len, last);
1860 s->block_start += len;
1861 flush_pending(s->strm);
1862 }
1863
1864 /* We've done all we can with the available input and output. */
1865 return last ? finish_started : need_more;
1866}
1867
1868/* ===========================================================================
1869 * Compress as much as possible from the input stream, return the current
1870 * block state.
1871 * This function does not perform lazy evaluation of matches and inserts
1872 * new strings in the dictionary only for unmatched strings or for short
1873 * matches. It is used only for the fast compression options.
1874 */
1875local block_state deflate_fast(s, flush)
1876 deflate_state *s;
1877 int flush;
1878{
1879 IPos hash_head; /* head of the hash chain */
1880 int bflush; /* set if current block must be flushed */
1881
1882 for (;;) {
1883 /* Make sure that we always have enough lookahead, except
1884 * at the end of the input file. We need MAX_MATCH bytes
1885 * for the next match, plus MIN_MATCH bytes to insert the
1886 * string following the next match.
1887 */
1888 if (s->lookahead < MIN_LOOKAHEAD) {
1889 fill_window(s);
1890 if (s->lookahead < MIN_LOOKAHEAD && flush == Z_NO_FLUSH) {
1891 return need_more;
1892 }
1893 if (s->lookahead == 0) break; /* flush the current block */
1894 }
1895
1896 /* Insert the string window[strstart .. strstart+2] in the
1897 * dictionary, and set hash_head to the head of the hash chain:
1898 */
1899 hash_head = NIL;
1900 if (s->lookahead >= MIN_MATCH) {
1901 hash_head = insert_string(s, s->strstart);
1902 }
1903
1904 /* Find the longest match, discarding those <= prev_length.
1905 * At this point we have always match_length < MIN_MATCH
1906 */
1907 if (hash_head != NIL && s->strstart - hash_head <= MAX_DIST(s)) {
1908 /* To simplify the code, we prevent matches with the string
1909 * of window index 0 (in particular we have to avoid a match
1910 * of the string with itself at the start of the input file).
1911 */
1912 s->match_length = longest_match (s, hash_head);
1913 /* longest_match() sets match_start */
1914 }
1915 if (s->match_length >= MIN_MATCH) {
1916 check_match(s, s->strstart, s->match_start, s->match_length);
1917
1918 _tr_tally_dist(s, s->strstart - s->match_start,
1919 s->match_length - MIN_MATCH, bflush);
1920
1921 s->lookahead -= s->match_length;
1922
1923 /* Insert new strings in the hash table only if the match length
1924 * is not too large. This saves time but degrades compression.
1925 */
1926#ifndef FASTEST
1927 if (s->match_length <= s->max_insert_length &&
1928 s->lookahead >= MIN_MATCH) {
1929 s->match_length--; /* string at strstart already in table */
1930 do {
1931 s->strstart++;
1932 hash_head = insert_string(s, s->strstart);
1933 /* strstart never exceeds WSIZE-MAX_MATCH, so there are
1934 * always MIN_MATCH bytes ahead.
1935 */
1936 } while (--s->match_length != 0);
1937 s->strstart++;
1938 } else
1939#endif
1940 {
1941 s->strstart += s->match_length;
1942 s->match_length = 0;
1943 s->ins_h = s->window[s->strstart];
1944 UPDATE_HASH(s, s->ins_h, s->window[s->strstart+1]);
1945#if MIN_MATCH != 3
1946 Call UPDATE_HASH() MIN_MATCH-3 more times
1947#endif
1948 /* If lookahead < MIN_MATCH, ins_h is garbage, but it does not
1949 * matter since it will be recomputed at next deflate call.
1950 */
1951 }
1952 } else {
1953 /* No match, output a literal byte */
1954 Tracevv((stderr,"%c", s->window[s->strstart]));
1955 _tr_tally_lit (s, s->window[s->strstart], bflush);
1956 s->lookahead--;
1957 s->strstart++;
1958 }
1959 if (bflush) FLUSH_BLOCK(s, 0);
1960 }
1961 s->insert = s->strstart < MIN_MATCH-1 ? s->strstart : MIN_MATCH-1;
1962 if (flush == Z_FINISH) {
1963 FLUSH_BLOCK(s, 1);
1964 return finish_done;
1965 }
1966 if (s->sym_next)
1967 FLUSH_BLOCK(s, 0);
1968 return block_done;
1969}
1970
1971#ifndef FASTEST
1972/* ===========================================================================
1973 * Same as above, but achieves better compression. We use a lazy
1974 * evaluation for matches: a match is finally adopted only if there is
1975 * no better match at the next window position.
1976 */
1977local block_state deflate_slow(s, flush)
1978 deflate_state *s;
1979 int flush;
1980{
1981 IPos hash_head; /* head of hash chain */
1982 int bflush; /* set if current block must be flushed */
1983
1984 /* Process the input block. */
1985 for (;;) {
1986 /* Make sure that we always have enough lookahead, except
1987 * at the end of the input file. We need MAX_MATCH bytes
1988 * for the next match, plus MIN_MATCH bytes to insert the
1989 * string following the next match.
1990 */
1991 if (s->lookahead < MIN_LOOKAHEAD) {
1992 fill_window(s);
1993 if (s->lookahead < MIN_LOOKAHEAD && flush == Z_NO_FLUSH) {
1994 return need_more;
1995 }
1996 if (s->lookahead == 0) break; /* flush the current block */
1997 }
1998
1999 /* Insert the string window[strstart .. strstart+2] in the
2000 * dictionary, and set hash_head to the head of the hash chain:
2001 */
2002 hash_head = NIL;
2003 if (s->lookahead >= MIN_MATCH) {
2004 hash_head = insert_string(s, s->strstart);
2005 }
2006
2007 /* Find the longest match, discarding those <= prev_length.
2008 */
2009 s->prev_length = s->match_length, s->prev_match = s->match_start;
2010 s->match_length = MIN_MATCH-1;
2011
2012 if (hash_head != NIL && s->prev_length < s->max_lazy_match &&
2013 s->strstart - hash_head <= MAX_DIST(s)) {
2014 /* To simplify the code, we prevent matches with the string
2015 * of window index 0 (in particular we have to avoid a match
2016 * of the string with itself at the start of the input file).
2017 */
2018 s->match_length = longest_match (s, hash_head);
2019 /* longest_match() sets match_start */
2020
2021 if (s->match_length <= 5 && (s->strategy == Z_FILTERED
2022#if TOO_FAR <= 32767
2023 || (s->match_length == MIN_MATCH &&
2024 s->strstart - s->match_start > TOO_FAR)
2025#endif
2026 )) {
2027
2028 /* If prev_match is also MIN_MATCH, match_start is garbage
2029 * but we will ignore the current match anyway.
2030 */
2031 s->match_length = MIN_MATCH-1;
2032 }
2033 }
2034 /* If there was a match at the previous step and the current
2035 * match is not better, output the previous match:
2036 */
2037 if (s->prev_length >= MIN_MATCH && s->match_length <= s->prev_length) {
2038 uInt max_insert = s->strstart + s->lookahead - MIN_MATCH;
2039 /* Do not insert strings in hash table beyond this. */
2040
2041 check_match(s, s->strstart-1, s->prev_match, s->prev_length);
2042
2043 _tr_tally_dist(s, s->strstart -1 - s->prev_match,
2044 s->prev_length - MIN_MATCH, bflush);
2045
2046 /* Insert in hash table all strings up to the end of the match.
2047 * strstart-1 and strstart are already inserted. If there is not
2048 * enough lookahead, the last two strings are not inserted in
2049 * the hash table.
2050 */
2051 s->lookahead -= s->prev_length-1;
2052 s->prev_length -= 2;
2053 do {
2054 if (++s->strstart <= max_insert) {
2055 hash_head = insert_string(s, s->strstart);
2056 }
2057 } while (--s->prev_length != 0);
2058 s->match_available = 0;
2059 s->match_length = MIN_MATCH-1;
2060 s->strstart++;
2061
2062 if (bflush) FLUSH_BLOCK(s, 0);
2063
2064 } else if (s->match_available) {
2065 /* If there was no match at the previous position, output a
2066 * single literal. If there was a match but the current match
2067 * is longer, truncate the previous match to a single literal.
2068 */
2069 Tracevv((stderr,"%c", s->window[s->strstart-1]));
2070 _tr_tally_lit(s, s->window[s->strstart-1], bflush);
2071 if (bflush) {
2072 FLUSH_BLOCK_ONLY(s, 0);
2073 }
2074 s->strstart++;
2075 s->lookahead--;
2076 if (s->strm->avail_out == 0) return need_more;
2077 } else {
2078 /* There is no previous match to compare with, wait for
2079 * the next step to decide.
2080 */
2081 s->match_available = 1;
2082 s->strstart++;
2083 s->lookahead--;
2084 }
2085 }
2086 Assert (flush != Z_NO_FLUSH, "no flush?");
2087 if (s->match_available) {
2088 Tracevv((stderr,"%c", s->window[s->strstart-1]));
2089 _tr_tally_lit(s, s->window[s->strstart-1], bflush);
2090 s->match_available = 0;
2091 }
2092 s->insert = s->strstart < MIN_MATCH-1 ? s->strstart : MIN_MATCH-1;
2093 if (flush == Z_FINISH) {
2094 FLUSH_BLOCK(s, 1);
2095 return finish_done;
2096 }
2097 if (s->sym_next)
2098 FLUSH_BLOCK(s, 0);
2099 return block_done;
2100}
2101#endif /* FASTEST */
2102
2103/* ===========================================================================
2104 * For Z_RLE, simply look for runs of bytes, generate matches only of distance
2105 * one. Do not maintain a hash table. (It will be regenerated if this run of
2106 * deflate switches away from Z_RLE.)
2107 */
2108local block_state deflate_rle(s, flush)
2109 deflate_state *s;
2110 int flush;
2111{
2112 int bflush; /* set if current block must be flushed */
2113 uInt prev; /* byte at distance one to match */
2114 Bytef *scan, *strend; /* scan goes up to strend for length of run */
2115
2116 for (;;) {
2117 /* Make sure that we always have enough lookahead, except
2118 * at the end of the input file. We need MAX_MATCH bytes
2119 * for the longest run, plus one for the unrolled loop.
2120 */
2121 if (s->lookahead <= MAX_MATCH) {
2122 fill_window(s);
2123 if (s->lookahead <= MAX_MATCH && flush == Z_NO_FLUSH) {
2124 return need_more;
2125 }
2126 if (s->lookahead == 0) break; /* flush the current block */
2127 }
2128
2129 /* See how many times the previous byte repeats */
2130 s->match_length = 0;
2131 if (s->lookahead >= MIN_MATCH && s->strstart > 0) {
2132 scan = s->window + s->strstart - 1;
2133 prev = *scan;
2134 if (prev == *++scan && prev == *++scan && prev == *++scan) {
2135 strend = s->window + s->strstart + MAX_MATCH;
2136 do {
2137 } while (prev == *++scan && prev == *++scan &&
2138 prev == *++scan && prev == *++scan &&
2139 prev == *++scan && prev == *++scan &&
2140 prev == *++scan && prev == *++scan &&
2141 scan < strend);
2142 s->match_length = MAX_MATCH - (uInt)(strend - scan);
2143 if (s->match_length > s->lookahead)
2144 s->match_length = s->lookahead;
2145 }
2146 Assert(scan <= s->window+(uInt)(s->window_size-1), "wild scan");
2147 }
2148
2149 /* Emit match if have run of MIN_MATCH or longer, else emit literal */
2150 if (s->match_length >= MIN_MATCH) {
2151 check_match(s, s->strstart, s->strstart - 1, s->match_length);
2152
2153 _tr_tally_dist(s, 1, s->match_length - MIN_MATCH, bflush);
2154
2155 s->lookahead -= s->match_length;
2156 s->strstart += s->match_length;
2157 s->match_length = 0;
2158 } else {
2159 /* No match, output a literal byte */
2160 Tracevv((stderr,"%c", s->window[s->strstart]));
2161 _tr_tally_lit (s, s->window[s->strstart], bflush);
2162 s->lookahead--;
2163 s->strstart++;
2164 }
2165 if (bflush) FLUSH_BLOCK(s, 0);
2166 }
2167 s->insert = 0;
2168 if (flush == Z_FINISH) {
2169 FLUSH_BLOCK(s, 1);
2170 return finish_done;
2171 }
2172 if (s->sym_next)
2173 FLUSH_BLOCK(s, 0);
2174 return block_done;
2175}
2176
2177/* ===========================================================================
2178 * For Z_HUFFMAN_ONLY, do not look for matches. Do not maintain a hash table.
2179 * (It will be regenerated if this run of deflate switches away from Huffman.)
2180 */
2181local block_state deflate_huff(s, flush)
2182 deflate_state *s;
2183 int flush;
2184{
2185 int bflush; /* set if current block must be flushed */
2186
2187 for (;;) {
2188 /* Make sure that we have a literal to write. */
2189 if (s->lookahead == 0) {
2190 fill_window(s);
2191 if (s->lookahead == 0) {
2192 if (flush == Z_NO_FLUSH)
2193 return need_more;
2194 break; /* flush the current block */
2195 }
2196 }
2197
2198 /* Output a literal byte */
2199 s->match_length = 0;
2200 Tracevv((stderr,"%c", s->window[s->strstart]));
2201 _tr_tally_lit (s, s->window[s->strstart], bflush);
2202 s->lookahead--;
2203 s->strstart++;
2204 if (bflush) FLUSH_BLOCK(s, 0);
2205 }
2206 s->insert = 0;
2207 if (flush == Z_FINISH) {
2208 FLUSH_BLOCK(s, 1);
2209 return finish_done;
2210 }
2211 if (s->sym_next)
2212 FLUSH_BLOCK(s, 0);
2213 return block_done;
2214}
2215