Slap

Ik heb een ROM-patcher gemaakt: slap. Het is een goed hulpmiddel; het is gratis/FOSS, multiplatform, ondersteunt twintig formaten, is vriendelijk, snel en maakt kleine patches.

Ik heb het gebouwd omdat ik geen CLI-tool voor Linux kon vinden die me beviel en die goed samenwerkte met de patches die ik nodig had om mijn FXPak voor te bereiden. Daarom is het mede gebouwd voor gebruik in scripting. Tegelijkertijd is het zeer communicatief; het geeft gestructureerde fouten, waarschuwingen en observaties voor allerlei situaties.

De tool gaat geen uitgangspunten over een patch. Ik ben er vrij zeker van dat alles wat niet ongeldig is, correct wordt afgehandeld. Als iets verkeerd gevormd is, of coherent is maar iets verrassends dreigt te doen, geeft slap precies aan wat er aan de hand is en waar.

Je kunt het uitproberen in een CLI-versie of een webversie. De tool is geschreven in Haskell en Rust, wat het proces om het goed in de browser te laten werken interessant maakte.

De tool kent zes commando's (verbs):

• apply — patch + originele ROM → gewijzigde ROM
• create — twee ROM's → patch
• undo — patch + gewijzigde ROM → originele ROM
• convert — patch in het ene formaat → patch in een ander formaat
• explain — patch → leesbare beschrijving van wat de patch doet
• info — patch → metadata van de patch

Appendix

Correctheid

Voor elke realistische patch is "we kunnen deze correct toepassen" een gegeven. Maar waar liggen de grenzen van wat acceptabel is? Voor elk formaat moesten we ons per "eigenschap X" afvragen:

• Is eigenschap X onderdeel van de specificatie ('spec')?
• Is het een eigenaardigheid die afhangt van de specifieke implementatie door de gebruiker?
• Is het een technische mogelijkheid die desondanks geen deel uitmaakt van de specificatie?

Enkele voorbeelden:

• Wat geldt als een correct gevormde IPS-patch? Kunnen records overlappen? Kunnen ze niet-monotoon zijn? Als het antwoord op beide "ja" is, maakt dit het toepassen minder voor de hand liggend dan het aanvankelijk leek. En wat betekent het om de truncatie-marker te respecteren als deze zegt dat het bestand moet worden "getrunceerd" naar een grootte die groter is dan het inputbestand?
• IPS kan niet adresseren voorbij 16MiB. Behalve in vreemde randgevallen waarbij alleen het begin van een bestand wordt gewijzigd, kan IPS dus alleen wijzigingen beschrijven in bestanden tot 16MiB. Het kan niet verder kijken dan 16MiB, maar het kan wel een record beschrijven dat binnen de grenzen begint maar schrijft tot voorbij die 16MiB. Dit is coherent en heeft voorspelbare resultaten, maar is erg vreemd. Is dit "volgens de specificatie"? We passen deze patches toe, maar we spreken af ze niet zelf te creëren.
• EBP ondersteunt JSON-metadata, wat wordt gebruikt om vier strings op te slaan. De expressieve kracht hiervan is veel groter dan wat er in de praktijk mee gedaan wordt. Is de specificatie onjuist als er iets anders aanwezig is dan die strings? Of is het omgekeerde het geval: arbitrary oneindige nesting? Kunnen we er tenminste vanuit gaan dat het UTF-8 moet zijn?
• NINJA2 heeft een interessante "normalisatie"-functie. Als de input ROM nog niet in een "normale vorm" is (gedeinterleaved, geen header, z64 byte-volgorde voor N64, etc.), moet de patcher deze in die vorm brengen. Als de patch zegt dat normalisatieprocedure 'foo' moet worden toegepast en de patcher kent procedure 'foo' niet, weigert hij de patch toe te passen. Het probleem is dat dit formaat ook checksums van de input opslaat, gebaseerd op de genormaliseerde vorm. Dit lijkt mij te conservatief; we zouden ten minste moeten controleren of het inputbestand al in de verwachte vorm is voordat we het opgeven.
• BPS lijkt het toe te staan om "dingen te kopiëren uit andere delen van de output, voordat er iets is geplaatst". Is dit coherent of niet?
• PPF3 houdt geen bestandsgroottes bij en staat undo toe. De datastroom kan groei beschrijven, maar op een manier waardoor undo incoherent wordt als dat gebeurt. De originele tool lijkt groei of krimp te willen blokkeren, maar ik vermoed dat dit niet goed werkte. Wat doen we als de gebruiker een PPF3 creëert die van grootte verandert en undo-data bevat? Vanwege structurele redenen in het formaat is het onmogelijk om te detecteren of een gebruiker probeert te trunceren via de undo-functie.

