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