bidiff

bidiff is a set of rust crates that generate and apply patches for arbitrary binary files.

It is particularly well-suited to deploying software updates, and:

• Is written in 100% safe Rust
• Has been fuzzed thoroughly
• Has reasonable memory requirements
• Supports large (>2GiB) inputs
• Supports multiple compression formats (brotli, zstd, etc.) via comde

License

This project (bidiff, bipatch and bic) is licensed under either of

• Apache License, Version 2.0 (LICENSE-APACHE or http://www.apache.org/licenses/LICENSE-2.0)
• MIT license (LICENSE-MIT or http://opensource.org/licenses/MIT)

at your option.

Benchmarks

In this section, we compare using bidiff to generate patches against two versions of well-known software, versus just compressing the newer version with zstd (hereafter referred to as "naive").

All measurements are done on an Intel(R) Core(TM) i7-8750H CPU @ 2.20GHz, with 12 partitions and 1 MiB chunks.

zstd compression at level 21 is used in both "naive" and "bidiff" runs:

Repository organization

This repository contains three crates:

• crates/bidiff contains the diff algorithm, and has an optional enc feature for serialization.
• crates/bipatch contains code that reads and applies patches generated by bidiff's enc feature.
• crates/bic is a demonstration command-line interface to the above two crates, which uses comde for compression.

The essential part is contained in the bidiff crate itself. The serialization/deserialization code is provided as a (practical) example of how to store patch files. It is very simplistic: a magic number, a version number, and then a series of ADD, COPY and SEEK instructions, with variable-length integer encoding.

Note: bidiff and bipatch do not concern themselves with compression, but patch files MUST be compressed. Uncompressed, they are slightly larger than the "newer" file (but lower-entropy).

Diffing is a memory- and CPU-intensive task. The requirements are discussed below. Patching, however, can be done in streaming fashion and requires very little memory (only small buffers to perform addition between the "older" file and parts of the "patch" file).

Prior art: bsdiff

bidiff is based on the bsdiff algorithm as described in Naïve Differences in Executable Code (2003) by Colin Percival, but the implementation differs in a few key areas.

The key idea behind bsdiff is to find approximate matches between an "older" and a "newer" file, and then stored the difference between those, which ends up having lower entropy than the newer data itself. After compression, the resulting patch file is usually much smaller than the newer file would be if compressed.

The algorithm works in two phases:

• Sorting, in which all suffixes of the "older" file are sorted, and their rank is stored in a suffix array. This is done using a SACA (Suffix Array Construction Algorithm).
• Scanning, in which the suffix array is used to find approximate matches. The most promising approximate matches are selected using a simple scoring system.

The original bsdiff implementation tends to be quite time and memory-hungry.

In particular:

• It requires max(17*n,9*n+m)+O(1) bytes of memory (where n and m are the size of the older and newer file respectively)
• It stores "control", "difference" and "extra" data separately for "better compression"
• It uses bzip2 as a compression method.
• It uses a rather old SACA, described in Faster Suffix Sorting (1999) by Larsson and Sadakane.

What makes bidiff different

bidiff generates patches of similar size compared to bsdiff, but is generally faster and requires less memory, thanks to the following changes.

bidiff does suffix sorting using a hand-ported Rust version of divsufsort by Yuta Mori, a highly-optimized suffix sorting algorithm that has been repeatedly mentioned in research, despite the emergence of newer sorting methods.

Whilst not "the latest" in suffix sorting, it performs surprisingly well in practice (in near-linear time) and has modest memory requirements of O(5*n) (where n is the size of the "older" file).

Switching to divsufsort alone is already a significant improvement on the original bsdiff in terms of memory usage and time efficiency, but bidiff does not stop there.

For large file support, bidiff does not use the divsufsort64 variant, which would require O(9*n) memory (plus a larger constant). Instead, it introduces "partitioned suffix arrays". The "older" file is split into multiple partitions, each suffix sorted separately.

This achieves two things:

• The maximum input size is no longer limited to 2**31-1 (due to using i32 as an index type)
• Suffix sorting can be performed in parallel

In practice, suffix sorting in bidiff is performed in parallel using rayon, as long as the number of partitions is greater than one.

Note: switching to u32 as an index type to raise the original limit from 2GiB to 4GiB is not an option. divsufsort uses negative numbers abundantly while sorting, so the only options are i32 and i64.

Using partitioned suffix arrays has a downside: the cost of searching for the "longest matching substring" in the original text is no longer O(log n), but O(p*log n), where p is the number of partitions.

Since that operation is performed a great number of times while diffing, using a large number of partitions slows the scanning phase more than it speeds up the sorting phase.

For sample 20MiB Windows executable files:

Another downside is that, due to partitioning, very occasionally, worse matches are found, for substrings that cross the border between two partitions. In practice, this only very slightly affects patch size, as the rest of the match is found immediately thereafter, resulting in two "ADD" operations rather than one, which still compresses nicely.

Seeing these results, one may consider performing binary searches in each suffix array in parallel. However, experimentation has shown that, since those are very short operations repeated many times, the cost of synchronization overshadows any gains one might have hoped for.

bidiff addresses this another way, by parallelizing the scanning phase. The "newer" file is split into "chunks", and each of them are diffed in parallel (by as many workers as is efficient given the number of cores available). The results are a series of approximate matches, which are reordered and translated into a patch file by another worker.

Note that dividing the newer file into chunks also contributes to generating very slightly worse patch files: cross-chunk matches will result in two ADD operations, where they would only be one before. However, in practice, the difference is negligible.

This technique results in notable speedups.

For the same inputs as before:

When parallelizing scanning, sort time begins to dominate. Using a combination of both techniques allow optimizing for core utilization and overall runtime:

These are one-off measurement on relatively small files (20 MiB) but this is representative of the tradeoff that's done here - performance varies similarly for larger files (and various kinds of files).

In this case, the overall speedup achieved is almost 3x, on a 6-core machine. The optimal parameters for "partitions" and "chunk size" depend on the machine used to diff, but are generally along the lines of:

• partitions = (num_cores - 1) (this leaves a core for bookkeeping and compression)
• chunk size = newer_size / (num_cores * k), where k is between 2 and 4;

Note: efforts to parallelize divsufsort and still have a single suffix array have been attempted. However, the speedups are rather disappointing - the parallel variant needs 4 to 8 cores before it starts beating the sequential version. See for yourself.

Choosing a chunk size that's too large will result in suboptimal core utilization, whereas choosing a chunk size that's too small will result in increased memory usage for diminishing returns: