Comienza en este número un nueva sección, dedicada a la programación en
ensamblador. Esta sección está pensada para que la gente que esté siguiendo el
curso de MH (ya sea en su versión HTML o escaneada) pueda ver ejemplos prácticos del
uso de este lenguaje. La temática de cada número podrá o no estar basada en otros
artículos de la revista, y el nivel también puede variar de un artículo a
otro (de hecho, esta semana comenzamos con un nivel bastante fuerte, porque la
rutina que comentamos tiene muchas optimizaciones). Espero sinceramente que os
agrade la sección, así que sin más preámbulos, vamos al lío.
El mes pasado 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.
COMPRESOR DE EJECUTABLES TAPC
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 |
INTRODUCCIÓN
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.
ANÁLISIS DE LA RUTINA DESCOMPRESORA DE TAPC
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.
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.
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.
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 |
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.
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.
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.
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.
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...
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.
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.
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.
Se suma a la distancia la posición actual de destino, obteniendo la posición
de origen de la copia en HL.
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
Se le indica al ensamblador TASM que estamos al final del archivo.
CONCLUSIONES
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.