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 PyObject *
 440 int_repr(PyIntObject *v)
 441 {
 442         return _PyInt_Format(v, 10, 0);
 443 }
 444
 445 static int
 446 int_compare(PyIntObject *v, PyIntObject *w)
 447 {
 448         register long i = v->ob_ival;
 449         register long j = w->ob_ival;
 450         return (i < j) ? -1 : (i > j) ? 1 : 0;
 451 }
 452
 453 static long
 454 int_hash(PyIntObject *v)
 455 {
 456         /* XXX If this is changed, you also need to change the way
 457            Python's long, float and complex types are hashed. */
 458         long x = v -> ob_ival;
 459         if (x == -1)
 460                 x = -2;
 461         return x;
 462 }
 463
 464 static PyObject *
 465 int_add(PyIntObject *v, PyIntObject *w)
 466 {
 467         register long a, b, x;
 468         CONVERT_TO_LONG(v, a);
 469         CONVERT_TO_LONG(w, b);
 470         x = a + b;
 471         if ((x^a) >= 0 || (x^b) >= 0)
 472                 return PyInt_FromLong(x);
 473         return PyLong_Type.tp_as_number->nb_add((PyObject *)v, (PyObject *)w);
 474 }
 475
 476 static PyObject *
 477 int_sub(PyIntObject *v, PyIntObject *w)
 478 {
 479         register long a, b, x;
 480         CONVERT_TO_LONG(v, a);
 481         CONVERT_TO_LONG(w, b);
 482         x = a - b;
 483         if ((x^a) >= 0 || (x^~b) >= 0)
 484                 return PyInt_FromLong(x);
 485         return PyLong_Type.tp_as_number->nb_subtract((PyObject *)v,
 486                                                      (PyObject *)w);
 487 }
 488
 489 /*
 490 Integer overflow checking for * is painful:  Python tried a couple ways, but
 491 they didn't work on all platforms, or failed in endcases (a product of
 492 -sys.maxint-1 has been a particular pain).
 493
 494 Here's another way:
 495
 496 The native long product x*y is either exactly right or *way* off, being
 497 just the last n bits of the true product, where n is the number of bits
 498 in a long (the delivered product is the true product plus i*2**n for
 499 some integer i).
 500
 501 The native double product (double)x * (double)y is subject to three
 502 rounding errors:  on a sizeof(long)==8 box, each cast to double can lose
 503 info, and even on a sizeof(long)==4 box, the multiplication can lose info.
 504 But, unlike the native long product, it's not in *range* trouble:  even
 505 if sizeof(long)==32 (256-bit longs), the product easily fits in the
 506 dynamic range of a double.  So the leading 50 (or so) bits of the double
 507 product are correct.
 508
 509 We check these two ways against each other, and declare victory if they're
 510 approximately the same.  Else, because the native long product is the only
 511 one that can lose catastrophic amounts of information, it's the native long
 512 product that must have overflowed.
 513 */
 514
 515 static PyObject *
 516 int_mul(PyObject *v, PyObject *w)
 517 {
 518         long a, b;
 519         long longprod;                  /* a*b in native long arithmetic */
 520         double doubled_longprod;        /* (double)longprod */
 521         double doubleprod;              /* (double)a * (double)b */
 522
 523         CONVERT_TO_LONG(v, a);
 524         CONVERT_TO_LONG(w, b);
 525         longprod = a * b;
 526         doubleprod = (double)a * (double)b;
 527         doubled_longprod = (double)longprod;
 528
 529         /* Fast path for normal case:  small multiplicands, and no info
 530            is lost in either method. */
 531         if (doubled_longprod == doubleprod)
 532                 return PyInt_FromLong(longprod);
 533
 534         /* Somebody somewhere lost info.  Close enough, or way off?  Note
 535            that a != 0 and b != 0 (else doubled_longprod == doubleprod == 0).
 536            The difference either is or isn't significant compared to the
 537            true value (of which doubleprod is a good approximation).
 538         */
 539         {
 540                 const double diff = doubled_longprod - doubleprod;
 541                 const double absdiff = diff >= 0.0 ? diff : -diff;
 542                 const double absprod = doubleprod >= 0.0 ? doubleprod :
 543                                                           -doubleprod;
 544                 /* absdiff/absprod <= 1/32 iff
 545                    32 * absdiff <= absprod -- 5 good bits is "close enough" */
 546                 if (32.0 * absdiff <= absprod)
 547                         return PyInt_FromLong(longprod);
 548                 else
 549                         return PyLong_Type.tp_as_number->nb_multiply(v, w);
 550         }
 551 }
 552
 553 /* Integer overflow checking for unary negation: on a 2's-complement
 554  * box, -x overflows iff x is the most negative long.  In this case we
 555  * get -x == x.  However, -x is undefined (by C) if x /is/ the most
 556  * negative long (it's a signed overflow case), and some compilers care.
 557  * So we cast x to unsigned long first.  However, then other compilers
 558  * warn about applying unary minus to an unsigned operand.  Hence the
 559  * weird "0-".
 560  */
 561 #define UNARY_NEG_WOULD_OVERFLOW(x)     \
 562         ((x) < 0 && (unsigned long)(x) == 0-(unsigned long)(x))
 563
 564 /* Return type of i_divmod */
 565 enum divmod_result {
 566         DIVMOD_OK,              /* Correct result */
 567         DIVMOD_OVERFLOW,        /* Overflow, try again using longs */
 568         DIVMOD_ERROR            /* Exception raised */
 569 };
 570
 571 static enum divmod_result
 572 i_divmod(register long x, register long y,
 573          long *p_xdivy, long *p_xmody)
 574 {
 575         long xdivy, xmody;
 576
 577         if (y == 0) {
 578                 PyErr_SetString(PyExc_ZeroDivisionError,
 579                                 "integer division or modulo by zero");
 580                 return DIVMOD_ERROR;
 581         }
 582         /* (-sys.maxint-1)/-1 is the only overflow case. */
 583         if (y == -1 && UNARY_NEG_WOULD_OVERFLOW(x))
 584                 return DIVMOD_OVERFLOW;
 585         xdivy = x / y;
 586         xmody = x - xdivy * y;
 587         /* If the signs of x and y differ, and the remainder is non-0,
 588          * C89 doesn't define whether xdivy is now the floor or the
 589          * ceiling of the infinitely precise quotient.  We want the floor,
 590          * and we have it iff the remainder's sign matches y's.
 591          */
 592         if (xmody && ((y ^ xmody) < 0) /* i.e. and signs differ */) {
 593                 xmody += y;
 594                 --xdivy;
 595                 assert(xmody && ((y ^ xmody) >= 0));
 596         }
 597         *p_xdivy = xdivy;
 598         *p_xmody = xmody;
 599         return DIVMOD_OK;
 600 }
 601
 602 static PyObject *
 603 int_div(PyIntObject *x, PyIntObject *y)
 604 {
 605         long xi, yi;
 606         long d, m;
 607         CONVERT_TO_LONG(x, xi);
 608         CONVERT_TO_LONG(y, yi);
 609         switch (i_divmod(xi, yi, &d, &m)) {
 610         case DIVMOD_OK:
 611                 return PyInt_FromLong(d);
 612         case DIVMOD_OVERFLOW:
 613                 return PyLong_Type.tp_as_number->nb_divide((PyObject *)x,
 614                                                            (PyObject *)y);
 615         default:
 616                 return NULL;
 617         }
 618 }
 619
 620 static PyObject *
 621 int_classic_div(PyIntObject *x, PyIntObject *y)
 622 {
 623         long xi, yi;
 624         long d, m;
 625         CONVERT_TO_LONG(x, xi);
 626         CONVERT_TO_LONG(y, yi);
 627         if (Py_DivisionWarningFlag &&
 628             PyErr_Warn(PyExc_DeprecationWarning, "classic int division") < 0)
 629                 return NULL;
 630         switch (i_divmod(xi, yi, &d, &m)) {
 631         case DIVMOD_OK:
 632                 return PyInt_FromLong(d);
 633         case DIVMOD_OVERFLOW:
 634                 return PyLong_Type.tp_as_number->nb_divide((PyObject *)x,
 635                                                            (PyObject *)y);
 636         default:
 637                 return NULL;
 638         }
 639 }
 640
 641 static PyObject *
 642 int_true_divide(PyObject *v, PyObject *w)
 643 {
 644         /* If they aren't both ints, give someone else a chance.  In
 645            particular, this lets int/long get handled by longs, which
 646            underflows to 0 gracefully if the long is too big to convert
 647            to float. */
 648         if (PyInt_Check(v) && PyInt_Check(w))
 649                 return PyFloat_Type.tp_as_number->nb_true_divide(v, w);
 650         Py_INCREF(Py_NotImplemented);
 651         return Py_NotImplemented;
 652 }
 653
 654 static PyObject *
 655 int_mod(PyIntObject *x, PyIntObject *y)
 656 {
 657         long xi, yi;
 658         long d, m;
 659         CONVERT_TO_LONG(x, xi);
 660         CONVERT_TO_LONG(y, yi);
 661         switch (i_divmod(xi, yi, &d, &m)) {
 662         case DIVMOD_OK:
 663                 return PyInt_FromLong(m);
 664         case DIVMOD_OVERFLOW:
 665                 return PyLong_Type.tp_as_number->nb_remainder((PyObject *)x,
 666                                                               (PyObject *)y);
 667         default:
 668                 return NULL;
 669         }
 670 }
 671
 672 static PyObject *
 673 int_divmod(PyIntObject *x, PyIntObject *y)
 674 {
 675         long xi, yi;
 676         long d, m;
 677         CONVERT_TO_LONG(x, xi);
 678         CONVERT_TO_LONG(y, yi);
 679         switch (i_divmod(xi, yi, &d, &m)) {
 680         case DIVMOD_OK:
 681                 return Py_BuildValue("(ll)", d, m);
 682         case DIVMOD_OVERFLOW:
 683                 return PyLong_Type.tp_as_number->nb_divmod((PyObject *)x,
 684                                                            (PyObject *)y);
 685         default:
 686                 return NULL;
 687         }
 688 }
 689
 690 static PyObject *
 691 int_pow(PyIntObject *v, PyIntObject *w, PyIntObject *z)
 692 {
 693         register long iv, iw, iz=0, ix, temp, prev;
 694         CONVERT_TO_LONG(v, iv);
 695         CONVERT_TO_LONG(w, iw);
 696         if (iw < 0) {
 697                 if ((PyObject *)z != Py_None) {
 698                         PyErr_SetString(PyExc_TypeError, "pow() 2nd argument "
 699                              "cannot be negative when 3rd argument specified");
 700                         return NULL;
 701                 }
 702                 /* Return a float.  This works because we know that
 703                    this calls float_pow() which converts its
 704                    arguments to double. */
 705                 return PyFloat_Type.tp_as_number->nb_power(
 706                         (PyObject *)v, (PyObject *)w, (PyObject *)z);
 707         }
 708         if ((PyObject *)z != Py_None) {
 709                 CONVERT_TO_LONG(z, iz);
 710                 if (iz == 0) {
 711                         PyErr_SetString(PyExc_ValueError,
 712                                         "pow() 3rd argument cannot be 0");
 713                         return NULL;
 714                 }
 715         }
 716         /*
 717          * XXX: The original exponentiation code stopped looping
 718          * when temp hit zero; this code will continue onwards
 719          * unnecessarily, but at least it won't cause any errors.
 720          * Hopefully the speed improvement from the fast exponentiation
 721          * will compensate for the slight inefficiency.
 722          * XXX: Better handling of overflows is desperately needed.
 723          */
 724         temp = iv;
 725         ix = 1;
 726         while (iw > 0) {
 727                 prev = ix;      /* Save value for overflow check */
 728                 if (iw & 1) {
 729                         ix = ix*temp;
 730                         if (temp == 0)
 731                                 break; /* Avoid ix / 0 */
 732                         if (ix / temp != prev) {
 733                                 return PyLong_Type.tp_as_number->nb_power(
 734                                         (PyObject *)v,
 735                                         (PyObject *)w,
 736                                         (PyObject *)z);
 737                         }
 738                 }
 739                 iw >>= 1;       /* Shift exponent down by 1 bit */
 740                 if (iw==0) break;
 741                 prev = temp;
 742                 temp *= temp;   /* Square the value of temp */
 743                 if (prev != 0 && temp / prev != prev) {
 744                         return PyLong_Type.tp_as_number->nb_power(
 745                                 (PyObject *)v, (PyObject *)w, (PyObject *)z);
 746                 }
 747                 if (iz) {
 748                         /* If we did a multiplication, perform a modulo */
 749                         ix = ix % iz;
 750                         temp = temp % iz;
 751                 }
 752         }
 753         if (iz) {
 754                 long div, mod;
 755                 switch (i_divmod(ix, iz, &div, &mod)) {
 756                 case DIVMOD_OK:
 757                         ix = mod;
 758                         break;
 759                 case DIVMOD_OVERFLOW:
 760                         return PyLong_Type.tp_as_number->nb_power(
 761                                 (PyObject *)v, (PyObject *)w, (PyObject *)z);
 762                 default:
 763                         return NULL;
 764                 }
 765         }
 766         return PyInt_FromLong(ix);
 767 }
 768
 769 static PyObject *
 770 int_neg(PyIntObject *v)
 771 {
 772         register long a;
 773         a = v->ob_ival;
 774         /* check for overflow */
 775         if (UNARY_NEG_WOULD_OVERFLOW(a)) {
 776                 PyObject *o = PyLong_FromLong(a);
 777                 if (o != NULL) {
 778                         PyObject *result = PyNumber_Negative(o);
 779                         Py_DECREF(o);
 780                         return result;
 781                 }
 782                 return NULL;
 783         }
 784         return PyInt_FromLong(-a);
 785 }
 786
 787 static PyObject *
 788 int_abs(PyIntObject *v)
 789 {
 790         if (v->ob_ival >= 0)
 791                 return int_int(v);
 792         else
 793                 return int_neg(v);
 794 }
 795
 796 static int
 797 int_nonzero(PyIntObject *v)
 798 {
 799         return v->ob_ival != 0;
 800 }
 801
 802 static PyObject *
 803 int_invert(PyIntObject *v)
 804 {
 805         return PyInt_FromLong(~v->ob_ival);
 806 }
 807
 808 static PyObject *
 809 int_lshift(PyIntObject *v, PyIntObject *w)
 810 {
 811         long a, b, c;
 812         PyObject *vv, *ww, *result;
 813
 814         CONVERT_TO_LONG(v, a);
 815         CONVERT_TO_LONG(w, b);
 816         if (b < 0) {
 817                 PyErr_SetString(PyExc_ValueError, "negative shift count");
 818                 return NULL;
 819         }
 820         if (a == 0 || b == 0)
 821                 return int_int(v);
 822         if (b >= LONG_BIT) {
 823                 vv = PyLong_FromLong(PyInt_AS_LONG(v));
 824                 if (vv == NULL)
 825                         return NULL;
 826                 ww = PyLong_FromLong(PyInt_AS_LONG(w));
 827                 if (ww == NULL) {
 828                         Py_DECREF(vv);
 829                         return NULL;
 830                 }
 831                 result = PyNumber_Lshift(vv, ww);
 832                 Py_DECREF(vv);
 833                 Py_DECREF(ww);
 834                 return result;
 835         }
 836         c = a << b;
 837         if (a != Py_ARITHMETIC_RIGHT_SHIFT(long, c, b)) {
 838                 vv = PyLong_FromLong(PyInt_AS_LONG(v));
 839                 if (vv == NULL)
 840                         return NULL;
 841                 ww = PyLong_FromLong(PyInt_AS_LONG(w));
 842                 if (ww == NULL) {
 843                         Py_DECREF(vv);
 844                         return NULL;
 845                 }
 846                 result = PyNumber_Lshift(vv, ww);
 847                 Py_DECREF(vv);
 848                 Py_DECREF(ww);
 849                 return result;
 850         }
 851         return PyInt_FromLong(c);
 852 }
 853
 854 static PyObject *
 855 int_rshift(PyIntObject *v, PyIntObject *w)
 856 {
 857         register long a, b;
 858         CONVERT_TO_LONG(v, a);
 859         CONVERT_TO_LONG(w, b);
 860         if (b < 0) {
 861                 PyErr_SetString(PyExc_ValueError, "negative shift count");
 862                 return NULL;
 863         }
 864         if (a == 0 || b == 0)
 865                 return int_int(v);
 866         if (b >= LONG_BIT) {
 867                 if (a < 0)
 868                         a = -1;
 869                 else
 870                         a = 0;
 871         }
 872         else {
 873                 a = Py_ARITHMETIC_RIGHT_SHIFT(long, a, b);
 874         }
 875         return PyInt_FromLong(a);
 876 }
 877
 878 static PyObject *
 879 int_and(PyIntObject *v, PyIntObject *w)
 880 {
 881         register long a, b;
 882         CONVERT_TO_LONG(v, a);
 883         CONVERT_TO_LONG(w, b);
 884         return PyInt_FromLong(a & b);
 885 }
 886
 887 static PyObject *
 888 int_xor(PyIntObject *v, PyIntObject *w)
 889 {
 890         register long a, b;
 891         CONVERT_TO_LONG(v, a);
 892         CONVERT_TO_LONG(w, b);
 893         return PyInt_FromLong(a ^ b);
 894 }
 895
 896 static PyObject *
 897 int_or(PyIntObject *v, PyIntObject *w)
 898 {
 899         register long a, b;
 900         CONVERT_TO_LONG(v, a);
 901         CONVERT_TO_LONG(w, b);
 902         return PyInt_FromLong(a | b);
 903 }
 904
 905 static int
 906 int_coerce(PyObject **pv, PyObject **pw)
 907 {
 908         if (PyInt_Check(*pw)) {
 909                 Py_INCREF(*pv);
 910                 Py_INCREF(*pw);
 911                 return 0;
 912         }
 913         return 1; /* Can't do it */
 914 }
 915
 916 static PyObject *
 917 int_int(PyIntObject *v)
 918 {
 919         if (PyInt_CheckExact(v))
 920                 Py_INCREF(v);
 921         else
 922                 v = (PyIntObject *)PyInt_FromLong(v->ob_ival);
 923         return (PyObject *)v;
 924 }
 925
 926 static PyObject *
 927 int_long(PyIntObject *v)
 928 {
 929         return PyLong_FromLong((v -> ob_ival));
 930 }
 931
 932 static const unsigned char BitLengthTable[32] = {
 933         0, 1, 2, 2, 3, 3, 3, 3, 4, 4, 4, 4, 4, 4, 4, 4,
 934         5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5
 935 };
 936
 937 static int
 938 bits_in_ulong(unsigned long d)
 939 {
 940         int d_bits = 0;
 941         while (d >= 32) {
 942                 d_bits += 6;
 943                 d >>= 6;
 944         }
 945         d_bits += (int)BitLengthTable[d];
 946         return d_bits;
 947 }
 948
 949 #if 8*SIZEOF_LONG-1 <= DBL_MANT_DIG
 950 /* Every Python int can be exactly represented as a float. */
 951
 952 static PyObject *
 953 int_float(PyIntObject *v)
 954 {
 955         return PyFloat_FromDouble((double)(v -> ob_ival));
 956 }
 957
 958 #else
 959 /* Here not all Python ints are exactly representable as floats, so we may
 960    have to round.  We do this manually, since the C standards don't specify
 961    whether converting an integer to a float rounds up or down */
 962
 963 static PyObject *
 964 int_float(PyIntObject *v)
 965 {
 966         unsigned long abs_ival, lsb;
 967         int round_up;
 968
 969         if (v->ob_ival < 0)
 970                 abs_ival = 0U-(unsigned long)v->ob_ival;
 971         else
 972                 abs_ival = (unsigned long)v->ob_ival;
 973         if (abs_ival < (1L << DBL_MANT_DIG))
 974                 /* small integer;  no need to round */
 975                 return PyFloat_FromDouble((double)v->ob_ival);
 976
 977         /* Round abs_ival to MANT_DIG significant bits, using the
 978            round-half-to-even rule.  abs_ival & lsb picks out the 'rounding'
 979            bit: the first bit after the most significant MANT_DIG bits of
 980            abs_ival.  We round up if this bit is set, provided that either:
 981
 982              (1) abs_ival isn't exactly halfway between two floats, in which
 983              case at least one of the bits following the rounding bit must be
 984              set; i.e., abs_ival & lsb-1 != 0, or:
 985
 986              (2) the resulting rounded value has least significant bit 0; or
 987              in other words the bit above the rounding bit is set (this is the
 988              'to-even' bit of round-half-to-even); i.e., abs_ival & 2*lsb != 0
 989
 990            The condition "(1) or (2)" equates to abs_ival & 3*lsb-1 != 0. */
 991
 992         lsb = 1L << (bits_in_ulong(abs_ival)-DBL_MANT_DIG-1);
 993         round_up = (abs_ival & lsb) && (abs_ival & (3*lsb-1));
 994         abs_ival &= -2*lsb;
 995         if (round_up)
 996                 abs_ival += 2*lsb;
 997         return PyFloat_FromDouble(v->ob_ival < 0 ?
 998                                   -(double)abs_ival :
 999                                   (double)abs_ival);
1000 }
1001
1002 #endif
1003
1004 static PyObject *
1005 int_oct(PyIntObject *v)
1006 {
1007         return _PyInt_Format(v, 8, 0);
1008 }
1009
1010 static PyObject *
1011 int_hex(PyIntObject *v)
1012 {
1013         return _PyInt_Format(v, 16, 0);
1014 }
1015
1016 static PyObject *
1017 int_subtype_new(PyTypeObject *type, PyObject *args, PyObject *kwds);
1018
1019 static PyObject *
1020 int_new(PyTypeObject *type, PyObject *args, PyObject *kwds)
1021 {
1022         PyObject *x = NULL;
1023         int base = -909;
1024         static char *kwlist[] = {"x", "base", 0};
1025
1026         if (type != &PyInt_Type)
1027                 return int_subtype_new(type, args, kwds); /* Wimp out */
1028         if (!PyArg_ParseTupleAndKeywords(args, kwds, "|Oi:int", kwlist,
1029                                          &x, &base))
1030                 return NULL;
1031         if (x == NULL)
1032                 return PyInt_FromLong(0L);
1033         if (base == -909)
1034                 return PyNumber_Int(x);
1035         if (PyString_Check(x)) {
1036                 /* Since PyInt_FromString doesn't have a length parameter,
1037                  * check here for possible NULs in the string. */
1038                 char *string = PyString_AS_STRING(x);
1039                 if (strlen(string) != PyString_Size(x)) {
1040                         /* create a repr() of the input string,
1041                          * just like PyInt_FromString does */
1042                         PyObject *srepr;
1043                         srepr = PyObject_Repr(x);
1044                         if (srepr == NULL)
1045                                 return NULL;
1046                         PyErr_Format(PyExc_ValueError,
1047                              "invalid literal for int() with base %d: %s",
1048                              base, PyString_AS_STRING(srepr));
1049                         Py_DECREF(srepr);
1050                         return NULL;
1051                 }
1052                 return PyInt_FromString(string, NULL, base);
1053         }
1054 #ifdef Py_USING_UNICODE
1055         if (PyUnicode_Check(x))
1056                 return PyInt_FromUnicode(PyUnicode_AS_UNICODE(x),
1057                                          PyUnicode_GET_SIZE(x),
1058                                          base);
1059 #endif
1060         PyErr_SetString(PyExc_TypeError,
1061                         "int() can't convert non-string with explicit base");
1062         return NULL;
1063 }
1064
1065 /* Wimpy, slow approach to tp_new calls for subtypes of int:
1066    first create a regular int from whatever arguments we got,
1067    then allocate a subtype instance and initialize its ob_ival
1068    from the regular int.  The regular int is then thrown away.
1069 */
1070 static PyObject *
1071 int_subtype_new(PyTypeObject *type, PyObject *args, PyObject *kwds)
1072 {
1073         PyObject *tmp, *newobj;
1074         long ival;
1075
1076         assert(PyType_IsSubtype(type, &PyInt_Type));
1077         tmp = int_new(&PyInt_Type, args, kwds);
1078         if (tmp == NULL)
1079                 return NULL;
1080         if (!PyInt_Check(tmp)) {
1081                 ival = PyLong_AsLong(tmp);
1082                 if (ival == -1 && PyErr_Occurred()) {
1083                         Py_DECREF(tmp);
1084                         return NULL;
1085                 }
1086         } else {
1087                 ival = ((PyIntObject *)tmp)->ob_ival;
1088         }
1089
1090         newobj = type->tp_alloc(type, 0);
1091         if (newobj == NULL) {
1092                 Py_DECREF(tmp);
1093                 return NULL;
1094         }
1095         ((PyIntObject *)newobj)->ob_ival = ival;
1096         Py_DECREF(tmp);
1097         return newobj;
1098 }
1099
1100 static PyObject *
1101 int_getnewargs(PyIntObject *v)
1102 {
1103         return Py_BuildValue("(l)", v->ob_ival);
1104 }
1105
1106 static PyObject *
1107 int_get0(PyIntObject *v, void *context) {
1108         return PyInt_FromLong(0L);
1109 }
1110
1111 static PyObject *
1112 int_get1(PyIntObject *v, void *context) {
1113         return PyInt_FromLong(1L);
1114 }
1115
1116 /* Convert an integer to the given base.  Returns a string.
1117    If base is 2, 8 or 16, add the proper prefix '0b', '0o' or '0x'.
1118    If newstyle is zero, then use the pre-2.6 behavior of octal having
1119    a leading "0" */
1120 PyAPI_FUNC(PyObject*)
1121 _PyInt_Format(PyIntObject *v, int base, int newstyle)
1122 {
1123         /* There are no doubt many, many ways to optimize this, using code
1124            similar to _PyLong_Format */
1125         long n = v->ob_ival;
1126         int  negative = n < 0;
1127         int is_zero = n == 0;
1128
1129         /* For the reasoning behind this size, see
1130            http://c-faq.com/misc/hexio.html. Then, add a few bytes for
1131            the possible sign and prefix "0[box]" */
1132         char buf[sizeof(n)*CHAR_BIT+6];
1133
1134         /* Start by pointing to the end of the buffer.  We fill in from
1135            the back forward. */
1136         char* p = &buf[sizeof(buf)];
1137
1138         assert(base >= 2 && base <= 36);
1139
1140         do {
1141                 /* I'd use i_divmod, except it doesn't produce the results
1142                    I want when n is negative.  So just duplicate the salient
1143                    part here. */
1144                 long div = n / base;
1145                 long mod = n - div * base;
1146
1147                 /* convert abs(mod) to the right character in [0-9, a-z] */
1148                 char cdigit = (char)(mod < 0 ? -mod : mod);
1149                 cdigit += (cdigit < 10) ? '0' : 'a'-10;
1150                 *--p = cdigit;
1151
1152                 n = div;
1153         } while(n);
1154
1155         if (base == 2) {
1156                 *--p = 'b';
1157                 *--p = '0';
1158         }
1159         else if (base == 8) {
1160                 if (newstyle) {
1161                         *--p = 'o';
1162                         *--p = '0';
1163                 }
1164                 else
1165                         if (!is_zero)
1166                                 *--p = '0';
1167         }
1168         else if (base == 16) {
1169                 *--p = 'x';
1170                 *--p = '0';
1171         }
1172         else if (base != 10) {
1173                 *--p = '#';
1174                 *--p = '0' + base%10;
1175                 if (base > 10)
1176                         *--p = '0' + base/10;
1177         }
1178         if (negative)
1179                 *--p = '-';
1180
1181         return PyString_FromStringAndSize(p, &buf[sizeof(buf)] - p);
1182 }
1183
1184 static PyObject *
1185 int__format__(PyObject *self, PyObject *args)
1186 {
1187         PyObject *format_spec;
1188
1189         if (!PyArg_ParseTuple(args, "O:__format__", &format_spec))
1190                 return NULL;
1191         if (PyBytes_Check(format_spec))
1192                 return _PyInt_FormatAdvanced(self,
1193                                              PyBytes_AS_STRING(format_spec),
1194                                              PyBytes_GET_SIZE(format_spec));
1195         if (PyUnicode_Check(format_spec)) {
1196                 /* Convert format_spec to a str */
1197                 PyObject *result;
1198                 PyObject *str_spec = PyObject_Str(format_spec);
1199
1200                 if (str_spec == NULL)
1201                         return NULL;
1202
1203                 result = _PyInt_FormatAdvanced(self,
1204                                                PyBytes_AS_STRING(str_spec),
1205                                                PyBytes_GET_SIZE(str_spec));
1206
1207                 Py_DECREF(str_spec);
1208                 return result;
1209         }
1210         PyErr_SetString(PyExc_TypeError, "__format__ requires str or unicode");
1211         return NULL;
1212 }
1213
1214 static PyObject *
1215 int_bit_length(PyIntObject *v)
1216 {
1217         unsigned long n;
1218
1219         if (v->ob_ival < 0)
1220                 /* avoid undefined behaviour when v->ob_ival == -LONG_MAX-1 */
1221                 n = 0U-(unsigned long)v->ob_ival;
1222         else
1223                 n = (unsigned long)v->ob_ival;
1224
1225         return PyInt_FromLong(bits_in_ulong(n));
1226 }
1227
1228 PyDoc_STRVAR(int_bit_length_doc,
1229 "int.bit_length() -> int\n\
1230 \n\
1231 Number of bits necessary to represent self in binary.\n\
1232 >>> bin(37)\n\
1233 '0b100101'\n\
1234 >>> (37).bit_length()\n\
1235 6");
1236
1237 #if 0
1238 static PyObject *
1239 int_is_finite(PyObject *v)
1240 {
1241         Py_RETURN_TRUE;
1242 }
1243 #endif
1244
1245 static PyMethodDef int_methods[] = {
1246         {"conjugate",   (PyCFunction)int_int,   METH_NOARGS,
1247          "Returns self, the complex conjugate of any int."},
1248         {"bit_length", (PyCFunction)int_bit_length, METH_NOARGS,
1249          int_bit_length_doc},
1250 #if 0
1251         {"is_finite",   (PyCFunction)int_is_finite,     METH_NOARGS,
1252          "Returns always True."},
1253 #endif
1254         {"__trunc__",   (PyCFunction)int_int,   METH_NOARGS,
1255          "Truncating an Integral returns itself."},
1256         {"__getnewargs__",      (PyCFunction)int_getnewargs,    METH_NOARGS},
1257         {"__format__", (PyCFunction)int__format__, METH_VARARGS},
1258         {NULL,          NULL}           /* sentinel */
1259 };
1260
1261 static PyGetSetDef int_getset[] = {
1262         {"real",
1263          (getter)int_int, (setter)NULL,
1264          "the real part of a complex number",
1265          NULL},
1266         {"imag",
1267          (getter)int_get0, (setter)NULL,
1268          "the imaginary part of a complex number",
1269          NULL},
1270         {"numerator",
1271          (getter)int_int, (setter)NULL,
1272          "the numerator of a rational number in lowest terms",
1273          NULL},
1274         {"denominator",
1275          (getter)int_get1, (setter)NULL,
1276          "the denominator of a rational number in lowest terms",
1277          NULL},
1278         {NULL}  /* Sentinel */
1279 };
1280
1281 PyDoc_STRVAR(int_doc,
1282 "int(x[, base]) -> integer\n\
1283 \n\
1284 Convert a string or number to an integer, if possible.  A floating point\n\
1285 argument will be truncated towards zero (this does not include a string\n\
1286 representation of a floating point number!)  When converting a string, use\n\
1287 the optional base.  It is an error to supply a base when converting a\n\
1288 non-string.  If base is zero, the proper base is guessed based on the\n\
1289 string content.  If the argument is outside the integer range a\n\
1290 long object will be returned instead.");
1291
1292 static PyNumberMethods int_as_number = {
1293         (binaryfunc)int_add,    /*nb_add*/
1294         (binaryfunc)int_sub,    /*nb_subtract*/
1295         (binaryfunc)int_mul,    /*nb_multiply*/
1296         (binaryfunc)int_classic_div, /*nb_divide*/
1297         (binaryfunc)int_mod,    /*nb_remainder*/
1298         (binaryfunc)int_divmod, /*nb_divmod*/
1299         (ternaryfunc)int_pow,   /*nb_power*/
1300         (unaryfunc)int_neg,     /*nb_negative*/
1301         (unaryfunc)int_int,     /*nb_positive*/
1302         (unaryfunc)int_abs,     /*nb_absolute*/
1303         (inquiry)int_nonzero,   /*nb_nonzero*/
1304         (unaryfunc)int_invert,  /*nb_invert*/
1305         (binaryfunc)int_lshift, /*nb_lshift*/
1306         (binaryfunc)int_rshift, /*nb_rshift*/
1307         (binaryfunc)int_and,    /*nb_and*/
1308         (binaryfunc)int_xor,    /*nb_xor*/
1309         (binaryfunc)int_or,     /*nb_or*/
1310         int_coerce,             /*nb_coerce*/
1311         (unaryfunc)int_int,     /*nb_int*/
1312         (unaryfunc)int_long,    /*nb_long*/
1313         (unaryfunc)int_float,   /*nb_float*/
1314         (unaryfunc)int_oct,     /*nb_oct*/
1315         (unaryfunc)int_hex,     /*nb_hex*/
1316         0,                      /*nb_inplace_add*/
1317         0,                      /*nb_inplace_subtract*/
1318         0,                      /*nb_inplace_multiply*/
1319         0,                      /*nb_inplace_divide*/
1320         0,                      /*nb_inplace_remainder*/
1321         0,                      /*nb_inplace_power*/
1322         0,                      /*nb_inplace_lshift*/
1323         0,                      /*nb_inplace_rshift*/
1324         0,                      /*nb_inplace_and*/
1325         0,                      /*nb_inplace_xor*/
1326         0,                      /*nb_inplace_or*/
1327         (binaryfunc)int_div,    /* nb_floor_divide */
1328         int_true_divide,        /* nb_true_divide */
1329         0,                      /* nb_inplace_floor_divide */
1330         0,                      /* nb_inplace_true_divide */
1331         (unaryfunc)int_int,     /* nb_index */
1332 };
1333
1334 PyTypeObject PyInt_Type = {
1335         PyVarObject_HEAD_INIT(&PyType_Type, 0)
1336         "int",
1337         sizeof(PyIntObject),
1338         0,
1339         (destructor)int_dealloc,                /* tp_dealloc */
1340         (printfunc)int_print,                   /* tp_print */
1341         0,                                      /* tp_getattr */
1342         0,                                      /* tp_setattr */
1343         (cmpfunc)int_compare,                   /* tp_compare */
1344         (reprfunc)int_repr,                     /* tp_repr */
1345         &int_as_number,                         /* tp_as_number */
1346         0,                                      /* tp_as_sequence */
1347         0,                                      /* tp_as_mapping */
1348         (hashfunc)int_hash,                     /* tp_hash */
1349         0,                                      /* tp_call */
1350         (reprfunc)int_repr,                     /* tp_str */
1351         PyObject_GenericGetAttr,                /* tp_getattro */
1352         0,                                      /* tp_setattro */
1353         0,                                      /* tp_as_buffer */
1354         Py_TPFLAGS_DEFAULT | Py_TPFLAGS_CHECKTYPES |
1355                 Py_TPFLAGS_BASETYPE | Py_TPFLAGS_INT_SUBCLASS,  /* tp_flags */
1356         int_doc,                                /* tp_doc */
1357         0,                                      /* tp_traverse */
1358         0,                                      /* tp_clear */
1359         0,                                      /* tp_richcompare */
1360         0,                                      /* tp_weaklistoffset */
1361         0,                                      /* tp_iter */
1362         0,                                      /* tp_iternext */
1363         int_methods,                            /* tp_methods */
1364         0,                                      /* tp_members */
1365         int_getset,                             /* tp_getset */
1366         0,                                      /* tp_base */
1367         0,                                      /* tp_dict */
1368         0,                                      /* tp_descr_get */
1369         0,                                      /* tp_descr_set */
1370         0,                                      /* tp_dictoffset */
1371         0,                                      /* tp_init */
1372         0,                                      /* tp_alloc */
1373         int_new,                                /* tp_new */
1374         (freefunc)int_free,                     /* tp_free */
1375 };
1376
1377 int
1378 _PyInt_Init(void)
1379 {
1380         PyIntObject *v;
1381         int ival;
1382 #if NSMALLNEGINTS + NSMALLPOSINTS > 0
1383         for (ival = -NSMALLNEGINTS; ival < NSMALLPOSINTS; ival++) {
1384               if (!free_list && (free_list = fill_free_list()) == NULL)
1385                         return 0;
1386                 /* PyObject_New is inlined */
1387                 v = free_list;
1388                 free_list = (PyIntObject *)Py_TYPE(v);
1389                 PyObject_INIT(v, &PyInt_Type);
1390                 v->ob_ival = ival;
1391                 small_ints[ival + NSMALLNEGINTS] = v;
1392         }
1393 #endif
1394         return 1;
1395 }
1396
1397 int
1398 PyInt_ClearFreeList(void)
1399 {
1400         PyIntObject *p;
1401         PyIntBlock *list, *next;
1402         int i;
1403         int u;                  /* remaining unfreed ints per block */
1404         int freelist_size = 0;
1405
1406         list = block_list;
1407         block_list = NULL;
1408         free_list = NULL;
1409         while (list != NULL) {
1410                 u = 0;
1411                 for (i = 0, p = &list->objects[0];
1412                      i < N_INTOBJECTS;
1413                      i++, p++) {
1414                         if (PyInt_CheckExact(p) && p->ob_refcnt != 0)
1415                                 u++;
1416                 }
1417                 next = list->next;
1418                 if (u) {
1419                         list->next = block_list;
1420                         block_list = list;
1421                         for (i = 0, p = &list->objects[0];
1422                              i < N_INTOBJECTS;
1423                              i++, p++) {
1424                                 if (!PyInt_CheckExact(p) ||
1425                                     p->ob_refcnt == 0) {
1426                                         Py_TYPE(p) = (struct _typeobject *)
1427                                                 free_list;
1428                                         free_list = p;
1429                                 }
1430 #if NSMALLNEGINTS + NSMALLPOSINTS > 0
1431                                 else if (-NSMALLNEGINTS <= p->ob_ival &&
1432                                          p->ob_ival < NSMALLPOSINTS &&
1433                                          small_ints[p->ob_ival +
1434                                                     NSMALLNEGINTS] == NULL) {
1435                                         Py_INCREF(p);
1436                                         small_ints[p->ob_ival +
1437                                                    NSMALLNEGINTS] = p;
1438                                 }
1439 #endif
1440                         }
1441                 }
1442                 else {
1443                         PyMem_FREE(list);
1444                 }
1445                 freelist_size += u;
1446                 list = next;
1447         }
1448
1449         return freelist_size;
1450 }
1451
1452 void
1453 PyInt_Fini(void)
1454 {
1455         PyIntObject *p;
1456         PyIntBlock *list;
1457         int i;
1458         int u;                  /* total unfreed ints per block */
1459
1460 #if NSMALLNEGINTS + NSMALLPOSINTS > 0
1461         PyIntObject **q;
1462
1463         i = NSMALLNEGINTS + NSMALLPOSINTS;
1464         q = small_ints;
1465         while (--i >= 0) {
1466                 Py_XDECREF(*q);
1467                 *q++ = NULL;
1468         }
1469 #endif
1470         u = PyInt_ClearFreeList();
1471         if (!Py_VerboseFlag)
1472                 return;
1473         fprintf(stderr, "# cleanup ints");
1474         if (!u) {
1475                 fprintf(stderr, "\n");
1476         }
1477         else {
1478                 fprintf(stderr,
1479                         ": %d unfreed int%s\n",
1480                         u, u == 1 ? "" : "s");
1481         }
1482         if (Py_VerboseFlag > 1) {
1483                 list = block_list;
1484                 while (list != NULL) {
1485                         for (i = 0, p = &list->objects[0];
1486                              i < N_INTOBJECTS;
1487                              i++, p++) {
1488                                 if (PyInt_CheckExact(p) && p->ob_refcnt != 0)
1489                                         /* XXX(twouters) cast refcount to
1490                                            long until %zd is universally
1491                                            available
1492                                          */
1493                                         fprintf(stderr,
1494                                 "#   <int at %p, refcnt=%ld, val=%ld>\n",
1495                                                 p, (long)p->ob_refcnt,
1496                                                 p->ob_ival);
1497                         }
1498                         list = list->next;
1499                 }
1500         }
1501 }