Checking if a number is prime in NASM Win64 Assembly I'm just learning Assembly. This program is a simple attempt to determine if a given number is prime or not.

Compiled as follows using VS2019 x64 Native Tools Command Prompt:


&gt; nasm -g -fwin64 isprime.asm

&gt; cl /Zi isprime.obj msvcrt.lib legacy_stdio_definitions.lib



isprime.asm

bits 64
default rel

extern printf
extern scanf

section .data

    number: dq 0
    isPrime: dq 1
    counter: dq 0

    question: db "Which number would you like to check? ", 0
    fmt: db "%d", 0
    numberIsPrime: db "%d is prime", 10, 0
    numberIsNotPrime: db "%d is not prime", 10, 0

section .text

global main
main:
    push rbp
    mov rbp, rsp

    sub rsp, 32
    mov rcx, question
    call printf
    add rsp, 32

    sub rsp, 32
    mov rdx, number
    mov rcx, fmt
    call scanf
    add rsp, 32

    mov rcx, [number]
    mov [counter], rcx

continue_prime_check:
    dec qword [counter]
    cmp qword [counter], 2
    jge not_reached_1_yet
    jmp prime_check_ended

not_reached_1_yet:
    mov rax, [number]
    cdq
    mov rbx, [counter]
    idiv rbx
    cmp edx, 0
    je evenly_divisible
    jmp not_evenly_divisible

evenly_divisible:
    mov qword [isPrime], 0

not_evenly_divisible:
    jmp continue_prime_check

prime_check_ended:
    cmp qword [isPrime], 1
    je number_was_prime
    jmp number_wasnt_prime

number_was_prime:
    sub rsp, 32
    mov rdx, [number]
    mov rcx, numberIsPrime
    call printf
    add rsp, 32
    jmp end_if

number_wasnt_prime:
    sub rsp, 32
    mov rdx, [number]
    mov rcx, numberIsNotPrime
    call printf
    add rsp, 32

end_if:
    mov rbp, rsp
    pop rbp
    ret
Style: Indent your operands to a consistent column, so mnemonics of different length don't make your code look so ragged.  And use local .label labels inside functions.



Comment code that depends on non-standard behaviour: stdout is only guaranteed to be line-buffered, and isn't automatically flushed when you read stdin in ISO C.  Some systems (like Linux) do need fflush(stdout) after a printf of a string that doesn't end with a newline.  But I tried building a win64 executable by linking with mingw64 gcc, and running it under wine64, and it did actually print the prompt, to my surprise.

Normally you'd want to write a program like this to take its input as a command-line argument, instead of prompting for it with stdio at all.  (Then you just use strtoul or atoi, or sscanf, or even a hand-written loop to convert the ASCII decimal string to integer.)



Correctness problem: rbx is a call-preserved register in the x64 Windows calling convention.  Pick a call-clobbered scratch register, like rcx, or r8..r11. 
 https://docs.microsoft.com/en-us/windows-hardware/drivers/debugger/x64-architecture.  If main's caller happens not to crash when you return after stepping on its RBX, you got lucky.



Use 32-bit operand operand-size when possible, and make sure operand-size is consistent.  You're only reading a 32-bit int with scanf("%d", &amp;number), and the upper 32 bits are left zero from your dq 0.  It makes no sense to reserve 64 bits of space and then only ask scanf to write the low 32 of it.

See also The advantages of using 32bit registers/instructions in x86-64

Worse, you do cdq (sign extend EAX into EDX:EAX), but then you use 64-bit idiv rbx which divides RDX:RAX by RBX.  If your number input was -15 (base 10), your 128-bit dividend would be 0x00000000FFFFFFFF00000000FFFFFFF1.  Dividing that by a small integer would make the quotient overflow RAX, raising #DE (divide exception).  I didn't test your original version to see if I could provoke that with negative inputs; I changed to using %u for scanf and printf.

It's unclear why you'd want signed division.  Is this program supposed to work for negative inputs?  Your loop condition exits the loop if the counter is less than 2 (signed compare).  Unsigned lets us handle a larger range of inputs with faster 32-bit division.



