diff options
Diffstat (limited to 'zlib/deflate.c')
| -rw-r--r-- | zlib/deflate.c | 285 |
1 files changed, 214 insertions, 71 deletions
diff --git a/zlib/deflate.c b/zlib/deflate.c index 26aaf58ef..25d5818e2 100644 --- a/zlib/deflate.c +++ b/zlib/deflate.c @@ -1,5 +1,5 @@ /* deflate.c -- compress data using the deflation algorithm - * Copyright (C) 1995-1996 Jean-loup Gailly. + * Copyright (C) 1995-1998 Jean-loup Gailly. * For conditions of distribution and use, see copyright notice in zlib.h */ @@ -36,8 +36,8 @@ * * REFERENCES * - * Deutsch, L.P.,"'Deflate' Compressed Data Format Specification". - * Available in ftp.uu.net:/pub/archiving/zip/doc/deflate-1.1.doc + * Deutsch, L.P.,"DEFLATE Compressed Data Format Specification". + * Available in ftp://ds.internic.net/rfc/rfc1951.txt * * A description of the Rabin and Karp algorithm is given in the book * "Algorithms" by R. Sedgewick, Addison-Wesley, p252. @@ -47,11 +47,12 @@ * */ -/* $Id$ */ +/* @(#) $Id$ */ #include "deflate.h" -char deflate_copyright[] = " deflate 1.0.4 Copyright 1995-1996 Jean-loup Gailly "; +const char deflate_copyright[] = + " deflate 1.1.3 Copyright 1995-1998 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 @@ -77,12 +78,14 @@ 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_slow OF((deflate_state *s, int flush)); local void lm_init OF((deflate_state *s)); -local uInt longest_match OF((deflate_state *s, IPos cur_match)); local void putShortMSB OF((deflate_state *s, uInt b)); local void flush_pending OF((z_streamp strm)); -local int read_buf OF((z_streamp strm, charf *buf, unsigned size)); +local int read_buf OF((z_streamp strm, Bytef *buf, unsigned size)); #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 #ifdef DEBUG @@ -120,7 +123,7 @@ typedef struct config_s { compress_func func; } config; -local config configuration_table[10] = { +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 */ @@ -157,14 +160,23 @@ struct static_tree_desc_s {int dummy;}; /* for buggy compilers */ * Insert string str in the dictionary and set match_head to the previous head * of the hash chain (the most recent string with same hash key). Return * the previous length of the hash chain. + * If this file is compiled with -DFASTEST, the compression level is forced + * to 1, and no hash chains are maintained. * IN assertion: all calls to to INSERT_STRING are made with consecutive * input characters and the first MIN_MATCH bytes of str are valid * (except for the last MIN_MATCH-1 bytes of the input file). */ +#ifdef FASTEST +#define INSERT_STRING(s, str, match_head) \ + (UPDATE_HASH(s, s->ins_h, s->window[(str) + (MIN_MATCH-1)]), \ + match_head = s->head[s->ins_h], \ + s->head[s->ins_h] = (Pos)(str)) +#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], \ s->head[s->ins_h] = (Pos)(str)) +#endif /* =========================================================================== * Initialize the hash table (avoiding 64K overflow for 16 bit systems). @@ -172,10 +184,10 @@ struct static_tree_desc_s {int dummy;}; /* for buggy compilers */ */ #define CLEAR_HASH(s) \ s->head[s->hash_size-1] = NIL; \ - zmemzero((charf *)s->head, (unsigned)(s->hash_size-1)*sizeof(*s->head)); + zmemzero((Bytef *)s->head, (unsigned)(s->hash_size-1)*sizeof(*s->head)); /* ========================================================================= */ -int deflateInit_(strm, level, version, stream_size) +int ZEXPORT deflateInit_(strm, level, version, stream_size) z_streamp strm; int level; const char *version; @@ -187,7 +199,7 @@ int deflateInit_(strm, level, version, stream_size) } /* ========================================================================= */ -int deflateInit2_(strm, level, method, windowBits, memLevel, strategy, +int ZEXPORT deflateInit2_(strm, level, method, windowBits, memLevel, strategy, version, stream_size) z_streamp strm; int level; @@ -200,13 +212,14 @@ int deflateInit2_(strm, level, method, windowBits, memLevel, strategy, { deflate_state *s; int noheader = 0; + static const char* my_version = ZLIB_VERSION; ushf *overlay; /* We overlay pending_buf and d_buf+l_buf. This works since the average * output size for (length,distance) codes is <= 24 bits. */ - if (version == Z_NULL || version[0] != ZLIB_VERSION[0] || + if (version == Z_NULL || version[0] != my_version[0] || stream_size != sizeof(z_stream)) { return Z_VERSION_ERROR; } @@ -220,6 +233,9 @@ int deflateInit2_(strm, level, method, windowBits, memLevel, strategy, if (strm->zfree == Z_NULL) strm->zfree = zcfree; if (level == Z_DEFAULT_COMPRESSION) level = 6; +#ifdef FASTEST + level = 1; +#endif if (windowBits < 0) { /* undocumented feature: suppress zlib header */ noheader = 1; @@ -253,6 +269,7 @@ int deflateInit2_(strm, level, method, windowBits, memLevel, strategy, overlay = (ushf *) ZALLOC(strm, s->lit_bufsize, sizeof(ush)+2); s->pending_buf = (uchf *) overlay; + s->pending_buf_size = (ulg)s->lit_bufsize * (sizeof(ush)+2L); if (s->window == Z_NULL || s->prev == Z_NULL || s->head == Z_NULL || s->pending_buf == Z_NULL) { @@ -271,7 +288,7 @@ int deflateInit2_(strm, level, method, windowBits, memLevel, strategy, } /* ========================================================================= */ -int deflateSetDictionary (strm, dictionary, dictLength) +int ZEXPORT deflateSetDictionary (strm, dictionary, dictLength) z_streamp strm; const Bytef *dictionary; uInt dictLength; @@ -290,9 +307,11 @@ int deflateSetDictionary (strm, dictionary, dictLength) if (length < MIN_MATCH) return Z_OK; if (length > MAX_DIST(s)) { length = MAX_DIST(s); - dictionary += dictLength - length; +#ifndef USE_DICT_HEAD + dictionary += dictLength - length; /* use the tail of the dictionary */ +#endif } - zmemcpy((charf *)s->window, dictionary, length); + zmemcpy(s->window, dictionary, length); s->strstart = length; s->block_start = (long)length; @@ -310,7 +329,7 @@ int deflateSetDictionary (strm, dictionary, dictLength) } /* ========================================================================= */ -int deflateReset (strm) +int ZEXPORT deflateReset (strm) z_streamp strm; { deflate_state *s; @@ -340,7 +359,7 @@ int deflateReset (strm) } /* ========================================================================= */ -int deflateParams(strm, level, strategy) +int ZEXPORT deflateParams(strm, level, strategy) z_streamp strm; int level; int strategy; @@ -414,7 +433,7 @@ local void flush_pending(strm) } /* ========================================================================= */ -int deflate (strm, flush) +int ZEXPORT deflate (strm, flush) z_streamp strm; int flush; { @@ -548,42 +567,87 @@ int deflate (strm, flush) } /* ========================================================================= */ -int deflateEnd (strm) +int ZEXPORT deflateEnd (strm) z_streamp strm; { int status; 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) { + return Z_STREAM_ERROR; + } + /* Deallocate in reverse order of allocations: */ TRY_FREE(strm, strm->state->pending_buf); TRY_FREE(strm, strm->state->head); TRY_FREE(strm, strm->state->prev); TRY_FREE(strm, strm->state->window); - status = strm->state->status; ZFREE(strm, strm->state); strm->state = Z_NULL; return status == BUSY_STATE ? Z_DATA_ERROR : Z_OK; } -/* ========================================================================= */ -int deflateCopy (dest, source) +/* ========================================================================= + * Copy the source state to the destination state. + * 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; { +#ifdef MAXSEG_64K + return Z_STREAM_ERROR; +#else + deflate_state *ds; + deflate_state *ss; + ushf *overlay; + + if (source == Z_NULL || dest == Z_NULL || source->state == Z_NULL) { return Z_STREAM_ERROR; } + + ss = source->state; + *dest = *source; - return Z_STREAM_ERROR; /* to be implemented */ -#if 0 - dest->state = (struct internal_state FAR *) - (*dest->zalloc)(1, sizeof(deflate_state)); - if (dest->state == Z_NULL) return Z_MEM_ERROR; - *(dest->state) = *(source->state); + 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; + ds->strm = dest; + + 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)); + overlay = (ushf *) ZALLOC(dest, ds->lit_bufsize, sizeof(ush)+2); + ds->pending_buf = (uchf *) overlay; + + if (ds->window == Z_NULL || ds->prev == Z_NULL || ds->head == Z_NULL || + ds->pending_buf == Z_NULL) { + deflateEnd (dest); + return Z_MEM_ERROR; + } + /* following zmemcpy do not work for 16-bit MSDOS */ + zmemcpy(ds->window, ss->window, ds->w_size * 2 * sizeof(Byte)); + zmemcpy(ds->prev, ss->prev, ds->w_size * sizeof(Pos)); + zmemcpy(ds->head, ss->head, ds->hash_size * sizeof(Pos)); + zmemcpy(ds->pending_buf, ss->pending_buf, (uInt)ds->pending_buf_size); + + ds->pending_out = ds->pending_buf + (ss->pending_out - ss->pending_buf); + ds->d_buf = overlay + ds->lit_bufsize/sizeof(ush); + ds->l_buf = ds->pending_buf + (1+sizeof(ush))*ds->lit_bufsize; + + ds->l_desc.dyn_tree = ds->dyn_ltree; + ds->d_desc.dyn_tree = ds->dyn_dtree; + ds->bl_desc.dyn_tree = ds->bl_tree; + return Z_OK; #endif } @@ -597,7 +661,7 @@ int deflateCopy (dest, source) */ local int read_buf(strm, buf, size) z_streamp strm; - charf *buf; + Bytef *buf; unsigned size; { unsigned len = strm->avail_in; @@ -658,6 +722,7 @@ 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 */ @@ -792,9 +857,67 @@ local uInt longest_match(s, cur_match) } while ((cur_match = prev[cur_match & wmask]) > limit && --chain_length != 0); - if ((uInt)best_len <= s->lookahead) return best_len; + if ((uInt)best_len <= s->lookahead) return (uInt)best_len; return s->lookahead; } + +#else /* FASTEST */ +/* --------------------------------------------------------------------------- + * Optimized version for level == 1 only + */ +local uInt longest_match(s, cur_match) + deflate_state *s; + IPos cur_match; /* current match */ +{ + register Bytef *scan = s->window + s->strstart; /* current string */ + register Bytef *match; /* matched string */ + register int len; /* length of current match */ + register Bytef *strend = s->window + s->strstart + MAX_MATCH; + + /* The code is optimized for HASH_BITS >= 8 and MAX_MATCH-2 multiple of 16. + * It is easy to get rid of this optimization if necessary. + */ + Assert(s->hash_bits >= 8 && MAX_MATCH == 258, "Code too clever"); + + Assert((ulg)s->strstart <= s->window_size-MIN_LOOKAHEAD, "need lookahead"); + + Assert(cur_match < s->strstart, "no future"); + + match = s->window + cur_match; + + /* Return failure if the match length is less than 2: + */ + if (match[0] != scan[0] || match[1] != scan[1]) return MIN_MATCH-1; + + /* The check at best_len-1 can be removed because it will be made + * again later. (This heuristic is not always a win.) + * It is not necessary to compare scan[2] and match[2] since they + * are always equal when the other bytes match, given that + * the hash keys are equal and that HASH_BITS >= 8. + */ + scan += 2, match += 2; + Assert(*scan == *match, "match[2]?"); + + /* We check for insufficient lookahead only every 8th comparison; + * the 256th check will be made at strstart+258. + */ + do { + } while (*++scan == *++match && *++scan == *++match && + *++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"); + + len = MAX_MATCH - (int)(strend - scan); + + if (len < MIN_MATCH) return MIN_MATCH - 1; + + s->match_start = cur_match; + return len <= s->lookahead ? len : s->lookahead; +} +#endif /* FASTEST */ #endif /* ASMV */ #ifdef DEBUG @@ -807,8 +930,8 @@ local void check_match(s, start, match, length) int length; { /* check that the match is indeed a match */ - if (zmemcmp((charf *)s->window + match, - (charf *)s->window + start, length) != EQUAL) { + if (zmemcmp(s->window + match, + s->window + start, length) != EQUAL) { fprintf(stderr, " start %u, match %u, length %d\n", start, match, length); do { @@ -816,7 +939,7 @@ local void check_match(s, start, match, length) } while (--length != 0); z_error("invalid match"); } - if (verbose > 1) { + if (z_verbose > 1) { fprintf(stderr,"\\[%d,%d]", start-match, length); do { putc(s->window[start++], stderr); } while (--length != 0); } @@ -861,33 +984,35 @@ local void fill_window(s) */ } else if (s->strstart >= wsize+MAX_DIST(s)) { - zmemcpy((charf *)s->window, (charf *)s->window+wsize, - (unsigned)wsize); + zmemcpy(s->window, s->window+wsize, (unsigned)wsize); s->match_start -= wsize; s->strstart -= wsize; /* we now have strstart >= MAX_DIST */ - s->block_start -= (long) wsize; /* Slide the hash table (could be avoided with 32 bit values - at the expense of memory usage): + 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. (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; - 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); - + 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); +#endif more += wsize; } if (s->strm->avail_in == 0) return; @@ -905,8 +1030,7 @@ local void fill_window(s) */ Assert(more >= 2, "more < 2"); - n = read_buf(s->strm, (charf *)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: */ @@ -951,12 +1075,24 @@ local void fill_window(s) * This function does not insert new strings in the dictionary since * uncompressible data is probably not useful. This function is used * only for the level=0 compression option. - * NOTE: this function should be optimized to avoid extra copying. + * NOTE: this function should be optimized to avoid extra copying from + * window to pending_buf. */ local block_state deflate_stored(s, flush) deflate_state *s; int flush; { + /* Stored blocks are limited to 0xffff bytes, pending_buf is limited + * to pending_buf_size, and each stored block has a 5 byte header: + */ + ulg max_block_size = 0xffff; + ulg max_start; + + if (max_block_size > s->pending_buf_size - 5) { + max_block_size = s->pending_buf_size - 5; + } + + /* Copy as much as possible from input to output: */ for (;;) { /* Fill the window as much as possible: */ if (s->lookahead <= 1) { @@ -974,14 +1110,17 @@ local block_state deflate_stored(s, flush) s->strstart += s->lookahead; s->lookahead = 0; - /* Stored blocks are limited to 0xffff bytes: */ - if (s->strstart == 0 || s->strstart > 0xfffe) { + /* 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 = s->strstart - 0xffff; - s->strstart = 0xffff; + s->lookahead = (uInt)(s->strstart - max_start); + s->strstart = (uInt)max_start; + FLUSH_BLOCK(s, 0); } - - /* Emit a stored block if it is large enough: */ + /* 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); } @@ -1041,14 +1180,15 @@ local block_state deflate_fast(s, flush) if (s->match_length >= MIN_MATCH) { check_match(s, s->strstart, s->match_start, s->match_length); - bflush = _tr_tally(s, s->strstart - s->match_start, - s->match_length - MIN_MATCH); + _tr_tally_dist(s, s->strstart - s->match_start, + s->match_length - MIN_MATCH, bflush); s->lookahead -= s->match_length; /* Insert new strings in the hash table only if the match length * is not too large. This saves time but degrades compression. */ +#ifndef FASTEST if (s->match_length <= s->max_insert_length && s->lookahead >= MIN_MATCH) { s->match_length--; /* string at strstart already in hash table */ @@ -1060,7 +1200,9 @@ local block_state deflate_fast(s, flush) */ } while (--s->match_length != 0); s->strstart++; - } else { + } else +#endif + { s->strstart += s->match_length; s->match_length = 0; s->ins_h = s->window[s->strstart]; @@ -1075,7 +1217,7 @@ local block_state deflate_fast(s, flush) } else { /* No match, output a literal byte */ Tracevv((stderr,"%c", s->window[s->strstart])); - bflush = _tr_tally (s, 0, s->window[s->strstart]); + _tr_tally_lit (s, s->window[s->strstart], bflush); s->lookahead--; s->strstart++; } @@ -1154,8 +1296,8 @@ local block_state deflate_slow(s, flush) check_match(s, s->strstart-1, s->prev_match, s->prev_length); - bflush = _tr_tally(s, s->strstart -1 - s->prev_match, - s->prev_length - MIN_MATCH); + _tr_tally_dist(s, s->strstart -1 - s->prev_match, + 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 @@ -1181,7 +1323,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])); - if (_tr_tally (s, 0, s->window[s->strstart-1])) { + _tr_tally_lit(s, s->window[s->strstart-1], bflush); + if (bflush) { FLUSH_BLOCK_ONLY(s, 0); } s->strstart++; @@ -1199,7 +1342,7 @@ local block_state deflate_slow(s, flush) Assert (flush != Z_NO_FLUSH, "no flush?"); if (s->match_available) { Tracevv((stderr,"%c", s->window[s->strstart-1])); - _tr_tally (s, 0, s->window[s->strstart-1]); + _tr_tally_lit(s, s->window[s->strstart-1], bflush); s->match_available = 0; } FLUSH_BLOCK(s, flush == Z_FINISH); |