Vamos ahora con el tema de los textos. Pintar letras no es algo demasiado complejo una vez que hemos pintado sprites, por lo que no voy a ahondar demasiado en ello. Sin embargo, sí hay un detalle que no es nada trivial, y es conseguir meter mucho texto en poco espacio. En mi juego Escape from M.O.N.J.A.S. tenía unos 10 kbytes de texto, y tenía el problema de que, sencillamente, no me cabía en la memoria. Sin embargo, el texto tiene la característica de que tiene mucha redundancia, por lo que es muy compresible. Así que decidí intentar ir por esa ruta.

Alguno pensará que comprimir datos en un Z80 a 3,5MHz es una quimera, algo totalmente imposible, por culpa de la poca potencia; sin embargo esto no tiene por qué ser así: hay algoritmos en los que lo complicado es comprimir, pero la descompresión es muy sencilla y rápida.

El algoritmo que utilicé fue el LZSS (cuando hice la primera implementación no sabía que se llamaba así, pero es tan sencillo en concepto que era obvio que tenía que estar ya inventado). La idea es sustituir cada bloque que sea idéntico a otro anterior por un par (offset, tamaño) que apunte a dicho bloque anterior. El ejemplo más típico que se pone es el del poema Green Eggs and Ham, y lo podemos ver explicado en la página de la wikipedia.

En mi caso me aprovecho además de que los caracteres ASCII tienen todos el bit 7 a cero, por lo que puedo utilizar un byte con el bit 7 a uno para indicar que ahí comienza un bloque comprimido. Cada bloque comprimido está formado por dos bytes, y como el bit 7 del primero tiene que estar a uno, eso me deja 15 bits en total para almacenar el offset y el tamaño del bloque. Tras hacer varias pruebas, encontré que para mi cantidad de texto el tamaño óptimo es de tres bits para el tamaño y 12 bits para el offset. Por supuesto, dado que no compensa comprimir bloques de tamaño cero, uno o dos, el valor almacenado será el tamaño menos tres (o sea, entre 3 y 10). Además, el offset será siempre a partir del principio del bloque completo de textos, y no «desplazamiento hacia atrás desde el punto actual». El motivo de esto es que al principio es donde hay más texto sin comprimir, y, por tanto, donde habrá más oportunidades de encontrar repetido texto de más adelante.

Esta implementación tiene varias cosas interesantes. Para empezar, es muy sencilla de implementar, y en segundo lugar, no necesita memoria intermedia para tablas (cosa que otros algoritmos, como el LZW, sí necesitan). Para simplificar aún más el algoritmo, habrá una condición extra: no habrá recursividad (esto es: dentro de un bloque comprimido no habrá otros bloques comprimidos, sino que siempre apuntarán a ristras de caracteres ASCII). Esto tiene el inconveniente de que la compresión es menor, pero simplifica sobremanera el algoritmo y reduce la memoria necesaria para la pila (y dado que trabajamos con threads, interesa que este valor sea lo menor posible).

Lo más interesante de este algoritmo así descrito es que se puede utilizar al vuelo; esto es: podemos ir imprimiendo los caracteres a medida que los vamos descomprimiendo. Y si le sumamos que una cadena ASCII normal es un bloque comprimido válido, tiene la ventaja extra de que podemos utilizar la misma función para imprimir textos «normales», sin comprimir.

Habrá una limitación extra, y es que un bloque comprimido no puede jamás cruzar la frontera entre dos «frases» o «bloques de texto». Esto es fundamental, pues si queremos poder descomprimir al vuelo una frase, necesitamos que empiece en un byte concreto, y no en mitad de un bloque comprimido. Así, si tenemos estas tres frases:

esta es la primera frase
la primera frase empieza en esta
es la primera que veo

tenemos que respetar las fronteras entre frases y no comprimir el final de la segunda junto con el principio de la tercera en un único bloque, pues entonces no podríamos descomprimir la tercera de manera independiente, sino que tendríamos que descomprimir la segunda antes, almacenando el resultado, y buscar el punto de unión.

Por desgracia, si la descompresión es muy sencilla y rápida, la compresión es endiabladamente fastidiada (con jota). De hecho, por lo que he visto, ni siquiera parece existir un algoritmo óptimo, sino sólo diferentes aproximaciones. Esto puede chocar, pues en apariencia basta con empezar por el principio e ir buscando si el bloque de caracteres que sigue ya está repetido anteriormente. Sin embargo, por sorprendente que parezca, el orden de las frases puede afectar (y mucho) al nivel de compresión obtenido. Veámoslo con este ejemplo:

12345678
12345
345678

Estas tres «frases» se pueden comprimir como

12345678
(0,5)
(2,6)

