miércoles, 29 de febrero de 2012

Dividiendo que es gerundio

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.

750|225
 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


¡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.
Así que lo primero que tenemos que comprobar es si el número que tenemos en A (la parte más significativa del dividendo) es mayor o igual que C (el divisor). Esto lo solucionamos con un cp c. Si el flag c se activa tras esa comparación, significará que que C es mayor que A. Eso indica que el divisor es más grande, es decir "no cabe". Así que diremos aquello de "cero al cociente y cogemos la cifra siguiente", metemos un cero en el cociente y volvemos a la instrucción add hl,hl para comenzar a coger la siguiente cifra.

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.
Comenzando por el final, con un simple sub c ya hemos substraído el divisor de A y lo tenemos preparado para seguir.

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


¡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:

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


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.

viernes, 3 de febrero de 2012

Cuarto aniversario del blog

¡Ya llevo cuatro años dando la lata por aquí! Y espero seguir mucho tiempo. Gracias a todos los que leéis el blog y participáis con comentarios.