Récursivité en arm

[Rockleader]

Hello,


j'ai un problème assez simple d'un point de vue algorithmique, mais que je n'arrive pas à coder correctement.


Il s'agit de faire récursivement la somme des éléments d'un tableau en arm

En supposant que le tableau se termine par une constante connu (disons -1) , c'est assez simple à réaliser en itératif. Par contre pour passer à la récursivité j'ai du mal; à chaque fois que l'on va rappeler le sous programme on va de nouveau empiler, et j'ai du mal à suivre le processus. Je pensais m'inspirer de fonction plus connu comme la factorielle mais j'ai pas trouvé de code arm le faisant x)

[Zorro_X]

je ne sais pas coder en arm, mais la fonction récursive serait quelque chose du genre :

Code: Tout sélectionner

somme(tableau,taille,element_courant)
{
   si(element_courant < taille )  // condition d'arrêt de la récursivité
   {
      // tu renvoies l'élément courant + l'adition des éléments restants :
      renvoyer tableau[element_courant] + somme(tableau, taille, element_courrant+1);
   }
   sinon
   {
       renvoyer 0;
   }
}

[Rockleader]

je ne sais pas coder en arm, mais la fonction récursive serait quelque chose du genre :

Code: Tout sélectionner

somme(tableau,taille,element_courant)
{
   si(element_courant < taille )  // condition d'arrêt de la récursivité
   {
      // tu renvoies l'élément courant + l'adition des éléments restants :
      renvoyer tableau[element_courant] + somme(tableau, taille, element_courrant+1);
   }
   sinon
   {
       renvoyer 0;
   }
}

J'avais déjà l'algo Mais merci quand même^^

[fatal_error]

je connais pas l'arm mais si tu as des fonctions c'est évident.
Si tu as pas de fonctions, tu peux toujours faire des goto...qui simulent le corps d'une fonction, et de fait, tu gères toi même ta pile d'appel+context.

Le passage du récursif à l'itératif se fait assez facilement,

Code: Tout sélectionner

int count(n){
 if (n==0){return 0}
 return 1+count(n-1)
}

donne quelque chose du style

Code: Tout sélectionner

globalCount = 0
globalStack //initialize stack properly
label: count
 n = globalStack.pop //pop is removing last added element
 if n==0
   goto finished
 globalCount +=1
 globalStack.push n-1 //store parameters to explore
 goto count

grossierement tu peux très bien imaginer globalStack un tableau de la taille de ton ...tableau
et une variable z qui compte la taille utilisée de ton tableau.
.push equivaut à ajouter un element (ici element c'est un int, mais tu pourrais imaginer que c'est un contexte (idem une liste de paramètres) a z+1, puis faire z++
.pop equivaut à retourner lelement à z, et faire z--
(dans les grandes lignes juste faire gaffe aux index)

c'est pas très générique, mais ca devrait faire son taff pour ton problème
(c'est pas générique, parce que on a pas besoin de sauvegarder le contexte de la fonction (idem on attend pas le retour de la fonction qu'on appèle), ya un nom quand tu fais l'appel récursif dans le return, mais j'ai oublié...)

[Rockleader]

Ya tellement d'arm différent je pense qu'on parle pas du même

Pour ma part, je n'ai pas la possibilité d'utiliser des fonction, autre que les opérateurs basiques style ADD pour faire une addition, MOV pour placer une valeur dans un registre; les instruction pour empiler et dépiler et chargé des valeurs de tableau.




Si j'avais du le faire en itératif (je fais du code à la va vite surement pas tout à fait juste mais c'est l'idée) Je mets des comm à chaque ligne

Code: Tout sélectionner

mov r0,#0 @r0 sera la somme
mov r1,#0 @r1 compteur
tq: cmp r1,#N @je suppose N taille du tableau défini
     beq FINtq @ si c'est égal tableau fini
      @ sinon
     ldrb r3,tab[r1]   @ r3 = tab[cpt]
     add r0,r0,r3 @ on incrémente la somme
     add r1,r1,#1 @on incrémente le compteur
     btq  @ on repart sur la boucle
FINtq: On sort du sous programme avec la somme dans r0

Sa c'est la version itérative basique; mais en récursif je vois pas trop comment on faire faire pour le coup...pas niveau algo mais niveau codage, parce que à chaque fois qu'on va rappeler notre fonction, notre nouvelle somme va s'empiler pour le passage suivant...mais à la fin il faudra bien dépiler et au final je crois qu'on va retomber sur somme = 0.

