Реверс-инжиниринг Star Wars: Yoda Stories

http://www.zachtronics.com/yoda-stories/
  • Перевод
image

[Прим. пер.: Зак Барт из Zachtronics не только пишет замечательные видеоигры-головоломки (SpaceChem, TIS-100, SHENZHEN I/O) и апгрейдит электронные пищущие машинки, но и увлекается обратной разработкой ресурсов старых игр. Эта статья посвящена успешному взлому любимой игры его детства.]

Предисловие


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

В 2006 году, через несколько дней после выпуска демо Star Wars: Empire at War, я опубликовал пару рудиментарных инструментов, позволявших выполнять дамп и переупаковку файлов данных игры, в том числе простой мод, благодаря которому можно было сыграть за Империю (эта возможность была отключена в демо). В сети почти уже не найти следов моей работы, но мне удалось получить бесплатную футболку разработчика игры Petroglyph, а это уже кое-что.

За много лет до этого у меня была ещё одна игра по «Звёздным войнам» под названием Star Wars: Yoda Stories. Она была довольно запутанной и получила плохие отзывы, но это меня не останавливало. Как начинающий программист и упёртый фанат Star Wars я пытался найти ресурсы игры, чтобы сделать собственную ужасную игру по Star Wars. Однако мне удалось обнаружить только звуковые эффекты и небольшое количество спрайтов, которые распространялись как иконки темы для рабочего стола.


Перенесёмся вперёд на шестнадцать лет: я изучаю свою древнюю коллекцию CD-дисков в поисках старых игр, в которые можно поиграть на компьютерной вечеринке в тематике 1990-х. Вставив CD в привод, я сразу же понял, что нашёл файл данных размером примерно четыре мегабайта, который ждёт применения полученных мной в колледже знаний для взлома. Лучше позже, чем никогда!

Структура файлов (сложность: падаван)


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

Если вы хотите поэкспериментировать сами, то вот ссылка на файл данных игры: YODESK.DTA

Пора открыть этот файл!


Итак, это определённо не текст и не предназначено для чтения человеком, но это нас совсем не удивляет. Я уверен, что шестнадцать лет назад я открыл тот же самый файл в «Блокноте» и сразу же закрыл его, даже близко не поняв, что же я увидел.

Сначала мы видим четырёхбуквенные символы ASCII, которые мне кажутся похожими на идентификаторы разделов. Опустившись ниже, мы видим этому подтверждение: SNDS, TILE, CHAR, PUZ2 и многое другое. Файл заканчивается разделом ENDF, и это подразумевает, что общая структура файла — это какая-то иерархия или список разделов с метками.

Идентификатор VERS очевидно начинает раздел «version», в котором содержатся следующие четыре байта: 0x00, 0x02, 0x00, 0x00. Подозреваю, что это версия 2.0 формата файлов, потому что Yoda Stories вышла после игры про Индиану Джонса, в которой, похоже, использовался тот же движок. Однако это не особо важно, потому что этот фрагмент данных нас не очень интересует.

Дальше идёт раздел STUP (setup?), в котором содержится множество загадочных данных:


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

Если мы снова взглянем на начало раздела (предыдущий скриншот), то увидим, что за идентификатором STUP идут четыре подозрительных байта: 0x00, 0x44, 0x01, 0x00. Если мы проверим оставшиеся в этом разделе данные после этих четырёх байтов, то увидим, что они имеют длину ровно 0x00014400 байт. Совпадение? Не думаю!

Очевидно, эти четыре байта — беззнаковое 32-битное целое число, указывающее количество данных, составляющих оставшуюся часть раздела STUP. Если вам кажется, что байты записаны в обратном порядке, то вы правы: они хранятся в порядке от младшего к старшему (little-endian), при котором наименее значимый байт хранится первым — распространённая практика для процессоров x86 и x86-64. Если мы считаем значение длины, то сможем пропустить остальную часть раздела, не зная при этом ничего о хранящихся в нём данных.

Считывание двоичных файлов вручную, даже размером всего 4 МБ — не очень продуктивный способ работы, поэтому настало время начать работу с программой, парсящей файл и/или скидывающей дампы данных в процессе выяснения того, как они закодированы. Я предпочитаю язык программирования C#, поэтому буду использовать его; предполагая, что формат файлов не совсем перепутан, я смогу создать достаточно подробный класс BinaryReader и начать работу. Вот программа, которую мы пока подготовили:

static void Main(string[] args)
{
	using (BinaryReader binaryReader = new BinaryReader(File.OpenRead("YODESK.DTA")))
	{
		bool keepReading = true;
		while (keepReading)
		{
			string section = new string(binaryReader.ReadChars(4));
			switch (section)
			{
				case "VERS":
					uint version = binaryReader.ReadUInt32();
					break;
				case "STUP":
					uint length = binaryReader.ReadUInt32();
					byte[] data = binaryReader.ReadBytes((int)length);
					break;
				default:
					throw new Exception("Unknown section: " + section);
			}
		}
	}
}

