longobject.c

/* Long (arbitrary precision) integer object implementation */

/* XXX The functional organization of this file is terrible */

#include "Python.h"
#include "longintrepr.h"

#include <assert.h>
#include <ctype.h>

#define ABS(x) ((x) < 0 ? -(x) : (x))

/* Forward */
static PyLongObject *long_normalize(PyLongObject *);
static PyLongObject *mul1(PyLongObject *, wdigit);
static PyLongObject *muladd1(PyLongObject *, wdigit, wdigit);
static PyLongObject *divrem1(PyLongObject *, wdigit, digit *);
static PyObject *long_format(PyObject *aa, int base, int addL);

static int ticker;	/* XXX Could be shared with ceval? */

#define SIGCHECK(PyTryBlock) \
	if (--ticker < 0) { \
		ticker = 100; \
		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)
{
	int j = ABS(v->ob_size);
	register int 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(int size)
{
	return PyObject_NEW_VAR(PyLongObject, &PyLong_Type, size);
}

/* Create a new long int object from a C long int */

PyObject *
PyLong_FromLong(long ival)
{
	/* Assume a C long fits in at most 5 'digits' */
	/* Works on both 32- and 64-bit machines */
	PyLongObject *v = _PyLong_New(5);
	if (v != NULL) {
		unsigned long t = ival;
		int i;
		if (ival < 0) {
			t = -ival;
			v->ob_size = -(v->ob_size);
  		}
		for (i = 0; i < 5; i++) {
			v->ob_digit[i] = (digit) (t & MASK);
			t >>= SHIFT;
		}
		v = long_normalize(v);
	}
	return (PyObject *)v;
}

/* Create a new long int object from a C unsigned long int */

PyObject *
PyLong_FromUnsignedLong(unsigned long ival)
{
	/* Assume a C long fits in at most 5 'digits' */
	/* Works on both 32- and 64-bit machines */
	PyLongObject *v = _PyLong_New(5);
	if (v != NULL) {
		unsigned long t = ival;
		int i;
		for (i = 0; i < 5; i++) {
			v->ob_digit[i] = (digit) (t & MASK);
			t >>= SHIFT;
		}
		v = long_normalize(v);
	}
	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;
}

/* 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;
	int i, 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 if the sign bit is set we're in
	 * trouble *unless* this is the min negative number.  So,
	 * trouble iff sign bit set && (positive || some bit set other
	 * than the sign bit).
	 */
	if ((long)x < 0 && (sign > 0 || (x << 1) != 0))
		goto overflow;
	return (long)x * sign;

 overflow:
	PyErr_SetString(PyExc_OverflowError,
			"long int too long to convert");
	return -1;
}

/* Get a C 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;
	int i;
	
	if (vv == NULL || !PyLong_Check(vv)) {
		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 long to convert");
			return (unsigned long) -1;
		}
	}
	return x;
}

/* Get a C double from a long int object. */

double
PyLong_AsDouble(PyObject *vv)
{
	register PyLongObject *v;
	double x;
	double multiplier = (double) (1L << SHIFT);
	int i, sign;
	
	if (vv == NULL || !PyLong_Check(vv)) {
		PyErr_BadInternalCall();
		return -1;
	}
	v = (PyLongObject *)vv;
	i = v->ob_size;
	sign = 1;
	x = 0.0;
	if (i < 0) {
		sign = -1;
		i = -(i);
	}
	while (--i >= 0) {
		x = x*multiplier + (double)v->ob_digit[i];
	}
	return x * sign;
}

/* Create a new long (or int) object from a C pointer */

PyObject *
PyLong_FromVoidPtr(void *p)
{
#if SIZEOF_VOID_P == SIZEOF_LONG
	return PyInt_FromLong((long)p);
#else
	/* optimize null pointers */
	if ( p == NULL )
		return PyInt_FromLong(0);

	/* we can assume that HAVE_LONG_LONG is true. if not, then the
	   configuration process should have bailed (having big pointers
	   without long longs seems non-sensical) */
	return PyLong_FromLongLong((LONG_LONG)p);
#endif /* SIZEOF_VOID_P == SIZEOF_LONG */
}

