]> git.decadent.org.uk Git - dak.git/blob - tools/dsync-0.0/libdsync/rsync-algo.cc
Add a test for PoolFile and Location.
[dak.git] / 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 }