Exercice assembleur x86 nombre premier
Introduction
Ce petit exercice d'assembleur vise les architectures x86 (Processeurs Intel et Amd 32 bits) et utilise la syntaxe de Nasm, un assembleur libre, gratuit et utilisable sur différentes plateformes telles que Windows ou Linux.
De même les fonctions externes utilisées sont issues de la bibliothèque C standard.
Ainsi vous n'aurez pas de problèmes liés à votre machine pour faire cet exercice: il n'est pas dépendant du système d'exploitation utilisé. Il est uniquement dépendant de l'architecture x86.
NOTE: Pour utiliser nasm afin de tester cet exercice, vous trouverez un tutoriel d'utilisation/installation de nasm pour Windows et Linux en cliquant ici.
Notions abordées dans cet exercice
- Les fonctions avec paramètre d'entrée et valeur de sortie
- Les sauts (jmp, jz/je etc...)
- L'arithmétique en tenant compte du type de variable (signé / non-signé)
- La division
Enoncé
Le but est d'écrire une fonction en assembleur capable de determiner si un entier non signé est un nombre premier ou pas. On donnera un seul paramètre d'entrée de type entier non signé qui représentera
le nombre à tester. La valeur de retour doit être 1 si le nombre est premier et 0 si le nombre n'est pas premier.
Voici ce que donnerait cette fonction en C:
int est_premier(unsigned int n); //Le prototype de cette fonction
//Exemple d'utilisation:
unsigned int nb = 3;
if (est_premier(nb) == 1){
printf("Le nombre %d est premier!, nb);
}
Il vous faudra insérer ce code là dedans:
extern printf, scanf section .data entrer db 'Entrez un nombre!', 0xa, 0x0 oui db 'C est un nombre premier', 0xa, 0x0 non db 'Ce n est pas un nombre premier', 0xa, 0x0 format_d db '%d', 0x0 section .text global main est_premier: ;Insérez votre code ici! main: push ebp mov ebp, esp ;On prévoit de la place pour un entier dans la pile ;Celui que l'on entrera avec scanf sub esp, 4 ;Petite phrase de bienvenue push entrer call printf add esp, 4 ;On demande à l'utilisateur d'entrer un nombre push esp ;Adresse de l'entier push format_d ; %d call scanf add esp, 8 ;On appelle notre fonction avec l'entier entré push dword [esp] call est_premier ;On teste le retour (eax == 0 ?) test eax, eax ;Si égal à zero => pas premier jz pasPremier ;Sinon push oui call printf ;On va vers la conclusion de la fonction pour ne pas ;entrer dans la section pasPremier jmp quit pasPremier: push non call printf quit: leave ret
C'est parti! Pas d'indice pour cet exercice!
Rappel
- Un nombre premier est un nombre qui ne peut être divisé que par lui-même ou par 1. Si on le divise par un autre nombre, le reste de la division ne sera pas égal à 0.
- Les sauts conditionnels ne sont pas les mêmes pour des nombres signés que pour les nombres non-signés. Idem pour les opérateurs de multiplication/division
- La valeur de retour d'une fonction se place dans le registre eax
Corrigé
Voici une solution:
est_premier: ;Prologue de la fonction push ebp mov ebp, esp ;On charge notre nombre n dans ecx ;ecx sera ensuite décrémenté pour tester tous les nombres ;qui pourraient diviser n en allant de n à 2 mov ecx, [ebp + 8] ;On part du principe qu'il est premier (ebx = 1) mov ebx, 1 divisions: ;Deux cas se présentent ici ;Soit on vient d'entrer dans la fonction et ecx est notre nombre ;s'il est plus petit ou égal à 2, il est premier ;Soit on vient de tester une division par 2 et donc inutile d'aller plus loin ;car il est premier cmp ecx, 2 ;ecx <= 2, notre nombre est premier jbe finDivisions ;On décrémente le diviseur dec ecx ;On met dans eax notre nombre à diviser (l'argument n) mov eax, [ebp + 8] ;edx doit être égal à zero car il est partie haute du nombre divisé xor edx, edx ;La division (eax / ecx) div ecx ;Le reste de la division est égal à zero? test edx, edx ;Si non c'est que notre diviseur n'a pas été capable de diviser ;notre nombre n. On continue à penser qu'il est premier et on le divisera ;par ecx - 1 jnz divisions ;Si le reste est nul c'est que notre nombre n'est pas premier mov ebx, 0 finDivisions: ;On charge le retour de la fonction avec ebx ;qui contient notre réponse ;(1: nombre premier 0: pas premier) mov eax, ebx leave ret
Explication
L'algorithme utilisé dans cette solution est assez simple même s'il ne parait pas l'être une fois traduit en assembleur (un peu comme tous les algorithme en assembleur finalement).
Voici ce qu'on fait ici. On part du principe que notre nombre n est premier. On prend notre nombre n et on le divise successivement par tous les nombres qu'il lui sont inférieurs jusqu'au nombre 2 inclus.
Si l'un de ces nombres est capable de le diviser (c'est à dire que le reste de la division est égal à zero), alors on arrête les tests et on déclare que notre nombre n'est pas premier.
De même si notre nombre est dés le départ inférieur ou égal à 2, on ne fait pas de test et on dit qu'il est premier.
Schématiquement voici notre idée:
Fonction est_premier (n: entier non signé) : entier
diviseur = n
premier = 1
Tant que n <= 2
Faire
diviseur = diviseur - 1
reste = n mod diviseur
Si reste == 0
Alors
premier = 0
sortir de la boucle
FinSi
FinTantQue
Fin
retourner premier
Pour celà on utilise l'instruction div qui divise eax par un registre donné en paramètre, en l'occurence ici c'est ecx qui est notre diviseur et qui est décrémenté à chaque test. C'est une division pour nombres non-signés (sinon utiliser idiv). Le quotient est placé dans eax (notre nombre n, rechargé à chaque passage dans la boucle) et le reste est placé dans edx.
On a juste à tester le reste. Cette boucle de divisions est située sous le label "divisions".
Voilà c'est un algorithme qui pourrait être optimisé, mais ce n'est pas le but...le but d'une solution étant de rester simple. Après tout ce ne sont pas les nombres premiers qui nous interessent mais l'assembleur (euh...n'est ce pas?).
Petite note: dans notre solution, lorsque l'on fait
div ecx
ce qui provoque eax = eax / ecx et edx = eax % ecx
on a pris soin de mettre edx à zero. C'est une précaution à prendre car en fait edx représente la partie de poids fort du nombre divisé.
Voici ce qui se passe en réalité:
eax = edx:eax / ecx et edx = edx:eax / ecx
En mettant edx à zero, on est sûr que edx ne viendra pas ajouter des bits de poids fort innatendus dans notre division.