/* Get a C pointer from a long object (or an int object in some cases) */

void *
PyLong_AsVoidPtr(PyObject *vv)
{
	/* This function will allow int or long objects. If vv is neither,
	   then the PyLong_AsLong*() functions will raise the exception:
	   PyExc_SystemError, "bad argument to internal function"
	*/

#if SIZEOF_VOID_P == SIZEOF_LONG
	long x;

	if ( PyInt_Check(vv) )
		x = PyInt_AS_LONG(vv);
	else
		x = PyLong_AsLong(vv);
#else
	/* we can assume that HAVE_LONG_LONG is true. if not, then the
	   configuration process should have bailed (having big pointers
	   without long longs seems non-sensical) */
	LONG_LONG x;

	if ( PyInt_Check(vv) )
		x = PyInt_AS_LONG(vv);
	else
		x = PyLong_AsLongLong(vv);
#endif /* SIZEOF_VOID_P == SIZEOF_LONG */

	if (x == -1 && PyErr_Occurred())
		return NULL;
	return (void *)x;
}

#ifdef HAVE_LONG_LONG
/*
 * LONG_LONG support by Chris Herborth (chrish@qnx.com)
 *
 * For better or worse :-), I tried to follow the coding style already
 * here.
 */

/* Create a new long int object from a C LONG_LONG int */

PyObject *
PyLong_FromLongLong(LONG_LONG ival)
{
#if SIZEOF_LONG_LONG == SIZEOF_LONG
	/* In case the compiler is faking it. */
	return PyLong_FromLong( (long)ival );
#else
	if ((LONG_LONG)LONG_MIN <= ival && ival <= (LONG_LONG)LONG_MAX) {
		return PyLong_FromLong( (long)ival );
	}
	else if (0 <= ival && ival <= (unsigned LONG_LONG)ULONG_MAX) {
		return PyLong_FromUnsignedLong( (unsigned long)ival );
	}
	else {
		/* Assume a C LONG_LONG fits in at most 10 'digits'.
		 * Should be OK if we're assuming long fits in 5.
		 */
		PyLongObject *v = _PyLong_New(10);

		if (v != NULL) {
			unsigned LONG_LONG t = ival;
			int i;
			if (ival < 0) {
				t = -ival;
				v->ob_size = -(v->ob_size);
  			}

			for (i = 0; i < 10; i++) {
				v->ob_digit[i] = (digit) (t & MASK);
				t >>= SHIFT;
			}

			v = long_normalize(v);
		}

		return (PyObject *)v;
	}
#endif
}

/* Create a new long int object from a C unsigned LONG_LONG int */
PyObject *
PyLong_FromUnsignedLongLong(unsigned LONG_LONG ival)
{
#if SIZEOF_LONG_LONG == SIZEOF_LONG
	/* In case the compiler is faking it. */
	return PyLong_FromUnsignedLong( (unsigned long)ival );
#else
	if( ival <= (unsigned LONG_LONG)ULONG_MAX ) {
		return PyLong_FromUnsignedLong( (unsigned long)ival );
	}
	else {
		/* Assume a C long fits in at most 10 'digits'. */
		PyLongObject *v = _PyLong_New(10);

		if (v != NULL) {
			unsigned LONG_LONG t = ival;
			int i;
			for (i = 0; i < 10; i++) {
				v->ob_digit[i] = (digit) (t & MASK);
				t >>= SHIFT;
			}

			v = long_normalize(v);
		}

		return (PyObject *)v;
	}
#endif
}

/* Get a C LONG_LONG int from a long int object.
   Returns -1 and sets an error condition if overflow occurs. */

LONG_LONG
PyLong_AsLongLong(PyObject *vv)
{
#if SIZEOF_LONG_LONG == SIZEOF_LONG
	/* In case the compiler is faking it. */
	return (LONG_LONG)PyLong_AsLong( vv );
#else
	register PyLongObject *v;
	LONG_LONG x, prev;
	int i, 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) {
			PyErr_SetString(PyExc_OverflowError,
				"long int too long to convert");
			return -1;
		}
	}

	return x * sign;
