Sieve of Eratosthenes in x86 assembly

Question

Hello I made a sieve of Eratosthenes algorithm on x86 assembly using NASM.

The highest number it can take is about 2 million and it takes like 2 seconds to complete.

Here's the code:

section .bss 
    buffer resb 100
    numbers resb 0

section .data
    arrayLength db 0

section .text
    global _start

    _start:
        call getLength
        call initList
        call algorithm
        call printNumbers
        
        exit

        algorithm: 
            mov r10, 0     ;starting index
            mov r11, 2     ;every nth number to be crossed out
            loop3:
                mov rax, [numbers]
                mov rbp, [arrayLength]
                crossOut rax, r10, r11, rbp           ;if this returns 0 it means all non primes are already crossed out   
                jz return               
                call getIndex                           ; get next r10d and r11d
                jmp loop3
            return:
                ret

        getIndex:                 ;gets the next item that isnt already crossed out (0 means not crossed)
            mov rax, [numbers]
            loop2:
                inc r10
                inc r11

                mov r12b, byte [rax + r10]             
                cmp r12b, 0                     
                jnz loop2

                ret

        getLength:
            mov eax, SYSREAD
            mov edi, 1
            mov esi, buffer
            mov edx, 100
            syscall
            stringToNumber buffer         ; returns edi as number
        
            mov rbp, rdi                ; store in ebp
            sub rbp, 2                  ; if user enters 30 then array length should be 28
                                        ; since first array item is 2

            mov [arrayLength], rbp      ; save in pointer
            extern malloc
            call malloc
            mov [numbers], rax          
            ret

        initList:
            mov rbx, 0          ;index
            mov rbp, [arrayLength]
            mov rax, [numbers]
            
            initloop:
                mov byte [rax + rbx], 0

                inc rbx
                cmp rbx, rbp
                jl initloop
            ret

        printNumbers:
            mov rbp, [arrayLength]
            mov r8d, 2          ; value
            mov r9d, 0          ; index
            
            printLoop:
                mov rax, [numbers]
                mov r11b, byte [rax + r9]

                cmp r11b, 0
                je handlePrime
                
                loopend:
                    inc r9d
                    inc r8d
                    cmp r9, rbp        ;return at array length
                    jnge printLoop
                    ret
                    
            handlePrime:
                printNumber r8
                jmp loopend
  
    
    %macro crossOut 4
    xor rdi, rdi     ;edi keeps track of how many numbers were crossed out
                     ;if 0 end loop
    mov rbx, %1     ;array
    add rbx, %2     ;move position to starting index
    mov rax, %3     ;every nth number to be crossed out 

    mov rbp, %4     ; array length
    mov rcx, 0      ;counter
    
    %%loop:

        add rcx, rax
        cmp rcx, rbp
        jge %%exit

        add rbx, rax
        cmp byte [rbx], 0           
        je %%crossout

        jmp %%loop
    %%crossout:
        mov byte [rbx], 1
        inc rdi
        jmp %%loop

    %%exit:
        cmp rdi, 0
%endmacro


;example:
;"123"  -> starting from 1

;1 + 0 * 10  = 1
;2 + 1 * 10  = 12
;3 + 12 * 10 = 123

%macro stringToNumber 1
    mov rdi, 0                 ; number stored here
    mov ebx, %1  
    mov ecx, 0   

    %%loop:
    xor esi, esi
    mov sil, byte [ebx + ecx]
    sub sil, 48

    cmp esi, 9                  ;if this is greater than 9 the string has ended
    jg %%exit

    mov rax, 10
    mul rdi                     ; multiply by 10
    add rsi, rax
    mov rdi, rsi

    inc ecx
    jmp %%loop
    
    %%exit:
%endmacro

Answer 1

vnp has already covered some excellent naming and organizational points. I won’t repeat them.

---

Your data structure is awkward. You allocate N - 2 bytes for the sieve, saving 2 bytes of memory, at the cost of needing to maintain both a value and index variables in registers, and needing to increment both. If you just allocated the full N bytes, then value and index would be the same, only one variable would be needed.

---

Crossing out multiples of 2’s means when you cross out multiples of a larger prime, p > 2, you don’t need to cross out 2p since it has already been done. Similarly, crossing out multiples of 3 means when you cross out multiples of a prime p > 3, you don’t have to cross out 3p since that has already been done. In general, crossOut should begin crossing out at p*p. For small prime numbers, this doesn’t save much, but as the primes get larger, the saved work becomes significant.

---

keeps track of how many numbers were crossed out; if 0 end loop`.

It took me a while to convince myself that this loop termination condition wasn’t flawed. It does work, but it is overly complex and slowing your code down.

First, why does it work? If p is prime, then p*p will never be crossed out by any preceding step. If p*p is less than your sieve limit, you will cross out that value at the very least, and the count will not be zero. If p*p is greater than the sieve limit, then every smaller multiple of p will have been crossed out, and the count will be zero.

So, blindly executing mov byte [rbx], 1 is all that is required. No testing cmp byte [rbx], 0 and no counting. Less memory cycles, less testing and less jumping will significantly improve the speed of the loop. Start the crossOut loop at p*p until that exceeds the sieve length.

Answer 2

• NASM supports local labels. Using .loop instead of loop2, loop3 etc improves readability.

• getIndex should be getNextPrime.

• call malloc does not belong to getLength. Do it in initList. BTW, you may as well call calloc, and don't bother to zero-fill the buffer manually.

• Instead of hand-rolled loops in initList and getIndex consider much more performant rep stosb and rep scasb respectively. Ditto for printNumbers.

• It seems that you try to avoid linking with libc. There is no reason to do it. getLength may benefit from calling fgets and strtol.

• What is printNumber? Yet again, I suspect that it does not call printf.