Archivo por meses: abril 2021

Pintando en el Spectrum (16)

Programación, Retrocomputación, Trucos, tutoriales

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.

Pintando en el Spectrum (15)

Programación, Retrocomputación, Trucos

En la última entrada hablé del gestor de tareas. Sin embargo, desde entonces la cosa ha evolucionado mucho y el código actualmente es algo diferente. En concreto, es este:

old_stack:
    DEFW 0
task_pointer:
    DEFW 0

task_run:
    ld (old_stack), SP
    ld iy, task_list
task_loop:
    ld a, (iy+0)
    and a
    jr z, task_end
    ld l, (iy+1)
    ld h, (iy+2)
    ld sp, hl
    ld (task_pointer), iy
    ret
task_end:
    ld sp, (old_stack)
    ret
task_yield:
    ld iy, (task_pointer)
    ld hl, 0
    add hl, sp ; get the current stack
    ld (iy+1), l
    ld (iy+2), h
    ld e, (iy+0)
    ld d, 0
    add iy, de ; jump to next entry
    jp task_loop

task_list:
    TASK_ENTRY 36, task1
    TASK_ENTRY 10, task2
    TASK_ENTRY 14, task3
    DEFB 0 ; fin de la lista de tareas

El primer cambio es que ahora guardo el valor de IY, de manera que puede modificarse dentro de la tarea sin problemas. El segundo es que ahora, cada tarea puede tener un tamaño de pila diferente, lo que permite ahorrar mucha memoria, pues hay tareas que casi no hacen llamadas anidadas, mientras que otras sí.

El segundo cambio fue crear una macro que simplifica crear la tabla de tareas. Al final, en la etiqueta task_list, tengo una lista de tareas de ejemplo con un total de tres tasks, donde el código de la primera empieza en task1, el de la segunda en task2, y el de la tercera en task3, y sus stacks respectivos tienen un tamaño de 36, 10 y 14 bytes. TASK_ENTRY es una macro con el siguiente formato:

MACRO TASK_ENTRY, STACK_SIZE, TASK_FUNCTION
    DEFB STACK_SIZE+3
    DEFW $+STACK_SIZE
    DEFS STACK_SIZE-2
    DEFW TASK_FUNCTION
ENDM

El primer byte indica el tamaño completo de la entrada, que será de tres bytes más que el tamaño de pila que queremos asignar a esta task. Los dos siguientes bytes contienen el valor del registro SP de esta tarea, o sea, el actual puntero de pila. Se inicializa de manera que apunte al final del bloque reservado para la pila. Luego vienen tantos bytes como tamaño de pila queramos menos 2, de manera que reservamos los dos últimos bytes para poner la dirección de inicio de la tarea. De esta manera, cuando se crea la entrada para una tarea, la pila sólo contiene la dirección de inicio de dicha tarea, y el puntero de pila apunta justo a ella.

Por último, añadí una función optativa para depurar las tareas. Es ésta:

    ld hl, (task_pointer)
    inc hl
    inc hl
    inc hl ; jump over the size and the stored SP pointer
    ld d, 0
task_check_size:
    ld a, (hl)
    and a
    jr nz, task_end_check_size
    inc d
    inc hl
    jr task_check_size
task_end_check_size:
    ld a, d
    ld SP, (old_stack)
    call do_debug

Este bloque se puede ejecutar justo después de que una tarea haya vuelto (llamando a task_yield), y lo que hace es comprobar cuanto espacio se ha llegado a ocupar en la pila. Para ello se basa en que el bloque de la pila se inicializó a cero, y que cuando se saca un valor de la pila sólo se incrementa SP, pero el valor sigue estando ahí. De esta manera, si vemos cuantos bytes seguidos cuyo valor sea cero hay desde el principio, sabremos hasta donde ha llegado a crecer la pila. Si este tamaño es cero significa que esa pila se ha llenado del todo en algún momento (y hasta es posible que haya sobreescrito alguna posición extra), por lo que en ese caso hay que aumentar el tamaño.

La llamada a CALL do_debug se supone que muestra, de alguna manera, el contenido del registro A.

Qué pinta tiene

Pues el juego ya lo he terminado y ahora mismo estoy puliendo los textos y la traducción al inglés, y los petatesters están buscando los bugs y pifias varias. Pero tiene esta pinta: