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