使用intel内联汇编器编码带有进位的bigint add

我想做一个快速代码来添加大整数中的 64 位数字：

uint64_t ans[n];
uint64_t a[n], b[n]; // assume initialized values....
for (int i = 0; i < n; i++)
  ans[i] = a[i] + b[i];

但以上不适用于进位。

我在这里看到另一个问题，建议使用 if 语句来检查哪个是优雅的：

ans[0] = a[0] + b[0];
int c = ans[0] < a[0];
for (int i = 0; i < n; i++) {
  ans[i] = a[i] + b[i] + c;
  c = ans[i] < a[i];
}

但是，我想学习如何嵌入内联（英特尔）汇编并更快地完成。 我确信有 64 位操作码，相当于：

add eax, ebx
adc ...

但我不知道如何将参数从 C++ 代码的其余部分传递给汇编器。

但以上不适用于进位。

如果您的意思是 GCC 不会生成使用ADC指令，那是因为它的优化器已经确定有一个更优化的方法来实现加法。

这是我的代码的测试版本。我已经将数组提取出来作为传递给函数的参数，这样代码就不能被省略，我们可以将我们的研究限制在相关部分。

void Test(uint64_t* a, uint64_t* b, uint64_t* ans, int n)
{
    for (int i = 0; i < n; ++i)
    {
        ans[i] = a[i] + b[i];
    }
}

现在，确实，当您使用现代版本的 GCC 编译它并看拆解，你会看到一堆看起来很疯狂的代码。

Godbolt 编译器资源管理器非常有用，它对 C 源代码行及其相应的汇编代码进行颜色编码（或者至少，它尽其所能；这在优化代码中并不完美，但它工作得足够好这里）。紫色代码是在循环内部实现 64 位加法的代码。 GCC 正在发出 SSE2 指令来进行加法。具体来说，你可以挑选MOVDQU（它将双四字从内存未对齐地移动到 XMM 寄存器中），PADDQ（对压缩整数四字进行加法），以及MOVQ（将一个四字从 XMM 寄存器移动到内存中）。粗略地说，对于非汇编专家来说，MOVDQU是它加载 64 位整数值的方式，PADDQ进行加法，然后MOVQ存储结果。

导致此输出特别嘈杂和令人困惑的部分原因是 GCC 是展开 the for环形。如果禁用循环展开（-fno-tree-vectorize）， 你得到更容易阅读的输出，尽管它仍然使用相同的指令做同样的事情。 （嗯，主要是。现在它正在使用MOVQ到处，对于加载和存储，而不是加载MOVDQU.)

另一方面，如果您明确禁止编译器使用 SSE2 指令（-mno-sse2), 您会看到输出明显不同。现在，因为它无法使用 SSE2 指令，所以它发出基本的 x86 指令来执行 64 位加法，而唯一的方法是ADD + ADC.

我怀疑这就是你的代码期待查看。显然，GCC 认为向量化操作会产生更快的代码，因此当您使用-O2 or -O3旗帜。在-O1，它总是使用ADD + ADC。这是指令较少并不意味着代码速度更快的情况之一。 （或者至少，GCC 不这么认为。实际代码的基准测试可能会讲述不同的故事。开销在某些人为场景中可能很大，但在现实世界中无关紧要。）

就其价值而言，Clang 的行为方式与 GCC 的行为方式非常相似。

如果您的意思是此代码不会将前一个加法的结果传递到下一个加法，那么您是对的。您显示的第二段代码实现了该算法，并且GCC 确实使用ADC操作说明.

至少，以 x86-32 为目标时是这样。当针对 x86-64 时，您有可用的本机 64 位整数寄存器，甚至不需要“进位”；simple ADD说明就足够了，要求显著地更少的代码。事实上，这只是 32 位架构上的“bigint”算术，这就是为什么我在前面的所有分析和编译器输出中都假设 x86-32。

在评论中，Ped7g 想知道为什么编译器似乎没有这个想法ADD+ADC连锁成语。我不完全确定他在这里指的是什么，因为他没有分享他尝试过的输入代码的任何示例，但正如我所展示的，编译器do use ADC说明请参见此处。但是，编译器不会跨循环迭代链接进位。这在实践中很难实现，因为有太多指令清除标志。手写汇编代码的人也许能够做到这一点，但编译器却做不到。

（注意c可能应该是一个unsigned整数以鼓励某些优化。在这种情况下，它只是确保 GCC 使用XOR准备进行 64 位加法而不是CDQ。虽然速度稍快，但不是huge改进，但里程可能会因实际代码而异。）

（此外，令人失望的是 GCC 无法发出用于设置的无分支代码c循环内部。如果输入值足够随机，分支预测就会失败，最终会得到效率相对较低的代码。几乎可以肯定有一些方法可以编写 C 源代码来说服 GCC 发出无分支代码，但这是一个完全不同的答案。）

我想学习如何嵌入内联（英特尔）汇编并做得更快。

好吧，我们已经看到，如果你天真地引起了一堆，它可能不一定会更快ADC发出的指令。除非您确信对性能的假设是正确的，否则不要手动优化！

此外，内联汇编不仅难以编写、调试和维护，而且甚至可能使代码变慢，因为它抑制了编译器本来可以完成的某些优化。您需要能够证明您的手工编码的程序集相对于编译器生成的程序集具有足够显着的性能优势，因此这些考虑因素变得不那么重要。您还应该确认没有办法让编译器生成接近理想输出的代码，无论是通过更改标志还是巧妙地编写 C 源代码。

But 如果你真的想，您可以阅读各种在线教程，教您如何使用 GCC 的内联汇编器。这是一个相当不错的;还有很多其他的。当然，还有手册。一切都会解释如何“扩展汇编”允许您指定输入操作数和输出操作数，这将回答您的问题“如何从 C++ 代码的其余部分将参数传递给汇编器”。

正如 Paddy 和 Christopher Oicles 所建议的，您应该更喜欢内在函数而不是内联汇编。不幸的是，没有任何内在因素会导致ADC发出的指令。内联汇编是您唯一的资源，或者我已经建议编写 C 源代码，以便编译器能够自行执行 Right Thing™。

有_addcarry_u32 and _addcarry_u64内在函数， 尽管。这些导致ADCX or ADOX发出的指令。这些是“扩展”版本ADC可以生成更高效的代码。它们是 Intel ADX 指令集的一部分，随 Broadwell 微架构一起引入。在我看来，Broadwell 的市场渗透率还不够高，您可以简单地发布ADCX or ADOX说明并到此为止。Lots的用户仍然拥有旧机器，尽可能支持它们符合您的利益。如果您正在准备针对特定架构进行调整的构建，那么它们非常有用，但我不建议将其用于一般用途。

我确信有 64 位操作码，相当于：add+adc

有 64 位版本ADD and ADC (and ADCX and ADOX）当您针对 64 位架构时。这将允许您使用相同的模式实现 128 位“bigint”算术。

在 x86-32 上，基本指令集中没有这些指令的 64 位版本。您必须转向 SSE2，就像我们看到 GCC 和 Clang 所做的那样。