что такое реверс в игре bmx 2

Touchgrind BMX 2

Touchgrind BMX 2 — спортивный симулятор трюков на велосипеде с видом от третьего лица. В этой игре вам предстоит путешествовать по. Подробнее

Об игре Touchgrind BMX 2

Особенности:
— Те же революционные элементы управления двумя пальцами, что и в первой части;
— Полностью настраиваемые велосипеды и специальные велосипеды;
— Множество разблокируемых предметов;
— Испытания и трофеи в каждой локации;
— Существенная система рейтинга для каждой локации — миа, страны, среди друзей;
— Личный профиль;
— Многопользовательские дуэли и частые внутриигровые турниры;
— Великолепная графика и звук;
— Раздел — как сделать, наглядно демонстрирующий, как кататься и выполнять трюки;
— Синхронизация прогресса между устройствами.

Скриншоты

Несколько лучших скриншотов из Touchgrind BMX 2:

Последние и новые скриншоты смотрите в галерее.

Даты выхода

Touchgrind BMX 2 уже вышла на iOS, Android.

Полный список дат выхода и платформ смотрите на странице релизов.

Похожие игры

Вот несколько игр, которые больше всего похожи на Touchgrind BMX 2:

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

Источник

Введение в реверс-инжиниринг: взламываем формат данных игры

Введение

Реверс-инжиниринг незнакомого файла данных можно описать как процесс постепенного понимания. Он во многом напоминает научный метод, только применённый к созданным человеком абстрактным объектам, а не к миру природы. Мы начинаем со сбора данных, а затем используем эту информацию для выдвижения одной или нескольких гипотез. Проверяем гипотезы и применяем результаты этих проверок для их уточнения. При необходимости повторяем процесс.

Развитие навыков реверс-инжиниринга — в основном вопрос практики. Накапливая опыт, вы выстраиваете интуитивное понимание того, что нужно исследовать в первую очередь, какие паттерны необходимо искать, и какие инструменты удобнее использовать.

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

Небольшая предыстория

Всё это началось, когда я пытался воссоздать игру Chip’s Challenge на Linux.

Изначально Chip’s Challenge была выпущена в 1989 году для ныне забытой портативной консоли Atari Lynx. Для того времени Atari Lynx была впечатляющей машиной, но она вышла в одно время с Nintendo Game Boy, которая в конце концов захватила рынок.

Chip’s Challenge — это игра-головоломка с видом сверху и тайловой картой. Как и в большинстве таких игр, цель каждого уровня заключается в том, чтобы добраться до выхода. В большей части уровней выход охраняется разъёмом для чипа, который можно миновать, только собрав определённое количество компьютерных чипов.

Новая игра начинается с первого уровня под названием «LESSON 1». Кроме чипов и разъёма для чипа, на нём появляются ключи и двери. На других уровнях возникают такие препятствия, как ловушки, бомбы, вода и существа, которые (чаще всего) движутся по предсказуемым маршрутам. Широкий набор объектов и устройств позволяет создавать множество загадок и ограничений по времени. Для завершения игры нужно пройти более 140 уровней.

Хотя Lynx в конце концов потерпела неудачу, Chip’s Challenge оказалась достаточно популярной и была портирована на множество других платформ, со временем появившись и на Microsoft Windows, где получила широкое распространение. Вокруг игры образовалась небольшая, но преданная база фанатов, и со временем был написан редактор уровней, позволявший игрокам создавать бесчисленные уровни.

И с этого начинается моя история. Я решил, что хочу создать версию базового движка игры с открытым исходным кодом, чтобы можно было играть в Chip’s Challenge в Linux и в Windows, и упростить запуск всех уровней, созданных фанатами.

Существование редактора уровней оказалось для меня чудом, потому что я мог исследовать скрытые особенности логики игры, создавая собственные уровни и проводя тесты. К сожалению, для оригинальной игры на Lynx редактора уровней не было, он появился только в более известном порте под Windows.

Порт под Windows создавался не разработчиками оригинала, поэтому в нём появилось множество изменений логики игры (и не все они были намеренными). Когда я начал писать свой движок, я хотел воссоздать в нём и логику игры оригинала на Lynx, и более известной версии под Windows. Но отсутствие редактора уровней на Lynx серьёзно ограничило мои возможности по подробному исследованию оригинальной игры. Порт под Windows имел преимущество: уровни сохранялись в отдельный файл данных, что упрощало его обнаружение и реверс-инжиниринг. Игра под Lynx распространялась на ROM-картриджах, содержавших спрайтовые изображения, звуковые эффекты и машинный код, а также данные уровней, которые выполнялись все вместе. Нет никаких намёков о том, где находятся данные в этом 128-килобайтном дампе ROM, или как они выглядят, а без этих знаний я никак не мог создать редактор уровней для версии на Lynx.

