Como habeis visto, las invitaciones de boda que os hemos entregado están inspiradas en "Alicia en el País de las Maravillas", el libro favorito de Patricia, del cual tiene una colección de tropecientas ediciones. Ella las diseñó a su gusto, y por ello yo diseñé esta web al mío: maquinitas antiguas, ingeniería inversa y cosas frikis en general (aunque ella tampoco se queda corta en ese aspecto).

Un poco de historia

Comparado con lo que tenemos hoy en día, las consolas de aquella época eran muy "simples": No eran más que un procesador conectado a una serie de periféricos (los botones de los mandos, chips de sonido, controlador de video, a veces una minúscula memoria RAM, etc).

El procesador de la Game Boy, desarrollado a medida para Nintendo, es el Sharp LR35902, una versión modificada del Intel 8080 con algunas carácterísticas propias, y otras del Zilog Z80 (una CPU a la que tengo un especial cariño, al ser la que tambien utilizaban los Amstrad CPC o los ZX Spectrum, y para la cual escribí un emulador hace unos años).

Al contrario que las consolas de hoy en día que tienen su propio sistema operativo, y en las cuales instalamos los juegos desde un CD o desde internet, estas consolas no tenían nada de eso. Los cartuchos que insertábamos en sus ranuras son chips de memoria (ROMs), a veces incluso con hardware extra del que no disponía la consola (como procesadores digitales de señal, ¡o incluso CPUs suplementarias para disponer de más potencia!, como es el caso del chip Super FX que tenían algunos juegos concretos de Super Nintendo).

Efectivamente, el contenido de esas memorias es lo que hoy conocemos como "firmware" en los dispositivos electrónicos: un bloque de ceros y unos grabados en un chip que representan las instrucciones que se van a ejecutar en el hardware.

El volcado

Podeis imaginaros la ROM como una columna de bytes, cada uno con su propia dirección (el de arriba de todo empezando en el 0, luego el 1, luego el 2, etc). Cuando queremos leer uno de esos bytes, tenemos que indicarle al procesador que en dirección queremos mirar.

El procesador de Game Boy es de 8 bits (trabaja con un solo byte de cada vez), y tiene un bus de direcciones de 16 bits. Esto significa que solo tiene direcciones desde 00 00 hasta FF FF (0 a 65535 en decimal). Básicamente, que el tamaño máximo que podría tener un juego son 64 kb (menos, ya que las direcciones tambien deben repartirse para la RAM, la memoria de video, etc).

Muchos de los primeros juegos no superaban ese tamaño (muchos ni siquiera superan los 32 kb).

Otros juegos, como el Donkey Kong tienen código más complejo, o más gráficos (este incluye soporte para Super Game Boy, un periférico para Super Nintendo que permitía jugar con juegos de Game Boy con gráficos en color), por lo que el tamaño del juego es mayor (en este caso son 512 kb).

Entonces, ¿cómo consigue la Game Boy leer más allá de esos 32 kb? Mediante el controlador MBC, que se encarga de hacer bank switching.

Bank switching ("cambio de bancos") es una técnica que consiste en dividir la memoria en una serie de bloques (por ejemplo, de 32 kb), e ir asignando las líneas de direcciones a un bloque u otro en función del que se quiere leer.

Así, por ejemplo, la dirección 0x5523 puede en un momento dado estar apuntando al banco 1 de memoria, y en otro momento estar apuntando al bloque 3. Todo ello se controla desde el código, dando instrucciones al controlador MBC para realizar dicho remapeo.

Pero basta de explicaciones técnicas, que os aburro.

Imágenes en Game Boy

Ahora que ya tenemos un volcado de la rom del juego en un archivo de nuestro ordenador, lo siguiente es investigar cómo podemos cambiarle los gráficos.

Podría parecer que es tan sencillo como buscar de alguna manera imágenes en formato JPEG o BMP dentro de la memoria del juego y cambiarlas por otras (como se haría con los juegos modernos), pero esto no es así.

Hoy en día tenemos ordenadores potentes, lo que ha derivado en que, en general, se malgasten de una manera abrumadora los recursos del sistema, y que el software que se desarrolla hoy es "basura" (como sobran recursos, no se molestan en hacer las cosas bien, aunque gasten 30 veces más memoria o procesador del necesario para un programa). Pero esta discusión creo que no es objeto en este articulo.

