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