[Перевод] Перепрограммирование GameBoy за счёт бага в Pokemon Yellow

Pokemon Yellow — это карманная вселенная со своими правилами. В ней можно покупать и продавать предметы, тренировать покемонов, побеждать других тренеров — но нельзя менять правила самой игры. Нельзя построить себе дом, поменять музыку или даже переодеться. Точнее, так было задумано. На самом деле есть последовательность валидных команд (типа перемещения из одного места в другое и манипуляций с предметами), которая позволяет превратить игру в Pacman, тетрис, Pong, MIDI-проигрыватель и что угодно ещё.

Существует спидран Felipe Lopes de Freitas (p4wn3r), в котором Pokemon Yellow проходится за 1 минуту 36 секунд. Этот спидран основан на следующем хаке: в норме инвентарь игрока ограничен 20 предметами. Но есть баг, который позволяет игнорировать это ограничение и обращаться с памятью, расположенной сразу после инвентаря, как будто бы это был список предметов. Соответственно, стандартные манипуляции с предметами позволяют эту память переписывать. Спидраннер использует эту возможность, чтобы заставить дверь из стартовой комнаты переносить его на финальную локацию, в которой ему остаётся только выслушать поздравления.

Когда я впервые увидел этот спидран и понял, что памятью Gameboy можно манипулировать с помощью одного только списка предметов, безо всяких внешних инструментов, я решил посмотреть, получится ли у меня усовершенствовать приёмы p4wn3r. Вот что получилось:

Gameboy — это восьмибитный компьютер. Соответственно, всё происходящее в игре — результат того, что исполняется некая последовательность однобайтовых команд. Например, последовательность[62 16 37 224 47 240 37 230 15 55] в местных машинных кодах означает, что надо выяснить, какие кнопки нажаты в данный момент, и записать результат в регистр A. Можно создать программу, которая будет читать ввод с кнопок и записывать куда-нибудь в память исполняемый код, а потом передавать ему управление. Если удастся каким-то образом засунуть такую программу (назовём её программой ввода) в память и заставить Gameboy её исполнить — то я выиграл, потому что теперь я могу исполнять произвольный код (скажем, тетрис) вместо Pokemon Yellow. 

Во-первых, как написать такую программу? Восьмибитными числами представлены не только правила, но и состояние игры (инвентарь, список покемонов, имя главного героя и т.п.) Инвентарь хранится вот так:

item-one-id         (0-255)
item-one-quantity   (0-255)
item-two-id         (0-255)
item-two-quantity   (0-255)
.
.
.

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

lemonade     x16
guard spec.  x224
leaf stone   x240
guard spec.  x230
parlyz heal  x55

Так что если нам удастся собрать нужные предметы в нужном количестве и порядке — то получится код программы ввода. Правда, его с самого начала нужно писать так, чтобы он состоял только из валидных ID и количеств предметов. Это не так-то просто, потому что предметов в игре немного, а многие машинные инструкции состоят из 2-3 битов. Та версия программы, на которой я остановился, состоит из 92 бит; примерно половина из них не делает ничего полезного и вставлена только для того, чтоб код был ещё и корректным списком предметов.

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

Поехали!

Я начинаю с того, что называю своего противника Lp/k. Эти символы в своё время превратятся в предметы и будут перемещены на указатель функции, чтобы я мог исполнить программу ввода. Но сперва её надо записать, так что я начинаю забег так же, как и p4wn3r: перезапускаю игру при сохранении, чтобы сломать список покемонов. После этого я меняю местами 8 и 10 покемона, что ломает список предметов и позволяет мне манипулировать предметами после 20-го (то есть соответствующей областью памяти). С помощью этих манипуляций я выставляю скорость текста на максимум и переключаю свою дверь на магазин Celadon Dept. store. p4wn3r в этот момент переключил её на “Зал славы” и выиграл, но мне неинтересен спидран как таковой.

Поэтому я не останавливаюсь, а выкладываю из своего поломанного инвентаря в сундук множество глитчевых предметов 0x00, которые мне ещё пригодятся. Потом я забираю из сундука зелье, что вызывает переполнение счётчика предметов с 0xFF на 0x00 и восстанавливает мой инвентарь. Зелье при этом, правда, исчезает. После этого я забираю 255 0x00-предметов и отправляюсь в магазин. Там я продаю 2 0x00 за 414925 монет каждый, что позволяет мне купить следующие предметы:

+-------------------+----------+
|##| Item           | Quantity |
+--+----------------+----------+
|1 | TM02           |  98      |
|2 | TM37           |  71      |
|3 | TM05           |   1      |
|4 | TM09           |   1      |
|5 | burn-heal      |  12      |
|6 | ice-heal       |  55      |
|7 | parlyz-heal    |  99      |
|8 | parlyz-heal    |  55      |
|9 | TM18           |   1      |
|10| fire-stone     |  23      |
|11| water-stone    |  29      |
|12| x-accuracy     |  58      |
|13| guard-spec     |  99      |
|14| guard-spec     |  24      |
|15| lemonade       |  16      |
|16| TM13           |   1      |
+--+----------------+----------+