Esto es: la segunda frase es un bloque con los 5 caracteres que hay a partir del offset 0, y la tercera frase es un bloque con los 6 caracteres a partir del offset 2. En total, 12 bytes. Sin embargo, si reordenamos estas frases así:

12345
12345678
345678

tenemos que la compresión será

12345
(0,5)678
(2,3)(7,3)

que consume 14 bytes.

La solución a esto ha sido ir probando a cambiar de sitio una frase de cada vez, recomprimir, y si le nivel de compresión es mejor, guardarlo y volver a probar, mientras que si el cambio es a peor, deshacerlo y probar de nuevo. Una pequeña mejora consiste en no deshacerlo con una probabilidad pequeña (el 0,1%), de manera que sea posible «volver atrás», y que el algoritmo pueda probar otros caminos lejos de un mínimo local, pero siempre conservando en memoria la mejor combinación hallada hasta el momento. Esto tiene el inconveniente de que para conseguir altos niveles de compresión se necesita mucho tiempo (para los textos actuales dejé mi PC trabajando unas 24 horas).

Además, existe otra optimización muy importante, que consiste en intentar comprimir antes los bloques de mayor tamaño, e ir probando luego con los de menor tamaño. Así, dado que el tamaño de un bloque puede ir de 3 a 10 bytes, primero busco todos los bloques de 10 bytes que puedo comprimir; una vez hallados, procedo a buscar en las cadenas sin comprimir que quedan los bloques de 9, luego los de 8, etc. Esto es importante porque puede ocurrir que por comprimir ahora un bloque de 3, más adelante no pueda comprimir un bloque mayor. Aquí tenemos un ejemplo:

12345678
ab456dfg
b456df

En este caso, si comprimo en el orden que aparece, tendré

12345678
ab(3,3)dfg
b(3,3)(12,3)

que son 20 bytes, mientras que si comprimo por tamaño, tendré:

12345678
ab456dfg
(9,6)

que son 18 bytes.

La diferencia entre aplicar o no estas dos optimizaciones en brutal: sin ellas, conseguía una compresión del 68% aproximadamente, mientras que aplicándolas, los textos quedan reducidos a un valor en torno al 59,7%. Una diferencia abismal, que me permitió reducir los más de diez kilobytes originales en unos seis, y que entrase por fin todo en memoria.

El compresor que escribí, además, parte de un fichero en formato assembler normal y saca el mismo fichero también en assembler pero con los datos comprimidos. Eso significa que se conservan las etiquetas, por lo que para descomprimir una frase sólo hay que pasar la etiqueta correspondiente a la rutina de descompresión/impresión, y listo.

Queda, eso sí, un detallito especial, que es qué hacemos con los caracteres específicos del español (la eñe y las aperturas de interrogación y exclamación; las tildes decidí obviarlas). La solución que se me ocurrió fue mapearlas en caracteres por debajo de 127 que no se utilicen, como el asterisco, el porcentaje, etc, reemplazándolos en el juego de caracteres del Spectrum. Por supuesto, para simplificar el trabajo, el compresor también se encarga de esta tarea, por lo que en el código fuente original los textos irán en UTF-8, y el compresor se encargará de sustituir la eñe por el asterisco, etc.

El código fuente está en el fichero convert_sentences.py en el repositorio de Escape from M.O.N.J.A.S.

Ha llegado el momento de empezar a pintar cosas en la pantalla. Obviamente lo que queremos pintar serán Sprites. Como explica la wikipedia, se trata de gráficos 2D que se integran con una escena de fondo. Como sabemos, el Spectrum no tiene soporte de sprites por hardware, lo que significa que nos toca a nosotros hacer todo el trabajo de pintarlos. Afortunadamente, en las entradas anteriores vimos cómo hacer una rutina que copie a la pantalla una imagen completa desde un buffer organizado de manera secuencial, y esto nos va a simplificar la tarea, como veremos.

Lo primero que necesitamos saber para pintar algo en pantalla es a partir de qué dirección de memoria tenemos que hacerlo. Si recordamos, la pantalla del Spectrum está formada por una matriz de 256 píxels de ancho por 192 de alto, y cada píxel puede tener dos colores, por lo que cada uno ocupa un bit. Esto significa que cada fila o scanline de la pantalla ocupa 32 bytes, y la parte de píxeles de la pantalla ocupa en total 6 144 bytes o 6 Kbytes exactos.

Sin embargo, justo a continuación viene una segunda zona denominada atributos, que define una matriz de 32 por 24 atributos y asigna un byte a cada uno. Este byte de atributos especifica qué colores tendrán un grupo de píxeles. En concreto, cada byte define dos colores para cada grupo de 8×8 píxeles de la pantalla: uno será el color que se mostrará cuando el bit correspondiente al píxel esté a cero, y el otro cuando esté a uno. Esta zona empieza en la dirección de memoria 22 528 y ocupa un total de 768 bytes. Este sistema permite al Spectrum mostrar hasta 16 colores simultáneos en pantalla pero consumiendo muy poca memoria.

