From 58f451f3c3240f76874e27bff8325dea88134e7e Mon Sep 17 00:00:00 2001 From: jbj Date: Sat, 8 Dec 2001 17:12:12 +0000 Subject: [PATCH] - 1st crack at making zlib rsync friendly. CVS patchset: 5216 CVS date: 2001/12/08 17:12:12 --- zlib/.lclintrc | 2 +- zlib/deflate.c | 107 ++++++++++++++++++++++++++++++++++++++++++++++++++++++--- zlib/deflate.h | 13 +++++-- zlib/trees.c | 27 ++++++++++----- zlib/zconf.h | 4 ++- zlib/zlib.h | 2 ++ 6 files changed, 137 insertions(+), 18 deletions(-) diff --git a/zlib/.lclintrc b/zlib/.lclintrc index 0d6dbc9..3cdbb7f 100644 --- a/zlib/.lclintrc +++ b/zlib/.lclintrc @@ -1,4 +1,4 @@ --I. -DHAVE_CONFIG_H -D_GNU_SOURCE -DSTDC +-I. -DHAVE_CONFIG_H -D_GNU_SOURCE -DSTDC -DHAVE_UNISTD_H -DUSE_MMAP -DWITH_RSYNC_PAD +partial +forcehints diff --git a/zlib/deflate.c b/zlib/deflate.c index 5541481..e9993f6 100644 --- a/zlib/deflate.c +++ b/zlib/deflate.c @@ -47,7 +47,7 @@ * */ -/* @(#) $Id: deflate.c,v 1.1.1.1 2001/11/21 19:43:12 jbj Exp $ */ +/* @(#) $Id: deflate.c,v 1.2 2001/11/22 21:12:46 jbj Exp $ */ #include "deflate.h" @@ -126,6 +126,19 @@ local void check_match OF((deflate_state *s, IPos start, IPos match, * See deflate.c for comments about the MIN_MATCH+1. */ +#if defined(WITH_RSYNC_PAD) +local int rsync = 0; +/* Perform rsync padding? */ + +#ifndef RSYNC_WIN +# define RSYNC_WIN 4096 +#endif +/* Size of rsync window, must be < MAX_DIST */ + +#define RSYNC_SUM_MATCH(s) (((s)->rsync_sum % (s)->rsync_win) == 0) +/* Whether window sum matches magic value */ +#endif + /* Values for max_lazy_match, good_match and max_chain_length, depending on * the desired pack level (0..9). The values given below have been tuned to * exclude worst case performance for pathological files. Better values may be @@ -695,6 +708,13 @@ local void lm_init (deflate_state *s) #ifdef ASMV match_init(); /* initialize the asm code */ #endif + +#if defined(WITH_RSYNC_PAD) + /* rsync params */ + s->rsync_chunk_end = 0xFFFFFFFFUL; + s->rsync_sum = 0; + s->rsync_win = RSYNC_WIN; +#endif } /* =========================================================================== @@ -971,6 +991,11 @@ local void fill_window(deflate_state *s) s->strstart -= wsize; /* we now have strstart >= MAX_DIST */ s->block_start -= (long) wsize; +#if defined(WITH_RSYNC_PAD) + if (s->rsync_chunk_end != 0xFFFFFFFFUL) + s->rsync_chunk_end -= wsize; +#endif + /* Slide the hash table (could be avoided with 32 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 @@ -1030,6 +1055,42 @@ local void fill_window(deflate_state *s) } while (s->lookahead < MIN_LOOKAHEAD && s->strm->avail_in != 0); } +#if defined(WITH_RSYNC_PAD) +local void rsync_roll(deflate_state *s, unsigned num) +{ + unsigned start = s->strstart; + unsigned i; + + if (start < s->rsync_win) { + /* before window fills. */ + for (i = start; i < s->rsync_win; i++) { + if (i == start + num) return; + s->rsync_sum += (ulg)s->window[i]; + } + num -= (s->rsync_win - start); + start = s->rsync_win; + } + + /* buffer after window full */ + for (i = start; i < start+num; i++) { + /* New character in */ + s->rsync_sum += (ulg)s->window[i]; + /* Old character out */ + s->rsync_sum -= (ulg)s->window[i - s->rsync_win]; + if (s->rsync_chunk_end == 0xFFFFFFFFUL && RSYNC_SUM_MATCH(s)) + s->rsync_chunk_end = i; + } +} + +/* =========================================================================== + * Set rsync_chunk_end if window sum matches magic value. + */ +#define RSYNC_ROLL(s, num) \ + do { if (rsync) rsync_roll((s), (num)); } while(0) +#else /* WITH_RSYNC_PAD */ +#define RSYNC_ROLL(s, num) +#endif /* WITH_RSYNC_PAD */ + /* =========================================================================== * Flush the current block, with given end-of-file flag. * IN assertion: strstart is set to the end of the current match. @@ -1039,6 +1100,7 @@ local void fill_window(deflate_state *s) (charf *)&s->window[(unsigned)s->block_start] : \ (charf *)Z_NULL), \ (ulg)((long)s->strstart - s->block_start), \ + bflush-1, \ (eof)); \ s->block_start = s->strstart; \ flush_pending(s->strm); \ @@ -1067,6 +1129,11 @@ local block_state deflate_stored(deflate_state *s, int flush) */ ulg max_block_size = 0xffff; ulg max_start; +#if defined(WITH_RSYNC_PAD) + int bflush = (rsync ? 2 : 1); +#else + int bflush = 1; +#endif if (max_block_size > s->pending_buf_size - 5) { max_block_size = s->pending_buf_size - 5; @@ -1087,6 +1154,7 @@ local block_state deflate_stored(deflate_state *s, int flush) } Assert(s->block_start >= 0L, "block gone"); + RSYNC_ROLL(s, s->lookahead); s->strstart += s->lookahead; s->lookahead = 0; @@ -1163,6 +1231,7 @@ local block_state deflate_fast(deflate_state *s, int flush) s->lookahead -= s->match_length; + RSYNC_ROLL(s, 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. */ @@ -1196,9 +1265,16 @@ local block_state deflate_fast(deflate_state *s, int flush) /* No match, output a literal byte */ Tracevv((stderr,"%c", s->window[s->strstart])); _tr_tally_lit (s, s->window[s->strstart], bflush); + RSYNC_ROLL(s, 1); s->lookahead--; s->strstart++; } +#if defined(WITH_RSYNC_PAD) + if (rsync && s->strstart > s->rsync_chunk_end) { + s->rsync_chunk_end = 0xFFFFFFFFUL; + bflush = 2; + } +#endif if (bflush) FLUSH_BLOCK(s, 0); } FLUSH_BLOCK(s, flush == Z_FINISH); @@ -1282,6 +1358,7 @@ local block_state deflate_slow(deflate_state *s, int flush) */ s->lookahead -= s->prev_length-1; s->prev_length -= 2; + RSYNC_ROLL(s, s->prev_length+1); do { if (++s->strstart <= max_insert) { INSERT_STRING(s, s->strstart, hash_head); @@ -1291,7 +1368,13 @@ local block_state deflate_slow(deflate_state *s, int flush) s->match_length = MIN_MATCH-1; s->strstart++; - if (bflush) FLUSH_BLOCK(s, 0); +#if defined(WITH_RSYNC_PAD) + if (rsync && s->strstart > s->rsync_chunk_end) { + s->rsync_chunk_end = 0xFFFFFFFFUL; + bflush = 2; + } +#endif + if (bflush) FLUSH_BLOCK(s, 0); } else if (s->match_available) { /* If there was no match at the previous position, output a @@ -1300,9 +1383,16 @@ local block_state deflate_slow(deflate_state *s, int flush) */ Tracevv((stderr,"%c", s->window[s->strstart-1])); _tr_tally_lit(s, s->window[s->strstart-1], bflush); +#if defined(WITH_RSYNC_PAD) + if (rsync && s->strstart > s->rsync_chunk_end) { + s->rsync_chunk_end = 0xFFFFFFFFUL; + bflush = 2; + } +#endif if (bflush) { - FLUSH_BLOCK_ONLY(s, 0); - } + FLUSH_BLOCK_ONLY(s, 0); + } + RSYNC_ROLL(s, 1); s->strstart++; s->lookahead--; if (s->strm->avail_out == 0) return need_more; @@ -1310,7 +1400,16 @@ local block_state deflate_slow(deflate_state *s, int flush) /* There is no previous match to compare with, wait for * the next step to decide. */ +#if defined(WITH_RSYNC_PAD) + if (rsync && s->strstart > s->rsync_chunk_end) { + /* Reset huffman tree */ + s->rsync_chunk_end = 0xFFFFFFFFUL; + bflush = 2; + FLUSH_BLOCK(s, 0); + } +#endif s->match_available = 1; + RSYNC_ROLL(s, 1); s->strstart++; s->lookahead--; } diff --git a/zlib/deflate.h b/zlib/deflate.h index 16615d4..de2eb0f 100644 --- a/zlib/deflate.h +++ b/zlib/deflate.h @@ -8,7 +8,7 @@ subject to change. Applications should only use zlib.h. */ -/* @(#) $Id: deflate.h,v 1.1.1.1 2001/11/21 19:43:12 jbj Exp $ */ +/* @(#) $Id: deflate.h,v 1.2 2001/11/22 21:12:46 jbj Exp $ */ #ifndef _DEFLATE_H #define _DEFLATE_H @@ -233,7 +233,7 @@ typedef struct internal_state { uInt matches; /* number of string matches in current block */ int last_eob_len; /* bit length of EOB code for last block */ -#ifdef DEBUG +#if defined(WITH_RSYNC_PAD) || defined(DEBUG) ulg compressed_len; /* total bit length of compressed file mod 2^32 */ ulg bits_sent; /* bit length of compressed data sent mod 2^32 */ #endif @@ -247,6 +247,13 @@ typedef struct internal_state { * are always zero. */ +#if defined(WITH_RSYNC_PAD) + /* rsync params */ + ulg rsync_chunk_end; + ulg rsync_sum; + int rsync_win; +#endif + } FAR deflate_state; /* Output a byte on the stream. @@ -271,7 +278,7 @@ void _tr_init OF((deflate_state *s)) int _tr_tally OF((deflate_state *s, unsigned dist, unsigned lc)) /*@modifies *s @*/; void _tr_flush_block OF((deflate_state *s, charf *buf, ulg stored_len, - int eof)) + int pad, int eof)) /*@modifies *s @*/; void _tr_align OF((deflate_state *s)) /*@modifies *s @*/; diff --git a/zlib/trees.c b/zlib/trees.c index 86116d0..0e4e34b 100644 --- a/zlib/trees.c +++ b/zlib/trees.c @@ -29,7 +29,7 @@ * Addison-Wesley, 1983. ISBN 0-201-06672-6. */ -/* @(#) $Id: trees.c,v 1.2 2001/11/21 22:01:55 jbj Exp $ */ +/* @(#) $Id: trees.c,v 1.3 2001/11/22 21:12:46 jbj Exp $ */ /* #define GEN_TREES_H */ @@ -416,7 +416,7 @@ void _tr_init(deflate_state *s) s->bi_buf = 0; s->bi_valid = 0; s->last_eob_len = 8; /* enough lookahead for inflate */ -#ifdef DEBUG +#if defined(WITH_RSYNC_PAD) || defined(DEBUG) s->compressed_len = 0L; s->bits_sent = 0L; #endif @@ -902,7 +902,7 @@ local void send_all_trees(deflate_state *s, int lcodes, int dcodes, int blcodes) void _tr_stored_block(deflate_state *s, charf *buf, ulg stored_len, int eof) { send_bits(s, (STORED_BLOCK<<1)+eof, 3); /* send block type */ -#ifdef DEBUG +#if defined(WITH_RSYNC_PAD) || defined(DEBUG) s->compressed_len = (s->compressed_len + 3 + 7) & (ulg)~7L; s->compressed_len += (stored_len + 4) << 3; #endif @@ -924,7 +924,7 @@ void _tr_align(deflate_state *s) { send_bits(s, STATIC_TREES<<1, 3); send_code(s, END_BLOCK, static_ltree); -#ifdef DEBUG +#if defined(WITH_RSYNC_PAD) || defined(DEBUG) s->compressed_len += 10L; /* 3 for block type, 7 for EOB */ #endif bi_flush(s); @@ -936,7 +936,7 @@ void _tr_align(deflate_state *s) if (1 + s->last_eob_len + 10 - s->bi_valid < 9) { send_bits(s, STATIC_TREES<<1, 3); send_code(s, END_BLOCK, static_ltree); -#ifdef DEBUG +#if defined(WITH_RSYNC_PAD) || defined(DEBUG) s->compressed_len += 10L; #endif bi_flush(s); @@ -951,9 +951,11 @@ void _tr_align(deflate_state *s) * @param s * @param buf input block, of NULL if too old * @param stored_len length of input block + * @param pad true if block is to be rsync padded * @param eof true if this is the last block for a file */ -void _tr_flush_block(deflate_state *s, charf *buf, ulg stored_len, int eof) +void _tr_flush_block(deflate_state *s, charf *buf, ulg stored_len, + int pad, int eof) { ulg opt_lenb, static_lenb; /* opt_len and static_len in bytes */ int max_blindex = 0; /* index of last bit length code of non zero freq */ @@ -1017,7 +1019,7 @@ void _tr_flush_block(deflate_state *s, charf *buf, ulg stored_len, int eof) #endif send_bits(s, (STATIC_TREES<<1)+eof, 3); compress_block(s, (ct_data *)static_ltree, (ct_data *)static_dtree); -#ifdef DEBUG +#if defined(WITH_RSYNC_PAD) || defined(DEBUG) s->compressed_len += 3 + s->static_len; #endif } else { @@ -1025,7 +1027,7 @@ void _tr_flush_block(deflate_state *s, charf *buf, ulg stored_len, int eof) send_all_trees(s, s->l_desc.max_code+1, s->d_desc.max_code+1, max_blindex+1); compress_block(s, (ct_data *)s->dyn_ltree, (ct_data *)s->dyn_dtree); -#ifdef DEBUG +#if defined(WITH_RSYNC_PAD) || defined(DEBUG) s->compressed_len += 3 + s->opt_len; #endif } @@ -1037,10 +1039,17 @@ void _tr_flush_block(deflate_state *s, charf *buf, ulg stored_len, int eof) if (eof) { bi_windup(s); -#ifdef DEBUG +#if defined(WITH_RSYNC_PAD) || defined(DEBUG) s->compressed_len += 7; /* align on byte boundary */ #endif } +#if defined(WITH_RSYNC_PAD) + else if (pad && (s->compressed_len % 8) != 0) { + send_bits(s, (STORED_BLOCK<<1)+eof, 3); /* send block type */ + s->compressed_len = (s->compressed_len + 3 + 7) & ~7L; + copy_block(s, buf, 0, 1); /* with header */ + } +#endif Tracev((stderr,"\ncomprlen %lu(%lu) ", s->compressed_len>>3, s->compressed_len-7*eof)); } diff --git a/zlib/zconf.h b/zlib/zconf.h index 65ee08d..e6284ff 100644 --- a/zlib/zconf.h +++ b/zlib/zconf.h @@ -3,10 +3,11 @@ * For conditions of distribution and use, see copyright notice in zlib.h */ -/* @(#) $Id: zconf.h,v 1.1.1.1 2001/11/21 19:43:12 jbj Exp $ */ +/* @(#) $Id: zconf.h,v 1.2 2001/11/22 21:12:46 jbj Exp $ */ #ifndef _ZCONF_H #define _ZCONF_H +/*@-constuse -typeuse@*/ /* * If you *really* need a unique prefix for all types and library functions, @@ -279,4 +280,5 @@ typedef uLong FAR uLongf; # pragma map(inflate_trees_free,"INTRFR") #endif +/*@=constuse =typeuse@*/ #endif /* _ZCONF_H */ diff --git a/zlib/zlib.h b/zlib/zlib.h index f726674..4553848 100644 --- a/zlib/zlib.h +++ b/zlib/zlib.h @@ -30,6 +30,7 @@ #ifndef _ZLIB_H #define _ZLIB_H +/*@-declundef -fcnuse @*/ #include "zconf.h" @@ -950,4 +951,5 @@ ZEXTERN const uLongf * ZEXPORT get_crc_table OF((void)) } #endif +/*@=declundef =fcnuse @*/ #endif /* _ZLIB_H */ -- 2.7.4