Compresión de ejecutables con TAPC

Este año 2003, Antonio Villena nos ofreció su primera versión del programa compresor de ejecutables TAPC. En este artículo nos habla sobre la técnica de compresión que ha utilizado.

La compresión es una técnica que basa su éxito en eliminar la redundancia de los datos. Por tanto, la existencia de redundancia es una condición necesaria para que se pueda aplicar la técnica. En la práctica eso no supone ningún impedimento ya que la redundancia abunda en todo tipo de datos y de forma natural. En un texto las palabras se suelen repetir, en una melodía se repiten los patrones sonoros, en un gráfico dos líneas contiguas son muy similares si las comparamos.

En este caso el objetivo es comprimir un juego de Spectrum, entre cuyos datos se encuentran instrucciones código máquina del Z80. Pues bien, incluso este tipo de datos también posee una redundancia que es posible eliminar. El estilo de programar, la abusiva utilización de instrucciones útiles frente al escaso empleo de otras más rebuscadas, incluso la mera lógica de poner un salto condicional después de una comparación, etc… dotan de la suficiente redundancia a un fragmento de código máquina Z80.

Afortunadamente un juego de Spectrum contiene muchos más tipos de datos: sprites, melodías, tablas, niveles… que son más redundantes que los anteriores, por tanto en general se pueden comprimir mejor.

Ahora llega la hora de comprimir; hay bastantes algoritmos de compresión así que tendremos que elegir uno. Aunque el cerco se estrecha si nos limitamos a la escasa potencia computacional de una CPU tipo CISC de 3.5MHz. Y lo peor de todo es que no disponemos de RAM extra; los juegos normalmente ocupan toda la RAM disponible, por lo que no tendremos espacio para meter tablas ni datos intermedios. Así que el único candidato que queda es una variante de Lempel-Ziv.

Los algoritmos de Lempel-Ziv buscan la redundancia mirando hacia atrás sobre el propio fichero que se está comprimiendo, para ver si hay un patrón que se encuentre repetido y, en lugar de codificar ese patrón, codificar su posición y su longitud. Si intentamos comprimir esta frase “hola, esto mola”, cuando el algoritmo esté comprimiendo y vaya por la letra “m”, se dará cuenta que el siguiente patrón “ola” ocupa tres bytes; sin embargo si somos capaces de codificar en menos de tres bytes, que existe una cadena de longitud 3, en una posición de 11 letras hacia atrás, el decodificador tendrá los suficientes datos como para reconstruir el mensaje inicial y se habrá eliminado la redundancia que existía.

La cuestión está en el “cómo” se codifican estos datos a nivel bit; es obvio que habrá que hacerlo de forma que se utilicen los menos bits posibles, e incluso se pueden usar ciertas ideas y trucos siempre y cuando se demuestre su efectividad.

Lo primero es diferenciar entre los “bytes” que no se pueden comprimir por no haber encontrado una cadena lo suficientemente larga. Para ello se empezará leyendo un bit: si este bit es cero significa que lo que viene después es un byte en bruto, que no ha podido comprimirse. Esta es la parte mala, hemos codificado con 9 bits un dato de 8, así que si todos los datos fueran así lo que hemos hecho es expandir con un factor de 9/8. Gracias a Dios esto sólo ocurre en archivos de naturaleza aleatoria, o datos ya comprimidos, circunstancias que en ningún caso se darán en un juego de Spectrum.

Para codificar otra cosa que no sean datos en bruto hay que tener en cuenta que para ganar en rendimiento es necesario codificar los acontecimientos más frecuentes con menos bits, y viceversa. Más o menos la idea es la misma que el algoritmo de Huffman, algoritmo que hemos descartado por emplear tablas que necesitan de memoria adicional. Pues bien, como el patrón que más se repite es el “byte bruto” que ya hemos visto antes, a este le damos la mínima longitud, o sea 1 bit, y le asignamos el bit 0. Para el resto habrá que ingeniárselas buscando un árbol que sea fácil de implementar en código y se ajuste a las frecuencias de aparición.

Los otros patrones son “10”, “110”, “1110”, “11110”, y “11111”. El secreto de su sencillez es que solo hay que contar el número de unos hasta ver un cero, o si contamos 5 parar. Esta feliz idea me ha permitido realizar un descompresor de 122 bytes.

