Реверс-инжиниринг карт Heroes of Might and Magic III: Horn of the Abyss + парсер на Python / Хабр

Интро

Мне стало любопытно: смогу ли я распарсить карту HotA и написать такой парсер, который сможет быстро отвечать на вопросы вроде: «Где можно выучить заклинание “Городской портал”?», «Где найти артефакт, например, Чёрный шар?», «Есть ли в тюрьме герой Джелу?» и всё в таком духе.

А ещё я решил, что искать в интернете готовые спецификации скучно. Гораздо интереснее попробовать разобраться самому. Прямо с нуля. Как будто интернета нет, а есть только карты, низкоуровневые редакторы и желание понять, что там внутри.

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

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

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

Подготовка

Взял два редактора: ImHex и HxD. Далее создал с нуля кучу пустых карт, которые отличаются названием, наличием подземелья, сложностью и так далее.

Идея простая: я создавал карты с нуля, менял в редакторе ровно одну вещь и потом сравнивал распакованные файлы в hex-редакторе. Например: название A против ABC, карта 36x36 против 72x72, подземелье выключено против включено.

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

Короче насоздавал я кучу карт и поехал.

С помощью ImHex открыл одну из карт и получил такое сообщение.

Карта в gzip. Надо всё распаковать.

С помощью WinRAR распаковал все карты. Теперь можно начинать сравнивать карты между собой и записывать изменения.

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

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

Файлы одинаковые.

Это хорошо. Можно ехать дальше.

Выдёргиваем название карты

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

HxD64 нашёл отличие.

У одной карты в ячейке 0x2B лежит 01, а в другой 03. Я пока не знаю, что это такое, кроме того, что числа отличаются. Теперь открываю карту, в названии которой лежит строка TITLE_0123456789.

Вижу: A = 1, название ABC = 3, название TITLE_0123456789 = 10. Туплю какое-то время, потому что не каждый день имею дело с низкоуровневым редактором, вспоминаю, что это же шестнадцатеричная система, а значит 10 — это 16 в десятичной. Всё сходится: у TITLE_0123456789 у нас 16 символов.

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

В кодировке Windows-1251:

CF = П
F0 = р
E8 = и
E2 = в
E5 = е
F2 = т

Итого получено с четырёх карт:

A: 01 00 00 00 41
ABC: 03 00 00 00 41 42 43
TITLE_0123456789: 10 00 00 00 54 49 54 4C 45 5F 30 31 32 33 34 35 36 37 38 39
Привет: 06 00 00 00 CF F0 E8 E2 E5 F2

Первый парсер названия HotA-карты

Я пока не знаю, что будет дальше в файле. Если я добавлю подземелье, поменяю размер карты или уровень сложности, какие-то байты точно изменятся. Но для текущих лабораторных карт я уже проверил одно: длина названия лежит по адресу 0x2B, а само название начинается с адреса 0x2F.

Этого достаточно, чтобы написать первый маленький Python-парсер, который вытаскивает название карты.

Перед кодом поясню, что вообще такое 0x2B. Это адрес байта в файле. 0x означает, что число записано в шестнадцатеричной системе.

В HxD адрес считается просто: слева есть начало строки, сверху есть номер колонки. На картинке строка 00000020, колонка 0B. Складываем:

0x20 + 0x0B = 0x2B

Или на это можно ещё смотреть как на координату байта в hex-редакторе.

import gzip

data = gzip.open("hota_lab_03_name_LONG.h3m", "rb").read()

n = int.from_bytes(data[0x2B:0x2F], "little")
name = data[0x2F:0x2F + n]

print(name.decode("cp1251"))

gzip.open(...).read() открывает gzip-сжатую .h3m-карту, распаковывает её и читает в память как последовательность байтов.

Если просто сделать:

print(data)

то мы увидим что-то вроде:

b'\\x20\\x00\\x00\\x00...'

Это и есть байты файла после распаковки.

Чтение длины названия

n = int.from_bytes(data[0x2B:0x2F], "little")

Здесь я беру байты с адресов:

0x2B
0x2C
0x2D
0x2E

Правая граница 0x2F в Python-срезе не включается.

В файле hota_lab_03_name_LONG.h3m там лежит:

10 00 00 00

int.from_bytes(..., "little") превращает эти байты в число, считая их как little-endian.

little-endian значит: младший байт числа лежит первым.

10 00 00 00

Если я прочитаю это как little-endian:

0x00000010 = 16

