context

A rom patcher takes a game file and applies a “patch” file to it. The patch is a recipe for turning the original file into some sort of variant of itself, such as a translation, a bugfix, or some other romhack thing. By convention, the way to distribute your game-modding work is to make and distribute a patch meant to be applied to the original.

I made a rom patcher. It’s good. It’s free/FOSS, multiplatform, supports twenty formats, cute, fast, and makes small patches.

I built it because I couldn’t find a CLI tool, available on Linux, that I cared for, that would play nice with applying the patches I needed to prep my FXPak. So it is in part built for scripting nicely. But it is also very chatty. It has structured errors/warnings/observations for all sorts of things.

It assumes nothing about a patch. I am fairly confident that it’ll handle anything that isn’t invalid gracefully; if something is malformed, or coherent but about to do something surprising, slap says exactly what and where.

Try it: cli version, web version. It is written in Haskell and Rust and this made getting it to work nicely in the browser, interesting.

It knows six verbs:

• apply — patch + original rom → modified rom

• create — two ROMs → patch

• undo — patch + modified rom → original rom

• convert — patch in one format → patch in another

• explain — patch → human-readable statement of what it does

• info — patch → its metadata

For any realistically likely to actually exist patch, “we can apply it, correctly” is of course a given. But what are the outer edges of what is acceptable? For each format we had to ask, for “property X”:

• is property x a ‘spec’ thing?

• an idiosyncratic up-to-the-applier kind of thing?

• a wire capability that is nonetheless not part of ‘the spec’?

some:

What counts as a well-formed IPS patch? Can the records overlap? Can they be non-monotonic? If the answer to both is “yes” then this makes applying it at least less obvious than it might have at first seemed. What does it mean to honor the truncation marker if it is saying to “truncate” to a size that is larger than the input file?

IPS can’t address past 16MiB, so barring some weird edge case about only modifying the start of a file: IPS can only describe changes in files up to 16MiB. Ish. It can’t see past 16MiB, but it can describe a record that begins in-bounds but writes moderately past that point, beyond 16MiB. This is coherent, has predictable results, and is super weird. Is it “in spec”? Of course we’ll apply these but do we agree to create them?

EBP supports JSON metadata, which it uses to store four strings. The expressive power is much greater than what is actually being done with it. Is “the spec” something is wrong if there is anything present in addition to the strings? Is it the reverse: arbitrary infinite nesting? Can we at least figure that it must be UTF-8?

NINJA2 has this cool “normalization” thing, where if the input rom is not already in a “normal form” (deinterleaved, no header, z64 byte order if N64, etc), the patcher is supposed to put it in that form. If the patch says to apply normalization procedure foo, and the patcher doesn’t know procedure foo (this is actually not contrived), it refuses to apply. The issue is: this format does also store checksums, of the input. The checksum is against the normalized form of that input. It seems to me like this is too conservative and we should at least check whether the input file is already in the expected shape, before giving up. Can I have my tool do that or is that me doing “embrace / extend / extinguish”?

BPS appears to allow “copying stuff from other parts of the output, before anything has been put there”. Is this coherent or no?

PPF3 doesn’t track file sizes, and allows undo. The wire can describe growth, but in a way where if you do so, undoing becomes incoherent. The OG tool looks to me like it intends to block actually doing growth or shrinking, but in a way that I suspect didn’t work. What do we do if the user creates a size-changing undo-bearing PPF3? What if they want to use the PPF3 undo feature; for format-structural reasons it is impossible to detect that the user is trying to truncate-via-undo.

and so on. On creation we are conservative: emit things any tool could apply just fine. On application we have attempted to support the entire “expressive range” of each format. Doing this means figuring out where “the line” is.

This meant a lot of time spent thinking about how something could go wrong: the wire able to represent incoherent instructions, for example. An outsized amount of that time went into making sure every way a patch can be malformed gets called by its name. If curious see Error.hs, ApplyError.hs, and VCDIFF.hs for the sorts of things we watch for.

Some formats can store text metadata. I went in expecting to find evidence in favor of some if not all of these being ASCII-only. Not so! We output UTF-8 and feel fairly confident that this is in all cases “not wrong”. The two things we see a lot of are either “in this format, the rule is use UTF-8” (great!), or “in this format, the rule is use ‘system codepage’” (whoa, what?). The latter still permits UTF-8: on a modern system, UTF-8 is the system codepage.

On the read/display side it is more involved. We provide a bunch of alternate decoding options in case UTF-8 is not how to read the patch.

We guard/sanitize what we decode/read. A few formats have metadata fields for arbitrary data. Not arbitrary text; arbitrary data. In practice if these fields are used at all, they are being used to store text. So we don’t want to firewall these fields off from the usual display and preservation-during-format-conversion machinery, but we also don’t want to read and then act on a bunch of control characters out of a suspicious embedded file. What we actually do: show everything, act on nothing. Unprintable codepoints are displayed escaped (<U+0007>, not a beep), and a byte sequence the chosen encoding cannot decode becomes U+FFFD, with a warning saying where.

to be clear

Every number in the CLI tables includes process startup, ours included. The smallest races are decided by a 10–25ms exec-and-runtime floor, not by patching.

Have some tables. These are sourced from the benchmark thing in the repo, which you can (in principle) run yourself.

We have four before/after pairs: a 4MiB GBC rom, a 16MiB GBA rom, a 64MiB N64 rom, a 520MiB disc image. For each format where we have a good way to script the reference tool, each tool creates a patch from the reference pair, and each tool applies. These are timed; times are medians of warm runs. Every output is checked byte-for-byte against the reference pair before its time counts.

• Each cell reads slap / reference.

• Anything that ran past fifteen seconds is written as 15s+.

• A blank cell is a pairing that wasn’t benched at that size. IPS and EBP cap out at 16MiB, hence.

• A — means a run happened and produced nothing to measure.

• ppf3 is compared with undo data off on both sides; the reference tool’s own mode.

creating

the patches themselves

applying

sips and makeppf3 only create, so in this table ips32 and ppf3 are compared against their format’s reference applier instead.

On application we lose more cells than we win; at cartridge sizes the gaps are tens of milliseconds. Every applier here takes slap’s patches byte-perfectly.

in fairness

• javaxdelta boots a JVM inside every timed call. That cost dominates its 4MiB numbers and fades to noise by 520MiB; the library itself is quick.

• applyppf3 and the ninja appliers modify a file in place instead of writing a fresh output, so each timed run is handed a pre-made copy, and making the copy is not timed. At 520MiB most of slap’s apply time is writing the 520MiB output; an in-place applier writes only the changed bytes. That row is two different jobs sharing a table.

in the browser

Web slap’s natural comparison is RomPatcher.js, the community’s longtime standard.

Three browser-sized pairs: the 4MiB and 64MiB roms from above, and an 8MiB pair for ips and ebp, which cannot address 64MiB.

Both sides apply slap’s patch; a blank cell means that pairing wasn’t benched at that size.

Both sides are timed warm: booted once, files already in memory. Unlike the CLI tables, startup is in none of these numbers.

At 4MiB, RomPatcher.js walks the same search our Rust differ walks, in pure JavaScript; that is the 15s+, and its patch comes out nearly as small. Above 4MiB (a threshold in its source) it switches to a linear pass, which is much quicker and writes a bigger patch. The trade lands in the patch table below.

The full grids, the harness itself, and the six CLI formats with no scriptable reference tool to race against are all in the results directory.