Используем Python для извлечения фона из Super Mario Bros

В этой статье мы собираемся зареверсить Super Mario Bros 1985 года, чтобы извлечь изображение фона. Конечно, это всё можно попробовать сделать с помощью компьютерного зрения, однако представленный здесь способ несколько интереснее. Весь исходный код доступен на GitHub.

Анализ исходного кода

Зареверсить любую программу гораздо проще, если у вас есть исходники. В нашем случае они представлены в виде 17000 строк кода 6502 ассемблера (NES CPU). Поскольку Nintendo никогда официально не открывала доступ к исходному коду, пришлось раздобыть его самостоятельно через дизассемблирование машинного кода SMB, кропотливо расшифровывая деталь за деталью и вставляя комментарии и осмысленные имена символов.

Просматриваем файл и находим что-то приблизительно похожее на данные уровня, которые мы ищем:

			;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 $fd
		

Если вы не знакомы с ассемблером, то тут говорится вставить эти байты в скомпилированную программу, а затем разрешить другим частям программы ссылаться на них через символ L_GroundArea6. Можете считать это массивом, в котором каждый элемент является одним байтом.

Первое, что стоит отметить, — здесь представлен очень небольшой объём данных — около 100 байт. Это исключает любую кодировку, позволяющую произвольно размещать блоки на уровне. Просмотрев файл, можно обнаружить, что эти данные на самом деле читаются (после нескольких переходов по ссылкам) в AreaParserCore. Эта подпрограмма вызывает множество других подпрограмм, в итоге вызывая отдельную подпрограмму для каждого типа объектов (из возможных 40), размещённого в сцене (например, StaircaseObject, VerticalPipe, RowOfBricks):

Подпрограмма пишет в MetatileBuffer — раздел памяти длиной в 13 байт, отображающий колонку блоков, где каждый байт представляет один блок. Метаблок — это блок размером 16×16, который составляет фон в SMB:

Он называется так, потому что состоит из четырёх пиксельных блоков 8×8, но об этом позже.

Тот факт, что декодер работает с предопределёнными объектами, объясняет небольшой размер уровней: данные уровня ссылаются только на типы объектов и их местоположение, например, «разместить трубу на (20, 16), ряд блоков на (10, 5), …». Тем не менее это значит, что для преобразования данных об уровне в метаблоки требуется много кода.

Портировать такие объёмы кода для извлечения уровней слишком долго, поэтому попробуем другой подход.

py65emu

Если бы у нас был интерфейс между Python и ассемблером 6502, мы могли бы вызвать подпрограмму AreaParserCore для каждой колонки на уровне, а затем использовать более лаконичный Python для конвертации информации о блоке в нужное изображение.

Здесь нам пригодится эмулятор 6502 py65emu. Вот как можно настроить py65emu для такой же конфигурации карты памяти, как на NES:

			from py65emu.cpu import CPU
from py65emu.mmu import MMU

# Загружаем ROM-память, хранящую код программы (т.е. скомпилированный ассемблерный код)
with open("program.bin", "rb") as f:
    prg_rom = f.read()

# Сопоставляем память
mmu = MMU([
    # Создаём 2 Кб оперативной памяти, привязанной к адресу 0x0
    (0x0, 2048, False, []),

    # Привязываем ROM-память, хранящую код программы, к 0x8000
    (0x8000, len(prg_rom), True, list(prg_rom))
])

# Создаём процессор, говорим ему начать работу с адреса 0x8000
cpu = CPU(mmu, 0x8000)
		

После этого мы можем выполнять одиночные инструкции с помощью метода cpu.step(). А ещё мы можем исследовать память с помощью mmu.read() и проверять регистры машины с помощью cpu.r.a, cpu.r.pc и т.д. Кроме того, мы можем записывать в память с помощью mmu.write().

Стоит отметить, что это только эмулятор процессора NES: он не эмулирует другие составляющие вроде PPU, поэтому его нельзя использовать для эмуляции целой игры. Тем не менее, этого должно быть достаточно для вызова нужных подпрограмм, так как они не требуют ничего, кроме процессора и памяти.

План состоит в том, чтобы настроить процессор так, как мы это сделали выше, а затем для каждой колонки уровня инициализировать разделы памяти с входными данными, нужными AreaParserCore. После этого мы вызываем AreaParserCore и считываем данные колонки. Полученный результат можно будет сконвертировать в изображение с помощью Python.

Но прежде чем мы это сделаем, нам нужно скомпилировать ассемблерный код в машинный.

