Я решил продолжить серию публикаций про внутреннее устройство NES-игр, на этот раз я расскажу об используемых мной инструментах для исследований.
Большая часть того, что необходимо исследователю, уже есть в эмуляторе FCEUX, который хорошо подходит для отладки игр. В документации стоит досконально изучить раздел Debug, каждый инструмент оттуда полезен исследователю, причём умение использовать их совместно друг с другом усиливает возможности хакера.
Однако я не буду пересказывать документацию, а остановлюсь на случаях, когда возможностей эмулятора оказывается мало и необходимо добавить новые, либо же когда существуют необычные способы найти желаемое в ROM-файле напрямую, в обход длительного изучения кода игр.
Использование Lua-скриптов
Собственно, первый способ, пример которого приведён на картинке для привлечения внимания – создание вспомогательных инструментов с помощью встроенного в эмулятор интерпретатора Lua-скрипт.
На примере выше для исследования игры (и просто читерского прохождения, при желании) используется такая возможность скриптов, как вывод изображений на экран поверх отрисовываемой эмулятором картинки.
Таким образом исследователь может заметить то, что недоступно обычному игроку, например, на скриншоте выше из трёх скрытых бриллиантов игрок может допрыгнуть только до первых двух, и никаким образом не может взять третий или даже просто догадаться об его существовании. В «Утиных историях 2» встречаются даже такие драгоценности, которые вообще размещены за пределами игрового уровня.
Другой пример скрипта с выводом на экран дополнительных данных – компас до ближайшего драгоценного камня в «Книге Джунглей»:
Естественно, визуализация информации из оперативной памяти или ROM игры не единственная возможность скриптов.
Другая часто используемая возможность – логгирование происходящего в коде игры, например, шаблон скрипта для дампа разархивированных данных сразу после их распаковки (для SMD игр, но принцип применим и для NES).
Ну, и никто не запрещает создание на Lua-скриптах полноценных утилит, вроде уже включённого в эмулятор редактора нажатых клавиш TasEditor.
Также, на мой взгляд, недооцененной является идея частичного переписывания кода игры на скриптах, когда игровые данные патчатся скриптом на лету для модификации геймплея. Proof-of-concept такого скрипта, модифицирующего врагов в «New Ghostbusters 2»:
Однако, для сложной обработки конкретной игры или создания новых методов хака стоит задуматься об использовании следующего метода.
Модификация исходного кода эмулятора
Здесь есть где разгуляться фантазии на разные темы, не касающиеся исследования игр, вроде добавления в эмуляторы поддержки достижений, 3d-рендера или улучшенной графики, однако я попытаюсь удержаться в рамках темы статьи.
Одно из направлений расширения эмулятора с целью улучшения возможностей для реверс-инженерии – прокидывание как можно большего числа его внутренних возможностей в Lua-библиотеки. Во второй статье цикла я уже показывал, как с помощью прокидывания всего пары новых функций появилась возможность сделать универсальный (подходящий для исследования любой игры) инструмент для исследования.
Другой простой и полезный пример, который пока ещё отсутствует в последней версии эмулятора – возможность модификации из скрипта памяти PPU.
Модификация эмулятора может также использоваться для того, чтобы встроить в него редактор для конкретной игры с возможностью на лету запустить её и проверить внесённые изменения:
Скрипты для статического анализа кода игры
Предыдущие две категории модификаций касались динамического анализа игры в ходе её выполнения. Однако большая часть исследования – это статический анализ ROM-файла игры (или дампов каких-либо данных из него).
Основной программой для такого анализа кода является интерактивный дизассемблер IDA. Он поддерживает ассемблер 6502, однако требует как плагина для правильной загрузки файлов в формате nes, так и набора скриптов для автоматизации рутинных действий по преобразованию загруженного файла в причёсанный код. Набор скриптов, специфичных для исследования NES-игр собран тут.
Сами скрипты для IDA могут быть написаны на встроенном языке команд idc или python, в любом случае лучше всего открыть их текстовым редактором и изучить, в большинстве случаев это помогает лучше понять команды самого IDA, которые пригодятся в работе с ним и научиться писать такие скрипты самому. Это очень пригодится, когда понадобится провести несколько сотен однотипных действий, вроде объединения байт в поинтеры или выделения массивов по некоторым правилам.
Инструменты для статического анализа данных игры
IDA хороший инструмент для анализа кода, настолько хороший, что некоторые гуру исследования игр даже считают, что только его достаточно для исследования и изменения игр. Однако, даже имея на руках разобранную до компилируемых и прокомментированных исходников игру, сложно модифицировать игровые данные – уровни, графические карты, анимации персонажей. К сожалению, формат игровых данных часто сильно отличается от игры к игре, поэтому создать универсальные инструменты, подходящие для большинства игр, достаточно трудно.
Редакторы тайловых карт
Формат хранения графических банков (самый низкий уровень хранения графики) стандартный для всех игр NES, поэтому существует множество редакторов тайловых карт, однако, среди них я не нашёл ни одной библиотеки, которая позволяла бы рендерить эти тайлы в своём приложении.
Такими программами можно редактировать тайлы графики в играх с наличием CHR-ROM – целыми банками графики. В других играх используется CHR-RAM – видеопамять тайлов в них считывается частями из банка с данными и кодом и копируется в видеопамять (при этом иногда достаточно хитрыми способами, но о них скорее лучше рассказывать в статье о компрессии данных).
На более высоком уровне игры отличаются уже настолько, что общих программ для редактирования практически нет, максимум существуют редакторы, охватывающие несколько игр на одном движке. Про свои попытки сделать универсальный редактор уровней я напишу в конце статьи, пока же приведу ещё несколько общих идей, как находить данные в играх, и утилит, реализующих эти идеи.
В качестве языка реализации я использую python за то, что на нём можно быстро и просто проверить какую-либо догадку, иногда даже прямо в интерактивном режиме.
Коррапт ROM
Собственно, как раз про эту идею была вторая статья цикла – если перебрать все возможные варианты изменения одного байта в ROM и посмотреть, как это отразится на экране, то это может помочь прояснить внутреннюю структуру игры. После этого возможно даже составить простой вариант редактора игры – нужно заготовить набор картинок-блоков верхнего уровня, из которых строится экран, не вникая до конца, как строятся сами эти картинки из данных ROM и отобразить массив этих картинок, обнаруженный этим методом.
Поиск блоков
Можно также зайти с другой стороны.
Фон, который отображается на экране, задаётся массивом индексов тайлов видеопамяти по фиксированному адресу PPU – для NES существует 4 экранные страницы, которые в зависимости от настроек PPU могут разными способами выводится на экран. Не важно, что именно будет на экране, достаточно просто захватить какую-нибудь загруженную страницу для анализа.
Первая экранная страница (Name Table) расположена по адресам PPU $2000-$23BF.
Её содержимое в эмуляторе FCEUX можно посмотреть в окне Debug -> Name Table Viewer:
А также в виде байт в окне Debug -> Hex Editor, View -> PPU Memory (перейти по адресу $2000).
Здесь же можно сделать дамп всей видеопамяти, который пригодится нам для анализа (File->Dump to File->PPU Memory).
Это просто массив из 960 индексов маленьких тайлов видеопамяти размером 8x8 пикселей. При этом, после реверса большого числа игр известно, что игровые экраны часто описываются блоками большего размера, например, 16x16 или 32x32 пикселей. Таким образом, если мы предположим некоторый размер блока (для начала попробуем самые стандартные – 2x2 тайла, выделены на скриншоте красной рамкой), то мы можем разбить данные из экранной страницы на участки, в каждом из которых окажется описание одного блока.
Так получается список из всех блоков, которые присутствуют на экране. Причём у нас «чистые» описания блоков, без информации о спрайтах персонажей (спрайты рисуются другим способом), и независимый от анимации (анимации фона практически всегда делаются с помощью изменений палитры либо самой видеопамяти, номера тайлов в Name Table остаются неизменными). Однако мы не знаем номера блоков.
У нас есть описание блоков на экране, но мы не знаем их порядок хранения в ROM. Тем не менее, мы можем с некоторой вероятностью предположить, где именно расположено описание блоков. Алгоритм для этого такой:
1. Проходим по всему ROM и размечаем все адреса, по которым обнаруживается какой-нибудь блок, при этом сохраняем его номер (настоящий номер может быть другой, нам важно отметить только отличия блоков друг от друга).
2. Находим область в ROM, в которой обнаружено наибольшее количество РАЗНЫХ блоков. С наибольшей вероятностью именно это и есть описание блоков.
https://gist.github.com/spiiin/500262e8d9da86f10a093bbb41833360
Таким образом, мы можем найти блоки размером 2x2 в играх, в которых они хранятся последовательно.
Это уже неплохо, но есть способ кардинально улучшить результаты работы алгоритма. Дело в том, что существует ограниченное количество основных размеров блоков и способов их хранения в ROM, и мы можем перебрать их все.
Основные размеры блоков: 2x2, 4x2, 2x4 и 4x4, но в случае необходимости легко добавить и другие размеры.
Со способом хранения их в ROM немного хитрее, блоки могут храниться как линейно, так и разбитыми на части массивами (Structure of Arrays, сокращенно SoA ), т.е. сначала в ROM хранится массив только первых частей блоков, за ним — массивы со следующими частями. Чаще всего такие массивы хранятся друг за другом, при этом промежуток между началами массивов равен количеству блоков. Чтобы найти в ROM такие SoA-массивы, мы должны узнать их длину, что можно сделать перебором всех вариантов (частенько в играх используется по 256 блоков, так что начинать проверку стоит с этого числа и постепенно его уменьшать).
Всё это выглядит достаточно запутанно, ведь мы опираемся только на вероятность того, что игра использует определённый вид блоков, но на практике утилита находит блоки в 80-90% проверенных игр!
https://github.com/spiiin/NesBlockFinder
Вдобавок, она позволяет отсеять игры с необычной структурой (неблочной), чтобы пристальнее их изучить.
Сравнение CDL-файлов
Эмулятор FCEUX умеет в ходе эмуляции каждую инструкцию отмечать, какие байты были интерпретированы как код, а какие – как данные (меню Debug -> Code/Data Logger...). Эта фича полезна сама по себе и тесно интегрирована с другими отладочными возможностями эмулятора – попробуйте включить этот режим и посмотреть, как изменились другие отладочные окна. Однако, я хочу рассказать об её одном частном применении. Если сохранить два таких cdl-файла, один ДО совершения изучаемого действия, а другой сразу же ПОСЛЕ его окончания, то разница между двумя такими файлами покажет только те данные (или код), которые были использованы во время совершения действия. При грамотном отсечении можно найти нужные данные, всего лишь правильно выбрав два момента времени между измеряемыми событиями.
Формат файла достаточно прост, как и скрипт сравнения, но пользы он может принести очень много, на нём вообще можно построить отдельную методологию отладки.
Компрессоры/Декомпрессоры
Эту тему невозможно раскрыть в паре абзацев, да и она будет слишком упрощённой в контексте только NES-игр, поэтому она заслуживает отдельной статьи.
Универсальный редактор уровней CadEditor
Собственно, изначально эта программа создавалась для отображения уровней в игре «Chip & Dale» (Chip And Dale Editor), дальше по просьбам она была переделана в редактор и со временем обрастали поддержкой других игр Capcom («Darkwing Duck», «Duck Tales 1-2», «Tale Spin», «Little Mermaid»).
Позже выяснилось также, что принципы блочного построения уровней в этих играх очень похожи на способы организации уровней из многих других игр, однако дьявол кроется в деталях – мелкие отличия в каждой игре требуют описывать внутренние структуры редактора максимально гибко, чтобы с помощью комбинаций этих структур можно было описать формат уровней для игр, для которых он изначально не предназначался, без изменения ядра самого редактора.
Фича, с помощью которой обеспечивается универсальность редактора – так называемые конфиги игр. Это скриптовые файлы на языке C#, в которых описано, как именно загружать данные конкретной игры. Почему именно C#? Редактор уже был написан на этом языке и это позволило легко переносить код из ядра в конфиги, не меняя его, что пришлось бы делать, если бы использовался более классический скриптовый язык, вроде Lua.
Использование полноценного языка вместо простого файла настроек позволяет описывать в конфигах свои функции загрузки и сохранения данных любой требуемой сложности. Скрипты представляют собой обычные текстовые файлы, что позволяет пользователям в случае необходимости создавать свой конфиги без перекомпиляции редактора, используя уже существующие конфиги в качестве шаблонов. В комплекте с редактором идут около 500 конфигов для 60 разных игр, около 100 из них сделаны пользователями редактора без моего участия, для игр, в некоторые из которых я даже никогда не играл:
Однако в данный момент, несмотря на попытки сделать универсальный редактор, обнаруживаются игры, которые невозможно описать без модификации самого редактора (тем не менее, множество игр уже можно добавить и так). Чтобы собирать информацию о таких играх с необычной структурой, я пошёл ещё немного дальше и начал использовать сам редактор как библиотеку для Python, чтобы исследовать формат игр перед добавлением их в редактор и тестировать правильность понимания построения уровня конкретной игры. Я реализовал это в виде блокнотов Jupyter, из-за того, что в них удобно как писать код в интерактивном режиме, так документировать его.
http://nbviewer.jupyter.org/github/spiiin/CadEditor/blob/master/JupyterCadEditor/CadEditor-example-yonoid.ipynb
Составление из базовых тайлов больших игровых структур и сборка в итоге целого уровня напоминает сборку пазла из тысяч кусочков, и доставляет такое же удовольствие, когда, наконец, каждый кусочек оказывается на своём месте.
В следующей статье не будет такого обилия технической информации и я приведу примеры сборки уровней игр с нестандартной структурой или использованием необычных модификаций стандартной блочной архитектуры. Также вы можете в комментариях назвать игру на NES, формат уровней которой интересен вам, возможно, я исследую и её тоже.
Автор: spiiin
