blob: 40aaba1e181e71dc3e3067bd435c5f33d454b7ce [file] [log] [blame]
Guido van Rossumedcc38a1991-05-05 20:09:44 +00001/* Long (arbitrary precision) integer object implementation */
2
Guido van Rossum23d6f0e1991-05-14 12:06:49 +00003/* XXX The functional organization of this file is terrible */
4
Guido van Rossumc0b618a1997-05-02 03:12:38 +00005#include "Python.h"
Guido van Rossumedcc38a1991-05-05 20:09:44 +00006#include "longintrepr.h"
Guido van Rossumc0b618a1997-05-02 03:12:38 +00007
Eric Smith8c663262007-08-25 02:26:07 +00008#include "formatter_unicode.h"
9
Guido van Rossumeb1fafc1994-08-29 12:47:19 +000010#include <ctype.h>
Guido van Rossumedcc38a1991-05-05 20:09:44 +000011
Guido van Rossumddefaf32007-01-14 03:31:43 +000012#ifndef NSMALLPOSINTS
13#define NSMALLPOSINTS 257
14#endif
15#ifndef NSMALLNEGINTS
16#define NSMALLNEGINTS 5
17#endif
18#if NSMALLNEGINTS + NSMALLPOSINTS > 0
19/* Small integers are preallocated in this array so that they
20 can be shared.
21 The integers that are preallocated are those in the range
22 -NSMALLNEGINTS (inclusive) to NSMALLPOSINTS (not inclusive).
23*/
24static PyLongObject small_ints[NSMALLNEGINTS + NSMALLPOSINTS];
25#ifdef COUNT_ALLOCS
26int quick_int_allocs, quick_neg_int_allocs;
27#endif
28
Guido van Rossum7eaf8222007-06-18 17:58:50 +000029static PyObject *
Guido van Rossumddefaf32007-01-14 03:31:43 +000030get_small_int(int ival)
31{
32 PyObject *v = (PyObject*)(small_ints + ival + NSMALLNEGINTS);
33 Py_INCREF(v);
34#ifdef COUNT_ALLOCS
35 if (ival >= 0)
36 quick_int_allocs++;
37 else
38 quick_neg_int_allocs++;
39#endif
40 return v;
41}
42#define CHECK_SMALL_INT(ival) \
43 do if (-NSMALLNEGINTS <= ival && ival < NSMALLPOSINTS) { \
44 return get_small_int(ival); \
45 } while(0)
46
47#else
48#define CHECK_SMALL_INT(ival)
49#endif
50
Christian Heimes90aa7642007-12-19 02:45:37 +000051#define MEDIUM_VALUE(x) (Py_SIZE(x) < 0 ? -(x)->ob_digit[0] : (Py_SIZE(x) == 0 ? 0 : (x)->ob_digit[0]))
Guido van Rossumddefaf32007-01-14 03:31:43 +000052/* If a freshly-allocated long is already shared, it must
53 be a small integer, so negating it must go to PyLong_FromLong */
54#define NEGATE(x) \
Christian Heimes90aa7642007-12-19 02:45:37 +000055 do if (Py_REFCNT(x) == 1) Py_SIZE(x) = -Py_SIZE(x); \
Christian Heimes217cfd12007-12-02 14:31:20 +000056 else { PyObject* tmp=PyLong_FromLong(-MEDIUM_VALUE(x)); \
Guido van Rossumddefaf32007-01-14 03:31:43 +000057 Py_DECREF(x); (x) = (PyLongObject*)tmp; } \
58 while(0)
Tim Peters5af4e6c2002-08-12 02:31:19 +000059/* For long multiplication, use the O(N**2) school algorithm unless
60 * both operands contain more than KARATSUBA_CUTOFF digits (this
61 * being an internal Python long digit, in base BASE).
62 */
Tim Peters0973b992004-08-29 22:16:50 +000063#define KARATSUBA_CUTOFF 70
64#define KARATSUBA_SQUARE_CUTOFF (2 * KARATSUBA_CUTOFF)
Tim Peters5af4e6c2002-08-12 02:31:19 +000065
Tim Peters47e52ee2004-08-30 02:44:38 +000066/* For exponentiation, use the binary left-to-right algorithm
67 * unless the exponent contains more than FIVEARY_CUTOFF digits.
68 * In that case, do 5 bits at a time. The potential drawback is that
69 * a table of 2**5 intermediate results is computed.
70 */
71#define FIVEARY_CUTOFF 8
72
Guido van Rossume32e0141992-01-19 16:31:05 +000073#define ABS(x) ((x) < 0 ? -(x) : (x))
74
Tim Peters5af4e6c2002-08-12 02:31:19 +000075#undef MIN
76#undef MAX
77#define MAX(x, y) ((x) < (y) ? (y) : (x))
78#define MIN(x, y) ((x) > (y) ? (y) : (x))
79
Guido van Rossume32e0141992-01-19 16:31:05 +000080/* Forward */
Tim Peters9f688bf2000-07-07 15:53:28 +000081static PyLongObject *long_normalize(PyLongObject *);
82static PyLongObject *mul1(PyLongObject *, wdigit);
83static PyLongObject *muladd1(PyLongObject *, wdigit, wdigit);
Tim Peters212e6142001-07-14 12:23:19 +000084static PyLongObject *divrem1(PyLongObject *, digit, digit *);
Guido van Rossume32e0141992-01-19 16:31:05 +000085
Guido van Rossumc0b618a1997-05-02 03:12:38 +000086#define SIGCHECK(PyTryBlock) \
Skip Montanarod581d772002-09-03 20:10:45 +000087 if (--_Py_Ticker < 0) { \
88 _Py_Ticker = _Py_CheckInterval; \
Thomas Wouters477c8d52006-05-27 19:21:47 +000089 if (PyErr_CheckSignals()) PyTryBlock \
Guido van Rossum23d6f0e1991-05-14 12:06:49 +000090 }
91
Guido van Rossumedcc38a1991-05-05 20:09:44 +000092/* Normalize (remove leading zeros from) a long int object.
93 Doesn't attempt to free the storage--in most cases, due to the nature
94 of the algorithms used, this could save at most be one word anyway. */
95
Guido van Rossumc0b618a1997-05-02 03:12:38 +000096static PyLongObject *
Tim Peters9f688bf2000-07-07 15:53:28 +000097long_normalize(register PyLongObject *v)
Guido van Rossumedcc38a1991-05-05 20:09:44 +000098{
Christian Heimes90aa7642007-12-19 02:45:37 +000099 Py_ssize_t j = ABS(Py_SIZE(v));
Martin v. Löwis18e16552006-02-15 17:27:45 +0000100 Py_ssize_t i = j;
Tim Peters5af4e6c2002-08-12 02:31:19 +0000101
Guido van Rossumedcc38a1991-05-05 20:09:44 +0000102 while (i > 0 && v->ob_digit[i-1] == 0)
103 --i;
104 if (i != j)
Christian Heimes90aa7642007-12-19 02:45:37 +0000105 Py_SIZE(v) = (Py_SIZE(v) < 0) ? -(i) : i;
Guido van Rossumedcc38a1991-05-05 20:09:44 +0000106 return v;
107}
108
109/* Allocate a new long int object with size digits.
110 Return NULL and set exception if we run out of memory. */
111
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000112PyLongObject *
Martin v. Löwis18e16552006-02-15 17:27:45 +0000113_PyLong_New(Py_ssize_t size)
Guido van Rossumedcc38a1991-05-05 20:09:44 +0000114{
Guido van Rossumddefaf32007-01-14 03:31:43 +0000115 PyLongObject *result;
116 /* Can't use sizeof(PyLongObject) here, since the
117 compiler takes padding at the end into account.
118 As the consequence, this would waste 2 bytes on
119 a 32-bit system, and 6 bytes on a 64-bit system.
120 This computation would be incorrect on systems
121 which have padding before the digits; with 16-bit
122 digits this should not happen. */
123 result = PyObject_MALLOC(sizeof(PyVarObject) +
124 size*sizeof(digit));
125 if (!result) {
Martin v. Löwis18e16552006-02-15 17:27:45 +0000126 PyErr_NoMemory();
127 return NULL;
128 }
Guido van Rossumddefaf32007-01-14 03:31:43 +0000129 return (PyLongObject*)PyObject_INIT_VAR(result, &PyLong_Type, size);
Guido van Rossumedcc38a1991-05-05 20:09:44 +0000130}
131
Tim Peters64b5ce32001-09-10 20:52:51 +0000132PyObject *
133_PyLong_Copy(PyLongObject *src)
134{
135 PyLongObject *result;
Martin v. Löwis18e16552006-02-15 17:27:45 +0000136 Py_ssize_t i;
Tim Peters64b5ce32001-09-10 20:52:51 +0000137
138 assert(src != NULL);
Christian Heimes90aa7642007-12-19 02:45:37 +0000139 i = Py_SIZE(src);
Tim Peters64b5ce32001-09-10 20:52:51 +0000140 if (i < 0)
141 i = -(i);
Guido van Rossumddefaf32007-01-14 03:31:43 +0000142 if (i < 2) {
143 int ival = src->ob_digit[0];
Christian Heimes90aa7642007-12-19 02:45:37 +0000144 if (Py_SIZE(src) < 0)
Guido van Rossumddefaf32007-01-14 03:31:43 +0000145 ival = -ival;
146 CHECK_SMALL_INT(ival);
147 }
Tim Peters64b5ce32001-09-10 20:52:51 +0000148 result = _PyLong_New(i);
149 if (result != NULL) {
Christian Heimes90aa7642007-12-19 02:45:37 +0000150 Py_SIZE(result) = Py_SIZE(src);
Tim Peters64b5ce32001-09-10 20:52:51 +0000151 while (--i >= 0)
152 result->ob_digit[i] = src->ob_digit[i];
153 }
154 return (PyObject *)result;
155}
156
Guido van Rossumedcc38a1991-05-05 20:09:44 +0000157/* Create a new long int object from a C long int */
158
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000159PyObject *
Tim Peters9f688bf2000-07-07 15:53:28 +0000160PyLong_FromLong(long ival)
Guido van Rossumedcc38a1991-05-05 20:09:44 +0000161{
Tim Petersce9de2f2001-06-14 04:56:19 +0000162 PyLongObject *v;
163 unsigned long t; /* unsigned so >> doesn't propagate sign bit */
164 int ndigits = 0;
Guido van Rossumddefaf32007-01-14 03:31:43 +0000165 int sign = 1;
166
167 CHECK_SMALL_INT(ival);
Tim Petersce9de2f2001-06-14 04:56:19 +0000168
169 if (ival < 0) {
170 ival = -ival;
Guido van Rossumddefaf32007-01-14 03:31:43 +0000171 sign = -1;
Tim Petersce9de2f2001-06-14 04:56:19 +0000172 }
173
Guido van Rossumddefaf32007-01-14 03:31:43 +0000174 /* Fast path for single-digits ints */
Martin v. Löwis9f2e3462007-07-21 17:22:18 +0000175 if (!(ival>>PyLong_SHIFT)) {
Guido van Rossumddefaf32007-01-14 03:31:43 +0000176 v = _PyLong_New(1);
177 if (v) {
Christian Heimes90aa7642007-12-19 02:45:37 +0000178 Py_SIZE(v) = sign;
Guido van Rossumddefaf32007-01-14 03:31:43 +0000179 v->ob_digit[0] = ival;
180 }
181 return (PyObject*)v;
182 }
183
184 /* 2 digits */
Martin v. Löwis9f2e3462007-07-21 17:22:18 +0000185 if (!(ival >> 2*PyLong_SHIFT)) {
Guido van Rossumddefaf32007-01-14 03:31:43 +0000186 v = _PyLong_New(2);
187 if (v) {
Christian Heimes90aa7642007-12-19 02:45:37 +0000188 Py_SIZE(v) = 2*sign;
Martin v. Löwis9f2e3462007-07-21 17:22:18 +0000189 v->ob_digit[0] = (digit)ival & PyLong_MASK;
190 v->ob_digit[1] = ival >> PyLong_SHIFT;
Guido van Rossumddefaf32007-01-14 03:31:43 +0000191 }
192 return (PyObject*)v;
193 }
194
195 /* Larger numbers: loop to determine number of digits */
Tim Petersce9de2f2001-06-14 04:56:19 +0000196 t = (unsigned long)ival;
197 while (t) {
198 ++ndigits;
Martin v. Löwis9f2e3462007-07-21 17:22:18 +0000199 t >>= PyLong_SHIFT;
Tim Petersce9de2f2001-06-14 04:56:19 +0000200 }
201 v = _PyLong_New(ndigits);
Guido van Rossumedcc38a1991-05-05 20:09:44 +0000202 if (v != NULL) {
Tim Petersce9de2f2001-06-14 04:56:19 +0000203 digit *p = v->ob_digit;
Christian Heimes90aa7642007-12-19 02:45:37 +0000204 Py_SIZE(v) = ndigits*sign;
Tim Petersce9de2f2001-06-14 04:56:19 +0000205 t = (unsigned long)ival;
206 while (t) {
Martin v. Löwis9f2e3462007-07-21 17:22:18 +0000207 *p++ = (digit)(t & PyLong_MASK);
208 t >>= PyLong_SHIFT;
Guido van Rossumedcc38a1991-05-05 20:09:44 +0000209 }
Guido van Rossumedcc38a1991-05-05 20:09:44 +0000210 }
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000211 return (PyObject *)v;
Guido van Rossumedcc38a1991-05-05 20:09:44 +0000212}
213
Guido van Rossum53756b11997-01-03 17:14:46 +0000214/* Create a new long int object from a C unsigned long int */
215
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000216PyObject *
Tim Peters9f688bf2000-07-07 15:53:28 +0000217PyLong_FromUnsignedLong(unsigned long ival)
Guido van Rossum53756b11997-01-03 17:14:46 +0000218{
Tim Petersce9de2f2001-06-14 04:56:19 +0000219 PyLongObject *v;
220 unsigned long t;
221 int ndigits = 0;
222
Martin v. Löwis9f2e3462007-07-21 17:22:18 +0000223 if (ival < PyLong_BASE)
Guido van Rossumddefaf32007-01-14 03:31:43 +0000224 return PyLong_FromLong(ival);
Tim Petersce9de2f2001-06-14 04:56:19 +0000225 /* Count the number of Python digits. */
226 t = (unsigned long)ival;
227 while (t) {
228 ++ndigits;
Martin v. Löwis9f2e3462007-07-21 17:22:18 +0000229 t >>= PyLong_SHIFT;
Tim Petersce9de2f2001-06-14 04:56:19 +0000230 }
231 v = _PyLong_New(ndigits);
Guido van Rossum53756b11997-01-03 17:14:46 +0000232 if (v != NULL) {
Tim Petersce9de2f2001-06-14 04:56:19 +0000233 digit *p = v->ob_digit;
Christian Heimes90aa7642007-12-19 02:45:37 +0000234 Py_SIZE(v) = ndigits;
Tim Petersce9de2f2001-06-14 04:56:19 +0000235 while (ival) {
Martin v. Löwis9f2e3462007-07-21 17:22:18 +0000236 *p++ = (digit)(ival & PyLong_MASK);
237 ival >>= PyLong_SHIFT;
Guido van Rossum53756b11997-01-03 17:14:46 +0000238 }
Guido van Rossum53756b11997-01-03 17:14:46 +0000239 }
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000240 return (PyObject *)v;
Guido van Rossum53756b11997-01-03 17:14:46 +0000241}
242
Guido van Rossum149e9ea1991-06-03 10:58:24 +0000243/* Create a new long int object from a C double */
244
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000245PyObject *
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000246PyLong_FromDouble(double dval)
Guido van Rossum149e9ea1991-06-03 10:58:24 +0000247{
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000248 PyLongObject *v;
Guido van Rossum149e9ea1991-06-03 10:58:24 +0000249 double frac;
250 int i, ndig, expo, neg;
251 neg = 0;
Tim Peters39dce292000-08-15 03:34:48 +0000252 if (Py_IS_INFINITY(dval)) {
Guido van Rossum1a23c241999-09-27 17:11:52 +0000253 PyErr_SetString(PyExc_OverflowError,
Guido van Rossumddefaf32007-01-14 03:31:43 +0000254 "cannot convert float infinity to int");
Guido van Rossum1a23c241999-09-27 17:11:52 +0000255 return NULL;
256 }
Christian Heimesa34706f2008-01-04 03:06:10 +0000257 if (Py_IS_NAN(dval)) {
258 return PyLong_FromLong(0L);
259 }
Guido van Rossum149e9ea1991-06-03 10:58:24 +0000260 if (dval < 0.0) {
261 neg = 1;
262 dval = -dval;
263 }
264 frac = frexp(dval, &expo); /* dval = frac*2**expo; 0.0 <= frac < 1.0 */
265 if (expo <= 0)
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000266 return PyLong_FromLong(0L);
Martin v. Löwis9f2e3462007-07-21 17:22:18 +0000267 ndig = (expo-1) / PyLong_SHIFT + 1; /* Number of 'digits' in result */
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000268 v = _PyLong_New(ndig);
Guido van Rossum149e9ea1991-06-03 10:58:24 +0000269 if (v == NULL)
270 return NULL;
Martin v. Löwis9f2e3462007-07-21 17:22:18 +0000271 frac = ldexp(frac, (expo-1) % PyLong_SHIFT + 1);
Guido van Rossum149e9ea1991-06-03 10:58:24 +0000272 for (i = ndig; --i >= 0; ) {
273 long bits = (long)frac;
Guido van Rossum2095d241997-04-09 19:41:24 +0000274 v->ob_digit[i] = (digit) bits;
Guido van Rossum149e9ea1991-06-03 10:58:24 +0000275 frac = frac - (double)bits;
Martin v. Löwis9f2e3462007-07-21 17:22:18 +0000276 frac = ldexp(frac, PyLong_SHIFT);
Guido van Rossum149e9ea1991-06-03 10:58:24 +0000277 }
278 if (neg)
Christian Heimes90aa7642007-12-19 02:45:37 +0000279 Py_SIZE(v) = -(Py_SIZE(v));
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000280 return (PyObject *)v;
Guido van Rossum149e9ea1991-06-03 10:58:24 +0000281}
282
Thomas Wouters89f507f2006-12-13 04:49:30 +0000283/* Checking for overflow in PyLong_AsLong is a PITA since C doesn't define
284 * anything about what happens when a signed integer operation overflows,
285 * and some compilers think they're doing you a favor by being "clever"
286 * then. The bit pattern for the largest postive signed long is
287 * (unsigned long)LONG_MAX, and for the smallest negative signed long
288 * it is abs(LONG_MIN), which we could write -(unsigned long)LONG_MIN.
289 * However, some other compilers warn about applying unary minus to an
290 * unsigned operand. Hence the weird "0-".
291 */
292#define PY_ABS_LONG_MIN (0-(unsigned long)LONG_MIN)
293#define PY_ABS_SSIZE_T_MIN (0-(size_t)PY_SSIZE_T_MIN)
294
Guido van Rossumedcc38a1991-05-05 20:09:44 +0000295/* Get a C long int from a long int object.
296 Returns -1 and sets an error condition if overflow occurs. */
297
298long
Martin v. Löwisd1a1d1e2007-12-04 22:10:37 +0000299PyLong_AsLongAndOverflow(PyObject *vv, int *overflow)
Guido van Rossumedcc38a1991-05-05 20:09:44 +0000300{
Guido van Rossumf7531811998-05-26 14:33:37 +0000301 /* This version by Tim Peters */
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000302 register PyLongObject *v;
Guido van Rossumf7531811998-05-26 14:33:37 +0000303 unsigned long x, prev;
Georg Brandl61c31b02007-02-26 14:46:30 +0000304 long res;
Martin v. Löwis18e16552006-02-15 17:27:45 +0000305 Py_ssize_t i;
306 int sign;
Guido van Rossumddefaf32007-01-14 03:31:43 +0000307 int do_decref = 0; /* if nb_int was called */
Guido van Rossumf7531811998-05-26 14:33:37 +0000308
Martin v. Löwisd1a1d1e2007-12-04 22:10:37 +0000309 *overflow = 0;
Guido van Rossumddefaf32007-01-14 03:31:43 +0000310 if (vv == NULL) {
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000311 PyErr_BadInternalCall();
Guido van Rossumedcc38a1991-05-05 20:09:44 +0000312 return -1;
313 }
Guido van Rossumddefaf32007-01-14 03:31:43 +0000314
315 if (!PyLong_Check(vv)) {
316 PyNumberMethods *nb;
317 if ((nb = vv->ob_type->tp_as_number) == NULL ||
318 nb->nb_int == NULL) {
319 PyErr_SetString(PyExc_TypeError, "an integer is required");
320 return -1;
321 }
322 vv = (*nb->nb_int) (vv);
323 if (vv == NULL)
324 return -1;
325 do_decref = 1;
326 if (!PyLong_Check(vv)) {
327 Py_DECREF(vv);
328 PyErr_SetString(PyExc_TypeError,
329 "nb_int should return int object");
330 return -1;
331 }
332 }
333
Georg Brandl61c31b02007-02-26 14:46:30 +0000334 res = -1;
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000335 v = (PyLongObject *)vv;
Christian Heimes90aa7642007-12-19 02:45:37 +0000336 i = Py_SIZE(v);
Guido van Rossumf7531811998-05-26 14:33:37 +0000337
Georg Brandl61c31b02007-02-26 14:46:30 +0000338 switch (i) {
339 case -1:
340 res = -v->ob_digit[0];
341 break;
342 case 0:
343 res = 0;
344 break;
345 case 1:
346 res = v->ob_digit[0];
347 break;
348 default:
349 sign = 1;
350 x = 0;
351 if (i < 0) {
352 sign = -1;
353 i = -(i);
354 }
355 while (--i >= 0) {
356 prev = x;
Martin v. Löwis9f2e3462007-07-21 17:22:18 +0000357 x = (x << PyLong_SHIFT) + v->ob_digit[i];
358 if ((x >> PyLong_SHIFT) != prev) {
Christian Heimes90aa7642007-12-19 02:45:37 +0000359 *overflow = Py_SIZE(v) > 0 ? 1 : -1;
Georg Brandl61c31b02007-02-26 14:46:30 +0000360 goto exit;
361 }
362 }
363 /* Haven't lost any bits, but casting to long requires extra care
364 * (see comment above).
365 */
366 if (x <= (unsigned long)LONG_MAX) {
367 res = (long)x * sign;
368 }
369 else if (sign < 0 && x == PY_ABS_LONG_MIN) {
370 res = LONG_MIN;
371 }
372 else {
Christian Heimes90aa7642007-12-19 02:45:37 +0000373 *overflow = Py_SIZE(v) > 0 ? 1 : -1;
Martin v. Löwisd1a1d1e2007-12-04 22:10:37 +0000374 /* res is already set to -1 */
Georg Brandl61c31b02007-02-26 14:46:30 +0000375 }
376 }
377 exit:
Guido van Rossumddefaf32007-01-14 03:31:43 +0000378 if (do_decref) {
379 Py_DECREF(vv);
380 }
Georg Brandl61c31b02007-02-26 14:46:30 +0000381 return res;
Guido van Rossumedcc38a1991-05-05 20:09:44 +0000382}
383
Martin v. Löwisd1a1d1e2007-12-04 22:10:37 +0000384long
385PyLong_AsLong(PyObject *obj)
386{
387 int overflow;
388 long result = PyLong_AsLongAndOverflow(obj, &overflow);
389 if (overflow) {
390 /* XXX: could be cute and give a different
391 message for overflow == -1 */
392 PyErr_SetString(PyExc_OverflowError,
393 "Python int too large to convert to C long");
394 }
395 return result;
396}
397
Thomas Wouters00ee7ba2006-08-21 19:07:27 +0000398/* Get a Py_ssize_t from a long int object.
399 Returns -1 and sets an error condition if overflow occurs. */
400
401Py_ssize_t
Guido van Rossumddefaf32007-01-14 03:31:43 +0000402PyLong_AsSsize_t(PyObject *vv) {
Martin v. Löwis18e16552006-02-15 17:27:45 +0000403 register PyLongObject *v;
404 size_t x, prev;
405 Py_ssize_t i;
406 int sign;
407
408 if (vv == NULL || !PyLong_Check(vv)) {
409 PyErr_BadInternalCall();
410 return -1;
411 }
412 v = (PyLongObject *)vv;
Christian Heimes90aa7642007-12-19 02:45:37 +0000413 i = Py_SIZE(v);
Guido van Rossumddefaf32007-01-14 03:31:43 +0000414 switch (i) {
415 case -1: return -v->ob_digit[0];
416 case 0: return 0;
417 case 1: return v->ob_digit[0];
418 }
Martin v. Löwis18e16552006-02-15 17:27:45 +0000419 sign = 1;
420 x = 0;
421 if (i < 0) {
422 sign = -1;
423 i = -(i);
424 }
425 while (--i >= 0) {
426 prev = x;
Martin v. Löwis9f2e3462007-07-21 17:22:18 +0000427 x = (x << PyLong_SHIFT) + v->ob_digit[i];
428 if ((x >> PyLong_SHIFT) != prev)
Martin v. Löwis18e16552006-02-15 17:27:45 +0000429 goto overflow;
430 }
Thomas Wouters89f507f2006-12-13 04:49:30 +0000431 /* Haven't lost any bits, but casting to a signed type requires
432 * extra care (see comment above).
Martin v. Löwis18e16552006-02-15 17:27:45 +0000433 */
Thomas Wouters89f507f2006-12-13 04:49:30 +0000434 if (x <= (size_t)PY_SSIZE_T_MAX) {
435 return (Py_ssize_t)x * sign;
436 }
437 else if (sign < 0 && x == PY_ABS_SSIZE_T_MIN) {
438 return PY_SSIZE_T_MIN;
439 }
440 /* else overflow */
Martin v. Löwis18e16552006-02-15 17:27:45 +0000441
442 overflow:
443 PyErr_SetString(PyExc_OverflowError,
Guido van Rossum523d4f92007-01-15 00:31:49 +0000444 "Python int too large to convert to C ssize_t");
Thomas Wouters00ee7ba2006-08-21 19:07:27 +0000445 return -1;
Martin v. Löwis18e16552006-02-15 17:27:45 +0000446}
447
Guido van Rossumd8c80482002-08-13 00:24:58 +0000448/* Get a C unsigned long int from a long int object.
Guido van Rossum53756b11997-01-03 17:14:46 +0000449 Returns -1 and sets an error condition if overflow occurs. */
450
451unsigned long
Tim Peters9f688bf2000-07-07 15:53:28 +0000452PyLong_AsUnsignedLong(PyObject *vv)
Guido van Rossum53756b11997-01-03 17:14:46 +0000453{
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000454 register PyLongObject *v;
Guido van Rossum53756b11997-01-03 17:14:46 +0000455 unsigned long x, prev;
Martin v. Löwis18e16552006-02-15 17:27:45 +0000456 Py_ssize_t i;
Tim Peters5af4e6c2002-08-12 02:31:19 +0000457
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000458 if (vv == NULL || !PyLong_Check(vv)) {
459 PyErr_BadInternalCall();
Guido van Rossum53756b11997-01-03 17:14:46 +0000460 return (unsigned long) -1;
461 }
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000462 v = (PyLongObject *)vv;
Christian Heimes90aa7642007-12-19 02:45:37 +0000463 i = Py_SIZE(v);
Guido van Rossum53756b11997-01-03 17:14:46 +0000464 x = 0;
465 if (i < 0) {
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000466 PyErr_SetString(PyExc_OverflowError,
Guido van Rossumddefaf32007-01-14 03:31:43 +0000467 "can't convert negative value to unsigned int");
Guido van Rossum53756b11997-01-03 17:14:46 +0000468 return (unsigned long) -1;
469 }
Guido van Rossumddefaf32007-01-14 03:31:43 +0000470 switch (i) {
471 case 0: return 0;
472 case 1: return v->ob_digit[0];
473 }
Guido van Rossum53756b11997-01-03 17:14:46 +0000474 while (--i >= 0) {
475 prev = x;
Martin v. Löwis9f2e3462007-07-21 17:22:18 +0000476 x = (x << PyLong_SHIFT) + v->ob_digit[i];
477 if ((x >> PyLong_SHIFT) != prev) {
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000478 PyErr_SetString(PyExc_OverflowError,
Guido van Rossum523d4f92007-01-15 00:31:49 +0000479 "python int too large to convert to C unsigned long");
Guido van Rossumddefaf32007-01-14 03:31:43 +0000480 return (unsigned long) -1;
481 }
482 }
483 return x;
484}
485
486/* Get a C unsigned long int from a long int object.
487 Returns -1 and sets an error condition if overflow occurs. */
488
489size_t
490PyLong_AsSize_t(PyObject *vv)
491{
492 register PyLongObject *v;
493 size_t x, prev;
494 Py_ssize_t i;
495
496 if (vv == NULL || !PyLong_Check(vv)) {
497 PyErr_BadInternalCall();
498 return (unsigned long) -1;
499 }
500 v = (PyLongObject *)vv;
Christian Heimes90aa7642007-12-19 02:45:37 +0000501 i = Py_SIZE(v);
Guido van Rossumddefaf32007-01-14 03:31:43 +0000502 x = 0;
503 if (i < 0) {
504 PyErr_SetString(PyExc_OverflowError,
505 "can't convert negative value to size_t");
506 return (size_t) -1;
507 }
508 switch (i) {
509 case 0: return 0;
510 case 1: return v->ob_digit[0];
511 }
512 while (--i >= 0) {
513 prev = x;
Martin v. Löwis9f2e3462007-07-21 17:22:18 +0000514 x = (x << PyLong_SHIFT) + v->ob_digit[i];
515 if ((x >> PyLong_SHIFT) != prev) {
Guido van Rossumddefaf32007-01-14 03:31:43 +0000516 PyErr_SetString(PyExc_OverflowError,
Guido van Rossum523d4f92007-01-15 00:31:49 +0000517 "Python int too large to convert to C size_t");
Guido van Rossum53756b11997-01-03 17:14:46 +0000518 return (unsigned long) -1;
519 }
520 }
521 return x;
522}
523
Thomas Hellera4ea6032003-04-17 18:55:45 +0000524/* Get a C unsigned long int from a long int object, ignoring the high bits.
525 Returns -1 and sets an error condition if an error occurs. */
526
Guido van Rossumddefaf32007-01-14 03:31:43 +0000527static unsigned long
528_PyLong_AsUnsignedLongMask(PyObject *vv)
Thomas Hellera4ea6032003-04-17 18:55:45 +0000529{
530 register PyLongObject *v;
531 unsigned long x;
Martin v. Löwis18e16552006-02-15 17:27:45 +0000532 Py_ssize_t i;
533 int sign;
Thomas Hellera4ea6032003-04-17 18:55:45 +0000534
535 if (vv == NULL || !PyLong_Check(vv)) {
536 PyErr_BadInternalCall();
537 return (unsigned long) -1;
538 }
539 v = (PyLongObject *)vv;
Christian Heimes90aa7642007-12-19 02:45:37 +0000540 i = Py_SIZE(v);
Guido van Rossumddefaf32007-01-14 03:31:43 +0000541 switch (i) {
542 case 0: return 0;
543 case 1: return v->ob_digit[0];
544 }
Thomas Hellera4ea6032003-04-17 18:55:45 +0000545 sign = 1;
546 x = 0;
547 if (i < 0) {
548 sign = -1;
549 i = -i;
550 }
551 while (--i >= 0) {
Martin v. Löwis9f2e3462007-07-21 17:22:18 +0000552 x = (x << PyLong_SHIFT) + v->ob_digit[i];
Thomas Hellera4ea6032003-04-17 18:55:45 +0000553 }
554 return x * sign;
555}
556
Guido van Rossumddefaf32007-01-14 03:31:43 +0000557unsigned long
558PyLong_AsUnsignedLongMask(register PyObject *op)
559{
560 PyNumberMethods *nb;
561 PyLongObject *lo;
562 unsigned long val;
563
564 if (op && PyLong_Check(op))
565 return _PyLong_AsUnsignedLongMask(op);
566
567 if (op == NULL || (nb = op->ob_type->tp_as_number) == NULL ||
568 nb->nb_int == NULL) {
569 PyErr_SetString(PyExc_TypeError, "an integer is required");
570 return (unsigned long)-1;
571 }
572
573 lo = (PyLongObject*) (*nb->nb_int) (op);
574 if (lo == NULL)
575 return (unsigned long)-1;
576 if (PyLong_Check(lo)) {
577 val = _PyLong_AsUnsignedLongMask((PyObject *)lo);
578 Py_DECREF(lo);
579 if (PyErr_Occurred())
580 return (unsigned long)-1;
581 return val;
582 }
583 else
584 {
585 Py_DECREF(lo);
586 PyErr_SetString(PyExc_TypeError,
587 "nb_int should return int object");
588 return (unsigned long)-1;
589 }
590}
591
Tim Peters5b8132f2003-01-31 15:52:05 +0000592int
593_PyLong_Sign(PyObject *vv)
594{
595 PyLongObject *v = (PyLongObject *)vv;
Tim Peters5b8132f2003-01-31 15:52:05 +0000596
597 assert(v != NULL);
598 assert(PyLong_Check(v));
Tim Peters5b8132f2003-01-31 15:52:05 +0000599
Christian Heimes90aa7642007-12-19 02:45:37 +0000600 return Py_SIZE(v) == 0 ? 0 : (Py_SIZE(v) < 0 ? -1 : 1);
Tim Peters5b8132f2003-01-31 15:52:05 +0000601}
602
Tim Petersbaefd9e2003-01-28 20:37:45 +0000603size_t
604_PyLong_NumBits(PyObject *vv)
605{
606 PyLongObject *v = (PyLongObject *)vv;
Tim Peters5b8132f2003-01-31 15:52:05 +0000607 size_t result = 0;
Martin v. Löwis18e16552006-02-15 17:27:45 +0000608 Py_ssize_t ndigits;
Tim Petersbaefd9e2003-01-28 20:37:45 +0000609
610 assert(v != NULL);
611 assert(PyLong_Check(v));
Christian Heimes90aa7642007-12-19 02:45:37 +0000612 ndigits = ABS(Py_SIZE(v));
Tim Petersbaefd9e2003-01-28 20:37:45 +0000613 assert(ndigits == 0 || v->ob_digit[ndigits - 1] != 0);
614 if (ndigits > 0) {
Tim Petersbaefd9e2003-01-28 20:37:45 +0000615 digit msd = v->ob_digit[ndigits - 1];
616
Martin v. Löwis9f2e3462007-07-21 17:22:18 +0000617 result = (ndigits - 1) * PyLong_SHIFT;
618 if (result / PyLong_SHIFT != (size_t)(ndigits - 1))
Tim Petersbaefd9e2003-01-28 20:37:45 +0000619 goto Overflow;
620 do {
621 ++result;
622 if (result == 0)
623 goto Overflow;
624 msd >>= 1;
625 } while (msd);
626 }
627 return result;
628
629Overflow:
Guido van Rossumddefaf32007-01-14 03:31:43 +0000630 PyErr_SetString(PyExc_OverflowError, "int has too many bits "
Tim Petersbaefd9e2003-01-28 20:37:45 +0000631 "to express in a platform size_t");
632 return (size_t)-1;
633}
634
Tim Peters2a9b3672001-06-11 21:23:58 +0000635PyObject *
636_PyLong_FromByteArray(const unsigned char* bytes, size_t n,
637 int little_endian, int is_signed)
638{
639 const unsigned char* pstartbyte;/* LSB of bytes */
640 int incr; /* direction to move pstartbyte */
641 const unsigned char* pendbyte; /* MSB of bytes */
642 size_t numsignificantbytes; /* number of bytes that matter */
643 size_t ndigits; /* number of Python long digits */
644 PyLongObject* v; /* result */
645 int idigit = 0; /* next free index in v->ob_digit */
646
647 if (n == 0)
648 return PyLong_FromLong(0L);
649
650 if (little_endian) {
651 pstartbyte = bytes;
652 pendbyte = bytes + n - 1;
653 incr = 1;
654 }
655 else {
656 pstartbyte = bytes + n - 1;
657 pendbyte = bytes;
658 incr = -1;
659 }
660
661 if (is_signed)
662 is_signed = *pendbyte >= 0x80;
663
664 /* Compute numsignificantbytes. This consists of finding the most
665 significant byte. Leading 0 bytes are insignficant if the number
666 is positive, and leading 0xff bytes if negative. */
667 {
668 size_t i;
669 const unsigned char* p = pendbyte;
670 const int pincr = -incr; /* search MSB to LSB */
671 const unsigned char insignficant = is_signed ? 0xff : 0x00;
672
673 for (i = 0; i < n; ++i, p += pincr) {
674 if (*p != insignficant)
675 break;
676 }
677 numsignificantbytes = n - i;
678 /* 2's-comp is a bit tricky here, e.g. 0xff00 == -0x0100, so
679 actually has 2 significant bytes. OTOH, 0xff0001 ==
680 -0x00ffff, so we wouldn't *need* to bump it there; but we
681 do for 0xffff = -0x0001. To be safe without bothering to
682 check every case, bump it regardless. */
683 if (is_signed && numsignificantbytes < n)
684 ++numsignificantbytes;
685 }
686
687 /* How many Python long digits do we need? We have
Martin v. Löwis9f2e3462007-07-21 17:22:18 +0000688 8*numsignificantbytes bits, and each Python long digit has PyLong_SHIFT
Tim Peters2a9b3672001-06-11 21:23:58 +0000689 bits, so it's the ceiling of the quotient. */
Martin v. Löwis9f2e3462007-07-21 17:22:18 +0000690 ndigits = (numsignificantbytes * 8 + PyLong_SHIFT - 1) / PyLong_SHIFT;
Tim Peters2a9b3672001-06-11 21:23:58 +0000691 if (ndigits > (size_t)INT_MAX)
692 return PyErr_NoMemory();
693 v = _PyLong_New((int)ndigits);
694 if (v == NULL)
695 return NULL;
696
697 /* Copy the bits over. The tricky parts are computing 2's-comp on
698 the fly for signed numbers, and dealing with the mismatch between
699 8-bit bytes and (probably) 15-bit Python digits.*/
700 {
701 size_t i;
Tim Petersf251d062001-06-13 21:09:15 +0000702 twodigits carry = 1; /* for 2's-comp calculation */
Tim Peters2a9b3672001-06-11 21:23:58 +0000703 twodigits accum = 0; /* sliding register */
704 unsigned int accumbits = 0; /* number of bits in accum */
705 const unsigned char* p = pstartbyte;
706
707 for (i = 0; i < numsignificantbytes; ++i, p += incr) {
Tim Peters8bc84b42001-06-12 19:17:03 +0000708 twodigits thisbyte = *p;
Tim Peters2a9b3672001-06-11 21:23:58 +0000709 /* Compute correction for 2's comp, if needed. */
710 if (is_signed) {
711 thisbyte = (0xff ^ thisbyte) + carry;
712 carry = thisbyte >> 8;
713 thisbyte &= 0xff;
714 }
715 /* Because we're going LSB to MSB, thisbyte is
716 more significant than what's already in accum,
717 so needs to be prepended to accum. */
718 accum |= thisbyte << accumbits;
719 accumbits += 8;
Martin v. Löwis9f2e3462007-07-21 17:22:18 +0000720 if (accumbits >= PyLong_SHIFT) {
Tim Peters2a9b3672001-06-11 21:23:58 +0000721 /* There's enough to fill a Python digit. */
722 assert(idigit < (int)ndigits);
Martin v. Löwis9f2e3462007-07-21 17:22:18 +0000723 v->ob_digit[idigit] = (digit)(accum & PyLong_MASK);
Tim Peters2a9b3672001-06-11 21:23:58 +0000724 ++idigit;
Martin v. Löwis9f2e3462007-07-21 17:22:18 +0000725 accum >>= PyLong_SHIFT;
726 accumbits -= PyLong_SHIFT;
727 assert(accumbits < PyLong_SHIFT);
Tim Peters2a9b3672001-06-11 21:23:58 +0000728 }
729 }
Martin v. Löwis9f2e3462007-07-21 17:22:18 +0000730 assert(accumbits < PyLong_SHIFT);
Tim Peters2a9b3672001-06-11 21:23:58 +0000731 if (accumbits) {
732 assert(idigit < (int)ndigits);
733 v->ob_digit[idigit] = (digit)accum;
734 ++idigit;
735 }
736 }
737
Christian Heimes90aa7642007-12-19 02:45:37 +0000738 Py_SIZE(v) = is_signed ? -idigit : idigit;
Tim Peters2a9b3672001-06-11 21:23:58 +0000739 return (PyObject *)long_normalize(v);
740}
741
742int
743_PyLong_AsByteArray(PyLongObject* v,
744 unsigned char* bytes, size_t n,
745 int little_endian, int is_signed)
746{
747 int i; /* index into v->ob_digit */
Martin v. Löwis18e16552006-02-15 17:27:45 +0000748 Py_ssize_t ndigits; /* |v->ob_size| */
Tim Peters2a9b3672001-06-11 21:23:58 +0000749 twodigits accum; /* sliding register */
750 unsigned int accumbits; /* # bits in accum */
751 int do_twos_comp; /* store 2's-comp? is_signed and v < 0 */
752 twodigits carry; /* for computing 2's-comp */
753 size_t j; /* # bytes filled */
754 unsigned char* p; /* pointer to next byte in bytes */
755 int pincr; /* direction to move p */
756
757 assert(v != NULL && PyLong_Check(v));
758
Christian Heimes90aa7642007-12-19 02:45:37 +0000759 if (Py_SIZE(v) < 0) {
760 ndigits = -(Py_SIZE(v));
Tim Peters2a9b3672001-06-11 21:23:58 +0000761 if (!is_signed) {
762 PyErr_SetString(PyExc_TypeError,
Guido van Rossumddefaf32007-01-14 03:31:43 +0000763 "can't convert negative int to unsigned");
Tim Peters2a9b3672001-06-11 21:23:58 +0000764 return -1;
765 }
766 do_twos_comp = 1;
767 }
768 else {
Christian Heimes90aa7642007-12-19 02:45:37 +0000769 ndigits = Py_SIZE(v);
Tim Peters2a9b3672001-06-11 21:23:58 +0000770 do_twos_comp = 0;
771 }
772
773 if (little_endian) {
774 p = bytes;
775 pincr = 1;
776 }
777 else {
778 p = bytes + n - 1;
779 pincr = -1;
780 }
781
Tim Peters898cf852001-06-13 20:50:08 +0000782 /* Copy over all the Python digits.
783 It's crucial that every Python digit except for the MSD contribute
Martin v. Löwis9f2e3462007-07-21 17:22:18 +0000784 exactly PyLong_SHIFT bits to the total, so first assert that the long is
Tim Peters898cf852001-06-13 20:50:08 +0000785 normalized. */
786 assert(ndigits == 0 || v->ob_digit[ndigits - 1] != 0);
Tim Peters2a9b3672001-06-11 21:23:58 +0000787 j = 0;
788 accum = 0;
789 accumbits = 0;
790 carry = do_twos_comp ? 1 : 0;
791 for (i = 0; i < ndigits; ++i) {
792 twodigits thisdigit = v->ob_digit[i];
793 if (do_twos_comp) {
Martin v. Löwis9f2e3462007-07-21 17:22:18 +0000794 thisdigit = (thisdigit ^ PyLong_MASK) + carry;
795 carry = thisdigit >> PyLong_SHIFT;
796 thisdigit &= PyLong_MASK;
Tim Peters2a9b3672001-06-11 21:23:58 +0000797 }
Tim Peters8bc84b42001-06-12 19:17:03 +0000798 /* Because we're going LSB to MSB, thisdigit is more
799 significant than what's already in accum, so needs to be
800 prepended to accum. */
801 accum |= thisdigit << accumbits;
Martin v. Löwis9f2e3462007-07-21 17:22:18 +0000802 accumbits += PyLong_SHIFT;
Tim Peters8bc84b42001-06-12 19:17:03 +0000803
Tim Petersede05092001-06-14 08:53:38 +0000804 /* The most-significant digit may be (probably is) at least
805 partly empty. */
Tim Peters8bc84b42001-06-12 19:17:03 +0000806 if (i == ndigits - 1) {
Tim Petersede05092001-06-14 08:53:38 +0000807 /* Count # of sign bits -- they needn't be stored,
808 * although for signed conversion we need later to
809 * make sure at least one sign bit gets stored.
810 * First shift conceptual sign bit to real sign bit.
811 */
812 stwodigits s = (stwodigits)(thisdigit <<
Martin v. Löwis9f2e3462007-07-21 17:22:18 +0000813 (8*sizeof(stwodigits) - PyLong_SHIFT));
Tim Peters7a3bfc32001-06-12 01:22:22 +0000814 unsigned int nsignbits = 0;
Martin v. Löwis9f2e3462007-07-21 17:22:18 +0000815 while ((s < 0) == do_twos_comp && nsignbits < PyLong_SHIFT) {
Tim Peters7a3bfc32001-06-12 01:22:22 +0000816 ++nsignbits;
Tim Petersede05092001-06-14 08:53:38 +0000817 s <<= 1;
Tim Peters7a3bfc32001-06-12 01:22:22 +0000818 }
Tim Petersede05092001-06-14 08:53:38 +0000819 accumbits -= nsignbits;
Tim Peters7a3bfc32001-06-12 01:22:22 +0000820 }
Tim Peters8bc84b42001-06-12 19:17:03 +0000821
Tim Peters2a9b3672001-06-11 21:23:58 +0000822 /* Store as many bytes as possible. */
Tim Peters7a3bfc32001-06-12 01:22:22 +0000823 while (accumbits >= 8) {
Tim Peters2a9b3672001-06-11 21:23:58 +0000824 if (j >= n)
825 goto Overflow;
826 ++j;
827 *p = (unsigned char)(accum & 0xff);
828 p += pincr;
829 accumbits -= 8;
830 accum >>= 8;
Tim Peters7a3bfc32001-06-12 01:22:22 +0000831 }
Tim Peters2a9b3672001-06-11 21:23:58 +0000832 }
833
834 /* Store the straggler (if any). */
835 assert(accumbits < 8);
836 assert(carry == 0); /* else do_twos_comp and *every* digit was 0 */
Tim Peters7a3bfc32001-06-12 01:22:22 +0000837 if (accumbits > 0) {
Tim Peters2a9b3672001-06-11 21:23:58 +0000838 if (j >= n)
839 goto Overflow;
840 ++j;
841 if (do_twos_comp) {
842 /* Fill leading bits of the byte with sign bits
843 (appropriately pretending that the long had an
844 infinite supply of sign bits). */
845 accum |= (~(twodigits)0) << accumbits;
846 }
847 *p = (unsigned char)(accum & 0xff);
848 p += pincr;
849 }
Tim Peters05607ad2001-06-13 21:01:27 +0000850 else if (j == n && n > 0 && is_signed) {
851 /* The main loop filled the byte array exactly, so the code
852 just above didn't get to ensure there's a sign bit, and the
853 loop below wouldn't add one either. Make sure a sign bit
854 exists. */
Tim Peters2a9b3672001-06-11 21:23:58 +0000855 unsigned char msb = *(p - pincr);
Tim Peters05607ad2001-06-13 21:01:27 +0000856 int sign_bit_set = msb >= 0x80;
857 assert(accumbits == 0);
858 if (sign_bit_set == do_twos_comp)
859 return 0;
860 else
Tim Peters2a9b3672001-06-11 21:23:58 +0000861 goto Overflow;
862 }
Tim Peters05607ad2001-06-13 21:01:27 +0000863
864 /* Fill remaining bytes with copies of the sign bit. */
865 {
866 unsigned char signbyte = do_twos_comp ? 0xffU : 0U;
867 for ( ; j < n; ++j, p += pincr)
868 *p = signbyte;
869 }
870
Tim Peters2a9b3672001-06-11 21:23:58 +0000871 return 0;
872
873Overflow:
Guido van Rossumddefaf32007-01-14 03:31:43 +0000874 PyErr_SetString(PyExc_OverflowError, "int too big to convert");
Tim Peters2a9b3672001-06-11 21:23:58 +0000875 return -1;
Tim Peters5af4e6c2002-08-12 02:31:19 +0000876
Tim Peters2a9b3672001-06-11 21:23:58 +0000877}
878
Tim Petersa1c1b0f2001-09-04 02:50:49 +0000879double
880_PyLong_AsScaledDouble(PyObject *vv, int *exponent)
881{
882/* NBITS_WANTED should be > the number of bits in a double's precision,
883 but small enough so that 2**NBITS_WANTED is within the normal double
884 range. nbitsneeded is set to 1 less than that because the most-significant
885 Python digit contains at least 1 significant bit, but we don't want to
886 bother counting them (catering to the worst case cheaply).
887
888 57 is one more than VAX-D double precision; I (Tim) don't know of a double
889 format with more precision than that; it's 1 larger so that we add in at
890 least one round bit to stand in for the ignored least-significant bits.
891*/
892#define NBITS_WANTED 57
893 PyLongObject *v;
894 double x;
Martin v. Löwis9f2e3462007-07-21 17:22:18 +0000895 const double multiplier = (double)(1L << PyLong_SHIFT);
Martin v. Löwis18e16552006-02-15 17:27:45 +0000896 Py_ssize_t i;
897 int sign;
Tim Petersa1c1b0f2001-09-04 02:50:49 +0000898 int nbitsneeded;
899
900 if (vv == NULL || !PyLong_Check(vv)) {
901 PyErr_BadInternalCall();
902 return -1;
903 }
904 v = (PyLongObject *)vv;
Christian Heimes90aa7642007-12-19 02:45:37 +0000905 i = Py_SIZE(v);
Tim Petersa1c1b0f2001-09-04 02:50:49 +0000906 sign = 1;
907 if (i < 0) {
908 sign = -1;
909 i = -(i);
910 }
911 else if (i == 0) {
912 *exponent = 0;
913 return 0.0;
914 }
915 --i;
916 x = (double)v->ob_digit[i];
917 nbitsneeded = NBITS_WANTED - 1;
918 /* Invariant: i Python digits remain unaccounted for. */
919 while (i > 0 && nbitsneeded > 0) {
920 --i;
921 x = x * multiplier + (double)v->ob_digit[i];
Martin v. Löwis9f2e3462007-07-21 17:22:18 +0000922 nbitsneeded -= PyLong_SHIFT;
Tim Petersa1c1b0f2001-09-04 02:50:49 +0000923 }
924 /* There are i digits we didn't shift in. Pretending they're all
Martin v. Löwis9f2e3462007-07-21 17:22:18 +0000925 zeroes, the true value is x * 2**(i*PyLong_SHIFT). */
Tim Petersa1c1b0f2001-09-04 02:50:49 +0000926 *exponent = i;
927 assert(x > 0.0);
928 return x * sign;
929#undef NBITS_WANTED
930}
931
Guido van Rossum09e6ad01997-02-14 22:54:21 +0000932/* Get a C double from a long int object. */
Guido van Rossumedcc38a1991-05-05 20:09:44 +0000933
934double
Tim Peters9f688bf2000-07-07 15:53:28 +0000935PyLong_AsDouble(PyObject *vv)
Guido van Rossumedcc38a1991-05-05 20:09:44 +0000936{
Thomas Wouters553489a2006-02-01 21:32:04 +0000937 int e = -1;
Guido van Rossumedcc38a1991-05-05 20:09:44 +0000938 double x;
Tim Peters9fffa3e2001-09-04 05:14:19 +0000939
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000940 if (vv == NULL || !PyLong_Check(vv)) {
941 PyErr_BadInternalCall();
Guido van Rossumedcc38a1991-05-05 20:09:44 +0000942 return -1;
943 }
Tim Peters9fffa3e2001-09-04 05:14:19 +0000944 x = _PyLong_AsScaledDouble(vv, &e);
945 if (x == -1.0 && PyErr_Occurred())
946 return -1.0;
Thomas Wouters553489a2006-02-01 21:32:04 +0000947 /* 'e' initialized to -1 to silence gcc-4.0.x, but it should be
948 set correctly after a successful _PyLong_AsScaledDouble() call */
949 assert(e >= 0);
Martin v. Löwis9f2e3462007-07-21 17:22:18 +0000950 if (e > INT_MAX / PyLong_SHIFT)
Tim Peters9fffa3e2001-09-04 05:14:19 +0000951 goto overflow;
952 errno = 0;
Martin v. Löwis9f2e3462007-07-21 17:22:18 +0000953 x = ldexp(x, e * PyLong_SHIFT);
Tim Peters57f282a2001-09-05 05:38:10 +0000954 if (Py_OVERFLOWED(x))
Tim Peters9fffa3e2001-09-04 05:14:19 +0000955 goto overflow;
956 return x;
957
958overflow:
959 PyErr_SetString(PyExc_OverflowError,
Guido van Rossum523d4f92007-01-15 00:31:49 +0000960 "Python int too large to convert to C double");
Tim Peters9fffa3e2001-09-04 05:14:19 +0000961 return -1.0;
Guido van Rossumedcc38a1991-05-05 20:09:44 +0000962}
963
Guido van Rossum78694d91998-09-18 14:14:13 +0000964/* Create a new long (or int) object from a C pointer */
965
966PyObject *
Tim Peters9f688bf2000-07-07 15:53:28 +0000967PyLong_FromVoidPtr(void *p)
Guido van Rossum78694d91998-09-18 14:14:13 +0000968{
Tim Peters70128a12001-06-16 08:48:40 +0000969#ifndef HAVE_LONG_LONG
970# error "PyLong_FromVoidPtr: sizeof(void*) > sizeof(long), but no long long"
971#endif
972#if SIZEOF_LONG_LONG < SIZEOF_VOID_P
Martin v. Löwisb9a0f912003-03-29 10:06:18 +0000973# error "PyLong_FromVoidPtr: sizeof(PY_LONG_LONG) < sizeof(void*)"
Tim Peters70128a12001-06-16 08:48:40 +0000974#endif
Guido van Rossumddefaf32007-01-14 03:31:43 +0000975 /* special-case null pointer */
976 if (!p)
Christian Heimes217cfd12007-12-02 14:31:20 +0000977 return PyLong_FromLong(0);
Guido van Rossumddefaf32007-01-14 03:31:43 +0000978 return PyLong_FromUnsignedLongLong((unsigned PY_LONG_LONG)(Py_uintptr_t)p);
Tim Peters70128a12001-06-16 08:48:40 +0000979
Guido van Rossum78694d91998-09-18 14:14:13 +0000980}
981
982/* Get a C pointer from a long object (or an int object in some cases) */
983
984void *
Tim Peters9f688bf2000-07-07 15:53:28 +0000985PyLong_AsVoidPtr(PyObject *vv)
Guido van Rossum78694d91998-09-18 14:14:13 +0000986{
987 /* This function will allow int or long objects. If vv is neither,
988 then the PyLong_AsLong*() functions will raise the exception:
989 PyExc_SystemError, "bad argument to internal function"
990 */
Tim Peters70128a12001-06-16 08:48:40 +0000991#if SIZEOF_VOID_P <= SIZEOF_LONG
Guido van Rossum78694d91998-09-18 14:14:13 +0000992 long x;
993
Guido van Rossumddefaf32007-01-14 03:31:43 +0000994 if (PyLong_Check(vv) && _PyLong_Sign(vv) < 0)
Guido van Rossum78694d91998-09-18 14:14:13 +0000995 x = PyLong_AsLong(vv);
Thomas Wouters49fd7fa2006-04-21 10:40:58 +0000996 else
997 x = PyLong_AsUnsignedLong(vv);
Guido van Rossum78694d91998-09-18 14:14:13 +0000998#else
Tim Peters70128a12001-06-16 08:48:40 +0000999
1000#ifndef HAVE_LONG_LONG
1001# error "PyLong_AsVoidPtr: sizeof(void*) > sizeof(long), but no long long"
1002#endif
1003#if SIZEOF_LONG_LONG < SIZEOF_VOID_P
Martin v. Löwisb9a0f912003-03-29 10:06:18 +00001004# error "PyLong_AsVoidPtr: sizeof(PY_LONG_LONG) < sizeof(void*)"
Tim Peters70128a12001-06-16 08:48:40 +00001005#endif
Martin v. Löwisb9a0f912003-03-29 10:06:18 +00001006 PY_LONG_LONG x;
Guido van Rossum78694d91998-09-18 14:14:13 +00001007
Guido van Rossumddefaf32007-01-14 03:31:43 +00001008 if (PyLong_Check(vv) && _PyLong_Sign(vv) < 0)
Guido van Rossum78694d91998-09-18 14:14:13 +00001009 x = PyLong_AsLongLong(vv);
Thomas Wouters49fd7fa2006-04-21 10:40:58 +00001010 else
1011 x = PyLong_AsUnsignedLongLong(vv);
Tim Peters70128a12001-06-16 08:48:40 +00001012
1013#endif /* SIZEOF_VOID_P <= SIZEOF_LONG */
Guido van Rossum78694d91998-09-18 14:14:13 +00001014
1015 if (x == -1 && PyErr_Occurred())
1016 return NULL;
1017 return (void *)x;
1018}
1019
Guido van Rossum1a8791e1998-08-04 22:46:29 +00001020#ifdef HAVE_LONG_LONG
Tim Petersd1a7da62001-06-13 00:35:57 +00001021
Martin v. Löwisb9a0f912003-03-29 10:06:18 +00001022/* Initial PY_LONG_LONG support by Chris Herborth (chrish@qnx.com), later
Tim Petersd1a7da62001-06-13 00:35:57 +00001023 * rewritten to use the newer PyLong_{As,From}ByteArray API.
Guido van Rossum1a8791e1998-08-04 22:46:29 +00001024 */
1025
Tim Peterscf37dfc2001-06-14 18:42:50 +00001026#define IS_LITTLE_ENDIAN (int)*(unsigned char*)&one
Tim Petersd1a7da62001-06-13 00:35:57 +00001027
Martin v. Löwisb9a0f912003-03-29 10:06:18 +00001028/* Create a new long int object from a C PY_LONG_LONG int. */
Guido van Rossum1a8791e1998-08-04 22:46:29 +00001029
1030PyObject *
Martin v. Löwisb9a0f912003-03-29 10:06:18 +00001031PyLong_FromLongLong(PY_LONG_LONG ival)
Guido van Rossum1a8791e1998-08-04 22:46:29 +00001032{
Thomas Wouters477c8d52006-05-27 19:21:47 +00001033 PyLongObject *v;
1034 unsigned PY_LONG_LONG t; /* unsigned so >> doesn't propagate sign bit */
1035 int ndigits = 0;
1036 int negative = 0;
1037
Guido van Rossumddefaf32007-01-14 03:31:43 +00001038 CHECK_SMALL_INT(ival);
Thomas Wouters477c8d52006-05-27 19:21:47 +00001039 if (ival < 0) {
1040 ival = -ival;
1041 negative = 1;
1042 }
1043
1044 /* Count the number of Python digits.
1045 We used to pick 5 ("big enough for anything"), but that's a
1046 waste of time and space given that 5*15 = 75 bits are rarely
1047 needed. */
1048 t = (unsigned PY_LONG_LONG)ival;
1049 while (t) {
1050 ++ndigits;
Martin v. Löwis9f2e3462007-07-21 17:22:18 +00001051 t >>= PyLong_SHIFT;
Thomas Wouters477c8d52006-05-27 19:21:47 +00001052 }
1053 v = _PyLong_New(ndigits);
1054 if (v != NULL) {
1055 digit *p = v->ob_digit;
Christian Heimes90aa7642007-12-19 02:45:37 +00001056 Py_SIZE(v) = negative ? -ndigits : ndigits;
Thomas Wouters477c8d52006-05-27 19:21:47 +00001057 t = (unsigned PY_LONG_LONG)ival;
1058 while (t) {
Martin v. Löwis9f2e3462007-07-21 17:22:18 +00001059 *p++ = (digit)(t & PyLong_MASK);
1060 t >>= PyLong_SHIFT;
Thomas Wouters477c8d52006-05-27 19:21:47 +00001061 }
1062 }
1063 return (PyObject *)v;
Guido van Rossum1a8791e1998-08-04 22:46:29 +00001064}
1065
Martin v. Löwisb9a0f912003-03-29 10:06:18 +00001066/* Create a new long int object from a C unsigned PY_LONG_LONG int. */
Tim Petersd1a7da62001-06-13 00:35:57 +00001067
Guido van Rossum1a8791e1998-08-04 22:46:29 +00001068PyObject *
Martin v. Löwisb9a0f912003-03-29 10:06:18 +00001069PyLong_FromUnsignedLongLong(unsigned PY_LONG_LONG ival)
Guido van Rossum1a8791e1998-08-04 22:46:29 +00001070{
Thomas Wouters477c8d52006-05-27 19:21:47 +00001071 PyLongObject *v;
1072 unsigned PY_LONG_LONG t;
1073 int ndigits = 0;
1074
Martin v. Löwis9f2e3462007-07-21 17:22:18 +00001075 if (ival < PyLong_BASE)
Guido van Rossumddefaf32007-01-14 03:31:43 +00001076 return PyLong_FromLong(ival);
Thomas Wouters477c8d52006-05-27 19:21:47 +00001077 /* Count the number of Python digits. */
1078 t = (unsigned PY_LONG_LONG)ival;
1079 while (t) {
1080 ++ndigits;
Martin v. Löwis9f2e3462007-07-21 17:22:18 +00001081 t >>= PyLong_SHIFT;
Thomas Wouters477c8d52006-05-27 19:21:47 +00001082 }
1083 v = _PyLong_New(ndigits);
1084 if (v != NULL) {
1085 digit *p = v->ob_digit;
Christian Heimes90aa7642007-12-19 02:45:37 +00001086 Py_SIZE(v) = ndigits;
Thomas Wouters477c8d52006-05-27 19:21:47 +00001087 while (ival) {
Martin v. Löwis9f2e3462007-07-21 17:22:18 +00001088 *p++ = (digit)(ival & PyLong_MASK);
1089 ival >>= PyLong_SHIFT;
Thomas Wouters477c8d52006-05-27 19:21:47 +00001090 }
1091 }
1092 return (PyObject *)v;
Guido van Rossum1a8791e1998-08-04 22:46:29 +00001093}
1094
Martin v. Löwis18e16552006-02-15 17:27:45 +00001095/* Create a new long int object from a C Py_ssize_t. */
1096
1097PyObject *
Guido van Rossumddefaf32007-01-14 03:31:43 +00001098PyLong_FromSsize_t(Py_ssize_t ival)
Martin v. Löwis18e16552006-02-15 17:27:45 +00001099{
1100 Py_ssize_t bytes = ival;
1101 int one = 1;
Martin v. Löwis9f2e3462007-07-21 17:22:18 +00001102 if (ival < PyLong_BASE)
Guido van Rossumddefaf32007-01-14 03:31:43 +00001103 return PyLong_FromLong(ival);
Martin v. Löwis18e16552006-02-15 17:27:45 +00001104 return _PyLong_FromByteArray(
1105 (unsigned char *)&bytes,
Guido van Rossumddefaf32007-01-14 03:31:43 +00001106 SIZEOF_SIZE_T, IS_LITTLE_ENDIAN, 1);
Martin v. Löwis18e16552006-02-15 17:27:45 +00001107}
1108
1109/* Create a new long int object from a C size_t. */
1110
1111PyObject *
Guido van Rossumddefaf32007-01-14 03:31:43 +00001112PyLong_FromSize_t(size_t ival)
Martin v. Löwis18e16552006-02-15 17:27:45 +00001113{
1114 size_t bytes = ival;
1115 int one = 1;
Martin v. Löwis9f2e3462007-07-21 17:22:18 +00001116 if (ival < PyLong_BASE)
Guido van Rossumddefaf32007-01-14 03:31:43 +00001117 return PyLong_FromLong(ival);
Martin v. Löwis18e16552006-02-15 17:27:45 +00001118 return _PyLong_FromByteArray(
1119 (unsigned char *)&bytes,
1120 SIZEOF_SIZE_T, IS_LITTLE_ENDIAN, 0);
1121}
1122
Martin v. Löwisb9a0f912003-03-29 10:06:18 +00001123/* Get a C PY_LONG_LONG int from a long int object.
Tim Petersd1a7da62001-06-13 00:35:57 +00001124 Return -1 and set an error if overflow occurs. */
Guido van Rossum1a8791e1998-08-04 22:46:29 +00001125
Martin v. Löwisb9a0f912003-03-29 10:06:18 +00001126PY_LONG_LONG
Tim Peters9f688bf2000-07-07 15:53:28 +00001127PyLong_AsLongLong(PyObject *vv)
Guido van Rossum1a8791e1998-08-04 22:46:29 +00001128{
Guido van Rossumddefaf32007-01-14 03:31:43 +00001129 PyLongObject *v;
Martin v. Löwisb9a0f912003-03-29 10:06:18 +00001130 PY_LONG_LONG bytes;
Tim Petersd1a7da62001-06-13 00:35:57 +00001131 int one = 1;
1132 int res;
1133
Tim Petersd38b1c72001-09-30 05:09:37 +00001134 if (vv == NULL) {
1135 PyErr_BadInternalCall();
1136 return -1;
1137 }
1138 if (!PyLong_Check(vv)) {
Martin v. Löwis6ce7ed22005-03-03 12:26:35 +00001139 PyNumberMethods *nb;
1140 PyObject *io;
Martin v. Löwis6ce7ed22005-03-03 12:26:35 +00001141 if ((nb = vv->ob_type->tp_as_number) == NULL ||
1142 nb->nb_int == NULL) {
1143 PyErr_SetString(PyExc_TypeError, "an integer is required");
1144 return -1;
1145 }
1146 io = (*nb->nb_int) (vv);
1147 if (io == NULL)
1148 return -1;
Martin v. Löwis6ce7ed22005-03-03 12:26:35 +00001149 if (PyLong_Check(io)) {
1150 bytes = PyLong_AsLongLong(io);
1151 Py_DECREF(io);
1152 return bytes;
1153 }
1154 Py_DECREF(io);
1155 PyErr_SetString(PyExc_TypeError, "integer conversion failed");
Guido van Rossum1a8791e1998-08-04 22:46:29 +00001156 return -1;
1157 }
1158
Guido van Rossumddefaf32007-01-14 03:31:43 +00001159 v = (PyLongObject*)vv;
Christian Heimes90aa7642007-12-19 02:45:37 +00001160 switch(Py_SIZE(v)) {
Guido van Rossumddefaf32007-01-14 03:31:43 +00001161 case -1: return -v->ob_digit[0];
1162 case 0: return 0;
1163 case 1: return v->ob_digit[0];
1164 }
Tim Petersd1a7da62001-06-13 00:35:57 +00001165 res = _PyLong_AsByteArray(
1166 (PyLongObject *)vv, (unsigned char *)&bytes,
1167 SIZEOF_LONG_LONG, IS_LITTLE_ENDIAN, 1);
Guido van Rossum1a8791e1998-08-04 22:46:29 +00001168
Martin v. Löwisb9a0f912003-03-29 10:06:18 +00001169 /* Plan 9 can't handle PY_LONG_LONG in ? : expressions */
Martin v. Löwisc8bb9eb2002-03-09 12:02:59 +00001170 if (res < 0)
Martin v. Löwisb9a0f912003-03-29 10:06:18 +00001171 return (PY_LONG_LONG)-1;
Martin v. Löwisc8bb9eb2002-03-09 12:02:59 +00001172 else
1173 return bytes;
Guido van Rossum1a8791e1998-08-04 22:46:29 +00001174}
1175
Martin v. Löwisb9a0f912003-03-29 10:06:18 +00001176/* Get a C unsigned PY_LONG_LONG int from a long int object.
Tim Petersd1a7da62001-06-13 00:35:57 +00001177 Return -1 and set an error if overflow occurs. */
1178
Martin v. Löwisb9a0f912003-03-29 10:06:18 +00001179unsigned PY_LONG_LONG
Tim Peters9f688bf2000-07-07 15:53:28 +00001180PyLong_AsUnsignedLongLong(PyObject *vv)
Guido van Rossum1a8791e1998-08-04 22:46:29 +00001181{
Guido van Rossumddefaf32007-01-14 03:31:43 +00001182 PyLongObject *v;
Martin v. Löwisb9a0f912003-03-29 10:06:18 +00001183 unsigned PY_LONG_LONG bytes;
Tim Petersd1a7da62001-06-13 00:35:57 +00001184 int one = 1;
1185 int res;
1186
Guido van Rossum1a8791e1998-08-04 22:46:29 +00001187 if (vv == NULL || !PyLong_Check(vv)) {
1188 PyErr_BadInternalCall();
Thomas Wouters49fd7fa2006-04-21 10:40:58 +00001189 return (unsigned PY_LONG_LONG)-1;
Guido van Rossum1a8791e1998-08-04 22:46:29 +00001190 }
1191
Guido van Rossumddefaf32007-01-14 03:31:43 +00001192 v = (PyLongObject*)vv;
Christian Heimes90aa7642007-12-19 02:45:37 +00001193 switch(Py_SIZE(v)) {
Guido van Rossumddefaf32007-01-14 03:31:43 +00001194 case 0: return 0;
1195 case 1: return v->ob_digit[0];
1196 }
1197
Tim Petersd1a7da62001-06-13 00:35:57 +00001198 res = _PyLong_AsByteArray(
1199 (PyLongObject *)vv, (unsigned char *)&bytes,
1200 SIZEOF_LONG_LONG, IS_LITTLE_ENDIAN, 0);
Guido van Rossum1a8791e1998-08-04 22:46:29 +00001201
Martin v. Löwisb9a0f912003-03-29 10:06:18 +00001202 /* Plan 9 can't handle PY_LONG_LONG in ? : expressions */
Martin v. Löwisc8bb9eb2002-03-09 12:02:59 +00001203 if (res < 0)
Martin v. Löwisb9a0f912003-03-29 10:06:18 +00001204 return (unsigned PY_LONG_LONG)res;
Martin v. Löwisc8bb9eb2002-03-09 12:02:59 +00001205 else
1206 return bytes;
Guido van Rossum1a8791e1998-08-04 22:46:29 +00001207}
Tim Petersd1a7da62001-06-13 00:35:57 +00001208
Thomas Hellera4ea6032003-04-17 18:55:45 +00001209/* Get a C unsigned long int from a long int object, ignoring the high bits.
1210 Returns -1 and sets an error condition if an error occurs. */
1211
Guido van Rossumddefaf32007-01-14 03:31:43 +00001212static unsigned PY_LONG_LONG
1213_PyLong_AsUnsignedLongLongMask(PyObject *vv)
Thomas Hellera4ea6032003-04-17 18:55:45 +00001214{
1215 register PyLongObject *v;
1216 unsigned PY_LONG_LONG x;
Martin v. Löwis18e16552006-02-15 17:27:45 +00001217 Py_ssize_t i;
1218 int sign;
Thomas Hellera4ea6032003-04-17 18:55:45 +00001219
1220 if (vv == NULL || !PyLong_Check(vv)) {
1221 PyErr_BadInternalCall();
1222 return (unsigned long) -1;
1223 }
1224 v = (PyLongObject *)vv;
Christian Heimes90aa7642007-12-19 02:45:37 +00001225 switch(Py_SIZE(v)) {
Guido van Rossumddefaf32007-01-14 03:31:43 +00001226 case 0: return 0;
1227 case 1: return v->ob_digit[0];
1228 }
Christian Heimes90aa7642007-12-19 02:45:37 +00001229 i = Py_SIZE(v);
Thomas Hellera4ea6032003-04-17 18:55:45 +00001230 sign = 1;
1231 x = 0;
1232 if (i < 0) {
1233 sign = -1;
1234 i = -i;
1235 }
1236 while (--i >= 0) {
Martin v. Löwis9f2e3462007-07-21 17:22:18 +00001237 x = (x << PyLong_SHIFT) + v->ob_digit[i];
Thomas Hellera4ea6032003-04-17 18:55:45 +00001238 }
1239 return x * sign;
1240}
Guido van Rossumddefaf32007-01-14 03:31:43 +00001241
1242unsigned PY_LONG_LONG
1243PyLong_AsUnsignedLongLongMask(register PyObject *op)
1244{
1245 PyNumberMethods *nb;
1246 PyLongObject *lo;
1247 unsigned PY_LONG_LONG val;
1248
1249 if (op && PyLong_Check(op))
1250 return _PyLong_AsUnsignedLongLongMask(op);
1251
1252 if (op == NULL || (nb = op->ob_type->tp_as_number) == NULL ||
1253 nb->nb_int == NULL) {
1254 PyErr_SetString(PyExc_TypeError, "an integer is required");
1255 return (unsigned PY_LONG_LONG)-1;
1256 }
1257
1258 lo = (PyLongObject*) (*nb->nb_int) (op);
1259 if (lo == NULL)
1260 return (unsigned PY_LONG_LONG)-1;
1261 if (PyLong_Check(lo)) {
1262 val = _PyLong_AsUnsignedLongLongMask((PyObject *)lo);
1263 Py_DECREF(lo);
1264 if (PyErr_Occurred())
1265 return (unsigned PY_LONG_LONG)-1;
1266 return val;
1267 }
1268 else
1269 {
1270 Py_DECREF(lo);
1271 PyErr_SetString(PyExc_TypeError,
1272 "nb_int should return int object");
1273 return (unsigned PY_LONG_LONG)-1;
1274 }
1275}
Tim Petersd1a7da62001-06-13 00:35:57 +00001276#undef IS_LITTLE_ENDIAN
1277
Guido van Rossum1a8791e1998-08-04 22:46:29 +00001278#endif /* HAVE_LONG_LONG */
1279
Martin v. Löwisda86fcc2007-09-10 07:59:54 +00001280#define CHECK_BINOP(v,w) \
1281 if (!PyLong_Check(v) || !PyLong_Check(w)) { \
Neil Schemenauerba872e22001-01-04 01:46:03 +00001282 Py_INCREF(Py_NotImplemented); \
1283 return Py_NotImplemented; \
1284 }
1285
Tim Peters877a2122002-08-12 05:09:36 +00001286/* x[0:m] and y[0:n] are digit vectors, LSD first, m >= n required. x[0:n]
1287 * is modified in place, by adding y to it. Carries are propagated as far as
1288 * x[m-1], and the remaining carry (0 or 1) is returned.
1289 */
1290static digit
Martin v. Löwis18e16552006-02-15 17:27:45 +00001291v_iadd(digit *x, Py_ssize_t m, digit *y, Py_ssize_t n)
Tim Peters877a2122002-08-12 05:09:36 +00001292{
1293 int i;
1294 digit carry = 0;
1295
1296 assert(m >= n);
1297 for (i = 0; i < n; ++i) {
1298 carry += x[i] + y[i];
Martin v. Löwis9f2e3462007-07-21 17:22:18 +00001299 x[i] = carry & PyLong_MASK;
1300 carry >>= PyLong_SHIFT;
Tim Peters877a2122002-08-12 05:09:36 +00001301 assert((carry & 1) == carry);
1302 }
1303 for (; carry && i < m; ++i) {
1304 carry += x[i];
Martin v. Löwis9f2e3462007-07-21 17:22:18 +00001305 x[i] = carry & PyLong_MASK;
1306 carry >>= PyLong_SHIFT;
Tim Peters877a2122002-08-12 05:09:36 +00001307 assert((carry & 1) == carry);
1308 }
1309 return carry;
1310}
1311
1312/* x[0:m] and y[0:n] are digit vectors, LSD first, m >= n required. x[0:n]
1313 * is modified in place, by subtracting y from it. Borrows are propagated as
1314 * far as x[m-1], and the remaining borrow (0 or 1) is returned.
1315 */
1316static digit
Martin v. Löwis18e16552006-02-15 17:27:45 +00001317v_isub(digit *x, Py_ssize_t m, digit *y, Py_ssize_t n)
Tim Peters877a2122002-08-12 05:09:36 +00001318{
1319 int i;
1320 digit borrow = 0;
1321
1322 assert(m >= n);
1323 for (i = 0; i < n; ++i) {
1324 borrow = x[i] - y[i] - borrow;
Martin v. Löwis9f2e3462007-07-21 17:22:18 +00001325 x[i] = borrow & PyLong_MASK;
1326 borrow >>= PyLong_SHIFT;
Tim Peters877a2122002-08-12 05:09:36 +00001327 borrow &= 1; /* keep only 1 sign bit */
1328 }
1329 for (; borrow && i < m; ++i) {
1330 borrow = x[i] - borrow;
Martin v. Löwis9f2e3462007-07-21 17:22:18 +00001331 x[i] = borrow & PyLong_MASK;
1332 borrow >>= PyLong_SHIFT;
Tim Peters877a2122002-08-12 05:09:36 +00001333 borrow &= 1;
1334 }
1335 return borrow;
1336}
Neil Schemenauerba872e22001-01-04 01:46:03 +00001337
Guido van Rossumedcc38a1991-05-05 20:09:44 +00001338/* Multiply by a single digit, ignoring the sign. */
1339
Guido van Rossumc0b618a1997-05-02 03:12:38 +00001340static PyLongObject *
Tim Peters9f688bf2000-07-07 15:53:28 +00001341mul1(PyLongObject *a, wdigit n)
Guido van Rossumedcc38a1991-05-05 20:09:44 +00001342{
1343 return muladd1(a, n, (digit)0);
1344}
1345
1346/* Multiply by a single digit and add a single digit, ignoring the sign. */
1347
Guido van Rossumc0b618a1997-05-02 03:12:38 +00001348static PyLongObject *
Tim Peters9f688bf2000-07-07 15:53:28 +00001349muladd1(PyLongObject *a, wdigit n, wdigit extra)
Guido van Rossumedcc38a1991-05-05 20:09:44 +00001350{
Christian Heimes90aa7642007-12-19 02:45:37 +00001351 Py_ssize_t size_a = ABS(Py_SIZE(a));
Guido van Rossumc0b618a1997-05-02 03:12:38 +00001352 PyLongObject *z = _PyLong_New(size_a+1);
Guido van Rossumedcc38a1991-05-05 20:09:44 +00001353 twodigits carry = extra;
Martin v. Löwis18e16552006-02-15 17:27:45 +00001354 Py_ssize_t i;
Tim Peters5af4e6c2002-08-12 02:31:19 +00001355
Guido van Rossumedcc38a1991-05-05 20:09:44 +00001356 if (z == NULL)
1357 return NULL;
1358 for (i = 0; i < size_a; ++i) {
1359 carry += (twodigits)a->ob_digit[i] * n;
Martin v. Löwis9f2e3462007-07-21 17:22:18 +00001360 z->ob_digit[i] = (digit) (carry & PyLong_MASK);
1361 carry >>= PyLong_SHIFT;
Guido van Rossumedcc38a1991-05-05 20:09:44 +00001362 }
Guido van Rossum2095d241997-04-09 19:41:24 +00001363 z->ob_digit[i] = (digit) carry;
Guido van Rossumedcc38a1991-05-05 20:09:44 +00001364 return long_normalize(z);
1365}
1366
Tim Peters212e6142001-07-14 12:23:19 +00001367/* Divide long pin, w/ size digits, by non-zero digit n, storing quotient
1368 in pout, and returning the remainder. pin and pout point at the LSD.
1369 It's OK for pin == pout on entry, which saves oodles of mallocs/frees in
Guido van Rossumcd16bf62007-06-13 18:07:49 +00001370 _PyLong_Format, but that should be done with great care since longs are
Tim Peters212e6142001-07-14 12:23:19 +00001371 immutable. */
1372
1373static digit
Martin v. Löwis18e16552006-02-15 17:27:45 +00001374inplace_divrem1(digit *pout, digit *pin, Py_ssize_t size, digit n)
Tim Peters212e6142001-07-14 12:23:19 +00001375{
1376 twodigits rem = 0;
1377
Martin v. Löwis9f2e3462007-07-21 17:22:18 +00001378 assert(n > 0 && n <= PyLong_MASK);
Tim Peters212e6142001-07-14 12:23:19 +00001379 pin += size;
1380 pout += size;
1381 while (--size >= 0) {
1382 digit hi;
Martin v. Löwis9f2e3462007-07-21 17:22:18 +00001383 rem = (rem << PyLong_SHIFT) + *--pin;
Tim Peters212e6142001-07-14 12:23:19 +00001384 *--pout = hi = (digit)(rem / n);
1385 rem -= hi * n;
1386 }
1387 return (digit)rem;
1388}
1389
Guido van Rossumedcc38a1991-05-05 20:09:44 +00001390/* Divide a long integer by a digit, returning both the quotient
1391 (as function result) and the remainder (through *prem).
1392 The sign of a is ignored; n should not be zero. */
1393
Guido van Rossumc0b618a1997-05-02 03:12:38 +00001394static PyLongObject *
Tim Peters212e6142001-07-14 12:23:19 +00001395divrem1(PyLongObject *a, digit n, digit *prem)
Guido van Rossumedcc38a1991-05-05 20:09:44 +00001396{
Christian Heimes90aa7642007-12-19 02:45:37 +00001397 const Py_ssize_t size = ABS(Py_SIZE(a));
Guido van Rossumc0b618a1997-05-02 03:12:38 +00001398 PyLongObject *z;
Tim Peters5af4e6c2002-08-12 02:31:19 +00001399
Martin v. Löwis9f2e3462007-07-21 17:22:18 +00001400 assert(n > 0 && n <= PyLong_MASK);
Guido van Rossumc0b618a1997-05-02 03:12:38 +00001401 z = _PyLong_New(size);
Guido van Rossumedcc38a1991-05-05 20:09:44 +00001402 if (z == NULL)
1403 return NULL;
Tim Peters212e6142001-07-14 12:23:19 +00001404 *prem = inplace_divrem1(z->ob_digit, a->ob_digit, size, n);
Guido van Rossumedcc38a1991-05-05 20:09:44 +00001405 return long_normalize(z);
1406}
1407
1408/* Convert a long int object to a string, using a given conversion base.
Guido van Rossum3d3037d1991-10-24 14:55:57 +00001409 Return a string object.
Guido van Rossumcd16bf62007-06-13 18:07:49 +00001410 If base is 2, 8 or 16, add the proper prefix '0b', '0o' or '0x'. */
Guido van Rossumedcc38a1991-05-05 20:09:44 +00001411
Guido van Rossumcd16bf62007-06-13 18:07:49 +00001412PyObject *
1413_PyLong_Format(PyObject *aa, int base)
Guido van Rossumedcc38a1991-05-05 20:09:44 +00001414{
Guido van Rossumc0b618a1997-05-02 03:12:38 +00001415 register PyLongObject *a = (PyLongObject *)aa;
Walter Dörwald1ab83302007-05-18 17:15:44 +00001416 PyObject *str;
Thomas Wouters89f507f2006-12-13 04:49:30 +00001417 Py_ssize_t i, j, sz;
Thomas Wouters0e3f5912006-08-11 14:57:12 +00001418 Py_ssize_t size_a;
Walter Dörwald1ab83302007-05-18 17:15:44 +00001419 Py_UNICODE *p;
Guido van Rossumedcc38a1991-05-05 20:09:44 +00001420 int bits;
1421 char sign = '\0';
Guido van Rossume32e0141992-01-19 16:31:05 +00001422
Guido van Rossumc0b618a1997-05-02 03:12:38 +00001423 if (a == NULL || !PyLong_Check(a)) {
1424 PyErr_BadInternalCall();
Guido van Rossume32e0141992-01-19 16:31:05 +00001425 return NULL;
1426 }
Guido van Rossumedcc38a1991-05-05 20:09:44 +00001427 assert(base >= 2 && base <= 36);
Christian Heimes90aa7642007-12-19 02:45:37 +00001428 size_a = ABS(Py_SIZE(a));
Tim Peters5af4e6c2002-08-12 02:31:19 +00001429
Guido van Rossumedcc38a1991-05-05 20:09:44 +00001430 /* Compute a rough upper bound for the length of the string */
1431 i = base;
1432 bits = 0;
1433 while (i > 1) {
1434 ++bits;
1435 i >>= 1;
1436 }
Thomas Wouters89f507f2006-12-13 04:49:30 +00001437 i = 5;
Martin v. Löwis9f2e3462007-07-21 17:22:18 +00001438 j = size_a*PyLong_SHIFT + bits-1;
Thomas Wouters89f507f2006-12-13 04:49:30 +00001439 sz = i + j / bits;
Martin v. Löwis9f2e3462007-07-21 17:22:18 +00001440 if (j / PyLong_SHIFT < size_a || sz < i) {
Thomas Wouters89f507f2006-12-13 04:49:30 +00001441 PyErr_SetString(PyExc_OverflowError,
Guido van Rossumddefaf32007-01-14 03:31:43 +00001442 "int is too large to format");
Thomas Wouters89f507f2006-12-13 04:49:30 +00001443 return NULL;
1444 }
Walter Dörwald1ab83302007-05-18 17:15:44 +00001445 str = PyUnicode_FromUnicode(NULL, sz);
Guido van Rossumedcc38a1991-05-05 20:09:44 +00001446 if (str == NULL)
1447 return NULL;
Walter Dörwald1ab83302007-05-18 17:15:44 +00001448 p = PyUnicode_AS_UNICODE(str) + sz;
Guido van Rossumedcc38a1991-05-05 20:09:44 +00001449 *p = '\0';
Christian Heimes90aa7642007-12-19 02:45:37 +00001450 if (Py_SIZE(a) < 0)
Guido van Rossum4c260ff1992-01-14 18:36:43 +00001451 sign = '-';
Tim Peters5af4e6c2002-08-12 02:31:19 +00001452
Christian Heimes90aa7642007-12-19 02:45:37 +00001453 if (Py_SIZE(a) == 0) {
Guido van Rossumbd3a5271998-08-11 15:04:47 +00001454 *--p = '0';
1455 }
1456 else if ((base & (base - 1)) == 0) {
1457 /* JRH: special case for power-of-2 bases */
Tim Peters586b2e32001-07-15 09:11:14 +00001458 twodigits accum = 0;
1459 int accumbits = 0; /* # of bits in accum */
1460 int basebits = 1; /* # of bits in base-1 */
Guido van Rossumbd3a5271998-08-11 15:04:47 +00001461 i = base;
Tim Peters7d3a5112000-07-08 04:17:21 +00001462 while ((i >>= 1) > 1)
1463 ++basebits;
Tim Peters586b2e32001-07-15 09:11:14 +00001464
1465 for (i = 0; i < size_a; ++i) {
Tim Peters0d2d87d2002-08-20 19:00:22 +00001466 accum |= (twodigits)a->ob_digit[i] << accumbits;
Martin v. Löwis9f2e3462007-07-21 17:22:18 +00001467 accumbits += PyLong_SHIFT;
Tim Peters586b2e32001-07-15 09:11:14 +00001468 assert(accumbits >= basebits);
1469 do {
Martin v. Löwisa5854c22002-02-16 23:39:10 +00001470 char cdigit = (char)(accum & (base - 1));
Raymond Hettinger3296e692005-06-29 23:29:56 +00001471 cdigit += (cdigit < 10) ? '0' : 'a'-10;
Walter Dörwald1ab83302007-05-18 17:15:44 +00001472 assert(p > PyUnicode_AS_UNICODE(str));
Martin v. Löwisa5854c22002-02-16 23:39:10 +00001473 *--p = cdigit;
Tim Peters586b2e32001-07-15 09:11:14 +00001474 accumbits -= basebits;
1475 accum >>= basebits;
1476 } while (i < size_a-1 ? accumbits >= basebits :
1477 accum > 0);
Guido van Rossumedcc38a1991-05-05 20:09:44 +00001478 }
Guido van Rossumbd3a5271998-08-11 15:04:47 +00001479 }
1480 else {
Tim Petersfad225f2001-07-13 02:59:26 +00001481 /* Not 0, and base not a power of 2. Divide repeatedly by
1482 base, but for speed use the highest power of base that
1483 fits in a digit. */
Martin v. Löwis18e16552006-02-15 17:27:45 +00001484 Py_ssize_t size = size_a;
Tim Peters212e6142001-07-14 12:23:19 +00001485 digit *pin = a->ob_digit;
1486 PyLongObject *scratch;
1487 /* powbasw <- largest power of base that fits in a digit. */
Tim Petersfad225f2001-07-13 02:59:26 +00001488 digit powbase = base; /* powbase == base ** power */
1489 int power = 1;
1490 for (;;) {
1491 unsigned long newpow = powbase * (unsigned long)base;
Martin v. Löwis9f2e3462007-07-21 17:22:18 +00001492 if (newpow >> PyLong_SHIFT) /* doesn't fit in a digit */
Tim Petersfad225f2001-07-13 02:59:26 +00001493 break;
1494 powbase = (digit)newpow;
1495 ++power;
1496 }
Tim Peters212e6142001-07-14 12:23:19 +00001497
1498 /* Get a scratch area for repeated division. */
1499 scratch = _PyLong_New(size);
1500 if (scratch == NULL) {
1501 Py_DECREF(str);
1502 return NULL;
1503 }
1504
1505 /* Repeatedly divide by powbase. */
Guido van Rossumbd3a5271998-08-11 15:04:47 +00001506 do {
Tim Petersfad225f2001-07-13 02:59:26 +00001507 int ntostore = power;
Tim Peters212e6142001-07-14 12:23:19 +00001508 digit rem = inplace_divrem1(scratch->ob_digit,
1509 pin, size, powbase);
1510 pin = scratch->ob_digit; /* no need to use a again */
1511 if (pin[size - 1] == 0)
1512 --size;
Guido van Rossumbd3a5271998-08-11 15:04:47 +00001513 SIGCHECK({
Tim Peters212e6142001-07-14 12:23:19 +00001514 Py_DECREF(scratch);
Guido van Rossumbd3a5271998-08-11 15:04:47 +00001515 Py_DECREF(str);
1516 return NULL;
1517 })
Tim Peters212e6142001-07-14 12:23:19 +00001518
1519 /* Break rem into digits. */
Tim Petersc8a6b9b2001-07-14 11:01:28 +00001520 assert(ntostore > 0);
1521 do {
Tim Petersfad225f2001-07-13 02:59:26 +00001522 digit nextrem = (digit)(rem / base);
1523 char c = (char)(rem - nextrem * base);
Walter Dörwald1ab83302007-05-18 17:15:44 +00001524 assert(p > PyUnicode_AS_UNICODE(str));
Raymond Hettinger3296e692005-06-29 23:29:56 +00001525 c += (c < 10) ? '0' : 'a'-10;
Tim Petersfad225f2001-07-13 02:59:26 +00001526 *--p = c;
1527 rem = nextrem;
Tim Petersc8a6b9b2001-07-14 11:01:28 +00001528 --ntostore;
1529 /* Termination is a bit delicate: must not
1530 store leading zeroes, so must get out if
Tim Peters212e6142001-07-14 12:23:19 +00001531 remaining quotient and rem are both 0. */
1532 } while (ntostore && (size || rem));
1533 } while (size != 0);
1534 Py_DECREF(scratch);
Guido van Rossumbd3a5271998-08-11 15:04:47 +00001535 }
1536
Guido van Rossumcd16bf62007-06-13 18:07:49 +00001537 if (base == 16) {
Guido van Rossum3d3037d1991-10-24 14:55:57 +00001538 *--p = 'x';
1539 *--p = '0';
1540 }
Guido van Rossumcd16bf62007-06-13 18:07:49 +00001541 else if (base == 8) {
1542 *--p = 'o';
1543 *--p = '0';
1544 }
1545 else if (base == 2) {
1546 *--p = 'b';
1547 *--p = '0';
1548 }
Guido van Rossumc6913e71991-11-19 20:26:46 +00001549 else if (base != 10) {
1550 *--p = '#';
1551 *--p = '0' + base%10;
1552 if (base > 10)
1553 *--p = '0' + base/10;
1554 }
Guido van Rossumedcc38a1991-05-05 20:09:44 +00001555 if (sign)
1556 *--p = sign;
Walter Dörwald1ab83302007-05-18 17:15:44 +00001557 if (p != PyUnicode_AS_UNICODE(str)) {
1558 Py_UNICODE *q = PyUnicode_AS_UNICODE(str);
Guido van Rossumedcc38a1991-05-05 20:09:44 +00001559 assert(p > q);
1560 do {
1561 } while ((*q++ = *p++) != '\0');
Guido van Rossumc7ec9c91991-05-28 21:58:16 +00001562 q--;
Walter Dörwald1ab83302007-05-18 17:15:44 +00001563 if (PyUnicode_Resize(&str, (Py_ssize_t) (q - PyUnicode_AS_UNICODE(str)))) {
1564 Py_DECREF(str);
1565 return NULL;
1566 }
Guido van Rossumedcc38a1991-05-05 20:09:44 +00001567 }
Guido van Rossumc0b618a1997-05-02 03:12:38 +00001568 return (PyObject *)str;
Guido van Rossumedcc38a1991-05-05 20:09:44 +00001569}
1570
Thomas Wouters477c8d52006-05-27 19:21:47 +00001571/* Table of digit values for 8-bit string -> integer conversion.
1572 * '0' maps to 0, ..., '9' maps to 9.
1573 * 'a' and 'A' map to 10, ..., 'z' and 'Z' map to 35.
1574 * All other indices map to 37.
1575 * Note that when converting a base B string, a char c is a legitimate
Martin v. Löwis9f2e3462007-07-21 17:22:18 +00001576 * base B digit iff _PyLong_DigitValue[Py_CHARPyLong_MASK(c)] < B.
Thomas Wouters477c8d52006-05-27 19:21:47 +00001577 */
1578int _PyLong_DigitValue[256] = {
1579 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37,
1580 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37,
1581 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37,
1582 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 37, 37, 37, 37, 37, 37,
1583 37, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24,
1584 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 37, 37, 37, 37, 37,
1585 37, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24,
1586 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 37, 37, 37, 37, 37,
1587 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37,
1588 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37,
1589 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37,
1590 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37,
1591 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37,
1592 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37,
1593 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37,
1594 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37,
1595};
1596
1597/* *str points to the first digit in a string of base `base` digits. base
Tim Petersbf2674b2003-02-02 07:51:32 +00001598 * is a power of 2 (2, 4, 8, 16, or 32). *str is set to point to the first
1599 * non-digit (which may be *str!). A normalized long is returned.
1600 * The point to this routine is that it takes time linear in the number of
1601 * string characters.
1602 */
1603static PyLongObject *
1604long_from_binary_base(char **str, int base)
1605{
1606 char *p = *str;
1607 char *start = p;
1608 int bits_per_char;
Martin v. Löwis18e16552006-02-15 17:27:45 +00001609 Py_ssize_t n;
Tim Petersbf2674b2003-02-02 07:51:32 +00001610 PyLongObject *z;
1611 twodigits accum;
1612 int bits_in_accum;
1613 digit *pdigit;
1614
1615 assert(base >= 2 && base <= 32 && (base & (base - 1)) == 0);
1616 n = base;
1617 for (bits_per_char = -1; n; ++bits_per_char)
1618 n >>= 1;
1619 /* n <- total # of bits needed, while setting p to end-of-string */
1620 n = 0;
Thomas Wouters477c8d52006-05-27 19:21:47 +00001621 while (_PyLong_DigitValue[Py_CHARMASK(*p)] < base)
Tim Petersbf2674b2003-02-02 07:51:32 +00001622 ++p;
Tim Petersbf2674b2003-02-02 07:51:32 +00001623 *str = p;
Martin v. Löwis9f2e3462007-07-21 17:22:18 +00001624 /* n <- # of Python digits needed, = ceiling(n/PyLong_SHIFT). */
1625 n = (p - start) * bits_per_char + PyLong_SHIFT - 1;
Thomas Wouters89f507f2006-12-13 04:49:30 +00001626 if (n / bits_per_char < p - start) {
Tim Peters1a3b19a2003-02-02 17:33:53 +00001627 PyErr_SetString(PyExc_ValueError,
Guido van Rossumddefaf32007-01-14 03:31:43 +00001628 "int string too large to convert");
Tim Peters1a3b19a2003-02-02 17:33:53 +00001629 return NULL;
1630 }
Martin v. Löwis9f2e3462007-07-21 17:22:18 +00001631 n = n / PyLong_SHIFT;
Tim Petersbf2674b2003-02-02 07:51:32 +00001632 z = _PyLong_New(n);
1633 if (z == NULL)
1634 return NULL;
1635 /* Read string from right, and fill in long from left; i.e.,
1636 * from least to most significant in both.
1637 */
1638 accum = 0;
1639 bits_in_accum = 0;
1640 pdigit = z->ob_digit;
1641 while (--p >= start) {
Thomas Wouters477c8d52006-05-27 19:21:47 +00001642 int k = _PyLong_DigitValue[Py_CHARMASK(*p)];
Tim Petersc7bc0b92003-05-05 20:39:43 +00001643 assert(k >= 0 && k < base);
1644 accum |= (twodigits)(k << bits_in_accum);
Tim Petersbf2674b2003-02-02 07:51:32 +00001645 bits_in_accum += bits_per_char;
Martin v. Löwis9f2e3462007-07-21 17:22:18 +00001646 if (bits_in_accum >= PyLong_SHIFT) {
1647 *pdigit++ = (digit)(accum & PyLong_MASK);
Martin v. Löwis18e16552006-02-15 17:27:45 +00001648 assert(pdigit - z->ob_digit <= (int)n);
Martin v. Löwis9f2e3462007-07-21 17:22:18 +00001649 accum >>= PyLong_SHIFT;
1650 bits_in_accum -= PyLong_SHIFT;
1651 assert(bits_in_accum < PyLong_SHIFT);
Tim Petersbf2674b2003-02-02 07:51:32 +00001652 }
1653 }
1654 if (bits_in_accum) {
Martin v. Löwis9f2e3462007-07-21 17:22:18 +00001655 assert(bits_in_accum <= PyLong_SHIFT);
Tim Petersbf2674b2003-02-02 07:51:32 +00001656 *pdigit++ = (digit)accum;
Martin v. Löwis18e16552006-02-15 17:27:45 +00001657 assert(pdigit - z->ob_digit <= (int)n);
Tim Petersbf2674b2003-02-02 07:51:32 +00001658 }
1659 while (pdigit - z->ob_digit < n)
1660 *pdigit++ = 0;
1661 return long_normalize(z);
1662}
1663
Guido van Rossumc0b618a1997-05-02 03:12:38 +00001664PyObject *
Tim Peters9f688bf2000-07-07 15:53:28 +00001665PyLong_FromString(char *str, char **pend, int base)
Guido van Rossumeb1fafc1994-08-29 12:47:19 +00001666{
Guido van Rossumcd16bf62007-06-13 18:07:49 +00001667 int sign = 1, error_if_nonzero = 0;
Guido van Rossum9e896b32000-04-05 20:11:21 +00001668 char *start, *orig_str = str;
Guido van Rossumcd16bf62007-06-13 18:07:49 +00001669 PyLongObject *z = NULL;
Guido van Rossum25236212007-08-22 23:28:23 +00001670 PyObject *strobj;
Thomas Wouters49fd7fa2006-04-21 10:40:58 +00001671 Py_ssize_t slen;
Tim Peters5af4e6c2002-08-12 02:31:19 +00001672
Guido van Rossum472c04f1996-12-05 21:57:21 +00001673 if ((base != 0 && base < 2) || base > 36) {
Guido van Rossumc0b618a1997-05-02 03:12:38 +00001674 PyErr_SetString(PyExc_ValueError,
Guido van Rossumddefaf32007-01-14 03:31:43 +00001675 "int() arg 2 must be >= 2 and <= 36");
Guido van Rossumeb1fafc1994-08-29 12:47:19 +00001676 return NULL;
1677 }
Guido van Rossum9fa2c111995-02-10 17:00:37 +00001678 while (*str != '\0' && isspace(Py_CHARMASK(*str)))
Guido van Rossumeb1fafc1994-08-29 12:47:19 +00001679 str++;
Guido van Rossumedcc38a1991-05-05 20:09:44 +00001680 if (*str == '+')
1681 ++str;
1682 else if (*str == '-') {
1683 ++str;
1684 sign = -1;
1685 }
Guido van Rossum9fa2c111995-02-10 17:00:37 +00001686 while (*str != '\0' && isspace(Py_CHARMASK(*str)))
Guido van Rossumeb1fafc1994-08-29 12:47:19 +00001687 str++;
Guido van Rossumedcc38a1991-05-05 20:09:44 +00001688 if (base == 0) {
1689 if (str[0] != '0')
1690 base = 10;
1691 else if (str[1] == 'x' || str[1] == 'X')
1692 base = 16;
Guido van Rossumcd16bf62007-06-13 18:07:49 +00001693 else if (str[1] == 'o' || str[1] == 'O')
Guido van Rossumedcc38a1991-05-05 20:09:44 +00001694 base = 8;
Guido van Rossumcd16bf62007-06-13 18:07:49 +00001695 else if (str[1] == 'b' || str[1] == 'B')
1696 base = 2;
1697 else {
1698 /* "old" (C-style) octal literal, now invalid.
1699 it might still be zero though */
1700 error_if_nonzero = 1;
1701 base = 10;
1702 }
Guido van Rossumedcc38a1991-05-05 20:09:44 +00001703 }
Guido van Rossumcd16bf62007-06-13 18:07:49 +00001704 if (str[0] == '0' &&
1705 ((base == 16 && (str[1] == 'x' || str[1] == 'X')) ||
1706 (base == 8 && (str[1] == 'o' || str[1] == 'O')) ||
1707 (base == 2 && (str[1] == 'b' || str[1] == 'B'))))
Guido van Rossumedcc38a1991-05-05 20:09:44 +00001708 str += 2;
Thomas Wouters477c8d52006-05-27 19:21:47 +00001709
Guido van Rossume6762971998-06-22 03:54:46 +00001710 start = str;
Tim Petersbf2674b2003-02-02 07:51:32 +00001711 if ((base & (base - 1)) == 0)
1712 z = long_from_binary_base(&str, base);
1713 else {
Thomas Wouters477c8d52006-05-27 19:21:47 +00001714/***
1715Binary bases can be converted in time linear in the number of digits, because
1716Python's representation base is binary. Other bases (including decimal!) use
1717the simple quadratic-time algorithm below, complicated by some speed tricks.
Tim Peters5af4e6c2002-08-12 02:31:19 +00001718
Thomas Wouters477c8d52006-05-27 19:21:47 +00001719First some math: the largest integer that can be expressed in N base-B digits
1720is B**N-1. Consequently, if we have an N-digit input in base B, the worst-
1721case number of Python digits needed to hold it is the smallest integer n s.t.
1722
1723 BASE**n-1 >= B**N-1 [or, adding 1 to both sides]
1724 BASE**n >= B**N [taking logs to base BASE]
1725 n >= log(B**N)/log(BASE) = N * log(B)/log(BASE)
1726
1727The static array log_base_BASE[base] == log(base)/log(BASE) so we can compute
1728this quickly. A Python long with that much space is reserved near the start,
1729and the result is computed into it.
1730
1731The input string is actually treated as being in base base**i (i.e., i digits
1732are processed at a time), where two more static arrays hold:
1733
1734 convwidth_base[base] = the largest integer i such that base**i <= BASE
1735 convmultmax_base[base] = base ** convwidth_base[base]
1736
1737The first of these is the largest i such that i consecutive input digits
1738must fit in a single Python digit. The second is effectively the input
1739base we're really using.
1740
1741Viewing the input as a sequence <c0, c1, ..., c_n-1> of digits in base
1742convmultmax_base[base], the result is "simply"
1743
1744 (((c0*B + c1)*B + c2)*B + c3)*B + ... ))) + c_n-1
1745
1746where B = convmultmax_base[base].
Thomas Wouters4d70c3d2006-06-08 14:42:34 +00001747
1748Error analysis: as above, the number of Python digits `n` needed is worst-
1749case
1750
1751 n >= N * log(B)/log(BASE)
1752
1753where `N` is the number of input digits in base `B`. This is computed via
1754
1755 size_z = (Py_ssize_t)((scan - str) * log_base_BASE[base]) + 1;
1756
1757below. Two numeric concerns are how much space this can waste, and whether
1758the computed result can be too small. To be concrete, assume BASE = 2**15,
1759which is the default (and it's unlikely anyone changes that).
1760
1761Waste isn't a problem: provided the first input digit isn't 0, the difference
1762between the worst-case input with N digits and the smallest input with N
1763digits is about a factor of B, but B is small compared to BASE so at most
1764one allocated Python digit can remain unused on that count. If
1765N*log(B)/log(BASE) is mathematically an exact integer, then truncating that
1766and adding 1 returns a result 1 larger than necessary. However, that can't
1767happen: whenever B is a power of 2, long_from_binary_base() is called
1768instead, and it's impossible for B**i to be an integer power of 2**15 when
1769B is not a power of 2 (i.e., it's impossible for N*log(B)/log(BASE) to be
1770an exact integer when B is not a power of 2, since B**i has a prime factor
1771other than 2 in that case, but (2**15)**j's only prime factor is 2).
1772
1773The computed result can be too small if the true value of N*log(B)/log(BASE)
1774is a little bit larger than an exact integer, but due to roundoff errors (in
1775computing log(B), log(BASE), their quotient, and/or multiplying that by N)
1776yields a numeric result a little less than that integer. Unfortunately, "how
1777close can a transcendental function get to an integer over some range?"
1778questions are generally theoretically intractable. Computer analysis via
1779continued fractions is practical: expand log(B)/log(BASE) via continued
1780fractions, giving a sequence i/j of "the best" rational approximations. Then
1781j*log(B)/log(BASE) is approximately equal to (the integer) i. This shows that
1782we can get very close to being in trouble, but very rarely. For example,
178376573 is a denominator in one of the continued-fraction approximations to
1784log(10)/log(2**15), and indeed:
1785
1786 >>> log(10)/log(2**15)*76573
1787 16958.000000654003
1788
1789is very close to an integer. If we were working with IEEE single-precision,
1790rounding errors could kill us. Finding worst cases in IEEE double-precision
1791requires better-than-double-precision log() functions, and Tim didn't bother.
1792Instead the code checks to see whether the allocated space is enough as each
1793new Python digit is added, and copies the whole thing to a larger long if not.
1794This should happen extremely rarely, and in fact I don't have a test case
1795that triggers it(!). Instead the code was tested by artificially allocating
1796just 1 digit at the start, so that the copying code was exercised for every
1797digit beyond the first.
Thomas Wouters477c8d52006-05-27 19:21:47 +00001798***/
1799 register twodigits c; /* current input character */
1800 Py_ssize_t size_z;
1801 int i;
1802 int convwidth;
1803 twodigits convmultmax, convmult;
1804 digit *pz, *pzstop;
1805 char* scan;
1806
1807 static double log_base_BASE[37] = {0.0e0,};
1808 static int convwidth_base[37] = {0,};
1809 static twodigits convmultmax_base[37] = {0,};
1810
1811 if (log_base_BASE[base] == 0.0) {
1812 twodigits convmax = base;
1813 int i = 1;
1814
1815 log_base_BASE[base] = log((double)base) /
Martin v. Löwis9f2e3462007-07-21 17:22:18 +00001816 log((double)PyLong_BASE);
Thomas Wouters477c8d52006-05-27 19:21:47 +00001817 for (;;) {
1818 twodigits next = convmax * base;
Martin v. Löwis9f2e3462007-07-21 17:22:18 +00001819 if (next > PyLong_BASE)
Thomas Wouters477c8d52006-05-27 19:21:47 +00001820 break;
1821 convmax = next;
1822 ++i;
1823 }
1824 convmultmax_base[base] = convmax;
1825 assert(i > 0);
1826 convwidth_base[base] = i;
1827 }
1828
1829 /* Find length of the string of numeric characters. */
1830 scan = str;
1831 while (_PyLong_DigitValue[Py_CHARMASK(*scan)] < base)
1832 ++scan;
1833
1834 /* Create a long object that can contain the largest possible
1835 * integer with this base and length. Note that there's no
1836 * need to initialize z->ob_digit -- no slot is read up before
1837 * being stored into.
1838 */
1839 size_z = (Py_ssize_t)((scan - str) * log_base_BASE[base]) + 1;
Thomas Wouters4d70c3d2006-06-08 14:42:34 +00001840 /* Uncomment next line to test exceedingly rare copy code */
1841 /* size_z = 1; */
Thomas Wouters477c8d52006-05-27 19:21:47 +00001842 assert(size_z > 0);
1843 z = _PyLong_New(size_z);
1844 if (z == NULL)
1845 return NULL;
Christian Heimes90aa7642007-12-19 02:45:37 +00001846 Py_SIZE(z) = 0;
Thomas Wouters477c8d52006-05-27 19:21:47 +00001847
1848 /* `convwidth` consecutive input digits are treated as a single
1849 * digit in base `convmultmax`.
1850 */
1851 convwidth = convwidth_base[base];
1852 convmultmax = convmultmax_base[base];
1853
1854 /* Work ;-) */
1855 while (str < scan) {
1856 /* grab up to convwidth digits from the input string */
1857 c = (digit)_PyLong_DigitValue[Py_CHARMASK(*str++)];
1858 for (i = 1; i < convwidth && str != scan; ++i, ++str) {
1859 c = (twodigits)(c * base +
1860 _PyLong_DigitValue[Py_CHARMASK(*str)]);
Martin v. Löwis9f2e3462007-07-21 17:22:18 +00001861 assert(c < PyLong_BASE);
Thomas Wouters477c8d52006-05-27 19:21:47 +00001862 }
1863
1864 convmult = convmultmax;
1865 /* Calculate the shift only if we couldn't get
1866 * convwidth digits.
1867 */
1868 if (i != convwidth) {
1869 convmult = base;
1870 for ( ; i > 1; --i)
1871 convmult *= base;
1872 }
1873
1874 /* Multiply z by convmult, and add c. */
1875 pz = z->ob_digit;
Christian Heimes90aa7642007-12-19 02:45:37 +00001876 pzstop = pz + Py_SIZE(z);
Thomas Wouters477c8d52006-05-27 19:21:47 +00001877 for (; pz < pzstop; ++pz) {
1878 c += (twodigits)*pz * convmult;
Martin v. Löwis9f2e3462007-07-21 17:22:18 +00001879 *pz = (digit)(c & PyLong_MASK);
1880 c >>= PyLong_SHIFT;
Thomas Wouters477c8d52006-05-27 19:21:47 +00001881 }
1882 /* carry off the current end? */
1883 if (c) {
Martin v. Löwis9f2e3462007-07-21 17:22:18 +00001884 assert(c < PyLong_BASE);
Christian Heimes90aa7642007-12-19 02:45:37 +00001885 if (Py_SIZE(z) < size_z) {
Thomas Wouters4d70c3d2006-06-08 14:42:34 +00001886 *pz = (digit)c;
Christian Heimes90aa7642007-12-19 02:45:37 +00001887 ++Py_SIZE(z);
Thomas Wouters4d70c3d2006-06-08 14:42:34 +00001888 }
1889 else {
1890 PyLongObject *tmp;
1891 /* Extremely rare. Get more space. */
Christian Heimes90aa7642007-12-19 02:45:37 +00001892 assert(Py_SIZE(z) == size_z);
Thomas Wouters4d70c3d2006-06-08 14:42:34 +00001893 tmp = _PyLong_New(size_z + 1);
1894 if (tmp == NULL) {
1895 Py_DECREF(z);
1896 return NULL;
1897 }
1898 memcpy(tmp->ob_digit,
1899 z->ob_digit,
1900 sizeof(digit) * size_z);
1901 Py_DECREF(z);
1902 z = tmp;
1903 z->ob_digit[size_z] = (digit)c;
1904 ++size_z;
1905 }
Thomas Wouters477c8d52006-05-27 19:21:47 +00001906 }
Tim Petersbf2674b2003-02-02 07:51:32 +00001907 }
Guido van Rossumedcc38a1991-05-05 20:09:44 +00001908 }
Guido van Rossumac6a37a1998-08-04 15:04:06 +00001909 if (z == NULL)
1910 return NULL;
Guido van Rossumcd16bf62007-06-13 18:07:49 +00001911 if (error_if_nonzero) {
1912 /* reset the base to 0, else the exception message
1913 doesn't make too much sense */
1914 base = 0;
Christian Heimes90aa7642007-12-19 02:45:37 +00001915 if (Py_SIZE(z) != 0)
Guido van Rossumcd16bf62007-06-13 18:07:49 +00001916 goto onError;
1917 /* there might still be other problems, therefore base
1918 remains zero here for the same reason */
1919 }
Guido van Rossum9e896b32000-04-05 20:11:21 +00001920 if (str == start)
1921 goto onError;
Thomas Wouters477c8d52006-05-27 19:21:47 +00001922 if (sign < 0)
Christian Heimes90aa7642007-12-19 02:45:37 +00001923 Py_SIZE(z) = -(Py_SIZE(z));
Guido van Rossum9e896b32000-04-05 20:11:21 +00001924 if (*str == 'L' || *str == 'l')
1925 str++;
1926 while (*str && isspace(Py_CHARMASK(*str)))
1927 str++;
1928 if (*str != '\0')
1929 goto onError;
Guido van Rossumeb1fafc1994-08-29 12:47:19 +00001930 if (pend)
1931 *pend = str;
Guido van Rossumc0b618a1997-05-02 03:12:38 +00001932 return (PyObject *) z;
Guido van Rossum9e896b32000-04-05 20:11:21 +00001933
1934 onError:
Guido van Rossum9e896b32000-04-05 20:11:21 +00001935 Py_XDECREF(z);
Thomas Wouters49fd7fa2006-04-21 10:40:58 +00001936 slen = strlen(orig_str) < 200 ? strlen(orig_str) : 200;
Guido van Rossum25236212007-08-22 23:28:23 +00001937 strobj = PyUnicode_FromStringAndSize(orig_str, slen);
Thomas Wouters49fd7fa2006-04-21 10:40:58 +00001938 if (strobj == NULL)
1939 return NULL;
Thomas Wouters49fd7fa2006-04-21 10:40:58 +00001940 PyErr_Format(PyExc_ValueError,
Guido van Rossum25236212007-08-22 23:28:23 +00001941 "invalid literal for int() with base %d: %R",
1942 base, strobj);
1943 Py_DECREF(strobj);
Guido van Rossum9e896b32000-04-05 20:11:21 +00001944 return NULL;
1945}
1946
1947PyObject *
Martin v. Löwis18e16552006-02-15 17:27:45 +00001948PyLong_FromUnicode(Py_UNICODE *u, Py_ssize_t length, int base)
Guido van Rossum9e896b32000-04-05 20:11:21 +00001949{
Walter Dörwald07e14762002-11-06 16:15:14 +00001950 PyObject *result;
Thomas Wouters49fd7fa2006-04-21 10:40:58 +00001951 char *buffer = (char *)PyMem_MALLOC(length+1);
Guido van Rossum9e896b32000-04-05 20:11:21 +00001952
Walter Dörwald07e14762002-11-06 16:15:14 +00001953 if (buffer == NULL)
1954 return NULL;
1955
1956 if (PyUnicode_EncodeDecimal(u, length, buffer, NULL)) {
1957 PyMem_FREE(buffer);
Guido van Rossum9e896b32000-04-05 20:11:21 +00001958 return NULL;
1959 }
Walter Dörwald07e14762002-11-06 16:15:14 +00001960 result = PyLong_FromString(buffer, NULL, base);
1961 PyMem_FREE(buffer);
1962 return result;
Guido van Rossumedcc38a1991-05-05 20:09:44 +00001963}
1964
Tim Peters9f688bf2000-07-07 15:53:28 +00001965/* forward */
Guido van Rossumc0b618a1997-05-02 03:12:38 +00001966static PyLongObject *x_divrem
Tim Peters9f688bf2000-07-07 15:53:28 +00001967 (PyLongObject *, PyLongObject *, PyLongObject **);
Guido van Rossumb43daf72007-08-01 18:08:08 +00001968static PyObject *long_long(PyObject *v);
Tim Peters9f688bf2000-07-07 15:53:28 +00001969static int long_divrem(PyLongObject *, PyLongObject *,
1970 PyLongObject **, PyLongObject **);
Guido van Rossumedcc38a1991-05-05 20:09:44 +00001971
1972/* Long division with remainder, top-level routine */
1973
Guido van Rossume32e0141992-01-19 16:31:05 +00001974static int
Tim Peters9f688bf2000-07-07 15:53:28 +00001975long_divrem(PyLongObject *a, PyLongObject *b,
1976 PyLongObject **pdiv, PyLongObject **prem)
Guido van Rossumedcc38a1991-05-05 20:09:44 +00001977{
Christian Heimes90aa7642007-12-19 02:45:37 +00001978 Py_ssize_t size_a = ABS(Py_SIZE(a)), size_b = ABS(Py_SIZE(b));
Guido van Rossumc0b618a1997-05-02 03:12:38 +00001979 PyLongObject *z;
Tim Peters5af4e6c2002-08-12 02:31:19 +00001980
Guido van Rossumedcc38a1991-05-05 20:09:44 +00001981 if (size_b == 0) {
Guido van Rossumbd3a5271998-08-11 15:04:47 +00001982 PyErr_SetString(PyExc_ZeroDivisionError,
Guido van Rossumddefaf32007-01-14 03:31:43 +00001983 "integer division or modulo by zero");
Guido van Rossume32e0141992-01-19 16:31:05 +00001984 return -1;
Guido van Rossumedcc38a1991-05-05 20:09:44 +00001985 }
1986 if (size_a < size_b ||
Guido van Rossum472c04f1996-12-05 21:57:21 +00001987 (size_a == size_b &&
1988 a->ob_digit[size_a-1] < b->ob_digit[size_b-1])) {
Guido van Rossumedcc38a1991-05-05 20:09:44 +00001989 /* |a| < |b|. */
Guido van Rossumddefaf32007-01-14 03:31:43 +00001990 *pdiv = (PyLongObject*)PyLong_FromLong(0);
Guido van Rossumd8faa362007-04-27 19:54:29 +00001991 if (*pdiv == NULL)
1992 return -1;
Guido van Rossumc0b618a1997-05-02 03:12:38 +00001993 Py_INCREF(a);
1994 *prem = (PyLongObject *) a;
Guido van Rossume32e0141992-01-19 16:31:05 +00001995 return 0;
Guido van Rossumedcc38a1991-05-05 20:09:44 +00001996 }
1997 if (size_b == 1) {
1998 digit rem = 0;
1999 z = divrem1(a, b->ob_digit[0], &rem);
Guido van Rossume32e0141992-01-19 16:31:05 +00002000 if (z == NULL)
2001 return -1;
Guido van Rossumc0b618a1997-05-02 03:12:38 +00002002 *prem = (PyLongObject *) PyLong_FromLong((long)rem);
Guido van Rossumd8faa362007-04-27 19:54:29 +00002003 if (*prem == NULL) {
2004 Py_DECREF(z);
2005 return -1;
2006 }
Guido van Rossumedcc38a1991-05-05 20:09:44 +00002007 }
Guido van Rossume32e0141992-01-19 16:31:05 +00002008 else {
Guido van Rossumedcc38a1991-05-05 20:09:44 +00002009 z = x_divrem(a, b, prem);
Guido van Rossume32e0141992-01-19 16:31:05 +00002010 if (z == NULL)
2011 return -1;
2012 }
Guido van Rossumedcc38a1991-05-05 20:09:44 +00002013 /* Set the signs.
2014 The quotient z has the sign of a*b;
2015 the remainder r has the sign of a,
2016 so a = b*z + r. */
Christian Heimes90aa7642007-12-19 02:45:37 +00002017 if ((Py_SIZE(a) < 0) != (Py_SIZE(b) < 0))
Guido van Rossumddefaf32007-01-14 03:31:43 +00002018 NEGATE(z);
Christian Heimes90aa7642007-12-19 02:45:37 +00002019 if (Py_SIZE(a) < 0 && Py_SIZE(*prem) != 0)
Guido van Rossumddefaf32007-01-14 03:31:43 +00002020 NEGATE(*prem);
Guido van Rossume32e0141992-01-19 16:31:05 +00002021 *pdiv = z;
2022 return 0;
Guido van Rossumedcc38a1991-05-05 20:09:44 +00002023}
2024
Guido van Rossum23d6f0e1991-05-14 12:06:49 +00002025/* Unsigned long division with remainder -- the algorithm */
Guido van Rossumedcc38a1991-05-05 20:09:44 +00002026
Guido van Rossumc0b618a1997-05-02 03:12:38 +00002027static PyLongObject *
Tim Peters9f688bf2000-07-07 15:53:28 +00002028x_divrem(PyLongObject *v1, PyLongObject *w1, PyLongObject **prem)
Guido van Rossumedcc38a1991-05-05 20:09:44 +00002029{
Christian Heimes90aa7642007-12-19 02:45:37 +00002030 Py_ssize_t size_v = ABS(Py_SIZE(v1)), size_w = ABS(Py_SIZE(w1));
Martin v. Löwis9f2e3462007-07-21 17:22:18 +00002031 digit d = (digit) ((twodigits)PyLong_BASE / (w1->ob_digit[size_w-1] + 1));
Guido van Rossumc0b618a1997-05-02 03:12:38 +00002032 PyLongObject *v = mul1(v1, d);
2033 PyLongObject *w = mul1(w1, d);
2034 PyLongObject *a;
Martin v. Löwis18e16552006-02-15 17:27:45 +00002035 Py_ssize_t j, k;
Tim Peters5af4e6c2002-08-12 02:31:19 +00002036
Guido van Rossumedcc38a1991-05-05 20:09:44 +00002037 if (v == NULL || w == NULL) {
Guido van Rossumc0b618a1997-05-02 03:12:38 +00002038 Py_XDECREF(v);
2039 Py_XDECREF(w);
Guido van Rossumedcc38a1991-05-05 20:09:44 +00002040 return NULL;
2041 }
Tim Peters5af4e6c2002-08-12 02:31:19 +00002042
Guido van Rossumedcc38a1991-05-05 20:09:44 +00002043 assert(size_v >= size_w && size_w > 1); /* Assert checks by div() */
Christian Heimes90aa7642007-12-19 02:45:37 +00002044 assert(Py_REFCNT(v) == 1); /* Since v will be used as accumulator! */
2045 assert(size_w == ABS(Py_SIZE(w))); /* That's how d was calculated */
Tim Peters5af4e6c2002-08-12 02:31:19 +00002046
Christian Heimes90aa7642007-12-19 02:45:37 +00002047 size_v = ABS(Py_SIZE(v));
Thomas Wouters477c8d52006-05-27 19:21:47 +00002048 k = size_v - size_w;
2049 a = _PyLong_New(k + 1);
Tim Peters5af4e6c2002-08-12 02:31:19 +00002050
Thomas Wouters477c8d52006-05-27 19:21:47 +00002051 for (j = size_v; a != NULL && k >= 0; --j, --k) {
Guido van Rossumedcc38a1991-05-05 20:09:44 +00002052 digit vj = (j >= size_v) ? 0 : v->ob_digit[j];
2053 twodigits q;
Guido van Rossum23d6f0e1991-05-14 12:06:49 +00002054 stwodigits carry = 0;
Guido van Rossumedcc38a1991-05-05 20:09:44 +00002055 int i;
Tim Peters5af4e6c2002-08-12 02:31:19 +00002056
Guido van Rossumeb1fafc1994-08-29 12:47:19 +00002057 SIGCHECK({
Guido van Rossumc0b618a1997-05-02 03:12:38 +00002058 Py_DECREF(a);
Guido van Rossumedcc38a1991-05-05 20:09:44 +00002059 a = NULL;
Guido van Rossumedcc38a1991-05-05 20:09:44 +00002060 break;
Guido van Rossum23d6f0e1991-05-14 12:06:49 +00002061 })
Guido van Rossumedcc38a1991-05-05 20:09:44 +00002062 if (vj == w->ob_digit[size_w-1])
Martin v. Löwis9f2e3462007-07-21 17:22:18 +00002063 q = PyLong_MASK;
Guido van Rossumedcc38a1991-05-05 20:09:44 +00002064 else
Martin v. Löwis9f2e3462007-07-21 17:22:18 +00002065 q = (((twodigits)vj << PyLong_SHIFT) + v->ob_digit[j-1]) /
Guido van Rossumedcc38a1991-05-05 20:09:44 +00002066 w->ob_digit[size_w-1];
Tim Peters5af4e6c2002-08-12 02:31:19 +00002067
Guido van Rossumedcc38a1991-05-05 20:09:44 +00002068 while (w->ob_digit[size_w-2]*q >
2069 ((
Martin v. Löwis9f2e3462007-07-21 17:22:18 +00002070 ((twodigits)vj << PyLong_SHIFT)
Guido van Rossumedcc38a1991-05-05 20:09:44 +00002071 + v->ob_digit[j-1]
2072 - q*w->ob_digit[size_w-1]
Martin v. Löwis9f2e3462007-07-21 17:22:18 +00002073 ) << PyLong_SHIFT)
Guido van Rossumedcc38a1991-05-05 20:09:44 +00002074 + v->ob_digit[j-2])
2075 --q;
Tim Peters5af4e6c2002-08-12 02:31:19 +00002076
Guido van Rossumedcc38a1991-05-05 20:09:44 +00002077 for (i = 0; i < size_w && i+k < size_v; ++i) {
2078 twodigits z = w->ob_digit[i] * q;
Martin v. Löwis9f2e3462007-07-21 17:22:18 +00002079 digit zz = (digit) (z >> PyLong_SHIFT);
Guido van Rossumc0b618a1997-05-02 03:12:38 +00002080 carry += v->ob_digit[i+k] - z
Martin v. Löwis9f2e3462007-07-21 17:22:18 +00002081 + ((twodigits)zz << PyLong_SHIFT);
2082 v->ob_digit[i+k] = (digit)(carry & PyLong_MASK);
Tim Peters7d3a5112000-07-08 04:17:21 +00002083 carry = Py_ARITHMETIC_RIGHT_SHIFT(BASE_TWODIGITS_TYPE,
Martin v. Löwis9f2e3462007-07-21 17:22:18 +00002084 carry, PyLong_SHIFT);
Tim Peters7d3a5112000-07-08 04:17:21 +00002085 carry -= zz;
Guido van Rossumedcc38a1991-05-05 20:09:44 +00002086 }
Tim Peters5af4e6c2002-08-12 02:31:19 +00002087
Guido van Rossumedcc38a1991-05-05 20:09:44 +00002088 if (i+k < size_v) {
2089 carry += v->ob_digit[i+k];
2090 v->ob_digit[i+k] = 0;
2091 }
Tim Peters5af4e6c2002-08-12 02:31:19 +00002092
Guido van Rossumedcc38a1991-05-05 20:09:44 +00002093 if (carry == 0)
Guido van Rossum2095d241997-04-09 19:41:24 +00002094 a->ob_digit[k] = (digit) q;
Guido van Rossumedcc38a1991-05-05 20:09:44 +00002095 else {
2096 assert(carry == -1);
Guido van Rossum2095d241997-04-09 19:41:24 +00002097 a->ob_digit[k] = (digit) q-1;
Guido van Rossumedcc38a1991-05-05 20:09:44 +00002098 carry = 0;
2099 for (i = 0; i < size_w && i+k < size_v; ++i) {
2100 carry += v->ob_digit[i+k] + w->ob_digit[i];
Martin v. Löwis9f2e3462007-07-21 17:22:18 +00002101 v->ob_digit[i+k] = (digit)(carry & PyLong_MASK);
Tim Peters7d3a5112000-07-08 04:17:21 +00002102 carry = Py_ARITHMETIC_RIGHT_SHIFT(
2103 BASE_TWODIGITS_TYPE,
Martin v. Löwis9f2e3462007-07-21 17:22:18 +00002104 carry, PyLong_SHIFT);
Guido van Rossumedcc38a1991-05-05 20:09:44 +00002105 }
2106 }
2107 } /* for j, k */
Tim Peters5af4e6c2002-08-12 02:31:19 +00002108
Guido van Rossumc206c761995-01-10 15:23:19 +00002109 if (a == NULL)
2110 *prem = NULL;
2111 else {
Guido van Rossumc6913e71991-11-19 20:26:46 +00002112 a = long_normalize(a);
Guido van Rossume32e0141992-01-19 16:31:05 +00002113 *prem = divrem1(v, d, &d);
2114 /* d receives the (unused) remainder */
2115 if (*prem == NULL) {
Guido van Rossumc0b618a1997-05-02 03:12:38 +00002116 Py_DECREF(a);
Guido van Rossume32e0141992-01-19 16:31:05 +00002117 a = NULL;
Guido van Rossumc6913e71991-11-19 20:26:46 +00002118 }
Guido van Rossumedcc38a1991-05-05 20:09:44 +00002119 }
Guido van Rossumc0b618a1997-05-02 03:12:38 +00002120 Py_DECREF(v);
2121 Py_DECREF(w);
Guido van Rossumedcc38a1991-05-05 20:09:44 +00002122 return a;
2123}
2124
2125/* Methods */
2126
2127static void
Tim Peters9f688bf2000-07-07 15:53:28 +00002128long_dealloc(PyObject *v)
Guido van Rossumedcc38a1991-05-05 20:09:44 +00002129{
Christian Heimes90aa7642007-12-19 02:45:37 +00002130 Py_TYPE(v)->tp_free(v);
Guido van Rossumedcc38a1991-05-05 20:09:44 +00002131}
2132
Guido van Rossumc0b618a1997-05-02 03:12:38 +00002133static PyObject *
Tim Peters9f688bf2000-07-07 15:53:28 +00002134long_repr(PyObject *v)
Guido van Rossumedcc38a1991-05-05 20:09:44 +00002135{
Guido van Rossumcd16bf62007-06-13 18:07:49 +00002136 return _PyLong_Format(v, 10);
Guido van Rossumedcc38a1991-05-05 20:09:44 +00002137}
2138
2139static int
Tim Peters9f688bf2000-07-07 15:53:28 +00002140long_compare(PyLongObject *a, PyLongObject *b)
Guido van Rossumedcc38a1991-05-05 20:09:44 +00002141{
Martin v. Löwis18e16552006-02-15 17:27:45 +00002142 Py_ssize_t sign;
Tim Peters5af4e6c2002-08-12 02:31:19 +00002143
Christian Heimes90aa7642007-12-19 02:45:37 +00002144 if (Py_SIZE(a) != Py_SIZE(b)) {
2145 if (ABS(Py_SIZE(a)) == 0 && ABS(Py_SIZE(b)) == 0)
Guido van Rossumc6913e71991-11-19 20:26:46 +00002146 sign = 0;
2147 else
Christian Heimes90aa7642007-12-19 02:45:37 +00002148 sign = Py_SIZE(a) - Py_SIZE(b);
Guido van Rossumc6913e71991-11-19 20:26:46 +00002149 }
Guido van Rossumedcc38a1991-05-05 20:09:44 +00002150 else {
Christian Heimes90aa7642007-12-19 02:45:37 +00002151 Py_ssize_t i = ABS(Py_SIZE(a));
Guido van Rossumedcc38a1991-05-05 20:09:44 +00002152 while (--i >= 0 && a->ob_digit[i] == b->ob_digit[i])
2153 ;
2154 if (i < 0)
2155 sign = 0;
Guido van Rossum0b0db8e1993-01-21 16:07:51 +00002156 else {
Guido van Rossumedcc38a1991-05-05 20:09:44 +00002157 sign = (int)a->ob_digit[i] - (int)b->ob_digit[i];
Christian Heimes90aa7642007-12-19 02:45:37 +00002158 if (Py_SIZE(a) < 0)
Guido van Rossum0b0db8e1993-01-21 16:07:51 +00002159 sign = -sign;
2160 }
Guido van Rossumedcc38a1991-05-05 20:09:44 +00002161 }
Guido van Rossumc6913e71991-11-19 20:26:46 +00002162 return sign < 0 ? -1 : sign > 0 ? 1 : 0;
Guido van Rossumedcc38a1991-05-05 20:09:44 +00002163}
2164
Guido van Rossum47b9ff62006-08-24 00:41:19 +00002165static PyObject *
2166long_richcompare(PyObject *self, PyObject *other, int op)
2167{
Martin v. Löwis14b6d922007-02-06 21:05:30 +00002168 PyObject *result;
Martin v. Löwisda86fcc2007-09-10 07:59:54 +00002169 CHECK_BINOP(self, other);
2170 result = Py_CmpToRich(op, long_compare((PyLongObject*)self,
2171 (PyLongObject*)other));
Martin v. Löwis14b6d922007-02-06 21:05:30 +00002172 return result;
Guido van Rossum47b9ff62006-08-24 00:41:19 +00002173}
2174
Guido van Rossum9bfef441993-03-29 10:43:31 +00002175static long
Tim Peters9f688bf2000-07-07 15:53:28 +00002176long_hash(PyLongObject *v)
Guido van Rossum9bfef441993-03-29 10:43:31 +00002177{
2178 long x;
Martin v. Löwis18e16552006-02-15 17:27:45 +00002179 Py_ssize_t i;
2180 int sign;
Guido van Rossum9bfef441993-03-29 10:43:31 +00002181
2182 /* This is designed so that Python ints and longs with the
2183 same value hash to the same value, otherwise comparisons
2184 of mapping keys will turn out weird */
Christian Heimes90aa7642007-12-19 02:45:37 +00002185 i = Py_SIZE(v);
Guido van Rossumddefaf32007-01-14 03:31:43 +00002186 switch(i) {
2187 case -1: return v->ob_digit[0]==1 ? -2 : -v->ob_digit[0];
2188 case 0: return 0;
2189 case 1: return v->ob_digit[0];
2190 }
Guido van Rossum9bfef441993-03-29 10:43:31 +00002191 sign = 1;
2192 x = 0;
2193 if (i < 0) {
2194 sign = -1;
2195 i = -(i);
2196 }
Martin v. Löwis9f2e3462007-07-21 17:22:18 +00002197#define LONG_BIT_PyLong_SHIFT (8*sizeof(long) - PyLong_SHIFT)
Thomas Woutersce272b62007-09-19 21:19:28 +00002198 /* The following loop produces a C long x such that (unsigned long)x
2199 is congruent to the absolute value of v modulo ULONG_MAX. The
2200 resulting x is nonzero if and only if v is. */
Guido van Rossum9bfef441993-03-29 10:43:31 +00002201 while (--i >= 0) {
Neal Norwitzd5a65a72003-02-23 23:11:41 +00002202 /* Force a native long #-bits (32 or 64) circular shift */
Martin v. Löwis9f2e3462007-07-21 17:22:18 +00002203 x = ((x << PyLong_SHIFT) & ~PyLong_MASK) | ((x >> LONG_BIT_PyLong_SHIFT) & PyLong_MASK);
Guido van Rossum9bfef441993-03-29 10:43:31 +00002204 x += v->ob_digit[i];
Thomas Woutersce272b62007-09-19 21:19:28 +00002205 /* If the addition above overflowed (thinking of x as
2206 unsigned), we compensate by incrementing. This preserves
2207 the value modulo ULONG_MAX. */
2208 if ((unsigned long)x < v->ob_digit[i])
2209 x++;
Guido van Rossum9bfef441993-03-29 10:43:31 +00002210 }
Martin v. Löwis9f2e3462007-07-21 17:22:18 +00002211#undef LONG_BIT_PyLong_SHIFT
Guido van Rossum9bfef441993-03-29 10:43:31 +00002212 x = x * sign;
2213 if (x == -1)
2214 x = -2;
2215 return x;
2216}
2217
2218
Guido van Rossumedcc38a1991-05-05 20:09:44 +00002219/* Add the absolute values of two long integers. */
2220
Guido van Rossumc0b618a1997-05-02 03:12:38 +00002221static PyLongObject *
Tim Peters9f688bf2000-07-07 15:53:28 +00002222x_add(PyLongObject *a, PyLongObject *b)
Guido van Rossumedcc38a1991-05-05 20:09:44 +00002223{
Christian Heimes90aa7642007-12-19 02:45:37 +00002224 Py_ssize_t size_a = ABS(Py_SIZE(a)), size_b = ABS(Py_SIZE(b));
Guido van Rossumc0b618a1997-05-02 03:12:38 +00002225 PyLongObject *z;
Guido van Rossumedcc38a1991-05-05 20:09:44 +00002226 int i;
2227 digit carry = 0;
Tim Peters69c2de32001-09-11 22:31:33 +00002228
Guido van Rossumedcc38a1991-05-05 20:09:44 +00002229 /* Ensure a is the larger of the two: */
2230 if (size_a < size_b) {
Guido van Rossumc0b618a1997-05-02 03:12:38 +00002231 { PyLongObject *temp = a; a = b; b = temp; }
Martin v. Löwis18e16552006-02-15 17:27:45 +00002232 { Py_ssize_t size_temp = size_a;
Guido van Rossumc0b618a1997-05-02 03:12:38 +00002233 size_a = size_b;
2234 size_b = size_temp; }
Guido van Rossumedcc38a1991-05-05 20:09:44 +00002235 }
Guido van Rossumc0b618a1997-05-02 03:12:38 +00002236 z = _PyLong_New(size_a+1);
Guido van Rossumedcc38a1991-05-05 20:09:44 +00002237 if (z == NULL)
2238 return NULL;
2239 for (i = 0; i < size_b; ++i) {
2240 carry += a->ob_digit[i] + b->ob_digit[i];
Martin v. Löwis9f2e3462007-07-21 17:22:18 +00002241 z->ob_digit[i] = carry & PyLong_MASK;
2242 carry >>= PyLong_SHIFT;
Guido van Rossumedcc38a1991-05-05 20:09:44 +00002243 }
2244 for (; i < size_a; ++i) {
2245 carry += a->ob_digit[i];
Martin v. Löwis9f2e3462007-07-21 17:22:18 +00002246 z->ob_digit[i] = carry & PyLong_MASK;
2247 carry >>= PyLong_SHIFT;
Guido van Rossumedcc38a1991-05-05 20:09:44 +00002248 }
2249 z->ob_digit[i] = carry;
2250 return long_normalize(z);
2251}
2252
2253/* Subtract the absolute values of two integers. */
2254
Guido van Rossumc0b618a1997-05-02 03:12:38 +00002255static PyLongObject *
Tim Peters9f688bf2000-07-07 15:53:28 +00002256x_sub(PyLongObject *a, PyLongObject *b)
Guido van Rossumedcc38a1991-05-05 20:09:44 +00002257{
Christian Heimes90aa7642007-12-19 02:45:37 +00002258 Py_ssize_t size_a = ABS(Py_SIZE(a)), size_b = ABS(Py_SIZE(b));
Guido van Rossumc0b618a1997-05-02 03:12:38 +00002259 PyLongObject *z;
Martin v. Löwis18e16552006-02-15 17:27:45 +00002260 Py_ssize_t i;
Guido van Rossumedcc38a1991-05-05 20:09:44 +00002261 int sign = 1;
2262 digit borrow = 0;
Tim Peters69c2de32001-09-11 22:31:33 +00002263
Guido van Rossumedcc38a1991-05-05 20:09:44 +00002264 /* Ensure a is the larger of the two: */
2265 if (size_a < size_b) {
2266 sign = -1;
Guido van Rossumc0b618a1997-05-02 03:12:38 +00002267 { PyLongObject *temp = a; a = b; b = temp; }
Martin v. Löwis18e16552006-02-15 17:27:45 +00002268 { Py_ssize_t size_temp = size_a;
Guido van Rossumc0b618a1997-05-02 03:12:38 +00002269 size_a = size_b;
2270 size_b = size_temp; }
Guido van Rossumedcc38a1991-05-05 20:09:44 +00002271 }
2272 else if (size_a == size_b) {
2273 /* Find highest digit where a and b differ: */
2274 i = size_a;
2275 while (--i >= 0 && a->ob_digit[i] == b->ob_digit[i])
2276 ;
2277 if (i < 0)
Guido van Rossumc0b618a1997-05-02 03:12:38 +00002278 return _PyLong_New(0);
Guido van Rossumedcc38a1991-05-05 20:09:44 +00002279 if (a->ob_digit[i] < b->ob_digit[i]) {
2280 sign = -1;
Guido van Rossumc0b618a1997-05-02 03:12:38 +00002281 { PyLongObject *temp = a; a = b; b = temp; }
Guido van Rossumedcc38a1991-05-05 20:09:44 +00002282 }
2283 size_a = size_b = i+1;
2284 }
Guido van Rossumc0b618a1997-05-02 03:12:38 +00002285 z = _PyLong_New(size_a);
Guido van Rossumedcc38a1991-05-05 20:09:44 +00002286 if (z == NULL)
2287 return NULL;
2288 for (i = 0; i < size_b; ++i) {
2289 /* The following assumes unsigned arithmetic
Martin v. Löwis9f2e3462007-07-21 17:22:18 +00002290 works module 2**N for some N>PyLong_SHIFT. */
Guido van Rossumeb1fafc1994-08-29 12:47:19 +00002291 borrow = a->ob_digit[i] - b->ob_digit[i] - borrow;
Martin v. Löwis9f2e3462007-07-21 17:22:18 +00002292 z->ob_digit[i] = borrow & PyLong_MASK;
2293 borrow >>= PyLong_SHIFT;
Guido van Rossumedcc38a1991-05-05 20:09:44 +00002294 borrow &= 1; /* Keep only one sign bit */
2295 }
2296 for (; i < size_a; ++i) {
2297 borrow = a->ob_digit[i] - borrow;
Martin v. Löwis9f2e3462007-07-21 17:22:18 +00002298 z->ob_digit[i] = borrow & PyLong_MASK;
2299 borrow >>= PyLong_SHIFT;
Tim Peters43f04a32000-07-08 02:26:47 +00002300 borrow &= 1; /* Keep only one sign bit */
Guido van Rossumedcc38a1991-05-05 20:09:44 +00002301 }
2302 assert(borrow == 0);
Guido van Rossumc6913e71991-11-19 20:26:46 +00002303 if (sign < 0)
Guido van Rossumddefaf32007-01-14 03:31:43 +00002304 NEGATE(z);
Guido van Rossumedcc38a1991-05-05 20:09:44 +00002305 return long_normalize(z);
2306}
2307
Guido van Rossumc0b618a1997-05-02 03:12:38 +00002308static PyObject *
Martin v. Löwisda86fcc2007-09-10 07:59:54 +00002309long_add(PyLongObject *a, PyLongObject *b)
Guido van Rossum4c260ff1992-01-14 18:36:43 +00002310{
Martin v. Löwisda86fcc2007-09-10 07:59:54 +00002311 PyLongObject *z;
Tim Peters69c2de32001-09-11 22:31:33 +00002312
Martin v. Löwisda86fcc2007-09-10 07:59:54 +00002313 CHECK_BINOP(a, b);
Neil Schemenauerba872e22001-01-04 01:46:03 +00002314
Christian Heimes90aa7642007-12-19 02:45:37 +00002315 if (ABS(Py_SIZE(a)) <= 1 && ABS(Py_SIZE(b)) <= 1) {
Christian Heimes217cfd12007-12-02 14:31:20 +00002316 PyObject *result = PyLong_FromLong(MEDIUM_VALUE(a) +
Martin v. Löwis14b6d922007-02-06 21:05:30 +00002317 MEDIUM_VALUE(b));
Martin v. Löwis14b6d922007-02-06 21:05:30 +00002318 return result;
2319 }
Christian Heimes90aa7642007-12-19 02:45:37 +00002320 if (Py_SIZE(a) < 0) {
2321 if (Py_SIZE(b) < 0) {
Guido van Rossumedcc38a1991-05-05 20:09:44 +00002322 z = x_add(a, b);
Christian Heimes90aa7642007-12-19 02:45:37 +00002323 if (z != NULL && Py_SIZE(z) != 0)
2324 Py_SIZE(z) = -(Py_SIZE(z));
Guido van Rossumedcc38a1991-05-05 20:09:44 +00002325 }
2326 else
2327 z = x_sub(b, a);
2328 }
2329 else {
Christian Heimes90aa7642007-12-19 02:45:37 +00002330 if (Py_SIZE(b) < 0)
Guido van Rossumedcc38a1991-05-05 20:09:44 +00002331 z = x_sub(a, b);
2332 else
2333 z = x_add(a, b);
2334 }
Guido van Rossumc0b618a1997-05-02 03:12:38 +00002335 return (PyObject *)z;
Guido van Rossumedcc38a1991-05-05 20:09:44 +00002336}
2337
Guido van Rossumc0b618a1997-05-02 03:12:38 +00002338static PyObject *
Martin v. Löwisda86fcc2007-09-10 07:59:54 +00002339long_sub(PyLongObject *a, PyLongObject *b)
Guido van Rossum4c260ff1992-01-14 18:36:43 +00002340{
Martin v. Löwisda86fcc2007-09-10 07:59:54 +00002341 PyLongObject *z;
Tim Peters5af4e6c2002-08-12 02:31:19 +00002342
Martin v. Löwisda86fcc2007-09-10 07:59:54 +00002343 CHECK_BINOP(a, b);
Neil Schemenauerba872e22001-01-04 01:46:03 +00002344
Christian Heimes90aa7642007-12-19 02:45:37 +00002345 if (ABS(Py_SIZE(a)) <= 1 && ABS(Py_SIZE(b)) <= 1) {
Martin v. Löwis14b6d922007-02-06 21:05:30 +00002346 PyObject* r;
2347 r = PyLong_FromLong(MEDIUM_VALUE(a)-MEDIUM_VALUE(b));
Martin v. Löwis14b6d922007-02-06 21:05:30 +00002348 return r;
2349 }
Christian Heimes90aa7642007-12-19 02:45:37 +00002350 if (Py_SIZE(a) < 0) {
2351 if (Py_SIZE(b) < 0)
Guido van Rossumedcc38a1991-05-05 20:09:44 +00002352 z = x_sub(a, b);
2353 else
2354 z = x_add(a, b);
Christian Heimes90aa7642007-12-19 02:45:37 +00002355 if (z != NULL && Py_SIZE(z) != 0)
2356 Py_SIZE(z) = -(Py_SIZE(z));
Guido van Rossumedcc38a1991-05-05 20:09:44 +00002357 }
2358 else {
Christian Heimes90aa7642007-12-19 02:45:37 +00002359 if (Py_SIZE(b) < 0)
Guido van Rossumedcc38a1991-05-05 20:09:44 +00002360 z = x_add(a, b);
2361 else
2362 z = x_sub(a, b);
2363 }
Guido van Rossumc0b618a1997-05-02 03:12:38 +00002364 return (PyObject *)z;
Guido van Rossumedcc38a1991-05-05 20:09:44 +00002365}
2366
Tim Peters5af4e6c2002-08-12 02:31:19 +00002367/* Grade school multiplication, ignoring the signs.
2368 * Returns the absolute value of the product, or NULL if error.
2369 */
2370static PyLongObject *
2371x_mul(PyLongObject *a, PyLongObject *b)
Neil Schemenauerba872e22001-01-04 01:46:03 +00002372{
Tim Peters5af4e6c2002-08-12 02:31:19 +00002373 PyLongObject *z;
Christian Heimes90aa7642007-12-19 02:45:37 +00002374 Py_ssize_t size_a = ABS(Py_SIZE(a));
2375 Py_ssize_t size_b = ABS(Py_SIZE(b));
Martin v. Löwis18e16552006-02-15 17:27:45 +00002376 Py_ssize_t i;
Neil Schemenauerba872e22001-01-04 01:46:03 +00002377
Tim Peters5af4e6c2002-08-12 02:31:19 +00002378 z = _PyLong_New(size_a + size_b);
2379 if (z == NULL)
Guido van Rossumedcc38a1991-05-05 20:09:44 +00002380 return NULL;
Tim Peters5af4e6c2002-08-12 02:31:19 +00002381
Christian Heimes90aa7642007-12-19 02:45:37 +00002382 memset(z->ob_digit, 0, Py_SIZE(z) * sizeof(digit));
Tim Peters0973b992004-08-29 22:16:50 +00002383 if (a == b) {
2384 /* Efficient squaring per HAC, Algorithm 14.16:
2385 * http://www.cacr.math.uwaterloo.ca/hac/about/chap14.pdf
2386 * Gives slightly less than a 2x speedup when a == b,
2387 * via exploiting that each entry in the multiplication
2388 * pyramid appears twice (except for the size_a squares).
2389 */
2390 for (i = 0; i < size_a; ++i) {
2391 twodigits carry;
2392 twodigits f = a->ob_digit[i];
2393 digit *pz = z->ob_digit + (i << 1);
2394 digit *pa = a->ob_digit + i + 1;
2395 digit *paend = a->ob_digit + size_a;
Tim Peters5af4e6c2002-08-12 02:31:19 +00002396
Tim Peters0973b992004-08-29 22:16:50 +00002397 SIGCHECK({
2398 Py_DECREF(z);
2399 return NULL;
2400 })
2401
2402 carry = *pz + f * f;
Martin v. Löwis9f2e3462007-07-21 17:22:18 +00002403 *pz++ = (digit)(carry & PyLong_MASK);
2404 carry >>= PyLong_SHIFT;
2405 assert(carry <= PyLong_MASK);
Tim Peters0973b992004-08-29 22:16:50 +00002406
2407 /* Now f is added in twice in each column of the
2408 * pyramid it appears. Same as adding f<<1 once.
2409 */
2410 f <<= 1;
2411 while (pa < paend) {
2412 carry += *pz + *pa++ * f;
Martin v. Löwis9f2e3462007-07-21 17:22:18 +00002413 *pz++ = (digit)(carry & PyLong_MASK);
2414 carry >>= PyLong_SHIFT;
2415 assert(carry <= (PyLong_MASK << 1));
Tim Peters0973b992004-08-29 22:16:50 +00002416 }
2417 if (carry) {
2418 carry += *pz;
Martin v. Löwis9f2e3462007-07-21 17:22:18 +00002419 *pz++ = (digit)(carry & PyLong_MASK);
2420 carry >>= PyLong_SHIFT;
Tim Peters0973b992004-08-29 22:16:50 +00002421 }
2422 if (carry)
Martin v. Löwis9f2e3462007-07-21 17:22:18 +00002423 *pz += (digit)(carry & PyLong_MASK);
2424 assert((carry >> PyLong_SHIFT) == 0);
Guido van Rossumedcc38a1991-05-05 20:09:44 +00002425 }
Tim Peters0973b992004-08-29 22:16:50 +00002426 }
2427 else { /* a is not the same as b -- gradeschool long mult */
2428 for (i = 0; i < size_a; ++i) {
2429 twodigits carry = 0;
2430 twodigits f = a->ob_digit[i];
2431 digit *pz = z->ob_digit + i;
2432 digit *pb = b->ob_digit;
2433 digit *pbend = b->ob_digit + size_b;
2434
2435 SIGCHECK({
2436 Py_DECREF(z);
2437 return NULL;
2438 })
2439
2440 while (pb < pbend) {
2441 carry += *pz + *pb++ * f;
Martin v. Löwis9f2e3462007-07-21 17:22:18 +00002442 *pz++ = (digit)(carry & PyLong_MASK);
2443 carry >>= PyLong_SHIFT;
2444 assert(carry <= PyLong_MASK);
Tim Peters0973b992004-08-29 22:16:50 +00002445 }
2446 if (carry)
Martin v. Löwis9f2e3462007-07-21 17:22:18 +00002447 *pz += (digit)(carry & PyLong_MASK);
2448 assert((carry >> PyLong_SHIFT) == 0);
Guido van Rossumedcc38a1991-05-05 20:09:44 +00002449 }
2450 }
Tim Peters44121a62002-08-12 06:17:58 +00002451 return long_normalize(z);
Tim Peters5af4e6c2002-08-12 02:31:19 +00002452}
2453
2454/* A helper for Karatsuba multiplication (k_mul).
2455 Takes a long "n" and an integer "size" representing the place to
2456 split, and sets low and high such that abs(n) == (high << size) + low,
2457 viewing the shift as being by digits. The sign bit is ignored, and
2458 the return values are >= 0.
2459 Returns 0 on success, -1 on failure.
2460*/
2461static int
Martin v. Löwis18e16552006-02-15 17:27:45 +00002462kmul_split(PyLongObject *n, Py_ssize_t size, PyLongObject **high, PyLongObject **low)
Tim Peters5af4e6c2002-08-12 02:31:19 +00002463{
2464 PyLongObject *hi, *lo;
Martin v. Löwis18e16552006-02-15 17:27:45 +00002465 Py_ssize_t size_lo, size_hi;
Christian Heimes90aa7642007-12-19 02:45:37 +00002466 const Py_ssize_t size_n = ABS(Py_SIZE(n));
Tim Peters5af4e6c2002-08-12 02:31:19 +00002467
2468 size_lo = MIN(size_n, size);
2469 size_hi = size_n - size_lo;
2470
2471 if ((hi = _PyLong_New(size_hi)) == NULL)
2472 return -1;
2473 if ((lo = _PyLong_New(size_lo)) == NULL) {
2474 Py_DECREF(hi);
2475 return -1;
2476 }
2477
2478 memcpy(lo->ob_digit, n->ob_digit, size_lo * sizeof(digit));
2479 memcpy(hi->ob_digit, n->ob_digit + size_lo, size_hi * sizeof(digit));
2480
2481 *high = long_normalize(hi);
2482 *low = long_normalize(lo);
2483 return 0;
2484}
2485
Tim Peters60004642002-08-12 22:01:34 +00002486static PyLongObject *k_lopsided_mul(PyLongObject *a, PyLongObject *b);
2487
Tim Peters5af4e6c2002-08-12 02:31:19 +00002488/* Karatsuba multiplication. Ignores the input signs, and returns the
2489 * absolute value of the product (or NULL if error).
2490 * See Knuth Vol. 2 Chapter 4.3.3 (Pp. 294-295).
2491 */
2492static PyLongObject *
2493k_mul(PyLongObject *a, PyLongObject *b)
2494{
Christian Heimes90aa7642007-12-19 02:45:37 +00002495 Py_ssize_t asize = ABS(Py_SIZE(a));
2496 Py_ssize_t bsize = ABS(Py_SIZE(b));
Tim Peters5af4e6c2002-08-12 02:31:19 +00002497 PyLongObject *ah = NULL;
2498 PyLongObject *al = NULL;
2499 PyLongObject *bh = NULL;
2500 PyLongObject *bl = NULL;
Tim Peters5af4e6c2002-08-12 02:31:19 +00002501 PyLongObject *ret = NULL;
Tim Peters738eda72002-08-12 15:08:20 +00002502 PyLongObject *t1, *t2, *t3;
Martin v. Löwis18e16552006-02-15 17:27:45 +00002503 Py_ssize_t shift; /* the number of digits we split off */
2504 Py_ssize_t i;
Tim Peters738eda72002-08-12 15:08:20 +00002505
Tim Peters5af4e6c2002-08-12 02:31:19 +00002506 /* (ah*X+al)(bh*X+bl) = ah*bh*X*X + (ah*bl + al*bh)*X + al*bl
2507 * Let k = (ah+al)*(bh+bl) = ah*bl + al*bh + ah*bh + al*bl
2508 * Then the original product is
Tim Peters18c15b92002-08-12 02:43:58 +00002509 * ah*bh*X*X + (k - ah*bh - al*bl)*X + al*bl
Tim Peters5af4e6c2002-08-12 02:31:19 +00002510 * By picking X to be a power of 2, "*X" is just shifting, and it's
2511 * been reduced to 3 multiplies on numbers half the size.
2512 */
2513
Tim Petersfc07e562002-08-12 02:54:10 +00002514 /* We want to split based on the larger number; fiddle so that b
Tim Peters5af4e6c2002-08-12 02:31:19 +00002515 * is largest.
2516 */
Tim Peters738eda72002-08-12 15:08:20 +00002517 if (asize > bsize) {
Tim Peters5af4e6c2002-08-12 02:31:19 +00002518 t1 = a;
2519 a = b;
2520 b = t1;
Tim Peters738eda72002-08-12 15:08:20 +00002521
2522 i = asize;
2523 asize = bsize;
2524 bsize = i;
Tim Peters5af4e6c2002-08-12 02:31:19 +00002525 }
2526
2527 /* Use gradeschool math when either number is too small. */
Tim Peters0973b992004-08-29 22:16:50 +00002528 i = a == b ? KARATSUBA_SQUARE_CUTOFF : KARATSUBA_CUTOFF;
2529 if (asize <= i) {
Tim Peters738eda72002-08-12 15:08:20 +00002530 if (asize == 0)
Tim Peters44121a62002-08-12 06:17:58 +00002531 return _PyLong_New(0);
2532 else
2533 return x_mul(a, b);
2534 }
Tim Peters5af4e6c2002-08-12 02:31:19 +00002535
Tim Peters60004642002-08-12 22:01:34 +00002536 /* If a is small compared to b, splitting on b gives a degenerate
2537 * case with ah==0, and Karatsuba may be (even much) less efficient
2538 * than "grade school" then. However, we can still win, by viewing
2539 * b as a string of "big digits", each of width a->ob_size. That
2540 * leads to a sequence of balanced calls to k_mul.
2541 */
2542 if (2 * asize <= bsize)
2543 return k_lopsided_mul(a, b);
2544
Tim Petersd6974a52002-08-13 20:37:51 +00002545 /* Split a & b into hi & lo pieces. */
Tim Peters738eda72002-08-12 15:08:20 +00002546 shift = bsize >> 1;
Tim Peters5af4e6c2002-08-12 02:31:19 +00002547 if (kmul_split(a, shift, &ah, &al) < 0) goto fail;
Christian Heimes90aa7642007-12-19 02:45:37 +00002548 assert(Py_SIZE(ah) > 0); /* the split isn't degenerate */
Tim Petersd6974a52002-08-13 20:37:51 +00002549
Tim Peters0973b992004-08-29 22:16:50 +00002550 if (a == b) {
2551 bh = ah;
2552 bl = al;
2553 Py_INCREF(bh);
2554 Py_INCREF(bl);
2555 }
2556 else if (kmul_split(b, shift, &bh, &bl) < 0) goto fail;
Tim Peters5af4e6c2002-08-12 02:31:19 +00002557
Tim Petersd64c1de2002-08-12 17:36:03 +00002558 /* The plan:
2559 * 1. Allocate result space (asize + bsize digits: that's always
2560 * enough).
2561 * 2. Compute ah*bh, and copy into result at 2*shift.
2562 * 3. Compute al*bl, and copy into result at 0. Note that this
2563 * can't overlap with #2.
2564 * 4. Subtract al*bl from the result, starting at shift. This may
2565 * underflow (borrow out of the high digit), but we don't care:
2566 * we're effectively doing unsigned arithmetic mod
2567 * BASE**(sizea + sizeb), and so long as the *final* result fits,
2568 * borrows and carries out of the high digit can be ignored.
2569 * 5. Subtract ah*bh from the result, starting at shift.
2570 * 6. Compute (ah+al)*(bh+bl), and add it into the result starting
2571 * at shift.
2572 */
2573
2574 /* 1. Allocate result space. */
Tim Peters70b041b2002-08-12 19:38:01 +00002575 ret = _PyLong_New(asize + bsize);
Tim Peters5af4e6c2002-08-12 02:31:19 +00002576 if (ret == NULL) goto fail;
2577#ifdef Py_DEBUG
2578 /* Fill with trash, to catch reference to uninitialized digits. */
Christian Heimes90aa7642007-12-19 02:45:37 +00002579 memset(ret->ob_digit, 0xDF, Py_SIZE(ret) * sizeof(digit));
Tim Peters5af4e6c2002-08-12 02:31:19 +00002580#endif
Tim Peters44121a62002-08-12 06:17:58 +00002581
Tim Petersd64c1de2002-08-12 17:36:03 +00002582 /* 2. t1 <- ah*bh, and copy into high digits of result. */
Tim Peters738eda72002-08-12 15:08:20 +00002583 if ((t1 = k_mul(ah, bh)) == NULL) goto fail;
Christian Heimes90aa7642007-12-19 02:45:37 +00002584 assert(Py_SIZE(t1) >= 0);
2585 assert(2*shift + Py_SIZE(t1) <= Py_SIZE(ret));
Tim Peters738eda72002-08-12 15:08:20 +00002586 memcpy(ret->ob_digit + 2*shift, t1->ob_digit,
Christian Heimes90aa7642007-12-19 02:45:37 +00002587 Py_SIZE(t1) * sizeof(digit));
Tim Peters738eda72002-08-12 15:08:20 +00002588
2589 /* Zero-out the digits higher than the ah*bh copy. */
Christian Heimes90aa7642007-12-19 02:45:37 +00002590 i = Py_SIZE(ret) - 2*shift - Py_SIZE(t1);
Tim Peters44121a62002-08-12 06:17:58 +00002591 if (i)
Christian Heimes90aa7642007-12-19 02:45:37 +00002592 memset(ret->ob_digit + 2*shift + Py_SIZE(t1), 0,
Tim Peters44121a62002-08-12 06:17:58 +00002593 i * sizeof(digit));
Tim Peters5af4e6c2002-08-12 02:31:19 +00002594
Tim Petersd64c1de2002-08-12 17:36:03 +00002595 /* 3. t2 <- al*bl, and copy into the low digits. */
Tim Peters738eda72002-08-12 15:08:20 +00002596 if ((t2 = k_mul(al, bl)) == NULL) {
2597 Py_DECREF(t1);
2598 goto fail;
2599 }
Christian Heimes90aa7642007-12-19 02:45:37 +00002600 assert(Py_SIZE(t2) >= 0);
2601 assert(Py_SIZE(t2) <= 2*shift); /* no overlap with high digits */
2602 memcpy(ret->ob_digit, t2->ob_digit, Py_SIZE(t2) * sizeof(digit));
Tim Peters5af4e6c2002-08-12 02:31:19 +00002603
2604 /* Zero out remaining digits. */
Christian Heimes90aa7642007-12-19 02:45:37 +00002605 i = 2*shift - Py_SIZE(t2); /* number of uninitialized digits */
Tim Peters5af4e6c2002-08-12 02:31:19 +00002606 if (i)
Christian Heimes90aa7642007-12-19 02:45:37 +00002607 memset(ret->ob_digit + Py_SIZE(t2), 0, i * sizeof(digit));
Tim Peters5af4e6c2002-08-12 02:31:19 +00002608
Tim Petersd64c1de2002-08-12 17:36:03 +00002609 /* 4 & 5. Subtract ah*bh (t1) and al*bl (t2). We do al*bl first
2610 * because it's fresher in cache.
2611 */
Christian Heimes90aa7642007-12-19 02:45:37 +00002612 i = Py_SIZE(ret) - shift; /* # digits after shift */
2613 (void)v_isub(ret->ob_digit + shift, i, t2->ob_digit, Py_SIZE(t2));
Tim Peters738eda72002-08-12 15:08:20 +00002614 Py_DECREF(t2);
2615
Christian Heimes90aa7642007-12-19 02:45:37 +00002616 (void)v_isub(ret->ob_digit + shift, i, t1->ob_digit, Py_SIZE(t1));
Tim Peters738eda72002-08-12 15:08:20 +00002617 Py_DECREF(t1);
2618
Tim Petersd64c1de2002-08-12 17:36:03 +00002619 /* 6. t3 <- (ah+al)(bh+bl), and add into result. */
Tim Peters5af4e6c2002-08-12 02:31:19 +00002620 if ((t1 = x_add(ah, al)) == NULL) goto fail;
2621 Py_DECREF(ah);
2622 Py_DECREF(al);
2623 ah = al = NULL;
2624
Tim Peters0973b992004-08-29 22:16:50 +00002625 if (a == b) {
2626 t2 = t1;
2627 Py_INCREF(t2);
2628 }
2629 else if ((t2 = x_add(bh, bl)) == NULL) {
Tim Peters5af4e6c2002-08-12 02:31:19 +00002630 Py_DECREF(t1);
2631 goto fail;
2632 }
2633 Py_DECREF(bh);
2634 Py_DECREF(bl);
2635 bh = bl = NULL;
2636
Tim Peters738eda72002-08-12 15:08:20 +00002637 t3 = k_mul(t1, t2);
Tim Peters5af4e6c2002-08-12 02:31:19 +00002638 Py_DECREF(t1);
2639 Py_DECREF(t2);
Tim Peters738eda72002-08-12 15:08:20 +00002640 if (t3 == NULL) goto fail;
Christian Heimes90aa7642007-12-19 02:45:37 +00002641 assert(Py_SIZE(t3) >= 0);
Tim Peters5af4e6c2002-08-12 02:31:19 +00002642
Tim Petersd6974a52002-08-13 20:37:51 +00002643 /* Add t3. It's not obvious why we can't run out of room here.
2644 * See the (*) comment after this function.
Tim Petersd8b21732002-08-12 19:30:26 +00002645 */
Christian Heimes90aa7642007-12-19 02:45:37 +00002646 (void)v_iadd(ret->ob_digit + shift, i, t3->ob_digit, Py_SIZE(t3));
Tim Peters738eda72002-08-12 15:08:20 +00002647 Py_DECREF(t3);
Tim Peters5af4e6c2002-08-12 02:31:19 +00002648
Tim Peters5af4e6c2002-08-12 02:31:19 +00002649 return long_normalize(ret);
2650
2651 fail:
2652 Py_XDECREF(ret);
2653 Py_XDECREF(ah);
2654 Py_XDECREF(al);
2655 Py_XDECREF(bh);
2656 Py_XDECREF(bl);
Tim Peters5af4e6c2002-08-12 02:31:19 +00002657 return NULL;
2658}
2659
Tim Petersd6974a52002-08-13 20:37:51 +00002660/* (*) Why adding t3 can't "run out of room" above.
2661
Tim Petersab86c2b2002-08-15 20:06:00 +00002662Let f(x) mean the floor of x and c(x) mean the ceiling of x. Some facts
2663to start with:
Tim Petersd6974a52002-08-13 20:37:51 +00002664
Tim Petersab86c2b2002-08-15 20:06:00 +000026651. For any integer i, i = c(i/2) + f(i/2). In particular,
2666 bsize = c(bsize/2) + f(bsize/2).
26672. shift = f(bsize/2)
26683. asize <= bsize
26694. Since we call k_lopsided_mul if asize*2 <= bsize, asize*2 > bsize in this
2670 routine, so asize > bsize/2 >= f(bsize/2) in this routine.
Tim Petersd6974a52002-08-13 20:37:51 +00002671
Tim Petersab86c2b2002-08-15 20:06:00 +00002672We allocated asize + bsize result digits, and add t3 into them at an offset
2673of shift. This leaves asize+bsize-shift allocated digit positions for t3
2674to fit into, = (by #1 and #2) asize + f(bsize/2) + c(bsize/2) - f(bsize/2) =
2675asize + c(bsize/2) available digit positions.
Tim Petersd6974a52002-08-13 20:37:51 +00002676
Tim Petersab86c2b2002-08-15 20:06:00 +00002677bh has c(bsize/2) digits, and bl at most f(size/2) digits. So bh+hl has
2678at most c(bsize/2) digits + 1 bit.
Tim Petersd6974a52002-08-13 20:37:51 +00002679
Tim Petersab86c2b2002-08-15 20:06:00 +00002680If asize == bsize, ah has c(bsize/2) digits, else ah has at most f(bsize/2)
2681digits, and al has at most f(bsize/2) digits in any case. So ah+al has at
2682most (asize == bsize ? c(bsize/2) : f(bsize/2)) digits + 1 bit.
Tim Petersd6974a52002-08-13 20:37:51 +00002683
Tim Petersab86c2b2002-08-15 20:06:00 +00002684The product (ah+al)*(bh+bl) therefore has at most
Tim Petersd6974a52002-08-13 20:37:51 +00002685
Tim Petersab86c2b2002-08-15 20:06:00 +00002686 c(bsize/2) + (asize == bsize ? c(bsize/2) : f(bsize/2)) digits + 2 bits
Tim Petersd6974a52002-08-13 20:37:51 +00002687
Tim Petersab86c2b2002-08-15 20:06:00 +00002688and we have asize + c(bsize/2) available digit positions. We need to show
2689this is always enough. An instance of c(bsize/2) cancels out in both, so
2690the question reduces to whether asize digits is enough to hold
2691(asize == bsize ? c(bsize/2) : f(bsize/2)) digits + 2 bits. If asize < bsize,
2692then we're asking whether asize digits >= f(bsize/2) digits + 2 bits. By #4,
2693asize is at least f(bsize/2)+1 digits, so this in turn reduces to whether 1
Martin v. Löwis9f2e3462007-07-21 17:22:18 +00002694digit is enough to hold 2 bits. This is so since PyLong_SHIFT=15 >= 2. If
Tim Petersab86c2b2002-08-15 20:06:00 +00002695asize == bsize, then we're asking whether bsize digits is enough to hold
Tim Peterse417de02002-08-15 20:10:45 +00002696c(bsize/2) digits + 2 bits, or equivalently (by #1) whether f(bsize/2) digits
2697is enough to hold 2 bits. This is so if bsize >= 2, which holds because
2698bsize >= KARATSUBA_CUTOFF >= 2.
Tim Peters8e966ee2002-08-14 16:36:23 +00002699
Tim Peters48d52c02002-08-14 17:07:32 +00002700Note that since there's always enough room for (ah+al)*(bh+bl), and that's
2701clearly >= each of ah*bh and al*bl, there's always enough room to subtract
2702ah*bh and al*bl too.
Tim Petersd6974a52002-08-13 20:37:51 +00002703*/
2704
Tim Peters60004642002-08-12 22:01:34 +00002705/* b has at least twice the digits of a, and a is big enough that Karatsuba
2706 * would pay off *if* the inputs had balanced sizes. View b as a sequence
2707 * of slices, each with a->ob_size digits, and multiply the slices by a,
2708 * one at a time. This gives k_mul balanced inputs to work with, and is
2709 * also cache-friendly (we compute one double-width slice of the result
2710 * at a time, then move on, never bactracking except for the helpful
2711 * single-width slice overlap between successive partial sums).
2712 */
2713static PyLongObject *
2714k_lopsided_mul(PyLongObject *a, PyLongObject *b)
2715{
Christian Heimes90aa7642007-12-19 02:45:37 +00002716 const Py_ssize_t asize = ABS(Py_SIZE(a));
2717 Py_ssize_t bsize = ABS(Py_SIZE(b));
Martin v. Löwis18e16552006-02-15 17:27:45 +00002718 Py_ssize_t nbdone; /* # of b digits already multiplied */
Tim Peters60004642002-08-12 22:01:34 +00002719 PyLongObject *ret;
2720 PyLongObject *bslice = NULL;
2721
2722 assert(asize > KARATSUBA_CUTOFF);
2723 assert(2 * asize <= bsize);
2724
2725 /* Allocate result space, and zero it out. */
2726 ret = _PyLong_New(asize + bsize);
2727 if (ret == NULL)
2728 return NULL;
Christian Heimes90aa7642007-12-19 02:45:37 +00002729 memset(ret->ob_digit, 0, Py_SIZE(ret) * sizeof(digit));
Tim Peters60004642002-08-12 22:01:34 +00002730
2731 /* Successive slices of b are copied into bslice. */
Tim Peters12034032002-08-12 22:10:00 +00002732 bslice = _PyLong_New(asize);
Tim Peters60004642002-08-12 22:01:34 +00002733 if (bslice == NULL)
2734 goto fail;
2735
2736 nbdone = 0;
2737 while (bsize > 0) {
2738 PyLongObject *product;
Martin v. Löwis18e16552006-02-15 17:27:45 +00002739 const Py_ssize_t nbtouse = MIN(bsize, asize);
Tim Peters60004642002-08-12 22:01:34 +00002740
2741 /* Multiply the next slice of b by a. */
2742 memcpy(bslice->ob_digit, b->ob_digit + nbdone,
2743 nbtouse * sizeof(digit));
Christian Heimes90aa7642007-12-19 02:45:37 +00002744 Py_SIZE(bslice) = nbtouse;
Tim Peters60004642002-08-12 22:01:34 +00002745 product = k_mul(a, bslice);
2746 if (product == NULL)
2747 goto fail;
2748
2749 /* Add into result. */
Christian Heimes90aa7642007-12-19 02:45:37 +00002750 (void)v_iadd(ret->ob_digit + nbdone, Py_SIZE(ret) - nbdone,
2751 product->ob_digit, Py_SIZE(product));
Tim Peters60004642002-08-12 22:01:34 +00002752 Py_DECREF(product);
2753
2754 bsize -= nbtouse;
2755 nbdone += nbtouse;
2756 }
2757
2758 Py_DECREF(bslice);
2759 return long_normalize(ret);
2760
2761 fail:
2762 Py_DECREF(ret);
2763 Py_XDECREF(bslice);
2764 return NULL;
2765}
Tim Peters5af4e6c2002-08-12 02:31:19 +00002766
2767static PyObject *
Martin v. Löwisda86fcc2007-09-10 07:59:54 +00002768long_mul(PyLongObject *a, PyLongObject *b)
Tim Peters5af4e6c2002-08-12 02:31:19 +00002769{
Martin v. Löwisda86fcc2007-09-10 07:59:54 +00002770 PyLongObject *z;
Tim Peters5af4e6c2002-08-12 02:31:19 +00002771
Martin v. Löwisda86fcc2007-09-10 07:59:54 +00002772 CHECK_BINOP(a, b);
Tim Peters5af4e6c2002-08-12 02:31:19 +00002773
Christian Heimes90aa7642007-12-19 02:45:37 +00002774 if (ABS(Py_SIZE(a)) <= 1 && ABS(Py_SIZE(b)) <= 1) {
Martin v. Löwis14b6d922007-02-06 21:05:30 +00002775 PyObject *r;
Martin v. Löwisda86fcc2007-09-10 07:59:54 +00002776 r = PyLong_FromLong(MEDIUM_VALUE(a)*MEDIUM_VALUE(b));
Martin v. Löwis14b6d922007-02-06 21:05:30 +00002777 return r;
2778 }
Guido van Rossumddefaf32007-01-14 03:31:43 +00002779
Tim Petersd64c1de2002-08-12 17:36:03 +00002780 z = k_mul(a, b);
Tim Peters9973d742002-08-15 19:41:06 +00002781 /* Negate if exactly one of the inputs is negative. */
Christian Heimes90aa7642007-12-19 02:45:37 +00002782 if (((Py_SIZE(a) ^ Py_SIZE(b)) < 0) && z)
Guido van Rossumddefaf32007-01-14 03:31:43 +00002783 NEGATE(z);
Tim Peters9973d742002-08-15 19:41:06 +00002784 return (PyObject *)z;
Guido van Rossumedcc38a1991-05-05 20:09:44 +00002785}
2786
Guido van Rossume32e0141992-01-19 16:31:05 +00002787/* The / and % operators are now defined in terms of divmod().
2788 The expression a mod b has the value a - b*floor(a/b).
2789 The long_divrem function gives the remainder after division of
Guido van Rossumedcc38a1991-05-05 20:09:44 +00002790 |a| by |b|, with the sign of a. This is also expressed
2791 as a - b*trunc(a/b), if trunc truncates towards zero.
2792 Some examples:
2793 a b a rem b a mod b
2794 13 10 3 3
2795 -13 10 -3 7
2796 13 -10 3 -7
2797 -13 -10 -3 -3
2798 So, to get from rem to mod, we have to add b if a and b
Guido van Rossum23d6f0e1991-05-14 12:06:49 +00002799 have different signs. We then subtract one from the 'div'
2800 part of the outcome to keep the invariant intact. */
Guido van Rossumedcc38a1991-05-05 20:09:44 +00002801
Tim Peters47e52ee2004-08-30 02:44:38 +00002802/* Compute
2803 * *pdiv, *pmod = divmod(v, w)
2804 * NULL can be passed for pdiv or pmod, in which case that part of
2805 * the result is simply thrown away. The caller owns a reference to
2806 * each of these it requests (does not pass NULL for).
2807 */
Guido van Rossume32e0141992-01-19 16:31:05 +00002808static int
Tim Peters5af4e6c2002-08-12 02:31:19 +00002809l_divmod(PyLongObject *v, PyLongObject *w,
Tim Peters9f688bf2000-07-07 15:53:28 +00002810 PyLongObject **pdiv, PyLongObject **pmod)
Guido van Rossume32e0141992-01-19 16:31:05 +00002811{
Guido van Rossumc0b618a1997-05-02 03:12:38 +00002812 PyLongObject *div, *mod;
Tim Peters5af4e6c2002-08-12 02:31:19 +00002813
Guido van Rossume32e0141992-01-19 16:31:05 +00002814 if (long_divrem(v, w, &div, &mod) < 0)
2815 return -1;
Christian Heimes90aa7642007-12-19 02:45:37 +00002816 if ((Py_SIZE(mod) < 0 && Py_SIZE(w) > 0) ||
2817 (Py_SIZE(mod) > 0 && Py_SIZE(w) < 0)) {
Guido van Rossumc0b618a1997-05-02 03:12:38 +00002818 PyLongObject *temp;
2819 PyLongObject *one;
2820 temp = (PyLongObject *) long_add(mod, w);
2821 Py_DECREF(mod);
Guido van Rossume32e0141992-01-19 16:31:05 +00002822 mod = temp;
2823 if (mod == NULL) {
Guido van Rossumc0b618a1997-05-02 03:12:38 +00002824 Py_DECREF(div);
Guido van Rossume32e0141992-01-19 16:31:05 +00002825 return -1;
2826 }
Guido van Rossumc0b618a1997-05-02 03:12:38 +00002827 one = (PyLongObject *) PyLong_FromLong(1L);
Guido van Rossume32e0141992-01-19 16:31:05 +00002828 if (one == NULL ||
Guido van Rossumc0b618a1997-05-02 03:12:38 +00002829 (temp = (PyLongObject *) long_sub(div, one)) == NULL) {
2830 Py_DECREF(mod);
2831 Py_DECREF(div);
2832 Py_XDECREF(one);
Guido van Rossume32e0141992-01-19 16:31:05 +00002833 return -1;
2834 }
Guido van Rossumc0b618a1997-05-02 03:12:38 +00002835 Py_DECREF(one);
2836 Py_DECREF(div);
Guido van Rossume32e0141992-01-19 16:31:05 +00002837 div = temp;
2838 }
Tim Peters47e52ee2004-08-30 02:44:38 +00002839 if (pdiv != NULL)
2840 *pdiv = div;
2841 else
2842 Py_DECREF(div);
2843
2844 if (pmod != NULL)
2845 *pmod = mod;
2846 else
2847 Py_DECREF(mod);
2848
Guido van Rossume32e0141992-01-19 16:31:05 +00002849 return 0;
2850}
2851
Guido van Rossumc0b618a1997-05-02 03:12:38 +00002852static PyObject *
Martin v. Löwisda86fcc2007-09-10 07:59:54 +00002853long_div(PyObject *a, PyObject *b)
Guido van Rossume32e0141992-01-19 16:31:05 +00002854{
Martin v. Löwisda86fcc2007-09-10 07:59:54 +00002855 PyLongObject *div;
Neil Schemenauerba872e22001-01-04 01:46:03 +00002856
Martin v. Löwisda86fcc2007-09-10 07:59:54 +00002857 CHECK_BINOP(a, b);
2858 if (l_divmod((PyLongObject*)a, (PyLongObject*)b, &div, NULL) < 0)
Tim Peters47e52ee2004-08-30 02:44:38 +00002859 div = NULL;
Guido van Rossumc0b618a1997-05-02 03:12:38 +00002860 return (PyObject *)div;
Guido van Rossume32e0141992-01-19 16:31:05 +00002861}
2862
Guido van Rossumc0b618a1997-05-02 03:12:38 +00002863static PyObject *
Martin v. Löwisda86fcc2007-09-10 07:59:54 +00002864long_true_divide(PyObject *a, PyObject *b)
Tim Peters20dab9f2001-09-04 05:31:47 +00002865{
Tim Peterse2a60002001-09-04 06:17:36 +00002866 double ad, bd;
Thomas Wouters553489a2006-02-01 21:32:04 +00002867 int failed, aexp = -1, bexp = -1;
Tim Peterse2a60002001-09-04 06:17:36 +00002868
Martin v. Löwisda86fcc2007-09-10 07:59:54 +00002869 CHECK_BINOP(a, b);
Tim Peterse2a60002001-09-04 06:17:36 +00002870 ad = _PyLong_AsScaledDouble((PyObject *)a, &aexp);
2871 bd = _PyLong_AsScaledDouble((PyObject *)b, &bexp);
Tim Peters6f97e492001-11-04 23:09:40 +00002872 failed = (ad == -1.0 || bd == -1.0) && PyErr_Occurred();
Tim Peters6f97e492001-11-04 23:09:40 +00002873 if (failed)
Tim Peterse2a60002001-09-04 06:17:36 +00002874 return NULL;
Thomas Wouters553489a2006-02-01 21:32:04 +00002875 /* 'aexp' and 'bexp' were initialized to -1 to silence gcc-4.0.x,
2876 but should really be set correctly after sucessful calls to
2877 _PyLong_AsScaledDouble() */
2878 assert(aexp >= 0 && bexp >= 0);
Tim Peterse2a60002001-09-04 06:17:36 +00002879
2880 if (bd == 0.0) {
2881 PyErr_SetString(PyExc_ZeroDivisionError,
Guido van Rossumddefaf32007-01-14 03:31:43 +00002882 "int division or modulo by zero");
Tim Peterse2a60002001-09-04 06:17:36 +00002883 return NULL;
2884 }
2885
Martin v. Löwis9f2e3462007-07-21 17:22:18 +00002886 /* True value is very close to ad/bd * 2**(PyLong_SHIFT*(aexp-bexp)) */
Tim Peterse2a60002001-09-04 06:17:36 +00002887 ad /= bd; /* overflow/underflow impossible here */
2888 aexp -= bexp;
Martin v. Löwis9f2e3462007-07-21 17:22:18 +00002889 if (aexp > INT_MAX / PyLong_SHIFT)
Tim Peterse2a60002001-09-04 06:17:36 +00002890 goto overflow;
Martin v. Löwis9f2e3462007-07-21 17:22:18 +00002891 else if (aexp < -(INT_MAX / PyLong_SHIFT))
Tim Peterse56ed9b2001-09-06 21:59:14 +00002892 return PyFloat_FromDouble(0.0); /* underflow to 0 */
Tim Peterse2a60002001-09-04 06:17:36 +00002893 errno = 0;
Martin v. Löwis9f2e3462007-07-21 17:22:18 +00002894 ad = ldexp(ad, aexp * PyLong_SHIFT);
Tim Peters57f282a2001-09-05 05:38:10 +00002895 if (Py_OVERFLOWED(ad)) /* ignore underflow to 0.0 */
Tim Peterse2a60002001-09-04 06:17:36 +00002896 goto overflow;
2897 return PyFloat_FromDouble(ad);
2898
2899overflow:
2900 PyErr_SetString(PyExc_OverflowError,
Guido van Rossumddefaf32007-01-14 03:31:43 +00002901 "int/int too large for a float");
Tim Peterse2a60002001-09-04 06:17:36 +00002902 return NULL;
Tim Peters5af4e6c2002-08-12 02:31:19 +00002903
Tim Peters20dab9f2001-09-04 05:31:47 +00002904}
2905
2906static PyObject *
Martin v. Löwisda86fcc2007-09-10 07:59:54 +00002907long_mod(PyObject *a, PyObject *b)
Guido van Rossume32e0141992-01-19 16:31:05 +00002908{
Martin v. Löwisda86fcc2007-09-10 07:59:54 +00002909 PyLongObject *mod;
2910
2911 CHECK_BINOP(a, b);
Neil Schemenauerba872e22001-01-04 01:46:03 +00002912
Martin v. Löwisda86fcc2007-09-10 07:59:54 +00002913 if (l_divmod((PyLongObject*)a, (PyLongObject*)b, NULL, &mod) < 0)
Tim Peters47e52ee2004-08-30 02:44:38 +00002914 mod = NULL;
Guido van Rossumc0b618a1997-05-02 03:12:38 +00002915 return (PyObject *)mod;
Guido van Rossume32e0141992-01-19 16:31:05 +00002916}
2917
Guido van Rossumc0b618a1997-05-02 03:12:38 +00002918static PyObject *
Martin v. Löwisda86fcc2007-09-10 07:59:54 +00002919long_divmod(PyObject *a, PyObject *b)
Guido van Rossumedcc38a1991-05-05 20:09:44 +00002920{
Martin v. Löwisda86fcc2007-09-10 07:59:54 +00002921 PyLongObject *div, *mod;
Guido van Rossumc0b618a1997-05-02 03:12:38 +00002922 PyObject *z;
Neil Schemenauerba872e22001-01-04 01:46:03 +00002923
Martin v. Löwisda86fcc2007-09-10 07:59:54 +00002924 CHECK_BINOP(a, b);
Neil Schemenauerba872e22001-01-04 01:46:03 +00002925
Martin v. Löwisda86fcc2007-09-10 07:59:54 +00002926 if (l_divmod((PyLongObject*)a, (PyLongObject*)b, &div, &mod) < 0) {
Guido van Rossumedcc38a1991-05-05 20:09:44 +00002927 return NULL;
Neil Schemenauerba872e22001-01-04 01:46:03 +00002928 }
Guido van Rossumc0b618a1997-05-02 03:12:38 +00002929 z = PyTuple_New(2);
Guido van Rossumedcc38a1991-05-05 20:09:44 +00002930 if (z != NULL) {
Guido van Rossumc0b618a1997-05-02 03:12:38 +00002931 PyTuple_SetItem(z, 0, (PyObject *) div);
2932 PyTuple_SetItem(z, 1, (PyObject *) mod);
Guido van Rossumedcc38a1991-05-05 20:09:44 +00002933 }
2934 else {
Guido van Rossumc0b618a1997-05-02 03:12:38 +00002935 Py_DECREF(div);
2936 Py_DECREF(mod);
Guido van Rossumedcc38a1991-05-05 20:09:44 +00002937 }
2938 return z;
2939}
2940
Tim Peters47e52ee2004-08-30 02:44:38 +00002941/* pow(v, w, x) */
Guido van Rossumc0b618a1997-05-02 03:12:38 +00002942static PyObject *
Neil Schemenauerba872e22001-01-04 01:46:03 +00002943long_pow(PyObject *v, PyObject *w, PyObject *x)
Guido van Rossumedcc38a1991-05-05 20:09:44 +00002944{
Tim Peters47e52ee2004-08-30 02:44:38 +00002945 PyLongObject *a, *b, *c; /* a,b,c = v,w,x */
2946 int negativeOutput = 0; /* if x<0 return negative output */
Neil Schemenauerba872e22001-01-04 01:46:03 +00002947
Tim Peters47e52ee2004-08-30 02:44:38 +00002948 PyLongObject *z = NULL; /* accumulated result */
Martin v. Löwis18e16552006-02-15 17:27:45 +00002949 Py_ssize_t i, j, k; /* counters */
Tim Peters47e52ee2004-08-30 02:44:38 +00002950 PyLongObject *temp = NULL;
2951
2952 /* 5-ary values. If the exponent is large enough, table is
2953 * precomputed so that table[i] == a**i % c for i in range(32).
2954 */
2955 PyLongObject *table[32] = {0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
2956 0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0};
2957
2958 /* a, b, c = v, w, x */
Martin v. Löwisda86fcc2007-09-10 07:59:54 +00002959 CHECK_BINOP(v, w);
2960 a = (PyLongObject*)v; Py_INCREF(a);
2961 b = (PyLongObject*)w; Py_INCREF(b);
Tim Peters47e52ee2004-08-30 02:44:38 +00002962 if (PyLong_Check(x)) {
2963 c = (PyLongObject *)x;
Neil Schemenauerba872e22001-01-04 01:46:03 +00002964 Py_INCREF(x);
2965 }
Tim Peters47e52ee2004-08-30 02:44:38 +00002966 else if (x == Py_None)
2967 c = NULL;
Neil Schemenauerba872e22001-01-04 01:46:03 +00002968 else {
2969 Py_DECREF(a);
2970 Py_DECREF(b);
2971 Py_INCREF(Py_NotImplemented);
2972 return Py_NotImplemented;
2973 }
Tim Peters4c483c42001-09-05 06:24:58 +00002974
Christian Heimes90aa7642007-12-19 02:45:37 +00002975 if (Py_SIZE(b) < 0) { /* if exponent is negative */
Tim Peters47e52ee2004-08-30 02:44:38 +00002976 if (c) {
Tim Peters4c483c42001-09-05 06:24:58 +00002977 PyErr_SetString(PyExc_TypeError, "pow() 2nd argument "
Tim Peters47e52ee2004-08-30 02:44:38 +00002978 "cannot be negative when 3rd argument specified");
Tim Peterscd97da32004-08-30 02:58:59 +00002979 goto Error;
Tim Peters32f453e2001-09-03 08:35:41 +00002980 }
Guido van Rossum2c7b8fe1999-10-11 22:34:41 +00002981 else {
Tim Peters47e52ee2004-08-30 02:44:38 +00002982 /* else return a float. This works because we know
2983 that this calls float_pow() which converts its
2984 arguments to double. */
2985 Py_DECREF(a);
2986 Py_DECREF(b);
2987 return PyFloat_Type.tp_as_number->nb_power(v, w, x);
Guido van Rossum2c7b8fe1999-10-11 22:34:41 +00002988 }
Guido van Rossumeb1fafc1994-08-29 12:47:19 +00002989 }
Tim Peters47e52ee2004-08-30 02:44:38 +00002990
2991 if (c) {
2992 /* if modulus == 0:
2993 raise ValueError() */
Christian Heimes90aa7642007-12-19 02:45:37 +00002994 if (Py_SIZE(c) == 0) {
Tim Peters47e52ee2004-08-30 02:44:38 +00002995 PyErr_SetString(PyExc_ValueError,
2996 "pow() 3rd argument cannot be 0");
Tim Peterscd97da32004-08-30 02:58:59 +00002997 goto Error;
Tim Peters47e52ee2004-08-30 02:44:38 +00002998 }
2999
3000 /* if modulus < 0:
3001 negativeOutput = True
3002 modulus = -modulus */
Christian Heimes90aa7642007-12-19 02:45:37 +00003003 if (Py_SIZE(c) < 0) {
Tim Peters47e52ee2004-08-30 02:44:38 +00003004 negativeOutput = 1;
3005 temp = (PyLongObject *)_PyLong_Copy(c);
3006 if (temp == NULL)
3007 goto Error;
3008 Py_DECREF(c);
3009 c = temp;
3010 temp = NULL;
Guido van Rossumddefaf32007-01-14 03:31:43 +00003011 NEGATE(c);
Tim Peters47e52ee2004-08-30 02:44:38 +00003012 }
3013
3014 /* if modulus == 1:
3015 return 0 */
Christian Heimes90aa7642007-12-19 02:45:37 +00003016 if ((Py_SIZE(c) == 1) && (c->ob_digit[0] == 1)) {
Tim Peters47e52ee2004-08-30 02:44:38 +00003017 z = (PyLongObject *)PyLong_FromLong(0L);
3018 goto Done;
3019 }
3020
3021 /* if base < 0:
3022 base = base % modulus
3023 Having the base positive just makes things easier. */
Christian Heimes90aa7642007-12-19 02:45:37 +00003024 if (Py_SIZE(a) < 0) {
Tim Peters47e52ee2004-08-30 02:44:38 +00003025 if (l_divmod(a, c, NULL, &temp) < 0)
Tim Peterscd97da32004-08-30 02:58:59 +00003026 goto Error;
Tim Peters47e52ee2004-08-30 02:44:38 +00003027 Py_DECREF(a);
3028 a = temp;
3029 temp = NULL;
3030 }
3031 }
3032
3033 /* At this point a, b, and c are guaranteed non-negative UNLESS
3034 c is NULL, in which case a may be negative. */
3035
3036 z = (PyLongObject *)PyLong_FromLong(1L);
3037 if (z == NULL)
3038 goto Error;
3039
3040 /* Perform a modular reduction, X = X % c, but leave X alone if c
3041 * is NULL.
3042 */
3043#define REDUCE(X) \
3044 if (c != NULL) { \
3045 if (l_divmod(X, c, NULL, &temp) < 0) \
3046 goto Error; \
3047 Py_XDECREF(X); \
3048 X = temp; \
3049 temp = NULL; \
3050 }
3051
3052 /* Multiply two values, then reduce the result:
3053 result = X*Y % c. If c is NULL, skip the mod. */
3054#define MULT(X, Y, result) \
3055{ \
3056 temp = (PyLongObject *)long_mul(X, Y); \
3057 if (temp == NULL) \
3058 goto Error; \
3059 Py_XDECREF(result); \
3060 result = temp; \
3061 temp = NULL; \
3062 REDUCE(result) \
3063}
3064
Christian Heimes90aa7642007-12-19 02:45:37 +00003065 if (Py_SIZE(b) <= FIVEARY_CUTOFF) {
Tim Peters47e52ee2004-08-30 02:44:38 +00003066 /* Left-to-right binary exponentiation (HAC Algorithm 14.79) */
3067 /* http://www.cacr.math.uwaterloo.ca/hac/about/chap14.pdf */
Christian Heimes90aa7642007-12-19 02:45:37 +00003068 for (i = Py_SIZE(b) - 1; i >= 0; --i) {
Tim Peters47e52ee2004-08-30 02:44:38 +00003069 digit bi = b->ob_digit[i];
3070
Martin v. Löwis9f2e3462007-07-21 17:22:18 +00003071 for (j = 1 << (PyLong_SHIFT-1); j != 0; j >>= 1) {
Tim Peters47e52ee2004-08-30 02:44:38 +00003072 MULT(z, z, z)
3073 if (bi & j)
3074 MULT(z, a, z)
3075 }
3076 }
3077 }
3078 else {
3079 /* Left-to-right 5-ary exponentiation (HAC Algorithm 14.82) */
3080 Py_INCREF(z); /* still holds 1L */
3081 table[0] = z;
3082 for (i = 1; i < 32; ++i)
3083 MULT(table[i-1], a, table[i])
3084
Christian Heimes90aa7642007-12-19 02:45:37 +00003085 for (i = Py_SIZE(b) - 1; i >= 0; --i) {
Tim Peters47e52ee2004-08-30 02:44:38 +00003086 const digit bi = b->ob_digit[i];
3087
Martin v. Löwis9f2e3462007-07-21 17:22:18 +00003088 for (j = PyLong_SHIFT - 5; j >= 0; j -= 5) {
Tim Peters47e52ee2004-08-30 02:44:38 +00003089 const int index = (bi >> j) & 0x1f;
3090 for (k = 0; k < 5; ++k)
3091 MULT(z, z, z)
3092 if (index)
3093 MULT(z, table[index], z)
3094 }
3095 }
3096 }
3097
Christian Heimes90aa7642007-12-19 02:45:37 +00003098 if (negativeOutput && (Py_SIZE(z) != 0)) {
Tim Peters47e52ee2004-08-30 02:44:38 +00003099 temp = (PyLongObject *)long_sub(z, c);
3100 if (temp == NULL)
3101 goto Error;
3102 Py_DECREF(z);
3103 z = temp;
3104 temp = NULL;
3105 }
3106 goto Done;
3107
3108 Error:
3109 if (z != NULL) {
3110 Py_DECREF(z);
3111 z = NULL;
3112 }
3113 /* fall through */
3114 Done:
Christian Heimes90aa7642007-12-19 02:45:37 +00003115 if (Py_SIZE(b) > FIVEARY_CUTOFF) {
Tim Peters47e52ee2004-08-30 02:44:38 +00003116 for (i = 0; i < 32; ++i)
3117 Py_XDECREF(table[i]);
3118 }
Tim Petersde7990b2005-07-17 23:45:23 +00003119 Py_DECREF(a);
3120 Py_DECREF(b);
3121 Py_XDECREF(c);
3122 Py_XDECREF(temp);
Guido van Rossumc0b618a1997-05-02 03:12:38 +00003123 return (PyObject *)z;
Guido van Rossumedcc38a1991-05-05 20:09:44 +00003124}
3125
Guido van Rossumc0b618a1997-05-02 03:12:38 +00003126static PyObject *
Tim Peters9f688bf2000-07-07 15:53:28 +00003127long_invert(PyLongObject *v)
Guido van Rossumedcc38a1991-05-05 20:09:44 +00003128{
Guido van Rossum4c260ff1992-01-14 18:36:43 +00003129 /* Implement ~x as -(x+1) */
Guido van Rossumc0b618a1997-05-02 03:12:38 +00003130 PyLongObject *x;
3131 PyLongObject *w;
Christian Heimes90aa7642007-12-19 02:45:37 +00003132 if (ABS(Py_SIZE(v)) <=1)
Guido van Rossumddefaf32007-01-14 03:31:43 +00003133 return PyLong_FromLong(-(MEDIUM_VALUE(v)+1));
Guido van Rossumc0b618a1997-05-02 03:12:38 +00003134 w = (PyLongObject *)PyLong_FromLong(1L);
Guido van Rossum4c260ff1992-01-14 18:36:43 +00003135 if (w == NULL)
3136 return NULL;
Guido van Rossumc0b618a1997-05-02 03:12:38 +00003137 x = (PyLongObject *) long_add(v, w);
3138 Py_DECREF(w);
Guido van Rossum4c260ff1992-01-14 18:36:43 +00003139 if (x == NULL)
3140 return NULL;
Christian Heimes90aa7642007-12-19 02:45:37 +00003141 Py_SIZE(x) = -(Py_SIZE(x));
Guido van Rossumc0b618a1997-05-02 03:12:38 +00003142 return (PyObject *)x;
Guido van Rossumedcc38a1991-05-05 20:09:44 +00003143}
3144
Guido van Rossumc0b618a1997-05-02 03:12:38 +00003145static PyObject *
Tim Peters9f688bf2000-07-07 15:53:28 +00003146long_neg(PyLongObject *v)
Guido van Rossumc6913e71991-11-19 20:26:46 +00003147{
Guido van Rossumc0b618a1997-05-02 03:12:38 +00003148 PyLongObject *z;
Christian Heimes90aa7642007-12-19 02:45:37 +00003149 if (ABS(Py_SIZE(v)) <= 1)
Guido van Rossumddefaf32007-01-14 03:31:43 +00003150 return PyLong_FromLong(-MEDIUM_VALUE(v));
Tim Peters69c2de32001-09-11 22:31:33 +00003151 z = (PyLongObject *)_PyLong_Copy(v);
3152 if (z != NULL)
Christian Heimes90aa7642007-12-19 02:45:37 +00003153 Py_SIZE(z) = -(Py_SIZE(v));
Guido van Rossumc0b618a1997-05-02 03:12:38 +00003154 return (PyObject *)z;
Guido van Rossumc6913e71991-11-19 20:26:46 +00003155}
3156
Guido van Rossumc0b618a1997-05-02 03:12:38 +00003157static PyObject *
Tim Peters9f688bf2000-07-07 15:53:28 +00003158long_abs(PyLongObject *v)
Guido van Rossumedcc38a1991-05-05 20:09:44 +00003159{
Christian Heimes90aa7642007-12-19 02:45:37 +00003160 if (Py_SIZE(v) < 0)
Guido van Rossum4c260ff1992-01-14 18:36:43 +00003161 return long_neg(v);
Tim Peters69c2de32001-09-11 22:31:33 +00003162 else
Guido van Rossumb43daf72007-08-01 18:08:08 +00003163 return long_long((PyObject *)v);
Guido van Rossumedcc38a1991-05-05 20:09:44 +00003164}
3165
Guido van Rossum23d6f0e1991-05-14 12:06:49 +00003166static int
Jack Diederich4dafcc42006-11-28 19:15:13 +00003167long_bool(PyLongObject *v)
Guido van Rossum23d6f0e1991-05-14 12:06:49 +00003168{
Christian Heimes90aa7642007-12-19 02:45:37 +00003169 return ABS(Py_SIZE(v)) != 0;
Guido van Rossumc6913e71991-11-19 20:26:46 +00003170}
3171
Guido van Rossumc0b618a1997-05-02 03:12:38 +00003172static PyObject *
Martin v. Löwisda86fcc2007-09-10 07:59:54 +00003173long_rshift(PyLongObject *a, PyLongObject *b)
Guido van Rossumc6913e71991-11-19 20:26:46 +00003174{
Neil Schemenauerba872e22001-01-04 01:46:03 +00003175 PyLongObject *z = NULL;
Guido van Rossumc6913e71991-11-19 20:26:46 +00003176 long shiftby;
Martin v. Löwis18e16552006-02-15 17:27:45 +00003177 Py_ssize_t newsize, wordshift, loshift, hishift, i, j;
Guido van Rossumc6913e71991-11-19 20:26:46 +00003178 digit lomask, himask;
Tim Peters5af4e6c2002-08-12 02:31:19 +00003179
Martin v. Löwisda86fcc2007-09-10 07:59:54 +00003180 CHECK_BINOP(a, b);
Neil Schemenauerba872e22001-01-04 01:46:03 +00003181
Christian Heimes90aa7642007-12-19 02:45:37 +00003182 if (Py_SIZE(a) < 0) {
Guido van Rossum4c260ff1992-01-14 18:36:43 +00003183 /* Right shifting negative numbers is harder */
Neil Schemenauerba872e22001-01-04 01:46:03 +00003184 PyLongObject *a1, *a2;
Guido van Rossumc0b618a1997-05-02 03:12:38 +00003185 a1 = (PyLongObject *) long_invert(a);
Neil Schemenauerba872e22001-01-04 01:46:03 +00003186 if (a1 == NULL)
3187 goto rshift_error;
Guido van Rossumc0b618a1997-05-02 03:12:38 +00003188 a2 = (PyLongObject *) long_rshift(a1, b);
3189 Py_DECREF(a1);
Neil Schemenauerba872e22001-01-04 01:46:03 +00003190 if (a2 == NULL)
3191 goto rshift_error;
3192 z = (PyLongObject *) long_invert(a2);
Guido van Rossumc0b618a1997-05-02 03:12:38 +00003193 Py_DECREF(a2);
Guido van Rossumc6913e71991-11-19 20:26:46 +00003194 }
Neil Schemenauerba872e22001-01-04 01:46:03 +00003195 else {
Tim Peters5af4e6c2002-08-12 02:31:19 +00003196
Neil Schemenauerba872e22001-01-04 01:46:03 +00003197 shiftby = PyLong_AsLong((PyObject *)b);
3198 if (shiftby == -1L && PyErr_Occurred())
3199 goto rshift_error;
3200 if (shiftby < 0) {
3201 PyErr_SetString(PyExc_ValueError,
3202 "negative shift count");
3203 goto rshift_error;
3204 }
Martin v. Löwis9f2e3462007-07-21 17:22:18 +00003205 wordshift = shiftby / PyLong_SHIFT;
Christian Heimes90aa7642007-12-19 02:45:37 +00003206 newsize = ABS(Py_SIZE(a)) - wordshift;
Neil Schemenauerba872e22001-01-04 01:46:03 +00003207 if (newsize <= 0) {
3208 z = _PyLong_New(0);
Neil Schemenauerba872e22001-01-04 01:46:03 +00003209 return (PyObject *)z;
3210 }
Martin v. Löwis9f2e3462007-07-21 17:22:18 +00003211 loshift = shiftby % PyLong_SHIFT;
3212 hishift = PyLong_SHIFT - loshift;
Neil Schemenauerba872e22001-01-04 01:46:03 +00003213 lomask = ((digit)1 << hishift) - 1;
Martin v. Löwis9f2e3462007-07-21 17:22:18 +00003214 himask = PyLong_MASK ^ lomask;
Neil Schemenauerba872e22001-01-04 01:46:03 +00003215 z = _PyLong_New(newsize);
3216 if (z == NULL)
3217 goto rshift_error;
Christian Heimes90aa7642007-12-19 02:45:37 +00003218 if (Py_SIZE(a) < 0)
3219 Py_SIZE(z) = -(Py_SIZE(z));
Neil Schemenauerba872e22001-01-04 01:46:03 +00003220 for (i = 0, j = wordshift; i < newsize; i++, j++) {
3221 z->ob_digit[i] = (a->ob_digit[j] >> loshift) & lomask;
3222 if (i+1 < newsize)
3223 z->ob_digit[i] |=
3224 (a->ob_digit[j+1] << hishift) & himask;
3225 }
3226 z = long_normalize(z);
Guido van Rossumc6913e71991-11-19 20:26:46 +00003227 }
Neil Schemenauerba872e22001-01-04 01:46:03 +00003228rshift_error:
Neil Schemenauerba872e22001-01-04 01:46:03 +00003229 return (PyObject *) z;
3230
Guido van Rossumc6913e71991-11-19 20:26:46 +00003231}
3232
Guido van Rossumc0b618a1997-05-02 03:12:38 +00003233static PyObject *
Neil Schemenauerba872e22001-01-04 01:46:03 +00003234long_lshift(PyObject *v, PyObject *w)
Guido van Rossumc6913e71991-11-19 20:26:46 +00003235{
Guido van Rossumf2e499b1997-03-16 00:37:59 +00003236 /* This version due to Tim Peters */
Martin v. Löwisda86fcc2007-09-10 07:59:54 +00003237 PyLongObject *a = (PyLongObject*)v;
3238 PyLongObject *b = (PyLongObject*)w;
Neil Schemenauerba872e22001-01-04 01:46:03 +00003239 PyLongObject *z = NULL;
Guido van Rossumc6913e71991-11-19 20:26:46 +00003240 long shiftby;
Martin v. Löwis18e16552006-02-15 17:27:45 +00003241 Py_ssize_t oldsize, newsize, wordshift, remshift, i, j;
Guido van Rossumf2e499b1997-03-16 00:37:59 +00003242 twodigits accum;
Tim Peters5af4e6c2002-08-12 02:31:19 +00003243
Martin v. Löwisda86fcc2007-09-10 07:59:54 +00003244 CHECK_BINOP(a, b);
Neil Schemenauerba872e22001-01-04 01:46:03 +00003245
Guido van Rossumc0b618a1997-05-02 03:12:38 +00003246 shiftby = PyLong_AsLong((PyObject *)b);
3247 if (shiftby == -1L && PyErr_Occurred())
Neil Schemenauerba872e22001-01-04 01:46:03 +00003248 goto lshift_error;
Guido van Rossumc6913e71991-11-19 20:26:46 +00003249 if (shiftby < 0) {
Guido van Rossumc0b618a1997-05-02 03:12:38 +00003250 PyErr_SetString(PyExc_ValueError, "negative shift count");
Neil Schemenauerba872e22001-01-04 01:46:03 +00003251 goto lshift_error;
Guido van Rossumc6913e71991-11-19 20:26:46 +00003252 }
Guido van Rossumf2e499b1997-03-16 00:37:59 +00003253 if ((long)(int)shiftby != shiftby) {
Guido van Rossumc0b618a1997-05-02 03:12:38 +00003254 PyErr_SetString(PyExc_ValueError,
3255 "outrageous left shift count");
Neil Schemenauerba872e22001-01-04 01:46:03 +00003256 goto lshift_error;
Guido van Rossumc6913e71991-11-19 20:26:46 +00003257 }
Martin v. Löwis9f2e3462007-07-21 17:22:18 +00003258 /* wordshift, remshift = divmod(shiftby, PyLong_SHIFT) */
3259 wordshift = (int)shiftby / PyLong_SHIFT;
3260 remshift = (int)shiftby - wordshift * PyLong_SHIFT;
Guido van Rossumf2e499b1997-03-16 00:37:59 +00003261
Christian Heimes90aa7642007-12-19 02:45:37 +00003262 oldsize = ABS(Py_SIZE(a));
Guido van Rossumf2e499b1997-03-16 00:37:59 +00003263 newsize = oldsize + wordshift;
3264 if (remshift)
3265 ++newsize;
Guido van Rossumc0b618a1997-05-02 03:12:38 +00003266 z = _PyLong_New(newsize);
Guido van Rossumc6913e71991-11-19 20:26:46 +00003267 if (z == NULL)
Neil Schemenauerba872e22001-01-04 01:46:03 +00003268 goto lshift_error;
Christian Heimes90aa7642007-12-19 02:45:37 +00003269 if (Py_SIZE(a) < 0)
Guido van Rossumddefaf32007-01-14 03:31:43 +00003270 NEGATE(z);
Guido van Rossumc6913e71991-11-19 20:26:46 +00003271 for (i = 0; i < wordshift; i++)
3272 z->ob_digit[i] = 0;
Tim Peters5af4e6c2002-08-12 02:31:19 +00003273 accum = 0;
Guido van Rossumf2e499b1997-03-16 00:37:59 +00003274 for (i = wordshift, j = 0; j < oldsize; i++, j++) {
Tim Peters0d2d87d2002-08-20 19:00:22 +00003275 accum |= (twodigits)a->ob_digit[j] << remshift;
Martin v. Löwis9f2e3462007-07-21 17:22:18 +00003276 z->ob_digit[i] = (digit)(accum & PyLong_MASK);
3277 accum >>= PyLong_SHIFT;
Guido van Rossumc6913e71991-11-19 20:26:46 +00003278 }
Guido van Rossumf2e499b1997-03-16 00:37:59 +00003279 if (remshift)
3280 z->ob_digit[newsize-1] = (digit)accum;
Tim Peters5af4e6c2002-08-12 02:31:19 +00003281 else
Guido van Rossumf2e499b1997-03-16 00:37:59 +00003282 assert(!accum);
Neil Schemenauerba872e22001-01-04 01:46:03 +00003283 z = long_normalize(z);
3284lshift_error:
Neil Schemenauerba872e22001-01-04 01:46:03 +00003285 return (PyObject *) z;
Guido van Rossumc6913e71991-11-19 20:26:46 +00003286}
3287
Guido van Rossum4c260ff1992-01-14 18:36:43 +00003288
3289/* Bitwise and/xor/or operations */
3290
Guido van Rossumc0b618a1997-05-02 03:12:38 +00003291static PyObject *
Tim Peters9f688bf2000-07-07 15:53:28 +00003292long_bitwise(PyLongObject *a,
3293 int op, /* '&', '|', '^' */
3294 PyLongObject *b)
Guido van Rossumc6913e71991-11-19 20:26:46 +00003295{
Martin v. Löwis9f2e3462007-07-21 17:22:18 +00003296 digit maska, maskb; /* 0 or PyLong_MASK */
Guido van Rossum4c260ff1992-01-14 18:36:43 +00003297 int negz;
Martin v. Löwis18e16552006-02-15 17:27:45 +00003298 Py_ssize_t size_a, size_b, size_z;
Guido van Rossumc0b618a1997-05-02 03:12:38 +00003299 PyLongObject *z;
Guido van Rossumc6913e71991-11-19 20:26:46 +00003300 int i;
Guido van Rossum8b27d921992-03-27 17:27:05 +00003301 digit diga, digb;
Guido van Rossumc0b618a1997-05-02 03:12:38 +00003302 PyObject *v;
Tim Peters5af4e6c2002-08-12 02:31:19 +00003303
Christian Heimes90aa7642007-12-19 02:45:37 +00003304 if (Py_SIZE(a) < 0) {
Guido van Rossumc0b618a1997-05-02 03:12:38 +00003305 a = (PyLongObject *) long_invert(a);
Hye-Shik Chang4af5c8c2006-03-07 15:39:21 +00003306 if (a == NULL)
3307 return NULL;
Martin v. Löwis9f2e3462007-07-21 17:22:18 +00003308 maska = PyLong_MASK;
Guido van Rossumc6913e71991-11-19 20:26:46 +00003309 }
Guido van Rossum4c260ff1992-01-14 18:36:43 +00003310 else {
Guido van Rossumc0b618a1997-05-02 03:12:38 +00003311 Py_INCREF(a);
Guido van Rossum4c260ff1992-01-14 18:36:43 +00003312 maska = 0;
Guido van Rossumafbb8db1991-12-31 13:14:13 +00003313 }
Christian Heimes90aa7642007-12-19 02:45:37 +00003314 if (Py_SIZE(b) < 0) {
Guido van Rossumc0b618a1997-05-02 03:12:38 +00003315 b = (PyLongObject *) long_invert(b);
Hye-Shik Chang4af5c8c2006-03-07 15:39:21 +00003316 if (b == NULL) {
3317 Py_DECREF(a);
3318 return NULL;
3319 }
Martin v. Löwis9f2e3462007-07-21 17:22:18 +00003320 maskb = PyLong_MASK;
Guido van Rossumc6913e71991-11-19 20:26:46 +00003321 }
Guido van Rossum4c260ff1992-01-14 18:36:43 +00003322 else {
Guido van Rossumc0b618a1997-05-02 03:12:38 +00003323 Py_INCREF(b);
Guido van Rossum4c260ff1992-01-14 18:36:43 +00003324 maskb = 0;
3325 }
Tim Peters5af4e6c2002-08-12 02:31:19 +00003326
Guido van Rossum4c260ff1992-01-14 18:36:43 +00003327 negz = 0;
3328 switch (op) {
3329 case '^':
3330 if (maska != maskb) {
Martin v. Löwis9f2e3462007-07-21 17:22:18 +00003331 maska ^= PyLong_MASK;
Guido van Rossum4c260ff1992-01-14 18:36:43 +00003332 negz = -1;
3333 }
3334 break;
Guido van Rossumeb1fafc1994-08-29 12:47:19 +00003335 case '&':
Guido van Rossum4c260ff1992-01-14 18:36:43 +00003336 if (maska && maskb) {
3337 op = '|';
Martin v. Löwis9f2e3462007-07-21 17:22:18 +00003338 maska ^= PyLong_MASK;
3339 maskb ^= PyLong_MASK;
Guido van Rossum4c260ff1992-01-14 18:36:43 +00003340 negz = -1;
3341 }
3342 break;
3343 case '|':
3344 if (maska || maskb) {
3345 op = '&';
Martin v. Löwis9f2e3462007-07-21 17:22:18 +00003346 maska ^= PyLong_MASK;
3347 maskb ^= PyLong_MASK;
Guido van Rossum4c260ff1992-01-14 18:36:43 +00003348 negz = -1;
3349 }
3350 break;
Guido van Rossumc6913e71991-11-19 20:26:46 +00003351 }
Tim Peters5af4e6c2002-08-12 02:31:19 +00003352
Guido van Rossumbd3a5271998-08-11 15:04:47 +00003353 /* JRH: The original logic here was to allocate the result value (z)
3354 as the longer of the two operands. However, there are some cases
3355 where the result is guaranteed to be shorter than that: AND of two
3356 positives, OR of two negatives: use the shorter number. AND with
3357 mixed signs: use the positive number. OR with mixed signs: use the
3358 negative number. After the transformations above, op will be '&'
3359 iff one of these cases applies, and mask will be non-0 for operands
3360 whose length should be ignored.
3361 */
3362
Christian Heimes90aa7642007-12-19 02:45:37 +00003363 size_a = Py_SIZE(a);
3364 size_b = Py_SIZE(b);
Guido van Rossumbd3a5271998-08-11 15:04:47 +00003365 size_z = op == '&'
3366 ? (maska
3367 ? size_b
3368 : (maskb ? size_a : MIN(size_a, size_b)))
3369 : MAX(size_a, size_b);
3370 z = _PyLong_New(size_z);
Hye-Shik Chang4af5c8c2006-03-07 15:39:21 +00003371 if (z == NULL) {
Thomas Wouters0e3f5912006-08-11 14:57:12 +00003372 Py_DECREF(a);
3373 Py_DECREF(b);
Guido van Rossumbd3a5271998-08-11 15:04:47 +00003374 return NULL;
3375 }
Tim Peters5af4e6c2002-08-12 02:31:19 +00003376
Guido van Rossum4c260ff1992-01-14 18:36:43 +00003377 for (i = 0; i < size_z; ++i) {
3378 diga = (i < size_a ? a->ob_digit[i] : 0) ^ maska;
3379 digb = (i < size_b ? b->ob_digit[i] : 0) ^ maskb;
3380 switch (op) {
3381 case '&': z->ob_digit[i] = diga & digb; break;
3382 case '|': z->ob_digit[i] = diga | digb; break;
3383 case '^': z->ob_digit[i] = diga ^ digb; break;
3384 }
Guido van Rossumafbb8db1991-12-31 13:14:13 +00003385 }
Tim Peters5af4e6c2002-08-12 02:31:19 +00003386
Guido van Rossumc0b618a1997-05-02 03:12:38 +00003387 Py_DECREF(a);
3388 Py_DECREF(b);
Guido van Rossum4c260ff1992-01-14 18:36:43 +00003389 z = long_normalize(z);
3390 if (negz == 0)
Guido van Rossumc0b618a1997-05-02 03:12:38 +00003391 return (PyObject *) z;
Guido van Rossum4c260ff1992-01-14 18:36:43 +00003392 v = long_invert(z);
Guido van Rossumc0b618a1997-05-02 03:12:38 +00003393 Py_DECREF(z);
Guido van Rossum4c260ff1992-01-14 18:36:43 +00003394 return v;
Guido van Rossumc6913e71991-11-19 20:26:46 +00003395}
3396
Guido van Rossumc0b618a1997-05-02 03:12:38 +00003397static PyObject *
Martin v. Löwisda86fcc2007-09-10 07:59:54 +00003398long_and(PyObject *a, PyObject *b)
Guido van Rossumc6913e71991-11-19 20:26:46 +00003399{
Neil Schemenauerba872e22001-01-04 01:46:03 +00003400 PyObject *c;
Martin v. Löwisda86fcc2007-09-10 07:59:54 +00003401 CHECK_BINOP(a, b);
3402 c = long_bitwise((PyLongObject*)a, '&', (PyLongObject*)b);
Neil Schemenauerba872e22001-01-04 01:46:03 +00003403 return c;
Guido van Rossumc6913e71991-11-19 20:26:46 +00003404}
3405
Guido van Rossumc0b618a1997-05-02 03:12:38 +00003406static PyObject *
Martin v. Löwisda86fcc2007-09-10 07:59:54 +00003407long_xor(PyObject *a, PyObject *b)
Guido van Rossumc6913e71991-11-19 20:26:46 +00003408{
Neil Schemenauerba872e22001-01-04 01:46:03 +00003409 PyObject *c;
Martin v. Löwisda86fcc2007-09-10 07:59:54 +00003410 CHECK_BINOP(a, b);
3411 c = long_bitwise((PyLongObject*)a, '^', (PyLongObject*)b);
Neil Schemenauerba872e22001-01-04 01:46:03 +00003412 return c;
Guido van Rossumc6913e71991-11-19 20:26:46 +00003413}
3414
Guido van Rossumc0b618a1997-05-02 03:12:38 +00003415static PyObject *
Martin v. Löwisda86fcc2007-09-10 07:59:54 +00003416long_or(PyObject *a, PyObject *b)
Guido van Rossumc6913e71991-11-19 20:26:46 +00003417{
Neil Schemenauerba872e22001-01-04 01:46:03 +00003418 PyObject *c;
Martin v. Löwisda86fcc2007-09-10 07:59:54 +00003419 CHECK_BINOP(a, b);
3420 c = long_bitwise((PyLongObject*)a, '|', (PyLongObject*)b);
Neil Schemenauerba872e22001-01-04 01:46:03 +00003421 return c;
Guido van Rossum23d6f0e1991-05-14 12:06:49 +00003422}
3423
Guido van Rossumc0b618a1997-05-02 03:12:38 +00003424static PyObject *
Tim Peters9f688bf2000-07-07 15:53:28 +00003425long_long(PyObject *v)
Guido van Rossum1899c2e1992-09-12 11:09:23 +00003426{
Brett Cannonc3647ac2005-04-26 03:45:26 +00003427 if (PyLong_CheckExact(v))
3428 Py_INCREF(v);
3429 else
3430 v = _PyLong_Copy((PyLongObject *)v);
Guido van Rossum1899c2e1992-09-12 11:09:23 +00003431 return v;
3432}
3433
Guido van Rossumc0b618a1997-05-02 03:12:38 +00003434static PyObject *
Tim Peters9f688bf2000-07-07 15:53:28 +00003435long_float(PyObject *v)
Guido van Rossum1899c2e1992-09-12 11:09:23 +00003436{
Guido van Rossum09e6ad01997-02-14 22:54:21 +00003437 double result;
Guido van Rossumc0b618a1997-05-02 03:12:38 +00003438 result = PyLong_AsDouble(v);
Tim Peters9fffa3e2001-09-04 05:14:19 +00003439 if (result == -1.0 && PyErr_Occurred())
3440 return NULL;
Guido van Rossumc0b618a1997-05-02 03:12:38 +00003441 return PyFloat_FromDouble(result);
Guido van Rossum1899c2e1992-09-12 11:09:23 +00003442}
3443
Guido van Rossumc0b618a1997-05-02 03:12:38 +00003444static PyObject *
Guido van Rossumbef14172001-08-29 15:47:46 +00003445long_subtype_new(PyTypeObject *type, PyObject *args, PyObject *kwds);
Guido van Rossum1899c2e1992-09-12 11:09:23 +00003446
Tim Peters6d6c1a32001-08-02 04:15:00 +00003447static PyObject *
3448long_new(PyTypeObject *type, PyObject *args, PyObject *kwds)
3449{
3450 PyObject *x = NULL;
3451 int base = -909; /* unlikely! */
Martin v. Löwis15e62742006-02-27 16:46:16 +00003452 static char *kwlist[] = {"x", "base", 0};
Tim Peters6d6c1a32001-08-02 04:15:00 +00003453
Guido van Rossumbef14172001-08-29 15:47:46 +00003454 if (type != &PyLong_Type)
3455 return long_subtype_new(type, args, kwds); /* Wimp out */
Guido van Rossumddefaf32007-01-14 03:31:43 +00003456 if (!PyArg_ParseTupleAndKeywords(args, kwds, "|Oi:int", kwlist,
Tim Peters6d6c1a32001-08-02 04:15:00 +00003457 &x, &base))
3458 return NULL;
3459 if (x == NULL)
3460 return PyLong_FromLong(0L);
3461 if (base == -909)
3462 return PyNumber_Long(x);
Guido van Rossum98297ee2007-11-06 21:34:58 +00003463 else if (PyUnicode_Check(x))
3464 return PyLong_FromUnicode(PyUnicode_AS_UNICODE(x),
3465 PyUnicode_GET_SIZE(x),
3466 base);
3467 else if (PyBytes_Check(x) || PyString_Check(x)) {
Guido van Rossumd8faa362007-04-27 19:54:29 +00003468 /* Since PyLong_FromString doesn't have a length parameter,
3469 * check here for possible NULs in the string. */
Guido van Rossum98297ee2007-11-06 21:34:58 +00003470 char *string;
Christian Heimes90aa7642007-12-19 02:45:37 +00003471 int size = Py_SIZE(x);
Guido van Rossum98297ee2007-11-06 21:34:58 +00003472 if (PyBytes_Check(x))
3473 string = PyBytes_AS_STRING(x);
3474 else
3475 string = PyString_AS_STRING(x);
Guido van Rossum4581ae52007-05-22 21:56:47 +00003476 if (strlen(string) != size) {
Guido van Rossum25236212007-08-22 23:28:23 +00003477 /* We only see this if there's a null byte in x,
Guido van Rossum98297ee2007-11-06 21:34:58 +00003478 x is a bytes or buffer, *and* a base is given. */
Guido van Rossumd8faa362007-04-27 19:54:29 +00003479 PyErr_Format(PyExc_ValueError,
Guido van Rossum25236212007-08-22 23:28:23 +00003480 "invalid literal for int() with base %d: %R",
3481 base, x);
Guido van Rossumd8faa362007-04-27 19:54:29 +00003482 return NULL;
Guido van Rossumddefaf32007-01-14 03:31:43 +00003483 }
Guido van Rossum4581ae52007-05-22 21:56:47 +00003484 return PyLong_FromString(string, NULL, base);
Guido van Rossumddefaf32007-01-14 03:31:43 +00003485 }
Tim Peters6d6c1a32001-08-02 04:15:00 +00003486 else {
3487 PyErr_SetString(PyExc_TypeError,
Guido van Rossumddefaf32007-01-14 03:31:43 +00003488 "int() can't convert non-string with explicit base");
Tim Peters6d6c1a32001-08-02 04:15:00 +00003489 return NULL;
3490 }
3491}
3492
Guido van Rossumbef14172001-08-29 15:47:46 +00003493/* Wimpy, slow approach to tp_new calls for subtypes of long:
3494 first create a regular long from whatever arguments we got,
3495 then allocate a subtype instance and initialize it from
3496 the regular long. The regular long is then thrown away.
3497*/
3498static PyObject *
3499long_subtype_new(PyTypeObject *type, PyObject *args, PyObject *kwds)
3500{
Thomas Wouters49fd7fa2006-04-21 10:40:58 +00003501 PyLongObject *tmp, *newobj;
Martin v. Löwis18e16552006-02-15 17:27:45 +00003502 Py_ssize_t i, n;
Guido van Rossumbef14172001-08-29 15:47:46 +00003503
3504 assert(PyType_IsSubtype(type, &PyLong_Type));
3505 tmp = (PyLongObject *)long_new(&PyLong_Type, args, kwds);
3506 if (tmp == NULL)
3507 return NULL;
Tim Peters64b5ce32001-09-10 20:52:51 +00003508 assert(PyLong_CheckExact(tmp));
Christian Heimes90aa7642007-12-19 02:45:37 +00003509 n = Py_SIZE(tmp);
Guido van Rossumbef14172001-08-29 15:47:46 +00003510 if (n < 0)
3511 n = -n;
Thomas Wouters49fd7fa2006-04-21 10:40:58 +00003512 newobj = (PyLongObject *)type->tp_alloc(type, n);
3513 if (newobj == NULL) {
Raymond Hettingerf4667932003-06-28 20:04:25 +00003514 Py_DECREF(tmp);
Guido van Rossumbef14172001-08-29 15:47:46 +00003515 return NULL;
Raymond Hettingerf4667932003-06-28 20:04:25 +00003516 }
Thomas Wouters49fd7fa2006-04-21 10:40:58 +00003517 assert(PyLong_Check(newobj));
Christian Heimes90aa7642007-12-19 02:45:37 +00003518 Py_SIZE(newobj) = Py_SIZE(tmp);
Guido van Rossumbef14172001-08-29 15:47:46 +00003519 for (i = 0; i < n; i++)
Thomas Wouters49fd7fa2006-04-21 10:40:58 +00003520 newobj->ob_digit[i] = tmp->ob_digit[i];
Guido van Rossumbef14172001-08-29 15:47:46 +00003521 Py_DECREF(tmp);
Thomas Wouters49fd7fa2006-04-21 10:40:58 +00003522 return (PyObject *)newobj;
Guido van Rossumbef14172001-08-29 15:47:46 +00003523}
3524
Guido van Rossum5d9113d2003-01-29 17:58:45 +00003525static PyObject *
3526long_getnewargs(PyLongObject *v)
3527{
3528 return Py_BuildValue("(N)", _PyLong_Copy(v));
3529}
3530
Guido van Rossumb43daf72007-08-01 18:08:08 +00003531static PyObject *
3532long_getN(PyLongObject *v, void *context) {
3533 return PyLong_FromLong((intptr_t)context);
3534}
3535
Guido van Rossum2fa33db2007-08-23 22:07:24 +00003536static PyObject *
Eric Smith8c663262007-08-25 02:26:07 +00003537long__format__(PyObject *self, PyObject *args)
3538{
3539 /* when back porting this to 2.6, check type of the format_spec
3540 and call either unicode_long__format__ or
3541 string_long__format__ */
3542 return unicode_long__format__(self, args);
3543}
3544
3545
3546static PyObject *
Guido van Rossum2fa33db2007-08-23 22:07:24 +00003547long_round(PyObject *self, PyObject *args)
3548{
3549#define UNDEF_NDIGITS (-0x7fffffff) /* Unlikely ndigits value */
3550 int ndigits = UNDEF_NDIGITS;
3551 double x;
3552 PyObject *res;
3553
3554 if (!PyArg_ParseTuple(args, "|i", &ndigits))
3555 return NULL;
3556
3557 if (ndigits == UNDEF_NDIGITS)
3558 return long_long(self);
3559
3560 /* If called with two args, defer to float.__round__(). */
3561 x = PyLong_AsDouble(self);
3562 if (x == -1.0 && PyErr_Occurred())
3563 return NULL;
3564 self = PyFloat_FromDouble(x);
3565 if (self == NULL)
3566 return NULL;
3567 res = PyObject_CallMethod(self, "__round__", "i", ndigits);
3568 Py_DECREF(self);
3569 return res;
3570#undef UNDEF_NDIGITS
3571}
3572
Guido van Rossum5d9113d2003-01-29 17:58:45 +00003573static PyMethodDef long_methods[] = {
Guido van Rossumb43daf72007-08-01 18:08:08 +00003574 {"conjugate", (PyCFunction)long_long, METH_NOARGS,
3575 "Returns self, the complex conjugate of any int."},
Guido van Rossum2fa33db2007-08-23 22:07:24 +00003576 {"__trunc__", (PyCFunction)long_long, METH_NOARGS,
3577 "Truncating an Integral returns itself."},
3578 {"__floor__", (PyCFunction)long_long, METH_NOARGS,
3579 "Flooring an Integral returns itself."},
3580 {"__ceil__", (PyCFunction)long_long, METH_NOARGS,
3581 "Ceiling of an Integral returns itself."},
3582 {"__round__", (PyCFunction)long_round, METH_VARARGS,
3583 "Rounding an Integral returns itself.\n"
3584 "Rounding with an ndigits arguments defers to float.__round__."},
Guido van Rossum5d9113d2003-01-29 17:58:45 +00003585 {"__getnewargs__", (PyCFunction)long_getnewargs, METH_NOARGS},
Eric Smith8c663262007-08-25 02:26:07 +00003586 {"__format__", (PyCFunction)long__format__, METH_VARARGS},
Guido van Rossum5d9113d2003-01-29 17:58:45 +00003587 {NULL, NULL} /* sentinel */
3588};
3589
Guido van Rossumb43daf72007-08-01 18:08:08 +00003590static PyGetSetDef long_getset[] = {
3591 {"real",
3592 (getter)long_long, (setter)NULL,
3593 "the real part of a complex number",
3594 NULL},
3595 {"imag",
3596 (getter)long_getN, (setter)NULL,
3597 "the imaginary part of a complex number",
3598 (void*)0},
3599 {"numerator",
3600 (getter)long_long, (setter)NULL,
3601 "the numerator of a rational number in lowest terms",
3602 NULL},
3603 {"denominator",
3604 (getter)long_getN, (setter)NULL,
3605 "the denominator of a rational number in lowest terms",
3606 (void*)1},
3607 {NULL} /* Sentinel */
3608};
3609
Martin v. Löwis14f8b4c2002-06-13 20:33:02 +00003610PyDoc_STRVAR(long_doc,
Guido van Rossumddefaf32007-01-14 03:31:43 +00003611"int(x[, base]) -> integer\n\
Tim Peters6d6c1a32001-08-02 04:15:00 +00003612\n\
Guido van Rossumddefaf32007-01-14 03:31:43 +00003613Convert a string or number to an integer, if possible. A floating\n\
Tim Peters6d6c1a32001-08-02 04:15:00 +00003614point argument will be truncated towards zero (this does not include a\n\
3615string representation of a floating point number!) When converting a\n\
3616string, use the optional base. It is an error to supply a base when\n\
Martin v. Löwis14f8b4c2002-06-13 20:33:02 +00003617converting a non-string.");
Tim Peters6d6c1a32001-08-02 04:15:00 +00003618
Guido van Rossumc0b618a1997-05-02 03:12:38 +00003619static PyNumberMethods long_as_number = {
Tim Peters9f688bf2000-07-07 15:53:28 +00003620 (binaryfunc) long_add, /*nb_add*/
3621 (binaryfunc) long_sub, /*nb_subtract*/
3622 (binaryfunc) long_mul, /*nb_multiply*/
Thomas Wouters49fd7fa2006-04-21 10:40:58 +00003623 long_mod, /*nb_remainder*/
3624 long_divmod, /*nb_divmod*/
3625 long_pow, /*nb_power*/
Tim Peters9f688bf2000-07-07 15:53:28 +00003626 (unaryfunc) long_neg, /*nb_negative*/
Guido van Rossumb43daf72007-08-01 18:08:08 +00003627 (unaryfunc) long_long, /*tp_positive*/
Tim Peters9f688bf2000-07-07 15:53:28 +00003628 (unaryfunc) long_abs, /*tp_absolute*/
Jack Diederich4dafcc42006-11-28 19:15:13 +00003629 (inquiry) long_bool, /*tp_bool*/
Tim Peters9f688bf2000-07-07 15:53:28 +00003630 (unaryfunc) long_invert, /*nb_invert*/
Thomas Wouters49fd7fa2006-04-21 10:40:58 +00003631 long_lshift, /*nb_lshift*/
Tim Peters9f688bf2000-07-07 15:53:28 +00003632 (binaryfunc) long_rshift, /*nb_rshift*/
Thomas Wouters49fd7fa2006-04-21 10:40:58 +00003633 long_and, /*nb_and*/
3634 long_xor, /*nb_xor*/
3635 long_or, /*nb_or*/
Neil Schemenauer16c70752007-09-21 20:19:23 +00003636 0, /*nb_reserved*/
Guido van Rossumb43daf72007-08-01 18:08:08 +00003637 long_long, /*nb_int*/
Thomas Wouters49fd7fa2006-04-21 10:40:58 +00003638 long_long, /*nb_long*/
3639 long_float, /*nb_float*/
Guido van Rossumcd16bf62007-06-13 18:07:49 +00003640 0, /*nb_oct*/ /* not used */
3641 0, /*nb_hex*/ /* not used */
Guido van Rossum4668b002001-08-08 05:00:18 +00003642 0, /* nb_inplace_add */
3643 0, /* nb_inplace_subtract */
3644 0, /* nb_inplace_multiply */
Guido van Rossum4668b002001-08-08 05:00:18 +00003645 0, /* nb_inplace_remainder */
3646 0, /* nb_inplace_power */
3647 0, /* nb_inplace_lshift */
3648 0, /* nb_inplace_rshift */
3649 0, /* nb_inplace_and */
3650 0, /* nb_inplace_xor */
3651 0, /* nb_inplace_or */
Thomas Wouters49fd7fa2006-04-21 10:40:58 +00003652 long_div, /* nb_floor_divide */
Guido van Rossum4668b002001-08-08 05:00:18 +00003653 long_true_divide, /* nb_true_divide */
3654 0, /* nb_inplace_floor_divide */
3655 0, /* nb_inplace_true_divide */
Thomas Wouters00ee7ba2006-08-21 19:07:27 +00003656 long_long, /* nb_index */
Guido van Rossumedcc38a1991-05-05 20:09:44 +00003657};
3658
Guido van Rossumc0b618a1997-05-02 03:12:38 +00003659PyTypeObject PyLong_Type = {
Martin v. Löwis9f2e3462007-07-21 17:22:18 +00003660 PyVarObject_HEAD_INIT(&PyType_Type, 0)
Guido van Rossumddefaf32007-01-14 03:31:43 +00003661 "int", /* tp_name */
3662 /* See _PyLong_New for why this isn't
3663 sizeof(PyLongObject) - sizeof(digit) */
3664 sizeof(PyVarObject), /* tp_basicsize */
Tim Peters6d6c1a32001-08-02 04:15:00 +00003665 sizeof(digit), /* tp_itemsize */
Thomas Wouters49fd7fa2006-04-21 10:40:58 +00003666 long_dealloc, /* tp_dealloc */
Tim Peters6d6c1a32001-08-02 04:15:00 +00003667 0, /* tp_print */
3668 0, /* tp_getattr */
3669 0, /* tp_setattr */
Guido van Rossum47b9ff62006-08-24 00:41:19 +00003670 0, /* tp_compare */
Thomas Wouters49fd7fa2006-04-21 10:40:58 +00003671 long_repr, /* tp_repr */
Tim Peters6d6c1a32001-08-02 04:15:00 +00003672 &long_as_number, /* tp_as_number */
3673 0, /* tp_as_sequence */
3674 0, /* tp_as_mapping */
3675 (hashfunc)long_hash, /* tp_hash */
3676 0, /* tp_call */
Guido van Rossumddefaf32007-01-14 03:31:43 +00003677 long_repr, /* tp_str */
Tim Peters6d6c1a32001-08-02 04:15:00 +00003678 PyObject_GenericGetAttr, /* tp_getattro */
3679 0, /* tp_setattro */
3680 0, /* tp_as_buffer */
Thomas Wouters27d517b2007-02-25 20:39:11 +00003681 Py_TPFLAGS_DEFAULT | Py_TPFLAGS_BASETYPE |
3682 Py_TPFLAGS_LONG_SUBCLASS, /* tp_flags */
Tim Peters6d6c1a32001-08-02 04:15:00 +00003683 long_doc, /* tp_doc */
3684 0, /* tp_traverse */
3685 0, /* tp_clear */
Guido van Rossum47b9ff62006-08-24 00:41:19 +00003686 long_richcompare, /* tp_richcompare */
Tim Peters6d6c1a32001-08-02 04:15:00 +00003687 0, /* tp_weaklistoffset */
3688 0, /* tp_iter */
3689 0, /* tp_iternext */
Guido van Rossum5d9113d2003-01-29 17:58:45 +00003690 long_methods, /* tp_methods */
Tim Peters6d6c1a32001-08-02 04:15:00 +00003691 0, /* tp_members */
Guido van Rossumb43daf72007-08-01 18:08:08 +00003692 long_getset, /* tp_getset */
Tim Peters6d6c1a32001-08-02 04:15:00 +00003693 0, /* tp_base */
3694 0, /* tp_dict */
3695 0, /* tp_descr_get */
3696 0, /* tp_descr_set */
3697 0, /* tp_dictoffset */
3698 0, /* tp_init */
3699 0, /* tp_alloc */
3700 long_new, /* tp_new */
Neil Schemenaueraa769ae2002-04-12 02:44:10 +00003701 PyObject_Del, /* tp_free */
Guido van Rossumedcc38a1991-05-05 20:09:44 +00003702};
Guido van Rossumddefaf32007-01-14 03:31:43 +00003703
3704int
3705_PyLong_Init(void)
3706{
3707#if NSMALLNEGINTS + NSMALLPOSINTS > 0
3708 int ival;
3709 PyLongObject *v = small_ints;
3710 for (ival = -NSMALLNEGINTS; ival < 0; ival++, v++) {
3711 PyObject_INIT(v, &PyLong_Type);
Christian Heimes90aa7642007-12-19 02:45:37 +00003712 Py_SIZE(v) = -1;
Guido van Rossumddefaf32007-01-14 03:31:43 +00003713 v->ob_digit[0] = -ival;
3714 }
3715 for (; ival < NSMALLPOSINTS; ival++, v++) {
3716 PyObject_INIT(v, &PyLong_Type);
Christian Heimes90aa7642007-12-19 02:45:37 +00003717 Py_SIZE(v) = ival ? 1 : 0;
Guido van Rossumddefaf32007-01-14 03:31:43 +00003718 v->ob_digit[0] = ival;
3719 }
3720#endif
3721 return 1;
3722}
3723
3724void
3725PyLong_Fini(void)
3726{
3727#if 0
3728 int i;
3729 /* This is currently not needed; the small integers
3730 are statically allocated */
3731#if NSMALLNEGINTS + NSMALLPOSINTS > 0
3732 PyIntObject **q;
3733
3734 i = NSMALLNEGINTS + NSMALLPOSINTS;
3735 q = small_ints;
3736 while (--i >= 0) {
3737 Py_XDECREF(*q);
3738 *q++ = NULL;
3739 }
3740#endif
3741#endif
3742}