source: python/trunk/Objects/intobject.c@ 388

Last change on this file since 388 was 2, checked in by Yuri Dario, 15 years ago

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