findFirstSetBitZeroIdx() does not work correctly for small morton code

[frank-aurich]

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]

Thanks, will look into this.

[Forceflow]

Fixed in latest release