Objects/intobject.c

   1
   2 /* Integer object implementation */
   3
   4 #include "Python.h"
   5 #include <ctype.h>
   6 #include <float.h>
   7
   8 static PyObject *int_int(PyIntObject *v);
   9
  10 long
  11 PyInt_GetMax(void)
  12 {
  13         return LONG_MAX;        /* To initialize sys.maxint */
  14 }
  15
  16 /* Integers are quite normal objects, to make object handling uniform.
  17    (Using odd pointers to represent integers would save much space
  18    but require extra checks for this special case throughout the code.)
  19    Since a typical Python program spends much of its time allocating
  20    and deallocating integers, these operations should be very fast.
  21    Therefore we use a dedicated allocation scheme with a much lower
  22    overhead (in space and time) than straight malloc(): a simple
  23    dedicated free list, filled when necessary with memory from malloc().
  24
  25    block_list is a singly-linked list of all PyIntBlocks ever allocated,
  26    linked via their next members.  PyIntBlocks are never returned to the
  27    system before shutdown (PyInt_Fini).
  28
  29    free_list is a singly-linked list of available PyIntObjects, linked
  30    via abuse of their ob_type members.
  31 */
  32
  33 #define BLOCK_SIZE      1000    /* 1K less typical malloc overhead */
  34 #define BHEAD_SIZE      8       /* Enough for a 64-bit pointer */
  35 #define N_INTOBJECTS    ((BLOCK_SIZE - BHEAD_SIZE) / sizeof(PyIntObject))
  36
  37 struct _intblock {
  38         struct _intblock *next;
  39         PyIntObject objects[N_INTOBJECTS];
  40 };
  41
  42 typedef struct _intblock PyIntBlock;
  43
  44 static PyIntBlock *block_list = NULL;
  45 static PyIntObject *free_list = NULL;
  46
  47 static PyIntObject *
  48 fill_free_list(void)
  49 {
  50         PyIntObject *p, *q;
  51         /* Python's object allocator isn't appropriate for large blocks. */
  52         p = (PyIntObject *) PyMem_MALLOC(sizeof(PyIntBlock));
  53         if (p == NULL)
  54                 return (PyIntObject *) PyErr_NoMemory();
  55         ((PyIntBlock *)p)->next = block_list;
  56         block_list = (PyIntBlock *)p;
  57         /* Link the int objects together, from rear to front, then return
  58            the address of the last int object in the block. */
  59         p = &((PyIntBlock *)p)->objects[0];
  60         q = p + N_INTOBJECTS;
  61         while (--q > p)
  62                 Py_TYPE(q) = (struct _typeobject *)(q-1);
  63         Py_TYPE(q) = NULL;
  64         return p + N_INTOBJECTS - 1;
  65 }
  66
  67 #ifndef NSMALLPOSINTS
  68 #define NSMALLPOSINTS           257
  69 #endif
  70 #ifndef NSMALLNEGINTS
  71 #define NSMALLNEGINTS           5
  72 #endif
  73 #if NSMALLNEGINTS + NSMALLPOSINTS > 0
  74 /* References to small integers are saved in this array so that they
  75    can be shared.
  76    The integers that are saved are those in the range
  77    -NSMALLNEGINTS (inclusive) to NSMALLPOSINTS (not inclusive).
  78 */
  79 static PyIntObject *small_ints[NSMALLNEGINTS + NSMALLPOSINTS];
  80 #endif
  81 #ifdef COUNT_ALLOCS
  82 Py_ssize_t quick_int_allocs;
  83 Py_ssize_t quick_neg_int_allocs;
  84 #endif
  85
  86 PyObject *
  87 PyInt_FromLong(long ival)
  88 {
  89         register PyIntObject *v;
  90 #if NSMALLNEGINTS + NSMALLPOSINTS > 0
  91         if (-NSMALLNEGINTS <= ival && ival < NSMALLPOSINTS) {
  92                 v = small_ints[ival + NSMALLNEGINTS];
  93                 Py_INCREF(v);
  94 #ifdef COUNT_ALLOCS
  95                 if (ival >= 0)
  96                         quick_int_allocs++;
  97                 else
  98                         quick_neg_int_allocs++;
  99 #endif
 100                 return (PyObject *) v;
 101         }
 102 #endif
 103         if (free_list == NULL) {
 104                 if ((free_list = fill_free_list()) == NULL)
 105                         return NULL;
 106         }
 107         /* Inline PyObject_New */
 108         v = free_list;
 109         free_list = (PyIntObject *)Py_TYPE(v);
 110         PyObject_INIT(v, &PyInt_Type);
 111         v->ob_ival = ival;
 112         return (PyObject *) v;
 113 }
 114
 115 PyObject *
 116 PyInt_FromSize_t(size_t ival)
 117 {
 118         if (ival <= LONG_MAX)
 119                 return PyInt_FromLong((long)ival);
 120         return _PyLong_FromSize_t(ival);
 121 }
 122
 123 PyObject *
 124 PyInt_FromSsize_t(Py_ssize_t ival)
 125 {
 126         if (ival >= LONG_MIN && ival <= LONG_MAX)
 127                 return PyInt_FromLong((long)ival);
 128         return _PyLong_FromSsize_t(ival);
 129 }
 130
 131 static void
 132 int_dealloc(PyIntObject *v)
 133 {
 134         if (PyInt_CheckExact(v)) {
 135                 Py_TYPE(v) = (struct _typeobject *)free_list;
 136                 free_list = v;
 137         }
 138         else
 139                 Py_TYPE(v)->tp_free((PyObject *)v);
 140 }
 141
 142 static void
 143 int_free(PyIntObject *v)
 144 {
 145         Py_TYPE(v) = (struct _typeobject *)free_list;
 146         free_list = v;
 147 }
 148
 149 long
 150 PyInt_AsLong(register PyObject *op)
 151 {
 152         PyNumberMethods *nb;
 153         PyIntObject *io;
 154         long val;
 155
 156         if (op && PyInt_Check(op))
 157                 return PyInt_AS_LONG((PyIntObject*) op);
 158
 159         if (op == NULL || (nb = Py_TYPE(op)->tp_as_number) == NULL ||
 160             nb->nb_int == NULL) {
 161                 PyErr_SetString(PyExc_TypeError, "an integer is required");
 162                 return -1;
 163         }
 164
 165         io = (PyIntObject*) (*nb->nb_int) (op);
 166         if (io == NULL)
 167                 return -1;
 168         if (!PyInt_Check(io)) {
 169                 if (PyLong_Check(io)) {
 170                         /* got a long? => retry int conversion */
 171                         val = PyLong_AsLong((PyObject *)io);
 172                         Py_DECREF(io);
 173                         if ((val == -1) && PyErr_Occurred())
 174                                 return -1;
 175                         return val;
 176                 }
 177                 else
 178                 {
 179                         Py_DECREF(io);
 180                         PyErr_SetString(PyExc_TypeError,
 181                                         "nb_int should return int object");
 182                         return -1;
 183                 }
 184         }
 185
 186         val = PyInt_AS_LONG(io);
 187         Py_DECREF(io);
 188
 189         return val;
 190 }
 191
 192 Py_ssize_t
 193 PyInt_AsSsize_t(register PyObject *op)
 194 {
 195 #if SIZEOF_SIZE_T != SIZEOF_LONG
 196         PyNumberMethods *nb;
 197         PyIntObject *io;
 198         Py_ssize_t val;
 199 #endif
 200
 201         if (op == NULL) {
 202                 PyErr_SetString(PyExc_TypeError, "an integer is required");
 203                 return -1;
 204         }
 205
 206         if (PyInt_Check(op))
 207                 return PyInt_AS_LONG((PyIntObject*) op);
 208         if (PyLong_Check(op))
 209                 return _PyLong_AsSsize_t(op);
 210 #if SIZEOF_SIZE_T == SIZEOF_LONG
 211         return PyInt_AsLong(op);
 212 #else
 213
 214         if ((nb = Py_TYPE(op)->tp_as_number) == NULL ||
 215             (nb->nb_int == NULL && nb->nb_long == 0)) {
 216                 PyErr_SetString(PyExc_TypeError, "an integer is required");
 217                 return -1;
 218         }
 219
 220         if (nb->nb_long != 0)
 221                 io = (PyIntObject*) (*nb->nb_long) (op);
 222         else
 223                 io = (PyIntObject*) (*nb->nb_int) (op);
 224         if (io == NULL)
 225                 return -1;
 226         if (!PyInt_Check(io)) {
 227                 if (PyLong_Check(io)) {
 228                         /* got a long? => retry int conversion */
 229                         val = _PyLong_AsSsize_t((PyObject *)io);
 230                         Py_DECREF(io);
 231                         if ((val == -1) && PyErr_Occurred())
 232                                 return -1;
 233                         return val;
 234                 }
 235                 else
 236                 {
 237                         Py_DECREF(io);
 238                         PyErr_SetString(PyExc_TypeError,
 239                                         "nb_int should return int object");
 240                         return -1;
 241                 }
 242         }
 243
 244         val = PyInt_AS_LONG(io);
 245         Py_DECREF(io);
 246
 247         return val;
 248 #endif
 249 }
 250
 251 unsigned long
 252 PyInt_AsUnsignedLongMask(register PyObject *op)
 253 {
 254         PyNumberMethods *nb;
 255         PyIntObject *io;
 256         unsigned long val;
 257
 258         if (op && PyInt_Check(op))
 259                 return PyInt_AS_LONG((PyIntObject*) op);
 260         if (op && PyLong_Check(op))
 261                 return PyLong_AsUnsignedLongMask(op);
 262
 263         if (op == NULL || (nb = Py_TYPE(op)->tp_as_number) == NULL ||
 264             nb->nb_int == NULL) {
 265                 PyErr_SetString(PyExc_TypeError, "an integer is required");
 266                 return (unsigned long)-1;
 267         }
 268
 269         io = (PyIntObject*) (*nb->nb_int) (op);
 270         if (io == NULL)
 271                 return (unsigned long)-1;
 272         if (!PyInt_Check(io)) {
 273                 if (PyLong_Check(io)) {
 274                         val = PyLong_AsUnsignedLongMask((PyObject *)io);
 275                         Py_DECREF(io);
 276                         if (PyErr_Occurred())
 277                                 return (unsigned long)-1;
 278                         return val;
 279                 }
 280                 else
 281                 {
 282                         Py_DECREF(io);
 283                         PyErr_SetString(PyExc_TypeError,
 284                                         "nb_int should return int object");
 285                         return (unsigned long)-1;
 286                 }
 287         }
 288
 289         val = PyInt_AS_LONG(io);
 290         Py_DECREF(io);
 291
 292         return val;
 293 }
 294
 295 #ifdef HAVE_LONG_LONG
 296 unsigned PY_LONG_LONG
 297 PyInt_AsUnsignedLongLongMask(register PyObject *op)
 298 {
 299         PyNumberMethods *nb;
 300         PyIntObject *io;
 301         unsigned PY_LONG_LONG val;
 302
 303         if (op && PyInt_Check(op))
 304                 return PyInt_AS_LONG((PyIntObject*) op);
 305         if (op && PyLong_Check(op))
 306                 return PyLong_AsUnsignedLongLongMask(op);
 307
 308         if (op == NULL || (nb = Py_TYPE(op)->tp_as_number) == NULL ||
 309             nb->nb_int == NULL) {
 310                 PyErr_SetString(PyExc_TypeError, "an integer is required");
 311                 return (unsigned PY_LONG_LONG)-1;
 312         }
 313
 314         io = (PyIntObject*) (*nb->nb_int) (op);
 315         if (io == NULL)
 316                 return (unsigned PY_LONG_LONG)-1;
 317         if (!PyInt_Check(io)) {
 318                 if (PyLong_Check(io)) {
 319                         val = PyLong_AsUnsignedLongLongMask((PyObject *)io);
 320                         Py_DECREF(io);
 321                         if (PyErr_Occurred())
 322                                 return (unsigned PY_LONG_LONG)-1;
 323                         return val;
 324                 }
 325                 else
 326                 {
 327                         Py_DECREF(io);
 328                         PyErr_SetString(PyExc_TypeError,
 329                                         "nb_int should return int object");
 330                         return (unsigned PY_LONG_LONG)-1;
 331                 }
 332         }
 333
 334         val = PyInt_AS_LONG(io);
 335         Py_DECREF(io);
 336
 337         return val;
 338 }
 339 #endif
 340
 341 PyObject *
 342 PyInt_FromString(char *s, char **pend, int base)
 343 {
 344         char *end;
 345         long x;
 346         Py_ssize_t slen;
 347         PyObject *sobj, *srepr;
 348
 349         if ((base != 0 && base < 2) || base > 36) {
 350                 PyErr_SetString(PyExc_ValueError,
 351                                 "int() base must be >= 2 and <= 36");
 352                 return NULL;
 353         }
 354
 355         while (*s && isspace(Py_CHARMASK(*s)))
 356                 s++;
 357         errno = 0;
 358         if (base == 0 && s[0] == '0') {
 359                 x = (long) PyOS_strtoul(s, &end, base);
 360                 if (x < 0)
 361                         return PyLong_FromString(s, pend, base);
 362         }
 363         else
 364                 x = PyOS_strtol(s, &end, base);
 365         if (end == s || !isalnum(Py_CHARMASK(end[-1])))
 366                 goto bad;
 367         while (*end && isspace(Py_CHARMASK(*end)))
 368                 end++;
 369         if (*end != '\0') {
 370   bad:
 371                 slen = strlen(s) < 200 ? strlen(s) : 200;
 372                 sobj = PyString_FromStringAndSize(s, slen);
 373                 if (sobj == NULL)
 374                         return NULL;
 375                 srepr = PyObject_Repr(sobj);
 376                 Py_DECREF(sobj);
 377                 if (srepr == NULL)
 378                         return NULL;
 379                 PyErr_Format(PyExc_ValueError,
 380                              "invalid literal for int() with base %d: %s",
 381                              base, PyString_AS_STRING(srepr));
 382                 Py_DECREF(srepr);
 383                 return NULL;
 384         }
 385         else if (errno != 0)
 386                 return PyLong_FromString(s, pend, base);
 387         if (pend)
 388                 *pend = end;
 389         return PyInt_FromLong(x);
 390 }
 391
 392 #ifdef Py_USING_UNICODE
 393 PyObject *
 394 PyInt_FromUnicode(Py_UNICODE *s, Py_ssize_t length, int base)
 395 {
 396         PyObject *result;
 397         char *buffer = (char *)PyMem_MALLOC(length+1);
 398
 399         if (buffer == NULL)
 400                 return PyErr_NoMemory();
 401
 402         if (PyUnicode_EncodeDecimal(s, length, buffer, NULL)) {
 403                 PyMem_FREE(buffer);
 404                 return NULL;
 405         }
 406         result = PyInt_FromString(buffer, NULL, base);
 407         PyMem_FREE(buffer);
 408         return result;
 409 }
 410 #endif
 411
 412 /* Methods */
 413
 414 /* Integers are seen as the "smallest" of all numeric types and thus
 415    don't have any knowledge about conversion of other types to
 416    integers. */
 417
 418 #define CONVERT_TO_LONG(obj, lng)               \
 419         if (PyInt_Check(obj)) {                 \
 420                 lng = PyInt_AS_LONG(obj);       \
 421         }                                       \
 422         else {                                  \
 423                 Py_INCREF(Py_NotImplemented);   \
 424                 return Py_NotImplemented;       \
 425         }
 426
 427 /* ARGSUSED */
 428 static int
 429 int_print(PyIntObject *v, FILE *fp, int flags)
 430      /* flags -- not used but required by interface */
 431 {
 432         long int_val = v->ob_ival;
 433         Py_BEGIN_ALLOW_THREADS
 434         fprintf(fp, "%ld", int_val);
 435         Py_END_ALLOW_THREADS
 436         return 0;
 437 }
 438
 439 static int
 440 int_compare(PyIntObject *v, PyIntObject *w)
 441 {
 442         register long i = v->ob_ival;
 443         register long j = w->ob_ival;
 444         return (i < j) ? -1 : (i > j) ? 1 : 0;
 445 }
 446
 447 static long
 448 int_hash(PyIntObject *v)
 449 {
 450         /* XXX If this is changed, you also need to change the way
 451            Python's long, float and complex types are hashed. */
 452         long x = v -> ob_ival;
 453         if (x == -1)
 454                 x = -2;
 455         return x;
 456 }
 457
 458 static PyObject *
 459 int_add(PyIntObject *v, PyIntObject *w)
 460 {
 461         register long a, b, x;
 462         CONVERT_TO_LONG(v, a);
 463         CONVERT_TO_LONG(w, b);
 464         /* casts in the line below avoid undefined behaviour on overflow */
 465         x = (long)((unsigned long)a + b);
 466         if ((x^a) >= 0 || (x^b) >= 0)
 467                 return PyInt_FromLong(x);
 468         return PyLong_Type.tp_as_number->nb_add((PyObject *)v, (PyObject *)w);
 469 }
 470
 471 static PyObject *
 472 int_sub(PyIntObject *v, PyIntObject *w)
 473 {
 474         register long a, b, x;
 475         CONVERT_TO_LONG(v, a);
 476         CONVERT_TO_LONG(w, b);
 477         /* casts in the line below avoid undefined behaviour on overflow */
 478         x = (long)((unsigned long)a - b);
 479         if ((x^a) >= 0 || (x^~b) >= 0)
 480                 return PyInt_FromLong(x);
 481         return PyLong_Type.tp_as_number->nb_subtract((PyObject *)v,
 482                                                      (PyObject *)w);
 483 }
 484
 485 /*
 486 Integer overflow checking for * is painful:  Python tried a couple ways, but
 487 they didn't work on all platforms, or failed in endcases (a product of
 488 -sys.maxint-1 has been a particular pain).
 489
 490 Here's another way:
 491
 492 The native long product x*y is either exactly right or *way* off, being
 493 just the last n bits of the true product, where n is the number of bits
 494 in a long (the delivered product is the true product plus i*2**n for
 495 some integer i).
 496
 497 The native double product (double)x * (double)y is subject to three
 498 rounding errors:  on a sizeof(long)==8 box, each cast to double can lose
 499 info, and even on a sizeof(long)==4 box, the multiplication can lose info.
 500 But, unlike the native long product, it's not in *range* trouble:  even
 501 if sizeof(long)==32 (256-bit longs), the product easily fits in the
 502 dynamic range of a double.  So the leading 50 (or so) bits of the double
 503 product are correct.
 504
 505 We check these two ways against each other, and declare victory if they're
 506 approximately the same.  Else, because the native long product is the only
 507 one that can lose catastrophic amounts of information, it's the native long
 508 product that must have overflowed.
 509 */
 510
 511 static PyObject *
 512 int_mul(PyObject *v, PyObject *w)
 513 {
 514         long a, b;
 515         long longprod;                  /* a*b in native long arithmetic */
 516         double doubled_longprod;        /* (double)longprod */
 517         double doubleprod;              /* (double)a * (double)b */
 518
 519         CONVERT_TO_LONG(v, a);
 520         CONVERT_TO_LONG(w, b);
 521         /* casts in the next line avoid undefined behaviour on overflow */
 522         longprod = (long)((unsigned long)a * b);
 523         doubleprod = (double)a * (double)b;
 524         doubled_longprod = (double)longprod;
 525
 526         /* Fast path for normal case:  small multiplicands, and no info
 527            is lost in either method. */
 528         if (doubled_longprod == doubleprod)
 529                 return PyInt_FromLong(longprod);
 530
 531         /* Somebody somewhere lost info.  Close enough, or way off?  Note
 532            that a != 0 and b != 0 (else doubled_longprod == doubleprod == 0).
 533            The difference either is or isn't significant compared to the
 534            true value (of which doubleprod is a good approximation).
 535         */
 536         {
 537                 const double diff = doubled_longprod - doubleprod;
 538                 const double absdiff = diff >= 0.0 ? diff : -diff;
 539                 const double absprod = doubleprod >= 0.0 ? doubleprod :
 540                                                           -doubleprod;
 541                 /* absdiff/absprod <= 1/32 iff
 542                    32 * absdiff <= absprod -- 5 good bits is "close enough" */
 543                 if (32.0 * absdiff <= absprod)
 544                         return PyInt_FromLong(longprod);
 545                 else
 546                         return PyLong_Type.tp_as_number->nb_multiply(v, w);
 547         }
 548 }
 549
 550 /* Integer overflow checking for unary negation: on a 2's-complement
 551  * box, -x overflows iff x is the most negative long.  In this case we
 552  * get -x == x.  However, -x is undefined (by C) if x /is/ the most
 553  * negative long (it's a signed overflow case), and some compilers care.
 554  * So we cast x to unsigned long first.  However, then other compilers
 555  * warn about applying unary minus to an unsigned operand.  Hence the
 556  * weird "0-".
 557  */
 558 #define UNARY_NEG_WOULD_OVERFLOW(x)     \
 559         ((x) < 0 && (unsigned long)(x) == 0-(unsigned long)(x))
 560
 561 /* Return type of i_divmod */
 562 enum divmod_result {
 563         DIVMOD_OK,              /* Correct result */
 564         DIVMOD_OVERFLOW,        /* Overflow, try again using longs */
 565         DIVMOD_ERROR            /* Exception raised */
 566 };
 567
 568 static enum divmod_result
 569 i_divmod(register long x, register long y,
 570          long *p_xdivy, long *p_xmody)
 571 {
 572         long xdivy, xmody;
 573
 574         if (y == 0) {
 575                 PyErr_SetString(PyExc_ZeroDivisionError,
 576                                 "integer division or modulo by zero");
 577                 return DIVMOD_ERROR;
 578         }
 579         /* (-sys.maxint-1)/-1 is the only overflow case. */
 580         if (y == -1 && UNARY_NEG_WOULD_OVERFLOW(x))
 581                 return DIVMOD_OVERFLOW;
 582         xdivy = x / y;
 583         xmody = x - xdivy * y;
 584         /* If the signs of x and y differ, and the remainder is non-0,
 585          * C89 doesn't define whether xdivy is now the floor or the
 586          * ceiling of the infinitely precise quotient.  We want the floor,
 587          * and we have it iff the remainder's sign matches y's.
 588          */
 589         if (xmody && ((y ^ xmody) < 0) /* i.e. and signs differ */) {
 590                 xmody += y;
 591                 --xdivy;
 592                 assert(xmody && ((y ^ xmody) >= 0));
 593         }
 594         *p_xdivy = xdivy;
 595         *p_xmody = xmody;
 596         return DIVMOD_OK;
 597 }
 598
 599 static PyObject *
 600 int_div(PyIntObject *x, PyIntObject *y)
 601 {
 602         long xi, yi;
 603         long d, m;
 604         CONVERT_TO_LONG(x, xi);
 605         CONVERT_TO_LONG(y, yi);
 606         switch (i_divmod(xi, yi, &d, &m)) {
 607         case DIVMOD_OK:
 608                 return PyInt_FromLong(d);
 609         case DIVMOD_OVERFLOW:
 610                 return PyLong_Type.tp_as_number->nb_divide((PyObject *)x,
 611                                                            (PyObject *)y);
 612         default:
 613                 return NULL;
 614         }
 615 }
 616
 617 static PyObject *
 618 int_classic_div(PyIntObject *x, PyIntObject *y)
 619 {
 620         long xi, yi;
 621         long d, m;
 622         CONVERT_TO_LONG(x, xi);
 623         CONVERT_TO_LONG(y, yi);
 624         if (Py_DivisionWarningFlag &&
 625             PyErr_Warn(PyExc_DeprecationWarning, "classic int division") < 0)
 626                 return NULL;
 627         switch (i_divmod(xi, yi, &d, &m)) {
 628         case DIVMOD_OK:
 629                 return PyInt_FromLong(d);
 630         case DIVMOD_OVERFLOW:
 631                 return PyLong_Type.tp_as_number->nb_divide((PyObject *)x,
 632                                                            (PyObject *)y);
 633         default:
 634                 return NULL;
 635         }
 636 }
 637
 638 static PyObject *
 639 int_true_divide(PyObject *v, PyObject *w)
 640 {
 641         /* If they aren't both ints, give someone else a chance.  In
 642            particular, this lets int/long get handled by longs, which
 643            underflows to 0 gracefully if the long is too big to convert
 644            to float. */
 645         if (PyInt_Check(v) && PyInt_Check(w))
 646                 return PyFloat_Type.tp_as_number->nb_true_divide(v, w);
 647         Py_INCREF(Py_NotImplemented);
 648         return Py_NotImplemented;
 649 }
 650
 651 static PyObject *
 652 int_mod(PyIntObject *x, PyIntObject *y)
 653 {
 654         long xi, yi;
 655         long d, m;
 656         CONVERT_TO_LONG(x, xi);
 657         CONVERT_TO_LONG(y, yi);
 658         switch (i_divmod(xi, yi, &d, &m)) {
 659         case DIVMOD_OK:
 660                 return PyInt_FromLong(m);
 661         case DIVMOD_OVERFLOW:
 662                 return PyLong_Type.tp_as_number->nb_remainder((PyObject *)x,
 663                                                               (PyObject *)y);
 664         default:
 665                 return NULL;
 666         }
 667 }
 668
 669 static PyObject *
 670 int_divmod(PyIntObject *x, PyIntObject *y)
 671 {
 672         long xi, yi;
 673         long d, m;
 674         CONVERT_TO_LONG(x, xi);
 675         CONVERT_TO_LONG(y, yi);
 676         switch (i_divmod(xi, yi, &d, &m)) {
 677         case DIVMOD_OK:
 678                 return Py_BuildValue("(ll)", d, m);
 679         case DIVMOD_OVERFLOW:
 680                 return PyLong_Type.tp_as_number->nb_divmod((PyObject *)x,
 681                                                            (PyObject *)y);
 682         default:
 683                 return NULL;
 684         }
 685 }
 686
 687 static PyObject *
 688 int_pow(PyIntObject *v, PyIntObject *w, PyIntObject *z)
 689 {
 690         register long iv, iw, iz=0, ix, temp, prev;
 691         CONVERT_TO_LONG(v, iv);
 692         CONVERT_TO_LONG(w, iw);
 693         if (iw < 0) {
 694                 if ((PyObject *)z != Py_None) {
 695                         PyErr_SetString(PyExc_TypeError, "pow() 2nd argument "
 696                              "cannot be negative when 3rd argument specified");
 697                         return NULL;
 698                 }
 699                 /* Return a float.  This works because we know that
 700                    this calls float_pow() which converts its
 701                    arguments to double. */
 702                 return PyFloat_Type.tp_as_number->nb_power(
 703                         (PyObject *)v, (PyObject *)w, (PyObject *)z);
 704         }
 705         if ((PyObject *)z != Py_None) {
 706                 CONVERT_TO_LONG(z, iz);
 707                 if (iz == 0) {
 708                         PyErr_SetString(PyExc_ValueError,
 709                                         "pow() 3rd argument cannot be 0");
 710                         return NULL;
 711                 }
 712         }
 713         /*
 714          * XXX: The original exponentiation code stopped looping
 715          * when temp hit zero; this code will continue onwards
 716          * unnecessarily, but at least it won't cause any errors.
 717          * Hopefully the speed improvement from the fast exponentiation
 718          * will compensate for the slight inefficiency.
 719          * XXX: Better handling of overflows is desperately needed.
 720          */
 721         temp = iv;
 722         ix = 1;
 723         while (iw > 0) {
 724                 prev = ix;      /* Save value for overflow check */
 725                 if (iw & 1) {
 726                         ix = ix*temp;
 727                         if (temp == 0)
 728                                 break; /* Avoid ix / 0 */
 729                         if (ix / temp != prev) {
 730                                 return PyLong_Type.tp_as_number->nb_power(
 731                                         (PyObject *)v,
 732                                         (PyObject *)w,
 733                                         (PyObject *)z);
 734                         }
 735                 }
 736                 iw >>= 1;       /* Shift exponent down by 1 bit */
 737                 if (iw==0) break;
 738                 prev = temp;
 739                 temp *= temp;   /* Square the value of temp */
 740                 if (prev != 0 && temp / prev != prev) {
 741                         return PyLong_Type.tp_as_number->nb_power(
 742                                 (PyObject *)v, (PyObject *)w, (PyObject *)z);
 743                 }
 744                 if (iz) {
 745                         /* If we did a multiplication, perform a modulo */
 746                         ix = ix % iz;
 747                         temp = temp % iz;
 748                 }
 749         }
 750         if (iz) {
 751                 long div, mod;
 752                 switch (i_divmod(ix, iz, &div, &mod)) {
 753                 case DIVMOD_OK:
 754                         ix = mod;
 755                         break;
 756                 case DIVMOD_OVERFLOW:
 757                         return PyLong_Type.tp_as_number->nb_power(
 758                                 (PyObject *)v, (PyObject *)w, (PyObject *)z);
 759                 default:
 760                         return NULL;
 761                 }
 762         }
 763         return PyInt_FromLong(ix);
 764 }
 765
 766 static PyObject *
 767 int_neg(PyIntObject *v)
 768 {
 769         register long a;
 770         a = v->ob_ival;
 771         /* check for overflow */
 772         if (UNARY_NEG_WOULD_OVERFLOW(a)) {
 773                 PyObject *o = PyLong_FromLong(a);
 774                 if (o != NULL) {
 775                         PyObject *result = PyNumber_Negative(o);
 776                         Py_DECREF(o);
 777                         return result;
 778                 }
 779                 return NULL;
 780         }
 781         return PyInt_FromLong(-a);
 782 }
 783
 784 static PyObject *
 785 int_abs(PyIntObject *v)
 786 {
 787         if (v->ob_ival >= 0)
 788                 return int_int(v);
 789         else
 790                 return int_neg(v);
 791 }
 792
 793 static int
 794 int_nonzero(PyIntObject *v)
 795 {
 796         return v->ob_ival != 0;
 797 }
 798
 799 static PyObject *
 800 int_invert(PyIntObject *v)
 801 {
 802         return PyInt_FromLong(~v->ob_ival);
 803 }
 804
 805 static PyObject *
 806 int_lshift(PyIntObject *v, PyIntObject *w)
 807 {
 808         long a, b, c;
 809         PyObject *vv, *ww, *result;
 810
 811         CONVERT_TO_LONG(v, a);
 812         CONVERT_TO_LONG(w, b);
 813         if (b < 0) {
 814                 PyErr_SetString(PyExc_ValueError, "negative shift count");
 815                 return NULL;
 816         }
 817         if (a == 0 || b == 0)
 818                 return int_int(v);
 819         if (b >= LONG_BIT) {
 820                 vv = PyLong_FromLong(PyInt_AS_LONG(v));
 821                 if (vv == NULL)
 822                         return NULL;
 823                 ww = PyLong_FromLong(PyInt_AS_LONG(w));
 824                 if (ww == NULL) {
 825                         Py_DECREF(vv);
 826                         return NULL;
 827                 }
 828                 result = PyNumber_Lshift(vv, ww);
 829                 Py_DECREF(vv);
 830                 Py_DECREF(ww);
 831                 return result;
 832         }
 833         c = a << b;
 834         if (a != Py_ARITHMETIC_RIGHT_SHIFT(long, c, b)) {
 835                 vv = PyLong_FromLong(PyInt_AS_LONG(v));
 836                 if (vv == NULL)
 837                         return NULL;
 838                 ww = PyLong_FromLong(PyInt_AS_LONG(w));
 839                 if (ww == NULL) {
 840                         Py_DECREF(vv);
 841                         return NULL;
 842                 }
 843                 result = PyNumber_Lshift(vv, ww);
 844                 Py_DECREF(vv);
 845                 Py_DECREF(ww);
 846                 return result;
 847         }
 848         return PyInt_FromLong(c);
 849 }
 850
 851 static PyObject *
 852 int_rshift(PyIntObject *v, PyIntObject *w)
 853 {
 854         register long a, b;
 855         CONVERT_TO_LONG(v, a);
 856         CONVERT_TO_LONG(w, b);
 857         if (b < 0) {
 858                 PyErr_SetString(PyExc_ValueError, "negative shift count");
 859                 return NULL;
 860         }
 861         if (a == 0 || b == 0)
 862                 return int_int(v);
 863         if (b >= LONG_BIT) {
 864                 if (a < 0)
 865                         a = -1;
 866                 else
 867                         a = 0;
 868         }
 869         else {
 870                 a = Py_ARITHMETIC_RIGHT_SHIFT(long, a, b);
 871         }
 872         return PyInt_FromLong(a);
 873 }
 874
 875 static PyObject *
 876 int_and(PyIntObject *v, PyIntObject *w)
 877 {
 878         register long a, b;
 879         CONVERT_TO_LONG(v, a);
 880         CONVERT_TO_LONG(w, b);
 881         return PyInt_FromLong(a & b);
 882 }
 883
 884 static PyObject *
 885 int_xor(PyIntObject *v, PyIntObject *w)
 886 {
 887         register long a, b;
 888         CONVERT_TO_LONG(v, a);
 889         CONVERT_TO_LONG(w, b);
 890         return PyInt_FromLong(a ^ b);
 891 }
 892
 893 static PyObject *
 894 int_or(PyIntObject *v, PyIntObject *w)
 895 {
 896         register long a, b;
 897         CONVERT_TO_LONG(v, a);
 898         CONVERT_TO_LONG(w, b);
 899         return PyInt_FromLong(a | b);
 900 }
 901
 902 static int
 903 int_coerce(PyObject **pv, PyObject **pw)
 904 {
 905         if (PyInt_Check(*pw)) {
 906                 Py_INCREF(*pv);
 907                 Py_INCREF(*pw);
 908                 return 0;
 909         }
 910         return 1; /* Can't do it */
 911 }
 912
 913 static PyObject *
 914 int_int(PyIntObject *v)
 915 {
 916         if (PyInt_CheckExact(v))
 917                 Py_INCREF(v);
 918         else
 919                 v = (PyIntObject *)PyInt_FromLong(v->ob_ival);
 920         return (PyObject *)v;
 921 }
 922
 923 static PyObject *
 924 int_long(PyIntObject *v)
 925 {
 926         return PyLong_FromLong((v -> ob_ival));
 927 }
 928
 929 static const unsigned char BitLengthTable[32] = {
 930         0, 1, 2, 2, 3, 3, 3, 3, 4, 4, 4, 4, 4, 4, 4, 4,
 931         5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5
 932 };
 933
 934 static int
 935 bits_in_ulong(unsigned long d)
 936 {
 937         int d_bits = 0;
 938         while (d >= 32) {
 939                 d_bits += 6;
 940                 d >>= 6;
 941         }
 942         d_bits += (int)BitLengthTable[d];
 943         return d_bits;
 944 }
 945
 946 #if 8*SIZEOF_LONG-1 <= DBL_MANT_DIG
 947 /* Every Python int can be exactly represented as a float. */
 948
 949 static PyObject *
 950 int_float(PyIntObject *v)
 951 {
 952         return PyFloat_FromDouble((double)(v -> ob_ival));
 953 }
 954
 955 #else
 956 /* Here not all Python ints are exactly representable as floats, so we may
 957    have to round.  We do this manually, since the C standards don't specify
 958    whether converting an integer to a float rounds up or down */
 959
 960 static PyObject *
 961 int_float(PyIntObject *v)
 962 {
 963         unsigned long abs_ival, lsb;
 964         int round_up;
 965
 966         if (v->ob_ival < 0)
 967                 abs_ival = 0U-(unsigned long)v->ob_ival;
 968         else
 969                 abs_ival = (unsigned long)v->ob_ival;
 970         if (abs_ival < (1L << DBL_MANT_DIG))
 971                 /* small integer;  no need to round */
 972                 return PyFloat_FromDouble((double)v->ob_ival);
 973
 974         /* Round abs_ival to MANT_DIG significant bits, using the
 975            round-half-to-even rule.  abs_ival & lsb picks out the 'rounding'
 976            bit: the first bit after the most significant MANT_DIG bits of
 977            abs_ival.  We round up if this bit is set, provided that either:
 978
 979              (1) abs_ival isn't exactly halfway between two floats, in which
 980              case at least one of the bits following the rounding bit must be
 981              set; i.e., abs_ival & lsb-1 != 0, or:
 982
 983              (2) the resulting rounded value has least significant bit 0; or
 984              in other words the bit above the rounding bit is set (this is the
 985              'to-even' bit of round-half-to-even); i.e., abs_ival & 2*lsb != 0
 986
 987            The condition "(1) or (2)" equates to abs_ival & 3*lsb-1 != 0. */
 988
 989         lsb = 1L << (bits_in_ulong(abs_ival)-DBL_MANT_DIG-1);
 990         round_up = (abs_ival & lsb) && (abs_ival & (3*lsb-1));
 991         abs_ival &= -2*lsb;
 992         if (round_up)
 993                 abs_ival += 2*lsb;
 994         return PyFloat_FromDouble(v->ob_ival < 0 ?
 995                                   -(double)abs_ival :
 996                                   (double)abs_ival);
 997 }
 998
 999 #endif
