[ADT] Add llvm::rotl and llvm::rotr to bit.h

[RKSimon]

LGTM

[andrew.w.kaylor]

llvm/include/llvm/ADT/bit.h

366

This is dead code. Because you defined N as unsigned, R will be converted to unsigned for the % operation on line 361 and the result will never be negative. It gets the right answer anyway, but it doesn't seem to be what you intended.

As an example, in your test "llvm::rotl<uint8_t>(0x53, -5)" this will happen

N = 8u; (std::numeric_limits<uint8t>::digits)
R = 0xFFFFFFFB % 8u; (unsigned)R % N

So R = 3, and rotl(0x53, 3) yields 0x9A, as expected.

The point is, the code on lines 365-366 isn't doing anything. The same applies to lines 378-379 below.

This was reported by Coverity, BTW, which is why I happened to notice.

[kazu]

llvm/include/llvm/ADT/bit.h

366

Thank you for catching and reporting this! I'll post a follow-up patch to fix this.

llvm/include/llvm/ADT/bit.h

 /// Count the number of set bits in a value.
 /// Ex. popcount(0xF000F000) = 8
 /// Returns 0 if the word is zero.
 template <typename T, typename = std::enable_if_t<std::is_unsigned_v<T>>>
 [[nodiscard]] inline int popcount(T Value) noexcept {
   return detail::PopulationCounter<T, sizeof(T)>::count(Value);
 }
 
+// Forward-declare rotr so that rotl can use it.
+template <typename T, typename = std::enable_if_t<std::is_unsigned_v<T>>>
+[[nodiscard]] constexpr T rotr(T V, int R);
+
+template <typename T, typename = std::enable_if_t<std::is_unsigned_v<T>>>
+[[nodiscard]] constexpr T rotl(T V, int R) {
+  unsigned N = std::numeric_limits<T>::digits;
+
+  R = R % N;
+  if (!R)
+    return V;
+
+  if (R < 0)
+    return llvm::rotr(V, -R);
+
+  return (V << R) | (V >> (N - R));
+}
+
+template <typename T, typename> [[nodiscard]] constexpr T rotr(T V, int R) {
+  unsigned N = std::numeric_limits<T>::digits;
+
+  R = R % N;
+  if (!R)
+    return V;
+
+  if (R < 0)
+    return llvm::rotl(V, -R);
+
+  return (V >> R) | (V << (N - R));
+}
+
 } // namespace llvm
 
 #endif

llvm/unittests/ADT/BitTest.cpp

TEST(BitTest, PopCount) {
 
   EXPECT_EQ(32, llvm::popcount(~0U));
   EXPECT_EQ(64, llvm::popcount(~0ULL));
 
   for (int I = 0; I != 32; ++I)
     EXPECT_EQ(1, llvm::popcount(1U << I));
 }
 
+TEST(BitTest, Rotl) {
+  EXPECT_EQ(0x53U, llvm::rotl<uint8_t>(0x53, 0));
+  EXPECT_EQ(0x4dU, llvm::rotl<uint8_t>(0x53, 2));
+  EXPECT_EQ(0xa6U, llvm::rotl<uint8_t>(0x53, 9));
+  EXPECT_EQ(0x9aU, llvm::rotl<uint8_t>(0x53, -5));
+
+  EXPECT_EQ(0xabcdU, llvm::rotl<uint16_t>(0xabcd, 0));
+  EXPECT_EQ(0xf36aU, llvm::rotl<uint16_t>(0xabcd, 6));
+  EXPECT_EQ(0xaf36U, llvm::rotl<uint16_t>(0xabcd, 18));
+  EXPECT_EQ(0xf36aU, llvm::rotl<uint16_t>(0xabcd, -10));
+
+  EXPECT_EQ(0xdeadbeefU, llvm::rotl<uint32_t>(0xdeadbeef, 0));
+  EXPECT_EQ(0x7ddfbd5bU, llvm::rotl<uint32_t>(0xdeadbeef, 17));
+  EXPECT_EQ(0x5b7ddfbdU, llvm::rotl<uint32_t>(0xdeadbeef, 41));
+  EXPECT_EQ(0xb6fbbf7aU, llvm::rotl<uint32_t>(0xdeadbeef, -22));
+
+  EXPECT_EQ(0x12345678deadbeefULL, llvm::rotl<uint64_t>(0x12345678deadbeefULL, 0));
+  EXPECT_EQ(0xf56df77891a2b3c6ULL, llvm::rotl<uint64_t>(0x12345678deadbeefULL, 35));
+  EXPECT_EQ(0x8d159e37ab6fbbc4ULL, llvm::rotl<uint64_t>(0x12345678deadbeefULL, 70));
+  EXPECT_EQ(0xb7dde2468acf1bd5ULL, llvm::rotl<uint64_t>(0x12345678deadbeefULL, -19));
+}
+
+TEST(BitTest, Rotr) {
+  EXPECT_EQ(0x53U, llvm::rotr<uint8_t>(0x53, 0));
+  EXPECT_EQ(0xd4U, llvm::rotr<uint8_t>(0x53, 2));
+  EXPECT_EQ(0xa9U, llvm::rotr<uint8_t>(0x53, 9));
+  EXPECT_EQ(0x6aU, llvm::rotr<uint8_t>(0x53, -5));
+
+  EXPECT_EQ(0xabcdU, llvm::rotr<uint16_t>(0xabcd, 0));
+  EXPECT_EQ(0x36afU, llvm::rotr<uint16_t>(0xabcd, 6));
+  EXPECT_EQ(0x6af3U, llvm::rotr<uint16_t>(0xabcd, 18));
+  EXPECT_EQ(0x36afU, llvm::rotr<uint16_t>(0xabcd, -10));
+
+  EXPECT_EQ(0xdeadbeefU, llvm::rotr<uint32_t>(0xdeadbeef, 0));
+  EXPECT_EQ(0xdf77ef56U, llvm::rotr<uint32_t>(0xdeadbeef, 17));
+  EXPECT_EQ(0x77ef56dfU, llvm::rotr<uint32_t>(0xdeadbeef, 41));
+  EXPECT_EQ(0xbbf7ab6fU, llvm::rotr<uint32_t>(0xdeadbeef, -22));
+
+  EXPECT_EQ(0x12345678deadbeefULL, llvm::rotr<uint64_t>(0x12345678deadbeefULL, 0));
+  EXPECT_EQ(0x1bd5b7dde2468acfULL, llvm::rotr<uint64_t>(0x12345678deadbeefULL, 35));
+  EXPECT_EQ(0xbc48d159e37ab6fbULL, llvm::rotr<uint64_t>(0x12345678deadbeefULL, 70));
+  EXPECT_EQ(0xb3c6f56df77891a2ULL, llvm::rotr<uint64_t>(0x12345678deadbeefULL, -19));
+}
+
 } // anonymous namespace