Первый шаг в нужном направлении

Несколько лет спустя, после описанных в предыдущей части событий, в один прекрасный день, мне вспомнились собственно описанные в предыдущей части события, а после этого в мою голову пришел неожиданный (для меня) и довольно очевидный (для остальных) вопрос - а что именно я хотел извлечь из LHX? На что я логично ответил сам себе - а что вообще интересного там есть? Опуская нюансы типа специфических кишок (как вычисляется попадание в противника, код отслеживания карьеры пилота и т.п - ну то есть, собственно, код), остаются, по большому счету, графика (движок + модельки/текстуры) и звук (движок + файлы звуков). Звук меня мало интересовал (в те годы импринтинга у меня даже ковокса не было - я просто не знал о таком) - писк из спикера это всего лишь писк из спикера. А вот графика - да. И я наконец(!) понял, что хочу вытащить из игры именно модельки объектов. 

Итак, модельки.

Предварительный анализ и проверка гипотезы

Начнем с начала, подумал я. Простейшая 3д модель (думал я до итогов реверса этой игры) - это:

1. список точек

2. список полигонов, завязанных на эти точки. 

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

Что такое точка в трехмерной модели? Это последовательность координат - x, y и z. Точек в модели обычно немалое количество, так что для экономии места (напомню, у нас DOS и “640 кб хватит всем” в контексте) их надо как-то оптимизировать. Варианты оптимизации я смог придумать только такие:

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

2. Или просто уменьшить количество точек - что логично, ведь лоу-поли модели не на ровном месте придумали. 

3. Или волевым решением уменьшить количество возможных вариантов значений координаты, применив, например, фирменную фишку тех лет - использовать один байт (который восьмибитный и имеет 256 вариантов значений) вместо двух байт ака слово ака integer тех лет (он был тогда 16-битный и имел 65536 вариантов значений). Это кратно уменьшает объем данных.

Таким образом, я предположил, что список точек модели - это не заархивированная (пункт 1) последовательность байт (а не слов, которые = 2 байта, см. пункт 3), каждый из которых является значением координаты точки по определенной оси. То есть, проще говоря, где-то в файле идет поток байтов, который надо трактовать как x1 y1 z1 x2 y2 z2 x3 y3 z3 и т.д.

Смотреть на модельку и искать в файле высмотренные последовательности (как в случае с цветами пикселей у спрайтов), очевидно, не получится. Поэтому единственный способ поиска, который у меня оставался на руках - это “испорти и посмотри”. Если я испорчу файл в том месте, где находится этот поток байт, то, очевидно, что у каких-то полигонов модельки исказятся значения вершин, и все это будет выглядеть в игре довольно несуразно. Так и вышло. Но не сразу. 

Файл тупо большой для рандомного воздействия, распакованный размер - больше 300 килобайт. 300 000 точек приложения усилий. Опять же - проверка на предмет того, то ли было испорчено, тоже довольно затратна - запусти игру, доберись до нужного места, проверь (это DOS игра, в ней модельки трехмерные, а вот внутриигровой просмотр - только с определенных точек зрения, можно и упустить нюансы-то)… Так что нужна была бОльшая прицельность. Я предположил, что портить данные надо, скорее всего, в окрестности упомянутых в прошлый раз названий техники. Ну и выбрал целью приложения усилий su25 (вот и пригодились детские наблюдения). 

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

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

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

Но это были мелочи - дело наконец сдвинулось с многолетней мертвой точки.

Интермедия

Где-то с этого момента начинается тема инструментов для проводимого мной вскрытия. В винде по умолчанию на удивление сложно с редактированием байтового содержимого файлов. В DOS это тоже из коробки не шло, но там вообще-то вся операционка весила 70-80 килобайт, и состояла из трех файлов.

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

Первый - wxHexEditor - простенький, но неплохо размечал блоки, хотя между сессиями работы разметка то ли ломалась, то ли вообще не сохранялась. 

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

