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 "nb_int should return int object");
186 val
= PyInt_AS_LONG(io
);
193 PyInt_AsSsize_t(register PyObject
*op
)
195 #if SIZEOF_SIZE_T != SIZEOF_LONG
202 PyErr_SetString(PyExc_TypeError
, "an integer is required");
207 return PyInt_AS_LONG((PyIntObject
*) op
);
208 if (PyLong_Check(op
))
209 return _PyLong_AsSsize_t(op
);
210 #if SIZEOF_SIZE_T == SIZEOF_LONG
211 return PyInt_AsLong(op
);
214 if ((nb
= Py_TYPE(op
)->tp_as_number
) == NULL
||
215 (nb
->nb_int
== NULL
&& nb
->nb_long
== 0)) {
216 PyErr_SetString(PyExc_TypeError
, "an integer is required");
220 if (nb
->nb_long
!= 0)
221 io
= (PyIntObject
*) (*nb
->nb_long
) (op
);
223 io
= (PyIntObject
*) (*nb
->nb_int
) (op
);
226 if (!PyInt_Check(io
)) {
227 if (PyLong_Check(io
)) {
228 /* got a long? => retry int conversion */
229 val
= _PyLong_AsSsize_t((PyObject
*)io
);
231 if ((val
== -1) && PyErr_Occurred())
238 PyErr_SetString(PyExc_TypeError
,
239 "nb_int should return int object");
244 val
= PyInt_AS_LONG(io
);
252 PyInt_AsUnsignedLongMask(register PyObject
*op
)
258 if (op
&& PyInt_Check(op
))
259 return PyInt_AS_LONG((PyIntObject
*) op
);
260 if (op
&& PyLong_Check(op
))
261 return PyLong_AsUnsignedLongMask(op
);
263 if (op
== NULL
|| (nb
= Py_TYPE(op
)->tp_as_number
) == NULL
||
264 nb
->nb_int
== NULL
) {
265 PyErr_SetString(PyExc_TypeError
, "an integer is required");
266 return (unsigned long)-1;
269 io
= (PyIntObject
*) (*nb
->nb_int
) (op
);
271 return (unsigned long)-1;
272 if (!PyInt_Check(io
)) {
273 if (PyLong_Check(io
)) {
274 val
= PyLong_AsUnsignedLongMask((PyObject
*)io
);
276 if (PyErr_Occurred())
277 return (unsigned long)-1;
283 PyErr_SetString(PyExc_TypeError
,
284 "nb_int should return int object");
285 return (unsigned long)-1;
289 val
= PyInt_AS_LONG(io
);
295 #ifdef HAVE_LONG_LONG
296 unsigned PY_LONG_LONG
297 PyInt_AsUnsignedLongLongMask(register PyObject
*op
)
301 unsigned PY_LONG_LONG val
;
303 if (op
&& PyInt_Check(op
))
304 return PyInt_AS_LONG((PyIntObject
*) op
);
305 if (op
&& PyLong_Check(op
))
306 return PyLong_AsUnsignedLongLongMask(op
);
308 if (op
== NULL
|| (nb
= Py_TYPE(op
)->tp_as_number
) == NULL
||
309 nb
->nb_int
== NULL
) {
310 PyErr_SetString(PyExc_TypeError
, "an integer is required");
311 return (unsigned PY_LONG_LONG
)-1;
314 io
= (PyIntObject
*) (*nb
->nb_int
) (op
);
316 return (unsigned PY_LONG_LONG
)-1;
317 if (!PyInt_Check(io
)) {
318 if (PyLong_Check(io
)) {
319 val
= PyLong_AsUnsignedLongLongMask((PyObject
*)io
);
321 if (PyErr_Occurred())
322 return (unsigned PY_LONG_LONG
)-1;
328 PyErr_SetString(PyExc_TypeError
,
329 "nb_int should return int object");
330 return (unsigned PY_LONG_LONG
)-1;
334 val
= PyInt_AS_LONG(io
);
342 PyInt_FromString(char *s
, char **pend
, int base
)
347 PyObject
*sobj
, *srepr
;
349 if ((base
!= 0 && base
< 2) || base
> 36) {
350 PyErr_SetString(PyExc_ValueError
,
351 "int() base must be >= 2 and <= 36");
355 while (*s
&& isspace(Py_CHARMASK(*s
)))
358 if (base
== 0 && s
[0] == '0') {
359 x
= (long) PyOS_strtoul(s
, &end
, base
);
361 return PyLong_FromString(s
, pend
, base
);
364 x
= PyOS_strtol(s
, &end
, base
);
365 if (end
== s
|| !isalnum(Py_CHARMASK(end
[-1])))
367 while (*end
&& isspace(Py_CHARMASK(*end
)))
371 slen
= strlen(s
) < 200 ? strlen(s
) : 200;
372 sobj
= PyString_FromStringAndSize(s
, slen
);
375 srepr
= PyObject_Repr(sobj
);
379 PyErr_Format(PyExc_ValueError
,
380 "invalid literal for int() with base %d: %s",
381 base
, PyString_AS_STRING(srepr
));
386 return PyLong_FromString(s
, pend
, base
);
389 return PyInt_FromLong(x
);
392 #ifdef Py_USING_UNICODE
394 PyInt_FromUnicode(Py_UNICODE
*s
, Py_ssize_t length
, int base
)
397 char *buffer
= (char *)PyMem_MALLOC(length
+1);
400 return PyErr_NoMemory();
402 if (PyUnicode_EncodeDecimal(s
, length
, buffer
, NULL
)) {
406 result
= PyInt_FromString(buffer
, NULL
, base
);
414 /* Integers are seen as the "smallest" of all numeric types and thus
415 don't have any knowledge about conversion of other types to
418 #define CONVERT_TO_LONG(obj, lng) \
419 if (PyInt_Check(obj)) { \
420 lng = PyInt_AS_LONG(obj); \
423 Py_INCREF(Py_NotImplemented); \
424 return Py_NotImplemented; \
429 int_print(PyIntObject
*v
, FILE *fp
, int flags
)
430 /* flags -- not used but required by interface */
432 long int_val
= v
->ob_ival
;
433 Py_BEGIN_ALLOW_THREADS
434 fprintf(fp
, "%ld", int_val
);
440 int_repr(PyIntObject
*v
)
442 return _PyInt_Format(v
, 10, 0);
446 int_compare(PyIntObject
*v
, PyIntObject
*w
)
448 register long i
= v
->ob_ival
;
449 register long j
= w
->ob_ival
;
450 return (i
< j
) ? -1 : (i
> j
) ? 1 : 0;
454 int_hash(PyIntObject
*v
)
456 /* XXX If this is changed, you also need to change the way
457 Python's long, float and complex types are hashed. */
458 long x
= v
-> ob_ival
;
465 int_add(PyIntObject
*v
, PyIntObject
*w
)
467 register long a
, b
, x
;
468 CONVERT_TO_LONG(v
, a
);
469 CONVERT_TO_LONG(w
, b
);
471 if ((x
^a
) >= 0 || (x
^b
) >= 0)
472 return PyInt_FromLong(x
);
473 return PyLong_Type
.tp_as_number
->nb_add((PyObject
*)v
, (PyObject
*)w
);
477 int_sub(PyIntObject
*v
, PyIntObject
*w
)
479 register long a
, b
, x
;
480 CONVERT_TO_LONG(v
, a
);
481 CONVERT_TO_LONG(w
, b
);
483 if ((x
^a
) >= 0 || (x
^~b
) >= 0)
484 return PyInt_FromLong(x
);
485 return PyLong_Type
.tp_as_number
->nb_subtract((PyObject
*)v
,
490 Integer overflow checking for * is painful: Python tried a couple ways, but
491 they didn't work on all platforms, or failed in endcases (a product of
492 -sys.maxint-1 has been a particular pain).
496 The native long product x*y is either exactly right or *way* off, being
497 just the last n bits of the true product, where n is the number of bits
498 in a long (the delivered product is the true product plus i*2**n for
501 The native double product (double)x * (double)y is subject to three
502 rounding errors: on a sizeof(long)==8 box, each cast to double can lose
503 info, and even on a sizeof(long)==4 box, the multiplication can lose info.
504 But, unlike the native long product, it's not in *range* trouble: even
505 if sizeof(long)==32 (256-bit longs), the product easily fits in the
506 dynamic range of a double. So the leading 50 (or so) bits of the double
509 We check these two ways against each other, and declare victory if they're
510 approximately the same. Else, because the native long product is the only
511 one that can lose catastrophic amounts of information, it's the native long
512 product that must have overflowed.
516 int_mul(PyObject
*v
, PyObject
*w
)
519 long longprod
; /* a*b in native long arithmetic */
520 double doubled_longprod
; /* (double)longprod */
521 double doubleprod
; /* (double)a * (double)b */
523 CONVERT_TO_LONG(v
, a
);
524 CONVERT_TO_LONG(w
, b
);
526 doubleprod
= (double)a
* (double)b
;
527 doubled_longprod
= (double)longprod
;
529 /* Fast path for normal case: small multiplicands, and no info
530 is lost in either method. */
531 if (doubled_longprod
== doubleprod
)
532 return PyInt_FromLong(longprod
);
534 /* Somebody somewhere lost info. Close enough, or way off? Note
535 that a != 0 and b != 0 (else doubled_longprod == doubleprod == 0).
536 The difference either is or isn't significant compared to the
537 true value (of which doubleprod is a good approximation).
540 const double diff
= doubled_longprod
- doubleprod
;
541 const double absdiff
= diff
>= 0.0 ? diff
: -diff
;
542 const double absprod
= doubleprod
>= 0.0 ? doubleprod
:
544 /* absdiff/absprod <= 1/32 iff
545 32 * absdiff <= absprod -- 5 good bits is "close enough" */
546 if (32.0 * absdiff
<= absprod
)
547 return PyInt_FromLong(longprod
);
549 return PyLong_Type
.tp_as_number
->nb_multiply(v
, w
);
553 /* Integer overflow checking for unary negation: on a 2's-complement
554 * box, -x overflows iff x is the most negative long. In this case we
555 * get -x == x. However, -x is undefined (by C) if x /is/ the most
556 * negative long (it's a signed overflow case), and some compilers care.
557 * So we cast x to unsigned long first. However, then other compilers
558 * warn about applying unary minus to an unsigned operand. Hence the
561 #define UNARY_NEG_WOULD_OVERFLOW(x) \
562 ((x) < 0 && (unsigned long)(x) == 0-(unsigned long)(x))
564 /* Return type of i_divmod */
566 DIVMOD_OK
, /* Correct result */
567 DIVMOD_OVERFLOW
, /* Overflow, try again using longs */
568 DIVMOD_ERROR
/* Exception raised */
571 static enum divmod_result
572 i_divmod(register long x
, register long y
,
573 long *p_xdivy
, long *p_xmody
)
578 PyErr_SetString(PyExc_ZeroDivisionError
,
579 "integer division or modulo by zero");
582 /* (-sys.maxint-1)/-1 is the only overflow case. */
583 if (y
== -1 && UNARY_NEG_WOULD_OVERFLOW(x
))
584 return DIVMOD_OVERFLOW
;
586 xmody
= x
- xdivy
* y
;
587 /* If the signs of x and y differ, and the remainder is non-0,
588 * C89 doesn't define whether xdivy is now the floor or the
589 * ceiling of the infinitely precise quotient. We want the floor,
590 * and we have it iff the remainder's sign matches y's.
592 if (xmody
&& ((y
^ xmody
) < 0) /* i.e. and signs differ */) {
595 assert(xmody
&& ((y
^ xmody
) >= 0));
603 int_div(PyIntObject
*x
, PyIntObject
*y
)
607 CONVERT_TO_LONG(x
, xi
);
608 CONVERT_TO_LONG(y
, yi
);
609 switch (i_divmod(xi
, yi
, &d
, &m
)) {
611 return PyInt_FromLong(d
);
612 case DIVMOD_OVERFLOW
:
613 return PyLong_Type
.tp_as_number
->nb_divide((PyObject
*)x
,
621 int_classic_div(PyIntObject
*x
, PyIntObject
*y
)
625 CONVERT_TO_LONG(x
, xi
);
626 CONVERT_TO_LONG(y
, yi
);
627 if (Py_DivisionWarningFlag
&&
628 PyErr_Warn(PyExc_DeprecationWarning
, "classic int division") < 0)
630 switch (i_divmod(xi
, yi
, &d
, &m
)) {
632 return PyInt_FromLong(d
);
633 case DIVMOD_OVERFLOW
:
634 return PyLong_Type
.tp_as_number
->nb_divide((PyObject
*)x
,
642 int_true_divide(PyObject
*v
, PyObject
*w
)
644 /* If they aren't both ints, give someone else a chance. In
645 particular, this lets int/long get handled by longs, which
646 underflows to 0 gracefully if the long is too big to convert
648 if (PyInt_Check(v
) && PyInt_Check(w
))
649 return PyFloat_Type
.tp_as_number
->nb_true_divide(v
, w
);
650 Py_INCREF(Py_NotImplemented
);
651 return Py_NotImplemented
;
655 int_mod(PyIntObject
*x
, PyIntObject
*y
)
659 CONVERT_TO_LONG(x
, xi
);
660 CONVERT_TO_LONG(y
, yi
);
661 switch (i_divmod(xi
, yi
, &d
, &m
)) {
663 return PyInt_FromLong(m
);
664 case DIVMOD_OVERFLOW
:
665 return PyLong_Type
.tp_as_number
->nb_remainder((PyObject
*)x
,
673 int_divmod(PyIntObject
*x
, PyIntObject
*y
)
677 CONVERT_TO_LONG(x
, xi
);
678 CONVERT_TO_LONG(y
, yi
);
679 switch (i_divmod(xi
, yi
, &d
, &m
)) {
681 return Py_BuildValue("(ll)", d
, m
);
682 case DIVMOD_OVERFLOW
:
683 return PyLong_Type
.tp_as_number
->nb_divmod((PyObject
*)x
,
691 int_pow(PyIntObject
*v
, PyIntObject
*w
, PyIntObject
*z
)
693 register long iv
, iw
, iz
=0, ix
, temp
, prev
;
694 CONVERT_TO_LONG(v
, iv
);
695 CONVERT_TO_LONG(w
, iw
);
697 if ((PyObject
*)z
!= Py_None
) {
698 PyErr_SetString(PyExc_TypeError
, "pow() 2nd argument "
699 "cannot be negative when 3rd argument specified");
702 /* Return a float. This works because we know that
703 this calls float_pow() which converts its
704 arguments to double. */
705 return PyFloat_Type
.tp_as_number
->nb_power(
706 (PyObject
*)v
, (PyObject
*)w
, (PyObject
*)z
);
708 if ((PyObject
*)z
!= Py_None
) {
709 CONVERT_TO_LONG(z
, iz
);
711 PyErr_SetString(PyExc_ValueError
,
712 "pow() 3rd argument cannot be 0");
717 * XXX: The original exponentiation code stopped looping
718 * when temp hit zero; this code will continue onwards
719 * unnecessarily, but at least it won't cause any errors.
720 * Hopefully the speed improvement from the fast exponentiation
721 * will compensate for the slight inefficiency.
722 * XXX: Better handling of overflows is desperately needed.
727 prev
= ix
; /* Save value for overflow check */
731 break; /* Avoid ix / 0 */
732 if (ix
/ temp
!= prev
) {
733 return PyLong_Type
.tp_as_number
->nb_power(
739 iw
>>= 1; /* Shift exponent down by 1 bit */
742 temp
*= temp
; /* Square the value of temp */
743 if (prev
!= 0 && temp
/ prev
!= prev
) {
744 return PyLong_Type
.tp_as_number
->nb_power(
745 (PyObject
*)v
, (PyObject
*)w
, (PyObject
*)z
);
748 /* If we did a multiplication, perform a modulo */
755 switch (i_divmod(ix
, iz
, &div
, &mod
)) {
759 case DIVMOD_OVERFLOW
:
760 return PyLong_Type
.tp_as_number
->nb_power(
761 (PyObject
*)v
, (PyObject
*)w
, (PyObject
*)z
);
766 return PyInt_FromLong(ix
);
770 int_neg(PyIntObject
*v
)
774 /* check for overflow */
775 if (UNARY_NEG_WOULD_OVERFLOW(a
)) {
776 PyObject
*o
= PyLong_FromLong(a
);
778 PyObject
*result
= PyNumber_Negative(o
);
784 return PyInt_FromLong(-a
);
788 int_abs(PyIntObject
*v
)
797 int_nonzero(PyIntObject
*v
)
799 return v
->ob_ival
!= 0;
803 int_invert(PyIntObject
*v
)
805 return PyInt_FromLong(~v
->ob_ival
);
809 int_lshift(PyIntObject
*v
, PyIntObject
*w
)
812 PyObject
*vv
, *ww
, *result
;
814 CONVERT_TO_LONG(v
, a
);
815 CONVERT_TO_LONG(w
, b
);
817 PyErr_SetString(PyExc_ValueError
, "negative shift count");
820 if (a
== 0 || b
== 0)
823 vv
= PyLong_FromLong(PyInt_AS_LONG(v
));
826 ww
= PyLong_FromLong(PyInt_AS_LONG(w
));
831 result
= PyNumber_Lshift(vv
, ww
);
837 if (a
!= Py_ARITHMETIC_RIGHT_SHIFT(long, c
, b
)) {
838 vv
= PyLong_FromLong(PyInt_AS_LONG(v
));
841 ww
= PyLong_FromLong(PyInt_AS_LONG(w
));
846 result
= PyNumber_Lshift(vv
, ww
);
851 return PyInt_FromLong(c
);
855 int_rshift(PyIntObject
*v
, PyIntObject
*w
)
858 CONVERT_TO_LONG(v
, a
);
859 CONVERT_TO_LONG(w
, b
);
861 PyErr_SetString(PyExc_ValueError
, "negative shift count");
864 if (a
== 0 || b
== 0)
873 a
= Py_ARITHMETIC_RIGHT_SHIFT(long, a
, b
);
875 return PyInt_FromLong(a
);
879 int_and(PyIntObject
*v
, PyIntObject
*w
)
882 CONVERT_TO_LONG(v
, a
);
883 CONVERT_TO_LONG(w
, b
);
884 return PyInt_FromLong(a
& b
);
888 int_xor(PyIntObject
*v
, PyIntObject
*w
)
891 CONVERT_TO_LONG(v
, a
);
892 CONVERT_TO_LONG(w
, b
);
893 return PyInt_FromLong(a
^ b
);
897 int_or(PyIntObject
*v
, PyIntObject
*w
)
900 CONVERT_TO_LONG(v
, a
);
901 CONVERT_TO_LONG(w
, b
);
902 return PyInt_FromLong(a
| b
);
906 int_coerce(PyObject
**pv
, PyObject
**pw
)
908 if (PyInt_Check(*pw
)) {
913 return 1; /* Can't do it */
917 int_int(PyIntObject
*v
)
919 if (PyInt_CheckExact(v
))
922 v
= (PyIntObject
*)PyInt_FromLong(v
->ob_ival
);
923 return (PyObject
*)v
;
927 int_long(PyIntObject
*v
)
929 return PyLong_FromLong((v
-> ob_ival
));
932 static const unsigned char BitLengthTable
[32] = {
933 0, 1, 2, 2, 3, 3, 3, 3, 4, 4, 4, 4, 4, 4, 4, 4,
934 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5
938 bits_in_ulong(unsigned long d
)
945 d_bits
+= (int)BitLengthTable
[d
];
949 #if 8*SIZEOF_LONG-1 <= DBL_MANT_DIG
950 /* Every Python int can be exactly represented as a float. */
953 int_float(PyIntObject
*v
)
955 return PyFloat_FromDouble((double)(v
-> ob_ival
));
959 /* Here not all Python ints are exactly representable as floats, so we may
960 have to round. We do this manually, since the C standards don't specify
961 whether converting an integer to a float rounds up or down */
964 int_float(PyIntObject
*v
)
966 unsigned long abs_ival
, lsb
;
970 abs_ival
= 0U-(unsigned long)v
->ob_ival
;
972 abs_ival
= (unsigned long)v
->ob_ival
;
973 if (abs_ival
< (1L << DBL_MANT_DIG
))
974 /* small integer; no need to round */
975 return PyFloat_FromDouble((double)v
->ob_ival
);
977 /* Round abs_ival to MANT_DIG significant bits, using the
978 round-half-to-even rule. abs_ival & lsb picks out the 'rounding'
979 bit: the first bit after the most significant MANT_DIG bits of
980 abs_ival. We round up if this bit is set, provided that either:
982 (1) abs_ival isn't exactly halfway between two floats, in which
983 case at least one of the bits following the rounding bit must be
984 set; i.e., abs_ival & lsb-1 != 0, or:
986 (2) the resulting rounded value has least significant bit 0; or
987 in other words the bit above the rounding bit is set (this is the
988 'to-even' bit of round-half-to-even); i.e., abs_ival & 2*lsb != 0
990 The condition "(1) or (2)" equates to abs_ival & 3*lsb-1 != 0. */
992 lsb
= 1L << (bits_in_ulong(abs_ival
)-DBL_MANT_DIG
-1);
993 round_up
= (abs_ival
& lsb
) && (abs_ival
& (3*lsb
-1));
997 return PyFloat_FromDouble(v
->ob_ival
< 0 ?
1005 int_oct(PyIntObject
*v
)
1007 return _PyInt_Format(v
, 8, 0);
1011 int_hex(PyIntObject
*v
)
1013 return _PyInt_Format(v
, 16, 0);
1017 int_subtype_new(PyTypeObject
*type
, PyObject
*args
, PyObject
*kwds
);
1020 int_new(PyTypeObject
*type
, PyObject
*args
, PyObject
*kwds
)
1024 static char *kwlist
[] = {"x", "base", 0};
1026 if (type
!= &PyInt_Type
)
1027 return int_subtype_new(type
, args
, kwds
); /* Wimp out */
1028 if (!PyArg_ParseTupleAndKeywords(args
, kwds
, "|Oi:int", kwlist
,
1032 return PyInt_FromLong(0L);
1034 return PyNumber_Int(x
);
1035 if (PyString_Check(x
)) {
1036 /* Since PyInt_FromString doesn't have a length parameter,
1037 * check here for possible NULs in the string. */
1038 char *string
= PyString_AS_STRING(x
);
1039 if (strlen(string
) != PyString_Size(x
)) {
1040 /* create a repr() of the input string,
1041 * just like PyInt_FromString does */
1043 srepr
= PyObject_Repr(x
);
1046 PyErr_Format(PyExc_ValueError
,
1047 "invalid literal for int() with base %d: %s",
1048 base
, PyString_AS_STRING(srepr
));
1052 return PyInt_FromString(string
, NULL
, base
);
1054 #ifdef Py_USING_UNICODE
1055 if (PyUnicode_Check(x
))
1056 return PyInt_FromUnicode(PyUnicode_AS_UNICODE(x
),
1057 PyUnicode_GET_SIZE(x
),
1060 PyErr_SetString(PyExc_TypeError
,
1061 "int() can't convert non-string with explicit base");
1065 /* Wimpy, slow approach to tp_new calls for subtypes of int:
1066 first create a regular int from whatever arguments we got,
1067 then allocate a subtype instance and initialize its ob_ival
1068 from the regular int. The regular int is then thrown away.
1071 int_subtype_new(PyTypeObject
*type
, PyObject
*args
, PyObject
*kwds
)
1073 PyObject
*tmp
, *newobj
;
1076 assert(PyType_IsSubtype(type
, &PyInt_Type
));
1077 tmp
= int_new(&PyInt_Type
, args
, kwds
);
1080 if (!PyInt_Check(tmp
)) {
1081 ival
= PyLong_AsLong(tmp
);
1082 if (ival
== -1 && PyErr_Occurred()) {
1087 ival
= ((PyIntObject
*)tmp
)->ob_ival
;
1090 newobj
= type
->tp_alloc(type
, 0);
1091 if (newobj
== NULL
) {
1095 ((PyIntObject
*)newobj
)->ob_ival
= ival
;
1101 int_getnewargs(PyIntObject
*v
)
1103 return Py_BuildValue("(l)", v
->ob_ival
);
1107 int_get0(PyIntObject
*v
, void *context
) {
1108 return PyInt_FromLong(0L);
1112 int_get1(PyIntObject
*v
, void *context
) {
1113 return PyInt_FromLong(1L);
1116 /* Convert an integer to the given base. Returns a string.
1117 If base is 2, 8 or 16, add the proper prefix '0b', '0o' or '0x'.
1118 If newstyle is zero, then use the pre-2.6 behavior of octal having
1120 PyAPI_FUNC(PyObject
*)
1121 _PyInt_Format(PyIntObject
*v
, int base
, int newstyle
)
1123 /* There are no doubt many, many ways to optimize this, using code
1124 similar to _PyLong_Format */
1125 long n
= v
->ob_ival
;
1126 int negative
= n
< 0;
1127 int is_zero
= n
== 0;
1129 /* For the reasoning behind this size, see
1130 http://c-faq.com/misc/hexio.html. Then, add a few bytes for
1131 the possible sign and prefix "0[box]" */
1132 char buf
[sizeof(n
)*CHAR_BIT
+6];
1134 /* Start by pointing to the end of the buffer. We fill in from
1135 the back forward. */
1136 char* p
= &buf
[sizeof(buf
)];
1138 assert(base
>= 2 && base
<= 36);
1141 /* I'd use i_divmod, except it doesn't produce the results
1142 I want when n is negative. So just duplicate the salient
1144 long div
= n
/ base
;
1145 long mod
= n
- div
* base
;
1147 /* convert abs(mod) to the right character in [0-9, a-z] */
1148 char cdigit
= (char)(mod
< 0 ? -mod
: mod
);
1149 cdigit
+= (cdigit
< 10) ? '0' : 'a'-10;
1159 else if (base
== 8) {
1168 else if (base
== 16) {
1172 else if (base
!= 10) {
1174 *--p
= '0' + base
%10;
1176 *--p
= '0' + base
/10;
1181 return PyString_FromStringAndSize(p
, &buf
[sizeof(buf
)] - p
);
1185 int__format__(PyObject
*self
, PyObject
*args
)
1187 PyObject
*format_spec
;
1189 if (!PyArg_ParseTuple(args
, "O:__format__", &format_spec
))
1191 if (PyBytes_Check(format_spec
))
1192 return _PyInt_FormatAdvanced(self
,
1193 PyBytes_AS_STRING(format_spec
),
1194 PyBytes_GET_SIZE(format_spec
));
1195 if (PyUnicode_Check(format_spec
)) {
1196 /* Convert format_spec to a str */
1198 PyObject
*str_spec
= PyObject_Str(format_spec
);
1200 if (str_spec
== NULL
)
1203 result
= _PyInt_FormatAdvanced(self
,
1204 PyBytes_AS_STRING(str_spec
),
1205 PyBytes_GET_SIZE(str_spec
));
1207 Py_DECREF(str_spec
);
1210 PyErr_SetString(PyExc_TypeError
, "__format__ requires str or unicode");
1215 int_bit_length(PyIntObject
*v
)
1220 /* avoid undefined behaviour when v->ob_ival == -LONG_MAX-1 */
1221 n
= 0U-(unsigned long)v
->ob_ival
;
1223 n
= (unsigned long)v
->ob_ival
;
1225 return PyInt_FromLong(bits_in_ulong(n
));
1228 PyDoc_STRVAR(int_bit_length_doc
,
1229 "int.bit_length() -> int\n\
1231 Number of bits necessary to represent self in binary.\n\
1234 >>> (37).bit_length()\n\
1239 int_is_finite(PyObject
*v
)
1245 static PyMethodDef int_methods
[] = {
1246 {"conjugate", (PyCFunction
)int_int
, METH_NOARGS
,
1247 "Returns self, the complex conjugate of any int."},
1248 {"bit_length", (PyCFunction
)int_bit_length
, METH_NOARGS
,
1249 int_bit_length_doc
},
1251 {"is_finite", (PyCFunction
)int_is_finite
, METH_NOARGS
,
1252 "Returns always True."},
1254 {"__trunc__", (PyCFunction
)int_int
, METH_NOARGS
,
1255 "Truncating an Integral returns itself."},
1256 {"__getnewargs__", (PyCFunction
)int_getnewargs
, METH_NOARGS
},
1257 {"__format__", (PyCFunction
)int__format__
, METH_VARARGS
},
1258 {NULL
, NULL
} /* sentinel */
1261 static PyGetSetDef int_getset
[] = {
1263 (getter
)int_int
, (setter
)NULL
,
1264 "the real part of a complex number",
1267 (getter
)int_get0
, (setter
)NULL
,
1268 "the imaginary part of a complex number",
1271 (getter
)int_int
, (setter
)NULL
,
1272 "the numerator of a rational number in lowest terms",
1275 (getter
)int_get1
, (setter
)NULL
,
1276 "the denominator of a rational number in lowest terms",
1278 {NULL
} /* Sentinel */
1281 PyDoc_STRVAR(int_doc
,
1282 "int(x[, base]) -> integer\n\
1284 Convert a string or number to an integer, if possible. A floating point\n\
1285 argument will be truncated towards zero (this does not include a string\n\
1286 representation of a floating point number!) When converting a string, use\n\
1287 the optional base. It is an error to supply a base when converting a\n\
1288 non-string. If base is zero, the proper base is guessed based on the\n\
1289 string content. If the argument is outside the integer range a\n\
1290 long object will be returned instead.");
1292 static PyNumberMethods int_as_number
= {
1293 (binaryfunc
)int_add
, /*nb_add*/
1294 (binaryfunc
)int_sub
, /*nb_subtract*/
1295 (binaryfunc
)int_mul
, /*nb_multiply*/
1296 (binaryfunc
)int_classic_div
, /*nb_divide*/
1297 (binaryfunc
)int_mod
, /*nb_remainder*/
1298 (binaryfunc
)int_divmod
, /*nb_divmod*/
1299 (ternaryfunc
)int_pow
, /*nb_power*/
1300 (unaryfunc
)int_neg
, /*nb_negative*/
1301 (unaryfunc
)int_int
, /*nb_positive*/
1302 (unaryfunc
)int_abs
, /*nb_absolute*/
1303 (inquiry
)int_nonzero
, /*nb_nonzero*/
1304 (unaryfunc
)int_invert
, /*nb_invert*/
1305 (binaryfunc
)int_lshift
, /*nb_lshift*/
1306 (binaryfunc
)int_rshift
, /*nb_rshift*/
1307 (binaryfunc
)int_and
, /*nb_and*/
1308 (binaryfunc
)int_xor
, /*nb_xor*/
1309 (binaryfunc
)int_or
, /*nb_or*/
1310 int_coerce
, /*nb_coerce*/
1311 (unaryfunc
)int_int
, /*nb_int*/
1312 (unaryfunc
)int_long
, /*nb_long*/
1313 (unaryfunc
)int_float
, /*nb_float*/
1314 (unaryfunc
)int_oct
, /*nb_oct*/
1315 (unaryfunc
)int_hex
, /*nb_hex*/
1316 0, /*nb_inplace_add*/
1317 0, /*nb_inplace_subtract*/
1318 0, /*nb_inplace_multiply*/
1319 0, /*nb_inplace_divide*/
1320 0, /*nb_inplace_remainder*/
1321 0, /*nb_inplace_power*/
1322 0, /*nb_inplace_lshift*/
1323 0, /*nb_inplace_rshift*/
1324 0, /*nb_inplace_and*/
1325 0, /*nb_inplace_xor*/
1326 0, /*nb_inplace_or*/
1327 (binaryfunc
)int_div
, /* nb_floor_divide */
1328 int_true_divide
, /* nb_true_divide */
1329 0, /* nb_inplace_floor_divide */
1330 0, /* nb_inplace_true_divide */
1331 (unaryfunc
)int_int
, /* nb_index */
1334 PyTypeObject PyInt_Type
= {
1335 PyVarObject_HEAD_INIT(&PyType_Type
, 0)
1337 sizeof(PyIntObject
),
1339 (destructor
)int_dealloc
, /* tp_dealloc */
1340 (printfunc
)int_print
, /* tp_print */
1343 (cmpfunc
)int_compare
, /* tp_compare */
1344 (reprfunc
)int_repr
, /* tp_repr */
1345 &int_as_number
, /* tp_as_number */
1346 0, /* tp_as_sequence */
1347 0, /* tp_as_mapping */
1348 (hashfunc
)int_hash
, /* tp_hash */
1350 (reprfunc
)int_repr
, /* tp_str */
1351 PyObject_GenericGetAttr
, /* tp_getattro */
1352 0, /* tp_setattro */
1353 0, /* tp_as_buffer */
1354 Py_TPFLAGS_DEFAULT
| Py_TPFLAGS_CHECKTYPES
|
1355 Py_TPFLAGS_BASETYPE
| Py_TPFLAGS_INT_SUBCLASS
, /* tp_flags */
1356 int_doc
, /* tp_doc */
1357 0, /* tp_traverse */
1359 0, /* tp_richcompare */
1360 0, /* tp_weaklistoffset */
1362 0, /* tp_iternext */
1363 int_methods
, /* tp_methods */
1365 int_getset
, /* tp_getset */
1368 0, /* tp_descr_get */
1369 0, /* tp_descr_set */
1370 0, /* tp_dictoffset */
1373 int_new
, /* tp_new */
1374 (freefunc
)int_free
, /* tp_free */
1382 #if NSMALLNEGINTS + NSMALLPOSINTS > 0
1383 for (ival
= -NSMALLNEGINTS
; ival
< NSMALLPOSINTS
; ival
++) {
1384 if (!free_list
&& (free_list
= fill_free_list()) == NULL
)
1386 /* PyObject_New is inlined */
1388 free_list
= (PyIntObject
*)Py_TYPE(v
);
1389 PyObject_INIT(v
, &PyInt_Type
);
1391 small_ints
[ival
+ NSMALLNEGINTS
] = v
;
1398 PyInt_ClearFreeList(void)
1401 PyIntBlock
*list
, *next
;
1403 int u
; /* remaining unfreed ints per block */
1404 int freelist_size
= 0;
1409 while (list
!= NULL
) {
1411 for (i
= 0, p
= &list
->objects
[0];
1414 if (PyInt_CheckExact(p
) && p
->ob_refcnt
!= 0)
1419 list
->next
= block_list
;
1421 for (i
= 0, p
= &list
->objects
[0];
1424 if (!PyInt_CheckExact(p
) ||
1425 p
->ob_refcnt
== 0) {
1426 Py_TYPE(p
) = (struct _typeobject
*)
1430 #if NSMALLNEGINTS + NSMALLPOSINTS > 0
1431 else if (-NSMALLNEGINTS
<= p
->ob_ival
&&
1432 p
->ob_ival
< NSMALLPOSINTS
&&
1433 small_ints
[p
->ob_ival
+
1434 NSMALLNEGINTS
] == NULL
) {
1436 small_ints
[p
->ob_ival
+
1449 return freelist_size
;
1458 int u
; /* total unfreed ints per block */
1460 #if NSMALLNEGINTS + NSMALLPOSINTS > 0
1463 i
= NSMALLNEGINTS
+ NSMALLPOSINTS
;
1470 u
= PyInt_ClearFreeList();
1471 if (!Py_VerboseFlag
)
1473 fprintf(stderr
, "# cleanup ints");
1475 fprintf(stderr
, "\n");
1479 ": %d unfreed int%s\n",
1480 u
, u
== 1 ? "" : "s");
1482 if (Py_VerboseFlag
> 1) {
1484 while (list
!= NULL
) {
1485 for (i
= 0, p
= &list
->objects
[0];
1488 if (PyInt_CheckExact(p
) && p
->ob_refcnt
!= 0)
1489 /* XXX(twouters) cast refcount to
1490 long until %zd is universally
1494 "# <int at %p, refcnt=%ld, val=%ld>\n",
1495 p
, (long)p
->ob_refcnt
,