CEP CTD Fonctions

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 cette séance est d'apprendre à programmer et appeler des fonctions en assembleur, et de comprendre les conventions de gestion des registres et de la mémoire imposées par le compilateur et la bibliothèque C que l'on utilise pour écrire nos programmes en assembleur. En respectant ces conventions, on verra qu'il est possible de mélanger du code C et assembleur sans difficulté dans le même programme.

Rappels de cours

Structure de la pile d'exécution d'un processus

Introduction

On a vu dans une séance précédente qu'un processus a une structure ressemblant au schéma suivant :

zone text
(code du programme)
zone data
(données statiques)
tas (heap)
(données dynamiques)
pile (stack)
(contexte d'exécution)

On a détaillé le contenu des zones text et data qui contiennent respectivement le code et les données statiques. Le tas est la zone dans laquelle les fonctions d'allocation dynamique de mémoire prennent l'espace mémoire à réserver : sa gestion interne sera détaillée dans le cours de système de 2A. On va étudier en détail dans cette séance la structuration de la dernière zone : la pile d'exécution.

Définition d'un cadre de pile

La pile est la zone mémoire contenant le contexte d'exécution des fonctions du programme. A chaque fois que le programme commence l'exécution d'une fonction, on doit mettre en place un cadre de pile (stack frame en anglais) qui contiendra notamment les variables locales de la fonction, les paramètres passés à la fonction, etc. Un cadre de pile a la structure suivante :

(sauvegardes)
variables locales
%ebp précédent
adresse de retour
paramètres

Dans ce schéma, les adresses sont croissantes vers le bas mais les valeurs sont empilées en haut car il s'agit d'une pile au sens algorithmique du terme. Les différentes zones sont détaillées ci-dessous :

  • les paramètres sont ceux passés à la fonction en cours d'exécution ;
  • l'adresse de retour est l'adresse de l'instruction suivant l'appel de la fonction en cours d'exécution dans la fonction appelante (i.e. c'est là qu'on revient quand on exécute return à la fin de la fonction) ;
  • le « %ebp précédent » est la sauvegarde du pointeur de base de la fonction appelante (on détaillera son rôle plus bas) ;
  • les variables locales de la fonction en cours d'exécution sont localisées dans son cadre de pile, à des adresses fixes par rapport à %ebp ;
  • on peut éventuellement utiliser de la place dans le cadre de pile pour sauvegarder des registres ou des valeurs temporaires si besoin.

Les pointeurs de pile

Le Pentium comprend 2 registres dont le rôle est lié à la pile d'exécution : %esp et %ebp.

%esp est le pointeur de pile : il contient en permanence l'adresse de la dernière case occupée dans la pile d'exécution. On ne le manipule pas directement en général pour éviter de risquer de déséquilibrer la pile.

%ebp est le pointeur de base : il contient l'adresse de la base du contexte d'exécution de la fonction en cours d'exécution. Dans notre cas, il pointera en permanence sur la case dans laquelle on a sauvegardé le %ebp précédent. On se sert de %ebp pour accéder aux variables locales et aux paramètres de la fonction en cours d'exécution, via un adressage indirect avec déplacement (e.g. -4(%ebp), 8(%ebp), etc.).

Appels de fonctions

L'instruction call permet d'appeler une fonction : on l'utilise en précisant l'étiquette correspondant au début de la fonction à appeler, par exemple call pgcd. Cette instruction a le même comportement qu'un branchement inconditionnel (jmp) mais en plus, elle empile automatiquement l'adresse de retour dans la pile d'exécution. L'adresse de retour est simplement l'adresse de l'instruction suivant le call dans la fonction appelante.

L'instruction réciproque s'appelle ret : elle dépile l'adresse de retour et revient donc à l'instruction suivant le call. C'est l'équivalent de l'instruction return qu'on a déjà vu en Ada et en C.

Comme on l'a déjà vu dans les exemples des séances précédentes, on renvoie par convention le résultat de la fonction dans le registre %eax. On ne traitera pas dans le cadre de ce cours le cas particulier des fonctions renvoyant une valeur de taille inférieure ou supérieure à 32 bits.

Mise en place du cadre de pile

Le cadre de pile d'une fonction est mis en place en deux temps :

  • dans la fonction appelante, qui copie les paramètres qu'elle va passer à la fonction appelée et empile l'adresse de retour en exécutant call ;
  • dans la fonction appelée, qui réserve la place nécessaire à son contexte d'exécution.

Lorsqu'on écrit le code d'une fonction, on commence par l'instruction enter qui a pour rôle de réserver l'espace nécessaire au contexte d'exécution. Jusqu'à présent, on l'a toujours utilisée sous la forme enter $0, $0 mais le premier paramètre sera en général différent de zéro, et précise justement le nombre d'octets à réserver pour le contexte (le deuxième paramètre sera toujours 0 dans notre cas). L'instruction enter $N, $0 est en fait équivalente à la suite d'instructions suivante :

subl $4, %esp
movl %ebp, (%esp)
movl %esp, %ebp
subl $N, %esp

Comme %esp pointe par convention sur la dernière case occupée, on doit commencer par le décrémenter de 4 avant de pouvoir sauvegarder %ebp dans la pile : c'est la sauvegarde du %ebp précédent dans le schéma du cadre de pile ci-dessus. Ensuite, on fait pointer %ebp sur la case où on a sauvegardé son ancienne valeur, et on décrémente %esp de N octets : c'est cette opération qui réserve la place nécessaire au cadre de pile. On rappelle que la pile « descend » vers les adresses décroissantes, d'où le fait qu'on effectue des soustractions.

L'instruction réciproque de enter s'appelle leave. Elle s'utilise sans paramètre et a pour effet de détruire le cadre de pile mis en place par enter. Elle est équivalente à la séquence d'instructions :

movl %ebp, %esp
movl (%esp), %ebp
addl $4, %esp

Elle commence par faire pointer %esp sur la case contenant l'ancienne valeur de %ebp : c'est comme cela qu'on détruit le cadre de pile (la mémoire n'est bien sûr pas « vidée » et contient toujours les valeurs précédentes, mais ces valeurs ne doivent plus être utilisées par le programme). Ensuite, on restaure l'ancienne valeur de %ebp en le dépilant.

