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