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