Patching Files

For updating files WoW uses bsdiff. Have a look at "http://www.daemonology.net/bsdiff/" or "http://www.pokorra.de/coding/bsdiff.html"

Depending on version, this might not be BSDIFF40 but ZBSDIFF1, which is a variant of BSDIFF40 with seemingly no differences than exchanging BZ2 library calls with their libz inflate equivalents.

struct zbsdiff1_header {
  char magic[8]; // "ZBSDIFF1" or "BSDIFF40"
  uint64_t control_block_size;
  uint64_t diff_block_size;
  uint64_t output_file_size;
} header;
char compressed_control_block[header.control_block_size];
char compressed_diff_block[header.diff_block_size];
char compressed_extra_block[0]; // to the end of the file

where compressed blocks are either BZ2 or zlib compressed depending on header.magic.

To patch a file, first decompress the blocks, then interpret control_block as

struct {
  uint64_t bytes_from_diff_block;
  uint64_t bytes_from_extra_block;
  uint64_t seek_in_input;
};

and iterate the data according to control_block:

• Copy bytes_from_diff_block data from input, bytewise += bytes from diff_block and copy to output: o[x] = i[x] + d[x]
• Copy bytes_from_extra_block bytes from extra_block to the output: o[x] = e[x]
• Seek seek_in_input in input, keep offset in output.
• Repeat.

This means that

• copying without modification: diff block filled with 0 (and rely on compression to make it small)
• copying with modification: diff block filled with bytewise diff
• addition: extra bytes
• removal: seek over removed bytes
• tuples of up to three operations are collapsed into one control blovk

For an implementation, consult bspatch from BSDIFF4.