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

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

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

#include <ctype.h>

#undef COUNT_ALLOCS

#ifndef NSMALLPOSINTS
#define NSMALLPOSINTS		257
#endif
#ifndef NSMALLNEGINTS
#define NSMALLNEGINTS		5
#endif

#define INT_OPERATIONS

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

#define MPZ(x) (((PyLongObject*)x)->number)

#define SIGN(x) mpz_sgn(MPZ(x))

#define FITS_INT(x) mpz_fits_sint_p(MPZ(x))
#define FITS_UINT(x) mpz_fits_uint_p(MPZ(x))

#define GET_INT(x) mpz_get_si(MPZ(x))
#define GET_UINT(x) mpz_get_ui(MPZ(x))

#define MPZ_ENDIAN(little_endian) ((little_endian)?-1:1)

#if NSMALLNEGINTS + NSMALLPOSINTS > 0
/* Small integers are preallocated in this array so that they
   can be shared.
   The integers that are preallocated are those in the range
   -NSMALLNEGINTS (inclusive) to NSMALLPOSINTS (not inclusive).
*/
static PyLongObject small_ints[NSMALLNEGINTS + NSMALLPOSINTS];
#ifdef COUNT_ALLOCS
int quick_int_allocs, quick_neg_int_allocs;
#endif

static PyObject *
get_small_int(int ival)
{
	PyObject *v = (PyObject*)(small_ints + ival + NSMALLNEGINTS);
	Py_INCREF(v);
#ifdef COUNT_ALLOCS
	if (ival >= 0)
		quick_int_allocs++;
	else
		quick_neg_int_allocs++;
#endif
	return v;
}

#define CHECK_SMALL_INT(ival) \
	if (-NSMALLNEGINTS <= ival && ival < NSMALLPOSINTS) { \
		return get_small_int((int)ival); \
	}

#define CHECK_SMALL_UINT(ival) \
	do if (ival < NSMALLPOSINTS) { \
		return get_small_int((int)ival); \
	} while(0)

static PyLongObject *
maybe_small_long(PyLongObject *v)
{
	int val;
	if (!FITS_INT(v))
		return v;
	val = GET_INT(v);
	if (-NSMALLNEGINTS <= val && val < NSMALLPOSINTS) {
		Py_DECREF(v);
		return (PyLongObject *)get_small_int(val);
	}
	return v;
}
#else
#define CHECK_SMALL_INT(ival)
#define maybe_small_long(val) (val)
#endif

static PyObject* long_neg(PyLongObject *v);
static PyObject* long_invert(PyLongObject *v);
static PyObject* long_long(PyObject *v);

static void
PyLong_FatalMemoryError(void)
{
	Py_FatalError("unable to allocate memory for an integer");
}

static void*
PyLong_Malloc(size_t size)
{
	void *p = PyObject_MALLOC(size);
	if (!p)
		PyLong_FatalMemoryError();
	return p;
}

static void*
PyLong_Realloc(void *ptr, size_t oldsize, size_t newsize)
{
	void *p = PyObject_Realloc(ptr, newsize);
	if (!p)
		PyLong_FatalMemoryError();
	return p;

}

static void
PyLong_Free(void *ptr, size_t size)
{
	PyObject_FREE(ptr);
}

/* Allocate a new long int object with size digits.
   Return NULL and set exception if we run out of memory. */

PyLongObject *
_PyLong_New(void)
{
	PyLongObject *result;
	result = PyObject_MALLOC(sizeof(PyLongObject));
	if (!result) {
		PyErr_NoMemory();
		return NULL;
	}
	PyObject_INIT(result, &PyLong_Type);
	mpz_init (result->number);
	return result;
}

PyObject *
_PyLong_Copy(PyLongObject *src)
{
	PyLongObject *result;
	assert(src != NULL);
	result = _PyLong_New();
	mpz_set(result->number, src->number);
	return (PyObject *)result;
}

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

PyObject *
PyLong_FromLong(long ival)
{
	PyLongObject *v;
	CHECK_SMALL_INT(ival);
	v = _PyLong_New();
	mpz_set_si(v->number, ival);
	return (PyObject *)v;
}

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

PyObject *
PyLong_FromUnsignedLong(unsigned long ival)
{
	PyLongObject *v;
	CHECK_SMALL_UINT(ival);
	v = _PyLong_New();
	mpz_set_ui(v->number, ival);
	return (PyObject *)v;
}

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

PyObject *
PyLong_FromDouble(double dval)
{
	PyLongObject *v;
	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;
	}
	v = _PyLong_New();
	mpz_set_d(v->number, dval);
	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_AsLongAndOverflow(PyObject *vv, int *overflow)
{
	union {
		long number;
		unsigned char bytes[sizeof(long)];
	} result;
	int res;
	int do_decref = 0; /* if nb_int was called */

	*overflow = 0;
	if (vv == NULL) {
		PyErr_BadInternalCall();
		return -1;
	}

	if (!PyLong_Check(vv)) {
		PyNumberMethods *nb;
		if ((nb = vv->ob_type->tp_as_number) == NULL ||
		    nb->nb_int == NULL) {
			PyErr_SetString(PyExc_TypeError, "an integer is required");
			return -1;
		}
		vv = (*nb->nb_int) (vv);
		if (vv == NULL)
			return -1;
		do_decref = 1;
		if (!PyLong_Check(vv)) {
			Py_DECREF(vv);
			PyErr_SetString(PyExc_TypeError,
					"nb_int should return int object");
			return -1;
		}
	}

	res = _PyLong_AsByteArray((PyLongObject*)vv, result.bytes, sizeof(result.bytes), 1, 1);
	if (res != 0) {
		result.number = -1L;
		*overflow = 1;
	}
	if (do_decref) {
		Py_DECREF(vv);
	}
	return result.number;
}

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 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)
{
	union {
		Py_ssize_t number;
		unsigned char bytes[sizeof(Py_ssize_t)];
	} result;
	int res;
	if (vv == NULL || !PyLong_Check(vv)) {
		PyErr_BadInternalCall();
		return -1;
	}
	res = _PyLong_AsByteArray((PyLongObject*)vv, result.bytes, sizeof(result.bytes), 1, 1);
	if (res != 0)
		return -1;
	return result.number;
}

