Этот пост является частью серии, озаглавленной Обратное проектирование игры Gameboy Advance. Прочтите введение здесь. Прочтите предыдущий пост здесь.
Подписывайтесь на меня в Twitter, чтобы получать больше удовольствия от компьютера 🐦
В прошлой главе нам удалось найти, где хранится тайловая карта в Slow WRAM. Круто!
Но откуда эти данные? Учитывая, что не существует другого «WRAM», кроме медленного и быстрого, можно предположить, что источником данных будет сам игровой картридж, то есть ПЗУ!
Если эта гипотеза подтвердится, это будет особенно важно и полезно для нас, так как нам нужен файл с этими данными для рисования тайловой карты в редакторе. В этом случае мы должны извлечь данные с помощью IDA, поскольку, в отличие от No $ GBA, IDA имеет функцию, которая позволяет извлекать данные из памяти в файл.
Поэтому давайте продолжим процесс, по которому мы шли: начнем из B, чтобы найти источник A! Потоки примерно такие:
С философской точки зрения, этот поток бесконечен в обоих направлениях. Мы могли бы растянуться влево, включая электронику картриджа или мышление дизайнера уровней, создавшего такой уровень, точно так же, как мы могли бы растянуться вправо, когда игрок видит уровень. Однако этого подмножества достаточно для нашего случая.
Таким образом, нам нужно найти, где уровень хранится в ПЗУ, и понять, как он хранится. В конце концов, он, вероятно, будет сжат, поскольку разработчики часто сжимают ресурсы игры.
В разговоре с несколькими коллегами они всегда говорили, что со сжатием тайловой карты будет сложно справиться, потому что помимо определения того, где хранится тайловая карта, мне нужно было бы выяснить, какой алгоритм сжатия был использован, поскольку мне нужно было бы воспроизвести его. для извлечения данных из ПЗУ, а также в инструменте редактора уровней.
Ну… Но IDA показывает интересный график использования памяти на картридже, и кое-что, что привлекло мое внимание, было то, что там был большой пространство зазора. Поэтому я подумал: «Эй, а нельзя ли сжать карту тайлов? В конце концов, есть много пробелов ... "
Чтобы подтвердить эту гипотезу, я скопировал часть тайловой карты, которую видел в No $ GBA, и поискал ее в ПЗУ в IDA, используя функцию Последовательность байтов (Alt + B). < br /> И, к сожалению, не нашел. Что ж, тогда он действительно должен быть сжат ... и с использованием какого-то алгоритма сжатия, который я еще не знаю ...
Самое близкое, что мы получили к источнику тайловой карты, - это медленное WRAM, и тайлы нашего моста расположены по адресу 02008432. Хорошо, поэтому мы собираемся взглянуть на него, чтобы сделать вывод, где тайловая карта начинается в медленном WRAM (как я уже объяснял, тайловая карта представляет собой очень характерную структуру: она разделена множеством нулей, оставляя небольшой набор разных байтов и различные байты одного и того же значения, повторяющиеся последовательно). Исходя из этого, я смог сделать вывод, что он начинается с 020039EB или с какого-то адреса поблизости.
Поэтому давайте продолжим нашу классическую и утомительную пошаговую отладку ... На этот раз нам нужно запустить уровень в игре и определить, когда начнет рисоваться тайловая карта.
Сделав это, я получил важную инструкцию на адрес 08051440: swi 0x11. Вскоре после этого будет написана часть тайловой карты:
Вы помните swi? Я уже кратко говорил об этой инструкции раньше, а теперь мне нужно объяснить ее более подробно, так как с этого момента мы будем ее часто использовать.
«swi» - это сокращение от программных прерываний (также называемых вызовами BIOS) - это уже дает вам ключ к разгадке, верно? GameBoy Advance имеет BIOS. В общих чертах архитектуры компьютера BIOS - это микропрограммное обеспечение, целью которого является инициализация физических компонентов системы, к которой он подключен, а также их сопоставление с системой, которая будет управлять устройством.
Эти «физические компоненты» упомянутыми могут быть, например, клавиатура и мышь. Однако устройство может состоять из другого, более специализированного оборудования, которое предоставляется системе как «функции», будучи очень быстрым, поскольку оно очень близко к металлу. В случае GBA, который представляет собой аппаратное обеспечение, специализированное для игр, BIOS предоставляет различные функции, часто используемые в играх, такие как управление музыкой и вычисление арктангенсов… и среди этих функций также есть компрессор и декомпрессор данных! Каждая функция имеет связанное числовое значение, которое необходимо передать в качестве параметра инструкции swi.
В этом случае инструкция swi 0x11 раскрывает алгоритм декомпрессии LZ77, который очень полезен, когда есть части повторяющихся данных (а в тайловой карте у нас есть именно это!) . Очень любопытно думать, что GBA, относительно небольшая и дешевая консоль, уже имела мощные алгоритмы сжатия, выполнявшиеся на аппаратном уровне в 2000-х годах. Способ «передачи параметров» и «получения возврата функции» для инструкций swi очень своеобразен: в основном это делается через регистры. Взгляните на пример в функции div (swi 0x06):
Ввод:
- R0: числитель
- R1: знаменатель
Вывод:
- R0: числитель / знаменатель
- R1: числитель% знаменатель
- R2: абс (числитель / знаменатель)
Если вам нужен более общий взгляд на swi, вы можете прочитать эту главу в руководстве GBA.
После всего этого давайте проанализируем найденную нами инструкцию: swi 0x11.
Согласно спецификации GBA, 0x11 относится к LZ77UnCompWram . Адрес, по которому он будет собирать данные для распаковки, определяется в R0, а место назначения, куда будет записан результат, - это адрес, указанный в R1.
Части головоломки начинают складываться вместе, если посмотреть на значения этих регистров незадолго до выполнения swi 0x11:
Значение R1 (адрес вывода распаковки) очень близко к тому, что мы сказали, это адрес, с которого начинается мозаичная карта, от 020039CC до 020039EB ! Но теперь нам нужно понять, откуда пришли данные, адрес, на который указывает R0: 0200F698…
Глядя на сборку, мое внимание привлекла строка перед swi 0x11, инструкция swi 0x13:
Согласно спецификации, swi 0x13 относится к HuffUnComp, который выполняет декомпрессию с использованием другого алгоритма: Хаффмана. Он также использует R0 как адрес ввода и R1 как адрес вывода.
И, поставив там точку останова, проверьте: он пишет точно туда, где вскоре после этого будет прочитана другая инструкция swi! Кроме того, он получает свои данные непосредственно из ПЗУ по адресу 0x81B27FC !!
Другими словами: разработчики игры решили сжать уровень, используя два алгоритма сжатия, а между выполнением один, а другой - временный буфер.
Комбинация Хаффмана и LZ77 очень популярна при изучении и общении с другими людьми. В то время как LZ77 удаляет повторение в части данных, Хаффман уменьшает количество символов в последовательности пропорционально ее частоте. Этот ответ на Stack Overflow поясняет, почему разработчики решили использовать оба в игре Klonoa. Существует очень популярный алгоритм, который точно описывает использование этих двух алгоритмов вместе: deflate. Этот алгоритм используется в таких форматах, как ZIP и PNG.
Хорошо. Давайте перейдем к адресу в ПЗУ, который служит источником для распаковки тайловой карты, то есть к адресу 0x81B27FC.
Обратите внимание, что в IDA Pro очень хороший статический анализ, так что достаточно оставить курсор на одной из строк сборки или на одном из байтов адреса, когда вы находитесь в шестнадцатеричном представлении. mode, а там уже написано, как далеко заходит этот дамп памяти. И нам легко удается извлечь это в файл с помощью инструмента Экспорт данных (shift + e) !
Но нет особой пользы в том, чтобы иметь только сжатый двоичный файл тайловой карты, верно? Итак, нам нужно найти способ распаковать его!
Первая идея, которая пришла в голову для этого, заключалась в изучении двух используемых алгоритмов сжатия ... и ... ну ... Моя голова кружилась, просто пытаясь понять их, и так что представьте, когда дойдет до реализации всего этого ?? Кроме того, GBA мог бы использовать другую версию этих алгоритмов, что еще больше усложнило бы его…
И тогда я подумал о лучшей идее: давайте воспользуемся одним из самых больших преимуществ разработки чего-либо с использованием очень популярной консоли. , сообщество!
Итак, я начал осматриваться, чтобы увидеть, не разработал ли кто-нибудь код для сжатия / распаковки данных с использованием алгоритмов GBA… и посмотрите, кто-то уже сделал именно это!
Кто-то в 2011–2012 годах написал код C с открытым исходным кодом с различными алгоритмами сжатия / распаковки для GBA, вам просто нужно передать путь к сжатому файлу исполняемому файлу, и он будет перезаписан распакованной версией. Потрясающе, не правда ли? Так что давайте использовать его!
Нам нужно воссоздать те же шаги, что и в игре: сначала распаковать с помощью Хаффмана, а затем с помощью LZ77.
Когда я начал распаковывать двоичный файл с помощью ./huffman.exe -d dump, я получил сообщение «ПРЕДУПРЕЖДЕНИЕ: неожиданный конец закодированного файла!» ... ну ... для момент, я проигнорировал это, давайте посмотрим, что произойдет.
Когда я пошел распаковывать LZ77, я заметил, что было несколько похожих исполняемых файлов: lze, lzss и lzx. Поскольку у меня были некоторые сомнения относительно того, какой из них будет правильным, я протестировал декомпрессию со всеми из них, и только lzss работал правильно (я считаю, что lzss = lz seven-seven = LZ77) с помощью команды ./lzss.exe -d dump, но снова я получил то же предупреждение: «ВНИМАНИЕ: неожиданный конец закодированного файла!»
Я снова получил сообщение говоря, что у него неожиданный конец ... и я увидел, что файл, полученный в результате распаковки, хоть и был правильным, но был неполным: он содержал начало тайловой карты уровня, но не был полным.
Связывая этот факт с предупреждением сообщения, очень ясно, что это из-за отсутствия данных для распаковки, но это странно, поскольку я извлек всю часть, которую IDA выбрала автоматически !! Может быть, мне нужно было извлечь немного больше? Проверка этой гипотезы ничего не стоит, так что вперед!
Как я уже описал, после установки точки останова на инструкции swi 0x11 мне удалось увидеть, когда она начала распаковывать карту листов. И еще одна деталь: эта инструкция вызывается не один раз. Так что, безусловно, есть еще один дамп в ПЗУ, который нам нужно извлечь. Поэтому я использовал IDA для извлечения рядом с автоматически выбранной областью в 0x81B27FC всей автоматически выбранной части после нее. Извлекая эти две области памяти, я смог запустить исполняемые файлы декомпрессии, не получая никаких предупреждений!
И теперь, сравнивая двоичный файл с тем, что я вижу в памяти в No $ GBA, тайловая карта полностью извлечена !!
Это просто фантастика, так как теперь нам удалось извлечь тайловую карту из ПЗУ, а также понять, как это работает !!! Теперь мы как никогда близки к построению тайловой карты в нашем редакторе для создания пользовательских уровней! Но всегда помните: все началось с очень простого вопроса: «Как я могу растянуть мост?»
Конечно, есть еще много вопросов, на которые нужно ответить, например, «у нас есть« линейный »дамп памяти, так как нам построить карту тайлов, которая представляет собой 2D-плоскость?» а также возникает гораздо более очевидный вопрос: «как мы собираемся все это строить?»
Мы ответим на все эти вопросы в следующей главе!