К сожалению, она будет работать только для первых двух разделов: как только мы доходим до третьего раздела (SNDS), становится очевидно, что нам придётся обрабатывать все варианты, которые есть в файле. Это довольно часто происходит при реверс-инжиниринге форматов файлов, потому что в них есть множество различных значений, имеющих один из множества типов; поэтому нам нужно понять каждый тип, с которым мы можем встретиться. К счастью, почти у всех разделов этого файла за идентификатором раздела следует его беззнаковая 32-битная длина, то есть мы сможем использовать для их пропуска код обработки раздела STUP.

static void Main(string[] args)
{
	using (BinaryReader binaryReader = new BinaryReader(File.OpenRead("YODESK.DTA")))
	{
		bool keepReading = true;
		while (keepReading)
		{
			string section = new string(binaryReader.ReadChars(4));
			switch (section)
			{
				case "VERS":
					uint version = binaryReader.ReadUInt32();
					break;
				case "STUP":
				case "SNDS":
				case "ZONE":
				case "TILE":
				case "PUZ2":
				case "CHAR":
				case "CHWP":
				case "CAUX":
				case "TNAM":
					uint sectionLength = binaryReader.ReadUInt32();
					byte[] sectionData = binaryReader.ReadBytes((int)sectionLength);
					break;
				case "ENDF":
					keepReading = false;
					break;
			}
		}
	}
}



Похоже, что в разделе ZONE его длина указана сразу за идентификатором (0x00010292), но если мы перепрыгнем на это количество байт, то окажемся в пустоте, то есть скорее всего, мы делаем что-то не так. Однако, очевидно, что сразу после начала есть другие идентификаторы: IZON, IZAX, IZX2, IZX3, IZX4 и от нуля до нескольких IACT после них. Этот набор идентификаторов повторяется ещё раз ниже, а затем встречается в файле ещё несколько раз. Здесь нам пригодится знание о том, как устроена игра: одна из важных «фич» Yoda Stories заключается в том, что при каждом новом прохождении генерируется случайная карта, но после нескольких игр становится очевидно, что карты на самом деле составлены из соединённых вместе карт меньшего размера. Тот факт, что разделы IACT содержат похожий на скрипты текст, подтверждает мысль о том, что каждый IZON на самом деле соответствует фрагменту карты:


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

Здесь много разделов IZON, поэтому очевидно, что есть какие-то данные, позволяющие перемещаться от одного к другому; однако вполне возможно, что программа просто сканирует данные, пока не находит следующую строку «IZON», хотя это и очень ненадёжный подход: кто знает, возможно, когда-то в строке диалога NPC кто-нибудь добавит «IZON»! Измерив длину от начала первого IZON до следующего IZON, мы получаем длину 0x064C, что подозрительно близко к четырём байтам после четырёх байтов, следующих за идентификатором ZONE (0x00000646). Если мы будем воспринимать эти четыре байта как идентификатор длины и посмотрим на следующие за ними байты 0x646, то начнём замечать паттерн:


4 байта: "ZONE"
2 байта: ????
2 байта: ????
4 байта: длина (X)
X байт: данные zone
2 байта: ????
4 байта: длина (X)
X байт: данные zone
2 байта: ????
4 байта: длина (X)
X байт: данные zone
...
2 байт: ????
4 байта: длина (X)
X байт: данные zone
4 байта: "PUZ2" (начало следующего раздела)


Дальнейшее изучение позволило выяснить факты различной степени полезности:

  • Два байта, следующие за идентификатором ZONE, соответствуют беззнаковому 16-битному целому числу, определяющему количество зон.
  • Два байта перед определителем длины каждой зоны могут иметь значения только 0x0001, 0x0002, 0x0003 и 0x0005.
  • Первые два байта данных зон — это какой-то ID-номер карты, начинающийся с 0x0000 и каждый раз увеличивающийся на единицу.

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

static void Main(string[] args)
{
	using (BinaryReader binaryReader = new BinaryReader(File.OpenRead("YODESK.DTA")))
	{
		bool keepReading = true;
		while (keepReading)
		{
			string section = new string(binaryReader.ReadChars(4));
			switch (section)
			{
				case "VERS":
					uint version = binaryReader.ReadUInt32();
					break;
				case "STUP":
				case "SNDS":
				case "TILE":
				case "PUZ2":
				case "CHAR":
				case "CHWP":
				case "CAUX":
				case "TNAM":
					uint sectionLength = binaryReader.ReadUInt32();
					byte[] sectionData = binaryReader.ReadBytes((int)sectionLength);
					break;
				case "ZONE":
					ushort count = binaryReader.ReadUInt16();
					for (int i = 0; i < count; i++)
					{
						ushort unknown = binaryReader.ReadUInt16();
						uint zoneLength = binaryReader.ReadUInt32();
						byte[] zoneData = binaryReader.ReadBytes((int)zoneLength);
					}
					break;
				case "ENDF":
					keepReading = false;
					break;
				default:
					throw new Exception("Unknown section: " + section);
			}
		}
	}
}

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

Тайлы (сложность: рыцарь-джедай)


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


