[libc++] Fix the rotate direction used in countl_zero()

[ldionne]

Summary

This "bug" was probably not noticed because it doesn't affect any integer
type we currently support. It requires integers with more than 2x the
size of unsigned long long. However, with such types, the algorithm
used to break down the large integer into groups of size unsigned long long
didn't work because we rotated in the wrong direction.

For example, the 256 bit number (1 << 255) would yield the wrong answer
when used with the algorithm before this patch.

In particular, note that the current rotation happens to work for 128 bit
integers because it just swaps the halves in this case.

[jloser]

Is there a test we can add to exhibit this bug and verify this fixes the problem?

[ldionne]

In D134625#3814774, @jloser wrote:

Is there a test we can add to exhibit this bug and verify this fixes the problem?

Indeed, let's add a test. Also, how did you encounter this bug?

[Delta-dev-99]

I was playing with the core libraries and details of C++ and tried compiling and running programs without standard libraries and with custom versions of standard library.
I was implementing bit operations and decided to take a look at llvm's implementation to compare with my own. I had a very similar idea, but the rotation direction was different on libcxx.
That's how I found it. I didn't had a test case.

[Delta-dev-99]

Possible test case: apply the operation to 256-bit integer 0x8000000000000000000000000000000000000000000000000000000000000000 (first bit from the left is set, all other bits cleared)
Correct answer: 0. The first bit from the left is set.
Current implementation's answer (probably, not tested yet): 128. It counts the bits cleared in the 2 blocks (64 bits each) in the middle of the number (bits 64 to 191) before finding the bit set in the left-most block (block 3).

Another possible test case: 256-bit integer 0x0000000000000000000000000000000080000000000000000000000000000000 (bit 127 is set, which is the left-most bit of block 1, all other bits cleared)
Correct answer: 128
Current implementation's answer (probably, not tested yet): 0

To clarify, all indexes are taken from the right, starting from 0.
Less significant bits/blocks get lower indexes

[Mordante]

We're moving to GitHub PRs it would be great when this patch can be finished before moving. Are you interested in finishing it? If not I'll take over. Please start by rebasing the patch to see whether it passes the CI.

[ldionne]

[Github PR transition cleanup]

I revisited this in the context of cleaning up our review queue. I think the author of the patch is right in theory, however this can't be tested because we don't support types larger than 128 bits (and for these types both before and after the patch are equivalent). But if we did support e.g. 256 bit integers, our current algorithm would give the wrong answer. Here's a walkthrough with a 256 bit integer.

Current algorithm:

// We have the following 256 bit number. The answer to countl_zero should be 0 because the leftmost bit is set:
// 10000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000   00000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000   00000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000   00000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000

// We start by doing __rotr(__t, unsigned long long digits == 64), which gives us the following number:
// 00000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000   10000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000   00000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000   00000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000

// Now countl_zero of that number (casted to unsigned long long) is:
// countl_zero(00000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000) == 64

// Since that is equal to numeric_limits<unsigned long long>::digits, don't get into the if-then-break, we set __ret = 64 and we keep going.

// Now we do __rotr(__t, unsigned long long digits) again, which gives us the following number:
// 00000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000   00000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000   10000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000   00000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000

// We countl_zero again, which gives us 64 and we set __ret = 128. We keep going again.

// We do __rotr(__t, unsigned long long digits) again, which gives us the following number:
// 00000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000   00000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000   00000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000   10000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000

// This time countl_zero(10000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000) is 0, which is not equal to numeric_limits<unsigned long long>::digits. So we enter the if-then-break and we return 128.

If instead we used __rotl(__t, unsigned long long digits) as proposed by this patch, we'd get this:

// This is the number we start with, same as above:
// 10000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000   00000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000   00000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000   00000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000

// We now do __rotl(__t, unsigned long long digits == 64), which gives us the following number:
// 00000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000   00000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000   00000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000   10000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000

// Now countl_zero of that number (casted to unsigned long long) is:
// countl_zero(10000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000) == 0

// That is equal to 0, which is not the same as __ulldigits, so we enter the if-then-break and we return __ret which is 0.

I also tried with the number 0x0000000000000000000000000000000080000000000000000000000000000000 as suggested and the same thing happens, we give the wrong answer. When you think about it it really makes sense, we need to "eat" the 0 digits to the left of the first digit that's 1 first, that's the only correct way to break down a large width integer into unsigned long long chunks. So I'll commandeer this patch and rebase it to finish it up.

[ldionne]

Rebase and fix CI. I can't add tests because this isn't technically a "live bug" -- but the bug would trigger if we started supporting 256 bit integers.

[ldionne]

Simd failures are unrelated, shipping.

libcxx/include/__bit/countl.h

else if (sizeof(_Tp) <= sizeof(unsigned long long))
         return std::__libcpp_clz(static_cast<unsigned long long>(__t))
               - (numeric_limits<unsigned long long>::digits - numeric_limits<_Tp>::digits);
     else
     {
         int __ret = 0;
         int __iter = 0;
         const unsigned int __ulldigits = numeric_limits<unsigned long long>::digits;
         while (true) {
-            __t = std::__rotr(__t, __ulldigits);
+            __t = std::__rotl(__t, __ulldigits);
             if ((__iter = std::__countl_zero(static_cast<unsigned long long>(__t))) != __ulldigits)
                 break;
             __ret += __iter;
             }
         return __ret + __iter;
     }
 }
 

libcxx/include/__bit/rotate.h

_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
   }
 
   return (__t >> (__cnt % __dig)) | (__t << (__dig - (__cnt % __dig)));
 }
 
+template <class _Tp>
+_LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX14 _Tp __rotl(_Tp __t, int __cnt) _NOEXCEPT {
+  return std::__rotr(__t, -__cnt);
+}
+
 #if _LIBCPP_STD_VER >= 20
 
 template <__libcpp_unsigned_integer _Tp>
 [[nodiscard]] _LIBCPP_HIDE_FROM_ABI constexpr _Tp rotl(_Tp __t, int __cnt) noexcept {
-  return std::__rotr(__t, -__cnt);
+  return std::__rotl(__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);
 }
 
 #endif // _LIBCPP_STD_VER >= 20
 
 _LIBCPP_END_NAMESPACE_STD
 
 #endif // _LIBCPP___BIT_ROTATE_H