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