CHIP-8 se refiere a varias cosas. Formalmente es un lenguaje de programación interpretado, pero también se refiere a la máquina virtual diseñada para ejecutar programas CHIP-8. Informalmente CHIP-8 es el Hola Mundo de la emulación. Un rito por el cual pasa(mos) programadores interesados en crear emuladorores y simuladores.

La intención original del diseño de CHIP-8 era para hacer la creación de videojuegos más fácil, y por lo mismo hay una multitud de videojuegos "clásicos" (pong, tetris, space invaders, etc) implementados para la máquina virtual CHIP-8. Me recuerda a la máquina virtual implementada para el juego Another World (Out Of This World en Norteamérica). Les recomiendo ampliamente que lean el estudio del código fuente por Fabien Sanglard.

Crear un intérprete de CHIP-8 es un buen ejercicio para asegurarnos de entender en general la arquitectura de una computadora simple (tiene solamente 35 operaciones u opcodes), así como también el lenguaje de programación que estamos utilizando (apuntadores, operaciones binarias, gráficos, etc).

En lo personal, CHIP-8 no fue mi primer proyecto de emulación. Ese honor se lo lleva un simulador para el microcontrolador 68HC11 de Motorola (ahora Freescale). Un descendiente directo del 6800, famoso por ser el microprocesador de la Altair 680 y, tal vez aún más famoso el hecho de que el equipo que diseñó el 6800 fueron contratados por MOS Technology para diseñar lo que sería el 6502, microprocesador utilizado en la Apple II, Atari 2600, Commodore C64 y Nintendo Entertainment System (aunque es una versión modificada)

Además, CHIP-8 fue diseñado por el legendario Joseph Weisbecker.

Arquitectura de la máquina virtual CHIP-8

Como su nombre lo indica, CHIP-8 es una arquitectura de 8 bits:

;; Memory Map:
;; +---------------+= 0xFFF (4095) End of Chip-8 RAM
;; |               |
;; |               |
;; |               |
;; |               |
;; |               |
;; | 0x200 to 0xFFF|
;; |     Chip-8    |
;; | Program / Data|
;; |     Space     |
;; |               |
;; |               |
;; |               |
;; |               |
;; |               |
;; |               |
;; +---------------+= 0x200 (512) Start of most Chip-8 programs
;; | 0x000 to 0x1FF|
;; | Reserved for  |
;; |  interpreter  |
;; +---------------+= 0x000 (0) Start of Chip-8 RAM

En las computadoras originales donde se implementaba el intérprete CHIP-8, el código del intérprete mismo ocupaba los primeros 512 bytes, y los segmentos al final del mapa de memoria se utilizaban para el stack, y para el framebuffer, dejando menos espacio para el programa y los datos.

En implementaciones modernas esto no es necesario, sin embargo el segmento de 0x000 a 0x1FF se utiliza para guardar una serie de sprites que representan los caracteres hexadecimales 0 1 2 3 4 5 6 7 8 9 A B C D E F.

Cada operación es representada por dos bytes, por lo que el apuntador de programa (PC) avanza dos bytes por cada operación ejecutada.

Y ya que estamos hablando de registros...

Registros

El intérprete define 16 registros de 8 bits cada uno. A estos registros se les conoce como Vx, es decir V0, V1, V2... VF.

El registro VF es "especial" en el sentido que algunos opcodes lo usan como bandera de acarreo (carry flag) o para detectar colisiones cuando se despliegan gráficos (recordemos que el propósito principal de CHIP-8 es para desarrollar videojuegos).

También está el registro I o registro de dirección. Este registro es de 16 bits, necesario para direccionar toda la memoria.

Finalmente esta el contador de programa PC, de 16 bits para contener la dirección que contiene el opcode a ejecutar.

Pila (Stack)

La pila funciona como cualquier pila FIFO. Es de 16 niveles, por lo que se usan 32 bytes (2 bytes por nivel) para guardar direcciones. Esta por supuesto el registro SP que apunta a la posición actual en la pila.

Contadores (Timers)

CHIP-8 define dos contadores: delay y sound. El primero es para medir el tiempo que transcurre entre eventos del juego (programa), y el segundo emite un sonido cuando su valor es distinto de 0.

Gráficos

CHIP-8 es capaz de desplegar gráficos simples en dos tonos (típicamente gris y negro). Su resolución es una cuadrícula de 64x32 es decir 64 columnas por 32 renglones.

