Objects/intobject.c

   1
   2 /* Integer object implementation */
   3
   4 #include "Python.h"
   5 #include <ctype.h>
   6
   7 long
   8 PyInt_GetMax(void)
   9 {
  10         return LONG_MAX;        /* To initialize sys.maxint */
  11 }
  12
  13 /* Integers are quite normal objects, to make object handling uniform.
  14    (Using odd pointers to represent integers would save much space
  15    but require extra checks for this special case throughout the code.)
  16    Since a typical Python program spends much of its time allocating
  17    and deallocating integers, these operations should be very fast.
  18    Therefore we use a dedicated allocation scheme with a much lower
  19    overhead (in space and time) than straight malloc(): a simple
  20    dedicated free list, filled when necessary with memory from malloc().
  21
  22    block_list is a singly-linked list of all PyIntBlocks ever allocated,
  23    linked via their next members.  PyIntBlocks are never returned to the
  24    system before shutdown (PyInt_Fini).
  25
  26    free_list is a singly-linked list of available PyIntObjects, linked
  27    via abuse of their ob_type members.
  28 */
  29
  30 #define BLOCK_SIZE      1000    /* 1K less typical malloc overhead */
  31 #define BHEAD_SIZE      8       /* Enough for a 64-bit pointer */
  32 #define N_INTOBJECTS    ((BLOCK_SIZE - BHEAD_SIZE) / sizeof(PyIntObject))
  33
  34 struct _intblock {
  35         struct _intblock *next;
  36         PyIntObject objects[N_INTOBJECTS];
  37 };
  38
  39 typedef struct _intblock PyIntBlock;
  40
  41 static PyIntBlock *block_list = NULL;
  42 static PyIntObject *free_list = NULL;
  43
  44 static PyIntObject *
  45 fill_free_list(void)
  46 {
  47         PyIntObject *p, *q;
  48         /* Python's object allocator isn't appropriate for large blocks. */
  49         p = (PyIntObject *) PyMem_MALLOC(sizeof(PyIntBlock));
  50         if (p == NULL)
  51                 return (PyIntObject *) PyErr_NoMemory();
  52         ((PyIntBlock *)p)->next = block_list;
  53         block_list = (PyIntBlock *)p;
  54         /* Link the int objects together, from rear to front, then return
  55            the address of the last int object in the block. */
  56         p = &((PyIntBlock *)p)->objects[0];
  57         q = p + N_INTOBJECTS;
  58         while (--q > p)
  59                 q->ob_type = (struct _typeobject *)(q-1);
  60         q->ob_type = NULL;
  61         return p + N_INTOBJECTS - 1;
  62 }
  63
  64 #ifndef NSMALLPOSINTS
  65 #define NSMALLPOSINTS           257
  66 #endif
  67 #ifndef NSMALLNEGINTS
  68 #define NSMALLNEGINTS           5
  69 #endif
  70 #if NSMALLNEGINTS + NSMALLPOSINTS > 0
  71 /* References to small integers are saved in this array so that they
  72    can be shared.
  73    The integers that are saved are those in the range
  74    -NSMALLNEGINTS (inclusive) to NSMALLPOSINTS (not inclusive).
  75 */
  76 static PyIntObject *small_ints[NSMALLNEGINTS + NSMALLPOSINTS];
  77 #endif
  78 #ifdef COUNT_ALLOCS
  79 int quick_int_allocs, quick_neg_int_allocs;
  80 #endif
  81
  82 PyObject *
  83 PyInt_FromLong(long ival)
  84 {
  85         register PyIntObject *v;
  86 #if NSMALLNEGINTS + NSMALLPOSINTS > 0
  87         if (-NSMALLNEGINTS <= ival && ival < NSMALLPOSINTS) {
  88                 v = small_ints[ival + NSMALLNEGINTS];
  89                 Py_INCREF(v);
  90 #ifdef COUNT_ALLOCS
  91                 if (ival >= 0)
  92                         quick_int_allocs++;
  93                 else
  94                         quick_neg_int_allocs++;
  95 #endif
  96                 return (PyObject *) v;
  97         }
  98 #endif
  99         if (free_list == NULL) {
 100                 if ((free_list = fill_free_list()) == NULL)
 101                         return NULL;
 102         }
 103         /* Inline PyObject_New */
 104         v = free_list;
 105         free_list = (PyIntObject *)v->ob_type;
 106         PyObject_INIT(v, &PyInt_Type);
 107         v->ob_ival = ival;
 108         return (PyObject *) v;
 109 }
 110
 111 PyObject *
 112 PyInt_FromSize_t(size_t ival)
 113 {
 114         if (ival <= LONG_MAX)
 115                 return PyInt_FromLong((long)ival);
 116         return _PyLong_FromSize_t(ival);
 117 }
 118
 119 PyObject *
 120 PyInt_FromSsize_t(Py_ssize_t ival)
 121 {
 122         if (ival >= LONG_MIN && ival <= LONG_MAX)
 123                 return PyInt_FromLong((long)ival);
 124         return _PyLong_FromSsize_t(ival);
 125 }
 126
 127 static void
 128 int_dealloc(PyIntObject *v)
 129 {
 130         if (PyInt_CheckExact(v)) {
 131                 v->ob_type = (struct _typeobject *)free_list;
 132                 free_list = v;
 133         }
 134         else
 135                 v->ob_type->tp_free((PyObject *)v);
 136 }
 137
 138 static void
 139 int_free(PyIntObject *v)
 140 {
 141         v->ob_type = (struct _typeobject *)free_list;
 142         free_list = v;
 143 }
 144
 145 long
 146 PyInt_AsLong(register PyObject *op)
 147 {
 148         PyNumberMethods *nb;
 149         PyIntObject *io;
 150         long val;
 151
 152         if (op && PyInt_Check(op))
 153                 return PyInt_AS_LONG((PyIntObject*) op);
 154
 155         if (op == NULL || (nb = op->ob_type->tp_as_number) == NULL ||
 156             nb->nb_int == NULL) {
 157                 PyErr_SetString(PyExc_TypeError, "an integer is required");
 158                 return -1;
 159         }
 160
 161         io = (PyIntObject*) (*nb->nb_int) (op);
 162         if (io == NULL)
 163                 return -1;
 164         if (!PyInt_Check(io)) {
 165                 if (PyLong_Check(io)) {
 166                         /* got a long? => retry int conversion */
 167                         val = PyLong_AsLong((PyObject *)io);
 168                         Py_DECREF(io);
 169                         if ((val == -1) && PyErr_Occurred())
 170                                 return -1;
 171                         return val;
 172                 }
 173                 else
 174                 {
 175                         Py_DECREF(io);
 176                         PyErr_SetString(PyExc_TypeError,
 177                                         "nb_int should return int object");
 178                         return -1;
 179                 }
 180         }
 181
 182         val = PyInt_AS_LONG(io);
 183         Py_DECREF(io);
 184
 185         return val;
 186 }
 187
 188 Py_ssize_t
 189 PyInt_AsSsize_t(register PyObject *op)
 190 {
 191 #if SIZEOF_SIZE_T != SIZEOF_LONG
 192         PyNumberMethods *nb;
 193         PyIntObject *io;
 194         Py_ssize_t val;
 195 #endif
 196
 197         if (op == NULL) {
 198                 PyErr_SetString(PyExc_TypeError, "an integer is required");
 199                 return -1;
 200         }
 201
 202         if (PyInt_Check(op))
 203                 return PyInt_AS_LONG((PyIntObject*) op);
 204         if (PyLong_Check(op))
 205                 return _PyLong_AsSsize_t(op);
 206 #if SIZEOF_SIZE_T == SIZEOF_LONG
 207         return PyInt_AsLong(op);
 208 #else
 209
 210         if ((nb = op->ob_type->tp_as_number) == NULL ||
 211             (nb->nb_int == NULL && nb->nb_long == 0)) {
 212                 PyErr_SetString(PyExc_TypeError, "an integer is required");
 213                 return -1;
 214         }
 215
 216         if (nb->nb_long != 0) {
 217                 io = (PyIntObject*) (*nb->nb_long) (op);
 218         } else {
 219                 io = (PyIntObject*) (*nb->nb_int) (op);
 220         }
 221         if (io == NULL)
 222                 return -1;
 223         if (!PyInt_Check(io)) {
 224                 if (PyLong_Check(io)) {
 225                         /* got a long? => retry int conversion */
 226                         val = _PyLong_AsSsize_t((PyObject *)io);
 227                         Py_DECREF(io);
 228                         if ((val == -1) && PyErr_Occurred())
 229                                 return -1;
 230                         return val;
 231                 }
 232                 else
 233                 {
 234                         Py_DECREF(io);
 235                         PyErr_SetString(PyExc_TypeError,
 236                                         "nb_int should return int object");
 237                         return -1;
 238                 }
 239         }
 240
 241         val = PyInt_AS_LONG(io);
 242         Py_DECREF(io);
 243
 244         return val;
 245 #endif
 246 }
 247
 248 unsigned long
 249 PyInt_AsUnsignedLongMask(register PyObject *op)
 250 {
 251         PyNumberMethods *nb;
 252         PyIntObject *io;
 253         unsigned long val;
 254
 255         if (op && PyInt_Check(op))
 256                 return PyInt_AS_LONG((PyIntObject*) op);
 257         if (op && PyLong_Check(op))
 258                 return PyLong_AsUnsignedLongMask(op);
 259
 260         if (op == NULL || (nb = op->ob_type->tp_as_number) == NULL ||
 261             nb->nb_int == NULL) {
 262                 PyErr_SetString(PyExc_TypeError, "an integer is required");
 263                 return (unsigned long)-1;
 264         }
 265
 266         io = (PyIntObject*) (*nb->nb_int) (op);
 267         if (io == NULL)
 268                 return (unsigned long)-1;
 269         if (!PyInt_Check(io)) {
 270                 if (PyLong_Check(io)) {
 271                         val = PyLong_AsUnsignedLongMask((PyObject *)io);
 272                         Py_DECREF(io);
 273                         if (PyErr_Occurred())
 274                                 return (unsigned long)-1;
 275                         return val;
 276                 }
 277                 else
 278                 {
 279                         Py_DECREF(io);
 280                         PyErr_SetString(PyExc_TypeError,
 281                                         "nb_int should return int object");
 282                         return (unsigned long)-1;
 283                 }
 284         }
 285
 286         val = PyInt_AS_LONG(io);
 287         Py_DECREF(io);
 288
 289         return val;
 290 }
 291
 292 #ifdef HAVE_LONG_LONG
 293 unsigned PY_LONG_LONG
 294 PyInt_AsUnsignedLongLongMask(register PyObject *op)
 295 {
 296         PyNumberMethods *nb;
 297         PyIntObject *io;
 298         unsigned PY_LONG_LONG val;
 299
 300         if (op && PyInt_Check(op))
 301                 return PyInt_AS_LONG((PyIntObject*) op);
 302         if (op && PyLong_Check(op))
 303                 return PyLong_AsUnsignedLongLongMask(op);
 304
 305         if (op == NULL || (nb = op->ob_type->tp_as_number) == NULL ||
 306             nb->nb_int == NULL) {
 307                 PyErr_SetString(PyExc_TypeError, "an integer is required");
 308                 return (unsigned PY_LONG_LONG)-1;
 309         }
 310
 311         io = (PyIntObject*) (*nb->nb_int) (op);
 312         if (io == NULL)
 313                 return (unsigned PY_LONG_LONG)-1;
 314         if (!PyInt_Check(io)) {
 315                 if (PyLong_Check(io)) {
 316                         val = PyLong_AsUnsignedLongLongMask((PyObject *)io);
 317                         Py_DECREF(io);
 318                         if (PyErr_Occurred())
 319                                 return (unsigned PY_LONG_LONG)-1;
 320                         return val;
 321                 }
 322                 else
 323                 {
 324                         Py_DECREF(io);
 325                         PyErr_SetString(PyExc_TypeError,
 326                                         "nb_int should return int object");
 327                         return (unsigned PY_LONG_LONG)-1;
 328                 }
 329         }
 330
 331         val = PyInt_AS_LONG(io);
 332         Py_DECREF(io);
 333
 334         return val;
 335 }
 336 #endif
 337
 338 PyObject *
 339 PyInt_FromString(char *s, char **pend, int base)
 340 {
 341         char *end;
 342         long x;
 343         Py_ssize_t slen;
 344         PyObject *sobj, *srepr;
 345
 346         if ((base != 0 && base < 2) || base > 36) {
 347                 PyErr_SetString(PyExc_ValueError,
 348                                 "int() base must be >= 2 and <= 36");
 349                 return NULL;
 350         }
 351
 352         while (*s && isspace(Py_CHARMASK(*s)))
 353                 s++;
 354         errno = 0;
 355         if (base == 0 && s[0] == '0') {
 356                 x = (long) PyOS_strtoul(s, &end, base);
 357                 if (x < 0)
 358                         return PyLong_FromString(s, pend, base);
 359         }
 360         else
 361                 x = PyOS_strtol(s, &end, base);
 362         if (end == s || !isalnum(Py_CHARMASK(end[-1])))
 363                 goto bad;
 364         while (*end && isspace(Py_CHARMASK(*end)))
 365                 end++;
 366         if (*end != '\0') {
 367   bad:
 368                 slen = strlen(s) < 200 ? strlen(s) : 200;
 369                 sobj = PyString_FromStringAndSize(s, slen);
 370                 if (sobj == NULL)
 371                         return NULL;
 372                 srepr = PyObject_Repr(sobj);
 373                 Py_DECREF(sobj);
 374                 if (srepr == NULL)
 375                         return NULL;
 376                 PyErr_Format(PyExc_ValueError,
 377                              "invalid literal for int() with base %d: %s",
 378                              base, PyString_AS_STRING(srepr));
 379                 Py_DECREF(srepr);
 380                 return NULL;
 381         }
 382         else if (errno != 0)
 383                 return PyLong_FromString(s, pend, base);
 384         if (pend)
 385                 *pend = end;
 386         return PyInt_FromLong(x);
 387 }
 388
 389 #ifdef Py_USING_UNICODE
 390 PyObject *
 391 PyInt_FromUnicode(Py_UNICODE *s, Py_ssize_t length, int base)
 392 {
 393         PyObject *result;
 394         char *buffer = (char *)PyMem_MALLOC(length+1);
 395
 396         if (buffer == NULL)
 397                 return NULL;
 398
 399         if (PyUnicode_EncodeDecimal(s, length, buffer, NULL)) {
 400                 PyMem_FREE(buffer);
 401                 return NULL;
 402         }
 403         result = PyInt_FromString(buffer, NULL, base);
 404         PyMem_FREE(buffer);
 405         return result;
 406 }
 407 #endif
 408
 409 /* Methods */
 410
 411 /* Integers are seen as the "smallest" of all numeric types and thus
 412    don't have any knowledge about conversion of other types to
 413    integers. */
 414
 415 #define CONVERT_TO_LONG(obj, lng)               \
 416         if (PyInt_Check(obj)) {                 \
 417                 lng = PyInt_AS_LONG(obj);       \
 418         }                                       \
 419         else {                                  \
 420                 Py_INCREF(Py_NotImplemented);   \
 421                 return Py_NotImplemented;       \
 422         }
 423
 424 /* ARGSUSED */
 425 static int
 426 int_print(PyIntObject *v, FILE *fp, int flags)
 427      /* flags -- not used but required by interface */
 428 {
 429         fprintf(fp, "%ld", v->ob_ival);
 430         return 0;
 431 }
 432
 433 static PyObject *
 434 int_repr(PyIntObject *v)
 435 {
 436         char buf[64];
 437         PyOS_snprintf(buf, sizeof(buf), "%ld", v->ob_ival);
 438         return PyString_FromString(buf);
 439 }
 440
 441 static int
 442 int_compare(PyIntObject *v, PyIntObject *w)
 443 {
 444         register long i = v->ob_ival;
 445         register long j = w->ob_ival;
 446         return (i < j) ? -1 : (i > j) ? 1 : 0;
 447 }
 448
 449 static long
 450 int_hash(PyIntObject *v)
 451 {
 452         /* XXX If this is changed, you also need to change the way
 453            Python's long, float and complex types are hashed. */
 454         long x = v -> ob_ival;
 455         if (x == -1)
 456                 x = -2;
 457         return x;
 458 }
 459
 460 static PyObject *
 461 int_add(PyIntObject *v, PyIntObject *w)
 462 {
 463         register long a, b, x;
 464         CONVERT_TO_LONG(v, a);
 465         CONVERT_TO_LONG(w, b);
 466         x = a + b;
 467         if ((x^a) >= 0 || (x^b) >= 0)
 468                 return PyInt_FromLong(x);
 469         return PyLong_Type.tp_as_number->nb_add((PyObject *)v, (PyObject *)w);
 470 }
 471
 472 static PyObject *
 473 int_sub(PyIntObject *v, PyIntObject *w)
 474 {
 475         register long a, b, x;
 476         CONVERT_TO_LONG(v, a);
 477         CONVERT_TO_LONG(w, b);
 478         x = 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         longprod = a * b;
 522         doubleprod = (double)a * (double)b;
 523         doubled_longprod = (double)longprod;
 524
 525         /* Fast path for normal case:  small multiplicands, and no info
 526            is lost in either method. */
 527         if (doubled_longprod == doubleprod)
 528                 return PyInt_FromLong(longprod);
 529
 530         /* Somebody somewhere lost info.  Close enough, or way off?  Note
 531            that a != 0 and b != 0 (else doubled_longprod == doubleprod == 0).
 532            The difference either is or isn't significant compared to the
 533            true value (of which doubleprod is a good approximation).
 534         */
 535         {
 536                 const double diff = doubled_longprod - doubleprod;
 537                 const double absdiff = diff >= 0.0 ? diff : -diff;
 538                 const double absprod = doubleprod >= 0.0 ? doubleprod :
 539                                                           -doubleprod;
 540                 /* absdiff/absprod <= 1/32 iff
 541                    32 * absdiff <= absprod -- 5 good bits is "close enough" */
 542                 if (32.0 * absdiff <= absprod)
 543                         return PyInt_FromLong(longprod);
 544                 else
 545                         return PyLong_Type.tp_as_number->nb_multiply(v, w);
 546         }
 547 }
 548
 549 /* Integer overflow checking for unary negation: on a 2's-complement
 550  * box, -x overflows iff x is the most negative long.  In this case we
 551  * get -x == x.  However, -x is undefined (by C) if x /is/ the most
 552  * negative long (it's a signed overflow case), and some compilers care.
 553  * So we cast x to unsigned long first.  However, then other compilers
 554  * warn about applying unary minus to an unsigned operand.  Hence the
 555  * weird "0-".
 556  */
 557 #define UNARY_NEG_WOULD_OVERFLOW(x)     \
 558         ((x) < 0 && (unsigned long)(x) == 0-(unsigned long)(x))
 559
 560 /* Return type of i_divmod */
 561 enum divmod_result {
 562         DIVMOD_OK,              /* Correct result */
 563         DIVMOD_OVERFLOW,        /* Overflow, try again using longs */
 564         DIVMOD_ERROR            /* Exception raised */
 565 };
 566
 567 static enum divmod_result
 568 i_divmod(register long x, register long y,
 569          long *p_xdivy, long *p_xmody)
 570 {
 571         long xdivy, xmody;
 572
 573         if (y == 0) {
 574                 PyErr_SetString(PyExc_ZeroDivisionError,
 575                                 "integer division or modulo by zero");
 576                 return DIVMOD_ERROR;
 577         }
 578         /* (-sys.maxint-1)/-1 is the only overflow case. */
 579         if (y == -1 && UNARY_NEG_WOULD_OVERFLOW(x))
 580                 return DIVMOD_OVERFLOW;
 581         xdivy = x / y;
 582         xmody = x - xdivy * y;
 583         /* If the signs of x and y differ, and the remainder is non-0,
 584          * C89 doesn't define whether xdivy is now the floor or the
 585          * ceiling of the infinitely precise quotient.  We want the floor,
 586          * and we have it iff the remainder's sign matches y's.
 587          */
 588         if (xmody && ((y ^ xmody) < 0) /* i.e. and signs differ */) {
 589                 xmody += y;
 590                 --xdivy;
 591                 assert(xmody && ((y ^ xmody) >= 0));
 592         }
 593         *p_xdivy = xdivy;
 594         *p_xmody = xmody;
 595         return DIVMOD_OK;
 596 }
 597
 598 static PyObject *
 599 int_div(PyIntObject *x, PyIntObject *y)
 600 {
 601         long xi, yi;
 602         long d, m;
 603         CONVERT_TO_LONG(x, xi);
 604         CONVERT_TO_LONG(y, yi);
 605         switch (i_divmod(xi, yi, &d, &m)) {
 606         case DIVMOD_OK:
 607                 return PyInt_FromLong(d);
 608         case DIVMOD_OVERFLOW:
 609                 return PyLong_Type.tp_as_number->nb_divide((PyObject *)x,
 610                                                            (PyObject *)y);
 611         default:
 612                 return NULL;
 613         }
 614 }
 615
 616 static PyObject *
 617 int_classic_div(PyIntObject *x, PyIntObject *y)
 618 {
 619         long xi, yi;
 620         long d, m;
 621         CONVERT_TO_LONG(x, xi);
 622         CONVERT_TO_LONG(y, yi);
 623         if (Py_DivisionWarningFlag &&
 624             PyErr_Warn(PyExc_DeprecationWarning, "classic int division") < 0)
 625                 return NULL;
 626         switch (i_divmod(xi, yi, &d, &m)) {
 627         case DIVMOD_OK:
 628                 return PyInt_FromLong(d);
 629         case DIVMOD_OVERFLOW:
 630                 return PyLong_Type.tp_as_number->nb_divide((PyObject *)x,
 631                                                            (PyObject *)y);
 632         default:
 633                 return NULL;
 634         }
 635 }
 636
 637 static PyObject *
 638 int_true_divide(PyObject *v, PyObject *w)
 639 {
 640         /* If they aren't both ints, give someone else a chance.  In
 641            particular, this lets int/long get handled by longs, which
 642            underflows to 0 gracefully if the long is too big to convert
 643            to float. */
 644         if (PyInt_Check(v) && PyInt_Check(w))
 645                 return PyFloat_Type.tp_as_number->nb_true_divide(v, w);
 646         Py_INCREF(Py_NotImplemented);
 647         return Py_NotImplemented;
 648 }
 649
 650 static PyObject *
 651 int_mod(PyIntObject *x, PyIntObject *y)
 652 {
 653         long xi, yi;
 654         long d, m;
 655         CONVERT_TO_LONG(x, xi);
 656         CONVERT_TO_LONG(y, yi);
 657         switch (i_divmod(xi, yi, &d, &m)) {
 658         case DIVMOD_OK:
 659                 return PyInt_FromLong(m);
 660         case DIVMOD_OVERFLOW:
 661                 return PyLong_Type.tp_as_number->nb_remainder((PyObject *)x,
 662                                                               (PyObject *)y);
 663         default:
 664                 return NULL;
 665         }
 666 }
 667
 668 static PyObject *
 669 int_divmod(PyIntObject *x, PyIntObject *y)
 670 {
 671         long xi, yi;
 672         long d, m;
 673         CONVERT_TO_LONG(x, xi);
 674         CONVERT_TO_LONG(y, yi);
 675         switch (i_divmod(xi, yi, &d, &m)) {
 676         case DIVMOD_OK:
 677                 return Py_BuildValue("(ll)", d, m);
 678         case DIVMOD_OVERFLOW:
 679                 return PyLong_Type.tp_as_number->nb_divmod((PyObject *)x,
 680                                                            (PyObject *)y);
 681         default:
 682                 return NULL;
 683         }
 684 }
 685
 686 static PyObject *
 687 int_pow(PyIntObject *v, PyIntObject *w, PyIntObject *z)
 688 {
 689         register long iv, iw, iz=0, ix, temp, prev;
 690         CONVERT_TO_LONG(v, iv);
 691         CONVERT_TO_LONG(w, iw);
 692         if (iw < 0) {
 693                 if ((PyObject *)z != Py_None) {
 694                         PyErr_SetString(PyExc_TypeError, "pow() 2nd argument "
 695                              "cannot be negative when 3rd argument specified");
 696                         return NULL;
 697                 }
 698                 /* Return a float.  This works because we know that
 699                    this calls float_pow() which converts its
 700                    arguments to double. */
 701                 return PyFloat_Type.tp_as_number->nb_power(
 702                         (PyObject *)v, (PyObject *)w, (PyObject *)z);
 703         }
 704         if ((PyObject *)z != Py_None) {
 705                 CONVERT_TO_LONG(z, iz);
 706                 if (iz == 0) {
 707                         PyErr_SetString(PyExc_ValueError,
 708                                         "pow() 3rd argument cannot be 0");
 709                         return NULL;
 710                 }
 711         }
 712         /*
 713          * XXX: The original exponentiation code stopped looping
 714          * when temp hit zero; this code will continue onwards
 715          * unnecessarily, but at least it won't cause any errors.
 716          * Hopefully the speed improvement from the fast exponentiation
 717          * will compensate for the slight inefficiency.
 718          * XXX: Better handling of overflows is desperately needed.
 719          */
 720         temp = iv;
 721         ix = 1;
 722         while (iw > 0) {
 723                 prev = ix;      /* Save value for overflow check */
 724                 if (iw & 1) {
 725                         ix = ix*temp;
 726                         if (temp == 0)
 727                                 break; /* Avoid ix / 0 */
 728                         if (ix / temp != prev) {
 729                                 return PyLong_Type.tp_as_number->nb_power(
 730                                         (PyObject *)v,
 731                                         (PyObject *)w,
 732                                         (PyObject *)z);
 733                         }
 734                 }
 735                 iw >>= 1;       /* Shift exponent down by 1 bit */
 736                 if (iw==0) break;
 737                 prev = temp;
 738                 temp *= temp;   /* Square the value of temp */
 739                 if (prev != 0 && temp / prev != prev) {
 740                         return PyLong_Type.tp_as_number->nb_power(
 741                                 (PyObject *)v, (PyObject *)w, (PyObject *)z);
 742                 }
 743                 if (iz) {
 744                         /* If we did a multiplication, perform a modulo */
 745                         ix = ix % iz;
 746                         temp = temp % iz;
 747                 }
 748         }
 749         if (iz) {
 750                 long div, mod;
 751                 switch (i_divmod(ix, iz, &div, &mod)) {
 752                 case DIVMOD_OK:
 753                         ix = mod;
 754                         break;
 755                 case DIVMOD_OVERFLOW:
 756                         return PyLong_Type.tp_as_number->nb_power(
 757                                 (PyObject *)v, (PyObject *)w, (PyObject *)z);
 758                 default:
 759                         return NULL;
 760                 }
 761         }
 762         return PyInt_FromLong(ix);
 763 }
 764
 765 static PyObject *
 766 int_neg(PyIntObject *v)
 767 {
 768         register long a;
 769         a = v->ob_ival;
 770         /* check for overflow */
 771         if (UNARY_NEG_WOULD_OVERFLOW(a)) {
 772                 PyObject *o = PyLong_FromLong(a);
 773                 if (o != NULL) {
 774                         PyObject *result = PyNumber_Negative(o);
 775                         Py_DECREF(o);
 776                         return result;
 777                 }
 778                 return NULL;
 779         }
 780         return PyInt_FromLong(-a);
 781 }
 782
 783 static PyObject *
 784 int_pos(PyIntObject *v)
 785 {
 786         if (PyInt_CheckExact(v)) {
 787                 Py_INCREF(v);
 788                 return (PyObject *)v;
 789         }
 790         else
 791                 return PyInt_FromLong(v->ob_ival);
 792 }
 793
 794 static PyObject *
 795 int_abs(PyIntObject *v)
 796 {
 797         if (v->ob_ival >= 0)
 798                 return int_pos(v);
 799         else
 800                 return int_neg(v);
 801 }
 802
 803 static int
 804 int_nonzero(PyIntObject *v)
 805 {
 806         return v->ob_ival != 0;
 807 }
 808
 809 static PyObject *
 810 int_invert(PyIntObject *v)
 811 {
 812         return PyInt_FromLong(~v->ob_ival);
 813 }
 814
 815 static PyObject *
 816 int_lshift(PyIntObject *v, PyIntObject *w)
 817 {
 818         long a, b, c;
 819         PyObject *vv, *ww, *result;
 820
 821         CONVERT_TO_LONG(v, a);
 822         CONVERT_TO_LONG(w, b);
 823         if (b < 0) {
 824                 PyErr_SetString(PyExc_ValueError, "negative shift count");
 825                 return NULL;
 826         }
 827         if (a == 0 || b == 0)
 828                 return int_pos(v);
 829         if (b >= LONG_BIT) {
 830                 vv = PyLong_FromLong(PyInt_AS_LONG(v));
 831                 if (vv == NULL)
 832                         return NULL;
 833                 ww = PyLong_FromLong(PyInt_AS_LONG(w));
 834                 if (ww == NULL) {
 835                         Py_DECREF(vv);
 836                         return NULL;
 837                 }
 838                 result = PyNumber_Lshift(vv, ww);
 839                 Py_DECREF(vv);
 840                 Py_DECREF(ww);
 841                 return result;
 842         }
 843         c = a << b;
 844         if (a != Py_ARITHMETIC_RIGHT_SHIFT(long, c, b)) {
 845                 vv = PyLong_FromLong(PyInt_AS_LONG(v));
 846                 if (vv == NULL)
 847                         return NULL;
 848                 ww = PyLong_FromLong(PyInt_AS_LONG(w));
 849                 if (ww == NULL) {
 850                         Py_DECREF(vv);
 851                         return NULL;
 852                 }
 853                 result = PyNumber_Lshift(vv, ww);
 854                 Py_DECREF(vv);
 855                 Py_DECREF(ww);
 856                 return result;
 857         }
 858         return PyInt_FromLong(c);
 859 }
 860
 861 static PyObject *
 862 int_rshift(PyIntObject *v, PyIntObject *w)
 863 {
 864         register long a, b;
 865         CONVERT_TO_LONG(v, a);
 866         CONVERT_TO_LONG(w, b);
 867         if (b < 0) {
 868                 PyErr_SetString(PyExc_ValueError, "negative shift count");
 869                 return NULL;
 870         }
 871         if (a == 0 || b == 0)
 872                 return int_pos(v);
 873         if (b >= LONG_BIT) {
 874                 if (a < 0)
 875                         a = -1;
 876                 else
 877                         a = 0;
 878         }
 879         else {
 880                 a = Py_ARITHMETIC_RIGHT_SHIFT(long, a, b);
 881         }
 882         return PyInt_FromLong(a);
 883 }
 884
 885 static PyObject *
 886 int_and(PyIntObject *v, PyIntObject *w)
 887 {
 888         register long a, b;
 889         CONVERT_TO_LONG(v, a);
 890         CONVERT_TO_LONG(w, b);
 891         return PyInt_FromLong(a & b);
 892 }
 893
 894 static PyObject *
 895 int_xor(PyIntObject *v, PyIntObject *w)
 896 {
 897         register long a, b;
 898         CONVERT_TO_LONG(v, a);
 899         CONVERT_TO_LONG(w, b);
 900         return PyInt_FromLong(a ^ b);
 901 }
 902
 903 static PyObject *
 904 int_or(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 int
 913 int_coerce(PyObject **pv, PyObject **pw)
 914 {
 915         if (PyInt_Check(*pw)) {
 916                 Py_INCREF(*pv);
 917                 Py_INCREF(*pw);
 918                 return 0;
 919         }
 920         return 1; /* Can't do it */
 921 }
 922
 923 static PyObject *
 924 int_int(PyIntObject *v)
 925 {
 926         if (PyInt_CheckExact(v))
 927                 Py_INCREF(v);
 928         else
 929                 v = (PyIntObject *)PyInt_FromLong(v->ob_ival);
 930         return (PyObject *)v;
 931 }
 932
 933 static PyObject *
 934 int_long(PyIntObject *v)
 935 {
 936         return PyLong_FromLong((v -> ob_ival));
 937 }
 938
 939 static PyObject *
 940 int_float(PyIntObject *v)
 941 {
 942         return PyFloat_FromDouble((double)(v -> ob_ival));
 943 }
 944
 945 static PyObject *
 946 int_oct(PyIntObject *v)
 947 {
 948         char buf[100];
 949         long x = v -> ob_ival;
 950         if (x < 0)
 951                 PyOS_snprintf(buf, sizeof(buf), "-0%lo", -x);
 952         else if (x == 0)
 953                 strcpy(buf, "0");
 954         else
 955                 PyOS_snprintf(buf, sizeof(buf), "0%lo", x);
 956         return PyString_FromString(buf);
 957 }
 958
 959 static PyObject *
 960 int_hex(PyIntObject *v)
 961 {
 962         char buf[100];
 963         long x = v -> ob_ival;
 964         if (x < 0)
 965                 PyOS_snprintf(buf, sizeof(buf), "-0x%lx", -x);
 966         else
 967                 PyOS_snprintf(buf, sizeof(buf), "0x%lx", x);
 968         return PyString_FromString(buf);
 969 }
 970
 971 static PyObject *
 972 int_subtype_new(PyTypeObject *type, PyObject *args, PyObject *kwds);
 973
 974 static PyObject *
 975 int_new(PyTypeObject *type, PyObject *args, PyObject *kwds)
 976 {
 977         PyObject *x = NULL;
 978         int base = -909;
 979         static char *kwlist[] = {"x", "base", 0};
 980
 981         if (type != &PyInt_Type)
 982                 return int_subtype_new(type, args, kwds); /* Wimp out */
 983         if (!PyArg_ParseTupleAndKeywords(args, kwds, "|Oi:int", kwlist,
 984                                          &x, &base))
 985                 return NULL;
 986         if (x == NULL)
 987                 return PyInt_FromLong(0L);
 988         if (base == -909)
 989                 return PyNumber_Int(x);
 990         if (PyString_Check(x)) {
 991                 /* Since PyInt_FromString doesn't have a length parameter,
 992                  * check here for possible NULs in the string. */
 993                 char *string = PyString_AS_STRING(x);
 994                 if (strlen(string) != PyString_Size(x)) {
 995                         /* create a repr() of the input string,
 996                          * just like PyInt_FromString does */
 997                         PyObject *srepr;
 998                         srepr = PyObject_Repr(x);
 999                         if (srepr == NULL)
1000                                 return NULL;
1001                         PyErr_Format(PyExc_ValueError,
1002                              "invalid literal for int() with base %d: %s",
1003                              base, PyString_AS_STRING(srepr));
1004                         Py_DECREF(srepr);
1005                         return NULL;
1006                 }
1007                 return PyInt_FromString(string, NULL, base);
1008         }
1009 #ifdef Py_USING_UNICODE
1010         if (PyUnicode_Check(x))
1011                 return PyInt_FromUnicode(PyUnicode_AS_UNICODE(x),
1012                                          PyUnicode_GET_SIZE(x),
1013                                          base);
1014 #endif
1015         PyErr_SetString(PyExc_TypeError,
1016                         "int() can't convert non-string with explicit base");
1017         return NULL;
1018 }
1019
1020 /* Wimpy, slow approach to tp_new calls for subtypes of int:
1021    first create a regular int from whatever arguments we got,
1022    then allocate a subtype instance and initialize its ob_ival
1023    from the regular int.  The regular int is then thrown away.
1024 */
1025 static PyObject *
1026 int_subtype_new(PyTypeObject *type, PyObject *args, PyObject *kwds)
1027 {
1028         PyObject *tmp, *newobj;
1029         long ival;
1030
1031         assert(PyType_IsSubtype(type, &PyInt_Type));
1032         tmp = int_new(&PyInt_Type, args, kwds);
1033         if (tmp == NULL)
1034                 return NULL;
1035         if (!PyInt_Check(tmp)) {
1036                 ival = PyLong_AsLong(tmp);
1037                 if (ival == -1 && PyErr_Occurred()) {
1038                         Py_DECREF(tmp);
1039                         return NULL;
1040                 }
1041         } else {
1042                 ival = ((PyIntObject *)tmp)->ob_ival;
1043         }
1044
1045         newobj = type->tp_alloc(type, 0);
1046         if (newobj == NULL) {
1047                 Py_DECREF(tmp);
1048                 return NULL;
1049         }
1050         ((PyIntObject *)newobj)->ob_ival = ival;
1051         Py_DECREF(tmp);
1052         return newobj;
1053 }
1054
1055 static PyObject *
1056 int_getnewargs(PyIntObject *v)
1057 {
1058         return Py_BuildValue("(l)", v->ob_ival);
1059 }
1060
1061 static PyMethodDef int_methods[] = {
1062         {"__getnewargs__",      (PyCFunction)int_getnewargs,    METH_NOARGS},
1063         {NULL,          NULL}           /* sentinel */
1064 };
1065
1066 PyDoc_STRVAR(int_doc,
1067 "int(x[, base]) -> integer\n\
1068 \n\
1069 Convert a string or number to an integer, if possible.  A floating point\n\
1070 argument will be truncated towards zero (this does not include a string\n\
1071 representation of a floating point number!)  When converting a string, use\n\
1072 the optional base.  It is an error to supply a base when converting a\n\
1073 non-string. If the argument is outside the integer range a long object\n\
1074 will be returned instead.");
1075
1076 static PyNumberMethods int_as_number = {
1077         (binaryfunc)int_add,    /*nb_add*/
1078         (binaryfunc)int_sub,    /*nb_subtract*/
1079         (binaryfunc)int_mul,    /*nb_multiply*/
1080         (binaryfunc)int_classic_div, /*nb_divide*/
1081         (binaryfunc)int_mod,    /*nb_remainder*/
1082         (binaryfunc)int_divmod, /*nb_divmod*/
1083         (ternaryfunc)int_pow,   /*nb_power*/
1084         (unaryfunc)int_neg,     /*nb_negative*/
1085         (unaryfunc)int_pos,     /*nb_positive*/
1086         (unaryfunc)int_abs,     /*nb_absolute*/
1087         (inquiry)int_nonzero,   /*nb_nonzero*/
1088         (unaryfunc)int_invert,  /*nb_invert*/
1089         (binaryfunc)int_lshift, /*nb_lshift*/
1090         (binaryfunc)int_rshift, /*nb_rshift*/
1091         (binaryfunc)int_and,    /*nb_and*/
1092         (binaryfunc)int_xor,    /*nb_xor*/
1093         (binaryfunc)int_or,     /*nb_or*/
1094         int_coerce,             /*nb_coerce*/
1095         (unaryfunc)int_int,     /*nb_int*/
1096         (unaryfunc)int_long,    /*nb_long*/
1097         (unaryfunc)int_float,   /*nb_float*/
1098         (unaryfunc)int_oct,     /*nb_oct*/
1099         (unaryfunc)int_hex,     /*nb_hex*/
1100         0,                      /*nb_inplace_add*/
1101         0,                      /*nb_inplace_subtract*/
1102         0,                      /*nb_inplace_multiply*/
1103         0,                      /*nb_inplace_divide*/
1104         0,                      /*nb_inplace_remainder*/
1105         0,                      /*nb_inplace_power*/
1106         0,                      /*nb_inplace_lshift*/
1107         0,                      /*nb_inplace_rshift*/
1108         0,                      /*nb_inplace_and*/
1109         0,                      /*nb_inplace_xor*/
1110         0,                      /*nb_inplace_or*/
1111         (binaryfunc)int_div,    /* nb_floor_divide */
1112         int_true_divide,        /* nb_true_divide */
1113         0,                      /* nb_inplace_floor_divide */
1114         0,                      /* nb_inplace_true_divide */
1115         (unaryfunc)int_int,     /* nb_index */
1116 };
1117
1118 PyTypeObject PyInt_Type = {
1119         PyObject_HEAD_INIT(&PyType_Type)
1120         0,
1121         "int",
1122         sizeof(PyIntObject),
1123         0,
1124         (destructor)int_dealloc,                /* tp_dealloc */
1125         (printfunc)int_print,                   /* tp_print */
1126         0,                                      /* tp_getattr */
1127         0,                                      /* tp_setattr */
1128         (cmpfunc)int_compare,                   /* tp_compare */
1129         (reprfunc)int_repr,                     /* tp_repr */
1130         &int_as_number,                         /* tp_as_number */
1131         0,                                      /* tp_as_sequence */
1132         0,                                      /* tp_as_mapping */
1133         (hashfunc)int_hash,                     /* tp_hash */
1134         0,                                      /* tp_call */
1135         (reprfunc)int_repr,                     /* tp_str */
1136         PyObject_GenericGetAttr,                /* tp_getattro */
1137         0,                                      /* tp_setattro */
1138         0,                                      /* tp_as_buffer */
1139         Py_TPFLAGS_DEFAULT | Py_TPFLAGS_CHECKTYPES |
1140                 Py_TPFLAGS_BASETYPE,            /* tp_flags */
1141         int_doc,                                /* tp_doc */
1142         0,                                      /* tp_traverse */
1143         0,                                      /* tp_clear */
1144         0,                                      /* tp_richcompare */
1145         0,                                      /* tp_weaklistoffset */
1146         0,                                      /* tp_iter */
1147         0,                                      /* tp_iternext */
1148         int_methods,                            /* tp_methods */
1149         0,                                      /* tp_members */
1150         0,                                      /* tp_getset */
1151         0,                                      /* tp_base */
1152         0,                                      /* tp_dict */
1153         0,                                      /* tp_descr_get */
1154         0,                                      /* tp_descr_set */
1155         0,                                      /* tp_dictoffset */
1156         0,                                      /* tp_init */
1157         0,                                      /* tp_alloc */
1158         int_new,                                /* tp_new */
1159         (freefunc)int_free,                     /* tp_free */
1160 };
1161
1162 int
1163 _PyInt_Init(void)
1164 {
1165         PyIntObject *v;
1166         int ival;
1167 #if NSMALLNEGINTS + NSMALLPOSINTS > 0
1168         for (ival = -NSMALLNEGINTS; ival < NSMALLPOSINTS; ival++) {
1169               if (!free_list && (free_list = fill_free_list()) == NULL)
1170                         return 0;
1171                 /* PyObject_New is inlined */
1172                 v = free_list;
1173                 free_list = (PyIntObject *)v->ob_type;
1174                 PyObject_INIT(v, &PyInt_Type);
1175                 v->ob_ival = ival;
1176                 small_ints[ival + NSMALLNEGINTS] = v;
1177         }
1178 #endif
1179         return 1;
1180 }
1181
1182 void
1183 PyInt_Fini(void)
1184 {
1185         PyIntObject *p;
1186         PyIntBlock *list, *next;
1187         int i;
1188         unsigned int ctr;
1189         int bc, bf;     /* block count, number of freed blocks */
1190         int irem, isum; /* remaining unfreed ints per block, total */
1191
1192 #if NSMALLNEGINTS + NSMALLPOSINTS > 0
1193         PyIntObject **q;
1194
1195         i = NSMALLNEGINTS + NSMALLPOSINTS;
1196         q = small_ints;
1197         while (--i >= 0) {
1198                 Py_XDECREF(*q);
1199                 *q++ = NULL;
1200         }
1201 #endif
1202         bc = 0;
1203         bf = 0;
1204         isum = 0;
1205         list = block_list;
1206         block_list = NULL;
1207         free_list = NULL;
1208         while (list != NULL) {
1209                 bc++;
1210                 irem = 0;
1211                 for (ctr = 0, p = &list->objects[0];
1212                      ctr < N_INTOBJECTS;
1213                      ctr++, p++) {
1214                         if (PyInt_CheckExact(p) && p->ob_refcnt != 0)
1215                                 irem++;
1216                 }
1217                 next = list->next;
1218                 if (irem) {
1219                         list->next = block_list;
1220                         block_list = list;
1221                         for (ctr = 0, p = &list->objects[0];
1222                              ctr < N_INTOBJECTS;
1223                              ctr++, p++) {
1224                                 if (!PyInt_CheckExact(p) ||
1225                                     p->ob_refcnt == 0) {
1226                                         p->ob_type = (struct _typeobject *)
1227                                                 free_list;
1228                                         free_list = p;
1229                                 }
1230 #if NSMALLNEGINTS + NSMALLPOSINTS > 0
1231                                 else if (-NSMALLNEGINTS <= p->ob_ival &&
1232                                          p->ob_ival < NSMALLPOSINTS &&
1233                                          small_ints[p->ob_ival +
1234                                                     NSMALLNEGINTS] == NULL) {
1235                                         Py_INCREF(p);
1236                                         small_ints[p->ob_ival +
1237                                                    NSMALLNEGINTS] = p;
1238                                 }
1239 #endif
1240                         }
1241                 }
1242                 else {
1243                         PyMem_FREE(list);
1244                         bf++;
1245                 }
1246                 isum += irem;
1247                 list = next;
1248         }
1249         if (!Py_VerboseFlag)
1250                 return;
1251         fprintf(stderr, "# cleanup ints");
1252         if (!isum) {
1253                 fprintf(stderr, "\n");
1254         }
1255         else {
1256                 fprintf(stderr,
1257                         ": %d unfreed int%s in %d out of %d block%s\n",
1258                         isum, isum == 1 ? "" : "s",
1259                         bc - bf, bc, bc == 1 ? "" : "s");
1260         }
1261         if (Py_VerboseFlag > 1) {
1262                 list = block_list;
1263                 while (list != NULL) {
1264                         for (ctr = 0, p = &list->objects[0];
1265                              ctr < N_INTOBJECTS;
1266                              ctr++, p++) {
1267                                 if (PyInt_CheckExact(p) && p->ob_refcnt != 0)
1268                                         /* XXX(twouters) cast refcount to
1269                                            long until %zd is universally
1270                                            available
1271                                          */
1272                                         fprintf(stderr,
1273                                 "#   <int at %p, refcnt=%ld, val=%ld>\n",
1274                                                 p, (long)p->ob_refcnt,
1275                                                 p->ob_ival);
1276                         }
1277                         list = list->next;
1278                 }
1279         }
1280 }