[libc++] Fix the signature of std::rotl and std::rotr

[DKay7]

Summary

• Changed parameters type in std::rotr and std::rorl functions from unsigned int to int.
• Implemented behaviour for negative parameter values.

Fixes #64544

[philnik]

Please add tests in libcxx/test/std/numerics/bit/bitops.rot/rotr.pass.cpp for this change.

libcxx/include/__bit/rotate.h

47

We might also want to fix __rotr, depending on where it is used. Generally, the underscore versions should have the same semantics as non-underscore versions.

[DKay7]

In D157569#4575253, @philnik wrote:

We might also want to fix __rotr, depending on where it is used. Generally, the underscore versions should have the same semantics as non-underscore versions.

I implemented the behavior for negative values in __rotr and thought that now std::rotl and std::rotr could be implemented as follows:

template <__libcpp_unsigned_integer _Tp>
[[nodiscard]] _LIBCPP_HIDE_FROM_ABI constexpr _Tp rotl(_Tp __t, int __cnt) noexcept {
    return std::__rotr(__t, -__cnt);
}

template <__libcpp_unsigned_integer _Tp>
[[nodiscard]] _LIBCPP_HIDE_FROM_ABI constexpr _Tp rotr(_Tp __t, int __cnt) noexcept {
  return std::__rotr(__t, __cnt);
}

This works for positive values, because rotl is the same as rotr with a negative value and vice versa. However, it doesn't seem very obvious and might be even confusing, so I wanted to find out if it's worth doing so. Thank you.

[DKay7]

• Added unit-tests for std::rotr and std::rorl with negative values.
• Rewrited std::__rotr as @philnik asked.
• Rewrited std::rotr and std::rorl via new std::__rotr, but not sure if new implementations are not confusing.

[philnik]

libcxx/include/__bit/rotate.h

40–41

It looks like your patch is missing the last commit. I'd recommend squashing the two into one and upload the resulting patch again.

[DKay7]

Updating D157569: Fixed issue #64544 ([libc++] std::rotl and std::rotr have the wrong signature)

• Squashed two last commits into one

[philnik]

It looks like __bit/rotate.h is now formatted. Please remove it from libcxx/utils/data/ignore_format.txt.

LGTM with passing CI.

I guess you don't have commit access? In that case, please provide "Your Name" <your.email@address> for attribution.

[DKay7]

Removed __bit/rotate.h from libcxx/utils/data/ignore_format.txt

• My name and email (as @philnik asked): "Daniil Kalinin" [e-mail]

#Updating D157569: [libc++] Fix the signature of std::rotl and std::rotr

[DKay7]

AIX build has failed with "There is not enough space in the file system" error. Actually, I have no idea how to deal with it.

[philnik]

In D157569#4581910, @DKay7 wrote:

AIX build has failed with "There is not enough space in the file system" error. Actually, I have no idea how to deal with it.

The AIX builders are currently broken. You've done nothing wrong.

libcxx/include/__bit/rotate.h

 #include <limits>
 
 #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
 #  pragma GCC system_header
 #endif
 
 _LIBCPP_BEGIN_NAMESPACE_STD
 
