这个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，这是我们在无符号乘法后添加的值

- denis631

---

乘法的两个操作数必须是相同类型。为此，x 被提升为类型 __int128，因为在强制转换后 y 是这种类型，而 __int128 的整数提升等级高于 int64_t。其中一个转换由 cqto 完成，但它只适用于 rax，因此另一个由 sarq 转换。 - EOF

不要用 1 或 -1 进行乘法运算，应该使用 0 或 -1。 算术右移与 cqto 的作用相同：将符号扩展到整个寄存器（对于 sarq 使用 %rcx，对于 cqto 使用 %rdx）。 - EOF

由于 imul 已经提供了 64x64->128 位乘法，我认为这样做没有意义。当然你仍然可以解释它的工作原理 :) 这可能是禁用优化的常见情况，否则编译器足够聪明以使用单个 imul。 - Jester

不需要@EOF，正如我所说的，至少gcc和clang足够聪明，可以将这段精确的C代码转换为单个“imul”。 由于某种原因，icc没有做到。 - Jester

@denis631，那么您必须提出一个新问题。 您当前的问题是针对x86-64键入的，它已经有一条指令可以执行64*64到128的操作。 - Z boson

Answer 1

作为常规，编译器选项很重要。使用“gcc -Og”（为调试优化）的源代码生成与您的列表非常相似的asm（强制转换将两个操作数扩展到128位，然后执行完整的128x128 => 128位乘法）。这是C标准所规定的完全幼稚的实现方式（将整数优先级规则用于将两个操作数转换为相同类型）。

如果你要谈论编译器输出，你应该始终说明使用了哪个版本的编译器以及使用了什么选项。或者只需在godbolt上发布链接，就像上面的链接一样。（编辑：哎呀，源代码和汇编来自一本没有提供这些信息的书。如果那是CS:APP 3e的全球版，请注意实践问题充满错误。）

使用 gcc -O3 或-O2，GCC利用了两个操作数仍然只有64位的事实，因此一个单独的imul就足够了。（这仍然对于每个输入都产生相同的结果，因此仍符合as-if规则实现C逻辑。C没有扩展操作，所以你被迫以“低效”的方式编写源代码，依赖于编译器将其转换为高效汇编代码。）

---

sar $63, %rcx是将rsi符号扩展为rcx:rsi的一部分，就像cqto将rax符号扩展为rdx:rax一样。它用原始符号位的副本替换RCX的每个位。

---

这个答案的大部分内容已经在评论中被其他人提供了，但我认为没有人注意到gcc -Og / -O1几乎可以给出相同的汇编输出。

- Peter Cordes

---

谢谢你的回答。像我说的，这是书上的作业，所以我不知道使用了哪个编译器和哪些优化级别标志。 - denis631

@TomZych：感谢你的整理。虽然只是小改进，但肯定有所改善。 :) - Peter Cordes

几乎有了我的复制编辑徽章 :) - Tom Zych

感谢您的回答，我已经点赞了。这里有一个小问题需要指出：为了准确起见，将128位上升转换不应该称为“整数提升”。整数提升特指转换为“int”或“unsigned int”。有关详细信息，请参阅https://en.cppreference.com/w/c/language/conversion中的“整数提升”部分。 - aafulei

@aafulei：在我还不知道更好的术语之前，感谢你发现了这个老回答中的术语错误 :) - Peter Cordes

Answer 2

GCC正在使用的是有符号乘法可以使用以下公式进行计算的属性。

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

尽管在这种情况下，x86-64指令集具有带符号的64位*64位至128位指令(imul与一个操作数)，但实际上并不需要这样做。然而，在其他情况下，这个公式很有用，例如用于实现带符号的128位SSE2/AVX2/AVX512乘法或实现256位乘法时，如果指令集只支持128位乘法 (像x86-64一样)。

然而，GCC的实现方式略有不同。如果我们将符号位扩展到整个字，称此函数为sign_ext，那么该函数会返回-1或0。接着，GCC所做的就是：

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

例如，在64位单词的伪指令中，sign_ext（x）*y是这样的。

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 的简单示例来进行演示会非常有教益。

- Z boson

Answer 3

为了理解为什么要执行这些操作，请将int128_t解释为：2^64 * xh + xl。

因此，如果我们想要相乘两个int128_t整数，我们将执行以下操作：

x = 2^64 * xh + xl

y = 2^64 * yh + yl

所以x * y = (2^128 * xh * yh) + (2^64 * xh * yl) + (2^64 * yh * xl) + (yl * xl)

这正是汇编代码所做的：

yh = %rdx yl = %rax

xh = %rcx xl = %rsi

2^64 * xh * yl: 是imulq %rax, %rcx，2^64表示我们需要将其添加到高位比特中

2^64 * yh * xl: 是imulq %rsi, %rdx，2^64表示我们需要将其添加到高位比特中

2^128 * xh * yh: 不需要执行此操作，因为2^128 * xh * yh无法适应128位整数。它只代表符号位信息，可以忽略。

xl * yl: 是mulq %rsi 希望这能澄清事情！

- denis631