• 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 #include "structseq.h"
8 
9 #include <float.h>
10 #include <ctype.h>
11 #include <stddef.h>
12 
13 /* For long multiplication, use the O(N**2) school algorithm unless
14  * both operands contain more than KARATSUBA_CUTOFF digits (this
15  * being an internal Python long digit, in base PyLong_BASE).
16  */
17 #define KARATSUBA_CUTOFF 70
18 #define KARATSUBA_SQUARE_CUTOFF (2 * KARATSUBA_CUTOFF)
19 
20 /* For exponentiation, use the binary left-to-right algorithm
21  * unless the exponent contains more than FIVEARY_CUTOFF digits.
22  * In that case, do 5 bits at a time.  The potential drawback is that
23  * a table of 2**5 intermediate results is computed.
24  */
25 #define FIVEARY_CUTOFF 8
26 
27 #define ABS(x) ((x) < 0 ? -(x) : (x))
28 
29 #undef MIN
30 #undef MAX
31 #define MAX(x, y) ((x) < (y) ? (y) : (x))
32 #define MIN(x, y) ((x) > (y) ? (y) : (x))
33 
34 #define SIGCHECK(PyTryBlock)                            \
35     do {                                                \
36         if (--_Py_Ticker < 0) {                         \
37             _Py_Ticker = _Py_CheckInterval;             \
38             if (PyErr_CheckSignals()) PyTryBlock        \
39                                           }             \
40     } while(0)
41 
42 /* Normalize (remove leading zeros from) a long int object.
43    Doesn't attempt to free the storage--in most cases, due to the nature
44    of the algorithms used, this could save at most be one word anyway. */
45 
46 static PyLongObject *
long_normalize(register PyLongObject * v)47 long_normalize(register PyLongObject *v)
48 {
49     Py_ssize_t j = ABS(Py_SIZE(v));
50     Py_ssize_t i = j;
51 
52     while (i > 0 && v->ob_digit[i-1] == 0)
53         --i;
54     if (i != j)
55         Py_SIZE(v) = (Py_SIZE(v) < 0) ? -(i) : i;
56     return v;
57 }
58 
59 /* Allocate a new long int object with size digits.
60    Return NULL and set exception if we run out of memory. */
61 
62 #define MAX_LONG_DIGITS \
63     ((PY_SSIZE_T_MAX - offsetof(PyLongObject, ob_digit))/sizeof(digit))
64 
65 PyLongObject *
_PyLong_New(Py_ssize_t size)66 _PyLong_New(Py_ssize_t size)
67 {
68     if (size > (Py_ssize_t)MAX_LONG_DIGITS) {
69         PyErr_SetString(PyExc_OverflowError,
70                         "too many digits in integer");
71         return NULL;
72     }
73     /* coverity[ampersand_in_size] */
74     /* XXX(nnorwitz): PyObject_NEW_VAR / _PyObject_VAR_SIZE need to detect
75        overflow */
76     return PyObject_NEW_VAR(PyLongObject, &PyLong_Type, size);
77 }
78 
79 PyObject *
_PyLong_Copy(PyLongObject * src)80 _PyLong_Copy(PyLongObject *src)
81 {
82     PyLongObject *result;
83     Py_ssize_t i;
84 
85     assert(src != NULL);
86     i = src->ob_size;
87     if (i < 0)
88         i = -(i);
89     result = _PyLong_New(i);
90     if (result != NULL) {
91         result->ob_size = src->ob_size;
92         while (--i >= 0)
93             result->ob_digit[i] = src->ob_digit[i];
94     }
95     return (PyObject *)result;
96 }
97 
98 /* Create a new long int object from a C long int */
99 
100 PyObject *
PyLong_FromLong(long ival)101 PyLong_FromLong(long ival)
102 {
103     PyLongObject *v;
104     unsigned long abs_ival;
105     unsigned long t;  /* unsigned so >> doesn't propagate sign bit */
106     int ndigits = 0;
107     int negative = 0;
108 
109     if (ival < 0) {
110         /* if LONG_MIN == -LONG_MAX-1 (true on most platforms) then
111            ANSI C says that the result of -ival is undefined when ival
112            == LONG_MIN.  Hence the following workaround. */
113         abs_ival = (unsigned long)(-1-ival) + 1;
114         negative = 1;
115     }
116     else {
117         abs_ival = (unsigned long)ival;
118     }
119 
120     /* Count the number of Python digits.
121        We used to pick 5 ("big enough for anything"), but that's a
122        waste of time and space given that 5*15 = 75 bits are rarely
123        needed. */
124     t = abs_ival;
125     while (t) {
126         ++ndigits;
127         t >>= PyLong_SHIFT;
128     }
129     v = _PyLong_New(ndigits);
130     if (v != NULL) {
131         digit *p = v->ob_digit;
132         v->ob_size = negative ? -ndigits : ndigits;
133         t = abs_ival;
134         while (t) {
135             *p++ = (digit)(t & PyLong_MASK);
136             t >>= PyLong_SHIFT;
137         }
138     }
139     return (PyObject *)v;
140 }
141 
142 /* Create a new long int object from a C unsigned long int */
143 
144 PyObject *
PyLong_FromUnsignedLong(unsigned long ival)145 PyLong_FromUnsignedLong(unsigned long ival)
146 {
147     PyLongObject *v;
148     unsigned long t;
149     int ndigits = 0;
150 
151     /* Count the number of Python digits. */
152     t = (unsigned long)ival;
153     while (t) {
154         ++ndigits;
155         t >>= PyLong_SHIFT;
156     }
157     v = _PyLong_New(ndigits);
158     if (v != NULL) {
159         digit *p = v->ob_digit;
160         Py_SIZE(v) = ndigits;
161         while (ival) {
162             *p++ = (digit)(ival & PyLong_MASK);
163             ival >>= PyLong_SHIFT;
164         }
165     }
166     return (PyObject *)v;
167 }
168 
169 /* Create a new long int object from a C double */
170 
171 PyObject *
PyLong_FromDouble(double dval)172 PyLong_FromDouble(double dval)
173 {
174     PyLongObject *v;
175     double frac;
176     int i, ndig, expo, neg;
177     neg = 0;
178     if (Py_IS_INFINITY(dval)) {
179         PyErr_SetString(PyExc_OverflowError,
180                         "cannot convert float infinity to integer");
181         return NULL;
182     }
183     if (Py_IS_NAN(dval)) {
184         PyErr_SetString(PyExc_ValueError,
185                         "cannot convert float NaN to integer");
186         return NULL;
187     }
188     if (dval < 0.0) {
189         neg = 1;
190         dval = -dval;
191     }
192     frac = frexp(dval, &expo); /* dval = frac*2**expo; 0.0 <= frac < 1.0 */
193     if (expo <= 0)
194         return PyLong_FromLong(0L);
195     ndig = (expo-1) / PyLong_SHIFT + 1; /* Number of 'digits' in result */
196     v = _PyLong_New(ndig);
197     if (v == NULL)
198         return NULL;
199     frac = ldexp(frac, (expo-1) % PyLong_SHIFT + 1);
200     for (i = ndig; --i >= 0; ) {
201         digit bits = (digit)frac;
202         v->ob_digit[i] = bits;
203         frac = frac - (double)bits;
204         frac = ldexp(frac, PyLong_SHIFT);
205     }
206     if (neg)
207         Py_SIZE(v) = -(Py_SIZE(v));
208     return (PyObject *)v;
209 }
210 
211 /* Checking for overflow in PyLong_AsLong is a PITA since C doesn't define
212  * anything about what happens when a signed integer operation overflows,
213  * and some compilers think they're doing you a favor by being "clever"
214  * then.  The bit pattern for the largest positive signed long is
215  * (unsigned long)LONG_MAX, and for the smallest negative signed long
216  * it is abs(LONG_MIN), which we could write -(unsigned long)LONG_MIN.
217  * However, some other compilers warn about applying unary minus to an
218  * unsigned operand.  Hence the weird "0-".
219  */
220 #define PY_ABS_LONG_MIN         (0-(unsigned long)LONG_MIN)
221 #define PY_ABS_SSIZE_T_MIN      (0-(size_t)PY_SSIZE_T_MIN)
222 
223 /* Get a C long int from a Python long or Python int object.
224    On overflow, returns -1 and sets *overflow to 1 or -1 depending
225    on the sign of the result.  Otherwise *overflow is 0.
226 
227    For other errors (e.g., type error), returns -1 and sets an error
228    condition.
229 */
230 
231 long
PyLong_AsLongAndOverflow(PyObject * vv,int * overflow)232 PyLong_AsLongAndOverflow(PyObject *vv, int *overflow)
233 {
234     /* This version by Tim Peters */
235     register PyLongObject *v;
236     unsigned long x, prev;
237     long res;
238     Py_ssize_t i;
239     int sign;
240     int do_decref = 0; /* if nb_int was called */
241 
242     *overflow = 0;
243     if (vv == NULL) {
244         PyErr_BadInternalCall();
245         return -1;
246     }
247 
248     if(PyInt_Check(vv))
249         return PyInt_AsLong(vv);
250 
251     if (!PyLong_Check(vv)) {
252         PyNumberMethods *nb;
253         nb = vv->ob_type->tp_as_number;
254         if (nb == NULL || nb->nb_int == NULL) {
255             PyErr_SetString(PyExc_TypeError,
256                             "an integer is required");
257             return -1;
258         }
259         vv = (*nb->nb_int) (vv);
260         if (vv == NULL)
261             return -1;
262         do_decref = 1;
263         if(PyInt_Check(vv)) {
264             res = PyInt_AsLong(vv);
265             goto exit;
266         }
267         if (!PyLong_Check(vv)) {
268             Py_DECREF(vv);
269             PyErr_SetString(PyExc_TypeError,
270                             "nb_int should return int object");
271             return -1;
272         }
273     }
274 
275     res = -1;
276     v = (PyLongObject *)vv;
277     i = Py_SIZE(v);
278 
279     switch (i) {
280     case -1:
281         res = -(sdigit)v->ob_digit[0];
282         break;
283     case 0:
284         res = 0;
285         break;
286     case 1:
287         res = v->ob_digit[0];
288         break;
289     default:
290         sign = 1;
291         x = 0;
292         if (i < 0) {
293             sign = -1;
294             i = -(i);
295         }
296         while (--i >= 0) {
297             prev = x;
298             x = (x << PyLong_SHIFT) + v->ob_digit[i];
299             if ((x >> PyLong_SHIFT) != prev) {
300                 *overflow = sign;
301                 goto exit;
302             }
303         }
304         /* Haven't lost any bits, but casting to long requires extra
305          * care (see comment above).
306          */
307         if (x <= (unsigned long)LONG_MAX) {
308             res = (long)x * sign;
309         }
310         else if (sign < 0 && x == PY_ABS_LONG_MIN) {
311             res = LONG_MIN;
312         }
313         else {
314             *overflow = sign;
315             /* res is already set to -1 */
316         }
317     }
318   exit:
319     if (do_decref) {
320         Py_DECREF(vv);
321     }
322     return res;
323 }
324 
325 /* Get a C long int from a long int object.
326    Returns -1 and sets an error condition if overflow occurs. */
327 
328 long
PyLong_AsLong(PyObject * obj)329 PyLong_AsLong(PyObject *obj)
330 {
331     int overflow;
332     long result = PyLong_AsLongAndOverflow(obj, &overflow);
333     if (overflow) {
334         /* XXX: could be cute and give a different
335            message for overflow == -1 */
336         PyErr_SetString(PyExc_OverflowError,
337                         "Python int too large to convert to C long");
338     }
339     return result;
340 }
341 
342 /* Get a C int from a long int object or any object that has an __int__
343    method.  Return -1 and set an error if overflow occurs. */
344 
345 int
_PyLong_AsInt(PyObject * obj)346 _PyLong_AsInt(PyObject *obj)
347 {
348     int overflow;
349     long result = PyLong_AsLongAndOverflow(obj, &overflow);
350     if (overflow || result > INT_MAX || result < INT_MIN) {
351         /* XXX: could be cute and give a different
352            message for overflow == -1 */
353         PyErr_SetString(PyExc_OverflowError,
354                         "Python int too large to convert to C int");
355         return -1;
356     }
357     return (int)result;
358 }
359 
360 /* Get a Py_ssize_t from a long int object.
361    Returns -1 and sets an error condition if overflow occurs. */
362 
363 Py_ssize_t
PyLong_AsSsize_t(PyObject * vv)364 PyLong_AsSsize_t(PyObject *vv) {
365     register PyLongObject *v;
366     size_t x, prev;
367     Py_ssize_t i;
368     int sign;
369 
370     if (vv == NULL || !PyLong_Check(vv)) {
371         PyErr_BadInternalCall();
372         return -1;
373     }
374     v = (PyLongObject *)vv;
375     i = v->ob_size;
376     sign = 1;
377     x = 0;
378     if (i < 0) {
379         sign = -1;
380         i = -(i);
381     }
382     while (--i >= 0) {
383         prev = x;
384         x = (x << PyLong_SHIFT) | v->ob_digit[i];
385         if ((x >> PyLong_SHIFT) != prev)
386             goto overflow;
387     }
388     /* Haven't lost any bits, but casting to a signed type requires
389      * extra care (see comment above).
390      */
391     if (x <= (size_t)PY_SSIZE_T_MAX) {
392         return (Py_ssize_t)x * sign;
393     }
394     else if (sign < 0 && x == PY_ABS_SSIZE_T_MIN) {
395         return PY_SSIZE_T_MIN;
396     }
397     /* else overflow */
398 
399   overflow:
400     PyErr_SetString(PyExc_OverflowError,
401                     "long int too large to convert to int");
402     return -1;
403 }
404 
405 /* Get a C unsigned long int from a long int object.
406    Returns -1 and sets an error condition if overflow occurs. */
407 
408 unsigned long
PyLong_AsUnsignedLong(PyObject * vv)409 PyLong_AsUnsignedLong(PyObject *vv)
410 {
411     register PyLongObject *v;
412     unsigned long x, prev;
413     Py_ssize_t i;
414 
415     if (vv == NULL || !PyLong_Check(vv)) {
416         if (vv != NULL && PyInt_Check(vv)) {
417             long val = PyInt_AsLong(vv);
418             if (val < 0) {
419                 PyErr_SetString(PyExc_OverflowError,
420                                 "can't convert negative value "
421                                 "to unsigned long");
422                 return (unsigned long) -1;
423             }
424             return val;
425         }
426         PyErr_BadInternalCall();
427         return (unsigned long) -1;
428     }
429     v = (PyLongObject *)vv;
430     i = Py_SIZE(v);
431     x = 0;
432     if (i < 0) {
433         PyErr_SetString(PyExc_OverflowError,
434                         "can't convert negative value to unsigned long");
435         return (unsigned long) -1;
436     }
437     while (--i >= 0) {
438         prev = x;
439         x = (x << PyLong_SHIFT) | v->ob_digit[i];
440         if ((x >> PyLong_SHIFT) != prev) {
441             PyErr_SetString(PyExc_OverflowError,
442                             "long int too large to convert");
443             return (unsigned long) -1;
444         }
445     }
446     return x;
447 }
448 
449 /* Get a C unsigned long int from a long int object, ignoring the high bits.
450    Returns -1 and sets an error condition if an error occurs. */
451 
452 unsigned long
PyLong_AsUnsignedLongMask(PyObject * vv)453 PyLong_AsUnsignedLongMask(PyObject *vv)
454 {
455     register PyLongObject *v;
456     unsigned long x;
457     Py_ssize_t i;
458     int sign;
459 
460     if (vv == NULL || !PyLong_Check(vv)) {
461         if (vv != NULL && PyInt_Check(vv))
462             return PyInt_AsUnsignedLongMask(vv);
463         PyErr_BadInternalCall();
464         return (unsigned long) -1;
465     }
466     v = (PyLongObject *)vv;
467     i = v->ob_size;
468     sign = 1;
469     x = 0;
470     if (i < 0) {
471         sign = -1;
472         i = -i;
473     }
474     while (--i >= 0) {
475         x = (x << PyLong_SHIFT) | v->ob_digit[i];
476     }
477     return x * sign;
478 }
479 
480 int
_PyLong_Sign(PyObject * vv)481 _PyLong_Sign(PyObject *vv)
482 {
483     PyLongObject *v = (PyLongObject *)vv;
484 
485     assert(v != NULL);
486     assert(PyLong_Check(v));
487 
488     return Py_SIZE(v) == 0 ? 0 : (Py_SIZE(v) < 0 ? -1 : 1);
489 }
490 
491 size_t
_PyLong_NumBits(PyObject * vv)492 _PyLong_NumBits(PyObject *vv)
493 {
494     PyLongObject *v = (PyLongObject *)vv;
495     size_t result = 0;
496     Py_ssize_t ndigits;
497 
498     assert(v != NULL);
499     assert(PyLong_Check(v));
500     ndigits = ABS(Py_SIZE(v));
501     assert(ndigits == 0 || v->ob_digit[ndigits - 1] != 0);
502     if (ndigits > 0) {
503         digit msd = v->ob_digit[ndigits - 1];
504 
505         result = (ndigits - 1) * PyLong_SHIFT;
506         if (result / PyLong_SHIFT != (size_t)(ndigits - 1))
507             goto Overflow;
508         do {
509             ++result;
510             if (result == 0)
511                 goto Overflow;
512             msd >>= 1;
513         } while (msd);
514     }
515     return result;
516 
517   Overflow:
518     PyErr_SetString(PyExc_OverflowError, "long has too many bits "
519                     "to express in a platform size_t");
520     return (size_t)-1;
521 }
522 
523 PyObject *
_PyLong_FromByteArray(const unsigned char * bytes,size_t n,int little_endian,int is_signed)524 _PyLong_FromByteArray(const unsigned char* bytes, size_t n,
525                       int little_endian, int is_signed)
526 {
527     const unsigned char* pstartbyte;    /* LSB of bytes */
528     int incr;                           /* direction to move pstartbyte */
529     const unsigned char* pendbyte;      /* MSB of bytes */
530     size_t numsignificantbytes;         /* number of bytes that matter */
531     Py_ssize_t ndigits;                 /* number of Python long digits */
532     PyLongObject* v;                    /* result */
533     Py_ssize_t idigit = 0;              /* next free index in v->ob_digit */
534 
535     if (n == 0)
536         return PyLong_FromLong(0L);
537 
538     if (little_endian) {
539         pstartbyte = bytes;
540         pendbyte = bytes + n - 1;
541         incr = 1;
542     }
543     else {
544         pstartbyte = bytes + n - 1;
545         pendbyte = bytes;
546         incr = -1;
547     }
548 
549     if (is_signed)
550         is_signed = *pendbyte >= 0x80;
551 
552     /* Compute numsignificantbytes.  This consists of finding the most
553        significant byte.  Leading 0 bytes are insignificant if the number
554        is positive, and leading 0xff bytes if negative. */
555     {
556         size_t i;
557         const unsigned char* p = pendbyte;
558         const int pincr = -incr;  /* search MSB to LSB */
559         const unsigned char insignificant = is_signed ? 0xff : 0x00;
560 
561         for (i = 0; i < n; ++i, p += pincr) {
562             if (*p != insignificant)
563                 break;
564         }
565         numsignificantbytes = n - i;
566         /* 2's-comp is a bit tricky here, e.g. 0xff00 == -0x0100, so
567            actually has 2 significant bytes.  OTOH, 0xff0001 ==
568            -0x00ffff, so we wouldn't *need* to bump it there; but we
569            do for 0xffff = -0x0001.  To be safe without bothering to
570            check every case, bump it regardless. */
571         if (is_signed && numsignificantbytes < n)
572             ++numsignificantbytes;
573     }
574 
575     /* How many Python long digits do we need?  We have
576        8*numsignificantbytes bits, and each Python long digit has
577        PyLong_SHIFT bits, so it's the ceiling of the quotient. */
578     /* catch overflow before it happens */
579     if (numsignificantbytes > (PY_SSIZE_T_MAX - PyLong_SHIFT) / 8) {
580         PyErr_SetString(PyExc_OverflowError,
581                         "byte array too long to convert to int");
582         return NULL;
583     }
584     ndigits = (numsignificantbytes * 8 + PyLong_SHIFT - 1) / PyLong_SHIFT;
585     v = _PyLong_New(ndigits);
586     if (v == NULL)
587         return NULL;
588 
589     /* Copy the bits over.  The tricky parts are computing 2's-comp on
590        the fly for signed numbers, and dealing with the mismatch between
591        8-bit bytes and (probably) 15-bit Python digits.*/
592     {
593         size_t i;
594         twodigits carry = 1;                    /* for 2's-comp calculation */
595         twodigits accum = 0;                    /* sliding register */
596         unsigned int accumbits = 0;             /* number of bits in accum */
597         const unsigned char* p = pstartbyte;
598 
599         for (i = 0; i < numsignificantbytes; ++i, p += incr) {
600             twodigits thisbyte = *p;
601             /* Compute correction for 2's comp, if needed. */
602             if (is_signed) {
603                 thisbyte = (0xff ^ thisbyte) + carry;
604                 carry = thisbyte >> 8;
605                 thisbyte &= 0xff;
606             }
607             /* Because we're going LSB to MSB, thisbyte is
608                more significant than what's already in accum,
609                so needs to be prepended to accum. */
610             accum |= (twodigits)thisbyte << accumbits;
611             accumbits += 8;
612             if (accumbits >= PyLong_SHIFT) {
613                 /* There's enough to fill a Python digit. */
614                 assert(idigit < ndigits);
615                 v->ob_digit[idigit] = (digit)(accum & PyLong_MASK);
616                 ++idigit;
617                 accum >>= PyLong_SHIFT;
618                 accumbits -= PyLong_SHIFT;
619                 assert(accumbits < PyLong_SHIFT);
620             }
621         }
622         assert(accumbits < PyLong_SHIFT);
623         if (accumbits) {
624             assert(idigit < ndigits);
625             v->ob_digit[idigit] = (digit)accum;
626             ++idigit;
627         }
628     }
629 
630     Py_SIZE(v) = is_signed ? -idigit : idigit;
631     return (PyObject *)long_normalize(v);
632 }
633 
634 int
_PyLong_AsByteArray(PyLongObject * v,unsigned char * bytes,size_t n,int little_endian,int is_signed)635 _PyLong_AsByteArray(PyLongObject* v,
636                     unsigned char* bytes, size_t n,
637                     int little_endian, int is_signed)
638 {
639     Py_ssize_t i;               /* index into v->ob_digit */
640     Py_ssize_t ndigits;         /* |v->ob_size| */
641     twodigits accum;            /* sliding register */
642     unsigned int accumbits;     /* # bits in accum */
643     int do_twos_comp;           /* store 2's-comp?  is_signed and v < 0 */
644     digit carry;                /* for computing 2's-comp */
645     size_t j;                   /* # bytes filled */
646     unsigned char* p;           /* pointer to next byte in bytes */
647     int pincr;                  /* direction to move p */
648 
649     assert(v != NULL && PyLong_Check(v));
650 
651     if (Py_SIZE(v) < 0) {
652         ndigits = -(Py_SIZE(v));
653         if (!is_signed) {
654             PyErr_SetString(PyExc_OverflowError,
655                             "can't convert negative long to unsigned");
656             return -1;
657         }
658         do_twos_comp = 1;
659     }
660     else {
661         ndigits = Py_SIZE(v);
662         do_twos_comp = 0;
663     }
664 
665     if (little_endian) {
666         p = bytes;
667         pincr = 1;
668     }
669     else {
670         p = bytes + n - 1;
671         pincr = -1;
672     }
673 
674     /* Copy over all the Python digits.
675        It's crucial that every Python digit except for the MSD contribute
676        exactly PyLong_SHIFT bits to the total, so first assert that the long is
677        normalized. */
678     assert(ndigits == 0 || v->ob_digit[ndigits - 1] != 0);
679     j = 0;
680     accum = 0;
681     accumbits = 0;
682     carry = do_twos_comp ? 1 : 0;
683     for (i = 0; i < ndigits; ++i) {
684         digit thisdigit = v->ob_digit[i];
685         if (do_twos_comp) {
686             thisdigit = (thisdigit ^ PyLong_MASK) + carry;
687             carry = thisdigit >> PyLong_SHIFT;
688             thisdigit &= PyLong_MASK;
689         }
690         /* Because we're going LSB to MSB, thisdigit is more
691            significant than what's already in accum, so needs to be
692            prepended to accum. */
693         accum |= (twodigits)thisdigit << accumbits;
694 
695         /* The most-significant digit may be (probably is) at least
696            partly empty. */
697         if (i == ndigits - 1) {
698             /* Count # of sign bits -- they needn't be stored,
699              * although for signed conversion we need later to
700              * make sure at least one sign bit gets stored. */
701             digit s = do_twos_comp ? thisdigit ^ PyLong_MASK : thisdigit;
702             while (s != 0) {
703                 s >>= 1;
704                 accumbits++;
705             }
706         }
707         else
708             accumbits += PyLong_SHIFT;
709 
710         /* Store as many bytes as possible. */
711         while (accumbits >= 8) {
712             if (j >= n)
713                 goto Overflow;
714             ++j;
715             *p = (unsigned char)(accum & 0xff);
716             p += pincr;
717             accumbits -= 8;
718             accum >>= 8;
719         }
720     }
721 
722     /* Store the straggler (if any). */
723     assert(accumbits < 8);
724     assert(carry == 0);  /* else do_twos_comp and *every* digit was 0 */
725     if (accumbits > 0) {
726         if (j >= n)
727             goto Overflow;
728         ++j;
729         if (do_twos_comp) {
730             /* Fill leading bits of the byte with sign bits
731                (appropriately pretending that the long had an
732                infinite supply of sign bits). */
733             accum |= (~(twodigits)0) << accumbits;
734         }
735         *p = (unsigned char)(accum & 0xff);
736         p += pincr;
737     }
738     else if (j == n && n > 0 && is_signed) {
739         /* The main loop filled the byte array exactly, so the code
740            just above didn't get to ensure there's a sign bit, and the
741            loop below wouldn't add one either.  Make sure a sign bit
742            exists. */
743         unsigned char msb = *(p - pincr);
744         int sign_bit_set = msb >= 0x80;
745         assert(accumbits == 0);
746         if (sign_bit_set == do_twos_comp)
747             return 0;
748         else
749             goto Overflow;
750     }
751 
752     /* Fill remaining bytes with copies of the sign bit. */
753     {
754         unsigned char signbyte = do_twos_comp ? 0xffU : 0U;
755         for ( ; j < n; ++j, p += pincr)
756             *p = signbyte;
757     }
758 
759     return 0;
760 
761   Overflow:
762     PyErr_SetString(PyExc_OverflowError, "long too big to convert");
763     return -1;
764 
765 }
766 
767 /* Create a new long (or int) object from a C pointer */
768 
769 PyObject *
PyLong_FromVoidPtr(void * p)770 PyLong_FromVoidPtr(void *p)
771 {
772 #if SIZEOF_VOID_P <= SIZEOF_LONG
773     if ((long)p < 0)
774         return PyLong_FromUnsignedLong((unsigned long)p);
775     return PyInt_FromLong((long)p);
776 #else
777 
778 #ifndef HAVE_LONG_LONG
779 #   error "PyLong_FromVoidPtr: sizeof(void*) > sizeof(long), but no long long"
780 #endif
781 #if SIZEOF_LONG_LONG < SIZEOF_VOID_P
782 #   error "PyLong_FromVoidPtr: sizeof(PY_LONG_LONG) < sizeof(void*)"
783 #endif
784     /* optimize null pointers */
785     if (p == NULL)
786         return PyInt_FromLong(0);
787     return PyLong_FromUnsignedLongLong((unsigned PY_LONG_LONG)p);
788 
789 #endif /* SIZEOF_VOID_P <= SIZEOF_LONG */
790 }
791 
792 /* Get a C pointer from a long object (or an int object in some cases) */
793 
794 void *
PyLong_AsVoidPtr(PyObject * vv)795 PyLong_AsVoidPtr(PyObject *vv)
796 {
797     /* This function will allow int or long objects. If vv is neither,
798        then the PyLong_AsLong*() functions will raise the exception:
799        PyExc_SystemError, "bad argument to internal function"
800     */
801 #if SIZEOF_VOID_P <= SIZEOF_LONG
802     long x;
803 
804     if (PyInt_Check(vv))
805         x = PyInt_AS_LONG(vv);
806     else if (PyLong_Check(vv) && _PyLong_Sign(vv) < 0)
807         x = PyLong_AsLong(vv);
808     else
809         x = PyLong_AsUnsignedLong(vv);
810 #else
811 
812 #ifndef HAVE_LONG_LONG
813 #   error "PyLong_AsVoidPtr: sizeof(void*) > sizeof(long), but no long long"
814 #endif
815 #if SIZEOF_LONG_LONG < SIZEOF_VOID_P
816 #   error "PyLong_AsVoidPtr: sizeof(PY_LONG_LONG) < sizeof(void*)"
817 #endif
818     PY_LONG_LONG x;
819 
820     if (PyInt_Check(vv))
821         x = PyInt_AS_LONG(vv);
822     else if (PyLong_Check(vv) && _PyLong_Sign(vv) < 0)
823         x = PyLong_AsLongLong(vv);
824     else
825         x = PyLong_AsUnsignedLongLong(vv);
826 
827 #endif /* SIZEOF_VOID_P <= SIZEOF_LONG */
828 
829     if (x == -1 && PyErr_Occurred())
830         return NULL;
831     return (void *)x;
832 }
833 
834 #ifdef HAVE_LONG_LONG
835 
836 /* Initial PY_LONG_LONG support by Chris Herborth (chrish@qnx.com), later
837  * rewritten to use the newer PyLong_{As,From}ByteArray API.
838  */
839 
840 #define IS_LITTLE_ENDIAN (int)*(unsigned char*)&one
841 #define PY_ABS_LLONG_MIN (0-(unsigned PY_LONG_LONG)PY_LLONG_MIN)
842 
843 /* Create a new long int object from a C PY_LONG_LONG int. */
844 
845 PyObject *
PyLong_FromLongLong(PY_LONG_LONG ival)846 PyLong_FromLongLong(PY_LONG_LONG ival)
847 {
848     PyLongObject *v;
849     unsigned PY_LONG_LONG abs_ival;
850     unsigned PY_LONG_LONG t;  /* unsigned so >> doesn't propagate sign bit */
851     int ndigits = 0;
852     int negative = 0;
853 
854     if (ival < 0) {
855         /* avoid signed overflow on negation;  see comments
856            in PyLong_FromLong above. */
857         abs_ival = (unsigned PY_LONG_LONG)(-1-ival) + 1;
858         negative = 1;
859     }
860     else {
861         abs_ival = (unsigned PY_LONG_LONG)ival;
862     }
863 
864     /* Count the number of Python digits.
865        We used to pick 5 ("big enough for anything"), but that's a
866        waste of time and space given that 5*15 = 75 bits are rarely
867        needed. */
868     t = abs_ival;
869     while (t) {
870         ++ndigits;
871         t >>= PyLong_SHIFT;
872     }
873     v = _PyLong_New(ndigits);
874     if (v != NULL) {
875         digit *p = v->ob_digit;
876         Py_SIZE(v) = negative ? -ndigits : ndigits;
877         t = abs_ival;
878         while (t) {
879             *p++ = (digit)(t & PyLong_MASK);
880             t >>= PyLong_SHIFT;
881         }
882     }
883     return (PyObject *)v;
884 }
885 
886 /* Create a new long int object from a C unsigned PY_LONG_LONG int. */
887 
888 PyObject *
PyLong_FromUnsignedLongLong(unsigned PY_LONG_LONG ival)889 PyLong_FromUnsignedLongLong(unsigned PY_LONG_LONG ival)
890 {
891     PyLongObject *v;
892     unsigned PY_LONG_LONG t;
893     int ndigits = 0;
894 
895     /* Count the number of Python digits. */
896     t = (unsigned PY_LONG_LONG)ival;
897     while (t) {
898         ++ndigits;
899         t >>= PyLong_SHIFT;
900     }
901     v = _PyLong_New(ndigits);
902     if (v != NULL) {
903         digit *p = v->ob_digit;
904         Py_SIZE(v) = ndigits;
905         while (ival) {
906             *p++ = (digit)(ival & PyLong_MASK);
907             ival >>= PyLong_SHIFT;
908         }
909     }
910     return (PyObject *)v;
911 }
912 
913 /* Create a new long int object from a C Py_ssize_t. */
914 
915 PyObject *
PyLong_FromSsize_t(Py_ssize_t ival)916 PyLong_FromSsize_t(Py_ssize_t ival)
917 {
918     Py_ssize_t bytes = ival;
919     int one = 1;
920     return _PyLong_FromByteArray((unsigned char *)&bytes,
921                                  SIZEOF_SIZE_T, IS_LITTLE_ENDIAN, 1);
922 }
923 
924 /* Create a new long int object from a C size_t. */
925 
926 PyObject *
PyLong_FromSize_t(size_t ival)927 PyLong_FromSize_t(size_t ival)
928 {
929     size_t bytes = ival;
930     int one = 1;
931     return _PyLong_FromByteArray((unsigned char *)&bytes,
932                                  SIZEOF_SIZE_T, IS_LITTLE_ENDIAN, 0);
933 }
934 
935 /* Get a C PY_LONG_LONG int from a long int object.
936    Return -1 and set an error if overflow occurs. */
937 
938 PY_LONG_LONG
PyLong_AsLongLong(PyObject * vv)939 PyLong_AsLongLong(PyObject *vv)
940 {
941     PY_LONG_LONG bytes;
942     int one = 1;
943     int res;
944 
945     if (vv == NULL) {
946         PyErr_BadInternalCall();
947         return -1;
948     }
949     if (!PyLong_Check(vv)) {
950         PyNumberMethods *nb;
951         PyObject *io;
952         if (PyInt_Check(vv))
953             return (PY_LONG_LONG)PyInt_AsLong(vv);
954         if ((nb = vv->ob_type->tp_as_number) == NULL ||
955             nb->nb_int == NULL) {
956             PyErr_SetString(PyExc_TypeError, "an integer is required");
957             return -1;
958         }
959         io = (*nb->nb_int) (vv);
960         if (io == NULL)
961             return -1;
962         if (PyInt_Check(io)) {
963             bytes = PyInt_AsLong(io);
964             Py_DECREF(io);
965             return bytes;
966         }
967         if (PyLong_Check(io)) {
968             bytes = PyLong_AsLongLong(io);
969             Py_DECREF(io);
970             return bytes;
971         }
972         Py_DECREF(io);
973         PyErr_SetString(PyExc_TypeError, "integer conversion failed");
974         return -1;
975     }
976 
977     res = _PyLong_AsByteArray((PyLongObject *)vv, (unsigned char *)&bytes,
978                               SIZEOF_LONG_LONG, IS_LITTLE_ENDIAN, 1);
979 
980     /* Plan 9 can't handle PY_LONG_LONG in ? : expressions */
981     if (res < 0)
982         return (PY_LONG_LONG)-1;
983     else
984         return bytes;
985 }
986 
987 /* Get a C unsigned PY_LONG_LONG int from a long int object.
988    Return -1 and set an error if overflow occurs. */
989 
990 unsigned PY_LONG_LONG
PyLong_AsUnsignedLongLong(PyObject * vv)991 PyLong_AsUnsignedLongLong(PyObject *vv)
992 {
993     unsigned PY_LONG_LONG bytes;
994     int one = 1;
995     int res;
996 
997     if (vv == NULL || !PyLong_Check(vv)) {
998         PyErr_BadInternalCall();
999         return (unsigned PY_LONG_LONG)-1;
1000     }
1001 
1002     res = _PyLong_AsByteArray((PyLongObject *)vv, (unsigned char *)&bytes,
1003                               SIZEOF_LONG_LONG, IS_LITTLE_ENDIAN, 0);
1004 
1005     /* Plan 9 can't handle PY_LONG_LONG in ? : expressions */
1006     if (res < 0)
1007         return (unsigned PY_LONG_LONG)res;
1008     else
1009         return bytes;
1010 }
1011 
1012 /* Get a C unsigned long int from a long int object, ignoring the high bits.
1013    Returns -1 and sets an error condition if an error occurs. */
1014 
1015 unsigned PY_LONG_LONG
PyLong_AsUnsignedLongLongMask(PyObject * vv)1016 PyLong_AsUnsignedLongLongMask(PyObject *vv)
1017 {
1018     register PyLongObject *v;
1019     unsigned PY_LONG_LONG x;
1020     Py_ssize_t i;
1021     int sign;
1022 
1023     if (vv == NULL || !PyLong_Check(vv)) {
1024         PyErr_BadInternalCall();
1025         return (unsigned long) -1;
1026     }
1027     v = (PyLongObject *)vv;
1028     i = v->ob_size;
1029     sign = 1;
1030     x = 0;
1031     if (i < 0) {
1032         sign = -1;
1033         i = -i;
1034     }
1035     while (--i >= 0) {
1036         x = (x << PyLong_SHIFT) | v->ob_digit[i];
1037     }
1038     return x * sign;
1039 }
1040 
1041 /* Get a C long long int from a Python long or Python int object.
1042    On overflow, returns -1 and sets *overflow to 1 or -1 depending
1043    on the sign of the result.  Otherwise *overflow is 0.
1044 
1045    For other errors (e.g., type error), returns -1 and sets an error
1046    condition.
1047 */
1048 
1049 PY_LONG_LONG
PyLong_AsLongLongAndOverflow(PyObject * vv,int * overflow)1050 PyLong_AsLongLongAndOverflow(PyObject *vv, int *overflow)
1051 {
1052     /* This version by Tim Peters */
1053     register PyLongObject *v;
1054     unsigned PY_LONG_LONG x, prev;
1055     PY_LONG_LONG res;
1056     Py_ssize_t i;
1057     int sign;
1058     int do_decref = 0; /* if nb_int was called */
1059 
1060     *overflow = 0;
1061     if (vv == NULL) {
1062         PyErr_BadInternalCall();
1063         return -1;
1064     }
1065 
1066     if (PyInt_Check(vv))
1067         return PyInt_AsLong(vv);
1068 
1069     if (!PyLong_Check(vv)) {
1070         PyNumberMethods *nb;
1071         nb = vv->ob_type->tp_as_number;
1072         if (nb == NULL || nb->nb_int == NULL) {
1073             PyErr_SetString(PyExc_TypeError,
1074                             "an integer is required");
1075             return -1;
1076         }
1077         vv = (*nb->nb_int) (vv);
1078         if (vv == NULL)
1079             return -1;
1080         do_decref = 1;
1081         if(PyInt_Check(vv)) {
1082             res = PyInt_AsLong(vv);
1083             goto exit;
1084         }
1085         if (!PyLong_Check(vv)) {
1086             Py_DECREF(vv);
1087             PyErr_SetString(PyExc_TypeError,
1088                             "nb_int should return int object");
1089             return -1;
1090         }
1091     }
1092 
1093     res = -1;
1094     v = (PyLongObject *)vv;
1095     i = Py_SIZE(v);
1096 
1097     switch (i) {
1098     case -1:
1099         res = -(sdigit)v->ob_digit[0];
1100         break;
1101     case 0:
1102         res = 0;
1103         break;
1104     case 1:
1105         res = v->ob_digit[0];
1106         break;
1107     default:
1108         sign = 1;
1109         x = 0;
1110         if (i < 0) {
1111             sign = -1;
1112             i = -(i);
1113         }
1114         while (--i >= 0) {
1115             prev = x;
1116             x = (x << PyLong_SHIFT) + v->ob_digit[i];
1117             if ((x >> PyLong_SHIFT) != prev) {
1118                 *overflow = sign;
1119                 goto exit;
1120             }
1121         }
1122         /* Haven't lost any bits, but casting to long requires extra
1123          * care (see comment above).
1124          */
1125         if (x <= (unsigned PY_LONG_LONG)PY_LLONG_MAX) {
1126             res = (PY_LONG_LONG)x * sign;
1127         }
1128         else if (sign < 0 && x == PY_ABS_LLONG_MIN) {
1129             res = PY_LLONG_MIN;
1130         }
1131         else {
1132             *overflow = sign;
1133             /* res is already set to -1 */
1134         }
1135     }
1136   exit:
1137     if (do_decref) {
1138         Py_DECREF(vv);
1139     }
1140     return res;
1141 }
1142 
1143 #undef IS_LITTLE_ENDIAN
1144 
1145 #endif /* HAVE_LONG_LONG */
1146 
1147 
1148 static int
convert_binop(PyObject * v,PyObject * w,PyLongObject ** a,PyLongObject ** b)1149 convert_binop(PyObject *v, PyObject *w, PyLongObject **a, PyLongObject **b) {
1150     if (PyLong_Check(v)) {
1151         *a = (PyLongObject *) v;
1152         Py_INCREF(v);
1153     }
1154     else if (PyInt_Check(v)) {
1155         *a = (PyLongObject *) PyLong_FromLong(PyInt_AS_LONG(v));
1156     }
1157     else {
1158         return 0;
1159     }
1160     if (PyLong_Check(w)) {
1161         *b = (PyLongObject *) w;
1162         Py_INCREF(w);
1163     }
1164     else if (PyInt_Check(w)) {
1165         *b = (PyLongObject *) PyLong_FromLong(PyInt_AS_LONG(w));
1166     }
1167     else {
1168         Py_DECREF(*a);
1169         return 0;
1170     }
1171     return 1;
1172 }
1173 
1174 #define CONVERT_BINOP(v, w, a, b)               \
1175     do {                                        \
1176         if (!convert_binop(v, w, a, b)) {       \
1177             Py_INCREF(Py_NotImplemented);       \
1178             return Py_NotImplemented;           \
1179         }                                       \
1180     } while(0)                                  \
1181 
1182 /* bits_in_digit(d) returns the unique integer k such that 2**(k-1) <= d <
1183    2**k if d is nonzero, else 0. */
1184 
1185 static const unsigned char BitLengthTable[32] = {
1186     0, 1, 2, 2, 3, 3, 3, 3, 4, 4, 4, 4, 4, 4, 4, 4,
1187     5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5
1188 };
1189 
1190 static int
bits_in_digit(digit d)1191 bits_in_digit(digit d)
1192 {
1193     int d_bits = 0;
1194     while (d >= 32) {
1195         d_bits += 6;
1196         d >>= 6;
1197     }
1198     d_bits += (int)BitLengthTable[d];
1199     return d_bits;
1200 }
1201 
1202 /* x[0:m] and y[0:n] are digit vectors, LSD first, m >= n required.  x[0:n]
1203  * is modified in place, by adding y to it.  Carries are propagated as far as
1204  * x[m-1], and the remaining carry (0 or 1) is returned.
1205  */
1206 static digit
v_iadd(digit * x,Py_ssize_t m,digit * y,Py_ssize_t n)1207 v_iadd(digit *x, Py_ssize_t m, digit *y, Py_ssize_t n)
1208 {
1209     Py_ssize_t i;
1210     digit carry = 0;
1211 
1212     assert(m >= n);
1213     for (i = 0; i < n; ++i) {
1214         carry += x[i] + y[i];
1215         x[i] = carry & PyLong_MASK;
1216         carry >>= PyLong_SHIFT;
1217         assert((carry & 1) == carry);
1218     }
1219     for (; carry && i < m; ++i) {
1220         carry += x[i];
1221         x[i] = carry & PyLong_MASK;
1222         carry >>= PyLong_SHIFT;
1223         assert((carry & 1) == carry);
1224     }
1225     return carry;
1226 }
1227 
1228 /* x[0:m] and y[0:n] are digit vectors, LSD first, m >= n required.  x[0:n]
1229  * is modified in place, by subtracting y from it.  Borrows are propagated as
1230  * far as x[m-1], and the remaining borrow (0 or 1) is returned.
1231  */
1232 static digit
v_isub(digit * x,Py_ssize_t m,digit * y,Py_ssize_t n)1233 v_isub(digit *x, Py_ssize_t m, digit *y, Py_ssize_t n)
1234 {
1235     Py_ssize_t i;
1236     digit borrow = 0;
1237 
1238     assert(m >= n);
1239     for (i = 0; i < n; ++i) {
1240         borrow = x[i] - y[i] - borrow;
1241         x[i] = borrow & PyLong_MASK;
1242         borrow >>= PyLong_SHIFT;
1243         borrow &= 1;            /* keep only 1 sign bit */
1244     }
1245     for (; borrow && i < m; ++i) {
1246         borrow = x[i] - borrow;
1247         x[i] = borrow & PyLong_MASK;
1248         borrow >>= PyLong_SHIFT;
1249         borrow &= 1;
1250     }
1251     return borrow;
1252 }
1253 
1254 /* Shift digit vector a[0:m] d bits left, with 0 <= d < PyLong_SHIFT.  Put
1255  * result in z[0:m], and return the d bits shifted out of the top.
1256  */
1257 static digit
v_lshift(digit * z,digit * a,Py_ssize_t m,int d)1258 v_lshift(digit *z, digit *a, Py_ssize_t m, int d)
1259 {
1260     Py_ssize_t i;
1261     digit carry = 0;
1262 
1263     assert(0 <= d && d < PyLong_SHIFT);
1264     for (i=0; i < m; i++) {
1265         twodigits acc = (twodigits)a[i] << d | carry;
1266         z[i] = (digit)acc & PyLong_MASK;
1267         carry = (digit)(acc >> PyLong_SHIFT);
1268     }
1269     return carry;
1270 }
1271 
1272 /* Shift digit vector a[0:m] d bits right, with 0 <= d < PyLong_SHIFT.  Put
1273  * result in z[0:m], and return the d bits shifted out of the bottom.
1274  */
1275 static digit
v_rshift(digit * z,digit * a,Py_ssize_t m,int d)1276 v_rshift(digit *z, digit *a, Py_ssize_t m, int d)
1277 {
1278     Py_ssize_t i;
1279     digit carry = 0;
1280     digit mask = ((digit)1 << d) - 1U;
1281 
1282     assert(0 <= d && d < PyLong_SHIFT);
1283     for (i=m; i-- > 0;) {
1284         twodigits acc = (twodigits)carry << PyLong_SHIFT | a[i];
1285         carry = (digit)acc & mask;
1286         z[i] = (digit)(acc >> d);
1287     }
1288     return carry;
1289 }
1290 
1291 /* Divide long pin, w/ size digits, by non-zero digit n, storing quotient
1292    in pout, and returning the remainder.  pin and pout point at the LSD.
1293    It's OK for pin == pout on entry, which saves oodles of mallocs/frees in
1294    _PyLong_Format, but that should be done with great care since longs are
1295    immutable. */
1296 
1297 static digit
inplace_divrem1(digit * pout,digit * pin,Py_ssize_t size,digit n)1298 inplace_divrem1(digit *pout, digit *pin, Py_ssize_t size, digit n)
1299 {
1300     twodigits rem = 0;
1301 
1302     assert(n > 0 && n <= PyLong_MASK);
1303     pin += size;
1304     pout += size;
1305     while (--size >= 0) {
1306         digit hi;
1307         rem = (rem << PyLong_SHIFT) | *--pin;
1308         *--pout = hi = (digit)(rem / n);
1309         rem -= (twodigits)hi * n;
1310     }
1311     return (digit)rem;
1312 }
1313 
1314 /* Divide a long integer by a digit, returning both the quotient
1315    (as function result) and the remainder (through *prem).
1316    The sign of a is ignored; n should not be zero. */
1317 
1318 static PyLongObject *
divrem1(PyLongObject * a,digit n,digit * prem)1319 divrem1(PyLongObject *a, digit n, digit *prem)
1320 {
1321     const Py_ssize_t size = ABS(Py_SIZE(a));
1322     PyLongObject *z;
1323 
1324     assert(n > 0 && n <= PyLong_MASK);
1325     z = _PyLong_New(size);
1326     if (z == NULL)
1327         return NULL;
1328     *prem = inplace_divrem1(z->ob_digit, a->ob_digit, size, n);
1329     return long_normalize(z);
1330 }
1331 
1332 /* Convert a long integer to a base 10 string.  Returns a new non-shared
1333    string.  (Return value is non-shared so that callers can modify the
1334    returned value if necessary.) */
1335 
1336 static PyObject *
long_to_decimal_string(PyObject * aa,int addL)1337 long_to_decimal_string(PyObject *aa, int addL)
1338 {
1339     PyLongObject *scratch, *a;
1340     PyObject *str;
1341     Py_ssize_t size, strlen, size_a, i, j;
1342     digit *pout, *pin, rem, tenpow;
1343     char *p;
1344     int negative;
1345 
1346     a = (PyLongObject *)aa;
1347     if (a == NULL || !PyLong_Check(a)) {
1348         PyErr_BadInternalCall();
1349         return NULL;
1350     }
1351     size_a = ABS(Py_SIZE(a));
1352     negative = Py_SIZE(a) < 0;
1353 
1354     /* quick and dirty upper bound for the number of digits
1355        required to express a in base _PyLong_DECIMAL_BASE:
1356 
1357          #digits = 1 + floor(log2(a) / log2(_PyLong_DECIMAL_BASE))
1358 
1359        But log2(a) < size_a * PyLong_SHIFT, and
1360        log2(_PyLong_DECIMAL_BASE) = log2(10) * _PyLong_DECIMAL_SHIFT
1361                                   > 3 * _PyLong_DECIMAL_SHIFT
1362     */
1363     if (size_a > PY_SSIZE_T_MAX / PyLong_SHIFT) {
1364         PyErr_SetString(PyExc_OverflowError,
1365                         "long is too large to format");
1366         return NULL;
1367     }
1368     /* the expression size_a * PyLong_SHIFT is now safe from overflow */
1369     size = 1 + size_a * PyLong_SHIFT / (3 * _PyLong_DECIMAL_SHIFT);
1370     scratch = _PyLong_New(size);
1371     if (scratch == NULL)
1372         return NULL;
1373 
1374     /* convert array of base _PyLong_BASE digits in pin to an array of
1375        base _PyLong_DECIMAL_BASE digits in pout, following Knuth (TAOCP,
1376        Volume 2 (3rd edn), section 4.4, Method 1b). */
1377     pin = a->ob_digit;
1378     pout = scratch->ob_digit;
1379     size = 0;
1380     for (i = size_a; --i >= 0; ) {
1381         digit hi = pin[i];
1382         for (j = 0; j < size; j++) {
1383             twodigits z = (twodigits)pout[j] << PyLong_SHIFT | hi;
1384             hi = (digit)(z / _PyLong_DECIMAL_BASE);
1385             pout[j] = (digit)(z - (twodigits)hi *
1386                               _PyLong_DECIMAL_BASE);
1387         }
1388         while (hi) {
1389             pout[size++] = hi % _PyLong_DECIMAL_BASE;
1390             hi /= _PyLong_DECIMAL_BASE;
1391         }
1392         /* check for keyboard interrupt */
1393         SIGCHECK({
1394                 Py_DECREF(scratch);
1395                 return NULL;
1396             });
1397     }
1398     /* pout should have at least one digit, so that the case when a = 0
1399        works correctly */
1400     if (size == 0)
1401         pout[size++] = 0;
1402 
1403     /* calculate exact length of output string, and allocate */
1404     strlen = (addL != 0) + negative +
1405         1 + (size - 1) * _PyLong_DECIMAL_SHIFT;
1406     tenpow = 10;
1407     rem = pout[size-1];
1408     while (rem >= tenpow) {
1409         tenpow *= 10;
1410         strlen++;
1411     }
1412     str = PyString_FromStringAndSize(NULL, strlen);
1413     if (str == NULL) {
1414         Py_DECREF(scratch);
1415         return NULL;
1416     }
1417 
1418     /* fill the string right-to-left */
1419     p = PyString_AS_STRING(str) + strlen;
1420     *p = '\0';
1421     if (addL)
1422         *--p = 'L';
1423     /* pout[0] through pout[size-2] contribute exactly
1424        _PyLong_DECIMAL_SHIFT digits each */
1425     for (i=0; i < size - 1; i++) {
1426         rem = pout[i];
1427         for (j = 0; j < _PyLong_DECIMAL_SHIFT; j++) {
1428             *--p = '0' + rem % 10;
1429             rem /= 10;
1430         }
1431     }
1432     /* pout[size-1]: always produce at least one decimal digit */
1433     rem = pout[i];
1434     do {
1435         *--p = '0' + rem % 10;
1436         rem /= 10;
1437     } while (rem != 0);
1438 
1439     /* and sign */
1440     if (negative)
1441         *--p = '-';
1442 
1443     /* check we've counted correctly */
1444     assert(p == PyString_AS_STRING(str));
1445     Py_DECREF(scratch);
1446     return (PyObject *)str;
1447 }
1448 
1449 /* Convert the long to a string object with given base,
1450    appending a base prefix of 0[box] if base is 2, 8 or 16.
1451    Add a trailing "L" if addL is non-zero.
1452    If newstyle is zero, then use the pre-2.6 behavior of octal having
1453    a leading "0", instead of the prefix "0o" */
1454 PyAPI_FUNC(PyObject *)
_PyLong_Format(PyObject * aa,int base,int addL,int newstyle)1455 _PyLong_Format(PyObject *aa, int base, int addL, int newstyle)
1456 {
1457     register PyLongObject *a = (PyLongObject *)aa;
1458     PyStringObject *str;
1459     Py_ssize_t i, sz;
1460     Py_ssize_t size_a;
1461     char *p;
1462     int bits;
1463     char sign = '\0';
1464 
1465     if (base == 10)
1466         return long_to_decimal_string((PyObject *)a, addL);
1467 
1468     if (a == NULL || !PyLong_Check(a)) {
1469         PyErr_BadInternalCall();
1470         return NULL;
1471     }
1472     assert(base >= 2 && base <= 36);
1473     size_a = ABS(Py_SIZE(a));
1474 
1475     /* Compute a rough upper bound for the length of the string */
1476     i = base;
1477     bits = 0;
1478     while (i > 1) {
1479         ++bits;
1480         i >>= 1;
1481     }
1482     i = 5 + (addL ? 1 : 0);
1483     /* ensure we don't get signed overflow in sz calculation */
1484     if (size_a > (PY_SSIZE_T_MAX - i) / PyLong_SHIFT) {
1485         PyErr_SetString(PyExc_OverflowError,
1486                         "long is too large to format");
1487         return NULL;
1488     }
1489     sz = i + 1 + (size_a * PyLong_SHIFT - 1) / bits;
1490     assert(sz >= 0);
1491     str = (PyStringObject *) PyString_FromStringAndSize((char *)0, sz);
1492     if (str == NULL)
1493         return NULL;
1494     p = PyString_AS_STRING(str) + sz;
1495     *p = '\0';
1496     if (addL)
1497         *--p = 'L';
1498     if (a->ob_size < 0)
1499         sign = '-';
1500 
1501     if (a->ob_size == 0) {
1502         *--p = '0';
1503     }
1504     else if ((base & (base - 1)) == 0) {
1505         /* JRH: special case for power-of-2 bases */
1506         twodigits accum = 0;
1507         int accumbits = 0;              /* # of bits in accum */
1508         int basebits = 1;               /* # of bits in base-1 */
1509         i = base;
1510         while ((i >>= 1) > 1)
1511             ++basebits;
1512 
1513         for (i = 0; i < size_a; ++i) {
1514             accum |= (twodigits)a->ob_digit[i] << accumbits;
1515             accumbits += PyLong_SHIFT;
1516             assert(accumbits >= basebits);
1517             do {
1518                 char cdigit = (char)(accum & (base - 1));
1519                 cdigit += (cdigit < 10) ? '0' : 'a'-10;
1520                 assert(p > PyString_AS_STRING(str));
1521                 *--p = cdigit;
1522                 accumbits -= basebits;
1523                 accum >>= basebits;
1524             } while (i < size_a-1 ? accumbits >= basebits : accum > 0);
1525         }
1526     }
1527     else {
1528         /* Not 0, and base not a power of 2.  Divide repeatedly by
1529            base, but for speed use the highest power of base that
1530            fits in a digit. */
1531         Py_ssize_t size = size_a;
1532         digit *pin = a->ob_digit;
1533         PyLongObject *scratch;
1534         /* powbasw <- largest power of base that fits in a digit. */
1535         digit powbase = base;  /* powbase == base ** power */
1536         int power = 1;
1537         for (;;) {
1538             twodigits newpow = powbase * (twodigits)base;
1539             if (newpow >> PyLong_SHIFT)
1540                 /* doesn't fit in a digit */
1541                 break;
1542             powbase = (digit)newpow;
1543             ++power;
1544         }
1545 
1546         /* Get a scratch area for repeated division. */
1547         scratch = _PyLong_New(size);
1548         if (scratch == NULL) {
1549             Py_DECREF(str);
1550             return NULL;
1551         }
1552 
1553         /* Repeatedly divide by powbase. */
1554         do {
1555             int ntostore = power;
1556             digit rem = inplace_divrem1(scratch->ob_digit,
1557                                         pin, size, powbase);
1558             pin = scratch->ob_digit; /* no need to use a again */
1559             if (pin[size - 1] == 0)
1560                 --size;
1561             SIGCHECK({
1562                     Py_DECREF(scratch);
1563                     Py_DECREF(str);
1564                     return NULL;
1565                 });
1566 
1567             /* Break rem into digits. */
1568             assert(ntostore > 0);
1569             do {
1570                 digit nextrem = (digit)(rem / base);
1571                 char c = (char)(rem - nextrem * base);
1572                 assert(p > PyString_AS_STRING(str));
1573                 c += (c < 10) ? '0' : 'a'-10;
1574                 *--p = c;
1575                 rem = nextrem;
1576                 --ntostore;
1577                 /* Termination is a bit delicate:  must not
1578                    store leading zeroes, so must get out if
1579                    remaining quotient and rem are both 0. */
1580             } while (ntostore && (size || rem));
1581         } while (size != 0);
1582         Py_DECREF(scratch);
1583     }
1584 
1585     if (base == 2) {
1586         *--p = 'b';
1587         *--p = '0';
1588     }
1589     else if (base == 8) {
1590         if (newstyle) {
1591             *--p = 'o';
1592             *--p = '0';
1593         }
1594         else
1595             if (size_a != 0)
1596                 *--p = '0';
1597     }
1598     else if (base == 16) {
1599         *--p = 'x';
1600         *--p = '0';
1601     }
1602     else if (base != 10) {
1603         *--p = '#';
1604         *--p = '0' + base%10;
1605         if (base > 10)
1606             *--p = '0' + base/10;
1607     }
1608     if (sign)
1609         *--p = sign;
1610     if (p != PyString_AS_STRING(str)) {
1611         char *q = PyString_AS_STRING(str);
1612         assert(p > q);
1613         do {
1614         } while ((*q++ = *p++) != '\0');
1615         q--;
1616         _PyString_Resize((PyObject **)&str,
1617                          (Py_ssize_t) (q - PyString_AS_STRING(str)));
1618     }
1619     return (PyObject *)str;
1620 }
1621 
1622 /* Table of digit values for 8-bit string -> integer conversion.
1623  * '0' maps to 0, ..., '9' maps to 9.
1624  * 'a' and 'A' map to 10, ..., 'z' and 'Z' map to 35.
1625  * All other indices map to 37.
1626  * Note that when converting a base B string, a char c is a legitimate
1627  * base B digit iff _PyLong_DigitValue[Py_CHARMASK(c)] < B.
1628  */
1629 int _PyLong_DigitValue[256] = {
1630     37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37,
1631     37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37,
1632     37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37,
1633     0,  1,  2,  3,  4,  5,  6,  7,  8,  9,  37, 37, 37, 37, 37, 37,
1634     37, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24,
1635     25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 37, 37, 37, 37, 37,
1636     37, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24,
1637     25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 37, 37, 37, 37, 37,
1638     37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37,
1639     37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37,
1640     37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37,
1641     37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37,
1642     37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37,
1643     37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37,
1644     37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37,
1645     37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37,
1646 };
1647 
1648 /* *str points to the first digit in a string of base `base` digits.  base
1649  * is a power of 2 (2, 4, 8, 16, or 32).  *str is set to point to the first
1650  * non-digit (which may be *str!).  A normalized long is returned.
1651  * The point to this routine is that it takes time linear in the number of
1652  * string characters.
1653  */
1654 static PyLongObject *
long_from_binary_base(char ** str,int base)1655 long_from_binary_base(char **str, int base)
1656 {
1657     char *p = *str;
1658     char *start = p;
1659     int bits_per_char;
1660     Py_ssize_t n;
1661     PyLongObject *z;
1662     twodigits accum;
1663     int bits_in_accum;
1664     digit *pdigit;
1665 
1666     assert(base >= 2 && base <= 32 && (base & (base - 1)) == 0);
1667     n = base;
1668     for (bits_per_char = -1; n; ++bits_per_char)
1669         n >>= 1;
1670     /* n <- total # of bits needed, while setting p to end-of-string */
1671     while (_PyLong_DigitValue[Py_CHARMASK(*p)] < base)
1672         ++p;
1673     *str = p;
1674     /* n <- # of Python digits needed, = ceiling(n/PyLong_SHIFT). */
1675     n = (p - start) * bits_per_char + PyLong_SHIFT - 1;
1676     if (n / bits_per_char < p - start) {
1677         PyErr_SetString(PyExc_ValueError,
1678                         "long string too large to convert");
1679         return NULL;
1680     }
1681     n = n / PyLong_SHIFT;
1682     z = _PyLong_New(n);
1683     if (z == NULL)
1684         return NULL;
1685     /* Read string from right, and fill in long from left; i.e.,
1686      * from least to most significant in both.
1687      */
1688     accum = 0;
1689     bits_in_accum = 0;
1690     pdigit = z->ob_digit;
1691     while (--p >= start) {
1692         int k = _PyLong_DigitValue[Py_CHARMASK(*p)];
1693         assert(k >= 0 && k < base);
1694         accum |= (twodigits)k << bits_in_accum;
1695         bits_in_accum += bits_per_char;
1696         if (bits_in_accum >= PyLong_SHIFT) {
1697             *pdigit++ = (digit)(accum & PyLong_MASK);
1698             assert(pdigit - z->ob_digit <= n);
1699             accum >>= PyLong_SHIFT;
1700             bits_in_accum -= PyLong_SHIFT;
1701             assert(bits_in_accum < PyLong_SHIFT);
1702         }
1703     }
1704     if (bits_in_accum) {
1705         assert(bits_in_accum <= PyLong_SHIFT);
1706         *pdigit++ = (digit)accum;
1707         assert(pdigit - z->ob_digit <= n);
1708     }
1709     while (pdigit - z->ob_digit < n)
1710         *pdigit++ = 0;
1711     return long_normalize(z);
1712 }
1713 
1714 PyObject *
PyLong_FromString(char * str,char ** pend,int base)1715 PyLong_FromString(char *str, char **pend, int base)
1716 {
1717     int sign = 1;
1718     char *start, *orig_str = str;
1719     PyLongObject *z;
1720     PyObject *strobj, *strrepr;
1721     Py_ssize_t slen;
1722 
1723     if ((base != 0 && base < 2) || base > 36) {
1724         PyErr_SetString(PyExc_ValueError,
1725                         "long() arg 2 must be >= 2 and <= 36");
1726         return NULL;
1727     }
1728     while (*str != '\0' && isspace(Py_CHARMASK(*str)))
1729         str++;
1730     if (*str == '+')
1731         ++str;
1732     else if (*str == '-') {
1733         ++str;
1734         sign = -1;
1735     }
1736     while (*str != '\0' && isspace(Py_CHARMASK(*str)))
1737         str++;
1738     if (base == 0) {
1739         /* No base given.  Deduce the base from the contents
1740            of the string */
1741         if (str[0] != '0')
1742             base = 10;
1743         else if (str[1] == 'x' || str[1] == 'X')
1744             base = 16;
1745         else if (str[1] == 'o' || str[1] == 'O')
1746             base = 8;
1747         else if (str[1] == 'b' || str[1] == 'B')
1748             base = 2;
1749         else
1750             /* "old" (C-style) octal literal, still valid in
1751                2.x, although illegal in 3.x */
1752             base = 8;
1753     }
1754     /* Whether or not we were deducing the base, skip leading chars
1755        as needed */
1756     if (str[0] == '0' &&
1757         ((base == 16 && (str[1] == 'x' || str[1] == 'X')) ||
1758          (base == 8  && (str[1] == 'o' || str[1] == 'O')) ||
1759          (base == 2  && (str[1] == 'b' || str[1] == 'B'))))
1760         str += 2;
1761 
1762     start = str;
1763     if ((base & (base - 1)) == 0)
1764         z = long_from_binary_base(&str, base);
1765     else {
1766 /***
1767 Binary bases can be converted in time linear in the number of digits, because
1768 Python's representation base is binary.  Other bases (including decimal!) use
1769 the simple quadratic-time algorithm below, complicated by some speed tricks.
1770 
1771 First some math:  the largest integer that can be expressed in N base-B digits
1772 is B**N-1.  Consequently, if we have an N-digit input in base B, the worst-
1773 case number of Python digits needed to hold it is the smallest integer n s.t.
1774 
1775     PyLong_BASE**n-1 >= B**N-1  [or, adding 1 to both sides]
1776     PyLong_BASE**n >= B**N      [taking logs to base PyLong_BASE]
1777     n >= log(B**N)/log(PyLong_BASE) = N * log(B)/log(PyLong_BASE)
1778 
1779 The static array log_base_PyLong_BASE[base] == log(base)/log(PyLong_BASE) so
1780 we can compute this quickly.  A Python long with that much space is reserved
1781 near the start, and the result is computed into it.
1782 
1783 The input string is actually treated as being in base base**i (i.e., i digits
1784 are processed at a time), where two more static arrays hold:
1785 
1786     convwidth_base[base] = the largest integer i such that
1787                            base**i <= PyLong_BASE
1788     convmultmax_base[base] = base ** convwidth_base[base]
1789 
1790 The first of these is the largest i such that i consecutive input digits
1791 must fit in a single Python digit.  The second is effectively the input
1792 base we're really using.
1793 
1794 Viewing the input as a sequence <c0, c1, ..., c_n-1> of digits in base
1795 convmultmax_base[base], the result is "simply"
1796 
1797    (((c0*B + c1)*B + c2)*B + c3)*B + ... ))) + c_n-1
1798 
1799 where B = convmultmax_base[base].
1800 
1801 Error analysis:  as above, the number of Python digits `n` needed is worst-
1802 case
1803 
1804     n >= N * log(B)/log(PyLong_BASE)
1805 
1806 where `N` is the number of input digits in base `B`.  This is computed via
1807 
1808     size_z = (Py_ssize_t)((scan - str) * log_base_PyLong_BASE[base]) + 1;
1809 
1810 below.  Two numeric concerns are how much space this can waste, and whether
1811 the computed result can be too small.  To be concrete, assume PyLong_BASE =
1812 2**15, which is the default (and it's unlikely anyone changes that).
1813 
1814 Waste isn't a problem: provided the first input digit isn't 0, the difference
1815 between the worst-case input with N digits and the smallest input with N
1816 digits is about a factor of B, but B is small compared to PyLong_BASE so at
1817 most one allocated Python digit can remain unused on that count.  If
1818 N*log(B)/log(PyLong_BASE) is mathematically an exact integer, then truncating
1819 that and adding 1 returns a result 1 larger than necessary.  However, that
1820 can't happen: whenever B is a power of 2, long_from_binary_base() is called
1821 instead, and it's impossible for B**i to be an integer power of 2**15 when B
1822 is not a power of 2 (i.e., it's impossible for N*log(B)/log(PyLong_BASE) to be
1823 an exact integer when B is not a power of 2, since B**i has a prime factor
1824 other than 2 in that case, but (2**15)**j's only prime factor is 2).
1825 
1826 The computed result can be too small if the true value of
1827 N*log(B)/log(PyLong_BASE) is a little bit larger than an exact integer, but
1828 due to roundoff errors (in computing log(B), log(PyLong_BASE), their quotient,
1829 and/or multiplying that by N) yields a numeric result a little less than that
1830 integer.  Unfortunately, "how close can a transcendental function get to an
1831 integer over some range?"  questions are generally theoretically intractable.
1832 Computer analysis via continued fractions is practical: expand
1833 log(B)/log(PyLong_BASE) via continued fractions, giving a sequence i/j of "the
1834 best" rational approximations.  Then j*log(B)/log(PyLong_BASE) is
1835 approximately equal to (the integer) i.  This shows that we can get very close
1836 to being in trouble, but very rarely.  For example, 76573 is a denominator in
1837 one of the continued-fraction approximations to log(10)/log(2**15), and
1838 indeed:
1839 
1840     >>> log(10)/log(2**15)*76573
1841     16958.000000654003
1842 
1843 is very close to an integer.  If we were working with IEEE single-precision,
1844 rounding errors could kill us.  Finding worst cases in IEEE double-precision
1845 requires better-than-double-precision log() functions, and Tim didn't bother.
1846 Instead the code checks to see whether the allocated space is enough as each
1847 new Python digit is added, and copies the whole thing to a larger long if not.
1848 This should happen extremely rarely, and in fact I don't have a test case
1849 that triggers it(!).  Instead the code was tested by artificially allocating
1850 just 1 digit at the start, so that the copying code was exercised for every
1851 digit beyond the first.
1852 ***/
1853         register twodigits c;           /* current input character */
1854         Py_ssize_t size_z;
1855         int i;
1856         int convwidth;
1857         twodigits convmultmax, convmult;
1858         digit *pz, *pzstop;
1859         char* scan;
1860 
1861         static double log_base_PyLong_BASE[37] = {0.0e0,};
1862         static int convwidth_base[37] = {0,};
1863         static twodigits convmultmax_base[37] = {0,};
1864 
1865         if (log_base_PyLong_BASE[base] == 0.0) {
1866             twodigits convmax = base;
1867             int i = 1;
1868 
1869             log_base_PyLong_BASE[base] = (log((double)base) /
1870                                           log((double)PyLong_BASE));
1871             for (;;) {
1872                 twodigits next = convmax * base;
1873                 if (next > PyLong_BASE)
1874                     break;
1875                 convmax = next;
1876                 ++i;
1877             }
1878             convmultmax_base[base] = convmax;
1879             assert(i > 0);
1880             convwidth_base[base] = i;
1881         }
1882 
1883         /* Find length of the string of numeric characters. */
1884         scan = str;
1885         while (_PyLong_DigitValue[Py_CHARMASK(*scan)] < base)
1886             ++scan;
1887 
1888         /* Create a long object that can contain the largest possible
1889          * integer with this base and length.  Note that there's no
1890          * need to initialize z->ob_digit -- no slot is read up before
1891          * being stored into.
1892          */
1893         size_z = (Py_ssize_t)((scan - str) * log_base_PyLong_BASE[base]) + 1;
1894         /* Uncomment next line to test exceedingly rare copy code */
1895         /* size_z = 1; */
1896         assert(size_z > 0);
1897         z = _PyLong_New(size_z);
1898         if (z == NULL)
1899             return NULL;
1900         Py_SIZE(z) = 0;
1901 
1902         /* `convwidth` consecutive input digits are treated as a single
1903          * digit in base `convmultmax`.
1904          */
1905         convwidth = convwidth_base[base];
1906         convmultmax = convmultmax_base[base];
1907 
1908         /* Work ;-) */
1909         while (str < scan) {
1910             /* grab up to convwidth digits from the input string */
1911             c = (digit)_PyLong_DigitValue[Py_CHARMASK(*str++)];
1912             for (i = 1; i < convwidth && str != scan; ++i, ++str) {
1913                 c = (twodigits)(c *  base +
1914                                 _PyLong_DigitValue[Py_CHARMASK(*str)]);
1915                 assert(c < PyLong_BASE);
1916             }
1917 
1918             convmult = convmultmax;
1919             /* Calculate the shift only if we couldn't get
1920              * convwidth digits.
1921              */
1922             if (i != convwidth) {
1923                 convmult = base;
1924                 for ( ; i > 1; --i)
1925                     convmult *= base;
1926             }
1927 
1928             /* Multiply z by convmult, and add c. */
1929             pz = z->ob_digit;
1930             pzstop = pz + Py_SIZE(z);
1931             for (; pz < pzstop; ++pz) {
1932                 c += (twodigits)*pz * convmult;
1933                 *pz = (digit)(c & PyLong_MASK);
1934                 c >>= PyLong_SHIFT;
1935             }
1936             /* carry off the current end? */
1937             if (c) {
1938                 assert(c < PyLong_BASE);
1939                 if (Py_SIZE(z) < size_z) {
1940                     *pz = (digit)c;
1941                     ++Py_SIZE(z);
1942                 }
1943                 else {
1944                     PyLongObject *tmp;
1945                     /* Extremely rare.  Get more space. */
1946                     assert(Py_SIZE(z) == size_z);
1947                     tmp = _PyLong_New(size_z + 1);
1948                     if (tmp == NULL) {
1949                         Py_DECREF(z);
1950                         return NULL;
1951                     }
1952                     memcpy(tmp->ob_digit,
1953                            z->ob_digit,
1954                            sizeof(digit) * size_z);
1955                     Py_DECREF(z);
1956                     z = tmp;
1957                     z->ob_digit[size_z] = (digit)c;
1958                     ++size_z;
1959                 }
1960             }
1961         }
1962     }
1963     if (z == NULL)
1964         return NULL;
1965     if (str == start)
1966         goto onError;
1967     if (sign < 0)
1968         Py_SIZE(z) = -(Py_SIZE(z));
1969     if (*str == 'L' || *str == 'l')
1970         str++;
1971     while (*str && isspace(Py_CHARMASK(*str)))
1972         str++;
1973     if (*str != '\0')
1974         goto onError;
1975     if (pend)
1976         *pend = str;
1977     return (PyObject *) z;
1978 
1979   onError:
1980     Py_XDECREF(z);
1981     slen = strlen(orig_str) < 200 ? strlen(orig_str) : 200;
1982     strobj = PyString_FromStringAndSize(orig_str, slen);
1983     if (strobj == NULL)
1984         return NULL;
1985     strrepr = PyObject_Repr(strobj);
1986     Py_DECREF(strobj);
1987     if (strrepr == NULL)
1988         return NULL;
1989     PyErr_Format(PyExc_ValueError,
1990                  "invalid literal for long() with base %d: %s",
1991                  base, PyString_AS_STRING(strrepr));
1992     Py_DECREF(strrepr);
1993     return NULL;
1994 }
1995 
1996 #ifdef Py_USING_UNICODE
1997 PyObject *
PyLong_FromUnicode(Py_UNICODE * u,Py_ssize_t length,int base)1998 PyLong_FromUnicode(Py_UNICODE *u, Py_ssize_t length, int base)
1999 {
2000     PyObject *result;
2001     char *buffer = (char *)PyMem_MALLOC(length+1);
2002 
2003     if (buffer == NULL)
2004         return NULL;
2005 
2006     if (PyUnicode_EncodeDecimal(u, length, buffer, NULL)) {
2007         PyMem_FREE(buffer);
2008         return NULL;
2009     }
2010     result = PyLong_FromString(buffer, NULL, base);
2011     PyMem_FREE(buffer);
2012     return result;
2013 }
2014 #endif
2015 
2016 /* forward */
2017 static PyLongObject *x_divrem
2018     (PyLongObject *, PyLongObject *, PyLongObject **);
2019 static PyObject *long_long(PyObject *v);
2020 
2021 /* Long division with remainder, top-level routine */
2022 
2023 static int
long_divrem(PyLongObject * a,PyLongObject * b,PyLongObject ** pdiv,PyLongObject ** prem)2024 long_divrem(PyLongObject *a, PyLongObject *b,
2025             PyLongObject **pdiv, PyLongObject **prem)
2026 {
2027     Py_ssize_t size_a = ABS(Py_SIZE(a)), size_b = ABS(Py_SIZE(b));
2028     PyLongObject *z;
2029 
2030     if (size_b == 0) {
2031         PyErr_SetString(PyExc_ZeroDivisionError,
2032                         "long division or modulo by zero");
2033         return -1;
2034     }
2035     if (size_a < size_b ||
2036         (size_a == size_b &&
2037          a->ob_digit[size_a-1] < b->ob_digit[size_b-1])) {
2038         /* |a| < |b|. */
2039         *pdiv = _PyLong_New(0);
2040         if (*pdiv == NULL)
2041             return -1;
2042         Py_INCREF(a);
2043         *prem = (PyLongObject *) a;
2044         return 0;
2045     }
2046     if (size_b == 1) {
2047         digit rem = 0;
2048         z = divrem1(a, b->ob_digit[0], &rem);
2049         if (z == NULL)
2050             return -1;
2051         *prem = (PyLongObject *) PyLong_FromLong((long)rem);
2052         if (*prem == NULL) {
2053             Py_DECREF(z);
2054             return -1;
2055         }
2056     }
2057     else {
2058         z = x_divrem(a, b, prem);
2059         if (z == NULL)
2060             return -1;
2061     }
2062     /* Set the signs.
2063        The quotient z has the sign of a*b;
2064        the remainder r has the sign of a,
2065        so a = b*z + r. */
2066     if ((a->ob_size < 0) != (b->ob_size < 0))
2067         z->ob_size = -(z->ob_size);
2068     if (a->ob_size < 0 && (*prem)->ob_size != 0)
2069         (*prem)->ob_size = -((*prem)->ob_size);
2070     *pdiv = z;
2071     return 0;
2072 }
2073 
2074 /* Unsigned long division with remainder -- the algorithm.  The arguments v1
2075    and w1 should satisfy 2 <= ABS(Py_SIZE(w1)) <= ABS(Py_SIZE(v1)). */
2076 
2077 static PyLongObject *
x_divrem(PyLongObject * v1,PyLongObject * w1,PyLongObject ** prem)2078 x_divrem(PyLongObject *v1, PyLongObject *w1, PyLongObject **prem)
2079 {
2080     PyLongObject *v, *w, *a;
2081     Py_ssize_t i, k, size_v, size_w;
2082     int d;
2083     digit wm1, wm2, carry, q, r, vtop, *v0, *vk, *w0, *ak;
2084     twodigits vv;
2085     sdigit zhi;
2086     stwodigits z;
2087 
2088     /* We follow Knuth [The Art of Computer Programming, Vol. 2 (3rd
2089        edn.), section 4.3.1, Algorithm D], except that we don't explicitly
2090        handle the special case when the initial estimate q for a quotient
2091        digit is >= PyLong_BASE: the max value for q is PyLong_BASE+1, and
2092        that won't overflow a digit. */
2093 
2094     /* allocate space; w will also be used to hold the final remainder */
2095     size_v = ABS(Py_SIZE(v1));
2096     size_w = ABS(Py_SIZE(w1));
2097     assert(size_v >= size_w && size_w >= 2); /* Assert checks by div() */
2098     v = _PyLong_New(size_v+1);
2099     if (v == NULL) {
2100         *prem = NULL;
2101         return NULL;
2102     }
2103     w = _PyLong_New(size_w);
2104     if (w == NULL) {
2105         Py_DECREF(v);
2106         *prem = NULL;
2107         return NULL;
2108     }
2109 
2110     /* normalize: shift w1 left so that its top digit is >= PyLong_BASE/2.
2111        shift v1 left by the same amount.  Results go into w and v. */
2112     d = PyLong_SHIFT - bits_in_digit(w1->ob_digit[size_w-1]);
2113     carry = v_lshift(w->ob_digit, w1->ob_digit, size_w, d);
2114     assert(carry == 0);
2115     carry = v_lshift(v->ob_digit, v1->ob_digit, size_v, d);
2116     if (carry != 0 || v->ob_digit[size_v-1] >= w->ob_digit[size_w-1]) {
2117         v->ob_digit[size_v] = carry;
2118         size_v++;
2119     }
2120 
2121     /* Now v->ob_digit[size_v-1] < w->ob_digit[size_w-1], so quotient has
2122        at most (and usually exactly) k = size_v - size_w digits. */
2123     k = size_v - size_w;
2124     assert(k >= 0);
2125     a = _PyLong_New(k);
2126     if (a == NULL) {
2127         Py_DECREF(w);
2128         Py_DECREF(v);
2129         *prem = NULL;
2130         return NULL;
2131     }
2132     v0 = v->ob_digit;
2133     w0 = w->ob_digit;
2134     wm1 = w0[size_w-1];
2135     wm2 = w0[size_w-2];
2136     for (vk = v0+k, ak = a->ob_digit + k; vk-- > v0;) {
2137         /* inner loop: divide vk[0:size_w+1] by w0[0:size_w], giving
2138            single-digit quotient q, remainder in vk[0:size_w]. */
2139 
2140         SIGCHECK({
2141                 Py_DECREF(a);
2142                 Py_DECREF(w);
2143                 Py_DECREF(v);
2144                 *prem = NULL;
2145                 return NULL;
2146             });
2147 
2148         /* estimate quotient digit q; may overestimate by 1 (rare) */
2149         vtop = vk[size_w];
2150         assert(vtop <= wm1);
2151         vv = ((twodigits)vtop << PyLong_SHIFT) | vk[size_w-1];
2152         q = (digit)(vv / wm1);
2153         r = (digit)(vv - (twodigits)wm1 * q); /* r = vv % wm1 */
2154         while ((twodigits)wm2 * q > (((twodigits)r << PyLong_SHIFT)
2155                                      | vk[size_w-2])) {
2156             --q;
2157             r += wm1;
2158             if (r >= PyLong_BASE)
2159                 break;
2160         }
2161         assert(q <= PyLong_BASE);
2162 
2163         /* subtract q*w0[0:size_w] from vk[0:size_w+1] */
2164         zhi = 0;
2165         for (i = 0; i < size_w; ++i) {
2166             /* invariants: -PyLong_BASE <= -q <= zhi <= 0;
2167                -PyLong_BASE * q <= z < PyLong_BASE */
2168             z = (sdigit)vk[i] + zhi -
2169                 (stwodigits)q * (stwodigits)w0[i];
2170             vk[i] = (digit)z & PyLong_MASK;
2171             zhi = (sdigit)Py_ARITHMETIC_RIGHT_SHIFT(stwodigits,
2172                                                     z, PyLong_SHIFT);
2173         }
2174 
2175         /* add w back if q was too large (this branch taken rarely) */
2176         assert((sdigit)vtop + zhi == -1 || (sdigit)vtop + zhi == 0);
2177         if ((sdigit)vtop + zhi < 0) {
2178             carry = 0;
2179             for (i = 0; i < size_w; ++i) {
2180                 carry += vk[i] + w0[i];
2181                 vk[i] = carry & PyLong_MASK;
2182                 carry >>= PyLong_SHIFT;
2183             }
2184             --q;
2185         }
2186 
2187         /* store quotient digit */
2188         assert(q < PyLong_BASE);
2189         *--ak = q;
2190     }
2191 
2192     /* unshift remainder; we reuse w to store the result */
2193     carry = v_rshift(w0, v0, size_w, d);
2194     assert(carry==0);
2195     Py_DECREF(v);
2196 
2197     *prem = long_normalize(w);
2198     return long_normalize(a);
2199 }
2200 
2201 /* For a nonzero PyLong a, express a in the form x * 2**e, with 0.5 <=
2202    abs(x) < 1.0 and e >= 0; return x and put e in *e.  Here x is
2203    rounded to DBL_MANT_DIG significant bits using round-half-to-even.
2204    If a == 0, return 0.0 and set *e = 0.  If the resulting exponent
2205    e is larger than PY_SSIZE_T_MAX, raise OverflowError and return
2206    -1.0. */
2207 
2208 /* attempt to define 2.0**DBL_MANT_DIG as a compile-time constant */
2209 #if DBL_MANT_DIG == 53
2210 #define EXP2_DBL_MANT_DIG 9007199254740992.0
2211 #else
2212 #define EXP2_DBL_MANT_DIG (ldexp(1.0, DBL_MANT_DIG))
2213 #endif
2214 
2215 double
_PyLong_Frexp(PyLongObject * a,Py_ssize_t * e)2216 _PyLong_Frexp(PyLongObject *a, Py_ssize_t *e)
2217 {
2218     Py_ssize_t a_size, a_bits, shift_digits, shift_bits, x_size;
2219     /* See below for why x_digits is always large enough. */
2220     digit rem, x_digits[2 + (DBL_MANT_DIG + 1) / PyLong_SHIFT];
2221     double dx;
2222     /* Correction term for round-half-to-even rounding.  For a digit x,
2223        "x + half_even_correction[x & 7]" gives x rounded to the nearest
2224        multiple of 4, rounding ties to a multiple of 8. */
2225     static const int half_even_correction[8] = {0, -1, -2, 1, 0, -1, 2, 1};
2226 
2227     a_size = ABS(Py_SIZE(a));
2228     if (a_size == 0) {
2229         /* Special case for 0: significand 0.0, exponent 0. */
2230         *e = 0;
2231         return 0.0;
2232     }
2233     a_bits = bits_in_digit(a->ob_digit[a_size-1]);
2234     /* The following is an overflow-free version of the check
2235        "if ((a_size - 1) * PyLong_SHIFT + a_bits > PY_SSIZE_T_MAX) ..." */
2236     if (a_size >= (PY_SSIZE_T_MAX - 1) / PyLong_SHIFT + 1 &&
2237         (a_size > (PY_SSIZE_T_MAX - 1) / PyLong_SHIFT + 1 ||
2238          a_bits > (PY_SSIZE_T_MAX - 1) % PyLong_SHIFT + 1))
2239         goto overflow;
2240     a_bits = (a_size - 1) * PyLong_SHIFT + a_bits;
2241 
2242     /* Shift the first DBL_MANT_DIG + 2 bits of a into x_digits[0:x_size]
2243        (shifting left if a_bits <= DBL_MANT_DIG + 2).
2244 
2245        Number of digits needed for result: write // for floor division.
2246        Then if shifting left, we end up using
2247 
2248          1 + a_size + (DBL_MANT_DIG + 2 - a_bits) // PyLong_SHIFT
2249 
2250        digits.  If shifting right, we use
2251 
2252          a_size - (a_bits - DBL_MANT_DIG - 2) // PyLong_SHIFT
2253 
2254        digits.  Using a_size = 1 + (a_bits - 1) // PyLong_SHIFT along with
2255        the inequalities
2256 
2257          m // PyLong_SHIFT + n // PyLong_SHIFT <= (m + n) // PyLong_SHIFT
2258          m // PyLong_SHIFT - n // PyLong_SHIFT <=
2259                                           1 + (m - n - 1) // PyLong_SHIFT,
2260 
2261        valid for any integers m and n, we find that x_size satisfies
2262 
2263          x_size <= 2 + (DBL_MANT_DIG + 1) // PyLong_SHIFT
2264 
2265        in both cases.
2266     */
2267     if (a_bits <= DBL_MANT_DIG + 2) {
2268         shift_digits = (DBL_MANT_DIG + 2 - a_bits) / PyLong_SHIFT;
2269         shift_bits = (DBL_MANT_DIG + 2 - a_bits) % PyLong_SHIFT;
2270         x_size = 0;
2271         while (x_size < shift_digits)
2272             x_digits[x_size++] = 0;
2273         rem = v_lshift(x_digits + x_size, a->ob_digit, a_size,
2274                        (int)shift_bits);
2275         x_size += a_size;
2276         x_digits[x_size++] = rem;
2277     }
2278     else {
2279         shift_digits = (a_bits - DBL_MANT_DIG - 2) / PyLong_SHIFT;
2280         shift_bits = (a_bits - DBL_MANT_DIG - 2) % PyLong_SHIFT;
2281         rem = v_rshift(x_digits, a->ob_digit + shift_digits,
2282                        a_size - shift_digits, (int)shift_bits);
2283         x_size = a_size - shift_digits;
2284         /* For correct rounding below, we need the least significant
2285            bit of x to be 'sticky' for this shift: if any of the bits
2286            shifted out was nonzero, we set the least significant bit
2287            of x. */
2288         if (rem)
2289             x_digits[0] |= 1;
2290         else
2291             while (shift_digits > 0)
2292                 if (a->ob_digit[--shift_digits]) {
2293                     x_digits[0] |= 1;
2294                     break;
2295                 }
2296     }
2297     assert(1 <= x_size &&
2298            x_size <= (Py_ssize_t)(sizeof(x_digits)/sizeof(digit)));
2299 
2300     /* Round, and convert to double. */
2301     x_digits[0] += half_even_correction[x_digits[0] & 7];
2302     dx = x_digits[--x_size];
2303     while (x_size > 0)
2304         dx = dx * PyLong_BASE + x_digits[--x_size];
2305 
2306     /* Rescale;  make correction if result is 1.0. */
2307     dx /= 4.0 * EXP2_DBL_MANT_DIG;
2308     if (dx == 1.0) {
2309         if (a_bits == PY_SSIZE_T_MAX)
2310             goto overflow;
2311         dx = 0.5;
2312         a_bits += 1;
2313     }
2314 
2315     *e = a_bits;
2316     return Py_SIZE(a) < 0 ? -dx : dx;
2317 
2318   overflow:
2319     /* exponent > PY_SSIZE_T_MAX */
2320     PyErr_SetString(PyExc_OverflowError,
2321                     "huge integer: number of bits overflows a Py_ssize_t");
2322     *e = 0;
2323     return -1.0;
2324 }
2325 
2326 /* Get a C double from a long int object.  Rounds to the nearest double,
2327    using the round-half-to-even rule in the case of a tie. */
2328 
2329 double
PyLong_AsDouble(PyObject * v)2330 PyLong_AsDouble(PyObject *v)
2331 {
2332     Py_ssize_t exponent;
2333     double x;
2334 
2335     if (v == NULL || !PyLong_Check(v)) {
2336         PyErr_BadInternalCall();
2337         return -1.0;
2338     }
2339     x = _PyLong_Frexp((PyLongObject *)v, &exponent);
2340     if ((x == -1.0 && PyErr_Occurred()) || exponent > DBL_MAX_EXP) {
2341         PyErr_SetString(PyExc_OverflowError,
2342                         "long int too large to convert to float");
2343         return -1.0;
2344     }
2345     return ldexp(x, (int)exponent);
2346 }
2347 
2348 /* Methods */
2349 
2350 static void
long_dealloc(PyObject * v)2351 long_dealloc(PyObject *v)
2352 {
2353     Py_TYPE(v)->tp_free(v);
2354 }
2355 
2356 static PyObject *
long_repr(PyObject * v)2357 long_repr(PyObject *v)
2358 {
2359     return _PyLong_Format(v, 10, 1, 0);
2360 }
2361 
2362 static PyObject *
long_str(PyObject * v)2363 long_str(PyObject *v)
2364 {
2365     return _PyLong_Format(v, 10, 0, 0);
2366 }
2367 
2368 static int
long_compare(PyLongObject * a,PyLongObject * b)2369 long_compare(PyLongObject *a, PyLongObject *b)
2370 {
2371     Py_ssize_t sign;
2372 
2373     if (Py_SIZE(a) != Py_SIZE(b)) {
2374         sign = Py_SIZE(a) - Py_SIZE(b);
2375     }
2376     else {
2377         Py_ssize_t i = ABS(Py_SIZE(a));
2378         while (--i >= 0 && a->ob_digit[i] == b->ob_digit[i])
2379             ;
2380         if (i < 0)
2381             sign = 0;
2382         else {
2383             sign = (sdigit)a->ob_digit[i] - (sdigit)b->ob_digit[i];
2384             if (Py_SIZE(a) < 0)
2385                 sign = -sign;
2386         }
2387     }
2388     return sign < 0 ? -1 : sign > 0 ? 1 : 0;
2389 }
2390 
2391 static long
long_hash(PyLongObject * v)2392 long_hash(PyLongObject *v)
2393 {
2394     unsigned long x;
2395     Py_ssize_t i;
2396     int sign;
2397 
2398     /* This is designed so that Python ints and longs with the
2399        same value hash to the same value, otherwise comparisons
2400        of mapping keys will turn out weird */
2401     i = v->ob_size;
2402     sign = 1;
2403     x = 0;
2404     if (i < 0) {
2405         sign = -1;
2406         i = -(i);
2407     }
2408     /* The following loop produces a C unsigned long x such that x is
2409        congruent to the absolute value of v modulo ULONG_MAX.  The
2410        resulting x is nonzero if and only if v is. */
2411     while (--i >= 0) {
2412         /* Force a native long #-bits (32 or 64) circular shift */
2413         x = (x >> (8*SIZEOF_LONG-PyLong_SHIFT)) | (x << PyLong_SHIFT);
2414         x += v->ob_digit[i];
2415         /* If the addition above overflowed we compensate by
2416            incrementing.  This preserves the value modulo
2417            ULONG_MAX. */
2418         if (x < v->ob_digit[i])
2419             x++;
2420     }
2421     x = x * sign;
2422     if (x == (unsigned long)-1)
2423         x = (unsigned long)-2;
2424     return (long)x;
2425 }
2426 
2427 
2428 /* Add the absolute values of two long integers. */
2429 
2430 static PyLongObject *
x_add(PyLongObject * a,PyLongObject * b)2431 x_add(PyLongObject *a, PyLongObject *b)
2432 {
2433     Py_ssize_t size_a = ABS(Py_SIZE(a)), size_b = ABS(Py_SIZE(b));
2434     PyLongObject *z;
2435     Py_ssize_t i;
2436     digit carry = 0;
2437 
2438     /* Ensure a is the larger of the two: */
2439     if (size_a < size_b) {
2440         { PyLongObject *temp = a; a = b; b = temp; }
2441         { Py_ssize_t size_temp = size_a;
2442             size_a = size_b;
2443             size_b = size_temp; }
2444     }
2445     z = _PyLong_New(size_a+1);
2446     if (z == NULL)
2447         return NULL;
2448     for (i = 0; i < size_b; ++i) {
2449         carry += a->ob_digit[i] + b->ob_digit[i];
2450         z->ob_digit[i] = carry & PyLong_MASK;
2451         carry >>= PyLong_SHIFT;
2452     }
2453     for (; i < size_a; ++i) {
2454         carry += a->ob_digit[i];
2455         z->ob_digit[i] = carry & PyLong_MASK;
2456         carry >>= PyLong_SHIFT;
2457     }
2458     z->ob_digit[i] = carry;
2459     return long_normalize(z);
2460 }
2461 
2462 /* Subtract the absolute values of two integers. */
2463 
2464 static PyLongObject *
x_sub(PyLongObject * a,PyLongObject * b)2465 x_sub(PyLongObject *a, PyLongObject *b)
2466 {
2467     Py_ssize_t size_a = ABS(Py_SIZE(a)), size_b = ABS(Py_SIZE(b));
2468     PyLongObject *z;
2469     Py_ssize_t i;
2470     int sign = 1;
2471     digit borrow = 0;
2472 
2473     /* Ensure a is the larger of the two: */
2474     if (size_a < size_b) {
2475         sign = -1;
2476         { PyLongObject *temp = a; a = b; b = temp; }
2477         { Py_ssize_t size_temp = size_a;
2478             size_a = size_b;
2479             size_b = size_temp; }
2480     }
2481     else if (size_a == size_b) {
2482         /* Find highest digit where a and b differ: */
2483         i = size_a;
2484         while (--i >= 0 && a->ob_digit[i] == b->ob_digit[i])
2485             ;
2486         if (i < 0)
2487             return _PyLong_New(0);
2488         if (a->ob_digit[i] < b->ob_digit[i]) {
2489             sign = -1;
2490             { PyLongObject *temp = a; a = b; b = temp; }
2491         }
2492         size_a = size_b = i+1;
2493     }
2494     z = _PyLong_New(size_a);
2495     if (z == NULL)
2496         return NULL;
2497     for (i = 0; i < size_b; ++i) {
2498         /* The following assumes unsigned arithmetic
2499            works module 2**N for some N>PyLong_SHIFT. */
2500         borrow = a->ob_digit[i] - b->ob_digit[i] - borrow;
2501         z->ob_digit[i] = borrow & PyLong_MASK;
2502         borrow >>= PyLong_SHIFT;
2503         borrow &= 1; /* Keep only one sign bit */
2504     }
2505     for (; i < size_a; ++i) {
2506         borrow = a->ob_digit[i] - borrow;
2507         z->ob_digit[i] = borrow & PyLong_MASK;
2508         borrow >>= PyLong_SHIFT;
2509         borrow &= 1; /* Keep only one sign bit */
2510     }
2511     assert(borrow == 0);
2512     if (sign < 0)
2513         z->ob_size = -(z->ob_size);
2514     return long_normalize(z);
2515 }
2516 
2517 static PyObject *
long_add(PyLongObject * v,PyLongObject * w)2518 long_add(PyLongObject *v, PyLongObject *w)
2519 {
2520     PyLongObject *a, *b, *z;
2521 
2522     CONVERT_BINOP((PyObject *)v, (PyObject *)w, &a, &b);
2523 
2524     if (a->ob_size < 0) {
2525         if (b->ob_size < 0) {
2526             z = x_add(a, b);
2527             if (z != NULL && z->ob_size != 0)
2528                 z->ob_size = -(z->ob_size);
2529         }
2530         else
2531             z = x_sub(b, a);
2532     }
2533     else {
2534         if (b->ob_size < 0)
2535             z = x_sub(a, b);
2536         else
2537             z = x_add(a, b);
2538     }
2539     Py_DECREF(a);
2540     Py_DECREF(b);
2541     return (PyObject *)z;
2542 }
2543 
2544 static PyObject *
long_sub(PyLongObject * v,PyLongObject * w)2545 long_sub(PyLongObject *v, PyLongObject *w)
2546 {
2547     PyLongObject *a, *b, *z;
2548 
2549     CONVERT_BINOP((PyObject *)v, (PyObject *)w, &a, &b);
2550 
2551     if (a->ob_size < 0) {
2552         if (b->ob_size < 0)
2553             z = x_sub(a, b);
2554         else
2555             z = x_add(a, b);
2556         if (z != NULL && z->ob_size != 0)
2557             z->ob_size = -(z->ob_size);
2558     }
2559     else {
2560         if (b->ob_size < 0)
2561             z = x_add(a, b);
2562         else
2563             z = x_sub(a, b);
2564     }
2565     Py_DECREF(a);
2566     Py_DECREF(b);
2567     return (PyObject *)z;
2568 }
2569 
2570 /* Grade school multiplication, ignoring the signs.
2571  * Returns the absolute value of the product, or NULL if error.
2572  */
2573 static PyLongObject *
x_mul(PyLongObject * a,PyLongObject * b)2574 x_mul(PyLongObject *a, PyLongObject *b)
2575 {
2576     PyLongObject *z;
2577     Py_ssize_t size_a = ABS(Py_SIZE(a));
2578     Py_ssize_t size_b = ABS(Py_SIZE(b));
2579     Py_ssize_t i;
2580 
2581     z = _PyLong_New(size_a + size_b);
2582     if (z == NULL)
2583         return NULL;
2584 
2585     memset(z->ob_digit, 0, Py_SIZE(z) * sizeof(digit));
2586     if (a == b) {
2587         /* Efficient squaring per HAC, Algorithm 14.16:
2588          * http://www.cacr.math.uwaterloo.ca/hac/about/chap14.pdf
2589          * Gives slightly less than a 2x speedup when a == b,
2590          * via exploiting that each entry in the multiplication
2591          * pyramid appears twice (except for the size_a squares).
2592          */
2593         for (i = 0; i < size_a; ++i) {
2594             twodigits carry;
2595             twodigits f = a->ob_digit[i];
2596             digit *pz = z->ob_digit + (i << 1);
2597             digit *pa = a->ob_digit + i + 1;
2598             digit *paend = a->ob_digit + size_a;
2599 
2600             SIGCHECK({
2601                     Py_DECREF(z);
2602                     return NULL;
2603                 });
2604 
2605             carry = *pz + f * f;
2606             *pz++ = (digit)(carry & PyLong_MASK);
2607             carry >>= PyLong_SHIFT;
2608             assert(carry <= PyLong_MASK);
2609 
2610             /* Now f is added in twice in each column of the
2611              * pyramid it appears.  Same as adding f<<1 once.
2612              */
2613             f <<= 1;
2614             while (pa < paend) {
2615                 carry += *pz + *pa++ * f;
2616                 *pz++ = (digit)(carry & PyLong_MASK);
2617                 carry >>= PyLong_SHIFT;
2618                 assert(carry <= (PyLong_MASK << 1));
2619             }
2620             if (carry) {
2621                 carry += *pz;
2622                 *pz++ = (digit)(carry & PyLong_MASK);
2623                 carry >>= PyLong_SHIFT;
2624             }
2625             if (carry)
2626                 *pz += (digit)(carry & PyLong_MASK);
2627             assert((carry >> PyLong_SHIFT) == 0);
2628         }
2629     }
2630     else {      /* a is not the same as b -- gradeschool long mult */
2631         for (i = 0; i < size_a; ++i) {
2632             twodigits carry = 0;
2633             twodigits f = a->ob_digit[i];
2634             digit *pz = z->ob_digit + i;
2635             digit *pb = b->ob_digit;
2636             digit *pbend = b->ob_digit + size_b;
2637 
2638             SIGCHECK({
2639                     Py_DECREF(z);
2640                     return NULL;
2641                 });
2642 
2643             while (pb < pbend) {
2644                 carry += *pz + *pb++ * f;
2645                 *pz++ = (digit)(carry & PyLong_MASK);
2646                 carry >>= PyLong_SHIFT;
2647                 assert(carry <= PyLong_MASK);
2648             }
2649             if (carry)
2650                 *pz += (digit)(carry & PyLong_MASK);
2651             assert((carry >> PyLong_SHIFT) == 0);
2652         }
2653     }
2654     return long_normalize(z);
2655 }
2656 
2657 /* A helper for Karatsuba multiplication (k_mul).
2658    Takes a long "n" and an integer "size" representing the place to
2659    split, and sets low and high such that abs(n) == (high << size) + low,
2660    viewing the shift as being by digits.  The sign bit is ignored, and
2661    the return values are >= 0.
2662    Returns 0 on success, -1 on failure.
2663 */
2664 static int
kmul_split(PyLongObject * n,Py_ssize_t size,PyLongObject ** high,PyLongObject ** low)2665 kmul_split(PyLongObject *n,
2666            Py_ssize_t size,
2667            PyLongObject **high,
2668            PyLongObject **low)
2669 {
2670     PyLongObject *hi, *lo;
2671     Py_ssize_t size_lo, size_hi;
2672     const Py_ssize_t size_n = ABS(Py_SIZE(n));
2673 
2674     size_lo = MIN(size_n, size);
2675     size_hi = size_n - size_lo;
2676 
2677     if ((hi = _PyLong_New(size_hi)) == NULL)
2678         return -1;
2679     if ((lo = _PyLong_New(size_lo)) == NULL) {
2680         Py_DECREF(hi);
2681         return -1;
2682     }
2683 
2684     memcpy(lo->ob_digit, n->ob_digit, size_lo * sizeof(digit));
2685     memcpy(hi->ob_digit, n->ob_digit + size_lo, size_hi * sizeof(digit));
2686 
2687     *high = long_normalize(hi);
2688     *low = long_normalize(lo);
2689     return 0;
2690 }
2691 
2692 static PyLongObject *k_lopsided_mul(PyLongObject *a, PyLongObject *b);
2693 
2694 /* Karatsuba multiplication.  Ignores the input signs, and returns the
2695  * absolute value of the product (or NULL if error).
2696  * See Knuth Vol. 2 Chapter 4.3.3 (Pp. 294-295).
2697  */
2698 static PyLongObject *
k_mul(PyLongObject * a,PyLongObject * b)2699 k_mul(PyLongObject *a, PyLongObject *b)
2700 {
2701     Py_ssize_t asize = ABS(Py_SIZE(a));
2702     Py_ssize_t bsize = ABS(Py_SIZE(b));
2703     PyLongObject *ah = NULL;
2704     PyLongObject *al = NULL;
2705     PyLongObject *bh = NULL;
2706     PyLongObject *bl = NULL;
2707     PyLongObject *ret = NULL;
2708     PyLongObject *t1, *t2, *t3;
2709     Py_ssize_t shift;           /* the number of digits we split off */
2710     Py_ssize_t i;
2711 
2712     /* (ah*X+al)(bh*X+bl) = ah*bh*X*X + (ah*bl + al*bh)*X + al*bl
2713      * Let k = (ah+al)*(bh+bl) = ah*bl + al*bh  + ah*bh + al*bl
2714      * Then the original product is
2715      *     ah*bh*X*X + (k - ah*bh - al*bl)*X + al*bl
2716      * By picking X to be a power of 2, "*X" is just shifting, and it's
2717      * been reduced to 3 multiplies on numbers half the size.
2718      */
2719 
2720     /* We want to split based on the larger number; fiddle so that b
2721      * is largest.
2722      */
2723     if (asize > bsize) {
2724         t1 = a;
2725         a = b;
2726         b = t1;
2727 
2728         i = asize;
2729         asize = bsize;
2730         bsize = i;
2731     }
2732 
2733     /* Use gradeschool math when either number is too small. */
2734     i = a == b ? KARATSUBA_SQUARE_CUTOFF : KARATSUBA_CUTOFF;
2735     if (asize <= i) {
2736         if (asize == 0)
2737             return _PyLong_New(0);
2738         else
2739             return x_mul(a, b);
2740     }
2741 
2742     /* If a is small compared to b, splitting on b gives a degenerate
2743      * case with ah==0, and Karatsuba may be (even much) less efficient
2744      * than "grade school" then.  However, we can still win, by viewing
2745      * b as a string of "big digits", each of width a->ob_size.  That
2746      * leads to a sequence of balanced calls to k_mul.
2747      */
2748     if (2 * asize <= bsize)
2749         return k_lopsided_mul(a, b);
2750 
2751     /* Split a & b into hi & lo pieces. */
2752     shift = bsize >> 1;
2753     if (kmul_split(a, shift, &ah, &al) < 0) goto fail;
2754     assert(Py_SIZE(ah) > 0);            /* the split isn't degenerate */
2755 
2756     if (a == b) {
2757         bh = ah;
2758         bl = al;
2759         Py_INCREF(bh);
2760         Py_INCREF(bl);
2761     }
2762     else if (kmul_split(b, shift, &bh, &bl) < 0) goto fail;
2763 
2764     /* The plan:
2765      * 1. Allocate result space (asize + bsize digits:  that's always
2766      *    enough).
2767      * 2. Compute ah*bh, and copy into result at 2*shift.
2768      * 3. Compute al*bl, and copy into result at 0.  Note that this
2769      *    can't overlap with #2.
2770      * 4. Subtract al*bl from the result, starting at shift.  This may
2771      *    underflow (borrow out of the high digit), but we don't care:
2772      *    we're effectively doing unsigned arithmetic mod
2773      *    PyLong_BASE**(sizea + sizeb), and so long as the *final* result fits,
2774      *    borrows and carries out of the high digit can be ignored.
2775      * 5. Subtract ah*bh from the result, starting at shift.
2776      * 6. Compute (ah+al)*(bh+bl), and add it into the result starting
2777      *    at shift.
2778      */
2779 
2780     /* 1. Allocate result space. */
2781     ret = _PyLong_New(asize + bsize);
2782     if (ret == NULL) goto fail;
2783 #ifdef Py_DEBUG
2784     /* Fill with trash, to catch reference to uninitialized digits. */
2785     memset(ret->ob_digit, 0xDF, Py_SIZE(ret) * sizeof(digit));
2786 #endif
2787 
2788     /* 2. t1 <- ah*bh, and copy into high digits of result. */
2789     if ((t1 = k_mul(ah, bh)) == NULL) goto fail;
2790     assert(Py_SIZE(t1) >= 0);
2791     assert(2*shift + Py_SIZE(t1) <= Py_SIZE(ret));
2792     memcpy(ret->ob_digit + 2*shift, t1->ob_digit,
2793            Py_SIZE(t1) * sizeof(digit));
2794 
2795     /* Zero-out the digits higher than the ah*bh copy. */
2796     i = Py_SIZE(ret) - 2*shift - Py_SIZE(t1);
2797     if (i)
2798         memset(ret->ob_digit + 2*shift + Py_SIZE(t1), 0,
2799                i * sizeof(digit));
2800 
2801     /* 3. t2 <- al*bl, and copy into the low digits. */
2802     if ((t2 = k_mul(al, bl)) == NULL) {
2803         Py_DECREF(t1);
2804         goto fail;
2805     }
2806     assert(Py_SIZE(t2) >= 0);
2807     assert(Py_SIZE(t2) <= 2*shift); /* no overlap with high digits */
2808     memcpy(ret->ob_digit, t2->ob_digit, Py_SIZE(t2) * sizeof(digit));
2809 
2810     /* Zero out remaining digits. */
2811     i = 2*shift - Py_SIZE(t2);          /* number of uninitialized digits */
2812     if (i)
2813         memset(ret->ob_digit + Py_SIZE(t2), 0, i * sizeof(digit));
2814 
2815     /* 4 & 5. Subtract ah*bh (t1) and al*bl (t2).  We do al*bl first
2816      * because it's fresher in cache.
2817      */
2818     i = Py_SIZE(ret) - shift;  /* # digits after shift */
2819     (void)v_isub(ret->ob_digit + shift, i, t2->ob_digit, Py_SIZE(t2));
2820     Py_DECREF(t2);
2821 
2822     (void)v_isub(ret->ob_digit + shift, i, t1->ob_digit, Py_SIZE(t1));
2823     Py_DECREF(t1);
2824 
2825     /* 6. t3 <- (ah+al)(bh+bl), and add into result. */
2826     if ((t1 = x_add(ah, al)) == NULL) goto fail;
2827     Py_DECREF(ah);
2828     Py_DECREF(al);
2829     ah = al = NULL;
2830 
2831     if (a == b) {
2832         t2 = t1;
2833         Py_INCREF(t2);
2834     }
2835     else if ((t2 = x_add(bh, bl)) == NULL) {
2836         Py_DECREF(t1);
2837         goto fail;
2838     }
2839     Py_DECREF(bh);
2840     Py_DECREF(bl);
2841     bh = bl = NULL;
2842 
2843     t3 = k_mul(t1, t2);
2844     Py_DECREF(t1);
2845     Py_DECREF(t2);
2846     if (t3 == NULL) goto fail;
2847     assert(Py_SIZE(t3) >= 0);
2848 
2849     /* Add t3.  It's not obvious why we can't run out of room here.
2850      * See the (*) comment after this function.
2851      */
2852     (void)v_iadd(ret->ob_digit + shift, i, t3->ob_digit, Py_SIZE(t3));
2853     Py_DECREF(t3);
2854 
2855     return long_normalize(ret);
2856 
2857   fail:
2858     Py_XDECREF(ret);
2859     Py_XDECREF(ah);
2860     Py_XDECREF(al);
2861     Py_XDECREF(bh);
2862     Py_XDECREF(bl);
2863     return NULL;
2864 }
2865 
2866 /* (*) Why adding t3 can't "run out of room" above.
2867 
2868 Let f(x) mean the floor of x and c(x) mean the ceiling of x.  Some facts
2869 to start with:
2870 
2871 1. For any integer i, i = c(i/2) + f(i/2).  In particular,
2872    bsize = c(bsize/2) + f(bsize/2).
2873 2. shift = f(bsize/2)
2874 3. asize <= bsize
2875 4. Since we call k_lopsided_mul if asize*2 <= bsize, asize*2 > bsize in this
2876    routine, so asize > bsize/2 >= f(bsize/2) in this routine.
2877 
2878 We allocated asize + bsize result digits, and add t3 into them at an offset
2879 of shift.  This leaves asize+bsize-shift allocated digit positions for t3
2880 to fit into, = (by #1 and #2) asize + f(bsize/2) + c(bsize/2) - f(bsize/2) =
2881 asize + c(bsize/2) available digit positions.
2882 
2883 bh has c(bsize/2) digits, and bl at most f(size/2) digits.  So bh+hl has
2884 at most c(bsize/2) digits + 1 bit.
2885 
2886 If asize == bsize, ah has c(bsize/2) digits, else ah has at most f(bsize/2)
2887 digits, and al has at most f(bsize/2) digits in any case.  So ah+al has at
2888 most (asize == bsize ? c(bsize/2) : f(bsize/2)) digits + 1 bit.
2889 
2890 The product (ah+al)*(bh+bl) therefore has at most
2891 
2892     c(bsize/2) + (asize == bsize ? c(bsize/2) : f(bsize/2)) digits + 2 bits
2893 
2894 and we have asize + c(bsize/2) available digit positions.  We need to show
2895 this is always enough.  An instance of c(bsize/2) cancels out in both, so
2896 the question reduces to whether asize digits is enough to hold
2897 (asize == bsize ? c(bsize/2) : f(bsize/2)) digits + 2 bits.  If asize < bsize,
2898 then we're asking whether asize digits >= f(bsize/2) digits + 2 bits.  By #4,
2899 asize is at least f(bsize/2)+1 digits, so this in turn reduces to whether 1
2900 digit is enough to hold 2 bits.  This is so since PyLong_SHIFT=15 >= 2.  If
2901 asize == bsize, then we're asking whether bsize digits is enough to hold
2902 c(bsize/2) digits + 2 bits, or equivalently (by #1) whether f(bsize/2) digits
2903 is enough to hold 2 bits.  This is so if bsize >= 2, which holds because
2904 bsize >= KARATSUBA_CUTOFF >= 2.
2905 
2906 Note that since there's always enough room for (ah+al)*(bh+bl), and that's
2907 clearly >= each of ah*bh and al*bl, there's always enough room to subtract
2908 ah*bh and al*bl too.
2909 */
2910 
2911 /* b has at least twice the digits of a, and a is big enough that Karatsuba
2912  * would pay off *if* the inputs had balanced sizes.  View b as a sequence
2913  * of slices, each with a->ob_size digits, and multiply the slices by a,
2914  * one at a time.  This gives k_mul balanced inputs to work with, and is
2915  * also cache-friendly (we compute one double-width slice of the result
2916  * at a time, then move on, never backtracking except for the helpful
2917  * single-width slice overlap between successive partial sums).
2918  */
2919 static PyLongObject *
k_lopsided_mul(PyLongObject * a,PyLongObject * b)2920 k_lopsided_mul(PyLongObject *a, PyLongObject *b)
2921 {
2922     const Py_ssize_t asize = ABS(Py_SIZE(a));
2923     Py_ssize_t bsize = ABS(Py_SIZE(b));
2924     Py_ssize_t nbdone;          /* # of b digits already multiplied */
2925     PyLongObject *ret;
2926     PyLongObject *bslice = NULL;
2927 
2928     assert(asize > KARATSUBA_CUTOFF);
2929     assert(2 * asize <= bsize);
2930 
2931     /* Allocate result space, and zero it out. */
2932     ret = _PyLong_New(asize + bsize);
2933     if (ret == NULL)
2934         return NULL;
2935     memset(ret->ob_digit, 0, Py_SIZE(ret) * sizeof(digit));
2936 
2937     /* Successive slices of b are copied into bslice. */
2938     bslice = _PyLong_New(asize);
2939     if (bslice == NULL)
2940         goto fail;
2941 
2942     nbdone = 0;
2943     while (bsize > 0) {
2944         PyLongObject *product;
2945         const Py_ssize_t nbtouse = MIN(bsize, asize);
2946 
2947         /* Multiply the next slice of b by a. */
2948         memcpy(bslice->ob_digit, b->ob_digit + nbdone,
2949                nbtouse * sizeof(digit));
2950         Py_SIZE(bslice) = nbtouse;
2951         product = k_mul(a, bslice);
2952         if (product == NULL)
2953             goto fail;
2954 
2955         /* Add into result. */
2956         (void)v_iadd(ret->ob_digit + nbdone, Py_SIZE(ret) - nbdone,
2957                      product->ob_digit, Py_SIZE(product));
2958         Py_DECREF(product);
2959 
2960         bsize -= nbtouse;
2961         nbdone += nbtouse;
2962     }
2963 
2964     Py_DECREF(bslice);
2965     return long_normalize(ret);
2966 
2967   fail:
2968     Py_DECREF(ret);
2969     Py_XDECREF(bslice);
2970     return NULL;
2971 }
2972 
2973 static PyObject *
long_mul(PyLongObject * v,PyLongObject * w)2974 long_mul(PyLongObject *v, PyLongObject *w)
2975 {
2976     PyLongObject *a, *b, *z;
2977 
2978     if (!convert_binop((PyObject *)v, (PyObject *)w, &a, &b)) {
2979         Py_INCREF(Py_NotImplemented);
2980         return Py_NotImplemented;
2981     }
2982 
2983     z = k_mul(a, b);
2984     /* Negate if exactly one of the inputs is negative. */
2985     if (((a->ob_size ^ b->ob_size) < 0) && z)
2986         z->ob_size = -(z->ob_size);
2987     Py_DECREF(a);
2988     Py_DECREF(b);
2989     return (PyObject *)z;
2990 }
2991 
2992 /* The / and % operators are now defined in terms of divmod().
2993    The expression a mod b has the value a - b*floor(a/b).
2994    The long_divrem function gives the remainder after division of
2995    |a| by |b|, with the sign of a.  This is also expressed
2996    as a - b*trunc(a/b), if trunc truncates towards zero.
2997    Some examples:
2998      a           b      a rem b         a mod b
2999      13          10      3               3
3000     -13          10     -3               7
3001      13         -10      3              -7
3002     -13         -10     -3              -3
3003    So, to get from rem to mod, we have to add b if a and b
3004    have different signs.  We then subtract one from the 'div'
3005    part of the outcome to keep the invariant intact. */
3006 
3007 /* Compute
3008  *     *pdiv, *pmod = divmod(v, w)
3009  * NULL can be passed for pdiv or pmod, in which case that part of
3010  * the result is simply thrown away.  The caller owns a reference to
3011  * each of these it requests (does not pass NULL for).
3012  */
3013 static int
l_divmod(PyLongObject * v,PyLongObject * w,PyLongObject ** pdiv,PyLongObject ** pmod)3014 l_divmod(PyLongObject *v, PyLongObject *w,
3015          PyLongObject **pdiv, PyLongObject **pmod)
3016 {
3017     PyLongObject *div, *mod;
3018 
3019     if (long_divrem(v, w, &div, &mod) < 0)
3020         return -1;
3021     if ((Py_SIZE(mod) < 0 && Py_SIZE(w) > 0) ||
3022         (Py_SIZE(mod) > 0 && Py_SIZE(w) < 0)) {
3023         PyLongObject *temp;
3024         PyLongObject *one;
3025         temp = (PyLongObject *) long_add(mod, w);
3026         Py_DECREF(mod);
3027         mod = temp;
3028         if (mod == NULL) {
3029             Py_DECREF(div);
3030             return -1;
3031         }
3032         one = (PyLongObject *) PyLong_FromLong(1L);
3033         if (one == NULL ||
3034             (temp = (PyLongObject *) long_sub(div, one)) == NULL) {
3035             Py_DECREF(mod);
3036             Py_DECREF(div);
3037             Py_XDECREF(one);
3038             return -1;
3039         }
3040         Py_DECREF(one);
3041         Py_DECREF(div);
3042         div = temp;
3043     }
3044     if (pdiv != NULL)
3045         *pdiv = div;
3046     else
3047         Py_DECREF(div);
3048 
3049     if (pmod != NULL)
3050         *pmod = mod;
3051     else
3052         Py_DECREF(mod);
3053 
3054     return 0;
3055 }
3056 
3057 static PyObject *
long_div(PyObject * v,PyObject * w)3058 long_div(PyObject *v, PyObject *w)
3059 {
3060     PyLongObject *a, *b, *div;
3061 
3062     CONVERT_BINOP(v, w, &a, &b);
3063     if (l_divmod(a, b, &div, NULL) < 0)
3064         div = NULL;
3065     Py_DECREF(a);
3066     Py_DECREF(b);
3067     return (PyObject *)div;
3068 }
3069 
3070 static PyObject *
long_classic_div(PyObject * v,PyObject * w)3071 long_classic_div(PyObject *v, PyObject *w)
3072 {
3073     PyLongObject *a, *b, *div;
3074 
3075     CONVERT_BINOP(v, w, &a, &b);
3076     if (Py_DivisionWarningFlag &&
3077         PyErr_Warn(PyExc_DeprecationWarning, "classic long division") < 0)
3078         div = NULL;
3079     else if (l_divmod(a, b, &div, NULL) < 0)
3080         div = NULL;
3081     Py_DECREF(a);
3082     Py_DECREF(b);
3083     return (PyObject *)div;
3084 }
3085 
3086 /* PyLong/PyLong -> float, with correctly rounded result. */
3087 
3088 #define MANT_DIG_DIGITS (DBL_MANT_DIG / PyLong_SHIFT)
3089 #define MANT_DIG_BITS (DBL_MANT_DIG % PyLong_SHIFT)
3090 
3091 static PyObject *
long_true_divide(PyObject * v,PyObject * w)3092 long_true_divide(PyObject *v, PyObject *w)
3093 {
3094     PyLongObject *a, *b, *x;
3095     Py_ssize_t a_size, b_size, shift, extra_bits, diff, x_size, x_bits;
3096     digit mask, low;
3097     int inexact, negate, a_is_small, b_is_small;
3098     double dx, result;
3099 
3100     CONVERT_BINOP(v, w, &a, &b);
3101 
3102     /*
3103        Method in a nutshell:
3104 
3105          0. reduce to case a, b > 0; filter out obvious underflow/overflow
3106          1. choose a suitable integer 'shift'
3107          2. use integer arithmetic to compute x = floor(2**-shift*a/b)
3108          3. adjust x for correct rounding
3109          4. convert x to a double dx with the same value
3110          5. return ldexp(dx, shift).
3111 
3112        In more detail:
3113 
3114        0. For any a, a/0 raises ZeroDivisionError; for nonzero b, 0/b
3115        returns either 0.0 or -0.0, depending on the sign of b.  For a and
3116        b both nonzero, ignore signs of a and b, and add the sign back in
3117        at the end.  Now write a_bits and b_bits for the bit lengths of a
3118        and b respectively (that is, a_bits = 1 + floor(log_2(a)); likewise
3119        for b).  Then
3120 
3121           2**(a_bits - b_bits - 1) < a/b < 2**(a_bits - b_bits + 1).
3122 
3123        So if a_bits - b_bits > DBL_MAX_EXP then a/b > 2**DBL_MAX_EXP and
3124        so overflows.  Similarly, if a_bits - b_bits < DBL_MIN_EXP -
3125        DBL_MANT_DIG - 1 then a/b underflows to 0.  With these cases out of
3126        the way, we can assume that
3127 
3128           DBL_MIN_EXP - DBL_MANT_DIG - 1 <= a_bits - b_bits <= DBL_MAX_EXP.
3129 
3130        1. The integer 'shift' is chosen so that x has the right number of
3131        bits for a double, plus two or three extra bits that will be used
3132        in the rounding decisions.  Writing a_bits and b_bits for the
3133        number of significant bits in a and b respectively, a
3134        straightforward formula for shift is:
3135 
3136           shift = a_bits - b_bits - DBL_MANT_DIG - 2
3137 
3138        This is fine in the usual case, but if a/b is smaller than the
3139        smallest normal float then it can lead to double rounding on an
3140        IEEE 754 platform, giving incorrectly rounded results.  So we
3141        adjust the formula slightly.  The actual formula used is:
3142 
3143            shift = MAX(a_bits - b_bits, DBL_MIN_EXP) - DBL_MANT_DIG - 2
3144 
3145        2. The quantity x is computed by first shifting a (left -shift bits
3146        if shift <= 0, right shift bits if shift > 0) and then dividing by
3147        b.  For both the shift and the division, we keep track of whether
3148        the result is inexact, in a flag 'inexact'; this information is
3149        needed at the rounding stage.
3150 
3151        With the choice of shift above, together with our assumption that
3152        a_bits - b_bits >= DBL_MIN_EXP - DBL_MANT_DIG - 1, it follows
3153        that x >= 1.
3154 
3155        3. Now x * 2**shift <= a/b < (x+1) * 2**shift.  We want to replace
3156        this with an exactly representable float of the form
3157 
3158           round(x/2**extra_bits) * 2**(extra_bits+shift).
3159 
3160        For float representability, we need x/2**extra_bits <
3161        2**DBL_MANT_DIG and extra_bits + shift >= DBL_MIN_EXP -
3162        DBL_MANT_DIG.  This translates to the condition:
3163 
3164           extra_bits >= MAX(x_bits, DBL_MIN_EXP - shift) - DBL_MANT_DIG
3165 
3166        To round, we just modify the bottom digit of x in-place; this can
3167        end up giving a digit with value > PyLONG_MASK, but that's not a
3168        problem since digits can hold values up to 2*PyLONG_MASK+1.
3169 
3170        With the original choices for shift above, extra_bits will always
3171        be 2 or 3.  Then rounding under the round-half-to-even rule, we
3172        round up iff the most significant of the extra bits is 1, and
3173        either: (a) the computation of x in step 2 had an inexact result,
3174        or (b) at least one other of the extra bits is 1, or (c) the least
3175        significant bit of x (above those to be rounded) is 1.
3176 
3177        4. Conversion to a double is straightforward; all floating-point
3178        operations involved in the conversion are exact, so there's no
3179        danger of rounding errors.
3180 
3181        5. Use ldexp(x, shift) to compute x*2**shift, the final result.
3182        The result will always be exactly representable as a double, except
3183        in the case that it overflows.  To avoid dependence on the exact
3184        behaviour of ldexp on overflow, we check for overflow before
3185        applying ldexp.  The result of ldexp is adjusted for sign before
3186        returning.
3187     */
3188 
3189     /* Reduce to case where a and b are both positive. */
3190     a_size = ABS(Py_SIZE(a));
3191     b_size = ABS(Py_SIZE(b));
3192     negate = (Py_SIZE(a) < 0) ^ (Py_SIZE(b) < 0);
3193     if (b_size == 0) {
3194         PyErr_SetString(PyExc_ZeroDivisionError,
3195                         "division by zero");
3196         goto error;
3197     }
3198     if (a_size == 0)
3199         goto underflow_or_zero;
3200 
3201     /* Fast path for a and b small (exactly representable in a double).
3202        Relies on floating-point division being correctly rounded; results
3203        may be subject to double rounding on x86 machines that operate with
3204        the x87 FPU set to 64-bit precision. */
3205     a_is_small = a_size <= MANT_DIG_DIGITS ||
3206         (a_size == MANT_DIG_DIGITS+1 &&
3207          a->ob_digit[MANT_DIG_DIGITS] >> MANT_DIG_BITS == 0);
3208     b_is_small = b_size <= MANT_DIG_DIGITS ||
3209         (b_size == MANT_DIG_DIGITS+1 &&
3210          b->ob_digit[MANT_DIG_DIGITS] >> MANT_DIG_BITS == 0);
3211     if (a_is_small && b_is_small) {
3212         double da, db;
3213         da = a->ob_digit[--a_size];
3214         while (a_size > 0)
3215             da = da * PyLong_BASE + a->ob_digit[--a_size];
3216         db = b->ob_digit[--b_size];
3217         while (b_size > 0)
3218             db = db * PyLong_BASE + b->ob_digit[--b_size];
3219         result = da / db;
3220         goto success;
3221     }
3222 
3223     /* Catch obvious cases of underflow and overflow */
3224     diff = a_size - b_size;
3225     if (diff > PY_SSIZE_T_MAX/PyLong_SHIFT - 1)
3226         /* Extreme overflow */
3227         goto overflow;
3228     else if (diff < 1 - PY_SSIZE_T_MAX/PyLong_SHIFT)
3229         /* Extreme underflow */
3230         goto underflow_or_zero;
3231     /* Next line is now safe from overflowing a Py_ssize_t */
3232     diff = diff * PyLong_SHIFT + bits_in_digit(a->ob_digit[a_size - 1]) -
3233         bits_in_digit(b->ob_digit[b_size - 1]);
3234     /* Now diff = a_bits - b_bits. */
3235     if (diff > DBL_MAX_EXP)
3236         goto overflow;
3237     else if (diff < DBL_MIN_EXP - DBL_MANT_DIG - 1)
3238         goto underflow_or_zero;
3239 
3240     /* Choose value for shift; see comments for step 1 above. */
3241     shift = MAX(diff, DBL_MIN_EXP) - DBL_MANT_DIG - 2;
3242 
3243     inexact = 0;
3244 
3245     /* x = abs(a * 2**-shift) */
3246     if (shift <= 0) {
3247         Py_ssize_t i, shift_digits = -shift / PyLong_SHIFT;
3248         digit rem;
3249         /* x = a << -shift */
3250         if (a_size >= PY_SSIZE_T_MAX - 1 - shift_digits) {
3251             /* In practice, it's probably impossible to end up
3252                here.  Both a and b would have to be enormous,
3253                using close to SIZE_T_MAX bytes of memory each. */
3254             PyErr_SetString(PyExc_OverflowError,
3255                             "intermediate overflow during division");
3256             goto error;
3257         }
3258         x = _PyLong_New(a_size + shift_digits + 1);
3259         if (x == NULL)
3260             goto error;
3261         for (i = 0; i < shift_digits; i++)
3262             x->ob_digit[i] = 0;
3263         rem = v_lshift(x->ob_digit + shift_digits, a->ob_digit,
3264                        a_size, -shift % PyLong_SHIFT);
3265         x->ob_digit[a_size + shift_digits] = rem;
3266     }
3267     else {
3268         Py_ssize_t shift_digits = shift / PyLong_SHIFT;
3269         digit rem;
3270         /* x = a >> shift */
3271         assert(a_size >= shift_digits);
3272         x = _PyLong_New(a_size - shift_digits);
3273         if (x == NULL)
3274             goto error;
3275         rem = v_rshift(x->ob_digit, a->ob_digit + shift_digits,
3276                        a_size - shift_digits, shift % PyLong_SHIFT);
3277         /* set inexact if any of the bits shifted out is nonzero */
3278         if (rem)
3279             inexact = 1;
3280         while (!inexact && shift_digits > 0)
3281             if (a->ob_digit[--shift_digits])
3282                 inexact = 1;
3283     }
3284     long_normalize(x);
3285     x_size = Py_SIZE(x);
3286 
3287     /* x //= b. If the remainder is nonzero, set inexact.  We own the only
3288        reference to x, so it's safe to modify it in-place. */
3289     if (b_size == 1) {
3290         digit rem = inplace_divrem1(x->ob_digit, x->ob_digit, x_size,
3291                               b->ob_digit[0]);
3292         long_normalize(x);
3293         if (rem)
3294             inexact = 1;
3295     }
3296     else {
3297         PyLongObject *div, *rem;
3298         div = x_divrem(x, b, &rem);
3299         Py_DECREF(x);
3300         x = div;
3301         if (x == NULL)
3302             goto error;
3303         if (Py_SIZE(rem))
3304             inexact = 1;
3305         Py_DECREF(rem);
3306     }
3307     x_size = ABS(Py_SIZE(x));
3308     assert(x_size > 0); /* result of division is never zero */
3309     x_bits = (x_size-1)*PyLong_SHIFT+bits_in_digit(x->ob_digit[x_size-1]);
3310 
3311     /* The number of extra bits that have to be rounded away. */
3312     extra_bits = MAX(x_bits, DBL_MIN_EXP - shift) - DBL_MANT_DIG;
3313     assert(extra_bits == 2 || extra_bits == 3);
3314 
3315     /* Round by directly modifying the low digit of x. */
3316     mask = (digit)1 << (extra_bits - 1);
3317     low = x->ob_digit[0] | inexact;
3318     if ((low & mask) && (low & (3U*mask-1U)))
3319         low += mask;
3320     x->ob_digit[0] = low & ~(2U*mask-1U);
3321 
3322     /* Convert x to a double dx; the conversion is exact. */
3323     dx = x->ob_digit[--x_size];
3324     while (x_size > 0)
3325         dx = dx * PyLong_BASE + x->ob_digit[--x_size];
3326     Py_DECREF(x);
3327 
3328     /* Check whether ldexp result will overflow a double. */
3329     if (shift + x_bits >= DBL_MAX_EXP &&
3330         (shift + x_bits > DBL_MAX_EXP || dx == ldexp(1.0, (int)x_bits)))
3331         goto overflow;
3332     result = ldexp(dx, (int)shift);
3333 
3334   success:
3335     Py_DECREF(a);
3336     Py_DECREF(b);
3337     return PyFloat_FromDouble(negate ? -result : result);
3338 
3339   underflow_or_zero:
3340     Py_DECREF(a);
3341     Py_DECREF(b);
3342     return PyFloat_FromDouble(negate ? -0.0 : 0.0);
3343 
3344   overflow:
3345     PyErr_SetString(PyExc_OverflowError,
3346                     "integer division result too large for a float");
3347   error:
3348     Py_DECREF(a);
3349     Py_DECREF(b);
3350     return NULL;
3351 }
3352 
3353 static PyObject *
long_mod(PyObject * v,PyObject * w)3354 long_mod(PyObject *v, PyObject *w)
3355 {
3356     PyLongObject *a, *b, *mod;
3357 
3358     CONVERT_BINOP(v, w, &a, &b);
3359 
3360     if (l_divmod(a, b, NULL, &mod) < 0)
3361         mod = NULL;
3362     Py_DECREF(a);
3363     Py_DECREF(b);
3364     return (PyObject *)mod;
3365 }
3366 
3367 static PyObject *
long_divmod(PyObject * v,PyObject * w)3368 long_divmod(PyObject *v, PyObject *w)
3369 {
3370     PyLongObject *a, *b, *div, *mod;
3371     PyObject *z;
3372 
3373     CONVERT_BINOP(v, w, &a, &b);
3374 
3375     if (l_divmod(a, b, &div, &mod) < 0) {
3376         Py_DECREF(a);
3377         Py_DECREF(b);
3378         return NULL;
3379     }
3380     z = PyTuple_New(2);
3381     if (z != NULL) {
3382         PyTuple_SetItem(z, 0, (PyObject *) div);
3383         PyTuple_SetItem(z, 1, (PyObject *) mod);
3384     }
3385     else {
3386         Py_DECREF(div);
3387         Py_DECREF(mod);
3388     }
3389     Py_DECREF(a);
3390     Py_DECREF(b);
3391     return z;
3392 }
3393 
3394 /* pow(v, w, x) */
3395 static PyObject *
long_pow(PyObject * v,PyObject * w,PyObject * x)3396 long_pow(PyObject *v, PyObject *w, PyObject *x)
3397 {
3398     PyLongObject *a, *b, *c; /* a,b,c = v,w,x */
3399     int negativeOutput = 0;  /* if x<0 return negative output */
3400 
3401     PyLongObject *z = NULL;  /* accumulated result */
3402     Py_ssize_t i, j, k;             /* counters */
3403     PyLongObject *temp = NULL;
3404 
3405     /* 5-ary values.  If the exponent is large enough, table is
3406      * precomputed so that table[i] == a**i % c for i in range(32).
3407      */
3408     PyLongObject *table[32] = {0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
3409                                0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0};
3410 
3411     /* a, b, c = v, w, x */
3412     CONVERT_BINOP(v, w, &a, &b);
3413     if (PyLong_Check(x)) {
3414         c = (PyLongObject *)x;
3415         Py_INCREF(x);
3416     }
3417     else if (PyInt_Check(x)) {
3418         c = (PyLongObject *)PyLong_FromLong(PyInt_AS_LONG(x));
3419         if (c == NULL)
3420             goto Error;
3421     }
3422     else if (x == Py_None)
3423         c = NULL;
3424     else {
3425         Py_DECREF(a);
3426         Py_DECREF(b);
3427         Py_INCREF(Py_NotImplemented);
3428         return Py_NotImplemented;
3429     }
3430 
3431     if (Py_SIZE(b) < 0) {  /* if exponent is negative */
3432         if (c) {
3433             PyErr_SetString(PyExc_TypeError, "pow() 2nd argument "
3434                             "cannot be negative when 3rd argument specified");
3435             goto Error;
3436         }
3437         else {
3438             /* else return a float.  This works because we know
3439                that this calls float_pow() which converts its
3440                arguments to double. */
3441             Py_DECREF(a);
3442             Py_DECREF(b);
3443             return PyFloat_Type.tp_as_number->nb_power(v, w, x);
3444         }
3445     }
3446 
3447     if (c) {
3448         /* if modulus == 0:
3449                raise ValueError() */
3450         if (Py_SIZE(c) == 0) {
3451             PyErr_SetString(PyExc_ValueError,
3452                             "pow() 3rd argument cannot be 0");
3453             goto Error;
3454         }
3455 
3456         /* if modulus < 0:
3457                negativeOutput = True
3458                modulus = -modulus */
3459         if (Py_SIZE(c) < 0) {
3460             negativeOutput = 1;
3461             temp = (PyLongObject *)_PyLong_Copy(c);
3462             if (temp == NULL)
3463                 goto Error;
3464             Py_DECREF(c);
3465             c = temp;
3466             temp = NULL;
3467             c->ob_size = - c->ob_size;
3468         }
3469 
3470         /* if modulus == 1:
3471                return 0 */
3472         if ((Py_SIZE(c) == 1) && (c->ob_digit[0] == 1)) {
3473             z = (PyLongObject *)PyLong_FromLong(0L);
3474             goto Done;
3475         }
3476 
3477         /* Reduce base by modulus in some cases:
3478            1. If base < 0.  Forcing the base non-negative makes things easier.
3479            2. If base is obviously larger than the modulus.  The "small
3480               exponent" case later can multiply directly by base repeatedly,
3481               while the "large exponent" case multiplies directly by base 31
3482               times.  It can be unboundedly faster to multiply by
3483               base % modulus instead.
3484            We could _always_ do this reduction, but l_divmod() isn't cheap,
3485            so we only do it when it buys something. */
3486         if (Py_SIZE(a) < 0 || Py_SIZE(a) > Py_SIZE(c)) {
3487             if (l_divmod(a, c, NULL, &temp) < 0)
3488                 goto Error;
3489             Py_DECREF(a);
3490             a = temp;
3491             temp = NULL;
3492         }
3493     }
3494 
3495     /* At this point a, b, and c are guaranteed non-negative UNLESS
3496        c is NULL, in which case a may be negative. */
3497 
3498     z = (PyLongObject *)PyLong_FromLong(1L);
3499     if (z == NULL)
3500         goto Error;
3501 
3502     /* Perform a modular reduction, X = X % c, but leave X alone if c
3503      * is NULL.
3504      */
3505 #define REDUCE(X)                                       \
3506     do {                                                \
3507         if (c != NULL) {                                \
3508             if (l_divmod(X, c, NULL, &temp) < 0)        \
3509                 goto Error;                             \
3510             Py_XDECREF(X);                              \
3511             X = temp;                                   \
3512             temp = NULL;                                \
3513         }                                               \
3514     } while(0)
3515 
3516     /* Multiply two values, then reduce the result:
3517        result = X*Y % c.  If c is NULL, skip the mod. */
3518 #define MULT(X, Y, result)                      \
3519     do {                                        \
3520         temp = (PyLongObject *)long_mul(X, Y);  \
3521         if (temp == NULL)                       \
3522             goto Error;                         \
3523         Py_XDECREF(result);                     \
3524         result = temp;                          \
3525         temp = NULL;                            \
3526         REDUCE(result);                         \
3527     } while(0)
3528 
3529     if (Py_SIZE(b) <= FIVEARY_CUTOFF) {
3530         /* Left-to-right binary exponentiation (HAC Algorithm 14.79) */
3531         /* http://www.cacr.math.uwaterloo.ca/hac/about/chap14.pdf    */
3532         for (i = Py_SIZE(b) - 1; i >= 0; --i) {
3533             digit bi = b->ob_digit[i];
3534 
3535             for (j = (digit)1 << (PyLong_SHIFT-1); j != 0; j >>= 1) {
3536                 MULT(z, z, z);
3537                 if (bi & j)
3538                     MULT(z, a, z);
3539             }
3540         }
3541     }
3542     else {
3543         /* Left-to-right 5-ary exponentiation (HAC Algorithm 14.82) */
3544         Py_INCREF(z);           /* still holds 1L */
3545         table[0] = z;
3546         for (i = 1; i < 32; ++i)
3547             MULT(table[i-1], a, table[i]);
3548 
3549         for (i = Py_SIZE(b) - 1; i >= 0; --i) {
3550             const digit bi = b->ob_digit[i];
3551 
3552             for (j = PyLong_SHIFT - 5; j >= 0; j -= 5) {
3553                 const int index = (bi >> j) & 0x1f;
3554                 for (k = 0; k < 5; ++k)
3555                     MULT(z, z, z);
3556                 if (index)
3557                     MULT(z, table[index], z);
3558             }
3559         }
3560     }
3561 
3562     if (negativeOutput && (Py_SIZE(z) != 0)) {
3563         temp = (PyLongObject *)long_sub(z, c);
3564         if (temp == NULL)
3565             goto Error;
3566         Py_DECREF(z);
3567         z = temp;
3568         temp = NULL;
3569     }
3570     goto Done;
3571 
3572   Error:
3573     if (z != NULL) {
3574         Py_DECREF(z);
3575         z = NULL;
3576     }
3577     /* fall through */
3578   Done:
3579     if (Py_SIZE(b) > FIVEARY_CUTOFF) {
3580         for (i = 0; i < 32; ++i)
3581             Py_XDECREF(table[i]);
3582     }
3583     Py_DECREF(a);
3584     Py_DECREF(b);
3585     Py_XDECREF(c);
3586     Py_XDECREF(temp);
3587     return (PyObject *)z;
3588 }
3589 
3590 static PyObject *
long_invert(PyLongObject * v)3591 long_invert(PyLongObject *v)
3592 {
3593     /* Implement ~x as -(x+1) */
3594     PyLongObject *x;
3595     PyLongObject *w;
3596     w = (PyLongObject *)PyLong_FromLong(1L);
3597     if (w == NULL)
3598         return NULL;
3599     x = (PyLongObject *) long_add(v, w);
3600     Py_DECREF(w);
3601     if (x == NULL)
3602         return NULL;
3603     Py_SIZE(x) = -(Py_SIZE(x));
3604     return (PyObject *)x;
3605 }
3606 
3607 static PyObject *
long_neg(PyLongObject * v)3608 long_neg(PyLongObject *v)
3609 {
3610     PyLongObject *z;
3611     if (v->ob_size == 0 && PyLong_CheckExact(v)) {
3612         /* -0 == 0 */
3613         Py_INCREF(v);
3614         return (PyObject *) v;
3615     }
3616     z = (PyLongObject *)_PyLong_Copy(v);
3617     if (z != NULL)
3618         z->ob_size = -(v->ob_size);
3619     return (PyObject *)z;
3620 }
3621 
3622 static PyObject *
long_abs(PyLongObject * v)3623 long_abs(PyLongObject *v)
3624 {
3625     if (v->ob_size < 0)
3626         return long_neg(v);
3627     else
3628         return long_long((PyObject *)v);
3629 }
3630 
3631 static int
long_nonzero(PyLongObject * v)3632 long_nonzero(PyLongObject *v)
3633 {
3634     return Py_SIZE(v) != 0;
3635 }
3636 
3637 static PyObject *
long_rshift(PyLongObject * v,PyLongObject * w)3638 long_rshift(PyLongObject *v, PyLongObject *w)
3639 {
3640     PyLongObject *a, *b;
3641     PyLongObject *z = NULL;
3642     Py_ssize_t shiftby, newsize, wordshift, loshift, hishift, i, j;
3643     digit lomask, himask;
3644 
3645     CONVERT_BINOP((PyObject *)v, (PyObject *)w, &a, &b);
3646 
3647     if (Py_SIZE(a) < 0) {
3648         /* Right shifting negative numbers is harder */
3649         PyLongObject *a1, *a2;
3650         a1 = (PyLongObject *) long_invert(a);
3651         if (a1 == NULL)
3652             goto rshift_error;
3653         a2 = (PyLongObject *) long_rshift(a1, b);
3654         Py_DECREF(a1);
3655         if (a2 == NULL)
3656             goto rshift_error;
3657         z = (PyLongObject *) long_invert(a2);
3658         Py_DECREF(a2);
3659     }
3660     else {
3661         shiftby = PyLong_AsSsize_t((PyObject *)b);
3662         if (shiftby == -1L && PyErr_Occurred())
3663             goto rshift_error;
3664         if (shiftby < 0) {
3665             PyErr_SetString(PyExc_ValueError,
3666                             "negative shift count");
3667             goto rshift_error;
3668         }
3669         wordshift = shiftby / PyLong_SHIFT;
3670         newsize = ABS(Py_SIZE(a)) - wordshift;
3671         if (newsize <= 0) {
3672             z = _PyLong_New(0);
3673             Py_DECREF(a);
3674             Py_DECREF(b);
3675             return (PyObject *)z;
3676         }
3677         loshift = shiftby % PyLong_SHIFT;
3678         hishift = PyLong_SHIFT - loshift;
3679         lomask = ((digit)1 << hishift) - 1;
3680         himask = PyLong_MASK ^ lomask;
3681         z = _PyLong_New(newsize);
3682         if (z == NULL)
3683             goto rshift_error;
3684         if (Py_SIZE(a) < 0)
3685             Py_SIZE(z) = -(Py_SIZE(z));
3686         for (i = 0, j = wordshift; i < newsize; i++, j++) {
3687             z->ob_digit[i] = (a->ob_digit[j] >> loshift) & lomask;
3688             if (i+1 < newsize)
3689                 z->ob_digit[i] |= (a->ob_digit[j+1] << hishift) & himask;
3690         }
3691         z = long_normalize(z);
3692     }
3693   rshift_error:
3694     Py_DECREF(a);
3695     Py_DECREF(b);
3696     return (PyObject *) z;
3697 
3698 }
3699 
3700 static PyObject *
long_lshift(PyObject * v,PyObject * w)3701 long_lshift(PyObject *v, PyObject *w)
3702 {
3703     /* This version due to Tim Peters */
3704     PyLongObject *a, *b;
3705     PyLongObject *z = NULL;
3706     Py_ssize_t shiftby, oldsize, newsize, wordshift, remshift, i, j;
3707     twodigits accum;
3708 
3709     CONVERT_BINOP(v, w, &a, &b);
3710 
3711     shiftby = PyLong_AsSsize_t((PyObject *)b);
3712     if (shiftby == -1L && PyErr_Occurred())
3713         goto out;
3714     if (shiftby < 0) {
3715         PyErr_SetString(PyExc_ValueError, "negative shift count");
3716         goto out;
3717     }
3718 
3719     if (Py_SIZE(a) == 0) {
3720         z = (PyLongObject *)PyLong_FromLong(0);
3721         goto out;
3722     }
3723 
3724     /* wordshift, remshift = divmod(shiftby, PyLong_SHIFT) */
3725     wordshift = shiftby / PyLong_SHIFT;
3726     remshift  = shiftby - wordshift * PyLong_SHIFT;
3727 
3728     oldsize = ABS(a->ob_size);
3729     newsize = oldsize + wordshift;
3730     if (remshift)
3731         ++newsize;
3732     z = _PyLong_New(newsize);
3733     if (z == NULL)
3734         goto out;
3735     if (a->ob_size < 0)
3736         z->ob_size = -(z->ob_size);
3737     for (i = 0; i < wordshift; i++)
3738         z->ob_digit[i] = 0;
3739     accum = 0;
3740     for (i = wordshift, j = 0; j < oldsize; i++, j++) {
3741         accum |= (twodigits)a->ob_digit[j] << remshift;
3742         z->ob_digit[i] = (digit)(accum & PyLong_MASK);
3743         accum >>= PyLong_SHIFT;
3744     }
3745     if (remshift)
3746         z->ob_digit[newsize-1] = (digit)accum;
3747     else
3748         assert(!accum);
3749     z = long_normalize(z);
3750   out:
3751     Py_DECREF(a);
3752     Py_DECREF(b);
3753     return (PyObject *) z;
3754 }
3755 
3756 /* Compute two's complement of digit vector a[0:m], writing result to
3757    z[0:m].  The digit vector a need not be normalized, but should not
3758    be entirely zero.  a and z may point to the same digit vector. */
3759 
3760 static void
v_complement(digit * z,digit * a,Py_ssize_t m)3761 v_complement(digit *z, digit *a, Py_ssize_t m)
3762 {
3763     Py_ssize_t i;
3764     digit carry = 1;
3765     for (i = 0; i < m; ++i) {
3766         carry += a[i] ^ PyLong_MASK;
3767         z[i] = carry & PyLong_MASK;
3768         carry >>= PyLong_SHIFT;
3769     }
3770     assert(carry == 0);
3771 }
3772 
3773 /* Bitwise and/xor/or operations */
3774 
3775 static PyObject *
long_bitwise(PyLongObject * a,int op,PyLongObject * b)3776 long_bitwise(PyLongObject *a,
3777              int op,  /* '&', '|', '^' */
3778              PyLongObject *b)
3779 {
3780     int nega, negb, negz;
3781     Py_ssize_t size_a, size_b, size_z, i;
3782     PyLongObject *z;
3783 
3784     /* Bitwise operations for negative numbers operate as though
3785        on a two's complement representation.  So convert arguments
3786        from sign-magnitude to two's complement, and convert the
3787        result back to sign-magnitude at the end. */
3788 
3789     /* If a is negative, replace it by its two's complement. */
3790     size_a = ABS(Py_SIZE(a));
3791     nega = Py_SIZE(a) < 0;
3792     if (nega) {
3793         z = _PyLong_New(size_a);
3794         if (z == NULL)
3795             return NULL;
3796         v_complement(z->ob_digit, a->ob_digit, size_a);
3797         a = z;
3798     }
3799     else
3800         /* Keep reference count consistent. */
3801         Py_INCREF(a);
3802 
3803     /* Same for b. */
3804     size_b = ABS(Py_SIZE(b));
3805     negb = Py_SIZE(b) < 0;
3806     if (negb) {
3807         z = _PyLong_New(size_b);
3808         if (z == NULL) {
3809             Py_DECREF(a);
3810             return NULL;
3811         }
3812         v_complement(z->ob_digit, b->ob_digit, size_b);
3813         b = z;
3814     }
3815     else
3816         Py_INCREF(b);
3817 
3818     /* Swap a and b if necessary to ensure size_a >= size_b. */
3819     if (size_a < size_b) {
3820         z = a; a = b; b = z;
3821         size_z = size_a; size_a = size_b; size_b = size_z;
3822         negz = nega; nega = negb; negb = negz;
3823     }
3824 
3825     /* JRH: The original logic here was to allocate the result value (z)
3826        as the longer of the two operands.  However, there are some cases
3827        where the result is guaranteed to be shorter than that: AND of two
3828        positives, OR of two negatives: use the shorter number.  AND with
3829        mixed signs: use the positive number.  OR with mixed signs: use the
3830        negative number.
3831     */
3832     switch (op) {
3833     case '^':
3834         negz = nega ^ negb;
3835         size_z = size_a;
3836         break;
3837     case '&':
3838         negz = nega & negb;
3839         size_z = negb ? size_a : size_b;
3840         break;
3841     case '|':
3842         negz = nega | negb;
3843         size_z = negb ? size_b : size_a;
3844         break;
3845     default:
3846         PyErr_BadArgument();
3847         return NULL;
3848     }
3849 
3850     /* We allow an extra digit if z is negative, to make sure that
3851        the final two's complement of z doesn't overflow. */
3852     z = _PyLong_New(size_z + negz);
3853     if (z == NULL) {
3854         Py_DECREF(a);
3855         Py_DECREF(b);
3856         return NULL;
3857     }
3858 
3859     /* Compute digits for overlap of a and b. */
3860     switch(op) {
3861     case '&':
3862         for (i = 0; i < size_b; ++i)
3863             z->ob_digit[i] = a->ob_digit[i] & b->ob_digit[i];
3864         break;
3865     case '|':
3866         for (i = 0; i < size_b; ++i)
3867             z->ob_digit[i] = a->ob_digit[i] | b->ob_digit[i];
3868         break;
3869     case '^':
3870         for (i = 0; i < size_b; ++i)
3871             z->ob_digit[i] = a->ob_digit[i] ^ b->ob_digit[i];
3872         break;
3873     default:
3874         PyErr_BadArgument();
3875         return NULL;
3876     }
3877 
3878     /* Copy any remaining digits of a, inverting if necessary. */
3879     if (op == '^' && negb)
3880         for (; i < size_z; ++i)
3881             z->ob_digit[i] = a->ob_digit[i] ^ PyLong_MASK;
3882     else if (i < size_z)
3883         memcpy(&z->ob_digit[i], &a->ob_digit[i],
3884                (size_z-i)*sizeof(digit));
3885 
3886     /* Complement result if negative. */
3887     if (negz) {
3888         Py_SIZE(z) = -(Py_SIZE(z));
3889         z->ob_digit[size_z] = PyLong_MASK;
3890         v_complement(z->ob_digit, z->ob_digit, size_z+1);
3891     }
3892 
3893     Py_DECREF(a);
3894     Py_DECREF(b);
3895     return (PyObject *)long_normalize(z);
3896 }
3897 
3898 static PyObject *
long_and(PyObject * v,PyObject * w)3899 long_and(PyObject *v, PyObject *w)
3900 {
3901     PyLongObject *a, *b;
3902     PyObject *c;
3903     CONVERT_BINOP(v, w, &a, &b);
3904     c = long_bitwise(a, '&', b);
3905     Py_DECREF(a);
3906     Py_DECREF(b);
3907     return c;
3908 }
3909 
3910 static PyObject *
long_xor(PyObject * v,PyObject * w)3911 long_xor(PyObject *v, PyObject *w)
3912 {
3913     PyLongObject *a, *b;
3914     PyObject *c;
3915     CONVERT_BINOP(v, w, &a, &b);
3916     c = long_bitwise(a, '^', b);
3917     Py_DECREF(a);
3918     Py_DECREF(b);
3919     return c;
3920 }
3921 
3922 static PyObject *
long_or(PyObject * v,PyObject * w)3923 long_or(PyObject *v, PyObject *w)
3924 {
3925     PyLongObject *a, *b;
3926     PyObject *c;
3927     CONVERT_BINOP(v, w, &a, &b);
3928     c = long_bitwise(a, '|', b);
3929     Py_DECREF(a);
3930     Py_DECREF(b);
3931     return c;
3932 }
3933 
3934 static int
long_coerce(PyObject ** pv,PyObject ** pw)3935 long_coerce(PyObject **pv, PyObject **pw)
3936 {
3937     if (PyInt_Check(*pw)) {
3938         *pw = PyLong_FromLong(PyInt_AS_LONG(*pw));
3939         if (*pw == NULL)
3940             return -1;
3941         Py_INCREF(*pv);
3942         return 0;
3943     }
3944     else if (PyLong_Check(*pw)) {
3945         Py_INCREF(*pv);
3946         Py_INCREF(*pw);
3947         return 0;
3948     }
3949     return 1; /* Can't do it */
3950 }
3951 
3952 static PyObject *
long_long(PyObject * v)3953 long_long(PyObject *v)
3954 {
3955     if (PyLong_CheckExact(v))
3956         Py_INCREF(v);
3957     else
3958         v = _PyLong_Copy((PyLongObject *)v);
3959     return v;
3960 }
3961 
3962 static PyObject *
long_int(PyObject * v)3963 long_int(PyObject *v)
3964 {
3965     long x;
3966     x = PyLong_AsLong(v);
3967     if (PyErr_Occurred()) {
3968         if (PyErr_ExceptionMatches(PyExc_OverflowError)) {
3969             PyErr_Clear();
3970             if (PyLong_CheckExact(v)) {
3971                 Py_INCREF(v);
3972                 return v;
3973             }
3974             else
3975                 return _PyLong_Copy((PyLongObject *)v);
3976         }
3977         else
3978             return NULL;
3979     }
3980     return PyInt_FromLong(x);
3981 }
3982 
3983 static PyObject *
long_float(PyObject * v)3984 long_float(PyObject *v)
3985 {
3986     double result;
3987     result = PyLong_AsDouble(v);
3988     if (result == -1.0 && PyErr_Occurred())
3989         return NULL;
3990     return PyFloat_FromDouble(result);
3991 }
3992 
3993 static PyObject *
long_oct(PyObject * v)3994 long_oct(PyObject *v)
3995 {
3996     return _PyLong_Format(v, 8, 1, 0);
3997 }
3998 
3999 static PyObject *
long_hex(PyObject * v)4000 long_hex(PyObject *v)
4001 {
4002     return _PyLong_Format(v, 16, 1, 0);
4003 }
4004 
4005 static PyObject *
4006 long_subtype_new(PyTypeObject *type, PyObject *args, PyObject *kwds);
4007 
4008 static PyObject *
long_new(PyTypeObject * type,PyObject * args,PyObject * kwds)4009 long_new(PyTypeObject *type, PyObject *args, PyObject *kwds)
4010 {
4011     PyObject *x = NULL;
4012     int base = -909;                         /* unlikely! */
4013     static char *kwlist[] = {"x", "base", 0};
4014 
4015     if (type != &PyLong_Type)
4016         return long_subtype_new(type, args, kwds); /* Wimp out */
4017     if (!PyArg_ParseTupleAndKeywords(args, kwds, "|Oi:long", kwlist,
4018                                      &x, &base))
4019         return NULL;
4020     if (x == NULL) {
4021         if (base != -909) {
4022             PyErr_SetString(PyExc_TypeError,
4023                             "long() missing string argument");
4024             return NULL;
4025         }
4026         return PyLong_FromLong(0L);
4027     }
4028     if (base == -909)
4029         return PyNumber_Long(x);
4030     else if (PyString_Check(x)) {
4031         /* Since PyLong_FromString doesn't have a length parameter,
4032          * check here for possible NULs in the string. */
4033         char *string = PyString_AS_STRING(x);
4034         if (strlen(string) != (size_t)PyString_Size(x)) {
4035             /* create a repr() of the input string,
4036              * just like PyLong_FromString does. */
4037             PyObject *srepr;
4038             srepr = PyObject_Repr(x);
4039             if (srepr == NULL)
4040                 return NULL;
4041             PyErr_Format(PyExc_ValueError,
4042                          "invalid literal for long() with base %d: %s",
4043                          base, PyString_AS_STRING(srepr));
4044             Py_DECREF(srepr);
4045             return NULL;
4046         }
4047         return PyLong_FromString(PyString_AS_STRING(x), NULL, base);
4048     }
4049 #ifdef Py_USING_UNICODE
4050     else if (PyUnicode_Check(x))
4051         return PyLong_FromUnicode(PyUnicode_AS_UNICODE(x),
4052                                   PyUnicode_GET_SIZE(x),
4053                                   base);
4054 #endif
4055     else {
4056         PyErr_SetString(PyExc_TypeError,
4057                         "long() can't convert non-string with explicit base");
4058         return NULL;
4059     }
4060 }
4061 
4062 /* Wimpy, slow approach to tp_new calls for subtypes of long:
4063    first create a regular long from whatever arguments we got,
4064    then allocate a subtype instance and initialize it from
4065    the regular long.  The regular long is then thrown away.
4066 */
4067 static PyObject *
long_subtype_new(PyTypeObject * type,PyObject * args,PyObject * kwds)4068 long_subtype_new(PyTypeObject *type, PyObject *args, PyObject *kwds)
4069 {
4070     PyLongObject *tmp, *newobj;
4071     Py_ssize_t i, n;
4072 
4073     assert(PyType_IsSubtype(type, &PyLong_Type));
4074     tmp = (PyLongObject *)long_new(&PyLong_Type, args, kwds);
4075     if (tmp == NULL)
4076         return NULL;
4077     assert(PyLong_Check(tmp));
4078     n = Py_SIZE(tmp);
4079     if (n < 0)
4080         n = -n;
4081     newobj = (PyLongObject *)type->tp_alloc(type, n);
4082     if (newobj == NULL) {
4083         Py_DECREF(tmp);
4084         return NULL;
4085     }
4086     assert(PyLong_Check(newobj));
4087     Py_SIZE(newobj) = Py_SIZE(tmp);
4088     for (i = 0; i < n; i++)
4089         newobj->ob_digit[i] = tmp->ob_digit[i];
4090     Py_DECREF(tmp);
4091     return (PyObject *)newobj;
4092 }
4093 
4094 static PyObject *
long_getnewargs(PyLongObject * v)4095 long_getnewargs(PyLongObject *v)
4096 {
4097     return Py_BuildValue("(N)", _PyLong_Copy(v));
4098 }
4099 
4100 static PyObject *
long_get0(PyLongObject * v,void * context)4101 long_get0(PyLongObject *v, void *context) {
4102     return PyLong_FromLong(0L);
4103 }
4104 
4105 static PyObject *
long_get1(PyLongObject * v,void * context)4106 long_get1(PyLongObject *v, void *context) {
4107     return PyLong_FromLong(1L);
4108 }
4109 
4110 static PyObject *
long__format__(PyObject * self,PyObject * args)4111 long__format__(PyObject *self, PyObject *args)
4112 {
4113     PyObject *format_spec;
4114 
4115     if (!PyArg_ParseTuple(args, "O:__format__", &format_spec))
4116         return NULL;
4117     if (PyBytes_Check(format_spec))
4118         return _PyLong_FormatAdvanced(self,
4119                                       PyBytes_AS_STRING(format_spec),
4120                                       PyBytes_GET_SIZE(format_spec));
4121     if (PyUnicode_Check(format_spec)) {
4122         /* Convert format_spec to a str */
4123         PyObject *result;
4124         PyObject *str_spec = PyObject_Str(format_spec);
4125 
4126         if (str_spec == NULL)
4127             return NULL;
4128 
4129         result = _PyLong_FormatAdvanced(self,
4130                                         PyBytes_AS_STRING(str_spec),
4131                                         PyBytes_GET_SIZE(str_spec));
4132 
4133         Py_DECREF(str_spec);
4134         return result;
4135     }
4136     PyErr_SetString(PyExc_TypeError, "__format__ requires str or unicode");
4137     return NULL;
4138 }
4139 
4140 static PyObject *
long_sizeof(PyLongObject * v)4141 long_sizeof(PyLongObject *v)
4142 {
4143     Py_ssize_t res;
4144 
4145     res = v->ob_type->tp_basicsize + ABS(Py_SIZE(v))*sizeof(digit);
4146     return PyInt_FromSsize_t(res);
4147 }
4148 
4149 static PyObject *
long_bit_length(PyLongObject * v)4150 long_bit_length(PyLongObject *v)
4151 {
4152     PyLongObject *result, *x, *y;
4153     Py_ssize_t ndigits, msd_bits = 0;
4154     digit msd;
4155 
4156     assert(v != NULL);
4157     assert(PyLong_Check(v));
4158 
4159     ndigits = ABS(Py_SIZE(v));
4160     if (ndigits == 0)
4161         return PyInt_FromLong(0);
4162 
4163     msd = v->ob_digit[ndigits-1];
4164     while (msd >= 32) {
4165         msd_bits += 6;
4166         msd >>= 6;
4167     }
4168     msd_bits += (long)(BitLengthTable[msd]);
4169 
4170     if (ndigits <= PY_SSIZE_T_MAX/PyLong_SHIFT)
4171         return PyInt_FromSsize_t((ndigits-1)*PyLong_SHIFT + msd_bits);
4172 
4173     /* expression above may overflow; use Python integers instead */
4174     result = (PyLongObject *)PyLong_FromSsize_t(ndigits - 1);
4175     if (result == NULL)
4176         return NULL;
4177     x = (PyLongObject *)PyLong_FromLong(PyLong_SHIFT);
4178     if (x == NULL)
4179         goto error;
4180     y = (PyLongObject *)long_mul(result, x);
4181     Py_DECREF(x);
4182     if (y == NULL)
4183         goto error;
4184     Py_DECREF(result);
4185     result = y;
4186 
4187     x = (PyLongObject *)PyLong_FromLong((long)msd_bits);
4188     if (x == NULL)
4189         goto error;
4190     y = (PyLongObject *)long_add(result, x);
4191     Py_DECREF(x);
4192     if (y == NULL)
4193         goto error;
4194     Py_DECREF(result);
4195     result = y;
4196 
4197     return (PyObject *)result;
4198 
4199   error:
4200     Py_DECREF(result);
4201     return NULL;
4202 }
4203 
4204 PyDoc_STRVAR(long_bit_length_doc,
4205 "long.bit_length() -> int or long\n\
4206 \n\
4207 Number of bits necessary to represent self in binary.\n\
4208 >>> bin(37L)\n\
4209 '0b100101'\n\
4210 >>> (37L).bit_length()\n\
4211 6");
4212 
4213 #if 0
4214 static PyObject *
4215 long_is_finite(PyObject *v)
4216 {
4217     Py_RETURN_TRUE;
4218 }
4219 #endif
4220 
4221 static PyMethodDef long_methods[] = {
4222     {"conjugate",       (PyCFunction)long_long, METH_NOARGS,
4223      "Returns self, the complex conjugate of any long."},
4224     {"bit_length",      (PyCFunction)long_bit_length, METH_NOARGS,
4225      long_bit_length_doc},
4226 #if 0
4227     {"is_finite",       (PyCFunction)long_is_finite,    METH_NOARGS,
4228      "Returns always True."},
4229 #endif
4230     {"__trunc__",       (PyCFunction)long_long, METH_NOARGS,
4231      "Truncating an Integral returns itself."},
4232     {"__getnewargs__",          (PyCFunction)long_getnewargs,   METH_NOARGS},
4233     {"__format__", (PyCFunction)long__format__, METH_VARARGS},
4234     {"__sizeof__",      (PyCFunction)long_sizeof, METH_NOARGS,
4235      "Returns size in memory, in bytes"},
4236     {NULL,              NULL}           /* sentinel */
4237 };
4238 
4239 static PyGetSetDef long_getset[] = {
4240     {"real",
4241      (getter)long_long, (setter)NULL,
4242      "the real part of a complex number",
4243      NULL},
4244     {"imag",
4245      (getter)long_get0, (setter)NULL,
4246      "the imaginary part of a complex number",
4247      NULL},
4248     {"numerator",
4249      (getter)long_long, (setter)NULL,
4250      "the numerator of a rational number in lowest terms",
4251      NULL},
4252     {"denominator",
4253      (getter)long_get1, (setter)NULL,
4254      "the denominator of a rational number in lowest terms",
4255      NULL},
4256     {NULL}  /* Sentinel */
4257 };
4258 
4259 PyDoc_STRVAR(long_doc,
4260 "long(x=0) -> long\n\
4261 long(x, base=10) -> long\n\
4262 \n\
4263 Convert a number or string to a long integer, or return 0L if no arguments\n\
4264 are given.  If x is floating point, the conversion truncates towards zero.\n\
4265 \n\
4266 If x is not a number or if base is given, then x must be a string or\n\
4267 Unicode object representing an integer literal in the given base.  The\n\
4268 literal can be preceded by '+' or '-' and be surrounded by whitespace.\n\
4269 The base defaults to 10.  Valid bases are 0 and 2-36.  Base 0 means to\n\
4270 interpret the base from the string as an integer literal.\n\
4271 >>> int('0b100', base=0)\n\
4272 4L");
4273 
4274 static PyNumberMethods long_as_number = {
4275     (binaryfunc)long_add,       /*nb_add*/
4276     (binaryfunc)long_sub,       /*nb_subtract*/
4277     (binaryfunc)long_mul,       /*nb_multiply*/
4278     long_classic_div,           /*nb_divide*/
4279     long_mod,                   /*nb_remainder*/
4280     long_divmod,                /*nb_divmod*/
4281     long_pow,                   /*nb_power*/
4282     (unaryfunc)long_neg,        /*nb_negative*/
4283     (unaryfunc)long_long,       /*tp_positive*/
4284     (unaryfunc)long_abs,        /*tp_absolute*/
4285     (inquiry)long_nonzero,      /*tp_nonzero*/
4286     (unaryfunc)long_invert,     /*nb_invert*/
4287     long_lshift,                /*nb_lshift*/
4288     (binaryfunc)long_rshift,    /*nb_rshift*/
4289     long_and,                   /*nb_and*/
4290     long_xor,                   /*nb_xor*/
4291     long_or,                    /*nb_or*/
4292     long_coerce,                /*nb_coerce*/
4293     long_int,                   /*nb_int*/
4294     long_long,                  /*nb_long*/
4295     long_float,                 /*nb_float*/
4296     long_oct,                   /*nb_oct*/
4297     long_hex,                   /*nb_hex*/
4298     0,                          /* nb_inplace_add */
4299     0,                          /* nb_inplace_subtract */
4300     0,                          /* nb_inplace_multiply */
4301     0,                          /* nb_inplace_divide */
4302     0,                          /* nb_inplace_remainder */
4303     0,                          /* nb_inplace_power */
4304     0,                          /* nb_inplace_lshift */
4305     0,                          /* nb_inplace_rshift */
4306     0,                          /* nb_inplace_and */
4307     0,                          /* nb_inplace_xor */
4308     0,                          /* nb_inplace_or */
4309     long_div,                   /* nb_floor_divide */
4310     long_true_divide,           /* nb_true_divide */
4311     0,                          /* nb_inplace_floor_divide */
4312     0,                          /* nb_inplace_true_divide */
4313     long_long,                  /* nb_index */
4314 };
4315 
4316 PyTypeObject PyLong_Type = {
4317     PyObject_HEAD_INIT(&PyType_Type)
4318     0,                                          /* ob_size */
4319     "long",                                     /* tp_name */
4320     offsetof(PyLongObject, ob_digit),           /* tp_basicsize */
4321     sizeof(digit),                              /* tp_itemsize */
4322     long_dealloc,                               /* tp_dealloc */
4323     0,                                          /* tp_print */
4324     0,                                          /* tp_getattr */
4325     0,                                          /* tp_setattr */
4326     (cmpfunc)long_compare,                      /* tp_compare */
4327     long_repr,                                  /* tp_repr */
4328     &long_as_number,                            /* tp_as_number */
4329     0,                                          /* tp_as_sequence */
4330     0,                                          /* tp_as_mapping */
4331     (hashfunc)long_hash,                        /* tp_hash */
4332     0,                                          /* tp_call */
4333     long_str,                                   /* tp_str */
4334     PyObject_GenericGetAttr,                    /* tp_getattro */
4335     0,                                          /* tp_setattro */
4336     0,                                          /* tp_as_buffer */
4337     Py_TPFLAGS_DEFAULT | Py_TPFLAGS_CHECKTYPES |
4338         Py_TPFLAGS_BASETYPE | Py_TPFLAGS_LONG_SUBCLASS, /* tp_flags */
4339     long_doc,                                   /* tp_doc */
4340     0,                                          /* tp_traverse */
4341     0,                                          /* tp_clear */
4342     0,                                          /* tp_richcompare */
4343     0,                                          /* tp_weaklistoffset */
4344     0,                                          /* tp_iter */
4345     0,                                          /* tp_iternext */
4346     long_methods,                               /* tp_methods */
4347     0,                                          /* tp_members */
4348     long_getset,                                /* tp_getset */
4349     0,                                          /* tp_base */
4350     0,                                          /* tp_dict */
4351     0,                                          /* tp_descr_get */
4352     0,                                          /* tp_descr_set */
4353     0,                                          /* tp_dictoffset */
4354     0,                                          /* tp_init */
4355     0,                                          /* tp_alloc */
4356     long_new,                                   /* tp_new */
4357     PyObject_Del,                               /* tp_free */
4358 };
4359 
4360 static PyTypeObject Long_InfoType;
4361 
4362 PyDoc_STRVAR(long_info__doc__,
4363 "sys.long_info\n\
4364 \n\
4365 A struct sequence that holds information about Python's\n\
4366 internal representation of integers.  The attributes are read only.");
4367 
4368 static PyStructSequence_Field long_info_fields[] = {
4369     {"bits_per_digit", "size of a digit in bits"},
4370     {"sizeof_digit", "size in bytes of the C type used to represent a digit"},
4371     {NULL, NULL}
4372 };
4373 
4374 static PyStructSequence_Desc long_info_desc = {
4375     "sys.long_info",   /* name */
4376     long_info__doc__,  /* doc */
4377     long_info_fields,  /* fields */
4378     2                  /* number of fields */
4379 };
4380 
4381 PyObject *
PyLong_GetInfo(void)4382 PyLong_GetInfo(void)
4383 {
4384     PyObject* long_info;
4385     int field = 0;
4386     long_info = PyStructSequence_New(&Long_InfoType);
4387     if (long_info == NULL)
4388         return NULL;
4389     PyStructSequence_SET_ITEM(long_info, field++,
4390                               PyInt_FromLong(PyLong_SHIFT));
4391     PyStructSequence_SET_ITEM(long_info, field++,
4392                               PyInt_FromLong(sizeof(digit)));
4393     if (PyErr_Occurred()) {
4394         Py_CLEAR(long_info);
4395         return NULL;
4396     }
4397     return long_info;
4398 }
4399 
4400 int
_PyLong_Init(void)4401 _PyLong_Init(void)
4402 {
4403     /* initialize long_info */
4404     if (Long_InfoType.tp_name == 0)
4405         PyStructSequence_InitType(&Long_InfoType, &long_info_desc);
4406     return 1;
4407 }
4408