Spiiin's blogКогда-то я для тестов автоматического корраптера игр я находил массивы с описаниями экранов уровней обеих игр серии Flintstones для NES.
С помощью цепочки логических рассуждений (и скриптов для их автоматизации) можно получить полное описание формата уровней.
Теория
Раньше для оптимизации поиска-коррапта я использовал только знание о том, что в nes-файле хранятся как банки с кодом и данными (PRG-банки), так и банки только с видеопамятью (CHR-банки), в которых данных не может быть по определению.
Количество банков в файле можно прочитать сразу в начале заголовка nes-файла (первые 16 байт файла), и не искать ничего в CHR-банках.
Однако, можно пойти ещё дальше, и разделить данные и код.
Идея показана в видео CaH4e3’а с разбором Чёрного Плаща.
Эмулятор Fceux умеет (в меню Debug -> Code/Data Logger) во время проигрывания игры запоминать, какие байты каким образом использовались - были ли они выполнены или рассматривались как данные.
Эти данные он сохраняет в простом по формату cdl-файле (для каждого байта в ROM создаётся байт с флажками, которые сигнализируют о его типе). Этот файл можно использовать в своих скриптах, чтобы корраптить только данные, но не код, либо же загрузить в дизассемблер IDA.
Для этого понадобятся плагин-загрузчик nes-ромов и скрипт загрузки для наложения на открытый файл cdl-файла (ссылки на них тут).
Конвертация адресов
Проходим игру, с запущенным Code-Data Logger, запуская все возможные сценарии (полное проигрывание заставки и диалогов, нахождение секреток, использование способностей, все варианты поражения и победы). Дальше применяем полученный в результате cdl-файл к открытой в IDA базе (Run script и открыть файл cdl.idc, который считает что файл cdl называется также, как и rom с игрой, но имеет разширение не nes, а cdl). Получаем листинг с размеченным кодом и данными. Чтобы конвертировать абсолютный адрес в ROM (который используется в конфигах CadEditor) в адрес вида Bank:Offset в листинге IDA (загрузчик ines.ldw от Cah4eЗ), вычитаем из абсолютного адреса 0x10 и делим на размер банка - 0x2000 в загрузчике, а затем прибавляем смещение самого банка.
Для примера сверим данные для конфига второго уровня (Settings_Flintstones_2.cs) - загружаем конфиг в CadEditor и переключаем на режим отображения номеров макроблоков 
Теперь можно проверить, что в Ida по вычисленному смещению находятся те же самые данные, что и отображает CadEditor.
Для примера со скрина это: 0x00, 0x00, 0x50, 0xD0, 0x11, 0x06 и т.д. (данные читаются не по строкам, а по столбцам!).
Абсолютное смещение этих данных 0x1519, относительное вычисляем по приведённой выше формуле: 0x1519 % 0x2000 - 0x10 + bank0_base = 0x1509 + 0x8000 = 0x9509 в банке 0.
Проверяем данные по этому адресу в IDA и убеждаемся, что этому смещению находятся правильные данные. Такие рассчёты необходимо проводить для каждого адреса, используемого в IDA.
Арифметика
Дальше сравним смещения экранов первого и второго уровня. Можно предположить, что все данные между этими массивами описывают первый уровень.
Размер первого уровня - 60x8 макроблоков, значит, размер данных между массивами экранов: 0x9509 - (0x8000 + 480) = 4905 байт, в которых и закодировано всё описание уровня.
Сначала этого массива идёт описание макроблоков уровня, но проблема в том, что неясно точное количество макроблоков, некоторые макроблоки выглядят неосмысленно, если открыть уровень в CadEditor
в режиме отображения номеров блоков и приглядеться повнимательнее, то окажется, что неправильные макроблоки имеют индексы: 16,26,36,46,56,… и 1F,2F,3F,4F,5F,…
Причём, макроблоки X6 используются на уровне для отрисовки колеса и динозавра-босса, так что они просто используют какую-то технику переключения видеопамяти,а макроблоки XF (и несколько последних из набора XE) дейстительно не используются, следовательно, описание макроблоков в ROM, идёт не последовательно, а с шагом 16, и самих макроблоков получается не 256, а чуть меньше:
Почему такой странный порядок описания макроблоков? Это небольшой трюк разработчиков, чтобы избежать лишней операции сдвига – один макроблок описывается 16 байтами входящих в него индексов блоков, следовательно, шаг между макроблоками составляет 16 байт адресов.
А это именно 4 бита, так что увеличивать старшие биты в индексе макроблока на 16, а не на 1, но по такой индекс можно сразу использовать для обращения ко второму макроблоку.
Позже будет замечено, что для вторых флинтстоунов, в которых размер макроблока составляет 4x2 блоков, индексы макроблоков идут в порядке с шагом 8 (т.е. сначала растут 5 старших бит, далее разряд перебрасывается в младшие), что согласуется с этой теорией.
На скрине видно не все макроблоки в высоту, всего “неправильных” блоков получается 26, т.е. кол-во макроблоков 256-26 = 230. Проверить это можно, если изменить следующий за последним байт описания - должен измениться первый блок - кусочек чистого голубого неба. Его абсолютный адрес вычисляется как: 0x1F0 + 230(44) = 0x1050 (адрес маленьких блоков)
Получаем:
Как видим, чистое небо “перекрасилось”. Значит, размер массива макроблоков 230(44) = 3680 байт, а следующий за ним массив - описание блоков, начинается с адреса 0x1050. Дальше в IDA рассматриваем конец оставшегося куска данных (размером 0x9509 - 0x9040 = 1225 байт), и видим чёткий переход по адресу 93F0 - оттуда описание блоков сменяется из произольных байт сменяется чем-то ещё, состоящим только из 0,1,2 и 3. Очень похоже но то, что сначала идёт описание блоков и 4х кусочков-тайлов, а затем на каждый блок по одному байту, который указывает на индекс в субпалитре (в ней всего 2 значащих бита, что и даёт значения от 1 до 3).
Отсюда получается и количество самих блоков - весь массив данных до описания субпалитр, занимает 944 байта, значит, он описывает 944/4 = 236 блоков, а следом за ним идёт еще 236 байт описания палитры. Всего до описания следующего уровня осталось 45 байт (кол-во байт = 3/4 от ширины уровня, которые каким-то образом переключают палитры и загружают новые части видеопамяти при скроллинге экрана влево и вправо (теоретически, движок может позволить создать уровень, который будет выглядеть по разному при движении влево и вправо).
Автоматизация
Дальше для удобства разметки всех уровней удобно прикинуть количество макроблоков и блоков в уровне автоматически. Для этого я использую немного магии - загружу редактор CadEditor как сборку в Python с помощью модуля Python.Net, и использую Jupyter Notebook, чтобы написать интерактивный скрипт подсчёта количества макроблоков и блоков на уровне.
Рассчёт количества сделан из простого соображения - если пройтись по всем номерам макроблоков в массиве, описывающем экран, самый самый старший номер покажет, сколько всего макроблоков было использовано.
Аналогично для количества блоков - проходим по описаниям всех макроблоков и ищем самый старший индекс.
http://nbviewer.jupyter.org/github/spiiin/CadEditor/blob/master/JupyterCadEditor/CadEditor-FlinstonesRDH.ipynb
Для Flintstones : Surprise at The Dinosaur Peak все рассчёты аналогичны.
Получаем практически готовые конфиги для CadEditor’а (осталось только эмпирическим путём подобрать палитру и используемую на уровне видеопамять из доступных 16):
Заметки по формату уровней
Часто используются хитрости для уменьшения размера, причём для разных уровней - свои.
Для уровня замка используется полбанка видеопамяти, которые дублируются во вторую половину видеопамяти, Для некоторых подуровней одного уровня используется общая “раскладка”, например, для ночных джунглей, т.е. они используют общие наборы блоков и макроблоков, а также координатную сетку для описания объектов).
После разметки обнаруживается небольшое различие в экранах для европейской, американской и японской версии игры, для уровня 3 данные не влезли в первые два банка, поэтому он находится в последнем банке с данными, в котором хранятся и строки, из-за чего смещения отличаются.
В Surprise at the Dinosaur Peak размер макроблока уменьшен до 4x2, при этом удалось достичь того, что уровни состоят из намного меньшего числа макроблоков, при таком размере их функциональность намного увеличена.
В описании уровней нету данных о физике блоков, она хранится где-то среди других данных, возможно, рядом со списками объектов.