Если я прочитаю это как big-endian:

0x10000000 = 268435456

Название TITLE_0123456789 имеет длину 16 байт, поэтому здесь подходит little-endian. Короче, методом тыка и эмпирически это получаю.

После этой строки:

n == 16

Чтение самого названия

Дальше я читаю само название:

name = data[0x2F:0x2F + n]

Это значит: я беру n байт, начиная с адреса 0x2F.

Для моей карты это:

взять 16 байт с адреса 0x2F

Эти байты:

54 49 54 4C 45 5F 30 31 32 33 34 35 36 37 38 39

соответствуют тексту:

TITLE_0123456789

Пока name — это байты, а не строка Python. Поэтому я делаю:

print(name.decode("cp1251"))

decode("cp1251") превращает байты в текст как Windows-1251. Это подходит для моих английских и русских тестовых карт. Но это не значит, что все карты в мире обязаны быть в cp1251: для китайских карт кодировка может быть другой.

Текущий вывод

Для моих лабораторных HotA-карт:

0x2B..0x2E — 4 байта длины названия
0x2F — начало байтов названия
длина читается как little-endian
текст для моих карт декодируется как cp1251

Это пока не универсальная спецификация всей HotA-карты, а первый проверенный мной кусок формата.

Проверяем описание карты

С названием стало уже довольно похоже на правду. Теперь логично проверить description, но тут не буду второй раз писать роман. Логика оказалась той же.

Если описание длинное или русское, всё то же самое: сначала 4 байта длины, потом байты строки. Для русского текста снова видны байты Windows-1251.

Значит, на текущем этапе можно аккуратно записать: description идёт сразу после name и хранится по той же схеме. Длина, потом байты.

Проверяем размер карты

Дальше сравнил две карты: 36x36 и 72x72.

На карте 36x36 в нужном месте лежит:

24 00 00 00

0x24 в десятичной системе — это 36.

На карте 72x72 там же лежит:

48 00 00 00

0x48 в десятичной системе — это 72.

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

длина названия -> байты названия -> длина описания -> байты описания

Значит, текущий кусок заголовка уже выглядит так:

размер карты
один байт, который пока не трогаю
длина названия
название
длина описания
описание

Проверяем подземелье

Дальше сравнил две карты: без подземелья и с подземельем.

После размера карты лежит один байт:

00 - подземелья нет
01 - подземелье есть

Текущий кусок заголовка стал понятнее:

размер карты
флаг подземелья
длина названия
название
длина описания
описание

Проверяем сложность

Дальше сравнил карты со всеми уровнями сложности.

Картина тоже простая: после описания лежит ещё один байт. Чем число больше, тем сложнее карта.

00 - легко
01 - нормально
02 - сложно
03 - эксперт
04 - невозможно

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

На этом месте у меня уже есть не просто «вытащить имя карты», а маленький кусок заголовка:

размер карты
флаг подземелья
название
описание
сложность

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

size = 36
underground = 0
name = "DIFF_IMPOSSIBLE"
description = "DIFF"
difficulty = 4

Это всё ещё не парсер всей карты. Но это уже нормальный маленький парсер шапки, который появился не из спецификации, а из сравнения байтов.

Городской портал в свитке

То, чем я занимался до этого, можно и в игре посмотреть. Это не так интересно. Гораздо интереснее начать исследовать карту на предмет объектов.

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

Потом сравнил эти две карты:

Разница получилась такая:

Волшебная стрела: 0F
Городской портал: 09

Остальные байты рядом пока не трогаю. Факт сейчас только один: при замене заклинания в свитке один байт поменялся с 0F на 09.

Но тут я сам себя останавливаю. Я же знаю, что заклинаний в героях дофига. А я пока увидел только 0F и 09.

Поэтому я сделал ещё несколько карт со свитками в той же точке 10:10, но с другими заклинаниями: Lightning Bolt, Implosion, Armageddon, Resurrection и Air Elemental. И там снова меняется всего один байт, причём в том же самом месте.

Magic Arrow     -> Town Portal     : 0F -> 09
Magic Arrow     -> Lightning Bolt  : 0F -> 11
Magic Arrow     -> Implosion       : 0F -> 12
Magic Arrow     -> Armageddon      : 0F -> 1A
Magic Arrow     -> Resurrection    : 0F -> 26
Magic Arrow     -> Air Elemental   : 0F -> 45

