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