Use 32-bit division for 32-bit numbers, it's about 2.5x faster than div r64 on Skylake, with similar performance ratios on other Intel CPUs.  See Trial-division code runs 2x faster as 32-bit on Windows than 64-bit on Linux for details.  (idiv and div are pretty similar in performance.  idiv r32 has a faster best-case throughput on Haswell than div r32, according to Agner Fog's instruction tables (https://agner.org/optimize/).  (1 per 8 vs. 9 clock cycles, and 1 fewer uop.  But for 64-bit division, div r64 has better throughput than idiv r64).

You were only checking the low 32-bits of the 64-bit remainder, too.  Since your original input was limited to 32-bit, this might be safe.  So possibly not a correctness problem.

Check a register for zero with test reg,reg, not cmp reg,0.  It saves a byte of code-size.  If the next instruction was js instead of jz, it would also have an advantage of micro-fusing into a compare+branch uop on more CPUs.



Use registers instead of static storage for your tmp variables, especially inside the loop.   That's what registers are for.  Static storage like you're using is equivalent to C static unsigned long long isPrime = 0;, instead of using an automatic storage variable that the compiler could optimize into a register.

asm doesn't have "variables", that's a high level concept that you can implement however you want, with registers, static storage, stack space, or whatever.  The normal way is to use registers and comment your code to keep track of what's where.  Anything that makes your code slower or larger defeats the purpose of writing in asm in the first place.  A compiler would easily make more efficient asm than what you've written.  (This is normal when you're a beginner, so don't feel bad about it, but be aware that looking at compiler output is another good way to learn efficient ways to do things in asm.  See How to remove “noise” from GCC/clang assembly output?)



Don't create a 0/1 boolean and then test it, just branch on the original condition and lay out your code to minimize the amount of jumping around.

You might want to save a 0/1 so you can exit with success or failure, making it possible to use this code as a prime-test in a script or something.  I did that in my version below, so I could verify its correctness with this bash one-liner on Linux.  (I tested it on Linux by using mov rdi, rcx / mov rsi, rdx before every scanf/printf to adapt for the calling convention difference between x86-64 System V and x64 Windows.)

 # check that all the numbers we think are non-prime actually have at least 2 prime factors (expect empty output because we filter out all lines with 2 spaces in `factor` output)
for i in $(seq 3 2 9999 );do echo $i | ./win-primes &gt;/dev/null || echo $i ;done | factor | grep -v ' .* '

# check that all the numbers we think are prime only have 1 prime factor (no lines with multiple spaces in the factor output
for i in $(seq 3 2 9999 );do echo $i | ./win-primes &gt;/dev/null &amp;&amp; echo $i ;done | factor | grep ' .* '




Speaking of branching, it's possible to branch much less.  See Why are loops always compiled into do while style tail jumps.

Put one of the conditional branches at the bottom of the loop, and another inside as a break condition.  In my version below, notice that I put the .notprime block after the ret at the end of the main function.  Putting a block out-of-line means you don't have to jump over it in the other path of execution.  Branch layout is a hard problem, figuring out which code can fall through into what other code, and with what values in registers, is part of the fun of writing branchy asm code.  (As opposed to simple loops with mostly SIMD instructions, then the fun in in branchless logic.)

Speaking of which, I probably should have laid out my loop so the fall-through and less-branching case was non-primes.  We expect them to be more common, and jumping around less in the common case is generally best for I-cache footprint and other front-end factors.  The loop naturally lends itself to checking both things in that order after division, though, so I'd have to do some extra setup to skew the loop and put the n%c == 0 branch at the bottom.



Pretty much never use mov rcx, symbol to get a static address into a register.  With nasm -fwin64, it assembles to the 10-byte mov r64, imm64 encoding, which is larger and typically slower to decode and/or fetch from uop cache than a 7-byte RIP-relative LEA.  Also, it needs a load-time fixup for ASLR.

If static addresses fit in 32-bit signed immediates (true in some systems), they usually also fit in 32-bit unsigned, so mov ecx, symbol is shorter (only 5 bytes).


mov ecx, symbol: 5 bytes, mov r32, imm32.  Best choice in position-dependent code (and usable in Windows with LargeAddressAware = no)
mov rcx, strict dword symbol: 7 bytes, mov r/m64, sign_extended_imm32.  Never use, except for kernel code (high addresses).
mov rcx, strict qword symbol: 10 bytes, mov r64, imm64.  Never use.
mov rcx, symbol with nasm -fwin64 is equivalent to strict qword
lea rcx, [rel symbol]: 7 bytes, normally the best choice if mov ecx, symbol isn't available and/or for position-independent code.    (You used default rel so you don't need the rel in every addressing mode).


