Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

findFirstSetBitZeroIdx() does not work correctly for small morton code #78

Closed
frank-aurich opened this issue May 20, 2022 · 2 comments
Closed
Assignees

Comments

@frank-aurich
Copy link

The function findFirstSetBitZeroIdx() does not work correctly for small (<= 4byte) morton values when compiling on 64-bit Linux using gcc or clang.

const uint32_t x = 545658634;
unsigned long c;
findFirstSetBitZeroIdx(x, c); // Expected: c == 29

The issue is that internally, the builtin function __builtin_clzll is used for all inputs, i.e. the input variable x is cast to unsigned long long. For the ID above, __builtin_clzll returns 34, which is correct if x were a 64-bit integer.
But that result is substracted from sizeof(morton) * 8, which in this case is 32.
In the end we have 32 - 34 -1, cast to unsigned long, which is an integer overflow.

Possible fix:

*firstbit_location = static_cast<unsigned long>((sizeof(unsigned long long) * 8) - __builtin_clzll(x) - 1);
@Forceflow Forceflow added the bug label Jul 20, 2022
@Forceflow Forceflow self-assigned this Jul 20, 2022
@Forceflow
Copy link
Owner

Thanks, will look into this.

@Forceflow
Copy link
Owner

Fixed in latest release

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Projects
None yet
Development

No branches or pull requests

2 participants