Exemple

Soit par exemple la fonction suivante :

int plus(void)
{
    int a = 5;
    int b = 4;
    return a + b;
}

En assembleur, on écrira :

plus:
    // on precisera toujours la position dans la pile de chaque variable
    //   (pour faciliter la relecture du code !)
    //     int a : ebp - 4
    //     int b : ebp - 8
    // on doit reserver de la place pour 2 variables locales
    // chaque variable prend 4 octets (int), donc 8 octets au total
    enter $8, $0
    // a = 5
    movl $5, -4(%ebp)
    // b = 4
    movl $4, -8(%ebp)
    // calcul de a + b
    movl -4(%ebp), %eax
    addl -8(%ebp), %eax
fin_plus:
    // la valeur a renvoyer est bien dans %eax a ce point
    leave
    ret

L'ordre dans lequel les variables locales sont placées dans la pile est arbitraire : il faut juste toujours garder la même convention. Dans notre cas on les placera simplement dans l'ordre de déclaration.

Dans l'exemple ci-dessus, la pile est donc dans l'état suivant lorsqu'on arrive sur l'étiquette fin_plus :

b = 4
a = 5
%ebp précédent
adresse de retour

Les cadres de pile s'empilent les uns au dessus des autres lors des appels de fonction. Par exemple, si la fonction plus ci-dessus est appelée par la fonction main comme suit :

int main(void)
{
    int x = plus();
    return 0;
}

On écrira en assembleur :

main:
    // int x : ebp - 4
    // il y a une seule variable locale de type int
    enter $4, $0
    // appel a plus
    call plus
    // x = plus()
    movl %eax, -4(%ebp)
    leave
    // return 0
    movl $0, %eax
    ret

La pile sera dans l'état suivant lorsqu'on arrivera à l'étiquette fin_plus :

b = 4
a = 5
%ebp de main
adresse de retour à main
x = ?
%ebp du système
adresse de retour au système

