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.
s1 and s2 are defineds as follows in librsync:
s1 = (x[1]+o) + (x[2]+o) + ... + (x[n]+o)
s2 = n*(x[1]+o) + (n-1)*(x[2]+o) + ... + (x[n]+o)
bup also implements a rolling checksum algorithm
bupsplit.c which is similar to librsync.
Unlike librsync which has RollsumRollin, RollsumRollout and RollsumRotate for
update s1 and s2, bup only uses one function rollsum_add. s1 and s2 are defined
as:
s1 = (x[1]+o) + (x[2]+o) + ... + (x[n]+o)
s2 = n*x[1] + (n-1)*x[2] + ... + x[n] + n*(n-1)*o