x816

Как указано в исходниках, код компилируется с помощью x816 — ассемблера 6502, базирующийся на MS-DOS, который используется поклонниками NES и ромхакерами и прекрасно работает в DOSBox.

Наряду с ROM-памятью, требуемой py65emu, x816 создаёт файл символов, сопоставляющий символы с их местоположением в памяти внутри адресного пространства процессора. Вот небольшой отрывок:

			AREAPARSERCORE                   = $0093FC   ; <> 37884, statement #3154
AREAPARSERTASKCONTROL            = $0086E6   ; <> 34534, statement #1570
AREAPARSERTASKHANDLER            = $0092B0   ; <> 37552, statement #3035
AREAPARSERTASKNUM                = $00071F   ; <> 1823, statement #141
AREAPARSERTASKS                  = $0092C8   ; <> 37576, statement #3048
		

Здесь мы видим функцию AreaParserCore, доступ к которой можно будет получить по адресу 0x93fc.

Для удобства был создан парсер для символьного файла, который соотносит символьные имена и адреса:

			sym_file = SymbolFile('SMBDIS.SYM')
print("0x{:x}".format(sym_file['AREAPARSERCORE'])) # выводит 0x93fc
print(sym_file.lookup_address(0x93fc)) # выводит "AREAPARSERCORE"
		

Подпрограммы

Напоминаем, сейчас нашей целью является возможность вызывать подпрограмму AreaParserCore из Python.

Чтобы понять механику работы подпрограмм, давайте взглянем на небольшую подпрограмму и её вызов:

			WritePPUReg1:
               sta PPU_CTRL_REG1         ;записать содержимое A в 1 регистр PPU
               sta Mirror_PPU_CTRL_REG1  ;и в его зеркало
               rts

...

jsr WritePPUReg1
		

Инструкция jsr (jump to subroutine, войти в подпрограмму) помещает регистр ПК в стек и присваивает ему адрес, на который ссылается WritePPUReg1. Регистр говорит процессору адрес следующей инструкции для загрузки, поэтому после jsr будет выполнена первая строка WritePPUReg1.

В конце подпрограммы выполняется инструкция rts (return from subroutine, вернуться из подпрограммы). Она удаляет из стека сохранённое значение и сохраняет его в регистре, что заставляет процессор выполнять инструкцию, следующую за вызовом jsr.

Что здорово в подпрограммах, так это возможность использовать вложенные вызовы, то есть подпрограммы, вызывающие подпрограммы. Адреса возврата будут сначала помещены в стек, а затем удалены в правильном порядке — точно так же, как при вызове функций в высокоуровневом языке.

Код для выполнения подпрограммы из Python:

			def execute_subroutine(cpu, addr):
    s_before = cpu.r.s
    cpu.JSR(addr)
    while cpu.r.s != s_before:
        cpu.step()

execute_subroutine(cpu, sym_file['AREAPARSERCORE'])
		

Здесь происходит следующее: сохраняется текущее значение регистра указателя стека (s), эмулируется вызов jsr, а затем выполняются инструкции до тех пор, пока стек не вернётся к начальной высоте, что случится только после возвращения первой подпрограммы. Это полезно, так как теперь у нас есть способ вызывать подпрограммы 6502 напрямую из Python.

Однако мы забываем об одной вещи: как передать данные на вход этой подпрограммы? Нам нужно как-то сообщить программе, какой уровень мы пытаемся отобразить или какую конкретно колонку мы хотим пропарсить.

В отличие от высокоуровневых языков вроде C или Python, подпрограммы ассемблера 6502 не принимают входные данные явно. Вместо этого входные данные передаются путём установки значений ячеек памяти в какой-то момент до вызова, которые затем считываются внутри подпрограммы. Учитывая размер AreaParserCore, зареверсить нужные входные данные таким образом будет сложно и риск ошибки будет велик.

Valgrind для NES?

Чтобы выяснить, где находятся входные данные для AreaParserCore, почерпнём вдохновение из инструмента memcheck для Valgrind. Memcheck отслеживает обращения к неинициализированному участку памяти путем хранения «теневой» памяти для каждого действительного участка. Теневая память запоминает, было ли что-либо записано на соответствующий участок. Если программа читает из адреса, в который никогда ничего не записывалось, выводится ошибка. Если бы мы могли запустить AreaParserCore с таким инструментом, это могло бы решить нашу проблему.

