Exercices sur les appels de fonctions et les pointeurs en assembleur x86

De Ensiwiki
Aller à : navigation, rechercher
AttentionCette page est maintenue uniquement par les enseignants. Afin de ne pas perturber le déroulement des cours, elle n'a pas vocation à être modifiée par les élèves. Mais si vous avez des modifications à proposer, merci d'en discuter ou d'envoyer un e-mail aux auteurs de la page (cf. historique)

Laptop.png  Première Année  CDROM.png  Informatique 

Introduction

Le but de ces deux séances est de pratiquer la manipulation de structures et de pointeurs en assembleur : il est essentiel d'être à l'aise sur ses notions pour l'examen final.

Toutes les sources nécessaires à ce TP sont disponibles dans le répertoire asm/4-appels-fonctions/. Il n'y a volontairement pas de squelette.

Note : certaines versions même récentes de Valgrind ne supportent pas l'instruction enter que l'on utilise au début des fonctions écrites en assembleur. Si vous obtenez une erreur du genre vex x86->IR: unhandled instruction bytes: 0xC8 à l'exécution, vous pouvez remplacer la ligne enter $N, $0 par les trois lignes suivantes (où N est bien sûr à remplacer par la taille de la zone contenant les variables locales dans votre programme) :

pushl %ebp
movl %esp, %ebp
subl $N, %esp

Exercice préliminaire

Dans cet exercice, on va manipuler une structure de donnée simple définie par :

struct structure_t {
    int entier;
    int *ptr;
};

La spécification du langage C impose que les champs d'une structure soient placés dans la mémoire dans le même ordre que la définition de la structure. Cela signifie que si on définit une variable struct structure_t s et que cette variable se trouve placé en mémoire à l'adresse A, alors s.entier sera lui aussi à l'adresse A et s.ptr sera placé à l'adresse A + 4 (puisqu'un entier prend 4 octets en mémoire).

Le fichier struct.c contient les définitions de type et les fonctions utiles pour cet exercice. On souhaite traduire en assembleur (dans un fichier acces_struct.S) les deux fonctions suivantes :

void affichage(struct structure_t s)
{
    affiche(s.entier, s.ptr);
}

void modification(int entier,
                  int *ptr,
                  struct structure_t *s)
{
    s->entier = entier;
    s->ptr = ptr;
}

Ces fonctions s'écrivent en quelques lignes d'assembleur chacune, mais il est important de bien comprendre les accès mémoires, notamment les calculs à faire pour accéder aux champs de la structure.

On peut compiler le programme grâce à la commande :

gcc -m32 -g -gstabs -std=c99 -Wall -Wextra struct.c acces_struct.S -o struct

Sous MacOS, on doit rajouter l'option -mstackrealign.

Manipulation de listes chaînées

Dans cet exercice, on va manipuler des listes chainées de cellules définies par :

struct cellule_t {
    int val;
    struct cellule_t *suiv;
};

Le fichier listes.c fourni des fonctions de test qui vous seront utiles. On demande de traduire en assembleur dans un fichier decoupe.S la fonction suivante :

struct cellule_t *decoupe(struct cellule_t *l,
                          struct cellule_t **l1,
                          struct cellule_t **l2)
{
    struct cellule_t sent1, sent2;
    *l1 = &sent1;
    *l2 = &sent2;
    while (l != NULL) {
        if (l->val % 2 == 1) {
            (*l1)->suiv = l;
            *l1 = l;
        } else {
            (*l2)->suiv = l;
            *l2 = l;
        }
        l = l->suiv;
    }
    (*l1)->suiv = NULL;
    (*l2)->suiv = NULL;
    *l1 = sent1.suiv;
    *l2 = sent2.suiv;
    return l;
}

Cette fonction prend en entrée une liste chainée l et produit en sortie deux listes l1 et l2 composées respectivement des élèments impairs et pairs de l.

On peut compiler le programme grâce à la commande :

gcc -m32 -g -gstabs -std=c99 -Wall -Wextra listes.c decoupe.S -o listes

Sous MacOS, on doit rajouter l'option -mstackrealign.

Exercice de révision sur les tableaux

Attention : cet exercice n'est à commencer qu'une fois que vous avez fini et compris les exercices précédents sur les listes chainées.

Pour s'entrainer, on propose un exercice simple sur les tableaux : le tri du nain de jardin, dont on résume le principe.

Un nain de jardin souhaite trier des pots de fleurs par taille croissante en appliquant la stratégie suivante. Il regarde le pot devant lui :

  • s'il est plus petit que le pot à sa droite, le nain avance d'un pas vers la droite (s'il n'est pas arrivé à la fin de la file de pots) ;
  • si le pot devant lui est plus grand que le pot à sa droite, le nain échange les deux pots, et recule d'un pas vers la gauche (s'il n'est pas revenu au début de la file de pots).

En C, on peut implanter ce tri naïf comme suit :

void tri_nain(int tab[], unsigned taille)
{
    for (unsigned i = 0; i < taille - 1; ) {
        if (tab[i] > tab[i + 1]) {
            int tmp = tab[i]; tab[i] = tab[i + 1]; tab[i + 1] = tmp;
            if (i > 0) {
                i = i - 1;
            }
        } else {
            i = i + 1;
        }
    }
}

Traduisez de façon systématique cette fonction de tri en assembleur, dans un fichier nain.S. Le programme principal de test est fourni dans le fichier tri.c.

On remarque qu'on fait beaucoup d'accès mémoire redondants dans cette traduction systématique, et qu'il semble facile d'optimiser le tri en utilisant intelligemment les registres pour stocker des valeurs. Implantez dans le fichier nain.S une fonction tri_nain_opt en utilisant tous les registres disponibles (y compris les registres non-scratch) pour éviter autant que possible les accès mémoires.

On rappelle que les registres non-scratch doivent être sauvegardés avant d'être utilisés. Vous pourrez comparer les vitesses d'exécution des deux implantations assembleur en adaptant le fichier tri.c fourni.