; TITLE prime number tester
; Version takes advantage of 64-bit mode for long pointers and additional
; registers but only uses 32-bit arithmetic.


SECTION .data
max equ 10000000			        ; test for primes up to this number
cacheSize equ 1000			        ; size of the prime number cache
cache:	TIMES cacheSize dd 0		; allocate space for the cache
count:	dd	0
printStr:	db	"%d",10,0	        ; output string for printf

SECTION .text

extern printf
global main

; function to find the number of primes from 1 to MAX
asmCheckPrimes:
    ; parameters: rdi = max, rsi = cache, rdx = count
    push rbp	; save base pointer, aligns the stack for OS X

    mov r11d, edi
    mov rdx, rsi
    mov r10, 4*cacheSize
    add r10, rdx
    
    mov edi, 1
    mov r9d, 1
    
    mov [rdx], DWORD 2
    add rdx, 4
    
    ; edi = i, r9d = count, r11d = max, rdx = pos, r10 = end

TOP:

    add edi, 2      ; increment the number being tested
    
    cmp edi, r11d   ; finished once that number exceeds max
    jge DONE
    
    call asmIsPrime ; check if number is prime - per the 64-bit ABI, arguments are passed in registers
    
    cmp eax, 1
    jne TOP         ; number was not prime, jump to the top to test the next number
    
    inc r9d         ; increment prime number count
    
    cmp rdx, r10
    jge TOP         ; if there's no space remaining in the cache, return to top
    
    mov [rdx], edi  ; add value to cache
    add rdx, 4      ; move cache pointer forward

    jmp TOP

DONE:
    mov eax, r9d    ; prepare to return the number of primes found

    pop rbp	; restore base pointer, cleans up stack for OS X

    ret

; function to check if given number is prime
asmIsPrime:

    ; edi = n, rsi = cache, rdx = end
    mov r12, rdx
    
    push rdx	; save parameter register
    
    ; start sqrt - compute the integer square root of n using Newton's approximation method
    mov r15d, edi
    
    ; r15d = prev, edi = n
    
TOPSQRT:

    mov eax, edi
    mov edx, 0
    div r15d        ; cur = n / prev
    add eax, r15d   ; cur = prev + n / prev
    shr eax, 1      ; cur = 1/2 * (prev + n / prev)
    
    mov r14d, eax
    sub eax, r15d   ; x = cur - prev
    
    cdq
    xor eax, edx
    sub eax, edx    ; x = abs(cur - prev)
    
    mov r15d, r14d  ; prev = cur
    
    cmp eax, 1      ; if abs(cur - prev) <= 1, finished
    jg TOPSQRT
    
    ; end sqrt, result in r15d
    
    mov r14d, 1
    mov r13, rsi
    ; r12 = end, r13 = cache, r14d = tmp, r15d = max
    
    ; first test all numbers in cache for potential divisors of n
TOPCACHELOOP:

    cmp r13, r12        ; if done with cache, skip to main test loop
    jge TOPPRIMELOOP
    
    mov r14d, [r13]     ; get current value from cache
    cmp r14d, r15d      ; if value from cache exceeds max, done testing, number is prime
    jg ISAPRIME
    
    mov eax, edi
    mov edx, 0
    div r14d            ; divide current value by cached value
    
    cmp edx, 0
    je ISNOTAPRIME      ; if remainder is zero, current value is not a prime
    
    add r13, 4          ; move forward in the cache
    jmp TOPCACHELOOP
    
    ; manually test remaining potential divisors
TOPPRIMELOOP:
    add r14d, 2
    cmp r14d, r15d      ; if tmp > max, done testing, number is prime
    jg ISAPRIME
    
    mov eax, edi
    mov edx, 0
    div r14d            ; divide num by tmp
    cmp edx, 0
    je ISNOTAPRIME      ; if tmp divides num, num is not a prime
    
    jmp TOPPRIMELOOP

ISAPRIME:
    mov eax, 1
    jmp DONEPRIME
ISNOTAPRIME:
    mov eax, 0
DONEPRIME:
    pop rdx	; restore parameter register
    ret


main:
    sub rsp, 8	; stack alignment, needed for OS X

    mov edi, max
    mov rsi, cache
    mov rdx, count
    call asmCheckPrimes
	
    mov rdi, printStr
    mov rsi, rax
    call printf

    add rsp, 8	; clean up
    ret