bpo-29882: Add _Py_popcount32() function (GH-20518) · python/cpython@c6b292c · GitHub
Skip to content

Commit c6b292c

Browse files
vstinnervstinner
authored
bpo-29882: Add _Py_popcount32() function (GH-20518)
* Rename pycore_byteswap.h to pycore_bitutils.h. * Move popcount_digit() to pycore_bitutils.h as _Py_popcount32(). * _Py_popcount32() uses GCC and clang builtin function if available. * Add unit tests to _Py_popcount32().
1 parent 301f0d4 commit c6b292c

11 files changed

Lines changed: 108 additions & 39 deletions

File tree

Include/internal/pycore_byteswap.h renamed to Include/internal/pycore_bitutils.h

Lines changed: 50 additions & 1 deletion

‎Makefile.pre.in‎

Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -1121,7 +1121,7 @@ PYTHON_HEADERS= \
11211121
$(srcdir)/Include/internal/pycore_abstract.h \
11221122
$(srcdir)/Include/internal/pycore_accu.h \
11231123
$(srcdir)/Include/internal/pycore_atomic.h \
1124-
$(srcdir)/Include/internal/pycore_byteswap.h \
1124+
$(srcdir)/Include/internal/pycore_bitutils.h \
11251125
$(srcdir)/Include/internal/pycore_bytes_methods.h \
11261126
$(srcdir)/Include/internal/pycore_call.h \
11271127
$(srcdir)/Include/internal/pycore_ceval.h \

‎Modules/_ctypes/cfield.c‎

Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -1,5 +1,5 @@
11
#include "Python.h"
2-
#include "pycore_byteswap.h" // _Py_bswap32()
2+
#include "pycore_bitutils.h" // _Py_bswap32()
33

44
#include <ffi.h>
55
#ifdef MS_WIN32

‎Modules/_testinternalcapi.c‎

Lines changed: 41 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -12,7 +12,7 @@
1212
#define PY_SSIZE_T_CLEAN
1313

1414
#include "Python.h"
15-
#include "pycore_byteswap.h" // _Py_bswap32()
15+
#include "pycore_bitutils.h" // _Py_bswap32()
1616
#include "pycore_initconfig.h" // _Py_GetConfigsAsDict()
1717
#include "pycore_hashtable.h" // _Py_hashtable_new()
1818
#include "pycore_gc.h" // PyGC_Head
@@ -63,6 +63,45 @@ test_bswap(PyObject *self, PyObject *Py_UNUSED(args))
6363
}
6464

6565

66+
static int
67+
check_popcount(uint32_t x, int expected)
68+
{
69+
// Use volatile to prevent the compiler to optimize out the whole test
70+
volatile uint32_t u = x;
71+
int bits = _Py_popcount32(u);
72+
if (bits != expected) {
73+
PyErr_Format(PyExc_AssertionError,
74+
"_Py_popcount32(%lu) returns %i, expected %i",
75+
(unsigned long)x, bits, expected);
76+
return -1;
77+
}
78+
return 0;
79+
}
80+
81+
82+
static PyObject*
83+
test_popcount(PyObject *self, PyObject *Py_UNUSED(args))
84+
{
85+
#define CHECK(X, RESULT) \
86+
do { \
87+
if (check_popcount(X, RESULT) < 0) { \
88+
return NULL; \
89+
} \
90+
} while (0)
91+
92+
CHECK(0, 0);
93+
CHECK(1, 1);
94+
CHECK(0x08080808, 4);
95+
CHECK(0x10101010, 4);
96+
CHECK(0x10204080, 4);
97+
CHECK(0xDEADCAFE, 22);
98+
CHECK(0xFFFFFFFF, 32);
99+
Py_RETURN_NONE;
100+
101+
#undef CHECK
102+
}
103+
104+
66105
#define TO_PTR(ch) ((void*)(uintptr_t)ch)
67106
#define FROM_PTR(ptr) ((uintptr_t)ptr)
68107
#define VALUE(key) (1 + ((int)(key) - 'a'))
@@ -157,6 +196,7 @@ static PyMethodDef TestMethods[] = {
157196
{"get_configs", get_configs, METH_NOARGS},
158197
{"get_recursion_depth", get_recursion_depth, METH_NOARGS},
159198
{"test_bswap", test_bswap, METH_NOARGS},
199+
{"test_popcount", test_popcount, METH_NOARGS},
160200
{"test_hashtable", test_hashtable, METH_NOARGS},
161201
{NULL, NULL} /* sentinel */
162202
};

