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.

Etiquetas:

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.

Páginas relacionadas

Pseudo-Random Numbers ROM Zone Finder Pro
Utilidad escrita en ZX BASIC para la Sinclair ZX Spectrum que busca en la ROM una zona de 256 octetos con el mayor número de octetos diferentes.
Pseudo-Random Numbers ROM Zone Finder
Utilidad escrita en Sinclair BASIC para la Sinclair ZX Spectrum que busca en la ROM una zona de 256 octetos con el mayor número de octetos diferentes.