La variable locale x n'a pas de valeur à ce moment-là car elle sera affectée dans main en revenant de l'appel à plus.

Passage de paramètres

Une fonction qui souhaite en appeler une autre en lui passant des paramètres doit les copier sur la pile avant d'exécuter l'instruction call.

Par exemple, si on modifie la fonction plus de l'exemple précédent pour qu'elle appelle une autre fonction affichant les valeurs à ajouter :

int plus(void)
{
    int a = 5;
    int b = 4;
    affichage(a, b);
    return a + b;
}

On va copier les valeurs de a et b dans la pile juste avant l'appel à la fonction affichage (il s'agit bien d'une copie, comme pour le passage de paramètres par copie du C).

On utilise pour ça l'instruction push, qui a pour effet d'empiler une valeur, c'est à dire :

  • de déplacer le pointeur de pile %esp qui pointe sur la dernière case occupée ;
  • de copier la valeur dans la case mémoire pointée maintenant par %esp.

Par exemple, pushl %eax est équivalent à :

subl $4, %esp
movl %eax, (%esp)

Le Pentium permet d'empiler des valeurs sur 16 ou 32 bits (pas des valeurs sur 8 bits). En pratique, on n'utilisera push qu'avec des valeurs sur 32 bits, pour respecter des contraintes d'alignement mémoire. On pourra donc écrire par exemple :

pushl %eax // empile le contenu du registre %eax
pushl $5 // empile la constante 5
pushl -4(%ebp) // empile le contenu d'une variable locale

On voit qu'il est possible d'empiler directement le contenu d'une variable (locale dans l'exemple, mais elle pourrait aussi être globale). L'instruction push est donc capable de faire des copies de mémoire à mémoire.

L'instruction réciproque s'appelle pop et elle permet de dépiler la valeur en sommet de pile. Par exemple, popl %eax est équivalent à :

movl (%esp), %eax
addl $4, %esp

Il est donc facile de copier sur la pile les paramètres à passer à une fonction en utilisant l'instruction push. Il faut cependant faire attention à l'ordre dans lequel on les copie : il faut respecter le même ordre dans la fonction appelante (qui copie les paramètres) et la fonction appelée (qui va les lire sur la pile). On utilisera la convention adoptée en C, où on copie les paramètres dans l'ordre des adresses croissantes : dans l'exemple de la fonction plus, on copiera donc a à l'adresse %ebp - 16 et b à l'adresse %ebp - 12.

Le code assembleur correspondant à la fonction plus sera donc :

plus:
    // int a : %ebp - 4
    // int b : %ebp - 8
    // 2 variables locales de 4 octets chacunes (int)
    enter $8, $0
    // a = 5
    movl $5, -4(%ebp)
    // b = 4
    movl $4, -8(%ebp)
    // affichage(a, b)
    pushl -8(%ebp)
    pushl -4(%ebp)
    call affichage
    addl $8, %esp
    // return a + b
    movl -4(%ebp), %eax
    addl -8(%ebp), %eax
    leave
    ret

Lorsqu'on entre dans la fonction affichage (juste après avoir effectué le call), la pile d'exécution sera donc dans l'état suivant :

%ebp de plus
adresse de retour à plus
param a = 5
param b = 4
b = 4
a = 5
%ebp de main
adresse de retour à main

On note l'instruction addl $8, %esp juste après le call affiche. En effet, il est important de maintenir l'équilibre de la pile en évitant d'y laisser des valeurs inutiles (dans le cas d'une fonction récursive par exemple, on pourrait rapidement arriver à saturer l'espace mémoire réservé pour la pile d'exécution). On doit donc dépiler les paramètres une fois l'appel à la fonction réalisé. On pourrait utiliser pop mais en pratique, on n'a pas besoin de récupérer les valeurs empilées. On peut donc simplement déplacer le pointeur de pile pour le remettre à sa position avant les push : dans le cas de cet exemple, on a empilé deux paramètres de 4 octets chacun, donc il suffit d'ajouter 8 à %esp.

Récupération de paramètres

