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