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