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