In short
- A patch stores instructions, mainly COPY (reuse bytes from the original) and ADD (insert new bytes).
- Instructions are grouped into windows, and each window can carry an Adler-32 checksum of its output.
- COPY instructions point at exact byte positions, so the source file must match exactly or the checksum fails.
- Patch size depends on how much new data there is, not on how big the file is.
The core idea: describe the difference
Say you have a 1 GB disc image and change a few menu texts. Sharing the whole modified image means sending a gigabyte. But nearly all of it is identical to the original, which the recipient already has. A delta patch sends only a description of the differences:
A worked example
Here’s a tiny “file” made of text, so you can see each byte. Spaces are shown as ·.
Original (source):
THE·QUICK·BROWN·FOX
Modified (target):
THE·QUICK·RED·FOX·JUMPS
Blue bytes already exist in the original; green bytes are new. A delta encoder like xdelta3 finds those matches and writes instructions like these:
| # | Instruction | Produces |
|---|---|---|
| 1 | COPY 10 bytes from source position 0 | THE QUICK |
| 2 | ADD 3 new bytes: RED | RED |
| 3 | COPY 4 bytes from source position 15 | FOX |
| 4 | ADD 6 new bytes: JUMPS | JUMPS |
Only the 9 new bytes are stored in full. The 14 copied bytes cost just a position and a length each. In a real 1 GB file, those copies can cover almost everything, which is why patches are often tiny.
VCDIFF also has a third instruction, RUN, which writes one byte repeatedly. It’s handy for padding and blank regions.
Why the source file must match exactly
Look at instruction 3: “copy 4 bytes from source position 15.” The patch trusts that position 15 of your original holds FOX. Now imagine someone has a slightly different original with one extra byte near the start:
THE··QUICK·BROWN·FOX
Every byte after the extra space has shifted by one. Instruction 3 now copies N·FO instead of ·FOX, and the rebuilt file is wrong. This is exactly what happens with a different revision, a headered ROM, or a disc dumped differently. The patch can’t know you meant “the same thing, shifted”. It only knows positions.
That’s the job of checksums.
Windows and checksums
Real files are too large to handle as a single list of instructions, so xdelta3 splits the output into windows, consecutive chunks that are encoded and decoded one after another. Each window records:
- which range of the source file it copies from (its source segment);
- the instructions, the new data to add, and the copy addresses;
- optionally, an Adler-32 checksum of the output that window should produce.
When you apply a patch, xdelta3 rebuilds a window, calculates the Adler-32 checksum of what it produced, and compares it with the stored value. If they differ, it stops with target window checksum mismatch. In Delta Patcher, that’s the “file you are trying to patch is not the right one” message. How to fix it.
The source window
To find matches, the encoder searches part of the original file at a time, called the source window. xdelta3’s default is 64 MB, which Delta Patcher uses when Src Window Size is set to Auto. If data in the modified file came from much further away in the original (because a large block was inserted earlier, say), the encoder may not find it within the window and stores it as new data instead. The patch still works; it’s just larger. When to raise the source window size.
Compression inside the patch
xdelta3 compresses a patch in two layers:
- Main compression (levels 0–9) controls how thoroughly the encoder searches for matches. Better matching means fewer ADD bytes.
- Secondary compression (lzma, djw, fgk or none) compresses the patch’s data, instruction and address sections after encoding.
Neither changes the result. A patch at level 0 with no secondary compression rebuilds exactly the same file as one at level 9 with LZMA; it’s just bigger.
The application header (patch descriptions)
VCDIFF allows a block of application-specific data at the start of a patch. xdelta3 normally stores file names there. Delta Patcher uses it for the Description field: it writes ^* followed by the Base64-encoded text, and when loading a patch, it decodes anything with that prefix and shows it in the Patch info tooltip. Patches without a description get the plain note “Created with Delta Patcher.”, which isn’t shown as a description.
Why patch size varies so much
| Change | Typical patch size | Why |
|---|---|---|
| Text edits in uncompressed data | Tiny | Almost everything becomes a COPY |
| Inserted data that shifts later content | Small | COPY instructions simply point to new positions |
| Edits inside compressed or encrypted archives | Large | A small change alters most following bytes, so little can be copied |
| Unrelated files | About the size of the target | Nothing matches; nearly everything is ADD |
What a patch does and doesn’t contain
A patch contains the new bytes (the ADD data) and references to the original. It doesn’t contain the copied parts of the original. That’s why patches are the normal way to share modifications: the recipient supplies their own original. It also means a patch is useless without the right original file.