Первая часть Legend of Zelda — бессмертная классика. Обычному игроку требуется на её прохождение пара дней, а для самых опытных спидраннеров это вопрос получаса. Однако очень запутанный и сложный баг, открытый Sockfolder, позволяет пользователю исполнять произвольный код прямо из игры, чтобы пройти игру меньше чем за три минуты.

Вкратце это происходит так:

1. Вводим код на экране ввода имени.
2. Входим во второе подземелье, берём свисток.
3. Переходим на кладбище, вызываем десять призраков.
4. Дожидаемся нужных условий, ставим игру на паузу, когда создания находятся в определённых местах.
5. Снимаем паузу, нажимаем одновременно A и B, и всё!

Да, это потрясающе. Теперь давайте рассмотрим подробнее, что же происходит в игре, и как выполняется этот удивительный баг Legend of Zelda.

Как вызвать ошибку

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

• мы можем работать только с тремя файлами, то есть программа может содержать только 3 * 8 символов = 24 байта;
• нам нужно ввести в качестве первых пяти символов одного из файлов ZELDA, если мы хотим начать со второго квеста.

Нам нужно начать со второго квеста по причине, которую я объясню позже. Мы называем первый файл ZELDA, потому что такое название подходит лучше всего. Теперь давайте начнём игру. Прежде чем мы попадём на кладбище, наше поведение практически не отличается от обычной игры. Главное, что нам нужно сделать — постараться не умереть дважды. Под «умереть» понимается и сама смерть, и частый переход в меню. Вы поймёте, почему это так, из дальнейших объяснений.

После того, как мы добыли свисток, мы переходим на этот экран кладбища, чтобы выполнить баг. Ошибка срабатывает здесь, потому что при использовании свистка создаётся объект из надгробия, которое открывает скрытую лестницу. Это необходимо для возникновения бага. И всё это связано с ограничениями спрайтов. В Legend of Zelda на экране одновременно может быть не больше 11 спрайтов. Если вы попытаетесь создать 12-й спрайт, игра не позволит сделать это. Для воспроизведения ошибки мы нарушаем лимит переполнения и создаём 12-й спрайт.

Когда вы создаёте объект «свисток», игра «забывает» проверить, сколько спрайтов было на экране до этого. Поэтому когда мы создали максимальное количество спрайтов, спрайт создаётся за пределами таблицы спрайтов, память перезаписывается, и возникает непредвиденное состояние.

В памяти есть небольшой фрагмент, начинающийся со смещения 350, хранящий идентификаторы одиннадцати спрайтов. Спрайт создаётся при загрузке экрана, начиная с позиции с минимально возможным смещением спрайта. Это значит, что спрайты ищут позицию с минимальным смещением, начиная со смещения 350 и дальше. Когда спрайт должен быть создан, игра ищет пустое значение в таблице спрайтов, чтобы заменить его идентификатором спрайта, таким образом создавая его. В отличие от создания спрайтов при загрузке экрана, при попытке создания спрайта игра ищет позицию с максимальным смещением для спрайта. Это значит, что сначала она проверяет, можно ли создать спрайт в позиции 10 (0A). Если нет, то она проверяет позицию 9 (09), т.е. смещение 359, и так далее. Если все позиции спрайтов заняты, то игра «сдаётся» и не создаёт спрайт.

Однако разработчики забыли выполнять проверку границ, чтобы игра могла «сдаться» при попытке создания объекта «свисток», и игра продолжает искать байты со значением 00 в месте за пределами таблицы спрайтов, чтобы записать туда идентификатор объекта. Но где же она ищет это значение сначала? На самом деле эта таблица — часть массива большего размера, хранящего информацию о спрайтах. Когда свисток находит место для создания в начале таблицы, он начинает поиск позиций со значением 00 с конца массива.

На экране кладбища этот фрагмент массива содержит информацию о текущем состоянии действий призраков. Давайте теперь поговорим о состояниях действий призраков. Призраки, создаваемые на кладбище, двигаются хаотично. Это потому, что их действия контролируются поведением, определяемым их состоянием действия. Эти состояния действия могут иметь любые значения от 0 (00) до 5 (05), в зависимости от действий призрака. Они записываются в конце массива, содержащего информацию о спрайтах.

