这个128位整数乘法如何在汇编(x86-64)中工作？

Question

我正在阅读计算机系统:程序员的观点,家庭作业是描述这种算法是如何工作的.

C功能:

void store_prod(__int128 *dest, int64_t x, int64_t y) {
    *dest = x * (__int128)y;
}

部件:

movq %rdx, %rax
cqto
movq  %rsi, %rcx
sarq  $63,  %rcx
imulq %rax, %rcx
imulq %rsi, %rdx
addq  %rdx, %rcx
mulq  %rsi
addq  %rcx, %rdx
movq  %rax, (%rdi)
movq  %rdx, 8(%rdi)
ret

我不知道它为什么表现: xh * yl + yh * xl = value which we add after unsigned multiplication

Answer 1

与往常一样，编译器选项很重要。带有gcc -Og（优化调试）的源代码产生与您的列表非常相似的 asm（在执行完整的 128x128 => 128 位乘法之前，强制转换符号将两个操作数扩展到 128 位）。这是 C 标准所说的应该发生的事情的幼稚实现（将两个操作数转换为相同类型的整数优先规则）。

如果您要谈论编译器输出，您应该始终说明哪个版本的哪个编译器具有哪些选项。或者只是在Godbolt上发布一个链接，就像上面的那个。（编辑：oops、source 和 asm 来自一本没有提供该信息的书。如果那是 CS:APP 3e 的全球版，请注意练习题在全球版中充满了错误。）

使用gcc -O3or -O2，GCC利用了两个操作数实际上仍然只有64位的事实，所以一个imul就足够了。（这仍然为每个输入产生相同的结果，因此仍然按照 as-if 规则实现 C 逻辑。C 没有扩展操作，因此您被迫以“低效”方式编写源代码，这取决于在编译器上将其转换为高效的 asm。）

该sar $63, %rcx是符号扩展的一部分rsi进入rcx:rsi，就像cqto登录延伸rax到rdx:rax。它用原始符号位的副本替换 RCX 的每一位。

这个答案的大部分内容已经由其他人在评论中给出，但我认为其他人没有注意到gcc -Og/-O1给出了几乎完全相同的 asm 输出。

Answer 2

GCC 正在做的是使用可以使用以下公式完成有符号乘法的属性。

(hi,lo) = unsigned(x*y)
hi -= ((x<0) ? y : 0)  + ((y<0) ? x : 0)

尽管事实上没有必要这样做，因为在这种情况下，x86-64 指令集具有带符号的 64 位 * 64 位到 128 位指令（imul带有一个操作数），但该公式在其他情况下很有用。例如，用于使用SSE2/AVX2/AVX512 实现有符号 128 位乘法，或者当指令集仅执行 128 位乘法（例如使用 x86-64）时实现 256 位乘法。

不过，GCC 对这个公式的实现有点不同。如果我们取符号位并将其扩展为整个字，调用该函数sign_ext，则该函数返回-1或0。那么GCC所做的是：

hi += sign_ext(x)*y + sign_ext(y)*x

例如，sign_ext(x)*y在 64 位字的伪指令中是

sarq  $63, x    ; sign_ext(x)
imulq   y, x    ; sign_ext(x)*y

所以现在你问（或打算问）：

为什么这个公式是正确的？

这是一个很好的问题。我也问了同样的问题，njuffa 写道

@Zboson：它直接来自二进制补码表示。例如，32 位整数-n和-m表示为无符号数x=2**32-n, y=2**32-m。如果你乘以你拥有的那些x*y = 2**64 - 2**32*n - 2**32*m + n*m。中间的条款表示对产品上半部分的必要修正。使用 -1*-1 完成一个简单的示例应该非常有启发性。