[Перевод] Введение в реверс-инжиниринг: взламываем формат данных игры
Введение
Реверс-инжиниринг незнакомого файла данных можно описать как процесс постепенного понимания. Он во многом напоминает научный метод, только применённый к созданным человеком абстрактным объектам, а не к миру природы. Мы начинаем со сбора данных, а затем используем эту информацию для выдвижения одной или нескольких гипотез. Проверяем гипотезы и применяем результаты этих проверок для их уточнения. При необходимости повторяем процесс.
Развитие навыков реверс-инжиниринга — в основном вопрос практики. Накапливая опыт, вы выстраиваете интуитивное понимание того, что нужно исследовать в первую очередь, какие паттерны необходимо искать, и какие инструменты удобнее использовать.
В этой статье я подробно расскажу о процессе обратной разработки файлов данных из старой компьютерной игры, чтобы продемонстрировать, как это делается.
Небольшая предыстория
Всё это началось, когда я пытался воссоздать игру Chip’s Challenge на Linux.
Изначально Chip’s Challenge была выпущена в 1989 году для ныне забытой портативной консоли Atari Lynx. Для того времени Atari Lynx была впечатляющей машиной, но она вышла в одно время с Nintendo Game Boy, которая в конце концов захватила рынок.
Chip’s Challenge — это игра-головоломка с видом сверху и тайловой картой. Как и в большинстве таких игр, цель каждого уровня заключается в том, чтобы добраться до выхода. В большей части уровней выход охраняется разъёмом для чипа, который можно миновать, только собрав определённое количество компьютерных чипов.
Видео: Atari Lynx в действии, прохождение первого уровня.
Новая игра начинается с первого уровня под названием «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.
Файлы данных
Вот ссылка на tarball каталога, содержащего все файлы данных. Я даю её на случай, если вы захотите повторять за мной все шаги, описанные в этой статье, или попытаетесь самостоятельно декодировать файлы данных.
Законно ли это? Хороший вопрос. Поскольку эти файлы являются только небольшой частью программы для MS-DOS, и сами по себе они бесполезны, и поскольку я выкладываю их только в образовательных целях, то полагаю, что это подпадает под требованиях добросовестного использования (fair use). Надеюсь, со мной согласятся все заинтересованные стороны. (Если же я всё-таки получу от юристов письмо с угрозами, то могу изменить статью так, чтобы изложить файлы данных в забавном ключе, а затем заявить, что это пародия.)
Предварительные требования
Я буду считать, что вы знаете шестнадцатеричное исчисление, пусть даже и не владеете декодированием шестнадцатеричных значений, а также что вы немного знакомы с командной оболочкой (shell) Unix. Показанная в этой статье сессия оболочки выполняется на стандартной системе Linux, но почти используемые команды являются распространёнными утилитами Unix, и широко распространены на других Unix-подобных системах.
Первый взгляд
Вот листинг каталога, содержащего файлы данных из порта под MS-DOS:
$ ls levels all_full.pak cake_wal.pak eeny_min.pak iceberg.pak lesson_5.pak mulligan.pak playtime.pak southpol.pak totally_.pak alphabet.pak castle_m.pak elementa.pak ice_cube.pak lesson_6.pak nice_day.pak potpourr.pak special.pak traffic_.pak amsterda.pak catacomb.pak fireflie.pak icedeath.pak lesson_7.pak nightmar.pak problems.pak spirals.pak trinity.pak apartmen.pak cellbloc.pak firetrap.pak icehouse.pak lesson_8.pak now_you_.pak refracti.pak spooks.pak trust_me.pak arcticfl.pak chchchip.pak floorgas.pak invincib.pak lobster_.pak nuts_and.pak reverse_.pak steam.pak undergro.pak balls_o_.pak chiller.pak forced_e.pak i.pak lock_blo.pak on_the_r.pak rink.pak stripes.pak up_the_b.pak beware_o.pak chipmine.pak force_fi.pak i_slide.pak loop_aro.pak oorto_ge.pak roadsign.pak suicide.pak vanishin.pak blink.pak citybloc.pak force_sq.pak jailer.pak memory.pak open_que.pak sampler.pak telebloc.pak victim.pak blobdanc.pak colony.pak fortune_.pak jumping_.pak metastab.pak oversea_.pak scavenge.pak telenet.pak vortex.pak blobnet.pak corridor.pak four_ple.pak kablam.pak mind_blo.pak pain.pak scoundre.pak t_fair.pak wars.pak block_fa.pak cypher.pak four_squ.pak knot.pak mishmesh.pak paranoia.pak seeing_s.pak the_last.pak writers_.pak block_ii.pak deceptio.pak glut.pak ladder.pak miss_dir.pak partial_.pak short_ci.pak the_mars.pak yorkhous.pak block_n_.pak deepfree.pak goldkey.pak lemmings.pak mixed_nu.pak pentagra.pak shrinkin.pak the_pris.pak block_ou.pak digdirt.pak go_with_.pak lesson_1.pak mix_up.pak perfect_.pak skelzie.pak three_do.pak block.pak digger.pak grail.pak lesson_2.pak monster_.pak pier_sev.pak slide_st.pak time_lap.pak bounce_c.pak doublema.pak hidden_d.pak lesson_3.pak morton.pak ping_pon.pak slo_mo.pak torturec.pak brushfir.pak drawn_an.pak hunt.pak lesson_4.pak mugger_s.pak playhous.pak socialis.pak tossed_s.pak
Как видите, все файлы заканчиваются на .pak. .pak является стандартным разрешением для файла данных приложений, и это, к сожалению, не даёт нам никакой информации о его внутренней структуре. Названия файлов — это первые восемь символов названия уровня, за некоторыми исключениями. (Например, в названиях файлов уровней «BLOCK BUSTER» и «BLOCK BUSTER II» опущено слово «buster», чтобы они не совпадали.)
$ ls levels | wc
17 148 1974
В каталоге находится 148 файлов данных, и в игре на самом деле ровно 148 уровней, так что тут всё совпадает.
Теперь давайте изучим, что же представляют собой эти файлы. xxd — это стандартная утилита для дампа шестнадцатеричных данных (hexdump). Давайте посмотрим, как выглядит внутри «LESSON 1».
$ xxd levels/lesson_1.pak 00000000: 1100 cb00 0200 0004 0202 0504 0407 0505 ................ 00000010: 0807 0709 0001 0a01 010b 0808 0d0a 0a11 ................ 00000020: 0023 1509 0718 0200 2209 0d26 0911 270b .#......"..&..'. 00000030: 0b28 0705 291e 0127 2705 020d 0122 0704 .(..)..''....".. 00000040: 0902 090a 0215 0426 0925 0111 1502 221d .......&.%....". 00000050: 0124 011d 0d01 0709 0020 001b 0400 1a00 .$....... ...... 00000060: 2015 2609 1f00 3300 2911 1522 2302 110d .&...3.).."#... 00000070: 0107 2609 1f18 2911 1509 181a 0223 021b ..&...)......#.. 00000080: 0215 2201 1c01 1c0d 0a07 0409 0201 0201 .."............. 00000090: 2826 0123 1505 0902 0121 1505 220a 2727 (&.#.....!..".'' 000000a0: 0b05 0400 060b 0828 0418 780b 0828 0418 .......(..x..(.. 000000b0: 700b 0828 0418 6400 1710 1e1e 1a19 0103 p..(..d......... 000000c0: 000e 1a17 1710 0e1f 010e 1314 1b29 1f1a .............).. 000000d0: 0012 101f 011b 0c1e 1f01 1f13 1001 0e13 ................ 000000e0: 141b 001e 1a0e 1610 1f2d 0020 1e10 0116 .........-. .... 000000f0: 1024 291f 1a01 1a1b 1019 000f 1a1a 1d1e .$)............. 00000100: 2d02
Что такое утилита для создания hexdump? Шестнадцатеричный дамп — это стандартный способ отображения точных байтов двоичного файла. Большинство байтовых значений нельзя связать с печатными символами ASCII, или они имеют непонятный внешний вид (например символ табуляции). В шестнадцатеричном дампе отдельные байты выводятся в виде численных значений. Значения отображаются в шестнадцатеричном виде, отсюда и название. В показанном выше примере в одной строке вывода отображается 16 байт. Самый левый столбец показывает позицию строки в файле, тоже в шестнадцатеричном виде, поэтому в каждой строке число увеличивается на 16. Байты отображаются в восемь столбцов, и в каждом столбце отображается по два байта. Справа в hexdump показывается, как бы выглядели байты при отображении символами, только все непечатаемые значения ASCII заменены точками. Это упрощает нахождение строк, которые могут быть встроены в двоичный файл.
Очевидно, что реверс-инжиниринг этих файлов не будет сводиться к обычному просмотру содержимого и изучению того, что там видно. Пока здесь нет ничего не говорит нам о том, какие функции выполняют данные.
Что мы ожидаем увидеть?
Давайте сделаем шаг назад и проясним ситуацию: какие конкретно данные мы ожидаем найти в этих файлах данных?
Самое очевидное — это некая «карта» уровня: данные, обозначающие позиции стен и дверей, а также всего остального, что делает уровень уникальным.
(К счастью для нас, фанаты игры проделали кропотливую работу и собрали полные карты для всех 148 уровней, поэтому мы можем использовать их, чтобы знать, что должно находиться на каждой карте.)
В дополнение к карте у каждого уровня должно быть несколько других атрибутов. Например, можно заметить, что у каждого уровня есть название, например «LESSON 1», «PERFECT MATCH», «DRAWN AND QUARTERED», и так далее. У разных уровней также есть разные ограничения по времени, поэтому можно предположить, что эта информация тоже содержится в данных. Кроме того, на каждом уровне есть собственное число собираемых чипов. (Мы могли бы предположить, что это число просто соответствует количеству чипов на уровне, но оказывается, что на некоторых уровнях содержится больше чипов, чем нужно для открытия разъёма чипов. Хотя бы для этих уровней минимальное количество должно указываться в явной форме.)
Ещё один фрагмент данных, который мы ожидаем найти в данных уровня — это текст подсказок. На некоторых уровнях есть «кнопка подсказки» — лежащий на земле большой вопросительный знак. Когда Чип встаёт на него, показывается текст подсказки. Кнопка подсказки есть примерно на 20 уровнях.
Наконец, у каждого уровня есть пароль — последовательность из четырёх букв, позволяющая игроку продолжить игру с этого уровня. (Этот пароль необходим, потому что в Lynx нет хранилища данных. Сохранять на консоли игры было нельзя, поэтому продолжать игру после включения консоли можно было с помощью паролей.)
Итак, вот наш список нужных данных:
- Карта уровня
- Название уровня
- Пароль уровня
- Ограничение времени
- Количество чипов
- Текст подсказки
Давайте примерно оценим общий размер данных. Проще всего определить ограничение по времени и количество чипов. Оба эти параметра могут иметь значения в интервале от 0 до 999, поэтому они скорее всего хранятся в виде целочисленных значений общим размером 4 байта. Пароль всегда состоит из четырёх букв, поэтому скорее всего хранится как ещё четыре байта, то есть всего 8 байт. Длина названий уровней варьируется от четырёх до девятнадцати символов. Если мы предположим, что нужен ещё один байт для завершения строки, то это двадцать байт, то есть промежуточный итог составляет 28 байт. Самый длинный текст подсказки имеет размер более 80 байт; если мы округлим это значение до 90, то в сумме получим 118 байт.
А что насчёт схемы уровня? Большинство уровней имеет размер 32 × 32 тайлов. Уровней большего размера не существует. Некоторые уровни меньше, но будет логично предположить, что они просто встроены в карту размером 32 × 32. Если предположить, что на один тайл карте требуется один байт, то для полной схемы нужно 1024 байта. То есть в целом мы получаем приблизительную оценку в 1142 байта на каждый уровень. Разумеется, это всего лишь грубая первоначальная прикидка. Вполне возможно, что некоторые из этих элементов хранятся иначе, или вообще не хранятся внутри файлов уровней. Или в них могут находиться другие данные, которые мы не заметили или не знаем о них. Но пока мы заложили неплохую основу.
Определившись с тем, что мы ожидаем увидеть в файлах данных, давайте вернёмся к изучению того, что же на самом деле в них содержится.
Что там есть и чего нет
Хотя на первый взгляд файл данных выглядит совершенно непонятно, в нём всё равно можно заметить пару моментов. Во-первых, это то, чего мы не видим. Например, мы не видим названия уровня или текста подсказок. Можно понять, что это не совпадение, изучив и другие файлы:
$ strings levels/* | less :!!;# &>''::4# .,,! -54"; /&67 !)60 <171 *(0* 82>'=/ 8><171&& 9>#2')( , )9 0hX `@PX )""* 24**5 ;))< B777:..22C1 E,,F -GDED EGFF16G;;H< IECJ 9K444 =MBBB>>N9"O"9P3?Q lines 1-24/1544 (more)
Здесь ничего не видно, кроме произвольных фрагментов ASCII-мусора.
Предположительно, где-то в этих файлах есть названия уровней и подсказки, но они или хранятся не в ASCII, или претерпели некую трансформацию (например, из-за сжатия).
Стоит также заметить следующее: файл едва дотягивает по размеру до 256 байт. Это довольно мало, учитывая, что изначально мы оценили его размер более чем в 1140 байт.
Опция -S сортирует файлы по убыванию размера.
$ ls -lS levels | head total 592 -rw-r--r-- 1 breadbox breadbox 680 Jun 23 2015 mulligan.pak -rw-r--r-- 1 breadbox breadbox 675 Jun 23 2015 shrinkin.pak -rw-r--r-- 1 breadbox breadbox 671 Jun 23 2015 balls_o_.pak -rw-r--r-- 1 breadbox breadbox 648 Jun 23 2015 cake_wal.pak -rw-r--r-- 1 breadbox breadbox 647 Jun 23 2015 citybloc.pak -rw-r--r-- 1 breadbox breadbox 639 Jun 23 2015 four_ple.pak -rw-r--r-- 1 breadbox breadbox 636 Jun 23 2015 trust_me.pak -rw-r--r-- 1 breadbox breadbox 625 Jun 23 2015 block_n_.pak -rw-r--r-- 1 breadbox breadbox 622 Jun 23 2015 mix_up.pak
Самый большой файл занимает всего 680 байт, и это не очень много. А каким будет самый маленький?
Опция -r сообщает ls, что нужно обратить порядок.
$ ls -lSr levels | head total 592 -rw-r--r-- 1 breadbox breadbox 206 Jun 23 2015 kablam.pak -rw-r--r-- 1 breadbox breadbox 214 Jun 23 2015 fortune_.pak -rw-r--r-- 1 breadbox breadbox 219 Jun 23 2015 digdirt.pak -rw-r--r-- 1 breadbox breadbox 226 Jun 23 2015 lesson_2.pak -rw-r--r-- 1 breadbox breadbox 229 Jun 23 2015 lesson_8.pak -rw-r--r-- 1 breadbox breadbox 237 Jun 23 2015 partial_.pak -rw-r--r-- 1 breadbox breadbox 239 Jun 23 2015 knot.pak -rw-r--r-- 1 breadbox breadbox 247 Jun 23 2015 cellbloc.pak -rw-r--r-- 1 breadbox breadbox 248 Jun 23 2015 torturec.pak
Самый мелкий файл занимает всего 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 байтов и поискать в них выделяющиеся паттерны:
$ for f in levels/* ; do xxd $f | sed -n 1p ; done | less 00000000: 2300 dc01 0300 0004 0101 0a03 030b 2323 #.............## 00000000: 2d00 bf01 0300 0015 0101 2203 0329 2222 -........."..)"" 00000000: 2b00 a101 0301 0105 0000 0601 0207 0505 +............... 00000000: 1d00 d300 0200 0003 0101 0402 0205 0102 ................ 00000000: 2d00 7a01 0300 0006 1414 0701 0109 0303 -.z............. 00000000: 3100 0802 0200 0003 0101 0502 0206 1313 1............... 00000000: 1a00 b700 0200 0003 0100 0502 0206 0101 ................ 00000000: 1a00 0601 0300 0005 0001 0601 0107 0303 ................ 00000000: 2000 7a01 0200 0003 0202 0401 0105 0028 .z............( 00000000: 3a00 a400 0200 0003 2828 0428 0205 0303 :.......((.(.... 00000000: 2600 da00 0300 0004 0507 0901 010a 0303 &............... 00000000: 2400 f000 0300 0004 0303 0504 0407 0101 $............... 00000000: 2a00 ef01 0300 0005 0101 0614 0007 0303 *............... 00000000: 2c00 8c01 0300 0004 0303 0500 0107 0101 ,............... 00000000: 2a00 0001 0300 0004 0303 0501 0107 0404 *............... 00000000: 1b00 6d01 0200 0003 0101 0502 0206 0003 ..m............. 00000000: 1e00 1701 0200 0003 0202 0401 0105 0013 ................ 00000000: 3200 ee01 0f00 0015 0101 270f 0f29 1414 2.........'..).. 00000000: 2a00 5b01 0300 0005 0303 0601 0107 1414 *.[............. 00000000: 2c00 8a01 0200 0003 0202 0401 0105 0303 ,............... 00000000: 1d00 9c00 0216 1604 0000 0516 0107 0205 ................ 00000000: 2000 e100 0200 0003 0101 0402 0205 0303 ............... 00000000: 2000 2601 0300 0004 0303 0502 0207 0101 .&............. 00000000: 1f00 f600 0132 0403 0000 0532 3206 0404 .....2.....22... lines 1-24/148 (more)
Просмотрев этот дамп, можно заметить, что в каждом столбце возникают некие схожие значения.
Начав с первого байта, мы вскоре осознаём, что его значение находится в очень ограниченном интервале значений, в пределах шестнадцатеричных 10–40 (или примерно 20–60 в десятичном исчислении). Это довольно специфичная особенность.
Ещё интереснее то, что второй байт каждого файла всегда равен нулю, без исключений. Вероятно, второй байт не используется, или является заполнителем. Однако есть и другая вероятность — эти первые два байта вместе обозначают 16-битное значение, хранящееся в порядке little-endian.
Что такое little-endian? При сохранении численного значения, которое больше одного байта, нужно заранее выбрать порядок, в котором будут храниться байты. Если сначала вы сохраняете байт, представляющий меньшую часть числа, то это называется прямым порядком (little-endian); если вы сначала сохраняете байты, обозначающие бОльшую часть числа, то это обратный порядок (big-endian). Например, десятичные значения мы записываем в обратном порядке (big-endian): строка »42» означает «сорок два», а не «четыре и двадцать». Little-endian — это естественный порядок для многих семейств микропроцессоров, поэтому он обычно более популярен, за исключением сетевых протоколов, в которых обычно требуется big-endian.
Если мы продолжим анализ, то вскоре увидим, что третий байт в файле не похож на два предыдущих: его значение меняется в широком диапазоне. Однако четвёртый байт всегда равен 00, 01 или 02, и 01 встречается чаще всего. Это тоже намекает нам, что эти два байта составляют ещё одно 16-битное значение, находящееся примерно в интервале десятичных значений 0–700. Эту гипотезу можно подтвердить ещё и тем, что значение третьего байта обычно низко, если значение четвёртого равно 02, и обычно велико, если четвёртый байт равен 00.
Кстати, стоит заметить, что это частично причина того, что стандартно формат шестнадцатеричного дампа отображает байты по парам — так упрощается чтение последовательности 16-битных целочисленных чисел. Формат шестнадцатеричного дампа был стандартизован, когда в ходу были 16-битные компьютеры. Попробуйте заменить xxd на xxd -g1, чтобы полностью отключить группирование, и вы заметите, что распознавание пар байтов посередине строки требует больших усилий. Это простой пример того, как инструменты, используемые для изучения незнакомых данных, склоняют нас замечать определённые типы паттернов. Хорошо, что по умолчанию xxd выделяет этот паттерн, потому что он очень распространён (даже сегодня, когда повсюду используются 64-битные компьютеры). Но полезно и знать, как изменить эти параметры, если они не помогают.
Давайте продолжим визуальное исследование, и посмотрим, сохраняется ли этот паттерн из 16-битных целочисленных значений. Пятый байт обычно имеет очень низкие значения: чаще всего встречаются 02 и 03, а максимальным значением кажется является 05. Шестой байт файла очень часто равен нулю —, но подчас он содержит гораздо большие значения, например 32 или 2C. В этой паре наше предположение о распределённых в интервале значениях не особо подтверждается.
Внимательнее изучаем исходные значения
Мы можем проверить свою догадку, использовав od для генерации шестнадцатеричного дампа. Утилита od похожа xxd, но обеспечивает гораздо больший выбор форматов вывода. Мы можем использовать её, чтобы сдампить вывод в виде 16-битных десятеричных целых чисел:
Опция -t утилиты od указывает формат вывода. В данном случае u обозначает беззнаковые десятеричные числа, а 2 обозначает два байта на запись. (Также этот формат можно задать с помощью опции -d.)
$ for f in levels/* ; do od -tu2 $f | sed -n 1p ; done | less 0000000 35 476 3 1024 257 778 2819 8995 0000000 45 447 3 5376 257 802 10499 8738 0000000 43 417 259 1281 0 262 1794 1285 0000000 29 211 2 768 257 516 1282 513 0000000 45 378 3 1536 5140 263 2305 771 0000000 49 520 2 768 257 517 1538 4883 0000000 26 183 2 768 1 517 1538 257 0000000 26 262 3 1280 256 262 1793 771 0000000 32 378 2 768 514 260 1281 10240 0000000 58 164 2 768 10280 10244 1282 771 0000000 38 218 3 1024 1797 265 2561 771 0000000 36 240 3 1024 771 1029 1796 257 0000000 42 495 3 1280 257 5126 1792 771 0000000 44 396 3 1024 771 5 1793 257 0000000 42 256 3 1024 771 261 1793 1028 0000000 27 365 2 768 257 517 1538 768 0000000 30 279 2 768 514 260 1281 4864 0000000 50 494 15 5376 257 3879 10511 5140 0000000 42 347 3 1280 771 262 1793 5140 0000000 44 394 2 768 514 260 1281 771 0000000 29 156 5634 1046 0 5637 1793 1282 0000000 32 225 2 768 257 516 1282 771 0000000 32 294 3 1024 771 517 1794 257 0000000 31 246 12801 772 0 12805 1586 1028 lines 1-24/148 (more)
Эти выходные данные показывают, что наши догадки о первых нескольких байтах были верными. Мы видим, что первое 16-битное значение находится в десятеричном интервале 20–70, а второе 16-битное значение — в десятеричном интервале 100–600. Однако последующие значения ведут себя не так хорошо. В них проявляются определённые паттерны (например, в четвёртой позиции на удивление часто встречается 1024), но они не обладают повторяемостью, свойственной первым значениям файла.
Поэтому давайте предварительно допустим, что первые четыре байта файла особые и состоят из двух 16-битных значений. Так как они находятся в самом начале файла, то скорее всего являются метаданными и помогают определить, как считывать остальную часть файла.
На самом деле, второй интервал значений (100–600) довольно близок к замеченному нами ранее интервалу размеров файлов (208–680). Возможно, это не совпадение? Давайте выдвинем гипотезу: хранящееся в третьем и четвёртом байтах файла 16-битное значение коррелирует с общим размером файла. Теперь, когда у нас есть гипотеза, мы можем её проверить. Посмотрим, действительно ли у больших файлов в этом месте постоянно большие значения, а у маленьких — маленькие.
Для отображения размера файла в байтах без всякой другой информации можно использовать wc с опцией -c. Аналогично, можно добавить к od опции, позволяющие выводить только интересующие нас значения. Затем мы можем использовать подстановку команд для записи этих значений в переменные оболочки и отобразить их вместе:
Опция -An утилиты od отключает самую левый столбец, в котором отображается смещение в файле, а -N4 приказывает od остановиться после первых 4 байтов файла.
$ for f in levels/* ; do size=$(wc -c <$f) ; data=$(od -tuS -An -N4 $f) ; echo "$size: $data" ; done | less 585: 35 476 586: 45 447 550: 43 417 302: 29 211 517: 45 378 671: 49 520 265: 26 183 344: 26 262 478: 32 378 342: 58 164 336: 38 218 352: 36 240 625: 42 495 532: 44 396 386: 42 256 450: 27 365 373: 30 279 648: 50 494 477: 42 347 530: 44 394 247: 29 156 325: 32 225 394: 32 294 343: 31 246
Посмотрев на эти выходные данные, можно увидеть, что значения приблизительно коррелируют. Меньшие файлы обычно имеют во второй позиции меньшие значения, а большие файлы — большие значения. Однако корреляция не точная, и стоит заметить, что размер файла всегда значительно больше, чем хранящееся в нём значение.
Кроме того, первое 16-битное значение тоже обычно бывает больше при больших размерах файлов, но совпадение тоже не совсем полное, и можно легко найти примеры файлов среднего размера с относительно большими значениями в первой позиции. Но возможно если мы сложим эти два значения, их сумма будет лучше коррелировать с размером файла?
Мы можем использовать read для извлечения двух чисел из выходных данных od в отдельные переменные, а затем использовать арифметику командной оболочки для нахождения их суммы:
Команда оболочки read не может использоваться с правой части вертикальной черты, потому что переданные в конвейер команды выполняются в дочернем командном процессоре (subshell), который при выходе берёт с собой свои переменные окружения в битоприёмник. Поэтому вместо этого нам необходимо воспользоваться функцией подстановки процессов bash и направить вывод od во временный файл, который затем можно перенаправить в команду read.
$ for f in levels/* ; do size=$(wc -c <$f) ; read v1 v2 < <(od -tuS -An -N4 $f) ; sum=$(($v1 + $v2)) ;
echo "$size: $v1 + $v2 = $sum" ; done | less
585: 35 + 476 = 511
586: 45 + 447 = 492
550: 43 + 417 = 460
302: 29 + 211 = 240
517: 45 + 378 = 423
671: 49 + 520 = 569
265: 26 + 183 = 209
344: 26 + 262 = 288
478: 32 + 378 = 410
342: 58 + 164 = 222
336: 38 + 218 = 256
352: 36 + 240 = 276
625: 42 + 495 = 537
532: 44 + 396 = 440
386: 42 + 256 = 298
450: 27 + 365 = 392
373: 30 + 279 = 309
648: 50 + 494 = 544
477: 42 + 347 = 389
530: 44 + 394 = 438
247: 29 + 156 = 185
325: 32 + 225 = 257
394: 32 + 294 = 326
343: 31 + 246 = 277
lines 1-24/148 (more)
Сумма двух числе тоже приблизительно коррелирует с размером файла, но они всё равно не совсем совпадают. Насколько же они отличаются? Давайте продемонстрируем их разность:
$ for f in levels/* ; do size=$(wc -c <$f) ; read v1 v2 < <(od -tuS -An -N4 $f) ; diff=$(($size - $v1 - $v2)) ;
echo "$size = $v1 + $v2 + $diff" ; done | less
585 = 35 + 476 + 74
586 = 45 + 447 + 94
550 = 43 + 417 + 90
302 = 29 + 211 + 62
517 = 45 + 378 + 94
671 = 49 + 520 + 102
265 = 26 + 183 + 56
344 = 26 + 262 + 56
478 = 32 + 378 + 68
342 = 58 + 164 + 120
336 = 38 + 218 + 80
352 = 36 + 240 + 76
625 = 42 + 495 + 88
532 = 44 + 396 + 92
386 = 42 + 256 + 88
450 = 27 + 365 + 58
373 = 30 + 279 + 64
648 = 50 + 494 + 104
477 = 42 + 347 + 88
530 = 44 + 394 + 92
247 = 29 + 156 + 62
325 = 32 + 225 + 68
394 = 32 + 294 + 68
343 = 31 + 246 + 66
lines 1-24/148 (more)
Разность, или значение «остатка», отображается в самой правой части вывода. Это значение не совсем попадает в постоянный паттерн, но, похоже, остаётся примерно в ограниченном интервале 40–120. И снова, чем больше файлы, тем обычно больше их значения остатков. Но иногда у мелких файлов тоже бывают большие значения остатков, так что это не так постоянно, как бы нам хотелось.
Тем не менее, стоит заметить, что значения остатков никогда не бывают отрицательными. Поэтому мысль о том, что эти два значения метаданных указывают на подразделы файла, сохраняет свою привлекательность.
(Если вы достаточно внимательны, то уже увидели нечто, дающее подсказку о пока незамеченной связи. Если не увидели, то продолжайте читать; тайна вскоре будет раскрыта.)
Более масштабные перекрёстные сравнения файлов
На этом этапе было бы неплохо иметь возможность перекрёстно сравнивать больше, чем 16 байт за раз. Для этого нам потребуется другой тип визуализации. Один из хороших подходов — создать изображение, в котором каждый пиксель обозначает отдельный байт одного из файлов, а цвет обозначает значение этого байта. Изображение может показать срез всех 148 файлов за раз, если каждый файл данных будет обозначаться одной строкой пикселей изображения. Так как все файлы имеют разный размер, мы возьмём по 200 первых байт каждого, чтобы построить прямоугольное изображение.
Проще всего будет построить изображение в градациях серого, в котором значение каждого байта соответствует разным уровням серого. Можно очень просто создать файл PGM с нашими данными, потому что заголовок PGM состоит только из ASCII-текста:
$ echo P5 200 148 255 >hdr.pgm
Что такое файл PGM? PGM, что расшифровывается как «portable graymap» («платформонезависимая карта оттенков серого») — это один из трёх форматов графических файлов, которые созданы ради чрезвычайной простоты считывания и записи: после заголовка в ASCII, каждый байт описывает цвет одного пикселя в градациях серого. Два остальных формата файлов из этого семейства — это PBM («portable bitmap», «платформонезависимая битовая карта»), описывающий монохромные изображения как 8 пикселей на байт, и PPM («portable pixmap», «платформонезависимая пиксельная карта»), которая описывает изображения как 3 байта на пиксель.
P5 — это начальная сигнатура, обозначающая формат файлов PGM. Следующие два числа, 200 и 148, задают ширину и высоту изображения, а последнее, 255, указывает максимальное значение на пиксель. Заголовок PGM завершается переходом на новую строку, после которого идут пиксельные данные. (Стоит заметить, что заголовок PGM чаще всего разбит на три отдельных строки текста, но стандарт PGM требует только, чтобы элементы были разделены каким-нибудь пробельным символом (whitespace).)
Мы можем использовать утилиту head, чтобы извлечь из каждого файла первые 200 байт:
$ for f in levels/* ; do head -c200 $f ; done >out.pgm
Затем мы можем конкатенировать их с заголовком и создать отображаемое изображение:
xview — это старая программа X для отображения изображений в окне. Можете заменить её своим любимой программой просмотра изображений, например, утилитой display из ImageMagick, но учтите, что есть на удивление много утилит просмотра изображений, которые не принимают файл изображения, перенаправленный на стандартный вход.
$ cat hdr.pgm out.pgm | xview /dev/stdin
Если вам сложно рассмотреть детали на тёмном изображении, то можете выбрать другую цветовую схему. Используйте утилиту pgmtoppm из ImageMagick, чтобы преобразовать пиксели в другой диапазон цветов. Эта версия создаст «негативное» изображение:
$ cat hdr.pgm out.pgm | pgmtoppm white-black | xview /dev/stdin
А эта версия делает низкие значения жёлтыми, а высокие — синими:
$ cat hdr.pgm out.pgm | pgmtoppm yellow-blue | xview /dev/stdin
Видимость цветов — очень субъективный вопрос, поэтому можете поэкспериментировать, и выбрать, что лучше для вас. Как бы то ни было, изображение 200 × 148 довольно мало, так что лучше всего повысить видимость, увеличив его размер:
$ cat hdr.pgm out.pgm | xview -zoom 300 /dev/stdin
Изображение тёмное, и это означает, что большинство байтов содержит маленькие значения. Контрастирует с ним заметная полоса в основном ярких пикселей ближе к левому краю. Эта полоса расположена в третьем байте файла, который, как мы говорили выше, варьируется в полном интервале значений.
И хотя за пределами третьего байта есть не так много высоких значений, когда они появляются, то часто состоят из серий, создавая на изображении короткие яркие полоски. Некоторые из этих серий периодически прерываются, создавая эффект пунктирной линии. (Возможно, при правильном подборе цвета можно будет заметить такие последовательности и в более тёмных цветах.)
При внимательном изучении изображения можно понять, что в основном в левой части доминируют небольшие вертикальные полосы. Эти полосы говорят нам о некой повторяемости в большинстве файлов. Но не во всех файлах — время от времени появляются строки пикселей, где полосы прерываются —, но этого более чем достаточно, чтобы определить наличие реального паттерна. Этот паттерн пропадает в правой части изображения, тёмный фон из полос уступает место чему-то более шумному и неопределённому. (Похоже, что полосы также отсутствуют в самой левой части изображения, но, повторюсь, возможно, что при
