Skip to content

bpo-29882: Add _Py_popcount32() function #20518

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.

Sign up for GitHub

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

Merged
vstinner merged 6 commits into from
Jun 8, 2020
Merged

bpo-29882: Add _Py_popcount32() function #20518

Show file tree
Hide file tree
Changes from 1 commit
Commits
Show all changes
6 commits
Select commit Hold shift + click to select a range
8daa537
bpo-29882: Add _Py_popcount32() function
vstinner May 29, 2020
9e813d1
Enhance unit test
vstinner May 29, 2020
b793ff8
Use constants
vstinner Jun 2, 2020
585f906
Add implementation note on SSE4a
vstinner Jun 2, 2020
48df7e3
hamt.c: cast result explicitly
vstinner Jun 2, 2020
5838d27
Address Mark's review
vstinner Jun 7, 2020
File filter

Filter by extension

Filter by extension
Conversations
Failed to load comments.
Loading
Jump to
Jump to file
Failed to load files.
Loading
Diff view
Diff view
Prev Previous commit
Address Mark's review 
* Remove UINT32_C()
* Fix #ifdef to decide if builtin functions are used of not:
  use SIZEOF_INT >= 4. Always use __builtin_popcountl() otherwise.
* popcount_digit(): check PyLong_SHIFT rather than sizeof(digit).
* Fix also two comments
  • Loading branch information
@vstinner
vstinner committed Jun 7, 2020
commit 5838d2751e34c106df9299d18f1125a8844c738e
24 changes: 16 additions & 8 deletions Include/internal/pycore_bitutils.h
View file
Open in desktop
Original file line number Diff line number Diff line change
Expand Up @@ -84,7 +84,7 @@ _Py_bswap64(uint64_t word)
}


// Population count: count the number of 1's in 'u'
// Population count: count the number of 1's in 'x'
// (number of bits set to 1), also known as the hamming weight.
//
// Implementation note. CPUID is not used, to test if x86 POPCNT instruction
Expand All @@ -95,21 +95,29 @@ _Py_bswap64(uint64_t word)
static inline int
_Py_popcount32(uint32_t x)
{
#if (defined(__clang__) || defined(__GNUC__)) && SIZEOF_INT == 4
#if (defined(__clang__) || defined(__GNUC__))

#if SIZEOF_INT >= 4
Py_BUILD_ASSERT(sizeof(x) <= sizeof(unsigned int));
return __builtin_popcount(x);
#elif (defined(__clang__) || defined(__GNUC__)) && SIZEOF_INT == 8
#else
// The C standard guarantees that unsigned long will always be big enough
// to hold a uint32_t value without losing information.
Py_BUILD_ASSERT(sizeof(x) <= sizeof(unsigned long));
return __builtin_popcountl(x);
#endif

#else
// 32-bit SWAR (SIMD Within A Register) popcount

// Binary: 0 1 0 1 ...
const uint32_t M1 = UINT32_C(0x55555555);
const uint32_t M1 = 0x55555555;
// Binary: 00 11 00 11. ..
const uint32_t M2 = UINT32_C(0x33333333);
const uint32_t M2 = 0x33333333;
// Binary: 0000 1111 0000 1111 ...
const uint32_t M4 = UINT32_C(0x0F0F0F0F);
// 256^4 + 256^3 + 256^2 + 256^1
const uint32_t SUM = UINT32_C(0x01010101);
const uint32_t M4 = 0x0F0F0F0F;
// 256**4 + 256**3 + 256**2 + 256**1
const uint32_t SUM = 0x01010101;

// Put count of each 2 bits into those 2 bits
x = x - ((x >> 1) & M1);
Expand Down
2 changes: 1 addition & 1 deletion Modules/_testinternalcapi.c
View file
Open in desktop
Original file line number Diff line number Diff line change
Expand Up @@ -84,7 +84,7 @@ test_popcount(PyObject *self, PyObject *Py_UNUSED(args))
{
#define CHECK(X, RESULT) \
do { \
if (check_popcount(UINT32_C(X), RESULT) < 0) { \
if (check_popcount(X, RESULT) < 0) { \
return NULL; \
} \
} while (0)
Expand Down
4 changes: 3 additions & 1 deletion Objects/longobject.c
View file
Open in desktop
Original file line number Diff line number Diff line change
Expand Up @@ -5308,7 +5308,9 @@ int_bit_length_impl(PyObject *self)
static int
popcount_digit(digit d)
{
Py_BUILD_ASSERT(sizeof(digit) <= sizeof(uint32_t));
// digit can be larger than uint32_t, but only PyLong_SHIFT bits
// of it will be ever used.
Py_BUILD_ASSERT(PyLong_SHIFT <= 32);
return _Py_popcount32((uint32_t)d);
}

Expand Down