bpo-29782: Consolidate _Py_Bit_Length() (GH-20739)

bpo-29782: Consolidate _Py_Bit_Length() (GH-20739) · python/cpython@794e7d1

@@ -695,6 +695,13 @@ _PyLong_Sign(PyObject *vv)

695695return Py_SIZE(v) == 0 ? 0 : (Py_SIZE(v) < 0 ? -1 : 1);696696}697697698+static int699+bit_length_digit(digit x)700+{701+Py_BUILD_ASSERT(PyLong_SHIFT <= sizeof(unsigned long) * 8);702+return _Py_bit_length((unsigned long)x);703+}704+698705size_t699706_PyLong_NumBits(PyObject *vv)700707{

@@ -712,7 +719,7 @@ _PyLong_NumBits(PyObject *vv)

712719if ((size_t)(ndigits - 1) > SIZE_MAX / (size_t)PyLong_SHIFT)713720 goto Overflow;714721result = (size_t)(ndigits - 1) * (size_t)PyLong_SHIFT;715-msd_bits = _Py_bit_length(msd);722+msd_bits = bit_length_digit(msd);716723if (SIZE_MAX - msd_bits < result)717724 goto Overflow;718725result += msd_bits;

@@ -1822,7 +1829,7 @@ long_format_binary(PyObject *aa, int base, int alternate,

18221829return -1;18231830 }18241831size_a_in_bits = (size_a - 1) * PyLong_SHIFT +1825-_Py_bit_length(a->ob_digit[size_a - 1]);1832+bit_length_digit(a->ob_digit[size_a - 1]);18261833/* Allow 1 character for a '-' sign. */18271834sz = negative + (size_a_in_bits + (bits - 1)) / bits;18281835 }

@@ -2642,7 +2649,7 @@ x_divrem(PyLongObject *v1, PyLongObject *w1, PyLongObject **prem)

2642264926432650/* normalize: shift w1 left so that its top digit is >= PyLong_BASE/2.26442651 shift v1 left by the same amount. Results go into w and v. */2645-d = PyLong_SHIFT - _Py_bit_length(w1->ob_digit[size_w-1]);2652+d = PyLong_SHIFT - bit_length_digit(w1->ob_digit[size_w-1]);26462653carry = v_lshift(w->ob_digit, w1->ob_digit, size_w, d);26472654assert(carry == 0);26482655carry = v_lshift(v->ob_digit, v1->ob_digit, size_v, d);

@@ -2764,7 +2771,7 @@ _PyLong_Frexp(PyLongObject *a, Py_ssize_t *e)

27642771*e = 0;27652772return 0.0;27662773 }2767-a_bits = _Py_bit_length(a->ob_digit[a_size-1]);2774+a_bits = bit_length_digit(a->ob_digit[a_size-1]);27682775/* The following is an overflow-free version of the check27692776 "if ((a_size - 1) * PyLong_SHIFT + a_bits > PY_SSIZE_T_MAX) ..." */27702777if (a_size >= (PY_SSIZE_T_MAX - 1) / PyLong_SHIFT + 1 &&

@@ -3857,8 +3864,8 @@ long_true_divide(PyObject *v, PyObject *w)

38573864/* Extreme underflow */38583865 goto underflow_or_zero;38593866/* Next line is now safe from overflowing a Py_ssize_t */3860-diff = diff * PyLong_SHIFT + _Py_bit_length(a->ob_digit[a_size - 1]) -3861-_Py_bit_length(b->ob_digit[b_size - 1]);3867+diff = diff * PyLong_SHIFT + bit_length_digit(a->ob_digit[a_size - 1]) -3868+bit_length_digit(b->ob_digit[b_size - 1]);38623869/* Now diff = a_bits - b_bits. */38633870if (diff > DBL_MAX_EXP)38643871 goto overflow;

@@ -3934,7 +3941,7 @@ long_true_divide(PyObject *v, PyObject *w)

39343941 }39353942x_size = Py_ABS(Py_SIZE(x));39363943assert(x_size > 0); /* result of division is never zero */3937-x_bits = (x_size-1)*PyLong_SHIFT+_Py_bit_length(x->ob_digit[x_size-1]);3944+x_bits = (x_size-1)*PyLong_SHIFT+bit_length_digit(x->ob_digit[x_size-1]);3938394539393946/* The number of extra bits that have to be rounded away. */39403947extra_bits = Py_MAX(x_bits, DBL_MIN_EXP - shift) - DBL_MANT_DIG;

@@ -4748,7 +4755,7 @@ _PyLong_GCD(PyObject *aarg, PyObject *barg)

47484755alloc_b = Py_SIZE(b);47494756/* reduce until a fits into 2 digits */47504757while ((size_a = Py_SIZE(a)) > 2) {4751-nbits = _Py_bit_length(a->ob_digit[size_a-1]);4758+nbits = bit_length_digit(a->ob_digit[size_a-1]);47524759/* extract top 2*PyLong_SHIFT bits of a into x, along with47534760 corresponding bits of b into y */47544761size_b = Py_SIZE(b);

@@ -5269,7 +5276,7 @@ int_bit_length_impl(PyObject *self)

52695276return PyLong_FromLong(0);5270527752715278msd = ((PyLongObject *)self)->ob_digit[ndigits-1];5272-msd_bits = _Py_bit_length(msd);5279+msd_bits = bit_length_digit(msd);5273528052745281if (ndigits <= PY_SSIZE_T_MAX/PyLong_SHIFT)52755282return PyLong_FromSsize_t((ndigits-1)*PyLong_SHIFT + msd_bits);