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