
Bdiff uses an LZ77-like algorithm which uses the old file as dictionary.

File format:
All values are stored in big endian order.
[n] means that value is n bytes long.
Bits are numbered from the least significant one.

Magic[5]='BDIFF'
Version[1]='a' for bdiff 1.0
Maxlenght[4]=Maximum length of block, without header (>=256)
Block, Block...

Block format:
- Block_type[1]
  bits7-6: 00 if the block must be copied from the original file
           10 if the block contains data to be copied to the destination file
           01 the block contains out-of-band data (checksums, etc.)
           11 Undefined
  bits5-0: depends on bits7-6

- If bits7-6==00 (duplicate data from oldfile)
  bits5-0: if !0 this is the length-5 of the block data to be copied, and
           the BlockSize field is not present.
  Orig_filepos[4]: position in the original file where the data is.
  BlockSize[4]: The length of the block (may be omitted)

- If bits7-6==10 (copy data from the diff file)
  bits5-0: if !0 this is the length-5 of the block data to be copied, and
           the BlockSize field is not present.
  BlockSize[4]: The length of the block (may be omitted)
  Data[BlockSize]: The data to be copied.

- If bits7-6==01 (other stuff)
  bits5-0: if 000000 the following 16 bytes are the md5sum of the old file:
                     md5sum[16]: md5 checksum
           if 000001 the following 16 bytes are the md5sum of the new file:
                     md5sum[16]: md5 checksum
           if 000010 new file permissions:
                     datalength[1]=12
                     userid[4]
                     groupid[4]
                     access[4]


That's all. Currently bdiff stores checksums at the beginning and at the end
of the file and it expects they are in that position while patching. The
format could support many md5 checksums scattered in the diff file for
paranoic checking. Bdiff always check the whole file currently.
