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

我有一个时间试图想出一个恒定的时间旋转，不违反C / C ++标准。

问题是边缘/angular落情况，在algorithm中调用操作，这些algorithm不能改变。 例如，下面是来自Crypto ++并执行GCC ubsan下的testing工具（即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))); } 

英特尔的ICC是特别无情的，它取消了y %= sizeof(T)*8的整个函数调用。 几年前，我们修复了这个问题，但是由于缺乏一个固定的时间解决scheme，而将其他勘误留在了原地。

还有一个痛点。 当y = 0 ，我得到一个条件，其中32 - y = 32 ，并设置不确定的行为。 如果我添加检查if(y == 0) ... ，那么代码将无法满足常量时间要求。

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

我怎样才能以最less的指令执行几乎恒定的时间旋转？

编辑 ：由接近恒定的时间 ，我的意思是避免分支，所以相同的指示总是执行。 我不担心CPU微码的时间。 虽然分支预测在x86 / x64上可能会很好，但是在其他平台（如embedded式）上可能performance不佳。

---

如果海湾合作委员会或铿锵提供一个固有的执行在接近恒定的时间旋转 ，这些技巧都不需要。 我甚至会安排“执行旋转”，因为他们甚至没有这个。

Answer 1

我已经链接到这个答案，从其他几个“轮换”问题的全部细节，包括这个社区wiki的问题 ，应该保持最新的最佳做法。

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

犹他大学的约翰·雷格尔（John Regehr）build议他尝试制作旋转function的版本“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); // eg 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的types上进行模板化，但是对于真正的使用来说，在函数名中使用宽度（比如rotl32 ）可能更有意义。 通常当你旋转的时候，你知道你想要什么样的宽度，而不是你正在存储的值大小。

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

在我做之前，Pabigot独立地提出了相同的想法， 并将其发布在gibhub上 。 他的版本有C ++的static_assert检查，使其在编译时错误使用types范围以外的旋转计数。

我testing了我的gcc.godbolt.org ，用NDEBUG定义了variables和编译时常量循环计数：

• gcc： gcc> = 4.9.0的优化代码，non-branching neg + shift +或者更早。
  （编译时常量计数：gcc 4.4.7很好）
• clang： clang> = 3.5.0的优化代码，non-branching neg + shift +或者更早。
  （编译时const旋转计数：铿锵3.0罚款）
• icc 13：最佳代码。
  （使用-march = native的编译shld $7, %edi, %edi计数：生成较慢的shld $7, %edi, %edi without -march=native ）

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

有一些8和16位旋转的警告，但编译器似乎罚款32或64，当n是uint32_t 。 请参阅godbolt链接上代码中的注释，了解我testinguint*_t各种宽度的一些注释。 希望这个成语在将来能够被所有编译器更好地认可，以获得更多types宽度的组合。 有时候，gcc将无用地发出一个AND循环次数的insn，即使x86 ISA定义了旋转insns，并且将AND作为第一步。

“最优”意味着与以下一样高效：

 # 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 

在内联时，编译器应该能够将值首先安排在正确的寄存器中，只需要一次旋转。

对于较老的编译器，当rotate count是一个编译时常量时，你仍然可以得到理想的代码。 Godbolt可以让你testingARM作为目标，而且它也使用了旋转。 在旧的编译器上有可变的计数，你得到一些代码膨胀，但没有分支或主要的性能问题，所以这个习惯用法一般应该是安全的。

顺便说一句，我修改John Regehr的原始使用CHAR_BIT * sizeof（x），而gcc / clang / icc也发出uint64_t最佳代码。 不过，我注意到，当函数返回types仍然是uint32_t时，将x更改为uint64_t使得gcc将其编译为/或。 所以如果你想让一个64b的低32b旋转的话，注意在一个单独的序列点中将结果转换为32位。 即将结果分配给64位variables，然后投射/返回。 icc仍然会产生一个循环insn，但是gcc和clang不会

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

如果任何人都可以用MSVC来testing这个，那么知道那里会发生什么是有用的。

Answer 2

您可以添加一个额外的模数操作，以防止移位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 3

将expression式写为T((x<<y) | ((x>>(sizeof(T)*CHAR_BITS-y-1)>>1))应该产生所有低于位大小的y值的行为T是没有填充的无符号types，除非编译器有一个好的优化器，否则得到的代码可能不如原来的expression式所产生的那么好，不得不忍受笨重的难以读取的代码，然而，许多编译器执行速度较慢是进程价格的一部分，因为这是一个超现代的编译器

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

可以通过调用do_something无条件来提高代码的“效率”。

PS：我想知道是否有真实世界的平台在改变右移的定义，使得x >> y当y正好等于x的位大小时，需要产生0或x，但是可以以任意的（未指定的）方式做出select，会要求平台生成额外的代码，否则会妨碍在非devise的情况下进行真正有用的优化？

Answer 4

一个替代的额外模是乘以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))); }