LdB TPL2

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 ce TP est de pratiquer la programmation en assembleur Pentium, en traduisant des programmes en C fournis. Un des facteur déterminant de la notation sera la clarté du code assembleur produit et le côté « systématique » de sa traduction à partir des algorithmes donnés en C.

Dans tout le TP, vous respecterez scrupuleusement les consignes ci-dessous : toute divergence sera sanctionnée.

Le code assembleur que vous écrivez doit toujours être commenté. Une façon simple de rendre le code lisible est d'indiquer en commentaire la ligne de C traduite avant d'écrire le code assembleur correspondant. Vous ajouterez aussi des commentaires pertinents pour expliquer les points complexes ou notables du code.

Toutes les parties de ce TP peuvent être résolues en n'utilisant que les registres %eax, %edx et %ecx (on appellera désormais « registres scratch » ces 3 registres). Il faut pour cela utiliser astucieusement les différents modes d'adressage du Pentium. Si vous avez l'impression d'être obligé d'utiliser %ebx, %edi ou %edi, c'est que votre utilisation des modes d'adressage n'est pas optimale, ce qui sera sanctionné dans la notation.

Le squelette de code fourni contient la déclaration de toutes les données utiles dans ce TP. Vous n'avez normalement pas besoin d'en ajouter d'autres. Vous utiliserez les registres scratch pour stocker les variables locales intermédiaires.

On ne vous demande pas de chercher à optimiser le code produit. Néanmoins, les programmes inutilement inefficaces (e.g. algorithme avec un coût exorbitant, accès mémoires redondants, etc.) seront pénalisés.

Vous pouvez compiler le programme avec la commande :

gcc -o tp2 -m32 -g -gstabs tp2.S

Programmation d'un générateur de nombres pseudo aléatoires

Principe

Dans la première partie de ce TP, vous allez écrire un code générant une série de nombres pseudo aléatoires. Pour cela on va implanter de façon logicielle un registre à décalage à rétroaction linéaire (Linear Feedback Shift Register) semblable à celui que vous avez étudié dans le cours d'Architecture des ordinateurs du premier semestre.

Le principe d'un LFSR est d'énumérer séquentiellement les valeurs d'un intervalle donné, sans répétition tant que l'on n'a pas épuisé toutes les valeurs de l'intervalle. Il s'agit donc simplement d'une machine à états qui part d'une valeur initiale « bien choisie » et pour chaque pas de l'automate, calcule la valeur suivante.

Algorithme à implanter

La variante que l'on va implanter ici s'appelle un LFSR de Galois sur 32 bits. Il n'est pas nécessaire de comprendre le fonctionnement exact de ce type de LFSR pour réussir ce TP, car on donne ci-dessous le code C à traduire en assembleur :

// initialisation du générateur : donnée dans le squelette fourni
...
unsigned char tab[taille];
for (unsigned i = 0; i < taille; i++) {
    aleat = ... // calcul du prochain nombre aléatoire
    tab[i] = aleat % 16;
}

On doit d'abord initialiser le générateur de nombres pseudo aléatoires (i.e. trouver la valeur initiale « bien choisie », c'est à dire ici une valeur qui changera à chaque exécution du programme, pour que les tests varient). Pour cela, on va utiliser une instruction particulière du processeur Pentium : rdtsc. Sans rentrer dans les détails de son fonctionnement, elle a pour effet de renvoyer dans %edx:%eax le nombre de cycles machine écoulés depuis le dernier reset du processeur. En pratique, comme on souhaite initialiser un LFSR sur 32 bits, on écrira simplement :

rdtsc
movl %eax, aleat

si aleat est la variable contenant la valeur courante du LFSR.

Ensuite, on va remplir un tableau d'octets (unsigned char) avec des valeurs aléatoires. Pour cela, à chaque pas de l'itération, on doit calculer la valeur suivante du LFSR, en utilisant la formule suivante :

 aleat = \frac{aleat}{2} \oplus ((-(aleat\ .\ 1))\ .\ 
0xD0000001)

\oplus est l'opérateur « ou exclusif bit à bit » et . est l'opérateur « et bit à bit ».

On décide (tout à fait arbitrairement) que le tableau sera rempli de valeurs entre 0 et 15 inclus.

Travail à réaliser

On vous demande de traduire le code C ci-dessus en assembleur. Vous compléterez le squelette tp2.S en insérant votre code sous le commentaire "Remplissage du tableau avec des nombres aléatoires". Comme indiqué dans les consignes générales, vous n'utiliserez que les registres scratch dans cet exercice, en exploitant notamment le fait que le Pentium sait manipuler directement des variables en mémoire, sans passer par des registres.

