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