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