tools/dsync-0.0/libdsync/rsync-algo.cc

   1 // -*- mode: cpp; mode: fold -*-
   2 // Description                                                          /*{{{*/
   3 // $Id: rsync-algo.cc,v 1.3 1999/12/26 06:59:01 jgg Exp $
   4 /* ######################################################################
   5
   6    RSync Algorithrim
   7
   8    The RSync algorithim is attributed to Andrew Tridgell and is a means
   9    for matching blocks between two streams.  The algorithrim implemented
  10    here differs slightly in its structure and is carefully optimized to be
  11    able to operate on very large files effectively.
  12
  13    We rely on the RSync rolling weak checksum routine and the MD4 strong
  14    checksum routine. This implementation requires a uniform block size
  15    for each run.
  16
  17    ##################################################################### */
  18                                                                         /*}}}*/
  19 // Include files                                                        /*{{{*/
  20 #ifdef __GNUG__
  21 #pragma implementation "dsync/rsync-algo.h"
  22 #endif
  23
  24 #include <dsync/rsync-algo.h>
  25 #include <dsync/error.h>
  26 #include <dsync/slidingwindow.h>
  27 #include <dsync/md5.h>
  28 #include <dsync/md4.h>
  29
  30 #include <stdio.h>
  31 #include <inttypes.h>
  32 #include <netinet/in.h>
  33                                                                         /*}}}*/
  34
  35 // RollingChecksum - Compute the checksum perscribed by rsync           /*{{{*/
  36 // ---------------------------------------------------------------------
  37 /* */
  38 static inline unsigned long RollingChecksum(unsigned char *Start,
  39                                             unsigned char *End)
  40 {
  41    unsigned long A = 0;
  42    unsigned long B = 0;
  43
  44    /* A = sum(X[i],j,k)  B = sum((k-j+1)*X[i],j,k);
  45       Which reduces to the recurrence, B = sum(A[I],j,k); */
  46    for (; Start != End; Start++)
  47    {
  48       A += *Start;
  49       B += A;
  50    }
  51
  52    return (A & 0xFFFF) | (B << 16);
  53 }
  54                                                                         /*}}}*/
  55 // GenerateRSync - Compute the rsync blocks for a file                  /*{{{*/
  56 // ---------------------------------------------------------------------
  57 /* This function generates the RSync checksums for each uniform block in
  58    the file. */
  59 bool GenerateRSync(FileFd &Fd,dsFList::RSyncChecksum &Ck,
  60                    unsigned char OutMD5[16],
  61                    unsigned long BlockSize)
  62 {
  63    SlidingWindow Wind(Fd);
  64    MD5Summation MD5;
  65
  66    Ck.Tag = dsFList::tRSyncChecksum;
  67    Ck.BlockSize = BlockSize;
  68    Ck.FileSize = Fd.Size();
  69
  70    // Allocate sum storage space
  71    delete [] Ck.Sums;
  72    Ck.Sums = new unsigned char[(Ck.FileSize + BlockSize-1)/BlockSize*20];
  73
  74    // Slide over the file
  75    unsigned char *Start = 0;
  76    unsigned char *End = 0;
  77    unsigned char *Sum = Ck.Sums;
  78    unsigned char *SumEnd = Sum + (Ck.FileSize + BlockSize-1)/BlockSize*20;
  79    while (Sum < SumEnd)
  80    {
  81       // Tail little bit of the file
  82       if ((unsigned)(End - Start) < BlockSize)
  83       {
  84          unsigned char *OldEnd = End;
  85          if (Wind.Extend(Start,End) == false)
  86             return false;
  87
  88          // The file is very small, pretend this is the last block
  89          if ((unsigned)(End - Start) < BlockSize && End != Start)
  90          {
  91             OldEnd = End;
  92             End = Start;
  93          }
  94
  95          // All Done
  96          if (Start == End)
  97          {
  98             /* The last block is rather artifical but can be of use in some
  99                cases. Just remember not to insert it into the hash
 100                search table!! */
 101             *(uint32_t *)Sum = htonl(0xDEADBEEF);
 102             InitMD4(Sum+4);
 103             ComputeMD4Final(Sum+4,Start,OldEnd,OldEnd-Start);
 104             MD5.Add(Start,OldEnd);
 105             Sum += 20;
 106             break;
 107          }
 108       }
 109
 110       // Compute the checksums
 111       MD5.Add(Start,Start+BlockSize);
 112       *(uint32_t *)Sum = htonl(RollingChecksum(Start,Start+BlockSize));
 113       InitMD4(Sum+4);
 114       ComputeMD4Final(Sum+4,Start,Start+BlockSize,BlockSize);
 115       Sum += 20;
 116
 117       Start += BlockSize;
 118    }
 119
 120    if (Sum != SumEnd)
 121       return _error->Error("Size Mismatch generating checksums");
 122
 123    MD5.Result().Value(OutMD5);
 124
 125    return true;
 126 }
 127                                                                         /*}}}*/
 128
 129 // RSyncMatch::RSyncMatch - Constructor                                 /*{{{*/
 130 // ---------------------------------------------------------------------
 131 /* This generates the btree and hash table for looking up checksums */
 132 RSyncMatch::RSyncMatch(dsFList::RSyncChecksum const &Ck) : Fast(1 << 16),
 133                                     Ck(Ck)
 134 {
 135    Indexes = 0;
 136    unsigned int Blocks = (Ck.FileSize + Ck.BlockSize-1)/Ck.BlockSize;
 137
 138    // Drop the last partial block from the hashing
 139    if (Blocks < 3)
 140       return;
 141    Blocks--;
 142
 143    // Setup the index table
 144    Indexes = new uint32_t *[Blocks];
 145    IndexesEnd = Indexes + Blocks;
 146
 147    // Ready the checksum pointers
 148    unsigned char *Sum = Ck.Sums;
 149    unsigned char *SumEnd = Sum + Blocks*20;
 150    for (uint32_t **I = Indexes; Sum < SumEnd; Sum += 20)
 151    {
 152       *I++ = (uint32_t *)Sum;
 153    }
 154
 155    // Sort them
 156    qsort(Indexes,Blocks,sizeof(*Indexes),Sort);
 157
 158    // Generate the hash table
 159    unsigned int Cur = 0;
 160    Hashes[Cur] = Indexes;
 161    for (uint32_t **I = Indexes; I != IndexesEnd; I++)
 162    {
 163       printf("%x\n",**I);
 164       Fast.Set((**I) >> 16);
 165       while (((**I) >> 24) > Cur)
 166          Hashes[Cur++] = I;
 167    }
 168    while (Cur <= 256)
 169       Hashes[Cur++] = IndexesEnd;
 170
 171    for (unsigned int Cur = 1; Cur != 255; Cur++)
 172    {
 173       printf("%u %p %x\n",Hashes[Cur] - Hashes[Cur-1],Hashes[Cur],**Hashes[Cur] >> 24);
 174    }
 175 }
 176                                                                         /*}}}*/
 177 // RSyncMatch::~RSyncMatch - Destructor                                 /*{{{*/
 178 // ---------------------------------------------------------------------
 179 /* */
 180 RSyncMatch::~RSyncMatch()
 181 {
 182    delete [] Indexes;
 183 }
 184                                                                         /*}}}*/
 185 // RSyncMatch::Sort - QSort function                                    /*{{{*/
 186 // ---------------------------------------------------------------------
 187 /* */
 188 int RSyncMatch::Sort(const void *L,const void *R)
 189 {
 190    if (**(uint32_t **)L == **(uint32_t **)R)
 191       return 0;
 192    if (**(uint32_t **)L > **(uint32_t **)R)
 193       return 1;
 194    return -1;
 195 }
 196                                                                         /*}}}*/
 197 bool RSyncMatch::Scan(FileFd &Fd)
 198 {
 199    for (unsigned int Cur = 1; Cur != 256; Cur++)
 200    {
 201       printf("%u %p\n",Hashes[Cur] - Hashes[Cur-1],Hashes[Cur]);
 202    }
 203
 204    return true;
 205 }