Objects/intobject.c

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