在汇编 x86-64 中使用 64 位乘积和 32 位整数的商

Question

开始学习汇编x86-64，我正在编写一个程序，获取整数数组并对其进行一些计算，目的与问题无关，但计算包括乘法和除法、大小和符号整数的数量是未知的，程序应该处理任何情况。 我想知道正确的方法是什么，我应该将整数扩展到 x64 大小的寄存器还是应该使用 EDX::EAX 扩展？

我的第一次尝试是

    movl (%r8), %edi #r8 holds the memory address of the array
    movl 4(%r8), %r10d # assume those are valid elements in the array, the check is done above 
    movl 8(%r8), %eax 
    imul %edi, %eax
    imul %r10d, %r10d
    cdq
    idiv %r10d 

但根据我的理解，使用此指令如果乘法导致溢出，eax 变为 0 并且进位标志打开，因此除以 r10d 可能会因除以 0 而导致 SIGFPE。 更好的方法是什么？我倾向于使用 x64 位大小的寄存器，因此处理所有情况会更容易，但我可能是错的。

Answer 1

x86-64 是 64 位架构，因此高效的 bigint 代码通常应该在 64 位块中工作。 例如

imul %rdi

将 128 位

RDX:RAX

设置为

RDI * RAX

的乘积。 使用

imul

的单操作数形式 (https://www.felixcloutier.com/x86/imul)。 像您使用的那样具有更多操作数的形式不会隐式写入 EDX 或 RDX。

如果 64 位足够宽，则可以在使用

movslq (%r8), %rax

等负载对输入进行符号扩展后使用非加宽 64 位数学。 然后 2 操作数

imul

相乘而不干扰 RDX。 如果您想进行 64 位除法，您需要

cqo

/

idiv

。 AT&T 语法将其称为

cqto

，但 GAS 接受任一助记符。

（如果内存中的值可以只是 64 位，您可以执行类似

imulq 8(%r8), %rax

之类的操作，而不是使用

mov

来加载。）

如果您知道商适合 32 位，则

mov 8(%r8), %eax

/

imull (%r8)

将在 EDX:EAX 中获得 64 位乘积（请注意

l

上显式的

imul

操作数大小后缀），其中设置为 32 位操作数大小

idivl 4(%r8)

。 在这种情况下，您不要使用

cdq

，这会将您的64位产品替换为低半部分的符号扩展。 （我们什么时候以及为什么使用 mul/div 来扩展和使用 cdq？ / 为什么在使用 DIV 指令之前 EDX 应该为 0？）。

但是，对 32 位操作数大小除法使用被除数的完整 64 位宽度可能会导致商不适合操作数大小（对于

INT_MIN

/

-1

或除法以外的情况） 0），在这种情况下，您将得到 #DE 异常。 （包括 Linux 在内的 POSIX 操作系统会将 SIGFPE 传送到您的进程。）

此外，这还将除数限制为 32 位。 你说平方

r10d

可能会溢出，所以这是它不是一个选项的另一个原因。

---

64 位除法操作数大小在 Ice Lake 之前的 Intel CPU 上要慢得多，但如果您的除数可能不适合 32 位，那么这是您唯一的选择。 （除了根据除数的大小进行分支之外，这可能是较旧的英特尔 CPU 上的胜利；一些 clang 版本/优化选项可以做到这一点。）

使用带符号的 32 位输入，使用 64 位整数作为临时值。 为了简单和高效，将 64 位整数保存在单个寄存器中。 （双操作数

imul

是单个uop，而一操作数在Intel上是2或3uop，因为它必须写入2个输出寄存器并分割乘法器单元的输出。https://uops.info /）

    movslq (%r8), %rdi   # sign-extend long (32-bit) to quad (64-bit)
    movslq 4(%r8), %r10
    movslq 8(%r8), %rax 

    imul   %rdi, %rax    # 64-bit non-widening multiplies can't overflow since the values are 32-bit
    imul   %r10, %r10

    cqto                # signed division of RAX by R10
    idiv   %r10

即使

INT_MIN

(

-2^31

) 的平方仍然适合

int64_t

，因此这些乘法不会导致溢出。 不需要

imul %rdi

将完整的 128 位乘积写入 RDX:RAX。 但在这种情况下，这将避免对

cqto

的需要，因为 x86 整数除法确实需要双倍宽度的被除数。

这实际上会给我们带来更小的机器代码，并且在最近的 Intel 和 AMD CPU 上的 uop 计数上实现收支平衡（https://uops.info/），其中

imul r64

“仅”2 uops，以及写入延迟RDX 是 RAX 结果准备好后的一个周期（与

cqo

相同）。

如果您将原始输入设置为 64 位，则使用加宽乘法的优点是，只要除数足够大以使商适合 64 位，则被除数可以大于 64 位而不会出错。