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