Однажды в процессе неторопливых исследований я наткнулся на копию порта Chip’s Challenge под MS-DOS. Как и в большинстве ранних портов игры, его логика была ближе к оригиналу, чем в версии под Windows. Когда я посмотрел на данные программы, чтобы узнать, как они хранятся, я с удивлением обнаружил, что данные уровней были выделены в отдельный каталог, а каждый уровень хранился в своём файле. Имея так удобно отделённые данные уровней, я предположил, что будет не слишком сложно выполнить реверс-инжиниринг файлов данных уровней. А это позволит написать редактор уровней для версии игры под MS-DOS. Я решил, что это интересная возможность.

Но затем другой участник сообщества Chip’s Challenge предупредил меня об интересном факте. Содержимое файлов уровней для MS-DOS оказалось побайтным дампом ROM Lynx. Это означало, что если я смогу декодировать файлы MS-DOS, то у меня получится затем использовать это знание для чтения и изменения уровней внутри дампа ROM Lynx. Тогда можно будет создать редактор уровней непосредственно для оригинальной игры на Lynx.

Внезапно моим основным приоритетом стал реверс-инжиниринг файлов уровней для MS-DOS.

Файлы данных

Законно ли это? Хороший вопрос. Поскольку эти файлы являются только небольшой частью программы для MS-DOS, и сами по себе они бесполезны, и поскольку я выкладываю их только в образовательных целях, то полагаю, что это подпадает под требованиях добросовестного использования (fair use). Надеюсь, со мной согласятся все заинтересованные стороны. (Если же я всё-таки получу от юристов письмо с угрозами, то могу изменить статью так, чтобы изложить файлы данных в забавном ключе, а затем заявить, что это пародия.)

Предварительные требования

Я буду считать, что вы знаете шестнадцатеричное исчисление, пусть даже и не владеете декодированием шестнадцатеричных значений, а также что вы немного знакомы с командной оболочкой (shell) Unix. Показанная в этой статье сессия оболочки выполняется на стандартной системе Linux, но почти используемые команды являются распространёнными утилитами Unix, и широко распространены на других Unix-подобных системах.

Первый взгляд

В каталоге находится 148 файлов данных, и в игре на самом деле ровно 148 уровней, так что тут всё совпадает.

Теперь давайте изучим, что же представляют собой эти файлы. xxd — это стандартная утилита для дампа шестнадцатеричных данных (hexdump). Давайте посмотрим, как выглядит внутри «LESSON 1».

Что такое утилита для создания hexdump? Шестнадцатеричный дамп — это стандартный способ отображения точных байтов двоичного файла. Большинство байтовых значений нельзя связать с печатными символами ASCII, или они имеют непонятный внешний вид (например символ табуляции). В шестнадцатеричном дампе отдельные байты выводятся в виде численных значений. Значения отображаются в шестнадцатеричном виде, отсюда и название. В показанном выше примере в одной строке вывода отображается 16 байт. Самый левый столбец показывает позицию строки в файле, тоже в шестнадцатеричном виде, поэтому в каждой строке число увеличивается на 16. Байты отображаются в восемь столбцов, и в каждом столбце отображается по два байта. Справа в hexdump показывается, как бы выглядели байты при отображении символами, только все непечатаемые значения ASCII заменены точками. Это упрощает нахождение строк, которые могут быть встроены в двоичный файл.

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

Что мы ожидаем увидеть?

Давайте сделаем шаг назад и проясним ситуацию: какие конкретно данные мы ожидаем найти в этих файлах данных?

Самое очевидное — это некая «карта» уровня: данные, обозначающие позиции стен и дверей, а также всего остального, что делает уровень уникальным.

(К счастью для нас, фанаты игры проделали кропотливую работу и собрали полные карты для всех 148 уровней, поэтому мы можем использовать их, чтобы знать, что должно находиться на каждой карте.)

В дополнение к карте у каждого уровня должно быть несколько других атрибутов. Например, можно заметить, что у каждого уровня есть название, например «LESSON 1», «PERFECT MATCH», «DRAWN AND QUARTERED», и так далее. У разных уровней также есть разные ограничения по времени, поэтому можно предположить, что эта информация тоже содержится в данных. Кроме того, на каждом уровне есть собственное число собираемых чипов. (Мы могли бы предположить, что это число просто соответствует количеству чипов на уровне, но оказывается, что на некоторых уровнях содержится больше чипов, чем нужно для открытия разъёма чипов. Хотя бы для этих уровней минимальное количество должно указываться в явной форме.)

