Я потратил две недели на чтение и реверс-инжиниринг исходного кода Another World (в Северной Америке игра вышла под названием Out Of This World). Моя работа основана на обратной разработке Грегори Монтуа (Gregory Montoir) оригинального исполняемого файла для DOS из двоичного кода в C++.
Я был потрясён, обнаружив элегантную систему, состоящую из виртуальной машины, интерпретирующей байт-код в реальном времени и генерирующей полноэкранное векторное движение. Результатом этой работы стала одна из лучших игр всех времён…
Всё это умещалось на гибкий диск ёмкостью 1,44 МБ и работало на 600 КБ ОЗУ. Совсем неплохо для 1991 года! Как обычно, я привёл свои заметки в порядок — это поможет кому-нибудь сэкономить несколько часов работы.
Но… какой исходный код?
Исходный код Another World никогда официально не публиковался и утечек тоже не было. Люди, страстно влюблённые в эту революционную игру, выполнили обратную разработку исполняемого файла DOS.
Отчасти это стало возможным благодаря небольшому размеру двоичного файла (20 КБ). Почему он был таким маленьким? Потому что ANOTHER.EXE — это не сама игра, а только виртуальная машина:
- Хранящая байт-код.
- Выполняющая системные вызовы.
Байт-код выполняет всю игровую логику с помощью собственных кодов операций, но использует системные вызовы для выполнения «тяжёлых» задач типа отрисовки, воспроизведения музыки, звуков и управления ресурсами игры.
Реализация только виртуальной машины под нужную ОС требует значительно меньше усилий, поэтому игра была портирована больше чем на дюжину платформ:
- 1991 год: Amiga, Atari ST
- 1992 год: Apple IIGS, DOS, SNES, Mega Drive
- 1993 год: 3DO
- 2004 год: GameBoy Advanced
- 2005 год: Windows XP, Symbia OS, Windows Mobile
- 2011 год: iOS
Каждый раз нужно было всего лишь скомпилировать виртуальную машину под ОС — байт-код оставался тем же!
Архитектура
Исполняемый файл занимает всего 20 КБ. Он имеет следующую схему:
Мы видим здесь четыре модуля:
- Virtual Machine (виртуальная машина): управляет всей системой.
- Resource Manager (менеджер ресурсов): загружает ресурсы с гибкого диска, когда их запрашивает виртуальная машина.
- Sound/Music mixer (микшер звука/музыки): микширует шумы при запросе ВМ.
- Renderer (рендерер): считывает и рендерит вершины по запросу ВМ. Считывает вершины из сегментов памяти.
Интересный факт: сегмент памяти палитр на самом деле содержит несколько палитр, используемых для красивых эффектов постепенного изменения цвета.
При запуске исполняемый файл устанавливает значение «0» для программного счётчика потока виртуальной машины (0x00) и начинает интерпретирование. После этого всё управляется байт-кодом.
Объяснение процесса визуализации
На предыдущей схеме показаны три буфера кадров (framebuffer). Два нужны, потому что Another World реализует двойную буферизацию программно, а третий используется как умная оптимизация:
Третий буфер кадра используется только один раз для композитинга фона и сцены, а потом повторно применяет его кадр за кадром с помощью простого memcpy:
В этом видео замедлена визуализация легендарного экрана первого уровня Another World, чтобы можно было заметить процесс отрисовки. Всё отрисовывается с помощью полигонов и пиксигонов. Количество перерисовок очень значительное, но поскольку сцена генерируется только один раз, то это не так уж и плохо.
Интересный факт: этот знаменитый фон состоит из 981 полигона.
Для визуалиации полной картины я замедлил и отрендерил три буфера кадра и то, что отображается на экране:
Здесь очень чётко видны:
- Двойная буферизация с визуализацией, выполняемой по очереди в переднем/заднем буфере.
- Буфер фона генерируется один раз и хранится в верхнем левом буфере. Затем он копируется в начале каждого кадра.
- Если фон изменяется (например, в случае с остановкой автомобиля), буфер фона обновляется, чтобы сэкономить ещё больше места и времени.
Если вы хотите проанализировать отрисовку подробнее, то вот полное видео.
Виртуальная машина Another World
На странице Эрика Шайи (Eric Chahi) подробно объясняется структура ВМ.
В коде на github можно увидеть, как реализуется каждый код операции. Все их довольно просто понять, за исключением операций визуализации. Хитрость в том, что исходный код сегмента полигонов, в котором должны считываться вершины, встроен с идентификатором кода операции.
Вот несколько скриншотов из редактора байт-кода ВМ (его создал Эрик Шайи и дал ему название «script editor»):
Здесь заметно, как теряется метка: setvec 21 nag1 устанавливает счётчик инструкций потока 21 на смещение метки «nag1». В байт-коде видно только жёстко заданное смещение.
Случаи использования кодов операций
На схемах ниже показан вызов кодов операций виртуальной машиной, который на самом деле является системным вызовом менеджеру ресурсов для загрузки четырёх сегментов памяти. Это обычно случается в начале части игры (вся игра разделена на 10 частей):
На следующей схеме код операции также является системным вызовом рендера, запрашивающим отрисовку и получение вершин. Коды операций визуализации немного более сложны, потому что они содержат указания на адреса, из которых нужно считывать вершины. Выбор целевого буфера кадра — это совершенно независимый код операции:
Примечание: выбор того, откуда рендерер должен считывать вершины (из сегмента кинематических полигонов или из сегмента анимаций), кодируется с помощью opcodeId.
Управление ресурсами
Ресурсы идентифицируются уникальным целочисленным идентификатором. При запуске менеджер ресурсов открывает MEMLIST.BIN и получает из него записи следующим образом:
typedef struct memEntry_s
{
int bankId;
int offset;
int size;
int unpackedSize;
} memEntry_t;Если ВМ запрашивает resourceId, то менеджер ресурсов:
- Находит его, открывая файл банка (по bankId).
- Пропускает
offsetи считываетsizeбайт в ОЗУ. - Если
size!=unpackedSize, то ресурс должен быть распакован.
Немного статистики о сжатии:
Общее количество ресурсов: 146
Сжатых : 120
Несжатых : 28
Примечание: 82% ресурсов сжато.
Общий размер (несжатый) : 1820901 байт.
Общий размер (сжатый) : 1236519 байт.
Примечание: экономия при сжатии : 32%.
Total RT_SOUND несжатый размер: 699868 (38% от общего несжатого размера) сжатый размер 585052 (47% пространства на гибком диске) экономия: (16%)
Total RT_MUSIC несжатый размер: 33344 (2% от общего несжатого размера) сжатый размер 3540 (0% пространства на гибком диске) экономия: (89%)
Total RT_POLY_ANIM несжатый размер: 384000 (21% от общего несжатого размера) сжатый размер 106676 (9% пространства на гибком диске) экономия: (72%)
Total RT_PALETTE несжатый размер: 18432 (1% от общего несжатого размера) сжатый размер 11032 (1% пространства на гибком диске) экономия: (40%)
Total RT_BYTECODE несжатый размер: 203546 (11% от общего несжатого размера) сжатый размер 135948 (11% пространства на гибком диске) экономия: (33%)
Total RT_POLY_CINEMATIC несжатый размер: 365960 (20% от общего несжатого размера) сжатый размер 291008 (24% пространства на гибком диске) экономия: (20%)
Примечание: чёртов коэффициент сжатия звука!
Всего файлов банков: 148
Файлов Total RT_SOUND: 103
Файлов Total RT_MUSIC: 3
Файлов Total RT_POLY_ANIM: 12
Файлов Total RT_PALETTE: 9
Файлов Total RT_BYTECODE: 9
Файлов Total RT_POLY_CINEMATIC: 9Я не стал тратить время на обратную разработку алгоритма сжатия. Тот факт, что звук сжался не очень хорошо, навёл меня на мысль, что алгоритм чувствителен к энтропии… поэтому, возможно, это вариация алгоритма Хаффмана?
Из 146 ресурсов 120 сжаты:
- Векторная визуализация плюс сжатие поверх него давали ОГРОМНУЮ выгоду (экономия до 62% места!).
- Сжатие звука очень неэффективно: экономия мала, и ресурсы занимают 47% пространства гибкого диска.
Интересный факт: начальная заставка (ресурс 0x1C) длительностью 3 минуты занимает после сжатия всего 57 510 байт.
Управление памятью
Как и во всех играх 90-х во время игрового процесса память не распределялась. При запуске движок игры получал 600 КБ памяти (кто-нибудь ещё помнит 640 КБ базовой памяти DOS?). Эти 600 КБ использовались как стековый распределитель:
Свободная память: менеджер памяти имел возможность освобождать память на один цикл назад ИЛИ освобождать всю память. На практике вся память освобождалась в конце каждой из 10 частей игры.
Интересный факт: изначально во всех 600 КБ хранились байт-код и вершины. Но после двух лет генерирования фонов из полигонов/пиксигонов игра по-прежнему была далека от завершения. Для ускорения разработки Эрик Шайи решил внедрить в свою замечательную архитектуру хак (ценой ему стало снижение производительности): менеджер ресурсов может загружать битовое изображение фона с гибкого диска в буфер фона (void copyToBackgroundBuffer(const uint8 *src);). Поэтому в конце базовой памяти были зарезервированы 32КБ (320x200/2).
Интересный факт: этот хак применили при выпуске Another World под Windows XP в 2005 году. Все фоны были нарисованы вручную и загружались напрямую с жёсткого диска без использования рендерера и его пиксигонов:
Уголок пуриста
Если вы пурист и хотите играть только в оригинальную версию, то Another World замечательно работает в DosBOX:
Или можно поиграть в версию для Windows XP. Рекомендую купить Collector's edition, потому что в ней содержится множество дополнительной информации, в том числе и технические заметки Эрика Шайи:
И ещё кое-что
Я много работал над кодом, чтобы сделать его проще для понимания. Вот пример того, насколько он стал яснее.
До:
void Logic::runScripts() {
for (int i = 0; i < 0x40; ++i) {
if (_scriptPaused[0][i] == 0) {
uint16 n = _scriptSlotsPos[0][i];
if (n != 0xFFFF) {
_scriptPtr.pc = _res->_segCode + n;
_stackPtr = 0;
_scriptHalted = false;
debug(DBG_LOGIC, "Logic::runScripts() i=0x%02X n=0x%02X *p=0x%02X", i, n, *_scriptPtr.pc);
executeScript();
_scriptSlotsPos[0][i] = _scriptPtr.pc - _res->_segCode;
debug(DBG_LOGIC, "Logic::runScripts() i=0x%02X pos=0x%X", i, _scriptSlotsPos[0][i]);
if (_stub->_pi.quit) {
break;
}
}
}
}
}После:
void VirtualMachine::hostFrame() {
// Выполнение ВМ для каждого активного потока (один кадр ВМ).
// Неактивные потоки помечаются указателем инструкции потока 0xFFFF (VM_INACTIVE_THREAD).
// Поток должен иметь код операции прерывания, чтобы интерпретатор смог перейти к следующему потоку.
for (int threadId = 0; threadId < VM_NUM_THREADS; threadId++) {
if (!vmIsChannelActive[CURR_STATE][threadId])
continue;
uint16 pcOffset = threadsData[PC_OFFSET][threadId];
if (pcOffset != VM_INACTIVE_THREAD) {
// Установка указателя скрипта в нужное положение.
// pc скрипта используется для выполнения executeThread по порядку
// для получения следующего кода операции.
_scriptPtr.pc = res->segBytecode + pcOffset;
_stackPtr = 0;
gotoNextThread = false;
debug(DBG_VM, "VirtualMachine::hostFrame() i=0x%02X n=0x%02X *p=0x%02X", threadId, n, *_scriptPtr.pc);
executeThread();
//Поскольку .pc будет изменён этой следующей итерацией цикла, нам нужно сохранить его.
threadsData[PC_OFFSET][threadId] = _scriptPtr.pc - res->segBytecode;
debug(DBG_VM, "VirtualMachine::hostFrame() i=0x%02X pos=0x%X", threadId, threadsData[0][threadId]);
if (sys->input.quit) {
break;
}
}
}
}
- Я использовал MACROS, чтобы избавиться от запутанных жёстко заданных значений.
- Переименовал переменные.
- Добавил МНОЖЕСТВО комментариев.
Здесь выложен «человекочитаемый» исходный код! Успешного хакинга.
Автор: PatientZero
