longobject.c revision 377be11ee1fab015f4cc77975374f86cf436536e
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 != 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 -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 1404 if ((base != 0 && base < 2) || base > 36) { 1405 PyErr_SetString(PyExc_ValueError, 1406 "long() arg 2 must be >= 2 and <= 36"); 1407 return NULL; 1408 } 1409 while (*str != '\0' && isspace(Py_CHARMASK(*str))) 1410 str++; 1411 if (*str == '+') 1412 ++str; 1413 else if (*str == '-') { 1414 ++str; 1415 sign = -1; 1416 } 1417 while (*str != '\0' && isspace(Py_CHARMASK(*str))) 1418 str++; 1419 if (base == 0) { 1420 if (str[0] != '0') 1421 base = 10; 1422 else if (str[1] == 'x' || str[1] == 'X') 1423 base = 16; 1424 else 1425 base = 8; 1426 } 1427 if (base == 16 && str[0] == '0' && (str[1] == 'x' || str[1] == 'X')) 1428 str += 2; 1429 start = str; 1430 if ((base & (base - 1)) == 0) 1431 z = long_from_binary_base(&str, base); 1432 else { 1433 z = _PyLong_New(0); 1434 for ( ; z != NULL; ++str) { 1435 int k = -1; 1436 PyLongObject *temp; 1437 1438 if (*str <= '9') 1439 k = *str - '0'; 1440 else if (*str >= 'a') 1441 k = *str - 'a' + 10; 1442 else if (*str >= 'A') 1443 k = *str - 'A' + 10; 1444 if (k < 0 || k >= base) 1445 break; 1446 temp = muladd1(z, (digit)base, (digit)k); 1447 Py_DECREF(z); 1448 z = temp; 1449 } 1450 } 1451 if (z == NULL) 1452 return NULL; 1453 if (str == start) 1454 goto onError; 1455 if (sign < 0 && z != NULL && z->ob_size != 0) 1456 z->ob_size = -(z->ob_size); 1457 if (*str == 'L' || *str == 'l') 1458 str++; 1459 while (*str && isspace(Py_CHARMASK(*str))) 1460 str++; 1461 if (*str != '\0') 1462 goto onError; 1463 if (pend) 1464 *pend = str; 1465 return (PyObject *) z; 1466 1467 onError: 1468 PyErr_Format(PyExc_ValueError, 1469 "invalid literal for long(): %.200s", orig_str); 1470 Py_XDECREF(z); 1471 return NULL; 1472} 1473 1474#ifdef Py_USING_UNICODE 1475PyObject * 1476PyLong_FromUnicode(Py_UNICODE *u, Py_ssize_t length, int base) 1477{ 1478 PyObject *result; 1479 char *buffer = (char *)PyMem_MALLOC(length+1); 1480 1481 if (buffer == NULL) 1482 return NULL; 1483 1484 if (PyUnicode_EncodeDecimal(u, length, buffer, NULL)) { 1485 PyMem_FREE(buffer); 1486 return NULL; 1487 } 1488 result = PyLong_FromString(buffer, NULL, base); 1489 PyMem_FREE(buffer); 1490 return result; 1491} 1492#endif 1493 1494/* forward */ 1495static PyLongObject *x_divrem 1496 (PyLongObject *, PyLongObject *, PyLongObject **); 1497static PyObject *long_pos(PyLongObject *); 1498static int long_divrem(PyLongObject *, PyLongObject *, 1499 PyLongObject **, PyLongObject **); 1500 1501/* Long division with remainder, top-level routine */ 1502 1503static int 1504long_divrem(PyLongObject *a, PyLongObject *b, 1505 PyLongObject **pdiv, PyLongObject **prem) 1506{ 1507 Py_ssize_t size_a = ABS(a->ob_size), size_b = ABS(b->ob_size); 1508 PyLongObject *z; 1509 1510 if (size_b == 0) { 1511 PyErr_SetString(PyExc_ZeroDivisionError, 1512 "long division or modulo by zero"); 1513 return -1; 1514 } 1515 if (size_a < size_b || 1516 (size_a == size_b && 1517 a->ob_digit[size_a-1] < b->ob_digit[size_b-1])) { 1518 /* |a| < |b|. */ 1519 *pdiv = _PyLong_New(0); 1520 Py_INCREF(a); 1521 *prem = (PyLongObject *) a; 1522 return 0; 1523 } 1524 if (size_b == 1) { 1525 digit rem = 0; 1526 z = divrem1(a, b->ob_digit[0], &rem); 1527 if (z == NULL) 1528 return -1; 1529 *prem = (PyLongObject *) PyLong_FromLong((long)rem); 1530 } 1531 else { 1532 z = x_divrem(a, b, prem); 1533 if (z == NULL) 1534 return -1; 1535 } 1536 /* Set the signs. 1537 The quotient z has the sign of a*b; 1538 the remainder r has the sign of a, 1539 so a = b*z + r. */ 1540 if ((a->ob_size < 0) != (b->ob_size < 0)) 1541 z->ob_size = -(z->ob_size); 1542 if (a->ob_size < 0 && (*prem)->ob_size != 0) 1543 (*prem)->ob_size = -((*prem)->ob_size); 1544 *pdiv = z; 1545 return 0; 1546} 1547 1548/* Unsigned long division with remainder -- the algorithm */ 1549 1550static PyLongObject * 1551x_divrem(PyLongObject *v1, PyLongObject *w1, PyLongObject **prem) 1552{ 1553 Py_ssize_t size_v = ABS(v1->ob_size), size_w = ABS(w1->ob_size); 1554 digit d = (digit) ((twodigits)BASE / (w1->ob_digit[size_w-1] + 1)); 1555 PyLongObject *v = mul1(v1, d); 1556 PyLongObject *w = mul1(w1, d); 1557 PyLongObject *a; 1558 Py_ssize_t j, k; 1559 1560 if (v == NULL || w == NULL) { 1561 Py_XDECREF(v); 1562 Py_XDECREF(w); 1563 return NULL; 1564 } 1565 1566 assert(size_v >= size_w && size_w > 1); /* Assert checks by div() */ 1567 assert(v->ob_refcnt == 1); /* Since v will be used as accumulator! */ 1568 assert(size_w == ABS(w->ob_size)); /* That's how d was calculated */ 1569 1570 size_v = ABS(v->ob_size); 1571 a = _PyLong_New(size_v - size_w + 1); 1572 1573 for (j = size_v, k = a->ob_size-1; a != NULL && k >= 0; --j, --k) { 1574 digit vj = (j >= size_v) ? 0 : v->ob_digit[j]; 1575 twodigits q; 1576 stwodigits carry = 0; 1577 int i; 1578 1579 SIGCHECK({ 1580 Py_DECREF(a); 1581 a = NULL; 1582 break; 1583 }) 1584 if (vj == w->ob_digit[size_w-1]) 1585 q = MASK; 1586 else 1587 q = (((twodigits)vj << SHIFT) + v->ob_digit[j-1]) / 1588 w->ob_digit[size_w-1]; 1589 1590 while (w->ob_digit[size_w-2]*q > 1591 (( 1592 ((twodigits)vj << SHIFT) 1593 + v->ob_digit[j-1] 1594 - q*w->ob_digit[size_w-1] 1595 ) << SHIFT) 1596 + v->ob_digit[j-2]) 1597 --q; 1598 1599 for (i = 0; i < size_w && i+k < size_v; ++i) { 1600 twodigits z = w->ob_digit[i] * q; 1601 digit zz = (digit) (z >> SHIFT); 1602 carry += v->ob_digit[i+k] - z 1603 + ((twodigits)zz << SHIFT); 1604 v->ob_digit[i+k] = (digit)(carry & MASK); 1605 carry = Py_ARITHMETIC_RIGHT_SHIFT(BASE_TWODIGITS_TYPE, 1606 carry, SHIFT); 1607 carry -= zz; 1608 } 1609 1610 if (i+k < size_v) { 1611 carry += v->ob_digit[i+k]; 1612 v->ob_digit[i+k] = 0; 1613 } 1614 1615 if (carry == 0) 1616 a->ob_digit[k] = (digit) q; 1617 else { 1618 assert(carry == -1); 1619 a->ob_digit[k] = (digit) q-1; 1620 carry = 0; 1621 for (i = 0; i < size_w && i+k < size_v; ++i) { 1622 carry += v->ob_digit[i+k] + w->ob_digit[i]; 1623 v->ob_digit[i+k] = (digit)(carry & MASK); 1624 carry = Py_ARITHMETIC_RIGHT_SHIFT( 1625 BASE_TWODIGITS_TYPE, 1626 carry, SHIFT); 1627 } 1628 } 1629 } /* for j, k */ 1630 1631 if (a == NULL) 1632 *prem = NULL; 1633 else { 1634 a = long_normalize(a); 1635 *prem = divrem1(v, d, &d); 1636 /* d receives the (unused) remainder */ 1637 if (*prem == NULL) { 1638 Py_DECREF(a); 1639 a = NULL; 1640 } 1641 } 1642 Py_DECREF(v); 1643 Py_DECREF(w); 1644 return a; 1645} 1646 1647/* Methods */ 1648 1649static void 1650long_dealloc(PyObject *v) 1651{ 1652 v->ob_type->tp_free(v); 1653} 1654 1655static PyObject * 1656long_repr(PyObject *v) 1657{ 1658 return long_format(v, 10, 1); 1659} 1660 1661static PyObject * 1662long_str(PyObject *v) 1663{ 1664 return long_format(v, 10, 0); 1665} 1666 1667static int 1668long_compare(PyLongObject *a, PyLongObject *b) 1669{ 1670 Py_ssize_t sign; 1671 1672 if (a->ob_size != b->ob_size) { 1673 if (ABS(a->ob_size) == 0 && ABS(b->ob_size) == 0) 1674 sign = 0; 1675 else 1676 sign = a->ob_size - b->ob_size; 1677 } 1678 else { 1679 Py_ssize_t i = ABS(a->ob_size); 1680 while (--i >= 0 && a->ob_digit[i] == b->ob_digit[i]) 1681 ; 1682 if (i < 0) 1683 sign = 0; 1684 else { 1685 sign = (int)a->ob_digit[i] - (int)b->ob_digit[i]; 1686 if (a->ob_size < 0) 1687 sign = -sign; 1688 } 1689 } 1690 return sign < 0 ? -1 : sign > 0 ? 1 : 0; 1691} 1692 1693static long 1694long_hash(PyLongObject *v) 1695{ 1696 long x; 1697 Py_ssize_t i; 1698 int sign; 1699 1700 /* This is designed so that Python ints and longs with the 1701 same value hash to the same value, otherwise comparisons 1702 of mapping keys will turn out weird */ 1703 i = v->ob_size; 1704 sign = 1; 1705 x = 0; 1706 if (i < 0) { 1707 sign = -1; 1708 i = -(i); 1709 } 1710#define LONG_BIT_SHIFT (8*sizeof(long) - SHIFT) 1711 while (--i >= 0) { 1712 /* Force a native long #-bits (32 or 64) circular shift */ 1713 x = ((x << SHIFT) & ~MASK) | ((x >> LONG_BIT_SHIFT) & MASK); 1714 x += v->ob_digit[i]; 1715 } 1716#undef LONG_BIT_SHIFT 1717 x = x * sign; 1718 if (x == -1) 1719 x = -2; 1720 return x; 1721} 1722 1723 1724/* Add the absolute values of two long integers. */ 1725 1726static PyLongObject * 1727x_add(PyLongObject *a, PyLongObject *b) 1728{ 1729 Py_ssize_t size_a = ABS(a->ob_size), size_b = ABS(b->ob_size); 1730 PyLongObject *z; 1731 int i; 1732 digit carry = 0; 1733 1734 /* Ensure a is the larger of the two: */ 1735 if (size_a < size_b) { 1736 { PyLongObject *temp = a; a = b; b = temp; } 1737 { Py_ssize_t size_temp = size_a; 1738 size_a = size_b; 1739 size_b = size_temp; } 1740 } 1741 z = _PyLong_New(size_a+1); 1742 if (z == NULL) 1743 return NULL; 1744 for (i = 0; i < size_b; ++i) { 1745 carry += a->ob_digit[i] + b->ob_digit[i]; 1746 z->ob_digit[i] = carry & MASK; 1747 carry >>= SHIFT; 1748 } 1749 for (; i < size_a; ++i) { 1750 carry += a->ob_digit[i]; 1751 z->ob_digit[i] = carry & MASK; 1752 carry >>= SHIFT; 1753 } 1754 z->ob_digit[i] = carry; 1755 return long_normalize(z); 1756} 1757 1758/* Subtract the absolute values of two integers. */ 1759 1760static PyLongObject * 1761x_sub(PyLongObject *a, PyLongObject *b) 1762{ 1763 Py_ssize_t size_a = ABS(a->ob_size), size_b = ABS(b->ob_size); 1764 PyLongObject *z; 1765 Py_ssize_t i; 1766 int sign = 1; 1767 digit borrow = 0; 1768 1769 /* Ensure a is the larger of the two: */ 1770 if (size_a < size_b) { 1771 sign = -1; 1772 { PyLongObject *temp = a; a = b; b = temp; } 1773 { Py_ssize_t size_temp = size_a; 1774 size_a = size_b; 1775 size_b = size_temp; } 1776 } 1777 else if (size_a == size_b) { 1778 /* Find highest digit where a and b differ: */ 1779 i = size_a; 1780 while (--i >= 0 && a->ob_digit[i] == b->ob_digit[i]) 1781 ; 1782 if (i < 0) 1783 return _PyLong_New(0); 1784 if (a->ob_digit[i] < b->ob_digit[i]) { 1785 sign = -1; 1786 { PyLongObject *temp = a; a = b; b = temp; } 1787 } 1788 size_a = size_b = i+1; 1789 } 1790 z = _PyLong_New(size_a); 1791 if (z == NULL) 1792 return NULL; 1793 for (i = 0; i < size_b; ++i) { 1794 /* The following assumes unsigned arithmetic 1795 works module 2**N for some N>SHIFT. */ 1796 borrow = a->ob_digit[i] - b->ob_digit[i] - borrow; 1797 z->ob_digit[i] = borrow & MASK; 1798 borrow >>= SHIFT; 1799 borrow &= 1; /* Keep only one sign bit */ 1800 } 1801 for (; i < size_a; ++i) { 1802 borrow = a->ob_digit[i] - borrow; 1803 z->ob_digit[i] = borrow & MASK; 1804 borrow >>= SHIFT; 1805 borrow &= 1; /* Keep only one sign bit */ 1806 } 1807 assert(borrow == 0); 1808 if (sign < 0) 1809 z->ob_size = -(z->ob_size); 1810 return long_normalize(z); 1811} 1812 1813static PyObject * 1814long_add(PyLongObject *v, PyLongObject *w) 1815{ 1816 PyLongObject *a, *b, *z; 1817 1818 CONVERT_BINOP((PyObject *)v, (PyObject *)w, &a, &b); 1819 1820 if (a->ob_size < 0) { 1821 if (b->ob_size < 0) { 1822 z = x_add(a, b); 1823 if (z != NULL && z->ob_size != 0) 1824 z->ob_size = -(z->ob_size); 1825 } 1826 else 1827 z = x_sub(b, a); 1828 } 1829 else { 1830 if (b->ob_size < 0) 1831 z = x_sub(a, b); 1832 else 1833 z = x_add(a, b); 1834 } 1835 Py_DECREF(a); 1836 Py_DECREF(b); 1837 return (PyObject *)z; 1838} 1839 1840static PyObject * 1841long_sub(PyLongObject *v, PyLongObject *w) 1842{ 1843 PyLongObject *a, *b, *z; 1844 1845 CONVERT_BINOP((PyObject *)v, (PyObject *)w, &a, &b); 1846 1847 if (a->ob_size < 0) { 1848 if (b->ob_size < 0) 1849 z = x_sub(a, b); 1850 else 1851 z = x_add(a, b); 1852 if (z != NULL && z->ob_size != 0) 1853 z->ob_size = -(z->ob_size); 1854 } 1855 else { 1856 if (b->ob_size < 0) 1857 z = x_add(a, b); 1858 else 1859 z = x_sub(a, b); 1860 } 1861 Py_DECREF(a); 1862 Py_DECREF(b); 1863 return (PyObject *)z; 1864} 1865 1866/* Grade school multiplication, ignoring the signs. 1867 * Returns the absolute value of the product, or NULL if error. 1868 */ 1869static PyLongObject * 1870x_mul(PyLongObject *a, PyLongObject *b) 1871{ 1872 PyLongObject *z; 1873 Py_ssize_t size_a = ABS(a->ob_size); 1874 Py_ssize_t size_b = ABS(b->ob_size); 1875 Py_ssize_t i; 1876 1877 z = _PyLong_New(size_a + size_b); 1878 if (z == NULL) 1879 return NULL; 1880 1881 memset(z->ob_digit, 0, z->ob_size * sizeof(digit)); 1882 if (a == b) { 1883 /* Efficient squaring per HAC, Algorithm 14.16: 1884 * http://www.cacr.math.uwaterloo.ca/hac/about/chap14.pdf 1885 * Gives slightly less than a 2x speedup when a == b, 1886 * via exploiting that each entry in the multiplication 1887 * pyramid appears twice (except for the size_a squares). 1888 */ 1889 for (i = 0; i < size_a; ++i) { 1890 twodigits carry; 1891 twodigits f = a->ob_digit[i]; 1892 digit *pz = z->ob_digit + (i << 1); 1893 digit *pa = a->ob_digit + i + 1; 1894 digit *paend = a->ob_digit + size_a; 1895 1896 SIGCHECK({ 1897 Py_DECREF(z); 1898 return NULL; 1899 }) 1900 1901 carry = *pz + f * f; 1902 *pz++ = (digit)(carry & MASK); 1903 carry >>= SHIFT; 1904 assert(carry <= MASK); 1905 1906 /* Now f is added in twice in each column of the 1907 * pyramid it appears. Same as adding f<<1 once. 1908 */ 1909 f <<= 1; 1910 while (pa < paend) { 1911 carry += *pz + *pa++ * f; 1912 *pz++ = (digit)(carry & MASK); 1913 carry >>= SHIFT; 1914 assert(carry <= (MASK << 1)); 1915 } 1916 if (carry) { 1917 carry += *pz; 1918 *pz++ = (digit)(carry & MASK); 1919 carry >>= SHIFT; 1920 } 1921 if (carry) 1922 *pz += (digit)(carry & MASK); 1923 assert((carry >> SHIFT) == 0); 1924 } 1925 } 1926 else { /* a is not the same as b -- gradeschool long mult */ 1927 for (i = 0; i < size_a; ++i) { 1928 twodigits carry = 0; 1929 twodigits f = a->ob_digit[i]; 1930 digit *pz = z->ob_digit + i; 1931 digit *pb = b->ob_digit; 1932 digit *pbend = b->ob_digit + size_b; 1933 1934 SIGCHECK({ 1935 Py_DECREF(z); 1936 return NULL; 1937 }) 1938 1939 while (pb < pbend) { 1940 carry += *pz + *pb++ * f; 1941 *pz++ = (digit)(carry & MASK); 1942 carry >>= SHIFT; 1943 assert(carry <= MASK); 1944 } 1945 if (carry) 1946 *pz += (digit)(carry & MASK); 1947 assert((carry >> SHIFT) == 0); 1948 } 1949 } 1950 return long_normalize(z); 1951} 1952 1953/* A helper for Karatsuba multiplication (k_mul). 1954 Takes a long "n" and an integer "size" representing the place to 1955 split, and sets low and high such that abs(n) == (high << size) + low, 1956 viewing the shift as being by digits. The sign bit is ignored, and 1957 the return values are >= 0. 1958 Returns 0 on success, -1 on failure. 1959*/ 1960static int 1961kmul_split(PyLongObject *n, Py_ssize_t size, PyLongObject **high, PyLongObject **low) 1962{ 1963 PyLongObject *hi, *lo; 1964 Py_ssize_t size_lo, size_hi; 1965 const Py_ssize_t size_n = ABS(n->ob_size); 1966 1967 size_lo = MIN(size_n, size); 1968 size_hi = size_n - size_lo; 1969 1970 if ((hi = _PyLong_New(size_hi)) == NULL) 1971 return -1; 1972 if ((lo = _PyLong_New(size_lo)) == NULL) { 1973 Py_DECREF(hi); 1974 return -1; 1975 } 1976 1977 memcpy(lo->ob_digit, n->ob_digit, size_lo * sizeof(digit)); 1978 memcpy(hi->ob_digit, n->ob_digit + size_lo, size_hi * sizeof(digit)); 1979 1980 *high = long_normalize(hi); 1981 *low = long_normalize(lo); 1982 return 0; 1983} 1984 1985static PyLongObject *k_lopsided_mul(PyLongObject *a, PyLongObject *b); 1986 1987/* Karatsuba multiplication. Ignores the input signs, and returns the 1988 * absolute value of the product (or NULL if error). 1989 * See Knuth Vol. 2 Chapter 4.3.3 (Pp. 294-295). 1990 */ 1991static PyLongObject * 1992k_mul(PyLongObject *a, PyLongObject *b) 1993{ 1994 Py_ssize_t asize = ABS(a->ob_size); 1995 Py_ssize_t bsize = ABS(b->ob_size); 1996 PyLongObject *ah = NULL; 1997 PyLongObject *al = NULL; 1998 PyLongObject *bh = NULL; 1999 PyLongObject *bl = NULL; 2000 PyLongObject *ret = NULL; 2001 PyLongObject *t1, *t2, *t3; 2002 Py_ssize_t shift; /* the number of digits we split off */ 2003 Py_ssize_t i; 2004 2005 /* (ah*X+al)(bh*X+bl) = ah*bh*X*X + (ah*bl + al*bh)*X + al*bl 2006 * Let k = (ah+al)*(bh+bl) = ah*bl + al*bh + ah*bh + al*bl 2007 * Then the original product is 2008 * ah*bh*X*X + (k - ah*bh - al*bl)*X + al*bl 2009 * By picking X to be a power of 2, "*X" is just shifting, and it's 2010 * been reduced to 3 multiplies on numbers half the size. 2011 */ 2012 2013 /* We want to split based on the larger number; fiddle so that b 2014 * is largest. 2015 */ 2016 if (asize > bsize) { 2017 t1 = a; 2018 a = b; 2019 b = t1; 2020 2021 i = asize; 2022 asize = bsize; 2023 bsize = i; 2024 } 2025 2026 /* Use gradeschool math when either number is too small. */ 2027 i = a == b ? KARATSUBA_SQUARE_CUTOFF : KARATSUBA_CUTOFF; 2028 if (asize <= i) { 2029 if (asize == 0) 2030 return _PyLong_New(0); 2031 else 2032 return x_mul(a, b); 2033 } 2034 2035 /* If a is small compared to b, splitting on b gives a degenerate 2036 * case with ah==0, and Karatsuba may be (even much) less efficient 2037 * than "grade school" then. However, we can still win, by viewing 2038 * b as a string of "big digits", each of width a->ob_size. That 2039 * leads to a sequence of balanced calls to k_mul. 2040 */ 2041 if (2 * asize <= bsize) 2042 return k_lopsided_mul(a, b); 2043 2044 /* Split a & b into hi & lo pieces. */ 2045 shift = bsize >> 1; 2046 if (kmul_split(a, shift, &ah, &al) < 0) goto fail; 2047 assert(ah->ob_size > 0); /* the split isn't degenerate */ 2048 2049 if (a == b) { 2050 bh = ah; 2051 bl = al; 2052 Py_INCREF(bh); 2053 Py_INCREF(bl); 2054 } 2055 else if (kmul_split(b, shift, &bh, &bl) < 0) goto fail; 2056 2057 /* The plan: 2058 * 1. Allocate result space (asize + bsize digits: that's always 2059 * enough). 2060 * 2. Compute ah*bh, and copy into result at 2*shift. 2061 * 3. Compute al*bl, and copy into result at 0. Note that this 2062 * can't overlap with #2. 2063 * 4. Subtract al*bl from the result, starting at shift. This may 2064 * underflow (borrow out of the high digit), but we don't care: 2065 * we're effectively doing unsigned arithmetic mod 2066 * BASE**(sizea + sizeb), and so long as the *final* result fits, 2067 * borrows and carries out of the high digit can be ignored. 2068 * 5. Subtract ah*bh from the result, starting at shift. 2069 * 6. Compute (ah+al)*(bh+bl), and add it into the result starting 2070 * at shift. 2071 */ 2072 2073 /* 1. Allocate result space. */ 2074 ret = _PyLong_New(asize + bsize); 2075 if (ret == NULL) goto fail; 2076#ifdef Py_DEBUG 2077 /* Fill with trash, to catch reference to uninitialized digits. */ 2078 memset(ret->ob_digit, 0xDF, ret->ob_size * sizeof(digit)); 2079#endif 2080 2081 /* 2. t1 <- ah*bh, and copy into high digits of result. */ 2082 if ((t1 = k_mul(ah, bh)) == NULL) goto fail; 2083 assert(t1->ob_size >= 0); 2084 assert(2*shift + t1->ob_size <= ret->ob_size); 2085 memcpy(ret->ob_digit + 2*shift, t1->ob_digit, 2086 t1->ob_size * sizeof(digit)); 2087 2088 /* Zero-out the digits higher than the ah*bh copy. */ 2089 i = ret->ob_size - 2*shift - t1->ob_size; 2090 if (i) 2091 memset(ret->ob_digit + 2*shift + t1->ob_size, 0, 2092 i * sizeof(digit)); 2093 2094 /* 3. t2 <- al*bl, and copy into the low digits. */ 2095 if ((t2 = k_mul(al, bl)) == NULL) { 2096 Py_DECREF(t1); 2097 goto fail; 2098 } 2099 assert(t2->ob_size >= 0); 2100 assert(t2->ob_size <= 2*shift); /* no overlap with high digits */ 2101 memcpy(ret->ob_digit, t2->ob_digit, t2->ob_size * sizeof(digit)); 2102 2103 /* Zero out remaining digits. */ 2104 i = 2*shift - t2->ob_size; /* number of uninitialized digits */ 2105 if (i) 2106 memset(ret->ob_digit + t2->ob_size, 0, i * sizeof(digit)); 2107 2108 /* 4 & 5. Subtract ah*bh (t1) and al*bl (t2). We do al*bl first 2109 * because it's fresher in cache. 2110 */ 2111 i = ret->ob_size - shift; /* # digits after shift */ 2112 (void)v_isub(ret->ob_digit + shift, i, t2->ob_digit, t2->ob_size); 2113 Py_DECREF(t2); 2114 2115 (void)v_isub(ret->ob_digit + shift, i, t1->ob_digit, t1->ob_size); 2116 Py_DECREF(t1); 2117 2118 /* 6. t3 <- (ah+al)(bh+bl), and add into result. */ 2119 if ((t1 = x_add(ah, al)) == NULL) goto fail; 2120 Py_DECREF(ah); 2121 Py_DECREF(al); 2122 ah = al = NULL; 2123 2124 if (a == b) { 2125 t2 = t1; 2126 Py_INCREF(t2); 2127 } 2128 else if ((t2 = x_add(bh, bl)) == NULL) { 2129 Py_DECREF(t1); 2130 goto fail; 2131 } 2132 Py_DECREF(bh); 2133 Py_DECREF(bl); 2134 bh = bl = NULL; 2135 2136 t3 = k_mul(t1, t2); 2137 Py_DECREF(t1); 2138 Py_DECREF(t2); 2139 if (t3 == NULL) goto fail; 2140 assert(t3->ob_size >= 0); 2141 2142 /* Add t3. It's not obvious why we can't run out of room here. 2143 * See the (*) comment after this function. 2144 */ 2145 (void)v_iadd(ret->ob_digit + shift, i, t3->ob_digit, t3->ob_size); 2146 Py_DECREF(t3); 2147 2148 return long_normalize(ret); 2149 2150 fail: 2151 Py_XDECREF(ret); 2152 Py_XDECREF(ah); 2153 Py_XDECREF(al); 2154 Py_XDECREF(bh); 2155 Py_XDECREF(bl); 2156 return NULL; 2157} 2158 2159/* (*) Why adding t3 can't "run out of room" above. 2160 2161Let f(x) mean the floor of x and c(x) mean the ceiling of x. Some facts 2162to start with: 2163 21641. For any integer i, i = c(i/2) + f(i/2). In particular, 2165 bsize = c(bsize/2) + f(bsize/2). 21662. shift = f(bsize/2) 21673. asize <= bsize 21684. Since we call k_lopsided_mul if asize*2 <= bsize, asize*2 > bsize in this 2169 routine, so asize > bsize/2 >= f(bsize/2) in this routine. 2170 2171We allocated asize + bsize result digits, and add t3 into them at an offset 2172of shift. This leaves asize+bsize-shift allocated digit positions for t3 2173to fit into, = (by #1 and #2) asize + f(bsize/2) + c(bsize/2) - f(bsize/2) = 2174asize + c(bsize/2) available digit positions. 2175 2176bh has c(bsize/2) digits, and bl at most f(size/2) digits. So bh+hl has 2177at most c(bsize/2) digits + 1 bit. 2178 2179If asize == bsize, ah has c(bsize/2) digits, else ah has at most f(bsize/2) 2180digits, and al has at most f(bsize/2) digits in any case. So ah+al has at 2181most (asize == bsize ? c(bsize/2) : f(bsize/2)) digits + 1 bit. 2182 2183The product (ah+al)*(bh+bl) therefore has at most 2184 2185 c(bsize/2) + (asize == bsize ? c(bsize/2) : f(bsize/2)) digits + 2 bits 2186 2187and we have asize + c(bsize/2) available digit positions. We need to show 2188this is always enough. An instance of c(bsize/2) cancels out in both, so 2189the question reduces to whether asize digits is enough to hold 2190(asize == bsize ? c(bsize/2) : f(bsize/2)) digits + 2 bits. If asize < bsize, 2191then we're asking whether asize digits >= f(bsize/2) digits + 2 bits. By #4, 2192asize is at least f(bsize/2)+1 digits, so this in turn reduces to whether 1 2193digit is enough to hold 2 bits. This is so since SHIFT=15 >= 2. If 2194asize == bsize, then we're asking whether bsize digits is enough to hold 2195c(bsize/2) digits + 2 bits, or equivalently (by #1) whether f(bsize/2) digits 2196is enough to hold 2 bits. This is so if bsize >= 2, which holds because 2197bsize >= KARATSUBA_CUTOFF >= 2. 2198 2199Note that since there's always enough room for (ah+al)*(bh+bl), and that's 2200clearly >= each of ah*bh and al*bl, there's always enough room to subtract 2201ah*bh and al*bl too. 2202*/ 2203 2204/* b has at least twice the digits of a, and a is big enough that Karatsuba 2205 * would pay off *if* the inputs had balanced sizes. View b as a sequence 2206 * of slices, each with a->ob_size digits, and multiply the slices by a, 2207 * one at a time. This gives k_mul balanced inputs to work with, and is 2208 * also cache-friendly (we compute one double-width slice of the result 2209 * at a time, then move on, never bactracking except for the helpful 2210 * single-width slice overlap between successive partial sums). 2211 */ 2212static PyLongObject * 2213k_lopsided_mul(PyLongObject *a, PyLongObject *b) 2214{ 2215 const Py_ssize_t asize = ABS(a->ob_size); 2216 Py_ssize_t bsize = ABS(b->ob_size); 2217 Py_ssize_t nbdone; /* # of b digits already multiplied */ 2218 PyLongObject *ret; 2219 PyLongObject *bslice = NULL; 2220 2221 assert(asize > KARATSUBA_CUTOFF); 2222 assert(2 * asize <= bsize); 2223 2224 /* Allocate result space, and zero it out. */ 2225 ret = _PyLong_New(asize + bsize); 2226 if (ret == NULL) 2227 return NULL; 2228 memset(ret->ob_digit, 0, ret->ob_size * sizeof(digit)); 2229 2230 /* Successive slices of b are copied into bslice. */ 2231 bslice = _PyLong_New(asize); 2232 if (bslice == NULL) 2233 goto fail; 2234 2235 nbdone = 0; 2236 while (bsize > 0) { 2237 PyLongObject *product; 2238 const Py_ssize_t nbtouse = MIN(bsize, asize); 2239 2240 /* Multiply the next slice of b by a. */ 2241 memcpy(bslice->ob_digit, b->ob_digit + nbdone, 2242 nbtouse * sizeof(digit)); 2243 bslice->ob_size = nbtouse; 2244 product = k_mul(a, bslice); 2245 if (product == NULL) 2246 goto fail; 2247 2248 /* Add into result. */ 2249 (void)v_iadd(ret->ob_digit + nbdone, ret->ob_size - nbdone, 2250 product->ob_digit, product->ob_size); 2251 Py_DECREF(product); 2252 2253 bsize -= nbtouse; 2254 nbdone += nbtouse; 2255 } 2256 2257 Py_DECREF(bslice); 2258 return long_normalize(ret); 2259 2260 fail: 2261 Py_DECREF(ret); 2262 Py_XDECREF(bslice); 2263 return NULL; 2264} 2265 2266static PyObject * 2267long_mul(PyLongObject *v, PyLongObject *w) 2268{ 2269 PyLongObject *a, *b, *z; 2270 2271 if (!convert_binop((PyObject *)v, (PyObject *)w, &a, &b)) { 2272 Py_INCREF(Py_NotImplemented); 2273 return Py_NotImplemented; 2274 } 2275 2276 z = k_mul(a, b); 2277 /* Negate if exactly one of the inputs is negative. */ 2278 if (((a->ob_size ^ b->ob_size) < 0) && z) 2279 z->ob_size = -(z->ob_size); 2280 Py_DECREF(a); 2281 Py_DECREF(b); 2282 return (PyObject *)z; 2283} 2284 2285/* The / and % operators are now defined in terms of divmod(). 2286 The expression a mod b has the value a - b*floor(a/b). 2287 The long_divrem function gives the remainder after division of 2288 |a| by |b|, with the sign of a. This is also expressed 2289 as a - b*trunc(a/b), if trunc truncates towards zero. 2290 Some examples: 2291 a b a rem b a mod b 2292 13 10 3 3 2293 -13 10 -3 7 2294 13 -10 3 -7 2295 -13 -10 -3 -3 2296 So, to get from rem to mod, we have to add b if a and b 2297 have different signs. We then subtract one from the 'div' 2298 part of the outcome to keep the invariant intact. */ 2299 2300/* Compute 2301 * *pdiv, *pmod = divmod(v, w) 2302 * NULL can be passed for pdiv or pmod, in which case that part of 2303 * the result is simply thrown away. The caller owns a reference to 2304 * each of these it requests (does not pass NULL for). 2305 */ 2306static int 2307l_divmod(PyLongObject *v, PyLongObject *w, 2308 PyLongObject **pdiv, PyLongObject **pmod) 2309{ 2310 PyLongObject *div, *mod; 2311 2312 if (long_divrem(v, w, &div, &mod) < 0) 2313 return -1; 2314 if ((mod->ob_size < 0 && w->ob_size > 0) || 2315 (mod->ob_size > 0 && w->ob_size < 0)) { 2316 PyLongObject *temp; 2317 PyLongObject *one; 2318 temp = (PyLongObject *) long_add(mod, w); 2319 Py_DECREF(mod); 2320 mod = temp; 2321 if (mod == NULL) { 2322 Py_DECREF(div); 2323 return -1; 2324 } 2325 one = (PyLongObject *) PyLong_FromLong(1L); 2326 if (one == NULL || 2327 (temp = (PyLongObject *) long_sub(div, one)) == NULL) { 2328 Py_DECREF(mod); 2329 Py_DECREF(div); 2330 Py_XDECREF(one); 2331 return -1; 2332 } 2333 Py_DECREF(one); 2334 Py_DECREF(div); 2335 div = temp; 2336 } 2337 if (pdiv != NULL) 2338 *pdiv = div; 2339 else 2340 Py_DECREF(div); 2341 2342 if (pmod != NULL) 2343 *pmod = mod; 2344 else 2345 Py_DECREF(mod); 2346 2347 return 0; 2348} 2349 2350static PyObject * 2351long_div(PyObject *v, PyObject *w) 2352{ 2353 PyLongObject *a, *b, *div; 2354 2355 CONVERT_BINOP(v, w, &a, &b); 2356 if (l_divmod(a, b, &div, NULL) < 0) 2357 div = NULL; 2358 Py_DECREF(a); 2359 Py_DECREF(b); 2360 return (PyObject *)div; 2361} 2362 2363static PyObject * 2364long_classic_div(PyObject *v, PyObject *w) 2365{ 2366 PyLongObject *a, *b, *div; 2367 2368 CONVERT_BINOP(v, w, &a, &b); 2369 if (Py_DivisionWarningFlag && 2370 PyErr_Warn(PyExc_DeprecationWarning, "classic long division") < 0) 2371 div = NULL; 2372 else if (l_divmod(a, b, &div, NULL) < 0) 2373 div = NULL; 2374 Py_DECREF(a); 2375 Py_DECREF(b); 2376 return (PyObject *)div; 2377} 2378 2379static PyObject * 2380long_true_divide(PyObject *v, PyObject *w) 2381{ 2382 PyLongObject *a, *b; 2383 double ad, bd; 2384 int failed, aexp = -1, bexp = -1; 2385 2386 CONVERT_BINOP(v, w, &a, &b); 2387 ad = _PyLong_AsScaledDouble((PyObject *)a, &aexp); 2388 bd = _PyLong_AsScaledDouble((PyObject *)b, &bexp); 2389 failed = (ad == -1.0 || bd == -1.0) && PyErr_Occurred(); 2390 Py_DECREF(a); 2391 Py_DECREF(b); 2392 if (failed) 2393 return NULL; 2394 /* 'aexp' and 'bexp' were initialized to -1 to silence gcc-4.0.x, 2395 but should really be set correctly after sucessful calls to 2396 _PyLong_AsScaledDouble() */ 2397 assert(aexp >= 0 && bexp >= 0); 2398 2399 if (bd == 0.0) { 2400 PyErr_SetString(PyExc_ZeroDivisionError, 2401 "long division or modulo by zero"); 2402 return NULL; 2403 } 2404 2405 /* True value is very close to ad/bd * 2**(SHIFT*(aexp-bexp)) */ 2406 ad /= bd; /* overflow/underflow impossible here */ 2407 aexp -= bexp; 2408 if (aexp > INT_MAX / SHIFT) 2409 goto overflow; 2410 else if (aexp < -(INT_MAX / SHIFT)) 2411 return PyFloat_FromDouble(0.0); /* underflow to 0 */ 2412 errno = 0; 2413 ad = ldexp(ad, aexp * SHIFT); 2414 if (Py_OVERFLOWED(ad)) /* ignore underflow to 0.0 */ 2415 goto overflow; 2416 return PyFloat_FromDouble(ad); 2417 2418overflow: 2419 PyErr_SetString(PyExc_OverflowError, 2420 "long/long too large for a float"); 2421 return NULL; 2422 2423} 2424 2425static PyObject * 2426long_mod(PyObject *v, PyObject *w) 2427{ 2428 PyLongObject *a, *b, *mod; 2429 2430 CONVERT_BINOP(v, w, &a, &b); 2431 2432 if (l_divmod(a, b, NULL, &mod) < 0) 2433 mod = NULL; 2434 Py_DECREF(a); 2435 Py_DECREF(b); 2436 return (PyObject *)mod; 2437} 2438 2439static PyObject * 2440long_divmod(PyObject *v, PyObject *w) 2441{ 2442 PyLongObject *a, *b, *div, *mod; 2443 PyObject *z; 2444 2445 CONVERT_BINOP(v, w, &a, &b); 2446 2447 if (l_divmod(a, b, &div, &mod) < 0) { 2448 Py_DECREF(a); 2449 Py_DECREF(b); 2450 return NULL; 2451 } 2452 z = PyTuple_New(2); 2453 if (z != NULL) { 2454 PyTuple_SetItem(z, 0, (PyObject *) div); 2455 PyTuple_SetItem(z, 1, (PyObject *) mod); 2456 } 2457 else { 2458 Py_DECREF(div); 2459 Py_DECREF(mod); 2460 } 2461 Py_DECREF(a); 2462 Py_DECREF(b); 2463 return z; 2464} 2465 2466/* pow(v, w, x) */ 2467static PyObject * 2468long_pow(PyObject *v, PyObject *w, PyObject *x) 2469{ 2470 PyLongObject *a, *b, *c; /* a,b,c = v,w,x */ 2471 int negativeOutput = 0; /* if x<0 return negative output */ 2472 2473 PyLongObject *z = NULL; /* accumulated result */ 2474 Py_ssize_t i, j, k; /* counters */ 2475 PyLongObject *temp = NULL; 2476 2477 /* 5-ary values. If the exponent is large enough, table is 2478 * precomputed so that table[i] == a**i % c for i in range(32). 2479 */ 2480 PyLongObject *table[32] = {0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0, 2481 0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0}; 2482 2483 /* a, b, c = v, w, x */ 2484 CONVERT_BINOP(v, w, &a, &b); 2485 if (PyLong_Check(x)) { 2486 c = (PyLongObject *)x; 2487 Py_INCREF(x); 2488 } 2489 else if (PyInt_Check(x)) { 2490 c = (PyLongObject *)PyLong_FromLong(PyInt_AS_LONG(x)); 2491 if (c == NULL) 2492 goto Error; 2493 } 2494 else if (x == Py_None) 2495 c = NULL; 2496 else { 2497 Py_DECREF(a); 2498 Py_DECREF(b); 2499 Py_INCREF(Py_NotImplemented); 2500 return Py_NotImplemented; 2501 } 2502 2503 if (b->ob_size < 0) { /* if exponent is negative */ 2504 if (c) { 2505 PyErr_SetString(PyExc_TypeError, "pow() 2nd argument " 2506 "cannot be negative when 3rd argument specified"); 2507 goto Error; 2508 } 2509 else { 2510 /* else return a float. This works because we know 2511 that this calls float_pow() which converts its 2512 arguments to double. */ 2513 Py_DECREF(a); 2514 Py_DECREF(b); 2515 return PyFloat_Type.tp_as_number->nb_power(v, w, x); 2516 } 2517 } 2518 2519 if (c) { 2520 /* if modulus == 0: 2521 raise ValueError() */ 2522 if (c->ob_size == 0) { 2523 PyErr_SetString(PyExc_ValueError, 2524 "pow() 3rd argument cannot be 0"); 2525 goto Error; 2526 } 2527 2528 /* if modulus < 0: 2529 negativeOutput = True 2530 modulus = -modulus */ 2531 if (c->ob_size < 0) { 2532 negativeOutput = 1; 2533 temp = (PyLongObject *)_PyLong_Copy(c); 2534 if (temp == NULL) 2535 goto Error; 2536 Py_DECREF(c); 2537 c = temp; 2538 temp = NULL; 2539 c->ob_size = - c->ob_size; 2540 } 2541 2542 /* if modulus == 1: 2543 return 0 */ 2544 if ((c->ob_size == 1) && (c->ob_digit[0] == 1)) { 2545 z = (PyLongObject *)PyLong_FromLong(0L); 2546 goto Done; 2547 } 2548 2549 /* if base < 0: 2550 base = base % modulus 2551 Having the base positive just makes things easier. */ 2552 if (a->ob_size < 0) { 2553 if (l_divmod(a, c, NULL, &temp) < 0) 2554 goto Error; 2555 Py_DECREF(a); 2556 a = temp; 2557 temp = NULL; 2558 } 2559 } 2560 2561 /* At this point a, b, and c are guaranteed non-negative UNLESS 2562 c is NULL, in which case a may be negative. */ 2563 2564 z = (PyLongObject *)PyLong_FromLong(1L); 2565 if (z == NULL) 2566 goto Error; 2567 2568 /* Perform a modular reduction, X = X % c, but leave X alone if c 2569 * is NULL. 2570 */ 2571#define REDUCE(X) \ 2572 if (c != NULL) { \ 2573 if (l_divmod(X, c, NULL, &temp) < 0) \ 2574 goto Error; \ 2575 Py_XDECREF(X); \ 2576 X = temp; \ 2577 temp = NULL; \ 2578 } 2579 2580 /* Multiply two values, then reduce the result: 2581 result = X*Y % c. If c is NULL, skip the mod. */ 2582#define MULT(X, Y, result) \ 2583{ \ 2584 temp = (PyLongObject *)long_mul(X, Y); \ 2585 if (temp == NULL) \ 2586 goto Error; \ 2587 Py_XDECREF(result); \ 2588 result = temp; \ 2589 temp = NULL; \ 2590 REDUCE(result) \ 2591} 2592 2593 if (b->ob_size <= FIVEARY_CUTOFF) { 2594 /* Left-to-right binary exponentiation (HAC Algorithm 14.79) */ 2595 /* http://www.cacr.math.uwaterloo.ca/hac/about/chap14.pdf */ 2596 for (i = b->ob_size - 1; i >= 0; --i) { 2597 digit bi = b->ob_digit[i]; 2598 2599 for (j = 1 << (SHIFT-1); j != 0; j >>= 1) { 2600 MULT(z, z, z) 2601 if (bi & j) 2602 MULT(z, a, z) 2603 } 2604 } 2605 } 2606 else { 2607 /* Left-to-right 5-ary exponentiation (HAC Algorithm 14.82) */ 2608 Py_INCREF(z); /* still holds 1L */ 2609 table[0] = z; 2610 for (i = 1; i < 32; ++i) 2611 MULT(table[i-1], a, table[i]) 2612 2613 for (i = b->ob_size - 1; i >= 0; --i) { 2614 const digit bi = b->ob_digit[i]; 2615 2616 for (j = SHIFT - 5; j >= 0; j -= 5) { 2617 const int index = (bi >> j) & 0x1f; 2618 for (k = 0; k < 5; ++k) 2619 MULT(z, z, z) 2620 if (index) 2621 MULT(z, table[index], z) 2622 } 2623 } 2624 } 2625 2626 if (negativeOutput && (z->ob_size != 0)) { 2627 temp = (PyLongObject *)long_sub(z, c); 2628 if (temp == NULL) 2629 goto Error; 2630 Py_DECREF(z); 2631 z = temp; 2632 temp = NULL; 2633 } 2634 goto Done; 2635 2636 Error: 2637 if (z != NULL) { 2638 Py_DECREF(z); 2639 z = NULL; 2640 } 2641 /* fall through */ 2642 Done: 2643 if (b->ob_size > FIVEARY_CUTOFF) { 2644 for (i = 0; i < 32; ++i) 2645 Py_XDECREF(table[i]); 2646 } 2647 Py_DECREF(a); 2648 Py_DECREF(b); 2649 Py_XDECREF(c); 2650 Py_XDECREF(temp); 2651 return (PyObject *)z; 2652} 2653 2654static PyObject * 2655long_invert(PyLongObject *v) 2656{ 2657 /* Implement ~x as -(x+1) */ 2658 PyLongObject *x; 2659 PyLongObject *w; 2660 w = (PyLongObject *)PyLong_FromLong(1L); 2661 if (w == NULL) 2662 return NULL; 2663 x = (PyLongObject *) long_add(v, w); 2664 Py_DECREF(w); 2665 if (x == NULL) 2666 return NULL; 2667 x->ob_size = -(x->ob_size); 2668 return (PyObject *)x; 2669} 2670 2671static PyObject * 2672long_pos(PyLongObject *v) 2673{ 2674 if (PyLong_CheckExact(v)) { 2675 Py_INCREF(v); 2676 return (PyObject *)v; 2677 } 2678 else 2679 return _PyLong_Copy(v); 2680} 2681 2682static PyObject * 2683long_neg(PyLongObject *v) 2684{ 2685 PyLongObject *z; 2686 if (v->ob_size == 0 && PyLong_CheckExact(v)) { 2687 /* -0 == 0 */ 2688 Py_INCREF(v); 2689 return (PyObject *) v; 2690 } 2691 z = (PyLongObject *)_PyLong_Copy(v); 2692 if (z != NULL) 2693 z->ob_size = -(v->ob_size); 2694 return (PyObject *)z; 2695} 2696 2697static PyObject * 2698long_abs(PyLongObject *v) 2699{ 2700 if (v->ob_size < 0) 2701 return long_neg(v); 2702 else 2703 return long_pos(v); 2704} 2705 2706static int 2707long_nonzero(PyLongObject *v) 2708{ 2709 return ABS(v->ob_size) != 0; 2710} 2711 2712static PyObject * 2713long_rshift(PyLongObject *v, PyLongObject *w) 2714{ 2715 PyLongObject *a, *b; 2716 PyLongObject *z = NULL; 2717 long shiftby; 2718 Py_ssize_t newsize, wordshift, loshift, hishift, i, j; 2719 digit lomask, himask; 2720 2721 CONVERT_BINOP((PyObject *)v, (PyObject *)w, &a, &b); 2722 2723 if (a->ob_size < 0) { 2724 /* Right shifting negative numbers is harder */ 2725 PyLongObject *a1, *a2; 2726 a1 = (PyLongObject *) long_invert(a); 2727 if (a1 == NULL) 2728 goto rshift_error; 2729 a2 = (PyLongObject *) long_rshift(a1, b); 2730 Py_DECREF(a1); 2731 if (a2 == NULL) 2732 goto rshift_error; 2733 z = (PyLongObject *) long_invert(a2); 2734 Py_DECREF(a2); 2735 } 2736 else { 2737 2738 shiftby = PyLong_AsLong((PyObject *)b); 2739 if (shiftby == -1L && PyErr_Occurred()) 2740 goto rshift_error; 2741 if (shiftby < 0) { 2742 PyErr_SetString(PyExc_ValueError, 2743 "negative shift count"); 2744 goto rshift_error; 2745 } 2746 wordshift = shiftby / SHIFT; 2747 newsize = ABS(a->ob_size) - wordshift; 2748 if (newsize <= 0) { 2749 z = _PyLong_New(0); 2750 Py_DECREF(a); 2751 Py_DECREF(b); 2752 return (PyObject *)z; 2753 } 2754 loshift = shiftby % SHIFT; 2755 hishift = SHIFT - loshift; 2756 lomask = ((digit)1 << hishift) - 1; 2757 himask = MASK ^ lomask; 2758 z = _PyLong_New(newsize); 2759 if (z == NULL) 2760 goto rshift_error; 2761 if (a->ob_size < 0) 2762 z->ob_size = -(z->ob_size); 2763 for (i = 0, j = wordshift; i < newsize; i++, j++) { 2764 z->ob_digit[i] = (a->ob_digit[j] >> loshift) & lomask; 2765 if (i+1 < newsize) 2766 z->ob_digit[i] |= 2767 (a->ob_digit[j+1] << hishift) & himask; 2768 } 2769 z = long_normalize(z); 2770 } 2771rshift_error: 2772 Py_DECREF(a); 2773 Py_DECREF(b); 2774 return (PyObject *) z; 2775 2776} 2777 2778static PyObject * 2779long_lshift(PyObject *v, PyObject *w) 2780{ 2781 /* This version due to Tim Peters */ 2782 PyLongObject *a, *b; 2783 PyLongObject *z = NULL; 2784 long shiftby; 2785 Py_ssize_t oldsize, newsize, wordshift, remshift, i, j; 2786 twodigits accum; 2787 2788 CONVERT_BINOP(v, w, &a, &b); 2789 2790 shiftby = PyLong_AsLong((PyObject *)b); 2791 if (shiftby == -1L && PyErr_Occurred()) 2792 goto lshift_error; 2793 if (shiftby < 0) { 2794 PyErr_SetString(PyExc_ValueError, "negative shift count"); 2795 goto lshift_error; 2796 } 2797 if ((long)(int)shiftby != shiftby) { 2798 PyErr_SetString(PyExc_ValueError, 2799 "outrageous left shift count"); 2800 goto lshift_error; 2801 } 2802 /* wordshift, remshift = divmod(shiftby, SHIFT) */ 2803 wordshift = (int)shiftby / SHIFT; 2804 remshift = (int)shiftby - wordshift * SHIFT; 2805 2806 oldsize = ABS(a->ob_size); 2807 newsize = oldsize + wordshift; 2808 if (remshift) 2809 ++newsize; 2810 z = _PyLong_New(newsize); 2811 if (z == NULL) 2812 goto lshift_error; 2813 if (a->ob_size < 0) 2814 z->ob_size = -(z->ob_size); 2815 for (i = 0; i < wordshift; i++) 2816 z->ob_digit[i] = 0; 2817 accum = 0; 2818 for (i = wordshift, j = 0; j < oldsize; i++, j++) { 2819 accum |= (twodigits)a->ob_digit[j] << remshift; 2820 z->ob_digit[i] = (digit)(accum & MASK); 2821 accum >>= SHIFT; 2822 } 2823 if (remshift) 2824 z->ob_digit[newsize-1] = (digit)accum; 2825 else 2826 assert(!accum); 2827 z = long_normalize(z); 2828lshift_error: 2829 Py_DECREF(a); 2830 Py_DECREF(b); 2831 return (PyObject *) z; 2832} 2833 2834 2835/* Bitwise and/xor/or operations */ 2836 2837static PyObject * 2838long_bitwise(PyLongObject *a, 2839 int op, /* '&', '|', '^' */ 2840 PyLongObject *b) 2841{ 2842 digit maska, maskb; /* 0 or MASK */ 2843 int negz; 2844 Py_ssize_t size_a, size_b, size_z; 2845 PyLongObject *z; 2846 int i; 2847 digit diga, digb; 2848 PyObject *v; 2849 2850 if (a->ob_size < 0) { 2851 a = (PyLongObject *) long_invert(a); 2852 if (a == NULL) 2853 return NULL; 2854 maska = MASK; 2855 } 2856 else { 2857 Py_INCREF(a); 2858 maska = 0; 2859 } 2860 if (b->ob_size < 0) { 2861 b = (PyLongObject *) long_invert(b); 2862 if (b == NULL) { 2863 Py_DECREF(a); 2864 return NULL; 2865 } 2866 maskb = MASK; 2867 } 2868 else { 2869 Py_INCREF(b); 2870 maskb = 0; 2871 } 2872 2873 negz = 0; 2874 switch (op) { 2875 case '^': 2876 if (maska != maskb) { 2877 maska ^= MASK; 2878 negz = -1; 2879 } 2880 break; 2881 case '&': 2882 if (maska && maskb) { 2883 op = '|'; 2884 maska ^= MASK; 2885 maskb ^= MASK; 2886 negz = -1; 2887 } 2888 break; 2889 case '|': 2890 if (maska || maskb) { 2891 op = '&'; 2892 maska ^= MASK; 2893 maskb ^= MASK; 2894 negz = -1; 2895 } 2896 break; 2897 } 2898 2899 /* JRH: The original logic here was to allocate the result value (z) 2900 as the longer of the two operands. However, there are some cases 2901 where the result is guaranteed to be shorter than that: AND of two 2902 positives, OR of two negatives: use the shorter number. AND with 2903 mixed signs: use the positive number. OR with mixed signs: use the 2904 negative number. After the transformations above, op will be '&' 2905 iff one of these cases applies, and mask will be non-0 for operands 2906 whose length should be ignored. 2907 */ 2908 2909 size_a = a->ob_size; 2910 size_b = b->ob_size; 2911 size_z = op == '&' 2912 ? (maska 2913 ? size_b 2914 : (maskb ? size_a : MIN(size_a, size_b))) 2915 : MAX(size_a, size_b); 2916 z = _PyLong_New(size_z); 2917 if (z == NULL) { 2918 Py_XDECREF(a); 2919 Py_XDECREF(b); 2920 Py_XDECREF(z); 2921 return NULL; 2922 } 2923 2924 for (i = 0; i < size_z; ++i) { 2925 diga = (i < size_a ? a->ob_digit[i] : 0) ^ maska; 2926 digb = (i < size_b ? b->ob_digit[i] : 0) ^ maskb; 2927 switch (op) { 2928 case '&': z->ob_digit[i] = diga & digb; break; 2929 case '|': z->ob_digit[i] = diga | digb; break; 2930 case '^': z->ob_digit[i] = diga ^ digb; break; 2931 } 2932 } 2933 2934 Py_DECREF(a); 2935 Py_DECREF(b); 2936 z = long_normalize(z); 2937 if (negz == 0) 2938 return (PyObject *) z; 2939 v = long_invert(z); 2940 Py_DECREF(z); 2941 return v; 2942} 2943 2944static PyObject * 2945long_and(PyObject *v, PyObject *w) 2946{ 2947 PyLongObject *a, *b; 2948 PyObject *c; 2949 CONVERT_BINOP(v, w, &a, &b); 2950 c = long_bitwise(a, '&', b); 2951 Py_DECREF(a); 2952 Py_DECREF(b); 2953 return c; 2954} 2955 2956static PyObject * 2957long_xor(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_or(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 int 2981long_coerce(PyObject **pv, PyObject **pw) 2982{ 2983 if (PyInt_Check(*pw)) { 2984 *pw = PyLong_FromLong(PyInt_AS_LONG(*pw)); 2985 Py_INCREF(*pv); 2986 return 0; 2987 } 2988 else if (PyLong_Check(*pw)) { 2989 Py_INCREF(*pv); 2990 Py_INCREF(*pw); 2991 return 0; 2992 } 2993 return 1; /* Can't do it */ 2994} 2995 2996static PyObject * 2997long_long(PyObject *v) 2998{ 2999 if (PyLong_CheckExact(v)) 3000 Py_INCREF(v); 3001 else 3002 v = _PyLong_Copy((PyLongObject *)v); 3003 return v; 3004} 3005 3006static PyObject * 3007long_int(PyObject *v) 3008{ 3009 long x; 3010 x = PyLong_AsLong(v); 3011 if (PyErr_Occurred()) { 3012 if (PyErr_ExceptionMatches(PyExc_OverflowError)) { 3013 PyErr_Clear(); 3014 if (PyLong_CheckExact(v)) { 3015 Py_INCREF(v); 3016 return v; 3017 } 3018 else 3019 return _PyLong_Copy((PyLongObject *)v); 3020 } 3021 else 3022 return NULL; 3023 } 3024 return PyInt_FromLong(x); 3025} 3026 3027static PyObject * 3028long_float(PyObject *v) 3029{ 3030 double result; 3031 result = PyLong_AsDouble(v); 3032 if (result == -1.0 && PyErr_Occurred()) 3033 return NULL; 3034 return PyFloat_FromDouble(result); 3035} 3036 3037static PyObject * 3038long_oct(PyObject *v) 3039{ 3040 return long_format(v, 8, 1); 3041} 3042 3043static PyObject * 3044long_hex(PyObject *v) 3045{ 3046 return long_format(v, 16, 1); 3047} 3048 3049static PyObject * 3050long_subtype_new(PyTypeObject *type, PyObject *args, PyObject *kwds); 3051 3052static PyObject * 3053long_new(PyTypeObject *type, PyObject *args, PyObject *kwds) 3054{ 3055 PyObject *x = NULL; 3056 int base = -909; /* unlikely! */ 3057 static char *kwlist[] = {"x", "base", 0}; 3058 3059 if (type != &PyLong_Type) 3060 return long_subtype_new(type, args, kwds); /* Wimp out */ 3061 if (!PyArg_ParseTupleAndKeywords(args, kwds, "|Oi:long", kwlist, 3062 &x, &base)) 3063 return NULL; 3064 if (x == NULL) 3065 return PyLong_FromLong(0L); 3066 if (base == -909) 3067 return PyNumber_Long(x); 3068 else if (PyString_Check(x)) 3069 return PyLong_FromString(PyString_AS_STRING(x), NULL, base); 3070#ifdef Py_USING_UNICODE 3071 else if (PyUnicode_Check(x)) 3072 return PyLong_FromUnicode(PyUnicode_AS_UNICODE(x), 3073 PyUnicode_GET_SIZE(x), 3074 base); 3075#endif 3076 else { 3077 PyErr_SetString(PyExc_TypeError, 3078 "long() can't convert non-string with explicit base"); 3079 return NULL; 3080 } 3081} 3082 3083/* Wimpy, slow approach to tp_new calls for subtypes of long: 3084 first create a regular long from whatever arguments we got, 3085 then allocate a subtype instance and initialize it from 3086 the regular long. The regular long is then thrown away. 3087*/ 3088static PyObject * 3089long_subtype_new(PyTypeObject *type, PyObject *args, PyObject *kwds) 3090{ 3091 PyLongObject *tmp, *newobj; 3092 Py_ssize_t i, n; 3093 3094 assert(PyType_IsSubtype(type, &PyLong_Type)); 3095 tmp = (PyLongObject *)long_new(&PyLong_Type, args, kwds); 3096 if (tmp == NULL) 3097 return NULL; 3098 assert(PyLong_CheckExact(tmp)); 3099 n = tmp->ob_size; 3100 if (n < 0) 3101 n = -n; 3102 newobj = (PyLongObject *)type->tp_alloc(type, n); 3103 if (newobj == NULL) { 3104 Py_DECREF(tmp); 3105 return NULL; 3106 } 3107 assert(PyLong_Check(newobj)); 3108 newobj->ob_size = tmp->ob_size; 3109 for (i = 0; i < n; i++) 3110 newobj->ob_digit[i] = tmp->ob_digit[i]; 3111 Py_DECREF(tmp); 3112 return (PyObject *)newobj; 3113} 3114 3115static PyObject * 3116long_getnewargs(PyLongObject *v) 3117{ 3118 return Py_BuildValue("(N)", _PyLong_Copy(v)); 3119} 3120 3121static PyMethodDef long_methods[] = { 3122 {"__getnewargs__", (PyCFunction)long_getnewargs, METH_NOARGS}, 3123 {NULL, NULL} /* sentinel */ 3124}; 3125 3126PyDoc_STRVAR(long_doc, 3127"long(x[, base]) -> integer\n\ 3128\n\ 3129Convert a string or number to a long integer, if possible. A floating\n\ 3130point argument will be truncated towards zero (this does not include a\n\ 3131string representation of a floating point number!) When converting a\n\ 3132string, use the optional base. It is an error to supply a base when\n\ 3133converting a non-string."); 3134 3135static PyNumberMethods long_as_number = { 3136 (binaryfunc) long_add, /*nb_add*/ 3137 (binaryfunc) long_sub, /*nb_subtract*/ 3138 (binaryfunc) long_mul, /*nb_multiply*/ 3139 long_classic_div, /*nb_divide*/ 3140 long_mod, /*nb_remainder*/ 3141 long_divmod, /*nb_divmod*/ 3142 long_pow, /*nb_power*/ 3143 (unaryfunc) long_neg, /*nb_negative*/ 3144 (unaryfunc) long_pos, /*tp_positive*/ 3145 (unaryfunc) long_abs, /*tp_absolute*/ 3146 (inquiry) long_nonzero, /*tp_nonzero*/ 3147 (unaryfunc) long_invert, /*nb_invert*/ 3148 long_lshift, /*nb_lshift*/ 3149 (binaryfunc) long_rshift, /*nb_rshift*/ 3150 long_and, /*nb_and*/ 3151 long_xor, /*nb_xor*/ 3152 long_or, /*nb_or*/ 3153 long_coerce, /*nb_coerce*/ 3154 long_int, /*nb_int*/ 3155 long_long, /*nb_long*/ 3156 long_float, /*nb_float*/ 3157 long_oct, /*nb_oct*/ 3158 long_hex, /*nb_hex*/ 3159 0, /* nb_inplace_add */ 3160 0, /* nb_inplace_subtract */ 3161 0, /* nb_inplace_multiply */ 3162 0, /* nb_inplace_divide */ 3163 0, /* nb_inplace_remainder */ 3164 0, /* nb_inplace_power */ 3165 0, /* nb_inplace_lshift */ 3166 0, /* nb_inplace_rshift */ 3167 0, /* nb_inplace_and */ 3168 0, /* nb_inplace_xor */ 3169 0, /* nb_inplace_or */ 3170 long_div, /* nb_floor_divide */ 3171 long_true_divide, /* nb_true_divide */ 3172 0, /* nb_inplace_floor_divide */ 3173 0, /* nb_inplace_true_divide */ 3174 long_index, /* nb_index */ 3175}; 3176 3177PyTypeObject PyLong_Type = { 3178 PyObject_HEAD_INIT(&PyType_Type) 3179 0, /* ob_size */ 3180 "long", /* tp_name */ 3181 sizeof(PyLongObject) - sizeof(digit), /* tp_basicsize */ 3182 sizeof(digit), /* tp_itemsize */ 3183 long_dealloc, /* tp_dealloc */ 3184 0, /* tp_print */ 3185 0, /* tp_getattr */ 3186 0, /* tp_setattr */ 3187 (cmpfunc)long_compare, /* tp_compare */ 3188 long_repr, /* tp_repr */ 3189 &long_as_number, /* tp_as_number */ 3190 0, /* tp_as_sequence */ 3191 0, /* tp_as_mapping */ 3192 (hashfunc)long_hash, /* tp_hash */ 3193 0, /* tp_call */ 3194 long_str, /* tp_str */ 3195 PyObject_GenericGetAttr, /* tp_getattro */ 3196 0, /* tp_setattro */ 3197 0, /* tp_as_buffer */ 3198 Py_TPFLAGS_DEFAULT | Py_TPFLAGS_CHECKTYPES | 3199 Py_TPFLAGS_BASETYPE, /* tp_flags */ 3200 long_doc, /* tp_doc */ 3201 0, /* tp_traverse */ 3202 0, /* tp_clear */ 3203 0, /* tp_richcompare */ 3204 0, /* tp_weaklistoffset */ 3205 0, /* tp_iter */ 3206 0, /* tp_iternext */ 3207 long_methods, /* tp_methods */ 3208 0, /* tp_members */ 3209 0, /* tp_getset */ 3210 0, /* tp_base */ 3211 0, /* tp_dict */ 3212 0, /* tp_descr_get */ 3213 0, /* tp_descr_set */ 3214 0, /* tp_dictoffset */ 3215 0, /* tp_init */ 3216 0, /* tp_alloc */ 3217 long_new, /* tp_new */ 3218 PyObject_Del, /* tp_free */ 3219}; 3220