Introduccion
Para un nuevo proyecto, necesitaba extraer datos de nivel del clásico videojuego de 1985
Super Mario Bros (SMB) . Más específicamente, quería extraer los gráficos de fondo de cada nivel del juego sin una interfaz, mover sprites, etc.
Por supuesto, podría pegar las imágenes del juego y, posiblemente, automatizar el proceso utilizando técnicas de visión artificial. Pero me pareció más interesante el método descrito a continuación, que le permite explorar los elementos de nivel que no se pueden obtener con capturas de pantalla.
En la primera etapa del proyecto, aprenderemos el lenguaje ensamblador 6502 y un emulador escrito en Python. El código fuente completo está disponible
aquí .
Análisis de código fuente
La ingeniería inversa de cualquier programa es mucho más simple si tiene su código fuente, y tenemos fuentes SMB en forma de
17 mil líneas de código ensamblador 6502 (procesador NES) publicado por doppelganger. Dado que Nintendo nunca lanzó un lanzamiento de fuente oficial, el código fue creado al desarmar el código de máquina SMB, descifrar dolorosamente el significado de cada parte, agregar comentarios y nombres simbólicos significativos.
Después de realizar una búsqueda rápida en el archivo, encontré algo similar a los datos de nivel que necesitábamos:
;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 no está familiarizado con el ensamblador, explicaré: todo esto simplemente significa "insertar un conjunto de bytes en el programa compilado y luego permitir que otras partes del programa lo consulten utilizando el símbolo
L_GroundArea6 ". Puede tomar este fragmento como una matriz en la que cada elemento es un byte.
Lo primero que puede notar es que el volumen de datos es muy pequeño (aproximadamente 100 bytes). Por lo tanto, excluimos todos los tipos de codificación, lo que le permite colocar bloques arbitrariamente en el nivel. Después de buscar un poco, descubrí que estos datos se leen (después de varias operaciones de direccionamiento indirecto) en
AreaParserCore . Este subprocedimiento, a su vez, invoca muchos otros subprocedimientos, invocando subprocedimientos específicos para cada tipo de objeto permitido en la escena (por ejemplo,
StaircaseObject ,
VerticalPipe ,
RowOfBricks ):
Gráfico de llamada AreaParserCore para AreaParserCoreEl procedimiento escribe en
MetatileBuffer : una sección de memoria de 13 bytes, que es una columna de bloques en un nivel, cada uno de los cuales representa un bloque separado. Un metatile es un bloque de 16x16 del que se componen los fondos de un juego SMB:
Nivelar con rectángulos en círculos alrededor de metatilesSe llaman metaarchivos, porque cada uno consta de cuatro mosaicos de 8x8 píxeles, pero más sobre eso a continuación.
El hecho de que el decodificador funcione con objetos predefinidos explica el pequeño tamaño del nivel: los datos de nivel deben referirse solo a los tipos de objetos y su ubicación, por ejemplo, "coloque la tubería en el punto (20, 16), varios bloques en el punto (10, 5), ... ". Sin embargo, esto significa que se necesita mucho código para convertir los datos de nivel sin procesar en metaarchivos.
Portar esta cantidad de código para crear su propio desempacador de nivel llevaría demasiado tiempo, así que intentemos un enfoque diferente.
py65emu
Si tuviéramos una interfaz entre Python y el lenguaje ensamblador 6502, podríamos llamar al subprocedimiento
AreaParserCore para cada columna de nivel, y luego usar Python más comprensible para convertir la información del bloque en la imagen deseada.
Luego aparece
py65emu en escena: un emulador conciso 6502 con una interfaz Python. Así es como se configura la misma configuración de memoria en py65emu que en NES:
from py65emu.cpu import CPU from py65emu.mmu import MMU
Después de eso, podemos ejecutar instrucciones individuales usando el método
cpu.step() , examinar la memoria usando
mmu.read() , estudiar los registros de la máquina usando
cpu.ra ,
cpu.r.pc , etc. Además, podemos escribir en la memoria usando
mmu.write() .
Vale la pena señalar que esto es solo un emulador de procesador NES: no emula otro hardware, como PPU (unidad de procesamiento de imágenes), por lo que no se puede usar para emular todo el juego. Sin embargo, debería ser suficiente para llamar al subproceso de análisis, ya que no utiliza ningún otro dispositivo de hardware, excepto la CPU y la memoria.
El plan es configurar la CPU como se muestra arriba, y luego para cada columna de nivel, inicializar las particiones de memoria con los valores de entrada requeridos para
AreaParserCore , llamar a
AreaParserCore y luego leer los datos de la columna. Después de completar estas operaciones, usamos Python para ensamblar el resultado en una imagen terminada.
Pero antes de eso, necesitamos compilar el listado en lenguaje ensamblador en código máquina.
x816
Como se indica en el código fuente, el ensamblador se compila utilizando x816. x816 es un ensamblador de MS-DOS 6502 utilizado por la comunidad
homebrew para piratas informáticos NES y ROM. Funciona muy bien en
DOSBox .
Junto con la ROM del programa, que es necesario para py65emu, el ensamblador x816 crea un archivo de caracteres que asigna los caracteres a su ubicación en la memoria en el espacio de direcciones de la CPU. Aquí hay un fragmento del archivo:
AREAPARSERCORE = $0093FC ; <> 37884, statement #3154
AREAPARSERTASKCONTROL = $0086E6 ; <> 34534, statement #1570
AREAPARSERTASKHANDLER = $0092B0 ; <> 37552, statement #3035
AREAPARSERTASKNUM = $00071F ; <> 1823, statement #141
AREAPARSERTASKS = $0092C8 ; <> 37576, statement #3048Aquí vemos que se puede acceder a la función
AreaParserCore en el código fuente en
0x93fc .
Por conveniencia, escribí un analizador de archivos de símbolos que coincide con los nombres y las direcciones de los símbolos:
sym_file = SymbolFile('SMBDIS.SYM') print("0x{:x}".format(sym_file['AREAPARSERCORE']))
Subprocedimientos
Como se indicó en el plan anterior, queremos aprender cómo llamar al subprocedimiento
AreaParserCore desde Python.
Para comprender la mecánica de un subprocedimiento, examinemos un subprocedimiento breve y su desafío correspondiente:
WritePPUReg1: sta PPU_CTRL_REG1 ; A 1 PPU sta Mirror_PPU_CTRL_REG1 ; rts ... jsr WritePPUReg1
La
jsr (saltar a subrutina, "saltar a subrutina")
jsr registro de
jsr PC a la pila y le asigna el valor de dirección al que se refiere
WritePPUReg1 . El registro de la PC le indica al procesador la dirección de la siguiente instrucción que se cargará, de modo que la siguiente instrucción ejecutada después de la instrucción
jsr es la primera línea de
WritePPUReg1 .
Al final de la subrutina, se
rts instrucción
rts (retorno de subrutina, "retorno de subrutina"). Este comando elimina el valor almacenado de la pila y lo almacena en el registro de la PC, lo que obliga a la CPU a ejecutar la instrucción después de la llamada
jsr .
Una gran característica de los subprocedimientos es que puede crear llamadas en línea, es decir, llamadas de subprocedimiento dentro de subprocedimientos. Las direcciones de retorno se insertarán en la pila y se mostrarán en el orden correcto, de la misma manera que con las llamadas a funciones en idiomas de alto nivel.
Aquí está el código para ejecutar la subrutina desde 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'])
El código guarda el valor actual de los registros de puntero de la pila, emula una llamada
jsr y luego ejecuta las instrucciones hasta que la pila vuelva a su altura original, lo que ocurre solo después del retorno del primer subprocedimiento. Esto será útil, porque ahora tenemos una manera de llamar directamente a las subrutinas 6502 desde Python.
Sin embargo, olvidamos algo: ¿cómo pasar los valores de entrada para este subprocedimiento? Necesitamos decirle al procedimiento qué nivel queremos representar y qué columna debemos analizar.
A diferencia de las funciones en lenguajes de alto nivel, las subrutinas del lenguaje ensamblador 6502 no pueden recibir datos de entrada especificados explícitamente. En cambio, la entrada se transmite especificando ubicaciones de memoria en algún lugar antes de la llamada, que luego se leen dentro de la llamada del subprocedimiento. Dado el tamaño de
AreaParserCore , la ingeniería inversa de la entrada requerida simplemente mirando el código fuente será muy compleja y propensa a errores.
Valgrind para NES?
Para encontrar una manera de determinar los valores de entrada de
AreaParserCore , utilicé la herramienta
memcheck para Valgrind como ejemplo. Memcheck reconoce las operaciones de acceso a la memoria no inicializada almacenando memoria paralela en paralelo con cada fragmento de la memoria asignada real. La memoria de sombra registra si la grabación se realizó en la memoria real correspondiente. Si el programa lee en la dirección en la que nunca escribió, se genera un error de memoria no inicializado. Podemos ejecutar
AreaParserCore con una herramienta que nos dice qué entrada debe establecerse antes de invocar el subprocedimiento.
De hecho, escribir una versión simple de memcheck para py65emu es muy fácil:
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
Aquí envolvemos la unidad de administración de memoria (MMU) de py65emu. Esta clase contiene una matriz
_uninitialized ,
_uninitialized elementos nos dicen si alguna vez se ha escrito en el byte correspondiente de RAM emulada. En el caso de una lectura no inicializada, se muestran la dirección de la operación de lectura no válida y el nombre del carácter correspondiente.
Estos son los resultados de la MMU
execute_subroutine(sym_file['AREAPARSERCORE']) cuando se llama a
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):
...Al mirar el código, puede ver que muchos de estos valores están establecidos por el subprocedimiento
InitializeArea , así que ejecutemos el script nuevamente, llamando a esta función primero. Repitiendo este proceso, llegamos a la siguiente secuencia de llamadas, que requiere solo el número mundial y el número de área:
mmu.write(sym_file['WORLDNUMBER'], 0)
El código escribe las primeras 48 columnas del nivel Mundial 1-1 en
metatile_data , utilizando el subprocedimiento
IncrementColumnPos para aumentar las variables internas necesarias para rastrear la columna actual.
Y aquí está el contenido de
metatile_data superpuesto en las capturas de pantalla del juego (no se muestran los bytes con un valor de 0):
Obviamente,
metatile_data coincide claramente con la información de fondo.
Meta Graphics
(Para ver el resultado final, puede pasar inmediatamente a la sección "Conectar todo").
Ahora veamos cómo convertir el número recibido de metaarchivos en imágenes reales. Los pasos que se describen a continuación se inventaron analizando las fuentes y leyendo la documentación con el increíble
Nesdev Wiki .
Para entender cómo renderizar cada metatile, primero debemos hablar sobre las paletas de colores NES. La consola PPU de NES generalmente puede generar 64 colores diferentes, pero el negro se duplica varias veces (consulte
Nesdev para
obtener más detalles ):
Cada nivel de Mario puede usar solo 10 de estos 64 colores para el fondo, divididos en 4 paletas de cuatro colores; El primer color es siempre el mismo. Aquí hay cuatro paletas para el Mundo 1-1:
Veamos ahora un ejemplo binario de un número de metaarchivo. Aquí está el número de metatile de azulejos de piedra agrietados, que es tierra de nivel 1-1 del mundo:
El índice de paleta nos dice qué paleta usar al renderizar el metatile (en nuestro caso, paleta 1). El índice de paleta también es el índice de las siguientes dos matrices:
MetatileGraphics_Low:
.db <Palette0_MTiles, <Palette1_MTiles, <Palette2_MTiles, <Palette3_MTiles
MetatileGraphics_High:
.db >Palette0_MTiles, >Palette1_MTiles, >Palette2_MTiles, >Palette3_MTilesLa combinación de estos dos arreglos nos da una dirección de 16 bits, que en nuestro ejemplo apunta a
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)
...Cuando multiplica el índice de metatile por 4, se convierte en el índice de esta matriz. Los datos están formateados en 4 registros por línea, por lo que nuestro metatile de ejemplo se refiere a la vigésima línea, marcada con un comentario de
cracked rock terrain .
Las cuatro entradas de esta línea son en realidad identificadores de mosaico: cada metatile consta de cuatro mosaicos de 8x8 píxeles dispuestos en el siguiente orden: superior izquierdo, inferior izquierdo, superior derecho e inferior derecho. Estos identificadores se pasan directamente a la consola NES PPU. El identificador se refiere a 16 bytes de datos en la consola CHR-ROM, y cada registro comienza con la dirección
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 es una memoria de solo lectura a la que solo PPU puede acceder. Está separado del PRG-ROM, que almacena el código del programa. Por lo tanto, los datos anteriores no están disponibles en el código fuente y deben obtenerse del volcado de la ROM del juego.
16 bytes para cada mosaico forman un mosaico de 2 bits 8x8: el primer bit son los primeros 8 bytes, y el segundo son los segundos 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 13333332Vincula estos datos a la paleta 1:
... y combina las piezas:
Finalmente obtuvimos un mosaico renderizado.
Poniendo todo junto
Repitiendo este procedimiento para cada metaarchivo, obtenemos un nivel completamente renderizado.
¡Y gracias a esto, pudimos extraer gráficos de nivel SMB usando Python!