/* Integer object implementation */

#include "Python.h"

#include <ctype.h>

static PyObject *int_int(PyIntObject *v);

long

PyInt_GetMax(void)

{

	return LONG_MAX;	/* To initialize sys.maxint */

}

/* Integers are quite normal objects, to make object handling uniform.

   (Using odd pointers to represent integers would save much space

   but require extra checks for this special case throughout the code.)

   Since a typical Python program spends much of its time allocating

   and deallocating integers, these operations should be very fast.

   Therefore we use a dedicated allocation scheme with a much lower

   overhead (in space and time) than straight malloc(): a simple

   dedicated free list, filled when necessary with memory from malloc().

   block_list is a singly-linked list of all PyIntBlocks ever allocated,

   linked via their next members.  PyIntBlocks are never returned to the

   system before shutdown (PyInt_Fini).

   free_list is a singly-linked list of available PyIntObjects, linked

   via abuse of their ob_type members.

*/

#define BLOCK_SIZE	1000	/* 1K less typical malloc overhead */

#define BHEAD_SIZE	8	/* Enough for a 64-bit pointer */

#define N_INTOBJECTS	((BLOCK_SIZE - BHEAD_SIZE) / sizeof(PyIntObject))

struct _intblock {

	struct _intblock *next;

	PyIntObject objects[N_INTOBJECTS];

};

typedef struct _intblock PyIntBlock;

static PyIntBlock *block_list = NULL;

static PyIntObject *free_list = NULL;

static PyIntObject *

fill_free_list(void)

{

	PyIntObject *p, *q;

	/* Python's object allocator isn't appropriate for large blocks. */

	p = (PyIntObject *) PyMem_MALLOC(sizeof(PyIntBlock));

	if (p == NULL)

		return (PyIntObject *) PyErr_NoMemory();

	((PyIntBlock *)p)->next = block_list;

	block_list = (PyIntBlock *)p;

	/* Link the int objects together, from rear to front, then return

	   the address of the last int object in the block. */

	p = &((PyIntBlock *)p)->objects[0];

	q = p + N_INTOBJECTS;

	while (--q > p)

		Py_TYPE(q) = (struct _typeobject *)(q-1);

	Py_TYPE(q) = NULL;

	return p + N_INTOBJECTS - 1;

}

#ifndef NSMALLPOSINTS

#define NSMALLPOSINTS		257

#endif

#ifndef NSMALLNEGINTS

#define NSMALLNEGINTS		5

#endif

#if NSMALLNEGINTS + NSMALLPOSINTS > 0

/* References to small integers are saved in this array so that they

   can be shared.

   The integers that are saved are those in the range

   -NSMALLNEGINTS (inclusive) to NSMALLPOSINTS (not inclusive).

*/

static PyIntObject *small_ints[NSMALLNEGINTS + NSMALLPOSINTS];

#endif

#ifdef COUNT_ALLOCS

int quick_int_allocs, quick_neg_int_allocs;

#endif

PyObject *

PyInt_FromLong(long ival)

{

	register PyIntObject *v;

#if NSMALLNEGINTS + NSMALLPOSINTS > 0

	if (-NSMALLNEGINTS <= ival && ival < NSMALLPOSINTS) {

		v = small_ints[ival + NSMALLNEGINTS];

		Py_INCREF(v);

#ifdef COUNT_ALLOCS

		if (ival >= 0)

			quick_int_allocs++;

		else

			quick_neg_int_allocs++;

#endif

		return (PyObject *) v;

	}

#endif

	if (free_list == NULL) {

		if ((free_list = fill_free_list()) == NULL)

			return NULL;

	}

	/* Inline PyObject_New */

	v = free_list;

	free_list = (PyIntObject *)Py_TYPE(v);

	PyObject_INIT(v, &PyInt_Type);

	v->ob_ival = ival;

	return (PyObject *) v;

}

PyObject *

PyInt_FromSize_t(size_t ival)

{

	if (ival <= LONG_MAX)

		return PyInt_FromLong((long)ival);

	return _PyLong_FromSize_t(ival);

}

PyObject *

