bps :: Binary Patching System2011-08-23
bps is a tool to encode the difference between two files: the original version, and the modified version. bps runs natively on Windows, and can run on other operating systems using either GTK+ or Qt. Lastly, it can be compiled with the phoenix-reference target, and run in command-line only mode, on virtually any platform with a C++ compiler.
Download
bps v03 - Windows binarybps v03 - source code
Comparison
| Input File | IPS | UPS | Xdelta3 | BPS | Xdelta3 -9 | BPS -7z |
| Der Langrisser (J) -> (U) | 858,833 | 854,756 | 849,758 | 823,917 | 816,436 | 783,650 |
| Mystic Ark (J) -> (U) | 364,984 | 368,276 | 342,946 | 252,938 | 219,223 | 165,761 |
| bsnes v078 -> v079 | 1,245,975 | 1,279,504 | 357,276 | 234,315 | 195,844 | 187,818 |
| FEoEZ (J) -> 48mbit * | 4,130,818 | 5,273,465 | 70 | 48 | 70 | 53 |
(* Far East of Eden Zero 40mbit ROM image, with 8mbit program ROM expansion inserted as 0x00s at 1MB file offset, forming 48mbit output ROM image.)
Usage
bps is a combined GUI and command-line tool in one. What mode it runs on depends upon what command-line flags are passed to it.
Direct invocation mode: bps
When running bps with no command-line arguments, it opens the GUI in patch application mode.
File-association mode: bps {patch}.bps
When BPS files are associated with bps.exe, or BPS files are dragged onto the BPS binary, it opens the GUI in patch application mode, and sets the patch file path to the one specified.
Verify Data will validate the checksums of the input and output files, to ensure that the patch was applied successfully to the correct file. It is highly recommended to leave this option on, but it can be turned off if you intend to apply multiple patches to the same file.
Patch creation mode: bps create
When specifying "create" as the program argument, bps will open in patch creation mode. Here, you can specify whether you wish the patch to be created in delta mode. If unchecked, the patch will be created in linear mode.
Delta Mode produces smaller patches, and can handle insertions to and deletions from the original file. The downside is that it takes longer to create the patch.
Linear Mode produces larger patches, and is near-useless when working with file insertions or deletions. Due to its fast speed, it may be a good match when patching binary executable files.
Command-line patch application mode: bps apply {patch}.bps {source-file} {target-file}
In this mode, the patch will be applied without the GUI, and the result will be printed to the console.
Command-line delta patch creation mode: bps create-delta {patch}.bps {source-file} {target-file}
In this mode, the patch will be created in delta mode without the GUI.
Command-line linear patch creation mode: bps create-linear {patch}.bps {source-file} {target-file}
In this mode, the patch will be created in linear mode without the GUI.
Command-line metadata deletion mode: bps metadata {patch}.bps delete
This command will delete any metadata stored inside the specified patch.
Command-line metadata insertion mode: bps metadata {patch}.bps {metadata}.xml
This command will insert the {metadata}.xml file into the metadata section of the specified patch.
BPS advantages
BPS has several key advantages over other patching specifications.
First, it is a very simple specification. Patch application can be accomplished with ~5KB of code. Patch creation, with or without delta encoding, can also be accomplished with ~5KB of code.
BPS can create delta patches, and it can also create traditional linear patches, which have tremendous speed advantages over delta patch creation.
The BPS patch application algorithm is the same for both delta and linear patches, and patch application is always lightning-fast.
BPS includes checksum information to ensure the proper files are used for patching, and to verify that patch application was successful.
BPS also supports embedded authorship metadata information.
The BPS specification can create and apply patches to files of infinite size. And due to its novel encoding method, it is neither big-nor-little-endian. The same code works on both endian modes seamlessly, which helps to eliminate the potential for porting issues.
The BPS specification is 100% closed. There are no "undefined" cases, or "reserved for future use" values. This helps to ensure that third-parties cannot hijack the specification through viral, non-universal extensions that would dillute the format's universal support.
And to top it all off: BPS patch creation and application is fast, and the patches it produces are typically among the smallest possible, even when they are not stored inside of compression containers.
IPS
IPS is limited to files that are 16MB or smaller. This rules out IPS usage for many Game Boy Advance projects, for one.
IPS cannot shrink files. The output file can never be smaller than the input file. There is a non-standard extension to the specification that allows for this, but many IPS patchers do not support it, making the feature unreliable at best, and corrupting output files at worst.
IPS does not store checksum information. As a result, it is impossible to know if the IPS patch has been applied to the correct file or not.
IPS does not store authorship information. When the patch is distributed independently, no information about the patch is available.
IPS patches cannot handle delta information: insertions to or deletions from the original file cause IPS to consider every subsequent byte as different, resulting in patch sizes as big as or larger than the original files.
UPS
UPS patches, when compressed for internet distribution, typically end up being twice the size or larger than ordinary patches. This is due to the storage method being a file XOR for reversibility; which destroys the data compressibility, simply to support a very niche functionality.
Because UPS patches are reversible, when your modified file is smaller than the original file, this information has to be stored in the patch as well. This data cannot be XORed, and as such it is stored directly. If you are patching a copyrighted file, this could expose you to potential legal troubles.
UPS patches do not attempt even basic RLE encoding, so simple file expansion padding with any value other than 0x00 end up storing all of the padded information directly, creating very large patch sizes.
UPS patches also do not store authorship information.
UPS patches also cannot handle delta information.
Xdelta and bsdiff
Xdelta and bsdiff are powerful patching formats, but suffer from ridiculously complicated file formats. The file formats internally use advanced compression technologies that require several hundreds of kilobytes worth of code to implement. As a result, the only implementations that exist are their canonical C/C++ implementations. This complexity makes them unsuitable for use in lightweight applications.
BPS file format specification
char[4] signature ("BPS1")
varint source-file-size
varint target-file-size
varint metadata-size
utf8[metadata-size] metadata
uint8[] patchdata
uint32 source-file-checksum
uint32 target-file-checksum
uint32 patch-file-checksum
varint encoding and decoding
BPS supports encoding of infinitely-sized numbers. It does this by using a bit-streaming technique. C implementations follow:
void encode(uint64_t data) {
while(true) {
uint64_t x = data & 0x7f;
data >>= 7;
if(data == 0) {
write(0x80 | x);
break;
}
write(x);
data--;
}
}
uint64_t decode() {
uint64_t data = 0, shift = 1;
while(true) {
uint8_t x = read();
data += (x & 0x7f) * shift;
if(x & 0x80) break;
shift <<= 7;
data += shift;
}
return data;
}
The idea is that the top bit indicates if we are finished decoding yet, and the lower bits make up part of the address. In this way, and combined with relative offset addressing, we can amortize all values to a single byte.
That is to say, while IPS always requires three bytes for every offset, and two bytes for every length; BPS averages to just barely over one byte per offset or length encoding.
Metadata
Metadata stores an XML file in UTF-8 encoding. The string is not null-terminated. Because binary differencing has unlimited potential uses, there is no rigid standard for this data. XML is extensible, which is the whole point here.
In the future, specifications for certain types of patches, eg SNES patches, may be defined.
Patch Data
The patch data contains zero or more blocks that specify how to create the modified file from the patch and original file.
The way BPS works, is that it encodes every single byte of the modified file. It does not have seek commands that skip around in the file, and it does not store target write addresses. It streams every byte, from the very first, to the very last.
To do this, BPS implements four commands:
%00 - SourceRead(length) %01 - TargetRead(length, data[length]) %10 - SourceCopy(length, offset) %11 - TargetCopy(length, offset)
To process the patch data, you simply keep parsing it until the remaining bytes left in the last are less than or equal to 12 (eg once the checksum footer section is reached.)
First, you decode() a varint. The low two bits of this value specify the command mode, as listed above. Shift this value right by two, and then add one, and you have the length, which is used by all commands. We add one, because it makes no sense to store a zero-length write command.
If this is a SourceCopy or TargetCopy command, call decode() again. This time, the lowest bit represents the sign. 0 = positive, 1 = negative. Shift the value right by one, and you have your offset. If the sign is 1 (negative), then negate the offset. The reason we store the sign-bit at the bottom, is because the encode/decode method does not allow us to encode twos-complement negative numbers in the traditional manner.
SourceRead
SourceRead copies bytes from the original file to the target output file. It copies from sourceData[outputOffset] to targetData[outputOffset], where outputOffset is the current write location for the output file.
This command is used to store data that is unchanged between the original and modified files.
TargetRead
TargetRead copies bytes from the patch file to the target output file. Immediately after the decoded varint, there is a stream of bytes equal to the length. Copy these and write them to targetData[outputOffset++].
This is the primary method for storing changes to the original data.
SourceCopy
This command treats the source file as a large dictionary. When patch application begins, sourceRelativeOffset is set to zero. The offset will be a signed value that is added to the sourceRelativeOffset. Once done, for the number of bytes requested by length, copy sourceData[sourceRelativeOffset++] to targetData[outputOffset++].
The sourceRelativeOffset now points to the end of the copy that was just done. The reason we store this as a relative value, is because smaller numbers consume less bytes with our encode/decode method. The general thinking is that the source and target files progress linearly, so most likely the next SourceCopy command will be a small number of bytes forward. In this way, we can amortize the encoded offset size to a single byte.
TargetCopy
This command treats all of the data that we have already written to the new target file as a large dictionary, and is also used for RLE encoding.
The idea is that sometimes there will be repeating data in the newly modified data, and this command can catch and encode that, without the need to store all of the bytes over and over with TargetRead.
It is also very effective for RLE encoding, which is very useful for expanded file padding. The trick to using this as an RLE command is to store a given number of bytes using TargetRead. Let's say TargetRead just copied over { 0x00, 0xff }. We can now perform a TargetCopy, starting from outputOffset - 2, with a length of 65,534. As the patch applier works one byte at a time, it will read the first two bytes as it writes them to the output. Now it is pointing at the newly written second instance of the two-byte pattern, and it will repeat. We have now encoded a 64KB binary sequence into two very small commands, typically about five bytes in size. Also note how unlike traditional RLE, we can encode more than one-byte repetitions as well.
TargetCopy has its own index, targetRelativeOffset, which is also initialized to zero at the start of the patch application process.
Checksum Data
At the end of the file, the source, target and patch CRC32 checksums are stored. The reason we store these at the bottom of the file, is so that the patch creator or applier can compute them as the files are processed, and patch creation will not need to seek back and rewrite sections of the header.
The patch checksum itself is special: it does not include the checksum value itself as part of the checksum. So this is equal to the checksum of patchData(patchSize - 4). The checksum would obviously change as the checksum was being written, so we don't count that part. Although it's possible to use trickery to do this anyway, it goes against BPS' goal of remaining a simple patching format. Speaking of which, this is why CRC32 is used, instead of stronger hashing algorithms such as SHA256: the checks are meant to ensure valid data is there, not to provide security against malicious attacks that try and disguise modified files as the originals.
Source Code
If any of this is unclear, please see the bps source code. Specifically, the implementations under nall/bps.