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