#endif
}

unsigned LONG_LONG
PyLong_AsUnsignedLongLong(PyObject *vv)
{
#if SIZEOF_LONG_LONG == 4
	/* In case the compiler is faking it. */
	return (unsigned LONG_LONG)PyLong_AsUnsignedLong( vv );
#else
	register PyLongObject *v;
	unsigned LONG_LONG x, prev;
	int i;
	
	if (vv == NULL || !PyLong_Check(vv)) {
		PyErr_BadInternalCall();
		return (unsigned LONG_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_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 long to convert");
			return (unsigned LONG_LONG) -1;
		}
	}

	return x;
#endif
}
#endif /* HAVE_LONG_LONG */

/* Multiply by a single digit, ignoring the sign. */

static PyLongObject *
mul1(PyLongObject *a, wdigit n)
{
	return muladd1(a, n, (digit)0);
}

/* Multiply by a single digit and add a single digit, ignoring the sign. */

static PyLongObject *
muladd1(PyLongObject *a, wdigit n, wdigit extra)
{
	int size_a = ABS(a->ob_size);
	PyLongObject *z = _PyLong_New(size_a+1);
	twodigits carry = extra;
	int i;
	
	if (z == NULL)
		return NULL;
	for (i = 0; i < size_a; ++i) {
		carry += (twodigits)a->ob_digit[i] * n;
		z->ob_digit[i] = (digit) (carry & MASK);
		carry >>= SHIFT;
	}
	z->ob_digit[i] = (digit) carry;
	return long_normalize(z);
}

/* Divide a long 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, wdigit n, digit *prem)
{
	int size = ABS(a->ob_size);
	PyLongObject *z;
	int i;
	twodigits rem = 0;
	
	assert(n > 0 && n <= MASK);
	z = _PyLong_New(size);
	if (z == NULL)
		return NULL;
	for (i = size; --i >= 0; ) {
		rem = (rem << SHIFT) + a->ob_digit[i];
		z->ob_digit[i] = (digit) (rem/n);
		rem %= n;
	}
	*prem = (digit) rem;
	return long_normalize(z);
}

/* Convert a long int object to a string, using a given conversion base.
   Return a string object.
   If base is 8 or 16, add the proper prefix '0' or '0x'. */

static PyObject *
long_format(PyObject *aa, int base, int addL)
{
	register PyLongObject *a = (PyLongObject *)aa;
	PyStringObject *str;
	int i;
	int size_a = ABS(a->ob_size);
	char *p;
	int bits;
	char sign = '\0';

	if (a == NULL || !PyLong_Check(a)) {
		PyErr_BadInternalCall();
		return NULL;
	}
	assert(base >= 2 && base <= 36);
	
	/* Compute a rough upper bound for the length of the string */
	i = base;
	bits = 0;
	while (i > 1) {
		++bits;
		i >>= 1;
	}
	i = 5 + (addL ? 1 : 0) + (size_a*SHIFT + bits-1) / bits;
	str = (PyStringObject *) PyString_FromStringAndSize((char *)0, i);
	if (str == NULL)
		return NULL;
	p = PyString_AS_STRING(str) + i;
	*p = '\0';
        if (addL)
                *--p = 'L';
	if (a->ob_size < 0)
		sign = '-';
	
	if (a->ob_size == 0) {
		*--p = '0';
	}
	else if ((base & (base - 1)) == 0) {
		/* JRH: special case for power-of-2 bases */
		twodigits temp = a->ob_digit[0];
		int bitsleft = SHIFT;
		int rem;
		int last = abs(a->ob_size);
		int basebits = 1;
		i = base;
		while ((i >>= 1) > 1)
			++basebits;
		
		i = 0;
		for (;;) {
			while (bitsleft >= basebits) {
				if ((temp == 0) && (i >= last - 1)) break;
				rem = temp & (base - 1);
				if (rem < 10)
					rem += '0';
				else
					rem += 'A' - 10;
				assert(p > PyString_AS_STRING(str));
				*--p = (char) rem;
				bitsleft -= basebits;
				temp >>= basebits;
			}
			if (++i >= last) {
				if (temp == 0) break;
				bitsleft = 99;
				/* loop again to pick up final digits */
			}
			else {
				temp = (a->ob_digit[i] << bitsleft) | temp;
				bitsleft += SHIFT;
			}
		}
	}
	else {
		Py_INCREF(a);
		do {
			digit rem;
			PyLongObject *temp = divrem1(a, (digit)base, &rem);
			if (temp == NULL) {
				Py_DECREF(a);
				Py_DECREF(str);
				return NULL;
			}
			if (rem < 10)
				rem += '0';
			else
				rem += 'A'-10;
			assert(p > PyString_AS_STRING(str));
			*--p = (char) rem;
			Py_DECREF(a);
			a = temp;
			SIGCHECK({
				Py_DECREF(a);
				Py_DECREF(str);
				return NULL;
			})
		} while (ABS(a->ob_size) != 0);
		Py_DECREF(a);
	}

	if (base == 8) {
		if (size_a != 0)
			*--p = '0';
	}
	else if (base == 16) {
		*--p = 'x';
		*--p = '0';
	}
	else if (base != 10) {
		*--p = '#';
		*--p = '0' + base%10;
		if (base > 10)
			*--p = '0' + base/10;
	}
	if (sign)
		*--p = sign;
	if (p != PyString_AS_STRING(str)) {
		char *q = PyString_AS_STRING(str);
		assert(p > q);
		do {
		} while ((*q++ = *p++) != '\0');
		q--;
		_PyString_Resize((PyObject **)&str,
				 (int) (q - PyString_AS_STRING(str)));
	}
	return (PyObject *)str;
}

PyObject *
PyLong_FromString(char *str, char **pend, int base)
{
	int sign = 1;
	char *start, *orig_str = str;
	PyLongObject *z;
	
	if ((base != 0 && base < 2) || base > 36) {
		PyErr_SetString(PyExc_ValueError,
				"invalid base for long literal");
		return NULL;
	}
	while (*str != '\0' && isspace(Py_CHARMASK(*str)))
		str++;
	if (*str == '+')
		++str;
	else if (*str == '-') {
		++str;
		sign = -1;
	}
	while (*str != '\0' && isspace(Py_CHARMASK(*str)))
		str++;
	if (base == 0) {
		if (str[0] != '0')
			base = 10;
		else if (str[1] == 'x' || str[1] == 'X')
			base = 16;
		else
			base = 8;
	}
	if (base == 16 && str[0] == '0' && (str[1] == 'x' || str[1] == 'X'))
		str += 2;
	z = _PyLong_New(0);
	start = str;
	for ( ; z != NULL; ++str) {
		int k = -1;
		PyLongObject *temp;
		
		if (*str <= '9')
			k = *str - '0';
		else if (*str >= 'a')
			k = *str - 'a' + 10;
		else if (*str >= 'A')
			k = *str - 'A' + 10;
		if (k < 0 || k >= base)
			break;
		temp = muladd1(z, (digit)base, (digit)k);
		Py_DECREF(z);
		z = temp;
	}
	if (z == NULL)
		return NULL;
	if (str == start)
		goto onError;
	if (sign < 0 && z != NULL && z->ob_size != 0)
		z->ob_size = -(z->ob_size);
	if (*str == 'L' || *str == 'l')
		str++;
	while (*str && isspace(Py_CHARMASK(*str)))
		str++;
	if (*str != '\0')
		goto onError;
	if (pend)
		*pend = str;
	return (PyObject *) z;

 onError:
	PyErr_Format(PyExc_ValueError, 
		     "invalid literal for long(): %.200s", orig_str);
	Py_XDECREF(z);
	return NULL;
}

PyObject *
PyLong_FromUnicode(Py_UNICODE *u, int length, int base)
{
	char buffer[256];

	if (length >= sizeof(buffer)) {
		PyErr_SetString(PyExc_ValueError,
				"long() literal too large to convert");
		return NULL;
	}
	if (PyUnicode_EncodeDecimal(u, length, buffer, NULL))
		return NULL;

	return PyLong_FromString(buffer, NULL, base);
}