В целом, все эти состояния действия соответствуют позиции в таблице функций, определяющей действия призраков. Поскольку состояния могут иметь всего 6 значений, таблица имеет размер, необходимый для хранения всех шести действий. Здесь состояние действия 0 (00) соответствует ускорению призрака. Это важно, потому что когда свисток начинает искать место для создания своего спрайта, он заполнит первую найденную в памяти позицию со значением 00. Ускорение призрака соответствует действию 0, записываемому в коде значением 00, поэтому игра считает его пустой позицией, и записывает в неё идентификатор свистка 5E.

Затем игра пытается выполнить код в позиции 5E таблицы, но поскольку таблица содержит только значения до 05, игра выполняет в качестве кода «мусорные» данные далеко за пределами таблицы. Если вы сделаете всё правильно, то «мусорные» данные приведут нас к коду, который мы записали символами файлов, игра выполнит переход к Зельде, и мы пройдём игру.

Однако чтобы баг сработал, нам нужно повредить третье состояние действия в таблице. Значит третий созданный призрак должен ускоряться, а все последующие должны выполнять другие действия (код которых не равен 00). Это важная информация. Теперь давайте посмотрим, что происходит, когда мы выполняем баг.

Выполнение бага

Если мы сделали всё правильно, игра пытается выполнить данные в позиции 5E таблицы. Она начинает считывать как код данные, начинающиеся со смещения 602. В памяти со смещением 602 и 603 хранится информация, связанная с состоянием действия Линка, поэтому мы можем управлять ею. Когда Линк стоит, значения в смещениях 602 и 603 будут равны 00. Но когда мы нажимаем кнопку B, чтобы использовать свисток, значение в 602 будет равно 10, а когда мы нажимаем A для использования меча, значение в 603 будет равно 01.

Поэтому когда мы нажмём обе эти кнопки одновременно, то соседние данные будут равны 10 01. Эти данные игра интерпретирует как команду ветвления BPL для перехода на смещение 605 и исполнение данных в нём как кода. Значения в 605 и 606 будут равны 00, если у нас не слишком низкое здоровье, и равны 40, если здоровье низкое. Чтобы быстро пройти игру, эти значения должны быть равны 00, поэтому нужно постараться сохранить здоровье до момента выполнения бага. Значение 00 соответствует инструкции BRK (break, прервать). Так как она ничего не делает здесь, нам нужно, чтобы значения были равны 00 и игра продолжила выполнять код.

Поскольку мы использовали меч, игра продолжит исполнять инструкцию в следующем нечётном байте. Следующая инструкция, не являющаяся BRK, находится в смещении 08, но так как мы использовали меч, игра перепрыгивает через неё и исполняет код в 09 и 0A. Значение в байте 09 всегда равно 10, это означает, что мы опять имеем дело с инструкцией ветвления BPL. Байты в смещении 623 (62E) относятся к музыке. Она пытается увеличиться в процессе проигрывания музыки, но иногда перепрыгивает на меньшие значения.

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

Однако после этих хаотичных данных есть область безопасных данных. Поэтому мы попытаемся перескочить туда. Нам нужно, чтобы данные в 60A были побольше, чтобы точно пропустить небезопасную область и попасть к постоянным, безопасным, данным. Если мы перешли туда, то всё в порядке. Но в смещении 630 есть счётчик количества смертей Линка. Если Линк умер дважды, это значение будет равно 02, что образует инструкцию и останавливает игру. Вот поэтому важно, чтобы вы не умерли два раза. Итак, в результате мы перейдём к смещению 638, которое является началом таблицы, хранящей имена файлов. Если мы попадём сюда, игра выполнит код, который мы ввели на экране файлов. И здесь начинается…

Код

Имена файлов хранятся в памяти по порядку. Это значит, что первые байты, которые мы исполним, это файл с именем ZELDA. К счастью, исполняемый этими байтами код безопасен, так что мы можем перейти к остальной части. Поскольку имя ZELDA не важно, давайте рассмотрим, что же делает остальной код. Сначала мы выполняем три команды PLP (pull from stack, извлечь из стека). Когда мы вызываем функцию, она записывает два значения в стек. Эти значения соответствуют тому, где вы находились в коде, когда выполняли функцию. Так игра может узнать, куда ей возвращаться после выполнения функции.

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

