* * *
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