После интересной обратной разработки игрового движка Comprehend (см. Recomprehend) я подбирал новый проект для реверс-инжиниринга игры под DOS. За долгие годы разные люди реверсировали множество старых популярных игр и опубликовали для них спецификации и инструменты. Например, на сайте shikadi.net есть куча информации об играх, в которые я играл в детстве.
Я обнаружил, что для реверс-инжиниринга игры The Lost Vikings компании Blizzard (тогда она называлась Silicon and Synapse), похоже, не предпринималось никаких серьёзных попыток. Игра была выпущена в 1993 году, на закате эры DOS, и очень нравилась мне в юности. The Lost Vikings — это головоломка-платформер, в которой игрок управляет тремя викингами, каждый из которых имеет собственные умения. Викингам нужно объединить свои силы для решения загадок и прохождения уровней с различной тематикой: космический корабль, доисторический мир, Древний Египет. На изображении ниже показан первый уровень игры (источник: Strategy Wiki):
Казалось, что эту игру разобрать будет довольно просто. Уровни основаны на тайловых картах и содержат простые загадки: кнопки, включающие и отключающие объекты, передвижные ящики и поднимающий предметы кран. И на самом деле, бóльшая часть проекта по обратной разработке была достаточно прямолинейной. У игры есть один пакетный файл данных, содержащий сжатые блоки файлов. Блоки кодируют различные ресурсы игры, такие как спрайты, карты, звуки и т.д. Я написал несколько утилит, которые можно использовать для просмотра ресурсов игры: The Lost Vikings Tools.
Интересный аспект работы движка заключается в том, что объекты в игре используют шаблонную систему классов. Для каждого мира в файле данных есть блок, определяющий набор классов объектов. Например, на показанном выше первом уровне обе двери аварийного выхода имеют тип класса 0x4f. Реверс-инжиниринг кода классов объектов привёл к следующей функции:
Пропуская пока альтернативный путь к адресу 0x142a2, этот код использует si как индекс в структуре массива классов объектов (каждый шаблон класса состоит из 0x15 байт). Слово в смещении 0x3 — это структура, используемая в качестве адреса в сегменте ES. Сегмент ES содержит все данные блока шаблона класса объекта. Затем код переходит в цикл по адресу 0x142a6. Этот цикл получает следующий байт из сегмента ES и использует его как индекс таблицы функций. На каждом шаге цикла bx содержит адрес в сегменте ES, а si содержит текущий код операции (опкод).
Интересно заметить, что в цикле используется безусловный переход, и поэтому он никогда не завершается. По крайней мере, при нормальном выполнении программы. Похоже, что у каждого класса объекта есть какая-то связанная с ним программа, основанная на опкодах, которая интерпретируется этой функцией. Первоначально я просто исследовал некоторые из функций в таблице вызовов. Вот как выглядит первая в режиме графов IDA:
Анализ стека IDA здесь выполнить не удаётся, и на то есть причины. pop ax в качестве первой команды функции — это довольно странное поведение. Команда вызова x86 загружает указатель команды (ip) в стек, а команда ret извлекает его, чтобы вернуть вызывающей функции. Команда pop здесь фактически отбрасывает адрес возврата. Это значит, что следующая команда ret перейдёт назад на два кадра стека вместо одного. Этот опкод выполняет выход из бесконечного цикла интерпретатора.
Чтобы понять, как на самом деле реализован опкод, нам нужно переключиться в линейный режим IDA:
Я прокомментировал имена функций их соответствующими номерами опкодов, чтобы эта часть кода была понятней. Здесь довольно умно выполняется повторное использование кода. Легче всего начать с изучения опкода 0x03. Вспомним, что в обрабатывающем опкоды цикле есть данные блоков классов объектов, загруженных в сегмент ES, а bx используется в качестве указателя команды виртуальной машины. Таким образом, опкод 0x03 — это команда безусловного перехода. Она загружает слово по адресу текущего указателя команд, устанавливает на него указатель команд, а затем возвращается к циклу обработки опкодов.
Работая в обратном порядке, опкод 0x05 пропускает следующее слово-операнд и сохраняет следующий адрес в массив. Реверс других функций показывает, что word_28522 — это индекс текущего экземпляра объекта, то есть этот опкод хранит один адрес для каждого объекта на уровне. Затем он восстанавливает значение bx и проходит в коде до опкода 0x03 (переход). Поэтому этот опкод, похоже, является очень ограниченной командой вызова со всего одним уровнем стека.
Опкод 0x00 сохраняет текущий указатель функции в глобальный массив. Заметьте, что он отличается от опкода 0x05, который сохраняет адрес после операнда адреса вызова. Затем он переходит к обработчику опкодов вызовов. Однако, команда не будет выполнена из-за первой команды pop. Вместо этого вызывающий цикл выполнит выход. Адрес, сохраняемый этой командой, используется как альтернативный путь входа к циклу вызова функций, который я не стал рассматривать выше. Здесь опкод 0x00 используется как что-то вроде выхода из сопрограммы (coroutine). Он сохраняет текущее положение в программе и выходит из цикла обработки опкодов, позволяя игровому движку выполнить другие задачи: обновить графику, получить данные ввода пользователя и т.д., возвращаясь к тому, откуда выполнила выход программа виртуальной машины. Это позволяет программе виртуальной машины выполнять сложные задачи без простоя остальной части игрового движка.
На этом этапе у меня уже было общее представление о том, как работает обработчик опкодов виртуальной машины. Изучив таблицу вызовов функций, я нашёл там примерно 215 реализованных опкодов, поэтому вместо их непосредственной обратной разработки по порядку я начал писать простой скрипт, чтобы декомпилировать программу для нужного класса объектов. Таким образом я мог сосредоточиться только на опкодах, вызываемых объектами на первом уровне.
В этот момент я в основном пытался определить, сколько операндов имеют опкоды, и в чём заключаются их основные задачи. Если обработчик опкодов был коротким, я обычно пытался полностью разобраться, что он делает. Если он был больше нескольких блоков кода, то я тогда просто старался выяснить, сколько операндов он имеет, и выполняет ли он условный переход или вызов. Я делал так, потому что иногда назначение опкода становится очевидным из окружающего его контекста в дизассемблированной программе, в котором зачастую проще разобраться, чем выполнить реверсирование кода.
Вот пример простого опкода:
Этот опкод получает операнд-слово и сохраняет его в глобальной переменной. Реверсирование других функций показывает, что эта глобальная переменная является временным хранилищем или регистром общего назначения. В виртуальной машине есть только один такой регистр, но он также имеет вот такой опкод:
Этот опкод сохраняет текущее значение регистра общего назначения по адресу в сегменте данных (DS), указанному операндом-словом. Программы в файле данных игры используют этот опкод для записи в определённые части игровых данных, таких как слоты инвентаря викингов. Несколько смещений DS также используются как дополнительные временные значения, когда их требуется больше одного. Например, смещения 0x0206 и 0x0208 часто используются как временные координаты x и y объекта.
Этот опкод и противоположный ему опкод 0x53, считывающий из DS в регистр общего назначения, интересны тем, что они могут считывать и записывать в DS любые игровые данные, а не только те, которые назначены создателями оригинальной игры. Это даёт нам интересные перспективы расширения оригинальной игры.
Более сложным является опкод 0x14:
На первый взгляд, его реверсирование не должно вызвать проблем. Он получает байтовый операнд и вызывает пару подфункций. Затем он получает ещё один байтовый операнд и снова вызывает те же подфункции. Но если взглянуть на первую подфункцию (sub_15473), то дело немного усложняется:
Анализ стека IDA выполнить снова не удаётся, и он показывает четыре выхода из этого блока, который я обрезал, потому что все они неверны. На самом деле происходит вот что: первый байтовый операнд передаётся в эту функцию в ax, который затем используется как индекс таблицы переходов. Хотя для ax выполняется операция AND с 7, на самом деле в таблице переходов есть всего четыре действительных значения. Взглянув на тип 0 в таблице переходов, мы увидим следующее:
Здесь загружается непосредственный операнд-слово. Этот фрагмент функции выполняет retn, который возвращается из обработчика опкода 0x14 верхнего уровня. Нетрудно заметить, почему у IDA возникают проблемы с правильным дизассемблированием этого кода.
Другие записи в таблице переходов различными способами загружают значения, а затем каждая из них снова делает retn. Тип 1 берёт байтовый операнд, используемый в качестве индекса поля объекта. Объект имеет поля для таких значений, как смещения x и y, флаги и т.д. Тип 2 получает операнд-слово и загружает значение из DS (как опкод 0x53 из примера выше). Тип 3 получает байтовый операнд и загружает поле целевого объекта для выполнения действий, например, для распознавания столкновений.
Вернёмся обратно к обработчику опкода 0x14 верхнего уровня. Здесь следующей вызывается sub_15470. Она всего на три байта впереди первой вызванной подфункции. И в этом снова есть есть умная оптимизация кода. Эта подфункция просто сдвигает ax вправо на 3, а затем переходит к коду, который мы только что реверсировали выше. Итак, первый байтовый операнд опкода 0x14 используется для кодирования того, как получаются два последующих аргумента. Реверсирование обработки второго байтового операнда показывает, что он работает таким же образом.
После получения всех его операндов (переменной длины) обработчик опкода 0x14 вызывает sub_13809. Я не буду вставлять сюда код, потому что функция довольно большая и вызывает множество других подфункций, каждая из которых тоже объёмна. Это один из тех случаев, когда я не заморачивался реверсированием действий функции, потому что позже они станут понятны из контекста.
Команды в виртуальной машине The Lost Vikings имеют переменную длину. В случае опкода 0x14 и других похожих опкодов определение длины требует декодирования некоторых операндов. Наличие команд переменной длины означает, что программу нужно дизассемблировать итеративно, как минимум определяя количество операндов для каждого нового опкода в программе. Если бы все опкоды имели фиксированную длину, то можно было бы пропускать неизвестные опкоды.
Существуют также команды, выполняющие стандартные операции, используемые многими программами. Например, многие программы выполняют суммирование или вычитание из текущего положения объекта на основании его направления. Это можно закодировать как несколько команд, но опкод 0x91 получает единственный операнд-слово как смещение в DS, а затем прибавляет или вычитает из него текущее значение временного регистра на основании текущего горизонтального направления объекта (флаг 0x0040). Следующий псевдокод демонстрирует работу опкода 0x90.
Благодаря этому на кодирование требуется гораздо меньше байтов, особенно потому, что эта операция выполняется несколькими программами. Во времена DOS, когда пространство на диске и вычислительная мощь были в дефиците, это имело большой смысл. Для современного реверс-разработчика это просто добавляет несколько новых опкодов, в которых нужно разобраться.
Я написал простой скрипт на Python, который может дизассемблировать программы виртуальной машины в то, что смутно напоминает C. Он линейно декодирует команды программы, сохраняя адреса переходов и вызовов. Когда он натыкается на функцию, останавливающую или перенаправляющую выполнение кода, например, возврат или безусловный переход, он останавливается и проверяет другие непосещённые адреса в программе.
В программах виртуальной машины использовали хитрости оптимизации, похожие на применённые в двоичном коде игры. Например, некоторые пути выхода из подпроцедур в программах виртуальной машины используются повторно с помощью перехода к ним из других подпроцедур. Дизассемблер справляется с этим, декодируя команды дважды, поэтому две подпроцедуры могут иметь код с одинаковыми адресами.
Дизассемблер может обрезать операции доступа к временному регистру, чтобы сделать конечный код более читаемым. Например, в программах виртуальной машины часто используются такие последовательности:
Дизассемблер реорганизует их следующим образом:
Дизассемблер не пытается перестроить блоки кода в такие конструкции, как if или while, поэтому получающиеся программы выглядят как спагетти-код. Некоторые большие программы сами по себе можно сделать полноценными проектами для обратной разработки.
Я начал с программы для башни с пушкой в верхней левой комнате первого уровня (класс объекта 0x04). Мне показалось, что это должна быть довольно простая программа. Башня с пушкой стреляет снарядами с определённым интервалом, и викинги не могут её уничтожить. Ниже показана программа, полученная после обработки моим дизассемблером. Над каждым опкодом есть комментарий, показывающий в квадратных скобках адрес, в кавычках — опкод, после чего идут операнды.
Программа башни выглядит вот так:
Здесь можно заметить следующее:
Рефакторинг программы помогает понять, что в ней происходит:
Стоит заметить, что в программе всё ещё есть части и опкоды, предназначение которых я не определил, но поведение башни достаточно понятно. Поле update_time объекта используется для кодирования скорости стрельбы башни. Программа сама не занимается уменьшением этого значения (по крайней мере, очевидным образом). Возможно, эту задачу выполняет один из неизвестных опкодов или какая-нибудь часть основного игрового движка.
Разумеется, возможность изучить исходные программы, используемые игрой, интересна сама по себе. Но самое любопытное в способе реализации виртуальной машиной поведения объекта заключается в том, что мы можем изменять его или создавать новые программы. Это было бы гораздо проще, если написать компилятор (о нём я расскажу ниже), но пока мы можем лишь менять значения в hex-редакторе вручную.
Повторюсь — я выбрал для модификации программу башни с пушкой, потому что она довольно проста. Сначала я решил изменить тип объекта, которым стреляет башня. Успех оказался переменным. Попытки реализовать стрельбу одними объектами, например, зелёным инопланетянином, приводили к «вываливанию» или зависанию игры. Выбор других объектов приводил к тому, что башня ничем не стреляла. Мне удалось заставить её стрелять огненными стрелами (в обычной игре это бонус, который может использовать один из викингов). Также довольно просто увеличить темп стрельбы пушки уменьшением значения поля update_time.
Вторая сделанная мной модификация стала немного более амбициозной: я заставил башню вместо стрельбы двигаться. Опкод (0x14) для создания пули довольно длинный:
Виртуальная машина предоставляет возможность использования однобайтовой команды nop (0x01) (что довольно благородно с её стороны), которую можно использовать для замены этой команды. Команды выше уже установили DS[0x0206] в текущее положение по оси x башни плюс-минус 4, в зависимости от её направления. Поэтому мне просто нужно добавить команды для присвоения этого значения текущему положению x. Для этого требуются всего две команды:
Благодаря этому изменению башня может двигаться, но её ничего не останавливает. Я пробовал реализовать распознавание столкновений и поворот обратно, но правильной работы добиться не удалось. Требуется более глубокая обратная разработка.
Я собрал небольшое видео моих модификаций:
Также я выложил в открытый доступ свой дизассемблер:
https://github.com/RyanMallon/TheLostVikingsTools/blob/master/dissassembler/lv_vm_disasm.py
В предыдущем разделе мы говорили о реверс-инжиниринге виртуальной машины, используемой для реализации объектов в Lost Vikings.
Раньше я тестировал некоторые из опкодов эмпирически, ручным патчингом исходных блоков данных в шестнадцатеричном редакторе. Такой подход работал, но был очень монотонным и не очень хорошо масштабировался для экспериментов с большими программами или с программами, содержащими циклы и переходы. Выше я предположил, что создание простого языка и компилятора будет полезно для дальнейшей обратной разработки виртуальной машины. Поэтому я его написал.
Для помощи в обратной разработке виртуальной машины и удобства создания новых программ я решил написать компилятор. Чтобы не усложнять, я выбрал однопроходный метод рекурсивного спуска.
Дизайн компилятора в основном позаимстован у компиляторов типа PL/0, которые часто изучают на университетских курсах о компиляторах (см. PL/0). Не буду вдаваться в подробности написания базового компилятора, потому что в Интернете достаточно информации об этом. В сущности, компилятор получает исходную программу, выполняет лексический анализ для создания потока токенов, а затем производит синтаксический анализ программы, генерируя код.
Я создал очень простой C-подобный язык для реализации на нём программ объектов. Одно из преимуществ использования C-подобного языка заключается в том, что можно использовать существующий препроцессор C для поддержки определения констант и макросов. Язык не позволяет определять переменные, программист ограничен полями объектов и глобальными переменными, определяемыми виртуальной машиной. Встроенные функции обеспечивают поддержку генерации опкодов для операций получения результатов и создания объектов. Язык имеет незначительные отличия от C, просто чтобы сохранить простоту лексического и синтаксического анализаторов.
Снова возьмём для примера объект башни с пушкой из первого уровня, который мы модифицировали выше. Реализовать стреляющую стрелами башню на Lost Vikings C можно следующим образом:
Каждому объекту нужен основной цикл, который никогда не должен завершаться. Основной цикл должен вызывать функцию yield(), чтобы позволить выполнять выход циклу обработки виртуальной машины. В противном случае движок игры «зависнет». Вызов update_obj() делает то, что следует из его названия.
Использование многих полей объектов относятся к конкретному объекту. В нашем случае я использовал поле field_30 в качестве таймера для управления скоростью стрельбы башни. Когда таймер достигает нуля, башня стреляет, а затем переустанавливает таймер.
Единственное, что осталось — сгенерировать код для этой программы.
Виртуальная машина The Lost Vikings не является идеальной средой для простого компилятора. Компиляторы типа PL/0 обычно генерируют код для абстрактной стековой машины, поэтому простое выражение типа:
сгенерирует вот такой код:
Однако у виртуальной машины The Lost Vikings нет стека. У неё есть простой временный регистр, поля объектов и глобальные переменные. Показанная выше программа транслируется в виртуальную машину Lost Vikings следующим образом:
Для неё гораздо сложнее генерировать код при компилировании из языка общего назначения. Возможно, потребуется генерировать в первом проходе промежуточное представление, а затем во втором проходе изменять порядок команд и т.д. для генерирования конечного кода.
Я пришёл к следующему решению: создание абстрактной стековой машины, для которой можно удобно компилировать поверх виртуальной машины Lost Vikings. Это возможно сделать благодаря опкодам для загрузки и хранения глобальных переменных. Эти опкоды получают в качестве своих операндов смещения в сегменте данных (DS) игры. Это позволяет использовать опкоды для загрузки и хранения любого произвольного адреса в DS.
Компилятор генерирует код, помещая фальшивый стек в верхнюю часть (0xf004) сегмента данных. Два адреса в основании фальшивого стека зарезервированы под специальный регистр: 0xf000 — это нулевой регистр, а 0xf002 — флаговый регистр, используемый для сравнения. Приведённое выше выражение теперь можно скомпилировать так:
Несмотря на не очень высокую производительность, этот код очень просто генерировать. Моя цель — создание компилятора для тестирования небольших программ, чтобы определить, что делают опкоды или их сочетания. Пока меня не очень волнует эффективность, с точки зрения и времени, и размера кода.
Вторая проблема в создании языка для оригинальной виртуальной машины заключается в том, что многие опкоды выполняют условный вызов функций. Например, опкод 0x1a проверяет, столкнулся ли текущий объект с викингом, и если это так, то он выполняет команду вызова. Желательнее, чтобы программист мог сам решать, нужно ли использовать вызов или переход (например, конструкцию с if).
Я реализовал это, сгенерировав код для стандартной вспомогательной функции, устанавливающей флаг и выполняющей возврат. При генерировании кода для опкода, выполняющего условный вызов, сначала сбрасывается флаговый регистр. Если опкод выполняет вызов, то флаговый регистр устанавливается. Затем можно проверять флаг для выполнения вызова перехода. Например, следующий код:
генерирует вот такой код:
Нулевой регистр используется здесь для сравнения его со значением флага. В начале каждой программы компилятор генерирует команды для сброса нулевого регистра.
Программы виртуальной машины для каждого мира игры упакованы в отдельный блок в файле данных. Компилятор использует простой подход: он добавляет сгенерированнй код к концу блока, а затем модифицирует заголовок программы объекта, чтобы тот указывал на патч в программе.
Всё это в теории работает, но на деле есть одна небольшая проблема. Игра хранит программы виртуальной машины в дополнительном сегменте (ES) в месте, указываемом с помощью API выделения памяти DOS. Функция выделения памяти выглядит так:
Вызов выделения памяти для виртуальной машины выглядит так:
То есть для программ выделяется 0xc000 байт (48 КБ). Проблема в том, что блок для программ мира космического корабля уже занимает 48972 байт, то есть в его конце остаётся всего 180 байт для патча в новой программе. Не так уж много, когда работаешь с компилятором, генерирующим очень избыточный код.
Я обнаружил эту проблему, когда пытался скомпилировать большую программу. Игра начала вести себя хаотично, она или «зависала», или случайным образом пропадала башня с пушкой. Такие ошибки довольно сложно отследить, потому что это может быть багом в моём компиляторе или сгенерированном коде, проблемой недопонимания принципа работы какого-то опкода, или багом/ограничением оригинальной игры.
Быстрым решением является патчинг двоичного кода игры для расширения размера памяти, выделяемого под программу. Увеличение выделенного размера до 0xd000 байт (52 КБ) не вызывает проблем и даёт достаточно места для экспериментов с простыми программами. Я добавил команды для этого в мой компилятор.
Целью создания компилятора было упрощение обратной разработки виртуальной машины. Для тестирования нового опкода необходимо добавить запись в словарь функций в классе генератора кода и создать функцию генерирования команд для опкода. Например, одним из первых экспериментов была работа с 0x41, который используется в нескольких дизассемблированных программ, таких как объекты кнопок/значков с вопросительным знаком.
Его запись словаря в компиляторе изначально выглядела так:
Кортеж указывает, будет ли функция возвращать значение, количество передаваемых ей аргументов и функцию генератора кода. Функции помечаются как возвращающие значение, если опкод выполняет условный вызов или переход.
После изучения опкода в IDA я знал, что опкод 0x41 выполняется безусловно и получает четыре аргумента. Его аргументы используют кодирование типа переменной, который я описывал в начале статьи. Он генерирует следующую функцию:
Вспомогательная функция pack_args обеспечивает упаковку аргументов типа переменной.
Теперь её можно вызвать в короткой тестовой программе. Для тестирования я использую функцию collided_with_viking (опкод 0x1a), поэтому тестируемый опкод запускается только при касании викингом башни. Заметьте, что функция collided_with_viking получает единственный байтовый операнд, назначение которого я не знаю, но значение 0x01 вполне для него подходит. Также я использую как одноразовый триггер поле field_32 объекта, чтобы тестируемый мной опкод срабатывал только при первом касании викингом объекта.
Моя тестовая программа выглядит так:
В результате в игре возникает вот такой графический «глитч»:
Похоже, что опкод используется для отображения диалогового окна, но непонятно, почему возникает эта графическая ошибка. Если посмотреть на некоторые дизассемблированные программы из оригинальной игры, то видно, что за опкодом 0x41 обычно следуют неизвестные опкоды 0xcb и 0x42, ни один из которых не получает мои аргументы. При добавлении встроенных программ для этих опкодов в компиляторе и повторном запуске игры отображается диалоговое окно, ожидающее нажатия кнопки, а затем окно закрывается. Итак, опкод 0x41 показывает диалоговое окно, опкод 0xcb дожидается нажатия кнопки, а опкод 0x42 удаляет окно.
Дальнейшие эксперименты с опкодом 0x41 показывают, что его первый аргумент — это индекс строки диалога. Строки хранятся в двоичном файле игры, что неудобно для моддинга. Второй аргумент по-прежнему неизвестен, а третий и четвёртый управляют смещением по x и y относительно объекта, рядом с которым открывается диалоговое окно.
Хорошим примером того, почему такое экспериментальное реверсирование полезно, может стать опкод 0xcb, рассмотренный в IDA:
Хотя эта функция и небольшая по размеру, и назначение её понятно (она изменяет глобальные переменные), совсем не очевидно, какое влияние она оказывает на игровой движок. Изучение перекрёстных ссылок для каждой из глобальных переменных в IDA тоже не особо помогает. Каждая из этих глобальных переменных используется во множестве мест, и ни у одного из них назначение не становится сразу очевидным. Я мог бы потратить кучу времени в IDA, пытаясь выяснить, что изменение этих глобальных переменных говорит игровому движку подождать нажатия кнопки в следующем игровом цикле. Эмпирическое тестирование позволило выяснить это очень быстро. Недостаток заключается в том, что я всё ещё не знаю точного назначения каждой глобальной переменной в функции.
Одна из интересных особенностей, обнаруженных мной при экспериментах с компилятором, заключается в том, как объекты могут ссылаться друг на друга. Из первоначального анализа я уже знал, что поддержка ссылок в коде есть, но компилятор помог мне быстро разобраться в подробностях.
Поле 0x3c каждого объекта определяет текущий целевой объект. Некоторые опкоды, например collided_with_viking (0x1a), автоматически присваивают значение этому полю, но его также можно указать вручную. Викинги — это всегда объекты 0 (Балеог), 1 (Эрик) и 2 (Олаф). После назначения целевого объекта, им можно управлять через целевые поля. Каждый опкод имеет свои варианты изменения поля текущего объекта (целевого поля). Например, опкод 0x59 добавляет временный регистр к полю в текущем объекте, а опкод 0x5b добавляет временный регистр к полю в целевом объекте.
Другие объекты могут управлять полями в объектах викингов, чтобы контролировать их поведение. Например, поле 0x32 для викингов — это количество ожидаемого урона. Объект может наносить урон викингу, прибавляя значение к этому полю. Сами викинги частично реализованы программами в виртуальной машине. При следующем запуске программы викинга она проверяет поле ожидаемого урона и наносит соответствующий урон.
Интерес представляют также 0x12 и 0x14, которые являются скоростями для всех объектов по x и y. До написания компилятора я думал, что объекты перемещаются или добавлением/вычитанием из их полей смещения по x и y (0x1e и 0x20) или, возможно, использованием похожего на функцию опкода. Однако игра использует пару полей скорости. Некоторые объекты, например, викинги, автоматически изменяют свою скорость. Поэтому, например, если объект присваивает викингам скорость, поднимающую их вверх, то в последующие циклы игры викинг соответственно меняет собственную скорость, чтобы снова упасть вниз.
Похоже, что в объектах викингов не хватало полей для хранения всего, поэтому каждый из четырёх слотов инвентаря викингов является глобальной переменной. Объект может проверять, равна ли соответствующая глобальная переменная нулю, и давать викингу предмет, напрямую присваивая значение глобальной переменной слота инвентаря.
Для экспериментов с виртуальной машиной и демонстрации её гибкости я написал немного более сложную программу для башни с пушкой на первом уровне. Башня проверяет, какой из викингов её коснулся, и реагирует по-разному. Если башни касается Эрик, она даёт ему предметы. Если касается Олаф, он отталкивается в воздух. Когда касается Балеог, башня меняет направление. Вот как это выглядит в действии:
Такой уровень гибкости в игре, созданной в начале 90-х, довольно сильно впечатляет. Исходный код этой программы я добавил в папку examples компилятора.
По-прежнему остаётся довольно много опкодов, полей и глобальных переменных, назначение которых я не понимаю. Компилятору недостаёт некоторых функций, например, пока он поддерживает только операторы сравнения == и !=, и в нём отсутствует большинство побитовых операторов. Он немного громоздок в работе, потому что требует отдельной распаковки блока оригинальной программы из файла данных игры, патчинга и повторной упаковки файла данных.
Все инструменты являются общественным достоянием (public domain), их открытый исходный код выложен на github: https://github.com/RyanMallon/TheLostVikingsTools.
Я занимался реверс-инжинирингом двух ранних игр Blizzard под DOS, The Lost Vikings и Blackthorne. Выше я писал о виртуальной машине, которая используется в The Lost Vikings для реализации игровых объектов. Blizzard выложила The Lost Vikings и Blackthorne в свободный доступ на Battle.net. Стоит заметить, что Blizzard создавала свои ранние игры, в том числе The Lost Vikings, под именем Silicon and Synapse. Blackthorne стала первой игрой, выпущенной под брендом Blizzard.
В этом разделе я расскажу о том, как в двух играх реализованы форматы спрайтов и тайловый движок. У этих двух игр очень похожие движки, причём в Blackthorne после The Lost Vikings внесены некоторые улучшения. В дальнейшем я буду называть игровой движок обеих игр «движком Blizzard».
Игры хранят все свои данные в одном пакетном файле данных, который называется DATA.DAT. Пакетный файл — это архив, в котором содержатся блоки спрайтов, уровней, звуков и т.д. Большинство блоков пакетного файла сжато разновидностью алгоритма сжатия LZSS.
Я создал несколько простых утилит, которые можно использовать для просмотра спрайтов, уровней и т.д. из The Lost Vikings и Blackthorne. Эти утилиты можно скачать с GitHub (ссылка выше). В этот раздел я добавил примеры кода. Все скриншоты в разделе сделаны с помощью этих утилит.
В обеих играх используется популярный режим VGA Mode X. Mode X — это 256-цветный плоскостной графический режим с разрешением 320×240. «Плоскостной» означает, что вместо линейного расположения пикселей, как в режиме VGA Mode 13h с разрешением 320×200, они разделены на набор плоскостей. Плоскостная графика изначально была разработана для ускорения обработки графики. Она позволяет нескольким чипам памяти хранить отдельные плоскости и передавать их паралелльно. В этой статье на Shikadi.net есть хорошее объяснение работы плоскостной графики.
В режиме Mode X используется четыре плоскости. Первая плоскость хранит пиксели 0, 4, 8 и т.д. Вторая плоскость хранит пиксели 1, 5, 9 и т.д. Поэтому спрайт 8×2 хранится не линейно, как пиксели:
Плоскостной режим Mode X хранит их так:
В основном я выполнял обратную разработку форматов спрайтов, изучая данные в блоках пакетного файла, а не код рендеринга в IDA. Я обладаю очень рудиментарным пониманием программирования под DOS и VGA, а код рендеринга старых игр обычно содержит множество хитростей для оптимизации и умное применения ассемблера, которые трудно понять (мне).
Первый формат спрайтов, используемый в играх — это просто «сырые» закодированные плоскостные данные. «Сырые» спрайты могут имеют любую ширину и высоту, делящуюся на четыре. Отрисовка «сырых» спрайтов проста:
Дополнительно можно выбрать индекс цвета, используемого в качестве прозрачного. «Сырые» спрайты одинаковой ширины и высоты всегда имеют одинаковый объём данных, но они не особо эффективно используют место. Это особенно справедливо для игрового движка Blizzard, потому что спрайты используют всего шестнадцать цветов (это всегда значения от 0x0 до 0xf), поэтому четыре байта на пиксель тратятся впустую. Шестнадцать цветов на спрайт используются потому, что это позволяет применить хитрые трюки с палитрой, которые я объясню ниже.
Второй формат спрайтов позволяет использовать прозрачность, не жертвуя индексом цвета, но ценой является более сложный алгоритм отрисовки и немного больший размер данных. В разработанных мной утилитах я назвал этот формат «распакованным» (unpacked), но, возможно, лучше назвать его «с маской».
В этом формате спрайтов каждому набору из восьми пикселей предшествует байт маски, указывающий, какие пиксели нужно отрисовывать. Прозрачные пиксели по-прежнему кодируются значением 0x0, но пропускаются при отрисовке. Это позволяет использовать индекс цвета 0x0 в качестве дополнительного цвета.
Алгоритм отрисовки таких спрайтов выглядит следующим образом:
Различные собираемые предметы The Lost Vikings являются распакованными спрайтами/спрайтами с маской 16×16. Их можно просмотреть с помощью:
Последний формат спрайтов используется только в The Lost Vikings и оптимизирован для отрисовки спрайтов 32×32. Как и в распакованном формате, каждому набору пикселей предшествует байт маски, определяющий отрисовываемые пиксели. Однако упакованный формат не хранит прозрачные пиксели и упаковывает по два пикселя в каждый байт, потому что используется всего шестнадцать цветов. Если количество отрисовываемых пикселей нечётно, то последний полубайт равен нулю.
Этот формат использует место более эффективно по сравнению с двумя предыдущими, но имеет более сложный алгоритм отрисовки и переменную длину спрайтов. Блоки пакетного файла, содержащие спрайты упакованного формата, начинаются с заголовка из 16-битных значений, определяющих смещение каждого спрайта.
Алгоритм отрисовки упакованных спрайтов таков:
В процессе написания поста я обнаружил в заголовке второго уровня The Lost Vikings приведённый ниже спрайт. В нём используется упакованный формат 32×32, однако не помню, чтобы видел его в игре. Может быть кто-нибудь знает, возможно, это секретный или неиспользованный ресурс? Его можно просмотреть следующим образом:
На этот вопрос у меня нет точного ответа. Я ни в коей мере не являюсь специалистом в тонкостях программирования для оптимизации VGA. Возможно, разные форматы используются для увеличения скорости рендеринга спрайтов, которые должны иметь разную частоту обновления. Тайлы для карт всегда имеют «сырой» формат. «Сырой» формат также используется для некоторых спрайтов интерфейса. Спрайты в упакованном формате 32×32 — это викинги и многие враги. Распакованный формат используется для некоторых слабо анимированных врагов типа башни с пушкой и других объектов, например, переключателей и лифтов.
Похоже, что в Blackthorne совсем не используется упакованный формат 32×32. Возможно, потому, что многие спрайты Blackthorne крупнее 32×32. Большинство спрайтов с подробной анимацией использует «сырой» формат. В Blackthorne нет уровней со скроллингом (как в оригинальной Prince of Persia), что ускоряет рендеринг.
Я не разобрался ещё в одном вопросе: как движок Blizzard понимает, какой формат и размер спрайтов используется для отрисовки каждого объекта? В заголовках уровней есть частичная соответствующая информация, но её недостаточно для правильной отрисовки всех объектов. Подозреваю, что эти части информации о рендеринге управляются виртуальной машиной.
Как я упомянул выше, в Blackthorne используются спрайты большего размера, чем в The Lost Vikings. Несмотря на то, что можно написать алгоритм рендеринга «сырых» спрайтов произвольного размера, в движке Blizzard применяется другой подход. Крупные спрайты рендерятся соединением нескольких мелких спрайтов по неизменному шаблону. Например, в главном персонаже Blackthorne используются спрайты 32×48, состоящие из двух спрайтов 16×16 для головы и одного спрайта 32×32 для тела:
Стоит заметить, что используемый здесь фоновый цвет на самом деле является цветом с индексом 0 для спрайтов Blackthorne, который считается в игре прозрачным цветом. Весь набор спрайтов персонажа Blackthorne можно посмотреть так:
Возможно, такой подход был выбран потому, что разработчики Blizzard уже написали оптимизированные циклы рендеринга для спрайтов 16×16 и 32×32, и быстрее было рендерить крупные спрайты как набор мелких, а не как один большой.
И в The Lost Vikings, и в Blackthorne уровни создаются из тайловых карт с тайлами 16×16 (хотя мне кажется, что в обеих играх авторы хорошо постарались, чтобы такого ощущения не возникало). Используемые для тайлов спрайты на самом деле имеют размер 8×8. Каждый тайл содержит структуру, которую я называю «заготовкой». Она определяет, как создать набор спрайтов 8×8 из тайла 16×16. Каждую часть компонента можно горизонтально/вертикально перевернуть, что позволяет использовать компонентные тайлы в разных местах.
Например, в полном наборе тайлов (тайлсете) первого уровня The Lost Vikings есть несколько тайлов, таких как лестницы, которые имеют отзеркаленные версии, а также множество тайлов, которые несколько раз используют один угловой фрагмент, например, синие панели с заклёпками.
Просмотреть этот набор тайлов можно так:
Пакетный файл содержит для каждого набора тайлов блок, описывающий заготовки. Каждая заготовка имеет длину 8 байт, а каждый тайл закодирован как 16-битное значение. Для каждого 16-битного значения индекс спрайта кодируется как 10-битное значение, а остальные 6 бит используются как флаги. Флаги определяют вертикальное и/или горизонтальное отзеркаливание спрайта, а также то, где находится этот компонент тайла: спереди или на фоне. Кодирование бита передней/фоновой части в заготовке позволило движку Blizzard использовать общую тайловую карту для рендеринга обоих слоёв
Blackthone расширяет использование заготовок в движке двумя способами. Во-первых, три неиспользованных бита флагов применены в качестве цветовой основы. The Lost Vikings привязывает ко всем тайлам карты только 16 цветов. Благодаря добавлению битов цветовой основы Blackthorne может использовать для тайлов 128 цветов, однако каждый отдельный спрайт компонента всё равно ограничен 16 цветами.
Во-вторых, в Blackthorne добавили фоновый слой карты. Это позволяет игре иметь более подробные фоны и небо, просвечивающие сквозь пустоты в передних тайлах. Для простоты я буду называть вторичный фоновый слой слоем неба, а основную тайловую карту — передним и фоновым слоями. Слой неба не использует биты флагов передней части/фона, поэтому можно рассматривать его как единый слой.
На рисунке ниже показано, как собирается тайловая карта для первого уровня Blackthorne:
Слева направо, сверху вниз: небо/фон, передние тайлы, фоновые тайлы, все слои
Можно просмотреть тайловую карту следующим образом (заметьте, что уровень имеет номер 3, потому что уровни 1 и 2 — это начальная анимационная заставка и обучающий уровень):
Здесь можно заметить пару интересных моментов:
Blizzard сделала ещё один умный шаг: всё в игре — промежуточные экраны, анимированные заставки, меню — является уровнями. Без сомнения, это очень сэкономило время на разработку. Поскольку весь тяжкий труд по реализации кода для уровней игры с анимацией и подвижными объектами был уже сделан, то вполне логично снова использовать его для управления заставками и меню. Полагаю, в движке игры снова используется виртуальная машина для реализации анимации в уровнях анимационных заставок. Единственным заметным исключением стал начальный экран The Lost Vikings из начала этого раздела, который закодирован как большой «сырой» спрайт без сжатия.
Например, при запуске игры отображается несколько начальных экранов. Два из них закодированы как единый уровень (из двух комнат). В левой части изображения ниже показан набор тайлов для уровня, а справа — сам уровень. В игре сначала показывается силуэт персонажа (который светится, но подробнее об этом позже). Логотип Blackthorne отображается над главным меню.
Не знаю точно, зачем нужны эти две копии тайлов логотипа Blackthorne. Заметьте, что они имеют немного отличающуюся расцветку. Например, в верхнем наборе значок TM чёрный и находится внутри логотипа, а в нижнем — белый и находится снаружи. Возможно, этот набор тайлов ещё раз используется для другого экрана в конце игры?
Набор тайлов и уровень этого экрана можно посмотреть так:
Выше я говорил о том, что в каждом спрайте используется шестнадцать цветов, а значения всегда кодируются как 0x0 – 0xf. Это позволяет каждому уровню назначать свою собственную палитру для повторного использования спрайтов в разных уровнях.
В The Lost Vikings есть несколько миров, в том числе космический, доисторический и безумный конфетный миры. В каждом есть свои цветовая схема и враги. Управляемые игроком викинги используют только два набора палитр из 16 цветов (Олаф и Балеог оба используют одну зелёно-жёлтую цветовую схему, у Эрика — красно-синяя схема). В интерфейсе используется ещё один набор из 16 цветов, а ещё одна используется для предметов, таких как ключи и пополнение здоровья, которые есть во всех мирах. Благодаря этому остаётся приличная часть 256-цветной палитры, которая определяется уровнем. В большинстве уровней загружается базовая 128-цветовая палитна, а затем набор из восьми 16-цветных палитр.
Индивидуальные палитры уровней позволяют повторно использовать спрайты с другой цветовой схемой. Это был популярный трюк в эру 8-битного цвета и ограниченного дискового пространства. Как известно, в играх Mortal Kombat есть несколько палитр, меняющих внешний вид персонажей-ниндзя. На рисунке ниже показаны одни и те же спрайты динозавра с настройками палитры разных уровней:
Просмотреть две разные версии спрайта динозавра можно так:
Заметьте, что программе просмотра спрайтов передаются аргументы номера уровня (-l) и смещения базовой палитры offset (-b). Номер уровня используется для определения того, какие блоки палитры нужно загружать при анализе блока заголовка уровня. Индекс базовой палитры я определил экспериментально. Повторюсь, в этой части движка Blizzard я разобрался не полностью. Снова подозреваю, что индекс базовой палитры указывается командами в программе объектов виртуальной машины.
Ещё один популярный трюк из эры DOS — анимация графики сменой цветов палитры. Анимация объекта перерисовкой пикселей довольно затратна, особенно для больших частей, которые нужно часто обновлять, например, для фоновых водопадов в Blackthorne. Вместо изменения самих пикселей гораздо экономнее изменять цвета палитры. При этом мгновенно обновляются все пиксели соответствующего цвета. Эта техника в основном полезна для простых цикличных анимаций, таких как водопады и мигающие огни в космических уровнях The Lost Vikings. Как сказано ранее, анимации палитры используются в Blackthorne для создания эффекта свечения силуэта на начальном экране.
Движок Blizzard реализует анимации палитры в заголовке уровня. Каждый аниматор палитры имеет 8-битное значение скорости и два 8-битных значения индекса цвета. Если два индекса не равны, то анимация циклически переключается между двумя этими индексами. Такой формат хорошо подходит для анимации движущихся по шаблону объектов.
Если два индекса равны, то анимация палитры используется для одного цвета и заголовок уровня указывает список 16-битных значений для анимации. Каждое из 16-битных значений кодирует значение цвета в формате RGB-555 (5 бит на цвет, то есть один бит теряется впустую). Обычная палитра VGA и движок Blizzard способны отображать 6 бит на цвет. Анимации палитры теряют младший значимый байт сдвигом каждого значения цвета на один влево. Этот формат анимации палитры полезен для анимации чего-то типа пульсирующего света.
Можно нажать в программе просмотра уровней «A», чтобы посмотреть анимации палитр.
На этом пока всё:
Можете читать меня в Twitter: @ryiron.
Я обнаружил, что для реверс-инжиниринга игры The Lost Vikings компании Blizzard (тогда она называлась Silicon and Synapse), похоже, не предпринималось никаких серьёзных попыток. Игра была выпущена в 1993 году, на закате эры DOS, и очень нравилась мне в юности. The Lost Vikings — это головоломка-платформер, в которой игрок управляет тремя викингами, каждый из которых имеет собственные умения. Викингам нужно объединить свои силы для решения загадок и прохождения уровней с различной тематикой: космический корабль, доисторический мир, Древний Египет. На изображении ниже показан первый уровень игры (источник: Strategy Wiki):
Казалось, что эту игру разобрать будет довольно просто. Уровни основаны на тайловых картах и содержат простые загадки: кнопки, включающие и отключающие объекты, передвижные ящики и поднимающий предметы кран. И на самом деле, бóльшая часть проекта по обратной разработке была достаточно прямолинейной. У игры есть один пакетный файл данных, содержащий сжатые блоки файлов. Блоки кодируют различные ресурсы игры, такие как спрайты, карты, звуки и т.д. Я написал несколько утилит, которые можно использовать для просмотра ресурсов игры: The Lost Vikings Tools.
Виртуальная машина
Интересный аспект работы движка заключается в том, что объекты в игре используют шаблонную систему классов. Для каждого мира в файле данных есть блок, определяющий набор классов объектов. Например, на показанном выше первом уровне обе двери аварийного выхода имеют тип класса 0x4f. Реверс-инжиниринг кода классов объектов привёл к следующей функции:
Пропуская пока альтернативный путь к адресу 0x142a2, этот код использует si как индекс в структуре массива классов объектов (каждый шаблон класса состоит из 0x15 байт). Слово в смещении 0x3 — это структура, используемая в качестве адреса в сегменте ES. Сегмент ES содержит все данные блока шаблона класса объекта. Затем код переходит в цикл по адресу 0x142a6. Этот цикл получает следующий байт из сегмента ES и использует его как индекс таблицы функций. На каждом шаге цикла bx содержит адрес в сегменте ES, а si содержит текущий код операции (опкод).
Интересно заметить, что в цикле используется безусловный переход, и поэтому он никогда не завершается. По крайней мере, при нормальном выполнении программы. Похоже, что у каждого класса объекта есть какая-то связанная с ним программа, основанная на опкодах, которая интерпретируется этой функцией. Первоначально я просто исследовал некоторые из функций в таблице вызовов. Вот как выглядит первая в режиме графов IDA:
Анализ стека IDA здесь выполнить не удаётся, и на то есть причины. pop ax в качестве первой команды функции — это довольно странное поведение. Команда вызова x86 загружает указатель команды (ip) в стек, а команда ret извлекает его, чтобы вернуть вызывающей функции. Команда pop здесь фактически отбрасывает адрес возврата. Это значит, что следующая команда ret перейдёт назад на два кадра стека вместо одного. Этот опкод выполняет выход из бесконечного цикла интерпретатора.
Чтобы понять, как на самом деле реализован опкод, нам нужно переключиться в линейный режим IDA:
Я прокомментировал имена функций их соответствующими номерами опкодов, чтобы эта часть кода была понятней. Здесь довольно умно выполняется повторное использование кода. Легче всего начать с изучения опкода 0x03. Вспомним, что в обрабатывающем опкоды цикле есть данные блоков классов объектов, загруженных в сегмент ES, а bx используется в качестве указателя команды виртуальной машины. Таким образом, опкод 0x03 — это команда безусловного перехода. Она загружает слово по адресу текущего указателя команд, устанавливает на него указатель команд, а затем возвращается к циклу обработки опкодов.
Работая в обратном порядке, опкод 0x05 пропускает следующее слово-операнд и сохраняет следующий адрес в массив. Реверс других функций показывает, что word_28522 — это индекс текущего экземпляра объекта, то есть этот опкод хранит один адрес для каждого объекта на уровне. Затем он восстанавливает значение bx и проходит в коде до опкода 0x03 (переход). Поэтому этот опкод, похоже, является очень ограниченной командой вызова со всего одним уровнем стека.
Опкод 0x00 сохраняет текущий указатель функции в глобальный массив. Заметьте, что он отличается от опкода 0x05, который сохраняет адрес после операнда адреса вызова. Затем он переходит к обработчику опкодов вызовов. Однако, команда не будет выполнена из-за первой команды pop. Вместо этого вызывающий цикл выполнит выход. Адрес, сохраняемый этой командой, используется как альтернативный путь входа к циклу вызова функций, который я не стал рассматривать выше. Здесь опкод 0x00 используется как что-то вроде выхода из сопрограммы (coroutine). Он сохраняет текущее положение в программе и выходит из цикла обработки опкодов, позволяя игровому движку выполнить другие задачи: обновить графику, получить данные ввода пользователя и т.д., возвращаясь к тому, откуда выполнила выход программа виртуальной машины. Это позволяет программе виртуальной машины выполнять сложные задачи без простоя остальной части игрового движка.
Дизассемблинг опкодов
На этом этапе у меня уже было общее представление о том, как работает обработчик опкодов виртуальной машины. Изучив таблицу вызовов функций, я нашёл там примерно 215 реализованных опкодов, поэтому вместо их непосредственной обратной разработки по порядку я начал писать простой скрипт, чтобы декомпилировать программу для нужного класса объектов. Таким образом я мог сосредоточиться только на опкодах, вызываемых объектами на первом уровне.
В этот момент я в основном пытался определить, сколько операндов имеют опкоды, и в чём заключаются их основные задачи. Если обработчик опкодов был коротким, я обычно пытался полностью разобраться, что он делает. Если он был больше нескольких блоков кода, то я тогда просто старался выяснить, сколько операндов он имеет, и выполняет ли он условный переход или вызов. Я делал так, потому что иногда назначение опкода становится очевидным из окружающего его контекста в дизассемблированной программе, в котором зачастую проще разобраться, чем выполнить реверсирование кода.
Вот пример простого опкода:
Этот опкод получает операнд-слово и сохраняет его в глобальной переменной. Реверсирование других функций показывает, что эта глобальная переменная является временным хранилищем или регистром общего назначения. В виртуальной машине есть только один такой регистр, но он также имеет вот такой опкод:
Этот опкод сохраняет текущее значение регистра общего назначения по адресу в сегменте данных (DS), указанному операндом-словом. Программы в файле данных игры используют этот опкод для записи в определённые части игровых данных, таких как слоты инвентаря викингов. Несколько смещений DS также используются как дополнительные временные значения, когда их требуется больше одного. Например, смещения 0x0206 и 0x0208 часто используются как временные координаты x и y объекта.
Этот опкод и противоположный ему опкод 0x53, считывающий из DS в регистр общего назначения, интересны тем, что они могут считывать и записывать в DS любые игровые данные, а не только те, которые назначены создателями оригинальной игры. Это даёт нам интересные перспективы расширения оригинальной игры.
Более сложным является опкод 0x14:
На первый взгляд, его реверсирование не должно вызвать проблем. Он получает байтовый операнд и вызывает пару подфункций. Затем он получает ещё один байтовый операнд и снова вызывает те же подфункции. Но если взглянуть на первую подфункцию (sub_15473), то дело немного усложняется:
Анализ стека IDA выполнить снова не удаётся, и он показывает четыре выхода из этого блока, который я обрезал, потому что все они неверны. На самом деле происходит вот что: первый байтовый операнд передаётся в эту функцию в ax, который затем используется как индекс таблицы переходов. Хотя для ax выполняется операция AND с 7, на самом деле в таблице переходов есть всего четыре действительных значения. Взглянув на тип 0 в таблице переходов, мы увидим следующее:
Здесь загружается непосредственный операнд-слово. Этот фрагмент функции выполняет retn, который возвращается из обработчика опкода 0x14 верхнего уровня. Нетрудно заметить, почему у IDA возникают проблемы с правильным дизассемблированием этого кода.
Другие записи в таблице переходов различными способами загружают значения, а затем каждая из них снова делает retn. Тип 1 берёт байтовый операнд, используемый в качестве индекса поля объекта. Объект имеет поля для таких значений, как смещения x и y, флаги и т.д. Тип 2 получает операнд-слово и загружает значение из DS (как опкод 0x53 из примера выше). Тип 3 получает байтовый операнд и загружает поле целевого объекта для выполнения действий, например, для распознавания столкновений.
Вернёмся обратно к обработчику опкода 0x14 верхнего уровня. Здесь следующей вызывается sub_15470. Она всего на три байта впереди первой вызванной подфункции. И в этом снова есть есть умная оптимизация кода. Эта подфункция просто сдвигает ax вправо на 3, а затем переходит к коду, который мы только что реверсировали выше. Итак, первый байтовый операнд опкода 0x14 используется для кодирования того, как получаются два последующих аргумента. Реверсирование обработки второго байтового операнда показывает, что он работает таким же образом.
После получения всех его операндов (переменной длины) обработчик опкода 0x14 вызывает sub_13809. Я не буду вставлять сюда код, потому что функция довольно большая и вызывает множество других подфункций, каждая из которых тоже объёмна. Это один из тех случаев, когда я не заморачивался реверсированием действий функции, потому что позже они станут понятны из контекста.
Виртуальная машина CISC
Команды в виртуальной машине The Lost Vikings имеют переменную длину. В случае опкода 0x14 и других похожих опкодов определение длины требует декодирования некоторых операндов. Наличие команд переменной длины означает, что программу нужно дизассемблировать итеративно, как минимум определяя количество операндов для каждого нового опкода в программе. Если бы все опкоды имели фиксированную длину, то можно было бы пропускать неизвестные опкоды.
Существуют также команды, выполняющие стандартные операции, используемые многими программами. Например, многие программы выполняют суммирование или вычитание из текущего положения объекта на основании его направления. Это можно закодировать как несколько команд, но опкод 0x91 получает единственный операнд-слово как смещение в DS, а затем прибавляет или вычитает из него текущее значение временного регистра на основании текущего горизонтального направления объекта (флаг 0x0040). Следующий псевдокод демонстрирует работу опкода 0x90.
if (this.flags & 0x0040)
DS[operand] -= var;
else
DS[operand] += var;Благодаря этому на кодирование требуется гораздо меньше байтов, особенно потому, что эта операция выполняется несколькими программами. Во времена DOS, когда пространство на диске и вычислительная мощь были в дефиците, это имело большой смысл. Для современного реверс-разработчика это просто добавляет несколько новых опкодов, в которых нужно разобраться.
Дизассемблер
Я написал простой скрипт на Python, который может дизассемблировать программы виртуальной машины в то, что смутно напоминает C. Он линейно декодирует команды программы, сохраняя адреса переходов и вызовов. Когда он натыкается на функцию, останавливающую или перенаправляющую выполнение кода, например, возврат или безусловный переход, он останавливается и проверяет другие непосещённые адреса в программе.
В программах виртуальной машины использовали хитрости оптимизации, похожие на применённые в двоичном коде игры. Например, некоторые пути выхода из подпроцедур в программах виртуальной машины используются повторно с помощью перехода к ним из других подпроцедур. Дизассемблер справляется с этим, декодируя команды дважды, поэтому две подпроцедуры могут иметь код с одинаковыми адресами.
Дизассемблер может обрезать операции доступа к временному регистру, чтобы сделать конечный код более читаемым. Например, в программах виртуальной машины часто используются такие последовательности:
var = 0x1000;
obj->field_10 = var;Дизассемблер реорганизует их следующим образом:
obj->field_10 = 0x1000;Дизассемблер не пытается перестроить блоки кода в такие конструкции, как if или while, поэтому получающиеся программы выглядят как спагетти-код. Некоторые большие программы сами по себе можно сделать полноценными проектами для обратной разработки.
Полная программа
Я начал с программы для башни с пушкой в верхней левой комнате первого уровня (класс объекта 0x04). Мне показалось, что это должна быть довольно простая программа. Башня с пушкой стреляет снарядами с определённым интервалом, и викинги не могут её уничтожить. Ниже показана программа, полученная после обработки моим дизассемблером. Над каждым опкодом есть комментарий, показывающий в квадратных скобках адрес, в кавычках — опкод, после чего идут операнды.
Программа башни выглядит вот так:
main_374d:
{
// [374d] (19) 37bc
this.field_21 = 0x37bc;
this.field_22 = 0x0001;
// [3750] (97) 00 01
if (0x0001 & (1 << 0))
var = 0x0001;
// [3753] (00)
this.save_state();
// [3754] (9c) 18 08
if (!(var))
this.db_flags &= ~(1 << 12);
label_3757:
// [3757] (2f)
vm_func_2f();
// [3758] (00)
this.save_state();
// [3759] (01)
nop();
// [375a] (51) 0000
// [375d] (8c) 30 3798
if (this.field_30 != 0x0000)
call sub_3798;
// [3761] (52) 1c
// [3763] (77) 0000 3757
if (this.update_time != 0x0000)
jump label_3757;
// [3768] (19) 37c8
this.field_21 = 0x37c8;
this.field_22 = 0x0001;
// [376b] (52) 1e
// [376d] (57) 0206
g_tmp_a = this.xoff;
// [3770] (51) 0004
// [3773] (91) 0206
if (this.flags & 0x0040)
g_tmp_a -= 0x0004;
else
g_tmp_a += 0x0004;
// [3776] (52) 20
// [3778] (57) 0208
g_tmp_b = this.yoff;
// [377b] (51) fff8
// [377e] (5a) 0208
g_tmp_b += 0xfff8;
// [3781] (51) 001e
// [3784] (56) 1c
this.update_time = 0x001e;
// [3786] (02) 3030
vm_func_02(0x3030);
// [3789] (14) 12 0206 0208 00 0000 0000 05
new.x = g_tmp_a;
new.y = g_tmp_b;
new.unknown_a = 0x0000;
new.unknown_b = 0x0000;
new.unknown_c &= 0x801;
new.type = 0x05;
spawn_obj(new);
// [3795] (03) 3757
jump label_3757;
}
sub_3798:
{
// [3798] (51) 000a
// [379b] (73) 30 37a5
if (this.field_30 == 0x000a)
jump label_37a5;
// [379f] (51) 0000
// [37a2] (56) 30
this.field_30 = 0x0000;
// [37a4] (06)
return;
label_37a5:
// [37a5] (52) 32
// [37a7] (69) 0a 37ba
if (this.argument < this.field_32)
jump label_37ba;
// [37ab] (52) 32
// [37ad] (5c) 0a
this.argument -= this.field_32;
// [37af] (51) 0000
// [37b2] (56) 30
this.field_30 = 0x0000;
// [37b4] (51) 0000
// [37b7] (56) 32
this.field_32 = 0x0000;
// [37b9] (06)
return;
label_37ba:
// [37ba] (0e)
vm_func_0e();
// [37bb] (10)
this.update();
}Здесь можно заметить следующее:
- Функция this.save_state() — это опкод 0x00. Она используется как результат, позволяющий программе сохранить место, в котором она находилась, и вернуться к коду игрового движка.
- Мой дизассемблер присваивает некоторым полям объекта придуманные мной имена. В этой программе видны имена xoff, yoff, flags и update_time.
- Также даны названия известным смещениям DS. g_tmp_a и g_tmp_b являются смещениями DS 0x0206 и 0x0208.
- Здесь используется опкод 0x14. Я дал ему имя spawn_obj(), потому что из контекста его применения понятно, что он используется для создания нового объекта пули при каждом выстреле башни.
- Опкод 0x19 присваивает значения полям 0x21 и 0x22 объекта. Примечательно, что полю 0x21 присваивается значение, напоминающее адрес программы. Читая код и экспериментируя, я выяснил, что этот адрес на самом деле является смещением для команд в маленькой вторичной виртуальной машине, которая управляет отображением графики объектов. Пока я не реверсировал этот код.
Рефакторинг программы помогает понять, что в ней происходит:
main_374d:
{
/* Инициализация башни */
this.set_graphics_prog(0x37bc);
if (0x0001 & (1 << 0))
var = 0x0001;
this.save_state();
if (!(var))
this.db_flags &= ~(1 << 12);
label_3757:
/*
* Основной цикл башни. Возвращает результат в основной
* движок игры при каждой итерации.
*/
while (1) {
vm_func_2f();
this.save_state();
/*
* Предназначение этой части неизвестно. Полю this.argument
* можно присвоить экземпляр объекта в заголовке
* уровня. Возможно, она используется для небольшого
* изменения поведения некоторых башен.
*/
if (this.field_30 != 0x0000) {
if (this.field_30 != 0x000a) {
this.field_30 = 0x0000;
} else {
if (this.argument < this.field_32) {
vm_func_0e();
this.update();
} else {
this.argument -= this.field_32;
this.field_30 = 0x0000;
this.field_32 = 0x0000;
}
}
}
/* Если время обновления update_time достигает нуля, то выпускается пуля */
if (this.update_time == 0x0000) {
this.set_graphics_prog(0x37c8);
/* Сброс времени обновления */
this.update_time = 0x001e;
vm_func_02(0x3030);
/*
* Создание объекта пули в четырёх пикселях от передней части
* башни и в восьми пикселях над центральной линией.
*/
if (this.flags & OBJ_FLAG_FLIP_HORIZONTAL)
new.x -= 4;
else
new.x += 4;
new->y = this.yoff - 8;
new->unknown_a = 0x0000;
new->unknown_b = 0x0000;
new->unknown_c &= 0x801;
new->type_d = 0x05;
spawn_obj(new);
}
}
}Стоит заметить, что в программе всё ещё есть части и опкоды, предназначение которых я не определил, но поведение башни достаточно понятно. Поле update_time объекта используется для кодирования скорости стрельбы башни. Программа сама не занимается уменьшением этого значения (по крайней мере, очевидным образом). Возможно, эту задачу выполняет один из неизвестных опкодов или какая-нибудь часть основного игрового движка.
Взлом игры
Разумеется, возможность изучить исходные программы, используемые игрой, интересна сама по себе. Но самое любопытное в способе реализации виртуальной машиной поведения объекта заключается в том, что мы можем изменять его или создавать новые программы. Это было бы гораздо проще, если написать компилятор (о нём я расскажу ниже), но пока мы можем лишь менять значения в hex-редакторе вручную.
Повторюсь — я выбрал для модификации программу башни с пушкой, потому что она довольно проста. Сначала я решил изменить тип объекта, которым стреляет башня. Успех оказался переменным. Попытки реализовать стрельбу одними объектами, например, зелёным инопланетянином, приводили к «вываливанию» или зависанию игры. Выбор других объектов приводил к тому, что башня ничем не стреляла. Мне удалось заставить её стрелять огненными стрелами (в обычной игре это бонус, который может использовать один из викингов). Также довольно просто увеличить темп стрельбы пушки уменьшением значения поля update_time.
Вторая сделанная мной модификация стала немного более амбициозной: я заставил башню вместо стрельбы двигаться. Опкод (0x14) для создания пули довольно длинный:
14 12 0206 0208 00 0000 0000 05Виртуальная машина предоставляет возможность использования однобайтовой команды nop (0x01) (что довольно благородно с её стороны), которую можно использовать для замены этой команды. Команды выше уже установили DS[0x0206] в текущее положение по оси x башни плюс-минус 4, в зависимости от её направления. Поэтому мне просто нужно добавить команды для присвоения этого значения текущему положению x. Для этого требуются всего две команды:
53 0206 // var = DS[0x0206];
56 1e // this.x = var;Благодаря этому изменению башня может двигаться, но её ничего не останавливает. Я пробовал реализовать распознавание столкновений и поворот обратно, но правильной работы добиться не удалось. Требуется более глубокая обратная разработка.
Я собрал небольшое видео моих модификаций:
Также я выложил в открытый доступ свой дизассемблер:
https://github.com/RyanMallon/TheLostVikingsTools/blob/master/dissassembler/lv_vm_disasm.py
Рекомпиляция игры
В предыдущем разделе мы говорили о реверс-инжиниринге виртуальной машины, используемой для реализации объектов в Lost Vikings.
Раньше я тестировал некоторые из опкодов эмпирически, ручным патчингом исходных блоков данных в шестнадцатеричном редакторе. Такой подход работал, но был очень монотонным и не очень хорошо масштабировался для экспериментов с большими программами или с программами, содержащими циклы и переходы. Выше я предположил, что создание простого языка и компилятора будет полезно для дальнейшей обратной разработки виртуальной машины. Поэтому я его написал.
Построение компилятора
Для помощи в обратной разработке виртуальной машины и удобства создания новых программ я решил написать компилятор. Чтобы не усложнять, я выбрал однопроходный метод рекурсивного спуска.
Дизайн компилятора в основном позаимстован у компиляторов типа PL/0, которые часто изучают на университетских курсах о компиляторах (см. PL/0). Не буду вдаваться в подробности написания базового компилятора, потому что в Интернете достаточно информации об этом. В сущности, компилятор получает исходную программу, выполняет лексический анализ для создания потока токенов, а затем производит синтаксический анализ программы, генерируя код.
Lost Vikings C
Я создал очень простой C-подобный язык для реализации на нём программ объектов. Одно из преимуществ использования C-подобного языка заключается в том, что можно использовать существующий препроцессор C для поддержки определения констант и макросов. Язык не позволяет определять переменные, программист ограничен полями объектов и глобальными переменными, определяемыми виртуальной машиной. Встроенные функции обеспечивают поддержку генерации опкодов для операций получения результатов и создания объектов. Язык имеет незначительные отличия от C, просто чтобы сохранить простоту лексического и синтаксического анализаторов.
Снова возьмём для примера объект башни с пушкой из первого уровня, который мы модифицировали выше. Реализовать стреляющую стрелами башню на Lost Vikings C можно следующим образом:
#include "vikings.h"
#define timer field_30
#define DELAY_TIME 40
function main
{
call set_gfx_prog(0x37bc);
this.timer = 0;
while (this.timer != 0xffff) {
call update_obj();
call yield();
if (this.timer != 0) {
this.timer = this.timer - 1;
} else {
// Вычисление смещения снаряда на основании
// направления башни.
if (this.flags & OBJ_FLAG_FLIP_HORIZ) {
g_tmp_a = this.x - 12;
} else {
g_tmp_a = this.x + 12;
}
g_tmp_b = this.y - 12;
// Обновление анимации башни
call set_gfx_prog(0x37c8);
// Создание стрелы
call spawn_obj(g_tmp_a, g_tmp_b, 0, 0, 7);
// Задержка перед следующим выстрелом
this.timer = DELAY_TIME;
}
}
}Каждому объекту нужен основной цикл, который никогда не должен завершаться. Основной цикл должен вызывать функцию yield(), чтобы позволить выполнять выход циклу обработки виртуальной машины. В противном случае движок игры «зависнет». Вызов update_obj() делает то, что следует из его названия.
Использование многих полей объектов относятся к конкретному объекту. В нашем случае я использовал поле field_30 в качестве таймера для управления скоростью стрельбы башни. Когда таймер достигает нуля, башня стреляет, а затем переустанавливает таймер.
Единственное, что осталось — сгенерировать код для этой программы.
Генерирование кода
Виртуальная машина The Lost Vikings не является идеальной средой для простого компилятора. Компиляторы типа PL/0 обычно генерируют код для абстрактной стековой машины, поэтому простое выражение типа:
this.x = this.y + 1;сгенерирует вот такой код:
push this.y ; запись this.y в стек
push 1 ; запись 1 в стек
add ; извлечение двух верхних значений, суммирование и запись результата
pop this.x ; извлечение результата в this.xОднако у виртуальной машины The Lost Vikings нет стека. У неё есть простой временный регистр, поля объектов и глобальные переменные. Показанная выше программа транслируется в виртуальную машину Lost Vikings следующим образом:
52 20 ; var = this.y
56 1e ; this.x = var
51 0001 ; var = 0x0001
59 1e ; this.y += varДля неё гораздо сложнее генерировать код при компилировании из языка общего назначения. Возможно, потребуется генерировать в первом проходе промежуточное представление, а затем во втором проходе изменять порядок команд и т.д. для генерирования конечного кода.
Абстрактная машина
Я пришёл к следующему решению: создание абстрактной стековой машины, для которой можно удобно компилировать поверх виртуальной машины Lost Vikings. Это возможно сделать благодаря опкодам для загрузки и хранения глобальных переменных. Эти опкоды получают в качестве своих операндов смещения в сегменте данных (DS) игры. Это позволяет использовать опкоды для загрузки и хранения любого произвольного адреса в DS.
Компилятор генерирует код, помещая фальшивый стек в верхнюю часть (0xf004) сегмента данных. Два адреса в основании фальшивого стека зарезервированы под специальный регистр: 0xf000 — это нулевой регистр, а 0xf002 — флаговый регистр, используемый для сравнения. Приведённое выше выражение теперь можно скомпилировать так:
52 20 ; var = this.x
57 f004 ; ds[f004] = var
51 0001 ; var = 0x0001
57 f006 ; ds[f006] = var
53 f006 ; var = ds[f006]
5a f004 ; ds[f004] += var
53 f004 ; var = ds[f004]
56 1e ; this.y = varНесмотря на не очень высокую производительность, этот код очень просто генерировать. Моя цель — создание компилятора для тестирования небольших программ, чтобы определить, что делают опкоды или их сочетания. Пока меня не очень волнует эффективность, с точки зрения и времени, и размера кода.
Вторая проблема в создании языка для оригинальной виртуальной машины заключается в том, что многие опкоды выполняют условный вызов функций. Например, опкод 0x1a проверяет, столкнулся ли текущий объект с викингом, и если это так, то он выполняет команду вызова. Желательнее, чтобы программист мог сам решать, нужно ли использовать вызов или переход (например, конструкцию с if).
Я реализовал это, сгенерировав код для стандартной вспомогательной функции, устанавливающей флаг и выполняющей возврат. При генерировании кода для опкода, выполняющего условный вызов, сначала сбрасывается флаговый регистр. Если опкод выполняет вызов, то флаговый регистр устанавливается. Затем можно проверять флаг для выполнения вызова перехода. Например, следующий код:
if (call collided_with_viking(0x01)) {
this.x = 1;
}генерирует вот такой код:
[c009] 51 0000 ; var = 0x0000
[c00c] 57 f002 ; ds[f002] = var, сброс флагового регистра
[c00f] 1a 01 c0a5 ; if (collided_with_viking(0x01)) call c0a5
[c013] 53 f002 ; var = ds[f002]
[c016] 74 f000 c026 ; if (var == ds[f000]) goto c026
[c01b] 51 0001 ; var = 0x0001
[c01e] 57 f004 ; ds[f004] = var
[c021] 53 f004 ; var = ds[f004]
[c024] 56 1e ; this.field_x = var
[c026] ... ; следующая команда после блока if
; Установка флаговой вспомогательной функции
[c0a5] 51 0001 ; var = 0x0001
[c0a8] 57 f002 ; ds[f002] = var, установка флагового регистра
[c0ab] 06 ; returnНулевой регистр используется здесь для сравнения его со значением флага. В начале каждой программы компилятор генерирует команды для сброса нулевого регистра.
Патчинг программ
Программы виртуальной машины для каждого мира игры упакованы в отдельный блок в файле данных. Компилятор использует простой подход: он добавляет сгенерированнй код к концу блока, а затем модифицирует заголовок программы объекта, чтобы тот указывал на патч в программе.
Всё это в теории работает, но на деле есть одна небольшая проблема. Игра хранит программы виртуальной машины в дополнительном сегменте (ES) в месте, указываемом с помощью API выделения памяти DOS. Функция выделения памяти выглядит так:
Вызов выделения памяти для виртуальной машины выглядит так:
То есть для программ выделяется 0xc000 байт (48 КБ). Проблема в том, что блок для программ мира космического корабля уже занимает 48972 байт, то есть в его конце остаётся всего 180 байт для патча в новой программе. Не так уж много, когда работаешь с компилятором, генерирующим очень избыточный код.
Я обнаружил эту проблему, когда пытался скомпилировать большую программу. Игра начала вести себя хаотично, она или «зависала», или случайным образом пропадала башня с пушкой. Такие ошибки довольно сложно отследить, потому что это может быть багом в моём компиляторе или сгенерированном коде, проблемой недопонимания принципа работы какого-то опкода, или багом/ограничением оригинальной игры.
Быстрым решением является патчинг двоичного кода игры для расширения размера памяти, выделяемого под программу. Увеличение выделенного размера до 0xd000 байт (52 КБ) не вызывает проблем и даёт достаточно места для экспериментов с простыми программами. Я добавил команды для этого в мой компилятор.
Эмпирическое реверсирование
Целью создания компилятора было упрощение обратной разработки виртуальной машины. Для тестирования нового опкода необходимо добавить запись в словарь функций в классе генератора кода и создать функцию генерирования команд для опкода. Например, одним из первых экспериментов была работа с 0x41, который используется в нескольких дизассемблированных программ, таких как объекты кнопок/значков с вопросительным знаком.
Его запись словаря в компиляторе изначально выглядела так:
"vm_func_41" : (False, 4, emit_builtin_vm_func_41),Кортеж указывает, будет ли функция возвращать значение, количество передаваемых ей аргументов и функцию генератора кода. Функции помечаются как возвращающие значение, если опкод выполняет условный вызов или переход.
После изучения опкода в IDA я знал, что опкод 0x41 выполняется безусловно и получает четыре аргумента. Его аргументы используют кодирование типа переменной, который я описывал в начале статьи. Он генерирует следующую функцию:
def emit_builtin_vm_func_41(self, reg_list):
operands = self.pack_args(reg_list, 4)
self.emit(0x41, *operands)Вспомогательная функция pack_args обеспечивает упаковку аргументов типа переменной.
Теперь её можно вызвать в короткой тестовой программе. Для тестирования я использую функцию collided_with_viking (опкод 0x1a), поэтому тестируемый опкод запускается только при касании викингом башни. Заметьте, что функция collided_with_viking получает единственный байтовый операнд, назначение которого я не знаю, но значение 0x01 вполне для него подходит. Также я использую как одноразовый триггер поле field_32 объекта, чтобы тестируемый мной опкод срабатывал только при первом касании викингом объекта.
Моя тестовая программа выглядит так:
function main
{
call set_gfx_prog(0x37bc);
this.field_32 = 0;
while (this.field_32 != 0xffff) {
call update_obj();
call yield();
if (call collided_with_viking(0x01)) {
if (this.field_32 == 0) {
call vm_func_41(1, 1, 1, 1);
this.field_32 = 1;
}
}
}
}В результате в игре возникает вот такой графический «глитч»:
Похоже, что опкод используется для отображения диалогового окна, но непонятно, почему возникает эта графическая ошибка. Если посмотреть на некоторые дизассемблированные программы из оригинальной игры, то видно, что за опкодом 0x41 обычно следуют неизвестные опкоды 0xcb и 0x42, ни один из которых не получает мои аргументы. При добавлении встроенных программ для этих опкодов в компиляторе и повторном запуске игры отображается диалоговое окно, ожидающее нажатия кнопки, а затем окно закрывается. Итак, опкод 0x41 показывает диалоговое окно, опкод 0xcb дожидается нажатия кнопки, а опкод 0x42 удаляет окно.
Дальнейшие эксперименты с опкодом 0x41 показывают, что его первый аргумент — это индекс строки диалога. Строки хранятся в двоичном файле игры, что неудобно для моддинга. Второй аргумент по-прежнему неизвестен, а третий и четвёртый управляют смещением по x и y относительно объекта, рядом с которым открывается диалоговое окно.
Хорошим примером того, почему такое экспериментальное реверсирование полезно, может стать опкод 0xcb, рассмотренный в IDA:
Хотя эта функция и небольшая по размеру, и назначение её понятно (она изменяет глобальные переменные), совсем не очевидно, какое влияние она оказывает на игровой движок. Изучение перекрёстных ссылок для каждой из глобальных переменных в IDA тоже не особо помогает. Каждая из этих глобальных переменных используется во множестве мест, и ни у одного из них назначение не становится сразу очевидным. Я мог бы потратить кучу времени в IDA, пытаясь выяснить, что изменение этих глобальных переменных говорит игровому движку подождать нажатия кнопки в следующем игровом цикле. Эмпирическое тестирование позволило выяснить это очень быстро. Недостаток заключается в том, что я всё ещё не знаю точного назначения каждой глобальной переменной в функции.
Интересные поля
Одна из интересных особенностей, обнаруженных мной при экспериментах с компилятором, заключается в том, как объекты могут ссылаться друг на друга. Из первоначального анализа я уже знал, что поддержка ссылок в коде есть, но компилятор помог мне быстро разобраться в подробностях.
Поле 0x3c каждого объекта определяет текущий целевой объект. Некоторые опкоды, например collided_with_viking (0x1a), автоматически присваивают значение этому полю, но его также можно указать вручную. Викинги — это всегда объекты 0 (Балеог), 1 (Эрик) и 2 (Олаф). После назначения целевого объекта, им можно управлять через целевые поля. Каждый опкод имеет свои варианты изменения поля текущего объекта (целевого поля). Например, опкод 0x59 добавляет временный регистр к полю в текущем объекте, а опкод 0x5b добавляет временный регистр к полю в целевом объекте.
Другие объекты могут управлять полями в объектах викингов, чтобы контролировать их поведение. Например, поле 0x32 для викингов — это количество ожидаемого урона. Объект может наносить урон викингу, прибавляя значение к этому полю. Сами викинги частично реализованы программами в виртуальной машине. При следующем запуске программы викинга она проверяет поле ожидаемого урона и наносит соответствующий урон.
Интерес представляют также 0x12 и 0x14, которые являются скоростями для всех объектов по x и y. До написания компилятора я думал, что объекты перемещаются или добавлением/вычитанием из их полей смещения по x и y (0x1e и 0x20) или, возможно, использованием похожего на функцию опкода. Однако игра использует пару полей скорости. Некоторые объекты, например, викинги, автоматически изменяют свою скорость. Поэтому, например, если объект присваивает викингам скорость, поднимающую их вверх, то в последующие циклы игры викинг соответственно меняет собственную скорость, чтобы снова упасть вниз.
Похоже, что в объектах викингов не хватало полей для хранения всего, поэтому каждый из четырёх слотов инвентаря викингов является глобальной переменной. Объект может проверять, равна ли соответствующая глобальная переменная нулю, и давать викингу предмет, напрямую присваивая значение глобальной переменной слота инвентаря.
Расширенный взлом игры
Для экспериментов с виртуальной машиной и демонстрации её гибкости я написал немного более сложную программу для башни с пушкой на первом уровне. Башня проверяет, какой из викингов её коснулся, и реагирует по-разному. Если башни касается Эрик, она даёт ему предметы. Если касается Олаф, он отталкивается в воздух. Когда касается Балеог, башня меняет направление. Вот как это выглядит в действии:
Такой уровень гибкости в игре, созданной в начале 90-х, довольно сильно впечатляет. Исходный код этой программы я добавил в папку examples компилятора.
Работа на будущее
По-прежнему остаётся довольно много опкодов, полей и глобальных переменных, назначение которых я не понимаю. Компилятору недостаёт некоторых функций, например, пока он поддерживает только операторы сравнения == и !=, и в нём отсутствует большинство побитовых операторов. Он немного громоздок в работе, потому что требует отдельной распаковки блока оригинальной программы из файла данных игры, патчинга и повторной упаковки файла данных.
Все инструменты являются общественным достоянием (public domain), их открытый исходный код выложен на github: https://github.com/RyanMallon/TheLostVikingsTools.
Олдскульная Blizzard: спрайты, карты и палитры
Я занимался реверс-инжинирингом двух ранних игр Blizzard под DOS, The Lost Vikings и Blackthorne. Выше я писал о виртуальной машине, которая используется в The Lost Vikings для реализации игровых объектов. Blizzard выложила The Lost Vikings и Blackthorne в свободный доступ на Battle.net. Стоит заметить, что Blizzard создавала свои ранние игры, в том числе The Lost Vikings, под именем Silicon and Synapse. Blackthorne стала первой игрой, выпущенной под брендом Blizzard.
В этом разделе я расскажу о том, как в двух играх реализованы форматы спрайтов и тайловый движок. У этих двух игр очень похожие движки, причём в Blackthorne после The Lost Vikings внесены некоторые улучшения. В дальнейшем я буду называть игровой движок обеих игр «движком Blizzard».
Игры хранят все свои данные в одном пакетном файле данных, который называется DATA.DAT. Пакетный файл — это архив, в котором содержатся блоки спрайтов, уровней, звуков и т.д. Большинство блоков пакетного файла сжато разновидностью алгоритма сжатия LZSS.
Я создал несколько простых утилит, которые можно использовать для просмотра спрайтов, уровней и т.д. из The Lost Vikings и Blackthorne. Эти утилиты можно скачать с GitHub (ссылка выше). В этот раздел я добавил примеры кода. Все скриншоты в разделе сделаны с помощью этих утилит.
./sprite_view DATA.DAT -fraw -s -u -w344 -p 0x17b 0x17c
./level_view --blackthorne DATA.DAT 1 -h0x6eГрафический режим
В обеих играх используется популярный режим VGA Mode X. Mode X — это 256-цветный плоскостной графический режим с разрешением 320×240. «Плоскостной» означает, что вместо линейного расположения пикселей, как в режиме VGA Mode 13h с разрешением 320×200, они разделены на набор плоскостей. Плоскостная графика изначально была разработана для ускорения обработки графики. Она позволяет нескольким чипам памяти хранить отдельные плоскости и передавать их паралелльно. В этой статье на Shikadi.net есть хорошее объяснение работы плоскостной графики.
В режиме Mode X используется четыре плоскости. Первая плоскость хранит пиксели 0, 4, 8 и т.д. Вторая плоскость хранит пиксели 1, 5, 9 и т.д. Поэтому спрайт 8×2 хранится не линейно, как пиксели:
0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15Плоскостной режим Mode X хранит их так:
0, 4, 8, 12, 1, 5, 9, 13, 2, 6, 10, 14, 3, 7, 11, 15В основном я выполнял обратную разработку форматов спрайтов, изучая данные в блоках пакетного файла, а не код рендеринга в IDA. Я обладаю очень рудиментарным пониманием программирования под DOS и VGA, а код рендеринга старых игр обычно содержит множество хитростей для оптимизации и умное применения ассемблера, которые трудно понять (мне).
Формат «сырых» спрайтов
Первый формат спрайтов, используемый в играх — это просто «сырые» закодированные плоскостные данные. «Сырые» спрайты могут имеют любую ширину и высоту, делящуюся на четыре. Отрисовка «сырых» спрайтов проста:
for (plane = 0; plane < 4; plane++) {
for (i = 0; i < (sprite_width * sprite_height) / 4; i++) {
offset = (i * 4) + plane;
y = offset / sprite_width;
x = offset % sprite_width;
pixel = *sprite++;
dst[((dst_y + y) * dst_width) + (dst_x + x)] = pixel;
}
}Дополнительно можно выбрать индекс цвета, используемого в качестве прозрачного. «Сырые» спрайты одинаковой ширины и высоты всегда имеют одинаковый объём данных, но они не особо эффективно используют место. Это особенно справедливо для игрового движка Blizzard, потому что спрайты используют всего шестнадцать цветов (это всегда значения от 0x0 до 0xf), поэтому четыре байта на пиксель тратятся впустую. Шестнадцать цветов на спрайт используются потому, что это позволяет применить хитрые трюки с палитрой, которые я объясню ниже.
Формат распакованных спрайтов/спрайтов с маской
Второй формат спрайтов позволяет использовать прозрачность, не жертвуя индексом цвета, но ценой является более сложный алгоритм отрисовки и немного больший размер данных. В разработанных мной утилитах я назвал этот формат «распакованным» (unpacked), но, возможно, лучше назвать его «с маской».
В этом формате спрайтов каждому набору из восьми пикселей предшествует байт маски, указывающий, какие пиксели нужно отрисовывать. Прозрачные пиксели по-прежнему кодируются значением 0x0, но пропускаются при отрисовке. Это позволяет использовать индекс цвета 0x0 в качестве дополнительного цвета.
Алгоритм отрисовки таких спрайтов выглядит следующим образом:
for (plane = 0; plane < 4; plane++) {
x = plane;
y = 0;
for (i = 0; i < (sprite_width * sprite_height) / 4 / 8; i++) {
mask = *sprite++;
for (bit = 7; bit >= 0; bit--) {
pixel = *sprite++;
if (mask & (1 << bit))
dst[((dst_y + y) * dst_width) + (dst_x + x)] = pixel;
x += 4;
if (x >= sprite_width) {
y++;
x = plane;
}
}
}
}Различные собираемые предметы The Lost Vikings являются распакованными спрайтами/спрайтами с маской 16×16. Их можно просмотреть с помощью:
./sprite_view DATA.DAT -l2 -funpacked -w16 -h16 0x12f
Упакованные спрайты 32×32
Последний формат спрайтов используется только в The Lost Vikings и оптимизирован для отрисовки спрайтов 32×32. Как и в распакованном формате, каждому набору пикселей предшествует байт маски, определяющий отрисовываемые пиксели. Однако упакованный формат не хранит прозрачные пиксели и упаковывает по два пикселя в каждый байт, потому что используется всего шестнадцать цветов. Если количество отрисовываемых пикселей нечётно, то последний полубайт равен нулю.
Этот формат использует место более эффективно по сравнению с двумя предыдущими, но имеет более сложный алгоритм отрисовки и переменную длину спрайтов. Блоки пакетного файла, содержащие спрайты упакованного формата, начинаются с заголовка из 16-битных значений, определяющих смещение каждого спрайта.
Алгоритм отрисовки упакованных спрайтов таков:
for (plane = 0; plane < 4; plane++) {
for (y = 0; y < 32; y++) {
num_pixels = 0;
mask = *sprite++;
for (bit = 7; bit >= 0; bit--) {
if (mask & (1 << bit)) {
pixel = *sprite;
if (num_pixels & 1)
sprite++;
else
pixel >>= 4;
pixel &= 0xf;
x = ((7 - bit) * 4) + plane;
dst[((dst_y + y) * dst_width) + (dst_x + x)] = pixel;
num_pixels++;
}
}
if (num_pixels & 1)
sprite++;
}
}В процессе написания поста я обнаружил в заголовке второго уровня The Lost Vikings приведённый ниже спрайт. В нём используется упакованный формат 32×32, однако не помню, чтобы видел его в игре. Может быть кто-нибудь знает, возможно, это секретный или неиспользованный ресурс? Его можно просмотреть следующим образом:
./sprite_view DATA.DAT -l2 -fpacked32 0xec -b0x10
Зачем использовать несколько форматов спрайтов?
На этот вопрос у меня нет точного ответа. Я ни в коей мере не являюсь специалистом в тонкостях программирования для оптимизации VGA. Возможно, разные форматы используются для увеличения скорости рендеринга спрайтов, которые должны иметь разную частоту обновления. Тайлы для карт всегда имеют «сырой» формат. «Сырой» формат также используется для некоторых спрайтов интерфейса. Спрайты в упакованном формате 32×32 — это викинги и многие враги. Распакованный формат используется для некоторых слабо анимированных врагов типа башни с пушкой и других объектов, например, переключателей и лифтов.
Похоже, что в Blackthorne совсем не используется упакованный формат 32×32. Возможно, потому, что многие спрайты Blackthorne крупнее 32×32. Большинство спрайтов с подробной анимацией использует «сырой» формат. В Blackthorne нет уровней со скроллингом (как в оригинальной Prince of Persia), что ускоряет рендеринг.
Я не разобрался ещё в одном вопросе: как движок Blizzard понимает, какой формат и размер спрайтов используется для отрисовки каждого объекта? В заголовках уровней есть частичная соответствующая информация, но её недостаточно для правильной отрисовки всех объектов. Подозреваю, что эти части информации о рендеринге управляются виртуальной машиной.
Расположение спрайтов
Как я упомянул выше, в Blackthorne используются спрайты большего размера, чем в The Lost Vikings. Несмотря на то, что можно написать алгоритм рендеринга «сырых» спрайтов произвольного размера, в движке Blizzard применяется другой подход. Крупные спрайты рендерятся соединением нескольких мелких спрайтов по неизменному шаблону. Например, в главном персонаже Blackthorne используются спрайты 32×48, состоящие из двух спрайтов 16×16 для головы и одного спрайта 32×32 для тела:
Стоит заметить, что используемый здесь фоновый цвет на самом деле является цветом с индексом 0 для спрайтов Blackthorne, который считается в игре прозрачным цветом. Весь набор спрайтов персонажа Blackthorne можно посмотреть так:
./sprite_view --blackthorne DATA.DAT -fraw -w32 -h48 -l2 -b0x80 0x42Возможно, такой подход был выбран потому, что разработчики Blizzard уже написали оптимизированные циклы рендеринга для спрайтов 16×16 и 32×32, и быстрее было рендерить крупные спрайты как набор мелких, а не как один большой.
Уровни из тайловых карт
И в The Lost Vikings, и в Blackthorne уровни создаются из тайловых карт с тайлами 16×16 (хотя мне кажется, что в обеих играх авторы хорошо постарались, чтобы такого ощущения не возникало). Используемые для тайлов спрайты на самом деле имеют размер 8×8. Каждый тайл содержит структуру, которую я называю «заготовкой». Она определяет, как создать набор спрайтов 8×8 из тайла 16×16. Каждую часть компонента можно горизонтально/вертикально перевернуть, что позволяет использовать компонентные тайлы в разных местах.
Например, в полном наборе тайлов (тайлсете) первого уровня The Lost Vikings есть несколько тайлов, таких как лестницы, которые имеют отзеркаленные версии, а также множество тайлов, которые несколько раз используют один угловой фрагмент, например, синие панели с заклёпками.
Просмотреть этот набор тайлов можно так:
./tileset_view DATA.DAT 1Пакетный файл содержит для каждого набора тайлов блок, описывающий заготовки. Каждая заготовка имеет длину 8 байт, а каждый тайл закодирован как 16-битное значение. Для каждого 16-битного значения индекс спрайта кодируется как 10-битное значение, а остальные 6 бит используются как флаги. Флаги определяют вертикальное и/или горизонтальное отзеркаливание спрайта, а также то, где находится этот компонент тайла: спереди или на фоне. Кодирование бита передней/фоновой части в заготовке позволило движку Blizzard использовать общую тайловую карту для рендеринга обоих слоёв
Blackthone расширяет использование заготовок в движке двумя способами. Во-первых, три неиспользованных бита флагов применены в качестве цветовой основы. The Lost Vikings привязывает ко всем тайлам карты только 16 цветов. Благодаря добавлению битов цветовой основы Blackthorne может использовать для тайлов 128 цветов, однако каждый отдельный спрайт компонента всё равно ограничен 16 цветами.
Во-вторых, в Blackthorne добавили фоновый слой карты. Это позволяет игре иметь более подробные фоны и небо, просвечивающие сквозь пустоты в передних тайлах. Для простоты я буду называть вторичный фоновый слой слоем неба, а основную тайловую карту — передним и фоновым слоями. Слой неба не использует биты флагов передней части/фона, поэтому можно рассматривать его как единый слой.
На рисунке ниже показано, как собирается тайловая карта для первого уровня Blackthorne:
Слева направо, сверху вниз: небо/фон, передние тайлы, фоновые тайлы, все слои
Можно просмотреть тайловую карту следующим образом (заметьте, что уровень имеет номер 3, потому что уровни 1 и 2 — это начальная анимационная заставка и обучающий уровень):
./level_view --blackthorne DATA.DAT 3Здесь можно заметить пару интересных моментов:
- Некоторые части слоя неба полностью перекрыты передними слоями. Возможно, так получилось из-за процесса разработки или инструментов Blizzard.
- Часть водопадов отрисовывается на слое неба, а другая часть — на фоне. Например, в правом нижнем углу основание водопада отрисовано на слое неба. Так получилось потому, что на верхнем слое есть камень, закрывающий водопад. Из-за формы камня его нельзя отрисовать с помощью одной карты с правильной обработкой передней части/фона.
- Некоторые области карты как будто отсутствуют. Например, водопад посередине вверху внезапно обрывается. Это потому, что в Blackthorne используются статические комнаты, а не скроллинг. Пустые области карты в процессе игры никогда не видны. На некоторых уровнях это весьма затратно, потому что не используются целые экраны. Возможно, Blizzard решила реализовать экраны на одной тайловой карте даже несмотря на то, что в игре не используется скроллинг, чтобы снова задействовать уже имеющийся код движка The Lost Vikings.
Всё — это уровень
Blizzard сделала ещё один умный шаг: всё в игре — промежуточные экраны, анимированные заставки, меню — является уровнями. Без сомнения, это очень сэкономило время на разработку. Поскольку весь тяжкий труд по реализации кода для уровней игры с анимацией и подвижными объектами был уже сделан, то вполне логично снова использовать его для управления заставками и меню. Полагаю, в движке игры снова используется виртуальная машина для реализации анимации в уровнях анимационных заставок. Единственным заметным исключением стал начальный экран The Lost Vikings из начала этого раздела, который закодирован как большой «сырой» спрайт без сжатия.
Например, при запуске игры отображается несколько начальных экранов. Два из них закодированы как единый уровень (из двух комнат). В левой части изображения ниже показан набор тайлов для уровня, а справа — сам уровень. В игре сначала показывается силуэт персонажа (который светится, но подробнее об этом позже). Логотип Blackthorne отображается над главным меню.
Не знаю точно, зачем нужны эти две копии тайлов логотипа Blackthorne. Заметьте, что они имеют немного отличающуюся расцветку. Например, в верхнем наборе значок TM чёрный и находится внутри логотипа, а в нижнем — белый и находится снаружи. Возможно, этот набор тайлов ещё раз используется для другого экрана в конце игры?
Набор тайлов и уровень этого экрана можно посмотреть так:
./tileset_view --blackthorne DATA.DAT 1 -c 0x6e
./level_view --blackthorne DATA.DAT 1 -h0x6eУправление палитрой
Выше я говорил о том, что в каждом спрайте используется шестнадцать цветов, а значения всегда кодируются как 0x0 – 0xf. Это позволяет каждому уровню назначать свою собственную палитру для повторного использования спрайтов в разных уровнях.
В The Lost Vikings есть несколько миров, в том числе космический, доисторический и безумный конфетный миры. В каждом есть свои цветовая схема и враги. Управляемые игроком викинги используют только два набора палитр из 16 цветов (Олаф и Балеог оба используют одну зелёно-жёлтую цветовую схему, у Эрика — красно-синяя схема). В интерфейсе используется ещё один набор из 16 цветов, а ещё одна используется для предметов, таких как ключи и пополнение здоровья, которые есть во всех мирах. Благодаря этому остаётся приличная часть 256-цветной палитры, которая определяется уровнем. В большинстве уровней загружается базовая 128-цветовая палитна, а затем набор из восьми 16-цветных палитр.
Индивидуальные палитры уровней позволяют повторно использовать спрайты с другой цветовой схемой. Это был популярный трюк в эру 8-битного цвета и ограниченного дискового пространства. Как известно, в играх Mortal Kombat есть несколько палитр, меняющих внешний вид персонажей-ниндзя. На рисунке ниже показаны одни и те же спрайты динозавра с настройками палитры разных уровней:
Просмотреть две разные версии спрайта динозавра можно так:
./sprite_view DATA.DAT -fpacked32 -b0xc0 -l5 0xf8
./sprite_view DATA.DAT -fpacked32 -b0xc0 -l10 0xf8Заметьте, что программе просмотра спрайтов передаются аргументы номера уровня (-l) и смещения базовой палитры offset (-b). Номер уровня используется для определения того, какие блоки палитры нужно загружать при анализе блока заголовка уровня. Индекс базовой палитры я определил экспериментально. Повторюсь, в этой части движка Blizzard я разобрался не полностью. Снова подозреваю, что индекс базовой палитры указывается командами в программе объектов виртуальной машины.
Анимации палитр
Ещё один популярный трюк из эры DOS — анимация графики сменой цветов палитры. Анимация объекта перерисовкой пикселей довольно затратна, особенно для больших частей, которые нужно часто обновлять, например, для фоновых водопадов в Blackthorne. Вместо изменения самих пикселей гораздо экономнее изменять цвета палитры. При этом мгновенно обновляются все пиксели соответствующего цвета. Эта техника в основном полезна для простых цикличных анимаций, таких как водопады и мигающие огни в космических уровнях The Lost Vikings. Как сказано ранее, анимации палитры используются в Blackthorne для создания эффекта свечения силуэта на начальном экране.
Движок Blizzard реализует анимации палитры в заголовке уровня. Каждый аниматор палитры имеет 8-битное значение скорости и два 8-битных значения индекса цвета. Если два индекса не равны, то анимация циклически переключается между двумя этими индексами. Такой формат хорошо подходит для анимации движущихся по шаблону объектов.
Если два индекса равны, то анимация палитры используется для одного цвета и заголовок уровня указывает список 16-битных значений для анимации. Каждое из 16-битных значений кодирует значение цвета в формате RGB-555 (5 бит на цвет, то есть один бит теряется впустую). Обычная палитра VGA и движок Blizzard способны отображать 6 бит на цвет. Анимации палитры теряют младший значимый байт сдвигом каждого значения цвета на один влево. Этот формат анимации палитры полезен для анимации чего-то типа пульсирующего света.
Можно нажать в программе просмотра уровней «A», чтобы посмотреть анимации палитр.
Game Over
На этом пока всё:
./level_view DATA.DAT 48
./level_view --blackthorne DATA.DAT 23
Можете читать меня в Twitter: @ryiron.
