
Programmation : assembleur 68030

Champs de bits
On va voir l'un des nouveaux ensembles d'instruction sur le 68030. Il
s'agit d'instruction de manipulation de champ de bits. Un champ de bits est
une suite de bits, très grande (de l'ordre du 2 milliard de bits (soit 256
Mo)). Et l'on peut faire a peut près n'importe quoi avec ces champs :
recherche de bits à 1, test, insertion, extraction. L'intérêt de ces champs
de bits ce que l'on peut accéder à un bit donné sans connaître l'adresse de
l'octet qui le contient.
Un champ de bits est représenté en mémoire par une suite d'octets
contigues. Pour définir un champ de bits, il faut fournir son adresse de
départ, un déplacement et sa taille. Cette adresse peut-être définie grâce à
un registre d'adresse (syntaxe : (An)), un des modes indexés ( (d16,An),
(d8,An,Xn), (bd,An,Xn), ...), une adresse immédiate (sur 16 ou 32 bit), ou
encore le champ de bits peut-être contenu dans un registre de donnée. Le
déplacement dans un champ de bits permet de repérer le premier bit de ce
champ. La taille du champ (sa largeur) correspond au nombre de bits modifiés
par l'instruction. Cette largeur est de taille maximum de 32 bits. La
définition d'un champ de bits à l'allure suivante :
<ae>{déplacement:largeur}
Avec ae, l'adresse du champ de bits, déplacement qui peut-être un valeur
immédiate (comprise entre 0 et 31), ou un registre (compris entre -2^31 à
2^31-1), et largeur qui peut-être une valeur immédiate (comprise entre 0 et
31 (valeur 0 : 32 bits de large, de 1 à 31 : de 1 à 31 bits de large)), ou
un registre de donnée; dans ce cas, il faut prendre la valeur du registre
modulo 32 pour obtenir la largeur effective.
Bon commençons par la première instruction (dans l'ordre alphabétique!) de
manipulation de champ de bits :
BFCHG <ae>{déplacement:largeur}
Cette instruction permet de tester et d'inverser un champ de bits. Les
résultats d'un test de champ de bits est le suivant :
N : à 1 si le bits le plus fort (le premier du champ) est à 1 (nombre
négatif)
Z : à 1 si tous les bits du champ sont à 0
Les autres flags ne sont pas affectés. Instruction suivante :
BFCLR <ae>{déplacement:largeur}
Cette instruction test et met à 0 tous les bits du champ défini. Le
résultat du test est identique à l'instruction BFCHG.
BFEXTS <ae>{déplacement:largeur},Dn
Cette instruction permet d'extraire d'un champ de bits un certain nombre
de bits et d'étendre sur 32 bits par le signe. Imaginez que vous vouliez
prendre le nombre signé sur 17 bits placé dans le champ de bits au
déplacement 20. L'instruction réalisant cette prouesse est :
BFEXTS Champ{20,17},d0
Et voilà dans d0 ce nombre sur 17 bits étendu par signe à 32 bits. Si
l'extension par signe ne vous intéresse pas, il vous suffit d'utiliser
l'instruction BFEXTU, qui réalise la même opération que BFEXTS, mais sans
l'extension de signe (Rm. : dans BFEXTU, les bits restant à gauche sont mis
à 0). Une autre instruction intéressante :
BFFFO <ae>{déplacement:largeur},Dn
Cette instruction recherche dans le champ de bits le premier bit à 1 de ce
champ (premier bit en partant des bits de poids forts). Si il y a un bit à 1
dans ce champ, alors le bit Z est à 0, et Dn contient le déplacement ou se
trouve ce bit. Si Z est à 1, alors tous les bits du champ sont à 0, et Dn ne
contient pas de déplacement vers un bit à 1. Nous verrons l'intérêt de cette
instruction dans l'exemple sur le crible d'Eratosthène.
BFINS Dn,<ae>{déplacement:largeur}
Cette instruction permet d'insérer une chaîne de bits dans un champ de
bits. Imaginez que votre nombre sur 17 bits qui se situe au déplacement 20
de votre champs de bits doit-être remplacé par le contenu de D0 (les 17 bits
de poid faible de D0), et bien l'instruction miracle est :
BFINS d0,Champ{20,17}
Nous verrons un exemple plus complet dans l'affichage de sprites.
BFEST
Test d'un champ de bits et mise à 1 (c'est le complémentaire de BFCLR).
Pour plus de détail sur cette instruction voir BFCLR.
BFTST
Test d'un champ de bits. Même remarque que précédemment.
Et voilà c'est toutes les instruction de manipulation de champ de bits.
Nous allons voir maintenant un premier exemple d'utilisation : le crible
d'Eratosthène. Cet algorithme permet de connaître les nombres premiers
(nombres divisible uniquement par 1 et par eux-même (exp. : 1, 2, 3, 5, ...)
compris entre 1 et un certain nombre. Le principe est le suivant : pour
chaque nombre supérieur à 1, on élimine tous ces multiples, qui ne seront
donc pas des nombres premiers. A la fin, tous les nombres premiers sont les
nombres qui ne sont pas éliminée. Mais quel est le rapport avec les champs
de bits? Et bien un nombre posséde deux état : éliminé ou pas (0/1). Donc
cette information peut-être codé sur un bit! Et voilà les champs de bits.
Voici un extrait du source (eratosth.s):
era_crible
lea crible,a0
moveq.l #2,d0 * module de départ
* il vaut commencer par 2, car tous les
* nombres sont des multiples de 1
* (x=x*1 : 1 : élément neutre pour la
* multiplication)
era_crible_b1
move.l d0,d1 * mise à 2*module de l'accu
lsl.l #1,d1 * car, un nombre est toujours multiple de lui même
era_crible_b2
bfclr (a0){d1:1} * la valeur de d1 n'est pas un nombre
* premier
* car elle est multiple de d0!
add.l d0,d1 * multiple suivant
cmp.l #VAL_MAX,d1
ble era_crible_b2
addq.l #1,d0 * nombre suivant
cmp.l #VAL_MAX,d0
ble era_crible_b1
rts
La boucle principal du programme n'est pas très compliqué, on commence par
initialisé le module de départ à 2. C'est le premier nombre premier (à part
1, mais lui pose problème). De plus le module est forcément multiple de 1,
donc, on commence a "cocher" les nombres qu'a partir du double du module
(d'ou le lsl.l #1,d1). Pour cocher un nombre, il suffit de mettre le bit qui
le représente (d'indice ce nombre) à 0. Lors de la recherche, on recherche
les bits qui sont à 1. Il faut faire attention à que lors de la recherche de
multiple, on ne dépasse pas la valeur maximal VAL_MAX. On passe d'un
multiple à l'autre en additionnant le module au multiple courant. Bon
maintenant l'extraction des nombres premiers :
extrait_crible
lea crible,a6
move.l #0,d6 * indice de début de la recherche
extrait_crible_b1
bfffo (a6){d6:32},d5
beq extrait_crible_s1
cmp.l #VAL_MAX,d5 * a t'on dépassé la valeur max?
bgt extrait_crible_s2 * oui, alors c'est fini !
* d5 : contient un nombre premier
* l'afficher !
bsr affd5
extrait_crible_s1
move.l d5,d6
addq.l #1,d6 * bit suivant, car celui-ci est déjà testé
cmp.l #VAL_MAX,d6 * on est rendu à la fin ?
ble extrait_crible_b1 * non alors, on continu!
extrait_crible_s2
rts
Pour rechercher les nombres premiers, et bien il suffit de rechercher les
bits qui sont restés à 1. Cette opération s'effectue grâce à l'instruction
bfffo qui travail sur une largeur de 32 bits (maximum) à partir du nombre
courant D6. Si l'on trouve un nombre premier correct (inférieur à VAL_MAX),
et bien on l'affiche (en décimal, s'il vous plait!) et on passe au nombre
suivant. On recommence la boucle de recherche tant la fin n'est pas
atteinte. Une manière d'optimiser est, lors du crible, de tester si le
module est un nombre premier (bftst), si non, ça ne sert à rien d'éliminer
tous ces multiples, car c'est déjà fait! Bon passons à une utilisation plus
visuel des instructions de manipulations de champs de bits :
Affichage de sprites
Le but de cet article n'est pas de faire des routines de sprites béton,
mais simplement l'utilisation des instructions de manipulation de champs de
bits. Donc on se limite au mode monochrome. Le choix du mode monochrome
n'est pas anodin, car la mémoire écran est alors comme un "vaste" champ de
bit. Les pixels sont rangés par ligne de 640 bits (pour une largeur de 80
colonnes), et les lignes se suivent. Ainsi pour trouver le pixels de
coordonnées (10,20), son rang dans le champ de bit est : 20*640+10. Si un
bit est à 1, alors le pixel correspondant est noir, si il est à 0, il est
blanc. Il y a deux méthodes de voir l'affichage de sprite dans ces
conditions : on lit un mot long en mémoire, et on l'affiche là ou il se
trouve, ou on lit le mots qui doit être affiché à la place courante.
Commençons par le première méthode (source : sprite1.s) :
movea.l adr_ecran,a0 * adresse du début de l'écran
move.l #pos_y,d0
mulu.w #ecran_largeur/8,d0 * adresse de début de la 1ère ligne
adda.l d0,a0 * dans a0
movea.l #sprite,a1 * adresse du sprite dans a1
move.w #hauteur-1,d0
prg_b1
move.w #largeur/32-1,d1 * affichage 32 bits par 32 bits
move.w #pos_x,d2 * premier pixel
prg_b2
move.l (a1)+,d7 * récupération des 32 bits à
* afficher
bfins d7,(a0){d2:32} * affichage !
add.l #32,d2 * pixels suivants
dbra d1,prg_b2
adda.l #ecran_largeur/8,a0 * passage à la ligne de l'écran
* suivante
dbra d0,prg_b1
rts
On commence par calculer l'adresse de la première ligne du sprite (largeur
de l'ecran en octet*pos_y). Ensuite pour chaque ligne du sprite, on
initialise notre déplacement par rapport au début de ligne (à pos_x). Pour
chaque mot long d'une ligne du sprite, on le lit (move.l (a1)+,d7), et on
l'affiche au bon endroit (bfins d7,(a0){d2:32}). Ensuite on passe au
déplacement suivant (add.l #32,d2). A la fin de la ligne, on passe à la
ligne écran suivante. Continuons avec la seconde méthode (source :
sprite2.s) :
movea.l adr_ecran,a0 * adresse du début de l'écran
move.l #pos_y,d0
mulu.w #ecran_largeur/8,d0 * adresse du premier pixel (au mot
* long pres)
add.w #(pos_x/32)*4,d0 * (pos_x/32 : No du mot long
* contenant les premiers pixels)
adda.l d0,a0 * dans a0
movea.l #sprite,a1 * adresse du sprite dans a1
move.w #hauteur-1,d0
prg_b1
* calcul du décalage
move.l #-(pos_x&31),d7
move.w #largeur/32-1,d1
prg_b2
bfextu (a1){d7:32},d6 * lecture du mot long à afficher
move.l d6,(a0)+ * affichage
add.l #32,d7 * pixels suivants
dbra d1,prg_b2
adda.l #ecran_largeur/8-largeur/8,a0 * passage à la ligne de
* l'écran suivante
adda.l #largeur/8,a1 * passage à la ligne du
* sprite suivante
dbra d0,prg_b1
Explicature : on commence par calculer l'adresse du mot long contenant le
premier pixel. Ensuite on calcul le décalage dans le sprite, c'est à dire le
déplacement qu'il faut faire pour que le 1er pixel soit correctement
affiché. Ce déplacement est de -(pos_x modulo 32) :
+ début du sprite
__¦____¦____¦____¦____¦ sprite
*
déplacement-+ *
*
¦____¦____¦____¦____¦ écran
^
+-- position en x du sprite
On voit clairement dans ce petit schéma, que le premier mot long qui va
être affiché contient des informations qui ne sont pas du sprite (les pos_x
modulo 32 premiers pixels). Une solution pour obtenir un affichage correct
est de prolonger le sprite d'un mot long à gauche. Mais attention ce mot
long ne fait pas partie du sprite, il ne faut donc pas l'afficher. Le reste
de la boucle est identique à la précédente, sauf que l'extraction de bit se
fait dans le sprite et l'affichage se fait brutalement dans la mémoire
écran.
En comparant ces deux méthodes, sur le plan algorithmique elle semblent
être aussi lente, sauf que la seconde est nettement plus rapide, pour la
simple raison que le nombre de cycle mémoire est nettement inférieur dans la
seconde. Pour faire une insertion de bits il faut lire un ou plusieurs
octets, les modifier et les réécrire. Par contre pour une extraction de bit,
il n'y a pas besoin de la dernière phase d'écriture. D'ou un gain de temps!
Bon je vous laisse rêver sur les innombrables possibilités de ces
instructions. Bonne code et A++
Golio Junior