/* forward */
static PyLongObject *x_divrem
	(PyLongObject *, PyLongObject *, PyLongObject **);
static PyObject *long_pos(PyLongObject *);
static int long_divrem(PyLongObject *, PyLongObject *,
	PyLongObject **, PyLongObject **);

/* Long division with remainder, top-level routine */

static int
long_divrem(PyLongObject *a, PyLongObject *b,
	    PyLongObject **pdiv, PyLongObject **prem)
{
	int size_a = ABS(a->ob_size), size_b = ABS(b->ob_size);
	PyLongObject *z;
	
	if (size_b == 0) {
		PyErr_SetString(PyExc_ZeroDivisionError,
				"long division or modulo");
		return -1;
	}
	if (size_a < size_b ||
	    (size_a == size_b &&
	     a->ob_digit[size_a-1] < b->ob_digit[size_b-1])) {
		/* |a| < |b|. */
		*pdiv = _PyLong_New(0);
		Py_INCREF(a);
		*prem = (PyLongObject *) a;
		return 0;
	}
	if (size_b == 1) {
		digit rem = 0;
		z = divrem1(a, b->ob_digit[0], &rem);
		if (z == NULL)
			return -1;
		*prem = (PyLongObject *) PyLong_FromLong((long)rem);
	}
	else {
		z = x_divrem(a, b, prem);
		if (z == NULL)
			return -1;
	}
	/* Set the signs.
	   The quotient z has the sign of a*b;
	   the remainder r has the sign of a,
	   so a = b*z + r. */
	if ((a->ob_size < 0) != (b->ob_size < 0))
		z->ob_size = -(z->ob_size);
	if (a->ob_size < 0 && (*prem)->ob_size != 0)
		(*prem)->ob_size = -((*prem)->ob_size);
	*pdiv = z;
	return 0;
}

/* Unsigned long division with remainder -- the algorithm */

static PyLongObject *
x_divrem(PyLongObject *v1, PyLongObject *w1, PyLongObject **prem)
{
	int size_v = ABS(v1->ob_size), size_w = ABS(w1->ob_size);
	digit d = (digit) ((twodigits)BASE / (w1->ob_digit[size_w-1] + 1));
	PyLongObject *v = mul1(v1, d);
	PyLongObject *w = mul1(w1, d);
	PyLongObject *a;
	int j, k;
	
	if (v == NULL || w == NULL) {
		Py_XDECREF(v);
		Py_XDECREF(w);
		return NULL;
	}
	
	assert(size_v >= size_w && size_w > 1); /* Assert checks by div() */
	assert(v->ob_refcnt == 1); /* Since v will be used as accumulator! */
	assert(size_w == ABS(w->ob_size)); /* That's how d was calculated */
	
	size_v = ABS(v->ob_size);
	a = _PyLong_New(size_v - size_w + 1);
	
	for (j = size_v, k = a->ob_size-1; a != NULL && k >= 0; --j, --k) {
		digit vj = (j >= size_v) ? 0 : v->ob_digit[j];
		twodigits q;
		stwodigits carry = 0;
		int i;
		
		SIGCHECK({
			Py_DECREF(a);
			a = NULL;
			break;
		})
		if (vj == w->ob_digit[size_w-1])
			q = MASK;
		else
			q = (((twodigits)vj << SHIFT) + v->ob_digit[j-1]) /
				w->ob_digit[size_w-1];
		
		while (w->ob_digit[size_w-2]*q >
				((
					((twodigits)vj << SHIFT)
					+ v->ob_digit[j-1]
					- q*w->ob_digit[size_w-1]
								) << SHIFT)
				+ v->ob_digit[j-2])
			--q;
		
		for (i = 0; i < size_w && i+k < size_v; ++i) {
			twodigits z = w->ob_digit[i] * q;
			digit zz = (digit) (z >> SHIFT);
			carry += v->ob_digit[i+k] - z
				+ ((twodigits)zz << SHIFT);
			v->ob_digit[i+k] = carry & MASK;
			carry = Py_ARITHMETIC_RIGHT_SHIFT(BASE_TWODIGITS_TYPE,
							  carry, SHIFT);
			carry -= zz;
		}
		
		if (i+k < size_v) {
			carry += v->ob_digit[i+k];
			v->ob_digit[i+k] = 0;
		}
		
		if (carry == 0)
			a->ob_digit[k] = (digit) q;
		else {
			assert(carry == -1);
			a->ob_digit[k] = (digit) q-1;
			carry = 0;
			for (i = 0; i < size_w && i+k < size_v; ++i) {
				carry += v->ob_digit[i+k] + w->ob_digit[i];
				v->ob_digit[i+k] = carry & MASK;
				carry = Py_ARITHMETIC_RIGHT_SHIFT(
						BASE_TWODIGITS_TYPE,
						carry, SHIFT);
			}
		}
	} /* for j, k */
	
	if (a == NULL)
		*prem = NULL;
	else {
		a = long_normalize(a);
		*prem = divrem1(v, d, &d);
		/* d receives the (unused) remainder */
		if (*prem == NULL) {
			Py_DECREF(a);
			a = NULL;
		}
	}
	Py_DECREF(v);
	Py_DECREF(w);
	return a;
}

