Slicing Chrome's Zucchini patches in half

August 30, 2026

Chrome's Linux executable is 291 MB. Between two adjacent stable releases, Zucchini, the differ inside Chrome's own updater, produces a 5.9 MB patch. This post introduces a tool that produces a 2.3 MB one for the same pair, byte-for-byte exact: the patch is a structural plan the decoder predicts the new binary from, plus a correction for the bytes it got wrong.

This is a prototype measured on one public release pair, not a change to Chrome's updater.

Why a small change makes a big patch

A one-line source edit rarely produces a one-line byte edit. The change is small, but it is diffuse. Functions slide, and a call stores the distance to its target rather than the target's address. That distance, its displacement, has to be re-encoded whenever the two ends moved by different amounts. A sorted table gains one entry and everything after it slides. Unwind records regenerate. Profile-guided optimisation moves around code nobody touched.

A copy-based differ like xdelta3 handles the slide without difficulty; finding moved regions is what those tools do. What they cannot do is know that the re-encoded addresses are a consequence of the slide. Inside a matched region they are mismatches, and the patch has to carry them. Here that is seven bytes. In Chrome's .text there are 8.7 million such displacement fields.

This is a twenty-five-year-old problem, and the differs that ship Chrome updates descend directly from the first papers on it:

Baker, Manber and Muth's Exediff (1999) drew the distinction that everything since depends on: primary changes, which come from the edit, and secondary changes, which come from the layout the edit disturbed. Exediff undid some of the secondary ones with symbol tables and knowledge of one instruction set. Colin Percival's bsdiff (2003) went the other way and understood nothing about the file: it aligns old and new with a suffix array, lets matches run through mismatching bytes, and stores the difference of the aligned regions, which is mostly zeros. You do not need to understand a secondary change to encode it cheaply; you only need to line the bytes up so the difference is small. Percival's 2006 thesis calls these second-order changes, notes that one modified line can touch 5–10% of an executable's bytes, and states the problem in a sentence: delta compression of executables is largely the problem of locating and compactly encoding second-order changes.

The two differs Google built for Chrome's updater attack that problem directly: instead of lining bytes up so the second-order changes are cheap, understand enough of the file to reproduce them. Courgette (2009) disassembles the x86, replaces every address with a label, adjusts the labels between versions, and diffs that. On its published example a 704 KB bsdiff patch became 79 KB, at the price of a decoder whose correctness depended on disassembling and reassembling faithfully. Zucchini replaced it with a more forgiving design: keep the file as bytes, annotate typed references (relative branches, absolute pointers, relocations), find large equivalent regions between old and new, and translate the references inside them. A missed reference costs a few bytes; it never costs correctness.

Here is how much each of those designs gets wrong on the Chrome pair, region by region across the new binary:

Chunk dedup, the first thing most people reach for, does badly here. rsync-style blocks survive only if they are byte-identical, and a slid function has a changed displacement every few dozen bytes, so 88% of the file is sent.

xdelta3 and bsdiff both find the slide at byte granularity, and then diverge on the displacement bytes. xdelta3 copies around them and gets only 6% of the file wrong, yet ships 40 MB, because copying around millions of four-byte holes takes millions of copy instructions, and those are the patch. bsdiff copies through them and is left with 8.7% wrong; those are small differences of large numbers, which is what its diff stream and bzip2 are built for, and the patch is 18.6 MB. Zucchini translates the references inside its copies before it compares, and gets 2.8% wrong: 5.9 MB. The prediction this post describes gets 0.5% wrong, and the rest of the post is about where that difference comes from.

Zucchini is the baseline for everything that follows. Presage keeps its safety property and pushes the prediction much further. The patch is a compact plan that lets the decoder build a complete, exact-length guess at the new executable from the old one, followed by a correction for every byte the guess got wrong. The guess has to be deterministic. It does not have to be right.

Zucchini, thinly sliced

The chart below starts with Zucchini's method rebuilt inside this framework, then takes one slice off at a time: each layer rebuilds something Zucchini sends as bytes, until the last, which changes how the remaining bytes are coded. Each bar is the compressed patch, split into the plan the decoder follows and the correction for what the plan got wrong.

Zucchini's method is three things: an equivalence map, the list of old regions to copy into the new layout; every reference it recognises inside the copies (PC-relative fields in code, absolute pointers in data, the slot address of each relocation entry), translated through that map; and a correction for what is still wrong.

