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