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 or Corporation for National Research Initiatives or
  13 CNRI not be used in advertising or publicity pertaining to
  14 distribution of the software without specific, written prior
  15 permission.
  16
  17 While CWI is the initial source for this software, a modified version
  18 is made available by the Corporation for National Research Initiatives
  19 (CNRI) at the Internet address ftp://ftp.python.org.
  20
  21 STICHTING MATHEMATISCH CENTRUM AND CNRI DISCLAIM ALL WARRANTIES WITH
  22 REGARD TO THIS SOFTWARE, INCLUDING ALL IMPLIED WARRANTIES OF
  23 MERCHANTABILITY AND FITNESS, IN NO EVENT SHALL STICHTING MATHEMATISCH
  24 CENTRUM OR CNRI BE LIABLE FOR ANY SPECIAL, INDIRECT OR CONSEQUENTIAL
  25 DAMAGES OR ANY DAMAGES WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR
  26 PROFITS, WHETHER IN AN ACTION OF CONTRACT, NEGLIGENCE OR OTHER
  27 TORTIOUS ACTION, ARISING OUT OF OR IN CONNECTION WITH THE USE OR
  28 PERFORMANCE OF THIS SOFTWARE.
  29
  30 ******************************************************************/
  31
  32 /* Integer object implementation */
  33
  34 #include "Python.h"
  35 #include <ctype.h>
  36
  37 #ifdef HAVE_LIMITS_H
  38 #include <limits.h>
  39 #endif
  40
  41 #ifndef LONG_MAX
  42 #define LONG_MAX 0X7FFFFFFFL
  43 #endif
  44
  45 #ifndef LONG_MIN
  46 #define LONG_MIN (-LONG_MAX-1)
  47 #endif
  48
  49 #ifndef CHAR_BIT
  50 #define CHAR_BIT 8
  51 #endif
  52
  53 #ifndef LONG_BIT
  54 #define LONG_BIT (CHAR_BIT * sizeof(long))
  55 #endif
  56
  57 long
  58 PyInt_GetMax()
  59 {
  60         return LONG_MAX;        /* To initialize sys.maxint */
  61 }
  62
  63 /* Standard Booleans */
  64
  65 PyIntObject _Py_ZeroStruct = {
  66         PyObject_HEAD_INIT(&PyInt_Type)
  67         0
  68 };
  69
  70 PyIntObject _Py_TrueStruct = {
  71         PyObject_HEAD_INIT(&PyInt_Type)
  72         1
  73 };
  74
  75 static PyObject *
  76 err_ovf(msg)
  77         char *msg;
  78 {
  79         PyErr_SetString(PyExc_OverflowError, msg);
  80         return NULL;
  81 }
  82
  83 /* Integers are quite normal objects, to make object handling uniform.
  84    (Using odd pointers to represent integers would save much space
  85    but require extra checks for this special case throughout the code.)
  86    Since, a typical Python program spends much of its time allocating
  87    and deallocating integers, these operations should be very fast.
  88    Therefore we use a dedicated allocation scheme with a much lower
  89    overhead (in space and time) than straight malloc(): a simple
  90    dedicated free list, filled when necessary with memory from malloc().
  91 */
  92
  93 #define BLOCK_SIZE      1000    /* 1K less typical malloc overhead */
  94 #define BHEAD_SIZE      8       /* Enough for a 64-bit pointer */
  95 #define N_INTOBJECTS    ((BLOCK_SIZE - BHEAD_SIZE) / sizeof(PyIntObject))
  96
  97 #define PyMem_MALLOC    malloc
  98 #define PyMem_FREE      free
  99
 100 struct _intblock {
 101         struct _intblock *next;
 102         PyIntObject objects[N_INTOBJECTS];
 103 };
 104
 105 typedef struct _intblock PyIntBlock;
 106
 107 static PyIntBlock *block_list = NULL;
 108 static PyIntObject *free_list = NULL;
 109
 110 static PyIntObject *
 111 fill_free_list()
 112 {
 113         PyIntObject *p, *q;
 114         p = (PyIntObject *)PyMem_MALLOC(sizeof(PyIntBlock));
 115         if (p == NULL)
 116                 return (PyIntObject *)PyErr_NoMemory();
 117         ((PyIntBlock *)p)->next = block_list;
 118         block_list = (PyIntBlock *)p;
 119         p = &((PyIntBlock *)p)->objects[0];
 120         q = p + N_INTOBJECTS;
 121         while (--q > p)
 122                 q->ob_type = (struct _typeobject *)(q-1);
 123         q->ob_type = NULL;
 124         return p + N_INTOBJECTS - 1;
 125 }
 126
 127 #ifndef NSMALLPOSINTS
 128 #define NSMALLPOSINTS           100
 129 #endif
 130 #ifndef NSMALLNEGINTS
 131 #define NSMALLNEGINTS           1
 132 #endif
 133 #if NSMALLNEGINTS + NSMALLPOSINTS > 0
 134 /* References to small integers are saved in this array so that they
 135    can be shared.
 136    The integers that are saved are those in the range
 137    -NSMALLNEGINTS (inclusive) to NSMALLPOSINTS (not inclusive).
 138 */
 139 static PyIntObject *small_ints[NSMALLNEGINTS + NSMALLPOSINTS];
 140 #endif
 141 #ifdef COUNT_ALLOCS
 142 int quick_int_allocs, quick_neg_int_allocs;
 143 #endif
 144
 145 PyObject *
 146 PyInt_FromLong(ival)
 147         long ival;
 148 {
 149         register PyIntObject *v;
 150 #if NSMALLNEGINTS + NSMALLPOSINTS > 0
 151         if (-NSMALLNEGINTS <= ival && ival < NSMALLPOSINTS &&
 152             (v = small_ints[ival + NSMALLNEGINTS]) != NULL) {
 153                 Py_INCREF(v);
 154 #ifdef COUNT_ALLOCS
 155                 if (ival >= 0)
 156                         quick_int_allocs++;
 157                 else
 158                         quick_neg_int_allocs++;
 159 #endif
 160                 return (PyObject *) v;
 161         }
 162 #endif
 163         if (free_list == NULL) {
 164                 if ((free_list = fill_free_list()) == NULL)
 165                         return NULL;
 166         }
 167         v = free_list;
 168         free_list = (PyIntObject *)v->ob_type;
 169         v->ob_type = &PyInt_Type;
 170         v->ob_ival = ival;
 171         _Py_NewReference((PyObject *)v);
 172 #if NSMALLNEGINTS + NSMALLPOSINTS > 0
 173         if (-NSMALLNEGINTS <= ival && ival < NSMALLPOSINTS) {
 174                 /* save this one for a following allocation */
 175                 Py_INCREF(v);
 176                 small_ints[ival + NSMALLNEGINTS] = v;
 177         }
 178 #endif
 179         return (PyObject *) v;
 180 }
 181
 182 static void
 183 int_dealloc(v)
 184         PyIntObject *v;
 185 {
 186         v->ob_type = (struct _typeobject *)free_list;
 187         free_list = v;
 188 }
 189
 190 long
 191 PyInt_AsLong(op)
 192         register PyObject *op;
 193 {
 194         PyNumberMethods *nb;
 195         PyIntObject *io;
 196         long val;
 197
 198         if (op && PyInt_Check(op))
 199                 return PyInt_AS_LONG((PyIntObject*) op);
 200
 201         if (op == NULL || (nb = op->ob_type->tp_as_number) == NULL ||
 202             nb->nb_int == NULL) {
 203                 PyErr_BadArgument();
 204                 return -1;
 205         }
 206
 207         io = (PyIntObject*) (*nb->nb_int) (op);
 208         if (io == NULL)
 209                 return -1;
 210         if (!PyInt_Check(io)) {
 211                 PyErr_SetString(PyExc_TypeError,
 212                                 "nb_int should return int object");
 213                 return -1;
 214         }
 215
 216         val = PyInt_AS_LONG(io);
 217         Py_DECREF(io);
 218
 219         return val;
 220 }
 221
 222 PyObject *
 223 PyInt_FromString(s, pend, base)
 224         char *s;
 225         char **pend;
 226         int base;
 227 {
 228         char *end;
 229         long x;
 230         char buffer[256]; /* For errors */
 231
 232         if ((base != 0 && base < 2) || base > 36) {
 233                 PyErr_SetString(PyExc_ValueError, "invalid base for int()");
 234                 return NULL;
 235         }
 236
 237         while (*s && isspace(Py_CHARMASK(*s)))
 238                 s++;
 239         errno = 0;
 240         if (base == 0 && s[0] == '0')
 241                 x = (long) PyOS_strtoul(s, &end, base);
 242         else
 243                 x = PyOS_strtol(s, &end, base);
 244         if (end == s || !isalnum(end[-1]))
 245                 goto bad;
 246         while (*end && isspace(Py_CHARMASK(*end)))
 247                 end++;
 248         if (*end != '\0') {
 249   bad:
 250                 sprintf(buffer, "invalid literal for int(): %.200s", s);
 251                 PyErr_SetString(PyExc_ValueError, buffer);
 252                 return NULL;
 253         }
 254         else if (errno != 0) {
 255                 sprintf(buffer, "int() literal too large: %.200s", s);
 256                 PyErr_SetString(PyExc_ValueError, buffer);
 257                 return NULL;
 258         }
 259         if (pend)
 260                 *pend = end;
 261         return PyInt_FromLong(x);
 262 }
 263
 264 /* Methods */
 265
 266 /* ARGSUSED */
 267 static int
 268 int_print(v, fp, flags)
 269         PyIntObject *v;
 270         FILE *fp;
 271         int flags; /* Not used but required by interface */
 272 {
 273         fprintf(fp, "%ld", v->ob_ival);
 274         return 0;
 275 }
 276
 277 static PyObject *
 278 int_repr(v)
 279         PyIntObject *v;
 280 {
 281         char buf[20];
 282         sprintf(buf, "%ld", v->ob_ival);
 283         return PyString_FromString(buf);
 284 }
 285
 286 static int
 287 int_compare(v, w)
 288         PyIntObject *v, *w;
 289 {
 290         register long i = v->ob_ival;
 291         register long j = w->ob_ival;
 292         return (i < j) ? -1 : (i > j) ? 1 : 0;
 293 }
 294
 295 static long
 296 int_hash(v)
 297         PyIntObject *v;
 298 {
 299         /* XXX If this is changed, you also need to change the way
 300            Python's long, float and complex types are hashed. */
 301         long x = v -> ob_ival;
 302         if (x == -1)
 303                 x = -2;
 304         return x;
 305 }
 306
 307 static PyObject *
 308 int_add(v, w)
 309         PyIntObject *v;
 310         PyIntObject *w;
 311 {
 312         register long a, b, x;
 313         a = v->ob_ival;
 314         b = w->ob_ival;
 315         x = a + b;
 316         if ((x^a) < 0 && (x^b) < 0)
 317                 return err_ovf("integer addition");
 318         return PyInt_FromLong(x);
 319 }
 320
 321 static PyObject *
 322 int_sub(v, w)
 323         PyIntObject *v;
 324         PyIntObject *w;
 325 {
 326         register long a, b, x;
 327         a = v->ob_ival;
 328         b = w->ob_ival;
 329         x = a - b;
 330         if ((x^a) < 0 && (x^~b) < 0)
 331                 return err_ovf("integer subtraction");
 332         return PyInt_FromLong(x);
 333 }
 334
 335 /*
 336 Integer overflow checking used to be done using a double, but on 64
 337 bit machines (where both long and double are 64 bit) this fails
 338 because the double doesn't have enouvg precision.  John Tromp suggests
 339 the following algorithm:
 340
 341 Suppose again we normalize a and b to be nonnegative.
 342 Let ah and al (bh and bl) be the high and low 32 bits of a (b, resp.).
 343 Now we test ah and bh against zero and get essentially 3 possible outcomes.
 344
 345 1) both ah and bh > 0 : then report overflow
 346
 347 2) both ah and bh = 0 : then compute a*b and report overflow if it comes out
 348                         negative
 349
 350 3) ah > 0 and bh = 0  : compute ah*bl and report overflow if it's >= 2^31
 351                         compute al*bl and report overflow if it's negative
 352                         add (ah*bl)<<32 to al*bl and report overflow if
 353                         it's negative
 354
 355 In case of no overflow the result is then negated if necessary.
 356
 357 The majority of cases will be 2), in which case this method is the same as
 358 what I suggested before. If multiplication is expensive enough, then the
 359 other method is faster on case 3), but also more work to program, so I
 360 guess the above is the preferred solution.
 361
 362 */
 363
 364 static PyObject *
 365 int_mul(v, w)
 366         PyIntObject *v;
 367         PyIntObject *w;
 368 {
 369         long a, b, ah, bh, x, y;
 370         int s = 1;
 371
 372         a = v->ob_ival;
 373         b = w->ob_ival;
 374         ah = a >> (LONG_BIT/2);
 375         bh = b >> (LONG_BIT/2);
 376
 377         /* Quick test for common case: two small positive ints */
 378
 379         if (ah == 0 && bh == 0) {
 380                 x = a*b;
 381                 if (x < 0)
 382                         goto bad;
 383                 return PyInt_FromLong(x);
 384         }
 385
 386         /* Arrange that a >= b >= 0 */
 387
 388         if (a < 0) {
 389                 a = -a;
 390                 if (a < 0) {
 391                         /* Largest negative */
 392                         if (b == 0 || b == 1) {
 393                                 x = a*b;
 394                                 goto ok;
 395                         }
 396                         else
 397                                 goto bad;
 398                 }
 399                 s = -s;
 400                 ah = a >> (LONG_BIT/2);
 401         }
 402         if (b < 0) {
 403                 b = -b;
 404                 if (b < 0) {
 405                         /* Largest negative */
 406                         if (a == 0 || (a == 1 && s == 1)) {
 407                                 x = a*b;
 408                                 goto ok;
 409                         }
 410                         else
 411                                 goto bad;
 412                 }
 413                 s = -s;
 414                 bh = b >> (LONG_BIT/2);
 415         }
 416
 417         /* 1) both ah and bh > 0 : then report overflow */
 418
 419         if (ah != 0 && bh != 0)
 420                 goto bad;
 421
 422         /* 2) both ah and bh = 0 : then compute a*b and report
 423                                    overflow if it comes out negative */
 424
 425         if (ah == 0 && bh == 0) {
 426                 x = a*b;
 427                 if (x < 0)
 428                         goto bad;
 429                 return PyInt_FromLong(x*s);
 430         }
 431
 432         if (a < b) {
 433                 /* Swap */
 434                 x = a;
 435                 a = b;
 436                 b = x;
 437                 ah = bh;
 438                 /* bh not used beyond this point */
 439         }
 440
 441         /* 3) ah > 0 and bh = 0  : compute ah*bl and report overflow if
 442                                    it's >= 2^31
 443                         compute al*bl and report overflow if it's negative
 444                         add (ah*bl)<<32 to al*bl and report overflow if
 445                         it's negative
 446                         (NB b == bl in this case, and we make a = al) */
 447
 448         y = ah*b;
 449         if (y >= (1L << (LONG_BIT/2 - 1)))
 450                 goto bad;
 451         a &= (1L << (LONG_BIT/2)) - 1;
 452         x = a*b;
 453         if (x < 0)
 454                 goto bad;
 455         x += y << (LONG_BIT/2);
 456         if (x < 0)
 457                 goto bad;
 458  ok:
 459         return PyInt_FromLong(x * s);
 460
 461  bad:
 462         return err_ovf("integer multiplication");
 463 }
 464
 465 static int
 466 i_divmod(x, y, p_xdivy, p_xmody)
 467         register PyIntObject *x, *y;
 468         long *p_xdivy, *p_xmody;
 469 {
 470         long xi = x->ob_ival;
 471         long yi = y->ob_ival;
 472         long xdivy, xmody;
 473
 474         if (yi == 0) {
 475                 PyErr_SetString(PyExc_ZeroDivisionError,
 476                                 "integer division or modulo");
 477                 return -1;
 478         }
 479         if (yi < 0) {
 480                 if (xi < 0) {
 481                         if (yi == -1 && -xi < 0) {
 482                                 /* most negative / -1 */
 483                                 err_ovf("integer division");
 484                                 return -1;
 485                         }
 486                         xdivy = -xi / -yi;
 487                 }
 488                 else
 489                         xdivy = - (xi / -yi);
 490         }
 491         else {
 492                 if (xi < 0)
 493                         xdivy = - (-xi / yi);
 494                 else
 495                         xdivy = xi / yi;
 496         }
 497         xmody = xi - xdivy*yi;
 498         if ((xmody < 0 && yi > 0) || (xmody > 0 && yi < 0)) {
 499                 xmody += yi;
 500                 xdivy -= 1;
 501         }
 502         *p_xdivy = xdivy;
 503         *p_xmody = xmody;
 504         return 0;
 505 }
 506
 507 static PyObject *
 508 int_div(x, y)
 509         PyIntObject *x;
 510         PyIntObject *y;
 511 {
 512         long d, m;
 513         if (i_divmod(x, y, &d, &m) < 0)
 514                 return NULL;
 515         return PyInt_FromLong(d);
 516 }
 517
 518 static PyObject *
 519 int_mod(x, y)
 520         PyIntObject *x;
 521         PyIntObject *y;
 522 {
 523         long d, m;
 524         if (i_divmod(x, y, &d, &m) < 0)
 525                 return NULL;
 526         return PyInt_FromLong(m);
 527 }
 528
 529 static PyObject *
 530 int_divmod(x, y)
 531         PyIntObject *x;
 532         PyIntObject *y;
 533 {
 534         long d, m;
 535         if (i_divmod(x, y, &d, &m) < 0)
 536                 return NULL;
 537         return Py_BuildValue("(ll)", d, m);
 538 }
 539
 540 static PyObject *
 541 int_pow(v, w, z)
 542         PyIntObject *v;
 543         PyIntObject *w;
 544         PyIntObject *z;
 545 {
 546 #if 1
 547         register long iv, iw, iz=0, ix, temp, prev;
 548         iv = v->ob_ival;
 549         iw = w->ob_ival;
 550         if (iw < 0) {
 551                 PyErr_SetString(PyExc_ValueError,
 552                                 "integer to the negative power");
 553                 return NULL;
 554         }
 555         if ((PyObject *)z != Py_None) {
 556                 iz = z->ob_ival;
 557                 if (iz == 0) {
 558                         PyErr_SetString(PyExc_ValueError,
 559                                         "pow(x, y, z) with z==0");
 560                         return NULL;
 561                 }
 562         }
 563         /*
 564          * XXX: The original exponentiation code stopped looping
 565          * when temp hit zero; this code will continue onwards
 566          * unnecessarily, but at least it won't cause any errors.
 567          * Hopefully the speed improvement from the fast exponentiation
 568          * will compensate for the slight inefficiency.
 569          * XXX: Better handling of overflows is desperately needed.
 570          */
 571         temp = iv;
 572         ix = 1;
 573         while (iw > 0) {
 574                 prev = ix;      /* Save value for overflow check */
 575                 if (iw & 1) {
 576                         ix = ix*temp;
 577                         if (temp == 0)
 578                                 break; /* Avoid ix / 0 */
 579                         if (ix / temp != prev)
 580                                 return err_ovf("integer exponentiation");
 581                 }
 582                 iw >>= 1;       /* Shift exponent down by 1 bit */
 583                 if (iw==0) break;
 584                 prev = temp;
 585                 temp *= temp;   /* Square the value of temp */
 586                 if (prev!=0 && temp/prev!=prev)
 587                         return err_ovf("integer exponentiation");
 588                 if (iz) {
 589                         /* If we did a multiplication, perform a modulo */
 590                         ix = ix % iz;
 591                         temp = temp % iz;
 592                 }
 593         }
 594         if (iz) {
 595                 PyObject *t1, *t2;
 596                 long int div, mod;
 597                 t1=PyInt_FromLong(ix);
 598                 t2=PyInt_FromLong(iz);
 599                 if (t1==NULL || t2==NULL ||
 600                         i_divmod((PyIntObject *)t1,
 601                                  (PyIntObject *)t2, &div, &mod)<0)
 602                 {
 603                         Py_XDECREF(t1);
 604                         Py_XDECREF(t2);
 605                         return(NULL);
 606                 }
 607                 Py_DECREF(t1);
 608                 Py_DECREF(t2);
 609                 ix=mod;
 610         }
 611         return PyInt_FromLong(ix);
 612 #else
 613         register long iv, iw, ix;
 614         iv = v->ob_ival;
 615         iw = w->ob_ival;
 616         if (iw < 0) {
 617                 PyErr_SetString(PyExc_ValueError,
 618                                 "integer to the negative power");
 619                 return NULL;
 620         }
 621         if ((PyObject *)z != Py_None) {
 622                 PyErr_SetString(PyExc_TypeError,
 623                                 "pow(int, int, int) not yet supported");
 624                 return NULL;
 625         }
 626         ix = 1;
 627         while (--iw >= 0) {
 628                 long prev = ix;
 629                 ix = ix * iv;
 630                 if (iv == 0)
 631                         break; /* 0 to some power -- avoid ix / 0 */
 632                 if (ix / iv != prev)
 633                         return err_ovf("integer exponentiation");
 634         }
 635         return PyInt_FromLong(ix);
 636 #endif
 637 }
 638
 639 static PyObject *
 640 int_neg(v)
 641         PyIntObject *v;
 642 {
 643         register long a, x;
 644         a = v->ob_ival;
 645         x = -a;
 646         if (a < 0 && x < 0)
 647                 return err_ovf("integer negation");
 648         return PyInt_FromLong(x);
 649 }
 650
 651 static PyObject *
 652 int_pos(v)
 653         PyIntObject *v;
 654 {
 655         Py_INCREF(v);
 656         return (PyObject *)v;
 657 }
 658
 659 static PyObject *
 660 int_abs(v)
 661         PyIntObject *v;
 662 {
 663         if (v->ob_ival >= 0)
 664                 return int_pos(v);
 665         else
 666                 return int_neg(v);
 667 }
 668
 669 static int
 670 int_nonzero(v)
 671         PyIntObject *v;
 672 {
 673         return v->ob_ival != 0;
 674 }
 675
 676 static PyObject *
 677 int_invert(v)
 678         PyIntObject *v;
 679 {
 680         return PyInt_FromLong(~v->ob_ival);
 681 }
 682
 683 static PyObject *
 684 int_lshift(v, w)
 685         PyIntObject *v;
 686         PyIntObject *w;
 687 {
 688         register long a, b;
 689         a = v->ob_ival;
 690         b = w->ob_ival;
 691         if (b < 0) {
 692                 PyErr_SetString(PyExc_ValueError, "negative shift count");
 693                 return NULL;
 694         }
 695         if (a == 0 || b == 0) {
 696                 Py_INCREF(v);
 697                 return (PyObject *) v;
 698         }
 699         if (b >= LONG_BIT) {
 700                 return PyInt_FromLong(0L);
 701         }
 702         a = (unsigned long)a << b;
 703         return PyInt_FromLong(a);
 704 }
 705
 706 static PyObject *
 707 int_rshift(v, w)
 708         PyIntObject *v;
 709         PyIntObject *w;
 710 {
 711         register long a, b;
 712         a = v->ob_ival;
 713         b = w->ob_ival;
 714         if (b < 0) {
 715                 PyErr_SetString(PyExc_ValueError, "negative shift count");
 716                 return NULL;
 717         }
 718         if (a == 0 || b == 0) {
 719                 Py_INCREF(v);
 720                 return (PyObject *) v;
 721         }
 722         if (b >= LONG_BIT) {
 723                 if (a < 0)
 724                         a = -1;
 725                 else
 726                         a = 0;
 727         }
 728         else {
 729                 if (a < 0)
 730                         a = ~( ~(unsigned long)a >> b );
 731                 else
 732                         a = (unsigned long)a >> b;
 733         }
 734         return PyInt_FromLong(a);
 735 }
 736
 737 static PyObject *
 738 int_and(v, w)
 739         PyIntObject *v;
 740         PyIntObject *w;
 741 {
 742         register long a, b;
 743         a = v->ob_ival;
 744         b = w->ob_ival;
 745         return PyInt_FromLong(a & b);
 746 }
 747
 748 static PyObject *
 749 int_xor(v, w)
 750         PyIntObject *v;
 751         PyIntObject *w;
 752 {
 753         register long a, b;
 754         a = v->ob_ival;
 755         b = w->ob_ival;
 756         return PyInt_FromLong(a ^ b);
 757 }
 758
 759 static PyObject *
 760 int_or(v, w)
 761         PyIntObject *v;
 762         PyIntObject *w;
 763 {
 764         register long a, b;
 765         a = v->ob_ival;
 766         b = w->ob_ival;
 767         return PyInt_FromLong(a | b);
 768 }
 769
 770 static PyObject *
 771 int_int(v)
 772         PyIntObject *v;
 773 {
 774         Py_INCREF(v);
 775         return (PyObject *)v;
 776 }
 777
 778 static PyObject *
 779 int_long(v)
 780         PyIntObject *v;
 781 {
 782         return PyLong_FromLong((v -> ob_ival));
 783 }
 784
 785 static PyObject *
 786 int_float(v)
 787         PyIntObject *v;
 788 {
 789         return PyFloat_FromDouble((double)(v -> ob_ival));
 790 }
 791
 792 static PyObject *
 793 int_oct(v)
 794         PyIntObject *v;
 795 {
 796         char buf[100];
 797         long x = v -> ob_ival;
 798         if (x == 0)
 799                 strcpy(buf, "0");
 800         else
 801                 sprintf(buf, "0%lo", x);
 802         return PyString_FromString(buf);
 803 }
 804
 805 static PyObject *
 806 int_hex(v)
 807         PyIntObject *v;
 808 {
 809         char buf[100];
 810         long x = v -> ob_ival;
 811         sprintf(buf, "0x%lx", x);
 812         return PyString_FromString(buf);
 813 }
 814
 815 static PyNumberMethods int_as_number = {
 816         (binaryfunc)int_add, /*nb_add*/
 817         (binaryfunc)int_sub, /*nb_subtract*/
 818         (binaryfunc)int_mul, /*nb_multiply*/
 819         (binaryfunc)int_div, /*nb_divide*/
 820         (binaryfunc)int_mod, /*nb_remainder*/
 821         (binaryfunc)int_divmod, /*nb_divmod*/
 822         (ternaryfunc)int_pow, /*nb_power*/
 823         (unaryfunc)int_neg, /*nb_negative*/
 824         (unaryfunc)int_pos, /*nb_positive*/
 825         (unaryfunc)int_abs, /*nb_absolute*/
 826         (inquiry)int_nonzero, /*nb_nonzero*/
 827         (unaryfunc)int_invert, /*nb_invert*/
 828         (binaryfunc)int_lshift, /*nb_lshift*/
 829         (binaryfunc)int_rshift, /*nb_rshift*/
 830         (binaryfunc)int_and, /*nb_and*/
 831         (binaryfunc)int_xor, /*nb_xor*/
 832         (binaryfunc)int_or, /*nb_or*/
 833         0,              /*nb_coerce*/
 834         (unaryfunc)int_int, /*nb_int*/
 835         (unaryfunc)int_long, /*nb_long*/
 836         (unaryfunc)int_float, /*nb_float*/
 837         (unaryfunc)int_oct, /*nb_oct*/
 838         (unaryfunc)int_hex, /*nb_hex*/
 839 };
 840
 841 PyTypeObject PyInt_Type = {
 842         PyObject_HEAD_INIT(&PyType_Type)
 843         0,
 844         "int",
 845         sizeof(PyIntObject),
 846         0,
 847         (destructor)int_dealloc, /*tp_dealloc*/
 848         (printfunc)int_print, /*tp_print*/
 849         0,              /*tp_getattr*/
 850         0,              /*tp_setattr*/
 851         (cmpfunc)int_compare, /*tp_compare*/
 852         (reprfunc)int_repr, /*tp_repr*/
 853         &int_as_number, /*tp_as_number*/
 854         0,              /*tp_as_sequence*/
 855         0,              /*tp_as_mapping*/
 856         (hashfunc)int_hash, /*tp_hash*/
 857 };
 858
 859 void
 860 PyInt_Fini()
 861 {
 862         PyIntObject *p;
 863         PyIntBlock *list, *next;
 864         int i;
 865         int bc, bf;     /* block count, number of freed blocks */
 866         int irem, isum; /* remaining unfreed ints per block, total */
 867
 868 #if NSMALLNEGINTS + NSMALLPOSINTS > 0
 869         PyIntObject **q;
 870
 871         i = NSMALLNEGINTS + NSMALLPOSINTS;
 872         q = small_ints;
 873         while (--i >= 0) {
 874                 Py_XDECREF(*q);
 875                 *q++ = NULL;
 876         }
 877 #endif
 878         bc = 0;
 879         bf = 0;
 880         isum = 0;
 881         list = block_list;
 882         block_list = NULL;
 883         free_list = NULL;
 884         while (list != NULL) {
 885                 bc++;
 886                 irem = 0;
 887                 for (i = 0, p = &list->objects[0];
 888                      i < N_INTOBJECTS;
 889                      i++, p++) {
 890                         if (PyInt_Check(p) && p->ob_refcnt != 0)
 891                                 irem++;
 892                 }
 893                 next = list->next;
 894                 if (irem) {
 895                         list->next = block_list;
 896                         block_list = list;
 897                         for (i = 0, p = &list->objects[0];
 898                              i < N_INTOBJECTS;
 899                              i++, p++) {
 900                                 if (!PyInt_Check(p) || p->ob_refcnt == 0) {
 901                                         p->ob_type = (struct _typeobject *)
 902                                                 free_list;
 903                                         free_list = p;
 904                                 }
 905 #if NSMALLNEGINTS + NSMALLPOSINTS > 0
 906                                 else if (-NSMALLNEGINTS <= p->ob_ival &&
 907                                          p->ob_ival < NSMALLPOSINTS &&
 908                                          small_ints[p->ob_ival +
 909                                                     NSMALLNEGINTS] == NULL) {
 910                                         Py_INCREF(p);
 911                                         small_ints[p->ob_ival +
 912                                                    NSMALLNEGINTS] = p;
 913                                 }
 914 #endif
 915                         }
 916                 }
 917                 else {
 918                         PyMem_FREE(list);
 919                         bf++;
 920                 }
 921                 isum += irem;
 922                 list = next;
 923         }
 924         if (!Py_VerboseFlag)
 925                 return;
 926         fprintf(stderr, "# cleanup ints");
 927         if (!isum) {
 928                 fprintf(stderr, "\n");
 929         }
 930         else {
 931                 fprintf(stderr,
 932                         ": %d unfreed int%s in %d out of %d block%s\n",
 933                         isum, isum == 1 ? "" : "s",
 934                         bc - bf, bc, bc == 1 ? "" : "s");
 935         }
 936         if (Py_VerboseFlag > 1) {
 937                 list = block_list;
 938                 while (list != NULL) {
 939                         for (i = 0, p = &list->objects[0];
 940                              i < N_INTOBJECTS;
 941                              i++, p++) {
 942                                 if (PyInt_Check(p) && p->ob_refcnt != 0)
 943                                         fprintf(stderr,
 944                                 "#   <int at %lx, refcnt=%d, val=%ld>\n",
 945                                                 p, p->ob_refcnt, p->ob_ival);
 946                         }
 947                         list = list->next;
 948                 }
 949         }
 950 }