如何在C++中使用处理器指令实现快速算术运算
How to use processor instructions in C++ to implement fast arithmetic operations
我正在研究 Shamir 的秘密共享方案的 C++ 实现。我将消息分成 8 位块，并在每个块上执行相应的算法。底层有限域是 Rijndael 的有限域 F_256 / (x^8 + x^4 + x^3 + x + 1).
我快速搜索了一些用于 Rijndael 有限域计算的知名和传播库（例如 OpenSSL 或类似库），但没有找到。所以我从头开始实现它，部分是作为编程练习。
然而前几天，我们大学的一位教授提到："Modern processors support carry-less integer operations, so the characteristic-2 finite field multiplications run fast nowadays.".
因此，由于我对硬件、汇编程序和类似东西知之甚少，我的问题是：在构建加密软件时，我如何实际使用（在 C++ 中）所有现代处理器的指令——无论是 AES， SHA，上面的算术还是其他什么？我找不到任何令人满意的资源。我的想法是构建一个包含以下两者的库："Modern-approach fast implementation" 和 fallback "pure C++ dependency-less code" 并让 GNU Autoconf 决定在每个主机上使用哪个。任何关于此主题的 book/article/tutorial 推荐都将不胜感激。
这个问题非常广泛，因为您可以通过多种方式访问底层硬件的强大功能，因此这里不是一种特定方式，而是您可以尝试 使用所有现代处理器的一系列方式' 说明:
成语识别
在 "long form" 中写出 C++ 中未直接提供的操作，并希望您的编译器将其识别为您想要的底层指令的习惯用法。例如，您可以将 x 左移 amount 的变量写为 (x << amount) | (x >> (32 - amount)) 并将所有 gcc, clang and icc will recognize this 写为旋转并发出支持的底层 rol 指令通过 x86.
有时这种技术会让您感到有点不舒服：上面的 C++ 旋转实现对 amount == 0（以及 amount >= 32 表现出 未定义的行为 ) 因为在 uint32_t 上移动 32 的结果是未定义的，但是 实际上 由 这些 编译器生成的代码就可以了在这种情况下。不过，在您的程序中存在这种潜伏的未定义行为是危险的，并且它可能不会 运行 清除 ubsan 和朋友。替代安全版本 amount ? (x << amount) | (x >> (32 - amount)) : x; 只能被 icc 识别，但不能被 gcc 或 clang 识别。
这种方法往往适用于直接映射到已经存在一段时间的 assembly-level 指令的常见习语：旋转、位测试和集合、结果比输入宽的乘法（例如，将两个相乘64 位结果的 32 位值），条件移动等，但不太可能获取密码学也可能感兴趣的前沿指令。例如，我很确定目前没有编译器可以识别 AES instruction set extensions 的应用程序。它在编译器开发人员付出大量努力的平台上也能发挥最佳效果，因为每个公认的习语都必须手动添加。
我认为这项技术不适用于您的 carry-less 乘法 (PCLMULQDQ)，但也许有一天（如果您向编译器提出问题）？它确实适用于其他 "crypt-interesting" 函数，包括旋转。
内函数
作为扩展，编译器通常会提供内部函数，它们不是语言本身的一部分，但通常直接映射到大多数硬件提供的指令。虽然它看起来像一个函数调用，但编译器通常只会在您调用它的地方发出所需的单个指令。
GCC 调用这些 built-in 函数 并且您可以找到 generic ones here. For example, you can use the __builtin_popcnt call to emit the popcnt instruction, if the current target supports it. Man of the gcc builtins are also supported by icc and clang, and in this case all of gcc, clang and icc 列表支持此调用并发出 popcnt 只要体系结构 (-march=Haswell) 设置为 Haswell。否则，clang 和 icc 使用一些巧妙的 SWAR 技巧内联替换版本，而 gcc 调用由 运行time1.[=53= 提供的 __popcountdi2 ]
上面的内在函数列表是通用的，通常在编译器支持的任何平台上提供。您还可以找到特定于平台的 instrinics，例如来自 gcc 的 this list。
专门针对 x86 SIMD 指令，英特尔提供了一组 intrinsic functions 声明的 headers 涵盖其 ISA 扩展，例如，通过包含 #include <x86intrin.h>。它们比 gcc 内部函数有更广泛的支持，例如，它们受 Microsoft 的 Visual Studio 编译器套件支持。新指令集通常在支持它们的芯片可用之前添加，因此您可以使用这些指令集在发布时立即访问新指令。
使用 SIMD 内部函数进行编程是 C++ 和完整汇编之间的折衷办法。编译器仍然会处理诸如调用约定和寄存器分配之类的事情，并且会进行一些优化（尤其是对于生成常量和其他广播）——但通常你写的或多或少是你写的进入装配层。
内联汇编
如果您的编译器提供它，您可以使用内联汇编来调用您想要的任何指令2。这与使用内部函数有很多相似之处，但难度更高，优化器帮助您的机会更少。你应该 probably prefer 内部函数，除非你有内联汇编的特定原因。一个例子可能是如果优化器在内部函数方面做得非常糟糕：您可以使用内联汇编块来准确获取您想要的代码。
Out-of-line大会
您也可以只用汇编编写整个内核函数，按照您的需要对其进行汇编，然后声明它 extern "C" 并从 C++ 中调用它。这类似于内联汇编选项，但适用于不支持内联汇编的编译器（例如，64 位 Visual Studio）。如果需要，您还可以使用不同的汇编器，如果您的目标是多个 C++ 编译器，这将特别方便，因为您可以为所有这些编译器使用一个汇编器。
您需要自己处理调用约定，以及其他诸如 DWARF unwind info and Windows SEH handling.
之类的乱七八糟的事情对于非常短的函数，这种方法效果不佳，因为调用开销可能会令人望而却步3.
Auto-Vectorization4
如果你今天想为 CPU 编写快速密码学，你将主要针对 SIMD 指令。大多数通过软件实现设计的新算法在设计时也考虑到了矢量化。
您可以使用内部函数或汇编来编写 SIMD 代码，但您也可以编写普通标量代码并依赖 auto-vectorizer。这些在 SIMD 的早期名声不好，虽然它们还远非完美，但它们已经走了很长一段路。
考虑这个简单的函数，将 payload 和 key 字节数组异或 key 到有效载荷中：
void otp_scramble(uint8_t* payload, uint8_t* key, size_t n) {
for (size_t i = 0; i < n; i++) {
payload[i] ^= key[i];
}
}
当然，这是一个垒球示例，但无论如何 gcc、clang 和 icc 都将其矢量化为 something like 这个内部循环4:
movdqu xmm0, XMMWORD PTR [rdi+rax]
movdqu xmm1, XMMWORD PTR [rsi+rax]
pxor xmm0, xmm1
movups XMMWORD PTR [rdi+rax], xmm0
它使用 SSE 指令一次加载和异或 16 个字节。然而，开发人员只需对简单的标量代码进行推理！
与内在函数或汇编相比，这种方法的一个优点是您不会在源代码级别烘焙指令集的 SIMD 长度。使用 -march=haswell 编译的与上面相同的 C++ 代码会导致如下循环：
vmovdqu ymm1, YMMWORD PTR [rdi+rax]
vpxor ymm0, ymm1, YMMWORD PTR [rsi+rax]
vmovdqu YMMWORD PTR [rdi+rax], ymm0
它使用 Haswell 上可用的 AVX2 指令一次处理 32 个字节。如果使用 -march=skylake-avx512 编译，clang 在 zmm 寄存器上使用 64 字节 vxorps 指令（但 gcc 和 icc 坚持使用 32 字节内部循环）。所以原则上你可以通过重新编译来利用新的 ISA。
auto-vectorizatoin 的缺点是它相当脆弱。一个编译器上的 auto-vectorizes 可能不在另一个编译器上，甚至在同一编译器的另一个版本上。所以你需要检查你是否得到了你想要的结果。 auto-vectorizer 处理的信息通常比您拥有的信息少：它可能不知道输入长度是某个幂或二次幂的倍数，或者输入指针以某种方式对齐。有时您可以将此信息传达给编译器，但有时您不能。
有时编译器在向量化时会做出 "interesting" 决定，例如内部循环的小 not-unrolled body，但随后是巨大的 "intro" 或 "outro" 处理奇数迭代，如 gcc 在上面显示的第一个循环后产生的结果：
movzx ecx, BYTE PTR [rsi+rax]
xor BYTE PTR [rdi+rax], cl
lea rcx, [rax+1]
cmp rdx, rcx
jbe .L1
movzx r8d, BYTE PTR [rsi+1+rax]
xor BYTE PTR [rdi+rcx], r8b
lea rcx, [rax+2]
cmp rdx, rcx
jbe .L1
movzx r8d, BYTE PTR [rsi+2+rax]
xor BYTE PTR [rdi+rcx], r8b
lea rcx, [rax+3]
cmp rdx, rcx
jbe .L1
movzx r8d, BYTE PTR [rsi+3+rax]
xor BYTE PTR [rdi+rcx], r8b
lea rcx, [rax+4]
cmp rdx, rcx
jbe .L1
movzx r8d, BYTE PTR [rsi+4+rax]
xor BYTE PTR [rdi+rcx], r8b
lea rcx, [rax+5]
cmp rdx, rcx
jbe .L1
movzx r8d, BYTE PTR [rsi+5+rax]
xor BYTE PTR [rdi+rcx], r8b
lea rcx, [rax+6]
cmp rdx, rcx
jbe .L1
movzx r8d, BYTE PTR [rsi+6+rax]
xor BYTE PTR [rdi+rcx], r8b
lea rcx, [rax+7]
cmp rdx, rcx
jbe .L1
movzx r8d, BYTE PTR [rsi+7+rax]
xor BYTE PTR [rdi+rcx], r8b
lea rcx, [rax+8]
cmp rdx, rcx
jbe .L1
movzx r8d, BYTE PTR [rsi+8+rax]
xor BYTE PTR [rdi+rcx], r8b
lea rcx, [rax+9]
cmp rdx, rcx
jbe .L1
movzx r8d, BYTE PTR [rsi+9+rax]
xor BYTE PTR [rdi+rcx], r8b
lea rcx, [rax+10]
cmp rdx, rcx
jbe .L1
movzx r8d, BYTE PTR [rsi+10+rax]
xor BYTE PTR [rdi+rcx], r8b
lea rcx, [rax+11]
cmp rdx, rcx
jbe .L1
movzx r8d, BYTE PTR [rsi+11+rax]
xor BYTE PTR [rdi+rcx], r8b
lea rcx, [rax+12]
cmp rdx, rcx
jbe .L1
movzx r8d, BYTE PTR [rsi+12+rax]
xor BYTE PTR [rdi+rcx], r8b
lea rcx, [rax+13]
cmp rdx, rcx
jbe .L1
movzx r8d, BYTE PTR [rsi+13+rax]
xor BYTE PTR [rdi+rcx], r8b
lea rcx, [rax+14]
cmp rdx, rcx
jbe .L1
movzx eax, BYTE PTR [rsi+14+rax]
xor BYTE PTR [rdi+rcx], al
你可能有更好的东西来使用你的指令缓存（这远非我见过的最糟糕的：在介绍和结尾部分很容易获得数百条指令的例子）。
不幸的是，向量化器可能不会生成 crypto-specific 指令，例如 carry-less 乘法。您可以考虑混合使用矢量化的标量代码和仅针对编译器不会生成的指令的内在代码，但这比实际成功更容易提出建议。到那时，您最好用内在函数编写整个循环。
1这里gcc方法的优点是在运行时间如果平台支持popcnt 此调用可以解析为仅使用 popcnt 指令的实现，使用 GNU IFUNC 机制。
2 假设底层汇编程序支持它，但即使它不支持，您也可以在内联汇编块中对原始指令字节进行编码。
3 调用开销不仅包括 call 和 ret 以及参数传递的显式成本：它还包括对优化器无法在函数调用周围的调用者中优化代码，因为它具有未知 side-effects.
4 在某些方面，auto-vectorization可以看作成语识别的一个特例，但它足够重要，有足够独特的考虑，所以它得到了它这里有自己的部分。
5 有细微差别：gcc 如图所示，clang 展开了一点，icc 使用了 load-op pxor 而不是单独加载。
我正在研究 Shamir 的秘密共享方案的 C++ 实现。我将消息分成 8 位块，并在每个块上执行相应的算法。底层有限域是 Rijndael 的有限域 F_256 / (x^8 + x^4 + x^3 + x + 1).
我快速搜索了一些用于 Rijndael 有限域计算的知名和传播库（例如 OpenSSL 或类似库），但没有找到。所以我从头开始实现它，部分是作为编程练习。 然而前几天，我们大学的一位教授提到："Modern processors support carry-less integer operations, so the characteristic-2 finite field multiplications run fast nowadays.".
因此，由于我对硬件、汇编程序和类似东西知之甚少，我的问题是：在构建加密软件时，我如何实际使用（在 C++ 中）所有现代处理器的指令——无论是 AES， SHA，上面的算术还是其他什么？我找不到任何令人满意的资源。我的想法是构建一个包含以下两者的库："Modern-approach fast implementation" 和 fallback "pure C++ dependency-less code" 并让 GNU Autoconf 决定在每个主机上使用哪个。任何关于此主题的 book/article/tutorial 推荐都将不胜感激。
这个问题非常广泛，因为您可以通过多种方式访问底层硬件的强大功能，因此这里不是一种特定方式，而是您可以尝试 使用所有现代处理器的一系列方式' 说明:
成语识别
在 "long form" 中写出 C++ 中未直接提供的操作，并希望您的编译器将其识别为您想要的底层指令的习惯用法。例如，您可以将 x 左移 amount 的变量写为 (x << amount) | (x >> (32 - amount)) 并将所有 gcc, clang and icc will recognize this 写为旋转并发出支持的底层 rol 指令通过 x86.
有时这种技术会让您感到有点不舒服：上面的 C++ 旋转实现对 amount == 0（以及 amount >= 32 表现出 未定义的行为 ) 因为在 uint32_t 上移动 32 的结果是未定义的，但是 实际上 由 这些 编译器生成的代码就可以了在这种情况下。不过，在您的程序中存在这种潜伏的未定义行为是危险的，并且它可能不会 运行 清除 ubsan 和朋友。替代安全版本 amount ? (x << amount) | (x >> (32 - amount)) : x; 只能被 icc 识别，但不能被 gcc 或 clang 识别。
这种方法往往适用于直接映射到已经存在一段时间的 assembly-level 指令的常见习语：旋转、位测试和集合、结果比输入宽的乘法（例如，将两个相乘64 位结果的 32 位值），条件移动等，但不太可能获取密码学也可能感兴趣的前沿指令。例如，我很确定目前没有编译器可以识别 AES instruction set extensions 的应用程序。它在编译器开发人员付出大量努力的平台上也能发挥最佳效果，因为每个公认的习语都必须手动添加。
我认为这项技术不适用于您的 carry-less 乘法 (PCLMULQDQ)，但也许有一天（如果您向编译器提出问题）？它确实适用于其他 "crypt-interesting" 函数，包括旋转。
内函数
作为扩展，编译器通常会提供内部函数，它们不是语言本身的一部分，但通常直接映射到大多数硬件提供的指令。虽然它看起来像一个函数调用，但编译器通常只会在您调用它的地方发出所需的单个指令。
GCC 调用这些 built-in 函数 并且您可以找到 generic ones here. For example, you can use the __builtin_popcnt call to emit the popcnt instruction, if the current target supports it. Man of the gcc builtins are also supported by icc and clang, and in this case all of gcc, clang and icc 列表支持此调用并发出 popcnt 只要体系结构 (-march=Haswell) 设置为 Haswell。否则，clang 和 icc 使用一些巧妙的 SWAR 技巧内联替换版本，而 gcc 调用由 运行time1.[=53= 提供的 __popcountdi2 ]
上面的内在函数列表是通用的，通常在编译器支持的任何平台上提供。您还可以找到特定于平台的 instrinics，例如来自 gcc 的 this list。
专门针对 x86 SIMD 指令，英特尔提供了一组 intrinsic functions 声明的 headers 涵盖其 ISA 扩展，例如，通过包含 #include <x86intrin.h>。它们比 gcc 内部函数有更广泛的支持，例如，它们受 Microsoft 的 Visual Studio 编译器套件支持。新指令集通常在支持它们的芯片可用之前添加，因此您可以使用这些指令集在发布时立即访问新指令。
使用 SIMD 内部函数进行编程是 C++ 和完整汇编之间的折衷办法。编译器仍然会处理诸如调用约定和寄存器分配之类的事情，并且会进行一些优化（尤其是对于生成常量和其他广播）——但通常你写的或多或少是你写的进入装配层。
内联汇编
如果您的编译器提供它，您可以使用内联汇编来调用您想要的任何指令2。这与使用内部函数有很多相似之处，但难度更高，优化器帮助您的机会更少。你应该 probably prefer 内部函数，除非你有内联汇编的特定原因。一个例子可能是如果优化器在内部函数方面做得非常糟糕：您可以使用内联汇编块来准确获取您想要的代码。
Out-of-line大会
您也可以只用汇编编写整个内核函数，按照您的需要对其进行汇编，然后声明它 extern "C" 并从 C++ 中调用它。这类似于内联汇编选项，但适用于不支持内联汇编的编译器（例如，64 位 Visual Studio）。如果需要，您还可以使用不同的汇编器，如果您的目标是多个 C++ 编译器，这将特别方便，因为您可以为所有这些编译器使用一个汇编器。
您需要自己处理调用约定，以及其他诸如 DWARF unwind info and Windows SEH handling.
之类的乱七八糟的事情对于非常短的函数，这种方法效果不佳，因为调用开销可能会令人望而却步3.
Auto-Vectorization4
如果你今天想为 CPU 编写快速密码学，你将主要针对 SIMD 指令。大多数通过软件实现设计的新算法在设计时也考虑到了矢量化。
您可以使用内部函数或汇编来编写 SIMD 代码，但您也可以编写普通标量代码并依赖 auto-vectorizer。这些在 SIMD 的早期名声不好，虽然它们还远非完美，但它们已经走了很长一段路。
考虑这个简单的函数，将 payload 和 key 字节数组异或 key 到有效载荷中：
void otp_scramble(uint8_t* payload, uint8_t* key, size_t n) {
for (size_t i = 0; i < n; i++) {
payload[i] ^= key[i];
}
}
当然，这是一个垒球示例，但无论如何 gcc、clang 和 icc 都将其矢量化为 something like 这个内部循环4:
movdqu xmm0, XMMWORD PTR [rdi+rax]
movdqu xmm1, XMMWORD PTR [rsi+rax]
pxor xmm0, xmm1
movups XMMWORD PTR [rdi+rax], xmm0
它使用 SSE 指令一次加载和异或 16 个字节。然而，开发人员只需对简单的标量代码进行推理！
与内在函数或汇编相比，这种方法的一个优点是您不会在源代码级别烘焙指令集的 SIMD 长度。使用 -march=haswell 编译的与上面相同的 C++ 代码会导致如下循环：
vmovdqu ymm1, YMMWORD PTR [rdi+rax]
vpxor ymm0, ymm1, YMMWORD PTR [rsi+rax]
vmovdqu YMMWORD PTR [rdi+rax], ymm0
它使用 Haswell 上可用的 AVX2 指令一次处理 32 个字节。如果使用 -march=skylake-avx512 编译，clang 在 zmm 寄存器上使用 64 字节 vxorps 指令（但 gcc 和 icc 坚持使用 32 字节内部循环）。所以原则上你可以通过重新编译来利用新的 ISA。
auto-vectorizatoin 的缺点是它相当脆弱。一个编译器上的 auto-vectorizes 可能不在另一个编译器上，甚至在同一编译器的另一个版本上。所以你需要检查你是否得到了你想要的结果。 auto-vectorizer 处理的信息通常比您拥有的信息少：它可能不知道输入长度是某个幂或二次幂的倍数，或者输入指针以某种方式对齐。有时您可以将此信息传达给编译器，但有时您不能。
有时编译器在向量化时会做出 "interesting" 决定，例如内部循环的小 not-unrolled body，但随后是巨大的 "intro" 或 "outro" 处理奇数迭代，如 gcc 在上面显示的第一个循环后产生的结果：
movzx ecx, BYTE PTR [rsi+rax]
xor BYTE PTR [rdi+rax], cl
lea rcx, [rax+1]
cmp rdx, rcx
jbe .L1
movzx r8d, BYTE PTR [rsi+1+rax]
xor BYTE PTR [rdi+rcx], r8b
lea rcx, [rax+2]
cmp rdx, rcx
jbe .L1
movzx r8d, BYTE PTR [rsi+2+rax]
xor BYTE PTR [rdi+rcx], r8b
lea rcx, [rax+3]
cmp rdx, rcx
jbe .L1
movzx r8d, BYTE PTR [rsi+3+rax]
xor BYTE PTR [rdi+rcx], r8b
lea rcx, [rax+4]
cmp rdx, rcx
jbe .L1
movzx r8d, BYTE PTR [rsi+4+rax]
xor BYTE PTR [rdi+rcx], r8b
lea rcx, [rax+5]
cmp rdx, rcx
jbe .L1
movzx r8d, BYTE PTR [rsi+5+rax]
xor BYTE PTR [rdi+rcx], r8b
lea rcx, [rax+6]
cmp rdx, rcx
jbe .L1
movzx r8d, BYTE PTR [rsi+6+rax]
xor BYTE PTR [rdi+rcx], r8b
lea rcx, [rax+7]
cmp rdx, rcx
jbe .L1
movzx r8d, BYTE PTR [rsi+7+rax]
xor BYTE PTR [rdi+rcx], r8b
lea rcx, [rax+8]
cmp rdx, rcx
jbe .L1
movzx r8d, BYTE PTR [rsi+8+rax]
xor BYTE PTR [rdi+rcx], r8b
lea rcx, [rax+9]
cmp rdx, rcx
jbe .L1
movzx r8d, BYTE PTR [rsi+9+rax]
xor BYTE PTR [rdi+rcx], r8b
lea rcx, [rax+10]
cmp rdx, rcx
jbe .L1
movzx r8d, BYTE PTR [rsi+10+rax]
xor BYTE PTR [rdi+rcx], r8b
lea rcx, [rax+11]
cmp rdx, rcx
jbe .L1
movzx r8d, BYTE PTR [rsi+11+rax]
xor BYTE PTR [rdi+rcx], r8b
lea rcx, [rax+12]
cmp rdx, rcx
jbe .L1
movzx r8d, BYTE PTR [rsi+12+rax]
xor BYTE PTR [rdi+rcx], r8b
lea rcx, [rax+13]
cmp rdx, rcx
jbe .L1
movzx r8d, BYTE PTR [rsi+13+rax]
xor BYTE PTR [rdi+rcx], r8b
lea rcx, [rax+14]
cmp rdx, rcx
jbe .L1
movzx eax, BYTE PTR [rsi+14+rax]
xor BYTE PTR [rdi+rcx], al
你可能有更好的东西来使用你的指令缓存（这远非我见过的最糟糕的：在介绍和结尾部分很容易获得数百条指令的例子）。
不幸的是，向量化器可能不会生成 crypto-specific 指令，例如 carry-less 乘法。您可以考虑混合使用矢量化的标量代码和仅针对编译器不会生成的指令的内在代码，但这比实际成功更容易提出建议。到那时，您最好用内在函数编写整个循环。
1这里gcc方法的优点是在运行时间如果平台支持popcnt 此调用可以解析为仅使用 popcnt 指令的实现，使用 GNU IFUNC 机制。
2 假设底层汇编程序支持它，但即使它不支持，您也可以在内联汇编块中对原始指令字节进行编码。
3 调用开销不仅包括 call 和 ret 以及参数传递的显式成本：它还包括对优化器无法在函数调用周围的调用者中优化代码，因为它具有未知 side-effects.
4 在某些方面，auto-vectorization可以看作成语识别的一个特例，但它足够重要，有足够独特的考虑，所以它得到了它这里有自己的部分。
5 有细微差别：gcc 如图所示，clang 展开了一点，icc 使用了 load-op pxor 而不是单独加载。