CEP CTD Pointeurs

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 de pratiquer la manipulation de structures et de pointeurs en assembleur : il est essentiel d'être à l'aise sur ses notions pour l'examen de TP final.

Exercice préliminaire

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

struct structure_t {
    int entier;
    char *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).

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

#include <stdio.h>

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

void affiche(int entier, int *ptr)
{
    printf("entier = %i, ptr = 0x%X\n", entier, (unsigned)ptr);
}

void affichage(struct structure_t);

void modification(int, char*, struct structure_t*);

int main(void)
{
    struct structure_t s = {-1, (char*)0x0ABCDEF0};
    affichage(s);
    modification(5, (char*)0x12345678, &s);
    affichage(s);
    return 0;
}

Ecrivez en assembleur dans un fichier struct.s les deux fonctions dont on donne le code C ci-dessous :

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

void modification(int entier, char *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 -Wall -Wextra -m32 -g -std=c99 struct.c struct.s -o struct.

Pour mettre au point votre code, vous aurez certainement besoin de GDB et de Valgrind, l'outil de validation des accès mémoire, que vous pouvez exécuter en tapant valgrind --leak-check=full ./struct.

Attention : certaines versions 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

Manipulation de listes chaînees

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

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

Copiez-collez dans un fichier liste.c le programme principal ci-dessous qui vous permettra de tester votre code :

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

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

// cree une liste chainee a partir d'un tableau d'entiers termine par -1
// les elements sont inseres dans l'ordre inverse par rapport au tableau initial
struct cellule_t *cree_liste(int tab[])
{
    struct cellule_t *liste = NULL;
    for (int i = 0; tab[i] != -1; i++) {
        struct cellule_t *cell = malloc(sizeof(struct cellule_t));
        assert(cell != NULL);
        cell->val = tab[i];
        cell->suiv = liste;
        liste = cell;
    }
    return liste;
}

// affiche une liste chainee d'entiers
void affiche_liste(struct cellule_t *liste)
{
    for (; liste != NULL; liste = liste->suiv) {
        printf("%d -> ", liste->val);
    }
    printf("FIN\n");
}

// detruit une liste chainee d'entiers
void detruit_liste(struct cellule_t *liste)
{
    while (liste != NULL) {
        struct cellule_t *suiv = liste->suiv;
        free(liste);
        liste = suiv;
    }
}

void inverse(struct cellule_t **l);

struct cellule_t *decoupe(struct cellule_t *l, struct cellule_t **l1, struct cellule_t **l2);

// une fonction de test basique
void test(int tableau[])
{
    struct cellule_t *liste, *l1, *l2;
    printf("Tableau initial : ");
    for (int i = 0; tableau[i] != -1; i++) {
        printf("%i ", tableau[i]);
    }
    printf("\n");
    liste = cree_liste(tableau);
    printf("Liste initiale : ");
    affiche_liste(liste);
    printf("Liste inversee : ");
    inverse(&liste);
    affiche_liste(liste);
    liste = decoupe(liste, &l1, &l2);
    printf("Liste initiale apres le decoupage : ");
    affiche_liste(liste);
    printf("Liste des elements impairs : ");
    affiche_liste(l1);
    printf("Liste des elements pairs : ");
    affiche_liste(l2);
    detruit_liste(liste);
    detruit_liste(l1);
    detruit_liste(l2);
}

int main(void)
{
    const int taille_tab = 11;
    int tableau[taille_tab];
    srand(time(NULL));

    printf("** Test d'un tableau quelconque **\n");
    for (int i = 0; i < taille_tab - 1; i++) {
        tableau[i] = rand() % 10;
    }
    tableau[taille_tab - 1] = -1;
    test(tableau);

    printf("\n** Test d'un tableau avec seulement des elements pairs **\n");
    for (int i = 0; i < taille_tab - 1; i++) {
        tableau[i] = (rand() % 10) & ~1;
    }
    tableau[taille_tab - 1] = -1;
    test(tableau);

    printf("\n** Test d'un tableau avec seulement des elements impairs **\n");
    for (int i = 0; i < taille_tab - 1; i++) {
        tableau[i] = (rand() % 10) | 1;
    }
    tableau[taille_tab - 1] = -1;
    test(tableau);

    printf("\n** Test d'un tableau vide **\n");
    tableau[0] = -1;
    test(tableau);

    return 0;
}

Commencez par écrire en assembleur dans un fichier liste.s la fonction suivante :

void inverse(struct cellule_t **l)
{  
   struct cellule_t *res, *suiv;
   res = NULL;
   while (*l != NULL) {
       suiv = (*l)->suiv;
       (*l)->suiv = res;
       res = *l; 
       *l = suiv;
   }   
   *l = res;
}

Cette fonction prend en paramètre l'adresse d'une liste chaînée (i.e. un pointeur sur un pointeur sur la cellule de tête de la liste) et inverse son contenu.

On demande ensuite de traduire en assembleur dans le fichier liste.s la fonction :

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.

Utilisez là aussi Valgrind pour mettre au point votre programme.

Pour vous entrainer à manipuler les pointeurs, vous pouvez écrire en assembleur les fonctions cree_liste, affiche_liste et detruit_liste dont on donne le code C ci-dessus (note : assert étant une macro, vous ne pouvez pas l'appeler depuis l'assembleur : ignorez donc la liste concernée).

Tri du nain de jardin

Si vous n'avez pas fini le tri du nain de jardin présenté à la séance précédente, vous devez le finir maintenant !

Si vous avez fini en avance

Reprenez le programme de test du tri du nain de jardin ci-dessus, mais remplacer ce tri par un tri par insertion, que vous implanterez en assembleur en traduisant la fonction C ci-dessous :

for (unsigned i = 1; i < taille; i++) {
    int v = tab[i];
    unsigned j = i;
    while ((j > 0) && (tab[j-1] > v)) {
        tab[j] = tab[j-1];
        j--;
    }
    tab[j] = v;
}