检查NASM Win64汇编中的数字是否为质数

> nasm -g -fwin64 isprime.asm

> cl /Zi isprime.obj msvcrt.lib legacy_stdio_definitions.lib

#1 楼

样式：将操作数缩进一致的列中，因此不同长度的助记符不会使您的代码看起来那么参差不齐。并在函数内部使用本地.label标签。


注释代码取决于非标准行为：stdout仅保证是行缓冲的，并且在读取stdin时不会自动刷新在ISO C中。某些系统（例如Linux）在fflush(stdout)后面不以换行符结尾的字符串时确实需要printf。但是我尝试通过与mingw64 gcc链接来构建一个win64可执行文件，并在wine64下运行它，实际上确实打印了提示，这令我惊讶。

通常，您想编写一个这样的程序将其输入作为命令行参数，而不用完全使用stdio进行提示。 （然后，您只需使用strtoul或atoi或sscanf，甚至是手写循环即可将ASCII十进制字符串转换为整数。）在x64 Windows调用约定中注册。选择一个呼叫密集的暂存器，例如rbx或rcx。
https://docs.microsoft.com/zh-cn/windows-hardware/drivers/debugger/x64-architecture。如果r8..r11的调用者踩到RBX后返回时碰巧没有崩溃，则表示很幸运。


请尽可能使用32位操作数操作数大小，并确保操作数-大小是一致的。您只读取带有main的32位int，而scanf("%d", &number)的高32位保留为零。保留64位空间然后只要求dq 0写入低32位是没有意义的。

另请参见在x86-64中使用32位寄存器/指令的优点

更糟糕的是，您执行scanf（将EAX扩展为EDX：EAX），然后使用64位cdq（将RDX：RAX除以RBX）。如果您输入的数字是idiv rbx（以10为底），则您的128位除数将是-15。将其除以小整数将导致商溢出RAX，从而引发0x00000000FFFFFFFF00000000FFFFFFF1（除法异常）。我没有测试您的原始版本，看看是否可以通过否定的输入来激发它。我改为将#DE用于scanf和printf。

尚不清楚为什么要进行有符号除法。这个程序应该用于负输入吗？如果计数器小于2（有符号比较），则循环条件退出循环。 Unsigned使我们能够以更快的32位除法处理更大范围的输入。


将32位除法用于32位数字，比Skylake上的%u快2.5倍，在其他英特尔CPU上具有相似的性能比。有关详细信息，请参见试用分区代码在Windows上以32位运行的速度比在Linux上以64位运行的速度快2倍。 （根据Agner Fog的指令表（https://agner.org/optimize/)，div r64和idiv在性能上非常相似。div在Haswell上的最佳情况吞吐量要比idiv r32更快。（每8个时钟与9个时钟1个时钟）周期，并且uop少1个。但是对于64位除法，div r32的吞吐量要比div r64更好。）

用idiv r64而不是test reg,reg检查一个寄存器是否为零，这样可以节省一个代码大小的字节。下一条指令是cmp reg,0而不是js，它还具有在更多CPU上微融合到compare + branch uop中的优势。


为tmp变量使用寄存器而不是静态存储，尤其是在循环内部。那就是寄存器的用途。像您使用的静态存储等效于C jz，而不是使用编译器可以优化到寄存器中的自动存储变量。

asm没有“变量”，这是一个高水平您可以根据需要实现的概念，包括寄存器，静态存储，堆栈空间或其他内容。通常的方法是使用寄存器并注释您的代码以跟踪位置。首先，任何会使您的代码变慢或变大的东西都无法达到编写asm的目的。编译器将比您所编写的内容更容易地使asm效率更高。 （当您是初学者时，这是正常的，因此不要为此感到难过，但是请注意，查看编译器输出是学习在asm中执行操作的有效方法的另一种好方法。请参阅如何从中删除“噪声” GCC / clang程序集输出吗？）