PyInt_FromSsize_t(Py_ssize_t ival)

{

	if (ival >= LONG_MIN && ival <= LONG_MAX)

		return PyInt_FromLong((long)ival);

	return _PyLong_FromSsize_t(ival);

}

static void

int_dealloc(PyIntObject *v)

{

	if (PyInt_CheckExact(v)) {

		Py_TYPE(v) = (struct _typeobject *)free_list;

		free_list = v;

	}

	else

		Py_TYPE(v)->tp_free((PyObject *)v);

}

static void

int_free(PyIntObject *v)

{

	Py_TYPE(v) = (struct _typeobject *)free_list;

	free_list = v;

}

long

PyInt_AsLong(register PyObject *op)

{

	PyNumberMethods *nb;

	PyIntObject *io;

	long val;

	if (op && PyInt_Check(op))

		return PyInt_AS_LONG((PyIntObject*) op);

	if (op == NULL || (nb = Py_TYPE(op)->tp_as_number) == NULL ||

	    nb->nb_int == NULL) {

		PyErr_SetString(PyExc_TypeError, "an integer is required");

		return -1;

	}

	io = (PyIntObject*) (*nb->nb_int) (op);

	if (io == NULL)

		return -1;

	if (!PyInt_Check(io)) {

		if (PyLong_Check(io)) {

			/* got a long? => retry int conversion */

			val = PyLong_AsLong((PyObject *)io);

			Py_DECREF(io);

			if ((val == -1) && PyErr_Occurred())

				return -1;

			return val;

		}

		else

		{

			Py_DECREF(io);

			PyErr_SetString(PyExc_TypeError,

					"nb_int should return int object");

			return -1;

		}

	}

	val = PyInt_AS_LONG(io);

	Py_DECREF(io);

	return val;

}

Py_ssize_t

PyInt_AsSsize_t(register PyObject *op)

{

#if SIZEOF_SIZE_T != SIZEOF_LONG

	PyNumberMethods *nb;

	PyIntObject *io;

	Py_ssize_t val;

#endif

	if (op == NULL) {

		PyErr_SetString(PyExc_TypeError, "an integer is required");

		return -1;

	}

	if (PyInt_Check(op))

		return PyInt_AS_LONG((PyIntObject*) op);

	if (PyLong_Check(op))

		return _PyLong_AsSsize_t(op);

#if SIZEOF_SIZE_T == SIZEOF_LONG

	return PyInt_AsLong(op);

#else

	if ((nb = Py_TYPE(op)->tp_as_number) == NULL ||

	    (nb->nb_int == NULL && nb->nb_long == 0)) {

		PyErr_SetString(PyExc_TypeError, "an integer is required");

		return -1;

	}

	if (nb->nb_long != 0)

		io = (PyIntObject*) (*nb->nb_long) (op);

	else

		io = (PyIntObject*) (*nb->nb_int) (op);

	if (io == NULL)

		return -1;

	if (!PyInt_Check(io)) {

		if (PyLong_Check(io)) {

			/* got a long? => retry int conversion */

			val = _PyLong_AsSsize_t((PyObject *)io);

			Py_DECREF(io);

			if ((val == -1) && PyErr_Occurred())

				return -1;

			return val;

		}

		else

		{

			Py_DECREF(io);

			PyErr_SetString(PyExc_TypeError,

					"nb_int should return int object");

			return -1;

		}

	}

	val = PyInt_AS_LONG(io);

	Py_DECREF(io);

	return val;

#endif

}

unsigned long

PyInt_AsUnsignedLongMask(register PyObject *op)

