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         if (op && !PyInt_CheckExact(op) && PyLong_Check(op))
 197                 return _PyLong_AsSsize_t(op);
 198 #if SIZEOF_SIZE_T == SIZEOF_LONG
 199         return PyInt_AsLong(op);
 200 #else
 201
 202         if (op && PyInt_Check(op))
 203                 return PyInt_AS_LONG((PyIntObject*) op);
 204
 205         if (op == NULL || (nb = op->ob_type->tp_as_number) == NULL ||
 206             (nb->nb_int == NULL && nb->nb_long == 0)) {
 207                 PyErr_SetString(PyExc_TypeError, "an integer is required");
 208                 return -1;
 209         }
 210
 211         if (nb->nb_long != 0) {
 212                 io = (PyIntObject*) (*nb->nb_long) (op);
 213         } else {
 214                 io = (PyIntObject*) (*nb->nb_int) (op);
 215         }
 216         if (io == NULL)
 217                 return -1;
 218         if (!PyInt_Check(io)) {
 219                 if (PyLong_Check(io)) {
 220                         /* got a long? => retry int conversion */
 221                         val = _PyLong_AsSsize_t((PyObject *)io);
 222                         Py_DECREF(io);
 223                         if ((val == -1) && PyErr_Occurred())
 224                                 return -1;
 225                         return val;
 226                 }
 227                 else
 228                 {
 229                         Py_DECREF(io);
 230                         PyErr_SetString(PyExc_TypeError,
 231                                         "nb_int should return int object");
 232                         return -1;
 233                 }
 234         }
 235
 236         val = PyInt_AS_LONG(io);
 237         Py_DECREF(io);
 238
 239         return val;
 240 #endif
 241 }
 242
 243 unsigned long
 244 PyInt_AsUnsignedLongMask(register PyObject *op)
 245 {
 246         PyNumberMethods *nb;
 247         PyIntObject *io;
 248         unsigned long val;
 249
 250         if (op && PyInt_Check(op))
 251                 return PyInt_AS_LONG((PyIntObject*) op);
 252         if (op && PyLong_Check(op))
 253                 return PyLong_AsUnsignedLongMask(op);
 254
 255         if (op == NULL || (nb = op->ob_type->tp_as_number) == NULL ||
 256             nb->nb_int == NULL) {
 257                 PyErr_SetString(PyExc_TypeError, "an integer is required");
 258                 return (unsigned long)-1;
 259         }
 260
 261         io = (PyIntObject*) (*nb->nb_int) (op);
 262         if (io == NULL)
 263                 return (unsigned long)-1;
 264         if (!PyInt_Check(io)) {
 265                 if (PyLong_Check(io)) {
 266                         val = PyLong_AsUnsignedLongMask((PyObject *)io);
 267                         Py_DECREF(io);
 268                         if (PyErr_Occurred())
 269                                 return (unsigned long)-1;
 270                         return val;
 271                 }
 272                 else
 273                 {
 274                         Py_DECREF(io);
 275                         PyErr_SetString(PyExc_TypeError,
 276                                         "nb_int should return int object");
 277                         return (unsigned long)-1;
 278                 }
 279         }
 280
 281         val = PyInt_AS_LONG(io);
 282         Py_DECREF(io);
 283
 284         return val;
 285 }
 286
 287 #ifdef HAVE_LONG_LONG
 288 unsigned PY_LONG_LONG
 289 PyInt_AsUnsignedLongLongMask(register PyObject *op)
 290 {
 291         PyNumberMethods *nb;
 292         PyIntObject *io;
 293         unsigned PY_LONG_LONG val;
 294
 295         if (op && PyInt_Check(op))
 296                 return PyInt_AS_LONG((PyIntObject*) op);
 297         if (op && PyLong_Check(op))
 298                 return PyLong_AsUnsignedLongLongMask(op);
 299
 300         if (op == NULL || (nb = op->ob_type->tp_as_number) == NULL ||
 301             nb->nb_int == NULL) {
 302                 PyErr_SetString(PyExc_TypeError, "an integer is required");
 303                 return (unsigned PY_LONG_LONG)-1;
 304         }
 305
 306         io = (PyIntObject*) (*nb->nb_int) (op);
 307         if (io == NULL)
 308                 return (unsigned PY_LONG_LONG)-1;
 309         if (!PyInt_Check(io)) {
 310                 if (PyLong_Check(io)) {
 311                         val = PyLong_AsUnsignedLongLongMask((PyObject *)io);
 312                         Py_DECREF(io);
 313                         if (PyErr_Occurred())
 314                                 return (unsigned PY_LONG_LONG)-1;
 315                         return val;
 316                 }
 317                 else
 318                 {
 319                         Py_DECREF(io);
 320                         PyErr_SetString(PyExc_TypeError,
 321                                         "nb_int should return int object");
 322                         return (unsigned PY_LONG_LONG)-1;
 323                 }
 324         }
 325
 326         val = PyInt_AS_LONG(io);
 327         Py_DECREF(io);
 328
 329         return val;
 330 }
 331 #endif
 332
 333 PyObject *
 334 PyInt_FromString(char *s, char **pend, int base)
 335 {
 336         char *end;
 337         long x;
 338         Py_ssize_t slen;
 339         PyObject *sobj, *srepr;
 340
 341         if ((base != 0 && base < 2) || base > 36) {
 342                 PyErr_SetString(PyExc_ValueError,
 343                                 "int() base must be >= 2 and <= 36");
 344                 return NULL;
 345         }
 346
 347         while (*s && isspace(Py_CHARMASK(*s)))
 348                 s++;
 349         errno = 0;
 350         if (base == 0 && s[0] == '0') {
 351                 x = (long) PyOS_strtoul(s, &end, base);
 352                 if (x < 0)
 353                         return PyLong_FromString(s, pend, base);
 354         }
 355         else
 356                 x = PyOS_strtol(s, &end, base);
 357         if (end == s || !isalnum(Py_CHARMASK(end[-1])))
 358                 goto bad;
 359         while (*end && isspace(Py_CHARMASK(*end)))
 360                 end++;
 361         if (*end != '\0') {
 362   bad:
 363                 slen = strlen(s) < 200 ? strlen(s) : 200;
 364                 sobj = PyString_FromStringAndSize(s, slen);
 365                 if (sobj == NULL)
 366                         return NULL;
 367                 srepr = PyObject_Repr(sobj);
 368                 Py_DECREF(sobj);
 369                 if (srepr == NULL)
 370                         return NULL;
 371                 PyErr_Format(PyExc_ValueError,
 372                              "invalid literal for int() with base %d: %s",
 373                              base, PyString_AS_STRING(srepr));
 374                 Py_DECREF(srepr);
 375                 return NULL;
 376         }
 377         else if (errno != 0)
 378                 return PyLong_FromString(s, pend, base);
 379         if (pend)
 380                 *pend = end;
 381         return PyInt_FromLong(x);
 382 }
 383
 384 #ifdef Py_USING_UNICODE
 385 PyObject *
 386 PyInt_FromUnicode(Py_UNICODE *s, Py_ssize_t length, int base)
 387 {
 388         PyObject *result;
 389         char *buffer = (char *)PyMem_MALLOC(length+1);
 390
 391         if (buffer == NULL)
 392                 return NULL;
 393
 394         if (PyUnicode_EncodeDecimal(s, length, buffer, NULL)) {
 395                 PyMem_FREE(buffer);
 396                 return NULL;
 397         }
 398         result = PyInt_FromString(buffer, NULL, base);
 399         PyMem_FREE(buffer);
 400         return result;
 401 }
 402 #endif
 403
 404 /* Methods */
 405
 406 /* Integers are seen as the "smallest" of all numeric types and thus
 407    don't have any knowledge about conversion of other types to
 408    integers. */
 409
 410 #define CONVERT_TO_LONG(obj, lng)               \
 411         if (PyInt_Check(obj)) {                 \
 412                 lng = PyInt_AS_LONG(obj);       \
 413         }                                       \
 414         else {                                  \
 415                 Py_INCREF(Py_NotImplemented);   \
 416                 return Py_NotImplemented;       \
 417         }
 418
 419 /* ARGSUSED */
 420 static int
 421 int_print(PyIntObject *v, FILE *fp, int flags)
 422      /* flags -- not used but required by interface */
 423 {
 424         fprintf(fp, "%ld", v->ob_ival);
 425         return 0;
 426 }
 427
 428 static PyObject *
 429 int_repr(PyIntObject *v)
 430 {
 431         char buf[64];
 432         PyOS_snprintf(buf, sizeof(buf), "%ld", v->ob_ival);
 433         return PyString_FromString(buf);
 434 }
 435
 436 static int
 437 int_compare(PyIntObject *v, PyIntObject *w)
 438 {
 439         register long i = v->ob_ival;
 440         register long j = w->ob_ival;
 441         return (i < j) ? -1 : (i > j) ? 1 : 0;
 442 }
 443
 444 static long
 445 int_hash(PyIntObject *v)
 446 {
 447         /* XXX If this is changed, you also need to change the way
 448            Python's long, float and complex types are hashed. */
 449         long x = v -> ob_ival;
 450         if (x == -1)
 451                 x = -2;
 452         return x;
 453 }
 454
 455 static PyObject *
 456 int_add(PyIntObject *v, PyIntObject *w)
 457 {
 458         register long a, b, x;
 459         CONVERT_TO_LONG(v, a);
 460         CONVERT_TO_LONG(w, b);
 461         x = a + b;
 462         if ((x^a) >= 0 || (x^b) >= 0)
 463                 return PyInt_FromLong(x);
 464         return PyLong_Type.tp_as_number->nb_add((PyObject *)v, (PyObject *)w);
 465 }
 466
 467 static PyObject *
 468 int_sub(PyIntObject *v, PyIntObject *w)
 469 {
 470         register long a, b, x;
 471         CONVERT_TO_LONG(v, a);
 472         CONVERT_TO_LONG(w, b);
 473         x = a - b;
 474         if ((x^a) >= 0 || (x^~b) >= 0)
 475                 return PyInt_FromLong(x);
 476         return PyLong_Type.tp_as_number->nb_subtract((PyObject *)v,
 477                                                      (PyObject *)w);
 478 }
 479
 480 /*
 481 Integer overflow checking for * is painful:  Python tried a couple ways, but
 482 they didn't work on all platforms, or failed in endcases (a product of
 483 -sys.maxint-1 has been a particular pain).
 484
 485 Here's another way:
 486
 487 The native long product x*y is either exactly right or *way* off, being
 488 just the last n bits of the true product, where n is the number of bits
 489 in a long (the delivered product is the true product plus i*2**n for
 490 some integer i).
 491
 492 The native double product (double)x * (double)y is subject to three
 493 rounding errors:  on a sizeof(long)==8 box, each cast to double can lose
 494 info, and even on a sizeof(long)==4 box, the multiplication can lose info.
 495 But, unlike the native long product, it's not in *range* trouble:  even
 496 if sizeof(long)==32 (256-bit longs), the product easily fits in the
 497 dynamic range of a double.  So the leading 50 (or so) bits of the double
 498 product are correct.
 499
 500 We check these two ways against each other, and declare victory if they're
 501 approximately the same.  Else, because the native long product is the only
 502 one that can lose catastrophic amounts of information, it's the native long
 503 product that must have overflowed.
 504 */
 505
 506 static PyObject *
 507 int_mul(PyObject *v, PyObject *w)
 508 {
 509         long a, b;
 510         long longprod;                  /* a*b in native long arithmetic */
 511         double doubled_longprod;        /* (double)longprod */
 512         double doubleprod;              /* (double)a * (double)b */
 513
 514         CONVERT_TO_LONG(v, a);
 515         CONVERT_TO_LONG(w, b);
 516         longprod = a * b;
 517         doubleprod = (double)a * (double)b;
 518         doubled_longprod = (double)longprod;
 519
 520         /* Fast path for normal case:  small multiplicands, and no info
 521            is lost in either method. */
 522         if (doubled_longprod == doubleprod)
 523                 return PyInt_FromLong(longprod);
 524
 525         /* Somebody somewhere lost info.  Close enough, or way off?  Note
 526            that a != 0 and b != 0 (else doubled_longprod == doubleprod == 0).
 527            The difference either is or isn't significant compared to the
 528            true value (of which doubleprod is a good approximation).
 529         */
 530         {
 531                 const double diff = doubled_longprod - doubleprod;
 532                 const double absdiff = diff >= 0.0 ? diff : -diff;
 533                 const double absprod = doubleprod >= 0.0 ? doubleprod :
 534                                                           -doubleprod;
 535                 /* absdiff/absprod <= 1/32 iff
 536                    32 * absdiff <= absprod -- 5 good bits is "close enough" */
 537                 if (32.0 * absdiff <= absprod)
 538                         return PyInt_FromLong(longprod);
 539                 else
 540                         return PyLong_Type.tp_as_number->nb_multiply(v, w);
 541         }
 542 }
 543
 544 /* Return type of i_divmod */
 545 enum divmod_result {
 546         DIVMOD_OK,              /* Correct result */
 547         DIVMOD_OVERFLOW,        /* Overflow, try again using longs */
 548         DIVMOD_ERROR            /* Exception raised */
 549 };
 550
 551 static enum divmod_result
 552 i_divmod(register long x, register long y,
 553          long *p_xdivy, long *p_xmody)
 554 {
 555         long xdivy, xmody;
 556
 557         if (y == 0) {
 558                 PyErr_SetString(PyExc_ZeroDivisionError,
 559                                 "integer division or modulo by zero");
 560                 return DIVMOD_ERROR;
 561         }
 562         /* (-sys.maxint-1)/-1 is the only overflow case. */
 563         if (y == -1 && x < 0 && x == -x)
 564                 return DIVMOD_OVERFLOW;
 565         xdivy = x / y;
 566         xmody = x - xdivy * y;
 567         /* If the signs of x and y differ, and the remainder is non-0,
 568          * C89 doesn't define whether xdivy is now the floor or the
 569          * ceiling of the infinitely precise quotient.  We want the floor,
 570          * and we have it iff the remainder's sign matches y's.
 571          */
 572         if (xmody && ((y ^ xmody) < 0) /* i.e. and signs differ */) {
 573                 xmody += y;
 574                 --xdivy;
 575                 assert(xmody && ((y ^ xmody) >= 0));
 576         }
 577         *p_xdivy = xdivy;
 578         *p_xmody = xmody;
 579         return DIVMOD_OK;
 580 }
 581
 582 static PyObject *
 583 int_div(PyIntObject *x, PyIntObject *y)
 584 {
 585         long xi, yi;
 586         long d, m;
 587         CONVERT_TO_LONG(x, xi);
 588         CONVERT_TO_LONG(y, yi);
 589         switch (i_divmod(xi, yi, &d, &m)) {
 590         case DIVMOD_OK:
 591                 return PyInt_FromLong(d);
 592         case DIVMOD_OVERFLOW:
 593                 return PyLong_Type.tp_as_number->nb_divide((PyObject *)x,
 594                                                            (PyObject *)y);
 595         default:
 596                 return NULL;
 597         }
 598 }
 599
 600 static PyObject *
 601 int_classic_div(PyIntObject *x, PyIntObject *y)
 602 {
 603         long xi, yi;
 604         long d, m;
 605         CONVERT_TO_LONG(x, xi);
 606         CONVERT_TO_LONG(y, yi);
 607         if (Py_DivisionWarningFlag &&
 608             PyErr_Warn(PyExc_DeprecationWarning, "classic int division") < 0)
 609                 return NULL;
 610         switch (i_divmod(xi, yi, &d, &m)) {
 611         case DIVMOD_OK:
 612                 return PyInt_FromLong(d);
 613         case DIVMOD_OVERFLOW:
 614                 return PyLong_Type.tp_as_number->nb_divide((PyObject *)x,
 615                                                            (PyObject *)y);
 616         default:
 617                 return NULL;
 618         }
 619 }
 620
 621 static PyObject *
 622 int_true_divide(PyObject *v, PyObject *w)
 623 {
 624         /* If they aren't both ints, give someone else a chance.  In
 625            particular, this lets int/long get handled by longs, which
 626            underflows to 0 gracefully if the long is too big to convert
 627            to float. */
 628         if (PyInt_Check(v) && PyInt_Check(w))
 629                 return PyFloat_Type.tp_as_number->nb_true_divide(v, w);
 630         Py_INCREF(Py_NotImplemented);
 631         return Py_NotImplemented;
 632 }
 633
 634 static PyObject *
 635 int_mod(PyIntObject *x, PyIntObject *y)
 636 {
 637         long xi, yi;
 638         long d, m;
 639         CONVERT_TO_LONG(x, xi);
 640         CONVERT_TO_LONG(y, yi);
 641         switch (i_divmod(xi, yi, &d, &m)) {
 642         case DIVMOD_OK:
 643                 return PyInt_FromLong(m);
 644         case DIVMOD_OVERFLOW:
 645                 return PyLong_Type.tp_as_number->nb_remainder((PyObject *)x,
 646                                                               (PyObject *)y);
 647         default:
 648                 return NULL;
 649         }
 650 }
 651
 652 static PyObject *
 653 int_divmod(PyIntObject *x, PyIntObject *y)
 654 {
 655         long xi, yi;
 656         long d, m;
 657         CONVERT_TO_LONG(x, xi);
 658         CONVERT_TO_LONG(y, yi);
 659         switch (i_divmod(xi, yi, &d, &m)) {
 660         case DIVMOD_OK:
 661                 return Py_BuildValue("(ll)", d, m);
 662         case DIVMOD_OVERFLOW:
 663                 return PyLong_Type.tp_as_number->nb_divmod((PyObject *)x,
 664                                                            (PyObject *)y);
 665         default:
 666                 return NULL;
 667         }
 668 }
 669
 670 static PyObject *
 671 int_pow(PyIntObject *v, PyIntObject *w, PyIntObject *z)
 672 {
 673         register long iv, iw, iz=0, ix, temp, prev;
 674         CONVERT_TO_LONG(v, iv);
 675         CONVERT_TO_LONG(w, iw);
 676         if (iw < 0) {
 677                 if ((PyObject *)z != Py_None) {
 678                         PyErr_SetString(PyExc_TypeError, "pow() 2nd argument "
 679                              "cannot be negative when 3rd argument specified");
 680                         return NULL;
 681                 }
 682                 /* Return a float.  This works because we know that
 683                    this calls float_pow() which converts its
 684                    arguments to double. */
 685                 return PyFloat_Type.tp_as_number->nb_power(
 686                         (PyObject *)v, (PyObject *)w, (PyObject *)z);
 687         }
 688         if ((PyObject *)z != Py_None) {
 689                 CONVERT_TO_LONG(z, iz);
 690                 if (iz == 0) {
 691                         PyErr_SetString(PyExc_ValueError,
 692                                         "pow() 3rd argument cannot be 0");
 693                         return NULL;
 694                 }
 695         }
 696         /*
 697          * XXX: The original exponentiation code stopped looping
 698          * when temp hit zero; this code will continue onwards
 699          * unnecessarily, but at least it won't cause any errors.
 700          * Hopefully the speed improvement from the fast exponentiation
 701          * will compensate for the slight inefficiency.
 702          * XXX: Better handling of overflows is desperately needed.
 703          */
 704         temp = iv;
 705         ix = 1;
 706         while (iw > 0) {
 707                 prev = ix;      /* Save value for overflow check */
 708                 if (iw & 1) {
 709                         ix = ix*temp;
 710                         if (temp == 0)
 711                                 break; /* Avoid ix / 0 */
 712                         if (ix / temp != prev) {
 713                                 return PyLong_Type.tp_as_number->nb_power(
 714                                         (PyObject *)v,
 715                                         (PyObject *)w,
 716                                         (PyObject *)z);
 717                         }
 718                 }
 719                 iw >>= 1;       /* Shift exponent down by 1 bit */
 720                 if (iw==0) break;
 721                 prev = temp;
 722                 temp *= temp;   /* Square the value of temp */
 723                 if (prev != 0 && temp / prev != prev) {
 724                         return PyLong_Type.tp_as_number->nb_power(
 725                                 (PyObject *)v, (PyObject *)w, (PyObject *)z);
 726                 }
 727                 if (iz) {
 728                         /* If we did a multiplication, perform a modulo */
 729                         ix = ix % iz;
 730                         temp = temp % iz;
 731                 }
 732         }
 733         if (iz) {
 734                 long div, mod;
 735                 switch (i_divmod(ix, iz, &div, &mod)) {
 736                 case DIVMOD_OK:
 737                         ix = mod;
 738                         break;
 739                 case DIVMOD_OVERFLOW:
 740                         return PyLong_Type.tp_as_number->nb_power(
 741                                 (PyObject *)v, (PyObject *)w, (PyObject *)z);
 742                 default:
 743                         return NULL;
 744                 }
 745         }
 746         return PyInt_FromLong(ix);
 747 }
 748
 749 static PyObject *
 750 int_neg(PyIntObject *v)
 751 {
 752         register long a, x;
 753         a = v->ob_ival;
 754         x = -a;
 755         if (a < 0 && x < 0) {
 756                 PyObject *o = PyLong_FromLong(a);
 757                 if (o != NULL) {
 758                         PyObject *result = PyNumber_Negative(o);
 759                         Py_DECREF(o);
 760                         return result;
 761                 }
 762                 return NULL;
 763         }
 764         return PyInt_FromLong(x);
 765 }
 766
 767 static PyObject *
 768 int_pos(PyIntObject *v)
 769 {
 770         if (PyInt_CheckExact(v)) {
 771                 Py_INCREF(v);
 772                 return (PyObject *)v;
 773         }
 774         else
 775                 return PyInt_FromLong(v->ob_ival);
 776 }
 777
 778 static PyObject *
 779 int_abs(PyIntObject *v)
 780 {
 781         if (v->ob_ival >= 0)
 782                 return int_pos(v);
 783         else
 784                 return int_neg(v);
 785 }
 786
 787 static int
 788 int_nonzero(PyIntObject *v)
 789 {
 790         return v->ob_ival != 0;
 791 }
 792
 793 static PyObject *
 794 int_invert(PyIntObject *v)
 795 {
 796         return PyInt_FromLong(~v->ob_ival);
 797 }
 798
 799 static PyObject *
 800 int_lshift(PyIntObject *v, PyIntObject *w)
 801 {
 802         long a, b, c;
 803         PyObject *vv, *ww, *result;
 804
 805         CONVERT_TO_LONG(v, a);
 806         CONVERT_TO_LONG(w, b);
 807         if (b < 0) {
 808                 PyErr_SetString(PyExc_ValueError, "negative shift count");
 809                 return NULL;
 810         }
 811         if (a == 0 || b == 0)
 812                 return int_pos(v);
 813         if (b >= LONG_BIT) {
 814                 vv = PyLong_FromLong(PyInt_AS_LONG(v));
 815                 if (vv == NULL)
 816                         return NULL;
 817                 ww = PyLong_FromLong(PyInt_AS_LONG(w));
 818                 if (ww == NULL) {
 819                         Py_DECREF(vv);
 820                         return NULL;
 821                 }
 822                 result = PyNumber_Lshift(vv, ww);
 823                 Py_DECREF(vv);
 824                 Py_DECREF(ww);
 825                 return result;
 826         }
 827         c = a << b;
 828         if (a != Py_ARITHMETIC_RIGHT_SHIFT(long, c, b)) {
 829                 vv = PyLong_FromLong(PyInt_AS_LONG(v));
 830                 if (vv == NULL)
 831                         return NULL;
 832                 ww = PyLong_FromLong(PyInt_AS_LONG(w));
 833                 if (ww == NULL) {
 834                         Py_DECREF(vv);
 835                         return NULL;
 836                 }
 837                 result = PyNumber_Lshift(vv, ww);
 838                 Py_DECREF(vv);
 839                 Py_DECREF(ww);
 840                 return result;
 841         }
 842         return PyInt_FromLong(c);
 843 }
 844
 845 static PyObject *
 846 int_rshift(PyIntObject *v, PyIntObject *w)
 847 {
 848         register long a, b;
 849         CONVERT_TO_LONG(v, a);
 850         CONVERT_TO_LONG(w, b);
 851         if (b < 0) {
 852                 PyErr_SetString(PyExc_ValueError, "negative shift count");
 853                 return NULL;
 854         }
 855         if (a == 0 || b == 0)
 856                 return int_pos(v);
 857         if (b >= LONG_BIT) {
 858                 if (a < 0)
 859                         a = -1;
 860                 else
 861                         a = 0;
 862         }
 863         else {
 864                 a = Py_ARITHMETIC_RIGHT_SHIFT(long, a, b);
 865         }
 866         return PyInt_FromLong(a);
 867 }
 868
 869 static PyObject *
 870 int_and(PyIntObject *v, PyIntObject *w)
 871 {
 872         register long a, b;
 873         CONVERT_TO_LONG(v, a);
 874         CONVERT_TO_LONG(w, b);
 875         return PyInt_FromLong(a & b);
 876 }
 877
 878 static PyObject *
 879 int_xor(PyIntObject *v, PyIntObject *w)
 880 {
 881         register long a, b;
 882         CONVERT_TO_LONG(v, a);
 883         CONVERT_TO_LONG(w, b);
 884         return PyInt_FromLong(a ^ b);
 885 }
 886
 887 static PyObject *
 888 int_or(PyIntObject *v, PyIntObject *w)
 889 {
 890         register long a, b;
 891         CONVERT_TO_LONG(v, a);
 892         CONVERT_TO_LONG(w, b);
 893         return PyInt_FromLong(a | b);
 894 }
 895
 896 static int
 897 int_coerce(PyObject **pv, PyObject **pw)
 898 {
 899         if (PyInt_Check(*pw)) {
 900                 Py_INCREF(*pv);
 901                 Py_INCREF(*pw);
 902                 return 0;
 903         }
 904         return 1; /* Can't do it */
 905 }
 906
 907 static PyObject *
 908 int_int(PyIntObject *v)
 909 {
 910         if (PyInt_CheckExact(v))
 911                 Py_INCREF(v);
 912         else
 913                 v = (PyIntObject *)PyInt_FromLong(v->ob_ival);
 914         return (PyObject *)v;
 915 }
 916
 917 static PyObject *
 918 int_long(PyIntObject *v)
 919 {
 920         return PyLong_FromLong((v -> ob_ival));
 921 }
 922
 923 static PyObject *
 924 int_float(PyIntObject *v)
 925 {
 926         return PyFloat_FromDouble((double)(v -> ob_ival));
 927 }
 928
 929 static PyObject *
 930 int_oct(PyIntObject *v)
 931 {
 932         char buf[100];
 933         long x = v -> ob_ival;
 934         if (x < 0)
 935                 PyOS_snprintf(buf, sizeof(buf), "-0%lo", -x);
 936         else if (x == 0)
 937                 strcpy(buf, "0");
 938         else
 939                 PyOS_snprintf(buf, sizeof(buf), "0%lo", x);
 940         return PyString_FromString(buf);
 941 }
 942
 943 static PyObject *
 944 int_hex(PyIntObject *v)
 945 {
 946         char buf[100];
 947         long x = v -> ob_ival;
 948         if (x < 0)
 949                 PyOS_snprintf(buf, sizeof(buf), "-0x%lx", -x);
 950         else
 951                 PyOS_snprintf(buf, sizeof(buf), "0x%lx", x);
 952         return PyString_FromString(buf);
 953 }
 954
 955 static PyObject *
 956 int_subtype_new(PyTypeObject *type, PyObject *args, PyObject *kwds);
 957
 958 static PyObject *
 959 int_new(PyTypeObject *type, PyObject *args, PyObject *kwds)
 960 {
 961         PyObject *x = NULL;
 962         int base = -909;
 963         static char *kwlist[] = {"x", "base", 0};
 964
 965         if (type != &PyInt_Type)
 966                 return int_subtype_new(type, args, kwds); /* Wimp out */
 967         if (!PyArg_ParseTupleAndKeywords(args, kwds, "|Oi:int", kwlist,
 968                                          &x, &base))
 969                 return NULL;
 970         if (x == NULL)
 971                 return PyInt_FromLong(0L);
 972         if (base == -909)
 973                 return PyNumber_Int(x);
 974         if (PyString_Check(x))
 975                 return PyInt_FromString(PyString_AS_STRING(x), NULL, base);
 976 #ifdef Py_USING_UNICODE
 977         if (PyUnicode_Check(x))
 978                 return PyInt_FromUnicode(PyUnicode_AS_UNICODE(x),
 979                                          PyUnicode_GET_SIZE(x),
 980                                          base);
 981 #endif
 982         PyErr_SetString(PyExc_TypeError,
 983                         "int() can't convert non-string with explicit base");
 984         return NULL;
 985 }
 986
 987 /* Wimpy, slow approach to tp_new calls for subtypes of int:
 988    first create a regular int from whatever arguments we got,
 989    then allocate a subtype instance and initialize its ob_ival
 990    from the regular int.  The regular int is then thrown away.
 991 */
 992 static PyObject *
 993 int_subtype_new(PyTypeObject *type, PyObject *args, PyObject *kwds)
 994 {
 995         PyObject *tmp, *newobj;
 996         long ival;
 997
 998         assert(PyType_IsSubtype(type, &PyInt_Type));
 999         tmp = int_new(&PyInt_Type, args, kwds);
1000         if (tmp == NULL)
1001                 return NULL;
1002         if (!PyInt_Check(tmp)) {
1003                 ival = PyLong_AsLong(tmp);
1004                 if (ival == -1 && PyErr_Occurred()) {
1005                         Py_DECREF(tmp);
1006                         return NULL;
1007                 }
1008         } else {
1009                 ival = ((PyIntObject *)tmp)->ob_ival;
1010         }
1011
1012         newobj = type->tp_alloc(type, 0);
1013         if (newobj == NULL) {
1014                 Py_DECREF(tmp);
1015                 return NULL;
1016         }
1017         ((PyIntObject *)newobj)->ob_ival = ival;
1018         Py_DECREF(tmp);
1019         return newobj;
1020 }
1021
1022 static PyObject *
1023 int_getnewargs(PyIntObject *v)
1024 {
1025         return Py_BuildValue("(l)", v->ob_ival);
1026 }
1027
1028 static PyMethodDef int_methods[] = {
1029         {"__getnewargs__",      (PyCFunction)int_getnewargs,    METH_NOARGS},
1030         {NULL,          NULL}           /* sentinel */
1031 };
1032
1033 PyDoc_STRVAR(int_doc,
1034 "int(x[, base]) -> integer\n\
1035 \n\
1036 Convert a string or number to an integer, if possible.  A floating point\n\
1037 argument will be truncated towards zero (this does not include a string\n\
1038 representation of a floating point number!)  When converting a string, use\n\
1039 the optional base.  It is an error to supply a base when converting a\n\
1040 non-string. If the argument is outside the integer range a long object\n\
1041 will be returned instead.");
1042
1043 static PyNumberMethods int_as_number = {
1044         (binaryfunc)int_add,    /*nb_add*/
1045         (binaryfunc)int_sub,    /*nb_subtract*/
1046         (binaryfunc)int_mul,    /*nb_multiply*/
1047         (binaryfunc)int_classic_div, /*nb_divide*/
1048         (binaryfunc)int_mod,    /*nb_remainder*/
1049         (binaryfunc)int_divmod, /*nb_divmod*/
1050         (ternaryfunc)int_pow,   /*nb_power*/
1051         (unaryfunc)int_neg,     /*nb_negative*/
1052         (unaryfunc)int_pos,     /*nb_positive*/
1053         (unaryfunc)int_abs,     /*nb_absolute*/
1054         (inquiry)int_nonzero,   /*nb_nonzero*/
1055         (unaryfunc)int_invert,  /*nb_invert*/
1056         (binaryfunc)int_lshift, /*nb_lshift*/
1057         (binaryfunc)int_rshift, /*nb_rshift*/
1058         (binaryfunc)int_and,    /*nb_and*/
1059         (binaryfunc)int_xor,    /*nb_xor*/
1060         (binaryfunc)int_or,     /*nb_or*/
1061         int_coerce,             /*nb_coerce*/
1062         (unaryfunc)int_int,     /*nb_int*/
1063         (unaryfunc)int_long,    /*nb_long*/
1064         (unaryfunc)int_float,   /*nb_float*/
1065         (unaryfunc)int_oct,     /*nb_oct*/
1066         (unaryfunc)int_hex,     /*nb_hex*/
1067         0,                      /*nb_inplace_add*/
1068         0,                      /*nb_inplace_subtract*/
1069         0,                      /*nb_inplace_multiply*/
1070         0,                      /*nb_inplace_divide*/
1071         0,                      /*nb_inplace_remainder*/
1072         0,                      /*nb_inplace_power*/
1073         0,                      /*nb_inplace_lshift*/
1074         0,                      /*nb_inplace_rshift*/
1075         0,                      /*nb_inplace_and*/
1076         0,                      /*nb_inplace_xor*/
1077         0,                      /*nb_inplace_or*/
1078         (binaryfunc)int_div,    /* nb_floor_divide */
1079         int_true_divide,        /* nb_true_divide */
1080         0,                      /* nb_inplace_floor_divide */
1081         0,                      /* nb_inplace_true_divide */
1082         PyInt_AsSsize_t,        /* nb_index */
1083 };
1084
1085 PyTypeObject PyInt_Type = {
1086         PyObject_HEAD_INIT(&PyType_Type)
1087         0,
1088         "int",
1089         sizeof(PyIntObject),
1090         0,
1091         (destructor)int_dealloc,                /* tp_dealloc */
1092         (printfunc)int_print,                   /* tp_print */
1093         0,                                      /* tp_getattr */
1094         0,                                      /* tp_setattr */
1095         (cmpfunc)int_compare,                   /* tp_compare */
1096         (reprfunc)int_repr,                     /* tp_repr */
1097         &int_as_number,                         /* tp_as_number */
1098         0,                                      /* tp_as_sequence */
1099         0,                                      /* tp_as_mapping */
1100         (hashfunc)int_hash,                     /* tp_hash */
1101         0,                                      /* tp_call */
1102         (reprfunc)int_repr,                     /* tp_str */
1103         PyObject_GenericGetAttr,                /* tp_getattro */
1104         0,                                      /* tp_setattro */
1105         0,                                      /* tp_as_buffer */
1106         Py_TPFLAGS_DEFAULT | Py_TPFLAGS_CHECKTYPES |
1107                 Py_TPFLAGS_BASETYPE,            /* tp_flags */
1108         int_doc,                                /* tp_doc */
1109         0,                                      /* tp_traverse */
1110         0,                                      /* tp_clear */
1111         0,                                      /* tp_richcompare */
1112         0,                                      /* tp_weaklistoffset */
1113         0,                                      /* tp_iter */
1114         0,                                      /* tp_iternext */
1115         int_methods,                            /* tp_methods */
1116         0,                                      /* tp_members */
1117         0,                                      /* tp_getset */
1118         0,                                      /* tp_base */
1119         0,                                      /* tp_dict */
1120         0,                                      /* tp_descr_get */
1121         0,                                      /* tp_descr_set */
1122         0,                                      /* tp_dictoffset */
1123         0,                                      /* tp_init */
1124         0,                                      /* tp_alloc */
1125         int_new,                                /* tp_new */
1126         (freefunc)int_free,                     /* tp_free */
1127 };
1128
1129 int
1130 _PyInt_Init(void)
1131 {
1132         PyIntObject *v;
1133         int ival;
1134 #if NSMALLNEGINTS + NSMALLPOSINTS > 0
1135         for (ival = -NSMALLNEGINTS; ival < NSMALLPOSINTS; ival++) {
1136               if (!free_list && (free_list = fill_free_list()) == NULL)
1137                         return 0;
1138                 /* PyObject_New is inlined */
1139                 v = free_list;
1140                 free_list = (PyIntObject *)v->ob_type;
1141                 PyObject_INIT(v, &PyInt_Type);
1142                 v->ob_ival = ival;
1143                 small_ints[ival + NSMALLNEGINTS] = v;
1144         }
1145 #endif
1146         return 1;
1147 }
1148
1149 void
1150 PyInt_Fini(void)
1151 {
1152         PyIntObject *p;
1153         PyIntBlock *list, *next;
1154         int i;
1155         unsigned int ctr;
1156         int bc, bf;     /* block count, number of freed blocks */
1157         int irem, isum; /* remaining unfreed ints per block, total */
1158
1159 #if NSMALLNEGINTS + NSMALLPOSINTS > 0
1160         PyIntObject **q;
1161
1162         i = NSMALLNEGINTS + NSMALLPOSINTS;
1163         q = small_ints;
1164         while (--i >= 0) {
1165                 Py_XDECREF(*q);
1166                 *q++ = NULL;
1167         }
1168 #endif
1169         bc = 0;
1170         bf = 0;
1171         isum = 0;
1172         list = block_list;
1173         block_list = NULL;
1174         free_list = NULL;
1175         while (list != NULL) {
1176                 bc++;
1177                 irem = 0;
1178                 for (ctr = 0, p = &list->objects[0];
1179                      ctr < N_INTOBJECTS;
1180                      ctr++, p++) {
1181                         if (PyInt_CheckExact(p) && p->ob_refcnt != 0)
1182                                 irem++;
1183                 }
1184                 next = list->next;
1185                 if (irem) {
1186                         list->next = block_list;
1187                         block_list = list;
1188                         for (ctr = 0, p = &list->objects[0];
1189                              ctr < N_INTOBJECTS;
1190                              ctr++, p++) {
1191                                 if (!PyInt_CheckExact(p) ||
1192                                     p->ob_refcnt == 0) {
1193                                         p->ob_type = (struct _typeobject *)
1194                                                 free_list;
1195                                         free_list = p;
1196                                 }
1197 #if NSMALLNEGINTS + NSMALLPOSINTS > 0
1198                                 else if (-NSMALLNEGINTS <= p->ob_ival &&
1199                                          p->ob_ival < NSMALLPOSINTS &&
1200                                          small_ints[p->ob_ival +
1201                                                     NSMALLNEGINTS] == NULL) {
1202                                         Py_INCREF(p);
1203                                         small_ints[p->ob_ival +
1204                                                    NSMALLNEGINTS] = p;
1205                                 }
1206 #endif
1207                         }
1208                 }
1209                 else {
1210                         PyMem_FREE(list);
1211                         bf++;
1212                 }
1213                 isum += irem;
1214                 list = next;
1215         }
1216         if (!Py_VerboseFlag)
1217                 return;
1218         fprintf(stderr, "# cleanup ints");
1219         if (!isum) {
1220                 fprintf(stderr, "\n");
1221         }
1222         else {
1223                 fprintf(stderr,
1224                         ": %d unfreed int%s in %d out of %d block%s\n",
1225                         isum, isum == 1 ? "" : "s",
1226                         bc - bf, bc, bc == 1 ? "" : "s");
1227         }
1228         if (Py_VerboseFlag > 1) {
1229                 list = block_list;
1230                 while (list != NULL) {
1231                         for (ctr = 0, p = &list->objects[0];
1232                              ctr < N_INTOBJECTS;
1233                              ctr++, p++) {
1234                                 if (PyInt_CheckExact(p) && p->ob_refcnt != 0)
1235                                         /* XXX(twouters) cast refcount to
1236                                            long until %zd is universally
1237                                            available
1238                                          */
1239                                         fprintf(stderr,
1240                                 "#   <int at %p, refcnt=%ld, val=%ld>\n",
1241                                                 p, (long)p->ob_refcnt,
1242                                                 p->ob_ival);
1243                         }
1244                         list = list->next;
1245                 }
1246         }
1247 }