На самом деле, написать простой вариант memcheck для py56emu не составляет труда:

			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
		

Здесь мы оборачиваем блок управления памятью (MMU) py65emu. Этот класс содержит массив _unitialized, элементы которого говорят нам, записывалось ли что-нибудь в соответствующий байт эмулированной RAM. Когда происходит чтение из неинициализированного участка памяти, его адрес и соответствующее имя символа выводятся на экран.

Вот что выдаёт обёрнутый MMU при вызове 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):
...
		

Посмотрев на код, можно заметить, что многие из этих значений устанавливаются подпрограммой InitializeArea, поэтому давайте перезапустим скрипт сначала с вызовом этой функции. Повторяя процесс, мы в итоге получаем такую последовательность вызовов, где требуется установить только номер мира и номер участка:

			mmu.write(sym_file['WORLDNUMBER'], 0)    # Номер мира, минус 1
mmu.write(sym_file['AREANUMBER'], 0)     # Номер уровня, минус 1
execute_subroutine(sym_file['LOADAREAPOINTER'])
execute_subroutine(sym_file['INITIALIZEAREA'])

metatile_data = []
for column_pos in range(48):
    execute_subroutine(sym_file['AREAPARSERCORE'])
    metatile_data.append([mmu.read_no_debug(sym_file['METATILEBUFFER'] + i)
                          for i in range(13)])
    execute_subroutine(sym_file['INCREMENTCOLUMNPOS'])
		

Здесь мы записываем первые 48 колонок World 1-1 в metatile_data, используя подпрограмму IncrementColumnPos для увеличения внутренних переменных, которые нужны для отслеживания текущей колонки.

Здесь можно увидеть содержимое metatile_data, наложенное на один из скриншотов из игры (байты с нулевым значением не показаны):

metatile_data полностью соответствует фону.

Изображения метаблоков

(Вы можете пропустить этот шаг и перейти к конечному результату)

Теперь давайте узнаем, как превратить полученные номера метаблоков в изображения. В получении этой информации помог анализ исходного кода и изучение документации Nesdev Wiki.

Чтобы понять, как отобразить каждый метаблок, сначала нужно узнать о цветовых палитрах на NES. NES PPU может отображать до 64 разных цветов, хотя чёрный повторяется несколько раз (подробности можно почитать здесь):

На каждом уровне Mario для создания фона используется только 10 из 64 цветов , разделённых на четыре цветовые палитры; первый цвет всегда один и тот же. Здесь мы видим палитры для World 1-1:

Посмотрим на номер метаблока, выраженный в двоичной системе. Это номер метаблока треснувшей плитки, по которой бегает герой:

Индекс палитры говорит нам, какую палитру использовать при отображении метаблока. В данном случае это Палитра 1. Индекс палитры также является индексом этих двух массивов:

			MetatileGraphics_Low:
  .db <Palette0_MTiles, <Palette1_MTiles, <Palette2_MTiles, <Palette3_MTiles

MetatileGraphics_High:
  .db >Palette0_MTiles, >Palette1_MTiles, >Palette2_MTiles, >Palette3_MTiles
		

Вместе эти массивы дают 16-битный адрес, который в нашем случае указывает на 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 <--- 20 строка
  .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)
  ...
		

Умноженный на 4 индекс метаблока является индексом этого массива. На каждую строку приходится по 4 записи, наш пример относится к 20 строке, что подтверждает комментарий cracked rock terrain.

Четыре значения на этой строке по сути являются ID блока: каждый метаблок состоит из четырёх блоков 8х8 в порядке верхний левый, нижний левый, верхний правый, нижний правый. Эти ID отправляются напрямую в PPU NES. ID ссылается на 16 байт данных в CHR-ROM NES, где каждая запись начинается с адреса 0x1000 + 16 * <id блока>:

			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:  0b01111111
		

CHR-ROM — часть read-only памяти, доступ к которой имеет только PPU. Эта часть отделена от PRG-ROM, где хранится программный код. Таким образом, к указанным выше данным нет доступа из исходного кода и их необходимо извлекать из дампа ROM SMB.

16 байт на каждый блок дают 2-битный блок 8х8: первый бит — первые 8 байт, второй бит — вторые 8 байт:

			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  13333332
		

Соотносим с первой палитрой:

И соединяем:

Вот мы и получили изображение блока.

Складываем всё воедино

Повторяем это действие для каждого метаблока и получаем изображение всего уровня:

Вот мы и извлекли изображение уровня SMB на чистом Python!