Spiiin's blog | Уровни Jungle Book [NES]. Часть 1.

Уровни Jungle Book [NES]. Часть 1.

2011/10/20

//Лучший способ научиться программированию - взять дизассемблер и посмотреть, как это делают другие.

Шаг 0xFF.
Когда-то давно у меня было несколько выпусков журнала “Великий Дракон”, в которых были опубликованы карты уровней из “Утиных историй”. Но только там были швы на границах сшитых скриншотов и на каждом экране была копия Скруджа. Я вспомнил про эти карты и подумал, что было бы неплохо научиться вырывать из картриджа с игрой карты уровней в том формате, в котором они там и записаны. Технически это, конечно, немножко сложнее, чем слепливать скриншоты, но зато можно разобраться с методикой. В каждой игре используется свой способ хранения (разве что может у игр с одинаковым движком будет одинаковый формат), но можно выделить общие действия.

Шаг 0x00.
Кроме обучения, можно использовать результат и в практических целях:

Планирование способов прохождения.
Наглядная подсказка.
Обнаружение неизвестных ранее секретных зон.
Анализ дизайна уровней.
Пиратское копирование уровней или графики в другую игру.
Модификация уровня и/или создание редактора уровней.
Распечатывание и развешивание на стены в качестве обоев.

Но карты для Duck Tales мне были не особо нужны, потому что они не особо запутанные и спустя годы я все равно помню все секретные проходы и оптимальные пути и сомневаюсь в наличии неизвестных ранее сокровищ и секретов, еще не открытых обычными геймерами. Поэтому интереснее выбрать игру с лабиринтами, в которых можно заблудиться и ограничено время, за которое необходимо найти выход. Из известных мне игр на NES сходу вспомнились Jungle Book и Alien 3. Маугли повезло больше, поэтому я стал рипать уровни из рома Jungle Book[E].nes.

Под катом спрятано техническое описание процесса вырезания и сами карты.

Шаг 0x01.
Необходимые инструменты - эмулятор NES со встроенным отладчиком и просмотром состояния памяти консоли (FCEUXSP), дизассемблер, бумага и ручка. Также очень не помешает знание какого-нибудь языка программирования, чтобы автоматизировать рассчеты, так как считать и рисовать придется довольно много.

Шаг 0x02.
Отрисовка графики фона на NES.
Консоль умеет рисовать бекграунд и до тридцати двух спрайтов. Чтобы вывести полноэкранный бекграунд, необходимо выключить вывод фона видеопроцессором, и записать в видеопамять по адресу $2000 960 байт. Каждый байт означает номер тайла размером 8х8 в знакогенераторе (в знакогенератор загружается 1 блок графики из картриджа размером в 4 килобайта, который содержит 256 инонок-тайлов, по 2 бита на пиксел). Так выкладывается 30 строк по 32 элемента.
Далее по адресам $23C0-$23FF в видеопамять записывается 64 байта атрибутов и каждому квадрату размером 2х2 тайла приписывается еще 2 бита цвета из атрибута. С помощью этого можно подкрасить двухбитовые пикселы тайлов до четырехбитовых. Эти 4 бита являются индексом в палитре, которая позволяет выбрать 16 цветов из 64 поддерживаемых видеопроцессором. Палитра расположена по адресу $3F00. Далее необходимо снова включить отрисовку фона и видеопроцессор обновит картинку на экране. Кроме того, через регистры процессора можно скроллить фоновую картинку по горизонтали и вертикали, поэтому чтобы передвинуть бекграунд вправо или влево, необязательно перерисовывать всю картинку целиком, достаточно включить аппаратный скроллинг и дорисовывать только новые столбы и строки.
Управление видеопроцессором осуществляется записью по определенным адресам CPU.
Подробнее про отрисовку можно почитать в доке Migera.

