[Python-checkins] bpo-31031: Unify duplicate bits_in_digit and bit_length (GH-2866)
Victor Stinner
webhook-mailer at python.org
Thu Jan 16 09:09:25 EST 2020
https://github.com/python/cpython/commit/c5b79003f5fe6aa28a2a028680367839ba8677db
commit: c5b79003f5fe6aa28a2a028680367839ba8677db
branch: master
author: Niklas Fiekas <niklas.fiekas at backscattering.de>
committer: Victor Stinner <vstinner at python.org>
date: 2020-01-16T15:09:19+01:00
summary:
bpo-31031: Unify duplicate bits_in_digit and bit_length (GH-2866)
Add _Py_bit_length() to unify duplicate bits_in_digit() and bit_length().
files:
M Include/pymath.h
M Modules/mathmodule.c
M Objects/longobject.c
M Python/pymath.c
diff --git a/Include/pymath.h b/Include/pymath.h
index f869724334a4c..63ca972784e31 100644
--- a/Include/pymath.h
+++ b/Include/pymath.h
@@ -227,4 +227,12 @@ PyAPI_FUNC(void) _Py_set_387controlword(unsigned short);
* behavior. */
#define _Py_InIntegralTypeRange(type, v) (_Py_IntegralTypeMin(type) <= v && v <= _Py_IntegralTypeMax(type))
+/* Return the smallest integer k such that n < 2**k, or 0 if n == 0.
+ * Equivalent to floor(log2(x))+1. Also equivalent to: bitwidth_of_type -
+ * count_leading_zero_bits(x)
+ */
+#ifndef Py_LIMITED_API
+PyAPI_FUNC(unsigned int) _Py_bit_length(unsigned long d);
+#endif
+
#endif /* Py_PYMATH_H */
diff --git a/Modules/mathmodule.c b/Modules/mathmodule.c
index 5e8e485afd41b..81d871786f139 100644
--- a/Modules/mathmodule.c
+++ b/Modules/mathmodule.c
@@ -1441,28 +1441,6 @@ math_fsum(PyObject *module, PyObject *seq)
#undef NUM_PARTIALS
-/* Return the smallest integer k such that n < 2**k, or 0 if n == 0.
- * Equivalent to floor(lg(x))+1. Also equivalent to: bitwidth_of_type -
- * count_leading_zero_bits(x)
- */
-
-/* XXX: This routine does more or less the same thing as
- * bits_in_digit() in Objects/longobject.c. Someday it would be nice to
- * consolidate them. On BSD, there's a library function called fls()
- * that we could use, and GCC provides __builtin_clz().
- */
-
-static unsigned long
-bit_length(unsigned long n)
-{
- unsigned long len = 0;
- while (n != 0) {
- ++len;
- n >>= 1;
- }
- return len;
-}
-
static unsigned long
count_set_bits(unsigned long n)
{
@@ -1877,7 +1855,7 @@ factorial_partial_product(unsigned long start, unsigned long stop,
/* find midpoint of range(start, stop), rounded up to next odd number. */
midpoint = (start + num_operands) | 1;
left = factorial_partial_product(start, midpoint,
- bit_length(midpoint - 2));
+ _Py_bit_length(midpoint - 2));
if (left == NULL)
goto error;
right = factorial_partial_product(midpoint, stop, max_bits);
@@ -1907,7 +1885,7 @@ factorial_odd_part(unsigned long n)
Py_INCREF(outer);
upper = 3;
- for (i = bit_length(n) - 2; i >= 0; i--) {
+ for (i = _Py_bit_length(n) - 2; i >= 0; i--) {
v = n >> i;
if (v <= 2)
continue;
@@ -1917,7 +1895,7 @@ factorial_odd_part(unsigned long n)
/* Here inner is the product of all odd integers j in the range (0,
n/2**(i+1)]. The factorial_partial_product call below gives the
product of all odd integers j in the range (n/2**(i+1), n/2**i]. */
- partial = factorial_partial_product(lower, upper, bit_length(upper-2));
+ partial = factorial_partial_product(lower, upper, _Py_bit_length(upper-2));
/* inner *= partial */
if (partial == NULL)
goto error;
diff --git a/Objects/longobject.c b/Objects/longobject.c
index be9301f85162c..b672ae4201891 100644
--- a/Objects/longobject.c
+++ b/Objects/longobject.c
@@ -803,26 +803,6 @@ _PyLong_Sign(PyObject *vv)
return Py_SIZE(v) == 0 ? 0 : (Py_SIZE(v) < 0 ? -1 : 1);
}
-/* bits_in_digit(d) returns the unique integer k such that 2**(k-1) <= d <
- 2**k if d is nonzero, else 0. */
-
-static const unsigned char BitLengthTable[32] = {
- 0, 1, 2, 2, 3, 3, 3, 3, 4, 4, 4, 4, 4, 4, 4, 4,
- 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5
-};
-
-static int
-bits_in_digit(digit d)
-{
- int d_bits = 0;
- while (d >= 32) {
- d_bits += 6;
- d >>= 6;
- }
- d_bits += (int)BitLengthTable[d];
- return d_bits;
-}
-
size_t
_PyLong_NumBits(PyObject *vv)
{
@@ -840,7 +820,7 @@ _PyLong_NumBits(PyObject *vv)
if ((size_t)(ndigits - 1) > SIZE_MAX / (size_t)PyLong_SHIFT)
goto Overflow;
result = (size_t)(ndigits - 1) * (size_t)PyLong_SHIFT;
- msd_bits = bits_in_digit(msd);
+ msd_bits = _Py_bit_length(msd);
if (SIZE_MAX - msd_bits < result)
goto Overflow;
result += msd_bits;
@@ -1950,7 +1930,7 @@ long_format_binary(PyObject *aa, int base, int alternate,
return -1;
}
size_a_in_bits = (size_a - 1) * PyLong_SHIFT +
- bits_in_digit(a->ob_digit[size_a - 1]);
+ _Py_bit_length(a->ob_digit[size_a - 1]);
/* Allow 1 character for a '-' sign. */
sz = negative + (size_a_in_bits + (bits - 1)) / bits;
}
@@ -2770,7 +2750,7 @@ x_divrem(PyLongObject *v1, PyLongObject *w1, PyLongObject **prem)
/* normalize: shift w1 left so that its top digit is >= PyLong_BASE/2.
shift v1 left by the same amount. Results go into w and v. */
- d = PyLong_SHIFT - bits_in_digit(w1->ob_digit[size_w-1]);
+ d = PyLong_SHIFT - _Py_bit_length(w1->ob_digit[size_w-1]);
carry = v_lshift(w->ob_digit, w1->ob_digit, size_w, d);
assert(carry == 0);
carry = v_lshift(v->ob_digit, v1->ob_digit, size_v, d);
@@ -2891,7 +2871,7 @@ _PyLong_Frexp(PyLongObject *a, Py_ssize_t *e)
*e = 0;
return 0.0;
}
- a_bits = bits_in_digit(a->ob_digit[a_size-1]);
+ a_bits = _Py_bit_length(a->ob_digit[a_size-1]);
/* The following is an overflow-free version of the check
"if ((a_size - 1) * PyLong_SHIFT + a_bits > PY_SSIZE_T_MAX) ..." */
if (a_size >= (PY_SSIZE_T_MAX - 1) / PyLong_SHIFT + 1 &&
@@ -3986,8 +3966,8 @@ long_true_divide(PyObject *v, PyObject *w)
/* Extreme underflow */
goto underflow_or_zero;
/* Next line is now safe from overflowing a Py_ssize_t */
- diff = diff * PyLong_SHIFT + bits_in_digit(a->ob_digit[a_size - 1]) -
- bits_in_digit(b->ob_digit[b_size - 1]);
+ diff = diff * PyLong_SHIFT + _Py_bit_length(a->ob_digit[a_size - 1]) -
+ _Py_bit_length(b->ob_digit[b_size - 1]);
/* Now diff = a_bits - b_bits. */
if (diff > DBL_MAX_EXP)
goto overflow;
@@ -4063,7 +4043,7 @@ long_true_divide(PyObject *v, PyObject *w)
}
x_size = Py_ABS(Py_SIZE(x));
assert(x_size > 0); /* result of division is never zero */
- x_bits = (x_size-1)*PyLong_SHIFT+bits_in_digit(x->ob_digit[x_size-1]);
+ x_bits = (x_size-1)*PyLong_SHIFT+_Py_bit_length(x->ob_digit[x_size-1]);
/* The number of extra bits that have to be rounded away. */
extra_bits = Py_MAX(x_bits, DBL_MIN_EXP - shift) - DBL_MANT_DIG;
@@ -4877,7 +4857,7 @@ _PyLong_GCD(PyObject *aarg, PyObject *barg)
alloc_b = Py_SIZE(b);
/* reduce until a fits into 2 digits */
while ((size_a = Py_SIZE(a)) > 2) {
- nbits = bits_in_digit(a->ob_digit[size_a-1]);
+ nbits = _Py_bit_length(a->ob_digit[size_a-1]);
/* extract top 2*PyLong_SHIFT bits of a into x, along with
corresponding bits of b into y */
size_b = Py_SIZE(b);
@@ -5395,7 +5375,7 @@ int_bit_length_impl(PyObject *self)
return PyLong_FromLong(0);
msd = ((PyLongObject *)self)->ob_digit[ndigits-1];
- msd_bits = bits_in_digit(msd);
+ msd_bits = _Py_bit_length(msd);
if (ndigits <= PY_SSIZE_T_MAX/PyLong_SHIFT)
return PyLong_FromSsize_t((ndigits-1)*PyLong_SHIFT + msd_bits);
diff --git a/Python/pymath.c b/Python/pymath.c
index 24b804223eef1..a08a0e796156f 100644
--- a/Python/pymath.c
+++ b/Python/pymath.c
@@ -79,3 +79,18 @@ round(double x)
return copysign(y, x);
}
#endif /* HAVE_ROUND */
+
+static const unsigned int BitLengthTable[32] = {
+ 0, 1, 2, 2, 3, 3, 3, 3, 4, 4, 4, 4, 4, 4, 4, 4,
+ 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5
+};
+
+unsigned int _Py_bit_length(unsigned long d) {
+ unsigned int d_bits = 0;
+ while (d >= 32) {
+ d_bits += 6;
+ d >>= 6;
+ }
+ d_bits += BitLengthTable[d];
+ return d_bits;
+}
More information about the Python-checkins
mailing list