Если мы спустимся вниз, к середине раздела TILE, то нам сразу станет очевидно, что здесь есть нечто интересное: растровые изображения! Изображения игры — это спрайты размером 32x32 пикселя, так что если столбце шириной 32-байт начинают появляться похожие паттерны, то существует высокая вероятность того, что это формат несжатых растровых изображений с одним байтом на пиксель.


Если мы перейдём к началу раздела TILE, то легко заметить 1024-байтный (32x32) участок данных, соответствующий пространству символов ASCII, предположительно являющийся данными спрайтов с префиксом из четырёх байтов. Если мы исследуем интервал значений этих четырёх байтов во всём массиве данных, то заметим, что они относительно случайны, но часто повторяются и выглядят как массив битовых флагов.

4 байта: флаги
1024 байта: данные изображения
4 байта: флаги
1024 байта: данные изображения
...
4 байта: флаги
1024 байта: данные изображения


Возможно, битовые флаги описывают свойства тайлов? Да какая разница! Мы уже близки к извлечению изображений! Нам осталось расширить функционал нашей программы до дампа предполагаемых данных изображений в файлы изображений и…

case "TILE":
{
	Directory.CreateDirectory(@"Tiles");
	uint tileSectionLength = binaryReader.ReadUInt32();
	for (int i = 0; i < tileSectionLength / 0x404; i++)
	{
		uint unknown = binaryReader.ReadUInt32();
		Bitmap tile = new Bitmap(32, 32);
		for (int j = 0; j < 0x400; j++)
		{
			byte pixelData = binaryReader.ReadByte();
			Color pixelColor = Color.FromArgb(pixelData, pixelData, pixelData);
			tile.SetPixel(j % 32, j / 32, pixelColor);
		}
		
		tile.Save(string.Format(@"Tiles\{0}.png", i));
	}
	break;
}



Победа! Или что-то вроде того…

Очевидно, что в игре есть цвет, поэтому простое присвоение значения пикселя каждому компоненту RGB не решит задачу; мы никогда не получим ничего, кроме градаций серого. Википедия говорит нам, что стандартной 8-битной цветовой схемой true color является 0bRRRGGGBB, так что давайте попробуем её:

case "TILE":
{
	Directory.CreateDirectory(@"Tiles");
	uint tileSectionLength = binaryReader.ReadUInt32();
	for (int i = 0; i < tileSectionLength / 0x404; i++)
	{
		uint unknown = binaryReader.ReadUInt32();
		Bitmap tile = new Bitmap(32, 32);
		for (int j = 0; j < 0x400; j++)
		{
			byte pixelData = binaryReader.ReadByte();
			byte r = (byte)((pixelData & 0xE0) << 0);
			byte g = (byte)((pixelData & 0x1C) << 3);
			byte b = (byte)((pixelData & 0x03) << 6);
			Color pixelColor = Color.FromArgb(r, g, b);
			tile.SetPixel(j % 32, j / 32, pixelColor);
		}
		
		tile.Save(string.Format(@"Tiles\{0}.png", i));
	}
	break;
}


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


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

0x1F 0x00 / 0x00 / 0x00
0x92 0x0B / 0x53 / 0xFB
0x93 0x00 / 0x00 / 0xFB
0x94 0x00 / 0x00 / 0xCB
0x95 0x00 / 0x00 / 0x9F
0x96 0x00 / 0x00 / 0x6F


Я слишком оптимистично предполагал, что существует какое-то битовое преобразование из значения пикселя в компоненты цвета, но то, что 0x1F каким-то образом соответствует чёрному (все нули) указывает на мою ошибку. Если уменьшение значения пикселя с 0x93 до 0x92 волшебным образом добавляет цвету два байта информации, то настало время признать неизбежное: где-то хранится цветовая палитра, и мы не имеем ни малейшего понятия, где она.

Конечно, мы можем взять кучу скриншотов и автоматизировать процесс сопоставления значения пикселей, но должен существовать и более оптимальный способ; данные палитры обязательно где-то хранятся. Если бы я программировал эту систему, то наверно просто хранил бы массив цветов, в котором индекс массива является значением данных пикселя. Развлечения ради, давайте поищем в файле один из цветов, использованных в спрайте R2D2, а именно 0x0B53FB…

Не-а, ничего.

Ещё один популярный формат пикселей — BGR, возможно, подойдёт 0xFB530B?

Тоже пусто.

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


Боже мой, это цветовая палитра! Следующие четыре байта имеют значение 0xFB000000, то есть цвет 0x93 в BGRA, поэтому есть большая вероятность, что мы наткнулись на что-то полезное. Если мы поищем данные в дизассемблере, то сможем понять немного больше:


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

