Introducción

Este pequeño ejercicio de ensamblador es para las arquitecturas x86 (procesador Intel y Amd 32 bits) y utiliza la sintaxis de Nasm, un ensamblador libre, gratuito y que puede ser utilizado en diferentes plataformas como Windows y Linux.
Las funciones externas utilizadas son sacadas de la biblioteca C estándar.

De este modo no tendrás problemas ligados a la maquina que utilizas para hacer este ejercicio: no depende del sistema operativo utilizado. Únicamente depende de la arquitectura x86.

Nota: Para utilizar nasm a fin de testear este ejercicio, haz clic aquí para ver un tutorial de uso/instalación de nasm para Windows y Linux.

Nociones abordadas en este ejercicio

• Las funciones con parámetro de entrada y valor de salida
• Las instrucciones de salto (jmp, jz/je etc...)
• La aritmética teniendo cuenta del tipo de variable (con signo, sin signo)
• La división

Enunciado

El objetivo es escribir una función en ensamblador capaz de determinar si un entero sin signo es un número primo o no. Habrá un solo parámetro de entrada de tipo entero sin signo que representará el número a testear. El valor de retorno deber ser 1 si el número es primo o 0 si no es primo.

Esto seria lo que daría esta función en C:

int es_primo(unsigned int n); //El modelo de esta función
//Ejemplo de uso:
unsigned int nb = 3;
if (es_primo(nb) == 1){
    printf("El numero %d es primo!, nb);
}

Será necesario insertar este código:

extern printf, scanf

seccion .data
		ingresar db 'Ingrese un numero!', 0xa, 0x0
		sí    db 'C es un numero primo', 0xa, 0x0
		no    db 'No es un numero primo', 0xa, 0x0
		format_d db '%d', 0x0

seccion .text
		global main

es_primo:
		;Inserte el código aquí!

	
main:
		push ebp
		mov ebp, esp

		;Dejamos espacio para un entero en la pila
		;El que ingresaremos con scanf
		sub esp, 4

		;Frase de bienvenida
		push ingresar
		call printf
		add esp, 4

		;Solicitamos al usuario ingresar un numero
		push esp ;Direccion del entero
		push format_d ; %d
		call scanf
		add esp, 8

		;Llamamos a nuestra función con el entero ingresado
		push dword [esp]
		call es_primo
		;Probamos el retorno (eax == 0 ?)
		test eax, eax
		;Si es igual a cero => no es primo
		jz noPrimo
		;Si no
		push sí
		call printf
		;Vamos al final de la función para no
		;ingresar en la sección noPrimo
		jmp quit

	noPrimo:
		push no
		call printf

	quit:
		leave
		ret

Para recordar

• Un número primo es un número que puede ser dividido únicamente por él mismo o por 1. Si es dividido por otro numero, el resto de la división no será igual a 0.
• Los saltos condicionales no son los mismos para números con signo que para números sin signo. Lo mismo para los operadores de multiplicación/división.
• El valor de retorno de una función se coloca en el registro eax

Solución

A continuación una solución:

es_primo:
		;Prologo de la función
		push ebp
		mov ebp, esp

		;Cargamos nuestro numero n en ecx
		;luego ecx será restado para testear todos los números
		;que podrían dividir n yendo desde n a 2
		mov ecx, [ebp + 8]
		;Partimos del principio que es primo (ebx = 1)
		mov ebx, 1
	divisiones:
		;Dos casos se presentan aquí
		;Ya sea venimos de entrar en la función y ecx es nuestro numero
		;si es menor o igual a 2, es primo
		;O venimos de testear una división por 2 y por lo tanto es inútil continuar
                                ;ya que es primo
		cmp ecx, 2
		;ecx <= 2, nuestro numero es primo
		jbe finDivisiones
		;Restamos el divisor
		dec ecx
		;Ponemos en eax el numero a dividir (el argumento n)
		mov eax, [ebp + 8]
		;edx debe ser igual a cero 
		xor edx, edx
		;La división (eax / ecx)
		div ecx
		;¿El resto de la división es igual a 0?
		test edx, edx
		;Si non es que nuestro divisor no ha podido dividir
		;nuestro numero n. Continuamos creyendo que es primo y lo dividiremos
		;por ecx - 1
		jnz divisiones
		;Si el resto es cero significa que nuestro numero no es primo
		mov ebx, 0

	finDivisiones:
		;Cargamos el retorno de la función con ebx
		;que contiene nuestra respuesta
		;(1: numero primo 0: no primo)
		mov eax, ebx
		leave
		ret

Explicación

El algoritmo utilizado en esta solución es bastante simple, así no lo parezca, una vez traducido en el ensamblador (al igual que con casi todos los algoritmos en ensamblador).

Esto es lo que hemos hecho. Partimos del principio que nuestro numero n es primo. Dividimos sucesivamente n entre todos los números menores a n hasta el número 2 incluido.
Si es divisible por alguno de estos números (es decir su resto es igual a cero), entonces paramos el test y concluimos que nuestro numero no es primo.
Si nuestro numero es desde un inicio menor o igual a 2, no hacemos ningún test y decimos que es primo.

Esquemáticamente está es nuestra idea:

Funcion es_primo (n: entero sin signo) : entero
    divisor = n
    primo = 1
    Mientras n <= 2
    Hacer
        divisor = divisor - 1
        resto = n mod divisor
        Si resto == 0
        Entonces
            primo = 0
            salir del bucle
        FinSi
     FinMientras
Fin
devolver primo

Para ello utilizamos la instrucción div que divide eax entre un registro dado como parámetro, en este caso es ecx que es nuestro divisor y que es restado en cada test. Es una división para números sin signo (si no utilizar idiv). El cociente se coloca en eax (nuestro numero n, recargado en cada pasada en la bucle) y el resto es colocado en edx.
Únicamente tenemos que testear el resto. Este bucle de divisiones está situado bajo la etiqueta “divisiones”.
Este es un algoritmo que podría ser optimizado, pero no es el objetivo aquí…después de todo no son los números primos que nos interesan sino el ensamblador.

Nota: en nuestra solución, cuando hacemos

div ecx

Lo que provoca eax = eax / ecx y edx = eax % ecx
Hemos tenido cuidado en poner edx en cero. Es una precaución que debemos tener en cuenta.
Esto es lo que pasa en realidad:
eax = edx:eax / ecx et edx = edx:eax / ecx
Poniendo edx en cero, estamos seguro que edx no agregará bits de peso inesperados en nuestra división.

El artículo original fue escrito por kilian, contribuidor de CommentCaMarche