Rolling algorithm vs CRC

[Ryan Malayter]

On Fri, May 22, 2009 at 9:02 AM, Hasanat Kazmi <hasanatkazmi at gmail.com> wrote:
> Hello,
> I have previously mailed on list that I am trying to port rsync to NT. I was
> wondering that whether CRC can be used to find check sums rather then
> rolling algorithm. I havnt found any document on web comparing rolling
> algorithm with CRC.
>

CRC doesn't have the correct properties for rsync, in that you cannot
"subtract" previous bytes from the current hash in an efficent way.
This is what enables rsync to compute the hash at every byte of the
file in an efficient manner. For more info, read Tridgell's thesis
paper at:
http://samba.org/~tridge/phd_thesis.pdf
-- 
RPM