Rolling checksum

The weak rolling checksum used in the rsync algorithm needs to have the property that it is very cheap to calculate the checksum of a buffer X₂ .. X_n+1 given the checksum of buffer X₁ .. X_n and the values of the bytes X₁ and X_n+1.

The weak checksum algorithm we used in our implementation was inspired by Mark Adler's adler-32 checksum. Our checksum is defined by

$$a(k,l) = (\sum_{i=k}^l X_i) \bmod M$$

$$b(k,l) = (\sum_{i=k}^l (l-i+1)X_i) \bmod M$$

s(k,l) = a(k,l) + 2¹⁶ b(k,l)

where s(k,l) is the rolling checksum of the bytes $X_k \ldots X_l$. For simplicity and speed, we use M = 2¹⁶.

The important property of this checksum is that successive values can be computed very efficiently using the recurrence relations

$$a(k+1,l+1) = (a(k,l) - X_k + X_{l+1}) \bmod M$$

$$b(k+1,l+1) = (b(k,l) - (l-k+1) X_k + a(k+1,l+1)) \bmod M$$

Thus the checksum can be calculated for blocks of length S at all possible offsets within a file in a ``rolling'' fashion, with very little computation at each point.

Despite its simplicity, this checksum was found to be quite adequate as a first level check for a match of two file blocks. We have found in practice that the probability of this checksum matching when the blocks are not equal is quite low. This is important because the much more expensive strong checksum must be calculated for each block where the weak checksum matches.