Tri par insertion

Principe

On va maintenant trier par ordre croissant le tableau d'octets rempli dans l'exercice précédent. On va pour ça utiliser le tri par insertion. Cet algorithme a l'avantage d'être simple, à défaut d'être efficace (il s'agit d'un tri en O(n^2)).

Le principe de ce tri est le suivant :

  • on parcours le tableau en partant de la deuxième case ;
  • à chaque itération, on sauvegarde la valeur de la case courante, puis on parcours le tableau en sens inverse pour décaler d'une case vers la droite toutes les valeurs strictement supérieures à la valeur sauvegardée ;
  • on insère enfin la valeur sauvegardée dans la case ainsi libérée, et on avance.

L'invariant de ce tri peut donc s'écrire sous la forme suivante :

  • initialement tab[0..taille-1] n'est pas trié ;
  • à la Ième itération, tab[0..I-1] est trié par ordre croissant et tab[I+1..taille-1] n'est pas trié ;
  • à la fin tab[0..taille-1] est trié par ordre croissant.

Algorithme à implanter

Le code C a traduire est donné ci-dessous :

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

Travail à réaliser

Vous devez traduire l'algorithme ci-dessus en assembleur, en complétant le squelette fourni sous le commentaire "Tri par insertion". Comme précédemment, vous n'avez besoin d'utiliser que les registres scratch, pour stocker les variables locales.

Découpage du tableau

Principe

Pour finir, on va découper le tableau trié en deux sous tableaux tab1 et tab2 contenant respectivement les valeurs impaires et paires de tab, rangées cette fois par ordre décroissant.

Algorithme à implanter

Note : une erreur s'était glissée dans le code ci-dessous, qui est maintenant corrigé (il fallait bien utiliser ptr1 et ptr2 dans la boucle et pas tab1 et tab2).

Le code C à traduire est donc :

unsigned char *ptr1, *ptr2;
ptr1 = tab1; ptr2 = tab2;
do {
    taille--;
    if (tab[taille] % 2 == 1) {
        *ptr1 = tab[taille];
        ptr1++;
    } else {
        *ptr2 = tab[taille];
        ptr2++;
    }
} while (taille != 0);

Dans ce code, ptr1 et ptr2 sont des pointeurs sur des octets : il s'agit donc de variables sur 32 bits contenant chacune l'adresse d'une case de 8 bits.

La structure de contrôle do ... while est une forme d'itération similaire au while mais où la condition de continuation est testée à la fin de la boucle : la boucle est donc toujours exécutée au moins une fois (on rappelle que taille doit être strictement positive).

Travail à réaliser

Vous traduirez l'algorithme ci-dessus en assembleur, en complétant le fichier tp2.S sous le commentaire "Découpage du tableau".

Mise au point

Pour trouver les bugs dans votre programme, il est fortement recommandé d'utiliser gdb et Valgrind.

Pour afficher le contenu du tableau tab sous gdb, vous pouvez utiliser la commande suivante :

x /10ub (unsigned char[])tab

qui a pour effet d'afficher 10 octets (unsigned bytes) à partir de l'adresse tab.

Note importante : certaines versions récentes de Valgrind ne supportent pas l'instruction enter que l'on utilise au début du squelette de code fourni. Si vous obtenez une erreur du genre vex x86->IR: unhandled instruction bytes: 0xC8 à l'exécution, vous pouvez remplacer la ligne enter $0, $0 par les deux lignes suivantes :

pushl %ebp
movl %esp, %ebp

Compte-rendu

On ne vous demande pas de rédiger de rapport. Vous rendrez directement sur Teide le fichier tp2.S, en ajoutant en commentaire à la fin du fichier les tests que vous avez effectués et leurs résultats.

Vous pouvez travailler en binôme ou en monôme : le fait d’être seul n’entraînera pas de bonus dans la notation.

Enfin, on rappelle que la fraude est sanctionnée sévèrement pour tous les TP et projets, comme précisé dans la charte d’utilisation du matériel informatique.

Les enseignants se réservent le droit d’utiliser des logiciels de détection automatique pour localiser les ressemblances suspectes entre les fichiers rendus. Toute fraude avérée sera sanctionnée par un 0/20 au TP, sans possibilité de rattrapage. La récidive entraînera l’application des sanctions administratives prévues dans le règlement des études.