bpo-29782: Consolidate _Py_Bit_Length() (GH-20739)
In GH-2866, _Py_Bit_Length() was added to pymath.h for lack of a better
location. GH-20518 added a more appropriate header file for bit utilities. It
also shows how to properly use intrinsics. This allows reconsidering bpo-29782.
* Move the function to the new header.
* Changed return type to match __builtin_clzl() and reviewed usage.
* Use intrinsics where available.
* Pick a fallback implementation suitable for inlining.
diff --git a/Objects/longobject.c b/Objects/longobject.c
index dead3e3..d92a9c5 100644
--- a/Objects/longobject.c
+++ b/Objects/longobject.c
@@ -695,6 +695,13 @@
return Py_SIZE(v) == 0 ? 0 : (Py_SIZE(v) < 0 ? -1 : 1);
}
+static int
+bit_length_digit(digit x)
+{
+ Py_BUILD_ASSERT(PyLong_SHIFT <= sizeof(unsigned long) * 8);
+ return _Py_bit_length((unsigned long)x);
+}
+
size_t
_PyLong_NumBits(PyObject *vv)
{
@@ -712,7 +719,7 @@
if ((size_t)(ndigits - 1) > SIZE_MAX / (size_t)PyLong_SHIFT)
goto Overflow;
result = (size_t)(ndigits - 1) * (size_t)PyLong_SHIFT;
- msd_bits = _Py_bit_length(msd);
+ msd_bits = bit_length_digit(msd);
if (SIZE_MAX - msd_bits < result)
goto Overflow;
result += msd_bits;
@@ -1822,7 +1829,7 @@
return -1;
}
size_a_in_bits = (size_a - 1) * PyLong_SHIFT +
- _Py_bit_length(a->ob_digit[size_a - 1]);
+ bit_length_digit(a->ob_digit[size_a - 1]);
/* Allow 1 character for a '-' sign. */
sz = negative + (size_a_in_bits + (bits - 1)) / bits;
}
@@ -2642,7 +2649,7 @@
/* 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 - _Py_bit_length(w1->ob_digit[size_w-1]);
+ d = PyLong_SHIFT - bit_length_digit(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);
@@ -2764,7 +2771,7 @@
*e = 0;
return 0.0;
}
- a_bits = _Py_bit_length(a->ob_digit[a_size-1]);
+ a_bits = bit_length_digit(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 &&
@@ -3857,8 +3864,8 @@
/* Extreme underflow */
goto underflow_or_zero;
/* Next line is now safe from overflowing a Py_ssize_t */
- diff = diff * PyLong_SHIFT + _Py_bit_length(a->ob_digit[a_size - 1]) -
- _Py_bit_length(b->ob_digit[b_size - 1]);
+ diff = diff * PyLong_SHIFT + bit_length_digit(a->ob_digit[a_size - 1]) -
+ bit_length_digit(b->ob_digit[b_size - 1]);
/* Now diff = a_bits - b_bits. */
if (diff > DBL_MAX_EXP)
goto overflow;
@@ -3934,7 +3941,7 @@
}
x_size = Py_ABS(Py_SIZE(x));
assert(x_size > 0); /* result of division is never zero */
- x_bits = (x_size-1)*PyLong_SHIFT+_Py_bit_length(x->ob_digit[x_size-1]);
+ x_bits = (x_size-1)*PyLong_SHIFT+bit_length_digit(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;
@@ -4748,7 +4755,7 @@
alloc_b = Py_SIZE(b);
/* reduce until a fits into 2 digits */
while ((size_a = Py_SIZE(a)) > 2) {
- nbits = _Py_bit_length(a->ob_digit[size_a-1]);
+ nbits = bit_length_digit(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);
@@ -5269,7 +5276,7 @@
return PyLong_FromLong(0);
msd = ((PyLongObject *)self)->ob_digit[ndigits-1];
- msd_bits = _Py_bit_length(msd);
+ msd_bits = bit_length_digit(msd);
if (ndigits <= PY_SSIZE_T_MAX/PyLong_SHIFT)
return PyLong_FromSsize_t((ndigits-1)*PyLong_SHIFT + msd_bits);