不违反标准的近恒定时间旋转

Question

我正在努力想出一个不违反 C/C++ 标准的恒定时间轮换。

问题出在 edge/corner 的情况下，在算法中调用操作并且无法更改这些算法。例如，以下内容来自 Crypto++ and executes the test harness under GCC ubsan（即 g++ fsanitize=undefined）：

$ ./cryptest.exe v | grep runtime
misc.h:637:22: runtime error: shift exponent 32 is too large for 32-bit type 'unsigned int'
misc.h:643:22: runtime error: shift exponent 32 is too large for 32-bit type 'unsigned int'
misc.h:625:22: runtime error: shift exponent 32 is too large for 32-bit type 'unsigned int'
misc.h:637:22: runtime error: shift exponent 32 is too large for 32-bit type 'unsigned int'
misc.h:643:22: runtime error: shift exponent 32 is too large for 32-bit type 'unsigned int'
misc.h:637:22: runtime error: shift exponent 32 is too large for 32-bit type 'unsigned int'

以及 misc.h:637 处的代码：

template <class T> inline T rotlMod(T x, unsigned int y)
{
    y %= sizeof(T)*8;
    return T((x<<y) | (x>>(sizeof(T)*8-y)));
}

Intel 的 ICC 特别狠，把整个函数调用都去掉了 y %= sizeof(T)*8。我们在几年前修复了这个问题，但由于缺少恒定时间解决方案而将其他勘误留在原地。

还有一个痛点。当 y = 0 时，我得到 32 - y = 32 的条件，它设置了未定义的行为。如果我添加了对if(y == 0) ...的检查，则代码无法满足恒定时间要求。

我看过许多其他实现，从 Linux 内核到其他加密库。它们都包含相同的未定义行为，因此它似乎是一个死胡同。

如何用最少的指令在几乎恒定的时间内执行循环？

编辑：按接近恒定时间，我的意思是避免分支所以相同指令总是被执行。我不担心 CPU 微码计时。虽然分支预测在 x86/x64 上可能很棒，但在其他平台（如嵌入式平台）上可能表现不佳。

如果 GCC or Clang provided an intrinsic to perform the ，则需要

None 个这些技巧。我什至满足于 "perform the rotate"，因为他们甚至没有。

Answer 1

您可以添加一个额外的模运算来防止移位 32 位，但我不认为这比将 if 检查与分支预测器结合使用更快。

template <class T> inline T rotlMod(T x, unsigned int y)
{
    y %= sizeof(T)*8;
    return T((x<<y) | (x>>((sizeof(T)*8-y) % (sizeof(T)*8))));
}

Answer 2

额外模数的替代方法是乘以 0 或 1（感谢 !!）：

