Деконструкция сбоев Pokémon?

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

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

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

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

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

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

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

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

Ответ 1

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

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

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

Ответ 2

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

Он наверняка сделал тонну денег, хотя...

Изменить 1:

Хорошо, ты наделал это. Я потратил немного времени на мою память и нашел для вас лакомый кусочек. GBC/DMG имеет код операции DAA. Decimal Adjust Accumulator (A). То, что это делает, преобразует значение в накопитель в формат BCD. Области в памяти, которые вы видите, уже находятся в формате BCD: http://en.wikipedia.org/wiki/Binary-coded_decimal

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

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

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

Ответ 3

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

Предположим, что вход представляет собой 32-разрядную десятичную цифру в шестнадцатеричной нотации, малое число (например, 0x56 0x34 0x12 0x00).
Теперь пропустите каждый байт, , пока вы не достигли нулевого байта. (Этого никогда не должно быть, если 0x999999 действительно гарантированно является максимальным... но, увы, это не так.)
В каждом цикле вычислить фактическое значение и записать данные обратно в целое число (или в некоторый другой буфер, где вы выполняете "loop-while", а не что-то вроде "для я = от 0 до 4",).

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

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

Изменить 1:

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

Изменить 2:

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