GeezerVison

Nice comment, thanks! Before the comment, I was surprised by the two loops.

I proposed to work use size_t for bit_count, but then I realzied that i is a Py_ssize_t, so it's better to leave the code as it is: work on Py_ssize_t for i and bit_count.

I just realised that this line isn't quite portable. The code is relying on the multiplication being a multiplication of 32-bit integers, so that the result is implicitly reduced modulo 2^32.

However, if we're on a platform with a 64-bit int then 0x01010101 will have type int (C99 6.4.4.1p5), u will be promoted to int (following the "usual arithmetic conversions" in C99 6.3.1.8p1), the multiplication will be a multiplication of 64-bit integers and we'll end up with the wrong result.

Fix implemented, in the shape of an extra (uint32_t) cast on the multiplication result along with some U suffixes on the integer constants.

Note that the U suffix on 0x01010101U is actually necessary to avoid undefined behaviour: consider a (hypothetical, but permissible under the C standard) machine with a 48-bit int. If we do u * 0x01010101 on that machine, then first the integer promotions are applied to both arguments, and they both end up being of type int. Then we do an int-by-int multiplication. With the right (wrong?) value of d, this could overflow, giving undefined behaviour.

But with the U suffix, we end up after the integer promotions multiplying an int by an unsigned int, and then the usual arithmetic conversions kick in and the multiplication is performed as type unsigned int, which has well-defined wraparound behaviour for the result.

The other U suffixes aren't strictly necessary; they're just there to satisfy my OCD and make the code easier to think about.

Python/hamt.c has basically a copy of this function, it's just written a little bit differently, but its return type is uint32_t. It exists since Python 3.8 and we didn't get any bug report :-)

I added pycore_byteswap.h. Maybe we could have a pycore_bitutils.h for such function and declare it as static inline, to reuse it here and in hamt.c. Or it can be done later ;-)

@pitrou also asked if "pycore_byteswap.h" filename was not too specific, maybe we could pick a more generic name to put more functions there. Like "bits and bytes utilities" :-)

Note: _testinternalcapi has tests for the byte swap functions ;-) We could have tests on this popcount function as well to detect if a compiler "miscompiles" this function.

Oh, I'm volunteer to move this function as static inline function and add the new test ;-) As I wrote, it can be done later.

It exists since Python 3.8 and we didn't get any bug report :-)

That's probably because it was never run on a machine with a 64-bit C int. Which is not surprising, because it's very hard to find such a machine these days. But who knows what could happen in the future. :-)

The version of the code in hamt.c has the same issues: it'll return the wrong result with a 64-bit C int, and it can technically invoke undefined behaviour. The return type of uint32_t on that function doesn't help, because you already have the wrong number / undefined behaviour before you hit the return.

Realistically, the undefined behaviour is unlikely to ever be an issue in practice. But the wrong result with a 64-bit int isn't entirely implausible.

I'll merge this, then we can look at combining the implementations or fixing the hamt.c code as necessary.