avoid undefined behaviour when n==0

ISO/IEC 9899:1999 section 6.5.7 states that "If the value of the right
operand is negative or is greater than or equal to the width of the
promoted left operand, the behavior is undefined".  So we have to take
care of such situations.

This has not been a problem because contemporary C compilers are
extraordinary smart to compile the series of shifts into a single
ROTLQ/ROTRQ machine instruction.  In contrast to what C says those
instructions have fully defined behaviour for all possible inputs.
Hence it has been quite difficult to observe the undefined-ness of such
situations.  But undefined is undefined.  We should not rely on such
target-specific assumptions.

We are fixing the situation by carefully avoiding shifts with out-of-
range values.  At least GCC since 4.6.3 and Clang since 8.0 can issue
the exact same instructions like before the changeset.

Also in case of Intel processors, there supposedly be intrinsics named
_rotr/_rotl that do exactly what we need.  They, in practice, are absent
on Clang before 9.x so we cannot blindly use.  But we can at least save
MSVC.

See also:
https://gcc.gnu.org/bugzilla/show_bug.cgi?id=57157
https://bugs.llvm.org/show_bug.cgi?id=17332

1 files changed, 49 insertions, 7 deletions

diff --git a/internal/bits.h b/internal/bits.h
index 1016f31803..52da71264c 100644
--- a/internal/bits.h
+++ b/internal/bits.h
@@ -15,12 +15,16 @@
  * @see        https://clang.llvm.org/docs/LanguageExtensions.html#builtin-rotateleft
  * @see        https://clang.llvm.org/docs/LanguageExtensions.html#builtin-rotateright
  * @see        https://docs.microsoft.com/en-us/cpp/c-runtime-library/reference/byteswap-uint64-byteswap-ulong-byteswap-ushort
+ * @see        https://docs.microsoft.com/en-us/cpp/c-runtime-library/reference/rotl-rotl64-rotr-rotr64
  * @see        https://docs.microsoft.com/en-us/cpp/intrinsics/bitscanforward-bitscanforward64
  * @see        https://docs.microsoft.com/en-us/cpp/intrinsics/bitscanreverse-bitscanreverse64
  * @see        https://docs.microsoft.com/en-us/cpp/intrinsics/lzcnt16-lzcnt-lzcnt64
  * @see        https://docs.microsoft.com/en-us/cpp/intrinsics/popcnt16-popcnt-popcnt64
  * @see        https://software.intel.com/sites/landingpage/IntrinsicsGuide/#text=_lzcnt_u32
  * @see        https://software.intel.com/sites/landingpage/IntrinsicsGuide/#text=_tzcnt_u32
+ * @see        https://software.intel.com/sites/landingpage/IntrinsicsGuide/#text=_rotl64
+ * @see        https://software.intel.com/sites/landingpage/IntrinsicsGuide/#text=_rotr64
+ * @see        https://stackoverflow.com/a/776523
  */
 #include "ruby/config.h"
 #include <limits.h>             /* for CHAR_BITS */
@@ -31,13 +35,33 @@
 # include <stdlib.h>            /* for _byteswap_uint64 */
 #endif
 
-#if defined(__x86_64__) && defined(__LZCNT__) && ! defined(MJIT_HEADER)
+#if defined(HAVE_X86INTRIN_H) && ! defined(MJIT_HEADER)
 # /* Rule out MJIT_HEADER, which does not interface well with <immintrin.h> */
-# include <immintrin.h>         /* for _lzcnt_u64 */
+# include <x86intrin.h>         /* for _lzcnt_u64 */
+#elif MSC_VERSION_SINCE(1310)
+# include <intrin.h>            /* for the following intrinsics */
+#endif
+
+#if defined(_MSC_VER) && defined(__AVX__)
+# pragma intrinsic(__popcnt)
+# pragma intrinsic(__popcnt64)
+#endif
+
+#if defined(_MSC_VER) && defined(__AVX2__)
+# pragma intrinsic(__lzcnt)
+# pragma intrinsic(__lzcnt64)
+#endif
+
+#if MSC_VERSION_SINCE(1310)
+# pragma intrinsic(_rotl)
+# pragma intrinsic(_rotr)
+# ifdef _WIN64
+#  pragma intrinsic(_rotl64)
+#  pragma intrinsic(_rotr64)
+# endif
 #endif
 
 #if MSC_VERSION_SINCE(1400)
-# include <intrin.h>            /* for the following intrinsics */
 # pragma intrinsic(_BitScanForward)
 # pragma intrinsic(_BitScanReverse)
 # ifdef _WIN64
@@ -500,9 +524,18 @@ RUBY_BIT_ROTL(VALUE v, int n)
 #elif __has_builtin(__builtin_rotateleft64) && (SIZEOF_VALUE * CHAR_BIT == 64)
     return __builtin_rotateleft64(v, n);
 
+#elif MSC_VERSION_SINCE(1310) && (SIZEOF_VALUE * CHAR_BIT == 32)
+    return _rotl(v, n);
+
+#elif MSC_VERSION_SINCE(1310) && (SIZEOF_VALUE * CHAR_BIT == 64)
+    return _rotl64(v, n);
+
+#elif defined(_lrotl) && (SIZEOF_VALUE == SIZEOF_LONG)
+    return _lrotl(v, n);
+
 #else
-    const int m = sizeof(VALUE) * CHAR_BIT;
-    return (v << n) | (v >> (m - n));
+    const int m = (sizeof(VALUE) * CHAR_BIT) - 1;
+    return (v << (n & m)) | (v >> (-n & m));
 #endif
 }
 
@@ -515,9 +548,18 @@ RUBY_BIT_ROTR(VALUE v, int n)
 #elif __has_builtin(__builtin_rotateright64) && (SIZEOF_VALUE * CHAR_BIT == 64)
     return __builtin_rotateright64(v, n);
 
+#elif MSC_VERSION_SINCE(1310) && (SIZEOF_VALUE * CHAR_BIT == 32)
+    return _rotr(v, n);
+
+#elif MSC_VERSION_SINCE(1310) && (SIZEOF_VALUE * CHAR_BIT == 64)
+    return _rotr64(v, n);
+
+#elif defined(_lrotr) && (SIZEOF_VALUE == SIZEOF_LONG)
+    return _lrotr(v, n);
+
 #else
-    const int m = sizeof(VALUE) * CHAR_BIT;
-    return (v << (m - n)) | (v >> n);
+    const int m = (sizeof(VALUE) * CHAR_BIT) - 1;
+    return (v << (-n & m)) | (v >> (n & m));
 #endif
 }