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.