Los gráficos se guardan en memoria como sprites, y se pueden renderear sprites de 8 pixeles de ancho por hasta 15 pixeles de alto. Además CHIP-8 incluye detección de colisiones.

Sonido

CHIP-8 es capaz de reproducir sonido. Para lograrlo existe un registro sound de 8 bits. Este registro se decrementa automáticamente a una frecuencia de 60Hz.

Mientras que el registro S sea mayor a cero, CHIP-8 reproduce un sonido. El tono del sonido es a discresión del programador.

Dispositivos de Entrada

El único dispositivo de entrada es el teclado. El intérprete asume un teclado hexadecimal, es decir 16 teclas del 0x0 a 0xF acomodadas de la siguiente manera:

|---+---+---+---|
| 1 | 2 | 3 | C |
| 4 | 5 | 6 | D |
| 7 | 8 | 9 | E |
| A | 0 | B | F |
|---+---+---+---|

Hay opcodes específicos para el manejo del teclado. Se puede saltar la siguiente instrucción dependiendo si una tecla específica está siendo presionada o no, o detener la ejecución del programa hasta que una tecla sea presionada.

Implementación de un intérprete CHIP-8

Con esta información en mano podemos implementar un intérprete CHIP-8 prácticamente en cualquier lenguaje, siempre y cuando tengamos acceso al teclado, reproducir sonido (o el buzzer si se tiene) y alguna manera de desplegar gráficos.

No es la intención de este artículo mostrar una implementación completa, sino resaltar las partes más interesantes de una implementación de un intérprete CHIP-8. En este caso hemos decidido utilizar Clojure, pero aunque el código es específico en este lenguaje, las técnicas utilizadas son las mismas.

Lo que vamos a implementar es un intérprete, que es la técnica más simple. En un intérprete se analiza cada instrucción, y se implementa la acción equivalente. El principal problema de un intérprete es que es lento, pero los ~520Hz del CPU de CHIP-8 no representan ningún problema para nosotros. Que viva la tecnología.

Pero para que no se queden con la curiosidad, la otra opción es la recompilación dinámica. Un dynarec o JIT (de las sigas en inglés Just In Time) lo que hace es traducir las instrucciones del CPU a emular (en este caso CHIP-8) a las instrucciones nativas del CPU host y las guarda en un caché para ser reutilizadas. Es una técnica mucho más complicada de programar y depurar, pero con excelentes resultados.

Tamaño de los datos

El primer problema con el que nos topamos es el tamaño de los datos. En CHIP-8 manejamos datos de 16 y 8 bits, mientras que en Clojure:

chip8.core> (type 8)
java.lang.Long

El tipo Long es la representación en complemento a 2 de un entero de 64 bits, con signo.

Ya que el tipo de dato java.lang.Long es más que suficiente para contener cualquier operando que vayamos a utilizar en CHIP-8, podemos simplemente usar java.lang.Long para todo, y crear una función para obtener una secuencia de bits cuando necesitemos operar con los bits individuales.

(defn bits [n s]
  (->> (map
        (fn [i]
          (bit-and 0x01 i))
        (iterate (fn [i] (bit-shift-right i 1))
                 n))
       (take s)
       reverse))

Para explicar la función anterior tomemos un ejemplo. Digamos el número 0xB (11 decimal). Para representar 0xB solo necesitamos 4 bits, por lo que claramente cabe en un java.lang.Long. Lo primero que hace la función bits es tomar el número 0xB y crear una secuencia con el resultado de aplicarle un corrimiento a la derecha, de manera infinita. El resultado sería:

(11 5 2 1 0 0 0 0 ...)

O lo que es lo mismo en bits:

(1011 0101 0010 0001 0000 ...)

Después a cada elemento de esta secuencia le aplicamos una máscara con la operación and y el operando 0x01. Esto nos va a permitir tomar el valor del bit menos significativo de cada elemento de la secuencia. Algo como esto:

(bit-shift-right 1011 0001) ;; 1
(bit-shift-right 0101 0001) ;; 1
(bit-shift-right 0010 0001) ;; 0
(bit-shift-right 0001 0001) ;; 1

El resultado es (1 1 0 1 0 0 0 0 ...). Lo único que resta es tomar s elementos de la secuencia infinita, dependiendo si queremos el resultado en 4, 8 o 16 bits, y finalmente aplicar un reverse para que la secuencia quede en orden:

chip8.cpu> (bits 11 4)
(1 0 1 1)

