CÁLCULO DE DIRECCIONES DE PANTALLA A PARTIR DE COORDENADAS
Cuando tenemos la coordenada de cualquier sprite almacenada en registros
o variables, necesitaremos saber donde hay que empezar a ponerlo cuando
vayamos a pintarlo. Esto, dada la extraña disposición de la memoria de la
pantalla en el Spectrum, no es tan sencillo como pueda serlo en otros
sistemas (por ejemplo en el modo VGA 13h del PC, donde el cálculo consiste
en hacer (320*y)+x ). Así pues, vamos a dedicar este artículo a ver
varias formas distintas de realizar esta tarea, comentando sus
ventajas e inconvenientes.
Para poder comprender las distintas rutinas hay que tener muy en cuenta
la disposición de la memoria de video, así que vamos a recordarla por si
a alguien se le ha olvidado.
Básicamente, el aparente caos que supone el orden de la pantalla se entiende una vez
que se descomponen las direcciones en campos de bits bien diferenciados:
| byte alto |
byte bajo |
| 010 tt yyy |
YYY XXXXX |
| tt |
tercio de la pantalla, de 00 a 10 |
| YYY |
fila dentro del tercio (en caracteres) |
| yyy |
fila dentro del caracter (en pixels) |
| XXXXX |
columna (en caracteres) |
Los datos de los que partimos son un byte con la coordenada Y en
el formato: ttYYYyyy , y otro byte para la coordenada X en el formato:
000XXXXX.
Así pues nuestro cometido principal consiste en reordenar todos los campos
de la coordenada Y al insertarlos en la dirección, para terminar añadiendo
al resultado la coordenada X, lo cual es bastante trivial.
Para realizar el calculo de la coordenada Y tenemos dos posibilidades
básicas: hacer todo el cálculo por nuestra cuenta, o usar una tabla que
almacene todos los resultados. También tenemos la opción intermedia de
usar las tablas sólo para la parte mas compleja y calcular el resto.
Realizando el cálculo, la primera rutina que se me ocurrió fue ésta:
; entrada x=L, y=A; salida en DE
CALC1: LD D,2 ; D = 00000010 2 / 7 2 / 7
RLCA ; A = tYYYyyyt 1 / 4 3 / 11
RL D ; D = 0000010t 2 / 8 5 / 19
RLCA ; A = YYYyyytt 1 / 4 6 / 23
RL D ; D = 000010tt 2 / 8 8 / 31
PUSH AF ; 1 /11 9 / 42
AND 224 ; A = YYY00000 2 / 7 11 / 49
ADD A,L ; A = YYYXXXXX 1 / 4 12 / 53
LD E,A ; E = YYY00000 1 / 4 13 / 57
POP AF ; A = YYYyyytt 1 /11 14 / 68
RLCA ; A = YYyyyttY 1 / 4 15 / 72
RLCA ; A = YyyyttYY 1 / 4 16 / 76
RLCA ; A = yyyttYYY 1 / 4 17 / 80
RLCA ; A = yyttYYYy 1 / 4 18 / 84
RL D ; D = 00010tty 2 / 8 20 / 92
RLCA ; A = yttYYYyy 1 / 4 21 / 96
RL D ; D = 0010ttyy 2 / 8 23 / 104
RLCA ; A = ttYYYyyy 1 / 4 24 / 108
RL D ; D = 010ttyyy 2 / 8 26 / 116
RET ; 1 /10 27 / 126
|
En los comentarios podeis ver el resultado de la última
operación (para que se entienda lo que va haciendo el programa), los
bytes y estados de la instrucción actual y por último la suma de bytes /
estados hasta el momento. En los siguientes listados prescindiré de algunos
de estos campos.
En total esta primera rutina ocupa 27 bytes, y tarda 126 estados en
realizar el cálculo.
¿Es mucho, es poco? Veamos si podemos mejorarla.
Si nos damos cuenta, existen algunas instrucciones que se repiten, por
lo que podemos ahorrar algunos bytes haciendo:
; entrada x=L, y=A; salida en DE
CALC2: LD D,74 ; 2 / 7 2 / 7
ROT1: RLCA ; 1 / 4,4 3 / 15
RL D ; 2 / 8,8 5 / 31
JR NC, ROT1 ; 2 / 12,7 7 / 50
PUSH AF ; 1 / 11 8 / 61
AND 224 ; 2 / 7 10 / 68
ADD A,L ; 1 / 4 11 / 72
LD E,A ; 1 / 4 12 / 76
POP AF ; 1 / 11 13 / 87
RLCA ; 1 / 4 14 / 91
RLCA ; 1 / 4 15 / 95
RLCA ; 1 / 4 16 / 99
ROT2: RLCA ; 1 / 4,4,4 17 / 111
RL D ; 2 / 8,8,8 19 / 135
JR NC, ROT2 ; 2 / 12,12,7 21 / 166
RET ; 1 / 10 22 / 176
|
Como podéis observar, el algoritmo es identico al caso anterior,
pero hemos introducido un par de bits extra en el registro D que
actúan de bits marcadores (los bit markers que vimos en el artículo anterior)
para salir de los bucles.
A cambio de ahorrar 5 bytes, estamos tardando 50 estados más en realizar
el cálculo.
Si nos fijamos en la primera rutina, vemos que estamos haciendo una
tontería con el campo yyy, ya que estamos rotando el byte 8 veces, para
que el campo vuelva otra vez al mismo sitio al final. Además, el uso de
instrucciones PUSH AF y POP AF resulta costoso en estados, así que podemos
refinar la rutina un poquito:
; entrada x=L, y=D; salida en HL
CALC3: LD A,D ; A = ttYYYyyy 1 / 4 1 / 4
LD H,2 ; H = 00000010 2 / 7 3 / 11
RLCA ; A = tYYYyyyt 1 / 4 4 / 15
RL H ; H = 0000010t 2 / 8 6 / 23
RLCA ; A = YYYyyytt 1 / 4 7 / 27
RL H ; H = 000010tt 2 / 8 9 / 35
AND 224 ; A = YYY00000 2 / 7 11 / 42
ADD A,L ; A = YYYXXXXX 1 / 4 12 / 46
LD L,A ; L = YYYXXXXX 1 / 4 13 / 50
LD A,D ; A = ttYYYyyy 1 / 4 14 / 54
AND 7 ; A = 00000yyy 2 / 7 16 / 61
RLC H ; D = 00010tt0 2 / 8 18 / 69
RLC H ; D = 0010tt00 2 / 8 20 / 77
RLC H ; D = 010tt000 2 / 8 22 / 85
ADD A,H ; A = 010ttyyy 1 / 4 23 / 89
LD H,A ; H = 010ttyyy 1 / 4 24 / 93
RET ; 1 /10 25 / 103
|
Ahora ocupa 25 bytes, y tarda sólo 103 estados en realizar el cálculo.
Haciendo lo mismo de antes, la versión pequeña saldría así:
; entrada x=L, y=D; salida en HL
CALC4: LD A,D ; 1 / 4 1 / 4
LD H,74 ; 2 / 7 3 / 11
ROT1: RLCA ; 1 / 4,4 4 / 19
RL H ; 2 / 8,8 6 / 35
JR NC,ROT1 ; 2 / 12,7 8 / 54
AND 224 ; 2 / 7 10 / 61
ADD A,L ; 1 / 4 11 / 65
LD L,A ; 1 / 4 12 / 69
LD A,D ; 1 / 4 13 / 73
AND 7 ; 2 / 7 15 / 80
ROT2: RLC H ; 2 / 8,8,8 17 / 104
JR NC,ROT2 ; 2 / 12,12,7 19 / 135
ADD A,H ; 1 / 4 20 / 139
LD H,A ; 1 / 4 21 / 143
RET ; 1 /10 22 / 153
|
De nuevo perdemos 50 estados, pero en esta ocasión tan solo ganamos
3 bytes en lugar de 5, por lo que no bajamos de los 22 bytes.
Parece como si no pudiésemos hacer el cálculo en menos de 100 estados,
pero sí que es posible si volvemos a cambiar de método.
En lugar de utilizar 5 rotaciones para poner el campo del tercio en su
sitio, podemos detectar en que tercio estamos al efectuar las dos
primeras rotaciones (las que ajustan la posición del campo YYY) gracias
al bit de acarreo, y en caso de que sea necesario, "inyectar" el bit directamente.
; entrada x=C, y=B; salida en HL
CALC5: LD A,B ; A = ttYYYyyy 1 / 4
AND A,7 ; A = 00000yyy 2 / 7
OR 64 ; A = 01000yyy 2 / 7
LD H,A ; H = 01000yyy 1 / 4
LD A,B ; A = ttYYYyyy 1 / 4
AND 248 ; A = ttYYY000 2 / 7
ADD A,A ; A = tYYY0000 1 / 4
JR NC,noter_3 ; 2 / 7,12
SET 4,H ; H = 01010yyy 2 / 8
noter_3: ADD A,A ; A = YYY00000 1 / 4
JR NC,noter_2 ; 2 / 7,12
SET 3,H ; H = 01001yyy 2 / 8
noter_2: ADD A,C ; A = YYYXXXXX 1 / 4
LD L,A ; L = YYYXXXXX 1 / 4
RET ; 1 / 10
|
El cálculo para la parte alta ya está terminado en la cuarta instrucción en el
caso de que estemos en el primer tercio. Los otros dos tercios necesitan
uno de los SETs para añadir el bit que les falta. Esta rutina también ocupa
22 bytes, y tarda 83 estados en el primer tercio y 86 para los
otros dos.
Parece que hemos llegado a la conclusión de que no es posible hacerlo más
pequeño, pero es posible hacerlo más rápido si tenemos en cuenta que no
existe el caso 11 para el campo tt, por lo que si detectamos el
tercer tercio, no es necesario probar si estamos en el segundo. Así
que separando los caminos un poquito y repitiendo por tanto algo de
código obtenemos:
; entrada x=C, y=B; salida en HL
CALC6: LD A,B ; A = ttYYYyyy 1 / 4
AND 7 ; A = 00000yyy 2 / 7
OR 64 ; A = 01000yyy 2 / 7
LD H,A ; H = 01000yyy 1 / 4
LD A,B ; A = ttYYYyyy 1 / 4
AND 248 ; A = ttYYY000 2 / 7
ADD A,A ; A = tYYY0000 1 / 4
JR C,ter_3 ; 2 / 7,12
ADD A,A ; A = YYY00000 1 / 4
JR NC,ter_1 ; 2 / 7,12
SET 3,H ; H = 01001yyy 2 / 8
ter_1: ADD A,C ; A = YYYXXXXX 1 / 4
LD L,A ; L = YYYXXXXX 1 / 4
RET ; 1 / 10
ter_3: SET 4,H ; H = 01010yyy 2 / 8
ADD A,A ; A = YYY00000 1 / 4
ADD A,C ; A = YYYXXXXX 1 / 4
LD L,A ; L = YYYXXXXX 1 / 4
RET ; 1 / 10
|
26 bytes, los tiempos para cada tercio son respectivamente: 78, 81, 79.
Aparte de ganar 7 estados para el tercer tercio, hemos ganado otros 5
para los otros dos casos porque el primer salto que antes se daba ahora no
se produce (y los saltos condicionales son mas rápidos cuando no se producen
(7 estados) que cuando se producen (12)).
Si el segundo salto lo hacemos de forma que salte en caso de acarreo hacia
otra zona donde se realiza el proceso del segundo tercio, separando el
código un poco más, optimizamos el camino del primer tercio a costa del camino
del segundo, con lo que obtendríamos 73, 86, 79 (y ocuparía algunos bytes mas).
Y eso es todo en cuanto a los métodos de cálculo directo. Vamos a ver
ahora los métodos que utilizan tablas.
Las tablas no son más que listas de resultados de ciertos cálculos que
dejamos apuntados en memoria para no tener que recalcularlos cada vez
que los necesitamos. Por lo tanto permiten ganar tiempo a cambio de usar memoria.
En un principio, para cada posible valor de Y, necesitaremos dos
valores en las tablas, uno para el byte alto y otro para la primera mitad del
byte bajo, a la cual le sumaremos el campo X para obtener la dirección
completa. Como tenemos 192 posibles valores de Y, obtenemos un
total de 192*2=384 bytes de datos.
Tan solo necesitamos que la rutina lea los datos de la tabla. Eso
se puede hacer por ejemplo así:
; entrada x=A, y=L; salida en DE
TABLA1: LD DE,TABLA ; 3 / 10 3 / 10
LD H,0 ; 2 / 7 5 / 17
ADD HL,HL ; 1 / 11 6 / 28
ADD HL,DE ; 1 / 11 7 / 39
ADD A,(HL) ; 1 / 7 8 / 46
LD E,A ; 1 / 4 9 / 50
INC HL ; 1 / 6 10 / 56
LD D,(HL) ; 1 / 7 11 / 63
RET ; 1 / 10 12 / 73
|
La tabla se construye pasando ttYYYyyy -> YYY00000, 010ttyyy para cada valor
del 0 al 191, y puede estar situada en cualquier parte de la memoria.
En un principio parece que no ganamos mucho sólo por el hecho de utilizar una
tabla, ya que tenemos que calcular la posición de los datos que
buscamos, y para esto tenemos que usar instrucciones de 16 bits que
resultan muy costosas en tiempo. Para mejorar esto tenemos que colocar
alguna restricción en la tabla, y aprovecharla para tener que realizar
menos cálculos. Por ejemplo, si hacemos que la tabla comience en una
dirección fija que sea múltiplo de 512, en lugar de un 0 colocamos en
H el valor TABLA/512, con lo cual al hacer la suma ADD HL,HL tenemos ya
la dirección de la tabla calculada por completo, y no necesitamos utilizar para
nada el registro DE.
; entrada x=A, y=L; salida en HL
TABLA2: LD H,TABLA/512 ; 2 / 7 2 / 7
ADD HL,HL ; 1 / 11 3 / 18
ADD A,(HL) ; 1 / 7 4 / 25
INC L ; 1 / 4 5 / 29
LD H,(HL) ; 1 / 7 6 / 36
LD L,A ; 1 / 4 7 / 40
RET ; 1 / 10 8 / 50
|
Ahora podemos utilizar INC L en lugar de INC HL porque el ADD HL,HL
dejó un valor par, y por lo tanto al incrementar L nunca va a incrementarse H,
y así nos ahorramos 2 estados mas. En el caso anterior, cabía la
posibilidad de que la etiqueta TABLA cayera en un lugar impar.
Esto ya tiene mejor pinta, ¿verdad?. Pues la cosa puede mejorar mas aún.
Si en lugar de una tabla con los 384 valores juntos creamos dos tablas de
192 bytes separadas entre si 256 bytes (osea, dejando un hueco
de 64), podemos pasar de un valor al siguiente usando INC H en lugar
de INC L (o INC HL), y nos podemos ahorrar la otra suma de 16 bits.
Sin restricción en la colocación de la pareja de tablas quedaría:
; entrada x=A, y=L; salida en DE
TABLA3: LD DE,TABLA1 ; 3 / 10
LD H,0 ; 2 / 7
ADD HL,DE ; 1 / 11
ADD A,(HL) ; 1 / 7
LD E,A ; 1 / 4
INC H ; 1 / 4
LD D,(HL) ; 1 / 7
RET ; 1 / 10 11+384 = 395 / 60
|
Ahora se hacen dos tablas ttYYYyyy -> YYY00000 por una parte y ttYYYyyy ->
010ttyyy por otra, para cada valor del 0 al 191.
Y juntando los dos trucos (aunque ahora la pareja de tablas basta con
alinearlas a un múltiplo de 256, no hace falta 512), obtenemos la
versión más rápida:
; entrada x=A, y=L; salida en HL
TABLA4: LD H,TABLA/256 ; 2 / 7
ADD A,(HL) ; 1 / 7
INC H ; 1 / 4
LD H,(HL) ; 1 / 7
LD L,A ; 1 / 4
RET ; 1 / 10 7+384 = 391 / 39
|
Como podemos ver, las tablas pueden ayudarnos a reducir el tiempo a la
mitad, lo cual resulta muy útil cuando tenemos que llamar a una rutina muy
a menudo.
Por último vamos a ver un par de ejemplos de rutinas "híbridas", en el
sentido de que realizan parte del cálculo y miran otra parte en alguna tabla,
obteniendose mayor velocidad que con el cálculo pero ocupando menos espacio que
las soluciones con tabla que hemos visto hasta ahora.
La primera que vamos a ver se aprovecha del hecho de que el cálculo de
la parte baja es muy sencillo, así que tan solo usamos una tabla de 192
bytes para la parte alta. La versión directamente optimizada (con la tabla
alineada a un múltiplo de 256) podría ser algo así:
; entrada x=B, y=A; salida en HL
HIBRI1: LD H,TABLA/256 ; 2 / 7
LD L,A ; 1 / 4
LD H,(HL) ; 1 / 7
RLCA ; 1 / 4
RLCA ; 1 / 4
AND 224 ; 2 / 7
ADD A,B ; 1 / 4
LD L,A ; 1 / 4
RET ; 1 / 10 11+192=203 / 51
|
En este caso tan solo necesitamos una tabla recorriendo ttYYYyyy -> 010ttyyy
de 0 a 191.
Para la última rutina que vamos a ver nos aprovecharemos del hecho
de que los valores que aparecen en la tabla de 192 bytes se repiten 8
veces, dado que el campo YYY no pinta nada en esta tabla. Así pues rotamos el
campo Y para acumular los bits que nos interesan en las posiciones mas bajas
y borramos los de las posiciones altas antes de mirar en la tabla. La
tabla resultante es de 32 bytes, de los cuales 8 no se usan (dado que
el tercio 11 no existe), por lo que son 24 bytes ocupando un espacio de 31.
; entrada x=B, y=A; salida en HL
HIBRI2: LD H,TABLITA/256 ; 2 / 7
RLCA ; 1 / 4
RLCA ; 1 / 4
LD C,A ; 1 / 4
AND 31 ; 2 / 7
LD L,A ; 1 / 4
LD H,(HL) ; 1 / 7
LD A,C ; 1 / 4
AND 224 ; 2 / 7
ADD A,B ; 1 / 4
LD L,A ; 1 / 4
RET ; 1 / 10 15+24 = 39 / 66
|
La tablita en este caso se construye recorriendo 000yyytt -> 010ttyyy de 0 a 30
(ignorando los casos con tt = 11).
Visto todo esto, ¿cual es la mejor rutina? Si nos quedamos sólo con las
mejores rutinas, podemos escoger la relación velocidad/espacio que mejor
convenga a nuestro programa, entre las siguientes:
| |
bytes |
/ |
estados |
| TABLA4: |
391 |
/ |
39 |
| HIBRI1: |
203 |
/ |
51 |
| HIBRI2: |
39(*) |
/ |
66 |
| CALC6: |
26 |
/ |
81 |
| CALC5: |
22 |
/ |
86 |
* > 46 si no aprovechásemos los huecos.
¿Pueden optimizarse más? Pues depende. Como rutinas de uso general, creo
que no dan más de si (aparte de la obviedad que supone usarlas en línea
y evitar por lo tanto el RET), pero una vez aplicadas a un juego
determinado, las características del juego pueden favorecer nuevas
optimizaciones. Por ejemplo, si un juego tan solo usa los dos primeros
tercios, dejando el tercio de abajo para puntuaciones, barras de energía,
etc... podemos reducir los tamaños de las tablas a 256,128 o
16 bytes (en esta ocasión seguidos) respectivamente, y las rutinas de
cálculo quedarían como una sóla de 18 bytes, tardando 71/74 estados.
Con esto concluye el artículo, si tenéis dudas o queréis proponer
temas para futuros artículos, podeis apuntaros a la lista de correo de
programación en ensamblador [z80asm] de speccy.org.
La mayoría de las rutinas vistas en este artículo ya fueron discutidas hace
tiempo en dicha lista, y quiero agradecer especialmente la colaboración de
Truevideo (que planteó su rutina usando tabla) y Z80user (autor
original de CALC6, de la cual se deriva fácilmente CALC5).
Hasta otra.
