我花了很长时间试图提出一个不违反 C/C++ 标准的恒定时间轮换。

问题是边缘/角落的情况，其中操作在算法中被调用并且这些算法无法更改。例如，以下来自 Crypto++并在 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 则不需要这些技巧或 Clang提供了执行 rotate in near constant time 的内在函数.我什至会满足于“执行旋转”，因为他们甚至没有。

最佳答案

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

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

John Regehr at the University of Utah推荐他尝试制作旋转功能的版本“c”。我用按位 AND 替换了他的断言，发现它仍然编译为单个旋转 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 检查，以使其在类型范围之外使用旋转计数成为编译时错误。

我 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+或更早的最佳代码。
  (编译时 const rotate count:clang 3.0 很好)
• icc 13:最优代码。
  (使用 -march=native 的编译时常量计数:生成较慢的 shld $7, %edi, %edi。没有 -march=native 也可以)

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

对于 8 位和 16 位旋转有一些注意事项，但是当 n 为 uint32_t 时，编译器对于 32 位或 64 位似乎没问题。请参阅 godbolt link 上的代码中的注释对于我测试各种宽度的 uint*_t 的一些笔记。希望这个成语能被所有编译器更好地识别，以便在未来有更多的类型宽度组合。有时 gcc 会在旋转计数上无用地发出 AND insn，即使 x86 ISA 使用该精确 AND 作为第一步定义了旋转 insn。

“最佳”意味着高效:

# 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    $7, %eax
    ret

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

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

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

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

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

关于c++ - 不违反标准的近恒定时间旋转，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/31387778/