Empezamos por el primer patrón “10”. Se trata de una ocurrencia genérica, puede tener cualquier longitud (con un límite de 256) y la posición hacia atrás máxima es de 65536 bytes. Se supone que es el segundo patrón más frecuente y es la idea original de algoritmo Lempel-Ziv puro. Lo siguiente que viene es la longitud, pero tampoco ésta tiene un tamaño fijo, sino variable. Lo que hacemos es leer los bits de dos en dos, siendo el primero el bit de información y el segundo sólo nos indica si debemos seguir leyendo o parar. Esta es la técnica conocida como “codificación gamma”. Lo más óptimo para esto es partir de un registro iniciado a 1, e ir metiendo los bits que vayamos leyendo por la derecha, desplazando el resto hacia la izquierda. Un ejemplo sencillo, “01110110”. Empezamos con el registro iniciado a “00000001”, leemos de la fuente “01”, o sea metemos un 0 y seguimos “00000010”. Ahora leemos “11”, metemos un 1 y continuamos “00000101”. Luego “01” dejará el registro en el valor “00001010” y proseguiremos hasta el último “10”, haciendo un último desplazamiento “00010101” y el cero nos indica que ya hemos acabado. En decimal el valor leído es de 21.

Este subalgoritmo es importante, tiene la característica de codificar números bajos con muchos menos bits que números más altos. Su uso lo justifica el hecho de que las ocurrencias más cortas son las más frecuentes. Es raro encontrar una cadena repetida de longitud 256, sin embargo las de longitud 2 son muy abundantes. Otra cosa útil de esta función es que el mínimo valor que se obtiene es 2, que coincide con la longitud mínima de una ocurrencia de este estilo.

Después de la longitud se debe decodificar la posición. En este caso el esquema es una muestra entre longitud fija y longitud variable. También se basa en un principio teórico que dice más o menos que los datos redundantes suelen estar localizados en zonas próximas entre sí. O sea que valores más bajos “de posiciones hacia atrás” serán más frecuentes y dignos de ser codificados en menos bits. Pero en este caso los márgenes que manejamos son mayores y si no queremos perjudicar en exceso a ocurrencias lejanas necesitamos combinarlo con una parte fija de 8 bits. La posición será un registro de 16 bits, cuyos 8 bits de mayor peso se obtendrán con la misma función de antes (pero restándole 2), y los ocho de menor peso tendrán una longitud fija de 8 bits.

En realidad a efectos prácticos la mitad superior de la longitud viene antes que la posición, porque resultaba conveniente para optimizar aún más la rutina descompresora.

Para acabar con el patrón “10” pongo el siguiente ejemplo: “1011100111111000011000”, primero delimitamos campos: “10”, “1110”, “01111110”, “00011000”. El primero delimita el patrón, que es del tipo que acabo de explicar; ahora viene la parte alta de la posición “1110” que se traduce en “1 11”, o sea siete pero que al restarle 2 se me queda en 5. El tercero es la longitud, que en este caso es de “1 0111” es decir empiezo con uno y leo los bits impares. Se corresponde con una longitud de 23. Acabando con la parte baja de la posición tendremos un 18h (la h por lo de hexadecimal), teniendo en total un registro de posición de 0518h ó 1304. O sea que el decodificador debe poner a continuación la misma cadena que se escribió 1304 bytes hacia atrás con una longitud de 23 bytes.

El siguiente patrón es el “110”. La funcionalidad se escapa un poco al algoritmo Lempel-Ziv aunque permite introducir bytes en bruto utilizando 7 bits en lugar de los nueve del patrón “0”. Después de este patrón leemos una longitud fija de 4 bits; en total hemos leído 7 bits “100XXXX”. Estos cuatro bits forman un valor desde 0 hasta 15. En caso de ser 0, nos indican que debemos escribir el byte más frecuente que existe, o sea el propio 0. Las zonas vacías de memoria tienen este valor, al iniciar registros, etc… El usar 7 bits para codificar un cero y 9 bits para los 255 símbolos restantes repercute positivamente en cuanto a compresión. Si no me creéis coged cualquier editor hexadecimal y abrid cualquier archivo, contáis el numero de ceros y lo dividís entre la longitud del archivo. Si este valor excede con creces al valor 1/256 me daréis la razón. Prosiguiendo, en caso de no ser cero, tendremos un valor de 1 a 15 que nos indicará cuantas posiciones debemos retroceder hasta encontrar el byte que buscamos. Como ejemplo tenemos la siguiente cadena: “tenemos la siguiente caden”, en este caso codificamos con un 4, ya que 4 posiciones hacia atrás hay una “a” y será más corto hacer esto que usando el patrón “0” y luego 8 bits. Con esto ahorramos 2 bits.

