Извлекаем уровни из Super Mario Bros с помощью Python

Введение

Для нового проекта мне понадобилось извлечь данные уровней из классической видеоигры 1985 года Super Mario Bros (SMB). Если конкретнее, то я хотел извлечь фоновую графику каждого уровня игры без интерфейса, подвижных спрайтов и т.п. Разумеется, я просто мог склеить изображения из игры и, возможно, автоматизировать процесс с помощью техник машинного зрения. Но мне показался более интересным описанный ниже метод, позволяющий исследовать те элементы уровней, которые нельзя получить с помощью скриншотов.
На первом этапе проекта мы изучим язык ассемблера 6502 и написанный на Python эмулятор. Полный исходный код выложен здесь.

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

Реверс-инжиниринг любой программы намного проще, если есть её исходный код, а у нас имеются исходники SMB в виде 17 тысяч строк ассемблерного кода 6502 (процессора NES), опубликованных doppelganger. Поскольку 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. Эта подпроцедура в свою очередь вызывает множество других подпроцедур, в конечном итоге вызывая конкретные подпроцедуры для каждого типа объектов, допустимых в сцене (например, StaircaseObject, VerticalPipe, RowOfBricks) для более чем 40 объектов:

Сокращённый граф вызовов для AreaParserCore

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

Уровень с прямоугольниками, описанными вокруг метатайлов

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

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

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

py65emu

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

Тут на сцене появляется py65emu — лаконичный эмулятор 6502 с интерфейсом Python. Вот как в 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([         # Создание 2K ОЗУ, привязываемых к адресу 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 (Picture Processing Unit), поэтому его нельзя использовать для эмуляции всей игры. Однако его должно быть достаточно для вызова подпроцедуры парсинга, потому что она не использует никаких других аппаратных устройств, кроме ЦП и памяти.

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

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

x816

Как указано в исходном коде, ассемблер компилируется с помощью x816. x816 — это ассемблер 6502 под MS-DOS, используемый сообществом разработчиков самодельных игр (homebrew) для NES и ROM-хакеров. Он замечательно работает в 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, «перейти к подпроцедуре») добавляет регистр PC в стек и присваивает ему значение адреса, на который ссылается WritePPUReg1. Регистр PC сообщает процессору адрес следующей загружаемой инструкции, чтобы следующая инструкция, выполняемая после инструкции jsr, была первой строкой WritePPUReg1.

В конце подпроцедуры выполняется инструкция rts (return from subroutine, «возврат из подпроцедуры»). Эта команда удаляет сохранённое значение из стека и сохраняет его в регистре PC, что заставляет ЦП выполнить инструкцию, следующую за вызовом 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.

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

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

Valgrind для NES?

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

На самом деле написать простую версию memcheck для py65emu очень легко:

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. Этот класс содержит массив _uninitialized, элементы которого сообщают нам, выполнялась ли когда-нибудь запись в соответствующий байт эмулируемой ОЗУ. В случае возникновения неинициализированного считывания выводится адрес неверной операции считывания и имя соответствующего символа.

Вот какие результаты даёт 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, наложенное на скриншоты из игры (байты со значением 0 не показаны):

Очевидно, что metatile_data явно соответствует информации фона.

Графика метатайлов

(Чтобы посмотреть конечный результат, можно сразу перейти к разделу «Соединяем всё вместе».)

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

Каждый уровень Mario может использовать для фона только 10 из этих 64 цветов, разделённых на на 4 четырёхцветных палитры; первый цвет всегда одинаков. Вот четыре палитры для World 1-1: Давайте теперь рассмотрим пример номера метатайла, представленный в двоичном виде. Вот номер метатайла тайла камней с трещинами, который является землёй уровня 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 <--- 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)
...

При умножении индекса метатайла на 4 он становится индексом этого массива. Данные форматированы в 4 записи на строку, поэтому наш пример метатайла ссылается на двадцатую строку, помеченную комментарием cracked rock terrain.

Четыре записи этой строки на самом деле являются идентификаторами тайлов: каждый метатайл состоит из четырёх тайлов размером 8x8 пикселей, выстроенных в следующем порядке — верхний левый, нижний левый, верхний правый и нижний правый. Эти идентификаторы передаются непосредственно в PPU консоли NES. Идентификатор ссылается на 16 байтов данных в CHR-ROM консоли, а каждая запись начинается с адреса 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: 0b01111111

CHR-ROM — это фрагмент памяти read-only, к которому может получать доступ только PPU. Он отделён от PRG-ROM, в котором хранится код программы. Поэтому приведённые выше данные отсутствуют в исходном коде и их нужно получать из дампа ROM игры.

16 байта для каждого тайла составляют 2-битный тайл размером 8x8: первый бит — это первые 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

Выполняем привязку этих данных к палитре 1:

…и объединяем куски: Наконец мы получили отрендеренный тайл.

Соединяем всё вместе

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

И благодаря этому нам удалось извлечь графику уровней SMB с помощью Python!