2 /* Integer object implementation */
8 static PyObject
*int_int(PyIntObject
*v
);
13 return LONG_MAX
; /* To initialize sys.maxint */
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().
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).
29 free_list is a singly-linked list of available PyIntObjects, linked
30 via abuse of their ob_type members.
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))
38 struct _intblock
*next
;
39 PyIntObject objects
[N_INTOBJECTS
];
42 typedef struct _intblock PyIntBlock
;
44 static PyIntBlock
*block_list
= NULL
;
45 static PyIntObject
*free_list
= NULL
;
51 /* Python's object allocator isn't appropriate for large blocks. */
52 p
= (PyIntObject
*) PyMem_MALLOC(sizeof(PyIntBlock
));
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];
62 Py_TYPE(q
) = (struct _typeobject
*)(q
-1);
64 return p
+ N_INTOBJECTS
- 1;
68 #define NSMALLPOSINTS 257
71 #define NSMALLNEGINTS 5
73 #if NSMALLNEGINTS + NSMALLPOSINTS > 0
74 /* References to small integers are saved in this array so that they
76 The integers that are saved are those in the range
77 -NSMALLNEGINTS (inclusive) to NSMALLPOSINTS (not inclusive).
79 static PyIntObject
*small_ints
[NSMALLNEGINTS
+ NSMALLPOSINTS
];
82 Py_ssize_t quick_int_allocs
;
83 Py_ssize_t quick_neg_int_allocs
;
87 PyInt_FromLong(long ival
)
89 register PyIntObject
*v
;
90 #if NSMALLNEGINTS + NSMALLPOSINTS > 0
91 if (-NSMALLNEGINTS
<= ival
&& ival
< NSMALLPOSINTS
) {
92 v
= small_ints
[ival
+ NSMALLNEGINTS
];
98 quick_neg_int_allocs
++;
100 return (PyObject
*) v
;
103 if (free_list
== NULL
) {
104 if ((free_list
= fill_free_list()) == NULL
)
107 /* Inline PyObject_New */
109 free_list
= (PyIntObject
*)Py_TYPE(v
);
110 PyObject_INIT(v
, &PyInt_Type
);
112 return (PyObject
*) v
;
116 PyInt_FromSize_t(size_t ival
)
118 if (ival
<= LONG_MAX
)
119 return PyInt_FromLong((long)ival
);
120 return _PyLong_FromSize_t(ival
);
124 PyInt_FromSsize_t(Py_ssize_t ival
)
126 if (ival
>= LONG_MIN
&& ival
<= LONG_MAX
)
127 return PyInt_FromLong((long)ival
);
128 return _PyLong_FromSsize_t(ival
);
132 int_dealloc(PyIntObject
*v
)
134 if (PyInt_CheckExact(v
)) {
135 Py_TYPE(v
) = (struct _typeobject
*)free_list
;
139 Py_TYPE(v
)->tp_free((PyObject
*)v
);
143 int_free(PyIntObject
*v
)
145 Py_TYPE(v
) = (struct _typeobject
*)free_list
;
150 PyInt_AsLong(register PyObject
*op
)
156 if (op
&& PyInt_Check(op
))
157 return PyInt_AS_LONG((PyIntObject
*) op
);
159 if (op
== NULL
|| (nb
= Py_TYPE(op
)->tp_as_number
) == NULL
||
160 nb
->nb_int
== NULL
) {
161 PyErr_SetString(PyExc_TypeError
, "an integer is required");
165 io
= (PyIntObject
*) (*nb
->nb_int
) (op
);
168 if (!PyInt_Check(io
)) {
169 if (PyLong_Check(io
)) {
170 /* got a long? => retry int conversion */
171 val
= PyLong_AsLong((PyObject
*)io
);
173 if ((val
== -1) && PyErr_Occurred())
180 PyErr_SetString(PyExc_TypeError
,
181 "__int__ method should return an integer");
186 val
= PyInt_AS_LONG(io
);
193 _PyInt_AsInt(PyObject
*obj
)
195 long result
= PyInt_AsLong(obj
);
196 if (result
== -1 && PyErr_Occurred())
198 if (result
> INT_MAX
|| result
< INT_MIN
) {
199 PyErr_SetString(PyExc_OverflowError
,
200 "Python int too large to convert to C int");
207 PyInt_AsSsize_t(register PyObject
*op
)
209 #if SIZEOF_SIZE_T != SIZEOF_LONG
216 PyErr_SetString(PyExc_TypeError
, "an integer is required");
221 return PyInt_AS_LONG((PyIntObject
*) op
);
222 if (PyLong_Check(op
))
223 return _PyLong_AsSsize_t(op
);
224 #if SIZEOF_SIZE_T == SIZEOF_LONG
225 return PyInt_AsLong(op
);
228 if ((nb
= Py_TYPE(op
)->tp_as_number
) == NULL
||
229 (nb
->nb_int
== NULL
&& nb
->nb_long
== 0)) {
230 PyErr_SetString(PyExc_TypeError
, "an integer is required");
234 if (nb
->nb_long
!= 0)
235 io
= (*nb
->nb_long
)(op
);
237 io
= (*nb
->nb_int
)(op
);
240 if (!PyInt_Check(io
)) {
241 if (PyLong_Check(io
)) {
242 /* got a long? => retry int conversion */
243 val
= _PyLong_AsSsize_t(io
);
245 if ((val
== -1) && PyErr_Occurred())
252 PyErr_SetString(PyExc_TypeError
,
253 "__int__ method should return an integer");
258 val
= PyInt_AS_LONG(io
);
266 PyInt_AsUnsignedLongMask(register PyObject
*op
)
272 if (op
&& PyInt_Check(op
))
273 return PyInt_AS_LONG((PyIntObject
*) op
);
274 if (op
&& PyLong_Check(op
))
275 return PyLong_AsUnsignedLongMask(op
);
277 if (op
== NULL
|| (nb
= Py_TYPE(op
)->tp_as_number
) == NULL
||
278 nb
->nb_int
== NULL
) {
279 PyErr_SetString(PyExc_TypeError
, "an integer is required");
280 return (unsigned long)-1;
283 io
= (PyIntObject
*) (*nb
->nb_int
) (op
);
285 return (unsigned long)-1;
286 if (!PyInt_Check(io
)) {
287 if (PyLong_Check(io
)) {
288 val
= PyLong_AsUnsignedLongMask((PyObject
*)io
);
290 if (PyErr_Occurred())
291 return (unsigned long)-1;
297 PyErr_SetString(PyExc_TypeError
,
298 "__int__ method should return an integer");
299 return (unsigned long)-1;
303 val
= PyInt_AS_LONG(io
);
309 #ifdef HAVE_LONG_LONG
310 unsigned PY_LONG_LONG
311 PyInt_AsUnsignedLongLongMask(register PyObject
*op
)
315 unsigned PY_LONG_LONG val
;
317 if (op
&& PyInt_Check(op
))
318 return PyInt_AS_LONG((PyIntObject
*) op
);
319 if (op
&& PyLong_Check(op
))
320 return PyLong_AsUnsignedLongLongMask(op
);
322 if (op
== NULL
|| (nb
= Py_TYPE(op
)->tp_as_number
) == NULL
||
323 nb
->nb_int
== NULL
) {
324 PyErr_SetString(PyExc_TypeError
, "an integer is required");
325 return (unsigned PY_LONG_LONG
)-1;
328 io
= (PyIntObject
*) (*nb
->nb_int
) (op
);
330 return (unsigned PY_LONG_LONG
)-1;
331 if (!PyInt_Check(io
)) {
332 if (PyLong_Check(io
)) {
333 val
= PyLong_AsUnsignedLongLongMask((PyObject
*)io
);
335 if (PyErr_Occurred())
336 return (unsigned PY_LONG_LONG
)-1;
342 PyErr_SetString(PyExc_TypeError
,
343 "__int__ method should return an integer");
344 return (unsigned PY_LONG_LONG
)-1;
348 val
= PyInt_AS_LONG(io
);
356 PyInt_FromString(char *s
, char **pend
, int base
)
361 PyObject
*sobj
, *srepr
;
363 if ((base
!= 0 && base
< 2) || base
> 36) {
364 PyErr_SetString(PyExc_ValueError
,
365 "int() base must be >= 2 and <= 36");
369 while (*s
&& isspace(Py_CHARMASK(*s
)))
372 if (base
== 0 && s
[0] == '0') {
373 x
= (long) PyOS_strtoul(s
, &end
, base
);
375 return PyLong_FromString(s
, pend
, base
);
378 x
= PyOS_strtol(s
, &end
, base
);
379 if (end
== s
|| !isalnum(Py_CHARMASK(end
[-1])))
381 while (*end
&& isspace(Py_CHARMASK(*end
)))
385 slen
= strlen(s
) < 200 ? strlen(s
) : 200;
386 sobj
= PyString_FromStringAndSize(s
, slen
);
389 srepr
= PyObject_Repr(sobj
);
393 PyErr_Format(PyExc_ValueError
,
394 "invalid literal for int() with base %d: %s",
395 base
, PyString_AS_STRING(srepr
));
400 return PyLong_FromString(s
, pend
, base
);
403 return PyInt_FromLong(x
);
406 #ifdef Py_USING_UNICODE
408 PyInt_FromUnicode(Py_UNICODE
*s
, Py_ssize_t length
, int base
)
411 char *buffer
= (char *)PyMem_MALLOC(length
+1);
414 return PyErr_NoMemory();
416 if (PyUnicode_EncodeDecimal(s
, length
, buffer
, NULL
)) {
420 result
= PyInt_FromString(buffer
, NULL
, base
);
428 /* Integers are seen as the "smallest" of all numeric types and thus
429 don't have any knowledge about conversion of other types to
432 #define CONVERT_TO_LONG(obj, lng) \
433 if (PyInt_Check(obj)) { \
434 lng = PyInt_AS_LONG(obj); \
437 Py_INCREF(Py_NotImplemented); \
438 return Py_NotImplemented; \
443 int_print(PyIntObject
*v
, FILE *fp
, int flags
)
444 /* flags -- not used but required by interface */
446 long int_val
= v
->ob_ival
;
447 Py_BEGIN_ALLOW_THREADS
448 fprintf(fp
, "%ld", int_val
);
454 int_compare(PyIntObject
*v
, PyIntObject
*w
)
456 register long i
= v
->ob_ival
;
457 register long j
= w
->ob_ival
;
458 return (i
< j
) ? -1 : (i
> j
) ? 1 : 0;
462 int_hash(PyIntObject
*v
)
464 /* XXX If this is changed, you also need to change the way
465 Python's long, float and complex types are hashed. */
466 long x
= v
-> ob_ival
;
473 int_add(PyIntObject
*v
, PyIntObject
*w
)
475 register long a
, b
, x
;
476 CONVERT_TO_LONG(v
, a
);
477 CONVERT_TO_LONG(w
, b
);
478 /* casts in the line below avoid undefined behaviour on overflow */
479 x
= (long)((unsigned long)a
+ b
);
480 if ((x
^a
) >= 0 || (x
^b
) >= 0)
481 return PyInt_FromLong(x
);
482 return PyLong_Type
.tp_as_number
->nb_add((PyObject
*)v
, (PyObject
*)w
);
486 int_sub(PyIntObject
*v
, PyIntObject
*w
)
488 register long a
, b
, x
;
489 CONVERT_TO_LONG(v
, a
);
490 CONVERT_TO_LONG(w
, b
);
491 /* casts in the line below avoid undefined behaviour on overflow */
492 x
= (long)((unsigned long)a
- b
);
493 if ((x
^a
) >= 0 || (x
^~b
) >= 0)
494 return PyInt_FromLong(x
);
495 return PyLong_Type
.tp_as_number
->nb_subtract((PyObject
*)v
,
500 Integer overflow checking for * is painful: Python tried a couple ways, but
501 they didn't work on all platforms, or failed in endcases (a product of
502 -sys.maxint-1 has been a particular pain).
506 The native long product x*y is either exactly right or *way* off, being
507 just the last n bits of the true product, where n is the number of bits
508 in a long (the delivered product is the true product plus i*2**n for
511 The native double product (double)x * (double)y is subject to three
512 rounding errors: on a sizeof(long)==8 box, each cast to double can lose
513 info, and even on a sizeof(long)==4 box, the multiplication can lose info.
514 But, unlike the native long product, it's not in *range* trouble: even
515 if sizeof(long)==32 (256-bit longs), the product easily fits in the
516 dynamic range of a double. So the leading 50 (or so) bits of the double
519 We check these two ways against each other, and declare victory if they're
520 approximately the same. Else, because the native long product is the only
521 one that can lose catastrophic amounts of information, it's the native long
522 product that must have overflowed.
526 int_mul(PyObject
*v
, PyObject
*w
)
529 long longprod
; /* a*b in native long arithmetic */
530 double doubled_longprod
; /* (double)longprod */
531 double doubleprod
; /* (double)a * (double)b */
533 CONVERT_TO_LONG(v
, a
);
534 CONVERT_TO_LONG(w
, b
);
535 /* casts in the next line avoid undefined behaviour on overflow */
536 longprod
= (long)((unsigned long)a
* b
);
537 doubleprod
= (double)a
* (double)b
;
538 doubled_longprod
= (double)longprod
;
540 /* Fast path for normal case: small multiplicands, and no info
541 is lost in either method. */
542 if (doubled_longprod
== doubleprod
)
543 return PyInt_FromLong(longprod
);
545 /* Somebody somewhere lost info. Close enough, or way off? Note
546 that a != 0 and b != 0 (else doubled_longprod == doubleprod == 0).
547 The difference either is or isn't significant compared to the
548 true value (of which doubleprod is a good approximation).
551 const double diff
= doubled_longprod
- doubleprod
;
552 const double absdiff
= diff
>= 0.0 ? diff
: -diff
;
553 const double absprod
= doubleprod
>= 0.0 ? doubleprod
:
555 /* absdiff/absprod <= 1/32 iff
556 32 * absdiff <= absprod -- 5 good bits is "close enough" */
557 if (32.0 * absdiff
<= absprod
)
558 return PyInt_FromLong(longprod
);
560 return PyLong_Type
.tp_as_number
->nb_multiply(v
, w
);
564 /* Integer overflow checking for unary negation: on a 2's-complement
565 * box, -x overflows iff x is the most negative long. In this case we
566 * get -x == x. However, -x is undefined (by C) if x /is/ the most
567 * negative long (it's a signed overflow case), and some compilers care.
568 * So we cast x to unsigned long first. However, then other compilers
569 * warn about applying unary minus to an unsigned operand. Hence the
572 #define UNARY_NEG_WOULD_OVERFLOW(x) \
573 ((x) < 0 && (unsigned long)(x) == 0-(unsigned long)(x))
575 /* Return type of i_divmod */
577 DIVMOD_OK
, /* Correct result */
578 DIVMOD_OVERFLOW
, /* Overflow, try again using longs */
579 DIVMOD_ERROR
/* Exception raised */
582 static enum divmod_result
583 i_divmod(register long x
, register long y
,
584 long *p_xdivy
, long *p_xmody
)
589 PyErr_SetString(PyExc_ZeroDivisionError
,
590 "integer division or modulo by zero");
593 /* (-sys.maxint-1)/-1 is the only overflow case. */
594 if (y
== -1 && UNARY_NEG_WOULD_OVERFLOW(x
))
595 return DIVMOD_OVERFLOW
;
597 /* xdiv*y can overflow on platforms where x/y gives floor(x/y)
598 * for x and y with differing signs. (This is unusual
599 * behaviour, and C99 prohibits it, but it's allowed by C89;
600 * for an example of overflow, take x = LONG_MIN, y = 5 or x =
601 * LONG_MAX, y = -5.) However, x - xdivy*y is always
602 * representable as a long, since it lies strictly between
603 * -abs(y) and abs(y). We add casts to avoid intermediate
606 xmody
= (long)(x
- (unsigned long)xdivy
* y
);
607 /* If the signs of x and y differ, and the remainder is non-0,
608 * C89 doesn't define whether xdivy is now the floor or the
609 * ceiling of the infinitely precise quotient. We want the floor,
610 * and we have it iff the remainder's sign matches y's.
612 if (xmody
&& ((y
^ xmody
) < 0) /* i.e. and signs differ */) {
615 assert(xmody
&& ((y
^ xmody
) >= 0));
623 int_div(PyIntObject
*x
, PyIntObject
*y
)
627 CONVERT_TO_LONG(x
, xi
);
628 CONVERT_TO_LONG(y
, yi
);
629 switch (i_divmod(xi
, yi
, &d
, &m
)) {
631 return PyInt_FromLong(d
);
632 case DIVMOD_OVERFLOW
:
633 return PyLong_Type
.tp_as_number
->nb_divide((PyObject
*)x
,
641 int_classic_div(PyIntObject
*x
, PyIntObject
*y
)
645 CONVERT_TO_LONG(x
, xi
);
646 CONVERT_TO_LONG(y
, yi
);
647 if (Py_DivisionWarningFlag
&&
648 PyErr_Warn(PyExc_DeprecationWarning
, "classic int division") < 0)
650 switch (i_divmod(xi
, yi
, &d
, &m
)) {
652 return PyInt_FromLong(d
);
653 case DIVMOD_OVERFLOW
:
654 return PyLong_Type
.tp_as_number
->nb_divide((PyObject
*)x
,
662 int_true_divide(PyIntObject
*x
, PyIntObject
*y
)
665 /* If they aren't both ints, give someone else a chance. In
666 particular, this lets int/long get handled by longs, which
667 underflows to 0 gracefully if the long is too big to convert
669 CONVERT_TO_LONG(x
, xi
);
670 CONVERT_TO_LONG(y
, yi
);
672 PyErr_SetString(PyExc_ZeroDivisionError
,
677 return PyFloat_FromDouble(yi
< 0 ? -0.0 : 0.0);
679 #define WIDTH_OF_ULONG (CHAR_BIT*SIZEOF_LONG)
680 #if DBL_MANT_DIG < WIDTH_OF_ULONG
681 if ((xi
>= 0 ? 0UL + xi
: 0UL - xi
) >> DBL_MANT_DIG
||
682 (yi
>= 0 ? 0UL + yi
: 0UL - yi
) >> DBL_MANT_DIG
)
683 /* Large x or y. Use long integer arithmetic. */
684 return PyLong_Type
.tp_as_number
->nb_true_divide(
685 (PyObject
*)x
, (PyObject
*)y
);
688 /* Both ints can be exactly represented as doubles. Do a
689 floating-point division. */
690 return PyFloat_FromDouble((double)xi
/ (double)yi
);
694 int_mod(PyIntObject
*x
, PyIntObject
*y
)
698 CONVERT_TO_LONG(x
, xi
);
699 CONVERT_TO_LONG(y
, yi
);
700 switch (i_divmod(xi
, yi
, &d
, &m
)) {
702 return PyInt_FromLong(m
);
703 case DIVMOD_OVERFLOW
:
704 return PyLong_Type
.tp_as_number
->nb_remainder((PyObject
*)x
,
712 int_divmod(PyIntObject
*x
, PyIntObject
*y
)
716 CONVERT_TO_LONG(x
, xi
);
717 CONVERT_TO_LONG(y
, yi
);
718 switch (i_divmod(xi
, yi
, &d
, &m
)) {
720 return Py_BuildValue("(ll)", d
, m
);
721 case DIVMOD_OVERFLOW
:
722 return PyLong_Type
.tp_as_number
->nb_divmod((PyObject
*)x
,
730 int_pow(PyIntObject
*v
, PyIntObject
*w
, PyIntObject
*z
)
732 register long iv
, iw
, iz
=0, ix
, temp
, prev
;
733 CONVERT_TO_LONG(v
, iv
);
734 CONVERT_TO_LONG(w
, iw
);
736 if ((PyObject
*)z
!= Py_None
) {
737 PyErr_SetString(PyExc_TypeError
, "pow() 2nd argument "
738 "cannot be negative when 3rd argument specified");
741 /* Return a float. This works because we know that
742 this calls float_pow() which converts its
743 arguments to double. */
744 return PyFloat_Type
.tp_as_number
->nb_power(
745 (PyObject
*)v
, (PyObject
*)w
, (PyObject
*)z
);
747 if ((PyObject
*)z
!= Py_None
) {
748 CONVERT_TO_LONG(z
, iz
);
750 PyErr_SetString(PyExc_ValueError
,
751 "pow() 3rd argument cannot be 0");
756 * XXX: The original exponentiation code stopped looping
757 * when temp hit zero; this code will continue onwards
758 * unnecessarily, but at least it won't cause any errors.
759 * Hopefully the speed improvement from the fast exponentiation
760 * will compensate for the slight inefficiency.
761 * XXX: Better handling of overflows is desperately needed.
766 prev
= ix
; /* Save value for overflow check */
769 * The (unsigned long) cast below ensures that the multiplication
770 * is interpreted as an unsigned operation rather than a signed one
771 * (C99 6.3.1.8p1), thus avoiding the perils of undefined behaviour
772 * from signed arithmetic overflow (C99 6.5p5). See issue #12973.
774 ix
= (unsigned long)ix
* temp
;
776 break; /* Avoid ix / 0 */
777 if (ix
/ temp
!= prev
) {
778 return PyLong_Type
.tp_as_number
->nb_power(
784 iw
>>= 1; /* Shift exponent down by 1 bit */
787 temp
= (unsigned long)temp
* temp
; /* Square the value of temp */
788 if (prev
!= 0 && temp
/ prev
!= prev
) {
789 return PyLong_Type
.tp_as_number
->nb_power(
790 (PyObject
*)v
, (PyObject
*)w
, (PyObject
*)z
);
793 /* If we did a multiplication, perform a modulo */
800 switch (i_divmod(ix
, iz
, &div
, &mod
)) {
804 case DIVMOD_OVERFLOW
:
805 return PyLong_Type
.tp_as_number
->nb_power(
806 (PyObject
*)v
, (PyObject
*)w
, (PyObject
*)z
);
811 return PyInt_FromLong(ix
);
815 int_neg(PyIntObject
*v
)
819 /* check for overflow */
820 if (UNARY_NEG_WOULD_OVERFLOW(a
)) {
821 PyObject
*o
= PyLong_FromLong(a
);
823 PyObject
*result
= PyNumber_Negative(o
);
829 return PyInt_FromLong(-a
);
833 int_abs(PyIntObject
*v
)
842 int_nonzero(PyIntObject
*v
)
844 return v
->ob_ival
!= 0;
848 int_invert(PyIntObject
*v
)
850 return PyInt_FromLong(~v
->ob_ival
);
854 int_lshift(PyIntObject
*v
, PyIntObject
*w
)
857 PyObject
*vv
, *ww
, *result
;
859 CONVERT_TO_LONG(v
, a
);
860 CONVERT_TO_LONG(w
, b
);
862 PyErr_SetString(PyExc_ValueError
, "negative shift count");
865 if (a
== 0 || b
== 0)
868 vv
= PyLong_FromLong(PyInt_AS_LONG(v
));
871 ww
= PyLong_FromLong(PyInt_AS_LONG(w
));
876 result
= PyNumber_Lshift(vv
, ww
);
882 if (a
!= Py_ARITHMETIC_RIGHT_SHIFT(long, c
, b
)) {
883 vv
= PyLong_FromLong(PyInt_AS_LONG(v
));
886 ww
= PyLong_FromLong(PyInt_AS_LONG(w
));
891 result
= PyNumber_Lshift(vv
, ww
);
896 return PyInt_FromLong(c
);
900 int_rshift(PyIntObject
*v
, PyIntObject
*w
)
903 CONVERT_TO_LONG(v
, a
);
904 CONVERT_TO_LONG(w
, b
);
906 PyErr_SetString(PyExc_ValueError
, "negative shift count");
909 if (a
== 0 || b
== 0)
918 a
= Py_ARITHMETIC_RIGHT_SHIFT(long, a
, b
);
920 return PyInt_FromLong(a
);
924 int_and(PyIntObject
*v
, PyIntObject
*w
)
927 CONVERT_TO_LONG(v
, a
);
928 CONVERT_TO_LONG(w
, b
);
929 return PyInt_FromLong(a
& b
);
933 int_xor(PyIntObject
*v
, PyIntObject
*w
)
936 CONVERT_TO_LONG(v
, a
);
937 CONVERT_TO_LONG(w
, b
);
938 return PyInt_FromLong(a
^ b
);
942 int_or(PyIntObject
*v
, PyIntObject
*w
)
945 CONVERT_TO_LONG(v
, a
);
946 CONVERT_TO_LONG(w
, b
);
947 return PyInt_FromLong(a
| b
);
951 int_coerce(PyObject
**pv
, PyObject
**pw
)
953 if (PyInt_Check(*pw
)) {
958 return 1; /* Can't do it */
962 int_int(PyIntObject
*v
)
964 if (PyInt_CheckExact(v
))
967 v
= (PyIntObject
*)PyInt_FromLong(v
->ob_ival
);
968 return (PyObject
*)v
;
972 int_long(PyIntObject
*v
)
974 return PyLong_FromLong((v
-> ob_ival
));
977 static const unsigned char BitLengthTable
[32] = {
978 0, 1, 2, 2, 3, 3, 3, 3, 4, 4, 4, 4, 4, 4, 4, 4,
979 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5
983 bits_in_ulong(unsigned long d
)
990 d_bits
+= (int)BitLengthTable
[d
];
994 #if 8*SIZEOF_LONG-1 <= DBL_MANT_DIG
995 /* Every Python int can be exactly represented as a float. */
998 int_float(PyIntObject
*v
)
1000 return PyFloat_FromDouble((double)(v
-> ob_ival
));
1004 /* Here not all Python ints are exactly representable as floats, so we may
1005 have to round. We do this manually, since the C standards don't specify
1006 whether converting an integer to a float rounds up or down */
1009 int_float(PyIntObject
*v
)
1011 unsigned long abs_ival
, lsb
;
1015 abs_ival
= 0U-(unsigned long)v
->ob_ival
;
1017 abs_ival
= (unsigned long)v
->ob_ival
;
1018 if (abs_ival
< (1L << DBL_MANT_DIG
))
1019 /* small integer; no need to round */
1020 return PyFloat_FromDouble((double)v
->ob_ival
);
1022 /* Round abs_ival to MANT_DIG significant bits, using the
1023 round-half-to-even rule. abs_ival & lsb picks out the 'rounding'
1024 bit: the first bit after the most significant MANT_DIG bits of
1025 abs_ival. We round up if this bit is set, provided that either:
1027 (1) abs_ival isn't exactly halfway between two floats, in which
1028 case at least one of the bits following the rounding bit must be
1029 set; i.e., abs_ival & lsb-1 != 0, or:
1031 (2) the resulting rounded value has least significant bit 0; or
1032 in other words the bit above the rounding bit is set (this is the
1033 'to-even' bit of round-half-to-even); i.e., abs_ival & 2*lsb != 0
1035 The condition "(1) or (2)" equates to abs_ival & 3*lsb-1 != 0. */
1037 lsb
= 1L << (bits_in_ulong(abs_ival
)-DBL_MANT_DIG
-1);
1038 round_up
= (abs_ival
& lsb
) && (abs_ival
& (3*lsb
-1));
1042 return PyFloat_FromDouble(v
->ob_ival
< 0 ?
1050 int_oct(PyIntObject
*v
)
1052 return _PyInt_Format(v
, 8, 0);
1056 int_hex(PyIntObject
*v
)
1058 return _PyInt_Format(v
, 16, 0);
1062 int_subtype_new(PyTypeObject
*type
, PyObject
*args
, PyObject
*kwds
);
1065 int_new(PyTypeObject
*type
, PyObject
*args
, PyObject
*kwds
)
1069 static char *kwlist
[] = {"x", "base", 0};
1071 if (type
!= &PyInt_Type
)
1072 return int_subtype_new(type
, args
, kwds
); /* Wimp out */
1073 if (!PyArg_ParseTupleAndKeywords(args
, kwds
, "|Oi:int", kwlist
,
1078 PyErr_SetString(PyExc_TypeError
,
1079 "int() missing string argument");
1082 return PyInt_FromLong(0L);
1085 return PyNumber_Int(x
);
1086 if (PyString_Check(x
)) {
1087 /* Since PyInt_FromString doesn't have a length parameter,
1088 * check here for possible NULs in the string. */
1089 char *string
= PyString_AS_STRING(x
);
1090 if (strlen(string
) != PyString_Size(x
)) {
1091 /* create a repr() of the input string,
1092 * just like PyInt_FromString does */
1094 srepr
= PyObject_Repr(x
);
1097 PyErr_Format(PyExc_ValueError
,
1098 "invalid literal for int() with base %d: %s",
1099 base
, PyString_AS_STRING(srepr
));
1103 return PyInt_FromString(string
, NULL
, base
);
1105 #ifdef Py_USING_UNICODE
1106 if (PyUnicode_Check(x
))
1107 return PyInt_FromUnicode(PyUnicode_AS_UNICODE(x
),
1108 PyUnicode_GET_SIZE(x
),
1111 PyErr_SetString(PyExc_TypeError
,
1112 "int() can't convert non-string with explicit base");
1116 /* Wimpy, slow approach to tp_new calls for subtypes of int:
1117 first create a regular int from whatever arguments we got,
1118 then allocate a subtype instance and initialize its ob_ival
1119 from the regular int. The regular int is then thrown away.
1122 int_subtype_new(PyTypeObject
*type
, PyObject
*args
, PyObject
*kwds
)
1124 PyObject
*tmp
, *newobj
;
1127 assert(PyType_IsSubtype(type
, &PyInt_Type
));
1128 tmp
= int_new(&PyInt_Type
, args
, kwds
);
1131 if (!PyInt_Check(tmp
)) {
1132 ival
= PyLong_AsLong(tmp
);
1133 if (ival
== -1 && PyErr_Occurred()) {
1138 ival
= ((PyIntObject
*)tmp
)->ob_ival
;
1141 newobj
= type
->tp_alloc(type
, 0);
1142 if (newobj
== NULL
) {
1146 ((PyIntObject
*)newobj
)->ob_ival
= ival
;
1152 int_getnewargs(PyIntObject
*v
)
1154 return Py_BuildValue("(l)", v
->ob_ival
);
1158 int_get0(PyIntObject
*v
, void *context
) {
1159 return PyInt_FromLong(0L);
1163 int_get1(PyIntObject
*v
, void *context
) {
1164 return PyInt_FromLong(1L);
1167 /* Convert an integer to a decimal string. On many platforms, this
1168 will be significantly faster than the general arbitrary-base
1169 conversion machinery in _PyInt_Format, thanks to optimization
1170 opportunities offered by division by a compile-time constant. */
1172 int_to_decimal_string(PyIntObject
*v
) {
1173 char buf
[sizeof(long)*CHAR_BIT
/3+6], *p
, *bufend
;
1174 long n
= v
->ob_ival
;
1176 p
= bufend
= buf
+ sizeof(buf
);
1177 absn
= n
< 0 ? 0UL - n
: n
;
1179 *--p
= '0' + (char)(absn
% 10);
1184 return PyString_FromStringAndSize(p
, bufend
- p
);
1187 /* Convert an integer to the given base. Returns a string.
1188 If base is 2, 8 or 16, add the proper prefix '0b', '0o' or '0x'.
1189 If newstyle is zero, then use the pre-2.6 behavior of octal having
1191 PyAPI_FUNC(PyObject
*)
1192 _PyInt_Format(PyIntObject
*v
, int base
, int newstyle
)
1194 /* There are no doubt many, many ways to optimize this, using code
1195 similar to _PyLong_Format */
1196 long n
= v
->ob_ival
;
1197 int negative
= n
< 0;
1198 int is_zero
= n
== 0;
1200 /* For the reasoning behind this size, see
1201 http://c-faq.com/misc/hexio.html. Then, add a few bytes for
1202 the possible sign and prefix "0[box]" */
1203 char buf
[sizeof(n
)*CHAR_BIT
+6];
1205 /* Start by pointing to the end of the buffer. We fill in from
1206 the back forward. */
1207 char* p
= &buf
[sizeof(buf
)];
1209 assert(base
>= 2 && base
<= 36);
1211 /* Special case base 10, for speed */
1213 return int_to_decimal_string(v
);
1216 /* I'd use i_divmod, except it doesn't produce the results
1217 I want when n is negative. So just duplicate the salient
1219 long div
= n
/ base
;
1220 long mod
= n
- div
* base
;
1222 /* convert abs(mod) to the right character in [0-9, a-z] */
1223 char cdigit
= (char)(mod
< 0 ? -mod
: mod
);
1224 cdigit
+= (cdigit
< 10) ? '0' : 'a'-10;
1234 else if (base
== 8) {
1243 else if (base
== 16) {
1249 *--p
= '0' + base
%10;
1251 *--p
= '0' + base
/10;
1256 return PyString_FromStringAndSize(p
, &buf
[sizeof(buf
)] - p
);
1260 int__format__(PyObject
*self
, PyObject
*args
)
1262 PyObject
*format_spec
;
1264 if (!PyArg_ParseTuple(args
, "O:__format__", &format_spec
))
1266 if (PyBytes_Check(format_spec
))
1267 return _PyInt_FormatAdvanced(self
,
1268 PyBytes_AS_STRING(format_spec
),
1269 PyBytes_GET_SIZE(format_spec
));
1270 if (PyUnicode_Check(format_spec
)) {
1271 /* Convert format_spec to a str */
1273 PyObject
*str_spec
= PyObject_Str(format_spec
);
1275 if (str_spec
== NULL
)
1278 result
= _PyInt_FormatAdvanced(self
,
1279 PyBytes_AS_STRING(str_spec
),
1280 PyBytes_GET_SIZE(str_spec
));
1282 Py_DECREF(str_spec
);
1285 PyErr_SetString(PyExc_TypeError
, "__format__ requires str or unicode");
1290 int_bit_length(PyIntObject
*v
)
1295 /* avoid undefined behaviour when v->ob_ival == -LONG_MAX-1 */
1296 n
= 0U-(unsigned long)v
->ob_ival
;
1298 n
= (unsigned long)v
->ob_ival
;
1300 return PyInt_FromLong(bits_in_ulong(n
));
1303 PyDoc_STRVAR(int_bit_length_doc
,
1304 "int.bit_length() -> int\n\
1306 Number of bits necessary to represent self in binary.\n\
1309 >>> (37).bit_length()\n\
1314 int_is_finite(PyObject
*v
)
1320 static PyMethodDef int_methods
[] = {
1321 {"conjugate", (PyCFunction
)int_int
, METH_NOARGS
,
1322 "Returns self, the complex conjugate of any int."},
1323 {"bit_length", (PyCFunction
)int_bit_length
, METH_NOARGS
,
1324 int_bit_length_doc
},
1326 {"is_finite", (PyCFunction
)int_is_finite
, METH_NOARGS
,
1327 "Returns always True."},
1329 {"__trunc__", (PyCFunction
)int_int
, METH_NOARGS
,
1330 "Truncating an Integral returns itself."},
1331 {"__getnewargs__", (PyCFunction
)int_getnewargs
, METH_NOARGS
},
1332 {"__format__", (PyCFunction
)int__format__
, METH_VARARGS
},
1333 {NULL
, NULL
} /* sentinel */
1336 static PyGetSetDef int_getset
[] = {
1338 (getter
)int_int
, (setter
)NULL
,
1339 "the real part of a complex number",
1342 (getter
)int_get0
, (setter
)NULL
,
1343 "the imaginary part of a complex number",
1346 (getter
)int_int
, (setter
)NULL
,
1347 "the numerator of a rational number in lowest terms",
1350 (getter
)int_get1
, (setter
)NULL
,
1351 "the denominator of a rational number in lowest terms",
1353 {NULL
} /* Sentinel */
1356 PyDoc_STRVAR(int_doc
,
1357 "int(x=0) -> int or long\n\
1358 int(x, base=10) -> int or long\n\
1360 Convert a number or string to an integer, or return 0 if no arguments\n\
1361 are given. If x is floating point, the conversion truncates towards zero.\n\
1362 If x is outside the integer range, the function returns a long instead.\n\
1364 If x is not a number or if base is given, then x must be a string or\n\
1365 Unicode object representing an integer literal in the given base. The\n\
1366 literal can be preceded by '+' or '-' and be surrounded by whitespace.\n\
1367 The base defaults to 10. Valid bases are 0 and 2-36. Base 0 means to\n\
1368 interpret the base from the string as an integer literal.\n\
1369 >>> int('0b100', base=0)\n\
1372 static PyNumberMethods int_as_number
= {
1373 (binaryfunc
)int_add
, /*nb_add*/
1374 (binaryfunc
)int_sub
, /*nb_subtract*/
1375 (binaryfunc
)int_mul
, /*nb_multiply*/
1376 (binaryfunc
)int_classic_div
, /*nb_divide*/
1377 (binaryfunc
)int_mod
, /*nb_remainder*/
1378 (binaryfunc
)int_divmod
, /*nb_divmod*/
1379 (ternaryfunc
)int_pow
, /*nb_power*/
1380 (unaryfunc
)int_neg
, /*nb_negative*/
1381 (unaryfunc
)int_int
, /*nb_positive*/
1382 (unaryfunc
)int_abs
, /*nb_absolute*/
1383 (inquiry
)int_nonzero
, /*nb_nonzero*/
1384 (unaryfunc
)int_invert
, /*nb_invert*/
1385 (binaryfunc
)int_lshift
, /*nb_lshift*/
1386 (binaryfunc
)int_rshift
, /*nb_rshift*/
1387 (binaryfunc
)int_and
, /*nb_and*/
1388 (binaryfunc
)int_xor
, /*nb_xor*/
1389 (binaryfunc
)int_or
, /*nb_or*/
1390 int_coerce
, /*nb_coerce*/
1391 (unaryfunc
)int_int
, /*nb_int*/
1392 (unaryfunc
)int_long
, /*nb_long*/
1393 (unaryfunc
)int_float
, /*nb_float*/
1394 (unaryfunc
)int_oct
, /*nb_oct*/
1395 (unaryfunc
)int_hex
, /*nb_hex*/
1396 0, /*nb_inplace_add*/
1397 0, /*nb_inplace_subtract*/
1398 0, /*nb_inplace_multiply*/
1399 0, /*nb_inplace_divide*/
1400 0, /*nb_inplace_remainder*/
1401 0, /*nb_inplace_power*/
1402 0, /*nb_inplace_lshift*/
1403 0, /*nb_inplace_rshift*/
1404 0, /*nb_inplace_and*/
1405 0, /*nb_inplace_xor*/
1406 0, /*nb_inplace_or*/
1407 (binaryfunc
)int_div
, /* nb_floor_divide */
1408 (binaryfunc
)int_true_divide
, /* nb_true_divide */
1409 0, /* nb_inplace_floor_divide */
1410 0, /* nb_inplace_true_divide */
1411 (unaryfunc
)int_int
, /* nb_index */
1414 PyTypeObject PyInt_Type
= {
1415 PyVarObject_HEAD_INIT(&PyType_Type
, 0)
1417 sizeof(PyIntObject
),
1419 (destructor
)int_dealloc
, /* tp_dealloc */
1420 (printfunc
)int_print
, /* tp_print */
1423 (cmpfunc
)int_compare
, /* tp_compare */
1424 (reprfunc
)int_to_decimal_string
, /* tp_repr */
1425 &int_as_number
, /* tp_as_number */
1426 0, /* tp_as_sequence */
1427 0, /* tp_as_mapping */
1428 (hashfunc
)int_hash
, /* tp_hash */
1430 (reprfunc
)int_to_decimal_string
, /* tp_str */
1431 PyObject_GenericGetAttr
, /* tp_getattro */
1432 0, /* tp_setattro */
1433 0, /* tp_as_buffer */
1434 Py_TPFLAGS_DEFAULT
| Py_TPFLAGS_CHECKTYPES
|
1435 Py_TPFLAGS_BASETYPE
| Py_TPFLAGS_INT_SUBCLASS
, /* tp_flags */
1436 int_doc
, /* tp_doc */
1437 0, /* tp_traverse */
1439 0, /* tp_richcompare */
1440 0, /* tp_weaklistoffset */
1442 0, /* tp_iternext */
1443 int_methods
, /* tp_methods */
1445 int_getset
, /* tp_getset */
1448 0, /* tp_descr_get */
1449 0, /* tp_descr_set */
1450 0, /* tp_dictoffset */
1453 int_new
, /* tp_new */
1454 (freefunc
)int_free
, /* tp_free */
1462 #if NSMALLNEGINTS + NSMALLPOSINTS > 0
1463 for (ival
= -NSMALLNEGINTS
; ival
< NSMALLPOSINTS
; ival
++) {
1464 if (!free_list
&& (free_list
= fill_free_list()) == NULL
)
1466 /* PyObject_New is inlined */
1468 free_list
= (PyIntObject
*)Py_TYPE(v
);
1469 PyObject_INIT(v
, &PyInt_Type
);
1471 small_ints
[ival
+ NSMALLNEGINTS
] = v
;
1478 PyInt_ClearFreeList(void)
1481 PyIntBlock
*list
, *next
;
1483 int u
; /* remaining unfreed ints per block */
1484 int freelist_size
= 0;
1489 while (list
!= NULL
) {
1491 for (i
= 0, p
= &list
->objects
[0];
1494 if (PyInt_CheckExact(p
) && p
->ob_refcnt
!= 0)
1499 list
->next
= block_list
;
1501 for (i
= 0, p
= &list
->objects
[0];
1504 if (!PyInt_CheckExact(p
) ||
1505 p
->ob_refcnt
== 0) {
1506 Py_TYPE(p
) = (struct _typeobject
*)
1510 #if NSMALLNEGINTS + NSMALLPOSINTS > 0
1511 else if (-NSMALLNEGINTS
<= p
->ob_ival
&&
1512 p
->ob_ival
< NSMALLPOSINTS
&&
1513 small_ints
[p
->ob_ival
+
1514 NSMALLNEGINTS
] == NULL
) {
1516 small_ints
[p
->ob_ival
+
1529 return freelist_size
;
1538 int u
; /* total unfreed ints per block */
1540 #if NSMALLNEGINTS + NSMALLPOSINTS > 0
1543 i
= NSMALLNEGINTS
+ NSMALLPOSINTS
;
1550 u
= PyInt_ClearFreeList();
1551 if (!Py_VerboseFlag
)
1553 fprintf(stderr
, "# cleanup ints");
1555 fprintf(stderr
, "\n");
1559 ": %d unfreed int%s\n",
1560 u
, u
== 1 ? "" : "s");
1562 if (Py_VerboseFlag
> 1) {
1564 while (list
!= NULL
) {
1565 for (i
= 0, p
= &list
->objects
[0];
1568 if (PyInt_CheckExact(p
) && p
->ob_refcnt
!= 0)
1569 /* XXX(twouters) cast refcount to
1570 long until %zd is universally
1574 "# <int at %p, refcnt=%ld, val=%ld>\n",
1575 p
, (long)p
->ob_refcnt
,