Spiiin's blogИзобрёл ещё один способ реверса формата уровней NES-игр.
Способ во многом лучше предыдущего (автокорраптера) и работает практически в любой игре:
не надо ловить момент старта уровня, достаточно сделать дамп памяти PPU в любой момент.
не надо использовать графику вообще, метод работает напрямую с данными от PPU консоли.
намного меньше усилий со стороны пользователя.
способ сочетается с предыдущим (можно использовать оба метода для достижения лучшего результата).
работает быстрее - перебирает все возможные варианты размещения блоков в ROM за 15-20 секунд.
универсальнее (сработал в 48 из 50 проверенных игр, будет время – прогоню более полные тесты).
Теория
Фон, который отображается на экране, задаётся массивом индексов тайлов видеопамяти по фиксированному адресу PPU – для NES существует 4 экранные страницы, которые в зависимости от настроек PPU могут разными способами выводится на экран.
Нам тут даже не важно, что именно будет на экране, достаточно просто захватить какую-нибудь загруженную страницу для анализа. Подробнее о страницах и адресах.
Первая экранная страница расположена по адресам PPU $2000-$23BF. Её содержимое можно в эмуляторе FCEUX можно посмотреть в окне Debug -> Name Table Viewer:
А также в виде байт в окне Debug -> Hex Editor, View -> PPU Memory (перейти по адресу $2000).
Здесь же можно сделать дамп всей видеопамяти, который пригодится нам для анализа (File->Dump to File->PPU Memory).
Идея метода
Мы знаем (путём реверса нескольких десятков игр), что в большинстве игр на NES для сохранения места в ROM уровни описываются не с помощью тайлов, а путём более крупных структур – блоков.
Таким образом, если мы предположим некоторый размер блока (для начала попробуем самый стандартный – 2x2 тайла), то мы можем разбить данные из Name Table на участки 2x2 тайла, в каждом из которых окажется описание одного блока. https://gist.github.com/spiiin/dfabd3cd7554c1bc0bdb1c0133e723b4
Так мы получаем список из всех блоков, которые присутствуют на экране. Причём у нас “чистые” описания блоков, без информации от спрайтов (спрайты рисуются другим способом), и независимый от анимации (анимации фона практически всегда делаются с помощью изменений палитры либо самой видеопамяти, номера тайлов в Name Table остаются неизменными).
На скриншоте выделены первые 4 блока размером 2x2 тайла, для лучшей видимосте перекрашенные выделяющимися по цвету тайлами.
У нас есть описание блоков на экране, но мы не знаем их порядок хранения в ROM. Тем не менее, мы можем с некоторой вероятностью (как покажет практика, вероятность очень высокая) предположить, где именно расположено описание блоков. Алгоритм для этого такой:
Проходим по всему ROM и размечаем все адреса, по которым обнаруживается какой-нибудь блок, при этом сохраняем его номер (настоящий номер может быть другой, нам важно отметить только отличия блоков друг от друга).
Находим область в ROM, в которой обнаружено наибольшее количество РАЗНЫХ блоков.
С наибольшей вероятностью именно это и есть описание блоков.
https://gist.github.com/spiiin/500262e8d9da86f10a093bbb41833360Таким образом, мы можем найти блоки размером 2x2 в играх, в которых они хранятся последовательно. Это уже неплохо, но есть способ кардинально улучшить результаты работы алгоритма.
Дело в том, что существует ограниченное количество основных размеров блоков и способов их хранения в ROM, и мы можем перебрать их все. Основные размеры блоков - 2x2, 4x2, 2x4 и 4x4, других не попадалось, но в случае необходимости легко добавить и их, нужно просто параметризировать итератор выбора индексов размером блока и скармливать ему другие индексы блоков (также меняя и порядок - блоки описываются как построчно, так и постолбцово).
Со способом хранения их в ROM немного хитрее, блоки могут храниться в ROM как линейно, так и разбитыми на части массивами (Structure of Arrays, сокращенно SoA ), т.е. сначала в ROM хранится массив только первых частей блоков, за ним - массивы со следующими частями.
Чаще всего такие массивы хранятся друг за другом, при этом промежуток между началами массивов равен количеству блоков. Чтобы найти в ROM такие SoA-массивы, мы должны узнать их длину, что можно сделать перебором всех вариантов (частенько в играх используется по 256 блоков, так что начинать проверку стоит с этого числа и постепенно его уменьшать). Я для такого поиска шарахнул регулярное выражение вида:
def buildReWithStride(blockStr, stride): strideStr = r".{%d}"%stride #пропускаем stride символов |
что, конечно, не самое лучшее решение, зато укладывается в пару строк кода. С такими методами поиска я приступил к охоте на блоки в играх.
Результаты находок разных типов
Блоки 2x2, линейные: 
Блоки 2x2, SoA: 
Блоки 4x4, линейные: 
Блоки 4x2, линейные: 
Необычные типы блоков Описание всего уровня блоками 2x2: 
Автоблоки из видеопамяти построчно: MegaMan, Banana Prince (достаточно открыть банк видеопамяти, чтобы увидеть блоки)
Несколько раздельных наборов блоков: Jungle Book (перебором обнаруживаются обе части).
Возможные улучшения
Самое банальное – перебирать как можно больше разных размеров блоков, что не очень нужно, так как другие размеры практически не встречаются.
Расширить метод для других платформ. Name Table есть ещё много где, и описание блоков хранится в ROM в несжатом виде (блоки по определению уникальны, следовательно, практически не сжимаются).
Необходимо работать не только с байтами, но и другими размерами слова.
После того, как найден точный адрес описания блоков в ROM, можно сделать ремаппинг индексов блоков в Name Table на правильные. После этого мы получим массив из индексов не тайлов, а блоков, и сможем в нём искать в ROM описание следующей единицы построения уровня – макроблоков (для игр, в которых это актуально). Здесь уже требуется больше ручной работы и понимания процесса (кроме того, часто макроблоки не используются).
Пример такого поиска для Чёрного Плаща: https://gist.github.com/spiiin/3635525e6846d4eaf33d7eafb5a6673f
