25

我有一段时间试图提出一个不违反 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，我得到一个条件 where 32 - y = 32，它设置了未定义的行为。如果我添加检查if(y == 0) ...，则代码无法满足恒定时间要求。

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

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

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

如果GCC或Clang提供了在接近恒定的时间内执行旋转的内在函数，则不需要这些技巧。我什至会满足于“执行轮换”，因为他们甚至没有。

4

4 回答 4

12

我已经链接到这个答案以获取其他几个“轮换”问题的完整细节，包括这个社区维基问题，应该与最佳实践保持同步。

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

犹他大学的 John Regehr推荐了他尝试制作旋转功能的“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 在我之前独立提出了相同的想法，并将其发布在 gibhub 上。他的版本具有 C++ static_assert 检查，以使其在类型范围之外使用旋转计数成为编译时错误。

我用 gcc.godbolt.org 测试了我的，定义了 NDEBUG，用于变量和编译时常量旋转计数：

  • gcc：具有gcc >= 4.9.0的最佳代码，非分支 neg+shifts+ 或更早。
    （编译时常量计数：gcc 4.4.7 很好）
  • clang： clang >= 3.5.0的最佳代码，非分支 neg+shifts+or 更早。
    （编译时 const rotate count：clang 3.0 很好）
  • icc 13：最佳代码。
    （使用 -march=native 的编译时常量计数：生成速度较慢shld $7, %edi, %edi。没有也可以-march=native）

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

8 位和 16 位旋转有一些注意事项，但编译器在 32 位或 64 位时似乎n很好uint32_t。有关我测试各种宽度的uint*_t. 希望这个成语能被所有编译器更好地识别，以便在未来有更多的类型宽度组合。有时 gcc 会在旋转计数上无用地发出一个ANDinsn，即使 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_twhile 函数返回类型仍然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 对此进行测试，那么了解那里发生的情况将会很有用。

于 2015-07-18T05:38:17.220 回答
6

您可以添加一个额外的模运算来防止移位 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))));
}
于 2015-07-13T16:02:47.343 回答
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可以通过无条件调用来提高代码的“效率” 。

PS：我想知道是否有任何现实世界的平台可以更改右移的定义，以便x >> y何时y精确等于 的位大小x，需要产生 0 或 x，但可以任意选择（未指定）时尚，是否需要平台生成额外的代码，或者会排除在非人为场景中真正有用的优化？

于 2015-07-14T15:54:34.553 回答
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)));
}
于 2015-07-13T19:16:12.070 回答