/* 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 PyLong_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 *);

#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(Py_SIZE(v));

	Py_ssize_t i = j;

	while (i > 0 && v->ob_digit[i-1] == 0)

		--i;

	if (i != j)

		Py_SIZE(v) = (Py_SIZE(v) < 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;

	}

	/* coverity[ampersand_in_size] */

	/* XXX(nnorwitz): This can overflow --

           PyObject_NEW_VAR / _PyObject_VAR_SIZE need to detect overflow */

	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 abs_ival;

	unsigned long t;  /* unsigned so >> doesn't propagate sign bit */

	int ndigits = 0;

	int negative = 0;

	if (ival < 0) {

		/* if LONG_MIN == -LONG_MAX-1 (true on most platforms) then

		   ANSI C says that the result of -ival is undefined when ival

		   == LONG_MIN.  Hence the following workaround. */

		abs_ival = (unsigned long)(-1-ival) + 1;

		negative = 1;

	}

	else {

		abs_ival = (unsigned long)ival;

	}

	/* 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 = abs_ival;

	while (t) {

		++ndigits;

		t >>= PyLong_SHIFT;

	}

	v = _PyLong_New(ndigits);

	if (v != NULL) {

		digit *p = v->ob_digit;

		v->ob_size = negative ? -ndigits : ndigits;

		t = abs_ival;

		while (t) {

			*p++ = (digit)(t & PyLong_MASK);

			t >>= PyLong_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 >>= PyLong_SHIFT;

	}

	v = _PyLong_New(ndigits);

	if (v != NULL) {

		digit *p = v->ob_digit;

		Py_SIZE(v) = ndigits;

		while (ival) {

			*p++ = (digit)(ival & PyLong_MASK);

			ival >>= PyLong_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 integer");

		return NULL;

	}

	if (Py_IS_NAN(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 */

	if (expo <= 0)

		return PyLong_FromLong(0L);

	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; ) {

		long bits = (long)frac;

		v->ob_digit[i] = (digit) bits;

		frac = frac - (double)bits;

		frac = ldexp(frac, PyLong_SHIFT);

	}

	if (neg)

		Py_SIZE(v) = -(Py_SIZE(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 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. */

long

PyLong_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 << PyLong_SHIFT) + v->ob_digit[i];

		if ((x >> PyLong_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 << PyLong_SHIFT) + v->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,

			"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 long

PyLong_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 = Py_SIZE(v);

	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 << PyLong_SHIFT) + v->ob_digit[i];

		if ((x >> PyLong_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 long

PyLong_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 << PyLong_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 Py_SIZE(v) == 0 ? 0 : (Py_SIZE(v) < 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(Py_SIZE(v));

	assert(ndigits == 0 || v->ob_digit[ndigits - 1] != 0);

	if (ndigits > 0) {

		digit msd = v->ob_digit[ndigits - 1];

		result = (ndigits - 1) * PyLong_SHIFT;

		if (result / PyLong_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 PyLong_SHIFT

	   bits, so it's the ceiling of the quotient. */

	ndigits = (numsignificantbytes * 8 + PyLong_SHIFT - 1) / PyLong_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,

			   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 < (int)ndigits);

				v->ob_digit[idigit] = (digit)(accum & PyLong_MASK);

				++idigit;

				accum >>= PyLong_SHIFT;

				accumbits -= PyLong_SHIFT;

				assert(accumbits < PyLong_SHIFT);

			}

		}

		assert(accumbits < PyLong_SHIFT);

		if (accumbits) {