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