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

Question

我有一段时间试图提出一个不违反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)));
}

英特尔的ICC特别无情,它删除了整个函数调用y %= sizeof(T)*8.几年前我们修复了这个问题,但由于缺乏恒定的时间解决方案而将其他勘误表留在了原位.

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

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

如何用最少的指令在几乎恒定的时间内完成旋转？

编辑:接近恒定时间,我的意思是避免分支,所以始终执行相同的指令.我并不担心CPU微码时序.虽然分支预测在x86/x64上可能很好,但在嵌入式等其他平台上可能效果不佳.

---

如果GCC或Clang提供了在近恒定时间内执行旋转的内在函数,则不需要这些技巧.我甚至满足于"执行旋转",因为他们甚至没有.

Answer 1

我已经将这个答案与其他几个"轮流"问题的全部细节联系起来,包括这个社区维基问题,该问题应该与最佳实践保持同步.

我发现了一篇关于这个问题的博客文章,看起来它终于解决了问题(使用足够新的编译器版本).

犹他大学的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,用于变量和编译时const旋转计数:

• gcc:最佳代码,gcc> = 4.9.0,非分支neg + shift +或更早.
  (编译时const数:gcc 4.4.7很好)
• clang:clang> = 3.5.0的最佳代码,非分支neg + shift +或更早的代码.
  (编译时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是uint32_t.请参阅godbolt链接代码中的注释,以获取我测试各种宽度的一些注释uint*_t.希望这个成语能够被所有编译器更好地识别,以便将来更多类型宽度的组合.有时候gcc会无用地AND在旋转计数上发出一个insn,即使x86 ISA定义旋转insn并使用精确的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

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

对于较旧的编译器,当旋转计数是编译时常量时,您仍将获得理想的代码.Godbolt让你用ARM作为目标进行测试,它也使用了旋转.对于较旧编译器的可变计数,您会得到一些代码膨胀,但没有分支或主要性能问题,因此这个习惯用法通常应该是安全的.

顺便说一下,我修改了John Regehr的原始版本以使用CHAR_BIT*sizeof(x),并且gcc/clang/icc uint64_t也会发出最佳代码.但是,我注意到更改x为uint64_t函数返回类型仍然uint32_t使gcc将其编译为shift /或.因此,如果您希望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测试这个,那么知道那里发生了什么会很有用.

Answer 2

你可以添加一个额外的模运算来防止32位的移位,但我不相信这比使用if check和branch预测器更快.

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))));
}