* * *
Programmation : Assembleur 68030
* * *

Récursivité


 Puisque l'initiation au 68030 est terminé, nous allons voir une technique de programmation très puissante et simple à mettre en oeuvre. La récursivité, c'est la possibilité que certain sous- programme puisse s'appeler eux même. Pour les matheux, la plus célèbre fonction récursive est factorielle. Factorielle est définie comme suit :

Fact(0)=1
Fact(1)=1
Fact(n)=fact(n-1)*n

pour n différent de 0 et 1


 Pour les non matheux, cette définition peut sembler assez barbare. Imaginez que nous voulions calculer factorielle de 4, et bien on commence par calculer factorielle de 3 (n_courant-1) que l'on va multiplier par 4 (n_courant). Mais comment calculer factorielle de 3? Et bien c'est très simple, on applique encore la formule : fact(3)=fact(2)*3, encore un pas et on arrive à fact(2)=fact(1)*2. Et là, on recommence? Oui, mais comme fact(1) est connu (égal à 1), et bien on le remplace par 1 et l'on "remonte" sa valeur d'un pas en arrière : fact(2)=1*2=2. De même pour fact(3)=2*3=6, et fact(4)=6*4=24.

 C'est comme ça que marche tous les algorithme récursif : pour calculer un pas, on a besoin des pas précédents, et pour les calculer, on rappel l'algorithme. Il y a bien sur toujours des cas d'arrêts (fact(0)=1 et fact(1)=1 dans le cas de factorielle). Mais tout ceci ne nous dit pas comment coder cet algorithme. Voyons de quoi nous avons besoin :

  - il faut passer des paramètres à la fonction appelée, et pouvoir en recevoir, quelque soit le pas d'exécution.

  - il faut qu'un appel du sous-programme ne modifie pas les variables qui nous sont utiles à un pas donné de l'exécution (par exemple la valeur de n dans l'exemple de factoriel)

 Mais comment faire tout ça à la fois? Et bien la solution vient de la pile! Et oui, notre chère pile va nous servir à stocker les paramètres importants de notre algorithme. Ainsi à chaque appel récursif, on sauve sur la pile les paramètres importants avant l'appel, on exécute le sous- programme, puis on récupère les paramètres de la pile. Il faut aussi veillez aux registres qui sont modifiés dans le sous-programme, ainsi que des variables globales.

 Le premier programme d'exemple permet justement de calculer la factoriel d'un nombre. Le voici :

* routine récursive de calcul de
* factoriel
* par Golio Junior pour Falk'mag 6


section TEXT

move.l #10,d0

bsr fact

* retour système
move.w #0,-(sp)
trap #1

* fonction qui calcul factoriel de
* manière récursive
* entrée :
* d0.l : factoriel à calculer
* sortie :
* d1.l : résultat de la factoriel

fact
tst.l d0
* factoriel de 0?
bne fact_s1
* non alors on
* continue
move.l #1,d1
* oui, alors c'est
* égal à 1
rts
fact_s1

cmp.l #1,d0
* factoriel de 1?
bne fact_s2
* non alors on
* continue
move.l #1,d1
* oui, alors c'est
* égal à 1
rts
fact_s2
move.l d0,-(sp)
* on calcul
* factoriel de d0-1
* donc on sauve d0
subq.l #1,d0
* d0=d0-1
bsr fact
* calcul de la
* factoriel
* d1 contient la
* factoriel de d0-1
move.l (sp)+,d0
* récupération de d0
mulu.l d0,d1
* calcul de
* factoriel d0
rts

 Ainsi le sous-programme fact calcul la factorielle d'un nombre contenu dans d0. Le résultat de fact est dans d1. Dans le sous programme, on commence par tester si d0 (n) vaut 0 ou 1, si c'est le cas, le résultat est 1 (donc d1=1). Par contre, il faut calculer factorielle de n-1. Mais attention, il faut conserver la valeur de n, donc il faut sauver d0 sur la pile. Après l'appel de fact, d1 contient la factorielle de d0-1, il faut donc multiplier d1 par d0 (celui qui est restauré).

 Un autre exemple de récursivité? Oui! Cette fois-ci on va s'attaquer au remplissage de surface, grâce à l'algorithme de germe. Cet algorithme permet de remplir des surfaces quelconques et il est très utilisée dans les logiciels de dessin : le fameux outil pot de peinture, qui permet de colorier des surfaces. Le principe est le suivant : on regarde si le point courant est à colorier, si oui, on le colorie et on regarde si les 4 voisins sont à colorier. Pour regarder si les 4 voisins sont à colorier, et bien on rappel le même sous-programme de manière récursive. Regardons les points important de cet algorithme :


  - pourvoir stocker les coordonnées du point courant (ou plutôt son adresse).
 - conserver la couleur de la surface que l'on colorie.

 Ce dernier point ne pose pas de problème, car la nature de l'algorithme impose que cette valeur ne va pas être modifiée, il va donc être inutile de la sauvegarder sur la pile. Par contre, elle doit être initialisée avant le premier appel du sous-programme récursif. Les coordonnées, ou plutôt l'adresse devront être sauvegardées sur la pile. Le programme d'exemple (rempliss.s) fonctionne en True Color, et donc un point est stocké sur 16 bits continus. La structure utilisée est la même que la structure des programmes de tracer de lignes, polygones et affichage de sprite (cf. PFM 8-9), donc pas de commentaire particulier. Le listing est le suivant :

* remplissage de surface grâce à un
* germe
* par Golio Junior pour Falk'mag 6

* Définition de l'image
Video_mode equ %000100100
* 40 col, 200 lig, 65536 cou, TV Pal
Taille_ecran equ 320*200*2
ecran_largeur equ 320
ecran_hauteur equ 200
Pas_Fond equ 1
Fond_offset equ 128

include "principa.s"

prg_init
clr.w couleur
* couleur de remplissage
rts

prg
move.l adr_ecran,a0
* adresse écran
adda.l
#(117*ecran_largeur+89)*2,a0
* adresse du germe de
* remplissage
move.w (a0),d0
* d0 : couleur de la
* surface à colorier
move.w couleur,d1
* d1 : couleur de
* remplissage
bsr remplir
* coloriage !

add.w #%0001000001000011,couleur
* passage à la couleur
* suivante
and.w #%1111111111011111,couleur
rts

remplir
cmp.w (a0),d0
* le point courant est-il
* à colorier?
bne pas_exploration
* non alors c'est fini!
move.w d1,(a0)
* sinon on le colorie

move.l a0,-(sp)
* sauvegarde de l'adresse
* du point courant
lea (a0,2),a0
* point à droite
bsr remplir
* coloriage
move.l (sp)+,a0
* récupération de
* l'adresse du point
* courant

move.l a0,-(sp)
* ....
lea (a0,-2),a0
* point à gauche
bsr remplir
move.l (sp)+,a0

move.l a0,-(sp)
* ....
lea (a0,ecran_largeur*2),a0
* point en bas
bsr remplir
move.l (sp)+,a0

move.l a0,-(sp)
* ....
lea (a0,-ecran_largeur*2),a0
* point en haut
bsr remplir
move.l (sp)+,a0

pas_exploration
rts

section DATA
Fond incbin "68030.tpi"
* fond d'écran

section BSS
couleur ds.w 1
* couleur de remplissage

include "principh.s"

 Et voilà la fin de ce court article sur la récursivité. J'espère ne pas avoir été trop théorique, mais le sujet est assez difficile.
Bon code et bonne lecture !




Golio Junior