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