Objects/intobject.c

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