Summary: bug fix! Rotation direction on `__countl_zero()` probably unnoticed because only affects rare cases (does not affect 128 bit ints because rotation is effectively swap) (does not affect integers of sizes less or equal to 64bits)

[Delta-dev-99]

Summary

__countl_zero should count zeros (bits) starting from the left.
The bug fixed by this only affects big integers that cannot be handled in one go.
The idea is to successively take blocks from the left and apply the opperation recursively.
To do that we rotate to the left and the left-most block gets wrapped-around to the right-most position,
where we can apply the operation to it alone (by casting it to a smaller integer).

The current rotation used is to the right (64-bits), which works for 128-bits because it just swaps the halves.

[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