Lo cierto es que antaño era lo contrario, había que aprovechar al máximo los recursos de los que se disponía, y se hacían verdaderas maravillas y optimizaciones, y los programadores eran Programadores con mayúsculas.

La pantalla de Game Boy es capaz de mostrar 4 colores; el formato que se utiliza para representar imágenes en esta consola es bien conocido, y se denomina 2BPP (2 bits per pixel).

Es decir, con solo 2 bits se puede representar un pixel, que puede variar entre 4 colores. Cómo os podeis imaginar, una imagen de este tipo ocupa muy poco y no necesita una descompresión previa (gastar procesador) antes de mostrarse en pantalla (como si ocurre, por ejemplo, en JPEG).

Además de esto, la forma de representar en memoria estas imágenes en Game Boy, es en baldositas de 8x8 pixeles, que pueden combinarse entre ellas. De esta forma, si en una imagen grande coinciden algunas de estas baldosas, solo hay que almacenar una y reutilizarla, y no todas.

Sabiendo que con 2 bits podemos representar un pixel, podemos decir que con 2 bytes podemos representar 8 pixeles, y a su vez, con 8 pixeles podemos representar una línea de un tile (baldosa). En resumen, con 16 bytes, podemos representar una baldosa completa.

Hay que tener en cuenta que esos 4 colores no son ningún color en concreto, si no una paleta de 4 colores cualquiera.

La pantalla monocroma de la Game Boy original solo puede representar 4 grises (con el tono verdoso o amarillento que les confiere el polarizador de la pantalla en si), sin embargo más tarde en la Game Boy Color y su nueva pantalla TFT en color podían representarse 4 colores cualquiera definidos por el juego, y en ocasiones incluso permitiendo al jugador escogerlos.

Cabe destacar tambien que en esta última no necesariamente se mostraban solo 4 colores en pantalla, ya que podían dibujarse varias capas de tiles, cada una de ellas con su propia paleta de 4 colores, pudiendo llegar hasta 56 colores en pantalla simultáneamente.

Volviendo al lío, y con toda esta información, abrimos rápidamente nuestro archivo en un visualizador de imágenes 2BPP para ver si podemos encontrar algo útil.

Como estamos visualizando el volcado completo del juego, podemos encontrar mucha "maraña" según vamos bajando (ya que el código del juego no representa ninguna imágen), pero si seguimos bajando, encontramos un trocito de memoria donde si se muestra algo.

¡Bingo! Hemos encontrado lo que parece ser la cara de Mario en el juego. Como se puede apreciar, está repetida muchas veces, ya que cada fotograma de sus animaciones (saltos, correr, etc) utiliza sus propios sprite (que es como se conoce a los gráficos que representan objetos móviles/interactuables en un juego).

Esto va a ser pan comido. Nos limitamos a buscar ese trozo de memoria en un editor hexadecimal, y vamos a reemplazar sus valores para convertir la cara de Mario en "mi cara".

Hasta aquí perfecto, ya tenemos al personaje cambiado. Pero ahora además vamos a cambiar la pantalla de introducción del juego, para ponerle otro título ("Patri y Anto: La Pedida") y ponernos a mi y a Patricia como protagonistas.

Seguimos buscando donde están las imágenes que componen esa pantalla, pero ¡no hay nada!. Las únicas imágenes que hemos encontrado son esos sprites de Mario y algún otro personaje, pero ni rastro de cualquier otro gráfico.

¿Qué es lo que ocurre? ¿Dónde están estos gráficos?

Ingeniería inversa del algoritmo de compresión

Como habíamos mencionado anteriormente, los recursos en aquella época eran muy limitados, por lo que había que optimizar todo al máximo. Tenemos muy poca memoria ROM donde almacenar cosas, y las imágenes es una de las cosas que más espacio ocupan, por lo que es necesario comprimirlas para que ocupen menos. Y, siendo más precisos, no solo se comprimen imágenes, sino la composición de los niveles del juego, etc

¿Por qué los sprites de Mario no estaban comprimidos?

