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