История
Дело было весной уже далёкого 2021-м года. Решил я тогда пореверсить какую-нибудь очередную игру на Sega Mega Drive / Genesis, и открыл в IDA Pro ром игры Fantastic Adventures of Dizzy. Эта игра была у меня в детстве на картридже, но пройти её тогда я, конечно, не смог - уж больно сложная (догадаться, что нужно собрать все звёзды, чтобы дойти до финального босса я был не в состоянии).
Тем не менее, даже сейчас - в сознательном возрасте, эту игру про яйцо, попавшее в трудную жизненную ситуацию, я считаю очень крутой и продуманной: графика сочная, музыка приятная, уровней много, куча головоломок - кайф! Вот так, на основании детской увлечённости и взрослого хобби я и выбираю игры под реверс-инжиниринг.
Что я хочу получить от процесса реверса игр?
На самом деле, чёткого ответа на этот вопрос у меня нет. Я не считаю себя ромхакером, чтобы выпускать моды хаки игр - мной был выпущен только один мод для одной игры на Сегу, когда у других их десятки. У меня не так много до конца доревершенных ромов (штуки 3-4 всего), часто процесс просто останавливается на каком-то месте и всё.
Скорее, я делаю это просто в качестве процесса, который успокаивает, позволяет помедитировать и, возможно, как результат, получить ещё и ра��очий инструмент для других потенциальных исследователей той же игры. Ну и, попутно я пользуюсь своими вспомогательными утилитами для IDA Pro, тем самым тестируя их и внося исправления или новые фичи.
Если говорить конкретно про игру Fantastic Dizzy, то мне хотелось сделать ещё и редактор уровней к ней, чтобы найти какие-то заложенные разработчиками секреты. Редактор уровней я так и не сделал, увы. Но, положительный результат от процесса у меня всё же получился.
Первая находка
Когда-то, ещё в 2015-2016 я уже ковырял эту игру. Тогда я нашёл какой-то алгоритм сжатия, понял, что это Amiga Imploder - часто использовавшийся во многих играх на Сегу и для Amiga, имеющий в заголовке тег IMP! и смог его отреверсить. Если точнее, то я восстановил код упаковщика посредством изучения его официального исполняемого файла - FImp.
После этого проект реверса игры заглох. На очень долгое время.
Возвращаемся в 2021
В свой второй подход к игре я смог сделать немного больше - нашёл второй алгоритм сжатия, который, к тому же, не был похож ни на один известный мне алгоритм сжатия (а за время "медитаций" я повидал их очень много). Распаковщик в коде игры был сложным, мне даже не удалось понять его логику, неговоря уже о переписывании на C.
Тогда я решил найти в титрах игры имя любого из разработчиков игры и написать ему, особо ни на что не претендуя, просто пообщаться. Ну, а если удастся ещё и разузнать что-то про применявшиеся инструменты разработки... будет очень круто!
Общение
Была только одна проблема. Игра старая (1991 год), авторы её тоже наверняка уже не молоды, почтовые адреса (если где-то и мелькали в интервью), уже давно не активны. Тем не менее, некоторое время поисков спустя, я нашёл одного разработчика и написал ему.
Написал на почту человеку предположительно с именем Derek Leigh-Gilchrist в фирму с названием Happy Cactus с таким вот вопросом:
Hello, I would like to contact "Derek Leigh-Gilchrist" to discuss Fantastic Adventures of Dizzy for Amiga and Sega Mega Drive with him. I'm a Sega Mega Drive and Amiga romhacker and it would be awesome to discuss these games with him.
Перевод:
Привет, я бы хотел связаться с "Derek Leigh-Gilchrist", чтобы обсудить с ним Fantastic Adventures of Dizzy для Amiga и Sega Mega Drive. Я - ромхакер Sega Mega Drive и Amiga игр и было бы классно обсудить с ним эти игры.
Читаю сейчас и смеюсь. До чего же я был тогда наивным...:)
Как бы то ни было, спустя время мне пришёл ответ:
Hello Vladimir!
It is I, Derek Leigh-Gilchrist... [Smile]
any questions, please ask away...Del.
Перевод:
Привет, Владимир!
Это Derek Leigh-Gilchrist...
Можешь задавать любые вопросы...Del.
Радости моей не было предела! Живой, да ещё и разработчик такой крутой игры из детства! Так и началась наша переписка.
Детали разработки игры Fantastic Dizzy
Characters and Sprites were compressed with a special compression system that analyzed the images before compressing them, and then used bit packing based on which colours were frequently next to other colours. The compression was an early form of 'deep learning' and it was created by a man called Jon Menzies who worked with us at Codemasters. We used this compression to help keep our games sitting on a 512k rom! It outperformed Lemppel-Ziv compression by about 30% on graphics files! Everything else was compressed with a modified version of imploder.
The z80 music driver was written by Ash Hogg, it converted specially created Amiga noisetracker modules.
I did all my Sega genesis work on an Amiga 4000/040 and downloaded the assembled code to sega megadrive ramboard via a parallel cable.
Hope this helps,
Del.
Перевод:
Значки и Спрайты были упакованы специальной системой сжатия, которая анализировала изображения вначале работы, и затем использовала битовое сжатие в зависимости от того, какие цвета встречались рядом наиболее часто. Само сжатие было ранней формой 'машинного обучения' и написано оно человеком по имени Jon Menzies, который работал тогда с нами в Codemasters. Мы использовали это сжатие для того, чтобы наши ромы укладывались в размер 512КБ! Оно превосходило алгоритм Lemppel-Ziv где-то на 30% на графических файлах! Всё остальное же сжималось модифицированной версией Imploder.
Драйвер музыки для z80 написал Ash Hogg, который конвертировал специально созданные Amiga noisetracker модули.
Всю свою работу для Sega Genesis я выполнял на Amiga 4000/040, а ассемблированный код загружал на картридж с оперативной памятью через параллельный кабель.
Надеюсь, данная информация окажется полезной,
Del.
Исходный код распаковщика
Здесь я хотел привести код в блоке кода, но, почему-то Markdown-редактор Хабра не осилил его, и обрезал мне часть статьи, поэтому, даю лишь ссылку: https://github.com/lab313ru/megapack-megadrive/blob/main/megaunp.s
По ней вы найдёте ровно тот код, что прислал мне Del, в оригинальном виде без исправлений.
Алгоритм сжатия
К сожалению, Дерек не смог найти исходный код упаковщика MEGAPACK. Я тогда ещё немного понаглел, узнал где сейчас Jon Menzies ("работал в Activision, а сейчас живёт в Калифорнии"), и наша переписка завершилась.
Спустя время, я, так и не осиливший алгоритм упаковщика, решил поделиться присланным текстом файла (да, Дерек отправил мне тогда код не вложением, а текстом, как есть) с достаточно известным в узких кругах ромхакером по имени Марат. И он, на моё удивление, через некоторое время прислал алгоритм упаковщика, написанный на Pascal.
Хотя, в своё время я и писал активно на Delphi, а в школе любил Pascal, смотреть на полученный файл мне было больно... Ни понимания алгоритма работы не прибавилось, ни возможности поделиться файлом с общественностью, который можно было бы встраивать в свой код. Тем не менее, это было огромный шаг к успеху! Алгоритм работает, сжимает как надо, 1 в 1.
Алгоритм сжатия на C
Конечно, я не мог просто так это оставить в Pascal-виде. Посидел пару дней (или недель), ��окряхтел, но алгоритм таки переписал. По ссылке (https://github.com/lab313ru/megapack-megadrive) вы найдёте все мелькавшие в статье исходники.
Сравнение с другими алгоритмами
Ну, так, а что там этим броским заголовком, в котором я назвал алгоритм сжатия от Jon Menzies лучшим? Давайте, в качестве примера, я приведу таблицу, в которой представлены все известные мне на 2021-й год упаковщики из других игр на Сегу). Исходный несжатый размер тестового файла - 18752 байт:
Алгоритм | Размер файла |
|---|---|
MEGAPACK (Fantastic Dizzy) | 10387 |
LZMA2 | 10867 |
GZIP | 11159 |
LZH Compression (Thunder Force 3) | 11386 |
Nemesis Compression (Many Sega games) | 11652 |
ApLib | 12682 |
RNC ProPack (Many Sega games) | 13297 |
Imploder Cruncher (Codemasters Sega games) | 13584 |
PowerPacker Cruncher (Amiga games) | 13728 |
Beam Software Compression (Radical Rex) | 13794 |
LZCaptsu Compression (Tecmo Cup) | 14774 |
LZKN1 Compression (Konami Sega games) | 15011 |
UMK3 Compression | 15131 |
LZToshio Compression (Crusader of Centy) | 15204 |
The Lost Vikings Compression | 15207 |
LZKN3 Compression (Konami Sega games) | 15392 |
Fact5LZ Compression (Internation Superstar Soccer Deluxe) | 15686 |
LZKN2 Compression (Konami Sega games) | 16204 |
I.T.L. Compression (Bonanza Bros.) | 16512 |
LZ4W (SGDK) | 16926 |
(Некоторые названия в таблице могут показаться вам незнакомыми, и это нормально. Часть из них восстанавливал из игр я сам)
Как видно из таблицы, алгоритм сжатия MEGAPACK явно превосходит всех остальных!
P.S.
Не бойтесь общаться:) Особенно с разработчиками видеоигр из вашего детства. Изучайте игры (особенно прошлых поколений) - в алгоритмах их работы можно найти много чего интересного.
Всем спасибо.
