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