Page MenuHomePhabricator

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)
Needs ReviewPublic

Authored by Delta-dev-99 on Sep 25 2022, 11:15 PM.

Details

Reviewers
None
Group Reviewers
Restricted Project
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.

Diff Detail

Event Timeline

Delta-dev-99 created this revision.Sep 25 2022, 11:15 PM
Herald added a project: Restricted Project. · View Herald TranscriptSep 25 2022, 11:15 PM
Delta-dev-99 requested review of this revision.Sep 25 2022, 11:15 PM
Herald added a project: Restricted Project. · View Herald TranscriptSep 25 2022, 11:15 PM
Herald added a reviewer: Restricted Project. · View Herald Transcript
jloser added a subscriber: jloser.Sep 26 2022, 5:19 AM

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

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?

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 added a comment.EditedSep 26 2022, 2:48 PM

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