1000
1001 static PyObject *
1002 int_oct(PyIntObject *v)
1003 {
1004         return _PyInt_Format(v, 8, 0);
1005 }
1006
1007 static PyObject *
1008 int_hex(PyIntObject *v)
1009 {
1010         return _PyInt_Format(v, 16, 0);
1011 }
1012
1013 static PyObject *
1014 int_subtype_new(PyTypeObject *type, PyObject *args, PyObject *kwds);
1015
1016 static PyObject *
1017 int_new(PyTypeObject *type, PyObject *args, PyObject *kwds)
1018 {
1019         PyObject *x = NULL;
1020         int base = -909;
1021         static char *kwlist[] = {"x", "base", 0};
1022
1023         if (type != &PyInt_Type)
1024                 return int_subtype_new(type, args, kwds); /* Wimp out */
1025         if (!PyArg_ParseTupleAndKeywords(args, kwds, "|Oi:int", kwlist,
1026                                          &x, &base))
1027                 return NULL;
1028         if (x == NULL)
1029                 return PyInt_FromLong(0L);
1030         if (base == -909)
1031                 return PyNumber_Int(x);
1032         if (PyString_Check(x)) {
1033                 /* Since PyInt_FromString doesn't have a length parameter,
1034                  * check here for possible NULs in the string. */
1035                 char *string = PyString_AS_STRING(x);
1036                 if (strlen(string) != PyString_Size(x)) {
1037                         /* create a repr() of the input string,
1038                          * just like PyInt_FromString does */
1039                         PyObject *srepr;
1040                         srepr = PyObject_Repr(x);
1041                         if (srepr == NULL)
1042                                 return NULL;
1043                         PyErr_Format(PyExc_ValueError,
1044                              "invalid literal for int() with base %d: %s",
1045                              base, PyString_AS_STRING(srepr));
1046                         Py_DECREF(srepr);
1047                         return NULL;
1048                 }
1049                 return PyInt_FromString(string, NULL, base);
1050         }
1051 #ifdef Py_USING_UNICODE
1052         if (PyUnicode_Check(x))
1053                 return PyInt_FromUnicode(PyUnicode_AS_UNICODE(x),
1054                                          PyUnicode_GET_SIZE(x),
1055                                          base);
1056 #endif
1057         PyErr_SetString(PyExc_TypeError,
1058                         "int() can't convert non-string with explicit base");
1059         return NULL;
1060 }
1061
1062 /* Wimpy, slow approach to tp_new calls for subtypes of int:
1063    first create a regular int from whatever arguments we got,
1064    then allocate a subtype instance and initialize its ob_ival
1065    from the regular int.  The regular int is then thrown away.
1066 */
1067 static PyObject *
1068 int_subtype_new(PyTypeObject *type, PyObject *args, PyObject *kwds)
1069 {
1070         PyObject *tmp, *newobj;
1071         long ival;
1072
1073         assert(PyType_IsSubtype(type, &PyInt_Type));
1074         tmp = int_new(&PyInt_Type, args, kwds);
1075         if (tmp == NULL)
1076                 return NULL;
1077         if (!PyInt_Check(tmp)) {
1078                 ival = PyLong_AsLong(tmp);
1079                 if (ival == -1 && PyErr_Occurred()) {
1080                         Py_DECREF(tmp);
1081                         return NULL;
1082                 }
1083         } else {
1084                 ival = ((PyIntObject *)tmp)->ob_ival;
1085         }
1086
1087         newobj = type->tp_alloc(type, 0);
1088         if (newobj == NULL) {
1089                 Py_DECREF(tmp);
1090                 return NULL;
1091         }
1092         ((PyIntObject *)newobj)->ob_ival = ival;
1093         Py_DECREF(tmp);
1094         return newobj;
1095 }
1096
1097 static PyObject *
1098 int_getnewargs(PyIntObject *v)
1099 {
1100         return Py_BuildValue("(l)", v->ob_ival);
1101 }
1102
1103 static PyObject *
1104 int_get0(PyIntObject *v, void *context) {
1105         return PyInt_FromLong(0L);
1106 }
1107
1108 static PyObject *
1109 int_get1(PyIntObject *v, void *context) {
1110         return PyInt_FromLong(1L);
1111 }
1112
1113 /* Convert an integer to a decimal string.  On many platforms, this
1114    will be significantly faster than the general arbitrary-base
1115    conversion machinery in _PyInt_Format, thanks to optimization
1116    opportunities offered by division by a compile-time constant. */
1117 static PyObject *
1118 int_to_decimal_string(PyIntObject *v) {
1119         char buf[sizeof(long)*CHAR_BIT/3+6], *p, *bufend;
1120         long n = v->ob_ival;
1121         unsigned long absn;
1122         p = bufend = buf + sizeof(buf);
1123         absn = n < 0 ? 0UL - n : n;
1124         do {
1125                 *--p = '0' + absn % 10;
1126                 absn /= 10;
1127         } while (absn);
1128         if (n < 0)
1129                 *--p = '-';
1130         return PyString_FromStringAndSize(p, bufend - p);
1131 }
1132
1133 /* Convert an integer to the given base.  Returns a string.
1134    If base is 2, 8 or 16, add the proper prefix '0b', '0o' or '0x'.
1135    If newstyle is zero, then use the pre-2.6 behavior of octal having
1136    a leading "0" */
1137 PyAPI_FUNC(PyObject*)
1138 _PyInt_Format(PyIntObject *v, int base, int newstyle)
1139 {
1140         /* There are no doubt many, many ways to optimize this, using code
1141            similar to _PyLong_Format */
1142         long n = v->ob_ival;
1143         int  negative = n < 0;
1144         int is_zero = n == 0;
1145
1146         /* For the reasoning behind this size, see
1147            http://c-faq.com/misc/hexio.html. Then, add a few bytes for
1148            the possible sign and prefix "0[box]" */
1149         char buf[sizeof(n)*CHAR_BIT+6];
1150
1151         /* Start by pointing to the end of the buffer.  We fill in from
1152            the back forward. */
1153         char* p = &buf[sizeof(buf)];
1154
1155         assert(base >= 2 && base <= 36);
1156
1157         /* Special case base 10, for speed */
1158         if (base == 10)
1159                 return int_to_decimal_string(v);
1160
1161         do {
1162                 /* I'd use i_divmod, except it doesn't produce the results
1163                    I want when n is negative.  So just duplicate the salient
1164                    part here. */
1165                 long div = n / base;
1166                 long mod = n - div * base;
1167
1168                 /* convert abs(mod) to the right character in [0-9, a-z] */
1169                 char cdigit = (char)(mod < 0 ? -mod : mod);
1170                 cdigit += (cdigit < 10) ? '0' : 'a'-10;
1171                 *--p = cdigit;
1172
1173                 n = div;
1174         } while(n);
1175
1176         if (base == 2) {
1177                 *--p = 'b';
1178                 *--p = '0';
1179         }
1180         else if (base == 8) {
1181                 if (newstyle) {
1182                         *--p = 'o';
1183                         *--p = '0';
1184                 }
1185                 else
1186                         if (!is_zero)
1187                                 *--p = '0';
1188         }
1189         else if (base == 16) {
1190                 *--p = 'x';
1191                 *--p = '0';
1192         }
1193         else {
1194                 *--p = '#';
1195                 *--p = '0' + base%10;
1196                 if (base > 10)
1197                         *--p = '0' + base/10;
1198         }
1199         if (negative)
1200                 *--p = '-';
1201
1202         return PyString_FromStringAndSize(p, &buf[sizeof(buf)] - p);
1203 }
1204
1205 static PyObject *
1206 int__format__(PyObject *self, PyObject *args)
1207 {
1208         PyObject *format_spec;
1209
1210         if (!PyArg_ParseTuple(args, "O:__format__", &format_spec))
1211                 return NULL;
1212         if (PyBytes_Check(format_spec))
1213                 return _PyInt_FormatAdvanced(self,
1214                                              PyBytes_AS_STRING(format_spec),
1215                                              PyBytes_GET_SIZE(format_spec));
1216         if (PyUnicode_Check(format_spec)) {
1217                 /* Convert format_spec to a str */
1218                 PyObject *result;
1219                 PyObject *str_spec = PyObject_Str(format_spec);
1220
1221                 if (str_spec == NULL)
1222                         return NULL;
1223
1224                 result = _PyInt_FormatAdvanced(self,
1225                                                PyBytes_AS_STRING(str_spec),
1226                                                PyBytes_GET_SIZE(str_spec));
1227
1228                 Py_DECREF(str_spec);
1229                 return result;
1230         }
1231         PyErr_SetString(PyExc_TypeError, "__format__ requires str or unicode");
1232         return NULL;
1233 }
1234
1235 static PyObject *
1236 int_bit_length(PyIntObject *v)
1237 {
1238         unsigned long n;
1239
1240         if (v->ob_ival < 0)
1241                 /* avoid undefined behaviour when v->ob_ival == -LONG_MAX-1 */
1242                 n = 0U-(unsigned long)v->ob_ival;
1243         else
1244                 n = (unsigned long)v->ob_ival;
1245
1246         return PyInt_FromLong(bits_in_ulong(n));
1247 }
1248
1249 PyDoc_STRVAR(int_bit_length_doc,
1250 "int.bit_length() -> int\n\
1251 \n\
1252 Number of bits necessary to represent self in binary.\n\
1253 >>> bin(37)\n\
1254 '0b100101'\n\
1255 >>> (37).bit_length()\n\
1256 6");
1257
1258 #if 0
1259 static PyObject *
1260 int_is_finite(PyObject *v)
1261 {
1262         Py_RETURN_TRUE;
1263 }
1264 #endif
1265
1266 static PyMethodDef int_methods[] = {
1267         {"conjugate",   (PyCFunction)int_int,   METH_NOARGS,
1268          "Returns self, the complex conjugate of any int."},
1269         {"bit_length", (PyCFunction)int_bit_length, METH_NOARGS,
1270          int_bit_length_doc},
1271 #if 0
1272         {"is_finite",   (PyCFunction)int_is_finite,     METH_NOARGS,
1273          "Returns always True."},
1274 #endif
1275         {"__trunc__",   (PyCFunction)int_int,   METH_NOARGS,
1276          "Truncating an Integral returns itself."},
1277         {"__getnewargs__",      (PyCFunction)int_getnewargs,    METH_NOARGS},
1278         {"__format__", (PyCFunction)int__format__, METH_VARARGS},
1279         {NULL,          NULL}           /* sentinel */
1280 };
1281
1282 static PyGetSetDef int_getset[] = {
1283         {"real",
1284          (getter)int_int, (setter)NULL,
1285          "the real part of a complex number",
1286          NULL},
1287         {"imag",
1288          (getter)int_get0, (setter)NULL,
1289          "the imaginary part of a complex number",
1290          NULL},
1291         {"numerator",
1292          (getter)int_int, (setter)NULL,
1293          "the numerator of a rational number in lowest terms",
1294          NULL},
1295         {"denominator",
1296          (getter)int_get1, (setter)NULL,
1297          "the denominator of a rational number in lowest terms",
1298          NULL},
1299         {NULL}  /* Sentinel */
1300 };
1301
1302 PyDoc_STRVAR(int_doc,
1303 "int(x[, base]) -> integer\n\
1304 \n\
1305 Convert a string or number to an integer, if possible.  A floating point\n\
1306 argument will be truncated towards zero (this does not include a string\n\
1307 representation of a floating point number!)  When converting a string, use\n\
1308 the optional base.  It is an error to supply a base when converting a\n\
1309 non-string.  If base is zero, the proper base is guessed based on the\n\
1310 string content.  If the argument is outside the integer range a\n\
1311 long object will be returned instead.");
1312
1313 static PyNumberMethods int_as_number = {
1314         (binaryfunc)int_add,    /*nb_add*/
1315         (binaryfunc)int_sub,    /*nb_subtract*/
1316         (binaryfunc)int_mul,    /*nb_multiply*/
1317         (binaryfunc)int_classic_div, /*nb_divide*/
1318         (binaryfunc)int_mod,    /*nb_remainder*/
1319         (binaryfunc)int_divmod, /*nb_divmod*/
1320         (ternaryfunc)int_pow,   /*nb_power*/
1321         (unaryfunc)int_neg,     /*nb_negative*/
1322         (unaryfunc)int_int,     /*nb_positive*/
1323         (unaryfunc)int_abs,     /*nb_absolute*/
1324         (inquiry)int_nonzero,   /*nb_nonzero*/
1325         (unaryfunc)int_invert,  /*nb_invert*/
1326         (binaryfunc)int_lshift, /*nb_lshift*/
1327         (binaryfunc)int_rshift, /*nb_rshift*/
1328         (binaryfunc)int_and,    /*nb_and*/
1329         (binaryfunc)int_xor,    /*nb_xor*/
1330         (binaryfunc)int_or,     /*nb_or*/
1331         int_coerce,             /*nb_coerce*/
1332         (unaryfunc)int_int,     /*nb_int*/
1333         (unaryfunc)int_long,    /*nb_long*/
1334         (unaryfunc)int_float,   /*nb_float*/
1335         (unaryfunc)int_oct,     /*nb_oct*/
1336         (unaryfunc)int_hex,     /*nb_hex*/
1337         0,                      /*nb_inplace_add*/
1338         0,                      /*nb_inplace_subtract*/
1339         0,                      /*nb_inplace_multiply*/
1340         0,                      /*nb_inplace_divide*/
1341         0,                      /*nb_inplace_remainder*/
1342         0,                      /*nb_inplace_power*/
1343         0,                      /*nb_inplace_lshift*/
1344         0,                      /*nb_inplace_rshift*/
1345         0,                      /*nb_inplace_and*/
1346         0,                      /*nb_inplace_xor*/
1347         0,                      /*nb_inplace_or*/
1348         (binaryfunc)int_div,    /* nb_floor_divide */
1349         int_true_divide,        /* nb_true_divide */
1350         0,                      /* nb_inplace_floor_divide */
1351         0,                      /* nb_inplace_true_divide */
1352         (unaryfunc)int_int,     /* nb_index */
1353 };
1354
1355 PyTypeObject PyInt_Type = {
1356         PyVarObject_HEAD_INIT(&PyType_Type, 0)
1357         "int",
1358         sizeof(PyIntObject),
1359         0,
1360         (destructor)int_dealloc,                /* tp_dealloc */
1361         (printfunc)int_print,                   /* tp_print */
1362         0,                                      /* tp_getattr */
1363         0,                                      /* tp_setattr */
1364         (cmpfunc)int_compare,                   /* tp_compare */
1365         (reprfunc)int_to_decimal_string,        /* tp_repr */
1366         &int_as_number,                         /* tp_as_number */
1367         0,                                      /* tp_as_sequence */
1368         0,                                      /* tp_as_mapping */
1369         (hashfunc)int_hash,                     /* tp_hash */
1370         0,                                      /* tp_call */
1371         (reprfunc)int_to_decimal_string,        /* tp_str */
1372         PyObject_GenericGetAttr,                /* tp_getattro */
1373         0,                                      /* tp_setattro */
1374         0,                                      /* tp_as_buffer */
1375         Py_TPFLAGS_DEFAULT | Py_TPFLAGS_CHECKTYPES |
1376                 Py_TPFLAGS_BASETYPE | Py_TPFLAGS_INT_SUBCLASS,  /* tp_flags */
1377         int_doc,                                /* tp_doc */
1378         0,                                      /* tp_traverse */
1379         0,                                      /* tp_clear */
1380         0,                                      /* tp_richcompare */
1381         0,                                      /* tp_weaklistoffset */
1382         0,                                      /* tp_iter */
1383         0,                                      /* tp_iternext */
1384         int_methods,                            /* tp_methods */
1385         0,                                      /* tp_members */
1386         int_getset,                             /* tp_getset */
1387         0,                                      /* tp_base */
1388         0,                                      /* tp_dict */
1389         0,                                      /* tp_descr_get */
1390         0,                                      /* tp_descr_set */
1391         0,                                      /* tp_dictoffset */
1392         0,                                      /* tp_init */
1393         0,                                      /* tp_alloc */
1394         int_new,                                /* tp_new */
1395         (freefunc)int_free,                     /* tp_free */
1396 };
1397
1398 int
1399 _PyInt_Init(void)
1400 {
1401         PyIntObject *v;
1402         int ival;
1403 #if NSMALLNEGINTS + NSMALLPOSINTS > 0
1404         for (ival = -NSMALLNEGINTS; ival < NSMALLPOSINTS; ival++) {
1405               if (!free_list && (free_list = fill_free_list()) == NULL)
1406                         return 0;
1407                 /* PyObject_New is inlined */
1408                 v = free_list;
1409                 free_list = (PyIntObject *)Py_TYPE(v);
1410                 PyObject_INIT(v, &PyInt_Type);
1411                 v->ob_ival = ival;
1412                 small_ints[ival + NSMALLNEGINTS] = v;
1413         }
1414 #endif
1415         return 1;
1416 }
1417
1418 int
1419 PyInt_ClearFreeList(void)
1420 {
1421         PyIntObject *p;
1422         PyIntBlock *list, *next;
1423         int i;
1424         int u;                  /* remaining unfreed ints per block */
1425         int freelist_size = 0;
1426
1427         list = block_list;
1428         block_list = NULL;
1429         free_list = NULL;
1430         while (list != NULL) {
1431                 u = 0;
1432                 for (i = 0, p = &list->objects[0];
1433                      i < N_INTOBJECTS;
1434                      i++, p++) {
1435                         if (PyInt_CheckExact(p) && p->ob_refcnt != 0)
1436                                 u++;
1437                 }
1438                 next = list->next;
1439                 if (u) {
1440                         list->next = block_list;
1441                         block_list = list;
1442                         for (i = 0, p = &list->objects[0];
1443                              i < N_INTOBJECTS;
1444                              i++, p++) {
1445                                 if (!PyInt_CheckExact(p) ||
1446                                     p->ob_refcnt == 0) {
1447                                         Py_TYPE(p) = (struct _typeobject *)
1448                                                 free_list;
1449                                         free_list = p;
1450                                 }
1451 #if NSMALLNEGINTS + NSMALLPOSINTS > 0
1452                                 else if (-NSMALLNEGINTS <= p->ob_ival &&
1453                                          p->ob_ival < NSMALLPOSINTS &&
1454                                          small_ints[p->ob_ival +
1455                                                     NSMALLNEGINTS] == NULL) {
1456                                         Py_INCREF(p);
1457                                         small_ints[p->ob_ival +
1458                                                    NSMALLNEGINTS] = p;
1459                                 }
1460 #endif
1461                         }
1462                 }
1463                 else {
1464                         PyMem_FREE(list);
1465                 }
1466                 freelist_size += u;
1467                 list = next;
1468         }
1469
1470         return freelist_size;
1471 }
1472
1473 void
1474 PyInt_Fini(void)
1475 {
1476         PyIntObject *p;
1477         PyIntBlock *list;
1478         int i;
1479         int u;                  /* total unfreed ints per block */
1480
1481 #if NSMALLNEGINTS + NSMALLPOSINTS > 0
1482         PyIntObject **q;
1483
1484         i = NSMALLNEGINTS + NSMALLPOSINTS;
1485         q = small_ints;
1486         while (--i >= 0) {
1487                 Py_XDECREF(*q);
1488                 *q++ = NULL;
1489         }
1490 #endif
1491         u = PyInt_ClearFreeList();
1492         if (!Py_VerboseFlag)
1493                 return;
1494         fprintf(stderr, "# cleanup ints");
1495         if (!u) {
1496                 fprintf(stderr, "\n");
1497         }
1498         else {
1499                 fprintf(stderr,
1500                         ": %d unfreed int%s\n",
1501                         u, u == 1 ? "" : "s");
1502         }
1503         if (Py_VerboseFlag > 1) {
1504                 list = block_list;
1505                 while (list != NULL) {
1506                         for (i = 0, p = &list->objects[0];
1507                              i < N_INTOBJECTS;
1508                              i++, p++) {
1509                                 if (PyInt_CheckExact(p) && p->ob_refcnt != 0)
1510                                         /* XXX(twouters) cast refcount to
1511                                            long until %zd is universally
1512                                            available
1513                                          */
1514                                         fprintf(stderr,
1515                                 "#   <int at %p, refcnt=%ld, val=%ld>\n",
1516                                                 p, (long)p->ob_refcnt,
1517                                                 p->ob_ival);
1518                         }
1519                         list = list->next;
1520                 }
1521         }
1522 }