{

	PyNumberMethods *nb;

	PyIntObject *io;

	unsigned long val;

	if (op && PyInt_Check(op))

		return PyInt_AS_LONG((PyIntObject*) op);

	if (op && PyLong_Check(op))

		return PyLong_AsUnsignedLongMask(op);

	if (op == NULL || (nb = Py_TYPE(op)->tp_as_number) == NULL ||

	    nb->nb_int == NULL) {

		PyErr_SetString(PyExc_TypeError, "an integer is required");

		return (unsigned long)-1;

	}

	io = (PyIntObject*) (*nb->nb_int) (op);

	if (io == NULL)

		return (unsigned long)-1;

	if (!PyInt_Check(io)) {

		if (PyLong_Check(io)) {

			val = PyLong_AsUnsignedLongMask((PyObject *)io);

			Py_DECREF(io);

			if (PyErr_Occurred())

				return (unsigned long)-1;

			return val;

		}

		else

		{

			Py_DECREF(io);

			PyErr_SetString(PyExc_TypeError,

					"nb_int should return int object");

			return (unsigned long)-1;

		}

	}

	val = PyInt_AS_LONG(io);

	Py_DECREF(io);

	return val;

}

#ifdef HAVE_LONG_LONG

unsigned PY_LONG_LONG

PyInt_AsUnsignedLongLongMask(register PyObject *op)

{

	PyNumberMethods *nb;

	PyIntObject *io;

	unsigned PY_LONG_LONG val;

	if (op && PyInt_Check(op))

		return PyInt_AS_LONG((PyIntObject*) op);

	if (op && PyLong_Check(op))

		return PyLong_AsUnsignedLongLongMask(op);

	if (op == NULL || (nb = Py_TYPE(op)->tp_as_number) == NULL ||

	    nb->nb_int == NULL) {

		PyErr_SetString(PyExc_TypeError, "an integer is required");

		return (unsigned PY_LONG_LONG)-1;

	}

	io = (PyIntObject*) (*nb->nb_int) (op);

	if (io == NULL)

		return (unsigned PY_LONG_LONG)-1;

	if (!PyInt_Check(io)) {

		if (PyLong_Check(io)) {

			val = PyLong_AsUnsignedLongLongMask((PyObject *)io);

			Py_DECREF(io);

			if (PyErr_Occurred())

				return (unsigned PY_LONG_LONG)-1;

			return val;

		}

		else

		{

			Py_DECREF(io);

			PyErr_SetString(PyExc_TypeError,

					"nb_int should return int object");

			return (unsigned PY_LONG_LONG)-1;

		}

	}

	val = PyInt_AS_LONG(io);

	Py_DECREF(io);

	return val;

}

#endif

PyObject *

PyInt_FromString(char *s, char **pend, int base)

{

	char *end;

	long x;

	Py_ssize_t slen;

	PyObject *sobj, *srepr;

	if ((base != 0 && base < 2) || base > 36) {

		PyErr_SetString(PyExc_ValueError,

				"int() base must be >= 2 and <= 36");

		return NULL;

	}

	while (*s && isspace(Py_CHARMASK(*s)))

		s++;

	errno = 0;

	if (base == 0 && s[0] == '0') {

		x = (long) PyOS_strtoul(s, &end, base);

		if (x < 0)

			return PyLong_FromString(s, pend, base);

	}

	else

		x = PyOS_strtol(s, &end, base);

	if (end == s || !isalnum(Py_CHARMASK(end[-1])))

		goto bad;

	while (*end && isspace(Py_CHARMASK(*end)))

		end++;

	if (*end != '\0') {

  bad:

		slen = strlen(s) < 200 ? strlen(s) : 200;

		sobj = PyString_FromStringAndSize(s, slen);

		if (sobj == NULL)

			return NULL;

		srepr = PyObject_Repr(sobj);

		Py_DECREF(sobj);

		if (srepr == NULL)

			return NULL;

		PyErr_Format(PyExc_ValueError,

			     "invalid literal for int() with base %d: %s",

			     base, PyString_AS_STRING(srepr));

		Py_DECREF(srepr);

		return NULL;

	}

	else if (errno != 0)

		return PyLong_FromString(s, pend, base);

	if (pend)

		*pend = end;

	return PyInt_FromLong(x);

}

#ifdef Py_USING_UNICODE

PyObject *

PyInt_FromUnicode(Py_UNICODE *s, Py_ssize_t length, int base)

