Разбираем глюки покемонов?

Question

(я прошу прощения, если это неправильное место, чтобы спросить это. Я думаю, что это определенно связано с программированием, хотя, если это относится к другому сайту, пожалуйста, дайте мне знать)

Я вырос, играя в Pokémon Red and Blueигры, которые были очень увлекательными, но несколько печально известными наличием множества эксплуатируемых глюков (например, см. этот нелепый скоростной запуск игры , использующий повреждение памяти, чтобы превратить экран элемента в редактор шестнадцатеричных кодов).

Недавно я обнаружил интересный спидран игры, в котором используется сбой, называемый «сбой ZZAZZ», чтобы испортить важные области памяти и позволить игроку почти сразу же выиграть игру.Согласно авторскому описанию speedrun , глюк ZZAZZ работает следующим образом:

Чтобы начать битву с трейнером, игре необходимо загрузить много данных, таких как [...] деньги, которые он уступит, если победит.Когда он загружает деньги, все может стать действительно безобразным.По независящим от меня причинам деньги хранятся совершенно по-другому, в игре используется структура данных из трех байтов, и вместо преобразования значения в двоичное, она хранится в «человеческом» представлении.Например, $ 123456 будет храниться как 0x123456 вместо 0x01E240, правильная конверсия.

[Некоторые недопустимые записи в таблице тренеров] указывают на местоположение с недопустимыми денежными данными.Когда игра пытается выполнить арифметику с этими данными в указанной структуре, она сходит с ума и начинает перезаписывать огромные порции оперативной памяти.Более конкретно, для каждого блока из трех байтов два из них будут содержать 0x9999 (максимальная сумма денег, которую может дать тренер).Этот шаблон повторяется много раз через RAM.Чтобы увидеть это лучше, я рекомендую приостановить воспроизведение видео на эмуляторе после того, как наложен указатель ZZAZZ, и установить для просмотра памяти VBA значение 0xD070.

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

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

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

Answer 1

Честно говоря, я предполагаю, что это просто глупый, неприятный сбой, когда кто-то пишет одну из своих первых игр в цель. Pokemon Red / Blue были первыми в серии и имели так много других глюков, что Nintendo обычно выходила из лотового тестирования, и я удивляюсь, как все прошло. Вопрос смещения экрана прокрутки - тот, который получает меня. В любом случае, кто знает, о чем они думают. Возможно, эта область была записана с помощью скрипта и поэтому хранила вещи по-другому. Возможно, битовый шаблон 0x0101 использовался, чтобы показать, что память была освобождена, и этот код случайно приводит в замешательство странные места. Я мог бы залить код Z80 и заново пережить время разработки собственных игр на этой платформе, но не лучше. Слишком много работы, чтобы попытаться расшифровать то, о чем они думали.

Это, конечно, принесло кучу денег ...

Редактировать 1:

Ладно, ты выловил это. Я потратил немного больше времени на то, чтобы забыть о своей памяти, и нашел для тебя лакомый кусочек. GBC / DMG имеет код операции под названием DAA. Десятичная регулировка аккумулятора (A). Это конвертирует значение в аккумуляторе в формат BCD. Вы видите области памяти в формате BCD: http://en.wikipedia.org/wiki/Binary-coded_decimal

Теперь я могу вам сказать, что примерно через 4 года, когда я вручную программировал ассемблер Z80 для игр, у меня никогда не было необходимости в этом коде операции, и я видел его только один раз в бейсбольной игре, которую мы сделали для отображения некоторых. баллы. Несмотря на то, что это арифметическая инструкция с 1 циклом, я никогда не смог бы найти для нее хорошего применения в обычном кодировании. Хм. На самом деле у меня до сих пор есть документы по технологиям DMG от Nintendo. Пойди разберись;) В любом случае, в этом нет ничего захватывающего, кроме того, что он смешным образом смешивается с несколькими флагами.

Я предполагаю, что таблица должна быть в формате BCD. Изменение его на что-то за пределами этого формата приводит к тому, что внутренняя математика становится крайне бесполезной - флаги Carry и Zero устанавливаются, когда их не должно быть. Это вызывает переполнение от одного столбца к следующему, что приводит к вычислению очень больших чисел. Не смотря прямо на рассматриваемые коды операций, которые читают эту область, я не могу сказать наверняка, но я предполагаю, что здесь есть проверка на все, что говорит, если перенос по-прежнему установлен после завершения математики BCD, установите максимальное значение вместо хранения отрицательного значения или значения за пределами. Эта или инструкция DAA при получении данных об мусоре возвращает 0x99 для возвращаемого значения, хотя я менее уверен в этом.

Надеюсь, это поможет ...

Answer 2

Я могу придумать алгоритм (хотя мне жаль того, кто мог его написать):

• Предположим, что ввод представляет собой 32-разрядную десятичную цифру в шестнадцатеричной записи с прямым порядком байтов (например, 0x56 0x34 0x12 0x00).

• Теперь переберите каждый байт, , пока вы не достигли нулевого байта . (Этого никогда не должно случиться, если 0x999999 действительно гарантированно будет максимальным ... но, увы, это не так.)

• В каждом цикле вычисляют фактическое значение и записывают данные обратно в целое число (или в какой-то другой буфер, где вы выполняете "loop-while" а не что-то вроде «для я = 0 до 4»).

Вы можете увидеть, как можно получить сбой, если ваше значение не имеет 0x00 в конце (т. Е. 32-разрядное "десятичное" целое число больше 0x999999).

Конечно, это довольно неясный способ вычисления значения, но я думаю, что вполне возможно, что кто-то сделал цикл while / do-while, а не ограниченный цикл for для этого.

Редактировать 1:

Сначала я подумал, что это будет иметь "преимущество", позволяя пользователю отображать строку непосредственно (поскольку она будет заканчиваться нулем), но, конечно, это не работает с немного порядковый Они могли бы сделать что-то похожее с большим порядком байтов, но для этого потребовалось бы переполнение цикла в обратном направлении , что, на мой взгляд, является менее вероятной ошибкой для кого-то, кто совершит ошибку.

Редактировать 2:

Возможно, это была оптимизация компилятора из-за неопределенного поведения (о котором не знал программист, например, неверное приведение указателя или проблема с алиасами)?

Answer 3

Тайна раскрыта!Похоже, пользователь TheZZAZZGlitch выяснил, что вызывает это .

Сбой возникает, когда игра пытается вычислить чрезвычайно большое целое число.Внутри игры есть подпрограмма, которая многократно добавляет значения для имитации умножения.Кажется, что байты записываются по ходу дела, смещаясь по выходной позиции записи.Код разработан, чтобы обрезать любое значение, которое превышает 0x009999, чтобы игрок не заработал более $ 9999 от битвы тренеров (значения хранятся в шестнадцатеричном коде в десятичной форме).Однако игра забывает сбросить указатель вывода, когда это происходит, поэтому, если генерируется чрезвычайно большое число, игра будет многократно записывать шаблон 0x009999 в ОЗУ, сдвигая указатель записи и записывая 0x99 в два из каждых трех байтов.

Надеюсь, это поможет!