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