- 1st crack at making zlib rsync friendly.

CVS patchset: 5216
CVS date: 2001/12/08 17:12:12

6 files changed, 137 insertions, 18 deletions

diff --git a/zlib/.lclintrc b/zlib/.lclintrc
index 0d6dbc94e..3cdbb7fd8 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 5541481c8..e9993f67c 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 16615d47b..de2eb0fe5 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 86116d087..0e4e34bd2 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 65ee08d3c..e6284ff0c 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 f726674c8..4553848d8 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 */