不要创建0/1布尔值，然后对其进行测试，只需在原始条件上分支并布置代码以最大程度地减少跳跃量

您可能想要保存一个0/1，以便成功或失败都可以退出，从而可以将此代码用作脚本等中的主要测试。我在下面的版本中做到了这一点，因此可以通过Linux上的这种bash一线式验证其正确性。 （我在Linux上通过在每次scanf / printf之前使用static unsigned long long isPrime = 0; / mov rdi, rcx对其进行了测试，以适应x86-64 System V和x64 Windows之间的调用约定差异。） prettyprint-override“> mov rsi, rdx


说到分支，可以减少很多分支。请参见为什么在样式尾部跳转时总是将循环编译成do。

将一个条件分支放在循环的底部，将另一个条件分支放在 # 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 ' .* ' 条件下。在下面的版本中，请注意，我在主功能末尾的break之后放置了.notprime块。将块置于离线状态意味着您不必在其他执行路径上跳过它。分支布局是一个棘手的问题，弄清楚哪些代码可以落入其他代码以及寄存器中的值是编写分支asm代码的乐趣的一部分。 （与主要使用SIMD指令的简单循环相反，然后是无分支逻辑带来的乐趣。）

说到这，我可能应该安排我的循环，以便进行深入了解和减少分支是非素数。我们希望它们会更常见，而在常见情况下，跳越少通常最适合I-cache占用空间和其他前端因素。循环自然会在除法后按顺序检查这两个事物，因此，我必须做一些额外的设置以使循环倾斜并将ret分支放在底部。


几乎不要使用n%c == 0将静态地址获取到寄存器中。使用mov rcx, symbol，它可以组装成10字节的nasm -fwin64编码，与7字节的相对于RIP的LEA相比，它更大，通常从uop缓存中解码和/或获取速度也更慢。此外，它还需要ASLR的加载时修复程序。

如果静态地址适合32位带符号立即数（在某些系统中为true），则它们通常也适合32位无符号，因此mov r64, imm64为较短（仅5个字节）。



mov ecx, symbol：5个字节，mov ecx, symbol。位置相关代码的最佳选择（可在Windows中使用LargeAddressAware = no）

mov r32, imm32：7个字节，mov rcx, strict dword symbol。除内核代码（高地址）外，请勿使用。

mov r/m64, sign_extended_imm32：10个字节，mov rcx, strict qword symbol。切勿使用。

mov r64, imm64与mov rcx, symbol等效于nasm -fwin64


strict qword：7个字节，通常是lea rcx, [rel symbol]不可用和/或与位置无关的代码的最佳选择。 （您使用了mov ecx, symbol，因此在每种寻址模式下都不需要default rel。）

我没有要测试的Windows系统，但是rel会将所有这4个链接到可执行文件中。 （与尝试链接Linux PIE可执行文件（完全不接受32位重定位）不同。）

Windows可执行文件是否可以识别大型地址。如果不是，则指针将是32位的（我认为所有指针，而不仅仅是静态代码/数据标签地址）。我认为实际上是31位，所以零扩展和符号扩展都可以使用，允许x86_64-w64-mingw32-ld win-primes.obj寻址模式。无论如何，在Windows非大地址可执行文件中，可以使用[array + rdx*4]将符号地址放入只有5个字节的寄存器中。这是需要在机器代码中立即进行加载时修复（针对ASLR）与为RIP相对LEA花费额外的2个字节之间的折衷。在某些CPU中相对LEA，但是后端端口压力通常对于这些指令来说不是问题（没有输入依赖性，因此它们可以在计划的端口上有空闲周期的任何时间运行）。


不要使用mov ecx, symbol。所有这些操作使您可以将64位机器代码意外地汇编为32位目标文件，而不是在mov reg,immediate上遇到汇编时错误，因为BITS 64并非64位模式之外的寄存器。

