miércoles, 29 de febrero de 2012
Una de las pegas que nos encontramos a la hora de trabajar con nuestros MSX (o en general cualquier trasto gobernado por un Z80) es que el Z80 no ofrece instrucciones de división, salvo que queramos dividir por potencias de dos en cuyo caso echaremos mano de las instrucciones de rotación y desplazamiento de bits. En el caso de que necesitemos dividir por un número que no sea potencia de 2, necesitaremos echar mano de una rutina que realice el trabajo.
Una primera aproximación (bastante grosera) es comenzar a restar el divisor del dividendo y parar cuando el dividendo sea menor que el divisor. El número de veces que hayamos podido hacerlo será el cociente y el dividendo que nos queda será el resto. Esto funciona bastante bien siempre que podamos prever que el cociente no será muy grande.
Sin embargo, cuando estamos ante dos números cualesquiera y pretendemos dividir uno por otro, la anterior aproximación puede eternizarse. Imaginad que queremos dividir 65535 entre 1 o, lo que sería peor, ¡65535 entre 0! En este último caso la rutina anterior jamás se detendría.
Así pues, deberemos pensar en una rutina de división algo más inteligente, que nos permita reducir el coste temporal de la operación a algo que podamos asumir.
¡De vuelta al cole!
Volvamos con la imaginación al cole un momento para recordar cómo nos enseñaron a dividir. Poníamos el dividendo y el divisor e íbamos mirando a ver a cuanto cabía, para ir restando del dividendo y bajando cifras. ¿Os acordáis? Veamos un ejemplo con esta operación: 750 dividido entre 225.
Vale, todos nos acordamos de cómo se hacía esto. Ahora vamos a hacer lo mismo, pero en lugar de en base 10, en base 2. Para ello pondremos los números en binario y a dividir.
Podéis intentar hacer la división vosotros mismos, teniendo en cuenta que ahora sólo hay dos posibles cifras en el cociente 0 y 1. Si no tenéis ganas, aquí tenéis la divisón hecha:
¡Vale! Nos da exactamente lo mismo: cociente 3 y resto 75. Así que el algoritmo de la división que nos enseñaron en el cole es perfectamente utilizable en binario. Ahora vamos a ver cómo lo podemos programar.
Seleccionando cifras...
El ejemplo que hemos visto, el dividendo es un número de 10 bits representable mediante un número de 16 bits, mientras que el divisor es un número de 8 bits. Así que intentaremos obtener una rutina que nos permita dividir un número de 16 bits entre uno de 8 bits y nos devuelva tanto el cociente como el resto de la división entera por defecto. Establezcamos primero cómo recibimos los parámetros. Algo lógico sería el dividendo en HL y el divisor en A, pero vamos a utilizar el registro C para el divisor, ya que A lo vamos a reservar para realizar las operaciones.
Lo primero que tenemos que ver es que vamos a ir cogiendo las cifras del dividendo comenzando por la mayor y siguiendo a partir de ahí. Podemos desplazar hl hacia la izquierda e ir mirando el flag c, por el que van a pasar todas las cifras del dividendo. Aprovechamos que la instrucción add hl,hl hace eso precisamente.
Ahora tenemos en el flag c la cifra más significativa del dividendo, nos toca comprobar si "cabe" o no. Es decir, tenemos que comprobar si el número formado por las cifras que hemos ido cogiendo del dividendo es mayor o igual que el divisor. Para esto nos vendría muy bien que ese número estuviera en A (ya os dije que mejor reservarlo), así que tras la instrucción anterior podríamos meter la cifra más significativa que acabamos de sacar del dividendo como cifra menos significativa de A. ¡Perfecto! Utilicemos rla, que nos soluciona la papeleta.
¡Ojo! Esto nos obliga a que al comienzo del algoritmo A valga cero. Así que en la inicialización necesitaremos un xor a para asegurar que no utilizamos valores que pudieran existir antes.
Cero al cociente...
Ahora tenemos la siguiente situación:
Pensemos ahora qué pasa cuando A es mayor o igual que C. Significa que "cabe" y al trabajar en binario siempre "cabe" a uno. Con lo cual deberemos realizar lo siguiente:
Nos queda decidir dónde y cómo vamos a almacenar el cociente. Una primera idea puede ser utilizar el registro DE (que de momento no lo estábamos utilizando). A cada cifra analizada vamos a meter un 0 o un 1 y además empezamos a meter por la cifra más significativa. Podemos hacer algo parecido a lo que estamos haciendo con A: meter las cifras por la derecha e ir desplazando hacia la izquierda... entonces... ¿para qué utilizar DE si podemos aprovechar HL?
En HL tenemos las cifras del dividendo, pero cada vez menos. Cada vez que hacemos un add hl,hl estaremos desplazando las cifras hacia la izquierda y metiendo ceros por la derecha. Así que podemos aprovechar este desplazamiento para ir metiendo por la derecha las cifras del cociente.
Por lo tanto, cuando haya que meter un cero en el cociente no habrá que hacer nada, porque add hl,hl ya lo ha hecho por nosotros. Cuando haya que meter un 1, simplemente necesitaremos hacer un inc l para solucionarlo (recordemos que el bit menos significativo será 0 tras el add hl,hl).
Juntémoslo todo
Si has llegado hasta aquí después de leer todo el rollo anterior, seguramente habrás visto que faltan algunos pequeños detalles para completar la rutina. En primer lugar deberemos repetir el proceso anterior para las 16 cifras que tiene el dividendo. Podemos utilizar el registro B y la instrucción djnz.
Pongamos ahora en limpio todo lo que hemos ido apuntando y añadamos las etiquetas para los saltos:
¡Y ya está! ¿A que ha quedado bonita? A la salida en HL tendremos el cociente y en A el resto de la división.
Fue MSX-Kun quien me habló de esta rutina, la cual encontró en un par de sitios (aquí y aquí) sobre Z80. Pero resulta que... ¡no funciona correctamente en todos los casos! ¡Probadla! ¿Por qué no funciona si todo parece correcto?
El problema es que el divisor es un número de 8 bits y este número puede ser todo lo grande que queramos (siempre que no nos pasemos de 8 bits). Pero la comparación la estamos haciendo con otro número de 8 bits y eso es lo que nos está dando problemas.
La solución pasa por trabajar no con un número de 8 bits, sino con un número de 9 bits. Para ello no debemos olvidarnos del flag c tras meter una nueva cifra en A. Si tras el rla se activa el flag c, significará que al meter la cifra en A tenemos un número con 9 bits significativos. Como el divisor es de 8 bits, SEGURO que A es mayor que C, por lo que deberíamos saltar a la parte donde metemos un uno en el divisor.
La rutina corregida es la siguiente:
Simplemente con esa nueva instrucción tendremos en cuenta el noveno bit de A y podremos realizar la división sin ningún problema.
Espero que os sirva la rutinita. Como siempre todo comentario será bienvenido.
Editado 17-Mayo-2017: el primer enlace a la rutina original ya no existe y en el segundo la corrigieron unos meses después de la publicación de este post, ¿se fijarían en él?
Una primera aproximación (bastante grosera) es comenzar a restar el divisor del dividendo y parar cuando el dividendo sea menor que el divisor. El número de veces que hayamos podido hacerlo será el cociente y el dividendo que nos queda será el resto. Esto funciona bastante bien siempre que podamos prever que el cociente no será muy grande.
Sin embargo, cuando estamos ante dos números cualesquiera y pretendemos dividir uno por otro, la anterior aproximación puede eternizarse. Imaginad que queremos dividir 65535 entre 1 o, lo que sería peor, ¡65535 entre 0! En este último caso la rutina anterior jamás se detendría.
Así pues, deberemos pensar en una rutina de división algo más inteligente, que nos permita reducir el coste temporal de la operación a algo que podamos asumir.
¡De vuelta al cole!
Volvamos con la imaginación al cole un momento para recordar cómo nos enseñaron a dividir. Poníamos el dividendo y el divisor e íbamos mirando a ver a cuanto cabía, para ir restando del dividendo y bajando cifras. ¿Os acordáis? Veamos un ejemplo con esta operación: 750 dividido entre 225.
750|225
75 3
75 3
Vale, todos nos acordamos de cómo se hacía esto. Ahora vamos a hacer lo mismo, pero en lugar de en base 10, en base 2. Para ello pondremos los números en binario y a dividir.
1011101110|11100001
Podéis intentar hacer la división vosotros mismos, teniendo en cuenta que ahora sólo hay dos posibles cifras en el cociente 0 y 1. Si no tenéis ganas, aquí tenéis la divisón hecha:
1011101110|11100001
100101101 11
1001011
100101101 11
1001011
¡Vale! Nos da exactamente lo mismo: cociente 3 y resto 75. Así que el algoritmo de la división que nos enseñaron en el cole es perfectamente utilizable en binario. Ahora vamos a ver cómo lo podemos programar.
Seleccionando cifras...
El ejemplo que hemos visto, el dividendo es un número de 10 bits representable mediante un número de 16 bits, mientras que el divisor es un número de 8 bits. Así que intentaremos obtener una rutina que nos permita dividir un número de 16 bits entre uno de 8 bits y nos devuelva tanto el cociente como el resto de la división entera por defecto. Establezcamos primero cómo recibimos los parámetros. Algo lógico sería el dividendo en HL y el divisor en A, pero vamos a utilizar el registro C para el divisor, ya que A lo vamos a reservar para realizar las operaciones.
Lo primero que tenemos que ver es que vamos a ir cogiendo las cifras del dividendo comenzando por la mayor y siguiendo a partir de ahí. Podemos desplazar hl hacia la izquierda e ir mirando el flag c, por el que van a pasar todas las cifras del dividendo. Aprovechamos que la instrucción add hl,hl hace eso precisamente.
Ahora tenemos en el flag c la cifra más significativa del dividendo, nos toca comprobar si "cabe" o no. Es decir, tenemos que comprobar si el número formado por las cifras que hemos ido cogiendo del dividendo es mayor o igual que el divisor. Para esto nos vendría muy bien que ese número estuviera en A (ya os dije que mejor reservarlo), así que tras la instrucción anterior podríamos meter la cifra más significativa que acabamos de sacar del dividendo como cifra menos significativa de A. ¡Perfecto! Utilicemos rla, que nos soluciona la papeleta.
¡Ojo! Esto nos obliga a que al comienzo del algoritmo A valga cero. Así que en la inicialización necesitaremos un xor a para asegurar que no utilizamos valores que pudieran existir antes.
Cero al cociente...
Ahora tenemos la siguiente situación:
- En HL tenemos las cifras del dividendo que aún no hemos utilizado.
- En A tenemos el número formado por las cifras más significativas del dividendo.
- En C tenemos el divisor.
Pensemos ahora qué pasa cuando A es mayor o igual que C. Significa que "cabe" y al trabajar en binario siempre "cabe" a uno. Con lo cual deberemos realizar lo siguiente:
- Añadir un 1 al cociente.
- Substraer el divisor al número en A.
Nos queda decidir dónde y cómo vamos a almacenar el cociente. Una primera idea puede ser utilizar el registro DE (que de momento no lo estábamos utilizando). A cada cifra analizada vamos a meter un 0 o un 1 y además empezamos a meter por la cifra más significativa. Podemos hacer algo parecido a lo que estamos haciendo con A: meter las cifras por la derecha e ir desplazando hacia la izquierda... entonces... ¿para qué utilizar DE si podemos aprovechar HL?
En HL tenemos las cifras del dividendo, pero cada vez menos. Cada vez que hacemos un add hl,hl estaremos desplazando las cifras hacia la izquierda y metiendo ceros por la derecha. Así que podemos aprovechar este desplazamiento para ir metiendo por la derecha las cifras del cociente.
Por lo tanto, cuando haya que meter un cero en el cociente no habrá que hacer nada, porque add hl,hl ya lo ha hecho por nosotros. Cuando haya que meter un 1, simplemente necesitaremos hacer un inc l para solucionarlo (recordemos que el bit menos significativo será 0 tras el add hl,hl).
Juntémoslo todo
Si has llegado hasta aquí después de leer todo el rollo anterior, seguramente habrás visto que faltan algunos pequeños detalles para completar la rutina. En primer lugar deberemos repetir el proceso anterior para las 16 cifras que tiene el dividendo. Podemos utilizar el registro B y la instrucción djnz.
Pongamos ahora en limpio todo lo que hemos ido apuntando y añadamos las etiquetas para los saltos:
div16by8: xor a
ld b,16
.bucle: add hl,hl
rla
cp c
jr c,.cero
sub c
inc l
.cero: djnz .bucle
ret
ld b,16
.bucle: add hl,hl
rla
cp c
jr c,.cero
sub c
inc l
.cero: djnz .bucle
ret
¡Y ya está! ¿A que ha quedado bonita? A la salida en HL tendremos el cociente y en A el resto de la división.
Fue MSX-Kun quien me habló de esta rutina, la cual encontró en un par de sitios (
El problema es que el divisor es un número de 8 bits y este número puede ser todo lo grande que queramos (siempre que no nos pasemos de 8 bits). Pero la comparación la estamos haciendo con otro número de 8 bits y eso es lo que nos está dando problemas.
La solución pasa por trabajar no con un número de 8 bits, sino con un número de 9 bits. Para ello no debemos olvidarnos del flag c tras meter una nueva cifra en A. Si tras el rla se activa el flag c, significará que al meter la cifra en A tenemos un número con 9 bits significativos. Como el divisor es de 8 bits, SEGURO que A es mayor que C, por lo que deberíamos saltar a la parte donde metemos un uno en el divisor.
La rutina corregida es la siguiente:
div16by8: xor a
ld b,16
.bucle: add hl,hl
rla
jr c,.uno
cp c
jr c,.cero
.uno: sub c
inc l
.cero: djnz .bucle
ret
ld b,16
.bucle: add hl,hl
rla
jr c,.uno
cp c
jr c,.cero
.uno: sub c
inc l
.cero: djnz .bucle
ret
Simplemente con esa nueva instrucción tendremos en cuenta el noveno bit de A y podremos realizar la división sin ningún problema.
Espero que os sirva la rutinita. Como siempre todo comentario será bienvenido.
Editado 17-Mayo-2017: el primer enlace a la rutina original ya no existe y en el segundo la corrigieron unos meses después de la publicación de este post, ¿se fijarían en él?