Tridgell describes it in his paper Rolling checksum. librsync implements it in rollsum.h and rollsum.c. The difference between the paper and librsync is the adding of ROLLSUM_CHAR_OFFSET in librsync. This post weak checksum question explains the meaning of ROLLSUM_CHAR_OFFSET:
librsync adds an offset to each byte before it is fed into the Fletcher checksum.
And I agree with the post’s author that
ROLLSUM_CHAR_OFFSET does not have any impact
on the rolling checksum algorithm. If
ROLLSUM_CHAR_OFFSET is 0, the paper and
the librsync are the same. Let’s use
o to represent ROLLSUM_CHAR_OFFSET.
s2 are defineds as follows in librsync:
s1 = (x+o) + (x+o) + ... + (x[n]+o) s2 = n*(x+o) + (n-1)*(x+o) + ... + (x[n]+o)
bup also implements a rolling checksum algorithm
bupsplit.c which is similar to librsync.
Unlike librsync which has
s2, bup only uses one function
s2 are defined
s1 = (x+o) + (x+o) + ... + (x[n]+o) s2 = n*x + (n-1)*x + ... + x[n] + n*(n-1)*o