Ещё один фрагмент данных, который мы ожидаем найти в данных уровня — это текст подсказок. На некоторых уровнях есть «кнопка подсказки» — лежащий на земле большой вопросительный знак. Когда Чип встаёт на него, показывается текст подсказки. Кнопка подсказки есть примерно на 20 уровнях.

Наконец, у каждого уровня есть пароль — последовательность из четырёх букв, позволяющая игроку продолжить игру с этого уровня. (Этот пароль необходим, потому что в Lynx нет хранилища данных. Сохранять на консоли игры было нельзя, поэтому продолжать игру после включения консоли можно было с помощью паролей.)

Итак, вот наш список нужных данных:

А что насчёт схемы уровня? Большинство уровней имеет размер 32 × 32 тайлов. Уровней большего размера не существует. Некоторые уровни меньше, но будет логично предположить, что они просто встроены в карту размером 32 × 32. Если предположить, что на один тайл карте требуется один байт, то для полной схемы нужно 1024 байта. То есть в целом мы получаем приблизительную оценку в 1142 байта на каждый уровень. Разумеется, это всего лишь грубая первоначальная прикидка. Вполне возможно, что некоторые из этих элементов хранятся иначе, или вообще не хранятся внутри файлов уровней. Или в них могут находиться другие данные, которые мы не заметили или не знаем о них. Но пока мы заложили неплохую основу.

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

Что там есть и чего нет

Здесь ничего не видно, кроме произвольных фрагментов ASCII-мусора.

Предположительно, где-то в этих файлах есть названия уровней и подсказки, но они или хранятся не в ASCII, или претерпели некую трансформацию (например, из-за сжатия).

Стоит также заметить следующее: файл едва дотягивает по размеру до 256 байт. Это довольно мало, учитывая, что изначально мы оценили его размер более чем в 1140 байт.

Самый большой файл занимает всего 680 байт, и это не очень много. А каким будет самый маленький?

Самый мелкий файл занимает всего 206 байт, что в три с лишним раза меньше самого большого. Это довольно широкий интервал с учётом того, что мы ожидали примерно одинаковых размеров уровней.

В нашей первоначальной оценке мы предположили, что карте потребуется по одному байту на тайл, и всего 1024 байт. Если мы урежем эту оценку вдвое, то есть каждый тайл потребует всего 4 бита (или два тайла на байт), то карта всё равно будет занимать 512 байт. 512 меньше, чем 680, но по-прежнему больше, чем размер большинства уровней. И в любом случае — 4 бита обеспечит всего 16 различных значений, а в игре гораздо больше разных объектов.

То есть очевидно, что карты не хранятся в этих файлах в открытом виде. В них используется или более сложное кодирование, обеспечивающее более эффективное описание, и/или они каким-то образом сжаты. Например, в уровне «LESSON 1» мы можем увидеть, как пропущенные записи для «пустых» тайлов значительно уменьшат общий размер данных карты.

Мы можем посмотреть на карты самых больших файлов:

Карта уровня 57: STRANGE MAZE

Карта уровня 98: SHRINKING

а затем сравнить их с картами самых маленьких файлов:

Карта уровня 106: KABLAM

Карта уровня 112: FORTUNE FAVORS THE

Это сравнение поддерживают нашу идею о том, что маленькие файлы данных соответствуют более простым уровням, или содержат больше избыточности. Например, если данные сжаты каким-то кодированием длин серий (run-length encoding), это с лёгкостью может объяснить интервалы размеров разных файлов.

Если файлы и на самом деле зашифрованы, то нам, скорее всего, придётся расшифровать сжатие, прежде чем мы приступим к расшифровке данных карт.

Изучаем несколько файлов одновременно

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

Давайте начнём с самого начала тайлов. Верх файла скорее всего используется для хранения «метаданных», сообщающих нам о содержимом файла. Посмотрев только на первую строку шестнадцатеричного дампа, мы можем выполнить простое и быстрое сравнение первых 16 байтов и поискать в них выделяющиеся паттерны:

Просмотрев этот дамп, можно заметить, что в каждом столбце возникают некие схожие значения.

Начав с первого байта, мы вскоре осознаём, что его значение находится в очень ограниченном интервале значений, в пределах шестнадцатеричных 10 – 40 (или примерно 20–60 в десятичном исчислении). Это довольно специфичная особенность.

Ещё интереснее то, что второй байт каждого файла всегда равен нулю, без исключений. Вероятно, второй байт не используется, или является заполнителем. Однако есть и другая вероятность — эти первые два байта вместе обозначают 16-битное значение, хранящееся в порядке little-endian.