Шаг 0x03.
Эмулятор FCEUXSP умеет отображать содержимое знакогенератора и текущую палитру (Tools->PPU Viewer), содержимое экранной страницы (Tools->Name Table Viewer), либо просто просматривать видеопамять (Tools->Hex Editor, View->Ppu memory). Еще встроенный отладчик позволяет ставить точки остановки на запись в видеопамять, и можно начать процесса взлома с того, чтобы поставить точку остановки на запись в видеопамять в диапазоне $2000-$23BF (то есть любое обновление экрана). Точка остановки срабатывает от нажатия на кнопку старт в главном меню игры до запуска первого уровня несколько раз, поэтому включать её стоит, когда уровень уже начался, чтобы поймать только обновление экрана.
Остановка сработает в тот момент, когда экран сдвинется вправо или влево и отладчик покажет адрес выполнения $E38C (инструкция STA $2007). В этот момент следует сделать дамп памяти Tools->Hex View и загрузить его в дизассемблер. Как это делается, хорошо описано здесь.
Новые дампы памяти надо делать каждый раз, когда в отладчике обнаруживается, что данные в области ROM’а (от $8000 до $FFFF) отличаются от тех, что видны в дизассемблере. Это происходит потому, что на картридже могут иметься несколько банков памяти, которые подставляются в адресное пространство процессора (вроде бы плоское), добавляя ему второе измерение. Про переключение банков я знаю пока мало, для этого надо вчитываться в доки по мапперам, а некоторые из них еще нерасшифрованы полностью, поэтому отслеживаю соотвествие кода в дампе тому, что отображает просмотрщик памяти в эмуляторе.
Функция, на которой остановился отладчик - горизонтальный скроллинг экрана, дорисовка нового столбца слева или справа. Данные копируются из оперативной памяти по адресу $040D и дальше в видеопамять.

Шаг 0x04.
Точка остановки переставляется на запись в адреса около $040D и срабатывает при очередном горизонтальном скроллинге, когда Маугли бежит вперед.
ROM:8462 LDA ($95),Y
ROM:8464 STA $40D,X
ROM:8467 LDA ($99),Y
ROM:8469 STA $40E,X
ROM:846C LDA ($71),Y
ROM:846E JMP loc_847D
ROM:8471 ; —————————————————————————————————————-
ROM:8471 LDA ($93),Y ; что-то типа записи в столбик, из которого будет перенос в видеопамять
ROM:8473 STA $40D,X
ROM:8476 LDA ($97),Y
ROM:8478 STA $40E,X
ROM:847B LDA ($6F),Y

