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