home *** CD-ROM | disk | FTP | other *** search
/ Big Green CD 8 / BGCD_8_Dev.iso / OPENSTEP / UNIX / Utilities / rsync-1.6.3-MIH / src / match.c < prev    next >
Encoding:
C/C++ Source or Header  |  1997-04-11  |  5.9 KB  |  279 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 ((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=0;
  40. static int total_tag_hits=0;
  41. static int total_matches=0;
  42. static int total_data_transfer=0;
  43.  
  44.  
  45. struct target {
  46.   tag t;
  47.   int i;
  48. };
  49.  
  50. static struct target *targets=NULL;
  51.  
  52. static tag *tag_table = NULL;
  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(t1->t - 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 len,
  95.             int offset,int i)
  96. {
  97.   int n = offset - last_match;
  98.   int j;
  99.  
  100.   if (verbose > 2)
  101.     if (i != -1)
  102.       fprintf(FERROR,"match at %d last_match=%d j=%d len=%d n=%d\n",
  103.           (int)offset,(int)last_match,i,(int)s->sums[i].len,n);
  104.  
  105.   send_token(f,i,buf,last_match,n,i==-1?0:s->sums[i].len);
  106.   data_transfer += n;
  107.  
  108.   if (n > 0)
  109.     write_flush(f);
  110.  
  111.   if (i != -1)
  112.     n += s->sums[i].len;
  113.   
  114.   for (j=0;j<n;j+=CHUNK_SIZE) {
  115.     int n1 = MIN(CHUNK_SIZE,n-j);
  116.     sum_update(map_ptr(buf,last_match+j,n1),n1);
  117.   }
  118.  
  119.  
  120.   if (i != -1)
  121.     last_match = offset + s->sums[i].len;
  122.  
  123. }
  124.  
  125.  
  126. static void hash_search(int f,struct sum_struct *s,
  127.             struct map_struct *buf,off_t len)
  128. {
  129.   int offset,j,k;
  130.   int end;
  131.   char sum2[SUM_LENGTH];
  132.   uint32 s1, s2, sum; 
  133.   char *map;
  134.  
  135.   if (verbose > 2)
  136.     fprintf(FERROR,"hash search b=%d len=%d\n",s->n,(int)len);
  137.  
  138.   k = MIN(len, s->n);
  139.  
  140.   map = map_ptr(buf,0,k);
  141.  
  142.   sum = get_checksum1(map, k);
  143.   s1 = sum & 0xFFFF;
  144.   s2 = sum >> 16;
  145.   if (verbose > 3)
  146.     fprintf(FERROR, "sum=%.8x k=%d\n", sum, k);
  147.  
  148.   offset = 0;
  149.  
  150.   end = len + 1 - s->sums[s->count-1].len;
  151.  
  152.   if (verbose > 3)
  153.     fprintf(FERROR,"hash search s->n=%d len=%d count=%d\n",
  154.         s->n,(int)len,s->count);
  155.  
  156.   do {
  157.     tag t = gettag2(s1,s2);
  158.     j = tag_table[t];
  159.     if (verbose > 4)
  160.       fprintf(FERROR,"offset=%d sum=%08x\n",
  161.           offset,sum);
  162.  
  163.     if (j != NULL_TAG) {
  164.       int done_csum2 = 0;
  165.  
  166.       sum = (s1 & 0xffff) | (s2 << 16);
  167.       tag_hits++;
  168.       do {
  169.     int i = targets[j].i;
  170.  
  171.     if (sum == s->sums[i].sum1) {
  172.       if (verbose > 3)
  173.         fprintf(FERROR,"potential match at %d target=%d %d sum=%08x\n",
  174.             offset,j,i,sum);
  175.  
  176.       if (!done_csum2) {
  177.         int l = MIN(s->n,len-offset);
  178.         map = map_ptr(buf,offset,l);
  179.         get_checksum2(map,l,sum2);
  180.         done_csum2 = 1;
  181.       }
  182.       if (memcmp(sum2,s->sums[i].sum2,csum_length) == 0) {
  183.         matched(f,s,buf,len,offset,i);
  184.         offset += s->sums[i].len - 1;
  185.         k = MIN((len-offset), s->n);
  186.         map = map_ptr(buf,offset,k);
  187.         sum = get_checksum1(map, k);
  188.         s1 = sum & 0xFFFF;
  189.         s2 = sum >> 16;
  190.         ++matches;
  191.         break;
  192.       } else {
  193.         false_alarms++;
  194.       }
  195.     }
  196.     j++;
  197.       } while (j<s->count && targets[j].t == t);
  198.     }
  199.  
  200.     /* Trim off the first byte from the checksum */
  201.     map = map_ptr(buf,offset,k+1);
  202.     s1 -= map[0] + CHAR_OFFSET;
  203.     s2 -= k * (map[0]+CHAR_OFFSET);
  204.  
  205.     /* Add on the next byte (if there is one) to the checksum */
  206.     if (k < (len-offset)) {
  207.       s1 += (map[k]+CHAR_OFFSET);
  208.       s2 += s1;
  209.     } else {
  210.       --k;
  211.     }
  212.  
  213.   } while (++offset < end);
  214.  
  215.   matched(f,s,buf,len,len,-1);
  216.   map_ptr(buf,len-1,1);
  217. }
  218.  
  219.  
  220. void match_sums(int f,struct sum_struct *s,struct map_struct *buf,off_t len)
  221. {
  222.   char file_sum[MD4_SUM_LENGTH];
  223.  
  224.   last_match = 0;
  225.   false_alarms = 0;
  226.   tag_hits = 0;
  227.   matches=0;
  228.   data_transfer=0;
  229.  
  230.   sum_init();
  231.  
  232.   if (len > 0 && s->count>0) {
  233.     build_hash_table(s);
  234.  
  235.     if (verbose > 2) 
  236.       fprintf(FERROR,"built hash table\n");
  237.  
  238.     hash_search(f,s,buf,len);
  239.  
  240.     if (verbose > 2) 
  241.       fprintf(FERROR,"done hash search\n");
  242.   } else {
  243.     matched(f,s,buf,len,len,-1);
  244.   }
  245.  
  246.   sum_end(file_sum);
  247.  
  248.   if (remote_version >= 14) {
  249.     if (verbose > 2)
  250.       fprintf(FERROR,"sending file_sum\n");
  251.     write_buf(f,file_sum,MD4_SUM_LENGTH);
  252.   }
  253.  
  254.   if (targets) {
  255.     free(targets);
  256.     targets=NULL;
  257.   }
  258.  
  259.   if (verbose > 2)
  260.     fprintf(FERROR, "false_alarms=%d tag_hits=%d matches=%d\n",
  261.         false_alarms, tag_hits, matches);
  262.  
  263.   total_tag_hits += tag_hits;
  264.   total_false_alarms += false_alarms;
  265.   total_matches += matches;
  266.   total_data_transfer += data_transfer;
  267. }
  268.  
  269. void match_report(void)
  270. {
  271.   if (verbose <= 1)
  272.     return;
  273.  
  274.   fprintf(FINFO,
  275.       "total: matches=%d  tag_hits=%d  false_alarms=%d  data=%d\n",
  276.       total_matches,total_tag_hits,
  277.       total_false_alarms,total_data_transfer);
  278. }
  279.