private static readonly byte[] PaletteData = new byte[] 
{ 
	0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 
	0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 
	0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0xFF, 0xFF, 0x8B, 0x00, 0xC3, 0xCF, 0x4B, 0x00, 
	0x8B, 0xA3, 0x1B, 0x00, 0x57, 0x77, 0x00, 0x00, 0x8B, 0xA3, 0x1B, 0x00, 0xC3, 0xCF, 0x4B, 0x00, 
	0xFB, 0xFB, 0xFB, 0x00, 0xEB, 0xE7, 0xE7, 0x00, 0xDB, 0xD3, 0xD3, 0x00, 0xCB, 0xC3, 0xC3, 0x00, 
	0xBB, 0xB3, 0xB3, 0x00, 0xAB, 0xA3, 0xA3, 0x00, 0x9B, 0x8F, 0x8F, 0x00, 0x8B, 0x7F, 0x7F, 0x00, 
	0x7B, 0x6F, 0x6F, 0x00, 0x67, 0x5B, 0x5B, 0x00, 0x57, 0x4B, 0x4B, 0x00, 0x47, 0x3B, 0x3B, 0x00, 
	0x33, 0x2B, 0x2B, 0x00, 0x23, 0x1B, 0x1B, 0x00, 0x13, 0x0F, 0x0F, 0x00, 0x00, 0x00, 0x00, 0x00, 
	0x00, 0xC7, 0x43, 0x00, 0x00, 0xB7, 0x43, 0x00, 0x00, 0xAB, 0x3F, 0x00, 0x00, 0x9F, 0x3F, 0x00, 
	0x00, 0x93, 0x3F, 0x00, 0x00, 0x87, 0x3B, 0x00, 0x00, 0x7B, 0x37, 0x00, 0x00, 0x6F, 0x33, 0x00, 
	0x00, 0x63, 0x33, 0x00, 0x00, 0x53, 0x2B, 0x00, 0x00, 0x47, 0x27, 0x00, 0x00, 0x3B, 0x23, 0x00, 
	0x00, 0x2F, 0x1B, 0x00, 0x00, 0x23, 0x13, 0x00, 0x00, 0x17, 0x0F, 0x00, 0x00, 0x0B, 0x07, 0x00, 
	0x4B, 0x7B, 0xBB, 0x00, 0x43, 0x73, 0xB3, 0x00, 0x43, 0x6B, 0xAB, 0x00, 0x3B, 0x63, 0xA3, 0x00, 
	0x3B, 0x63, 0x9B, 0x00, 0x33, 0x5B, 0x93, 0x00, 0x33, 0x5B, 0x8B, 0x00, 0x2B, 0x53, 0x83, 0x00, 
	0x2B, 0x4B, 0x73, 0x00, 0x23, 0x4B, 0x6B, 0x00, 0x23, 0x43, 0x5F, 0x00, 0x1B, 0x3B, 0x53, 0x00, 
	0x1B, 0x37, 0x47, 0x00, 0x1B, 0x33, 0x43, 0x00, 0x13, 0x2B, 0x3B, 0x00, 0x0B, 0x23, 0x2B, 0x00, 
	0xD7, 0xFF, 0xFF, 0x00, 0xBB, 0xEF, 0xEF, 0x00, 0xA3, 0xDF, 0xDF, 0x00, 0x8B, 0xCF, 0xCF, 0x00, 
	0x77, 0xC3, 0xC3, 0x00, 0x63, 0xB3, 0xB3, 0x00, 0x53, 0xA3, 0xA3, 0x00, 0x43, 0x93, 0x93, 0x00, 
	0x33, 0x87, 0x87, 0x00, 0x27, 0x77, 0x77, 0x00, 0x1B, 0x67, 0x67, 0x00, 0x13, 0x5B, 0x5B, 0x00, 
	0x0B, 0x4B, 0x4B, 0x00, 0x07, 0x3B, 0x3B, 0x00, 0x00, 0x2B, 0x2B, 0x00, 0x00, 0x1F, 0x1F, 0x00, 
	0xDB, 0xEB, 0xFB, 0x00, 0xD3, 0xE3, 0xFB, 0x00, 0xC3, 0xDB, 0xFB, 0x00, 0xBB, 0xD3, 0xFB, 0x00, 
	0xB3, 0xCB, 0xFB, 0x00, 0xA3, 0xC3, 0xFB, 0x00, 0x9B, 0xBB, 0xFB, 0x00, 0x8F, 0xB7, 0xFB, 0x00, 
	0x83, 0xB3, 0xF7, 0x00, 0x73, 0xA7, 0xFB, 0x00, 0x63, 0x9B, 0xFB, 0x00, 0x5B, 0x93, 0xF3, 0x00, 
	0x5B, 0x8B, 0xEB, 0x00, 0x53, 0x8B, 0xDB, 0x00, 0x53, 0x83, 0xD3, 0x00, 0x4B, 0x7B, 0xCB, 0x00, 
	0x9B, 0xC7, 0xFF, 0x00, 0x8F, 0xB7, 0xF7, 0x00, 0x87, 0xB3, 0xEF, 0x00, 0x7F, 0xA7, 0xF3, 0x00, 
	0x73, 0x9F, 0xEF, 0x00, 0x53, 0x83, 0xCF, 0x00, 0x3B, 0x6B, 0xB3, 0x00, 0x2F, 0x5B, 0xA3, 0x00, 
	0x23, 0x4F, 0x93, 0x00, 0x1B, 0x43, 0x83, 0x00, 0x13, 0x3B, 0x77, 0x00, 0x0B, 0x2F, 0x67, 0x00, 
	0x07, 0x27, 0x57, 0x00, 0x00, 0x1B, 0x47, 0x00, 0x00, 0x13, 0x37, 0x00, 0x00, 0x0F, 0x2B, 0x00, 
	0xFB, 0xFB, 0xE7, 0x00, 0xF3, 0xF3, 0xD3, 0x00, 0xEB, 0xE7, 0xC7, 0x00, 0xE3, 0xDF, 0xB7, 0x00, 
	0xDB, 0xD7, 0xA7, 0x00, 0xD3, 0xCF, 0x97, 0x00, 0xCB, 0xC7, 0x8B, 0x00, 0xC3, 0xBB, 0x7F, 0x00, 
	0xBB, 0xB3, 0x73, 0x00, 0xAF, 0xA7, 0x63, 0x00, 0x9B, 0x93, 0x47, 0x00, 0x87, 0x7B, 0x33, 0x00, 
	0x6F, 0x67, 0x1F, 0x00, 0x5B, 0x53, 0x0F, 0x00, 0x47, 0x43, 0x00, 0x00, 0x37, 0x33, 0x00, 0x00, 
	0xFF, 0xF7, 0xF7, 0x00, 0xEF, 0xDF, 0xDF, 0x00, 0xDF, 0xC7, 0xC7, 0x00, 0xCF, 0xB3, 0xB3, 0x00, 
	0xBF, 0x9F, 0x9F, 0x00, 0xB3, 0x8B, 0x8B, 0x00, 0xA3, 0x7B, 0x7B, 0x00, 0x93, 0x6B, 0x6B, 0x00, 
	0x83, 0x57, 0x57, 0x00, 0x73, 0x4B, 0x4B, 0x00, 0x67, 0x3B, 0x3B, 0x00, 0x57, 0x2F, 0x2F, 0x00, 
	0x47, 0x27, 0x27, 0x00, 0x37, 0x1B, 0x1B, 0x00, 0x27, 0x13, 0x13, 0x00, 0x1B, 0x0B, 0x0B, 0x00, 
	0xF7, 0xB3, 0x37, 0x00, 0xE7, 0x93, 0x07, 0x00, 0xFB, 0x53, 0x0B, 0x00, 0xFB, 0x00, 0x00, 0x00, 
	0xCB, 0x00, 0x00, 0x00, 0x9F, 0x00, 0x00, 0x00, 0x6F, 0x00, 0x00, 0x00, 0x43, 0x00, 0x00, 0x00, 
	0xBF, 0xBB, 0xFB, 0x00, 0x8F, 0x8B, 0xFB, 0x00, 0x5F, 0x5B, 0xFB, 0x00, 0x93, 0xBB, 0xFF, 0x00, 
	0x5F, 0x97, 0xF7, 0x00, 0x3B, 0x7B, 0xEF, 0x00, 0x23, 0x63, 0xC3, 0x00, 0x13, 0x53, 0xB3, 0x00, 
	0x00, 0x00, 0xFF, 0x00, 0x00, 0x00, 0xEF, 0x00, 0x00, 0x00, 0xE3, 0x00, 0x00, 0x00, 0xD3, 0x00, 
	0x00, 0x00, 0xC3, 0x00, 0x00, 0x00, 0xB7, 0x00, 0x00, 0x00, 0xA7, 0x00, 0x00, 0x00, 0x9B, 0x00, 
	0x00, 0x00, 0x8B, 0x00, 0x00, 0x00, 0x7F, 0x00, 0x00, 0x00, 0x6F, 0x00, 0x00, 0x00, 0x63, 0x00, 
	0x00, 0x00, 0x53, 0x00, 0x00, 0x00, 0x47, 0x00, 0x00, 0x00, 0x37, 0x00, 0x00, 0x00, 0x2B, 0x00, 
	0x00, 0xFF, 0xFF, 0x00, 0x00, 0xE3, 0xF7, 0x00, 0x00, 0xCF, 0xF3, 0x00, 0x00, 0xB7, 0xEF, 0x00, 
	0x00, 0xA3, 0xEB, 0x00, 0x00, 0x8B, 0xE7, 0x00, 0x00, 0x77, 0xDF, 0x00, 0x00, 0x63, 0xDB, 0x00, 
	0x00, 0x4F, 0xD7, 0x00, 0x00, 0x3F, 0xD3, 0x00, 0x00, 0x2F, 0xCF, 0x00, 0x97, 0xFF, 0xFF, 0x00, 
	0x83, 0xDF, 0xEF, 0x00, 0x73, 0xC3, 0xDF, 0x00, 0x5F, 0xA7, 0xCF, 0x00, 0x53, 0x8B, 0xC3, 0x00, 
	0x2B, 0x2B, 0x00, 0x00, 0x23, 0x23, 0x00, 0x00, 0x1B, 0x1B, 0x00, 0x00, 0x13, 0x13, 0x00, 0x00, 
	0xFF, 0x0B, 0x00, 0x00, 0xFF, 0x00, 0x4B, 0x00, 0xFF, 0x00, 0xA3, 0x00, 0xFF, 0x00, 0xFF, 0x00, 
	0x00, 0xFF, 0x00, 0x00, 0x00, 0x4B, 0x00, 0x00, 0xFF, 0xFF, 0x00, 0x00, 0xFF, 0x33, 0x2F, 0x00, 
	0x00, 0x00, 0xFF, 0x00, 0x00, 0x1F, 0x97, 0x00, 0xDF, 0x00, 0xFF, 0x00, 0x73, 0x00, 0x77, 0x00, 
	0x6B, 0x7B, 0xC3, 0x00, 0x57, 0x57, 0xAB, 0x00, 0x57, 0x47, 0x93, 0x00, 0x53, 0x37, 0x7F, 0x00, 
	0x4F, 0x27, 0x67, 0x00, 0x47, 0x1B, 0x4F, 0x00, 0x3B, 0x13, 0x3B, 0x00, 0x27, 0x77, 0x77, 0x00, 
	0x23, 0x73, 0x73, 0x00, 0x1F, 0x6F, 0x6F, 0x00, 0x1B, 0x6B, 0x6B, 0x00, 0x1B, 0x67, 0x67, 0x00, 
	0x1B, 0x6B, 0x6B, 0x00, 0x1F, 0x6F, 0x6F, 0x00, 0x23, 0x73, 0x73, 0x00, 0x27, 0x77, 0x77, 0x00, 
	0xFF, 0xFF, 0xEF, 0x00, 0xF7, 0xF7, 0xDB, 0x00, 0xF3, 0xEF, 0xCB, 0x00, 0xEF, 0xEB, 0xBB, 0x00, 
	0xF3, 0xEF, 0xCB, 0x00, 0xE7, 0x93, 0x07, 0x00, 0xE7, 0x97, 0x0F, 0x00, 0xEB, 0x9F, 0x17, 0x00, 
	0xEF, 0xA3, 0x23, 0x00, 0xF3, 0xAB, 0x2B, 0x00, 0xF7, 0xB3, 0x37, 0x00, 0xEF, 0xA7, 0x27, 0x00, 
	0xEB, 0x9F, 0x1B, 0x00, 0xE7, 0x97, 0x0F, 0x00, 0x0B, 0xCB, 0xFB, 0x00, 0x0B, 0xA3, 0xFB, 0x00, 
	0x0B, 0x73, 0xFB, 0x00, 0x0B, 0x4B, 0xFB, 0x00, 0x0B, 0x23, 0xFB, 0x00, 0x0B, 0x73, 0xFB, 0x00, 
	0x00, 0x13, 0x93, 0x00, 0x00, 0x0B, 0xD3, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 
	0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 
	0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0xFF, 0xFF, 0xFF, 0x00, 
};