Что такое little-endian? При сохранении численного значения, которое больше одного байта, нужно заранее выбрать порядок, в котором будут храниться байты. Если сначала вы сохраняете байт, представляющий меньшую часть числа, то это называется прямым порядком (little-endian); если вы сначала сохраняете байты, обозначающие бОльшую часть числа, то это обратный порядок (big-endian). Например, десятичные значения мы записываем в обратном порядке (big-endian): строка «42» означает «сорок два», а не «четыре и двадцать». Little-endian — это естественный порядок для многих семейств микропроцессоров, поэтому он обычно более популярен, за исключением сетевых протоколов, в которых обычно требуется big-endian.

Внимательнее изучаем исходные значения

Эти выходные данные показывают, что наши догадки о первых нескольких байтах были верными. Мы видим, что первое 16-битное значение находится в десятеричном интервале 20–70, а второе 16-битное значение — в десятеричном интервале 100–600. Однако последующие значения ведут себя не так хорошо. В них проявляются определённые паттерны (например, в четвёртой позиции на удивление часто встречается 1024), но они не обладают повторяемостью, свойственной первым значениям файла.

Поэтому давайте предварительно допустим, что первые четыре байта файла особые и состоят из двух 16-битных значений. Так как они находятся в самом начале файла, то скорее всего являются метаданными и помогают определить, как считывать остальную часть файла.

На самом деле, второй интервал значений (100–600) довольно близок к замеченному нами ранее интервалу размеров файлов (208–680). Возможно, это не совпадение? Давайте выдвинем гипотезу: хранящееся в третьем и четвёртом байтах файла 16-битное значение коррелирует с общим размером файла. Теперь, когда у нас есть гипотеза, мы можем её проверить. Посмотрим, действительно ли у больших файлов в этом месте постоянно большие значения, а у маленьких — маленькие.

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

Кроме того, первое 16-битное значение тоже обычно бывает больше при больших размерах файлов, но совпадение тоже не совсем полное, и можно легко найти примеры файлов среднего размера с относительно большими значениями в первой позиции. Но возможно если мы сложим эти два значения, их сумма будет лучше коррелировать с размером файла?

Мы можем использовать read для извлечения двух чисел из выходных данных od в отдельные переменные, а затем использовать арифметику командной оболочки для нахождения их суммы:

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

Разность, или значение «остатка», отображается в самой правой части вывода. Это значение не совсем попадает в постоянный паттерн, но, похоже, остаётся примерно в ограниченном интервале 40–120. И снова, чем больше файлы, тем обычно больше их значения остатков. Но иногда у мелких файлов тоже бывают большие значения остатков, так что это не так постоянно, как бы нам хотелось.

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

(Если вы достаточно внимательны, то уже увидели нечто, дающее подсказку о пока незамеченной связи. Если не увидели, то продолжайте читать; тайна вскоре будет раскрыта.)

Более масштабные перекрёстные сравнения файлов

На этом этапе было бы неплохо иметь возможность перекрёстно сравнивать больше, чем 16 байт за раз. Для этого нам потребуется другой тип визуализации. Один из хороших подходов — создать изображение, в котором каждый пиксель обозначает отдельный байт одного из файлов, а цвет обозначает значение этого байта. Изображение может показать срез всех 148 файлов за раз, если каждый файл данных будет обозначаться одной строкой пикселей изображения. Так как все файлы имеют разный размер, мы возьмём по 200 первых байт каждого, чтобы построить прямоугольное изображение.

Проще всего будет построить изображение в градациях серого, в котором значение каждого байта соответствует разным уровням серого. Можно очень просто создать файл PGM с нашими данными, потому что заголовок PGM состоит только из ASCII-текста:

Что такое файл PGM? PGM, что расшифровывается как «portable graymap» («платформонезависимая карта оттенков серого») — это один из трёх форматов графических файлов, которые созданы ради чрезвычайной простоты считывания и записи: после заголовка в ASCII, каждый байт описывает цвет одного пикселя в градациях серого. Два остальных формата файлов из этого семейства — это PBM («portable bitmap», «платформонезависимая битовая карта»), описывающий монохромные изображения как 8 пикселей на байт, и PPM («portable pixmap», «платформонезависимая пиксельная карта»), которая описывает изображения как 3 байта на пиксель.

Затем мы можем конкатенировать их с заголовком и создать отображаемое изображение:

xview — это старая программа X для отображения изображений в окне. Можете заменить её своим любимой программой просмотра изображений, например, утилитой display из ImageMagick, но учтите, что есть на удивление много утилит просмотра изображений, которые не принимают файл изображения, перенаправленный на стандартный вход.

Если вам сложно рассмотреть детали на тёмном изображении, то можете выбрать другую цветовую схему. Используйте утилиту pgmtoppm из ImageMagick, чтобы преобразовать пиксели в другой диапазон цветов. Эта версия создаст «негативное» изображение:

А эта версия делает низкие значения жёлтыми, а высокие — синими:

