Zucchini is an executable patch algorithm currently used by Google in Chrome updates. It is a substantial improvement over Google's earlier Courgette, both in compression ratio and speed, and also a good deal better than our current mbsdiff (BSDiff 4) in compression ratio.

All the documentation I know of is in the Chromium source tree. The big idea is this: A lot of the change that happens between builds is just bulk movement of code, and this also causes all cross-references to that code to change. Zucchini encodes the movement of the code/data ("equivalences"), like most binary diff tools, but it also disassembles the program in order to find references into that moving data (the "target"). If it copies code containing those references, it can adjust them to point at the new location of the target, without needing to store that adjustment explicitly.

I ran some tests with Firefox updates a few versions ago, here's how it compares (sizes in MB):

Patch application takes about twice as long as mbsdiff, (Courgette is about 4x mbsdiff), but that is partially offset by the LZMA (xz) decompression being much faster when handling smaller patches.

A practical hurdle to incorporating Zucchini is that it relies on some standard libraries and headers elsewhere in the Chromium tree. We've already vendored some of this, twice, for sandboxing and ipc, and it's unpleasant to bring in yet another version of some of this.

This may not be worth the added complexity — BSDiff does very well considering how simple it is — but since we still have bug 504624 for Courgette I thought it would be good to make a case for Zucchini.