Google Git
Sign in
chromium / external / github.com / python / cpython / ca878b6e45f9c7934842f7bb94274e671b155e09 / . / Objects / longobject.c
blob: b4c0f63a9843ce587931b417a7aed3d37cc5bb51 [file] [log] [blame]
/* Long (arbitrary precision) integer object implementation */
/* XXX The functional organization of this file is terrible */
#include "Python.h"
#include "pycore_bitutils.h" // _Py_popcount32()
#include "pycore_initconfig.h" // _PyStatus_OK()
#include "pycore_call.h" // _PyObject_MakeTpCall
#include "pycore_long.h" // _Py_SmallInts
#include "pycore_object.h" // _PyObject_Init()
#include "pycore_runtime.h" // _PY_NSMALLPOSINTS
#include "pycore_structseq.h" // _PyStructSequence_FiniBuiltin()
#include <float.h> // DBL_MANT_DIG
#include <stddef.h> // offsetof
#include "clinic/longobject.c.h"
/*[clinic input]
class int "PyObject *" "&PyLong_Type"
[clinic start generated code]*/
/*[clinic end generated code: output=da39a3ee5e6b4b0d input=ec0275e3422a36e3]*/
#define medium_value(x) ((stwodigits)_PyLong_CompactValue(x))
#define IS_SMALL_INT(ival) (-_PY_NSMALLNEGINTS <= (ival) && (ival) < _PY_NSMALLPOSINTS)
#define IS_SMALL_UINT(ival) ((ival) < _PY_NSMALLPOSINTS)
#define _MAX_STR_DIGITS_ERROR_FMT_TO_INT "Exceeds the limit (%d digits) for integer string conversion: value has %zd digits; use sys.set_int_max_str_digits() to increase the limit"
#define _MAX_STR_DIGITS_ERROR_FMT_TO_STR "Exceeds the limit (%d digits) for integer string conversion; use sys.set_int_max_str_digits() to increase the limit"
/* If defined, use algorithms from the _pylong.py module */
#define WITH_PYLONG_MODULE 1
// Forward declarations
static PyLongObject* long_neg(PyLongObject *v);
static PyLongObject *x_divrem(PyLongObject *, PyLongObject *, PyLongObject **);
static PyObject* long_long(PyObject *v);
static PyObject* long_lshift_int64(PyLongObject *a, int64_t shiftby);
static inline void
_Py_DECREF_INT(PyLongObject *op)
{
assert(PyLong_CheckExact(op));
_Py_DECREF_SPECIALIZED((PyObject *)op, (destructor)PyObject_Free);
}
static inline int
is_medium_int(stwodigits x)
{
/* Take care that we are comparing unsigned values. */
twodigits x_plus_mask = ((twodigits)x) + PyLong_MASK;
return x_plus_mask < ((twodigits)PyLong_MASK) + PyLong_BASE;
}
static PyObject *
get_small_int(sdigit ival)
{
assert(IS_SMALL_INT(ival));
return (PyObject *)&_PyLong_SMALL_INTS[_PY_NSMALLNEGINTS + ival];
}
static PyLongObject *
maybe_small_long(PyLongObject *v)
{
if (v && _PyLong_IsCompact(v)) {
stwodigits ival = medium_value(v);
if (IS_SMALL_INT(ival)) {
_Py_DECREF_INT(v);
return (PyLongObject *)get_small_int((sdigit)ival);
}
}
return v;
}
/* For int multiplication, use the O(N**2) school algorithm unless
* both operands contain more than KARATSUBA_CUTOFF digits (this
* being an internal Python int digit, in base BASE).
*/
#define KARATSUBA_CUTOFF 70
#define KARATSUBA_SQUARE_CUTOFF (2 * KARATSUBA_CUTOFF)
/* For exponentiation, use the binary left-to-right algorithm unless the
^ exponent contains more than HUGE_EXP_CUTOFF bits. In that case, do
* (no more than) EXP_WINDOW_SIZE bits at a time. The potential drawback is
* that a table of 2**(EXP_WINDOW_SIZE - 1) intermediate results is
* precomputed.
*/
#define EXP_WINDOW_SIZE 5
#define EXP_TABLE_LEN (1 << (EXP_WINDOW_SIZE - 1))
/* Suppose the exponent has bit length e. All ways of doing this
* need e squarings. The binary method also needs a multiply for
* each bit set. In a k-ary method with window width w, a multiply
* for each non-zero window, so at worst (and likely!)
* ceiling(e/w). The k-ary sliding window method has the same
* worst case, but the window slides so it can sometimes skip
* over an all-zero window that the fixed-window method can't
* exploit. In addition, the windowing methods need multiplies
* to precompute a table of small powers.
*
* For the sliding window method with width 5, 16 precomputation
* multiplies are needed. Assuming about half the exponent bits
* are set, then, the binary method needs about e/2 extra mults
* and the window method about 16 + e/5.
*
* The latter is smaller for e > 53 1/3. We don't have direct
* access to the bit length, though, so call it 60, which is a
* multiple of a long digit's max bit length (15 or 30 so far).
*/
#define HUGE_EXP_CUTOFF 60
#define SIGCHECK(PyTryBlock) \
do { \
if (PyErr_CheckSignals()) PyTryBlock \
} while(0)
/* Normalize (remove leading zeros from) an int object.
Doesn't attempt to free the storage--in most cases, due to the nature
of the algorithms used, this could save at most be one word anyway. */
static PyLongObject *
long_normalize(PyLongObject *v)
{
Py_ssize_t j = _PyLong_DigitCount(v);
Py_ssize_t i = j;
while (i > 0 && v->long_value.ob_digit[i-1] == 0)
--i;
if (i != j) {
if (i == 0) {
_PyLong_SetSignAndDigitCount(v, 0, 0);
}
else {
_PyLong_SetDigitCount(v, i);
}
}
return v;
}
/* Allocate a new int object with size digits.
Return NULL and set exception if we run out of memory. */
#if SIZEOF_SIZE_T < 8
# define MAX_LONG_DIGITS \
((PY_SSIZE_T_MAX - offsetof(PyLongObject, long_value.ob_digit))/sizeof(digit))
#else
/* Guarantee that the number of bits fits in int64_t.
This is more than an exbibyte, that is more than many of modern
architectures support in principle.
-1 is added to avoid overflow in _PyLong_Frexp(). */
# define MAX_LONG_DIGITS ((INT64_MAX-1) / PyLong_SHIFT)
#endif
PyLongObject *
_PyLong_New(Py_ssize_t size)
{
assert(size >= 0);
PyLongObject *result;
if (size > (Py_ssize_t)MAX_LONG_DIGITS) {
PyErr_SetString(PyExc_OverflowError,
"too many digits in integer");
return NULL;
}
/* Fast operations for single digit integers (including zero)
* assume that there is always at least one digit present. */
Py_ssize_t ndigits = size ? size : 1;
/* Number of bytes needed is: offsetof(PyLongObject, ob_digit) +
sizeof(digit)*size. Previous incarnations of this code used
sizeof() instead of the offsetof, but this risks being
incorrect in the presence of padding between the header
and the digits. */
result = PyObject_Malloc(offsetof(PyLongObject, long_value.ob_digit) +
ndigits*sizeof(digit));
if (!result) {
PyErr_NoMemory();
return NULL;
}
_PyLong_SetSignAndDigitCount(result, size != 0, size);
_PyObject_Init((PyObject*)result, &PyLong_Type);
/* The digit has to be initialized explicitly to avoid
* use-of-uninitialized-value. */
result->long_value.ob_digit[0] = 0;
return result;
}
PyLongObject *
_PyLong_FromDigits(int negative, Py_ssize_t digit_count, digit *digits)
{
assert(digit_count >= 0);
if (digit_count == 0) {
return (PyLongObject *)_PyLong_GetZero();
}
PyLongObject *result = _PyLong_New(digit_count);
if (result == NULL) {
PyErr_NoMemory();
return NULL;
}
_PyLong_SetSignAndDigitCount(result, negative?-1:1, digit_count);
memcpy(result->long_value.ob_digit, digits, digit_count * sizeof(digit));
return result;
}
PyObject *
_PyLong_Copy(PyLongObject *src)
{
assert(src != NULL);
if (_PyLong_IsCompact(src)) {
stwodigits ival = medium_value(src);
if (IS_SMALL_INT(ival)) {
return get_small_int((sdigit)ival);
}
}
Py_ssize_t size = _PyLong_DigitCount(src);
return (PyObject *)_PyLong_FromDigits(_PyLong_IsNegative(src), size, src->long_value.ob_digit);
}
static PyObject *
_PyLong_FromMedium(sdigit x)
{
assert(!IS_SMALL_INT(x));
assert(is_medium_int(x));
/* We could use a freelist here */
PyLongObject *v = PyObject_Malloc(sizeof(PyLongObject));
if (v == NULL) {
PyErr_NoMemory();
return NULL;
}
digit abs_x = x < 0 ? -x : x;
_PyLong_SetSignAndDigitCount(v, x<0?-1:1, 1);
_PyObject_Init((PyObject*)v, &PyLong_Type);
v->long_value.ob_digit[0] = abs_x;
return (PyObject*)v;
}
static PyObject *
_PyLong_FromLarge(stwodigits ival)
{
twodigits abs_ival;
int sign;
assert(!is_medium_int(ival));
if (ival < 0) {
/* negate: can't write this as abs_ival = -ival since that
invokes undefined behaviour when ival is LONG_MIN */
abs_ival = 0U-(twodigits)ival;
sign = -1;
}
else {
abs_ival = (twodigits)ival;
sign = 1;
}
/* Must be at least two digits */
assert(abs_ival >> PyLong_SHIFT != 0);
twodigits t = abs_ival >> (PyLong_SHIFT * 2);
Py_ssize_t ndigits = 2;
while (t) {
++ndigits;
t >>= PyLong_SHIFT;
}
PyLongObject *v = _PyLong_New(ndigits);
if (v != NULL) {
digit *p = v->long_value.ob_digit;
_PyLong_SetSignAndDigitCount(v, sign, ndigits);
t = abs_ival;
while (t) {
*p++ = Py_SAFE_DOWNCAST(
t & PyLong_MASK, twodigits, digit);
t >>= PyLong_SHIFT;
}
}
return (PyObject *)v;
}
/* Create a new int object from a C word-sized int */
static inline PyLongObject *
_PyLong_FromSTwoDigits(stwodigits x)
{
if (IS_SMALL_INT(x)) {
return (PyLongObject*)get_small_int((sdigit)x);
}
assert(x != 0);
if (is_medium_int(x)) {
return (PyLongObject*)_PyLong_FromMedium((sdigit)x);
}
return (PyLongObject*)_PyLong_FromLarge(x);
}
/* If a freshly-allocated int is already shared, it must
be a small integer, so negating it must go to PyLong_FromLong */
Py_LOCAL_INLINE(void)
_PyLong_Negate(PyLongObject **x_p)
{
PyLongObject *x;
x = (PyLongObject *)*x_p;
if (Py_REFCNT(x) == 1) {
_PyLong_FlipSign(x);
return;
}
*x_p = _PyLong_FromSTwoDigits(-medium_value(x));
Py_DECREF(x);
}
/* Create a new int object from a C long int */
PyObject *
PyLong_FromLong(long ival)
{
PyLongObject *v;
unsigned long abs_ival, t;
int ndigits;
/* Handle small and medium cases. */
if (IS_SMALL_INT(ival)) {
return get_small_int((sdigit)ival);
}
if (-(long)PyLong_MASK <= ival && ival <= (long)PyLong_MASK) {
return _PyLong_FromMedium((sdigit)ival);
}
/* Count digits (at least two - smaller cases were handled above). */
abs_ival = ival < 0 ? 0U-(unsigned long)ival : (unsigned long)ival;
/* Do shift in two steps to avoid possible undefined behavior. */
t = abs_ival >> PyLong_SHIFT >> PyLong_SHIFT;
ndigits = 2;
while (t) {
++ndigits;
t >>= PyLong_SHIFT;
}
/* Construct output value. */
v = _PyLong_New(ndigits);
if (v != NULL) {
digit *p = v->long_value.ob_digit;
_PyLong_SetSignAndDigitCount(v, ival < 0 ? -1 : 1, ndigits);
t = abs_ival;
while (t) {
*p++ = (digit)(t & PyLong_MASK);
t >>= PyLong_SHIFT;
}
}
return (PyObject *)v;
}
#define PYLONG_FROM_UINT(INT_TYPE, ival) \
do { \
if (IS_SMALL_UINT(ival)) { \
return get_small_int((sdigit)(ival)); \
} \
/* Count the number of Python digits. */ \
Py_ssize_t ndigits = 0; \
INT_TYPE t = (ival); \
while (t) { \
++ndigits; \
t >>= PyLong_SHIFT; \
} \
PyLongObject *v = _PyLong_New(ndigits); \
if (v == NULL) { \
return NULL; \
} \
digit *p = v->long_value.ob_digit; \
while ((ival)) { \
*p++ = (digit)((ival) & PyLong_MASK); \
(ival) >>= PyLong_SHIFT; \
} \
return (PyObject *)v; \
} while(0)
/* Create a new int object from a C unsigned long int */
PyObject *
PyLong_FromUnsignedLong(unsigned long ival)
{
PYLONG_FROM_UINT(unsigned long, ival);
}
/* Create a new int object from a C unsigned long long int. */
PyObject *
PyLong_FromUnsignedLongLong(unsigned long long ival)
{
PYLONG_FROM_UINT(unsigned long long, ival);
}
/* Create a new int object from a C size_t. */
PyObject *
PyLong_FromSize_t(size_t ival)
{
PYLONG_FROM_UINT(size_t, ival);
}
/* Create a new int object from a C double */
PyObject *
PyLong_FromDouble(double dval)
{
/* Try to get out cheap if this fits in a long. When a finite value of real
* floating type is converted to an integer type, the value is truncated
* toward zero. If the value of the integral part cannot be represented by
* the integer type, the behavior is undefined. Thus, we must check that
* value is in range (LONG_MIN - 1, LONG_MAX + 1). If a long has more bits
* of precision than a double, casting LONG_MIN - 1 to double may yield an
* approximation, but LONG_MAX + 1 is a power of two and can be represented
* as double exactly (assuming FLT_RADIX is 2 or 16), so for simplicity
* check against [-(LONG_MAX + 1), LONG_MAX + 1).
*/
const double int_max = (unsigned long)LONG_MAX + 1;
if (-int_max < dval && dval < int_max) {
return PyLong_FromLong((long)dval);
}
PyLongObject *v;
double frac;
int i, ndig, expo, neg;
neg = 0;
if (isinf(dval)) {
PyErr_SetString(PyExc_OverflowError,
"cannot convert float infinity to integer");
return NULL;
}
if (isnan(dval)) {
PyErr_SetString(PyExc_ValueError,
"cannot convert float NaN to integer");
return NULL;
}
if (dval < 0.0) {
neg = 1;
dval = -dval;
}
frac = frexp(dval, &expo); /* dval = frac*2**expo; 0.0 <= frac < 1.0 */
assert(expo > 0);
ndig = (expo-1) / PyLong_SHIFT + 1; /* Number of 'digits' in result */
v = _PyLong_New(ndig);
if (v == NULL)
return NULL;
frac = ldexp(frac, (expo-1) % PyLong_SHIFT + 1);
for (i = ndig; --i >= 0; ) {
digit bits = (digit)frac;
v->long_value.ob_digit[i] = bits;
frac = frac - (double)bits;
frac = ldexp(frac, PyLong_SHIFT);
}
if (neg) {
_PyLong_FlipSign(v);
}
return (PyObject *)v;
}
/* Checking for overflow in PyLong_AsLong is a PITA since C doesn't define
* anything about what happens when a signed integer operation overflows,
* and some compilers think they're doing you a favor by being "clever"
* then. The bit pattern for the largest positive signed long is
* (unsigned long)LONG_MAX, and for the smallest negative signed long
* it is abs(LONG_MIN), which we could write -(unsigned long)LONG_MIN.
* However, some other compilers warn about applying unary minus to an
* unsigned operand. Hence the weird "0-".
*/
#define PY_ABS_LONG_MIN (0-(unsigned long)LONG_MIN)
#define PY_ABS_SSIZE_T_MIN (0-(size_t)PY_SSIZE_T_MIN)
/* Get a C long int from an int object or any object that has an __index__
method.
On overflow, return -1 and set *overflow to 1 or -1 depending on the sign of
the result. Otherwise *overflow is 0.
For other errors (e.g., TypeError), return -1 and set an error condition.
In this case *overflow will be 0.
*/
long
PyLong_AsLongAndOverflow(PyObject *vv, int *overflow)
{
/* This version by Tim Peters */
PyLongObject *v;
unsigned long x, prev;
long res;
Py_ssize_t i;
int sign;
int do_decref = 0; /* if PyNumber_Index was called */
*overflow = 0;
if (vv == NULL) {
PyErr_BadInternalCall();
return -1;
}
if (PyLong_Check(vv)) {
v = (PyLongObject *)vv;
}
else {
v = (PyLongObject *)_PyNumber_Index(vv);
if (v == NULL)
return -1;
do_decref = 1;
}
if (_PyLong_IsCompact(v)) {
#if SIZEOF_LONG < SIZEOF_SIZE_T
Py_ssize_t tmp = _PyLong_CompactValue(v);
if (tmp < LONG_MIN) {
*overflow = -1;
res = -1;
}
else if (tmp > LONG_MAX) {
*overflow = 1;
res = -1;
}
else {
res = (long)tmp;
}
#else
res = _PyLong_CompactValue(v);
#endif
}
else {
res = -1;
i = _PyLong_DigitCount(v);
sign = _PyLong_NonCompactSign(v);
x = 0;
while (--i >= 0) {
prev = x;
x = (x << PyLong_SHIFT) | v->long_value.ob_digit[i];
if ((x >> PyLong_SHIFT) != prev) {
*overflow = sign;
goto exit;
}
}
/* Haven't lost any bits, but casting to long requires extra
* care (see comment above).
*/
if (x <= (unsigned long)LONG_MAX) {
res = (long)x * sign;
}
else if (sign < 0 && x == PY_ABS_LONG_MIN) {
res = LONG_MIN;
}
else {
*overflow = sign;
/* res is already set to -1 */
}
}
exit:
if (do_decref) {
Py_DECREF(v);
}
return res;
}
/* Get a C long int from an int object or any object that has an __index__
method. Return -1 and set an error if overflow occurs. */
long
PyLong_AsLong(PyObject *obj)
{
int overflow;
long result = PyLong_AsLongAndOverflow(obj, &overflow);
if (overflow) {
/* XXX: could be cute and give a different
message for overflow == -1 */
PyErr_SetString(PyExc_OverflowError,
"Python int too large to convert to C long");
}
return result;
}
/* Get a C int from an int object or any object that has an __index__
method. Return -1 and set an error if overflow occurs. */
int
PyLong_AsInt(PyObject *obj)
{
int overflow;
long result = PyLong_AsLongAndOverflow(obj, &overflow);
if (overflow || result > INT_MAX || result < INT_MIN) {
/* XXX: could be cute and give a different
message for overflow == -1 */
PyErr_SetString(PyExc_OverflowError,
"Python int too large to convert to C int");
return -1;
}
return (int)result;
}
/* Get a Py_ssize_t from an int object.
Returns -1 and sets an error condition if overflow occurs. */
Py_ssize_t
PyLong_AsSsize_t(PyObject *vv) {
PyLongObject *v;
size_t x, prev;
Py_ssize_t i;
int sign;
if (vv == NULL) {
PyErr_BadInternalCall();
return -1;
}
if (!PyLong_Check(vv)) {
PyErr_SetString(PyExc_TypeError, "an integer is required");
return -1;
}
v = (PyLongObject *)vv;
if (_PyLong_IsCompact(v)) {
return _PyLong_CompactValue(v);
}
i = _PyLong_DigitCount(v);
sign = _PyLong_NonCompactSign(v);
x = 0;
while (--i >= 0) {
prev = x;
x = (x << PyLong_SHIFT) | v->long_value.ob_digit[i];
if ((x >> PyLong_SHIFT) != prev)
goto overflow;
}
/* Haven't lost any bits, but casting to a signed type requires
* extra care (see comment above).
*/
if (x <= (size_t)PY_SSIZE_T_MAX) {
return (Py_ssize_t)x * sign;
}
else if (sign < 0 && x == PY_ABS_SSIZE_T_MIN) {
return PY_SSIZE_T_MIN;
}
/* else overflow */
overflow:
PyErr_SetString(PyExc_OverflowError,
"Python int too large to convert to C ssize_t");
return -1;
}
/* Get a C unsigned long int from an int object.
Returns -1 and sets an error condition if overflow occurs. */
unsigned long
PyLong_AsUnsignedLong(PyObject *vv)
{
PyLongObject *v;
unsigned long x, prev;
Py_ssize_t i;
if (vv == NULL) {
PyErr_BadInternalCall();
return (unsigned long)-1;
}
if (!PyLong_Check(vv)) {
PyErr_SetString(PyExc_TypeError, "an integer is required");
return (unsigned long)-1;
}
v = (PyLongObject *)vv;
if (_PyLong_IsNonNegativeCompact(v)) {
#if SIZEOF_LONG < SIZEOF_SIZE_T
size_t tmp = (size_t)_PyLong_CompactValue(v);
unsigned long res = (unsigned long)tmp;
if (res != tmp) {
goto overflow;
}
return res;
#else
return (unsigned long)(size_t)_PyLong_CompactValue(v);
#endif
}
if (_PyLong_IsNegative(v)) {
PyErr_SetString(PyExc_OverflowError,
"can't convert negative value to unsigned int");
return (unsigned long) -1;
}
i = _PyLong_DigitCount(v);
x = 0;
while (--i >= 0) {
prev = x;
x = (x << PyLong_SHIFT) | v->long_value.ob_digit[i];
if ((x >> PyLong_SHIFT) != prev) {
goto overflow;
}
}
return x;
overflow:
PyErr_SetString(PyExc_OverflowError,
"Python int too large to convert "
"to C unsigned long");
return (unsigned long) -1;
}
/* Get a C size_t from an int object. Returns (size_t)-1 and sets
an error condition if overflow occurs. */
size_t
PyLong_AsSize_t(PyObject *vv)
{
PyLongObject *v;
size_t x, prev;
Py_ssize_t i;
if (vv == NULL) {
PyErr_BadInternalCall();
return (size_t) -1;
}
if (!PyLong_Check(vv)) {
PyErr_SetString(PyExc_TypeError, "an integer is required");
return (size_t)-1;
}
v = (PyLongObject *)vv;
if (_PyLong_IsNonNegativeCompact(v)) {
return (size_t)_PyLong_CompactValue(v);
}
if (_PyLong_IsNegative(v)) {
PyErr_SetString(PyExc_OverflowError,
"can't convert negative value to size_t");
return (size_t) -1;
}
i = _PyLong_DigitCount(v);
x = 0;
while (--i >= 0) {
prev = x;
x = (x << PyLong_SHIFT) | v->long_value.ob_digit[i];
if ((x >> PyLong_SHIFT) != prev) {
PyErr_SetString(PyExc_OverflowError,
"Python int too large to convert to C size_t");
return (size_t) -1;
}
}
return x;
}
/* Get a C unsigned long int from an int object, ignoring the high bits.
Returns -1 and sets an error condition if an error occurs. */
static unsigned long
_PyLong_AsUnsignedLongMask(PyObject *vv)
{
PyLongObject *v;
unsigned long x;
Py_ssize_t i;
if (vv == NULL || !PyLong_Check(vv)) {
PyErr_BadInternalCall();
return (unsigned long) -1;
}
v = (PyLongObject *)vv;
if (_PyLong_IsCompact(v)) {
#if SIZEOF_LONG < SIZEOF_SIZE_T
return (unsigned long)(size_t)_PyLong_CompactValue(v);
#else
return (unsigned long)(long)_PyLong_CompactValue(v);
#endif
}
i = _PyLong_DigitCount(v);
int sign = _PyLong_NonCompactSign(v);
x = 0;
while (--i >= 0) {
x = (x << PyLong_SHIFT) | v->long_value.ob_digit[i];
}
return x * sign;
}
unsigned long
PyLong_AsUnsignedLongMask(PyObject *op)
{
PyLongObject *lo;
unsigned long val;
if (op == NULL) {
PyErr_BadInternalCall();
return (unsigned long)-1;
}
if (PyLong_Check(op)) {
return _PyLong_AsUnsignedLongMask(op);
}
lo = (PyLongObject *)_PyNumber_Index(op);
if (lo == NULL)
return (unsigned long)-1;
val = _PyLong_AsUnsignedLongMask((PyObject *)lo);
Py_DECREF(lo);
return val;
}
int
_PyLong_Sign(PyObject *vv)
{
PyLongObject *v = (PyLongObject *)vv;
assert(v != NULL);
assert(PyLong_Check(v));
if (_PyLong_IsCompact(v)) {
return _PyLong_CompactSign(v);
}
return _PyLong_NonCompactSign(v);
}
int
PyLong_GetSign(PyObject *vv, int *sign)
{
if (!PyLong_Check(vv)) {
PyErr_Format(PyExc_TypeError, "expect int, got %T", vv);
return -1;
}
*sign = _PyLong_Sign(vv);
return 0;
}
static int
bit_length_digit(digit x)
{
// digit can be larger than unsigned long, but only PyLong_SHIFT bits
// of it will be ever used.
static_assert(PyLong_SHIFT <= sizeof(unsigned long) * 8,
"digit is larger than unsigned long");
return _Py_bit_length((unsigned long)x);
}
int64_t
_PyLong_NumBits(PyObject *vv)
{
PyLongObject *v = (PyLongObject *)vv;
int64_t result = 0;
Py_ssize_t ndigits;
int msd_bits;
assert(v != NULL);
assert(PyLong_Check(v));
ndigits = _PyLong_DigitCount(v);
assert(ndigits == 0 || v->long_value.ob_digit[ndigits - 1] != 0);
if (ndigits > 0) {
digit msd = v->long_value.ob_digit[ndigits - 1];
assert(ndigits <= INT64_MAX / PyLong_SHIFT);
result = (int64_t)(ndigits - 1) * PyLong_SHIFT;
msd_bits = bit_length_digit(msd);
result += msd_bits;
}
return result;
}
PyObject *
_PyLong_FromByteArray(const unsigned char* bytes, size_t n,
int little_endian, int is_signed)
{
const unsigned char* pstartbyte; /* LSB of bytes */
int incr; /* direction to move pstartbyte */
const unsigned char* pendbyte; /* MSB of bytes */
size_t numsignificantbytes; /* number of bytes that matter */
Py_ssize_t ndigits; /* number of Python int digits */
PyLongObject* v; /* result */
Py_ssize_t idigit = 0; /* next free index in v->long_value.ob_digit */
if (n == 0)
return PyLong_FromLong(0L);
if (little_endian) {
pstartbyte = bytes;
pendbyte = bytes + n - 1;
incr = 1;
}
else {
pstartbyte = bytes + n - 1;
pendbyte = bytes;
incr = -1;
}
if (is_signed)
is_signed = *pendbyte >= 0x80;
/* Compute numsignificantbytes. This consists of finding the most
significant byte. Leading 0 bytes are insignificant if the number
is positive, and leading 0xff bytes if negative. */
{
size_t i;
const unsigned char* p = pendbyte;
const int pincr = -incr; /* search MSB to LSB */
const unsigned char insignificant = is_signed ? 0xff : 0x00;
for (i = 0; i < n; ++i, p += pincr) {
if (*p != insignificant)
break;
}
numsignificantbytes = n - i;
/* 2's-comp is a bit tricky here, e.g. 0xff00 == -0x0100, so
actually has 2 significant bytes. OTOH, 0xff0001 ==
-0x00ffff, so we wouldn't *need* to bump it there; but we
do for 0xffff = -0x0001. To be safe without bothering to
check every case, bump it regardless. */
if (is_signed && numsignificantbytes < n)
++numsignificantbytes;
}
/* How many Python int digits do we need? We have
8*numsignificantbytes bits, and each Python int digit has
PyLong_SHIFT bits, so it's the ceiling of the quotient. */
/* catch overflow before it happens */
if (numsignificantbytes > (PY_SSIZE_T_MAX - PyLong_SHIFT) / 8) {
PyErr_SetString(PyExc_OverflowError,
"byte array too long to convert to int");
return NULL;
}
ndigits = (numsignificantbytes * 8 + PyLong_SHIFT - 1) / PyLong_SHIFT;
v = _PyLong_New(ndigits);
if (v == NULL)
return NULL;
/* Copy the bits over. The tricky parts are computing 2's-comp on
the fly for signed numbers, and dealing with the mismatch between
8-bit bytes and (probably) 15-bit Python digits.*/
{
size_t i;
twodigits carry = 1; /* for 2's-comp calculation */
twodigits accum = 0; /* sliding register */
unsigned int accumbits = 0; /* number of bits in accum */
const unsigned char* p = pstartbyte;
for (i = 0; i < numsignificantbytes; ++i, p += incr) {
twodigits thisbyte = *p;
/* Compute correction for 2's comp, if needed. */
if (is_signed) {
thisbyte = (0xff ^ thisbyte) + carry;
carry = thisbyte >> 8;
thisbyte &= 0xff;
}
/* Because we're going LSB to MSB, thisbyte is
more significant than what's already in accum,
so needs to be prepended to accum. */
accum |= thisbyte << accumbits;
accumbits += 8;
if (accumbits >= PyLong_SHIFT) {
/* There's enough to fill a Python digit. */
assert(idigit < ndigits);
v->long_value.ob_digit[idigit] = (digit)(accum & PyLong_MASK);
++idigit;
accum >>= PyLong_SHIFT;
accumbits -= PyLong_SHIFT;
assert(accumbits < PyLong_SHIFT);
}
}
assert(accumbits < PyLong_SHIFT);
if (accumbits) {
assert(idigit < ndigits);
v->long_value.ob_digit[idigit] = (digit)accum;
++idigit;
}
}
int sign = is_signed ? -1: 1;
if (idigit == 0) {
sign = 0;
}
_PyLong_SetSignAndDigitCount(v, sign, idigit);
return (PyObject *)maybe_small_long(long_normalize(v));
}
int
_PyLong_AsByteArray(PyLongObject* v,
unsigned char* bytes, size_t n,
int little_endian, int is_signed,
int with_exceptions)
{
Py_ssize_t i; /* index into v->long_value.ob_digit */
Py_ssize_t ndigits; /* number of digits */
twodigits accum; /* sliding register */
unsigned int accumbits; /* # bits in accum */
int do_twos_comp; /* store 2's-comp? is_signed and v < 0 */
digit carry; /* for computing 2's-comp */
size_t j; /* # bytes filled */
unsigned char* p; /* pointer to next byte in bytes */
int pincr; /* direction to move p */
assert(v != NULL && PyLong_Check(v));
ndigits = _PyLong_DigitCount(v);
if (_PyLong_IsNegative(v)) {
if (!is_signed) {
if (with_exceptions) {
PyErr_SetString(PyExc_OverflowError,
"can't convert negative int to unsigned");
}
return -1;
}
do_twos_comp = 1;
}
else {
do_twos_comp = 0;
}
if (little_endian) {
p = bytes;
pincr = 1;
}
else {
p = bytes + n - 1;
pincr = -1;
}
/* Copy over all the Python digits.
It's crucial that every Python digit except for the MSD contribute
exactly PyLong_SHIFT bits to the total, so first assert that the int is
normalized.
NOTE: PyLong_AsNativeBytes() assumes that this function will fill in 'n'
bytes even if it eventually fails to convert the whole number. Make sure
you account for that if you are changing this algorithm to return without
doing that.
*/
assert(ndigits == 0 || v->long_value.ob_digit[ndigits - 1] != 0);
j = 0;
accum = 0;
accumbits = 0;
carry = do_twos_comp ? 1 : 0;
for (i = 0; i < ndigits; ++i) {
digit thisdigit = v->long_value.ob_digit[i];
if (do_twos_comp) {
thisdigit = (thisdigit ^ PyLong_MASK) + carry;
carry = thisdigit >> PyLong_SHIFT;
thisdigit &= PyLong_MASK;
}
/* Because we're going LSB to MSB, thisdigit is more
significant than what's already in accum, so needs to be
prepended to accum. */
accum |= (twodigits)thisdigit << accumbits;
/* The most-significant digit may be (probably is) at least
partly empty. */
if (i == ndigits - 1) {
/* Count # of sign bits -- they needn't be stored,
* although for signed conversion we need later to
* make sure at least one sign bit gets stored. */
digit s = do_twos_comp ? thisdigit ^ PyLong_MASK : thisdigit;
while (s != 0) {
s >>= 1;
accumbits++;
}
}
else
accumbits += PyLong_SHIFT;
/* Store as many bytes as possible. */
while (accumbits >= 8) {
if (j >= n)
goto Overflow;
++j;
*p = (unsigned char)(accum & 0xff);
p += pincr;
accumbits -= 8;
accum >>= 8;
}
}
/* Store the straggler (if any). */
assert(accumbits < 8);
assert(carry == 0); /* else do_twos_comp and *every* digit was 0 */
if (accumbits > 0) {
if (j >= n)
goto Overflow;
++j;
if (do_twos_comp) {
/* Fill leading bits of the byte with sign bits
(appropriately pretending that the int had an
infinite supply of sign bits). */
accum |= (~(twodigits)0) << accumbits;
}
*p = (unsigned char)(accum & 0xff);
p += pincr;
}
else if (j == n && n > 0 && is_signed) {
/* The main loop filled the byte array exactly, so the code
just above didn't get to ensure there's a sign bit, and the
loop below wouldn't add one either. Make sure a sign bit
exists. */
unsigned char msb = *(p - pincr);
int sign_bit_set = msb >= 0x80;
assert(accumbits == 0);
if (sign_bit_set == do_twos_comp)
return 0;
else
goto Overflow;
}
/* Fill remaining bytes with copies of the sign bit. */
{
unsigned char signbyte = do_twos_comp ? 0xffU : 0U;
for ( ; j < n; ++j, p += pincr)
*p = signbyte;
}
return 0;
Overflow:
if (with_exceptions) {
PyErr_SetString(PyExc_OverflowError, "int too big to convert");
}
return -1;
}
// Refactored out for readability, not reuse
static inline int
_fits_in_n_bits(Py_ssize_t v, Py_ssize_t n)
{
if (n >= (Py_ssize_t)sizeof(Py_ssize_t) * 8) {
return 1;
}
// If all bits above n are the same, we fit.
// (Use n-1 if we require the sign bit to be consistent.)
Py_ssize_t v_extended = v >> ((int)n - 1);
return v_extended == 0 || v_extended == -1;
}
static inline int
_resolve_endianness(int *endianness)
{
if (*endianness == -1 || (*endianness & 2)) {
*endianness = PY_LITTLE_ENDIAN;
} else {
*endianness &= 1;
}
assert(*endianness == 0 || *endianness == 1);
return 0;
}
Py_ssize_t
PyLong_AsNativeBytes(PyObject* vv, void* buffer, Py_ssize_t n, int flags)
{
PyLongObject *v;
union {
Py_ssize_t v;
unsigned char b[sizeof(Py_ssize_t)];
} cv;
int do_decref = 0;
Py_ssize_t res = 0;
if (vv == NULL || n < 0) {
PyErr_BadInternalCall();
return -1;
}
int little_endian = flags;
if (_resolve_endianness(&little_endian) < 0) {
return -1;
}
if (PyLong_Check(vv)) {
v = (PyLongObject *)vv;
}
else if (flags != -1 && (flags & Py_ASNATIVEBYTES_ALLOW_INDEX)) {
v = (PyLongObject *)_PyNumber_Index(vv);
if (v == NULL) {
return -1;
}
do_decref = 1;
}
else {
PyErr_Format(PyExc_TypeError, "expect int, got %T", vv);
return -1;
}
if ((flags != -1 && (flags & Py_ASNATIVEBYTES_REJECT_NEGATIVE))
&& _PyLong_IsNegative(v)) {
PyErr_SetString(PyExc_ValueError, "Cannot convert negative int");
if (do_decref) {
Py_DECREF(v);
}
return -1;
}
if (_PyLong_IsCompact(v)) {
res = 0;
cv.v = _PyLong_CompactValue(v);
/* Most paths result in res = sizeof(compact value). Only the case
* where 0 < n < sizeof(compact value) do we need to check and adjust
* our return value. */
res = sizeof(cv.b);
if (n <= 0) {
// nothing to do!
}
else if (n <= (Py_ssize_t)sizeof(cv.b)) {
#if PY_LITTLE_ENDIAN
if (little_endian) {
memcpy(buffer, cv.b, n);
}
else {
for (Py_ssize_t i = 0; i < n; ++i) {
((unsigned char*)buffer)[n - i - 1] = cv.b[i];
}
}
#else
if (little_endian) {
for (Py_ssize_t i = 0; i < n; ++i) {
((unsigned char*)buffer)[i] = cv.b[sizeof(cv.b) - i - 1];
}
}
else {
memcpy(buffer, &cv.b[sizeof(cv.b) - n], n);
}
#endif
/* If we fit, return the requested number of bytes */
if (_fits_in_n_bits(cv.v, n * 8)) {
res = n;
} else if (cv.v > 0 && _fits_in_n_bits(cv.v, n * 8 + 1)) {
/* Positive values with the MSB set do not require an
* additional bit when the caller's intent is to treat them
* as unsigned. */
if (flags == -1 || (flags & Py_ASNATIVEBYTES_UNSIGNED_BUFFER)) {
res = n;
} else {
res = n + 1;
}
}
}
else {
unsigned char fill = cv.v < 0 ? 0xFF : 0x00;
#if PY_LITTLE_ENDIAN
if (little_endian) {
memcpy(buffer, cv.b, sizeof(cv.b));
memset((char *)buffer + sizeof(cv.b), fill, n - sizeof(cv.b));
}
else {
unsigned char *b = (unsigned char *)buffer;
for (Py_ssize_t i = 0; i < n - (int)sizeof(cv.b); ++i) {
*b++ = fill;
}
for (Py_ssize_t i = sizeof(cv.b); i > 0; --i) {
*b++ = cv.b[i - 1];
}
}
#else
if (little_endian) {
unsigned char *b = (unsigned char *)buffer;
for (Py_ssize_t i = sizeof(cv.b); i > 0; --i) {
*b++ = cv.b[i - 1];
}
for (Py_ssize_t i = 0; i < n - (int)sizeof(cv.b); ++i) {
*b++ = fill;
}
}
else {
memset(buffer, fill, n - sizeof(cv.b));
memcpy((char *)buffer + n - sizeof(cv.b), cv.b, sizeof(cv.b));
}
#endif
}
}
else {
if (n > 0) {
_PyLong_AsByteArray(v, buffer, (size_t)n, little_endian, 1, 0);
}
/* Calculates the number of bits required for the *absolute* value
* of v. This does not take sign into account, only magnitude. */
int64_t nb = _PyLong_NumBits((PyObject *)v);
assert(nb >= 0);
/* Normally this would be ((nb - 1) / 8) + 1 to avoid rounding up
* multiples of 8 to the next byte, but we add an implied bit for
* the sign and it cancels out. */
res = (Py_ssize_t)(nb / 8) + 1;
/* Two edge cases exist that are best handled after extracting the
* bits. These may result in us reporting overflow when the value
* actually fits.
*/
if (n > 0 && res == n + 1 && nb % 8 == 0) {
if (_PyLong_IsNegative(v)) {
/* Values of 0x80...00 from negative values that use every
* available bit in the buffer do not require an additional
* bit to store the sign. */
int is_edge_case = 1;
unsigned char *b = (unsigned char *)buffer;
for (Py_ssize_t i = 0; i < n && is_edge_case; ++i, ++b) {
if (i == 0) {
is_edge_case = (*b == (little_endian ? 0 : 0x80));
} else if (i < n - 1) {
is_edge_case = (*b == 0);
} else {
is_edge_case = (*b == (little_endian ? 0x80 : 0));
}
}
if (is_edge_case) {
res = n;
}
}
else {
/* Positive values with the MSB set do not require an
* additional bit when the caller's intent is to treat them
* as unsigned. */
unsigned char *b = (unsigned char *)buffer;
if (b[little_endian ? n - 1 : 0] & 0x80) {
if (flags == -1 || (flags & Py_ASNATIVEBYTES_UNSIGNED_BUFFER)) {
res = n;
} else {
res = n + 1;
}
}
}
}
}
if (do_decref) {
Py_DECREF(v);
}
return res;
}
PyObject *
PyLong_FromNativeBytes(const void* buffer, size_t n, int flags)
{
if (!buffer) {
PyErr_BadInternalCall();
return NULL;
}
int little_endian = flags;
if (_resolve_endianness(&little_endian) < 0) {
return NULL;
}
return _PyLong_FromByteArray(
(const unsigned char *)buffer,
n,
little_endian,
(flags == -1 || !(flags & Py_ASNATIVEBYTES_UNSIGNED_BUFFER)) ? 1 : 0
);
}
PyObject *
PyLong_FromUnsignedNativeBytes(const void* buffer, size_t n, int flags)
{
if (!buffer) {
PyErr_BadInternalCall();
return NULL;
}
int little_endian = flags;
if (_resolve_endianness(&little_endian) < 0) {
return NULL;
}
return _PyLong_FromByteArray((const unsigned char *)buffer, n, little_endian, 0);
}
/* Create a new int object from a C pointer */
PyObject *
PyLong_FromVoidPtr(void *p)
{
#if SIZEOF_VOID_P <= SIZEOF_LONG
return PyLong_FromUnsignedLong((unsigned long)(uintptr_t)p);
#else
#if SIZEOF_LONG_LONG < SIZEOF_VOID_P
# error "PyLong_FromVoidPtr: sizeof(long long) < sizeof(void*)"
#endif
return PyLong_FromUnsignedLongLong((unsigned long long)(uintptr_t)p);
#endif /* SIZEOF_VOID_P <= SIZEOF_LONG */
}
/* Get a C pointer from an int object. */
void *
PyLong_AsVoidPtr(PyObject *vv)
{
#if SIZEOF_VOID_P <= SIZEOF_LONG
long x;
if (PyLong_Check(vv) && _PyLong_IsNegative((PyLongObject *)vv)) {
x = PyLong_AsLong(vv);
}
else {
x = PyLong_AsUnsignedLong(vv);
}
#else
#if SIZEOF_LONG_LONG < SIZEOF_VOID_P
# error "PyLong_AsVoidPtr: sizeof(long long) < sizeof(void*)"
#endif
long long x;
if (PyLong_Check(vv) && _PyLong_IsNegative((PyLongObject *)vv)) {
x = PyLong_AsLongLong(vv);
}
else {
x = PyLong_AsUnsignedLongLong(vv);
}
#endif /* SIZEOF_VOID_P <= SIZEOF_LONG */
if (x == -1 && PyErr_Occurred())
return NULL;
return (void *)x;
}
/* Initial long long support by Chris Herborth (chrish@qnx.com), later
* rewritten to use the newer PyLong_{As,From}ByteArray API.
*/
#define PY_ABS_LLONG_MIN (0-(unsigned long long)LLONG_MIN)
/* Create a new int object from a C long long int. */
PyObject *
PyLong_FromLongLong(long long ival)
{
PyLongObject *v;
unsigned long long abs_ival, t;
int ndigits;
/* Handle small and medium cases. */
if (IS_SMALL_INT(ival)) {
return get_small_int((sdigit)ival);
}
if (-(long long)PyLong_MASK <= ival && ival <= (long long)PyLong_MASK) {
return _PyLong_FromMedium((sdigit)ival);
}
/* Count digits (at least two - smaller cases were handled above). */
abs_ival = ival < 0 ? 0U-(unsigned long long)ival : (unsigned long long)ival;
/* Do shift in two steps to avoid possible undefined behavior. */
t = abs_ival >> PyLong_SHIFT >> PyLong_SHIFT;
ndigits = 2;
while (t) {
++ndigits;
t >>= PyLong_SHIFT;
}
/* Construct output value. */
v = _PyLong_New(ndigits);
if (v != NULL) {
digit *p = v->long_value.ob_digit;
_PyLong_SetSignAndDigitCount(v, ival < 0 ? -1 : 1, ndigits);
t = abs_ival;
while (t) {
*p++ = (digit)(t & PyLong_MASK);
t >>= PyLong_SHIFT;
}
}
return (PyObject *)v;
}
/* Create a new int object from a C Py_ssize_t. */
PyObject *
PyLong_FromSsize_t(Py_ssize_t ival)
{
PyLongObject *v;
size_t abs_ival;
size_t t; /* unsigned so >> doesn't propagate sign bit */
int ndigits = 0;
int negative = 0;
if (IS_SMALL_INT(ival)) {
return get_small_int((sdigit)ival);
}
if (ival < 0) {
/* avoid signed overflow when ival = SIZE_T_MIN */
abs_ival = (size_t)(-1-ival)+1;
negative = 1;
}
else {
abs_ival = (size_t)ival;
}
/* Count the number of Python digits. */
t = abs_ival;
while (t) {
++ndigits;
t >>= PyLong_SHIFT;
}
v = _PyLong_New(ndigits);
if (v != NULL) {
digit *p = v->long_value.ob_digit;
_PyLong_SetSignAndDigitCount(v, negative ? -1 : 1, ndigits);
t = abs_ival;
while (t) {
*p++ = (digit)(t & PyLong_MASK);
t >>= PyLong_SHIFT;
}
}
return (PyObject *)v;
}
/* Get a C long long int from an int object or any object that has an
__index__ method. Return -1 and set an error if overflow occurs. */
long long
PyLong_AsLongLong(PyObject *vv)
{
PyLongObject *v;
long long bytes;
int res;
int do_decref = 0; /* if PyNumber_Index was called */
if (vv == NULL) {
PyErr_BadInternalCall();
return -1;
}
if (PyLong_Check(vv)) {
v = (PyLongObject *)vv;
}
else {
v = (PyLongObject *)_PyNumber_Index(vv);
if (v == NULL)
return -1;
do_decref = 1;
}
if (_PyLong_IsCompact(v)) {
res = 0;
bytes = _PyLong_CompactValue(v);
}
else {
res = _PyLong_AsByteArray((PyLongObject *)v, (unsigned char *)&bytes,
SIZEOF_LONG_LONG, PY_LITTLE_ENDIAN, 1, 1);
}
if (do_decref) {
Py_DECREF(v);
}
/* Plan 9 can't handle long long in ? : expressions */
if (res < 0)
return (long long)-1;
else
return bytes;
}
/* Get a C unsigned long long int from an int object.
Return -1 and set an error if overflow occurs. */
unsigned long long
PyLong_AsUnsignedLongLong(PyObject *vv)
{
PyLongObject *v;
unsigned long long bytes;
int res;
if (vv == NULL) {
PyErr_BadInternalCall();
return (unsigned long long)-1;
}
if (!PyLong_Check(vv)) {
PyErr_SetString(PyExc_TypeError, "an integer is required");
return (unsigned long long)-1;
}
v = (PyLongObject*)vv;
if (_PyLong_IsNonNegativeCompact(v)) {
res = 0;
#if SIZEOF_LONG_LONG < SIZEOF_SIZE_T
size_t tmp = (size_t)_PyLong_CompactValue(v);
bytes = (unsigned long long)tmp;
if (bytes != tmp) {
PyErr_SetString(PyExc_OverflowError,
"Python int too large to convert "
"to C unsigned long long");
res = -1;
}
#else
bytes = (unsigned long long)(size_t)_PyLong_CompactValue(v);
#endif
}
else {
res = _PyLong_AsByteArray((PyLongObject *)vv, (unsigned char *)&bytes,
SIZEOF_LONG_LONG, PY_LITTLE_ENDIAN, 0, 1);
}
/* Plan 9 can't handle long long in ? : expressions */
if (res < 0)
return (unsigned long long)res;
else
return bytes;
}
/* Get a C unsigned long int from an int object, ignoring the high bits.
Returns -1 and sets an error condition if an error occurs. */
static unsigned long long
_PyLong_AsUnsignedLongLongMask(PyObject *vv)
{
PyLongObject *v;
unsigned long long x;
Py_ssize_t i;
int sign;
if (vv == NULL || !PyLong_Check(vv)) {
PyErr_BadInternalCall();
return (unsigned long long) -1;
}
v = (PyLongObject *)vv;
if (_PyLong_IsCompact(v)) {
#if SIZEOF_LONG_LONG < SIZEOF_SIZE_T
return (unsigned long long)(size_t)_PyLong_CompactValue(v);
#else
return (unsigned long long)(long long)_PyLong_CompactValue(v);
#endif
}
i = _PyLong_DigitCount(v);
sign = _PyLong_NonCompactSign(v);
x = 0;
while (--i >= 0) {
x = (x << PyLong_SHIFT) | v->long_value.ob_digit[i];
}
return x * sign;
}
unsigned long long
PyLong_AsUnsignedLongLongMask(PyObject *op)
{
PyLongObject *lo;
unsigned long long val;
if (op == NULL) {
PyErr_BadInternalCall();
return (unsigned long long)-1;
}
if (PyLong_Check(op)) {
return _PyLong_AsUnsignedLongLongMask(op);
}
lo = (PyLongObject *)_PyNumber_Index(op);
if (lo == NULL)
return (unsigned long long)-1;
val = _PyLong_AsUnsignedLongLongMask((PyObject *)lo);
Py_DECREF(lo);
return val;
}
/* Get a C long long int from an int object or any object that has an
__index__ method.
On overflow, return -1 and set *overflow to 1 or -1 depending on the sign of
the result. Otherwise *overflow is 0.
For other errors (e.g., TypeError), return -1 and set an error condition.
In this case *overflow will be 0.
*/
long long
PyLong_AsLongLongAndOverflow(PyObject *vv, int *overflow)
{
/* This version by Tim Peters */
PyLongObject *v;
unsigned long long x, prev;
long long res;
Py_ssize_t i;
int sign;
int do_decref = 0; /* if PyNumber_Index was called */
*overflow = 0;
if (vv == NULL) {
PyErr_BadInternalCall();
return -1;
}
if (PyLong_Check(vv)) {
v = (PyLongObject *)vv;
}
else {
v = (PyLongObject *)_PyNumber_Index(vv);
if (v == NULL)
return -1;
do_decref = 1;
}
if (_PyLong_IsCompact(v)) {
#if SIZEOF_LONG_LONG < SIZEOF_SIZE_T
Py_ssize_t tmp = _PyLong_CompactValue(v);
if (tmp < LLONG_MIN) {
*overflow = -1;
res = -1;
}
else if (tmp > LLONG_MAX) {
*overflow = 1;
res = -1;
}
else {
res = (long long)tmp;
}
#else
res = _PyLong_CompactValue(v);
#endif
}
else {
i = _PyLong_DigitCount(v);
sign = _PyLong_NonCompactSign(v);
x = 0;
while (--i >= 0) {
prev = x;
x = (x << PyLong_SHIFT) + v->long_value.ob_digit[i];
if ((x >> PyLong_SHIFT) != prev) {
*overflow = sign;
res = -1;
goto exit;
}
}
/* Haven't lost any bits, but casting to long requires extra
* care (see comment above).
*/
if (x <= (unsigned long long)LLONG_MAX) {
res = (long long)x * sign;
}
else if (sign < 0 && x == PY_ABS_LLONG_MIN) {
res = LLONG_MIN;
}
else {
*overflow = sign;
res = -1;
}
}
exit:
if (do_decref) {
Py_DECREF(v);
}
return res;
}
int
_PyLong_UnsignedShort_Converter(PyObject *obj, void *ptr)
{
unsigned long uval;
if (PyLong_Check(obj) && _PyLong_IsNegative((PyLongObject *)obj)) {
PyErr_SetString(PyExc_ValueError, "value must be positive");
return 0;
}
uval = PyLong_AsUnsignedLong(obj);
if (uval == (unsigned long)-1 && PyErr_Occurred())
return 0;
if (uval > USHRT_MAX) {
PyErr_SetString(PyExc_OverflowError,
"Python int too large for C unsigned short");
return 0;
}
*(unsigned short *)ptr = Py_SAFE_DOWNCAST(uval, unsigned long, unsigned short);
return 1;
}
int
_PyLong_UnsignedInt_Converter(PyObject *obj, void *ptr)
{
unsigned long uval;
if (PyLong_Check(obj) && _PyLong_IsNegative((PyLongObject *)obj)) {
PyErr_SetString(PyExc_ValueError, "value must be positive");
return 0;
}
uval = PyLong_AsUnsignedLong(obj);
if (uval == (unsigned long)-1 && PyErr_Occurred())
return 0;
if (uval > UINT_MAX) {
PyErr_SetString(PyExc_OverflowError,
"Python int too large for C unsigned int");
return 0;
}
*(unsigned int *)ptr = Py_SAFE_DOWNCAST(uval, unsigned long, unsigned int);
return 1;
}
int
_PyLong_UnsignedLong_Converter(PyObject *obj, void *ptr)
{
unsigned long uval;
if (PyLong_Check(obj) && _PyLong_IsNegative((PyLongObject *)obj)) {
PyErr_SetString(PyExc_ValueError, "value must be positive");
return 0;
}
uval = PyLong_AsUnsignedLong(obj);
if (uval == (unsigned long)-1 && PyErr_Occurred())
return 0;
*(unsigned long *)ptr = uval;
return 1;
}
int
_PyLong_UnsignedLongLong_Converter(PyObject *obj, void *ptr)
{
unsigned long long uval;
if (PyLong_Check(obj) && _PyLong_IsNegative((PyLongObject *)obj)) {
PyErr_SetString(PyExc_ValueError, "value must be positive");
return 0;
}
uval = PyLong_AsUnsignedLongLong(obj);
if (uval == (unsigned long long)-1 && PyErr_Occurred())
return 0;
*(unsigned long long *)ptr = uval;
return 1;
}
int
_PyLong_Size_t_Converter(PyObject *obj, void *ptr)
{
size_t uval;
if (PyLong_Check(obj) && _PyLong_IsNegative((PyLongObject *)obj)) {
PyErr_SetString(PyExc_ValueError, "value must be positive");
return 0;
}
uval = PyLong_AsSize_t(obj);
if (uval == (size_t)-1 && PyErr_Occurred())
return 0;
*(size_t *)ptr = uval;
return 1;
}
#define CHECK_BINOP(v,w) \
do { \
if (!PyLong_Check(v) || !PyLong_Check(w)) \
Py_RETURN_NOTIMPLEMENTED; \
} while(0)
/* x[0:m] and y[0:n] are digit vectors, LSD first, m >= n required. x[0:n]
* is modified in place, by adding y to it. Carries are propagated as far as
* x[m-1], and the remaining carry (0 or 1) is returned.
*/
static digit
v_iadd(digit *x, Py_ssize_t m, digit *y, Py_ssize_t n)
{
Py_ssize_t i;
digit carry = 0;
assert(m >= n);
for (i = 0; i < n; ++i) {
carry += x[i] + y[i];
x[i] = carry & PyLong_MASK;
carry >>= PyLong_SHIFT;
assert((carry & 1) == carry);
}
for (; carry && i < m; ++i) {
carry += x[i];
x[i] = carry & PyLong_MASK;
carry >>= PyLong_SHIFT;
assert((carry & 1) == carry);
}
return carry;
}
/* x[0:m] and y[0:n] are digit vectors, LSD first, m >= n required. x[0:n]
* is modified in place, by subtracting y from it. Borrows are propagated as
* far as x[m-1], and the remaining borrow (0 or 1) is returned.
*/
static digit
v_isub(digit *x, Py_ssize_t m, digit *y, Py_ssize_t n)
{
Py_ssize_t i;
digit borrow = 0;
assert(m >= n);
for (i = 0; i < n; ++i) {
borrow = x[i] - y[i] - borrow;
x[i] = borrow & PyLong_MASK;
borrow >>= PyLong_SHIFT;
borrow &= 1; /* keep only 1 sign bit */
}
for (; borrow && i < m; ++i) {
borrow = x[i] - borrow;
x[i] = borrow & PyLong_MASK;
borrow >>= PyLong_SHIFT;
borrow &= 1;
}
return borrow;
}
/* Shift digit vector a[0:m] d bits left, with 0 <= d < PyLong_SHIFT. Put
* result in z[0:m], and return the d bits shifted out of the top.
*/
static digit
v_lshift(digit *z, digit *a, Py_ssize_t m, int d)
{
Py_ssize_t i;
digit carry = 0;
assert(0 <= d && d < PyLong_SHIFT);
for (i=0; i < m; i++) {
twodigits acc = (twodigits)a[i] << d | carry;
z[i] = (digit)acc & PyLong_MASK;
carry = (digit)(acc >> PyLong_SHIFT);
}
return carry;
}
/* Shift digit vector a[0:m] d bits right, with 0 <= d < PyLong_SHIFT. Put
* result in z[0:m], and return the d bits shifted out of the bottom.
*/
static digit
v_rshift(digit *z, digit *a, Py_ssize_t m, int d)
{
Py_ssize_t i;
digit carry = 0;
digit mask = ((digit)1 << d) - 1U;
assert(0 <= d && d < PyLong_SHIFT);
for (i=m; i-- > 0;) {
twodigits acc = (twodigits)carry << PyLong_SHIFT | a[i];
carry = (digit)acc & mask;
z[i] = (digit)(acc >> d);
}
return carry;
}
/* Divide long pin, w/ size digits, by non-zero digit n, storing quotient
in pout, and returning the remainder. pin and pout point at the LSD.
It's OK for pin == pout on entry, which saves oodles of mallocs/frees in
_PyLong_Format, but that should be done with great care since ints are
immutable.
This version of the code can be 20% faster than the pre-2022 version
on todays compilers on architectures like amd64. It evolved from Mark
Dickinson observing that a 128:64 divide instruction was always being
generated by the compiler despite us working with 30-bit digit values.
See the thread for full context:
https://mail.python.org/archives/list/python-dev@python.org/thread/ZICIMX5VFCX4IOFH5NUPVHCUJCQ4Q7QM/#NEUNFZU3TQU4CPTYZNF3WCN7DOJBBTK5
If you ever want to change this code, pay attention to performance using
different compilers, optimization levels, and cpu architectures. Beware of
PGO/FDO builds doing value specialization such as a fast path for //10. :)
Verify that 17 isn't specialized and this works as a quick test:
python -m timeit -s 'x = 10**1000; r=x//10; assert r == 10**999, r' 'x//17'
*/
static digit
inplace_divrem1(digit *pout, digit *pin, Py_ssize_t size, digit n)
{
digit remainder = 0;
assert(n > 0 && n <= PyLong_MASK);
while (--size >= 0) {
twodigits dividend;
dividend = ((twodigits)remainder << PyLong_SHIFT) | pin[size];
digit quotient;
quotient = (digit)(dividend / n);
remainder = dividend % n;
pout[size] = quotient;
}
return remainder;
}
/* Divide an integer by a digit, returning both the quotient
(as function result) and the remainder (through *prem).
The sign of a is ignored; n should not be zero. */
static PyLongObject *
divrem1(PyLongObject *a, digit n, digit *prem)
{
const Py_ssize_t size = _PyLong_DigitCount(a);
PyLongObject *z;
assert(n > 0 && n <= PyLong_MASK);
z = _PyLong_New(size);
if (z == NULL)
return NULL;
*prem = inplace_divrem1(z->long_value.ob_digit, a->long_value.ob_digit, size, n);
return long_normalize(z);
}
/* Remainder of long pin, w/ size digits, by non-zero digit n,
returning the remainder. pin points at the LSD. */
static digit
inplace_rem1(digit *pin, Py_ssize_t size, digit n)
{
twodigits rem = 0;
assert(n > 0 && n <= PyLong_MASK);
while (--size >= 0)
rem = ((rem << PyLong_SHIFT) | pin[size]) % n;
return (digit)rem;
}
/* Get the remainder of an integer divided by a digit, returning
the remainder as the result of the function. The sign of a is
ignored; n should not be zero. */
static PyLongObject *
rem1(PyLongObject *a, digit n)
{
const Py_ssize_t size = _PyLong_DigitCount(a);
assert(n > 0 && n <= PyLong_MASK);
return (PyLongObject *)PyLong_FromLong(
(long)inplace_rem1(a->long_value.ob_digit, size, n)
);
}
#ifdef WITH_PYLONG_MODULE
/* asymptotically faster long_to_decimal_string, using _pylong.py */
static int
pylong_int_to_decimal_string(PyObject *aa,
PyObject **p_output,
_PyUnicodeWriter *writer,
_PyBytesWriter *bytes_writer,
char **bytes_str)
{
PyObject *s = NULL;
PyObject *mod = PyImport_ImportModule("_pylong");
if (mod == NULL) {
return -1;
}
s = PyObject_CallMethod(mod, "int_to_decimal_string", "O", aa);
if (s == NULL) {
goto error;
}
if (!PyUnicode_Check(s)) {
PyErr_SetString(PyExc_TypeError,
"_pylong.int_to_decimal_string did not return a str");
goto error;
}
if (writer) {
Py_ssize_t size = PyUnicode_GET_LENGTH(s);
if (_PyUnicodeWriter_Prepare(writer, size, '9') == -1) {
goto error;
}
if (_PyUnicodeWriter_WriteStr(writer, s) < 0) {
goto error;
}
goto success;
}
else if (bytes_writer) {
Py_ssize_t size = PyUnicode_GET_LENGTH(s);
const void *data = PyUnicode_DATA(s);
int kind = PyUnicode_KIND(s);
*bytes_str = _PyBytesWriter_Prepare(bytes_writer, *bytes_str, size);
if (*bytes_str == NULL) {
goto error;
}
char *p = *bytes_str;
for (Py_ssize_t i=0; i < size; i++) {
Py_UCS4 ch = PyUnicode_READ(kind, data, i);
*p++ = (char) ch;
}
(*bytes_str) = p;
goto success;
}
else {
*p_output = Py_NewRef(s);
goto success;
}
error:
Py_DECREF(mod);
Py_XDECREF(s);
return -1;
success:
Py_DECREF(mod);
Py_DECREF(s);
return 0;
}
#endif /* WITH_PYLONG_MODULE */
/* Convert an integer to a base 10 string. Returns a new non-shared
string. (Return value is non-shared so that callers can modify the
returned value if necessary.) */
static int
long_to_decimal_string_internal(PyObject *aa,
PyObject **p_output,
_PyUnicodeWriter *writer,
_PyBytesWriter *bytes_writer,
char **bytes_str)
{
PyLongObject *scratch, *a;
PyObject *str = NULL;
Py_ssize_t size, strlen, size_a, i, j;
digit *pout, *pin, rem, tenpow;
int negative;
int d;
// writer or bytes_writer can be used, but not both at the same time.
assert(writer == NULL || bytes_writer == NULL);
a = (PyLongObject *)aa;
if (a == NULL || !PyLong_Check(a)) {
PyErr_BadInternalCall();
return -1;
}
size_a = _PyLong_DigitCount(a);
negative = _PyLong_IsNegative(a);
/* quick and dirty pre-check for overflowing the decimal digit limit,
based on the inequality 10/3 >= log2(10)
explanation in https://github.com/python/cpython/pull/96537
*/
if (size_a >= 10 * _PY_LONG_MAX_STR_DIGITS_THRESHOLD
/ (3 * PyLong_SHIFT) + 2) {
PyInterpreterState *interp = _PyInterpreterState_GET();
int max_str_digits = interp->long_state.max_str_digits;
if ((max_str_digits > 0) &&
(max_str_digits / (3 * PyLong_SHIFT) <= (size_a - 11) / 10)) {
PyErr_Format(PyExc_ValueError, _MAX_STR_DIGITS_ERROR_FMT_TO_STR,
max_str_digits);
return -1;
}
}
#if WITH_PYLONG_MODULE
if (size_a > 1000) {
/* Switch to _pylong.int_to_decimal_string(). */
return pylong_int_to_decimal_string(aa,
p_output,
writer,
bytes_writer,
bytes_str);
}
#endif
/* quick and dirty upper bound for the number of digits
required to express a in base _PyLong_DECIMAL_BASE:
#digits = 1 + floor(log2(a) / log2(_PyLong_DECIMAL_BASE))
But log2(a) < size_a * PyLong_SHIFT, and
log2(_PyLong_DECIMAL_BASE) = log2(10) * _PyLong_DECIMAL_SHIFT
> 3.3 * _PyLong_DECIMAL_SHIFT
size_a * PyLong_SHIFT / (3.3 * _PyLong_DECIMAL_SHIFT) =
size_a + size_a / d < size_a + size_a / floor(d),
where d = (3.3 * _PyLong_DECIMAL_SHIFT) /
(PyLong_SHIFT - 3.3 * _PyLong_DECIMAL_SHIFT)
*/
d = (33 * _PyLong_DECIMAL_SHIFT) /
(10 * PyLong_SHIFT - 33 * _PyLong_DECIMAL_SHIFT);
assert(size_a < PY_SSIZE_T_MAX/2);
size = 1 + size_a + size_a / d;
scratch = _PyLong_New(size);
if (scratch == NULL)
return -1;
/* convert array of base _PyLong_BASE digits in pin to an array of
base _PyLong_DECIMAL_BASE digits in pout, following Knuth (TAOCP,
Volume 2 (3rd edn), section 4.4, Method 1b). */
pin = a->long_value.ob_digit;
pout = scratch->long_value.ob_digit;
size = 0;
for (i = size_a; --i >= 0; ) {
digit hi = pin[i];
for (j = 0; j < size; j++) {
twodigits z = (twodigits)pout[j] << PyLong_SHIFT | hi;
hi = (digit)(z / _PyLong_DECIMAL_BASE);
pout[j] = (digit)(z - (twodigits)hi *
_PyLong_DECIMAL_BASE);
}
while (hi) {
pout[size++] = hi % _PyLong_DECIMAL_BASE;
hi /= _PyLong_DECIMAL_BASE;
}
/* check for keyboard interrupt */
SIGCHECK({
Py_DECREF(scratch);
return -1;
});
}
/* pout should have at least one digit, so that the case when a = 0
works correctly */
if (size == 0)
pout[size++] = 0;
/* calculate exact length of output string, and allocate */
strlen = negative + 1 + (size - 1) * _PyLong_DECIMAL_SHIFT;
tenpow = 10;
rem = pout[size-1];
while (rem >= tenpow) {
tenpow *= 10;
strlen++;
}
if (strlen > _PY_LONG_MAX_STR_DIGITS_THRESHOLD) {
PyInterpreterState *interp = _PyInterpreterState_GET();
int max_str_digits = interp->long_state.max_str_digits;
Py_ssize_t strlen_nosign = strlen - negative;
if ((max_str_digits > 0) && (strlen_nosign > max_str_digits)) {
Py_DECREF(scratch);
PyErr_Format(PyExc_ValueError, _MAX_STR_DIGITS_ERROR_FMT_TO_STR,
max_str_digits);
return -1;
}
}
if (writer) {
if (_PyUnicodeWriter_Prepare(writer, strlen, '9') == -1) {
Py_DECREF(scratch);
return -1;
}
}
else if (bytes_writer) {
*bytes_str = _PyBytesWriter_Prepare(bytes_writer, *bytes_str, strlen);
if (*bytes_str == NULL) {
Py_DECREF(scratch);
return -1;
}
}
else {
str = PyUnicode_New(strlen, '9');
if (str == NULL) {
Py_DECREF(scratch);
return -1;
}
}
#define WRITE_DIGITS(p) \
do { \
/* pout[0] through pout[size-2] contribute exactly \
_PyLong_DECIMAL_SHIFT digits each */ \
for (i=0; i < size - 1; i++) { \
rem = pout[i]; \
for (j = 0; j < _PyLong_DECIMAL_SHIFT; j++) { \
*--p = '0' + rem % 10; \
rem /= 10; \
} \
} \
/* pout[size-1]: always produce at least one decimal digit */ \
rem = pout[i]; \
do { \
*--p = '0' + rem % 10; \
rem /= 10; \
} while (rem != 0); \
\
/* and sign */ \
if (negative) \
*--p = '-'; \
} while (0)
#define WRITE_UNICODE_DIGITS(TYPE) \
do { \
if (writer) \
p = (TYPE*)PyUnicode_DATA(writer->buffer) + writer->pos + strlen; \
else \
p = (TYPE*)PyUnicode_DATA(str) + strlen; \
\
WRITE_DIGITS(p); \
\
/* check we've counted correctly */ \
if (writer) \
assert(p == ((TYPE*)PyUnicode_DATA(writer->buffer) + writer->pos)); \
else \
assert(p == (TYPE*)PyUnicode_DATA(str)); \
} while (0)
/* fill the string right-to-left */
if (bytes_writer) {
char *p = *bytes_str + strlen;
WRITE_DIGITS(p);
assert(p == *bytes_str);
}
else {
int kind = writer ? writer->kind : PyUnicode_KIND(str);
if (kind == PyUnicode_1BYTE_KIND) {
Py_UCS1 *p;
WRITE_UNICODE_DIGITS(Py_UCS1);
}
else if (kind == PyUnicode_2BYTE_KIND) {
Py_UCS2 *p;
WRITE_UNICODE_DIGITS(Py_UCS2);
}
else {
assert (kind == PyUnicode_4BYTE_KIND);
Py_UCS4 *p;
WRITE_UNICODE_DIGITS(Py_UCS4);
}
}
#undef WRITE_DIGITS
#undef WRITE_UNICODE_DIGITS
_Py_DECREF_INT(scratch);
if (writer) {
writer->pos += strlen;
}
else if (bytes_writer) {
(*bytes_str) += strlen;
}
else {
assert(_PyUnicode_CheckConsistency(str, 1));
*p_output = (PyObject *)str;
}
return 0;
}
static PyObject *
long_to_decimal_string(PyObject *aa)
{
PyObject *v;
if (long_to_decimal_string_internal(aa, &v, NULL, NULL, NULL) == -1)
return NULL;
return v;
}
/* Convert an int object to a string, using a given conversion base,
which should be one of 2, 8 or 16. Return a string object.
If base is 2, 8 or 16, add the proper prefix '0b', '0o' or '0x'
if alternate is nonzero. */
static int
long_format_binary(PyObject *aa, int base, int alternate,
PyObject **p_output, _PyUnicodeWriter *writer,
_PyBytesWriter *bytes_writer, char **bytes_str)
{
PyLongObject *a = (PyLongObject *)aa;
PyObject *v = NULL;
Py_ssize_t sz;
Py_ssize_t size_a;
int negative;
int bits;
assert(base == 2 || base == 8 || base == 16);
// writer or bytes_writer can be used, but not both at the same time.
assert(writer == NULL || bytes_writer == NULL);
if (a == NULL || !PyLong_Check(a)) {
PyErr_BadInternalCall();
return -1;
}
size_a = _PyLong_DigitCount(a);
negative = _PyLong_IsNegative(a);
/* Compute a rough upper bound for the length of the string */
switch (base) {
case 16:
bits = 4;
break;
case 8:
bits = 3;
break;
case 2:
bits = 1;
break;
default:
Py_UNREACHABLE();
}
/* Compute exact length 'sz' of output string. */
if (size_a == 0) {
sz = 1;
}
else {
Py_ssize_t size_a_in_bits;
/* Ensure overflow doesn't occur during computation of sz. */
if (size_a > (PY_SSIZE_T_MAX - 3) / PyLong_SHIFT) {
PyErr_SetString(PyExc_OverflowError,
"int too large to format");
return -1;
}
size_a_in_bits = (size_a - 1) * PyLong_SHIFT +
bit_length_digit(a->long_value.ob_digit[size_a - 1]);
/* Allow 1 character for a '-' sign. */
sz = negative + (size_a_in_bits + (bits - 1)) / bits;
}
if (alternate) {
/* 2 characters for prefix */
sz += 2;
}
if (writer) {
if (_PyUnicodeWriter_Prepare(writer, sz, 'x') == -1)
return -1;
}
else if (bytes_writer) {
*bytes_str = _PyBytesWriter_Prepare(bytes_writer, *bytes_str, sz);
if (*bytes_str == NULL)
return -1;
}
else {
v = PyUnicode_New(sz, 'x');
if (v == NULL)
return -1;
}
#define WRITE_DIGITS(p) \
do { \
if (size_a == 0) { \
*--p = '0'; \
} \
else { \
/* JRH: special case for power-of-2 bases */ \
twodigits accum = 0; \
int accumbits = 0; /* # of bits in accum */ \
Py_ssize_t i; \
for (i = 0; i < size_a; ++i) { \
accum |= (twodigits)a->long_value.ob_digit[i] << accumbits; \
accumbits += PyLong_SHIFT; \
assert(accumbits >= bits); \
do { \
char cdigit; \
cdigit = (char)(accum & (base - 1)); \
cdigit += (cdigit < 10) ? '0' : 'a'-10; \
*--p = cdigit; \
accumbits -= bits; \
accum >>= bits; \
} while (i < size_a-1 ? accumbits >= bits : accum > 0); \
} \
} \
\
if (alternate) { \
if (base == 16) \
*--p = 'x'; \
else if (base == 8) \
*--p = 'o'; \
else /* (base == 2) */ \
*--p = 'b'; \
*--p = '0'; \
} \
if (negative) \
*--p = '-'; \
} while (0)
#define WRITE_UNICODE_DIGITS(TYPE) \
do { \
if (writer) \
p = (TYPE*)PyUnicode_DATA(writer->buffer) + writer->pos + sz; \
else \
p = (TYPE*)PyUnicode_DATA(v) + sz; \
\
WRITE_DIGITS(p); \
\
if (writer) \
assert(p == ((TYPE*)PyUnicode_DATA(writer->buffer) + writer->pos)); \
else \
assert(p == (TYPE*)PyUnicode_DATA(v)); \
} while (0)
if (bytes_writer) {
char *p = *bytes_str + sz;
WRITE_DIGITS(p);
assert(p == *bytes_str);
}
else {
int kind = writer ? writer->kind : PyUnicode_KIND(v);
if (kind == PyUnicode_1BYTE_KIND) {
Py_UCS1 *p;
WRITE_UNICODE_DIGITS(Py_UCS1);
}
else if (kind == PyUnicode_2BYTE_KIND) {
Py_UCS2 *p;
WRITE_UNICODE_DIGITS(Py_UCS2);
}
else {
assert (kind == PyUnicode_4BYTE_KIND);
Py_UCS4 *p;
WRITE_UNICODE_DIGITS(Py_UCS4);
}
}
#undef WRITE_DIGITS
#undef WRITE_UNICODE_DIGITS
if (writer) {
writer->pos += sz;
}
else if (bytes_writer) {
(*bytes_str) += sz;
}
else {
assert(_PyUnicode_CheckConsistency(v, 1));
*p_output = v;
}
return 0;
}
PyObject *
_PyLong_Format(PyObject *obj, int base)
{
PyObject *str;
int err;
if (base == 10)
err = long_to_decimal_string_internal(obj, &str, NULL, NULL, NULL);
else
err = long_format_binary(obj, base, 1, &str, NULL, NULL, NULL);
if (err == -1)
return NULL;
return str;
}
int
_PyLong_FormatWriter(_PyUnicodeWriter *writer,
PyObject *obj,
int base, int alternate)
{
if (base == 10)
return long_to_decimal_string_internal(obj, NULL, writer,
NULL, NULL);
else
return long_format_binary(obj, base, alternate, NULL, writer,
NULL, NULL);
}
char*
_PyLong_FormatBytesWriter(_PyBytesWriter *writer, char *str,
PyObject *obj,
int base, int alternate)
{
char *str2;
int res;
str2 = str;
if (base == 10)
res = long_to_decimal_string_internal(obj, NULL, NULL,
writer, &str2);
else
res = long_format_binary(obj, base, alternate, NULL, NULL,
writer, &str2);
if (res < 0)
return NULL;
assert(str2 != NULL);
return str2;
}
/* Table of digit values for 8-bit string -> integer conversion.
* '0' maps to 0, ..., '9' maps to 9.
* 'a' and 'A' map to 10, ..., 'z' and 'Z' map to 35.
* All other indices map to 37.
* Note that when converting a base B string, a char c is a legitimate
* base B digit iff _PyLong_DigitValue[Py_CHARPyLong_MASK(c)] < B.
*/
unsigned char _PyLong_DigitValue[256] = {
37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37,
37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37,
37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37,
0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 37, 37, 37, 37, 37, 37,
37, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24,
25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 37, 37, 37, 37, 37,
37, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24,
25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 37, 37, 37, 37, 37,
37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37,
37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37,
37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37,
37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37,
37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37,
37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37,
37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37,
37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37,
};
/* `start` and `end` point to the start and end of a string of base `base`
* digits. base is a power of 2 (2, 4, 8, 16, or 32). An unnormalized int is
* returned in *res. The string should be already validated by the caller and
* consists only of valid digit characters and underscores. `digits` gives the
* number of digit characters.
*
* The point to this routine is that it takes time linear in the
* number of string characters.
*
* Return values:
* -1 on syntax error (exception needs to be set, *res is untouched)
* 0 else (exception may be set, in that case *res is set to NULL)
*/
static int
long_from_binary_base(const char *start, const char *end, Py_ssize_t digits, int base, PyLongObject **res)
{
const char *p;
int bits_per_char;
Py_ssize_t n;
PyLongObject *z;
twodigits accum;
int bits_in_accum;
digit *pdigit;
assert(base >= 2 && base <= 32 && (base & (base - 1)) == 0);
n = base;
for (bits_per_char = -1; n; ++bits_per_char) {
n >>= 1;
}
/* n <- the number of Python digits needed,
= ceiling((digits * bits_per_char) / PyLong_SHIFT). */
if (digits > (PY_SSIZE_T_MAX - (PyLong_SHIFT - 1)) / bits_per_char) {
PyErr_SetString(PyExc_ValueError,
"int string too large to convert");
*res = NULL;
return 0;
}
n = (digits * bits_per_char + PyLong_SHIFT - 1) / PyLong_SHIFT;
z = _PyLong_New(n);
if (z == NULL) {
*res = NULL;
return 0;
}
/* Read string from right, and fill in int from left; i.e.,
* from least to most significant in both.
*/
accum = 0;
bits_in_accum = 0;
pdigit = z->long_value.ob_digit;
p = end;
while (--p >= start) {
int k;
if (*p == '_') {
continue;
}
k = (int)_PyLong_DigitValue[Py_CHARMASK(*p)];
assert(k >= 0 && k < base);
accum |= (twodigits)k << bits_in_accum;
bits_in_accum += bits_per_char;
if (bits_in_accum >= PyLong_SHIFT) {
*pdigit++ = (digit)(accum & PyLong_MASK);
assert(pdigit - z->long_value.ob_digit <= n);
accum >>= PyLong_SHIFT;
bits_in_accum -= PyLong_SHIFT;
assert(bits_in_accum < PyLong_SHIFT);
}
}
if (bits_in_accum) {
assert(bits_in_accum <= PyLong_SHIFT);
*pdigit++ = (digit)accum;
assert(pdigit - z->long_value.ob_digit <= n);
}
while (pdigit - z->long_value.ob_digit < n)
*pdigit++ = 0;
*res = z;
return 0;
}
#ifdef WITH_PYLONG_MODULE
/* asymptotically faster str-to-long conversion for base 10, using _pylong.py */
static int
pylong_int_from_string(const char *start, const char *end, PyLongObject **res)
{
PyObject *mod = PyImport_ImportModule("_pylong");
if (mod == NULL) {
goto error;
}
PyObject *s = PyUnicode_FromStringAndSize(start, end-start);
if (s == NULL) {
Py_DECREF(mod);
goto error;
}
PyObject *result = PyObject_CallMethod(mod, "int_from_string", "O", s);
Py_DECREF(s);
Py_DECREF(mod);
if (result == NULL) {
goto error;
}
if (!PyLong_Check(result)) {
Py_DECREF(result);
PyErr_SetString(PyExc_TypeError,
"_pylong.int_from_string did not return an int");
goto error;
}
*res = (PyLongObject *)result;
return 0;
error:
*res = NULL;
return 0; // See the long_from_string_base() API comment.
}
#endif /* WITH_PYLONG_MODULE */
/***
long_from_non_binary_base: parameters and return values are the same as
long_from_binary_base.
Binary bases can be converted in time linear in the number of digits, because
Python's representation base is binary. Other bases (including decimal!) use
the simple quadratic-time algorithm below, complicated by some speed tricks.
First some math: the largest integer that can be expressed in N base-B digits
is B**N-1. Consequently, if we have an N-digit input in base B, the worst-
case number of Python digits needed to hold it is the smallest integer n s.t.
BASE**n-1 >= B**N-1 [or, adding 1 to both sides]
BASE**n >= B**N [taking logs to base BASE]
n >= log(B**N)/log(BASE) = N * log(B)/log(BASE)
The static array log_base_BASE[base] == log(base)/log(BASE) so we can compute
this quickly. A Python int with that much space is reserved near the start,
and the result is computed into it.
The input string is actually treated as being in base base**i (i.e., i digits
are processed at a time), where two more static arrays hold:
convwidth_base[base] = the largest integer i such that base**i <= BASE
convmultmax_base[base] = base ** convwidth_base[base]
The first of these is the largest i such that i consecutive input digits
must fit in a single Python digit. The second is effectively the input
base we're really using.
Viewing the input as a sequence <c0, c1, ..., c_n-1> of digits in base
convmultmax_base[base], the result is "simply"
(((c0*B + c1)*B + c2)*B + c3)*B + ... ))) + c_n-1
where B = convmultmax_base[base].
Error analysis: as above, the number of Python digits `n` needed is worst-
case
n >= N * log(B)/log(BASE)
where `N` is the number of input digits in base `B`. This is computed via
size_z = (Py_ssize_t)((scan - str) * log_base_BASE[base]) + 1;
below. Two numeric concerns are how much space this can waste, and whether
the computed result can be too small. To be concrete, assume BASE = 2**15,
which is the default (and it's unlikely anyone changes that).
Waste isn't a problem: provided the first input digit isn't 0, the difference
between the worst-case input with N digits and the smallest input with N
digits is about a factor of B, but B is small compared to BASE so at most
one allocated Python digit can remain unused on that count. If
N*log(B)/log(BASE) is mathematically an exact integer, then truncating that
and adding 1 returns a result 1 larger than necessary. However, that can't
happen: whenever B is a power of 2, long_from_binary_base() is called
instead, and it's impossible for B**i to be an integer power of 2**15 when
B is not a power of 2 (i.e., it's impossible for N*log(B)/log(BASE) to be
an exact integer when B is not a power of 2, since B**i has a prime factor
other than 2 in that case, but (2**15)**j's only prime factor is 2).
The computed result can be too small if the true value of N*log(B)/log(BASE)
is a little bit larger than an exact integer, but due to roundoff errors (in
computing log(B), log(BASE), their quotient, and/or multiplying that by N)
yields a numeric result a little less than that integer. Unfortunately, "how
close can a transcendental function get to an integer over some range?"
questions are generally theoretically intractable. Computer analysis via
continued fractions is practical: expand log(B)/log(BASE) via continued
fractions, giving a sequence i/j of "the best" rational approximations. Then
j*log(B)/log(BASE) is approximately equal to (the integer) i. This shows that
we can get very close to being in trouble, but very rarely. For example,
76573 is a denominator in one of the continued-fraction approximations to
log(10)/log(2**15), and indeed:
>>> log(10)/log(2**15)*76573
16958.000000654003
is very close to an integer. If we were working with IEEE single-precision,
rounding errors could kill us. Finding worst cases in IEEE double-precision
requires better-than-double-precision log() functions, and Tim didn't bother.
Instead the code checks to see whether the allocated space is enough as each
new Python digit is added, and copies the whole thing to a larger int if not.
This should happen extremely rarely, and in fact I don't have a test case
that triggers it(!). Instead the code was tested by artificially allocating
just 1 digit at the start, so that the copying code was exercised for every
digit beyond the first.
***/
static int
long_from_non_binary_base(const char *start, const char *end, Py_ssize_t digits, int base, PyLongObject **res)
{
twodigits c; /* current input character */
Py_ssize_t size_z;
int i;
int convwidth;
twodigits convmultmax, convmult;
digit *pz, *pzstop;
PyLongObject *z;
const char *p;
static double log_base_BASE[37] = {0.0e0,};
static int convwidth_base[37] = {0,};
static twodigits convmultmax_base[37] = {0,};
if (log_base_BASE[base] == 0.0) {
twodigits convmax = base;
int i = 1;
log_base_BASE[base] = (log((double)base) /
log((double)PyLong_BASE));
for (;;) {
twodigits next = convmax * base;
if (next > PyLong_BASE) {
break;
}
convmax = next;
++i;
}
convmultmax_base[base] = convmax;
assert(i > 0);
convwidth_base[base] = i;
}
/* Create an int object that can contain the largest possible
* integer with this base and length. Note that there's no
* need to initialize z->long_value.ob_digit -- no slot is read up before
* being stored into.
*/
double fsize_z = (double)digits * log_base_BASE[base] + 1.0;
if (fsize_z > (double)MAX_LONG_DIGITS) {
/* The same exception as in _PyLong_New(). */
PyErr_SetString(PyExc_OverflowError,
"too many digits in integer");
*res = NULL;
return 0;
}
size_z = (Py_ssize_t)fsize_z;
/* Uncomment next line to test exceedingly rare copy code */
/* size_z = 1; */
assert(size_z > 0);
z = _PyLong_New(size_z);
if (z == NULL) {
*res = NULL;
return 0;
}
_PyLong_SetSignAndDigitCount(z, 0, 0);
/* `convwidth` consecutive input digits are treated as a single
* digit in base `convmultmax`.
*/
convwidth = convwidth_base[base];
convmultmax = convmultmax_base[base];
/* Work ;-) */
p = start;
while (p < end) {
if (*p == '_') {
p++;
continue;
}
/* grab up to convwidth digits from the input string */
c = (digit)_PyLong_DigitValue[Py_CHARMASK(*p++)];
for (i = 1; i < convwidth && p != end; ++p) {
if (*p == '_') {
continue;
}
i++;
c = (twodigits)(c * base +
(int)_PyLong_DigitValue[Py_CHARMASK(*p)]);
assert(c < PyLong_BASE);
}
convmult = convmultmax;
/* Calculate the shift only if we couldn't get
* convwidth digits.
*/
if (i != convwidth) {
convmult = base;
for ( ; i > 1; --i) {
convmult *= base;
}
}
/* Multiply z by convmult, and add c. */
pz = z->long_value.ob_digit;
pzstop = pz + _PyLong_DigitCount(z);
for (; pz < pzstop; ++pz) {
c += (twodigits)*pz * convmult;
*pz = (digit)(c & PyLong_MASK);
c >>= PyLong_SHIFT;
}
/* carry off the current end? */
if (c) {
assert(c < PyLong_BASE);
if (_PyLong_DigitCount(z) < size_z) {
*pz = (digit)c;
assert(!_PyLong_IsNegative(z));
_PyLong_SetSignAndDigitCount(z, 1, _PyLong_DigitCount(z) + 1);
}
else {
PyLongObject *tmp;
/* Extremely rare. Get more space. */
assert(_PyLong_DigitCount(z) == size_z);
tmp = _PyLong_New(size_z + 1);
if (tmp == NULL) {
Py_DECREF(z);
*res = NULL;
return 0;
}
memcpy(tmp->long_value.ob_digit,
z->long_value.ob_digit,
sizeof(digit) * size_z);
Py_SETREF(z, tmp);
z->long_value.ob_digit[size_z] = (digit)c;
++size_z;
}
}
}
*res = z;
return 0;
}
/* *str points to the first digit in a string of base `base` digits. base is an
* integer from 2 to 36 inclusive. Here we don't need to worry about prefixes
* like 0x or leading +- signs. The string should be null terminated consisting
* of ASCII digits and separating underscores possibly with trailing whitespace
* but we have to validate all of those points here.
*
* If base is a power of 2 then the complexity is linear in the number of
* characters in the string. Otherwise a quadratic algorithm is used for
* non-binary bases.
*
* Return values:
*
* - Returns -1 on syntax error (exception needs to be set, *res is untouched)
* - Returns 0 and sets *res to NULL for MemoryError, OverflowError, or
* _pylong.int_from_string() errors.
* - Returns 0 and sets *res to an unsigned, unnormalized PyLong (success!).
*
* Afterwards *str is set to point to the first non-digit (which may be *str!).
*/
static int
long_from_string_base(const char **str, int base, PyLongObject **res)
{
const char *start, *end, *p;
char prev = 0;
Py_ssize_t digits = 0;
int is_binary_base = (base & (base - 1)) == 0;
/* Here we do four things:
*
* - Find the `end` of the string.
* - Validate the string.
* - Count the number of `digits` (rather than underscores)