-template<class _Tp>
-_LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX14
-_Tp __rotr(_Tp __t, unsigned int __cnt) _NOEXCEPT
-{
-    static_assert(__libcpp_is_unsigned_integer<_Tp>::value, "__rotr requires an unsigned integer type");
-    const unsigned int __dig = numeric_limits<_Tp>::digits;
-    if ((__cnt % __dig) == 0)
-        return __t;
-    return (__t >> (__cnt % __dig)) | (__t << (__dig - (__cnt % __dig)));
+template <class _Tp>
+_LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX14 _Tp __rotr(_Tp __t, int __cnt) _NOEXCEPT {
+
+  if (__cnt < 0) {
+    __cnt *= -1;
+    return (__t << (__cnt % __dig)) | (__t >> (__dig - (__cnt % __dig))); // rotr with negative __cnt is similar to rotl
+  }
+
 }
 
 #if _LIBCPP_STD_VER >= 20
 
 template <__libcpp_unsigned_integer _Tp>
-[[nodiscard]] _LIBCPP_HIDE_FROM_ABI constexpr _Tp rotl(_Tp __t, unsigned int __cnt) noexcept {
-  const unsigned int __dig = numeric_limits<_Tp>::digits;
-  if ((__cnt % __dig) == 0)
-    return __t;
-  return (__t << (__cnt % __dig)) | (__t >> (__dig - (__cnt % __dig)));
+[[nodiscard]] _LIBCPP_HIDE_FROM_ABI constexpr _Tp rotl(_Tp __t, int __cnt) noexcept {
+  return std::__rotr(__t, -__cnt);
 }
 
 template <__libcpp_unsigned_integer _Tp>
-[[nodiscard]] _LIBCPP_HIDE_FROM_ABI constexpr _Tp rotr(_Tp __t, unsigned int __cnt) noexcept {
+[[nodiscard]] _LIBCPP_HIDE_FROM_ABI constexpr _Tp rotr(_Tp __t, int __cnt) noexcept {
   return std::__rotr(__t, __cnt);
 }
 
 #endif // _LIBCPP_STD_VER >= 20
 
 _LIBCPP_END_NAMESPACE_STD
 
 #endif // _LIBCPP___BIT_ROTATE_H

libcxx/include/bit

template <class T>
     constexpr T bit_ceil(T x);                   // C++20
   template <class T>
     constexpr T bit_floor(T x) noexcept;         // C++20
   template <class T>
     constexpr int bit_width(T x) noexcept;       // C++20
 
   // [bit.rotate], rotating
   template<class T>
-    constexpr T rotl(T x, unsigned int s) noexcept; // C++20
+    constexpr T rotl(T x, int s) noexcept; // C++20
   template<class T>
-    constexpr T rotr(T x, unsigned int s) noexcept; // C++20
+    constexpr T rotr(T x, int s) noexcept; // C++20
 
   // [bit.count], counting
   template<class T>
     constexpr int countl_zero(T x) noexcept;  // C++20
   template<class T>
     constexpr int countl_one(T x) noexcept;   // C++20
   template<class T>
     constexpr int countr_zero(T x) noexcept;  // C++20

libcxx/test/std/numerics/bit/bitops.rot/rotl.pass.cpp

 enum class E2 : unsigned char { red };
 
 template <class T>
 constexpr bool test()
 {
     ASSERT_SAME_TYPE(decltype(std::rotl(T(), 0)), T);
     ASSERT_NOEXCEPT(std::rotl(T(), 0));
     T max = std::numeric_limits<T>::max();
+    T highbit = std::rotr(T(1), 1);
 
     assert(std::rotl(T(max - 1), 0) == T(max - 1));
     assert(std::rotl(T(max - 1), 1) == T(max - 2));
     assert(std::rotl(T(max - 1), 2) == T(max - 4));
     assert(std::rotl(T(max - 1), 3) == T(max - 8));
     assert(std::rotl(T(max - 1), 4) == T(max - 16));
     assert(std::rotl(T(max - 1), 5) == T(max - 32));
     assert(std::rotl(T(max - 1), 6) == T(max - 64));
     assert(std::rotl(T(max - 1), 7) == T(max - 128));
 
+    assert(std::rotl(T(max - 1), -1) == T(max - highbit));
+    assert(std::rotl(T(max - 1), -2) == T(max - (highbit >> 1)));
+    assert(std::rotl(T(max - 1), -3) == T(max - (highbit >> 2)));
+    assert(std::rotl(T(max - 1), -4) == T(max - (highbit >> 3)));
+    assert(std::rotl(T(max - 1), -5) == T(max - (highbit >> 4)));
+    assert(std::rotl(T(max - 1), -6) == T(max - (highbit >> 5)));
+    assert(std::rotl(T(max - 1), -7) == T(max - (highbit >> 6)));
+
     assert(std::rotl(T(1), 0) == T(1));
     assert(std::rotl(T(1), 1) == T(2));
     assert(std::rotl(T(1), 2) == T(4));
     assert(std::rotl(T(1), 3) == T(8));
     assert(std::rotl(T(1), 4) == T(16));
     assert(std::rotl(T(1), 5) == T(32));
     assert(std::rotl(T(1), 6) == T(64));
     assert(std::rotl(T(1), 7) == T(128));
 
+    assert(std::rotl(T(128), -1) == T(64));
+    assert(std::rotl(T(128), -2) == T(32));
+    assert(std::rotl(T(128), -3) == T(16));
+    assert(std::rotl(T(128), -4) == T(8));
+    assert(std::rotl(T(128), -5) == T(4));
+    assert(std::rotl(T(128), -6) == T(2));
+    assert(std::rotl(T(128), -7) == T(1));
+
 #ifndef TEST_HAS_NO_INT128
     if constexpr (std::is_same_v<T, __uint128_t>) {
         T val = (T(1) << 63) | (T(1) << 64);
         assert(std::rotl(val, 0) == val);
         assert(std::rotl(val, 128) == val);
         assert(std::rotl(val, 256) == val);
         assert(std::rotl(val, 1) == val << 1);
         assert(std::rotl(val, 127) == val >> 1);
         assert(std::rotl(T(3), 127) == ((T(1) << 127) | T(1)));
+
+        assert(std::rotl(val, -128) == val);
+        assert(std::rotl(val, -256) == val);
+        assert(std::rotl(val, -1) == val >> 1);
+        assert(std::rotl(val, -127) == val << 1);
+        assert(std::rotl(T(3), -1) == ((T(1) << 127) | T(1)));
     }
 #endif
 
     return true;
 }
 
 int main(int, char**)
 {

libcxx/test/std/numerics/bit/bitops.rot/rotr.pass.cpp

constexpr bool test()
     assert(std::rotr(T(max - 1), 1) == T(max - highbit));
     assert(std::rotr(T(max - 1), 2) == T(max - (highbit >> 1)));
     assert(std::rotr(T(max - 1), 3) == T(max - (highbit >> 2)));
     assert(std::rotr(T(max - 1), 4) == T(max - (highbit >> 3)));
     assert(std::rotr(T(max - 1), 5) == T(max - (highbit >> 4)));
     assert(std::rotr(T(max - 1), 6) == T(max - (highbit >> 5)));
     assert(std::rotr(T(max - 1), 7) == T(max - (highbit >> 6)));
 
+    assert(std::rotr(T(max - 1), -1) == T(max - 2));
+    assert(std::rotr(T(max - 1), -2) == T(max - 4));
+    assert(std::rotr(T(max - 1), -3) == T(max - 8));
+    assert(std::rotr(T(max - 1), -4) == T(max - 16));
+    assert(std::rotr(T(max - 1), -5) == T(max - 32));
+    assert(std::rotr(T(max - 1), -6) == T(max - 64));
+    assert(std::rotr(T(max - 1), -7) == T(max - 128));
+
     assert(std::rotr(T(128), 0) == T(128));
     assert(std::rotr(T(128), 1) == T(64));
     assert(std::rotr(T(128), 2) == T(32));
     assert(std::rotr(T(128), 3) == T(16));
     assert(std::rotr(T(128), 4) == T(8));
     assert(std::rotr(T(128), 5) == T(4));
     assert(std::rotr(T(128), 6) == T(2));
     assert(std::rotr(T(128), 7) == T(1));
 
+    assert(std::rotr(T(1), -1) == T(2));
+    assert(std::rotr(T(1), -2) == T(4));
+    assert(std::rotr(T(1), -3) == T(8));
+    assert(std::rotr(T(1), -4) == T(16));
+    assert(std::rotr(T(1), -5) == T(32));
+    assert(std::rotr(T(1), -6) == T(64));
+    assert(std::rotr(T(1), -7) == T(128));
+
 #ifndef TEST_HAS_NO_INT128
     if constexpr (std::is_same_v<T, __uint128_t>) {
         T val = (T(1) << 63) | (T(1) << 64);
         assert(std::rotr(val, 0) == val);
         assert(std::rotr(val, 128) == val);
         assert(std::rotr(val, 256) == val);
         assert(std::rotr(val, 1) == val >> 1);
         assert(std::rotr(val, 127) == val << 1);
         assert(std::rotr(T(3), 1) == ((T(1) << 127) | T(1)));
+
+        assert(std::rotr(val, -128) == val);
+        assert(std::rotr(val, -256) == val);
+        assert(std::rotr(val, -1) == val << 1);
+        assert(std::rotr(val, -127) == val >> 1);
+        assert(std::rotr(T(3), -127) == ((T(1) << 127) | T(1)));
     }
 #endif
 
     return true;
 }
 
 int main(int, char**)
 {

libcxx/utils/data/ignore_format.txt

 libcxx/include/barrier
 libcxx/include/__bit/bit_cast.h
 libcxx/include/__bit/bit_ceil.h
 libcxx/include/__bit/byteswap.h
 libcxx/include/__bit/countl.h
 libcxx/include/__bit/countr.h
 libcxx/include/__bit/endian.h
 libcxx/include/__bit/popcount.h
-libcxx/include/__bit/rotate.h
 libcxx/include/bitset
 libcxx/include/cctype
 libcxx/include/chrono
 libcxx/include/__chrono/calendar.h
 libcxx/include/__chrono/convert_to_timespec.h
 libcxx/include/__chrono/day.h
 libcxx/include/__chrono/duration.h
 libcxx/include/__chrono/file_clock.h