1
2 /* Integer object implementation */
3
4 #include "Python.h"
5 #include <ctype.h>
6 #include <float.h>
7
8 static PyObject *int_int(PyIntObject *v);
9
10 long
PyInt_GetMax(void)11 PyInt_GetMax(void)
12 {
13 return LONG_MAX; /* To initialize sys.maxint */
14 }
15
16 /* Integers are quite normal objects, to make object handling uniform.
17 (Using odd pointers to represent integers would save much space
18 but require extra checks for this special case throughout the code.)
19 Since a typical Python program spends much of its time allocating
20 and deallocating integers, these operations should be very fast.
21 Therefore we use a dedicated allocation scheme with a much lower
22 overhead (in space and time) than straight malloc(): a simple
23 dedicated free list, filled when necessary with memory from malloc().
24
25 block_list is a singly-linked list of all PyIntBlocks ever allocated,
26 linked via their next members. PyIntBlocks are never returned to the
27 system before shutdown (PyInt_Fini).
28
29 free_list is a singly-linked list of available PyIntObjects, linked
30 via abuse of their ob_type members.
31 */
32
33 #define BLOCK_SIZE 1000 /* 1K less typical malloc overhead */
34 #define BHEAD_SIZE 8 /* Enough for a 64-bit pointer */
35 #define N_INTOBJECTS ((BLOCK_SIZE - BHEAD_SIZE) / sizeof(PyIntObject))
36
37 struct _intblock {
38 struct _intblock *next;
39 PyIntObject objects[N_INTOBJECTS];
40 };
41
42 typedef struct _intblock PyIntBlock;
43
44 static PyIntBlock *block_list = NULL;
45 static PyIntObject *free_list = NULL;
46
47 static PyIntObject *
fill_free_list(void)48 fill_free_list(void)
49 {
50 PyIntObject *p, *q;
51 /* Python's object allocator isn't appropriate for large blocks. */
52 p = (PyIntObject *) PyMem_MALLOC(sizeof(PyIntBlock));
53 if (p == NULL)
54 return (PyIntObject *) PyErr_NoMemory();
55 ((PyIntBlock *)p)->next = block_list;
56 block_list = (PyIntBlock *)p;
57 /* Link the int objects together, from rear to front, then return
58 the address of the last int object in the block. */
59 p = &((PyIntBlock *)p)->objects[0];
60 q = p + N_INTOBJECTS;
61 while (--q > p)
62 Py_TYPE(q) = (struct _typeobject *)(q-1);
63 Py_TYPE(q) = NULL;
64 return p + N_INTOBJECTS - 1;
65 }
66
67 #ifndef NSMALLPOSINTS
68 #define NSMALLPOSINTS 257
69 #endif
70 #ifndef NSMALLNEGINTS
71 #define NSMALLNEGINTS 5
72 #endif
73 #if NSMALLNEGINTS + NSMALLPOSINTS > 0
74 /* References to small integers are saved in this array so that they
75 can be shared.
76 The integers that are saved are those in the range
77 -NSMALLNEGINTS (inclusive) to NSMALLPOSINTS (not inclusive).
78 */
79 static PyIntObject *small_ints[NSMALLNEGINTS + NSMALLPOSINTS];
80 #endif
81 #ifdef COUNT_ALLOCS
82 Py_ssize_t quick_int_allocs;
83 Py_ssize_t quick_neg_int_allocs;
84 #endif
85
86 PyObject *
PyInt_FromLong(long ival)87 PyInt_FromLong(long ival)
88 {
89 register PyIntObject *v;
90 #if NSMALLNEGINTS + NSMALLPOSINTS > 0
91 if (-NSMALLNEGINTS <= ival && ival < NSMALLPOSINTS) {
92 v = small_ints[ival + NSMALLNEGINTS];
93 Py_INCREF(v);
94 #ifdef COUNT_ALLOCS
95 if (ival >= 0)
96 quick_int_allocs++;
97 else
98 quick_neg_int_allocs++;
99 #endif
100 return (PyObject *) v;
101 }
102 #endif
103 if (free_list == NULL) {
104 if ((free_list = fill_free_list()) == NULL)
105 return NULL;
106 }
107 /* Inline PyObject_New */
108 v = free_list;
109 free_list = (PyIntObject *)Py_TYPE(v);
110 (void)PyObject_INIT(v, &PyInt_Type);
111 v->ob_ival = ival;
112 return (PyObject *) v;
113 }
114
115 PyObject *
PyInt_FromSize_t(size_t ival)116 PyInt_FromSize_t(size_t ival)
117 {
118 if (ival <= LONG_MAX)
119 return PyInt_FromLong((long)ival);
120 return _PyLong_FromSize_t(ival);
121 }
122
123 PyObject *
PyInt_FromSsize_t(Py_ssize_t ival)124 PyInt_FromSsize_t(Py_ssize_t ival)
125 {
126 if (ival >= LONG_MIN && ival <= LONG_MAX)
127 return PyInt_FromLong((long)ival);
128 return _PyLong_FromSsize_t(ival);
129 }
130
131 static void
int_dealloc(PyIntObject * v)132 int_dealloc(PyIntObject *v)
133 {
134 if (PyInt_CheckExact(v)) {
135 Py_TYPE(v) = (struct _typeobject *)free_list;
136 free_list = v;
137 }
138 else
139 Py_TYPE(v)->tp_free((PyObject *)v);
140 }
141
142 long
PyInt_AsLong(register PyObject * op)143 PyInt_AsLong(register PyObject *op)
144 {
145 PyNumberMethods *nb;
146 PyIntObject *io;
147 long val;
148
149 if (op && PyInt_Check(op))
150 return PyInt_AS_LONG((PyIntObject*) op);
151
152 if (op == NULL || (nb = Py_TYPE(op)->tp_as_number) == NULL ||
153 nb->nb_int == NULL) {
154 PyErr_SetString(PyExc_TypeError, "an integer is required");
155 return -1;
156 }
157
158 io = (PyIntObject*) (*nb->nb_int) (op);
159 if (io == NULL)
160 return -1;
161 if (!PyInt_Check(io)) {
162 if (PyLong_Check(io)) {
163 /* got a long? => retry int conversion */
164 val = PyLong_AsLong((PyObject *)io);
165 Py_DECREF(io);
166 if ((val == -1) && PyErr_Occurred())
167 return -1;
168 return val;
169 }
170 else
171 {
172 Py_DECREF(io);
173 PyErr_SetString(PyExc_TypeError,
174 "__int__ method should return an integer");
175 return -1;
176 }
177 }
178
179 val = PyInt_AS_LONG(io);
180 Py_DECREF(io);
181
182 return val;
183 }
184
185 int
_PyInt_AsInt(PyObject * obj)186 _PyInt_AsInt(PyObject *obj)
187 {
188 long result = PyInt_AsLong(obj);
189 if (result == -1 && PyErr_Occurred())
190 return -1;
191 if (result > INT_MAX || result < INT_MIN) {
192 PyErr_SetString(PyExc_OverflowError,
193 "Python int too large to convert to C int");
194 return -1;
195 }
196 return (int)result;
197 }
198
199 Py_ssize_t
PyInt_AsSsize_t(register PyObject * op)200 PyInt_AsSsize_t(register PyObject *op)
201 {
202 #if SIZEOF_SIZE_T != SIZEOF_LONG
203 PyNumberMethods *nb;
204 PyObject *io;
205 Py_ssize_t val;
206 #endif
207
208 if (op == NULL) {
209 PyErr_SetString(PyExc_TypeError, "an integer is required");
210 return -1;
211 }
212
213 if (PyInt_Check(op))
214 return PyInt_AS_LONG((PyIntObject*) op);
215 if (PyLong_Check(op))
216 return _PyLong_AsSsize_t(op);
217 #if SIZEOF_SIZE_T == SIZEOF_LONG
218 return PyInt_AsLong(op);
219 #else
220
221 if ((nb = Py_TYPE(op)->tp_as_number) == NULL ||
222 (nb->nb_int == NULL && nb->nb_long == 0)) {
223 PyErr_SetString(PyExc_TypeError, "an integer is required");
224 return -1;
225 }
226
227 if (nb->nb_long != 0)
228 io = (*nb->nb_long)(op);
229 else
230 io = (*nb->nb_int)(op);
231 if (io == NULL)
232 return -1;
233 if (!PyInt_Check(io)) {
234 if (PyLong_Check(io)) {
235 /* got a long? => retry int conversion */
236 val = _PyLong_AsSsize_t(io);
237 Py_DECREF(io);
238 if ((val == -1) && PyErr_Occurred())
239 return -1;
240 return val;
241 }
242 else
243 {
244 Py_DECREF(io);
245 PyErr_SetString(PyExc_TypeError,
246 "__int__ method should return an integer");
247 return -1;
248 }
249 }
250
251 val = PyInt_AS_LONG(io);
252 Py_DECREF(io);
253
254 return val;
255 #endif
256 }
257
258 unsigned long
PyInt_AsUnsignedLongMask(register PyObject * op)259 PyInt_AsUnsignedLongMask(register PyObject *op)
260 {
261 PyNumberMethods *nb;
262 PyIntObject *io;
263 unsigned long val;
264
265 if (op && PyInt_Check(op))
266 return PyInt_AS_LONG((PyIntObject*) op);
267 if (op && PyLong_Check(op))
268 return PyLong_AsUnsignedLongMask(op);
269
270 if (op == NULL || (nb = Py_TYPE(op)->tp_as_number) == NULL ||
271 nb->nb_int == NULL) {
272 PyErr_SetString(PyExc_TypeError, "an integer is required");
273 return (unsigned long)-1;
274 }
275
276 io = (PyIntObject*) (*nb->nb_int) (op);
277 if (io == NULL)
278 return (unsigned long)-1;
279 if (!PyInt_Check(io)) {
280 if (PyLong_Check(io)) {
281 val = PyLong_AsUnsignedLongMask((PyObject *)io);
282 Py_DECREF(io);
283 if (PyErr_Occurred())
284 return (unsigned long)-1;
285 return val;
286 }
287 else
288 {
289 Py_DECREF(io);
290 PyErr_SetString(PyExc_TypeError,
291 "__int__ method should return an integer");
292 return (unsigned long)-1;
293 }
294 }
295
296 val = PyInt_AS_LONG(io);
297 Py_DECREF(io);
298
299 return val;
300 }
301
302 #ifdef HAVE_LONG_LONG
303 unsigned PY_LONG_LONG
PyInt_AsUnsignedLongLongMask(register PyObject * op)304 PyInt_AsUnsignedLongLongMask(register PyObject *op)
305 {
306 PyNumberMethods *nb;
307 PyIntObject *io;
308 unsigned PY_LONG_LONG val;
309
310 if (op && PyInt_Check(op))
311 return PyInt_AS_LONG((PyIntObject*) op);
312 if (op && PyLong_Check(op))
313 return PyLong_AsUnsignedLongLongMask(op);
314
315 if (op == NULL || (nb = Py_TYPE(op)->tp_as_number) == NULL ||
316 nb->nb_int == NULL) {
317 PyErr_SetString(PyExc_TypeError, "an integer is required");
318 return (unsigned PY_LONG_LONG)-1;
319 }
320
321 io = (PyIntObject*) (*nb->nb_int) (op);
322 if (io == NULL)
323 return (unsigned PY_LONG_LONG)-1;
324 if (!PyInt_Check(io)) {
325 if (PyLong_Check(io)) {
326 val = PyLong_AsUnsignedLongLongMask((PyObject *)io);
327 Py_DECREF(io);
328 if (PyErr_Occurred())
329 return (unsigned PY_LONG_LONG)-1;
330 return val;
331 }
332 else
333 {
334 Py_DECREF(io);
335 PyErr_SetString(PyExc_TypeError,
336 "__int__ method should return an integer");
337 return (unsigned PY_LONG_LONG)-1;
338 }
339 }
340
341 val = PyInt_AS_LONG(io);
342 Py_DECREF(io);
343
344 return val;
345 }
346 #endif
347
348 PyObject *
PyInt_FromString(char * s,char ** pend,int base)349 PyInt_FromString(char *s, char **pend, int base)
350 {
351 char *end;
352 long x;
353 Py_ssize_t slen;
354 PyObject *sobj, *srepr;
355
356 if ((base != 0 && base < 2) || base > 36) {
357 PyErr_SetString(PyExc_ValueError,
358 "int() base must be >= 2 and <= 36");
359 return NULL;
360 }
361
362 while (*s && isspace(Py_CHARMASK(*s)))
363 s++;
364 errno = 0;
365 if (base == 0 && s[0] == '0') {
366 x = (long) PyOS_strtoul(s, &end, base);
367 if (x < 0)
368 return PyLong_FromString(s, pend, base);
369 }
370 else
371 x = PyOS_strtol(s, &end, base);
372 if (end == s || !isalnum(Py_CHARMASK(end[-1])))
373 goto bad;
374 while (*end && isspace(Py_CHARMASK(*end)))
375 end++;
376 if (*end != '\0') {
377 bad:
378 slen = strlen(s) < 200 ? strlen(s) : 200;
379 sobj = PyString_FromStringAndSize(s, slen);
380 if (sobj == NULL)
381 return NULL;
382 srepr = PyObject_Repr(sobj);
383 Py_DECREF(sobj);
384 if (srepr == NULL)
385 return NULL;
386 PyErr_Format(PyExc_ValueError,
387 "invalid literal for int() with base %d: %s",
388 base, PyString_AS_STRING(srepr));
389 Py_DECREF(srepr);
390 return NULL;
391 }
392 else if (errno != 0)
393 return PyLong_FromString(s, pend, base);
394 if (pend)
395 *pend = end;
396 return PyInt_FromLong(x);
397 }
398
399 #ifdef Py_USING_UNICODE
400 PyObject *
PyInt_FromUnicode(Py_UNICODE * s,Py_ssize_t length,int base)401 PyInt_FromUnicode(Py_UNICODE *s, Py_ssize_t length, int base)
402 {
403 PyObject *result;
404 char *buffer = (char *)PyMem_MALLOC(length+1);
405
406 if (buffer == NULL)
407 return PyErr_NoMemory();
408
409 if (PyUnicode_EncodeDecimal(s, length, buffer, NULL)) {
410 PyMem_FREE(buffer);
411 return NULL;
412 }
413 result = PyInt_FromString(buffer, NULL, base);
414 PyMem_FREE(buffer);
415 return result;
416 }
417 #endif
418
419 /* Methods */
420
421 /* Integers are seen as the "smallest" of all numeric types and thus
422 don't have any knowledge about conversion of other types to
423 integers. */
424
425 #define CONVERT_TO_LONG(obj, lng) \
426 if (PyInt_Check(obj)) { \
427 lng = PyInt_AS_LONG(obj); \
428 } \
429 else { \
430 Py_INCREF(Py_NotImplemented); \
431 return Py_NotImplemented; \
432 }
433
434 /* ARGSUSED */
435 static int
int_print(PyIntObject * v,FILE * fp,int flags)436 int_print(PyIntObject *v, FILE *fp, int flags)
437 /* flags -- not used but required by interface */
438 {
439 long int_val = v->ob_ival;
440 Py_BEGIN_ALLOW_THREADS
441 fprintf(fp, "%ld", int_val);
442 Py_END_ALLOW_THREADS
443 return 0;
444 }
445
446 static int
int_compare(PyIntObject * v,PyIntObject * w)447 int_compare(PyIntObject *v, PyIntObject *w)
448 {
449 register long i = v->ob_ival;
450 register long j = w->ob_ival;
451 return (i < j) ? -1 : (i > j) ? 1 : 0;
452 }
453
454 static long
int_hash(PyIntObject * v)455 int_hash(PyIntObject *v)
456 {
457 /* XXX If this is changed, you also need to change the way
458 Python's long, float and complex types are hashed. */
459 long x = v -> ob_ival;
460 if (x == -1)
461 x = -2;
462 return x;
463 }
464
465 static PyObject *
int_add(PyIntObject * v,PyIntObject * w)466 int_add(PyIntObject *v, PyIntObject *w)
467 {
468 register long a, b, x;
469 CONVERT_TO_LONG(v, a);
470 CONVERT_TO_LONG(w, b);
471 /* casts in the line below avoid undefined behaviour on overflow */
472 x = (long)((unsigned long)a + b);
473 if ((x^a) >= 0 || (x^b) >= 0)
474 return PyInt_FromLong(x);
475 return PyLong_Type.tp_as_number->nb_add((PyObject *)v, (PyObject *)w);
476 }
477
478 static PyObject *
int_sub(PyIntObject * v,PyIntObject * w)479 int_sub(PyIntObject *v, PyIntObject *w)
480 {
481 register long a, b, x;
482 CONVERT_TO_LONG(v, a);
483 CONVERT_TO_LONG(w, b);
484 /* casts in the line below avoid undefined behaviour on overflow */
485 x = (long)((unsigned long)a - b);
486 if ((x^a) >= 0 || (x^~b) >= 0)
487 return PyInt_FromLong(x);
488 return PyLong_Type.tp_as_number->nb_subtract((PyObject *)v,
489 (PyObject *)w);
490 }
491
492 /*
493 Integer overflow checking for * is painful: Python tried a couple ways, but
494 they didn't work on all platforms, or failed in endcases (a product of
495 -sys.maxint-1 has been a particular pain).
496
497 Here's another way:
498
499 The native long product x*y is either exactly right or *way* off, being
500 just the last n bits of the true product, where n is the number of bits
501 in a long (the delivered product is the true product plus i*2**n for
502 some integer i).
503
504 The native double product (double)x * (double)y is subject to three
505 rounding errors: on a sizeof(long)==8 box, each cast to double can lose
506 info, and even on a sizeof(long)==4 box, the multiplication can lose info.
507 But, unlike the native long product, it's not in *range* trouble: even
508 if sizeof(long)==32 (256-bit longs), the product easily fits in the
509 dynamic range of a double. So the leading 50 (or so) bits of the double
510 product are correct.
511
512 We check these two ways against each other, and declare victory if they're
513 approximately the same. Else, because the native long product is the only
514 one that can lose catastrophic amounts of information, it's the native long
515 product that must have overflowed.
516 */
517
518 static PyObject *
int_mul(PyObject * v,PyObject * w)519 int_mul(PyObject *v, PyObject *w)
520 {
521 long a, b;
522 long longprod; /* a*b in native long arithmetic */
523 double doubled_longprod; /* (double)longprod */
524 double doubleprod; /* (double)a * (double)b */
525
526 CONVERT_TO_LONG(v, a);
527 CONVERT_TO_LONG(w, b);
528 /* casts in the next line avoid undefined behaviour on overflow */
529 longprod = (long)((unsigned long)a * b);
530 doubleprod = (double)a * (double)b;
531 doubled_longprod = (double)longprod;
532
533 /* Fast path for normal case: small multiplicands, and no info
534 is lost in either method. */
535 if (doubled_longprod == doubleprod)
536 return PyInt_FromLong(longprod);
537
538 /* Somebody somewhere lost info. Close enough, or way off? Note
539 that a != 0 and b != 0 (else doubled_longprod == doubleprod == 0).
540 The difference either is or isn't significant compared to the
541 true value (of which doubleprod is a good approximation).
542 */
543 {
544 const double diff = doubled_longprod - doubleprod;
545 const double absdiff = diff >= 0.0 ? diff : -diff;
546 const double absprod = doubleprod >= 0.0 ? doubleprod :
547 -doubleprod;
548 /* absdiff/absprod <= 1/32 iff
549 32 * absdiff <= absprod -- 5 good bits is "close enough" */
550 if (32.0 * absdiff <= absprod)
551 return PyInt_FromLong(longprod);
552 else
553 return PyLong_Type.tp_as_number->nb_multiply(v, w);
554 }
555 }
556
557 /* Integer overflow checking for unary negation: on a 2's-complement
558 * box, -x overflows iff x is the most negative long. In this case we
559 * get -x == x. However, -x is undefined (by C) if x /is/ the most
560 * negative long (it's a signed overflow case), and some compilers care.
561 * So we cast x to unsigned long first. However, then other compilers
562 * warn about applying unary minus to an unsigned operand. Hence the
563 * weird "0-".
564 */
565 #define UNARY_NEG_WOULD_OVERFLOW(x) \
566 ((x) < 0 && (unsigned long)(x) == 0-(unsigned long)(x))
567
568 /* Return type of i_divmod */
569 enum divmod_result {
570 DIVMOD_OK, /* Correct result */
571 DIVMOD_OVERFLOW, /* Overflow, try again using longs */
572 DIVMOD_ERROR /* Exception raised */
573 };
574
575 static enum divmod_result
i_divmod(register long x,register long y,long * p_xdivy,long * p_xmody)576 i_divmod(register long x, register long y,
577 long *p_xdivy, long *p_xmody)
578 {
579 long xdivy, xmody;
580
581 if (y == 0) {
582 PyErr_SetString(PyExc_ZeroDivisionError,
583 "integer division or modulo by zero");
584 return DIVMOD_ERROR;
585 }
586 /* (-sys.maxint-1)/-1 is the only overflow case. */
587 if (y == -1 && UNARY_NEG_WOULD_OVERFLOW(x))
588 return DIVMOD_OVERFLOW;
589 xdivy = x / y;
590 /* xdiv*y can overflow on platforms where x/y gives floor(x/y)
591 * for x and y with differing signs. (This is unusual
592 * behaviour, and C99 prohibits it, but it's allowed by C89;
593 * for an example of overflow, take x = LONG_MIN, y = 5 or x =
594 * LONG_MAX, y = -5.) However, x - xdivy*y is always
595 * representable as a long, since it lies strictly between
596 * -abs(y) and abs(y). We add casts to avoid intermediate
597 * overflow.
598 */
599 xmody = (long)(x - (unsigned long)xdivy * y);
600 /* If the signs of x and y differ, and the remainder is non-0,
601 * C89 doesn't define whether xdivy is now the floor or the
602 * ceiling of the infinitely precise quotient. We want the floor,
603 * and we have it iff the remainder's sign matches y's.
604 */
605 if (xmody && ((y ^ xmody) < 0) /* i.e. and signs differ */) {
606 xmody += y;
607 --xdivy;
608 assert(xmody && ((y ^ xmody) >= 0));
609 }
610 *p_xdivy = xdivy;
611 *p_xmody = xmody;
612 return DIVMOD_OK;
613 }
614
615 static PyObject *
int_div(PyIntObject * x,PyIntObject * y)616 int_div(PyIntObject *x, PyIntObject *y)
617 {
618 long xi, yi;
619 long d, m;
620 CONVERT_TO_LONG(x, xi);
621 CONVERT_TO_LONG(y, yi);
622 switch (i_divmod(xi, yi, &d, &m)) {
623 case DIVMOD_OK:
624 return PyInt_FromLong(d);
625 case DIVMOD_OVERFLOW:
626 return PyLong_Type.tp_as_number->nb_divide((PyObject *)x,
627 (PyObject *)y);
628 default:
629 return NULL;
630 }
631 }
632
633 static PyObject *
int_classic_div(PyIntObject * x,PyIntObject * y)634 int_classic_div(PyIntObject *x, PyIntObject *y)
635 {
636 long xi, yi;
637 long d, m;
638 CONVERT_TO_LONG(x, xi);
639 CONVERT_TO_LONG(y, yi);
640 if (Py_DivisionWarningFlag &&
641 PyErr_Warn(PyExc_DeprecationWarning, "classic int division") < 0)
642 return NULL;
643 switch (i_divmod(xi, yi, &d, &m)) {
644 case DIVMOD_OK:
645 return PyInt_FromLong(d);
646 case DIVMOD_OVERFLOW:
647 return PyLong_Type.tp_as_number->nb_divide((PyObject *)x,
648 (PyObject *)y);
649 default:
650 return NULL;
651 }
652 }
653
654 static PyObject *
int_true_divide(PyIntObject * x,PyIntObject * y)655 int_true_divide(PyIntObject *x, PyIntObject *y)
656 {
657 long xi, yi;
658 /* If they aren't both ints, give someone else a chance. In
659 particular, this lets int/long get handled by longs, which
660 underflows to 0 gracefully if the long is too big to convert
661 to float. */
662 CONVERT_TO_LONG(x, xi);
663 CONVERT_TO_LONG(y, yi);
664 if (yi == 0) {
665 PyErr_SetString(PyExc_ZeroDivisionError,
666 "division by zero");
667 return NULL;
668 }
669 if (xi == 0)
670 return PyFloat_FromDouble(yi < 0 ? -0.0 : 0.0);
671
672 #define WIDTH_OF_ULONG (CHAR_BIT*SIZEOF_LONG)
673 #if DBL_MANT_DIG < WIDTH_OF_ULONG
674 if ((xi >= 0 ? 0UL + xi : 0UL - xi) >> DBL_MANT_DIG ||
675 (yi >= 0 ? 0UL + yi : 0UL - yi) >> DBL_MANT_DIG)
676 /* Large x or y. Use long integer arithmetic. */
677 return PyLong_Type.tp_as_number->nb_true_divide(
678 (PyObject *)x, (PyObject *)y);
679 else
680 #endif
681 /* Both ints can be exactly represented as doubles. Do a
682 floating-point division. */
683 return PyFloat_FromDouble((double)xi / (double)yi);
684 }
685
686 static PyObject *
int_mod(PyIntObject * x,PyIntObject * y)687 int_mod(PyIntObject *x, PyIntObject *y)
688 {
689 long xi, yi;
690 long d, m;
691 CONVERT_TO_LONG(x, xi);
692 CONVERT_TO_LONG(y, yi);
693 switch (i_divmod(xi, yi, &d, &m)) {
694 case DIVMOD_OK:
695 return PyInt_FromLong(m);
696 case DIVMOD_OVERFLOW:
697 return PyLong_Type.tp_as_number->nb_remainder((PyObject *)x,
698 (PyObject *)y);
699 default:
700 return NULL;
701 }
702 }
703
704 static PyObject *
int_divmod(PyIntObject * x,PyIntObject * y)705 int_divmod(PyIntObject *x, PyIntObject *y)
706 {
707 long xi, yi;
708 long d, m;
709 CONVERT_TO_LONG(x, xi);
710 CONVERT_TO_LONG(y, yi);
711 switch (i_divmod(xi, yi, &d, &m)) {
712 case DIVMOD_OK:
713 return Py_BuildValue("(ll)", d, m);
714 case DIVMOD_OVERFLOW:
715 return PyLong_Type.tp_as_number->nb_divmod((PyObject *)x,
716 (PyObject *)y);
717 default:
718 return NULL;
719 }
720 }
721
722 static PyObject *
int_pow(PyIntObject * v,PyIntObject * w,PyIntObject * z)723 int_pow(PyIntObject *v, PyIntObject *w, PyIntObject *z)
724 {
725 register long iv, iw, iz=0, ix, temp, prev;
726 CONVERT_TO_LONG(v, iv);
727 CONVERT_TO_LONG(w, iw);
728 if (iw < 0) {
729 if ((PyObject *)z != Py_None) {
730 PyErr_SetString(PyExc_TypeError, "pow() 2nd argument "
731 "cannot be negative when 3rd argument specified");
732 return NULL;
733 }
734 /* Return a float. This works because we know that
735 this calls float_pow() which converts its
736 arguments to double. */
737 return PyFloat_Type.tp_as_number->nb_power(
738 (PyObject *)v, (PyObject *)w, (PyObject *)z);
739 }
740 if ((PyObject *)z != Py_None) {
741 CONVERT_TO_LONG(z, iz);
742 if (iz == 0) {
743 PyErr_SetString(PyExc_ValueError,
744 "pow() 3rd argument cannot be 0");
745 return NULL;
746 }
747 }
748 /*
749 * XXX: The original exponentiation code stopped looping
750 * when temp hit zero; this code will continue onwards
751 * unnecessarily, but at least it won't cause any errors.
752 * Hopefully the speed improvement from the fast exponentiation
753 * will compensate for the slight inefficiency.
754 * XXX: Better handling of overflows is desperately needed.
755 */
756 temp = iv;
757 ix = 1;
758 while (iw > 0) {
759 prev = ix; /* Save value for overflow check */
760 if (iw & 1) {
761 /*
762 * The (unsigned long) cast below ensures that the multiplication
763 * is interpreted as an unsigned operation rather than a signed one
764 * (C99 6.3.1.8p1), thus avoiding the perils of undefined behaviour
765 * from signed arithmetic overflow (C99 6.5p5). See issue #12973.
766 */
767 ix = (unsigned long)ix * temp;
768 if (temp == 0)
769 break; /* Avoid ix / 0 */
770 if (ix / temp != prev) {
771 return PyLong_Type.tp_as_number->nb_power(
772 (PyObject *)v,
773 (PyObject *)w,
774 (PyObject *)z);
775 }
776 }
777 iw >>= 1; /* Shift exponent down by 1 bit */
778 if (iw==0) break;
779 prev = temp;
780 temp = (unsigned long)temp * temp; /* Square the value of temp */
781 if (prev != 0 && temp / prev != prev) {
782 return PyLong_Type.tp_as_number->nb_power(
783 (PyObject *)v, (PyObject *)w, (PyObject *)z);
784 }
785 if (iz) {
786 /* If we did a multiplication, perform a modulo */
787 ix = ix % iz;
788 temp = temp % iz;
789 }
790 }
791 if (iz) {
792 long div, mod;
793 switch (i_divmod(ix, iz, &div, &mod)) {
794 case DIVMOD_OK:
795 ix = mod;
796 break;
797 case DIVMOD_OVERFLOW:
798 return PyLong_Type.tp_as_number->nb_power(
799 (PyObject *)v, (PyObject *)w, (PyObject *)z);
800 default:
801 return NULL;
802 }
803 }
804 return PyInt_FromLong(ix);
805 }
806
807 static PyObject *
int_neg(PyIntObject * v)808 int_neg(PyIntObject *v)
809 {
810 register long a;
811 a = v->ob_ival;
812 /* check for overflow */
813 if (UNARY_NEG_WOULD_OVERFLOW(a)) {
814 PyObject *o = PyLong_FromLong(a);
815 if (o != NULL) {
816 PyObject *result = PyNumber_Negative(o);
817 Py_DECREF(o);
818 return result;
819 }
820 return NULL;
821 }
822 return PyInt_FromLong(-a);
823 }
824
825 static PyObject *
int_abs(PyIntObject * v)826 int_abs(PyIntObject *v)
827 {
828 if (v->ob_ival >= 0)
829 return int_int(v);
830 else
831 return int_neg(v);
832 }
833
834 static int
int_nonzero(PyIntObject * v)835 int_nonzero(PyIntObject *v)
836 {
837 return v->ob_ival != 0;
838 }
839
840 static PyObject *
int_invert(PyIntObject * v)841 int_invert(PyIntObject *v)
842 {
843 return PyInt_FromLong(~v->ob_ival);
844 }
845
846 static PyObject *
int_lshift(PyIntObject * v,PyIntObject * w)847 int_lshift(PyIntObject *v, PyIntObject *w)
848 {
849 long a, b, c;
850 PyObject *vv, *ww, *result;
851
852 CONVERT_TO_LONG(v, a);
853 CONVERT_TO_LONG(w, b);
854 if (b < 0) {
855 PyErr_SetString(PyExc_ValueError, "negative shift count");
856 return NULL;
857 }
858 if (a == 0 || b == 0)
859 return int_int(v);
860 if (b >= LONG_BIT) {
861 vv = PyLong_FromLong(PyInt_AS_LONG(v));
862 if (vv == NULL)
863 return NULL;
864 ww = PyLong_FromLong(PyInt_AS_LONG(w));
865 if (ww == NULL) {
866 Py_DECREF(vv);
867 return NULL;
868 }
869 result = PyNumber_Lshift(vv, ww);
870 Py_DECREF(vv);
871 Py_DECREF(ww);
872 return result;
873 }
874 c = a << b;
875 if (a != Py_ARITHMETIC_RIGHT_SHIFT(long, c, b)) {
876 vv = PyLong_FromLong(PyInt_AS_LONG(v));
877 if (vv == NULL)
878 return NULL;
879 ww = PyLong_FromLong(PyInt_AS_LONG(w));
880 if (ww == NULL) {
881 Py_DECREF(vv);
882 return NULL;
883 }
884 result = PyNumber_Lshift(vv, ww);
885 Py_DECREF(vv);
886 Py_DECREF(ww);
887 return result;
888 }
889 return PyInt_FromLong(c);
890 }
891
892 static PyObject *
int_rshift(PyIntObject * v,PyIntObject * w)893 int_rshift(PyIntObject *v, PyIntObject *w)
894 {
895 register long a, b;
896 CONVERT_TO_LONG(v, a);
897 CONVERT_TO_LONG(w, b);
898 if (b < 0) {
899 PyErr_SetString(PyExc_ValueError, "negative shift count");
900 return NULL;
901 }
902 if (a == 0 || b == 0)
903 return int_int(v);
904 if (b >= LONG_BIT) {
905 if (a < 0)
906 a = -1;
907 else
908 a = 0;
909 }
910 else {
911 a = Py_ARITHMETIC_RIGHT_SHIFT(long, a, b);
912 }
913 return PyInt_FromLong(a);
914 }
915
916 static PyObject *
int_and(PyIntObject * v,PyIntObject * w)917 int_and(PyIntObject *v, PyIntObject *w)
918 {
919 register long a, b;
920 CONVERT_TO_LONG(v, a);
921 CONVERT_TO_LONG(w, b);
922 return PyInt_FromLong(a & b);
923 }
924
925 static PyObject *
int_xor(PyIntObject * v,PyIntObject * w)926 int_xor(PyIntObject *v, PyIntObject *w)
927 {
928 register long a, b;
929 CONVERT_TO_LONG(v, a);
930 CONVERT_TO_LONG(w, b);
931 return PyInt_FromLong(a ^ b);
932 }
933
934 static PyObject *
int_or(PyIntObject * v,PyIntObject * w)935 int_or(PyIntObject *v, PyIntObject *w)
936 {
937 register long a, b;
938 CONVERT_TO_LONG(v, a);
939 CONVERT_TO_LONG(w, b);
940 return PyInt_FromLong(a | b);
941 }
942
943 static int
int_coerce(PyObject ** pv,PyObject ** pw)944 int_coerce(PyObject **pv, PyObject **pw)
945 {
946 if (PyInt_Check(*pw)) {
947 Py_INCREF(*pv);
948 Py_INCREF(*pw);
949 return 0;
950 }
951 return 1; /* Can't do it */
952 }
953
954 static PyObject *
int_int(PyIntObject * v)955 int_int(PyIntObject *v)
956 {
957 if (PyInt_CheckExact(v))
958 Py_INCREF(v);
959 else
960 v = (PyIntObject *)PyInt_FromLong(v->ob_ival);
961 return (PyObject *)v;
962 }
963
964 static PyObject *
int_long(PyIntObject * v)965 int_long(PyIntObject *v)
966 {
967 return PyLong_FromLong((v -> ob_ival));
968 }
969
970 static const unsigned char BitLengthTable[32] = {
971 0, 1, 2, 2, 3, 3, 3, 3, 4, 4, 4, 4, 4, 4, 4, 4,
972 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5
973 };
974
975 static int
bits_in_ulong(unsigned long d)976 bits_in_ulong(unsigned long d)
977 {
978 int d_bits = 0;
979 while (d >= 32) {
980 d_bits += 6;
981 d >>= 6;
982 }
983 d_bits += (int)BitLengthTable[d];
984 return d_bits;
985 }
986
987 #if 8*SIZEOF_LONG-1 <= DBL_MANT_DIG
988 /* Every Python int can be exactly represented as a float. */
989
990 static PyObject *
int_float(PyIntObject * v)991 int_float(PyIntObject *v)
992 {
993 return PyFloat_FromDouble((double)(v -> ob_ival));
994 }
995
996 #else
997 /* Here not all Python ints are exactly representable as floats, so we may
998 have to round. We do this manually, since the C standards don't specify
999 whether converting an integer to a float rounds up or down */
1000
1001 static PyObject *
int_float(PyIntObject * v)1002 int_float(PyIntObject *v)
1003 {
1004 unsigned long abs_ival, lsb;
1005 int round_up;
1006
1007 if (v->ob_ival < 0)
1008 abs_ival = 0U-(unsigned long)v->ob_ival;
1009 else
1010 abs_ival = (unsigned long)v->ob_ival;
1011 if (abs_ival < (1L << DBL_MANT_DIG))
1012 /* small integer; no need to round */
1013 return PyFloat_FromDouble((double)v->ob_ival);
1014
1015 /* Round abs_ival to MANT_DIG significant bits, using the
1016 round-half-to-even rule. abs_ival & lsb picks out the 'rounding'
1017 bit: the first bit after the most significant MANT_DIG bits of
1018 abs_ival. We round up if this bit is set, provided that either:
1019
1020 (1) abs_ival isn't exactly halfway between two floats, in which
1021 case at least one of the bits following the rounding bit must be
1022 set; i.e., abs_ival & lsb-1 != 0, or:
1023
1024 (2) the resulting rounded value has least significant bit 0; or
1025 in other words the bit above the rounding bit is set (this is the
1026 'to-even' bit of round-half-to-even); i.e., abs_ival & 2*lsb != 0
1027
1028 The condition "(1) or (2)" equates to abs_ival & 3*lsb-1 != 0. */
1029
1030 lsb = 1L << (bits_in_ulong(abs_ival)-DBL_MANT_DIG-1);
1031 round_up = (abs_ival & lsb) && (abs_ival & (3*lsb-1));
1032 abs_ival &= -2*lsb;
1033 if (round_up)
1034 abs_ival += 2*lsb;
1035 return PyFloat_FromDouble(v->ob_ival < 0 ?
1036 -(double)abs_ival :
1037 (double)abs_ival);
1038 }
1039
1040 #endif
1041
1042 static PyObject *
int_oct(PyIntObject * v)1043 int_oct(PyIntObject *v)
1044 {
1045 return _PyInt_Format(v, 8, 0);
1046 }
1047
1048 static PyObject *
int_hex(PyIntObject * v)1049 int_hex(PyIntObject *v)
1050 {
1051 return _PyInt_Format(v, 16, 0);
1052 }
1053
1054 static PyObject *
1055 int_subtype_new(PyTypeObject *type, PyObject *args, PyObject *kwds);
1056
1057 static PyObject *
int_new(PyTypeObject * type,PyObject * args,PyObject * kwds)1058 int_new(PyTypeObject *type, PyObject *args, PyObject *kwds)
1059 {
1060 PyObject *x = NULL;
1061 int base = -909;
1062 static char *kwlist[] = {"x", "base", 0};
1063
1064 if (type != &PyInt_Type)
1065 return int_subtype_new(type, args, kwds); /* Wimp out */
1066 if (!PyArg_ParseTupleAndKeywords(args, kwds, "|Oi:int", kwlist,
1067 &x, &base))
1068 return NULL;
1069 if (x == NULL) {
1070 if (base != -909) {
1071 PyErr_SetString(PyExc_TypeError,
1072 "int() missing string argument");
1073 return NULL;
1074 }
1075 return PyInt_FromLong(0L);
1076 }
1077 if (base == -909)
1078 return PyNumber_Int(x);
1079 if (PyString_Check(x)) {
1080 /* Since PyInt_FromString doesn't have a length parameter,
1081 * check here for possible NULs in the string. */
1082 char *string = PyString_AS_STRING(x);
1083 if (strlen(string) != PyString_Size(x)) {
1084 /* create a repr() of the input string,
1085 * just like PyInt_FromString does */
1086 PyObject *srepr;
1087 srepr = PyObject_Repr(x);
1088 if (srepr == NULL)
1089 return NULL;
1090 PyErr_Format(PyExc_ValueError,
1091 "invalid literal for int() with base %d: %s",
1092 base, PyString_AS_STRING(srepr));
1093 Py_DECREF(srepr);
1094 return NULL;
1095 }
1096 return PyInt_FromString(string, NULL, base);
1097 }
1098 #ifdef Py_USING_UNICODE
1099 if (PyUnicode_Check(x))
1100 return PyInt_FromUnicode(PyUnicode_AS_UNICODE(x),
1101 PyUnicode_GET_SIZE(x),
1102 base);
1103 #endif
1104 PyErr_SetString(PyExc_TypeError,
1105 "int() can't convert non-string with explicit base");
1106 return NULL;
1107 }
1108
1109 /* Wimpy, slow approach to tp_new calls for subtypes of int:
1110 first create a regular int from whatever arguments we got,
1111 then allocate a subtype instance and initialize its ob_ival
1112 from the regular int. The regular int is then thrown away.
1113 */
1114 static PyObject *
int_subtype_new(PyTypeObject * type,PyObject * args,PyObject * kwds)1115 int_subtype_new(PyTypeObject *type, PyObject *args, PyObject *kwds)
1116 {
1117 PyObject *tmp, *newobj;
1118 long ival;
1119
1120 assert(PyType_IsSubtype(type, &PyInt_Type));
1121 tmp = int_new(&PyInt_Type, args, kwds);
1122 if (tmp == NULL)
1123 return NULL;
1124 if (!PyInt_Check(tmp)) {
1125 ival = PyLong_AsLong(tmp);
1126 if (ival == -1 && PyErr_Occurred()) {
1127 Py_DECREF(tmp);
1128 return NULL;
1129 }
1130 } else {
1131 ival = ((PyIntObject *)tmp)->ob_ival;
1132 }
1133
1134 newobj = type->tp_alloc(type, 0);
1135 if (newobj == NULL) {
1136 Py_DECREF(tmp);
1137 return NULL;
1138 }
1139 ((PyIntObject *)newobj)->ob_ival = ival;
1140 Py_DECREF(tmp);
1141 return newobj;
1142 }
1143
1144 static PyObject *
int_getnewargs(PyIntObject * v)1145 int_getnewargs(PyIntObject *v)
1146 {
1147 return Py_BuildValue("(l)", v->ob_ival);
1148 }
1149
1150 static PyObject *
int_get0(PyIntObject * v,void * context)1151 int_get0(PyIntObject *v, void *context) {
1152 return PyInt_FromLong(0L);
1153 }
1154
1155 static PyObject *
int_get1(PyIntObject * v,void * context)1156 int_get1(PyIntObject *v, void *context) {
1157 return PyInt_FromLong(1L);
1158 }
1159
1160 /* Convert an integer to a decimal string. On many platforms, this
1161 will be significantly faster than the general arbitrary-base
1162 conversion machinery in _PyInt_Format, thanks to optimization
1163 opportunities offered by division by a compile-time constant. */
1164 static PyObject *
int_to_decimal_string(PyIntObject * v)1165 int_to_decimal_string(PyIntObject *v) {
1166 char buf[sizeof(long)*CHAR_BIT/3+6], *p, *bufend;
1167 long n = v->ob_ival;
1168 unsigned long absn;
1169 p = bufend = buf + sizeof(buf);
1170 absn = n < 0 ? 0UL - n : n;
1171 do {
1172 *--p = '0' + (char)(absn % 10);
1173 absn /= 10;
1174 } while (absn);
1175 if (n < 0)
1176 *--p = '-';
1177 return PyString_FromStringAndSize(p, bufend - p);
1178 }
1179
1180 /* Convert an integer to the given base. Returns a string.
1181 If base is 2, 8 or 16, add the proper prefix '0b', '0o' or '0x'.
1182 If newstyle is zero, then use the pre-2.6 behavior of octal having
1183 a leading "0" */
1184 PyAPI_FUNC(PyObject*)
_PyInt_Format(PyIntObject * v,int base,int newstyle)1185 _PyInt_Format(PyIntObject *v, int base, int newstyle)
1186 {
1187 /* There are no doubt many, many ways to optimize this, using code
1188 similar to _PyLong_Format */
1189 long n = v->ob_ival;
1190 int negative = n < 0;
1191 int is_zero = n == 0;
1192
1193 /* For the reasoning behind this size, see
1194 http://c-faq.com/misc/hexio.html. Then, add a few bytes for
1195 the possible sign and prefix "0[box]" */
1196 char buf[sizeof(n)*CHAR_BIT+6];
1197
1198 /* Start by pointing to the end of the buffer. We fill in from
1199 the back forward. */
1200 char* p = &buf[sizeof(buf)];
1201
1202 assert(base >= 2 && base <= 36);
1203
1204 /* Special case base 10, for speed */
1205 if (base == 10)
1206 return int_to_decimal_string(v);
1207
1208 do {
1209 /* I'd use i_divmod, except it doesn't produce the results
1210 I want when n is negative. So just duplicate the salient
1211 part here. */
1212 long div = n / base;
1213 long mod = n - div * base;
1214
1215 /* convert abs(mod) to the right character in [0-9, a-z] */
1216 char cdigit = (char)(mod < 0 ? -mod : mod);
1217 cdigit += (cdigit < 10) ? '0' : 'a'-10;
1218 *--p = cdigit;
1219
1220 n = div;
1221 } while(n);
1222
1223 if (base == 2) {
1224 *--p = 'b';
1225 *--p = '0';
1226 }
1227 else if (base == 8) {
1228 if (newstyle) {
1229 *--p = 'o';
1230 *--p = '0';
1231 }
1232 else
1233 if (!is_zero)
1234 *--p = '0';
1235 }
1236 else if (base == 16) {
1237 *--p = 'x';
1238 *--p = '0';
1239 }
1240 else {
1241 *--p = '#';
1242 *--p = '0' + base%10;
1243 if (base > 10)
1244 *--p = '0' + base/10;
1245 }
1246 if (negative)
1247 *--p = '-';
1248
1249 return PyString_FromStringAndSize(p, &buf[sizeof(buf)] - p);
1250 }
1251
1252 static PyObject *
int__format__(PyObject * self,PyObject * args)1253 int__format__(PyObject *self, PyObject *args)
1254 {
1255 PyObject *format_spec;
1256
1257 if (!PyArg_ParseTuple(args, "O:__format__", &format_spec))
1258 return NULL;
1259 if (PyBytes_Check(format_spec))
1260 return _PyInt_FormatAdvanced(self,
1261 PyBytes_AS_STRING(format_spec),
1262 PyBytes_GET_SIZE(format_spec));
1263 if (PyUnicode_Check(format_spec)) {
1264 /* Convert format_spec to a str */
1265 PyObject *result;
1266 PyObject *str_spec = PyObject_Str(format_spec);
1267
1268 if (str_spec == NULL)
1269 return NULL;
1270
1271 result = _PyInt_FormatAdvanced(self,
1272 PyBytes_AS_STRING(str_spec),
1273 PyBytes_GET_SIZE(str_spec));
1274
1275 Py_DECREF(str_spec);
1276 return result;
1277 }
1278 PyErr_SetString(PyExc_TypeError, "__format__ requires str or unicode");
1279 return NULL;
1280 }
1281
1282 static PyObject *
int_bit_length(PyIntObject * v)1283 int_bit_length(PyIntObject *v)
1284 {
1285 unsigned long n;
1286
1287 if (v->ob_ival < 0)
1288 /* avoid undefined behaviour when v->ob_ival == -LONG_MAX-1 */
1289 n = 0U-(unsigned long)v->ob_ival;
1290 else
1291 n = (unsigned long)v->ob_ival;
1292
1293 return PyInt_FromLong(bits_in_ulong(n));
1294 }
1295
1296 PyDoc_STRVAR(int_bit_length_doc,
1297 "int.bit_length() -> int\n\
1298 \n\
1299 Number of bits necessary to represent self in binary.\n\
1300 >>> bin(37)\n\
1301 '0b100101'\n\
1302 >>> (37).bit_length()\n\
1303 6");
1304
1305 #if 0
1306 static PyObject *
1307 int_is_finite(PyObject *v)
1308 {
1309 Py_RETURN_TRUE;
1310 }
1311 #endif
1312
1313 static PyMethodDef int_methods[] = {
1314 {"conjugate", (PyCFunction)int_int, METH_NOARGS,
1315 "Returns self, the complex conjugate of any int."},
1316 {"bit_length", (PyCFunction)int_bit_length, METH_NOARGS,
1317 int_bit_length_doc},
1318 #if 0
1319 {"is_finite", (PyCFunction)int_is_finite, METH_NOARGS,
1320 "Returns always True."},
1321 #endif
1322 {"__trunc__", (PyCFunction)int_int, METH_NOARGS,
1323 "Truncating an Integral returns itself."},
1324 {"__getnewargs__", (PyCFunction)int_getnewargs, METH_NOARGS},
1325 {"__format__", (PyCFunction)int__format__, METH_VARARGS},
1326 {NULL, NULL} /* sentinel */
1327 };
1328
1329 static PyGetSetDef int_getset[] = {
1330 {"real",
1331 (getter)int_int, (setter)NULL,
1332 "the real part of a complex number",
1333 NULL},
1334 {"imag",
1335 (getter)int_get0, (setter)NULL,
1336 "the imaginary part of a complex number",
1337 NULL},
1338 {"numerator",
1339 (getter)int_int, (setter)NULL,
1340 "the numerator of a rational number in lowest terms",
1341 NULL},
1342 {"denominator",
1343 (getter)int_get1, (setter)NULL,
1344 "the denominator of a rational number in lowest terms",
1345 NULL},
1346 {NULL} /* Sentinel */
1347 };
1348
1349 PyDoc_STRVAR(int_doc,
1350 "int(x=0) -> int or long\n\
1351 int(x, base=10) -> int or long\n\
1352 \n\
1353 Convert a number or string to an integer, or return 0 if no arguments\n\
1354 are given. If x is floating point, the conversion truncates towards zero.\n\
1355 If x is outside the integer range, the function returns a long instead.\n\
1356 \n\
1357 If x is not a number or if base is given, then x must be a string or\n\
1358 Unicode object representing an integer literal in the given base. The\n\
1359 literal can be preceded by '+' or '-' and be surrounded by whitespace.\n\
1360 The base defaults to 10. Valid bases are 0 and 2-36. Base 0 means to\n\
1361 interpret the base from the string as an integer literal.\n\
1362 >>> int('0b100', base=0)\n\
1363 4");
1364
1365 static PyNumberMethods int_as_number = {
1366 (binaryfunc)int_add, /*nb_add*/
1367 (binaryfunc)int_sub, /*nb_subtract*/
1368 (binaryfunc)int_mul, /*nb_multiply*/
1369 (binaryfunc)int_classic_div, /*nb_divide*/
1370 (binaryfunc)int_mod, /*nb_remainder*/
1371 (binaryfunc)int_divmod, /*nb_divmod*/
1372 (ternaryfunc)int_pow, /*nb_power*/
1373 (unaryfunc)int_neg, /*nb_negative*/
1374 (unaryfunc)int_int, /*nb_positive*/
1375 (unaryfunc)int_abs, /*nb_absolute*/
1376 (inquiry)int_nonzero, /*nb_nonzero*/
1377 (unaryfunc)int_invert, /*nb_invert*/
1378 (binaryfunc)int_lshift, /*nb_lshift*/
1379 (binaryfunc)int_rshift, /*nb_rshift*/
1380 (binaryfunc)int_and, /*nb_and*/
1381 (binaryfunc)int_xor, /*nb_xor*/
1382 (binaryfunc)int_or, /*nb_or*/
1383 int_coerce, /*nb_coerce*/
1384 (unaryfunc)int_int, /*nb_int*/
1385 (unaryfunc)int_long, /*nb_long*/
1386 (unaryfunc)int_float, /*nb_float*/
1387 (unaryfunc)int_oct, /*nb_oct*/
1388 (unaryfunc)int_hex, /*nb_hex*/
1389 0, /*nb_inplace_add*/
1390 0, /*nb_inplace_subtract*/
1391 0, /*nb_inplace_multiply*/
1392 0, /*nb_inplace_divide*/
1393 0, /*nb_inplace_remainder*/
1394 0, /*nb_inplace_power*/
1395 0, /*nb_inplace_lshift*/
1396 0, /*nb_inplace_rshift*/
1397 0, /*nb_inplace_and*/
1398 0, /*nb_inplace_xor*/
1399 0, /*nb_inplace_or*/
1400 (binaryfunc)int_div, /* nb_floor_divide */
1401 (binaryfunc)int_true_divide, /* nb_true_divide */
1402 0, /* nb_inplace_floor_divide */
1403 0, /* nb_inplace_true_divide */
1404 (unaryfunc)int_int, /* nb_index */
1405 };
1406
1407 PyTypeObject PyInt_Type = {
1408 PyVarObject_HEAD_INIT(&PyType_Type, 0)
1409 "int",
1410 sizeof(PyIntObject),
1411 0,
1412 (destructor)int_dealloc, /* tp_dealloc */
1413 (printfunc)int_print, /* tp_print */
1414 0, /* tp_getattr */
1415 0, /* tp_setattr */
1416 (cmpfunc)int_compare, /* tp_compare */
1417 (reprfunc)int_to_decimal_string, /* tp_repr */
1418 &int_as_number, /* tp_as_number */
1419 0, /* tp_as_sequence */
1420 0, /* tp_as_mapping */
1421 (hashfunc)int_hash, /* tp_hash */
1422 0, /* tp_call */
1423 (reprfunc)int_to_decimal_string, /* tp_str */
1424 PyObject_GenericGetAttr, /* tp_getattro */
1425 0, /* tp_setattro */
1426 0, /* tp_as_buffer */
1427 Py_TPFLAGS_DEFAULT | Py_TPFLAGS_CHECKTYPES |
1428 Py_TPFLAGS_BASETYPE | Py_TPFLAGS_INT_SUBCLASS, /* tp_flags */
1429 int_doc, /* tp_doc */
1430 0, /* tp_traverse */
1431 0, /* tp_clear */
1432 0, /* tp_richcompare */
1433 0, /* tp_weaklistoffset */
1434 0, /* tp_iter */
1435 0, /* tp_iternext */
1436 int_methods, /* tp_methods */
1437 0, /* tp_members */
1438 int_getset, /* tp_getset */
1439 0, /* tp_base */
1440 0, /* tp_dict */
1441 0, /* tp_descr_get */
1442 0, /* tp_descr_set */
1443 0, /* tp_dictoffset */
1444 0, /* tp_init */
1445 0, /* tp_alloc */
1446 int_new, /* tp_new */
1447 };
1448
1449 int
_PyInt_Init(void)1450 _PyInt_Init(void)
1451 {
1452 PyIntObject *v;
1453 int ival;
1454 #if NSMALLNEGINTS + NSMALLPOSINTS > 0
1455 for (ival = -NSMALLNEGINTS; ival < NSMALLPOSINTS; ival++) {
1456 if (!free_list && (free_list = fill_free_list()) == NULL)
1457 return 0;
1458 /* PyObject_New is inlined */
1459 v = free_list;
1460 free_list = (PyIntObject *)Py_TYPE(v);
1461 (void)PyObject_INIT(v, &PyInt_Type);
1462 v->ob_ival = ival;
1463 small_ints[ival + NSMALLNEGINTS] = v;
1464 }
1465 #endif
1466 return 1;
1467 }
1468
1469 int
PyInt_ClearFreeList(void)1470 PyInt_ClearFreeList(void)
1471 {
1472 PyIntObject *p;
1473 PyIntBlock *list, *next;
1474 int i;
1475 int u; /* remaining unfreed ints per block */
1476 int freelist_size = 0;
1477
1478 list = block_list;
1479 block_list = NULL;
1480 free_list = NULL;
1481 while (list != NULL) {
1482 u = 0;
1483 for (i = 0, p = &list->objects[0];
1484 i < N_INTOBJECTS;
1485 i++, p++) {
1486 if (PyInt_CheckExact(p) && p->ob_refcnt != 0)
1487 u++;
1488 }
1489 next = list->next;
1490 if (u) {
1491 list->next = block_list;
1492 block_list = list;
1493 for (i = 0, p = &list->objects[0];
1494 i < N_INTOBJECTS;
1495 i++, p++) {
1496 if (!PyInt_CheckExact(p) ||
1497 p->ob_refcnt == 0) {
1498 Py_TYPE(p) = (struct _typeobject *)
1499 free_list;
1500 free_list = p;
1501 }
1502 #if NSMALLNEGINTS + NSMALLPOSINTS > 0
1503 else if (-NSMALLNEGINTS <= p->ob_ival &&
1504 p->ob_ival < NSMALLPOSINTS &&
1505 small_ints[p->ob_ival +
1506 NSMALLNEGINTS] == NULL) {
1507 Py_INCREF(p);
1508 small_ints[p->ob_ival +
1509 NSMALLNEGINTS] = p;
1510 }
1511 #endif
1512 }
1513 }
1514 else {
1515 PyMem_FREE(list);
1516 }
1517 freelist_size += u;
1518 list = next;
1519 }
1520
1521 return freelist_size;
1522 }
1523
1524 void
PyInt_Fini(void)1525 PyInt_Fini(void)
1526 {
1527 PyIntObject *p;
1528 PyIntBlock *list;
1529 int i;
1530 int u; /* total unfreed ints per block */
1531
1532 #if NSMALLNEGINTS + NSMALLPOSINTS > 0
1533 PyIntObject **q;
1534
1535 i = NSMALLNEGINTS + NSMALLPOSINTS;
1536 q = small_ints;
1537 while (--i >= 0) {
1538 Py_XDECREF(*q);
1539 *q++ = NULL;
1540 }
1541 #endif
1542 u = PyInt_ClearFreeList();
1543 if (!Py_VerboseFlag)
1544 return;
1545 fprintf(stderr, "# cleanup ints");
1546 if (!u) {
1547 fprintf(stderr, "\n");
1548 }
1549 else {
1550 fprintf(stderr,
1551 ": %d unfreed int%s\n",
1552 u, u == 1 ? "" : "s");
1553 }
1554 if (Py_VerboseFlag > 1) {
1555 list = block_list;
1556 while (list != NULL) {
1557 for (i = 0, p = &list->objects[0];
1558 i < N_INTOBJECTS;
1559 i++, p++) {
1560 if (PyInt_CheckExact(p) && p->ob_refcnt != 0)
1561 /* XXX(twouters) cast refcount to
1562 long until %zd is universally
1563 available
1564 */
1565 fprintf(stderr,
1566 "# <int at %p, refcnt=%ld, val=%ld>\n",
1567 p, (long)p->ob_refcnt,
1568 p->ob_ival);
1569 }
1570 list = list->next;
1571 }
1572 }
1573 }
1574