Après ces chapitres sur l’utilisation de X11, nous allons
revenir à la programmation de quelques algorithmes de recherche de chemins tels
qu’ils sont présentés dans le livre déjà cité de Virginie MATHIVET aux éditions
ENI.
Tous les sources de ce projet sont à télécharger depuis ce répertoire
Tous les sources de ce projet sont à télécharger depuis ce répertoire
La transposition des programmes JAVA en assembleur ARM pose
quelques petits problèmes de réflexion (Oui je sais pour les fanas de langage
évolué, c’est du grand n’importe quoi !!) mais rien d’impossible. Nous
allons donc manipuler des tables, et des listes chainées ce qui nous permet
d’utiliser les registres comme pointeurs.
Pour pouvoir réutiliser ces algorithmes dans d’autres
programmes, j’ai décidé de les écrire dans des petits programmes sources
différents et d’utiliser l’utilitaire make pour compiler et linker l’ensemble
du projet. Comme cela j’ai découvert les subtilités de ce
programme !! Vous trouverez ici le
fichier des commandes pour ce projet et qu’il faudra lancer par make –f makefile.txt
sur le raspberry.
Remarque : il manque dans ces commandes, la
recompilation lorsque l’on a modifié uniquement un fichier d’include
(modification d’une constante ou d’une structure par exemple).
Le programme maitre est le programme lancer.s qui va
contenir la description des cartes, l’appel aux programmes de création des
structures de données puis les appels à chaque algorithme de recherche :
recherche en profondeur, en largeur, algorithme de Bellman-Ford, de Dijkstra et
A* (pour la théorie, je vous renvoie au livre en question ou à des articles sur
Internet).
Pour chaque algorithme, nous mesurerons le temps d’exécution
avec les procédures décrites dans les chapitres précédents de ce blog.
Le programme le plus important est le programme carte.s qui va
traduire la description de chaque carte en données exploitable par les
algorithmes. Chaque case de la carte est enregistrée dans une table composée d’une
structure Tuile. Ici, j’ai eu quelques difficultés pour associer les données d’un
nœud (nécessaires aux algorithmes) avec les données internes à la tuile. J’ai
donc crée une structure Tuile mais qui contient au début les données d’un Nœud.
Ceci permet de généraliser les algorithmes à d’autres problèmes de recherche.
Il suffira simplement de modifier (ou dédoubler) la structure pour adapter les
données internes au problème concerné
La taille des cartes étant très variable, la place nécessaire
sera réservée sur le tas. Pour cela une routine contenant l’appel système BREAK
sera ajouté au fichier des routines. Voici son code :
allocPlace:
push
{r1,lr} /* save des 2 registres */
push
{r2,r7} /* save des registres */
mov
r2,r0
mov
r0,#0 /* recuperation de l'adresse
du tas */
mov r7, #0x2D /* code de l'appel systeme
'brk' */
swi #0 /* appel systeme */
mov
r1,r0 @ save du début
add
r0,r2 @ reservation
place demandé
mov r7,
#0x2D /* code de l'appel
systeme 'brk' */
swi #0 /* appel systeme */
cmp
r0,#-1 @ erreur allocation
beq
100f
mov
r0,r1 @ retour adresse début
100:
pop {r2,r7}
pop
{r1,lr} /* fin procedure */
bx lr
Dans le programme carte.s, nous décodons les lignes de la
description de la carte et pour chaque case, nous créeons une tuile dans une
table avec le type, sa place et son cout.
Puis à partir de cette table, nous créons une liste chainée
de tous les nœuds et une liste chainée de tous les arcs, listes qui seront
utilisées par les algorithmes.
Chaque algorithme est codé dans un programme spécifique
suivant la description java du livre et en l’adaptant aux structures de données
crées dans le programme carte. La mise au point est un peu délicate compte tenu
du nombre de registres utilisés. A ce propos, le rôle de chaque registre dans
un programme comme celui-ci n’est pas toujours facile à déterminer. Faut-il
respecter par exemple les normes habituelles de passage des arguments aux
sous-routines ? si oui, cela oblige à faire des mouvements de registres à
registres si ceux-ci ne sont pas bien choisis. On s’aperçoit par exemple qu’il
faudrait utiliser les registres à partir de r4 pour les indices supérieurs de
boucle ou pour conserver les données principales du programme. Je n’ai pas
encore trouvé la bonne méthode pour ces attributions, ce qui entraine quelques
bizarreries dans mes programmes. Comme ici, une fonction qui n’utilise pas
comme paramètre d’entrée le registre r0 mais seulement r1 (indice de ligne dans
la table des tuiles) et r2 (indice de colonnes) ou alors le registre r10 qui
sert dans plusieurs routines !!!
Après corrections de nombreuses anomalies, le programme
donne les mêmes résultats pour les exemples du livre avec bien sûr des temps d’exécution
bien différents. L’algorithme de Bellman-Ford a un temps d’exécution anormal
par rapport aux autres. Il faut que j’analyse plus finement son comportement pour
voir s’il n’y a pas une erreur de programmation ou un mauvais choix de la
structure des données.
Exercices : lire
la description d’une carte à partir d’un fichier dont on passe le nom en paramètre.
Le
départ de plusieurs algorithmes est toujours la case 0,0. Modifier les
algorithmes pour qu’ils commencent à la case départ donnée par la structure
graphe.
Adapter les algorithmes à d’autres
problèmes.
