x86-64 TUTORIAL: FIND PRIME NUMBERS


x86-64 TUTORIAL: MULTIPLICATION & DIVISION  |  x86-64 TUTORIAL: BIT SHIFTING OPERATIONS

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 -m elf_x86_64 -dynamic-linker /lib64/ld-linux-x86-64.so.2 \
    /usr/lib/x86_64-linux-gnu/crt1.o  /usr/lib/x86_64-linux-gnu/crti.o \
    prime.o asm_io.o  /usr/lib/x86_64-linux-gnu/crtn.o -lc -o prime.out

Download prime.asm, asm_io.inc and asm_io.asm.


x86-64 TUTORIAL: MULTIPLICATION & DIVISION  |  x86-64 TUTORIAL: BIT SHIFTING OPERATIONS