Bij het creëren zijn we conservatief: we genereren bestanden die door elk hulpmiddel correct kunnen worden toegepast. Bij het toepassen hebben we geprobeerd het volledige "expressieve bereik" van elk formaat te ondersteunen. Dit betekende veel tijd besteden aan nadenken over hoe er iets mis zou kunnen gaan, zoals een datastroom die incoherente instructies representeert. Een groot deel van die tijd ging naar het zorgen dat elke manier waarop een patch foutief gevormd kan zijn, met de juiste naam wordt aangeroepen.

Tekstcodering

Sommige formaten kunnen tekstmetadata opslaan. Ik verwachtte dat deze uitsluitend ASCII zouden zijn, maar dat is niet het geval. We outputten UTF-8 en zijn er vrij zeker van dat dit in alle gevallen "niet fout" is. De twee meest voorkomende regels die we tegenkomen zijn: "gebruik UTF-8" (prima) of "gebruik de systeempagina/codepage" (wat?). Dat laatste staat UTF-8 nog steeds toe, aangezien UTF-8 op moderne systemen de standaard systeempagina is.

Aan de lees- en weergavekant is het complexer. We bieden diverse alternatieve decoderingsopties aan voor het geval UTF-8 niet de juiste manier is om de patch te lezen.

We beveiligen en saniteren wat we decoderen/lezen. Een paar formaten hebben metadatavelden voor willekeurige data (niet willekeurige tekst, maar data). In de praktijk worden deze velden, indien gebruikt, gebruikt voor tekst. We willen deze velden niet volledig afsluiten van de gebruikelijke weergave en conversie-mechanismen, maar we willen ook geen controlekarakters uitvoeren uit een verdacht ingebed bestand. Onze aanpak: alles tonen, op niets reageren. Niet-printbare codepunten worden escaped weergegeven (bijv. <U+0007> in plaats van een beep), en een bytevolgorde die de gekozen codering niet kan decoderen, wordt U+FFFD met een waarschuwing over de locatie.

Benchmarks

Toelichting

Elk getal in de CLI-tabellen is inclusief het opstarten van het proces. De kleinste verschillen worden bepaald door een vloer van 10–25ms voor executie en runtime, niet door het patchen zelf.

We gebruiken vier paren bestanden: een GBC ROM (4MiB), een GBA ROM (16MiB), een N64 ROM (64MiB) en een disc-image (520MiB). Voor elk formaat waarbij we de referentietool kunnen scripten, maakt elke tool een patch van het paar en past deze vervolgens toe. De tijden zijn medianen van 'warme' runs. Elke output wordt byte-voor-byte gecontroleerd tegen het referentiepaar voordat de tijd wordt geteld.

In de cellen staat: slap / referentie.

• Getallen boven de vijftien seconden worden genoteerd als 15s+.
• Een lege cel betekent dat die combinatie niet is getest voor die grootte (IPS en EBP stoppen bij 16MiB).
• — betekent dat er een run was, maar dat er niets meetbaars is geproduceerd.
• PPF3 wordt vergeleken met de undo-data uitgeschakeld, conform de modus van de referentietool.