The starting point does the same three things with presage's own coder and lands at 5.1 MB against Zucchini's 5.9. The equivalence map costs the same in both; the rest is a cheaper correction format, and two streams Zucchini sends that do not pay for themselves on this pair.

Every layer after that is a change to the method, and each has to buy its accuracy for less than it costs to describe: the encoder measures each proposal against the real target, and the plan only includes what paid. The sections below take the layers in the same order; the small chart under each heading marks which one it covers.

Rebuilding the relocation table

This is the first change to Zucchini's method, and the biggest single step in the chart.

Chrome's .rela.dyn is 26 MB: 1.1 million relative relocations, each saying "at load time, write this address into that slot". When code and data move, both columns change through the whole table, and a byte-level view of it, Zucchini's included, has almost nothing to copy.

Zucchini treats each entry's slot address as a reference and translates it; the addend it copies as bytes, and its source carries a TODO to handle it. On this table that leaves every addend wrong, nearly a third of its patch.

The obvious fix is to treat the addend as the pointer it is and translate it the way Zucchini translates its other references, old row to new row through the equivalence map. That gets one addend in nine right, hardly better than the bytes: the moment one relocation slides past another in sort order, every row after it is compared against the wrong entry, and nothing downstream recovers. What works is a join: correct the slot column first, which gives the decoder the exact new slot addresses, then use those slots as keys to match projected old addends to new entries.