Значения в смещении 10 памяти соответствуют номеру мира, в котором мы находимся. Если мы в надземном мире, значение равно 00. Для первого подземелья значение равно 01, для второго — 02, и так далее. Так как Зельда находится в девятом подземелье, нам нужно, чтобы это значение было равно 09. Однако мы выполняем баг в надземном мире и значение равно 00. Так что нам нужно найти способ приравнять его к 09. Значение в смещении 11 соответствует каким-то данным о состоянии игры. Когда игра загружается, значение равно 00, когда игра не загружается — 01. Нам нужно загрузить девятое подземелье, поэтому это значение должно быть равно 00.

Значение в смещении 12 соответствует какой-то части состояния. Когда экран загружается, значение обычно равно 02, когда не загружается — обычно 05. Так как мы хотим загрузить подземелье, это значение должно быть равно 02.

Последнее значение, которое мы хотим изменить, соответствует квесту, в котором мы находимся. Значение в смещении 62D соответствует первому или второму квесту, и имеет значение 00 или 01. Мы начали со второго квеста, но хотим закончить в первом квесте, потому что так мы запутаем игру. Поэтому нам нужно изменить это значение на 00. Это поместит нас в странный гибрид первого и второго квестов. Нам нужно это гибридное состояние для выполнения кода с определённой целью. Мы рассмотрим её, когда будем объяснять, что делает код.

Ну ладно, мы установили себе цели, давайте перейдём к коду. Сначала у нас идёт функция LSR (logical shift to the right, логическое смещение вправо) для смещения 11. Эта функция делит значение пополам и записывает остаток в перенос. 11 — это место в памяти, которое хранит значение, соответствующее состоянию игры, и до этой инструкции его значение равно 01. Когда мы делим на два, у нас получается 00 с остатком 01, так как деление целочисленное. В смещение 11 записано значение 00, а в перенос — 01.

Затем у нас идёт функция ROX для смещения 0D (rotate left, поворот влево) с индексом X. Так как мы перезаписали состояние действия третьего с конца созданного нами призрака, X равен трём. 0D + X равно 0D + 03, что равно шестнадцатеричному 10. Поэтому эта функция поворачивает влево в смещении 10. Эта функция умножает значение в смещении 10 на 2 и добавляет к переносу. Значение начинается с 0. Ноль, умноженный на 2 равно 0, а 0 + 1 равно 1, поэтому значение записывается в смещение 10.

Теперь снова повторяется операция ROX для смещения 0D с индексом X. Значение X не изменилось, оно всё ещё равно трём, поэтому это ещё один поворот влево в смещении 10. 1 * 2 = 2, и так как мы уже использовали перенос, его значение равно 0. 2 + 0 = 2, поэтому значение 2 записывается в смещение 2.

Дальше у нас идёт третья операция ROX для смещения 0D. 2 * 2 = 4, а 4 + 0 = 4, поэтому в смещение 10 записывается значение 4.

Следующая инструкция — LSR в смещении 12. Мы начинаем со значением 5, так что деление на два даёт нам остаток 1. 2 записывается в смещение 12, а 1 — в перенос.

Затем выполняется последний поворот ROX влево в смещении 10. 4 * 2 = 8. Значение переноса равно 1, мы прибавляем его к произведению, получая 9.

Последняя инструкция перед возвратом — логический сдвиг вправо в смещении 62D. Значение здесь равно 1, потому что мы во втором квесте. И так как мы поделили на 2, значение будет приравнено к 0. Так мы попали в режим гибридного квеста.

Теперь мы выполняем функцию возврата и игра обновляет значения своего состояния значениями, записанными в нашем коде. На этом баг завершён, и мы попадаем в комнату Зельды. Мы попадаем туда, потому что гибридный квест запутывает игру. Она не знает, куда точно поместить Линка. И так мы оказываемся в комнате Зельды, пройдя таким образом игру.

Надеюсь, это поможет вам понять, что происходит внутри игры Legend of Zelda при выполнении произвольного кода и выполнении бага быстрого прохождения игры.