Comment donc les nombres aléatoires sont-ils générés sur un VG5000µ. C'est ce que je vous propose de suivre aujourd'hui en décortiquant le code.
Afin de suivre, il est important de comprendre comment les nombres sont stockés sur VG5000µ, et je vous propose pour cela un petit détour par cet article.
Petit rappel avant de commencer : un générateur de nombres aléatoires est une procédure qui émet une suite de nombres sur un intervalle, cette suite tentant d'avoir des propriétés intéressantes qui donnent l'illusion de l'aléatoire. La suite est cependant parfaitement définie, même si pas toujours simple à suivre, et c'est ce que nous allons voir par la suite.
L'initialisation
Tout commence très tôt pour le générateur de nombres aléatoires. Dès l’initialisation de la machine, une série de valeurs est copiée depuis la ROM vers les variables systèmes. Cela se passe en $1071, juste après l'initialisation de l'affichage.
ld hl,initvalues
ld bc,$0065
ld de,ramlow
ldir
Il y a donc 101 valeurs ($65) copiées depuis initvalues ($1194) vers ramlow ($4830). Parmi celles-ci, les suivantes sont copiés vers $4844 et nous intéressent aujourd'hui.
defb $00,$00,$00
defb $35,$4a,$ca,$99
defb $39,$1c,$76,$98
defb $22,$95,$b3,$98
defb $0a,$dd,$47,$98
defb $53,$d1,$99,$99
defb $0a,$1a,$9f,$98
defb $65,$bc,$cd,$98
defb $d6,$77,$3e,$98
defb $52,$c7,$4f,$80
Les trois premiers octets sont les trois index avec lesquels le générateur va jouer. Nous les appellerons les trois seeds. Suivent 8 nombres plutôt grands, positifs et négatifs (le premier vaut -26514538). Et enfin vient le nombre d'origine, qui vaut 0.8116351366043091, que vous pouvez retrouver sous sa forme arrondie en tapant PRINT RND(0) dès l'allumage du VG5000µ.
Cette table n'est pas la seule qui va être utilisée par le générateur. Il en existe une autre, qui sera utilisée depuis la ROM, en $093d, d'une longueur de 3.
defb $68,$b1,$46,$68
defb $99,$e9,$92,$69
defb $10,$d1,$75,$68
L'instruction RND
L'instruction RND commence en $090d par un petit préambule qui vérifie l'argument passé à la fonction. Cet argument est disponible dans FAC, l'accumulateur flottant (voir précédemment)
inst_rnd: rst getsign
ld hl,rnd_seed_2
jp m,reseed
ld hl,rnd_gen
call hl_to_fac
ld hl,rnd_seed_2
ret z
Ce préambule teste en premier lieu le signe de l'argument. S'il est négatif, la routine branche vers reseed, que nous verrons plus loin. C'est au passage un comportement qui n'est indiqué ni dans le manuel d'utilisation du VG5000µ, ni dans les « Clés pour VG5000 », qui donnent de fausses informations (je vous laisse regarder).
Dans le cas du branchement, HL point vers la seed 2 (et je ne vois aucun intérêt à ce que cela ne soit pas fait après le branchement...)
Si l'argument est nul ou positif, alors la nombre pointé par HL, qui est la variable système du dernier nombre généré ,est copié dans FAC. Souvenez-vous, c'est à cette adresse qu'a été placé à l'initialisation le nombre 0.8116351.
On refait pointer HL vers la seed 2 puis, si l’argument était 0, on sort de la routine immédiatement (le flag Zéro a été conservé depuis rst getsign).
Le calcul
Puisqu'on est à présent dans le cas où l’argument est positif, il convient de générer un nouveau nombre. Ce nouveau nombre est basé sur, d'une part, le nombre généré précédemment, et d'autre part, les trois index qui avaient été initialisés à zéro (voir ci-dessus).
Première étape
add a,(hl)
and a,$07
ld b,$00
ld (hl),a
inc hl
add a,a
add a,a
ld c,a
add hl,bc
call hl_to_bcde
call fp_mul
La première section du code précédent récupère l'index seed 2 en l'incrémentant de 1. En effet, A contient 1 depuis l'appel à getsign. Le résultat est pris modulo 8 et remonté en RAM.
Au passage, B est initialisé à 0 pour que BC puisse servir d'index, et HL va pointer un cran plus loin, sur le début de la table des coefficients initialisés au boot (la table des 8 valeurs).
La seconde section calcul le pointeur dans cette table en quadruplant A, qui est l'index, en format BC comme index à ajouter au pointeur de base HL.
L'appel hl_to_bcde copie le nombre pointé dans la table vers BCDE, puis l'appel à fp_mul effectue la multiplication avec le contenu de FAC.
Résumé : cette première étape est donc une multiplication du précédent nombre généré par un autre nombre, fixe, pris dans une table dans 8 valeurs tour à tour.
Le tout premier appel à RND(1) va multiplier 16129081 ($98 $76 $1c $39) avec0.8116351366043091($80 $4f $c7 $52`).
Cela donne 13090929 ($98 $47$c0 $71). Cela peut se vérifier dans FAC ($49e6). Attention, le nombre est octet par octet dans le sens inverse à celui que j'utilise ici.
Seconde étape
ld a,(rnd_seed_1)
inc a
and a,$03
ld b,$00
cp a,$01
adc a,b
ld (rnd_seed_1),a
ld hl,rnd_add - 4
add a,a
add a,a
ld c,a
add hl,bc
call fp_add_hl
afterreseed: call fac_to_bcde
La seconde étape se divise elle aussi en deux sections.
Dans la première section, on récupère la seed 1, qui est incrémentée de 1 et modulo 4. Cependant, la valeur 0 est interdite. Par une comparaison avec 1 et un ajout à 0 (via B) avec retenue, si l'index était à 0, alors il est poussé à 1.
C'est donc en fait un index modulo 3 que l'on obtient.
Et cet index forme un pointeur via HL de manière similaire à l'étape précédente, dans la table de trois valeurs de la ROM mentionné au début de l'article.
Cette valeur est alors ajoutée à FAC. L'appel à fp_add_hl se charge de l'étape intermédiaire de chargement de la valeur dans BCDE. Puis le résultat est ramené dans BCDE.
Le label est un branchement venant du reseed que nous verrons plus loin.
Résumé : cette seconde étape est une addition du nombre obtenue à la première étape avec un des trois nombres pris dans la deuxième table, pris tour à tour.
Le tout premier appel additionne 13090929 ($98 $47 $c0 $71 ) avec 4.626181e-08 ($68 $b1 $46 $68). Ce second nombre est bien trop petit par rapport au premier. Cette addition ne change rien... dans ce cas-ci. Nous verrons plus tard à quoi cette addition peut servir.
Troisième étape
ld a,e
ld e,c
xor a,$4f
ld c,a
Dans cette troisième étape, le générateur fait des mélanges. Les 8 bits de poids les plus faibles sont mis de côté et les 8 bits de poids fort sont placés dans les 8 bits de poids faible.
Les 8 bits mis de côté sont XORés avec b01001111. Ce qui signifie que certains bits sont inversés. Puis le résultat est placé dans les 8 bits de poids fort.
Cette opération ne me semble pas avoir de sens arithmétique. Cela semble être juste un mélange. Peut-être pour amener de l'entropie dans les bits de poids faible... Peut-être.
Résumé : cet étape mélange les parties de la mantisse et change quelques bits.
Le nombre est à présent 12501063 ($98 $3e $c0 $47).
Étape intermédiaire
ld (hl),$80
dec hl
ld b,(hl)
ld (hl),$80
Cette étape profite que HL pointe actuellement (depuis la récupération de FAC dans BCDE) sur l'octet après FAC pour préparer le terrain pour plus tard. Cet octet contient le complément à 1 du bit de signe du nombre de FAC. En mettant cet octet à $80, on force la valeur à être positive.
HL pointe ensuite sur l'octet précédent, l'exposant, et met celui-ci à $80, c'est-à-dire $2^ 0$ (voir l'article sur les nombres, toujours).
Résumé : le nombre final sera un nombre positif et l'exposant est fixé à $2^0 = 1$.
Pas d’influence, pour le moment sur le nombre tenu dans BCDE.
Quatrième étape*
ld hl,rnd_seed_0
inc (hl)
ld a,(hl)
sub a,$ab
jr nz,rnd_cnt
ld (hl),a
inc c
dec d
inc e
C'est la dernière étape du calcul. Dans la première partie, la seed 0 est incrémentée et récupérée dans A.
Si la soustraction par 171 ($ab) n'est pas nulle, on branche plus loin à l'étape finale. Sinon, le résultat (0) est replacé dans la seed 0. C'est donc un compteur jusqu'à 171 qui, lorsqu'il atteint cette valeur, modifie légèrement la mantisse.
Le premier et le troisième octets de la mantisse sont incrémentés, celui du milieu décrémenté, sans se soucier de débordements éventuels.
Résumé : une fois tous les 171 tirages, la mantisse est modifiée légèrement.
Comme ici, c'est le premier tirage, il ne se passe rien.
Étape finale
rnd_cnt: call bcde_norm
ld hl,rnd_gen
jp cpy_faclsb_hl
La mantisse a été générée, l'exposant est là. Mais tout nombre dans FAC en sorti de routine doit être normalisé.
Comme indiqué dans l'article précédent sur la représentation des nombres, cela signifie que la mantisse et l'exposant vont être modifiée afin d'obtenir une mantisse avec un premier bit à 1 implicite, lui-même remplacé par le bit de signe.
MAIS ! Il y a un twist ! La routine bcde_norm n'attend pas en entrée un nombre BCDE, mais une mantisse 32 bits CDEB. L'exposant du nombre actuel va donc se retrouver... en partie la moins significative du nombre, afin de nourrir, en quelque sorte, la partie droite de la mantisse lors de l'éventuel décalage vers la gauche.
C'est peut-être un peu obscure : je donne un exemple dans le résumé.
En sortie de normalisation, le nombre est bien dans FAC. Le contenu de FAC est alors copié à l'emplacement du dernier nombre généré.
C'est terminé !
Résumé : mise en forme du nombre, à la fois dans FAC comme résultat de la fonction, et de côté pour servir de base au prochain nombre généré (ou pour être retourné en case de RND(0)).
Nous en étions à $98 $3e $c0 $47. Mais la normalisation s'attend à une mantisse 32 bits, et c'est donc comme ça que va être perçue la mantisse : $3e $c0 $47 $98.
La normalisation doit déplacer la mantisse à gauche jusqu'à ce que le bit de poids fort soit à 1. Il va falloir deux étapes pour cela :
- de
$3ec04798à$7d808f30, puis - de
$7d808f30à$fb011e60
Comme le bit de poids fort du dernier octet n'est pas à 1, il n'y a pas d'arrondi. Cet octet est abandonné, le bit de signe et l'exposant corrigé par le nombre d'étapes ($80 - 2 donne $7e).
Au final, nous avons obtenu : $7e $7b $01 $1e, soit 0.245121
Suppléments
Re-seed
Si l'argument de RND() est négatif, alors un branchement a lieu sur une routine de réinitialisation du générateur.
reseed: ld (hl),a
dec hl
ld (hl),a
dec hl
ld (hl),a
jr afterreseed
À l'arrivée dans cette partie, HL pointe sur seed 2 et A est égal à $FF. Ce qui a pour résultat de mettre les trois octets à $FF.
Le branchement ramène dans le générateur à la fin de la seconde étape, c'est-à-dire après la multiplication et l'addition. Ce qui est dans FAC (l'argument négatif de RND()) est ramené dans BCDE et le reste des étapes est effectué.
C'est donc une nouvelle séquence qui démarre, dépendante de l'argument passé à RND().
Cas de l'addition
Revenons sur la seconde étape, l'addition avec un nombre tout petit. Dans l'exemple que nous avons suivi pendant l'article, l'addition ne servait à rien, car la différence entre les exposants était trop grand et donc le nombre à addition non significatif.
La question à se poser est donc : dans quels cas ces nombres deviennent-ils significatifs ?
Le plus petit d'entre eux est : $68 $46 $b1 $68 qui a pour exposant $68. C'est-à-dire $80 - 24.
Il faut donc un nombre strictement inférieur à $00 $00 $00 $80 (0.5) pour que l'addition soit intéressante.
Sauf que... juste avant l'addition, la multiplication a été faite avec un nombre dont l'exposant était au minimum $98. Puisque dans une multiplication, les exposants s'ajoutent, cela implique que seuls des nombres avec un exposants à '$68' initialement vont être assez petits après la multiplication et être modifiés par l'addition.
C'est quelque chose de facile à déclencher en modifiant à la main le dernier nombre généré en mémoire. Mais est-ce que cela se passe si on laisse le générateur se dérouler normalement ?
Un expérience simple avec un debuggeur en mettant un point d'arrêt dans le code d'addition et en faisant tourner le générateur montre que... non. Cela n'arrive pas. Ou alors assez rarement pour résister à l'expérience.
Il est temps de se poser la question des bornes maximales et minimales des nombres générés.
Mais vu la longueur de l'article, ce sera pour le prochain...