case "TILE":
{
	Directory.CreateDirectory(@"Tiles");
	uint tileSectionLength = binaryReader.ReadUInt32();
	for (int i = 0; i < tileSectionLength / 0x404; i++)
	{
		uint unknown = binaryReader.ReadUInt32();
		Bitmap tile = new Bitmap(32, 32);
		for (int j = 0; j < 0x400; j++)
		{
			byte pixelData = binaryReader.ReadByte();
			byte r = PaletteData[pixelData * 4 + 2];
			byte g = PaletteData[pixelData * 4 + 1];
			byte b = PaletteData[pixelData * 4 + 0];
			Color pixelColor = pixelData == 0 ? Color.Transparent : Color.FromArgb(r, g, b);
			tile.SetPixel(j % 32, j / 32, pixelColor);
		}
		
		tile.Save(string.Format(@"Tiles\{0}.png", i));
	}
	break;
}


Сработало! Мы извлекли больше двух тысяч странных, но очаровательных спрайтов. Стоит заметить, что цвет 0x00 на самом деле прозрачный, и это достаточно очевидно, если взглянуть на сырые данные пикселей.

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

ТИПЫ ТАЙЛОВ:
bit0 = игровой объект
bit1 = без коллизий, отрисовывается позади игрока
bit2 = с коллизиями, средний слой
bit3 = блок, который можно толкать/тянуть
bit4 = без коллизий, отрисовывается перед игроком (для высоких объектов, за которыми может проходить игрок)
bit5 = тайл мини-карты
bit6 = оружие
bit7 = предмет
bit8 = персонаж

