Einführung
Für ein neues Projekt musste ich Level-Daten aus dem klassischen Videospiel
Super Mario Bros (SMB) von 1985 extrahieren. Insbesondere wollte ich die Hintergrundgrafiken der einzelnen Ebenen des Spiels ohne Benutzeroberfläche, bewegte Sprites usw. extrahieren.
Natürlich könnte ich nur die Bilder aus dem Spiel kleben und möglicherweise den Prozess mithilfe von Bildverarbeitungstechniken automatisieren. Interessanter erschien mir jedoch die unten beschriebene Methode, mit der Sie die Ebenenelemente untersuchen können, die mit Screenshots nicht erhalten werden können.
In der ersten Phase des Projekts lernen wir die Assembler-Sprache 6502 und einen in Python geschriebenen Emulator. Den vollständigen Quellcode finden Sie
hier .
Quellcode-Analyse
Das Reverse Engineering eines Programms ist viel einfacher, wenn Sie seinen Quellcode haben, und wir haben SMB-Quellen in Form von
17.000 Zeilen Assembler-Code 6502 (NES-Prozessor), die von doppelganger veröffentlicht wurden. Da Nintendo nie eine offizielle Quellversion veröffentlicht hat, wurde der Code durch Zerlegen des SMB-Maschinencodes erstellt, wobei die Bedeutung jedes Teils schmerzhaft entschlüsselt, Kommentare und aussagekräftige symbolische Namen hinzugefügt wurden.
Nachdem ich eine schnelle Suche in der Datei durchgeführt hatte, fand ich etwas Ähnliches wie die benötigten Level-Daten:
;level 1-1
L_GroundArea6:
.db $50, $21
.db $07, $81, $47, $24, $57, $00, $63, $01, $77, $01
.db $c9, $71, $68, $f2, $e7, $73, $97, $fb, $06, $83
.db $5c, $01, $d7, $22, $e7, $00, $03, $a7, $6c, $02
.db $b3, $22, $e3, $01, $e7, $07, $47, $a0, $57, $06
.db $a7, $01, $d3, $00, $d7, $01, $07, $81, $67, $20
.db $93, $22, $03, $a3, $1c, $61, $17, $21, $6f, $33
.db $c7, $63, $d8, $62, $e9, $61, $fa, $60, $4f, $b3
.db $87, $63, $9c, $01, $b7, $63, $c8, $62, $d9, $61
.db $ea, $60, $39, $f1, $87, $21, $a7, $01, $b7, $20
.db $39, $f1, $5f, $38, $6d, $c1, $af, $26
.db $fdWenn Sie mit Assembler nicht vertraut sind, erkläre ich Folgendes: All dies bedeutet einfach "Fügen Sie einen solchen Satz von Bytes in das kompilierte Programm ein und lassen Sie dann andere Teile des Programms mit dem Symbol
L_GroundArea6 darauf verweisen". Sie können dieses Fragment als Array verwenden, in dem jedes Element ein Byte ist.
Das erste, was Sie feststellen können, ist, dass das Datenvolumen sehr klein ist (ca. 100 Byte). Daher schließen wir alle Arten der Codierung aus, sodass Sie Blöcke beliebig auf der Ebene platzieren können. Nachdem ich ein bisschen gesucht hatte, stellte ich fest, dass diese Daten (nach mehreren indirekten Adressierungsvorgängen) in
AreaParserCore gelesen wurden . Diese Unterprozedur ruft wiederum viele andere Unterprozeduren auf und ruft letztendlich bestimmte Unterprozeduren für jeden in der Szene zulässigen Objekttyp auf (z. B.
StaircaseObject ,
VerticalPipe ,
RowOfBricks ):
AreaParserCore für AreaParserCoreDie Prozedur schreibt in
MetatileBuffer : einen 13-Byte-Speicherabschnitt, der eine Spalte von Blöcken in einer Ebene ist, von denen jedes Byte einen separaten Block darstellt. Eine Metatile ist ein 16x16-Block, aus dem die Hintergründe eines SMB-Spiels bestehen:
Ebene mit Rechtecken, die um Metatile kreisenSie werden als Metadateien bezeichnet, da jede aus vier 8x8-Pixel-Kacheln besteht, aber dazu weiter unten mehr.
Die Tatsache, dass der Decoder mit vordefinierten Objekten arbeitet, erklärt die geringe Größe des Levels: Level-Daten sollten sich nur auf die Objekttypen und deren Position beziehen, z. B. „Positionieren Sie das Rohr am Punkt (20, 16), eine Anzahl von Blöcken am Punkt (10, 5), ... ". Dies bedeutet jedoch, dass viel Code erforderlich ist, um Rohdaten in Metadateien umzuwandeln.
Das Portieren dieser Codemenge zum Erstellen eines eigenen Level-Unpackers würde zu viel Zeit in Anspruch nehmen. Versuchen wir also einen anderen Ansatz.
py65emu
Wenn wir eine Schnittstelle zwischen Python und der Assembler-Sprache 6502 hätten, könnten wir die
AreaParserCore für jede
AreaParserCore aufrufen und dann verständlicheres Python verwenden, um die
AreaParserCore in das gewünschte Bild zu konvertieren.
Dann erscheint
py65emu in der Szene - ein prägnanter 6502-Emulator mit einer Python-Oberfläche. So wird in py65emu dieselbe Speicherkonfiguration wie in NES konfiguriert:
from py65emu.cpu import CPU from py65emu.mmu import MMU
Danach können wir einzelne Anweisungen mit der Methode
cpu.step() ausführen, den Speicher mit
mmu.read() , die Maschinenregister mit
cpu.ra ,
cpu.r.pc usw. untersuchen. Außerdem können wir mit
mmu.write() in den Speicher schreiben.
Es ist erwähnenswert, dass dies nur ein NES-Prozessor-Emulator ist: Er emuliert keine andere Hardware, wie z. B. PPU (Picture Processing Unit), und kann daher nicht zum Emulieren des gesamten Spiels verwendet werden. Es sollte jedoch ausreichen, die Parsing-Unterprozedur aufzurufen, da keine anderen Hardwaregeräte außer der CPU und dem Speicher verwendet werden.
Es ist geplant, die CPU wie oben gezeigt zu konfigurieren und dann für jede
AreaParserCore die Speicherpartitionen mit den für
AreaParserCore erforderlichen Eingabewerten zu
AreaParserCore ,
AreaParserCore und dann die
AreaParserCore zurückzulesen. Nach Abschluss dieser Vorgänge verwenden wir Python, um das Ergebnis zu einem fertigen Bild zusammenzusetzen.
Zuvor müssen wir jedoch die Liste in Assemblersprache in Maschinencode kompilieren.
x816
Wie im Quellcode angegeben, wird der Assembler mit x816 kompiliert. x816 ist ein MS-DOS-Assembler 6502, der von der
Homebrew- Community für NES- und ROM-Hacker verwendet wird. Es funktioniert hervorragend unter
DOSBox .
Zusammen mit dem ROM des Programms, das für py65emu erforderlich ist, erstellt der x816-Assembler eine Zeichendatei, die Zeichen ihrem Speicherort im Adressraum der CPU zuordnet. Hier ist ein Ausschnitt aus der Datei:
AREAPARSERCORE = $0093FC ; <> 37884, statement #3154
AREAPARSERTASKCONTROL = $0086E6 ; <> 34534, statement #1570
AREAPARSERTASKHANDLER = $0092B0 ; <> 37552, statement #3035
AREAPARSERTASKNUM = $00071F ; <> 1823, statement #141
AREAPARSERTASKS = $0092C8 ; <> 37576, statement #3048Hier sehen wir, dass auf die
AreaParserCore Funktion im Quellcode unter
0x93fc zugegriffen werden
0x93fc .
Der Einfachheit halber habe ich einen Symboldateiparser geschrieben, der mit Symbolnamen und -adressen übereinstimmt:
sym_file = SymbolFile('SMBDIS.SYM') print("0x{:x}".format(sym_file['AREAPARSERCORE']))
Unterverfahren
Wie im obigen Plan angegeben, möchten wir lernen, wie die
AreaParserCore von Python aus
AreaParserCore .
Um die Mechanik eines Unterverfahrens zu verstehen, untersuchen wir ein kurzes Unterverfahren und die entsprechende Herausforderung:
WritePPUReg1: sta PPU_CTRL_REG1 ; A 1 PPU sta Mirror_PPU_CTRL_REG1 ; rts ... jsr WritePPUReg1
Der
jsr (Sprung zum Unterprogramm, "Sprung zum Unterprogramm")
jsr PC-Register auf den Stapel und weist ihm den Adresswert zu, auf den sich
WritePPUReg1 bezieht. Das PC-Register teilt dem Prozessor die Adresse des nächsten zu
jsr Befehls mit, so dass der nächste Befehl, der nach dem
jsr ausgeführt wird, die erste Zeile von
WritePPUReg1 .
Am Ende des Unterprogramms wird die Anweisung
rts ausgeführt (Rückgabe vom Unterprogramm, "Rückgabe vom Unterprogramm"). Dieser Befehl entfernt den gespeicherten Wert aus dem Stapel und speichert ihn im PC-Register, wodurch die CPU
jsr , den Befehl nach dem
jsr Aufruf auszuführen.
Eine großartige Funktion von Unterprozeduren besteht darin, dass Sie Inline-Aufrufe erstellen können, dh Unterprozeduraufrufe innerhalb von Unterprozeduren. Rücksprungadressen werden auf den Stapel verschoben und in der richtigen Reihenfolge angezeigt, genau wie bei Funktionsaufrufen in Hochsprachen.
Hier ist der Code zum Ausführen der Unterroutine von Python:
def execute_subroutine(cpu, addr): s_before = cpu.rs cpu.JSR(addr) while cpu.rs != s_before: cpu.step() execute_subroutine(cpu, sym_file['AREAPARSERCORE'])
Der Code speichert den aktuellen Wert der Stapelzeigerregister, emuliert einen
jsr Aufruf und führt dann Anweisungen aus, bis der Stapel auf seine ursprüngliche Höhe zurückkehrt, was erst nach der Rückgabe der ersten Unterprozedur geschieht. Dies ist nützlich, da wir jetzt die Möglichkeit haben, 6502-Subroutinen direkt von Python aus aufzurufen.
Wir haben jedoch etwas vergessen: Wie werden Eingabewerte für diese Unterprozedur übergeben? Wir müssen der Prozedur mitteilen, welche Ebene wir rendern möchten und welche Spalte wir analysieren müssen.
Im Gegensatz zu Funktionen in Hochsprachen können Unterprogramme der Assemblersprache 6502 keine explizit angegebenen Eingabedaten empfangen. Stattdessen wird die Eingabe übertragen, indem Speicherplätze irgendwo vor dem Aufruf angegeben werden, die dann innerhalb des Unterprozeduraufrufs gelesen werden. Angesichts der Größe von
AreaParserCore ist das Reverse Engineering der erforderlichen Eingabe durch einfaches Betrachten des Quellcodes sehr komplex und fehleranfällig.
Valgrind für NES?
Um einen Weg zu finden, die Eingabewerte von
AreaParserCore zu bestimmen, habe ich das
Memcheck- Tool für Valgrind als Beispiel verwendet. Memcheck erkennt Zugriffsvorgänge auf nicht initialisierten Speicher, indem der Schattenspeicher parallel zu jedem Fragment des tatsächlich zugewiesenen Speichers gespeichert wird. Der Schattenspeicher zeichnet auf, ob eine Aufzeichnung in den entsprechenden realen Speicher erfolgt ist. Wenn das Programm an die Adresse liest, an die es nie geschrieben hat, wird ein nicht initialisierter Speicherfehler ausgegeben. Wir können
AreaParserCore mit einem Tool
AreaParserCore , das uns sagt, welche Eingaben festgelegt werden müssen, bevor die
AreaParserCore .
Tatsächlich ist das Schreiben einer einfachen Memcheck-Version für py65emu sehr einfach:
def format_addr(addr): try: symbol_name = sym_file.lookup_address(addr) s = "0x{:04x} ({}):".format(addr, symbol_name) except KeyError: s = "0x{:04x}:".format(addr) return s class MemCheckMMU(MMU): def __init__(self, *args, **kwargs): super().__init__(*args, **kwargs) self._uninitialized = array.array('B', [1] * 2048) def read(self, addr): val = super().read(addr) if addr < 2048: if self._uninitialized[addr]: print("Uninitialized read! {}".format(format_addr(addr))) return val def write(self, addr, val): super().write(addr, val) if addr < 2048: self._uninitialized[addr] = 0
Hier haben wir die Speicherverwaltungseinheit (MMU) von py65emu verpackt. Diese Klasse enthält ein nicht
_uninitialized Array, dessen Elemente uns mitteilen, ob es jemals in das entsprechende Byte des emulierten RAM geschrieben wurde. Bei einem nicht initialisierten Lesevorgang werden die Adresse des ungültigen Lesevorgangs und der Name des entsprechenden Zeichens angezeigt.
Hier sind die Ergebnisse der
execute_subroutine(sym_file['AREAPARSERCORE']) MMU beim Aufruf von
execute_subroutine(sym_file['AREAPARSERCORE']) :
Uninitialized read! 0x0728 (BACKLOADINGFLAG):
Uninitialized read! 0x0742 (BACKGROUNDSCENERY):
Uninitialized read! 0x0741 (FOREGROUNDSCENERY):
Uninitialized read! 0x074e (AREATYPE):
Uninitialized read! 0x075f (WORLDNUMBER):
Uninitialized read! 0x0743 (CLOUDTYPEOVERRIDE):
Uninitialized read! 0x0727 (TERRAINCONTROL):
Uninitialized read! 0x0743 (CLOUDTYPEOVERRIDE):
Uninitialized read! 0x074e (AREATYPE):
...Wenn Sie sich den Code ansehen, können Sie sehen, dass viele dieser Werte von der
InitializeArea Unterprozedur festgelegt werden. Führen Sie das Skript also erneut aus und rufen Sie zuerst diese Funktion auf. Wenn wir diesen Vorgang wiederholen, kommen wir zu der folgenden Abfolge von Anrufen, für die nur die Weltnummer und die Bereichsnummer erforderlich sind:
mmu.write(sym_file['WORLDNUMBER'], 0)
Der Code schreibt die ersten 48 Spalten der World 1-1-Ebene in
metatile_data , wobei die
IncrementColumnPos metatile_data , um die internen Variablen zu erhöhen, die zum Verfolgen der aktuellen Spalte erforderlich sind.
Und hier ist der Inhalt von
metatile_data , der Screenshots aus dem Spiel überlagert ist (Bytes mit dem Wert 0 werden nicht angezeigt):
Offensichtlich
metatile_data eindeutig mit Hintergrundinformationen überein.
Metagrafiken
(Um das Endergebnis zu sehen, können Sie sofort mit dem Abschnitt „Alles miteinander verbinden“ fortfahren.)
Lassen Sie uns nun herausfinden, wie die empfangene Anzahl von Metadateien in echte Bilder umgewandelt werden kann. Die unten beschriebenen Schritte wurden erfunden, indem die Quellen analysiert und die Dokumentation mit dem erstaunlichen
Nesdev-Wiki gelesen wurden .
Um zu verstehen, wie jede Metatilität gerendert wird, müssen wir zunächst über NES-Farbpaletten sprechen. Die NES-Konsolen-PPU kann im Allgemeinen 64 verschiedene Farben rendern, Schwarz wird jedoch mehrmals dupliziert (
Einzelheiten siehe
Nesdev ):
Jede Mario-Stufe kann nur 10 dieser 64 Farben für den Hintergrund verwenden, die in 4 Vierfarbenpaletten unterteilt sind. Die erste Farbe ist immer die gleiche. Hier sind vier Paletten für World 1-1:
Schauen wir uns nun ein binäres Beispiel für eine Metadateinummer an. Hier ist die metatile Zahl der geknackten Steinfliesen, bei der es sich um Land der Stufe 1-1 handelt:
Der Palettenindex gibt an, welche Palette beim Rendern der Metatile verwendet werden soll (in unserem Fall Palette 1). Der Palettenindex ist auch der Index der folgenden zwei Arrays:
MetatileGraphics_Low:
.db <Palette0_MTiles, <Palette1_MTiles, <Palette2_MTiles, <Palette3_MTiles
MetatileGraphics_High:
.db >Palette0_MTiles, >Palette1_MTiles, >Palette2_MTiles, >Palette3_MTilesDie Kombination dieser beiden Arrays ergibt eine 16-Bit-Adresse, die in unserem Beispiel auf
Palette1_Mtiles :
Palette1_MTiles:
.db $a2, $a2, $a3, $a3 ;vertical rope
.db $99, $24, $99, $24 ;horizontal rope
.db $24, $a2, $3e, $3f ;left pulley
.db $5b, $5c, $24, $a3 ;right pulley
.db $24, $24, $24, $24 ;blank used for balance rope
.db $9d, $47, $9e, $47 ;castle top
.db $47, $47, $27, $27 ;castle window left
.db $47, $47, $47, $47 ;castle brick wall
.db $27, $27, $47, $47 ;castle window right
.db $a9, $47, $aa, $47 ;castle top w/ brick
.db $9b, $27, $9c, $27 ;entrance top
.db $27, $27, $27, $27 ;entrance bottom
.db $52, $52, $52, $52 ;green ledge stump
.db $80, $a0, $81, $a1 ;fence
.db $be, $be, $bf, $bf ;tree trunk
.db $75, $ba, $76, $bb ;mushroom stump top
.db $ba, $ba, $bb, $bb ;mushroom stump bottom
.db $45, $47, $45, $47 ;breakable brick w/ line
.db $47, $47, $47, $47 ;breakable brick
.db $45, $47, $45, $47 ;breakable brick (not used)
.db $b4, $b6, $b5, $b7 ;cracked rock terrain <--- This is the 20th line
.db $45, $47, $45, $47 ;brick with line (power-up)
.db $45, $47, $45, $47 ;brick with line (vine)
.db $45, $47, $45, $47 ;brick with line (star)
.db $45, $47, $45, $47 ;brick with line (coins)
...Wenn Sie den metatilen Index mit 4 multiplizieren, wird er zum Index dieses Arrays. Die Daten sind in 4 Datensätzen pro Zeile formatiert, daher bezieht sich unser Beispiel metatile auf die zwanzigste Zeile, die mit einem Kommentar zum
cracked rock terrain gekennzeichnet ist.
Die vier Einträge dieser Zeile sind tatsächlich Kachelkennungen: Jede Metatile besteht aus vier 8x8-Pixel-Kacheln, die in der folgenden Reihenfolge angeordnet sind - oben links, unten links, oben rechts und unten rechts. Diese Kennungen werden direkt an die NES-PPU-Konsole übergeben. Die Kennung bezieht sich auf 16 Datenbytes in der CHR-ROM-Konsole, und jeder Datensatz beginnt mit der Adresse
0x1000 + 16 * < > :
0x1000 + 16 * 0xb4: 0b01111111 0x1000 + 16 * 0xb5: 0b11011110
0x1001 + 16 * 0xb4: 0b10000000 0x1001 + 16 * 0xb5: 0b01100001
0x1002 + 16 * 0xb4: 0b10000000 0x1002 + 16 * 0xb5: 0b01100001
0x1003 + 16 * 0xb4: 0b10000000 0x1003 + 16 * 0xb5: 0b01100001
0x1004 + 16 * 0xb4: 0b10000000 0x1004 + 16 * 0xb5: 0b01110001
0x1005 + 16 * 0xb4: 0b10000000 0x1005 + 16 * 0xb5: 0b01011110
0x1006 + 16 * 0xb4: 0b10000000 0x1006 + 16 * 0xb5: 0b01111111
0x1007 + 16 * 0xb4: 0b10000000 0x1007 + 16 * 0xb5: 0b01100001
0x1008 + 16 * 0xb4: 0b10000000 0x1008 + 16 * 0xb5: 0b01100001
0x1009 + 16 * 0xb4: 0b01111111 0x1009 + 16 * 0xb5: 0b11011111
0x100a + 16 * 0xb4: 0b01111111 0x100a + 16 * 0xb5: 0b11011111
0x100b + 16 * 0xb4: 0b01111111 0x100b + 16 * 0xb5: 0b11011111
0x100c + 16 * 0xb4: 0b01111111 0x100c + 16 * 0xb5: 0b11011111
0x100d + 16 * 0xb4: 0b01111111 0x100d + 16 * 0xb5: 0b11111111
0x100e + 16 * 0xb4: 0b01111111 0x100e + 16 * 0xb5: 0b11000001
0x100f + 16 * 0xb4: 0b01111111 0x100f + 16 * 0xb5: 0b11011111
0x1000 + 16 * 0xb6: 0b10000000 0x1000 + 16 * 0xb7: 0b01100001
0x1001 + 16 * 0xb6: 0b10000000 0x1001 + 16 * 0xb7: 0b01100001
0x1002 + 16 * 0xb6: 0b11000000 0x1002 + 16 * 0xb7: 0b11000001
0x1003 + 16 * 0xb6: 0b11110000 0x1003 + 16 * 0xb7: 0b11000001
0x1004 + 16 * 0xb6: 0b10111111 0x1004 + 16 * 0xb7: 0b10000001
0x1005 + 16 * 0xb6: 0b10001111 0x1005 + 16 * 0xb7: 0b10000001
0x1006 + 16 * 0xb6: 0b10000001 0x1006 + 16 * 0xb7: 0b10000011
0x1007 + 16 * 0xb6: 0b01111110 0x1007 + 16 * 0xb7: 0b11111110
0x1008 + 16 * 0xb6: 0b01111111 0x1008 + 16 * 0xb7: 0b11011111
0x1009 + 16 * 0xb6: 0b01111111 0x1009 + 16 * 0xb7: 0b11011111
0x100a + 16 * 0xb6: 0b11111111 0x100a + 16 * 0xb7: 0b10111111
0x100b + 16 * 0xb6: 0b00111111 0x100b + 16 * 0xb7: 0b10111111
0x100c + 16 * 0xb6: 0b01001111 0x100c + 16 * 0xb7: 0b01111111
0x100d + 16 * 0xb6: 0b01110001 0x100d + 16 * 0xb7: 0b01111111
0x100e + 16 * 0xb6: 0b01111111 0x100e + 16 * 0xb7: 0b01111111
0x100f + 16 * 0xb6: 0b11111111 0x100f + 16 * 0xb7: 0b01111111CHR-ROM ist ein schreibgeschützter Speicher, auf den nur PPU zugreifen kann. Es ist vom PRG-ROM getrennt, in dem der Programmcode gespeichert ist. Daher sind die obigen Daten im Quellcode nicht verfügbar und müssen aus dem Speicherauszug des ROM des Spiels abgerufen werden.
16 Bytes für jede Kachel bilden eine 2x-8x8-Kachel: Das erste Bit sind die ersten 8 Bytes und das zweite sind die zweiten 8 Bytes:
21111111 13211112
12222222 23122223
12222222 23122223
12222222 23122223
12222222 23132223
12222222 23233332
12222222 23111113
12222222 23122223
12222222 23122223
12222222 23122223
33222222 31222223
11332222 31222223
12113333 12222223
12221113 12222223
12222223 12222233
23333332 13333332Binden Sie diese Daten an Palette 1:
... und kombinieren Sie die Stücke:
Endlich haben wir eine gerenderte Kachel bekommen.
Alles zusammenfügen
Wenn Sie diesen Vorgang für jede Metadatei wiederholen, erhalten Sie eine vollständig gerenderte Ebene.
Und dank dessen konnten wir mit Python Grafiken auf SMB-Ebene extrahieren!