decimal - para - hashtags

¿Deconstruyendo fallas Pokémon? (3)

(Me disculpo si este es el lugar equivocado para preguntar esto. Creo que definitivamente está relacionado con la programación, aunque si esto pertenece a algún otro sitio, por favor avíseme)

Crecí jugando Pokémon Rojo y Azul, juegos que fueron muy divertidos pero que son algo notorios por tener numerosos fallos explotables (por ejemplo, vea esta ridícula carrera del juego que usa la corrupción de memoria para convertir la pantalla de elementos en un editor hexadecimal).

Recientemente, encontré un speedrun interesante del juego que usa una falla llamada "Zzzzz glitch" para corromper ubicaciones de memoria importantes y permitir que el jugador gane casi inmediatamente el juego. De acuerdo con la descripción del autor del speedrun , la falla de ZZAZZ funciona de la siguiente manera:

Para iniciar una batalla de Entrenador, el juego necesita cargar una gran cantidad de datos, como el dinero que [...] concederá si es derrotado. Cuando se carga el dinero es donde las cosas pueden ponerse realmente feas. Por razones que están más allá de mí, el dinero se almacena de una manera completamente diferente, el juego usa una estructura de datos de tres bytes y en lugar de convertir el valor en binario, lo almacena en representación "humana". Por ejemplo, $ 123456 se almacenaría como 0x123456 en lugar de 0x01E240, la conversión correcta.
[Algunas entradas no válidas en la tabla de Entrenador] apuntan a la ubicación con datos monetarios no válidos. Cuando el juego intenta realizar aritmética con estos datos en dicha estructura, se vuelve loco y comienza a sobrescribir grandes porciones de RAM. Más específicamente, por cada bloque de tres bytes, dos de ellos contendrán 0x9999 (la cantidad máxima de dinero que un capacitador podría proporcionar). Este patrón se repite muchas veces a través de la memoria RAM. Para ver esto mejor, recomiendo pausar el video en el emulador después de que el entrenador ZZAZZ se enfrente y establecer el visor de memoria de VBA a 0xD070.

Este análisis tiene sentido, pero como programador no puedo dejar de preguntarme cómo los programadores escribieron el código que haría esto posible. Ningún enfoque que se me ocurra para escribir una función que convierta un número decimal codificado en hexadecimal a decimal alguna vez comenzaría a llenar bloques aleatorios de memoria con 0x9999 si la entrada no fuera un número decimal codificado hexadecimal válido.

Mi pregunta es: sin diseñar específicamente el algoritmo para que falle de esta manera, ¿hay una implementación directa de una conversión de decimal codificado hexadecimal a decimal que podría dar como resultado este tipo de corrupción de memoria cuando se alimenta con un valor no válido?

De nuevo, si esto no es tema, mis disculpas. Mi opinión es que otros programadores en este sitio también pueden haber crecido jugando a este juego, y parece un ejercicio interesante de ingeniería inversa para tratar de descubrir cómo un problema como este podría ser posible.

¡Misterio resuelto! Parece que el usuario TheZZAZZGlitch descubrió qué causa esto .

El error se activa cuando el juego intenta calcular un número entero extremadamente grande. Internamente, el juego tiene una rutina que agrega valores repetidamente para simular una multiplicación. Parece escribir bytes a medida que avanza, desplazándose sobre una posición de escritura de salida. El código está diseñado para cortar cualquier valor que exceda 0x009999 para que el jugador no gane más de $ 9999 de una batalla de entrenador (los valores se almacenan en decimales codificados hexadecimales). Sin embargo, el juego olvida restablecer el puntero de salida cuando esto ocurre, por lo que si se genera un número extremadamente grande, el juego repetidamente escribirá el patrón 0x009999 en la RAM desplazando el puntero de escritura y escribiendo 0x99 en dos de cada tres bytes.

¡Espero que esto ayude!

