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

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

问题是边缘/角落情况，其中操作在算法中调用并且这些算法无法更改。例如，以下内容来自Crypto++并执行下面的测试工具海湾合作委员会乌桑 (i.e., 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我添加了一个检查if(y == 0) ...，那么该代码无法满足恒定时间要求。

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

如何使用最少的指令在几乎恒定的时间内执行旋转？

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

如果以下情况，则不需要这些技巧：GCC or Clang提供了一个内在的执行以接近恒定的时间旋转。我什至会选择“执行轮换”，因为他们甚至没有。

我已链接到此答案，以获取其他几个“旋转”问题的完整详细信息，包括这个社区维基问题，应与最佳实践保持同步。

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

约翰·雷格尔，犹他大学推荐他尝试制作旋转函数的版本“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 在我之前独立提出了同样的想法，并发布到github上。他的版本具有 C++ static_assert 检查，以使其在使用类型范围之外的循环计数时出现编译时错误。

I 使用 gcc.godbolt.org 测试了我的，定义了 NDEBUG，对于变量和编译时常量循环计数：

• gcc：最佳代码海湾合作委员会 >= 4.9.0，非分支 neg+shift+or 与较早的。
  （编译时 const 计数：gcc 4.4.7 就可以了）
• clang：最佳代码铿锵> = 3.5.0，非分支 neg+shift+or 与较早的。
  （编译时 const 循环计数：clang 3.0 就可以了）
• icc 13：最佳代码。
  （使用 -march=native 进行编译时 const 计数：生成速度较慢shld $7, %edi, %edi。没有就好-march=native)

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

8 位和 16 位循环有一些注意事项，但编译器似乎可以使用 32 位或 64 位，当n is uint32_t。参见代码中的注释神螺栓链接一些我测试各种宽度的笔记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 to uint64_t而函数返回类型仍然是uint32_t让 gcc 将其编译为移位/或。因此，如果您想要 64b 旋转的低 32b，请小心将结果转换为单独序列点中的 32 位。即，将结果分配给 64 位变量，然后转换/返回它。 icc 仍会生成旋转 insn，但 gcc 和 clang 不会生成，因为

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

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