X-Git-Url: https://mattmccutchen.net/rsync/rsync.git/blobdiff_plain/5914bf15d2bb62003de56cea1d95f62b5830618a..93465f51bcc2484a1bdf0f94ed3b812fa5c39576:/zlib/deflate.c diff --git a/zlib/deflate.c b/zlib/deflate.c index 95b84d0d..fd8db9e5 100644 --- a/zlib/deflate.c +++ b/zlib/deflate.c @@ -1,6 +1,6 @@ /* deflate.c -- compress data using the deflation algorithm - * Copyright (C) 1995-1998 Jean-loup Gailly. - * For conditions of distribution and use, see copyright notice in zlib.h + * Copyright (C) 1995-2005 Jean-loup Gailly. + * For conditions of distribution and use, see copyright notice in zlib.h */ /* @@ -37,7 +37,7 @@ * REFERENCES * * Deutsch, L.P.,"DEFLATE Compressed Data Format Specification". - * Available in ftp://ds.internic.net/rfc/rfc1951.txt + * Available in http://www.ietf.org/rfc/rfc1951.txt * * A description of the Rabin and Karp algorithm is given in the book * "Algorithms" by R. Sedgewick, Addison-Wesley, p252. @@ -51,8 +51,10 @@ #include "deflate.h" +#define read_buf dread_buf + const char deflate_copyright[] = - " deflate 1.1.2 Copyright 1995-1998 Jean-loup Gailly "; + " deflate 1.2.3 Copyright 1995-2005 Jean-loup Gailly "; /* 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 @@ -76,17 +78,22 @@ typedef block_state (*compress_func) OF((deflate_state *s, int flush)); 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)); +#ifndef FASTEST local block_state deflate_slow OF((deflate_state *s, int flush)); +#endif 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 int dread_buf OF((z_streamp strm, Bytef *buf, unsigned size)); +local int read_buf OF((z_streamp strm, Bytef *buf, unsigned size)); +#ifndef FASTEST #ifdef ASMV void match_init OF((void)); /* asm code initialization */ uInt longest_match OF((deflate_state *s, IPos cur_match)); #else local uInt longest_match OF((deflate_state *s, IPos cur_match)); #endif +#endif +local uInt longest_match_fast OF((deflate_state *s, IPos cur_match)); #ifdef DEBUG local void check_match OF((deflate_state *s, IPos start, IPos match, @@ -123,10 +130,16 @@ typedef struct config_s { compress_func func; } config; +#ifdef FASTEST +local const config configuration_table[2] = { +/* good lazy nice chain */ +/* 0 */ {0, 0, 0, 0, deflate_stored}, /* store only */ +/* 1 */ {4, 4, 8, 4, deflate_fast}}; /* max speed, no lazy matches */ +#else local const config configuration_table[10] = { /* good lazy nice chain */ /* 0 */ {0, 0, 0, 0, deflate_stored}, /* store only */ -/* 1 */ {4, 4, 8, 4, deflate_fast}, /* maximum speed, no lazy matches */ +/* 1 */ {4, 4, 8, 4, deflate_fast}, /* max speed, no lazy matches */ /* 2 */ {4, 5, 16, 8, deflate_fast}, /* 3 */ {4, 6, 32, 32, deflate_fast}, @@ -135,7 +148,8 @@ local const config configuration_table[10] = { /* 6 */ {8, 16, 128, 128, deflate_slow}, /* 7 */ {8, 32, 128, 256, deflate_slow}, /* 8 */ {32, 128, 258, 1024, deflate_slow}, -/* 9 */ {32, 258, 258, 4096, deflate_slow}}; /* maximum compression */ +/* 9 */ {32, 258, 258, 4096, deflate_slow}}; /* max compression */ +#endif /* Note: the deflate() code requires max_lazy >= MIN_MATCH and max_chain >= 4 * For deflate_fast() (levels <= 3) good is ignored and lazy has a different @@ -145,7 +159,9 @@ local const config configuration_table[10] = { #define EQUAL 0 /* result of memcmp for equal strings */ +#ifndef NO_DUMMY_DECL struct static_tree_desc_s {int dummy;}; /* for buggy compilers */ +#endif /* =========================================================================== * Update a hash value with the given input byte @@ -174,7 +190,7 @@ struct static_tree_desc_s {int dummy;}; /* for buggy compilers */ #else #define INSERT_STRING(s, str, match_head) \ (UPDATE_HASH(s, s->ins_h, s->window[(str) + (MIN_MATCH-1)]), \ - s->prev[(str) & s->w_mask] = match_head = s->head[s->ins_h], \ + match_head = s->prev[(str) & s->w_mask] = s->head[s->ins_h], \ s->head[s->ins_h] = (Pos)(str)) #endif @@ -194,13 +210,13 @@ int ZEXPORT deflateInit_(strm, level, version, stream_size) int stream_size; { return deflateInit2_(strm, level, Z_DEFLATED, MAX_WBITS, DEF_MEM_LEVEL, - Z_DEFAULT_STRATEGY, version, stream_size); + 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) + version, stream_size) z_streamp strm; int level; int method; @@ -211,8 +227,8 @@ int ZEXPORT deflateInit2_(strm, level, method, windowBits, memLevel, strategy, int stream_size; { deflate_state *s; - int noheader = 0; - static const char* my_version = ZLIB_VERSION; + int wrap = 1; + static const char my_version[] = ZLIB_VERSION; ushf *overlay; /* We overlay pending_buf and d_buf+l_buf. This works since the average @@ -221,37 +237,46 @@ int ZEXPORT deflateInit2_(strm, level, method, windowBits, memLevel, strategy, if (version == Z_NULL || version[0] != my_version[0] || stream_size != sizeof(z_stream)) { - return Z_VERSION_ERROR; + return Z_VERSION_ERROR; } if (strm == Z_NULL) return Z_STREAM_ERROR; strm->msg = Z_NULL; - if (strm->zalloc == Z_NULL) { - strm->zalloc = zcalloc; - strm->opaque = (voidpf)0; + if (strm->zalloc == (alloc_func)0) { + strm->zalloc = zcalloc; + strm->opaque = (voidpf)0; } - if (strm->zfree == Z_NULL) strm->zfree = zcfree; + if (strm->zfree == (free_func)0) strm->zfree = zcfree; - if (level == Z_DEFAULT_COMPRESSION) level = 6; #ifdef FASTEST - level = 1; + if (level != 0) level = 1; +#else + if (level == Z_DEFAULT_COMPRESSION) level = 6; #endif - if (windowBits < 0) { /* undocumented feature: suppress zlib header */ - noheader = 1; + if (windowBits < 0) { /* suppress zlib wrapper */ + wrap = 0; windowBits = -windowBits; } +#ifdef GZIP + else if (windowBits > 15) { + wrap = 2; /* write gzip wrapper instead */ + windowBits -= 16; + } +#endif if (memLevel < 1 || memLevel > MAX_MEM_LEVEL || method != Z_DEFLATED || windowBits < 8 || windowBits > 15 || level < 0 || level > 9 || - strategy < 0 || strategy > Z_HUFFMAN_ONLY) { + strategy < 0 || strategy > Z_FIXED) { return Z_STREAM_ERROR; } + if (windowBits == 8) windowBits = 9; /* until 256-byte window bug fixed */ s = (deflate_state *) ZALLOC(strm, 1, sizeof(deflate_state)); if (s == Z_NULL) return Z_MEM_ERROR; strm->state = (struct internal_state FAR *)s; s->strm = strm; - s->noheader = noheader; + s->wrap = wrap; + s->gzhead = Z_NULL; s->w_bits = windowBits; s->w_size = 1 << s->w_bits; s->w_mask = s->w_size - 1; @@ -273,6 +298,7 @@ int ZEXPORT deflateInit2_(strm, level, method, windowBits, memLevel, strategy, if (s->window == Z_NULL || s->prev == Z_NULL || s->head == Z_NULL || s->pending_buf == Z_NULL) { + s->status = FINISH_STATE; strm->msg = (char*)ERR_MSG(Z_MEM_ERROR); deflateEnd (strm); return Z_MEM_ERROR; @@ -299,17 +325,18 @@ int ZEXPORT deflateSetDictionary (strm, dictionary, dictLength) IPos hash_head = 0; if (strm == Z_NULL || strm->state == Z_NULL || dictionary == Z_NULL || - strm->state->status != INIT_STATE) return Z_STREAM_ERROR; + strm->state->wrap == 2 || + (strm->state->wrap == 1 && strm->state->status != INIT_STATE)) + return Z_STREAM_ERROR; s = strm->state; - strm->adler = adler32(strm->adler, dictionary, dictLength); + if (s->wrap) + strm->adler = adler32(strm->adler, dictionary, dictLength); if (length < MIN_MATCH) return Z_OK; if (length > MAX_DIST(s)) { - length = MAX_DIST(s); -#ifndef USE_DICT_HEAD - dictionary += dictLength - length; /* use the tail of the dictionary */ -#endif + length = MAX_DIST(s); + dictionary += dictLength - length; /* use the tail of the dictionary */ } zmemcpy(s->window, dictionary, length); s->strstart = length; @@ -322,7 +349,7 @@ int ZEXPORT deflateSetDictionary (strm, dictionary, dictLength) s->ins_h = s->window[0]; UPDATE_HASH(s, s->ins_h, s->window[1]); for (n = 0; n <= length - MIN_MATCH; n++) { - INSERT_STRING(s, n, hash_head); + INSERT_STRING(s, n, hash_head); } if (hash_head) hash_head = 0; /* to make compiler happy */ return Z_OK; @@ -333,9 +360,11 @@ int ZEXPORT deflateReset (strm) z_streamp strm; { deflate_state *s; - + if (strm == Z_NULL || strm->state == Z_NULL || - strm->zalloc == Z_NULL || strm->zfree == Z_NULL) return Z_STREAM_ERROR; + strm->zalloc == (alloc_func)0 || strm->zfree == (free_func)0) { + return Z_STREAM_ERROR; + } strm->total_in = strm->total_out = 0; strm->msg = Z_NULL; /* use zfree if we ever allocate msg dynamically */ @@ -345,11 +374,15 @@ int ZEXPORT deflateReset (strm) s->pending = 0; s->pending_out = s->pending_buf; - if (s->noheader < 0) { - s->noheader = 0; /* was set to -1 by deflate(..., Z_FINISH); */ + if (s->wrap < 0) { + s->wrap = -s->wrap; /* was made negative by deflate(..., Z_FINISH); */ } - s->status = s->noheader ? BUSY_STATE : INIT_STATE; - strm->adler = 1; + s->status = s->wrap ? INIT_STATE : BUSY_STATE; + strm->adler = +#ifdef GZIP + s->wrap == 2 ? crc32(0L, Z_NULL, 0) : +#endif + adler32(0L, Z_NULL, 0); s->last_flush = Z_NO_FLUSH; _tr_init(s); @@ -358,6 +391,29 @@ int ZEXPORT deflateReset (strm) return Z_OK; } +/* ========================================================================= */ +int ZEXPORT deflateSetHeader (strm, head) + z_streamp strm; + gz_headerp head; +{ + if (strm == Z_NULL || strm->state == Z_NULL) return Z_STREAM_ERROR; + if (strm->state->wrap != 2) return Z_STREAM_ERROR; + strm->state->gzhead = head; + return Z_OK; +} + +/* ========================================================================= */ +int ZEXPORT deflatePrime (strm, bits, value) + z_streamp strm; + int bits; + int value; +{ + if (strm == Z_NULL || strm->state == Z_NULL) return Z_STREAM_ERROR; + strm->state->bi_valid = bits; + strm->state->bi_buf = (ush)(value & ((1 << bits) - 1)); + return Z_OK; +} + /* ========================================================================= */ int ZEXPORT deflateParams(strm, level, strategy) z_streamp strm; @@ -371,29 +427,91 @@ int ZEXPORT deflateParams(strm, level, strategy) if (strm == Z_NULL || strm->state == Z_NULL) return Z_STREAM_ERROR; s = strm->state; - if (level == Z_DEFAULT_COMPRESSION) { - level = 6; - } - if (level < 0 || level > 9 || strategy < 0 || strategy > Z_HUFFMAN_ONLY) { - return Z_STREAM_ERROR; +#ifdef FASTEST + if (level != 0) level = 1; +#else + if (level == Z_DEFAULT_COMPRESSION) level = 6; +#endif + if (level < 0 || level > 9 || strategy < 0 || strategy > Z_FIXED) { + return Z_STREAM_ERROR; } func = configuration_table[s->level].func; if (func != configuration_table[level].func && strm->total_in != 0) { - /* Flush the last buffer: */ - err = deflate(strm, Z_PARTIAL_FLUSH); + /* Flush the last buffer: */ + err = deflate(strm, Z_PARTIAL_FLUSH); } if (s->level != level) { - s->level = level; - s->max_lazy_match = configuration_table[level].max_lazy; - s->good_match = configuration_table[level].good_length; - s->nice_match = configuration_table[level].nice_length; - s->max_chain_length = configuration_table[level].max_chain; + s->level = level; + s->max_lazy_match = configuration_table[level].max_lazy; + s->good_match = configuration_table[level].good_length; + s->nice_match = configuration_table[level].nice_length; + s->max_chain_length = configuration_table[level].max_chain; } s->strategy = strategy; return err; } +/* ========================================================================= */ +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; +{ + deflate_state *s; + + if (strm == Z_NULL || strm->state == Z_NULL) return Z_STREAM_ERROR; + s = strm->state; + s->good_match = good_length; + s->max_lazy_match = max_lazy; + s->nice_match = nice_length; + s->max_chain_length = max_chain; + return Z_OK; +} + +/* ========================================================================= + * For the default windowBits of 15 and memLevel of 8, this function returns + * a close to exact, as well as small, upper bound on the compressed size. + * They are coded as constants here for a reason--if the #define's are + * changed, then this function needs to be changed as well. The return + * value for 15 and 8 only works for those exact settings. + * + * For any setting other than those defaults for windowBits and memLevel, + * the value returned is a conservative worst case for the maximum expansion + * resulting from using fixed blocks instead of stored blocks, which deflate + * can emit on compressed data for some combinations of the parameters. + * + * This function could be more sophisticated to provide closer upper bounds + * for every combination of windowBits and memLevel, as well as wrap. + * But even the conservative upper bound of about 14% expansion does not + * seem onerous for output buffer allocation. + */ +uLong ZEXPORT deflateBound(strm, sourceLen) + z_streamp strm; + uLong sourceLen; +{ + deflate_state *s; + uLong destLen; + + /* conservative upper bound */ + destLen = sourceLen + + ((sourceLen + 7) >> 3) + ((sourceLen + 63) >> 6) + 11; + + /* if can't get parameters, return conservative bound */ + if (strm == Z_NULL || strm->state == Z_NULL) + return destLen; + + /* if not default parameters, return conservative bound */ + s = strm->state; + if (s->w_bits != 15 || s->hash_bits != 8 + 7) + return destLen; + + /* default settings: return tight bound for that case */ + return compressBound(sourceLen); +} + /* ========================================================================= * Put a short in the pending buffer. The 16-bit value is put in MSB order. * IN assertion: the stream state is correct and there is enough room in @@ -405,13 +523,13 @@ local void putShortMSB (s, b) { put_byte(s, (Byte)(b >> 8)); put_byte(s, (Byte)(b & 0xff)); -} +} /* ========================================================================= * Flush as much pending output as possible. All deflate() output goes * through this function so some applications may wish to modify it * to avoid allocating a large strm->next_out buffer and copying into it. - * (See also dread_buf()). + * (See also read_buf()). */ local void flush_pending(strm) z_streamp strm; @@ -441,14 +559,14 @@ int ZEXPORT deflate (strm, flush) deflate_state *s; if (strm == Z_NULL || strm->state == Z_NULL || - flush > Z_INSERT_ONLY || flush < 0) { + flush > Z_INSERT_ONLY || flush < 0) { return Z_STREAM_ERROR; } s = strm->state; if (strm->next_out == Z_NULL || (strm->next_in == Z_NULL && strm->avail_in != 0) || - (s->status == FINISH_STATE && flush != Z_FINISH)) { + (s->status == FINISH_STATE && flush != Z_FINISH)) { ERR_RETURN(strm, Z_STREAM_ERROR); } if (strm->avail_out == 0) ERR_RETURN(strm, Z_BUF_ERROR); @@ -457,48 +575,206 @@ int ZEXPORT deflate (strm, flush) old_flush = s->last_flush; s->last_flush = flush; - /* Write the zlib header */ + /* Write the header */ if (s->status == INIT_STATE) { +#ifdef GZIP + if (s->wrap == 2) { + strm->adler = crc32(0L, Z_NULL, 0); + put_byte(s, 31); + put_byte(s, 139); + put_byte(s, 8); + if (s->gzhead == NULL) { + put_byte(s, 0); + put_byte(s, 0); + put_byte(s, 0); + put_byte(s, 0); + put_byte(s, 0); + put_byte(s, s->level == 9 ? 2 : + (s->strategy >= Z_HUFFMAN_ONLY || s->level < 2 ? + 4 : 0)); + put_byte(s, OS_CODE); + s->status = BUSY_STATE; + } + else { + put_byte(s, (s->gzhead->text ? 1 : 0) + + (s->gzhead->hcrc ? 2 : 0) + + (s->gzhead->extra == Z_NULL ? 0 : 4) + + (s->gzhead->name == Z_NULL ? 0 : 8) + + (s->gzhead->comment == Z_NULL ? 0 : 16) + ); + put_byte(s, (Byte)(s->gzhead->time & 0xff)); + put_byte(s, (Byte)((s->gzhead->time >> 8) & 0xff)); + put_byte(s, (Byte)((s->gzhead->time >> 16) & 0xff)); + put_byte(s, (Byte)((s->gzhead->time >> 24) & 0xff)); + put_byte(s, s->level == 9 ? 2 : + (s->strategy >= Z_HUFFMAN_ONLY || s->level < 2 ? + 4 : 0)); + put_byte(s, s->gzhead->os & 0xff); + if (s->gzhead->extra != NULL) { + put_byte(s, s->gzhead->extra_len & 0xff); + put_byte(s, (s->gzhead->extra_len >> 8) & 0xff); + } + if (s->gzhead->hcrc) + strm->adler = crc32(strm->adler, s->pending_buf, + s->pending); + s->gzindex = 0; + s->status = EXTRA_STATE; + } + } + else +#endif + { + uInt header = (Z_DEFLATED + ((s->w_bits-8)<<4)) << 8; + uInt level_flags; + + if (s->strategy >= Z_HUFFMAN_ONLY || s->level < 2) + level_flags = 0; + else if (s->level < 6) + level_flags = 1; + else if (s->level == 6) + level_flags = 2; + else + level_flags = 3; + header |= (level_flags << 6); + if (s->strstart != 0) header |= PRESET_DICT; + header += 31 - (header % 31); + + s->status = BUSY_STATE; + putShortMSB(s, header); + + /* Save the adler32 of the preset dictionary: */ + if (s->strstart != 0) { + putShortMSB(s, (uInt)(strm->adler >> 16)); + putShortMSB(s, (uInt)(strm->adler & 0xffff)); + } + strm->adler = adler32(0L, Z_NULL, 0); + } + } +#ifdef GZIP + if (s->status == EXTRA_STATE) { + if (s->gzhead->extra != NULL) { + uInt beg = s->pending; /* start of bytes to update crc */ + + while (s->gzindex < (s->gzhead->extra_len & 0xffff)) { + if (s->pending == s->pending_buf_size) { + if (s->gzhead->hcrc && s->pending > beg) + strm->adler = crc32(strm->adler, s->pending_buf + beg, + s->pending - beg); + flush_pending(strm); + beg = s->pending; + if (s->pending == s->pending_buf_size) + break; + } + put_byte(s, s->gzhead->extra[s->gzindex]); + s->gzindex++; + } + if (s->gzhead->hcrc && s->pending > beg) + strm->adler = crc32(strm->adler, s->pending_buf + beg, + s->pending - beg); + if (s->gzindex == s->gzhead->extra_len) { + s->gzindex = 0; + s->status = NAME_STATE; + } + } + else + s->status = NAME_STATE; + } + if (s->status == NAME_STATE) { + if (s->gzhead->name != NULL) { + uInt beg = s->pending; /* start of bytes to update crc */ + int val; - uInt header = (Z_DEFLATED + ((s->w_bits-8)<<4)) << 8; - uInt level_flags = (s->level-1) >> 1; - - if (level_flags > 3) level_flags = 3; - header |= (level_flags << 6); - if (s->strstart != 0) header |= PRESET_DICT; - header += 31 - (header % 31); - - s->status = BUSY_STATE; - putShortMSB(s, header); + do { + if (s->pending == s->pending_buf_size) { + if (s->gzhead->hcrc && s->pending > beg) + strm->adler = crc32(strm->adler, s->pending_buf + beg, + s->pending - beg); + flush_pending(strm); + beg = s->pending; + if (s->pending == s->pending_buf_size) { + val = 1; + break; + } + } + val = s->gzhead->name[s->gzindex++]; + put_byte(s, val); + } while (val != 0); + if (s->gzhead->hcrc && s->pending > beg) + strm->adler = crc32(strm->adler, s->pending_buf + beg, + s->pending - beg); + if (val == 0) { + s->gzindex = 0; + s->status = COMMENT_STATE; + } + } + else + s->status = COMMENT_STATE; + } + if (s->status == COMMENT_STATE) { + if (s->gzhead->comment != NULL) { + uInt beg = s->pending; /* start of bytes to update crc */ + int val; - /* Save the adler32 of the preset dictionary: */ - if (s->strstart != 0) { - putShortMSB(s, (uInt)(strm->adler >> 16)); - putShortMSB(s, (uInt)(strm->adler & 0xffff)); - } - strm->adler = 1L; + do { + if (s->pending == s->pending_buf_size) { + if (s->gzhead->hcrc && s->pending > beg) + strm->adler = crc32(strm->adler, s->pending_buf + beg, + s->pending - beg); + flush_pending(strm); + beg = s->pending; + if (s->pending == s->pending_buf_size) { + val = 1; + break; + } + } + val = s->gzhead->comment[s->gzindex++]; + put_byte(s, val); + } while (val != 0); + if (s->gzhead->hcrc && s->pending > beg) + strm->adler = crc32(strm->adler, s->pending_buf + beg, + s->pending - beg); + if (val == 0) + s->status = HCRC_STATE; + } + else + s->status = HCRC_STATE; + } + if (s->status == HCRC_STATE) { + if (s->gzhead->hcrc) { + if (s->pending + 2 > s->pending_buf_size) + flush_pending(strm); + if (s->pending + 2 <= s->pending_buf_size) { + put_byte(s, (Byte)(strm->adler & 0xff)); + put_byte(s, (Byte)((strm->adler >> 8) & 0xff)); + strm->adler = crc32(0L, Z_NULL, 0); + s->status = BUSY_STATE; + } + } + else + s->status = BUSY_STATE; } +#endif /* Flush as much pending output as possible */ if (s->pending != 0) { flush_pending(strm); if (strm->avail_out == 0) { - /* Since avail_out is 0, deflate will be called again with - * more output space, but possibly with both pending and - * avail_in equal to zero. There won't be anything to do, - * but this is not an error situation so make sure we - * return OK instead of BUF_ERROR at next call of deflate: + /* Since avail_out is 0, deflate will be called again with + * more output space, but possibly with both pending and + * avail_in equal to zero. There won't be anything to do, + * but this is not an error situation so make sure we + * return OK instead of BUF_ERROR at next call of deflate: */ - s->last_flush = -1; - return Z_OK; - } + s->last_flush = -1; + return Z_OK; + } /* Make sure there is something to do and avoid duplicate consecutive * flushes. For repeated and useless calls with Z_FINISH, we keep - * returning Z_STREAM_END instead of Z_BUFF_ERROR. + * returning Z_STREAM_END instead of Z_BUF_ERROR. */ } else if (strm->avail_in == 0 && flush <= old_flush && - flush != Z_FINISH) { + flush != Z_FINISH) { ERR_RETURN(strm, Z_BUF_ERROR); } @@ -513,24 +789,24 @@ int ZEXPORT deflate (strm, flush) (flush != Z_NO_FLUSH && s->status != FINISH_STATE)) { block_state bstate; - bstate = (*(configuration_table[s->level].func))(s, flush); + bstate = (*(configuration_table[s->level].func))(s, flush); if (bstate == finish_started || bstate == finish_done) { s->status = FINISH_STATE; } if (bstate == need_more || bstate == finish_started) { - if (strm->avail_out == 0) { - s->last_flush = -1; /* avoid BUF_ERROR next call, see above */ - } - return Z_OK; - /* If flush != Z_NO_FLUSH && avail_out == 0, the next call - * of deflate should use the same flush parameter to make sure - * that the flush is complete. So we don't have to output an - * empty block here, this will be done at next call. This also - * ensures that for a very small output buffer, we emit at most - * one empty block. - */ - } + if (strm->avail_out == 0) { + s->last_flush = -1; /* avoid BUF_ERROR next call, see above */ + } + return Z_OK; + /* If flush != Z_NO_FLUSH && avail_out == 0, the next call + * of deflate should use the same flush parameter to make sure + * that the flush is complete. So we don't have to output an + * empty block here, this will be done at next call. This also + * ensures that for a very small output buffer, we emit at most + * one empty block. + */ + } if (bstate == block_done) { if (flush == Z_PARTIAL_FLUSH) { _tr_align(s); @@ -544,25 +820,40 @@ int ZEXPORT deflate (strm, flush) } } flush_pending(strm); - if (strm->avail_out == 0) { - s->last_flush = -1; /* avoid BUF_ERROR at next call, see above */ - return Z_OK; - } + if (strm->avail_out == 0) { + s->last_flush = -1; /* avoid BUF_ERROR at next call, see above */ + return Z_OK; + } } } Assert(strm->avail_out > 0, "bug2"); if (flush != Z_FINISH) return Z_OK; - if (s->noheader) return Z_STREAM_END; - - /* Write the zlib trailer (adler32) */ - putShortMSB(s, (uInt)(strm->adler >> 16)); - putShortMSB(s, (uInt)(strm->adler & 0xffff)); + if (s->wrap <= 0) return Z_STREAM_END; + + /* Write the trailer */ +#ifdef GZIP + if (s->wrap == 2) { + put_byte(s, (Byte)(strm->adler & 0xff)); + put_byte(s, (Byte)((strm->adler >> 8) & 0xff)); + put_byte(s, (Byte)((strm->adler >> 16) & 0xff)); + put_byte(s, (Byte)((strm->adler >> 24) & 0xff)); + put_byte(s, (Byte)(strm->total_in & 0xff)); + put_byte(s, (Byte)((strm->total_in >> 8) & 0xff)); + put_byte(s, (Byte)((strm->total_in >> 16) & 0xff)); + put_byte(s, (Byte)((strm->total_in >> 24) & 0xff)); + } + else +#endif + { + putShortMSB(s, (uInt)(strm->adler >> 16)); + putShortMSB(s, (uInt)(strm->adler & 0xffff)); + } flush_pending(strm); /* If avail_out is zero, the application will call deflate again * to flush the rest. */ - s->noheader = -1; /* write the trailer only once! */ + if (s->wrap > 0) s->wrap = -s->wrap; /* write the trailer only once! */ return s->pending != 0 ? Z_OK : Z_STREAM_END; } @@ -575,8 +866,13 @@ int ZEXPORT deflateEnd (strm) if (strm == Z_NULL || strm->state == Z_NULL) return Z_STREAM_ERROR; status = strm->state->status; - if (status != INIT_STATE && status != BUSY_STATE && - status != FINISH_STATE) { + if (status != INIT_STATE && + status != EXTRA_STATE && + status != NAME_STATE && + status != COMMENT_STATE && + status != HCRC_STATE && + status != BUSY_STATE && + status != FINISH_STATE) { return Z_STREAM_ERROR; } @@ -608,17 +904,19 @@ int ZEXPORT deflateCopy (dest, source) deflate_state *ss; ushf *overlay; - ss = source->state; - if (source == Z_NULL || dest == Z_NULL || ss == Z_NULL) { + if (source == Z_NULL || dest == Z_NULL || source->state == Z_NULL) { return Z_STREAM_ERROR; } - *dest = *source; + + ss = source->state; + + zmemcpy(dest, source, sizeof(z_stream)); ds = (deflate_state *) ZALLOC(dest, 1, sizeof(deflate_state)); if (ds == Z_NULL) return Z_MEM_ERROR; dest->state = (struct internal_state FAR *) ds; - *ds = *ss; + zmemcpy(ds, ss, sizeof(deflate_state)); ds->strm = dest; ds->window = (Bytef *) ZALLOC(dest, ds->w_size, 2*sizeof(Byte)); @@ -647,7 +945,7 @@ int ZEXPORT deflateCopy (dest, source) ds->bl_desc.dyn_tree = ds->bl_tree; return Z_OK; -#endif +#endif /* MAXSEG_64K */ } /* =========================================================================== @@ -657,7 +955,7 @@ int ZEXPORT deflateCopy (dest, source) * allocating a large strm->next_in buffer and copying from it. * (See also flush_pending()). */ -local int dread_buf(strm, buf, size) +local int read_buf(strm, buf, size) z_streamp strm; Bytef *buf; unsigned size; @@ -669,9 +967,14 @@ local int dread_buf(strm, buf, size) strm->avail_in -= len; - if (!strm->state->noheader) { + if (strm->state->wrap == 1) { strm->adler = adler32(strm->adler, strm->next_in, len); } +#ifdef GZIP + else if (strm->state->wrap == 2) { + strm->adler = crc32(strm->adler, strm->next_in, len); + } +#endif zmemcpy(buf, strm->next_in, len); strm->next_in += len; strm->total_in += len; @@ -702,11 +1005,14 @@ local void lm_init (s) s->match_length = s->prev_length = MIN_MATCH-1; s->match_available = 0; s->ins_h = 0; +#ifndef FASTEST #ifdef ASMV match_init(); /* initialize the asm code */ #endif +#endif } +#ifndef FASTEST /* =========================================================================== * Set match_start to the longest match starting at the given string and * return its length. Matches shorter or equal to prev_length are discarded, @@ -720,7 +1026,6 @@ local void lm_init (s) /* For 80x86 and 680x0, an optimized version will be provided in match.asm or * match.S. The code will be functionally equivalent. */ -#ifndef FASTEST local uInt longest_match(s, cur_match) deflate_state *s; IPos cur_match; /* current match */ @@ -773,7 +1078,12 @@ local uInt longest_match(s, cur_match) match = s->window + cur_match; /* Skip to next match if the match length cannot increase - * or if the match length is less than 2: + * or if the match length is less than 2. Note that the checks below + * for insufficient lookahead only occur occasionally for performance + * reasons. Therefore uninitialized memory will be accessed, and + * conditional jumps will be made that depend on those values. + * However the length of the match is limited to the lookahead, so + * the output of deflate is not affected by the uninitialized values. */ #if (defined(UNALIGNED_OK) && MAX_MATCH == 258) /* This code assumes sizeof(unsigned short) == 2. Do not use @@ -858,12 +1168,13 @@ local uInt longest_match(s, cur_match) if ((uInt)best_len <= s->lookahead) return (uInt)best_len; return s->lookahead; } +#endif /* ASMV */ +#endif /* FASTEST */ -#else /* FASTEST */ /* --------------------------------------------------------------------------- - * Optimized version for level == 1 only + * Optimized version for level == 1 or strategy == Z_RLE only */ -local uInt longest_match(s, cur_match) +local uInt longest_match_fast(s, cur_match) deflate_state *s; IPos cur_match; /* current match */ { @@ -901,10 +1212,10 @@ local uInt longest_match(s, cur_match) */ do { } while (*++scan == *++match && *++scan == *++match && - *++scan == *++match && *++scan == *++match && - *++scan == *++match && *++scan == *++match && - *++scan == *++match && *++scan == *++match && - scan < strend); + *++scan == *++match && *++scan == *++match && + *++scan == *++match && *++scan == *++match && + *++scan == *++match && *++scan == *++match && + scan < strend); Assert(scan <= s->window+(unsigned)(s->window_size-1), "wild scan"); @@ -913,10 +1224,8 @@ local uInt longest_match(s, cur_match) if (len < MIN_MATCH) return MIN_MATCH - 1; s->match_start = cur_match; - return len <= s->lookahead ? len : s->lookahead; + return (uInt)len <= s->lookahead ? (uInt)len : s->lookahead; } -#endif /* FASTEST */ -#endif /* ASMV */ #ifdef DEBUG /* =========================================================================== @@ -931,10 +1240,10 @@ local void check_match(s, start, match, length) if (zmemcmp(s->window + match, s->window + start, length) != EQUAL) { fprintf(stderr, " start %u, match %u, length %d\n", - start, match, length); + start, match, length); do { - fprintf(stderr, "%c%c", s->window[match++], s->window[start++]); - } while (--length != 0); + fprintf(stderr, "%c%c", s->window[match++], s->window[start++]); + } while (--length != 0); z_error("invalid match"); } if (z_verbose > 1) { @@ -944,7 +1253,7 @@ local void check_match(s, start, match, length) } #else # define check_match(s, start, match, length) -#endif +#endif /* DEBUG */ /* =========================================================================== * Fill the window when the lookahead becomes insufficient. @@ -968,19 +1277,22 @@ local void fill_window(s) more = (unsigned)(s->window_size -(ulg)s->lookahead -(ulg)s->strstart); /* Deal with !@#$% 64K limit: */ - if (more == 0 && s->strstart == 0 && s->lookahead == 0) { - more = wsize; + 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 - * and lookahead == 1 (input done one byte at time) - */ - more--; + } 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. */ - } else if (s->strstart >= wsize+MAX_DIST(s)) { + if (s->strstart >= wsize+MAX_DIST(s)) { zmemcpy(s->window, s->window+wsize, (unsigned)wsize); s->match_start -= wsize; @@ -993,23 +1305,24 @@ local void fill_window(s) later. (Using level 0 permanently is not an optimal usage of zlib, so we don't care about this pathological case.) */ - n = s->hash_size; - p = &s->head[n]; - do { - m = *--p; - *p = (Pos)(m >= wsize ? m-wsize : NIL); - } while (--n); - - n = wsize; + /* %%% avoid this when Z_RLE */ + n = s->hash_size; + p = &s->head[n]; + do { + m = *--p; + *p = (Pos)(m >= wsize ? m-wsize : NIL); + } while (--n); + + n = wsize; #ifndef FASTEST - p = &s->prev[n]; - do { - m = *--p; - *p = (Pos)(m >= wsize ? m-wsize : NIL); - /* If n is not on any hash chain, prev[n] is garbage but - * its value will never be used. - */ - } while (--n); + p = &s->prev[n]; + do { + m = *--p; + *p = (Pos)(m >= wsize ? m-wsize : NIL); + /* If n is not on any hash chain, prev[n] is garbage but + * its value will never be used. + */ + } while (--n); #endif more += wsize; } @@ -1028,7 +1341,7 @@ local void fill_window(s) */ Assert(more >= 2, "more < 2"); - n = dread_buf(s->strm, s->window + s->strstart + s->lookahead, more); + 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: */ @@ -1054,8 +1367,8 @@ local void fill_window(s) _tr_flush_block(s, (s->block_start >= 0L ? \ (charf *)&s->window[(unsigned)s->block_start] : \ (charf *)Z_NULL), \ - (ulg)((long)s->strstart - s->block_start), \ - (eof)); \ + (ulg)((long)s->strstart - s->block_start), \ + (eof)); \ s->block_start = s->strstart; \ flush_pending(s->strm); \ Tracev((stderr,"[FLUSH]")); \ @@ -1096,33 +1409,43 @@ local block_state deflate_stored(s, flush) if (s->lookahead <= 1) { Assert(s->strstart < s->w_size+MAX_DIST(s) || - s->block_start >= (long)s->w_size, "slide too late"); + s->block_start >= (long)s->w_size, "slide too late"); fill_window(s); if (s->lookahead == 0 && flush == Z_NO_FLUSH) return need_more; if (s->lookahead == 0) break; /* flush the current block */ } - Assert(s->block_start >= 0L, "block gone"); + Assert(s->block_start >= 0L, "block gone"); + + s->strstart += s->lookahead; + s->lookahead = 0; - s->strstart += s->lookahead; - s->lookahead = 0; + if (flush == Z_INSERT_ONLY) { + s->block_start = s->strstart; + continue; + } - /* Emit a stored block if pending_buf will be full: */ - max_start = s->block_start + max_block_size; + /* Emit a stored block if pending_buf will be full: */ + max_start = s->block_start + max_block_size; if (s->strstart == 0 || (ulg)s->strstart >= max_start) { - /* strstart == 0 is possible when wraparound on 16-bit machine */ - s->lookahead = (uInt)(s->strstart - max_start); - s->strstart = (uInt)max_start; + /* strstart == 0 is possible when wraparound on 16-bit machine */ + s->lookahead = (uInt)(s->strstart - max_start); + s->strstart = (uInt)max_start; FLUSH_BLOCK(s, 0); - } - /* Flush if we may have to slide, otherwise block_start may become + } + /* Flush if we may have to slide, otherwise block_start may become * negative and the data will be gone: */ if (s->strstart - (uInt)s->block_start >= MAX_DIST(s)) { FLUSH_BLOCK(s, 0); - } + } } + if (flush == Z_INSERT_ONLY) { + s->block_start = s->strstart; + return need_more; + } + FLUSH_BLOCK(s, flush == Z_FINISH); return flush == Z_FINISH ? finish_done : block_done; } @@ -1150,8 +1473,8 @@ local block_state deflate_fast(s, flush) if (s->lookahead < MIN_LOOKAHEAD) { fill_window(s); if (s->lookahead < MIN_LOOKAHEAD && flush == Z_NO_FLUSH) { - return need_more; - } + return need_more; + } if (s->lookahead == 0) break; /* flush the current block */ } @@ -1176,10 +1499,19 @@ local block_state deflate_fast(s, flush) * of window index 0 (in particular we have to avoid a match * of the string with itself at the start of the input file). */ - if (s->strategy != Z_HUFFMAN_ONLY) { +#ifdef FASTEST + if ((s->strategy != Z_HUFFMAN_ONLY && s->strategy != Z_RLE) || + (s->strategy == Z_RLE && s->strstart - hash_head == 1)) { + s->match_length = longest_match_fast (s, hash_head); + } +#else + if (s->strategy != Z_HUFFMAN_ONLY && s->strategy != Z_RLE) { s->match_length = longest_match (s, hash_head); + } else if (s->strategy == Z_RLE && s->strstart - hash_head == 1) { + s->match_length = longest_match_fast (s, hash_head); } - /* longest_match() sets match_start */ +#endif + /* longest_match() or longest_match_fast() sets match_start */ } if (s->match_length >= MIN_MATCH) { check_match(s, s->strstart, s->match_start, s->match_length); @@ -1195,7 +1527,7 @@ local block_state deflate_fast(s, flush) #ifndef FASTEST if (s->match_length <= s->max_insert_length && s->lookahead >= MIN_MATCH) { - s->match_length--; /* string at strstart already in hash table */ + s->match_length--; /* string at strstart already in table */ do { s->strstart++; INSERT_STRING(s, s->strstart, hash_head); @@ -1203,10 +1535,10 @@ local block_state deflate_fast(s, flush) * always MIN_MATCH bytes ahead. */ } while (--s->match_length != 0); - s->strstart++; + s->strstart++; } else #endif - { + { s->strstart += s->match_length; s->match_length = 0; s->ins_h = s->window[s->strstart]; @@ -1223,7 +1555,7 @@ local block_state deflate_fast(s, flush) Tracevv((stderr,"%c", s->window[s->strstart])); _tr_tally_lit (s, s->window[s->strstart], bflush); s->lookahead--; - s->strstart++; + s->strstart++; } if (bflush) FLUSH_BLOCK(s, 0); } @@ -1235,6 +1567,7 @@ local block_state deflate_fast(s, flush) return flush == Z_FINISH ? finish_done : block_done; } +#ifndef FASTEST /* =========================================================================== * Same as above, but achieves better compression. We use a lazy * evaluation for matches: a match is finally adopted only if there is @@ -1257,8 +1590,8 @@ local block_state deflate_slow(s, flush) if (s->lookahead < MIN_LOOKAHEAD) { fill_window(s); if (s->lookahead < MIN_LOOKAHEAD && flush == Z_NO_FLUSH) { - return need_more; - } + return need_more; + } if (s->lookahead == 0) break; /* flush the current block */ } @@ -1286,14 +1619,19 @@ local block_state deflate_slow(s, flush) * of window index 0 (in particular we have to avoid a match * of the string with itself at the start of the input file). */ - if (s->strategy != Z_HUFFMAN_ONLY) { + if (s->strategy != Z_HUFFMAN_ONLY && s->strategy != Z_RLE) { s->match_length = longest_match (s, hash_head); + } else if (s->strategy == Z_RLE && s->strstart - hash_head == 1) { + s->match_length = longest_match_fast (s, hash_head); } - /* longest_match() sets match_start */ + /* longest_match() or longest_match_fast() sets match_start */ - if (s->match_length <= 5 && (s->strategy == Z_FILTERED || - (s->match_length == MIN_MATCH && - s->strstart - s->match_start > TOO_FAR))) { + if (s->match_length <= 5 && (s->strategy == Z_FILTERED +#if TOO_FAR <= 32767 + || (s->match_length == MIN_MATCH && + s->strstart - s->match_start > TOO_FAR) +#endif + )) { /* If prev_match is also MIN_MATCH, match_start is garbage * but we will ignore the current match anyway. @@ -1311,7 +1649,7 @@ local block_state deflate_slow(s, flush) check_match(s, s->strstart-1, s->prev_match, s->prev_length); _tr_tally_dist(s, s->strstart -1 - s->prev_match, - s->prev_length - MIN_MATCH, bflush); + s->prev_length - MIN_MATCH, bflush); /* Insert in hash table all strings up to the end of the match. * strstart-1 and strstart are already inserted. If there is not @@ -1337,8 +1675,8 @@ local block_state deflate_slow(s, flush) * is longer, truncate the previous match to a single literal. */ Tracevv((stderr,"%c", s->window[s->strstart-1])); - _tr_tally_lit(s, s->window[s->strstart-1], bflush); - if (bflush) { + _tr_tally_lit(s, s->window[s->strstart-1], bflush); + if (bflush) { FLUSH_BLOCK_ONLY(s, 0); } s->strstart++; @@ -1366,3 +1704,65 @@ local block_state deflate_slow(s, flush) FLUSH_BLOCK(s, flush == Z_FINISH); return flush == Z_FINISH ? finish_done : block_done; } +#endif /* FASTEST */ + +#if 0 +/* =========================================================================== + * For Z_RLE, simply look for runs of bytes, generate matches only of distance + * 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; +{ + int bflush; /* set if current block must be flushed */ + uInt run; /* length of run */ + uInt max; /* maximum length of run */ + uInt prev; /* byte at distance one to match */ + Bytef *scan; /* scan for end of run */ + + for (;;) { + /* Make sure that we always have enough lookahead, except + * at the end of the input file. We need MAX_MATCH bytes + * for the longest encodable run. + */ + if (s->lookahead < MAX_MATCH) { + fill_window(s); + if (s->lookahead < MAX_MATCH && flush == Z_NO_FLUSH) { + return need_more; + } + if (s->lookahead == 0) break; /* flush the current block */ + } + + /* See how many times the previous byte repeats */ + run = 0; + if (s->strstart > 0) { /* if there is a previous byte, that is */ + max = s->lookahead < MAX_MATCH ? s->lookahead : MAX_MATCH; + scan = s->window + s->strstart - 1; + prev = *scan++; + do { + if (*scan++ != prev) + break; + } while (++run < max); + } + + /* Emit match if have run of MIN_MATCH or longer, else emit literal */ + if (run >= MIN_MATCH) { + check_match(s, s->strstart, s->strstart - 1, run); + _tr_tally_dist(s, 1, run - MIN_MATCH, bflush); + s->lookahead -= run; + s->strstart += run; + } else { + /* No match, output a literal byte */ + Tracevv((stderr,"%c", s->window[s->strstart])); + _tr_tally_lit (s, s->window[s->strstart], bflush); + s->lookahead--; + s->strstart++; + } + if (bflush) FLUSH_BLOCK(s, 0); + } + FLUSH_BLOCK(s, flush == Z_FINISH); + return flush == Z_FINISH ? finish_done : block_done; +} +#endif