I don't have a Windows system to test on, but x86_64-w64-mingw32-ld win-primes.obj will link all 4 of these into an executable.  (Unlike trying to link a Linux PIE executable, where 32-bit relocations aren't accepted at all).

Windows executables can be Large Address Aware or not.  If not, pointers will be 32-bit (I think all pointers, not just static code/data label addresses).  Or actually 31-bit, so zero-extension and sign-extension both work, I think, allowing [array + rdx*4] addressing modes.  Anyway, in a Windows non-largeaddress executable, you can use mov ecx, symbol to put a symbol address into a register with only 5 bytes.  It's a tradeoff between needing a load-time fixup (for ASLR) of the immediate in the machine code vs. costing 2 extra bytes for a RIP-relative LEA.

mov reg,immediate can execute on more ports than RIP-relative LEA in some CPUs, but back-end port pressure is not usually a problem for these instructions (no input dependencies so they can run any time there's a spare cycle on the port they're scheduled to).



Don't use BITS 64.  All that does is let you accidentally assemble 64-bit machine code into a 32-bit object file instead of getting an assemble-time error on push rbp, because rbp isn't a register outside of 64-bit mode.

nasm -fwin64 sets the target bitness to 64-bit.  The only time bits 64 is useful for fully 64-bit code is if you want to make a flat binary, e.g. for turning asm into shellcode or a bootloader.  (nasm -fbin doesn't have bin64 or any other option for setting the target mode.)

The main use-case for bits 64 is if you're writing code that starts out in 16 bit mode, and switches the CPU to 64-bit mode.  So the first part of the code would be bits 16, then you might have some bits 32 code that you reach with a jmp far, or maybe go straight to bits 64 after setting up a GDT.  If you're not doing that or didn't understand this paragraph, you don't need and shouldn't use bits 64.



Put your read-only constant data in .rdata, not .data  The .data section is for mutable static data.  Grouping read-only data together into .rdata is good because 1) it catches bugs if you accidentally write to it, and 2) whole pages that are unmodified can be shared between different processes running the same executable.  (shared memory mapping.)  Note that runtime relocation fixups from stuff like mov ecx, symbol in an executable or DLL using ASLR will prevent sharing.

(On non-Windows, the equivalent section is .rodata).



Omit the frame pointer, like gcc -fomit-frame-pointer (on by default with optimization enabled).  You're not accessing the stack through RBP anyway, so you're not saving any code size by having it available instead of using offsets relative to RSP.  So those extra instructions are just costing you code-size and uops for no benefit.  mov rsp, rbp (note that you got this backwards but it's ok because you'd already adjusted RSP so they were equal again anway) + pop rbp is equivalent to leave.  leave costs 3 uops total, one more than mov + pop on Intel CPUs, but it's only 1 per function.  If you already have your stack pointer pointing at the saved RBP value, you should just pop rbp instead of leave or mov + pop.

You actually should use stack space to scanf into, instead of static storage, though.



You're not checking for errors from scanf.  If the user enters invalid input, scanf will return 0 and leave number unmodified, so 0.  That's pretty much ok for asm.  It doesn't get stuck in an infinite loop or crash.

In most languages that would be a big no-no, but you wouldn't normally write the input/output code in asm for real in the first place.