‎Modules/sha256module.c‎

Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -17,7 +17,7 @@
1717
/* SHA objects */
1818

1919
#include "Python.h"
20-
#include "pycore_byteswap.h" // _Py_bswap32()
20+
#include "pycore_bitutils.h" // _Py_bswap32()
2121
#include "structmember.h" // PyMemberDef
2222
#include "hashlib.h"
2323
#include "pystrhex.h"

‎Modules/sha512module.c‎

Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -17,7 +17,7 @@
1717
/* SHA objects */
1818

1919
#include "Python.h"
20-
#include "pycore_byteswap.h" // _Py_bswap32()
20+
#include "pycore_bitutils.h" // _Py_bswap32()
2121
#include "structmember.h" // PyMemberDef
2222
#include "hashlib.h"
2323
#include "pystrhex.h"

‎Objects/longobject.c‎

Lines changed: 7 additions & 8 deletions
Original file line numberDiff line numberDiff line change
@@ -3,8 +3,9 @@
33
/* XXX The functional organization of this file is terrible */
44

55
#include "Python.h"
6-
#include "pycore_interp.h" // _PY_NSMALLPOSINTS
7-
#include "pycore_pystate.h" // _Py_IsMainInterpreter()
6+
#include "pycore_bitutils.h" // _Py_popcount32()
7+
#include "pycore_interp.h" // _PY_NSMALLPOSINTS
8+
#include "pycore_pystate.h" // _Py_IsMainInterpreter()
89
#include "longintrepr.h"
910

1011
#include <float.h>
@@ -5307,12 +5308,10 @@ int_bit_length_impl(PyObject *self)
53075308
static int
53085309
popcount_digit(digit d)
53095310
{
5310-
/* 32bit SWAR popcount. */
5311-
uint32_t u = d;
5312-
u -= (u >> 1) & 0x55555555U;
5313-
u = (u & 0x33333333U) + ((u >> 2) & 0x33333333U);
5314-
u = (u + (u >> 4)) & 0x0f0f0f0fU;
5315-
return (uint32_t)(u * 0x01010101U) >> 24;
5311+
// digit can be larger than uint32_t, but only PyLong_SHIFT bits
5312+
// of it will be ever used.
5313+
Py_BUILD_ASSERT(PyLong_SHIFT <= 32);
5314+
return _Py_popcount32((uint32_t)d);
53165315
}
53175316

53185317
/*[clinic input]

‎Objects/stringlib/codecs.h‎

Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -4,7 +4,7 @@
44
# error "codecs.h is specific to Unicode"
55
#endif
66

7-
#include "pycore_byteswap.h" // _Py_bswap32()
7+
#include "pycore_bitutils.h" // _Py_bswap32()
88

99
/* Mask to quickly check whether a C 'long' contains a
1010
non-ASCII, UTF8-encoded char. */

‎PCbuild/pythoncore.vcxproj‎

Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -170,7 +170,7 @@
170170
<ClInclude Include="..\Include\internal\pycore_accu.h" />
171171
<ClInclude Include="..\Include\internal\pycore_atomic.h" />
172172
<ClInclude Include="..\Include\internal\pycore_bytes_methods.h" />
173-
<ClInclude Include="..\Include\internal\pycore_byteswap.h" />
173+
<ClInclude Include="..\Include\internal\pycore_bitutils.h" />
174174
<ClInclude Include="..\Include\internal\pycore_call.h" />
175175
<ClInclude Include="..\Include\internal\pycore_ceval.h" />
176176
<ClInclude Include="..\Include\internal\pycore_code.h" />

‎PCbuild/pythoncore.vcxproj.filters‎

Lines changed: 1 addition & 1 deletion

0 commit comments

Comments
 (0)