rsync - Jul 2003 - Rolling Checksum Algorithms

Hi,

Where can I get good pointers on the rolling checksum algorithm used in rsync? 
I need an 8-bit or 12-bit rolling checksum too.  Any place where
"rolling"
checksum algorithms are discussed?

Seun Osewa

-------------------------------------------------
This mail sent through IMP: http://horde.org/imp/

On Sun, Jul 20, 2003 at 01:06:11PM +0100, seunosewa@inaira.com
wrote:
> Hi,
> 
> Where can I get good pointers on the rolling checksum algorithm used in
rsync?
> I need an 8-bit or 12-bit rolling checksum too.  Any place where
"rolling"
> checksum algorithms are discussed?
You can have a look at the rsync white paper. 

You can also look at pysync for sample implementations in Python;

http://freshmeat.net/projects/pysync/

I think I've posted on this list some comments about various variations on
the rolling checksum. I think the rsync whitepaper credits it as being a
variation on the Adler checksum, but I think it is closer to something I've
seen called a Fletcher checksum.

Pysync has a Python implementation of a rolling adler32 checksum, and has
comments about the variations in rsync, librsync, and xdelta.

-- 
----------------------------------------------------------------
Donovan Baarda                http://minkirri.apana.org.au/~abo/
----------------------------------------------------------------

On Sun, 20 Jul 2003 22:06, seunosewa@inaira.com wrote:
> Hi,
>
> Where can I get good pointers on the rolling checksum algorithm used in
> rsync? I need an 8-bit or 12-bit rolling checksum too.  Any place where
> "rolling" checksum algorithms are discussed?
>
>
There is very detailed discussion on the checksums used in rsync here:

	http://rsync.samba.org/tech_report/

HTH
Bob Parker