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