Steve Frécinaux

Quicksort en assembleur bêta

Je ne résiste pas à l’envie de vous montrer ce que j’ai fait jeudi soir… Je vous resitue : le lendemin j’avais examen de “structure des ordinateurs”, portant en fait sur une machine ultra-simplifiée, mais reprenant les principes directeurs d’un ordinateur normal, le cours étant disponible sur le lien précédant. Entre autre, dans la matière du cours, il fallait être capable de rédiger de petits programmes en assembleur, que nous pouvions tester chez nous grâce à un simulateur en mode console du MIT. Oh, rien de bien compliqué, on ne nous demandait rien de plus ardu que des mini programmes du genre “trouver le maximum dans une liste de N mots de 32 bits”. Pourtant, comme je ne devais pas encore être bien remis de l’examen d’algorithmique du mercredi, j’ai décidé, comme ça, de m’amuser à implémenter l’algorithme QuickSort (un algorithme de tri bien amusant, qui, avec ses homologues HeapSort et BubbleSort, était donc matière d’examen), le tout dans le langage assembleur de notre machine d’étude (mais qui selon notre professeur pourrait être compilé en code x86 dans un assembleur adapté).

Les contraintes de départ sont les mêmes que celles que nous devions habituellement satisfaire, c’est à dire : créer un programme principal dont la seule utilité est d’appeler une fonction à laquelle il passe les arguments nécessaires, en l’occurence l’adresse du tableau à trier (en mémoire) et le nombre de mots qui le composent (un mot = 4 octets, dans ce cas précis). Le but est donc de trier les N mots suivant l’adresse donnée dans l’ordre croissant.

Sachant qu’en assembleur, les seules choses que l’on peut faire sont des opérations simples et des sauts, l’aventure aurait pu sembler ardue, et pourtant, j’y suis arrivé ^^. La solution n’est sans doute pas optimale, mais elle a le mérite de fonctionner. Voici le programme résultant (qs.uasm).

Vous pouvez voir dans le code source une instruction .include beta qui permet en fait d’inclure un fichier contenant les définitions de toutes les macros utilisées (ADD, MUL, MOVE, etc.), et permettant donc au simulateur de les transformer en “code beta”, le code binaire de notre machine d’école. Une seconde instruction, .include qsdat, permet quand à elle d’inclure depuis un autre fichier les mots qu’il faudra trier. L’instruction BR(prgm) permet de sauter directement à l’adresse prgm:. Je ne vais pas indiquer ici la signification de chaque commande, elles sont détaillées, si ça vous intéresse vraiment, dans mon cours de SDO

Comme je ne suis pas trop fou, j’ai en parallèle rédigé un petit script en PERL (mon premier, snif) qui m’a permis de générer un tableau de nombres aléatoires, à trier (qsdat.pl) :

print 'Nom du fichier : ';
$fichier = <STDIN>;
$fichier = chop($fichier);

print 'Nombre de mots : ';
$nb = <STDIN>;
$nb = int($nb);
srand(15435340);

open (DONNEES, '>' . $fichier);
print DONNEES "dat_size:\n   LONG($nb)\n";
print DONNEES "dat:\n";

for ($i = 0; $i < $nb; $i++) {
  $mot = int(rand(32000));
  print DONNEES "   LONG($mot)\n";
}
print 'Ok.';

Qui a pour effet de générer mon fichier de données utilisé pour mon petit programme (qsdat.uasm).

Et bien vous me croirez ou pas, mais d’un seul coup d’un seul, je lance ma console, je tape uasm qs (qui ‘compile’ le programme, pour qu’il puisse être compris par le simulateur), puis bsim qs (le simulateur), je laisse le simulateur exécuter le programme tout seul, et à la fin, mes 20 mots étaient bel et biens triés par ordre croissant !

Autant vous dire que je me sentais prêt pour mon examen, après ça ^^ (d’ailleurs, il s’est bien passé)

Voilà, c’était une aventure de Nud’ au pays des micros…