Сначала это кажется странным: заклинаний ведь много. Но одна ячейка в hex-редакторе — это один байт, а один байт может хранить число от 0 до 255. Если читать его как знаковое число, получится диапазон от -128 до 127, но для id заклинания логичнее беззнаковый вариант. В реальной игре заклинаний около 70, так что одного байта им вполне хватает.

То есть сам факт, что меняется только одна ячейка, не ломает идею про spell_id. Наоборот, это выглядит нормально. Но размер поля я пока не считаю доказанным. Возможно, это действительно один байт. А возможно, это 4-байтовое little-endian число, у которого сейчас меняется только младший байт, а остальные три остаются нулями.

Железный вывод на этом этапе такой: при смене заклинания в свитке меняется байт по адресу 0x2B53, и его значение похоже на id выбранного заклинания.

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

Координаты объекта

Теперь я оставил заклинание в покое и начал двигать сам объект.

Для чистоты эксперимента во всех трёх картах лежал один и тот же свиток с «Городским порталом». Менялись только координаты:

hota_clean_scroll_02_town_portal_x10_y10_z0.raw
hota_clean_scroll_03_town_portal_x11_y10_z0.raw
hota_clean_scroll_04_town_portal_x10_y11_z0.raw

Сначала я сравнил карту, где свиток лежит в 10:10:0, с картой, где тот же свиток лежит в 11:10:0. То есть сдвинул объект на одну клетку по оси X.

Разница снова получилась минимальная:

0x2B46: 0A -> 0B

0A в шестнадцатеричной системе — это 10, а 0B — это 11. Значит, похоже, что по адресу 0x2B46 лежит координата X объекта.

Потом я сделал второй контрольный опыт: сравнил 10:10:0 с 10:11:0. Тут X уже не менялся, зато объект сдвинулся на одну клетку по оси Y.

И опять изменился один байт, только теперь следующий:

0x2B47: 0A -> 0B

То есть рядом начинает вырисовываться очень простая структура:

0x2B46 = x
0x2B47 = y
0x2B48 = z

Для исходного свитка в точке 10:10:0 это выглядит так:

0A 0A 00

То есть:

x = 10
y = 10
z = 0

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

Свиток и учёный

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

В первой карте в точке 10:10:0 лежит свиток с «Городским порталом». Во второй карте в той же точке 10:10:0 стоит учёный, который учит «Городской портал».

То есть смысл один:

Town Portal

Координаты тоже одни:

10:10:0

Но объект другой:

свиток
учёный

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

Но один важный факт всё равно видно. У свитка рядом с данными объекта лежит:

09 00 00 00

А у учёного в похожем месте лежит:

02 09

09 снова похоже на «Городской портал». Но теперь перед ним стоит ещё 02. Значит, для учёного это уже не просто поле заклинания, как у свитка. Похоже на пару:

02 - тип награды: заклинание
09 - какое именно заклинание

И вот тут становится понятно, почему нельзя просто искать байт 09 по всей карте. Один и тот же «Городской портал» может лежать в разных объектах по-разному.

Для свитка:

Для учёного:

02 09

То есть следующий шаг для нормального скрипта уже не «найти все байты 09», а научиться понимать, какой объект сейчас читается. Для свитка надо проверять одно поле, для учёного другое.

Скрипт для поиска портала в тестовых картах

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

Пока проверяю два случая:

свиток с «Городским порталом»;
учёный, который учит «Городской портал».

"""Учебный скрипт: идёт по карте побайтно и ищет знакомые TP-паттерны."""

import gzip
import struct
import sys
from pathlib import Path

u32 = struct.Struct("<I").unpack_from  # читает 4 байта как unsigned little-endian

TOWN_PORTAL = 9  # id заклинания Town Portal
SCHOLAR_REWARD_SPELL = 2  # тип награды учёного: заклинание

MAX_XY = 252  # максимальная координата на карте 252x252
MAX_Z = 1  # 0 - поверхность, 1 - подземелье

OBJECT_COORD_SIZE = 3  # x, y, z занимают три байта
OBJECT_COMMON_ZERO_OFFSET = 7  # общий нулевой блок начинается через 7 байт
OBJECT_COMMON_ZERO_SIZE = 5  # в наших объектах этот общий блок занимает 5 байт
OBJECT_DATA_OFFSET = 12  # после первых 12 байт начинаются данные конкретного объекта
SCAN_MARGIN = 20  # минимальный запас байтов для проверки паттерна

