Exercício de Assembly (linguagem de montagem) x86 número primo

Novembro 2016


Introdução

Este exercício de linguagem para a montagem x86 visa às arquiteturas x86 (Intel e AMD de 32 bits) e utiliza a sintaxe Nasm, um "assembly" livre, gratuito e irrestrito em diversas plataformas como Windows ou Linux.
Igualmente, as funções externas são usadas a partir da biblioteca C padrão.
Assim, você não encontrará problemas com a sua máquina para fazer este exercício: ele não depende do sistema operacional utilizado. Ele só dependente da arquitetura x86.
Para utilizar o Nasm para testar esse exercício, leia clicando aqui.

Noções abordadas neste exercício

  • Funções com definição de entrada e valor de saída
  • Saltos (jmp, jz/je etc...)
  • A aritmética tendo em conta o tipo de variável (com sinal e sem sinal)
  • Divisão

Enunciado

O objetivo de escrever uma função em linguagem de montagem capaz de determinar, se um inteiro sem sinal é um número primo, ou não. Vamos dar um único parâmetro de entrada do tipo inteiro, sem sinal, que representará o número a ser testado. O valor de retorno deve ser 1 se o número for primo e 0, se o número não for primo.

Veja o que dará esta função em C:
int é_primo(unsigned int n); //O protótipo desta função  
//Exemplo de uso:
unsigned int nb = 3;
if (é_primo(nb) == 1){
printf("O número %d é primo!, nb);
}


Você deverá inserir este código:
extern printf, scanf  

section .data
entrar db 'Entre um número!', 0xa, 0x0
sim db 'É um número primo', 0xa, 0x0
não db 'Não é um número primo', 0xa, 0x0
formato_d db '%d', 0x0

seção .text
global main

é_primo:
;Insira o seu código aqui!


main:
push ebp
mov ebp, esp

;prever um espaço para um número inteiro na pilha
;Aquele que você entrará com scanf
sub esp, 4

;Pequena frase de boas-vindas
push entrar
call printf
add esp, 4

;Pedir ao usuário para entrar um número
push esp ;Endereço do número inteiro
push format_d ; %d
call scanf
add esp, 8

;Chamaremos a nossa função com o número inteiro digitado
push dword [esp]
call é_primo
;Testaremos o retorno (eax == 0 ?)
test eax, eax
;Se igual a zero => não primo
jz nãoPrimo
;Senão
push sim
call printf
;Estamos caminhando para a conclusão da função para não
;entrar na seção nãoPrimo
jmp quit

nãoPrimo:
push não
call printf

quit:
leave
ret


Pronto! Não há indícios para este exercício!

Lembrete

  • Um número primo é um número que só pode ser dividido por si mesmo, ou por 1. Se ele for dividido por outro número, o resto da divisão não será igual a 0.
  • Os saltos condicionais não são os mesmos para os números com sinal e para os números sem sinal. O mesmo vale para os operadores de multiplicação/divisão
  • O valor de retorno de uma função é colocado no registro eax

Correção

Veja uma solução:
é_primo:  
;Prólogo da função
push ebp
mov ebp, esp

;Carregaremos nosso número n em ecx
;ecx será, então, decrementado para testar todos os números
;que poderia dividir n variando de n até 2
mov ecx, [ebp + 8]
;Partiremos do princípio que ele é primo (ebx = 1)
mov ebx, 1

Divisões:
;Aqui se apresentam dois casos
;Ou acabamos de entrar na função e ecx é o nosso número
;se ele for menor ou igual a 2, ele é primo
;Ou acabamos de testar uma divisão por 2 e não precisamos continuar
;pois ele é primo
cmp ecx, 2
;ecx <= 2, nosso número é primo
jbe fimDivisões
;Decrementamos o divisor
dec ecx
;Colocamos em eax nosso número a ser dividido (argumento n)
mov eax, [ebp + 8]
;edx deve ser igual a zero porque ele é a parte superior do número dividido
xor edx, edx
;A divisão (eax / ecx)
div ecx
;O resto da divisão é igual a zero?
teset edx, edx
;Se não é porque o nosso divisor não pode dividir
;nosso número n. Continuamos a pensar que ele é primo e o dividimos
;por ecx - 1
jnz divisões
;Se o resto é zero, é que o nosso número não é primo
mov ebx, 0

fimDivisões:
;Carregamos o retorno da função com ebx
;com a nossa resposta
;(1: número primo 0: número não primo)
mov eax, ebx
leave
ret

Explicação

O algoritmo utilizado nesta solução é bastante simples, mesmo se não parece depois de traduzido em "assembly" (um pouco como todos os algoritmos em "assembly").
Veja o que faremos aqui. Suponhamos que o nosso número n é primo. Vamos pegar o nosso número n e dividí-lo, sucessivamente, por todos os números inferiores a ele, até o número 2, inclusive.
Se qualquer um destes números pode dividi-lo (ou seja, o resto da divisão é igual a zero), então paramos os testes e declaramos que o nosso número não é primo.
Da mesma forma, se o nosso número é, desde o início, inferior ou igual a 2, não fazemos o teste e declaramos que ele é primo.

Esquematicamente, esta é a nossa ideia:

Função é primo (n: inteiro sem sinal) : inteiro  
divisor = n
primo = 1
Como n <= 2
Fazer
divisor = divisor - 1
resto = n mod divisor
Se resta == 0
Então
primo = 0
sair do circuito
FinSi
FimComo
Fim
retornar primo

Para isso, usamos a instrução div que divide eax por um registro dado em parâmetro, neste caso, é o ecx que é o nosso divisor e que e decrementado a cada teste. É uma divisão por números sem sinal (caso contrário, use iDiv). O quociente é colocado em eax (nosso número n, recarregado a cada passagem pelo circuito) e o restante é colocado em edx.
Só precisamos testar o resto. Este circuito de divisões está localizado sob o rótulo de "divisões".
É um algoritmo que poderá ser otimizado, mas este não é o objetivo ... já que o objetivo de uma solução é ser simples. Apesar de tudo, não são os números primos que nos interessam, mas a linguagem de montagem (não é?).


Nota: Em nossa solução, ao fazer
div ecx

O que causa eax = eax / ecx e edx = eax % ecx
Tomamos cuidado em colocar edx a zero. É uma precaução tomada por que na verdade edx representa a parte mais significativa do número dividido.
Veja o que acontece na realidade:
eax = edx:eax / ecx e edx = edx:eax / ecx
Ao colocar edx a zero, é certo que edx não acrescentará bits significativos inesperados em nossa divisão.

Saiba mais sobre a linguagem de montagem

tutorial 1

tutorial 2

Veja também :
Este documento, intitulado « Exercício de Assembly (linguagem de montagem) x86 número primo »a partir de CCM (br.ccm.net) está disponibilizado sob a licença Creative Commons. Você pode copiar, modificar cópias desta página, nas condições estipuladas pela licença, como esta nota aparece claramente.