Presage regenerates the table column by column. The slot column is a sorted address sequence and is sent as gaps. The addend column is pointers, projected through the address oracle (the decoder's own answer to where the bytes at an old address ended up) and joined on the rebuilt slots. With the equivalence map as the only oracle the join gets four addends in five exactly right; the next layer gets most of the rest. In the final patch the 26 MB table costs 81 KB, all of it plan: whatever the oracle gets wrong is corrected as an address, never as bytes.

One function, three bytes

Take v8::base::TimeTicks::Now(). Between the two releases it moved about 440 KB later in the file. Its body is 98 bytes, and three of them changed:

That is nearly all code churn in a release-to-release build: the same instructions with different addresses inside them, Percival's second-order change one instruction at a time. A byte differ pays for it in every one of the roughly 925,000 functions in the image.

The starting point already reproduces those three bytes most of the time: the equivalences copy the body and retarget the displacement through the equivalence map. For about one function in seven that comes out wrong, and this layer takes over. Usually the body was copied from the right place, but the displacements inside it were retargeted to the wrong one, because the equivalence map knows where bytes moved, not which function a call was to.

The plan carries a function map: which old function became which new one, and where each body now belongs. The encoder knows this because Chrome's publisher has the unstripped build on both sides; the client receives no symbols, only where each matched body came from and where it lands. The decoder walks each placed function, decodes its x86, and re-encodes every PC-relative displacement (calls, jumps, RIP-relative loads) against the new addresses. For TimeTicks::Now() that reproduces those three bytes from nothing.

The map has to be cheap or it cannot pay. Sent as plain addresses it would cost 1.32 MB compressed, more than the layer saves. So the plan does not send the list of old functions at all. Both sides enumerate it from the old image, from call targets, relocation targets and the 0xcc padding Clang leaves between functions, which together find 99% of them; the plan carries only the exceptions and a replay of what changed, which functions were dropped, reordered, resized or inserted. That brings the map to 155 KB. Anything the decoder can enumerate, the plan names rather than spells out, and anything it can derive, the plan does not name either.

Even at that price, the map on its own is a step backwards: retargeting every function through it predicts no better than the equivalences did, and the map still has to be paid for. What makes it pay is one bit per function, choosing whether the equivalence copy or the moved old body is the better starting point. Neither wins everywhere. Equivalences preserve the compiler's local layout, including the islands of data it emits between functions; function identity wins when the byte matcher has grabbed the wrong copy of near-identical code, which identical-code folding (ICF) makes common.

The map is also what finishes the relocation table. A displacement only needs some equivalent destination; a pointer needs the right identity, and ICF means one old address can stand for several functions that the new build split apart. With the map naming which one, 99% of addends come out exact and the addend column shrinks six-fold.

Tables the ELF doesn't label

.eh_frame is the same problem in a smaller section. Each frame record has a PC-relative start address that moves with its function, and the rest of the record usually doesn't. The decoder retargets the address field through the oracle and keeps the rest of the record, then regenerates .eh_frame_hdr, a sorted index over those records, rather than patching a second copy of the same facts.

.rodata is harder because nothing labels its address tables. Clang's switch jump tables are arrays of 32-bit offsets relative to the table's own base, indistinguishable from any other aligned integers. You can still guess: a run of aligned words that all land inside .text when added to the table base is probably a jump table. That test finds some 27,000 candidate tables.

Rewriting all of them made the patch worse. Detection says what a region could be, not whether the rewrite beats the bytes the equivalence layer already supplied. So the encoder tries each candidate against the real target and ships a selection bitmap: about 3,600 tables are retargeted and the rest are left alone. The decoder then places the kept tables with a running cursor, each starting where the previous one ended, rather than by projecting their old addresses, with one small correction wherever the cursor is off.

Correcting what can't be rebuilt

After all of the structural layers the decoder has an exact-length prediction that is 99.4% correct, and the remaining 0.6% still has shape. A delta format, which searches the prediction for long runs of the target's bytes, is the wrong tool for it. What is left in .text is half a million short edits, and those are cheaper as a plain list: the gap since the last edit, its length and the replacement bytes, each as its own column. Splitting the replacement bytes further by run length costs nothing to signal, because the decoder already knows each run's length, and a one-byte opcode fix has nothing in common with a four-byte displacement fix. Together that is 157 KB.

The next layer went back to addresses. About a quarter of the wrong .text bytes were four-byte displacement fields that resolved to the wrong place. The decoder can enumerate all 8.7 million such fields in its own prediction. Where many fields disagree about the same target, the plan corrects the mapping once; the stragglers get a signed per-field delta. The encoder rejects any remap that would break more fields than it fixes. The layer traded 292 KB of plan for 472 KB of correction, and address fields fell from a quarter of the wrong code bytes to 2%. The same treatment extended to the operand fields the retargeter never writes: immediates and stack-slot displacements paid for their columns, register-relative displacements did not, and the encoder ships only the classes that do.

The correction knows the prediction

Everything so far has used the prediction to build the file. The correction itself was then handed to an ordinary compressor, which sees a stream of replacement bytes and knows nothing about what they replace. But every correction byte sits on top of a predicted byte, and the two are related: a mispredicted displacement usually differs from the prediction in its low bytes only, and a recompiled instruction usually keeps its opcode and changes an operand.

The last layer is a small context-mixing arithmetic coder that models each correction byte given the predicted byte underneath it. The encoder offers it to every stream of the correction and keeps it wherever it beats the general compressor. In Chrome's .text it wins the run lengths and every column of short replacement bytes, and loses, as it should, on the gaps between edits, which have no prediction byte to condition on, and on the long runs of recompiled code, where the byte underneath predicts nothing. It costs decode time, about a second and a half per megabyte of correction, and it pays twice: once on the correction, and again run over the plan's own columns with each column's structure as its context. That is the last bar of the chart: 2.26 MB, 38% of Zucchini's patch.

What remains

Every layer is verified the same way: replay the plan, apply the correction, compare the 291 MB result to the target byte for byte. Applying the patch takes 2.7 seconds. For this pair, rebuilding the second-order changes instead of transmitting them cut an already executable-aware patch by more than half.

What remains is not an address problem. More than a third of the final patch is .text correction, and the largest single item in it is 400 KB of replacement bytes for runs of five bytes or more: recompiled code, not addresses. Most of those bytes sit in the roughly 9,500 functions the compiler resized between the two builds. The commit log between the two tags explains the scale: eight bug fixes touching about thirty source files, and six rolls of the Linux PGO profile. Thirty files don't resize 9,500 functions; a new profile does, because it drives inlining and hot/cold splitting across the whole binary. The bytes still to send are mostly the compiler reacting to a profile, not the fixes users are updating for. Predicting that is a different problem from predicting where things landed.

Where to go from here

I focused on Chrome as the test case because it's what Courgette and Zucchini were built for, and I wanted to see how far a structure-aware patch could be pushed in a direct comparison. But the approach is not specific to it. The core of presage builds a prediction from a plan and encodes the bytes that prediction got wrong; everything it understands about x86-64 code and ELF tables lives in one structure module, which can be combined with modules that model additional toolchain-specific structure. Go binaries are a natural next target: less than half of a typical Go executable is machine code, and the rest is metadata the linker derives from it, so structure-aware patches end up dozens of times smaller than general-purpose differs produce. That is the subject of the next post.

presage is on GitHub at wjordan/presage.