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