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