Obviamente esta solución está lejos de ser óptima con el uso de la memoria, ya que representa cada número con 64 bits cuando podríamos usar 8. Es decir, estamos usando 8 veces más memoria de la necesaria.

La otra opción es utilizar los tipos de datos que se adapten al tamaño específico. Por ejemplo, para representar la memoria pudiéramos usar un arreglo de bytes de 4096 posiciones:

(defonce memory (byte-array 4096))

El tipo byte es de 8 bits así que no desperdiciamos memoria. Siguiendo con el ejemplo de la memoria, podemos definir un par de funciones read-mem y write-mem para leer y escribir a la memoria respectivamente.

Aquí el problema es otro. Supongamos que escribimos un valor a la memoria, y después leemos el valor para asegurarnos que se escribió correctamente:

(write-mem 0x200 0xFF)
(read-mem 0x200)

;; Result
-1

Esperábamos 255 de resultado, y obtenemos -1. El problema es que Clojure usa representación en complemento a dos, con signo. Eso último es importante. Entonces un byte en realidad no puede representar del 0 al 255, sino del -128 al 127.

Los bits que forman el byte son los mismos, pero al momento de querer hacer una comparación nos vamos a topar con un problema:

(= 0xFF (read-mem 0x200))

;; Result
false

Para resolver este problema podemos de nuevo aplicar un and al número leído de la memoria, convirtiéndolo en un java.lang.Long y ahora si, su valor será el esperado:

(= 0xFF (byte->ubyte (read-mem 0x200)))

;; Result
true

Siguiendo con el tema de los números con signo, si tratamos de escribir el valor 0xFF a un byte, esto nos va a generar un error ya que 0xFF no cabe en 8 bits si estamos usando representación con signo:

(aset-byte memory 0x200 0xFF)
IllegalArgumentException Value out of range for byte: 255  clojure.lang.RT.byteCast (RT.java:1083)

Para eso entonces necesitamos usar unchecked-byte:

(aset-byte memory 0x200 (unchecked-byte 0xFF))

Que internamente va a convertir 0xFF a -1 como ya vimos anteriormente.

Evaluando opcodes

Pudiendo leer y escribir a la memoria, lo primero que vamos a querer es ejecutar opcodes. Incluso antes de implementar cualquier opcode es bueno tener claro cual va a ser el mecanismo para evaluar un opcode en particular.

Y aquí hay varias opciones. La primera y más intuitiva es un switch o if anidado. Rápidamente se va a salir de control, y va a ser una fuente de bugs sutiles difíciles de identificar.

Otra opción es utilizar pattern matching, es decir algún mecanismo o librería externa para especificar un patrón de datos, y en base a eso ejecutar una función específica.

Supongamos que recibimos el opcode como un valor entero. Por ejemplo el opcode para dibujar un sprite en pantalla es dxyn donde x, y y n pueden tomar cualquier valor del 0x0 al 0xF. Entonces necesitamos un patrón que diga "Si recibimos un opcode que empiece con D y las otras 3 posiciones lo que sea, ejecuta la función opcode-dxyn".

(defn evaluate
  [opcode]
  (let [opcode-match (vec (format "%04X" opcode))]
    (match opcode-match
           [\D  _  _  _] (opcode-dxyn (bit-shift-right (bit-and opcode 0x0F00) 8)
                                      (bit-shift-right (bit-and opcode 0x00F0) 4)
                                      (bit-and opcode 0x000F)))))

Primero formateamos el opcode en entero, como una cadena hexadecimal de cuatro posiciones, y lo pasamos a un vector de tal manera que cada elemento de la cadena se convierte en un caracter.

Después definimos la forma de los datos, en este caso [\D _ _ _] donde _ significa "lo que sea". Entonces mientras empiece con D, siempre va a ejecutar opcode-dxyn.

Finalmente le pasamos los argumentos a la función que implementa el opcode. Como podemos observar, los valores con los que opera forman parte del opcode mismo, entonces basta con aplicar algunos corrimientos y máscaras al opcode en su representación de entero, y listo.

Siguiendo con el ejemplo del opcode dxyn este recibe tres parámetros de un nibble (4 bits) cada uno:

  1. x le aplicamos una máscara con 0x0F00 y 8 corrimientos (2 nibbles) a la derecha.
  2. y le aplicamos una máscara con 0x00F0 y 4 corrimientos (1 nibble) a la derecha.
  3. n le aplicamos una máscara con 0x000F. Aquí no es necesario ningún corrimiento ya que el dato ya lo tenemos en la posición deseada.