Réciproquement, dans la fonction appelée, on va accéder aux paramètres passés par la fonction appelante dans la pile. Ces paramètres sont situés tout en bas du contexte d'exécution, « sous » la position actuelle de %ebp. Comme la pile se remplit vers les adresses décroissantes, cela signifie qu'on va récupérer les paramètres à l'aide d'un déplacement positif par rapport à %ebp.

Entre la position actuelle de %ebp et le premier paramètre, il ne faut pas oublier que l'instruction call a placé l'adresse de retour à la fonction appelante. Le premier paramètre est donc situé à l'adresse %ebp + 8 (et pas + 4).

Par exemple, si on modifie la fonction plus de façon à ce qu'elle fasse la somme de ses paramètres :

int plus(int a, int b)
{
    return a + b;
}

Le code assembleur correspondant sera :

plus:
    // pas de variable locale
    enter $0, $0
    // calcul de a + b
    // on recupere la valeur de a dans %eax
    movl 8(%ebp), %eax
    // on ajoute la valeur de b a %eax
    addl 12(%ebp), %eax
    // la valeur a renvoyer est bien dans %eax a ce point
fin_plus:
    leave
    ret

Interaction avec le langage C

On écrit très rarement des programmes entièrement en assembleur : en général, un programme sera composé de fonctions C et assembleur s'appelant les unes les autres. Il est donc important de respecter les mêmes conventions que le compilateur C lorsqu'on écrit du code assembleur devant interagir avec du code C.

Gestion des registres

Le compilateur GCC classe les registres généraux du processeur dans 2 catégories :

  • les registres scratch sont des registres « de calcul » qui peuvent être utilisés librement dans les fonctions en assembleur ;
  • les registres non-scratch sont des registres « précieux » dans lesquels le compilateur peut stocker des valeurs importantes.

Sur Pentium :

  • les registres scratch sont %eax, %edx et %ecx ;
  • les registres non-scratch sont %ebx, %esi et %edi.

Il s'agit d'une convention arbitraire : on doit cependant la prendre en compte lorsqu'on veut interagir avec du code généré par GCC.

Appel d'une fonction assembleur depuis une fonction C

Sans le savoir, on a toujours écrit du code assembleur appelé depuis une fonction C. En effet, lors de la création du binaire final, le compilateur a lié le programme avec un module (appelé crt0) dont le rôle est de préparer l'exécution du programme et qui se termine par un appel à la fonction main (en pratique on ne revient jamais de cet appel).

Pour appeler une fonction écrite en assembleur depuis du code écrit en C, on doit :

  • respecter la convention de pile présentée dans la première partie, notamment en ce qui concerne la gestion des paramètres ;
  • respecter la convention de gestion des registres, et plus précisément :
    • la fonction en assembleur ne doit pas modifier le contenu des registres non-scratch avant de les avoir sauvegardé : en effet, la fonction C appelante a pu laisser des valeurs importantes dans ces registres, et s'attend à les retrouver au retour de la fonction assembleur ;
    • la fonction en assembleur peut utiliser sans restriction les registres scratch ;
  • respecter la convention de nommage des fonctions, qui dépend du système utilisé : sous Linux les fonctions en assembleur sont nommées de la même façon que les fonctions en C ;
  • rendre visible le prototype de la fonction assembleur là où elle est appelée dans le programme en C et rendre public (avec la directive .globl) le point d'entrée de la fonction assembleur.

Par exemple, si on écrit une fonction main en C qui appelle la fonction plus renvoyant la somme de ces paramètres, on écrira en C :

#include <stdio.h>

// prototype de la fonction ecrite en assembleur
int plus(int, int);

int main(void)
{
    int a = 5;
    int b = 4;
    int x = plus(a, b);
    printf("La somme vaut %d\n", x);
    return 0;
}

et en assembleur, on pourrait écrire :

    .globl plus
plus:
    // pas de variable locale
    enter $0, $0
    // sauvegarde du registre non-scratch %edi
    pushl %edi
    // calcul de a + b
    // on recupere la valeur de a dans %edi
    movl 8(%ebp), %edi
    // on ajoute la valeur de b a %edi
    addl 12(%ebp), %edi
    // on doit renvoyer la somme dans %eax
    movl %edi, %eax
    // restauration du registre %edi
    popl %edi
    leave
    ret

