blob: 4f43b111e502d44aa2106db57e2bd482aa5f451e [file] [log] [blame]
Guido van Rossumf70e43a1991-02-19 12:39:46 +00001
Guido van Rossum85a5fbb1990-10-14 12:07:46 +00002/* Integer object implementation */
3
Guido van Rossumc0b618a1997-05-02 03:12:38 +00004#include "Python.h"
Barry Warsaw226ae6c1999-10-12 19:54:53 +00005#include <ctype.h>
Guido van Rossum85a5fbb1990-10-14 12:07:46 +00006
Guido van Rossum2e1d4331993-12-24 10:22:45 +00007long
Fred Drakea2f55112000-07-09 15:16:51 +00008PyInt_GetMax(void)
Guido van Rossum2e1d4331993-12-24 10:22:45 +00009{
10 return LONG_MAX; /* To initialize sys.maxint */
11}
12
Guido van Rossume27f7952001-08-23 02:59:04 +000013/* Return 1 if exception raised, 0 if caller should retry using longs */
14static int
Fred Drakea2f55112000-07-09 15:16:51 +000015err_ovf(char *msg)
Guido van Rossum165e67e1990-10-14 20:02:26 +000016{
Guido van Rossume27f7952001-08-23 02:59:04 +000017 if (PyErr_Warn(PyExc_OverflowWarning, msg) < 0) {
Guido van Rossum0b131162001-08-23 21:32:40 +000018 if (PyErr_ExceptionMatches(PyExc_OverflowWarning))
19 PyErr_SetString(PyExc_OverflowError, msg);
Guido van Rossume27f7952001-08-23 02:59:04 +000020 return 1;
21 }
22 else
23 return 0;
Guido van Rossum165e67e1990-10-14 20:02:26 +000024}
25
Guido van Rossum3f5da241990-12-20 15:06:42 +000026/* Integers are quite normal objects, to make object handling uniform.
27 (Using odd pointers to represent integers would save much space
28 but require extra checks for this special case throughout the code.)
Tim Peters29c0afc2002-04-28 16:57:34 +000029 Since a typical Python program spends much of its time allocating
Guido van Rossum3f5da241990-12-20 15:06:42 +000030 and deallocating integers, these operations should be very fast.
31 Therefore we use a dedicated allocation scheme with a much lower
32 overhead (in space and time) than straight malloc(): a simple
33 dedicated free list, filled when necessary with memory from malloc().
Tim Peters29c0afc2002-04-28 16:57:34 +000034
35 block_list is a singly-linked list of all PyIntBlocks ever allocated,
36 linked via their next members. PyIntBlocks are never returned to the
37 system before shutdown (PyInt_Fini).
38
39 free_list is a singly-linked list of available PyIntObjects, linked
40 via abuse of their ob_type members.
Guido van Rossum3f5da241990-12-20 15:06:42 +000041*/
42
43#define BLOCK_SIZE 1000 /* 1K less typical malloc overhead */
Guido van Rossum3fce8831999-03-12 19:43:17 +000044#define BHEAD_SIZE 8 /* Enough for a 64-bit pointer */
45#define N_INTOBJECTS ((BLOCK_SIZE - BHEAD_SIZE) / sizeof(PyIntObject))
Guido van Rossumda084ed1999-03-10 22:55:24 +000046
Guido van Rossum3fce8831999-03-12 19:43:17 +000047struct _intblock {
48 struct _intblock *next;
49 PyIntObject objects[N_INTOBJECTS];
50};
51
52typedef struct _intblock PyIntBlock;
53
54static PyIntBlock *block_list = NULL;
55static PyIntObject *free_list = NULL;
Guido van Rossum3f5da241990-12-20 15:06:42 +000056
Guido van Rossumc0b618a1997-05-02 03:12:38 +000057static PyIntObject *
Fred Drakea2f55112000-07-09 15:16:51 +000058fill_free_list(void)
Guido van Rossum3f5da241990-12-20 15:06:42 +000059{
Guido van Rossumc0b618a1997-05-02 03:12:38 +000060 PyIntObject *p, *q;
Tim Peters29c0afc2002-04-28 16:57:34 +000061 /* Python's object allocator isn't appropriate for large blocks. */
Guido van Rossumb18618d2000-05-03 23:44:39 +000062 p = (PyIntObject *) PyMem_MALLOC(sizeof(PyIntBlock));
Guido van Rossum3f5da241990-12-20 15:06:42 +000063 if (p == NULL)
Guido van Rossumb18618d2000-05-03 23:44:39 +000064 return (PyIntObject *) PyErr_NoMemory();
Guido van Rossum3fce8831999-03-12 19:43:17 +000065 ((PyIntBlock *)p)->next = block_list;
66 block_list = (PyIntBlock *)p;
Tim Peters29c0afc2002-04-28 16:57:34 +000067 /* Link the int objects together, from rear to front, then return
68 the address of the last int object in the block. */
Guido van Rossum3fce8831999-03-12 19:43:17 +000069 p = &((PyIntBlock *)p)->objects[0];
Guido van Rossum3f5da241990-12-20 15:06:42 +000070 q = p + N_INTOBJECTS;
71 while (--q > p)
Guido van Rossumda084ed1999-03-10 22:55:24 +000072 q->ob_type = (struct _typeobject *)(q-1);
73 q->ob_type = NULL;
Guido van Rossum3f5da241990-12-20 15:06:42 +000074 return p + N_INTOBJECTS - 1;
75}
76
Sjoerd Mullender842d2cc1993-10-15 16:18:48 +000077#ifndef NSMALLPOSINTS
78#define NSMALLPOSINTS 100
79#endif
80#ifndef NSMALLNEGINTS
81#define NSMALLNEGINTS 1
82#endif
83#if NSMALLNEGINTS + NSMALLPOSINTS > 0
84/* References to small integers are saved in this array so that they
85 can be shared.
86 The integers that are saved are those in the range
87 -NSMALLNEGINTS (inclusive) to NSMALLPOSINTS (not inclusive).
88*/
Guido van Rossumc0b618a1997-05-02 03:12:38 +000089static PyIntObject *small_ints[NSMALLNEGINTS + NSMALLPOSINTS];
Sjoerd Mullender842d2cc1993-10-15 16:18:48 +000090#endif
91#ifdef COUNT_ALLOCS
92int quick_int_allocs, quick_neg_int_allocs;
93#endif
Guido van Rossum3f5da241990-12-20 15:06:42 +000094
Guido van Rossumc0b618a1997-05-02 03:12:38 +000095PyObject *
Fred Drakea2f55112000-07-09 15:16:51 +000096PyInt_FromLong(long ival)
Guido van Rossum85a5fbb1990-10-14 12:07:46 +000097{
Guido van Rossumc0b618a1997-05-02 03:12:38 +000098 register PyIntObject *v;
Sjoerd Mullender842d2cc1993-10-15 16:18:48 +000099#if NSMALLNEGINTS + NSMALLPOSINTS > 0
100 if (-NSMALLNEGINTS <= ival && ival < NSMALLPOSINTS &&
101 (v = small_ints[ival + NSMALLNEGINTS]) != NULL) {
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000102 Py_INCREF(v);
Sjoerd Mullender842d2cc1993-10-15 16:18:48 +0000103#ifdef COUNT_ALLOCS
104 if (ival >= 0)
105 quick_int_allocs++;
106 else
107 quick_neg_int_allocs++;
108#endif
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000109 return (PyObject *) v;
Sjoerd Mullender842d2cc1993-10-15 16:18:48 +0000110 }
111#endif
Guido van Rossum3f5da241990-12-20 15:06:42 +0000112 if (free_list == NULL) {
113 if ((free_list = fill_free_list()) == NULL)
114 return NULL;
Guido van Rossum85a5fbb1990-10-14 12:07:46 +0000115 }
Guido van Rossumb18618d2000-05-03 23:44:39 +0000116 /* PyObject_New is inlined */
Guido van Rossum3f5da241990-12-20 15:06:42 +0000117 v = free_list;
Guido van Rossumda084ed1999-03-10 22:55:24 +0000118 free_list = (PyIntObject *)v->ob_type;
Guido van Rossumb18618d2000-05-03 23:44:39 +0000119 PyObject_INIT(v, &PyInt_Type);
Guido van Rossum3f5da241990-12-20 15:06:42 +0000120 v->ob_ival = ival;
Sjoerd Mullender842d2cc1993-10-15 16:18:48 +0000121#if NSMALLNEGINTS + NSMALLPOSINTS > 0
122 if (-NSMALLNEGINTS <= ival && ival < NSMALLPOSINTS) {
123 /* save this one for a following allocation */
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000124 Py_INCREF(v);
Sjoerd Mullender842d2cc1993-10-15 16:18:48 +0000125 small_ints[ival + NSMALLNEGINTS] = v;
126 }
127#endif
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000128 return (PyObject *) v;
Guido van Rossum3f5da241990-12-20 15:06:42 +0000129}
130
131static void
Fred Drakea2f55112000-07-09 15:16:51 +0000132int_dealloc(PyIntObject *v)
Guido van Rossum3f5da241990-12-20 15:06:42 +0000133{
Guido van Rossumdea6ef92001-09-11 16:13:52 +0000134 if (PyInt_CheckExact(v)) {
Guido van Rossumbef14172001-08-29 15:47:46 +0000135 v->ob_type = (struct _typeobject *)free_list;
136 free_list = v;
137 }
138 else
139 v->ob_type->tp_free((PyObject *)v);
Guido van Rossum85a5fbb1990-10-14 12:07:46 +0000140}
141
Guido van Rossum93646982002-04-26 00:53:34 +0000142static void
143int_free(PyIntObject *v)
144{
145 v->ob_type = (struct _typeobject *)free_list;
146 free_list = v;
147}
148
Guido van Rossum85a5fbb1990-10-14 12:07:46 +0000149long
Fred Drakea2f55112000-07-09 15:16:51 +0000150PyInt_AsLong(register PyObject *op)
Guido van Rossum85a5fbb1990-10-14 12:07:46 +0000151{
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000152 PyNumberMethods *nb;
153 PyIntObject *io;
Guido van Rossumbf8c0e31994-08-29 12:48:32 +0000154 long val;
Tim Petersa3c01ce2001-12-04 23:05:10 +0000155
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000156 if (op && PyInt_Check(op))
157 return PyInt_AS_LONG((PyIntObject*) op);
Tim Petersa3c01ce2001-12-04 23:05:10 +0000158
Guido van Rossumbf8c0e31994-08-29 12:48:32 +0000159 if (op == NULL || (nb = op->ob_type->tp_as_number) == NULL ||
160 nb->nb_int == NULL) {
Guido van Rossumc18a6f42000-05-09 14:27:48 +0000161 PyErr_SetString(PyExc_TypeError, "an integer is required");
Guido van Rossum85a5fbb1990-10-14 12:07:46 +0000162 return -1;
163 }
Tim Petersa3c01ce2001-12-04 23:05:10 +0000164
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000165 io = (PyIntObject*) (*nb->nb_int) (op);
Guido van Rossumbf8c0e31994-08-29 12:48:32 +0000166 if (io == NULL)
167 return -1;
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000168 if (!PyInt_Check(io)) {
169 PyErr_SetString(PyExc_TypeError,
170 "nb_int should return int object");
Guido van Rossumbf8c0e31994-08-29 12:48:32 +0000171 return -1;
172 }
Tim Petersa3c01ce2001-12-04 23:05:10 +0000173
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000174 val = PyInt_AS_LONG(io);
175 Py_DECREF(io);
Tim Petersa3c01ce2001-12-04 23:05:10 +0000176
Guido van Rossumbf8c0e31994-08-29 12:48:32 +0000177 return val;
Guido van Rossum85a5fbb1990-10-14 12:07:46 +0000178}
179
Barry Warsaw226ae6c1999-10-12 19:54:53 +0000180PyObject *
Fred Drakea2f55112000-07-09 15:16:51 +0000181PyInt_FromString(char *s, char **pend, int base)
Barry Warsaw226ae6c1999-10-12 19:54:53 +0000182{
183 char *end;
184 long x;
185 char buffer[256]; /* For errors */
186
187 if ((base != 0 && base < 2) || base > 36) {
Fred Drake661ea262000-10-24 19:57:45 +0000188 PyErr_SetString(PyExc_ValueError, "int() base must be >= 2 and <= 36");
Barry Warsaw226ae6c1999-10-12 19:54:53 +0000189 return NULL;
190 }
191
192 while (*s && isspace(Py_CHARMASK(*s)))
193 s++;
194 errno = 0;
195 if (base == 0 && s[0] == '0')
196 x = (long) PyOS_strtoul(s, &end, base);
197 else
198 x = PyOS_strtol(s, &end, base);
Martin v. Löwis2b6727b2001-03-06 12:12:02 +0000199 if (end == s || !isalnum(Py_CHARMASK(end[-1])))
Barry Warsaw226ae6c1999-10-12 19:54:53 +0000200 goto bad;
201 while (*end && isspace(Py_CHARMASK(*end)))
202 end++;
203 if (*end != '\0') {
204 bad:
Barry Warsaw61975092001-11-28 20:55:34 +0000205 PyOS_snprintf(buffer, sizeof(buffer),
206 "invalid literal for int(): %.200s", s);
Barry Warsaw226ae6c1999-10-12 19:54:53 +0000207 PyErr_SetString(PyExc_ValueError, buffer);
208 return NULL;
209 }
210 else if (errno != 0) {
Barry Warsaw61975092001-11-28 20:55:34 +0000211 PyOS_snprintf(buffer, sizeof(buffer),
212 "int() literal too large: %.200s", s);
Barry Warsaw226ae6c1999-10-12 19:54:53 +0000213 PyErr_SetString(PyExc_ValueError, buffer);
214 return NULL;
215 }
216 if (pend)
217 *pend = end;
218 return PyInt_FromLong(x);
219}
220
Martin v. Löwis339d0f72001-08-17 18:39:25 +0000221#ifdef Py_USING_UNICODE
Guido van Rossum9e896b32000-04-05 20:11:21 +0000222PyObject *
Fred Drakea2f55112000-07-09 15:16:51 +0000223PyInt_FromUnicode(Py_UNICODE *s, int length, int base)
Guido van Rossum9e896b32000-04-05 20:11:21 +0000224{
225 char buffer[256];
Tim Petersa3c01ce2001-12-04 23:05:10 +0000226
Guido van Rossum9e896b32000-04-05 20:11:21 +0000227 if (length >= sizeof(buffer)) {
228 PyErr_SetString(PyExc_ValueError,
229 "int() literal too large to convert");
230 return NULL;
231 }
232 if (PyUnicode_EncodeDecimal(s, length, buffer, NULL))
233 return NULL;
234 return PyInt_FromString(buffer, NULL, base);
235}
Martin v. Löwis339d0f72001-08-17 18:39:25 +0000236#endif
Guido van Rossum9e896b32000-04-05 20:11:21 +0000237
Guido van Rossum85a5fbb1990-10-14 12:07:46 +0000238/* Methods */
239
Neil Schemenauer139e72a2001-01-04 01:45:33 +0000240/* Integers are seen as the "smallest" of all numeric types and thus
241 don't have any knowledge about conversion of other types to
242 integers. */
243
244#define CONVERT_TO_LONG(obj, lng) \
245 if (PyInt_Check(obj)) { \
246 lng = PyInt_AS_LONG(obj); \
247 } \
248 else { \
249 Py_INCREF(Py_NotImplemented); \
250 return Py_NotImplemented; \
251 }
252
Guido van Rossum719f5fa1992-03-27 17:31:02 +0000253/* ARGSUSED */
Guido van Rossum90933611991-06-07 16:10:43 +0000254static int
Fred Drakea2f55112000-07-09 15:16:51 +0000255int_print(PyIntObject *v, FILE *fp, int flags)
256 /* flags -- not used but required by interface */
Guido van Rossum85a5fbb1990-10-14 12:07:46 +0000257{
258 fprintf(fp, "%ld", v->ob_ival);
Guido van Rossum90933611991-06-07 16:10:43 +0000259 return 0;
Guido van Rossum85a5fbb1990-10-14 12:07:46 +0000260}
261
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000262static PyObject *
Fred Drakea2f55112000-07-09 15:16:51 +0000263int_repr(PyIntObject *v)
Guido van Rossum85a5fbb1990-10-14 12:07:46 +0000264{
Tim Peters42221042001-12-01 02:52:56 +0000265 char buf[64];
Barry Warsaw61975092001-11-28 20:55:34 +0000266 PyOS_snprintf(buf, sizeof(buf), "%ld", v->ob_ival);
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000267 return PyString_FromString(buf);
Guido van Rossum85a5fbb1990-10-14 12:07:46 +0000268}
269
270static int
Fred Drakea2f55112000-07-09 15:16:51 +0000271int_compare(PyIntObject *v, PyIntObject *w)
Guido van Rossum85a5fbb1990-10-14 12:07:46 +0000272{
273 register long i = v->ob_ival;
274 register long j = w->ob_ival;
275 return (i < j) ? -1 : (i > j) ? 1 : 0;
276}
277
Guido van Rossum9bfef441993-03-29 10:43:31 +0000278static long
Fred Drakea2f55112000-07-09 15:16:51 +0000279int_hash(PyIntObject *v)
Guido van Rossum9bfef441993-03-29 10:43:31 +0000280{
Guido van Rossum541cdd81997-01-06 22:53:20 +0000281 /* XXX If this is changed, you also need to change the way
282 Python's long, float and complex types are hashed. */
Guido van Rossum9bfef441993-03-29 10:43:31 +0000283 long x = v -> ob_ival;
284 if (x == -1)
285 x = -2;
286 return x;
287}
288
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000289static PyObject *
Fred Drakea2f55112000-07-09 15:16:51 +0000290int_add(PyIntObject *v, PyIntObject *w)
Guido van Rossum85a5fbb1990-10-14 12:07:46 +0000291{
292 register long a, b, x;
Neil Schemenauer139e72a2001-01-04 01:45:33 +0000293 CONVERT_TO_LONG(v, a);
294 CONVERT_TO_LONG(w, b);
Guido van Rossum85a5fbb1990-10-14 12:07:46 +0000295 x = a + b;
Guido van Rossume27f7952001-08-23 02:59:04 +0000296 if ((x^a) >= 0 || (x^b) >= 0)
297 return PyInt_FromLong(x);
298 if (err_ovf("integer addition"))
299 return NULL;
300 return PyLong_Type.tp_as_number->nb_add((PyObject *)v, (PyObject *)w);
Guido van Rossum85a5fbb1990-10-14 12:07:46 +0000301}
302
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000303static PyObject *
Fred Drakea2f55112000-07-09 15:16:51 +0000304int_sub(PyIntObject *v, PyIntObject *w)
Guido van Rossum85a5fbb1990-10-14 12:07:46 +0000305{
306 register long a, b, x;
Neil Schemenauer139e72a2001-01-04 01:45:33 +0000307 CONVERT_TO_LONG(v, a);
308 CONVERT_TO_LONG(w, b);
Guido van Rossum85a5fbb1990-10-14 12:07:46 +0000309 x = a - b;
Guido van Rossume27f7952001-08-23 02:59:04 +0000310 if ((x^a) >= 0 || (x^~b) >= 0)
311 return PyInt_FromLong(x);
312 if (err_ovf("integer subtraction"))
313 return NULL;
314 return PyLong_Type.tp_as_number->nb_subtract((PyObject *)v,
315 (PyObject *)w);
Guido van Rossum85a5fbb1990-10-14 12:07:46 +0000316}
317
Guido van Rossumbf8c0e31994-08-29 12:48:32 +0000318/*
Tim Petersa3c01ce2001-12-04 23:05:10 +0000319Integer overflow checking for * is painful: Python tried a couple ways, but
320they didn't work on all platforms, or failed in endcases (a product of
321-sys.maxint-1 has been a particular pain).
Guido van Rossumbf8c0e31994-08-29 12:48:32 +0000322
Tim Petersa3c01ce2001-12-04 23:05:10 +0000323Here's another way:
Guido van Rossumbf8c0e31994-08-29 12:48:32 +0000324
Tim Petersa3c01ce2001-12-04 23:05:10 +0000325The native long product x*y is either exactly right or *way* off, being
326just the last n bits of the true product, where n is the number of bits
327in a long (the delivered product is the true product plus i*2**n for
328some integer i).
Guido van Rossumbf8c0e31994-08-29 12:48:32 +0000329
Tim Petersa3c01ce2001-12-04 23:05:10 +0000330The native double product (double)x * (double)y is subject to three
331rounding errors: on a sizeof(long)==8 box, each cast to double can lose
332info, and even on a sizeof(long)==4 box, the multiplication can lose info.
333But, unlike the native long product, it's not in *range* trouble: even
334if sizeof(long)==32 (256-bit longs), the product easily fits in the
335dynamic range of a double. So the leading 50 (or so) bits of the double
336product are correct.
Guido van Rossumbf8c0e31994-08-29 12:48:32 +0000337
Tim Petersa3c01ce2001-12-04 23:05:10 +0000338We check these two ways against each other, and declare victory if they're
339approximately the same. Else, because the native long product is the only
340one that can lose catastrophic amounts of information, it's the native long
341product that must have overflowed.
Guido van Rossumbf8c0e31994-08-29 12:48:32 +0000342*/
343
Neil Schemenauer3bc3f282002-08-09 15:20:48 +0000344/* Return true if the sq_repeat method should be used */
345#define USE_SQ_REPEAT(o) (!PyInt_Check(o) && \
346 o->ob_type->tp_as_sequence && \
347 o->ob_type->tp_as_sequence->sq_repeat && \
348 (!o->ob_type->tp_as_number || \
349 !o->ob_type->tp_as_number->nb_multiply))
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000350static PyObject *
Neil Schemenauer139e72a2001-01-04 01:45:33 +0000351int_mul(PyObject *v, PyObject *w)
Guido van Rossum85a5fbb1990-10-14 12:07:46 +0000352{
Tim Petersa3c01ce2001-12-04 23:05:10 +0000353 long a, b;
354 long longprod; /* a*b in native long arithmetic */
355 double doubled_longprod; /* (double)longprod */
356 double doubleprod; /* (double)a * (double)b */
Guido van Rossumbf8c0e31994-08-29 12:48:32 +0000357
Neil Schemenauer3bc3f282002-08-09 15:20:48 +0000358 if (USE_SQ_REPEAT(v)) {
Neil Schemenauer139e72a2001-01-04 01:45:33 +0000359 /* sequence * int */
360 a = PyInt_AsLong(w);
361 return (*v->ob_type->tp_as_sequence->sq_repeat)(v, a);
362 }
Neil Schemenauer3bc3f282002-08-09 15:20:48 +0000363 if (USE_SQ_REPEAT(w)) {
Neil Schemenauer139e72a2001-01-04 01:45:33 +0000364 /* int * sequence */
365 a = PyInt_AsLong(v);
366 return (*w->ob_type->tp_as_sequence->sq_repeat)(w, a);
367 }
368
369 CONVERT_TO_LONG(v, a);
370 CONVERT_TO_LONG(w, b);
Tim Petersa3c01ce2001-12-04 23:05:10 +0000371 longprod = a * b;
372 doubleprod = (double)a * (double)b;
373 doubled_longprod = (double)longprod;
Guido van Rossumbf8c0e31994-08-29 12:48:32 +0000374
Tim Petersa3c01ce2001-12-04 23:05:10 +0000375 /* Fast path for normal case: small multiplicands, and no info
376 is lost in either method. */
377 if (doubled_longprod == doubleprod)
378 return PyInt_FromLong(longprod);
Guido van Rossumbf8c0e31994-08-29 12:48:32 +0000379
Tim Petersa3c01ce2001-12-04 23:05:10 +0000380 /* Somebody somewhere lost info. Close enough, or way off? Note
381 that a != 0 and b != 0 (else doubled_longprod == doubleprod == 0).
382 The difference either is or isn't significant compared to the
383 true value (of which doubleprod is a good approximation).
384 */
385 {
386 const double diff = doubled_longprod - doubleprod;
387 const double absdiff = diff >= 0.0 ? diff : -diff;
388 const double absprod = doubleprod >= 0.0 ? doubleprod :
389 -doubleprod;
390 /* absdiff/absprod <= 1/32 iff
391 32 * absdiff <= absprod -- 5 good bits is "close enough" */
392 if (32.0 * absdiff <= absprod)
393 return PyInt_FromLong(longprod);
394 else if (err_ovf("integer multiplication"))
395 return NULL;
396 else
397 return PyLong_Type.tp_as_number->nb_multiply(v, w);
Guido van Rossumbf8c0e31994-08-29 12:48:32 +0000398 }
Guido van Rossum85a5fbb1990-10-14 12:07:46 +0000399}
400
Guido van Rossume27f7952001-08-23 02:59:04 +0000401/* Return type of i_divmod */
402enum divmod_result {
403 DIVMOD_OK, /* Correct result */
404 DIVMOD_OVERFLOW, /* Overflow, try again using longs */
405 DIVMOD_ERROR /* Exception raised */
406};
407
408static enum divmod_result
Tim Peters1dad6a82001-06-18 19:21:11 +0000409i_divmod(register long x, register long y,
Fred Drakea2f55112000-07-09 15:16:51 +0000410 long *p_xdivy, long *p_xmody)
Guido van Rossum85a5fbb1990-10-14 12:07:46 +0000411{
Guido van Rossum2b16a6f1992-01-19 16:28:51 +0000412 long xdivy, xmody;
Tim Petersa3c01ce2001-12-04 23:05:10 +0000413
Tim Peters1dad6a82001-06-18 19:21:11 +0000414 if (y == 0) {
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000415 PyErr_SetString(PyExc_ZeroDivisionError,
Fred Drake661ea262000-10-24 19:57:45 +0000416 "integer division or modulo by zero");
Guido van Rossume27f7952001-08-23 02:59:04 +0000417 return DIVMOD_ERROR;
Guido van Rossum85a5fbb1990-10-14 12:07:46 +0000418 }
Tim Peters1dad6a82001-06-18 19:21:11 +0000419 /* (-sys.maxint-1)/-1 is the only overflow case. */
420 if (y == -1 && x < 0 && x == -x) {
Guido van Rossume27f7952001-08-23 02:59:04 +0000421 if (err_ovf("integer division"))
422 return DIVMOD_ERROR;
423 return DIVMOD_OVERFLOW;
Guido van Rossum00466951991-05-05 20:08:27 +0000424 }
Tim Peters1dad6a82001-06-18 19:21:11 +0000425 xdivy = x / y;
426 xmody = x - xdivy * y;
427 /* If the signs of x and y differ, and the remainder is non-0,
428 * C89 doesn't define whether xdivy is now the floor or the
429 * ceiling of the infinitely precise quotient. We want the floor,
430 * and we have it iff the remainder's sign matches y's.
431 */
432 if (xmody && ((y ^ xmody) < 0) /* i.e. and signs differ */) {
433 xmody += y;
434 --xdivy;
435 assert(xmody && ((y ^ xmody) >= 0));
Guido van Rossum00466951991-05-05 20:08:27 +0000436 }
Guido van Rossum2b16a6f1992-01-19 16:28:51 +0000437 *p_xdivy = xdivy;
438 *p_xmody = xmody;
Guido van Rossume27f7952001-08-23 02:59:04 +0000439 return DIVMOD_OK;
Guido van Rossum2b16a6f1992-01-19 16:28:51 +0000440}
441
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000442static PyObject *
Fred Drakea2f55112000-07-09 15:16:51 +0000443int_div(PyIntObject *x, PyIntObject *y)
Guido van Rossum2b16a6f1992-01-19 16:28:51 +0000444{
Neil Schemenauer139e72a2001-01-04 01:45:33 +0000445 long xi, yi;
Guido van Rossum2b16a6f1992-01-19 16:28:51 +0000446 long d, m;
Neil Schemenauer139e72a2001-01-04 01:45:33 +0000447 CONVERT_TO_LONG(x, xi);
448 CONVERT_TO_LONG(y, yi);
Guido van Rossume27f7952001-08-23 02:59:04 +0000449 switch (i_divmod(xi, yi, &d, &m)) {
450 case DIVMOD_OK:
451 return PyInt_FromLong(d);
452 case DIVMOD_OVERFLOW:
453 return PyLong_Type.tp_as_number->nb_divide((PyObject *)x,
454 (PyObject *)y);
455 default:
Guido van Rossum2b16a6f1992-01-19 16:28:51 +0000456 return NULL;
Guido van Rossume27f7952001-08-23 02:59:04 +0000457 }
Guido van Rossum2b16a6f1992-01-19 16:28:51 +0000458}
459
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000460static PyObject *
Guido van Rossum393661d2001-08-31 17:40:15 +0000461int_classic_div(PyIntObject *x, PyIntObject *y)
462{
463 long xi, yi;
464 long d, m;
465 CONVERT_TO_LONG(x, xi);
466 CONVERT_TO_LONG(y, yi);
467 if (Py_DivisionWarningFlag &&
468 PyErr_Warn(PyExc_DeprecationWarning, "classic int division") < 0)
469 return NULL;
470 switch (i_divmod(xi, yi, &d, &m)) {
471 case DIVMOD_OK:
472 return PyInt_FromLong(d);
473 case DIVMOD_OVERFLOW:
474 return PyLong_Type.tp_as_number->nb_divide((PyObject *)x,
475 (PyObject *)y);
476 default:
477 return NULL;
478 }
479}
480
481static PyObject *
Tim Peters9c1d7fd2001-09-04 05:52:47 +0000482int_true_divide(PyObject *v, PyObject *w)
483{
Tim Peterse2a60002001-09-04 06:17:36 +0000484 /* If they aren't both ints, give someone else a chance. In
485 particular, this lets int/long get handled by longs, which
486 underflows to 0 gracefully if the long is too big to convert
487 to float. */
488 if (PyInt_Check(v) && PyInt_Check(w))
489 return PyFloat_Type.tp_as_number->nb_true_divide(v, w);
490 Py_INCREF(Py_NotImplemented);
491 return Py_NotImplemented;
Tim Peters9c1d7fd2001-09-04 05:52:47 +0000492}
493
494static PyObject *
Fred Drakea2f55112000-07-09 15:16:51 +0000495int_mod(PyIntObject *x, PyIntObject *y)
Guido van Rossum2b16a6f1992-01-19 16:28:51 +0000496{
Neil Schemenauer139e72a2001-01-04 01:45:33 +0000497 long xi, yi;
Guido van Rossum2b16a6f1992-01-19 16:28:51 +0000498 long d, m;
Neil Schemenauer139e72a2001-01-04 01:45:33 +0000499 CONVERT_TO_LONG(x, xi);
500 CONVERT_TO_LONG(y, yi);
Guido van Rossume27f7952001-08-23 02:59:04 +0000501 switch (i_divmod(xi, yi, &d, &m)) {
502 case DIVMOD_OK:
503 return PyInt_FromLong(m);
504 case DIVMOD_OVERFLOW:
505 return PyLong_Type.tp_as_number->nb_remainder((PyObject *)x,
506 (PyObject *)y);
507 default:
Guido van Rossum2b16a6f1992-01-19 16:28:51 +0000508 return NULL;
Guido van Rossume27f7952001-08-23 02:59:04 +0000509 }
Guido van Rossum2b16a6f1992-01-19 16:28:51 +0000510}
511
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000512static PyObject *
Fred Drakea2f55112000-07-09 15:16:51 +0000513int_divmod(PyIntObject *x, PyIntObject *y)
Guido van Rossum2b16a6f1992-01-19 16:28:51 +0000514{
Neil Schemenauer139e72a2001-01-04 01:45:33 +0000515 long xi, yi;
Guido van Rossum2b16a6f1992-01-19 16:28:51 +0000516 long d, m;
Neil Schemenauer139e72a2001-01-04 01:45:33 +0000517 CONVERT_TO_LONG(x, xi);
518 CONVERT_TO_LONG(y, yi);
Guido van Rossume27f7952001-08-23 02:59:04 +0000519 switch (i_divmod(xi, yi, &d, &m)) {
520 case DIVMOD_OK:
521 return Py_BuildValue("(ll)", d, m);
522 case DIVMOD_OVERFLOW:
523 return PyLong_Type.tp_as_number->nb_divmod((PyObject *)x,
524 (PyObject *)y);
525 default:
Guido van Rossum2b16a6f1992-01-19 16:28:51 +0000526 return NULL;
Guido van Rossume27f7952001-08-23 02:59:04 +0000527 }
Guido van Rossum00466951991-05-05 20:08:27 +0000528}
529
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000530static PyObject *
Fred Drakea2f55112000-07-09 15:16:51 +0000531int_pow(PyIntObject *v, PyIntObject *w, PyIntObject *z)
Guido van Rossum85a5fbb1990-10-14 12:07:46 +0000532{
Guido van Rossum9478dd41996-12-06 20:14:43 +0000533 register long iv, iw, iz=0, ix, temp, prev;
Neil Schemenauer139e72a2001-01-04 01:45:33 +0000534 CONVERT_TO_LONG(v, iv);
535 CONVERT_TO_LONG(w, iw);
Guido van Rossumbf8c0e31994-08-29 12:48:32 +0000536 if (iw < 0) {
Tim Peters32f453e2001-09-03 08:35:41 +0000537 if ((PyObject *)z != Py_None) {
Tim Peters4c483c42001-09-05 06:24:58 +0000538 PyErr_SetString(PyExc_TypeError, "pow() 2nd argument "
539 "cannot be negative when 3rd argument specified");
Tim Peters32f453e2001-09-03 08:35:41 +0000540 return NULL;
541 }
Guido van Rossumb82fedc2001-07-12 11:19:45 +0000542 /* Return a float. This works because we know that
543 this calls float_pow() which converts its
544 arguments to double. */
545 return PyFloat_Type.tp_as_number->nb_power(
546 (PyObject *)v, (PyObject *)w, (PyObject *)z);
Guido van Rossumbf8c0e31994-08-29 12:48:32 +0000547 }
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000548 if ((PyObject *)z != Py_None) {
Neil Schemenauer139e72a2001-01-04 01:45:33 +0000549 CONVERT_TO_LONG(z, iz);
Guido van Rossum9478dd41996-12-06 20:14:43 +0000550 if (iz == 0) {
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000551 PyErr_SetString(PyExc_ValueError,
Tim Peters4c483c42001-09-05 06:24:58 +0000552 "pow() 3rd argument cannot be 0");
Guido van Rossum9478dd41996-12-06 20:14:43 +0000553 return NULL;
554 }
Guido van Rossumbf8c0e31994-08-29 12:48:32 +0000555 }
556 /*
557 * XXX: The original exponentiation code stopped looping
558 * when temp hit zero; this code will continue onwards
559 * unnecessarily, but at least it won't cause any errors.
560 * Hopefully the speed improvement from the fast exponentiation
561 * will compensate for the slight inefficiency.
562 * XXX: Better handling of overflows is desperately needed.
563 */
564 temp = iv;
565 ix = 1;
566 while (iw > 0) {
567 prev = ix; /* Save value for overflow check */
Tim Petersa3c01ce2001-12-04 23:05:10 +0000568 if (iw & 1) {
Guido van Rossumbf8c0e31994-08-29 12:48:32 +0000569 ix = ix*temp;
570 if (temp == 0)
571 break; /* Avoid ix / 0 */
Guido van Rossume27f7952001-08-23 02:59:04 +0000572 if (ix / temp != prev) {
573 if (err_ovf("integer exponentiation"))
574 return NULL;
575 return PyLong_Type.tp_as_number->nb_power(
576 (PyObject *)v,
577 (PyObject *)w,
Tim Peters31960db2001-08-23 21:28:33 +0000578 (PyObject *)z);
Guido van Rossume27f7952001-08-23 02:59:04 +0000579 }
Guido van Rossumbf8c0e31994-08-29 12:48:32 +0000580 }
581 iw >>= 1; /* Shift exponent down by 1 bit */
582 if (iw==0) break;
583 prev = temp;
584 temp *= temp; /* Square the value of temp */
Guido van Rossume27f7952001-08-23 02:59:04 +0000585 if (prev!=0 && temp/prev!=prev) {
586 if (err_ovf("integer exponentiation"))
587 return NULL;
588 return PyLong_Type.tp_as_number->nb_power(
589 (PyObject *)v, (PyObject *)w, (PyObject *)z);
590 }
Guido van Rossum9478dd41996-12-06 20:14:43 +0000591 if (iz) {
Guido van Rossumbf8c0e31994-08-29 12:48:32 +0000592 /* If we did a multiplication, perform a modulo */
593 ix = ix % iz;
594 temp = temp % iz;
595 }
596 }
Guido van Rossum9478dd41996-12-06 20:14:43 +0000597 if (iz) {
Neil Schemenauer139e72a2001-01-04 01:45:33 +0000598 long div, mod;
Guido van Rossume27f7952001-08-23 02:59:04 +0000599 switch (i_divmod(ix, iz, &div, &mod)) {
600 case DIVMOD_OK:
601 ix = mod;
602 break;
603 case DIVMOD_OVERFLOW:
604 return PyLong_Type.tp_as_number->nb_power(
605 (PyObject *)v, (PyObject *)w, (PyObject *)z);
606 default:
607 return NULL;
608 }
Guido van Rossumbf8c0e31994-08-29 12:48:32 +0000609 }
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000610 return PyInt_FromLong(ix);
Tim Petersa3c01ce2001-12-04 23:05:10 +0000611}
Guido van Rossum85a5fbb1990-10-14 12:07:46 +0000612
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000613static PyObject *
Fred Drakea2f55112000-07-09 15:16:51 +0000614int_neg(PyIntObject *v)
Guido van Rossum85a5fbb1990-10-14 12:07:46 +0000615{
616 register long a, x;
617 a = v->ob_ival;
618 x = -a;
Guido van Rossume27f7952001-08-23 02:59:04 +0000619 if (a < 0 && x < 0) {
620 if (err_ovf("integer negation"))
621 return NULL;
622 return PyNumber_Negative(PyLong_FromLong(a));
623 }
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000624 return PyInt_FromLong(x);
Guido van Rossum85a5fbb1990-10-14 12:07:46 +0000625}
626
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000627static PyObject *
Fred Drakea2f55112000-07-09 15:16:51 +0000628int_pos(PyIntObject *v)
Guido van Rossum85a5fbb1990-10-14 12:07:46 +0000629{
Tim Peters73a1dfe2001-09-11 21:44:14 +0000630 if (PyInt_CheckExact(v)) {
631 Py_INCREF(v);
632 return (PyObject *)v;
633 }
634 else
635 return PyInt_FromLong(v->ob_ival);
Guido van Rossum85a5fbb1990-10-14 12:07:46 +0000636}
637
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000638static PyObject *
Fred Drakea2f55112000-07-09 15:16:51 +0000639int_abs(PyIntObject *v)
Guido van Rossum00466951991-05-05 20:08:27 +0000640{
641 if (v->ob_ival >= 0)
642 return int_pos(v);
643 else
644 return int_neg(v);
645}
646
Guido van Rossum0bff0151991-05-14 12:05:32 +0000647static int
Fred Drakea2f55112000-07-09 15:16:51 +0000648int_nonzero(PyIntObject *v)
Guido van Rossum0bff0151991-05-14 12:05:32 +0000649{
650 return v->ob_ival != 0;
651}
652
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000653static PyObject *
Fred Drakea2f55112000-07-09 15:16:51 +0000654int_invert(PyIntObject *v)
Guido van Rossum7928cd71991-10-24 14:59:31 +0000655{
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000656 return PyInt_FromLong(~v->ob_ival);
Guido van Rossum7928cd71991-10-24 14:59:31 +0000657}
658
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000659static PyObject *
Fred Drakea2f55112000-07-09 15:16:51 +0000660int_lshift(PyIntObject *v, PyIntObject *w)
Guido van Rossum7928cd71991-10-24 14:59:31 +0000661{
662 register long a, b;
Neil Schemenauer139e72a2001-01-04 01:45:33 +0000663 CONVERT_TO_LONG(v, a);
664 CONVERT_TO_LONG(w, b);
Guido van Rossumf3b351f1992-01-14 18:33:22 +0000665 if (b < 0) {
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000666 PyErr_SetString(PyExc_ValueError, "negative shift count");
Guido van Rossumf3b351f1992-01-14 18:33:22 +0000667 return NULL;
668 }
Tim Peters73a1dfe2001-09-11 21:44:14 +0000669 if (a == 0 || b == 0)
670 return int_pos(v);
Guido van Rossum72481a31993-10-26 15:21:51 +0000671 if (b >= LONG_BIT) {
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000672 return PyInt_FromLong(0L);
Guido van Rossumf3b351f1992-01-14 18:33:22 +0000673 }
Fred Drake1bc8fab2001-07-19 21:49:38 +0000674 a = (long)((unsigned long)a << b);
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000675 return PyInt_FromLong(a);
Guido van Rossum7928cd71991-10-24 14:59:31 +0000676}
677
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000678static PyObject *
Fred Drakea2f55112000-07-09 15:16:51 +0000679int_rshift(PyIntObject *v, PyIntObject *w)
Guido van Rossum7928cd71991-10-24 14:59:31 +0000680{
681 register long a, b;
Neil Schemenauer139e72a2001-01-04 01:45:33 +0000682 CONVERT_TO_LONG(v, a);
683 CONVERT_TO_LONG(w, b);
Guido van Rossumf3b351f1992-01-14 18:33:22 +0000684 if (b < 0) {
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000685 PyErr_SetString(PyExc_ValueError, "negative shift count");
Guido van Rossumf3b351f1992-01-14 18:33:22 +0000686 return NULL;
687 }
Tim Peters73a1dfe2001-09-11 21:44:14 +0000688 if (a == 0 || b == 0)
689 return int_pos(v);
Guido van Rossum72481a31993-10-26 15:21:51 +0000690 if (b >= LONG_BIT) {
Guido van Rossumf3b351f1992-01-14 18:33:22 +0000691 if (a < 0)
692 a = -1;
693 else
694 a = 0;
695 }
696 else {
Tim Peters7d3a5112000-07-08 04:17:21 +0000697 a = Py_ARITHMETIC_RIGHT_SHIFT(long, a, b);
Guido van Rossumf3b351f1992-01-14 18:33:22 +0000698 }
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000699 return PyInt_FromLong(a);
Guido van Rossum7928cd71991-10-24 14:59:31 +0000700}
701
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000702static PyObject *
Fred Drakea2f55112000-07-09 15:16:51 +0000703int_and(PyIntObject *v, PyIntObject *w)
Guido van Rossum7928cd71991-10-24 14:59:31 +0000704{
705 register long a, b;
Neil Schemenauer139e72a2001-01-04 01:45:33 +0000706 CONVERT_TO_LONG(v, a);
707 CONVERT_TO_LONG(w, b);
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000708 return PyInt_FromLong(a & b);
Guido van Rossum7928cd71991-10-24 14:59:31 +0000709}
710
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000711static PyObject *
Fred Drakea2f55112000-07-09 15:16:51 +0000712int_xor(PyIntObject *v, PyIntObject *w)
Guido van Rossum7928cd71991-10-24 14:59:31 +0000713{
714 register long a, b;
Neil Schemenauer139e72a2001-01-04 01:45:33 +0000715 CONVERT_TO_LONG(v, a);
716 CONVERT_TO_LONG(w, b);
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000717 return PyInt_FromLong(a ^ b);
Guido van Rossum7928cd71991-10-24 14:59:31 +0000718}
719
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000720static PyObject *
Fred Drakea2f55112000-07-09 15:16:51 +0000721int_or(PyIntObject *v, PyIntObject *w)
Guido van Rossum7928cd71991-10-24 14:59:31 +0000722{
723 register long a, b;
Neil Schemenauer139e72a2001-01-04 01:45:33 +0000724 CONVERT_TO_LONG(v, a);
725 CONVERT_TO_LONG(w, b);
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000726 return PyInt_FromLong(a | b);
Guido van Rossum7928cd71991-10-24 14:59:31 +0000727}
728
Guido van Rossum1952e382001-09-19 01:25:16 +0000729static int
730int_coerce(PyObject **pv, PyObject **pw)
731{
732 if (PyInt_Check(*pw)) {
733 Py_INCREF(*pv);
734 Py_INCREF(*pw);
735 return 0;
736 }
737 return 1; /* Can't do it */
738}
739
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000740static PyObject *
Fred Drakea2f55112000-07-09 15:16:51 +0000741int_int(PyIntObject *v)
Guido van Rossum1899c2e1992-09-12 11:09:23 +0000742{
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000743 Py_INCREF(v);
744 return (PyObject *)v;
Guido van Rossum1899c2e1992-09-12 11:09:23 +0000745}
746
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000747static PyObject *
Fred Drakea2f55112000-07-09 15:16:51 +0000748int_long(PyIntObject *v)
Guido van Rossum1899c2e1992-09-12 11:09:23 +0000749{
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000750 return PyLong_FromLong((v -> ob_ival));
Guido van Rossum1899c2e1992-09-12 11:09:23 +0000751}
752
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000753static PyObject *
Fred Drakea2f55112000-07-09 15:16:51 +0000754int_float(PyIntObject *v)
Guido van Rossum1899c2e1992-09-12 11:09:23 +0000755{
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000756 return PyFloat_FromDouble((double)(v -> ob_ival));
Guido van Rossum1899c2e1992-09-12 11:09:23 +0000757}
758
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000759static PyObject *
Fred Drakea2f55112000-07-09 15:16:51 +0000760int_oct(PyIntObject *v)
Guido van Rossum1899c2e1992-09-12 11:09:23 +0000761{
Guido van Rossum6f72f971997-01-14 15:43:41 +0000762 char buf[100];
Guido van Rossum9bfef441993-03-29 10:43:31 +0000763 long x = v -> ob_ival;
Guido van Rossum1899c2e1992-09-12 11:09:23 +0000764 if (x == 0)
765 strcpy(buf, "0");
Guido van Rossum1899c2e1992-09-12 11:09:23 +0000766 else
Barry Warsaw61975092001-11-28 20:55:34 +0000767 PyOS_snprintf(buf, sizeof(buf), "0%lo", x);
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000768 return PyString_FromString(buf);
Guido van Rossum1899c2e1992-09-12 11:09:23 +0000769}
770
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000771static PyObject *
Fred Drakea2f55112000-07-09 15:16:51 +0000772int_hex(PyIntObject *v)
Guido van Rossum1899c2e1992-09-12 11:09:23 +0000773{
Guido van Rossum6f72f971997-01-14 15:43:41 +0000774 char buf[100];
Guido van Rossum9bfef441993-03-29 10:43:31 +0000775 long x = v -> ob_ival;
Barry Warsaw61975092001-11-28 20:55:34 +0000776 PyOS_snprintf(buf, sizeof(buf), "0x%lx", x);
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000777 return PyString_FromString(buf);
Guido van Rossum1899c2e1992-09-12 11:09:23 +0000778}
779
Jeremy Hylton938ace62002-07-17 16:30:39 +0000780static PyObject *
Guido van Rossumbef14172001-08-29 15:47:46 +0000781int_subtype_new(PyTypeObject *type, PyObject *args, PyObject *kwds);
782
Tim Peters6d6c1a32001-08-02 04:15:00 +0000783static PyObject *
784int_new(PyTypeObject *type, PyObject *args, PyObject *kwds)
785{
786 PyObject *x = NULL;
787 int base = -909;
788 static char *kwlist[] = {"x", "base", 0};
789
Guido van Rossumbef14172001-08-29 15:47:46 +0000790 if (type != &PyInt_Type)
791 return int_subtype_new(type, args, kwds); /* Wimp out */
Tim Peters6d6c1a32001-08-02 04:15:00 +0000792 if (!PyArg_ParseTupleAndKeywords(args, kwds, "|Oi:int", kwlist,
793 &x, &base))
794 return NULL;
795 if (x == NULL)
796 return PyInt_FromLong(0L);
797 if (base == -909)
798 return PyNumber_Int(x);
799 if (PyString_Check(x))
800 return PyInt_FromString(PyString_AS_STRING(x), NULL, base);
Martin v. Löwis339d0f72001-08-17 18:39:25 +0000801#ifdef Py_USING_UNICODE
Tim Peters6d6c1a32001-08-02 04:15:00 +0000802 if (PyUnicode_Check(x))
803 return PyInt_FromUnicode(PyUnicode_AS_UNICODE(x),
804 PyUnicode_GET_SIZE(x),
805 base);
Martin v. Löwis339d0f72001-08-17 18:39:25 +0000806#endif
Tim Peters6d6c1a32001-08-02 04:15:00 +0000807 PyErr_SetString(PyExc_TypeError,
808 "int() can't convert non-string with explicit base");
809 return NULL;
810}
811
Guido van Rossumbef14172001-08-29 15:47:46 +0000812/* Wimpy, slow approach to tp_new calls for subtypes of int:
813 first create a regular int from whatever arguments we got,
814 then allocate a subtype instance and initialize its ob_ival
815 from the regular int. The regular int is then thrown away.
816*/
817static PyObject *
818int_subtype_new(PyTypeObject *type, PyObject *args, PyObject *kwds)
819{
820 PyObject *tmp, *new;
821
822 assert(PyType_IsSubtype(type, &PyInt_Type));
823 tmp = int_new(&PyInt_Type, args, kwds);
824 if (tmp == NULL)
825 return NULL;
826 assert(PyInt_Check(tmp));
Guido van Rossumd93dce12001-08-30 03:09:31 +0000827 new = type->tp_alloc(type, 0);
Guido van Rossumbef14172001-08-29 15:47:46 +0000828 if (new == NULL)
829 return NULL;
830 ((PyIntObject *)new)->ob_ival = ((PyIntObject *)tmp)->ob_ival;
831 Py_DECREF(tmp);
832 return new;
833}
834
Martin v. Löwis14f8b4c2002-06-13 20:33:02 +0000835PyDoc_STRVAR(int_doc,
Tim Peters6d6c1a32001-08-02 04:15:00 +0000836"int(x[, base]) -> integer\n\
837\n\
838Convert a string or number to an integer, if possible. A floating point\n\
839argument will be truncated towards zero (this does not include a string\n\
840representation of a floating point number!) When converting a string, use\n\
841the optional base. It is an error to supply a base when converting a\n\
Martin v. Löwis14f8b4c2002-06-13 20:33:02 +0000842non-string.");
Tim Peters6d6c1a32001-08-02 04:15:00 +0000843
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000844static PyNumberMethods int_as_number = {
Neil Schemenauer139e72a2001-01-04 01:45:33 +0000845 (binaryfunc)int_add, /*nb_add*/
846 (binaryfunc)int_sub, /*nb_subtract*/
847 (binaryfunc)int_mul, /*nb_multiply*/
Guido van Rossum393661d2001-08-31 17:40:15 +0000848 (binaryfunc)int_classic_div, /*nb_divide*/
Neil Schemenauer139e72a2001-01-04 01:45:33 +0000849 (binaryfunc)int_mod, /*nb_remainder*/
850 (binaryfunc)int_divmod, /*nb_divmod*/
851 (ternaryfunc)int_pow, /*nb_power*/
852 (unaryfunc)int_neg, /*nb_negative*/
853 (unaryfunc)int_pos, /*nb_positive*/
854 (unaryfunc)int_abs, /*nb_absolute*/
855 (inquiry)int_nonzero, /*nb_nonzero*/
856 (unaryfunc)int_invert, /*nb_invert*/
857 (binaryfunc)int_lshift, /*nb_lshift*/
858 (binaryfunc)int_rshift, /*nb_rshift*/
859 (binaryfunc)int_and, /*nb_and*/
860 (binaryfunc)int_xor, /*nb_xor*/
861 (binaryfunc)int_or, /*nb_or*/
Guido van Rossum1952e382001-09-19 01:25:16 +0000862 int_coerce, /*nb_coerce*/
Neil Schemenauer139e72a2001-01-04 01:45:33 +0000863 (unaryfunc)int_int, /*nb_int*/
864 (unaryfunc)int_long, /*nb_long*/
865 (unaryfunc)int_float, /*nb_float*/
866 (unaryfunc)int_oct, /*nb_oct*/
867 (unaryfunc)int_hex, /*nb_hex*/
868 0, /*nb_inplace_add*/
869 0, /*nb_inplace_subtract*/
870 0, /*nb_inplace_multiply*/
871 0, /*nb_inplace_divide*/
872 0, /*nb_inplace_remainder*/
873 0, /*nb_inplace_power*/
874 0, /*nb_inplace_lshift*/
875 0, /*nb_inplace_rshift*/
876 0, /*nb_inplace_and*/
877 0, /*nb_inplace_xor*/
878 0, /*nb_inplace_or*/
Guido van Rossum4668b002001-08-08 05:00:18 +0000879 (binaryfunc)int_div, /* nb_floor_divide */
880 int_true_divide, /* nb_true_divide */
881 0, /* nb_inplace_floor_divide */
882 0, /* nb_inplace_true_divide */
Guido van Rossum85a5fbb1990-10-14 12:07:46 +0000883};
884
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000885PyTypeObject PyInt_Type = {
886 PyObject_HEAD_INIT(&PyType_Type)
Guido van Rossum85a5fbb1990-10-14 12:07:46 +0000887 0,
888 "int",
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000889 sizeof(PyIntObject),
Guido van Rossum85a5fbb1990-10-14 12:07:46 +0000890 0,
Tim Peters6d6c1a32001-08-02 04:15:00 +0000891 (destructor)int_dealloc, /* tp_dealloc */
892 (printfunc)int_print, /* tp_print */
893 0, /* tp_getattr */
894 0, /* tp_setattr */
895 (cmpfunc)int_compare, /* tp_compare */
896 (reprfunc)int_repr, /* tp_repr */
897 &int_as_number, /* tp_as_number */
898 0, /* tp_as_sequence */
899 0, /* tp_as_mapping */
900 (hashfunc)int_hash, /* tp_hash */
901 0, /* tp_call */
Guido van Rossume75bfde2002-02-01 15:34:10 +0000902 (reprfunc)int_repr, /* tp_str */
Tim Peters6d6c1a32001-08-02 04:15:00 +0000903 PyObject_GenericGetAttr, /* tp_getattro */
904 0, /* tp_setattro */
905 0, /* tp_as_buffer */
Guido van Rossumbef14172001-08-29 15:47:46 +0000906 Py_TPFLAGS_DEFAULT | Py_TPFLAGS_CHECKTYPES |
907 Py_TPFLAGS_BASETYPE, /* tp_flags */
Tim Peters6d6c1a32001-08-02 04:15:00 +0000908 int_doc, /* tp_doc */
909 0, /* tp_traverse */
910 0, /* tp_clear */
911 0, /* tp_richcompare */
912 0, /* tp_weaklistoffset */
913 0, /* tp_iter */
914 0, /* tp_iternext */
915 0, /* tp_methods */
916 0, /* tp_members */
917 0, /* tp_getset */
918 0, /* tp_base */
919 0, /* tp_dict */
920 0, /* tp_descr_get */
921 0, /* tp_descr_set */
922 0, /* tp_dictoffset */
923 0, /* tp_init */
924 0, /* tp_alloc */
925 int_new, /* tp_new */
Guido van Rossum93646982002-04-26 00:53:34 +0000926 (freefunc)int_free, /* tp_free */
Guido van Rossum85a5fbb1990-10-14 12:07:46 +0000927};
Guido van Rossumfbbd57e1997-08-05 02:16:08 +0000928
929void
Fred Drakea2f55112000-07-09 15:16:51 +0000930PyInt_Fini(void)
Guido van Rossumfbbd57e1997-08-05 02:16:08 +0000931{
Guido van Rossum3fce8831999-03-12 19:43:17 +0000932 PyIntObject *p;
933 PyIntBlock *list, *next;
Guido van Rossumfbbd57e1997-08-05 02:16:08 +0000934 int i;
Guido van Rossumda084ed1999-03-10 22:55:24 +0000935 int bc, bf; /* block count, number of freed blocks */
936 int irem, isum; /* remaining unfreed ints per block, total */
Guido van Rossumfbbd57e1997-08-05 02:16:08 +0000937
Guido van Rossumda084ed1999-03-10 22:55:24 +0000938#if NSMALLNEGINTS + NSMALLPOSINTS > 0
939 PyIntObject **q;
940
941 i = NSMALLNEGINTS + NSMALLPOSINTS;
942 q = small_ints;
943 while (--i >= 0) {
944 Py_XDECREF(*q);
945 *q++ = NULL;
946 }
Guido van Rossumfbbd57e1997-08-05 02:16:08 +0000947#endif
Guido van Rossumda084ed1999-03-10 22:55:24 +0000948 bc = 0;
949 bf = 0;
950 isum = 0;
951 list = block_list;
952 block_list = NULL;
Guido van Rossum51288bc1999-03-19 20:30:39 +0000953 free_list = NULL;
Guido van Rossumda084ed1999-03-10 22:55:24 +0000954 while (list != NULL) {
Guido van Rossumda084ed1999-03-10 22:55:24 +0000955 bc++;
956 irem = 0;
Guido van Rossum51288bc1999-03-19 20:30:39 +0000957 for (i = 0, p = &list->objects[0];
958 i < N_INTOBJECTS;
959 i++, p++) {
Guido van Rossumdea6ef92001-09-11 16:13:52 +0000960 if (PyInt_CheckExact(p) && p->ob_refcnt != 0)
Guido van Rossumda084ed1999-03-10 22:55:24 +0000961 irem++;
962 }
Guido van Rossum3fce8831999-03-12 19:43:17 +0000963 next = list->next;
Guido van Rossumda084ed1999-03-10 22:55:24 +0000964 if (irem) {
Guido van Rossum3fce8831999-03-12 19:43:17 +0000965 list->next = block_list;
966 block_list = list;
Guido van Rossum51288bc1999-03-19 20:30:39 +0000967 for (i = 0, p = &list->objects[0];
968 i < N_INTOBJECTS;
969 i++, p++) {
Guido van Rossumdea6ef92001-09-11 16:13:52 +0000970 if (!PyInt_CheckExact(p) ||
Guido van Rossumbef14172001-08-29 15:47:46 +0000971 p->ob_refcnt == 0) {
Guido van Rossum51288bc1999-03-19 20:30:39 +0000972 p->ob_type = (struct _typeobject *)
973 free_list;
974 free_list = p;
975 }
976#if NSMALLNEGINTS + NSMALLPOSINTS > 0
977 else if (-NSMALLNEGINTS <= p->ob_ival &&
978 p->ob_ival < NSMALLPOSINTS &&
979 small_ints[p->ob_ival +
980 NSMALLNEGINTS] == NULL) {
981 Py_INCREF(p);
982 small_ints[p->ob_ival +
983 NSMALLNEGINTS] = p;
984 }
985#endif
986 }
Guido van Rossumda084ed1999-03-10 22:55:24 +0000987 }
988 else {
Tim Peters29c0afc2002-04-28 16:57:34 +0000989 PyMem_FREE(list);
Guido van Rossumda084ed1999-03-10 22:55:24 +0000990 bf++;
991 }
992 isum += irem;
Guido van Rossum3fce8831999-03-12 19:43:17 +0000993 list = next;
Guido van Rossumda084ed1999-03-10 22:55:24 +0000994 }
Guido van Rossum3fce8831999-03-12 19:43:17 +0000995 if (!Py_VerboseFlag)
996 return;
997 fprintf(stderr, "# cleanup ints");
998 if (!isum) {
999 fprintf(stderr, "\n");
1000 }
1001 else {
1002 fprintf(stderr,
1003 ": %d unfreed int%s in %d out of %d block%s\n",
1004 isum, isum == 1 ? "" : "s",
1005 bc - bf, bc, bc == 1 ? "" : "s");
1006 }
1007 if (Py_VerboseFlag > 1) {
1008 list = block_list;
1009 while (list != NULL) {
Guido van Rossum51288bc1999-03-19 20:30:39 +00001010 for (i = 0, p = &list->objects[0];
1011 i < N_INTOBJECTS;
1012 i++, p++) {
Guido van Rossumdea6ef92001-09-11 16:13:52 +00001013 if (PyInt_CheckExact(p) && p->ob_refcnt != 0)
Guido van Rossum3fce8831999-03-12 19:43:17 +00001014 fprintf(stderr,
Fred Drakea44d3532000-06-30 15:01:00 +00001015 "# <int at %p, refcnt=%d, val=%ld>\n",
1016 p, p->ob_refcnt, p->ob_ival);
Guido van Rossum3fce8831999-03-12 19:43:17 +00001017 }
1018 list = list->next;
Guido van Rossumda084ed1999-03-10 22:55:24 +00001019 }
1020 }
Guido van Rossumfbbd57e1997-08-05 02:16:08 +00001021}