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:

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:

* > 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.