使用 intel 内联汇编器对带进位的 bigint add 进行编码
Using intel inline assembler to code bigint add with carry
我想编写一个在大整数中添加 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];
}
不过，我想学习如何嵌入内联 (intel) 程序集，并且速度更快。
我确定有 64 位操作码，相当于：
add eax, ebx
adc ...
但我不知道如何将参数从其余的 c++ 代码传递给汇编器。
but the above does not work with carry.
如果你的意思是 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 和 look at the disassembly 编译它时，您会看到一堆看起来很疯狂的代码。
Godbolt 编译器资源管理器非常有用，它对 C 源代码行及其相应的汇编代码进行了颜色编码（或者至少，它尽其所能；这在优化代码中并不完美，但它在这里工作得很好）。紫色代码是在循环内部实现 64 位加法的代码。 GCC 发出 SSE2 指令来做加法。具体来说，您可以选择 MOVDQU (which does an unaligned move of a double quadword from memory into an XMM register), PADDQ (which does an addition on packed integer quadwords), and MOVQ（它将四字从 XMM 寄存器移动到内存中）。粗略地说，对于非汇编专家来说，MOVDQU 是加载 64 位整数值的方式，PADDQ 进行加法运算，然后 MOVQ 存储结果。
使此输出特别嘈杂和令人困惑的部分原因是 GCC 展开 for 循环。如果您禁用循环展开 (-fno-tree-vectorize)，您会得到 output that is easier to read，尽管它仍然使用相同的指令执行相同的操作。 （好吧，主要是。现在它到处都使用 MOVQ 来加载和存储，而不是使用 MOVDQU 加载。）
另一方面，如果您明确禁止编译器使用 SSE2 指令 (-mno-sse2)，则 you see output that is significantly different。现在，因为它不能使用 SSE2 指令，它发出基本的 x86 指令来进行 64 位加法——唯一的方法是 ADD + ADC.
我怀疑这是您期望看到的代码。显然，GCC 认为向量化操作会产生更快的代码，因此当您使用 -O2 或 -O3 标志进行编译时，它就是这样做的。在 -O1，它总是使用 ADD + ADC。这是其中一种情况，其中更少的指令并不意味着更快的代码。 （或者至少，GCC 不这么认为。实际代码的基准测试可能会讲述一个不同的故事。开销在某些人为的场景中可能很重要，但在现实世界中无关紧要。）
就其价值而言，Clang 的行为方式与此处的 GCC 非常相似。
如果您的意思是此代码不会将上一次加法的结果带到下一次加法，那么您是对的。您展示的第二段代码实现了该算法，GCC does compile this using the ADC instruction.
至少，它在针对 x86-32 时是这样。当以 x86-64 为目标时，您可以使用本机 64 位整数寄存器，甚至不需要 "carrying"； simple ADD instructions are sufficient，需要 显着 更少的代码。事实上，这只是 32 位架构上的 "bigint" 算法，这就是为什么我在前面的所有分析和编译器输出中都假定 x86-32。
在评论中，Ped7g 想知道为什么编译器似乎没有 ADD+ADC 链习惯用法的想法。我不完全确定他在这里指的是什么，因为他没有分享他尝试过的任何输入代码示例，但正如我所展示的，编译器 do 使用 ADC 说明在这里。但是，编译器不会跨循环迭代链接进位。这在实践中实现起来太困难了，因为太多的指令清除了标志。手写汇编代码的人可能能够做到，但编译器不会。
（请注意，c 可能应该是一个 无符号 整数以鼓励某些优化。在这种情况下，它只是确保 GCC 使用 XOR准备执行 64 位加法而不是 CDQ 时的指令。虽然速度稍快，但不是 巨大的 改进，但里程可能因实际代码而异。）
（此外，令人失望的是，GCC 无法发出用于在循环内设置 c 的无分支代码。如果输入值足够随机，分支预测将失败，并且最终效率相对较低代码。几乎肯定有一些方法可以编写 C 源代码来说服 GCC 发出无分支代码，但这是一个完全不同的答案。）
I would like to learn how to embed inline (intel) assembly and do it faster.
好吧，我们已经看到，如果您天真地发出一堆 ADC 指令，它不一定会更快。除非您确信您对性能的假设是正确的，否则不要手动优化！
此外，内联汇编不仅难以编写、调试和维护，而且甚至可能使您的代码变慢，因为它抑制了编译器本来可以完成的某些优化。您需要能够证明您的手工编码程序集在性能上足以胜过编译器生成的程序集，因此这些考虑因素变得不那么重要了。您还应该确认没有办法让编译器生成接近理想输出的代码，无论是通过更改标志还是巧妙地编写 C 源代码。
但是if you really wanted to, you could read any of a variety of online tutorials that teach you how to use GCC's inline assembler. This is a pretty good one; there are plenty of others. And of course, there is the manual. All will explain how "extended asm"允许您指定输入操作数和输出操作数，这将回答您"how to pass parameters to the assembler from the rest of the c++ code"的问题。
正如 paddy 和 Christopher Oicles 所建议的，您应该更喜欢内部函数而不是内联汇编。不幸的是，没有导致发出 ADC 指令的内在函数。内联汇编是您唯一的方法——或者我已经建议的编写 C 源代码以便编译器自己做正确的事。
有 _addcarry_u32 and _addcarry_u64 intrinsics, though. These cause ADCX or ADOX instructions to be emitted. 它们是英特尔 ADX 指令集的一部分，随 Broadwell 微体系结构引入。在我看来，Broadwell 没有足够高的市场渗透率，您可以简单地发出 ADCX 或 ADOX 指令并收工。 很多 用户仍然使用旧机器，尽可能支持它们符合您的利益。如果您正在准备针对特定架构调整的构建，它们会很棒，但我不建议将其用于一般用途。
I am sure there are 64 bit opcodes, the equivalent of: add+adc
当您面向 64 位架构时，有 64 位版本的 ADD 和 ADC（以及 ADCX 和 ADOX）。这将允许您使用相同的模式实现 128 位 "bigint" 算术。
在 x86-32 上，基本指令集中没有这些指令的 64 位版本。你必须求助于 SSE2，就像我们看到的 GCC 和 Clang 那样。
我不完全确定这是否是您要找的，而且我的组装技术绝对不是最好的（例如缺少后缀），但这使用 ADC 应该可以解决您的问题.
注意省略了 C++ for 循环；我们需要在 asm 中循环，因为我们需要 CF 才能在迭代中生存。 （GCC6 有标志输出约束，但没有标志输入；没有办法要求编译器将 FLAGS 从一个 asm 语句传递到另一个，并且 gcc 可能会低效地使用 setc/cmp 即使有它的语法。 )
#include <cstdint>
#include <iostream>
#define N 4
int main(int argc, char *argv[]) {
uint64_t ans[N];
const uint64_t a[N] = {UINT64_MAX, UINT64_MAX, 0, 0};
const uint64_t b[N] = {2, 1, 3, 1};
const uint64_t i = N;
asm volatile (
"xor %%eax, %%eax\n\t" // i=0 and clear CF
"mov %3, %%rdi\n\t" // N
".L_loop:\n\t"
"mov (%%rax,%1), %%rdx\n\t" // rdx = a[i]
"adc (%%rax,%2), %%rdx\n\t" // rdx += b[i] + carry
"mov %%rdx, (%%rax, %0)\n\t"// ans[i] = a[i] + b[i]
"lea 8(%%rax), %%rax\n\t" // i += 8 bytes
"dec %%rdi\n\t" // --i
"jnz .L_loop\n\t" // if (rdi == 0) goto .L_loop;
: /* Outputs (none) */
: /* Inputs */ "r" (ans), "r" (a), "r" (b), "r" (i)
: /* Clobbered */ "%rax", "%rbx", "%rdx", "%rdi", "memory"
);
// SHOULD OUTPUT 1 1 4 1
for (int i = 0; i < N; ++i)
std::cout << ans[i] << std::endl;
return 0;
}
为了避免设置carry flag (CF)，我需要倒数到0以避免做CMP。 DEC 没有设置 carry flag，因此它可能是此应用程序的完美竞争者。 但是，我不知道如何使用 %rdi 从数组开头索引比 inc %rax.[=36 所需的额外指令和寄存器更快=]
volatile 和 "memory" 破坏是必要的，因为我们只要求编译器提供指针输入，而不告诉它我们实际读取和写入的内存。
在一些较旧的 CPU 上，特别是 Core2 / Nehalem，inc 之后的 adc 将导致 partial-flag stall. See 。但在现代 CPU 上，这是高效的。
编辑：
正如 @PeterCordes 所指出的，我的 inc %rax 和使用 lea 缩放 8 的效率非常低（现在想想还是很愚蠢）。现在，它只是 lea 8(%rax), %rax.
编者注：我们可以通过使用从数组末尾开始的负索引来保存另一条指令，使用 inc / jnz.
向 0 计数
(这个 hard-codes 数组大小为 4。您可以通过要求数组长度作为立即常数，并将 -i 作为输入来使它更灵活。或者要求指针到最后。）
// untested
asm volatile (
"mov $-3, %[idx]\n\t" // i=-3 (which we will scale by 8)
"mov (%[a]), %%rdx \n\t"
"add (%[b]), %%rdx \n\t" // peel the first iteration so we don't have to zero CF first, and ADD is faster on some CPUs.
"mov %%rdx, (%0) \n\t"
".L_loop:\n\t" // do{
"mov 8*4(%[a], %[idx], 8), %%rdx\n\t" // rdx = a[i + len]
"adc 8*4(%[b], %[idx], 8), %%rdx\n\t" // rdx += b[i + len] + carry
"mov %%rdx, 8*4(%[ans], %[idx], 8)\n\t" // ans[i] = rdx
"inc %[idx]\n\t"
"jnz .L_loop\n\t" // }while (++i);
: /* Outputs, actually a read-write input */ [idx] "+&r" (i)
: /* Inputs */ [ans] "r" (ans), [a] "r" (a), [b] "r" (b)
: /* Clobbered */ "rdx", "memory"
);
循环标签应该使用 %%= 以防 GCC 复制此代码，或者使用像 1:
这样的带编号的本地标签
使用 scaled-index 寻址模式并不比我们之前使用的常规索引寻址模式（2 个寄存器）昂贵。理想情况下，我们会为 adc 或存储使用 one-register 寻址模式，可能通过减去输入上的指针来索引其他两个相对于 ans 的数组。
但是我们需要一个单独的 LEA 来增加 8，因为我们仍然需要避免破坏 CF。不过，在 Haswell 及更高版本上，索引存储不能在端口 7 上使用 AGU，并且 Sandybridge/Ivybridge 它们 un-laminate 到 2 微码。所以对于 Intel SnB-family，避免在此处使用索引存储会很好，因为每次迭代我们需要 2x 加载 + 1x 存储。参见 Micro fusion and addressing modes
较早的 Intel CPU (Core2 / Nehalem) 会在上述循环中出现 partial-flag 停顿，因此上述问题与它们无关。
AMD CPU 可能适用于上述循环。 Agner Fog's optimization and microarch guides不要提任何严重的问题。
不过，对 AMD 或 Intel 来说，展开一点也没什么坏处。
我想编写一个在大整数中添加 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];
}
不过，我想学习如何嵌入内联 (intel) 程序集，并且速度更快。 我确定有 64 位操作码，相当于：
add eax, ebx
adc ...
但我不知道如何将参数从其余的 c++ 代码传递给汇编器。
but the above does not work with carry.
如果你的意思是 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 和 look at the disassembly 编译它时，您会看到一堆看起来很疯狂的代码。
Godbolt 编译器资源管理器非常有用，它对 C 源代码行及其相应的汇编代码进行了颜色编码（或者至少，它尽其所能；这在优化代码中并不完美，但它在这里工作得很好）。紫色代码是在循环内部实现 64 位加法的代码。 GCC 发出 SSE2 指令来做加法。具体来说，您可以选择 MOVDQU (which does an unaligned move of a double quadword from memory into an XMM register), PADDQ (which does an addition on packed integer quadwords), and MOVQ（它将四字从 XMM 寄存器移动到内存中）。粗略地说，对于非汇编专家来说，MOVDQU 是加载 64 位整数值的方式，PADDQ 进行加法运算，然后 MOVQ 存储结果。
使此输出特别嘈杂和令人困惑的部分原因是 GCC 展开 for 循环。如果您禁用循环展开 (-fno-tree-vectorize)，您会得到 output that is easier to read，尽管它仍然使用相同的指令执行相同的操作。 （好吧，主要是。现在它到处都使用 MOVQ 来加载和存储，而不是使用 MOVDQU 加载。）
另一方面，如果您明确禁止编译器使用 SSE2 指令 (-mno-sse2)，则 you see output that is significantly different。现在，因为它不能使用 SSE2 指令，它发出基本的 x86 指令来进行 64 位加法——唯一的方法是 ADD + ADC.
我怀疑这是您期望看到的代码。显然，GCC 认为向量化操作会产生更快的代码，因此当您使用 -O2 或 -O3 标志进行编译时，它就是这样做的。在 -O1，它总是使用 ADD + ADC。这是其中一种情况，其中更少的指令并不意味着更快的代码。 （或者至少，GCC 不这么认为。实际代码的基准测试可能会讲述一个不同的故事。开销在某些人为的场景中可能很重要，但在现实世界中无关紧要。）
就其价值而言，Clang 的行为方式与此处的 GCC 非常相似。
如果您的意思是此代码不会将上一次加法的结果带到下一次加法，那么您是对的。您展示的第二段代码实现了该算法，GCC does compile this using the ADC instruction.
至少，它在针对 x86-32 时是这样。当以 x86-64 为目标时，您可以使用本机 64 位整数寄存器，甚至不需要 "carrying"； simple ADD instructions are sufficient，需要 显着 更少的代码。事实上，这只是 32 位架构上的 "bigint" 算法，这就是为什么我在前面的所有分析和编译器输出中都假定 x86-32。
在评论中，Ped7g 想知道为什么编译器似乎没有 ADD+ADC 链习惯用法的想法。我不完全确定他在这里指的是什么，因为他没有分享他尝试过的任何输入代码示例，但正如我所展示的，编译器 do 使用 ADC 说明在这里。但是，编译器不会跨循环迭代链接进位。这在实践中实现起来太困难了，因为太多的指令清除了标志。手写汇编代码的人可能能够做到，但编译器不会。
（请注意，c 可能应该是一个 无符号 整数以鼓励某些优化。在这种情况下，它只是确保 GCC 使用 XOR准备执行 64 位加法而不是 CDQ 时的指令。虽然速度稍快，但不是 巨大的 改进，但里程可能因实际代码而异。）
（此外，令人失望的是，GCC 无法发出用于在循环内设置 c 的无分支代码。如果输入值足够随机，分支预测将失败，并且最终效率相对较低代码。几乎肯定有一些方法可以编写 C 源代码来说服 GCC 发出无分支代码，但这是一个完全不同的答案。）
I would like to learn how to embed inline (intel) assembly and do it faster.
好吧，我们已经看到，如果您天真地发出一堆 ADC 指令，它不一定会更快。除非您确信您对性能的假设是正确的，否则不要手动优化！
此外，内联汇编不仅难以编写、调试和维护，而且甚至可能使您的代码变慢，因为它抑制了编译器本来可以完成的某些优化。您需要能够证明您的手工编码程序集在性能上足以胜过编译器生成的程序集，因此这些考虑因素变得不那么重要了。您还应该确认没有办法让编译器生成接近理想输出的代码，无论是通过更改标志还是巧妙地编写 C 源代码。
但是if you really wanted to, you could read any of a variety of online tutorials that teach you how to use GCC's inline assembler. This is a pretty good one; there are plenty of others. And of course, there is the manual. All will explain how "extended asm"允许您指定输入操作数和输出操作数，这将回答您"how to pass parameters to the assembler from the rest of the c++ code"的问题。
正如 paddy 和 Christopher Oicles 所建议的，您应该更喜欢内部函数而不是内联汇编。不幸的是，没有导致发出 ADC 指令的内在函数。内联汇编是您唯一的方法——或者我已经建议的编写 C 源代码以便编译器自己做正确的事。
有 _addcarry_u32 and _addcarry_u64 intrinsics, though. These cause ADCX or ADOX instructions to be emitted. ADCX 或 ADOX 指令并收工。 很多 用户仍然使用旧机器，尽可能支持它们符合您的利益。如果您正在准备针对特定架构调整的构建，它们会很棒，但我不建议将其用于一般用途。
I am sure there are 64 bit opcodes, the equivalent of:
add+adc
当您面向 64 位架构时，有 64 位版本的 ADD 和 ADC（以及 ADCX 和 ADOX）。这将允许您使用相同的模式实现 128 位 "bigint" 算术。
在 x86-32 上，基本指令集中没有这些指令的 64 位版本。你必须求助于 SSE2，就像我们看到的 GCC 和 Clang 那样。
我不完全确定这是否是您要找的，而且我的组装技术绝对不是最好的（例如缺少后缀），但这使用 ADC 应该可以解决您的问题.
注意省略了 C++ for 循环；我们需要在 asm 中循环，因为我们需要 CF 才能在迭代中生存。 （GCC6 有标志输出约束，但没有标志输入；没有办法要求编译器将 FLAGS 从一个 asm 语句传递到另一个，并且 gcc 可能会低效地使用 setc/cmp 即使有它的语法。 )
#include <cstdint>
#include <iostream>
#define N 4
int main(int argc, char *argv[]) {
uint64_t ans[N];
const uint64_t a[N] = {UINT64_MAX, UINT64_MAX, 0, 0};
const uint64_t b[N] = {2, 1, 3, 1};
const uint64_t i = N;
asm volatile (
"xor %%eax, %%eax\n\t" // i=0 and clear CF
"mov %3, %%rdi\n\t" // N
".L_loop:\n\t"
"mov (%%rax,%1), %%rdx\n\t" // rdx = a[i]
"adc (%%rax,%2), %%rdx\n\t" // rdx += b[i] + carry
"mov %%rdx, (%%rax, %0)\n\t"// ans[i] = a[i] + b[i]
"lea 8(%%rax), %%rax\n\t" // i += 8 bytes
"dec %%rdi\n\t" // --i
"jnz .L_loop\n\t" // if (rdi == 0) goto .L_loop;
: /* Outputs (none) */
: /* Inputs */ "r" (ans), "r" (a), "r" (b), "r" (i)
: /* Clobbered */ "%rax", "%rbx", "%rdx", "%rdi", "memory"
);
// SHOULD OUTPUT 1 1 4 1
for (int i = 0; i < N; ++i)
std::cout << ans[i] << std::endl;
return 0;
}
为了避免设置carry flag (CF)，我需要倒数到0以避免做CMP。 DEC 没有设置 carry flag，因此它可能是此应用程序的完美竞争者。 但是，我不知道如何使用 [=36 所需的额外指令和寄存器更快=]
%rdi 从数组开头索引比 inc %rax.
volatile 和 "memory" 破坏是必要的，因为我们只要求编译器提供指针输入，而不告诉它我们实际读取和写入的内存。
在一些较旧的 CPU 上，特别是 Core2 / Nehalem，inc 之后的 adc 将导致 partial-flag stall. See
编辑：
正如 @PeterCordes 所指出的，我的 inc %rax 和使用 lea 缩放 8 的效率非常低（现在想想还是很愚蠢）。现在，它只是 lea 8(%rax), %rax.
编者注：我们可以通过使用从数组末尾开始的负索引来保存另一条指令，使用 inc / jnz.
(这个 hard-codes 数组大小为 4。您可以通过要求数组长度作为立即常数，并将 -i 作为输入来使它更灵活。或者要求指针到最后。）
// untested
asm volatile (
"mov $-3, %[idx]\n\t" // i=-3 (which we will scale by 8)
"mov (%[a]), %%rdx \n\t"
"add (%[b]), %%rdx \n\t" // peel the first iteration so we don't have to zero CF first, and ADD is faster on some CPUs.
"mov %%rdx, (%0) \n\t"
".L_loop:\n\t" // do{
"mov 8*4(%[a], %[idx], 8), %%rdx\n\t" // rdx = a[i + len]
"adc 8*4(%[b], %[idx], 8), %%rdx\n\t" // rdx += b[i + len] + carry
"mov %%rdx, 8*4(%[ans], %[idx], 8)\n\t" // ans[i] = rdx
"inc %[idx]\n\t"
"jnz .L_loop\n\t" // }while (++i);
: /* Outputs, actually a read-write input */ [idx] "+&r" (i)
: /* Inputs */ [ans] "r" (ans), [a] "r" (a), [b] "r" (b)
: /* Clobbered */ "rdx", "memory"
);
循环标签应该使用 %%= 以防 GCC 复制此代码，或者使用像 1:
使用 scaled-index 寻址模式并不比我们之前使用的常规索引寻址模式（2 个寄存器）昂贵。理想情况下，我们会为 adc 或存储使用 one-register 寻址模式，可能通过减去输入上的指针来索引其他两个相对于 ans 的数组。
但是我们需要一个单独的 LEA 来增加 8，因为我们仍然需要避免破坏 CF。不过，在 Haswell 及更高版本上，索引存储不能在端口 7 上使用 AGU，并且 Sandybridge/Ivybridge 它们 un-laminate 到 2 微码。所以对于 Intel SnB-family，避免在此处使用索引存储会很好，因为每次迭代我们需要 2x 加载 + 1x 存储。参见 Micro fusion and addressing modes
较早的 Intel CPU (Core2 / Nehalem) 会在上述循环中出现 partial-flag 停顿，因此上述问题与它们无关。
AMD CPU 可能适用于上述循环。 Agner Fog's optimization and microarch guides不要提任何严重的问题。
不过，对 AMD 或 Intel 来说，展开一点也没什么坏处。