Dans ce code, on utilise le registre non-scratch %edi pour faire le calcul : il s'agit d'un exemple purement scolaire pour illustrer la sauvegarde d'un registre non-scratch car en pratique on aurait pu utiliser n'importe-quel registre scratch.

Appel d'une fonction C depuis une fonction assembleur

On peut avoir besoin d'appeler une fonction C depuis du code assembleur (cas beaucoup moins fréquent que la réciproque en pratique). Ce cas est délicat car il impose de respecter des conventions très différentes d'un système à l'autre. On a choisi ici de respecter la convention utilisé sous Linux.

Pour appeler une fonction écrite en C depuis de l'assembleur, on doit donc :

  • respecter la convention de pile présentée dans la première partie, notamment en ce qui concerne la gestion des paramètres ;
  • respecter la convention de gestion des registres, et plus précisément :
    • la fonction en assembleur ne doit pas laisser de valeurs importantes dans les registres scratch sans les sauvegarder avant d'appeler la fonction C : en effet, l'appel à la fonction C pourrait parfaitement détruire le contenu de ces registres, car GCC considère qu'il peut s'en servir comme bon lui semble ;
    • la fonction en assembleur peut par contre laisser des valeurs importantes dans les registres non-scratch car on est sur qu'ils ne seront pas modifiés par l'appel à la fonction C ;
  • respecter la convention de nommage des fonctions, qui dépend du système utilisé : sous Linux on peut appeler directement la fonction C fct grâce à call fct.

Par exemple, si on écrit une version de la fonction plus qui effectue un affichage de la somme effectuée et qu'on suppose la fonction affiche écrite en C :

#include <stdio.h>

void affiche(int z)
{
    printf("La somme vaut %d\n", z);
}

int plus(void)
{
    int a = 5;
    int b = 4;
    affiche(a + b);
    return a + b;
}

On pourrait écrire plus en assembleur comme suit :

    .globl plus
plus:
    // int a : %ebp - 4
    // int b : %ebp - 8
    // 2 variables locales de 4 octets chacunes (int)
    enter $8, $0
    // a = 5
    movl $5, -4(%ebp)
    // b = 4
    movl $4, -8(%ebp)
    // calcul de a + b
    movl -4(%ebp), %eax
    addl -8(%ebp), %eax
    // affiche(a + b)
    pushl %eax
    call affiche
    addl $4, %esp
    // return a + b
    movl -4(%ebp), %eax
    addl -8(%ebp), %eax
    leave
    ret

Exemples détaillés

Pour chacun des exemples ci-dessous, vous écrirez aussi un programme principal en C qui appelle la fonction assembleur et affiche son résultat, par exemple sur le modèle suivant pour le PGCD :

#include <stdio.h>

unsigned pgcd(unsigned, unsigned);

int main(void)
{
    printf("%u\n", pgcd(15, 10));
    return 0;
}

Pour mettre au point vos programmes, vous aurez besoin de savoir afficher le contenu des variables locales et des paramètres des fonctions. Cela peut se faire facilement en :

  • affichant l'adresse de base du cadre de pile, c'est à dire simplement le contenu du registre $ebp : la commande GDB i r $ebp donne cette information ;
  • affichant la contenu de la mémoire à l'adresse voulue : par exemple, si on veut afficher la valeur du premier paramètre d'une fonction, de type int, et que le contenu de %ebp est 0xffffdaf8, on doit afficher le mot de 32 bits à l'adresse 0xffffdb00 (%ebp + 8), par exemple avec la commande display /xw (int)0xffffdb00.

Vous compilerez vos programmes avec (par exemple pour le PGCD ci-dessous), la commande suivante : gcc -Wall -Wextra -std=c99 -m32 -g pgcd.c pgcd.s -o pgcd. Note : si vous oubliez le -m32, vous obtiendrez vraisemblablement une erreur dès le enter au début de la fonction.

PGCD

Ecrire le code assembleur correspondant à la fonction PGCD ci-dessous :

