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 "pycore_bitutils.h" // _Py_popcount32()
7 #include "pycore_initconfig.h" // _Py_global_config_int_max_str_digits
8 #include "pycore_interp.h" // _PY_NSMALLPOSINTS
9 #include "pycore_long.h" // __PyLong_GetSmallInt_internal()
10 #include "pycore_object.h" // _PyObject_InitVar()
11 #include "pycore_pystate.h" // _Py_IsMainInterpreter()
12 #include "longintrepr.h"
13
14 #include <float.h>
15 #include <ctype.h>
16 #include <stddef.h>
17
18 #include "clinic/longobject.c.h"
19 /*[clinic input]
20 class int "PyObject *" "&PyLong_Type"
21 [clinic start generated code]*/
22 /*[clinic end generated code: output=da39a3ee5e6b4b0d input=ec0275e3422a36e3]*/
23
24 #define NSMALLNEGINTS _PY_NSMALLNEGINTS
25 #define NSMALLPOSINTS _PY_NSMALLPOSINTS
26
27 _Py_IDENTIFIER(little);
28 _Py_IDENTIFIER(big);
29
30 /* convert a PyLong of size 1, 0 or -1 to an sdigit */
31 #define MEDIUM_VALUE(x) (assert(-1 <= Py_SIZE(x) && Py_SIZE(x) <= 1), \
32 Py_SIZE(x) < 0 ? -(sdigit)(x)->ob_digit[0] : \
33 (Py_SIZE(x) == 0 ? (sdigit)0 : \
34 (sdigit)(x)->ob_digit[0]))
35
36 #define IS_SMALL_INT(ival) (-NSMALLNEGINTS <= (ival) && (ival) < NSMALLPOSINTS)
37 #define IS_SMALL_UINT(ival) ((ival) < NSMALLPOSINTS)
38
39 #define _MAX_STR_DIGITS_ERROR_FMT "Exceeds the limit (%d) for integer string conversion: value has %zd digits"
40
41 static PyObject *
get_small_int(sdigit ival)42 get_small_int(sdigit ival)
43 {
44 assert(IS_SMALL_INT(ival));
45 PyObject *v = __PyLong_GetSmallInt_internal(ival);
46 Py_INCREF(v);
47 return v;
48 }
49
50 static PyLongObject *
maybe_small_long(PyLongObject * v)51 maybe_small_long(PyLongObject *v)
52 {
53 if (v && Py_ABS(Py_SIZE(v)) <= 1) {
54 sdigit ival = MEDIUM_VALUE(v);
55 if (IS_SMALL_INT(ival)) {
56 Py_DECREF(v);
57 return (PyLongObject *)get_small_int(ival);
58 }
59 }
60 return v;
61 }
62
63 /* If a freshly-allocated int is already shared, it must
64 be a small integer, so negating it must go to PyLong_FromLong */
65 Py_LOCAL_INLINE(void)
_PyLong_Negate(PyLongObject ** x_p)66 _PyLong_Negate(PyLongObject **x_p)
67 {
68 PyLongObject *x;
69
70 x = (PyLongObject *)*x_p;
71 if (Py_REFCNT(x) == 1) {
72 Py_SET_SIZE(x, -Py_SIZE(x));
73 return;
74 }
75
76 *x_p = (PyLongObject *)PyLong_FromLong(-MEDIUM_VALUE(x));
77 Py_DECREF(x);
78 }
79
80 /* For int multiplication, use the O(N**2) school algorithm unless
81 * both operands contain more than KARATSUBA_CUTOFF digits (this
82 * being an internal Python int digit, in base BASE).
83 */
84 #define KARATSUBA_CUTOFF 70
85 #define KARATSUBA_SQUARE_CUTOFF (2 * KARATSUBA_CUTOFF)
86
87 /* For exponentiation, use the binary left-to-right algorithm
88 * unless the exponent contains more than FIVEARY_CUTOFF digits.
89 * In that case, do 5 bits at a time. The potential drawback is that
90 * a table of 2**5 intermediate results is computed.
91 */
92 #define FIVEARY_CUTOFF 8
93
94 #define SIGCHECK(PyTryBlock) \
95 do { \
96 if (PyErr_CheckSignals()) PyTryBlock \
97 } while(0)
98
99 /* Normalize (remove leading zeros from) an int object.
100 Doesn't attempt to free the storage--in most cases, due to the nature
101 of the algorithms used, this could save at most be one word anyway. */
102
103 static PyLongObject *
long_normalize(PyLongObject * v)104 long_normalize(PyLongObject *v)
105 {
106 Py_ssize_t j = Py_ABS(Py_SIZE(v));
107 Py_ssize_t i = j;
108
109 while (i > 0 && v->ob_digit[i-1] == 0)
110 --i;
111 if (i != j) {
112 Py_SET_SIZE(v, (Py_SIZE(v) < 0) ? -(i) : i);
113 }
114 return v;
115 }
116
117 /* Allocate a new int object with size digits.
118 Return NULL and set exception if we run out of memory. */
119
120 #define MAX_LONG_DIGITS \
121 ((PY_SSIZE_T_MAX - offsetof(PyLongObject, ob_digit))/sizeof(digit))
122
123 PyLongObject *
_PyLong_New(Py_ssize_t size)124 _PyLong_New(Py_ssize_t size)
125 {
126 PyLongObject *result;
127 /* Number of bytes needed is: offsetof(PyLongObject, ob_digit) +
128 sizeof(digit)*size. Previous incarnations of this code used
129 sizeof(PyVarObject) instead of the offsetof, but this risks being
130 incorrect in the presence of padding between the PyVarObject header
131 and the digits. */
132 if (size > (Py_ssize_t)MAX_LONG_DIGITS) {
133 PyErr_SetString(PyExc_OverflowError,
134 "too many digits in integer");
135 return NULL;
136 }
137 result = PyObject_Malloc(offsetof(PyLongObject, ob_digit) +
138 size*sizeof(digit));
139 if (!result) {
140 PyErr_NoMemory();
141 return NULL;
142 }
143 _PyObject_InitVar((PyVarObject*)result, &PyLong_Type, size);
144 return result;
145 }
146
147 PyObject *
_PyLong_Copy(PyLongObject * src)148 _PyLong_Copy(PyLongObject *src)
149 {
150 PyLongObject *result;
151 Py_ssize_t i;
152
153 assert(src != NULL);
154 i = Py_SIZE(src);
155 if (i < 0)
156 i = -(i);
157 if (i < 2) {
158 sdigit ival = MEDIUM_VALUE(src);
159 if (IS_SMALL_INT(ival)) {
160 return get_small_int(ival);
161 }
162 }
163 result = _PyLong_New(i);
164 if (result != NULL) {
165 Py_SET_SIZE(result, Py_SIZE(src));
166 while (--i >= 0) {
167 result->ob_digit[i] = src->ob_digit[i];
168 }
169 }
170 return (PyObject *)result;
171 }
172
173 /* Create a new int object from a C long int */
174
175 PyObject *
PyLong_FromLong(long ival)176 PyLong_FromLong(long ival)
177 {
178 PyLongObject *v;
179 unsigned long abs_ival;
180 unsigned long t; /* unsigned so >> doesn't propagate sign bit */
181 int ndigits = 0;
182 int sign;
183
184 if (IS_SMALL_INT(ival)) {
185 return get_small_int((sdigit)ival);
186 }
187
188 if (ival < 0) {
189 /* negate: can't write this as abs_ival = -ival since that
190 invokes undefined behaviour when ival is LONG_MIN */
191 abs_ival = 0U-(unsigned long)ival;
192 sign = -1;
193 }
194 else {
195 abs_ival = (unsigned long)ival;
196 sign = ival == 0 ? 0 : 1;
197 }
198
199 /* Fast path for single-digit ints */
200 if (!(abs_ival >> PyLong_SHIFT)) {
201 v = _PyLong_New(1);
202 if (v) {
203 Py_SET_SIZE(v, sign);
204 v->ob_digit[0] = Py_SAFE_DOWNCAST(
205 abs_ival, unsigned long, digit);
206 }
207 return (PyObject*)v;
208 }
209
210 #if PyLong_SHIFT==15
211 /* 2 digits */
212 if (!(abs_ival >> 2*PyLong_SHIFT)) {
213 v = _PyLong_New(2);
214 if (v) {
215 Py_SET_SIZE(v, 2 * sign);
216 v->ob_digit[0] = Py_SAFE_DOWNCAST(
217 abs_ival & PyLong_MASK, unsigned long, digit);
218 v->ob_digit[1] = Py_SAFE_DOWNCAST(
219 abs_ival >> PyLong_SHIFT, unsigned long, digit);
220 }
221 return (PyObject*)v;
222 }
223 #endif
224
225 /* Larger numbers: loop to determine number of digits */
226 t = abs_ival;
227 while (t) {
228 ++ndigits;
229 t >>= PyLong_SHIFT;
230 }
231 v = _PyLong_New(ndigits);
232 if (v != NULL) {
233 digit *p = v->ob_digit;
234 Py_SET_SIZE(v, ndigits * sign);
235 t = abs_ival;
236 while (t) {
237 *p++ = Py_SAFE_DOWNCAST(
238 t & PyLong_MASK, unsigned long, digit);
239 t >>= PyLong_SHIFT;
240 }
241 }
242 return (PyObject *)v;
243 }
244
245 #define PYLONG_FROM_UINT(INT_TYPE, ival) \
246 do { \
247 if (IS_SMALL_UINT(ival)) { \
248 return get_small_int((sdigit)(ival)); \
249 } \
250 /* Count the number of Python digits. */ \
251 Py_ssize_t ndigits = 0; \
252 INT_TYPE t = (ival); \
253 while (t) { \
254 ++ndigits; \
255 t >>= PyLong_SHIFT; \
256 } \
257 PyLongObject *v = _PyLong_New(ndigits); \
258 if (v == NULL) { \
259 return NULL; \
260 } \
261 digit *p = v->ob_digit; \
262 while ((ival)) { \
263 *p++ = (digit)((ival) & PyLong_MASK); \
264 (ival) >>= PyLong_SHIFT; \
265 } \
266 return (PyObject *)v; \
267 } while(0)
268
269 /* Create a new int object from a C unsigned long int */
270
271 PyObject *
PyLong_FromUnsignedLong(unsigned long ival)272 PyLong_FromUnsignedLong(unsigned long ival)
273 {
274 PYLONG_FROM_UINT(unsigned long, ival);
275 }
276
277 /* Create a new int object from a C unsigned long long int. */
278
279 PyObject *
PyLong_FromUnsignedLongLong(unsigned long long ival)280 PyLong_FromUnsignedLongLong(unsigned long long ival)
281 {
282 PYLONG_FROM_UINT(unsigned long long, ival);
283 }
284
285 /* Create a new int object from a C size_t. */
286
287 PyObject *
PyLong_FromSize_t(size_t ival)288 PyLong_FromSize_t(size_t ival)
289 {
290 PYLONG_FROM_UINT(size_t, ival);
291 }
292
293 /* Create a new int object from a C double */
294
295 PyObject *
PyLong_FromDouble(double dval)296 PyLong_FromDouble(double dval)
297 {
298 /* Try to get out cheap if this fits in a long. When a finite value of real
299 * floating type is converted to an integer type, the value is truncated
300 * toward zero. If the value of the integral part cannot be represented by
301 * the integer type, the behavior is undefined. Thus, we must check that
302 * value is in range (LONG_MIN - 1, LONG_MAX + 1). If a long has more bits
303 * of precision than a double, casting LONG_MIN - 1 to double may yield an
304 * approximation, but LONG_MAX + 1 is a power of two and can be represented
305 * as double exactly (assuming FLT_RADIX is 2 or 16), so for simplicity
306 * check against [-(LONG_MAX + 1), LONG_MAX + 1).
307 */
308 const double int_max = (unsigned long)LONG_MAX + 1;
309 if (-int_max < dval && dval < int_max) {
310 return PyLong_FromLong((long)dval);
311 }
312
313 PyLongObject *v;
314 double frac;
315 int i, ndig, expo, neg;
316 neg = 0;
317 if (Py_IS_INFINITY(dval)) {
318 PyErr_SetString(PyExc_OverflowError,
319 "cannot convert float infinity to integer");
320 return NULL;
321 }
322 if (Py_IS_NAN(dval)) {
323 PyErr_SetString(PyExc_ValueError,
324 "cannot convert float NaN to integer");
325 return NULL;
326 }
327 if (dval < 0.0) {
328 neg = 1;
329 dval = -dval;
330 }
331 frac = frexp(dval, &expo); /* dval = frac*2**expo; 0.0 <= frac < 1.0 */
332 assert(expo > 0);
333 ndig = (expo-1) / PyLong_SHIFT + 1; /* Number of 'digits' in result */
334 v = _PyLong_New(ndig);
335 if (v == NULL)
336 return NULL;
337 frac = ldexp(frac, (expo-1) % PyLong_SHIFT + 1);
338 for (i = ndig; --i >= 0; ) {
339 digit bits = (digit)frac;
340 v->ob_digit[i] = bits;
341 frac = frac - (double)bits;
342 frac = ldexp(frac, PyLong_SHIFT);
343 }
344 if (neg) {
345 Py_SET_SIZE(v, -(Py_SIZE(v)));
346 }
347 return (PyObject *)v;
348 }
349
350 /* Checking for overflow in PyLong_AsLong is a PITA since C doesn't define
351 * anything about what happens when a signed integer operation overflows,
352 * and some compilers think they're doing you a favor by being "clever"
353 * then. The bit pattern for the largest positive signed long is
354 * (unsigned long)LONG_MAX, and for the smallest negative signed long
355 * it is abs(LONG_MIN), which we could write -(unsigned long)LONG_MIN.
356 * However, some other compilers warn about applying unary minus to an
357 * unsigned operand. Hence the weird "0-".
358 */
359 #define PY_ABS_LONG_MIN (0-(unsigned long)LONG_MIN)
360 #define PY_ABS_SSIZE_T_MIN (0-(size_t)PY_SSIZE_T_MIN)
361
362 /* Get a C long int from an int object or any object that has an __index__
363 method.
364
365 On overflow, return -1 and set *overflow to 1 or -1 depending on the sign of
366 the result. Otherwise *overflow is 0.
367
368 For other errors (e.g., TypeError), return -1 and set an error condition.
369 In this case *overflow will be 0.
370 */
371
372 long
PyLong_AsLongAndOverflow(PyObject * vv,int * overflow)373 PyLong_AsLongAndOverflow(PyObject *vv, int *overflow)
374 {
375 /* This version by Tim Peters */
376 PyLongObject *v;
377 unsigned long x, prev;
378 long res;
379 Py_ssize_t i;
380 int sign;
381 int do_decref = 0; /* if PyNumber_Index was called */
382
383 *overflow = 0;
384 if (vv == NULL) {
385 PyErr_BadInternalCall();
386 return -1;
387 }
388
389 if (PyLong_Check(vv)) {
390 v = (PyLongObject *)vv;
391 }
392 else {
393 v = (PyLongObject *)_PyNumber_Index(vv);
394 if (v == NULL)
395 return -1;
396 do_decref = 1;
397 }
398
399 res = -1;
400 i = Py_SIZE(v);
401
402 switch (i) {
403 case -1:
404 res = -(sdigit)v->ob_digit[0];
405 break;
406 case 0:
407 res = 0;
408 break;
409 case 1:
410 res = v->ob_digit[0];
411 break;
412 default:
413 sign = 1;
414 x = 0;
415 if (i < 0) {
416 sign = -1;
417 i = -(i);
418 }
419 while (--i >= 0) {
420 prev = x;
421 x = (x << PyLong_SHIFT) | v->ob_digit[i];
422 if ((x >> PyLong_SHIFT) != prev) {
423 *overflow = sign;
424 goto exit;
425 }
426 }
427 /* Haven't lost any bits, but casting to long requires extra
428 * care (see comment above).
429 */
430 if (x <= (unsigned long)LONG_MAX) {
431 res = (long)x * sign;
432 }
433 else if (sign < 0 && x == PY_ABS_LONG_MIN) {
434 res = LONG_MIN;
435 }
436 else {
437 *overflow = sign;
438 /* res is already set to -1 */
439 }
440 }
441 exit:
442 if (do_decref) {
443 Py_DECREF(v);
444 }
445 return res;
446 }
447
448 /* Get a C long int from an int object or any object that has an __index__
449 method. Return -1 and set an error if overflow occurs. */
450
451 long
PyLong_AsLong(PyObject * obj)452 PyLong_AsLong(PyObject *obj)
453 {
454 int overflow;
455 long result = PyLong_AsLongAndOverflow(obj, &overflow);
456 if (overflow) {
457 /* XXX: could be cute and give a different
458 message for overflow == -1 */
459 PyErr_SetString(PyExc_OverflowError,
460 "Python int too large to convert to C long");
461 }
462 return result;
463 }
464
465 /* Get a C int from an int object or any object that has an __index__
466 method. Return -1 and set an error if overflow occurs. */
467
468 int
_PyLong_AsInt(PyObject * obj)469 _PyLong_AsInt(PyObject *obj)
470 {
471 int overflow;
472 long result = PyLong_AsLongAndOverflow(obj, &overflow);
473 if (overflow || result > INT_MAX || result < INT_MIN) {
474 /* XXX: could be cute and give a different
475 message for overflow == -1 */
476 PyErr_SetString(PyExc_OverflowError,
477 "Python int too large to convert to C int");
478 return -1;
479 }
480 return (int)result;
481 }
482
483 /* Get a Py_ssize_t from an int object.
484 Returns -1 and sets an error condition if overflow occurs. */
485
486 Py_ssize_t
PyLong_AsSsize_t(PyObject * vv)487 PyLong_AsSsize_t(PyObject *vv) {
488 PyLongObject *v;
489 size_t x, prev;
490 Py_ssize_t i;
491 int sign;
492
493 if (vv == NULL) {
494 PyErr_BadInternalCall();
495 return -1;
496 }
497 if (!PyLong_Check(vv)) {
498 PyErr_SetString(PyExc_TypeError, "an integer is required");
499 return -1;
500 }
501
502 v = (PyLongObject *)vv;
503 i = Py_SIZE(v);
504 switch (i) {
505 case -1: return -(sdigit)v->ob_digit[0];
506 case 0: return 0;
507 case 1: return v->ob_digit[0];
508 }
509 sign = 1;
510 x = 0;
511 if (i < 0) {
512 sign = -1;
513 i = -(i);
514 }
515 while (--i >= 0) {
516 prev = x;
517 x = (x << PyLong_SHIFT) | v->ob_digit[i];
518 if ((x >> PyLong_SHIFT) != prev)
519 goto overflow;
520 }
521 /* Haven't lost any bits, but casting to a signed type requires
522 * extra care (see comment above).
523 */
524 if (x <= (size_t)PY_SSIZE_T_MAX) {
525 return (Py_ssize_t)x * sign;
526 }
527 else if (sign < 0 && x == PY_ABS_SSIZE_T_MIN) {
528 return PY_SSIZE_T_MIN;
529 }
530 /* else overflow */
531
532 overflow:
533 PyErr_SetString(PyExc_OverflowError,
534 "Python int too large to convert to C ssize_t");
535 return -1;
536 }
537
538 /* Get a C unsigned long int from an int object.
539 Returns -1 and sets an error condition if overflow occurs. */
540
541 unsigned long
PyLong_AsUnsignedLong(PyObject * vv)542 PyLong_AsUnsignedLong(PyObject *vv)
543 {
544 PyLongObject *v;
545 unsigned long x, prev;
546 Py_ssize_t i;
547
548 if (vv == NULL) {
549 PyErr_BadInternalCall();
550 return (unsigned long)-1;
551 }
552 if (!PyLong_Check(vv)) {
553 PyErr_SetString(PyExc_TypeError, "an integer is required");
554 return (unsigned long)-1;
555 }
556
557 v = (PyLongObject *)vv;
558 i = Py_SIZE(v);
559 x = 0;
560 if (i < 0) {
561 PyErr_SetString(PyExc_OverflowError,
562 "can't convert negative value to unsigned int");
563 return (unsigned long) -1;
564 }
565 switch (i) {
566 case 0: return 0;
567 case 1: return v->ob_digit[0];
568 }
569 while (--i >= 0) {
570 prev = x;
571 x = (x << PyLong_SHIFT) | v->ob_digit[i];
572 if ((x >> PyLong_SHIFT) != prev) {
573 PyErr_SetString(PyExc_OverflowError,
574 "Python int too large to convert "
575 "to C unsigned long");
576 return (unsigned long) -1;
577 }
578 }
579 return x;
580 }
581
582 /* Get a C size_t from an int object. Returns (size_t)-1 and sets
583 an error condition if overflow occurs. */
584
585 size_t
PyLong_AsSize_t(PyObject * vv)586 PyLong_AsSize_t(PyObject *vv)
587 {
588 PyLongObject *v;
589 size_t x, prev;
590 Py_ssize_t i;
591
592 if (vv == NULL) {
593 PyErr_BadInternalCall();
594 return (size_t) -1;
595 }
596 if (!PyLong_Check(vv)) {
597 PyErr_SetString(PyExc_TypeError, "an integer is required");
598 return (size_t)-1;
599 }
600
601 v = (PyLongObject *)vv;
602 i = Py_SIZE(v);
603 x = 0;
604 if (i < 0) {
605 PyErr_SetString(PyExc_OverflowError,
606 "can't convert negative value to size_t");
607 return (size_t) -1;
608 }
609 switch (i) {
610 case 0: return 0;
611 case 1: return v->ob_digit[0];
612 }
613 while (--i >= 0) {
614 prev = x;
615 x = (x << PyLong_SHIFT) | v->ob_digit[i];
616 if ((x >> PyLong_SHIFT) != prev) {
617 PyErr_SetString(PyExc_OverflowError,
618 "Python int too large to convert to C size_t");
619 return (size_t) -1;
620 }
621 }
622 return x;
623 }
624
625 /* Get a C unsigned long int from an int object, ignoring the high bits.
626 Returns -1 and sets an error condition if an error occurs. */
627
628 static unsigned long
_PyLong_AsUnsignedLongMask(PyObject * vv)629 _PyLong_AsUnsignedLongMask(PyObject *vv)
630 {
631 PyLongObject *v;
632 unsigned long x;
633 Py_ssize_t i;
634 int sign;
635
636 if (vv == NULL || !PyLong_Check(vv)) {
637 PyErr_BadInternalCall();
638 return (unsigned long) -1;
639 }
640 v = (PyLongObject *)vv;
641 i = Py_SIZE(v);
642 switch (i) {
643 case 0: return 0;
644 case 1: return v->ob_digit[0];
645 }
646 sign = 1;
647 x = 0;
648 if (i < 0) {
649 sign = -1;
650 i = -i;
651 }
652 while (--i >= 0) {
653 x = (x << PyLong_SHIFT) | v->ob_digit[i];
654 }
655 return x * sign;
656 }
657
658 unsigned long
PyLong_AsUnsignedLongMask(PyObject * op)659 PyLong_AsUnsignedLongMask(PyObject *op)
660 {
661 PyLongObject *lo;
662 unsigned long val;
663
664 if (op == NULL) {
665 PyErr_BadInternalCall();
666 return (unsigned long)-1;
667 }
668
669 if (PyLong_Check(op)) {
670 return _PyLong_AsUnsignedLongMask(op);
671 }
672
673 lo = (PyLongObject *)_PyNumber_Index(op);
674 if (lo == NULL)
675 return (unsigned long)-1;
676
677 val = _PyLong_AsUnsignedLongMask((PyObject *)lo);
678 Py_DECREF(lo);
679 return val;
680 }
681
682 int
_PyLong_Sign(PyObject * vv)683 _PyLong_Sign(PyObject *vv)
684 {
685 PyLongObject *v = (PyLongObject *)vv;
686
687 assert(v != NULL);
688 assert(PyLong_Check(v));
689
690 return Py_SIZE(v) == 0 ? 0 : (Py_SIZE(v) < 0 ? -1 : 1);
691 }
692
693 static int
bit_length_digit(digit x)694 bit_length_digit(digit x)
695 {
696 Py_BUILD_ASSERT(PyLong_SHIFT <= sizeof(unsigned long) * 8);
697 return _Py_bit_length((unsigned long)x);
698 }
699
700 size_t
_PyLong_NumBits(PyObject * vv)701 _PyLong_NumBits(PyObject *vv)
702 {
703 PyLongObject *v = (PyLongObject *)vv;
704 size_t result = 0;
705 Py_ssize_t ndigits;
706 int msd_bits;
707
708 assert(v != NULL);
709 assert(PyLong_Check(v));
710 ndigits = Py_ABS(Py_SIZE(v));
711 assert(ndigits == 0 || v->ob_digit[ndigits - 1] != 0);
712 if (ndigits > 0) {
713 digit msd = v->ob_digit[ndigits - 1];
714 if ((size_t)(ndigits - 1) > SIZE_MAX / (size_t)PyLong_SHIFT)
715 goto Overflow;
716 result = (size_t)(ndigits - 1) * (size_t)PyLong_SHIFT;
717 msd_bits = bit_length_digit(msd);
718 if (SIZE_MAX - msd_bits < result)
719 goto Overflow;
720 result += msd_bits;
721 }
722 return result;
723
724 Overflow:
725 PyErr_SetString(PyExc_OverflowError, "int has too many bits "
726 "to express in a platform size_t");
727 return (size_t)-1;
728 }
729
730 PyObject *
_PyLong_FromByteArray(const unsigned char * bytes,size_t n,int little_endian,int is_signed)731 _PyLong_FromByteArray(const unsigned char* bytes, size_t n,
732 int little_endian, int is_signed)
733 {
734 const unsigned char* pstartbyte; /* LSB of bytes */
735 int incr; /* direction to move pstartbyte */
736 const unsigned char* pendbyte; /* MSB of bytes */
737 size_t numsignificantbytes; /* number of bytes that matter */
738 Py_ssize_t ndigits; /* number of Python int digits */
739 PyLongObject* v; /* result */
740 Py_ssize_t idigit = 0; /* next free index in v->ob_digit */
741
742 if (n == 0)
743 return PyLong_FromLong(0L);
744
745 if (little_endian) {
746 pstartbyte = bytes;
747 pendbyte = bytes + n - 1;
748 incr = 1;
749 }
750 else {
751 pstartbyte = bytes + n - 1;
752 pendbyte = bytes;
753 incr = -1;
754 }
755
756 if (is_signed)
757 is_signed = *pendbyte >= 0x80;
758
759 /* Compute numsignificantbytes. This consists of finding the most
760 significant byte. Leading 0 bytes are insignificant if the number
761 is positive, and leading 0xff bytes if negative. */
762 {
763 size_t i;
764 const unsigned char* p = pendbyte;
765 const int pincr = -incr; /* search MSB to LSB */
766 const unsigned char insignificant = is_signed ? 0xff : 0x00;
767
768 for (i = 0; i < n; ++i, p += pincr) {
769 if (*p != insignificant)
770 break;
771 }
772 numsignificantbytes = n - i;
773 /* 2's-comp is a bit tricky here, e.g. 0xff00 == -0x0100, so
774 actually has 2 significant bytes. OTOH, 0xff0001 ==
775 -0x00ffff, so we wouldn't *need* to bump it there; but we
776 do for 0xffff = -0x0001. To be safe without bothering to
777 check every case, bump it regardless. */
778 if (is_signed && numsignificantbytes < n)
779 ++numsignificantbytes;
780 }
781
782 /* How many Python int digits do we need? We have
783 8*numsignificantbytes bits, and each Python int digit has
784 PyLong_SHIFT bits, so it's the ceiling of the quotient. */
785 /* catch overflow before it happens */
786 if (numsignificantbytes > (PY_SSIZE_T_MAX - PyLong_SHIFT) / 8) {
787 PyErr_SetString(PyExc_OverflowError,
788 "byte array too long to convert to int");
789 return NULL;
790 }
791 ndigits = (numsignificantbytes * 8 + PyLong_SHIFT - 1) / PyLong_SHIFT;
792 v = _PyLong_New(ndigits);
793 if (v == NULL)
794 return NULL;
795
796 /* Copy the bits over. The tricky parts are computing 2's-comp on
797 the fly for signed numbers, and dealing with the mismatch between
798 8-bit bytes and (probably) 15-bit Python digits.*/
799 {
800 size_t i;
801 twodigits carry = 1; /* for 2's-comp calculation */
802 twodigits accum = 0; /* sliding register */
803 unsigned int accumbits = 0; /* number of bits in accum */
804 const unsigned char* p = pstartbyte;
805
806 for (i = 0; i < numsignificantbytes; ++i, p += incr) {
807 twodigits thisbyte = *p;
808 /* Compute correction for 2's comp, if needed. */
809 if (is_signed) {
810 thisbyte = (0xff ^ thisbyte) + carry;
811 carry = thisbyte >> 8;
812 thisbyte &= 0xff;
813 }
814 /* Because we're going LSB to MSB, thisbyte is
815 more significant than what's already in accum,
816 so needs to be prepended to accum. */
817 accum |= thisbyte << accumbits;
818 accumbits += 8;
819 if (accumbits >= PyLong_SHIFT) {
820 /* There's enough to fill a Python digit. */
821 assert(idigit < ndigits);
822 v->ob_digit[idigit] = (digit)(accum & PyLong_MASK);
823 ++idigit;
824 accum >>= PyLong_SHIFT;
825 accumbits -= PyLong_SHIFT;
826 assert(accumbits < PyLong_SHIFT);
827 }
828 }
829 assert(accumbits < PyLong_SHIFT);
830 if (accumbits) {
831 assert(idigit < ndigits);
832 v->ob_digit[idigit] = (digit)accum;
833 ++idigit;
834 }
835 }
836
837 Py_SET_SIZE(v, is_signed ? -idigit : idigit);
838 return (PyObject *)long_normalize(v);
839 }
840
841 int
_PyLong_AsByteArray(PyLongObject * v,unsigned char * bytes,size_t n,int little_endian,int is_signed)842 _PyLong_AsByteArray(PyLongObject* v,
843 unsigned char* bytes, size_t n,
844 int little_endian, int is_signed)
845 {
846 Py_ssize_t i; /* index into v->ob_digit */
847 Py_ssize_t ndigits; /* |v->ob_size| */
848 twodigits accum; /* sliding register */
849 unsigned int accumbits; /* # bits in accum */
850 int do_twos_comp; /* store 2's-comp? is_signed and v < 0 */
851 digit carry; /* for computing 2's-comp */
852 size_t j; /* # bytes filled */
853 unsigned char* p; /* pointer to next byte in bytes */
854 int pincr; /* direction to move p */
855
856 assert(v != NULL && PyLong_Check(v));
857
858 if (Py_SIZE(v) < 0) {
859 ndigits = -(Py_SIZE(v));
860 if (!is_signed) {
861 PyErr_SetString(PyExc_OverflowError,
862 "can't convert negative int to unsigned");
863 return -1;
864 }
865 do_twos_comp = 1;
866 }
867 else {
868 ndigits = Py_SIZE(v);
869 do_twos_comp = 0;
870 }
871
872 if (little_endian) {
873 p = bytes;
874 pincr = 1;
875 }
876 else {
877 p = bytes + n - 1;
878 pincr = -1;
879 }
880
881 /* Copy over all the Python digits.
882 It's crucial that every Python digit except for the MSD contribute
883 exactly PyLong_SHIFT bits to the total, so first assert that the int is
884 normalized. */
885 assert(ndigits == 0 || v->ob_digit[ndigits - 1] != 0);
886 j = 0;
887 accum = 0;
888 accumbits = 0;
889 carry = do_twos_comp ? 1 : 0;
890 for (i = 0; i < ndigits; ++i) {
891 digit thisdigit = v->ob_digit[i];
892 if (do_twos_comp) {
893 thisdigit = (thisdigit ^ PyLong_MASK) + carry;
894 carry = thisdigit >> PyLong_SHIFT;
895 thisdigit &= PyLong_MASK;
896 }
897 /* Because we're going LSB to MSB, thisdigit is more
898 significant than what's already in accum, so needs to be
899 prepended to accum. */
900 accum |= (twodigits)thisdigit << accumbits;
901
902 /* The most-significant digit may be (probably is) at least
903 partly empty. */
904 if (i == ndigits - 1) {
905 /* Count # of sign bits -- they needn't be stored,
906 * although for signed conversion we need later to
907 * make sure at least one sign bit gets stored. */
908 digit s = do_twos_comp ? thisdigit ^ PyLong_MASK : thisdigit;
909 while (s != 0) {
910 s >>= 1;
911 accumbits++;
912 }
913 }
914 else
915 accumbits += PyLong_SHIFT;
916
917 /* Store as many bytes as possible. */
918 while (accumbits >= 8) {
919 if (j >= n)
920 goto Overflow;
921 ++j;
922 *p = (unsigned char)(accum & 0xff);
923 p += pincr;
924 accumbits -= 8;
925 accum >>= 8;
926 }
927 }
928
929 /* Store the straggler (if any). */
930 assert(accumbits < 8);
931 assert(carry == 0); /* else do_twos_comp and *every* digit was 0 */
932 if (accumbits > 0) {
933 if (j >= n)
934 goto Overflow;
935 ++j;
936 if (do_twos_comp) {
937 /* Fill leading bits of the byte with sign bits
938 (appropriately pretending that the int had an
939 infinite supply of sign bits). */
940 accum |= (~(twodigits)0) << accumbits;
941 }
942 *p = (unsigned char)(accum & 0xff);
943 p += pincr;
944 }
945 else if (j == n && n > 0 && is_signed) {
946 /* The main loop filled the byte array exactly, so the code
947 just above didn't get to ensure there's a sign bit, and the
948 loop below wouldn't add one either. Make sure a sign bit
949 exists. */
950 unsigned char msb = *(p - pincr);
951 int sign_bit_set = msb >= 0x80;
952 assert(accumbits == 0);
953 if (sign_bit_set == do_twos_comp)
954 return 0;
955 else
956 goto Overflow;
957 }
958
959 /* Fill remaining bytes with copies of the sign bit. */
960 {
961 unsigned char signbyte = do_twos_comp ? 0xffU : 0U;
962 for ( ; j < n; ++j, p += pincr)
963 *p = signbyte;
964 }
965
966 return 0;
967
968 Overflow:
969 PyErr_SetString(PyExc_OverflowError, "int too big to convert");
970 return -1;
971
972 }
973
974 /* Create a new int object from a C pointer */
975
976 PyObject *
PyLong_FromVoidPtr(void * p)977 PyLong_FromVoidPtr(void *p)
978 {
979 #if SIZEOF_VOID_P <= SIZEOF_LONG
980 return PyLong_FromUnsignedLong((unsigned long)(uintptr_t)p);
981 #else
982
983 #if SIZEOF_LONG_LONG < SIZEOF_VOID_P
984 # error "PyLong_FromVoidPtr: sizeof(long long) < sizeof(void*)"
985 #endif
986 return PyLong_FromUnsignedLongLong((unsigned long long)(uintptr_t)p);
987 #endif /* SIZEOF_VOID_P <= SIZEOF_LONG */
988
989 }
990
991 /* Get a C pointer from an int object. */
992
993 void *
PyLong_AsVoidPtr(PyObject * vv)994 PyLong_AsVoidPtr(PyObject *vv)
995 {
996 #if SIZEOF_VOID_P <= SIZEOF_LONG
997 long x;
998
999 if (PyLong_Check(vv) && _PyLong_Sign(vv) < 0)
1000 x = PyLong_AsLong(vv);
1001 else
1002 x = PyLong_AsUnsignedLong(vv);
1003 #else
1004
1005 #if SIZEOF_LONG_LONG < SIZEOF_VOID_P
1006 # error "PyLong_AsVoidPtr: sizeof(long long) < sizeof(void*)"
1007 #endif
1008 long long x;
1009
1010 if (PyLong_Check(vv) && _PyLong_Sign(vv) < 0)
1011 x = PyLong_AsLongLong(vv);
1012 else
1013 x = PyLong_AsUnsignedLongLong(vv);
1014
1015 #endif /* SIZEOF_VOID_P <= SIZEOF_LONG */
1016
1017 if (x == -1 && PyErr_Occurred())
1018 return NULL;
1019 return (void *)x;
1020 }
1021
1022 /* Initial long long support by Chris Herborth (chrish@qnx.com), later
1023 * rewritten to use the newer PyLong_{As,From}ByteArray API.
1024 */
1025
1026 #define PY_ABS_LLONG_MIN (0-(unsigned long long)LLONG_MIN)
1027
1028 /* Create a new int object from a C long long int. */
1029
1030 PyObject *
PyLong_FromLongLong(long long ival)1031 PyLong_FromLongLong(long long ival)
1032 {
1033 PyLongObject *v;
1034 unsigned long long abs_ival;
1035 unsigned long long t; /* unsigned so >> doesn't propagate sign bit */
1036 int ndigits = 0;
1037 int negative = 0;
1038
1039 if (IS_SMALL_INT(ival)) {
1040 return get_small_int((sdigit)ival);
1041 }
1042
1043 if (ival < 0) {
1044 /* avoid signed overflow on negation; see comments
1045 in PyLong_FromLong above. */
1046 abs_ival = (unsigned long long)(-1-ival) + 1;
1047 negative = 1;
1048 }
1049 else {
1050 abs_ival = (unsigned long long)ival;
1051 }
1052
1053 /* Count the number of Python digits.
1054 We used to pick 5 ("big enough for anything"), but that's a
1055 waste of time and space given that 5*15 = 75 bits are rarely
1056 needed. */
1057 t = abs_ival;
1058 while (t) {
1059 ++ndigits;
1060 t >>= PyLong_SHIFT;
1061 }
1062 v = _PyLong_New(ndigits);
1063 if (v != NULL) {
1064 digit *p = v->ob_digit;
1065 Py_SET_SIZE(v, negative ? -ndigits : ndigits);
1066 t = abs_ival;
1067 while (t) {
1068 *p++ = (digit)(t & PyLong_MASK);
1069 t >>= PyLong_SHIFT;
1070 }
1071 }
1072 return (PyObject *)v;
1073 }
1074
1075 /* Create a new int object from a C Py_ssize_t. */
1076
1077 PyObject *
PyLong_FromSsize_t(Py_ssize_t ival)1078 PyLong_FromSsize_t(Py_ssize_t ival)
1079 {
1080 PyLongObject *v;
1081 size_t abs_ival;
1082 size_t t; /* unsigned so >> doesn't propagate sign bit */
1083 int ndigits = 0;
1084 int negative = 0;
1085
1086 if (IS_SMALL_INT(ival)) {
1087 return get_small_int((sdigit)ival);
1088 }
1089
1090 if (ival < 0) {
1091 /* avoid signed overflow when ival = SIZE_T_MIN */
1092 abs_ival = (size_t)(-1-ival)+1;
1093 negative = 1;
1094 }
1095 else {
1096 abs_ival = (size_t)ival;
1097 }
1098
1099 /* Count the number of Python digits. */
1100 t = abs_ival;
1101 while (t) {
1102 ++ndigits;
1103 t >>= PyLong_SHIFT;
1104 }
1105 v = _PyLong_New(ndigits);
1106 if (v != NULL) {
1107 digit *p = v->ob_digit;
1108 Py_SET_SIZE(v, negative ? -ndigits : ndigits);
1109 t = abs_ival;
1110 while (t) {
1111 *p++ = (digit)(t & PyLong_MASK);
1112 t >>= PyLong_SHIFT;
1113 }
1114 }
1115 return (PyObject *)v;
1116 }
1117
1118 /* Get a C long long int from an int object or any object that has an
1119 __index__ method. Return -1 and set an error if overflow occurs. */
1120
1121 long long
PyLong_AsLongLong(PyObject * vv)1122 PyLong_AsLongLong(PyObject *vv)
1123 {
1124 PyLongObject *v;
1125 long long bytes;
1126 int res;
1127 int do_decref = 0; /* if PyNumber_Index was called */
1128
1129 if (vv == NULL) {
1130 PyErr_BadInternalCall();
1131 return -1;
1132 }
1133
1134 if (PyLong_Check(vv)) {
1135 v = (PyLongObject *)vv;
1136 }
1137 else {
1138 v = (PyLongObject *)_PyNumber_Index(vv);
1139 if (v == NULL)
1140 return -1;
1141 do_decref = 1;
1142 }
1143
1144 res = 0;
1145 switch(Py_SIZE(v)) {
1146 case -1:
1147 bytes = -(sdigit)v->ob_digit[0];
1148 break;
1149 case 0:
1150 bytes = 0;
1151 break;
1152 case 1:
1153 bytes = v->ob_digit[0];
1154 break;
1155 default:
1156 res = _PyLong_AsByteArray((PyLongObject *)v, (unsigned char *)&bytes,
1157 SIZEOF_LONG_LONG, PY_LITTLE_ENDIAN, 1);
1158 }
1159 if (do_decref) {
1160 Py_DECREF(v);
1161 }
1162
1163 /* Plan 9 can't handle long long in ? : expressions */
1164 if (res < 0)
1165 return (long long)-1;
1166 else
1167 return bytes;
1168 }
1169
1170 /* Get a C unsigned long long int from an int object.
1171 Return -1 and set an error if overflow occurs. */
1172
1173 unsigned long long
PyLong_AsUnsignedLongLong(PyObject * vv)1174 PyLong_AsUnsignedLongLong(PyObject *vv)
1175 {
1176 PyLongObject *v;
1177 unsigned long long bytes;
1178 int res;
1179
1180 if (vv == NULL) {
1181 PyErr_BadInternalCall();
1182 return (unsigned long long)-1;
1183 }
1184 if (!PyLong_Check(vv)) {
1185 PyErr_SetString(PyExc_TypeError, "an integer is required");
1186 return (unsigned long long)-1;
1187 }
1188
1189 v = (PyLongObject*)vv;
1190 switch(Py_SIZE(v)) {
1191 case 0: return 0;
1192 case 1: return v->ob_digit[0];
1193 }
1194
1195 res = _PyLong_AsByteArray((PyLongObject *)vv, (unsigned char *)&bytes,
1196 SIZEOF_LONG_LONG, PY_LITTLE_ENDIAN, 0);
1197
1198 /* Plan 9 can't handle long long in ? : expressions */
1199 if (res < 0)
1200 return (unsigned long long)res;
1201 else
1202 return bytes;
1203 }
1204
1205 /* Get a C unsigned long int from an int object, ignoring the high bits.
1206 Returns -1 and sets an error condition if an error occurs. */
1207
1208 static unsigned long long
_PyLong_AsUnsignedLongLongMask(PyObject * vv)1209 _PyLong_AsUnsignedLongLongMask(PyObject *vv)
1210 {
1211 PyLongObject *v;
1212 unsigned long long x;
1213 Py_ssize_t i;
1214 int sign;
1215
1216 if (vv == NULL || !PyLong_Check(vv)) {
1217 PyErr_BadInternalCall();
1218 return (unsigned long long) -1;
1219 }
1220 v = (PyLongObject *)vv;
1221 switch(Py_SIZE(v)) {
1222 case 0: return 0;
1223 case 1: return v->ob_digit[0];
1224 }
1225 i = Py_SIZE(v);
1226 sign = 1;
1227 x = 0;
1228 if (i < 0) {
1229 sign = -1;
1230 i = -i;
1231 }
1232 while (--i >= 0) {
1233 x = (x << PyLong_SHIFT) | v->ob_digit[i];
1234 }
1235 return x * sign;
1236 }
1237
1238 unsigned long long
PyLong_AsUnsignedLongLongMask(PyObject * op)1239 PyLong_AsUnsignedLongLongMask(PyObject *op)
1240 {
1241 PyLongObject *lo;
1242 unsigned long long val;
1243
1244 if (op == NULL) {
1245 PyErr_BadInternalCall();
1246 return (unsigned long long)-1;
1247 }
1248
1249 if (PyLong_Check(op)) {
1250 return _PyLong_AsUnsignedLongLongMask(op);
1251 }
1252
1253 lo = (PyLongObject *)_PyNumber_Index(op);
1254 if (lo == NULL)
1255 return (unsigned long long)-1;
1256
1257 val = _PyLong_AsUnsignedLongLongMask((PyObject *)lo);
1258 Py_DECREF(lo);
1259 return val;
1260 }
1261
1262 /* Get a C long long int from an int object or any object that has an
1263 __index__ method.
1264
1265 On overflow, return -1 and set *overflow to 1 or -1 depending on the sign of
1266 the result. Otherwise *overflow is 0.
1267
1268 For other errors (e.g., TypeError), return -1 and set an error condition.
1269 In this case *overflow will be 0.
1270 */
1271
1272 long long
PyLong_AsLongLongAndOverflow(PyObject * vv,int * overflow)1273 PyLong_AsLongLongAndOverflow(PyObject *vv, int *overflow)
1274 {
1275 /* This version by Tim Peters */
1276 PyLongObject *v;
1277 unsigned long long x, prev;
1278 long long res;
1279 Py_ssize_t i;
1280 int sign;
1281 int do_decref = 0; /* if PyNumber_Index was called */
1282
1283 *overflow = 0;
1284 if (vv == NULL) {
1285 PyErr_BadInternalCall();
1286 return -1;
1287 }
1288
1289 if (PyLong_Check(vv)) {
1290 v = (PyLongObject *)vv;
1291 }
1292 else {
1293 v = (PyLongObject *)_PyNumber_Index(vv);
1294 if (v == NULL)
1295 return -1;
1296 do_decref = 1;
1297 }
1298
1299 res = -1;
1300 i = Py_SIZE(v);
1301
1302 switch (i) {
1303 case -1:
1304 res = -(sdigit)v->ob_digit[0];
1305 break;
1306 case 0:
1307 res = 0;
1308 break;
1309 case 1:
1310 res = v->ob_digit[0];
1311 break;
1312 default:
1313 sign = 1;
1314 x = 0;
1315 if (i < 0) {
1316 sign = -1;
1317 i = -(i);
1318 }
1319 while (--i >= 0) {
1320 prev = x;
1321 x = (x << PyLong_SHIFT) + v->ob_digit[i];
1322 if ((x >> PyLong_SHIFT) != prev) {
1323 *overflow = sign;
1324 goto exit;
1325 }
1326 }
1327 /* Haven't lost any bits, but casting to long requires extra
1328 * care (see comment above).
1329 */
1330 if (x <= (unsigned long long)LLONG_MAX) {
1331 res = (long long)x * sign;
1332 }
1333 else if (sign < 0 && x == PY_ABS_LLONG_MIN) {
1334 res = LLONG_MIN;
1335 }
1336 else {
1337 *overflow = sign;
1338 /* res is already set to -1 */
1339 }
1340 }
1341 exit:
1342 if (do_decref) {
1343 Py_DECREF(v);
1344 }
1345 return res;
1346 }
1347
1348 int
_PyLong_UnsignedShort_Converter(PyObject * obj,void * ptr)1349 _PyLong_UnsignedShort_Converter(PyObject *obj, void *ptr)
1350 {
1351 unsigned long uval;
1352
1353 if (PyLong_Check(obj) && _PyLong_Sign(obj) < 0) {
1354 PyErr_SetString(PyExc_ValueError, "value must be positive");
1355 return 0;
1356 }
1357 uval = PyLong_AsUnsignedLong(obj);
1358 if (uval == (unsigned long)-1 && PyErr_Occurred())
1359 return 0;
1360 if (uval > USHRT_MAX) {
1361 PyErr_SetString(PyExc_OverflowError,
1362 "Python int too large for C unsigned short");
1363 return 0;
1364 }
1365
1366 *(unsigned short *)ptr = Py_SAFE_DOWNCAST(uval, unsigned long, unsigned short);
1367 return 1;
1368 }
1369
1370 int
_PyLong_UnsignedInt_Converter(PyObject * obj,void * ptr)1371 _PyLong_UnsignedInt_Converter(PyObject *obj, void *ptr)
1372 {
1373 unsigned long uval;
1374
1375 if (PyLong_Check(obj) && _PyLong_Sign(obj) < 0) {
1376 PyErr_SetString(PyExc_ValueError, "value must be positive");
1377 return 0;
1378 }
1379 uval = PyLong_AsUnsignedLong(obj);
1380 if (uval == (unsigned long)-1 && PyErr_Occurred())
1381 return 0;
1382 if (uval > UINT_MAX) {
1383 PyErr_SetString(PyExc_OverflowError,
1384 "Python int too large for C unsigned int");
1385 return 0;
1386 }
1387
1388 *(unsigned int *)ptr = Py_SAFE_DOWNCAST(uval, unsigned long, unsigned int);
1389 return 1;
1390 }
1391
1392 int
_PyLong_UnsignedLong_Converter(PyObject * obj,void * ptr)1393 _PyLong_UnsignedLong_Converter(PyObject *obj, void *ptr)
1394 {
1395 unsigned long uval;
1396
1397 if (PyLong_Check(obj) && _PyLong_Sign(obj) < 0) {
1398 PyErr_SetString(PyExc_ValueError, "value must be positive");
1399 return 0;
1400 }
1401 uval = PyLong_AsUnsignedLong(obj);
1402 if (uval == (unsigned long)-1 && PyErr_Occurred())
1403 return 0;
1404
1405 *(unsigned long *)ptr = uval;
1406 return 1;
1407 }
1408
1409 int
_PyLong_UnsignedLongLong_Converter(PyObject * obj,void * ptr)1410 _PyLong_UnsignedLongLong_Converter(PyObject *obj, void *ptr)
1411 {
1412 unsigned long long uval;
1413
1414 if (PyLong_Check(obj) && _PyLong_Sign(obj) < 0) {
1415 PyErr_SetString(PyExc_ValueError, "value must be positive");
1416 return 0;
1417 }
1418 uval = PyLong_AsUnsignedLongLong(obj);
1419 if (uval == (unsigned long long)-1 && PyErr_Occurred())
1420 return 0;
1421
1422 *(unsigned long long *)ptr = uval;
1423 return 1;
1424 }
1425
1426 int
_PyLong_Size_t_Converter(PyObject * obj,void * ptr)1427 _PyLong_Size_t_Converter(PyObject *obj, void *ptr)
1428 {
1429 size_t uval;
1430
1431 if (PyLong_Check(obj) && _PyLong_Sign(obj) < 0) {
1432 PyErr_SetString(PyExc_ValueError, "value must be positive");
1433 return 0;
1434 }
1435 uval = PyLong_AsSize_t(obj);
1436 if (uval == (size_t)-1 && PyErr_Occurred())
1437 return 0;
1438
1439 *(size_t *)ptr = uval;
1440 return 1;
1441 }
1442
1443
1444 #define CHECK_BINOP(v,w) \
1445 do { \
1446 if (!PyLong_Check(v) || !PyLong_Check(w)) \
1447 Py_RETURN_NOTIMPLEMENTED; \
1448 } while(0)
1449
1450 /* x[0:m] and y[0:n] are digit vectors, LSD first, m >= n required. x[0:n]
1451 * is modified in place, by adding y to it. Carries are propagated as far as
1452 * x[m-1], and the remaining carry (0 or 1) is returned.
1453 */
1454 static digit
v_iadd(digit * x,Py_ssize_t m,digit * y,Py_ssize_t n)1455 v_iadd(digit *x, Py_ssize_t m, digit *y, Py_ssize_t n)
1456 {
1457 Py_ssize_t i;
1458 digit carry = 0;
1459
1460 assert(m >= n);
1461 for (i = 0; i < n; ++i) {
1462 carry += x[i] + y[i];
1463 x[i] = carry & PyLong_MASK;
1464 carry >>= PyLong_SHIFT;
1465 assert((carry & 1) == carry);
1466 }
1467 for (; carry && i < m; ++i) {
1468 carry += x[i];
1469 x[i] = carry & PyLong_MASK;
1470 carry >>= PyLong_SHIFT;
1471 assert((carry & 1) == carry);
1472 }
1473 return carry;
1474 }
1475
1476 /* x[0:m] and y[0:n] are digit vectors, LSD first, m >= n required. x[0:n]
1477 * is modified in place, by subtracting y from it. Borrows are propagated as
1478 * far as x[m-1], and the remaining borrow (0 or 1) is returned.
1479 */
1480 static digit
v_isub(digit * x,Py_ssize_t m,digit * y,Py_ssize_t n)1481 v_isub(digit *x, Py_ssize_t m, digit *y, Py_ssize_t n)
1482 {
1483 Py_ssize_t i;
1484 digit borrow = 0;
1485
1486 assert(m >= n);
1487 for (i = 0; i < n; ++i) {
1488 borrow = x[i] - y[i] - borrow;
1489 x[i] = borrow & PyLong_MASK;
1490 borrow >>= PyLong_SHIFT;
1491 borrow &= 1; /* keep only 1 sign bit */
1492 }
1493 for (; borrow && i < m; ++i) {
1494 borrow = x[i] - borrow;
1495 x[i] = borrow & PyLong_MASK;
1496 borrow >>= PyLong_SHIFT;
1497 borrow &= 1;
1498 }
1499 return borrow;
1500 }
1501
1502 /* Shift digit vector a[0:m] d bits left, with 0 <= d < PyLong_SHIFT. Put
1503 * result in z[0:m], and return the d bits shifted out of the top.
1504 */
1505 static digit
v_lshift(digit * z,digit * a,Py_ssize_t m,int d)1506 v_lshift(digit *z, digit *a, Py_ssize_t m, int d)
1507 {
1508 Py_ssize_t i;
1509 digit carry = 0;
1510
1511 assert(0 <= d && d < PyLong_SHIFT);
1512 for (i=0; i < m; i++) {
1513 twodigits acc = (twodigits)a[i] << d | carry;
1514 z[i] = (digit)acc & PyLong_MASK;
1515 carry = (digit)(acc >> PyLong_SHIFT);
1516 }
1517 return carry;
1518 }
1519
1520 /* Shift digit vector a[0:m] d bits right, with 0 <= d < PyLong_SHIFT. Put
1521 * result in z[0:m], and return the d bits shifted out of the bottom.
1522 */
1523 static digit
v_rshift(digit * z,digit * a,Py_ssize_t m,int d)1524 v_rshift(digit *z, digit *a, Py_ssize_t m, int d)
1525 {
1526 Py_ssize_t i;
1527 digit carry = 0;
1528 digit mask = ((digit)1 << d) - 1U;
1529
1530 assert(0 <= d && d < PyLong_SHIFT);
1531 for (i=m; i-- > 0;) {
1532 twodigits acc = (twodigits)carry << PyLong_SHIFT | a[i];
1533 carry = (digit)acc & mask;
1534 z[i] = (digit)(acc >> d);
1535 }
1536 return carry;
1537 }
1538
1539 /* Divide long pin, w/ size digits, by non-zero digit n, storing quotient
1540 in pout, and returning the remainder. pin and pout point at the LSD.
1541 It's OK for pin == pout on entry, which saves oodles of mallocs/frees in
1542 _PyLong_Format, but that should be done with great care since ints are
1543 immutable. */
1544
1545 static digit
inplace_divrem1(digit * pout,digit * pin,Py_ssize_t size,digit n)1546 inplace_divrem1(digit *pout, digit *pin, Py_ssize_t size, digit n)
1547 {
1548 twodigits rem = 0;
1549
1550 assert(n > 0 && n <= PyLong_MASK);
1551 pin += size;
1552 pout += size;
1553 while (--size >= 0) {
1554 digit hi;
1555 rem = (rem << PyLong_SHIFT) | *--pin;
1556 *--pout = hi = (digit)(rem / n);
1557 rem -= (twodigits)hi * n;
1558 }
1559 return (digit)rem;
1560 }
1561
1562 /* Divide an integer by a digit, returning both the quotient
1563 (as function result) and the remainder (through *prem).
1564 The sign of a is ignored; n should not be zero. */
1565
1566 static PyLongObject *
divrem1(PyLongObject * a,digit n,digit * prem)1567 divrem1(PyLongObject *a, digit n, digit *prem)
1568 {
1569 const Py_ssize_t size = Py_ABS(Py_SIZE(a));
1570 PyLongObject *z;
1571
1572 assert(n > 0 && n <= PyLong_MASK);
1573 z = _PyLong_New(size);
1574 if (z == NULL)
1575 return NULL;
1576 *prem = inplace_divrem1(z->ob_digit, a->ob_digit, size, n);
1577 return long_normalize(z);
1578 }
1579
1580 /* Convert an integer to a base 10 string. Returns a new non-shared
1581 string. (Return value is non-shared so that callers can modify the
1582 returned value if necessary.) */
1583
1584 static int
long_to_decimal_string_internal(PyObject * aa,PyObject ** p_output,_PyUnicodeWriter * writer,_PyBytesWriter * bytes_writer,char ** bytes_str)1585 long_to_decimal_string_internal(PyObject *aa,
1586 PyObject **p_output,
1587 _PyUnicodeWriter *writer,
1588 _PyBytesWriter *bytes_writer,
1589 char **bytes_str)
1590 {
1591 PyLongObject *scratch, *a;
1592 PyObject *str = NULL;
1593 Py_ssize_t size, strlen, size_a, i, j;
1594 digit *pout, *pin, rem, tenpow;
1595 int negative;
1596 int d;
1597 enum PyUnicode_Kind kind;
1598
1599 a = (PyLongObject *)aa;
1600 if (a == NULL || !PyLong_Check(a)) {
1601 PyErr_BadInternalCall();
1602 return -1;
1603 }
1604 size_a = Py_ABS(Py_SIZE(a));
1605 negative = Py_SIZE(a) < 0;
1606
1607 /* quick and dirty upper bound for the number of digits
1608 required to express a in base _PyLong_DECIMAL_BASE:
1609
1610 #digits = 1 + floor(log2(a) / log2(_PyLong_DECIMAL_BASE))
1611
1612 But log2(a) < size_a * PyLong_SHIFT, and
1613 log2(_PyLong_DECIMAL_BASE) = log2(10) * _PyLong_DECIMAL_SHIFT
1614 > 3.3 * _PyLong_DECIMAL_SHIFT
1615
1616 size_a * PyLong_SHIFT / (3.3 * _PyLong_DECIMAL_SHIFT) =
1617 size_a + size_a / d < size_a + size_a / floor(d),
1618 where d = (3.3 * _PyLong_DECIMAL_SHIFT) /
1619 (PyLong_SHIFT - 3.3 * _PyLong_DECIMAL_SHIFT)
1620 */
1621 d = (33 * _PyLong_DECIMAL_SHIFT) /
1622 (10 * PyLong_SHIFT - 33 * _PyLong_DECIMAL_SHIFT);
1623 assert(size_a < PY_SSIZE_T_MAX/2);
1624 size = 1 + size_a + size_a / d;
1625 scratch = _PyLong_New(size);
1626 if (scratch == NULL)
1627 return -1;
1628
1629 /* convert array of base _PyLong_BASE digits in pin to an array of
1630 base _PyLong_DECIMAL_BASE digits in pout, following Knuth (TAOCP,
1631 Volume 2 (3rd edn), section 4.4, Method 1b). */
1632 pin = a->ob_digit;
1633 pout = scratch->ob_digit;
1634 size = 0;
1635 for (i = size_a; --i >= 0; ) {
1636 digit hi = pin[i];
1637 for (j = 0; j < size; j++) {
1638 twodigits z = (twodigits)pout[j] << PyLong_SHIFT | hi;
1639 hi = (digit)(z / _PyLong_DECIMAL_BASE);
1640 pout[j] = (digit)(z - (twodigits)hi *
1641 _PyLong_DECIMAL_BASE);
1642 }
1643 while (hi) {
1644 pout[size++] = hi % _PyLong_DECIMAL_BASE;
1645 hi /= _PyLong_DECIMAL_BASE;
1646 }
1647 /* check for keyboard interrupt */
1648 SIGCHECK({
1649 Py_DECREF(scratch);
1650 return -1;
1651 });
1652 }
1653 /* pout should have at least one digit, so that the case when a = 0
1654 works correctly */
1655 if (size == 0)
1656 pout[size++] = 0;
1657
1658 /* calculate exact length of output string, and allocate */
1659 strlen = negative + 1 + (size - 1) * _PyLong_DECIMAL_SHIFT;
1660 tenpow = 10;
1661 rem = pout[size-1];
1662 while (rem >= tenpow) {
1663 tenpow *= 10;
1664 strlen++;
1665 }
1666 if (strlen > _PY_LONG_MAX_STR_DIGITS_THRESHOLD) {
1667 PyInterpreterState *interp = _PyInterpreterState_GET();
1668 int max_str_digits = interp->int_max_str_digits;
1669 Py_ssize_t strlen_nosign = strlen - negative;
1670 if ((max_str_digits > 0) && (strlen_nosign > max_str_digits)) {
1671 Py_DECREF(scratch);
1672 PyErr_Format(PyExc_ValueError, _MAX_STR_DIGITS_ERROR_FMT,
1673 max_str_digits, strlen_nosign);
1674 return -1;
1675 }
1676 }
1677 if (writer) {
1678 if (_PyUnicodeWriter_Prepare(writer, strlen, '9') == -1) {
1679 Py_DECREF(scratch);
1680 return -1;
1681 }
1682 kind = writer->kind;
1683 }
1684 else if (bytes_writer) {
1685 *bytes_str = _PyBytesWriter_Prepare(bytes_writer, *bytes_str, strlen);
1686 if (*bytes_str == NULL) {
1687 Py_DECREF(scratch);
1688 return -1;
1689 }
1690 }
1691 else {
1692 str = PyUnicode_New(strlen, '9');
1693 if (str == NULL) {
1694 Py_DECREF(scratch);
1695 return -1;
1696 }
1697 kind = PyUnicode_KIND(str);
1698 }
1699
1700 #define WRITE_DIGITS(p) \
1701 do { \
1702 /* pout[0] through pout[size-2] contribute exactly \
1703 _PyLong_DECIMAL_SHIFT digits each */ \
1704 for (i=0; i < size - 1; i++) { \
1705 rem = pout[i]; \
1706 for (j = 0; j < _PyLong_DECIMAL_SHIFT; j++) { \
1707 *--p = '0' + rem % 10; \
1708 rem /= 10; \
1709 } \
1710 } \
1711 /* pout[size-1]: always produce at least one decimal digit */ \
1712 rem = pout[i]; \
1713 do { \
1714 *--p = '0' + rem % 10; \
1715 rem /= 10; \
1716 } while (rem != 0); \
1717 \
1718 /* and sign */ \
1719 if (negative) \
1720 *--p = '-'; \
1721 } while (0)
1722
1723 #define WRITE_UNICODE_DIGITS(TYPE) \
1724 do { \
1725 if (writer) \
1726 p = (TYPE*)PyUnicode_DATA(writer->buffer) + writer->pos + strlen; \
1727 else \
1728 p = (TYPE*)PyUnicode_DATA(str) + strlen; \
1729 \
1730 WRITE_DIGITS(p); \
1731 \
1732 /* check we've counted correctly */ \
1733 if (writer) \
1734 assert(p == ((TYPE*)PyUnicode_DATA(writer->buffer) + writer->pos)); \
1735 else \
1736 assert(p == (TYPE*)PyUnicode_DATA(str)); \
1737 } while (0)
1738
1739 /* fill the string right-to-left */
1740 if (bytes_writer) {
1741 char *p = *bytes_str + strlen;
1742 WRITE_DIGITS(p);
1743 assert(p == *bytes_str);
1744 }
1745 else if (kind == PyUnicode_1BYTE_KIND) {
1746 Py_UCS1 *p;
1747 WRITE_UNICODE_DIGITS(Py_UCS1);
1748 }
1749 else if (kind == PyUnicode_2BYTE_KIND) {
1750 Py_UCS2 *p;
1751 WRITE_UNICODE_DIGITS(Py_UCS2);
1752 }
1753 else {
1754 Py_UCS4 *p;
1755 assert (kind == PyUnicode_4BYTE_KIND);
1756 WRITE_UNICODE_DIGITS(Py_UCS4);
1757 }
1758 #undef WRITE_DIGITS
1759 #undef WRITE_UNICODE_DIGITS
1760
1761 Py_DECREF(scratch);
1762 if (writer) {
1763 writer->pos += strlen;
1764 }
1765 else if (bytes_writer) {
1766 (*bytes_str) += strlen;
1767 }
1768 else {
1769 assert(_PyUnicode_CheckConsistency(str, 1));
1770 *p_output = (PyObject *)str;
1771 }
1772 return 0;
1773 }
1774
1775 static PyObject *
long_to_decimal_string(PyObject * aa)1776 long_to_decimal_string(PyObject *aa)
1777 {
1778 PyObject *v;
1779 if (long_to_decimal_string_internal(aa, &v, NULL, NULL, NULL) == -1)
1780 return NULL;
1781 return v;
1782 }
1783
1784 /* Convert an int object to a string, using a given conversion base,
1785 which should be one of 2, 8 or 16. Return a string object.
1786 If base is 2, 8 or 16, add the proper prefix '0b', '0o' or '0x'
1787 if alternate is nonzero. */
1788
1789 static int
long_format_binary(PyObject * aa,int base,int alternate,PyObject ** p_output,_PyUnicodeWriter * writer,_PyBytesWriter * bytes_writer,char ** bytes_str)1790 long_format_binary(PyObject *aa, int base, int alternate,
1791 PyObject **p_output, _PyUnicodeWriter *writer,
1792 _PyBytesWriter *bytes_writer, char **bytes_str)
1793 {
1794 PyLongObject *a = (PyLongObject *)aa;
1795 PyObject *v = NULL;
1796 Py_ssize_t sz;
1797 Py_ssize_t size_a;
1798 enum PyUnicode_Kind kind;
1799 int negative;
1800 int bits;
1801
1802 assert(base == 2 || base == 8 || base == 16);
1803 if (a == NULL || !PyLong_Check(a)) {
1804 PyErr_BadInternalCall();
1805 return -1;
1806 }
1807 size_a = Py_ABS(Py_SIZE(a));
1808 negative = Py_SIZE(a) < 0;
1809
1810 /* Compute a rough upper bound for the length of the string */
1811 switch (base) {
1812 case 16:
1813 bits = 4;
1814 break;
1815 case 8:
1816 bits = 3;
1817 break;
1818 case 2:
1819 bits = 1;
1820 break;
1821 default:
1822 Py_UNREACHABLE();
1823 }
1824
1825 /* Compute exact length 'sz' of output string. */
1826 if (size_a == 0) {
1827 sz = 1;
1828 }
1829 else {
1830 Py_ssize_t size_a_in_bits;
1831 /* Ensure overflow doesn't occur during computation of sz. */
1832 if (size_a > (PY_SSIZE_T_MAX - 3) / PyLong_SHIFT) {
1833 PyErr_SetString(PyExc_OverflowError,
1834 "int too large to format");
1835 return -1;
1836 }
1837 size_a_in_bits = (size_a - 1) * PyLong_SHIFT +
1838 bit_length_digit(a->ob_digit[size_a - 1]);
1839 /* Allow 1 character for a '-' sign. */
1840 sz = negative + (size_a_in_bits + (bits - 1)) / bits;
1841 }
1842 if (alternate) {
1843 /* 2 characters for prefix */
1844 sz += 2;
1845 }
1846
1847 if (writer) {
1848 if (_PyUnicodeWriter_Prepare(writer, sz, 'x') == -1)
1849 return -1;
1850 kind = writer->kind;
1851 }
1852 else if (bytes_writer) {
1853 *bytes_str = _PyBytesWriter_Prepare(bytes_writer, *bytes_str, sz);
1854 if (*bytes_str == NULL)
1855 return -1;
1856 }
1857 else {
1858 v = PyUnicode_New(sz, 'x');
1859 if (v == NULL)
1860 return -1;
1861 kind = PyUnicode_KIND(v);
1862 }
1863
1864 #define WRITE_DIGITS(p) \
1865 do { \
1866 if (size_a == 0) { \
1867 *--p = '0'; \
1868 } \
1869 else { \
1870 /* JRH: special case for power-of-2 bases */ \
1871 twodigits accum = 0; \
1872 int accumbits = 0; /* # of bits in accum */ \
1873 Py_ssize_t i; \
1874 for (i = 0; i < size_a; ++i) { \
1875 accum |= (twodigits)a->ob_digit[i] << accumbits; \
1876 accumbits += PyLong_SHIFT; \
1877 assert(accumbits >= bits); \
1878 do { \
1879 char cdigit; \
1880 cdigit = (char)(accum & (base - 1)); \
1881 cdigit += (cdigit < 10) ? '0' : 'a'-10; \
1882 *--p = cdigit; \
1883 accumbits -= bits; \
1884 accum >>= bits; \
1885 } while (i < size_a-1 ? accumbits >= bits : accum > 0); \
1886 } \
1887 } \
1888 \
1889 if (alternate) { \
1890 if (base == 16) \
1891 *--p = 'x'; \
1892 else if (base == 8) \
1893 *--p = 'o'; \
1894 else /* (base == 2) */ \
1895 *--p = 'b'; \
1896 *--p = '0'; \
1897 } \
1898 if (negative) \
1899 *--p = '-'; \
1900 } while (0)
1901
1902 #define WRITE_UNICODE_DIGITS(TYPE) \
1903 do { \
1904 if (writer) \
1905 p = (TYPE*)PyUnicode_DATA(writer->buffer) + writer->pos + sz; \
1906 else \
1907 p = (TYPE*)PyUnicode_DATA(v) + sz; \
1908 \
1909 WRITE_DIGITS(p); \
1910 \
1911 if (writer) \
1912 assert(p == ((TYPE*)PyUnicode_DATA(writer->buffer) + writer->pos)); \
1913 else \
1914 assert(p == (TYPE*)PyUnicode_DATA(v)); \
1915 } while (0)
1916
1917 if (bytes_writer) {
1918 char *p = *bytes_str + sz;
1919 WRITE_DIGITS(p);
1920 assert(p == *bytes_str);
1921 }
1922 else if (kind == PyUnicode_1BYTE_KIND) {
1923 Py_UCS1 *p;
1924 WRITE_UNICODE_DIGITS(Py_UCS1);
1925 }
1926 else if (kind == PyUnicode_2BYTE_KIND) {
1927 Py_UCS2 *p;
1928 WRITE_UNICODE_DIGITS(Py_UCS2);
1929 }
1930 else {
1931 Py_UCS4 *p;
1932 assert (kind == PyUnicode_4BYTE_KIND);
1933 WRITE_UNICODE_DIGITS(Py_UCS4);
1934 }
1935 #undef WRITE_DIGITS
1936 #undef WRITE_UNICODE_DIGITS
1937
1938 if (writer) {
1939 writer->pos += sz;
1940 }
1941 else if (bytes_writer) {
1942 (*bytes_str) += sz;
1943 }
1944 else {
1945 assert(_PyUnicode_CheckConsistency(v, 1));
1946 *p_output = v;
1947 }
1948 return 0;
1949 }
1950
1951 PyObject *
_PyLong_Format(PyObject * obj,int base)1952 _PyLong_Format(PyObject *obj, int base)
1953 {
1954 PyObject *str;
1955 int err;
1956 if (base == 10)
1957 err = long_to_decimal_string_internal(obj, &str, NULL, NULL, NULL);
1958 else
1959 err = long_format_binary(obj, base, 1, &str, NULL, NULL, NULL);
1960 if (err == -1)
1961 return NULL;
1962 return str;
1963 }
1964
1965 int
_PyLong_FormatWriter(_PyUnicodeWriter * writer,PyObject * obj,int base,int alternate)1966 _PyLong_FormatWriter(_PyUnicodeWriter *writer,
1967 PyObject *obj,
1968 int base, int alternate)
1969 {
1970 if (base == 10)
1971 return long_to_decimal_string_internal(obj, NULL, writer,
1972 NULL, NULL);
1973 else
1974 return long_format_binary(obj, base, alternate, NULL, writer,
1975 NULL, NULL);
1976 }
1977
1978 char*
_PyLong_FormatBytesWriter(_PyBytesWriter * writer,char * str,PyObject * obj,int base,int alternate)1979 _PyLong_FormatBytesWriter(_PyBytesWriter *writer, char *str,
1980 PyObject *obj,
1981 int base, int alternate)
1982 {
1983 char *str2;
1984 int res;
1985 str2 = str;
1986 if (base == 10)
1987 res = long_to_decimal_string_internal(obj, NULL, NULL,
1988 writer, &str2);
1989 else
1990 res = long_format_binary(obj, base, alternate, NULL, NULL,
1991 writer, &str2);
1992 if (res < 0)
1993 return NULL;
1994 assert(str2 != NULL);
1995 return str2;
1996 }
1997
1998 /* Table of digit values for 8-bit string -> integer conversion.
1999 * '0' maps to 0, ..., '9' maps to 9.
2000 * 'a' and 'A' map to 10, ..., 'z' and 'Z' map to 35.
2001 * All other indices map to 37.
2002 * Note that when converting a base B string, a char c is a legitimate
2003 * base B digit iff _PyLong_DigitValue[Py_CHARPyLong_MASK(c)] < B.
2004 */
2005 unsigned char _PyLong_DigitValue[256] = {
2006 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37,
2007 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37,
2008 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37,
2009 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 37, 37, 37, 37, 37, 37,
2010 37, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24,
2011 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 37, 37, 37, 37, 37,
2012 37, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24,
2013 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 37, 37, 37, 37, 37,
2014 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37,
2015 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37,
2016 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37,
2017 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37,
2018 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37,
2019 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37,
2020 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37,
2021 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37,
2022 };
2023
2024 /* *str points to the first digit in a string of base `base` digits. base
2025 * is a power of 2 (2, 4, 8, 16, or 32). *str is set to point to the first
2026 * non-digit (which may be *str!). A normalized int is returned.
2027 * The point to this routine is that it takes time linear in the number of
2028 * string characters.
2029 *
2030 * Return values:
2031 * -1 on syntax error (exception needs to be set, *res is untouched)
2032 * 0 else (exception may be set, in that case *res is set to NULL)
2033 */
2034 static int
long_from_binary_base(const char ** str,int base,PyLongObject ** res)2035 long_from_binary_base(const char **str, int base, PyLongObject **res)
2036 {
2037 const char *p = *str;
2038 const char *start = p;
2039 char prev = 0;
2040 Py_ssize_t digits = 0;
2041 int bits_per_char;
2042 Py_ssize_t n;
2043 PyLongObject *z;
2044 twodigits accum;
2045 int bits_in_accum;
2046 digit *pdigit;
2047
2048 assert(base >= 2 && base <= 32 && (base & (base - 1)) == 0);
2049 n = base;
2050 for (bits_per_char = -1; n; ++bits_per_char) {
2051 n >>= 1;
2052 }
2053 /* count digits and set p to end-of-string */
2054 while (_PyLong_DigitValue[Py_CHARMASK(*p)] < base || *p == '_') {
2055 if (*p == '_') {
2056 if (prev == '_') {
2057 *str = p - 1;
2058 return -1;
2059 }
2060 } else {
2061 ++digits;
2062 }
2063 prev = *p;
2064 ++p;
2065 }
2066 if (prev == '_') {
2067 /* Trailing underscore not allowed. */
2068 *str = p - 1;
2069 return -1;
2070 }
2071
2072 *str = p;
2073 /* n <- the number of Python digits needed,
2074 = ceiling((digits * bits_per_char) / PyLong_SHIFT). */
2075 if (digits > (PY_SSIZE_T_MAX - (PyLong_SHIFT - 1)) / bits_per_char) {
2076 PyErr_SetString(PyExc_ValueError,
2077 "int string too large to convert");
2078 *res = NULL;
2079 return 0;
2080 }
2081 n = (digits * bits_per_char + PyLong_SHIFT - 1) / PyLong_SHIFT;
2082 z = _PyLong_New(n);
2083 if (z == NULL) {
2084 *res = NULL;
2085 return 0;
2086 }
2087 /* Read string from right, and fill in int from left; i.e.,
2088 * from least to most significant in both.
2089 */
2090 accum = 0;
2091 bits_in_accum = 0;
2092 pdigit = z->ob_digit;
2093 while (--p >= start) {
2094 int k;
2095 if (*p == '_') {
2096 continue;
2097 }
2098 k = (int)_PyLong_DigitValue[Py_CHARMASK(*p)];
2099 assert(k >= 0 && k < base);
2100 accum |= (twodigits)k << bits_in_accum;
2101 bits_in_accum += bits_per_char;
2102 if (bits_in_accum >= PyLong_SHIFT) {
2103 *pdigit++ = (digit)(accum & PyLong_MASK);
2104 assert(pdigit - z->ob_digit <= n);
2105 accum >>= PyLong_SHIFT;
2106 bits_in_accum -= PyLong_SHIFT;
2107 assert(bits_in_accum < PyLong_SHIFT);
2108 }
2109 }
2110 if (bits_in_accum) {
2111 assert(bits_in_accum <= PyLong_SHIFT);
2112 *pdigit++ = (digit)accum;
2113 assert(pdigit - z->ob_digit <= n);
2114 }
2115 while (pdigit - z->ob_digit < n)
2116 *pdigit++ = 0;
2117 *res = long_normalize(z);
2118 return 0;
2119 }
2120
2121 /* Parses an int from a bytestring. Leading and trailing whitespace will be
2122 * ignored.
2123 *
2124 * If successful, a PyLong object will be returned and 'pend' will be pointing
2125 * to the first unused byte unless it's NULL.
2126 *
2127 * If unsuccessful, NULL will be returned.
2128 */
2129 PyObject *
PyLong_FromString(const char * str,char ** pend,int base)2130 PyLong_FromString(const char *str, char **pend, int base)
2131 {
2132 int sign = 1, error_if_nonzero = 0;
2133 const char *start, *orig_str = str;
2134 PyLongObject *z = NULL;
2135 PyObject *strobj;
2136 Py_ssize_t slen;
2137
2138 if ((base != 0 && base < 2) || base > 36) {
2139 PyErr_SetString(PyExc_ValueError,
2140 "int() arg 2 must be >= 2 and <= 36");
2141 return NULL;
2142 }
2143 while (*str != '\0' && Py_ISSPACE(*str)) {
2144 str++;
2145 }
2146 if (*str == '+') {
2147 ++str;
2148 }
2149 else if (*str == '-') {
2150 ++str;
2151 sign = -1;
2152 }
2153 if (base == 0) {
2154 if (str[0] != '0') {
2155 base = 10;
2156 }
2157 else if (str[1] == 'x' || str[1] == 'X') {
2158 base = 16;
2159 }
2160 else if (str[1] == 'o' || str[1] == 'O') {
2161 base = 8;
2162 }
2163 else if (str[1] == 'b' || str[1] == 'B') {
2164 base = 2;
2165 }
2166 else {
2167 /* "old" (C-style) octal literal, now invalid.
2168 it might still be zero though */
2169 error_if_nonzero = 1;
2170 base = 10;
2171 }
2172 }
2173 if (str[0] == '0' &&
2174 ((base == 16 && (str[1] == 'x' || str[1] == 'X')) ||
2175 (base == 8 && (str[1] == 'o' || str[1] == 'O')) ||
2176 (base == 2 && (str[1] == 'b' || str[1] == 'B')))) {
2177 str += 2;
2178 /* One underscore allowed here. */
2179 if (*str == '_') {
2180 ++str;
2181 }
2182 }
2183 if (str[0] == '_') {
2184 /* May not start with underscores. */
2185 goto onError;
2186 }
2187
2188 start = str;
2189 if ((base & (base - 1)) == 0) {
2190 /* binary bases are not limited by int_max_str_digits */
2191 int res = long_from_binary_base(&str, base, &z);
2192 if (res < 0) {
2193 /* Syntax error. */
2194 goto onError;
2195 }
2196 }
2197 else {
2198 /***
2199 Binary bases can be converted in time linear in the number of digits, because
2200 Python's representation base is binary. Other bases (including decimal!) use
2201 the simple quadratic-time algorithm below, complicated by some speed tricks.
2202
2203 First some math: the largest integer that can be expressed in N base-B digits
2204 is B**N-1. Consequently, if we have an N-digit input in base B, the worst-
2205 case number of Python digits needed to hold it is the smallest integer n s.t.
2206
2207 BASE**n-1 >= B**N-1 [or, adding 1 to both sides]
2208 BASE**n >= B**N [taking logs to base BASE]
2209 n >= log(B**N)/log(BASE) = N * log(B)/log(BASE)
2210
2211 The static array log_base_BASE[base] == log(base)/log(BASE) so we can compute
2212 this quickly. A Python int with that much space is reserved near the start,
2213 and the result is computed into it.
2214
2215 The input string is actually treated as being in base base**i (i.e., i digits
2216 are processed at a time), where two more static arrays hold:
2217
2218 convwidth_base[base] = the largest integer i such that base**i <= BASE
2219 convmultmax_base[base] = base ** convwidth_base[base]
2220
2221 The first of these is the largest i such that i consecutive input digits
2222 must fit in a single Python digit. The second is effectively the input
2223 base we're really using.
2224
2225 Viewing the input as a sequence <c0, c1, ..., c_n-1> of digits in base
2226 convmultmax_base[base], the result is "simply"
2227
2228 (((c0*B + c1)*B + c2)*B + c3)*B + ... ))) + c_n-1
2229
2230 where B = convmultmax_base[base].
2231
2232 Error analysis: as above, the number of Python digits `n` needed is worst-
2233 case
2234
2235 n >= N * log(B)/log(BASE)
2236
2237 where `N` is the number of input digits in base `B`. This is computed via
2238
2239 size_z = (Py_ssize_t)((scan - str) * log_base_BASE[base]) + 1;
2240
2241 below. Two numeric concerns are how much space this can waste, and whether
2242 the computed result can be too small. To be concrete, assume BASE = 2**15,
2243 which is the default (and it's unlikely anyone changes that).
2244
2245 Waste isn't a problem: provided the first input digit isn't 0, the difference
2246 between the worst-case input with N digits and the smallest input with N
2247 digits is about a factor of B, but B is small compared to BASE so at most
2248 one allocated Python digit can remain unused on that count. If
2249 N*log(B)/log(BASE) is mathematically an exact integer, then truncating that
2250 and adding 1 returns a result 1 larger than necessary. However, that can't
2251 happen: whenever B is a power of 2, long_from_binary_base() is called
2252 instead, and it's impossible for B**i to be an integer power of 2**15 when
2253 B is not a power of 2 (i.e., it's impossible for N*log(B)/log(BASE) to be
2254 an exact integer when B is not a power of 2, since B**i has a prime factor
2255 other than 2 in that case, but (2**15)**j's only prime factor is 2).
2256
2257 The computed result can be too small if the true value of N*log(B)/log(BASE)
2258 is a little bit larger than an exact integer, but due to roundoff errors (in
2259 computing log(B), log(BASE), their quotient, and/or multiplying that by N)
2260 yields a numeric result a little less than that integer. Unfortunately, "how
2261 close can a transcendental function get to an integer over some range?"
2262 questions are generally theoretically intractable. Computer analysis via
2263 continued fractions is practical: expand log(B)/log(BASE) via continued
2264 fractions, giving a sequence i/j of "the best" rational approximations. Then
2265 j*log(B)/log(BASE) is approximately equal to (the integer) i. This shows that
2266 we can get very close to being in trouble, but very rarely. For example,
2267 76573 is a denominator in one of the continued-fraction approximations to
2268 log(10)/log(2**15), and indeed:
2269
2270 >>> log(10)/log(2**15)*76573
2271 16958.000000654003
2272
2273 is very close to an integer. If we were working with IEEE single-precision,
2274 rounding errors could kill us. Finding worst cases in IEEE double-precision
2275 requires better-than-double-precision log() functions, and Tim didn't bother.
2276 Instead the code checks to see whether the allocated space is enough as each
2277 new Python digit is added, and copies the whole thing to a larger int if not.
2278 This should happen extremely rarely, and in fact I don't have a test case
2279 that triggers it(!). Instead the code was tested by artificially allocating
2280 just 1 digit at the start, so that the copying code was exercised for every
2281 digit beyond the first.
2282 ***/
2283 twodigits c; /* current input character */
2284 Py_ssize_t size_z;
2285 Py_ssize_t digits = 0;
2286 int i;
2287 int convwidth;
2288 twodigits convmultmax, convmult;
2289 digit *pz, *pzstop;
2290 const char *scan, *lastdigit;
2291 char prev = 0;
2292
2293 static double log_base_BASE[37] = {0.0e0,};
2294 static int convwidth_base[37] = {0,};
2295 static twodigits convmultmax_base[37] = {0,};
2296
2297 if (log_base_BASE[base] == 0.0) {
2298 twodigits convmax = base;
2299 int i = 1;
2300
2301 log_base_BASE[base] = (log((double)base) /
2302 log((double)PyLong_BASE));
2303 for (;;) {
2304 twodigits next = convmax * base;
2305 if (next > PyLong_BASE) {
2306 break;
2307 }
2308 convmax = next;
2309 ++i;
2310 }
2311 convmultmax_base[base] = convmax;
2312 assert(i > 0);
2313 convwidth_base[base] = i;
2314 }
2315
2316 /* Find length of the string of numeric characters. */
2317 scan = str;
2318 lastdigit = str;
2319
2320 while (_PyLong_DigitValue[Py_CHARMASK(*scan)] < base || *scan == '_') {
2321 if (*scan == '_') {
2322 if (prev == '_') {
2323 /* Only one underscore allowed. */
2324 str = lastdigit + 1;
2325 goto onError;
2326 }
2327 }
2328 else {
2329 ++digits;
2330 lastdigit = scan;
2331 }
2332 prev = *scan;
2333 ++scan;
2334 }
2335 if (prev == '_') {
2336 /* Trailing underscore not allowed. */
2337 /* Set error pointer to first underscore. */
2338 str = lastdigit + 1;
2339 goto onError;
2340 }
2341
2342 /* Limit the size to avoid excessive computation attacks. */
2343 if (digits > _PY_LONG_MAX_STR_DIGITS_THRESHOLD) {
2344 PyInterpreterState *interp = _PyInterpreterState_GET();
2345 int max_str_digits = interp->int_max_str_digits;
2346 if ((max_str_digits > 0) && (digits > max_str_digits)) {
2347 PyErr_Format(PyExc_ValueError, _MAX_STR_DIGITS_ERROR_FMT,
2348 max_str_digits, digits);
2349 return NULL;
2350 }
2351 }
2352
2353 /* Create an int object that can contain the largest possible
2354 * integer with this base and length. Note that there's no
2355 * need to initialize z->ob_digit -- no slot is read up before
2356 * being stored into.
2357 */
2358 double fsize_z = (double)digits * log_base_BASE[base] + 1.0;
2359 if (fsize_z > (double)MAX_LONG_DIGITS) {
2360 /* The same exception as in _PyLong_New(). */
2361 PyErr_SetString(PyExc_OverflowError,
2362 "too many digits in integer");
2363 return NULL;
2364 }
2365 size_z = (Py_ssize_t)fsize_z;
2366 /* Uncomment next line to test exceedingly rare copy code */
2367 /* size_z = 1; */
2368 assert(size_z > 0);
2369 z = _PyLong_New(size_z);
2370 if (z == NULL) {
2371 return NULL;
2372 }
2373 Py_SET_SIZE(z, 0);
2374
2375 /* `convwidth` consecutive input digits are treated as a single
2376 * digit in base `convmultmax`.
2377 */
2378 convwidth = convwidth_base[base];
2379 convmultmax = convmultmax_base[base];
2380
2381 /* Work ;-) */
2382 while (str < scan) {
2383 if (*str == '_') {
2384 str++;
2385 continue;
2386 }
2387 /* grab up to convwidth digits from the input string */
2388 c = (digit)_PyLong_DigitValue[Py_CHARMASK(*str++)];
2389 for (i = 1; i < convwidth && str != scan; ++str) {
2390 if (*str == '_') {
2391 continue;
2392 }
2393 i++;
2394 c = (twodigits)(c * base +
2395 (int)_PyLong_DigitValue[Py_CHARMASK(*str)]);
2396 assert(c < PyLong_BASE);
2397 }
2398
2399 convmult = convmultmax;
2400 /* Calculate the shift only if we couldn't get
2401 * convwidth digits.
2402 */
2403 if (i != convwidth) {
2404 convmult = base;
2405 for ( ; i > 1; --i) {
2406 convmult *= base;
2407 }
2408 }
2409
2410 /* Multiply z by convmult, and add c. */
2411 pz = z->ob_digit;
2412 pzstop = pz + Py_SIZE(z);
2413 for (; pz < pzstop; ++pz) {
2414 c += (twodigits)*pz * convmult;
2415 *pz = (digit)(c & PyLong_MASK);
2416 c >>= PyLong_SHIFT;
2417 }
2418 /* carry off the current end? */
2419 if (c) {
2420 assert(c < PyLong_BASE);
2421 if (Py_SIZE(z) < size_z) {
2422 *pz = (digit)c;
2423 Py_SET_SIZE(z, Py_SIZE(z) + 1);
2424 }
2425 else {
2426 PyLongObject *tmp;
2427 /* Extremely rare. Get more space. */
2428 assert(Py_SIZE(z) == size_z);
2429 tmp = _PyLong_New(size_z + 1);
2430 if (tmp == NULL) {
2431 Py_DECREF(z);
2432 return NULL;
2433 }
2434 memcpy(tmp->ob_digit,
2435 z->ob_digit,
2436 sizeof(digit) * size_z);
2437 Py_DECREF(z);
2438 z = tmp;
2439 z->ob_digit[size_z] = (digit)c;
2440 ++size_z;
2441 }
2442 }
2443 }
2444 }
2445 if (z == NULL) {
2446 return NULL;
2447 }
2448 if (error_if_nonzero) {
2449 /* reset the base to 0, else the exception message
2450 doesn't make too much sense */
2451 base = 0;
2452 if (Py_SIZE(z) != 0) {
2453 goto onError;
2454 }
2455 /* there might still be other problems, therefore base
2456 remains zero here for the same reason */
2457 }
2458 if (str == start) {
2459 goto onError;
2460 }
2461 if (sign < 0) {
2462 Py_SET_SIZE(z, -(Py_SIZE(z)));
2463 }
2464 while (*str && Py_ISSPACE(*str)) {
2465 str++;
2466 }
2467 if (*str != '\0') {
2468 goto onError;
2469 }
2470 long_normalize(z);
2471 z = maybe_small_long(z);
2472 if (z == NULL) {
2473 return NULL;
2474 }
2475 if (pend != NULL) {
2476 *pend = (char *)str;
2477 }
2478 return (PyObject *) z;
2479
2480 onError:
2481 if (pend != NULL) {
2482 *pend = (char *)str;
2483 }
2484 Py_XDECREF(z);
2485 slen = strlen(orig_str) < 200 ? strlen(orig_str) : 200;
2486 strobj = PyUnicode_FromStringAndSize(orig_str, slen);
2487 if (strobj == NULL) {
2488 return NULL;
2489 }
2490 PyErr_Format(PyExc_ValueError,
2491 "invalid literal for int() with base %d: %.200R",
2492 base, strobj);
2493 Py_DECREF(strobj);
2494 return NULL;
2495 }
2496
2497 /* Since PyLong_FromString doesn't have a length parameter,
2498 * check here for possible NULs in the string.
2499 *
2500 * Reports an invalid literal as a bytes object.
2501 */
2502 PyObject *
_PyLong_FromBytes(const char * s,Py_ssize_t len,int base)2503 _PyLong_FromBytes(const char *s, Py_ssize_t len, int base)
2504 {
2505 PyObject *result, *strobj;
2506 char *end = NULL;
2507
2508 result = PyLong_FromString(s, &end, base);
2509 if (end == NULL || (result != NULL && end == s + len))
2510 return result;
2511 Py_XDECREF(result);
2512 strobj = PyBytes_FromStringAndSize(s, Py_MIN(len, 200));
2513 if (strobj != NULL) {
2514 PyErr_Format(PyExc_ValueError,
2515 "invalid literal for int() with base %d: %.200R",
2516 base, strobj);
2517 Py_DECREF(strobj);
2518 }
2519 return NULL;
2520 }
2521
2522 PyObject *
PyLong_FromUnicodeObject(PyObject * u,int base)2523 PyLong_FromUnicodeObject(PyObject *u, int base)
2524 {
2525 PyObject *result, *asciidig;
2526 const char *buffer;
2527 char *end = NULL;
2528 Py_ssize_t buflen;
2529
2530 asciidig = _PyUnicode_TransformDecimalAndSpaceToASCII(u);
2531 if (asciidig == NULL)
2532 return NULL;
2533 assert(PyUnicode_IS_ASCII(asciidig));
2534 /* Simply get a pointer to existing ASCII characters. */
2535 buffer = PyUnicode_AsUTF8AndSize(asciidig, &buflen);
2536 assert(buffer != NULL);
2537
2538 result = PyLong_FromString(buffer, &end, base);
2539 if (end == NULL || (result != NULL && end == buffer + buflen)) {
2540 Py_DECREF(asciidig);
2541 return result;
2542 }
2543 Py_DECREF(asciidig);
2544 Py_XDECREF(result);
2545 PyErr_Format(PyExc_ValueError,
2546 "invalid literal for int() with base %d: %.200R",
2547 base, u);
2548 return NULL;
2549 }
2550
2551 /* forward */
2552 static PyLongObject *x_divrem
2553 (PyLongObject *, PyLongObject *, PyLongObject **);
2554 static PyObject *long_long(PyObject *v);
2555
2556 /* Int division with remainder, top-level routine */
2557
2558 static int
long_divrem(PyLongObject * a,PyLongObject * b,PyLongObject ** pdiv,PyLongObject ** prem)2559 long_divrem(PyLongObject *a, PyLongObject *b,
2560 PyLongObject **pdiv, PyLongObject **prem)
2561 {
2562 Py_ssize_t size_a = Py_ABS(Py_SIZE(a)), size_b = Py_ABS(Py_SIZE(b));
2563 PyLongObject *z;
2564
2565 if (size_b == 0) {
2566 PyErr_SetString(PyExc_ZeroDivisionError,
2567 "integer division or modulo by zero");
2568 return -1;
2569 }
2570 if (size_a < size_b ||
2571 (size_a == size_b &&
2572 a->ob_digit[size_a-1] < b->ob_digit[size_b-1])) {
2573 /* |a| < |b|. */
2574 *prem = (PyLongObject *)long_long((PyObject *)a);
2575 if (*prem == NULL) {
2576 return -1;
2577 }
2578 PyObject *zero = _PyLong_GetZero();
2579 Py_INCREF(zero);
2580 *pdiv = (PyLongObject*)zero;
2581 return 0;
2582 }
2583 if (size_b == 1) {
2584 digit rem = 0;
2585 z = divrem1(a, b->ob_digit[0], &rem);
2586 if (z == NULL)
2587 return -1;
2588 *prem = (PyLongObject *) PyLong_FromLong((long)rem);
2589 if (*prem == NULL) {
2590 Py_DECREF(z);
2591 return -1;
2592 }
2593 }
2594 else {
2595 z = x_divrem(a, b, prem);
2596 if (z == NULL)
2597 return -1;
2598 }
2599 /* Set the signs.
2600 The quotient z has the sign of a*b;
2601 the remainder r has the sign of a,
2602 so a = b*z + r. */
2603 if ((Py_SIZE(a) < 0) != (Py_SIZE(b) < 0)) {
2604 _PyLong_Negate(&z);
2605 if (z == NULL) {
2606 Py_CLEAR(*prem);
2607 return -1;
2608 }
2609 }
2610 if (Py_SIZE(a) < 0 && Py_SIZE(*prem) != 0) {
2611 _PyLong_Negate(prem);
2612 if (*prem == NULL) {
2613 Py_DECREF(z);
2614 Py_CLEAR(*prem);
2615 return -1;
2616 }
2617 }
2618 *pdiv = maybe_small_long(z);
2619 return 0;
2620 }
2621
2622 /* Unsigned int division with remainder -- the algorithm. The arguments v1
2623 and w1 should satisfy 2 <= Py_ABS(Py_SIZE(w1)) <= Py_ABS(Py_SIZE(v1)). */
2624
2625 static PyLongObject *
x_divrem(PyLongObject * v1,PyLongObject * w1,PyLongObject ** prem)2626 x_divrem(PyLongObject *v1, PyLongObject *w1, PyLongObject **prem)
2627 {
2628 PyLongObject *v, *w, *a;
2629 Py_ssize_t i, k, size_v, size_w;
2630 int d;
2631 digit wm1, wm2, carry, q, r, vtop, *v0, *vk, *w0, *ak;
2632 twodigits vv;
2633 sdigit zhi;
2634 stwodigits z;
2635
2636 /* We follow Knuth [The Art of Computer Programming, Vol. 2 (3rd
2637 edn.), section 4.3.1, Algorithm D], except that we don't explicitly
2638 handle the special case when the initial estimate q for a quotient
2639 digit is >= PyLong_BASE: the max value for q is PyLong_BASE+1, and
2640 that won't overflow a digit. */
2641
2642 /* allocate space; w will also be used to hold the final remainder */
2643 size_v = Py_ABS(Py_SIZE(v1));
2644 size_w = Py_ABS(Py_SIZE(w1));
2645 assert(size_v >= size_w && size_w >= 2); /* Assert checks by div() */
2646 v = _PyLong_New(size_v+1);
2647 if (v == NULL) {
2648 *prem = NULL;
2649 return NULL;
2650 }
2651 w = _PyLong_New(size_w);
2652 if (w == NULL) {
2653 Py_DECREF(v);
2654 *prem = NULL;
2655 return NULL;
2656 }
2657
2658 /* normalize: shift w1 left so that its top digit is >= PyLong_BASE/2.
2659 shift v1 left by the same amount. Results go into w and v. */
2660 d = PyLong_SHIFT - bit_length_digit(w1->ob_digit[size_w-1]);
2661 carry = v_lshift(w->ob_digit, w1->ob_digit, size_w, d);
2662 assert(carry == 0);
2663 carry = v_lshift(v->ob_digit, v1->ob_digit, size_v, d);
2664 if (carry != 0 || v->ob_digit[size_v-1] >= w->ob_digit[size_w-1]) {
2665 v->ob_digit[size_v] = carry;
2666 size_v++;
2667 }
2668
2669 /* Now v->ob_digit[size_v-1] < w->ob_digit[size_w-1], so quotient has
2670 at most (and usually exactly) k = size_v - size_w digits. */
2671 k = size_v - size_w;
2672 assert(k >= 0);
2673 a = _PyLong_New(k);
2674 if (a == NULL) {
2675 Py_DECREF(w);
2676 Py_DECREF(v);
2677 *prem = NULL;
2678 return NULL;
2679 }
2680 v0 = v->ob_digit;
2681 w0 = w->ob_digit;
2682 wm1 = w0[size_w-1];
2683 wm2 = w0[size_w-2];
2684 for (vk = v0+k, ak = a->ob_digit + k; vk-- > v0;) {
2685 /* inner loop: divide vk[0:size_w+1] by w0[0:size_w], giving
2686 single-digit quotient q, remainder in vk[0:size_w]. */
2687
2688 SIGCHECK({
2689 Py_DECREF(a);
2690 Py_DECREF(w);
2691 Py_DECREF(v);
2692 *prem = NULL;
2693 return NULL;
2694 });
2695
2696 /* estimate quotient digit q; may overestimate by 1 (rare) */
2697 vtop = vk[size_w];
2698 assert(vtop <= wm1);
2699 vv = ((twodigits)vtop << PyLong_SHIFT) | vk[size_w-1];
2700 q = (digit)(vv / wm1);
2701 r = (digit)(vv - (twodigits)wm1 * q); /* r = vv % wm1 */
2702 while ((twodigits)wm2 * q > (((twodigits)r << PyLong_SHIFT)
2703 | vk[size_w-2])) {
2704 --q;
2705 r += wm1;
2706 if (r >= PyLong_BASE)
2707 break;
2708 }
2709 assert(q <= PyLong_BASE);
2710
2711 /* subtract q*w0[0:size_w] from vk[0:size_w+1] */
2712 zhi = 0;
2713 for (i = 0; i < size_w; ++i) {
2714 /* invariants: -PyLong_BASE <= -q <= zhi <= 0;
2715 -PyLong_BASE * q <= z < PyLong_BASE */
2716 z = (sdigit)vk[i] + zhi -
2717 (stwodigits)q * (stwodigits)w0[i];
2718 vk[i] = (digit)z & PyLong_MASK;
2719 zhi = (sdigit)Py_ARITHMETIC_RIGHT_SHIFT(stwodigits,
2720 z, PyLong_SHIFT);
2721 }
2722
2723 /* add w back if q was too large (this branch taken rarely) */
2724 assert((sdigit)vtop + zhi == -1 || (sdigit)vtop + zhi == 0);
2725 if ((sdigit)vtop + zhi < 0) {
2726 carry = 0;
2727 for (i = 0; i < size_w; ++i) {
2728 carry += vk[i] + w0[i];
2729 vk[i] = carry & PyLong_MASK;
2730 carry >>= PyLong_SHIFT;
2731 }
2732 --q;
2733 }
2734
2735 /* store quotient digit */
2736 assert(q < PyLong_BASE);
2737 *--ak = q;
2738 }
2739
2740 /* unshift remainder; we reuse w to store the result */
2741 carry = v_rshift(w0, v0, size_w, d);
2742 assert(carry==0);
2743 Py_DECREF(v);
2744
2745 *prem = long_normalize(w);
2746 return long_normalize(a);
2747 }
2748
2749 /* For a nonzero PyLong a, express a in the form x * 2**e, with 0.5 <=
2750 abs(x) < 1.0 and e >= 0; return x and put e in *e. Here x is
2751 rounded to DBL_MANT_DIG significant bits using round-half-to-even.
2752 If a == 0, return 0.0 and set *e = 0. If the resulting exponent
2753 e is larger than PY_SSIZE_T_MAX, raise OverflowError and return
2754 -1.0. */
2755
2756 /* attempt to define 2.0**DBL_MANT_DIG as a compile-time constant */
2757 #if DBL_MANT_DIG == 53
2758 #define EXP2_DBL_MANT_DIG 9007199254740992.0
2759 #else
2760 #define EXP2_DBL_MANT_DIG (ldexp(1.0, DBL_MANT_DIG))
2761 #endif
2762
2763 double
_PyLong_Frexp(PyLongObject * a,Py_ssize_t * e)2764 _PyLong_Frexp(PyLongObject *a, Py_ssize_t *e)
2765 {
2766 Py_ssize_t a_size, a_bits, shift_digits, shift_bits, x_size;
2767 /* See below for why x_digits is always large enough. */
2768 digit rem;
2769 digit x_digits[2 + (DBL_MANT_DIG + 1) / PyLong_SHIFT] = {0,};
2770 double dx;
2771 /* Correction term for round-half-to-even rounding. For a digit x,
2772 "x + half_even_correction[x & 7]" gives x rounded to the nearest
2773 multiple of 4, rounding ties to a multiple of 8. */
2774 static const int half_even_correction[8] = {0, -1, -2, 1, 0, -1, 2, 1};
2775
2776 a_size = Py_ABS(Py_SIZE(a));
2777 if (a_size == 0) {
2778 /* Special case for 0: significand 0.0, exponent 0. */
2779 *e = 0;
2780 return 0.0;
2781 }
2782 a_bits = bit_length_digit(a->ob_digit[a_size-1]);
2783 /* The following is an overflow-free version of the check
2784 "if ((a_size - 1) * PyLong_SHIFT + a_bits > PY_SSIZE_T_MAX) ..." */
2785 if (a_size >= (PY_SSIZE_T_MAX - 1) / PyLong_SHIFT + 1 &&
2786 (a_size > (PY_SSIZE_T_MAX - 1) / PyLong_SHIFT + 1 ||
2787 a_bits > (PY_SSIZE_T_MAX - 1) % PyLong_SHIFT + 1))
2788 goto overflow;
2789 a_bits = (a_size - 1) * PyLong_SHIFT + a_bits;
2790
2791 /* Shift the first DBL_MANT_DIG + 2 bits of a into x_digits[0:x_size]
2792 (shifting left if a_bits <= DBL_MANT_DIG + 2).
2793
2794 Number of digits needed for result: write // for floor division.
2795 Then if shifting left, we end up using
2796
2797 1 + a_size + (DBL_MANT_DIG + 2 - a_bits) // PyLong_SHIFT
2798
2799 digits. If shifting right, we use
2800
2801 a_size - (a_bits - DBL_MANT_DIG - 2) // PyLong_SHIFT
2802
2803 digits. Using a_size = 1 + (a_bits - 1) // PyLong_SHIFT along with
2804 the inequalities
2805
2806 m // PyLong_SHIFT + n // PyLong_SHIFT <= (m + n) // PyLong_SHIFT
2807 m // PyLong_SHIFT - n // PyLong_SHIFT <=
2808 1 + (m - n - 1) // PyLong_SHIFT,
2809
2810 valid for any integers m and n, we find that x_size satisfies
2811
2812 x_size <= 2 + (DBL_MANT_DIG + 1) // PyLong_SHIFT
2813
2814 in both cases.
2815 */
2816 if (a_bits <= DBL_MANT_DIG + 2) {
2817 shift_digits = (DBL_MANT_DIG + 2 - a_bits) / PyLong_SHIFT;
2818 shift_bits = (DBL_MANT_DIG + 2 - a_bits) % PyLong_SHIFT;
2819 x_size = shift_digits;
2820 rem = v_lshift(x_digits + x_size, a->ob_digit, a_size,
2821 (int)shift_bits);
2822 x_size += a_size;
2823 x_digits[x_size++] = rem;
2824 }
2825 else {
2826 shift_digits = (a_bits - DBL_MANT_DIG - 2) / PyLong_SHIFT;
2827 shift_bits = (a_bits - DBL_MANT_DIG - 2) % PyLong_SHIFT;
2828 rem = v_rshift(x_digits, a->ob_digit + shift_digits,
2829 a_size - shift_digits, (int)shift_bits);
2830 x_size = a_size - shift_digits;
2831 /* For correct rounding below, we need the least significant
2832 bit of x to be 'sticky' for this shift: if any of the bits
2833 shifted out was nonzero, we set the least significant bit
2834 of x. */
2835 if (rem)
2836 x_digits[0] |= 1;
2837 else
2838 while (shift_digits > 0)
2839 if (a->ob_digit[--shift_digits]) {
2840 x_digits[0] |= 1;
2841 break;
2842 }
2843 }
2844 assert(1 <= x_size && x_size <= (Py_ssize_t)Py_ARRAY_LENGTH(x_digits));
2845
2846 /* Round, and convert to double. */
2847 x_digits[0] += half_even_correction[x_digits[0] & 7];
2848 dx = x_digits[--x_size];
2849 while (x_size > 0)
2850 dx = dx * PyLong_BASE + x_digits[--x_size];
2851
2852 /* Rescale; make correction if result is 1.0. */
2853 dx /= 4.0 * EXP2_DBL_MANT_DIG;
2854 if (dx == 1.0) {
2855 if (a_bits == PY_SSIZE_T_MAX)
2856 goto overflow;
2857 dx = 0.5;
2858 a_bits += 1;
2859 }
2860
2861 *e = a_bits;
2862 return Py_SIZE(a) < 0 ? -dx : dx;
2863
2864 overflow:
2865 /* exponent > PY_SSIZE_T_MAX */
2866 PyErr_SetString(PyExc_OverflowError,
2867 "huge integer: number of bits overflows a Py_ssize_t");
2868 *e = 0;
2869 return -1.0;
2870 }
2871
2872 /* Get a C double from an int object. Rounds to the nearest double,
2873 using the round-half-to-even rule in the case of a tie. */
2874
2875 double
PyLong_AsDouble(PyObject * v)2876 PyLong_AsDouble(PyObject *v)
2877 {
2878 Py_ssize_t exponent;
2879 double x;
2880
2881 if (v == NULL) {
2882 PyErr_BadInternalCall();
2883 return -1.0;
2884 }
2885 if (!PyLong_Check(v)) {
2886 PyErr_SetString(PyExc_TypeError, "an integer is required");
2887 return -1.0;
2888 }
2889 if (Py_ABS(Py_SIZE(v)) <= 1) {
2890 /* Fast path; single digit long (31 bits) will cast safely
2891 to double. This improves performance of FP/long operations
2892 by 20%.
2893 */
2894 return (double)MEDIUM_VALUE((PyLongObject *)v);
2895 }
2896 x = _PyLong_Frexp((PyLongObject *)v, &exponent);
2897 if ((x == -1.0 && PyErr_Occurred()) || exponent > DBL_MAX_EXP) {
2898 PyErr_SetString(PyExc_OverflowError,
2899 "int too large to convert to float");
2900 return -1.0;
2901 }
2902 return ldexp(x, (int)exponent);
2903 }
2904
2905 /* Methods */
2906
2907 /* if a < b, return a negative number
2908 if a == b, return 0
2909 if a > b, return a positive number */
2910
2911 static Py_ssize_t
long_compare(PyLongObject * a,PyLongObject * b)2912 long_compare(PyLongObject *a, PyLongObject *b)
2913 {
2914 Py_ssize_t sign = Py_SIZE(a) - Py_SIZE(b);
2915 if (sign == 0) {
2916 Py_ssize_t i = Py_ABS(Py_SIZE(a));
2917 sdigit diff = 0;
2918 while (--i >= 0) {
2919 diff = (sdigit) a->ob_digit[i] - (sdigit) b->ob_digit[i];
2920 if (diff) {
2921 break;
2922 }
2923 }
2924 sign = Py_SIZE(a) < 0 ? -diff : diff;
2925 }
2926 return sign;
2927 }
2928
2929 static PyObject *
long_richcompare(PyObject * self,PyObject * other,int op)2930 long_richcompare(PyObject *self, PyObject *other, int op)
2931 {
2932 Py_ssize_t result;
2933 CHECK_BINOP(self, other);
2934 if (self == other)
2935 result = 0;
2936 else
2937 result = long_compare((PyLongObject*)self, (PyLongObject*)other);
2938 Py_RETURN_RICHCOMPARE(result, 0, op);
2939 }
2940
2941 static Py_hash_t
long_hash(PyLongObject * v)2942 long_hash(PyLongObject *v)
2943 {
2944 Py_uhash_t x;
2945 Py_ssize_t i;
2946 int sign;
2947
2948 i = Py_SIZE(v);
2949 switch(i) {
2950 case -1: return v->ob_digit[0]==1 ? -2 : -(sdigit)v->ob_digit[0];
2951 case 0: return 0;
2952 case 1: return v->ob_digit[0];
2953 }
2954 sign = 1;
2955 x = 0;
2956 if (i < 0) {
2957 sign = -1;
2958 i = -(i);
2959 }
2960 while (--i >= 0) {
2961 /* Here x is a quantity in the range [0, _PyHASH_MODULUS); we
2962 want to compute x * 2**PyLong_SHIFT + v->ob_digit[i] modulo
2963 _PyHASH_MODULUS.
2964
2965 The computation of x * 2**PyLong_SHIFT % _PyHASH_MODULUS
2966 amounts to a rotation of the bits of x. To see this, write
2967
2968 x * 2**PyLong_SHIFT = y * 2**_PyHASH_BITS + z
2969
2970 where y = x >> (_PyHASH_BITS - PyLong_SHIFT) gives the top
2971 PyLong_SHIFT bits of x (those that are shifted out of the
2972 original _PyHASH_BITS bits, and z = (x << PyLong_SHIFT) &
2973 _PyHASH_MODULUS gives the bottom _PyHASH_BITS - PyLong_SHIFT
2974 bits of x, shifted up. Then since 2**_PyHASH_BITS is
2975 congruent to 1 modulo _PyHASH_MODULUS, y*2**_PyHASH_BITS is
2976 congruent to y modulo _PyHASH_MODULUS. So
2977
2978 x * 2**PyLong_SHIFT = y + z (mod _PyHASH_MODULUS).
2979
2980 The right-hand side is just the result of rotating the
2981 _PyHASH_BITS bits of x left by PyLong_SHIFT places; since
2982 not all _PyHASH_BITS bits of x are 1s, the same is true
2983 after rotation, so 0 <= y+z < _PyHASH_MODULUS and y + z is
2984 the reduction of x*2**PyLong_SHIFT modulo
2985 _PyHASH_MODULUS. */
2986 x = ((x << PyLong_SHIFT) & _PyHASH_MODULUS) |
2987 (x >> (_PyHASH_BITS - PyLong_SHIFT));
2988 x += v->ob_digit[i];
2989 if (x >= _PyHASH_MODULUS)
2990 x -= _PyHASH_MODULUS;
2991 }
2992 x = x * sign;
2993 if (x == (Py_uhash_t)-1)
2994 x = (Py_uhash_t)-2;
2995 return (Py_hash_t)x;
2996 }
2997
2998
2999 /* Add the absolute values of two integers. */
3000
3001 static PyLongObject *
x_add(PyLongObject * a,PyLongObject * b)3002 x_add(PyLongObject *a, PyLongObject *b)
3003 {
3004 Py_ssize_t size_a = Py_ABS(Py_SIZE(a)), size_b = Py_ABS(Py_SIZE(b));
3005 PyLongObject *z;
3006 Py_ssize_t i;
3007 digit carry = 0;
3008
3009 /* Ensure a is the larger of the two: */
3010 if (size_a < size_b) {
3011 { PyLongObject *temp = a; a = b; b = temp; }
3012 { Py_ssize_t size_temp = size_a;
3013 size_a = size_b;
3014 size_b = size_temp; }
3015 }
3016 z = _PyLong_New(size_a+1);
3017 if (z == NULL)
3018 return NULL;
3019 for (i = 0; i < size_b; ++i) {
3020 carry += a->ob_digit[i] + b->ob_digit[i];
3021 z->ob_digit[i] = carry & PyLong_MASK;
3022 carry >>= PyLong_SHIFT;
3023 }
3024 for (; i < size_a; ++i) {
3025 carry += a->ob_digit[i];
3026 z->ob_digit[i] = carry & PyLong_MASK;
3027 carry >>= PyLong_SHIFT;
3028 }
3029 z->ob_digit[i] = carry;
3030 return long_normalize(z);
3031 }
3032
3033 /* Subtract the absolute values of two integers. */
3034
3035 static PyLongObject *
x_sub(PyLongObject * a,PyLongObject * b)3036 x_sub(PyLongObject *a, PyLongObject *b)
3037 {
3038 Py_ssize_t size_a = Py_ABS(Py_SIZE(a)), size_b = Py_ABS(Py_SIZE(b));
3039 PyLongObject *z;
3040 Py_ssize_t i;
3041 int sign = 1;
3042 digit borrow = 0;
3043
3044 /* Ensure a is the larger of the two: */
3045 if (size_a < size_b) {
3046 sign = -1;
3047 { PyLongObject *temp = a; a = b; b = temp; }
3048 { Py_ssize_t size_temp = size_a;
3049 size_a = size_b;
3050 size_b = size_temp; }
3051 }
3052 else if (size_a == size_b) {
3053 /* Find highest digit where a and b differ: */
3054 i = size_a;
3055 while (--i >= 0 && a->ob_digit[i] == b->ob_digit[i])
3056 ;
3057 if (i < 0)
3058 return (PyLongObject *)PyLong_FromLong(0);
3059 if (a->ob_digit[i] < b->ob_digit[i]) {
3060 sign = -1;
3061 { PyLongObject *temp = a; a = b; b = temp; }
3062 }
3063 size_a = size_b = i+1;
3064 }
3065 z = _PyLong_New(size_a);
3066 if (z == NULL)
3067 return NULL;
3068 for (i = 0; i < size_b; ++i) {
3069 /* The following assumes unsigned arithmetic
3070 works module 2**N for some N>PyLong_SHIFT. */
3071 borrow = a->ob_digit[i] - b->ob_digit[i] - borrow;
3072 z->ob_digit[i] = borrow & PyLong_MASK;
3073 borrow >>= PyLong_SHIFT;
3074 borrow &= 1; /* Keep only one sign bit */
3075 }
3076 for (; i < size_a; ++i) {
3077 borrow = a->ob_digit[i] - borrow;
3078 z->ob_digit[i] = borrow & PyLong_MASK;
3079 borrow >>= PyLong_SHIFT;
3080 borrow &= 1; /* Keep only one sign bit */
3081 }
3082 assert(borrow == 0);
3083 if (sign < 0) {
3084 Py_SET_SIZE(z, -Py_SIZE(z));
3085 }
3086 return maybe_small_long(long_normalize(z));
3087 }
3088
3089 static PyObject *
long_add(PyLongObject * a,PyLongObject * b)3090 long_add(PyLongObject *a, PyLongObject *b)
3091 {
3092 PyLongObject *z;
3093
3094 CHECK_BINOP(a, b);
3095
3096 if (Py_ABS(Py_SIZE(a)) <= 1 && Py_ABS(Py_SIZE(b)) <= 1) {
3097 return PyLong_FromLong(MEDIUM_VALUE(a) + MEDIUM_VALUE(b));
3098 }
3099 if (Py_SIZE(a) < 0) {
3100 if (Py_SIZE(b) < 0) {
3101 z = x_add(a, b);
3102 if (z != NULL) {
3103 /* x_add received at least one multiple-digit int,
3104 and thus z must be a multiple-digit int.
3105 That also means z is not an element of
3106 small_ints, so negating it in-place is safe. */
3107 assert(Py_REFCNT(z) == 1);
3108 Py_SET_SIZE(z, -(Py_SIZE(z)));
3109 }
3110 }
3111 else
3112 z = x_sub(b, a);
3113 }
3114 else {
3115 if (Py_SIZE(b) < 0)
3116 z = x_sub(a, b);
3117 else
3118 z = x_add(a, b);
3119 }
3120 return (PyObject *)z;
3121 }
3122
3123 static PyObject *
long_sub(PyLongObject * a,PyLongObject * b)3124 long_sub(PyLongObject *a, PyLongObject *b)
3125 {
3126 PyLongObject *z;
3127
3128 CHECK_BINOP(a, b);
3129
3130 if (Py_ABS(Py_SIZE(a)) <= 1 && Py_ABS(Py_SIZE(b)) <= 1) {
3131 return PyLong_FromLong(MEDIUM_VALUE(a) - MEDIUM_VALUE(b));
3132 }
3133 if (Py_SIZE(a) < 0) {
3134 if (Py_SIZE(b) < 0) {
3135 z = x_sub(b, a);
3136 }
3137 else {
3138 z = x_add(a, b);
3139 if (z != NULL) {
3140 assert(Py_SIZE(z) == 0 || Py_REFCNT(z) == 1);
3141 Py_SET_SIZE(z, -(Py_SIZE(z)));
3142 }
3143 }
3144 }
3145 else {
3146 if (Py_SIZE(b) < 0)
3147 z = x_add(a, b);
3148 else
3149 z = x_sub(a, b);
3150 }
3151 return (PyObject *)z;
3152 }
3153
3154 /* Grade school multiplication, ignoring the signs.
3155 * Returns the absolute value of the product, or NULL if error.
3156 */
3157 static PyLongObject *
x_mul(PyLongObject * a,PyLongObject * b)3158 x_mul(PyLongObject *a, PyLongObject *b)
3159 {
3160 PyLongObject *z;
3161 Py_ssize_t size_a = Py_ABS(Py_SIZE(a));
3162 Py_ssize_t size_b = Py_ABS(Py_SIZE(b));
3163 Py_ssize_t i;
3164
3165 z = _PyLong_New(size_a + size_b);
3166 if (z == NULL)
3167 return NULL;
3168
3169 memset(z->ob_digit, 0, Py_SIZE(z) * sizeof(digit));
3170 if (a == b) {
3171 /* Efficient squaring per HAC, Algorithm 14.16:
3172 * http://www.cacr.math.uwaterloo.ca/hac/about/chap14.pdf
3173 * Gives slightly less than a 2x speedup when a == b,
3174 * via exploiting that each entry in the multiplication
3175 * pyramid appears twice (except for the size_a squares).
3176 */
3177 for (i = 0; i < size_a; ++i) {
3178 twodigits carry;
3179 twodigits f = a->ob_digit[i];
3180 digit *pz = z->ob_digit + (i << 1);
3181 digit *pa = a->ob_digit + i + 1;
3182 digit *paend = a->ob_digit + size_a;
3183
3184 SIGCHECK({
3185 Py_DECREF(z);
3186 return NULL;
3187 });
3188
3189 carry = *pz + f * f;
3190 *pz++ = (digit)(carry & PyLong_MASK);
3191 carry >>= PyLong_SHIFT;
3192 assert(carry <= PyLong_MASK);
3193
3194 /* Now f is added in twice in each column of the
3195 * pyramid it appears. Same as adding f<<1 once.
3196 */
3197 f <<= 1;
3198 while (pa < paend) {
3199 carry += *pz + *pa++ * f;
3200 *pz++ = (digit)(carry & PyLong_MASK);
3201 carry >>= PyLong_SHIFT;
3202 assert(carry <= (PyLong_MASK << 1));
3203 }
3204 if (carry) {
3205 carry += *pz;
3206 *pz++ = (digit)(carry & PyLong_MASK);
3207 carry >>= PyLong_SHIFT;
3208 }
3209 if (carry)
3210 *pz += (digit)(carry & PyLong_MASK);
3211 assert((carry >> PyLong_SHIFT) == 0);
3212 }
3213 }
3214 else { /* a is not the same as b -- gradeschool int mult */
3215 for (i = 0; i < size_a; ++i) {
3216 twodigits carry = 0;
3217 twodigits f = a->ob_digit[i];
3218 digit *pz = z->ob_digit + i;
3219 digit *pb = b->ob_digit;
3220 digit *pbend = b->ob_digit + size_b;
3221
3222 SIGCHECK({
3223 Py_DECREF(z);
3224 return NULL;
3225 });
3226
3227 while (pb < pbend) {
3228 carry += *pz + *pb++ * f;
3229 *pz++ = (digit)(carry & PyLong_MASK);
3230 carry >>= PyLong_SHIFT;
3231 assert(carry <= PyLong_MASK);
3232 }
3233 if (carry)
3234 *pz += (digit)(carry & PyLong_MASK);
3235 assert((carry >> PyLong_SHIFT) == 0);
3236 }
3237 }
3238 return long_normalize(z);
3239 }
3240
3241 /* A helper for Karatsuba multiplication (k_mul).
3242 Takes an int "n" and an integer "size" representing the place to
3243 split, and sets low and high such that abs(n) == (high << size) + low,
3244 viewing the shift as being by digits. The sign bit is ignored, and
3245 the return values are >= 0.
3246 Returns 0 on success, -1 on failure.
3247 */
3248 static int
kmul_split(PyLongObject * n,Py_ssize_t size,PyLongObject ** high,PyLongObject ** low)3249 kmul_split(PyLongObject *n,
3250 Py_ssize_t size,
3251 PyLongObject **high,
3252 PyLongObject **low)
3253 {
3254 PyLongObject *hi, *lo;
3255 Py_ssize_t size_lo, size_hi;
3256 const Py_ssize_t size_n = Py_ABS(Py_SIZE(n));
3257
3258 size_lo = Py_MIN(size_n, size);
3259 size_hi = size_n - size_lo;
3260
3261 if ((hi = _PyLong_New(size_hi)) == NULL)
3262 return -1;
3263 if ((lo = _PyLong_New(size_lo)) == NULL) {
3264 Py_DECREF(hi);
3265 return -1;
3266 }
3267
3268 memcpy(lo->ob_digit, n->ob_digit, size_lo * sizeof(digit));
3269 memcpy(hi->ob_digit, n->ob_digit + size_lo, size_hi * sizeof(digit));
3270
3271 *high = long_normalize(hi);
3272 *low = long_normalize(lo);
3273 return 0;
3274 }
3275
3276 static PyLongObject *k_lopsided_mul(PyLongObject *a, PyLongObject *b);
3277
3278 /* Karatsuba multiplication. Ignores the input signs, and returns the
3279 * absolute value of the product (or NULL if error).
3280 * See Knuth Vol. 2 Chapter 4.3.3 (Pp. 294-295).
3281 */
3282 static PyLongObject *
k_mul(PyLongObject * a,PyLongObject * b)3283 k_mul(PyLongObject *a, PyLongObject *b)
3284 {
3285 Py_ssize_t asize = Py_ABS(Py_SIZE(a));
3286 Py_ssize_t bsize = Py_ABS(Py_SIZE(b));
3287 PyLongObject *ah = NULL;
3288 PyLongObject *al = NULL;
3289 PyLongObject *bh = NULL;
3290 PyLongObject *bl = NULL;
3291 PyLongObject *ret = NULL;
3292 PyLongObject *t1, *t2, *t3;
3293 Py_ssize_t shift; /* the number of digits we split off */
3294 Py_ssize_t i;
3295
3296 /* (ah*X+al)(bh*X+bl) = ah*bh*X*X + (ah*bl + al*bh)*X + al*bl
3297 * Let k = (ah+al)*(bh+bl) = ah*bl + al*bh + ah*bh + al*bl
3298 * Then the original product is
3299 * ah*bh*X*X + (k - ah*bh - al*bl)*X + al*bl
3300 * By picking X to be a power of 2, "*X" is just shifting, and it's
3301 * been reduced to 3 multiplies on numbers half the size.
3302 */
3303
3304 /* We want to split based on the larger number; fiddle so that b
3305 * is largest.
3306 */
3307 if (asize > bsize) {
3308 t1 = a;
3309 a = b;
3310 b = t1;
3311
3312 i = asize;
3313 asize = bsize;
3314 bsize = i;
3315 }
3316
3317 /* Use gradeschool math when either number is too small. */
3318 i = a == b ? KARATSUBA_SQUARE_CUTOFF : KARATSUBA_CUTOFF;
3319 if (asize <= i) {
3320 if (asize == 0)
3321 return (PyLongObject *)PyLong_FromLong(0);
3322 else
3323 return x_mul(a, b);
3324 }
3325
3326 /* If a is small compared to b, splitting on b gives a degenerate
3327 * case with ah==0, and Karatsuba may be (even much) less efficient
3328 * than "grade school" then. However, we can still win, by viewing
3329 * b as a string of "big digits", each of width a->ob_size. That
3330 * leads to a sequence of balanced calls to k_mul.
3331 */
3332 if (2 * asize <= bsize)
3333 return k_lopsided_mul(a, b);
3334
3335 /* Split a & b into hi & lo pieces. */
3336 shift = bsize >> 1;
3337 if (kmul_split(a, shift, &ah, &al) < 0) goto fail;
3338 assert(Py_SIZE(ah) > 0); /* the split isn't degenerate */
3339
3340 if (a == b) {
3341 bh = ah;
3342 bl = al;
3343 Py_INCREF(bh);
3344 Py_INCREF(bl);
3345 }
3346 else if (kmul_split(b, shift, &bh, &bl) < 0) goto fail;
3347
3348 /* The plan:
3349 * 1. Allocate result space (asize + bsize digits: that's always
3350 * enough).
3351 * 2. Compute ah*bh, and copy into result at 2*shift.
3352 * 3. Compute al*bl, and copy into result at 0. Note that this
3353 * can't overlap with #2.
3354 * 4. Subtract al*bl from the result, starting at shift. This may
3355 * underflow (borrow out of the high digit), but we don't care:
3356 * we're effectively doing unsigned arithmetic mod
3357 * BASE**(sizea + sizeb), and so long as the *final* result fits,
3358 * borrows and carries out of the high digit can be ignored.
3359 * 5. Subtract ah*bh from the result, starting at shift.
3360 * 6. Compute (ah+al)*(bh+bl), and add it into the result starting
3361 * at shift.
3362 */
3363
3364 /* 1. Allocate result space. */
3365 ret = _PyLong_New(asize + bsize);
3366 if (ret == NULL) goto fail;
3367 #ifdef Py_DEBUG
3368 /* Fill with trash, to catch reference to uninitialized digits. */
3369 memset(ret->ob_digit, 0xDF, Py_SIZE(ret) * sizeof(digit));
3370 #endif
3371
3372 /* 2. t1 <- ah*bh, and copy into high digits of result. */
3373 if ((t1 = k_mul(ah, bh)) == NULL) goto fail;
3374 assert(Py_SIZE(t1) >= 0);
3375 assert(2*shift + Py_SIZE(t1) <= Py_SIZE(ret));
3376 memcpy(ret->ob_digit + 2*shift, t1->ob_digit,
3377 Py_SIZE(t1) * sizeof(digit));
3378
3379 /* Zero-out the digits higher than the ah*bh copy. */
3380 i = Py_SIZE(ret) - 2*shift - Py_SIZE(t1);
3381 if (i)
3382 memset(ret->ob_digit + 2*shift + Py_SIZE(t1), 0,
3383 i * sizeof(digit));
3384
3385 /* 3. t2 <- al*bl, and copy into the low digits. */
3386 if ((t2 = k_mul(al, bl)) == NULL) {
3387 Py_DECREF(t1);
3388 goto fail;
3389 }
3390 assert(Py_SIZE(t2) >= 0);
3391 assert(Py_SIZE(t2) <= 2*shift); /* no overlap with high digits */
3392 memcpy(ret->ob_digit, t2->ob_digit, Py_SIZE(t2) * sizeof(digit));
3393
3394 /* Zero out remaining digits. */
3395 i = 2*shift - Py_SIZE(t2); /* number of uninitialized digits */
3396 if (i)
3397 memset(ret->ob_digit + Py_SIZE(t2), 0, i * sizeof(digit));
3398
3399 /* 4 & 5. Subtract ah*bh (t1) and al*bl (t2). We do al*bl first
3400 * because it's fresher in cache.
3401 */
3402 i = Py_SIZE(ret) - shift; /* # digits after shift */
3403 (void)v_isub(ret->ob_digit + shift, i, t2->ob_digit, Py_SIZE(t2));
3404 Py_DECREF(t2);
3405
3406 (void)v_isub(ret->ob_digit + shift, i, t1->ob_digit, Py_SIZE(t1));
3407 Py_DECREF(t1);
3408
3409 /* 6. t3 <- (ah+al)(bh+bl), and add into result. */
3410 if ((t1 = x_add(ah, al)) == NULL) goto fail;
3411 Py_DECREF(ah);
3412 Py_DECREF(al);
3413 ah = al = NULL;
3414
3415 if (a == b) {
3416 t2 = t1;
3417 Py_INCREF(t2);
3418 }
3419 else if ((t2 = x_add(bh, bl)) == NULL) {
3420 Py_DECREF(t1);
3421 goto fail;
3422 }
3423 Py_DECREF(bh);
3424 Py_DECREF(bl);
3425 bh = bl = NULL;
3426
3427 t3 = k_mul(t1, t2);
3428 Py_DECREF(t1);
3429 Py_DECREF(t2);
3430 if (t3 == NULL) goto fail;
3431 assert(Py_SIZE(t3) >= 0);
3432
3433 /* Add t3. It's not obvious why we can't run out of room here.
3434 * See the (*) comment after this function.
3435 */
3436 (void)v_iadd(ret->ob_digit + shift, i, t3->ob_digit, Py_SIZE(t3));
3437 Py_DECREF(t3);
3438
3439 return long_normalize(ret);
3440
3441 fail:
3442 Py_XDECREF(ret);
3443 Py_XDECREF(ah);
3444 Py_XDECREF(al);
3445 Py_XDECREF(bh);
3446 Py_XDECREF(bl);
3447 return NULL;
3448 }
3449
3450 /* (*) Why adding t3 can't "run out of room" above.
3451
3452 Let f(x) mean the floor of x and c(x) mean the ceiling of x. Some facts
3453 to start with:
3454
3455 1. For any integer i, i = c(i/2) + f(i/2). In particular,
3456 bsize = c(bsize/2) + f(bsize/2).
3457 2. shift = f(bsize/2)
3458 3. asize <= bsize
3459 4. Since we call k_lopsided_mul if asize*2 <= bsize, asize*2 > bsize in this
3460 routine, so asize > bsize/2 >= f(bsize/2) in this routine.
3461
3462 We allocated asize + bsize result digits, and add t3 into them at an offset
3463 of shift. This leaves asize+bsize-shift allocated digit positions for t3
3464 to fit into, = (by #1 and #2) asize + f(bsize/2) + c(bsize/2) - f(bsize/2) =
3465 asize + c(bsize/2) available digit positions.
3466
3467 bh has c(bsize/2) digits, and bl at most f(size/2) digits. So bh+hl has
3468 at most c(bsize/2) digits + 1 bit.
3469
3470 If asize == bsize, ah has c(bsize/2) digits, else ah has at most f(bsize/2)
3471 digits, and al has at most f(bsize/2) digits in any case. So ah+al has at
3472 most (asize == bsize ? c(bsize/2) : f(bsize/2)) digits + 1 bit.
3473
3474 The product (ah+al)*(bh+bl) therefore has at most
3475
3476 c(bsize/2) + (asize == bsize ? c(bsize/2) : f(bsize/2)) digits + 2 bits
3477
3478 and we have asize + c(bsize/2) available digit positions. We need to show
3479 this is always enough. An instance of c(bsize/2) cancels out in both, so
3480 the question reduces to whether asize digits is enough to hold
3481 (asize == bsize ? c(bsize/2) : f(bsize/2)) digits + 2 bits. If asize < bsize,
3482 then we're asking whether asize digits >= f(bsize/2) digits + 2 bits. By #4,
3483 asize is at least f(bsize/2)+1 digits, so this in turn reduces to whether 1
3484 digit is enough to hold 2 bits. This is so since PyLong_SHIFT=15 >= 2. If
3485 asize == bsize, then we're asking whether bsize digits is enough to hold
3486 c(bsize/2) digits + 2 bits, or equivalently (by #1) whether f(bsize/2) digits
3487 is enough to hold 2 bits. This is so if bsize >= 2, which holds because
3488 bsize >= KARATSUBA_CUTOFF >= 2.
3489
3490 Note that since there's always enough room for (ah+al)*(bh+bl), and that's
3491 clearly >= each of ah*bh and al*bl, there's always enough room to subtract
3492 ah*bh and al*bl too.
3493 */
3494
3495 /* b has at least twice the digits of a, and a is big enough that Karatsuba
3496 * would pay off *if* the inputs had balanced sizes. View b as a sequence
3497 * of slices, each with a->ob_size digits, and multiply the slices by a,
3498 * one at a time. This gives k_mul balanced inputs to work with, and is
3499 * also cache-friendly (we compute one double-width slice of the result
3500 * at a time, then move on, never backtracking except for the helpful
3501 * single-width slice overlap between successive partial sums).
3502 */
3503 static PyLongObject *
k_lopsided_mul(PyLongObject * a,PyLongObject * b)3504 k_lopsided_mul(PyLongObject *a, PyLongObject *b)
3505 {
3506 const Py_ssize_t asize = Py_ABS(Py_SIZE(a));
3507 Py_ssize_t bsize = Py_ABS(Py_SIZE(b));
3508 Py_ssize_t nbdone; /* # of b digits already multiplied */
3509 PyLongObject *ret;
3510 PyLongObject *bslice = NULL;
3511
3512 assert(asize > KARATSUBA_CUTOFF);
3513 assert(2 * asize <= bsize);
3514
3515 /* Allocate result space, and zero it out. */
3516 ret = _PyLong_New(asize + bsize);
3517 if (ret == NULL)
3518 return NULL;
3519 memset(ret->ob_digit, 0, Py_SIZE(ret) * sizeof(digit));
3520
3521 /* Successive slices of b are copied into bslice. */
3522 bslice = _PyLong_New(asize);
3523 if (bslice == NULL)
3524 goto fail;
3525
3526 nbdone = 0;
3527 while (bsize > 0) {
3528 PyLongObject *product;
3529 const Py_ssize_t nbtouse = Py_MIN(bsize, asize);
3530
3531 /* Multiply the next slice of b by a. */
3532 memcpy(bslice->ob_digit, b->ob_digit + nbdone,
3533 nbtouse * sizeof(digit));
3534 Py_SET_SIZE(bslice, nbtouse);
3535 product = k_mul(a, bslice);
3536 if (product == NULL)
3537 goto fail;
3538
3539 /* Add into result. */
3540 (void)v_iadd(ret->ob_digit + nbdone, Py_SIZE(ret) - nbdone,
3541 product->ob_digit, Py_SIZE(product));
3542 Py_DECREF(product);
3543
3544 bsize -= nbtouse;
3545 nbdone += nbtouse;
3546 }
3547
3548 Py_DECREF(bslice);
3549 return long_normalize(ret);
3550
3551 fail:
3552 Py_DECREF(ret);
3553 Py_XDECREF(bslice);
3554 return NULL;
3555 }
3556
3557 static PyObject *
long_mul(PyLongObject * a,PyLongObject * b)3558 long_mul(PyLongObject *a, PyLongObject *b)
3559 {
3560 PyLongObject *z;
3561
3562 CHECK_BINOP(a, b);
3563
3564 /* fast path for single-digit multiplication */
3565 if (Py_ABS(Py_SIZE(a)) <= 1 && Py_ABS(Py_SIZE(b)) <= 1) {
3566 stwodigits v = (stwodigits)(MEDIUM_VALUE(a)) * MEDIUM_VALUE(b);
3567 return PyLong_FromLongLong((long long)v);
3568 }
3569
3570 z = k_mul(a, b);
3571 /* Negate if exactly one of the inputs is negative. */
3572 if (((Py_SIZE(a) ^ Py_SIZE(b)) < 0) && z) {
3573 _PyLong_Negate(&z);
3574 if (z == NULL)
3575 return NULL;
3576 }
3577 return (PyObject *)z;
3578 }
3579
3580 /* Fast modulo division for single-digit longs. */
3581 static PyObject *
fast_mod(PyLongObject * a,PyLongObject * b)3582 fast_mod(PyLongObject *a, PyLongObject *b)
3583 {
3584 sdigit left = a->ob_digit[0];
3585 sdigit right = b->ob_digit[0];
3586 sdigit mod;
3587
3588 assert(Py_ABS(Py_SIZE(a)) == 1);
3589 assert(Py_ABS(Py_SIZE(b)) == 1);
3590
3591 if (Py_SIZE(a) == Py_SIZE(b)) {
3592 /* 'a' and 'b' have the same sign. */
3593 mod = left % right;
3594 }
3595 else {
3596 /* Either 'a' or 'b' is negative. */
3597 mod = right - 1 - (left - 1) % right;
3598 }
3599
3600 return PyLong_FromLong(mod * (sdigit)Py_SIZE(b));
3601 }
3602
3603 /* Fast floor division for single-digit longs. */
3604 static PyObject *
fast_floor_div(PyLongObject * a,PyLongObject * b)3605 fast_floor_div(PyLongObject *a, PyLongObject *b)
3606 {
3607 sdigit left = a->ob_digit[0];
3608 sdigit right = b->ob_digit[0];
3609 sdigit div;
3610
3611 assert(Py_ABS(Py_SIZE(a)) == 1);
3612 assert(Py_ABS(Py_SIZE(b)) == 1);
3613
3614 if (Py_SIZE(a) == Py_SIZE(b)) {
3615 /* 'a' and 'b' have the same sign. */
3616 div = left / right;
3617 }
3618 else {
3619 /* Either 'a' or 'b' is negative. */
3620 div = -1 - (left - 1) / right;
3621 }
3622
3623 return PyLong_FromLong(div);
3624 }
3625
3626 /* The / and % operators are now defined in terms of divmod().
3627 The expression a mod b has the value a - b*floor(a/b).
3628 The long_divrem function gives the remainder after division of
3629 |a| by |b|, with the sign of a. This is also expressed
3630 as a - b*trunc(a/b), if trunc truncates towards zero.
3631 Some examples:
3632 a b a rem b a mod b
3633 13 10 3 3
3634 -13 10 -3 7
3635 13 -10 3 -7
3636 -13 -10 -3 -3
3637 So, to get from rem to mod, we have to add b if a and b
3638 have different signs. We then subtract one from the 'div'
3639 part of the outcome to keep the invariant intact. */
3640
3641 /* Compute
3642 * *pdiv, *pmod = divmod(v, w)
3643 * NULL can be passed for pdiv or pmod, in which case that part of
3644 * the result is simply thrown away. The caller owns a reference to
3645 * each of these it requests (does not pass NULL for).
3646 */
3647 static int
l_divmod(PyLongObject * v,PyLongObject * w,PyLongObject ** pdiv,PyLongObject ** pmod)3648 l_divmod(PyLongObject *v, PyLongObject *w,
3649 PyLongObject **pdiv, PyLongObject **pmod)
3650 {
3651 PyLongObject *div, *mod;
3652
3653 if (Py_ABS(Py_SIZE(v)) == 1 && Py_ABS(Py_SIZE(w)) == 1) {
3654 /* Fast path for single-digit longs */
3655 div = NULL;
3656 if (pdiv != NULL) {
3657 div = (PyLongObject *)fast_floor_div(v, w);
3658 if (div == NULL) {
3659 return -1;
3660 }
3661 }
3662 if (pmod != NULL) {
3663 mod = (PyLongObject *)fast_mod(v, w);
3664 if (mod == NULL) {
3665 Py_XDECREF(div);
3666 return -1;
3667 }
3668 *pmod = mod;
3669 }
3670 if (pdiv != NULL) {
3671 /* We only want to set `*pdiv` when `*pmod` is
3672 set successfully. */
3673 *pdiv = div;
3674 }
3675 return 0;
3676 }
3677 if (long_divrem(v, w, &div, &mod) < 0)
3678 return -1;
3679 if ((Py_SIZE(mod) < 0 && Py_SIZE(w) > 0) ||
3680 (Py_SIZE(mod) > 0 && Py_SIZE(w) < 0)) {
3681 PyLongObject *temp;
3682 temp = (PyLongObject *) long_add(mod, w);
3683 Py_DECREF(mod);
3684 mod = temp;
3685 if (mod == NULL) {
3686 Py_DECREF(div);
3687 return -1;
3688 }
3689 temp = (PyLongObject *) long_sub(div, (PyLongObject *)_PyLong_GetOne());
3690 if (temp == NULL) {
3691 Py_DECREF(mod);
3692 Py_DECREF(div);
3693 return -1;
3694 }
3695 Py_DECREF(div);
3696 div = temp;
3697 }
3698 if (pdiv != NULL)
3699 *pdiv = div;
3700 else
3701 Py_DECREF(div);
3702
3703 if (pmod != NULL)
3704 *pmod = mod;
3705 else
3706 Py_DECREF(mod);
3707
3708 return 0;
3709 }
3710
3711 static PyObject *
long_div(PyObject * a,PyObject * b)3712 long_div(PyObject *a, PyObject *b)
3713 {
3714 PyLongObject *div;
3715
3716 CHECK_BINOP(a, b);
3717
3718 if (Py_ABS(Py_SIZE(a)) == 1 && Py_ABS(Py_SIZE(b)) == 1) {
3719 return fast_floor_div((PyLongObject*)a, (PyLongObject*)b);
3720 }
3721
3722 if (l_divmod((PyLongObject*)a, (PyLongObject*)b, &div, NULL) < 0)
3723 div = NULL;
3724 return (PyObject *)div;
3725 }
3726
3727 /* PyLong/PyLong -> float, with correctly rounded result. */
3728
3729 #define MANT_DIG_DIGITS (DBL_MANT_DIG / PyLong_SHIFT)
3730 #define MANT_DIG_BITS (DBL_MANT_DIG % PyLong_SHIFT)
3731
3732 static PyObject *
long_true_divide(PyObject * v,PyObject * w)3733 long_true_divide(PyObject *v, PyObject *w)
3734 {
3735 PyLongObject *a, *b, *x;
3736 Py_ssize_t a_size, b_size, shift, extra_bits, diff, x_size, x_bits;
3737 digit mask, low;
3738 int inexact, negate, a_is_small, b_is_small;
3739 double dx, result;
3740
3741 CHECK_BINOP(v, w);
3742 a = (PyLongObject *)v;
3743 b = (PyLongObject *)w;
3744
3745 /*
3746 Method in a nutshell:
3747
3748 0. reduce to case a, b > 0; filter out obvious underflow/overflow
3749 1. choose a suitable integer 'shift'
3750 2. use integer arithmetic to compute x = floor(2**-shift*a/b)
3751 3. adjust x for correct rounding
3752 4. convert x to a double dx with the same value
3753 5. return ldexp(dx, shift).
3754
3755 In more detail:
3756
3757 0. For any a, a/0 raises ZeroDivisionError; for nonzero b, 0/b
3758 returns either 0.0 or -0.0, depending on the sign of b. For a and
3759 b both nonzero, ignore signs of a and b, and add the sign back in
3760 at the end. Now write a_bits and b_bits for the bit lengths of a
3761 and b respectively (that is, a_bits = 1 + floor(log_2(a)); likewise
3762 for b). Then
3763
3764 2**(a_bits - b_bits - 1) < a/b < 2**(a_bits - b_bits + 1).
3765
3766 So if a_bits - b_bits > DBL_MAX_EXP then a/b > 2**DBL_MAX_EXP and
3767 so overflows. Similarly, if a_bits - b_bits < DBL_MIN_EXP -
3768 DBL_MANT_DIG - 1 then a/b underflows to 0. With these cases out of
3769 the way, we can assume that
3770
3771 DBL_MIN_EXP - DBL_MANT_DIG - 1 <= a_bits - b_bits <= DBL_MAX_EXP.
3772
3773 1. The integer 'shift' is chosen so that x has the right number of
3774 bits for a double, plus two or three extra bits that will be used
3775 in the rounding decisions. Writing a_bits and b_bits for the
3776 number of significant bits in a and b respectively, a
3777 straightforward formula for shift is:
3778
3779 shift = a_bits - b_bits - DBL_MANT_DIG - 2
3780
3781 This is fine in the usual case, but if a/b is smaller than the
3782 smallest normal float then it can lead to double rounding on an
3783 IEEE 754 platform, giving incorrectly rounded results. So we
3784 adjust the formula slightly. The actual formula used is:
3785
3786 shift = MAX(a_bits - b_bits, DBL_MIN_EXP) - DBL_MANT_DIG - 2
3787
3788 2. The quantity x is computed by first shifting a (left -shift bits
3789 if shift <= 0, right shift bits if shift > 0) and then dividing by
3790 b. For both the shift and the division, we keep track of whether
3791 the result is inexact, in a flag 'inexact'; this information is
3792 needed at the rounding stage.
3793
3794 With the choice of shift above, together with our assumption that
3795 a_bits - b_bits >= DBL_MIN_EXP - DBL_MANT_DIG - 1, it follows
3796 that x >= 1.
3797
3798 3. Now x * 2**shift <= a/b < (x+1) * 2**shift. We want to replace
3799 this with an exactly representable float of the form
3800
3801 round(x/2**extra_bits) * 2**(extra_bits+shift).
3802
3803 For float representability, we need x/2**extra_bits <
3804 2**DBL_MANT_DIG and extra_bits + shift >= DBL_MIN_EXP -
3805 DBL_MANT_DIG. This translates to the condition:
3806
3807 extra_bits >= MAX(x_bits, DBL_MIN_EXP - shift) - DBL_MANT_DIG
3808
3809 To round, we just modify the bottom digit of x in-place; this can
3810 end up giving a digit with value > PyLONG_MASK, but that's not a
3811 problem since digits can hold values up to 2*PyLONG_MASK+1.
3812
3813 With the original choices for shift above, extra_bits will always
3814 be 2 or 3. Then rounding under the round-half-to-even rule, we
3815 round up iff the most significant of the extra bits is 1, and
3816 either: (a) the computation of x in step 2 had an inexact result,
3817 or (b) at least one other of the extra bits is 1, or (c) the least
3818 significant bit of x (above those to be rounded) is 1.
3819
3820 4. Conversion to a double is straightforward; all floating-point
3821 operations involved in the conversion are exact, so there's no
3822 danger of rounding errors.
3823
3824 5. Use ldexp(x, shift) to compute x*2**shift, the final result.
3825 The result will always be exactly representable as a double, except
3826 in the case that it overflows. To avoid dependence on the exact
3827 behaviour of ldexp on overflow, we check for overflow before
3828 applying ldexp. The result of ldexp is adjusted for sign before
3829 returning.
3830 */
3831
3832 /* Reduce to case where a and b are both positive. */
3833 a_size = Py_ABS(Py_SIZE(a));
3834 b_size = Py_ABS(Py_SIZE(b));
3835 negate = (Py_SIZE(a) < 0) ^ (Py_SIZE(b) < 0);
3836 if (b_size == 0) {
3837 PyErr_SetString(PyExc_ZeroDivisionError,
3838 "division by zero");
3839 goto error;
3840 }
3841 if (a_size == 0)
3842 goto underflow_or_zero;
3843
3844 /* Fast path for a and b small (exactly representable in a double).
3845 Relies on floating-point division being correctly rounded; results
3846 may be subject to double rounding on x86 machines that operate with
3847 the x87 FPU set to 64-bit precision. */
3848 a_is_small = a_size <= MANT_DIG_DIGITS ||
3849 (a_size == MANT_DIG_DIGITS+1 &&
3850 a->ob_digit[MANT_DIG_DIGITS] >> MANT_DIG_BITS == 0);
3851 b_is_small = b_size <= MANT_DIG_DIGITS ||
3852 (b_size == MANT_DIG_DIGITS+1 &&
3853 b->ob_digit[MANT_DIG_DIGITS] >> MANT_DIG_BITS == 0);
3854 if (a_is_small && b_is_small) {
3855 double da, db;
3856 da = a->ob_digit[--a_size];
3857 while (a_size > 0)
3858 da = da * PyLong_BASE + a->ob_digit[--a_size];
3859 db = b->ob_digit[--b_size];
3860 while (b_size > 0)
3861 db = db * PyLong_BASE + b->ob_digit[--b_size];
3862 result = da / db;
3863 goto success;
3864 }
3865
3866 /* Catch obvious cases of underflow and overflow */
3867 diff = a_size - b_size;
3868 if (diff > PY_SSIZE_T_MAX/PyLong_SHIFT - 1)
3869 /* Extreme overflow */
3870 goto overflow;
3871 else if (diff < 1 - PY_SSIZE_T_MAX/PyLong_SHIFT)
3872 /* Extreme underflow */
3873 goto underflow_or_zero;
3874 /* Next line is now safe from overflowing a Py_ssize_t */
3875 diff = diff * PyLong_SHIFT + bit_length_digit(a->ob_digit[a_size - 1]) -
3876 bit_length_digit(b->ob_digit[b_size - 1]);
3877 /* Now diff = a_bits - b_bits. */
3878 if (diff > DBL_MAX_EXP)
3879 goto overflow;
3880 else if (diff < DBL_MIN_EXP - DBL_MANT_DIG - 1)
3881 goto underflow_or_zero;
3882
3883 /* Choose value for shift; see comments for step 1 above. */
3884 shift = Py_MAX(diff, DBL_MIN_EXP) - DBL_MANT_DIG - 2;
3885
3886 inexact = 0;
3887
3888 /* x = abs(a * 2**-shift) */
3889 if (shift <= 0) {
3890 Py_ssize_t i, shift_digits = -shift / PyLong_SHIFT;
3891 digit rem;
3892 /* x = a << -shift */
3893 if (a_size >= PY_SSIZE_T_MAX - 1 - shift_digits) {
3894 /* In practice, it's probably impossible to end up
3895 here. Both a and b would have to be enormous,
3896 using close to SIZE_T_MAX bytes of memory each. */
3897 PyErr_SetString(PyExc_OverflowError,
3898 "intermediate overflow during division");
3899 goto error;
3900 }
3901 x = _PyLong_New(a_size + shift_digits + 1);
3902 if (x == NULL)
3903 goto error;
3904 for (i = 0; i < shift_digits; i++)
3905 x->ob_digit[i] = 0;
3906 rem = v_lshift(x->ob_digit + shift_digits, a->ob_digit,
3907 a_size, -shift % PyLong_SHIFT);
3908 x->ob_digit[a_size + shift_digits] = rem;
3909 }
3910 else {
3911 Py_ssize_t shift_digits = shift / PyLong_SHIFT;
3912 digit rem;
3913 /* x = a >> shift */
3914 assert(a_size >= shift_digits);
3915 x = _PyLong_New(a_size - shift_digits);
3916 if (x == NULL)
3917 goto error;
3918 rem = v_rshift(x->ob_digit, a->ob_digit + shift_digits,
3919 a_size - shift_digits, shift % PyLong_SHIFT);
3920 /* set inexact if any of the bits shifted out is nonzero */
3921 if (rem)
3922 inexact = 1;
3923 while (!inexact && shift_digits > 0)
3924 if (a->ob_digit[--shift_digits])
3925 inexact = 1;
3926 }
3927 long_normalize(x);
3928 x_size = Py_SIZE(x);
3929
3930 /* x //= b. If the remainder is nonzero, set inexact. We own the only
3931 reference to x, so it's safe to modify it in-place. */
3932 if (b_size == 1) {
3933 digit rem = inplace_divrem1(x->ob_digit, x->ob_digit, x_size,
3934 b->ob_digit[0]);
3935 long_normalize(x);
3936 if (rem)
3937 inexact = 1;
3938 }
3939 else {
3940 PyLongObject *div, *rem;
3941 div = x_divrem(x, b, &rem);
3942 Py_DECREF(x);
3943 x = div;
3944 if (x == NULL)
3945 goto error;
3946 if (Py_SIZE(rem))
3947 inexact = 1;
3948 Py_DECREF(rem);
3949 }
3950 x_size = Py_ABS(Py_SIZE(x));
3951 assert(x_size > 0); /* result of division is never zero */
3952 x_bits = (x_size-1)*PyLong_SHIFT+bit_length_digit(x->ob_digit[x_size-1]);
3953
3954 /* The number of extra bits that have to be rounded away. */
3955 extra_bits = Py_MAX(x_bits, DBL_MIN_EXP - shift) - DBL_MANT_DIG;
3956 assert(extra_bits == 2 || extra_bits == 3);
3957
3958 /* Round by directly modifying the low digit of x. */
3959 mask = (digit)1 << (extra_bits - 1);
3960 low = x->ob_digit[0] | inexact;
3961 if ((low & mask) && (low & (3U*mask-1U)))
3962 low += mask;
3963 x->ob_digit[0] = low & ~(2U*mask-1U);
3964
3965 /* Convert x to a double dx; the conversion is exact. */
3966 dx = x->ob_digit[--x_size];
3967 while (x_size > 0)
3968 dx = dx * PyLong_BASE + x->ob_digit[--x_size];
3969 Py_DECREF(x);
3970
3971 /* Check whether ldexp result will overflow a double. */
3972 if (shift + x_bits >= DBL_MAX_EXP &&
3973 (shift + x_bits > DBL_MAX_EXP || dx == ldexp(1.0, (int)x_bits)))
3974 goto overflow;
3975 result = ldexp(dx, (int)shift);
3976
3977 success:
3978 return PyFloat_FromDouble(negate ? -result : result);
3979
3980 underflow_or_zero:
3981 return PyFloat_FromDouble(negate ? -0.0 : 0.0);
3982
3983 overflow:
3984 PyErr_SetString(PyExc_OverflowError,
3985 "integer division result too large for a float");
3986 error:
3987 return NULL;
3988 }
3989
3990 static PyObject *
long_mod(PyObject * a,PyObject * b)3991 long_mod(PyObject *a, PyObject *b)
3992 {
3993 PyLongObject *mod;
3994
3995 CHECK_BINOP(a, b);
3996
3997 if (Py_ABS(Py_SIZE(a)) == 1 && Py_ABS(Py_SIZE(b)) == 1) {
3998 return fast_mod((PyLongObject*)a, (PyLongObject*)b);
3999 }
4000
4001 if (l_divmod((PyLongObject*)a, (PyLongObject*)b, NULL, &mod) < 0)
4002 mod = NULL;
4003 return (PyObject *)mod;
4004 }
4005
4006 static PyObject *
long_divmod(PyObject * a,PyObject * b)4007 long_divmod(PyObject *a, PyObject *b)
4008 {
4009 PyLongObject *div, *mod;
4010 PyObject *z;
4011
4012 CHECK_BINOP(a, b);
4013
4014 if (l_divmod((PyLongObject*)a, (PyLongObject*)b, &div, &mod) < 0) {
4015 return NULL;
4016 }
4017 z = PyTuple_New(2);
4018 if (z != NULL) {
4019 PyTuple_SET_ITEM(z, 0, (PyObject *) div);
4020 PyTuple_SET_ITEM(z, 1, (PyObject *) mod);
4021 }
4022 else {
4023 Py_DECREF(div);
4024 Py_DECREF(mod);
4025 }
4026 return z;
4027 }
4028
4029
4030 /* Compute an inverse to a modulo n, or raise ValueError if a is not
4031 invertible modulo n. Assumes n is positive. The inverse returned
4032 is whatever falls out of the extended Euclidean algorithm: it may
4033 be either positive or negative, but will be smaller than n in
4034 absolute value.
4035
4036 Pure Python equivalent for long_invmod:
4037
4038 def invmod(a, n):
4039 b, c = 1, 0
4040 while n:
4041 q, r = divmod(a, n)
4042 a, b, c, n = n, c, b - q*c, r
4043
4044 # at this point a is the gcd of the original inputs
4045 if a == 1:
4046 return b
4047 raise ValueError("Not invertible")
4048 */
4049
4050 static PyLongObject *
long_invmod(PyLongObject * a,PyLongObject * n)4051 long_invmod(PyLongObject *a, PyLongObject *n)
4052 {
4053 PyLongObject *b, *c;
4054
4055 /* Should only ever be called for positive n */
4056 assert(Py_SIZE(n) > 0);
4057
4058 b = (PyLongObject *)PyLong_FromLong(1L);
4059 if (b == NULL) {
4060 return NULL;
4061 }
4062 c = (PyLongObject *)PyLong_FromLong(0L);
4063 if (c == NULL) {
4064 Py_DECREF(b);
4065 return NULL;
4066 }
4067 Py_INCREF(a);
4068 Py_INCREF(n);
4069
4070 /* references now owned: a, b, c, n */
4071 while (Py_SIZE(n) != 0) {
4072 PyLongObject *q, *r, *s, *t;
4073
4074 if (l_divmod(a, n, &q, &r) == -1) {
4075 goto Error;
4076 }
4077 Py_DECREF(a);
4078 a = n;
4079 n = r;
4080 t = (PyLongObject *)long_mul(q, c);
4081 Py_DECREF(q);
4082 if (t == NULL) {
4083 goto Error;
4084 }
4085 s = (PyLongObject *)long_sub(b, t);
4086 Py_DECREF(t);
4087 if (s == NULL) {
4088 goto Error;
4089 }
4090 Py_DECREF(b);
4091 b = c;
4092 c = s;
4093 }
4094 /* references now owned: a, b, c, n */
4095
4096 Py_DECREF(c);
4097 Py_DECREF(n);
4098 if (long_compare(a, (PyLongObject *)_PyLong_GetOne())) {
4099 /* a != 1; we don't have an inverse. */
4100 Py_DECREF(a);
4101 Py_DECREF(b);
4102 PyErr_SetString(PyExc_ValueError,
4103 "base is not invertible for the given modulus");
4104 return NULL;
4105 }
4106 else {
4107 /* a == 1; b gives an inverse modulo n */
4108 Py_DECREF(a);
4109 return b;
4110 }
4111
4112 Error:
4113 Py_DECREF(a);
4114 Py_DECREF(b);
4115 Py_DECREF(c);
4116 Py_DECREF(n);
4117 return NULL;
4118 }
4119
4120
4121 /* pow(v, w, x) */
4122 static PyObject *
long_pow(PyObject * v,PyObject * w,PyObject * x)4123 long_pow(PyObject *v, PyObject *w, PyObject *x)
4124 {
4125 PyLongObject *a, *b, *c; /* a,b,c = v,w,x */
4126 int negativeOutput = 0; /* if x<0 return negative output */
4127
4128 PyLongObject *z = NULL; /* accumulated result */
4129 Py_ssize_t i, j, k; /* counters */
4130 PyLongObject *temp = NULL;
4131
4132 /* 5-ary values. If the exponent is large enough, table is
4133 * precomputed so that table[i] == a**i % c for i in range(32).
4134 */
4135 PyLongObject *table[32] = {0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
4136 0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0};
4137
4138 /* a, b, c = v, w, x */
4139 CHECK_BINOP(v, w);
4140 a = (PyLongObject*)v; Py_INCREF(a);
4141 b = (PyLongObject*)w; Py_INCREF(b);
4142 if (PyLong_Check(x)) {
4143 c = (PyLongObject *)x;
4144 Py_INCREF(x);
4145 }
4146 else if (x == Py_None)
4147 c = NULL;
4148 else {
4149 Py_DECREF(a);
4150 Py_DECREF(b);
4151 Py_RETURN_NOTIMPLEMENTED;
4152 }
4153
4154 if (Py_SIZE(b) < 0 && c == NULL) {
4155 /* if exponent is negative and there's no modulus:
4156 return a float. This works because we know
4157 that this calls float_pow() which converts its
4158 arguments to double. */
4159 Py_DECREF(a);
4160 Py_DECREF(b);
4161 return PyFloat_Type.tp_as_number->nb_power(v, w, x);
4162 }
4163
4164 if (c) {
4165 /* if modulus == 0:
4166 raise ValueError() */
4167 if (Py_SIZE(c) == 0) {
4168 PyErr_SetString(PyExc_ValueError,
4169 "pow() 3rd argument cannot be 0");
4170 goto Error;
4171 }
4172
4173 /* if modulus < 0:
4174 negativeOutput = True
4175 modulus = -modulus */
4176 if (Py_SIZE(c) < 0) {
4177 negativeOutput = 1;
4178 temp = (PyLongObject *)_PyLong_Copy(c);
4179 if (temp == NULL)
4180 goto Error;
4181 Py_DECREF(c);
4182 c = temp;
4183 temp = NULL;
4184 _PyLong_Negate(&c);
4185 if (c == NULL)
4186 goto Error;
4187 }
4188
4189 /* if modulus == 1:
4190 return 0 */
4191 if ((Py_SIZE(c) == 1) && (c->ob_digit[0] == 1)) {
4192 z = (PyLongObject *)PyLong_FromLong(0L);
4193 goto Done;
4194 }
4195
4196 /* if exponent is negative, negate the exponent and
4197 replace the base with a modular inverse */
4198 if (Py_SIZE(b) < 0) {
4199 temp = (PyLongObject *)_PyLong_Copy(b);
4200 if (temp == NULL)
4201 goto Error;
4202 Py_DECREF(b);
4203 b = temp;
4204 temp = NULL;
4205 _PyLong_Negate(&b);
4206 if (b == NULL)
4207 goto Error;
4208
4209 temp = long_invmod(a, c);
4210 if (temp == NULL)
4211 goto Error;
4212 Py_DECREF(a);
4213 a = temp;
4214 temp = NULL;
4215 }
4216
4217 /* Reduce base by modulus in some cases:
4218 1. If base < 0. Forcing the base non-negative makes things easier.
4219 2. If base is obviously larger than the modulus. The "small
4220 exponent" case later can multiply directly by base repeatedly,
4221 while the "large exponent" case multiplies directly by base 31
4222 times. It can be unboundedly faster to multiply by
4223 base % modulus instead.
4224 We could _always_ do this reduction, but l_divmod() isn't cheap,
4225 so we only do it when it buys something. */
4226 if (Py_SIZE(a) < 0 || Py_SIZE(a) > Py_SIZE(c)) {
4227 if (l_divmod(a, c, NULL, &temp) < 0)
4228 goto Error;
4229 Py_DECREF(a);
4230 a = temp;
4231 temp = NULL;
4232 }
4233 }
4234
4235 /* At this point a, b, and c are guaranteed non-negative UNLESS
4236 c is NULL, in which case a may be negative. */
4237
4238 z = (PyLongObject *)PyLong_FromLong(1L);
4239 if (z == NULL)
4240 goto Error;
4241
4242 /* Perform a modular reduction, X = X % c, but leave X alone if c
4243 * is NULL.
4244 */
4245 #define REDUCE(X) \
4246 do { \
4247 if (c != NULL) { \
4248 if (l_divmod(X, c, NULL, &temp) < 0) \
4249 goto Error; \
4250 Py_XDECREF(X); \
4251 X = temp; \
4252 temp = NULL; \
4253 } \
4254 } while(0)
4255
4256 /* Multiply two values, then reduce the result:
4257 result = X*Y % c. If c is NULL, skip the mod. */
4258 #define MULT(X, Y, result) \
4259 do { \
4260 temp = (PyLongObject *)long_mul(X, Y); \
4261 if (temp == NULL) \
4262 goto Error; \
4263 Py_XDECREF(result); \
4264 result = temp; \
4265 temp = NULL; \
4266 REDUCE(result); \
4267 } while(0)
4268
4269 if (Py_SIZE(b) <= FIVEARY_CUTOFF) {
4270 /* Left-to-right binary exponentiation (HAC Algorithm 14.79) */
4271 /* http://www.cacr.math.uwaterloo.ca/hac/about/chap14.pdf */
4272 for (i = Py_SIZE(b) - 1; i >= 0; --i) {
4273 digit bi = b->ob_digit[i];
4274
4275 for (j = (digit)1 << (PyLong_SHIFT-1); j != 0; j >>= 1) {
4276 MULT(z, z, z);
4277 if (bi & j)
4278 MULT(z, a, z);
4279 }
4280 }
4281 }
4282 else {
4283 /* Left-to-right 5-ary exponentiation (HAC Algorithm 14.82) */
4284 Py_INCREF(z); /* still holds 1L */
4285 table[0] = z;
4286 for (i = 1; i < 32; ++i)
4287 MULT(table[i-1], a, table[i]);
4288
4289 for (i = Py_SIZE(b) - 1; i >= 0; --i) {
4290 const digit bi = b->ob_digit[i];
4291
4292 for (j = PyLong_SHIFT - 5; j >= 0; j -= 5) {
4293 const int index = (bi >> j) & 0x1f;
4294 for (k = 0; k < 5; ++k)
4295 MULT(z, z, z);
4296 if (index)
4297 MULT(z, table[index], z);
4298 }
4299 }
4300 }
4301
4302 if (negativeOutput && (Py_SIZE(z) != 0)) {
4303 temp = (PyLongObject *)long_sub(z, c);
4304 if (temp == NULL)
4305 goto Error;
4306 Py_DECREF(z);
4307 z = temp;
4308 temp = NULL;
4309 }
4310 goto Done;
4311
4312 Error:
4313 Py_CLEAR(z);
4314 /* fall through */
4315 Done:
4316 if (Py_SIZE(b) > FIVEARY_CUTOFF) {
4317 for (i = 0; i < 32; ++i)
4318 Py_XDECREF(table[i]);
4319 }
4320 Py_DECREF(a);
4321 Py_DECREF(b);
4322 Py_XDECREF(c);
4323 Py_XDECREF(temp);
4324 return (PyObject *)z;
4325 }
4326
4327 static PyObject *
long_invert(PyLongObject * v)4328 long_invert(PyLongObject *v)
4329 {
4330 /* Implement ~x as -(x+1) */
4331 PyLongObject *x;
4332 if (Py_ABS(Py_SIZE(v)) <=1)
4333 return PyLong_FromLong(-(MEDIUM_VALUE(v)+1));
4334 x = (PyLongObject *) long_add(v, (PyLongObject *)_PyLong_GetOne());
4335 if (x == NULL)
4336 return NULL;
4337 _PyLong_Negate(&x);
4338 /* No need for maybe_small_long here, since any small
4339 longs will have been caught in the Py_SIZE <= 1 fast path. */
4340 return (PyObject *)x;
4341 }
4342
4343 static PyObject *
long_neg(PyLongObject * v)4344 long_neg(PyLongObject *v)
4345 {
4346 PyLongObject *z;
4347 if (Py_ABS(Py_SIZE(v)) <= 1)
4348 return PyLong_FromLong(-MEDIUM_VALUE(v));
4349 z = (PyLongObject *)_PyLong_Copy(v);
4350 if (z != NULL)
4351 Py_SET_SIZE(z, -(Py_SIZE(v)));
4352 return (PyObject *)z;
4353 }
4354
4355 static PyObject *
long_abs(PyLongObject * v)4356 long_abs(PyLongObject *v)
4357 {
4358 if (Py_SIZE(v) < 0)
4359 return long_neg(v);
4360 else
4361 return long_long((PyObject *)v);
4362 }
4363
4364 static int
long_bool(PyLongObject * v)4365 long_bool(PyLongObject *v)
4366 {
4367 return Py_SIZE(v) != 0;
4368 }
4369
4370 /* wordshift, remshift = divmod(shiftby, PyLong_SHIFT) */
4371 static int
divmod_shift(PyObject * shiftby,Py_ssize_t * wordshift,digit * remshift)4372 divmod_shift(PyObject *shiftby, Py_ssize_t *wordshift, digit *remshift)
4373 {
4374 assert(PyLong_Check(shiftby));
4375 assert(Py_SIZE(shiftby) >= 0);
4376 Py_ssize_t lshiftby = PyLong_AsSsize_t((PyObject *)shiftby);
4377 if (lshiftby >= 0) {
4378 *wordshift = lshiftby / PyLong_SHIFT;
4379 *remshift = lshiftby % PyLong_SHIFT;
4380 return 0;
4381 }
4382 /* PyLong_Check(shiftby) is true and Py_SIZE(shiftby) >= 0, so it must
4383 be that PyLong_AsSsize_t raised an OverflowError. */
4384 assert(PyErr_ExceptionMatches(PyExc_OverflowError));
4385 PyErr_Clear();
4386 PyLongObject *wordshift_obj = divrem1((PyLongObject *)shiftby, PyLong_SHIFT, remshift);
4387 if (wordshift_obj == NULL) {
4388 return -1;
4389 }
4390 *wordshift = PyLong_AsSsize_t((PyObject *)wordshift_obj);
4391 Py_DECREF(wordshift_obj);
4392 if (*wordshift >= 0 && *wordshift < PY_SSIZE_T_MAX / (Py_ssize_t)sizeof(digit)) {
4393 return 0;
4394 }
4395 PyErr_Clear();
4396 /* Clip the value. With such large wordshift the right shift
4397 returns 0 and the left shift raises an error in _PyLong_New(). */
4398 *wordshift = PY_SSIZE_T_MAX / sizeof(digit);
4399 *remshift = 0;
4400 return 0;
4401 }
4402
4403 static PyObject *
long_rshift1(PyLongObject * a,Py_ssize_t wordshift,digit remshift)4404 long_rshift1(PyLongObject *a, Py_ssize_t wordshift, digit remshift)
4405 {
4406 PyLongObject *z = NULL;
4407 Py_ssize_t newsize, hishift, i, j;
4408 digit lomask, himask;
4409
4410 if (Py_SIZE(a) < 0) {
4411 /* Right shifting negative numbers is harder */
4412 PyLongObject *a1, *a2;
4413 a1 = (PyLongObject *) long_invert(a);
4414 if (a1 == NULL)
4415 return NULL;
4416 a2 = (PyLongObject *) long_rshift1(a1, wordshift, remshift);
4417 Py_DECREF(a1);
4418 if (a2 == NULL)
4419 return NULL;
4420 z = (PyLongObject *) long_invert(a2);
4421 Py_DECREF(a2);
4422 }
4423 else {
4424 newsize = Py_SIZE(a) - wordshift;
4425 if (newsize <= 0)
4426 return PyLong_FromLong(0);
4427 hishift = PyLong_SHIFT - remshift;
4428 lomask = ((digit)1 << hishift) - 1;
4429 himask = PyLong_MASK ^ lomask;
4430 z = _PyLong_New(newsize);
4431 if (z == NULL)
4432 return NULL;
4433 for (i = 0, j = wordshift; i < newsize; i++, j++) {
4434 z->ob_digit[i] = (a->ob_digit[j] >> remshift) & lomask;
4435 if (i+1 < newsize)
4436 z->ob_digit[i] |= (a->ob_digit[j+1] << hishift) & himask;
4437 }
4438 z = maybe_small_long(long_normalize(z));
4439 }
4440 return (PyObject *)z;
4441 }
4442
4443 static PyObject *
long_rshift(PyObject * a,PyObject * b)4444 long_rshift(PyObject *a, PyObject *b)
4445 {
4446 Py_ssize_t wordshift;
4447 digit remshift;
4448
4449 CHECK_BINOP(a, b);
4450
4451 if (Py_SIZE(b) < 0) {
4452 PyErr_SetString(PyExc_ValueError, "negative shift count");
4453 return NULL;
4454 }
4455 if (Py_SIZE(a) == 0) {
4456 return PyLong_FromLong(0);
4457 }
4458 if (divmod_shift(b, &wordshift, &remshift) < 0)
4459 return NULL;
4460 return long_rshift1((PyLongObject *)a, wordshift, remshift);
4461 }
4462
4463 /* Return a >> shiftby. */
4464 PyObject *
_PyLong_Rshift(PyObject * a,size_t shiftby)4465 _PyLong_Rshift(PyObject *a, size_t shiftby)
4466 {
4467 Py_ssize_t wordshift;
4468 digit remshift;
4469
4470 assert(PyLong_Check(a));
4471 if (Py_SIZE(a) == 0) {
4472 return PyLong_FromLong(0);
4473 }
4474 wordshift = shiftby / PyLong_SHIFT;
4475 remshift = shiftby % PyLong_SHIFT;
4476 return long_rshift1((PyLongObject *)a, wordshift, remshift);
4477 }
4478
4479 static PyObject *
long_lshift1(PyLongObject * a,Py_ssize_t wordshift,digit remshift)4480 long_lshift1(PyLongObject *a, Py_ssize_t wordshift, digit remshift)
4481 {
4482 /* This version due to Tim Peters */
4483 PyLongObject *z = NULL;
4484 Py_ssize_t oldsize, newsize, i, j;
4485 twodigits accum;
4486
4487 oldsize = Py_ABS(Py_SIZE(a));
4488 newsize = oldsize + wordshift;
4489 if (remshift)
4490 ++newsize;
4491 z = _PyLong_New(newsize);
4492 if (z == NULL)
4493 return NULL;
4494 if (Py_SIZE(a) < 0) {
4495 assert(Py_REFCNT(z) == 1);
4496 Py_SET_SIZE(z, -Py_SIZE(z));
4497 }
4498 for (i = 0; i < wordshift; i++)
4499 z->ob_digit[i] = 0;
4500 accum = 0;
4501 for (i = wordshift, j = 0; j < oldsize; i++, j++) {
4502 accum |= (twodigits)a->ob_digit[j] << remshift;
4503 z->ob_digit[i] = (digit)(accum & PyLong_MASK);
4504 accum >>= PyLong_SHIFT;
4505 }
4506 if (remshift)
4507 z->ob_digit[newsize-1] = (digit)accum;
4508 else
4509 assert(!accum);
4510 z = long_normalize(z);
4511 return (PyObject *) maybe_small_long(z);
4512 }
4513
4514 static PyObject *
long_lshift(PyObject * a,PyObject * b)4515 long_lshift(PyObject *a, PyObject *b)
4516 {
4517 Py_ssize_t wordshift;
4518 digit remshift;
4519
4520 CHECK_BINOP(a, b);
4521
4522 if (Py_SIZE(b) < 0) {
4523 PyErr_SetString(PyExc_ValueError, "negative shift count");
4524 return NULL;
4525 }
4526 if (Py_SIZE(a) == 0) {
4527 return PyLong_FromLong(0);
4528 }
4529 if (divmod_shift(b, &wordshift, &remshift) < 0)
4530 return NULL;
4531 return long_lshift1((PyLongObject *)a, wordshift, remshift);
4532 }
4533
4534 /* Return a << shiftby. */
4535 PyObject *
_PyLong_Lshift(PyObject * a,size_t shiftby)4536 _PyLong_Lshift(PyObject *a, size_t shiftby)
4537 {
4538 Py_ssize_t wordshift;
4539 digit remshift;
4540
4541 assert(PyLong_Check(a));
4542 if (Py_SIZE(a) == 0) {
4543 return PyLong_FromLong(0);
4544 }
4545 wordshift = shiftby / PyLong_SHIFT;
4546 remshift = shiftby % PyLong_SHIFT;
4547 return long_lshift1((PyLongObject *)a, wordshift, remshift);
4548 }
4549
4550 /* Compute two's complement of digit vector a[0:m], writing result to
4551 z[0:m]. The digit vector a need not be normalized, but should not
4552 be entirely zero. a and z may point to the same digit vector. */
4553
4554 static void
v_complement(digit * z,digit * a,Py_ssize_t m)4555 v_complement(digit *z, digit *a, Py_ssize_t m)
4556 {
4557 Py_ssize_t i;
4558 digit carry = 1;
4559 for (i = 0; i < m; ++i) {
4560 carry += a[i] ^ PyLong_MASK;
4561 z[i] = carry & PyLong_MASK;
4562 carry >>= PyLong_SHIFT;
4563 }
4564 assert(carry == 0);
4565 }
4566
4567 /* Bitwise and/xor/or operations */
4568
4569 static PyObject *
long_bitwise(PyLongObject * a,char op,PyLongObject * b)4570 long_bitwise(PyLongObject *a,
4571 char op, /* '&', '|', '^' */
4572 PyLongObject *b)
4573 {
4574 int nega, negb, negz;
4575 Py_ssize_t size_a, size_b, size_z, i;
4576 PyLongObject *z;
4577
4578 /* Bitwise operations for negative numbers operate as though
4579 on a two's complement representation. So convert arguments
4580 from sign-magnitude to two's complement, and convert the
4581 result back to sign-magnitude at the end. */
4582
4583 /* If a is negative, replace it by its two's complement. */
4584 size_a = Py_ABS(Py_SIZE(a));
4585 nega = Py_SIZE(a) < 0;
4586 if (nega) {
4587 z = _PyLong_New(size_a);
4588 if (z == NULL)
4589 return NULL;
4590 v_complement(z->ob_digit, a->ob_digit, size_a);
4591 a = z;
4592 }
4593 else
4594 /* Keep reference count consistent. */
4595 Py_INCREF(a);
4596
4597 /* Same for b. */
4598 size_b = Py_ABS(Py_SIZE(b));
4599 negb = Py_SIZE(b) < 0;
4600 if (negb) {
4601 z = _PyLong_New(size_b);
4602 if (z == NULL) {
4603 Py_DECREF(a);
4604 return NULL;
4605 }
4606 v_complement(z->ob_digit, b->ob_digit, size_b);
4607 b = z;
4608 }
4609 else
4610 Py_INCREF(b);
4611
4612 /* Swap a and b if necessary to ensure size_a >= size_b. */
4613 if (size_a < size_b) {
4614 z = a; a = b; b = z;
4615 size_z = size_a; size_a = size_b; size_b = size_z;
4616 negz = nega; nega = negb; negb = negz;
4617 }
4618
4619 /* JRH: The original logic here was to allocate the result value (z)
4620 as the longer of the two operands. However, there are some cases
4621 where the result is guaranteed to be shorter than that: AND of two
4622 positives, OR of two negatives: use the shorter number. AND with
4623 mixed signs: use the positive number. OR with mixed signs: use the
4624 negative number.
4625 */
4626 switch (op) {
4627 case '^':
4628 negz = nega ^ negb;
4629 size_z = size_a;
4630 break;
4631 case '&':
4632 negz = nega & negb;
4633 size_z = negb ? size_a : size_b;
4634 break;
4635 case '|':
4636 negz = nega | negb;
4637 size_z = negb ? size_b : size_a;
4638 break;
4639 default:
4640 Py_UNREACHABLE();
4641 }
4642
4643 /* We allow an extra digit if z is negative, to make sure that
4644 the final two's complement of z doesn't overflow. */
4645 z = _PyLong_New(size_z + negz);
4646 if (z == NULL) {
4647 Py_DECREF(a);
4648 Py_DECREF(b);
4649 return NULL;
4650 }
4651
4652 /* Compute digits for overlap of a and b. */
4653 switch(op) {
4654 case '&':
4655 for (i = 0; i < size_b; ++i)
4656 z->ob_digit[i] = a->ob_digit[i] & b->ob_digit[i];
4657 break;
4658 case '|':
4659 for (i = 0; i < size_b; ++i)
4660 z->ob_digit[i] = a->ob_digit[i] | b->ob_digit[i];
4661 break;
4662 case '^':
4663 for (i = 0; i < size_b; ++i)
4664 z->ob_digit[i] = a->ob_digit[i] ^ b->ob_digit[i];
4665 break;
4666 default:
4667 Py_UNREACHABLE();
4668 }
4669
4670 /* Copy any remaining digits of a, inverting if necessary. */
4671 if (op == '^' && negb)
4672 for (; i < size_z; ++i)
4673 z->ob_digit[i] = a->ob_digit[i] ^ PyLong_MASK;
4674 else if (i < size_z)
4675 memcpy(&z->ob_digit[i], &a->ob_digit[i],
4676 (size_z-i)*sizeof(digit));
4677
4678 /* Complement result if negative. */
4679 if (negz) {
4680 Py_SET_SIZE(z, -(Py_SIZE(z)));
4681 z->ob_digit[size_z] = PyLong_MASK;
4682 v_complement(z->ob_digit, z->ob_digit, size_z+1);
4683 }
4684
4685 Py_DECREF(a);
4686 Py_DECREF(b);
4687 return (PyObject *)maybe_small_long(long_normalize(z));
4688 }
4689
4690 static PyObject *
long_and(PyObject * a,PyObject * b)4691 long_and(PyObject *a, PyObject *b)
4692 {
4693 PyObject *c;
4694 CHECK_BINOP(a, b);
4695 c = long_bitwise((PyLongObject*)a, '&', (PyLongObject*)b);
4696 return c;
4697 }
4698
4699 static PyObject *
long_xor(PyObject * a,PyObject * b)4700 long_xor(PyObject *a, PyObject *b)
4701 {
4702 PyObject *c;
4703 CHECK_BINOP(a, b);
4704 c = long_bitwise((PyLongObject*)a, '^', (PyLongObject*)b);
4705 return c;
4706 }
4707
4708 static PyObject *
long_or(PyObject * a,PyObject * b)4709 long_or(PyObject *a, PyObject *b)
4710 {
4711 PyObject *c;
4712 CHECK_BINOP(a, b);
4713 c = long_bitwise((PyLongObject*)a, '|', (PyLongObject*)b);
4714 return c;
4715 }
4716
4717 static PyObject *
long_long(PyObject * v)4718 long_long(PyObject *v)
4719 {
4720 if (PyLong_CheckExact(v))
4721 Py_INCREF(v);
4722 else
4723 v = _PyLong_Copy((PyLongObject *)v);
4724 return v;
4725 }
4726
4727 PyObject *
_PyLong_GCD(PyObject * aarg,PyObject * barg)4728 _PyLong_GCD(PyObject *aarg, PyObject *barg)
4729 {
4730 PyLongObject *a, *b, *c = NULL, *d = NULL, *r;
4731 stwodigits x, y, q, s, t, c_carry, d_carry;
4732 stwodigits A, B, C, D, T;
4733 int nbits, k;
4734 Py_ssize_t size_a, size_b, alloc_a, alloc_b;
4735 digit *a_digit, *b_digit, *c_digit, *d_digit, *a_end, *b_end;
4736
4737 a = (PyLongObject *)aarg;
4738 b = (PyLongObject *)barg;
4739 size_a = Py_SIZE(a);
4740 size_b = Py_SIZE(b);
4741 if (-2 <= size_a && size_a <= 2 && -2 <= size_b && size_b <= 2) {
4742 Py_INCREF(a);
4743 Py_INCREF(b);
4744 goto simple;
4745 }
4746
4747 /* Initial reduction: make sure that 0 <= b <= a. */
4748 a = (PyLongObject *)long_abs(a);
4749 if (a == NULL)
4750 return NULL;
4751 b = (PyLongObject *)long_abs(b);
4752 if (b == NULL) {
4753 Py_DECREF(a);
4754 return NULL;
4755 }
4756 if (long_compare(a, b) < 0) {
4757 r = a;
4758 a = b;
4759 b = r;
4760 }
4761 /* We now own references to a and b */
4762
4763 alloc_a = Py_SIZE(a);
4764 alloc_b = Py_SIZE(b);
4765 /* reduce until a fits into 2 digits */
4766 while ((size_a = Py_SIZE(a)) > 2) {
4767 nbits = bit_length_digit(a->ob_digit[size_a-1]);
4768 /* extract top 2*PyLong_SHIFT bits of a into x, along with
4769 corresponding bits of b into y */
4770 size_b = Py_SIZE(b);
4771 assert(size_b <= size_a);
4772 if (size_b == 0) {
4773 if (size_a < alloc_a) {
4774 r = (PyLongObject *)_PyLong_Copy(a);
4775 Py_DECREF(a);
4776 }
4777 else
4778 r = a;
4779 Py_DECREF(b);
4780 Py_XDECREF(c);
4781 Py_XDECREF(d);
4782 return (PyObject *)r;
4783 }
4784 x = (((twodigits)a->ob_digit[size_a-1] << (2*PyLong_SHIFT-nbits)) |
4785 ((twodigits)a->ob_digit[size_a-2] << (PyLong_SHIFT-nbits)) |
4786 (a->ob_digit[size_a-3] >> nbits));
4787
4788 y = ((size_b >= size_a - 2 ? b->ob_digit[size_a-3] >> nbits : 0) |
4789 (size_b >= size_a - 1 ? (twodigits)b->ob_digit[size_a-2] << (PyLong_SHIFT-nbits) : 0) |
4790 (size_b >= size_a ? (twodigits)b->ob_digit[size_a-1] << (2*PyLong_SHIFT-nbits) : 0));
4791
4792 /* inner loop of Lehmer's algorithm; A, B, C, D never grow
4793 larger than PyLong_MASK during the algorithm. */
4794 A = 1; B = 0; C = 0; D = 1;
4795 for (k=0;; k++) {
4796 if (y-C == 0)
4797 break;
4798 q = (x+(A-1))/(y-C);
4799 s = B+q*D;
4800 t = x-q*y;
4801 if (s > t)
4802 break;
4803 x = y; y = t;
4804 t = A+q*C; A = D; B = C; C = s; D = t;
4805 }
4806
4807 if (k == 0) {
4808 /* no progress; do a Euclidean step */
4809 if (l_divmod(a, b, NULL, &r) < 0)
4810 goto error;
4811 Py_DECREF(a);
4812 a = b;
4813 b = r;
4814 alloc_a = alloc_b;
4815 alloc_b = Py_SIZE(b);
4816 continue;
4817 }
4818
4819 /*
4820 a, b = A*b-B*a, D*a-C*b if k is odd
4821 a, b = A*a-B*b, D*b-C*a if k is even
4822 */
4823 if (k&1) {
4824 T = -A; A = -B; B = T;
4825 T = -C; C = -D; D = T;
4826 }
4827 if (c != NULL) {
4828 Py_SET_SIZE(c, size_a);
4829 }
4830 else if (Py_REFCNT(a) == 1) {
4831 Py_INCREF(a);
4832 c = a;
4833 }
4834 else {
4835 alloc_a = size_a;
4836 c = _PyLong_New(size_a);
4837 if (c == NULL)
4838 goto error;
4839 }
4840
4841 if (d != NULL) {
4842 Py_SET_SIZE(d, size_a);
4843 }
4844 else if (Py_REFCNT(b) == 1 && size_a <= alloc_b) {
4845 Py_INCREF(b);
4846 d = b;
4847 Py_SET_SIZE(d, size_a);
4848 }
4849 else {
4850 alloc_b = size_a;
4851 d = _PyLong_New(size_a);
4852 if (d == NULL)
4853 goto error;
4854 }
4855 a_end = a->ob_digit + size_a;
4856 b_end = b->ob_digit + size_b;
4857
4858 /* compute new a and new b in parallel */
4859 a_digit = a->ob_digit;
4860 b_digit = b->ob_digit;
4861 c_digit = c->ob_digit;
4862 d_digit = d->ob_digit;
4863 c_carry = 0;
4864 d_carry = 0;
4865 while (b_digit < b_end) {
4866 c_carry += (A * *a_digit) - (B * *b_digit);
4867 d_carry += (D * *b_digit++) - (C * *a_digit++);
4868 *c_digit++ = (digit)(c_carry & PyLong_MASK);
4869 *d_digit++ = (digit)(d_carry & PyLong_MASK);
4870 c_carry >>= PyLong_SHIFT;
4871 d_carry >>= PyLong_SHIFT;
4872 }
4873 while (a_digit < a_end) {
4874 c_carry += A * *a_digit;
4875 d_carry -= C * *a_digit++;
4876 *c_digit++ = (digit)(c_carry & PyLong_MASK);
4877 *d_digit++ = (digit)(d_carry & PyLong_MASK);
4878 c_carry >>= PyLong_SHIFT;
4879 d_carry >>= PyLong_SHIFT;
4880 }
4881 assert(c_carry == 0);
4882 assert(d_carry == 0);
4883
4884 Py_INCREF(c);
4885 Py_INCREF(d);
4886 Py_DECREF(a);
4887 Py_DECREF(b);
4888 a = long_normalize(c);
4889 b = long_normalize(d);
4890 }
4891 Py_XDECREF(c);
4892 Py_XDECREF(d);
4893
4894 simple:
4895 assert(Py_REFCNT(a) > 0);
4896 assert(Py_REFCNT(b) > 0);
4897 /* Issue #24999: use two shifts instead of ">> 2*PyLong_SHIFT" to avoid
4898 undefined behaviour when LONG_MAX type is smaller than 60 bits */
4899 #if LONG_MAX >> PyLong_SHIFT >> PyLong_SHIFT
4900 /* a fits into a long, so b must too */
4901 x = PyLong_AsLong((PyObject *)a);
4902 y = PyLong_AsLong((PyObject *)b);
4903 #elif LLONG_MAX >> PyLong_SHIFT >> PyLong_SHIFT
4904 x = PyLong_AsLongLong((PyObject *)a);
4905 y = PyLong_AsLongLong((PyObject *)b);
4906 #else
4907 # error "_PyLong_GCD"
4908 #endif
4909 x = Py_ABS(x);
4910 y = Py_ABS(y);
4911 Py_DECREF(a);
4912 Py_DECREF(b);
4913
4914 /* usual Euclidean algorithm for longs */
4915 while (y != 0) {
4916 t = y;
4917 y = x % y;
4918 x = t;
4919 }
4920 #if LONG_MAX >> PyLong_SHIFT >> PyLong_SHIFT
4921 return PyLong_FromLong(x);
4922 #elif LLONG_MAX >> PyLong_SHIFT >> PyLong_SHIFT
4923 return PyLong_FromLongLong(x);
4924 #else
4925 # error "_PyLong_GCD"
4926 #endif
4927
4928 error:
4929 Py_DECREF(a);
4930 Py_DECREF(b);
4931 Py_XDECREF(c);
4932 Py_XDECREF(d);
4933 return NULL;
4934 }
4935
4936 static PyObject *
long_float(PyObject * v)4937 long_float(PyObject *v)
4938 {
4939 double result;
4940 result = PyLong_AsDouble(v);
4941 if (result == -1.0 && PyErr_Occurred())
4942 return NULL;
4943 return PyFloat_FromDouble(result);
4944 }
4945
4946 static PyObject *
4947 long_subtype_new(PyTypeObject *type, PyObject *x, PyObject *obase);
4948
4949 /*[clinic input]
4950 @classmethod
4951 int.__new__ as long_new
4952 x: object(c_default="NULL") = 0
4953 /
4954 base as obase: object(c_default="NULL") = 10
4955 [clinic start generated code]*/
4956
4957 static PyObject *
long_new_impl(PyTypeObject * type,PyObject * x,PyObject * obase)4958 long_new_impl(PyTypeObject *type, PyObject *x, PyObject *obase)
4959 /*[clinic end generated code: output=e47cfe777ab0f24c input=81c98f418af9eb6f]*/
4960 {
4961 Py_ssize_t base;
4962
4963 if (type != &PyLong_Type)
4964 return long_subtype_new(type, x, obase); /* Wimp out */
4965 if (x == NULL) {
4966 if (obase != NULL) {
4967 PyErr_SetString(PyExc_TypeError,
4968 "int() missing string argument");
4969 return NULL;
4970 }
4971 return PyLong_FromLong(0L);
4972 }
4973 /* default base and limit, forward to standard implementation */
4974 if (obase == NULL)
4975 return PyNumber_Long(x);
4976
4977 base = PyNumber_AsSsize_t(obase, NULL);
4978 if (base == -1 && PyErr_Occurred())
4979 return NULL;
4980 if ((base != 0 && base < 2) || base > 36) {
4981 PyErr_SetString(PyExc_ValueError,
4982 "int() base must be >= 2 and <= 36, or 0");
4983 return NULL;
4984 }
4985
4986 if (PyUnicode_Check(x))
4987 return PyLong_FromUnicodeObject(x, (int)base);
4988 else if (PyByteArray_Check(x) || PyBytes_Check(x)) {
4989 const char *string;
4990 if (PyByteArray_Check(x))
4991 string = PyByteArray_AS_STRING(x);
4992 else
4993 string = PyBytes_AS_STRING(x);
4994 return _PyLong_FromBytes(string, Py_SIZE(x), (int)base);
4995 }
4996 else {
4997 PyErr_SetString(PyExc_TypeError,
4998 "int() can't convert non-string with explicit base");
4999 return NULL;
5000 }
5001 }
5002
5003 /* Wimpy, slow approach to tp_new calls for subtypes of int:
5004 first create a regular int from whatever arguments we got,
5005 then allocate a subtype instance and initialize it from
5006 the regular int. The regular int is then thrown away.
5007 */
5008 static PyObject *
long_subtype_new(PyTypeObject * type,PyObject * x,PyObject * obase)5009 long_subtype_new(PyTypeObject *type, PyObject *x, PyObject *obase)
5010 {
5011 PyLongObject *tmp, *newobj;
5012 Py_ssize_t i, n;
5013
5014 assert(PyType_IsSubtype(type, &PyLong_Type));
5015 tmp = (PyLongObject *)long_new_impl(&PyLong_Type, x, obase);
5016 if (tmp == NULL)
5017 return NULL;
5018 assert(PyLong_Check(tmp));
5019 n = Py_SIZE(tmp);
5020 if (n < 0)
5021 n = -n;
5022 newobj = (PyLongObject *)type->tp_alloc(type, n);
5023 if (newobj == NULL) {
5024 Py_DECREF(tmp);
5025 return NULL;
5026 }
5027 assert(PyLong_Check(newobj));
5028 Py_SET_SIZE(newobj, Py_SIZE(tmp));
5029 for (i = 0; i < n; i++) {
5030 newobj->ob_digit[i] = tmp->ob_digit[i];
5031 }
5032 Py_DECREF(tmp);
5033 return (PyObject *)newobj;
5034 }
5035
5036 /*[clinic input]
5037 int.__getnewargs__
5038 [clinic start generated code]*/
5039
5040 static PyObject *
int___getnewargs___impl(PyObject * self)5041 int___getnewargs___impl(PyObject *self)
5042 /*[clinic end generated code: output=839a49de3f00b61b input=5904770ab1fb8c75]*/
5043 {
5044 return Py_BuildValue("(N)", _PyLong_Copy((PyLongObject *)self));
5045 }
5046
5047 static PyObject *
long_get0(PyObject * Py_UNUSED (self),void * Py_UNUSED (context))5048 long_get0(PyObject *Py_UNUSED(self), void *Py_UNUSED(context))
5049 {
5050 return PyLong_FromLong(0L);
5051 }
5052
5053 static PyObject *
long_get1(PyObject * Py_UNUSED (self),void * Py_UNUSED (ignored))5054 long_get1(PyObject *Py_UNUSED(self), void *Py_UNUSED(ignored))
5055 {
5056 return PyLong_FromLong(1L);
5057 }
5058
5059 /*[clinic input]
5060 int.__format__
5061
5062 format_spec: unicode
5063 /
5064 [clinic start generated code]*/
5065
5066 static PyObject *
int___format___impl(PyObject * self,PyObject * format_spec)5067 int___format___impl(PyObject *self, PyObject *format_spec)
5068 /*[clinic end generated code: output=b4929dee9ae18689 input=e31944a9b3e428b7]*/
5069 {
5070 _PyUnicodeWriter writer;
5071 int ret;
5072
5073 _PyUnicodeWriter_Init(&writer);
5074 ret = _PyLong_FormatAdvancedWriter(
5075 &writer,
5076 self,
5077 format_spec, 0, PyUnicode_GET_LENGTH(format_spec));
5078 if (ret == -1) {
5079 _PyUnicodeWriter_Dealloc(&writer);
5080 return NULL;
5081 }
5082 return _PyUnicodeWriter_Finish(&writer);
5083 }
5084
5085 /* Return a pair (q, r) such that a = b * q + r, and
5086 abs(r) <= abs(b)/2, with equality possible only if q is even.
5087 In other words, q == a / b, rounded to the nearest integer using
5088 round-half-to-even. */
5089
5090 PyObject *
_PyLong_DivmodNear(PyObject * a,PyObject * b)5091 _PyLong_DivmodNear(PyObject *a, PyObject *b)
5092 {
5093 PyLongObject *quo = NULL, *rem = NULL;
5094 PyObject *twice_rem, *result, *temp;
5095 int quo_is_odd, quo_is_neg;
5096 Py_ssize_t cmp;
5097
5098 /* Equivalent Python code:
5099
5100 def divmod_near(a, b):
5101 q, r = divmod(a, b)
5102 # round up if either r / b > 0.5, or r / b == 0.5 and q is odd.
5103 # The expression r / b > 0.5 is equivalent to 2 * r > b if b is
5104 # positive, 2 * r < b if b negative.
5105 greater_than_half = 2*r > b if b > 0 else 2*r < b
5106 exactly_half = 2*r == b
5107 if greater_than_half or exactly_half and q % 2 == 1:
5108 q += 1
5109 r -= b
5110 return q, r
5111
5112 */
5113 if (!PyLong_Check(a) || !PyLong_Check(b)) {
5114 PyErr_SetString(PyExc_TypeError,
5115 "non-integer arguments in division");
5116 return NULL;
5117 }
5118
5119 /* Do a and b have different signs? If so, quotient is negative. */
5120 quo_is_neg = (Py_SIZE(a) < 0) != (Py_SIZE(b) < 0);
5121
5122 if (long_divrem((PyLongObject*)a, (PyLongObject*)b, &quo, &rem) < 0)
5123 goto error;
5124
5125 /* compare twice the remainder with the divisor, to see
5126 if we need to adjust the quotient and remainder */
5127 PyObject *one = _PyLong_GetOne(); // borrowed reference
5128 twice_rem = long_lshift((PyObject *)rem, one);
5129 if (twice_rem == NULL)
5130 goto error;
5131 if (quo_is_neg) {
5132 temp = long_neg((PyLongObject*)twice_rem);
5133 Py_DECREF(twice_rem);
5134 twice_rem = temp;
5135 if (twice_rem == NULL)
5136 goto error;
5137 }
5138 cmp = long_compare((PyLongObject *)twice_rem, (PyLongObject *)b);
5139 Py_DECREF(twice_rem);
5140
5141 quo_is_odd = Py_SIZE(quo) != 0 && ((quo->ob_digit[0] & 1) != 0);
5142 if ((Py_SIZE(b) < 0 ? cmp < 0 : cmp > 0) || (cmp == 0 && quo_is_odd)) {
5143 /* fix up quotient */
5144 if (quo_is_neg)
5145 temp = long_sub(quo, (PyLongObject *)one);
5146 else
5147 temp = long_add(quo, (PyLongObject *)one);
5148 Py_DECREF(quo);
5149 quo = (PyLongObject *)temp;
5150 if (quo == NULL)
5151 goto error;
5152 /* and remainder */
5153 if (quo_is_neg)
5154 temp = long_add(rem, (PyLongObject *)b);
5155 else
5156 temp = long_sub(rem, (PyLongObject *)b);
5157 Py_DECREF(rem);
5158 rem = (PyLongObject *)temp;
5159 if (rem == NULL)
5160 goto error;
5161 }
5162
5163 result = PyTuple_New(2);
5164 if (result == NULL)
5165 goto error;
5166
5167 /* PyTuple_SET_ITEM steals references */
5168 PyTuple_SET_ITEM(result, 0, (PyObject *)quo);
5169 PyTuple_SET_ITEM(result, 1, (PyObject *)rem);
5170 return result;
5171
5172 error:
5173 Py_XDECREF(quo);
5174 Py_XDECREF(rem);
5175 return NULL;
5176 }
5177
5178 /*[clinic input]
5179 int.__round__
5180
5181 ndigits as o_ndigits: object = NULL
5182 /
5183
5184 Rounding an Integral returns itself.
5185
5186 Rounding with an ndigits argument also returns an integer.
5187 [clinic start generated code]*/
5188
5189 static PyObject *
int___round___impl(PyObject * self,PyObject * o_ndigits)5190 int___round___impl(PyObject *self, PyObject *o_ndigits)
5191 /*[clinic end generated code: output=954fda6b18875998 input=1614cf23ec9e18c3]*/
5192 {
5193 PyObject *temp, *result, *ndigits;
5194
5195 /* To round an integer m to the nearest 10**n (n positive), we make use of
5196 * the divmod_near operation, defined by:
5197 *
5198 * divmod_near(a, b) = (q, r)
5199 *
5200 * where q is the nearest integer to the quotient a / b (the
5201 * nearest even integer in the case of a tie) and r == a - q * b.
5202 * Hence q * b = a - r is the nearest multiple of b to a,
5203 * preferring even multiples in the case of a tie.
5204 *
5205 * So the nearest multiple of 10**n to m is:
5206 *
5207 * m - divmod_near(m, 10**n)[1].
5208 */
5209 if (o_ndigits == NULL)
5210 return long_long(self);
5211
5212 ndigits = _PyNumber_Index(o_ndigits);
5213 if (ndigits == NULL)
5214 return NULL;
5215
5216 /* if ndigits >= 0 then no rounding is necessary; return self unchanged */
5217 if (Py_SIZE(ndigits) >= 0) {
5218 Py_DECREF(ndigits);
5219 return long_long(self);
5220 }
5221
5222 /* result = self - divmod_near(self, 10 ** -ndigits)[1] */
5223 temp = long_neg((PyLongObject*)ndigits);
5224 Py_DECREF(ndigits);
5225 ndigits = temp;
5226 if (ndigits == NULL)
5227 return NULL;
5228
5229 result = PyLong_FromLong(10L);
5230 if (result == NULL) {
5231 Py_DECREF(ndigits);
5232 return NULL;
5233 }
5234
5235 temp = long_pow(result, ndigits, Py_None);
5236 Py_DECREF(ndigits);
5237 Py_DECREF(result);
5238 result = temp;
5239 if (result == NULL)
5240 return NULL;
5241
5242 temp = _PyLong_DivmodNear(self, result);
5243 Py_DECREF(result);
5244 result = temp;
5245 if (result == NULL)
5246 return NULL;
5247
5248 temp = long_sub((PyLongObject *)self,
5249 (PyLongObject *)PyTuple_GET_ITEM(result, 1));
5250 Py_DECREF(result);
5251 result = temp;
5252
5253 return result;
5254 }
5255
5256 /*[clinic input]
5257 int.__sizeof__ -> Py_ssize_t
5258
5259 Returns size in memory, in bytes.
5260 [clinic start generated code]*/
5261
5262 static Py_ssize_t
int___sizeof___impl(PyObject * self)5263 int___sizeof___impl(PyObject *self)
5264 /*[clinic end generated code: output=3303f008eaa6a0a5 input=9b51620c76fc4507]*/
5265 {
5266 Py_ssize_t res;
5267
5268 res = offsetof(PyLongObject, ob_digit) + Py_ABS(Py_SIZE(self))*sizeof(digit);
5269 return res;
5270 }
5271
5272 /*[clinic input]
5273 int.bit_length
5274
5275 Number of bits necessary to represent self in binary.
5276
5277 >>> bin(37)
5278 '0b100101'
5279 >>> (37).bit_length()
5280 6
5281 [clinic start generated code]*/
5282
5283 static PyObject *
int_bit_length_impl(PyObject * self)5284 int_bit_length_impl(PyObject *self)
5285 /*[clinic end generated code: output=fc1977c9353d6a59 input=e4eb7a587e849a32]*/
5286 {
5287 PyLongObject *result, *x, *y;
5288 Py_ssize_t ndigits;
5289 int msd_bits;
5290 digit msd;
5291
5292 assert(self != NULL);
5293 assert(PyLong_Check(self));
5294
5295 ndigits = Py_ABS(Py_SIZE(self));
5296 if (ndigits == 0)
5297 return PyLong_FromLong(0);
5298
5299 msd = ((PyLongObject *)self)->ob_digit[ndigits-1];
5300 msd_bits = bit_length_digit(msd);
5301
5302 if (ndigits <= PY_SSIZE_T_MAX/PyLong_SHIFT)
5303 return PyLong_FromSsize_t((ndigits-1)*PyLong_SHIFT + msd_bits);
5304
5305 /* expression above may overflow; use Python integers instead */
5306 result = (PyLongObject *)PyLong_FromSsize_t(ndigits - 1);
5307 if (result == NULL)
5308 return NULL;
5309 x = (PyLongObject *)PyLong_FromLong(PyLong_SHIFT);
5310 if (x == NULL)
5311 goto error;
5312 y = (PyLongObject *)long_mul(result, x);
5313 Py_DECREF(x);
5314 if (y == NULL)
5315 goto error;
5316 Py_DECREF(result);
5317 result = y;
5318
5319 x = (PyLongObject *)PyLong_FromLong((long)msd_bits);
5320 if (x == NULL)
5321 goto error;
5322 y = (PyLongObject *)long_add(result, x);
5323 Py_DECREF(x);
5324 if (y == NULL)
5325 goto error;
5326 Py_DECREF(result);
5327 result = y;
5328
5329 return (PyObject *)result;
5330
5331 error:
5332 Py_DECREF(result);
5333 return NULL;
5334 }
5335
5336 static int
popcount_digit(digit d)5337 popcount_digit(digit d)
5338 {
5339 // digit can be larger than uint32_t, but only PyLong_SHIFT bits
5340 // of it will be ever used.
5341 Py_BUILD_ASSERT(PyLong_SHIFT <= 32);
5342 return _Py_popcount32((uint32_t)d);
5343 }
5344
5345 /*[clinic input]
5346 int.bit_count
5347
5348 Number of ones in the binary representation of the absolute value of self.
5349
5350 Also known as the population count.
5351
5352 >>> bin(13)
5353 '0b1101'
5354 >>> (13).bit_count()
5355 3
5356 [clinic start generated code]*/
5357
5358 static PyObject *
int_bit_count_impl(PyObject * self)5359 int_bit_count_impl(PyObject *self)
5360 /*[clinic end generated code: output=2e571970daf1e5c3 input=7e0adef8e8ccdf2e]*/
5361 {
5362 assert(self != NULL);
5363 assert(PyLong_Check(self));
5364
5365 PyLongObject *z = (PyLongObject *)self;
5366 Py_ssize_t ndigits = Py_ABS(Py_SIZE(z));
5367 Py_ssize_t bit_count = 0;
5368
5369 /* Each digit has up to PyLong_SHIFT ones, so the accumulated bit count
5370 from the first PY_SSIZE_T_MAX/PyLong_SHIFT digits can't overflow a
5371 Py_ssize_t. */
5372 Py_ssize_t ndigits_fast = Py_MIN(ndigits, PY_SSIZE_T_MAX/PyLong_SHIFT);
5373 for (Py_ssize_t i = 0; i < ndigits_fast; i++) {
5374 bit_count += popcount_digit(z->ob_digit[i]);
5375 }
5376
5377 PyObject *result = PyLong_FromSsize_t(bit_count);
5378 if (result == NULL) {
5379 return NULL;
5380 }
5381
5382 /* Use Python integers if bit_count would overflow. */
5383 for (Py_ssize_t i = ndigits_fast; i < ndigits; i++) {
5384 PyObject *x = PyLong_FromLong(popcount_digit(z->ob_digit[i]));
5385 if (x == NULL) {
5386 goto error;
5387 }
5388 PyObject *y = long_add((PyLongObject *)result, (PyLongObject *)x);
5389 Py_DECREF(x);
5390 if (y == NULL) {
5391 goto error;
5392 }
5393 Py_DECREF(result);
5394 result = y;
5395 }
5396
5397 return result;
5398
5399 error:
5400 Py_DECREF(result);
5401 return NULL;
5402 }
5403
5404 /*[clinic input]
5405 int.as_integer_ratio
5406
5407 Return integer ratio.
5408
5409 Return a pair of integers, whose ratio is exactly equal to the original int
5410 and with a positive denominator.
5411
5412 >>> (10).as_integer_ratio()
5413 (10, 1)
5414 >>> (-10).as_integer_ratio()
5415 (-10, 1)
5416 >>> (0).as_integer_ratio()
5417 (0, 1)
5418 [clinic start generated code]*/
5419
5420 static PyObject *
int_as_integer_ratio_impl(PyObject * self)5421 int_as_integer_ratio_impl(PyObject *self)
5422 /*[clinic end generated code: output=e60803ae1cc8621a input=55ce3058e15de393]*/
5423 {
5424 PyObject *ratio_tuple;
5425 PyObject *numerator = long_long(self);
5426 if (numerator == NULL) {
5427 return NULL;
5428 }
5429 ratio_tuple = PyTuple_Pack(2, numerator, _PyLong_GetOne());
5430 Py_DECREF(numerator);
5431 return ratio_tuple;
5432 }
5433
5434 /*[clinic input]
5435 int.to_bytes
5436
5437 length: Py_ssize_t
5438 Length of bytes object to use. An OverflowError is raised if the
5439 integer is not representable with the given number of bytes.
5440 byteorder: unicode
5441 The byte order used to represent the integer. If byteorder is 'big',
5442 the most significant byte is at the beginning of the byte array. If
5443 byteorder is 'little', the most significant byte is at the end of the
5444 byte array. To request the native byte order of the host system, use
5445 `sys.byteorder' as the byte order value.
5446 *
5447 signed as is_signed: bool = False
5448 Determines whether two's complement is used to represent the integer.
5449 If signed is False and a negative integer is given, an OverflowError
5450 is raised.
5451
5452 Return an array of bytes representing an integer.
5453 [clinic start generated code]*/
5454
5455 static PyObject *
int_to_bytes_impl(PyObject * self,Py_ssize_t length,PyObject * byteorder,int is_signed)5456 int_to_bytes_impl(PyObject *self, Py_ssize_t length, PyObject *byteorder,
5457 int is_signed)
5458 /*[clinic end generated code: output=89c801df114050a3 input=ddac63f4c7bf414c]*/
5459 {
5460 int little_endian;
5461 PyObject *bytes;
5462
5463 if (_PyUnicode_EqualToASCIIId(byteorder, &PyId_little))
5464 little_endian = 1;
5465 else if (_PyUnicode_EqualToASCIIId(byteorder, &PyId_big))
5466 little_endian = 0;
5467 else {
5468 PyErr_SetString(PyExc_ValueError,
5469 "byteorder must be either 'little' or 'big'");
5470 return NULL;
5471 }
5472
5473 if (length < 0) {
5474 PyErr_SetString(PyExc_ValueError,
5475 "length argument must be non-negative");
5476 return NULL;
5477 }
5478
5479 bytes = PyBytes_FromStringAndSize(NULL, length);
5480 if (bytes == NULL)
5481 return NULL;
5482
5483 if (_PyLong_AsByteArray((PyLongObject *)self,
5484 (unsigned char *)PyBytes_AS_STRING(bytes),
5485 length, little_endian, is_signed) < 0) {
5486 Py_DECREF(bytes);
5487 return NULL;
5488 }
5489
5490 return bytes;
5491 }
5492
5493 /*[clinic input]
5494 @classmethod
5495 int.from_bytes
5496
5497 bytes as bytes_obj: object
5498 Holds the array of bytes to convert. The argument must either
5499 support the buffer protocol or be an iterable object producing bytes.
5500 Bytes and bytearray are examples of built-in objects that support the
5501 buffer protocol.
5502 byteorder: unicode
5503 The byte order used to represent the integer. If byteorder is 'big',
5504 the most significant byte is at the beginning of the byte array. If
5505 byteorder is 'little', the most significant byte is at the end of the
5506 byte array. To request the native byte order of the host system, use
5507 `sys.byteorder' as the byte order value.
5508 *
5509 signed as is_signed: bool = False
5510 Indicates whether two's complement is used to represent the integer.
5511
5512 Return the integer represented by the given array of bytes.
5513 [clinic start generated code]*/
5514
5515 static PyObject *
int_from_bytes_impl(PyTypeObject * type,PyObject * bytes_obj,PyObject * byteorder,int is_signed)5516 int_from_bytes_impl(PyTypeObject *type, PyObject *bytes_obj,
5517 PyObject *byteorder, int is_signed)
5518 /*[clinic end generated code: output=efc5d68e31f9314f input=cdf98332b6a821b0]*/
5519 {
5520 int little_endian;
5521 PyObject *long_obj, *bytes;
5522
5523 if (_PyUnicode_EqualToASCIIId(byteorder, &PyId_little))
5524 little_endian = 1;
5525 else if (_PyUnicode_EqualToASCIIId(byteorder, &PyId_big))
5526 little_endian = 0;
5527 else {
5528 PyErr_SetString(PyExc_ValueError,
5529 "byteorder must be either 'little' or 'big'");
5530 return NULL;
5531 }
5532
5533 bytes = PyObject_Bytes(bytes_obj);
5534 if (bytes == NULL)
5535 return NULL;
5536
5537 long_obj = _PyLong_FromByteArray(
5538 (unsigned char *)PyBytes_AS_STRING(bytes), Py_SIZE(bytes),
5539 little_endian, is_signed);
5540 Py_DECREF(bytes);
5541
5542 if (long_obj != NULL && type != &PyLong_Type) {
5543 Py_SETREF(long_obj, PyObject_CallOneArg((PyObject *)type, long_obj));
5544 }
5545
5546 return long_obj;
5547 }
5548
5549 static PyObject *
long_long_meth(PyObject * self,PyObject * Py_UNUSED (ignored))5550 long_long_meth(PyObject *self, PyObject *Py_UNUSED(ignored))
5551 {
5552 return long_long(self);
5553 }
5554
5555 static PyMethodDef long_methods[] = {
5556 {"conjugate", long_long_meth, METH_NOARGS,
5557 "Returns self, the complex conjugate of any int."},
5558 INT_BIT_LENGTH_METHODDEF
5559 INT_BIT_COUNT_METHODDEF
5560 INT_TO_BYTES_METHODDEF
5561 INT_FROM_BYTES_METHODDEF
5562 INT_AS_INTEGER_RATIO_METHODDEF
5563 {"__trunc__", long_long_meth, METH_NOARGS,
5564 "Truncating an Integral returns itself."},
5565 {"__floor__", long_long_meth, METH_NOARGS,
5566 "Flooring an Integral returns itself."},
5567 {"__ceil__", long_long_meth, METH_NOARGS,
5568 "Ceiling of an Integral returns itself."},
5569 INT___ROUND___METHODDEF
5570 INT___GETNEWARGS___METHODDEF
5571 INT___FORMAT___METHODDEF
5572 INT___SIZEOF___METHODDEF
5573 {NULL, NULL} /* sentinel */
5574 };
5575
5576 static PyGetSetDef long_getset[] = {
5577 {"real",
5578 (getter)long_long_meth, (setter)NULL,
5579 "the real part of a complex number",
5580 NULL},
5581 {"imag",
5582 long_get0, (setter)NULL,
5583 "the imaginary part of a complex number",
5584 NULL},
5585 {"numerator",
5586 (getter)long_long_meth, (setter)NULL,
5587 "the numerator of a rational number in lowest terms",
5588 NULL},
5589 {"denominator",
5590 long_get1, (setter)NULL,
5591 "the denominator of a rational number in lowest terms",
5592 NULL},
5593 {NULL} /* Sentinel */
5594 };
5595
5596 PyDoc_STRVAR(long_doc,
5597 "int([x]) -> integer\n\
5598 int(x, base=10) -> integer\n\
5599 \n\
5600 Convert a number or string to an integer, or return 0 if no arguments\n\
5601 are given. If x is a number, return x.__int__(). For floating point\n\
5602 numbers, this truncates towards zero.\n\
5603 \n\
5604 If x is not a number or if base is given, then x must be a string,\n\
5605 bytes, or bytearray instance representing an integer literal in the\n\
5606 given base. The literal can be preceded by '+' or '-' and be surrounded\n\
5607 by whitespace. The base defaults to 10. Valid bases are 0 and 2-36.\n\
5608 Base 0 means to interpret the base from the string as an integer literal.\n\
5609 >>> int('0b100', base=0)\n\
5610 4");
5611
5612 static PyNumberMethods long_as_number = {
5613 (binaryfunc)long_add, /*nb_add*/
5614 (binaryfunc)long_sub, /*nb_subtract*/
5615 (binaryfunc)long_mul, /*nb_multiply*/
5616 long_mod, /*nb_remainder*/
5617 long_divmod, /*nb_divmod*/
5618 long_pow, /*nb_power*/
5619 (unaryfunc)long_neg, /*nb_negative*/
5620 long_long, /*tp_positive*/
5621 (unaryfunc)long_abs, /*tp_absolute*/
5622 (inquiry)long_bool, /*tp_bool*/
5623 (unaryfunc)long_invert, /*nb_invert*/
5624 long_lshift, /*nb_lshift*/
5625 long_rshift, /*nb_rshift*/
5626 long_and, /*nb_and*/
5627 long_xor, /*nb_xor*/
5628 long_or, /*nb_or*/
5629 long_long, /*nb_int*/
5630 0, /*nb_reserved*/
5631 long_float, /*nb_float*/
5632 0, /* nb_inplace_add */
5633 0, /* nb_inplace_subtract */
5634 0, /* nb_inplace_multiply */
5635 0, /* nb_inplace_remainder */
5636 0, /* nb_inplace_power */
5637 0, /* nb_inplace_lshift */
5638 0, /* nb_inplace_rshift */
5639 0, /* nb_inplace_and */
5640 0, /* nb_inplace_xor */
5641 0, /* nb_inplace_or */
5642 long_div, /* nb_floor_divide */
5643 long_true_divide, /* nb_true_divide */
5644 0, /* nb_inplace_floor_divide */
5645 0, /* nb_inplace_true_divide */
5646 long_long, /* nb_index */
5647 };
5648
5649 PyTypeObject PyLong_Type = {
5650 PyVarObject_HEAD_INIT(&PyType_Type, 0)
5651 "int", /* tp_name */
5652 offsetof(PyLongObject, ob_digit), /* tp_basicsize */
5653 sizeof(digit), /* tp_itemsize */
5654 0, /* tp_dealloc */
5655 0, /* tp_vectorcall_offset */
5656 0, /* tp_getattr */
5657 0, /* tp_setattr */
5658 0, /* tp_as_async */
5659 long_to_decimal_string, /* tp_repr */
5660 &long_as_number, /* tp_as_number */
5661 0, /* tp_as_sequence */
5662 0, /* tp_as_mapping */
5663 (hashfunc)long_hash, /* tp_hash */
5664 0, /* tp_call */
5665 0, /* tp_str */
5666 PyObject_GenericGetAttr, /* tp_getattro */
5667 0, /* tp_setattro */
5668 0, /* tp_as_buffer */
5669 Py_TPFLAGS_DEFAULT | Py_TPFLAGS_BASETYPE |
5670 Py_TPFLAGS_LONG_SUBCLASS |
5671 _Py_TPFLAGS_MATCH_SELF, /* tp_flags */
5672 long_doc, /* tp_doc */
5673 0, /* tp_traverse */
5674 0, /* tp_clear */
5675 long_richcompare, /* tp_richcompare */
5676 0, /* tp_weaklistoffset */
5677 0, /* tp_iter */
5678 0, /* tp_iternext */
5679 long_methods, /* tp_methods */
5680 0, /* tp_members */
5681 long_getset, /* tp_getset */
5682 0, /* tp_base */
5683 0, /* tp_dict */
5684 0, /* tp_descr_get */
5685 0, /* tp_descr_set */
5686 0, /* tp_dictoffset */
5687 0, /* tp_init */
5688 0, /* tp_alloc */
5689 long_new, /* tp_new */
5690 PyObject_Del, /* tp_free */
5691 };
5692
5693 static PyTypeObject Int_InfoType;
5694
5695 PyDoc_STRVAR(int_info__doc__,
5696 "sys.int_info\n\
5697 \n\
5698 A named tuple that holds information about Python's\n\
5699 internal representation of integers. The attributes are read only.");
5700
5701 static PyStructSequence_Field int_info_fields[] = {
5702 {"bits_per_digit", "size of a digit in bits"},
5703 {"sizeof_digit", "size in bytes of the C type used to represent a digit"},
5704 {"default_max_str_digits", "maximum string conversion digits limitation"},
5705 {"str_digits_check_threshold", "minimum positive value for int_max_str_digits"},
5706 {NULL, NULL}
5707 };
5708
5709 static PyStructSequence_Desc int_info_desc = {
5710 "sys.int_info", /* name */
5711 int_info__doc__, /* doc */
5712 int_info_fields, /* fields */
5713 4 /* number of fields */
5714 };
5715
5716 PyObject *
PyLong_GetInfo(void)5717 PyLong_GetInfo(void)
5718 {
5719 PyObject* int_info;
5720 int field = 0;
5721 int_info = PyStructSequence_New(&Int_InfoType);
5722 if (int_info == NULL)
5723 return NULL;
5724 PyStructSequence_SET_ITEM(int_info, field++,
5725 PyLong_FromLong(PyLong_SHIFT));
5726 PyStructSequence_SET_ITEM(int_info, field++,
5727 PyLong_FromLong(sizeof(digit)));
5728 /*
5729 * The following two fields were added after investigating uses of
5730 * sys.int_info in the wild: Exceedingly rarely used. The ONLY use found was
5731 * numba using sys.int_info.bits_per_digit as attribute access rather than
5732 * sequence unpacking. Cython and sympy also refer to sys.int_info but only
5733 * as info for debugging. No concern about adding these in a backport.
5734 */
5735 PyStructSequence_SET_ITEM(int_info, field++,
5736 PyLong_FromLong(_PY_LONG_DEFAULT_MAX_STR_DIGITS));
5737 PyStructSequence_SET_ITEM(int_info, field++,
5738 PyLong_FromLong(_PY_LONG_MAX_STR_DIGITS_THRESHOLD));
5739 if (PyErr_Occurred()) {
5740 Py_CLEAR(int_info);
5741 return NULL;
5742 }
5743 return int_info;
5744 }
5745
5746 int
_PyLong_Init(PyInterpreterState * interp)5747 _PyLong_Init(PyInterpreterState *interp)
5748 {
5749 for (Py_ssize_t i=0; i < NSMALLNEGINTS + NSMALLPOSINTS; i++) {
5750 sdigit ival = (sdigit)i - NSMALLNEGINTS;
5751 int size = (ival < 0) ? -1 : ((ival == 0) ? 0 : 1);
5752
5753 PyLongObject *v = _PyLong_New(1);
5754 if (!v) {
5755 return -1;
5756 }
5757
5758 Py_SET_SIZE(v, size);
5759 v->ob_digit[0] = (digit)abs(ival);
5760
5761 interp->small_ints[i] = v;
5762 }
5763 interp->int_max_str_digits = _Py_global_config_int_max_str_digits;
5764 if (interp->int_max_str_digits == -1) {
5765 interp->int_max_str_digits = _PY_LONG_DEFAULT_MAX_STR_DIGITS;
5766 }
5767 return 0;
5768 }
5769
5770
5771 int
_PyLong_InitTypes(void)5772 _PyLong_InitTypes(void)
5773 {
5774 /* initialize int_info */
5775 if (Int_InfoType.tp_name == NULL) {
5776 if (PyStructSequence_InitType2(&Int_InfoType, &int_info_desc) < 0) {
5777 return -1;
5778 }
5779 }
5780 return 0;
5781 }
5782
5783 void
_PyLong_Fini(PyInterpreterState * interp)5784 _PyLong_Fini(PyInterpreterState *interp)
5785 {
5786 for (Py_ssize_t i = 0; i < NSMALLNEGINTS + NSMALLPOSINTS; i++) {
5787 Py_CLEAR(interp->small_ints[i]);
5788 }
5789 }
5790