So as long as you're aware you're doing so, leave out error checking if you want.  You can always single-step in a debugger and print RAX after function calls, or even trace all the system calls your program makes.  (See the bottom of https://stackoverflow.com/tags/x86/info for debugging tips.)



Here's how I'd write it

Incorporating some of the things mentioned in other answers as well, like counting up from small divisors (quickly rule out most numbers), and only counting up to ~sqrt(n) because divisors come in pairs.  This vastly speeds up the code for large primes like 2^31-1 = 2147483647.  My version is dominated by startup overhead for that on Linux; perf stat says task clock = 0.339985 ms.  arith.divider_active only reports 180k clock cycles out of ~950k clocks total on my i7-6700k Skylake (including kernel time).  The inner loop should saturate the division unit and just bottleneck on div throughput.

;; bits 64
default rel

extern printf
extern scanf

section .rdata   ;; I typically put static data at the end, but here is fine too
;;    number: dq 0        ; use stack space for these
;    isPrime: dq 1
;    counter: dq 0        ; and just a register for this.

    prompt: db "Which number would you like to check? ", 0
    scan_fmt: db "%u", 0                                   ; %u instead of %d
    numberIsPrime: db "%u is prime", 10, 0
    numberIsNotPrime: db "%u is not prime", 10, 0

section .text

global main
main:
;    push rbp
;    mov rbp, rsp   ; unneeded, we're not using the stack frame

    stack_reserve: equ 32+8
    sub    rsp, stack_reserve   ; shadow space for callees + 8 bytes for stack alignment

    lea    rcx, [prompt]
    call   printf             ; magically flushes stdout with Windows C library

    ; memory from rsp+0 .. rsp+31 has potentially been stepped on by printf
    ; leave RSP where it is, ready for another call

;;; scanf into that 8-byte block of stack space above the shadow space, or into our *own* shadow space
    lea    rdx, [rsp+32]        ; stack addresses are normally 64-bit, can't get away with edx
    lea    rcx, [scan_fmt]
    mov    dword [rdx], 0       ; instead of error check, set n = 0 in case of I/O error
    call   scanf
    ;cmp   eax, 1               ; success = exactly 1 conversion
    ;jnz   .scanf_fail          ; TODO: error check

    mov    r8d, [rsp+32]        ; r8d: 32-bit unsigned number to be checked

    cmp    r8d, 3
    jbe   .prime                ; 2 is prime, and let's consider 0 and 1 prime as well.
                                ; catch 3 here so the loop can avoid the 3%3 == 0 corner case

    test   r8b, 1               ; all *other* even numbers (LSB=0) are non-prime
    jz    .notprime

    ;; n &gt;= 5 at this point
    mov    ecx, 3               ; ECX: trial divisor counter
.divloop:                  ; do {
    mov    eax, r8d
    xor    edx, edx
    div    ecx                ; *much* faster than div rcx

    test   edx, edx
    jz    .notprime           ; if (n%c == 0) goto notprime

    add    ecx, 2             ; we've already ruled out all the even divisors

    cmp    eax, ecx
    ja    .divloop         ; while( n/c &gt; (c+2) );
    ;; loop until c*c &gt; n, i.e. until c &gt;= sqrt(n), because divisors come in pairs
    ;; The c*c == n exact case is caught by the edx==0 test

    ;; Checking based on c*(c+2) lets us exit even earlier,
    ;;  and saves instructions because we can add before cmp
    ;; It's safe: I checked against a known-good primality test.
    ;; It works because any numbers between c*c and c*(c+2) are either prime
    ;;  or have smaller prime factors that we already found

;; fall-through: n is prime
.prime:
    lea    rcx, [numberIsPrime]
    mov    byte [rsp+32], 0
.print:
    mov    edx, r8d        ; n
    call   printf          ; format string already set one of 2 ways
;    mov rsp, rbp
;    pop rbp          ; just use LEAVE if you need this

    ;xor    eax,eax    ; return 0
    movzx  eax, byte [rsp+32]    ; return isprime(n) ? EXIT_SUCCESS(0) : EXIT_FAILURE(1)
    add    rsp, stack_reserve
    ret

.notprime:
    mov    byte [rsp+32], 1            ; store return value on the stack (above printf's shadow space).
                                       ;;  Typically you'd use a call-preserved register but we didn't need any for anything else
    lea    rcx, [numberIsNotPrime]
    jmp   .print
   ;; function tail-duplication would also be an option instead of jmp back
   ;; i.e. call printf  here and fall through to a mov eax,1 / ret


Note the comments describing conditions that hold when execution reaches that comment line.  I find that useful for keeping track of what previous conditions have ruled out.

This actually does one better than checking n/c &gt; c as the loop condition.  n/c &gt; c+2 doesn't miss any primes, and will exit the loop one iteration sooner sometimes.  It also saves instructions by not having to copy the old ecx to edx so you can compare against the old value.

A more intuitive / more-obviously-correct version that does n/c &gt; c needs an extra mov edx,ecx

.divloop:                  ; do {
    mov    eax, r8d
    xor    edx, edx
    div    ecx

    test   edx, edx
    jz    .notprime           ; if (n%c == 0) goto notprime

    mov    edx, ecx           ; save old c for compare
    add    ecx, 2             ; we've already ruled out all the even divisors

    cmp    eax, edx
    ja    .divloop         ; while( n/c &gt; c );




Using the division result in the loop condition means out-of-order execution can't evaluate the loop condition ahead of div progress.  So it won't be able to hide the branch mispredict when we leave the loop.

If we had calculated sqrt(n) ahead of time with something like this:

cvtsi2ss   xmm0, r8      ; signed 64-bit source = zero-extended r8d = uint32_t =&gt; float
sqrtss     xmm0, xmm0
cvtss2si   r9d,  xmm0    ; upper bound for ecx = sqrt(n)
;; or maybe we'd need to use sd instead of ss to avoid maybe rounding down


then the divide execution unit would have been busy doing that for about 3 cycles on Skylake.  That might actually be worth it; the branch mispredict penalty is probably higher.  Avoid stalling pipeline by calculating conditional early
.  Skylake has relatively great throughput for FP sqrt, older CPUs are worse.  But it's still slow compared to multiply.  If the throughput cost of one sqrt is less than the branch-mispredict penalty + div latency, then this wins for primes (where we eventually exit the loop by falling through the cmp/ja which OoO exec can't check until the div result for that iteration is ready.)

More importantly, most of the time you'll leave the loop from finding a divisor, unless you expect your inputs to usually be primes, and that branch unavoidably depends on the div result; that's the whole point of doing division.  So on the whole, doing an actual sqrt ahead of time to calculate a loop bound isn't worth it vs. using the clever trick of comparing the divisor and quotient.

To put it another way, an extra sqrtsd at the start delays all the div instructions including the last one by however long sqrt occupies the divider (before an integer div can start).  Or maybe one div could start while cvtsi2sd is running.  But anyway, that's approximately how many extra cycles it would add before execution of the last test/jz uop can detect that the loop should have exited, and starts branch mispredict recovery.

(I'm assuming that the loop-exit branch does mispredict.  This is normal unless you have a loop that runs for the same number of iterations repeatedly, and that count is under about 22 or 23 for Skylake.  It's IT-TAGE branch predictors are based on branch history, so this loop with 2 branches in it might only accurately predict the loop-exit for trip counts of &lt;= ~11 even if the loop has the same trip-count repeatedly.  Neither of those things are probably common.)



sqrtss is faster than sqrtsd.  A double can exactly represent every 32-bit integer (in fact up to ~53 bits, the size of its significand).  But We're probably find with rounding to the nearest float; a 32-bit float has more range than even int64_t so there's no risk of overflow to +Inf.  The only worry is that (float)n could round down, and we could miss a composite like n = prime^2.  You could compensate by always adding half the distance between representable floats for numbers in the size range 232-1, but the extra div operations we end up doing for large primes costs more than just spending a few extra cycles for double.

Even if we could cheaply do int->float conversion with rounding towards +Inf, any rounding up would mean extra loop iterations for large n.  But if we only need correctness for large n and speed for small n, it would be fun.  But changing the MXCSR rounding mode isn't worth it.

If we did use double sqrtsd, we could check check for n being a perfect square just by looking at the FP inexact flag when square-rooting and converting to integer.  If both of those operations are exact, then n was a perfect square.  (But you'd have to reset the IE flag in MXCSR first, and that's slower than just integer squaring and comparison.)