push rbp将目标位设置为64位。 rbp唯一可用于全64位代码的时间是如果您想制作一个平面二进制文件，例如用于将asm转换为shellcode或引导程序。 （nasm -fwin64没有bits 64或用于设置目标模式的任何其他选项。）

nasm -fbin的主要用例是，如果您正在编写以16位模式开始并将CPU切换为64位模式的代码。因此，代码的第一部分将是bin64，那么您可能会有一些bits 64到达的bits 16代码，或者在设置GDT之后直接转到bits 32。如果您不这样做或不了解本段，则不需要也不应使用jmp far。


将只读常量数据放在bits 64中，而不是bits 64 .rdata部分用于可变静态数据。将只读数据分组到.data中是很好的，因为1）如果不小心将其写入会捕获错误，并且2）未修改的整个页面可以在运行同一可执行文件的不同进程之间共享。 （共享内存映射。）请注意，使用ASLR在可执行文件或DLL中使用.data之类的东西进行运行时重定位修正将阻止共享。 >

省略帧指针，例如.rdata（默认情况下处于启用状态且启用了优化）。无论如何，您都不会通过RBP访问堆栈，因此不会通过提供可用的代码大小而不是使用相对于RSP的偏移量来保存任何代码大小。因此，这些额外的指令只会花费您代码大小和成本，没有任何好处。 mov ecx, symbol（请注意，您已将此设置反过来了，但是可以，因为您已经调整了RSP，因此它们再次相等。）+ .rodata等同于gcc -fomit-frame-pointer。 mov rsp, rbp的总成本为3 uop，比Intel CPU上的pop rbp + leave多一倍，但每个功能只有1个。如果已经有指向保存的RBP值的堆栈指针，则应该只使用leave而不是mov或pop + pop rbp。 。


您不是要检查来自leave的错误。如果用户输入无效的输入，scanf将返回mov并保留pop不变，因此scanf。对于asm来说几乎可以。它不会陷入无限循环或崩溃中。

在大多数语言中，这是一个很大的禁忌，但您通常不会在asm中实际编写输入/输出代码首先。

，只要您知道自己正在这样做，就不要进行错误检查。您始终可以单步进入调试器并在函数调用后打印RAX，甚至跟踪程序进行的所有系统调用。 （有关调试提示，请参见https://stackoverflow.com/tags/x86/info的底部。）


这是我的写法

还要结合其他答案中提到的一些内容，例如从小除数开始计数（迅速排除掉大多数数字），并且由于除数成对出现，因此仅计数到scanf。这极大地加快了诸如0 = 2147483647之类的大质数的代码。我的版本受Linux上启动开销的支配。 number表示任务时钟= 0.339985毫秒。在我的i7-6700k Skylake上，0仅报告了约950k个时钟中的180k个时钟周期（包括内核时间）。内部循环应使除法单元达到饱和，并成为~sqrt(n)吞吐量的瓶颈。我发现这对于跟踪先前已排除的条件很有用。

这实际上比将2^31-1作为循环条件进行检查要好。 perf stat不会遗漏任何质数，有时会更快地退出循环一次。它还节省了指令，无需将旧的arith.divider_active复制到div，因此您可以将其与旧值进行比较。 />

;; 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

在循环条件中使用除法结果意味着乱序执行无法在n/c > c进行之前评估循环条件。因此，当我们离开循环时，它将无法隐藏分支的错误预测。

如果我们提前计算了n/c > c+2，例如：

.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 );

