8

我正在阅读Computer Systems: A Programmer's Perspective，作业是描述该算法的工作原理。

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

4

3 回答 3

5

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

如果你要谈论编译器输出，你应该总是说哪个编译器的哪个版本有什么选项。或者只是在godbolt上发布一个链接，就像上面的那个。（编辑：哎呀，来源和 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 输出。

于 2015-11-19T00:43:57.787 回答
2

为了理解我们为什么要做这个操作，试着把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 y = %rax

xh = %rcx xl = %rsi

2^64 * xh * yl: 是imulq %rax, %rcx2^64 表示，我们需要将它添加到高位

2^64 * yh * xl: is imulq %rsi, %rdx2^64 表示我们需要将它添加到高位

2^128 * xh * yh：不需要此操作，因为2^128 * xh * yh不适合 128 位整数。它仅代表符号位信息，可以忽略。

xl * yl: 是mulq %rsi

我希望这能解决问题！

于 2015-11-21T10:11:13.970 回答
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，然后函数返回-1or 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 完成一个简单的示例应该非常有启发性。

于 2015-11-25T09:40:55.053 回答