Présentation
Pour un nouveau projet, j'avais besoin d'extraire des données de niveau du jeu vidéo
Super Mario Bros (SMB) de 1985. Plus précisément, je voulais extraire les graphiques d'arrière-plan de chaque niveau du jeu sans interface, sans sprites en mouvement, etc.
Bien sûr, je pouvais juste coller les images du jeu et, éventuellement, automatiser le processus en utilisant des techniques de vision industrielle. Mais il m'a semblé plus intéressant la méthode décrite ci-dessous, qui vous permet d'explorer les éléments de niveau qui ne peuvent pas être obtenus à l'aide de captures d'écran.
À la première étape du projet, nous apprendrons le langage assembleur 6502 et un émulateur écrit en Python. Le code source complet est disponible
ici .
Analyse du code source
L'ingénierie inverse de n'importe quel programme est beaucoup plus simple si vous avez son code source, et nous avons des sources SMB sous la forme de
17 000 lignes de code assembleur 6502 (processeur NES) publiées par doppelganger. Étant donné que Nintendo n'a jamais publié de version officielle, le code a été créé en désassemblant le code de la machine SMB, en déchiffrant péniblement la signification de chaque partie, en ajoutant des commentaires et des noms symboliques significatifs.
Après avoir effectué une recherche rapide sur le fichier, j'ai trouvé quelque chose de similaire aux données de niveau dont nous avions besoin:
;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 $fdSi vous n'êtes pas familier avec l'assembleur, alors je vais vous expliquer: tout cela signifie simplement "insérer un tel ensemble d'octets dans le programme compilé, puis autoriser d'autres parties du programme à s'y référer en utilisant le symbole
L_GroundArea6 ". Vous pouvez prendre ce fragment comme un tableau dans lequel chaque élément est un octet.
La première chose que vous pouvez remarquer est que le volume de données est très petit (environ 100 octets). Par conséquent, nous excluons tous les types de codage, ce qui vous permet de placer arbitrairement des blocs au niveau. Après avoir cherché un peu, j'ai trouvé que ces données sont lues (après plusieurs opérations d'adressage indirect) dans
AreaParserCore . Cette sous-procédure, à son tour, appelle de nombreuses autres sous-procédures, invoquant finalement des sous-procédures spécifiques pour chaque type d'objet autorisé dans la scène (par exemple,
StaircaseObject ,
VerticalPipe ,
RowOfBricks ):
AreaParserCore appel AreaParserCore pour AreaParserCoreLa procédure écrit dans
MetatileBuffer : une section de mémoire de 13 octets, qui est une colonne de blocs dans un niveau, dont chaque octet représente un bloc distinct. Un métatile est un bloc 16x16 à partir duquel les arrière-plans d'un jeu SMB sont constitués:
Niveau avec des rectangles entourés de métatilesIls sont appelés méta-fichiers, car chacun se compose de quatre tuiles de 8 x 8 pixels, mais plus à ce sujet ci-dessous.
Le fait que le décodeur fonctionne avec des objets prédéfinis explique la petite taille du niveau: les données de niveau doivent se référer uniquement aux types d'objets et à leur emplacement, par exemple, «positionner le tuyau au point (20, 16), un certain nombre de blocs au point (10, 5), ... ". Cependant, cela signifie qu'il faut beaucoup de code pour transformer les données de niveau brut en fichiers méta.
Porter cette quantité de code pour créer votre propre décompresseur de niveau prendrait trop de temps, alors essayons une approche différente.
py65emu
Si nous avions une interface entre Python et le langage assembleur 6502, nous pourrions appeler la sous-
AreaParserCore pour chaque colonne de niveau, puis utiliser Python plus compréhensible pour convertir les informations de bloc en l'image souhaitée.
Puis
py65emu apparaît sur la scène - un émulateur 6502 concis avec une interface Python. Voici comment la même configuration de mémoire est configurée dans py65emu que dans NES:
from py65emu.cpu import CPU from py65emu.mmu import MMU
Après cela, nous pouvons exécuter des instructions individuelles en utilisant la méthode
cpu.step() , examiner la mémoire en utilisant
mmu.read() , étudier les registres de la machine en utilisant
cpu.ra ,
cpu.r.pc , etc. De plus, nous pouvons écrire dans la mémoire en utilisant
mmu.write() .
Il convient de noter qu'il ne s'agit que d'un émulateur de processeur NES: il n'émule pas d'autres matériels, tels que PPU (Picture Processing Unit), il ne peut donc pas être utilisé pour émuler l'intégralité du jeu. Cependant, il devrait suffire d'appeler la sous-procédure d'analyse, car elle n'utilise aucun autre périphérique matériel à l'exception du processeur et de la mémoire.
Le plan consiste à configurer le processeur comme indiqué ci-dessus, puis pour chaque colonne de niveau, initialiser les partitions de mémoire avec les valeurs d'entrée requises pour
AreaParserCore , appeler
AreaParserCore , puis relire les données de colonne. Après avoir terminé ces opérations, nous utilisons Python pour assembler le résultat dans une image finie.
Mais avant cela, nous devons compiler la liste en langage assembleur dans le code machine.
x816
Comme indiqué dans le code source, l'assembleur est compilé à l'aide de x816. x816 est un assembleur MS-DOS 6502 utilisé par la communauté
homebrew pour les pirates NES et ROM. Cela fonctionne très bien sur
DOSBox .
Avec la ROM du programme, qui est nécessaire pour py65emu, l'assembleur x816 crée un fichier de caractères qui mappe les caractères à leur emplacement en mémoire dans l'espace d'adressage du CPU. Voici un extrait du fichier:
AREAPARSERCORE = $0093FC ; <> 37884, statement #3154
AREAPARSERTASKCONTROL = $0086E6 ; <> 34534, statement #1570
AREAPARSERTASKHANDLER = $0092B0 ; <> 37552, statement #3035
AREAPARSERTASKNUM = $00071F ; <> 1823, statement #141
AREAPARSERTASKS = $0092C8 ; <> 37576, statement #3048Ici, nous voyons que la fonction
AreaParserCore dans le code source est accessible à
0x93fc .
Pour plus de commodité, j'ai écrit un analyseur de fichiers de symboles qui correspond aux noms et adresses des symboles:
sym_file = SymbolFile('SMBDIS.SYM') print("0x{:x}".format(sym_file['AREAPARSERCORE']))
Sous-procédures
Comme indiqué dans le plan ci-dessus, nous voulons apprendre à appeler la sous-
AreaParserCore partir de Python.
Pour comprendre la mécanique d'une sous-procédure, examinons une sous-procédure courte et son défi correspondant:
WritePPUReg1: sta PPU_CTRL_REG1 ; A 1 PPU sta Mirror_PPU_CTRL_REG1 ; rts ... jsr WritePPUReg1
L'
jsr (jump to subroutine, "jump to subroutine")
jsr registre PC sur la pile et lui attribue la valeur d'adresse à laquelle
WritePPUReg1 réfère. Le registre PC indique au processeur l'adresse de la prochaine instruction à charger, de sorte que la prochaine instruction exécutée après l'instruction
jsr soit la première ligne de
WritePPUReg1 .
A la fin du sous-programme, l'instruction
rts est exécutée (retour du sous-programme, «retour du sous-programme»). Cette commande supprime la valeur stockée de la pile et la stocke dans le registre PC, ce qui oblige la CPU à exécuter l'instruction après l'appel
jsr .
Une grande caractéristique des sous-procédures est que vous pouvez créer des appels en ligne, c'est-à-dire des appels de sous-procédure dans des sous-procédures. Les adresses de retour seront poussées sur la pile et sautées dans le bon ordre, de la même manière qu'avec les appels de fonction dans les langages de haut niveau.
Voici le code pour exécuter le sous-programme à partir de 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'])
Le code enregistre la valeur actuelle du ou des registres de pointeurs de pile, émule un appel
jsr , puis exécute des instructions jusqu'à ce que la pile retrouve sa hauteur d'origine, ce qui ne se produit qu'après le retour de la première sous-procédure. Cela sera utile, car nous avons maintenant un moyen d'appeler directement 6502 sous-programmes depuis Python.
Cependant, nous avons oublié quelque chose: comment passer des valeurs d'entrée pour cette sous-procédure? Nous devons indiquer à la procédure quel niveau nous voulons afficher et quelle colonne nous devons analyser.
Contrairement aux fonctions des langages de haut niveau, les sous-programmes du langage d'assemblage 6502 ne peuvent pas recevoir de données d'entrée explicitement spécifiées. Au lieu de cela, l'entrée est transmise en spécifiant des emplacements de mémoire quelque part avant l'appel, qui sont ensuite lus à l'intérieur de l'appel de sous-procédure. Compte tenu de la taille de
AreaParserCore , l'ingénierie inverse de l'entrée requise en regardant simplement le code source sera très complexe et sujette aux erreurs.
Valgrind pour NES?
Pour trouver un moyen de déterminer les valeurs d'entrée de
AreaParserCore , j'ai utilisé l'outil
memcheck pour Valgrind comme exemple. Memcheck reconnaît les opérations d'accès à la mémoire non initialisée en stockant la mémoire fantôme en parallèle avec chaque fragment de la mémoire allouée réelle. La mémoire fantôme enregistre si l'enregistrement a été effectué dans la mémoire réelle correspondante. Si le programme lit à l'adresse à laquelle il n'a jamais écrit, une erreur de mémoire non initialisée est générée. Nous pouvons exécuter
AreaParserCore avec un outil qui nous indique quelle entrée doit être définie avant d'appeler la sous-procédure.
En fait, écrire une version simple de memcheck pour py65emu est très facile:
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
Ici, nous avons enveloppé l'unité de gestion de la mémoire (MMU) de py65emu. Cette classe contient un tableau
_uninitialized , dont les éléments nous indiquent s'il a déjà été écrit dans l'octet correspondant de la RAM émulée. En cas de lecture non initialisée, l'adresse de l'opération de lecture non valide et le nom du caractère correspondant sont affichés.
Voici les résultats de la MMU
execute_subroutine(sym_file['AREAPARSERCORE']) lors de l'appel de
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):
...En regardant le code, vous pouvez voir que bon nombre de ces valeurs sont définies par la sous-procédure
InitializeArea , alors exécutons à nouveau le script, en appelant cette fonction en premier. En répétant ce processus, nous arrivons à la séquence d'appels suivante, qui ne nécessite que le numéro mondial et le numéro de zone:
mmu.write(sym_file['WORLDNUMBER'], 0)
Le code écrit les 48 premières colonnes du niveau World 1-1 dans
metatile_data , en utilisant la sous-
metatile_data IncrementColumnPos pour augmenter les variables internes nécessaires pour suivre la colonne actuelle.
Et voici le contenu de
metatile_data superposé aux captures d'écran du jeu (les octets avec une valeur de 0 ne sont pas affichés):
De toute évidence,
metatile_data correspond clairement aux informations d'arrière-plan.
Meta Graphics
(Pour voir le résultat final, vous pouvez immédiatement passer à la section «Tout connecter ensemble».)
Voyons maintenant comment transformer le nombre de méta-fichiers reçus en images réelles. Les étapes décrites ci-dessous ont été inventées en analysant les sources et en lisant la documentation avec l'incroyable
Wiki Nesdev .
Pour comprendre comment rendre chaque métatile, nous devons d'abord parler des palettes de couleurs NES. Le PPU de la console NES peut généralement afficher 64 couleurs différentes, mais le noir est dupliqué plusieurs fois (voir
Nesdev pour
plus de
détails ):
Chaque niveau Mario ne peut utiliser que 10 de ces 64 couleurs pour l'arrière-plan, divisé en 4 palettes à quatre couleurs; La première couleur est toujours la même. Voici quatre palettes pour le Monde 1-1:
Voyons maintenant un exemple binaire d'un numéro de méta-fichier. Voici le nombre de métatiles de tuiles de pierre fissurées, qui est un terrain de niveau mondial 1-1:
L'index de palette nous indique quelle palette utiliser lors du rendu du métatile (dans notre cas, palette 1). L'index de palette est également l'index des deux tableaux suivants:
MetatileGraphics_Low:
.db <Palette0_MTiles, <Palette1_MTiles, <Palette2_MTiles, <Palette3_MTiles
MetatileGraphics_High:
.db >Palette0_MTiles, >Palette1_MTiles, >Palette2_MTiles, >Palette3_MTilesLa combinaison de ces deux tableaux nous donne une adresse 16 bits, qui dans notre exemple pointe vers
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)
...Lorsque vous multipliez l'index métatile par 4, il devient l'index de ce tableau. Les données sont formatées en 4 enregistrements par ligne, donc notre exemple de métatile se réfère à la vingtième ligne, marquée d'un commentaire de
cracked rock terrain .
Les quatre entrées de cette ligne sont en fait des identificateurs de tuiles: chaque métatile se compose de quatre tuiles de 8 x 8 pixels disposées dans l'ordre suivant - en haut à gauche, en bas à gauche, en haut à droite et en bas à droite. Ces identifiants sont transmis directement à la console NES PPU. L'identifiant fait référence à 16 octets de données dans la console CHR-ROM, et chaque enregistrement commence par l'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 est une mémoire en lecture seule à laquelle seul PPU peut accéder. Il est séparé du PRG-ROM, qui stocke le code du programme. Par conséquent, les données ci-dessus ne sont pas disponibles dans le code source et doivent être obtenues à partir du vidage de la ROM du jeu.
16 octets pour chaque tuile constituent une tuile 8x8 2 bits: le premier bit est les 8 premiers octets, et le second est le deuxième 8 octets:
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 13333332Liez ces données à la palette 1:
... et combinez les pièces:
Enfin, nous avons obtenu une tuile rendue.
Tout mettre ensemble
En répétant cette procédure pour chaque méta-fichier, nous obtenons un niveau complètement rendu.
Et grâce à cela, nous avons pu extraire des graphiques de niveau SMB en utilisant Python!