[Zorro_X]

Bah, ce qu'ils veulent te faire faire dans l'exercice c'est utiliser les "call" et les "ret" (return) ainsi que dépiler les paramètres de la pile (suite à un call) pour récupérer un état...
Compile une fonction bête avec un ou deux paramètres qui ne fait pas grand chose et regarde le code assembleur, tu verras comment ca fonctionne.
Après, si t'as pas les call/ret je ne vois pas comment tu peux faire du "récursif" en assembleur (??)

Edit : réflexion faite, si, tu peux simuler un call et un ret en utilisant le registre de pile et le registre d'instruction, le tout en ne faisant que du "mov", en utilisant les bonnes adresses... ;) Là tu risques de t'amuser un petit peu !

[Rockleader]

Edit : réflexion faite, si, tu peux simuler un call et un ret en utilisant le registre de pile et le registre d'instruction, le tout en ne faisant que du "mov", en utilisant les bonnes adresses... Là tu risques de t'amuser un petit peu

C'est l'idée, je me suis déjà servi du registre de pile r13 pour faire passer tout un tas de paramètres, mais ça se limitait à une fonction
Là la fonction se rappelle elle même, et je commence à être perdu avec mon pointeur de pile ^^

[Zorro_X]

Ca remonte un peu loin tout ça pour moi et l'assembleur n'est pas ma façon de coder préférée, mais si mes souvenirs sont bons :
call :
1) ajouter l'adresse suivante du pointeur d'instruction dans la pile ;
2) ajouter les paramètres dans la pile, un à un ;
3) changer l'adresse du pointeur d'instruction vers celle du point d'entrée dans la fonction ;

Puis dans la fonction :
1) accéder aux paramètres directement dans la pile, sans les dépiler ;
2) dérouler le code de la fonction ;

Enfin, le return fait le ménage :
1) dépiler les paramètres ;
2) dépiler l'adresse de retour (en la mettant dans un autre registre par exemple) ;
2bis) placer la valeur de retour dans un registre particulier réservé à cet usage ;
3) changer l'adresse du pointeur d'instruction vers celle de retour.

Après, c'est à toi de trouver les mov et les registres qu'il faut utiliser, surtout pour les opérations "empiler" et "dépiler", le reste, ca devrait aller tout seul... ;)

[fatal_error]

mais à la fin il faudra bien dépiler et au final je crois qu'on va retomber sur somme = 0.

(c'est pas générique, parce que on a pas besoin de sauvegarder le contexte de la fonction (idem on attend pas le retour de la fonction qu'on appèle), ya un nom quand tu fais l'appel récursif dans le return, mais j'ai oublié...)

ben c'est complement stupide de dépiler dans la mesure ou tu as pas besoin de revenir dans ta fonction appelante!!!

si tu as un truc style

Code: Tout sélectionner

f(n){
 return f(n-1)+f(n-2)
}

ok une fois que tu as calculé f(n-1) tu dois revenir pour calculer f(n-2)
mais quand t'as

Code: Tout sélectionner

f(n){
 return 1+f(n-1) ben t'as pas besoin de revenir....
}

à la rigueur, si tu avais

Code: Tout sélectionner

f(n){
 return f(n-1) + 1 //...ben si t'es teubé, tu calcules f(n-1) d'abord puis tu reviens pour ajouter 1 XD
}


donc pour la théorie, ce que tu fais, c'est
lors du call de f (avant pour etre précis)
tu stores toutes les variables nécessaires dans un context.
tu appeles f
...
tu restores tes variables, et tu termines f

jte ferais pas le code en arm, parce que cam fout la gerbe l'assembleur, mais tu peux t'en sortir ainsi (même si je me répète récursiver sur l'enveloppe, ca sert à rien)

[Rockleader]

Ce que je veux dire, il faut bien dépiler le contexte de la fonction pour revenir dans le main à la fin. Donc on est obligé de dépiler, mais il ne faut dépiler qu'à la fin. C'est là que c'est tordu =)


Enfin bref, c'est chiant l'arm :mur:

Parait que c'est avec ça que sont codé la plupart des programmes des smartphones --' vive la galère =)

[Zorro_X]

bah !? dépiler c'est juste décrémenter le registre de la pile (!)