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