Y así sucesivamente para cada opcode.

(defn evaluate
  [opcode]
  (let [opcode-match (vec (format "%04X" opcode))]
    (match opcode-match
           [\0 \0 \E \0] (opcode-00E0)
           [\0 \0 \E \E] (opcode-00EE)
           [\1  _  _  _] (opcode-1nnn (bit-and opcode 0x0FFF))
           [\2  _  _  _] (opcode-2nnn (bit-and opcode 0x0FFF))
           [\3  _  _  _] (opcode-3xkk (bit-shift-right (bit-and opcode 0x0F00) 8)
                                      (bit-and opcode 0x00FF))
           [\4  _  _  _] (opcode-4xkk (bit-shift-right (bit-and opcode 0x0F00) 8)
                                      (bit-and opcode 0x00FF))
           [\5  _  _ \0] (opcode-5xy0 (bit-shift-right (bit-and opcode 0x0F00) 8)
                                      (bit-shift-right (bit-and opcode 0x00F0) 4))
           [\6  _  _  _] (opcode-6xkk (bit-shift-right (bit-and opcode 0x0F00) 8)
                                      (bit-and opcode 0x00FF))
           [\7  _  _  _] (opcode-7xkk (bit-shift-right (bit-and opcode 0x0F00) 8)
                                      (bit-and opcode 0x00FF))
           [\8  _  _ \0] (opcode-8xy0 (bit-shift-right (bit-and opcode 0x0F00) 8)
                                      (bit-shift-right (bit-and opcode 0x00F0) 4))
           [\8  _  _ \1] (opcode-8xy1 (bit-shift-right (bit-and opcode 0x0F00) 8)
                                      (bit-shift-right (bit-and opcode 0x00F0) 4))
           [\8  _  _ \2] (opcode-8xy2 (bit-shift-right (bit-and opcode 0x0F00) 8)
                                      (bit-shift-right (bit-and opcode 0x00F0) 4))
           [\8  _  _ \3] (opcode-8xy3 (bit-shift-right (bit-and opcode 0x0F00) 8)
                                      (bit-shift-right (bit-and opcode 0x00F0) 4))
           [\8  _  _ \4] (opcode-8xy4 (bit-shift-right (bit-and opcode 0x0F00) 8)
                                      (bit-shift-right (bit-and opcode 0x00F0) 4))
           [\8  _  _ \5] (opcode-8xy5 (bit-shift-right (bit-and opcode 0x0F00) 8)
                                      (bit-shift-right (bit-and opcode 0x00F0) 4))
           [\8  _  _ \6] (opcode-8xy6 (bit-shift-right (bit-and opcode 0x0F00) 8)
                                      (bit-shift-right (bit-and opcode 0x00F0) 4))
           [\8  _  _ \7] (opcode-8xy7 (bit-shift-right (bit-and opcode 0x0F00) 8)
                                      (bit-shift-right (bit-and opcode 0x00F0) 4))
           [\8  _  _ \E] (opcode-8xye (bit-shift-right (bit-and opcode 0x0F00) 8)
                                      (bit-shift-right (bit-and opcode 0x00F0) 4))
           [\9  _  _ \0] (opcode-9xy0 (bit-shift-right (bit-and opcode 0x0F00) 8)
                                      (bit-shift-right (bit-and opcode 0x00F0) 4))

           [\F  _ \1 \E] (opcode-fx1e (bit-shift-right (bit-and opcode 0x0F00) 8))
           [\F  _ \3 \3] (opcode-fx33 (bit-shift-right (bit-and opcode 0x0F00) 8))
           [\F  _ \5 \5] (opcode-fx55 (bit-shift-right (bit-and opcode 0x0F00) 8))
           [\F  _ \6 \5] (opcode-fx65 (bit-shift-right (bit-and opcode 0x0F00) 8))
           [\A  _  _  _] (opcode-annn (bit-and opcode 0x0FFF))
           [\B  _  _  _] (opcode-bnnn (bit-and opcode 0x0FFF))
           [\C  _  _  _] (opcode-cxkk (bit-shift-right (bit-and opcode 0x0F00) 8)
                                      (bit-and opcode 0x00FF))
           [\D  _  _  _] (opcode-dxyn (bit-shift-right (bit-and opcode 0x0F00) 8)
                                      (bit-shift-right (bit-and opcode 0x00F0) 4)
                                      (bit-and opcode 0x000F))

           ;; and last...
           [\0  _  _  _] (opcode-0nnn))))