Al ser unos sprites que se utilizan mucho durante todo el juego, ya que es el personaje que manejamos, tener que descomprimirlo cada vez que se cambia de pantalla o de nivel supone utilizar recursos de procesador que ralentizarían el juego. En este tipo de procesadores tan "lentos" cada ciclo de reloj cuenta, es por eso que ese tipo de sprites no solían comprimirse.

Sin embargo, el resto de imágenes, como los fondos o decoraciones, al estar muy ligadas a pantallas concretas, solo se descomprimen y utilizan cuando se llega a dichas pantallas.

Esto además es importante, porque si recordais lo que hablabamos del bank switching, muchas imágenes estarían repartidas por distintos bancos de memoria; si tuviesemos que cambiar al banco del personaje Mario cada vez que queremos cargarlo, en cada pantalla, se complicaría todavía más el código.

Vale, vale, me dejo de rollos. Entonces, ¿qué es lo que tengo que hacer para encontrar las imágenes que busco?. Pues no me queda más remedio que hacer ingeniería inversa del código del juego para buscar la rutina que se encarga de descomprimir los datos, y por supuesto, la dirección de memoria donde están los datos que quiero descomprimir.

Para ello me valgo de un emulador de Game Boy con depurador incorporado, que me permitirá ver la ejecución del juego instrucción a instrucción.

El primer paso es el más sencillo: buscaré el punto donde la memoria de video (VRAM) empiece a llenarse con las imagenes descomprimidas que busco, y así podré identificar cual es la rutina que lo está haciendo. Una vez identificado dicho punto, puedo colocar un breakpoint en esa instrucción, y la ejecución del programa se parará ahí.

¡Chupado!. Ya lo tengo todo: la dirección donde empieza la rutina de descompresión (257F), y la dirección donde la rutina empieza a leer los datos que va a descomprimir (5A56). ¡Incluso la dirección de VRAM donde están los datos ya descomprimidos cuando termina la rutina (que en Game Boy siempre es desde 8000).