template <class T> T rotlMod(T x, unsigned int y)
{
    y %= sizeof(T) * 8;
    return T((x << y) | (x >> ((!!y) * (sizeof(T) * 8 - y)));
}

Answer 3

将表达式写为 T((x<<y) | ((x>>(sizeof(T)*CHAR_BITS-y-1)>>1)) 应该会为位大小以下的所有 y 值产生定义的行为，假设 T 是无填充的无符号类型。除非编译器有一个好的优化器，否则生成的代码可能不如原始表达式生成的代码好。不得不忍受笨拙难读的代码，这会导致在许多编译器上执行速度变慢，这是进步的代价的一部分，但是，因为给定的超现代编译器

if (y) do_something();
return T((x<<y) | (x>>(sizeof(T)*8-y)));

可以通过无条件地调用 do_something 来改进代码的 "efficiency"。

PS：我想知道是否有任何现实世界的平台改变shift-right的定义使得x >> y当y正好等于位大小x，将需要产生 0 或 x，但可以以任意（未指定）的方式做出选择，将需要平台生成额外的代码或将排除真正有用的 在非人为场景中进行优化？

Answer 4

我已链接到此答案以获取其他几个 "rotate" 问题的完整详细信息，包括 this community wiki question，这些问题应与最佳实践保持同步。

我找到了一篇关于这个问题的博客 post，看起来它终于解决了（使用足够新的编译器版本）。

John Regehr at the University of Utah 推荐他尝试制作旋转功能的版本 "c"。我把他的assert换成按位AND，发现还是编译成一个rotate insn。

typedef uint32_t rotwidth_t;  // parameterize for comparing compiler output with various sizes

rotwidth_t rotl (rotwidth_t x, unsigned int n)
{
  const unsigned int mask = (CHAR_BIT*sizeof(x)-1);  // e.g. 31

  assert ( (n<=mask)  &&"rotate by type width or more");
  n &= mask;  // avoid undef behaviour with NDEBUG.  0 overhead for most types / compilers
  return (x<<n) | (x>>( (-n)&mask ));
}

rotwidth_t rot_const(rotwidth_t x)
{
  return rotl(x, 7);
}

这可以根据 x 的类型进行模板化，但在实际使用中可能更有意义，在函数名称中包含宽度（如 rotl32）。通常当你旋转时，你知道你想要什么宽度，这比你当前存储值的大小变量更重要。

还要确保只将它用于无符号类型。有符号类型的右移进行算术移位，移入符号位。（这在技术上是依赖于实现的行为，但现在一切都使用 2 的补码。）

Pabigot 在我之前独立提出了相同的想法，and posted it at gibhub。他的版本有 C++ static_assert 检查，使使用超出类型范围的循环计数成为编译时错误。

I tested mine with gcc.godbolt.org，定义了 NDEBUG，用于变量和编译时常量循环计数：

gcc：最优代码 gcc >= 4.9.0，非分支 neg+shifts+ 或更早版本。
（编译时常量计数：gcc 4.4.7 可以）
clang：clang >= 3.5.0、非分支 neg+shifts+ 或更早版本的最佳代码。
（编译时常量旋转计数：clang 3.0 可以）
icc 13: 最佳编码。
（使用 -march=native 的编译时常量计数：生成速度较慢 shld , %edi, %edi。没有 -march=native 很好）

即使较新的编译器版本也可以处理来自维基百科（包含在 godbolt 示例中）的常见代码，而无需生成分支或 cmov。 John Regehr 的版本具有在旋转计数为 0 时避免未定义行为的优点。

有一些关于 8 位和 16 位循环的注意事项，但当 n 为 uint32_t 时，编译器似乎可以处理 32 位或 64 位。有关我测试 uint*_t 的各种宽度的一些注释，请参阅 godbolt link 代码中的注释。希望这个习惯用法能被所有编译器更好地识别，以便将来有更多的类型宽度组合。有时 gcc 会在循环计数上无用地发出 AND insn，即使 x86 ISA 将循环 insns 定义为第一步

"optimal" 表示与：

一样高效

# gcc 4.9.2 rotl(unsigned int, unsigned int):
    movl    %edi, %eax
    movl    %esi, %ecx
    roll    %cl, %eax
    ret
# rot_const(unsigned int):
    movl    %edi, %eax
    roll    , %eax
    ret

在内联时，编译器应该能够首先将值安排在正确的寄存器中，从而只进行一次循环。

对于较旧的编译器，当循环计数是编译时常量时，您仍然可以获得理想的代码。 Godbolt 允许您以 ARM 作为目标进行测试，它也在那里使用了旋转。在较旧的编译器上使用变量计数，你会得到一些代码膨胀，但没有分支或主要的性能问题，所以这个习惯用法通常可以安全使用。

顺便说一句，我修改了 John Regehr 的原始代码以使用 CHAR_BIT*sizeof(x)，并且 gcc / clang / icc 也为 uint64_t 发出最佳代码。但是，我确实注意到将 x 更改为 uint64_t 而函数 return 类型仍然是 uint32_t 会使 gcc 将其编译为 shifts/or。因此，如果您想要 64b 旋转的低 32b，请小心将结果转换为单独序列点中的 32 位。即，将结果分配给一个 64 位变量，然后 cast/return 它。 icc 仍然会生成一个 rotate insn，但是 gcc 和 clang 不会，for

// generates slow code: cast separately.
uint32_t r = (uint32_t)( (x<<n) | (x>>( -n&(CHAR_BIT*sizeof(x)-1) )) );

如果有人可以使用 MSVC 对此进行测试，那么了解其中发生的情况将很有用。

不违反标准的近恒定时间旋转

Near constant time rotate that does not violate the standards

c++

bitwise-operators

undefined-behavior

constant-time