This is the block-matching core of the delta-sync algorithm that cloud-backup clients (rsync, and the sync engines inside iCloud/Drive-style mobile storage) use to avoid re-uploading a whole file after a small local edit. The remote copy is chopped into fixed-size blocks; for each one the client keeps two checksums:
weak(B) = rolling additive checksum, O(1) to slide by one byte
→ a1 = (Σ bytes) mod M, a2 = (Σ i·byte_i) mod M
→ cheap, but collides often (fast reject only)
strong(B) = multiplicative hash over the whole block
→ confirms a weak match is a real match (negligible collision odds)
On the next sync, the client recomputes both checksums for every local block and compares them against the table of remote checksums:
- weak mismatch → block changed, skip straight to "upload" — no need to even try the strong hash.
- weak match, strong mismatch → a rare collision; the weak check would have accepted it, the strong hash catches it (tracked below as a "weak-hash reject" avoided).
- both match → block is byte-identical remotely; it is never transferred.
Only the blocks that fail this test are sent. Delta upload = changed_blocks × block_size; full re-upload = total_blocks × block_size. Transfer time = bytes ÷ (bandwidth/8), so a small block size finds edits precisely but adds per-block checksum overhead, while a large block size wastes bandwidth re-sending untouched bytes that merely sit next to a changed one.