Еще порой использовал HxD, но в нем нету разметки. 

Сейчас для редактирования байтов я обошелся бы одним лишь ImHex, скорее всего.

Вновь к станку и немного безумия.

Напомню, что к этому моменту я уже нашел внутри игрового экзешника байт, описывающий одну координату одной из точек одной модели самолета Су-25 из игры LHX.

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

Сразу же выявилось странное для меня поведение - изменение значений байта, который описывал координату высоты точки, приводила к неочевидному изменению положения этой точки в игре. Очевидным я считаю поведение “чем больше значение координаты z - тем выше точка, и чем меньше - тем ниже”). 

В игре же - при изменении значения этого байта от 0x00 до 0x7F (0x.. обозначает, что число за ним записано в шестнадцатеричной форме, если кто не знал - в десятичной записи это изменение от 0 до 127) высота точки росла от середины модели и выше, а при дальнейшем изменении от 0x80 до 0xFF (значения 128 - 255) эта точка перещелкивалась по оси 0z в самый низ модели и росла к ее середине, останавливаясь в этой самой середине при значении 0xFF (собственно 255). Признаться, я поначалу подумал недоброе, но пороговое значение 0x80 быстро подсказало мне, что программа считает этот байт не простым, а знаковым - так как у байта, начиная со значения 0x80 и заканчивая 0xFF, последний (он же восьмой, он же старший) бит становится равен 1 - и для процессора (если он в курсе, что этот байт описывает знаковое число) это признак знака минус (потому и знаковый) у числа, которое он описывает.

А неожиданный рост координаты от низа модели к середине, а не ожидаемый от середины к низу (ведь значения 0x80 - 0xFF - отрицательные в случае знакового типа) объясняется тем, что в знаковых числах не совсем уж доисторических компов отрицательные значения записываются не в простом бинарном виде, а в виде дополнительного кода. Это все я узнал через википедию и то, что описанные дальше вещи не взорвали мне мозг, я считаю немалой своей победой. Поэтому вещи под катом - на свой страх и риск.

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

И 10 минут гуглежа привели меня к этому самому прекрасному (тут никакой иронии) инструменту.

Интермедия 2

Называется он Kaitai Struct. У него есть DSL-язык для описания структур (с незначительными ограничениями, но они заметны только в очень специфических случаях), основанный на YAML; у него есть web IDE, в которой можно редактировать DSL-описание и загружать куски байтового содержимого - и оно будет переработано и показано согласно правилам (или не будет, если он напорется на несоответствие байтового потока и его DSL-описания); и у него есть конвертеры из DSL-описания в код парсера для нескольких языков - и я этим всем активно пользовался. Этот инструмент - он именно для описания хитрых и сложных структур данных со всякими там вложенностями, байтовыми или просто размерами и всем таким прочим. Конечно, есть и другие инструменты такой направленности (в том же ImHex есть инструменты для этого), но пользовался я именно этим, и вполне успешно. И далее для описания структур буду пользоваться его синтаксисом.

Набирая обороты

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

Таким образом, я узнал, что в такой-то области экзешника лежит последовательность байт, представляющих значения координат двух наборов точек. Я даже узнал, что первая последовательность из них начинается сразу же после завершающего нуля строки с названием объекта (так как строка, естественно, null-terminated), что удобно. (а моя гипотеза оказалась верна, что приятно). Но я еще не знал, сколько байт брать - а это определялось количеством моделек (не для всех объектов в игре есть две модели) и количеством точек в них. Конечно же, ковыряя байты и постоянно запуская порченный экзешник можно было бы путем проб и ошибок определить все наборы, но...

