blob: 4db2a69bab00c3c36bc8d10e92510d0b16c2d6ea [file] [log] [blame]
Guido van Rossumf70e43a1991-02-19 12:39:46 +00001/***********************************************************
Guido van Rossum6610ad91995-01-04 19:07:38 +00002Copyright 1991-1995 by Stichting Mathematisch Centrum, Amsterdam,
3The Netherlands.
Guido van Rossumf70e43a1991-02-19 12:39:46 +00004
5 All Rights Reserved
6
Guido van Rossumd266eb41996-10-25 14:44:06 +00007Permission to use, copy, modify, and distribute this software and its
8documentation for any purpose and without fee is hereby granted,
Guido van Rossumf70e43a1991-02-19 12:39:46 +00009provided that the above copyright notice appear in all copies and that
Guido van Rossumd266eb41996-10-25 14:44:06 +000010both that copyright notice and this permission notice appear in
Guido van Rossumf70e43a1991-02-19 12:39:46 +000011supporting documentation, and that the names of Stichting Mathematisch
Guido van Rossumd266eb41996-10-25 14:44:06 +000012Centrum or CWI or Corporation for National Research Initiatives or
13CNRI not be used in advertising or publicity pertaining to
14distribution of the software without specific, written prior
15permission.
Guido van Rossumf70e43a1991-02-19 12:39:46 +000016
Guido van Rossumd266eb41996-10-25 14:44:06 +000017While CWI is the initial source for this software, a modified version
18is made available by the Corporation for National Research Initiatives
19(CNRI) at the Internet address ftp://ftp.python.org.
20
21STICHTING MATHEMATISCH CENTRUM AND CNRI DISCLAIM ALL WARRANTIES WITH
22REGARD TO THIS SOFTWARE, INCLUDING ALL IMPLIED WARRANTIES OF
23MERCHANTABILITY AND FITNESS, IN NO EVENT SHALL STICHTING MATHEMATISCH
24CENTRUM OR CNRI BE LIABLE FOR ANY SPECIAL, INDIRECT OR CONSEQUENTIAL
25DAMAGES OR ANY DAMAGES WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR
26PROFITS, WHETHER IN AN ACTION OF CONTRACT, NEGLIGENCE OR OTHER
27TORTIOUS ACTION, ARISING OUT OF OR IN CONNECTION WITH THE USE OR
28PERFORMANCE OF THIS SOFTWARE.
Guido van Rossumf70e43a1991-02-19 12:39:46 +000029
30******************************************************************/
31
Guido van Rossum85a5fbb1990-10-14 12:07:46 +000032/* Integer object implementation */
33
Guido van Rossumc0b618a1997-05-02 03:12:38 +000034#include "Python.h"
Guido van Rossum85a5fbb1990-10-14 12:07:46 +000035
Guido van Rossumbf8c0e31994-08-29 12:48:32 +000036#ifdef HAVE_LIMITS_H
Guido van Rossum72481a31993-10-26 15:21:51 +000037#include <limits.h>
38#endif
39
40#ifndef LONG_MAX
41#define LONG_MAX 0X7FFFFFFFL
42#endif
43
44#ifndef LONG_MIN
45#define LONG_MIN (-LONG_MAX-1)
46#endif
47
48#ifndef CHAR_BIT
49#define CHAR_BIT 8
50#endif
51
Guido van Rossumb376a4a1993-11-23 17:53:17 +000052#ifndef LONG_BIT
Guido van Rossum72481a31993-10-26 15:21:51 +000053#define LONG_BIT (CHAR_BIT * sizeof(long))
Guido van Rossumb376a4a1993-11-23 17:53:17 +000054#endif
Guido van Rossum72481a31993-10-26 15:21:51 +000055
Guido van Rossum2e1d4331993-12-24 10:22:45 +000056long
Guido van Rossumc0b618a1997-05-02 03:12:38 +000057PyInt_GetMax()
Guido van Rossum2e1d4331993-12-24 10:22:45 +000058{
59 return LONG_MAX; /* To initialize sys.maxint */
60}
61
Guido van Rossum85a5fbb1990-10-14 12:07:46 +000062/* Standard Booleans */
Guido van Rossum3f5da241990-12-20 15:06:42 +000063
Guido van Rossumc0b618a1997-05-02 03:12:38 +000064PyIntObject _Py_ZeroStruct = {
65 PyObject_HEAD_INIT(&PyInt_Type)
Guido van Rossum85a5fbb1990-10-14 12:07:46 +000066 0
67};
Guido van Rossum3f5da241990-12-20 15:06:42 +000068
Guido van Rossumc0b618a1997-05-02 03:12:38 +000069PyIntObject _Py_TrueStruct = {
70 PyObject_HEAD_INIT(&PyInt_Type)
Guido van Rossum85a5fbb1990-10-14 12:07:46 +000071 1
72};
73
Guido van Rossumc0b618a1997-05-02 03:12:38 +000074static PyObject *
Guido van Rossum3a628451991-12-10 13:57:36 +000075err_ovf(msg)
76 char *msg;
Guido van Rossum165e67e1990-10-14 20:02:26 +000077{
Guido van Rossumc0b618a1997-05-02 03:12:38 +000078 PyErr_SetString(PyExc_OverflowError, msg);
Guido van Rossum165e67e1990-10-14 20:02:26 +000079 return NULL;
80}
81
Guido van Rossum3f5da241990-12-20 15:06:42 +000082/* Integers are quite normal objects, to make object handling uniform.
83 (Using odd pointers to represent integers would save much space
84 but require extra checks for this special case throughout the code.)
85 Since, a typical Python program spends much of its time allocating
86 and deallocating integers, these operations should be very fast.
87 Therefore we use a dedicated allocation scheme with a much lower
88 overhead (in space and time) than straight malloc(): a simple
89 dedicated free list, filled when necessary with memory from malloc().
90*/
91
92#define BLOCK_SIZE 1000 /* 1K less typical malloc overhead */
Guido van Rossumc0b618a1997-05-02 03:12:38 +000093#define N_INTOBJECTS (BLOCK_SIZE / sizeof(PyIntObject))
Guido van Rossum3f5da241990-12-20 15:06:42 +000094
Guido van Rossumc0b618a1997-05-02 03:12:38 +000095static PyIntObject *
Guido van Rossum3f5da241990-12-20 15:06:42 +000096fill_free_list()
97{
Guido van Rossumc0b618a1997-05-02 03:12:38 +000098 PyIntObject *p, *q;
99 p = PyMem_NEW(PyIntObject, N_INTOBJECTS);
Guido van Rossum3f5da241990-12-20 15:06:42 +0000100 if (p == NULL)
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000101 return (PyIntObject *)PyErr_NoMemory();
Guido van Rossum3f5da241990-12-20 15:06:42 +0000102 q = p + N_INTOBJECTS;
103 while (--q > p)
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000104 *(PyIntObject **)q = q-1;
105 *(PyIntObject **)q = NULL;
Guido van Rossum3f5da241990-12-20 15:06:42 +0000106 return p + N_INTOBJECTS - 1;
107}
108
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000109static PyIntObject *free_list = NULL;
Sjoerd Mullender842d2cc1993-10-15 16:18:48 +0000110#ifndef NSMALLPOSINTS
111#define NSMALLPOSINTS 100
112#endif
113#ifndef NSMALLNEGINTS
114#define NSMALLNEGINTS 1
115#endif
116#if NSMALLNEGINTS + NSMALLPOSINTS > 0
117/* References to small integers are saved in this array so that they
118 can be shared.
119 The integers that are saved are those in the range
120 -NSMALLNEGINTS (inclusive) to NSMALLPOSINTS (not inclusive).
121*/
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000122static PyIntObject *small_ints[NSMALLNEGINTS + NSMALLPOSINTS];
Sjoerd Mullender842d2cc1993-10-15 16:18:48 +0000123#endif
124#ifdef COUNT_ALLOCS
125int quick_int_allocs, quick_neg_int_allocs;
126#endif
Guido van Rossum3f5da241990-12-20 15:06:42 +0000127
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000128PyObject *
129PyInt_FromLong(ival)
Guido van Rossum85a5fbb1990-10-14 12:07:46 +0000130 long ival;
131{
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000132 register PyIntObject *v;
Sjoerd Mullender842d2cc1993-10-15 16:18:48 +0000133#if NSMALLNEGINTS + NSMALLPOSINTS > 0
134 if (-NSMALLNEGINTS <= ival && ival < NSMALLPOSINTS &&
135 (v = small_ints[ival + NSMALLNEGINTS]) != NULL) {
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000136 Py_INCREF(v);
Sjoerd Mullender842d2cc1993-10-15 16:18:48 +0000137#ifdef COUNT_ALLOCS
138 if (ival >= 0)
139 quick_int_allocs++;
140 else
141 quick_neg_int_allocs++;
142#endif
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000143 return (PyObject *) v;
Sjoerd Mullender842d2cc1993-10-15 16:18:48 +0000144 }
145#endif
Guido van Rossum3f5da241990-12-20 15:06:42 +0000146 if (free_list == NULL) {
147 if ((free_list = fill_free_list()) == NULL)
148 return NULL;
Guido van Rossum85a5fbb1990-10-14 12:07:46 +0000149 }
Guido van Rossum3f5da241990-12-20 15:06:42 +0000150 v = free_list;
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000151 free_list = *(PyIntObject **)free_list;
152 v->ob_type = &PyInt_Type;
Guido van Rossum3f5da241990-12-20 15:06:42 +0000153 v->ob_ival = ival;
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000154 _Py_NewReference(v);
Sjoerd Mullender842d2cc1993-10-15 16:18:48 +0000155#if NSMALLNEGINTS + NSMALLPOSINTS > 0
156 if (-NSMALLNEGINTS <= ival && ival < NSMALLPOSINTS) {
157 /* save this one for a following allocation */
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000158 Py_INCREF(v);
Sjoerd Mullender842d2cc1993-10-15 16:18:48 +0000159 small_ints[ival + NSMALLNEGINTS] = v;
160 }
161#endif
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000162 return (PyObject *) v;
Guido van Rossum3f5da241990-12-20 15:06:42 +0000163}
164
165static void
166int_dealloc(v)
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000167 PyIntObject *v;
Guido van Rossum3f5da241990-12-20 15:06:42 +0000168{
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000169 *(PyIntObject **)v = free_list;
Guido van Rossum3f5da241990-12-20 15:06:42 +0000170 free_list = v;
Guido van Rossum85a5fbb1990-10-14 12:07:46 +0000171}
172
173long
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000174PyInt_AsLong(op)
175 register PyObject *op;
Guido van Rossum85a5fbb1990-10-14 12:07:46 +0000176{
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000177 PyNumberMethods *nb;
178 PyIntObject *io;
Guido van Rossumbf8c0e31994-08-29 12:48:32 +0000179 long val;
180
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000181 if (op && PyInt_Check(op))
182 return PyInt_AS_LONG((PyIntObject*) op);
Guido van Rossumbf8c0e31994-08-29 12:48:32 +0000183
184 if (op == NULL || (nb = op->ob_type->tp_as_number) == NULL ||
185 nb->nb_int == NULL) {
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000186 PyErr_BadArgument();
Guido van Rossum85a5fbb1990-10-14 12:07:46 +0000187 return -1;
188 }
Guido van Rossumbf8c0e31994-08-29 12:48:32 +0000189
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000190 io = (PyIntObject*) (*nb->nb_int) (op);
Guido van Rossumbf8c0e31994-08-29 12:48:32 +0000191 if (io == NULL)
192 return -1;
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000193 if (!PyInt_Check(io)) {
194 PyErr_SetString(PyExc_TypeError,
195 "nb_int should return int object");
Guido van Rossumbf8c0e31994-08-29 12:48:32 +0000196 return -1;
197 }
198
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000199 val = PyInt_AS_LONG(io);
200 Py_DECREF(io);
Guido van Rossumbf8c0e31994-08-29 12:48:32 +0000201
202 return val;
Guido van Rossum85a5fbb1990-10-14 12:07:46 +0000203}
204
205/* Methods */
206
Guido van Rossum719f5fa1992-03-27 17:31:02 +0000207/* ARGSUSED */
Guido van Rossum90933611991-06-07 16:10:43 +0000208static int
Guido van Rossum3f5da241990-12-20 15:06:42 +0000209int_print(v, fp, flags)
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000210 PyIntObject *v;
Guido van Rossum85a5fbb1990-10-14 12:07:46 +0000211 FILE *fp;
Guido van Rossum719f5fa1992-03-27 17:31:02 +0000212 int flags; /* Not used but required by interface */
Guido van Rossum85a5fbb1990-10-14 12:07:46 +0000213{
214 fprintf(fp, "%ld", v->ob_ival);
Guido van Rossum90933611991-06-07 16:10:43 +0000215 return 0;
Guido van Rossum85a5fbb1990-10-14 12:07:46 +0000216}
217
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000218static PyObject *
Guido van Rossum3f5da241990-12-20 15:06:42 +0000219int_repr(v)
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000220 PyIntObject *v;
Guido van Rossum85a5fbb1990-10-14 12:07:46 +0000221{
222 char buf[20];
223 sprintf(buf, "%ld", v->ob_ival);
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000224 return PyString_FromString(buf);
Guido van Rossum85a5fbb1990-10-14 12:07:46 +0000225}
226
227static int
Guido van Rossum3f5da241990-12-20 15:06:42 +0000228int_compare(v, w)
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000229 PyIntObject *v, *w;
Guido van Rossum85a5fbb1990-10-14 12:07:46 +0000230{
231 register long i = v->ob_ival;
232 register long j = w->ob_ival;
233 return (i < j) ? -1 : (i > j) ? 1 : 0;
234}
235
Guido van Rossum9bfef441993-03-29 10:43:31 +0000236static long
237int_hash(v)
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000238 PyIntObject *v;
Guido van Rossum9bfef441993-03-29 10:43:31 +0000239{
Guido van Rossum541cdd81997-01-06 22:53:20 +0000240 /* XXX If this is changed, you also need to change the way
241 Python's long, float and complex types are hashed. */
Guido van Rossum9bfef441993-03-29 10:43:31 +0000242 long x = v -> ob_ival;
243 if (x == -1)
244 x = -2;
245 return x;
246}
247
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000248static PyObject *
Guido van Rossum3f5da241990-12-20 15:06:42 +0000249int_add(v, w)
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000250 PyIntObject *v;
251 PyIntObject *w;
Guido van Rossum85a5fbb1990-10-14 12:07:46 +0000252{
253 register long a, b, x;
Guido van Rossum85a5fbb1990-10-14 12:07:46 +0000254 a = v->ob_ival;
Guido van Rossum2b16a6f1992-01-19 16:28:51 +0000255 b = w->ob_ival;
Guido van Rossum85a5fbb1990-10-14 12:07:46 +0000256 x = a + b;
Guido van Rossum165e67e1990-10-14 20:02:26 +0000257 if ((x^a) < 0 && (x^b) < 0)
Guido van Rossum3a628451991-12-10 13:57:36 +0000258 return err_ovf("integer addition");
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000259 return PyInt_FromLong(x);
Guido van Rossum85a5fbb1990-10-14 12:07:46 +0000260}
261
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000262static PyObject *
Guido van Rossum3f5da241990-12-20 15:06:42 +0000263int_sub(v, w)
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000264 PyIntObject *v;
265 PyIntObject *w;
Guido van Rossum85a5fbb1990-10-14 12:07:46 +0000266{
267 register long a, b, x;
Guido van Rossum85a5fbb1990-10-14 12:07:46 +0000268 a = v->ob_ival;
Guido van Rossum2b16a6f1992-01-19 16:28:51 +0000269 b = w->ob_ival;
Guido van Rossum85a5fbb1990-10-14 12:07:46 +0000270 x = a - b;
Guido van Rossum165e67e1990-10-14 20:02:26 +0000271 if ((x^a) < 0 && (x^~b) < 0)
Guido van Rossum3a628451991-12-10 13:57:36 +0000272 return err_ovf("integer subtraction");
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000273 return PyInt_FromLong(x);
Guido van Rossum85a5fbb1990-10-14 12:07:46 +0000274}
275
Guido van Rossumbf8c0e31994-08-29 12:48:32 +0000276/*
277Integer overflow checking used to be done using a double, but on 64
278bit machines (where both long and double are 64 bit) this fails
279because the double doesn't have enouvg precision. John Tromp suggests
280the following algorithm:
281
282Suppose again we normalize a and b to be nonnegative.
283Let ah and al (bh and bl) be the high and low 32 bits of a (b, resp.).
284Now we test ah and bh against zero and get essentially 3 possible outcomes.
285
2861) both ah and bh > 0 : then report overflow
287
2882) both ah and bh = 0 : then compute a*b and report overflow if it comes out
289 negative
290
2913) ah > 0 and bh = 0 : compute ah*bl and report overflow if it's >= 2^31
292 compute al*bl and report overflow if it's negative
293 add (ah*bl)<<32 to al*bl and report overflow if
294 it's negative
295
296In case of no overflow the result is then negated if necessary.
297
298The majority of cases will be 2), in which case this method is the same as
299what I suggested before. If multiplication is expensive enough, then the
300other method is faster on case 3), but also more work to program, so I
301guess the above is the preferred solution.
302
303*/
304
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000305static PyObject *
Guido van Rossum3f5da241990-12-20 15:06:42 +0000306int_mul(v, w)
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000307 PyIntObject *v;
308 PyIntObject *w;
Guido van Rossum85a5fbb1990-10-14 12:07:46 +0000309{
Guido van Rossumbf8c0e31994-08-29 12:48:32 +0000310 long a, b, ah, bh, x, y;
311 int s = 1;
312
Guido van Rossum85a5fbb1990-10-14 12:07:46 +0000313 a = v->ob_ival;
Guido van Rossum2b16a6f1992-01-19 16:28:51 +0000314 b = w->ob_ival;
Guido van Rossumbf8c0e31994-08-29 12:48:32 +0000315 ah = a >> (LONG_BIT/2);
316 bh = b >> (LONG_BIT/2);
317
318 /* Quick test for common case: two small positive ints */
319
320 if (ah == 0 && bh == 0) {
321 x = a*b;
322 if (x < 0)
323 goto bad;
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000324 return PyInt_FromLong(x);
Guido van Rossumbf8c0e31994-08-29 12:48:32 +0000325 }
326
327 /* Arrange that a >= b >= 0 */
328
329 if (a < 0) {
330 a = -a;
331 if (a < 0) {
332 /* Largest negative */
333 if (b == 0 || b == 1) {
334 x = a*b;
335 goto ok;
336 }
337 else
338 goto bad;
339 }
340 s = -s;
341 ah = a >> (LONG_BIT/2);
342 }
343 if (b < 0) {
344 b = -b;
345 if (b < 0) {
346 /* Largest negative */
Guido van Rossum9478dd41996-12-06 20:14:43 +0000347 if (a == 0 || (a == 1 && s == 1)) {
Guido van Rossumbf8c0e31994-08-29 12:48:32 +0000348 x = a*b;
349 goto ok;
350 }
351 else
352 goto bad;
353 }
354 s = -s;
355 bh = b >> (LONG_BIT/2);
356 }
357
358 /* 1) both ah and bh > 0 : then report overflow */
359
360 if (ah != 0 && bh != 0)
361 goto bad;
362
363 /* 2) both ah and bh = 0 : then compute a*b and report
364 overflow if it comes out negative */
365
366 if (ah == 0 && bh == 0) {
367 x = a*b;
368 if (x < 0)
369 goto bad;
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000370 return PyInt_FromLong(x*s);
Guido van Rossumbf8c0e31994-08-29 12:48:32 +0000371 }
372
373 if (a < b) {
374 /* Swap */
375 x = a;
376 a = b;
377 b = x;
378 ah = bh;
379 /* bh not used beyond this point */
380 }
381
382 /* 3) ah > 0 and bh = 0 : compute ah*bl and report overflow if
383 it's >= 2^31
384 compute al*bl and report overflow if it's negative
385 add (ah*bl)<<32 to al*bl and report overflow if
386 it's negative
387 (NB b == bl in this case, and we make a = al) */
388
389 y = ah*b;
Guido van Rossum541cdd81997-01-06 22:53:20 +0000390 if (y >= (1L << (LONG_BIT/2 - 1)))
Guido van Rossumbf8c0e31994-08-29 12:48:32 +0000391 goto bad;
392 a &= (1L << (LONG_BIT/2)) - 1;
393 x = a*b;
394 if (x < 0)
395 goto bad;
Guido van Rossum541cdd81997-01-06 22:53:20 +0000396 x += y << (LONG_BIT/2);
Guido van Rossumbf8c0e31994-08-29 12:48:32 +0000397 if (x < 0)
398 goto bad;
399 ok:
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000400 return PyInt_FromLong(x * s);
Guido van Rossumbf8c0e31994-08-29 12:48:32 +0000401
402 bad:
403 return err_ovf("integer multiplication");
Guido van Rossum85a5fbb1990-10-14 12:07:46 +0000404}
405
Guido van Rossum2b16a6f1992-01-19 16:28:51 +0000406static int
407i_divmod(x, y, p_xdivy, p_xmody)
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000408 register PyIntObject *x, *y;
Guido van Rossum2b16a6f1992-01-19 16:28:51 +0000409 long *p_xdivy, *p_xmody;
Guido van Rossum85a5fbb1990-10-14 12:07:46 +0000410{
Guido van Rossum2b16a6f1992-01-19 16:28:51 +0000411 long xi = x->ob_ival;
412 long yi = y->ob_ival;
413 long xdivy, xmody;
414
415 if (yi == 0) {
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000416 PyErr_SetString(PyExc_ZeroDivisionError,
417 "integer division or modulo");
Guido van Rossum2b16a6f1992-01-19 16:28:51 +0000418 return -1;
Guido van Rossum85a5fbb1990-10-14 12:07:46 +0000419 }
Guido van Rossum00466951991-05-05 20:08:27 +0000420 if (yi < 0) {
Guido van Rossum2b16a6f1992-01-19 16:28:51 +0000421 if (xi < 0)
422 xdivy = -xi / -yi;
423 else
424 xdivy = - (xi / -yi);
Guido van Rossum00466951991-05-05 20:08:27 +0000425 }
426 else {
Guido van Rossum2b16a6f1992-01-19 16:28:51 +0000427 if (xi < 0)
428 xdivy = - (-xi / yi);
429 else
430 xdivy = xi / yi;
Guido van Rossum00466951991-05-05 20:08:27 +0000431 }
432 xmody = xi - xdivy*yi;
Guido van Rossum9478dd41996-12-06 20:14:43 +0000433 if ((xmody < 0 && yi > 0) || (xmody > 0 && yi < 0)) {
Guido van Rossum00466951991-05-05 20:08:27 +0000434 xmody += yi;
435 xdivy -= 1;
436 }
Guido van Rossum2b16a6f1992-01-19 16:28:51 +0000437 *p_xdivy = xdivy;
438 *p_xmody = xmody;
439 return 0;
440}
441
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000442static PyObject *
Guido van Rossum2b16a6f1992-01-19 16:28:51 +0000443int_div(x, y)
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000444 PyIntObject *x;
445 PyIntObject *y;
Guido van Rossum2b16a6f1992-01-19 16:28:51 +0000446{
447 long d, m;
448 if (i_divmod(x, y, &d, &m) < 0)
449 return NULL;
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000450 return PyInt_FromLong(d);
Guido van Rossum2b16a6f1992-01-19 16:28:51 +0000451}
452
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000453static PyObject *
Guido van Rossum2b16a6f1992-01-19 16:28:51 +0000454int_mod(x, y)
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000455 PyIntObject *x;
456 PyIntObject *y;
Guido van Rossum2b16a6f1992-01-19 16:28:51 +0000457{
458 long d, m;
459 if (i_divmod(x, y, &d, &m) < 0)
460 return NULL;
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000461 return PyInt_FromLong(m);
Guido van Rossum2b16a6f1992-01-19 16:28:51 +0000462}
463
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000464static PyObject *
Guido van Rossum2b16a6f1992-01-19 16:28:51 +0000465int_divmod(x, y)
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000466 PyIntObject *x;
467 PyIntObject *y;
Guido van Rossum2b16a6f1992-01-19 16:28:51 +0000468{
Guido van Rossum2b16a6f1992-01-19 16:28:51 +0000469 long d, m;
470 if (i_divmod(x, y, &d, &m) < 0)
471 return NULL;
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000472 return Py_BuildValue("(ll)", d, m);
Guido van Rossum00466951991-05-05 20:08:27 +0000473}
474
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000475static PyObject *
Guido van Rossumbf8c0e31994-08-29 12:48:32 +0000476int_pow(v, w, z)
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000477 PyIntObject *v;
478 PyIntObject *w;
479 PyIntObject *z;
Guido van Rossum85a5fbb1990-10-14 12:07:46 +0000480{
Guido van Rossumbf8c0e31994-08-29 12:48:32 +0000481#if 1
Guido van Rossum9478dd41996-12-06 20:14:43 +0000482 register long iv, iw, iz=0, ix, temp, prev;
Guido van Rossumbf8c0e31994-08-29 12:48:32 +0000483 iv = v->ob_ival;
484 iw = w->ob_ival;
485 if (iw < 0) {
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000486 PyErr_SetString(PyExc_ValueError,
487 "integer to the negative power");
Guido van Rossumbf8c0e31994-08-29 12:48:32 +0000488 return NULL;
489 }
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000490 if ((PyObject *)z != Py_None) {
Guido van Rossumbf8c0e31994-08-29 12:48:32 +0000491 iz = z->ob_ival;
Guido van Rossum9478dd41996-12-06 20:14:43 +0000492 if (iz == 0) {
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000493 PyErr_SetString(PyExc_ValueError,
494 "pow(x, y, z) with z==0");
Guido van Rossum9478dd41996-12-06 20:14:43 +0000495 return NULL;
496 }
Guido van Rossumbf8c0e31994-08-29 12:48:32 +0000497 }
498 /*
499 * XXX: The original exponentiation code stopped looping
500 * when temp hit zero; this code will continue onwards
501 * unnecessarily, but at least it won't cause any errors.
502 * Hopefully the speed improvement from the fast exponentiation
503 * will compensate for the slight inefficiency.
504 * XXX: Better handling of overflows is desperately needed.
505 */
506 temp = iv;
507 ix = 1;
508 while (iw > 0) {
509 prev = ix; /* Save value for overflow check */
510 if (iw & 1) {
511 ix = ix*temp;
512 if (temp == 0)
513 break; /* Avoid ix / 0 */
514 if (ix / temp != prev)
515 return err_ovf("integer pow()");
516 }
517 iw >>= 1; /* Shift exponent down by 1 bit */
518 if (iw==0) break;
519 prev = temp;
520 temp *= temp; /* Square the value of temp */
521 if (prev!=0 && temp/prev!=prev)
522 return err_ovf("integer pow()");
Guido van Rossum9478dd41996-12-06 20:14:43 +0000523 if (iz) {
Guido van Rossumbf8c0e31994-08-29 12:48:32 +0000524 /* If we did a multiplication, perform a modulo */
525 ix = ix % iz;
526 temp = temp % iz;
527 }
528 }
Guido van Rossum9478dd41996-12-06 20:14:43 +0000529 if (iz) {
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000530 PyObject *t1, *t2;
Guido van Rossumbf8c0e31994-08-29 12:48:32 +0000531 long int div, mod;
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000532 t1=PyInt_FromLong(ix);
533 t2=PyInt_FromLong(iz);
Guido van Rossumbf8c0e31994-08-29 12:48:32 +0000534 if (t1==NULL || t2==NULL ||
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000535 i_divmod((PyIntObject *)t1,
536 (PyIntObject *)t2, &div, &mod)<0)
537 {
538 Py_XDECREF(t1);
539 Py_XDECREF(t2);
Guido van Rossumbf8c0e31994-08-29 12:48:32 +0000540 return(NULL);
541 }
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000542 Py_DECREF(t1);
543 Py_DECREF(t2);
Guido van Rossumbf8c0e31994-08-29 12:48:32 +0000544 ix=mod;
545 }
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000546 return PyInt_FromLong(ix);
Guido van Rossumbf8c0e31994-08-29 12:48:32 +0000547#else
Guido van Rossum85a5fbb1990-10-14 12:07:46 +0000548 register long iv, iw, ix;
Guido van Rossum85a5fbb1990-10-14 12:07:46 +0000549 iv = v->ob_ival;
Guido van Rossum2b16a6f1992-01-19 16:28:51 +0000550 iw = w->ob_ival;
Guido van Rossum00466951991-05-05 20:08:27 +0000551 if (iw < 0) {
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000552 PyErr_SetString(PyExc_ValueError,
553 "integer to the negative power");
Guido van Rossum00466951991-05-05 20:08:27 +0000554 return NULL;
Guido van Rossum85a5fbb1990-10-14 12:07:46 +0000555 }
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000556 if ((PyObject *)z != Py_None) {
557 PyErr_SetString(PyExc_TypeError,
558 "pow(int, int, int) not yet supported");
Guido van Rossumbf8c0e31994-08-29 12:48:32 +0000559 return NULL;
560 }
Guido van Rossum00466951991-05-05 20:08:27 +0000561 ix = 1;
562 while (--iw >= 0) {
563 long prev = ix;
564 ix = ix * iv;
565 if (iv == 0)
566 break; /* 0 to some power -- avoid ix / 0 */
567 if (ix / iv != prev)
Guido van Rossum3a628451991-12-10 13:57:36 +0000568 return err_ovf("integer pow()");
Guido van Rossum00466951991-05-05 20:08:27 +0000569 }
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000570 return PyInt_FromLong(ix);
Guido van Rossumbf8c0e31994-08-29 12:48:32 +0000571#endif
572}
Guido van Rossum85a5fbb1990-10-14 12:07:46 +0000573
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000574static PyObject *
Guido van Rossum3f5da241990-12-20 15:06:42 +0000575int_neg(v)
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000576 PyIntObject *v;
Guido van Rossum85a5fbb1990-10-14 12:07:46 +0000577{
578 register long a, x;
579 a = v->ob_ival;
580 x = -a;
Guido van Rossum165e67e1990-10-14 20:02:26 +0000581 if (a < 0 && x < 0)
Guido van Rossum3a628451991-12-10 13:57:36 +0000582 return err_ovf("integer negation");
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000583 return PyInt_FromLong(x);
Guido van Rossum85a5fbb1990-10-14 12:07:46 +0000584}
585
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000586static PyObject *
Guido van Rossum3f5da241990-12-20 15:06:42 +0000587int_pos(v)
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000588 PyIntObject *v;
Guido van Rossum85a5fbb1990-10-14 12:07:46 +0000589{
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000590 Py_INCREF(v);
591 return (PyObject *)v;
Guido van Rossum85a5fbb1990-10-14 12:07:46 +0000592}
593
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000594static PyObject *
Guido van Rossum00466951991-05-05 20:08:27 +0000595int_abs(v)
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000596 PyIntObject *v;
Guido van Rossum00466951991-05-05 20:08:27 +0000597{
598 if (v->ob_ival >= 0)
599 return int_pos(v);
600 else
601 return int_neg(v);
602}
603
Guido van Rossum0bff0151991-05-14 12:05:32 +0000604static int
605int_nonzero(v)
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000606 PyIntObject *v;
Guido van Rossum0bff0151991-05-14 12:05:32 +0000607{
608 return v->ob_ival != 0;
609}
610
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000611static PyObject *
Guido van Rossum7928cd71991-10-24 14:59:31 +0000612int_invert(v)
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000613 PyIntObject *v;
Guido van Rossum7928cd71991-10-24 14:59:31 +0000614{
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000615 return PyInt_FromLong(~v->ob_ival);
Guido van Rossum7928cd71991-10-24 14:59:31 +0000616}
617
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000618static PyObject *
Guido van Rossum7928cd71991-10-24 14:59:31 +0000619int_lshift(v, w)
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000620 PyIntObject *v;
621 PyIntObject *w;
Guido van Rossum7928cd71991-10-24 14:59:31 +0000622{
623 register long a, b;
Guido van Rossum7928cd71991-10-24 14:59:31 +0000624 a = v->ob_ival;
Guido van Rossum2b16a6f1992-01-19 16:28:51 +0000625 b = w->ob_ival;
Guido van Rossumf3b351f1992-01-14 18:33:22 +0000626 if (b < 0) {
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000627 PyErr_SetString(PyExc_ValueError, "negative shift count");
Guido van Rossumf3b351f1992-01-14 18:33:22 +0000628 return NULL;
629 }
630 if (a == 0 || b == 0) {
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000631 Py_INCREF(v);
632 return (PyObject *) v;
Guido van Rossumf3b351f1992-01-14 18:33:22 +0000633 }
Guido van Rossum72481a31993-10-26 15:21:51 +0000634 if (b >= LONG_BIT) {
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000635 return PyInt_FromLong(0L);
Guido van Rossumf3b351f1992-01-14 18:33:22 +0000636 }
637 a = (unsigned long)a << b;
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000638 return PyInt_FromLong(a);
Guido van Rossum7928cd71991-10-24 14:59:31 +0000639}
640
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000641static PyObject *
Guido van Rossum7928cd71991-10-24 14:59:31 +0000642int_rshift(v, w)
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000643 PyIntObject *v;
644 PyIntObject *w;
Guido van Rossum7928cd71991-10-24 14:59:31 +0000645{
646 register long a, b;
Guido van Rossum7928cd71991-10-24 14:59:31 +0000647 a = v->ob_ival;
Guido van Rossum2b16a6f1992-01-19 16:28:51 +0000648 b = w->ob_ival;
Guido van Rossumf3b351f1992-01-14 18:33:22 +0000649 if (b < 0) {
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000650 PyErr_SetString(PyExc_ValueError, "negative shift count");
Guido van Rossumf3b351f1992-01-14 18:33:22 +0000651 return NULL;
652 }
653 if (a == 0 || b == 0) {
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000654 Py_INCREF(v);
655 return (PyObject *) v;
Guido van Rossumf3b351f1992-01-14 18:33:22 +0000656 }
Guido van Rossum72481a31993-10-26 15:21:51 +0000657 if (b >= LONG_BIT) {
Guido van Rossumf3b351f1992-01-14 18:33:22 +0000658 if (a < 0)
659 a = -1;
660 else
661 a = 0;
662 }
663 else {
664 if (a < 0)
665 a = ~( ~(unsigned long)a >> b );
666 else
667 a = (unsigned long)a >> b;
668 }
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000669 return PyInt_FromLong(a);
Guido van Rossum7928cd71991-10-24 14:59:31 +0000670}
671
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000672static PyObject *
Guido van Rossum7928cd71991-10-24 14:59:31 +0000673int_and(v, w)
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000674 PyIntObject *v;
675 PyIntObject *w;
Guido van Rossum7928cd71991-10-24 14:59:31 +0000676{
677 register long a, b;
Guido van Rossum7928cd71991-10-24 14:59:31 +0000678 a = v->ob_ival;
Guido van Rossum2b16a6f1992-01-19 16:28:51 +0000679 b = w->ob_ival;
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000680 return PyInt_FromLong(a & b);
Guido van Rossum7928cd71991-10-24 14:59:31 +0000681}
682
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000683static PyObject *
Guido van Rossum7928cd71991-10-24 14:59:31 +0000684int_xor(v, w)
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000685 PyIntObject *v;
686 PyIntObject *w;
Guido van Rossum7928cd71991-10-24 14:59:31 +0000687{
688 register long a, b;
Guido van Rossum7928cd71991-10-24 14:59:31 +0000689 a = v->ob_ival;
Guido van Rossum2b16a6f1992-01-19 16:28:51 +0000690 b = w->ob_ival;
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000691 return PyInt_FromLong(a ^ b);
Guido van Rossum7928cd71991-10-24 14:59:31 +0000692}
693
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000694static PyObject *
Guido van Rossum7928cd71991-10-24 14:59:31 +0000695int_or(v, w)
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000696 PyIntObject *v;
697 PyIntObject *w;
Guido van Rossum7928cd71991-10-24 14:59:31 +0000698{
699 register long a, b;
Guido van Rossum7928cd71991-10-24 14:59:31 +0000700 a = v->ob_ival;
Guido van Rossum2b16a6f1992-01-19 16:28:51 +0000701 b = w->ob_ival;
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000702 return PyInt_FromLong(a | b);
Guido van Rossum7928cd71991-10-24 14:59:31 +0000703}
704
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000705static PyObject *
Guido van Rossum1899c2e1992-09-12 11:09:23 +0000706int_int(v)
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000707 PyIntObject *v;
Guido van Rossum1899c2e1992-09-12 11:09:23 +0000708{
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000709 Py_INCREF(v);
710 return (PyObject *)v;
Guido van Rossum1899c2e1992-09-12 11:09:23 +0000711}
712
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000713static PyObject *
Guido van Rossum1899c2e1992-09-12 11:09:23 +0000714int_long(v)
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000715 PyIntObject *v;
Guido van Rossum1899c2e1992-09-12 11:09:23 +0000716{
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000717 return PyLong_FromLong((v -> ob_ival));
Guido van Rossum1899c2e1992-09-12 11:09:23 +0000718}
719
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000720static PyObject *
Guido van Rossum1899c2e1992-09-12 11:09:23 +0000721int_float(v)
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000722 PyIntObject *v;
Guido van Rossum1899c2e1992-09-12 11:09:23 +0000723{
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000724 return PyFloat_FromDouble((double)(v -> ob_ival));
Guido van Rossum1899c2e1992-09-12 11:09:23 +0000725}
726
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000727static PyObject *
Guido van Rossum1899c2e1992-09-12 11:09:23 +0000728int_oct(v)
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000729 PyIntObject *v;
Guido van Rossum1899c2e1992-09-12 11:09:23 +0000730{
Guido van Rossum6f72f971997-01-14 15:43:41 +0000731 char buf[100];
Guido van Rossum9bfef441993-03-29 10:43:31 +0000732 long x = v -> ob_ival;
Guido van Rossum1899c2e1992-09-12 11:09:23 +0000733 if (x == 0)
734 strcpy(buf, "0");
Guido van Rossum1899c2e1992-09-12 11:09:23 +0000735 else
Guido van Rossumebee0251997-01-12 19:48:03 +0000736 sprintf(buf, "0%lo", x);
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000737 return PyString_FromString(buf);
Guido van Rossum1899c2e1992-09-12 11:09:23 +0000738}
739
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000740static PyObject *
Guido van Rossum1899c2e1992-09-12 11:09:23 +0000741int_hex(v)
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000742 PyIntObject *v;
Guido van Rossum1899c2e1992-09-12 11:09:23 +0000743{
Guido van Rossum6f72f971997-01-14 15:43:41 +0000744 char buf[100];
Guido van Rossum9bfef441993-03-29 10:43:31 +0000745 long x = v -> ob_ival;
Guido van Rossumebee0251997-01-12 19:48:03 +0000746 sprintf(buf, "0x%lx", x);
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000747 return PyString_FromString(buf);
Guido van Rossum1899c2e1992-09-12 11:09:23 +0000748}
749
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000750static PyNumberMethods int_as_number = {
Guido van Rossumbf8c0e31994-08-29 12:48:32 +0000751 (binaryfunc)int_add, /*nb_add*/
752 (binaryfunc)int_sub, /*nb_subtract*/
753 (binaryfunc)int_mul, /*nb_multiply*/
754 (binaryfunc)int_div, /*nb_divide*/
755 (binaryfunc)int_mod, /*nb_remainder*/
756 (binaryfunc)int_divmod, /*nb_divmod*/
757 (ternaryfunc)int_pow, /*nb_power*/
758 (unaryfunc)int_neg, /*nb_negative*/
759 (unaryfunc)int_pos, /*nb_positive*/
760 (unaryfunc)int_abs, /*nb_absolute*/
761 (inquiry)int_nonzero, /*nb_nonzero*/
762 (unaryfunc)int_invert, /*nb_invert*/
763 (binaryfunc)int_lshift, /*nb_lshift*/
764 (binaryfunc)int_rshift, /*nb_rshift*/
765 (binaryfunc)int_and, /*nb_and*/
766 (binaryfunc)int_xor, /*nb_xor*/
767 (binaryfunc)int_or, /*nb_or*/
Guido van Rossum1899c2e1992-09-12 11:09:23 +0000768 0, /*nb_coerce*/
Guido van Rossumbf8c0e31994-08-29 12:48:32 +0000769 (unaryfunc)int_int, /*nb_int*/
770 (unaryfunc)int_long, /*nb_long*/
771 (unaryfunc)int_float, /*nb_float*/
772 (unaryfunc)int_oct, /*nb_oct*/
773 (unaryfunc)int_hex, /*nb_hex*/
Guido van Rossum85a5fbb1990-10-14 12:07:46 +0000774};
775
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000776PyTypeObject PyInt_Type = {
777 PyObject_HEAD_INIT(&PyType_Type)
Guido van Rossum85a5fbb1990-10-14 12:07:46 +0000778 0,
779 "int",
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000780 sizeof(PyIntObject),
Guido van Rossum85a5fbb1990-10-14 12:07:46 +0000781 0,
Guido van Rossumbf8c0e31994-08-29 12:48:32 +0000782 (destructor)int_dealloc, /*tp_dealloc*/
783 (printfunc)int_print, /*tp_print*/
Guido van Rossum85a5fbb1990-10-14 12:07:46 +0000784 0, /*tp_getattr*/
785 0, /*tp_setattr*/
Guido van Rossumbf8c0e31994-08-29 12:48:32 +0000786 (cmpfunc)int_compare, /*tp_compare*/
787 (reprfunc)int_repr, /*tp_repr*/
Guido van Rossum85a5fbb1990-10-14 12:07:46 +0000788 &int_as_number, /*tp_as_number*/
789 0, /*tp_as_sequence*/
790 0, /*tp_as_mapping*/
Guido van Rossumbf8c0e31994-08-29 12:48:32 +0000791 (hashfunc)int_hash, /*tp_hash*/
Guido van Rossum85a5fbb1990-10-14 12:07:46 +0000792};