Si lo comparamos con una serie de if anidados, esta implementación nos permite expander la tabla a como vamos implementando nuevos opcodes de una manera más limpia y fácil de razonar.

Una vez teniendo la tabla de opcodes completa, lo que sigue es una manera de ejecutar instrucción por instrucción (step). Como se mencionó anteriormente, todas las instrucciones ocupan 2 bytes, por lo que es necesario leer los bytes de la memoria referenciados por PC y PC+1 y llamar a evaluate con el resultado:

(defn step
  "Evaluate a single instruction"
  []
  (let [op-a (read-mem (aget PC 0))
        op-b (read-mem (+ (aget PC 0) 1))
        opcode (str (format "%02X" (bit-and 0xFF op-a)) (format "%02X" (bit-and 0xFF op-b)))]
    (evaluate (Integer/parseInt opcode 16))))

Pintando la pantalla

De todos los opcodes en CHIP-8, el que merece especial atención es dxyn, también conocido como DRAW.

Por muy básico que sea, CHIP-8 tiene noción de sprites. Un sprite es una serie de bytes donde cada bit representa un pixel. Un 0 es un pixel "apagado" y un 1 es un pixel "prendido". Por ejemplo el siguiente diseño:

Screen-Shot-2018-10-03-at-8.16.19-PM-1

Puede ser representado por un sprite de 7 bytes:

Hex    Bin        Dots
0x18   00011000   ...XX...
0x24   00100100   ..X..X..
0x42   01000010   .X....X.
0x81   10000001   X......X
0x99   10011001   X..XX..X
0x66   01100110   .XX..XX.
0xC3   11000011   XX....XX

La representación "dots" es simplemente para darle claridad al sprite. También podemos deducir que el bit más significativo del primer byte del sprite corresponde al pixel superior izquierdo, y el bit menos significativo del último byte corresponde al pixel inferior derecho.

El opcode dxyn recibe tres parámetros:

  1. x: registro que contiene el valor de la coordenada x donde se va pintar el pixel 0,0 del sprite (es decir, el bit más significativo del primer byte que compone el _sprite).
  2. y: registro que contiene el valor de la coordenada y donde se va a pintar el sprite.
  3. n: el número de bytes (o renglones) que componen al sprite. En un solo ciclo podemos pintar un sprite de hasta 8x15.

Otras cosas que son necesarias saber:

  1. Todos los sprites son de 8 pixeles de ancho.
  2. Si las coordenadas causan que el sprite se salga de la pantalla, la parte que se sale se pinta del lado contrario (wrapping). Es decir si pintamos una linea recta en las coordenadas 63,0, tan solo el primer pixel se va a pintar en la esquina superior derecha, y el resto se va a pintar en la esquina superior izquierda, algo así:
--------------------------------
|.....                       ..|
|                              |
--------------------------------

Pudiéramos pensar que hasta aquí tenemos suficiente información para implementar el algoritmo que pinta sprites a la pantalla, pero no es así. Aún faltan dos detalles críticos que requieren explicarlo más a detalle:

Los pixeles se pintan con XOR

Anteriormente dijimos que un 1 en un sprite es un pixel "encendido", y un 0 es un pixel "apagado". Esto simplemente no es correcto. En mi defensa lo dije para simplificar la explicación de cómo se representan los sprites en memoria.

Pero ahora si viene la verdadera historia de cómo un bit de un sprite pasa de ser un dato en memoria, a un pixel en pantalla.

Supongamos que queremos pintar a nuestro extraño enemigo en pantalla, en las coordenadas 0,0:

Hex    Bin        Dots
0x18   00011000   ...XX...
0x24   00100100   ..X..X..
0x42   01000010   .X....X.
0x81   10000001   X......X
0x99   10011001   X..XX..X
0x66   01100110   .XX..XX.
0xC3   11000011   XX....XX

Y supongamos que estamos trabajando con una pantalla totalmente en blanco.

Para pintar el sprite completo:

  1. Se carga al registro I la dirección donde está guardado el primer byte del sprite.
  2. Se carga a un registro x el valor de la coordenada x que es 0 en este caso. Supongamos que el registro es el 0xA.
  3. Se carga a un registro y el valor de la coordenada y que es 0 en este caso. Supongamos que el registro es el 0xB.
  4. Se llama al opcode DAB7.

