ยปCore Development>Code coverage>Objects/intobject.c

Python code coverage for Objects/intobject.c

#countcontent
1n/a
2n/a/* Integer object implementation */
3n/a
4n/a#include "Python.h"
5n/a#include <ctype.h>
6n/a#include <float.h>
7n/a
8n/astatic PyObject *int_int(PyIntObject *v);
9n/a
10n/along
11n/aPyInt_GetMax(void)
12318{
13318 return LONG_MAX; /* To initialize sys.maxint */
14n/a}
15n/a
16n/a/* Integers are quite normal objects, to make object handling uniform.
17n/a (Using odd pointers to represent integers would save much space
18n/a but require extra checks for this special case throughout the code.)
19n/a Since a typical Python program spends much of its time allocating
20n/a and deallocating integers, these operations should be very fast.
21n/a Therefore we use a dedicated allocation scheme with a much lower
22n/a overhead (in space and time) than straight malloc(): a simple
23n/a dedicated free list, filled when necessary with memory from malloc().
24n/a
25n/a block_list is a singly-linked list of all PyIntBlocks ever allocated,
26n/a linked via their next members. PyIntBlocks are never returned to the
27n/a system before shutdown (PyInt_Fini).
28n/a
29n/a free_list is a singly-linked list of available PyIntObjects, linked
30n/a via abuse of their ob_type members.
31n/a*/
32n/a
33n/a#define BLOCK_SIZE 1000 /* 1K less typical malloc overhead */
34n/a#define BHEAD_SIZE 8 /* Enough for a 64-bit pointer */
35n/a#define N_INTOBJECTS ((BLOCK_SIZE - BHEAD_SIZE) / sizeof(PyIntObject))
36n/a
37n/astruct _intblock {
38n/a struct _intblock *next;
39n/a PyIntObject objects[N_INTOBJECTS];
40n/a};
41n/a
42n/atypedef struct _intblock PyIntBlock;
43n/a
44n/astatic PyIntBlock *block_list = NULL;
45n/astatic PyIntObject *free_list = NULL;
46n/a
47n/astatic PyIntObject *
48n/afill_free_list(void)
49134641{
50n/a PyIntObject *p, *q;
51n/a /* Python's object allocator isn't appropriate for large blocks. */
52134641 p = (PyIntObject *) PyMem_MALLOC(sizeof(PyIntBlock));
53134641 if (p == NULL)
540 return (PyIntObject *) PyErr_NoMemory();
55134641 ((PyIntBlock *)p)->next = block_list;
56134641 block_list = (PyIntBlock *)p;
57n/a /* Link the int objects together, from rear to front, then return
58n/a the address of the last int object in the block. */
59134641 p = &((PyIntBlock *)p)->objects[0];
60134641 q = p + N_INTOBJECTS;
613366025 while (--q > p)
623096743 Py_TYPE(q) = (struct _typeobject *)(q-1);
63134641 Py_TYPE(q) = NULL;
64134641 return p + N_INTOBJECTS - 1;
65n/a}
66n/a
67n/a#ifndef NSMALLPOSINTS
68n/a#define NSMALLPOSINTS 257
69n/a#endif
70n/a#ifndef NSMALLNEGINTS
71n/a#define NSMALLNEGINTS 5
72n/a#endif
73n/a#if NSMALLNEGINTS + NSMALLPOSINTS > 0
74n/a/* References to small integers are saved in this array so that they
75n/a can be shared.
76n/a The integers that are saved are those in the range
77n/a -NSMALLNEGINTS (inclusive) to NSMALLPOSINTS (not inclusive).
78n/a*/
79n/astatic PyIntObject *small_ints[NSMALLNEGINTS + NSMALLPOSINTS];
80n/a#endif
81n/a#ifdef COUNT_ALLOCS
82n/aPy_ssize_t quick_int_allocs;
83n/aPy_ssize_t quick_neg_int_allocs;
84n/a#endif
85n/a
86n/aPyObject *
87n/aPyInt_FromLong(long ival)
881005439293{
89n/a register PyIntObject *v;
90n/a#if NSMALLNEGINTS + NSMALLPOSINTS > 0
911005439293 if (-NSMALLNEGINTS <= ival && ival < NSMALLPOSINTS) {
92488688887 v = small_ints[ival + NSMALLNEGINTS];
93488688887 Py_INCREF(v);
94n/a#ifdef COUNT_ALLOCS
95n/a if (ival >= 0)
96n/a quick_int_allocs++;
97n/a else
98n/a quick_neg_int_allocs++;
99n/a#endif
100488688887 return (PyObject *) v;
101n/a }
102n/a#endif
103516750406 if (free_list == NULL) {
104131418 if ((free_list = fill_free_list()) == NULL)
1050 return NULL;
106n/a }
107n/a /* Inline PyObject_New */
108516750406 v = free_list;
109516750406 free_list = (PyIntObject *)Py_TYPE(v);
110516750406 PyObject_INIT(v, &PyInt_Type);
111516750406 v->ob_ival = ival;
112516750406 return (PyObject *) v;
113n/a}
114n/a
115n/aPyObject *
116n/aPyInt_FromSize_t(size_t ival)
117199{
118199 if (ival <= LONG_MAX)
119199 return PyInt_FromLong((long)ival);
1200 return _PyLong_FromSize_t(ival);
121n/a}
122n/a
123n/aPyObject *
124n/aPyInt_FromSsize_t(Py_ssize_t ival)
125200708595{
126n/a if (ival >= LONG_MIN && ival <= LONG_MAX)
127200708595 return PyInt_FromLong((long)ival);
128n/a return _PyLong_FromSsize_t(ival);
129n/a}
130n/a
131n/astatic void
132n/aint_dealloc(PyIntObject *v)
133516570063{
134516570063 if (PyInt_CheckExact(v)) {
135516529818 Py_TYPE(v) = (struct _typeobject *)free_list;
136516529818 free_list = v;
137n/a }
138n/a else
13940245 Py_TYPE(v)->tp_free((PyObject *)v);
140516570063}
141n/a
142n/astatic void
143n/aint_free(PyIntObject *v)
1440{
1450 Py_TYPE(v) = (struct _typeobject *)free_list;
1460 free_list = v;
1470}
148n/a
149n/along
150n/aPyInt_AsLong(register PyObject *op)
15127519985{
152n/a PyNumberMethods *nb;
153n/a PyIntObject *io;
154n/a long val;
155n/a
15627519985 if (op && PyInt_Check(op))
15727316499 return PyInt_AS_LONG((PyIntObject*) op);
158n/a
159203486 if (op == NULL || (nb = Py_TYPE(op)->tp_as_number) == NULL ||
160n/a nb->nb_int == NULL) {
161142 PyErr_SetString(PyExc_TypeError, "an integer is required");
162142 return -1;
163n/a }
164n/a
165203344 io = (PyIntObject*) (*nb->nb_int) (op);
166203344 if (io == NULL)
1671 return -1;
168203343 if (!PyInt_Check(io)) {
16915343 if (PyLong_Check(io)) {
170n/a /* got a long? => retry int conversion */
17115342 val = PyLong_AsLong((PyObject *)io);
17215342 Py_DECREF(io);
17315342 if ((val == -1) && PyErr_Occurred())
17415337 return -1;
1755 return val;
176n/a }
177n/a else
178n/a {
1791 Py_DECREF(io);
1801 PyErr_SetString(PyExc_TypeError,
181n/a "__int__ method should return an integer");
1821 return -1;
183n/a }
184n/a }
185n/a
186188000 val = PyInt_AS_LONG(io);
187188000 Py_DECREF(io);
188n/a
189188000 return val;
190n/a}
191n/a
192n/aPy_ssize_t
193n/aPyInt_AsSsize_t(register PyObject *op)
19498909717{
195n/a#if SIZEOF_SIZE_T != SIZEOF_LONG
196n/a PyNumberMethods *nb;
197n/a PyIntObject *io;
198n/a Py_ssize_t val;
199n/a#endif
200n/a
20198909717 if (op == NULL) {
2020 PyErr_SetString(PyExc_TypeError, "an integer is required");
2030 return -1;
204n/a }
205n/a
20698909717 if (PyInt_Check(op))
20798727072 return PyInt_AS_LONG((PyIntObject*) op);
208182645 if (PyLong_Check(op))
209182632 return _PyLong_AsSsize_t(op);
210n/a#if SIZEOF_SIZE_T == SIZEOF_LONG
21113 return PyInt_AsLong(op);
212n/a#else
213n/a
214n/a if ((nb = Py_TYPE(op)->tp_as_number) == NULL ||
215n/a (nb->nb_int == NULL && nb->nb_long == 0)) {
216n/a PyErr_SetString(PyExc_TypeError, "an integer is required");
217n/a return -1;
218n/a }
219n/a
220n/a if (nb->nb_long != 0)
221n/a io = (PyIntObject*) (*nb->nb_long) (op);
222n/a else
223n/a io = (PyIntObject*) (*nb->nb_int) (op);
224n/a if (io == NULL)
225n/a return -1;
226n/a if (!PyInt_Check(io)) {
227n/a if (PyLong_Check(io)) {
228n/a /* got a long? => retry int conversion */
229n/a val = _PyLong_AsSsize_t((PyObject *)io);
230n/a Py_DECREF(io);
231n/a if ((val == -1) && PyErr_Occurred())
232n/a return -1;
233n/a return val;
234n/a }
235n/a else
236n/a {
237n/a Py_DECREF(io);
238n/a PyErr_SetString(PyExc_TypeError,
239n/a "__int__ method should return an integer");
240n/a return -1;
241n/a }
242n/a }
243n/a
244n/a val = PyInt_AS_LONG(io);
245n/a Py_DECREF(io);
246n/a
247n/a return val;
248n/a#endif
249n/a}
250n/a
251n/aunsigned long
252n/aPyInt_AsUnsignedLongMask(register PyObject *op)
253181878{
254n/a PyNumberMethods *nb;
255n/a PyIntObject *io;
256n/a unsigned long val;
257n/a
258181878 if (op && PyInt_Check(op))
259180441 return PyInt_AS_LONG((PyIntObject*) op);
2601437 if (op && PyLong_Check(op))
2611362 return PyLong_AsUnsignedLongMask(op);
262n/a
26375 if (op == NULL || (nb = Py_TYPE(op)->tp_as_number) == NULL ||
264n/a nb->nb_int == NULL) {
26558 PyErr_SetString(PyExc_TypeError, "an integer is required");
26658 return (unsigned long)-1;
267n/a }
268n/a
26917 io = (PyIntObject*) (*nb->nb_int) (op);
27017 if (io == NULL)
2710 return (unsigned long)-1;
27217 if (!PyInt_Check(io)) {
2733 if (PyLong_Check(io)) {
2743 val = PyLong_AsUnsignedLongMask((PyObject *)io);
2753 Py_DECREF(io);
2763 if (PyErr_Occurred())
2770 return (unsigned long)-1;
2783 return val;
279n/a }
280n/a else
281n/a {
2820 Py_DECREF(io);
2830 PyErr_SetString(PyExc_TypeError,
284n/a "__int__ method should return an integer");
2850 return (unsigned long)-1;
286n/a }
287n/a }
288n/a
28914 val = PyInt_AS_LONG(io);
29014 Py_DECREF(io);
291n/a
29214 return val;
293n/a}
294n/a
295n/a#ifdef HAVE_LONG_LONG
296n/aunsigned PY_LONG_LONG
297n/aPyInt_AsUnsignedLongLongMask(register PyObject *op)
2980{
299n/a PyNumberMethods *nb;
300n/a PyIntObject *io;
301n/a unsigned PY_LONG_LONG val;
302n/a
3030 if (op && PyInt_Check(op))
3040 return PyInt_AS_LONG((PyIntObject*) op);
3050 if (op && PyLong_Check(op))
3060 return PyLong_AsUnsignedLongLongMask(op);
307n/a
3080 if (op == NULL || (nb = Py_TYPE(op)->tp_as_number) == NULL ||
309n/a nb->nb_int == NULL) {
3100 PyErr_SetString(PyExc_TypeError, "an integer is required");
3110 return (unsigned PY_LONG_LONG)-1;
312n/a }
313n/a
3140 io = (PyIntObject*) (*nb->nb_int) (op);
3150 if (io == NULL)
3160 return (unsigned PY_LONG_LONG)-1;
3170 if (!PyInt_Check(io)) {
3180 if (PyLong_Check(io)) {
3190 val = PyLong_AsUnsignedLongLongMask((PyObject *)io);
3200 Py_DECREF(io);
3210 if (PyErr_Occurred())
3220 return (unsigned PY_LONG_LONG)-1;
3230 return val;
324n/a }
325n/a else
326n/a {
3270 Py_DECREF(io);
3280 PyErr_SetString(PyExc_TypeError,
329n/a "__int__ method should return an integer");
3300 return (unsigned PY_LONG_LONG)-1;
331n/a }
332n/a }
333n/a
3340 val = PyInt_AS_LONG(io);
3350 Py_DECREF(io);
336n/a
3370 return val;
338n/a}
339n/a#endif
340n/a
341n/aPyObject *
342n/aPyInt_FromString(char *s, char **pend, int base)
3431174310{
344n/a char *end;
345n/a long x;
346n/a Py_ssize_t slen;
347n/a PyObject *sobj, *srepr;
348n/a
3491174310 if ((base != 0 && base < 2) || base > 36) {
3501 PyErr_SetString(PyExc_ValueError,
351n/a "int() base must be >= 2 and <= 36");
3521 return NULL;
353n/a }
354n/a
3552355106 while (*s && isspace(Py_CHARMASK(*s)))
3566488 s++;
3571174309 errno = 0;
3581174325 if (base == 0 && s[0] == '0') {
35916 x = (long) PyOS_strtoul(s, &end, base);
36016 if (x < 0)
3610 return PyLong_FromString(s, pend, base);
362n/a }
363n/a else
3641174293 x = PyOS_strtol(s, &end, base);
3651174309 if (end == s || !isalnum(Py_CHARMASK(end[-1])))
366n/a goto bad;
3672294303 while (*end && isspace(Py_CHARMASK(*end)))
36835483 end++;
3691129410 if (*end != '\0') {
37045428 bad:
37145428 slen = strlen(s) < 200 ? strlen(s) : 200;
37245428 sobj = PyString_FromStringAndSize(s, slen);
37345428 if (sobj == NULL)
3740 return NULL;
37545428 srepr = PyObject_Repr(sobj);
37645428 Py_DECREF(sobj);
37745428 if (srepr == NULL)
3780 return NULL;
37945428 PyErr_Format(PyExc_ValueError,
380n/a "invalid literal for int() with base %d: %s",
381n/a base, PyString_AS_STRING(srepr));
38245428 Py_DECREF(srepr);
38345428 return NULL;
384n/a }
3851128881 else if (errno != 0)
38628557 return PyLong_FromString(s, pend, base);
3871100324 if (pend)
388629087 *pend = end;
3891100324 return PyInt_FromLong(x);
390n/a}
391n/a
392n/a#ifdef Py_USING_UNICODE
393n/aPyObject *
394n/aPyInt_FromUnicode(Py_UNICODE *s, Py_ssize_t length, int base)
395700{
396n/a PyObject *result;
397700 char *buffer = (char *)PyMem_MALLOC(length+1);
398n/a
399700 if (buffer == NULL)
4000 return PyErr_NoMemory();
401n/a
402700 if (PyUnicode_EncodeDecimal(s, length, buffer, NULL)) {
40313 PyMem_FREE(buffer);
40413 return NULL;
405n/a }
406687 result = PyInt_FromString(buffer, NULL, base);
407687 PyMem_FREE(buffer);
408687 return result;
409n/a}
410n/a#endif
411n/a
412n/a/* Methods */
413n/a
414n/a/* Integers are seen as the "smallest" of all numeric types and thus
415n/a don't have any knowledge about conversion of other types to
416n/a integers. */
417n/a
418n/a#define CONVERT_TO_LONG(obj, lng) \
419n/a if (PyInt_Check(obj)) { \
420n/a lng = PyInt_AS_LONG(obj); \
421n/a } \
422n/a else { \
423n/a Py_INCREF(Py_NotImplemented); \
424n/a return Py_NotImplemented; \
425n/a }
426n/a
427n/a/* ARGSUSED */
428n/astatic int
429n/aint_print(PyIntObject *v, FILE *fp, int flags)
430n/a /* flags -- not used but required by interface */
431639{
432639 long int_val = v->ob_ival;
433639 Py_BEGIN_ALLOW_THREADS
434639 fprintf(fp, "%ld", int_val);
435639 Py_END_ALLOW_THREADS
436639 return 0;
437n/a}
438n/a
439n/astatic int
440n/aint_compare(PyIntObject *v, PyIntObject *w)
441389097386{
442389097386 register long i = v->ob_ival;
443389097386 register long j = w->ob_ival;
444389097386 return (i < j) ? -1 : (i > j) ? 1 : 0;
445n/a}
446n/a
447n/astatic long
448n/aint_hash(PyIntObject *v)
449620795085{
450n/a /* XXX If this is changed, you also need to change the way
451n/a Python's long, float and complex types are hashed. */
452620795085 long x = v -> ob_ival;
453620795085 if (x == -1)
45442808 x = -2;
455620795085 return x;
456n/a}
457n/a
458n/astatic PyObject *
459n/aint_add(PyIntObject *v, PyIntObject *w)
460683174{
461n/a register long a, b, x;
462683277 CONVERT_TO_LONG(v, a);
4631366142 CONVERT_TO_LONG(w, b);
464n/a /* casts in the line below avoid undefined behaviour on overflow */
465104393 x = (long)((unsigned long)a + b);
466104822 if ((x^a) >= 0 || (x^b) >= 0)
467104264 return PyInt_FromLong(x);
468129 return PyLong_Type.tp_as_number->nb_add((PyObject *)v, (PyObject *)w);
469n/a}
470n/a
471n/astatic PyObject *
472n/aint_sub(PyIntObject *v, PyIntObject *w)
47349471{
474n/a register long a, b, x;
47549502 CONVERT_TO_LONG(v, a);
47698880 CONVERT_TO_LONG(w, b);
477n/a /* casts in the line below avoid undefined behaviour on overflow */
4786699 x = (long)((unsigned long)a - b);
4797042 if ((x^a) >= 0 || (x^~b) >= 0)
4806630 return PyInt_FromLong(x);
48169 return PyLong_Type.tp_as_number->nb_subtract((PyObject *)v,
482n/a (PyObject *)w);
483n/a}
484n/a
485n/a/*
486n/aInteger overflow checking for * is painful: Python tried a couple ways, but
487n/athey didn't work on all platforms, or failed in endcases (a product of
488n/a-sys.maxint-1 has been a particular pain).
489n/a
490n/aHere's another way:
491n/a
492n/aThe native long product x*y is either exactly right or *way* off, being
493n/ajust the last n bits of the true product, where n is the number of bits
494n/ain a long (the delivered product is the true product plus i*2**n for
495n/asome integer i).
496n/a
497n/aThe native double product (double)x * (double)y is subject to three
498n/arounding errors: on a sizeof(long)==8 box, each cast to double can lose
499n/ainfo, and even on a sizeof(long)==4 box, the multiplication can lose info.
500n/aBut, unlike the native long product, it's not in *range* trouble: even
501n/aif sizeof(long)==32 (256-bit longs), the product easily fits in the
502n/adynamic range of a double. So the leading 50 (or so) bits of the double
503n/aproduct are correct.
504n/a
505n/aWe check these two ways against each other, and declare victory if they're
506n/aapproximately the same. Else, because the native long product is the only
507n/aone that can lose catastrophic amounts of information, it's the native long
508n/aproduct that must have overflowed.
509n/a*/
510n/a
511n/astatic PyObject *
512n/aint_mul(PyObject *v, PyObject *w)
5131884817{
514n/a long a, b;
515n/a long longprod; /* a*b in native long arithmetic */
516n/a double doubled_longprod; /* (double)longprod */
517n/a double doubleprod; /* (double)a * (double)b */
518n/a
5192183294 CONVERT_TO_LONG(v, a);
5203172680 CONVERT_TO_LONG(w, b);
521n/a /* casts in the next line avoid undefined behaviour on overflow */
5221181558 longprod = (long)((unsigned long)a * b);
5231181558 doubleprod = (double)a * (double)b;
5241181558 doubled_longprod = (double)longprod;
525n/a
526n/a /* Fast path for normal case: small multiplicands, and no info
527n/a is lost in either method. */
5281181558 if (doubled_longprod == doubleprod)
5291175247 return PyInt_FromLong(longprod);
530n/a
531n/a /* Somebody somewhere lost info. Close enough, or way off? Note
532n/a that a != 0 and b != 0 (else doubled_longprod == doubleprod == 0).
533n/a The difference either is or isn't significant compared to the
534n/a true value (of which doubleprod is a good approximation).
535n/a */
536n/a {
5376311 const double diff = doubled_longprod - doubleprod;
5386311 const double absdiff = diff >= 0.0 ? diff : -diff;
539n/a const double absprod = doubleprod >= 0.0 ? doubleprod :
5406311 -doubleprod;
541n/a /* absdiff/absprod <= 1/32 iff
542n/a 32 * absdiff <= absprod -- 5 good bits is "close enough" */
5436311 if (32.0 * absdiff <= absprod)
544231 return PyInt_FromLong(longprod);
545n/a else
5466080 return PyLong_Type.tp_as_number->nb_multiply(v, w);
547n/a }
548n/a}
549n/a
550n/a/* Integer overflow checking for unary negation: on a 2's-complement
551n/a * box, -x overflows iff x is the most negative long. In this case we
552n/a * get -x == x. However, -x is undefined (by C) if x /is/ the most
553n/a * negative long (it's a signed overflow case), and some compilers care.
554n/a * So we cast x to unsigned long first. However, then other compilers
555n/a * warn about applying unary minus to an unsigned operand. Hence the
556n/a * weird "0-".
557n/a */
558n/a#define UNARY_NEG_WOULD_OVERFLOW(x) \
559n/a ((x) < 0 && (unsigned long)(x) == 0-(unsigned long)(x))
560n/a
561n/a/* Return type of i_divmod */
562n/aenum divmod_result {
563n/a DIVMOD_OK, /* Correct result */
564n/a DIVMOD_OVERFLOW, /* Overflow, try again using longs */
565n/a DIVMOD_ERROR /* Exception raised */
566n/a};
567n/a
568n/astatic enum divmod_result
569n/ai_divmod(register long x, register long y,
570n/a long *p_xdivy, long *p_xmody)
5711340651{
572n/a long xdivy, xmody;
573n/a
5741340651 if (y == 0) {
5751327 PyErr_SetString(PyExc_ZeroDivisionError,
576n/a "integer division or modulo by zero");
5771327 return DIVMOD_ERROR;
578n/a }
579n/a /* (-sys.maxint-1)/-1 is the only overflow case. */
5801339324 if (y == -1 && UNARY_NEG_WOULD_OVERFLOW(x))
5811 return DIVMOD_OVERFLOW;
5821339323 xdivy = x / y;
583n/a /* xdiv*y can overflow on platforms where x/y gives floor(x/y)
584n/a * for x and y with differing signs. (This is unusual
585n/a * behaviour, and C99 prohibits it, but it's allowed by C89;
586n/a * for an example of overflow, take x = LONG_MIN, y = 5 or x =
587n/a * LONG_MAX, y = -5.) However, x - xdivy*y is always
588n/a * representable as a long, since it lies strictly between
589n/a * -abs(y) and abs(y). We add casts to avoid intermediate
590n/a * overflow.
591n/a */
5921339323 xmody = (long)(x - (unsigned long)xdivy * y);
593n/a /* If the signs of x and y differ, and the remainder is non-0,
594n/a * C89 doesn't define whether xdivy is now the floor or the
595n/a * ceiling of the infinitely precise quotient. We want the floor,
596n/a * and we have it iff the remainder's sign matches y's.
597n/a */
5981339323 if (xmody && ((y ^ xmody) < 0) /* i.e. and signs differ */) {
59929785 xmody += y;
60029785 --xdivy;
60129785 assert(xmody && ((y ^ xmody) >= 0));
602n/a }
6031339323 *p_xdivy = xdivy;
6041339323 *p_xmody = xmody;
6051339323 return DIVMOD_OK;
606n/a}
607n/a
608n/astatic PyObject *
609n/aint_div(PyIntObject *x, PyIntObject *y)
610195590{
611n/a long xi, yi;
612n/a long d, m;
613195610 CONVERT_TO_LONG(x, xi);
614391140 CONVERT_TO_LONG(y, yi);
615194545 switch (i_divmod(xi, yi, &d, &m)) {
616n/a case DIVMOD_OK:
617193223 return PyInt_FromLong(d);
618n/a case DIVMOD_OVERFLOW:
6190 return PyLong_Type.tp_as_number->nb_divide((PyObject *)x,
620n/a (PyObject *)y);
621n/a default:
6221322 return NULL;
623n/a }
624n/a}
625n/a
626n/astatic PyObject *
627n/aint_classic_div(PyIntObject *x, PyIntObject *y)
6289238{
629n/a long xi, yi;
630n/a long d, m;
6319262 CONVERT_TO_LONG(x, xi);
63218428 CONVERT_TO_LONG(y, yi);
6331438 if (Py_DivisionWarningFlag &&
634n/a PyErr_Warn(PyExc_DeprecationWarning, "classic int division") < 0)
6350 return NULL;
6361438 switch (i_divmod(xi, yi, &d, &m)) {
637n/a case DIVMOD_OK:
6381433 return PyInt_FromLong(d);
639n/a case DIVMOD_OVERFLOW:
6400 return PyLong_Type.tp_as_number->nb_divide((PyObject *)x,
641n/a (PyObject *)y);
642n/a default:
6435 return NULL;
644n/a }
645n/a}
646n/a
647n/astatic PyObject *
648n/aint_true_divide(PyIntObject *x, PyIntObject *y)
64979006{
650n/a long xi, yi;
651n/a /* If they aren't both ints, give someone else a chance. In
652n/a particular, this lets int/long get handled by longs, which
653n/a underflows to 0 gracefully if the long is too big to convert
654n/a to float. */
65579008 CONVERT_TO_LONG(x, xi);
656158008 CONVERT_TO_LONG(y, yi);
65746 if (yi == 0) {
6580 PyErr_SetString(PyExc_ZeroDivisionError,
659n/a "division by zero");
6600 return NULL;
661n/a }
66246 if (xi == 0)
6630 return PyFloat_FromDouble(yi < 0 ? -0.0 : 0.0);
664n/a
665n/a#define WIDTH_OF_ULONG (CHAR_BIT*SIZEOF_LONG)
666n/a#if DBL_MANT_DIG < WIDTH_OF_ULONG
66746 if ((xi >= 0 ? 0UL + xi : 0UL - xi) >> DBL_MANT_DIG ||
668n/a (yi >= 0 ? 0UL + yi : 0UL - yi) >> DBL_MANT_DIG)
669n/a /* Large x or y. Use long integer arithmetic. */
6700 return PyLong_Type.tp_as_number->nb_true_divide(
671n/a (PyObject *)x, (PyObject *)y);
672n/a else
673n/a#endif
674n/a /* Both ints can be exactly represented as doubles. Do a
675n/a floating-point division. */
67646 return PyFloat_FromDouble((double)xi / (double)yi);
677n/a}
678n/a
679n/astatic PyObject *
680n/aint_mod(PyIntObject *x, PyIntObject *y)
681498840{
682n/a long xi, yi;
683n/a long d, m;
684498865 CONVERT_TO_LONG(x, xi);
685997630 CONVERT_TO_LONG(y, yi);
686497402 switch (i_divmod(xi, yi, &d, &m)) {
687n/a case DIVMOD_OK:
688497402 return PyInt_FromLong(m);
689n/a case DIVMOD_OVERFLOW:
6900 return PyLong_Type.tp_as_number->nb_remainder((PyObject *)x,
691n/a (PyObject *)y);
692n/a default:
6930 return NULL;
694n/a }
695n/a}
696n/a
697n/astatic PyObject *
698n/aint_divmod(PyIntObject *x, PyIntObject *y)
699612183{
700n/a long xi, yi;
701n/a long d, m;
702612193 CONVERT_TO_LONG(x, xi);
7031224346 CONVERT_TO_LONG(y, yi);
704608572 switch (i_divmod(xi, yi, &d, &m)) {
705n/a case DIVMOD_OK:
706608571 return Py_BuildValue("(ll)", d, m);
707n/a case DIVMOD_OVERFLOW:
7081 return PyLong_Type.tp_as_number->nb_divmod((PyObject *)x,
709n/a (PyObject *)y);
710n/a default:
7110 return NULL;
712n/a }
713n/a}
714n/a
715n/astatic PyObject *
716n/aint_pow(PyIntObject *v, PyIntObject *w, PyIntObject *z)
717973051{
718973051 register long iv, iw, iz=0, ix, temp, prev;
719973073 CONVERT_TO_LONG(v, iv);
7201946058 CONVERT_TO_LONG(w, iw);
721971022 if (iw < 0) {
7225293 if ((PyObject *)z != Py_None) {
7231 PyErr_SetString(PyExc_TypeError, "pow() 2nd argument "
724n/a "cannot be negative when 3rd argument specified");
7251 return NULL;
726n/a }
727n/a /* Return a float. This works because we know that
728n/a this calls float_pow() which converts its
729n/a arguments to double. */
7305292 return PyFloat_Type.tp_as_number->nb_power(
731n/a (PyObject *)v, (PyObject *)w, (PyObject *)z);
732n/a }
733965729 if ((PyObject *)z != Py_None) {
73439665 CONVERT_TO_LONG(z, iz);
73538903 if (iz == 0) {
7361 PyErr_SetString(PyExc_ValueError,
737n/a "pow() 3rd argument cannot be 0");
7381 return NULL;
739n/a }
740n/a }
741n/a /*
742n/a * XXX: The original exponentiation code stopped looping
743n/a * when temp hit zero; this code will continue onwards
744n/a * unnecessarily, but at least it won't cause any errors.
745n/a * Hopefully the speed improvement from the fast exponentiation
746n/a * will compensate for the slight inefficiency.
747n/a * XXX: Better handling of overflows is desperately needed.
748n/a */
749965347 temp = iv;
750965347 ix = 1;
7514970033 while (iw > 0) {
7523942572 prev = ix; /* Save value for overflow check */
7533942572 if (iw & 1) {
7542474497 ix = ix*temp;
7552474497 if (temp == 0)
7564329 break; /* Avoid ix / 0 */
7572470168 if (ix / temp != prev) {
75813073 return PyLong_Type.tp_as_number->nb_power(
759n/a (PyObject *)v,
760n/a (PyObject *)w,
761n/a (PyObject *)z);
762n/a }
763n/a }
7643925170 iw >>= 1; /* Shift exponent down by 1 bit */
7653925170 if (iw==0) break;
7663120389 prev = temp;
7673120389 temp *= temp; /* Square the value of temp */
7683120389 if (prev != 0 && temp / prev != prev) {
76981050 return PyLong_Type.tp_as_number->nb_power(
770n/a (PyObject *)v, (PyObject *)w, (PyObject *)z);
771n/a }
7723039339 if (iz) {
773n/a /* If we did a multiplication, perform a modulo */
774309048 ix = ix % iz;
775309048 temp = temp % iz;
776n/a }
777n/a }
778871224 if (iz) {
779n/a long div, mod;
78038694 switch (i_divmod(ix, iz, &div, &mod)) {
781n/a case DIVMOD_OK:
78238694 ix = mod;
78338694 break;
784n/a case DIVMOD_OVERFLOW:
7850 return PyLong_Type.tp_as_number->nb_power(
786n/a (PyObject *)v, (PyObject *)w, (PyObject *)z);
787n/a default:
7880 return NULL;
789n/a }
790n/a }
791871224 return PyInt_FromLong(ix);
792n/a}
793n/a
794n/astatic PyObject *
795n/aint_neg(PyIntObject *v)
796404960{
797n/a register long a;
798404960 a = v->ob_ival;
799n/a /* check for overflow */
800404960 if (UNARY_NEG_WOULD_OVERFLOW(a)) {
8012 PyObject *o = PyLong_FromLong(a);
8022 if (o != NULL) {
8032 PyObject *result = PyNumber_Negative(o);
8042 Py_DECREF(o);
8052 return result;
806n/a }
8070 return NULL;
808n/a }
809404958 return PyInt_FromLong(-a);
810n/a}
811n/a
812n/astatic PyObject *
813n/aint_abs(PyIntObject *v)
814287995{
815287995 if (v->ob_ival >= 0)
816145804 return int_int(v);
817n/a else
818142191 return int_neg(v);
819n/a}
820n/a
821n/astatic int
822n/aint_nonzero(PyIntObject *v)
82367512913{
82467512913 return v->ob_ival != 0;
825n/a}
826n/a
827n/astatic PyObject *
828n/aint_invert(PyIntObject *v)
82919073{
83019073 return PyInt_FromLong(~v->ob_ival);
831n/a}
832n/a
833n/astatic PyObject *
834n/aint_lshift(PyIntObject *v, PyIntObject *w)
835750395{
836n/a long a, b, c;
837n/a PyObject *vv, *ww, *result;
838n/a
839750402 CONVERT_TO_LONG(v, a);
8401500776 CONVERT_TO_LONG(w, b);
841749987 if (b < 0) {
8424 PyErr_SetString(PyExc_ValueError, "negative shift count");
8434 return NULL;
844n/a }
845749983 if (a == 0 || b == 0)
846154940 return int_int(v);
847595043 if (b >= LONG_BIT) {
848159208 vv = PyLong_FromLong(PyInt_AS_LONG(v));
849159208 if (vv == NULL)
8500 return NULL;
851159208 ww = PyLong_FromLong(PyInt_AS_LONG(w));
852159208 if (ww == NULL) {
8530 Py_DECREF(vv);
8540 return NULL;
855n/a }
856159208 result = PyNumber_Lshift(vv, ww);
857159208 Py_DECREF(vv);
858159208 Py_DECREF(ww);
859159208 return result;
860n/a }
861435835 c = a << b;
862435835 if (a != Py_ARITHMETIC_RIGHT_SHIFT(long, c, b)) {
863323696 vv = PyLong_FromLong(PyInt_AS_LONG(v));
864323696 if (vv == NULL)
8650 return NULL;
866323696 ww = PyLong_FromLong(PyInt_AS_LONG(w));
867323696 if (ww == NULL) {
8680 Py_DECREF(vv);
8690 return NULL;
870n/a }
871323696 result = PyNumber_Lshift(vv, ww);
872323696 Py_DECREF(vv);
873323696 Py_DECREF(ww);
874323696 return result;
875n/a }
876112139 return PyInt_FromLong(c);
877n/a}
878n/a
879n/astatic PyObject *
880n/aint_rshift(PyIntObject *v, PyIntObject *w)
881557653{
882n/a register long a, b;
883557660 CONVERT_TO_LONG(v, a);
8841115292 CONVERT_TO_LONG(w, b);
885557621 if (b < 0) {
8864 PyErr_SetString(PyExc_ValueError, "negative shift count");
8874 return NULL;
888n/a }
889557617 if (a == 0 || b == 0)
89022127 return int_int(v);
891535490 if (b >= LONG_BIT) {
8920 if (a < 0)
8930 a = -1;
894n/a else
8950 a = 0;
896n/a }
897n/a else {
898535490 a = Py_ARITHMETIC_RIGHT_SHIFT(long, a, b);
899n/a }
900535490 return PyInt_FromLong(a);
901n/a}
902n/a
903n/astatic PyObject *
904n/aint_and(PyIntObject *v, PyIntObject *w)
9051066075{
906n/a register long a, b;
9071066084 CONVERT_TO_LONG(v, a);
9082132132 CONVERT_TO_LONG(w, b);
9091059397 return PyInt_FromLong(a & b);
910n/a}
911n/a
912n/astatic PyObject *
913n/aint_xor(PyIntObject *v, PyIntObject *w)
914504013{
915n/a register long a, b;
916504022 CONVERT_TO_LONG(v, a);
9171008008 CONVERT_TO_LONG(w, b);
918503981 return PyInt_FromLong(a ^ b);
919n/a}
920n/a
921n/astatic PyObject *
922n/aint_or(PyIntObject *v, PyIntObject *w)
923476079{
924n/a register long a, b;
925476088 CONVERT_TO_LONG(v, a);
926952140 CONVERT_TO_LONG(w, b);
927476032 return PyInt_FromLong(a | b);
928n/a}
929n/a
930n/astatic int
931n/aint_coerce(PyObject **pv, PyObject **pw)
932930223{
933930223 if (PyInt_Check(*pw)) {
9342 Py_INCREF(*pv);
9352 Py_INCREF(*pw);
9362 return 0;
937n/a }
938930221 return 1; /* Can't do it */
939n/a}
940n/a
941n/astatic PyObject *
942n/aint_int(PyIntObject *v)
943344427{
944344427 if (PyInt_CheckExact(v))
945333276 Py_INCREF(v);
946n/a else
94711151 v = (PyIntObject *)PyInt_FromLong(v->ob_ival);
948344427 return (PyObject *)v;
949n/a}
950n/a
951n/astatic PyObject *
952n/aint_long(PyIntObject *v)
953281923{
954281923 return PyLong_FromLong((v -> ob_ival));
955n/a}
956n/a
957n/astatic const unsigned char BitLengthTable[32] = {
958n/a 0, 1, 2, 2, 3, 3, 3, 3, 4, 4, 4, 4, 4, 4, 4, 4,
959n/a 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5
960n/a};
961n/a
962n/astatic int
963n/abits_in_ulong(unsigned long d)
964174938{
965174938 int d_bits = 0;
966840025 while (d >= 32) {
967490149 d_bits += 6;
968490149 d >>= 6;
969n/a }
970174938 d_bits += (int)BitLengthTable[d];
971174938 return d_bits;
972n/a}
973n/a
974n/a#if 8*SIZEOF_LONG-1 <= DBL_MANT_DIG
975n/a/* Every Python int can be exactly represented as a float. */
976n/a
977n/astatic PyObject *
978n/aint_float(PyIntObject *v)
979n/a{
980n/a return PyFloat_FromDouble((double)(v -> ob_ival));
981n/a}
982n/a
983n/a#else
984n/a/* Here not all Python ints are exactly representable as floats, so we may
985n/a have to round. We do this manually, since the C standards don't specify
986n/a whether converting an integer to a float rounds up or down */
987n/a
988n/astatic PyObject *
989n/aint_float(PyIntObject *v)
990557033{
991n/a unsigned long abs_ival, lsb;
992n/a int round_up;
993n/a
994557033 if (v->ob_ival < 0)
99597361 abs_ival = 0U-(unsigned long)v->ob_ival;
996n/a else
997459672 abs_ival = (unsigned long)v->ob_ival;
998557033 if (abs_ival < (1L << DBL_MANT_DIG))
999n/a /* small integer; no need to round */
1000550678 return PyFloat_FromDouble((double)v->ob_ival);
1001n/a
1002n/a /* Round abs_ival to MANT_DIG significant bits, using the
1003n/a round-half-to-even rule. abs_ival & lsb picks out the 'rounding'
1004n/a bit: the first bit after the most significant MANT_DIG bits of
1005n/a abs_ival. We round up if this bit is set, provided that either:
1006n/a
1007n/a (1) abs_ival isn't exactly halfway between two floats, in which
1008n/a case at least one of the bits following the rounding bit must be
1009n/a set; i.e., abs_ival & lsb-1 != 0, or:
1010n/a
1011n/a (2) the resulting rounded value has least significant bit 0; or
1012n/a in other words the bit above the rounding bit is set (this is the
1013n/a 'to-even' bit of round-half-to-even); i.e., abs_ival & 2*lsb != 0
1014n/a
1015n/a The condition "(1) or (2)" equates to abs_ival & 3*lsb-1 != 0. */
1016n/a
10176355 lsb = 1L << (bits_in_ulong(abs_ival)-DBL_MANT_DIG-1);
10186355 round_up = (abs_ival & lsb) && (abs_ival & (3*lsb-1));
10196355 abs_ival &= -2*lsb;
10206355 if (round_up)
10212124 abs_ival += 2*lsb;
10226355 return PyFloat_FromDouble(v->ob_ival < 0 ?
1023n/a -(double)abs_ival :
1024n/a (double)abs_ival);
1025n/a}
1026n/a
1027n/a#endif
1028n/a
1029n/astatic PyObject *
1030n/aint_oct(PyIntObject *v)
10316{
10326 return _PyInt_Format(v, 8, 0);
1033n/a}
1034n/a
1035n/astatic PyObject *
1036n/aint_hex(PyIntObject *v)
1037328{
1038328 return _PyInt_Format(v, 16, 0);
1039n/a}
1040n/a
1041n/astatic PyObject *
1042n/aint_subtype_new(PyTypeObject *type, PyObject *args, PyObject *kwds);
1043n/a
1044n/astatic PyObject *
1045n/aint_new(PyTypeObject *type, PyObject *args, PyObject *kwds)
10464807139{
10474807139 PyObject *x = NULL;
10484807139 int base = -909;
1049n/a static char *kwlist[] = {"x", "base", 0};
1050n/a
10514807139 if (type != &PyInt_Type)
105240246 return int_subtype_new(type, args, kwds); /* Wimp out */
10534766893 if (!PyArg_ParseTupleAndKeywords(args, kwds, "|Oi:int", kwlist,
1054n/a &x, &base))
10551 return NULL;
10564766892 if (x == NULL)
105732 return PyInt_FromLong(0L);
10584766860 if (base == -909)
10594296258 return PyNumber_Int(x);
1060470602 if (PyString_Check(x)) {
1061n/a /* Since PyInt_FromString doesn't have a length parameter,
1062n/a * check here for possible NULs in the string. */
1063470585 char *string = PyString_AS_STRING(x);
1064470585 if (strlen(string) != PyString_Size(x)) {
1065n/a /* create a repr() of the input string,
1066n/a * just like PyInt_FromString does */
1067n/a PyObject *srepr;
10682 srepr = PyObject_Repr(x);
10692 if (srepr == NULL)
10700 return NULL;
10712 PyErr_Format(PyExc_ValueError,
1072n/a "invalid literal for int() with base %d: %s",
1073n/a base, PyString_AS_STRING(srepr));
10742 Py_DECREF(srepr);
10752 return NULL;
1076n/a }
1077470583 return PyInt_FromString(string, NULL, base);
1078n/a }
1079n/a#ifdef Py_USING_UNICODE
108017 if (PyUnicode_Check(x))
108116 return PyInt_FromUnicode(PyUnicode_AS_UNICODE(x),
1082n/a PyUnicode_GET_SIZE(x),
1083n/a base);
1084n/a#endif
10851 PyErr_SetString(PyExc_TypeError,
1086n/a "int() can't convert non-string with explicit base");
10871 return NULL;
1088n/a}
1089n/a
1090n/a/* Wimpy, slow approach to tp_new calls for subtypes of int:
1091n/a first create a regular int from whatever arguments we got,
1092n/a then allocate a subtype instance and initialize its ob_ival
1093n/a from the regular int. The regular int is then thrown away.
1094n/a*/
1095n/astatic PyObject *
1096n/aint_subtype_new(PyTypeObject *type, PyObject *args, PyObject *kwds)
109740246{
1098n/a PyObject *tmp, *newobj;
1099n/a long ival;
1100n/a
110140246 assert(PyType_IsSubtype(type, &PyInt_Type));
110240246 tmp = int_new(&PyInt_Type, args, kwds);
110340246 if (tmp == NULL)
11040 return NULL;
110540246 if (!PyInt_Check(tmp)) {
11061 ival = PyLong_AsLong(tmp);
11071 if (ival == -1 && PyErr_Occurred()) {
11081 Py_DECREF(tmp);
11091 return NULL;
1110n/a }
1111n/a } else {
111240245 ival = ((PyIntObject *)tmp)->ob_ival;
1113n/a }
1114n/a
111540245 newobj = type->tp_alloc(type, 0);
111640245 if (newobj == NULL) {
11170 Py_DECREF(tmp);
11180 return NULL;
1119n/a }
112040245 ((PyIntObject *)newobj)->ob_ival = ival;
112140245 Py_DECREF(tmp);
112240245 return newobj;
1123n/a}
1124n/a
1125n/astatic PyObject *
1126n/aint_getnewargs(PyIntObject *v)
112718{
112818 return Py_BuildValue("(l)", v->ob_ival);
1129n/a}
1130n/a
1131n/astatic PyObject *
11321int_get0(PyIntObject *v, void *context) {
11331 return PyInt_FromLong(0L);
1134n/a}
1135n/a
1136n/astatic PyObject *
11371000int_get1(PyIntObject *v, void *context) {
11381000 return PyInt_FromLong(1L);
1139n/a}
1140n/a
1141n/a/* Convert an integer to a decimal string. On many platforms, this
1142n/a will be significantly faster than the general arbitrary-base
1143n/a conversion machinery in _PyInt_Format, thanks to optimization
1144n/a opportunities offered by division by a compile-time constant. */
1145n/astatic PyObject *
1146975398int_to_decimal_string(PyIntObject *v) {
1147n/a char buf[sizeof(long)*CHAR_BIT/3+6], *p, *bufend;
1148975398 long n = v->ob_ival;
1149n/a unsigned long absn;
1150975398 p = bufend = buf + sizeof(buf);
1151975398 absn = n < 0 ? 0UL - n : n;
1152n/a do {
11532301967 *--p = '0' + (char)(absn % 10);
11542301967 absn /= 10;
11552301967 } while (absn);
1156975398 if (n < 0)
1157228223 *--p = '-';
1158975398 return PyString_FromStringAndSize(p, bufend - p);
1159n/a}
1160n/a
1161n/a/* Convert an integer to the given base. Returns a string.
1162n/a If base is 2, 8 or 16, add the proper prefix '0b', '0o' or '0x'.
1163n/a If newstyle is zero, then use the pre-2.6 behavior of octal having
1164n/a a leading "0" */
1165n/aPyAPI_FUNC(PyObject*)
1166n/a_PyInt_Format(PyIntObject *v, int base, int newstyle)
1167216868{
1168n/a /* There are no doubt many, many ways to optimize this, using code
1169n/a similar to _PyLong_Format */
1170216868 long n = v->ob_ival;
1171216868 int negative = n < 0;
1172216868 int is_zero = n == 0;
1173n/a
1174n/a /* For the reasoning behind this size, see
1175n/a http://c-faq.com/misc/hexio.html. Then, add a few bytes for
1176n/a the possible sign and prefix "0[box]" */
1177n/a char buf[sizeof(n)*CHAR_BIT+6];
1178n/a
1179n/a /* Start by pointing to the end of the buffer. We fill in from
1180n/a the back forward. */
1181216868 char* p = &buf[sizeof(buf)];
1182n/a
1183216868 assert(base >= 2 && base <= 36);
1184n/a
1185n/a /* Special case base 10, for speed */
1186216868 if (base == 10)
118719218 return int_to_decimal_string(v);
1188n/a
1189n/a do {
1190n/a /* I'd use i_divmod, except it doesn't produce the results
1191n/a I want when n is negative. So just duplicate the salient
1192n/a part here. */
11932242906 long div = n / base;
11942242906 long mod = n - div * base;
1195n/a
1196n/a /* convert abs(mod) to the right character in [0-9, a-z] */
11972242906 char cdigit = (char)(mod < 0 ? -mod : mod);
11982242906 cdigit += (cdigit < 10) ? '0' : 'a'-10;
11992242906 *--p = cdigit;
1200n/a
12012242906 n = div;
12022242906 } while(n);
1203n/a
1204197650 if (base == 2) {
1205130041 *--p = 'b';
1206130041 *--p = '0';
1207n/a }
120867609 else if (base == 8) {
120951 if (newstyle) {
121045 *--p = 'o';
121145 *--p = '0';
1212n/a }
1213n/a else
12146 if (!is_zero)
12156 *--p = '0';
1216n/a }
121767558 else if (base == 16) {
121867558 *--p = 'x';
121967558 *--p = '0';
1220n/a }
1221n/a else {
12220 *--p = '#';
12230 *--p = '0' + base%10;
12240 if (base > 10)
12250 *--p = '0' + base/10;
1226n/a }
1227197650 if (negative)
122865069 *--p = '-';
1229n/a
1230197650 return PyString_FromStringAndSize(p, &buf[sizeof(buf)] - p);
1231n/a}
1232n/a
1233n/astatic PyObject *
1234n/aint__format__(PyObject *self, PyObject *args)
1235476{
1236n/a PyObject *format_spec;
1237n/a
1238476 if (!PyArg_ParseTuple(args, "O:__format__", &format_spec))
12390 return NULL;
1240476 if (PyBytes_Check(format_spec))
1241344 return _PyInt_FormatAdvanced(self,
1242n/a PyBytes_AS_STRING(format_spec),
1243n/a PyBytes_GET_SIZE(format_spec));
1244132 if (PyUnicode_Check(format_spec)) {
1245n/a /* Convert format_spec to a str */
1246n/a PyObject *result;
1247130 PyObject *str_spec = PyObject_Str(format_spec);
1248n/a
1249130 if (str_spec == NULL)
12500 return NULL;
1251n/a
1252130 result = _PyInt_FormatAdvanced(self,
1253n/a PyBytes_AS_STRING(str_spec),
1254n/a PyBytes_GET_SIZE(str_spec));
1255n/a
1256130 Py_DECREF(str_spec);
1257130 return result;
1258n/a }
12592 PyErr_SetString(PyExc_TypeError, "__format__ requires str or unicode");
12602 return NULL;
1261n/a}
1262n/a
1263n/astatic PyObject *
1264n/aint_bit_length(PyIntObject *v)
1265168583{
1266n/a unsigned long n;
1267n/a
1268168583 if (v->ob_ival < 0)
1269n/a /* avoid undefined behaviour when v->ob_ival == -LONG_MAX-1 */
127065026 n = 0U-(unsigned long)v->ob_ival;
1271n/a else
1272103557 n = (unsigned long)v->ob_ival;
1273n/a
1274168583 return PyInt_FromLong(bits_in_ulong(n));
1275n/a}
1276n/a
1277n/aPyDoc_STRVAR(int_bit_length_doc,
1278n/a"int.bit_length() -> int\n\
1279n/a\n\
1280n/aNumber of bits necessary to represent self in binary.\n\
1281n/a>>> bin(37)\n\
1282n/a'0b100101'\n\
1283n/a>>> (37).bit_length()\n\
1284n/a6");
1285n/a
1286n/a#if 0
1287n/astatic PyObject *
1288n/aint_is_finite(PyObject *v)
1289n/a{
1290n/a Py_RETURN_TRUE;
1291n/a}
1292n/a#endif
1293n/a
1294n/astatic PyMethodDef int_methods[] = {
1295n/a {"conjugate", (PyCFunction)int_int, METH_NOARGS,
1296n/a "Returns self, the complex conjugate of any int."},
1297n/a {"bit_length", (PyCFunction)int_bit_length, METH_NOARGS,
1298n/a int_bit_length_doc},
1299n/a#if 0
1300n/a {"is_finite", (PyCFunction)int_is_finite, METH_NOARGS,
1301n/a "Returns always True."},
1302n/a#endif
1303n/a {"__trunc__", (PyCFunction)int_int, METH_NOARGS,
1304n/a "Truncating an Integral returns itself."},
1305n/a {"__getnewargs__", (PyCFunction)int_getnewargs, METH_NOARGS},
1306n/a {"__format__", (PyCFunction)int__format__, METH_VARARGS},
1307n/a {NULL, NULL} /* sentinel */
1308n/a};
1309n/a
1310n/astatic PyGetSetDef int_getset[] = {
1311n/a {"real",
1312n/a (getter)int_int, (setter)NULL,
1313n/a "the real part of a complex number",
1314n/a NULL},
1315n/a {"imag",
1316n/a (getter)int_get0, (setter)NULL,
1317n/a "the imaginary part of a complex number",
1318n/a NULL},
1319n/a {"numerator",
1320n/a (getter)int_int, (setter)NULL,
1321n/a "the numerator of a rational number in lowest terms",
1322n/a NULL},
1323n/a {"denominator",
1324n/a (getter)int_get1, (setter)NULL,
1325n/a "the denominator of a rational number in lowest terms",
1326n/a NULL},
1327n/a {NULL} /* Sentinel */
1328n/a};
1329n/a
1330n/aPyDoc_STRVAR(int_doc,
1331n/a"int(x[, base]) -> integer\n\
1332n/a\n\
1333n/aConvert a string or number to an integer, if possible. A floating point\n\
1334n/aargument will be truncated towards zero (this does not include a string\n\
1335n/arepresentation of a floating point number!) When converting a string, use\n\
1336n/athe optional base. It is an error to supply a base when converting a\n\
1337n/anon-string. If base is zero, the proper base is guessed based on the\n\
1338n/astring content. If the argument is outside the integer range a\n\
1339n/along object will be returned instead.");
1340n/a
1341n/astatic PyNumberMethods int_as_number = {
1342n/a (binaryfunc)int_add, /*nb_add*/
1343n/a (binaryfunc)int_sub, /*nb_subtract*/
1344n/a (binaryfunc)int_mul, /*nb_multiply*/
1345n/a (binaryfunc)int_classic_div, /*nb_divide*/
1346n/a (binaryfunc)int_mod, /*nb_remainder*/
1347n/a (binaryfunc)int_divmod, /*nb_divmod*/
1348n/a (ternaryfunc)int_pow, /*nb_power*/
1349n/a (unaryfunc)int_neg, /*nb_negative*/
1350n/a (unaryfunc)int_int, /*nb_positive*/
1351n/a (unaryfunc)int_abs, /*nb_absolute*/
1352n/a (inquiry)int_nonzero, /*nb_nonzero*/
1353n/a (unaryfunc)int_invert, /*nb_invert*/
1354n/a (binaryfunc)int_lshift, /*nb_lshift*/
1355n/a (binaryfunc)int_rshift, /*nb_rshift*/
1356n/a (binaryfunc)int_and, /*nb_and*/
1357n/a (binaryfunc)int_xor, /*nb_xor*/
1358n/a (binaryfunc)int_or, /*nb_or*/
1359n/a int_coerce, /*nb_coerce*/
1360n/a (unaryfunc)int_int, /*nb_int*/
1361n/a (unaryfunc)int_long, /*nb_long*/
1362n/a (unaryfunc)int_float, /*nb_float*/
1363n/a (unaryfunc)int_oct, /*nb_oct*/
1364n/a (unaryfunc)int_hex, /*nb_hex*/
1365n/a 0, /*nb_inplace_add*/
1366n/a 0, /*nb_inplace_subtract*/
1367n/a 0, /*nb_inplace_multiply*/
1368n/a 0, /*nb_inplace_divide*/
1369n/a 0, /*nb_inplace_remainder*/
1370n/a 0, /*nb_inplace_power*/
1371n/a 0, /*nb_inplace_lshift*/
1372n/a 0, /*nb_inplace_rshift*/
1373n/a 0, /*nb_inplace_and*/
1374n/a 0, /*nb_inplace_xor*/
1375n/a 0, /*nb_inplace_or*/
1376n/a (binaryfunc)int_div, /* nb_floor_divide */
1377n/a (binaryfunc)int_true_divide, /* nb_true_divide */
1378n/a 0, /* nb_inplace_floor_divide */
1379n/a 0, /* nb_inplace_true_divide */
1380n/a (unaryfunc)int_int, /* nb_index */
1381n/a};
1382n/a
1383n/aPyTypeObject PyInt_Type = {
1384n/a PyVarObject_HEAD_INIT(&PyType_Type, 0)
1385n/a "int",
1386n/a sizeof(PyIntObject),
1387n/a 0,
1388n/a (destructor)int_dealloc, /* tp_dealloc */
1389n/a (printfunc)int_print, /* tp_print */
1390n/a 0, /* tp_getattr */
1391n/a 0, /* tp_setattr */
1392n/a (cmpfunc)int_compare, /* tp_compare */
1393n/a (reprfunc)int_to_decimal_string, /* tp_repr */
1394n/a &int_as_number, /* tp_as_number */
1395n/a 0, /* tp_as_sequence */
1396n/a 0, /* tp_as_mapping */
1397n/a (hashfunc)int_hash, /* tp_hash */
1398n/a 0, /* tp_call */
1399n/a (reprfunc)int_to_decimal_string, /* tp_str */
1400n/a PyObject_GenericGetAttr, /* tp_getattro */
1401n/a 0, /* tp_setattro */
1402n/a 0, /* tp_as_buffer */
1403n/a Py_TPFLAGS_DEFAULT | Py_TPFLAGS_CHECKTYPES |
1404n/a Py_TPFLAGS_BASETYPE | Py_TPFLAGS_INT_SUBCLASS, /* tp_flags */
1405n/a int_doc, /* tp_doc */
1406n/a 0, /* tp_traverse */
1407n/a 0, /* tp_clear */
1408n/a 0, /* tp_richcompare */
1409n/a 0, /* tp_weaklistoffset */
1410n/a 0, /* tp_iter */
1411n/a 0, /* tp_iternext */
1412n/a int_methods, /* tp_methods */
1413n/a 0, /* tp_members */
1414n/a int_getset, /* tp_getset */
1415n/a 0, /* tp_base */
1416n/a 0, /* tp_dict */
1417n/a 0, /* tp_descr_get */
1418n/a 0, /* tp_descr_set */
1419n/a 0, /* tp_dictoffset */
1420n/a 0, /* tp_init */
1421n/a 0, /* tp_alloc */
1422n/a int_new, /* tp_new */
1423n/a (freefunc)int_free, /* tp_free */
1424n/a};
1425n/a
1426n/aint
1427n/a_PyInt_Init(void)
1428293{
1429n/a PyIntObject *v;
1430n/a int ival;
1431n/a#if NSMALLNEGINTS + NSMALLPOSINTS > 0
143277059 for (ival = -NSMALLNEGINTS; ival < NSMALLPOSINTS; ival++) {
143376766 if (!free_list && (free_list = fill_free_list()) == NULL)
14340 return 0;
1435n/a /* PyObject_New is inlined */
143676766 v = free_list;
143776766 free_list = (PyIntObject *)Py_TYPE(v);
143876766 PyObject_INIT(v, &PyInt_Type);
143976766 v->ob_ival = ival;
144076766 small_ints[ival + NSMALLNEGINTS] = v;
1441n/a }
1442n/a#endif
1443293 return 1;
1444n/a}
1445n/a
1446n/aint
1447n/aPyInt_ClearFreeList(void)
14481352{
1449n/a PyIntObject *p;
1450n/a PyIntBlock *list, *next;
1451n/a int i;
1452n/a int u; /* remaining unfreed ints per block */
14531352 int freelist_size = 0;
1454n/a
14551352 list = block_list;
14561352 block_list = NULL;
14571352 free_list = NULL;
14583828580 while (list != NULL) {
14593825876 u = 0;
14603825876 for (i = 0, p = &list->objects[0];
146199472776 i < N_INTOBJECTS;
146291821024 i++, p++) {
146391821024 if (PyInt_CheckExact(p) && p->ob_refcnt != 0)
146485037815 u++;
1465n/a }
14663825876 next = list->next;
14673825876 if (u) {
14683700836 list->next = block_list;
14693700836 block_list = list;
14703700836 for (i = 0, p = &list->objects[0];
147196221736 i < N_INTOBJECTS;
147288820064 i++, p++) {
147392602313 if (!PyInt_CheckExact(p) ||
1474n/a p->ob_refcnt == 0) {
14753782249 Py_TYPE(p) = (struct _typeobject *)
1476n/a free_list;
14773782249 free_list = p;
1478n/a }
1479n/a#if NSMALLNEGINTS + NSMALLPOSINTS > 0
148085037815 else if (-NSMALLNEGINTS <= p->ob_ival &&
1481n/a p->ob_ival < NSMALLPOSINTS &&
1482n/a small_ints[p->ob_ival +
1483n/a NSMALLNEGINTS] == NULL) {
14844394 Py_INCREF(p);
14854394 small_ints[p->ob_ival +
1486n/a NSMALLNEGINTS] = p;
1487n/a }
1488n/a#endif
1489n/a }
1490n/a }
1491n/a else {
1492125040 PyMem_FREE(list);
1493n/a }
14943825876 freelist_size += u;
14953825876 list = next;
1496n/a }
1497n/a
14981352 return freelist_size;
1499n/a}
1500n/a
1501n/avoid
1502n/aPyInt_Fini(void)
1503293{
1504n/a PyIntObject *p;
1505n/a PyIntBlock *list;
1506n/a int i;
1507n/a int u; /* total unfreed ints per block */
1508n/a
1509n/a#if NSMALLNEGINTS + NSMALLPOSINTS > 0
1510n/a PyIntObject **q;
1511n/a
1512293 i = NSMALLNEGINTS + NSMALLPOSINTS;
1513293 q = small_ints;
151477352 while (--i >= 0) {
151576766 Py_XDECREF(*q);
151676766 *q++ = NULL;
1517n/a }
1518n/a#endif
1519293 u = PyInt_ClearFreeList();
1520293 if (!Py_VerboseFlag)
1521293 return;
15220 fprintf(stderr, "# cleanup ints");
15230 if (!u) {
15240 fprintf(stderr, "\n");
1525n/a }
1526n/a else {
15270 fprintf(stderr,
1528n/a ": %d unfreed int%s\n",
1529n/a u, u == 1 ? "" : "s");
1530n/a }
15310 if (Py_VerboseFlag > 1) {
15320 list = block_list;
15330 while (list != NULL) {
15340 for (i = 0, p = &list->objects[0];
15350 i < N_INTOBJECTS;
15360 i++, p++) {
15370 if (PyInt_CheckExact(p) && p->ob_refcnt != 0)
1538n/a /* XXX(twouters) cast refcount to
1539n/a long until %zd is universally
1540n/a available
1541n/a */
15420 fprintf(stderr,
1543n/a "# <int at %p, refcnt=%ld, val=%ld>\n",
1544n/a p, (long)p->ob_refcnt,
1545n/a p->ob_ival);
1546n/a }
15470 list = list->next;
1548n/a }
1549n/a }
1550n/a}