1
/* Long (arbitrary precision) integer object implementation */
3
/* XXX The functional organization of this file is terrible */
6
#include "longintrepr.h"
13
#define NSMALLPOSINTS 257
16
#define NSMALLNEGINTS 5
19
/* convert a PyLong of size 1, 0 or -1 to an sdigit */
20
#define MEDIUM_VALUE(x) (Py_SIZE(x) < 0 ? -(sdigit)(x)->ob_digit[0] : \
21
(Py_SIZE(x) == 0 ? (sdigit)0 : \
22
(sdigit)(x)->ob_digit[0]))
23
#define ABS(x) ((x) < 0 ? -(x) : (x))
25
#if NSMALLNEGINTS + NSMALLPOSINTS > 0
26
/* Small integers are preallocated in this array so that they
28
The integers that are preallocated are those in the range
29
-NSMALLNEGINTS (inclusive) to NSMALLPOSINTS (not inclusive).
31
static PyLongObject small_ints[NSMALLNEGINTS + NSMALLPOSINTS];
33
int quick_int_allocs, quick_neg_int_allocs;
37
get_small_int(sdigit ival)
39
PyObject *v = (PyObject*)(small_ints + ival + NSMALLNEGINTS);
45
quick_neg_int_allocs++;
49
#define CHECK_SMALL_INT(ival) \
50
do if (-NSMALLNEGINTS <= ival && ival < NSMALLPOSINTS) { \
51
return get_small_int((sdigit)ival); \
55
maybe_small_long(PyLongObject *v)
57
if (v && ABS(Py_SIZE(v)) <= 1) {
58
sdigit ival = MEDIUM_VALUE(v);
59
if (-NSMALLNEGINTS <= ival && ival < NSMALLPOSINTS) {
61
return (PyLongObject *)get_small_int(ival);
67
#define CHECK_SMALL_INT(ival)
68
#define maybe_small_long(val) (val)
71
/* If a freshly-allocated long is already shared, it must
72
be a small integer, so negating it must go to PyLong_FromLong */
74
do if (Py_REFCNT(x) == 1) Py_SIZE(x) = -Py_SIZE(x); \
75
else { PyObject* tmp=PyLong_FromLong(-MEDIUM_VALUE(x)); \
76
Py_DECREF(x); (x) = (PyLongObject*)tmp; } \
78
/* For long multiplication, use the O(N**2) school algorithm unless
79
* both operands contain more than KARATSUBA_CUTOFF digits (this
80
* being an internal Python long digit, in base BASE).
82
#define KARATSUBA_CUTOFF 70
83
#define KARATSUBA_SQUARE_CUTOFF (2 * KARATSUBA_CUTOFF)
85
/* For exponentiation, use the binary left-to-right algorithm
86
* unless the exponent contains more than FIVEARY_CUTOFF digits.
87
* In that case, do 5 bits at a time. The potential drawback is that
88
* a table of 2**5 intermediate results is computed.
90
#define FIVEARY_CUTOFF 8
94
#define MAX(x, y) ((x) < (y) ? (y) : (x))
95
#define MIN(x, y) ((x) > (y) ? (y) : (x))
97
#define SIGCHECK(PyTryBlock) \
98
if (--_Py_Ticker < 0) { \
99
_Py_Ticker = _Py_CheckInterval; \
100
if (PyErr_CheckSignals()) PyTryBlock \
103
/* Normalize (remove leading zeros from) a long int object.
104
Doesn't attempt to free the storage--in most cases, due to the nature
105
of the algorithms used, this could save at most be one word anyway. */
107
static PyLongObject *
108
long_normalize(register PyLongObject *v)
110
Py_ssize_t j = ABS(Py_SIZE(v));
113
while (i > 0 && v->ob_digit[i-1] == 0)
116
Py_SIZE(v) = (Py_SIZE(v) < 0) ? -(i) : i;
120
/* Allocate a new long int object with size digits.
121
Return NULL and set exception if we run out of memory. */
123
#define MAX_LONG_DIGITS \
124
((PY_SSIZE_T_MAX - offsetof(PyLongObject, ob_digit))/sizeof(digit))
127
_PyLong_New(Py_ssize_t size)
129
PyLongObject *result;
130
/* Number of bytes needed is: offsetof(PyLongObject, ob_digit) +
131
sizeof(digit)*size. Previous incarnations of this code used
132
sizeof(PyVarObject) instead of the offsetof, but this risks being
133
incorrect in the presence of padding between the PyVarObject header
135
if (size > (Py_ssize_t)MAX_LONG_DIGITS) {
136
PyErr_SetString(PyExc_OverflowError,
137
"too many digits in integer");
140
result = PyObject_MALLOC(offsetof(PyLongObject, ob_digit) +
146
return (PyLongObject*)PyObject_INIT_VAR(result, &PyLong_Type, size);
150
_PyLong_Copy(PyLongObject *src)
152
PyLongObject *result;
160
sdigit ival = src->ob_digit[0];
161
if (Py_SIZE(src) < 0)
163
CHECK_SMALL_INT(ival);
165
result = _PyLong_New(i);
166
if (result != NULL) {
167
Py_SIZE(result) = Py_SIZE(src);
169
result->ob_digit[i] = src->ob_digit[i];
171
return (PyObject *)result;
174
/* Create a new long int object from a C long int */
177
PyLong_FromLong(long ival)
180
unsigned long abs_ival;
181
unsigned long t; /* unsigned so >> doesn't propagate sign bit */
185
CHECK_SMALL_INT(ival);
188
/* negate: can't write this as abs_ival = -ival since that
189
invokes undefined behaviour when ival is LONG_MIN */
190
abs_ival = 0U-(unsigned long)ival;
194
abs_ival = (unsigned long)ival;
197
/* Fast path for single-digit ints */
198
if (!(abs_ival >> PyLong_SHIFT)) {
202
v->ob_digit[0] = Py_SAFE_DOWNCAST(
203
abs_ival, unsigned long, digit);
210
if (!(abs_ival >> 2*PyLong_SHIFT)) {
214
v->ob_digit[0] = Py_SAFE_DOWNCAST(
215
abs_ival & PyLong_MASK, unsigned long, digit);
216
v->ob_digit[1] = Py_SAFE_DOWNCAST(
217
abs_ival >> PyLong_SHIFT, unsigned long, digit);
223
/* Larger numbers: loop to determine number of digits */
229
v = _PyLong_New(ndigits);
231
digit *p = v->ob_digit;
232
Py_SIZE(v) = ndigits*sign;
235
*p++ = Py_SAFE_DOWNCAST(
236
t & PyLong_MASK, unsigned long, digit);
240
return (PyObject *)v;
243
/* Create a new long int object from a C unsigned long int */
246
PyLong_FromUnsignedLong(unsigned long ival)
252
if (ival < PyLong_BASE)
253
return PyLong_FromLong(ival);
254
/* Count the number of Python digits. */
255
t = (unsigned long)ival;
260
v = _PyLong_New(ndigits);
262
digit *p = v->ob_digit;
263
Py_SIZE(v) = ndigits;
265
*p++ = (digit)(ival & PyLong_MASK);
266
ival >>= PyLong_SHIFT;
269
return (PyObject *)v;
272
/* Create a new long int object from a C double */
275
PyLong_FromDouble(double dval)
279
int i, ndig, expo, neg;
281
if (Py_IS_INFINITY(dval)) {
282
PyErr_SetString(PyExc_OverflowError,
283
"cannot convert float infinity to integer");
286
if (Py_IS_NAN(dval)) {
287
PyErr_SetString(PyExc_ValueError,
288
"cannot convert float NaN to integer");
295
frac = frexp(dval, &expo); /* dval = frac*2**expo; 0.0 <= frac < 1.0 */
297
return PyLong_FromLong(0L);
298
ndig = (expo-1) / PyLong_SHIFT + 1; /* Number of 'digits' in result */
299
v = _PyLong_New(ndig);
302
frac = ldexp(frac, (expo-1) % PyLong_SHIFT + 1);
303
for (i = ndig; --i >= 0; ) {
304
digit bits = (digit)frac;
305
v->ob_digit[i] = bits;
306
frac = frac - (double)bits;
307
frac = ldexp(frac, PyLong_SHIFT);
310
Py_SIZE(v) = -(Py_SIZE(v));
311
return (PyObject *)v;
314
/* Checking for overflow in PyLong_AsLong is a PITA since C doesn't define
315
* anything about what happens when a signed integer operation overflows,
316
* and some compilers think they're doing you a favor by being "clever"
317
* then. The bit pattern for the largest postive signed long is
318
* (unsigned long)LONG_MAX, and for the smallest negative signed long
319
* it is abs(LONG_MIN), which we could write -(unsigned long)LONG_MIN.
320
* However, some other compilers warn about applying unary minus to an
321
* unsigned operand. Hence the weird "0-".
323
#define PY_ABS_LONG_MIN (0-(unsigned long)LONG_MIN)
324
#define PY_ABS_SSIZE_T_MIN (0-(size_t)PY_SSIZE_T_MIN)
326
/* Get a C long int from a long int object.
327
Returns -1 and sets an error condition if overflow occurs. */
330
PyLong_AsLongAndOverflow(PyObject *vv, int *overflow)
332
/* This version by Tim Peters */
333
register PyLongObject *v;
334
unsigned long x, prev;
338
int do_decref = 0; /* if nb_int was called */
342
PyErr_BadInternalCall();
346
if (!PyLong_Check(vv)) {
348
if ((nb = vv->ob_type->tp_as_number) == NULL ||
349
nb->nb_int == NULL) {
350
PyErr_SetString(PyExc_TypeError, "an integer is required");
353
vv = (*nb->nb_int) (vv);
357
if (!PyLong_Check(vv)) {
359
PyErr_SetString(PyExc_TypeError,
360
"nb_int should return int object");
366
v = (PyLongObject *)vv;
371
res = -(sdigit)v->ob_digit[0];
377
res = v->ob_digit[0];
388
x = (x << PyLong_SHIFT) + v->ob_digit[i];
389
if ((x >> PyLong_SHIFT) != prev) {
390
*overflow = Py_SIZE(v) > 0 ? 1 : -1;
394
/* Haven't lost any bits, but casting to long requires extra care
395
* (see comment above).
397
if (x <= (unsigned long)LONG_MAX) {
398
res = (long)x * sign;
400
else if (sign < 0 && x == PY_ABS_LONG_MIN) {
404
*overflow = Py_SIZE(v) > 0 ? 1 : -1;
405
/* res is already set to -1 */
416
PyLong_AsLong(PyObject *obj)
419
long result = PyLong_AsLongAndOverflow(obj, &overflow);
421
/* XXX: could be cute and give a different
422
message for overflow == -1 */
423
PyErr_SetString(PyExc_OverflowError,
424
"Python int too large to convert to C long");
429
/* Get a Py_ssize_t from a long int object.
430
Returns -1 and sets an error condition if overflow occurs. */
433
PyLong_AsSsize_t(PyObject *vv) {
434
register PyLongObject *v;
439
if (vv == NULL || !PyLong_Check(vv)) {
440
PyErr_BadInternalCall();
443
v = (PyLongObject *)vv;
446
case -1: return -(sdigit)v->ob_digit[0];
448
case 1: return v->ob_digit[0];
458
x = (x << PyLong_SHIFT) + v->ob_digit[i];
459
if ((x >> PyLong_SHIFT) != prev)
462
/* Haven't lost any bits, but casting to a signed type requires
463
* extra care (see comment above).
465
if (x <= (size_t)PY_SSIZE_T_MAX) {
466
return (Py_ssize_t)x * sign;
468
else if (sign < 0 && x == PY_ABS_SSIZE_T_MIN) {
469
return PY_SSIZE_T_MIN;
474
PyErr_SetString(PyExc_OverflowError,
475
"Python int too large to convert to C ssize_t");
479
/* Get a C unsigned long int from a long int object.
480
Returns -1 and sets an error condition if overflow occurs. */
483
PyLong_AsUnsignedLong(PyObject *vv)
485
register PyLongObject *v;
486
unsigned long x, prev;
489
if (vv == NULL || !PyLong_Check(vv)) {
490
PyErr_BadInternalCall();
491
return (unsigned long) -1;
493
v = (PyLongObject *)vv;
497
PyErr_SetString(PyExc_OverflowError,
498
"can't convert negative value to unsigned int");
499
return (unsigned long) -1;
503
case 1: return v->ob_digit[0];
507
x = (x << PyLong_SHIFT) + v->ob_digit[i];
508
if ((x >> PyLong_SHIFT) != prev) {
509
PyErr_SetString(PyExc_OverflowError,
510
"python int too large to convert to C unsigned long");
511
return (unsigned long) -1;
517
/* Get a C unsigned long int from a long int object.
518
Returns -1 and sets an error condition if overflow occurs. */
521
PyLong_AsSize_t(PyObject *vv)
523
register PyLongObject *v;
527
if (vv == NULL || !PyLong_Check(vv)) {
528
PyErr_BadInternalCall();
529
return (unsigned long) -1;
531
v = (PyLongObject *)vv;
535
PyErr_SetString(PyExc_OverflowError,
536
"can't convert negative value to size_t");
541
case 1: return v->ob_digit[0];
545
x = (x << PyLong_SHIFT) + v->ob_digit[i];
546
if ((x >> PyLong_SHIFT) != prev) {
547
PyErr_SetString(PyExc_OverflowError,
548
"Python int too large to convert to C size_t");
549
return (unsigned long) -1;
555
/* Get a C unsigned long int from a long int object, ignoring the high bits.
556
Returns -1 and sets an error condition if an error occurs. */
559
_PyLong_AsUnsignedLongMask(PyObject *vv)
561
register PyLongObject *v;
566
if (vv == NULL || !PyLong_Check(vv)) {
567
PyErr_BadInternalCall();
568
return (unsigned long) -1;
570
v = (PyLongObject *)vv;
574
case 1: return v->ob_digit[0];
583
x = (x << PyLong_SHIFT) + v->ob_digit[i];
589
PyLong_AsUnsignedLongMask(register PyObject *op)
595
if (op && PyLong_Check(op))
596
return _PyLong_AsUnsignedLongMask(op);
598
if (op == NULL || (nb = op->ob_type->tp_as_number) == NULL ||
599
nb->nb_int == NULL) {
600
PyErr_SetString(PyExc_TypeError, "an integer is required");
601
return (unsigned long)-1;
604
lo = (PyLongObject*) (*nb->nb_int) (op);
606
return (unsigned long)-1;
607
if (PyLong_Check(lo)) {
608
val = _PyLong_AsUnsignedLongMask((PyObject *)lo);
610
if (PyErr_Occurred())
611
return (unsigned long)-1;
617
PyErr_SetString(PyExc_TypeError,
618
"nb_int should return int object");
619
return (unsigned long)-1;
624
_PyLong_Sign(PyObject *vv)
626
PyLongObject *v = (PyLongObject *)vv;
629
assert(PyLong_Check(v));
631
return Py_SIZE(v) == 0 ? 0 : (Py_SIZE(v) < 0 ? -1 : 1);
635
_PyLong_NumBits(PyObject *vv)
637
PyLongObject *v = (PyLongObject *)vv;
642
assert(PyLong_Check(v));
643
ndigits = ABS(Py_SIZE(v));
644
assert(ndigits == 0 || v->ob_digit[ndigits - 1] != 0);
646
digit msd = v->ob_digit[ndigits - 1];
648
result = (ndigits - 1) * PyLong_SHIFT;
649
if (result / PyLong_SHIFT != (size_t)(ndigits - 1))
661
PyErr_SetString(PyExc_OverflowError, "int has too many bits "
662
"to express in a platform size_t");
667
_PyLong_FromByteArray(const unsigned char* bytes, size_t n,
668
int little_endian, int is_signed)
670
const unsigned char* pstartbyte;/* LSB of bytes */
671
int incr; /* direction to move pstartbyte */
672
const unsigned char* pendbyte; /* MSB of bytes */
673
size_t numsignificantbytes; /* number of bytes that matter */
674
Py_ssize_t ndigits; /* number of Python long digits */
675
PyLongObject* v; /* result */
676
Py_ssize_t idigit = 0; /* next free index in v->ob_digit */
679
return PyLong_FromLong(0L);
683
pendbyte = bytes + n - 1;
687
pstartbyte = bytes + n - 1;
693
is_signed = *pendbyte >= 0x80;
695
/* Compute numsignificantbytes. This consists of finding the most
696
significant byte. Leading 0 bytes are insignficant if the number
697
is positive, and leading 0xff bytes if negative. */
700
const unsigned char* p = pendbyte;
701
const int pincr = -incr; /* search MSB to LSB */
702
const unsigned char insignficant = is_signed ? 0xff : 0x00;
704
for (i = 0; i < n; ++i, p += pincr) {
705
if (*p != insignficant)
708
numsignificantbytes = n - i;
709
/* 2's-comp is a bit tricky here, e.g. 0xff00 == -0x0100, so
710
actually has 2 significant bytes. OTOH, 0xff0001 ==
711
-0x00ffff, so we wouldn't *need* to bump it there; but we
712
do for 0xffff = -0x0001. To be safe without bothering to
713
check every case, bump it regardless. */
714
if (is_signed && numsignificantbytes < n)
715
++numsignificantbytes;
718
/* How many Python long digits do we need? We have
719
8*numsignificantbytes bits, and each Python long digit has
720
PyLong_SHIFT bits, so it's the ceiling of the quotient. */
721
/* catch overflow before it happens */
722
if (numsignificantbytes > (PY_SSIZE_T_MAX - PyLong_SHIFT) / 8) {
723
PyErr_SetString(PyExc_OverflowError,
724
"byte array too long to convert to int");
727
ndigits = (numsignificantbytes * 8 + PyLong_SHIFT - 1) / PyLong_SHIFT;
728
v = _PyLong_New(ndigits);
732
/* Copy the bits over. The tricky parts are computing 2's-comp on
733
the fly for signed numbers, and dealing with the mismatch between
734
8-bit bytes and (probably) 15-bit Python digits.*/
737
twodigits carry = 1; /* for 2's-comp calculation */
738
twodigits accum = 0; /* sliding register */
739
unsigned int accumbits = 0; /* number of bits in accum */
740
const unsigned char* p = pstartbyte;
742
for (i = 0; i < numsignificantbytes; ++i, p += incr) {
743
twodigits thisbyte = *p;
744
/* Compute correction for 2's comp, if needed. */
746
thisbyte = (0xff ^ thisbyte) + carry;
747
carry = thisbyte >> 8;
750
/* Because we're going LSB to MSB, thisbyte is
751
more significant than what's already in accum,
752
so needs to be prepended to accum. */
753
accum |= (twodigits)thisbyte << accumbits;
755
if (accumbits >= PyLong_SHIFT) {
756
/* There's enough to fill a Python digit. */
757
assert(idigit < ndigits);
758
v->ob_digit[idigit] = (digit)(accum &
761
accum >>= PyLong_SHIFT;
762
accumbits -= PyLong_SHIFT;
763
assert(accumbits < PyLong_SHIFT);
766
assert(accumbits < PyLong_SHIFT);
768
assert(idigit < ndigits);
769
v->ob_digit[idigit] = (digit)accum;
774
Py_SIZE(v) = is_signed ? -idigit : idigit;
775
return (PyObject *)long_normalize(v);
779
_PyLong_AsByteArray(PyLongObject* v,
780
unsigned char* bytes, size_t n,
781
int little_endian, int is_signed)
783
Py_ssize_t i; /* index into v->ob_digit */
784
Py_ssize_t ndigits; /* |v->ob_size| */
785
twodigits accum; /* sliding register */
786
unsigned int accumbits; /* # bits in accum */
787
int do_twos_comp; /* store 2's-comp? is_signed and v < 0 */
788
digit carry; /* for computing 2's-comp */
789
size_t j; /* # bytes filled */
790
unsigned char* p; /* pointer to next byte in bytes */
791
int pincr; /* direction to move p */
793
assert(v != NULL && PyLong_Check(v));
795
if (Py_SIZE(v) < 0) {
796
ndigits = -(Py_SIZE(v));
798
PyErr_SetString(PyExc_OverflowError,
799
"can't convert negative int to unsigned");
805
ndigits = Py_SIZE(v);
818
/* Copy over all the Python digits.
819
It's crucial that every Python digit except for the MSD contribute
820
exactly PyLong_SHIFT bits to the total, so first assert that the long is
822
assert(ndigits == 0 || v->ob_digit[ndigits - 1] != 0);
826
carry = do_twos_comp ? 1 : 0;
827
for (i = 0; i < ndigits; ++i) {
828
digit thisdigit = v->ob_digit[i];
830
thisdigit = (thisdigit ^ PyLong_MASK) + carry;
831
carry = thisdigit >> PyLong_SHIFT;
832
thisdigit &= PyLong_MASK;
834
/* Because we're going LSB to MSB, thisdigit is more
835
significant than what's already in accum, so needs to be
836
prepended to accum. */
837
accum |= (twodigits)thisdigit << accumbits;
839
/* The most-significant digit may be (probably is) at least
841
if (i == ndigits - 1) {
842
/* Count # of sign bits -- they needn't be stored,
843
* although for signed conversion we need later to
844
* make sure at least one sign bit gets stored. */
845
digit s = do_twos_comp ? thisdigit ^ PyLong_MASK :
853
accumbits += PyLong_SHIFT;
855
/* Store as many bytes as possible. */
856
while (accumbits >= 8) {
860
*p = (unsigned char)(accum & 0xff);
867
/* Store the straggler (if any). */
868
assert(accumbits < 8);
869
assert(carry == 0); /* else do_twos_comp and *every* digit was 0 */
875
/* Fill leading bits of the byte with sign bits
876
(appropriately pretending that the long had an
877
infinite supply of sign bits). */
878
accum |= (~(twodigits)0) << accumbits;
880
*p = (unsigned char)(accum & 0xff);
883
else if (j == n && n > 0 && is_signed) {
884
/* The main loop filled the byte array exactly, so the code
885
just above didn't get to ensure there's a sign bit, and the
886
loop below wouldn't add one either. Make sure a sign bit
888
unsigned char msb = *(p - pincr);
889
int sign_bit_set = msb >= 0x80;
890
assert(accumbits == 0);
891
if (sign_bit_set == do_twos_comp)
897
/* Fill remaining bytes with copies of the sign bit. */
899
unsigned char signbyte = do_twos_comp ? 0xffU : 0U;
900
for ( ; j < n; ++j, p += pincr)
907
PyErr_SetString(PyExc_OverflowError, "int too big to convert");
913
_PyLong_AsScaledDouble(PyObject *vv, int *exponent)
915
/* NBITS_WANTED should be > the number of bits in a double's precision,
916
but small enough so that 2**NBITS_WANTED is within the normal double
917
range. nbitsneeded is set to 1 less than that because the most-significant
918
Python digit contains at least 1 significant bit, but we don't want to
919
bother counting them (catering to the worst case cheaply).
921
57 is one more than VAX-D double precision; I (Tim) don't know of a double
922
format with more precision than that; it's 1 larger so that we add in at
923
least one round bit to stand in for the ignored least-significant bits.
925
#define NBITS_WANTED 57
928
const double multiplier = (double)(1L << PyLong_SHIFT);
933
if (vv == NULL || !PyLong_Check(vv)) {
934
PyErr_BadInternalCall();
937
v = (PyLongObject *)vv;
949
x = (double)v->ob_digit[i];
950
nbitsneeded = NBITS_WANTED - 1;
951
/* Invariant: i Python digits remain unaccounted for. */
952
while (i > 0 && nbitsneeded > 0) {
954
x = x * multiplier + (double)v->ob_digit[i];
955
nbitsneeded -= PyLong_SHIFT;
957
/* There are i digits we didn't shift in. Pretending they're all
958
zeroes, the true value is x * 2**(i*PyLong_SHIFT). */
965
/* Get a C double from a long int object. */
968
PyLong_AsDouble(PyObject *vv)
973
if (vv == NULL || !PyLong_Check(vv)) {
974
PyErr_BadInternalCall();
977
x = _PyLong_AsScaledDouble(vv, &e);
978
if (x == -1.0 && PyErr_Occurred())
980
/* 'e' initialized to -1 to silence gcc-4.0.x, but it should be
981
set correctly after a successful _PyLong_AsScaledDouble() call */
983
if (e > INT_MAX / PyLong_SHIFT)
986
x = ldexp(x, e * PyLong_SHIFT);
987
if (Py_OVERFLOWED(x))
992
PyErr_SetString(PyExc_OverflowError,
993
"Python int too large to convert to C double");
997
/* Create a new long (or int) object from a C pointer */
1000
PyLong_FromVoidPtr(void *p)
1002
#ifndef HAVE_LONG_LONG
1003
# error "PyLong_FromVoidPtr: sizeof(void*) > sizeof(long), but no long long"
1005
#if SIZEOF_LONG_LONG < SIZEOF_VOID_P
1006
# error "PyLong_FromVoidPtr: sizeof(PY_LONG_LONG) < sizeof(void*)"
1008
/* special-case null pointer */
1010
return PyLong_FromLong(0);
1011
return PyLong_FromUnsignedLongLong((unsigned PY_LONG_LONG)(Py_uintptr_t)p);
1015
/* Get a C pointer from a long object (or an int object in some cases) */
1018
PyLong_AsVoidPtr(PyObject *vv)
1020
/* This function will allow int or long objects. If vv is neither,
1021
then the PyLong_AsLong*() functions will raise the exception:
1022
PyExc_SystemError, "bad argument to internal function"
1024
#if SIZEOF_VOID_P <= SIZEOF_LONG
1027
if (PyLong_Check(vv) && _PyLong_Sign(vv) < 0)
1028
x = PyLong_AsLong(vv);
1030
x = PyLong_AsUnsignedLong(vv);
1033
#ifndef HAVE_LONG_LONG
1034
# error "PyLong_AsVoidPtr: sizeof(void*) > sizeof(long), but no long long"
1036
#if SIZEOF_LONG_LONG < SIZEOF_VOID_P
1037
# error "PyLong_AsVoidPtr: sizeof(PY_LONG_LONG) < sizeof(void*)"
1041
if (PyLong_Check(vv) && _PyLong_Sign(vv) < 0)
1042
x = PyLong_AsLongLong(vv);
1044
x = PyLong_AsUnsignedLongLong(vv);
1046
#endif /* SIZEOF_VOID_P <= SIZEOF_LONG */
1048
if (x == -1 && PyErr_Occurred())
1053
#ifdef HAVE_LONG_LONG
1055
/* Initial PY_LONG_LONG support by Chris Herborth (chrish@qnx.com), later
1056
* rewritten to use the newer PyLong_{As,From}ByteArray API.
1059
#define IS_LITTLE_ENDIAN (int)*(unsigned char*)&one
1061
/* Create a new long int object from a C PY_LONG_LONG int. */
1064
PyLong_FromLongLong(PY_LONG_LONG ival)
1067
unsigned PY_LONG_LONG abs_ival;
1068
unsigned PY_LONG_LONG t; /* unsigned so >> doesn't propagate sign bit */
1072
CHECK_SMALL_INT(ival);
1074
/* avoid signed overflow on negation; see comments
1075
in PyLong_FromLong above. */
1076
abs_ival = (unsigned PY_LONG_LONG)(-1-ival) + 1;
1080
abs_ival = (unsigned PY_LONG_LONG)ival;
1083
/* Count the number of Python digits.
1084
We used to pick 5 ("big enough for anything"), but that's a
1085
waste of time and space given that 5*15 = 75 bits are rarely
1092
v = _PyLong_New(ndigits);
1094
digit *p = v->ob_digit;
1095
Py_SIZE(v) = negative ? -ndigits : ndigits;
1098
*p++ = (digit)(t & PyLong_MASK);
1102
return (PyObject *)v;
1105
/* Create a new long int object from a C unsigned PY_LONG_LONG int. */
1108
PyLong_FromUnsignedLongLong(unsigned PY_LONG_LONG ival)
1111
unsigned PY_LONG_LONG t;
1114
if (ival < PyLong_BASE)
1115
return PyLong_FromLong((long)ival);
1116
/* Count the number of Python digits. */
1117
t = (unsigned PY_LONG_LONG)ival;
1122
v = _PyLong_New(ndigits);
1124
digit *p = v->ob_digit;
1125
Py_SIZE(v) = ndigits;
1127
*p++ = (digit)(ival & PyLong_MASK);
1128
ival >>= PyLong_SHIFT;
1131
return (PyObject *)v;
1134
/* Create a new long int object from a C Py_ssize_t. */
1137
PyLong_FromSsize_t(Py_ssize_t ival)
1141
size_t t; /* unsigned so >> doesn't propagate sign bit */
1145
CHECK_SMALL_INT(ival);
1147
/* avoid signed overflow when ival = SIZE_T_MIN */
1148
abs_ival = (size_t)(-1-ival)+1;
1152
abs_ival = (size_t)ival;
1155
/* Count the number of Python digits. */
1161
v = _PyLong_New(ndigits);
1163
digit *p = v->ob_digit;
1164
Py_SIZE(v) = negative ? -ndigits : ndigits;
1167
*p++ = (digit)(t & PyLong_MASK);
1171
return (PyObject *)v;
1174
/* Create a new long int object from a C size_t. */
1177
PyLong_FromSize_t(size_t ival)
1183
if (ival < PyLong_BASE)
1184
return PyLong_FromLong(ival);
1185
/* Count the number of Python digits. */
1191
v = _PyLong_New(ndigits);
1193
digit *p = v->ob_digit;
1194
Py_SIZE(v) = ndigits;
1196
*p++ = (digit)(ival & PyLong_MASK);
1197
ival >>= PyLong_SHIFT;
1200
return (PyObject *)v;
1203
/* Get a C PY_LONG_LONG int from a long int object.
1204
Return -1 and set an error if overflow occurs. */
1207
PyLong_AsLongLong(PyObject *vv)
1215
PyErr_BadInternalCall();
1218
if (!PyLong_Check(vv)) {
1219
PyNumberMethods *nb;
1221
if ((nb = vv->ob_type->tp_as_number) == NULL ||
1222
nb->nb_int == NULL) {
1223
PyErr_SetString(PyExc_TypeError, "an integer is required");
1226
io = (*nb->nb_int) (vv);
1229
if (PyLong_Check(io)) {
1230
bytes = PyLong_AsLongLong(io);
1235
PyErr_SetString(PyExc_TypeError, "integer conversion failed");
1239
v = (PyLongObject*)vv;
1240
switch(Py_SIZE(v)) {
1241
case -1: return -(sdigit)v->ob_digit[0];
1243
case 1: return v->ob_digit[0];
1245
res = _PyLong_AsByteArray(
1246
(PyLongObject *)vv, (unsigned char *)&bytes,
1247
SIZEOF_LONG_LONG, IS_LITTLE_ENDIAN, 1);
1249
/* Plan 9 can't handle PY_LONG_LONG in ? : expressions */
1251
return (PY_LONG_LONG)-1;
1256
/* Get a C unsigned PY_LONG_LONG int from a long int object.
1257
Return -1 and set an error if overflow occurs. */
1259
unsigned PY_LONG_LONG
1260
PyLong_AsUnsignedLongLong(PyObject *vv)
1263
unsigned PY_LONG_LONG bytes;
1267
if (vv == NULL || !PyLong_Check(vv)) {
1268
PyErr_BadInternalCall();
1269
return (unsigned PY_LONG_LONG)-1;
1272
v = (PyLongObject*)vv;
1273
switch(Py_SIZE(v)) {
1275
case 1: return v->ob_digit[0];
1278
res = _PyLong_AsByteArray(
1279
(PyLongObject *)vv, (unsigned char *)&bytes,
1280
SIZEOF_LONG_LONG, IS_LITTLE_ENDIAN, 0);
1282
/* Plan 9 can't handle PY_LONG_LONG in ? : expressions */
1284
return (unsigned PY_LONG_LONG)res;
1289
/* Get a C unsigned long int from a long int object, ignoring the high bits.
1290
Returns -1 and sets an error condition if an error occurs. */
1292
static unsigned PY_LONG_LONG
1293
_PyLong_AsUnsignedLongLongMask(PyObject *vv)
1295
register PyLongObject *v;
1296
unsigned PY_LONG_LONG x;
1300
if (vv == NULL || !PyLong_Check(vv)) {
1301
PyErr_BadInternalCall();
1302
return (unsigned long) -1;
1304
v = (PyLongObject *)vv;
1305
switch(Py_SIZE(v)) {
1307
case 1: return v->ob_digit[0];
1317
x = (x << PyLong_SHIFT) + v->ob_digit[i];
1322
unsigned PY_LONG_LONG
1323
PyLong_AsUnsignedLongLongMask(register PyObject *op)
1325
PyNumberMethods *nb;
1327
unsigned PY_LONG_LONG val;
1329
if (op && PyLong_Check(op))
1330
return _PyLong_AsUnsignedLongLongMask(op);
1332
if (op == NULL || (nb = op->ob_type->tp_as_number) == NULL ||
1333
nb->nb_int == NULL) {
1334
PyErr_SetString(PyExc_TypeError, "an integer is required");
1335
return (unsigned PY_LONG_LONG)-1;
1338
lo = (PyLongObject*) (*nb->nb_int) (op);
1340
return (unsigned PY_LONG_LONG)-1;
1341
if (PyLong_Check(lo)) {
1342
val = _PyLong_AsUnsignedLongLongMask((PyObject *)lo);
1344
if (PyErr_Occurred())
1345
return (unsigned PY_LONG_LONG)-1;
1351
PyErr_SetString(PyExc_TypeError,
1352
"nb_int should return int object");
1353
return (unsigned PY_LONG_LONG)-1;
1356
#undef IS_LITTLE_ENDIAN
1358
#endif /* HAVE_LONG_LONG */
1360
#define CHECK_BINOP(v,w) \
1361
if (!PyLong_Check(v) || !PyLong_Check(w)) { \
1362
Py_INCREF(Py_NotImplemented); \
1363
return Py_NotImplemented; \
1366
/* x[0:m] and y[0:n] are digit vectors, LSD first, m >= n required. x[0:n]
1367
* is modified in place, by adding y to it. Carries are propagated as far as
1368
* x[m-1], and the remaining carry (0 or 1) is returned.
1371
v_iadd(digit *x, Py_ssize_t m, digit *y, Py_ssize_t n)
1377
for (i = 0; i < n; ++i) {
1378
carry += x[i] + y[i];
1379
x[i] = carry & PyLong_MASK;
1380
carry >>= PyLong_SHIFT;
1381
assert((carry & 1) == carry);
1383
for (; carry && i < m; ++i) {
1385
x[i] = carry & PyLong_MASK;
1386
carry >>= PyLong_SHIFT;
1387
assert((carry & 1) == carry);
1392
/* x[0:m] and y[0:n] are digit vectors, LSD first, m >= n required. x[0:n]
1393
* is modified in place, by subtracting y from it. Borrows are propagated as
1394
* far as x[m-1], and the remaining borrow (0 or 1) is returned.
1397
v_isub(digit *x, Py_ssize_t m, digit *y, Py_ssize_t n)
1403
for (i = 0; i < n; ++i) {
1404
borrow = x[i] - y[i] - borrow;
1405
x[i] = borrow & PyLong_MASK;
1406
borrow >>= PyLong_SHIFT;
1407
borrow &= 1; /* keep only 1 sign bit */
1409
for (; borrow && i < m; ++i) {
1410
borrow = x[i] - borrow;
1411
x[i] = borrow & PyLong_MASK;
1412
borrow >>= PyLong_SHIFT;
1418
/* Multiply by a single digit, ignoring the sign. */
1420
static PyLongObject *
1421
mul1(PyLongObject *a, digit n)
1423
Py_ssize_t size_a = ABS(Py_SIZE(a));
1424
PyLongObject *z = _PyLong_New(size_a+1);
1425
twodigits carry = 0;
1430
for (i = 0; i < size_a; ++i) {
1431
carry += (twodigits)a->ob_digit[i] * n;
1432
z->ob_digit[i] = (digit) (carry & PyLong_MASK);
1433
carry >>= PyLong_SHIFT;
1435
z->ob_digit[i] = (digit) carry;
1436
return long_normalize(z);
1439
/* Divide long pin, w/ size digits, by non-zero digit n, storing quotient
1440
in pout, and returning the remainder. pin and pout point at the LSD.
1441
It's OK for pin == pout on entry, which saves oodles of mallocs/frees in
1442
_PyLong_Format, but that should be done with great care since longs are
1446
inplace_divrem1(digit *pout, digit *pin, Py_ssize_t size, digit n)
1450
assert(n > 0 && n <= PyLong_MASK);
1453
while (--size >= 0) {
1455
rem = (rem << PyLong_SHIFT) + *--pin;
1456
*--pout = hi = (digit)(rem / n);
1457
rem -= (twodigits)hi * n;
1462
/* Divide a long integer by a digit, returning both the quotient
1463
(as function result) and the remainder (through *prem).
1464
The sign of a is ignored; n should not be zero. */
1466
static PyLongObject *
1467
divrem1(PyLongObject *a, digit n, digit *prem)
1469
const Py_ssize_t size = ABS(Py_SIZE(a));
1472
assert(n > 0 && n <= PyLong_MASK);
1473
z = _PyLong_New(size);
1476
*prem = inplace_divrem1(z->ob_digit, a->ob_digit, size, n);
1477
return long_normalize(z);
1480
/* Convert a long int object to a string, using a given conversion base.
1481
Return a string object.
1482
If base is 2, 8 or 16, add the proper prefix '0b', '0o' or '0x'. */
1485
_PyLong_Format(PyObject *aa, int base)
1487
register PyLongObject *a = (PyLongObject *)aa;
1489
Py_ssize_t i, j, sz;
1495
if (a == NULL || !PyLong_Check(a)) {
1496
PyErr_BadInternalCall();
1499
assert(base >= 2 && base <= 36);
1500
size_a = ABS(Py_SIZE(a));
1502
/* Compute a rough upper bound for the length of the string */
1510
j = size_a*PyLong_SHIFT + bits-1;
1512
if (j / PyLong_SHIFT < size_a || sz < i) {
1513
PyErr_SetString(PyExc_OverflowError,
1514
"int is too large to format");
1517
str = PyUnicode_FromUnicode(NULL, sz);
1520
p = PyUnicode_AS_UNICODE(str) + sz;
1525
if (Py_SIZE(a) == 0) {
1528
else if ((base & (base - 1)) == 0) {
1529
/* JRH: special case for power-of-2 bases */
1530
twodigits accum = 0;
1531
int accumbits = 0; /* # of bits in accum */
1532
int basebits = 1; /* # of bits in base-1 */
1534
while ((i >>= 1) > 1)
1537
for (i = 0; i < size_a; ++i) {
1538
accum |= (twodigits)a->ob_digit[i] << accumbits;
1539
accumbits += PyLong_SHIFT;
1540
assert(accumbits >= basebits);
1542
char cdigit = (char)(accum & (base - 1));
1543
cdigit += (cdigit < 10) ? '0' : 'a'-10;
1544
assert(p > PyUnicode_AS_UNICODE(str));
1546
accumbits -= basebits;
1548
} while (i < size_a-1 ? accumbits >= basebits :
1553
/* Not 0, and base not a power of 2. Divide repeatedly by
1554
base, but for speed use the highest power of base that
1556
Py_ssize_t size = size_a;
1557
digit *pin = a->ob_digit;
1558
PyLongObject *scratch;
1559
/* powbasw <- largest power of base that fits in a digit. */
1560
digit powbase = base; /* powbase == base ** power */
1563
twodigits newpow = powbase * (twodigits)base;
1564
if (newpow >> PyLong_SHIFT) /* doesn't fit in a digit */
1566
powbase = (digit)newpow;
1570
/* Get a scratch area for repeated division. */
1571
scratch = _PyLong_New(size);
1572
if (scratch == NULL) {
1577
/* Repeatedly divide by powbase. */
1579
int ntostore = power;
1580
digit rem = inplace_divrem1(scratch->ob_digit,
1581
pin, size, powbase);
1582
pin = scratch->ob_digit; /* no need to use a again */
1583
if (pin[size - 1] == 0)
1591
/* Break rem into digits. */
1592
assert(ntostore > 0);
1594
digit nextrem = (digit)(rem / base);
1595
char c = (char)(rem - nextrem * base);
1596
assert(p > PyUnicode_AS_UNICODE(str));
1597
c += (c < 10) ? '0' : 'a'-10;
1601
/* Termination is a bit delicate: must not
1602
store leading zeroes, so must get out if
1603
remaining quotient and rem are both 0. */
1604
} while (ntostore && (size || rem));
1605
} while (size != 0);
1613
else if (base == 8) {
1617
else if (base == 2) {
1621
else if (base != 10) {
1623
*--p = '0' + base%10;
1625
*--p = '0' + base/10;
1629
if (p != PyUnicode_AS_UNICODE(str)) {
1630
Py_UNICODE *q = PyUnicode_AS_UNICODE(str);
1633
} while ((*q++ = *p++) != '\0');
1635
if (PyUnicode_Resize(&str, (Py_ssize_t) (q - PyUnicode_AS_UNICODE(str)))) {
1640
return (PyObject *)str;
1643
/* Table of digit values for 8-bit string -> integer conversion.
1644
* '0' maps to 0, ..., '9' maps to 9.
1645
* 'a' and 'A' map to 10, ..., 'z' and 'Z' map to 35.
1646
* All other indices map to 37.
1647
* Note that when converting a base B string, a char c is a legitimate
1648
* base B digit iff _PyLong_DigitValue[Py_CHARPyLong_MASK(c)] < B.
1650
unsigned char _PyLong_DigitValue[256] = {
1651
37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37,
1652
37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37,
1653
37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37,
1654
0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 37, 37, 37, 37, 37, 37,
1655
37, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24,
1656
25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 37, 37, 37, 37, 37,
1657
37, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24,
1658
25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 37, 37, 37, 37, 37,
1659
37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37,
1660
37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37,
1661
37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37,
1662
37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37,
1663
37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37,
1664
37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37,
1665
37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37,
1666
37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37,
1669
/* *str points to the first digit in a string of base `base` digits. base
1670
* is a power of 2 (2, 4, 8, 16, or 32). *str is set to point to the first
1671
* non-digit (which may be *str!). A normalized long is returned.
1672
* The point to this routine is that it takes time linear in the number of
1673
* string characters.
1675
static PyLongObject *
1676
long_from_binary_base(char **str, int base)
1687
assert(base >= 2 && base <= 32 && (base & (base - 1)) == 0);
1689
for (bits_per_char = -1; n; ++bits_per_char)
1691
/* n <- total # of bits needed, while setting p to end-of-string */
1693
while (_PyLong_DigitValue[Py_CHARMASK(*p)] < base)
1696
/* n <- # of Python digits needed, = ceiling(n/PyLong_SHIFT). */
1697
n = (p - start) * bits_per_char + PyLong_SHIFT - 1;
1698
if (n / bits_per_char < p - start) {
1699
PyErr_SetString(PyExc_ValueError,
1700
"int string too large to convert");
1703
n = n / PyLong_SHIFT;
1707
/* Read string from right, and fill in long from left; i.e.,
1708
* from least to most significant in both.
1712
pdigit = z->ob_digit;
1713
while (--p >= start) {
1714
int k = (int)_PyLong_DigitValue[Py_CHARMASK(*p)];
1715
assert(k >= 0 && k < base);
1716
accum |= (twodigits)k << bits_in_accum;
1717
bits_in_accum += bits_per_char;
1718
if (bits_in_accum >= PyLong_SHIFT) {
1719
*pdigit++ = (digit)(accum & PyLong_MASK);
1720
assert(pdigit - z->ob_digit <= n);
1721
accum >>= PyLong_SHIFT;
1722
bits_in_accum -= PyLong_SHIFT;
1723
assert(bits_in_accum < PyLong_SHIFT);
1726
if (bits_in_accum) {
1727
assert(bits_in_accum <= PyLong_SHIFT);
1728
*pdigit++ = (digit)accum;
1729
assert(pdigit - z->ob_digit <= n);
1731
while (pdigit - z->ob_digit < n)
1733
return long_normalize(z);
1737
PyLong_FromString(char *str, char **pend, int base)
1739
int sign = 1, error_if_nonzero = 0;
1740
char *start, *orig_str = str;
1741
PyLongObject *z = NULL;
1745
if ((base != 0 && base < 2) || base > 36) {
1746
PyErr_SetString(PyExc_ValueError,
1747
"int() arg 2 must be >= 2 and <= 36");
1750
while (*str != '\0' && isspace(Py_CHARMASK(*str)))
1754
else if (*str == '-') {
1761
else if (str[1] == 'x' || str[1] == 'X')
1763
else if (str[1] == 'o' || str[1] == 'O')
1765
else if (str[1] == 'b' || str[1] == 'B')
1768
/* "old" (C-style) octal literal, now invalid.
1769
it might still be zero though */
1770
error_if_nonzero = 1;
1774
if (str[0] == '0' &&
1775
((base == 16 && (str[1] == 'x' || str[1] == 'X')) ||
1776
(base == 8 && (str[1] == 'o' || str[1] == 'O')) ||
1777
(base == 2 && (str[1] == 'b' || str[1] == 'B'))))
1781
if ((base & (base - 1)) == 0)
1782
z = long_from_binary_base(&str, base);
1785
Binary bases can be converted in time linear in the number of digits, because
1786
Python's representation base is binary. Other bases (including decimal!) use
1787
the simple quadratic-time algorithm below, complicated by some speed tricks.
1789
First some math: the largest integer that can be expressed in N base-B digits
1790
is B**N-1. Consequently, if we have an N-digit input in base B, the worst-
1791
case number of Python digits needed to hold it is the smallest integer n s.t.
1793
BASE**n-1 >= B**N-1 [or, adding 1 to both sides]
1794
BASE**n >= B**N [taking logs to base BASE]
1795
n >= log(B**N)/log(BASE) = N * log(B)/log(BASE)
1797
The static array log_base_BASE[base] == log(base)/log(BASE) so we can compute
1798
this quickly. A Python long with that much space is reserved near the start,
1799
and the result is computed into it.
1801
The input string is actually treated as being in base base**i (i.e., i digits
1802
are processed at a time), where two more static arrays hold:
1804
convwidth_base[base] = the largest integer i such that base**i <= BASE
1805
convmultmax_base[base] = base ** convwidth_base[base]
1807
The first of these is the largest i such that i consecutive input digits
1808
must fit in a single Python digit. The second is effectively the input
1809
base we're really using.
1811
Viewing the input as a sequence <c0, c1, ..., c_n-1> of digits in base
1812
convmultmax_base[base], the result is "simply"
1814
(((c0*B + c1)*B + c2)*B + c3)*B + ... ))) + c_n-1
1816
where B = convmultmax_base[base].
1818
Error analysis: as above, the number of Python digits `n` needed is worst-
1821
n >= N * log(B)/log(BASE)
1823
where `N` is the number of input digits in base `B`. This is computed via
1825
size_z = (Py_ssize_t)((scan - str) * log_base_BASE[base]) + 1;
1827
below. Two numeric concerns are how much space this can waste, and whether
1828
the computed result can be too small. To be concrete, assume BASE = 2**15,
1829
which is the default (and it's unlikely anyone changes that).
1831
Waste isn't a problem: provided the first input digit isn't 0, the difference
1832
between the worst-case input with N digits and the smallest input with N
1833
digits is about a factor of B, but B is small compared to BASE so at most
1834
one allocated Python digit can remain unused on that count. If
1835
N*log(B)/log(BASE) is mathematically an exact integer, then truncating that
1836
and adding 1 returns a result 1 larger than necessary. However, that can't
1837
happen: whenever B is a power of 2, long_from_binary_base() is called
1838
instead, and it's impossible for B**i to be an integer power of 2**15 when
1839
B is not a power of 2 (i.e., it's impossible for N*log(B)/log(BASE) to be
1840
an exact integer when B is not a power of 2, since B**i has a prime factor
1841
other than 2 in that case, but (2**15)**j's only prime factor is 2).
1843
The computed result can be too small if the true value of N*log(B)/log(BASE)
1844
is a little bit larger than an exact integer, but due to roundoff errors (in
1845
computing log(B), log(BASE), their quotient, and/or multiplying that by N)
1846
yields a numeric result a little less than that integer. Unfortunately, "how
1847
close can a transcendental function get to an integer over some range?"
1848
questions are generally theoretically intractable. Computer analysis via
1849
continued fractions is practical: expand log(B)/log(BASE) via continued
1850
fractions, giving a sequence i/j of "the best" rational approximations. Then
1851
j*log(B)/log(BASE) is approximately equal to (the integer) i. This shows that
1852
we can get very close to being in trouble, but very rarely. For example,
1853
76573 is a denominator in one of the continued-fraction approximations to
1854
log(10)/log(2**15), and indeed:
1856
>>> log(10)/log(2**15)*76573
1859
is very close to an integer. If we were working with IEEE single-precision,
1860
rounding errors could kill us. Finding worst cases in IEEE double-precision
1861
requires better-than-double-precision log() functions, and Tim didn't bother.
1862
Instead the code checks to see whether the allocated space is enough as each
1863
new Python digit is added, and copies the whole thing to a larger long if not.
1864
This should happen extremely rarely, and in fact I don't have a test case
1865
that triggers it(!). Instead the code was tested by artificially allocating
1866
just 1 digit at the start, so that the copying code was exercised for every
1867
digit beyond the first.
1869
register twodigits c; /* current input character */
1873
twodigits convmultmax, convmult;
1877
static double log_base_BASE[37] = {0.0e0,};
1878
static int convwidth_base[37] = {0,};
1879
static twodigits convmultmax_base[37] = {0,};
1881
if (log_base_BASE[base] == 0.0) {
1882
twodigits convmax = base;
1885
log_base_BASE[base] = log((double)base) /
1886
log((double)PyLong_BASE);
1888
twodigits next = convmax * base;
1889
if (next > PyLong_BASE)
1894
convmultmax_base[base] = convmax;
1896
convwidth_base[base] = i;
1899
/* Find length of the string of numeric characters. */
1901
while (_PyLong_DigitValue[Py_CHARMASK(*scan)] < base)
1904
/* Create a long object that can contain the largest possible
1905
* integer with this base and length. Note that there's no
1906
* need to initialize z->ob_digit -- no slot is read up before
1907
* being stored into.
1909
size_z = (Py_ssize_t)((scan - str) * log_base_BASE[base]) + 1;
1910
/* Uncomment next line to test exceedingly rare copy code */
1913
z = _PyLong_New(size_z);
1918
/* `convwidth` consecutive input digits are treated as a single
1919
* digit in base `convmultmax`.
1921
convwidth = convwidth_base[base];
1922
convmultmax = convmultmax_base[base];
1925
while (str < scan) {
1926
/* grab up to convwidth digits from the input string */
1927
c = (digit)_PyLong_DigitValue[Py_CHARMASK(*str++)];
1928
for (i = 1; i < convwidth && str != scan; ++i, ++str) {
1929
c = (twodigits)(c * base +
1930
(int)_PyLong_DigitValue[Py_CHARMASK(*str)]);
1931
assert(c < PyLong_BASE);
1934
convmult = convmultmax;
1935
/* Calculate the shift only if we couldn't get
1938
if (i != convwidth) {
1944
/* Multiply z by convmult, and add c. */
1946
pzstop = pz + Py_SIZE(z);
1947
for (; pz < pzstop; ++pz) {
1948
c += (twodigits)*pz * convmult;
1949
*pz = (digit)(c & PyLong_MASK);
1952
/* carry off the current end? */
1954
assert(c < PyLong_BASE);
1955
if (Py_SIZE(z) < size_z) {
1961
/* Extremely rare. Get more space. */
1962
assert(Py_SIZE(z) == size_z);
1963
tmp = _PyLong_New(size_z + 1);
1968
memcpy(tmp->ob_digit,
1970
sizeof(digit) * size_z);
1973
z->ob_digit[size_z] = (digit)c;
1981
if (error_if_nonzero) {
1982
/* reset the base to 0, else the exception message
1983
doesn't make too much sense */
1985
if (Py_SIZE(z) != 0)
1987
/* there might still be other problems, therefore base
1988
remains zero here for the same reason */
1993
Py_SIZE(z) = -(Py_SIZE(z));
1994
while (*str && isspace(Py_CHARMASK(*str)))
2001
return (PyObject *) maybe_small_long(z);
2005
slen = strlen(orig_str) < 200 ? strlen(orig_str) : 200;
2006
strobj = PyUnicode_FromStringAndSize(orig_str, slen);
2009
PyErr_Format(PyExc_ValueError,
2010
"invalid literal for int() with base %d: %R",
2017
PyLong_FromUnicode(Py_UNICODE *u, Py_ssize_t length, int base)
2020
char *buffer = (char *)PyMem_MALLOC(length+1);
2025
if (PyUnicode_EncodeDecimal(u, length, buffer, NULL)) {
2029
result = PyLong_FromString(buffer, NULL, base);
2035
static PyLongObject *x_divrem
2036
(PyLongObject *, PyLongObject *, PyLongObject **);
2037
static PyObject *long_long(PyObject *v);
2039
/* Long division with remainder, top-level routine */
2042
long_divrem(PyLongObject *a, PyLongObject *b,
2043
PyLongObject **pdiv, PyLongObject **prem)
2045
Py_ssize_t size_a = ABS(Py_SIZE(a)), size_b = ABS(Py_SIZE(b));
2049
PyErr_SetString(PyExc_ZeroDivisionError,
2050
"integer division or modulo by zero");
2053
if (size_a < size_b ||
2054
(size_a == size_b &&
2055
a->ob_digit[size_a-1] < b->ob_digit[size_b-1])) {
2057
*pdiv = (PyLongObject*)PyLong_FromLong(0);
2061
*prem = (PyLongObject *) a;
2066
z = divrem1(a, b->ob_digit[0], &rem);
2069
*prem = (PyLongObject *) PyLong_FromLong((long)rem);
2070
if (*prem == NULL) {
2076
z = x_divrem(a, b, prem);
2081
The quotient z has the sign of a*b;
2082
the remainder r has the sign of a,
2084
if ((Py_SIZE(a) < 0) != (Py_SIZE(b) < 0))
2086
if (Py_SIZE(a) < 0 && Py_SIZE(*prem) != 0)
2088
*pdiv = maybe_small_long(z);
2092
/* Unsigned long division with remainder -- the algorithm */
2094
static PyLongObject *
2095
x_divrem(PyLongObject *v1, PyLongObject *w1, PyLongObject **prem)
2097
Py_ssize_t size_v = ABS(Py_SIZE(v1)), size_w = ABS(Py_SIZE(w1));
2098
digit d = (digit) ((twodigits)PyLong_BASE / (w1->ob_digit[size_w-1] + 1));
2099
PyLongObject *v = mul1(v1, d);
2100
PyLongObject *w = mul1(w1, d);
2104
if (v == NULL || w == NULL) {
2110
assert(size_v >= size_w && size_w > 1); /* Assert checks by div() */
2111
assert(Py_REFCNT(v) == 1); /* Since v will be used as accumulator! */
2112
assert(size_w == ABS(Py_SIZE(w))); /* That's how d was calculated */
2114
size_v = ABS(Py_SIZE(v));
2115
k = size_v - size_w;
2116
a = _PyLong_New(k + 1);
2118
for (j = size_v; a != NULL && k >= 0; --j, --k) {
2119
digit vj = (j >= size_v) ? 0 : v->ob_digit[j];
2121
stwodigits carry = 0;
2129
if (vj == w->ob_digit[size_w-1])
2132
q = (((twodigits)vj << PyLong_SHIFT) + v->ob_digit[j-1]) /
2133
w->ob_digit[size_w-1];
2135
while (w->ob_digit[size_w-2]*q >
2137
((twodigits)vj << PyLong_SHIFT)
2139
- q*w->ob_digit[size_w-1]
2144
for (i = 0; i < size_w && i+k < size_v; ++i) {
2145
twodigits z = w->ob_digit[i] * q;
2146
digit zz = (digit) (z >> PyLong_SHIFT);
2147
carry += v->ob_digit[i+k] - z
2148
+ ((twodigits)zz << PyLong_SHIFT);
2149
v->ob_digit[i+k] = (digit)(carry & PyLong_MASK);
2150
carry = Py_ARITHMETIC_RIGHT_SHIFT(stwodigits,
2151
carry, PyLong_SHIFT);
2156
carry += v->ob_digit[i+k];
2157
v->ob_digit[i+k] = 0;
2161
a->ob_digit[k] = (digit) q;
2163
assert(carry == -1);
2164
a->ob_digit[k] = (digit) q-1;
2166
for (i = 0; i < size_w && i+k < size_v; ++i) {
2167
carry += v->ob_digit[i+k] + w->ob_digit[i];
2168
v->ob_digit[i+k] = (digit)(carry & PyLong_MASK);
2169
carry = Py_ARITHMETIC_RIGHT_SHIFT(
2171
carry, PyLong_SHIFT);
2179
a = long_normalize(a);
2180
*prem = divrem1(v, d, &d);
2181
/* d receives the (unused) remainder */
2182
if (*prem == NULL) {
2195
long_dealloc(PyObject *v)
2197
Py_TYPE(v)->tp_free(v);
2201
long_repr(PyObject *v)
2203
return _PyLong_Format(v, 10);
2207
long_compare(PyLongObject *a, PyLongObject *b)
2211
if (Py_SIZE(a) != Py_SIZE(b)) {
2212
if (ABS(Py_SIZE(a)) == 0 && ABS(Py_SIZE(b)) == 0)
2215
sign = Py_SIZE(a) - Py_SIZE(b);
2218
Py_ssize_t i = ABS(Py_SIZE(a));
2219
while (--i >= 0 && a->ob_digit[i] == b->ob_digit[i])
2224
sign = (sdigit)a->ob_digit[i] - (sdigit)b->ob_digit[i];
2229
return sign < 0 ? -1 : sign > 0 ? 1 : 0;
2232
#define TEST_COND(cond) \
2233
((cond) ? Py_True : Py_False)
2236
long_richcompare(PyObject *self, PyObject *other, int op)
2240
CHECK_BINOP(self, other);
2244
result = long_compare((PyLongObject*)self, (PyLongObject*)other);
2245
/* Convert the return value to a Boolean */
2248
v = TEST_COND(result == 0);
2251
v = TEST_COND(result != 0);
2254
v = TEST_COND(result <= 0);
2257
v = TEST_COND(result >= 0);
2260
v = TEST_COND(result == -1);
2263
v = TEST_COND(result == 1);
2266
PyErr_BadArgument();
2274
long_hash(PyLongObject *v)
2280
/* This is designed so that Python ints and longs with the
2281
same value hash to the same value, otherwise comparisons
2282
of mapping keys will turn out weird */
2285
case -1: return v->ob_digit[0]==1 ? -2 : -(sdigit)v->ob_digit[0];
2287
case 1: return v->ob_digit[0];
2295
/* The following loop produces a C unsigned long x such that x is
2296
congruent to the absolute value of v modulo ULONG_MAX. The
2297
resulting x is nonzero if and only if v is. */
2299
/* Force a native long #-bits (32 or 64) circular shift */
2300
x = (x >> (8*SIZEOF_LONG-PyLong_SHIFT)) | (x << PyLong_SHIFT);
2301
x += v->ob_digit[i];
2302
/* If the addition above overflowed we compensate by
2303
incrementing. This preserves the value modulo
2305
if (x < v->ob_digit[i])
2309
if (x == (unsigned long)-1)
2310
x = (unsigned long)-2;
2315
/* Add the absolute values of two long integers. */
2317
static PyLongObject *
2318
x_add(PyLongObject *a, PyLongObject *b)
2320
Py_ssize_t size_a = ABS(Py_SIZE(a)), size_b = ABS(Py_SIZE(b));
2325
/* Ensure a is the larger of the two: */
2326
if (size_a < size_b) {
2327
{ PyLongObject *temp = a; a = b; b = temp; }
2328
{ Py_ssize_t size_temp = size_a;
2330
size_b = size_temp; }
2332
z = _PyLong_New(size_a+1);
2335
for (i = 0; i < size_b; ++i) {
2336
carry += a->ob_digit[i] + b->ob_digit[i];
2337
z->ob_digit[i] = carry & PyLong_MASK;
2338
carry >>= PyLong_SHIFT;
2340
for (; i < size_a; ++i) {
2341
carry += a->ob_digit[i];
2342
z->ob_digit[i] = carry & PyLong_MASK;
2343
carry >>= PyLong_SHIFT;
2345
z->ob_digit[i] = carry;
2346
return long_normalize(z);
2349
/* Subtract the absolute values of two integers. */
2351
static PyLongObject *
2352
x_sub(PyLongObject *a, PyLongObject *b)
2354
Py_ssize_t size_a = ABS(Py_SIZE(a)), size_b = ABS(Py_SIZE(b));
2360
/* Ensure a is the larger of the two: */
2361
if (size_a < size_b) {
2363
{ PyLongObject *temp = a; a = b; b = temp; }
2364
{ Py_ssize_t size_temp = size_a;
2366
size_b = size_temp; }
2368
else if (size_a == size_b) {
2369
/* Find highest digit where a and b differ: */
2371
while (--i >= 0 && a->ob_digit[i] == b->ob_digit[i])
2374
return (PyLongObject *)PyLong_FromLong(0);
2375
if (a->ob_digit[i] < b->ob_digit[i]) {
2377
{ PyLongObject *temp = a; a = b; b = temp; }
2379
size_a = size_b = i+1;
2381
z = _PyLong_New(size_a);
2384
for (i = 0; i < size_b; ++i) {
2385
/* The following assumes unsigned arithmetic
2386
works module 2**N for some N>PyLong_SHIFT. */
2387
borrow = a->ob_digit[i] - b->ob_digit[i] - borrow;
2388
z->ob_digit[i] = borrow & PyLong_MASK;
2389
borrow >>= PyLong_SHIFT;
2390
borrow &= 1; /* Keep only one sign bit */
2392
for (; i < size_a; ++i) {
2393
borrow = a->ob_digit[i] - borrow;
2394
z->ob_digit[i] = borrow & PyLong_MASK;
2395
borrow >>= PyLong_SHIFT;
2396
borrow &= 1; /* Keep only one sign bit */
2398
assert(borrow == 0);
2401
return long_normalize(z);
2405
long_add(PyLongObject *a, PyLongObject *b)
2411
if (ABS(Py_SIZE(a)) <= 1 && ABS(Py_SIZE(b)) <= 1) {
2412
PyObject *result = PyLong_FromLong(MEDIUM_VALUE(a) +
2416
if (Py_SIZE(a) < 0) {
2417
if (Py_SIZE(b) < 0) {
2419
if (z != NULL && Py_SIZE(z) != 0)
2420
Py_SIZE(z) = -(Py_SIZE(z));
2431
return (PyObject *)z;
2435
long_sub(PyLongObject *a, PyLongObject *b)
2441
if (ABS(Py_SIZE(a)) <= 1 && ABS(Py_SIZE(b)) <= 1) {
2443
r = PyLong_FromLong(MEDIUM_VALUE(a)-MEDIUM_VALUE(b));
2446
if (Py_SIZE(a) < 0) {
2451
if (z != NULL && Py_SIZE(z) != 0)
2452
Py_SIZE(z) = -(Py_SIZE(z));
2460
return (PyObject *)z;
2463
/* Grade school multiplication, ignoring the signs.
2464
* Returns the absolute value of the product, or NULL if error.
2466
static PyLongObject *
2467
x_mul(PyLongObject *a, PyLongObject *b)
2470
Py_ssize_t size_a = ABS(Py_SIZE(a));
2471
Py_ssize_t size_b = ABS(Py_SIZE(b));
2474
z = _PyLong_New(size_a + size_b);
2478
memset(z->ob_digit, 0, Py_SIZE(z) * sizeof(digit));
2480
/* Efficient squaring per HAC, Algorithm 14.16:
2481
* http://www.cacr.math.uwaterloo.ca/hac/about/chap14.pdf
2482
* Gives slightly less than a 2x speedup when a == b,
2483
* via exploiting that each entry in the multiplication
2484
* pyramid appears twice (except for the size_a squares).
2486
for (i = 0; i < size_a; ++i) {
2488
twodigits f = a->ob_digit[i];
2489
digit *pz = z->ob_digit + (i << 1);
2490
digit *pa = a->ob_digit + i + 1;
2491
digit *paend = a->ob_digit + size_a;
2498
carry = *pz + f * f;
2499
*pz++ = (digit)(carry & PyLong_MASK);
2500
carry >>= PyLong_SHIFT;
2501
assert(carry <= PyLong_MASK);
2503
/* Now f is added in twice in each column of the
2504
* pyramid it appears. Same as adding f<<1 once.
2507
while (pa < paend) {
2508
carry += *pz + *pa++ * f;
2509
*pz++ = (digit)(carry & PyLong_MASK);
2510
carry >>= PyLong_SHIFT;
2511
assert(carry <= (PyLong_MASK << 1));
2515
*pz++ = (digit)(carry & PyLong_MASK);
2516
carry >>= PyLong_SHIFT;
2519
*pz += (digit)(carry & PyLong_MASK);
2520
assert((carry >> PyLong_SHIFT) == 0);
2523
else { /* a is not the same as b -- gradeschool long mult */
2524
for (i = 0; i < size_a; ++i) {
2525
twodigits carry = 0;
2526
twodigits f = a->ob_digit[i];
2527
digit *pz = z->ob_digit + i;
2528
digit *pb = b->ob_digit;
2529
digit *pbend = b->ob_digit + size_b;
2536
while (pb < pbend) {
2537
carry += *pz + *pb++ * f;
2538
*pz++ = (digit)(carry & PyLong_MASK);
2539
carry >>= PyLong_SHIFT;
2540
assert(carry <= PyLong_MASK);
2543
*pz += (digit)(carry & PyLong_MASK);
2544
assert((carry >> PyLong_SHIFT) == 0);
2547
return long_normalize(z);
2550
/* A helper for Karatsuba multiplication (k_mul).
2551
Takes a long "n" and an integer "size" representing the place to
2552
split, and sets low and high such that abs(n) == (high << size) + low,
2553
viewing the shift as being by digits. The sign bit is ignored, and
2554
the return values are >= 0.
2555
Returns 0 on success, -1 on failure.
2558
kmul_split(PyLongObject *n, Py_ssize_t size, PyLongObject **high, PyLongObject **low)
2560
PyLongObject *hi, *lo;
2561
Py_ssize_t size_lo, size_hi;
2562
const Py_ssize_t size_n = ABS(Py_SIZE(n));
2564
size_lo = MIN(size_n, size);
2565
size_hi = size_n - size_lo;
2567
if ((hi = _PyLong_New(size_hi)) == NULL)
2569
if ((lo = _PyLong_New(size_lo)) == NULL) {
2574
memcpy(lo->ob_digit, n->ob_digit, size_lo * sizeof(digit));
2575
memcpy(hi->ob_digit, n->ob_digit + size_lo, size_hi * sizeof(digit));
2577
*high = long_normalize(hi);
2578
*low = long_normalize(lo);
2582
static PyLongObject *k_lopsided_mul(PyLongObject *a, PyLongObject *b);
2584
/* Karatsuba multiplication. Ignores the input signs, and returns the
2585
* absolute value of the product (or NULL if error).
2586
* See Knuth Vol. 2 Chapter 4.3.3 (Pp. 294-295).
2588
static PyLongObject *
2589
k_mul(PyLongObject *a, PyLongObject *b)
2591
Py_ssize_t asize = ABS(Py_SIZE(a));
2592
Py_ssize_t bsize = ABS(Py_SIZE(b));
2593
PyLongObject *ah = NULL;
2594
PyLongObject *al = NULL;
2595
PyLongObject *bh = NULL;
2596
PyLongObject *bl = NULL;
2597
PyLongObject *ret = NULL;
2598
PyLongObject *t1, *t2, *t3;
2599
Py_ssize_t shift; /* the number of digits we split off */
2602
/* (ah*X+al)(bh*X+bl) = ah*bh*X*X + (ah*bl + al*bh)*X + al*bl
2603
* Let k = (ah+al)*(bh+bl) = ah*bl + al*bh + ah*bh + al*bl
2604
* Then the original product is
2605
* ah*bh*X*X + (k - ah*bh - al*bl)*X + al*bl
2606
* By picking X to be a power of 2, "*X" is just shifting, and it's
2607
* been reduced to 3 multiplies on numbers half the size.
2610
/* We want to split based on the larger number; fiddle so that b
2613
if (asize > bsize) {
2623
/* Use gradeschool math when either number is too small. */
2624
i = a == b ? KARATSUBA_SQUARE_CUTOFF : KARATSUBA_CUTOFF;
2627
return (PyLongObject *)PyLong_FromLong(0);
2632
/* If a is small compared to b, splitting on b gives a degenerate
2633
* case with ah==0, and Karatsuba may be (even much) less efficient
2634
* than "grade school" then. However, we can still win, by viewing
2635
* b as a string of "big digits", each of width a->ob_size. That
2636
* leads to a sequence of balanced calls to k_mul.
2638
if (2 * asize <= bsize)
2639
return k_lopsided_mul(a, b);
2641
/* Split a & b into hi & lo pieces. */
2643
if (kmul_split(a, shift, &ah, &al) < 0) goto fail;
2644
assert(Py_SIZE(ah) > 0); /* the split isn't degenerate */
2652
else if (kmul_split(b, shift, &bh, &bl) < 0) goto fail;
2655
* 1. Allocate result space (asize + bsize digits: that's always
2657
* 2. Compute ah*bh, and copy into result at 2*shift.
2658
* 3. Compute al*bl, and copy into result at 0. Note that this
2659
* can't overlap with #2.
2660
* 4. Subtract al*bl from the result, starting at shift. This may
2661
* underflow (borrow out of the high digit), but we don't care:
2662
* we're effectively doing unsigned arithmetic mod
2663
* BASE**(sizea + sizeb), and so long as the *final* result fits,
2664
* borrows and carries out of the high digit can be ignored.
2665
* 5. Subtract ah*bh from the result, starting at shift.
2666
* 6. Compute (ah+al)*(bh+bl), and add it into the result starting
2670
/* 1. Allocate result space. */
2671
ret = _PyLong_New(asize + bsize);
2672
if (ret == NULL) goto fail;
2674
/* Fill with trash, to catch reference to uninitialized digits. */
2675
memset(ret->ob_digit, 0xDF, Py_SIZE(ret) * sizeof(digit));
2678
/* 2. t1 <- ah*bh, and copy into high digits of result. */
2679
if ((t1 = k_mul(ah, bh)) == NULL) goto fail;
2680
assert(Py_SIZE(t1) >= 0);
2681
assert(2*shift + Py_SIZE(t1) <= Py_SIZE(ret));
2682
memcpy(ret->ob_digit + 2*shift, t1->ob_digit,
2683
Py_SIZE(t1) * sizeof(digit));
2685
/* Zero-out the digits higher than the ah*bh copy. */
2686
i = Py_SIZE(ret) - 2*shift - Py_SIZE(t1);
2688
memset(ret->ob_digit + 2*shift + Py_SIZE(t1), 0,
2691
/* 3. t2 <- al*bl, and copy into the low digits. */
2692
if ((t2 = k_mul(al, bl)) == NULL) {
2696
assert(Py_SIZE(t2) >= 0);
2697
assert(Py_SIZE(t2) <= 2*shift); /* no overlap with high digits */
2698
memcpy(ret->ob_digit, t2->ob_digit, Py_SIZE(t2) * sizeof(digit));
2700
/* Zero out remaining digits. */
2701
i = 2*shift - Py_SIZE(t2); /* number of uninitialized digits */
2703
memset(ret->ob_digit + Py_SIZE(t2), 0, i * sizeof(digit));
2705
/* 4 & 5. Subtract ah*bh (t1) and al*bl (t2). We do al*bl first
2706
* because it's fresher in cache.
2708
i = Py_SIZE(ret) - shift; /* # digits after shift */
2709
(void)v_isub(ret->ob_digit + shift, i, t2->ob_digit, Py_SIZE(t2));
2712
(void)v_isub(ret->ob_digit + shift, i, t1->ob_digit, Py_SIZE(t1));
2715
/* 6. t3 <- (ah+al)(bh+bl), and add into result. */
2716
if ((t1 = x_add(ah, al)) == NULL) goto fail;
2725
else if ((t2 = x_add(bh, bl)) == NULL) {
2736
if (t3 == NULL) goto fail;
2737
assert(Py_SIZE(t3) >= 0);
2739
/* Add t3. It's not obvious why we can't run out of room here.
2740
* See the (*) comment after this function.
2742
(void)v_iadd(ret->ob_digit + shift, i, t3->ob_digit, Py_SIZE(t3));
2745
return long_normalize(ret);
2756
/* (*) Why adding t3 can't "run out of room" above.
2758
Let f(x) mean the floor of x and c(x) mean the ceiling of x. Some facts
2761
1. For any integer i, i = c(i/2) + f(i/2). In particular,
2762
bsize = c(bsize/2) + f(bsize/2).
2763
2. shift = f(bsize/2)
2765
4. Since we call k_lopsided_mul if asize*2 <= bsize, asize*2 > bsize in this
2766
routine, so asize > bsize/2 >= f(bsize/2) in this routine.
2768
We allocated asize + bsize result digits, and add t3 into them at an offset
2769
of shift. This leaves asize+bsize-shift allocated digit positions for t3
2770
to fit into, = (by #1 and #2) asize + f(bsize/2) + c(bsize/2) - f(bsize/2) =
2771
asize + c(bsize/2) available digit positions.
2773
bh has c(bsize/2) digits, and bl at most f(size/2) digits. So bh+hl has
2774
at most c(bsize/2) digits + 1 bit.
2776
If asize == bsize, ah has c(bsize/2) digits, else ah has at most f(bsize/2)
2777
digits, and al has at most f(bsize/2) digits in any case. So ah+al has at
2778
most (asize == bsize ? c(bsize/2) : f(bsize/2)) digits + 1 bit.
2780
The product (ah+al)*(bh+bl) therefore has at most
2782
c(bsize/2) + (asize == bsize ? c(bsize/2) : f(bsize/2)) digits + 2 bits
2784
and we have asize + c(bsize/2) available digit positions. We need to show
2785
this is always enough. An instance of c(bsize/2) cancels out in both, so
2786
the question reduces to whether asize digits is enough to hold
2787
(asize == bsize ? c(bsize/2) : f(bsize/2)) digits + 2 bits. If asize < bsize,
2788
then we're asking whether asize digits >= f(bsize/2) digits + 2 bits. By #4,
2789
asize is at least f(bsize/2)+1 digits, so this in turn reduces to whether 1
2790
digit is enough to hold 2 bits. This is so since PyLong_SHIFT=15 >= 2. If
2791
asize == bsize, then we're asking whether bsize digits is enough to hold
2792
c(bsize/2) digits + 2 bits, or equivalently (by #1) whether f(bsize/2) digits
2793
is enough to hold 2 bits. This is so if bsize >= 2, which holds because
2794
bsize >= KARATSUBA_CUTOFF >= 2.
2796
Note that since there's always enough room for (ah+al)*(bh+bl), and that's
2797
clearly >= each of ah*bh and al*bl, there's always enough room to subtract
2798
ah*bh and al*bl too.
2801
/* b has at least twice the digits of a, and a is big enough that Karatsuba
2802
* would pay off *if* the inputs had balanced sizes. View b as a sequence
2803
* of slices, each with a->ob_size digits, and multiply the slices by a,
2804
* one at a time. This gives k_mul balanced inputs to work with, and is
2805
* also cache-friendly (we compute one double-width slice of the result
2806
* at a time, then move on, never bactracking except for the helpful
2807
* single-width slice overlap between successive partial sums).
2809
static PyLongObject *
2810
k_lopsided_mul(PyLongObject *a, PyLongObject *b)
2812
const Py_ssize_t asize = ABS(Py_SIZE(a));
2813
Py_ssize_t bsize = ABS(Py_SIZE(b));
2814
Py_ssize_t nbdone; /* # of b digits already multiplied */
2816
PyLongObject *bslice = NULL;
2818
assert(asize > KARATSUBA_CUTOFF);
2819
assert(2 * asize <= bsize);
2821
/* Allocate result space, and zero it out. */
2822
ret = _PyLong_New(asize + bsize);
2825
memset(ret->ob_digit, 0, Py_SIZE(ret) * sizeof(digit));
2827
/* Successive slices of b are copied into bslice. */
2828
bslice = _PyLong_New(asize);
2834
PyLongObject *product;
2835
const Py_ssize_t nbtouse = MIN(bsize, asize);
2837
/* Multiply the next slice of b by a. */
2838
memcpy(bslice->ob_digit, b->ob_digit + nbdone,
2839
nbtouse * sizeof(digit));
2840
Py_SIZE(bslice) = nbtouse;
2841
product = k_mul(a, bslice);
2842
if (product == NULL)
2845
/* Add into result. */
2846
(void)v_iadd(ret->ob_digit + nbdone, Py_SIZE(ret) - nbdone,
2847
product->ob_digit, Py_SIZE(product));
2855
return long_normalize(ret);
2864
long_mul(PyLongObject *a, PyLongObject *b)
2870
/* fast path for single-digit multiplication */
2871
if (ABS(Py_SIZE(a)) <= 1 && ABS(Py_SIZE(b)) <= 1) {
2872
stwodigits v = (stwodigits)(MEDIUM_VALUE(a)) * MEDIUM_VALUE(b);
2873
#ifdef HAVE_LONG_LONG
2874
return PyLong_FromLongLong((PY_LONG_LONG)v);
2876
/* if we don't have long long then we're almost certainly
2877
using 15-bit digits, so v will fit in a long. In the
2878
unlikely event that we're using 30-bit digits on a platform
2879
without long long, a large v will just cause us to fall
2880
through to the general multiplication code below. */
2881
if (v >= LONG_MIN && v <= LONG_MAX)
2882
return PyLong_FromLong((long)v);
2887
/* Negate if exactly one of the inputs is negative. */
2888
if (((Py_SIZE(a) ^ Py_SIZE(b)) < 0) && z)
2890
return (PyObject *)z;
2893
/* The / and % operators are now defined in terms of divmod().
2894
The expression a mod b has the value a - b*floor(a/b).
2895
The long_divrem function gives the remainder after division of
2896
|a| by |b|, with the sign of a. This is also expressed
2897
as a - b*trunc(a/b), if trunc truncates towards zero.
2904
So, to get from rem to mod, we have to add b if a and b
2905
have different signs. We then subtract one from the 'div'
2906
part of the outcome to keep the invariant intact. */
2909
* *pdiv, *pmod = divmod(v, w)
2910
* NULL can be passed for pdiv or pmod, in which case that part of
2911
* the result is simply thrown away. The caller owns a reference to
2912
* each of these it requests (does not pass NULL for).
2915
l_divmod(PyLongObject *v, PyLongObject *w,
2916
PyLongObject **pdiv, PyLongObject **pmod)
2918
PyLongObject *div, *mod;
2920
if (long_divrem(v, w, &div, &mod) < 0)
2922
if ((Py_SIZE(mod) < 0 && Py_SIZE(w) > 0) ||
2923
(Py_SIZE(mod) > 0 && Py_SIZE(w) < 0)) {
2926
temp = (PyLongObject *) long_add(mod, w);
2933
one = (PyLongObject *) PyLong_FromLong(1L);
2935
(temp = (PyLongObject *) long_sub(div, one)) == NULL) {
2959
long_div(PyObject *a, PyObject *b)
2964
if (l_divmod((PyLongObject*)a, (PyLongObject*)b, &div, NULL) < 0)
2966
return (PyObject *)div;
2970
long_true_divide(PyObject *a, PyObject *b)
2973
int failed, aexp = -1, bexp = -1;
2976
ad = _PyLong_AsScaledDouble((PyObject *)a, &aexp);
2977
bd = _PyLong_AsScaledDouble((PyObject *)b, &bexp);
2978
failed = (ad == -1.0 || bd == -1.0) && PyErr_Occurred();
2981
/* 'aexp' and 'bexp' were initialized to -1 to silence gcc-4.0.x,
2982
but should really be set correctly after sucessful calls to
2983
_PyLong_AsScaledDouble() */
2984
assert(aexp >= 0 && bexp >= 0);
2987
PyErr_SetString(PyExc_ZeroDivisionError,
2988
"int division or modulo by zero");
2992
/* True value is very close to ad/bd * 2**(PyLong_SHIFT*(aexp-bexp)) */
2993
ad /= bd; /* overflow/underflow impossible here */
2995
if (aexp > INT_MAX / PyLong_SHIFT)
2997
else if (aexp < -(INT_MAX / PyLong_SHIFT))
2998
return PyFloat_FromDouble(0.0); /* underflow to 0 */
3000
ad = ldexp(ad, aexp * PyLong_SHIFT);
3001
if (Py_OVERFLOWED(ad)) /* ignore underflow to 0.0 */
3003
return PyFloat_FromDouble(ad);
3006
PyErr_SetString(PyExc_OverflowError,
3007
"int/int too large for a float");
3013
long_mod(PyObject *a, PyObject *b)
3019
if (l_divmod((PyLongObject*)a, (PyLongObject*)b, NULL, &mod) < 0)
3021
return (PyObject *)mod;
3025
long_divmod(PyObject *a, PyObject *b)
3027
PyLongObject *div, *mod;
3032
if (l_divmod((PyLongObject*)a, (PyLongObject*)b, &div, &mod) < 0) {
3037
PyTuple_SetItem(z, 0, (PyObject *) div);
3038
PyTuple_SetItem(z, 1, (PyObject *) mod);
3049
long_pow(PyObject *v, PyObject *w, PyObject *x)
3051
PyLongObject *a, *b, *c; /* a,b,c = v,w,x */
3052
int negativeOutput = 0; /* if x<0 return negative output */
3054
PyLongObject *z = NULL; /* accumulated result */
3055
Py_ssize_t i, j, k; /* counters */
3056
PyLongObject *temp = NULL;
3058
/* 5-ary values. If the exponent is large enough, table is
3059
* precomputed so that table[i] == a**i % c for i in range(32).
3061
PyLongObject *table[32] = {0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
3062
0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0};
3064
/* a, b, c = v, w, x */
3066
a = (PyLongObject*)v; Py_INCREF(a);
3067
b = (PyLongObject*)w; Py_INCREF(b);
3068
if (PyLong_Check(x)) {
3069
c = (PyLongObject *)x;
3072
else if (x == Py_None)
3077
Py_INCREF(Py_NotImplemented);
3078
return Py_NotImplemented;
3081
if (Py_SIZE(b) < 0) { /* if exponent is negative */
3083
PyErr_SetString(PyExc_TypeError, "pow() 2nd argument "
3084
"cannot be negative when 3rd argument specified");
3088
/* else return a float. This works because we know
3089
that this calls float_pow() which converts its
3090
arguments to double. */
3093
return PyFloat_Type.tp_as_number->nb_power(v, w, x);
3099
raise ValueError() */
3100
if (Py_SIZE(c) == 0) {
3101
PyErr_SetString(PyExc_ValueError,
3102
"pow() 3rd argument cannot be 0");
3107
negativeOutput = True
3108
modulus = -modulus */
3109
if (Py_SIZE(c) < 0) {
3111
temp = (PyLongObject *)_PyLong_Copy(c);
3122
if ((Py_SIZE(c) == 1) && (c->ob_digit[0] == 1)) {
3123
z = (PyLongObject *)PyLong_FromLong(0L);
3128
base = base % modulus
3129
Having the base positive just makes things easier. */
3130
if (Py_SIZE(a) < 0) {
3131
if (l_divmod(a, c, NULL, &temp) < 0)
3139
/* At this point a, b, and c are guaranteed non-negative UNLESS
3140
c is NULL, in which case a may be negative. */
3142
z = (PyLongObject *)PyLong_FromLong(1L);
3146
/* Perform a modular reduction, X = X % c, but leave X alone if c
3151
if (l_divmod(X, c, NULL, &temp) < 0) \
3158
/* Multiply two values, then reduce the result:
3159
result = X*Y % c. If c is NULL, skip the mod. */
3160
#define MULT(X, Y, result) \
3162
temp = (PyLongObject *)long_mul(X, Y); \
3165
Py_XDECREF(result); \
3171
if (Py_SIZE(b) <= FIVEARY_CUTOFF) {
3172
/* Left-to-right binary exponentiation (HAC Algorithm 14.79) */
3173
/* http://www.cacr.math.uwaterloo.ca/hac/about/chap14.pdf */
3174
for (i = Py_SIZE(b) - 1; i >= 0; --i) {
3175
digit bi = b->ob_digit[i];
3177
for (j = (digit)1 << (PyLong_SHIFT-1); j != 0; j >>= 1) {
3185
/* Left-to-right 5-ary exponentiation (HAC Algorithm 14.82) */
3186
Py_INCREF(z); /* still holds 1L */
3188
for (i = 1; i < 32; ++i)
3189
MULT(table[i-1], a, table[i])
3191
for (i = Py_SIZE(b) - 1; i >= 0; --i) {
3192
const digit bi = b->ob_digit[i];
3194
for (j = PyLong_SHIFT - 5; j >= 0; j -= 5) {
3195
const int index = (bi >> j) & 0x1f;
3196
for (k = 0; k < 5; ++k)
3199
MULT(z, table[index], z)
3204
if (negativeOutput && (Py_SIZE(z) != 0)) {
3205
temp = (PyLongObject *)long_sub(z, c);
3221
if (Py_SIZE(b) > FIVEARY_CUTOFF) {
3222
for (i = 0; i < 32; ++i)
3223
Py_XDECREF(table[i]);
3229
return (PyObject *)z;
3233
long_invert(PyLongObject *v)
3235
/* Implement ~x as -(x+1) */
3238
if (ABS(Py_SIZE(v)) <=1)
3239
return PyLong_FromLong(-(MEDIUM_VALUE(v)+1));
3240
w = (PyLongObject *)PyLong_FromLong(1L);
3243
x = (PyLongObject *) long_add(v, w);
3247
Py_SIZE(x) = -(Py_SIZE(x));
3248
return (PyObject *)maybe_small_long(x);
3252
long_neg(PyLongObject *v)
3255
if (ABS(Py_SIZE(v)) <= 1)
3256
return PyLong_FromLong(-MEDIUM_VALUE(v));
3257
z = (PyLongObject *)_PyLong_Copy(v);
3259
Py_SIZE(z) = -(Py_SIZE(v));
3260
return (PyObject *)z;
3264
long_abs(PyLongObject *v)
3269
return long_long((PyObject *)v);
3273
long_bool(PyLongObject *v)
3275
return ABS(Py_SIZE(v)) != 0;
3279
long_rshift(PyLongObject *a, PyLongObject *b)
3281
PyLongObject *z = NULL;
3283
Py_ssize_t newsize, wordshift, loshift, hishift, i, j;
3284
digit lomask, himask;
3288
if (Py_SIZE(a) < 0) {
3289
/* Right shifting negative numbers is harder */
3290
PyLongObject *a1, *a2;
3291
a1 = (PyLongObject *) long_invert(a);
3294
a2 = (PyLongObject *) long_rshift(a1, b);
3298
z = (PyLongObject *) long_invert(a2);
3303
shiftby = PyLong_AsLong((PyObject *)b);
3304
if (shiftby == -1L && PyErr_Occurred())
3307
PyErr_SetString(PyExc_ValueError,
3308
"negative shift count");
3311
wordshift = shiftby / PyLong_SHIFT;
3312
newsize = ABS(Py_SIZE(a)) - wordshift;
3314
return PyLong_FromLong(0);
3315
loshift = shiftby % PyLong_SHIFT;
3316
hishift = PyLong_SHIFT - loshift;
3317
lomask = ((digit)1 << hishift) - 1;
3318
himask = PyLong_MASK ^ lomask;
3319
z = _PyLong_New(newsize);
3323
Py_SIZE(z) = -(Py_SIZE(z));
3324
for (i = 0, j = wordshift; i < newsize; i++, j++) {
3325
z->ob_digit[i] = (a->ob_digit[j] >> loshift) & lomask;
3328
(a->ob_digit[j+1] << hishift) & himask;
3330
z = long_normalize(z);
3333
return (PyObject *) maybe_small_long(z);
3338
long_lshift(PyObject *v, PyObject *w)
3340
/* This version due to Tim Peters */
3341
PyLongObject *a = (PyLongObject*)v;
3342
PyLongObject *b = (PyLongObject*)w;
3343
PyLongObject *z = NULL;
3345
Py_ssize_t oldsize, newsize, wordshift, remshift, i, j;
3350
shiftby = PyLong_AsLong((PyObject *)b);
3351
if (shiftby == -1L && PyErr_Occurred())
3354
PyErr_SetString(PyExc_ValueError, "negative shift count");
3357
if ((long)(int)shiftby != shiftby) {
3358
PyErr_SetString(PyExc_ValueError,
3359
"outrageous left shift count");
3362
/* wordshift, remshift = divmod(shiftby, PyLong_SHIFT) */
3363
wordshift = (int)shiftby / PyLong_SHIFT;
3364
remshift = (int)shiftby - wordshift * PyLong_SHIFT;
3366
oldsize = ABS(Py_SIZE(a));
3367
newsize = oldsize + wordshift;
3370
z = _PyLong_New(newsize);
3375
for (i = 0; i < wordshift; i++)
3378
for (i = wordshift, j = 0; j < oldsize; i++, j++) {
3379
accum |= (twodigits)a->ob_digit[j] << remshift;
3380
z->ob_digit[i] = (digit)(accum & PyLong_MASK);
3381
accum >>= PyLong_SHIFT;
3384
z->ob_digit[newsize-1] = (digit)accum;
3387
z = long_normalize(z);
3389
return (PyObject *) maybe_small_long(z);
3393
/* Bitwise and/xor/or operations */
3396
long_bitwise(PyLongObject *a,
3397
int op, /* '&', '|', '^' */
3400
digit maska, maskb; /* 0 or PyLong_MASK */
3402
Py_ssize_t size_a, size_b, size_z, i;
3407
if (Py_SIZE(a) < 0) {
3408
a = (PyLongObject *) long_invert(a);
3411
maska = PyLong_MASK;
3417
if (Py_SIZE(b) < 0) {
3418
b = (PyLongObject *) long_invert(b);
3423
maskb = PyLong_MASK;
3433
if (maska != maskb) {
3434
maska ^= PyLong_MASK;
3439
if (maska && maskb) {
3441
maska ^= PyLong_MASK;
3442
maskb ^= PyLong_MASK;
3447
if (maska || maskb) {
3449
maska ^= PyLong_MASK;
3450
maskb ^= PyLong_MASK;
3456
/* JRH: The original logic here was to allocate the result value (z)
3457
as the longer of the two operands. However, there are some cases
3458
where the result is guaranteed to be shorter than that: AND of two
3459
positives, OR of two negatives: use the shorter number. AND with
3460
mixed signs: use the positive number. OR with mixed signs: use the
3461
negative number. After the transformations above, op will be '&'
3462
iff one of these cases applies, and mask will be non-0 for operands
3463
whose length should be ignored.
3466
size_a = Py_SIZE(a);
3467
size_b = Py_SIZE(b);
3471
: (maskb ? size_a : MIN(size_a, size_b)))
3472
: MAX(size_a, size_b);
3473
z = _PyLong_New(size_z);
3480
for (i = 0; i < size_z; ++i) {
3481
diga = (i < size_a ? a->ob_digit[i] : 0) ^ maska;
3482
digb = (i < size_b ? b->ob_digit[i] : 0) ^ maskb;
3484
case '&': z->ob_digit[i] = diga & digb; break;
3485
case '|': z->ob_digit[i] = diga | digb; break;
3486
case '^': z->ob_digit[i] = diga ^ digb; break;
3492
z = long_normalize(z);
3494
return (PyObject *) maybe_small_long(z);
3501
long_and(PyObject *a, PyObject *b)
3505
c = long_bitwise((PyLongObject*)a, '&', (PyLongObject*)b);
3510
long_xor(PyObject *a, PyObject *b)
3514
c = long_bitwise((PyLongObject*)a, '^', (PyLongObject*)b);
3519
long_or(PyObject *a, PyObject *b)
3523
c = long_bitwise((PyLongObject*)a, '|', (PyLongObject*)b);
3528
long_long(PyObject *v)
3530
if (PyLong_CheckExact(v))
3533
v = _PyLong_Copy((PyLongObject *)v);
3538
long_float(PyObject *v)
3541
result = PyLong_AsDouble(v);
3542
if (result == -1.0 && PyErr_Occurred())
3544
return PyFloat_FromDouble(result);
3548
long_subtype_new(PyTypeObject *type, PyObject *args, PyObject *kwds);
3551
long_new(PyTypeObject *type, PyObject *args, PyObject *kwds)
3554
int base = -909; /* unlikely! */
3555
static char *kwlist[] = {"x", "base", 0};
3557
if (type != &PyLong_Type)
3558
return long_subtype_new(type, args, kwds); /* Wimp out */
3559
if (!PyArg_ParseTupleAndKeywords(args, kwds, "|Oi:int", kwlist,
3563
return PyLong_FromLong(0L);
3565
return PyNumber_Long(x);
3566
else if (PyUnicode_Check(x))
3567
return PyLong_FromUnicode(PyUnicode_AS_UNICODE(x),
3568
PyUnicode_GET_SIZE(x),
3570
else if (PyByteArray_Check(x) || PyBytes_Check(x)) {
3571
/* Since PyLong_FromString doesn't have a length parameter,
3572
* check here for possible NULs in the string. */
3574
Py_ssize_t size = Py_SIZE(x);
3575
if (PyByteArray_Check(x))
3576
string = PyByteArray_AS_STRING(x);
3578
string = PyBytes_AS_STRING(x);
3579
if (strlen(string) != (size_t)size) {
3580
/* We only see this if there's a null byte in x,
3581
x is a bytes or buffer, *and* a base is given. */
3582
PyErr_Format(PyExc_ValueError,
3583
"invalid literal for int() with base %d: %R",
3587
return PyLong_FromString(string, NULL, base);
3590
PyErr_SetString(PyExc_TypeError,
3591
"int() can't convert non-string with explicit base");
3596
/* Wimpy, slow approach to tp_new calls for subtypes of long:
3597
first create a regular long from whatever arguments we got,
3598
then allocate a subtype instance and initialize it from
3599
the regular long. The regular long is then thrown away.
3602
long_subtype_new(PyTypeObject *type, PyObject *args, PyObject *kwds)
3604
PyLongObject *tmp, *newobj;
3607
assert(PyType_IsSubtype(type, &PyLong_Type));
3608
tmp = (PyLongObject *)long_new(&PyLong_Type, args, kwds);
3611
assert(PyLong_CheckExact(tmp));
3615
newobj = (PyLongObject *)type->tp_alloc(type, n);
3616
if (newobj == NULL) {
3620
assert(PyLong_Check(newobj));
3621
Py_SIZE(newobj) = Py_SIZE(tmp);
3622
for (i = 0; i < n; i++)
3623
newobj->ob_digit[i] = tmp->ob_digit[i];
3625
return (PyObject *)newobj;
3629
long_getnewargs(PyLongObject *v)
3631
return Py_BuildValue("(N)", _PyLong_Copy(v));
3635
long_getN(PyLongObject *v, void *context) {
3636
return PyLong_FromLong((Py_intptr_t)context);
3640
long__format__(PyObject *self, PyObject *args)
3642
PyObject *format_spec;
3644
if (!PyArg_ParseTuple(args, "U:__format__", &format_spec))
3646
return _PyLong_FormatAdvanced(self,
3647
PyUnicode_AS_UNICODE(format_spec),
3648
PyUnicode_GET_SIZE(format_spec));
3652
long_round(PyObject *self, PyObject *args)
3654
PyObject *o_ndigits=NULL, *temp;
3655
PyLongObject *pow=NULL, *q=NULL, *r=NULL, *ndigits=NULL, *one;
3659
/* Notes on the algorithm: to round to the nearest 10**n (n positive),
3660
the straightforward method is:
3663
(2) round to nearest integer (round to even in case of tie)
3664
(3) multiply result by 10**n.
3666
But the rounding step involves examining the fractional part of the
3667
quotient to see whether it's greater than 0.5 or not. Since we
3668
want to do the whole calculation in integer arithmetic, it's
3671
(1) divide by (10**n)/2
3672
(2) round to nearest multiple of 2 (multiple of 4 in case of tie)
3673
(3) multiply result by (10**n)/2.
3675
Then all we need to know about the fractional part of the quotient
3676
arising in step (2) is whether it's zero or not.
3678
Doing both a multiplication and division is wasteful, and is easily
3679
avoided if we just figure out how much to adjust the original input
3680
by to do the rounding.
3682
Here's the whole algorithm expressed in Python.
3684
def round(self, ndigits = None):
3685
"""round(int, int) -> int"""
3686
if ndigits is None or ndigits >= 0:
3688
pow = 10**-ndigits >> 1
3689
q, r = divmod(self, pow)
3692
if (q & 2 == r == 0):
3699
if (!PyArg_ParseTuple(args, "|O", &o_ndigits))
3701
if (o_ndigits == NULL)
3702
return long_long(self);
3704
ndigits = (PyLongObject *)PyNumber_Index(o_ndigits);
3705
if (ndigits == NULL)
3708
if (Py_SIZE(ndigits) >= 0) {
3710
return long_long(self);
3713
Py_INCREF(self); /* to keep refcounting simple */
3714
/* we now own references to self, ndigits */
3716
/* pow = 10 ** -ndigits >> 1 */
3717
pow = (PyLongObject *)PyLong_FromLong(10L);
3720
temp = long_neg(ndigits);
3722
ndigits = (PyLongObject *)temp;
3723
if (ndigits == NULL)
3725
temp = long_pow((PyObject *)pow, (PyObject *)ndigits, Py_None);
3727
pow = (PyLongObject *)temp;
3730
assert(PyLong_Check(pow)); /* check long_pow returned a long */
3731
one = (PyLongObject *)PyLong_FromLong(1L);
3734
temp = long_rshift(pow, one);
3737
pow = (PyLongObject *)temp;
3741
/* q, r = divmod(self, pow) */
3742
errcode = l_divmod((PyLongObject *)self, pow, &q, &r);
3747
temp = long_sub((PyLongObject *)self, r);
3753
/* get value of quotient modulo 4 */
3754
if (Py_SIZE(q) == 0)
3756
else if (Py_SIZE(q) > 0)
3757
q_mod_4 = q->ob_digit[0] & 3;
3759
q_mod_4 = (PyLong_BASE-q->ob_digit[0]) & 3;
3761
if ((q_mod_4 & 1) == 1) {
3762
/* q is odd; round self up or down by adding or subtracting pow */
3763
if (q_mod_4 == 1 && Py_SIZE(r) == 0)
3764
temp = (PyObject *)long_sub((PyLongObject *)self, pow);
3766
temp = (PyObject *)long_add((PyLongObject *)self, pow);
3783
Py_XDECREF(ndigits);
3788
long_sizeof(PyLongObject *v)
3792
res = offsetof(PyLongObject, ob_digit) + ABS(Py_SIZE(v))*sizeof(digit);
3793
return PyLong_FromSsize_t(res);
3796
static const unsigned char BitLengthTable[32] = {
3797
0, 1, 2, 2, 3, 3, 3, 3, 4, 4, 4, 4, 4, 4, 4, 4,
3798
5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5
3802
long_bit_length(PyLongObject *v)
3804
PyLongObject *result, *x, *y;
3805
Py_ssize_t ndigits, msd_bits = 0;
3809
assert(PyLong_Check(v));
3811
ndigits = ABS(Py_SIZE(v));
3813
return PyLong_FromLong(0);
3815
msd = v->ob_digit[ndigits-1];
3820
msd_bits += (long)(BitLengthTable[msd]);
3822
if (ndigits <= PY_SSIZE_T_MAX/PyLong_SHIFT)
3823
return PyLong_FromSsize_t((ndigits-1)*PyLong_SHIFT + msd_bits);
3825
/* expression above may overflow; use Python integers instead */
3826
result = (PyLongObject *)PyLong_FromSsize_t(ndigits - 1);
3829
x = (PyLongObject *)PyLong_FromLong(PyLong_SHIFT);
3832
y = (PyLongObject *)long_mul(result, x);
3839
x = (PyLongObject *)PyLong_FromLong(msd_bits);
3842
y = (PyLongObject *)long_add(result, x);
3849
return (PyObject *)result;
3856
PyDoc_STRVAR(long_bit_length_doc,
3857
"int.bit_length() -> int\n\
3859
Number of bits necessary to represent self in binary.\n\
3862
>>> (37).bit_length()\n\
3867
long_is_finite(PyObject *v)
3873
static PyMethodDef long_methods[] = {
3874
{"conjugate", (PyCFunction)long_long, METH_NOARGS,
3875
"Returns self, the complex conjugate of any int."},
3876
{"bit_length", (PyCFunction)long_bit_length, METH_NOARGS,
3877
long_bit_length_doc},
3879
{"is_finite", (PyCFunction)long_is_finite, METH_NOARGS,
3880
"Returns always True."},
3882
{"__trunc__", (PyCFunction)long_long, METH_NOARGS,
3883
"Truncating an Integral returns itself."},
3884
{"__floor__", (PyCFunction)long_long, METH_NOARGS,
3885
"Flooring an Integral returns itself."},
3886
{"__ceil__", (PyCFunction)long_long, METH_NOARGS,
3887
"Ceiling of an Integral returns itself."},
3888
{"__round__", (PyCFunction)long_round, METH_VARARGS,
3889
"Rounding an Integral returns itself.\n"
3890
"Rounding with an ndigits argument also returns an integer."},
3891
{"__getnewargs__", (PyCFunction)long_getnewargs, METH_NOARGS},
3892
{"__format__", (PyCFunction)long__format__, METH_VARARGS},
3893
{"__sizeof__", (PyCFunction)long_sizeof, METH_NOARGS,
3894
"Returns size in memory, in bytes"},
3895
{NULL, NULL} /* sentinel */
3898
static PyGetSetDef long_getset[] = {
3900
(getter)long_long, (setter)NULL,
3901
"the real part of a complex number",
3904
(getter)long_getN, (setter)NULL,
3905
"the imaginary part of a complex number",
3908
(getter)long_long, (setter)NULL,
3909
"the numerator of a rational number in lowest terms",
3912
(getter)long_getN, (setter)NULL,
3913
"the denominator of a rational number in lowest terms",
3915
{NULL} /* Sentinel */
3918
PyDoc_STRVAR(long_doc,
3919
"int(x[, base]) -> integer\n\
3921
Convert a string or number to an integer, if possible. A floating\n\
3922
point argument will be truncated towards zero (this does not include a\n\
3923
string representation of a floating point number!) When converting a\n\
3924
string, use the optional base. It is an error to supply a base when\n\
3925
converting a non-string.");
3927
static PyNumberMethods long_as_number = {
3928
(binaryfunc) long_add, /*nb_add*/
3929
(binaryfunc) long_sub, /*nb_subtract*/
3930
(binaryfunc) long_mul, /*nb_multiply*/
3931
long_mod, /*nb_remainder*/
3932
long_divmod, /*nb_divmod*/
3933
long_pow, /*nb_power*/
3934
(unaryfunc) long_neg, /*nb_negative*/
3935
(unaryfunc) long_long, /*tp_positive*/
3936
(unaryfunc) long_abs, /*tp_absolute*/
3937
(inquiry) long_bool, /*tp_bool*/
3938
(unaryfunc) long_invert, /*nb_invert*/
3939
long_lshift, /*nb_lshift*/
3940
(binaryfunc) long_rshift, /*nb_rshift*/
3941
long_and, /*nb_and*/
3942
long_xor, /*nb_xor*/
3944
long_long, /*nb_int*/
3946
long_float, /*nb_float*/
3947
0, /* nb_inplace_add */
3948
0, /* nb_inplace_subtract */
3949
0, /* nb_inplace_multiply */
3950
0, /* nb_inplace_remainder */
3951
0, /* nb_inplace_power */
3952
0, /* nb_inplace_lshift */
3953
0, /* nb_inplace_rshift */
3954
0, /* nb_inplace_and */
3955
0, /* nb_inplace_xor */
3956
0, /* nb_inplace_or */
3957
long_div, /* nb_floor_divide */
3958
long_true_divide, /* nb_true_divide */
3959
0, /* nb_inplace_floor_divide */
3960
0, /* nb_inplace_true_divide */
3961
long_long, /* nb_index */
3964
PyTypeObject PyLong_Type = {
3965
PyVarObject_HEAD_INIT(&PyType_Type, 0)
3966
"int", /* tp_name */
3967
offsetof(PyLongObject, ob_digit), /* tp_basicsize */
3968
sizeof(digit), /* tp_itemsize */
3969
long_dealloc, /* tp_dealloc */
3973
0, /* tp_reserved */
3974
long_repr, /* tp_repr */
3975
&long_as_number, /* tp_as_number */
3976
0, /* tp_as_sequence */
3977
0, /* tp_as_mapping */
3978
(hashfunc)long_hash, /* tp_hash */
3980
long_repr, /* tp_str */
3981
PyObject_GenericGetAttr, /* tp_getattro */
3982
0, /* tp_setattro */
3983
0, /* tp_as_buffer */
3984
Py_TPFLAGS_DEFAULT | Py_TPFLAGS_BASETYPE |
3985
Py_TPFLAGS_LONG_SUBCLASS, /* tp_flags */
3986
long_doc, /* tp_doc */
3987
0, /* tp_traverse */
3989
long_richcompare, /* tp_richcompare */
3990
0, /* tp_weaklistoffset */
3992
0, /* tp_iternext */
3993
long_methods, /* tp_methods */
3995
long_getset, /* tp_getset */
3998
0, /* tp_descr_get */
3999
0, /* tp_descr_set */
4000
0, /* tp_dictoffset */
4003
long_new, /* tp_new */
4004
PyObject_Del, /* tp_free */
4007
static PyTypeObject Int_InfoType;
4009
PyDoc_STRVAR(int_info__doc__,
4012
A struct sequence that holds information about Python's\n\
4013
internal representation of integers. The attributes are read only.");
4015
static PyStructSequence_Field int_info_fields[] = {
4016
{"bits_per_digit", "size of a digit in bits"},
4017
{"sizeof_digit", "size in bytes of the C type used to "
4018
"represent a digit"},
4022
static PyStructSequence_Desc int_info_desc = {
4023
"sys.int_info", /* name */
4024
int_info__doc__, /* doc */
4025
int_info_fields, /* fields */
4026
2 /* number of fields */
4030
PyLong_GetInfo(void)
4034
int_info = PyStructSequence_New(&Int_InfoType);
4035
if (int_info == NULL)
4037
PyStructSequence_SET_ITEM(int_info, field++, PyLong_FromLong(PyLong_SHIFT));
4038
PyStructSequence_SET_ITEM(int_info, field++, PyLong_FromLong(sizeof(digit)));
4039
if (PyErr_Occurred()) {
4049
#if NSMALLNEGINTS + NSMALLPOSINTS > 0
4051
PyLongObject *v = small_ints;
4053
for (ival = -NSMALLNEGINTS; ival < NSMALLPOSINTS; ival++, v++) {
4054
size = (ival < 0) ? -1 : ((ival == 0) ? 0 : 1);
4055
if (Py_TYPE(v) == &PyLong_Type) {
4056
/* The element is already initialized, most likely
4057
* the Python interpreter was initialized before.
4060
PyObject* op = (PyObject*)v;
4062
refcnt = Py_REFCNT(op) < 0 ? 0 : Py_REFCNT(op);
4063
_Py_NewReference(op);
4064
/* _Py_NewReference sets the ref count to 1 but
4065
* the ref count might be larger. Set the refcnt
4066
* to the original refcnt + 1 */
4067
Py_REFCNT(op) = refcnt + 1;
4068
assert(Py_SIZE(op) == size);
4069
assert(v->ob_digit[0] == abs(ival));
4072
PyObject_INIT(v, &PyLong_Type);
4075
v->ob_digit[0] = abs(ival);
4078
/* initialize int_info */
4079
if (Int_InfoType.tp_name == 0)
4080
PyStructSequence_InitType(&Int_InfoType, &int_info_desc);
4088
/* Integers are currently statically allocated. Py_DECREF is not
4089
needed, but Python must forget about the reference or multiple
4090
reinitializations will fail. */
4091
#if NSMALLNEGINTS + NSMALLPOSINTS > 0
4093
PyLongObject *v = small_ints;
4094
for (i = 0; i < NSMALLNEGINTS + NSMALLPOSINTS; i++, v++) {
4096
_Py_ForgetReference((PyObject*)v);
added
removed
Objects/longobject.c