Honestamente, supongo que esto es solo una falla estúpida y desagradable por parte de alguien que escribe uno de sus primeros juegos en blanco. Pokemon Red / Blue fue la primera de la serie y tenía tantas otras fallas técnicas que normalmente Nintendo patearía de las pruebas de lotes, que me pregunto cómo se hizo. El problema de desplazamiento de pantalla de desplazamiento es el que me atrapa. De todos modos, quién sabe en qué estaban pensando. Quizás esta área fue escrita a través de un script y por lo tanto almacenó las cosas de manera diferente. Tal vez el patrón de bits 0x0101 se usó para mostrar que la memoria se liberó y ese código accidentalmente se vuelve loco en lugares extraños. Podría verter el código Z80 y revivir mi propio tiempo de desarrollo de juegos en esa plataforma, pero meh. Demasiado trabajo para tratar de descifrar qué estaban quemando.

Sin duda, ganó un montón de dinero ...

Editar 1:

Ok, lo estimuló. Pasé un poco más de tiempo revisando mi memoria y encontré un bocado para ti. El GBC / DMG tiene un código de operación llamado DAA. Ajuste decimal del acumulador (A). Lo que esto hace es convertir un valor en el acumulador al formato BCD. Las áreas en la memoria que está viendo ya están en formato BCD: http://en.wikipedia.org/wiki/Binary-coded_decimal

Ahora puedo decirles que, en los 4 años aproximadamente, cuando programé manualmente el ensamblador Z80 para juegos, nunca tuve la necesidad de este código de operación, y solo lo vi una vez en un juego de béisbol que hicimos para mostrar algunas puntuaciones. Si bien es una instrucción aritmética de 1 ciclo, nunca podría encontrar un buen uso en la codificación normal. Hmm. En realidad todavía tengo los documentos técnicos de DMG de Nintendo. Ve figura;) De todos modos, no hay nada emocionante allí, excepto que se mezcla con una serie de banderas de manera funky.

Supongo que se supone que la tabla está en formato BCD. Cambiarlo a algo fuera de ese formato hace que las matemáticas interal se vuelvan extremadamente locas: las banderas Carry y Zero se establecen cuando no deberían estar. Esto causa el desbordamiento de una columna a la siguiente, lo que hace que se calculen números muy grandes. Sin mirar directamente los códigos de operación en cuestión que leen esta área, no puedo decir con certeza, pero mi opinión es que aquí hay un control de atrapar que dice que si el acarreo todavía está establecido al completar las matemáticas BCD, establezca un valor máximo En lugar de almacenar un valor negativo o fuera de límites. Eso o la instrucción DAA, cuando la recepción de datos de basura está devolviendo 0x99 por su valor de retorno, aunque estoy menos seguro de eso.

Espero que esto ayude...

Puedo pensar en un algoritmo (aunque siento pena por quienquiera que lo haya escrito):

Supongamos que la entrada es un dígito decimal de 32 bits en notación hexadecimal, little endian (por ejemplo, 0x56 0x34 0x12 0x00).
Ahora recorra cada byte, mientras que no ha alcanzado un byte cero . (Esto nunca debería suceder, si se garantiza que 0x999999 sea el máximo ... pero, por desgracia, no lo es).
En cada bucle, calcule el valor real y vuelva a escribir los datos en el entero (o en otro búfer, donde haga un "bucle mientras" en lugar de algo como "para i = 0 a 4").

Puede ver cómo puede obtener una falla, si su valor no tiene 0x00 al final (es decir, el entero "decimal" de 32 bits es mayor que 0x999999).

Por supuesto, esta es una forma bastante oscura de calcular el valor, pero creo que es bastante posible que alguien haya hecho un ciclo while / do-while en lugar de un loop for bound para esto.

Editar 1:

Al principio pensé que esto tendría la "ventaja" de permitir que la cadena se mostrara directamente al usuario (ya que terminaría en nulo), pero por supuesto eso no funciona con little endian. Podrían haber hecho algo similar con Big Endian, pero eso requeriría que un ciclo hacia atrás se desborde, lo que me parece un error menos probable para alguien.

Editar 2:

Quizás fue una optimización del compilador debido a un comportamiento indefinido (que el programador desconocía, como un molde de puntero no válido o un problema de alias).