{

	PyObject *result;

	char *buffer = (char *)PyMem_MALLOC(length+1);

	if (buffer == NULL)

		return PyErr_NoMemory();

	if (PyUnicode_EncodeDecimal(s, length, buffer, NULL)) {

		PyMem_FREE(buffer);

		return NULL;

	}

	result = PyInt_FromString(buffer, NULL, base);

	PyMem_FREE(buffer);

	return result;

}

#endif

/* Methods */

/* Integers are seen as the "smallest" of all numeric types and thus

   don't have any knowledge about conversion of other types to

   integers. */

#define CONVERT_TO_LONG(obj, lng)		\

	if (PyInt_Check(obj)) {			\

		lng = PyInt_AS_LONG(obj);	\

	}					\

	else {					\

		Py_INCREF(Py_NotImplemented);	\

		return Py_NotImplemented;	\

	}

/* ARGSUSED */

static int

int_print(PyIntObject *v, FILE *fp, int flags)

     /* flags -- not used but required by interface */

{

	long int_val = v->ob_ival;

	Py_BEGIN_ALLOW_THREADS

	fprintf(fp, "%ld", int_val);

	Py_END_ALLOW_THREADS

	return 0;

}

static PyObject *

int_repr(PyIntObject *v)

{

	return _PyInt_Format(v, 10, 0);

}

static int

int_compare(PyIntObject *v, PyIntObject *w)

{

	register long i = v->ob_ival;

	register long j = w->ob_ival;

	return (i < j) ? -1 : (i > j) ? 1 : 0;

}

static long

int_hash(PyIntObject *v)

{

	/* XXX If this is changed, you also need to change the way

	   Python's long, float and complex types are hashed. */

	long x = v -> ob_ival;

	if (x == -1)

		x = -2;

	return x;

}

static PyObject *

int_add(PyIntObject *v, PyIntObject *w)

{

	register long a, b, x;

	CONVERT_TO_LONG(v, a);

	CONVERT_TO_LONG(w, b);

	x = a + b;

	if ((x^a) >= 0 || (x^b) >= 0)

		return PyInt_FromLong(x);

	return PyLong_Type.tp_as_number->nb_add((PyObject *)v, (PyObject *)w);

}

static PyObject *

int_sub(PyIntObject *v, PyIntObject *w)

{

	register long a, b, x;

	CONVERT_TO_LONG(v, a);

	CONVERT_TO_LONG(w, b);

	x = a - b;

	if ((x^a) >= 0 || (x^~b) >= 0)

		return PyInt_FromLong(x);

	return PyLong_Type.tp_as_number->nb_subtract((PyObject *)v,

						     (PyObject *)w);

}

/*

Integer overflow checking for * is painful:  Python tried a couple ways, but

they didn't work on all platforms, or failed in endcases (a product of

-sys.maxint-1 has been a particular pain).

Here's another way:

The native long product x*y is either exactly right or *way* off, being

just the last n bits of the true product, where n is the number of bits

in a long (the delivered product is the true product plus i*2**n for

some integer i).

The native double product (double)x * (double)y is subject to three

rounding errors:  on a sizeof(long)==8 box, each cast to double can lose

info, and even on a sizeof(long)==4 box, the multiplication can lose info.

But, unlike the native long product, it's not in *range* trouble:  even

if sizeof(long)==32 (256-bit longs), the product easily fits in the

dynamic range of a double.  So the leading 50 (or so) bits of the double

product are correct.

We check these two ways against each other, and declare victory if they're

approximately the same.  Else, because the native long product is the only

one that can lose catastrophic amounts of information, it's the native long

product that must have overflowed.

*/

static PyObject *

int_mul(PyObject *v, PyObject *w)

{

	long a, b;

	long longprod;			/* a*b in native long arithmetic */

	double doubled_longprod;	/* (double)longprod */

	double doubleprod;		/* (double)a * (double)b */

	CONVERT_TO_LONG(v, a);

	CONVERT_TO_LONG(w, b);

	longprod = a * b;

	doubleprod = (double)a * (double)b;

	doubled_longprod = (double)longprod;

	/* Fast path for normal case:  small multiplicands, and no info

	   is lost in either method. */

	if (doubled_longprod == doubleprod)