This weekend, I was hacking Obnam, my backup program, adding support for using the rsync algorithm for backing up only the changed parts of modified files. I was reminded once again how beautiful rsync is. There also seems to be very few implementations of it in pure Python, which is a shame, since all the C implementations get bogged down in memory management and other trivia.

So I thought I'd whip up a very simplistic version of it just in case someone finds it useful. Code is in bzr at http://code.liw.fi/obsync/bzr/trunk/, and crucial parts are excerpted below.

A note on the implementation: I've aimed at simplicity, not speed. I've opted to use zlib.adler32 for the weak checksum rather than the rolling checksum from the original paper: the rolling checksum was fairly slow to compute in pure Python, so it seemed just as good to use the library function.

The code in the bzr branch also includes a main program to allow a UI slightly similar to the rdiff program, and a shell script to verify that the code actually works, for at least one test case.

(I'm not providing an explanation of how rsync works: I'm throwing out this blog entry in a few minutes' break. Read the paper, or Wikipedia, or ask me to explain in a later blog entry if you're lazy.)

block_size = 4096

def signature(f):
    while True:
        block_data = f.read(block_size)
        if not block_data:
            break
        yield (zlib.adler32(block_data), hashlib.md5(block_data).digest())

class RsyncLookupTable(object):

    def __init__(self, checksums):
        self.dict = {}
        for block_number, c in enumerate(checksums):
            weak, strong = c
            if weak not in self.dict:
                self.dict[weak] = dict()
            self.dict[weak][strong] = block_number

    def __getitem__(self, block_data):
        weak = zlib.adler32(block_data)
        subdict = self.dict.get(weak)
        if subdict:
            strong = hashlib.md5(block_data).digest()
            return subdict.get(strong)
        return None

def delta(sigs, f):
    table = RsyncLookupTable(sigs)
    block_data = f.read(block_size)
    while block_data:
        block_number = table[block_data]
        if block_number:
            yield (block_number * block_size, len(block_data))
            block_data = f.read(block_size)
        else:
            yield block_data[0]
            block_data = block_data[1:] + f.read(1)

def patch(outputf, deltas, old_file):
    for x in deltas:
        if type(x) == str:
            outputf.write(x)
        else:
            offset, length = x
            old_file.seek(offset)
            outputf.write(old_file.read(length))