# 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:

> nasm -g -fwin64 isprime.asm

> 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

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

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
jmp end_if

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

end_if:
mov rbp, rsp
pop rbp
ret

• Which assembler are you using? – 1201ProgramAlarm Oct 4 '18 at 2:23
• The x64 Native Tools for VS2017 (NASM version 2.13.03 compiled on Feb 7 2018) – T145 Oct 4 '18 at 2:24

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", &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.

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 >/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 >/dev/null && 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 >= 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 > (c+2) );
;; loop until c*c > n, i.e. until c >= 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)
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 > c as the loop condition. n/c > 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 > 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 > 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 => 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 <= ~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.)

• It will take a while to digest everything, but I noticed you had the comment ; TODO: error check, and was wondering what an error check might look like. For which error you're checking included obviously. – T145 Oct 4 '18 at 20:30
• @Mr.Vix: both for I/O error (eax < 0), or simply input that doesn't match the format so no conversions performed (eax==0). See docs.microsoft.com/en-gb/cpp/c-runtime-library/reference/…, or the POSIX scanf docs, or ISO C scanf: en.cppreference.com/w/c/io/fscanf. Note the "return value" section of those docs. Of course printf can also have an I/O error if run with stdout closed (if that possible on Windows?), or redirected to a file on a full disk. But IDK if not prompting for input is useful behaviour in that case. – Peter Cordes Oct 4 '18 at 20:40
• @Mr.Vix: We do one sub rsp, 40 at the top of the function (32+8), and one at the bottom. It should be obvious that add rsp, 32 / sub rsp,32 back to back is a no-op, so yes, the other answers and comments explaining that you just allocate enough stack for the whole function and keep it allocated are correct. – Peter Cordes Oct 4 '18 at 20:42
• This may be a bit nit-picky, but isn't rax supposed to be the standard return register? Shouldn't we use that to store the result? – T145 Oct 5 '18 at 13:38
• @Mr.Vix: also, main's signature is int main(void) (or argc,argv), so the return value really is only the 32-bit eax, ignoring whatever is in the upper 32 bits of RAX. (On many systems, like Unix/Linux, process exit status is only 1 byte. IDK about Windows, but on Linux only the low byte of main's return value or the arg to exit(int) matters.) – Peter Cordes Oct 5 '18 at 17:37

There are numerous small things.

1. You don't have to keep subtracting and adding 32 from rsp. Allocate the space once at the start of the function (main), reuse it for the duration, and add it back at the end (but see below).
2. My personal preference would be to use mov ecx,offset question to make it clear that I want the address of the variable, and not the contents of it.
3. Start your prime check with the low numbers, not the high ones. They're far more likely to be divisors.
4. Check for divisible by 2 first (before your loop), then you only need to check the odd numbers in your loop.
5. Instead of a conditional jump around an unconditional jump, negate the condition. So you'd change

    jge not_reached_1_yet
jmp prime_check_ended
not_reached_1_yet:


to

    jnge prime_check_ended    ; or j

6. Instead of cmp edx,0, you can use test edx,edx. The test will do a bit-wise logical and of the two operands and set the flags accordingly without storing the result of the and. This is a common way to check for zero.

7. Once you find that your number is not prime, you can stop looping.
8. You can also stop looping once you get to the square root of number. This is often done by comparing the square of counter with number, but you can easily check it by comparing eax with counter after the division. If eax is less or equal to counter you can stop looping.
9. Your mov rbp,rsp at the end is backwards. It should be mov rsp,rbp. This will also remove the 32 bytes of stack space you reserved for argument storage during function calls, so you don't need to explicitly add those 32 bytes back to the stack pointer.
• For point one, do you mean rsp? I'm also guessing you're referring to the main ftn. If you may also give some more info on point six I'd appreciate it! – T145 Oct 4 '18 at 3:04
• @Mr.Vix I've rephrased point one and expanded on point six. – 1201ProgramAlarm Oct 4 '18 at 3:20
• So just to clarify, you mean all I need to do is have sub rsp in place of the first sub rsp, 32 in my main ftn, and then make the mov rsp, rbp change? All of the other sub rsp, 32 and add rsp, 32 calls can be deleted? – T145 Oct 4 '18 at 4:01
• @Mr.Vix Yes. Only one sub and no adds. – 1201ProgramAlarm Oct 4 '18 at 4:09
• Nice trick with comparing the quotient to the divisor. You can even go one better than that, and do n/c > (c+2) so you can increment the counter before the compare, and still not miss any factors. (I used that trick in my answer) – Peter Cordes Oct 4 '18 at 19:41
• The printing branches are identical, except that they load rcx with different addresses. Better setup rcx when you arrive to the conclusion, and unify printing.

Expanding on that, an idiomatic assembly program would first guess the right string, and correct it if it was wrong:

prime_check_ended:
mov rcx, numberIsPrime
cmp cmp qword [isPrime], 1
je print_result
mov rcx, numberIsNotPrime

print_result:
mov rdx, [number]
call printf

• I don't know wether NASM supports local labels. If it does, it is a good habit to use them. Otherwise you risk polluting the label space.

• It does. A label that starts with a . is scoped to the previous non-. label. (Really it creates a label like foo.bar if you write foo: blah blah / .bar:, so you can refer to it from outside that scope.) – Peter Cordes Oct 4 '18 at 7:53
• How should I use local labels to improve the code? May you give an example? This is my first time hearing of the feature. – T145 Oct 4 '18 at 16:32
• @Mr.Vix A label like your end_if is very generic, and non-specific to the particular function. It could be used all over the (larger) program, but being global it must appear only once. Making it local allows its reuse. – vnp Oct 4 '18 at 17:36