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