Cómo saber si un número es primo: en C y ensamblador x86

Este pequeño código en lenguaje ensamblador está escrito para las arquitecturas x86 (procesadores AMD e Intel 32 bits) y utiliza la sintaxis de NASM. Las funciones externas utilizadas son tomadas de la biblioteca C estándar. Este no depende del sistema operativo, únicamente de la arquitectura x86.

¿Cuál es el objetivo?

Para escribir este código se utilizan las funciones con parámetro de entrada y valor de salida, las instrucciones de salto (jmp, jz/je...), la aritmética que tiene en cuenta el tipo de variable (con signo, sin signo) y la división. El objetivo es escribir una función en ensamblador capaz de determinar si un número entero sin signo es primo o no. Habrá un solo parámetro de entrada de tipo entero sin signo que representará el número a comprobar. El valor de retorno debe ser 1 si el número es primo y 0 si no lo es.

¿Qué es un número primo?

Un número primo es un número que puede ser dividido únicamente por sí mismo y por 1. Si es dividido por otro número, el resto de la división será distinto a 0.

¿Qué tipos de saltos condicionales hay y dónde se coloca el valor de retorno de una función?

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 y división. Por otra parte, el valor de retorno de una función se coloca en el registro eax.

¿Cuál es el código en C?

Primero escribimos el código en C para más adelante traducirlo a ensamblador: 

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 número %d es primo!, nb);
}

¿Cuál es el código en ensamblador x86?

• A continuación, el código:

es_primo:
  ;Prólogo de la función
  push ebp
  mov ebp, esp
;Cargamos el número n en ecx
  ;luego ecx será decrementado para testear todos los números
  ;que podrían dividir n yendo desde n hasta 2
  mov ecx, [ebp + 8]
  ;Partimos del principio que es primo (ebx = 1)
  mov ebx, 1
 divisiones:
  ;Aquí se presentan dos casos
  ;O hemos entrado en la función y ecx es nuestro número
  ;si es menor o igual a 2, es primo
  ;O hemos comprobado la división por 2 y por lo tanto es inútil continuar
  ;ya que no es primo
  cmp ecx, 2
  ;ecx <= 2, el número es primo
  jbe finDivisiones
  ;Decrementamos el divisor
  dec ecx
  ;Ponemos en eax el número 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 residuo de la división es igual a 0?
  test edx, edx
  ;Si no, es que el divisor no ha podido dividir
  ;el número n. Seguimos suponiendo que es primo y lo dividiremos
  ;por ecx - 1
  jnz divisiones
  ;Si el residuo es cero significa que el número no es primo
  mov ebx, 0
finDivisiones:
  ;Cargamos el retorno de la función con ebx
  ;que contiene la respuesta
  ;(1: número primo 0: no primo)
  mov eax, ebx
  leave
  ret

• Deberás insertar este código aquí:

extern printf, scanf
seccion .data
  ingresar db 'Ingrese un número!', 0xa, 0x0 sí    db 'C es un número primo', 0xa, 0x0 no    db 'No es un número 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 número
  push esp ;Dirección del entero
  push format_d ; %d
  call scanf
  add esp, 8 ;Llamamos a la 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

¿Cuál es el algoritmo utilizado?

El algoritmo utilizado en esta solución es bastante simple una vez traducido en ensamblador. Esto es lo que hemos hecho:

1. Partimos de la base de que nuestro número n es primo.
2. Dividimos sucesivamente n entre todos los números menores a n hasta el número 2 incluido.
3. Si es divisible por alguno de estos números (es decir el resto es igual a cero), entonces paramos el test y concluimos con que el número no es primo.
4. Sin embargo, si el número es desde un inicio menor o igual a 2, no hacemos ningún test y concluimos 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 debemos utilizar la instrucción div que divide eax entre un registro dado como parámetro. En este caso ecx es nuestro divisor y es decrementado en cada test. Es una división para números sin signo (en caso contratio, utilizar idiv). El cociente se coloca en eax (el número n, incrementado en cada vuelta del bucle) y el residuo es colocado en edx. Únicamente tenemos que testear el residuo. Este bucle de divisiones está situado bajo la etiqueta “divisiones”. Este es un algoritmo que podría ser optimizado, pero ese no es nuestro objetivo. Después de todo, no son los números primos los que nos interesan, sino el ensamblador.

• En el código, cuando escribimos div ecx da como resultado: eax = eax / ecx y edx = eax % ecx.
• Hemos tenido cuidado en poner edx a cero.
• Esto es lo que pasa en realidad: eax = edx:eax / ecx et edx = edx:eax / ecx.
• Poniendo edx en cero, estamos seguros de que edx no agrega bits significativos inesperados en la división.