Столбик заполняется данными из адресов, записанных либо в ячейки 95-96 и 98-99, либо в ячейки 93-94 и 97-98. Такая адресация - злейший враг для хакера по двум причинам. Во-первых, чтобы проверить, какие адреса находятся в нулевой странице (по адресам $00-$FF, нужно каждый раз смотреть их в дизассемблере, что добавляет в код третье измерение и сильно усложняет восприятие, а во-вторых, брейкпоинты на чтение, поставленные на нулевую страницу, не работают, так как чтение значения из нее не производится, а происходит вычисление адреса относительно того, что записано в эти ячейки памяти.
Я проверяю, что за адреса лежат в этих ячейках памяти на каждом шаге в поисках закономерности - каждые 4 шага адреса повторяются, но это не позволяет разобраться, откуда они берутся.

Шаг 0x05.
Дальше проверяю то, откуда берутся адреса в ячейках 93-98. Брейкнулся в кусок функции:
ROM:856B LDY $DD88,X
ROM:856E LDA 0,Y
ROM:8571 STA byte_83
ROM:8573 LDA 1,Y
ROM:8576 STA byte_84
ROM:8578 LDA 4,Y
ROM:857B STA byte_85
ROM:857D LDA 5,Y
ROM:8580 STA byte_86
ROM:8582 LDY $DD8C,X
ROM:8585 LDA 0,Y
ROM:8588 STA byte_87
ROM:858A LDA 1,Y
ROM:858D STA byte_88
ROM:858F LDA 4,Y
ROM:8592 STA byte_89
ROM:8594 LDA 5,Y
ROM:8597 STA byte_8A
ROM:8599 LDY $DD90,X
ROM:859C LDA 0,Y
ROM:859F STA byte_93
ROM:85A1 LDA 1,Y
ROM:85A4 STA byte_94
ROM:85A6 LDA 4,Y
ROM:85A9 STA byte_95
ROM:85AB LDA 5,Y
ROM:85AE STA byte_96
ROM:85B0 LDY $DD94,X
ROM:85B3 LDA 0,Y
ROM:85B6 STA byte_97
ROM:85B8 LDA 1,Y
ROM:85BB STA byte_98
ROM:85BD LDA 4,Y
ROM:85C0 STA byte_99
ROM:85C2 LDA 5,Y
ROM:85C5 STA byte_9A
ROM:85C7 RTS

Отсюда видно, что в роме (область $DDxx - уже области памяти картриджа) есть массивы указателей, которыми индексируется какие-то ячейки оперативной памяти (какие именно показывает регистр Y), и данные из этих ячеек переносятся дальше. Тут непонятно, откуда берется X и Y, но вместо дальнейшего реверс-анализа я смотрю их изменение во времени при нескольких последовательных скроллингах. X меняется последовательно от 0 до 3, а Y не совсем понятно как, но адреса находятся примерно в диапазоне $60-$80. Много их там быть не может, потому что эта область - оперативная память и расходовать ее много нельзя ввиду ее небольшого размера. Поэтому лучше ставить точки остановки на как можно меньшее число адресов в этой зоне, так как иногда одна и та же ячейка может за один кадр использоваться в разных целях (например для рассчета позиций врагов). Так что в качестве следующей точки остановки выбрал ячейки $67-$68

Шаг 0x06.
Следующая остановка показывает, что запись в эти ячейки производится 1 раз при старте уровня (сразу после затухания экрана LEVEL 1 GET READY) по адресу $F542 (STA 0047,Y). Сделав в отладчике step out , доходим до выхода из функции, засекаем ее начало и делаем дамп памяти, чтобы засунуть его в дизассемблер. Это - функция загрузки уровня. По адресу 35D хранится номер уровня, служащий индексом для таблицы смещений , где лежит набор адресов, копирующих в набор - диапазон 47-82.
ROM:F52F LDA byte_35D ; взять номер уровня
ROM:F532 ASL A ; (адрес занимает 2 байта)
ROM:F533 TAX
ROM:F534 LDA $F71A,X ; загрузить из F71A адрес начала таблицы смещений уровня
ROM:F537 STA byte_21
ROM:F539 LDA $F71B,X
ROM:F53C STA byte_22
ROM:F53E LDY #$3B ; ‘;’
ROM:F540 LDA ($21),Y ; копирование адреса в набор 47-82 для уровня
ROM:F542 STA $47,Y
ROM:F545 DEY
ROM:F546 BPL loc_F540 ; копирование адреса в набор 47-82 для уровня
ROM:F548 LDY #$46 ; ‘F’ ; дальше еще полкилобайта какого-то кода

Чуть про философию реверса - выбор названий для переменных здесь намного важнее, чем в обычном программировании, потому что, разбираясь с кодом алгоритма, изначально есть только адреса, по сути анонимные переменные , по аналогии с анонимными функциями. А воспринимаемый набор действий над такими переменными без названия имеет только образ, без определения. Мысленно можно построить только граф выполнения, временную развертку команд над адресами. Распознавание в командах действий позволяет заменить граф последовательностью функций, а распознавание назначения адресов - разделить безымянное адресное пространство на области, имеющие определенное предназначение. Чтобы привести алгоритм к известному, надо подобрать такие названия областей, чтобы по ним было понятно их содержимое. Ну и необходимо помнить, что ввиду малого количества памяти эти области могут перекрываться и использоваться в различных целях, то есть в данном месте значения в ячейках 42-83 являются набором стартовых адресов при загрузке уровня, а по окончании уже могут быть например, количеством набранных за уровень очков или еще чем-нибудь.

Шаг 0x07.
Начиная с обнаружения функции загрузки, можно не лезть дальше вглубь в сам ROM, а расшифровать ее, то есть понять назначение ячеек, в которые считываются данные. Здесь стоит подумать, что именно необходимо искать. Из предыдущего опыта разбора игровых данных в Охотниках за привидениями, я запомнил, что запись об уровне может иметь сложный формат, содержать вперемежку код логики игровых событий и данные. Так что, скорее всего, здесь тоже применяется какой-нибудь метод для сжатия игровых данных. Так что при анализе вверх от данных из рома к видеопамяти придется разобраться еще с функцией расшифровки данных и сэмулировать ему на каком-нибудь языке. Однако и возможность того, что данные лежат целым блоком, тоже есть. Так что стоит придумать способ отрисовки картинки уровня по какому-либо набору данных. Чтобы найти этот набор, можно взять любой адрес начала записи об уровне и попытаться разделить в нем код и данные. Правило визуального отделения данных и кодов - данные обладают когерентностью (соседние похожи между собой), коды - не обладают. Еще можно узнавать шаблоны кодов (зная коды команд, содержащих в операнде непосредственный адрес (jmp и lda с некоторыми типами адресаций) + код rts для конца функций, можно находить в коде адреса, и попробовать ассемблировать эти куски в дизассемблере). Вообщем, даже если начать рисовать смесью кодов и данных, то все равно можно найти какой-то осмысленный кусок и понять структуру. Так что дальше надо написать программу рисования и скормить ей все данные об уровне.
Как было сказано выше, для получения этих данных можно не лезть глубже, а начать вместо обратного просмотра прямой, отслеживая данные от момента считывания из РОМа в зону 47-82 ( набор ) до попадания прямо на экран.
Начинаем выныривать.
ROM:F71A .WORD $B6E3 ; адреса начала смещений уровней и бонусных зон (всего по 72, хотя под карту юзаются 59, дальше что-то еще).
ROM:F71C .WORD $B72B
ROM:F71E .WORD $B773
ROM:F720 .WORD $B7BB
ROM:F722 .WORD $B803
ROM:F724 .WORD $B84B
ROM:F726 .WORD $B893
ROM:F728 .WORD $B8DB
ROM:F72A .WORD $B923
ROM:F72C .WORD $B96B
ROM:F72E .WORD $BBAB
ROM:F730 .WORD $BB63
ROM:F732 .WORD $B9B3
ROM:F734 .WORD $B9FB
ROM:F736 .WORD $BA43
ROM:F738 .WORD $BA8B
ROM:F73A .WORD $BAD3
ROM:F73C .WORD $BB1B
ROM:F73E .WORD $BBAB

Шаг 0x08.
Скрипт рисования. На питоне, для работы с изображениями нужна библиотека PIL.

#Класс инкапсулирует данные об одном тайле и позволяет сравнить тайлы с учетом палитры.
class PpuSprite:
   def __init__(self, im):
     self.image = im
     self.imageData = im.getdata()
     self.colorTable = im.getcolors()
     self.colorTable.sort()
     self.firstColorsPos = [] 
     self.calcFirstColorsPoses()
     self.indexedData = []
     self.prepareIndexedData()
 
   def calcFirstColorsPoses(self):        
     for _,colorInPalette in self.colorTable:
       firstColorPos = -1
       for color in self.imageData:
         firstColorPos+=1
         if color == colorInPalette:
           break
       self.firstColorsPos.append((firstColorPos,colorInPalette))
     self.firstColorsPos.sort()
 
   def prepareIndexedData(self):
     def calcColorHash(c):
       return c[0]<<16 | c[1]<<8 | c[2]
     colorHashes = map (lambda colorRec : calcColorHash(colorRec[1]), self.firstColorsPos)
     for pixel in self.imageData:
       pixelHash = calcColorHash(pixel)
       colorIndex = -1
       for colorHash in colorHashes:
         colorIndex +=1
         if pixelHash == colorHash:
           break
       self.indexedData.append(colorIndex)
 
   def isEqual(self, otherPpuSprite):
     if len(self.firstColorsPos) != len(otherPpuSprite.firstColorsPos):
       return False
     for fcp1, fcp2 in zip(self.firstColorsPos, otherPpuSprite.firstColorsPos):
       if  fcp1[0]!= fcp2[0]:
         return False
     if len(self.colorTable) != len(otherPpuSprite.colorTable):
       return False
     for colorTableRec1, colorTableRec2 in zip(self.colorTable, otherPpuSprite.colorTable):
       if colorTableRec1[0] != colorTableRec2[0]:
         return False
     for pixel1, pixel2 in zip(self.indexedData, otherPpuSprite.indexedData):
       if pixel1!=pixel2:
         return False
     return True

Дальше следует захватить из эмулятора блок с тайлами текущего уровня и распилить его на кусочки. FCEUXSP позволяет только посмотреть этот блок (View->Name Table View), но можно заскриншотить его и вырезать в любом графическом редакторе. Вот так выглядит блок для первого уровня:

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

imNameTable = Image.open(os.path.expanduser("~/desktop/jungleBook/jungleBookTable1.png"))   #сохраненная таблица тайлов.
imLevelTable = Image.open(os.path.expanduser("~/desktop/jungleBook/jungleBookLevel1.png"))  #любой скриншот уровня, загружается для теста
nameSize = imNameTable.size
levelSize = imLevelTable.size
nameTable = [imNameTable.crop((x,y,x+8,y+8)) for y,x in itertools.product(xrange(0,nameSize[1],8),xrange(0,nameSize[0],8))]
levelTable = [imLevelTable.crop((x,y,x+8,y+8)) for y,x in itertools.product(xrange(0,levelSize[1],8),xrange(0,levelSize[0],8))]
ppuSpriteMemTable = map (lambda im: PpuSprite(im),nameTable) 
ppuSpriteLvlTable = map (lambda im: PpuSprite(im),levelTable)

Функция отрисовки по массиву тайлов (принимает линейный массив данных, таблицу спрайтов, размер уровня и флажок, построчно или постолбцово рисовать, возврашает экземляр класс PIL Image):

def drawLevelFromData(levelArray, ppuSpriteTable, size, vertical = False):
  w,h = size
  im = Image.new("RGBA", (w*8,h*8))
  for i in xrange(len(levelArray)):
    if vertical:
      x,y = i/h, i%h
    else:
      x,y = i%w, i/w
    ind = levelArray[i]
    if (ind!=-1):
      im.paste(ppuSpriteTable[ind].image, (x*8,y*8,x*8+8,y*8+8))
  return im

Чтобы проверить программу рисования и корректность сравнения по индексированным цветам, превратим скриншот уровня в данные и отдадим этой функции.

def findFirstPicIndex(sprite, ppuSpriteTable):
  index = -1
  for ppuSprite in ppuSpriteTable:
    index+=1
    if ppuSprite.isEqual(sprite):
      return index
  return -1
 
def makeLevelMap(mem, lev):
  levTable = []
  for l in lev:
    levTable.append(findFirstPicIndex(l, mem))
  return levTable
 
mapLevel = makeLevelMap(ppuSpriteMemTable, ppuSpriteLvlTable)
drawLevelFromData(mapLevel, sprites,(WIDTH,HEIGHT),True).show()

На выходе можно увидеть уровень, выглядящий примерно как рендер Матрицы на компьютере с недостаточной мощностью:

Шаг 0x09.
Дальше я попытался отрисовать данные уровня разными способами, ничего интересного не получил, и понял, что надо все-таки еще искать функцию-комбинатор, которые будет определять, как данные из набора попадают на экран . Набор смещений 47-82 для первого уровня по адресу $B6E3
A139 A739 DDC8 DDC8 DBF4
DC59 AA49 AAC0 DCBE DD23
AB37 ABAE D974 D9F4 A7C9
A849 DA74 DAF4 A8C9 A949
DB74 A9C9 BBF3 A825 A795
A765 A764 A766 A7F5 A7C5
Точка остановки на чтение этих значений. $8D62 в новом банке памяти (надо сделать еще один дамп), анализ кода там:
берем 4 бита шагов (2 горизонт, 2 вертикаль) и используем их как смещение от адреса DDA8
ROM:DDA8 .WORD $4F4F ; idle вторая часть (адреса из набора )
ROM:DDAA .WORD $5151
ROM:DDAC .WORD $4F4F
ROM:DDAE .WORD $5151
ROM:DDB0 .WORD $5757
ROM:DDB2 .WORD $5959
ROM:DDB4 .WORD $5757
ROM:DDB6 .WORD $5959
и переносим их в 8b-8e
потом повторно берем из DDB8 и переносим в 9b-9e:
ROM:DDB8 .WORD $615F ; idle вторая часть(адреса из набора )
ROM:DDBA .WORD $615F
ROM:DDBC .WORD $6967
ROM:DDBE .WORD $6967
ROM:DDC0 .WORD $615F
ROM:DDC2 .WORD $615F
ROM:DDC4 .WORD $6967
ROM:DDC6 .WORD $6967

Это массив направлений , где хранится по 4 значения адресов из набора , которые будут скопированы по адресу предэкран (назовем так адреса 9B-9E и 8B-8E, потому что там лежат адреса массивов, из которых будут считаны номеры тайлов, попадающих в зону экрана $40E-$423).

Продолжение