Objects/intobject.c

   1 /***********************************************************
   2 Copyright 1991-1995 by Stichting Mathematisch Centrum, Amsterdam,
   3 The Netherlands.
   4
   5                         All Rights Reserved
   6
   7 Permission to use, copy, modify, and distribute this software and its
   8 documentation for any purpose and without fee is hereby granted,
   9 provided that the above copyright notice appear in all copies and that
  10 both that copyright notice and this permission notice appear in
  11 supporting documentation, and that the names of Stichting Mathematisch
  12 Centrum or CWI not be used in advertising or publicity pertaining to
  13 distribution of the software without specific, written prior permission.
  14
  15 STICHTING MATHEMATISCH CENTRUM DISCLAIMS ALL WARRANTIES WITH REGARD TO
  16 THIS SOFTWARE, INCLUDING ALL IMPLIED WARRANTIES OF MERCHANTABILITY AND
  17 FITNESS, IN NO EVENT SHALL STICHTING MATHEMATISCH CENTRUM BE LIABLE
  18 FOR ANY SPECIAL, INDIRECT OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES
  19 WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN
  20 ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT
  21 OF OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
  22
  23 ******************************************************************/
  24
  25 /* Integer object implementation */
  26
  27 #include "allobjects.h"
  28 #include "modsupport.h"
  29
  30 #ifdef HAVE_LIMITS_H
  31 #include <limits.h>
  32 #endif
  33
  34 #ifndef LONG_MAX
  35 #define LONG_MAX 0X7FFFFFFFL
  36 #endif
  37
  38 #ifndef LONG_MIN
  39 #define LONG_MIN (-LONG_MAX-1)
  40 #endif
  41
  42 #ifndef CHAR_BIT
  43 #define CHAR_BIT 8
  44 #endif
  45
  46 #ifndef LONG_BIT
  47 #define LONG_BIT (CHAR_BIT * sizeof(long))
  48 #endif
  49
  50 long
  51 getmaxint()
  52 {
  53         return LONG_MAX;        /* To initialize sys.maxint */
  54 }
  55
  56 /* Standard Booleans */
  57
  58 intobject FalseObject = {
  59         OB_HEAD_INIT(&Inttype)
  60         0
  61 };
  62
  63 intobject TrueObject = {
  64         OB_HEAD_INIT(&Inttype)
  65         1
  66 };
  67
  68 static object *
  69 err_ovf(msg)
  70         char *msg;
  71 {
  72         err_setstr(OverflowError, msg);
  73         return NULL;
  74 }
  75
  76 /* Integers are quite normal objects, to make object handling uniform.
  77    (Using odd pointers to represent integers would save much space
  78    but require extra checks for this special case throughout the code.)
  79    Since, a typical Python program spends much of its time allocating
  80    and deallocating integers, these operations should be very fast.
  81    Therefore we use a dedicated allocation scheme with a much lower
  82    overhead (in space and time) than straight malloc(): a simple
  83    dedicated free list, filled when necessary with memory from malloc().
  84 */
  85
  86 #define BLOCK_SIZE      1000    /* 1K less typical malloc overhead */
  87 #define N_INTOBJECTS    (BLOCK_SIZE / sizeof(intobject))
  88
  89 static intobject *
  90 fill_free_list()
  91 {
  92         intobject *p, *q;
  93         p = NEW(intobject, N_INTOBJECTS);
  94         if (p == NULL)
  95                 return (intobject *)err_nomem();
  96         q = p + N_INTOBJECTS;
  97         while (--q > p)
  98                 *(intobject **)q = q-1;
  99         *(intobject **)q = NULL;
 100         return p + N_INTOBJECTS - 1;
 101 }
 102
 103 static intobject *free_list = NULL;
 104 #ifndef NSMALLPOSINTS
 105 #define NSMALLPOSINTS           100
 106 #endif
 107 #ifndef NSMALLNEGINTS
 108 #define NSMALLNEGINTS           1
 109 #endif
 110 #if NSMALLNEGINTS + NSMALLPOSINTS > 0
 111 /* References to small integers are saved in this array so that they
 112    can be shared.
 113    The integers that are saved are those in the range
 114    -NSMALLNEGINTS (inclusive) to NSMALLPOSINTS (not inclusive).
 115 */
 116 static intobject *small_ints[NSMALLNEGINTS + NSMALLPOSINTS];
 117 #endif
 118 #ifdef COUNT_ALLOCS
 119 int quick_int_allocs, quick_neg_int_allocs;
 120 #endif
 121
 122 object *
 123 newintobject(ival)
 124         long ival;
 125 {
 126         register intobject *v;
 127 #if NSMALLNEGINTS + NSMALLPOSINTS > 0
 128         if (-NSMALLNEGINTS <= ival && ival < NSMALLPOSINTS &&
 129             (v = small_ints[ival + NSMALLNEGINTS]) != NULL) {
 130                 INCREF(v);
 131 #ifdef COUNT_ALLOCS
 132                 if (ival >= 0)
 133                         quick_int_allocs++;
 134                 else
 135                         quick_neg_int_allocs++;
 136 #endif
 137                 return (object *) v;
 138         }
 139 #endif
 140         if (free_list == NULL) {
 141                 if ((free_list = fill_free_list()) == NULL)
 142                         return NULL;
 143         }
 144         v = free_list;
 145         free_list = *(intobject **)free_list;
 146         v->ob_type = &Inttype;
 147         v->ob_ival = ival;
 148         NEWREF(v);
 149 #if NSMALLNEGINTS + NSMALLPOSINTS > 0
 150         if (-NSMALLNEGINTS <= ival && ival < NSMALLPOSINTS) {
 151                 /* save this one for a following allocation */
 152                 INCREF(v);
 153                 small_ints[ival + NSMALLNEGINTS] = v;
 154         }
 155 #endif
 156         return (object *) v;
 157 }
 158
 159 static void
 160 int_dealloc(v)
 161         intobject *v;
 162 {
 163         *(intobject **)v = free_list;
 164         free_list = v;
 165 }
 166
 167 long
 168 getintvalue(op)
 169         register object *op;
 170 {
 171         number_methods *nb;
 172         intobject *io;
 173         long val;
 174
 175         if (op && is_intobject(op))
 176                 return GETINTVALUE((intobject*) op);
 177
 178         if (op == NULL || (nb = op->ob_type->tp_as_number) == NULL ||
 179             nb->nb_int == NULL) {
 180                 err_badarg();
 181                 return -1;
 182         }
 183
 184         io = (intobject*) (*nb->nb_int) (op);
 185         if (io == NULL)
 186                 return -1;
 187         if (!is_intobject(io)) {
 188                 err_setstr(TypeError, "nb_int should return int object");
 189                 return -1;
 190         }
 191
 192         val = GETINTVALUE(io);
 193         DECREF(io);
 194
 195         return val;
 196 }
 197
 198 /* Methods */
 199
 200 /* ARGSUSED */
 201 static int
 202 int_print(v, fp, flags)
 203         intobject *v;
 204         FILE *fp;
 205         int flags; /* Not used but required by interface */
 206 {
 207         fprintf(fp, "%ld", v->ob_ival);
 208         return 0;
 209 }
 210
 211 static object *
 212 int_repr(v)
 213         intobject *v;
 214 {
 215         char buf[20];
 216         sprintf(buf, "%ld", v->ob_ival);
 217         return newstringobject(buf);
 218 }
 219
 220 static int
 221 int_compare(v, w)
 222         intobject *v, *w;
 223 {
 224         register long i = v->ob_ival;
 225         register long j = w->ob_ival;
 226         return (i < j) ? -1 : (i > j) ? 1 : 0;
 227 }
 228
 229 static long
 230 int_hash(v)
 231         intobject *v;
 232 {
 233         long x = v -> ob_ival;
 234         if (x == -1)
 235                 x = -2;
 236         return x;
 237 }
 238
 239 static object *
 240 int_add(v, w)
 241         intobject *v;
 242         intobject *w;
 243 {
 244         register long a, b, x;
 245         a = v->ob_ival;
 246         b = w->ob_ival;
 247         x = a + b;
 248         if ((x^a) < 0 && (x^b) < 0)
 249                 return err_ovf("integer addition");
 250         return newintobject(x);
 251 }
 252
 253 static object *
 254 int_sub(v, w)
 255         intobject *v;
 256         intobject *w;
 257 {
 258         register long a, b, x;
 259         a = v->ob_ival;
 260         b = w->ob_ival;
 261         x = a - b;
 262         if ((x^a) < 0 && (x^~b) < 0)
 263                 return err_ovf("integer subtraction");
 264         return newintobject(x);
 265 }
 266
 267 /*
 268 Integer overflow checking used to be done using a double, but on 64
 269 bit machines (where both long and double are 64 bit) this fails
 270 because the double doesn't have enouvg precision.  John Tromp suggests
 271 the following algorithm:
 272
 273 Suppose again we normalize a and b to be nonnegative.
 274 Let ah and al (bh and bl) be the high and low 32 bits of a (b, resp.).
 275 Now we test ah and bh against zero and get essentially 3 possible outcomes.
 276
 277 1) both ah and bh > 0 : then report overflow
 278
 279 2) both ah and bh = 0 : then compute a*b and report overflow if it comes out
 280                         negative
 281
 282 3) ah > 0 and bh = 0  : compute ah*bl and report overflow if it's >= 2^31
 283                         compute al*bl and report overflow if it's negative
 284                         add (ah*bl)<<32 to al*bl and report overflow if
 285                         it's negative
 286
 287 In case of no overflow the result is then negated if necessary.
 288
 289 The majority of cases will be 2), in which case this method is the same as
 290 what I suggested before. If multiplication is expensive enough, then the
 291 other method is faster on case 3), but also more work to program, so I
 292 guess the above is the preferred solution.
 293
 294 */
 295
 296 static object *
 297 int_mul(v, w)
 298         intobject *v;
 299         intobject *w;
 300 {
 301         long a, b, ah, bh, x, y;
 302         int s = 1;
 303
 304         a = v->ob_ival;
 305         b = w->ob_ival;
 306         ah = a >> (LONG_BIT/2);
 307         bh = b >> (LONG_BIT/2);
 308
 309         /* Quick test for common case: two small positive ints */
 310
 311         if (ah == 0 && bh == 0) {
 312                 x = a*b;
 313                 if (x < 0)
 314                         goto bad;
 315                 return newintobject(x);
 316         }
 317
 318         /* Arrange that a >= b >= 0 */
 319
 320         if (a < 0) {
 321                 a = -a;
 322                 if (a < 0) {
 323                         /* Largest negative */
 324                         if (b == 0 || b == 1) {
 325                                 x = a*b;
 326                                 goto ok;
 327                         }
 328                         else
 329                                 goto bad;
 330                 }
 331                 s = -s;
 332                 ah = a >> (LONG_BIT/2);
 333         }
 334         if (b < 0) {
 335                 b = -b;
 336                 if (b < 0) {
 337                         /* Largest negative */
 338                         if (a == 0 || a == 1 && s == 1) {
 339                                 x = a*b;
 340                                 goto ok;
 341                         }
 342                         else
 343                                 goto bad;
 344                 }
 345                 s = -s;
 346                 bh = b >> (LONG_BIT/2);
 347         }
 348
 349         /* 1) both ah and bh > 0 : then report overflow */
 350
 351         if (ah != 0 && bh != 0)
 352                 goto bad;
 353
 354         /* 2) both ah and bh = 0 : then compute a*b and report
 355                                    overflow if it comes out negative */
 356
 357         if (ah == 0 && bh == 0) {
 358                 x = a*b;
 359                 if (x < 0)
 360                         goto bad;
 361                 return newintobject(x*s);
 362         }
 363
 364         if (a < b) {
 365                 /* Swap */
 366                 x = a;
 367                 a = b;
 368                 b = x;
 369                 ah = bh;
 370                 /* bh not used beyond this point */
 371         }
 372
 373         /* 3) ah > 0 and bh = 0  : compute ah*bl and report overflow if
 374                                    it's >= 2^31
 375                         compute al*bl and report overflow if it's negative
 376                         add (ah*bl)<<32 to al*bl and report overflow if
 377                         it's negative
 378                         (NB b == bl in this case, and we make a = al) */
 379
 380         y = ah*b;
 381         if (y >= (1L << (LONG_BIT/2)))
 382                 goto bad;
 383         a &= (1L << (LONG_BIT/2)) - 1;
 384         x = a*b;
 385         if (x < 0)
 386                 goto bad;
 387         x += y << LONG_BIT/2;
 388         if (x < 0)
 389                 goto bad;
 390  ok:
 391         return newintobject(x * s);
 392
 393  bad:
 394         return err_ovf("integer multiplication");
 395 }
 396
 397 static int
 398 i_divmod(x, y, p_xdivy, p_xmody)
 399         register intobject *x, *y;
 400         long *p_xdivy, *p_xmody;
 401 {
 402         long xi = x->ob_ival;
 403         long yi = y->ob_ival;
 404         long xdivy, xmody;
 405
 406         if (yi == 0) {
 407                 err_setstr(ZeroDivisionError, "integer division or modulo");
 408                 return -1;
 409         }
 410         if (yi < 0) {
 411                 if (xi < 0)
 412                         xdivy = -xi / -yi;
 413                 else
 414                         xdivy = - (xi / -yi);
 415         }
 416         else {
 417                 if (xi < 0)
 418                         xdivy = - (-xi / yi);
 419                 else
 420                         xdivy = xi / yi;
 421         }
 422         xmody = xi - xdivy*yi;
 423         if (xmody < 0 && yi > 0 || xmody > 0 && yi < 0) {
 424                 xmody += yi;
 425                 xdivy -= 1;
 426         }
 427         *p_xdivy = xdivy;
 428         *p_xmody = xmody;
 429         return 0;
 430 }
 431
 432 static object *
 433 int_div(x, y)
 434         intobject *x;
 435         intobject *y;
 436 {
 437         long d, m;
 438         if (i_divmod(x, y, &d, &m) < 0)
 439                 return NULL;
 440         return newintobject(d);
 441 }
 442
 443 static object *
 444 int_mod(x, y)
 445         intobject *x;
 446         intobject *y;
 447 {
 448         long d, m;
 449         if (i_divmod(x, y, &d, &m) < 0)
 450                 return NULL;
 451         return newintobject(m);
 452 }
 453
 454 static object *
 455 int_divmod(x, y)
 456         intobject *x;
 457         intobject *y;
 458 {
 459         long d, m;
 460         if (i_divmod(x, y, &d, &m) < 0)
 461                 return NULL;
 462         return mkvalue("(ll)", d, m);
 463 }
 464
 465 static object *
 466 int_pow(v, w, z)
 467         intobject *v;
 468         intobject *w;
 469         intobject *z;
 470 {
 471 #if 1
 472         register long iv, iw, iz, ix, temp, prev;
 473         int zset = 0;
 474         iv = v->ob_ival;
 475         iw = w->ob_ival;
 476         if (iw < 0) {
 477                 err_setstr(ValueError, "integer to the negative power");
 478                 return NULL;
 479         }
 480         if ((object *)z != None) {
 481                 iz = z->ob_ival;
 482                 zset = 1;
 483         }
 484         /*
 485          * XXX: The original exponentiation code stopped looping
 486          * when temp hit zero; this code will continue onwards
 487          * unnecessarily, but at least it won't cause any errors.
 488          * Hopefully the speed improvement from the fast exponentiation
 489          * will compensate for the slight inefficiency.
 490          * XXX: Better handling of overflows is desperately needed.
 491          */
 492         temp = iv;
 493         ix = 1;
 494         while (iw > 0) {
 495                 prev = ix;      /* Save value for overflow check */
 496                 if (iw & 1) {
 497                         ix = ix*temp;
 498                         if (temp == 0)
 499                                 break; /* Avoid ix / 0 */
 500                         if (ix / temp != prev)
 501                                 return err_ovf("integer pow()");
 502                 }
 503                 iw >>= 1;       /* Shift exponent down by 1 bit */
 504                 if (iw==0) break;
 505                 prev = temp;
 506                 temp *= temp;   /* Square the value of temp */
 507                 if (prev!=0 && temp/prev!=prev)
 508                         return err_ovf("integer pow()");
 509                 if (zset) {
 510                         /* If we did a multiplication, perform a modulo */
 511                         ix = ix % iz;
 512                         temp = temp % iz;
 513                 }
 514         }
 515         if (zset) {
 516                 object *t1, *t2;
 517                 long int div, mod;
 518                 t1=newintobject(ix);
 519                 t2=newintobject(iz);
 520                 if (t1==NULL || t2==NULL ||
 521                         i_divmod((intobject *)t1, (intobject *)t2, &div, &mod)<0) {
 522                         XDECREF(t1);
 523                         XDECREF(t2);
 524                         return(NULL);
 525                 }
 526                 DECREF(t1);
 527                 DECREF(t2);
 528                 ix=mod;
 529         }
 530         return newintobject(ix);
 531 #else
 532         register long iv, iw, ix;
 533         iv = v->ob_ival;
 534         iw = w->ob_ival;
 535         if (iw < 0) {
 536                 err_setstr(ValueError, "integer to the negative power");
 537                 return NULL;
 538         }
 539         if ((object *)z != None) {
 540                 err_setstr(TypeError, "pow(int, int, int) not yet supported");
 541                 return NULL;
 542         }
 543         ix = 1;
 544         while (--iw >= 0) {
 545                 long prev = ix;
 546                 ix = ix * iv;
 547                 if (iv == 0)
 548                         break; /* 0 to some power -- avoid ix / 0 */
 549                 if (ix / iv != prev)
 550                         return err_ovf("integer pow()");
 551         }
 552         return newintobject(ix);
 553 #endif
 554 }
 555
 556 static object *
 557 int_neg(v)
 558         intobject *v;
 559 {
 560         register long a, x;
 561         a = v->ob_ival;
 562         x = -a;
 563         if (a < 0 && x < 0)
 564                 return err_ovf("integer negation");
 565         return newintobject(x);
 566 }
 567
 568 static object *
 569 int_pos(v)
 570         intobject *v;
 571 {
 572         INCREF(v);
 573         return (object *)v;
 574 }
 575
 576 static object *
 577 int_abs(v)
 578         intobject *v;
 579 {
 580         if (v->ob_ival >= 0)
 581                 return int_pos(v);
 582         else
 583                 return int_neg(v);
 584 }
 585
 586 static int
 587 int_nonzero(v)
 588         intobject *v;
 589 {
 590         return v->ob_ival != 0;
 591 }
 592
 593 static object *
 594 int_invert(v)
 595         intobject *v;
 596 {
 597         return newintobject(~v->ob_ival);
 598 }
 599
 600 static object *
 601 int_lshift(v, w)
 602         intobject *v;
 603         intobject *w;
 604 {
 605         register long a, b;
 606         a = v->ob_ival;
 607         b = w->ob_ival;
 608         if (b < 0) {
 609                 err_setstr(ValueError, "negative shift count");
 610                 return NULL;
 611         }
 612         if (a == 0 || b == 0) {
 613                 INCREF(v);
 614                 return (object *) v;
 615         }
 616         if (b >= LONG_BIT) {
 617                 return newintobject(0L);
 618         }
 619         a = (unsigned long)a << b;
 620         return newintobject(a);
 621 }
 622
 623 static object *
 624 int_rshift(v, w)
 625         intobject *v;
 626         intobject *w;
 627 {
 628         register long a, b;
 629         a = v->ob_ival;
 630         b = w->ob_ival;
 631         if (b < 0) {
 632                 err_setstr(ValueError, "negative shift count");
 633                 return NULL;
 634         }
 635         if (a == 0 || b == 0) {
 636                 INCREF(v);
 637                 return (object *) v;
 638         }
 639         if (b >= LONG_BIT) {
 640                 if (a < 0)
 641                         a = -1;
 642                 else
 643                         a = 0;
 644         }
 645         else {
 646                 if (a < 0)
 647                         a = ~( ~(unsigned long)a >> b );
 648                 else
 649                         a = (unsigned long)a >> b;
 650         }
 651         return newintobject(a);
 652 }
 653
 654 static object *
 655 int_and(v, w)
 656         intobject *v;
 657         intobject *w;
 658 {
 659         register long a, b;
 660         a = v->ob_ival;
 661         b = w->ob_ival;
 662         return newintobject(a & b);
 663 }
 664
 665 static object *
 666 int_xor(v, w)
 667         intobject *v;
 668         intobject *w;
 669 {
 670         register long a, b;
 671         a = v->ob_ival;
 672         b = w->ob_ival;
 673         return newintobject(a ^ b);
 674 }
 675
 676 static object *
 677 int_or(v, w)
 678         intobject *v;
 679         intobject *w;
 680 {
 681         register long a, b;
 682         a = v->ob_ival;
 683         b = w->ob_ival;
 684         return newintobject(a | b);
 685 }
 686
 687 static object *
 688 int_int(v)
 689         intobject *v;
 690 {
 691         INCREF(v);
 692         return (object *)v;
 693 }
 694
 695 static object *
 696 int_long(v)
 697         intobject *v;
 698 {
 699         return newlongobject((v -> ob_ival));
 700 }
 701
 702 static object *
 703 int_float(v)
 704         intobject *v;
 705 {
 706         return newfloatobject((double)(v -> ob_ival));
 707 }
 708
 709 static object *
 710 int_oct(v)
 711         intobject *v;
 712 {
 713         char buf[20];
 714         long x = v -> ob_ival;
 715         if (x == 0)
 716                 strcpy(buf, "0");
 717         else if (x > 0)
 718                 sprintf(buf, "0%lo", x);
 719         else
 720                 sprintf(buf, "-0%lo", -x);
 721         return newstringobject(buf);
 722 }
 723
 724 static object *
 725 int_hex(v)
 726         intobject *v;
 727 {
 728         char buf[20];
 729         long x = v -> ob_ival;
 730         if (x >= 0)
 731                 sprintf(buf, "0x%lx", x);
 732         else
 733                 sprintf(buf, "-0x%lx", -x);
 734         return newstringobject(buf);
 735 }
 736
 737 static number_methods int_as_number = {
 738         (binaryfunc)int_add, /*nb_add*/
 739         (binaryfunc)int_sub, /*nb_subtract*/
 740         (binaryfunc)int_mul, /*nb_multiply*/
 741         (binaryfunc)int_div, /*nb_divide*/
 742         (binaryfunc)int_mod, /*nb_remainder*/
 743         (binaryfunc)int_divmod, /*nb_divmod*/
 744         (ternaryfunc)int_pow, /*nb_power*/
 745         (unaryfunc)int_neg, /*nb_negative*/
 746         (unaryfunc)int_pos, /*nb_positive*/
 747         (unaryfunc)int_abs, /*nb_absolute*/
 748         (inquiry)int_nonzero, /*nb_nonzero*/
 749         (unaryfunc)int_invert, /*nb_invert*/
 750         (binaryfunc)int_lshift, /*nb_lshift*/
 751         (binaryfunc)int_rshift, /*nb_rshift*/
 752         (binaryfunc)int_and, /*nb_and*/
 753         (binaryfunc)int_xor, /*nb_xor*/
 754         (binaryfunc)int_or, /*nb_or*/
 755         0,              /*nb_coerce*/
 756         (unaryfunc)int_int, /*nb_int*/
 757         (unaryfunc)int_long, /*nb_long*/
 758         (unaryfunc)int_float, /*nb_float*/
 759         (unaryfunc)int_oct, /*nb_oct*/
 760         (unaryfunc)int_hex, /*nb_hex*/
 761 };
 762
 763 typeobject Inttype = {
 764         OB_HEAD_INIT(&Typetype)
 765         0,
 766         "int",
 767         sizeof(intobject),
 768         0,
 769         (destructor)int_dealloc, /*tp_dealloc*/
 770         (printfunc)int_print, /*tp_print*/
 771         0,              /*tp_getattr*/
 772         0,              /*tp_setattr*/
 773         (cmpfunc)int_compare, /*tp_compare*/
 774         (reprfunc)int_repr, /*tp_repr*/
 775         &int_as_number, /*tp_as_number*/
 776         0,              /*tp_as_sequence*/
 777         0,              /*tp_as_mapping*/
 778         (hashfunc)int_hash, /*tp_hash*/
 779 };