Los dos siguientes patrones son “1110” y “11110” que voy a explicar a la vez porque su funcionalidad es muy parecida. Se trata de ocurrencias de longitud 2 y 3 respectivamente (2 para “1110” y 3 para “11110”) pero cuya posición no excede los 128 bytes hacia atrás. Así se podrá codificar con un número fijo de bits, en particular 7. Sumando tenemos una longitud total de 11 para el patrón “1110” y de 12 para el patrón “11110”. Por poner un ejemplo aunque seguro que no hace falta si leemos “111101010101”, lo separamos en “11110”,“1010101” que quiere decir “una cadena de longitud 3 con posición 85”.

El último patrón que queda por explicar es el “11111”. Se trata de una ocurrencia en la que sólo codificamos la longitud, ya que la posición es la misma que la que tuvo la inmediatamente anterior. La longitud, que es lo único que viene después, mantiene idéntico formato a la del tipo “10”. El porqué esto funciona es fácil de comprender con un ejemplo. Imagínad un gráfico en el cual dos líneas consecutivas solo difieran en un byte. Entonces la primera línea se codificará usando muchos patrones tipo “0”, hasta empezar con la línea siguiente. Aquí encontraremos una ocurrencia de longitud X y posición 256 (el ancho de la línea), después codificaremos con tipo “0” ó “110” el byte que difiera, y por último encontraremos otra cadena de longitud 255-X y posición 256. Como ves el hecho de encontrar dos ocurrencias consecutivas con la misma posición es más normal de lo que cabría pensar, y justifica la implementación de este patrón.

Por último, y también es importante, tiene que haber una forma de parar el descompresor para ejecutar el código. Esto se podría hacer comparando cada vez que leemos si hemos superado una determinada posición, pero también podemos usar otro patrón, el “000000000” para indicar el EOF (End of File). Claro que si empiezo leyendo un “0”, ¿no lo confundiré con un patrón del tipo “0”? (byte en bruto). Pues no, porque como recordaréis el byte 0 es tan frecuente que se codifica con 7 bits en lugar de nueve, exactamente con la cadena “1100000”, así que no habrá confusiones.

Ya adquirida toda la base teórica estamos listos, suponiendo unos mínimos conocimientos de ensamblador Z80, para entender el código del descompresor.

Antonio Villena

La rutina que vamos a ver en este número se encuentra aquí, en el directorio Z80, bajo el nombre “PRU.ASM”. Como comprobaréis los pocos comentarios que hay no son demasiado explicativos, así que vamos a dedicar este artículo a destripar su funcionamiento al completo. El fundamento teórico de la compresión lo tenéis en el artículo anterior, y es necesario que lo leáis y comprendáis si queréis entender bien lo que se os avecina.

La primera rutina que voy a explicar es LEEB, que se encarga de leer los bits uno a uno conforme vamos avanzando al descomprimir los datos. Dicha rutina es la siguiente:

DORA 	DEC 	IX
  	DEFB 	$30
LEEB 	AND 	A
  	RL 	(IX)
  	JR 	Z, DORA
  	RET

El punto de entrada está en LEEB, así que de momento olvidaos de las dos primeras instrucciones.

Lo primero que nos encontramos es un AND A, instrucción que nos sirve para borrar el flag de acarreo (Carry).

En la siguiente instrucción rotamos hacia la izquierda el contenido de memoria al que apunta IX, que es donde están los bits que queremos leer. El bit leido pasa al Carry, y al mismo tiempo el contenido antiguo del carry (en este caso un 0), pasa al bit menos significativo de (IX), es decir, que entra un 0 por la derecha.

¿Que sucede cuando hemos extraido los 8 bits del byte al que apunta IX? Que hemos metido 8 bits 0 por la derecha, con lo que el resultado de la operación es 0, se activa el flag Z y saltamos a DORA en la siguiente instrucción.

Si no estamos extrayendo el octavo bit, el salto no se produce y retornamos de la rutina con el RET, y la información del bit recién extraido está en el flag Carry.

