Реверсим с Python-ом олдскульную игру Super Mario

В этой статье мы собираемся зареверсить 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), размещённого в сцене (например, StaircaseObjectVerticalPipeRowOfBricks):

Подпрограмма пишет в 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.acpu.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. Он определяет, производится ли доступ к неинициализированному участку памяти. Если программа читает из адреса, в который никогда ничего не записывалось, выводится ошибка. Если бы мы могли запустить 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 ограничивается десятью из этих цветов для фона, разделённого на четыре цветовые палитры; первый цвет всегда один и тот же. Здесь мы видим палитры для World 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!

Перевод статьи «Extracting Super Mario Bros levels with Python»

Ещё интересное для вас:
Тест: какой язык программирования вам стоит выбрать для изучения?
Тест: как хорошо вы разбираетесь в Data Science?
Соревнования и бесплатная онлайн-школа для программистов