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