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