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