unsigned pgcd(unsigned a, unsigned b)
{
    while (a != b) {
        if (a > b) {
            a = a - b;
        } else {
            b = b - a;
        }
    }
    return a;
}

Multiplication

Ecrire en assembleur la fonction de multiplication simple ci-dessous :

unsigned mult(unsigned x, unsigned y);
{
    unsigned res = 0;
    while (y != 0) {
        res = res + x;
        y--;
    }
    return res;
}

Suite de Fibonacci

Ecrire en assembleur la fonction récursive ci-dessous :

unsigned fibo(unsigned n);
{
    if (n == 0) {
        return 0;
    } else if (n == 1) {
        return 1;
    } else {
        return fibo(n - 1) + fibo(n - 2);
    }
}

Vous la testerez sur différentes valeurs en comparant avec la définition sur wikipedia.

Exercices

Dans tous les exercices ci-dessous, on vous demande de réaliser une traduction systématique du code C vers l'assembleur, c'est à dire sans chercher à optimiser votre code, par exemple en remplaçant des variables par des registres. On vous demande donc de manipuler les variables locales et les paramètres des fonctions directement dans la pile d'exécution.

Première fonction

Copiez-collez dans un fichier age.c le programme principal suivant :

#include <stdio.h>

unsigned age(unsigned);

int main(void)
{
    printf("En quelle annee etes-vous ne(e) ? ");
    unsigned annee;
    scanf("%u", &annee);
    printf("Vous avez donc %u ans !\n", age(annee));
    return 0;
}

Ecrivez dans un fichier age.s le code assembleur correspondant à la fonction C suivante :

unsigned age(unsigned annee_naissance)
{
    unsigned annee_courante = 2012;
    unsigned age = annee_courante - annee_naissance;
    return age;
}

Pour compiler, vous pourrez utiliser la commande suivante : gcc -Wall -Wextra -std=c99 -m32 -g age.c age.s -o age.

Appels croisés C/assembleur

Copiez-collez maintenant dans un fichier fact.c le code ci-dessous :

#include <stdio.h>
#include <stdlib.h>

unsigned fact(unsigned);

void erreur_fact(unsigned n)
{
    printf("Fact(%u) ne tient pas sur 32 bits !\n", n);
    // la fonction exit arrête proprement le programme
    exit(1);
}

int main(void)
{
    printf("Valeur de n : ");
    unsigned n;
    scanf("%u", &n);
    printf("Fact(%u) = %u\n", n, fact(n));
    return 0;
}

Ecrivez dans un fichier fact.s le code assembleur correspondant à la fonction C ci-dessous :

unsigned fact(unsigned n)
{
    if (n <= 1) {
        return 1;
    } else {
        return n * fact(n - 1);
    }
}

Vous utiliserez pour cela l'instruction de multiplication déjà vue à la première séance et dont on fourni la documentation.

Testez votre programme pour les valeurs 0, 1, 2, 5 et 13. Comme chacun sait, 13! = 6227020800 : est-ce bien la valeur obtenue ? Sinon, que se passe-t'il et comment détecter ce phénomène ? Modifier votre programme assembleur pour qu'il appelle la fonction erreur_fact fournie dans le fichier fact.c quand l'erreur est détectée.

Utilisation de la bibliothèque C standard

Copiez-collez dans un fichier palin.c le programme principal suivant :

#include <stdio.h>

int palin(char *ch);

// Ce programme lit ses parametres sur la ligne de commande.
// On peut par exemple l'appeler avec :
//   ./palin "chaine1" "la chaine 2" ""
// pour lui passer comme parametres : chaine1, la chaine 2
//   (considere comme un seul parametre), et la chaine vide
int main(int argc, char *argv[])
{
    for (int i = 1; i < argc; i++) {
        if (palin(argv[i])) {
            printf("\"%s\" est un palindrome.\n", argv[i]);
        } else {
            printf("\"%s\" n'est pas un palindrome.\n", argv[i]);
        }
    }
    return 0;
}

Implantez en assembleur dans un fichier palin.s une fonction détectant si la chaine passée en argument est un palindrome, et équivalente au code C ci-dessous :