Como ya vimos en la primera entrada, la organización de la pantalla es algo caótica. Veámoslo en un gráfico:

Vemos que los bytes situados en las direcciones de memoria en hexadecimal 0x4000, 0x4100, 0x4200, 0x4300, 0x4400, 0x4500, 0x4600 y 0x4700 se corresponden con el bloque de 8×8 píxeles superior izquierdo de la pantalla, y que los atributos de dicho bloque están almacenados en la dirección 0x5800, que especifica que los dos colores de ese grupo de píxeles son blanco y negro. El siguiente bloque de 8×8 píxeles está en las direcciones 0x4001, 0x4101, 0x4201, 0x4301, 0x4401, 0x4501, 0x4601 y 0x4701, y sus atributos, que indican que los dos colores mostrados serán celeste y rojo, están en la dirección 0x5801. Y así sucesivamente. Esta disposición puede parecer absurda, pero si nos fijamos, vemos que la dirección de memoria de un scanline de píxeles y la de los atributos que le corresponden tienen el mismo valor en los ocho bits inferiores. Gracias a esta característica, es posible leer los dos bytes necesarios para mostrar los ocho píxeles en sólo tres ciclos de reloj, en lugar de los cuatro que se necesitarían si ambas direcciones no tuviesen siempre un byte idéntico (lo que se denomina fast-page). Y si tenemos en cuenta que cada bloque de 8 píxeles tarda cuatro ciclos de reloj en ser pintado, salta a la vista de donde sale el ciclo de contención de memoria que vimos en el primer artículo: la circuitería «compacta» la lectura de dos grupos de 8 píxeles consecutivos, de manera que en lugar de bloquear al procesador durante tres ciclos y liberarlo uno, lo bloquea durante seis ciclos y lo libera durante dos consecutivos. Además, de esta manera se garantiza también que los siete bits bajos se recorren completos aproximadamente cada milisegundo, lo que es más que de sobra para garantizar el refresco de la RAM.

Obviamente este sistema se implementó porque permite abaratar y simplificar el hardware, pero tiene el inconveniente de que, a la hora de programar para él, es bastante engorroso calcular la dirección de memoria que se corresponde con cada coordenada. Así, si dividimos la pantalla en caracteres (bloques de 8×8 píxeles) y queremos encontrar las ocho direcciones de memoria de sus ocho bytes, la operación que hay que hacer es la siguiente (gráficamente):

En azul tenemos la coordenada X, que puede valer entre 0 y 31 para las 32 columnas del Spectrum. En verde y magenta tenemos la coordenada Y en líneas: en la parte verde estaría la coordenada Y en caracteres (de 0 a 23), y en magenta sería el scanline dentro de ese carácter, todo de arriba a abajo y de izquierda a derecha. A mayores es necesario poner los tres bits superiores a 010 para que apunte al bloque de memoria concreto. Como vemos, la cosa es bastante complicada y requiere rotaciones y máscaras. Sin embargo, gracias a las rutinas que vimos en las entradas anteriores esta complicación desaparece completamente. Si las utilizamos, la conversión es tan sencilla como:

Ponemos los tres bits superiores a 100 porque, para simplificar, colocamos el buffer en la dirección 0x8000 (32768). De esta manera, si ponemos la coordenada X en el byte inferior y la coordenada Y en la superior, sólo tendremos que poner a uno el bit 7 del byte inferior y ya tendremos la dirección de memoria del scanline superior del carácter con dichas coordenadas; para pasar al siguiente carácter sólo tenemos que sumar uno; para pasar al anterior, restar uno; para pasar al que está encima, restar 32, y para pasar al que está debajo, sumar 32. Tan simple como esto. ¿Y si tenemos una dirección de píxeles, cómo calculamos la de sus atributos? Pues sólo tenemos que hacer esto:

Sencillo ¿no? Aunque para los que no se quieran complicar, aquí está un trozo de código que lo hace:

; Asumimos que HL contiene la dirección de memoria
; de un byte de pantalla
    ld a, l
    and 0x1F
    ld l, a
    ld a, h
    rrca
    rrca
    rrca
    ld h, a
    and 0xE0
    or l
    ld l, a
    ld a, h
    and 3
    or 0x98
    ld h, a
; Ahora HL contiene la dirección de memoria del atributo
; que corresponde con el byte de pantalla inicial

Y como esta entrada quedó ya algo larga, seguiré en la siguiente.