title: Near constant time rotate that does not violate the standards
body: <p>I'm having a heck of a time trying to come up with a constant time rotate that does not violate the C/C++ standards.</p>
  
  <p>The problem is the edge/corner cases, where operations are called out in algorithms and those algorithms cannot be changed. For example, the following is from <a href="http://www.cryptopp.com/" rel="noreferrer">Crypto++</a> and executes the test harness under <a href="http://developerblog.redhat.com/2014/10/16/gcc-undefined-behavior-sanitizer-ubsan/" rel="noreferrer">GCC ubsan</a> (i.e., <code>g++ fsanitize=undefined</code>):</p>
  
  <pre class="lang-none prettyprint-override"><code>$ ./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'
  </code></pre>
  
  <p>And the code at <code>misc.h:637</code>:</p>
  
  <pre class="lang-c++ prettyprint-override"><code>template &lt;class T&gt; inline T rotlMod(T x, unsigned int y)
  {
      y %= sizeof(T)*8;
      return T((x&lt;&lt;y) | (x&gt;&gt;(sizeof(T)*8-y)));
  }
  </code></pre>
  
  <p>Intel's ICC was particularly ruthless, and it removed the entire function call with out the <code>y %= sizeof(T)*8</code>. We fixed that a few years back, but left the other errata in-place due to lack of a constant time solution.</p>
  
  <p>There's one pain point remaining. When <code>y = 0</code>, I get a condition where <code>32 - y = 32</code>, and it sets up the undefined behavior. <em>If</em> I add a check for <code>if(y == 0) ...</code>, then the code fails to meet the constant time requirement.</p>
  
  <p>I've looked at  a number of other implementations, from the Linux kernel to other cryptographic libraries. They all contain the same undefined behavior, so it appears to be a dead end.</p>
  
  <p>How can I perform the rotate in nearly constant time with a minimum number of instructions?</p>
  
  <p><strong><em>EDIT</em></strong>: by <em>near constant time</em>, I mean avoid the branch so the same instructions are always executed. I'm not worried about CPU microcode timings. While branch prediction may be great on x86/x64, it may not perform as well on other platforms, like embedded.</p>
  
  <hr>
  
  <p>None of these tricks would be required if <a href="https://gcc.gnu.org/onlinedocs/gcc-5.2.0/gcc/" rel="noreferrer">GCC</a> or <a href="http://llvm.org/docs/LangRef.html#intrinsic-functions" rel="noreferrer">Clang</a> provided an intrinsic to perform the <a href="https://stackoverflow.com/q/31387778/608639">rotate in near constant time</a>. I'd even settle for "perform the rotate" since they don't even have that.</p>