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(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 xi, register long yi,
 438          long *p_xdivy, long *p_xmody)
 439 {
 440         long xdivy, xmody;
 441
 442         if (yi == 0) {
 443                 PyErr_SetString(PyExc_ZeroDivisionError,
 444                                 "integer division or modulo by zero");
 445                 return -1;
 446         }
 447         if (yi < 0) {
 448                 if (xi < 0) {
 449                         if (yi == -1 && -xi < 0) {
 450                                 /* most negative / -1 */
 451                                 err_ovf("integer division");
 452                                 return -1;
 453                         }
 454                         xdivy = -xi / -yi;
 455                 }
 456                 else
 457                         xdivy = - (xi / -yi);
 458         }
 459         else {
 460                 if (xi < 0)
 461                         xdivy = - (-xi / yi);
 462                 else
 463                         xdivy = xi / yi;
 464         }
 465         xmody = xi - xdivy*yi;
 466         if ((xmody < 0 && yi > 0) || (xmody > 0 && yi < 0)) {
 467                 xmody += yi;
 468                 xdivy -= 1;
 469         }
 470         *p_xdivy = xdivy;
 471         *p_xmody = xmody;
 472         return 0;
 473 }
 474
 475 static PyObject *
 476 int_div(PyIntObject *x, PyIntObject *y)
 477 {
 478         long xi, yi;
 479         long d, m;
 480         CONVERT_TO_LONG(x, xi);
 481         CONVERT_TO_LONG(y, yi);
 482         if (i_divmod(xi, yi, &d, &m) < 0)
 483                 return NULL;
 484         return PyInt_FromLong(d);
 485 }
 486
 487 static PyObject *
 488 int_mod(PyIntObject *x, PyIntObject *y)
 489 {
 490         long xi, yi;
 491         long d, m;
 492         CONVERT_TO_LONG(x, xi);
 493         CONVERT_TO_LONG(y, yi);
 494         if (i_divmod(xi, yi, &d, &m) < 0)
 495                 return NULL;
 496         return PyInt_FromLong(m);
 497 }
 498
 499 static PyObject *
 500 int_divmod(PyIntObject *x, PyIntObject *y)
 501 {
 502         long xi, yi;
 503         long d, m;
 504         CONVERT_TO_LONG(x, xi);
 505         CONVERT_TO_LONG(y, yi);
 506         if (i_divmod(xi, yi, &d, &m) < 0)
 507                 return NULL;
 508         return Py_BuildValue("(ll)", d, m);
 509 }
 510
 511 static PyObject *
 512 int_pow(PyIntObject *v, PyIntObject *w, PyIntObject *z)
 513 {
 514 #if 1
 515         register long iv, iw, iz=0, ix, temp, prev;
 516         CONVERT_TO_LONG(v, iv);
 517         CONVERT_TO_LONG(w, iw);
 518         if (iw < 0) {
 519                 if (iv)
 520                         PyErr_SetString(PyExc_ValueError,
 521                                         "cannot raise integer to a negative power");
 522                 else
 523                         PyErr_SetString(PyExc_ZeroDivisionError,
 524                                         "cannot raise 0 to a negative power");
 525                 return NULL;
 526         }
 527         if ((PyObject *)z != Py_None) {
 528                 CONVERT_TO_LONG(z, iz);
 529                 if (iz == 0) {
 530                         PyErr_SetString(PyExc_ValueError,
 531                                         "pow() arg 3 cannot be 0");
 532                         return NULL;
 533                 }
 534         }
 535         /*
 536          * XXX: The original exponentiation code stopped looping
 537          * when temp hit zero; this code will continue onwards
 538          * unnecessarily, but at least it won't cause any errors.
 539          * Hopefully the speed improvement from the fast exponentiation
 540          * will compensate for the slight inefficiency.
 541          * XXX: Better handling of overflows is desperately needed.
 542          */
 543         temp = iv;
 544         ix = 1;
 545         while (iw > 0) {
 546                 prev = ix;      /* Save value for overflow check */
 547                 if (iw & 1) {
 548                         ix = ix*temp;
 549                         if (temp == 0)
 550                                 break; /* Avoid ix / 0 */
 551                         if (ix / temp != prev)
 552                                 return err_ovf("integer exponentiation");
 553                 }
 554                 iw >>= 1;       /* Shift exponent down by 1 bit */
 555                 if (iw==0) break;
 556                 prev = temp;
 557                 temp *= temp;   /* Square the value of temp */
 558                 if (prev!=0 && temp/prev!=prev)
 559                         return err_ovf("integer exponentiation");
 560                 if (iz) {
 561                         /* If we did a multiplication, perform a modulo */
 562                         ix = ix % iz;
 563                         temp = temp % iz;
 564                 }
 565         }
 566         if (iz) {
 567                 long div, mod;
 568                 if (i_divmod(ix, iz, &div, &mod) < 0)
 569                         return(NULL);
 570                 ix=mod;
 571         }
 572         return PyInt_FromLong(ix);
 573 #else
 574         register long iv, iw, ix;
 575         CONVERT_TO_LONG(v, iv);
 576         CONVERT_TO_LONG(w, iw);
 577         if (iw < 0) {
 578                 PyErr_SetString(PyExc_ValueError,
 579                                 "integer to the negative power");
 580                 return NULL;
 581         }
 582         if ((PyObject *)z != Py_None) {
 583                 PyErr_SetString(PyExc_TypeError,
 584                                 "pow(int, int, int) not yet supported");
 585                 return NULL;
 586         }
 587         ix = 1;
 588         while (--iw >= 0) {
 589                 long prev = ix;
 590                 ix = ix * iv;
 591                 if (iv == 0)
 592                         break; /* 0 to some power -- avoid ix / 0 */
 593                 if (ix / iv != prev)
 594                         return err_ovf("integer exponentiation");
 595         }
 596         return PyInt_FromLong(ix);
 597 #endif
 598 }
 599
 600 static PyObject *
 601 int_neg(PyIntObject *v)
 602 {
 603         register long a, x;
 604         a = v->ob_ival;
 605         x = -a;
 606         if (a < 0 && x < 0)
 607                 return err_ovf("integer negation");
 608         return PyInt_FromLong(x);
 609 }
 610
 611 static PyObject *
 612 int_pos(PyIntObject *v)
 613 {
 614         Py_INCREF(v);
 615         return (PyObject *)v;
 616 }
 617
 618 static PyObject *
 619 int_abs(PyIntObject *v)
 620 {
 621         if (v->ob_ival >= 0)
 622                 return int_pos(v);
 623         else
 624                 return int_neg(v);
 625 }
 626
 627 static int
 628 int_nonzero(PyIntObject *v)
 629 {
 630         return v->ob_ival != 0;
 631 }
 632
 633 static PyObject *
 634 int_invert(PyIntObject *v)
 635 {
 636         return PyInt_FromLong(~v->ob_ival);
 637 }
 638
 639 static PyObject *
 640 int_lshift(PyIntObject *v, PyIntObject *w)
 641 {
 642         register long a, b;
 643         CONVERT_TO_LONG(v, a);
 644         CONVERT_TO_LONG(w, b);
 645         if (b < 0) {
 646                 PyErr_SetString(PyExc_ValueError, "negative shift count");
 647                 return NULL;
 648         }
 649         if (a == 0 || b == 0) {
 650                 Py_INCREF(v);
 651                 return (PyObject *) v;
 652         }
 653         if (b >= LONG_BIT) {
 654                 return PyInt_FromLong(0L);
 655         }
 656         a = (unsigned long)a << b;
 657         return PyInt_FromLong(a);
 658 }
 659
 660 static PyObject *
 661 int_rshift(PyIntObject *v, PyIntObject *w)
 662 {
 663         register long a, b;
 664         CONVERT_TO_LONG(v, a);
 665         CONVERT_TO_LONG(w, b);
 666         if (b < 0) {
 667                 PyErr_SetString(PyExc_ValueError, "negative shift count");
 668                 return NULL;
 669         }
 670         if (a == 0 || b == 0) {
 671                 Py_INCREF(v);
 672                 return (PyObject *) v;
 673         }
 674         if (b >= LONG_BIT) {
 675                 if (a < 0)
 676                         a = -1;
 677                 else
 678                         a = 0;
 679         }
 680         else {
 681                 a = Py_ARITHMETIC_RIGHT_SHIFT(long, a, b);
 682         }
 683         return PyInt_FromLong(a);
 684 }
 685
 686 static PyObject *
 687 int_and(PyIntObject *v, PyIntObject *w)
 688 {
 689         register long a, b;
 690         CONVERT_TO_LONG(v, a);
 691         CONVERT_TO_LONG(w, b);
 692         return PyInt_FromLong(a & b);
 693 }
 694
 695 static PyObject *
 696 int_xor(PyIntObject *v, PyIntObject *w)
 697 {
 698         register long a, b;
 699         CONVERT_TO_LONG(v, a);
 700         CONVERT_TO_LONG(w, b);
 701         return PyInt_FromLong(a ^ b);
 702 }
 703
 704 static PyObject *
 705 int_or(PyIntObject *v, PyIntObject *w)
 706 {
 707         register long a, b;
 708         CONVERT_TO_LONG(v, a);
 709         CONVERT_TO_LONG(w, b);
 710         return PyInt_FromLong(a | b);
 711 }
 712
 713 static PyObject *
 714 int_int(PyIntObject *v)
 715 {
 716         Py_INCREF(v);
 717         return (PyObject *)v;
 718 }
 719
 720 static PyObject *
 721 int_long(PyIntObject *v)
 722 {
 723         return PyLong_FromLong((v -> ob_ival));
 724 }
 725
 726 static PyObject *
 727 int_float(PyIntObject *v)
 728 {
 729         return PyFloat_FromDouble((double)(v -> ob_ival));
 730 }
 731
 732 static PyObject *
 733 int_oct(PyIntObject *v)
 734 {
 735         char buf[100];
 736         long x = v -> ob_ival;
 737         if (x == 0)
 738                 strcpy(buf, "0");
 739         else
 740                 sprintf(buf, "0%lo", x);
 741         return PyString_FromString(buf);
 742 }
 743
 744 static PyObject *
 745 int_hex(PyIntObject *v)
 746 {
 747         char buf[100];
 748         long x = v -> ob_ival;
 749         sprintf(buf, "0x%lx", x);
 750         return PyString_FromString(buf);
 751 }
 752
 753 static PyNumberMethods int_as_number = {
 754         (binaryfunc)int_add,    /*nb_add*/
 755         (binaryfunc)int_sub,    /*nb_subtract*/
 756         (binaryfunc)int_mul,    /*nb_multiply*/
 757         (binaryfunc)int_div,    /*nb_divide*/
 758         (binaryfunc)int_mod,    /*nb_remainder*/
 759         (binaryfunc)int_divmod, /*nb_divmod*/
 760         (ternaryfunc)int_pow,   /*nb_power*/
 761         (unaryfunc)int_neg,     /*nb_negative*/
 762         (unaryfunc)int_pos,     /*nb_positive*/
 763         (unaryfunc)int_abs,     /*nb_absolute*/
 764         (inquiry)int_nonzero,   /*nb_nonzero*/
 765         (unaryfunc)int_invert,  /*nb_invert*/
 766         (binaryfunc)int_lshift, /*nb_lshift*/
 767         (binaryfunc)int_rshift, /*nb_rshift*/
 768         (binaryfunc)int_and,    /*nb_and*/
 769         (binaryfunc)int_xor,    /*nb_xor*/
 770         (binaryfunc)int_or,     /*nb_or*/
 771         0,                      /*nb_coerce*/
 772         (unaryfunc)int_int,     /*nb_int*/
 773         (unaryfunc)int_long,    /*nb_long*/
 774         (unaryfunc)int_float,   /*nb_float*/
 775         (unaryfunc)int_oct,     /*nb_oct*/
 776         (unaryfunc)int_hex,     /*nb_hex*/
 777         0,                      /*nb_inplace_add*/
 778         0,                      /*nb_inplace_subtract*/
 779         0,                      /*nb_inplace_multiply*/
 780         0,                      /*nb_inplace_divide*/
 781         0,                      /*nb_inplace_remainder*/
 782         0,                      /*nb_inplace_power*/
 783         0,                      /*nb_inplace_lshift*/
 784         0,                      /*nb_inplace_rshift*/
 785         0,                      /*nb_inplace_and*/
 786         0,                      /*nb_inplace_xor*/
 787         0,                      /*nb_inplace_or*/
 788 };
 789
 790 PyTypeObject PyInt_Type = {
 791         PyObject_HEAD_INIT(&PyType_Type)
 792         0,
 793         "int",
 794         sizeof(PyIntObject),
 795         0,
 796         (destructor)int_dealloc, /*tp_dealloc*/
 797         (printfunc)int_print, /*tp_print*/
 798         0,              /*tp_getattr*/
 799         0,              /*tp_setattr*/
 800         (cmpfunc)int_compare, /*tp_compare*/
 801         (reprfunc)int_repr, /*tp_repr*/
 802         &int_as_number, /*tp_as_number*/
 803         0,              /*tp_as_sequence*/
 804         0,              /*tp_as_mapping*/
 805         (hashfunc)int_hash, /*tp_hash*/
 806         0,                      /*tp_call*/
 807         0,                      /*tp_str*/
 808         0,                      /*tp_getattro*/
 809         0,                      /*tp_setattro*/
 810         0,                      /*tp_as_buffer*/
 811         Py_TPFLAGS_CHECKTYPES   /*tp_flags*/
 812 };
 813
 814 void
 815 PyInt_Fini(void)
 816 {
 817         PyIntObject *p;
 818         PyIntBlock *list, *next;
 819         int i;
 820         int bc, bf;     /* block count, number of freed blocks */
 821         int irem, isum; /* remaining unfreed ints per block, total */
 822
 823 #if NSMALLNEGINTS + NSMALLPOSINTS > 0
 824         PyIntObject **q;
 825
 826         i = NSMALLNEGINTS + NSMALLPOSINTS;
 827         q = small_ints;
 828         while (--i >= 0) {
 829                 Py_XDECREF(*q);
 830                 *q++ = NULL;
 831         }
 832 #endif
 833         bc = 0;
 834         bf = 0;
 835         isum = 0;
 836         list = block_list;
 837         block_list = NULL;
 838         free_list = NULL;
 839         while (list != NULL) {
 840                 bc++;
 841                 irem = 0;
 842                 for (i = 0, p = &list->objects[0];
 843                      i < N_INTOBJECTS;
 844                      i++, p++) {
 845                         if (PyInt_Check(p) && p->ob_refcnt != 0)
 846                                 irem++;
 847                 }
 848                 next = list->next;
 849                 if (irem) {
 850                         list->next = block_list;
 851                         block_list = list;
 852                         for (i = 0, p = &list->objects[0];
 853                              i < N_INTOBJECTS;
 854                              i++, p++) {
 855                                 if (!PyInt_Check(p) || p->ob_refcnt == 0) {
 856                                         p->ob_type = (struct _typeobject *)
 857                                                 free_list;
 858                                         free_list = p;
 859                                 }
 860 #if NSMALLNEGINTS + NSMALLPOSINTS > 0
 861                                 else if (-NSMALLNEGINTS <= p->ob_ival &&
 862                                          p->ob_ival < NSMALLPOSINTS &&
 863                                          small_ints[p->ob_ival +
 864                                                     NSMALLNEGINTS] == NULL) {
 865                                         Py_INCREF(p);
 866                                         small_ints[p->ob_ival +
 867                                                    NSMALLNEGINTS] = p;
 868                                 }
 869 #endif
 870                         }
 871                 }
 872                 else {
 873                         PyMem_FREE(list); /* XXX PyObject_FREE ??? */
 874                         bf++;
 875                 }
 876                 isum += irem;
 877                 list = next;
 878         }
 879         if (!Py_VerboseFlag)
 880                 return;
 881         fprintf(stderr, "# cleanup ints");
 882         if (!isum) {
 883                 fprintf(stderr, "\n");
 884         }
 885         else {
 886                 fprintf(stderr,
 887                         ": %d unfreed int%s in %d out of %d block%s\n",
 888                         isum, isum == 1 ? "" : "s",
 889                         bc - bf, bc, bc == 1 ? "" : "s");
 890         }
 891         if (Py_VerboseFlag > 1) {
 892                 list = block_list;
 893                 while (list != NULL) {
 894                         for (i = 0, p = &list->objects[0];
 895                              i < N_INTOBJECTS;
 896                              i++, p++) {
 897                                 if (PyInt_Check(p) && p->ob_refcnt != 0)
 898                                         fprintf(stderr,
 899                                 "#   <int at %p, refcnt=%d, val=%ld>\n",
 900                                                 p, p->ob_refcnt, p->ob_ival);
 901                         }
 902                         list = list->next;
 903                 }
 904         }
 905 }