Тут стоит упомянуть о том, что от Ida я все же не отворачивался. Хотя бы потому что изначально в роли hex-редактора выступала именно она. Так вот, Ida при загрузке распакованного экзешника разбивала его аж на 101 сегмент (и я вообще без понятия на основании чего и как она это сделала, и что такое сегменты - я тоже не знал(ю)). И как-то так вышло, что довольно много сегментов содержали то самое название объекта где-то в середине себя, и некоторые из них кончались как раз на байте с последней координатой последней точки модели. Порой концы выставленных Идой сегментов плавали (начинались/кончались немного раньше/позже ожидаемых мест), но идею я ухватил. И посмотрел в начало сегмента, описывающего su25. Почти в самом начале сегмента стояло четыре нуля (как и в других сегментах с названиями объектов), а перед ними - ещё 2 байта. И второй байт из них содержал значение, равное количеству точек в наборе для лоу-поли модели. Тут я еще внимательней присмотрелся к листингу сегмента и увидел, наконец, метки вида "unk_XXXXX" и комментарии "DATA XREF: XXXXXXXX".

Напомню, я сознательно решил не изучать все, что связано с реверсом кода - поэтому просто принял как данность то, что Ida нашла какие-то точки в коде, на которые ссылаются из других точек и проставила соответствующие метки и комментарии на обоих концах ссылки. Я переименовал метки, посидел-покумекал, посчитал байтики в калькуляторе - и вот что получил. 

В некоторых случаях (и su25 оказался таким случаем, тут мне опять повезло с выбором) сегмент, который выделила Ida, содержал в себе последовательность вида:

1. какой-то 1 байт

2. ещё 1 байт, содержащий количество точек лоу-поли

3. ссылка на адрес старта списка лоу-поли точек (это вот те самые 4 нуля и еще 4 байта за ними, которые равны адресу внутри дампа экзешника)

4. непонятная куча каких-то байт (порченье которых обычно приводило к незапуску экзешника) номер 1 (вообще, "непоймичто номер 1", оказывается, довольно частое явление в реверсе - я сверялся с инетом)

5. 1 байт = количество точек хай-поли

6. ссылка на адрес старта списка хай-поли точек (опять же, через 4 нуля и 4 байта адреса)

7. непонятная куча каких-то байт номер 2

8. набор байт, которые оканчиваются машинным нулем = null-terminated строка с названием объекта

9. список лоу-поли точек, длина списка уже известна

10. список хай-поли точек, длина списка уже известна

meta:
  id: lhx_points
  endian: le

seq:
 -id: unknownByte
  type: u1
 -id: low_poly_dots_number
  type: u1
 -id: xref_jump_to_low_poly_dots
  type: xref_jump
 -id: unknownByteHeap1
  size: ??? - ВОТ ИЗ-ЗА ЭТОГО ЭТО ОПИСАНИЕ НЕ БУДЕТ РАБОТАТЬ
 -id: high_poly_dots_number
  type: u1
 -id: xref_jump_to_high_poly_dots
  type: xref_jump
 -id: unknownByteHeap2
  size: ??? - И ИЗ-ЗА ЭТОГО
 -id: object_name
  type: str
 -id: low_poly_dots
  type: dotcloud
  size: low_poly_dots_number
 -id: high_poly_dots
  type: dotcloud
  size: high_poly_dots_number

types:
 xref_jump:
  seq:
   -id: xref_signature
    contents: [0x00, 0x00, 0x00, 0x00]
   -id: in_exe_address
    size: u4
 dotcloud:
  seq:
   - id: dots
     type: dot
     repeat: eos
 dot:
  seq:
   - id: x
     type: s1
   - id: z
     type: s1
   - id: y
     type: s1

Я, конечно же, сразу скопировал облако точек лоу-поли модели в Mathematica чтобы насладиться зрелищем убедиться что я был прав. Я был прав.

Но не все было радужно. Для каких-то сегментов не было ссылок на хай-поли точки (и на непонятные кучи каких-то байт за ними), для каких-то - ссылка на точки была пуста, просто 0000. А для каких-то объектов не было сегментов вообще в принципе.

Что ж, по одной проблеме за раз.