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 
				



Tweet


Follow @_vicash_