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