ФЛАГИ ДЛЯ ОРУЖИЯ:
bit16 = лёгкий бластер
bit17 = тяжёлый бластер ИЛИ термический детонатор (????)
bit18 = световой меч
bit19 = сила

ФЛАГИ ДЛЯ ПРЕДМЕТОВ:
bit16 = ключ-карта
bit17 = элемент головоломки
bit18 = элемент головоломки (редкий???)
bit19 = элемент головоломки (ключевой предмет???)
bit20 = локатор
bit22 = аптечка

ФЛАГИ ДЛЯ ПЕРСОНАЖЕЙ:
bit16 = игрок
bit17 = враг
bit18 = дружественный

ФЛАГИ ДЛЯ ДРУГИХ ТАЙЛОВ:
bit16 = дверь

ФЛАГИ ДЛЯ ТАЙЛОВ МИНИ-КАРТЫ:
bit17 = конкретный тайл мини-карты (дом)
bit18 = конкретный тайл мини-карты (головоломка, нерешённая)
bit19 = конкретный тайл мини-карты (головоломка, решённая)
bit20 = конкретный тайл мини-карты (шлюз, нерешённый)
bit21 = конкретный тайл мини-карты (шлюз, решённый)
bit22 = конкретный тайл мини-карты (верхняя стена, закрытая)
bit23 = конкретный тайл мини-карты (нижняя стена, закрытая)
bit24 = конкретный тайл мини-карты (левая стена, закрытая)
bit25 = конкретный тайл мини-карты (правая стена, закрытая)
bit26 = конкретный тайл мини-карты (верхняя стена, открытая)
bit27 = конкретный тайл мини-карты (нижняя стена, открытая)
bit28 = конкретный тайл мини-карты (левая стена, открытая)
bit29 = конкретный тайл мини-карты (правая стена, открытая)
bit30 = конкретный тайл мини-карты (задача)


