longobject.c revision eb1fafcec14725f71aadf3874df6507a5fe577a1
1/*********************************************************** 2Copyright 1991, 1992, 1993, 1994 by Stichting Mathematisch Centrum, 3Amsterdam, The 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 not be used in advertising or publicity pertaining to 13distribution of the software without specific, written prior permission. 14 15STICHTING MATHEMATISCH CENTRUM DISCLAIMS ALL WARRANTIES WITH REGARD TO 16THIS SOFTWARE, INCLUDING ALL IMPLIED WARRANTIES OF MERCHANTABILITY AND 17FITNESS, IN NO EVENT SHALL STICHTING MATHEMATISCH CENTRUM BE LIABLE 18FOR ANY SPECIAL, INDIRECT OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES 19WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN 20ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT 21OF OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE. 22 23******************************************************************/ 24 25/* Long (arbitrary precision) integer object implementation */ 26 27/* XXX The functional organization of this file is terrible */ 28 29#include "allobjects.h" 30#include "longintrepr.h" 31#include <math.h> 32#include <assert.h> 33#include <ctype.h> 34 35#define ABS(x) ((x) < 0 ? -(x) : (x)) 36 37/* Forward */ 38static longobject *long_normalize PROTO((longobject *)); 39static longobject *mul1 PROTO((longobject *, wdigit)); 40static longobject *muladd1 PROTO((longobject *, wdigit, wdigit)); 41static longobject *divrem1 PROTO((longobject *, wdigit, digit *)); 42static object *long_format PROTO((object *aa, int base)); 43 44static int ticker; /* XXX Could be shared with ceval? */ 45 46#define SIGCHECK(block) \ 47 if (--ticker < 0) { \ 48 ticker = 100; \ 49 if (sigcheck()) { block; } \ 50 } 51 52/* Normalize (remove leading zeros from) a long int object. 53 Doesn't attempt to free the storage--in most cases, due to the nature 54 of the algorithms used, this could save at most be one word anyway. */ 55 56static longobject * 57long_normalize(v) 58 register longobject *v; 59{ 60 int j = ABS(v->ob_size); 61 register int i = j; 62 63 while (i > 0 && v->ob_digit[i-1] == 0) 64 --i; 65 if (i != j) 66 v->ob_size = (v->ob_size < 0) ? -(i) : i; 67 return v; 68} 69 70/* Allocate a new long int object with size digits. 71 Return NULL and set exception if we run out of memory. */ 72 73longobject * 74alloclongobject(size) 75 int size; 76{ 77 return NEWVAROBJ(longobject, &Longtype, size); 78} 79 80/* Create a new long int object from a C long int */ 81 82object * 83newlongobject(ival) 84 long ival; 85{ 86 /* Assume a C long fits in at most 3 'digits' */ 87 /* XXX On 64 bit machines this isn't true!!! */ 88 longobject *v = alloclongobject(3); 89 if (v != NULL) { 90 if (ival < 0) { 91 ival = -ival; 92 v->ob_size = -(v->ob_size); 93 } 94 v->ob_digit[0] = ival & MASK; 95 v->ob_digit[1] = (ival >> SHIFT) & MASK; 96 v->ob_digit[2] = ((unsigned long)ival >> (2*SHIFT)) & MASK; 97 v = long_normalize(v); 98 } 99 return (object *)v; 100} 101 102/* Create a new long int object from a C double */ 103 104object * 105dnewlongobject(dval) 106 double dval; 107{ 108 longobject *v; 109 double frac; 110 int i, ndig, expo, neg; 111 neg = 0; 112 if (dval < 0.0) { 113 neg = 1; 114 dval = -dval; 115 } 116 frac = frexp(dval, &expo); /* dval = frac*2**expo; 0.0 <= frac < 1.0 */ 117 if (expo <= 0) 118 return newlongobject(0L); 119 ndig = (expo-1) / SHIFT + 1; /* Number of 'digits' in result */ 120 v = alloclongobject(ndig); 121 if (v == NULL) 122 return NULL; 123 frac = ldexp(frac, (expo-1) % SHIFT + 1); 124 for (i = ndig; --i >= 0; ) { 125 long bits = (long)frac; 126 v->ob_digit[i] = bits; 127 frac = frac - (double)bits; 128 frac = ldexp(frac, SHIFT); 129 } 130 if (neg) 131 v->ob_size = -(v->ob_size); 132 return (object *)v; 133} 134 135/* Get a C long int from a long int object. 136 Returns -1 and sets an error condition if overflow occurs. */ 137 138long 139getlongvalue(vv) 140 object *vv; 141{ 142 register longobject *v; 143 long x, prev; 144 int i, sign; 145 146 if (vv == NULL || !is_longobject(vv)) { 147 err_badcall(); 148 return -1; 149 } 150 v = (longobject *)vv; 151 i = v->ob_size; 152 sign = 1; 153 x = 0; 154 if (i < 0) { 155 sign = -1; 156 i = -(i); 157 } 158 while (--i >= 0) { 159 prev = x; 160 x = (x << SHIFT) + v->ob_digit[i]; 161 if ((x >> SHIFT) != prev) { 162 err_setstr(ValueError, 163 "long int too long to convert"); 164 return -1; 165 } 166 } 167 return x * sign; 168} 169 170/* Get a C double from a long int object. No overflow check. */ 171 172double 173dgetlongvalue(vv) 174 object *vv; 175{ 176 register longobject *v; 177 double x; 178 double multiplier = (double) (1L << SHIFT); 179 int i, sign; 180 181 if (vv == NULL || !is_longobject(vv)) { 182 err_badcall(); 183 return -1; 184 } 185 v = (longobject *)vv; 186 i = v->ob_size; 187 sign = 1; 188 x = 0.0; 189 if (i < 0) { 190 sign = -1; 191 i = -(i); 192 } 193 while (--i >= 0) { 194 x = x*multiplier + (double)v->ob_digit[i]; 195 } 196 return x * sign; 197} 198 199/* Multiply by a single digit, ignoring the sign. */ 200 201static longobject * 202mul1(a, n) 203 longobject *a; 204 wdigit n; 205{ 206 return muladd1(a, n, (digit)0); 207} 208 209/* Multiply by a single digit and add a single digit, ignoring the sign. */ 210 211static longobject * 212muladd1(a, n, extra) 213 longobject *a; 214 wdigit n; 215 wdigit extra; 216{ 217 int size_a = ABS(a->ob_size); 218 longobject *z = alloclongobject(size_a+1); 219 twodigits carry = extra; 220 int i; 221 222 if (z == NULL) 223 return NULL; 224 for (i = 0; i < size_a; ++i) { 225 carry += (twodigits)a->ob_digit[i] * n; 226 z->ob_digit[i] = carry & MASK; 227 carry >>= SHIFT; 228 } 229 z->ob_digit[i] = carry; 230 return long_normalize(z); 231} 232 233/* Divide a long integer by a digit, returning both the quotient 234 (as function result) and the remainder (through *prem). 235 The sign of a is ignored; n should not be zero. */ 236 237static longobject * 238divrem1(a, n, prem) 239 longobject *a; 240 wdigit n; 241 digit *prem; 242{ 243 int size = ABS(a->ob_size); 244 longobject *z; 245 int i; 246 twodigits rem = 0; 247 248 assert(n > 0 && n <= MASK); 249 z = alloclongobject(size); 250 if (z == NULL) 251 return NULL; 252 for (i = size; --i >= 0; ) { 253 rem = (rem << SHIFT) + a->ob_digit[i]; 254 z->ob_digit[i] = rem/n; 255 rem %= n; 256 } 257 *prem = rem; 258 return long_normalize(z); 259} 260 261/* Convert a long int object to a string, using a given conversion base. 262 Return a string object. 263 If base is 8 or 16, add the proper prefix '0' or '0x'. 264 External linkage: used in bltinmodule.c by hex() and oct(). */ 265 266static object * 267long_format(aa, base) 268 object *aa; 269 int base; 270{ 271 register longobject *a = (longobject *)aa; 272 stringobject *str; 273 int i; 274 int size_a = ABS(a->ob_size); 275 char *p; 276 int bits; 277 char sign = '\0'; 278 279 if (a == NULL || !is_longobject(a)) { 280 err_badcall(); 281 return NULL; 282 } 283 assert(base >= 2 && base <= 36); 284 285 /* Compute a rough upper bound for the length of the string */ 286 i = base; 287 bits = 0; 288 while (i > 1) { 289 ++bits; 290 i >>= 1; 291 } 292 i = 6 + (size_a*SHIFT + bits-1) / bits; 293 str = (stringobject *) newsizedstringobject((char *)0, i); 294 if (str == NULL) 295 return NULL; 296 p = GETSTRINGVALUE(str) + i; 297 *p = '\0'; 298 *--p = 'L'; 299 if (a->ob_size < 0) 300 sign = '-'; 301 302 INCREF(a); 303 do { 304 digit rem; 305 longobject *temp = divrem1(a, (digit)base, &rem); 306 if (temp == NULL) { 307 DECREF(a); 308 DECREF(str); 309 return NULL; 310 } 311 if (rem < 10) 312 rem += '0'; 313 else 314 rem += 'A'-10; 315 assert(p > GETSTRINGVALUE(str)); 316 *--p = rem; 317 DECREF(a); 318 a = temp; 319 SIGCHECK({ 320 DECREF(a); 321 DECREF(str); 322 return NULL; 323 }) 324 } while (ABS(a->ob_size) != 0); 325 DECREF(a); 326 if (base == 8) { 327 if (size_a != 0) 328 *--p = '0'; 329 } 330 else if (base == 16) { 331 *--p = 'x'; 332 *--p = '0'; 333 } 334 else if (base != 10) { 335 *--p = '#'; 336 *--p = '0' + base%10; 337 if (base > 10) 338 *--p = '0' + base/10; 339 } 340 if (sign) 341 *--p = sign; 342 if (p != GETSTRINGVALUE(str)) { 343 char *q = GETSTRINGVALUE(str); 344 assert(p > q); 345 do { 346 } while ((*q++ = *p++) != '\0'); 347 q--; 348 resizestring((object **)&str, (int) (q - GETSTRINGVALUE(str))); 349 } 350 return (object *)str; 351} 352 353/* Convert a string to a long int object, in a given base. 354 Base zero implies a default depending on the number. 355 External linkage: used in compile.c and stropmodule.c. */ 356 357object * 358long_scan(str, base) 359 char *str; 360 int base; 361{ 362 return long_escan(str, (char **)NULL, base); 363} 364 365object * 366long_escan(str, pend, base) 367 char *str; 368 char **pend; 369 int base; 370{ 371 int sign = 1; 372 longobject *z; 373 374 if (base != 0 && base < 2 || base > 36) { 375 err_setstr(ValueError, "invalid base for long literal"); 376 return NULL; 377 } 378 while (*str != '\0' && isspace(*str)) 379 str++; 380 if (*str == '+') 381 ++str; 382 else if (*str == '-') { 383 ++str; 384 sign = -1; 385 } 386 while (*str != '\0' && isspace(*str)) 387 str++; 388 if (base == 0) { 389 if (str[0] != '0') 390 base = 10; 391 else if (str[1] == 'x' || str[1] == 'X') 392 base = 16; 393 else 394 base = 8; 395 } 396 if (base == 16 && str[0] == '0' && (str[1] == 'x' || str[1] == 'X')) 397 str += 2; 398 z = alloclongobject(0); 399 for ( ; z != NULL; ++str) { 400 int k = -1; 401 longobject *temp; 402 403 if (*str <= '9') 404 k = *str - '0'; 405 else if (*str >= 'a') 406 k = *str - 'a' + 10; 407 else if (*str >= 'A') 408 k = *str - 'A' + 10; 409 if (k < 0 || k >= base) 410 break; 411 temp = muladd1(z, (digit)base, (digit)k); 412 DECREF(z); 413 z = temp; 414 } 415 if (sign < 0 && z != NULL && z->ob_size != 0) 416 z->ob_size = -(z->ob_size); 417 if (pend) 418 *pend = str; 419 return (object *) z; 420} 421 422static longobject *x_divrem PROTO((longobject *, longobject *, longobject **)); 423static object *long_pos PROTO((longobject *)); 424static long_divrem PROTO((longobject *, longobject *, 425 longobject **, longobject **)); 426 427/* Long division with remainder, top-level routine */ 428 429static int 430long_divrem(a, b, pdiv, prem) 431 longobject *a, *b; 432 longobject **pdiv; 433 longobject **prem; 434{ 435 int size_a = ABS(a->ob_size), size_b = ABS(b->ob_size); 436 longobject *z; 437 438 if (size_b == 0) { 439 err_setstr(ZeroDivisionError, "long division or modulo"); 440 return -1; 441 } 442 if (size_a < size_b || 443 size_a == size_b && 444 a->ob_digit[size_a-1] < b->ob_digit[size_b-1]) { 445 /* |a| < |b|. */ 446 *pdiv = alloclongobject(0); 447 INCREF(a); 448 *prem = (longobject *) a; 449 return 0; 450 } 451 if (size_b == 1) { 452 digit rem = 0; 453 z = divrem1(a, b->ob_digit[0], &rem); 454 if (z == NULL) 455 return -1; 456 *prem = (longobject *) newlongobject((long)rem); 457 } 458 else { 459 z = x_divrem(a, b, prem); 460 if (z == NULL) 461 return -1; 462 } 463 /* Set the signs. 464 The quotient z has the sign of a*b; 465 the remainder r has the sign of a, 466 so a = b*z + r. */ 467 if ((a->ob_size < 0) != (b->ob_size < 0)) 468 z->ob_size = -(z->ob_size); 469 if (a->ob_size < 0 && (*prem)->ob_size != 0) 470 (*prem)->ob_size = -((*prem)->ob_size); 471 *pdiv = z; 472 return 0; 473} 474 475/* Unsigned long division with remainder -- the algorithm */ 476 477static longobject * 478x_divrem(v1, w1, prem) 479 longobject *v1, *w1; 480 longobject **prem; 481{ 482 int size_v = ABS(v1->ob_size), size_w = ABS(w1->ob_size); 483 digit d = (twodigits)BASE / (w1->ob_digit[size_w-1] + 1); 484 longobject *v = mul1(v1, d); 485 longobject *w = mul1(w1, d); 486 longobject *a; 487 int j, k; 488 489 if (v == NULL || w == NULL) { 490 XDECREF(v); 491 XDECREF(w); 492 return NULL; 493 } 494 495 assert(size_v >= size_w && size_w > 1); /* Assert checks by div() */ 496 assert(v->ob_refcnt == 1); /* Since v will be used as accumulator! */ 497 assert(size_w == ABS(w->ob_size)); /* That's how d was calculated */ 498 499 size_v = ABS(v->ob_size); 500 a = alloclongobject(size_v - size_w + 1); 501 502 for (j = size_v, k = a->ob_size-1; a != NULL && k >= 0; --j, --k) { 503 digit vj = (j >= size_v) ? 0 : v->ob_digit[j]; 504 twodigits q; 505 stwodigits carry = 0; 506 int i; 507 508 SIGCHECK({ 509 DECREF(a); 510 a = NULL; 511 break; 512 }) 513 if (vj == w->ob_digit[size_w-1]) 514 q = MASK; 515 else 516 q = (((twodigits)vj << SHIFT) + v->ob_digit[j-1]) / 517 w->ob_digit[size_w-1]; 518 519 while (w->ob_digit[size_w-2]*q > 520 (( 521 ((twodigits)vj << SHIFT) 522 + v->ob_digit[j-1] 523 - q*w->ob_digit[size_w-1] 524 ) << SHIFT) 525 + v->ob_digit[j-2]) 526 --q; 527 528 for (i = 0; i < size_w && i+k < size_v; ++i) { 529 twodigits z = w->ob_digit[i] * q; 530 digit zz = z >> SHIFT; 531 carry += v->ob_digit[i+k] - z + ((twodigits)zz << SHIFT); 532 v->ob_digit[i+k] = carry & MASK; 533 carry = (carry >> SHIFT) - zz; 534 } 535 536 if (i+k < size_v) { 537 carry += v->ob_digit[i+k]; 538 v->ob_digit[i+k] = 0; 539 } 540 541 if (carry == 0) 542 a->ob_digit[k] = q; 543 else { 544 assert(carry == -1); 545 a->ob_digit[k] = q-1; 546 carry = 0; 547 for (i = 0; i < size_w && i+k < size_v; ++i) { 548 carry += v->ob_digit[i+k] + w->ob_digit[i]; 549 v->ob_digit[i+k] = carry & MASK; 550 carry >>= SHIFT; 551 } 552 } 553 } /* for j, k */ 554 555 if (a != NULL) { 556 a = long_normalize(a); 557 *prem = divrem1(v, d, &d); 558 /* d receives the (unused) remainder */ 559 if (*prem == NULL) { 560 DECREF(a); 561 a = NULL; 562 } 563 } 564 DECREF(v); 565 DECREF(w); 566 return a; 567} 568 569/* Methods */ 570 571/* Forward */ 572static void long_dealloc PROTO((object *)); 573static int long_print PROTO((object *, FILE *, int)); 574static object *long_repr PROTO((object *)); 575static int long_compare PROTO((longobject *, longobject *)); 576static long long_hash PROTO((longobject *)); 577 578static object *long_add PROTO((longobject *, longobject *)); 579static object *long_sub PROTO((longobject *, longobject *)); 580static object *long_mul PROTO((longobject *, longobject *)); 581static object *long_div PROTO((longobject *, longobject *)); 582static object *long_mod PROTO((longobject *, longobject *)); 583static object *long_divmod PROTO((longobject *, longobject *)); 584static object *long_pow PROTO((longobject *, longobject *, longobject *)); 585static object *long_neg PROTO((longobject *)); 586static object *long_pos PROTO((longobject *)); 587static object *long_abs PROTO((longobject *)); 588static int long_nonzero PROTO((longobject *)); 589static object *long_invert PROTO((longobject *)); 590static object *long_lshift PROTO((longobject *, longobject *)); 591static object *long_rshift PROTO((longobject *, longobject *)); 592static object *long_and PROTO((longobject *, longobject *)); 593static object *long_xor PROTO((longobject *, longobject *)); 594static object *long_or PROTO((longobject *, longobject *)); 595 596static void 597long_dealloc(v) 598 object *v; 599{ 600 DEL(v); 601} 602 603static object * 604long_repr(v) 605 object *v; 606{ 607 return long_format(v, 10); 608} 609 610static int 611long_compare(a, b) 612 longobject *a, *b; 613{ 614 int sign; 615 616 if (a->ob_size != b->ob_size) { 617 if (ABS(a->ob_size) == 0 && ABS(b->ob_size) == 0) 618 sign = 0; 619 else 620 sign = a->ob_size - b->ob_size; 621 } 622 else { 623 int i = ABS(a->ob_size); 624 while (--i >= 0 && a->ob_digit[i] == b->ob_digit[i]) 625 ; 626 if (i < 0) 627 sign = 0; 628 else { 629 sign = (int)a->ob_digit[i] - (int)b->ob_digit[i]; 630 if (a->ob_size < 0) 631 sign = -sign; 632 } 633 } 634 return sign < 0 ? -1 : sign > 0 ? 1 : 0; 635} 636 637static long 638long_hash(v) 639 longobject *v; 640{ 641 long x; 642 int i, sign; 643 644 /* This is designed so that Python ints and longs with the 645 same value hash to the same value, otherwise comparisons 646 of mapping keys will turn out weird */ 647 i = v->ob_size; 648 sign = 1; 649 x = 0; 650 if (i < 0) { 651 sign = -1; 652 i = -(i); 653 } 654 while (--i >= 0) { 655 /* Force a 32-bit circular shift */ 656 x = ((x << SHIFT) & ~MASK) | ((x >> (32-SHIFT)) & MASK); 657 x += v->ob_digit[i]; 658 } 659 x = x * sign; 660 if (x == -1) 661 x = -2; 662 return x; 663} 664 665 666/* Add the absolute values of two long integers. */ 667 668static longobject *x_add PROTO((longobject *, longobject *)); 669static longobject * 670x_add(a, b) 671 longobject *a, *b; 672{ 673 int size_a = ABS(a->ob_size), size_b = ABS(b->ob_size); 674 longobject *z; 675 int i; 676 digit carry = 0; 677 678 /* Ensure a is the larger of the two: */ 679 if (size_a < size_b) { 680 { longobject *temp = a; a = b; b = temp; } 681 { int size_temp = size_a; size_a = size_b; size_b = size_temp; } 682 } 683 z = alloclongobject(size_a+1); 684 if (z == NULL) 685 return NULL; 686 for (i = 0; i < size_b; ++i) { 687 carry += a->ob_digit[i] + b->ob_digit[i]; 688 z->ob_digit[i] = carry & MASK; 689 /* The following assumes unsigned shifts don't 690 propagate the sign bit. */ 691 carry >>= SHIFT; 692 } 693 for (; i < size_a; ++i) { 694 carry += a->ob_digit[i]; 695 z->ob_digit[i] = carry & MASK; 696 carry >>= SHIFT; 697 } 698 z->ob_digit[i] = carry; 699 return long_normalize(z); 700} 701 702/* Subtract the absolute values of two integers. */ 703 704static longobject *x_sub PROTO((longobject *, longobject *)); 705static longobject * 706x_sub(a, b) 707 longobject *a, *b; 708{ 709 int size_a = ABS(a->ob_size), size_b = ABS(b->ob_size); 710 longobject *z; 711 int i; 712 int sign = 1; 713 digit borrow = 0; 714 715 /* Ensure a is the larger of the two: */ 716 if (size_a < size_b) { 717 sign = -1; 718 { longobject *temp = a; a = b; b = temp; } 719 { int size_temp = size_a; size_a = size_b; size_b = size_temp; } 720 } 721 else if (size_a == size_b) { 722 /* Find highest digit where a and b differ: */ 723 i = size_a; 724 while (--i >= 0 && a->ob_digit[i] == b->ob_digit[i]) 725 ; 726 if (i < 0) 727 return alloclongobject(0); 728 if (a->ob_digit[i] < b->ob_digit[i]) { 729 sign = -1; 730 { longobject *temp = a; a = b; b = temp; } 731 } 732 size_a = size_b = i+1; 733 } 734 z = alloclongobject(size_a); 735 if (z == NULL) 736 return NULL; 737 for (i = 0; i < size_b; ++i) { 738 /* The following assumes unsigned arithmetic 739 works module 2**N for some N>SHIFT. */ 740 borrow = a->ob_digit[i] - b->ob_digit[i] - borrow; 741 z->ob_digit[i] = borrow & MASK; 742 borrow >>= SHIFT; 743 borrow &= 1; /* Keep only one sign bit */ 744 } 745 for (; i < size_a; ++i) { 746 borrow = a->ob_digit[i] - borrow; 747 z->ob_digit[i] = borrow & MASK; 748 borrow >>= SHIFT; 749 } 750 assert(borrow == 0); 751 if (sign < 0) 752 z->ob_size = -(z->ob_size); 753 return long_normalize(z); 754} 755 756static object * 757long_add(a, b) 758 longobject *a; 759 longobject *b; 760{ 761 longobject *z; 762 763 if (a->ob_size < 0) { 764 if (b->ob_size < 0) { 765 z = x_add(a, b); 766 if (z != NULL && z->ob_size != 0) 767 z->ob_size = -(z->ob_size); 768 } 769 else 770 z = x_sub(b, a); 771 } 772 else { 773 if (b->ob_size < 0) 774 z = x_sub(a, b); 775 else 776 z = x_add(a, b); 777 } 778 return (object *)z; 779} 780 781static object * 782long_sub(a, b) 783 longobject *a; 784 longobject *b; 785{ 786 longobject *z; 787 788 if (a->ob_size < 0) { 789 if (b->ob_size < 0) 790 z = x_sub(a, b); 791 else 792 z = x_add(a, b); 793 if (z != NULL && z->ob_size != 0) 794 z->ob_size = -(z->ob_size); 795 } 796 else { 797 if (b->ob_size < 0) 798 z = x_add(a, b); 799 else 800 z = x_sub(a, b); 801 } 802 return (object *)z; 803} 804 805static object * 806long_mul(a, b) 807 longobject *a; 808 longobject *b; 809{ 810 int size_a; 811 int size_b; 812 longobject *z; 813 int i; 814 815 size_a = ABS(a->ob_size); 816 size_b = ABS(b->ob_size); 817 z = alloclongobject(size_a + size_b); 818 if (z == NULL) 819 return NULL; 820 for (i = 0; i < z->ob_size; ++i) 821 z->ob_digit[i] = 0; 822 for (i = 0; i < size_a; ++i) { 823 twodigits carry = 0; 824 twodigits f = a->ob_digit[i]; 825 int j; 826 827 SIGCHECK({ 828 DECREF(z); 829 return NULL; 830 }) 831 for (j = 0; j < size_b; ++j) { 832 carry += z->ob_digit[i+j] + b->ob_digit[j] * f; 833 z->ob_digit[i+j] = carry & MASK; 834 carry >>= SHIFT; 835 } 836 for (; carry != 0; ++j) { 837 assert(i+j < z->ob_size); 838 carry += z->ob_digit[i+j]; 839 z->ob_digit[i+j] = carry & MASK; 840 carry >>= SHIFT; 841 } 842 } 843 if (a->ob_size < 0) 844 z->ob_size = -(z->ob_size); 845 if (b->ob_size < 0) 846 z->ob_size = -(z->ob_size); 847 return (object *) long_normalize(z); 848} 849 850/* The / and % operators are now defined in terms of divmod(). 851 The expression a mod b has the value a - b*floor(a/b). 852 The long_divrem function gives the remainder after division of 853 |a| by |b|, with the sign of a. This is also expressed 854 as a - b*trunc(a/b), if trunc truncates towards zero. 855 Some examples: 856 a b a rem b a mod b 857 13 10 3 3 858 -13 10 -3 7 859 13 -10 3 -7 860 -13 -10 -3 -3 861 So, to get from rem to mod, we have to add b if a and b 862 have different signs. We then subtract one from the 'div' 863 part of the outcome to keep the invariant intact. */ 864 865static int l_divmod PROTO((longobject *, longobject *, 866 longobject **, longobject **)); 867static int 868l_divmod(v, w, pdiv, pmod) 869 longobject *v; 870 longobject *w; 871 longobject **pdiv; 872 longobject **pmod; 873{ 874 longobject *div, *mod; 875 876 if (long_divrem(v, w, &div, &mod) < 0) 877 return -1; 878 if (mod->ob_size < 0 && w->ob_size > 0 || 879 mod->ob_size > 0 && w->ob_size < 0) { 880 longobject *temp; 881 longobject *one; 882 temp = (longobject *) long_add(mod, w); 883 DECREF(mod); 884 mod = temp; 885 if (mod == NULL) { 886 DECREF(div); 887 return -1; 888 } 889 one = (longobject *) newlongobject(1L); 890 if (one == NULL || 891 (temp = (longobject *) long_sub(div, one)) == NULL) { 892 DECREF(mod); 893 DECREF(div); 894 XDECREF(one); 895 return -1; 896 } 897 DECREF(one); 898 DECREF(div); 899 div = temp; 900 } 901 *pdiv = div; 902 *pmod = mod; 903 return 0; 904} 905 906static object * 907long_div(v, w) 908 longobject *v; 909 longobject *w; 910{ 911 longobject *div, *mod; 912 if (l_divmod(v, w, &div, &mod) < 0) 913 return NULL; 914 DECREF(mod); 915 return (object *)div; 916} 917 918static object * 919long_mod(v, w) 920 longobject *v; 921 longobject *w; 922{ 923 longobject *div, *mod; 924 if (l_divmod(v, w, &div, &mod) < 0) 925 return NULL; 926 DECREF(div); 927 return (object *)mod; 928} 929 930static object * 931long_divmod(v, w) 932 longobject *v; 933 longobject *w; 934{ 935 object *z; 936 longobject *div, *mod; 937 if (l_divmod(v, w, &div, &mod) < 0) 938 return NULL; 939 z = newtupleobject(2); 940 if (z != NULL) { 941 settupleitem(z, 0, (object *) div); 942 settupleitem(z, 1, (object *) mod); 943 } 944 else { 945 DECREF(div); 946 DECREF(mod); 947 } 948 return z; 949} 950 951static object * 952long_pow(a, b, c) 953 longobject *a; 954 longobject *b; 955 longobject *c; 956{ 957 longobject *z, *div, *mod; 958 int size_b, i; 959 960 size_b = b->ob_size; 961 if (size_b < 0) { 962 err_setstr(ValueError, "long integer to the negative power"); 963 return NULL; 964 } 965 z = (longobject *)newlongobject(1L); 966 INCREF(a); 967 for (i = 0; i < size_b; ++i) { 968 digit bi = b->ob_digit[i]; 969 int j; 970 971 for (j = 0; j < SHIFT; ++j) { 972 longobject *temp; 973 974 if (bi & 1) { 975 temp = (longobject *)long_mul(z, a); 976 DECREF(z); 977 if ((object*)c!=None && temp!=NULL) { 978 l_divmod(temp, c, &div, &mod); 979 XDECREF(div); 980 DECREF(temp); 981 temp = mod; 982 } 983 z = temp; 984 if (z == NULL) 985 break; 986 } 987 bi >>= 1; 988 if (bi == 0 && i+1 == size_b) 989 break; 990 temp = (longobject *)long_mul(a, a); 991 DECREF(a); 992 if ((object*)c!=None && temp!=NULL) { 993 l_divmod(temp, c, &div, &mod); 994 XDECREF(div); 995 DECREF(temp); 996 temp = mod; 997 } 998 a = temp; 999 if (a == NULL) { 1000 DECREF(z); 1001 z = NULL; 1002 break; 1003 } 1004 } 1005 if (a == NULL) 1006 break; 1007 } 1008 XDECREF(a); 1009 if ((object*)c!=None && z!=NULL) { 1010 l_divmod(z, c, &div, &mod); 1011 XDECREF(div); 1012 DECREF(z); 1013 z=mod; 1014 } 1015 return (object *)z; 1016} 1017 1018static object * 1019long_invert(v) 1020 longobject *v; 1021{ 1022 /* Implement ~x as -(x+1) */ 1023 longobject *x; 1024 longobject *w; 1025 w = (longobject *)newlongobject(1L); 1026 if (w == NULL) 1027 return NULL; 1028 x = (longobject *) long_add(v, w); 1029 DECREF(w); 1030 if (x == NULL) 1031 return NULL; 1032 if (x->ob_size != 0) 1033 x->ob_size = -(x->ob_size); 1034 return (object *)x; 1035} 1036 1037static object * 1038long_pos(v) 1039 longobject *v; 1040{ 1041 INCREF(v); 1042 return (object *)v; 1043} 1044 1045static object * 1046long_neg(v) 1047 longobject *v; 1048{ 1049 longobject *z; 1050 int i, n; 1051 n = ABS(v->ob_size); 1052 if (n == 0) { 1053 /* -0 == 0 */ 1054 INCREF(v); 1055 return (object *) v; 1056 } 1057 z = alloclongobject(ABS(n)); 1058 if (z == NULL) 1059 return NULL; 1060 for (i = 0; i < n; i++) 1061 z->ob_digit[i] = v->ob_digit[i]; 1062 z->ob_size = -(v->ob_size); 1063 return (object *)z; 1064} 1065 1066static object * 1067long_abs(v) 1068 longobject *v; 1069{ 1070 if (v->ob_size < 0) 1071 return long_neg(v); 1072 else { 1073 INCREF(v); 1074 return (object *)v; 1075 } 1076} 1077 1078static int 1079long_nonzero(v) 1080 longobject *v; 1081{ 1082 return ABS(v->ob_size) != 0; 1083} 1084 1085static object * 1086long_rshift(a, b) 1087 longobject *a; 1088 longobject *b; 1089{ 1090 longobject *z; 1091 long shiftby; 1092 int newsize, wordshift, loshift, hishift, i, j; 1093 digit lomask, himask; 1094 1095 if (a->ob_size < 0) { 1096 /* Right shifting negative numbers is harder */ 1097 longobject *a1, *a2, *a3; 1098 a1 = (longobject *) long_invert(a); 1099 if (a1 == NULL) return NULL; 1100 a2 = (longobject *) long_rshift(a1, b); 1101 DECREF(a1); 1102 if (a2 == NULL) return NULL; 1103 a3 = (longobject *) long_invert(a2); 1104 DECREF(a2); 1105 return (object *) a3; 1106 } 1107 1108 shiftby = getlongvalue((object *)b); 1109 if (shiftby == -1L && err_occurred()) 1110 return NULL; 1111 if (shiftby < 0) { 1112 err_setstr(ValueError, "negative shift count"); 1113 return NULL; 1114 } 1115 wordshift = shiftby / SHIFT; 1116 newsize = ABS(a->ob_size) - wordshift; 1117 if (newsize <= 0) { 1118 z = alloclongobject(0); 1119 return (object *)z; 1120 } 1121 loshift = shiftby % SHIFT; 1122 hishift = SHIFT - loshift; 1123 lomask = ((digit)1 << hishift) - 1; 1124 himask = MASK ^ lomask; 1125 z = alloclongobject(newsize); 1126 if (z == NULL) 1127 return NULL; 1128 if (a->ob_size < 0) 1129 z->ob_size = -(z->ob_size); 1130 for (i = 0, j = wordshift; i < newsize; i++, j++) { 1131 z->ob_digit[i] = (a->ob_digit[j] >> loshift) & lomask; 1132 if (i+1 < newsize) 1133 z->ob_digit[i] |= 1134 (a->ob_digit[j+1] << hishift) & himask; 1135 } 1136 return (object *) long_normalize(z); 1137} 1138 1139static object * 1140long_lshift(a, b) 1141 longobject *a; 1142 longobject *b; 1143{ 1144 longobject *z; 1145 long shiftby; 1146 int newsize, wordshift, loshift, hishift, i, j; 1147 digit lomask, himask; 1148 1149 shiftby = getlongvalue((object *)b); 1150 if (shiftby == -1L && err_occurred()) 1151 return NULL; 1152 if (shiftby < 0) { 1153 err_setstr(ValueError, "negative shift count"); 1154 return NULL; 1155 } 1156 if (shiftby > MASK) { 1157 err_setstr(ValueError, "outrageous left shift count"); 1158 return NULL; 1159 } 1160 if (shiftby % SHIFT == 0) { 1161 wordshift = shiftby / SHIFT; 1162 loshift = 0; 1163 hishift = SHIFT; 1164 newsize = ABS(a->ob_size) + wordshift; 1165 lomask = MASK; 1166 himask = 0; 1167 } 1168 else { 1169 wordshift = shiftby / SHIFT + 1; 1170 loshift = SHIFT - shiftby%SHIFT; 1171 hishift = shiftby % SHIFT; 1172 newsize = ABS(a->ob_size) + wordshift; 1173 lomask = ((digit)1 << hishift) - 1; 1174 himask = MASK ^ lomask; 1175 } 1176 z = alloclongobject(newsize); 1177 if (z == NULL) 1178 return NULL; 1179 if (a->ob_size < 0) 1180 z->ob_size = -(z->ob_size); 1181 for (i = 0; i < wordshift; i++) 1182 z->ob_digit[i] = 0; 1183 for (i = wordshift, j = 0; i < newsize; i++, j++) { 1184 if (i > 0) 1185 z->ob_digit[i-1] |= 1186 (a->ob_digit[j] << hishift) & himask; 1187 z->ob_digit[i] = 1188 (a->ob_digit[j] >> loshift) & lomask; 1189 } 1190 return (object *) long_normalize(z); 1191} 1192 1193 1194/* Bitwise and/xor/or operations */ 1195 1196#define MAX(x, y) ((x) < (y) ? (y) : (x)) 1197#define MIN(x, y) ((x) > (y) ? (y) : (x)) 1198 1199static object *long_bitwise PROTO((longobject *, int, longobject *)); 1200static object * 1201long_bitwise(a, op, b) 1202 longobject *a; 1203 int op; /* '&', '|', '^' */ 1204 longobject *b; 1205{ 1206 digit maska, maskb; /* 0 or MASK */ 1207 int negz; 1208 int size_a, size_b, size_z; 1209 longobject *z; 1210 int i; 1211 digit diga, digb; 1212 object *v; 1213 1214 if (a->ob_size < 0) { 1215 a = (longobject *) long_invert(a); 1216 maska = MASK; 1217 } 1218 else { 1219 INCREF(a); 1220 maska = 0; 1221 } 1222 if (b->ob_size < 0) { 1223 b = (longobject *) long_invert(b); 1224 maskb = MASK; 1225 } 1226 else { 1227 INCREF(b); 1228 maskb = 0; 1229 } 1230 1231 size_a = a->ob_size; 1232 size_b = b->ob_size; 1233 size_z = MAX(size_a, size_b); 1234 z = alloclongobject(size_z); 1235 if (a == NULL || b == NULL || z == NULL) { 1236 XDECREF(a); 1237 XDECREF(b); 1238 XDECREF(z); 1239 return NULL; 1240 } 1241 1242 negz = 0; 1243 switch (op) { 1244 case '^': 1245 if (maska != maskb) { 1246 maska ^= MASK; 1247 negz = -1; 1248 } 1249 break; 1250 case '&': 1251 if (maska && maskb) { 1252 op = '|'; 1253 maska ^= MASK; 1254 maskb ^= MASK; 1255 negz = -1; 1256 } 1257 break; 1258 case '|': 1259 if (maska || maskb) { 1260 op = '&'; 1261 maska ^= MASK; 1262 maskb ^= MASK; 1263 negz = -1; 1264 } 1265 break; 1266 } 1267 1268 for (i = 0; i < size_z; ++i) { 1269 diga = (i < size_a ? a->ob_digit[i] : 0) ^ maska; 1270 digb = (i < size_b ? b->ob_digit[i] : 0) ^ maskb; 1271 switch (op) { 1272 case '&': z->ob_digit[i] = diga & digb; break; 1273 case '|': z->ob_digit[i] = diga | digb; break; 1274 case '^': z->ob_digit[i] = diga ^ digb; break; 1275 } 1276 } 1277 1278 DECREF(a); 1279 DECREF(b); 1280 z = long_normalize(z); 1281 if (negz == 0) 1282 return (object *) z; 1283 v = long_invert(z); 1284 DECREF(z); 1285 return v; 1286} 1287 1288static object * 1289long_and(a, b) 1290 longobject *a; 1291 longobject *b; 1292{ 1293 return long_bitwise(a, '&', b); 1294} 1295 1296static object * 1297long_xor(a, b) 1298 longobject *a; 1299 longobject *b; 1300{ 1301 return long_bitwise(a, '^', b); 1302} 1303 1304static object * 1305long_or(a, b) 1306 longobject *a; 1307 longobject *b; 1308{ 1309 return long_bitwise(a, '|', b); 1310} 1311 1312static int 1313long_coerce(pv, pw) 1314 object **pv; 1315 object **pw; 1316{ 1317 if (is_intobject(*pw)) { 1318 *pw = newlongobject(getintvalue(*pw)); 1319 INCREF(*pv); 1320 return 0; 1321 } 1322 return 1; /* Can't do it */ 1323} 1324 1325static object * 1326long_int(v) 1327 object *v; 1328{ 1329 long x; 1330 x = getlongvalue(v); 1331 if (err_occurred()) 1332 return NULL; 1333 return newintobject(x); 1334} 1335 1336static object * 1337long_long(v) 1338 object *v; 1339{ 1340 INCREF(v); 1341 return v; 1342} 1343 1344static object * 1345long_float(v) 1346 object *v; 1347{ 1348 return newfloatobject(dgetlongvalue(v)); 1349} 1350 1351static object * 1352long_oct(v) 1353 object *v; 1354{ 1355 return long_format(v, 8); 1356} 1357 1358static object * 1359long_hex(v) 1360 object *v; 1361{ 1362 return long_format(v, 16); 1363} 1364 1365 1366#define UF (unaryfunc) 1367#define BF (binaryfunc) 1368#define TF (ternaryfunc) 1369#define IF (inquiry) 1370 1371static number_methods long_as_number = { 1372 BF long_add, /*nb_add*/ 1373 BF long_sub, /*nb_subtract*/ 1374 BF long_mul, /*nb_multiply*/ 1375 BF long_div, /*nb_divide*/ 1376 BF long_mod, /*nb_remainder*/ 1377 BF long_divmod, /*nb_divmod*/ 1378 TF long_pow, /*nb_power*/ 1379 UF long_neg, /*nb_negative*/ 1380 UF long_pos, /*tp_positive*/ 1381 UF long_abs, /*tp_absolute*/ 1382 IF long_nonzero,/*tp_nonzero*/ 1383 UF long_invert, /*nb_invert*/ 1384 BF long_lshift, /*nb_lshift*/ 1385 BF long_rshift, /*nb_rshift*/ 1386 BF long_and, /*nb_and*/ 1387 BF long_xor, /*nb_xor*/ 1388 BF long_or, /*nb_or*/ 1389 (int (*) FPROTO((object **, object **))) 1390 (coercion)long_coerce, /*nb_coerce*/ 1391 UF long_int, /*nb_int*/ 1392 UF long_long, /*nb_long*/ 1393 UF long_float, /*nb_float*/ 1394 UF long_oct, /*nb_oct*/ 1395 UF long_hex, /*nb_hex*/ 1396}; 1397 1398typeobject Longtype = { 1399 OB_HEAD_INIT(&Typetype) 1400 0, 1401 "long int", 1402 sizeof(longobject) - sizeof(digit), 1403 sizeof(digit), 1404 (destructor)long_dealloc, /*tp_dealloc*/ 1405 0, /*tp_print*/ 1406 0, /*tp_getattr*/ 1407 0, /*tp_setattr*/ 1408 (int (*) FPROTO((object *, object *))) 1409 (cmpfunc)long_compare, /*tp_compare*/ 1410 (reprfunc)long_repr, /*tp_repr*/ 1411 &long_as_number,/*tp_as_number*/ 1412 0, /*tp_as_sequence*/ 1413 0, /*tp_as_mapping*/ 1414 (long (*) FPROTO((object *))) 1415 (hashfunc)long_hash, /*tp_hash*/ 1416}; 1417