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