En DORA decrementamos el puntero IX para que apunte al siguiente byte (decrementamos porque el archivo está comprimido hacia detrás).

La siguiente instrucción resulta que no es una instrucción completa, sino sólo media, por eso está escrita en forma de dato, de forma que ese dato junto con la siguiente instrucción (el AND A) forman la instrucción completa. El código 30h = 48 decimal es el primer byte de JR NC, desp . Sabemos seguro que el Carry está a uno (ya que el último bit que sale antes de que el byte pase a valer 0 tiene que ser un uno seguro), así que no se provocará ningún salto y logramos pasar directamente al RL (IX) sin que llegue a ejecutarse la instrucción AND A (que se usó como distancia de salto de la instrucción JR).

Al volver a ejecutar RL (IX), leemos el primer bit del siguiente byte, de nuevo en el indicador de acarreo, pero en esta ocasión introducimos un 1 por la derecha. Este uno no es un dato, sino el “bit marcador” (marker bit), que indicará el final del byte cuando hayamos leido otra vez 8 bits y toque pasar al siguiente. Si os dais cuenta, el último bit que se sacará de cada byte siempre será el marker bit. Esta técnica es importante porque permite prescindir de contadores que habrían sido necesarios para controlar la lectura de 8 en 8 bits si no la hubiesemos utilizado. La segunda vez que pasemos por el salto condicional JR Z, DORA sabemos seguro que el salto no va a producirse, porque aunque los datos del siguiente byte fueran todo ceros, el bit-marker asegura que hasta que no hagamos otras 8 lecturas, el contenido de (IX) no volverá a valer 0. Por lo tanto, retornamos en el RET y listos.

Vayamos con la siguiente subrutina, que se usa para leer un número fijo de bits:

LOLO 	CALL 	LEEB
  	RL 	C
  	JR 	NC, LOLO
  	LD 	L, C
  	RET

En la primera instrucción leemos un bit, bit que introducimos en el registro C por la derecha, al realizar la rotación a la izquierda. Este proceso lo repetimos hasta que sale un bit 1 por la izquierda. Ese bit que sale por la izquierda no es un dato, sino otro marker-bit, que a la entrada de la rutina sirve para indicar cuantos bits queremos leer. Por ejemplo, para C=00000001b, se leerán un total de 8 bits, mientras que para C=00010000b tan sólo se leerán 4.

Cuando se hayan leido los bits necesarios, el contenido de C se copia en el registro L, y regresamos.

Por último vamos a ver la subrutina que lee un número variable de bits codificados con la técnica de gamma encoding:

DOND 	INC 	B
DONE 	CALL 	LEEB
  	RL 	B
  	CALL 	LEEB
  	JR 	C, DONE
  	RET

A esta rutina se entra por DONE con B=1, o bien por DOND cuando tenemos B=0, ya que necesitamos un 1, pues los códigos variables que usamos tienen al menos el primer bit a 1.

Nada más comenzar leemos un bit y lo colocamos en B (como siempre, haciendo que entre por la derecha), y a continuación leemos el siguiente pero su valor no lo almacenamos sino que lo usamos para ver si queremos seguir leyendo. En el momento en que tengamos un bit a 0, salimos de la subrutina.

Ahora ya estamos listos para comenzar a examinar la rutina descompresora desde el principio:

#define 	DEFB 	.BYTE
#define 	DEFW 	.WORD
#define 	EQU 	.EQU

Estas son pseudo-instrucciones del ensamblador TASM, que es el que ha utilizado Antonio en su código. Se pueden desechar si usamos otro ensamblador.

  	.ORG 	$5D01
  	LD 	IX, 0000
  	LD 	DE, 0000

El valor que se carga en IX no es en realidad 0, sino que el compresor sitúa en ese espacio el comienzo de la zona comprimida+1, ya que IX es de donde se leen los bits uno a uno. En el primer byte que se lee de (IX) almacena el valor 128, por lo que solo contiene un bit marcador y el primer bit que devuelve LEEB es por tanto ya de la zona comprimida. Igualmente, el compresor coloca en DE el comienzo de la zona donde vamos a descomprimir los datos. Al decir comienzo, hemos de recordar que la descompresión la realizamos hacia atrás, así que el valor inicial de DE estará por el final de la memoria y el de IX dependerá del nivel de compresión alcanzado con cada archivo en concreto.

  	LD 	B, C