Видимость цветов — очень субъективный вопрос, поэтому можете поэкспериментировать, и выбрать, что лучше для вас. Как бы то ни было, изображение 200 × 148 довольно мало, так что лучше всего повысить видимость, увеличив его размер:

Изображение тёмное, и это означает, что большинство байтов содержит маленькие значения. Контрастирует с ним заметная полоса в основном ярких пикселей ближе к левому краю. Эта полоса расположена в третьем байте файла, который, как мы говорили выше, варьируется в полном интервале значений.

И хотя за пределами третьего байта есть не так много высоких значений, когда они появляются, то часто состоят из серий, создавая на изображении короткие яркие полоски. Некоторые из этих серий периодически прерываются, создавая эффект пунктирной линии. (Возможно, при правильном подборе цвета можно будет заметить такие последовательности и в более тёмных цветах.)

При внимательном изучении изображения можно понять, что в основном в левой части доминируют небольшие вертикальные полосы. Эти полосы говорят нам о некой повторяемости в большинстве файлов. Но не во всех файлах — время от времени появляются строки пикселей, где полосы прерываются — но этого более чем достаточно, чтобы определить наличие реального паттерна. Этот паттерн пропадает в правой части изображения, тёмный фон из полос уступает место чему-то более шумному и неопределённому. (Похоже, что полосы также отсутствуют в самой левой части изображения, но, повторюсь, возможно, что при использовании другой цветовой схемы можно увидеть, что они начинаются ближе к левому краю, чем это кажется здесь.)

Полосы состоят из тонких линий из немного более ярких пикселей на фоне из немного более тёмных пикселей. Следовательно, этот графический паттерн должен коррелировать с паттерном файлов данных, в которых немного бОльшие значения одинаково рассеяны среди немного меньших значений байтов. Похоже, что полосы истощаются примерно посередине изображения. Так как на нём показаны первые 200 байт файлов, следует ожидать, что байтовый паттерн заканчивается примерно после 100 байт.

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

Мы сразу же видим, что эта область файлов данных сильно отличается. Здесь намного чаще встречаются большие значения байтов, особенно ближе к концу файла. (Однако как и раньше, они предпочитают группироваться вместе, покрывая изображение яркими горизонтальными полосками.) Похоже, что частота высоких значений байтов увеличивается почти до самого конца, где резко обрывается и примерно в последних десяти-двенадцати байтах сменяется низкими значениями. И паттерн здесь тоже не универсален, но он слишком стандартный, чтобы оказаться совпадением.

Возможно, в середине файлов могут быть и другие области, которые мы пока не рассматривали. Следующее, что мы хотим сделать — исследовать таким образом файлы целиком. Но так как все файлы имеют разные размеры, их нельзя расположить в красивом прямоугольном массиве пикселей. Мы можем заполнить конец каждой строки чёрными пикселями, но будет лучше, если мы изменим их размер так, чтобы все строки были одинаковой ширины и пропорциональные области разных файлов более-менее совпадали.

И мы на самом деле можем это сделать, приложив чуть больше усилий. Можно воспользоваться Python и его библиотекой для работы с изображениями PIL («Pillow»):

Когда мы вызовем этот скрипт, использовав качестве аргументов полный список файлов данных, он создаст полное изображение и отобразит его в отдельном окне:

К сожалению, хоть это изображение и является полным, оно не показывает нам ничего нового. (А на самом деле показывает даже меньше, потому что изменение размера уничтожило паттерн из полос.) Наверно, для изучения всего множества данных нам потребуется процесс визуализации получше.

Характеризуем данные

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

Для полной переписи значений достаточно всего нескольких строк на Python:

Засунув все данные в одну переменную, мы можем выполнить подсчёт частоты появления каждого байтового значения.

Мы видим, что чаще всего встречаются байтовые значения 0 и 1, следующими по частоте идут 2 и 3, после чего количество продолжает уменьшаться (хотя и с меньшим постоянством). Чтобы лучше визуализировать эти данные, мы можем передать вывод в gnuplot и превратить эту перепись в гистограмму:

Очень заметно, что первые несколько байтовых значений встречаются гораздо чаще, чем все остальные. Несколько следующих значений тоже достаточно распространены, а затем частоты значений примерно от 50 начинают снижаться по плавной кривой вероятностей. Однако есть подмножество высоких значений, равномерно отделённых друг от друга, частота которых кажется довольно стабильной. Посмотрев на исходные выходные данные, мы можем убедиться, что это подмножество состоит из значений, без остатка делящихся на восемь.

Эти различия в количестве значений намекают, что существует несколько разных «классов» байтовых значений, поэтому будет логично посмотреть, как распределены эти классы. Первой группой байтовых значений будут самые низкие значения: 0, 1, 2 и 3. Тогда второй группой могут быть значения от 4 до 64. А третьей группой будут значения выше 64, которые без остатка делятся на 8. Всё остальное, в том числе и не делящиеся на 8 значения больше 64, будут составлять четвёртую и последнюю группу.

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

Мы назначили четырём группам красный, зелёный, синий и белый цвета. (Вы опять же можете попробовать выбрать другие цвета, соответствующие вашим предпочтениям.)

Благодаря этому изображению мы можем предварительно подтвердить правильность разделения файлов данных на пять частей:

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

Мы снова видим, что незелёные пиксели с основной третьей части время от времени образуют пунктирные паттерны из перемежающихся зелёных и красных пикселей (или синих, или белых). Однако этот паттерн не особо регулярен, и может быть мнимым.

Разумеется, это деление файла на пять частей очень условно. Четвёртая часть с высокими байтовыми значениями, делящимися на восемь, может оказаться всего лишь концом третьей части. Или может оказаться, что лучше всего разделить крупную третью часть на несколько частей, которые мы ещё не определили. На этом этапе обнаружение частей больше помогает нам находить места для дальнейшего исследования. Нам пока достаточно знать, что существуют части, в которых меняется общий состав байтовых значений, а приблизительное представление об их размере поможет нам продолжать исследования.

Поиск структуры

Что нам искать дальше? Ну, как и раньше, проще всего начать с верха файла. Или, скорее, рядом с верхом. Так как мы уже довольно уверенно определили первую часть как четырёхбайтный заголовок, давайте внимательнее рассмотрим то, что идёт дальше — область, которую мы называем второй частью, или частью полос. Эти полосы — самый сильный намёк на существование структуры, поэтому искать новые свидетельства наличия паттерна лучше искать здесь.

(На время мы предположим, что паттерн из полос начинается сразу же после первых четырёх байтов. Визуально это неочевидно, но кажется вероятным, и исследование байтовых значений быстро должно показать нам правду.)

Давайте вернёмся к hex dump, на этот раз сосредоточившись на второй части. Помните, что мы ожидаем найти повторяющийся паттерн немного более высоких значений, равномерно распределённых среди немного более низких значений.

Внимательно посмотрев на последовательность байтов в строке, мы можем увидеть паттерн, по которому первый, четвёртый, седьмой и десятый байт больше, чем его ближайшие соседи. Этот паттерн неидеален, в нём есть исключения, но он определённо достаточно устойчив, чтобы создавать визуальную повторяемость полос, замеченную на всех изображениях. (И его достаточно для подтверждения нашего предположения о том, что паттерн из полос начинается сразу после четырёхбайтного заголовка.)

Постоянство этого паттерна явно предполагает, что эта часть файла является массивом или таблицей, и каждая запись в массиве имеет длину три байта.

Можно настроить формат шестнадцатеричного дампа, чтобы проще увидеть вывод как серию триплетов:

Ещё один стоящий упоминания паттерн, который заметен не сразу: первый байт каждого триплета при движении слева направо увеличивается. Хотя этот паттерн менее заметен, устойчивость его высока; нужно просмотреть много строк, прежде чем мы найдём первое несоответствие. А байты обычно увеличиваются на небольшие значения, однако не представляющие никакого регулярного паттерна.

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

Давайте вернёмся к дампу только первого уровня, чтобы изучить файл целиком:

Если наша теория о маркерах верна, то есть две возможности. Во-первых, возможно, после части с полосами существует некое специальное байтовое значение (сразу после семнадцатого триплета). Во-вторых, вероятно, существует хранимое где-то значение, равное размеру части с полосами. Этот размер может равен числу 17 (то есть обозначает количество триплетов), или 51 (обозначает общее количество байтов в части), или 55 (51 плюс 4, то есть смещение файла, в котором заканчивается эта часть).

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

Для второго варианта очевидно будет поискать индикатор размера в первой части. Узрите — первое 16-битное значение в четырёхбайтном заголовке файла равно 17:

Если наша теория верна, тогда это значение определяет не сам размер части с полосами, а количество трёхбайтных записей. Чтобы проверить эту идею, давайте вернёмся к вычислениям, где мы сравнивали сумму двух 16-битных целочисленных значений с размером файла. На этот раз мы умножим первое число на три, чтобы получить настоящий размер в байтах:

Ага! После этого изменения общая сумма из заголовка всегда точно на четыре меньше размера всего файла данных. А поскольку четыре — это ещё и количество байтов в заголовке, очевидно, что это не совпадение. Первое число даёт нам количество трёхбайтных записей в таблице, а второе число — количество байтов, составлящих оставшуюся часть файла данных.

Мы обнаружили постоянную формулу, а значит, полностью теперь понимаем, что означают числа в первой части.

