1 

     2 /* Integer object implementation */

     3 

     4 #include "Python.h"

     5 #include <ctype.h>

     6 

     7 static PyObject *int_int(PyIntObject *v);

     8 

     9 long

    10 PyInt_GetMax(void)

    11 {

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

    13 }

    14 

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

    16    (Using odd pointers to represent integers would save much space

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

    18    Since a typical Python program spends much of its time allocating

    19    and deallocating integers, these operations should be very fast.

    20    Therefore we use a dedicated allocation scheme with a much lower

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

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

    23 

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

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

    26    system before shutdown (PyInt_Fini).

    27 

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

    29    via abuse of their ob_type members.

    30 */

    31 

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

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

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

    35 

    36 struct _intblock {

    37 	struct _intblock *next;

    38 	PyIntObject objects[N_INTOBJECTS];

    39 };

    40 

    41 typedef struct _intblock PyIntBlock;

    42 

    43 static PyIntBlock *block_list = NULL;

    44 static PyIntObject *free_list = NULL;

    45 

    46 static PyIntObject *

    47 fill_free_list(void)

    48 {

    49 	PyIntObject *p, *q;

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

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

    52 	if (p == NULL)

    53 		return (PyIntObject *) PyErr_NoMemory();

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

    55 	block_list = (PyIntBlock *)p;

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

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

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

    59 	q = p + N_INTOBJECTS;

    60 	while (--q > p)

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

    62 	Py_TYPE(q) = NULL;

    63 	return p + N_INTOBJECTS - 1;

    64 }

    65 

    66 #ifndef NSMALLPOSINTS

    67 #define NSMALLPOSINTS		257

    68 #endif

    69 #ifndef NSMALLNEGINTS

    70 #define NSMALLNEGINTS		5

    71 #endif

    72 #if NSMALLNEGINTS + NSMALLPOSINTS > 0

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

    74    can be shared.

    75    The integers that are saved are those in the range

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

    77 */

    78 static PyIntObject *small_ints[NSMALLNEGINTS + NSMALLPOSINTS];

    79 #endif

    80 #ifdef COUNT_ALLOCS

    81 int quick_int_allocs, quick_neg_int_allocs;

    82 #endif

    83 

    84 PyObject *

    85 PyInt_FromLong(long ival)

    86 {

    87 	register PyIntObject *v;

    88 #if NSMALLNEGINTS + NSMALLPOSINTS > 0

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

    90 		v = small_ints[ival + NSMALLNEGINTS];

    91 		Py_INCREF(v);

    92 #ifdef COUNT_ALLOCS

    93 		if (ival >= 0)

    94 			quick_int_allocs++;

    95 		else

    96 			quick_neg_int_allocs++;

    97 #endif

    98 		return (PyObject *) v;

    99 	}

   100 #endif

   101 	if (free_list == NULL) {

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

   103 			return NULL;

   104 	}

   105 	/* Inline PyObject_New */

   106 	v = free_list;

   107 	free_list = (PyIntObject *)Py_TYPE(v);

   108 	PyObject_INIT(v, &PyInt_Type);

   109 	v->ob_ival = ival;

   110 	return (PyObject *) v;

   111 }

   112 

   113 PyObject *

   114 PyInt_FromSize_t(size_t ival)

   115 {

   116 	if (ival <= LONG_MAX)

   117 		return PyInt_FromLong((long)ival);

   118 	return _PyLong_FromSize_t(ival);

   119 }

   120 

   121 PyObject *

   122 PyInt_FromSsize_t(Py_ssize_t ival)

   123 {

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

   125 		return PyInt_FromLong((long)ival);

   126 	return _PyLong_FromSsize_t(ival);

   127 }

   128 

   129 static void

   130 int_dealloc(PyIntObject *v)

   131 {

   132 	if (PyInt_CheckExact(v)) {

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

   134 		free_list = v;

   135 	}

   136 	else

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

   138 }

   139 

   140 static void

   141 int_free(PyIntObject *v)

   142 {

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

   144 	free_list = v;

   145 }

   146 

   147 long

   148 PyInt_AsLong(register PyObject *op)

   149 {

   150 	PyNumberMethods *nb;

   151 	PyIntObject *io;

   152 	long val;

   153 

   154 	if (op && PyInt_Check(op))

   155 		return PyInt_AS_LONG((PyIntObject*) op);

   156 

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

   158 	    nb->nb_int == NULL) {

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

   160 		return -1;

   161 	}

   162 

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

   164 	if (io == NULL)

   165 		return -1;

   166 	if (!PyInt_Check(io)) {

   167 		if (PyLong_Check(io)) {

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

   169 			val = PyLong_AsLong((PyObject *)io);

   170 			Py_DECREF(io);

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

   172 				return -1;

   173 			return val;

   174 		}

   175 		else

   176 		{

   177 			Py_DECREF(io);

   178 			PyErr_SetString(PyExc_TypeError,

   179 					"nb_int should return int object");

   180 			return -1;

   181 		}

   182 	}

   183 

   184 	val = PyInt_AS_LONG(io);

   185 	Py_DECREF(io);

   186 

   187 	return val;

   188 }

   189 

   190 Py_ssize_t

   191 PyInt_AsSsize_t(register PyObject *op)

   192 {

   193 #if SIZEOF_SIZE_T != SIZEOF_LONG

   194 	PyNumberMethods *nb;

   195 	PyIntObject *io;

   196 	Py_ssize_t val;

   197 #endif

   198 

   199 	if (op == NULL) {

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

   201 		return -1;

   202 	}

   203 

   204 	if (PyInt_Check(op))

   205 		return PyInt_AS_LONG((PyIntObject*) op);

   206 	if (PyLong_Check(op))

   207 		return _PyLong_AsSsize_t(op);

   208 #if SIZEOF_SIZE_T == SIZEOF_LONG

   209 	return PyInt_AsLong(op);

   210 #else

   211 

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

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

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

   215 		return -1;

   216 	}

   217 

   218 	if (nb->nb_long != 0)

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

   220 	else

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

   222 	if (io == NULL)

   223 		return -1;

   224 	if (!PyInt_Check(io)) {

   225 		if (PyLong_Check(io)) {

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

   227 			val = _PyLong_AsSsize_t((PyObject *)io);

   228 			Py_DECREF(io);

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

   230 				return -1;

   231 			return val;

   232 		}

   233 		else

   234 		{

   235 			Py_DECREF(io);

   236 			PyErr_SetString(PyExc_TypeError,

   237 					"nb_int should return int object");

   238 			return -1;

   239 		}

   240 	}

   241 

   242 	val = PyInt_AS_LONG(io);

   243 	Py_DECREF(io);

   244 

   245 	return val;

   246 #endif

   247 }

   248 

   249 unsigned long

   250 PyInt_AsUnsignedLongMask(register PyObject *op)

   251 {

   252 	PyNumberMethods *nb;

   253 	PyIntObject *io;

   254 	unsigned long val;

   255 

   256 	if (op && PyInt_Check(op))

   257 		return PyInt_AS_LONG((PyIntObject*) op);

   258 	if (op && PyLong_Check(op))

   259 		return PyLong_AsUnsignedLongMask(op);

   260 

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

   262 	    nb->nb_int == NULL) {

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

   264 		return (unsigned long)-1;

   265 	}

   266 

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

   268 	if (io == NULL)

   269 		return (unsigned long)-1;

   270 	if (!PyInt_Check(io)) {

   271 		if (PyLong_Check(io)) {

   272 			val = PyLong_AsUnsignedLongMask((PyObject *)io);

   273 			Py_DECREF(io);

   274 			if (PyErr_Occurred())

   275 				return (unsigned long)-1;

   276 			return val;

   277 		}

   278 		else

   279 		{

   280 			Py_DECREF(io);

   281 			PyErr_SetString(PyExc_TypeError,

   282 					"nb_int should return int object");

   283 			return (unsigned long)-1;

   284 		}

   285 	}

   286 

   287 	val = PyInt_AS_LONG(io);

   288 	Py_DECREF(io);

   289 

   290 	return val;

   291 }

   292 

   293 #ifdef HAVE_LONG_LONG

   294 unsigned PY_LONG_LONG

   295 PyInt_AsUnsignedLongLongMask(register PyObject *op)

   296 {

   297 	PyNumberMethods *nb;

   298 	PyIntObject *io;

   299 	unsigned PY_LONG_LONG val;

   300 

   301 	if (op && PyInt_Check(op))

   302 		return PyInt_AS_LONG((PyIntObject*) op);

   303 	if (op && PyLong_Check(op))

   304 		return PyLong_AsUnsignedLongLongMask(op);

   305 

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

   307 	    nb->nb_int == NULL) {

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

   309 		return (unsigned PY_LONG_LONG)-1;

   310 	}

   311 

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

   313 	if (io == NULL)

   314 		return (unsigned PY_LONG_LONG)-1;

   315 	if (!PyInt_Check(io)) {

   316 		if (PyLong_Check(io)) {

   317 			val = PyLong_AsUnsignedLongLongMask((PyObject *)io);

   318 			Py_DECREF(io);

   319 			if (PyErr_Occurred())

   320 				return (unsigned PY_LONG_LONG)-1;

   321 			return val;

   322 		}

   323 		else

   324 		{

   325 			Py_DECREF(io);

   326 			PyErr_SetString(PyExc_TypeError,

   327 					"nb_int should return int object");

   328 			return (unsigned PY_LONG_LONG)-1;

   329 		}

   330 	}

   331 

   332 	val = PyInt_AS_LONG(io);

   333 	Py_DECREF(io);

   334 

   335 	return val;

   336 }

   337 #endif

   338 

   339 PyObject *

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

   341 {

   342 	char *end;

   343 	long x;

   344 	Py_ssize_t slen;

   345 	PyObject *sobj, *srepr;

   346 

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

   348 		PyErr_SetString(PyExc_ValueError,

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

   350 		return NULL;

   351 	}

   352 

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

   354 		s++;

   355 	errno = 0;

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

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

   358 		if (x < 0)

   359 			return PyLong_FromString(s, pend, base);

   360 	}

   361 	else

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

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

   364 		goto bad;

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

   366 		end++;

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

   368   bad:

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

   370 		sobj = PyString_FromStringAndSize(s, slen);

   371 		if (sobj == NULL)

   372 			return NULL;

   373 		srepr = PyObject_Repr(sobj);

   374 		Py_DECREF(sobj);

   375 		if (srepr == NULL)

   376 			return NULL;

   377 		PyErr_Format(PyExc_ValueError,

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

   379 			     base, PyString_AS_STRING(srepr));

   380 		Py_DECREF(srepr);

   381 		return NULL;

   382 	}

   383 	else if (errno != 0)

   384 		return PyLong_FromString(s, pend, base);

   385 	if (pend)

   386 		*pend = end;

   387 	return PyInt_FromLong(x);

   388 }

   389 

   390 #ifdef Py_USING_UNICODE

   391 PyObject *

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

   393 {

   394 	PyObject *result;

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

   396 

   397 	if (buffer == NULL)

   398 		return PyErr_NoMemory();

   399 

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

   401 		PyMem_FREE(buffer);

   402 		return NULL;

   403 	}

   404 	result = PyInt_FromString(buffer, NULL, base);

   405 	PyMem_FREE(buffer);

   406 	return result;

   407 }

   408 #endif

   409 

   410 /* Methods */

   411 

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

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

   414    integers. */

   415 

   416 #define CONVERT_TO_LONG(obj, lng)		\

   417 	if (PyInt_Check(obj)) {			\

   418 		lng = PyInt_AS_LONG(obj);	\

   419 	}					\

   420 	else {					\

   421 		Py_INCREF(Py_NotImplemented);	\

   422 		return Py_NotImplemented;	\

   423 	}

   424 

   425 /* ARGSUSED */

   426 static int

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

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

   429 {

   430 	long int_val = v->ob_ival;

   431 	Py_BEGIN_ALLOW_THREADS

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

   433 	Py_END_ALLOW_THREADS

   434 	return 0;

   435 }

   436 

   437 static PyObject *

   438 int_repr(PyIntObject *v)

   439 {

   440 	return _PyInt_Format(v, 10, 0);

   441 }

   442 

   443 static int

   444 int_compare(PyIntObject *v, PyIntObject *w)

   445 {

   446 	register long i = v->ob_ival;

   447 	register long j = w->ob_ival;

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

   449 }

   450 

   451 static long

   452 int_hash(PyIntObject *v)

   453 {

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

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

   456 	long x = v -> ob_ival;

   457 	if (x == -1)

   458 		x = -2;

   459 	return x;

   460 }

   461 

   462 static PyObject *

   463 int_add(PyIntObject *v, PyIntObject *w)

   464 {

   465 	register long a, b, x;

   466 	CONVERT_TO_LONG(v, a);

   467 	CONVERT_TO_LONG(w, b);

   468 	x = a + b;

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

   470 		return PyInt_FromLong(x);

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

   472 }

   473 

   474 static PyObject *

   475 int_sub(PyIntObject *v, PyIntObject *w)

   476 {

   477 	register long a, b, x;

   478 	CONVERT_TO_LONG(v, a);

   479 	CONVERT_TO_LONG(w, b);

   480 	x = a - b;

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

   482 		return PyInt_FromLong(x);

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

   484 						     (PyObject *)w);

   485 }

   486 

   487 /*

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

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

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

   491 

   492 Here's another way:

   493 

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

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

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

   497 some integer i).

   498 

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

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

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

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

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

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

   505 product are correct.

   506 

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

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

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

   510 product that must have overflowed.

   511 */

   512 

   513 static PyObject *

   514 int_mul(PyObject *v, PyObject *w)

   515 {

   516 	long a, b;

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

   518 	double doubled_longprod;	/* (double)longprod */

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

   520 

   521 	CONVERT_TO_LONG(v, a);

   522 	CONVERT_TO_LONG(w, b);

   523 	longprod = a * b;

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

   525 	doubled_longprod = (double)longprod;

   526 

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

   528 	   is lost in either method. */

   529 	if (doubled_longprod == doubleprod)

   530 		return PyInt_FromLong(longprod);

   531 

   532 	/* Somebody somewhere lost info.  Close enough, or way off?  Note

   533 	   that a != 0 and b != 0 (else doubled_longprod == doubleprod == 0).

   534 	   The difference either is or isn't significant compared to the

   535 	   true value (of which doubleprod is a good approximation).

   536 	*/

   537 	{

   538 		const double diff = doubled_longprod - doubleprod;

   539 		const double absdiff = diff >= 0.0 ? diff : -diff;

   540 		const double absprod = doubleprod >= 0.0 ? doubleprod :

   541 							  -doubleprod;

   542 		/* absdiff/absprod <= 1/32 iff

   543 		   32 * absdiff <= absprod -- 5 good bits is "close enough" */

   544 		if (32.0 * absdiff <= absprod)

   545 			return PyInt_FromLong(longprod);

   546 		else

   547 			return PyLong_Type.tp_as_number->nb_multiply(v, w);

   548 	}

   549 }

   550 

   551 /* Integer overflow checking for unary negation: on a 2's-complement

   552  * box, -x overflows iff x is the most negative long.  In this case we

   553  * get -x == x.  However, -x is undefined (by C) if x /is/ the most

   554  * negative long (it's a signed overflow case), and some compilers care.

   555  * So we cast x to unsigned long first.  However, then other compilers

   556  * warn about applying unary minus to an unsigned operand.  Hence the

   557  * weird "0-".

   558  */

   559 #define UNARY_NEG_WOULD_OVERFLOW(x)	\

   560 	((x) < 0 && (unsigned long)(x) == 0-(unsigned long)(x))

   561 

   562 /* Return type of i_divmod */

   563 enum divmod_result {

   564 	DIVMOD_OK,		/* Correct result */

   565 	DIVMOD_OVERFLOW,	/* Overflow, try again using longs */

   566 	DIVMOD_ERROR		/* Exception raised */

   567 };

   568 

   569 static enum divmod_result

   570 i_divmod(register long x, register long y,

   571          long *p_xdivy, long *p_xmody)

   572 {

   573 	long xdivy, xmody;

   574 

   575 	if (y == 0) {

   576 		PyErr_SetString(PyExc_ZeroDivisionError,

   577 				"integer division or modulo by zero");

   578 		return DIVMOD_ERROR;

   579 	}

   580 	/* (-sys.maxint-1)/-1 is the only overflow case. */

   581 	if (y == -1 && UNARY_NEG_WOULD_OVERFLOW(x))

   582 		return DIVMOD_OVERFLOW;

   583 	xdivy = x / y;

   584 	xmody = x - xdivy * y;

   585 	/* If the signs of x and y differ, and the remainder is non-0,

   586 	 * C89 doesn't define whether xdivy is now the floor or the

   587 	 * ceiling of the infinitely precise quotient.  We want the floor,

   588 	 * and we have it iff the remainder's sign matches y's.

   589 	 */

   590 	if (xmody && ((y ^ xmody) < 0) /* i.e. and signs differ */) {

   591 		xmody += y;

   592 		--xdivy;

   593 		assert(xmody && ((y ^ xmody) >= 0));

   594 	}

   595 	*p_xdivy = xdivy;

   596 	*p_xmody = xmody;

   597 	return DIVMOD_OK;

   598 }

   599 

   600 static PyObject *

   601 int_div(PyIntObject *x, PyIntObject *y)

   602 {

   603 	long xi, yi;

   604 	long d, m;

   605 	CONVERT_TO_LONG(x, xi);

   606 	CONVERT_TO_LONG(y, yi);

   607 	switch (i_divmod(xi, yi, &d, &m)) {

   608 	case DIVMOD_OK:

   609 		return PyInt_FromLong(d);

   610 	case DIVMOD_OVERFLOW:

   611 		return PyLong_Type.tp_as_number->nb_divide((PyObject *)x,

   612 							   (PyObject *)y);

   613 	default:

   614 		return NULL;

   615 	}

   616 }

   617 

   618 static PyObject *

   619 int_classic_div(PyIntObject *x, PyIntObject *y)

   620 {

   621 	long xi, yi;

   622 	long d, m;

   623 	CONVERT_TO_LONG(x, xi);

   624 	CONVERT_TO_LONG(y, yi);

   625 	if (Py_DivisionWarningFlag &&

   626 	    PyErr_Warn(PyExc_DeprecationWarning, "classic int division") < 0)

   627 		return NULL;

   628 	switch (i_divmod(xi, yi, &d, &m)) {

   629 	case DIVMOD_OK:

   630 		return PyInt_FromLong(d);

   631 	case DIVMOD_OVERFLOW:

   632 		return PyLong_Type.tp_as_number->nb_divide((PyObject *)x,

   633 							   (PyObject *)y);

   634 	default:

   635 		return NULL;

   636 	}

   637 }

   638 

   639 static PyObject *

   640 int_true_divide(PyObject *v, PyObject *w)

   641 {

   642 	/* If they aren't both ints, give someone else a chance.  In

   643 	   particular, this lets int/long get handled by longs, which

   644 	   underflows to 0 gracefully if the long is too big to convert

   645 	   to float. */

   646 	if (PyInt_Check(v) && PyInt_Check(w))

   647 		return PyFloat_Type.tp_as_number->nb_true_divide(v, w);

   648 	Py_INCREF(Py_NotImplemented);

   649 	return Py_NotImplemented;

   650 }

   651 

   652 static PyObject *

   653 int_mod(PyIntObject *x, PyIntObject *y)

   654 {

   655 	long xi, yi;

   656 	long d, m;

   657 	CONVERT_TO_LONG(x, xi);

   658 	CONVERT_TO_LONG(y, yi);

   659 	switch (i_divmod(xi, yi, &d, &m)) {

   660 	case DIVMOD_OK:

   661 		return PyInt_FromLong(m);

   662 	case DIVMOD_OVERFLOW:

   663 		return PyLong_Type.tp_as_number->nb_remainder((PyObject *)x,

   664 							      (PyObject *)y);

   665 	default:

   666 		return NULL;

   667 	}

   668 }

   669 

   670 static PyObject *

   671 int_divmod(PyIntObject *x, PyIntObject *y)

   672 {

   673 	long xi, yi;

   674 	long d, m;

   675 	CONVERT_TO_LONG(x, xi);

   676 	CONVERT_TO_LONG(y, yi);

   677 	switch (i_divmod(xi, yi, &d, &m)) {

   678 	case DIVMOD_OK:

   679 		return Py_BuildValue("(ll)", d, m);

   680 	case DIVMOD_OVERFLOW:

   681 		return PyLong_Type.tp_as_number->nb_divmod((PyObject *)x,

   682 							   (PyObject *)y);

   683 	default:

   684 		return NULL;

   685 	}

   686 }

   687 

   688 static PyObject *

   689 int_pow(PyIntObject *v, PyIntObject *w, PyIntObject *z)

   690 {

   691 	register long iv, iw, iz=0, ix, temp, prev;

   692 	CONVERT_TO_LONG(v, iv);

   693 	CONVERT_TO_LONG(w, iw);

   694 	if (iw < 0) {

   695 		if ((PyObject *)z != Py_None) {

   696 			PyErr_SetString(PyExc_TypeError, "pow() 2nd argument "

   697 			     "cannot be negative when 3rd argument specified");

   698 			return NULL;

   699 		}

   700 		/* Return a float.  This works because we know that

   701 		   this calls float_pow() which converts its

   702 		   arguments to double. */

   703 		return PyFloat_Type.tp_as_number->nb_power(

   704 			(PyObject *)v, (PyObject *)w, (PyObject *)z);

   705 	}

   706  	if ((PyObject *)z != Py_None) {

   707 		CONVERT_TO_LONG(z, iz);

   708 		if (iz == 0) {

   709 			PyErr_SetString(PyExc_ValueError,

   710 					"pow() 3rd argument cannot be 0");

   711 			return NULL;

   712 		}

   713 	}

   714 	/*

   715 	 * XXX: The original exponentiation code stopped looping

   716 	 * when temp hit zero; this code will continue onwards

   717 	 * unnecessarily, but at least it won't cause any errors.

   718 	 * Hopefully the speed improvement from the fast exponentiation

   719 	 * will compensate for the slight inefficiency.

   720 	 * XXX: Better handling of overflows is desperately needed.

   721 	 */

   722  	temp = iv;

   723 	ix = 1;

   724 	while (iw > 0) {

   725 	 	prev = ix;	/* Save value for overflow check */

   726 	 	if (iw & 1) {

   727 		 	ix = ix*temp;

   728 			if (temp == 0)

   729 				break; /* Avoid ix / 0 */

   730 			if (ix / temp != prev) {

   731 				return PyLong_Type.tp_as_number->nb_power(

   732 					(PyObject *)v,

   733 					(PyObject *)w,

   734 					(PyObject *)z);

   735 			}

   736 		}

   737 	 	iw >>= 1;	/* Shift exponent down by 1 bit */

   738 	        if (iw==0) break;

   739 	 	prev = temp;

   740 	 	temp *= temp;	/* Square the value of temp */

   741 	 	if (prev != 0 && temp / prev != prev) {

   742 			return PyLong_Type.tp_as_number->nb_power(

   743 				(PyObject *)v, (PyObject *)w, (PyObject *)z);

   744 		}

   745 	 	if (iz) {

   746 			/* If we did a multiplication, perform a modulo */

   747 		 	ix = ix % iz;

   748 		 	temp = temp % iz;

   749 		}

   750 	}

   751 	if (iz) {

   752 	 	long div, mod;

   753 		switch (i_divmod(ix, iz, &div, &mod)) {

   754 		case DIVMOD_OK:

   755 			ix = mod;

   756 			break;

   757 		case DIVMOD_OVERFLOW:

   758 			return PyLong_Type.tp_as_number->nb_power(

   759 				(PyObject *)v, (PyObject *)w, (PyObject *)z);

   760 		default:

   761 			return NULL;

   762 		}

   763 	}

   764 	return PyInt_FromLong(ix);

   765 }

   766 

   767 static PyObject *

   768 int_neg(PyIntObject *v)

   769 {

   770 	register long a;

   771 	a = v->ob_ival;

   772         /* check for overflow */

   773 	if (UNARY_NEG_WOULD_OVERFLOW(a)) {

   774 		PyObject *o = PyLong_FromLong(a);

   775 		if (o != NULL) {

   776 			PyObject *result = PyNumber_Negative(o);

   777 			Py_DECREF(o);

   778 			return result;

   779 		}

   780 		return NULL;

   781 	}

   782 	return PyInt_FromLong(-a);

   783 }

   784 

   785 static PyObject *

   786 int_abs(PyIntObject *v)

   787 {

   788 	if (v->ob_ival >= 0)

   789 		return int_int(v);

   790 	else

   791 		return int_neg(v);

   792 }

   793 

   794 static int

   795 int_nonzero(PyIntObject *v)

   796 {

   797 	return v->ob_ival != 0;

   798 }

   799 

   800 static PyObject *

   801 int_invert(PyIntObject *v)

   802 {

   803 	return PyInt_FromLong(~v->ob_ival);

   804 }

   805 

   806 static PyObject *

   807 int_lshift(PyIntObject *v, PyIntObject *w)

   808 {

   809 	long a, b, c;

   810 	PyObject *vv, *ww, *result;

   811 

   812 	CONVERT_TO_LONG(v, a);

   813 	CONVERT_TO_LONG(w, b);

   814 	if (b < 0) {

   815 		PyErr_SetString(PyExc_ValueError, "negative shift count");

   816 		return NULL;

   817 	}

   818 	if (a == 0 || b == 0)

   819 		return int_int(v);

   820 	if (b >= LONG_BIT) {

   821 		vv = PyLong_FromLong(PyInt_AS_LONG(v));

   822 		if (vv == NULL)

   823 			return NULL;

   824 		ww = PyLong_FromLong(PyInt_AS_LONG(w));

   825 		if (ww == NULL) {

   826 			Py_DECREF(vv);

   827 			return NULL;

   828 		}

   829 		result = PyNumber_Lshift(vv, ww);

   830 		Py_DECREF(vv);

   831 		Py_DECREF(ww);

   832 		return result;

   833 	}

   834 	c = a << b;

   835 	if (a != Py_ARITHMETIC_RIGHT_SHIFT(long, c, b)) {

   836 		vv = PyLong_FromLong(PyInt_AS_LONG(v));

   837 		if (vv == NULL)

   838 			return NULL;

   839 		ww = PyLong_FromLong(PyInt_AS_LONG(w));

   840 		if (ww == NULL) {

   841 			Py_DECREF(vv);

   842 			return NULL;

   843 		}

   844 		result = PyNumber_Lshift(vv, ww);

   845 		Py_DECREF(vv);

   846 		Py_DECREF(ww);

   847 		return result;

   848 	}

   849 	return PyInt_FromLong(c);

   850 }

   851 

   852 static PyObject *

   853 int_rshift(PyIntObject *v, PyIntObject *w)

   854 {

   855 	register long a, b;

   856 	CONVERT_TO_LONG(v, a);

   857 	CONVERT_TO_LONG(w, b);

   858 	if (b < 0) {

   859 		PyErr_SetString(PyExc_ValueError, "negative shift count");

   860 		return NULL;

   861 	}

   862 	if (a == 0 || b == 0)

   863 		return int_int(v);

   864 	if (b >= LONG_BIT) {

   865 		if (a < 0)

   866 			a = -1;

   867 		else

   868 			a = 0;

   869 	}

   870 	else {

   871 		a = Py_ARITHMETIC_RIGHT_SHIFT(long, a, b);

   872 	}

   873 	return PyInt_FromLong(a);

   874 }

   875 

   876 static PyObject *

   877 int_and(PyIntObject *v, PyIntObject *w)

   878 {

   879 	register long a, b;

   880 	CONVERT_TO_LONG(v, a);

   881 	CONVERT_TO_LONG(w, b);

   882 	return PyInt_FromLong(a & b);

   883 }

   884 

   885 static PyObject *

   886 int_xor(PyIntObject *v, PyIntObject *w)

   887 {

   888 	register long a, b;

   889 	CONVERT_TO_LONG(v, a);

   890 	CONVERT_TO_LONG(w, b);

   891 	return PyInt_FromLong(a ^ b);

   892 }

   893 

   894 static PyObject *

   895 int_or(PyIntObject *v, PyIntObject *w)

   896 {

   897 	register long a, b;

   898 	CONVERT_TO_LONG(v, a);

   899 	CONVERT_TO_LONG(w, b);

   900 	return PyInt_FromLong(a | b);

   901 }

   902 

   903 static int

   904 int_coerce(PyObject **pv, PyObject **pw)

   905 {

   906 	if (PyInt_Check(*pw)) {

   907 		Py_INCREF(*pv);

   908 		Py_INCREF(*pw);

   909 		return 0;

   910 	}

   911 	return 1; /* Can't do it */

   912 }

   913 

   914 static PyObject *

   915 int_int(PyIntObject *v)

   916 {

   917 	if (PyInt_CheckExact(v))

   918 		Py_INCREF(v);

   919 	else

   920 		v = (PyIntObject *)PyInt_FromLong(v->ob_ival);

   921 	return (PyObject *)v;

   922 }

   923 

   924 static PyObject *

   925 int_long(PyIntObject *v)

   926 {

   927 	return PyLong_FromLong((v -> ob_ival));

   928 }

   929 

   930 static PyObject *

   931 int_float(PyIntObject *v)

   932 {

   933 	return PyFloat_FromDouble((double)(v -> ob_ival));

   934 }

   935 

   936 static PyObject *

   937 int_oct(PyIntObject *v)

   938 {

   939 	return _PyInt_Format(v, 8, 0);

   940 }

   941 

   942 static PyObject *

   943 int_hex(PyIntObject *v)

   944 {

   945 	return _PyInt_Format(v, 16, 0);

   946 }

   947 

   948 static PyObject *

   949 int_subtype_new(PyTypeObject *type, PyObject *args, PyObject *kwds);

   950 

   951 static PyObject *

   952 int_new(PyTypeObject *type, PyObject *args, PyObject *kwds)

   953 {

   954 	PyObject *x = NULL;

   955 	int base = -909;

   956 	static char *kwlist[] = {"x", "base", 0};

   957 

   958 	if (type != &PyInt_Type)

   959 		return int_subtype_new(type, args, kwds); /* Wimp out */

   960 	if (!PyArg_ParseTupleAndKeywords(args, kwds, "|Oi:int", kwlist,

   961 					 &x, &base))

   962 		return NULL;

   963 	if (x == NULL)

   964 		return PyInt_FromLong(0L);

   965 	if (base == -909)

   966 		return PyNumber_Int(x);

   967 	if (PyString_Check(x)) {

   968 		/* Since PyInt_FromString doesn't have a length parameter,

   969 		 * check here for possible NULs in the string. */

   970 		char *string = PyString_AS_STRING(x);

   971 		if (strlen(string) != PyString_Size(x)) {

   972 			/* create a repr() of the input string,

   973 			 * just like PyInt_FromString does */

   974 			PyObject *srepr;

   975 			srepr = PyObject_Repr(x);

   976 			if (srepr == NULL)

   977 				return NULL;

   978 			PyErr_Format(PyExc_ValueError,

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

   980 			     base, PyString_AS_STRING(srepr));

   981 			Py_DECREF(srepr);

   982 			return NULL;

   983 		}

   984 		return PyInt_FromString(string, NULL, base);

   985 	}

   986 #ifdef Py_USING_UNICODE

   987 	if (PyUnicode_Check(x))

   988 		return PyInt_FromUnicode(PyUnicode_AS_UNICODE(x),

   989 					 PyUnicode_GET_SIZE(x),

   990 					 base);

   991 #endif

   992 	PyErr_SetString(PyExc_TypeError,

   993 			"int() can't convert non-string with explicit base");

   994 	return NULL;

   995 }

   996 

   997 /* Wimpy, slow approach to tp_new calls for subtypes of int:

   998    first create a regular int from whatever arguments we got,

   999    then allocate a subtype instance and initialize its ob_ival

  1000    from the regular int.  The regular int is then thrown away.

  1001 */

  1002 static PyObject *

  1003 int_subtype_new(PyTypeObject *type, PyObject *args, PyObject *kwds)

  1004 {

  1005 	PyObject *tmp, *newobj;

  1006 	long ival;

  1007 

  1008 	assert(PyType_IsSubtype(type, &PyInt_Type));

  1009 	tmp = int_new(&PyInt_Type, args, kwds);

  1010 	if (tmp == NULL)

  1011 		return NULL;

  1012 	if (!PyInt_Check(tmp)) {

  1013 		ival = PyLong_AsLong(tmp);

  1014 		if (ival == -1 && PyErr_Occurred()) {

  1015 			Py_DECREF(tmp);

  1016 			return NULL;

  1017 		}

  1018 	} else {

  1019 		ival = ((PyIntObject *)tmp)->ob_ival;

  1020 	}

  1021 

  1022 	newobj = type->tp_alloc(type, 0);

  1023 	if (newobj == NULL) {

  1024 		Py_DECREF(tmp);

  1025 		return NULL;

  1026 	}

  1027 	((PyIntObject *)newobj)->ob_ival = ival;

  1028 	Py_DECREF(tmp);

  1029 	return newobj;

  1030 }

  1031 

  1032 static PyObject *

  1033 int_getnewargs(PyIntObject *v)

  1034 {

  1035 	return Py_BuildValue("(l)", v->ob_ival);

  1036 }

  1037 

  1038 static PyObject *

  1039 int_getN(PyIntObject *v, void *context) {

  1040 	return PyInt_FromLong((Py_intptr_t)context);

  1041 }

  1042 

  1043 /* Convert an integer to the given base.  Returns a string.

  1044    If base is 2, 8 or 16, add the proper prefix '0b', '0o' or '0x'.

  1045    If newstyle is zero, then use the pre-2.6 behavior of octal having

  1046    a leading "0" */

  1047 PyAPI_FUNC(PyObject*)

  1048 _PyInt_Format(PyIntObject *v, int base, int newstyle)

  1049 {

  1050 	/* There are no doubt many, many ways to optimize this, using code

  1051 	   similar to _PyLong_Format */

  1052 	long n = v->ob_ival;

  1053 	int  negative = n < 0;

  1054 	int is_zero = n == 0;

  1055 

  1056 	/* For the reasoning behind this size, see

  1057 	   http://c-faq.com/misc/hexio.html. Then, add a few bytes for

  1058 	   the possible sign and prefix "0[box]" */

  1059 	char buf[sizeof(n)*CHAR_BIT+6];

  1060 

  1061 	/* Start by pointing to the end of the buffer.  We fill in from

  1062 	   the back forward. */

  1063 	char* p = &buf[sizeof(buf)];

  1064 

  1065 	assert(base >= 2 && base <= 36);

  1066 

  1067 	do {

  1068 		/* I'd use i_divmod, except it doesn't produce the results

  1069 		   I want when n is negative.  So just duplicate the salient

  1070 		   part here. */

  1071 		long div = n / base;

  1072 		long mod = n - div * base;

  1073 

  1074 		/* convert abs(mod) to the right character in [0-9, a-z] */

  1075 		char cdigit = (char)(mod < 0 ? -mod : mod);

  1076 		cdigit += (cdigit < 10) ? '0' : 'a'-10;

  1077 		*--p = cdigit;

  1078 

  1079 		n = div;

  1080 	} while(n);

  1081 

  1082 	if (base == 2) {

  1083 		*--p = 'b';

  1084 		*--p = '0';

  1085 	}

  1086 	else if (base == 8) {

  1087 		if (newstyle) {

  1088 			*--p = 'o';

  1089 			*--p = '0';

  1090 		}

  1091 		else

  1092 			if (!is_zero)

  1093 				*--p = '0';

  1094 	}

  1095 	else if (base == 16) {

  1096 		*--p = 'x';

  1097 		*--p = '0';

  1098 	}

  1099 	else if (base != 10) {

  1100 		*--p = '#';

  1101 		*--p = '0' + base%10;

  1102 		if (base > 10)

  1103 			*--p = '0' + base/10;

  1104 	}

  1105 	if (negative)

  1106 		*--p = '-';

  1107 

  1108 	return PyString_FromStringAndSize(p, &buf[sizeof(buf)] - p);

  1109 }

  1110 

  1111 static PyObject *

  1112 int__format__(PyObject *self, PyObject *args)

  1113 {

  1114 	PyObject *format_spec;

  1115 

  1116 	if (!PyArg_ParseTuple(args, "O:__format__", &format_spec))

  1117 		return NULL;

  1118 	if (PyBytes_Check(format_spec))

  1119 		return _PyInt_FormatAdvanced(self,

  1120 					     PyBytes_AS_STRING(format_spec),

  1121 					     PyBytes_GET_SIZE(format_spec));

  1122 	if (PyUnicode_Check(format_spec)) {

  1123 		/* Convert format_spec to a str */

  1124 		PyObject *result;

  1125 		PyObject *str_spec = PyObject_Str(format_spec);

  1126 

  1127 		if (str_spec == NULL)

  1128 			return NULL;

  1129 

  1130 		result = _PyInt_FormatAdvanced(self,

  1131 					       PyBytes_AS_STRING(str_spec),

  1132 					       PyBytes_GET_SIZE(str_spec));

  1133 

  1134 		Py_DECREF(str_spec);

  1135 		return result;