Esta instrucción carga en B el valor 1. Si nos fijamos en el bloque anterior la rutina comienza en 5D01, y al invocarla con USR, BC almacena el valor de la dirección de ejecución.

El valor 1 para B es necesario para el caso del patrón 0, que es el primero que se ejecuta, sin necesidad de decodificar el campo de patrón. Esto es así porque no tiene sentido esperar que se repita ningún dato antes de que existan dichos datos. El único cuidado que hay que tener es que el primer dato que se extrae no sea 0, porque para el patrón 0, el dato 00000000 significa el final del archivo. El compresor se encarga de que esto no suceda, añadiendo un dato basura distinto de 0 si fuera necesario.

REOT 	CALL 	LOLO
  	JP 	Z, $0000
LI00 	LD 	A, C

Aquí entramos ya sea la primera vez desde arriba o bien más tarde desde abajo hasta la etiqueta REOT, con B=1 y C=1. El hecho de que C sea 1 sirve para que la llamada a LOLO lea un byte completo (el dato sin comprimir). Si el dato leido fuera un 0, hemos alcanzado el final de la compresión, y saltamos a la dirección de ejecución del programa descomprimido (de nuevo, este campo no es 0, sino que será rellenado convenientemente por el programa compresor).

En A metemos el dato que hemos leido ahora mismo, que será el siguiente en ser colocado en su sitio. Si venimos desde abajo entrando por LI00, estaremos introduciendo un 0 proviniente del subcaso 0000 del patrón 110.

Sigamos…

RAVE 	LD 	(DE), A
  	DEC 	HL
  	DEC 	DE
  	DJNZ 	RDAD

A RAVE llegamos con el siguiente byte que tenemos que escribir en el registro A, y con el número de bytes que quedan por copiar de una zona de memoria en el registro B. Si no estamos copiando de una zona de memoria, B valdrá 1 y no buscará por lo tanto nuevos bytes. En caso de que nos queden bytes por copiar, se saltará a RDAD para tomar el siguiente byte antes de volver a RAVE.

Justo aquí acabamos de procesar un código LZ y vamos a comenzar a leer el siguiente en este código:

BUKX 	LD 	H, B
  	LD 	BC, $0501
RENU 	CALL 	LEEB
  	JR 	NC, REXU
  	DJNZ 	RENU

Sabemos que B vale 0 porque venimos de un DJNZ, así que la primera instrucción pone a 0 el registro H.

En la siguiente instrucción de este bloque metemos un 5 en B, que hará de contador, y en C aprovechamos para renovar el bit marcador para un uso futuro.

Ahora comenzamos a leer bits, y en cuanto encontramos un bit a 0 significará que ya tenemos nuestro patrón. Si leemos 5 bits y aún no hemos encontrado el patrón, es que hemos leido el patrón 11111, por lo que seguimos adelante. Si lo encontramos antes, salimos hacia la etiqueta REXU, con un valor en B que depende del patrón que hemos encontrado, teniendo los valores B=5, 4, 3, 2 ó 1 para los patrones 0,10,110,1110 ó 11110 respectivamente.

  	LD 	HL, RUTA+1
  	PUSH 	HL

Aquí estamos en el caso del patrón 11111. Recordemos que para este patrón necesitamos leer la longitud de copia, que tiene un número variable de bits. Para ello podríamos llamar a la subrutina decodificadora gamma que vimos anteriormente, entrando por DOND, pero el caso es que luego nos interesa dar un salto a otra posición, por lo que en lugar de hacer CALL DOND, JR RUTA+1 lo que hacemos es guardar en la pila la dirección a donde queremos saltar, que quedará como un retorno ficticio cuando ejecutemos el siguiente RET, y colocamos la subrutina gamma justo a continuación:

DOND 	INC 	B
DONE 	CALL 	LEEB
  	RL 	B
  	CALL 	LEEB
  	JR 	C, DONE
  	RET

Ésta ya la hemos visto y no requiere más comentarios.

Ahora dejemos el patrón 11111 para más adelante (cuando alcancemos la etiqueta RUTA), y veamos lo que pasa si el patrón era cualquier otro.

REXU 	LD 	A, B
  	SUB 	3

