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