home *** CD-ROM | disk | FTP | other *** search
/ OS/2 Shareware BBS: 35 Internet / 35-Internet.zip / rsync221.zip / match.c < prev    next >
C/C++ Source or Header  |  1999-03-04  |  7KB  |  303 lines
  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 (-1)
  33.  
  34. static int false_alarms;
  35. static int tag_hits;
  36. static int matches;
  37. static int64 data_transfer;
  38.  
  39. static int total_false_alarms;
  40. static int total_tag_hits;
  41. static int total_matches;
  42.  
  43. extern struct stats stats;
  44.  
  45. struct target {
  46.   tag t;
  47.   int i;
  48. };
  49.  
  50. static struct target *targets;
  51.  
  52. static int *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 = (int *)malloc(sizeof(tag_table[0])*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.     OFF_T 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 (i >= 0) {
  107.         stats.matched_data += s->sums[i].len;
  108.         n += s->sums[i].len;
  109.     }
  110.   
  111.     for (j=0;j<n;j+=CHUNK_SIZE) {
  112.         int n1 = MIN(CHUNK_SIZE,n-j);
  113.         sum_update(map_ptr(buf,last_match+j,n1),n1);
  114.     }
  115.  
  116.  
  117.     if (i >= 0)
  118.         last_match = offset + s->sums[i].len;
  119.     else
  120.         last_match = offset;
  121.  
  122.     if (buf)
  123.         show_progress(last_match, buf->size);
  124.  
  125.     if (i == -1) end_progress();
  126. }
  127.  
  128.  
  129. static void hash_search(int f,struct sum_struct *s,
  130.             struct map_struct *buf,OFF_T len)
  131. {
  132.     OFF_T offset;
  133.     int j,k;
  134.     int end;
  135.     char sum2[SUM_LENGTH];
  136.     uint32 s1, s2, sum; 
  137.     schar *map;
  138.  
  139.     if (verbose > 2)
  140.         rprintf(FINFO,"hash search b=%d len=%d\n",s->n,(int)len);
  141.  
  142.     k = MIN(len, s->n);
  143.     
  144.     map = (schar *)map_ptr(buf,0,k);
  145.     
  146.     sum = get_checksum1((char *)map, k);
  147.     s1 = sum & 0xFFFF;
  148.     s2 = sum >> 16;
  149.     if (verbose > 3)
  150.         rprintf(FINFO, "sum=%.8x k=%d\n", sum, k);
  151.     
  152.     offset = 0;
  153.     
  154.     end = len + 1 - s->sums[s->count-1].len;
  155.     
  156.     if (verbose > 3)
  157.         rprintf(FINFO,"hash search s->n=%d len=%d count=%d\n",
  158.             s->n,(int)len,s->count);
  159.     
  160.     do {
  161.         tag t = gettag2(s1,s2);
  162.         int done_csum2 = 0;
  163.             
  164.         j = tag_table[t];
  165.         if (verbose > 4)
  166.             rprintf(FINFO,"offset=%d sum=%08x\n",(int)offset,sum);
  167.         
  168.         if (j == NULL_TAG) {
  169.             goto null_tag;
  170.         }
  171.  
  172.         sum = (s1 & 0xffff) | (s2 << 16);
  173.         tag_hits++;
  174.         for (; j<s->count && targets[j].t == t; j++) {
  175.             int i = targets[j].i;
  176.             
  177.             if (sum != s->sums[i].sum1) continue;
  178.             
  179.             if (verbose > 3)
  180.                 rprintf(FINFO,"potential match at %d target=%d %d sum=%08x\n",
  181.                     (int)offset,j,i,sum);
  182.             
  183.             if (!done_csum2) {
  184.                 int l = MIN(s->n,len-offset);
  185.                 map = (schar *)map_ptr(buf,offset,l);
  186.                 get_checksum2((char *)map,l,sum2);
  187.                 done_csum2 = 1;
  188.             }
  189.             
  190.             if (memcmp(sum2,s->sums[i].sum2,csum_length) != 0) {
  191.                 false_alarms++;
  192.                 continue;
  193.             }
  194.             
  195.             matched(f,s,buf,offset,i);
  196.             offset += s->sums[i].len - 1;
  197.             k = MIN((len-offset), s->n);
  198.             map = (schar *)map_ptr(buf,offset,k);
  199.             sum = get_checksum1((char *)map, k);
  200.             s1 = sum & 0xFFFF;
  201.             s2 = sum >> 16;
  202.             matches++;
  203.             break;
  204.         }
  205.         
  206.     null_tag:
  207.         /* Trim off the first byte from the checksum */
  208.         map = (schar *)map_ptr(buf,offset,k+1);
  209.         s1 -= map[0] + CHAR_OFFSET;
  210.         s2 -= k * (map[0]+CHAR_OFFSET);
  211.         
  212.         /* Add on the next byte (if there is one) to the checksum */
  213.         if (k < (len-offset)) {
  214.             s1 += (map[k]+CHAR_OFFSET);
  215.             s2 += s1;
  216.         } else {
  217.             --k;
  218.         }
  219.  
  220.         /* By matching early we avoid re-reading the
  221.            data 3 times in the case where a token
  222.            match comes a long way after last
  223.            match. The 3 reads are caused by the
  224.            running match, the checksum update and the
  225.            literal send. */
  226.         if (offset-last_match >= CHUNK_SIZE+s->n && 
  227.             (end-offset > CHUNK_SIZE)) {
  228.             matched(f,s,buf,offset - s->n, -2);
  229.         }
  230.     } while (++offset < end);
  231.     
  232.     matched(f,s,buf,len,-1);
  233.     map_ptr(buf,len-1,1);
  234. }
  235.  
  236.  
  237. void match_sums(int f,struct sum_struct *s,struct map_struct *buf,OFF_T len)
  238. {
  239.     char file_sum[MD4_SUM_LENGTH];
  240.  
  241.     last_match = 0;
  242.     false_alarms = 0;
  243.     tag_hits = 0;
  244.     matches=0;
  245.     data_transfer=0;
  246.  
  247.     sum_init();
  248.  
  249.     if (len > 0 && s->count>0) {
  250.         build_hash_table(s);
  251.         
  252.         if (verbose > 2) 
  253.             rprintf(FINFO,"built hash table\n");
  254.         
  255.         hash_search(f,s,buf,len);
  256.         
  257.         if (verbose > 2) 
  258.             rprintf(FINFO,"done hash search\n");
  259.     } else {
  260.         OFF_T j;
  261.         /* by doing this in pieces we avoid too many seeks */
  262.         for (j=0;j<(len-CHUNK_SIZE);j+=CHUNK_SIZE) {
  263.             int n1 = MIN(CHUNK_SIZE,(len-CHUNK_SIZE)-j);
  264.             matched(f,s,buf,j+n1,-2);
  265.         }
  266.         matched(f,s,buf,len,-1);
  267.     }
  268.  
  269.     sum_end(file_sum);
  270.  
  271.     if (remote_version >= 14) {
  272.         if (verbose > 2)
  273.             rprintf(FINFO,"sending file_sum\n");
  274.         write_buf(f,file_sum,MD4_SUM_LENGTH);
  275.     }
  276.  
  277.     if (targets) {
  278.         free(targets);
  279.         targets=NULL;
  280.     }
  281.     
  282.     if (verbose > 2)
  283.         rprintf(FINFO, "false_alarms=%d tag_hits=%d matches=%d\n",
  284.             false_alarms, tag_hits, matches);
  285.     
  286.     total_tag_hits += tag_hits;
  287.     total_false_alarms += false_alarms;
  288.     total_matches += matches;
  289.     stats.literal_data += data_transfer;
  290. }
  291.  
  292. void match_report(void)
  293. {
  294.     if (verbose <= 1)
  295.         return;
  296.  
  297.     rprintf(FINFO,
  298.         "total: matches=%d  tag_hits=%d  false_alarms=%d data=%.0f\n",
  299.         total_matches,total_tag_hits,
  300.         total_false_alarms,
  301.         (double)stats.literal_data);
  302. }
  303.