Al restar 3 al número de patrón que estaba en B, se obtienen los siguientes casos (NZ quiere decir flag Zero = 0, Z flag Zero = 1, y lo mismo para el carry):

patrón 0: A = 2 , NC , NZ
patrón 10: A = 1 , NC , NZ
patrón 110: A = 0 , NC , Z
patrón 1110: A = -1 , C , NZ
patrón 11110: A = -2 , C , NZ

  	JR 	NZ, NLTR

Si no estamos en el patrón 110, saltamos a probar los siguientes

  	LD 	BC, ALAE
  	PUSH 	BC
  	LD 	BC, $0110

Al igual que en el caso anterior, introducimos una dirección de retorno en la pila y el bit marcador del registro C lo introducimos en esta ocasión en el bit 4 del byte -los bits se numeran del 7 (más significativo) al 0 (menos significativo)-, con lo que en la siguiente rutina leemos 4 bits (tal y como requiere el patrón).

LOLO 	CALL 	LEEB
  	RL 	C
  	JR 	NC, LOLO
  	LD 	L, C
  	RET

Esta rutina también la hemos visto, y pasemos ahora a los patrones que no hemos tocado aún, es decir, todos menos el 11111 y el 110.

NLTR 	JR 	NC, LE23

Si no hay carry estamos en los casos 0 o 10, saltamos a otro sitio para procesarlos.

  	CPL 	 
  	LD 	B, A
  	INC 	C
  	JR 	KXKX

Este código se ejecuta para los patrones 1110 y 11110. Ambos casos son muy parecidos, tan sólo se diferencian en las distancias (2 y 3 respectivamente), por lo que comparten el mismo código sin necesidad de seguir bifurcando.

La primera instrucción CPL es equivalente a XOR 255. Cambia todos los bits del acumulador, obteniendose A=0 para el patrón 1110 y A=1 para el patrón 11110. Este valor se copia a B en la siguiente instrucción.

A continuación INC C pasa el valor de 1 a 2, con lo que el marker bit se mueve un lugar y solo se leerán 7 bits fijos en lugar de 8 para la distancia.

Por último saltamos a otra zona del código, por lo que, al igual que con los patrones vistos anteriormente: continuará…

Retomamos aquí el caso de los patrones 0 y 10, en ese caso tras restar 3 el valor de A para estos casos era 2 y 1 respectivamente.

LE23 	LD 	B, A
  	DJNZ 	REOT

Primero copiamos el valor de A en B, para a continuación hacer la última bifurcación usando la instrucción DJNZ.

Para el patrón 0, al decrementar B, está toma el valor 1, y salta a la etiqueta REOT, que está arriba del todo y ya hemos visto. Recordemos que el valor de C que fue renovado entre las etiquetas BUKX y RENO, es 1, y no ha sido tocado, por lo que todo va como debería.

Para el caso 10, seguimos ejecutando código…

  	CALL 	DOND
  	DEC 	B
  	DEC 	B
  	LD 	H, B
  	LD 	B, A
  	CALL 	DONE

La primera llamada a la subrutina gamma, lee la parte alta de la distancia, le resta 2 y la guarda en H. A continuación, vuelve a fijar el registro B a 1 (A conservaba ese valor desde la resta de 3 al interpretar el patrón), y llamamos de nuevo a la subrutina para leer la longitud que se va a copiar, longitud que quedará guardada en B.

KXKX 	CALL 	LOLO

En esta etiqueta nos encontramos con el salto que se ejecutaba para los patrones 1110 y 11110, por lo que esta llamada a LOLO (la subrutina que lee un número fijo de bits), lee 8 bits para el patrón 10 y 7 bits para los otros 2 casos. Tras este salto, para los 3 patrones tenemos la distancia de la zona que queremos copiar en HL, porque en LOLO se copia el resultado en L, y para el patrón 10 acabamos de guardar la parte alta en H, cuyo valor lo habíamos puesto a 0 anteriormente, y sigue valiendo 0 para los otros dos patrones que consideramos hasta ahora.

  	POP 	AF

Este código se usa para desechar la distancia del caso anterior, que se guarda en la pila. La primera vez el valor desechado es el de retorno al BASIC, pero nos da igual porque no vamos a retornar a él de todas formas.

  	XOR 	A
  	CP 	H
  	JR 	NZ, RUTA
  	BIT 	7, L
  	JR 	NZ, RUTA
  	INC 	B
  	INC 	B
