$treeview $search $mathjax $extrastylesheet
librsync
2.0.2
$projectbrief
|
$projectbrief
|
$searchbox |
00001 /*= -*- c-basic-offset: 4; indent-tabs-mode: nil; -*- 00002 * 00003 * librsync -- library for network deltas 00004 * 00005 * Copyright (C) 1999, 2000, 2001 by Martin Pool <mbp@sourcefrog.net> 00006 * Copyright (C) 1999 by Andrew Tridgell 00007 * 00008 * This program is free software; you can redistribute it and/or modify 00009 * it under the terms of the GNU Lesser General Public License as published by 00010 * the Free Software Foundation; either version 2.1 of the License, or 00011 * (at your option) any later version. 00012 * 00013 * This program is distributed in the hope that it will be useful, 00014 * but WITHOUT ANY WARRANTY; without even the implied warranty of 00015 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 00016 * GNU Lesser General Public License for more details. 00017 * 00018 * You should have received a copy of the GNU Lesser General Public License 00019 * along with this program; if not, write to the Free Software 00020 * Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA. 00021 */ 00022 00023 #include "config.h" 00024 00025 #include <assert.h> 00026 #include <stddef.h> 00027 #include <stdlib.h> 00028 #include <stdio.h> 00029 #include <string.h> 00030 00031 #include "librsync.h" 00032 #include "sumset.h" 00033 #include "util.h" 00034 #include "trace.h" 00035 00036 const int RS_MD4_SUM_LENGTH = 16; 00037 const int RS_BLAKE2_SUM_LENGTH = 32; 00038 00039 static void rs_block_sig_init(rs_block_sig_t *sig, rs_weak_sum_t weak_sum, 00040 rs_strong_sum_t *strong_sum, int strong_len) 00041 { 00042 sig->weak_sum = weak_sum; 00043 if (strong_sum) 00044 memcpy(sig->strong_sum, strong_sum, strong_len); 00045 } 00046 00047 static inline unsigned rs_block_sig_hash(const rs_block_sig_t *sig) 00048 { 00049 return (unsigned)sig->weak_sum; 00050 } 00051 00052 typedef struct rs_block_match { 00053 rs_block_sig_t block_sig; 00054 rs_signature_t *signature; 00055 const void *buf; 00056 size_t len; 00057 } rs_block_match_t; 00058 00059 static void rs_block_match_init(rs_block_match_t *match, rs_signature_t *sig, 00060 rs_weak_sum_t weak_sum, 00061 rs_strong_sum_t *strong_sum, const void *buf, 00062 size_t len) 00063 { 00064 rs_block_sig_init(&match->block_sig, weak_sum, strong_sum, 00065 sig->strong_sum_len); 00066 match->signature = sig; 00067 match->buf = buf; 00068 match->len = len; 00069 } 00070 00071 static inline int rs_block_match_cmp(rs_block_match_t *match, 00072 const rs_block_sig_t *block_sig) 00073 { 00074 /* If buf is not NULL, the strong sum is yet to be calculated. */ 00075 if (match->buf) { 00076 #ifndef HASHTABLE_NSTATS 00077 match->signature->calc_strong_count++; 00078 #endif 00079 rs_signature_calc_strong_sum(match->signature, match->buf, match->len, 00080 &(match->block_sig.strong_sum)); 00081 match->buf = NULL; 00082 } 00083 return memcmp(&match->block_sig.strong_sum, &block_sig->strong_sum, 00084 match->signature->strong_sum_len); 00085 } 00086 00087 /* Instantiate hashtable for rs_block_sig and rs_block_match. */ 00088 #define ENTRY rs_block_sig 00089 #define MATCH rs_block_match 00090 #define NAME hashtable 00091 #include "hashtable.h" 00092 00093 /* Get the size of a packed rs_block_sig_t. */ 00094 static inline size_t rs_block_sig_size(const rs_signature_t *sig) 00095 { 00096 /* Round up to next multiple of sizeof(weak_sum) to align memory correctly. 00097 */ 00098 return offsetof(rs_block_sig_t, 00099 strong_sum) + ((sig->strong_sum_len + 00100 sizeof(rs_weak_sum_t)- 00101 1) / sizeof(rs_weak_sum_t)) * 00102 sizeof(rs_weak_sum_t); 00103 } 00104 00105 /* Get the pointer to the block_sig_t from a block index. */ 00106 static inline rs_block_sig_t *rs_block_sig_ptr(const rs_signature_t *sig, 00107 int block_idx) 00108 { 00109 return (rs_block_sig_t *)((char *)sig->block_sigs + 00110 block_idx * rs_block_sig_size(sig)); 00111 } 00112 00113 /* Get the index of a block from a block_sig_t pointer. */ 00114 static inline int rs_block_sig_idx(const rs_signature_t *sig, 00115 rs_block_sig_t *block_sig) 00116 { 00117 return ((char *)block_sig - 00118 (char *)sig->block_sigs) / rs_block_sig_size(sig); 00119 } 00120 00121 rs_result rs_signature_init(rs_signature_t *sig, int magic, int block_len, 00122 int strong_len, rs_long_t sig_fsize) 00123 { 00124 int max_strong_len; 00125 00126 /* Check and set default arguments. */ 00127 magic = magic ? magic : RS_BLAKE2_SIG_MAGIC; 00128 switch (magic) { 00129 case RS_BLAKE2_SIG_MAGIC: 00130 max_strong_len = RS_BLAKE2_SUM_LENGTH; 00131 break; 00132 case RS_MD4_SIG_MAGIC: 00133 max_strong_len = RS_MD4_SUM_LENGTH; 00134 break; 00135 default: 00136 rs_error("invalid magic %#x", magic); 00137 return RS_BAD_MAGIC; 00138 } 00139 strong_len = strong_len ? strong_len : max_strong_len; 00140 if (strong_len < 1 || max_strong_len < strong_len) { 00141 rs_error("invalid strong_sum_len %d for magic %#x", strong_len, magic); 00142 return RS_PARAM_ERROR; 00143 } 00144 /* Set attributes from args. */ 00145 sig->magic = magic; 00146 sig->block_len = block_len; 00147 sig->strong_sum_len = strong_len; 00148 sig->count = 0; 00149 /* Calculate the number of blocks if we have the signature file size. */ 00150 /* Magic+header is 12 bytes, each block thereafter is 4 bytes 00151 weak_sum+strong_sum_len bytes */ 00152 sig->size = (int)(sig_fsize ? (sig_fsize - 12) / (4 + strong_len) : 0); 00153 if (sig->size) 00154 sig->block_sigs = 00155 rs_alloc(sig->size * rs_block_sig_size(sig), 00156 "signature->block_sigs"); 00157 else 00158 sig->block_sigs = NULL; 00159 sig->hashtable = NULL; 00160 #ifndef HASHTABLE_NSTATS 00161 sig->calc_strong_count = 0; 00162 #endif 00163 rs_signature_check(sig); 00164 return RS_DONE; 00165 } 00166 00167 void rs_signature_done(rs_signature_t *sig) 00168 { 00169 hashtable_free(sig->hashtable); 00170 rs_bzero(sig, sizeof(*sig)); 00171 } 00172 00173 rs_block_sig_t *rs_signature_add_block(rs_signature_t *sig, 00174 rs_weak_sum_t weak_sum, 00175 rs_strong_sum_t *strong_sum) 00176 { 00177 rs_signature_check(sig); 00178 /* If block_sigs is full, allocate more space. */ 00179 if (sig->count == sig->size) { 00180 sig->size = sig->size ? sig->size * 2 : 16; 00181 sig->block_sigs = 00182 rs_realloc(sig->block_sigs, sig->size * rs_block_sig_size(sig), 00183 "signature->block_sigs"); 00184 } 00185 rs_block_sig_t *b = rs_block_sig_ptr(sig, sig->count++); 00186 rs_block_sig_init(b, weak_sum, strong_sum, sig->strong_sum_len); 00187 return b; 00188 } 00189 00190 rs_long_t rs_signature_find_match(rs_signature_t *sig, rs_weak_sum_t weak_sum, 00191 void const *buf, size_t len) 00192 { 00193 rs_block_match_t m; 00194 rs_block_sig_t *b; 00195 00196 rs_signature_check(sig); 00197 rs_block_match_init(&m, sig, weak_sum, NULL, buf, len); 00198 if ((b = hashtable_find(sig->hashtable, &m))) { 00199 return (rs_long_t)rs_block_sig_idx(sig, b) * sig->block_len; 00200 } 00201 return -1; 00202 } 00203 00204 void rs_signature_log_stats(rs_signature_t const *sig) 00205 { 00206 #ifndef HASHTABLE_NSTATS 00207 hashtable_t *t = sig->hashtable; 00208 00209 rs_log(RS_LOG_INFO | RS_LOG_NONAME, 00210 "match statistics: signature[%ld searches, %ld (%.3f%%) matches, " 00211 "%ld (%.3fx) weak sum compares, %ld (%.3f%%) strong sum compares, " 00212 "%ld (%.3f%%) strong sum calcs]", t->find_count, t->match_count, 00213 100.0 * (double)t->match_count / t->find_count, t->hashcmp_count, 00214 (double)t->hashcmp_count / t->find_count, t->entrycmp_count, 00215 100.0 * (double)t->entrycmp_count / t->find_count, 00216 sig->calc_strong_count, 00217 100.0 * (double)sig->calc_strong_count / t->find_count); 00218 #endif 00219 } 00220 00221 rs_result rs_build_hash_table(rs_signature_t *sig) 00222 { 00223 rs_block_match_t m; 00224 rs_block_sig_t *b; 00225 int i; 00226 00227 rs_signature_check(sig); 00228 sig->hashtable = hashtable_new(sig->count); 00229 if (!sig->hashtable) 00230 return RS_MEM_ERROR; 00231 for (i = 0; i < sig->count; i++) { 00232 b = rs_block_sig_ptr(sig, i); 00233 rs_block_match_init(&m, sig, b->weak_sum, &b->strong_sum, NULL, 0); 00234 if (!hashtable_find(sig->hashtable, &m)) 00235 hashtable_add(sig->hashtable, b); 00236 } 00237 hashtable_stats_init(sig->hashtable); 00238 return RS_DONE; 00239 } 00240 00241 void rs_free_sumset(rs_signature_t *psums) 00242 { 00243 rs_signature_done(psums); 00244 free(psums); 00245 } 00246 00247 void rs_sumset_dump(rs_signature_t const *sums) 00248 { 00249 int i; 00250 rs_block_sig_t *b; 00251 char strong_hex[RS_MAX_STRONG_SUM_LENGTH * 3]; 00252 00253 rs_log(RS_LOG_INFO | RS_LOG_NONAME, 00254 "sumset info: magic=%#x, block_len=%d, block_num=%d", sums->magic, 00255 sums->block_len, sums->count); 00256 00257 for (i = 0; i < sums->count; i++) { 00258 b = rs_block_sig_ptr(sums, i); 00259 rs_hexify(strong_hex, b->strong_sum, sums->strong_sum_len); 00260 rs_log(RS_LOG_INFO | RS_LOG_NONAME, 00261 "sum %6d: weak=" FMT_WEAKSUM ", strong=%s", i, b->weak_sum, 00262 strong_hex); 00263 } 00264 }