Rolling algorithm vs CRC

Jamie Lokier jamie at shareable.org
Fri May 22 15:10:43 GMT 2009


Ryan Malayter wrote:
> 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.

As you sure about this?  Each bit of the byte to be subtracted is
mixed linearly (i.e. XORs, no ANDs or ORs) into the result even when
the result is many bytes away (i.e. block size).  It looks, on the
face of it, like a small table-driven algorithm, same size table as
normal fast CRC but precalculated differently, might work for
subtracting previous bytes, as quickly as it adds them on the end.

-- Jamie


More information about the rsync mailing list