En este momento lo que hace el intérprete es tomar el primer byte del sprite: 00011000 y el byte que corresponde a lo que está pintado en la pantalla desde 0,0 hasta 7,0, y les aplica un XOR. El resultado del XOR es lo que finalmente se va a pintar en la pantalla.

Volviendo al ejemplo, sería XOR 00011000 00000000. Si vemos la tabla de verdad del XOR:

x y | o
----|--
0 0 | 0
0 1 | 1
1 0 | 1
1 1 | 0

Entonces aplicando XOR en nuestro caso, nos queda como resultado 00011000, que es igual al primer byte del sprite, y por lo tanto se pinta lo siguiente: ...XX...

Hay una razón muy importante por la cual se hace la operación XOR. Si vemos la tabla de verdad del XOR nos podemos dar cuenta que si ambos bits son iguales, el resultado es un pixel apagado. Eso quiere decir que podemos pintar un sprite y borrarlo con exactamente la misma instrucción y los mismos operandos.

Supongamos que tenemos el siguiente sprite: 00111100 y lo pintamos a la pantalla en las coordenadas 0,0 con el siguiente pseudocódigo:

LOAD V0,0  ;; carga 0 al registro V0
LOAD V1,0  ;; carga 0 al registro V1
LOADI $100 ;; carga 0x100 al registro I
DRAW $1    ;; ejecuta D011

Si después queremos borrar ese sprite, basta con ejecutar exactamente la misma rutina ya que XOR 00111100 00111100 da como resultado 00000000. Esto es muy conveniente, ahorra espacio, permite reutilizar código y facilita una operación extremadamente común en videojuegos: animar un sprite (pintarlo, borrarlo y pintarlo en otro lugar).

Detección de colisiones

El último detalle a considerar sobre los gráficos del CHIP-8 es que el mismo opcode que pinta sprites se encarga de la detección de colisiones. La detección de colisiones se hace con el registro VF. Cuando VF = 1 es que hubo una colisión entre dos sprites.

¿Pero qué es una colisión? es cuando a raíz de pintar un nuevo sprite (aplicando el XOR como se explica en la sección anterior), un pixel en la pantalla que estaba "encendido" ahora ya no lo está. Si (y solo si) esto sucede, entonces VF = 1. De lo contrario no se hace nada con VF.

Algoritmo para pintar la pantalla

Entonces un algoritmo de alto nivel para pintar sprites es:

  1. Leemos el sprite de la memoria, byte por byte.
  2. Por cada byte del sprite, leemos el byte correspondiente del framebuffer, cuidando el wrapping de la pantalla.
  3. XOR byte-sprite byte-framebuffer.
  4. Pintamos en la pantalla el resultado del Paso 3, en las coordenadas correspondientes, cuidando el wrapping de la pantalla.
  5. Escribimos la bandera de colisión en caso de ser necesario.

Paso a paso

Pudiendo leer datos de la memoria y pudiendo desplegar gráficos a la pantalla, lo que sigue es la parte divertida: ejecutar roms.

En el caso de CHIP-8, los roms son simplemente un bloque de datos binarios. No tienen ningún formato específico, y eso facilita mucho las cosas. Para leer el rom simplemente hay que leer cada byte en secuencia e ir escribiendolo a la memoria de la máquina virtual. Los programas de CHIP-8 comienzan en la dirección 0x200 por lo que hay que empezar a escribir el rom a partir de esta dirección de memoria, de otro modo no va a encontrar la primera instrucción a ejecutar.

Con el rom en memoria, necesitamos otras funciones básicas para poder probar nuestro emulador:

  1. step. Evaluar una sola instrucción. Lee dos bytes de la memoria comenzando por la dirección apuntada por el apuntador de programa PC, y ejecuta el opcode correspondiente. Recordemos que todas las instrucciones son de 2 bytes, por lo que después de cada opcode, PC debe avanzar 2 bytes, o 4 si se cumplen ciertas condiciones en los opcodes de salto y bifurcaciones.
  2. reset. Regresar el estado de la máquina virtual a su estado inicial. Registros y memoria a 0, PC a 0x200, etc.
  3. debug. No es estrictamente necesaria, pero eventualmente vas a necesitar imprimir el contenido de los registros y tal vez una sección de la memoria.
  4. pause y resume. Igual no es estrictamente necesaria, pero es invaluable poder detener la ejecución en cualquier momento para inspeccionar el contenido de los registros y la memoria.

Debuggeando

