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-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 bits 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 before Ice Lake which introduced a new 64-bit-wide integer divider unit. 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 is 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 qwordlea 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 trade-off 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 anyway) + 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 and saves a few bytes. If you already have your stack pointer pointing at the saved RBP value, you should just pop rbp instead of leave or mov + pop. (Phoronix benchmarked -fomit-frame-pointer on Zen 3 with GCC12 and found a minor speedup as expected).
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)
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 > 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 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 begin 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. Its 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 fine with single-precision 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 with a large prime above 224, but that could only happen with an input above 248 since square root produces an output much smaller than its input. You could maybe add something to bias it towards rounding up or make sure the stop condition is high enough, but more operations probably costs more than just doing a double sqrtsd
Even if we could cheaply do int->float conversion with rounding towards +Inf, any rounding up would mean extra loop iterations for large prime n. But if we only need correctness for large prime n and speed for small or composite n, it would be fun. But changing the MXCSR rounding mode isn't worth it; only AVX-512 and AVX10 allow rounding-mode overrides on a per-instruction basis.
If we did use double sqrtsd, we could 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.)
