1. Introdução
Para um novo projeto, eu precisava extrair dados de nível do clássico videogame de 1985
Super Mario Bros (SMB) . Mais especificamente, eu queria extrair os gráficos de fundo de cada nível do jogo sem uma interface, sprites em movimento etc.
Obviamente, eu poderia colar as imagens do jogo e, possivelmente, automatizar o processo usando técnicas de visão de máquina. Mas me pareceu mais interessante o método descrito abaixo, que permite explorar os elementos de nível que não podem ser obtidos usando capturas de tela.
Na primeira etapa do projeto, aprenderemos a linguagem assembler 6502 e um emulador escrito em Python. O código fonte completo está disponível
aqui .
Análise do código fonte
A engenharia reversa de qualquer programa é muito mais simples se você tiver seu código fonte, e nós temos fontes SMB na forma de
17 mil linhas de código assembler 6502 (processador NES) publicadas pela doppelganger. Como a Nintendo nunca lançou um release oficial de origem, o código foi criado desmontando o código da máquina SMB, decifrando dolorosamente o significado de cada parte, adicionando comentários e nomes simbólicos significativos.
Depois de fazer uma pesquisa rápida no arquivo, encontrei algo semelhante aos dados de nível que precisávamos:
;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 $fdSe você não estiver familiarizado com o assembler, explicarei: tudo isso significa simplesmente "insira esse conjunto de bytes no programa compilado e permita que outras partes do programa se refiram a ele usando o símbolo
L_GroundArea6 ". Você pode pegar esse fragmento como uma matriz na qual cada elemento é um byte.
A primeira coisa que você pode notar é que o volume de dados é muito pequeno (cerca de 100 bytes). Portanto, excluímos todos os tipos de codificação, permitindo que você coloque arbitrariamente blocos no nível. Depois de pesquisar um pouco, descobri que esses dados são lidos (após várias operações de endereçamento indireto) no
AreaParserCore . Esse subprocedimento, por sua vez, chama muitos outros subprocedimentos, invocando subprocedimentos específicos para cada tipo de objeto permitido na cena (por exemplo,
StaircaseObject ,
VerticalPipe ,
RowOfBricks ):
Gráfico de chamada AreaParserCore para AreaParserCoreO procedimento grava no
MetatileBuffer : uma seção de memória de 13 bytes, que é uma coluna de blocos em um nível, e cada byte representa um bloco separado. Metatile é um bloco de 16x16 a partir do qual os planos de fundo de um jogo SMB são compostos:
Nível com retângulos circulados em torno de metáteisEles são chamados de metarquivos, porque cada um consiste em quatro blocos de 8x8 pixels, mas mais sobre isso abaixo.
O fato de o decodificador trabalhar com objetos predefinidos explica o tamanho pequeno do nível: os dados do nível devem se referir apenas aos tipos de objetos e sua localização, por exemplo, “posicione o tubo no ponto (20, 16), vários blocos no ponto (10, 5), ... " No entanto, isso significa que é necessário muito código para transformar dados brutos em metarquivos.
Portar essa quantidade de código para criar seu próprio desempacotador de nível levaria muito tempo, então vamos tentar uma abordagem diferente.
py65emu
Se tivéssemos uma interface entre o Python e a linguagem assembler 6502, poderíamos chamar o subprocedimento
AreaParserCore para cada coluna de nível e, em seguida, usar o Python mais compreensível para converter as informações do bloco na imagem desejada.
Então o
py65emu aparece em cena - um emulador 6502 conciso com uma interface Python. Veja como a mesma configuração de memória é configurada no py65emu e no NES:
from py65emu.cpu import CPU from py65emu.mmu import MMU
Depois disso, podemos executar instruções individuais usando o método
cpu.step() , examinar a memória usando
mmu.read() , estudar os registros da máquina usando
cpu.ra ,
cpu.r.pc , etc. Além disso, podemos gravar na memória usando
mmu.write() .
Vale ressaltar que este é apenas um emulador de processador NES: ele não emula outro hardware, como PPU (Picture Processing Unit), portanto não pode ser usado para emular o jogo inteiro. No entanto, deve ser suficiente chamar o subprocedimento de análise, porque ele não usa nenhum outro dispositivo de hardware, exceto a CPU e a memória.
O plano é configurar a CPU como mostrado acima e, para cada coluna de nível, inicialize as partições de memória com os valores de entrada necessários para o
AreaParserCore , chame
AreaParserCore e leia os dados da coluna novamente. Após concluir essas operações, usamos o Python para reunir o resultado em uma imagem finalizada.
Mas antes disso, precisamos compilar a listagem na linguagem assembly em código de máquina.
x816
Conforme indicado no código fonte, o assembler é compilado usando x816. O x816 é um assembler 6502 do MS-DOS usado pela comunidade
homebrew para hackers de NES e ROM. Funciona muito bem no
DOSBox .
Juntamente com a ROM do programa, necessária para o py65emu, o montador x816 cria um arquivo de caracteres que liga os caracteres à sua localização na memória no espaço de endereço da CPU. Aqui está um trecho do arquivo:
AREAPARSERCORE = $0093FC ; <> 37884, statement #3154
AREAPARSERTASKCONTROL = $0086E6 ; <> 34534, statement #1570
AREAPARSERTASKHANDLER = $0092B0 ; <> 37552, statement #3035
AREAPARSERTASKNUM = $00071F ; <> 1823, statement #141
AREAPARSERTASKS = $0092C8 ; <> 37576, statement #3048Aqui vemos que a função
AreaParserCore no código-fonte pode ser acessada em
0x93fc .
Por conveniência, escrevi um analisador de arquivo de símbolo que corresponde aos nomes e endereços dos símbolos:
sym_file = SymbolFile('SMBDIS.SYM') print("0x{:x}".format(sym_file['AREAPARSERCORE']))
Subprocedimentos
Conforme declarado no plano acima, queremos aprender como chamar o subprocedimento
AreaParserCore do Python.
Para entender a mecânica de um subprocedimento, vamos examinar um pequeno subprocedimento e seu desafio correspondente:
WritePPUReg1: sta PPU_CTRL_REG1 ; A 1 PPU sta Mirror_PPU_CTRL_REG1 ; rts ... jsr WritePPUReg1
A instrução
jsr (pula para a subrotina, "pula para a subrotina")
jsr registro
jsr PC na pilha e atribui a ele o valor do endereço ao qual
WritePPUReg1 se refere. O registro do PC informa ao processador o endereço da próxima instrução a ser carregada, de modo que a próxima instrução executada após a instrução
jsr seja a primeira linha do
WritePPUReg1 .
No final da sub-rotina, a instrução
rts é executada (retorno da sub-rotina, "retorno da sub-rotina"). Este comando remove o valor armazenado da pilha e o armazena no registro do PC, o que força a CPU a executar a instrução após a chamada
jsr .
Um ótimo recurso dos subprocedimentos é que você pode criar chamadas embutidas, ou seja, chamadas de subprocedimentos dentro dos subprocedimentos. Os endereços de retorno serão colocados na pilha e exibidos na ordem correta, da mesma maneira que nas chamadas de função em idiomas de alto nível.
Aqui está o código para executar a sub-rotina do 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'])
O código salva o valor atual do (
s ) registrador (
s ) do ponteiro da pilha, emula uma chamada
jsr e executa as instruções até que a pilha retorne à sua altura original, o que ocorre somente após o retorno do primeiro subprocedimento. Isso será útil, porque agora temos uma maneira de chamar diretamente 6502 sub-rotinas do Python.
No entanto, esquecemos algo: como passar valores de entrada para esse subprocedimento? Precisamos dizer ao procedimento qual nível queremos renderizar e qual coluna precisamos analisar.
Diferentemente das funções nas linguagens de alto nível, as sub-rotinas da linguagem de montagem 6502 não podem receber dados de entrada especificados explicitamente. Em vez disso, a entrada é transmitida especificando os locais de memória em algum lugar antes da chamada, que são lidos dentro da chamada de subprocedimento. Dado o tamanho do
AreaParserCore , a engenharia reversa, a entrada necessária, basta olhar o código-fonte será muito complexo e propenso a erros.
Valgrind para NES?
Para encontrar uma maneira de determinar os valores de entrada do
AreaParserCore , usei a ferramenta
memcheck para o Valgrind como exemplo. A verificação de memória reconhece operações de acesso à memória não inicializada, armazenando a memória de sombra em paralelo com cada fragmento da memória alocada real. A memória de sombra registra se a gravação foi feita na memória real correspondente. Se o programa ler para o endereço no qual nunca gravou, será gerado um erro de memória não inicializado. Podemos executar o
AreaParserCore com uma ferramenta que nos informa quais entradas precisam ser definidas antes de chamar o subprocedimento.
De fato, escrever uma versão simples do memcheck para py65emu é muito 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
Aqui envolvemos a unidade de gerenciamento de memória (MMU) do py65emu. Essa classe contém uma matriz
_uninitialized ,
_uninitialized elementos nos informam se alguma vez foi gravada no byte correspondente da RAM emulada. No caso de uma leitura não inicializada, o endereço da operação de leitura inválida e o nome do caractere correspondente são exibidos.
Aqui estão os resultados da MMU
execute_subroutine(sym_file['AREAPARSERCORE']) ao chamar
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):
...Observando o código, você pode ver que muitos desses valores são definidos pelo subprocedimento
InitializeArea ; portanto, vamos executar o script novamente, chamando essa função primeiro. Repetindo esse processo, chegamos à seguinte sequência de chamadas, que requer apenas o número do mundo e o número da área:
mmu.write(sym_file['WORLDNUMBER'], 0)
O código grava as primeiras 48 colunas do nível Mundial 1-1 em
metatile_data , usando o subprocedimento
IncrementColumnPos para aumentar as variáveis internas necessárias para rastrear a coluna atual.
E aqui está o conteúdo de
metatile_data sobreposto nas capturas de tela do jogo (bytes com o valor 0 não são mostrados):
Obviamente,
metatile_data corresponde claramente a informações de segundo plano.
Meta Graphics
(Para ver o resultado final, você pode prosseguir imediatamente para a seção “Conectando tudo junto”.)
Agora vamos descobrir como transformar o número recebido de metarquivos em imagens reais. As etapas descritas abaixo foram inventadas analisando as fontes e lendo a documentação com o incrível
Nesdev Wiki .
Para entender como renderizar cada metátil, primeiro precisamos falar sobre paletas de cores do NES. Geralmente, o PPU do console do NES pode renderizar 64 cores diferentes, mas o preto é duplicado várias vezes (consulte o
Nesdev para
obter detalhes ):
Cada nível de Mario pode usar apenas 10 dessas 64 cores como plano de fundo, divididas em 4 paletas de quatro cores; A primeira cor é sempre a mesma. Aqui estão quatro paletas para o mundo 1-1:
Vamos agora ver um exemplo binário de um número de arquivo meta. Aqui está o número de metila da telha de pedra rachada, que é a terra de nível 1-1 do mundo:
O índice da paleta nos diz qual paleta usar ao renderizar o metátil (no nosso caso, paleta 1). O índice da paleta também é o índice das duas matrizes a seguir:
MetatileGraphics_Low:
.db <Palette0_MTiles, <Palette1_MTiles, <Palette2_MTiles, <Palette3_MTiles
MetatileGraphics_High:
.db >Palette0_MTiles, >Palette1_MTiles, >Palette2_MTiles, >Palette3_MTilesA combinação dessas duas matrizes nos fornece um endereço de 16 bits, que em nosso exemplo aponta para
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)
...Quando você multiplica o índice metátil por 4, ele se torna o índice dessa matriz. Os dados são formatados em 4 registros por linha; portanto, nosso exemplo metátil refere-se à vigésima linha, marcada com um comentário de
cracked rock terrain .
As quatro entradas dessa linha são, na verdade, identificadores de bloco: cada metatile consiste em quatro blocos de 8x8 pixels organizados na seguinte ordem - superior esquerdo, inferior esquerdo, superior direito e inferior direito. Esses identificadores são passados diretamente para o console do NES PPU. O identificador refere-se a 16 bytes de dados no console do CHR-ROM e cada registro começa com o endereço
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: 0b01111111O CHR-ROM é um pedaço de memória somente leitura que somente a PPU pode acessar. É separado do PRG-ROM, que armazena o código do programa. Portanto, os dados acima não estão disponíveis no código fonte e devem ser obtidos no dump da ROM do jogo.
16 bytes para cada bloco compõem um bloco 8x8 de 2 bits: o primeiro bit é o primeiro 8 bytes e o segundo é o segundo 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 13333332Vincule esses dados à paleta 1:
... e combine as peças:
Finalmente, conseguimos um bloco renderizado.
Juntando tudo
Repetindo este procedimento para cada arquivo meta, obtemos um nível completamente renderizado.
E, graças a isso, conseguimos extrair gráficos de nível SMB usando Python!