Prime Number Calculation
Below is a code snippet that prints a list of prime numbers, one on each line,
based on a limit entered by the user. It uses both while loops and conditional
branch ( if - else ) statements. We shall convert this to an assembly program to
demonstrate implementation of these control flow structures in x86-64
assembly.
unsigned guess; /* current guess for prime */
unsigned factor; /* possible factor for guess */
unsigned limit; /* find primes up to this value */
printf("Find primes up to:" );
scanf ("%u",&limit);
printf("2\n3\n"); /* treat first two primes as special case */
guess = 5;
while (guess <= limit) {
/* look for a factor of guess */
factor = 3;
while (factor*factor < guess && guess%factor != 0) {
factor += 2;
}
if (guess%factor != 0) {
printf("%d\n",guess);
}
guess += 2; /* only look at odd numbers */
}
Below is the code we shall call prime.asm . Apart from the CMP , JMP and Jcc (jump
based on status of bit in the RFLAGS register) instructions, we also
demonstrate use of the general purpose registers in 32-bit form ( EAX , EBX , etc.), even though the program is assembled in 64-bit long mode. We
still use some I/O functions from the file asm_io.asm .
%include "asm_io.inc"
%macro prologue 0
push rbp
mov rbp,rsp
push rbx
push r12
push r13
push r14
push r15
pushfq
%endmacro ; end of prologue
%macro epilogue 0
popfq
pop r15
pop r14
pop r13
pop r12
pop rbx
leave
ret
%endmacro ; end of epilogue
section .rodata
prompt1 db "Find primes upto: "
section .bss
guess resd 1 ; uninitialized integer
limit resd 1 ; uninitialized integer
section .text
global main
main:
prologue
; enter a value in the variable limit
mov rdi, prompt1
call print_string
mov rdi, dword limit
call read_int
; print the first 2 prime numbers
mov rdi, 0x2
call print_int
call print_nl
mov rdi, 0x3
call print_int
call print_nl
mov [guess],dword 0x5
while_limit:
mov eax, [guess] ; since we are dealing with integers, we use the 32-bit register to move data
mov edx, [limit] ; since we are dealing with integers
cmp eax, edx
jnbe end_of_while_limit ; jump if not below or equal
mov rcx, 3 ; RCX holds the variable factor
while_factor:
mov rax, rcx
mul rax ; calculate factor*factor. we could use EAX here,
; but using RAX will reduce chances of an overflow
jo end_of_while_factor ; we still check for overflow though with jump if overflow
cmp eax,[guess] ; we compare with EAX, otherwise if we use RAX here,
; 8 bytes will be read from the address of the variable guess
jge end_of_while_factor ; jump if greater than or equal
mov eax,[guess] ; moving 4 bytes only
cqo
div rcx ; guess / factor
cmp rdx,0 ; guess % factor is in RDX
je end_of_while_factor ; jump if equal
add rcx,2 ; factor+=2
jmp while_factor ; loop
end_of_while_factor:
mov eax,[guess]
cqo
div rcx
cmp rdx,0 ; guess%factor is in RDX
je end_of_if ; jump if equal
mov edi, [guess] ; move the value in guess into EDI for printing
call print_int
call print_nl
end_of_if:
mov eax, [guess]
add rax, 2 ; guess+=2
mov [guess],eax
jmp while_limit ; loop
end_of_while_limit:
epilogue
The section .bss is used to allocate uninitialized data, and stands for block
started by symbol. The keyword resd is Nasm's syntax for reserving memory for a
double word or 4 bytes. Many MOV instructions, implicitly read or write 8 bytes
if the 64-bit versions of the general purpose registers are used. Since we are
dealing with integers, we want only 4 bytes to be read or written, and hence we
use the 32-bit counterparts of the general purpose registers.
To compile the code we do the following:
$ yasm -f elf64 prime.asm $ yasm -f elf64 asm_io.asm $ ld -dynamic-linker /lib64/ld-linux-x86-64.so.2 /usr/lib64/crt1.o /usr/lib64/crti.o \ prime.o asm_io.o /usr/lib64/crtn.o -lc -o prime.out

