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