，那么除法执行单元将在Skylake上忙于执行大约3个周期。这实际上可能是值得的；分支机构错误预测的惩罚可能更高。通过计算条件提早避免流水线
。 Skylake对于FP sqrt具有相对较高的吞吐量，而较旧的CPU则更糟。但是与乘法相比，它仍然很慢。如果一个sqrt的吞吐成本小于分支错误预测的损失+ ecx延迟，那么这将赢得质数（在这里我们最终通过掉入edx退出循环，OoO执行人员直到该迭代的n/c > c结果都无法检查它更重要的是，大多数情况下，除非您期望输入通常为质数，否则您将避免寻找除数，因此该分支不可避免地取决于mov edx,ecx结果；这就是进行除法的重点。因此，总的来说，与使用比较除数和商的巧妙技巧相比，提前进行实际的div计算循环边界是不值得的。在启动时额外的sqrt(n)会延迟所有div指令（包括最后一条指令），但是cmp/ja占用分频器的时间会很长（在整数div可以启动之前）。或者，可能在运行div时启动一个sqrt。但是无论如何，这大约是在执行最后一个sqrtsd uop之前可以检测到循环应该退出并开始分支错误预测恢复之前要增加的额外周期数。（我假设loop-exit分支的预测错误。这是正常现象，除非您有一个循环重复运行相同次数的迭代，并且Skylake的计数低于22或23。基于分支历史，因此即使循环重复具有相同的跳闸计数，该循环中有2个分支的循环也只能准确地预测跳闸计数<=〜11的循环退出。 ）


div比sqrt更快。 div可以精确地表示每个32位整数（实际上最多约53位，其有效位数大小）。但是我们可能会发现四舍五入到最接近的div； 32位cvtsi2sd的范围甚至比test/jz更大，因此没有溢出到+ Inf的风险。唯一担心的是sqrtss可能会四舍五入，而我们可能会错过sqrtsd这样的复合词。对于大小范围为232-1的数字，您可以通过始终将可表示的double s之间的距离增加一半来补偿，但是最终我们为大素数执行的额外float操作所花费的成本不只是为float花费几个额外的周期。 >
即使我们可以廉价地将int-> float转换为+ Inf舍入，任何舍入也将意味着较大的int64_t会进行额外的循环迭代。但是，如果我们仅对于较大的(float)n需要正确性，而对于较小的n = prime^2只需要速度，那将很有趣。但是更改MXCSR取整模式是不值得的。转换为整数。如果这两个操作都正确，则float是一个理想的平方。 （但是您必须首先在MXCSR中重置IE标志，这比仅进行整数平方和比较要慢。）

#2 楼

有很多小东西。


不必继续从rsp中减去和加32。在功能开始时分配一次空间（main），在整个过程中重复使用，然后在末尾重新添加（但请参见下文）。我需要变量的地址，而不是变量的内容。
从低位开始而不是高位开始素数检查。他们更有可能是除数。
首先检查2的整数（在循环之前），然后只需要检查循环中的奇数即可。有条件的跳跃围绕无条件的跳跃，否定条件。因此，您可以将

    jge not_reached_1_yet
    jmp prime_check_ended
not_reached_1_yet:

更改为

    jnge prime_check_ended    ; or j

可以使用mov ecx,offset question代替cmp edx,0。 test edx,edx将对两个操作数进行按位逻辑test并相应地设置标志，而不存储and的结果。这是检查零的常用方法。
一旦发现您的数字不是素数，就可以停止循环。
一旦到达and的平方根，也可以停止循环。这通常是通过比较number和counter的平方来完成的，但是您可以通过在除法后将number与eax进行比较来轻松地进行检查。如果counter小于或等于计数器，则可以停止循环。
最后的eax向后。应该是mov rbp,rsp。这还将删除函数调用期间为参数存储保留的32个字节的堆栈空间，因此您无需将这32个字节显式添加回堆栈指针。

#3 楼

打印分支是相同的，除了它们用不同的地址加载rcx。得出结论时，请更好地设置rcx并统一打印。

对此进行扩展，惯用的汇编程序会首先猜测正确的字符串，如果输入错误，则对其进行纠正：

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

print_result:
    mov rdx, [number]
    call printf

我不知道NASM是否支持本地标签。如果是这样，使用它们是一个好习惯。否则可能会污染标签空间。