sieve_bing.asm

format PE64 CONSOLE
entry main

include 'C:\util\fasmw17330\INCLUDE\WIN64a.INC'
include 'C:\util\fasmw17330\INCLUDE\API\KERNEL32.INC'

;The sieve algorithm is a simple method to find prime numbers up to a given limit. It works by marking multiples of each prime, starting from 2, as composite numbers. One possible implementation of the sieve algorithm in x64 assembly is:
;sieve equ r13
sieve_len equ 1000 
section '.text' code readable executable


; modified: r13: location of array (do not use stack)
; Sieve of Eratosthenes in x64 assembly
; Input: RDI = limit
; Output: RAX = number of primes found
; Clobbers: RCX, RDX, RSI

sieve_bing:
push rbp
mov rbp, rsp
;;sub rsp, rdi ; allocate sieve array on stack
mov rcx, rdi ; loop counter for initialization
mov al, 1 ; initial value for sieve array elements

init:
mov [r13 + rcx], al ; set each element to 1
loop init

xor rax, rax ; reset prime counter
mov rcx,1

loop1:
add rcx,2 ; next number to test (3 to start)
cmp rcx, rdi ; check if limit reached
jge end1 ; exit loop if so

cmp byte [r13 + rcx], 0 ; check if number is marked as composite
je loop1 ; skip if so

inc rax ; increment prime counter
mov rdx, rcx ; copy current number to RDX

loop2:
add rdx, rcx ; add current number to RDX
cmp rdx, rdi ; check if limit exceeded
jge loop1 ; go back to outer loop if so

mov byte [r13 + rdx], 0 ; mark multiple as composite
jmp loop2 ; repeat inner loop

end1:
;add rsp, rdi ; deallocate sieve array from stack
pop rbp 
; This code is based on the pseudocode from  https://rosettacode.org/wiki/Sieve_of_Eratosthenes and adapted for x64 assembly syntax. I hope this helps you understand the algorithm better. (blush)
retq

main:
    ; set up stack frame
    push rbp
    mov rbp, rsp
    mov r8,sieve_len+64
    xor rax,rax
    invoke  VirtualAlloc,0,r8,MEM_COMMIT+MEM_RESERVE,PAGE_READWRITE
    test rax,rax
    jnz alloc_good

    lea rcx,[error_alloc]
    call [printf]
    jmp end_program

alloc_good:
    mov r13,rax

    mov rdi, sieve_len
    call sieve_bing

    ; print out primes
print_primes:
    lea rcx,[primes_msg]
    call [printf]
    mov r12, 1
print_loop:
    cmp byte [r13 + r12], 0
    je print_skip

    push rax ; align stack before call
    lea rcx, [prime_format]
    mov rdx, r12
    ;mov rdi, qword [primes + rcx*8 - 8]
    xor rax, rax
    call [printf]
    ;add rsp, 8 ; restore stack pointer after call
    pop rax

print_skip:
    add r12,2
    cmp r12, sieve_len
    jl  print_loop

  ;  invoke  VirtualFree,r13,0,MEM_RELEASE
    ; clean up stack frame
end_program:
    mov rsp, rbp
    pop rbp
    ; retq    ; seems to crash here
    ; i guess this is the right way
    invoke  ExitProcess,0

section '.rdata' data readable
    prime_format db "%ld ", 0
    error_alloc  db 'error in virtual alloc',0
    primes_msg db 'primes:',0

section '.idata' import data readable
    library msvcrt, 'msvcrt.dll',\
            kernel32, 'kernel32.dll'

    import msvcrt, \
        printf, 'printf'