X-Git-Url: https://mattmccutchen.net/rsync/rsync.git/blobdiff_plain/951e826b75c4a4e6bc066e248d7489fb6eba6fde..58663df4323991bde024ffe4436b67e53f56e52b:/match.c

diff --git a/match.c b/match.c
index bb40ebfe..f327fd37 100644
--- a/match.c
+++ b/match.c
@@ -3,7 +3,7 @@
  *
  * Copyright (C) 1996 Andrew Tridgell
  * Copyright (C) 1996 Paul Mackerras
- * Copyright (C) 2003-2008 Wayne Davison
+ * Copyright (C) 2003-2009 Wayne Davison
  *
  * This program is free software; you can redistribute it and/or modify
  * it under the terms of the GNU General Public License as published by
@@ -20,11 +20,14 @@
  */
 
 #include "rsync.h"
+#include "inums.h"
 
 extern int checksum_seed;
 extern int append_mode;
+extern int checksum_len;
 
 int updating_basis_file;
+char sender_file_sum[MAX_DIGEST_LEN];
 
 static int false_alarms;
 static int hash_hits;
@@ -88,8 +91,7 @@ static void build_hash_table(struct sum_struct *s)
 static OFF_T last_match;
 
 
-/**
- * Transmit a literal and/or match token.
+/* Transmit a literal and/or match token.
  *
  * This delightfully-named function is called either when we find a
  * match and need to transmit all the unmatched data leading up to it,
@@ -97,19 +99,19 @@ static OFF_T last_match;
  * transmit it.  As a result of this second case, it is called even if
  * we have not matched at all!
  *
- * @param i If >0, the number of a matched token.  If 0, indicates we
- * have only literal data.
- **/
+ * If i >= 0, the number of a matched token.  If < 0, indicates we have
+ * only literal data.  A -1 will send a 0-token-int too, and a -2 sends
+ * only literal data, w/o any token-int. */
 static void matched(int f, struct sum_struct *s, struct map_struct *buf,
 		    OFF_T offset, int32 i)
 {
 	int32 n = (int32)(offset - last_match); /* max value: block_size (int32) */
 	int32 j;
 
-	if (DEBUG_GTE(CHKSUM, 2) && i >= 0) {
+	if (DEBUG_GTE(DELTASUM, 2) && i >= 0) {
 		rprintf(FINFO,
-			"match at %.0f last_match=%.0f j=%d len=%ld n=%ld\n",
-			(double)offset, (double)last_match, i,
+			"match at %s last_match=%s j=%d len=%ld n=%ld\n",
+			big_num(offset), big_num(last_match), i,
 			(long)s->sums[i].len, (long)n);
 	}
 
@@ -139,8 +141,8 @@ static void matched(int f, struct sum_struct *s, struct map_struct *buf,
 static void hash_search(int f,struct sum_struct *s,
 			struct map_struct *buf, OFF_T len)
 {
-	OFF_T offset, end;
-	int32 k, want_i, backup;
+	OFF_T offset, aligned_offset, end;
+	int32 k, want_i, aligned_i, backup;
 	char sum2[SUM_LENGTH];
 	uint32 s1, s2, sum;
 	int more;
@@ -150,9 +152,9 @@ static void hash_search(int f,struct sum_struct *s,
 	 * coding of the output to work more efficiently. */
 	want_i = 0;
 
-	if (DEBUG_GTE(CHKSUM, 2)) {
-		rprintf(FINFO, "hash search b=%ld len=%.0f\n",
-			(long)s->blength, (double)len);
+	if (DEBUG_GTE(DELTASUM, 2)) {
+		rprintf(FINFO, "hash search b=%ld len=%s\n",
+			(long)s->blength, big_num(len));
 	}
 
 	k = (int32)MIN(len, (OFF_T)s->blength);
@@ -162,25 +164,25 @@ static void hash_search(int f,struct sum_struct *s,
 	sum = get_checksum1((char *)map, k);
 	s1 = sum & 0xFFFF;
 	s2 = sum >> 16;
-	if (DEBUG_GTE(CHKSUM, 3))
+	if (DEBUG_GTE(DELTASUM, 3))
 		rprintf(FINFO, "sum=%.8x k=%ld\n", sum, (long)k);
 
-	offset = 0;
+	offset = aligned_offset = aligned_i = 0;
 
 	end = len + 1 - s->sums[s->count-1].len;
 
-	if (DEBUG_GTE(CHKSUM, 3)) {
-		rprintf(FINFO, "hash search s->blength=%ld len=%.0f count=%.0f\n",
-			(long)s->blength, (double)len, (double)s->count);
+	if (DEBUG_GTE(DELTASUM, 3)) {
+		rprintf(FINFO, "hash search s->blength=%ld len=%s count=%s\n",
+			(long)s->blength, big_num(len), big_num(s->count));
 	}
 
 	do {
 		int done_csum2 = 0;
 		int32 i;
 
-		if (DEBUG_GTE(CHKSUM, 4)) {
-			rprintf(FINFO, "offset=%.0f sum=%04x%04x\n",
-				(double)offset, s2 & 0xFFFF, s1 & 0xFFFF);
+		if (DEBUG_GTE(DELTASUM, 4)) {
+			rprintf(FINFO, "offset=%s sum=%04x%04x\n",
+				big_num(offset), s2 & 0xFFFF, s1 & 0xFFFF);
 		}
 
 		if (tablesize == TRADITIONAL_TABLESIZE) {
@@ -211,10 +213,10 @@ static void hash_search(int f,struct sum_struct *s,
 			    && !(s->sums[i].flags & SUMFLG_SAME_OFFSET))
 				continue;
 
-			if (DEBUG_GTE(CHKSUM, 3)) {
+			if (DEBUG_GTE(DELTASUM, 3)) {
 				rprintf(FINFO,
-					"potential match at %.0f i=%ld sum=%08x\n",
-					(double)offset, (long)i, sum);
+					"potential match at %s i=%ld sum=%08x\n",
+					big_num(offset), (long)i, sum);
 			}
 
 			if (!done_csum2) {
@@ -230,27 +232,51 @@ static void hash_search(int f,struct sum_struct *s,
 
 			/* When updating in-place, the best possible match is
 			 * one with an identical offset, so we prefer that over
-			 * the following want_i optimization. */
+			 * the adjacent want_i optimization. */
 			if (updating_basis_file) {
-				int32 i2;
-				for (i2 = i; i2 >= 0; i2 = s->sums[i2].chain) {
-					if (s->sums[i2].offset != offset)
-						continue;
-					if (i2 != i) {
-						if (sum != s->sums[i2].sum1)
-							break;
-						if (memcmp(sum2, s->sums[i2].sum2,
-							   s->s2length) != 0)
-							break;
-						i = i2;
+				/* All the generator's chunks start at blength boundaries. */
+				while (aligned_offset < offset) {
+					aligned_offset += s->blength;
+					aligned_i++;
+				}
+				if ((offset == aligned_offset
+				  || (sum == 0 && l == s->blength && aligned_offset + l <= len))
+				 && aligned_i < s->count) {
+					if (i != aligned_i) {
+						if (sum != s->sums[aligned_i].sum1
+						 || l != s->sums[aligned_i].len
+						 || memcmp(sum2, s->sums[aligned_i].sum2, s->s2length) != 0)
+							goto check_want_i;
+						i = aligned_i;
+					}
+					if (offset != aligned_offset) {
+						/* We've matched some zeros in a spot that is also zeros
+						 * further along in the basis file, if we find zeros ahead
+						 * in the sender's file, we'll output enough literal data
+						 * to re-align with the basis file, and get back to seeking
+						 * instead of writing. */
+						backup = (int32)(aligned_offset - last_match);
+						if (backup < 0)
+							backup = 0;
+						map = (schar *)map_ptr(buf, aligned_offset - backup, l + backup)
+						    + backup;
+						sum = get_checksum1((char *)map, l);
+						if (sum != s->sums[i].sum1)
+							goto check_want_i;
+						get_checksum2((char *)map, l, sum2);
+						if (memcmp(sum2, s->sums[i].sum2, s->s2length) != 0)
+							goto check_want_i;
+						/* OK, we have a re-alignment match.  Bump the offset
+						 * forward to the new match point. */
+						offset = aligned_offset;
 					}
-					/* This chunk was at the same offset on
-					 * both the sender and the receiver. */
+					/* This identical chunk is in the same spot in the old and new file. */
 					s->sums[i].flags |= SUMFLG_SAME_OFFSET;
-					goto set_want_i;
+					want_i = i;
 				}
 			}
 
+		  check_want_i:
 			/* we've found a match, but now check to see
 			 * if want_i can hint at a better match. */
 			if (i != want_i && want_i < s->count
@@ -262,7 +288,6 @@ static void hash_search(int f,struct sum_struct *s,
 				 * will be happy */
 				i = want_i;
 			}
-		    set_want_i:
 			want_i = i + 1;
 
 			matched(f,s,buf,offset,i);
@@ -327,9 +352,6 @@ static void hash_search(int f,struct sum_struct *s,
  **/
 void match_sums(int f, struct sum_struct *s, struct map_struct *buf, OFF_T len)
 {
-	char file_sum[MAX_DIGEST_LEN];
-	int sum_len;
-
 	last_match = 0;
 	false_alarms = 0;
 	hash_hits = 0;
@@ -362,12 +384,12 @@ void match_sums(int f, struct sum_struct *s, struct map_struct *buf, OFF_T len)
 	if (len > 0 && s->count > 0) {
 		build_hash_table(s);
 
-		if (DEBUG_GTE(CHKSUM, 2))
+		if (DEBUG_GTE(DELTASUM, 2))
 			rprintf(FINFO,"built hash table\n");
 
 		hash_search(f, s, buf, len);
 
-		if (DEBUG_GTE(CHKSUM, 2))
+		if (DEBUG_GTE(DELTASUM, 2))
 			rprintf(FINFO,"done hash search\n");
 	} else {
 		OFF_T j;
@@ -377,18 +399,28 @@ void match_sums(int f, struct sum_struct *s, struct map_struct *buf, OFF_T len)
 		matched(f, s, buf, len, -1);
 	}
 
-	sum_len = sum_end(file_sum);
-	/* If we had a read error, send a bad checksum. */
-	if (buf && buf->status != 0)
-		file_sum[0]++;
+	if (sum_end(sender_file_sum) != checksum_len)
+		overflow_exit("checksum_len"); /* Impossible... */
+
+	/* If we had a read error, send a bad checksum.  We use all bits
+	 * off as long as the checksum doesn't happen to be that, in
+	 * which case we turn the last 0 bit into a 1. */
+	if (buf && buf->status != 0) {
+		int i;
+		for (i = 0; i < checksum_len && sender_file_sum[i] == 0; i++) {}
+		memset(sender_file_sum, 0, checksum_len);
+		if (i == checksum_len)
+			sender_file_sum[i-1]++;
+	}
 
-	if (DEBUG_GTE(CHKSUM, 2))
+	if (DEBUG_GTE(DELTASUM, 2))
 		rprintf(FINFO,"sending file_sum\n");
-	write_buf(f, file_sum, sum_len);
+	write_buf(f, sender_file_sum, checksum_len);
 
-	if (DEBUG_GTE(CHKSUM, 2))
+	if (DEBUG_GTE(DELTASUM, 2)) {
 		rprintf(FINFO, "false_alarms=%d hash_hits=%d matches=%d\n",
 			false_alarms, hash_hits, matches);
+	}
 
 	total_hash_hits += hash_hits;
 	total_false_alarms += false_alarms;
@@ -398,11 +430,11 @@ void match_sums(int f, struct sum_struct *s, struct map_struct *buf, OFF_T len)
 
 void match_report(void)
 {
-	if (!DEBUG_GTE(CHKSUM, 1))
+	if (!DEBUG_GTE(DELTASUM, 1))
 		return;
 
 	rprintf(FINFO,
-		"total: matches=%d  hash_hits=%d  false_alarms=%d data=%.0f\n",
+		"total: matches=%d  hash_hits=%d  false_alarms=%d data=%s\n",
 		total_matches, total_hash_hits, total_false_alarms,
-		(double)stats.literal_data);
+		big_num(stats.literal_data));
 }