X-Git-Url: https://mattmccutchen.net/rsync/rsync.git/blobdiff_plain/68207537326987e28d42ad3b2fe53bdb1ebcc781..a0456b9c4635be8832fc5712454a75ec102b1176:/match.c diff --git a/match.c b/match.c index 19b17c5c..9719319a 100644 --- a/match.c +++ b/match.c @@ -1,21 +1,23 @@ /* - Copyright (C) Andrew Tridgell 1996 - Copyright (C) Paul Mackerras 1996 - - 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 - the Free Software Foundation; either version 2 of the License, or - (at your option) any later version. - - This program is distributed in the hope that it will be useful, - but WITHOUT ANY WARRANTY; without even the implied warranty of - MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the - GNU General Public License for more details. - - You should have received a copy of the GNU General Public License - along with this program; if not, write to the Free Software - Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA. -*/ + * Block matching used by the file-transfer code. + * + * Copyright (C) 1996 Andrew Tridgell + * Copyright (C) 1996 Paul Mackerras + * Copyright (C) 2003-2007 Wayne Davison + * + * This program is free software; you can redistribute it and/or modify + * it under the terms of the GNU General Public License version 2 as + * published by the Free Software Foundation. + * + * This program is distributed in the hope that it will be useful, + * but WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + * GNU General Public License for more details. + * + * You should have received a copy of the GNU General Public License along + * with this program; if not, write to the Free Software Foundation, Inc., + * 51 Franklin Street - Fifth Floor, Boston, MA 02110-1301, USA. + */ #include "rsync.h" @@ -37,30 +39,24 @@ static int total_matches; extern struct stats stats; -static uint32 tablesize; +#define TABLESIZE (1<<16) + static int32 *hash_table; -#define SUM2HASH(sum) ((sum)%tablesize) +#define SUM2HASH2(s1,s2) (((s1) + (s2)) & 0xFFFF) +#define SUM2HASH(sum) SUM2HASH2((sum)&0xFFFF,(sum)>>16) static void build_hash_table(struct sum_struct *s) { int32 i; - uint32 prior_size = tablesize; - - /* Dynamically calculate the hash table size so that the hash load - * for big files is about 80%. This number must be odd or s2 will - * not be able to span the entire set. */ - tablesize = (uint32)(s->count/8) * 10 + 11; - if (tablesize < 65537) - tablesize = 65537; /* a prime number */ - if (tablesize != prior_size) { - free(hash_table); - hash_table = new_array(int32, tablesize); + + if (!hash_table) { + hash_table = new_array(int32, TABLESIZE); if (!hash_table) out_of_memory("build_hash_table"); } - memset(hash_table, 0xFF, tablesize * sizeof hash_table[0]); + memset(hash_table, 0xFF, TABLESIZE * sizeof hash_table[0]); for (i = 0; i < s->count; i++) { uint32 t = SUM2HASH(s->sums[i].sum1); @@ -88,7 +84,7 @@ static OFF_T last_match; static void matched(int f, struct sum_struct *s, struct map_struct *buf, OFF_T offset, int32 i) { - int32 n = offset - last_match; /* max value: block_size (int32) */ + int32 n = (int32)(offset - last_match); /* max value: block_size (int32) */ int32 j; if (verbose > 2 && i >= 0) { @@ -124,8 +120,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, backup; - int32 k, want_i; + OFF_T offset, end; + int32 k, want_i, backup; char sum2[SUM_LENGTH]; uint32 s1, s2, sum; int more; @@ -163,13 +159,16 @@ static void hash_search(int f,struct sum_struct *s, int done_csum2 = 0; int32 i; - if (verbose > 4) - rprintf(FINFO,"offset=%.0f sum=%08x\n",(double)offset,sum); + if (verbose > 4) { + rprintf(FINFO, "offset=%.0f sum=%04x%04x\n", + (double)offset, s2 & 0xFFFF, s1 & 0xFFFF); + } - i = hash_table[SUM2HASH(sum)]; + i = hash_table[SUM2HASH2(s1,s2)]; if (i < 0) goto null_hash; + sum = (s1 & 0xffff) | (s2 << 16); hash_hits++; do { int32 l; @@ -254,7 +253,7 @@ static void hash_search(int f,struct sum_struct *s, } while ((i = s->sums[i].chain) >= 0); null_hash: - backup = offset - last_match; + backup = (int32)(offset - last_match); /* We sometimes read 1 byte prior to last_match... */ if (backup < 0) backup = 0; @@ -272,7 +271,6 @@ static void hash_search(int f,struct sum_struct *s, s2 += s1; } else --k; - sum = (s1 & 0xffff) | (s2 << 16); /* By matching early we avoid re-reading the data 3 times in the case where a token @@ -305,7 +303,8 @@ 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[MD4_SUM_LENGTH]; + char file_sum[MAX_DIGEST_LEN]; + int sum_len; last_match = 0; false_alarms = 0; @@ -315,7 +314,7 @@ void match_sums(int f, struct sum_struct *s, struct map_struct *buf, OFF_T len) sum_init(checksum_seed); - if (append_mode) { + if (append_mode > 0) { OFF_T j = 0; for (j = CHUNK_SIZE; j < s->flength; j += CHUNK_SIZE) { if (buf && do_progress) @@ -325,10 +324,10 @@ void match_sums(int f, struct sum_struct *s, struct map_struct *buf, OFF_T len) last_match = j; } if (last_match < s->flength) { - int32 len = s->flength - last_match; + int32 n = (int32)(s->flength - last_match); if (buf && do_progress) show_progress(last_match, buf->file_size); - sum_update(map_ptr(buf, last_match, len), len); + sum_update(map_ptr(buf, last_match, n), n); last_match = s->flength; } s->count = 0; @@ -340,7 +339,7 @@ void match_sums(int f, struct sum_struct *s, struct map_struct *buf, OFF_T len) if (verbose > 2) rprintf(FINFO,"built hash table\n"); - hash_search(f,s,buf,len); + hash_search(f, s, buf, len); if (verbose > 2) rprintf(FINFO,"done hash search\n"); @@ -352,14 +351,14 @@ void match_sums(int f, struct sum_struct *s, struct map_struct *buf, OFF_T len) matched(f, s, buf, len, -1); } - sum_end(file_sum); + 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 (verbose > 2) rprintf(FINFO,"sending file_sum\n"); - write_buf(f,file_sum,MD4_SUM_LENGTH); + write_buf(f, file_sum, sum_len); if (verbose > 2) rprintf(FINFO, "false_alarms=%d hash_hits=%d matches=%d\n",