(Кстати, здесь есть тот самый тайный паттерн, который могли заметить внимательные читатели. При внимательном изучении уравнений становится понятно, что когда файлы имеют одинаковое первое число, у них получается одинаковая разность остатка. Так получается, потому что разность всегда в два раза больше значения первого числа. Это неочевидный паттерн, но кропотливый или удачливый наблюдатель мог бы его заметить.)

Итак, мы можем сказать, что файл имеет три основные части:

Интерпретируем метаданные

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

Но какие же метаданные содержит эта таблица?

Выше мы заметили, что есть пара признаков того, что файл данных может быть сжат. (Теперь это кажется ещё правдоподобнее, ведь мы знаем, что третья часть каждого файла, предположительно содержащая данные каждого уровня, имеет размер всего 100–600 байт.) Если это так, то вполне возможно, что таблица, предваряющая основные данные, содержит метаданные сжатия — некий словарь, применяемый во время распаковки. Например, перед данными, закодированными алгоритмом Хаффмана, обычно есть словарь, сопоставляющий исходные байтовые значения с битовыми последовательностями. Хоть мы и не ожидаем, что эти файлы закодированы алгоритмом Хаффмана (так как данные демонстрируют чёткие паттерны на уровне байтов, то есть вряд ли являются битовым потоком), было бы вполне разумно попробовать интерпретировать эту таблицу как словарь распаковки.

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

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

Теперь мы можем проверить этот скрипт на примере файла данных:

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

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

Взяв эту гипотезу, мы можем увидеть структуру более правдоподобного алгоритма сжатия. Программа берёт исходные данные и сканирует их, ища самые часто встречающиеся двухбайтные последовательности. Затем она заменяет двухбайтную последовательность одним байтовым значением, которое не встречается в данных. Затем она повторяет процесс, продолжая его, пока в данных не найдётся более чем двукратного повторения двухбайтных последовательностей. На самом деле, у такого алгоритма сжатия есть название: он известен как сжатие «re-pair», что является сокращением от «recursive pairs».

(И это может объяснить некоторые паттерны, которые мы видим в словаре. В процессе сжатия словарь строится слева направо, поэтому при распаковке он должен применяться справа налево. Так как записи словаря часто ссылаются на предыдущие записи, логично, что вторые и третьи байты часто будут меньше по значению, чем первый.)

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

Итак, мы можем внести изменение в одну строку программы на Python, чтобы применять словарь справа налево:

Если мы попробуем эту версию, то вывод будет гораздо больше:

Мы видим в этом выводе много нулевых байтов, но это вполне может соответствовать почти пустой карте. Похоже, ненулевые байты сгруппировались рядом друг с другом. Так как мы надеемся найти карту размером 32 × 32, давайте переформатируем вывод в 32 байт на строку:

Внимательно посмотрев на паттерны ненулевых значений, мы увидим, что в выводе чётко видна карта. На самом деле, мы можем сделать этот паттерн более заметным с помощью инструмента «раскрашенного» дампа, который назначает каждому байтовому значению свой цвет, упрощая поиск паттернов повторяющихся значений:

Сравните это с нарисованной фанатами картой первого уровня:

Без сомнений, мы видим данные карты уровня. Можно быть вполне уверенными, что мы верно определили алгоритм распаковки.

Интерпретирование данных

Сравнивая байтовые значения с изображением карты, мы можем определить, что 00 кодирует пустой тайл, 01 кодирует стену, а 23 обозначает чип. 1A обозначает красную дверь, 1B — синюю дверь, и так далее. Мы можем присвоить точные значения чипам, ключам, дверям и всем другим тайлам, из которых состоит вся карта уровня.

Теперь мы можем перейти на следующий уровень и найти байтовые значения для появляющихся там объектов. И продолжить со следующими уровнями, пока не получим полный список байтовых значений и игровых объектов, которые они кодируют.

Как мы изначально и предположили, карта заканчивается ровно после 1024 байт (по смещению 000003FF ).

Сразу же за данными карты идёт последовательность из 384 байт (значения которых находятся в интервале 00000400 – 0000057F ), почти все из которых равны нулю, но между ними попадаются и ненулевые значения. После этого идёт совершенно другой паттерн байтов, поэтому логично будет предположить, что эта 384-байтная последовательность является отдельной частью.

Если мы посмотрим ещё на несколько уровней, то быстро заметим паттерн. 384-байтная часть на самом деле состоит из трёх подразделов, каждый длиной 128 байт. Каждый подраздел начинается с нескольких ненулевых байтов, за которым идут нули, заполняющие остаток подраздела.

