[Перевод] Реверс-инжиниринг Fantastic Dizzy

Я написал несколько простых инструментов для извлечения, просмотра и запаковки ресурсов оригинальной игры. Инструменты выложены на GitHub.

Распаковка EXE

Двоичный файл PCDIZZY.EXE упакован в формат Microsoft EXEPack. Хотя есть множество инструментов для Linux, способных распаковывать такие исполняемые файлы, ни один из них, похоже, не поддерживает версию, использованную для Fantastic Dizzy. Поэтому для распаковки исполняемого файла я воспользовался DOS-версией UNP. После распаковки исполняемого файла его можно было загрузить в IDA. Удобно то, что распакованная версия двоичного файла по-прежнему хорошо работала, поэтому её отладку можно было выполнять с помощью дебаггера DOSBox.

Файлы данных

В игре есть два файла данных: DIZZY.NDX и DIZZY.RES. Расширения, а также размеры файлов дают нам намёк о том, что в них может содержаться. Файл NDX занимает примерно 8 КБ, а файл RES — около 800 КБ. Так как игра написана на C, мы можем поискать в IDA вызовы fopen, чтобы увидеть, где открываются файлы данных. В играх для DOS, написанных на ассемблере, для этого нужно искать инструкции int 21h (для открытия файла ah=3d). Двоичный файл Dizzy содержит функцию-обёртку вокруг fopen, позволяющую указывать основное имя и расширение файла. Она приводит нас к следующему блоку кода:

Он загружает файлы DIZZY.RES и DIZZY.NDX, а также сохраняет в глобальных переменных указатели на файлы. При обратной разработке двоичных файлов DOS возникает раздражающая проблема: регистры в них 16-битные, но указатели в некоторых случаях могут быть 32-битными. Здесь указатели FILE * имеют размер 32 бит и возвращаются из do_open_file в ax:dx. Заметьте, что строки тоже являются 32-битными указателями, и dizzy_basename передаётся вызывающей функции в стеке (и это сбило автоанализ IDA с толку — он посчитал, что это аргумент режима для fopen).

Поискав в xrefs вхождения g_dizzy_res/ndx, можно найти, где считываются файлы. На этом этапе полезен отладчик DOSBox, потому что высока вероятность множества операций считывания файлов с произвольным доступом, и использование IDA для определения считываемых смещений было бы довольно монотонным процессом. Хорошее руководство по сборке и использованию отладчика DOSBox можно взять здесь.

При совместном использовании IDA и отладчика DOSBox становится очевидным, что файл NDX используется как индекс для файла RES. Каждая запись в файле NDX занимает 16 байт; она хранит идентификатор фрагмента, его размер и смещение в файле RES. Посмотрев на то, как считываются данные RES, можно увидеть, что сначала в файле NDX проверяется байт флага. Если бит 0x80 не задан, то данные считываются непосредственно из файла RES, в противном случае выполняется более сложный путь кода. Флаг установлен для большинства фрагментов, поэтому с большой долей вероятности можно предположить, что он обозначает какой-то вид сжатия, используемый для этих фрагментов.

Сжатие

Путь сжатия начинается со считывания из основания фрагмента RES двух 32-битных слов, обозначающих исходный и конечный размеры, а затем вызывается функция распаковки. В 1991 году были популярны простое кодирование длин серий (run length encoding, RLE) и сжатие с использованием словаря, например различные алгоритмы Liv-Zempel. Начало цикла распаковки выглядит так:

Токены для распаковки получаются с помощью функции get_next_token, которая считывает следующую часть исходных данных в ax:dx со сдвигом на cl. Регистр cl используется как позиция битового сдвига с возвратом к нулю после достижения восьми. В начале цикла считывается токен и проверяется нижний бит. Если флаг установлен, то код прост:

Он всего лишь сохраняет текущий байт, получает следующий токен и продолжает работу. Если флаг сброшен, то выбирается более долгий путь кода, который завершается инструкцией rep movsb. Это указывает на то, что в сжатии используется какой-то словарь.

Алгоритм сжатия интересен по нескольким причинам. Во-первых, в нём используется кодирование с переменной длиной бита. Абсолютное значение кодируется как 1 флаг и 8-битное значение данных. Любопытно то, что битовый поток закодирован как little endian. Это немного усложняет анализ распаковки путём наблюдения за файлом RES в шестнадцатеричном редакторе. Например, если первые три байта фрагмента закодированы как абсолютные значения, то данные выстроены следующим образом:

 Байты:   AAAAAAAA BBBBBBBB CCCCCCCC DDDDDDDD Токен 1: 6543210F        7 Токен 2:          543210F        76 Токен 3:                   43210F        765

Кроме того, распаковщик может пропустить байт при считывании, если при получении следующего токена счётчик cl возвращается к нулю. Я не знаю, оптимизация ли это, или баг, или хак, созданный разработчиком игры, чтобы устранить проблему со своими инструментами.

Если флаг сброшен, то распаковщик выполняет копирование из начальной части распакованных данных. В этом случае следующие биты кодируют длину и смещение, с которого нужно выполнять копирование. Смещение закодировано в 10 или 13 битах, а нужный вариант указывает флаг. Это кажется очень странным выбором, потому что немного усложняет код, и в лучшем случае экономит всего 2 бита.

