1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
1.2 +++ b/modules/zlib/src/deflate.c Wed Dec 31 06:09:35 2014 +0100
1.3 @@ -0,0 +1,1967 @@
1.4 +/* deflate.c -- compress data using the deflation algorithm
1.5 + * Copyright (C) 1995-2013 Jean-loup Gailly and Mark Adler
1.6 + * For conditions of distribution and use, see copyright notice in zlib.h
1.7 + */
1.8 +
1.9 +/*
1.10 + * ALGORITHM
1.11 + *
1.12 + * The "deflation" process depends on being able to identify portions
1.13 + * of the input text which are identical to earlier input (within a
1.14 + * sliding window trailing behind the input currently being processed).
1.15 + *
1.16 + * The most straightforward technique turns out to be the fastest for
1.17 + * most input files: try all possible matches and select the longest.
1.18 + * The key feature of this algorithm is that insertions into the string
1.19 + * dictionary are very simple and thus fast, and deletions are avoided
1.20 + * completely. Insertions are performed at each input character, whereas
1.21 + * string matches are performed only when the previous match ends. So it
1.22 + * is preferable to spend more time in matches to allow very fast string
1.23 + * insertions and avoid deletions. The matching algorithm for small
1.24 + * strings is inspired from that of Rabin & Karp. A brute force approach
1.25 + * is used to find longer strings when a small match has been found.
1.26 + * A similar algorithm is used in comic (by Jan-Mark Wams) and freeze
1.27 + * (by Leonid Broukhis).
1.28 + * A previous version of this file used a more sophisticated algorithm
1.29 + * (by Fiala and Greene) which is guaranteed to run in linear amortized
1.30 + * time, but has a larger average cost, uses more memory and is patented.
1.31 + * However the F&G algorithm may be faster for some highly redundant
1.32 + * files if the parameter max_chain_length (described below) is too large.
1.33 + *
1.34 + * ACKNOWLEDGEMENTS
1.35 + *
1.36 + * The idea of lazy evaluation of matches is due to Jan-Mark Wams, and
1.37 + * I found it in 'freeze' written by Leonid Broukhis.
1.38 + * Thanks to many people for bug reports and testing.
1.39 + *
1.40 + * REFERENCES
1.41 + *
1.42 + * Deutsch, L.P.,"DEFLATE Compressed Data Format Specification".
1.43 + * Available in http://tools.ietf.org/html/rfc1951
1.44 + *
1.45 + * A description of the Rabin and Karp algorithm is given in the book
1.46 + * "Algorithms" by R. Sedgewick, Addison-Wesley, p252.
1.47 + *
1.48 + * Fiala,E.R., and Greene,D.H.
1.49 + * Data Compression with Finite Windows, Comm.ACM, 32,4 (1989) 490-595
1.50 + *
1.51 + */
1.52 +
1.53 +/* @(#) $Id$ */
1.54 +
1.55 +#include "deflate.h"
1.56 +
1.57 +const char deflate_copyright[] =
1.58 + " deflate 1.2.8 Copyright 1995-2013 Jean-loup Gailly and Mark Adler ";
1.59 +/*
1.60 + If you use the zlib library in a product, an acknowledgment is welcome
1.61 + in the documentation of your product. If for some reason you cannot
1.62 + include such an acknowledgment, I would appreciate that you keep this
1.63 + copyright string in the executable of your product.
1.64 + */
1.65 +
1.66 +/* ===========================================================================
1.67 + * Function prototypes.
1.68 + */
1.69 +typedef enum {
1.70 + need_more, /* block not completed, need more input or more output */
1.71 + block_done, /* block flush performed */
1.72 + finish_started, /* finish started, need only more output at next deflate */
1.73 + finish_done /* finish done, accept no more input or output */
1.74 +} block_state;
1.75 +
1.76 +typedef block_state (*compress_func) OF((deflate_state *s, int flush));
1.77 +/* Compression function. Returns the block state after the call. */
1.78 +
1.79 +local void fill_window OF((deflate_state *s));
1.80 +local block_state deflate_stored OF((deflate_state *s, int flush));
1.81 +local block_state deflate_fast OF((deflate_state *s, int flush));
1.82 +#ifndef FASTEST
1.83 +local block_state deflate_slow OF((deflate_state *s, int flush));
1.84 +#endif
1.85 +local block_state deflate_rle OF((deflate_state *s, int flush));
1.86 +local block_state deflate_huff OF((deflate_state *s, int flush));
1.87 +local void lm_init OF((deflate_state *s));
1.88 +local void putShortMSB OF((deflate_state *s, uInt b));
1.89 +local void flush_pending OF((z_streamp strm));
1.90 +local int read_buf OF((z_streamp strm, Bytef *buf, unsigned size));
1.91 +#ifdef ASMV
1.92 + void match_init OF((void)); /* asm code initialization */
1.93 + uInt longest_match OF((deflate_state *s, IPos cur_match));
1.94 +#else
1.95 +local uInt longest_match OF((deflate_state *s, IPos cur_match));
1.96 +#endif
1.97 +
1.98 +#ifdef DEBUG
1.99 +local void check_match OF((deflate_state *s, IPos start, IPos match,
1.100 + int length));
1.101 +#endif
1.102 +
1.103 +/* ===========================================================================
1.104 + * Local data
1.105 + */
1.106 +
1.107 +#define NIL 0
1.108 +/* Tail of hash chains */
1.109 +
1.110 +#ifndef TOO_FAR
1.111 +# define TOO_FAR 4096
1.112 +#endif
1.113 +/* Matches of length 3 are discarded if their distance exceeds TOO_FAR */
1.114 +
1.115 +/* Values for max_lazy_match, good_match and max_chain_length, depending on
1.116 + * the desired pack level (0..9). The values given below have been tuned to
1.117 + * exclude worst case performance for pathological files. Better values may be
1.118 + * found for specific files.
1.119 + */
1.120 +typedef struct config_s {
1.121 + ush good_length; /* reduce lazy search above this match length */
1.122 + ush max_lazy; /* do not perform lazy search above this match length */
1.123 + ush nice_length; /* quit search above this match length */
1.124 + ush max_chain;
1.125 + compress_func func;
1.126 +} config;
1.127 +
1.128 +#ifdef FASTEST
1.129 +local const config configuration_table[2] = {
1.130 +/* good lazy nice chain */
1.131 +/* 0 */ {0, 0, 0, 0, deflate_stored}, /* store only */
1.132 +/* 1 */ {4, 4, 8, 4, deflate_fast}}; /* max speed, no lazy matches */
1.133 +#else
1.134 +local const config configuration_table[10] = {
1.135 +/* good lazy nice chain */
1.136 +/* 0 */ {0, 0, 0, 0, deflate_stored}, /* store only */
1.137 +/* 1 */ {4, 4, 8, 4, deflate_fast}, /* max speed, no lazy matches */
1.138 +/* 2 */ {4, 5, 16, 8, deflate_fast},
1.139 +/* 3 */ {4, 6, 32, 32, deflate_fast},
1.140 +
1.141 +/* 4 */ {4, 4, 16, 16, deflate_slow}, /* lazy matches */
1.142 +/* 5 */ {8, 16, 32, 32, deflate_slow},
1.143 +/* 6 */ {8, 16, 128, 128, deflate_slow},
1.144 +/* 7 */ {8, 32, 128, 256, deflate_slow},
1.145 +/* 8 */ {32, 128, 258, 1024, deflate_slow},
1.146 +/* 9 */ {32, 258, 258, 4096, deflate_slow}}; /* max compression */
1.147 +#endif
1.148 +
1.149 +/* Note: the deflate() code requires max_lazy >= MIN_MATCH and max_chain >= 4
1.150 + * For deflate_fast() (levels <= 3) good is ignored and lazy has a different
1.151 + * meaning.
1.152 + */
1.153 +
1.154 +#define EQUAL 0
1.155 +/* result of memcmp for equal strings */
1.156 +
1.157 +#ifndef NO_DUMMY_DECL
1.158 +struct static_tree_desc_s {int dummy;}; /* for buggy compilers */
1.159 +#endif
1.160 +
1.161 +/* rank Z_BLOCK between Z_NO_FLUSH and Z_PARTIAL_FLUSH */
1.162 +#define RANK(f) (((f) << 1) - ((f) > 4 ? 9 : 0))
1.163 +
1.164 +/* ===========================================================================
1.165 + * Update a hash value with the given input byte
1.166 + * IN assertion: all calls to to UPDATE_HASH are made with consecutive
1.167 + * input characters, so that a running hash key can be computed from the
1.168 + * previous key instead of complete recalculation each time.
1.169 + */
1.170 +#define UPDATE_HASH(s,h,c) (h = (((h)<<s->hash_shift) ^ (c)) & s->hash_mask)
1.171 +
1.172 +
1.173 +/* ===========================================================================
1.174 + * Insert string str in the dictionary and set match_head to the previous head
1.175 + * of the hash chain (the most recent string with same hash key). Return
1.176 + * the previous length of the hash chain.
1.177 + * If this file is compiled with -DFASTEST, the compression level is forced
1.178 + * to 1, and no hash chains are maintained.
1.179 + * IN assertion: all calls to to INSERT_STRING are made with consecutive
1.180 + * input characters and the first MIN_MATCH bytes of str are valid
1.181 + * (except for the last MIN_MATCH-1 bytes of the input file).
1.182 + */
1.183 +#ifdef FASTEST
1.184 +#define INSERT_STRING(s, str, match_head) \
1.185 + (UPDATE_HASH(s, s->ins_h, s->window[(str) + (MIN_MATCH-1)]), \
1.186 + match_head = s->head[s->ins_h], \
1.187 + s->head[s->ins_h] = (Pos)(str))
1.188 +#else
1.189 +#define INSERT_STRING(s, str, match_head) \
1.190 + (UPDATE_HASH(s, s->ins_h, s->window[(str) + (MIN_MATCH-1)]), \
1.191 + match_head = s->prev[(str) & s->w_mask] = s->head[s->ins_h], \
1.192 + s->head[s->ins_h] = (Pos)(str))
1.193 +#endif
1.194 +
1.195 +/* ===========================================================================
1.196 + * Initialize the hash table (avoiding 64K overflow for 16 bit systems).
1.197 + * prev[] will be initialized on the fly.
1.198 + */
1.199 +#define CLEAR_HASH(s) \
1.200 + s->head[s->hash_size-1] = NIL; \
1.201 + zmemzero((Bytef *)s->head, (unsigned)(s->hash_size-1)*sizeof(*s->head));
1.202 +
1.203 +/* ========================================================================= */
1.204 +int ZEXPORT deflateInit_(strm, level, version, stream_size)
1.205 + z_streamp strm;
1.206 + int level;
1.207 + const char *version;
1.208 + int stream_size;
1.209 +{
1.210 + return deflateInit2_(strm, level, Z_DEFLATED, MAX_WBITS, DEF_MEM_LEVEL,
1.211 + Z_DEFAULT_STRATEGY, version, stream_size);
1.212 + /* To do: ignore strm->next_in if we use it as window */
1.213 +}
1.214 +
1.215 +/* ========================================================================= */
1.216 +int ZEXPORT deflateInit2_(strm, level, method, windowBits, memLevel, strategy,
1.217 + version, stream_size)
1.218 + z_streamp strm;
1.219 + int level;
1.220 + int method;
1.221 + int windowBits;
1.222 + int memLevel;
1.223 + int strategy;
1.224 + const char *version;
1.225 + int stream_size;
1.226 +{
1.227 + deflate_state *s;
1.228 + int wrap = 1;
1.229 + static const char my_version[] = ZLIB_VERSION;
1.230 +
1.231 + ushf *overlay;
1.232 + /* We overlay pending_buf and d_buf+l_buf. This works since the average
1.233 + * output size for (length,distance) codes is <= 24 bits.
1.234 + */
1.235 +
1.236 + if (version == Z_NULL || version[0] != my_version[0] ||
1.237 + stream_size != sizeof(z_stream)) {
1.238 + return Z_VERSION_ERROR;
1.239 + }
1.240 + if (strm == Z_NULL) return Z_STREAM_ERROR;
1.241 +
1.242 + strm->msg = Z_NULL;
1.243 + if (strm->zalloc == (alloc_func)0) {
1.244 +#ifdef Z_SOLO
1.245 + return Z_STREAM_ERROR;
1.246 +#else
1.247 + strm->zalloc = zcalloc;
1.248 + strm->opaque = (voidpf)0;
1.249 +#endif
1.250 + }
1.251 + if (strm->zfree == (free_func)0)
1.252 +#ifdef Z_SOLO
1.253 + return Z_STREAM_ERROR;
1.254 +#else
1.255 + strm->zfree = zcfree;
1.256 +#endif
1.257 +
1.258 +#ifdef FASTEST
1.259 + if (level != 0) level = 1;
1.260 +#else
1.261 + if (level == Z_DEFAULT_COMPRESSION) level = 6;
1.262 +#endif
1.263 +
1.264 + if (windowBits < 0) { /* suppress zlib wrapper */
1.265 + wrap = 0;
1.266 + windowBits = -windowBits;
1.267 + }
1.268 +#ifdef GZIP
1.269 + else if (windowBits > 15) {
1.270 + wrap = 2; /* write gzip wrapper instead */
1.271 + windowBits -= 16;
1.272 + }
1.273 +#endif
1.274 + if (memLevel < 1 || memLevel > MAX_MEM_LEVEL || method != Z_DEFLATED ||
1.275 + windowBits < 8 || windowBits > 15 || level < 0 || level > 9 ||
1.276 + strategy < 0 || strategy > Z_FIXED) {
1.277 + return Z_STREAM_ERROR;
1.278 + }
1.279 + if (windowBits == 8) windowBits = 9; /* until 256-byte window bug fixed */
1.280 + s = (deflate_state *) ZALLOC(strm, 1, sizeof(deflate_state));
1.281 + if (s == Z_NULL) return Z_MEM_ERROR;
1.282 + strm->state = (struct internal_state FAR *)s;
1.283 + s->strm = strm;
1.284 +
1.285 + s->wrap = wrap;
1.286 + s->gzhead = Z_NULL;
1.287 + s->w_bits = windowBits;
1.288 + s->w_size = 1 << s->w_bits;
1.289 + s->w_mask = s->w_size - 1;
1.290 +
1.291 + s->hash_bits = memLevel + 7;
1.292 + s->hash_size = 1 << s->hash_bits;
1.293 + s->hash_mask = s->hash_size - 1;
1.294 + s->hash_shift = ((s->hash_bits+MIN_MATCH-1)/MIN_MATCH);
1.295 +
1.296 + s->window = (Bytef *) ZALLOC(strm, s->w_size, 2*sizeof(Byte));
1.297 + s->prev = (Posf *) ZALLOC(strm, s->w_size, sizeof(Pos));
1.298 + s->head = (Posf *) ZALLOC(strm, s->hash_size, sizeof(Pos));
1.299 +
1.300 + s->high_water = 0; /* nothing written to s->window yet */
1.301 +
1.302 + s->lit_bufsize = 1 << (memLevel + 6); /* 16K elements by default */
1.303 +
1.304 + overlay = (ushf *) ZALLOC(strm, s->lit_bufsize, sizeof(ush)+2);
1.305 + s->pending_buf = (uchf *) overlay;
1.306 + s->pending_buf_size = (ulg)s->lit_bufsize * (sizeof(ush)+2L);
1.307 +
1.308 + if (s->window == Z_NULL || s->prev == Z_NULL || s->head == Z_NULL ||
1.309 + s->pending_buf == Z_NULL) {
1.310 + s->status = FINISH_STATE;
1.311 + strm->msg = ERR_MSG(Z_MEM_ERROR);
1.312 + deflateEnd (strm);
1.313 + return Z_MEM_ERROR;
1.314 + }
1.315 + s->d_buf = overlay + s->lit_bufsize/sizeof(ush);
1.316 + s->l_buf = s->pending_buf + (1+sizeof(ush))*s->lit_bufsize;
1.317 +
1.318 + s->level = level;
1.319 + s->strategy = strategy;
1.320 + s->method = (Byte)method;
1.321 +
1.322 + return deflateReset(strm);
1.323 +}
1.324 +
1.325 +/* ========================================================================= */
1.326 +int ZEXPORT deflateSetDictionary (strm, dictionary, dictLength)
1.327 + z_streamp strm;
1.328 + const Bytef *dictionary;
1.329 + uInt dictLength;
1.330 +{
1.331 + deflate_state *s;
1.332 + uInt str, n;
1.333 + int wrap;
1.334 + unsigned avail;
1.335 + z_const unsigned char *next;
1.336 +
1.337 + if (strm == Z_NULL || strm->state == Z_NULL || dictionary == Z_NULL)
1.338 + return Z_STREAM_ERROR;
1.339 + s = strm->state;
1.340 + wrap = s->wrap;
1.341 + if (wrap == 2 || (wrap == 1 && s->status != INIT_STATE) || s->lookahead)
1.342 + return Z_STREAM_ERROR;
1.343 +
1.344 + /* when using zlib wrappers, compute Adler-32 for provided dictionary */
1.345 + if (wrap == 1)
1.346 + strm->adler = adler32(strm->adler, dictionary, dictLength);
1.347 + s->wrap = 0; /* avoid computing Adler-32 in read_buf */
1.348 +
1.349 + /* if dictionary would fill window, just replace the history */
1.350 + if (dictLength >= s->w_size) {
1.351 + if (wrap == 0) { /* already empty otherwise */
1.352 + CLEAR_HASH(s);
1.353 + s->strstart = 0;
1.354 + s->block_start = 0L;
1.355 + s->insert = 0;
1.356 + }
1.357 + dictionary += dictLength - s->w_size; /* use the tail */
1.358 + dictLength = s->w_size;
1.359 + }
1.360 +
1.361 + /* insert dictionary into window and hash */
1.362 + avail = strm->avail_in;
1.363 + next = strm->next_in;
1.364 + strm->avail_in = dictLength;
1.365 + strm->next_in = (z_const Bytef *)dictionary;
1.366 + fill_window(s);
1.367 + while (s->lookahead >= MIN_MATCH) {
1.368 + str = s->strstart;
1.369 + n = s->lookahead - (MIN_MATCH-1);
1.370 + do {
1.371 + UPDATE_HASH(s, s->ins_h, s->window[str + MIN_MATCH-1]);
1.372 +#ifndef FASTEST
1.373 + s->prev[str & s->w_mask] = s->head[s->ins_h];
1.374 +#endif
1.375 + s->head[s->ins_h] = (Pos)str;
1.376 + str++;
1.377 + } while (--n);
1.378 + s->strstart = str;
1.379 + s->lookahead = MIN_MATCH-1;
1.380 + fill_window(s);
1.381 + }
1.382 + s->strstart += s->lookahead;
1.383 + s->block_start = (long)s->strstart;
1.384 + s->insert = s->lookahead;
1.385 + s->lookahead = 0;
1.386 + s->match_length = s->prev_length = MIN_MATCH-1;
1.387 + s->match_available = 0;
1.388 + strm->next_in = next;
1.389 + strm->avail_in = avail;
1.390 + s->wrap = wrap;
1.391 + return Z_OK;
1.392 +}
1.393 +
1.394 +/* ========================================================================= */
1.395 +int ZEXPORT deflateResetKeep (strm)
1.396 + z_streamp strm;
1.397 +{
1.398 + deflate_state *s;
1.399 +
1.400 + if (strm == Z_NULL || strm->state == Z_NULL ||
1.401 + strm->zalloc == (alloc_func)0 || strm->zfree == (free_func)0) {
1.402 + return Z_STREAM_ERROR;
1.403 + }
1.404 +
1.405 + strm->total_in = strm->total_out = 0;
1.406 + strm->msg = Z_NULL; /* use zfree if we ever allocate msg dynamically */
1.407 + strm->data_type = Z_UNKNOWN;
1.408 +
1.409 + s = (deflate_state *)strm->state;
1.410 + s->pending = 0;
1.411 + s->pending_out = s->pending_buf;
1.412 +
1.413 + if (s->wrap < 0) {
1.414 + s->wrap = -s->wrap; /* was made negative by deflate(..., Z_FINISH); */
1.415 + }
1.416 + s->status = s->wrap ? INIT_STATE : BUSY_STATE;
1.417 + strm->adler =
1.418 +#ifdef GZIP
1.419 + s->wrap == 2 ? crc32(0L, Z_NULL, 0) :
1.420 +#endif
1.421 + adler32(0L, Z_NULL, 0);
1.422 + s->last_flush = Z_NO_FLUSH;
1.423 +
1.424 + _tr_init(s);
1.425 +
1.426 + return Z_OK;
1.427 +}
1.428 +
1.429 +/* ========================================================================= */
1.430 +int ZEXPORT deflateReset (strm)
1.431 + z_streamp strm;
1.432 +{
1.433 + int ret;
1.434 +
1.435 + ret = deflateResetKeep(strm);
1.436 + if (ret == Z_OK)
1.437 + lm_init(strm->state);
1.438 + return ret;
1.439 +}
1.440 +
1.441 +/* ========================================================================= */
1.442 +int ZEXPORT deflateSetHeader (strm, head)
1.443 + z_streamp strm;
1.444 + gz_headerp head;
1.445 +{
1.446 + if (strm == Z_NULL || strm->state == Z_NULL) return Z_STREAM_ERROR;
1.447 + if (strm->state->wrap != 2) return Z_STREAM_ERROR;
1.448 + strm->state->gzhead = head;
1.449 + return Z_OK;
1.450 +}
1.451 +
1.452 +/* ========================================================================= */
1.453 +int ZEXPORT deflatePending (strm, pending, bits)
1.454 + unsigned *pending;
1.455 + int *bits;
1.456 + z_streamp strm;
1.457 +{
1.458 + if (strm == Z_NULL || strm->state == Z_NULL) return Z_STREAM_ERROR;
1.459 + if (pending != Z_NULL)
1.460 + *pending = strm->state->pending;
1.461 + if (bits != Z_NULL)
1.462 + *bits = strm->state->bi_valid;
1.463 + return Z_OK;
1.464 +}
1.465 +
1.466 +/* ========================================================================= */
1.467 +int ZEXPORT deflatePrime (strm, bits, value)
1.468 + z_streamp strm;
1.469 + int bits;
1.470 + int value;
1.471 +{
1.472 + deflate_state *s;
1.473 + int put;
1.474 +
1.475 + if (strm == Z_NULL || strm->state == Z_NULL) return Z_STREAM_ERROR;
1.476 + s = strm->state;
1.477 + if ((Bytef *)(s->d_buf) < s->pending_out + ((Buf_size + 7) >> 3))
1.478 + return Z_BUF_ERROR;
1.479 + do {
1.480 + put = Buf_size - s->bi_valid;
1.481 + if (put > bits)
1.482 + put = bits;
1.483 + s->bi_buf |= (ush)((value & ((1 << put) - 1)) << s->bi_valid);
1.484 + s->bi_valid += put;
1.485 + _tr_flush_bits(s);
1.486 + value >>= put;
1.487 + bits -= put;
1.488 + } while (bits);
1.489 + return Z_OK;
1.490 +}
1.491 +
1.492 +/* ========================================================================= */
1.493 +int ZEXPORT deflateParams(strm, level, strategy)
1.494 + z_streamp strm;
1.495 + int level;
1.496 + int strategy;
1.497 +{
1.498 + deflate_state *s;
1.499 + compress_func func;
1.500 + int err = Z_OK;
1.501 +
1.502 + if (strm == Z_NULL || strm->state == Z_NULL) return Z_STREAM_ERROR;
1.503 + s = strm->state;
1.504 +
1.505 +#ifdef FASTEST
1.506 + if (level != 0) level = 1;
1.507 +#else
1.508 + if (level == Z_DEFAULT_COMPRESSION) level = 6;
1.509 +#endif
1.510 + if (level < 0 || level > 9 || strategy < 0 || strategy > Z_FIXED) {
1.511 + return Z_STREAM_ERROR;
1.512 + }
1.513 + func = configuration_table[s->level].func;
1.514 +
1.515 + if ((strategy != s->strategy || func != configuration_table[level].func) &&
1.516 + strm->total_in != 0) {
1.517 + /* Flush the last buffer: */
1.518 + err = deflate(strm, Z_BLOCK);
1.519 + if (err == Z_BUF_ERROR && s->pending == 0)
1.520 + err = Z_OK;
1.521 + }
1.522 + if (s->level != level) {
1.523 + s->level = level;
1.524 + s->max_lazy_match = configuration_table[level].max_lazy;
1.525 + s->good_match = configuration_table[level].good_length;
1.526 + s->nice_match = configuration_table[level].nice_length;
1.527 + s->max_chain_length = configuration_table[level].max_chain;
1.528 + }
1.529 + s->strategy = strategy;
1.530 + return err;
1.531 +}
1.532 +
1.533 +/* ========================================================================= */
1.534 +int ZEXPORT deflateTune(strm, good_length, max_lazy, nice_length, max_chain)
1.535 + z_streamp strm;
1.536 + int good_length;
1.537 + int max_lazy;
1.538 + int nice_length;
1.539 + int max_chain;
1.540 +{
1.541 + deflate_state *s;
1.542 +
1.543 + if (strm == Z_NULL || strm->state == Z_NULL) return Z_STREAM_ERROR;
1.544 + s = strm->state;
1.545 + s->good_match = good_length;
1.546 + s->max_lazy_match = max_lazy;
1.547 + s->nice_match = nice_length;
1.548 + s->max_chain_length = max_chain;
1.549 + return Z_OK;
1.550 +}
1.551 +
1.552 +/* =========================================================================
1.553 + * For the default windowBits of 15 and memLevel of 8, this function returns
1.554 + * a close to exact, as well as small, upper bound on the compressed size.
1.555 + * They are coded as constants here for a reason--if the #define's are
1.556 + * changed, then this function needs to be changed as well. The return
1.557 + * value for 15 and 8 only works for those exact settings.
1.558 + *
1.559 + * For any setting other than those defaults for windowBits and memLevel,
1.560 + * the value returned is a conservative worst case for the maximum expansion
1.561 + * resulting from using fixed blocks instead of stored blocks, which deflate
1.562 + * can emit on compressed data for some combinations of the parameters.
1.563 + *
1.564 + * This function could be more sophisticated to provide closer upper bounds for
1.565 + * every combination of windowBits and memLevel. But even the conservative
1.566 + * upper bound of about 14% expansion does not seem onerous for output buffer
1.567 + * allocation.
1.568 + */
1.569 +uLong ZEXPORT deflateBound(strm, sourceLen)
1.570 + z_streamp strm;
1.571 + uLong sourceLen;
1.572 +{
1.573 + deflate_state *s;
1.574 + uLong complen, wraplen;
1.575 + Bytef *str;
1.576 +
1.577 + /* conservative upper bound for compressed data */
1.578 + complen = sourceLen +
1.579 + ((sourceLen + 7) >> 3) + ((sourceLen + 63) >> 6) + 5;
1.580 +
1.581 + /* if can't get parameters, return conservative bound plus zlib wrapper */
1.582 + if (strm == Z_NULL || strm->state == Z_NULL)
1.583 + return complen + 6;
1.584 +
1.585 + /* compute wrapper length */
1.586 + s = strm->state;
1.587 + switch (s->wrap) {
1.588 + case 0: /* raw deflate */
1.589 + wraplen = 0;
1.590 + break;
1.591 + case 1: /* zlib wrapper */
1.592 + wraplen = 6 + (s->strstart ? 4 : 0);
1.593 + break;
1.594 + case 2: /* gzip wrapper */
1.595 + wraplen = 18;
1.596 + if (s->gzhead != Z_NULL) { /* user-supplied gzip header */
1.597 + if (s->gzhead->extra != Z_NULL)
1.598 + wraplen += 2 + s->gzhead->extra_len;
1.599 + str = s->gzhead->name;
1.600 + if (str != Z_NULL)
1.601 + do {
1.602 + wraplen++;
1.603 + } while (*str++);
1.604 + str = s->gzhead->comment;
1.605 + if (str != Z_NULL)
1.606 + do {
1.607 + wraplen++;
1.608 + } while (*str++);
1.609 + if (s->gzhead->hcrc)
1.610 + wraplen += 2;
1.611 + }
1.612 + break;
1.613 + default: /* for compiler happiness */
1.614 + wraplen = 6;
1.615 + }
1.616 +
1.617 + /* if not default parameters, return conservative bound */
1.618 + if (s->w_bits != 15 || s->hash_bits != 8 + 7)
1.619 + return complen + wraplen;
1.620 +
1.621 + /* default settings: return tight bound for that case */
1.622 + return sourceLen + (sourceLen >> 12) + (sourceLen >> 14) +
1.623 + (sourceLen >> 25) + 13 - 6 + wraplen;
1.624 +}
1.625 +
1.626 +/* =========================================================================
1.627 + * Put a short in the pending buffer. The 16-bit value is put in MSB order.
1.628 + * IN assertion: the stream state is correct and there is enough room in
1.629 + * pending_buf.
1.630 + */
1.631 +local void putShortMSB (s, b)
1.632 + deflate_state *s;
1.633 + uInt b;
1.634 +{
1.635 + put_byte(s, (Byte)(b >> 8));
1.636 + put_byte(s, (Byte)(b & 0xff));
1.637 +}
1.638 +
1.639 +/* =========================================================================
1.640 + * Flush as much pending output as possible. All deflate() output goes
1.641 + * through this function so some applications may wish to modify it
1.642 + * to avoid allocating a large strm->next_out buffer and copying into it.
1.643 + * (See also read_buf()).
1.644 + */
1.645 +local void flush_pending(strm)
1.646 + z_streamp strm;
1.647 +{
1.648 + unsigned len;
1.649 + deflate_state *s = strm->state;
1.650 +
1.651 + _tr_flush_bits(s);
1.652 + len = s->pending;
1.653 + if (len > strm->avail_out) len = strm->avail_out;
1.654 + if (len == 0) return;
1.655 +
1.656 + zmemcpy(strm->next_out, s->pending_out, len);
1.657 + strm->next_out += len;
1.658 + s->pending_out += len;
1.659 + strm->total_out += len;
1.660 + strm->avail_out -= len;
1.661 + s->pending -= len;
1.662 + if (s->pending == 0) {
1.663 + s->pending_out = s->pending_buf;
1.664 + }
1.665 +}
1.666 +
1.667 +/* ========================================================================= */
1.668 +int ZEXPORT deflate (strm, flush)
1.669 + z_streamp strm;
1.670 + int flush;
1.671 +{
1.672 + int old_flush; /* value of flush param for previous deflate call */
1.673 + deflate_state *s;
1.674 +
1.675 + if (strm == Z_NULL || strm->state == Z_NULL ||
1.676 + flush > Z_BLOCK || flush < 0) {
1.677 + return Z_STREAM_ERROR;
1.678 + }
1.679 + s = strm->state;
1.680 +
1.681 + if (strm->next_out == Z_NULL ||
1.682 + (strm->next_in == Z_NULL && strm->avail_in != 0) ||
1.683 + (s->status == FINISH_STATE && flush != Z_FINISH)) {
1.684 + ERR_RETURN(strm, Z_STREAM_ERROR);
1.685 + }
1.686 + if (strm->avail_out == 0) ERR_RETURN(strm, Z_BUF_ERROR);
1.687 +
1.688 + s->strm = strm; /* just in case */
1.689 + old_flush = s->last_flush;
1.690 + s->last_flush = flush;
1.691 +
1.692 + /* Write the header */
1.693 + if (s->status == INIT_STATE) {
1.694 +#ifdef GZIP
1.695 + if (s->wrap == 2) {
1.696 + strm->adler = crc32(0L, Z_NULL, 0);
1.697 + put_byte(s, 31);
1.698 + put_byte(s, 139);
1.699 + put_byte(s, 8);
1.700 + if (s->gzhead == Z_NULL) {
1.701 + put_byte(s, 0);
1.702 + put_byte(s, 0);
1.703 + put_byte(s, 0);
1.704 + put_byte(s, 0);
1.705 + put_byte(s, 0);
1.706 + put_byte(s, s->level == 9 ? 2 :
1.707 + (s->strategy >= Z_HUFFMAN_ONLY || s->level < 2 ?
1.708 + 4 : 0));
1.709 + put_byte(s, OS_CODE);
1.710 + s->status = BUSY_STATE;
1.711 + }
1.712 + else {
1.713 + put_byte(s, (s->gzhead->text ? 1 : 0) +
1.714 + (s->gzhead->hcrc ? 2 : 0) +
1.715 + (s->gzhead->extra == Z_NULL ? 0 : 4) +
1.716 + (s->gzhead->name == Z_NULL ? 0 : 8) +
1.717 + (s->gzhead->comment == Z_NULL ? 0 : 16)
1.718 + );
1.719 + put_byte(s, (Byte)(s->gzhead->time & 0xff));
1.720 + put_byte(s, (Byte)((s->gzhead->time >> 8) & 0xff));
1.721 + put_byte(s, (Byte)((s->gzhead->time >> 16) & 0xff));
1.722 + put_byte(s, (Byte)((s->gzhead->time >> 24) & 0xff));
1.723 + put_byte(s, s->level == 9 ? 2 :
1.724 + (s->strategy >= Z_HUFFMAN_ONLY || s->level < 2 ?
1.725 + 4 : 0));
1.726 + put_byte(s, s->gzhead->os & 0xff);
1.727 + if (s->gzhead->extra != Z_NULL) {
1.728 + put_byte(s, s->gzhead->extra_len & 0xff);
1.729 + put_byte(s, (s->gzhead->extra_len >> 8) & 0xff);
1.730 + }
1.731 + if (s->gzhead->hcrc)
1.732 + strm->adler = crc32(strm->adler, s->pending_buf,
1.733 + s->pending);
1.734 + s->gzindex = 0;
1.735 + s->status = EXTRA_STATE;
1.736 + }
1.737 + }
1.738 + else
1.739 +#endif
1.740 + {
1.741 + uInt header = (Z_DEFLATED + ((s->w_bits-8)<<4)) << 8;
1.742 + uInt level_flags;
1.743 +
1.744 + if (s->strategy >= Z_HUFFMAN_ONLY || s->level < 2)
1.745 + level_flags = 0;
1.746 + else if (s->level < 6)
1.747 + level_flags = 1;
1.748 + else if (s->level == 6)
1.749 + level_flags = 2;
1.750 + else
1.751 + level_flags = 3;
1.752 + header |= (level_flags << 6);
1.753 + if (s->strstart != 0) header |= PRESET_DICT;
1.754 + header += 31 - (header % 31);
1.755 +
1.756 + s->status = BUSY_STATE;
1.757 + putShortMSB(s, header);
1.758 +
1.759 + /* Save the adler32 of the preset dictionary: */
1.760 + if (s->strstart != 0) {
1.761 + putShortMSB(s, (uInt)(strm->adler >> 16));
1.762 + putShortMSB(s, (uInt)(strm->adler & 0xffff));
1.763 + }
1.764 + strm->adler = adler32(0L, Z_NULL, 0);
1.765 + }
1.766 + }
1.767 +#ifdef GZIP
1.768 + if (s->status == EXTRA_STATE) {
1.769 + if (s->gzhead->extra != Z_NULL) {
1.770 + uInt beg = s->pending; /* start of bytes to update crc */
1.771 +
1.772 + while (s->gzindex < (s->gzhead->extra_len & 0xffff)) {
1.773 + if (s->pending == s->pending_buf_size) {
1.774 + if (s->gzhead->hcrc && s->pending > beg)
1.775 + strm->adler = crc32(strm->adler, s->pending_buf + beg,
1.776 + s->pending - beg);
1.777 + flush_pending(strm);
1.778 + beg = s->pending;
1.779 + if (s->pending == s->pending_buf_size)
1.780 + break;
1.781 + }
1.782 + put_byte(s, s->gzhead->extra[s->gzindex]);
1.783 + s->gzindex++;
1.784 + }
1.785 + if (s->gzhead->hcrc && s->pending > beg)
1.786 + strm->adler = crc32(strm->adler, s->pending_buf + beg,
1.787 + s->pending - beg);
1.788 + if (s->gzindex == s->gzhead->extra_len) {
1.789 + s->gzindex = 0;
1.790 + s->status = NAME_STATE;
1.791 + }
1.792 + }
1.793 + else
1.794 + s->status = NAME_STATE;
1.795 + }
1.796 + if (s->status == NAME_STATE) {
1.797 + if (s->gzhead->name != Z_NULL) {
1.798 + uInt beg = s->pending; /* start of bytes to update crc */
1.799 + int val;
1.800 +
1.801 + do {
1.802 + if (s->pending == s->pending_buf_size) {
1.803 + if (s->gzhead->hcrc && s->pending > beg)
1.804 + strm->adler = crc32(strm->adler, s->pending_buf + beg,
1.805 + s->pending - beg);
1.806 + flush_pending(strm);
1.807 + beg = s->pending;
1.808 + if (s->pending == s->pending_buf_size) {
1.809 + val = 1;
1.810 + break;
1.811 + }
1.812 + }
1.813 + val = s->gzhead->name[s->gzindex++];
1.814 + put_byte(s, val);
1.815 + } while (val != 0);
1.816 + if (s->gzhead->hcrc && s->pending > beg)
1.817 + strm->adler = crc32(strm->adler, s->pending_buf + beg,
1.818 + s->pending - beg);
1.819 + if (val == 0) {
1.820 + s->gzindex = 0;
1.821 + s->status = COMMENT_STATE;
1.822 + }
1.823 + }
1.824 + else
1.825 + s->status = COMMENT_STATE;
1.826 + }
1.827 + if (s->status == COMMENT_STATE) {
1.828 + if (s->gzhead->comment != Z_NULL) {
1.829 + uInt beg = s->pending; /* start of bytes to update crc */
1.830 + int val;
1.831 +
1.832 + do {
1.833 + if (s->pending == s->pending_buf_size) {
1.834 + if (s->gzhead->hcrc && s->pending > beg)
1.835 + strm->adler = crc32(strm->adler, s->pending_buf + beg,
1.836 + s->pending - beg);
1.837 + flush_pending(strm);
1.838 + beg = s->pending;
1.839 + if (s->pending == s->pending_buf_size) {
1.840 + val = 1;
1.841 + break;
1.842 + }
1.843 + }
1.844 + val = s->gzhead->comment[s->gzindex++];
1.845 + put_byte(s, val);
1.846 + } while (val != 0);
1.847 + if (s->gzhead->hcrc && s->pending > beg)
1.848 + strm->adler = crc32(strm->adler, s->pending_buf + beg,
1.849 + s->pending - beg);
1.850 + if (val == 0)
1.851 + s->status = HCRC_STATE;
1.852 + }
1.853 + else
1.854 + s->status = HCRC_STATE;
1.855 + }
1.856 + if (s->status == HCRC_STATE) {
1.857 + if (s->gzhead->hcrc) {
1.858 + if (s->pending + 2 > s->pending_buf_size)
1.859 + flush_pending(strm);
1.860 + if (s->pending + 2 <= s->pending_buf_size) {
1.861 + put_byte(s, (Byte)(strm->adler & 0xff));
1.862 + put_byte(s, (Byte)((strm->adler >> 8) & 0xff));
1.863 + strm->adler = crc32(0L, Z_NULL, 0);
1.864 + s->status = BUSY_STATE;
1.865 + }
1.866 + }
1.867 + else
1.868 + s->status = BUSY_STATE;
1.869 + }
1.870 +#endif
1.871 +
1.872 + /* Flush as much pending output as possible */
1.873 + if (s->pending != 0) {
1.874 + flush_pending(strm);
1.875 + if (strm->avail_out == 0) {
1.876 + /* Since avail_out is 0, deflate will be called again with
1.877 + * more output space, but possibly with both pending and
1.878 + * avail_in equal to zero. There won't be anything to do,
1.879 + * but this is not an error situation so make sure we
1.880 + * return OK instead of BUF_ERROR at next call of deflate:
1.881 + */
1.882 + s->last_flush = -1;
1.883 + return Z_OK;
1.884 + }
1.885 +
1.886 + /* Make sure there is something to do and avoid duplicate consecutive
1.887 + * flushes. For repeated and useless calls with Z_FINISH, we keep
1.888 + * returning Z_STREAM_END instead of Z_BUF_ERROR.
1.889 + */
1.890 + } else if (strm->avail_in == 0 && RANK(flush) <= RANK(old_flush) &&
1.891 + flush != Z_FINISH) {
1.892 + ERR_RETURN(strm, Z_BUF_ERROR);
1.893 + }
1.894 +
1.895 + /* User must not provide more input after the first FINISH: */
1.896 + if (s->status == FINISH_STATE && strm->avail_in != 0) {
1.897 + ERR_RETURN(strm, Z_BUF_ERROR);
1.898 + }
1.899 +
1.900 + /* Start a new block or continue the current one.
1.901 + */
1.902 + if (strm->avail_in != 0 || s->lookahead != 0 ||
1.903 + (flush != Z_NO_FLUSH && s->status != FINISH_STATE)) {
1.904 + block_state bstate;
1.905 +
1.906 + bstate = s->strategy == Z_HUFFMAN_ONLY ? deflate_huff(s, flush) :
1.907 + (s->strategy == Z_RLE ? deflate_rle(s, flush) :
1.908 + (*(configuration_table[s->level].func))(s, flush));
1.909 +
1.910 + if (bstate == finish_started || bstate == finish_done) {
1.911 + s->status = FINISH_STATE;
1.912 + }
1.913 + if (bstate == need_more || bstate == finish_started) {
1.914 + if (strm->avail_out == 0) {
1.915 + s->last_flush = -1; /* avoid BUF_ERROR next call, see above */
1.916 + }
1.917 + return Z_OK;
1.918 + /* If flush != Z_NO_FLUSH && avail_out == 0, the next call
1.919 + * of deflate should use the same flush parameter to make sure
1.920 + * that the flush is complete. So we don't have to output an
1.921 + * empty block here, this will be done at next call. This also
1.922 + * ensures that for a very small output buffer, we emit at most
1.923 + * one empty block.
1.924 + */
1.925 + }
1.926 + if (bstate == block_done) {
1.927 + if (flush == Z_PARTIAL_FLUSH) {
1.928 + _tr_align(s);
1.929 + } else if (flush != Z_BLOCK) { /* FULL_FLUSH or SYNC_FLUSH */
1.930 + _tr_stored_block(s, (char*)0, 0L, 0);
1.931 + /* For a full flush, this empty block will be recognized
1.932 + * as a special marker by inflate_sync().
1.933 + */
1.934 + if (flush == Z_FULL_FLUSH) {
1.935 + CLEAR_HASH(s); /* forget history */
1.936 + if (s->lookahead == 0) {
1.937 + s->strstart = 0;
1.938 + s->block_start = 0L;
1.939 + s->insert = 0;
1.940 + }
1.941 + }
1.942 + }
1.943 + flush_pending(strm);
1.944 + if (strm->avail_out == 0) {
1.945 + s->last_flush = -1; /* avoid BUF_ERROR at next call, see above */
1.946 + return Z_OK;
1.947 + }
1.948 + }
1.949 + }
1.950 + Assert(strm->avail_out > 0, "bug2");
1.951 +
1.952 + if (flush != Z_FINISH) return Z_OK;
1.953 + if (s->wrap <= 0) return Z_STREAM_END;
1.954 +
1.955 + /* Write the trailer */
1.956 +#ifdef GZIP
1.957 + if (s->wrap == 2) {
1.958 + put_byte(s, (Byte)(strm->adler & 0xff));
1.959 + put_byte(s, (Byte)((strm->adler >> 8) & 0xff));
1.960 + put_byte(s, (Byte)((strm->adler >> 16) & 0xff));
1.961 + put_byte(s, (Byte)((strm->adler >> 24) & 0xff));
1.962 + put_byte(s, (Byte)(strm->total_in & 0xff));
1.963 + put_byte(s, (Byte)((strm->total_in >> 8) & 0xff));
1.964 + put_byte(s, (Byte)((strm->total_in >> 16) & 0xff));
1.965 + put_byte(s, (Byte)((strm->total_in >> 24) & 0xff));
1.966 + }
1.967 + else
1.968 +#endif
1.969 + {
1.970 + putShortMSB(s, (uInt)(strm->adler >> 16));
1.971 + putShortMSB(s, (uInt)(strm->adler & 0xffff));
1.972 + }
1.973 + flush_pending(strm);
1.974 + /* If avail_out is zero, the application will call deflate again
1.975 + * to flush the rest.
1.976 + */
1.977 + if (s->wrap > 0) s->wrap = -s->wrap; /* write the trailer only once! */
1.978 + return s->pending != 0 ? Z_OK : Z_STREAM_END;
1.979 +}
1.980 +
1.981 +/* ========================================================================= */
1.982 +int ZEXPORT deflateEnd (strm)
1.983 + z_streamp strm;
1.984 +{
1.985 + int status;
1.986 +
1.987 + if (strm == Z_NULL || strm->state == Z_NULL) return Z_STREAM_ERROR;
1.988 +
1.989 + status = strm->state->status;
1.990 + if (status != INIT_STATE &&
1.991 + status != EXTRA_STATE &&
1.992 + status != NAME_STATE &&
1.993 + status != COMMENT_STATE &&
1.994 + status != HCRC_STATE &&
1.995 + status != BUSY_STATE &&
1.996 + status != FINISH_STATE) {
1.997 + return Z_STREAM_ERROR;
1.998 + }
1.999 +
1.1000 + /* Deallocate in reverse order of allocations: */
1.1001 + TRY_FREE(strm, strm->state->pending_buf);
1.1002 + TRY_FREE(strm, strm->state->head);
1.1003 + TRY_FREE(strm, strm->state->prev);
1.1004 + TRY_FREE(strm, strm->state->window);
1.1005 +
1.1006 + ZFREE(strm, strm->state);
1.1007 + strm->state = Z_NULL;
1.1008 +
1.1009 + return status == BUSY_STATE ? Z_DATA_ERROR : Z_OK;
1.1010 +}
1.1011 +
1.1012 +/* =========================================================================
1.1013 + * Copy the source state to the destination state.
1.1014 + * To simplify the source, this is not supported for 16-bit MSDOS (which
1.1015 + * doesn't have enough memory anyway to duplicate compression states).
1.1016 + */
1.1017 +int ZEXPORT deflateCopy (dest, source)
1.1018 + z_streamp dest;
1.1019 + z_streamp source;
1.1020 +{
1.1021 +#ifdef MAXSEG_64K
1.1022 + return Z_STREAM_ERROR;
1.1023 +#else
1.1024 + deflate_state *ds;
1.1025 + deflate_state *ss;
1.1026 + ushf *overlay;
1.1027 +
1.1028 +
1.1029 + if (source == Z_NULL || dest == Z_NULL || source->state == Z_NULL) {
1.1030 + return Z_STREAM_ERROR;
1.1031 + }
1.1032 +
1.1033 + ss = source->state;
1.1034 +
1.1035 + zmemcpy((voidpf)dest, (voidpf)source, sizeof(z_stream));
1.1036 +
1.1037 + ds = (deflate_state *) ZALLOC(dest, 1, sizeof(deflate_state));
1.1038 + if (ds == Z_NULL) return Z_MEM_ERROR;
1.1039 + dest->state = (struct internal_state FAR *) ds;
1.1040 + zmemcpy((voidpf)ds, (voidpf)ss, sizeof(deflate_state));
1.1041 + ds->strm = dest;
1.1042 +
1.1043 + ds->window = (Bytef *) ZALLOC(dest, ds->w_size, 2*sizeof(Byte));
1.1044 + ds->prev = (Posf *) ZALLOC(dest, ds->w_size, sizeof(Pos));
1.1045 + ds->head = (Posf *) ZALLOC(dest, ds->hash_size, sizeof(Pos));
1.1046 + overlay = (ushf *) ZALLOC(dest, ds->lit_bufsize, sizeof(ush)+2);
1.1047 + ds->pending_buf = (uchf *) overlay;
1.1048 +
1.1049 + if (ds->window == Z_NULL || ds->prev == Z_NULL || ds->head == Z_NULL ||
1.1050 + ds->pending_buf == Z_NULL) {
1.1051 + deflateEnd (dest);
1.1052 + return Z_MEM_ERROR;
1.1053 + }
1.1054 + /* following zmemcpy do not work for 16-bit MSDOS */
1.1055 + zmemcpy(ds->window, ss->window, ds->w_size * 2 * sizeof(Byte));
1.1056 + zmemcpy((voidpf)ds->prev, (voidpf)ss->prev, ds->w_size * sizeof(Pos));
1.1057 + zmemcpy((voidpf)ds->head, (voidpf)ss->head, ds->hash_size * sizeof(Pos));
1.1058 + zmemcpy(ds->pending_buf, ss->pending_buf, (uInt)ds->pending_buf_size);
1.1059 +
1.1060 + ds->pending_out = ds->pending_buf + (ss->pending_out - ss->pending_buf);
1.1061 + ds->d_buf = overlay + ds->lit_bufsize/sizeof(ush);
1.1062 + ds->l_buf = ds->pending_buf + (1+sizeof(ush))*ds->lit_bufsize;
1.1063 +
1.1064 + ds->l_desc.dyn_tree = ds->dyn_ltree;
1.1065 + ds->d_desc.dyn_tree = ds->dyn_dtree;
1.1066 + ds->bl_desc.dyn_tree = ds->bl_tree;
1.1067 +
1.1068 + return Z_OK;
1.1069 +#endif /* MAXSEG_64K */
1.1070 +}
1.1071 +
1.1072 +/* ===========================================================================
1.1073 + * Read a new buffer from the current input stream, update the adler32
1.1074 + * and total number of bytes read. All deflate() input goes through
1.1075 + * this function so some applications may wish to modify it to avoid
1.1076 + * allocating a large strm->next_in buffer and copying from it.
1.1077 + * (See also flush_pending()).
1.1078 + */
1.1079 +local int read_buf(strm, buf, size)
1.1080 + z_streamp strm;
1.1081 + Bytef *buf;
1.1082 + unsigned size;
1.1083 +{
1.1084 + unsigned len = strm->avail_in;
1.1085 +
1.1086 + if (len > size) len = size;
1.1087 + if (len == 0) return 0;
1.1088 +
1.1089 + strm->avail_in -= len;
1.1090 +
1.1091 + zmemcpy(buf, strm->next_in, len);
1.1092 + if (strm->state->wrap == 1) {
1.1093 + strm->adler = adler32(strm->adler, buf, len);
1.1094 + }
1.1095 +#ifdef GZIP
1.1096 + else if (strm->state->wrap == 2) {
1.1097 + strm->adler = crc32(strm->adler, buf, len);
1.1098 + }
1.1099 +#endif
1.1100 + strm->next_in += len;
1.1101 + strm->total_in += len;
1.1102 +
1.1103 + return (int)len;
1.1104 +}
1.1105 +
1.1106 +/* ===========================================================================
1.1107 + * Initialize the "longest match" routines for a new zlib stream
1.1108 + */
1.1109 +local void lm_init (s)
1.1110 + deflate_state *s;
1.1111 +{
1.1112 + s->window_size = (ulg)2L*s->w_size;
1.1113 +
1.1114 + CLEAR_HASH(s);
1.1115 +
1.1116 + /* Set the default configuration parameters:
1.1117 + */
1.1118 + s->max_lazy_match = configuration_table[s->level].max_lazy;
1.1119 + s->good_match = configuration_table[s->level].good_length;
1.1120 + s->nice_match = configuration_table[s->level].nice_length;
1.1121 + s->max_chain_length = configuration_table[s->level].max_chain;
1.1122 +
1.1123 + s->strstart = 0;
1.1124 + s->block_start = 0L;
1.1125 + s->lookahead = 0;
1.1126 + s->insert = 0;
1.1127 + s->match_length = s->prev_length = MIN_MATCH-1;
1.1128 + s->match_available = 0;
1.1129 + s->ins_h = 0;
1.1130 +#ifndef FASTEST
1.1131 +#ifdef ASMV
1.1132 + match_init(); /* initialize the asm code */
1.1133 +#endif
1.1134 +#endif
1.1135 +}
1.1136 +
1.1137 +#ifndef FASTEST
1.1138 +/* ===========================================================================
1.1139 + * Set match_start to the longest match starting at the given string and
1.1140 + * return its length. Matches shorter or equal to prev_length are discarded,
1.1141 + * in which case the result is equal to prev_length and match_start is
1.1142 + * garbage.
1.1143 + * IN assertions: cur_match is the head of the hash chain for the current
1.1144 + * string (strstart) and its distance is <= MAX_DIST, and prev_length >= 1
1.1145 + * OUT assertion: the match length is not greater than s->lookahead.
1.1146 + */
1.1147 +#ifndef ASMV
1.1148 +/* For 80x86 and 680x0, an optimized version will be provided in match.asm or
1.1149 + * match.S. The code will be functionally equivalent.
1.1150 + */
1.1151 +local uInt longest_match(s, cur_match)
1.1152 + deflate_state *s;
1.1153 + IPos cur_match; /* current match */
1.1154 +{
1.1155 + unsigned chain_length = s->max_chain_length;/* max hash chain length */
1.1156 + register Bytef *scan = s->window + s->strstart; /* current string */
1.1157 + register Bytef *match; /* matched string */
1.1158 + register int len; /* length of current match */
1.1159 + int best_len = s->prev_length; /* best match length so far */
1.1160 + int nice_match = s->nice_match; /* stop if match long enough */
1.1161 + IPos limit = s->strstart > (IPos)MAX_DIST(s) ?
1.1162 + s->strstart - (IPos)MAX_DIST(s) : NIL;
1.1163 + /* Stop when cur_match becomes <= limit. To simplify the code,
1.1164 + * we prevent matches with the string of window index 0.
1.1165 + */
1.1166 + Posf *prev = s->prev;
1.1167 + uInt wmask = s->w_mask;
1.1168 +
1.1169 +#ifdef UNALIGNED_OK
1.1170 + /* Compare two bytes at a time. Note: this is not always beneficial.
1.1171 + * Try with and without -DUNALIGNED_OK to check.
1.1172 + */
1.1173 + register Bytef *strend = s->window + s->strstart + MAX_MATCH - 1;
1.1174 + register ush scan_start = *(ushf*)scan;
1.1175 + register ush scan_end = *(ushf*)(scan+best_len-1);
1.1176 +#else
1.1177 + register Bytef *strend = s->window + s->strstart + MAX_MATCH;
1.1178 + register Byte scan_end1 = scan[best_len-1];
1.1179 + register Byte scan_end = scan[best_len];
1.1180 +#endif
1.1181 +
1.1182 + /* The code is optimized for HASH_BITS >= 8 and MAX_MATCH-2 multiple of 16.
1.1183 + * It is easy to get rid of this optimization if necessary.
1.1184 + */
1.1185 + Assert(s->hash_bits >= 8 && MAX_MATCH == 258, "Code too clever");
1.1186 +
1.1187 + /* Do not waste too much time if we already have a good match: */
1.1188 + if (s->prev_length >= s->good_match) {
1.1189 + chain_length >>= 2;
1.1190 + }
1.1191 + /* Do not look for matches beyond the end of the input. This is necessary
1.1192 + * to make deflate deterministic.
1.1193 + */
1.1194 + if ((uInt)nice_match > s->lookahead) nice_match = s->lookahead;
1.1195 +
1.1196 + Assert((ulg)s->strstart <= s->window_size-MIN_LOOKAHEAD, "need lookahead");
1.1197 +
1.1198 + do {
1.1199 + Assert(cur_match < s->strstart, "no future");
1.1200 + match = s->window + cur_match;
1.1201 +
1.1202 + /* Skip to next match if the match length cannot increase
1.1203 + * or if the match length is less than 2. Note that the checks below
1.1204 + * for insufficient lookahead only occur occasionally for performance
1.1205 + * reasons. Therefore uninitialized memory will be accessed, and
1.1206 + * conditional jumps will be made that depend on those values.
1.1207 + * However the length of the match is limited to the lookahead, so
1.1208 + * the output of deflate is not affected by the uninitialized values.
1.1209 + */
1.1210 +#if (defined(UNALIGNED_OK) && MAX_MATCH == 258)
1.1211 + /* This code assumes sizeof(unsigned short) == 2. Do not use
1.1212 + * UNALIGNED_OK if your compiler uses a different size.
1.1213 + */
1.1214 + if (*(ushf*)(match+best_len-1) != scan_end ||
1.1215 + *(ushf*)match != scan_start) continue;
1.1216 +
1.1217 + /* It is not necessary to compare scan[2] and match[2] since they are
1.1218 + * always equal when the other bytes match, given that the hash keys
1.1219 + * are equal and that HASH_BITS >= 8. Compare 2 bytes at a time at
1.1220 + * strstart+3, +5, ... up to strstart+257. We check for insufficient
1.1221 + * lookahead only every 4th comparison; the 128th check will be made
1.1222 + * at strstart+257. If MAX_MATCH-2 is not a multiple of 8, it is
1.1223 + * necessary to put more guard bytes at the end of the window, or
1.1224 + * to check more often for insufficient lookahead.
1.1225 + */
1.1226 + Assert(scan[2] == match[2], "scan[2]?");
1.1227 + scan++, match++;
1.1228 + do {
1.1229 + } while (*(ushf*)(scan+=2) == *(ushf*)(match+=2) &&
1.1230 + *(ushf*)(scan+=2) == *(ushf*)(match+=2) &&
1.1231 + *(ushf*)(scan+=2) == *(ushf*)(match+=2) &&
1.1232 + *(ushf*)(scan+=2) == *(ushf*)(match+=2) &&
1.1233 + scan < strend);
1.1234 + /* The funny "do {}" generates better code on most compilers */
1.1235 +
1.1236 + /* Here, scan <= window+strstart+257 */
1.1237 + Assert(scan <= s->window+(unsigned)(s->window_size-1), "wild scan");
1.1238 + if (*scan == *match) scan++;
1.1239 +
1.1240 + len = (MAX_MATCH - 1) - (int)(strend-scan);
1.1241 + scan = strend - (MAX_MATCH-1);
1.1242 +
1.1243 +#else /* UNALIGNED_OK */
1.1244 +
1.1245 + if (match[best_len] != scan_end ||
1.1246 + match[best_len-1] != scan_end1 ||
1.1247 + *match != *scan ||
1.1248 + *++match != scan[1]) continue;
1.1249 +
1.1250 + /* The check at best_len-1 can be removed because it will be made
1.1251 + * again later. (This heuristic is not always a win.)
1.1252 + * It is not necessary to compare scan[2] and match[2] since they
1.1253 + * are always equal when the other bytes match, given that
1.1254 + * the hash keys are equal and that HASH_BITS >= 8.
1.1255 + */
1.1256 + scan += 2, match++;
1.1257 + Assert(*scan == *match, "match[2]?");
1.1258 +
1.1259 + /* We check for insufficient lookahead only every 8th comparison;
1.1260 + * the 256th check will be made at strstart+258.
1.1261 + */
1.1262 + do {
1.1263 + } while (*++scan == *++match && *++scan == *++match &&
1.1264 + *++scan == *++match && *++scan == *++match &&
1.1265 + *++scan == *++match && *++scan == *++match &&
1.1266 + *++scan == *++match && *++scan == *++match &&
1.1267 + scan < strend);
1.1268 +
1.1269 + Assert(scan <= s->window+(unsigned)(s->window_size-1), "wild scan");
1.1270 +
1.1271 + len = MAX_MATCH - (int)(strend - scan);
1.1272 + scan = strend - MAX_MATCH;
1.1273 +
1.1274 +#endif /* UNALIGNED_OK */
1.1275 +
1.1276 + if (len > best_len) {
1.1277 + s->match_start = cur_match;
1.1278 + best_len = len;
1.1279 + if (len >= nice_match) break;
1.1280 +#ifdef UNALIGNED_OK
1.1281 + scan_end = *(ushf*)(scan+best_len-1);
1.1282 +#else
1.1283 + scan_end1 = scan[best_len-1];
1.1284 + scan_end = scan[best_len];
1.1285 +#endif
1.1286 + }
1.1287 + } while ((cur_match = prev[cur_match & wmask]) > limit
1.1288 + && --chain_length != 0);
1.1289 +
1.1290 + if ((uInt)best_len <= s->lookahead) return (uInt)best_len;
1.1291 + return s->lookahead;
1.1292 +}
1.1293 +#endif /* ASMV */
1.1294 +
1.1295 +#else /* FASTEST */
1.1296 +
1.1297 +/* ---------------------------------------------------------------------------
1.1298 + * Optimized version for FASTEST only
1.1299 + */
1.1300 +local uInt longest_match(s, cur_match)
1.1301 + deflate_state *s;
1.1302 + IPos cur_match; /* current match */
1.1303 +{
1.1304 + register Bytef *scan = s->window + s->strstart; /* current string */
1.1305 + register Bytef *match; /* matched string */
1.1306 + register int len; /* length of current match */
1.1307 + register Bytef *strend = s->window + s->strstart + MAX_MATCH;
1.1308 +
1.1309 + /* The code is optimized for HASH_BITS >= 8 and MAX_MATCH-2 multiple of 16.
1.1310 + * It is easy to get rid of this optimization if necessary.
1.1311 + */
1.1312 + Assert(s->hash_bits >= 8 && MAX_MATCH == 258, "Code too clever");
1.1313 +
1.1314 + Assert((ulg)s->strstart <= s->window_size-MIN_LOOKAHEAD, "need lookahead");
1.1315 +
1.1316 + Assert(cur_match < s->strstart, "no future");
1.1317 +
1.1318 + match = s->window + cur_match;
1.1319 +
1.1320 + /* Return failure if the match length is less than 2:
1.1321 + */
1.1322 + if (match[0] != scan[0] || match[1] != scan[1]) return MIN_MATCH-1;
1.1323 +
1.1324 + /* The check at best_len-1 can be removed because it will be made
1.1325 + * again later. (This heuristic is not always a win.)
1.1326 + * It is not necessary to compare scan[2] and match[2] since they
1.1327 + * are always equal when the other bytes match, given that
1.1328 + * the hash keys are equal and that HASH_BITS >= 8.
1.1329 + */
1.1330 + scan += 2, match += 2;
1.1331 + Assert(*scan == *match, "match[2]?");
1.1332 +
1.1333 + /* We check for insufficient lookahead only every 8th comparison;
1.1334 + * the 256th check will be made at strstart+258.
1.1335 + */
1.1336 + do {
1.1337 + } while (*++scan == *++match && *++scan == *++match &&
1.1338 + *++scan == *++match && *++scan == *++match &&
1.1339 + *++scan == *++match && *++scan == *++match &&
1.1340 + *++scan == *++match && *++scan == *++match &&
1.1341 + scan < strend);
1.1342 +
1.1343 + Assert(scan <= s->window+(unsigned)(s->window_size-1), "wild scan");
1.1344 +
1.1345 + len = MAX_MATCH - (int)(strend - scan);
1.1346 +
1.1347 + if (len < MIN_MATCH) return MIN_MATCH - 1;
1.1348 +
1.1349 + s->match_start = cur_match;
1.1350 + return (uInt)len <= s->lookahead ? (uInt)len : s->lookahead;
1.1351 +}
1.1352 +
1.1353 +#endif /* FASTEST */
1.1354 +
1.1355 +#ifdef DEBUG
1.1356 +/* ===========================================================================
1.1357 + * Check that the match at match_start is indeed a match.
1.1358 + */
1.1359 +local void check_match(s, start, match, length)
1.1360 + deflate_state *s;
1.1361 + IPos start, match;
1.1362 + int length;
1.1363 +{
1.1364 + /* check that the match is indeed a match */
1.1365 + if (zmemcmp(s->window + match,
1.1366 + s->window + start, length) != EQUAL) {
1.1367 + fprintf(stderr, " start %u, match %u, length %d\n",
1.1368 + start, match, length);
1.1369 + do {
1.1370 + fprintf(stderr, "%c%c", s->window[match++], s->window[start++]);
1.1371 + } while (--length != 0);
1.1372 + z_error("invalid match");
1.1373 + }
1.1374 + if (z_verbose > 1) {
1.1375 + fprintf(stderr,"\\[%d,%d]", start-match, length);
1.1376 + do { putc(s->window[start++], stderr); } while (--length != 0);
1.1377 + }
1.1378 +}
1.1379 +#else
1.1380 +# define check_match(s, start, match, length)
1.1381 +#endif /* DEBUG */
1.1382 +
1.1383 +/* ===========================================================================
1.1384 + * Fill the window when the lookahead becomes insufficient.
1.1385 + * Updates strstart and lookahead.
1.1386 + *
1.1387 + * IN assertion: lookahead < MIN_LOOKAHEAD
1.1388 + * OUT assertions: strstart <= window_size-MIN_LOOKAHEAD
1.1389 + * At least one byte has been read, or avail_in == 0; reads are
1.1390 + * performed for at least two bytes (required for the zip translate_eol
1.1391 + * option -- not supported here).
1.1392 + */
1.1393 +local void fill_window(s)
1.1394 + deflate_state *s;
1.1395 +{
1.1396 + register unsigned n, m;
1.1397 + register Posf *p;
1.1398 + unsigned more; /* Amount of free space at the end of the window. */
1.1399 + uInt wsize = s->w_size;
1.1400 +
1.1401 + Assert(s->lookahead < MIN_LOOKAHEAD, "already enough lookahead");
1.1402 +
1.1403 + do {
1.1404 + more = (unsigned)(s->window_size -(ulg)s->lookahead -(ulg)s->strstart);
1.1405 +
1.1406 + /* Deal with !@#$% 64K limit: */
1.1407 + if (sizeof(int) <= 2) {
1.1408 + if (more == 0 && s->strstart == 0 && s->lookahead == 0) {
1.1409 + more = wsize;
1.1410 +
1.1411 + } else if (more == (unsigned)(-1)) {
1.1412 + /* Very unlikely, but possible on 16 bit machine if
1.1413 + * strstart == 0 && lookahead == 1 (input done a byte at time)
1.1414 + */
1.1415 + more--;
1.1416 + }
1.1417 + }
1.1418 +
1.1419 + /* If the window is almost full and there is insufficient lookahead,
1.1420 + * move the upper half to the lower one to make room in the upper half.
1.1421 + */
1.1422 + if (s->strstart >= wsize+MAX_DIST(s)) {
1.1423 +
1.1424 + zmemcpy(s->window, s->window+wsize, (unsigned)wsize);
1.1425 + s->match_start -= wsize;
1.1426 + s->strstart -= wsize; /* we now have strstart >= MAX_DIST */
1.1427 + s->block_start -= (long) wsize;
1.1428 +
1.1429 + /* Slide the hash table (could be avoided with 32 bit values
1.1430 + at the expense of memory usage). We slide even when level == 0
1.1431 + to keep the hash table consistent if we switch back to level > 0
1.1432 + later. (Using level 0 permanently is not an optimal usage of
1.1433 + zlib, so we don't care about this pathological case.)
1.1434 + */
1.1435 + n = s->hash_size;
1.1436 + p = &s->head[n];
1.1437 + do {
1.1438 + m = *--p;
1.1439 + *p = (Pos)(m >= wsize ? m-wsize : NIL);
1.1440 + } while (--n);
1.1441 +
1.1442 + n = wsize;
1.1443 +#ifndef FASTEST
1.1444 + p = &s->prev[n];
1.1445 + do {
1.1446 + m = *--p;
1.1447 + *p = (Pos)(m >= wsize ? m-wsize : NIL);
1.1448 + /* If n is not on any hash chain, prev[n] is garbage but
1.1449 + * its value will never be used.
1.1450 + */
1.1451 + } while (--n);
1.1452 +#endif
1.1453 + more += wsize;
1.1454 + }
1.1455 + if (s->strm->avail_in == 0) break;
1.1456 +
1.1457 + /* If there was no sliding:
1.1458 + * strstart <= WSIZE+MAX_DIST-1 && lookahead <= MIN_LOOKAHEAD - 1 &&
1.1459 + * more == window_size - lookahead - strstart
1.1460 + * => more >= window_size - (MIN_LOOKAHEAD-1 + WSIZE + MAX_DIST-1)
1.1461 + * => more >= window_size - 2*WSIZE + 2
1.1462 + * In the BIG_MEM or MMAP case (not yet supported),
1.1463 + * window_size == input_size + MIN_LOOKAHEAD &&
1.1464 + * strstart + s->lookahead <= input_size => more >= MIN_LOOKAHEAD.
1.1465 + * Otherwise, window_size == 2*WSIZE so more >= 2.
1.1466 + * If there was sliding, more >= WSIZE. So in all cases, more >= 2.
1.1467 + */
1.1468 + Assert(more >= 2, "more < 2");
1.1469 +
1.1470 + n = read_buf(s->strm, s->window + s->strstart + s->lookahead, more);
1.1471 + s->lookahead += n;
1.1472 +
1.1473 + /* Initialize the hash value now that we have some input: */
1.1474 + if (s->lookahead + s->insert >= MIN_MATCH) {
1.1475 + uInt str = s->strstart - s->insert;
1.1476 + s->ins_h = s->window[str];
1.1477 + UPDATE_HASH(s, s->ins_h, s->window[str + 1]);
1.1478 +#if MIN_MATCH != 3
1.1479 + Call UPDATE_HASH() MIN_MATCH-3 more times
1.1480 +#endif
1.1481 + while (s->insert) {
1.1482 + UPDATE_HASH(s, s->ins_h, s->window[str + MIN_MATCH-1]);
1.1483 +#ifndef FASTEST
1.1484 + s->prev[str & s->w_mask] = s->head[s->ins_h];
1.1485 +#endif
1.1486 + s->head[s->ins_h] = (Pos)str;
1.1487 + str++;
1.1488 + s->insert--;
1.1489 + if (s->lookahead + s->insert < MIN_MATCH)
1.1490 + break;
1.1491 + }
1.1492 + }
1.1493 + /* If the whole input has less than MIN_MATCH bytes, ins_h is garbage,
1.1494 + * but this is not important since only literal bytes will be emitted.
1.1495 + */
1.1496 +
1.1497 + } while (s->lookahead < MIN_LOOKAHEAD && s->strm->avail_in != 0);
1.1498 +
1.1499 + /* If the WIN_INIT bytes after the end of the current data have never been
1.1500 + * written, then zero those bytes in order to avoid memory check reports of
1.1501 + * the use of uninitialized (or uninitialised as Julian writes) bytes by
1.1502 + * the longest match routines. Update the high water mark for the next
1.1503 + * time through here. WIN_INIT is set to MAX_MATCH since the longest match
1.1504 + * routines allow scanning to strstart + MAX_MATCH, ignoring lookahead.
1.1505 + */
1.1506 + if (s->high_water < s->window_size) {
1.1507 + ulg curr = s->strstart + (ulg)(s->lookahead);
1.1508 + ulg init;
1.1509 +
1.1510 + if (s->high_water < curr) {
1.1511 + /* Previous high water mark below current data -- zero WIN_INIT
1.1512 + * bytes or up to end of window, whichever is less.
1.1513 + */
1.1514 + init = s->window_size - curr;
1.1515 + if (init > WIN_INIT)
1.1516 + init = WIN_INIT;
1.1517 + zmemzero(s->window + curr, (unsigned)init);
1.1518 + s->high_water = curr + init;
1.1519 + }
1.1520 + else if (s->high_water < (ulg)curr + WIN_INIT) {
1.1521 + /* High water mark at or above current data, but below current data
1.1522 + * plus WIN_INIT -- zero out to current data plus WIN_INIT, or up
1.1523 + * to end of window, whichever is less.
1.1524 + */
1.1525 + init = (ulg)curr + WIN_INIT - s->high_water;
1.1526 + if (init > s->window_size - s->high_water)
1.1527 + init = s->window_size - s->high_water;
1.1528 + zmemzero(s->window + s->high_water, (unsigned)init);
1.1529 + s->high_water += init;
1.1530 + }
1.1531 + }
1.1532 +
1.1533 + Assert((ulg)s->strstart <= s->window_size - MIN_LOOKAHEAD,
1.1534 + "not enough room for search");
1.1535 +}
1.1536 +
1.1537 +/* ===========================================================================
1.1538 + * Flush the current block, with given end-of-file flag.
1.1539 + * IN assertion: strstart is set to the end of the current match.
1.1540 + */
1.1541 +#define FLUSH_BLOCK_ONLY(s, last) { \
1.1542 + _tr_flush_block(s, (s->block_start >= 0L ? \
1.1543 + (charf *)&s->window[(unsigned)s->block_start] : \
1.1544 + (charf *)Z_NULL), \
1.1545 + (ulg)((long)s->strstart - s->block_start), \
1.1546 + (last)); \
1.1547 + s->block_start = s->strstart; \
1.1548 + flush_pending(s->strm); \
1.1549 + Tracev((stderr,"[FLUSH]")); \
1.1550 +}
1.1551 +
1.1552 +/* Same but force premature exit if necessary. */
1.1553 +#define FLUSH_BLOCK(s, last) { \
1.1554 + FLUSH_BLOCK_ONLY(s, last); \
1.1555 + if (s->strm->avail_out == 0) return (last) ? finish_started : need_more; \
1.1556 +}
1.1557 +
1.1558 +/* ===========================================================================
1.1559 + * Copy without compression as much as possible from the input stream, return
1.1560 + * the current block state.
1.1561 + * This function does not insert new strings in the dictionary since
1.1562 + * uncompressible data is probably not useful. This function is used
1.1563 + * only for the level=0 compression option.
1.1564 + * NOTE: this function should be optimized to avoid extra copying from
1.1565 + * window to pending_buf.
1.1566 + */
1.1567 +local block_state deflate_stored(s, flush)
1.1568 + deflate_state *s;
1.1569 + int flush;
1.1570 +{
1.1571 + /* Stored blocks are limited to 0xffff bytes, pending_buf is limited
1.1572 + * to pending_buf_size, and each stored block has a 5 byte header:
1.1573 + */
1.1574 + ulg max_block_size = 0xffff;
1.1575 + ulg max_start;
1.1576 +
1.1577 + if (max_block_size > s->pending_buf_size - 5) {
1.1578 + max_block_size = s->pending_buf_size - 5;
1.1579 + }
1.1580 +
1.1581 + /* Copy as much as possible from input to output: */
1.1582 + for (;;) {
1.1583 + /* Fill the window as much as possible: */
1.1584 + if (s->lookahead <= 1) {
1.1585 +
1.1586 + Assert(s->strstart < s->w_size+MAX_DIST(s) ||
1.1587 + s->block_start >= (long)s->w_size, "slide too late");
1.1588 +
1.1589 + fill_window(s);
1.1590 + if (s->lookahead == 0 && flush == Z_NO_FLUSH) return need_more;
1.1591 +
1.1592 + if (s->lookahead == 0) break; /* flush the current block */
1.1593 + }
1.1594 + Assert(s->block_start >= 0L, "block gone");
1.1595 +
1.1596 + s->strstart += s->lookahead;
1.1597 + s->lookahead = 0;
1.1598 +
1.1599 + /* Emit a stored block if pending_buf will be full: */
1.1600 + max_start = s->block_start + max_block_size;
1.1601 + if (s->strstart == 0 || (ulg)s->strstart >= max_start) {
1.1602 + /* strstart == 0 is possible when wraparound on 16-bit machine */
1.1603 + s->lookahead = (uInt)(s->strstart - max_start);
1.1604 + s->strstart = (uInt)max_start;
1.1605 + FLUSH_BLOCK(s, 0);
1.1606 + }
1.1607 + /* Flush if we may have to slide, otherwise block_start may become
1.1608 + * negative and the data will be gone:
1.1609 + */
1.1610 + if (s->strstart - (uInt)s->block_start >= MAX_DIST(s)) {
1.1611 + FLUSH_BLOCK(s, 0);
1.1612 + }
1.1613 + }
1.1614 + s->insert = 0;
1.1615 + if (flush == Z_FINISH) {
1.1616 + FLUSH_BLOCK(s, 1);
1.1617 + return finish_done;
1.1618 + }
1.1619 + if ((long)s->strstart > s->block_start)
1.1620 + FLUSH_BLOCK(s, 0);
1.1621 + return block_done;
1.1622 +}
1.1623 +
1.1624 +/* ===========================================================================
1.1625 + * Compress as much as possible from the input stream, return the current
1.1626 + * block state.
1.1627 + * This function does not perform lazy evaluation of matches and inserts
1.1628 + * new strings in the dictionary only for unmatched strings or for short
1.1629 + * matches. It is used only for the fast compression options.
1.1630 + */
1.1631 +local block_state deflate_fast(s, flush)
1.1632 + deflate_state *s;
1.1633 + int flush;
1.1634 +{
1.1635 + IPos hash_head; /* head of the hash chain */
1.1636 + int bflush; /* set if current block must be flushed */
1.1637 +
1.1638 + for (;;) {
1.1639 + /* Make sure that we always have enough lookahead, except
1.1640 + * at the end of the input file. We need MAX_MATCH bytes
1.1641 + * for the next match, plus MIN_MATCH bytes to insert the
1.1642 + * string following the next match.
1.1643 + */
1.1644 + if (s->lookahead < MIN_LOOKAHEAD) {
1.1645 + fill_window(s);
1.1646 + if (s->lookahead < MIN_LOOKAHEAD && flush == Z_NO_FLUSH) {
1.1647 + return need_more;
1.1648 + }
1.1649 + if (s->lookahead == 0) break; /* flush the current block */
1.1650 + }
1.1651 +
1.1652 + /* Insert the string window[strstart .. strstart+2] in the
1.1653 + * dictionary, and set hash_head to the head of the hash chain:
1.1654 + */
1.1655 + hash_head = NIL;
1.1656 + if (s->lookahead >= MIN_MATCH) {
1.1657 + INSERT_STRING(s, s->strstart, hash_head);
1.1658 + }
1.1659 +
1.1660 + /* Find the longest match, discarding those <= prev_length.
1.1661 + * At this point we have always match_length < MIN_MATCH
1.1662 + */
1.1663 + if (hash_head != NIL && s->strstart - hash_head <= MAX_DIST(s)) {
1.1664 + /* To simplify the code, we prevent matches with the string
1.1665 + * of window index 0 (in particular we have to avoid a match
1.1666 + * of the string with itself at the start of the input file).
1.1667 + */
1.1668 + s->match_length = longest_match (s, hash_head);
1.1669 + /* longest_match() sets match_start */
1.1670 + }
1.1671 + if (s->match_length >= MIN_MATCH) {
1.1672 + check_match(s, s->strstart, s->match_start, s->match_length);
1.1673 +
1.1674 + _tr_tally_dist(s, s->strstart - s->match_start,
1.1675 + s->match_length - MIN_MATCH, bflush);
1.1676 +
1.1677 + s->lookahead -= s->match_length;
1.1678 +
1.1679 + /* Insert new strings in the hash table only if the match length
1.1680 + * is not too large. This saves time but degrades compression.
1.1681 + */
1.1682 +#ifndef FASTEST
1.1683 + if (s->match_length <= s->max_insert_length &&
1.1684 + s->lookahead >= MIN_MATCH) {
1.1685 + s->match_length--; /* string at strstart already in table */
1.1686 + do {
1.1687 + s->strstart++;
1.1688 + INSERT_STRING(s, s->strstart, hash_head);
1.1689 + /* strstart never exceeds WSIZE-MAX_MATCH, so there are
1.1690 + * always MIN_MATCH bytes ahead.
1.1691 + */
1.1692 + } while (--s->match_length != 0);
1.1693 + s->strstart++;
1.1694 + } else
1.1695 +#endif
1.1696 + {
1.1697 + s->strstart += s->match_length;
1.1698 + s->match_length = 0;
1.1699 + s->ins_h = s->window[s->strstart];
1.1700 + UPDATE_HASH(s, s->ins_h, s->window[s->strstart+1]);
1.1701 +#if MIN_MATCH != 3
1.1702 + Call UPDATE_HASH() MIN_MATCH-3 more times
1.1703 +#endif
1.1704 + /* If lookahead < MIN_MATCH, ins_h is garbage, but it does not
1.1705 + * matter since it will be recomputed at next deflate call.
1.1706 + */
1.1707 + }
1.1708 + } else {
1.1709 + /* No match, output a literal byte */
1.1710 + Tracevv((stderr,"%c", s->window[s->strstart]));
1.1711 + _tr_tally_lit (s, s->window[s->strstart], bflush);
1.1712 + s->lookahead--;
1.1713 + s->strstart++;
1.1714 + }
1.1715 + if (bflush) FLUSH_BLOCK(s, 0);
1.1716 + }
1.1717 + s->insert = s->strstart < MIN_MATCH-1 ? s->strstart : MIN_MATCH-1;
1.1718 + if (flush == Z_FINISH) {
1.1719 + FLUSH_BLOCK(s, 1);
1.1720 + return finish_done;
1.1721 + }
1.1722 + if (s->last_lit)
1.1723 + FLUSH_BLOCK(s, 0);
1.1724 + return block_done;
1.1725 +}
1.1726 +
1.1727 +#ifndef FASTEST
1.1728 +/* ===========================================================================
1.1729 + * Same as above, but achieves better compression. We use a lazy
1.1730 + * evaluation for matches: a match is finally adopted only if there is
1.1731 + * no better match at the next window position.
1.1732 + */
1.1733 +local block_state deflate_slow(s, flush)
1.1734 + deflate_state *s;
1.1735 + int flush;
1.1736 +{
1.1737 + IPos hash_head; /* head of hash chain */
1.1738 + int bflush; /* set if current block must be flushed */
1.1739 +
1.1740 + /* Process the input block. */
1.1741 + for (;;) {
1.1742 + /* Make sure that we always have enough lookahead, except
1.1743 + * at the end of the input file. We need MAX_MATCH bytes
1.1744 + * for the next match, plus MIN_MATCH bytes to insert the
1.1745 + * string following the next match.
1.1746 + */
1.1747 + if (s->lookahead < MIN_LOOKAHEAD) {
1.1748 + fill_window(s);
1.1749 + if (s->lookahead < MIN_LOOKAHEAD && flush == Z_NO_FLUSH) {
1.1750 + return need_more;
1.1751 + }
1.1752 + if (s->lookahead == 0) break; /* flush the current block */
1.1753 + }
1.1754 +
1.1755 + /* Insert the string window[strstart .. strstart+2] in the
1.1756 + * dictionary, and set hash_head to the head of the hash chain:
1.1757 + */
1.1758 + hash_head = NIL;
1.1759 + if (s->lookahead >= MIN_MATCH) {
1.1760 + INSERT_STRING(s, s->strstart, hash_head);
1.1761 + }
1.1762 +
1.1763 + /* Find the longest match, discarding those <= prev_length.
1.1764 + */
1.1765 + s->prev_length = s->match_length, s->prev_match = s->match_start;
1.1766 + s->match_length = MIN_MATCH-1;
1.1767 +
1.1768 + if (hash_head != NIL && s->prev_length < s->max_lazy_match &&
1.1769 + s->strstart - hash_head <= MAX_DIST(s)) {
1.1770 + /* To simplify the code, we prevent matches with the string
1.1771 + * of window index 0 (in particular we have to avoid a match
1.1772 + * of the string with itself at the start of the input file).
1.1773 + */
1.1774 + s->match_length = longest_match (s, hash_head);
1.1775 + /* longest_match() sets match_start */
1.1776 +
1.1777 + if (s->match_length <= 5 && (s->strategy == Z_FILTERED
1.1778 +#if TOO_FAR <= 32767
1.1779 + || (s->match_length == MIN_MATCH &&
1.1780 + s->strstart - s->match_start > TOO_FAR)
1.1781 +#endif
1.1782 + )) {
1.1783 +
1.1784 + /* If prev_match is also MIN_MATCH, match_start is garbage
1.1785 + * but we will ignore the current match anyway.
1.1786 + */
1.1787 + s->match_length = MIN_MATCH-1;
1.1788 + }
1.1789 + }
1.1790 + /* If there was a match at the previous step and the current
1.1791 + * match is not better, output the previous match:
1.1792 + */
1.1793 + if (s->prev_length >= MIN_MATCH && s->match_length <= s->prev_length) {
1.1794 + uInt max_insert = s->strstart + s->lookahead - MIN_MATCH;
1.1795 + /* Do not insert strings in hash table beyond this. */
1.1796 +
1.1797 + check_match(s, s->strstart-1, s->prev_match, s->prev_length);
1.1798 +
1.1799 + _tr_tally_dist(s, s->strstart -1 - s->prev_match,
1.1800 + s->prev_length - MIN_MATCH, bflush);
1.1801 +
1.1802 + /* Insert in hash table all strings up to the end of the match.
1.1803 + * strstart-1 and strstart are already inserted. If there is not
1.1804 + * enough lookahead, the last two strings are not inserted in
1.1805 + * the hash table.
1.1806 + */
1.1807 + s->lookahead -= s->prev_length-1;
1.1808 + s->prev_length -= 2;
1.1809 + do {
1.1810 + if (++s->strstart <= max_insert) {
1.1811 + INSERT_STRING(s, s->strstart, hash_head);
1.1812 + }
1.1813 + } while (--s->prev_length != 0);
1.1814 + s->match_available = 0;
1.1815 + s->match_length = MIN_MATCH-1;
1.1816 + s->strstart++;
1.1817 +
1.1818 + if (bflush) FLUSH_BLOCK(s, 0);
1.1819 +
1.1820 + } else if (s->match_available) {
1.1821 + /* If there was no match at the previous position, output a
1.1822 + * single literal. If there was a match but the current match
1.1823 + * is longer, truncate the previous match to a single literal.
1.1824 + */
1.1825 + Tracevv((stderr,"%c", s->window[s->strstart-1]));
1.1826 + _tr_tally_lit(s, s->window[s->strstart-1], bflush);
1.1827 + if (bflush) {
1.1828 + FLUSH_BLOCK_ONLY(s, 0);
1.1829 + }
1.1830 + s->strstart++;
1.1831 + s->lookahead--;
1.1832 + if (s->strm->avail_out == 0) return need_more;
1.1833 + } else {
1.1834 + /* There is no previous match to compare with, wait for
1.1835 + * the next step to decide.
1.1836 + */
1.1837 + s->match_available = 1;
1.1838 + s->strstart++;
1.1839 + s->lookahead--;
1.1840 + }
1.1841 + }
1.1842 + Assert (flush != Z_NO_FLUSH, "no flush?");
1.1843 + if (s->match_available) {
1.1844 + Tracevv((stderr,"%c", s->window[s->strstart-1]));
1.1845 + _tr_tally_lit(s, s->window[s->strstart-1], bflush);
1.1846 + s->match_available = 0;
1.1847 + }
1.1848 + s->insert = s->strstart < MIN_MATCH-1 ? s->strstart : MIN_MATCH-1;
1.1849 + if (flush == Z_FINISH) {
1.1850 + FLUSH_BLOCK(s, 1);
1.1851 + return finish_done;
1.1852 + }
1.1853 + if (s->last_lit)
1.1854 + FLUSH_BLOCK(s, 0);
1.1855 + return block_done;
1.1856 +}
1.1857 +#endif /* FASTEST */
1.1858 +
1.1859 +/* ===========================================================================
1.1860 + * For Z_RLE, simply look for runs of bytes, generate matches only of distance
1.1861 + * one. Do not maintain a hash table. (It will be regenerated if this run of
1.1862 + * deflate switches away from Z_RLE.)
1.1863 + */
1.1864 +local block_state deflate_rle(s, flush)
1.1865 + deflate_state *s;
1.1866 + int flush;
1.1867 +{
1.1868 + int bflush; /* set if current block must be flushed */
1.1869 + uInt prev; /* byte at distance one to match */
1.1870 + Bytef *scan, *strend; /* scan goes up to strend for length of run */
1.1871 +
1.1872 + for (;;) {
1.1873 + /* Make sure that we always have enough lookahead, except
1.1874 + * at the end of the input file. We need MAX_MATCH bytes
1.1875 + * for the longest run, plus one for the unrolled loop.
1.1876 + */
1.1877 + if (s->lookahead <= MAX_MATCH) {
1.1878 + fill_window(s);
1.1879 + if (s->lookahead <= MAX_MATCH && flush == Z_NO_FLUSH) {
1.1880 + return need_more;
1.1881 + }
1.1882 + if (s->lookahead == 0) break; /* flush the current block */
1.1883 + }
1.1884 +
1.1885 + /* See how many times the previous byte repeats */
1.1886 + s->match_length = 0;
1.1887 + if (s->lookahead >= MIN_MATCH && s->strstart > 0) {
1.1888 + scan = s->window + s->strstart - 1;
1.1889 + prev = *scan;
1.1890 + if (prev == *++scan && prev == *++scan && prev == *++scan) {
1.1891 + strend = s->window + s->strstart + MAX_MATCH;
1.1892 + do {
1.1893 + } while (prev == *++scan && prev == *++scan &&
1.1894 + prev == *++scan && prev == *++scan &&
1.1895 + prev == *++scan && prev == *++scan &&
1.1896 + prev == *++scan && prev == *++scan &&
1.1897 + scan < strend);
1.1898 + s->match_length = MAX_MATCH - (int)(strend - scan);
1.1899 + if (s->match_length > s->lookahead)
1.1900 + s->match_length = s->lookahead;
1.1901 + }
1.1902 + Assert(scan <= s->window+(uInt)(s->window_size-1), "wild scan");
1.1903 + }
1.1904 +
1.1905 + /* Emit match if have run of MIN_MATCH or longer, else emit literal */
1.1906 + if (s->match_length >= MIN_MATCH) {
1.1907 + check_match(s, s->strstart, s->strstart - 1, s->match_length);
1.1908 +
1.1909 + _tr_tally_dist(s, 1, s->match_length - MIN_MATCH, bflush);
1.1910 +
1.1911 + s->lookahead -= s->match_length;
1.1912 + s->strstart += s->match_length;
1.1913 + s->match_length = 0;
1.1914 + } else {
1.1915 + /* No match, output a literal byte */
1.1916 + Tracevv((stderr,"%c", s->window[s->strstart]));
1.1917 + _tr_tally_lit (s, s->window[s->strstart], bflush);
1.1918 + s->lookahead--;
1.1919 + s->strstart++;
1.1920 + }
1.1921 + if (bflush) FLUSH_BLOCK(s, 0);
1.1922 + }
1.1923 + s->insert = 0;
1.1924 + if (flush == Z_FINISH) {
1.1925 + FLUSH_BLOCK(s, 1);
1.1926 + return finish_done;
1.1927 + }
1.1928 + if (s->last_lit)
1.1929 + FLUSH_BLOCK(s, 0);
1.1930 + return block_done;
1.1931 +}
1.1932 +
1.1933 +/* ===========================================================================
1.1934 + * For Z_HUFFMAN_ONLY, do not look for matches. Do not maintain a hash table.
1.1935 + * (It will be regenerated if this run of deflate switches away from Huffman.)
1.1936 + */
1.1937 +local block_state deflate_huff(s, flush)
1.1938 + deflate_state *s;
1.1939 + int flush;
1.1940 +{
1.1941 + int bflush; /* set if current block must be flushed */
1.1942 +
1.1943 + for (;;) {
1.1944 + /* Make sure that we have a literal to write. */
1.1945 + if (s->lookahead == 0) {
1.1946 + fill_window(s);
1.1947 + if (s->lookahead == 0) {
1.1948 + if (flush == Z_NO_FLUSH)
1.1949 + return need_more;
1.1950 + break; /* flush the current block */
1.1951 + }
1.1952 + }
1.1953 +
1.1954 + /* Output a literal byte */
1.1955 + s->match_length = 0;
1.1956 + Tracevv((stderr,"%c", s->window[s->strstart]));
1.1957 + _tr_tally_lit (s, s->window[s->strstart], bflush);
1.1958 + s->lookahead--;
1.1959 + s->strstart++;
1.1960 + if (bflush) FLUSH_BLOCK(s, 0);
1.1961 + }
1.1962 + s->insert = 0;
1.1963 + if (flush == Z_FINISH) {
1.1964 + FLUSH_BLOCK(s, 1);
1.1965 + return finish_done;
1.1966 + }
1.1967 + if (s->last_lit)
1.1968 + FLUSH_BLOCK(s, 0);
1.1969 + return block_done;
1.1970 +}
