1 /* Long (arbitrary precision) integer object implementation */
2
3 /* XXX The functional organization of this file is terrible */
4
5 #include "Python.h"
6 #include "longintrepr.h"
7 #include "structseq.h"
8
9 #include <float.h>
10 #include <ctype.h>
11 #include <stddef.h>
12
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).
16 */
17 #define KARATSUBA_CUTOFF 70
18 #define KARATSUBA_SQUARE_CUTOFF (2 * KARATSUBA_CUTOFF)
19
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.
24 */
25 #define FIVEARY_CUTOFF 8
26
27 #define ABS(x) ((x) < 0 ? -(x) : (x))
28
29 #undef MIN
30 #undef MAX
31 #define MAX(x, y) ((x) < (y) ? (y) : (x))
32 #define MIN(x, y) ((x) > (y) ? (y) : (x))
33
34 #define SIGCHECK(PyTryBlock) \
35 do { \
36 if (--_Py_Ticker < 0) { \
37 _Py_Ticker = _Py_CheckInterval; \
38 if (PyErr_CheckSignals()) PyTryBlock \
39 } \
40 } while(0)
41
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. */
45
46 static PyLongObject *
long_normalize(register PyLongObject * v)47 long_normalize(register PyLongObject *v)
48 {
49 Py_ssize_t j = ABS(Py_SIZE(v));
50 Py_ssize_t i = j;
51
52 while (i > 0 && v->ob_digit[i-1] == 0)
53 --i;
54 if (i != j)
55 Py_SIZE(v) = (Py_SIZE(v) < 0) ? -(i) : i;
56 return v;
57 }
58
59 /* Allocate a new long int object with size digits.
60 Return NULL and set exception if we run out of memory. */
61
62 #define MAX_LONG_DIGITS \
63 ((PY_SSIZE_T_MAX - offsetof(PyLongObject, ob_digit))/sizeof(digit))
64
65 PyLongObject *
_PyLong_New(Py_ssize_t size)66 _PyLong_New(Py_ssize_t size)
67 {
68 if (size > (Py_ssize_t)MAX_LONG_DIGITS) {
69 PyErr_SetString(PyExc_OverflowError,
70 "too many digits in integer");
71 return NULL;
72 }
73 /* coverity[ampersand_in_size] */
74 /* XXX(nnorwitz): PyObject_NEW_VAR / _PyObject_VAR_SIZE need to detect
75 overflow */
76 return PyObject_NEW_VAR(PyLongObject, &PyLong_Type, size);
77 }
78
79 PyObject *
_PyLong_Copy(PyLongObject * src)80 _PyLong_Copy(PyLongObject *src)
81 {
82 PyLongObject *result;
83 Py_ssize_t i;
84
85 assert(src != NULL);
86 i = src->ob_size;
87 if (i < 0)
88 i = -(i);
89 result = _PyLong_New(i);
90 if (result != NULL) {
91 result->ob_size = src->ob_size;
92 while (--i >= 0)
93 result->ob_digit[i] = src->ob_digit[i];
94 }
95 return (PyObject *)result;
96 }
97
98 /* Create a new long int object from a C long int */
99
100 PyObject *
PyLong_FromLong(long ival)101 PyLong_FromLong(long ival)
102 {
103 PyLongObject *v;
104 unsigned long abs_ival;
105 unsigned long t; /* unsigned so >> doesn't propagate sign bit */
106 int ndigits = 0;
107 int negative = 0;
108
109 if (ival < 0) {
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;
114 negative = 1;
115 }
116 else {
117 abs_ival = (unsigned long)ival;
118 }
119
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
123 needed. */
124 t = abs_ival;
125 while (t) {
126 ++ndigits;
127 t >>= PyLong_SHIFT;
128 }
129 v = _PyLong_New(ndigits);
130 if (v != NULL) {
131 digit *p = v->ob_digit;
132 v->ob_size = negative ? -ndigits : ndigits;
133 t = abs_ival;
134 while (t) {
135 *p++ = (digit)(t & PyLong_MASK);
136 t >>= PyLong_SHIFT;
137 }
138 }
139 return (PyObject *)v;
140 }
141
142 /* Create a new long int object from a C unsigned long int */
143
144 PyObject *
PyLong_FromUnsignedLong(unsigned long ival)145 PyLong_FromUnsignedLong(unsigned long ival)
146 {
147 PyLongObject *v;
148 unsigned long t;
149 int ndigits = 0;
150
151 /* Count the number of Python digits. */
152 t = (unsigned long)ival;
153 while (t) {
154 ++ndigits;
155 t >>= PyLong_SHIFT;
156 }
157 v = _PyLong_New(ndigits);
158 if (v != NULL) {
159 digit *p = v->ob_digit;
160 Py_SIZE(v) = ndigits;
161 while (ival) {
162 *p++ = (digit)(ival & PyLong_MASK);
163 ival >>= PyLong_SHIFT;
164 }
165 }
166 return (PyObject *)v;
167 }
168
169 /* Create a new long int object from a C double */
170
171 PyObject *
PyLong_FromDouble(double dval)172 PyLong_FromDouble(double dval)
173 {
174 PyLongObject *v;
175 double frac;
176 int i, ndig, expo, neg;
177 neg = 0;
178 if (Py_IS_INFINITY(dval)) {
179 PyErr_SetString(PyExc_OverflowError,
180 "cannot convert float infinity to integer");
181 return NULL;
182 }
183 if (Py_IS_NAN(dval)) {
184 PyErr_SetString(PyExc_ValueError,
185 "cannot convert float NaN to integer");
186 return NULL;
187 }
188 if (dval < 0.0) {
189 neg = 1;
190 dval = -dval;
191 }
192 frac = frexp(dval, &expo); /* dval = frac*2**expo; 0.0 <= frac < 1.0 */
193 if (expo <= 0)
194 return PyLong_FromLong(0L);
195 ndig = (expo-1) / PyLong_SHIFT + 1; /* Number of 'digits' in result */
196 v = _PyLong_New(ndig);
197 if (v == NULL)
198 return NULL;
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);
205 }
206 if (neg)
207 Py_SIZE(v) = -(Py_SIZE(v));
208 return (PyObject *)v;
209 }
210
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 positive 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-".
219 */
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)
222
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.
226
227 For other errors (e.g., type error), returns -1 and sets an error
228 condition.
229 */
230
231 long
PyLong_AsLongAndOverflow(PyObject * vv,int * overflow)232 PyLong_AsLongAndOverflow(PyObject *vv, int *overflow)
233 {
234 /* This version by Tim Peters */
235 register PyLongObject *v;
236 unsigned long x, prev;
237 long res;
238 Py_ssize_t i;
239 int sign;
240 int do_decref = 0; /* if nb_int was called */
241
242 *overflow = 0;
243 if (vv == NULL) {
244 PyErr_BadInternalCall();
245 return -1;
246 }
247
248 if(PyInt_Check(vv))
249 return PyInt_AsLong(vv);
250
251 if (!PyLong_Check(vv)) {
252 PyNumberMethods *nb;
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");
257 return -1;
258 }
259 vv = (*nb->nb_int) (vv);
260 if (vv == NULL)
261 return -1;
262 do_decref = 1;
263 if(PyInt_Check(vv)) {
264 res = PyInt_AsLong(vv);
265 goto exit;
266 }
267 if (!PyLong_Check(vv)) {
268 Py_DECREF(vv);
269 PyErr_SetString(PyExc_TypeError,
270 "nb_int should return int object");
271 return -1;
272 }
273 }
274
275 res = -1;
276 v = (PyLongObject *)vv;
277 i = Py_SIZE(v);
278
279 switch (i) {
280 case -1:
281 res = -(sdigit)v->ob_digit[0];
282 break;
283 case 0:
284 res = 0;
285 break;
286 case 1:
287 res = v->ob_digit[0];
288 break;
289 default:
290 sign = 1;
291 x = 0;
292 if (i < 0) {
293 sign = -1;
294 i = -(i);
295 }
296 while (--i >= 0) {
297 prev = x;
298 x = (x << PyLong_SHIFT) + v->ob_digit[i];
299 if ((x >> PyLong_SHIFT) != prev) {
300 *overflow = sign;
301 goto exit;
302 }
303 }
304 /* Haven't lost any bits, but casting to long requires extra
305 * care (see comment above).
306 */
307 if (x <= (unsigned long)LONG_MAX) {
308 res = (long)x * sign;
309 }
310 else if (sign < 0 && x == PY_ABS_LONG_MIN) {
311 res = LONG_MIN;
312 }
313 else {
314 *overflow = sign;
315 /* res is already set to -1 */
316 }
317 }
318 exit:
319 if (do_decref) {
320 Py_DECREF(vv);
321 }
322 return res;
323 }
324
325 /* Get a C long int from a long int object.
326 Returns -1 and sets an error condition if overflow occurs. */
327
328 long
PyLong_AsLong(PyObject * obj)329 PyLong_AsLong(PyObject *obj)
330 {
331 int overflow;
332 long result = PyLong_AsLongAndOverflow(obj, &overflow);
333 if (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");
338 }
339 return result;
340 }
341
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. */
344
345 int
_PyLong_AsInt(PyObject * obj)346 _PyLong_AsInt(PyObject *obj)
347 {
348 int overflow;
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");
355 return -1;
356 }
357 return (int)result;
358 }
359
360 /* Get a Py_ssize_t from a long int object.
361 Returns -1 and sets an error condition if overflow occurs. */
362
363 Py_ssize_t
PyLong_AsSsize_t(PyObject * vv)364 PyLong_AsSsize_t(PyObject *vv) {
365 register PyLongObject *v;
366 size_t x, prev;
367 Py_ssize_t i;
368 int sign;
369
370 if (vv == NULL || !PyLong_Check(vv)) {
371 PyErr_BadInternalCall();
372 return -1;
373 }
374 v = (PyLongObject *)vv;
375 i = v->ob_size;
376 sign = 1;
377 x = 0;
378 if (i < 0) {
379 sign = -1;
380 i = -(i);
381 }
382 while (--i >= 0) {
383 prev = x;
384 x = (x << PyLong_SHIFT) | v->ob_digit[i];
385 if ((x >> PyLong_SHIFT) != prev)
386 goto overflow;
387 }
388 /* Haven't lost any bits, but casting to a signed type requires
389 * extra care (see comment above).
390 */
391 if (x <= (size_t)PY_SSIZE_T_MAX) {
392 return (Py_ssize_t)x * sign;
393 }
394 else if (sign < 0 && x == PY_ABS_SSIZE_T_MIN) {
395 return PY_SSIZE_T_MIN;
396 }
397 /* else overflow */
398
399 overflow:
400 PyErr_SetString(PyExc_OverflowError,
401 "long int too large to convert to int");
402 return -1;
403 }
404
405 /* Get a C unsigned long int from a long int object.
406 Returns -1 and sets an error condition if overflow occurs. */
407
408 unsigned long
PyLong_AsUnsignedLong(PyObject * vv)409 PyLong_AsUnsignedLong(PyObject *vv)
410 {
411 register PyLongObject *v;
412 unsigned long x, prev;
413 Py_ssize_t i;
414
415 if (vv == NULL || !PyLong_Check(vv)) {
416 if (vv != NULL && PyInt_Check(vv)) {
417 long val = PyInt_AsLong(vv);
418 if (val < 0) {
419 PyErr_SetString(PyExc_OverflowError,
420 "can't convert negative value "
421 "to unsigned long");
422 return (unsigned long) -1;
423 }
424 return val;
425 }
426 PyErr_BadInternalCall();
427 return (unsigned long) -1;
428 }
429 v = (PyLongObject *)vv;
430 i = Py_SIZE(v);
431 x = 0;
432 if (i < 0) {
433 PyErr_SetString(PyExc_OverflowError,
434 "can't convert negative value to unsigned long");
435 return (unsigned long) -1;
436 }
437 while (--i >= 0) {
438 prev = x;
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;
444 }
445 }
446 return x;
447 }
448
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. */
451
452 unsigned long
PyLong_AsUnsignedLongMask(PyObject * vv)453 PyLong_AsUnsignedLongMask(PyObject *vv)
454 {
455 register PyLongObject *v;
456 unsigned long x;
457 Py_ssize_t i;
458 int sign;
459
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;
465 }
466 v = (PyLongObject *)vv;
467 i = v->ob_size;
468 sign = 1;
469 x = 0;
470 if (i < 0) {
471 sign = -1;
472 i = -i;
473 }
474 while (--i >= 0) {
475 x = (x << PyLong_SHIFT) | v->ob_digit[i];
476 }
477 return x * sign;
478 }
479
480 int
_PyLong_Sign(PyObject * vv)481 _PyLong_Sign(PyObject *vv)
482 {
483 PyLongObject *v = (PyLongObject *)vv;
484
485 assert(v != NULL);
486 assert(PyLong_Check(v));
487
488 return Py_SIZE(v) == 0 ? 0 : (Py_SIZE(v) < 0 ? -1 : 1);
489 }
490
491 size_t
_PyLong_NumBits(PyObject * vv)492 _PyLong_NumBits(PyObject *vv)
493 {
494 PyLongObject *v = (PyLongObject *)vv;
495 size_t result = 0;
496 Py_ssize_t ndigits;
497
498 assert(v != NULL);
499 assert(PyLong_Check(v));
500 ndigits = ABS(Py_SIZE(v));
501 assert(ndigits == 0 || v->ob_digit[ndigits - 1] != 0);
502 if (ndigits > 0) {
503 digit msd = v->ob_digit[ndigits - 1];
504
505 result = (ndigits - 1) * PyLong_SHIFT;
506 if (result / PyLong_SHIFT != (size_t)(ndigits - 1))
507 goto Overflow;
508 do {
509 ++result;
510 if (result == 0)
511 goto Overflow;
512 msd >>= 1;
513 } while (msd);
514 }
515 return result;
516
517 Overflow:
518 PyErr_SetString(PyExc_OverflowError, "long has too many bits "
519 "to express in a platform size_t");
520 return (size_t)-1;
521 }
522
523 PyObject *
_PyLong_FromByteArray(const unsigned char * bytes,size_t n,int little_endian,int is_signed)524 _PyLong_FromByteArray(const unsigned char* bytes, size_t n,
525 int little_endian, int is_signed)
526 {
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 */
534
535 if (n == 0)
536 return PyLong_FromLong(0L);
537
538 if (little_endian) {
539 pstartbyte = bytes;
540 pendbyte = bytes + n - 1;
541 incr = 1;
542 }
543 else {
544 pstartbyte = bytes + n - 1;
545 pendbyte = bytes;
546 incr = -1;
547 }
548
549 if (is_signed)
550 is_signed = *pendbyte >= 0x80;
551
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. */
555 {
556 size_t i;
557 const unsigned char* p = pendbyte;
558 const int pincr = -incr; /* search MSB to LSB */
559 const unsigned char insignificant = is_signed ? 0xff : 0x00;
560
561 for (i = 0; i < n; ++i, p += pincr) {
562 if (*p != insignificant)
563 break;
564 }
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;
573 }
574
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");
582 return NULL;
583 }
584 ndigits = (numsignificantbytes * 8 + PyLong_SHIFT - 1) / PyLong_SHIFT;
585 v = _PyLong_New(ndigits);
586 if (v == NULL)
587 return NULL;
588
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.*/
592 {
593 size_t i;
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;
598
599 for (i = 0; i < numsignificantbytes; ++i, p += incr) {
600 twodigits thisbyte = *p;
601 /* Compute correction for 2's comp, if needed. */
602 if (is_signed) {
603 thisbyte = (0xff ^ thisbyte) + carry;
604 carry = thisbyte >> 8;
605 thisbyte &= 0xff;
606 }
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;
611 accumbits += 8;
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);
616 ++idigit;
617 accum >>= PyLong_SHIFT;
618 accumbits -= PyLong_SHIFT;
619 assert(accumbits < PyLong_SHIFT);
620 }
621 }
622 assert(accumbits < PyLong_SHIFT);
623 if (accumbits) {
624 assert(idigit < ndigits);
625 v->ob_digit[idigit] = (digit)accum;
626 ++idigit;
627 }
628 }
629
630 Py_SIZE(v) = is_signed ? -idigit : idigit;
631 return (PyObject *)long_normalize(v);
632 }
633
634 int
_PyLong_AsByteArray(PyLongObject * v,unsigned char * bytes,size_t n,int little_endian,int is_signed)635 _PyLong_AsByteArray(PyLongObject* v,
636 unsigned char* bytes, size_t n,
637 int little_endian, int is_signed)
638 {
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 */
648
649 assert(v != NULL && PyLong_Check(v));
650
651 if (Py_SIZE(v) < 0) {
652 ndigits = -(Py_SIZE(v));
653 if (!is_signed) {
654 PyErr_SetString(PyExc_OverflowError,
655 "can't convert negative long to unsigned");
656 return -1;
657 }
658 do_twos_comp = 1;
659 }
660 else {
661 ndigits = Py_SIZE(v);
662 do_twos_comp = 0;
663 }
664
665 if (little_endian) {
666 p = bytes;
667 pincr = 1;
668 }
669 else {
670 p = bytes + n - 1;
671 pincr = -1;
672 }
673
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
677 normalized. */
678 assert(ndigits == 0 || v->ob_digit[ndigits - 1] != 0);
679 j = 0;
680 accum = 0;
681 accumbits = 0;
682 carry = do_twos_comp ? 1 : 0;
683 for (i = 0; i < ndigits; ++i) {
684 digit thisdigit = v->ob_digit[i];
685 if (do_twos_comp) {
686 thisdigit = (thisdigit ^ PyLong_MASK) + carry;
687 carry = thisdigit >> PyLong_SHIFT;
688 thisdigit &= PyLong_MASK;
689 }
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;
694
695 /* The most-significant digit may be (probably is) at least
696 partly empty. */
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;
702 while (s != 0) {
703 s >>= 1;
704 accumbits++;
705 }
706 }
707 else
708 accumbits += PyLong_SHIFT;
709
710 /* Store as many bytes as possible. */
711 while (accumbits >= 8) {
712 if (j >= n)
713 goto Overflow;
714 ++j;
715 *p = (unsigned char)(accum & 0xff);
716 p += pincr;
717 accumbits -= 8;
718 accum >>= 8;
719 }
720 }
721
722 /* Store the straggler (if any). */
723 assert(accumbits < 8);
724 assert(carry == 0); /* else do_twos_comp and *every* digit was 0 */
725 if (accumbits > 0) {
726 if (j >= n)
727 goto Overflow;
728 ++j;
729 if (do_twos_comp) {
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;
734 }
735 *p = (unsigned char)(accum & 0xff);
736 p += pincr;
737 }
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
742 exists. */
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)
747 return 0;
748 else
749 goto Overflow;
750 }
751
752 /* Fill remaining bytes with copies of the sign bit. */
753 {
754 unsigned char signbyte = do_twos_comp ? 0xffU : 0U;
755 for ( ; j < n; ++j, p += pincr)
756 *p = signbyte;
757 }
758
759 return 0;
760
761 Overflow:
762 PyErr_SetString(PyExc_OverflowError, "long too big to convert");
763 return -1;
764
765 }
766
767 /* Create a new long (or int) object from a C pointer */
768
769 PyObject *
PyLong_FromVoidPtr(void * p)770 PyLong_FromVoidPtr(void *p)
771 {
772 #if SIZEOF_VOID_P <= SIZEOF_LONG
773 if ((long)p < 0)
774 return PyLong_FromUnsignedLong((unsigned long)p);
775 return PyInt_FromLong((long)p);
776 #else
777
778 #ifndef HAVE_LONG_LONG
779 # error "PyLong_FromVoidPtr: sizeof(void*) > sizeof(long), but no long long"
780 #endif
781 #if SIZEOF_LONG_LONG < SIZEOF_VOID_P
782 # error "PyLong_FromVoidPtr: sizeof(PY_LONG_LONG) < sizeof(void*)"
783 #endif
784 /* optimize null pointers */
785 if (p == NULL)
786 return PyInt_FromLong(0);
787 return PyLong_FromUnsignedLongLong((unsigned PY_LONG_LONG)p);
788
789 #endif /* SIZEOF_VOID_P <= SIZEOF_LONG */
790 }
791
792 /* Get a C pointer from a long object (or an int object in some cases) */
793
794 void *
PyLong_AsVoidPtr(PyObject * vv)795 PyLong_AsVoidPtr(PyObject *vv)
796 {
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"
800 */
801 #if SIZEOF_VOID_P <= SIZEOF_LONG
802 long x;
803
804 if (PyInt_Check(vv))
805 x = PyInt_AS_LONG(vv);
806 else if (PyLong_Check(vv) && _PyLong_Sign(vv) < 0)
807 x = PyLong_AsLong(vv);
808 else
809 x = PyLong_AsUnsignedLong(vv);
810 #else
811
812 #ifndef HAVE_LONG_LONG
813 # error "PyLong_AsVoidPtr: sizeof(void*) > sizeof(long), but no long long"
814 #endif
815 #if SIZEOF_LONG_LONG < SIZEOF_VOID_P
816 # error "PyLong_AsVoidPtr: sizeof(PY_LONG_LONG) < sizeof(void*)"
817 #endif
818 PY_LONG_LONG x;
819
820 if (PyInt_Check(vv))
821 x = PyInt_AS_LONG(vv);
822 else if (PyLong_Check(vv) && _PyLong_Sign(vv) < 0)
823 x = PyLong_AsLongLong(vv);
824 else
825 x = PyLong_AsUnsignedLongLong(vv);
826
827 #endif /* SIZEOF_VOID_P <= SIZEOF_LONG */
828
829 if (x == -1 && PyErr_Occurred())
830 return NULL;
831 return (void *)x;
832 }
833
834 #ifdef HAVE_LONG_LONG
835
836 /* Initial PY_LONG_LONG support by Chris Herborth (chrish@qnx.com), later
837 * rewritten to use the newer PyLong_{As,From}ByteArray API.
838 */
839
840 #define IS_LITTLE_ENDIAN (int)*(unsigned char*)&one
841 #define PY_ABS_LLONG_MIN (0-(unsigned PY_LONG_LONG)PY_LLONG_MIN)
842
843 /* Create a new long int object from a C PY_LONG_LONG int. */
844
845 PyObject *
PyLong_FromLongLong(PY_LONG_LONG ival)846 PyLong_FromLongLong(PY_LONG_LONG ival)
847 {
848 PyLongObject *v;
849 unsigned PY_LONG_LONG abs_ival;
850 unsigned PY_LONG_LONG t; /* unsigned so >> doesn't propagate sign bit */
851 int ndigits = 0;
852 int negative = 0;
853
854 if (ival < 0) {
855 /* avoid signed overflow on negation; see comments
856 in PyLong_FromLong above. */
857 abs_ival = (unsigned PY_LONG_LONG)(-1-ival) + 1;
858 negative = 1;
859 }
860 else {
861 abs_ival = (unsigned PY_LONG_LONG)ival;
862 }
863
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
867 needed. */
868 t = abs_ival;
869 while (t) {
870 ++ndigits;
871 t >>= PyLong_SHIFT;
872 }
873 v = _PyLong_New(ndigits);
874 if (v != NULL) {
875 digit *p = v->ob_digit;
876 Py_SIZE(v) = negative ? -ndigits : ndigits;
877 t = abs_ival;
878 while (t) {
879 *p++ = (digit)(t & PyLong_MASK);
880 t >>= PyLong_SHIFT;
881 }
882 }
883 return (PyObject *)v;
884 }
885
886 /* Create a new long int object from a C unsigned PY_LONG_LONG int. */
887
888 PyObject *
PyLong_FromUnsignedLongLong(unsigned PY_LONG_LONG ival)889 PyLong_FromUnsignedLongLong(unsigned PY_LONG_LONG ival)
890 {
891 PyLongObject *v;
892 unsigned PY_LONG_LONG t;
893 int ndigits = 0;
894
895 /* Count the number of Python digits. */
896 t = (unsigned PY_LONG_LONG)ival;
897 while (t) {
898 ++ndigits;
899 t >>= PyLong_SHIFT;
900 }
901 v = _PyLong_New(ndigits);
902 if (v != NULL) {
903 digit *p = v->ob_digit;
904 Py_SIZE(v) = ndigits;
905 while (ival) {
906 *p++ = (digit)(ival & PyLong_MASK);
907 ival >>= PyLong_SHIFT;
908 }
909 }
910 return (PyObject *)v;
911 }
912
913 /* Create a new long int object from a C Py_ssize_t. */
914
915 PyObject *
PyLong_FromSsize_t(Py_ssize_t ival)916 PyLong_FromSsize_t(Py_ssize_t ival)
917 {
918 Py_ssize_t bytes = ival;
919 int one = 1;
920 return _PyLong_FromByteArray((unsigned char *)&bytes,
921 SIZEOF_SIZE_T, IS_LITTLE_ENDIAN, 1);
922 }
923
924 /* Create a new long int object from a C size_t. */
925
926 PyObject *
PyLong_FromSize_t(size_t ival)927 PyLong_FromSize_t(size_t ival)
928 {
929 size_t bytes = ival;
930 int one = 1;
931 return _PyLong_FromByteArray((unsigned char *)&bytes,
932 SIZEOF_SIZE_T, IS_LITTLE_ENDIAN, 0);
933 }
934
935 /* Get a C PY_LONG_LONG int from a long int object.
936 Return -1 and set an error if overflow occurs. */
937
938 PY_LONG_LONG
PyLong_AsLongLong(PyObject * vv)939 PyLong_AsLongLong(PyObject *vv)
940 {
941 PY_LONG_LONG bytes;
942 int one = 1;
943 int res;
944
945 if (vv == NULL) {
946 PyErr_BadInternalCall();
947 return -1;
948 }
949 if (!PyLong_Check(vv)) {
950 PyNumberMethods *nb;
951 PyObject *io;
952 if (PyInt_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");
957 return -1;
958 }
959 io = (*nb->nb_int) (vv);
960 if (io == NULL)
961 return -1;
962 if (PyInt_Check(io)) {
963 bytes = PyInt_AsLong(io);
964 Py_DECREF(io);
965 return bytes;
966 }
967 if (PyLong_Check(io)) {
968 bytes = PyLong_AsLongLong(io);
969 Py_DECREF(io);
970 return bytes;
971 }
972 Py_DECREF(io);
973 PyErr_SetString(PyExc_TypeError, "integer conversion failed");
974 return -1;
975 }
976
977 res = _PyLong_AsByteArray((PyLongObject *)vv, (unsigned char *)&bytes,
978 SIZEOF_LONG_LONG, IS_LITTLE_ENDIAN, 1);
979
980 /* Plan 9 can't handle PY_LONG_LONG in ? : expressions */
981 if (res < 0)
982 return (PY_LONG_LONG)-1;
983 else
984 return bytes;
985 }
986
987 /* Get a C unsigned PY_LONG_LONG int from a long int object.
988 Return -1 and set an error if overflow occurs. */
989
990 unsigned PY_LONG_LONG
PyLong_AsUnsignedLongLong(PyObject * vv)991 PyLong_AsUnsignedLongLong(PyObject *vv)
992 {
993 unsigned PY_LONG_LONG bytes;
994 int one = 1;
995 int res;
996
997 if (vv == NULL || !PyLong_Check(vv)) {
998 PyErr_BadInternalCall();
999 return (unsigned PY_LONG_LONG)-1;
1000 }
1001
1002 res = _PyLong_AsByteArray((PyLongObject *)vv, (unsigned char *)&bytes,
1003 SIZEOF_LONG_LONG, IS_LITTLE_ENDIAN, 0);
1004
1005 /* Plan 9 can't handle PY_LONG_LONG in ? : expressions */
1006 if (res < 0)
1007 return (unsigned PY_LONG_LONG)res;
1008 else
1009 return bytes;
1010 }
1011
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. */
1014
1015 unsigned PY_LONG_LONG
PyLong_AsUnsignedLongLongMask(PyObject * vv)1016 PyLong_AsUnsignedLongLongMask(PyObject *vv)
1017 {
1018 register PyLongObject *v;
1019 unsigned PY_LONG_LONG x;
1020 Py_ssize_t i;
1021 int sign;
1022
1023 if (vv == NULL || !PyLong_Check(vv)) {
1024 PyErr_BadInternalCall();
1025 return (unsigned long) -1;
1026 }
1027 v = (PyLongObject *)vv;
1028 i = v->ob_size;
1029 sign = 1;
1030 x = 0;
1031 if (i < 0) {
1032 sign = -1;
1033 i = -i;
1034 }
1035 while (--i >= 0) {
1036 x = (x << PyLong_SHIFT) | v->ob_digit[i];
1037 }
1038 return x * sign;
1039 }
1040
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.
1044
1045 For other errors (e.g., type error), returns -1 and sets an error
1046 condition.
1047 */
1048
1049 PY_LONG_LONG
PyLong_AsLongLongAndOverflow(PyObject * vv,int * overflow)1050 PyLong_AsLongLongAndOverflow(PyObject *vv, int *overflow)
1051 {
1052 /* This version by Tim Peters */
1053 register PyLongObject *v;
1054 unsigned PY_LONG_LONG x, prev;
1055 PY_LONG_LONG res;
1056 Py_ssize_t i;
1057 int sign;
1058 int do_decref = 0; /* if nb_int was called */
1059
1060 *overflow = 0;
1061 if (vv == NULL) {
1062 PyErr_BadInternalCall();
1063 return -1;
1064 }
1065
1066 if (PyInt_Check(vv))
1067 return PyInt_AsLong(vv);
1068
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");
1075 return -1;
1076 }
1077 vv = (*nb->nb_int) (vv);
1078 if (vv == NULL)
1079 return -1;
1080 do_decref = 1;
1081 if(PyInt_Check(vv)) {
1082 res = PyInt_AsLong(vv);
1083 goto exit;
1084 }
1085 if (!PyLong_Check(vv)) {
1086 Py_DECREF(vv);
1087 PyErr_SetString(PyExc_TypeError,
1088 "nb_int should return int object");
1089 return -1;
1090 }
1091 }
1092
1093 res = -1;
1094 v = (PyLongObject *)vv;
1095 i = Py_SIZE(v);
1096
1097 switch (i) {
1098 case -1:
1099 res = -(sdigit)v->ob_digit[0];
1100 break;
1101 case 0:
1102 res = 0;
1103 break;
1104 case 1:
1105 res = v->ob_digit[0];
1106 break;
1107 default:
1108 sign = 1;
1109 x = 0;
1110 if (i < 0) {
1111 sign = -1;
1112 i = -(i);
1113 }
1114 while (--i >= 0) {
1115 prev = x;
1116 x = (x << PyLong_SHIFT) + v->ob_digit[i];
1117 if ((x >> PyLong_SHIFT) != prev) {
1118 *overflow = sign;
1119 goto exit;
1120 }
1121 }
1122 /* Haven't lost any bits, but casting to long requires extra
1123 * care (see comment above).
1124 */
1125 if (x <= (unsigned PY_LONG_LONG)PY_LLONG_MAX) {
1126 res = (PY_LONG_LONG)x * sign;
1127 }
1128 else if (sign < 0 && x == PY_ABS_LLONG_MIN) {
1129 res = PY_LLONG_MIN;
1130 }
1131 else {
1132 *overflow = sign;
1133 /* res is already set to -1 */
1134 }
1135 }
1136 exit:
1137 if (do_decref) {
1138 Py_DECREF(vv);
1139 }
1140 return res;
1141 }
1142
1143 #undef IS_LITTLE_ENDIAN
1144
1145 #endif /* HAVE_LONG_LONG */
1146
1147
1148 static int
convert_binop(PyObject * v,PyObject * w,PyLongObject ** a,PyLongObject ** b)1149 convert_binop(PyObject *v, PyObject *w, PyLongObject **a, PyLongObject **b) {
1150 if (PyLong_Check(v)) {
1151 *a = (PyLongObject *) v;
1152 Py_INCREF(v);
1153 }
1154 else if (PyInt_Check(v)) {
1155 *a = (PyLongObject *) PyLong_FromLong(PyInt_AS_LONG(v));
1156 }
1157 else {
1158 return 0;
1159 }
1160 if (PyLong_Check(w)) {
1161 *b = (PyLongObject *) w;
1162 Py_INCREF(w);
1163 }
1164 else if (PyInt_Check(w)) {
1165 *b = (PyLongObject *) PyLong_FromLong(PyInt_AS_LONG(w));
1166 }
1167 else {
1168 Py_DECREF(*a);
1169 return 0;
1170 }
1171 return 1;
1172 }
1173
1174 #define CONVERT_BINOP(v, w, a, b) \
1175 do { \
1176 if (!convert_binop(v, w, a, b)) { \
1177 Py_INCREF(Py_NotImplemented); \
1178 return Py_NotImplemented; \
1179 } \
1180 } while(0) \
1181
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. */
1184
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
1188 };
1189
1190 static int
bits_in_digit(digit d)1191 bits_in_digit(digit d)
1192 {
1193 int d_bits = 0;
1194 while (d >= 32) {
1195 d_bits += 6;
1196 d >>= 6;
1197 }
1198 d_bits += (int)BitLengthTable[d];
1199 return d_bits;
1200 }
1201
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.
1205 */
1206 static digit
v_iadd(digit * x,Py_ssize_t m,digit * y,Py_ssize_t n)1207 v_iadd(digit *x, Py_ssize_t m, digit *y, Py_ssize_t n)
1208 {
1209 Py_ssize_t i;
1210 digit carry = 0;
1211
1212 assert(m >= 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);
1218 }
1219 for (; carry && i < m; ++i) {
1220 carry += x[i];
1221 x[i] = carry & PyLong_MASK;
1222 carry >>= PyLong_SHIFT;
1223 assert((carry & 1) == carry);
1224 }
1225 return carry;
1226 }
1227
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.
1231 */
1232 static digit
v_isub(digit * x,Py_ssize_t m,digit * y,Py_ssize_t n)1233 v_isub(digit *x, Py_ssize_t m, digit *y, Py_ssize_t n)
1234 {
1235 Py_ssize_t i;
1236 digit borrow = 0;
1237
1238 assert(m >= 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 */
1244 }
1245 for (; borrow && i < m; ++i) {
1246 borrow = x[i] - borrow;
1247 x[i] = borrow & PyLong_MASK;
1248 borrow >>= PyLong_SHIFT;
1249 borrow &= 1;
1250 }
1251 return borrow;
1252 }
1253
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.
1256 */
1257 static digit
v_lshift(digit * z,digit * a,Py_ssize_t m,int d)1258 v_lshift(digit *z, digit *a, Py_ssize_t m, int d)
1259 {
1260 Py_ssize_t i;
1261 digit carry = 0;
1262
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);
1268 }
1269 return carry;
1270 }
1271
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.
1274 */
1275 static digit
v_rshift(digit * z,digit * a,Py_ssize_t m,int d)1276 v_rshift(digit *z, digit *a, Py_ssize_t m, int d)
1277 {
1278 Py_ssize_t i;
1279 digit carry = 0;
1280 digit mask = ((digit)1 << d) - 1U;
1281
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);
1287 }
1288 return carry;
1289 }
1290
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
1295 immutable. */
1296
1297 static digit
inplace_divrem1(digit * pout,digit * pin,Py_ssize_t size,digit n)1298 inplace_divrem1(digit *pout, digit *pin, Py_ssize_t size, digit n)
1299 {
1300 twodigits rem = 0;
1301
1302 assert(n > 0 && n <= PyLong_MASK);
1303 pin += size;
1304 pout += size;
1305 while (--size >= 0) {
1306 digit hi;
1307 rem = (rem << PyLong_SHIFT) | *--pin;
1308 *--pout = hi = (digit)(rem / n);
1309 rem -= (twodigits)hi * n;
1310 }
1311 return (digit)rem;
1312 }
1313
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. */
1317
1318 static PyLongObject *
divrem1(PyLongObject * a,digit n,digit * prem)1319 divrem1(PyLongObject *a, digit n, digit *prem)
1320 {
1321 const Py_ssize_t size = ABS(Py_SIZE(a));
1322 PyLongObject *z;
1323
1324 assert(n > 0 && n <= PyLong_MASK);
1325 z = _PyLong_New(size);
1326 if (z == NULL)
1327 return NULL;
1328 *prem = inplace_divrem1(z->ob_digit, a->ob_digit, size, n);
1329 return long_normalize(z);
1330 }
1331
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.) */
1335
1336 static PyObject *
long_to_decimal_string(PyObject * aa,int addL)1337 long_to_decimal_string(PyObject *aa, int addL)
1338 {
1339 PyLongObject *scratch, *a;
1340 PyObject *str;
1341 Py_ssize_t size, strlen, size_a, i, j;
1342 digit *pout, *pin, rem, tenpow;
1343 char *p;
1344 int negative;
1345
1346 a = (PyLongObject *)aa;
1347 if (a == NULL || !PyLong_Check(a)) {
1348 PyErr_BadInternalCall();
1349 return NULL;
1350 }
1351 size_a = ABS(Py_SIZE(a));
1352 negative = Py_SIZE(a) < 0;
1353
1354 /* quick and dirty upper bound for the number of digits
1355 required to express a in base _PyLong_DECIMAL_BASE:
1356
1357 #digits = 1 + floor(log2(a) / log2(_PyLong_DECIMAL_BASE))
1358
1359 But log2(a) < size_a * PyLong_SHIFT, and
1360 log2(_PyLong_DECIMAL_BASE) = log2(10) * _PyLong_DECIMAL_SHIFT
1361 > 3 * _PyLong_DECIMAL_SHIFT
1362 */
1363 if (size_a > PY_SSIZE_T_MAX / PyLong_SHIFT) {
1364 PyErr_SetString(PyExc_OverflowError,
1365 "long is too large to format");
1366 return NULL;
1367 }
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)
1372 return NULL;
1373
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). */
1377 pin = a->ob_digit;
1378 pout = scratch->ob_digit;
1379 size = 0;
1380 for (i = size_a; --i >= 0; ) {
1381 digit hi = pin[i];
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);
1387 }
1388 while (hi) {
1389 pout[size++] = hi % _PyLong_DECIMAL_BASE;
1390 hi /= _PyLong_DECIMAL_BASE;
1391 }
1392 /* check for keyboard interrupt */
1393 SIGCHECK({
1394 Py_DECREF(scratch);
1395 return NULL;
1396 });
1397 }
1398 /* pout should have at least one digit, so that the case when a = 0
1399 works correctly */
1400 if (size == 0)
1401 pout[size++] = 0;
1402
1403 /* calculate exact length of output string, and allocate */
1404 strlen = (addL != 0) + negative +
1405 1 + (size - 1) * _PyLong_DECIMAL_SHIFT;
1406 tenpow = 10;
1407 rem = pout[size-1];
1408 while (rem >= tenpow) {
1409 tenpow *= 10;
1410 strlen++;
1411 }
1412 str = PyString_FromStringAndSize(NULL, strlen);
1413 if (str == NULL) {
1414 Py_DECREF(scratch);
1415 return NULL;
1416 }
1417
1418 /* fill the string right-to-left */
1419 p = PyString_AS_STRING(str) + strlen;
1420 *p = '\0';
1421 if (addL)
1422 *--p = 'L';
1423 /* pout[0] through pout[size-2] contribute exactly
1424 _PyLong_DECIMAL_SHIFT digits each */
1425 for (i=0; i < size - 1; i++) {
1426 rem = pout[i];
1427 for (j = 0; j < _PyLong_DECIMAL_SHIFT; j++) {
1428 *--p = '0' + rem % 10;
1429 rem /= 10;
1430 }
1431 }
1432 /* pout[size-1]: always produce at least one decimal digit */
1433 rem = pout[i];
1434 do {
1435 *--p = '0' + rem % 10;
1436 rem /= 10;
1437 } while (rem != 0);
1438
1439 /* and sign */
1440 if (negative)
1441 *--p = '-';
1442
1443 /* check we've counted correctly */
1444 assert(p == PyString_AS_STRING(str));
1445 Py_DECREF(scratch);
1446 return (PyObject *)str;
1447 }
1448
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 *)
_PyLong_Format(PyObject * aa,int base,int addL,int newstyle)1455 _PyLong_Format(PyObject *aa, int base, int addL, int newstyle)
1456 {
1457 register PyLongObject *a = (PyLongObject *)aa;
1458 PyStringObject *str;
1459 Py_ssize_t i, sz;
1460 Py_ssize_t size_a;
1461 char *p;
1462 int bits;
1463 char sign = '\0';
1464
1465 if (base == 10)
1466 return long_to_decimal_string((PyObject *)a, addL);
1467
1468 if (a == NULL || !PyLong_Check(a)) {
1469 PyErr_BadInternalCall();
1470 return NULL;
1471 }
1472 assert(base >= 2 && base <= 36);
1473 size_a = ABS(Py_SIZE(a));
1474
1475 /* Compute a rough upper bound for the length of the string */
1476 i = base;
1477 bits = 0;
1478 while (i > 1) {
1479 ++bits;
1480 i >>= 1;
1481 }
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");
1487 return NULL;
1488 }
1489 sz = i + 1 + (size_a * PyLong_SHIFT - 1) / bits;
1490 assert(sz >= 0);
1491 str = (PyStringObject *) PyString_FromStringAndSize((char *)0, sz);
1492 if (str == NULL)
1493 return NULL;
1494 p = PyString_AS_STRING(str) + sz;
1495 *p = '\0';
1496 if (addL)
1497 *--p = 'L';
1498 if (a->ob_size < 0)
1499 sign = '-';
1500
1501 if (a->ob_size == 0) {
1502 *--p = '0';
1503 }
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 */
1509 i = base;
1510 while ((i >>= 1) > 1)
1511 ++basebits;
1512
1513 for (i = 0; i < size_a; ++i) {
1514 accum |= (twodigits)a->ob_digit[i] << accumbits;
1515 accumbits += PyLong_SHIFT;
1516 assert(accumbits >= basebits);
1517 do {
1518 char cdigit = (char)(accum & (base - 1));
1519 cdigit += (cdigit < 10) ? '0' : 'a'-10;
1520 assert(p > PyString_AS_STRING(str));
1521 *--p = cdigit;
1522 accumbits -= basebits;
1523 accum >>= basebits;
1524 } while (i < size_a-1 ? accumbits >= basebits : accum > 0);
1525 }
1526 }
1527 else {
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
1530 fits in a digit. */
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 */
1536 int power = 1;
1537 for (;;) {
1538 twodigits newpow = powbase * (twodigits)base;
1539 if (newpow >> PyLong_SHIFT)
1540 /* doesn't fit in a digit */
1541 break;
1542 powbase = (digit)newpow;
1543 ++power;
1544 }
1545
1546 /* Get a scratch area for repeated division. */
1547 scratch = _PyLong_New(size);
1548 if (scratch == NULL) {
1549 Py_DECREF(str);
1550 return NULL;
1551 }
1552
1553 /* Repeatedly divide by powbase. */
1554 do {
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)
1560 --size;
1561 SIGCHECK({
1562 Py_DECREF(scratch);
1563 Py_DECREF(str);
1564 return NULL;
1565 });
1566
1567 /* Break rem into digits. */
1568 assert(ntostore > 0);
1569 do {
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;
1574 *--p = c;
1575 rem = nextrem;
1576 --ntostore;
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);
1582 Py_DECREF(scratch);
1583 }
1584
1585 if (base == 2) {
1586 *--p = 'b';
1587 *--p = '0';
1588 }
1589 else if (base == 8) {
1590 if (newstyle) {
1591 *--p = 'o';
1592 *--p = '0';
1593 }
1594 else
1595 if (size_a != 0)
1596 *--p = '0';
1597 }
1598 else if (base == 16) {
1599 *--p = 'x';
1600 *--p = '0';
1601 }
1602 else if (base != 10) {
1603 *--p = '#';
1604 *--p = '0' + base%10;
1605 if (base > 10)
1606 *--p = '0' + base/10;
1607 }
1608 if (sign)
1609 *--p = sign;
1610 if (p != PyString_AS_STRING(str)) {
1611 char *q = PyString_AS_STRING(str);
1612 assert(p > q);
1613 do {
1614 } while ((*q++ = *p++) != '\0');
1615 q--;
1616 _PyString_Resize((PyObject **)&str,
1617 (Py_ssize_t) (q - PyString_AS_STRING(str)));
1618 }
1619 return (PyObject *)str;
1620 }
1621
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.
1628 */
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,
1646 };
1647
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.
1653 */
1654 static PyLongObject *
long_from_binary_base(char ** str,int base)1655 long_from_binary_base(char **str, int base)
1656 {
1657 char *p = *str;
1658 char *start = p;
1659 int bits_per_char;
1660 Py_ssize_t n;
1661 PyLongObject *z;
1662 twodigits accum;
1663 int bits_in_accum;
1664 digit *pdigit;
1665
1666 assert(base >= 2 && base <= 32 && (base & (base - 1)) == 0);
1667 n = base;
1668 for (bits_per_char = -1; n; ++bits_per_char)
1669 n >>= 1;
1670 /* n <- total # of bits needed, while setting p to end-of-string */
1671 while (_PyLong_DigitValue[Py_CHARMASK(*p)] < base)
1672 ++p;
1673 *str = p;
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");
1679 return NULL;
1680 }
1681 n = n / PyLong_SHIFT;
1682 z = _PyLong_New(n);
1683 if (z == NULL)
1684 return NULL;
1685 /* Read string from right, and fill in long from left; i.e.,
1686 * from least to most significant in both.
1687 */
1688 accum = 0;
1689 bits_in_accum = 0;
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);
1702 }
1703 }
1704 if (bits_in_accum) {
1705 assert(bits_in_accum <= PyLong_SHIFT);
1706 *pdigit++ = (digit)accum;
1707 assert(pdigit - z->ob_digit <= n);
1708 }
1709 while (pdigit - z->ob_digit < n)
1710 *pdigit++ = 0;
1711 return long_normalize(z);
1712 }
1713
1714 PyObject *
PyLong_FromString(char * str,char ** pend,int base)1715 PyLong_FromString(char *str, char **pend, int base)
1716 {
1717 int sign = 1;
1718 char *start, *orig_str = str;
1719 PyLongObject *z;
1720 PyObject *strobj, *strrepr;
1721 Py_ssize_t slen;
1722
1723 if ((base != 0 && base < 2) || base > 36) {
1724 PyErr_SetString(PyExc_ValueError,
1725 "long() arg 2 must be >= 2 and <= 36");
1726 return NULL;
1727 }
1728 while (*str != '\0' && isspace(Py_CHARMASK(*str)))
1729 str++;
1730 if (*str == '+')
1731 ++str;
1732 else if (*str == '-') {
1733 ++str;
1734 sign = -1;
1735 }
1736 while (*str != '\0' && isspace(Py_CHARMASK(*str)))
1737 str++;
1738 if (base == 0) {
1739 /* No base given. Deduce the base from the contents
1740 of the string */
1741 if (str[0] != '0')
1742 base = 10;
1743 else if (str[1] == 'x' || str[1] == 'X')
1744 base = 16;
1745 else if (str[1] == 'o' || str[1] == 'O')
1746 base = 8;
1747 else if (str[1] == 'b' || str[1] == 'B')
1748 base = 2;
1749 else
1750 /* "old" (C-style) octal literal, still valid in
1751 2.x, although illegal in 3.x */
1752 base = 8;
1753 }
1754 /* Whether or not we were deducing the base, skip leading chars
1755 as needed */
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'))))
1760 str += 2;
1761
1762 start = str;
1763 if ((base & (base - 1)) == 0)
1764 z = long_from_binary_base(&str, base);
1765 else {
1766 /***
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.
1770
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.
1774
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)
1778
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.
1782
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:
1785
1786 convwidth_base[base] = the largest integer i such that
1787 base**i <= PyLong_BASE
1788 convmultmax_base[base] = base ** convwidth_base[base]
1789
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.
1793
1794 Viewing the input as a sequence <c0, c1, ..., c_n-1> of digits in base
1795 convmultmax_base[base], the result is "simply"
1796
1797 (((c0*B + c1)*B + c2)*B + c3)*B + ... ))) + c_n-1
1798
1799 where B = convmultmax_base[base].
1800
1801 Error analysis: as above, the number of Python digits `n` needed is worst-
1802 case
1803
1804 n >= N * log(B)/log(PyLong_BASE)
1805
1806 where `N` is the number of input digits in base `B`. This is computed via
1807
1808 size_z = (Py_ssize_t)((scan - str) * log_base_PyLong_BASE[base]) + 1;
1809
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).
1813
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).
1825
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
1838 indeed:
1839
1840 >>> log(10)/log(2**15)*76573
1841 16958.000000654003
1842
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.
1852 ***/
1853 register twodigits c; /* current input character */
1854 Py_ssize_t size_z;
1855 int i;
1856 int convwidth;
1857 twodigits convmultmax, convmult;
1858 digit *pz, *pzstop;
1859 char* scan;
1860
1861 static double log_base_PyLong_BASE[37] = {0.0e0,};
1862 static int convwidth_base[37] = {0,};
1863 static twodigits convmultmax_base[37] = {0,};
1864
1865 if (log_base_PyLong_BASE[base] == 0.0) {
1866 twodigits convmax = base;
1867 int i = 1;
1868
1869 log_base_PyLong_BASE[base] = (log((double)base) /
1870 log((double)PyLong_BASE));
1871 for (;;) {
1872 twodigits next = convmax * base;
1873 if (next > PyLong_BASE)
1874 break;
1875 convmax = next;
1876 ++i;
1877 }
1878 convmultmax_base[base] = convmax;
1879 assert(i > 0);
1880 convwidth_base[base] = i;
1881 }
1882
1883 /* Find length of the string of numeric characters. */
1884 scan = str;
1885 while (_PyLong_DigitValue[Py_CHARMASK(*scan)] < base)
1886 ++scan;
1887
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.
1892 */
1893 size_z = (Py_ssize_t)((scan - str) * log_base_PyLong_BASE[base]) + 1;
1894 /* Uncomment next line to test exceedingly rare copy code */
1895 /* size_z = 1; */
1896 assert(size_z > 0);
1897 z = _PyLong_New(size_z);
1898 if (z == NULL)
1899 return NULL;
1900 Py_SIZE(z) = 0;
1901
1902 /* `convwidth` consecutive input digits are treated as a single
1903 * digit in base `convmultmax`.
1904 */
1905 convwidth = convwidth_base[base];
1906 convmultmax = convmultmax_base[base];
1907
1908 /* Work ;-) */
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);
1916 }
1917
1918 convmult = convmultmax;
1919 /* Calculate the shift only if we couldn't get
1920 * convwidth digits.
1921 */
1922 if (i != convwidth) {
1923 convmult = base;
1924 for ( ; i > 1; --i)
1925 convmult *= base;
1926 }
1927
1928 /* Multiply z by convmult, and add c. */
1929 pz = z->ob_digit;
1930 pzstop = pz + Py_SIZE(z);
1931 for (; pz < pzstop; ++pz) {
1932 c += (twodigits)*pz * convmult;
1933 *pz = (digit)(c & PyLong_MASK);
1934 c >>= PyLong_SHIFT;
1935 }
1936 /* carry off the current end? */
1937 if (c) {
1938 assert(c < PyLong_BASE);
1939 if (Py_SIZE(z) < size_z) {
1940 *pz = (digit)c;
1941 ++Py_SIZE(z);
1942 }
1943 else {
1944 PyLongObject *tmp;
1945 /* Extremely rare. Get more space. */
1946 assert(Py_SIZE(z) == size_z);
1947 tmp = _PyLong_New(size_z + 1);
1948 if (tmp == NULL) {
1949 Py_DECREF(z);
1950 return NULL;
1951 }
1952 memcpy(tmp->ob_digit,
1953 z->ob_digit,
1954 sizeof(digit) * size_z);
1955 Py_DECREF(z);
1956 z = tmp;
1957 z->ob_digit[size_z] = (digit)c;
1958 ++size_z;
1959 }
1960 }
1961 }
1962 }
1963 if (z == NULL)
1964 return NULL;
1965 if (str == start)
1966 goto onError;
1967 if (sign < 0)
1968 Py_SIZE(z) = -(Py_SIZE(z));
1969 if (*str == 'L' || *str == 'l')
1970 str++;
1971 while (*str && isspace(Py_CHARMASK(*str)))
1972 str++;
1973 if (*str != '\0')
1974 goto onError;
1975 if (pend)
1976 *pend = str;
1977 return (PyObject *) z;
1978
1979 onError:
1980 Py_XDECREF(z);
1981 slen = strlen(orig_str) < 200 ? strlen(orig_str) : 200;
1982 strobj = PyString_FromStringAndSize(orig_str, slen);
1983 if (strobj == NULL)
1984 return NULL;
1985 strrepr = PyObject_Repr(strobj);
1986 Py_DECREF(strobj);
1987 if (strrepr == NULL)
1988 return NULL;
1989 PyErr_Format(PyExc_ValueError,
1990 "invalid literal for long() with base %d: %s",
1991 base, PyString_AS_STRING(strrepr));
1992 Py_DECREF(strrepr);
1993 return NULL;
1994 }
1995
1996 #ifdef Py_USING_UNICODE
1997 PyObject *
PyLong_FromUnicode(Py_UNICODE * u,Py_ssize_t length,int base)1998 PyLong_FromUnicode(Py_UNICODE *u, Py_ssize_t length, int base)
1999 {
2000 PyObject *result;
2001 char *buffer = (char *)PyMem_MALLOC(length+1);
2002
2003 if (buffer == NULL)
2004 return NULL;
2005
2006 if (PyUnicode_EncodeDecimal(u, length, buffer, NULL)) {
2007 PyMem_FREE(buffer);
2008 return NULL;
2009 }
2010 result = PyLong_FromString(buffer, NULL, base);
2011 PyMem_FREE(buffer);
2012 return result;
2013 }
2014 #endif
2015
2016 /* forward */
2017 static PyLongObject *x_divrem
2018 (PyLongObject *, PyLongObject *, PyLongObject **);
2019 static PyObject *long_long(PyObject *v);
2020
2021 /* Long division with remainder, top-level routine */
2022
2023 static int
long_divrem(PyLongObject * a,PyLongObject * b,PyLongObject ** pdiv,PyLongObject ** prem)2024 long_divrem(PyLongObject *a, PyLongObject *b,
2025 PyLongObject **pdiv, PyLongObject **prem)
2026 {
2027 Py_ssize_t size_a = ABS(Py_SIZE(a)), size_b = ABS(Py_SIZE(b));
2028 PyLongObject *z;
2029
2030 if (size_b == 0) {
2031 PyErr_SetString(PyExc_ZeroDivisionError,
2032 "long division or modulo by zero");
2033 return -1;
2034 }
2035 if (size_a < size_b ||
2036 (size_a == size_b &&
2037 a->ob_digit[size_a-1] < b->ob_digit[size_b-1])) {
2038 /* |a| < |b|. */
2039 *pdiv = _PyLong_New(0);
2040 if (*pdiv == NULL)
2041 return -1;
2042 Py_INCREF(a);
2043 *prem = (PyLongObject *) a;
2044 return 0;
2045 }
2046 if (size_b == 1) {
2047 digit rem = 0;
2048 z = divrem1(a, b->ob_digit[0], &rem);
2049 if (z == NULL)
2050 return -1;
2051 *prem = (PyLongObject *) PyLong_FromLong((long)rem);
2052 if (*prem == NULL) {
2053 Py_DECREF(z);
2054 return -1;
2055 }
2056 }
2057 else {
2058 z = x_divrem(a, b, prem);
2059 if (z == NULL)
2060 return -1;
2061 }
2062 /* Set the signs.
2063 The quotient z has the sign of a*b;
2064 the remainder r has the sign of a,
2065 so a = b*z + r. */
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);
2070 *pdiv = z;
2071 return 0;
2072 }
2073
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)). */
2076
2077 static PyLongObject *
x_divrem(PyLongObject * v1,PyLongObject * w1,PyLongObject ** prem)2078 x_divrem(PyLongObject *v1, PyLongObject *w1, PyLongObject **prem)
2079 {
2080 PyLongObject *v, *w, *a;
2081 Py_ssize_t i, k, size_v, size_w;
2082 int d;
2083 digit wm1, wm2, carry, q, r, vtop, *v0, *vk, *w0, *ak;
2084 twodigits vv;
2085 sdigit zhi;
2086 stwodigits z;
2087
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. */
2093
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);
2099 if (v == NULL) {
2100 *prem = NULL;
2101 return NULL;
2102 }
2103 w = _PyLong_New(size_w);
2104 if (w == NULL) {
2105 Py_DECREF(v);
2106 *prem = NULL;
2107 return NULL;
2108 }
2109
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);
2114 assert(carry == 0);
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;
2118 size_v++;
2119 }
2120
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;
2124 assert(k >= 0);
2125 a = _PyLong_New(k);
2126 if (a == NULL) {
2127 Py_DECREF(w);
2128 Py_DECREF(v);
2129 *prem = NULL;
2130 return NULL;
2131 }
2132 v0 = v->ob_digit;
2133 w0 = w->ob_digit;
2134 wm1 = w0[size_w-1];
2135 wm2 = w0[size_w-2];
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]. */
2139
2140 SIGCHECK({
2141 Py_DECREF(a);
2142 Py_DECREF(w);
2143 Py_DECREF(v);
2144 *prem = NULL;
2145 return NULL;
2146 });
2147
2148 /* estimate quotient digit q; may overestimate by 1 (rare) */
2149 vtop = vk[size_w];
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)
2155 | vk[size_w-2])) {
2156 --q;
2157 r += wm1;
2158 if (r >= PyLong_BASE)
2159 break;
2160 }
2161 assert(q <= PyLong_BASE);
2162
2163 /* subtract q*w0[0:size_w] from vk[0:size_w+1] */
2164 zhi = 0;
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,
2172 z, PyLong_SHIFT);
2173 }
2174
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) {
2178 carry = 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;
2183 }
2184 --q;
2185 }
2186
2187 /* store quotient digit */
2188 assert(q < PyLong_BASE);
2189 *--ak = q;
2190 }
2191
2192 /* unshift remainder; we reuse w to store the result */
2193 carry = v_rshift(w0, v0, size_w, d);
2194 assert(carry==0);
2195 Py_DECREF(v);
2196
2197 *prem = long_normalize(w);
2198 return long_normalize(a);
2199 }
2200
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
2206 -1.0. */
2207
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
2211 #else
2212 #define EXP2_DBL_MANT_DIG (ldexp(1.0, DBL_MANT_DIG))
2213 #endif
2214
2215 double
_PyLong_Frexp(PyLongObject * a,Py_ssize_t * e)2216 _PyLong_Frexp(PyLongObject *a, Py_ssize_t *e)
2217 {
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];
2221 double dx;
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};
2226
2227 a_size = ABS(Py_SIZE(a));
2228 if (a_size == 0) {
2229 /* Special case for 0: significand 0.0, exponent 0. */
2230 *e = 0;
2231 return 0.0;
2232 }
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))
2239 goto overflow;
2240 a_bits = (a_size - 1) * PyLong_SHIFT + a_bits;
2241
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).
2244
2245 Number of digits needed for result: write // for floor division.
2246 Then if shifting left, we end up using
2247
2248 1 + a_size + (DBL_MANT_DIG + 2 - a_bits) // PyLong_SHIFT
2249
2250 digits. If shifting right, we use
2251
2252 a_size - (a_bits - DBL_MANT_DIG - 2) // PyLong_SHIFT
2253
2254 digits. Using a_size = 1 + (a_bits - 1) // PyLong_SHIFT along with
2255 the inequalities
2256
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,
2260
2261 valid for any integers m and n, we find that x_size satisfies
2262
2263 x_size <= 2 + (DBL_MANT_DIG + 1) // PyLong_SHIFT
2264
2265 in both cases.
2266 */
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;
2270 x_size = 0;
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,
2274 (int)shift_bits);
2275 x_size += a_size;
2276 x_digits[x_size++] = rem;
2277 }
2278 else {
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
2287 of x. */
2288 if (rem)
2289 x_digits[0] |= 1;
2290 else
2291 while (shift_digits > 0)
2292 if (a->ob_digit[--shift_digits]) {
2293 x_digits[0] |= 1;
2294 break;
2295 }
2296 }
2297 assert(1 <= x_size &&
2298 x_size <= (Py_ssize_t)(sizeof(x_digits)/sizeof(digit)));
2299
2300 /* Round, and convert to double. */
2301 x_digits[0] += half_even_correction[x_digits[0] & 7];
2302 dx = x_digits[--x_size];
2303 while (x_size > 0)
2304 dx = dx * PyLong_BASE + x_digits[--x_size];
2305
2306 /* Rescale; make correction if result is 1.0. */
2307 dx /= 4.0 * EXP2_DBL_MANT_DIG;
2308 if (dx == 1.0) {
2309 if (a_bits == PY_SSIZE_T_MAX)
2310 goto overflow;
2311 dx = 0.5;
2312 a_bits += 1;
2313 }
2314
2315 *e = a_bits;
2316 return Py_SIZE(a) < 0 ? -dx : dx;
2317
2318 overflow:
2319 /* exponent > PY_SSIZE_T_MAX */
2320 PyErr_SetString(PyExc_OverflowError,
2321 "huge integer: number of bits overflows a Py_ssize_t");
2322 *e = 0;
2323 return -1.0;
2324 }
2325
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. */
2328
2329 double
PyLong_AsDouble(PyObject * v)2330 PyLong_AsDouble(PyObject *v)
2331 {
2332 Py_ssize_t exponent;
2333 double x;
2334
2335 if (v == NULL || !PyLong_Check(v)) {
2336 PyErr_BadInternalCall();
2337 return -1.0;
2338 }
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");
2343 return -1.0;
2344 }
2345 return ldexp(x, (int)exponent);
2346 }
2347
2348 /* Methods */
2349
2350 static void
long_dealloc(PyObject * v)2351 long_dealloc(PyObject *v)
2352 {
2353 Py_TYPE(v)->tp_free(v);
2354 }
2355
2356 static PyObject *
long_repr(PyObject * v)2357 long_repr(PyObject *v)
2358 {
2359 return _PyLong_Format(v, 10, 1, 0);
2360 }
2361
2362 static PyObject *
long_str(PyObject * v)2363 long_str(PyObject *v)
2364 {
2365 return _PyLong_Format(v, 10, 0, 0);
2366 }
2367
2368 static int
long_compare(PyLongObject * a,PyLongObject * b)2369 long_compare(PyLongObject *a, PyLongObject *b)
2370 {
2371 Py_ssize_t sign;
2372
2373 if (Py_SIZE(a) != Py_SIZE(b)) {
2374 sign = Py_SIZE(a) - Py_SIZE(b);
2375 }
2376 else {
2377 Py_ssize_t i = ABS(Py_SIZE(a));
2378 while (--i >= 0 && a->ob_digit[i] == b->ob_digit[i])
2379 ;
2380 if (i < 0)
2381 sign = 0;
2382 else {
2383 sign = (sdigit)a->ob_digit[i] - (sdigit)b->ob_digit[i];
2384 if (Py_SIZE(a) < 0)
2385 sign = -sign;
2386 }
2387 }
2388 return sign < 0 ? -1 : sign > 0 ? 1 : 0;
2389 }
2390
2391 static long
long_hash(PyLongObject * v)2392 long_hash(PyLongObject *v)
2393 {
2394 unsigned long x;
2395 Py_ssize_t i;
2396 int sign;
2397
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 */
2401 i = v->ob_size;
2402 sign = 1;
2403 x = 0;
2404 if (i < 0) {
2405 sign = -1;
2406 i = -(i);
2407 }
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. */
2411 while (--i >= 0) {
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
2417 ULONG_MAX. */
2418 if (x < v->ob_digit[i])
2419 x++;
2420 }
2421 x = x * sign;
2422 if (x == (unsigned long)-1)
2423 x = (unsigned long)-2;
2424 return (long)x;
2425 }
2426
2427
2428 /* Add the absolute values of two long integers. */
2429
2430 static PyLongObject *
x_add(PyLongObject * a,PyLongObject * b)2431 x_add(PyLongObject *a, PyLongObject *b)
2432 {
2433 Py_ssize_t size_a = ABS(Py_SIZE(a)), size_b = ABS(Py_SIZE(b));
2434 PyLongObject *z;
2435 Py_ssize_t i;
2436 digit carry = 0;
2437
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;
2442 size_a = size_b;
2443 size_b = size_temp; }
2444 }
2445 z = _PyLong_New(size_a+1);
2446 if (z == NULL)
2447 return NULL;
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;
2452 }
2453 for (; i < size_a; ++i) {
2454 carry += a->ob_digit[i];
2455 z->ob_digit[i] = carry & PyLong_MASK;
2456 carry >>= PyLong_SHIFT;
2457 }
2458 z->ob_digit[i] = carry;
2459 return long_normalize(z);
2460 }
2461
2462 /* Subtract the absolute values of two integers. */
2463
2464 static PyLongObject *
x_sub(PyLongObject * a,PyLongObject * b)2465 x_sub(PyLongObject *a, PyLongObject *b)
2466 {
2467 Py_ssize_t size_a = ABS(Py_SIZE(a)), size_b = ABS(Py_SIZE(b));
2468 PyLongObject *z;
2469 Py_ssize_t i;
2470 int sign = 1;
2471 digit borrow = 0;
2472
2473 /* Ensure a is the larger of the two: */
2474 if (size_a < size_b) {
2475 sign = -1;
2476 { PyLongObject *temp = a; a = b; b = temp; }
2477 { Py_ssize_t size_temp = size_a;
2478 size_a = size_b;
2479 size_b = size_temp; }
2480 }
2481 else if (size_a == size_b) {
2482 /* Find highest digit where a and b differ: */
2483 i = size_a;
2484 while (--i >= 0 && a->ob_digit[i] == b->ob_digit[i])
2485 ;
2486 if (i < 0)
2487 return _PyLong_New(0);
2488 if (a->ob_digit[i] < b->ob_digit[i]) {
2489 sign = -1;
2490 { PyLongObject *temp = a; a = b; b = temp; }
2491 }
2492 size_a = size_b = i+1;
2493 }
2494 z = _PyLong_New(size_a);
2495 if (z == NULL)
2496 return NULL;
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 */
2504 }
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 */
2510 }
2511 assert(borrow == 0);
2512 if (sign < 0)
2513 z->ob_size = -(z->ob_size);
2514 return long_normalize(z);
2515 }
2516
2517 static PyObject *
long_add(PyLongObject * v,PyLongObject * w)2518 long_add(PyLongObject *v, PyLongObject *w)
2519 {
2520 PyLongObject *a, *b, *z;
2521
2522 CONVERT_BINOP((PyObject *)v, (PyObject *)w, &a, &b);
2523
2524 if (a->ob_size < 0) {
2525 if (b->ob_size < 0) {
2526 z = x_add(a, b);
2527 if (z != NULL && z->ob_size != 0)
2528 z->ob_size = -(z->ob_size);
2529 }
2530 else
2531 z = x_sub(b, a);
2532 }
2533 else {
2534 if (b->ob_size < 0)
2535 z = x_sub(a, b);
2536 else
2537 z = x_add(a, b);
2538 }
2539 Py_DECREF(a);
2540 Py_DECREF(b);
2541 return (PyObject *)z;
2542 }
2543
2544 static PyObject *
long_sub(PyLongObject * v,PyLongObject * w)2545 long_sub(PyLongObject *v, PyLongObject *w)
2546 {
2547 PyLongObject *a, *b, *z;
2548
2549 CONVERT_BINOP((PyObject *)v, (PyObject *)w, &a, &b);
2550
2551 if (a->ob_size < 0) {
2552 if (b->ob_size < 0)
2553 z = x_sub(a, b);
2554 else
2555 z = x_add(a, b);
2556 if (z != NULL && z->ob_size != 0)
2557 z->ob_size = -(z->ob_size);
2558 }
2559 else {
2560 if (b->ob_size < 0)
2561 z = x_add(a, b);
2562 else
2563 z = x_sub(a, b);
2564 }
2565 Py_DECREF(a);
2566 Py_DECREF(b);
2567 return (PyObject *)z;
2568 }
2569
2570 /* Grade school multiplication, ignoring the signs.
2571 * Returns the absolute value of the product, or NULL if error.
2572 */
2573 static PyLongObject *
x_mul(PyLongObject * a,PyLongObject * b)2574 x_mul(PyLongObject *a, PyLongObject *b)
2575 {
2576 PyLongObject *z;
2577 Py_ssize_t size_a = ABS(Py_SIZE(a));
2578 Py_ssize_t size_b = ABS(Py_SIZE(b));
2579 Py_ssize_t i;
2580
2581 z = _PyLong_New(size_a + size_b);
2582 if (z == NULL)
2583 return NULL;
2584
2585 memset(z->ob_digit, 0, Py_SIZE(z) * sizeof(digit));
2586 if (a == b) {
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).
2592 */
2593 for (i = 0; i < size_a; ++i) {
2594 twodigits carry;
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;
2599
2600 SIGCHECK({
2601 Py_DECREF(z);
2602 return NULL;
2603 });
2604
2605 carry = *pz + f * f;
2606 *pz++ = (digit)(carry & PyLong_MASK);
2607 carry >>= PyLong_SHIFT;
2608 assert(carry <= PyLong_MASK);
2609
2610 /* Now f is added in twice in each column of the
2611 * pyramid it appears. Same as adding f<<1 once.
2612 */
2613 f <<= 1;
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));
2619 }
2620 if (carry) {
2621 carry += *pz;
2622 *pz++ = (digit)(carry & PyLong_MASK);
2623 carry >>= PyLong_SHIFT;
2624 }
2625 if (carry)
2626 *pz += (digit)(carry & PyLong_MASK);
2627 assert((carry >> PyLong_SHIFT) == 0);
2628 }
2629 }
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;
2637
2638 SIGCHECK({
2639 Py_DECREF(z);
2640 return NULL;
2641 });
2642
2643 while (pb < pbend) {
2644 carry += *pz + *pb++ * f;
2645 *pz++ = (digit)(carry & PyLong_MASK);
2646 carry >>= PyLong_SHIFT;
2647 assert(carry <= PyLong_MASK);
2648 }
2649 if (carry)
2650 *pz += (digit)(carry & PyLong_MASK);
2651 assert((carry >> PyLong_SHIFT) == 0);
2652 }
2653 }
2654 return long_normalize(z);
2655 }
2656
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.
2663 */
2664 static int
kmul_split(PyLongObject * n,Py_ssize_t size,PyLongObject ** high,PyLongObject ** low)2665 kmul_split(PyLongObject *n,
2666 Py_ssize_t size,
2667 PyLongObject **high,
2668 PyLongObject **low)
2669 {
2670 PyLongObject *hi, *lo;
2671 Py_ssize_t size_lo, size_hi;
2672 const Py_ssize_t size_n = ABS(Py_SIZE(n));
2673
2674 size_lo = MIN(size_n, size);
2675 size_hi = size_n - size_lo;
2676
2677 if ((hi = _PyLong_New(size_hi)) == NULL)
2678 return -1;
2679 if ((lo = _PyLong_New(size_lo)) == NULL) {
2680 Py_DECREF(hi);
2681 return -1;
2682 }
2683
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));
2686
2687 *high = long_normalize(hi);
2688 *low = long_normalize(lo);
2689 return 0;
2690 }
2691
2692 static PyLongObject *k_lopsided_mul(PyLongObject *a, PyLongObject *b);
2693
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).
2697 */
2698 static PyLongObject *
k_mul(PyLongObject * a,PyLongObject * b)2699 k_mul(PyLongObject *a, PyLongObject *b)
2700 {
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 */
2710 Py_ssize_t i;
2711
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.
2718 */
2719
2720 /* We want to split based on the larger number; fiddle so that b
2721 * is largest.
2722 */
2723 if (asize > bsize) {
2724 t1 = a;
2725 a = b;
2726 b = t1;
2727
2728 i = asize;
2729 asize = bsize;
2730 bsize = i;
2731 }
2732
2733 /* Use gradeschool math when either number is too small. */
2734 i = a == b ? KARATSUBA_SQUARE_CUTOFF : KARATSUBA_CUTOFF;
2735 if (asize <= i) {
2736 if (asize == 0)
2737 return _PyLong_New(0);
2738 else
2739 return x_mul(a, b);
2740 }
2741
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.
2747 */
2748 if (2 * asize <= bsize)
2749 return k_lopsided_mul(a, b);
2750
2751 /* Split a & b into hi & lo pieces. */
2752 shift = bsize >> 1;
2753 if (kmul_split(a, shift, &ah, &al) < 0) goto fail;
2754 assert(Py_SIZE(ah) > 0); /* the split isn't degenerate */
2755
2756 if (a == b) {
2757 bh = ah;
2758 bl = al;
2759 Py_INCREF(bh);
2760 Py_INCREF(bl);
2761 }
2762 else if (kmul_split(b, shift, &bh, &bl) < 0) goto fail;
2763
2764 /* The plan:
2765 * 1. Allocate result space (asize + bsize digits: that's always
2766 * enough).
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
2777 * at shift.
2778 */
2779
2780 /* 1. Allocate result space. */
2781 ret = _PyLong_New(asize + bsize);
2782 if (ret == NULL) goto fail;
2783 #ifdef Py_DEBUG
2784 /* Fill with trash, to catch reference to uninitialized digits. */
2785 memset(ret->ob_digit, 0xDF, Py_SIZE(ret) * sizeof(digit));
2786 #endif
2787
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));
2794
2795 /* Zero-out the digits higher than the ah*bh copy. */
2796 i = Py_SIZE(ret) - 2*shift - Py_SIZE(t1);
2797 if (i)
2798 memset(ret->ob_digit + 2*shift + Py_SIZE(t1), 0,
2799 i * sizeof(digit));
2800
2801 /* 3. t2 <- al*bl, and copy into the low digits. */
2802 if ((t2 = k_mul(al, bl)) == NULL) {
2803 Py_DECREF(t1);
2804 goto fail;
2805 }
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));
2809
2810 /* Zero out remaining digits. */
2811 i = 2*shift - Py_SIZE(t2); /* number of uninitialized digits */
2812 if (i)
2813 memset(ret->ob_digit + Py_SIZE(t2), 0, i * sizeof(digit));
2814
2815 /* 4 & 5. Subtract ah*bh (t1) and al*bl (t2). We do al*bl first
2816 * because it's fresher in cache.
2817 */
2818 i = Py_SIZE(ret) - shift; /* # digits after shift */
2819 (void)v_isub(ret->ob_digit + shift, i, t2->ob_digit, Py_SIZE(t2));
2820 Py_DECREF(t2);
2821
2822 (void)v_isub(ret->ob_digit + shift, i, t1->ob_digit, Py_SIZE(t1));
2823 Py_DECREF(t1);
2824
2825 /* 6. t3 <- (ah+al)(bh+bl), and add into result. */
2826 if ((t1 = x_add(ah, al)) == NULL) goto fail;
2827 Py_DECREF(ah);
2828 Py_DECREF(al);
2829 ah = al = NULL;
2830
2831 if (a == b) {
2832 t2 = t1;
2833 Py_INCREF(t2);
2834 }
2835 else if ((t2 = x_add(bh, bl)) == NULL) {
2836 Py_DECREF(t1);
2837 goto fail;
2838 }
2839 Py_DECREF(bh);
2840 Py_DECREF(bl);
2841 bh = bl = NULL;
2842
2843 t3 = k_mul(t1, t2);
2844 Py_DECREF(t1);
2845 Py_DECREF(t2);
2846 if (t3 == NULL) goto fail;
2847 assert(Py_SIZE(t3) >= 0);
2848
2849 /* Add t3. It's not obvious why we can't run out of room here.
2850 * See the (*) comment after this function.
2851 */
2852 (void)v_iadd(ret->ob_digit + shift, i, t3->ob_digit, Py_SIZE(t3));
2853 Py_DECREF(t3);
2854
2855 return long_normalize(ret);
2856
2857 fail:
2858 Py_XDECREF(ret);
2859 Py_XDECREF(ah);
2860 Py_XDECREF(al);
2861 Py_XDECREF(bh);
2862 Py_XDECREF(bl);
2863 return NULL;
2864 }
2865
2866 /* (*) Why adding t3 can't "run out of room" above.
2867
2868 Let f(x) mean the floor of x and c(x) mean the ceiling of x. Some facts
2869 to start with:
2870
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)
2874 3. asize <= bsize
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.
2877
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.
2882
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.
2885
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.
2889
2890 The product (ah+al)*(bh+bl) therefore has at most
2891
2892 c(bsize/2) + (asize == bsize ? c(bsize/2) : f(bsize/2)) digits + 2 bits
2893
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.
2905
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.
2909 */
2910
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).
2918 */
2919 static PyLongObject *
k_lopsided_mul(PyLongObject * a,PyLongObject * b)2920 k_lopsided_mul(PyLongObject *a, PyLongObject *b)
2921 {
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 */
2925 PyLongObject *ret;
2926 PyLongObject *bslice = NULL;
2927
2928 assert(asize > KARATSUBA_CUTOFF);
2929 assert(2 * asize <= bsize);
2930
2931 /* Allocate result space, and zero it out. */
2932 ret = _PyLong_New(asize + bsize);
2933 if (ret == NULL)
2934 return NULL;
2935 memset(ret->ob_digit, 0, Py_SIZE(ret) * sizeof(digit));
2936
2937 /* Successive slices of b are copied into bslice. */
2938 bslice = _PyLong_New(asize);
2939 if (bslice == NULL)
2940 goto fail;
2941
2942 nbdone = 0;
2943 while (bsize > 0) {
2944 PyLongObject *product;
2945 const Py_ssize_t nbtouse = MIN(bsize, asize);
2946
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)
2953 goto fail;
2954
2955 /* Add into result. */
2956 (void)v_iadd(ret->ob_digit + nbdone, Py_SIZE(ret) - nbdone,
2957 product->ob_digit, Py_SIZE(product));
2958 Py_DECREF(product);
2959
2960 bsize -= nbtouse;
2961 nbdone += nbtouse;
2962 }
2963
2964 Py_DECREF(bslice);
2965 return long_normalize(ret);
2966
2967 fail:
2968 Py_DECREF(ret);
2969 Py_XDECREF(bslice);
2970 return NULL;
2971 }
2972
2973 static PyObject *
long_mul(PyLongObject * v,PyLongObject * w)2974 long_mul(PyLongObject *v, PyLongObject *w)
2975 {
2976 PyLongObject *a, *b, *z;
2977
2978 if (!convert_binop((PyObject *)v, (PyObject *)w, &a, &b)) {
2979 Py_INCREF(Py_NotImplemented);
2980 return Py_NotImplemented;
2981 }
2982
2983 z = k_mul(a, b);
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);
2987 Py_DECREF(a);
2988 Py_DECREF(b);
2989 return (PyObject *)z;
2990 }
2991
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.
2997 Some examples:
2998 a b a rem b a mod b
2999 13 10 3 3
3000 -13 10 -3 7
3001 13 -10 3 -7
3002 -13 -10 -3 -3
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. */
3006
3007 /* Compute
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).
3012 */
3013 static int
l_divmod(PyLongObject * v,PyLongObject * w,PyLongObject ** pdiv,PyLongObject ** pmod)3014 l_divmod(PyLongObject *v, PyLongObject *w,
3015 PyLongObject **pdiv, PyLongObject **pmod)
3016 {
3017 PyLongObject *div, *mod;
3018
3019 if (long_divrem(v, w, &div, &mod) < 0)
3020 return -1;
3021 if ((Py_SIZE(mod) < 0 && Py_SIZE(w) > 0) ||
3022 (Py_SIZE(mod) > 0 && Py_SIZE(w) < 0)) {
3023 PyLongObject *temp;
3024 PyLongObject *one;
3025 temp = (PyLongObject *) long_add(mod, w);
3026 Py_DECREF(mod);
3027 mod = temp;
3028 if (mod == NULL) {
3029 Py_DECREF(div);
3030 return -1;
3031 }
3032 one = (PyLongObject *) PyLong_FromLong(1L);
3033 if (one == NULL ||
3034 (temp = (PyLongObject *) long_sub(div, one)) == NULL) {
3035 Py_DECREF(mod);
3036 Py_DECREF(div);
3037 Py_XDECREF(one);
3038 return -1;
3039 }
3040 Py_DECREF(one);
3041 Py_DECREF(div);
3042 div = temp;
3043 }
3044 if (pdiv != NULL)
3045 *pdiv = div;
3046 else
3047 Py_DECREF(div);
3048
3049 if (pmod != NULL)
3050 *pmod = mod;
3051 else
3052 Py_DECREF(mod);
3053
3054 return 0;
3055 }
3056
3057 static PyObject *
long_div(PyObject * v,PyObject * w)3058 long_div(PyObject *v, PyObject *w)
3059 {
3060 PyLongObject *a, *b, *div;
3061
3062 CONVERT_BINOP(v, w, &a, &b);
3063 if (l_divmod(a, b, &div, NULL) < 0)
3064 div = NULL;
3065 Py_DECREF(a);
3066 Py_DECREF(b);
3067 return (PyObject *)div;
3068 }
3069
3070 static PyObject *
long_classic_div(PyObject * v,PyObject * w)3071 long_classic_div(PyObject *v, PyObject *w)
3072 {
3073 PyLongObject *a, *b, *div;
3074
3075 CONVERT_BINOP(v, w, &a, &b);
3076 if (Py_DivisionWarningFlag &&
3077 PyErr_Warn(PyExc_DeprecationWarning, "classic long division") < 0)
3078 div = NULL;
3079 else if (l_divmod(a, b, &div, NULL) < 0)
3080 div = NULL;
3081 Py_DECREF(a);
3082 Py_DECREF(b);
3083 return (PyObject *)div;
3084 }
3085
3086 /* PyLong/PyLong -> float, with correctly rounded result. */
3087
3088 #define MANT_DIG_DIGITS (DBL_MANT_DIG / PyLong_SHIFT)
3089 #define MANT_DIG_BITS (DBL_MANT_DIG % PyLong_SHIFT)
3090
3091 static PyObject *
long_true_divide(PyObject * v,PyObject * w)3092 long_true_divide(PyObject *v, PyObject *w)
3093 {
3094 PyLongObject *a, *b, *x;
3095 Py_ssize_t a_size, b_size, shift, extra_bits, diff, x_size, x_bits;
3096 digit mask, low;
3097 int inexact, negate, a_is_small, b_is_small;
3098 double dx, result;
3099
3100 CONVERT_BINOP(v, w, &a, &b);
3101
3102 /*
3103 Method in a nutshell:
3104
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).
3111
3112 In more detail:
3113
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
3119 for b). Then
3120
3121 2**(a_bits - b_bits - 1) < a/b < 2**(a_bits - b_bits + 1).
3122
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
3127
3128 DBL_MIN_EXP - DBL_MANT_DIG - 1 <= a_bits - b_bits <= DBL_MAX_EXP.
3129
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:
3135
3136 shift = a_bits - b_bits - DBL_MANT_DIG - 2
3137
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:
3142
3143 shift = MAX(a_bits - b_bits, DBL_MIN_EXP) - DBL_MANT_DIG - 2
3144
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.
3150
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
3153 that x >= 1.
3154
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
3157
3158 round(x/2**extra_bits) * 2**(extra_bits+shift).
3159
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:
3163
3164 extra_bits >= MAX(x_bits, DBL_MIN_EXP - shift) - DBL_MANT_DIG
3165
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.
3169
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.
3176
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.
3180
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
3186 returning.
3187 */
3188
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);
3193 if (b_size == 0) {
3194 PyErr_SetString(PyExc_ZeroDivisionError,
3195 "division by zero");
3196 goto error;
3197 }
3198 if (a_size == 0)
3199 goto underflow_or_zero;
3200
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) {
3212 double da, db;
3213 da = a->ob_digit[--a_size];
3214 while (a_size > 0)
3215 da = da * PyLong_BASE + a->ob_digit[--a_size];
3216 db = b->ob_digit[--b_size];
3217 while (b_size > 0)
3218 db = db * PyLong_BASE + b->ob_digit[--b_size];
3219 result = da / db;
3220 goto success;
3221 }
3222
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 */
3227 goto 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)
3236 goto overflow;
3237 else if (diff < DBL_MIN_EXP - DBL_MANT_DIG - 1)
3238 goto underflow_or_zero;
3239
3240 /* Choose value for shift; see comments for step 1 above. */
3241 shift = MAX(diff, DBL_MIN_EXP) - DBL_MANT_DIG - 2;
3242
3243 inexact = 0;
3244
3245 /* x = abs(a * 2**-shift) */
3246 if (shift <= 0) {
3247 Py_ssize_t i, shift_digits = -shift / PyLong_SHIFT;
3248 digit rem;
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");
3256 goto error;
3257 }
3258 x = _PyLong_New(a_size + shift_digits + 1);
3259 if (x == NULL)
3260 goto error;
3261 for (i = 0; i < shift_digits; i++)
3262 x->ob_digit[i] = 0;
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;
3266 }
3267 else {
3268 Py_ssize_t shift_digits = shift / PyLong_SHIFT;
3269 digit rem;
3270 /* x = a >> shift */
3271 assert(a_size >= shift_digits);
3272 x = _PyLong_New(a_size - shift_digits);
3273 if (x == NULL)
3274 goto error;
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 */
3278 if (rem)
3279 inexact = 1;
3280 while (!inexact && shift_digits > 0)
3281 if (a->ob_digit[--shift_digits])
3282 inexact = 1;
3283 }
3284 long_normalize(x);
3285 x_size = Py_SIZE(x);
3286
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. */
3289 if (b_size == 1) {
3290 digit rem = inplace_divrem1(x->ob_digit, x->ob_digit, x_size,
3291 b->ob_digit[0]);
3292 long_normalize(x);
3293 if (rem)
3294 inexact = 1;
3295 }
3296 else {
3297 PyLongObject *div, *rem;
3298 div = x_divrem(x, b, &rem);
3299 Py_DECREF(x);
3300 x = div;
3301 if (x == NULL)
3302 goto error;
3303 if (Py_SIZE(rem))
3304 inexact = 1;
3305 Py_DECREF(rem);
3306 }
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]);
3310
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);
3314
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 & (3U*mask-1U)))
3319 low += mask;
3320 x->ob_digit[0] = low & ~(2U*mask-1U);
3321
3322 /* Convert x to a double dx; the conversion is exact. */
3323 dx = x->ob_digit[--x_size];
3324 while (x_size > 0)
3325 dx = dx * PyLong_BASE + x->ob_digit[--x_size];
3326 Py_DECREF(x);
3327
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)))
3331 goto overflow;
3332 result = ldexp(dx, (int)shift);
3333
3334 success:
3335 Py_DECREF(a);
3336 Py_DECREF(b);
3337 return PyFloat_FromDouble(negate ? -result : result);
3338
3339 underflow_or_zero:
3340 Py_DECREF(a);
3341 Py_DECREF(b);
3342 return PyFloat_FromDouble(negate ? -0.0 : 0.0);
3343
3344 overflow:
3345 PyErr_SetString(PyExc_OverflowError,
3346 "integer division result too large for a float");
3347 error:
3348 Py_DECREF(a);
3349 Py_DECREF(b);
3350 return NULL;
3351 }
3352
3353 static PyObject *
long_mod(PyObject * v,PyObject * w)3354 long_mod(PyObject *v, PyObject *w)
3355 {
3356 PyLongObject *a, *b, *mod;
3357
3358 CONVERT_BINOP(v, w, &a, &b);
3359
3360 if (l_divmod(a, b, NULL, &mod) < 0)
3361 mod = NULL;
3362 Py_DECREF(a);
3363 Py_DECREF(b);
3364 return (PyObject *)mod;
3365 }
3366
3367 static PyObject *
long_divmod(PyObject * v,PyObject * w)3368 long_divmod(PyObject *v, PyObject *w)
3369 {
3370 PyLongObject *a, *b, *div, *mod;
3371 PyObject *z;
3372
3373 CONVERT_BINOP(v, w, &a, &b);
3374
3375 if (l_divmod(a, b, &div, &mod) < 0) {
3376 Py_DECREF(a);
3377 Py_DECREF(b);
3378 return NULL;
3379 }
3380 z = PyTuple_New(2);
3381 if (z != NULL) {
3382 PyTuple_SetItem(z, 0, (PyObject *) div);
3383 PyTuple_SetItem(z, 1, (PyObject *) mod);
3384 }
3385 else {
3386 Py_DECREF(div);
3387 Py_DECREF(mod);
3388 }
3389 Py_DECREF(a);
3390 Py_DECREF(b);
3391 return z;
3392 }
3393
3394 /* pow(v, w, x) */
3395 static PyObject *
long_pow(PyObject * v,PyObject * w,PyObject * x)3396 long_pow(PyObject *v, PyObject *w, PyObject *x)
3397 {
3398 PyLongObject *a, *b, *c; /* a,b,c = v,w,x */
3399 int negativeOutput = 0; /* if x<0 return negative output */
3400
3401 PyLongObject *z = NULL; /* accumulated result */
3402 Py_ssize_t i, j, k; /* counters */
3403 PyLongObject *temp = NULL;
3404
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).
3407 */
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};
3410
3411 /* a, b, c = v, w, x */
3412 CONVERT_BINOP(v, w, &a, &b);
3413 if (PyLong_Check(x)) {
3414 c = (PyLongObject *)x;
3415 Py_INCREF(x);
3416 }
3417 else if (PyInt_Check(x)) {
3418 c = (PyLongObject *)PyLong_FromLong(PyInt_AS_LONG(x));
3419 if (c == NULL)
3420 goto Error;
3421 }
3422 else if (x == Py_None)
3423 c = NULL;
3424 else {
3425 Py_DECREF(a);
3426 Py_DECREF(b);
3427 Py_INCREF(Py_NotImplemented);
3428 return Py_NotImplemented;
3429 }
3430
3431 if (Py_SIZE(b) < 0) { /* if exponent is negative */
3432 if (c) {
3433 PyErr_SetString(PyExc_TypeError, "pow() 2nd argument "
3434 "cannot be negative when 3rd argument specified");
3435 goto Error;
3436 }
3437 else {
3438 /* else return a float. This works because we know
3439 that this calls float_pow() which converts its
3440 arguments to double. */
3441 Py_DECREF(a);
3442 Py_DECREF(b);
3443 return PyFloat_Type.tp_as_number->nb_power(v, w, x);
3444 }
3445 }
3446
3447 if (c) {
3448 /* if modulus == 0:
3449 raise ValueError() */
3450 if (Py_SIZE(c) == 0) {
3451 PyErr_SetString(PyExc_ValueError,
3452 "pow() 3rd argument cannot be 0");
3453 goto Error;
3454 }
3455
3456 /* if modulus < 0:
3457 negativeOutput = True
3458 modulus = -modulus */
3459 if (Py_SIZE(c) < 0) {
3460 negativeOutput = 1;
3461 temp = (PyLongObject *)_PyLong_Copy(c);
3462 if (temp == NULL)
3463 goto Error;
3464 Py_DECREF(c);
3465 c = temp;
3466 temp = NULL;
3467 c->ob_size = - c->ob_size;
3468 }
3469
3470 /* if modulus == 1:
3471 return 0 */
3472 if ((Py_SIZE(c) == 1) && (c->ob_digit[0] == 1)) {
3473 z = (PyLongObject *)PyLong_FromLong(0L);
3474 goto Done;
3475 }
3476
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)
3488 goto Error;
3489 Py_DECREF(a);
3490 a = temp;
3491 temp = NULL;
3492 }
3493 }
3494
3495 /* At this point a, b, and c are guaranteed non-negative UNLESS
3496 c is NULL, in which case a may be negative. */
3497
3498 z = (PyLongObject *)PyLong_FromLong(1L);
3499 if (z == NULL)
3500 goto Error;
3501
3502 /* Perform a modular reduction, X = X % c, but leave X alone if c
3503 * is NULL.
3504 */
3505 #define REDUCE(X) \
3506 do { \
3507 if (c != NULL) { \
3508 if (l_divmod(X, c, NULL, &temp) < 0) \
3509 goto Error; \
3510 Py_XDECREF(X); \
3511 X = temp; \
3512 temp = NULL; \
3513 } \
3514 } while(0)
3515
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) \
3519 do { \
3520 temp = (PyLongObject *)long_mul(X, Y); \
3521 if (temp == NULL) \
3522 goto Error; \
3523 Py_XDECREF(result); \
3524 result = temp; \
3525 temp = NULL; \
3526 REDUCE(result); \
3527 } while(0)
3528
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];
3534
3535 for (j = (digit)1 << (PyLong_SHIFT-1); j != 0; j >>= 1) {
3536 MULT(z, z, z);
3537 if (bi & j)
3538 MULT(z, a, z);
3539 }
3540 }
3541 }
3542 else {
3543 /* Left-to-right 5-ary exponentiation (HAC Algorithm 14.82) */
3544 Py_INCREF(z); /* still holds 1L */
3545 table[0] = z;
3546 for (i = 1; i < 32; ++i)
3547 MULT(table[i-1], a, table[i]);
3548
3549 for (i = Py_SIZE(b) - 1; i >= 0; --i) {
3550 const digit bi = b->ob_digit[i];
3551
3552 for (j = PyLong_SHIFT - 5; j >= 0; j -= 5) {
3553 const int index = (bi >> j) & 0x1f;
3554 for (k = 0; k < 5; ++k)
3555 MULT(z, z, z);
3556 if (index)
3557 MULT(z, table[index], z);
3558 }
3559 }
3560 }
3561
3562 if (negativeOutput && (Py_SIZE(z) != 0)) {
3563 temp = (PyLongObject *)long_sub(z, c);
3564 if (temp == NULL)
3565 goto Error;
3566 Py_DECREF(z);
3567 z = temp;
3568 temp = NULL;
3569 }
3570 goto Done;
3571
3572 Error:
3573 if (z != NULL) {
3574 Py_DECREF(z);
3575 z = NULL;
3576 }
3577 /* fall through */
3578 Done:
3579 if (Py_SIZE(b) > FIVEARY_CUTOFF) {
3580 for (i = 0; i < 32; ++i)
3581 Py_XDECREF(table[i]);
3582 }
3583 Py_DECREF(a);
3584 Py_DECREF(b);
3585 Py_XDECREF(c);
3586 Py_XDECREF(temp);
3587 return (PyObject *)z;
3588 }
3589
3590 static PyObject *
long_invert(PyLongObject * v)3591 long_invert(PyLongObject *v)
3592 {
3593 /* Implement ~x as -(x+1) */
3594 PyLongObject *x;
3595 PyLongObject *w;
3596 w = (PyLongObject *)PyLong_FromLong(1L);
3597 if (w == NULL)
3598 return NULL;
3599 x = (PyLongObject *) long_add(v, w);
3600 Py_DECREF(w);
3601 if (x == NULL)
3602 return NULL;
3603 Py_SIZE(x) = -(Py_SIZE(x));
3604 return (PyObject *)x;
3605 }
3606
3607 static PyObject *
long_neg(PyLongObject * v)3608 long_neg(PyLongObject *v)
3609 {
3610 PyLongObject *z;
3611 if (v->ob_size == 0 && PyLong_CheckExact(v)) {
3612 /* -0 == 0 */
3613 Py_INCREF(v);
3614 return (PyObject *) v;
3615 }
3616 z = (PyLongObject *)_PyLong_Copy(v);
3617 if (z != NULL)
3618 z->ob_size = -(v->ob_size);
3619 return (PyObject *)z;
3620 }
3621
3622 static PyObject *
long_abs(PyLongObject * v)3623 long_abs(PyLongObject *v)
3624 {
3625 if (v->ob_size < 0)
3626 return long_neg(v);
3627 else
3628 return long_long((PyObject *)v);
3629 }
3630
3631 static int
long_nonzero(PyLongObject * v)3632 long_nonzero(PyLongObject *v)
3633 {
3634 return Py_SIZE(v) != 0;
3635 }
3636
3637 static PyObject *
long_rshift(PyLongObject * v,PyLongObject * w)3638 long_rshift(PyLongObject *v, PyLongObject *w)
3639 {
3640 PyLongObject *a, *b;
3641 PyLongObject *z = NULL;
3642 Py_ssize_t shiftby, newsize, wordshift, loshift, hishift, i, j;
3643 digit lomask, himask;
3644
3645 CONVERT_BINOP((PyObject *)v, (PyObject *)w, &a, &b);
3646
3647 if (Py_SIZE(a) < 0) {
3648 /* Right shifting negative numbers is harder */
3649 PyLongObject *a1, *a2;
3650 a1 = (PyLongObject *) long_invert(a);
3651 if (a1 == NULL)
3652 goto rshift_error;
3653 a2 = (PyLongObject *) long_rshift(a1, b);
3654 Py_DECREF(a1);
3655 if (a2 == NULL)
3656 goto rshift_error;
3657 z = (PyLongObject *) long_invert(a2);
3658 Py_DECREF(a2);
3659 }
3660 else {
3661 shiftby = PyLong_AsSsize_t((PyObject *)b);
3662 if (shiftby == -1L && PyErr_Occurred())
3663 goto rshift_error;
3664 if (shiftby < 0) {
3665 PyErr_SetString(PyExc_ValueError,
3666 "negative shift count");
3667 goto rshift_error;
3668 }
3669 wordshift = shiftby / PyLong_SHIFT;
3670 newsize = ABS(Py_SIZE(a)) - wordshift;
3671 if (newsize <= 0) {
3672 z = _PyLong_New(0);
3673 Py_DECREF(a);
3674 Py_DECREF(b);
3675 return (PyObject *)z;
3676 }
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);
3682 if (z == NULL)
3683 goto rshift_error;
3684 if (Py_SIZE(a) < 0)
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;
3688 if (i+1 < newsize)
3689 z->ob_digit[i] |= (a->ob_digit[j+1] << hishift) & himask;
3690 }
3691 z = long_normalize(z);
3692 }
3693 rshift_error:
3694 Py_DECREF(a);
3695 Py_DECREF(b);
3696 return (PyObject *) z;
3697
3698 }
3699
3700 static PyObject *
long_lshift(PyObject * v,PyObject * w)3701 long_lshift(PyObject *v, PyObject *w)
3702 {
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;
3707 twodigits accum;
3708
3709 CONVERT_BINOP(v, w, &a, &b);
3710
3711 shiftby = PyLong_AsSsize_t((PyObject *)b);
3712 if (shiftby == -1L && PyErr_Occurred())
3713 goto out;
3714 if (shiftby < 0) {
3715 PyErr_SetString(PyExc_ValueError, "negative shift count");
3716 goto out;
3717 }
3718
3719 if (Py_SIZE(a) == 0) {
3720 z = (PyLongObject *)PyLong_FromLong(0);
3721 goto out;
3722 }
3723
3724 /* wordshift, remshift = divmod(shiftby, PyLong_SHIFT) */
3725 wordshift = shiftby / PyLong_SHIFT;
3726 remshift = shiftby - wordshift * PyLong_SHIFT;
3727
3728 oldsize = ABS(a->ob_size);
3729 newsize = oldsize + wordshift;
3730 if (remshift)
3731 ++newsize;
3732 z = _PyLong_New(newsize);
3733 if (z == NULL)
3734 goto out;
3735 if (a->ob_size < 0)
3736 z->ob_size = -(z->ob_size);
3737 for (i = 0; i < wordshift; i++)
3738 z->ob_digit[i] = 0;
3739 accum = 0;
3740 for (i = wordshift, j = 0; j < oldsize; i++, j++) {
3741 accum |= (twodigits)a->ob_digit[j] << remshift;
3742 z->ob_digit[i] = (digit)(accum & PyLong_MASK);
3743 accum >>= PyLong_SHIFT;
3744 }
3745 if (remshift)
3746 z->ob_digit[newsize-1] = (digit)accum;
3747 else
3748 assert(!accum);
3749 z = long_normalize(z);
3750 out:
3751 Py_DECREF(a);
3752 Py_DECREF(b);
3753 return (PyObject *) z;
3754 }
3755
3756 /* Compute two's complement of digit vector a[0:m], writing result to
3757 z[0:m]. The digit vector a need not be normalized, but should not
3758 be entirely zero. a and z may point to the same digit vector. */
3759
3760 static void
v_complement(digit * z,digit * a,Py_ssize_t m)3761 v_complement(digit *z, digit *a, Py_ssize_t m)
3762 {
3763 Py_ssize_t i;
3764 digit carry = 1;
3765 for (i = 0; i < m; ++i) {
3766 carry += a[i] ^ PyLong_MASK;
3767 z[i] = carry & PyLong_MASK;
3768 carry >>= PyLong_SHIFT;
3769 }
3770 assert(carry == 0);
3771 }
3772
3773 /* Bitwise and/xor/or operations */
3774
3775 static PyObject *
long_bitwise(PyLongObject * a,int op,PyLongObject * b)3776 long_bitwise(PyLongObject *a,
3777 int op, /* '&', '|', '^' */
3778 PyLongObject *b)
3779 {
3780 int nega, negb, negz;
3781 Py_ssize_t size_a, size_b, size_z, i;
3782 PyLongObject *z;
3783
3784 /* Bitwise operations for negative numbers operate as though
3785 on a two's complement representation. So convert arguments
3786 from sign-magnitude to two's complement, and convert the
3787 result back to sign-magnitude at the end. */
3788
3789 /* If a is negative, replace it by its two's complement. */
3790 size_a = ABS(Py_SIZE(a));
3791 nega = Py_SIZE(a) < 0;
3792 if (nega) {
3793 z = _PyLong_New(size_a);
3794 if (z == NULL)
3795 return NULL;
3796 v_complement(z->ob_digit, a->ob_digit, size_a);
3797 a = z;
3798 }
3799 else
3800 /* Keep reference count consistent. */
3801 Py_INCREF(a);
3802
3803 /* Same for b. */
3804 size_b = ABS(Py_SIZE(b));
3805 negb = Py_SIZE(b) < 0;
3806 if (negb) {
3807 z = _PyLong_New(size_b);
3808 if (z == NULL) {
3809 Py_DECREF(a);
3810 return NULL;
3811 }
3812 v_complement(z->ob_digit, b->ob_digit, size_b);
3813 b = z;
3814 }
3815 else
3816 Py_INCREF(b);
3817
3818 /* Swap a and b if necessary to ensure size_a >= size_b. */
3819 if (size_a < size_b) {
3820 z = a; a = b; b = z;
3821 size_z = size_a; size_a = size_b; size_b = size_z;
3822 negz = nega; nega = negb; negb = negz;
3823 }
3824
3825 /* JRH: The original logic here was to allocate the result value (z)
3826 as the longer of the two operands. However, there are some cases
3827 where the result is guaranteed to be shorter than that: AND of two
3828 positives, OR of two negatives: use the shorter number. AND with
3829 mixed signs: use the positive number. OR with mixed signs: use the
3830 negative number.
3831 */
3832 switch (op) {
3833 case '^':
3834 negz = nega ^ negb;
3835 size_z = size_a;
3836 break;
3837 case '&':
3838 negz = nega & negb;
3839 size_z = negb ? size_a : size_b;
3840 break;
3841 case '|':
3842 negz = nega | negb;
3843 size_z = negb ? size_b : size_a;
3844 break;
3845 default:
3846 PyErr_BadArgument();
3847 return NULL;
3848 }
3849
3850 /* We allow an extra digit if z is negative, to make sure that
3851 the final two's complement of z doesn't overflow. */
3852 z = _PyLong_New(size_z + negz);
3853 if (z == NULL) {
3854 Py_DECREF(a);
3855 Py_DECREF(b);
3856 return NULL;
3857 }
3858
3859 /* Compute digits for overlap of a and b. */
3860 switch(op) {
3861 case '&':
3862 for (i = 0; i < size_b; ++i)
3863 z->ob_digit[i] = a->ob_digit[i] & b->ob_digit[i];
3864 break;
3865 case '|':
3866 for (i = 0; i < size_b; ++i)
3867 z->ob_digit[i] = a->ob_digit[i] | b->ob_digit[i];
3868 break;
3869 case '^':
3870 for (i = 0; i < size_b; ++i)
3871 z->ob_digit[i] = a->ob_digit[i] ^ b->ob_digit[i];
3872 break;
3873 default:
3874 PyErr_BadArgument();
3875 return NULL;
3876 }
3877
3878 /* Copy any remaining digits of a, inverting if necessary. */
3879 if (op == '^' && negb)
3880 for (; i < size_z; ++i)
3881 z->ob_digit[i] = a->ob_digit[i] ^ PyLong_MASK;
3882 else if (i < size_z)
3883 memcpy(&z->ob_digit[i], &a->ob_digit[i],
3884 (size_z-i)*sizeof(digit));
3885
3886 /* Complement result if negative. */
3887 if (negz) {
3888 Py_SIZE(z) = -(Py_SIZE(z));
3889 z->ob_digit[size_z] = PyLong_MASK;
3890 v_complement(z->ob_digit, z->ob_digit, size_z+1);
3891 }
3892
3893 Py_DECREF(a);
3894 Py_DECREF(b);
3895 return (PyObject *)long_normalize(z);
3896 }
3897
3898 static PyObject *
long_and(PyObject * v,PyObject * w)3899 long_and(PyObject *v, PyObject *w)
3900 {
3901 PyLongObject *a, *b;
3902 PyObject *c;
3903 CONVERT_BINOP(v, w, &a, &b);
3904 c = long_bitwise(a, '&', b);
3905 Py_DECREF(a);
3906 Py_DECREF(b);
3907 return c;
3908 }
3909
3910 static PyObject *
long_xor(PyObject * v,PyObject * w)3911 long_xor(PyObject *v, PyObject *w)
3912 {
3913 PyLongObject *a, *b;
3914 PyObject *c;
3915 CONVERT_BINOP(v, w, &a, &b);
3916 c = long_bitwise(a, '^', b);
3917 Py_DECREF(a);
3918 Py_DECREF(b);
3919 return c;
3920 }
3921
3922 static PyObject *
long_or(PyObject * v,PyObject * w)3923 long_or(PyObject *v, PyObject *w)
3924 {
3925 PyLongObject *a, *b;
3926 PyObject *c;
3927 CONVERT_BINOP(v, w, &a, &b);
3928 c = long_bitwise(a, '|', b);
3929 Py_DECREF(a);
3930 Py_DECREF(b);
3931 return c;
3932 }
3933
3934 static int
long_coerce(PyObject ** pv,PyObject ** pw)3935 long_coerce(PyObject **pv, PyObject **pw)
3936 {
3937 if (PyInt_Check(*pw)) {
3938 *pw = PyLong_FromLong(PyInt_AS_LONG(*pw));
3939 if (*pw == NULL)
3940 return -1;
3941 Py_INCREF(*pv);
3942 return 0;
3943 }
3944 else if (PyLong_Check(*pw)) {
3945 Py_INCREF(*pv);
3946 Py_INCREF(*pw);
3947 return 0;
3948 }
3949 return 1; /* Can't do it */
3950 }
3951
3952 static PyObject *
long_long(PyObject * v)3953 long_long(PyObject *v)
3954 {
3955 if (PyLong_CheckExact(v))
3956 Py_INCREF(v);
3957 else
3958 v = _PyLong_Copy((PyLongObject *)v);
3959 return v;
3960 }
3961
3962 static PyObject *
long_int(PyObject * v)3963 long_int(PyObject *v)
3964 {
3965 long x;
3966 x = PyLong_AsLong(v);
3967 if (PyErr_Occurred()) {
3968 if (PyErr_ExceptionMatches(PyExc_OverflowError)) {
3969 PyErr_Clear();
3970 if (PyLong_CheckExact(v)) {
3971 Py_INCREF(v);
3972 return v;
3973 }
3974 else
3975 return _PyLong_Copy((PyLongObject *)v);
3976 }
3977 else
3978 return NULL;
3979 }
3980 return PyInt_FromLong(x);
3981 }
3982
3983 static PyObject *
long_float(PyObject * v)3984 long_float(PyObject *v)
3985 {
3986 double result;
3987 result = PyLong_AsDouble(v);
3988 if (result == -1.0 && PyErr_Occurred())
3989 return NULL;
3990 return PyFloat_FromDouble(result);
3991 }
3992
3993 static PyObject *
long_oct(PyObject * v)3994 long_oct(PyObject *v)
3995 {
3996 return _PyLong_Format(v, 8, 1, 0);
3997 }
3998
3999 static PyObject *
long_hex(PyObject * v)4000 long_hex(PyObject *v)
4001 {
4002 return _PyLong_Format(v, 16, 1, 0);
4003 }
4004
4005 static PyObject *
4006 long_subtype_new(PyTypeObject *type, PyObject *args, PyObject *kwds);
4007
4008 static PyObject *
long_new(PyTypeObject * type,PyObject * args,PyObject * kwds)4009 long_new(PyTypeObject *type, PyObject *args, PyObject *kwds)
4010 {
4011 PyObject *x = NULL;
4012 int base = -909; /* unlikely! */
4013 static char *kwlist[] = {"x", "base", 0};
4014
4015 if (type != &PyLong_Type)
4016 return long_subtype_new(type, args, kwds); /* Wimp out */
4017 if (!PyArg_ParseTupleAndKeywords(args, kwds, "|Oi:long", kwlist,
4018 &x, &base))
4019 return NULL;
4020 if (x == NULL) {
4021 if (base != -909) {
4022 PyErr_SetString(PyExc_TypeError,
4023 "long() missing string argument");
4024 return NULL;
4025 }
4026 return PyLong_FromLong(0L);
4027 }
4028 if (base == -909)
4029 return PyNumber_Long(x);
4030 else if (PyString_Check(x)) {
4031 /* Since PyLong_FromString doesn't have a length parameter,
4032 * check here for possible NULs in the string. */
4033 char *string = PyString_AS_STRING(x);
4034 if (strlen(string) != (size_t)PyString_Size(x)) {
4035 /* create a repr() of the input string,
4036 * just like PyLong_FromString does. */
4037 PyObject *srepr;
4038 srepr = PyObject_Repr(x);
4039 if (srepr == NULL)
4040 return NULL;
4041 PyErr_Format(PyExc_ValueError,
4042 "invalid literal for long() with base %d: %s",
4043 base, PyString_AS_STRING(srepr));
4044 Py_DECREF(srepr);
4045 return NULL;
4046 }
4047 return PyLong_FromString(PyString_AS_STRING(x), NULL, base);
4048 }
4049 #ifdef Py_USING_UNICODE
4050 else if (PyUnicode_Check(x))
4051 return PyLong_FromUnicode(PyUnicode_AS_UNICODE(x),
4052 PyUnicode_GET_SIZE(x),
4053 base);
4054 #endif
4055 else {
4056 PyErr_SetString(PyExc_TypeError,
4057 "long() can't convert non-string with explicit base");
4058 return NULL;
4059 }
4060 }
4061
4062 /* Wimpy, slow approach to tp_new calls for subtypes of long:
4063 first create a regular long from whatever arguments we got,
4064 then allocate a subtype instance and initialize it from
4065 the regular long. The regular long is then thrown away.
4066 */
4067 static PyObject *
long_subtype_new(PyTypeObject * type,PyObject * args,PyObject * kwds)4068 long_subtype_new(PyTypeObject *type, PyObject *args, PyObject *kwds)
4069 {
4070 PyLongObject *tmp, *newobj;
4071 Py_ssize_t i, n;
4072
4073 assert(PyType_IsSubtype(type, &PyLong_Type));
4074 tmp = (PyLongObject *)long_new(&PyLong_Type, args, kwds);
4075 if (tmp == NULL)
4076 return NULL;
4077 assert(PyLong_Check(tmp));
4078 n = Py_SIZE(tmp);
4079 if (n < 0)
4080 n = -n;
4081 newobj = (PyLongObject *)type->tp_alloc(type, n);
4082 if (newobj == NULL) {
4083 Py_DECREF(tmp);
4084 return NULL;
4085 }
4086 assert(PyLong_Check(newobj));
4087 Py_SIZE(newobj) = Py_SIZE(tmp);
4088 for (i = 0; i < n; i++)
4089 newobj->ob_digit[i] = tmp->ob_digit[i];
4090 Py_DECREF(tmp);
4091 return (PyObject *)newobj;
4092 }
4093
4094 static PyObject *
long_getnewargs(PyLongObject * v)4095 long_getnewargs(PyLongObject *v)
4096 {
4097 return Py_BuildValue("(N)", _PyLong_Copy(v));
4098 }
4099
4100 static PyObject *
long_get0(PyLongObject * v,void * context)4101 long_get0(PyLongObject *v, void *context) {
4102 return PyLong_FromLong(0L);
4103 }
4104
4105 static PyObject *
long_get1(PyLongObject * v,void * context)4106 long_get1(PyLongObject *v, void *context) {
4107 return PyLong_FromLong(1L);
4108 }
4109
4110 static PyObject *
long__format__(PyObject * self,PyObject * args)4111 long__format__(PyObject *self, PyObject *args)
4112 {
4113 PyObject *format_spec;
4114
4115 if (!PyArg_ParseTuple(args, "O:__format__", &format_spec))
4116 return NULL;
4117 if (PyBytes_Check(format_spec))
4118 return _PyLong_FormatAdvanced(self,
4119 PyBytes_AS_STRING(format_spec),
4120 PyBytes_GET_SIZE(format_spec));
4121 if (PyUnicode_Check(format_spec)) {
4122 /* Convert format_spec to a str */
4123 PyObject *result;
4124 PyObject *str_spec = PyObject_Str(format_spec);
4125
4126 if (str_spec == NULL)
4127 return NULL;
4128
4129 result = _PyLong_FormatAdvanced(self,
4130 PyBytes_AS_STRING(str_spec),
4131 PyBytes_GET_SIZE(str_spec));
4132
4133 Py_DECREF(str_spec);
4134 return result;
4135 }
4136 PyErr_SetString(PyExc_TypeError, "__format__ requires str or unicode");
4137 return NULL;
4138 }
4139
4140 static PyObject *
long_sizeof(PyLongObject * v)4141 long_sizeof(PyLongObject *v)
4142 {
4143 Py_ssize_t res;
4144
4145 res = v->ob_type->tp_basicsize + ABS(Py_SIZE(v))*sizeof(digit);
4146 return PyInt_FromSsize_t(res);
4147 }
4148
4149 static PyObject *
long_bit_length(PyLongObject * v)4150 long_bit_length(PyLongObject *v)
4151 {
4152 PyLongObject *result, *x, *y;
4153 Py_ssize_t ndigits, msd_bits = 0;
4154 digit msd;
4155
4156 assert(v != NULL);
4157 assert(PyLong_Check(v));
4158
4159 ndigits = ABS(Py_SIZE(v));
4160 if (ndigits == 0)
4161 return PyInt_FromLong(0);
4162
4163 msd = v->ob_digit[ndigits-1];
4164 while (msd >= 32) {
4165 msd_bits += 6;
4166 msd >>= 6;
4167 }
4168 msd_bits += (long)(BitLengthTable[msd]);
4169
4170 if (ndigits <= PY_SSIZE_T_MAX/PyLong_SHIFT)
4171 return PyInt_FromSsize_t((ndigits-1)*PyLong_SHIFT + msd_bits);
4172
4173 /* expression above may overflow; use Python integers instead */
4174 result = (PyLongObject *)PyLong_FromSsize_t(ndigits - 1);
4175 if (result == NULL)
4176 return NULL;
4177 x = (PyLongObject *)PyLong_FromLong(PyLong_SHIFT);
4178 if (x == NULL)
4179 goto error;
4180 y = (PyLongObject *)long_mul(result, x);
4181 Py_DECREF(x);
4182 if (y == NULL)
4183 goto error;
4184 Py_DECREF(result);
4185 result = y;
4186
4187 x = (PyLongObject *)PyLong_FromLong((long)msd_bits);
4188 if (x == NULL)
4189 goto error;
4190 y = (PyLongObject *)long_add(result, x);
4191 Py_DECREF(x);
4192 if (y == NULL)
4193 goto error;
4194 Py_DECREF(result);
4195 result = y;
4196
4197 return (PyObject *)result;
4198
4199 error:
4200 Py_DECREF(result);
4201 return NULL;
4202 }
4203
4204 PyDoc_STRVAR(long_bit_length_doc,
4205 "long.bit_length() -> int or long\n\
4206 \n\
4207 Number of bits necessary to represent self in binary.\n\
4208 >>> bin(37L)\n\
4209 '0b100101'\n\
4210 >>> (37L).bit_length()\n\
4211 6");
4212
4213 #if 0
4214 static PyObject *
4215 long_is_finite(PyObject *v)
4216 {
4217 Py_RETURN_TRUE;
4218 }
4219 #endif
4220
4221 static PyMethodDef long_methods[] = {
4222 {"conjugate", (PyCFunction)long_long, METH_NOARGS,
4223 "Returns self, the complex conjugate of any long."},
4224 {"bit_length", (PyCFunction)long_bit_length, METH_NOARGS,
4225 long_bit_length_doc},
4226 #if 0
4227 {"is_finite", (PyCFunction)long_is_finite, METH_NOARGS,
4228 "Returns always True."},
4229 #endif
4230 {"__trunc__", (PyCFunction)long_long, METH_NOARGS,
4231 "Truncating an Integral returns itself."},
4232 {"__getnewargs__", (PyCFunction)long_getnewargs, METH_NOARGS},
4233 {"__format__", (PyCFunction)long__format__, METH_VARARGS},
4234 {"__sizeof__", (PyCFunction)long_sizeof, METH_NOARGS,
4235 "Returns size in memory, in bytes"},
4236 {NULL, NULL} /* sentinel */
4237 };
4238
4239 static PyGetSetDef long_getset[] = {
4240 {"real",
4241 (getter)long_long, (setter)NULL,
4242 "the real part of a complex number",
4243 NULL},
4244 {"imag",
4245 (getter)long_get0, (setter)NULL,
4246 "the imaginary part of a complex number",
4247 NULL},
4248 {"numerator",
4249 (getter)long_long, (setter)NULL,
4250 "the numerator of a rational number in lowest terms",
4251 NULL},
4252 {"denominator",
4253 (getter)long_get1, (setter)NULL,
4254 "the denominator of a rational number in lowest terms",
4255 NULL},
4256 {NULL} /* Sentinel */
4257 };
4258
4259 PyDoc_STRVAR(long_doc,
4260 "long(x=0) -> long\n\
4261 long(x, base=10) -> long\n\
4262 \n\
4263 Convert a number or string to a long integer, or return 0L if no arguments\n\
4264 are given. If x is floating point, the conversion truncates towards zero.\n\
4265 \n\
4266 If x is not a number or if base is given, then x must be a string or\n\
4267 Unicode object representing an integer literal in the given base. The\n\
4268 literal can be preceded by '+' or '-' and be surrounded by whitespace.\n\
4269 The base defaults to 10. Valid bases are 0 and 2-36. Base 0 means to\n\
4270 interpret the base from the string as an integer literal.\n\
4271 >>> int('0b100', base=0)\n\
4272 4L");
4273
4274 static PyNumberMethods long_as_number = {
4275 (binaryfunc)long_add, /*nb_add*/
4276 (binaryfunc)long_sub, /*nb_subtract*/
4277 (binaryfunc)long_mul, /*nb_multiply*/
4278 long_classic_div, /*nb_divide*/
4279 long_mod, /*nb_remainder*/
4280 long_divmod, /*nb_divmod*/
4281 long_pow, /*nb_power*/
4282 (unaryfunc)long_neg, /*nb_negative*/
4283 (unaryfunc)long_long, /*tp_positive*/
4284 (unaryfunc)long_abs, /*tp_absolute*/
4285 (inquiry)long_nonzero, /*tp_nonzero*/
4286 (unaryfunc)long_invert, /*nb_invert*/
4287 long_lshift, /*nb_lshift*/
4288 (binaryfunc)long_rshift, /*nb_rshift*/
4289 long_and, /*nb_and*/
4290 long_xor, /*nb_xor*/
4291 long_or, /*nb_or*/
4292 long_coerce, /*nb_coerce*/
4293 long_int, /*nb_int*/
4294 long_long, /*nb_long*/
4295 long_float, /*nb_float*/
4296 long_oct, /*nb_oct*/
4297 long_hex, /*nb_hex*/
4298 0, /* nb_inplace_add */
4299 0, /* nb_inplace_subtract */
4300 0, /* nb_inplace_multiply */
4301 0, /* nb_inplace_divide */
4302 0, /* nb_inplace_remainder */
4303 0, /* nb_inplace_power */
4304 0, /* nb_inplace_lshift */
4305 0, /* nb_inplace_rshift */
4306 0, /* nb_inplace_and */
4307 0, /* nb_inplace_xor */
4308 0, /* nb_inplace_or */
4309 long_div, /* nb_floor_divide */
4310 long_true_divide, /* nb_true_divide */
4311 0, /* nb_inplace_floor_divide */
4312 0, /* nb_inplace_true_divide */
4313 long_long, /* nb_index */
4314 };
4315
4316 PyTypeObject PyLong_Type = {
4317 PyObject_HEAD_INIT(&PyType_Type)
4318 0, /* ob_size */
4319 "long", /* tp_name */
4320 offsetof(PyLongObject, ob_digit), /* tp_basicsize */
4321 sizeof(digit), /* tp_itemsize */
4322 long_dealloc, /* tp_dealloc */
4323 0, /* tp_print */
4324 0, /* tp_getattr */
4325 0, /* tp_setattr */
4326 (cmpfunc)long_compare, /* tp_compare */
4327 long_repr, /* tp_repr */
4328 &long_as_number, /* tp_as_number */
4329 0, /* tp_as_sequence */
4330 0, /* tp_as_mapping */
4331 (hashfunc)long_hash, /* tp_hash */
4332 0, /* tp_call */
4333 long_str, /* tp_str */
4334 PyObject_GenericGetAttr, /* tp_getattro */
4335 0, /* tp_setattro */
4336 0, /* tp_as_buffer */
4337 Py_TPFLAGS_DEFAULT | Py_TPFLAGS_CHECKTYPES |
4338 Py_TPFLAGS_BASETYPE | Py_TPFLAGS_LONG_SUBCLASS, /* tp_flags */
4339 long_doc, /* tp_doc */
4340 0, /* tp_traverse */
4341 0, /* tp_clear */
4342 0, /* tp_richcompare */
4343 0, /* tp_weaklistoffset */
4344 0, /* tp_iter */
4345 0, /* tp_iternext */
4346 long_methods, /* tp_methods */
4347 0, /* tp_members */
4348 long_getset, /* tp_getset */
4349 0, /* tp_base */
4350 0, /* tp_dict */
4351 0, /* tp_descr_get */
4352 0, /* tp_descr_set */
4353 0, /* tp_dictoffset */
4354 0, /* tp_init */
4355 0, /* tp_alloc */
4356 long_new, /* tp_new */
4357 PyObject_Del, /* tp_free */
4358 };
4359
4360 static PyTypeObject Long_InfoType;
4361
4362 PyDoc_STRVAR(long_info__doc__,
4363 "sys.long_info\n\
4364 \n\
4365 A struct sequence that holds information about Python's\n\
4366 internal representation of integers. The attributes are read only.");
4367
4368 static PyStructSequence_Field long_info_fields[] = {
4369 {"bits_per_digit", "size of a digit in bits"},
4370 {"sizeof_digit", "size in bytes of the C type used to represent a digit"},
4371 {NULL, NULL}
4372 };
4373
4374 static PyStructSequence_Desc long_info_desc = {
4375 "sys.long_info", /* name */
4376 long_info__doc__, /* doc */
4377 long_info_fields, /* fields */
4378 2 /* number of fields */
4379 };
4380
4381 PyObject *
PyLong_GetInfo(void)4382 PyLong_GetInfo(void)
4383 {
4384 PyObject* long_info;
4385 int field = 0;
4386 long_info = PyStructSequence_New(&Long_InfoType);
4387 if (long_info == NULL)
4388 return NULL;
4389 PyStructSequence_SET_ITEM(long_info, field++,
4390 PyInt_FromLong(PyLong_SHIFT));
4391 PyStructSequence_SET_ITEM(long_info, field++,
4392 PyInt_FromLong(sizeof(digit)));
4393 if (PyErr_Occurred()) {
4394 Py_CLEAR(long_info);
4395 return NULL;
4396 }
4397 return long_info;
4398 }
4399
4400 int
_PyLong_Init(void)4401 _PyLong_Init(void)
4402 {
4403 /* initialize long_info */
4404 if (Long_InfoType.tp_name == 0)
4405 PyStructSequence_InitType(&Long_InfoType, &long_info_desc);
4406 return 1;
4407 }
4408