Сказ о компрессоре, который можно называть, но не помню, как

в 6:53, , рубрики: dos, LZ, reverse engineering, обратная разработка, реверс-инжиниринг, сжатие без потерь, сжатие данных, старые игры, метки:

Вашему вниманию предоставляется не совсем новогодняя история, в которой есть завязка, интрига, детективное расследование, погоня, коварство, мудрость древних и счастливый финал. Под катом вас ожидают археологические раскопки Хабра эпохи перестройки и щепотка ассемблера x86 по вкусу.
Сказ о компрессоре, который можно называть, но не помню, как - 1

Завязка

Я люблю играть в старые компьютерные игры, которые выпущены в конце 80-х – начале 90-х. В них есть свой непередаваемый олдовый антураж, преобладание игровой механики и сюжета над выразительными средствами и прочие вещи, за которые люди любят олдскул. Еще когда я учился в старших классах, мне попалась игра Skycat от Gamos, которая представляла собой 2d-шутер с элементами головоломки. Мне было интересно в нее играть, однако я не мог пройти даже первый уровень. В те времена я уже увлекался программированием на Паскале и успел упереться в ограниченные возможности графики модуля GRAPH.TPU, поэтому потихоньку стал приобщаться к миру ассемблера x86. И вот в один прекрасный день, поглядев на IDA им. тов. Гильфанова и на файл SKYCAT.EXE весом в каких-то 15 килобайт, я принял опрометчивое решение: провести полный reverse engineering непроходимой игры, чтобы узнать, что у нее там внутри. Этим увлекательным процессом я занимаюсь уже много лет в очень неторопливом режиме, и по его завершении планирую поделиться результатами с сообществом (надеюсь, что не через столько же лет, сейчас дело гораздо ближе к успешному концу, чем к началу). Но эта статья будет не совсем о том.

На новогодние праздники-2016 я решил потешить себя игрой в Sid Meier's Civilization на самом сложном уровне. Как вы уже поняли, геймер я довольно криворукий, поэтому после пары неудачных партий я решил поискать заныканный в папке с игрой трейнер, CIVHELP.EXE, который делает довольно простые вещи – меняет в сейве год и казну. Поглядев на размер файла в 9 килобайт и свой в меру успешный опыт обратной разработки SkyCat, я принял еще одно опрометчивое решение – а чего не поковырять-то, в самом деле! IDA предостерегла меня сообщением «Possibly packed file, continue?», но тщетно. Под капотом начались чудеса.

Интрига

После анализа файла IDA выдала неутешительную картину – в файле была обнаружена жалкая щепотка инструкций на 300 байт весу, всё остальное было детектировано как упакованные данные. Ну что ж, не беда – загрузим в Turbo Debugger, поставим точку останова аккурат после распаковки, запустим, сделаем дамп памяти. И…

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

Дабы не утомить читателя, у которого от новогодних праздников наверняка слегка притупилось внимание, опишу вкратце, что происходит в этих 300 спартанских байтах. Сначала происходит перемещение кода распаковщика в старшие адреса памяти (чтобы при распаковке не потереть собственный код), а на прежнем месте идет распаковка сегмента упакованных данных и передача управления в него. Эти манипуляции показались мне не особо сложными, но вот код распаковщика показался знакомым. Аналогичная штука распаковывала звуковые файлы в SkyCat!


Голос робота в заставке хранится в запакованном файле

Я был, мягко говоря, удивлён. Полез сверять ассемблерный код распаковщика звука в SkyCat и кода CIVHELP. Они оказались идентичными с точностью до названия меток. Вывод напрашивался сам собой – распаковщик должен быть достаточно известным, чтобы попасть в две программы от разных авторов. Дожидаться третьего пришествия таинственного распаковщика я не стал и решил узнать имя виновника торжества. Вот только как это сделать, имея на руках кучку ассемблерного кода?

Детективное расследование

Распаковщик оказался устроен не очень сложно, поэтому расковыряв его код при анализе SkyCat, я понял его принцип работы: читать из входного потока управляющее слово, из этого слова читать побитовые команды – либо копирование байта из входного потока в выходной, либо копирование части уже декодированного потока в выходной, – и по исчерпанию управляющего слова снова зачерпывать его из входного потока, пока тот не иссякнет. Если читатель не боится древних пророчеств на страшном языке ассемблера x86, то с полученным кодом может ознакомиться здесь. Остаток университетских знаний в голове подсказал, что на такой идее построен алгоритм Лемпеля-Зива и все его многочисленные потомки. Соответственно, круг моих поисков сузился (пусть и незначительно) до семейства LZ, оставив за бортом таких замечательных человекопараходов, как Хаффман, Барроуз, Уиллер, Фано и Шеннон. Изучив внушительный список алгоритмов семейства LZ, я не нашёл ни одной реализации, использовавшей подход моего таинственного декомпрессора – не использовать при распаковке словарей, не разбазаривать по нескольку бит на индикацию копирования единичного символа и прочие тонкие моменты.