Creëren (tijd om een patch te maken)

Tijd in milliseconden (ms) of seconden (s)

Formaat / Referentie	4MiB	16MiB	64MiB	520MiB
ips / flips	18ms / 12ms	9ms / 21ms
ips32 / sips	15ms / 8ms	11ms / 17ms	38ms / 68ms	150ms / 413ms
ups / goUps	9ms / 12ms	11ms / 24ms	44ms / 99ms	198ms / 588ms
bps / flips	57ms / 327ms	103ms / 1.29s	1.55s / 11.94s	1.88s / 15s+
ppf3 / makeppf3	11ms / 10ms	19ms / 14ms	74ms / 57ms	487ms / 333ms
ninja1 / ninjaPhp	17ms / 41ms	45ms / 53ms	130ms / 241ms
ninja2 / ninja2Php	19ms / 145ms	50ms / 103ms	204ms / 685ms	1.47s / 1.59s
gdiff / javaxdelta	18ms / 136ms	12ms / 249ms	239ms / 1.27s	733ms / 10.76s
bsdiff / bsdiff	74ms / 560ms	110ms / 2.65s	682ms / 14.79s	3.57s / 15s+
xdelta1 / xdelta1	44ms / 41ms	45ms / 49ms	386ms / 270ms	1.62s / 1.33s
xdelta3 / xdelta3	76ms / 47ms	21ms / 34ms	398ms / 383ms	596ms / 326ms

Patch-grootte (gegenereerde bestanden)

Grootte van de patches gemaakt door slap / referentie

Formaat / Referentie	4MiB	16MiB	64MiB	520MiB
ips / flips	655KiB / 654KiB	16KiB / 16KiB
ips32 / sips	672KiB / 899KiB	18KiB / 23KiB	4.4MiB / 4.7MiB	388KiB / 613KiB
ups / goUps	888KiB / 888KiB	11KiB / 11KiB	4.5MiB / 4.5MiB	467KiB / 467KiB
bps / flips	276KiB / 272KiB	10KiB / 12KiB	1.9MiB / 1.8MiB	280KiB / —
ppf3 / makeppf3	922KiB / 937KiB	24KiB / 33KiB	4.6MiB / 4.9MiB	481KiB / 728KiB
ninja1 / ninjaPhp	888KiB / 899KiB	18KiB / 23KiB	4.4MiB / 4.7MiB
ninja2 / ninja2Php	891KiB / 903KiB	22KiB / 28KiB	4.4MiB / 4.7MiB	467KiB / 679KiB
gdiff / javaxdelta	600KiB / 747KiB	21KiB / 33KiB	1.9MiB / 1.9MiB	367KiB / 425KiB
bsdiff / bsdiff	204KiB / 215KiB	8KiB / 8KiB	1.9MiB / 1.8MiB	287KiB / —
xdelta1 / xdelta1	239KiB / 239KiB	13KiB / 17KiB	1.7MiB / 1.8MiB	275KiB / 279KiB
xdelta3 / xdelta3	218KiB / 236KiB	10KiB / 13KiB	1.7MiB / 1.7MiB	263KiB / 272KiB

Toepassen (snelheid van applicatie)

Tijd om de door slap gemaakte patch toe te passen: slap / referentie-applier

Formaat / Applier	4MiB	16MiB	64MiB	520MiB
ips / flips	20ms / 10ms	33ms / 30ms
ips32 / atmosphereIps	21ms / 9ms	32ms / 27ms	103ms / 103ms	835ms / 776ms
ups / goUps	15ms / 12ms	35ms / 30ms	126ms / 123ms	902ms / 918ms
bps / flips	34ms / 38ms	35ms / 136ms	122ms / 532ms	896ms / 4.2s
ppf3 / applyppf3	16ms / 30ms	31ms / 19ms	112ms / 109ms	837ms / 109ms
ninja1 / ninjaPhp	21ms / 15s+	60ms / 15s+	163ms / 15s+
ninja2 / ninja2Php	23ms / 65ms	64ms / 51ms	232ms / 232ms	1.82s / 1.48s
gdiff / javaxdelta	18ms / 48ms	33ms / 55ms	110ms / 165ms	830ms / 1.01s
bsdiff / bsdiff	44ms / 27ms	112ms / 59ms	471ms / 279ms	3.41s / 1.72s
xdelta1 / xdelta1	30ms / 19ms	65ms / 46ms	238ms / 174ms	1.84s / 1.18s
xdelta3 / xdelta3	35ms / 16ms	35ms / 32ms	152ms / 134ms	848ms / 843ms

