this fixes two problems:
[rsync.git] / match.c
1 /* 
2    Copyright (C) Andrew Tridgell 1996
3    Copyright (C) Paul Mackerras 1996
4    
5    This program is free software; you can redistribute it and/or modify
6    it under the terms of the GNU General Public License as published by
7    the Free Software Foundation; either version 2 of the License, or
8    (at your option) any later version.
9    
10    This program is distributed in the hope that it will be useful,
11    but WITHOUT ANY WARRANTY; without even the implied warranty of
12    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
13    GNU General Public License for more details.
14    
15    You should have received a copy of the GNU General Public License
16    along with this program; if not, write to the Free Software
17    Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
18 */
19
20 #include "rsync.h"
21
22 extern int csum_length;
23
24 extern int verbose;
25 extern int am_server;
26
27 extern int remote_version;
28
29 typedef unsigned short tag;
30
31 #define TABLESIZE (1<<16)
32 #define NULL_TAG ((tag)-1)
33
34 static int false_alarms;
35 static int tag_hits;
36 static int matches;
37 static int data_transfer;
38
39 static int total_false_alarms;
40 static int total_tag_hits;
41 static int total_matches;
42 static int64 total_data_transfer;
43
44
45 struct target {
46   tag t;
47   int i;
48 };
49
50 static struct target *targets;
51
52 static tag *tag_table;
53
54 #define gettag2(s1,s2) (((s1) + (s2)) & 0xFFFF)
55 #define gettag(sum) gettag2((sum)&0xFFFF,(sum)>>16)
56
57 static int compare_targets(struct target *t1,struct target *t2)
58 {
59   return((int)t1->t - (int)t2->t);
60 }
61
62
63 static void build_hash_table(struct sum_struct *s)
64 {
65   int i;
66
67   if (!tag_table)
68     tag_table = (tag *)malloc(sizeof(tag)*TABLESIZE);
69
70   targets = (struct target *)malloc(sizeof(targets[0])*s->count);
71   if (!tag_table || !targets) 
72     out_of_memory("build_hash_table");
73
74   for (i=0;i<s->count;i++) {
75     targets[i].i = i;
76     targets[i].t = gettag(s->sums[i].sum1);
77   }
78
79   qsort(targets,s->count,sizeof(targets[0]),(int (*)())compare_targets);
80
81   for (i=0;i<TABLESIZE;i++)
82     tag_table[i] = NULL_TAG;
83
84   for (i=s->count-1;i>=0;i--) {    
85     tag_table[targets[i].t] = i;
86   }
87 }
88
89
90 static OFF_T last_match;
91
92
93 static void matched(int f,struct sum_struct *s,struct map_struct *buf,
94                     OFF_T offset,int i)
95 {
96         OFF_T n = offset - last_match;
97         int j;
98
99         if (verbose > 2 && i >= 0)
100                 rprintf(FINFO,"match at %d last_match=%d j=%d len=%d n=%d\n",
101                         (int)offset,(int)last_match,i,(int)s->sums[i].len,(int)n);
102
103         send_token(f,i,buf,last_match,n,i<0?0:s->sums[i].len);
104         data_transfer += n;
105
106         if (n > 0)
107                 write_flush(f);
108
109         if (i >= 0)
110                 n += s->sums[i].len;
111   
112         for (j=0;j<n;j+=CHUNK_SIZE) {
113                 int n1 = MIN(CHUNK_SIZE,n-j);
114                 sum_update(map_ptr(buf,last_match+j,n1),n1);
115         }
116
117
118         if (i >= 0)
119                 last_match = offset + s->sums[i].len;
120         else
121                 last_match = offset;
122 }
123
124
125 static void hash_search(int f,struct sum_struct *s,
126                         struct map_struct *buf,OFF_T len)
127 {
128         OFF_T offset;
129         int j,k;
130         int end;
131         char sum2[SUM_LENGTH];
132         uint32 s1, s2, sum; 
133         schar *map;
134         extern int do_compression;
135
136         if (verbose > 2)
137                 rprintf(FINFO,"hash search b=%d len=%d\n",s->n,(int)len);
138
139         k = MIN(len, s->n);
140         
141         map = (schar *)map_ptr(buf,0,k);
142         
143         sum = get_checksum1((char *)map, k);
144         s1 = sum & 0xFFFF;
145         s2 = sum >> 16;
146         if (verbose > 3)
147                 rprintf(FINFO, "sum=%.8x k=%d\n", sum, k);
148         
149         offset = 0;
150         
151         end = len + 1 - s->sums[s->count-1].len;
152         
153         if (verbose > 3)
154                 rprintf(FINFO,"hash search s->n=%d len=%d count=%d\n",
155                         s->n,(int)len,s->count);
156         
157         do {
158                 tag t = gettag2(s1,s2);
159                 int done_csum2 = 0;
160                         
161                 j = tag_table[t];
162                 if (verbose > 4)
163                         rprintf(FINFO,"offset=%d sum=%08x\n",(int)offset,sum);
164                 
165                 if (j == NULL_TAG) {
166                         goto null_tag;
167                 }
168
169                 sum = (s1 & 0xffff) | (s2 << 16);
170                 tag_hits++;
171                 for (; j<s->count && targets[j].t == t; j++) {
172                         int i = targets[j].i;
173                         
174                         if (sum != s->sums[i].sum1) continue;
175                         
176                         if (verbose > 3)
177                                 rprintf(FINFO,"potential match at %d target=%d %d sum=%08x\n",
178                                         (int)offset,j,i,sum);
179                         
180                         if (!done_csum2) {
181                                 int l = MIN(s->n,len-offset);
182                                 map = (schar *)map_ptr(buf,offset,l);
183                                 get_checksum2((char *)map,l,sum2);
184                                 done_csum2 = 1;
185                         }
186                         
187                         if (memcmp(sum2,s->sums[i].sum2,csum_length) != 0) {
188                                 false_alarms++;
189                                 continue;
190                         }
191                         
192                         matched(f,s,buf,offset,i);
193                         offset += s->sums[i].len - 1;
194                         k = MIN((len-offset), s->n);
195                         map = (schar *)map_ptr(buf,offset,k);
196                         sum = get_checksum1((char *)map, k);
197                         s1 = sum & 0xFFFF;
198                         s2 = sum >> 16;
199                         matches++;
200                         break;
201                 }
202                 
203         null_tag:
204                 /* Trim off the first byte from the checksum */
205                 map = (schar *)map_ptr(buf,offset,k+1);
206                 s1 -= map[0] + CHAR_OFFSET;
207                 s2 -= k * (map[0]+CHAR_OFFSET);
208                 
209                 /* Add on the next byte (if there is one) to the checksum */
210                 if (k < (len-offset)) {
211                         s1 += (map[k]+CHAR_OFFSET);
212                         s2 += s1;
213                 } else {
214                         --k;
215                 }
216
217                 if (!do_compression) {
218                         /* By matching early we avoid re-reading the
219                            data 3 times in the case where a token
220                            match comes a long way after last
221                            match. The 3 reads are caused by the
222                            running match, the checksum update and the
223                            literal send.
224
225                            we don't enable this for the compressed
226                            case yet as the deflated token code can't
227                            handle it. Paul is working on it */
228                         if (offset-last_match >= CHUNK_SIZE+s->n && 
229                             (end-offset > CHUNK_SIZE)) {
230                                 matched(f,s,buf,offset - s->n, -2);
231                         }
232                 }
233         } while (++offset < end);
234         
235         matched(f,s,buf,len,-1);
236         map_ptr(buf,len-1,1);
237 }
238
239
240 void match_sums(int f,struct sum_struct *s,struct map_struct *buf,OFF_T len)
241 {
242         char file_sum[MD4_SUM_LENGTH];
243
244         last_match = 0;
245         false_alarms = 0;
246         tag_hits = 0;
247         matches=0;
248         data_transfer=0;
249
250         sum_init();
251
252         if (len > 0 && s->count>0) {
253                 build_hash_table(s);
254                 
255                 if (verbose > 2) 
256                         rprintf(FINFO,"built hash table\n");
257                 
258                 hash_search(f,s,buf,len);
259                 
260                 if (verbose > 2) 
261                         rprintf(FINFO,"done hash search\n");
262         } else {
263                 matched(f,s,buf,len,-1);
264         }
265
266         sum_end(file_sum);
267
268         if (remote_version >= 14) {
269                 if (verbose > 2)
270                         rprintf(FINFO,"sending file_sum\n");
271                 write_buf(f,file_sum,MD4_SUM_LENGTH);
272         }
273
274         if (targets) {
275                 free(targets);
276                 targets=NULL;
277         }
278         
279         if (verbose > 2)
280                 rprintf(FINFO, "false_alarms=%d tag_hits=%d matches=%d\n",
281                         false_alarms, tag_hits, matches);
282         
283         total_tag_hits += tag_hits;
284         total_false_alarms += false_alarms;
285         total_matches += matches;
286         total_data_transfer += data_transfer;
287 }
288
289 void match_report(void)
290 {
291         if (verbose <= 1)
292                 return;
293
294         rprintf(FINFO,
295                 "total: matches=%d  tag_hits=%d  false_alarms=%d  data=%ld\n",
296                 total_matches,total_tag_hits,
297                 total_false_alarms,(long)total_data_transfer);
298 }