Кодирование длин серий выглядит немного странно. Распаковщик считывает биты, пока не достигнет нулевого бита. Тогда количество битов, используемых для кодирования длины, равно двум плюс количество ненулевых битов. Например, при кодировании длины 58 (0x3a) битовый поток выглядит так:

 11110 111010

Для кодирования необходимо 11 бит. Маленькие длины кодируются лучше, потому что минимальная длина бита равна 2. Копирование длин до 3 требует для кодирования всего 3 бит, до 7 требует 5 бит, и так далее. Не знаю точно, является ли такой вид кодирования распространённой техникой.

Отладчик DOSBox очень полезен и для для воссоздания алгоритма распаковки. Если вы не знаете, как должны выглядеть распакованные данные, то сложно понять, правильно ли работает распаковщик. С помощью отладчика можно пошагово пройти по всему алгоритму распаковки и сохранить дамп распакованной памяти для сравнения.

Ещё одна полезная функция — это флаг в файле NDX, сообщающий о том, что ресурс сжат. Так как оригинальная игра поддерживает неупакованные ресурсы, мы можем перепаковать файл RES без необходимости реализации алгоритма сжатия. Модифицирование и переупаковка фрагментов с последующим запуском игры является хорошим способом проверки наших предположений о форматах данных.

Уровни

Fantastic Dizzy — это игра с как бы открытым миром. Уровни — это области с вертикальным или горизонтальным скроллингом. Игрок перемещается между уровнями, доходя до конца уровня или заходя и выходя из зданий. Хотя ссылки на фрагменты в файле RES осуществляются через 16-битные идентификаторы (ID), двоичный файл игры на самом деле содержит таблицу сопоставления названий уровней с идентификаторами фрагментов. Каждый уровень состоит из нескольких фрагментов: заголовка, одного или нескольких слоёв, тайлсета и палитры. Здесь есть небольшая избыточность, потому что некоторые уровни используют одинаковую палитру и тайлсет, но не пользуются повторно одинаковыми фрагментами, поэтому в файле RES содержится множество дублирующихся ресурсов.

Слои кодируют тайлы для уровня. Для разных частей мира или для слоёв фона можно использовать дополнительные слои. Например, на уровне tree1.stg есть восемь слоёв для разных частей верхушек деревьев и один общий слой фона. Однако подводные уровни разделены на sea1.stg и sea2.stg, каждый из которых имеет один слой переднего плана и один слой фона.

Слои фона являются фонами фиксированной ширины без скроллинга, например лес в части игры с верхушками деревьев. Тайлы переднего плана и фона, которые расположены перед и за персонажем, закодированы в том же слое, что и тайлы, по которым можно ходить. Например, на скриншоте показан уровень с верхушек деревьев из начала игры:

Уровень верхушек деревьев

Он является седьмым слоем tree1.stg:

Седьмой слой уровня tree1.stg

Стоит заметить, что игрок может проходить перед хижиной, но за двумя деревьями. Вся информация тайлов содержится в одном массиве тайловой карты, находящемся в одном слое. Тайлы во фрагментах слоя закодированы двумя байтами, и нижние 9 бит используются для индекса тайла. Я разобрался с верхними битами не полностью, но в них как минимум содержится информация о сдвиге палитры для тайла и, вероятно, информация о коллизиях.

Как уровни в игре также хранятся катсцены, портреты персонажей и экран управления инвентарём. Похоже, такая техника стандартна для DOS-игр, вероятно, потому что минимизирует количество необходимого кода.

«Уровень» управления инвентарём

Спрайты

Формат спрайтов не особо интересен. Каждый спрайт — это битовая карта с одним байтом на пиксель, но всего с 16 цветами на спрайт. Использование ограниченного количества цветов было распространённой техникой в эпоху 256-цветного VGA, потому что для спрайтов можно было легко выполнять сдвиг палитры или использовать их в уровнях с другими палитрами; кроме того, это экономило выделяемое под спрайты место.

Спрайты имеют различный размер, поэтому отдельный фрагмент содержит информацию о размерах спрайта и их смещениях по x и y. Спрайты сгруппированы в наборы, но группировка выглядит довольно произвольной. Например, один набор спрайтов содержит графику экрана заставки, объекты инвентаря, а также некоторых неигровых персонажей. Это немного усложняет просмотр наборов спрайтов, потому что палитра не одинакова для всех спрайтов.

Спрайты персонажа игрока

Что ещё осталось?

Осталось подвергнуть реверс-инжинирингу еще несколько вещей. В основном меня интересуют форматы файлов данных, но есть некоторые аспекты, которые я не понимаю:

• Где хранятся местоположения объектов (ключи, фрукты и т.д.). Похоже, что они не записаны во фрагменты уровней. Возможно, они хранятся в двоичном файле игры, потому что игрок может подобрать объект на одном уровне и выбросить его на другом.
• Как работают коллизии для уровней. Игрок может проходить перед или за некоторыми тайлами, а полы могут быть плоскими или наклонными.
• Как соединены уровни. Эта информация может храниться в двоичном файле игры.
• Сдвиг палитры для тайлов на уровнях не совсем правилен. В некоторых тайлах отображются неверные цвета.
• Каждый набор спрайтов имеет три фрагмента: заголовок, таблицу и данные. Фрагменты с таблицей и данными мне понятны, но в заголовок включена какая-то информация о спрайтах, например, смещение по x и y. С его форматом я разобрался не до конца.