Slicing Chrome's Zucchini Patches in Half
I've been experimenting with structure-aware compression, and put together a tool called presage that applies the technique to binary patching.
Chrome's Linux executable is 291 MB. Zucchini, the differ in Chrome's release updater, produces a 5.9 MB patch between two recent stable releases. Presage cuts that by more than half to 2.3 MB after a set of LLM-assisted hill-climbing rounds that refined the underlying structure-aware technique.
| Method | Bytes | |
|---|---|---|
| Full download (xz -9) | 81,816,856 | |
| xdelta3 | 40,102,887 | |
| bsdiff | 18,599,806 | |
| Zucchini (xz -9) | 5,889,352 | |
| presage | 2,263,302 |
The basic idea is to start with a structured plan that lets the decoder predict the bytes of the new binary from the old one, followed by a correction to recover the byte-exact final result.
Why a Small Change Makes a Big Patch
A small source-code edit rarely produces a similarly small change in a compiled binary. Expand one function, and every function after it slides down in the file. Because each call instruction stores a relative displacement to its target rather than an absolute address, it has to be re-encoded whenever caller and callee shift by different amounts. Other secondary effects work the same way: sorted tables and stack-unwinding records shift from a single insertion or deletion, and profile-guided optimization (PGO) can regenerate different code whenever the profile changes.
gcc -O1, after adding if (n == 42) return -3; to validate().A copy-based differ like xdelta3 can track function code shifting to a new offset, but it doesn't know the structure of the relative displacements, so the patch has to carry them. Those seven re-encoded address bytes are only a tiny sample: Chrome's .text code section holds 8.7M such displacements.
This problem has a quarter-century history. The 1999 Exediff paper calls the direct effects of an edit primary changes and the changes caused by the resulting layout secondary changes. bsdiff (2003) encodes secondary changes cheaply without understanding them, and aligns old and new so the bytewise difference is mostly zeros. Chrome's differs use knowledge of the compiled binary structure to reproduce secondary changes instead. Courgette (2009) disassembles the code, replaces addresses with labels, and diffs the result, at the cost of a decoder that has to reassemble the binary. Zucchini (2017) keeps the file as bytes and simply translates the references it recognizes, so a missed reference adds a few bytes to a patch instead of a reassembly failure.
Here are the bytes each differ gets wrong in the new Chrome binary, shaded on a log scale.
Block-level deduplication like rsync fares worst, because a changed displacement every few dozen bytes breaks nearly every 4 KB block. Byte-level differs handle the slide, then diverge on those changed fields. xdelta3 copies around them, so millions of copy instructions make up most of its patch, while bsdiff copies straight through and relies on bzip2 to compress the small bytewise differences. Zucchini and Presage predict those references before comparing instead.
Presage keeps Zucchini's safety property while pushing its structure-aware prediction much further. Every patch splits into a plan that guides the decoder from the old binary to a full-length guess at the new one, and a correction for every byte that misses.
Zucchini, Thinly Sliced
To see where Chrome's 5.9 MB patch actually goes, I started by rebuilding Zucchini's baseline inside Presage. Zucchini uses an equivalence map to copy regions of the old file into the new layout, translates the relative jumps, calls, absolute pointers, and relocation slots it recognizes inside those copies, and writes a correction for everything still wrong. With Presage's tighter correction format, that baseline starts at 5.1 MB.
From there, every row on the chart came out of the same loop: inspect what caused the most wrong bytes left in the prediction, propose a structural rule to rebuild it, test it against the real 291 MB target, and keep only what shrinks the final patch. Two big structural wins do most of the work, followed by a few narrower predictors and a better final compressor, until the hill-climbing hits diminishing returns.
Rebuilding the Relocation Table
When Linux loads a binary into memory, it walks the .rela.dyn table to fix up pointers whose addresses depend on where the executable landed. Chrome's 26 MB table holds 1.1M relative relocations, and each row tells the loader to write a target address, the addend, into a slot. When code and data shift, both columns change down the whole table. Zucchini translates the slot and copies the addend as raw bytes (there's still a TODO in its source to handle addends), so nearly every addend misses. Correcting them accounts for almost a third of Zucchini's patch.
The obvious fix is to translate addends as pointers and pair old and new rows by index, which gets only ~11% right. Because the table is sorted by slot address, the moment a single relocation moves earlier or later, every row after it lines up against the wrong neighbor. Presage rebuilds the sorted slot column first as gaps between consecutive addresses. Then it maps each old entry's slot and addend through the equivalence map and joins them onto the new table by slot address.
Joined on slot address, ~79% of addends come out exact, and the function map in the next step recovers most of the rest. In the final patch, the 26 MB table takes 81 KB.
One Function, Three Bytes
Between the two releases, v8::base::TimeTicks::Now() moved ~440 KB later in the file. Only 3 of its 98 bytes changed, all in the displacement of its one call.
Across ~925k functions, the same instructions with different addresses drive most of the churn between releases. Zucchini only matches raw byte ranges, and still gets ~15% of functions wrong.
Presage adds a function map that pairs old functions with their new counterparts. Built on the publisher's side from unstripped binaries that still carry function names and boundaries, it sends no symbols to the client. With that map, the decoder walks each placed function and recomputes every relative displacement from the new addresses.
Sent as a plain list of addresses, the map would cost 1.32 MB, which is more than it saves. The trick is that the decoder can find 99% of the old functions on its own from call targets, relocation targets, and the 0xcc padding bytes Clang leaves between functions. That leaves the plan spending just 155 KB on the missed functions and what changed between builds.
Even at 155 KB, retargeting every function unconditionally through the map makes the patch worse, because the prediction is no better than the equivalence copy alone. What makes it pay off is 1 bit per function to pick either the equivalence copy or the function-map prediction. Equivalences preserve the compiler's local layout, including small constant-data blocks placed between functions. The function map wins when the byte matcher grabs the wrong copy of near-identical code under identical-code folding (ICF), where the linker merges identical functions into one copy.
The function map also fixes the rest of the relocation table. Under ICF, one old address can stand for several logical functions that separate in the new build. Once the map tracks function identity instead of raw byte matches, exact relocation addends jump from ~79% to 99%.
The Remaining Layers
Stack-unwinding records in .eh_frame carry relative start addresses that shift with their functions, so Presage retargets them and regenerates the sorted .eh_frame_hdr index instead of patching a second copy. Jump tables from switch statements in .rodata are trickier because Linux's ELF format doesn't mark where they live. Scanning .rodata for runs of aligned offsets that land inside .text turns up ~27k candidates. Rewriting all of them made the patch larger, so the encoder tests each candidate against the real binary and sends a bitmap of the ~3.6k tables worth rewriting.
Even then, ~25% of the wrong bytes left in .text sit inside 4-byte displacement fields. Since the decoder can enumerate all 8.7M of them from its own prediction, the plan remaps targets that many fields disagree on, as long as the remap fixes more fields than it breaks, and sends a signed per-field delta for the rest. Address fields drop from 25% of the wrong code bytes to 2%. Presage uses the same per-field deltas for instruction operands that address retargeting leaves alone, such as immediate constants and stack-slot offsets.
Until the final layer, the correction stream went to an ordinary compressor that sees replacement bytes without knowing what they replace. A mispredicted displacement usually differs only in its low bytes, and a recompiled instruction usually keeps its opcode. Presage adds a small context-mixing arithmetic coder that predicts each correction byte from the predicted byte underneath it, and also compresses the plan's own streams using each field's structure as context. Per stream, the encoder tries both and keeps the smaller output. The arithmetic coder wins on short replacements, and the general compressor still wins on long runs of recompiled code. Running the arithmetic coder adds ~1.5s of decode time per MB of correction, and brings the final patch to 2.26 MB (38% of Zucchini's).
What Remains
| Component | Bytes | Share | plan correction |
|---|---|---|---|
.text correction | 847,113 | 37.4% | |
| equivalence map | 476,977 | 21.1% | |
| address-field corrections | 325,955 | 14.4% | |
| function map | 154,793 | 6.8% | |
.rodata correction | 135,041 | 6.0% | |
| operand-field corrections | 123,452 | 5.5% | |
.rela.dyn plan | 81,017 | 3.6% | |
| per-function choice bits | 72,152 | 3.2% | |
.eh_frame correction | 21,606 | 1.0% | |
| everything else | 25,196 | 1.1% | |
| Total | 2,263,302 | 100% |
Every layer is verified by replaying the plan, applying the correction, and comparing all 291 MB against the target byte for byte. Applying the final patch takes 2.7s.
More than a third of the final patch is .text correction, and its largest share is 400 KB of recompiled code, mostly in the ~9.5k functions the compiler resized between the two builds. The commit log between the two tags has 8 bug fixes touching ~30 source files, alongside 6 updates to the Linux PGO profile. A new profile drives inlining and hot/cold splitting across the whole binary, which is what resizes those 9.5k functions. Most of the remaining code diff is just PGO recompilation.
Where to Go from Here
I explored Chrome release-patch optimizations in this post because Courgette and Zucchini were built for Chrome. Everything Presage knows about x86-64 and ELF lives in one structure module, and modules for other toolchains can sit beside it. Go binaries are an even better fit, because less than half of a typical Go executable is machine code and the rest is metadata the linker derives from it. With a module that models the Go linker, Presage produces patches dozens of times smaller than a general-purpose differ's. That is the next post.
I think structure-aware compression suits LLM-assisted hill-climbing performance optimization remarkably well, and having bespoke optimizations like this be cost-effective opens up a range of interesting opportunities for pushing system performance and efficiency beyond what was previously possible with general-purpose, one-size-fits-all algorithms.
Presage is on GitHub at wjordan/presage.