/* Methods */

static void
long_dealloc(PyObject *v)
{
	PyObject_DEL(v);
}

static PyObject *
long_repr(PyObject *v)
{
	return long_format(v, 10, 1);
}

static PyObject *
long_str(PyObject *v)
{
	return long_format(v, 10, 0);
}

static int
long_compare(PyLongObject *a, PyLongObject *b)
{
	int sign;
	
	if (a->ob_size != b->ob_size) {
		if (ABS(a->ob_size) == 0 && ABS(b->ob_size) == 0)
			sign = 0;
		else
			sign = a->ob_size - b->ob_size;
	}
	else {
		int i = ABS(a->ob_size);
		while (--i >= 0 && a->ob_digit[i] == b->ob_digit[i])
			;
		if (i < 0)
			sign = 0;
		else {
			sign = (int)a->ob_digit[i] - (int)b->ob_digit[i];
			if (a->ob_size < 0)
				sign = -sign;
		}
	}
	return sign < 0 ? -1 : sign > 0 ? 1 : 0;
}

static long
long_hash(PyLongObject *v)
{
	long x;
	int i, sign;

	/* This is designed so that Python ints and longs with the
	   same value hash to the same value, otherwise comparisons
	   of mapping keys will turn out weird */
	i = v->ob_size;
	sign = 1;
	x = 0;
	if (i < 0) {
		sign = -1;
		i = -(i);
	}
	while (--i >= 0) {
		/* Force a 32-bit circular shift */
		x = ((x << SHIFT) & ~MASK) | ((x >> (32-SHIFT)) & MASK);
		x += v->ob_digit[i];
	}
	x = x * sign;
	if (x == -1)
		x = -2;
	return x;
}


/* Add the absolute values of two long integers. */

static PyLongObject *
x_add(PyLongObject *a, PyLongObject *b)
{
	int size_a = ABS(a->ob_size), size_b = ABS(b->ob_size);
	PyLongObject *z;
	int i;
	digit carry = 0;
	
	/* Ensure a is the larger of the two: */
	if (size_a < size_b) {
		{ PyLongObject *temp = a; a = b; b = temp; }
		{ int size_temp = size_a;
		  size_a = size_b;
		  size_b = size_temp; }
	}
	z = _PyLong_New(size_a+1);
	if (z == NULL)
		return NULL;
	for (i = 0; i < size_b; ++i) {
		carry += a->ob_digit[i] + b->ob_digit[i];
		z->ob_digit[i] = carry & MASK;
		carry >>= SHIFT;
	}
	for (; i < size_a; ++i) {
		carry += a->ob_digit[i];
		z->ob_digit[i] = carry & MASK;
		carry >>= SHIFT;
	}
	z->ob_digit[i] = carry;
	return long_normalize(z);
}

/* Subtract the absolute values of two integers. */

static PyLongObject *
x_sub(PyLongObject *a, PyLongObject *b)