RUTA

Este trozo de código es algo complicado. Básicamente, comprueba si la distancia total es menor de 128, y si es así le sumamos 2 a la longitud de la coincidencia. Con esto logramos por una parte, ajustar el valor de B en los patrones 1110 y 11110 (recordemos que B valía 0 y 1 respectivamente), y por otra parte, para el patrón 10 logramos que la longitud mínima cuando la distancia es pequeña sea de 4 (ya que si tuvieramos 2 o 3 habríamos usado los patrones 1110 ó 11110). Para lograr esto, ponemos el valor de A a 0 (mediante la instrucción XOR A), y lo comparamos con H. Si no coinciden, es que la distancia es grande y no hace falta incrementar. Si coinciden, miramos el valor del bit 7 (el más significativo) de L, con una instrucción de bit. Si está activo significa que L > 128, entonces no se activa el flag Z, por lo que se produce el salto y tampoco se incrementa la longitud.

Sigamos…

RUTA 	OR 	225

Si entramos mediante RUTA+1 (que es la dirección de retorno que pusimos en la pila para el patrón 11111), la instrucción que se ejecuta es 225 = POP HL. Con esto recuperamos la distancia anterior de la pila, en lugar de desecharla como hicimos con los patrones que estabamos viendo hasta ahora en el POP AF de arriba. Desde más arriba, lo que conseguimos con la instrucción OR es poner el flag Z a 0, lo cual asegura que no se producirá salto condicional que aparece un poco más abajo.

  	PUSH 	HL

Con esto guardamos la distancia para el próximo patrón. Esta distancia podrá ser la que acabamos de sacar o una que acabemos de calcular, y en la próxima iteración podrá ser ignorada, desechada o recuparada.

ALAE 	JR 	Z, LI00

Aquí entra el último patrón que teníamos por ahí perdido: el 110. Este patrón acababa de leer 4 bits, y si resultan ser todos 0 es un byte 0 que tiene que meter, por lo que salta por arriba del todo. En el patrón 11111 este salto no se producirá seguro porque viene de leer la longitud, que es distinta de cero, y los demás patrones acaban de ejecutar la instrucción OR 255, por lo que tampoco saltarán.

Llegados a este punto, es que hemos comenzado un proceso de copia de bytes anteriores. En este momento tenemos en HL la distancia que separa la posición actual de la que queremos comenzar a copiar, y en B tenemos el número de bytes que se van a copiar.

  	ADD 	HL, DE

Se suma a la distancia la posición actual de destino, obteniendo la posición de origen de la copia en HL.

RDAD 	LD 	A, (HL)
  	JR 	RAVE

Se coge un byte y se va a RAVE a colocarlo. Esto se repetirá hasta que B sea 0 y se comienze por lo tanto a decodificar un nuevo patrón.

Por último viene la rutina de leer bits, que fue la primera en ser comentada.

DORA 	DEC 	IX
  	DEFB 	$30
LEEB 	AND 	A
  	RL 	(IX)
  	JR 	Z, DORA
  	RET

Y eso es todo. Con

  	.END

Se le indica al ensamblador TASM que estamos al final del archivo.

Acabamos de revisar una obra maestra de la optimización en tamaño. Tal vez sea posible ahorrar algún byte extra por algún lado, pero en ese caso os aseguro que no sería nada fácil encontrar dónde. La optimización no sólo se basa en las distintas técnicas (como el bit marcador) y trucos (como los datos de una instrucción que constituyen otra instrucción en si misma, o el guardar una dirección de retorno falsa en la pila) que hemos visto, sino sobre todo en la reutilización de código (los distintos patrones comparten partes del código, en lugar de tener cada uno su apartado), y en el control y la sabia utilización de los registros, que han permitido implementar la descompresión sin necesidad de usar ninguna variable extra aparte de los registros normales y la pila.

Es de esperar que en los próximos artículos los programas analizados sean algo más simples, y no incidiremos tanto en la optimización de espacio, sino algo más en la de velocidad, o en un equilibrio entre ambos aspectos, ya que en un ordenador como el Spectrum tanto memoria como velocidad escasean, y la velocidad suele ser el factor determinante que permita o no realizar una tarea crítica a tiempo para conseguir un movimiento suave y sin parpadeos, por ejemplo.

Nos vemos próximamente.