Parte de lo que hace tan atractivo (y didáctico) el programar un emulador, es que requiere de un enorme trabajo para llevarlo hasta el punto en el que puedes ejecutar incluso parcialmente un rom.

Identificar y corregir errores puede ser un proceso tedioso y frustrante. Sin embargo, cuando logras identificar el error y esto genera un efecto dominó permitiéndote ejecutar más roms, se siente una satisfacción muy grande. Nada como ver la pantalla inicial de Space Invaders:

space-invaders

Es por esto que creo conveniente dedicar una sección a técnicas para debuggear tu emulador.

Estrategia 1: Pruebas unitarias

Por ahí me topé con una cita muy acertada sobre las pruebas unitarias:

Las pruebas unitaras son como el sexo en la adolescencia: todo el mundo dice que lo está haciendo pero es mentira, y los pocos que si lo están haciendo, lo hacen mal.

Especialmente durante la primera fase del emulador, cuando aún estamos implementando opcodes y no tenemos manera de desplegar nada a la pantalla, es de suma importancia poder probar cada opcode de manera aislada y asegurarnos que la interpretación es correcta. Y no solo de opcodes sino también de funciones relacionadas. Por ejemplo lectura y escritura de registros, la pila, memoria, etc.

Básicamente estaremos desarrollando mini-programas, escribiendo datos a la memoria y los registros para después ejecutar la función que interpreta el opcode.

Lo bueno de las pruebas unitarias es que nos dan confianza de que el opcode funciona como nosotros pensamos que debe funcionar. La otra es que si hacemos una modificación a funciones básicas, o queremos probar una implementación alternativa, tenemos las pruebas unitarias para respaldarnos.

Lo malo es que en realidad estamos probando nuestro entendimiento del funcionamiento. Las pruebas unitarias reflejan nuestro entendimiento, y no pueden decirnos si este entendimiento es correcto o incorrecto.

Estrategia 2: Roms propios

Eventualmente querrás probar una serie de opcodes, o dicho de otra manera un programa. La mejor manera de hacerlo es escribir tus propios programas. Para esto solo necesitas un hex editor. CHIP-8 no tiene un formato de programa, por lo que escribir programas directamente en el bytecode es viable. Tedioso, pero viable.

Para escribir programas, simplemente introduce los bytes que representan los opcodes, guarda el archivo como binario, y finalmente ejecuta el programa en tu emulador y observa la salida. Necesitas una manera de leer el programa y cargarlo a la memoria de tu emulador.

Esto solo funciona para programas relativamente simples. Cualquier cosa remotamente parecida a un juego sería extremadamente tedioso escribir "a mano", por lo que se recomienda usar un ensamblador. CHIP-8 no define unlenguaje ensamblado "oficial", pero existen muchos ensambladores competentes. Simplemente elige uno y aprende a programar en CHIP-8 ASM.

En este punto recomiendo que tengas a la mano un debugger. De preferencia uno que te permita modificar los valores de los registros del CPU e inspeccionar la memoria mientras se ejecuta el programa paso a paso. De esta manera puedes ejecutar cada instrucción de tu programa, y asegurarte que el valor en los registros es el mismo tanto en tu emulador como en el debugger. En el momento que veas una diferencia, ya tienes el opcode aislado y puedes corregir el problema.

Estrategia 3: Roms de terceros

Aquí empieza la verdadera prueba. Para llegar a este punto necesitas primero haber implementado todos los opcodes, que para el caso de CHIP-8 solo son 35. Además necesitas poder pintar la pantalla. Recordemos que CHIP-8 es una máquina virtual diseñada específicamente para videojuegos, por lo que la mayoría de los roms son visuales.

Descarga tantos roms como quieras, y comienza a ejecutarlos. Si ya tienes interacción con el teclado incluso puedes jugarlos. Si no ves nada en la pantalla, lo más seguro es que tu emulador se haya quedado atorado en un opcode. Tal vez por un salto equivocado, o una comparación erronea. Existen demasiadas cosas que pueden salir mal.

En el momento que detectes algo incorrecto, trata de aislar el problema. Si cuentas con el código fuente del programa, estúdialo. Si no, siempre puedes usar tu hex editor para ver el bytecode y analizar lo que está haciendo el programa.

Otra buena idea es comparar la ejecución de tu emulador con la de otros emuladores. Es posible que el error no sea tuyo, y sea del rom en cuestión.

Errores comunes

Finalmente voy a comentar sobre los errores más comunes con los que me he topado al programar mi propio emulador.

En mi caso primero me aseguré que mis rutinas para pintar la pantalla fueran correctas, para eliminar cualquier error que fuera causado por cómo se pinta la pantalla, en vez del estado interno del emulador.

Uno de los errores más comunes es con el opcode fx33. Este opcode toma el valor del registro Vx y guarda su representación en Binary Coded Decimal en las direcciones I, I+1 e I+2 para las centenas, decenas y unidades, respectivamente.

En mi caso el error se manifestó de la siguiente manera: al estar jugando tetris (uno de los primeros juegos que intenté correr) el score por linea era 100. Pensé que era normal, hasta que lo probé en otro emulador y ahí el score por linea era 001. En el juego pong, el síntoma era que cuando un jugador anotaba un punto, el punto le contaba al jugador contrario.

Finalmente la razón era la misma, y al solucionarlo para uno se solucionaron ambos roms. El problema era que no estaba considerando el caso cuando el número a codificar como BCD no tiene centenas o decenas. En esos casos se debe rellenar con 0.

Para dar con el error tuve que estudiar el código de pong. Me di cuenta que el puntaje se lleva en uns olo registro. Para el jugador de la izquierda, le suma 10 a cada punto, y para el jugador a la derecha solo le suma 1. Entonces cuando el jugador de la izquiera anota, Vx vale 10, pero como mi codificación BCD era incorrecta, esto se desplegaba como 01 lo que hacía ver que el punto iba para el jugador contrario.

El otro error que me llevó mucho más tiempo resolver, tenía que ver con la detección de colisiones (o eso pensaba yo).

El síntoma era que en juegos como "brix" (un clon de breakout) había ocasiones en las que la bola chocaba contra ladrillos "fantasma", o sea ladrillos que ya habían sido eliminados de la pantalla. Y lo que era más raro, cuando esto sucedía, los ladrillos volvían a aparecer.

Si lo pensamos un poco es un tanto obvio por qué vuelven a aparecer; al detectar una colisión normalmente el juego vuelve a pintar el mismo sprite para borrarlo, solo que en este caso ya estaba borrado y entonces el resultado es que vuelve a aparecer.

El problema entonces no era que "reaparecieran". El problema era por qué se detectaba la colisión. Eso me llevo a una larga búsqueda del opcode culpable, seguramente alguno que modificara el valor de VF. Finalmente delimité el problema a los opcodes 8xy5 y 8xy7. Sin embargo después de "corregirlos", el problema persistía.

Lo que hice finalmente es bajar la velocidad del CPU a una frecuencia extremadamente baja, que me permitiera ver paso a paso el proceso que seguía el CPU y la pantalla sin tener que ejecutar cada instrucción manualmente. Además, modifiqué el generador de números aleatorios para regresar un valor constante, esto para que la pelota siempre iniciara con la misma velocidad y dirección.

Por puro azar, la constante que seleccioné para reemplazar el número aleatorio causaba que la pelota pasara exactamente entre dos ladrillos. Por mi experiencia ejecutando el juego en otros emuladores, sabía que esto no debería causar una colisión, pero en mi emulador si la causaba. En ese momento se me iluminó la mente:

¿Y si el problema no es el cálculo de la bandera VF, sino que en realidad lo que se está leyendo del framebuffer es incorrecto?

Así fue. Básicamente la función para leer el estado actual de la pantalla estaba incorrecta, y en ciertos casos causaba que un bit que estaba "apagado" lo detectara como "encendido", y al calcular la colisión, esta la detectaba (correctamente) como una colisión válida.

Y así es esto, una combinación de conocimientos técnicos, corazonadas y algo de suerte.

Palabras finales

Al estar batallando con mi emulador le compartí mi frustración a Francisco Soto, para desahogarme principalmente.

Minutos después el Slack de la comunidad devz estaba inundado de comentarios sobre CHIP-8, y por lo menos dos personas más comentaron su deseo de crear emuladores propios...

...de una especificación de una máquina virtual de hace casi 50 años...

Eso es lo que hace a los proyectos de emulación tan atractivos.

Links

  • chip8-clj. Mi implementación de un intérprete CHIP-8 que desarrollé principalmente para poder escribir este artículo. Tengo toda la intención de hacerlo más amigable (actualmente se interactúa por medio del REPL) pero no es una prioridad.
  • Documentación CHIP-8. Contiene algunos errores, pero en general es bastante completa.