Примечательно, что биты от 16 и выше используются с разными значениями в зависимости от битов 0-8, и немного поначалу немного сбивает с толку, если ожидать, что конкретный бит должен иметь только одно значение.

Карты (сложность: рыцарь-джедай)


Хотя мы уже добились того, к чему стремились, карты зон тоже выглядят интересным объектом для исследования. Если мы вернёмся к тому, как описываются зоны в шестнадцатеричном редакторе, то увидим, что в записях зон есть несколько подразделов. Чтобы анализировать зоны, а не пропускать их, о каждом из них нужно узнать больше:


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


Очень часто этот процесс похож на игру в сложную головоломку (можете мне поверить, я их пишу), но в конце концов меня осенило: здесь есть небольшой заголовок, определяющий, кроме всего прочего, размер карты (9x9 или 18x18), затем идут 6 байт на квадрат сетки, потом 16-битное целое число, определяющее количество идущих за ним 12-байтных структур.

Другие подразделы столь же запутаны: IZAX определяет свою длину плюс шесть, то же самое с IZX2 и IZX3; IZX4 имеет постоянную длину, а часто встречающийся IACT непосредственно указывает свою длину. Соединим всё вместе и получим следующее:

4 байта: "IZON"
4 байта: неизвестно
2 байта: ширина карты (W)
2 байта: высота карты (H)
1 байт: флаги карты (неизвестные значения)
5 байтов: не используются (одинаковые значения для всех карт)
1 байт: планета (0x01 = пустынная, 0x02 = снежная, 0x03 = лесная, 0x05 = болотистая)
1 байт: не используется (одинаковые значения для всех карт)
W*H*6 байт: данные карты
2 байта: объём записи информации объекта (X)
X*12 байт: данные информации объекта
4 байта: "IZAX"
2 байта: длина (X)
X-6 байт: данные IZAX
4 байта: "IZX2"
2 байта: длина (X)
X-6 байт: данные IZX2
4 байта: "IZX3"
2 байта: длина (X)
X-6 байт: данные IZX3
4 байта: "IZX4"
8 байт: данные IZX4
4 байта: "IACT"
4 байта: длина (X)
X байт: данные действий
4 байта: "IACT"
4 байта: длина (X)
X байт: данные действий
...
4 байта: "IACT"
4 байта: длина (X)
X байт: данные действий


Мы знаем, что есть шесть байтов на квадрат сетки, то есть высокая вероятность того, что они соответствуют тому, что записывается в квадрат сетки при загрузке карты. Просто посмотрев на первый квадрат первой карты (0x00, 0x00, 0xFF, 0xFF, 0x01, 0x00), я почти был уверен в том, что это три 16-битных целых числа, каждое из которых обозначает тайл, размещаемый в этом месте (потому что тайлов намного больше 256). Расширив функционал программы для соединения извлечённых файлов на основе этой информации, мы получим следующее:


Карты! Похоже, наша догадка оказалась верной. Оказывается, в игре более 600 карт, и у каждой есть собственные скрипт и схема. Удивительно, как много усилий было вложено в эту кажущуюся простой игру.



Также интересна длина переменной «информация объекта» в конце подраздела IZON. Похоже, она определяет дополнительные свойства тайлов, располагаемых на карте. Изучение данных как одного гигантского фрагмента в шестнадцатеричном редакторе не очень помогает, но если мы табулируем их как 12-байтные записи и сравним с изображением карты, то начинают появляться некие паттерны:



Тип N/A X Y N/A Арг
09 00 00 00 04 00 04 00 01 00 01 00
09 00 00 00 09 00 09 00 01 00 05 00
09 00 00 00 0F 00 09 00 01 00 09 00
0F 00 00 00 09 00 0D 00 01 00 5D 00
06 00 00 00 0A 00 03 00 01 00 AE 04
06 00 00 00 0A 00 04 00 01 00 AE 04


