1 /* Long (arbitrary precision) integer object implementation */
3 /* XXX The functional organization of this file is terrible */
6 #include "longintrepr.h"
13 /* For long multiplication, use the O(N**2) school algorithm unless
14 * both operands contain more than KARATSUBA_CUTOFF digits (this
15 * being an internal Python long digit, in base PyLong_BASE).
17 #define KARATSUBA_CUTOFF 70
18 #define KARATSUBA_SQUARE_CUTOFF (2 * KARATSUBA_CUTOFF)
20 /* For exponentiation, use the binary left-to-right algorithm
21 * unless the exponent contains more than FIVEARY_CUTOFF digits.
22 * In that case, do 5 bits at a time. The potential drawback is that
23 * a table of 2**5 intermediate results is computed.
25 #define FIVEARY_CUTOFF 8
27 #define ABS(x) ((x) < 0 ? -(x) : (x))
31 #define MAX(x, y) ((x) < (y) ? (y) : (x))
32 #define MIN(x, y) ((x) > (y) ? (y) : (x))
34 #define SIGCHECK(PyTryBlock) \
36 if (--_Py_Ticker < 0) { \
37 _Py_Ticker = _Py_CheckInterval; \
38 if (PyErr_CheckSignals()) PyTryBlock \
42 /* Normalize (remove leading zeros from) a long int object.
43 Doesn't attempt to free the storage--in most cases, due to the nature
44 of the algorithms used, this could save at most be one word anyway. */
47 long_normalize(register PyLongObject
*v
)
49 Py_ssize_t j
= ABS(Py_SIZE(v
));
52 while (i
> 0 && v
->ob_digit
[i
-1] == 0)
55 Py_SIZE(v
) = (Py_SIZE(v
) < 0) ? -(i
) : i
;
59 /* Allocate a new long int object with size digits.
60 Return NULL and set exception if we run out of memory. */
62 #define MAX_LONG_DIGITS \
63 ((PY_SSIZE_T_MAX - offsetof(PyLongObject, ob_digit))/sizeof(digit))
66 _PyLong_New(Py_ssize_t size
)
68 if (size
> (Py_ssize_t
)MAX_LONG_DIGITS
) {
69 PyErr_SetString(PyExc_OverflowError
,
70 "too many digits in integer");
73 /* coverity[ampersand_in_size] */
74 /* XXX(nnorwitz): PyObject_NEW_VAR / _PyObject_VAR_SIZE need to detect
76 return PyObject_NEW_VAR(PyLongObject
, &PyLong_Type
, size
);
80 _PyLong_Copy(PyLongObject
*src
)
89 result
= _PyLong_New(i
);
91 result
->ob_size
= src
->ob_size
;
93 result
->ob_digit
[i
] = src
->ob_digit
[i
];
95 return (PyObject
*)result
;
98 /* Create a new long int object from a C long int */
101 PyLong_FromLong(long ival
)
104 unsigned long abs_ival
;
105 unsigned long t
; /* unsigned so >> doesn't propagate sign bit */
110 /* if LONG_MIN == -LONG_MAX-1 (true on most platforms) then
111 ANSI C says that the result of -ival is undefined when ival
112 == LONG_MIN. Hence the following workaround. */
113 abs_ival
= (unsigned long)(-1-ival
) + 1;
117 abs_ival
= (unsigned long)ival
;
120 /* Count the number of Python digits.
121 We used to pick 5 ("big enough for anything"), but that's a
122 waste of time and space given that 5*15 = 75 bits are rarely
129 v
= _PyLong_New(ndigits
);
131 digit
*p
= v
->ob_digit
;
132 v
->ob_size
= negative
? -ndigits
: ndigits
;
135 *p
++ = (digit
)(t
& PyLong_MASK
);
139 return (PyObject
*)v
;
142 /* Create a new long int object from a C unsigned long int */
145 PyLong_FromUnsignedLong(unsigned long ival
)
151 /* Count the number of Python digits. */
152 t
= (unsigned long)ival
;
157 v
= _PyLong_New(ndigits
);
159 digit
*p
= v
->ob_digit
;
160 Py_SIZE(v
) = ndigits
;
162 *p
++ = (digit
)(ival
& PyLong_MASK
);
163 ival
>>= PyLong_SHIFT
;
166 return (PyObject
*)v
;
169 /* Create a new long int object from a C double */
172 PyLong_FromDouble(double dval
)
176 int i
, ndig
, expo
, neg
;
178 if (Py_IS_INFINITY(dval
)) {
179 PyErr_SetString(PyExc_OverflowError
,
180 "cannot convert float infinity to integer");
183 if (Py_IS_NAN(dval
)) {
184 PyErr_SetString(PyExc_ValueError
,
185 "cannot convert float NaN to integer");
192 frac
= frexp(dval
, &expo
); /* dval = frac*2**expo; 0.0 <= frac < 1.0 */
194 return PyLong_FromLong(0L);
195 ndig
= (expo
-1) / PyLong_SHIFT
+ 1; /* Number of 'digits' in result */
196 v
= _PyLong_New(ndig
);
199 frac
= ldexp(frac
, (expo
-1) % PyLong_SHIFT
+ 1);
200 for (i
= ndig
; --i
>= 0; ) {
201 digit bits
= (digit
)frac
;
202 v
->ob_digit
[i
] = bits
;
203 frac
= frac
- (double)bits
;
204 frac
= ldexp(frac
, PyLong_SHIFT
);
207 Py_SIZE(v
) = -(Py_SIZE(v
));
208 return (PyObject
*)v
;
211 /* Checking for overflow in PyLong_AsLong is a PITA since C doesn't define
212 * anything about what happens when a signed integer operation overflows,
213 * and some compilers think they're doing you a favor by being "clever"
214 * then. The bit pattern for the largest postive signed long is
215 * (unsigned long)LONG_MAX, and for the smallest negative signed long
216 * it is abs(LONG_MIN), which we could write -(unsigned long)LONG_MIN.
217 * However, some other compilers warn about applying unary minus to an
218 * unsigned operand. Hence the weird "0-".
220 #define PY_ABS_LONG_MIN (0-(unsigned long)LONG_MIN)
221 #define PY_ABS_SSIZE_T_MIN (0-(size_t)PY_SSIZE_T_MIN)
223 /* Get a C long int from a Python long or Python int object.
224 On overflow, returns -1 and sets *overflow to 1 or -1 depending
225 on the sign of the result. Otherwise *overflow is 0.
227 For other errors (e.g., type error), returns -1 and sets an error
232 PyLong_AsLongAndOverflow(PyObject
*vv
, int *overflow
)
234 /* This version by Tim Peters */
235 register PyLongObject
*v
;
236 unsigned long x
, prev
;
240 int do_decref
= 0; /* if nb_int was called */
244 PyErr_BadInternalCall();
249 return PyInt_AsLong(vv
);
251 if (!PyLong_Check(vv
)) {
253 nb
= vv
->ob_type
->tp_as_number
;
254 if (nb
== NULL
|| nb
->nb_int
== NULL
) {
255 PyErr_SetString(PyExc_TypeError
,
256 "an integer is required");
259 vv
= (*nb
->nb_int
) (vv
);
263 if(PyInt_Check(vv
)) {
264 res
= PyInt_AsLong(vv
);
267 if (!PyLong_Check(vv
)) {
269 PyErr_SetString(PyExc_TypeError
,
270 "nb_int should return int object");
276 v
= (PyLongObject
*)vv
;
281 res
= -(sdigit
)v
->ob_digit
[0];
287 res
= v
->ob_digit
[0];
298 x
= (x
<< PyLong_SHIFT
) + v
->ob_digit
[i
];
299 if ((x
>> PyLong_SHIFT
) != prev
) {
304 /* Haven't lost any bits, but casting to long requires extra
305 * care (see comment above).
307 if (x
<= (unsigned long)LONG_MAX
) {
308 res
= (long)x
* sign
;
310 else if (sign
< 0 && x
== PY_ABS_LONG_MIN
) {
315 /* res is already set to -1 */
325 /* Get a C long int from a long int object.
326 Returns -1 and sets an error condition if overflow occurs. */
329 PyLong_AsLong(PyObject
*obj
)
332 long result
= PyLong_AsLongAndOverflow(obj
, &overflow
);
334 /* XXX: could be cute and give a different
335 message for overflow == -1 */
336 PyErr_SetString(PyExc_OverflowError
,
337 "Python int too large to convert to C long");
342 /* Get a C int from a long int object or any object that has an __int__
343 method. Return -1 and set an error if overflow occurs. */
346 _PyLong_AsInt(PyObject
*obj
)
349 long result
= PyLong_AsLongAndOverflow(obj
, &overflow
);
350 if (overflow
|| result
> INT_MAX
|| result
< INT_MIN
) {
351 /* XXX: could be cute and give a different
352 message for overflow == -1 */
353 PyErr_SetString(PyExc_OverflowError
,
354 "Python int too large to convert to C int");
360 /* Get a Py_ssize_t from a long int object.
361 Returns -1 and sets an error condition if overflow occurs. */
364 PyLong_AsSsize_t(PyObject
*vv
) {
365 register PyLongObject
*v
;
370 if (vv
== NULL
|| !PyLong_Check(vv
)) {
371 PyErr_BadInternalCall();
374 v
= (PyLongObject
*)vv
;
384 x
= (x
<< PyLong_SHIFT
) | v
->ob_digit
[i
];
385 if ((x
>> PyLong_SHIFT
) != prev
)
388 /* Haven't lost any bits, but casting to a signed type requires
389 * extra care (see comment above).
391 if (x
<= (size_t)PY_SSIZE_T_MAX
) {
392 return (Py_ssize_t
)x
* sign
;
394 else if (sign
< 0 && x
== PY_ABS_SSIZE_T_MIN
) {
395 return PY_SSIZE_T_MIN
;
400 PyErr_SetString(PyExc_OverflowError
,
401 "long int too large to convert to int");
405 /* Get a C unsigned long int from a long int object.
406 Returns -1 and sets an error condition if overflow occurs. */
409 PyLong_AsUnsignedLong(PyObject
*vv
)
411 register PyLongObject
*v
;
412 unsigned long x
, prev
;
415 if (vv
== NULL
|| !PyLong_Check(vv
)) {
416 if (vv
!= NULL
&& PyInt_Check(vv
)) {
417 long val
= PyInt_AsLong(vv
);
419 PyErr_SetString(PyExc_OverflowError
,
420 "can't convert negative value "
422 return (unsigned long) -1;
426 PyErr_BadInternalCall();
427 return (unsigned long) -1;
429 v
= (PyLongObject
*)vv
;
433 PyErr_SetString(PyExc_OverflowError
,
434 "can't convert negative value to unsigned long");
435 return (unsigned long) -1;
439 x
= (x
<< PyLong_SHIFT
) | v
->ob_digit
[i
];
440 if ((x
>> PyLong_SHIFT
) != prev
) {
441 PyErr_SetString(PyExc_OverflowError
,
442 "long int too large to convert");
443 return (unsigned long) -1;
449 /* Get a C unsigned long int from a long int object, ignoring the high bits.
450 Returns -1 and sets an error condition if an error occurs. */
453 PyLong_AsUnsignedLongMask(PyObject
*vv
)
455 register PyLongObject
*v
;
460 if (vv
== NULL
|| !PyLong_Check(vv
)) {
461 if (vv
!= NULL
&& PyInt_Check(vv
))
462 return PyInt_AsUnsignedLongMask(vv
);
463 PyErr_BadInternalCall();
464 return (unsigned long) -1;
466 v
= (PyLongObject
*)vv
;
475 x
= (x
<< PyLong_SHIFT
) | v
->ob_digit
[i
];
481 _PyLong_Sign(PyObject
*vv
)
483 PyLongObject
*v
= (PyLongObject
*)vv
;
486 assert(PyLong_Check(v
));
488 return Py_SIZE(v
) == 0 ? 0 : (Py_SIZE(v
) < 0 ? -1 : 1);
492 _PyLong_NumBits(PyObject
*vv
)
494 PyLongObject
*v
= (PyLongObject
*)vv
;
499 assert(PyLong_Check(v
));
500 ndigits
= ABS(Py_SIZE(v
));
501 assert(ndigits
== 0 || v
->ob_digit
[ndigits
- 1] != 0);
503 digit msd
= v
->ob_digit
[ndigits
- 1];
505 result
= (ndigits
- 1) * PyLong_SHIFT
;
506 if (result
/ PyLong_SHIFT
!= (size_t)(ndigits
- 1))
518 PyErr_SetString(PyExc_OverflowError
, "long has too many bits "
519 "to express in a platform size_t");
524 _PyLong_FromByteArray(const unsigned char* bytes
, size_t n
,
525 int little_endian
, int is_signed
)
527 const unsigned char* pstartbyte
; /* LSB of bytes */
528 int incr
; /* direction to move pstartbyte */
529 const unsigned char* pendbyte
; /* MSB of bytes */
530 size_t numsignificantbytes
; /* number of bytes that matter */
531 Py_ssize_t ndigits
; /* number of Python long digits */
532 PyLongObject
* v
; /* result */
533 Py_ssize_t idigit
= 0; /* next free index in v->ob_digit */
536 return PyLong_FromLong(0L);
540 pendbyte
= bytes
+ n
- 1;
544 pstartbyte
= bytes
+ n
- 1;
550 is_signed
= *pendbyte
>= 0x80;
552 /* Compute numsignificantbytes. This consists of finding the most
553 significant byte. Leading 0 bytes are insignificant if the number
554 is positive, and leading 0xff bytes if negative. */
557 const unsigned char* p
= pendbyte
;
558 const int pincr
= -incr
; /* search MSB to LSB */
559 const unsigned char insignficant
= is_signed
? 0xff : 0x00;
561 for (i
= 0; i
< n
; ++i
, p
+= pincr
) {
562 if (*p
!= insignficant
)
565 numsignificantbytes
= n
- i
;
566 /* 2's-comp is a bit tricky here, e.g. 0xff00 == -0x0100, so
567 actually has 2 significant bytes. OTOH, 0xff0001 ==
568 -0x00ffff, so we wouldn't *need* to bump it there; but we
569 do for 0xffff = -0x0001. To be safe without bothering to
570 check every case, bump it regardless. */
571 if (is_signed
&& numsignificantbytes
< n
)
572 ++numsignificantbytes
;
575 /* How many Python long digits do we need? We have
576 8*numsignificantbytes bits, and each Python long digit has
577 PyLong_SHIFT bits, so it's the ceiling of the quotient. */
578 /* catch overflow before it happens */
579 if (numsignificantbytes
> (PY_SSIZE_T_MAX
- PyLong_SHIFT
) / 8) {
580 PyErr_SetString(PyExc_OverflowError
,
581 "byte array too long to convert to int");
584 ndigits
= (numsignificantbytes
* 8 + PyLong_SHIFT
- 1) / PyLong_SHIFT
;
585 v
= _PyLong_New(ndigits
);
589 /* Copy the bits over. The tricky parts are computing 2's-comp on
590 the fly for signed numbers, and dealing with the mismatch between
591 8-bit bytes and (probably) 15-bit Python digits.*/
594 twodigits carry
= 1; /* for 2's-comp calculation */
595 twodigits accum
= 0; /* sliding register */
596 unsigned int accumbits
= 0; /* number of bits in accum */
597 const unsigned char* p
= pstartbyte
;
599 for (i
= 0; i
< numsignificantbytes
; ++i
, p
+= incr
) {
600 twodigits thisbyte
= *p
;
601 /* Compute correction for 2's comp, if needed. */
603 thisbyte
= (0xff ^ thisbyte
) + carry
;
604 carry
= thisbyte
>> 8;
607 /* Because we're going LSB to MSB, thisbyte is
608 more significant than what's already in accum,
609 so needs to be prepended to accum. */
610 accum
|= (twodigits
)thisbyte
<< accumbits
;
612 if (accumbits
>= PyLong_SHIFT
) {
613 /* There's enough to fill a Python digit. */
614 assert(idigit
< ndigits
);
615 v
->ob_digit
[idigit
] = (digit
)(accum
& PyLong_MASK
);
617 accum
>>= PyLong_SHIFT
;
618 accumbits
-= PyLong_SHIFT
;
619 assert(accumbits
< PyLong_SHIFT
);
622 assert(accumbits
< PyLong_SHIFT
);
624 assert(idigit
< ndigits
);
625 v
->ob_digit
[idigit
] = (digit
)accum
;
630 Py_SIZE(v
) = is_signed
? -idigit
: idigit
;
631 return (PyObject
*)long_normalize(v
);
635 _PyLong_AsByteArray(PyLongObject
* v
,
636 unsigned char* bytes
, size_t n
,
637 int little_endian
, int is_signed
)
639 Py_ssize_t i
; /* index into v->ob_digit */
640 Py_ssize_t ndigits
; /* |v->ob_size| */
641 twodigits accum
; /* sliding register */
642 unsigned int accumbits
; /* # bits in accum */
643 int do_twos_comp
; /* store 2's-comp? is_signed and v < 0 */
644 digit carry
; /* for computing 2's-comp */
645 size_t j
; /* # bytes filled */
646 unsigned char* p
; /* pointer to next byte in bytes */
647 int pincr
; /* direction to move p */
649 assert(v
!= NULL
&& PyLong_Check(v
));
651 if (Py_SIZE(v
) < 0) {
652 ndigits
= -(Py_SIZE(v
));
654 PyErr_SetString(PyExc_OverflowError
,
655 "can't convert negative long to unsigned");
661 ndigits
= Py_SIZE(v
);
674 /* Copy over all the Python digits.
675 It's crucial that every Python digit except for the MSD contribute
676 exactly PyLong_SHIFT bits to the total, so first assert that the long is
678 assert(ndigits
== 0 || v
->ob_digit
[ndigits
- 1] != 0);
682 carry
= do_twos_comp
? 1 : 0;
683 for (i
= 0; i
< ndigits
; ++i
) {
684 digit thisdigit
= v
->ob_digit
[i
];
686 thisdigit
= (thisdigit
^ PyLong_MASK
) + carry
;
687 carry
= thisdigit
>> PyLong_SHIFT
;
688 thisdigit
&= PyLong_MASK
;
690 /* Because we're going LSB to MSB, thisdigit is more
691 significant than what's already in accum, so needs to be
692 prepended to accum. */
693 accum
|= (twodigits
)thisdigit
<< accumbits
;
695 /* The most-significant digit may be (probably is) at least
697 if (i
== ndigits
- 1) {
698 /* Count # of sign bits -- they needn't be stored,
699 * although for signed conversion we need later to
700 * make sure at least one sign bit gets stored. */
701 digit s
= do_twos_comp
? thisdigit
^ PyLong_MASK
: thisdigit
;
708 accumbits
+= PyLong_SHIFT
;
710 /* Store as many bytes as possible. */
711 while (accumbits
>= 8) {
715 *p
= (unsigned char)(accum
& 0xff);
722 /* Store the straggler (if any). */
723 assert(accumbits
< 8);
724 assert(carry
== 0); /* else do_twos_comp and *every* digit was 0 */
730 /* Fill leading bits of the byte with sign bits
731 (appropriately pretending that the long had an
732 infinite supply of sign bits). */
733 accum
|= (~(twodigits
)0) << accumbits
;
735 *p
= (unsigned char)(accum
& 0xff);
738 else if (j
== n
&& n
> 0 && is_signed
) {
739 /* The main loop filled the byte array exactly, so the code
740 just above didn't get to ensure there's a sign bit, and the
741 loop below wouldn't add one either. Make sure a sign bit
743 unsigned char msb
= *(p
- pincr
);
744 int sign_bit_set
= msb
>= 0x80;
745 assert(accumbits
== 0);
746 if (sign_bit_set
== do_twos_comp
)
752 /* Fill remaining bytes with copies of the sign bit. */
754 unsigned char signbyte
= do_twos_comp
? 0xffU
: 0U;
755 for ( ; j
< n
; ++j
, p
+= pincr
)
762 PyErr_SetString(PyExc_OverflowError
, "long too big to convert");
767 /* Create a new long (or int) object from a C pointer */
770 PyLong_FromVoidPtr(void *p
)
772 #if SIZEOF_VOID_P <= SIZEOF_LONG
774 return PyLong_FromUnsignedLong((unsigned long)p
);
775 return PyInt_FromLong((long)p
);
778 #ifndef HAVE_LONG_LONG
779 # error "PyLong_FromVoidPtr: sizeof(void*) > sizeof(long), but no long long"
781 #if SIZEOF_LONG_LONG < SIZEOF_VOID_P
782 # error "PyLong_FromVoidPtr: sizeof(PY_LONG_LONG) < sizeof(void*)"
784 /* optimize null pointers */
786 return PyInt_FromLong(0);
787 return PyLong_FromUnsignedLongLong((unsigned PY_LONG_LONG
)p
);
789 #endif /* SIZEOF_VOID_P <= SIZEOF_LONG */
792 /* Get a C pointer from a long object (or an int object in some cases) */
795 PyLong_AsVoidPtr(PyObject
*vv
)
797 /* This function will allow int or long objects. If vv is neither,
798 then the PyLong_AsLong*() functions will raise the exception:
799 PyExc_SystemError, "bad argument to internal function"
801 #if SIZEOF_VOID_P <= SIZEOF_LONG
805 x
= PyInt_AS_LONG(vv
);
806 else if (PyLong_Check(vv
) && _PyLong_Sign(vv
) < 0)
807 x
= PyLong_AsLong(vv
);
809 x
= PyLong_AsUnsignedLong(vv
);
812 #ifndef HAVE_LONG_LONG
813 # error "PyLong_AsVoidPtr: sizeof(void*) > sizeof(long), but no long long"
815 #if SIZEOF_LONG_LONG < SIZEOF_VOID_P
816 # error "PyLong_AsVoidPtr: sizeof(PY_LONG_LONG) < sizeof(void*)"
821 x
= PyInt_AS_LONG(vv
);
822 else if (PyLong_Check(vv
) && _PyLong_Sign(vv
) < 0)
823 x
= PyLong_AsLongLong(vv
);
825 x
= PyLong_AsUnsignedLongLong(vv
);
827 #endif /* SIZEOF_VOID_P <= SIZEOF_LONG */
829 if (x
== -1 && PyErr_Occurred())
834 #ifdef HAVE_LONG_LONG
836 /* Initial PY_LONG_LONG support by Chris Herborth (chrish@qnx.com), later
837 * rewritten to use the newer PyLong_{As,From}ByteArray API.
840 #define IS_LITTLE_ENDIAN (int)*(unsigned char*)&one
841 #define PY_ABS_LLONG_MIN (0-(unsigned PY_LONG_LONG)PY_LLONG_MIN)
843 /* Create a new long int object from a C PY_LONG_LONG int. */
846 PyLong_FromLongLong(PY_LONG_LONG ival
)
849 unsigned PY_LONG_LONG abs_ival
;
850 unsigned PY_LONG_LONG t
; /* unsigned so >> doesn't propagate sign bit */
855 /* avoid signed overflow on negation; see comments
856 in PyLong_FromLong above. */
857 abs_ival
= (unsigned PY_LONG_LONG
)(-1-ival
) + 1;
861 abs_ival
= (unsigned PY_LONG_LONG
)ival
;
864 /* Count the number of Python digits.
865 We used to pick 5 ("big enough for anything"), but that's a
866 waste of time and space given that 5*15 = 75 bits are rarely
873 v
= _PyLong_New(ndigits
);
875 digit
*p
= v
->ob_digit
;
876 Py_SIZE(v
) = negative
? -ndigits
: ndigits
;
879 *p
++ = (digit
)(t
& PyLong_MASK
);
883 return (PyObject
*)v
;
886 /* Create a new long int object from a C unsigned PY_LONG_LONG int. */
889 PyLong_FromUnsignedLongLong(unsigned PY_LONG_LONG ival
)
892 unsigned PY_LONG_LONG t
;
895 /* Count the number of Python digits. */
896 t
= (unsigned PY_LONG_LONG
)ival
;
901 v
= _PyLong_New(ndigits
);
903 digit
*p
= v
->ob_digit
;
904 Py_SIZE(v
) = ndigits
;
906 *p
++ = (digit
)(ival
& PyLong_MASK
);
907 ival
>>= PyLong_SHIFT
;
910 return (PyObject
*)v
;
913 /* Create a new long int object from a C Py_ssize_t. */
916 PyLong_FromSsize_t(Py_ssize_t ival
)
918 Py_ssize_t bytes
= ival
;
920 return _PyLong_FromByteArray((unsigned char *)&bytes
,
921 SIZEOF_SIZE_T
, IS_LITTLE_ENDIAN
, 1);
924 /* Create a new long int object from a C size_t. */
927 PyLong_FromSize_t(size_t ival
)
931 return _PyLong_FromByteArray((unsigned char *)&bytes
,
932 SIZEOF_SIZE_T
, IS_LITTLE_ENDIAN
, 0);
935 /* Get a C PY_LONG_LONG int from a long int object.
936 Return -1 and set an error if overflow occurs. */
939 PyLong_AsLongLong(PyObject
*vv
)
946 PyErr_BadInternalCall();
949 if (!PyLong_Check(vv
)) {
953 return (PY_LONG_LONG
)PyInt_AsLong(vv
);
954 if ((nb
= vv
->ob_type
->tp_as_number
) == NULL
||
955 nb
->nb_int
== NULL
) {
956 PyErr_SetString(PyExc_TypeError
, "an integer is required");
959 io
= (*nb
->nb_int
) (vv
);
962 if (PyInt_Check(io
)) {
963 bytes
= PyInt_AsLong(io
);
967 if (PyLong_Check(io
)) {
968 bytes
= PyLong_AsLongLong(io
);
973 PyErr_SetString(PyExc_TypeError
, "integer conversion failed");
977 res
= _PyLong_AsByteArray((PyLongObject
*)vv
, (unsigned char *)&bytes
,
978 SIZEOF_LONG_LONG
, IS_LITTLE_ENDIAN
, 1);
980 /* Plan 9 can't handle PY_LONG_LONG in ? : expressions */
982 return (PY_LONG_LONG
)-1;
987 /* Get a C unsigned PY_LONG_LONG int from a long int object.
988 Return -1 and set an error if overflow occurs. */
990 unsigned PY_LONG_LONG
991 PyLong_AsUnsignedLongLong(PyObject
*vv
)
993 unsigned PY_LONG_LONG bytes
;
997 if (vv
== NULL
|| !PyLong_Check(vv
)) {
998 PyErr_BadInternalCall();
999 return (unsigned PY_LONG_LONG
)-1;
1002 res
= _PyLong_AsByteArray((PyLongObject
*)vv
, (unsigned char *)&bytes
,
1003 SIZEOF_LONG_LONG
, IS_LITTLE_ENDIAN
, 0);
1005 /* Plan 9 can't handle PY_LONG_LONG in ? : expressions */
1007 return (unsigned PY_LONG_LONG
)res
;
1012 /* Get a C unsigned long int from a long int object, ignoring the high bits.
1013 Returns -1 and sets an error condition if an error occurs. */
1015 unsigned PY_LONG_LONG
1016 PyLong_AsUnsignedLongLongMask(PyObject
*vv
)
1018 register PyLongObject
*v
;
1019 unsigned PY_LONG_LONG x
;
1023 if (vv
== NULL
|| !PyLong_Check(vv
)) {
1024 PyErr_BadInternalCall();
1025 return (unsigned long) -1;
1027 v
= (PyLongObject
*)vv
;
1036 x
= (x
<< PyLong_SHIFT
) | v
->ob_digit
[i
];
1041 /* Get a C long long int from a Python long or Python int object.
1042 On overflow, returns -1 and sets *overflow to 1 or -1 depending
1043 on the sign of the result. Otherwise *overflow is 0.
1045 For other errors (e.g., type error), returns -1 and sets an error
1050 PyLong_AsLongLongAndOverflow(PyObject
*vv
, int *overflow
)
1052 /* This version by Tim Peters */
1053 register PyLongObject
*v
;
1054 unsigned PY_LONG_LONG x
, prev
;
1058 int do_decref
= 0; /* if nb_int was called */
1062 PyErr_BadInternalCall();
1066 if (PyInt_Check(vv
))
1067 return PyInt_AsLong(vv
);
1069 if (!PyLong_Check(vv
)) {
1070 PyNumberMethods
*nb
;
1071 nb
= vv
->ob_type
->tp_as_number
;
1072 if (nb
== NULL
|| nb
->nb_int
== NULL
) {
1073 PyErr_SetString(PyExc_TypeError
,
1074 "an integer is required");
1077 vv
= (*nb
->nb_int
) (vv
);
1081 if(PyInt_Check(vv
)) {
1082 res
= PyInt_AsLong(vv
);
1085 if (!PyLong_Check(vv
)) {
1087 PyErr_SetString(PyExc_TypeError
,
1088 "nb_int should return int object");
1094 v
= (PyLongObject
*)vv
;
1099 res
= -(sdigit
)v
->ob_digit
[0];
1105 res
= v
->ob_digit
[0];
1116 x
= (x
<< PyLong_SHIFT
) + v
->ob_digit
[i
];
1117 if ((x
>> PyLong_SHIFT
) != prev
) {
1122 /* Haven't lost any bits, but casting to long requires extra
1123 * care (see comment above).
1125 if (x
<= (unsigned PY_LONG_LONG
)PY_LLONG_MAX
) {
1126 res
= (PY_LONG_LONG
)x
* sign
;
1128 else if (sign
< 0 && x
== PY_ABS_LLONG_MIN
) {
1133 /* res is already set to -1 */
1143 #undef IS_LITTLE_ENDIAN
1145 #endif /* HAVE_LONG_LONG */
1149 convert_binop(PyObject
*v
, PyObject
*w
, PyLongObject
**a
, PyLongObject
**b
) {
1150 if (PyLong_Check(v
)) {
1151 *a
= (PyLongObject
*) v
;
1154 else if (PyInt_Check(v
)) {
1155 *a
= (PyLongObject
*) PyLong_FromLong(PyInt_AS_LONG(v
));
1160 if (PyLong_Check(w
)) {
1161 *b
= (PyLongObject
*) w
;
1164 else if (PyInt_Check(w
)) {
1165 *b
= (PyLongObject
*) PyLong_FromLong(PyInt_AS_LONG(w
));
1174 #define CONVERT_BINOP(v, w, a, b) \
1176 if (!convert_binop(v, w, a, b)) { \
1177 Py_INCREF(Py_NotImplemented); \
1178 return Py_NotImplemented; \
1182 /* bits_in_digit(d) returns the unique integer k such that 2**(k-1) <= d <
1183 2**k if d is nonzero, else 0. */
1185 static const unsigned char BitLengthTable
[32] = {
1186 0, 1, 2, 2, 3, 3, 3, 3, 4, 4, 4, 4, 4, 4, 4, 4,
1187 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5
1191 bits_in_digit(digit d
)
1198 d_bits
+= (int)BitLengthTable
[d
];
1202 /* x[0:m] and y[0:n] are digit vectors, LSD first, m >= n required. x[0:n]
1203 * is modified in place, by adding y to it. Carries are propagated as far as
1204 * x[m-1], and the remaining carry (0 or 1) is returned.
1207 v_iadd(digit
*x
, Py_ssize_t m
, digit
*y
, Py_ssize_t n
)
1213 for (i
= 0; i
< n
; ++i
) {
1214 carry
+= x
[i
] + y
[i
];
1215 x
[i
] = carry
& PyLong_MASK
;
1216 carry
>>= PyLong_SHIFT
;
1217 assert((carry
& 1) == carry
);
1219 for (; carry
&& i
< m
; ++i
) {
1221 x
[i
] = carry
& PyLong_MASK
;
1222 carry
>>= PyLong_SHIFT
;
1223 assert((carry
& 1) == carry
);
1228 /* x[0:m] and y[0:n] are digit vectors, LSD first, m >= n required. x[0:n]
1229 * is modified in place, by subtracting y from it. Borrows are propagated as
1230 * far as x[m-1], and the remaining borrow (0 or 1) is returned.
1233 v_isub(digit
*x
, Py_ssize_t m
, digit
*y
, Py_ssize_t n
)
1239 for (i
= 0; i
< n
; ++i
) {
1240 borrow
= x
[i
] - y
[i
] - borrow
;
1241 x
[i
] = borrow
& PyLong_MASK
;
1242 borrow
>>= PyLong_SHIFT
;
1243 borrow
&= 1; /* keep only 1 sign bit */
1245 for (; borrow
&& i
< m
; ++i
) {
1246 borrow
= x
[i
] - borrow
;
1247 x
[i
] = borrow
& PyLong_MASK
;
1248 borrow
>>= PyLong_SHIFT
;
1254 /* Shift digit vector a[0:m] d bits left, with 0 <= d < PyLong_SHIFT. Put
1255 * result in z[0:m], and return the d bits shifted out of the top.
1258 v_lshift(digit
*z
, digit
*a
, Py_ssize_t m
, int d
)
1263 assert(0 <= d
&& d
< PyLong_SHIFT
);
1264 for (i
=0; i
< m
; i
++) {
1265 twodigits acc
= (twodigits
)a
[i
] << d
| carry
;
1266 z
[i
] = (digit
)acc
& PyLong_MASK
;
1267 carry
= (digit
)(acc
>> PyLong_SHIFT
);
1272 /* Shift digit vector a[0:m] d bits right, with 0 <= d < PyLong_SHIFT. Put
1273 * result in z[0:m], and return the d bits shifted out of the bottom.
1276 v_rshift(digit
*z
, digit
*a
, Py_ssize_t m
, int d
)
1280 digit mask
= ((digit
)1 << d
) - 1U;
1282 assert(0 <= d
&& d
< PyLong_SHIFT
);
1283 for (i
=m
; i
-- > 0;) {
1284 twodigits acc
= (twodigits
)carry
<< PyLong_SHIFT
| a
[i
];
1285 carry
= (digit
)acc
& mask
;
1286 z
[i
] = (digit
)(acc
>> d
);
1291 /* Divide long pin, w/ size digits, by non-zero digit n, storing quotient
1292 in pout, and returning the remainder. pin and pout point at the LSD.
1293 It's OK for pin == pout on entry, which saves oodles of mallocs/frees in
1294 _PyLong_Format, but that should be done with great care since longs are
1298 inplace_divrem1(digit
*pout
, digit
*pin
, Py_ssize_t size
, digit n
)
1302 assert(n
> 0 && n
<= PyLong_MASK
);
1305 while (--size
>= 0) {
1307 rem
= (rem
<< PyLong_SHIFT
) | *--pin
;
1308 *--pout
= hi
= (digit
)(rem
/ n
);
1309 rem
-= (twodigits
)hi
* n
;
1314 /* Divide a long integer by a digit, returning both the quotient
1315 (as function result) and the remainder (through *prem).
1316 The sign of a is ignored; n should not be zero. */
1318 static PyLongObject
*
1319 divrem1(PyLongObject
*a
, digit n
, digit
*prem
)
1321 const Py_ssize_t size
= ABS(Py_SIZE(a
));
1324 assert(n
> 0 && n
<= PyLong_MASK
);
1325 z
= _PyLong_New(size
);
1328 *prem
= inplace_divrem1(z
->ob_digit
, a
->ob_digit
, size
, n
);
1329 return long_normalize(z
);
1332 /* Convert a long integer to a base 10 string. Returns a new non-shared
1333 string. (Return value is non-shared so that callers can modify the
1334 returned value if necessary.) */
1337 long_to_decimal_string(PyObject
*aa
, int addL
)
1339 PyLongObject
*scratch
, *a
;
1341 Py_ssize_t size
, strlen
, size_a
, i
, j
;
1342 digit
*pout
, *pin
, rem
, tenpow
;
1346 a
= (PyLongObject
*)aa
;
1347 if (a
== NULL
|| !PyLong_Check(a
)) {
1348 PyErr_BadInternalCall();
1351 size_a
= ABS(Py_SIZE(a
));
1352 negative
= Py_SIZE(a
) < 0;
1354 /* quick and dirty upper bound for the number of digits
1355 required to express a in base _PyLong_DECIMAL_BASE:
1357 #digits = 1 + floor(log2(a) / log2(_PyLong_DECIMAL_BASE))
1359 But log2(a) < size_a * PyLong_SHIFT, and
1360 log2(_PyLong_DECIMAL_BASE) = log2(10) * _PyLong_DECIMAL_SHIFT
1361 > 3 * _PyLong_DECIMAL_SHIFT
1363 if (size_a
> PY_SSIZE_T_MAX
/ PyLong_SHIFT
) {
1364 PyErr_SetString(PyExc_OverflowError
,
1365 "long is too large to format");
1368 /* the expression size_a * PyLong_SHIFT is now safe from overflow */
1369 size
= 1 + size_a
* PyLong_SHIFT
/ (3 * _PyLong_DECIMAL_SHIFT
);
1370 scratch
= _PyLong_New(size
);
1371 if (scratch
== NULL
)
1374 /* convert array of base _PyLong_BASE digits in pin to an array of
1375 base _PyLong_DECIMAL_BASE digits in pout, following Knuth (TAOCP,
1376 Volume 2 (3rd edn), section 4.4, Method 1b). */
1378 pout
= scratch
->ob_digit
;
1380 for (i
= size_a
; --i
>= 0; ) {
1382 for (j
= 0; j
< size
; j
++) {
1383 twodigits z
= (twodigits
)pout
[j
] << PyLong_SHIFT
| hi
;
1384 hi
= (digit
)(z
/ _PyLong_DECIMAL_BASE
);
1385 pout
[j
] = (digit
)(z
- (twodigits
)hi
*
1386 _PyLong_DECIMAL_BASE
);
1389 pout
[size
++] = hi
% _PyLong_DECIMAL_BASE
;
1390 hi
/= _PyLong_DECIMAL_BASE
;
1392 /* check for keyboard interrupt */
1398 /* pout should have at least one digit, so that the case when a = 0
1403 /* calculate exact length of output string, and allocate */
1404 strlen
= (addL
!= 0) + negative
+
1405 1 + (size
- 1) * _PyLong_DECIMAL_SHIFT
;
1408 while (rem
>= tenpow
) {
1412 str
= PyString_FromStringAndSize(NULL
, strlen
);
1418 /* fill the string right-to-left */
1419 p
= PyString_AS_STRING(str
) + strlen
;
1423 /* pout[0] through pout[size-2] contribute exactly
1424 _PyLong_DECIMAL_SHIFT digits each */
1425 for (i
=0; i
< size
- 1; i
++) {
1427 for (j
= 0; j
< _PyLong_DECIMAL_SHIFT
; j
++) {
1428 *--p
= '0' + rem
% 10;
1432 /* pout[size-1]: always produce at least one decimal digit */
1435 *--p
= '0' + rem
% 10;
1443 /* check we've counted correctly */
1444 assert(p
== PyString_AS_STRING(str
));
1446 return (PyObject
*)str
;
1449 /* Convert the long to a string object with given base,
1450 appending a base prefix of 0[box] if base is 2, 8 or 16.
1451 Add a trailing "L" if addL is non-zero.
1452 If newstyle is zero, then use the pre-2.6 behavior of octal having
1453 a leading "0", instead of the prefix "0o" */
1454 PyAPI_FUNC(PyObject
*)
1455 _PyLong_Format(PyObject
*aa
, int base
, int addL
, int newstyle
)
1457 register PyLongObject
*a
= (PyLongObject
*)aa
;
1458 PyStringObject
*str
;
1466 return long_to_decimal_string((PyObject
*)a
, addL
);
1468 if (a
== NULL
|| !PyLong_Check(a
)) {
1469 PyErr_BadInternalCall();
1472 assert(base
>= 2 && base
<= 36);
1473 size_a
= ABS(Py_SIZE(a
));
1475 /* Compute a rough upper bound for the length of the string */
1482 i
= 5 + (addL
? 1 : 0);
1483 /* ensure we don't get signed overflow in sz calculation */
1484 if (size_a
> (PY_SSIZE_T_MAX
- i
) / PyLong_SHIFT
) {
1485 PyErr_SetString(PyExc_OverflowError
,
1486 "long is too large to format");
1489 sz
= i
+ 1 + (size_a
* PyLong_SHIFT
- 1) / bits
;
1491 str
= (PyStringObject
*) PyString_FromStringAndSize((char *)0, sz
);
1494 p
= PyString_AS_STRING(str
) + sz
;
1501 if (a
->ob_size
== 0) {
1504 else if ((base
& (base
- 1)) == 0) {
1505 /* JRH: special case for power-of-2 bases */
1506 twodigits accum
= 0;
1507 int accumbits
= 0; /* # of bits in accum */
1508 int basebits
= 1; /* # of bits in base-1 */
1510 while ((i
>>= 1) > 1)
1513 for (i
= 0; i
< size_a
; ++i
) {
1514 accum
|= (twodigits
)a
->ob_digit
[i
] << accumbits
;
1515 accumbits
+= PyLong_SHIFT
;
1516 assert(accumbits
>= basebits
);
1518 char cdigit
= (char)(accum
& (base
- 1));
1519 cdigit
+= (cdigit
< 10) ? '0' : 'a'-10;
1520 assert(p
> PyString_AS_STRING(str
));
1522 accumbits
-= basebits
;
1524 } while (i
< size_a
-1 ? accumbits
>= basebits
: accum
> 0);
1528 /* Not 0, and base not a power of 2. Divide repeatedly by
1529 base, but for speed use the highest power of base that
1531 Py_ssize_t size
= size_a
;
1532 digit
*pin
= a
->ob_digit
;
1533 PyLongObject
*scratch
;
1534 /* powbasw <- largest power of base that fits in a digit. */
1535 digit powbase
= base
; /* powbase == base ** power */
1538 twodigits newpow
= powbase
* (twodigits
)base
;
1539 if (newpow
>> PyLong_SHIFT
)
1540 /* doesn't fit in a digit */
1542 powbase
= (digit
)newpow
;
1546 /* Get a scratch area for repeated division. */
1547 scratch
= _PyLong_New(size
);
1548 if (scratch
== NULL
) {
1553 /* Repeatedly divide by powbase. */
1555 int ntostore
= power
;
1556 digit rem
= inplace_divrem1(scratch
->ob_digit
,
1557 pin
, size
, powbase
);
1558 pin
= scratch
->ob_digit
; /* no need to use a again */
1559 if (pin
[size
- 1] == 0)
1567 /* Break rem into digits. */
1568 assert(ntostore
> 0);
1570 digit nextrem
= (digit
)(rem
/ base
);
1571 char c
= (char)(rem
- nextrem
* base
);
1572 assert(p
> PyString_AS_STRING(str
));
1573 c
+= (c
< 10) ? '0' : 'a'-10;
1577 /* Termination is a bit delicate: must not
1578 store leading zeroes, so must get out if
1579 remaining quotient and rem are both 0. */
1580 } while (ntostore
&& (size
|| rem
));
1581 } while (size
!= 0);
1589 else if (base
== 8) {
1598 else if (base
== 16) {
1602 else if (base
!= 10) {
1604 *--p
= '0' + base
%10;
1606 *--p
= '0' + base
/10;
1610 if (p
!= PyString_AS_STRING(str
)) {
1611 char *q
= PyString_AS_STRING(str
);
1614 } while ((*q
++ = *p
++) != '\0');
1616 _PyString_Resize((PyObject
**)&str
,
1617 (Py_ssize_t
) (q
- PyString_AS_STRING(str
)));
1619 return (PyObject
*)str
;
1622 /* Table of digit values for 8-bit string -> integer conversion.
1623 * '0' maps to 0, ..., '9' maps to 9.
1624 * 'a' and 'A' map to 10, ..., 'z' and 'Z' map to 35.
1625 * All other indices map to 37.
1626 * Note that when converting a base B string, a char c is a legitimate
1627 * base B digit iff _PyLong_DigitValue[Py_CHARMASK(c)] < B.
1629 int _PyLong_DigitValue
[256] = {
1630 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37,
1631 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37,
1632 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37,
1633 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 37, 37, 37, 37, 37, 37,
1634 37, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24,
1635 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 37, 37, 37, 37, 37,
1636 37, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24,
1637 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 37, 37, 37, 37, 37,
1638 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37,
1639 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37,
1640 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37,
1641 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37,
1642 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37,
1643 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37,
1644 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37,
1645 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37,
1648 /* *str points to the first digit in a string of base `base` digits. base
1649 * is a power of 2 (2, 4, 8, 16, or 32). *str is set to point to the first
1650 * non-digit (which may be *str!). A normalized long is returned.
1651 * The point to this routine is that it takes time linear in the number of
1652 * string characters.
1654 static PyLongObject
*
1655 long_from_binary_base(char **str
, int base
)
1666 assert(base
>= 2 && base
<= 32 && (base
& (base
- 1)) == 0);
1668 for (bits_per_char
= -1; n
; ++bits_per_char
)
1670 /* n <- total # of bits needed, while setting p to end-of-string */
1671 while (_PyLong_DigitValue
[Py_CHARMASK(*p
)] < base
)
1674 /* n <- # of Python digits needed, = ceiling(n/PyLong_SHIFT). */
1675 n
= (p
- start
) * bits_per_char
+ PyLong_SHIFT
- 1;
1676 if (n
/ bits_per_char
< p
- start
) {
1677 PyErr_SetString(PyExc_ValueError
,
1678 "long string too large to convert");
1681 n
= n
/ PyLong_SHIFT
;
1685 /* Read string from right, and fill in long from left; i.e.,
1686 * from least to most significant in both.
1690 pdigit
= z
->ob_digit
;
1691 while (--p
>= start
) {
1692 int k
= _PyLong_DigitValue
[Py_CHARMASK(*p
)];
1693 assert(k
>= 0 && k
< base
);
1694 accum
|= (twodigits
)k
<< bits_in_accum
;
1695 bits_in_accum
+= bits_per_char
;
1696 if (bits_in_accum
>= PyLong_SHIFT
) {
1697 *pdigit
++ = (digit
)(accum
& PyLong_MASK
);
1698 assert(pdigit
- z
->ob_digit
<= n
);
1699 accum
>>= PyLong_SHIFT
;
1700 bits_in_accum
-= PyLong_SHIFT
;
1701 assert(bits_in_accum
< PyLong_SHIFT
);
1704 if (bits_in_accum
) {
1705 assert(bits_in_accum
<= PyLong_SHIFT
);
1706 *pdigit
++ = (digit
)accum
;
1707 assert(pdigit
- z
->ob_digit
<= n
);
1709 while (pdigit
- z
->ob_digit
< n
)
1711 return long_normalize(z
);
1715 PyLong_FromString(char *str
, char **pend
, int base
)
1718 char *start
, *orig_str
= str
;
1720 PyObject
*strobj
, *strrepr
;
1723 if ((base
!= 0 && base
< 2) || base
> 36) {
1724 PyErr_SetString(PyExc_ValueError
,
1725 "long() arg 2 must be >= 2 and <= 36");
1728 while (*str
!= '\0' && isspace(Py_CHARMASK(*str
)))
1732 else if (*str
== '-') {
1736 while (*str
!= '\0' && isspace(Py_CHARMASK(*str
)))
1739 /* No base given. Deduce the base from the contents
1743 else if (str
[1] == 'x' || str
[1] == 'X')
1745 else if (str
[1] == 'o' || str
[1] == 'O')
1747 else if (str
[1] == 'b' || str
[1] == 'B')
1750 /* "old" (C-style) octal literal, still valid in
1751 2.x, although illegal in 3.x */
1754 /* Whether or not we were deducing the base, skip leading chars
1756 if (str
[0] == '0' &&
1757 ((base
== 16 && (str
[1] == 'x' || str
[1] == 'X')) ||
1758 (base
== 8 && (str
[1] == 'o' || str
[1] == 'O')) ||
1759 (base
== 2 && (str
[1] == 'b' || str
[1] == 'B'))))
1763 if ((base
& (base
- 1)) == 0)
1764 z
= long_from_binary_base(&str
, base
);
1767 Binary bases can be converted in time linear in the number of digits, because
1768 Python's representation base is binary. Other bases (including decimal!) use
1769 the simple quadratic-time algorithm below, complicated by some speed tricks.
1771 First some math: the largest integer that can be expressed in N base-B digits
1772 is B**N-1. Consequently, if we have an N-digit input in base B, the worst-
1773 case number of Python digits needed to hold it is the smallest integer n s.t.
1775 PyLong_BASE**n-1 >= B**N-1 [or, adding 1 to both sides]
1776 PyLong_BASE**n >= B**N [taking logs to base PyLong_BASE]
1777 n >= log(B**N)/log(PyLong_BASE) = N * log(B)/log(PyLong_BASE)
1779 The static array log_base_PyLong_BASE[base] == log(base)/log(PyLong_BASE) so
1780 we can compute this quickly. A Python long with that much space is reserved
1781 near the start, and the result is computed into it.
1783 The input string is actually treated as being in base base**i (i.e., i digits
1784 are processed at a time), where two more static arrays hold:
1786 convwidth_base[base] = the largest integer i such that
1787 base**i <= PyLong_BASE
1788 convmultmax_base[base] = base ** convwidth_base[base]
1790 The first of these is the largest i such that i consecutive input digits
1791 must fit in a single Python digit. The second is effectively the input
1792 base we're really using.
1794 Viewing the input as a sequence <c0, c1, ..., c_n-1> of digits in base
1795 convmultmax_base[base], the result is "simply"
1797 (((c0*B + c1)*B + c2)*B + c3)*B + ... ))) + c_n-1
1799 where B = convmultmax_base[base].
1801 Error analysis: as above, the number of Python digits `n` needed is worst-
1804 n >= N * log(B)/log(PyLong_BASE)
1806 where `N` is the number of input digits in base `B`. This is computed via
1808 size_z = (Py_ssize_t)((scan - str) * log_base_PyLong_BASE[base]) + 1;
1810 below. Two numeric concerns are how much space this can waste, and whether
1811 the computed result can be too small. To be concrete, assume PyLong_BASE =
1812 2**15, which is the default (and it's unlikely anyone changes that).
1814 Waste isn't a problem: provided the first input digit isn't 0, the difference
1815 between the worst-case input with N digits and the smallest input with N
1816 digits is about a factor of B, but B is small compared to PyLong_BASE so at
1817 most one allocated Python digit can remain unused on that count. If
1818 N*log(B)/log(PyLong_BASE) is mathematically an exact integer, then truncating
1819 that and adding 1 returns a result 1 larger than necessary. However, that
1820 can't happen: whenever B is a power of 2, long_from_binary_base() is called
1821 instead, and it's impossible for B**i to be an integer power of 2**15 when B
1822 is not a power of 2 (i.e., it's impossible for N*log(B)/log(PyLong_BASE) to be
1823 an exact integer when B is not a power of 2, since B**i has a prime factor
1824 other than 2 in that case, but (2**15)**j's only prime factor is 2).
1826 The computed result can be too small if the true value of
1827 N*log(B)/log(PyLong_BASE) is a little bit larger than an exact integer, but
1828 due to roundoff errors (in computing log(B), log(PyLong_BASE), their quotient,
1829 and/or multiplying that by N) yields a numeric result a little less than that
1830 integer. Unfortunately, "how close can a transcendental function get to an
1831 integer over some range?" questions are generally theoretically intractable.
1832 Computer analysis via continued fractions is practical: expand
1833 log(B)/log(PyLong_BASE) via continued fractions, giving a sequence i/j of "the
1834 best" rational approximations. Then j*log(B)/log(PyLong_BASE) is
1835 approximately equal to (the integer) i. This shows that we can get very close
1836 to being in trouble, but very rarely. For example, 76573 is a denominator in
1837 one of the continued-fraction approximations to log(10)/log(2**15), and
1840 >>> log(10)/log(2**15)*76573
1843 is very close to an integer. If we were working with IEEE single-precision,
1844 rounding errors could kill us. Finding worst cases in IEEE double-precision
1845 requires better-than-double-precision log() functions, and Tim didn't bother.
1846 Instead the code checks to see whether the allocated space is enough as each
1847 new Python digit is added, and copies the whole thing to a larger long if not.
1848 This should happen extremely rarely, and in fact I don't have a test case
1849 that triggers it(!). Instead the code was tested by artificially allocating
1850 just 1 digit at the start, so that the copying code was exercised for every
1851 digit beyond the first.
1853 register twodigits c
; /* current input character */
1857 twodigits convmultmax
, convmult
;
1861 static double log_base_PyLong_BASE
[37] = {0.0e0
,};
1862 static int convwidth_base
[37] = {0,};
1863 static twodigits convmultmax_base
[37] = {0,};
1865 if (log_base_PyLong_BASE
[base
] == 0.0) {
1866 twodigits convmax
= base
;
1869 log_base_PyLong_BASE
[base
] = (log((double)base
) /
1870 log((double)PyLong_BASE
));
1872 twodigits next
= convmax
* base
;
1873 if (next
> PyLong_BASE
)
1878 convmultmax_base
[base
] = convmax
;
1880 convwidth_base
[base
] = i
;
1883 /* Find length of the string of numeric characters. */
1885 while (_PyLong_DigitValue
[Py_CHARMASK(*scan
)] < base
)
1888 /* Create a long object that can contain the largest possible
1889 * integer with this base and length. Note that there's no
1890 * need to initialize z->ob_digit -- no slot is read up before
1891 * being stored into.
1893 size_z
= (Py_ssize_t
)((scan
- str
) * log_base_PyLong_BASE
[base
]) + 1;
1894 /* Uncomment next line to test exceedingly rare copy code */
1897 z
= _PyLong_New(size_z
);
1902 /* `convwidth` consecutive input digits are treated as a single
1903 * digit in base `convmultmax`.
1905 convwidth
= convwidth_base
[base
];
1906 convmultmax
= convmultmax_base
[base
];
1909 while (str
< scan
) {
1910 /* grab up to convwidth digits from the input string */
1911 c
= (digit
)_PyLong_DigitValue
[Py_CHARMASK(*str
++)];
1912 for (i
= 1; i
< convwidth
&& str
!= scan
; ++i
, ++str
) {
1913 c
= (twodigits
)(c
* base
+
1914 _PyLong_DigitValue
[Py_CHARMASK(*str
)]);
1915 assert(c
< PyLong_BASE
);
1918 convmult
= convmultmax
;
1919 /* Calculate the shift only if we couldn't get
1922 if (i
!= convwidth
) {
1928 /* Multiply z by convmult, and add c. */
1930 pzstop
= pz
+ Py_SIZE(z
);
1931 for (; pz
< pzstop
; ++pz
) {
1932 c
+= (twodigits
)*pz
* convmult
;
1933 *pz
= (digit
)(c
& PyLong_MASK
);
1936 /* carry off the current end? */
1938 assert(c
< PyLong_BASE
);
1939 if (Py_SIZE(z
) < size_z
) {
1945 /* Extremely rare. Get more space. */
1946 assert(Py_SIZE(z
) == size_z
);
1947 tmp
= _PyLong_New(size_z
+ 1);
1952 memcpy(tmp
->ob_digit
,
1954 sizeof(digit
) * size_z
);
1957 z
->ob_digit
[size_z
] = (digit
)c
;
1968 Py_SIZE(z
) = -(Py_SIZE(z
));
1969 if (*str
== 'L' || *str
== 'l')
1971 while (*str
&& isspace(Py_CHARMASK(*str
)))
1977 return (PyObject
*) z
;
1981 slen
= strlen(orig_str
) < 200 ? strlen(orig_str
) : 200;
1982 strobj
= PyString_FromStringAndSize(orig_str
, slen
);
1985 strrepr
= PyObject_Repr(strobj
);
1987 if (strrepr
== NULL
)
1989 PyErr_Format(PyExc_ValueError
,
1990 "invalid literal for long() with base %d: %s",
1991 base
, PyString_AS_STRING(strrepr
));
1996 #ifdef Py_USING_UNICODE
1998 PyLong_FromUnicode(Py_UNICODE
*u
, Py_ssize_t length
, int base
)
2001 char *buffer
= (char *)PyMem_MALLOC(length
+1);
2006 if (PyUnicode_EncodeDecimal(u
, length
, buffer
, NULL
)) {
2010 result
= PyLong_FromString(buffer
, NULL
, base
);
2017 static PyLongObject
*x_divrem
2018 (PyLongObject
*, PyLongObject
*, PyLongObject
**);
2019 static PyObject
*long_long(PyObject
*v
);
2021 /* Long division with remainder, top-level routine */
2024 long_divrem(PyLongObject
*a
, PyLongObject
*b
,
2025 PyLongObject
**pdiv
, PyLongObject
**prem
)
2027 Py_ssize_t size_a
= ABS(Py_SIZE(a
)), size_b
= ABS(Py_SIZE(b
));
2031 PyErr_SetString(PyExc_ZeroDivisionError
,
2032 "long division or modulo by zero");
2035 if (size_a
< size_b
||
2036 (size_a
== size_b
&&
2037 a
->ob_digit
[size_a
-1] < b
->ob_digit
[size_b
-1])) {
2039 *pdiv
= _PyLong_New(0);
2043 *prem
= (PyLongObject
*) a
;
2048 z
= divrem1(a
, b
->ob_digit
[0], &rem
);
2051 *prem
= (PyLongObject
*) PyLong_FromLong((long)rem
);
2052 if (*prem
== NULL
) {
2058 z
= x_divrem(a
, b
, prem
);
2063 The quotient z has the sign of a*b;
2064 the remainder r has the sign of a,
2066 if ((a
->ob_size
< 0) != (b
->ob_size
< 0))
2067 z
->ob_size
= -(z
->ob_size
);
2068 if (a
->ob_size
< 0 && (*prem
)->ob_size
!= 0)
2069 (*prem
)->ob_size
= -((*prem
)->ob_size
);
2074 /* Unsigned long division with remainder -- the algorithm. The arguments v1
2075 and w1 should satisfy 2 <= ABS(Py_SIZE(w1)) <= ABS(Py_SIZE(v1)). */
2077 static PyLongObject
*
2078 x_divrem(PyLongObject
*v1
, PyLongObject
*w1
, PyLongObject
**prem
)
2080 PyLongObject
*v
, *w
, *a
;
2081 Py_ssize_t i
, k
, size_v
, size_w
;
2083 digit wm1
, wm2
, carry
, q
, r
, vtop
, *v0
, *vk
, *w0
, *ak
;
2088 /* We follow Knuth [The Art of Computer Programming, Vol. 2 (3rd
2089 edn.), section 4.3.1, Algorithm D], except that we don't explicitly
2090 handle the special case when the initial estimate q for a quotient
2091 digit is >= PyLong_BASE: the max value for q is PyLong_BASE+1, and
2092 that won't overflow a digit. */
2094 /* allocate space; w will also be used to hold the final remainder */
2095 size_v
= ABS(Py_SIZE(v1
));
2096 size_w
= ABS(Py_SIZE(w1
));
2097 assert(size_v
>= size_w
&& size_w
>= 2); /* Assert checks by div() */
2098 v
= _PyLong_New(size_v
+1);
2103 w
= _PyLong_New(size_w
);
2110 /* normalize: shift w1 left so that its top digit is >= PyLong_BASE/2.
2111 shift v1 left by the same amount. Results go into w and v. */
2112 d
= PyLong_SHIFT
- bits_in_digit(w1
->ob_digit
[size_w
-1]);
2113 carry
= v_lshift(w
->ob_digit
, w1
->ob_digit
, size_w
, d
);
2115 carry
= v_lshift(v
->ob_digit
, v1
->ob_digit
, size_v
, d
);
2116 if (carry
!= 0 || v
->ob_digit
[size_v
-1] >= w
->ob_digit
[size_w
-1]) {
2117 v
->ob_digit
[size_v
] = carry
;
2121 /* Now v->ob_digit[size_v-1] < w->ob_digit[size_w-1], so quotient has
2122 at most (and usually exactly) k = size_v - size_w digits. */
2123 k
= size_v
- size_w
;
2136 for (vk
= v0
+k
, ak
= a
->ob_digit
+ k
; vk
-- > v0
;) {
2137 /* inner loop: divide vk[0:size_w+1] by w0[0:size_w], giving
2138 single-digit quotient q, remainder in vk[0:size_w]. */
2148 /* estimate quotient digit q; may overestimate by 1 (rare) */
2150 assert(vtop
<= wm1
);
2151 vv
= ((twodigits
)vtop
<< PyLong_SHIFT
) | vk
[size_w
-1];
2152 q
= (digit
)(vv
/ wm1
);
2153 r
= (digit
)(vv
- (twodigits
)wm1
* q
); /* r = vv % wm1 */
2154 while ((twodigits
)wm2
* q
> (((twodigits
)r
<< PyLong_SHIFT
)
2158 if (r
>= PyLong_BASE
)
2161 assert(q
<= PyLong_BASE
);
2163 /* subtract q*w0[0:size_w] from vk[0:size_w+1] */
2165 for (i
= 0; i
< size_w
; ++i
) {
2166 /* invariants: -PyLong_BASE <= -q <= zhi <= 0;
2167 -PyLong_BASE * q <= z < PyLong_BASE */
2168 z
= (sdigit
)vk
[i
] + zhi
-
2169 (stwodigits
)q
* (stwodigits
)w0
[i
];
2170 vk
[i
] = (digit
)z
& PyLong_MASK
;
2171 zhi
= (sdigit
)Py_ARITHMETIC_RIGHT_SHIFT(stwodigits
,
2175 /* add w back if q was too large (this branch taken rarely) */
2176 assert((sdigit
)vtop
+ zhi
== -1 || (sdigit
)vtop
+ zhi
== 0);
2177 if ((sdigit
)vtop
+ zhi
< 0) {
2179 for (i
= 0; i
< size_w
; ++i
) {
2180 carry
+= vk
[i
] + w0
[i
];
2181 vk
[i
] = carry
& PyLong_MASK
;
2182 carry
>>= PyLong_SHIFT
;
2187 /* store quotient digit */
2188 assert(q
< PyLong_BASE
);
2192 /* unshift remainder; we reuse w to store the result */
2193 carry
= v_rshift(w0
, v0
, size_w
, d
);
2197 *prem
= long_normalize(w
);
2198 return long_normalize(a
);
2201 /* For a nonzero PyLong a, express a in the form x * 2**e, with 0.5 <=
2202 abs(x) < 1.0 and e >= 0; return x and put e in *e. Here x is
2203 rounded to DBL_MANT_DIG significant bits using round-half-to-even.
2204 If a == 0, return 0.0 and set *e = 0. If the resulting exponent
2205 e is larger than PY_SSIZE_T_MAX, raise OverflowError and return
2208 /* attempt to define 2.0**DBL_MANT_DIG as a compile-time constant */
2209 #if DBL_MANT_DIG == 53
2210 #define EXP2_DBL_MANT_DIG 9007199254740992.0
2212 #define EXP2_DBL_MANT_DIG (ldexp(1.0, DBL_MANT_DIG))
2216 _PyLong_Frexp(PyLongObject
*a
, Py_ssize_t
*e
)
2218 Py_ssize_t a_size
, a_bits
, shift_digits
, shift_bits
, x_size
;
2219 /* See below for why x_digits is always large enough. */
2220 digit rem
, x_digits
[2 + (DBL_MANT_DIG
+ 1) / PyLong_SHIFT
];
2222 /* Correction term for round-half-to-even rounding. For a digit x,
2223 "x + half_even_correction[x & 7]" gives x rounded to the nearest
2224 multiple of 4, rounding ties to a multiple of 8. */
2225 static const int half_even_correction
[8] = {0, -1, -2, 1, 0, -1, 2, 1};
2227 a_size
= ABS(Py_SIZE(a
));
2229 /* Special case for 0: significand 0.0, exponent 0. */
2233 a_bits
= bits_in_digit(a
->ob_digit
[a_size
-1]);
2234 /* The following is an overflow-free version of the check
2235 "if ((a_size - 1) * PyLong_SHIFT + a_bits > PY_SSIZE_T_MAX) ..." */
2236 if (a_size
>= (PY_SSIZE_T_MAX
- 1) / PyLong_SHIFT
+ 1 &&
2237 (a_size
> (PY_SSIZE_T_MAX
- 1) / PyLong_SHIFT
+ 1 ||
2238 a_bits
> (PY_SSIZE_T_MAX
- 1) % PyLong_SHIFT
+ 1))
2240 a_bits
= (a_size
- 1) * PyLong_SHIFT
+ a_bits
;
2242 /* Shift the first DBL_MANT_DIG + 2 bits of a into x_digits[0:x_size]
2243 (shifting left if a_bits <= DBL_MANT_DIG + 2).
2245 Number of digits needed for result: write // for floor division.
2246 Then if shifting left, we end up using
2248 1 + a_size + (DBL_MANT_DIG + 2 - a_bits) // PyLong_SHIFT
2250 digits. If shifting right, we use
2252 a_size - (a_bits - DBL_MANT_DIG - 2) // PyLong_SHIFT
2254 digits. Using a_size = 1 + (a_bits - 1) // PyLong_SHIFT along with
2257 m // PyLong_SHIFT + n // PyLong_SHIFT <= (m + n) // PyLong_SHIFT
2258 m // PyLong_SHIFT - n // PyLong_SHIFT <=
2259 1 + (m - n - 1) // PyLong_SHIFT,
2261 valid for any integers m and n, we find that x_size satisfies
2263 x_size <= 2 + (DBL_MANT_DIG + 1) // PyLong_SHIFT
2267 if (a_bits
<= DBL_MANT_DIG
+ 2) {
2268 shift_digits
= (DBL_MANT_DIG
+ 2 - a_bits
) / PyLong_SHIFT
;
2269 shift_bits
= (DBL_MANT_DIG
+ 2 - a_bits
) % PyLong_SHIFT
;
2271 while (x_size
< shift_digits
)
2272 x_digits
[x_size
++] = 0;
2273 rem
= v_lshift(x_digits
+ x_size
, a
->ob_digit
, a_size
,
2276 x_digits
[x_size
++] = rem
;
2279 shift_digits
= (a_bits
- DBL_MANT_DIG
- 2) / PyLong_SHIFT
;
2280 shift_bits
= (a_bits
- DBL_MANT_DIG
- 2) % PyLong_SHIFT
;
2281 rem
= v_rshift(x_digits
, a
->ob_digit
+ shift_digits
,
2282 a_size
- shift_digits
, (int)shift_bits
);
2283 x_size
= a_size
- shift_digits
;
2284 /* For correct rounding below, we need the least significant
2285 bit of x to be 'sticky' for this shift: if any of the bits
2286 shifted out was nonzero, we set the least significant bit
2291 while (shift_digits
> 0)
2292 if (a
->ob_digit
[--shift_digits
]) {
2297 assert(1 <= x_size
&&
2298 x_size
<= (Py_ssize_t
)(sizeof(x_digits
)/sizeof(digit
)));
2300 /* Round, and convert to double. */
2301 x_digits
[0] += half_even_correction
[x_digits
[0] & 7];
2302 dx
= x_digits
[--x_size
];
2304 dx
= dx
* PyLong_BASE
+ x_digits
[--x_size
];
2306 /* Rescale; make correction if result is 1.0. */
2307 dx
/= 4.0 * EXP2_DBL_MANT_DIG
;
2309 if (a_bits
== PY_SSIZE_T_MAX
)
2316 return Py_SIZE(a
) < 0 ? -dx
: dx
;
2319 /* exponent > PY_SSIZE_T_MAX */
2320 PyErr_SetString(PyExc_OverflowError
,
2321 "huge integer: number of bits overflows a Py_ssize_t");
2326 /* Get a C double from a long int object. Rounds to the nearest double,
2327 using the round-half-to-even rule in the case of a tie. */
2330 PyLong_AsDouble(PyObject
*v
)
2332 Py_ssize_t exponent
;
2335 if (v
== NULL
|| !PyLong_Check(v
)) {
2336 PyErr_BadInternalCall();
2339 x
= _PyLong_Frexp((PyLongObject
*)v
, &exponent
);
2340 if ((x
== -1.0 && PyErr_Occurred()) || exponent
> DBL_MAX_EXP
) {
2341 PyErr_SetString(PyExc_OverflowError
,
2342 "long int too large to convert to float");
2345 return ldexp(x
, (int)exponent
);
2351 long_dealloc(PyObject
*v
)
2353 Py_TYPE(v
)->tp_free(v
);
2357 long_repr(PyObject
*v
)
2359 return _PyLong_Format(v
, 10, 1, 0);
2363 long_str(PyObject
*v
)
2365 return _PyLong_Format(v
, 10, 0, 0);
2369 long_compare(PyLongObject
*a
, PyLongObject
*b
)
2373 if (Py_SIZE(a
) != Py_SIZE(b
)) {
2374 sign
= Py_SIZE(a
) - Py_SIZE(b
);
2377 Py_ssize_t i
= ABS(Py_SIZE(a
));
2378 while (--i
>= 0 && a
->ob_digit
[i
] == b
->ob_digit
[i
])
2383 sign
= (sdigit
)a
->ob_digit
[i
] - (sdigit
)b
->ob_digit
[i
];
2388 return sign
< 0 ? -1 : sign
> 0 ? 1 : 0;
2392 long_hash(PyLongObject
*v
)
2398 /* This is designed so that Python ints and longs with the
2399 same value hash to the same value, otherwise comparisons
2400 of mapping keys will turn out weird */
2408 /* The following loop produces a C unsigned long x such that x is
2409 congruent to the absolute value of v modulo ULONG_MAX. The
2410 resulting x is nonzero if and only if v is. */
2412 /* Force a native long #-bits (32 or 64) circular shift */
2413 x
= (x
>> (8*SIZEOF_LONG
-PyLong_SHIFT
)) | (x
<< PyLong_SHIFT
);
2414 x
+= v
->ob_digit
[i
];
2415 /* If the addition above overflowed we compensate by
2416 incrementing. This preserves the value modulo
2418 if (x
< v
->ob_digit
[i
])
2422 if (x
== (unsigned long)-1)
2423 x
= (unsigned long)-2;
2428 /* Add the absolute values of two long integers. */
2430 static PyLongObject
*
2431 x_add(PyLongObject
*a
, PyLongObject
*b
)
2433 Py_ssize_t size_a
= ABS(Py_SIZE(a
)), size_b
= ABS(Py_SIZE(b
));
2438 /* Ensure a is the larger of the two: */
2439 if (size_a
< size_b
) {
2440 { PyLongObject
*temp
= a
; a
= b
; b
= temp
; }
2441 { Py_ssize_t size_temp
= size_a
;
2443 size_b
= size_temp
; }
2445 z
= _PyLong_New(size_a
+1);
2448 for (i
= 0; i
< size_b
; ++i
) {
2449 carry
+= a
->ob_digit
[i
] + b
->ob_digit
[i
];
2450 z
->ob_digit
[i
] = carry
& PyLong_MASK
;
2451 carry
>>= PyLong_SHIFT
;
2453 for (; i
< size_a
; ++i
) {
2454 carry
+= a
->ob_digit
[i
];
2455 z
->ob_digit
[i
] = carry
& PyLong_MASK
;
2456 carry
>>= PyLong_SHIFT
;
2458 z
->ob_digit
[i
] = carry
;
2459 return long_normalize(z
);
2462 /* Subtract the absolute values of two integers. */
2464 static PyLongObject
*
2465 x_sub(PyLongObject
*a
, PyLongObject
*b
)
2467 Py_ssize_t size_a
= ABS(Py_SIZE(a
)), size_b
= ABS(Py_SIZE(b
));
2473 /* Ensure a is the larger of the two: */
2474 if (size_a
< size_b
) {
2476 { PyLongObject
*temp
= a
; a
= b
; b
= temp
; }
2477 { Py_ssize_t size_temp
= size_a
;
2479 size_b
= size_temp
; }
2481 else if (size_a
== size_b
) {
2482 /* Find highest digit where a and b differ: */
2484 while (--i
>= 0 && a
->ob_digit
[i
] == b
->ob_digit
[i
])
2487 return _PyLong_New(0);
2488 if (a
->ob_digit
[i
] < b
->ob_digit
[i
]) {
2490 { PyLongObject
*temp
= a
; a
= b
; b
= temp
; }
2492 size_a
= size_b
= i
+1;
2494 z
= _PyLong_New(size_a
);
2497 for (i
= 0; i
< size_b
; ++i
) {
2498 /* The following assumes unsigned arithmetic
2499 works module 2**N for some N>PyLong_SHIFT. */
2500 borrow
= a
->ob_digit
[i
] - b
->ob_digit
[i
] - borrow
;
2501 z
->ob_digit
[i
] = borrow
& PyLong_MASK
;
2502 borrow
>>= PyLong_SHIFT
;
2503 borrow
&= 1; /* Keep only one sign bit */
2505 for (; i
< size_a
; ++i
) {
2506 borrow
= a
->ob_digit
[i
] - borrow
;
2507 z
->ob_digit
[i
] = borrow
& PyLong_MASK
;
2508 borrow
>>= PyLong_SHIFT
;
2509 borrow
&= 1; /* Keep only one sign bit */
2511 assert(borrow
== 0);
2513 z
->ob_size
= -(z
->ob_size
);
2514 return long_normalize(z
);
2518 long_add(PyLongObject
*v
, PyLongObject
*w
)
2520 PyLongObject
*a
, *b
, *z
;
2522 CONVERT_BINOP((PyObject
*)v
, (PyObject
*)w
, &a
, &b
);
2524 if (a
->ob_size
< 0) {
2525 if (b
->ob_size
< 0) {
2527 if (z
!= NULL
&& z
->ob_size
!= 0)
2528 z
->ob_size
= -(z
->ob_size
);
2541 return (PyObject
*)z
;
2545 long_sub(PyLongObject
*v
, PyLongObject
*w
)
2547 PyLongObject
*a
, *b
, *z
;
2549 CONVERT_BINOP((PyObject
*)v
, (PyObject
*)w
, &a
, &b
);
2551 if (a
->ob_size
< 0) {
2556 if (z
!= NULL
&& z
->ob_size
!= 0)
2557 z
->ob_size
= -(z
->ob_size
);
2567 return (PyObject
*)z
;
2570 /* Grade school multiplication, ignoring the signs.
2571 * Returns the absolute value of the product, or NULL if error.
2573 static PyLongObject
*
2574 x_mul(PyLongObject
*a
, PyLongObject
*b
)
2577 Py_ssize_t size_a
= ABS(Py_SIZE(a
));
2578 Py_ssize_t size_b
= ABS(Py_SIZE(b
));
2581 z
= _PyLong_New(size_a
+ size_b
);
2585 memset(z
->ob_digit
, 0, Py_SIZE(z
) * sizeof(digit
));
2587 /* Efficient squaring per HAC, Algorithm 14.16:
2588 * http://www.cacr.math.uwaterloo.ca/hac/about/chap14.pdf
2589 * Gives slightly less than a 2x speedup when a == b,
2590 * via exploiting that each entry in the multiplication
2591 * pyramid appears twice (except for the size_a squares).
2593 for (i
= 0; i
< size_a
; ++i
) {
2595 twodigits f
= a
->ob_digit
[i
];
2596 digit
*pz
= z
->ob_digit
+ (i
<< 1);
2597 digit
*pa
= a
->ob_digit
+ i
+ 1;
2598 digit
*paend
= a
->ob_digit
+ size_a
;
2605 carry
= *pz
+ f
* f
;
2606 *pz
++ = (digit
)(carry
& PyLong_MASK
);
2607 carry
>>= PyLong_SHIFT
;
2608 assert(carry
<= PyLong_MASK
);
2610 /* Now f is added in twice in each column of the
2611 * pyramid it appears. Same as adding f<<1 once.
2614 while (pa
< paend
) {
2615 carry
+= *pz
+ *pa
++ * f
;
2616 *pz
++ = (digit
)(carry
& PyLong_MASK
);
2617 carry
>>= PyLong_SHIFT
;
2618 assert(carry
<= (PyLong_MASK
<< 1));
2622 *pz
++ = (digit
)(carry
& PyLong_MASK
);
2623 carry
>>= PyLong_SHIFT
;
2626 *pz
+= (digit
)(carry
& PyLong_MASK
);
2627 assert((carry
>> PyLong_SHIFT
) == 0);
2630 else { /* a is not the same as b -- gradeschool long mult */
2631 for (i
= 0; i
< size_a
; ++i
) {
2632 twodigits carry
= 0;
2633 twodigits f
= a
->ob_digit
[i
];
2634 digit
*pz
= z
->ob_digit
+ i
;
2635 digit
*pb
= b
->ob_digit
;
2636 digit
*pbend
= b
->ob_digit
+ size_b
;
2643 while (pb
< pbend
) {
2644 carry
+= *pz
+ *pb
++ * f
;
2645 *pz
++ = (digit
)(carry
& PyLong_MASK
);
2646 carry
>>= PyLong_SHIFT
;
2647 assert(carry
<= PyLong_MASK
);
2650 *pz
+= (digit
)(carry
& PyLong_MASK
);
2651 assert((carry
>> PyLong_SHIFT
) == 0);
2654 return long_normalize(z
);
2657 /* A helper for Karatsuba multiplication (k_mul).
2658 Takes a long "n" and an integer "size" representing the place to
2659 split, and sets low and high such that abs(n) == (high << size) + low,
2660 viewing the shift as being by digits. The sign bit is ignored, and
2661 the return values are >= 0.
2662 Returns 0 on success, -1 on failure.
2665 kmul_split(PyLongObject
*n
,
2667 PyLongObject
**high
,
2670 PyLongObject
*hi
, *lo
;
2671 Py_ssize_t size_lo
, size_hi
;
2672 const Py_ssize_t size_n
= ABS(Py_SIZE(n
));
2674 size_lo
= MIN(size_n
, size
);
2675 size_hi
= size_n
- size_lo
;
2677 if ((hi
= _PyLong_New(size_hi
)) == NULL
)
2679 if ((lo
= _PyLong_New(size_lo
)) == NULL
) {
2684 memcpy(lo
->ob_digit
, n
->ob_digit
, size_lo
* sizeof(digit
));
2685 memcpy(hi
->ob_digit
, n
->ob_digit
+ size_lo
, size_hi
* sizeof(digit
));
2687 *high
= long_normalize(hi
);
2688 *low
= long_normalize(lo
);
2692 static PyLongObject
*k_lopsided_mul(PyLongObject
*a
, PyLongObject
*b
);
2694 /* Karatsuba multiplication. Ignores the input signs, and returns the
2695 * absolute value of the product (or NULL if error).
2696 * See Knuth Vol. 2 Chapter 4.3.3 (Pp. 294-295).
2698 static PyLongObject
*
2699 k_mul(PyLongObject
*a
, PyLongObject
*b
)
2701 Py_ssize_t asize
= ABS(Py_SIZE(a
));
2702 Py_ssize_t bsize
= ABS(Py_SIZE(b
));
2703 PyLongObject
*ah
= NULL
;
2704 PyLongObject
*al
= NULL
;
2705 PyLongObject
*bh
= NULL
;
2706 PyLongObject
*bl
= NULL
;
2707 PyLongObject
*ret
= NULL
;
2708 PyLongObject
*t1
, *t2
, *t3
;
2709 Py_ssize_t shift
; /* the number of digits we split off */
2712 /* (ah*X+al)(bh*X+bl) = ah*bh*X*X + (ah*bl + al*bh)*X + al*bl
2713 * Let k = (ah+al)*(bh+bl) = ah*bl + al*bh + ah*bh + al*bl
2714 * Then the original product is
2715 * ah*bh*X*X + (k - ah*bh - al*bl)*X + al*bl
2716 * By picking X to be a power of 2, "*X" is just shifting, and it's
2717 * been reduced to 3 multiplies on numbers half the size.
2720 /* We want to split based on the larger number; fiddle so that b
2723 if (asize
> bsize
) {
2733 /* Use gradeschool math when either number is too small. */
2734 i
= a
== b
? KARATSUBA_SQUARE_CUTOFF
: KARATSUBA_CUTOFF
;
2737 return _PyLong_New(0);
2742 /* If a is small compared to b, splitting on b gives a degenerate
2743 * case with ah==0, and Karatsuba may be (even much) less efficient
2744 * than "grade school" then. However, we can still win, by viewing
2745 * b as a string of "big digits", each of width a->ob_size. That
2746 * leads to a sequence of balanced calls to k_mul.
2748 if (2 * asize
<= bsize
)
2749 return k_lopsided_mul(a
, b
);
2751 /* Split a & b into hi & lo pieces. */
2753 if (kmul_split(a
, shift
, &ah
, &al
) < 0) goto fail
;
2754 assert(Py_SIZE(ah
) > 0); /* the split isn't degenerate */
2762 else if (kmul_split(b
, shift
, &bh
, &bl
) < 0) goto fail
;
2765 * 1. Allocate result space (asize + bsize digits: that's always
2767 * 2. Compute ah*bh, and copy into result at 2*shift.
2768 * 3. Compute al*bl, and copy into result at 0. Note that this
2769 * can't overlap with #2.
2770 * 4. Subtract al*bl from the result, starting at shift. This may
2771 * underflow (borrow out of the high digit), but we don't care:
2772 * we're effectively doing unsigned arithmetic mod
2773 * PyLong_BASE**(sizea + sizeb), and so long as the *final* result fits,
2774 * borrows and carries out of the high digit can be ignored.
2775 * 5. Subtract ah*bh from the result, starting at shift.
2776 * 6. Compute (ah+al)*(bh+bl), and add it into the result starting
2780 /* 1. Allocate result space. */
2781 ret
= _PyLong_New(asize
+ bsize
);
2782 if (ret
== NULL
) goto fail
;
2784 /* Fill with trash, to catch reference to uninitialized digits. */
2785 memset(ret
->ob_digit
, 0xDF, Py_SIZE(ret
) * sizeof(digit
));
2788 /* 2. t1 <- ah*bh, and copy into high digits of result. */
2789 if ((t1
= k_mul(ah
, bh
)) == NULL
) goto fail
;
2790 assert(Py_SIZE(t1
) >= 0);
2791 assert(2*shift
+ Py_SIZE(t1
) <= Py_SIZE(ret
));
2792 memcpy(ret
->ob_digit
+ 2*shift
, t1
->ob_digit
,
2793 Py_SIZE(t1
) * sizeof(digit
));
2795 /* Zero-out the digits higher than the ah*bh copy. */
2796 i
= Py_SIZE(ret
) - 2*shift
- Py_SIZE(t1
);
2798 memset(ret
->ob_digit
+ 2*shift
+ Py_SIZE(t1
), 0,
2801 /* 3. t2 <- al*bl, and copy into the low digits. */
2802 if ((t2
= k_mul(al
, bl
)) == NULL
) {
2806 assert(Py_SIZE(t2
) >= 0);
2807 assert(Py_SIZE(t2
) <= 2*shift
); /* no overlap with high digits */
2808 memcpy(ret
->ob_digit
, t2
->ob_digit
, Py_SIZE(t2
) * sizeof(digit
));
2810 /* Zero out remaining digits. */
2811 i
= 2*shift
- Py_SIZE(t2
); /* number of uninitialized digits */
2813 memset(ret
->ob_digit
+ Py_SIZE(t2
), 0, i
* sizeof(digit
));
2815 /* 4 & 5. Subtract ah*bh (t1) and al*bl (t2). We do al*bl first
2816 * because it's fresher in cache.
2818 i
= Py_SIZE(ret
) - shift
; /* # digits after shift */
2819 (void)v_isub(ret
->ob_digit
+ shift
, i
, t2
->ob_digit
, Py_SIZE(t2
));
2822 (void)v_isub(ret
->ob_digit
+ shift
, i
, t1
->ob_digit
, Py_SIZE(t1
));
2825 /* 6. t3 <- (ah+al)(bh+bl), and add into result. */
2826 if ((t1
= x_add(ah
, al
)) == NULL
) goto fail
;
2835 else if ((t2
= x_add(bh
, bl
)) == NULL
) {
2846 if (t3
== NULL
) goto fail
;
2847 assert(Py_SIZE(t3
) >= 0);
2849 /* Add t3. It's not obvious why we can't run out of room here.
2850 * See the (*) comment after this function.
2852 (void)v_iadd(ret
->ob_digit
+ shift
, i
, t3
->ob_digit
, Py_SIZE(t3
));
2855 return long_normalize(ret
);
2866 /* (*) Why adding t3 can't "run out of room" above.
2868 Let f(x) mean the floor of x and c(x) mean the ceiling of x. Some facts
2871 1. For any integer i, i = c(i/2) + f(i/2). In particular,
2872 bsize = c(bsize/2) + f(bsize/2).
2873 2. shift = f(bsize/2)
2875 4. Since we call k_lopsided_mul if asize*2 <= bsize, asize*2 > bsize in this
2876 routine, so asize > bsize/2 >= f(bsize/2) in this routine.
2878 We allocated asize + bsize result digits, and add t3 into them at an offset
2879 of shift. This leaves asize+bsize-shift allocated digit positions for t3
2880 to fit into, = (by #1 and #2) asize + f(bsize/2) + c(bsize/2) - f(bsize/2) =
2881 asize + c(bsize/2) available digit positions.
2883 bh has c(bsize/2) digits, and bl at most f(size/2) digits. So bh+hl has
2884 at most c(bsize/2) digits + 1 bit.
2886 If asize == bsize, ah has c(bsize/2) digits, else ah has at most f(bsize/2)
2887 digits, and al has at most f(bsize/2) digits in any case. So ah+al has at
2888 most (asize == bsize ? c(bsize/2) : f(bsize/2)) digits + 1 bit.
2890 The product (ah+al)*(bh+bl) therefore has at most
2892 c(bsize/2) + (asize == bsize ? c(bsize/2) : f(bsize/2)) digits + 2 bits
2894 and we have asize + c(bsize/2) available digit positions. We need to show
2895 this is always enough. An instance of c(bsize/2) cancels out in both, so
2896 the question reduces to whether asize digits is enough to hold
2897 (asize == bsize ? c(bsize/2) : f(bsize/2)) digits + 2 bits. If asize < bsize,
2898 then we're asking whether asize digits >= f(bsize/2) digits + 2 bits. By #4,
2899 asize is at least f(bsize/2)+1 digits, so this in turn reduces to whether 1
2900 digit is enough to hold 2 bits. This is so since PyLong_SHIFT=15 >= 2. If
2901 asize == bsize, then we're asking whether bsize digits is enough to hold
2902 c(bsize/2) digits + 2 bits, or equivalently (by #1) whether f(bsize/2) digits
2903 is enough to hold 2 bits. This is so if bsize >= 2, which holds because
2904 bsize >= KARATSUBA_CUTOFF >= 2.
2906 Note that since there's always enough room for (ah+al)*(bh+bl), and that's
2907 clearly >= each of ah*bh and al*bl, there's always enough room to subtract
2908 ah*bh and al*bl too.
2911 /* b has at least twice the digits of a, and a is big enough that Karatsuba
2912 * would pay off *if* the inputs had balanced sizes. View b as a sequence
2913 * of slices, each with a->ob_size digits, and multiply the slices by a,
2914 * one at a time. This gives k_mul balanced inputs to work with, and is
2915 * also cache-friendly (we compute one double-width slice of the result
2916 * at a time, then move on, never backtracking except for the helpful
2917 * single-width slice overlap between successive partial sums).
2919 static PyLongObject
*
2920 k_lopsided_mul(PyLongObject
*a
, PyLongObject
*b
)
2922 const Py_ssize_t asize
= ABS(Py_SIZE(a
));
2923 Py_ssize_t bsize
= ABS(Py_SIZE(b
));
2924 Py_ssize_t nbdone
; /* # of b digits already multiplied */
2926 PyLongObject
*bslice
= NULL
;
2928 assert(asize
> KARATSUBA_CUTOFF
);
2929 assert(2 * asize
<= bsize
);
2931 /* Allocate result space, and zero it out. */
2932 ret
= _PyLong_New(asize
+ bsize
);
2935 memset(ret
->ob_digit
, 0, Py_SIZE(ret
) * sizeof(digit
));
2937 /* Successive slices of b are copied into bslice. */
2938 bslice
= _PyLong_New(asize
);
2944 PyLongObject
*product
;
2945 const Py_ssize_t nbtouse
= MIN(bsize
, asize
);
2947 /* Multiply the next slice of b by a. */
2948 memcpy(bslice
->ob_digit
, b
->ob_digit
+ nbdone
,
2949 nbtouse
* sizeof(digit
));
2950 Py_SIZE(bslice
) = nbtouse
;
2951 product
= k_mul(a
, bslice
);
2952 if (product
== NULL
)
2955 /* Add into result. */
2956 (void)v_iadd(ret
->ob_digit
+ nbdone
, Py_SIZE(ret
) - nbdone
,
2957 product
->ob_digit
, Py_SIZE(product
));
2965 return long_normalize(ret
);
2974 long_mul(PyLongObject
*v
, PyLongObject
*w
)
2976 PyLongObject
*a
, *b
, *z
;
2978 if (!convert_binop((PyObject
*)v
, (PyObject
*)w
, &a
, &b
)) {
2979 Py_INCREF(Py_NotImplemented
);
2980 return Py_NotImplemented
;
2984 /* Negate if exactly one of the inputs is negative. */
2985 if (((a
->ob_size
^ b
->ob_size
) < 0) && z
)
2986 z
->ob_size
= -(z
->ob_size
);
2989 return (PyObject
*)z
;
2992 /* The / and % operators are now defined in terms of divmod().
2993 The expression a mod b has the value a - b*floor(a/b).
2994 The long_divrem function gives the remainder after division of
2995 |a| by |b|, with the sign of a. This is also expressed
2996 as a - b*trunc(a/b), if trunc truncates towards zero.
3003 So, to get from rem to mod, we have to add b if a and b
3004 have different signs. We then subtract one from the 'div'
3005 part of the outcome to keep the invariant intact. */
3008 * *pdiv, *pmod = divmod(v, w)
3009 * NULL can be passed for pdiv or pmod, in which case that part of
3010 * the result is simply thrown away. The caller owns a reference to
3011 * each of these it requests (does not pass NULL for).
3014 l_divmod(PyLongObject
*v
, PyLongObject
*w
,
3015 PyLongObject
**pdiv
, PyLongObject
**pmod
)
3017 PyLongObject
*div
, *mod
;
3019 if (long_divrem(v
, w
, &div
, &mod
) < 0)
3021 if ((Py_SIZE(mod
) < 0 && Py_SIZE(w
) > 0) ||
3022 (Py_SIZE(mod
) > 0 && Py_SIZE(w
) < 0)) {
3025 temp
= (PyLongObject
*) long_add(mod
, w
);
3032 one
= (PyLongObject
*) PyLong_FromLong(1L);
3034 (temp
= (PyLongObject
*) long_sub(div
, one
)) == NULL
) {
3058 long_div(PyObject
*v
, PyObject
*w
)
3060 PyLongObject
*a
, *b
, *div
;
3062 CONVERT_BINOP(v
, w
, &a
, &b
);
3063 if (l_divmod(a
, b
, &div
, NULL
) < 0)
3067 return (PyObject
*)div
;
3071 long_classic_div(PyObject
*v
, PyObject
*w
)
3073 PyLongObject
*a
, *b
, *div
;
3075 CONVERT_BINOP(v
, w
, &a
, &b
);
3076 if (Py_DivisionWarningFlag
&&
3077 PyErr_Warn(PyExc_DeprecationWarning
, "classic long division") < 0)
3079 else if (l_divmod(a
, b
, &div
, NULL
) < 0)
3083 return (PyObject
*)div
;
3086 /* PyLong/PyLong -> float, with correctly rounded result. */
3088 #define MANT_DIG_DIGITS (DBL_MANT_DIG / PyLong_SHIFT)
3089 #define MANT_DIG_BITS (DBL_MANT_DIG % PyLong_SHIFT)
3092 long_true_divide(PyObject
*v
, PyObject
*w
)
3094 PyLongObject
*a
, *b
, *x
;
3095 Py_ssize_t a_size
, b_size
, shift
, extra_bits
, diff
, x_size
, x_bits
;
3097 int inexact
, negate
, a_is_small
, b_is_small
;
3100 CONVERT_BINOP(v
, w
, &a
, &b
);
3103 Method in a nutshell:
3105 0. reduce to case a, b > 0; filter out obvious underflow/overflow
3106 1. choose a suitable integer 'shift'
3107 2. use integer arithmetic to compute x = floor(2**-shift*a/b)
3108 3. adjust x for correct rounding
3109 4. convert x to a double dx with the same value
3110 5. return ldexp(dx, shift).
3114 0. For any a, a/0 raises ZeroDivisionError; for nonzero b, 0/b
3115 returns either 0.0 or -0.0, depending on the sign of b. For a and
3116 b both nonzero, ignore signs of a and b, and add the sign back in
3117 at the end. Now write a_bits and b_bits for the bit lengths of a
3118 and b respectively (that is, a_bits = 1 + floor(log_2(a)); likewise
3121 2**(a_bits - b_bits - 1) < a/b < 2**(a_bits - b_bits + 1).
3123 So if a_bits - b_bits > DBL_MAX_EXP then a/b > 2**DBL_MAX_EXP and
3124 so overflows. Similarly, if a_bits - b_bits < DBL_MIN_EXP -
3125 DBL_MANT_DIG - 1 then a/b underflows to 0. With these cases out of
3126 the way, we can assume that
3128 DBL_MIN_EXP - DBL_MANT_DIG - 1 <= a_bits - b_bits <= DBL_MAX_EXP.
3130 1. The integer 'shift' is chosen so that x has the right number of
3131 bits for a double, plus two or three extra bits that will be used
3132 in the rounding decisions. Writing a_bits and b_bits for the
3133 number of significant bits in a and b respectively, a
3134 straightforward formula for shift is:
3136 shift = a_bits - b_bits - DBL_MANT_DIG - 2
3138 This is fine in the usual case, but if a/b is smaller than the
3139 smallest normal float then it can lead to double rounding on an
3140 IEEE 754 platform, giving incorrectly rounded results. So we
3141 adjust the formula slightly. The actual formula used is:
3143 shift = MAX(a_bits - b_bits, DBL_MIN_EXP) - DBL_MANT_DIG - 2
3145 2. The quantity x is computed by first shifting a (left -shift bits
3146 if shift <= 0, right shift bits if shift > 0) and then dividing by
3147 b. For both the shift and the division, we keep track of whether
3148 the result is inexact, in a flag 'inexact'; this information is
3149 needed at the rounding stage.
3151 With the choice of shift above, together with our assumption that
3152 a_bits - b_bits >= DBL_MIN_EXP - DBL_MANT_DIG - 1, it follows
3155 3. Now x * 2**shift <= a/b < (x+1) * 2**shift. We want to replace
3156 this with an exactly representable float of the form
3158 round(x/2**extra_bits) * 2**(extra_bits+shift).
3160 For float representability, we need x/2**extra_bits <
3161 2**DBL_MANT_DIG and extra_bits + shift >= DBL_MIN_EXP -
3162 DBL_MANT_DIG. This translates to the condition:
3164 extra_bits >= MAX(x_bits, DBL_MIN_EXP - shift) - DBL_MANT_DIG
3166 To round, we just modify the bottom digit of x in-place; this can
3167 end up giving a digit with value > PyLONG_MASK, but that's not a
3168 problem since digits can hold values up to 2*PyLONG_MASK+1.
3170 With the original choices for shift above, extra_bits will always
3171 be 2 or 3. Then rounding under the round-half-to-even rule, we
3172 round up iff the most significant of the extra bits is 1, and
3173 either: (a) the computation of x in step 2 had an inexact result,
3174 or (b) at least one other of the extra bits is 1, or (c) the least
3175 significant bit of x (above those to be rounded) is 1.
3177 4. Conversion to a double is straightforward; all floating-point
3178 operations involved in the conversion are exact, so there's no
3179 danger of rounding errors.
3181 5. Use ldexp(x, shift) to compute x*2**shift, the final result.
3182 The result will always be exactly representable as a double, except
3183 in the case that it overflows. To avoid dependence on the exact
3184 behaviour of ldexp on overflow, we check for overflow before
3185 applying ldexp. The result of ldexp is adjusted for sign before
3189 /* Reduce to case where a and b are both positive. */
3190 a_size
= ABS(Py_SIZE(a
));
3191 b_size
= ABS(Py_SIZE(b
));
3192 negate
= (Py_SIZE(a
) < 0) ^ (Py_SIZE(b
) < 0);
3194 PyErr_SetString(PyExc_ZeroDivisionError
,
3195 "division by zero");
3199 goto underflow_or_zero
;
3201 /* Fast path for a and b small (exactly representable in a double).
3202 Relies on floating-point division being correctly rounded; results
3203 may be subject to double rounding on x86 machines that operate with
3204 the x87 FPU set to 64-bit precision. */
3205 a_is_small
= a_size
<= MANT_DIG_DIGITS
||
3206 (a_size
== MANT_DIG_DIGITS
+1 &&
3207 a
->ob_digit
[MANT_DIG_DIGITS
] >> MANT_DIG_BITS
== 0);
3208 b_is_small
= b_size
<= MANT_DIG_DIGITS
||
3209 (b_size
== MANT_DIG_DIGITS
+1 &&
3210 b
->ob_digit
[MANT_DIG_DIGITS
] >> MANT_DIG_BITS
== 0);
3211 if (a_is_small
&& b_is_small
) {
3213 da
= a
->ob_digit
[--a_size
];
3215 da
= da
* PyLong_BASE
+ a
->ob_digit
[--a_size
];
3216 db
= b
->ob_digit
[--b_size
];
3218 db
= db
* PyLong_BASE
+ b
->ob_digit
[--b_size
];
3223 /* Catch obvious cases of underflow and overflow */
3224 diff
= a_size
- b_size
;
3225 if (diff
> PY_SSIZE_T_MAX
/PyLong_SHIFT
- 1)
3226 /* Extreme overflow */
3228 else if (diff
< 1 - PY_SSIZE_T_MAX
/PyLong_SHIFT
)
3229 /* Extreme underflow */
3230 goto underflow_or_zero
;
3231 /* Next line is now safe from overflowing a Py_ssize_t */
3232 diff
= diff
* PyLong_SHIFT
+ bits_in_digit(a
->ob_digit
[a_size
- 1]) -
3233 bits_in_digit(b
->ob_digit
[b_size
- 1]);
3234 /* Now diff = a_bits - b_bits. */
3235 if (diff
> DBL_MAX_EXP
)
3237 else if (diff
< DBL_MIN_EXP
- DBL_MANT_DIG
- 1)
3238 goto underflow_or_zero
;
3240 /* Choose value for shift; see comments for step 1 above. */
3241 shift
= MAX(diff
, DBL_MIN_EXP
) - DBL_MANT_DIG
- 2;
3245 /* x = abs(a * 2**-shift) */
3247 Py_ssize_t i
, shift_digits
= -shift
/ PyLong_SHIFT
;
3249 /* x = a << -shift */
3250 if (a_size
>= PY_SSIZE_T_MAX
- 1 - shift_digits
) {
3251 /* In practice, it's probably impossible to end up
3252 here. Both a and b would have to be enormous,
3253 using close to SIZE_T_MAX bytes of memory each. */
3254 PyErr_SetString(PyExc_OverflowError
,
3255 "intermediate overflow during division");
3258 x
= _PyLong_New(a_size
+ shift_digits
+ 1);
3261 for (i
= 0; i
< shift_digits
; i
++)
3263 rem
= v_lshift(x
->ob_digit
+ shift_digits
, a
->ob_digit
,
3264 a_size
, -shift
% PyLong_SHIFT
);
3265 x
->ob_digit
[a_size
+ shift_digits
] = rem
;
3268 Py_ssize_t shift_digits
= shift
/ PyLong_SHIFT
;
3270 /* x = a >> shift */
3271 assert(a_size
>= shift_digits
);
3272 x
= _PyLong_New(a_size
- shift_digits
);
3275 rem
= v_rshift(x
->ob_digit
, a
->ob_digit
+ shift_digits
,
3276 a_size
- shift_digits
, shift
% PyLong_SHIFT
);
3277 /* set inexact if any of the bits shifted out is nonzero */
3280 while (!inexact
&& shift_digits
> 0)
3281 if (a
->ob_digit
[--shift_digits
])
3285 x_size
= Py_SIZE(x
);
3287 /* x //= b. If the remainder is nonzero, set inexact. We own the only
3288 reference to x, so it's safe to modify it in-place. */
3290 digit rem
= inplace_divrem1(x
->ob_digit
, x
->ob_digit
, x_size
,
3297 PyLongObject
*div
, *rem
;
3298 div
= x_divrem(x
, b
, &rem
);
3307 x_size
= ABS(Py_SIZE(x
));
3308 assert(x_size
> 0); /* result of division is never zero */
3309 x_bits
= (x_size
-1)*PyLong_SHIFT
+bits_in_digit(x
->ob_digit
[x_size
-1]);
3311 /* The number of extra bits that have to be rounded away. */
3312 extra_bits
= MAX(x_bits
, DBL_MIN_EXP
- shift
) - DBL_MANT_DIG
;
3313 assert(extra_bits
== 2 || extra_bits
== 3);
3315 /* Round by directly modifying the low digit of x. */
3316 mask
= (digit
)1 << (extra_bits
- 1);
3317 low
= x
->ob_digit
[0] | inexact
;
3318 if (low
& mask
&& low
& (3*mask
-1))
3320 x
->ob_digit
[0] = low
& ~(mask
-1U);
3322 /* Convert x to a double dx; the conversion is exact. */
3323 dx
= x
->ob_digit
[--x_size
];
3325 dx
= dx
* PyLong_BASE
+ x
->ob_digit
[--x_size
];
3328 /* Check whether ldexp result will overflow a double. */
3329 if (shift
+ x_bits
>= DBL_MAX_EXP
&&
3330 (shift
+ x_bits
> DBL_MAX_EXP
|| dx
== ldexp(1.0, (int)x_bits
)))
3332 result
= ldexp(dx
, (int)shift
);
3337 return PyFloat_FromDouble(negate
? -result
: result
);
3342 return PyFloat_FromDouble(negate
? -0.0 : 0.0);
3345 PyErr_SetString(PyExc_OverflowError
,
3346 "integer division result too large for a float");
3354 long_mod(PyObject
*v
, PyObject
*w
)
3356 PyLongObject
*a
, *b
, *mod
;
3358 CONVERT_BINOP(v
, w
, &a
, &b
);
3360 if (l_divmod(a
, b
, NULL
, &mod
) < 0)
3364 return (PyObject
*)mod
;
3368 long_divmod(PyObject
*v
, PyObject
*w
)
3370 PyLongObject
*a
, *b
, *div
, *mod
;
3373 CONVERT_BINOP(v
, w
, &a
, &b
);
3375 if (l_divmod(a
, b
, &div
, &mod
) < 0) {
3382 PyTuple_SetItem(z
, 0, (PyObject
*) div
);
3383 PyTuple_SetItem(z
, 1, (PyObject
*) mod
);
3396 long_pow(PyObject
*v
, PyObject
*w
, PyObject
*x
)
3398 PyLongObject
*a
, *b
, *c
; /* a,b,c = v,w,x */
3399 int negativeOutput
= 0; /* if x<0 return negative output */
3401 PyLongObject
*z
= NULL
; /* accumulated result */
3402 Py_ssize_t i
, j
, k
; /* counters */
3403 PyLongObject
*temp
= NULL
;
3405 /* 5-ary values. If the exponent is large enough, table is
3406 * precomputed so that table[i] == a**i % c for i in range(32).
3408 PyLongObject
*table
[32] = {0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
3409 0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0};
3411 /* a, b, c = v, w, x */
3412 CONVERT_BINOP(v
, w
, &a
, &b
);
3413 if (PyLong_Check(x
)) {
3414 c
= (PyLongObject
*)x
;
3417 else if (PyInt_Check(x
)) {
3418 c
= (PyLongObject
*)PyLong_FromLong(PyInt_AS_LONG(x
));
3422 else if (x
== Py_None
)
3427 Py_INCREF(Py_NotImplemented
);
3428 return Py_NotImplemented
;
3431 if (Py_SIZE(b
) < 0) { /* if exponent is negative */
3433 PyErr_SetString(PyExc_TypeError
, "pow() 2nd argument "
3434 "cannot be negative when 3rd argument specified");
3438 /* else return a float. This works because we know
3439 that this calls float_pow() which converts its
3440 arguments to double. */
3443 return PyFloat_Type
.tp_as_number
->nb_power(v
, w
, x
);
3449 raise ValueError() */
3450 if (Py_SIZE(c
) == 0) {
3451 PyErr_SetString(PyExc_ValueError
,
3452 "pow() 3rd argument cannot be 0");
3457 negativeOutput = True
3458 modulus = -modulus */
3459 if (Py_SIZE(c
) < 0) {
3461 temp
= (PyLongObject
*)_PyLong_Copy(c
);
3467 c
->ob_size
= - c
->ob_size
;
3472 if ((Py_SIZE(c
) == 1) && (c
->ob_digit
[0] == 1)) {
3473 z
= (PyLongObject
*)PyLong_FromLong(0L);
3477 /* Reduce base by modulus in some cases:
3478 1. If base < 0. Forcing the base non-negative makes things easier.
3479 2. If base is obviously larger than the modulus. The "small
3480 exponent" case later can multiply directly by base repeatedly,
3481 while the "large exponent" case multiplies directly by base 31
3482 times. It can be unboundedly faster to multiply by
3483 base % modulus instead.
3484 We could _always_ do this reduction, but l_divmod() isn't cheap,
3485 so we only do it when it buys something. */
3486 if (Py_SIZE(a
) < 0 || Py_SIZE(a
) > Py_SIZE(c
)) {
3487 if (l_divmod(a
, c
, NULL
, &temp
) < 0)
3495 /* At this point a, b, and c are guaranteed non-negative UNLESS
3496 c is NULL, in which case a may be negative. */
3498 z
= (PyLongObject
*)PyLong_FromLong(1L);
3502 /* Perform a modular reduction, X = X % c, but leave X alone if c
3508 if (l_divmod(X, c, NULL, &temp) < 0) \
3516 /* Multiply two values, then reduce the result:
3517 result = X*Y % c. If c is NULL, skip the mod. */
3518 #define MULT(X, Y, result) \
3520 temp = (PyLongObject *)long_mul(X, Y); \
3523 Py_XDECREF(result); \
3529 if (Py_SIZE(b
) <= FIVEARY_CUTOFF
) {
3530 /* Left-to-right binary exponentiation (HAC Algorithm 14.79) */
3531 /* http://www.cacr.math.uwaterloo.ca/hac/about/chap14.pdf */
3532 for (i
= Py_SIZE(b
) - 1; i
>= 0; --i
) {
3533 digit bi
= b
->ob_digit
[i
];
3535 for (j
= (digit
)1 << (PyLong_SHIFT
-1); j
!= 0; j
>>= 1) {
3543 /* Left-to-right 5-ary exponentiation (HAC Algorithm 14.82) */
3544 Py_INCREF(z
); /* still holds 1L */
3546 for (i
= 1; i
< 32; ++i
)
3547 MULT(table
[i
-1], a
, table
[i
]);
3549 for (i
= Py_SIZE(b
) - 1; i
>= 0; --i
) {
3550 const digit bi
= b
->ob_digit
[i
];
3552 for (j
= PyLong_SHIFT
- 5; j
>= 0; j
-= 5) {
3553 const int index
= (bi
>> j
) & 0x1f;
3554 for (k
= 0; k
< 5; ++k
)
3557 MULT(z
, table
[index
], z
);
3562 if (negativeOutput
&& (Py_SIZE(z
) != 0)) {
3563 temp
= (PyLongObject
*)long_sub(z
, c
);
3579 if (Py_SIZE(b
) > FIVEARY_CUTOFF
) {
3580 for (i
= 0; i
< 32; ++i
)
3581 Py_XDECREF(table
[i
]);
3587 return (PyObject
*)z
;
3591 long_invert(PyLongObject
*v
)
3593 /* Implement ~x as -(x+1) */
3596 w
= (PyLongObject
*)PyLong_FromLong(1L);
3599 x
= (PyLongObject
*) long_add(v
, w
);
3603 Py_SIZE(x
) = -(Py_SIZE(x
));
3604 return (PyObject
*)x
;
3608 long_neg(PyLongObject
*v
)
3611 if (v
->ob_size
== 0 && PyLong_CheckExact(v
)) {
3614 return (PyObject
*) v
;
3616 z
= (PyLongObject
*)_PyLong_Copy(v
);
3618 z
->ob_size
= -(v
->ob_size
);
3619 return (PyObject
*)z
;
3623 long_abs(PyLongObject
*v
)
3628 return long_long((PyObject
*)v
);
3632 long_nonzero(PyLongObject
*v
)
3634 return Py_SIZE(v
) != 0;
3638 long_rshift(PyLongObject
*v
, PyLongObject
*w
)
3640 PyLongObject
*a
, *b
;
3641 PyLongObject
*z
= NULL
;
3642 Py_ssize_t shiftby
, newsize
, wordshift
, loshift
, hishift
, i
, j
;
3643 digit lomask
, himask
;
3645 CONVERT_BINOP((PyObject
*)v
, (PyObject
*)w
, &a
, &b
);
3647 if (Py_SIZE(a
) < 0) {
3648 /* Right shifting negative numbers is harder */
3649 PyLongObject
*a1
, *a2
;
3650 a1
= (PyLongObject
*) long_invert(a
);
3653 a2
= (PyLongObject
*) long_rshift(a1
, b
);
3657 z
= (PyLongObject
*) long_invert(a2
);
3661 shiftby
= PyLong_AsSsize_t((PyObject
*)b
);
3662 if (shiftby
== -1L && PyErr_Occurred())
3665 PyErr_SetString(PyExc_ValueError
,
3666 "negative shift count");
3669 wordshift
= shiftby
/ PyLong_SHIFT
;
3670 newsize
= ABS(Py_SIZE(a
)) - wordshift
;
3675 return (PyObject
*)z
;
3677 loshift
= shiftby
% PyLong_SHIFT
;
3678 hishift
= PyLong_SHIFT
- loshift
;
3679 lomask
= ((digit
)1 << hishift
) - 1;
3680 himask
= PyLong_MASK
^ lomask
;
3681 z
= _PyLong_New(newsize
);
3685 Py_SIZE(z
) = -(Py_SIZE(z
));
3686 for (i
= 0, j
= wordshift
; i
< newsize
; i
++, j
++) {
3687 z
->ob_digit
[i
] = (a
->ob_digit
[j
] >> loshift
) & lomask
;
3689 z
->ob_digit
[i
] |= (a
->ob_digit
[j
+1] << hishift
) & himask
;
3691 z
= long_normalize(z
);
3696 return (PyObject
*) z
;
3701 long_lshift(PyObject
*v
, PyObject
*w
)
3703 /* This version due to Tim Peters */
3704 PyLongObject
*a
, *b
;
3705 PyLongObject
*z
= NULL
;
3706 Py_ssize_t shiftby
, oldsize
, newsize
, wordshift
, remshift
, i
, j
;
3709 CONVERT_BINOP(v
, w
, &a
, &b
);
3711 shiftby
= PyLong_AsSsize_t((PyObject
*)b
);
3712 if (shiftby
== -1L && PyErr_Occurred())
3715 PyErr_SetString(PyExc_ValueError
, "negative shift count");
3718 /* wordshift, remshift = divmod(shiftby, PyLong_SHIFT) */
3719 wordshift
= shiftby
/ PyLong_SHIFT
;
3720 remshift
= shiftby
- wordshift
* PyLong_SHIFT
;
3722 oldsize
= ABS(a
->ob_size
);
3723 newsize
= oldsize
+ wordshift
;
3726 z
= _PyLong_New(newsize
);
3730 z
->ob_size
= -(z
->ob_size
);
3731 for (i
= 0; i
< wordshift
; i
++)
3734 for (i
= wordshift
, j
= 0; j
< oldsize
; i
++, j
++) {
3735 accum
|= (twodigits
)a
->ob_digit
[j
] << remshift
;
3736 z
->ob_digit
[i
] = (digit
)(accum
& PyLong_MASK
);
3737 accum
>>= PyLong_SHIFT
;
3740 z
->ob_digit
[newsize
-1] = (digit
)accum
;
3743 z
= long_normalize(z
);
3747 return (PyObject
*) z
;
3750 /* Compute two's complement of digit vector a[0:m], writing result to
3751 z[0:m]. The digit vector a need not be normalized, but should not
3752 be entirely zero. a and z may point to the same digit vector. */
3755 v_complement(digit
*z
, digit
*a
, Py_ssize_t m
)
3759 for (i
= 0; i
< m
; ++i
) {
3760 carry
+= a
[i
] ^ PyLong_MASK
;
3761 z
[i
] = carry
& PyLong_MASK
;
3762 carry
>>= PyLong_SHIFT
;
3767 /* Bitwise and/xor/or operations */
3770 long_bitwise(PyLongObject
*a
,
3771 int op
, /* '&', '|', '^' */
3774 int nega
, negb
, negz
;
3775 Py_ssize_t size_a
, size_b
, size_z
, i
;
3778 /* Bitwise operations for negative numbers operate as though
3779 on a two's complement representation. So convert arguments
3780 from sign-magnitude to two's complement, and convert the
3781 result back to sign-magnitude at the end. */
3783 /* If a is negative, replace it by its two's complement. */
3784 size_a
= ABS(Py_SIZE(a
));
3785 nega
= Py_SIZE(a
) < 0;
3787 z
= _PyLong_New(size_a
);
3790 v_complement(z
->ob_digit
, a
->ob_digit
, size_a
);
3794 /* Keep reference count consistent. */
3798 size_b
= ABS(Py_SIZE(b
));
3799 negb
= Py_SIZE(b
) < 0;
3801 z
= _PyLong_New(size_b
);
3806 v_complement(z
->ob_digit
, b
->ob_digit
, size_b
);
3812 /* Swap a and b if necessary to ensure size_a >= size_b. */
3813 if (size_a
< size_b
) {
3814 z
= a
; a
= b
; b
= z
;
3815 size_z
= size_a
; size_a
= size_b
; size_b
= size_z
;
3816 negz
= nega
; nega
= negb
; negb
= negz
;
3819 /* JRH: The original logic here was to allocate the result value (z)
3820 as the longer of the two operands. However, there are some cases
3821 where the result is guaranteed to be shorter than that: AND of two
3822 positives, OR of two negatives: use the shorter number. AND with
3823 mixed signs: use the positive number. OR with mixed signs: use the
3833 size_z
= negb
? size_a
: size_b
;
3837 size_z
= negb
? size_b
: size_a
;
3840 PyErr_BadArgument();
3844 /* We allow an extra digit if z is negative, to make sure that
3845 the final two's complement of z doesn't overflow. */
3846 z
= _PyLong_New(size_z
+ negz
);
3853 /* Compute digits for overlap of a and b. */
3856 for (i
= 0; i
< size_b
; ++i
)
3857 z
->ob_digit
[i
] = a
->ob_digit
[i
] & b
->ob_digit
[i
];
3860 for (i
= 0; i
< size_b
; ++i
)
3861 z
->ob_digit
[i
] = a
->ob_digit
[i
] | b
->ob_digit
[i
];
3864 for (i
= 0; i
< size_b
; ++i
)
3865 z
->ob_digit
[i
] = a
->ob_digit
[i
] ^ b
->ob_digit
[i
];
3868 PyErr_BadArgument();
3872 /* Copy any remaining digits of a, inverting if necessary. */
3873 if (op
== '^' && negb
)
3874 for (; i
< size_z
; ++i
)
3875 z
->ob_digit
[i
] = a
->ob_digit
[i
] ^ PyLong_MASK
;
3876 else if (i
< size_z
)
3877 memcpy(&z
->ob_digit
[i
], &a
->ob_digit
[i
],
3878 (size_z
-i
)*sizeof(digit
));
3880 /* Complement result if negative. */
3882 Py_SIZE(z
) = -(Py_SIZE(z
));
3883 z
->ob_digit
[size_z
] = PyLong_MASK
;
3884 v_complement(z
->ob_digit
, z
->ob_digit
, size_z
+1);
3889 return (PyObject
*)long_normalize(z
);
3893 long_and(PyObject
*v
, PyObject
*w
)
3895 PyLongObject
*a
, *b
;
3897 CONVERT_BINOP(v
, w
, &a
, &b
);
3898 c
= long_bitwise(a
, '&', b
);
3905 long_xor(PyObject
*v
, PyObject
*w
)
3907 PyLongObject
*a
, *b
;
3909 CONVERT_BINOP(v
, w
, &a
, &b
);
3910 c
= long_bitwise(a
, '^', b
);
3917 long_or(PyObject
*v
, PyObject
*w
)
3919 PyLongObject
*a
, *b
;
3921 CONVERT_BINOP(v
, w
, &a
, &b
);
3922 c
= long_bitwise(a
, '|', b
);
3929 long_coerce(PyObject
**pv
, PyObject
**pw
)
3931 if (PyInt_Check(*pw
)) {
3932 *pw
= PyLong_FromLong(PyInt_AS_LONG(*pw
));
3938 else if (PyLong_Check(*pw
)) {
3943 return 1; /* Can't do it */
3947 long_long(PyObject
*v
)
3949 if (PyLong_CheckExact(v
))
3952 v
= _PyLong_Copy((PyLongObject
*)v
);
3957 long_int(PyObject
*v
)
3960 x
= PyLong_AsLong(v
);
3961 if (PyErr_Occurred()) {
3962 if (PyErr_ExceptionMatches(PyExc_OverflowError
)) {
3964 if (PyLong_CheckExact(v
)) {
3969 return _PyLong_Copy((PyLongObject
*)v
);
3974 return PyInt_FromLong(x
);
3978 long_float(PyObject
*v
)
3981 result
= PyLong_AsDouble(v
);
3982 if (result
== -1.0 && PyErr_Occurred())
3984 return PyFloat_FromDouble(result
);
3988 long_oct(PyObject
*v
)
3990 return _PyLong_Format(v
, 8, 1, 0);
3994 long_hex(PyObject
*v
)
3996 return _PyLong_Format(v
, 16, 1, 0);
4000 long_subtype_new(PyTypeObject
*type
, PyObject
*args
, PyObject
*kwds
);
4003 long_new(PyTypeObject
*type
, PyObject
*args
, PyObject
*kwds
)
4006 int base
= -909; /* unlikely! */
4007 static char *kwlist
[] = {"x", "base", 0};
4009 if (type
!= &PyLong_Type
)
4010 return long_subtype_new(type
, args
, kwds
); /* Wimp out */
4011 if (!PyArg_ParseTupleAndKeywords(args
, kwds
, "|Oi:long", kwlist
,
4016 PyErr_SetString(PyExc_TypeError
,
4017 "long() missing string argument");
4020 return PyLong_FromLong(0L);
4023 return PyNumber_Long(x
);
4024 else if (PyString_Check(x
)) {
4025 /* Since PyLong_FromString doesn't have a length parameter,
4026 * check here for possible NULs in the string. */
4027 char *string
= PyString_AS_STRING(x
);
4028 if (strlen(string
) != (size_t)PyString_Size(x
)) {
4029 /* create a repr() of the input string,
4030 * just like PyLong_FromString does. */
4032 srepr
= PyObject_Repr(x
);
4035 PyErr_Format(PyExc_ValueError
,
4036 "invalid literal for long() with base %d: %s",
4037 base
, PyString_AS_STRING(srepr
));
4041 return PyLong_FromString(PyString_AS_STRING(x
), NULL
, base
);
4043 #ifdef Py_USING_UNICODE
4044 else if (PyUnicode_Check(x
))
4045 return PyLong_FromUnicode(PyUnicode_AS_UNICODE(x
),
4046 PyUnicode_GET_SIZE(x
),
4050 PyErr_SetString(PyExc_TypeError
,
4051 "long() can't convert non-string with explicit base");
4056 /* Wimpy, slow approach to tp_new calls for subtypes of long:
4057 first create a regular long from whatever arguments we got,
4058 then allocate a subtype instance and initialize it from
4059 the regular long. The regular long is then thrown away.
4062 long_subtype_new(PyTypeObject
*type
, PyObject
*args
, PyObject
*kwds
)
4064 PyLongObject
*tmp
, *newobj
;
4067 assert(PyType_IsSubtype(type
, &PyLong_Type
));
4068 tmp
= (PyLongObject
*)long_new(&PyLong_Type
, args
, kwds
);
4071 assert(PyLong_CheckExact(tmp
));
4075 newobj
= (PyLongObject
*)type
->tp_alloc(type
, n
);
4076 if (newobj
== NULL
) {
4080 assert(PyLong_Check(newobj
));
4081 Py_SIZE(newobj
) = Py_SIZE(tmp
);
4082 for (i
= 0; i
< n
; i
++)
4083 newobj
->ob_digit
[i
] = tmp
->ob_digit
[i
];
4085 return (PyObject
*)newobj
;
4089 long_getnewargs(PyLongObject
*v
)
4091 return Py_BuildValue("(N)", _PyLong_Copy(v
));
4095 long_get0(PyLongObject
*v
, void *context
) {
4096 return PyLong_FromLong(0L);
4100 long_get1(PyLongObject
*v
, void *context
) {
4101 return PyLong_FromLong(1L);
4105 long__format__(PyObject
*self
, PyObject
*args
)
4107 PyObject
*format_spec
;
4109 if (!PyArg_ParseTuple(args
, "O:__format__", &format_spec
))
4111 if (PyBytes_Check(format_spec
))
4112 return _PyLong_FormatAdvanced(self
,
4113 PyBytes_AS_STRING(format_spec
),
4114 PyBytes_GET_SIZE(format_spec
));
4115 if (PyUnicode_Check(format_spec
)) {
4116 /* Convert format_spec to a str */
4118 PyObject
*str_spec
= PyObject_Str(format_spec
);
4120 if (str_spec
== NULL
)
4123 result
= _PyLong_FormatAdvanced(self
,
4124 PyBytes_AS_STRING(str_spec
),
4125 PyBytes_GET_SIZE(str_spec
));
4127 Py_DECREF(str_spec
);
4130 PyErr_SetString(PyExc_TypeError
, "__format__ requires str or unicode");
4135 long_sizeof(PyLongObject
*v
)
4139 res
= v
->ob_type
->tp_basicsize
+ ABS(Py_SIZE(v
))*sizeof(digit
);
4140 return PyInt_FromSsize_t(res
);
4144 long_bit_length(PyLongObject
*v
)
4146 PyLongObject
*result
, *x
, *y
;
4147 Py_ssize_t ndigits
, msd_bits
= 0;
4151 assert(PyLong_Check(v
));
4153 ndigits
= ABS(Py_SIZE(v
));
4155 return PyInt_FromLong(0);
4157 msd
= v
->ob_digit
[ndigits
-1];
4162 msd_bits
+= (long)(BitLengthTable
[msd
]);
4164 if (ndigits
<= PY_SSIZE_T_MAX
/PyLong_SHIFT
)
4165 return PyInt_FromSsize_t((ndigits
-1)*PyLong_SHIFT
+ msd_bits
);
4167 /* expression above may overflow; use Python integers instead */
4168 result
= (PyLongObject
*)PyLong_FromSsize_t(ndigits
- 1);
4171 x
= (PyLongObject
*)PyLong_FromLong(PyLong_SHIFT
);
4174 y
= (PyLongObject
*)long_mul(result
, x
);
4181 x
= (PyLongObject
*)PyLong_FromLong((long)msd_bits
);
4184 y
= (PyLongObject
*)long_add(result
, x
);
4191 return (PyObject
*)result
;
4198 PyDoc_STRVAR(long_bit_length_doc
,
4199 "long.bit_length() -> int or long\n\
4201 Number of bits necessary to represent self in binary.\n\
4204 >>> (37L).bit_length()\n\
4209 long_is_finite(PyObject
*v
)
4215 static PyMethodDef long_methods
[] = {
4216 {"conjugate", (PyCFunction
)long_long
, METH_NOARGS
,
4217 "Returns self, the complex conjugate of any long."},
4218 {"bit_length", (PyCFunction
)long_bit_length
, METH_NOARGS
,
4219 long_bit_length_doc
},
4221 {"is_finite", (PyCFunction
)long_is_finite
, METH_NOARGS
,
4222 "Returns always True."},
4224 {"__trunc__", (PyCFunction
)long_long
, METH_NOARGS
,
4225 "Truncating an Integral returns itself."},
4226 {"__getnewargs__", (PyCFunction
)long_getnewargs
, METH_NOARGS
},
4227 {"__format__", (PyCFunction
)long__format__
, METH_VARARGS
},
4228 {"__sizeof__", (PyCFunction
)long_sizeof
, METH_NOARGS
,
4229 "Returns size in memory, in bytes"},
4230 {NULL
, NULL
} /* sentinel */
4233 static PyGetSetDef long_getset
[] = {
4235 (getter
)long_long
, (setter
)NULL
,
4236 "the real part of a complex number",
4239 (getter
)long_get0
, (setter
)NULL
,
4240 "the imaginary part of a complex number",
4243 (getter
)long_long
, (setter
)NULL
,
4244 "the numerator of a rational number in lowest terms",
4247 (getter
)long_get1
, (setter
)NULL
,
4248 "the denominator of a rational number in lowest terms",
4250 {NULL
} /* Sentinel */
4253 PyDoc_STRVAR(long_doc
,
4254 "long(x=0) -> long\n\
4255 long(x, base=10) -> long\n\
4257 Convert a number or string to a long integer, or return 0L if no arguments\n\
4258 are given. If x is floating point, the conversion truncates towards zero.\n\
4260 If x is not a number or if base is given, then x must be a string or\n\
4261 Unicode object representing an integer literal in the given base. The\n\
4262 literal can be preceded by '+' or '-' and be surrounded by whitespace.\n\
4263 The base defaults to 10. Valid bases are 0 and 2-36. Base 0 means to\n\
4264 interpret the base from the string as an integer literal.\n\
4265 >>> int('0b100', base=0)\n\
4268 static PyNumberMethods long_as_number
= {
4269 (binaryfunc
)long_add
, /*nb_add*/
4270 (binaryfunc
)long_sub
, /*nb_subtract*/
4271 (binaryfunc
)long_mul
, /*nb_multiply*/
4272 long_classic_div
, /*nb_divide*/
4273 long_mod
, /*nb_remainder*/
4274 long_divmod
, /*nb_divmod*/
4275 long_pow
, /*nb_power*/
4276 (unaryfunc
)long_neg
, /*nb_negative*/
4277 (unaryfunc
)long_long
, /*tp_positive*/
4278 (unaryfunc
)long_abs
, /*tp_absolute*/
4279 (inquiry
)long_nonzero
, /*tp_nonzero*/
4280 (unaryfunc
)long_invert
, /*nb_invert*/
4281 long_lshift
, /*nb_lshift*/
4282 (binaryfunc
)long_rshift
, /*nb_rshift*/
4283 long_and
, /*nb_and*/
4284 long_xor
, /*nb_xor*/
4286 long_coerce
, /*nb_coerce*/
4287 long_int
, /*nb_int*/
4288 long_long
, /*nb_long*/
4289 long_float
, /*nb_float*/
4290 long_oct
, /*nb_oct*/
4291 long_hex
, /*nb_hex*/
4292 0, /* nb_inplace_add */
4293 0, /* nb_inplace_subtract */
4294 0, /* nb_inplace_multiply */
4295 0, /* nb_inplace_divide */
4296 0, /* nb_inplace_remainder */
4297 0, /* nb_inplace_power */
4298 0, /* nb_inplace_lshift */
4299 0, /* nb_inplace_rshift */
4300 0, /* nb_inplace_and */
4301 0, /* nb_inplace_xor */
4302 0, /* nb_inplace_or */
4303 long_div
, /* nb_floor_divide */
4304 long_true_divide
, /* nb_true_divide */
4305 0, /* nb_inplace_floor_divide */
4306 0, /* nb_inplace_true_divide */
4307 long_long
, /* nb_index */
4310 PyTypeObject PyLong_Type
= {
4311 PyObject_HEAD_INIT(&PyType_Type
)
4313 "long", /* tp_name */
4314 offsetof(PyLongObject
, ob_digit
), /* tp_basicsize */
4315 sizeof(digit
), /* tp_itemsize */
4316 long_dealloc
, /* tp_dealloc */
4320 (cmpfunc
)long_compare
, /* tp_compare */
4321 long_repr
, /* tp_repr */
4322 &long_as_number
, /* tp_as_number */
4323 0, /* tp_as_sequence */
4324 0, /* tp_as_mapping */
4325 (hashfunc
)long_hash
, /* tp_hash */
4327 long_str
, /* tp_str */
4328 PyObject_GenericGetAttr
, /* tp_getattro */
4329 0, /* tp_setattro */
4330 0, /* tp_as_buffer */
4331 Py_TPFLAGS_DEFAULT
| Py_TPFLAGS_CHECKTYPES
|
4332 Py_TPFLAGS_BASETYPE
| Py_TPFLAGS_LONG_SUBCLASS
, /* tp_flags */
4333 long_doc
, /* tp_doc */
4334 0, /* tp_traverse */
4336 0, /* tp_richcompare */
4337 0, /* tp_weaklistoffset */
4339 0, /* tp_iternext */
4340 long_methods
, /* tp_methods */
4342 long_getset
, /* tp_getset */
4345 0, /* tp_descr_get */
4346 0, /* tp_descr_set */
4347 0, /* tp_dictoffset */
4350 long_new
, /* tp_new */
4351 PyObject_Del
, /* tp_free */
4354 static PyTypeObject Long_InfoType
;
4356 PyDoc_STRVAR(long_info__doc__
,
4359 A struct sequence that holds information about Python's\n\
4360 internal representation of integers. The attributes are read only.");
4362 static PyStructSequence_Field long_info_fields
[] = {
4363 {"bits_per_digit", "size of a digit in bits"},
4364 {"sizeof_digit", "size in bytes of the C type used to represent a digit"},
4368 static PyStructSequence_Desc long_info_desc
= {
4369 "sys.long_info", /* name */
4370 long_info__doc__
, /* doc */
4371 long_info_fields
, /* fields */
4372 2 /* number of fields */
4376 PyLong_GetInfo(void)
4378 PyObject
* long_info
;
4380 long_info
= PyStructSequence_New(&Long_InfoType
);
4381 if (long_info
== NULL
)
4383 PyStructSequence_SET_ITEM(long_info
, field
++,
4384 PyInt_FromLong(PyLong_SHIFT
));
4385 PyStructSequence_SET_ITEM(long_info
, field
++,
4386 PyInt_FromLong(sizeof(digit
)));
4387 if (PyErr_Occurred()) {
4388 Py_CLEAR(long_info
);
4397 /* initialize long_info */
4398 if (Long_InfoType
.tp_name
== 0)
4399 PyStructSequence_InitType(&Long_InfoType
, &long_info_desc
);