Opmerking: sips en makeppf3 kunnen alleen patches creëren, dus voor ips32 en ppf3 wordt de referentie-applier van het formaat gebruikt.

Bij het toepassen verliezen we meer cellen dan we winnen; bij cartridge-groottes gaat het om verschillen van tientallen milliseconden. Elke applier hier past de patches van slap byte-perfect toe.

Kanttekeningen

• javaxdelta start een JVM binnen elke getimede aanroep. Die kosten domineren de resultaten bij 4MiB en worden ruis bij 520MiB; de library zelf is snel.
• applyppf3 en de ninja-appliers wijzigen een bestand in place in plaats van een nieuwe output te schrijven. Elke run krijgt daarom een vooraf gemaakte kopie, waarbij het maken van die kopie niet wordt getimed. Bij 520MiB bestaat het grootste deel van de applicatietijd van slap uit het schrijven van de 520MiB-output; een in-place applier schrijft alleen de gewijzigde bytes.

In de browser

De natuurlijke vergelijking voor web-slap is RomPatcher.js, de langdurige standaard binnen de community. We gebruiken drie paren: de 4MiB en 64MiB ROM's van hierboven, en een paar van 8MiB voor ips en ebp (die geen 64MiB kunnen adresseren). Beide kanten passen de patch van slap toe. De tijden zijn 'warm': één keer opgestart, bestanden al in het geheugen.

Creëren (web-slap / RomPatcher.js)

Formaat	4MiB	8MiB	64MiB
ips	45ms / 36ms	17ms / 219ms
ups	6ms / 43ms		75ms / 620ms
bps	60ms / 15s+		2.0s / 560ms
ppf	5ms / 31ms		72ms / 421ms
ebp	45ms / 37ms	17ms / 220ms
aps	6ms / 33ms		74ms / 412ms
rup	14ms / 61ms		214ms / 789ms

Bij 4MiB doorloopt RomPatcher.js in pure JavaScript dezelfde zoekopdracht als onze Rust-differ; dat verklaart de 15s+, waarbij de patch bijna net zo klein uitvalt. Boven de 4MiB (een drempelwaarde in de broncode) schakelt het over op een lineaire pass, wat veel sneller is maar een grotere patch schrijft.

Patch-grootte (web-slap / RomPatcher.js)

Formaat	4MiB	8MiB	64MiB
ips	655KiB / 886KiB	554KiB / 556KiB
ups	888KiB / 888KiB		4.5MiB / 4.5MiB
bps	276KiB / 308KiB		1.9MiB / 4.4MiB
ppf	922KiB / 936KiB		4.6MiB / 4.9MiB
ebp	655KiB / 886KiB	554KiB / 556KiB
aps	905KiB / 908KiB		4.5MiB / 4.6MiB
rup	891KiB / 903KiB		4.4MiB / 4.7MiB

Toepassen (web-slap / RomPatcher.js)

Formaat	4MiB	8MiB	64MiB
ips	22ms / 4ms	9ms / 14ms
ups	5ms / 12ms		82ms / 98ms
bps	29ms / 10ms		68ms / 48ms
ppf	3ms / 10ms		43ms / 59ms
ebp	22ms / 3ms	8ms / 19ms
aps	24ms / 11ms		37ms / 66ms
rup	12ms / 17ms		176ms / 198ms