/* 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)
{
	if (vv == NULL || !PyLong_Check(vv)) {
		PyErr_BadInternalCall();
		return (unsigned long) -1;
	}
	if (!FITS_UINT(vv)) {
		PyErr_SetString(PyExc_OverflowError,
			   "can't convert negative value to unsigned int");
		return (unsigned long) -1;
	}
	return GET_UINT(vv);
}

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

size_t
PyLong_AsSize_t(PyObject *vv)
{
	union {
		size_t number;
		unsigned char bytes[sizeof(size_t)];
	} result;
	int res;
	if (vv == NULL || !PyLong_Check(vv)) {
		PyErr_BadInternalCall();
		return (unsigned long) -1;
	}
	res = _PyLong_AsByteArray((PyLongObject*)vv, result.bytes, sizeof(result.bytes), 1, 0);
	if (res != 0)
		return -1;
	return result.number;
}

/* 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. */

static unsigned long
_PyLong_AsUnsignedLongMask(PyLongObject *orig)
{
	PyLongObject* v;
	PyObject* mask;
	unsigned long ival;

	mask = PyLong_FromUnsignedLong(ULONG_MAX);
	v = _PyLong_New();
	mpz_set(MPZ(v), MPZ(orig));
	mpz_and(MPZ(v), MPZ(v), MPZ(mask));
	ival = GET_UINT(v);
	Py_DECREF(mask);
	Py_DECREF(v);
	return ival;
}

unsigned long
PyLong_AsUnsignedLongMask(register PyObject *op)
{
	PyNumberMethods *nb;
	PyLongObject *lo;
	unsigned long val;

	if (op && PyLong_Check(op))
		return _PyLong_AsUnsignedLongMask((PyLongObject *)op);

	if (op == NULL || (nb = op->ob_type->tp_as_number) == NULL ||
	    nb->nb_int == NULL) {
		PyErr_SetString(PyExc_TypeError, "an integer is required");
		return (unsigned long)-1;
	}

	lo = (PyLongObject*) (*nb->nb_int) (op);
	if (lo == NULL)
		return (unsigned long)-1;
	if (PyLong_Check(lo)) {
		val = _PyLong_AsUnsignedLongMask(lo);
		Py_DECREF(lo);
		if (PyErr_Occurred())
			return (unsigned long)-1;
		return val;
	}
	else
	{
		Py_DECREF(lo);
		PyErr_SetString(PyExc_TypeError,
				"nb_int should return int object");
		return (unsigned long)-1;
	}
}

int
_PyLong_Sign(PyObject *vv)
{
	return SIGN(vv);
}

size_t
_PyLong_NumBits(PyObject *vv)
{
	assert(v != NULL);
	assert(PyLong_Check(v));
	if (SIGN(vv) == 0)
		return 0;
	return mpz_sizeinbase(MPZ(vv), 2);
}

PyObject *
_PyLong_FromByteArray(const unsigned char* constbytes, size_t n,
		      int little_endian, int is_signed)
{
	PyLongObject *result;
	int order;
	int neg;
	/* FIXME: don't use the stack! */
	unsigned char bytes[n];

	if (n == 0)
		return PyLong_FromLong(0L);

	result = _PyLong_New();
	if (!result)
		return NULL;

	neg = 0;
	memcpy(bytes, constbytes, n);
	if (is_signed) {
		size_t index;
		if (little_endian)
			index = n-1;
		else
			index = 0;
		if (bytes[index] >= 0x80) {
			size_t i;
			for (i=0; i<n; i++)
				bytes[i] = ~bytes[i];
			neg = 1;
		}
	}

	order = MPZ_ENDIAN(little_endian);
	mpz_import(result->number, n, order, sizeof(bytes[0]), order, 0, bytes);
	if (neg) {
		PyObject* invert = long_invert(result);
		Py_DECREF(result);
		if (!invert)
			return NULL;
		result = (PyLongObject*)invert;
	}
	return (PyObject*)result;
}

