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