• Home
  • Line#
  • Scopes#
  • Navigate#
  • Raw
  • Download
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