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