SCROLL_NO_MESSAGE = 0  # у свитка нет сообщения/охраны перед spell_id
SCROLL_SPELL_OFFSET_AFTER_FLAG = 1  # spell_id идёт сразу после флага сообщения
SCHOLAR_REWARD_VALUE_OFFSET = 1  # id награды идёт сразу после типа награды

data = gzip.decompress(Path(sys.argv[1]).read_bytes())

for off in range(len(data) - SCAN_MARGIN):
    x, y, z = data[off : off + OBJECT_COORD_SIZE]

    if x > MAX_XY or y > MAX_XY or z > MAX_Z:
        continue

    zero_start = off + OBJECT_COMMON_ZERO_OFFSET
    zero_end = zero_start + OBJECT_COMMON_ZERO_SIZE
    common_zeroes = data[zero_start:zero_end]
    if common_zeroes != bytes(OBJECT_COMMON_ZERO_SIZE):
        continue

    object_data = off + OBJECT_DATA_OFFSET

    if (
        data[object_data] == SCROLL_NO_MESSAGE
        and u32(data, object_data + SCROLL_SPELL_OFFSET_AFTER_FLAG)[0] == TOWN_PORTAL
    ):
        print(f"scroll  x={x} y={y} z={z} offset=0x{off:X}")

    if (
        data[object_data] == SCHOLAR_REWARD_SPELL
        and data[object_data + SCHOLAR_REWARD_VALUE_OFFSET] == TOWN_PORTAL
    ):
        print(f"scholar x={x} y={y} z={z} offset=0x{off:X}")

Проверяю на лабораторной карте со свитком:

python .\find_tp_short.py .\raw\hota_clean_scroll_02_town_portal_x10_y10_z0.h3m

Вывод:

scroll  x=10 y=10 z=0 offset=0x2B46

Теперь на карте с учёным:

python .\find_tp_short.py .\raw\hota_clean_scholar_01_town_portal_x10_y10_z0.h3m

Вывод:

scholar x=10 y=10 z=0 offset=0x2B47

И ещё контрольный запуск на свитке с Magic Arrow. Там скрипт ничего не выводит, потому что это не Town Portal.

Этот скрипт специально маленький и честно привязан к лабораторным паттернам. Он ещё не полноценный парсер объектов на произвольной карте. Зато он показывает главное: как найденные в HxD байты превращаются в первые проверки на Python.

Готовый парсер на Python

В этом месте я перескочу сразу к парсеру. Ибо логика выше понятна: если так же идти дальше по объектам, можно выдрать уже почти всё, что нужно.

Полный код я выложил на GitHub: hota-map-parser.

Как запустить у себя на компе:

Нужен Python 3.10 или новее.
Скачиваем репозиторий. Можно через зелёную кнопку Code -> Download ZIP на GitHub, а можно через консоль:

git clone https://github.com/Alexmod/hota-map-parser.git
cd hota-map-parser

Кладём .h3m-карту HOTA в эту папку или просто указываем путь к карте в команде.
Запускаем:

python .\analyze_h3m.py ".\my_map.h3m" summary

Внешних библиотек не надо, pip install тут не нужен.

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

PS> python .\analyze_h3m.py
Использование:
 python analyze_h3m.py "<map.h3m>" summary
 python analyze_h3m.py "<map.h3m>" spell "Town Portal"
 python analyze_h3m.py "<map.h3m>" artifact "Golden Bow"
 python analyze_h3m.py "<map.h3m>" hero "Gelu"
 python analyze_h3m.py "<map.h3m>" prisons
 python analyze_h3m.py "<map.h3m>" camps
 python analyze_h3m.py "<map.h3m>" debug

Codex

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

Если хотите попробовать так же, то схема примерно такая:

Скачиваете или клонируете репозиторий hota-map-parser.
Кладёте в эту папку карту, которую хотите разобрать.
В Codex создаёте новый проект и прикрепляете папку с парсером.
Проверяете, что рядом с analyze_h3m.py лежит AGENTS.md. Это файл с инструкциями для агента: какой скрипт запускать, какие команды есть, что координаты надо давать как (x, y, z) и так далее.

После этого можно писать ему не «запусти такую-то команду», а просто: «где на этой карте взять Town Portal?» или «есть ли тут Джелу в тюрьме?». Codex сам лезет в папку, запускает analyze_h3m.py и пересказывает результат уже по-человечески.

Скриншоты моих бесед:

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

Enjoy.