int
_PyLong_AsByteArray(PyLongObject* v,
		    unsigned char* bytes, size_t n,
		    int little_endian, int is_signed)
{
	size_t count;
	assert(v != NULL && PyLong_Check(v));
	int order;

	if (SIGN(v) < 0) {
		if (!is_signed) {
			PyErr_SetString(PyExc_TypeError,
				"can't convert negative int to unsigned");
			return -1;
		}
	}

	count = mpz_sizeinbase(MPZ(v), 256);
	if (count > n)
		goto overflow;

	order = MPZ_ENDIAN(little_endian);
	mpz_export(bytes, &count, order, sizeof(bytes[0]), order, 0, v->number);

	if (count != n) {
		size_t padding = n - count;
		if (little_endian) {
			memset(bytes + count, 0, padding);
		} else {
			memmove(bytes + padding, bytes, count);
			memset(bytes, 0, padding);
		}
	}
	if (SIGN(v) < 0) {
		ssize_t i;
		for (i=0; i<n; i++) {
			bytes[i] = ~bytes[i];
		}
		if (little_endian) {
			for (i=0; i<n; i++) {
				if (bytes[i] != 0xff) {
					bytes[i]++;
					break;
				} else {
					bytes[i] = 0;
				}
			}
		} else {
			for (i=n-1; 0<=i; i--) {
				if (bytes[i] != 0xff) {
					bytes[i]++;
					break;
				} else {
					bytes[i] = 0;
				}
			}
		}
	}
	if (is_signed && (count == n)) {
		int s1 = SIGN(v), s2, index;
		if (s1 != 0) {
			if (little_endian)
				index = n-1;
			else
				index = 0;
			if (bytes[index] >= 0x80)
				s2 = -1;
			else
				s2 = 1;
			if (s1 != s2)
				goto overflow;
		}
	}
	return 0;

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

double
_PyLong_AsScaledDouble(PyObject *vv, int *exponent)
{
	double result;
	long long_exponent;

	if (vv == NULL || !PyLong_Check(vv)) {
		PyErr_BadInternalCall();
		return -1;
	}

	result = mpz_get_d_2exp(&long_exponent, MPZ(vv));
	*exponent = long_exponent;
	return result;
}

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

double
PyLong_AsDouble(PyObject *vv)
{
	int e = -1;
	double x;

	if (vv == NULL || !PyLong_Check(vv)) {
		PyErr_BadInternalCall();
		return -1;
	}
	x = _PyLong_AsScaledDouble(vv, &e);
	if (x == -1.0 && PyErr_Occurred())
		return -1.0;
	/* 'e' initialized to -1 to silence gcc-4.0.x, but it should be
	   set correctly after a successful _PyLong_AsScaledDouble() call */
	assert(e >= 0);
	if (e > INT_MAX)
		goto overflow;
	errno = 0;
	x = ldexp(x, e);
	if (Py_OVERFLOWED(x))
		goto overflow;
	return x;

overflow:
	PyErr_SetString(PyExc_OverflowError,
		"Python int too large to convert to C double");
	return -1.0;
}

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

PyObject *
PyLong_FromVoidPtr(void *p)
{
#ifndef HAVE_LONG_LONG
#   error "PyLong_FromVoidPtr: sizeof(void*) > sizeof(long), but no long long"
#endif
#if SIZEOF_LONG_LONG < SIZEOF_VOID_P
#   error "PyLong_FromVoidPtr: sizeof(PY_LONG_LONG) < sizeof(void*)"
#endif
	/* special-case null pointer */
	if (!p)
		return PyLong_FromLong(0);
	return PyLong_FromUnsignedLongLong((unsigned PY_LONG_LONG)(Py_uintptr_t)p);

}

/* 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 (PyLong_Check(vv) && _PyLong_Sign(vv) < 0)
		x = PyLong_AsLong(vv);
	else
		x = PyLong_AsUnsignedLong(vv);
#else

#ifndef HAVE_LONG_LONG
#   error "PyLong_AsVoidPtr: sizeof(void*) > sizeof(long), but no long long"
#endif
#if SIZEOF_LONG_LONG < SIZEOF_VOID_P
#   error "PyLong_AsVoidPtr: sizeof(PY_LONG_LONG) < sizeof(void*)"
#endif
	PY_LONG_LONG x;

	if (PyLong_Check(vv) && _PyLong_Sign(vv) < 0)
		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;
}

#ifdef HAVE_LONG_LONG

/* Initial PY_LONG_LONG support by Chris Herborth (chrish@qnx.com), later
 * rewritten to use the newer PyLong_{As,From}ByteArray API.
 */

#define IS_LITTLE_ENDIAN (int)*(unsigned char*)&one

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

PyObject *
PyLong_FromLongLong(PY_LONG_LONG ival)
{
	union {
		PY_LONG_LONG number;
		unsigned char bytes[sizeof(PY_LONG_LONG)];
	} val;
	CHECK_SMALL_INT(ival);
	val.number = ival;
	return _PyLong_FromByteArray(val.bytes, sizeof(val.bytes), 1, 1);
}

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

PyObject *
PyLong_FromUnsignedLongLong(unsigned PY_LONG_LONG ival)
{
	union {
		unsigned PY_LONG_LONG number;
		unsigned char bytes[sizeof(unsigned PY_LONG_LONG)];
	} val;
	CHECK_SMALL_UINT(ival);
	val.number = ival;
	return _PyLong_FromByteArray(val.bytes, sizeof(val.bytes), 1, 0);
}

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

PyObject *
PyLong_FromSsize_t(Py_ssize_t ival)
{
	union {
		Py_ssize_t number;
		unsigned char bytes[sizeof(Py_ssize_t)];
	} val;
	CHECK_SMALL_INT(ival);
	val.number = ival;
	return _PyLong_FromByteArray(val.bytes, sizeof(val.bytes), 1, 1);
}

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

PyObject *
PyLong_FromSize_t(size_t ival)
{
	union {
		ssize_t number;
		unsigned char bytes[sizeof(ssize_t)];
	} val;
	CHECK_SMALL_UINT(ival);
	val.number = ival;
	return _PyLong_FromByteArray(val.bytes, sizeof(val.bytes), 1, 0);
}

/* Get a C PY_LONG_LONG int from a long int object.
   Return -1 and set an error if overflow occurs. */

static PY_LONG_LONG
_PyLong_AsLongLong(PyObject *vv)
{
	union {
		PY_LONG_LONG number;
		unsigned char bytes[sizeof(PY_LONG_LONG)];
	} result;
	int res;

	res = _PyLong_AsByteArray((PyLongObject*)vv, result.bytes, sizeof(result.bytes), 1, 1);
	if (res != 0)
		return (PY_LONG_LONG)-1;
	return result.number;
}

PY_LONG_LONG
PyLong_AsLongLong(PyObject *vv)
{
	PY_LONG_LONG bytes;

	if (vv == NULL) {
		PyErr_BadInternalCall();
		return -1;
	}
	if (!PyLong_Check(vv)) {
		PyNumberMethods *nb;
		PyObject *io;
		if ((nb = vv->ob_type->tp_as_number) == NULL ||
		    nb->nb_int == NULL) {
			PyErr_SetString(PyExc_TypeError, "an integer is required");
			return -1;
		}
		io = (*nb->nb_int) (vv);
		if (io == NULL)
			return -1;
		if (PyLong_Check(io)) {
			bytes = _PyLong_AsLongLong((PyObject*)io);
			Py_DECREF(io);
			return bytes;
		}
		Py_DECREF(io);
		PyErr_SetString(PyExc_TypeError, "integer conversion failed");
		return -1;
	}

	return _PyLong_AsLongLong((PyObject*)vv);
}

/* Get a C unsigned PY_LONG_LONG int from a long int object.
   Return -1 and set an error if overflow occurs. */

unsigned PY_LONG_LONG
PyLong_AsUnsignedLongLong(PyObject *vv)
{
	union {
		unsigned PY_LONG_LONG number;
		unsigned char bytes[sizeof(unsigned PY_LONG_LONG)];
	} result;
	int res;
	if (vv == NULL || !PyLong_Check(vv)) {
		PyErr_BadInternalCall();
		return (unsigned PY_LONG_LONG)-1;
	}
	res = _PyLong_AsByteArray((PyLongObject*)vv, result.bytes, sizeof(result.bytes), 1, 0);
	if (res != 0)
		return (unsigned PY_LONG_LONG)-1;
	return result.number;
}

static unsigned PY_LONG_LONG
_PyLong_AsUnsignedLongLongMask(PyObject *orig)
{
	PyLongObject* v;
	PyObject* mask;
	unsigned PY_LONG_LONG ival;

	mask = PyLong_FromUnsignedLongLong(ULLONG_MAX);
	v = _PyLong_New();
	mpz_set(MPZ(v), MPZ(orig));
	mpz_and(MPZ(v), MPZ(v), MPZ(mask));
	ival = PyLong_AsUnsignedLongLong((PyObject*)v);
	Py_DECREF(mask);
	Py_DECREF(v);
	return ival;
}

unsigned PY_LONG_LONG
PyLong_AsUnsignedLongLongMask(register PyObject *op)
{
	PyNumberMethods *nb;
	PyLongObject *lo;
	unsigned PY_LONG_LONG val;

	if (op && PyLong_Check(op))
		return _PyLong_AsUnsignedLongLongMask(op);

	if (op == NULL || (nb = op->ob_type->tp_as_number) == NULL ||
	    nb->nb_int == NULL) {
		PyErr_SetString(PyExc_TypeError, "an integer is required");
		return (unsigned PY_LONG_LONG)-1;
	}

	lo = (PyLongObject*) (*nb->nb_int) (op);
	if (lo == NULL)
		return (unsigned PY_LONG_LONG)-1;
	if (PyLong_Check(lo)) {
		val = _PyLong_AsUnsignedLongLongMask((PyObject *)lo);
		Py_DECREF(lo);
		if (PyErr_Occurred())
			return (unsigned PY_LONG_LONG)-1;
		return val;
	}
	else
	{
		Py_DECREF(lo);
		PyErr_SetString(PyExc_TypeError,
				"nb_int should return int object");
		return (unsigned PY_LONG_LONG)-1;
	}
}
#undef IS_LITTLE_ENDIAN

#endif /* HAVE_LONG_LONG */

#define CHECK_BINOP(v,w) \
	if (!PyLong_Check(v) || !PyLong_Check(w)) { \
		Py_INCREF(Py_NotImplemented); \
		return Py_NotImplemented; \
	}

PyObject *
_PyLong_Format(PyObject *aa, int base)
{
	register PyLongObject *a = (PyLongObject *)aa;
	char* c_str, *c_str_ptr;
	size_t len;
	PyObject *str;
	Py_UNICODE *strptr;

	c_str = mpz_get_str(NULL, base, a->number);
	if (!c_str) {
		/* FIXME: use mpz error code */
		PyErr_NoMemory();
		return NULL;
	}
	/* NEED MODIFIABLE STRING, ref=1 */
	len = strlen(c_str);
	if (base == 2 || base == 8 || base == 16)
		len += 2;
	else if (base != 10)
		len += 3;
	str = PyUnicode_FromStringAndSize(NULL, len);
	c_str_ptr = c_str;
	strptr = PyUnicode_AS_UNICODE(str);

	if (*c_str_ptr == '-') {
		*strptr++ = *c_str_ptr++;
	}

	if (base == 16) {
		*strptr++ = '0';
		*strptr++ = 'x';
	}
	else if (base == 8) {
		*strptr++ = '0';
		*strptr++ = 'o';
	}
	else if (base == 2) {
		*strptr++ = '0';
		*strptr++ = 'b';
	}
	else if (base != 10) {
		if (base > 10)
			*strptr++ = '0' + base/10;
		*strptr++ = '0' + base%10;
		*strptr++ = '#';
	}

	for(; *c_str_ptr != '\0'; c_str_ptr++) {
		*strptr++ = *c_str_ptr;
	}
	PyLong_Free(c_str, 0);
	return (PyObject *)str;
}

PyObject *
PyLong_FromString(char *str, char **pend, int base)
{
	PyLongObject *result;
	int sign = 1, error_if_nonzero = 0;
	int ret;
	char *orig_str;

	if ((base != 0 && base < 2) || base > 36) {
		PyErr_SetString(PyExc_ValueError,
				"int() arg 2 must be >= 2 and <= 36");
		return NULL;
	}

	orig_str = str;
	while (*str != '\0' && isspace(Py_CHARMASK(*str)))
		str++;
	if (*str == '+')
		++str;
	else if (*str == '-') {
		++str;
		sign = -1;
	}
	if (base == 0) {
		if (str[0] != '0')
			base = 10;
		else if (str[1] == 'x' || str[1] == 'X')
			base = 16;
		else if (str[1] == 'o' || str[1] == 'O')
			base = 8;
		else if (str[1] == 'b' || str[1] == 'B')
			base = 2;
		else {
			/* "old" (C-style) octal literal, now invalid.
			   it might still be zero though */
			error_if_nonzero = 1;
			base = 10;
		}
	}
	if (str[0] == '0' &&
	    ((base == 16 && (str[1] == 'x' || str[1] == 'X')) ||
	     (base == 8  && (str[1] == 'o' || str[1] == 'O')) ||
	     (base == 2  && (str[1] == 'b' || str[1] == 'B'))))
		str += 2;

	result = _PyLong_New();
	if (!result)
			return NULL;

	ret = mpz_set_str(result->number, str, base);
	if (ret != 0)
	{
		PyObject *strobj;
		Py_ssize_t slen;
		Py_XDECREF(result);
		slen = strlen(orig_str) < 200 ? strlen(orig_str) : 200;
		strobj = PyUnicode_FromStringAndSize(orig_str, slen);
		if (strobj == NULL) {
			return NULL;
		}
		if (error_if_nonzero) {
			/* reset the base to 0, else the exception message
			   doesn't make too much sense */
			base = 0;
		}
		PyErr_Format(PyExc_ValueError,
				"invalid literal for int() with base %d: %R",
				base, strobj);
		Py_DECREF(strobj);
		return NULL;
	}
	if (sign < 0)
		mpz_neg(MPZ(result), MPZ(result));
	result = maybe_small_long(result);
	return (PyObject*)result;
}

PyObject *
PyLong_FromUnicode(Py_UNICODE *u, Py_ssize_t length, int base)
{
	PyObject *result;
	char *buffer = (char *)PyMem_MALLOC(length+1);

	if (buffer == NULL)
		return NULL;

	if (PyUnicode_EncodeDecimal(u, length, buffer, NULL)) {
		PyMem_FREE(buffer);
		return NULL;
	}
	result = PyLong_FromString(buffer, NULL, base);
	PyMem_FREE(buffer);
	return result;
}

/* Methods */

static void
long_dealloc(PyObject *v)
{
	mpz_clear(MPZ(v));
	Py_TYPE(v)->tp_free(v);
}

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

static int
long_compare(PyLongObject *a, PyLongObject *b)
{
	int r = mpz_cmp(a->number, b->number);
	if (r > 0)
		return 1;
	else if (r < 0)
		return -1;
	else
		return 0;
}

static PyObject *
long_richcompare(PyObject *self, PyObject *other, int op)
{
	PyObject *result;
	CHECK_BINOP(self, other);
	result = Py_CmpToRich(op, long_compare((PyLongObject*)self,
					       (PyLongObject*)other));
	return result;
}

static long
long_hash(PyLongObject *v)
{
	long x;
	/* FIXME: Use MSB! */
	x = GET_INT(v);
	if (x == -1)
		x = -2;
	return x;
}

static PyObject *
long_add(PyLongObject *a, PyLongObject *b)
{
	PyLongObject *z;
	CHECK_BINOP(a, b);

#ifdef INT_OPERATIONS
	if (FITS_INT(a) && FITS_INT(b)) {
		int aa = GET_INT(a);
		int bb = GET_INT(b);
		int sum = aa + bb;
		if (((aa < 0) ^ (bb < 0))
		|| ((aa < 0) == (sum < 0))) {
			return PyLong_FromLong(sum);
		}
	}
#endif

	z = _PyLong_New();
	if (!z)
		return NULL;
	mpz_add(z->number, a->number, b->number);
	return (PyObject*) maybe_small_long(z);
}

static PyObject *
long_sub(PyLongObject *a, PyLongObject *b)
{
	PyLongObject *z;
	CHECK_BINOP(a, b);

#ifdef INT_OPERATIONS
	if (FITS_INT(a) && FITS_INT(b)) {
		int aa = GET_INT(a);
		int bb = GET_INT(b);
		int diff = aa - bb;
		if (((aa < 0) == (bb < 0))
		|| ((aa < 0) == (diff < 0))) {
			return PyLong_FromLong(diff);
		}
	}
#endif

	z = _PyLong_New();
	if (!z)
		return NULL;
	mpz_sub(z->number, a->number, b->number);
	return (PyObject*) maybe_small_long(z);
}

static PyObject *
long_mul(PyLongObject *a, PyLongObject *b)
{
	PyLongObject *z;

	CHECK_BINOP(a, b);

#ifdef INT_OPERATIONS
	if (FITS_INT(a) && FITS_INT(b)) {
		int aa = GET_INT(a);
		int bb = GET_INT(b);
		int product;
		if (aa != INT_MIN || (bb == 0) || (bb == 1)) {
			product = aa * bb;
			if (aa == 0 || bb == 0 || (product / bb) == aa) {
				return PyLong_FromLong(product);
			}
		}
	}
#endif

	z = _PyLong_New();
	if (!z)
		return NULL;
	mpz_mul(z->number, a->number, b->number);
	return (PyObject*) maybe_small_long(z);
}

static PyObject *
long_div(PyObject *a, PyObject *b)
{
	PyLongObject *div;
	CHECK_BINOP(a, b);
#ifdef INT_OPERATIONS
	if (FITS_INT(b)) {
		int bb = GET_INT(b);
		if (bb == 0) {
			PyErr_SetString(PyExc_ZeroDivisionError,
					"integer division or modulo by zero");
			return NULL;
		}
		if (FITS_INT(a))
		{
			int aa = GET_INT(a);
			if (aa != INT_MIN || bb != -1) {
				int q = aa / bb;
				if (((aa < 0) != (bb < 0))
				&& (aa % bb != 0))
					q -= 1;
				div = (PyLongObject*)PyLong_FromLong(q);
				return (PyObject*)div;
			}
		}
	}
#endif
	div = _PyLong_New();
	if (!div)
		return NULL;
	mpz_fdiv_q(div->number, MPZ(a), MPZ(b));
	return (PyObject *)div;
}

static PyObject *
long_true_divide(PyObject *a, PyObject *b)
{
	double ad, bd;
	int failed, aexp = -1, bexp = -1;

	CHECK_BINOP(a, b);
	ad = _PyLong_AsScaledDouble((PyObject *)a, &aexp);
	bd = _PyLong_AsScaledDouble((PyObject *)b, &bexp);
	failed = (ad == -1.0 || bd == -1.0) && PyErr_Occurred();
	if (failed)
		return NULL;
	/* 'aexp' and 'bexp' were initialized to -1 to silence gcc-4.0.x,
	   but should really be set correctly after sucessful calls to
	   _PyLong_AsScaledDouble() */
	assert(aexp >= 0 && bexp >= 0);

	if (bd == 0.0) {
		PyErr_SetString(PyExc_ZeroDivisionError,
			"int division or modulo by zero");
		return NULL;
	}

	/* True value is very close to ad/bd * 2**(PyLong_SHIFT*(aexp-bexp)) */
	ad /= bd;	/* overflow/underflow impossible here */
	aexp -= bexp;
	if (aexp > INT_MAX)
		goto overflow;
	else if (aexp < -INT_MAX)
		return PyFloat_FromDouble(0.0);	/* underflow to 0 */
	errno = 0;
	ad = ldexp(ad, aexp);
	if (Py_OVERFLOWED(ad)) /* ignore underflow to 0.0 */
		goto overflow;
	return PyFloat_FromDouble(ad);

overflow:
	PyErr_SetString(PyExc_OverflowError,
		"int/int too large for a float");
	return NULL;
}

static PyObject *
long_mod(PyObject *a, PyObject *b)
{
	PyLongObject *z;
	CHECK_BINOP(a, b);
#ifdef INT_OPERATIONS
	if (FITS_INT(b)) {
		int aa, bb, r;
		bb = GET_INT(b);
		if (bb == 0) {
			PyErr_SetString(PyExc_ZeroDivisionError,
					"integer division or modulo by zero");
			return NULL;
		}
		if (FITS_INT(a))
		{
			aa = GET_INT(a);
			r = aa % bb;
			if (r && (aa < 0) != (bb < 0))
				r += bb;
			z = (PyLongObject*)PyLong_FromLong(r);
			return (PyObject*)z;
		}
	}
#endif
	z = _PyLong_New();
	if (!z)
		return NULL;
	mpz_mod(z->number, MPZ(a), MPZ(b));
	if (mpz_cmp_ui(z->number, 0) != 0
	&& SIGN(b) < 0 && mpz_cmp_si(MPZ(b), -1) != 0) {
		mpz_add(z->number, z->number, MPZ(b));
	}
	return (PyObject *)z;
}

static PyObject *
long_divmod(PyObject *a, PyObject *b)
{
	PyLongObject *div, *mod;
	PyObject *z;

	CHECK_BINOP(a, b);

#ifdef INT_OPERATIONS
	if (FITS_INT(a) && FITS_INT(b)) {
		int aa = GET_INT(a);
		int bb = GET_INT(b);
		if (aa != INT_MIN || bb != -1) {
			int divi = aa / bb;
			int modi = aa % bb;
			if (((aa < 0) != (bb < 0))
			&& (modi != 0)) {
				divi -= 1;
				modi += bb;
			}
			return Py_BuildValue("(ii)", divi, modi);
		}
	}
#endif

	div = _PyLong_New();
	if (!div)
		return NULL;
	mod = _PyLong_New();
	if (!mod) {
		Py_DECREF(div);
		return NULL;
	}
	mpz_fdiv_qr(div->number, mod->number, MPZ(a), MPZ(b));

	z = PyTuple_New(2);
	if (z != NULL) {
		PyTuple_SetItem(z, 0, (PyObject *) div);
		PyTuple_SetItem(z, 1, (PyObject *) mod);
	}
	else {
		Py_DECREF(div);
		Py_DECREF(mod);
	}
	return z;
}

/* pow(v, w, x) */
static PyObject *
long_pow(PyObject *v, PyObject *w, PyObject *x)
{
	PyLongObject *z;
	PyLongObject *c;
	CHECK_BINOP(v, w);
	z = _PyLong_New();
	if (!z)
		return NULL;
	if (PyLong_Check(x)) {
		c = (PyLongObject *)x;
	} else {
		if (x != Py_None) {
			Py_INCREF(Py_NotImplemented);
			return Py_NotImplemented;
		} else {
			c = NULL;
		}
	}

	if (SIGN(w) < 0) {
		if (c) {
			PyErr_SetString(PyExc_TypeError, "pow() 2nd argument "
			    "cannot be negative when 3rd argument specified");
			goto error;
		}

		/* else return a float.  This works because we know
		   that this calls float_pow() which converts its
		   arguments to double. */
		return PyFloat_Type.tp_as_number->nb_power(v, w, x);
	}

	if (c) {
		if (SIGN(c) == 0) {
			PyErr_SetString(PyExc_ValueError,
					"pow() 3rd argument cannot be 0");
			goto error;
		}
		mpz_powm(MPZ(z), MPZ(v), MPZ(w), MPZ(c));
		if (SIGN(c) < 0 && SIGN(z) != 0)
			mpz_add(MPZ(z), MPZ(z), MPZ(c));
	} else {
		int exp;
		if (!FITS_INT(w)) {
			PyErr_SetString(PyExc_OverflowError,
				"exponent doesn't fit in an integer");
			return NULL;
		}
		exp = GET_INT(w);
		mpz_pow_ui(z->number, MPZ(v), exp);
	}
	return (PyObject*) maybe_small_long(z);

error:
	Py_DECREF(z);
	return NULL;
}

static PyObject *
long_invert(PyLongObject *v)
{
	PyLongObject *z;
#ifdef INT_OPERATIONS
	if (FITS_INT(v))
		return PyLong_FromLong(-(GET_INT(v)+1));
#endif
	z = _PyLong_New();
	if (!z)
		return NULL;
	mpz_neg(z->number, v->number);
	mpz_sub_ui(z->number, z->number, 1);
	return (PyObject *)z;
}

static PyObject *
long_neg(PyLongObject *v)
{
	PyLongObject *z;
#ifdef INT_OPERATIONS
	if (FITS_INT(v)) {
		int val = GET_INT(v);
		int neg = -val;
		if (neg != val)
			return PyLong_FromLong(neg);
	}
#endif
	z = _PyLong_New();
	if (!z)
		return NULL;
	mpz_neg(z->number, v->number);
	return (PyObject *)z;
}

static PyObject *
long_abs(PyLongObject *v)
{
	PyLongObject *z;
#ifdef INT_OPERATIONS
	if (FITS_INT(v)) {
		int val = GET_INT(v);
		int aval = ABS(val);
		if (val != aval) {
			return PyLong_FromLong(aval);
		}
	}
#endif
	z = _PyLong_New();
	if (!z)
		return NULL;
	mpz_abs(z->number, v->number);
	return (PyObject *)z;
}

static int
long_bool(PyLongObject *v)
{
	return SIGN(v) != 0;
}

static PyObject *
long_rshift(PyLongObject *a, PyLongObject *b)
{
	PyLongObject *z = NULL;
	long shiftby;

	CHECK_BINOP(a, b);

	if ((mpz_cmp_si(MPZ(a), 0) < 0)) {
		/* Right shifting negative numbers is harder */
		PyLongObject *a1, *a2;
		a1 = (PyLongObject *) long_invert(a);
		if (a1 == NULL)
			goto rshift_error;
		a2 = (PyLongObject *) long_rshift(a1, b);
		Py_DECREF(a1);
		if (a2 == NULL)
			goto rshift_error;
		z = (PyLongObject *) long_invert(a2);
		Py_DECREF(a2);

		z = maybe_small_long(z);
		return (PyObject *) z;
	}

	shiftby = PyLong_AsLong((PyObject *)b);
	if (shiftby == -1L && PyErr_Occurred())
		goto rshift_error;
	if (shiftby < 0) {
		PyErr_SetString(PyExc_ValueError,
				"negative shift count");
		goto rshift_error;
	}

#ifdef INT_OPERATIONS
	if (FITS_INT(a)) {
		int aa = GET_INT(a);
		int shifted;
		if (shiftby < sizeof(int) * 8)
			shifted = aa >> shiftby;
		else
			shifted = 0;
		return PyLong_FromLong(shifted);
	}
#endif

	z = _PyLong_New();
	if (!z)
		return NULL;
	mpz_fdiv_q_2exp(z->number, a->number, shiftby);
	z = maybe_small_long(z);

rshift_error:
	return (PyObject *) z;

}

static PyObject *
long_lshift(PyObject *v, PyObject *w)
{
	/* This version due to Tim Peters */
	PyLongObject *a = (PyLongObject*)v;
	PyLongObject *b = (PyLongObject*)w;
	PyLongObject *z = NULL;
	long shiftby;

	CHECK_BINOP(a, b);

	shiftby = PyLong_AsLong((PyObject *)b);
	if (shiftby == -1L && PyErr_Occurred())
		goto lshift_error;
	if (shiftby < 0) {
		PyErr_SetString(PyExc_ValueError, "negative shift count");
		goto lshift_error;
	}
	if ((long)(int)shiftby != shiftby) {
		PyErr_SetString(PyExc_ValueError,
				"outrageous left shift count");
		goto lshift_error;
	}

#ifdef INT_OPERATIONS
	if ((shiftby < sizeof(int) * 8)
	&& FITS_INT(a)) {
		int aa = GET_INT(a);
		int shifted = aa << shiftby;
		if ((shifted >> shiftby) == aa) {
			return PyLong_FromLong(shifted);
		}
	}
#endif

	z = _PyLong_New();
	if (!z)
	    return NULL;
	mpz_mul_2exp(z->number, a->number, shiftby);
	z = maybe_small_long(z);

lshift_error:
	return (PyObject *) z;
}


/* Bitwise and/xor/or operations */

static PyObject *
long_bitwise(PyLongObject *a,
	     int op,  /* '&', '|', '^' */
	     PyLongObject *b)
{
	PyLongObject *z;

#ifdef INT_OPERATIONS
	if (FITS_INT(a) && FITS_INT(b)) {
		int aa = GET_INT(a);
		int bb = GET_INT(b);
		int r;
		switch (op) {
			case '^':
				r = aa ^ bb;
				break;
			case '&':
				r = aa & bb;
				break;
			case '|':
				r = aa | bb;
				break;
		}
		return PyLong_FromLong(r);
	}
#endif

	z = _PyLong_New();
	if (!z)
			return NULL;

	switch (op) {
	case '^':
		mpz_xor(z->number, MPZ(a), MPZ(b));
		break;
	case '&':
		mpz_and(z->number, MPZ(a), MPZ(b));
		break;
	case '|':
		mpz_ior(z->number, MPZ(a), MPZ(b));
		break;
	}
	return (PyObject*) maybe_small_long(z);
}

static PyObject *
long_and(PyObject *a, PyObject *b)
{
	PyObject *c;
	CHECK_BINOP(a, b);
	c = long_bitwise((PyLongObject*)a, '&', (PyLongObject*)b);
	return c;
}

static PyObject *
long_xor(PyObject *a, PyObject *b)
{
	PyObject *c;
	CHECK_BINOP(a, b);
	c = long_bitwise((PyLongObject*)a, '^', (PyLongObject*)b);
	return c;
}

static PyObject *
long_or(PyObject *a, PyObject *b)
{
	PyObject *c;
	CHECK_BINOP(a, b);
	c = long_bitwise((PyLongObject*)a, '|', (PyLongObject*)b);
	return c;
}

static PyObject *
long_long(PyObject *v)
{
	if (PyLong_CheckExact(v))
		Py_INCREF(v);
	else
		v = _PyLong_Copy((PyLongObject *)v);
	return v;
}

static PyObject *
long_float(PyObject *v)
{
	double result;
	result = PyLong_AsDouble(v);
	if (result == -1.0 && PyErr_Occurred())
		return NULL;
	return PyFloat_FromDouble(result);
}

static PyObject *
long_subtype_new(PyTypeObject *type, PyObject *args, PyObject *kwds);

static PyObject *
long_new(PyTypeObject *type, PyObject *args, PyObject *kwds)
{
	PyObject *x = NULL;
	int base = -909;		     /* unlikely! */
	static char *kwlist[] = {"x", "base", 0};

	if (type != &PyLong_Type)
		return long_subtype_new(type, args, kwds); /* Wimp out */
	if (!PyArg_ParseTupleAndKeywords(args, kwds, "|Oi:int", kwlist,
					 &x, &base))
		return NULL;
	if (x == NULL)
		return PyLong_FromLong(0L);
	if (base == -909)
		return PyNumber_Long(x);
	else if (PyUnicode_Check(x))
		return PyLong_FromUnicode(PyUnicode_AS_UNICODE(x),
					  PyUnicode_GET_SIZE(x),
					  base);
	else if (PyByteArray_Check(x) || PyBytes_Check(x)) {
		/* Since PyLong_FromString doesn't have a length parameter,
		 * check here for possible NULs in the string. */
		char *string;
		int size = Py_SIZE(x);
		if (PyByteArray_Check(x))
			string = PyByteArray_AS_STRING(x);
		else
			string = PyBytes_AS_STRING(x);
		if (strlen(string) != size) {
			/* We only see this if there's a null byte in x,
			   x is a bytes or buffer, *and* a base is given. */
			PyErr_Format(PyExc_ValueError,
			    "invalid literal for int() with base %d: %R",
			    base, x);
			return NULL;
		}
		return PyLong_FromString(string, NULL, base);
	}
	else {
		PyErr_SetString(PyExc_TypeError,
			"int() can't convert non-string with explicit base");
		return NULL;
	}
}

/* Wimpy, slow approach to tp_new calls for subtypes of long:
   first create a regular long from whatever arguments we got,
   then allocate a subtype instance and initialize it from
   the regular long.  The regular long is then thrown away.
*/
static PyObject *
long_subtype_new(PyTypeObject *type, PyObject *args, PyObject *kwds)
{
	PyLongObject *tmp, *newobj;

	assert(PyType_IsSubtype(type, &PyLong_Type));
	tmp = (PyLongObject *)long_new(&PyLong_Type, args, kwds);
	if (tmp == NULL)
		return NULL;
	assert(PyLong_CheckExact(tmp));
	newobj = (PyLongObject *)type->tp_alloc(type, 0);
	if (newobj == NULL) {
		Py_DECREF(tmp);
		return NULL;
	}
	assert(PyLong_Check(newobj));
	mpz_init(newobj->number);
	mpz_set(newobj->number, tmp->number);
	Py_DECREF(tmp);
	return (PyObject *)newobj;
}

static PyObject *
long_getnewargs(PyLongObject *v)
{
	return Py_BuildValue("(N)", _PyLong_Copy(v));
}

static PyObject *
long_getN(PyLongObject *v, void *context) {
	return PyLong_FromLong((Py_intptr_t)context);
}

static PyObject *
long__format__(PyObject *self, PyObject *args)
{
	PyObject *format_spec;

	if (!PyArg_ParseTuple(args, "U:__format__", &format_spec))
		return NULL;
	return _PyLong_FormatAdvanced(self,
				      PyUnicode_AS_UNICODE(format_spec),
				      PyUnicode_GET_SIZE(format_spec));
}


static PyObject *
long_round(PyObject *self, PyObject *args)
{
#define UNDEF_NDIGITS (-0x7fffffff) /* Unlikely ndigits value */
	int ndigits = UNDEF_NDIGITS;
	double x;
	PyObject *res;

	if (!PyArg_ParseTuple(args, "|i", &ndigits))
		return NULL;

	if (ndigits == UNDEF_NDIGITS)
		return long_long(self);

	/* If called with two args, defer to float.__round__(). */
	x = PyLong_AsDouble(self);
	if (x == -1.0 && PyErr_Occurred())
		return NULL;
	self = PyFloat_FromDouble(x);
	if (self == NULL)
		return NULL;
	res = PyObject_CallMethod(self, "__round__", "i", ndigits);
	Py_DECREF(self);
	return res;
#undef UNDEF_NDIGITS
}

static PyObject *
long_numbits(PyObject *self)
{
	size_t bits = _PyLong_NumBits(self);
	return PyLong_FromUnsignedLong(bits);
}

static PyObject *
long_sizeof(PyLongObject *v)
{
	Py_ssize_t res;
	/* FIXME: compute real memory used space in bytes */
	res = sizeof(PyVarObject) /* + abs(Py_SIZE(v))*sizeof(limb_t) */;
	return PyLong_FromSsize_t(res);
}

#if 0
static PyObject *
long_is_finite(PyObject *v)
{
	Py_RETURN_TRUE;
}
#endif

static PyMethodDef long_methods[] = {
	{"conjugate",	(PyCFunction)long_long,	METH_NOARGS,
	 "Returns self, the complex conjugate of any int."},
#if 0
	{"is_finite",	(PyCFunction)long_is_finite,	METH_NOARGS,
	 "Returns always True."},
#endif
	{"__trunc__",	(PyCFunction)long_long,	METH_NOARGS,
         "Truncating an Integral returns itself."},
	{"__floor__",	(PyCFunction)long_long,	METH_NOARGS,
         "Flooring an Integral returns itself."},
	{"__ceil__",	(PyCFunction)long_long,	METH_NOARGS,
         "Ceiling of an Integral returns itself."},
	{"numbits",	(PyCFunction)long_numbits, METH_NOARGS,
         "Number of bits."},
	{"__round__",	(PyCFunction)long_round, METH_VARARGS,
         "Rounding an Integral returns itself.\n"
	 "Rounding with an ndigits arguments defers to float.__round__."},
	{"__getnewargs__",	(PyCFunction)long_getnewargs,	METH_NOARGS},
        {"__format__", (PyCFunction)long__format__, METH_VARARGS},
	{"__sizeof__",	(PyCFunction)long_sizeof, METH_NOARGS,
	 "Returns size in memory, in bytes"},
	{NULL,		NULL}		/* sentinel */
};

static PyGetSetDef long_getset[] = {
    {"real",
     (getter)long_long, (setter)NULL,
     "the real part of a complex number",
     NULL},
    {"imag",
     (getter)long_getN, (setter)NULL,
     "the imaginary part of a complex number",
     (void*)0},
    {"numerator",
     (getter)long_long, (setter)NULL,
     "the numerator of a rational number in lowest terms",
     NULL},
    {"denominator",
     (getter)long_getN, (setter)NULL,
     "the denominator of a rational number in lowest terms",
     (void*)1},
    {NULL}  /* Sentinel */
};

PyDoc_STRVAR(long_doc,
"int(x[, base]) -> integer\n\
\n\
Convert a string or number to an integer, if possible.  A floating\n\
point argument will be truncated towards zero (this does not include a\n\
string representation of a floating point number!)  When converting a\n\
string, use the optional base.  It is an error to supply a base when\n\
converting a non-string.");

static PyNumberMethods long_as_number = {
	(binaryfunc)	long_add,	/*nb_add*/
	(binaryfunc)	long_sub,	/*nb_subtract*/
	(binaryfunc)	long_mul,	/*nb_multiply*/
			long_mod,	/*nb_remainder*/
			long_divmod,	/*nb_divmod*/
			long_pow,	/*nb_power*/
	(unaryfunc) 	long_neg,	/*nb_negative*/
	(unaryfunc) 	long_long,	/*tp_positive*/
	(unaryfunc) 	long_abs,	/*tp_absolute*/
	(inquiry)	long_bool,	/*tp_bool*/
	(unaryfunc)	long_invert,	/*nb_invert*/
			long_lshift,	/*nb_lshift*/
	(binaryfunc)	long_rshift,	/*nb_rshift*/
			long_and,	/*nb_and*/
			long_xor,	/*nb_xor*/
			long_or,	/*nb_or*/
			long_long,	/*nb_int*/
			long_long,	/*nb_long*/
			long_float,	/*nb_float*/
	0,				/* nb_inplace_add */
	0,				/* nb_inplace_subtract */
	0,				/* nb_inplace_multiply */
	0,				/* nb_inplace_remainder */
	0,				/* nb_inplace_power */
	0,				/* nb_inplace_lshift */
	0,				/* nb_inplace_rshift */
	0,				/* nb_inplace_and */
	0,				/* nb_inplace_xor */
	0,				/* nb_inplace_or */
	long_div,			/* nb_floor_divide */
	long_true_divide,		/* nb_true_divide */
	0,				/* nb_inplace_floor_divide */
	0,				/* nb_inplace_true_divide */
	long_long,			/* nb_index */
};

PyTypeObject PyLong_Type = {
	PyVarObject_HEAD_INIT(&PyType_Type, 0)
	"int",					/* tp_name */
	sizeof(PyLongObject),			/* tp_basicsize */
	0,					/* tp_itemsize */
	long_dealloc,				/* tp_dealloc */
	0,					/* tp_print */
	0,					/* tp_getattr */
	0,					/* tp_setattr */
	0,					/* tp_compare */
	long_repr,				/* tp_repr */
	&long_as_number,			/* tp_as_number */
	0,					/* tp_as_sequence */
	0,					/* tp_as_mapping */
	(hashfunc)long_hash,			/* tp_hash */
        0,              			/* tp_call */
        long_repr,				/* tp_str */
	PyObject_GenericGetAttr,		/* tp_getattro */
	0,					/* tp_setattro */
	0,					/* tp_as_buffer */
	Py_TPFLAGS_DEFAULT | Py_TPFLAGS_BASETYPE |
		Py_TPFLAGS_LONG_SUBCLASS,	/* tp_flags */
	long_doc,				/* tp_doc */
	0,					/* tp_traverse */
	0,					/* tp_clear */
	long_richcompare,			/* tp_richcompare */
	0,					/* tp_weaklistoffset */
	0,					/* tp_iter */
	0,					/* tp_iternext */
	long_methods,				/* tp_methods */
	0,					/* tp_members */
	long_getset,				/* tp_getset */
	0,					/* tp_base */
	0,					/* tp_dict */
	0,					/* tp_descr_get */
	0,					/* tp_descr_set */
	0,					/* tp_dictoffset */
	0,					/* tp_init */
	0,					/* tp_alloc */
	long_new,				/* tp_new */
	PyObject_Del,                           /* tp_free */
};

int
_PyLong_Init(void)
{
	PyLongObject *v;
#if NSMALLNEGINTS + NSMALLPOSINTS > 0
	int ival;
#endif
	mp_set_memory_functions(
		PyLong_Malloc,
		PyLong_Realloc,
		PyLong_Free
	);
#if NSMALLNEGINTS + NSMALLPOSINTS > 0
	v = small_ints;
	for (ival = -NSMALLNEGINTS; ival <  NSMALLPOSINTS; ival++, v++) {
			PyObject_INIT(v, &PyLong_Type);
		mpz_init (v->number);
		mpz_set_si(v->number, ival);
	}
#endif
	PyObject_INIT(&_Py_TrueStruct, &PyBool_Type);
	PyObject_INIT(&_Py_FalseStruct, &PyBool_Type);
	mpz_init(_Py_TrueStruct.number);
	mpz_init(_Py_FalseStruct.number);
	mpz_set_si(_Py_TrueStruct.number, 1);
	return 1;
}

void
PyLong_Fini(void)
{
	/* Integers are currently statically allocated. Py_DECREF is not
	   needed, but Python must forget about the reference or multiple
	   reinitializations will fail. */
#if NSMALLNEGINTS + NSMALLPOSINTS > 0
	int i;
	PyLongObject *v = small_ints;
	for (i = 0; i < NSMALLNEGINTS + NSMALLPOSINTS; i++, v++) {
		_Py_DEC_REFTOTAL;
		_Py_ForgetReference((PyObject*)v);
	}
#endif
	mpz_clear(_Py_FalseStruct.number);
	mpz_clear(_Py_TrueStruct.number);
}