diff options
Diffstat (limited to 'src/Common/zlib/deflate.c')
| -rw-r--r-- | src/Common/zlib/deflate.c | 612 |
1 files changed, 267 insertions, 345 deletions
diff --git a/src/Common/zlib/deflate.c b/src/Common/zlib/deflate.c index 4a689db3..012ea814 100644 --- a/src/Common/zlib/deflate.c +++ b/src/Common/zlib/deflate.c @@ -1,5 +1,5 @@ /* deflate.c -- compress data using the deflation algorithm - * Copyright (C) 1995-2022 Jean-loup Gailly and Mark Adler + * Copyright (C) 1995-2024 Jean-loup Gailly and Mark Adler * For conditions of distribution and use, see copyright notice in zlib.h */ @@ -52,7 +52,7 @@ #include "deflate.h" const char deflate_copyright[] = - " deflate 1.2.13 Copyright 1995-2022 Jean-loup Gailly and Mark Adler "; + " deflate 1.3.1 Copyright 1995-2024 Jean-loup Gailly and Mark Adler "; /* If you use the zlib library in a product, an acknowledgment is welcome in the documentation of your product. If for some reason you cannot @@ -60,9 +60,6 @@ const char deflate_copyright[] = copyright string in the executable of your product. */ -/* =========================================================================== - * Function prototypes. - */ typedef enum { need_more, /* block not completed, need more input or more output */ block_done, /* block flush performed */ @@ -70,29 +67,16 @@ typedef enum { finish_done /* finish done, accept no more input or output */ } block_state; -typedef block_state (*compress_func) OF((deflate_state *s, int flush)); +typedef block_state (*compress_func)(deflate_state *s, int flush); /* Compression function. Returns the block state after the call. */ -local int deflateStateCheck OF((z_streamp strm)); -local void slide_hash OF((deflate_state *s)); -local void fill_window OF((deflate_state *s)); -local block_state deflate_stored OF((deflate_state *s, int flush)); -local block_state deflate_fast OF((deflate_state *s, int flush)); +local block_state deflate_stored(deflate_state *s, int flush); +local block_state deflate_fast(deflate_state *s, int flush); #ifndef FASTEST -local block_state deflate_slow OF((deflate_state *s, int flush)); -#endif -local block_state deflate_rle OF((deflate_state *s, int flush)); -local block_state deflate_huff OF((deflate_state *s, int flush)); -local void lm_init OF((deflate_state *s)); -local void putShortMSB OF((deflate_state *s, uInt b)); -local void flush_pending OF((z_streamp strm)); -local unsigned read_buf OF((z_streamp strm, Bytef *buf, unsigned size)); -local uInt longest_match OF((deflate_state *s, IPos cur_match)); - -#ifdef ZLIB_DEBUG -local void check_match OF((deflate_state *s, IPos start, IPos match, - int length)); +local block_state deflate_slow(deflate_state *s, int flush); #endif +local block_state deflate_rle(deflate_state *s, int flush); +local block_state deflate_huff(deflate_state *s, int flush); /* =========================================================================== * Local data @@ -195,9 +179,12 @@ local const config configuration_table[10] = { * bit values at the expense of memory usage). We slide even when level == 0 to * keep the hash table consistent if we switch back to level > 0 later. */ -local void slide_hash(s) - deflate_state *s; -{ +#if defined(__has_feature) +# if __has_feature(memory_sanitizer) + __attribute__((no_sanitize("memory"))) +# endif +#endif +local void slide_hash(deflate_state *s) { unsigned n, m; Posf *p; uInt wsize = s->w_size; @@ -221,30 +208,177 @@ local void slide_hash(s) #endif } +/* =========================================================================== + * Read a new buffer from the current input stream, update the adler32 + * and total number of bytes read. All deflate() input goes through + * this function so some applications may wish to modify it to avoid + * allocating a large strm->next_in buffer and copying from it. + * (See also flush_pending()). + */ +local unsigned read_buf(z_streamp strm, Bytef *buf, unsigned size) { + unsigned len = strm->avail_in; + + if (len > size) len = size; + if (len == 0) return 0; + + strm->avail_in -= len; + + zmemcpy(buf, strm->next_in, len); + if (strm->state->wrap == 1) { + strm->adler = adler32(strm->adler, buf, len); + } +#ifdef GZIP + else if (strm->state->wrap == 2) { + strm->adler = crc32(strm->adler, buf, len); + } +#endif + strm->next_in += len; + strm->total_in += len; + + return len; +} + +/* =========================================================================== + * Fill the window when the lookahead becomes insufficient. + * Updates strstart and lookahead. + * + * IN assertion: lookahead < MIN_LOOKAHEAD + * OUT assertions: strstart <= window_size-MIN_LOOKAHEAD + * At least one byte has been read, or avail_in == 0; reads are + * performed for at least two bytes (required for the zip translate_eol + * option -- not supported here). + */ +local void fill_window(deflate_state *s) { + unsigned n; + unsigned more; /* Amount of free space at the end of the window. */ + uInt wsize = s->w_size; + + Assert(s->lookahead < MIN_LOOKAHEAD, "already enough lookahead"); + + do { + more = (unsigned)(s->window_size -(ulg)s->lookahead -(ulg)s->strstart); + + /* Deal with !@#$% 64K limit: */ + if (sizeof(int) <= 2) { + if (more == 0 && s->strstart == 0 && s->lookahead == 0) { + more = wsize; + + } else if (more == (unsigned)(-1)) { + /* Very unlikely, but possible on 16 bit machine if + * strstart == 0 && lookahead == 1 (input done a byte at time) + */ + more--; + } + } + + /* If the window is almost full and there is insufficient lookahead, + * move the upper half to the lower one to make room in the upper half. + */ + if (s->strstart >= wsize + MAX_DIST(s)) { + + zmemcpy(s->window, s->window + wsize, (unsigned)wsize - more); + s->match_start -= wsize; + s->strstart -= wsize; /* we now have strstart >= MAX_DIST */ + s->block_start -= (long) wsize; + if (s->insert > s->strstart) + s->insert = s->strstart; + slide_hash(s); + more += wsize; + } + if (s->strm->avail_in == 0) break; + + /* If there was no sliding: + * strstart <= WSIZE+MAX_DIST-1 && lookahead <= MIN_LOOKAHEAD - 1 && + * more == window_size - lookahead - strstart + * => more >= window_size - (MIN_LOOKAHEAD-1 + WSIZE + MAX_DIST-1) + * => more >= window_size - 2*WSIZE + 2 + * In the BIG_MEM or MMAP case (not yet supported), + * window_size == input_size + MIN_LOOKAHEAD && + * strstart + s->lookahead <= input_size => more >= MIN_LOOKAHEAD. + * Otherwise, window_size == 2*WSIZE so more >= 2. + * If there was sliding, more >= WSIZE. So in all cases, more >= 2. + */ + Assert(more >= 2, "more < 2"); + + n = read_buf(s->strm, s->window + s->strstart + s->lookahead, more); + s->lookahead += n; + + /* Initialize the hash value now that we have some input: */ + if (s->lookahead + s->insert >= MIN_MATCH) { + uInt str = s->strstart - s->insert; + s->ins_h = s->window[str]; + UPDATE_HASH(s, s->ins_h, s->window[str + 1]); +#if MIN_MATCH != 3 + Call UPDATE_HASH() MIN_MATCH-3 more times +#endif + while (s->insert) { + UPDATE_HASH(s, s->ins_h, s->window[str + MIN_MATCH-1]); +#ifndef FASTEST + s->prev[str & s->w_mask] = s->head[s->ins_h]; +#endif + s->head[s->ins_h] = (Pos)str; + str++; + s->insert--; + if (s->lookahead + s->insert < MIN_MATCH) + break; + } + } + /* If the whole input has less than MIN_MATCH bytes, ins_h is garbage, + * but this is not important since only literal bytes will be emitted. + */ + + } while (s->lookahead < MIN_LOOKAHEAD && s->strm->avail_in != 0); + + /* If the WIN_INIT bytes after the end of the current data have never been + * written, then zero those bytes in order to avoid memory check reports of + * the use of uninitialized (or uninitialised as Julian writes) bytes by + * the longest match routines. Update the high water mark for the next + * time through here. WIN_INIT is set to MAX_MATCH since the longest match + * routines allow scanning to strstart + MAX_MATCH, ignoring lookahead. + */ + if (s->high_water < s->window_size) { + ulg curr = s->strstart + (ulg)(s->lookahead); + ulg init; + + if (s->high_water < curr) { + /* Previous high water mark below current data -- zero WIN_INIT + * bytes or up to end of window, whichever is less. + */ + init = s->window_size - curr; + if (init > WIN_INIT) + init = WIN_INIT; + zmemzero(s->window + curr, (unsigned)init); + s->high_water = curr + init; + } + else if (s->high_water < (ulg)curr + WIN_INIT) { + /* High water mark at or above current data, but below current data + * plus WIN_INIT -- zero out to current data plus WIN_INIT, or up + * to end of window, whichever is less. + */ + init = (ulg)curr + WIN_INIT - s->high_water; + if (init > s->window_size - s->high_water) + init = s->window_size - s->high_water; + zmemzero(s->window + s->high_water, (unsigned)init); + s->high_water += init; + } + } + + Assert((ulg)s->strstart <= s->window_size - MIN_LOOKAHEAD, + "not enough room for search"); +} + /* ========================================================================= */ -int ZEXPORT deflateInit_(strm, level, version, stream_size) - z_streamp strm; - int level; - const char *version; - int stream_size; -{ +int ZEXPORT deflateInit_(z_streamp strm, int level, const char *version, + int stream_size) { return deflateInit2_(strm, level, Z_DEFLATED, MAX_WBITS, DEF_MEM_LEVEL, Z_DEFAULT_STRATEGY, version, stream_size); /* To do: ignore strm->next_in if we use it as window */ } /* ========================================================================= */ -int ZEXPORT deflateInit2_(strm, level, method, windowBits, memLevel, strategy, - version, stream_size) - z_streamp strm; - int level; - int method; - int windowBits; - int memLevel; - int strategy; - const char *version; - int stream_size; -{ +int ZEXPORT deflateInit2_(z_streamp strm, int level, int method, + int windowBits, int memLevel, int strategy, + const char *version, int stream_size) { deflate_state *s; int wrap = 1; static const char my_version[] = ZLIB_VERSION; @@ -359,7 +493,7 @@ int ZEXPORT deflateInit2_(strm, level, method, windowBits, memLevel, strategy, * symbols from which it is being constructed. */ - s->pending_buf = (uchf *) ZALLOC(strm, s->lit_bufsize, 4); + s->pending_buf = (uchf *) ZALLOC(strm, s->lit_bufsize, LIT_BUFS); s->pending_buf_size = (ulg)s->lit_bufsize * 4; if (s->window == Z_NULL || s->prev == Z_NULL || s->head == Z_NULL || @@ -369,8 +503,14 @@ int ZEXPORT deflateInit2_(strm, level, method, windowBits, memLevel, strategy, deflateEnd (strm); return Z_MEM_ERROR; } +#ifdef LIT_MEM + s->d_buf = (ushf *)(s->pending_buf + (s->lit_bufsize << 1)); + s->l_buf = s->pending_buf + (s->lit_bufsize << 2); + s->sym_end = s->lit_bufsize - 1; +#else s->sym_buf = s->pending_buf + s->lit_bufsize; s->sym_end = (s->lit_bufsize - 1) * 3; +#endif /* We avoid equality with lit_bufsize*3 because of wraparound at 64K * on 16 bit machines and because stored blocks are restricted to * 64K-1 bytes. @@ -386,9 +526,7 @@ int ZEXPORT deflateInit2_(strm, level, method, windowBits, memLevel, strategy, /* ========================================================================= * Check for a valid deflate stream state. Return 0 if ok, 1 if not. */ -local int deflateStateCheck(strm) - z_streamp strm; -{ +local int deflateStateCheck(z_streamp strm) { deflate_state *s; if (strm == Z_NULL || strm->zalloc == (alloc_func)0 || strm->zfree == (free_func)0) @@ -409,11 +547,8 @@ local int deflateStateCheck(strm) } /* ========================================================================= */ -int ZEXPORT deflateSetDictionary(strm, dictionary, dictLength) - z_streamp strm; - const Bytef *dictionary; - uInt dictLength; -{ +int ZEXPORT deflateSetDictionary(z_streamp strm, const Bytef *dictionary, + uInt dictLength) { deflate_state *s; uInt str, n; int wrap; @@ -478,11 +613,8 @@ int ZEXPORT deflateSetDictionary(strm, dictionary, dictLength) } /* ========================================================================= */ -int ZEXPORT deflateGetDictionary(strm, dictionary, dictLength) - z_streamp strm; - Bytef *dictionary; - uInt *dictLength; -{ +int ZEXPORT deflateGetDictionary(z_streamp strm, Bytef *dictionary, + uInt *dictLength) { deflate_state *s; uInt len; @@ -500,9 +632,7 @@ int ZEXPORT deflateGetDictionary(strm, dictionary, dictLength) } /* ========================================================================= */ -int ZEXPORT deflateResetKeep(strm) - z_streamp strm; -{ +int ZEXPORT deflateResetKeep(z_streamp strm) { deflate_state *s; if (deflateStateCheck(strm)) { @@ -537,10 +667,32 @@ int ZEXPORT deflateResetKeep(strm) return Z_OK; } +/* =========================================================================== + * Initialize the "longest match" routines for a new zlib stream + */ +local void lm_init(deflate_state *s) { + s->window_size = (ulg)2L*s->w_size; + + CLEAR_HASH(s); + + /* Set the default configuration parameters: + */ + s->max_lazy_match = configuration_table[s->level].max_lazy; + s->good_match = configuration_table[s->level].good_length; + s->nice_match = configuration_table[s->level].nice_length; + s->max_chain_length = configuration_table[s->level].max_chain; + + s->strstart = 0; + s->block_start = 0L; + s->lookahead = 0; + s->insert = 0; + s->match_length = s->prev_length = MIN_MATCH-1; + s->match_available = 0; + s->ins_h = 0; +} + /* ========================================================================= */ -int ZEXPORT deflateReset(strm) - z_streamp strm; -{ +int ZEXPORT deflateReset(z_streamp strm) { int ret; ret = deflateResetKeep(strm); @@ -550,10 +702,7 @@ int ZEXPORT deflateReset(strm) } /* ========================================================================= */ -int ZEXPORT deflateSetHeader(strm, head) - z_streamp strm; - gz_headerp head; -{ +int ZEXPORT deflateSetHeader(z_streamp strm, gz_headerp head) { if (deflateStateCheck(strm) || strm->state->wrap != 2) return Z_STREAM_ERROR; strm->state->gzhead = head; @@ -561,11 +710,7 @@ int ZEXPORT deflateSetHeader(strm, head) } /* ========================================================================= */ -int ZEXPORT deflatePending(strm, pending, bits) - unsigned *pending; - int *bits; - z_streamp strm; -{ +int ZEXPORT deflatePending(z_streamp strm, unsigned *pending, int *bits) { if (deflateStateCheck(strm)) return Z_STREAM_ERROR; if (pending != Z_NULL) *pending = strm->state->pending; @@ -575,19 +720,21 @@ int ZEXPORT deflatePending(strm, pending, bits) } /* ========================================================================= */ -int ZEXPORT deflatePrime(strm, bits, value) - z_streamp strm; - int bits; - int value; -{ +int ZEXPORT deflatePrime(z_streamp strm, int bits, int value) { deflate_state *s; int put; if (deflateStateCheck(strm)) return Z_STREAM_ERROR; s = strm->state; +#ifdef LIT_MEM + if (bits < 0 || bits > 16 || + (uchf *)s->d_buf < s->pending_out + ((Buf_size + 7) >> 3)) + return Z_BUF_ERROR; +#else if (bits < 0 || bits > 16 || s->sym_buf < s->pending_out + ((Buf_size + 7) >> 3)) return Z_BUF_ERROR; +#endif do { put = Buf_size - s->bi_valid; if (put > bits) @@ -602,11 +749,7 @@ int ZEXPORT deflatePrime(strm, bits, value) } /* ========================================================================= */ -int ZEXPORT deflateParams(strm, level, strategy) - z_streamp strm; - int level; - int strategy; -{ +int ZEXPORT deflateParams(z_streamp strm, int level, int strategy) { deflate_state *s; compress_func func; @@ -651,13 +794,8 @@ int ZEXPORT deflateParams(strm, level, strategy) } /* ========================================================================= */ -int ZEXPORT deflateTune(strm, good_length, max_lazy, nice_length, max_chain) - z_streamp strm; - int good_length; - int max_lazy; - int nice_length; - int max_chain; -{ +int ZEXPORT deflateTune(z_streamp strm, int good_length, int max_lazy, + int nice_length, int max_chain) { deflate_state *s; if (deflateStateCheck(strm)) return Z_STREAM_ERROR; @@ -693,10 +831,7 @@ int ZEXPORT deflateTune(strm, good_length, max_lazy, nice_length, max_chain) * * Shifts are used to approximate divisions, for speed. */ -uLong ZEXPORT deflateBound(strm, sourceLen) - z_streamp strm; - uLong sourceLen; -{ +uLong ZEXPORT deflateBound(z_streamp strm, uLong sourceLen) { deflate_state *s; uLong fixedlen, storelen, wraplen; @@ -752,7 +887,8 @@ uLong ZEXPORT deflateBound(strm, sourceLen) /* if not default parameters, return one of the conservative bounds */ if (s->w_bits != 15 || s->hash_bits != 8 + 7) - return (s->w_bits <= s->hash_bits ? fixedlen : storelen) + wraplen; + return (s->w_bits <= s->hash_bits && s->level ? fixedlen : storelen) + + wraplen; /* default settings: return tight bound for that case -- ~0.03% overhead plus a small constant */ @@ -765,10 +901,7 @@ uLong ZEXPORT deflateBound(strm, sourceLen) * IN assertion: the stream state is correct and there is enough room in * pending_buf. */ -local void putShortMSB(s, b) - deflate_state *s; - uInt b; -{ +local void putShortMSB(deflate_state *s, uInt b) { put_byte(s, (Byte)(b >> 8)); put_byte(s, (Byte)(b & 0xff)); } @@ -779,9 +912,7 @@ local void putShortMSB(s, b) * applications may wish to modify it to avoid allocating a large * strm->next_out buffer and copying into it. (See also read_buf()). */ -local void flush_pending(strm) - z_streamp strm; -{ +local void flush_pending(z_streamp strm) { unsigned len; deflate_state *s = strm->state; @@ -812,10 +943,7 @@ local void flush_pending(strm) } while (0) /* ========================================================================= */ -int ZEXPORT deflate(strm, flush) - z_streamp strm; - int flush; -{ +int ZEXPORT deflate(z_streamp strm, int flush) { int old_flush; /* value of flush param for previous deflate call */ deflate_state *s; @@ -1127,9 +1255,7 @@ int ZEXPORT deflate(strm, flush) } /* ========================================================================= */ -int ZEXPORT deflateEnd(strm) - z_streamp strm; -{ +int ZEXPORT deflateEnd(z_streamp strm) { int status; if (deflateStateCheck(strm)) return Z_STREAM_ERROR; @@ -1153,11 +1279,10 @@ int ZEXPORT deflateEnd(strm) * To simplify the source, this is not supported for 16-bit MSDOS (which * doesn't have enough memory anyway to duplicate compression states). */ -int ZEXPORT deflateCopy(dest, source) - z_streamp dest; - z_streamp source; -{ +int ZEXPORT deflateCopy(z_streamp dest, z_streamp source) { #ifdef MAXSEG_64K + (void)dest; + (void)source; return Z_STREAM_ERROR; #else deflate_state *ds; @@ -1181,7 +1306,7 @@ int ZEXPORT deflateCopy(dest, source) ds->window = (Bytef *) ZALLOC(dest, ds->w_size, 2*sizeof(Byte)); ds->prev = (Posf *) ZALLOC(dest, ds->w_size, sizeof(Pos)); ds->head = (Posf *) ZALLOC(dest, ds->hash_size, sizeof(Pos)); - ds->pending_buf = (uchf *) ZALLOC(dest, ds->lit_bufsize, 4); + ds->pending_buf = (uchf *) ZALLOC(dest, ds->lit_bufsize, LIT_BUFS); if (ds->window == Z_NULL || ds->prev == Z_NULL || ds->head == Z_NULL || ds->pending_buf == Z_NULL) { @@ -1192,10 +1317,15 @@ int ZEXPORT deflateCopy(dest, source) zmemcpy(ds->window, ss->window, ds->w_size * 2 * sizeof(Byte)); zmemcpy((voidpf)ds->prev, (voidpf)ss->prev, ds->w_size * sizeof(Pos)); zmemcpy((voidpf)ds->head, (voidpf)ss->head, ds->hash_size * sizeof(Pos)); - zmemcpy(ds->pending_buf, ss->pending_buf, (uInt)ds->pending_buf_size); + zmemcpy(ds->pending_buf, ss->pending_buf, ds->lit_bufsize * LIT_BUFS); ds->pending_out = ds->pending_buf + (ss->pending_out - ss->pending_buf); +#ifdef LIT_MEM + ds->d_buf = (ushf *)(ds->pending_buf + (ds->lit_bufsize << 1)); + ds->l_buf = ds->pending_buf + (ds->lit_bufsize << 2); +#else ds->sym_buf = ds->pending_buf + ds->lit_bufsize; +#endif ds->l_desc.dyn_tree = ds->dyn_ltree; ds->d_desc.dyn_tree = ds->dyn_dtree; @@ -1205,66 +1335,6 @@ int ZEXPORT deflateCopy(dest, source) #endif /* MAXSEG_64K */ } -/* =========================================================================== - * Read a new buffer from the current input stream, update the adler32 - * and total number of bytes read. All deflate() input goes through - * this function so some applications may wish to modify it to avoid - * allocating a large strm->next_in buffer and copying from it. - * (See also flush_pending()). - */ -local unsigned read_buf(strm, buf, size) - z_streamp strm; - Bytef *buf; - unsigned size; -{ - unsigned len = strm->avail_in; - - if (len > size) len = size; - if (len == 0) return 0; - - strm->avail_in -= len; - - zmemcpy(buf, strm->next_in, len); - if (strm->state->wrap == 1) { - strm->adler = adler32(strm->adler, buf, len); - } -#ifdef GZIP - else if (strm->state->wrap == 2) { - strm->adler = crc32(strm->adler, buf, len); - } -#endif - strm->next_in += len; - strm->total_in += len; - - return len; -} - -/* =========================================================================== - * Initialize the "longest match" routines for a new zlib stream - */ -local void lm_init(s) - deflate_state *s; -{ - s->window_size = (ulg)2L*s->w_size; - - CLEAR_HASH(s); - - /* Set the default configuration parameters: - */ - s->max_lazy_match = configuration_table[s->level].max_lazy; - s->good_match = configuration_table[s->level].good_length; - s->nice_match = configuration_table[s->level].nice_length; - s->max_chain_length = configuration_table[s->level].max_chain; - - s->strstart = 0; - s->block_start = 0L; - s->lookahead = 0; - s->insert = 0; - s->match_length = s->prev_length = MIN_MATCH-1; - s->match_available = 0; - s->ins_h = 0; -} - #ifndef FASTEST /* =========================================================================== * Set match_start to the longest match starting at the given string and @@ -1275,10 +1345,7 @@ local void lm_init(s) * string (strstart) and its distance is <= MAX_DIST, and prev_length >= 1 * OUT assertion: the match length is not greater than s->lookahead. */ -local uInt longest_match(s, cur_match) - deflate_state *s; - IPos cur_match; /* current match */ -{ +local uInt longest_match(deflate_state *s, IPos cur_match) { unsigned chain_length = s->max_chain_length;/* max hash chain length */ register Bytef *scan = s->window + s->strstart; /* current string */ register Bytef *match; /* matched string */ @@ -1426,10 +1493,7 @@ local uInt longest_match(s, cur_match) /* --------------------------------------------------------------------------- * Optimized version for FASTEST only */ -local uInt longest_match(s, cur_match) - deflate_state *s; - IPos cur_match; /* current match */ -{ +local uInt longest_match(deflate_state *s, IPos cur_match) { register Bytef *scan = s->window + s->strstart; /* current string */ register Bytef *match; /* matched string */ register int len; /* length of current match */ @@ -1490,19 +1554,23 @@ local uInt longest_match(s, cur_match) /* =========================================================================== * Check that the match at match_start is indeed a match. */ -local void check_match(s, start, match, length) - deflate_state *s; - IPos start, match; - int length; -{ +local void check_match(deflate_state *s, IPos start, IPos match, int length) { /* check that the match is indeed a match */ - if (zmemcmp(s->window + match, - s->window + start, length) != EQUAL) { - fprintf(stderr, " start %u, match %u, length %d\n", - start, match, length); + Bytef *back = s->window + (int)match, *here = s->window + start; + IPos len = length; + if (match == (IPos)-1) { + /* match starts one byte before the current window -- just compare the + subsequent length-1 bytes */ + back++; + here++; + len--; + } + if (zmemcmp(back, here, len) != EQUAL) { + fprintf(stderr, " start %u, match %d, length %d\n", + start, (int)match, length); do { - fprintf(stderr, "%c%c", s->window[match++], s->window[start++]); - } while (--length != 0); + fprintf(stderr, "(%02x %02x)", *back++, *here++); + } while (--len != 0); z_error("invalid match"); } if (z_verbose > 1) { @@ -1515,137 +1583,6 @@ local void check_match(s, start, match, length) #endif /* ZLIB_DEBUG */ /* =========================================================================== - * Fill the window when the lookahead becomes insufficient. - * Updates strstart and lookahead. - * - * IN assertion: lookahead < MIN_LOOKAHEAD - * OUT assertions: strstart <= window_size-MIN_LOOKAHEAD - * At least one byte has been read, or avail_in == 0; reads are - * performed for at least two bytes (required for the zip translate_eol - * option -- not supported here). - */ -local void fill_window(s) - deflate_state *s; -{ - unsigned n; - unsigned more; /* Amount of free space at the end of the window. */ - uInt wsize = s->w_size; - - Assert(s->lookahead < MIN_LOOKAHEAD, "already enough lookahead"); - - do { - more = (unsigned)(s->window_size -(ulg)s->lookahead -(ulg)s->strstart); - - /* Deal with !@#$% 64K limit: */ - if (sizeof(int) <= 2) { - if (more == 0 && s->strstart == 0 && s->lookahead == 0) { - more = wsize; - - } else if (more == (unsigned)(-1)) { - /* Very unlikely, but possible on 16 bit machine if - * strstart == 0 && lookahead == 1 (input done a byte at time) - */ - more--; - } - } - - /* If the window is almost full and there is insufficient lookahead, - * move the upper half to the lower one to make room in the upper half. - */ - if (s->strstart >= wsize + MAX_DIST(s)) { - - zmemcpy(s->window, s->window + wsize, (unsigned)wsize - more); - s->match_start -= wsize; - s->strstart -= wsize; /* we now have strstart >= MAX_DIST */ - s->block_start -= (long) wsize; - if (s->insert > s->strstart) - s->insert = s->strstart; - slide_hash(s); - more += wsize; - } - if (s->strm->avail_in == 0) break; - - /* If there was no sliding: - * strstart <= WSIZE+MAX_DIST-1 && lookahead <= MIN_LOOKAHEAD - 1 && - * more == window_size - lookahead - strstart - * => more >= window_size - (MIN_LOOKAHEAD-1 + WSIZE + MAX_DIST-1) - * => more >= window_size - 2*WSIZE + 2 - * In the BIG_MEM or MMAP case (not yet supported), - * window_size == input_size + MIN_LOOKAHEAD && - * strstart + s->lookahead <= input_size => more >= MIN_LOOKAHEAD. - * Otherwise, window_size == 2*WSIZE so more >= 2. - * If there was sliding, more >= WSIZE. So in all cases, more >= 2. - */ - Assert(more >= 2, "more < 2"); - - n = read_buf(s->strm, s->window + s->strstart + s->lookahead, more); - s->lookahead += n; - - /* Initialize the hash value now that we have some input: */ - if (s->lookahead + s->insert >= MIN_MATCH) { - uInt str = s->strstart - s->insert; - s->ins_h = s->window[str]; - UPDATE_HASH(s, s->ins_h, s->window[str + 1]); -#if MIN_MATCH != 3 - Call UPDATE_HASH() MIN_MATCH-3 more times -#endif - while (s->insert) { - UPDATE_HASH(s, s->ins_h, s->window[str + MIN_MATCH-1]); -#ifndef FASTEST - s->prev[str & s->w_mask] = s->head[s->ins_h]; -#endif - s->head[s->ins_h] = (Pos)str; - str++; - s->insert--; - if (s->lookahead + s->insert < MIN_MATCH) - break; - } - } - /* If the whole input has less than MIN_MATCH bytes, ins_h is garbage, - * but this is not important since only literal bytes will be emitted. - */ - - } while (s->lookahead < MIN_LOOKAHEAD && s->strm->avail_in != 0); - - /* If the WIN_INIT bytes after the end of the current data have never been - * written, then zero those bytes in order to avoid memory check reports of - * the use of uninitialized (or uninitialised as Julian writes) bytes by - * the longest match routines. Update the high water mark for the next - * time through here. WIN_INIT is set to MAX_MATCH since the longest match - * routines allow scanning to strstart + MAX_MATCH, ignoring lookahead. - */ - if (s->high_water < s->window_size) { - ulg curr = s->strstart + (ulg)(s->lookahead); - ulg init; - - if (s->high_water < curr) { - /* Previous high water mark below current data -- zero WIN_INIT - * bytes or up to end of window, whichever is less. - */ - init = s->window_size - curr; - if (init > WIN_INIT) - init = WIN_INIT; - zmemzero(s->window + curr, (unsigned)init); - s->high_water = curr + init; - } - else if (s->high_water < (ulg)curr + WIN_INIT) { - /* High water mark at or above current data, but below current data - * plus WIN_INIT -- zero out to current data plus WIN_INIT, or up - * to end of window, whichever is less. - */ - init = (ulg)curr + WIN_INIT - s->high_water; - if (init > s->window_size - s->high_water) - init = s->window_size - s->high_water; - zmemzero(s->window + s->high_water, (unsigned)init); - s->high_water += init; - } - } - - Assert((ulg)s->strstart <= s->window_size - MIN_LOOKAHEAD, - "not enough room for search"); -} - -/* =========================================================================== * Flush the current block, with given end-of-file flag. * IN assertion: strstart is set to the end of the current match. */ @@ -1687,10 +1624,7 @@ local void fill_window(s) * copied. It is most efficient with large input and output buffers, which * maximizes the opportunities to have a single copy from next_in to next_out. */ -local block_state deflate_stored(s, flush) - deflate_state *s; - int flush; -{ +local block_state deflate_stored(deflate_state *s, int flush) { /* Smallest worthy block size when not flushing or finishing. By default * this is 32K. This can be as small as 507 bytes for memLevel == 1. For * large input and output buffers, the stored block size will be larger. @@ -1874,10 +1808,7 @@ local block_state deflate_stored(s, flush) * new strings in the dictionary only for unmatched strings or for short * matches. It is used only for the fast compression options. */ -local block_state deflate_fast(s, flush) - deflate_state *s; - int flush; -{ +local block_state deflate_fast(deflate_state *s, int flush) { IPos hash_head; /* head of the hash chain */ int bflush; /* set if current block must be flushed */ @@ -1976,10 +1907,7 @@ local block_state deflate_fast(s, flush) * evaluation for matches: a match is finally adopted only if there is * no better match at the next window position. */ -local block_state deflate_slow(s, flush) - deflate_state *s; - int flush; -{ +local block_state deflate_slow(deflate_state *s, int flush) { IPos hash_head; /* head of hash chain */ int bflush; /* set if current block must be flushed */ @@ -2107,10 +2035,7 @@ local block_state deflate_slow(s, flush) * one. Do not maintain a hash table. (It will be regenerated if this run of * deflate switches away from Z_RLE.) */ -local block_state deflate_rle(s, flush) - deflate_state *s; - int flush; -{ +local block_state deflate_rle(deflate_state *s, int flush) { int bflush; /* set if current block must be flushed */ uInt prev; /* byte at distance one to match */ Bytef *scan, *strend; /* scan goes up to strend for length of run */ @@ -2181,10 +2106,7 @@ local block_state deflate_rle(s, flush) * For Z_HUFFMAN_ONLY, do not look for matches. Do not maintain a hash table. * (It will be regenerated if this run of deflate switches away from Huffman.) */ -local block_state deflate_huff(s, flush) - deflate_state *s; - int flush; -{ +local block_state deflate_huff(deflate_state *s, int flush) { int bflush; /* set if current block must be flushed */ for (;;) { |