c++ - 如何在C++中使用处理器指令来实现快速算术运算

Question

我正在研究Shamir的 secret 共享方案的C++实现。我将消息分成8位的块，并在每个块上执行相应的算术运算。底层有限域是Rijndael的有限域F_256/(x ^ 8 + x ^ 4 + x ^ 3 + x + 1)。

我快速搜索了是否有用于Rijndael的有限域计算的知名且扩展的库(例如OpenSSL或类似的库)，但没有找到。因此，我从头开始实现了它，部分是作为编程练习。
但是，几天前，我们大学的一位教授提到:“现代处理器支持无进位整数运算，因此如今特征2有限域乘法运算速度很快。”

因此，由于我对硬件，汇编器和类似的东西知之甚少，所以我的问题是:在构建加密软件时，我实际上如何使用(在C++中)所有现代处理器的指令-无论是AES，SHA还是上面的算法还是其他？我找不到任何令人满意的资源。我的想法是建立一个同时包含“现代方法快速实现”和后备“纯C++无依赖代码”的库，并让GNU Autoconf决定在每个主机上使用哪个库。对此书的任何书籍/文章/教程建议将不胜感激。

Answer 1

这个问题很广泛，因为您可以通过多种方式访问​​底层硬件的功能，因此，这里列出了可以尝试使用所有现代处理器指令的方式，而不是一种特定的方式:

习语识别

用“长格式”写出C++中没有直接提供的操作，并希望您的编译器将其识别为所需基本指令的惯用法。例如，您可以编写一个变量，将x向左旋转，amount作为(x << amount) | (x >> (32 - amount))，将所有gcc, clang and icc will recognize this旋转作为旋转，并发出x86支持的底层rol指令。

有时，这种技术会使您感到有些不舒服:上面的C++旋转实现对amount == 0(以及amount >= 32)表现出不确定的行为，因为uint32_t移位32的结果是不确定的，但是这些编译器实际生成的代码在那种情况下就可以了。尽管如此，在程序中潜伏着未定义的行为还是很危险的，并且可能无法与ubsan和 friend 进行清晰的交流。备用安全版本amount ? (x << amount) | (x >> (32 - amount)) : x;仅由icc识别，而不能由gcc或clang识别。

这种方法往往适用于直接映射到已经存在了一段时间的汇编级指令的常见习语:旋转，位测试和设置，结果乘以比输入更宽的乘法(例如，将两个32位值乘以64位结果)，条件移动等，但不太可能选择加密技术也可能感兴趣的前沿指令。例如，我非常确定目前没有编译器会识别AES instruction set extensions的应用程序。由于必须手动添加每个公认的习惯用法，因此它也最适合在编译器开发人员付出了很多努力的平台上使用。

我认为此技术不适用于您的无进位乘法(PCLMULQDQ)，但可能有一天(如果您对编译器提出问题)？它确实可以用于其他“有趣的加密”功能，包括旋转。

内在函数

作为扩展，编译器通常会提供固有功能，这些功能不是语言本身的一部分，而是经常直接映射到大多数硬件提供的指令。尽管它看起来像一个函数调用，但编译器通常只在您调用的位置发出所需的一条指令。

GCC调用了这些内置函数，您可以找到generic ones here的列表。例如，如果当前目标支持，则可以使用__builtin_popcnt调用发出popcnt指令。 icc和clang也支持内置gcc的man，在这种情况下，只要体系结构(popcnt)设置为Haswell，所有gcc, clang and icc都支持此调用并发出-march=Haswell。否则，clang和icc使用一些巧妙的SWAR技巧内联替换版本，而gcc调用runtime1提供的__popcountdi2。

上面的内在函数列表是通用的，通常在编译器支持的任何平台上提供。您还可以找到特定于平台的指令，例如gcc的this list。

专门针对x86 SIMD指令，英特尔提供了一组intrinsic functions声明的 header ，用于覆盖其ISA扩展，例如，通过包含#include <x86intrin.h>。这些功能比gcc指令更广泛的支持，例如，Microsoft的Visual Studio编译器套件支持它们。通常会在支持它们的芯片可用之前添加新的指令集，因此您可以使用它们来在发布时立即访问新的指令。

使用SIMD内在函数进行编程是介于C++和完整汇编之间的一半。编译器仍会处理诸如调用约定和寄存器分配之类的事情，并进行了一些优化(特别是用于生成常量和其他广播)-但通常您编写的内容或多或少是在汇编级别获得的。

内联汇编

如果编译器提供了它，则可以使用内联汇编来调用所需的任何指令2。这与使用内部函数有很多相似之处，但是难度更高，优化器帮助您的机会也更少。除非您有内联汇编的特定原因，否则应使用probably prefer内部函数。一个示例可能是优化器在使用内在函数方面做得很糟糕:您可以使用内联汇编块来获取所需的确切代码。

离线装配

您也可以只用汇编语言编写整个内核函数，按需要进行汇编，然后将其声明为extern "C"并从C++进行调用。这类似于内联汇编选项，但适用于不支持内联汇编的编译器(例如64位Visual Studio)。如果需要，还可以使用其他汇编器，如果您要针对多个C++编译器，这将特别方便，因为您可以对所有这些使用单个汇编器。

您需要自己注意调用约定以及其他麻烦的事情，例如DWARF unwind info和Windows SEH handling。

对于功能非常短的函数，此方法效果不佳，因为调用开销可能会令人望而却步3。

自动向量化4

如果您想今天为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长度。与上述相同的C++代码使用-march=haswell编译会导致如下循环:

  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在vxorps寄存器上使用64字节的zmm指令(但gcc和icc坚持使用32字节的内部循环)。因此，原则上，您只需重新编译就可以利用新ISA的优势。

auto-vectorizatoin的缺点是它相当脆弱。在一个编译器上自动矢量化的内容可能不会在同一编译器的另一版本上，甚至在另一版本上也不会。因此，您需要检查是否获得了想要的结果。自动向量化器所处理的信息通常少于您所拥有的信息:它可能不知道输入长度是某些幂的倍数或两倍，或者输入指针是以某种方式对齐的。有时您可以将此信息传达给编译器，但有时则不能。

有时，编译器在向量化时会做出“有趣的”决定，例如为内循环使用一个小的未展开主体，然后再处理一个巨大的“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

您可能有更好的东西来花费指令缓存(这与我见过的最糟糕的情况相去甚远:很容易在前奏和后奏部分中获得包含数百条指令的示例)。

不幸的是，矢量化器可能不会产生特定于加密的指令，例如无进位乘法。您可以考虑将标量代码进行矢量化处理，然后将其仅作为编译器不会生成的指令的内在函数使用，但这比实际成功更容易提出。到那时，您最好用内在函数编写整个循环。

1这里的gcc方法的优点是，在运行时，如果平台支持popcnt，则该调用可以使用GNU IFUNC机制解析为仅使用popcnt指令的实现。

2假设底层的汇编程序支持它，但是即使不支持，您也可以在内联汇编块中对原始指令字节进行编码。

3调用开销不仅包含call和ret以及参数传递的显式开销:还包括对优化器的影响，该优化器无法在函数调用周围的调用方中优化代码，因为它具有未知的副作用。

4在某些方面，自动矢量化可以被视为成语识别的一种特殊情况，但是它很重要，并且具有足够的独特考虑，因此在这里可以找到自己的部分。

5差别很小:gcc如图所示，clang展开了一点，icc使用了加载操作pxor而不是单独的加载。