Line data Source code
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 3 : PyInt_GetMax(void)
12 : {
13 3 : 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 69 : fill_free_list(void)
49 : {
50 : PyIntObject *p, *q;
51 : /* Python's object allocator isn't appropriate for large blocks. */
52 69 : p = (PyIntObject *) PyMem_MALLOC(sizeof(PyIntBlock));
53 69 : if (p == NULL)
54 0 : return (PyIntObject *) PyErr_NoMemory();
55 69 : ((PyIntBlock *)p)->next = block_list;
56 69 : 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 69 : p = &((PyIntBlock *)p)->objects[0];
60 69 : q = p + N_INTOBJECTS;
61 2898 : while (--q > p)
62 2760 : Py_TYPE(q) = (struct _typeobject *)(q-1);
63 69 : Py_TYPE(q) = NULL;
64 69 : 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 191939 : PyInt_FromLong(long ival)
88 : {
89 : register PyIntObject *v;
90 : #if NSMALLNEGINTS + NSMALLPOSINTS > 0
91 191939 : if (-NSMALLNEGINTS <= ival && ival < NSMALLPOSINTS) {
92 169436 : v = small_ints[ival + NSMALLNEGINTS];
93 169436 : 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 169436 : return (PyObject *) v;
101 : }
102 : #endif
103 22503 : if (free_list == NULL) {
104 48 : if ((free_list = fill_free_list()) == NULL)
105 0 : return NULL;
106 : }
107 : /* Inline PyObject_New */
108 22503 : v = free_list;
109 22503 : free_list = (PyIntObject *)Py_TYPE(v);
110 22503 : (void)PyObject_INIT(v, &PyInt_Type);
111 22503 : v->ob_ival = ival;
112 22503 : return (PyObject *) v;
113 : }
114 :
115 : PyObject *
116 0 : PyInt_FromSize_t(size_t ival)
117 : {
118 0 : if (ival <= LONG_MAX)
119 0 : return PyInt_FromLong((long)ival);
120 0 : return _PyLong_FromSize_t(ival);
121 : }
122 :
123 : PyObject *
124 52785 : PyInt_FromSsize_t(Py_ssize_t ival)
125 : {
126 : if (ival >= LONG_MIN && ival <= LONG_MAX)
127 52785 : return PyInt_FromLong((long)ival);
128 : return _PyLong_FromSsize_t(ival);
129 : }
130 :
131 : static void
132 22551 : int_dealloc(PyIntObject *v)
133 : {
134 22551 : if (PyInt_CheckExact(v)) {
135 22551 : Py_TYPE(v) = (struct _typeobject *)free_list;
136 22551 : free_list = v;
137 : }
138 : else
139 0 : Py_TYPE(v)->tp_free((PyObject *)v);
140 22551 : }
141 :
142 : long
143 67637 : PyInt_AsLong(register PyObject *op)
144 : {
145 : PyNumberMethods *nb;
146 : PyIntObject *io;
147 : long val;
148 :
149 67637 : if (op && PyInt_Check(op))
150 67637 : return PyInt_AS_LONG((PyIntObject*) op);
151 :
152 0 : if (op == NULL || (nb = Py_TYPE(op)->tp_as_number) == NULL ||
153 0 : nb->nb_int == NULL) {
154 0 : PyErr_SetString(PyExc_TypeError, "an integer is required");
155 0 : return -1;
156 : }
157 :
158 0 : io = (PyIntObject*) (*nb->nb_int) (op);
159 0 : if (io == NULL)
160 0 : return -1;
161 0 : if (!PyInt_Check(io)) {
162 0 : if (PyLong_Check(io)) {
163 : /* got a long? => retry int conversion */
164 0 : val = PyLong_AsLong((PyObject *)io);
165 0 : Py_DECREF(io);
166 0 : if ((val == -1) && PyErr_Occurred())
167 0 : return -1;
168 0 : return val;
169 : }
170 : else
171 : {
172 0 : Py_DECREF(io);
173 0 : PyErr_SetString(PyExc_TypeError,
174 : "__int__ method should return an integer");
175 0 : return -1;
176 : }
177 : }
178 :
179 0 : val = PyInt_AS_LONG(io);
180 0 : Py_DECREF(io);
181 :
182 0 : return val;
183 : }
184 :
185 : int
186 0 : _PyInt_AsInt(PyObject *obj)
187 : {
188 0 : long result = PyInt_AsLong(obj);
189 0 : if (result == -1 && PyErr_Occurred())
190 0 : return -1;
191 0 : if (result > INT_MAX || result < INT_MIN) {
192 0 : PyErr_SetString(PyExc_OverflowError,
193 : "Python int too large to convert to C int");
194 0 : return -1;
195 : }
196 0 : return (int)result;
197 : }
198 :
199 : Py_ssize_t
200 91763 : 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 91763 : if (op == NULL) {
209 0 : PyErr_SetString(PyExc_TypeError, "an integer is required");
210 0 : return -1;
211 : }
212 :
213 91763 : if (PyInt_Check(op))
214 91763 : return PyInt_AS_LONG((PyIntObject*) op);
215 0 : if (PyLong_Check(op))
216 0 : return _PyLong_AsSsize_t(op);
217 : #if SIZEOF_SIZE_T == SIZEOF_LONG
218 0 : 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 0 : PyInt_AsUnsignedLongMask(register PyObject *op)
260 : {
261 : PyNumberMethods *nb;
262 : PyIntObject *io;
263 : unsigned long val;
264 :
265 0 : if (op && PyInt_Check(op))
266 0 : return PyInt_AS_LONG((PyIntObject*) op);
267 0 : if (op && PyLong_Check(op))
268 0 : return PyLong_AsUnsignedLongMask(op);
269 :
270 0 : if (op == NULL || (nb = Py_TYPE(op)->tp_as_number) == NULL ||
271 0 : nb->nb_int == NULL) {
272 0 : PyErr_SetString(PyExc_TypeError, "an integer is required");
273 0 : return (unsigned long)-1;
274 : }
275 :
276 0 : io = (PyIntObject*) (*nb->nb_int) (op);
277 0 : if (io == NULL)
278 0 : return (unsigned long)-1;
279 0 : if (!PyInt_Check(io)) {
280 0 : if (PyLong_Check(io)) {
281 0 : val = PyLong_AsUnsignedLongMask((PyObject *)io);
282 0 : Py_DECREF(io);
283 0 : if (PyErr_Occurred())
284 0 : return (unsigned long)-1;
285 0 : return val;
286 : }
287 : else
288 : {
289 0 : Py_DECREF(io);
290 0 : PyErr_SetString(PyExc_TypeError,
291 : "__int__ method should return an integer");
292 0 : return (unsigned long)-1;
293 : }
294 : }
295 :
296 0 : val = PyInt_AS_LONG(io);
297 0 : Py_DECREF(io);
298 :
299 0 : return val;
300 : }
301 :
302 : #ifdef HAVE_LONG_LONG
303 : unsigned PY_LONG_LONG
304 0 : PyInt_AsUnsignedLongLongMask(register PyObject *op)
305 : {
306 : PyNumberMethods *nb;
307 : PyIntObject *io;
308 : unsigned PY_LONG_LONG val;
309 :
310 0 : if (op && PyInt_Check(op))
311 0 : return PyInt_AS_LONG((PyIntObject*) op);
312 0 : if (op && PyLong_Check(op))
313 0 : return PyLong_AsUnsignedLongLongMask(op);
314 :
315 0 : if (op == NULL || (nb = Py_TYPE(op)->tp_as_number) == NULL ||
316 0 : nb->nb_int == NULL) {
317 0 : PyErr_SetString(PyExc_TypeError, "an integer is required");
318 0 : return (unsigned PY_LONG_LONG)-1;
319 : }
320 :
321 0 : io = (PyIntObject*) (*nb->nb_int) (op);
322 0 : if (io == NULL)
323 0 : return (unsigned PY_LONG_LONG)-1;
324 0 : if (!PyInt_Check(io)) {
325 0 : if (PyLong_Check(io)) {
326 0 : val = PyLong_AsUnsignedLongLongMask((PyObject *)io);
327 0 : Py_DECREF(io);
328 0 : if (PyErr_Occurred())
329 0 : return (unsigned PY_LONG_LONG)-1;
330 0 : return val;
331 : }
332 : else
333 : {
334 0 : Py_DECREF(io);
335 0 : PyErr_SetString(PyExc_TypeError,
336 : "__int__ method should return an integer");
337 0 : return (unsigned PY_LONG_LONG)-1;
338 : }
339 : }
340 :
341 0 : val = PyInt_AS_LONG(io);
342 0 : Py_DECREF(io);
343 :
344 0 : return val;
345 : }
346 : #endif
347 :
348 : PyObject *
349 3075 : 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 3075 : if ((base != 0 && base < 2) || base > 36) {
357 0 : PyErr_SetString(PyExc_ValueError,
358 : "int() base must be >= 2 and <= 36");
359 0 : return NULL;
360 : }
361 :
362 6150 : while (*s && isspace(Py_CHARMASK(*s)))
363 0 : s++;
364 3075 : errno = 0;
365 3075 : if (base == 0 && s[0] == '0') {
366 0 : x = (long) PyOS_strtoul(s, &end, base);
367 0 : if (x < 0)
368 0 : return PyLong_FromString(s, pend, base);
369 : }
370 : else
371 3075 : x = PyOS_strtol(s, &end, base);
372 3075 : if (end == s || !isalnum(Py_CHARMASK(end[-1])))
373 : goto bad;
374 6150 : while (*end && isspace(Py_CHARMASK(*end)))
375 0 : end++;
376 3075 : if (*end != '\0') {
377 : bad:
378 0 : slen = strlen(s) < 200 ? strlen(s) : 200;
379 0 : sobj = PyString_FromStringAndSize(s, slen);
380 0 : if (sobj == NULL)
381 0 : return NULL;
382 0 : srepr = PyObject_Repr(sobj);
383 0 : Py_DECREF(sobj);
384 0 : if (srepr == NULL)
385 0 : return NULL;
386 0 : PyErr_Format(PyExc_ValueError,
387 : "invalid literal for int() with base %d: %s",
388 0 : base, PyString_AS_STRING(srepr));
389 0 : Py_DECREF(srepr);
390 0 : return NULL;
391 : }
392 3075 : else if (errno != 0)
393 0 : return PyLong_FromString(s, pend, base);
394 3075 : if (pend)
395 3 : *pend = end;
396 3075 : return PyInt_FromLong(x);
397 : }
398 :
399 : #ifdef Py_USING_UNICODE
400 : PyObject *
401 0 : PyInt_FromUnicode(Py_UNICODE *s, Py_ssize_t length, int base)
402 : {
403 : PyObject *result;
404 0 : char *buffer = (char *)PyMem_MALLOC(length+1);
405 :
406 0 : if (buffer == NULL)
407 0 : return PyErr_NoMemory();
408 :
409 0 : if (PyUnicode_EncodeDecimal(s, length, buffer, NULL)) {
410 0 : PyMem_FREE(buffer);
411 0 : return NULL;
412 : }
413 0 : result = PyInt_FromString(buffer, NULL, base);
414 0 : PyMem_FREE(buffer);
415 0 : 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 0 : int_print(PyIntObject *v, FILE *fp, int flags)
437 : /* flags -- not used but required by interface */
438 : {
439 0 : long int_val = v->ob_ival;
440 : Py_BEGIN_ALLOW_THREADS
441 0 : fprintf(fp, "%ld", int_val);
442 : Py_END_ALLOW_THREADS
443 0 : return 0;
444 : }
445 :
446 : static int
447 2498 : int_compare(PyIntObject *v, PyIntObject *w)
448 : {
449 2498 : register long i = v->ob_ival;
450 2498 : register long j = w->ob_ival;
451 2498 : return (i < j) ? -1 : (i > j) ? 1 : 0;
452 : }
453 :
454 : static long
455 11245 : 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 11245 : long x = v -> ob_ival;
460 11245 : if (x == -1)
461 583 : x = -2;
462 11245 : return x;
463 : }
464 :
465 : static PyObject *
466 573 : int_add(PyIntObject *v, PyIntObject *w)
467 : {
468 : register long a, b, x;
469 573 : CONVERT_TO_LONG(v, a);
470 573 : CONVERT_TO_LONG(w, b);
471 : /* casts in the line below avoid undefined behaviour on overflow */
472 0 : x = (long)((unsigned long)a + b);
473 0 : if ((x^a) >= 0 || (x^b) >= 0)
474 0 : return PyInt_FromLong(x);
475 0 : return PyLong_Type.tp_as_number->nb_add((PyObject *)v, (PyObject *)w);
476 : }
477 :
478 : static PyObject *
479 0 : int_sub(PyIntObject *v, PyIntObject *w)
480 : {
481 : register long a, b, x;
482 0 : CONVERT_TO_LONG(v, a);
483 0 : CONVERT_TO_LONG(w, b);
484 : /* casts in the line below avoid undefined behaviour on overflow */
485 0 : x = (long)((unsigned long)a - b);
486 0 : if ((x^a) >= 0 || (x^~b) >= 0)
487 0 : return PyInt_FromLong(x);
488 0 : 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 2994 : 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 2994 : CONVERT_TO_LONG(v, a);
527 1458 : CONVERT_TO_LONG(w, b);
528 : /* casts in the next line avoid undefined behaviour on overflow */
529 1089 : longprod = (long)((unsigned long)a * b);
530 1089 : doubleprod = (double)a * (double)b;
531 1089 : doubled_longprod = (double)longprod;
532 :
533 : /* Fast path for normal case: small multiplicands, and no info
534 : is lost in either method. */
535 1089 : if (doubled_longprod == doubleprod)
536 1089 : 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 0 : const double diff = doubled_longprod - doubleprod;
545 0 : const double absdiff = diff >= 0.0 ? diff : -diff;
546 0 : 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 0 : if (32.0 * absdiff <= absprod)
551 0 : return PyInt_FromLong(longprod);
552 : else
553 0 : 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 0 : i_divmod(register long x, register long y,
577 : long *p_xdivy, long *p_xmody)
578 : {
579 : long xdivy, xmody;
580 :
581 0 : if (y == 0) {
582 0 : PyErr_SetString(PyExc_ZeroDivisionError,
583 : "integer division or modulo by zero");
584 0 : return DIVMOD_ERROR;
585 : }
586 : /* (-sys.maxint-1)/-1 is the only overflow case. */
587 0 : if (y == -1 && UNARY_NEG_WOULD_OVERFLOW(x))
588 0 : return DIVMOD_OVERFLOW;
589 0 : 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 0 : 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 0 : if (xmody && ((y ^ xmody) < 0) /* i.e. and signs differ */) {
606 0 : xmody += y;
607 0 : --xdivy;
608 : assert(xmody && ((y ^ xmody) >= 0));
609 : }
610 0 : *p_xdivy = xdivy;
611 0 : *p_xmody = xmody;
612 0 : return DIVMOD_OK;
613 : }
614 :
615 : static PyObject *
616 0 : int_div(PyIntObject *x, PyIntObject *y)
617 : {
618 : long xi, yi;
619 : long d, m;
620 0 : CONVERT_TO_LONG(x, xi);
621 0 : CONVERT_TO_LONG(y, yi);
622 0 : switch (i_divmod(xi, yi, &d, &m)) {
623 : case DIVMOD_OK:
624 0 : return PyInt_FromLong(d);
625 : case DIVMOD_OVERFLOW:
626 0 : return PyLong_Type.tp_as_number->nb_divide((PyObject *)x,
627 : (PyObject *)y);
628 : default:
629 0 : return NULL;
630 : }
631 : }
632 :
633 : static PyObject *
634 0 : int_classic_div(PyIntObject *x, PyIntObject *y)
635 : {
636 : long xi, yi;
637 : long d, m;
638 0 : CONVERT_TO_LONG(x, xi);
639 0 : CONVERT_TO_LONG(y, yi);
640 0 : if (Py_DivisionWarningFlag &&
641 0 : PyErr_Warn(PyExc_DeprecationWarning, "classic int division") < 0)
642 0 : return NULL;
643 0 : switch (i_divmod(xi, yi, &d, &m)) {
644 : case DIVMOD_OK:
645 0 : return PyInt_FromLong(d);
646 : case DIVMOD_OVERFLOW:
647 0 : return PyLong_Type.tp_as_number->nb_divide((PyObject *)x,
648 : (PyObject *)y);
649 : default:
650 0 : return NULL;
651 : }
652 : }
653 :
654 : static PyObject *
655 0 : 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 0 : CONVERT_TO_LONG(x, xi);
663 0 : CONVERT_TO_LONG(y, yi);
664 0 : if (yi == 0) {
665 0 : PyErr_SetString(PyExc_ZeroDivisionError,
666 : "division by zero");
667 0 : return NULL;
668 : }
669 0 : if (xi == 0)
670 0 : 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 0 : if ((xi >= 0 ? 0UL + xi : 0UL - xi) >> DBL_MANT_DIG ||
675 0 : (yi >= 0 ? 0UL + yi : 0UL - yi) >> DBL_MANT_DIG)
676 : /* Large x or y. Use long integer arithmetic. */
677 0 : 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 0 : return PyFloat_FromDouble((double)xi / (double)yi);
684 : }
685 :
686 : static PyObject *
687 0 : int_mod(PyIntObject *x, PyIntObject *y)
688 : {
689 : long xi, yi;
690 : long d, m;
691 0 : CONVERT_TO_LONG(x, xi);
692 0 : CONVERT_TO_LONG(y, yi);
693 0 : switch (i_divmod(xi, yi, &d, &m)) {
694 : case DIVMOD_OK:
695 0 : return PyInt_FromLong(m);
696 : case DIVMOD_OVERFLOW:
697 0 : return PyLong_Type.tp_as_number->nb_remainder((PyObject *)x,
698 : (PyObject *)y);
699 : default:
700 0 : return NULL;
701 : }
702 : }
703 :
704 : static PyObject *
705 0 : int_divmod(PyIntObject *x, PyIntObject *y)
706 : {
707 : long xi, yi;
708 : long d, m;
709 0 : CONVERT_TO_LONG(x, xi);
710 0 : CONVERT_TO_LONG(y, yi);
711 0 : switch (i_divmod(xi, yi, &d, &m)) {
712 : case DIVMOD_OK:
713 0 : return Py_BuildValue("(ll)", d, m);
714 : case DIVMOD_OVERFLOW:
715 0 : return PyLong_Type.tp_as_number->nb_divmod((PyObject *)x,
716 : (PyObject *)y);
717 : default:
718 0 : return NULL;
719 : }
720 : }
721 :
722 : static PyObject *
723 3 : int_pow(PyIntObject *v, PyIntObject *w, PyIntObject *z)
724 : {
725 3 : register long iv, iw, iz=0, ix, temp, prev;
726 3 : CONVERT_TO_LONG(v, iv);
727 3 : CONVERT_TO_LONG(w, iw);
728 3 : if (iw < 0) {
729 3 : if ((PyObject *)z != Py_None) {
730 0 : PyErr_SetString(PyExc_TypeError, "pow() 2nd argument "
731 : "cannot be negative when 3rd argument specified");
732 0 : 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 3 : return PyFloat_Type.tp_as_number->nb_power(
738 : (PyObject *)v, (PyObject *)w, (PyObject *)z);
739 : }
740 0 : if ((PyObject *)z != Py_None) {
741 0 : CONVERT_TO_LONG(z, iz);
742 0 : if (iz == 0) {
743 0 : PyErr_SetString(PyExc_ValueError,
744 : "pow() 3rd argument cannot be 0");
745 0 : 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 0 : temp = iv;
757 0 : ix = 1;
758 0 : while (iw > 0) {
759 0 : prev = ix; /* Save value for overflow check */
760 0 : 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 0 : ix = (unsigned long)ix * temp;
768 0 : if (temp == 0)
769 0 : break; /* Avoid ix / 0 */
770 0 : if (ix / temp != prev) {
771 0 : return PyLong_Type.tp_as_number->nb_power(
772 : (PyObject *)v,
773 : (PyObject *)w,
774 : (PyObject *)z);
775 : }
776 : }
777 0 : iw >>= 1; /* Shift exponent down by 1 bit */
778 0 : if (iw==0) break;
779 0 : prev = temp;
780 0 : temp = (unsigned long)temp * temp; /* Square the value of temp */
781 0 : if (prev != 0 && temp / prev != prev) {
782 0 : return PyLong_Type.tp_as_number->nb_power(
783 : (PyObject *)v, (PyObject *)w, (PyObject *)z);
784 : }
785 0 : if (iz) {
786 : /* If we did a multiplication, perform a modulo */
787 0 : ix = ix % iz;
788 0 : temp = temp % iz;
789 : }
790 : }
791 0 : if (iz) {
792 : long div, mod;
793 0 : switch (i_divmod(ix, iz, &div, &mod)) {
794 : case DIVMOD_OK:
795 0 : ix = mod;
796 0 : break;
797 : case DIVMOD_OVERFLOW:
798 0 : return PyLong_Type.tp_as_number->nb_power(
799 : (PyObject *)v, (PyObject *)w, (PyObject *)z);
800 : default:
801 0 : return NULL;
802 : }
803 : }
804 0 : return PyInt_FromLong(ix);
805 : }
806 :
807 : static PyObject *
808 201 : int_neg(PyIntObject *v)
809 : {
810 : register long a;
811 201 : a = v->ob_ival;
812 : /* check for overflow */
813 201 : if (UNARY_NEG_WOULD_OVERFLOW(a)) {
814 0 : PyObject *o = PyLong_FromLong(a);
815 0 : if (o != NULL) {
816 0 : PyObject *result = PyNumber_Negative(o);
817 0 : Py_DECREF(o);
818 0 : return result;
819 : }
820 0 : return NULL;
821 : }
822 201 : return PyInt_FromLong(-a);
823 : }
824 :
825 : static PyObject *
826 0 : int_abs(PyIntObject *v)
827 : {
828 0 : if (v->ob_ival >= 0)
829 0 : return int_int(v);
830 : else
831 0 : return int_neg(v);
832 : }
833 :
834 : static int
835 27285 : int_nonzero(PyIntObject *v)
836 : {
837 27285 : return v->ob_ival != 0;
838 : }
839 :
840 : static PyObject *
841 90 : int_invert(PyIntObject *v)
842 : {
843 90 : return PyInt_FromLong(~v->ob_ival);
844 : }
845 :
846 : static PyObject *
847 0 : int_lshift(PyIntObject *v, PyIntObject *w)
848 : {
849 : long a, b, c;
850 : PyObject *vv, *ww, *result;
851 :
852 0 : CONVERT_TO_LONG(v, a);
853 0 : CONVERT_TO_LONG(w, b);
854 0 : if (b < 0) {
855 0 : PyErr_SetString(PyExc_ValueError, "negative shift count");
856 0 : return NULL;
857 : }
858 0 : if (a == 0 || b == 0)
859 0 : return int_int(v);
860 0 : if (b >= LONG_BIT) {
861 0 : vv = PyLong_FromLong(PyInt_AS_LONG(v));
862 0 : if (vv == NULL)
863 0 : return NULL;
864 0 : ww = PyLong_FromLong(PyInt_AS_LONG(w));
865 0 : if (ww == NULL) {
866 0 : Py_DECREF(vv);
867 0 : return NULL;
868 : }
869 0 : result = PyNumber_Lshift(vv, ww);
870 0 : Py_DECREF(vv);
871 0 : Py_DECREF(ww);
872 0 : return result;
873 : }
874 0 : c = a << b;
875 0 : if (a != Py_ARITHMETIC_RIGHT_SHIFT(long, c, b)) {
876 0 : vv = PyLong_FromLong(PyInt_AS_LONG(v));
877 0 : if (vv == NULL)
878 0 : return NULL;
879 0 : ww = PyLong_FromLong(PyInt_AS_LONG(w));
880 0 : if (ww == NULL) {
881 0 : Py_DECREF(vv);
882 0 : return NULL;
883 : }
884 0 : result = PyNumber_Lshift(vv, ww);
885 0 : Py_DECREF(vv);
886 0 : Py_DECREF(ww);
887 0 : return result;
888 : }
889 0 : return PyInt_FromLong(c);
890 : }
891 :
892 : static PyObject *
893 0 : int_rshift(PyIntObject *v, PyIntObject *w)
894 : {
895 : register long a, b;
896 0 : CONVERT_TO_LONG(v, a);
897 0 : CONVERT_TO_LONG(w, b);
898 0 : if (b < 0) {
899 0 : PyErr_SetString(PyExc_ValueError, "negative shift count");
900 0 : return NULL;
901 : }
902 0 : if (a == 0 || b == 0)
903 0 : return int_int(v);
904 0 : if (b >= LONG_BIT) {
905 0 : if (a < 0)
906 0 : a = -1;
907 : else
908 0 : a = 0;
909 : }
910 : else {
911 0 : a = Py_ARITHMETIC_RIGHT_SHIFT(long, a, b);
912 : }
913 0 : return PyInt_FromLong(a);
914 : }
915 :
916 : static PyObject *
917 17580 : int_and(PyIntObject *v, PyIntObject *w)
918 : {
919 : register long a, b;
920 17580 : CONVERT_TO_LONG(v, a);
921 17580 : CONVERT_TO_LONG(w, b);
922 17580 : return PyInt_FromLong(a & b);
923 : }
924 :
925 : static PyObject *
926 0 : int_xor(PyIntObject *v, PyIntObject *w)
927 : {
928 : register long a, b;
929 0 : CONVERT_TO_LONG(v, a);
930 0 : CONVERT_TO_LONG(w, b);
931 0 : return PyInt_FromLong(a ^ b);
932 : }
933 :
934 : static PyObject *
935 1761 : int_or(PyIntObject *v, PyIntObject *w)
936 : {
937 : register long a, b;
938 1761 : CONVERT_TO_LONG(v, a);
939 1761 : CONVERT_TO_LONG(w, b);
940 1761 : return PyInt_FromLong(a | b);
941 : }
942 :
943 : static int
944 3216 : int_coerce(PyObject **pv, PyObject **pw)
945 : {
946 3216 : if (PyInt_Check(*pw)) {
947 0 : Py_INCREF(*pv);
948 0 : Py_INCREF(*pw);
949 0 : return 0;
950 : }
951 3216 : return 1; /* Can't do it */
952 : }
953 :
954 : static PyObject *
955 0 : int_int(PyIntObject *v)
956 : {
957 0 : if (PyInt_CheckExact(v))
958 0 : Py_INCREF(v);
959 : else
960 0 : v = (PyIntObject *)PyInt_FromLong(v->ob_ival);
961 0 : return (PyObject *)v;
962 : }
963 :
964 : static PyObject *
965 0 : int_long(PyIntObject *v)
966 : {
967 0 : 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 0 : bits_in_ulong(unsigned long d)
977 : {
978 0 : int d_bits = 0;
979 0 : while (d >= 32) {
980 0 : d_bits += 6;
981 0 : d >>= 6;
982 : }
983 0 : d_bits += (int)BitLengthTable[d];
984 0 : 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 0 : int_float(PyIntObject *v)
1003 : {
1004 : unsigned long abs_ival, lsb;
1005 : int round_up;
1006 :
1007 0 : if (v->ob_ival < 0)
1008 0 : abs_ival = 0U-(unsigned long)v->ob_ival;
1009 : else
1010 0 : abs_ival = (unsigned long)v->ob_ival;
1011 0 : if (abs_ival < (1L << DBL_MANT_DIG))
1012 : /* small integer; no need to round */
1013 0 : 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 0 : lsb = 1L << (bits_in_ulong(abs_ival)-DBL_MANT_DIG-1);
1031 0 : round_up = (abs_ival & lsb) && (abs_ival & (3*lsb-1));
1032 0 : abs_ival &= -2*lsb;
1033 0 : if (round_up)
1034 0 : abs_ival += 2*lsb;
1035 0 : return PyFloat_FromDouble(v->ob_ival < 0 ?
1036 0 : -(double)abs_ival :
1037 : (double)abs_ival);
1038 : }
1039 :
1040 : #endif
1041 :
1042 : static PyObject *
1043 0 : int_oct(PyIntObject *v)
1044 : {
1045 0 : return _PyInt_Format(v, 8, 0);
1046 : }
1047 :
1048 : static PyObject *
1049 0 : int_hex(PyIntObject *v)
1050 : {
1051 0 : 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 3075 : int_new(PyTypeObject *type, PyObject *args, PyObject *kwds)
1059 : {
1060 3075 : PyObject *x = NULL;
1061 3075 : int base = -909;
1062 : static char *kwlist[] = {"x", "base", 0};
1063 :
1064 3075 : if (type != &PyInt_Type)
1065 0 : return int_subtype_new(type, args, kwds); /* Wimp out */
1066 3075 : if (!PyArg_ParseTupleAndKeywords(args, kwds, "|Oi:int", kwlist,
1067 : &x, &base))
1068 0 : return NULL;
1069 3075 : if (x == NULL) {
1070 0 : if (base != -909) {
1071 0 : PyErr_SetString(PyExc_TypeError,
1072 : "int() missing string argument");
1073 0 : return NULL;
1074 : }
1075 0 : return PyInt_FromLong(0L);
1076 : }
1077 3075 : if (base == -909)
1078 3 : return PyNumber_Int(x);
1079 3072 : if (PyString_Check(x)) {
1080 : /* Since PyInt_FromString doesn't have a length parameter,
1081 : * check here for possible NULs in the string. */
1082 3072 : char *string = PyString_AS_STRING(x);
1083 3072 : if (strlen(string) != PyString_Size(x)) {
1084 : /* create a repr() of the input string,
1085 : * just like PyInt_FromString does */
1086 : PyObject *srepr;
1087 0 : srepr = PyObject_Repr(x);
1088 0 : if (srepr == NULL)
1089 0 : return NULL;
1090 0 : PyErr_Format(PyExc_ValueError,
1091 : "invalid literal for int() with base %d: %s",
1092 0 : base, PyString_AS_STRING(srepr));
1093 0 : Py_DECREF(srepr);
1094 0 : return NULL;
1095 : }
1096 3072 : return PyInt_FromString(string, NULL, base);
1097 : }
1098 : #ifdef Py_USING_UNICODE
1099 0 : if (PyUnicode_Check(x))
1100 0 : return PyInt_FromUnicode(PyUnicode_AS_UNICODE(x),
1101 0 : PyUnicode_GET_SIZE(x),
1102 : base);
1103 : #endif
1104 0 : PyErr_SetString(PyExc_TypeError,
1105 : "int() can't convert non-string with explicit base");
1106 0 : 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 0 : 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 0 : tmp = int_new(&PyInt_Type, args, kwds);
1122 0 : if (tmp == NULL)
1123 0 : return NULL;
1124 0 : if (!PyInt_Check(tmp)) {
1125 0 : ival = PyLong_AsLong(tmp);
1126 0 : if (ival == -1 && PyErr_Occurred()) {
1127 0 : Py_DECREF(tmp);
1128 0 : return NULL;
1129 : }
1130 : } else {
1131 0 : ival = ((PyIntObject *)tmp)->ob_ival;
1132 : }
1133 :
1134 0 : newobj = type->tp_alloc(type, 0);
1135 0 : if (newobj == NULL) {
1136 0 : Py_DECREF(tmp);
1137 0 : return NULL;
1138 : }
1139 0 : ((PyIntObject *)newobj)->ob_ival = ival;
1140 0 : Py_DECREF(tmp);
1141 0 : return newobj;
1142 : }
1143 :
1144 : static PyObject *
1145 0 : int_getnewargs(PyIntObject *v)
1146 : {
1147 0 : return Py_BuildValue("(l)", v->ob_ival);
1148 : }
1149 :
1150 : static PyObject *
1151 0 : int_get0(PyIntObject *v, void *context) {
1152 0 : return PyInt_FromLong(0L);
1153 : }
1154 :
1155 : static PyObject *
1156 0 : int_get1(PyIntObject *v, void *context) {
1157 0 : 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 1050 : int_to_decimal_string(PyIntObject *v) {
1166 : char buf[sizeof(long)*CHAR_BIT/3+6], *p, *bufend;
1167 1050 : long n = v->ob_ival;
1168 : unsigned long absn;
1169 1050 : p = bufend = buf + sizeof(buf);
1170 1050 : absn = n < 0 ? 0UL - n : n;
1171 : do {
1172 2256 : *--p = '0' + (char)(absn % 10);
1173 2256 : absn /= 10;
1174 2256 : } while (absn);
1175 1050 : if (n < 0)
1176 0 : *--p = '-';
1177 1050 : 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 378 : _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 378 : long n = v->ob_ival;
1190 378 : int negative = n < 0;
1191 378 : 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 378 : char* p = &buf[sizeof(buf)];
1201 :
1202 : assert(base >= 2 && base <= 36);
1203 :
1204 : /* Special case base 10, for speed */
1205 378 : if (base == 10)
1206 282 : 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 144 : long div = n / base;
1213 144 : long mod = n - div * base;
1214 :
1215 : /* convert abs(mod) to the right character in [0-9, a-z] */
1216 144 : char cdigit = (char)(mod < 0 ? -mod : mod);
1217 144 : cdigit += (cdigit < 10) ? '0' : 'a'-10;
1218 144 : *--p = cdigit;
1219 :
1220 144 : n = div;
1221 144 : } while(n);
1222 :
1223 96 : if (base == 2) {
1224 0 : *--p = 'b';
1225 0 : *--p = '0';
1226 : }
1227 96 : else if (base == 8) {
1228 0 : if (newstyle) {
1229 0 : *--p = 'o';
1230 0 : *--p = '0';
1231 : }
1232 : else
1233 0 : if (!is_zero)
1234 0 : *--p = '0';
1235 : }
1236 96 : else if (base == 16) {
1237 96 : *--p = 'x';
1238 96 : *--p = '0';
1239 : }
1240 : else {
1241 0 : *--p = '#';
1242 0 : *--p = '0' + base%10;
1243 0 : if (base > 10)
1244 0 : *--p = '0' + base/10;
1245 : }
1246 96 : if (negative)
1247 0 : *--p = '-';
1248 :
1249 96 : return PyString_FromStringAndSize(p, &buf[sizeof(buf)] - p);
1250 : }
1251 :
1252 : static PyObject *
1253 0 : int__format__(PyObject *self, PyObject *args)
1254 : {
1255 : PyObject *format_spec;
1256 :
1257 0 : if (!PyArg_ParseTuple(args, "O:__format__", &format_spec))
1258 0 : return NULL;
1259 0 : if (PyBytes_Check(format_spec))
1260 0 : return _PyInt_FormatAdvanced(self,
1261 0 : PyBytes_AS_STRING(format_spec),
1262 0 : PyBytes_GET_SIZE(format_spec));
1263 0 : if (PyUnicode_Check(format_spec)) {
1264 : /* Convert format_spec to a str */
1265 : PyObject *result;
1266 0 : PyObject *str_spec = PyObject_Str(format_spec);
1267 :
1268 0 : if (str_spec == NULL)
1269 0 : return NULL;
1270 :
1271 0 : result = _PyInt_FormatAdvanced(self,
1272 0 : PyBytes_AS_STRING(str_spec),
1273 : PyBytes_GET_SIZE(str_spec));
1274 :
1275 0 : Py_DECREF(str_spec);
1276 0 : return result;
1277 : }
1278 0 : PyErr_SetString(PyExc_TypeError, "__format__ requires str or unicode");
1279 0 : return NULL;
1280 : }
1281 :
1282 : static PyObject *
1283 0 : int_bit_length(PyIntObject *v)
1284 : {
1285 : unsigned long n;
1286 :
1287 0 : if (v->ob_ival < 0)
1288 : /* avoid undefined behaviour when v->ob_ival == -LONG_MAX-1 */
1289 0 : n = 0U-(unsigned long)v->ob_ival;
1290 : else
1291 0 : n = (unsigned long)v->ob_ival;
1292 :
1293 0 : 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 3 : _PyInt_Init(void)
1451 : {
1452 : PyIntObject *v;
1453 : int ival;
1454 : #if NSMALLNEGINTS + NSMALLPOSINTS > 0
1455 789 : for (ival = -NSMALLNEGINTS; ival < NSMALLPOSINTS; ival++) {
1456 786 : if (!free_list && (free_list = fill_free_list()) == NULL)
1457 0 : return 0;
1458 : /* PyObject_New is inlined */
1459 786 : v = free_list;
1460 786 : free_list = (PyIntObject *)Py_TYPE(v);
1461 786 : (void)PyObject_INIT(v, &PyInt_Type);
1462 786 : v->ob_ival = ival;
1463 786 : small_ints[ival + NSMALLNEGINTS] = v;
1464 : }
1465 : #endif
1466 3 : return 1;
1467 : }
1468 :
1469 : int
1470 6 : PyInt_ClearFreeList(void)
1471 : {
1472 : PyIntObject *p;
1473 : PyIntBlock *list, *next;
1474 : int i;
1475 : int u; /* remaining unfreed ints per block */
1476 6 : int freelist_size = 0;
1477 :
1478 6 : list = block_list;
1479 6 : block_list = NULL;
1480 6 : free_list = NULL;
1481 142 : while (list != NULL) {
1482 130 : u = 0;
1483 5590 : for (i = 0, p = &list->objects[0];
1484 5460 : i < N_INTOBJECTS;
1485 5330 : i++, p++) {
1486 5330 : if (PyInt_CheckExact(p) && p->ob_refcnt != 0)
1487 2889 : u++;
1488 : }
1489 130 : next = list->next;
1490 130 : if (u) {
1491 96 : list->next = block_list;
1492 96 : block_list = list;
1493 4128 : for (i = 0, p = &list->objects[0];
1494 4032 : i < N_INTOBJECTS;
1495 3936 : i++, p++) {
1496 6825 : if (!PyInt_CheckExact(p) ||
1497 2889 : p->ob_refcnt == 0) {
1498 1047 : Py_TYPE(p) = (struct _typeobject *)
1499 : free_list;
1500 1047 : free_list = p;
1501 : }
1502 : #if NSMALLNEGINTS + NSMALLPOSINTS > 0
1503 5754 : else if (-NSMALLNEGINTS <= p->ob_ival &&
1504 4329 : p->ob_ival < NSMALLPOSINTS &&
1505 1464 : small_ints[p->ob_ival +
1506 : NSMALLNEGINTS] == NULL) {
1507 678 : Py_INCREF(p);
1508 678 : small_ints[p->ob_ival +
1509 678 : NSMALLNEGINTS] = p;
1510 : }
1511 : #endif
1512 : }
1513 : }
1514 : else {
1515 34 : PyMem_FREE(list);
1516 : }
1517 130 : freelist_size += u;
1518 130 : list = next;
1519 : }
1520 :
1521 6 : return freelist_size;
1522 : }
1523 :
1524 : void
1525 3 : 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 3 : i = NSMALLNEGINTS + NSMALLPOSINTS;
1536 3 : q = small_ints;
1537 792 : while (--i >= 0) {
1538 786 : Py_XDECREF(*q);
1539 786 : *q++ = NULL;
1540 : }
1541 : #endif
1542 3 : u = PyInt_ClearFreeList();
1543 3 : if (!Py_VerboseFlag)
1544 6 : return;
1545 0 : fprintf(stderr, "# cleanup ints");
1546 0 : if (!u) {
1547 0 : fprintf(stderr, "\n");
1548 : }
1549 : else {
1550 0 : fprintf(stderr,
1551 : ": %d unfreed int%s\n",
1552 : u, u == 1 ? "" : "s");
1553 : }
1554 0 : if (Py_VerboseFlag > 1) {
1555 0 : list = block_list;
1556 0 : while (list != NULL) {
1557 0 : for (i = 0, p = &list->objects[0];
1558 0 : i < N_INTOBJECTS;
1559 0 : i++, p++) {
1560 0 : if (PyInt_CheckExact(p) && p->ob_refcnt != 0)
1561 : /* XXX(twouters) cast refcount to
1562 : long until %zd is universally
1563 : available
1564 : */
1565 0 : fprintf(stderr,
1566 : "# <int at %p, refcnt=%ld, val=%ld>\n",
1567 : p, (long)p->ob_refcnt,
1568 : p->ob_ival);
1569 : }
1570 0 : list = list->next;
1571 : }
1572 : }
1573 : }
|