A partir de aquí sería tan fácil como volcar los datos de la VRAM directamente a un archivo, o utilizar mi emulador de Z80 para ejecutar de forma aislada la rutina de descompresión contra cualquier bloque de datos comprimidos, y ya tendría las imágenes que busco listas para ser modificadas (o casi listas, ya que tengo que convertirlas de 2BPP a un formato que pueda modificar cómodamente con un editor de imágenes, como por ejemplo BMP.

Pero, en lugar de eso, vamos a mirar más a fondo la rutina de descompresión y a tratar de replicar su algoritmo, y más adelante veremos por qué.

Aquí empieza lo complicado. Tendremos que ir viendo, instrucción a instrucción, que transformaciones y movimientos hace el código sobre los bytes que va leyendo. En un lenguaje de programación de hoy en día, esto sería relativamente sencillo, ya que es muy fácil de entender (hay funciones como "descomprimir()", o "suma estos dos cadenas de texto y colocalas en esta variable").

Pero el código en ensamblador representa las operaciones que hace el procesador, que son muy atómicas ("suma este byte con este otro", "mueve este byte desde esta dirección a esta otra"), y además cuenta con un limitado número de registros donde almacenar bytes para trabajar con ellos (en la imagen anterior, podeis verlos en la esquina superior derecha). Concretamente, cuenta con los registros A, B, C, D, E, H y L: 7 espacios donde almacenar bytes como "mesa de trabajo" (F es un registro especial donde se almacenan las flags, así que no contamos con él).

Esto significa que tiene que trasegar constantemente datos de un sitio a otro para realizar las operaciones. Especialmente en arquitecturas como esta, de 8 bits.

Vamos, que hay que echar un buen rato leyendo la rutina o incluso ejecutarla instrucción a instrucción para averiguar que hace exactamente.

Abajo podemos ver el grafo de ejecución de la rutina de descompresión, que nos ayudará a desgranar el algoritmo.

No vamos a entrar en detalle, pero en este código se puede reconocer un algoritmo con un esquema RLE (Run-length encoding), muy común en diversos algoritmos de compresión sin pérdida. Básicamente este esquema propone contar repeticiones de un byte o una serie de bytes o caracteres, y por así decirlo, solo almacenar "X veces este byte" en lugar de "este byte este byte este byte este byte". Es decir, en lugar de guardar "AAAAA", guardaría "5A".

Más concretamente, el algoritmo que usa el juego parece ser una variación del algoritmo LZSS (Lempel-Ziv-Storer-Szymanski), que si tiramos de historia, es bien sabido que Nintendo utilizaba ciertas variaciones de dicho algoritmo en sus juegos.

Sin embargo no parece ser ninguna de las implementaciones más conocidas que usan sus otros juegos, pero con un poquito de esfuerzo, pude implementar la solución en un pequeño script en Python. ¡Ya puedo descomprimir mis imagenes!

Os preguntareis por que tanto esfuerzo para recomponer el algoritmo de descompresión, cuando ya había comentado que podía descomprimir utilizando el código del propio juego sin tener que entenderlo. Y la respuesta es bien sencilla ¿se os ocurre por qué?

Porque cuando modifique las imágenes, tengo que volver a comprimirlas antes de insertarlas de nuevo en el juego.

El juego no cuenta con una rutina de compresión, porque no la necesita. Las imágenes ya están comprimidas cuando el desarrollador las introduce en el juego.

Así que si quiero volver a comprimir, tengo que darle la vuelta al algoritmo de descompresión para implementar el de compresión (¿entendeis ahora porque se le llama ingeniería "inversa" o retroingeniería a esta metodología?).

Esto puede sonar fácil al contar con el código de descompresión que he programado, pero no lo es en absoluto. Incluso para algunos algoritmos, especialmentelos los criptográficos, sería imposible obtener el algoritmo "contrario".

Afortunadamente, los algoritmos RLE como este no son tan complejos, y con un poco de observación y otro poco de ensayo y error, es posible obtener el de compresión, como podeis ver en el script de abajo. Aun así, esta es la parte que más tiempo me ha costado de todo el proceso, con diferencia.

Con esto, ya puedo volver a comprimir imagenes que el juego sea capaz de descomprimir.

Como curiosidad, si descomprimo una de las imágenes del juego, y la vuelvo a comprimir sin modificar, no obtengo el mismo resultado que antes de ser descomprimida, aunque sigue siendo válida para el juego. ¿Por qué?

Porque el algoritmo de compresión que he desarrollado no es exactamente el mismo que el que utilizó el autor del juego, pero debido a las caracteristicas de los RLE, mi algoritmo tambien es válido para su descompresión. Y de hecho, comprime más que el original, lo cual es una ventaja, porque al ser más corto, cuando vuelva a insertarlo no sobreescribiré datos que no pertenecen a la compresión ni modificaré el tamaño de la ROM, lo que me obligaría a tener que modificar bastantes partes del código para volver a alinear las instrucciones.

Ahora que tenemos todas las piezas, solo tengo que:

1. Copiar el bloque de datos (recordemos que había obtenido su dirección de memoria).
2. Descomprimirlo con mi algoritmo.
3. Convertirlo de 2BPP a BMP.
4. Abrirlo en un editor de imágenes y modificarlo a mi antojo.
5. Convertirlo de BMP a 2BPP
6. Volver a comprimirlo con mi otro algoritmo.
7. Volver a colocarlo en la dirección de memoria donde estaba.

Y, con ánimo de dejar el artículo completo, este es el script para convertir un BMP (indexado a 4 colores) en 2BPP.

¡Ya está! ¡Juego hackeado!

¿Y sabeis lo más guay? Que no solo puede jugarse con el emulador, sino tambien en una Game Boy real.

¡Ups! ¿Que ocurre ahora?

Nada que no podamos arreglar rápidamente. Nos queda modificar otra parte del código del juego, que se encarga de enumerar que baldosa tiene que ir en cada lugar de la pantalla.

Al haber modificado los tiles originales con unos nuevos, no todos están en el mismo lugar que estaban antes (si comparamos las imágenes de antes, podemos ver que las del título si coinciden en el mismo sitio, pero las caras no, ya que la imágen de Donkey Kong reutilizaba mucho una baldosa negra, mientras que nuestras caras casi no reutilizan ninguna (únicamente algunas de "mi pelo").

Afortunadamente el arreglo es simple, y se trata de cambiar unos bytes en un lugar concreto de la rom donde le decimos "aquí va la baldosa 7", aquí va la baldosa 12", etc.

Y aquí acaba esta aventura. Espero que os haya resultado entretenido, o al menos no demasiado pesado.

¡Que no se diga que en la web de mi boda no se aprende!