diff options
| -rw-r--r-- | Include/pymath.h | 8 | ||||
| -rw-r--r-- | Modules/mathmodule.c | 28 | ||||
| -rw-r--r-- | Objects/longobject.c | 38 | ||||
| -rw-r--r-- | Python/pymath.c | 15 |
4 files changed, 35 insertions, 54 deletions
diff --git a/Include/pymath.h b/Include/pymath.h index f869724..63ca972 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 5e8e485..81d8717 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 be9301f..b672ae4 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 24b8042..a08a0e7 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; +} |