Эти предметы я раскладываю в инвентаре в таком порядке, чтобы получилась моя первая программа ввода. Первая — потому что написать окончательную версию программы ввода внутри игры у меня не получилось. Та, которую я собираю из предметов, умеет читать только кнопки A, B, start и select. Каждый фрейм игры она пишет 4 бита в определённую область памяти; собрав 200 с лишним байт, она исполняет то, что написала. С помощью этой программы я пишу следующую, которая читает уже все 8 кнопок и пишет произвольное число байтов в произвольную область памяти, а потом исполняет код по произвольному адресу. Эта программа, в свою очередь, используется для загрузки третьей, которая делает всё то же самое, но ещё и выводит записываемый код на экран.

Закончив с кодом первой программы, я отправляюсь в Celadon mansion (это не критично, мне просто нравится локация). Там я снова меняю местами сломанных покемонов и ломаю инвентарь. Проскроллив до имени своего противника, я выкидываю предметы до тех пор, пока имя не окажется на указателе функции. Как только я закрываю меню, программа ввода исполняется, и я могу заливать следующую программу.

Инфраструктура

Всё видео было записано ботами, а сам я к Gameboy (точнее, к эмулятору) даже не притрагивался. Ниже — краткое описание инфраструктуры, которую я создал для этого проекта. Исходники доступны в http://hg.bortreb.com/vba-clojure

Прежде всего, мне нужен был программный доступ к эмулятору, так что я скачал vba-rerecording. Поверх него я написал низкоуровневый интерфейс на C, к которому я смогу обращаться из Java через JNI. Этот интерфейс позволяет обращаться к базовым функциям эмулятора: прогнать один фрейм игры или один тик часов Gameboy, обратиться к любому адресу памяти или регистру. Кроме того, он позволяет выгрузить состояние эмулятора в объект Java или загрузить его обратно.

Поверх JNI я написал обёртку на clojure, так что в итоге у меня получился функциональный интерфейс к vba-rerecording. Этот интерфейс работает с состоянием эмулятора как с иммутабельным объектом и позволяет делать в функциональном стиле всё то, что интерфейс на C позволял делать в императивном. С помощью этого интерфейса я написал функции, которые принимают на вход состояние эмулятора, находят и исполняют последовательность команд, которая приведёт к желаемому эффекту. Из этих функций я собрал высокоуровневые функции, которые выполняют в игре задачи типа перемещения и покупки предметов. Вот, например, код для перемещения кратчайшим путём из магазина покемонов в Viridian City в лабораторию Оака:

(defn-memo viridian-store->oaks-lab
  ([] (viridian-store->oaks-lab
       (get-oaks-parcel)))
  ([script]
     (->> script
          (walk [↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓
                 ← ← ← ← ← ← ← ← ← 
                 ↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓
                 ← ←
                 ↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓
                 ↓ ↓ ↓ ↓ ↓ ↓ ↓
                 → → → → → → → →
                 ↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓
                 ← ← ← ← ←
                 ↓ ↓ ↓ ↓
                 ])
          (walk-thru-grass
           [↓ ↓ ↓ ↓ ↓ ↓ ↓])
          (walk [↓ ↓ ← ↓ ↓ ↓ ←
                 ↓ ↓ ↓ ↓ ↓ ↓
                 → → → ↑])
                
          (do-nothing 1))))

А вот функция, которая находит кратчайшую последовательность команд для переноса нужных предметов в сундук:

(defn-memo hacking-10
  ([] (hacking-10 (hacking-9)))
  ([script]
     (->> script
          begin-deposit
          (deposit-held-item 17 230)
          (deposit-held-item-named :parlyz-heal 55)
          (deposit-held-item 14 178)
          (deposit-held-item-named :water-stone 29)
          (deposit-held-item 14 32)
          (deposit-held-item-named :TM18 1)
          (deposit-held-item 13 1)
          (deposit-held-item 13 191)
          (deposit-held-item-named :TM02 98)
          (deposit-held-item-named :TM09 1)
          close-menu)))

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

Мне особенно пригодились глитч-предметы 0x00 и 0xFF. 0x00 стоит почти половину максимально возможного числа денег, и всего двух хватило на то, чтоб купить все необходимые предметы. К тому же 0x00 — это NO-OP, который я могу вставлять куда угодно, чтобы подогнать программу под требования инвентаря. 0xFF имеет другое полезное свойство. В норме игра объединяет стеки предметов: если купить, например, покеболл, а потом ещё один покеболл, то инвентарь будет выглядеть вот так:

pokeball x2

Но если где-то перед тем в списке предметов есть 0xFF, то эта функция отключается, что позволяет мне получить вот такой инвентарь:

pokeball x1
pokeball x1
pokeball x1

Так что я вставляю в самое начало инвентаря 0xFF и больше об этом не беспокоюсь. 

Полезная нагрузка, которую я залил в Gameboy, — это тоже последовательность программ. Я создал упрощённый формат MIDI, имплементировал его в машинных кодах GameBoy, и перевёл в свой формат мелодию с http://www.everyponysings.com/. В полезной нагрузке последней программы ввода содержится как сам MIDI-файл, так и интерпретатор. Картинка устроена так же — я перевёл PNG-файл в Gameboy-совместимый формат и добавил код, который её показывает. И картинку, и мелодию загружает последняя программа ввода, так что исходники можно увидеть на экране эмулятора (или скачать с http://hg.bortreb.com/vba-clojure).