Следующая идея (которая, вообще-то, человеку разумному пришла бы в голову первой) – сигнатурный анализ. Различные программы зачастую оставляют в файлах специальные байты-маркеры, чтобы понять, какая программа создала данный файл и/или какая программа сможет его прочитать/отредактировать/запустить. Например, исполняемые файлы DOS начинаются с символов MZ, изображения BMP содержат заголовок BM. Насчёт SkyCat я был уверен, что знаю назначение каждого байта, и поэтому там никаких пометок быть не могло. В файле CIVHELP.EXE после кода распаковки шли 5 байт данных, которые при конвертации в строку выглядели как *FAB*. Беглое гугление показало, что по данному клочку текста ничего компьютерного найти мне не удастся. Попытка сигнатурного анализа успела провалиться, не успев начаться.

В азарте я стал читать на различных сайтах о продолжателях дела Лемпеля и Зива, вглядываться в их исходные коды, изучать различную логику работы, но ничего похожего не находилось. После нескольких часов поиска я набрел на сборник различных компрессоров с исходниками, стал скачивать архивы один за другим, распаковывать, просматривать исходники… и вдруг глаз зацепился за знакомый ассемблерный код!

Погоня

; "Лягушка" - программа, которая сначала прыгает по памяти,
; потом распаковывает данные и наконец запускает полученный код
; Адаптация (C) Красильников 1991

Файл FROG.ASM содержал такое забавное описание, а под ним – код того самого компрессора! Казалось бы, мои поиски закончены, но у меня оставался еще ряд вопросов.
В папке с компрессором лежал документ, который гласил:

Ю. Д. Красильников. Программа сжатия/разжатия файлов и компрессор .COM-файлов.
Мотивом для написания данных программ послужила опубликованная ранее в «Софтпанораме» статья И.Тараненко «Процедура упаковки данных SQUEEZE». Процедура использовала принцип работы упаковщика LZEXE. Данный алгоритм отличает простота, эффективность и очень высокая скорость распаковки данных.

Уже отсюда следовало, что товарищ Красильников не предлагал упаковку EXE-файлов, потому что это до него умели делать как минимум товарищ Тараненко и утилита LZEXE. Дальнейшее описание гласило, что FROG.ASM – вообще вспомогательная утилита для распаковки, код COM-упаковщика написан на языке C. Кто же тогда запаковал CIVHELP.EXE и какой программой? Почему звуковые файлы в SkyCat были упакованы как простые данные?

Я решил копать в сторону LZEXE. Оказалось, что ее автор, Фабрис Беллар – очень крутой программист, и мне должно быть стыдно, что я до сих пор о нем ничего не знал. В голове промелькнула таинственная строчка *FAB*, и стало ясно, что это подпись автора. Однако исходников своего замечательного компрессора Фабрис так и не предоставил. Некоторым утешением стало, что Митугу Куризоно создал утилиту UNLZEXE, которая раскукоживала результат жизнедеятельности LZEXE до исходного состояния. Что ж, это нам и нужно! Я расчехлил DosBox, набрал в командной строке

UNLZEXE.EXE CIVHELP.EXE

и получил сообщение

CIVHELP.EXE is not LZEXE file

Коварство

– Да что ж такое! – подумал я. – Не может же эта строчка *FAB* быть в файле просто так!

К счастью, в моем распоряжении был файл UNLZEXE.C с весьма лаконичным исходным кодом. Из него стало понятно, что для распаковки в EXE-файле по смещению 1C должна располагаться строка "LZ91". Подправляем HEX-редактором 4 байта – вуаля! Получаем из 8 килобайт аж целых 12, файл запускается, IDA показывает большую кучу кода и небольшую кучку человекочитаемых строк. По какой причине в заголовке оказались коварные байты, я не знаю. Фабрис утверждает, что выпускал только две версии компрессора, и у обеих сигнатуры были на месте. Мое предположение – это было сделано вручную для маскировки следов использования компрессора. Зачем было это делать при создании маленького трейнера для сейвов – отдельная загадка.

Мудрость древних

Остался один вопрос – происхождение компрессора в игре SkyCat. Точного ответа у меня нет, но есть догадка. Описанная выше программа-лягушка была опубликована в «Софтпанораме» – бюллетене программистов, основанном в 1989 году Николаем Безруковым. Основными целями «Софтпанорамы» были свободный обмен программами в исходных кодах и защита от компьютерных вирусов. Поскольку сообщество зародилось раньше, чем в стране получил распространение Фидонет, общение происходило путем рассылки и копирования дискет. Получается такой доисторический Хабр с уклоном в программирование, который заслуживает отдельной серьезной статьи (и очень желательно, чтобы ее написал кто-нибудь из тогдашних активных участников). Думаю, вполне вероятно, что прочитав один из выпусков «Софтпанорамы» разработчики отечественной компании Gamos могли позаимствовать открытый код у отечественного программиста Красильникова.

Счастливый финал

Поскольку мои поиски происхождения таинственного алгоритма увенчались успехом, я успокоился и остался доволен. А погружение в архив «Софтпанорамы» перенесло меня в незабываемый мир новостей программирования девяностых, что меня даже в некоторой степени осчастливило. Советую и вам причаститься к духу эпохи.

Автор: pehat

Источник

* - обязательные к заполнению поля


https://ajax.googleapis.com/ajax/libs/jquery/3.4.1/jquery.min.js