/* Long (arbitrary precision) integer object implementation */ /* XXX The functional organization of this file is terrible */ #include "Python.h"#include "longintrepr.h" #include <ctype.h> /* For long multiplication, use the O(N**2) school algorithm unless * both operands contain more than KARATSUBA_CUTOFF digits (this * being an internal Python long 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 FIVEARY_CUTOFF digits. * In that case, do 5 bits at a time.  The potential drawback is that * a table of 2**5 intermediate results is computed. */#define FIVEARY_CUTOFF 8 #define ABS(x) ((x) < 0 ? -(x) : (x)) #undef MIN#undef MAX#define MAX(x, y) ((x) < (y) ? (y) : (x))#define MIN(x, y) ((x) > (y) ? (y) : (x)) /* Forward */static PyLongObject *long_normalize(PyLongObject *);static PyLongObject *mul1(PyLongObject *, wdigit);static PyLongObject *muladd1(PyLongObject *, wdigit, wdigit);static PyLongObject *divrem1(PyLongObject *, digit, digit *);static PyObject *long_format(PyObject *aa, int base, int addL); #define SIGCHECK(PyTryBlock) \	if (--_Py_Ticker < 0) { \		_Py_Ticker = _Py_CheckInterval; \		if (PyErr_CheckSignals()) PyTryBlock \	} /* Normalize (remove leading zeros from) a long 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(register PyLongObject *v){	Py_ssize_t j = ABS(v->ob_size);	Py_ssize_t i = j; 	while (i > 0 && v->ob_digit[i-1] == 0)		--i;	if (i != j)		v->ob_size = (v->ob_size < 0) ? -(i) : i;	return v;} /* Allocate a new long int object with size digits.   Return NULL and set exception if we run out of memory. */ PyLongObject *_PyLong_New(Py_ssize_t size){	if (size > PY_SSIZE_T_MAX) {		PyErr_NoMemory();		return NULL;	}	return PyObject_NEW_VAR(PyLongObject, &PyLong_Type, size);} PyObject *_PyLong_Copy(PyLongObject *src){	PyLongObject *result;	Py_ssize_t i; 	assert(src != NULL);	i = src->ob_size;	if (i < 0)		i = -(i);	result = _PyLong_New(i);	if (result != NULL) {		result->ob_size = src->ob_size;		while (--i >= 0)			result->ob_digit[i] = src->ob_digit[i];	}	return (PyObject *)result;} /* Create a new long int object from a C long int */ PyObject *PyLong_FromLong(long ival){	PyLongObject *v;	unsigned long t;  /* unsigned so >> doesn't propagate sign bit */	int ndigits = 0;	int negative = 0; 	if (ival < 0) {		ival = -ival;		negative = 1;	} 	/* Count the number of Python digits.	   We used to pick 5 ("big enough for anything"), but that's a	   waste of time and space given that 5*15 = 75 bits are rarely	   needed. */	t = (unsigned long)ival;	while (t) {		++ndigits;		t >>= SHIFT;	}	v = _PyLong_New(ndigits);	if (v != NULL) {		digit *p = v->ob_digit;		v->ob_size = negative ? -ndigits : ndigits;		t = (unsigned long)ival;		while (t) {			*p++ = (digit)(t & MASK);			t >>= SHIFT;		}	}	return (PyObject *)v;} /* Create a new long int object from a C unsigned long int */ PyObject *PyLong_FromUnsignedLong(unsigned long ival){	PyLongObject *v;	unsigned long t;	int ndigits = 0; 	/* Count the number of Python digits. */	t = (unsigned long)ival;	while (t) {		++ndigits;		t >>= SHIFT;	}	v = _PyLong_New(ndigits);	if (v != NULL) {		digit *p = v->ob_digit;		v->ob_size = ndigits;		while (ival) {			*p++ = (digit)(ival & MASK);			ival >>= SHIFT;		}	}	return (PyObject *)v;} /* Create a new long int object from a C double */ PyObject *PyLong_FromDouble(double dval){	PyLongObject *v;	double frac;	int i, ndig, expo, neg;	neg = 0;	if (Py_IS_INFINITY(dval)) {		PyErr_SetString(PyExc_OverflowError,			"cannot convert float infinity to long");		return NULL;	}	if (dval < 0.0) {		neg = 1;		dval = -dval;	}	frac = frexp(dval, &expo); /* dval = frac*2**expo; 0.0 <= frac < 1.0 */	if (expo <= 0)		return PyLong_FromLong(0L);	ndig = (expo-1) / SHIFT + 1; /* Number of 'digits' in result */	v = _PyLong_New(ndig);	if (v == NULL)		return NULL;	frac = ldexp(frac, (expo-1) % SHIFT + 1);	for (i = ndig; --i >= 0; ) {		long bits = (long)frac;		v->ob_digit[i] = (digit) bits;		frac = frac - (double)bits;		frac = ldexp(frac, SHIFT);	}	if (neg)		v->ob_size = -(v->ob_size);	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 postive 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 a long int object.   Returns -1 and sets an error condition if overflow occurs. */ longPyLong_AsLong(PyObject *vv){	/* This version by Tim Peters */	register PyLongObject *v;	unsigned long x, prev;	Py_ssize_t i;	int sign; 	if (vv == NULL || !PyLong_Check(vv)) {		if (vv != NULL && PyInt_Check(vv))			return PyInt_AsLong(vv);		PyErr_BadInternalCall();		return -1;	}	v = (PyLongObject *)vv;	i = v->ob_size;	sign = 1;	x = 0;	if (i < 0) {		sign = -1;		i = -(i);	}	while (--i >= 0) {		prev = x;		x = (x << SHIFT) + v->ob_digit[i];		if ((x >> SHIFT) != prev)			goto overflow;	}	/* Haven't lost any bits, but casting to long requires extra care	 * (see comment above).         */	if (x <= (unsigned long)LONG_MAX) {		return (long)x * sign;	}	else if (sign < 0 && x == PY_ABS_LONG_MIN) {		return LONG_MIN;	}	/* else overflow */  overflow:	PyErr_SetString(PyExc_OverflowError,			"long int too large to convert to int");	return -1;} /* Get a Py_ssize_t from a long int object.   Returns -1 and sets an error condition if overflow occurs. */ Py_ssize_t_PyLong_AsSsize_t(PyObject *vv) {	register PyLongObject *v;	size_t x, prev;	Py_ssize_t i;	int sign; 	if (vv == NULL || !PyLong_Check(vv)) {		PyErr_BadInternalCall();		return -1;	}	v = (PyLongObject *)vv;	i = v->ob_size;	sign = 1;	x = 0;	if (i < 0) {		sign = -1;		i = -(i);	}	while (--i >= 0) {		prev = x;		x = (x << SHIFT) + v->ob_digit[i];		if ((x >> 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,			"long int too large to convert to int");	return -1;} /* Get a C unsigned long int from a long int object.   Returns -1 and sets an error condition if overflow occurs. */ unsigned longPyLong_AsUnsignedLong(PyObject *vv){	register PyLongObject *v;	unsigned long x, prev;	Py_ssize_t i; 	if (vv == NULL || !PyLong_Check(vv)) {		if (vv != NULL && PyInt_Check(vv)) {			long val = PyInt_AsLong(vv);			if (val < 0) {				PyErr_SetString(PyExc_OverflowError,				"can't convert negative value to unsigned long");				return (unsigned long) -1;			}			return val;		}		PyErr_BadInternalCall();		return (unsigned long) -1;	}	v = (PyLongObject *)vv;	i = v->ob_size;	x = 0;	if (i < 0) {		PyErr_SetString(PyExc_OverflowError,			   "can't convert negative value to unsigned long");		return (unsigned long) -1;	}	while (--i >= 0) {		prev = x;		x = (x << SHIFT) + v->ob_digit[i];		if ((x >> SHIFT) != prev) {			PyErr_SetString(PyExc_OverflowError,				"long int too large to convert");			return (unsigned long) -1;		}	}	return x;} /* Get a C unsigned long int from a long int object, ignoring the high bits.   Returns -1 and sets an error condition if an error occurs. */ unsigned longPyLong_AsUnsignedLongMask(PyObject *vv){	register PyLongObject *v;	unsigned long x;	Py_ssize_t i;	int sign; 	if (vv == NULL || !PyLong_Check(vv)) {		if (vv != NULL && PyInt_Check(vv))			return PyInt_AsUnsignedLongMask(vv);		PyErr_BadInternalCall();		return (unsigned long) -1;	}	v = (PyLongObject *)vv;	i = v->ob_size;	sign = 1;	x = 0;	if (i < 0) {		sign = -1;		i = -i;	}	while (--i >= 0) {		x = (x << SHIFT) + v->ob_digit[i];	}	return x * sign;} int_PyLong_Sign(PyObject *vv){	PyLongObject *v = (PyLongObject *)vv; 	assert(v != NULL);	assert(PyLong_Check(v)); 	return v->ob_size == 0 ? 0 : (v->ob_size < 0 ? -1 : 1);} size_t_PyLong_NumBits(PyObject *vv){	PyLongObject *v = (PyLongObject *)vv;	size_t result = 0;	Py_ssize_t ndigits; 	assert(v != NULL);	assert(PyLong_Check(v));	ndigits = ABS(v->ob_size);	assert(ndigits == 0 || v->ob_digit[ndigits - 1] != 0);	if (ndigits > 0) {		digit msd = v->ob_digit[ndigits - 1]; 		result = (ndigits - 1) * SHIFT;		if (result / SHIFT != (size_t)(ndigits - 1))			goto Overflow;		do {			++result;			if (result == 0)				goto Overflow;			msd >>= 1;		} while (msd);	}	return result; Overflow:	PyErr_SetString(PyExc_OverflowError, "long has too many bits "			"to express in a platform size_t");	return (size_t)-1;} 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 */	size_t ndigits;			/* number of Python long digits */	PyLongObject* v;		/* result */	int idigit = 0;  		/* next free index in v->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 insignficant 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 insignficant = is_signed ? 0xff : 0x00; 		for (i = 0; i < n; ++i, p += pincr) {			if (*p != insignficant)				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 long digits do we need?  We have	   8*numsignificantbytes bits, and each Python long digit has SHIFT	   bits, so it's the ceiling of the quotient. */	ndigits = (numsignificantbytes * 8 + SHIFT - 1) / SHIFT;	if (ndigits > (size_t)INT_MAX)		return PyErr_NoMemory();	v = _PyLong_New((int)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,

Lines 1–500 of 3458. Load more