X-Git-Url: https://mattmccutchen.net/rsync/rsync.git/blobdiff_plain/5a18b34de343eca4b5537443e9bb207d91524d7e..58663df4323991bde024ffe4436b67e53f56e52b:/match.c diff --git a/match.c b/match.c index 7e9b611e..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,6 +20,7 @@ */ #include "rsync.h" +#include "inums.h" extern int checksum_seed; extern int append_mode; @@ -90,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, @@ -99,9 +99,9 @@ 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) { @@ -111,7 +111,7 @@ static void matched(int f, struct sum_struct *s, struct map_struct *buf, if (DEBUG_GTE(DELTASUM, 2) && i >= 0) { rprintf(FINFO, "match at %s last_match=%s j=%d len=%ld n=%ld\n", - big_num(offset, 0), big_num(last_match, 0), i, + big_num(offset), big_num(last_match), i, (long)s->sums[i].len, (long)n); } @@ -141,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; @@ -154,7 +154,7 @@ static void hash_search(int f,struct sum_struct *s, if (DEBUG_GTE(DELTASUM, 2)) { rprintf(FINFO, "hash search b=%ld len=%s\n", - (long)s->blength, big_num(len, 0)); + (long)s->blength, big_num(len)); } k = (int32)MIN(len, (OFF_T)s->blength); @@ -167,13 +167,13 @@ static void hash_search(int f,struct sum_struct *s, 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(DELTASUM, 3)) { rprintf(FINFO, "hash search s->blength=%ld len=%s count=%s\n", - (long)s->blength, big_num(len, 0), big_num(s->count, 0)); + (long)s->blength, big_num(len), big_num(s->count)); } do { @@ -182,7 +182,7 @@ static void hash_search(int f,struct sum_struct *s, if (DEBUG_GTE(DELTASUM, 4)) { rprintf(FINFO, "offset=%s sum=%04x%04x\n", - big_num(offset, 0), s2 & 0xFFFF, s1 & 0xFFFF); + big_num(offset), s2 & 0xFFFF, s1 & 0xFFFF); } if (tablesize == TRADITIONAL_TABLESIZE) { @@ -216,7 +216,7 @@ static void hash_search(int f,struct sum_struct *s, if (DEBUG_GTE(DELTASUM, 3)) { rprintf(FINFO, "potential match at %s i=%ld sum=%08x\n", - big_num(offset, 0), (long)i, sum); + big_num(offset), (long)i, sum); } if (!done_csum2) { @@ -232,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 @@ -264,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); @@ -413,5 +436,5 @@ void match_report(void) rprintf(FINFO, "total: matches=%d hash_hits=%d false_alarms=%d data=%s\n", total_matches, total_hash_hits, total_false_alarms, - big_num(stats.literal_data, 0)); + big_num(stats.literal_data)); }