int palin(char *ch)
{
    unsigned inf, sup;
    for (inf = 0, sup = strlen(ch) - 1; (inf < sup) && (ch[inf] == ch[sup]); inf++, sup--);
    return inf >= sup;
}

Si vous avez fini en avance : modifier votre programme pour qu'il gère correctement les espaces, la ponctuation et les majuscules dans la chaine passée en paramètre (e.g. les chaines "Esope reste ici et se repose" et "Dammit, I'm mad!" doivent être considérées comme des palindromes).

Passage de tableaux en paramètre

Copiez-collez dans un fichier tri_nain.c le code ci-dessous :

#include <time.h>
#include <stdio.h>
#include <assert.h>
#include <stdlib.h>
#include <string.h>

// affiche un tableau d'entiers signes de taille donnee
void afficher_tab(int tab[], unsigned taille)
{
    for (unsigned i = 0; i < taille; i++)
        printf("%i ", tab[i]);
    printf("\n");
}

void tri_nain(int[], unsigned);

// fonction de comparaison utilise par le tri
//   de reference
int comp_int(const void *a, const void *b)
{
        return *(int*)a - *(int*)b;
}

void test_tri(unsigned taille, int trace) {
    // tableau initial
    int *org =  malloc(taille * sizeof(int)); assert(org);
    // tableau trie avec le tri de reference
    // il servira a verifier que le tri fonctionne
    int *ref =  malloc(taille * sizeof(int)); assert(ref);
    // tableau a trier
    int *tab =  malloc(taille * sizeof(int)); assert(tab);
    // remplissage avec des valeurs aleatoires
    for (unsigned i = 0; i < taille; i++) {
        org[i] = (rand() % 19) - 9;
    }
    if (trace == 1) {
        printf("Tableau initial : "); afficher_tab(org, taille);
    }
    // tri de reference
    memcpy(ref, org, sizeof(int) * taille);
    clock_t debut = clock();
    qsort(ref, taille, sizeof(int), comp_int);
    clock_t fin = clock();
    printf("Tri de reference effectue en %f sec.\n", (double)(fin - debut) / CLOCKS_PER_SEC);
    // tri du nain
    memcpy(tab, org, sizeof(int) * taille);
    debut = clock();
    tri_nain(tab, taille);
    fin = clock();
    if (trace == 1) {
        printf("Tableau trie par le nain : "); afficher_tab(tab, taille);
    }
    // verification de l'integrite du tri
    if (memcmp(ref, tab, sizeof(int) * taille) == 0) {
        printf("Tri effectue par le nain en %f sec.\n", (double)(fin - debut) / CLOCKS_PER_SEC);
    } else {
        printf("Erreur : le tri n'est pas correct !\n");
    }
    free(org); free(ref); free(tab);
}


int main(void)
{
    // initialisation du generateur de nombres aleatoires
    srand(time(NULL));
    // pour tester visuellement
    printf("Tri d'un petit tableau :\n");
    test_tri(10, 1);
    // pour avoir des temps de calcul significatifs
    printf("\nTri d'un grand tableau :\n");
    // ajuster le nombre d'elements en fonction de la puissance de la machine
    test_tri(100000, 0);
    return 0;
}

Implantez dans un fichier tri_nain.s l'algorithme du tri par le nain de jardin, dont on rappelle le principe.

Un nain de jardin en train de buller au lieu de trier ses pots de fleurs !
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 pourrait écrire la fonction à implanter comme ci-dessous :

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;
        }
    }
}

On note que la fonction tri_nain prend en paramètre le tableau d'entiers à trier. On rappelle qu'en C, lorsqu'on passe un tableau en paramètre d'une fonction, c'est son adresse qui est passée (c'est à dire qu'on copie dans la pile un pointeur sur le premier élément du tableau, et pas l'ensemble des éléments du tableau !).

Si vous avez fini en avance : 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 tri_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_nain.c fourni.

Notez bien que le tri de référence est un quicksort, c'est à dire un tri en O(n.log(n)) alors que le tri du nain est un tri en O(n^2) : même en optimisant le code produit, cela ne compensera pas le fait que l'algorithme du nain est intrinsèquement moins efficace que celui du quicksort.