Números seudo-aleatorios de ocho bitios en Z80
Descripción del contenido de la página
Varias rutinas para obtener números seudo-aleatorios de ocho bitios en Z80 en una Sinclair ZX Spectrum.
En marzo de 2010 empecé a trabajar en el código fuente de un jueguecito de «marcianos», muy sencillo, que había escrito en 1986 para la ZX Spectrum en ensamblador de Z80: Alien-A. Quería prepararlo para publicarlo y hacerle algunas pequeñas mejoras, entre las cuales una rutina mejor para obtener números seudo-aleatorios de ocho bitios (es decir, con valores entre 0 y 255).
La rutina original del código de 1986 es la siguiente:
SEED EQU 23670
RANDOM
LD HL,(SEED)
LD B,(HL)
ADC HL,DE
LD A,#3F
AND H
LD H,A
LD (SEED),HL
LD A,R
SUB B
RET
No recuerdo su origen. No sé si encontré ese algoritmo en alguna parte o se me ocurrió a mí. De hecho al volverla a ver después de tantos años, me resultó curioso que usaba el registro DE (cuyo valor podía ser cualquiera, según del uso que le diera el programa principal). Según parece las intrucciones LD A,#3F y AND H limitan el valor de HL a las direcciones de la ROM.
El algoritmo no era muy eficiente, lo cual se comprobaba claramente al observar el reparto de las estrellas en el cielo, cuyas coordenadas se calculaban al azar: los puntos que representaban las estrellas formaban grupos en ciertos lugares de la pantalla, e incluso formaban algunas líneas.
Hice algunas modificaciones, quitando y poniendo cálculos y utilizando también la variable del sistema FRAMES, pero no logré mejorar mucho el resultado:
SEED EQU 23670
FRAMES EQU 23672
RANDOM
LD HL,(FRAMES)
LD B,(HL)
;ADC HL,DE
;LD A,#3F
;AND H
;LD H,A
;LD (SEED),HL
LD A,R
XOR B
;SUB B
RET
Decidí que no merecía la pena intentar reinventar la rueda: probablemente había muchas rutinas de este tipo ya escritas por otros programadores. Tras unas búsquedas en la red, encontré algunos ejemplos, como el que sigue, descrito por su autor, Lee Davison, en la página Z80 8 bit PRNG:
RANDOM
; Reference: http://members.multimania.co.uk/leeedavison/z80/prng/index.html
LD A,(R_SEED)
AND #B8
SCF
JP PO,NO_CLR
CCF
NO_CLR LD A,(R_SEED)
RLA
LD (R_SEED),A
RET
R_SEED DEFB 1
No funcionó mejor que la original.
En la página de San Bergmans Pseudo-Random Number Generator Tests encontré otro ejemplo parecido que tampoco me convenció:
RANDOM
LD A,(R_SEED)
LD C,A
AND #B8
SCF
JP PO,NO_CLR
CCF
NO_CLR LD A,C
RLA
LD C,A
LD (R_SEED),A
RET
R_SEED DEFB 1
Una entrada en un foro, titulada Z80 ASM game 30 minute tutorial, me dio la idea de utilizar un puntero a una dirección de la ROM en que hubiera 256 valores variados:
SEED EQU 23670
FRAMES EQU 23672
RANDOM
PUSH HL
LD HL,SEED
LD A,(HL)
LD HL,FRAMES
ADD A,(HL)
LD HL,14000
ADD A,L
LD L,A
LD A,(HL)
LD HL,SEED
LD (HL),A
POP HL
RET
Pero el resultado tampoco era bueno.
Busqué en los libros que tengo sobre código máquina de Z80. Recordé que el libro con el que aprendí las primeras nociones de Z80 para ZX Spectrum (como muchos otros principiantes de entonces) tenía el listado completo, y explicado paso a paso, de una versión del juego de la rana que tiene que atravesar una carretera, y sin duda tenía que usar algún tipo de generador de números seudo-aleatorios. Se trataba de Lenguaje máquina ZX Spectrum para principiantes, editado por Indescomp en 1984 (y cuya versión original en inglés es de Beam Software, de 1982).
Efectivamente, no fue difícil encontrar la rutina, que era una variante más de la misma idea:
RANDOM
; Reference: "Lenguaje Máquina ZX Spectrum para principiantes", Indescomp, 1984, p. 226
PUSH HL
PUSH BC
LD HL,(R_SEED)
LD B,(HL)
INC HL
LD A,#3F
AND H
LD H,A
LD A,B
LD (R_SEED),HL
POP BC
POP HL
RET
R_SEED DEFW 0
Pero, como en los otros casos, no devolvía valores suficientemente variados.
Entonces recordé que en un programa mío inédito, Finen per Imago, una aventura conversacional en Z80, había escrito una rutina para generar números seudo-aleatorios. Devolvía valores de ocho bitios en el rango especificado por los registros H y L. Bastaba pues añadirle un punto de entrada para darle a esos registros los valores 255 y 0 respectivamente. El resultado fue el siguiente:
SEED EQU 23670
FRAMES EQU 23672
STACK_BC EQU #2D2B
FP_TO_BC EQU #2DA2
FP_TO_A EQU #2DD5
RANDOM
PUSH HL
LD HL,#FF00
JR RANDOM_LH1
;
;Número aleatorio, rango L...H
;
;Entrada
; L=número mínimo permitido
; H=número máximo permitido
;Salida
; A=número aleatorio entre L y H, que es L+INT(RND*(H-L+1))
; indicador Z=indica si A es cero
;
RANDOM_LH PUSH HL
RANDOM_LH1 PUSH IY
PUSH DE
PUSH BC
LD IY,ERR_NR ;apuntar a las variables del sistema
PUSH HL ;guardar provisionalmente mínimo y máximo
LD B,0 ;pasar a BC...
LD C,L ;...el mínimo
CALL STACK_BC ;pasar BC a la pila del calculador (min)
RST #28 ;llamar al calculador
DEFB #31 ;duplicar (min,min)
DEFB #38 ;fin
POP HL ;recuperar mínimo y máximo
LD B,0 ;pasar a BC...
LD C,H ;...el máximo
CALL STACK_BC ;pasar BC a la pila del calculador (min,min,max)
RST #28 ;calculador
DEFB #01 ;intercambiar (min,max,min)
DEFB #03 ;restar (min,max-min)
DEFB #A1 ;meter 1 (min,max-min,1)
DEFB #0F ;sumar (min,max-min+1)
DEFB #38 ;fin de operaciones del calculador
LD BC,(SEED) ;tomar el valor de SEED
CALL STACK_BC ;almacenarlo en la pila del calculador (min,max-min,1,seed)
;Hallar número aleatorio
RST #28 ;llamar al calculador
DEFB #A1 ;meter 1 (min,max-min+1,seed,1)
DEFB #0F ;sumar (min,max-min+1,seed+1)
DEFB #34 ;stk-data, guardar dato que sigue
DEFB #37,#16 ;75 (min,max-min+1,seed+1,75)
DEFB #04 ;multiplicar (min,max-min+1,(seed+1)*75)
DEFB #34 ;stk-data, guardar dato que sigue
DEFB #80,#41,0,0,#80 ;65537 (min,max-min+1,(seed+1)*75,65537)
DEFB #32 ;n-mod-m (min,max-min+1,resto,cociente)
DEFB #02 ;borrar (min,max-min+1,resto)
DEFB #A1 ;meter 1 (min,max-min+1,resto,1)
DEFB #03 ;restar (min,max-min+1,rnd)
DEFB #31 ;duplicar (min,max-min+1,rnd,rnd)
DEFB #38 ;fin de operaciones del calculador
CALL FP_TO_BC ;pasar cima de la pila del calculador a BC (min,max-min+1,rnd)
LD (SEED),BC ;guardar nuevo valor de SEED
LD A,(HL) ;HL salió de FP_TO_BC apuntando al número siguiente
AND A ;¿es entero?
JR Z,RANDOM_LH2 ;si es así, saltar
SUB 16 ;restar 16 al exponente, que es dividir entre 65536,...
LD (HL),A ;...y devolverlo a su lugar
RANDOM_LH2 RST #28 ;calculador
DEFB #04 ;multiplica (min,(max-min+1)*rnd)
DEFB #0F ;sumar (min+(max-min+1)*rnd)
DEFB #27 ;entero (INT(min+(max-min+1)*rnd)
DEFB #38 ;fin de operaciones del calculador
CALL FP_TO_A ;tomar en A el número aleatorio de la pila del calculador
AND A ;alzar o bajar el indicador Z según A sea o no cero, respectivamente
POP BC
POP DE
POP IY
POP HL
RET
Como se ve, la rutina utiliza el calculador del sistema para hacer todas las operaciones. Sin embargo, por algún motivo que no acerté a descubrir, el código entraba en algún punto sin retorno y no devolvía ningún valor. Sospeché que era un problema de incompatibilidad con el emulador Fuse, pues el mismo código funcionaba perfectamente en el programa para el que fue escrito, pero no me paré a investigarlo.
Por último eché un vistazo al listado desensamblado de la ROM de la ZX Spectrum, para localizar la rutina que calcula los números seudo-aleatorios para la función RND de Sinclair BASIC, con la intención de hacer una llamada directa, pero al final me decidí a escribir una rutina nueva, inspirada en todas las anteriores:
SEED EQU 23670
RANDOM
PUSH HL
PUSH BC
LD HL,SEED
LD B,(HL)
LD A,R
ADD A,B
LD HL,509
ADD A,L
LD L,A
LD A,(HL)
LD (SEED),A
POP BC
POP HL
RET
Y acerté: Las estrellitas del juego parecían bien repartidas por toda la pantalla.
Utilizo una zona de la ROM de la ZX Spectrum, apuntada por el registro HL, para obtener su contenido; cada valor devuelto se guarda a su vez como semilla para usar como puntero de esa zona en la siguiente ocasión, modificado con el registro R, de contenido imprevisible.
¿Y por qué usé la dirección 509? En principio usé 13990, dirección a partir de la cual hay 256 octetos suficientemente variados; lo averigüé echando una vistazo alrededor de la dirección 14000 que utilizaba una de las rutinas mencionadas anteriormente. Pero para afinar aun más el algoritmo se me ocurrió la idea de buscar, en toda la ROM, la dirección que apuntara a los 256 octetos más variados. Para descubrir dicha dirección, y más que nada por el placer de escribir un programa nuevo en Sinclar BASIC después de muchos años, programé en una tarde Pseudo-Random Numbers ROM Zone Finder, programa de nombre muy largo que me encantó crear.
Lo ejecuté poniendo el emulador Fuse al máximo de velocidad que puede alcanzar en mi máquina (1300% de la velocidad original de la ZX Spectrum) y esperé varias horas el resultado (el programa podría ser más rápido si usara una zona de memoria para representar los valores hallados, en lugar de usar PLOT y POINT, pero me gustaba ver el efecto de los puntitos sobre la pantalla, representando la distribución de los valores hallados en cada bloque de 256 direcciones).
El resultado fue la dirección que usé en la rutina: 509; en el rango 509-764 está el mayor número de octetos diferentes: 166.
Sin embargo, días después comprobé que la dirección 509 volvía a dar peores resultados que la 13990 que había usado anteriormente. Al principio no lo entendí. Incluso volví a repasar el algoritmo de Pseudo-Random Numbers ROM Zone Finder por si había metido la pata. Hice algunas pruebas y mejoré el código de la rutina para que usara la variable del sistema FRAMES, y corregí un fallo: había estado sumando la semilla modificada al registro L, no al registo completo HL; eso causaba que no se alcanzara todo el rango de las 256 direcciones. Sin embargo aun con esa corrección el código seguía sin funcionar correctamente con la dirección 509 como base de la tabla de valores y decidí usar la 13990:
SEED EQU 23670
FRAMES EQU 23672
RANDOM
PUSH HL
PUSH BC
LD A,(SEED)
LD B,A
LD A,(FRAMES)
LD C,A
LD A,R
ADD A,B
ADD A,C
;LD HL,509 ; ROM address with the higher number of different values (166) in 256 bytes
LD HL,13990 ; ROM address pointing to 256 misc values
LD B,0
LD C,A
ADD HL,BC
LD A,(HL)
LD (SEED),A
POP BC
POP HL
RET
Al final creí haber encontrado la causa del problema: estaba usando una dirección de la ROM... y en los últimos días había estaba trabajando (con el emulador Fuse) con la ZX Spectrum 128K, mientras que antes había trabajado con los restantes modelos: 48K, +2, +2A y sobre todo con la +3. No estaba seguro de si esas dos zonas de la ROM eran diferentes en alguno de los modelos, pero parecía una buena explicación.
Repetí la búsqueda de las zonas con Pseudo-Random Numbers ROM Zone Finder Pro, para cada una de las cinco computadoras y para todas obtuve el mismo resultado: entre las direcciones 509 y 764 había el mayor número de 256 octetos diferentes de los 16 KiB de ROM: 166 valores distintos. Mi teoría estaba equivocada.
Días después, buscando una información sobre ensambladores de Z80 escritos en Forth, encontré la siguiente rutina en Home of the Z80 CPU:
; Source found in:
; http://z80.info/zip/z80asm.zip
; returns pseudo random 8 bit number in A. Only affects A.
; (r_seed) is the byte from which the number is generated and MUST be
; initialised to a non zero value or this function will always return
; zero. Also r_seed must be in RAM, you can see why......
rand_8:
LD A,(r_seed) ; get seed
AND #B8 ; mask non feedback bits
SCF ; set carry
JP PO,no_clr ; skip clear if odd
CCF ; complement carry (clear it)
no_clr:
LD A,(r_seed) ; get seed back
RLA ; rotate carry into byte
LD (r_seed),A ; save back for next prn
RET
r_seed:
DB 1 ; prng seed byte (must not be zero)
(En lugar de r_seed es mejor usar la variable del sistema SEED y así ahorramos un bonito octeto). Cuando probé la rutina comprobé que las estrellas siempre formaban dos perfectas líneas diagonales... Una auténtica conjunción estelar, nada aleatoria.
Poco después, buscando un diseñador de caracteres cómodo para ZX Spectrum, di con la la página de Jim Grimwood dedicada a la revista Your Spectrum; y entre los muchos tesoros que contiene, me llamó la atención un programa llamado Random Plot para el que se usó una rutina de números aleatorios interesante extraída de otro programa, cuyo enlace también se incluye. Aún no la he probado.