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