Если мы будем обрабатывать каждую запись как шесть 16-битных целых чисел, то первое оказывается флагом типа, а третье и четвёртое — координатами карты. Второе и пятое постоянно имеют одинаковые значения (0x0000 и 0x0001), а последнее очень сумбурно, что делает его похожим на аргумент. Когда мы начинаем смотреть, на какие тайлы указывают эти записи, то каждая запись типа 0x09 указывает на дверь, где аргумент — это ID карты, на которую ведёт дверь в игре.

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

ID типа Описание Аргумент
0x00 расположение триггера
0x01 точка спауна
0x02 место, связанное с Силой
0x03 транспорт на дополнительную карту карта, на которую транспорт переносит игрока
0x04 транспорт на основную карту карта, на которую транспорт переносит игрока
0x05 объект, который даёт игроку локатор
0x06 ящик с предметом предмет, лежащий внутри
0x07 NPC, дающий головоломку ID тайла соответствующего персонажа
0x08 ящик с оружием лежащее внутри оружие
0x09 дверь (на вход) карта, с которой соединена дверь
0x0A дверь (на выход)
0x0B не используется
0x0C блокировка
0x0D телепорт
0x0E X-Wing с планеты Дагоба карта, на которую X-Wing переносит игрока
0x0F X-Wing на планету Дагоба карта, на которую X-Wing переносит игрока

Скрипты (сложность: мастер-джедай)


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


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

Создание мода


Подраздел IZON для карты номер 95 начинается со смещения 0x266512 в файле данных. Мы можем пропустить 20 байт, чтобы добраться до данных карты, а потом пропустить ещё 6*(18*9+12) байт, чтобы перейти в точку (12, 11). Если затем мы с помощью hex-редактора сбросим значения тайлов 1985 и 1986 до «среднего» значения квадрата каждой сетки и перезапишем файл данных игры, то получим следующее:


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

ДОПОЛНЕНИЕ: пользователь sehugg с Hacker News сообщил, что на самом деле это машина из фильма 1978 года "Лето в поисках «Корвета»", в котором снимался Марк Хэмилл (игравший Люка Скайуокера). Вот так пасхалка!

В заключение


Очевидно, что имея терпение, с этими данными можно сделать гораздо больше; после реверс-инжиниринга большей части файла данных игры её на удивление просто будет пересоздать с нуля (сейчас она работает в ужасно маленьком окне) или написать инструменты для экспорта, редактирования и переупаковки содержимого игры, чтобы создавать моды. Не знаю, зачем вам это может понадобиться, но такая возможность определённо есть. Как минимум, теперь у меня есть доступ к крутому и исчерпывающему набору странно выглядящих спрайтов по «Звёздным войнам». Надеюсь, вы узнали нечто интересное о реверс-инжиниринге форматов файлов данных старых компьютерных игр!
Поделиться публикацией
AdBlock похитил этот баннер, но баннеры не зубы — отрастут

Подробнее
Реклама
Комментарии 13
  • 0
    Говорят, что на красной машине можно ездить. Не проверяли это утверждение? Еще говорят, что есть на одной из ледяных карт, которых нет на локаторе, есть снеговик. Некий супер-монстр, которого очень сложно убить.
    • +2
      А это не тот ли йетти-монстр из фильма, которому люк отрезал руку?
    • +4
      Читается как добротный детектив…
      • 0

        Точно. Не представляю, как вручную можно догадаться о некоторых вещах — типа того, что где-то записано число 12 байтовых структур. Если длину в байтах еще более-менее можно прикинуть "на глазок", то более сложные случаи явно должна изучать программа. Интересно, кто-нибудь делал программы анализаторы для такого выявления форматов файлов? А потом отсюда вытекает другой вопрос — создать формат, противодействующий такому анализу.

        • 0

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

          • 0

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

      • 0
        Большое спасибо, было интересно почитать. Играл в эту игру очень давно, нравилась.
        • 0
          Спасибо за перевод! Люблю такие статьи!
          • 0
            никогда не хватало терпения на копание в данных игры. начинал десятки, не закончил ни одной))
            • 0
              А у меня однажды появился стимул.

              Был у меня в свое время компьютер с видеокартой Trident TVGA9000. Она поддерживала какие-то нестандартные VESA режимы с глубиной цвета 16 бит, но GTA 1 упорно хотела запускаться только в режиме 256 цветов. В итоге пришлось расковырять форматы файлов и, вооружившись Паскалем пополам с ассемблером, написать смотрелку спрайтов из игры. Тогда-то я и увидел, насколько более красочной могла бы быть игра)
            • +2
              Небольшое дополнение к статье — тайлсеты, и заодно — от Индиана Джонса.

              Взято отсюда
              • 0
                Была у меня эта игра игра на каком то сборнике, помню я ее вдоль и поперек проходил.
                • 0
                  Почти два десятка лет прошло, как видел эту игру. Не ожидал её встретить тут!
                  И почти столько же, как вытаскивал картинки и звуки из других игрушек.

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