У некоторых уровней здесь содержится много данных; у других (например у первого уровня) только самый минимум. Сравнивая уровни с их картами, мы вскоре заметим, что количество данных в этой части файла напрямую связано с количеством «мобов» на уровне. В данном случае в число «мобов» включаются все существа на уровне, блоки земли (которые не движутся самостоятельно, но их можно толкать) и сам главный герой Чип (игрок). То есть мобы указываются не на самой карте, а кодируются в этих трёх буферах.

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

Первый 128-байтный подраздел — это список байтовых значений, определяющих тип моба. Например, буферы второго уровня выглядят так:

Сравните это с картой уровня:

Значение двух других подразделов менее очевидно. Но изучив повторяющиеся значения в этих подразделах и сравнив карты для этих мобов, мы поймём, что байты во втором подразделе хранят координату X каждого моба, а байты в третьем подразделе — координату Y каждого моба. Пониманию этого решения мешает тот факт, что координаты, хранящиеся в этих подразделах, на самом деле сдвинуты на 3 бита влево, т.е. умножены на 8. Этот небольшой факт объясняет «синюю» группу, которую мы обнаружили при переписи значений. (Причины, по которым выполнен этот сдвиг, непонятны, но скорее всего нижние три бита используются для представления анимации, когда мобы двигаются.)

Разобравшись с этой частью, мы можем теперь увидеть, у скольких файлов данных осталось после неё всего несколько байт:

Изучение первой пары байтов в оставшейся части быстро намекает нам, что они содержат ещё одно 16-битное целочисленное значение. Если считать их так, то большинство значений оказывается в десятичной записи круглыми числами:

Если мы снова обратимся к списку, изначально созданному из данных, которые ожидали найти в файлах, то осознаем, что это число — время на прохождение уровня (если значение равно нулю, то на уровне нет ограничения по времени).

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

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

После этого мы достигли конца всех файлов. Теперь у нас есть полное описание схемы данных уровней. Наша задача выполнена.

Незавершённые дела

Внимательный читатель может заметить, что изначально мы ожидали найти в этих файлах ещё два элемента, которые так ни разу и не встретили. Мы объясним отсутствие обоих:

Второй элемент — это четырёхбуквенный пароль уровня. Он не скрыт нигде в данных уровня. К сожалению, этот задачу не решить дальнейшим исследованием файла данных. Мы вынуждены заключить, что пароли просто хранятся где-то в другом месте. Самое вероятное объяснение: они жёстко прописаны где-то в самой программе. Однако позже выяснилось, что пароли не хранятся напрямую. От людей, знакомых с самим кодом, я узнал, что пароли генерируются динамически с помощью генератора псевдослучайных чисел, инициализируемого определённой последовательностью. Следовательно, пароли к уровням невозможно изменять напрямую, это можно сделать только изменением ассемблерного кода.

Послесловие

Выполнив полный реверс-инжиниринг данных в файлах уровней, я мог начать писать программу, способную кодировать и декодировать данные уровней. Благодаря ей я смог создать долгожданный редактор уровней для версии Chip’s Challenge под Lynx, и наличие этого инструмента сильно повысило мои возможности по изучению логики игры, а также улучшило качество её эмуляции.

Но… должен признаться, что лично я выполнял обратную разработку файлов данных не в описанном выше порядке. Я начал с другого конца — с определения строковых данных. Я принялся изучать файлы первых восьми уровней. Так как они называются с «LESSON 1» по «LESSON 8», я искал в них данные одинаковых подстрок. И мне повезло: ни одно из названий этих уровней не подверглось сжатию, поэтому все восемь названий хранятся в файлах данных в исходном виде. Разумеется, меня смутило, что эти строки хранятся не в символах ASCII, но двойная S в названии помогла мне обнаружить паттерн, повторяющийся во всех восьми файлов данных. А найдя название, я узнал кодировку символов букв, цифр и символа пробела. Затем я применил это кодирование к остальной части файла и сразу после названия увидел строки подсказок, и начал наблюдать аномалии:

Великолепная утилита tr упрощает преобразование собственного набора символов файлов данных в ASCII.

Например, в тексте подсказки есть два места, где последовательность из S и пробела заменена на правую скобку. Эти аномалии дали мне достаточно улик, чтобы дедуктивно вычислить наличие сжатия и получить некую информацию о её природе. Позже я связал аномальные байтовые значения с их вхождениями ближе к началу файла данных. (Например, в показанном выше шестнадцатеричном дампе по смещению 00000035 есть правая скобка, за которой следует заглавная S и пробел.) Из этого я вычислил схему сжатия аналогично описанному в статье процессу. Всё остальное было довольно просто.

Мне кажется, из этого можно извлечь такой урок: нет единственно верного способа исследования незнакомого файла данных. Любые инструменты, которые подойдут вам — это подходящие инструменты для реверс-инжиниринга.

Источник