|
27
|
1 /* Long (arbitrary precision) integer object implementation */
|
|
|
2
|
|
|
3 /* XXX The functional organization of this file is terrible */
|
|
|
4
|
|
|
5 #include "Python.h"
|
|
|
6 #include "longintrepr.h"
|
|
|
7
|
|
|
8
|
|
|
9 /* convert a PyLong of size 1, 0 or -1 to an sdigit */
|
|
|
10 #define MEDIUM_VALUE(x) (Py_SIZE(x) < 0 ? -(sdigit)(x)->ob_digit[0] : \
|
|
|
11 (Py_SIZE(x) == 0 ? (sdigit)0 : \
|
|
|
12 (sdigit)(x)->ob_digit[0]))
|
|
|
13 #define ABS(x) ((x) < 0 ? -(x) : (x))
|
|
|
14
|
|
|
15 /* If a freshly-allocated long is already shared, it must
|
|
|
16 be a small integer, so negating it must go to PyLong_FromLong */
|
|
|
17 #define NEGATE(x) \
|
|
|
18 do if (Py_REFCNT(x) == 1) Py_SIZE(x) = -Py_SIZE(x); \
|
|
|
19 else { PyObject* tmp=PyLong_FromLong(-MEDIUM_VALUE(x)); \
|
|
|
20 Py_DECREF(x); (x) = (PyLongObject*)tmp; } \
|
|
|
21 while(0)
|
|
|
22 /* For long multiplication, use the O(N**2) school algorithm unless
|
|
|
23 * both operands contain more than KARATSUBA_CUTOFF digits (this
|
|
|
24 * being an internal Python long digit, in base BASE).
|
|
|
25 */
|
|
|
26 #define KARATSUBA_CUTOFF 70
|
|
|
27 #define KARATSUBA_SQUARE_CUTOFF (2 * KARATSUBA_CUTOFF)
|
|
|
28
|
|
|
29 /* For exponentiation, use the binary left-to-right algorithm
|
|
|
30 * unless the exponent contains more than FIVEARY_CUTOFF digits.
|
|
|
31 * In that case, do 5 bits at a time. The potential drawback is that
|
|
|
32 * a table of 2**5 intermediate results is computed.
|
|
|
33 */
|
|
|
34 #define FIVEARY_CUTOFF 8
|
|
|
35
|
|
|
36 #undef MIN
|
|
|
37 #undef MAX
|
|
|
38 #define MAX(x, y) ((x) < (y) ? (y) : (x))
|
|
|
39 #define MIN(x, y) ((x) > (y) ? (y) : (x))
|
|
|
40
|
|
|
41 #define SIGCHECK(PyTryBlock) \
|
|
|
42 do { \
|
|
|
43 if (PyErr_CheckSignals()) PyTryBlock \
|
|
|
44 } while(0)
|
|
|
45
|
|
|
46 /* Normalize (remove leading zeros from) a long int object.
|
|
|
47 Doesn't attempt to free the storage--in most cases, due to the nature
|
|
|
48 of the algorithms used, this could save at most be one word anyway. */
|
|
|
49
|
|
|
50 static PyLongObject *
|
|
|
51 long_normalize(register PyLongObject *v)
|
|
|
52 {
|
|
|
53 Py_ssize_t j = ABS(Py_SIZE(v));
|
|
|
54 Py_ssize_t i = j;
|
|
|
55
|
|
|
56 while (i > 0 && v->ob_digit[i-1] == 0)
|
|
|
57 --i;
|
|
|
58 if (i != j)
|
|
|
59 Py_SIZE(v) = (Py_SIZE(v) < 0) ? -(i) : i;
|
|
|
60 return v;
|
|
|
61 }
|
|
|
62
|
|
|
63 /* Allocate a new long int object with size digits.
|
|
|
64 Return NULL and set exception if we run out of memory. */
|
|
|
65
|
|
|
66 #define MAX_LONG_DIGITS \
|
|
|
67 ((PY_SSIZE_T_MAX - offsetof(PyLongObject, ob_digit))/sizeof(digit))
|
|
|
68
|
|
|
69 PyLongObject *
|
|
|
70 _PyLong_New(Py_ssize_t size)
|
|
|
71 {
|
|
|
72 PyLongObject *result;
|
|
|
73 /* Number of bytes needed is: offsetof(PyLongObject, ob_digit) +
|
|
|
74 sizeof(digit)*size. Previous incarnations of this code used
|
|
|
75 sizeof(PyVarObject) instead of the offsetof, but this risks being
|
|
|
76 incorrect in the presence of padding between the PyVarObject header
|
|
|
77 and the digits. */
|
|
|
78 if (size > (Py_ssize_t)MAX_LONG_DIGITS) {
|
|
|
79 PyErr_SetString(PyExc_OverflowError,
|
|
|
80 "too many digits in integer");
|
|
|
81 return NULL;
|
|
|
82 }
|
|
|
83 result = PyObject_MALLOC(offsetof(PyLongObject, ob_digit) +
|
|
|
84 size*sizeof(digit));
|
|
|
85 if (!result) {
|
|
|
86 PyErr_NoMemory();
|
|
|
87 return NULL;
|
|
|
88 }
|
|
|
89 return (PyLongObject*)PyObject_INIT_VAR(result, &PyLong_Type, size);
|
|
|
90 }
|
|
|
91
|
|
|
92 PyObject *
|
|
|
93 _PyLong_Copy(PyLongObject *src)
|
|
|
94 {
|
|
|
95 PyLongObject *result;
|
|
|
96 Py_ssize_t i;
|
|
|
97
|
|
|
98 assert(src != NULL);
|
|
|
99 i = Py_SIZE(src);
|
|
|
100 if (i < 0)
|
|
|
101 i = -(i);
|
|
|
102 if (i < 2) {
|
|
|
103 sdigit ival = src->ob_digit[0];
|
|
|
104 if (Py_SIZE(src) < 0)
|
|
|
105 ival = -ival;
|
|
|
106 CHECK_SMALL_INT(ival);
|
|
|
107 }
|
|
|
108 result = _PyLong_New(i);
|
|
|
109 if (result != NULL) {
|
|
|
110 Py_SIZE(result) = Py_SIZE(src);
|
|
|
111 while (--i >= 0)
|
|
|
112 result->ob_digit[i] = src->ob_digit[i];
|
|
|
113 }
|
|
|
114 return (PyObject *)result;
|
|
|
115 }
|
|
|
116
|
|
|
117 /* Create a new long int object from a C long int */
|
|
|
118
|
|
|
119 PyObject *
|
|
|
120 PyLong_FromLong(long ival)
|
|
|
121 {
|
|
|
122 PyLongObject *v;
|
|
|
123 unsigned long abs_ival;
|
|
|
124 unsigned long t; /* unsigned so >> doesn't propagate sign bit */
|
|
|
125 int ndigits = 0;
|
|
|
126 int sign = 1;
|
|
|
127
|
|
|
128 if (ival < 0) {
|
|
|
129 /* negate: can't write this as abs_ival = -ival since that
|
|
|
130 invokes undefined behaviour when ival is LONG_MIN */
|
|
|
131 abs_ival = 0U-(unsigned long)ival;
|
|
|
132 sign = -1;
|
|
|
133 }
|
|
|
134 else {
|
|
|
135 abs_ival = (unsigned long)ival;
|
|
|
136 }
|
|
|
137
|
|
|
138 /* Fast path for single-digit ints */
|
|
|
139 if (!(abs_ival >> PyLong_SHIFT)) {
|
|
|
140 v = _PyLong_New(1);
|
|
|
141 if (v) {
|
|
|
142 Py_SIZE(v) = sign;
|
|
|
143 v->ob_digit[0] = Py_SAFE_DOWNCAST(
|
|
|
144 abs_ival, unsigned long, digit);
|
|
|
145 }
|
|
|
146 return (PyObject*)v;
|
|
|
147 }
|
|
|
148
|
|
|
149 #if PyLong_SHIFT==15
|
|
|
150 /* 2 digits */
|
|
|
151 if (!(abs_ival >> 2*PyLong_SHIFT)) {
|
|
|
152 v = _PyLong_New(2);
|
|
|
153 if (v) {
|
|
|
154 Py_SIZE(v) = 2*sign;
|
|
|
155 v->ob_digit[0] = Py_SAFE_DOWNCAST(
|
|
|
156 abs_ival & PyLong_MASK, unsigned long, digit);
|
|
|
157 v->ob_digit[1] = Py_SAFE_DOWNCAST(
|
|
|
158 abs_ival >> PyLong_SHIFT, unsigned long, digit);
|
|
|
159 }
|
|
|
160 return (PyObject*)v;
|
|
|
161 }
|
|
|
162 #endif
|
|
|
163
|
|
|
164 /* Larger numbers: loop to determine number of digits */
|
|
|
165 t = abs_ival;
|
|
|
166 while (t) {
|
|
|
167 ++ndigits;
|
|
|
168 t >>= PyLong_SHIFT;
|
|
|
169 }
|
|
|
170 v = _PyLong_New(ndigits);
|
|
|
171 if (v != NULL) {
|
|
|
172 digit *p = v->ob_digit;
|
|
|
173 Py_SIZE(v) = ndigits*sign;
|
|
|
174 t = abs_ival;
|
|
|
175 while (t) {
|
|
|
176 *p++ = Py_SAFE_DOWNCAST(
|
|
|
177 t & PyLong_MASK, unsigned long, digit);
|
|
|
178 t >>= PyLong_SHIFT;
|
|
|
179 }
|
|
|
180 }
|
|
|
181 return (PyObject *)v;
|
|
|
182 }
|
|
|
183
|
|
|
184 /* Create a new long int object from a C unsigned long int */
|
|
|
185
|
|
|
186 PyObject *
|
|
|
187 PyLong_FromUnsignedLong(unsigned long ival)
|
|
|
188 {
|
|
|
189 PyLongObject *v;
|
|
|
190 unsigned long t;
|
|
|
191 int ndigits = 0;
|
|
|
192
|
|
|
193 if (ival < PyLong_BASE)
|
|
|
194 return PyLong_FromLong(ival);
|
|
|
195 /* Count the number of Python digits. */
|
|
|
196 t = (unsigned long)ival;
|
|
|
197 while (t) {
|
|
|
198 ++ndigits;
|
|
|
199 t >>= PyLong_SHIFT;
|
|
|
200 }
|
|
|
201 v = _PyLong_New(ndigits);
|
|
|
202 if (v != NULL) {
|
|
|
203 digit *p = v->ob_digit;
|
|
|
204 Py_SIZE(v) = ndigits;
|
|
|
205 while (ival) {
|
|
|
206 *p++ = (digit)(ival & PyLong_MASK);
|
|
|
207 ival >>= PyLong_SHIFT;
|
|
|
208 }
|
|
|
209 }
|
|
|
210 return (PyObject *)v;
|
|
|
211 }
|
|
|
212
|
|
|
213 /* Create a new long int object from a C double */
|
|
|
214
|
|
|
215 PyObject *
|
|
|
216 PyLong_FromDouble(double dval)
|
|
|
217 {
|
|
|
218 PyLongObject *v;
|
|
|
219 double frac;
|
|
|
220 int i, ndig, expo, neg;
|
|
|
221 neg = 0;
|
|
|
222 if (Py_IS_INFINITY(dval)) {
|
|
|
223 PyErr_SetString(PyExc_OverflowError,
|
|
|
224 "cannot convert float infinity to integer");
|
|
|
225 return NULL;
|
|
|
226 }
|
|
|
227 if (Py_IS_NAN(dval)) {
|
|
|
228 PyErr_SetString(PyExc_ValueError,
|
|
|
229 "cannot convert float NaN to integer");
|
|
|
230 return NULL;
|
|
|
231 }
|
|
|
232 if (dval < 0.0) {
|
|
|
233 neg = 1;
|
|
|
234 dval = -dval;
|
|
|
235 }
|
|
|
236 frac = frexp(dval, &expo); /* dval = frac*2**expo; 0.0 <= frac < 1.0 */
|
|
|
237 if (expo <= 0)
|
|
|
238 return PyLong_FromLong(0L);
|
|
|
239 ndig = (expo-1) / PyLong_SHIFT + 1; /* Number of 'digits' in result */
|
|
|
240 v = _PyLong_New(ndig);
|
|
|
241 if (v == NULL)
|
|
|
242 return NULL;
|
|
|
243 frac = ldexp(frac, (expo-1) % PyLong_SHIFT + 1);
|
|
|
244 for (i = ndig; --i >= 0; ) {
|
|
|
245 digit bits = (digit)frac;
|
|
|
246 v->ob_digit[i] = bits;
|
|
|
247 frac = frac - (double)bits;
|
|
|
248 frac = ldexp(frac, PyLong_SHIFT);
|
|
|
249 }
|
|
|
250 if (neg)
|
|
|
251 Py_SIZE(v) = -(Py_SIZE(v));
|
|
|
252 return (PyObject *)v;
|
|
|
253 }
|
|
|
254
|
|
|
255 /* Checking for overflow in PyLong_AsLong is a PITA since C doesn't define
|
|
|
256 * anything about what happens when a signed integer operation overflows,
|
|
|
257 * and some compilers think they're doing you a favor by being "clever"
|
|
|
258 * then. The bit pattern for the largest postive signed long is
|
|
|
259 * (unsigned long)LONG_MAX, and for the smallest negative signed long
|
|
|
260 * it is abs(LONG_MIN), which we could write -(unsigned long)LONG_MIN.
|
|
|
261 * However, some other compilers warn about applying unary minus to an
|
|
|
262 * unsigned operand. Hence the weird "0-".
|
|
|
263 */
|
|
|
264 #define PY_ABS_LONG_MIN (0-(unsigned long)LONG_MIN)
|
|
|
265 #define PY_ABS_SSIZE_T_MIN (0-(size_t)PY_SSIZE_T_MIN)
|
|
|
266
|
|
|
267 /* Get a C long int from a long int object or any object that has an __int__
|
|
|
268 method.
|
|
|
269
|
|
|
270 On overflow, return -1 and set *overflow to 1 or -1 depending on the sign of
|
|
|
271 the result. Otherwise *overflow is 0.
|
|
|
272
|
|
|
273 For other errors (e.g., TypeError), return -1 and set an error condition.
|
|
|
274 In this case *overflow will be 0.
|
|
|
275 */
|
|
|
276
|
|
|
277 long
|
|
|
278 PyLong_AsLongAndOverflow(PyObject *vv, int *overflow)
|
|
|
279 {
|
|
|
280 /* This version by Tim Peters */
|
|
|
281 register PyLongObject *v;
|
|
|
282 unsigned long x, prev;
|
|
|
283 long res;
|
|
|
284 Py_ssize_t i;
|
|
|
285 int sign;
|
|
|
286 int do_decref = 0; /* if nb_int was called */
|
|
|
287
|
|
|
288 *overflow = 0;
|
|
|
289 if (vv == NULL) {
|
|
|
290 PyErr_BadInternalCall();
|
|
|
291 return -1;
|
|
|
292 }
|
|
|
293
|
|
|
294 if (!PyLong_Check(vv)) {
|
|
|
295 PyNumberMethods *nb;
|
|
|
296 nb = vv->ob_type->tp_as_number;
|
|
|
297 if (nb == NULL || nb->nb_int == NULL) {
|
|
|
298 PyErr_SetString(PyExc_TypeError,
|
|
|
299 "an integer is required");
|
|
|
300 return -1;
|
|
|
301 }
|
|
|
302 vv = (*nb->nb_int) (vv);
|
|
|
303 if (vv == NULL)
|
|
|
304 return -1;
|
|
|
305 do_decref = 1;
|
|
|
306 if (!PyLong_Check(vv)) {
|
|
|
307 Py_DECREF(vv);
|
|
|
308 PyErr_SetString(PyExc_TypeError,
|
|
|
309 "nb_int should return int object");
|
|
|
310 return -1;
|
|
|
311 }
|
|
|
312 }
|
|
|
313
|
|
|
314 res = -1;
|
|
|
315 v = (PyLongObject *)vv;
|
|
|
316 i = Py_SIZE(v);
|
|
|
317
|
|
|
318 switch (i) {
|
|
|
319 case -1:
|
|
|
320 res = -(sdigit)v->ob_digit[0];
|
|
|
321 break;
|
|
|
322 case 0:
|
|
|
323 res = 0;
|
|
|
324 break;
|
|
|
325 case 1:
|
|
|
326 res = v->ob_digit[0];
|
|
|
327 break;
|
|
|
328 default:
|
|
|
329 sign = 1;
|
|
|
330 x = 0;
|
|
|
331 if (i < 0) {
|
|
|
332 sign = -1;
|
|
|
333 i = -(i);
|
|
|
334 }
|
|
|
335 while (--i >= 0) {
|
|
|
336 prev = x;
|
|
|
337 x = (x << PyLong_SHIFT) | v->ob_digit[i];
|
|
|
338 if ((x >> PyLong_SHIFT) != prev) {
|
|
|
339 *overflow = sign;
|
|
|
340 goto exit;
|
|
|
341 }
|
|
|
342 }
|
|
|
343 /* Haven't lost any bits, but casting to long requires extra
|
|
|
344 * care (see comment above).
|
|
|
345 */
|
|
|
346 if (x <= (unsigned long)LONG_MAX) {
|
|
|
347 res = (long)x * sign;
|
|
|
348 }
|
|
|
349 else if (sign < 0 && x == PY_ABS_LONG_MIN) {
|
|
|
350 res = LONG_MIN;
|
|
|
351 }
|
|
|
352 else {
|
|
|
353 *overflow = sign;
|
|
|
354 /* res is already set to -1 */
|
|
|
355 }
|
|
|
356 }
|
|
|
357 exit:
|
|
|
358 if (do_decref) {
|
|
|
359 Py_DECREF(vv);
|
|
|
360 }
|
|
|
361 return res;
|
|
|
362 }
|
|
|
363
|
|
|
364 /* Get a C long int from a long int object or any object that has an __int__
|
|
|
365 method. Return -1 and set an error if overflow occurs. */
|
|
|
366
|
|
|
367 long
|
|
|
368 PyLong_AsLong(PyObject *obj)
|
|
|
369 {
|
|
|
370 int overflow;
|
|
|
371 long result = PyLong_AsLongAndOverflow(obj, &overflow);
|
|
|
372 if (overflow) {
|
|
|
373 /* XXX: could be cute and give a different
|
|
|
374 message for overflow == -1 */
|
|
|
375 PyErr_SetString(PyExc_OverflowError,
|
|
|
376 "Python int too large to convert to C long");
|
|
|
377 }
|
|
|
378 return result;
|
|
|
379 }
|
|
|
380
|
|
|
381 /* Get a Py_ssize_t from a long int object.
|
|
|
382 Returns -1 and sets an error condition if overflow occurs. */
|
|
|
383
|
|
|
384 Py_ssize_t
|
|
|
385 PyLong_AsSsize_t(PyObject *vv) {
|
|
|
386 register PyLongObject *v;
|
|
|
387 size_t x, prev;
|
|
|
388 Py_ssize_t i;
|
|
|
389 int sign;
|
|
|
390
|
|
|
391 if (vv == NULL) {
|
|
|
392 PyErr_BadInternalCall();
|
|
|
393 return -1;
|
|
|
394 }
|
|
|
395 if (!PyLong_Check(vv)) {
|
|
|
396 PyErr_SetString(PyExc_TypeError, "an integer is required");
|
|
|
397 return -1;
|
|
|
398 }
|
|
|
399
|
|
|
400 v = (PyLongObject *)vv;
|
|
|
401 i = Py_SIZE(v);
|
|
|
402 switch (i) {
|
|
|
403 case -1: return -(sdigit)v->ob_digit[0];
|
|
|
404 case 0: return 0;
|
|
|
405 case 1: return v->ob_digit[0];
|
|
|
406 }
|
|
|
407 sign = 1;
|
|
|
408 x = 0;
|
|
|
409 if (i < 0) {
|
|
|
410 sign = -1;
|
|
|
411 i = -(i);
|
|
|
412 }
|
|
|
413 while (--i >= 0) {
|
|
|
414 prev = x;
|
|
|
415 x = (x << PyLong_SHIFT) | v->ob_digit[i];
|
|
|
416 if ((x >> PyLong_SHIFT) != prev)
|
|
|
417 goto overflow;
|
|
|
418 }
|
|
|
419 /* Haven't lost any bits, but casting to a signed type requires
|
|
|
420 * extra care (see comment above).
|
|
|
421 */
|
|
|
422 if (x <= (size_t)PY_SSIZE_T_MAX) {
|
|
|
423 return (Py_ssize_t)x * sign;
|
|
|
424 }
|
|
|
425 else if (sign < 0 && x == PY_ABS_SSIZE_T_MIN) {
|
|
|
426 return PY_SSIZE_T_MIN;
|
|
|
427 }
|
|
|
428 /* else overflow */
|
|
|
429
|
|
|
430 overflow:
|
|
|
431 PyErr_SetString(PyExc_OverflowError,
|
|
|
432 "Python int too large to convert to C ssize_t");
|
|
|
433 return -1;
|
|
|
434 }
|
|
|
435
|
|
|
436 /* Get a C unsigned long int from a long int object.
|
|
|
437 Returns -1 and sets an error condition if overflow occurs. */
|
|
|
438
|
|
|
439 unsigned long
|
|
|
440 PyLong_AsUnsignedLong(PyObject *vv)
|
|
|
441 {
|
|
|
442 register PyLongObject *v;
|
|
|
443 unsigned long x, prev;
|
|
|
444 Py_ssize_t i;
|
|
|
445
|
|
|
446 if (vv == NULL) {
|
|
|
447 PyErr_BadInternalCall();
|
|
|
448 return (unsigned long)-1;
|
|
|
449 }
|
|
|
450 if (!PyLong_Check(vv)) {
|
|
|
451 PyErr_SetString(PyExc_TypeError, "an integer is required");
|
|
|
452 return (unsigned long)-1;
|
|
|
453 }
|
|
|
454
|
|
|
455 v = (PyLongObject *)vv;
|
|
|
456 i = Py_SIZE(v);
|
|
|
457 x = 0;
|
|
|
458 if (i < 0) {
|
|
|
459 PyErr_SetString(PyExc_OverflowError,
|
|
|
460 "can't convert negative value to unsigned int");
|
|
|
461 return (unsigned long) -1;
|
|
|
462 }
|
|
|
463 switch (i) {
|
|
|
464 case 0: return 0;
|
|
|
465 case 1: return v->ob_digit[0];
|
|
|
466 }
|
|
|
467 while (--i >= 0) {
|
|
|
468 prev = x;
|
|
|
469 x = (x << PyLong_SHIFT) | v->ob_digit[i];
|
|
|
470 if ((x >> PyLong_SHIFT) != prev) {
|
|
|
471 PyErr_SetString(PyExc_OverflowError,
|
|
|
472 "python int too large to convert "
|
|
|
473 "to C unsigned long");
|
|
|
474 return (unsigned long) -1;
|
|
|
475 }
|
|
|
476 }
|
|
|
477 return x;
|
|
|
478 }
|
|
|
479
|
|
|
480 /* Get a C size_t from a long int object. Returns (size_t)-1 and sets
|
|
|
481 an error condition if overflow occurs. */
|
|
|
482
|
|
|
483 size_t
|
|
|
484 PyLong_AsSize_t(PyObject *vv)
|
|
|
485 {
|
|
|
486 register PyLongObject *v;
|
|
|
487 size_t x, prev;
|
|
|
488 Py_ssize_t i;
|
|
|
489
|
|
|
490 if (vv == NULL) {
|
|
|
491 PyErr_BadInternalCall();
|
|
|
492 return (size_t) -1;
|
|
|
493 }
|
|
|
494 if (!PyLong_Check(vv)) {
|
|
|
495 PyErr_SetString(PyExc_TypeError, "an integer is required");
|
|
|
496 return (size_t)-1;
|
|
|
497 }
|
|
|
498
|
|
|
499 v = (PyLongObject *)vv;
|
|
|
500 i = Py_SIZE(v);
|
|
|
501 x = 0;
|
|
|
502 if (i < 0) {
|
|
|
503 PyErr_SetString(PyExc_OverflowError,
|
|
|
504 "can't convert negative value to size_t");
|
|
|
505 return (size_t) -1;
|
|
|
506 }
|
|
|
507 switch (i) {
|
|
|
508 case 0: return 0;
|
|
|
509 case 1: return v->ob_digit[0];
|
|
|
510 }
|
|
|
511 while (--i >= 0) {
|
|
|
512 prev = x;
|
|
|
513 x = (x << PyLong_SHIFT) | v->ob_digit[i];
|
|
|
514 if ((x >> PyLong_SHIFT) != prev) {
|
|
|
515 PyErr_SetString(PyExc_OverflowError,
|
|
|
516 "Python int too large to convert to C size_t");
|
|
|
517 return (size_t) -1;
|
|
|
518 }
|
|
|
519 }
|
|
|
520 return x;
|
|
|
521 }
|
|
|
522
|
|
|
523 /* Get a C unsigned long int from a long int object, ignoring the high bits.
|
|
|
524 Returns -1 and sets an error condition if an error occurs. */
|
|
|
525
|
|
|
526 static unsigned long
|
|
|
527 _PyLong_AsUnsignedLongMask(PyObject *vv)
|
|
|
528 {
|
|
|
529 register PyLongObject *v;
|
|
|
530 unsigned long x;
|
|
|
531 Py_ssize_t i;
|
|
|
532 int sign;
|
|
|
533
|
|
|
534 if (vv == NULL || !PyLong_Check(vv)) {
|
|
|
535 PyErr_BadInternalCall();
|
|
|
536 return (unsigned long) -1;
|
|
|
537 }
|
|
|
538 v = (PyLongObject *)vv;
|
|
|
539 i = Py_SIZE(v);
|
|
|
540 switch (i) {
|
|
|
541 case 0: return 0;
|
|
|
542 case 1: return v->ob_digit[0];
|
|
|
543 }
|
|
|
544 sign = 1;
|
|
|
545 x = 0;
|
|
|
546 if (i < 0) {
|
|
|
547 sign = -1;
|
|
|
548 i = -i;
|
|
|
549 }
|
|
|
550 while (--i >= 0) {
|
|
|
551 x = (x << PyLong_SHIFT) | v->ob_digit[i];
|
|
|
552 }
|
|
|
553 return x * sign;
|
|
|
554 }
|
|
|
555
|
|
|
556 unsigned long
|
|
|
557 PyLong_AsUnsignedLongMask(register PyObject *op)
|
|
|
558 {
|
|
|
559 PyNumberMethods *nb;
|
|
|
560 PyLongObject *lo;
|
|
|
561 unsigned long val;
|
|
|
562
|
|
|
563 if (op && PyLong_Check(op))
|
|
|
564 return _PyLong_AsUnsignedLongMask(op);
|
|
|
565
|
|
|
566 if (op == NULL || (nb = op->ob_type->tp_as_number) == NULL ||
|
|
|
567 nb->nb_int == NULL) {
|
|
|
568 PyErr_SetString(PyExc_TypeError, "an integer is required");
|
|
|
569 return (unsigned long)-1;
|
|
|
570 }
|
|
|
571
|
|
|
572 lo = (PyLongObject*) (*nb->nb_int) (op);
|
|
|
573 if (lo == NULL)
|
|
|
574 return (unsigned long)-1;
|
|
|
575 if (PyLong_Check(lo)) {
|
|
|
576 val = _PyLong_AsUnsignedLongMask((PyObject *)lo);
|
|
|
577 Py_DECREF(lo);
|
|
|
578 if (PyErr_Occurred())
|
|
|
579 return (unsigned long)-1;
|
|
|
580 return val;
|
|
|
581 }
|
|
|
582 else
|
|
|
583 {
|
|
|
584 Py_DECREF(lo);
|
|
|
585 PyErr_SetString(PyExc_TypeError,
|
|
|
586 "nb_int should return int object");
|
|
|
587 return (unsigned long)-1;
|
|
|
588 }
|
|
|
589 }
|
|
|
590
|
|
|
591 int
|
|
|
592 _PyLong_Sign(PyObject *vv)
|
|
|
593 {
|
|
|
594 PyLongObject *v = (PyLongObject *)vv;
|
|
|
595
|
|
|
596 assert(v != NULL);
|
|
|
597 assert(PyLong_Check(v));
|
|
|
598
|
|
|
599 return Py_SIZE(v) == 0 ? 0 : (Py_SIZE(v) < 0 ? -1 : 1);
|
|
|
600 }
|
|
|
601
|
|
|
602 size_t
|
|
|
603 _PyLong_NumBits(PyObject *vv)
|
|
|
604 {
|
|
|
605 PyLongObject *v = (PyLongObject *)vv;
|
|
|
606 size_t result = 0;
|
|
|
607 Py_ssize_t ndigits;
|
|
|
608
|
|
|
609 assert(v != NULL);
|
|
|
610 assert(PyLong_Check(v));
|
|
|
611 ndigits = ABS(Py_SIZE(v));
|
|
|
612 assert(ndigits == 0 || v->ob_digit[ndigits - 1] != 0);
|
|
|
613 if (ndigits > 0) {
|
|
|
614 digit msd = v->ob_digit[ndigits - 1];
|
|
|
615
|
|
|
616 result = (ndigits - 1) * PyLong_SHIFT;
|
|
|
617 if (result / PyLong_SHIFT != (size_t)(ndigits - 1))
|
|
|
618 goto Overflow;
|
|
|
619 do {
|
|
|
620 ++result;
|
|
|
621 if (result == 0)
|
|
|
622 goto Overflow;
|
|
|
623 msd >>= 1;
|
|
|
624 } while (msd);
|
|
|
625 }
|
|
|
626 return result;
|
|
|
627
|
|
|
628 Overflow:
|
|
|
629 PyErr_SetString(PyExc_OverflowError, "int has too many bits "
|
|
|
630 "to express in a platform size_t");
|
|
|
631 return (size_t)-1;
|
|
|
632 }
|
|
|
633
|
|
|
634 PyObject *
|
|
|
635 _PyLong_FromByteArray(const unsigned char* bytes, size_t n,
|
|
|
636 int little_endian, int is_signed)
|
|
|
637 {
|
|
|
638 const unsigned char* pstartbyte; /* LSB of bytes */
|
|
|
639 int incr; /* direction to move pstartbyte */
|
|
|
640 const unsigned char* pendbyte; /* MSB of bytes */
|
|
|
641 size_t numsignificantbytes; /* number of bytes that matter */
|
|
|
642 Py_ssize_t ndigits; /* number of Python long digits */
|
|
|
643 PyLongObject* v; /* result */
|
|
|
644 Py_ssize_t idigit = 0; /* next free index in v->ob_digit */
|
|
|
645
|
|
|
646 if (n == 0)
|
|
|
647 return PyLong_FromLong(0L);
|
|
|
648
|
|
|
649 if (little_endian) {
|
|
|
650 pstartbyte = bytes;
|
|
|
651 pendbyte = bytes + n - 1;
|
|
|
652 incr = 1;
|
|
|
653 }
|
|
|
654 else {
|
|
|
655 pstartbyte = bytes + n - 1;
|
|
|
656 pendbyte = bytes;
|
|
|
657 incr = -1;
|
|
|
658 }
|
|
|
659
|
|
|
660 if (is_signed)
|
|
|
661 is_signed = *pendbyte >= 0x80;
|
|
|
662
|
|
|
663 /* Compute numsignificantbytes. This consists of finding the most
|
|
|
664 significant byte. Leading 0 bytes are insignificant if the number
|
|
|
665 is positive, and leading 0xff bytes if negative. */
|
|
|
666 {
|
|
|
667 size_t i;
|
|
|
668 const unsigned char* p = pendbyte;
|
|
|
669 const int pincr = -incr; /* search MSB to LSB */
|
|
|
670 const unsigned char insignficant = is_signed ? 0xff : 0x00;
|
|
|
671
|
|
|
672 for (i = 0; i < n; ++i, p += pincr) {
|
|
|
673 if (*p != insignficant)
|
|
|
674 break;
|
|
|
675 }
|
|
|
676 numsignificantbytes = n - i;
|
|
|
677 /* 2's-comp is a bit tricky here, e.g. 0xff00 == -0x0100, so
|
|
|
678 actually has 2 significant bytes. OTOH, 0xff0001 ==
|
|
|
679 -0x00ffff, so we wouldn't *need* to bump it there; but we
|
|
|
680 do for 0xffff = -0x0001. To be safe without bothering to
|
|
|
681 check every case, bump it regardless. */
|
|
|
682 if (is_signed && numsignificantbytes < n)
|
|
|
683 ++numsignificantbytes;
|
|
|
684 }
|
|
|
685
|
|
|
686 /* How many Python long digits do we need? We have
|
|
|
687 8*numsignificantbytes bits, and each Python long digit has
|
|
|
688 PyLong_SHIFT bits, so it's the ceiling of the quotient. */
|
|
|
689 /* catch overflow before it happens */
|
|
|
690 if (numsignificantbytes > (PY_SSIZE_T_MAX - PyLong_SHIFT) / 8) {
|
|
|
691 PyErr_SetString(PyExc_OverflowError,
|
|
|
692 "byte array too long to convert to int");
|
|
|
693 return NULL;
|
|
|
694 }
|
|
|
695 ndigits = (numsignificantbytes * 8 + PyLong_SHIFT - 1) / PyLong_SHIFT;
|
|
|
696 v = _PyLong_New(ndigits);
|
|
|
697 if (v == NULL)
|
|
|
698 return NULL;
|
|
|
699
|
|
|
700 /* Copy the bits over. The tricky parts are computing 2's-comp on
|
|
|
701 the fly for signed numbers, and dealing with the mismatch between
|
|
|
702 8-bit bytes and (probably) 15-bit Python digits.*/
|
|
|
703 {
|
|
|
704 size_t i;
|
|
|
705 twodigits carry = 1; /* for 2's-comp calculation */
|
|
|
706 twodigits accum = 0; /* sliding register */
|
|
|
707 unsigned int accumbits = 0; /* number of bits in accum */
|
|
|
708 const unsigned char* p = pstartbyte;
|
|
|
709
|
|
|
710 for (i = 0; i < numsignificantbytes; ++i, p += incr) {
|
|
|
711 twodigits thisbyte = *p;
|
|
|
712 /* Compute correction for 2's comp, if needed. */
|
|
|
713 if (is_signed) {
|
|
|
714 thisbyte = (0xff ^ thisbyte) + carry;
|
|
|
715 carry = thisbyte >> 8;
|
|
|
716 thisbyte &= 0xff;
|
|
|
717 }
|
|
|
718 /* Because we're going LSB to MSB, thisbyte is
|
|
|
719 more significant than what's already in accum,
|
|
|
720 so needs to be prepended to accum. */
|
|
|
721 accum |= (twodigits)thisbyte << accumbits;
|
|
|
722 accumbits += 8;
|
|
|
723 if (accumbits >= PyLong_SHIFT) {
|
|
|
724 /* There's enough to fill a Python digit. */
|
|
|
725 assert(idigit < ndigits);
|
|
|
726 v->ob_digit[idigit] = (digit)(accum & PyLong_MASK);
|
|
|
727 ++idigit;
|
|
|
728 accum >>= PyLong_SHIFT;
|
|
|
729 accumbits -= PyLong_SHIFT;
|
|
|
730 assert(accumbits < PyLong_SHIFT);
|
|
|
731 }
|
|
|
732 }
|
|
|
733 assert(accumbits < PyLong_SHIFT);
|
|
|
734 if (accumbits) {
|
|
|
735 assert(idigit < ndigits);
|
|
|
736 v->ob_digit[idigit] = (digit)accum;
|
|
|
737 ++idigit;
|
|
|
738 }
|
|
|
739 }
|
|
|
740
|
|
|
741 Py_SIZE(v) = is_signed ? -idigit : idigit;
|
|
|
742 return (PyObject *)long_normalize(v);
|
|
|
743 }
|
|
|
744
|
|
|
745 int
|
|
|
746 _PyLong_AsByteArray(PyLongObject* v,
|
|
|
747 unsigned char* bytes, size_t n,
|
|
|
748 int little_endian, int is_signed)
|
|
|
749 {
|
|
|
750 Py_ssize_t i; /* index into v->ob_digit */
|
|
|
751 Py_ssize_t ndigits; /* |v->ob_size| */
|
|
|
752 twodigits accum; /* sliding register */
|
|
|
753 unsigned int accumbits; /* # bits in accum */
|
|
|
754 int do_twos_comp; /* store 2's-comp? is_signed and v < 0 */
|
|
|
755 digit carry; /* for computing 2's-comp */
|
|
|
756 size_t j; /* # bytes filled */
|
|
|
757 unsigned char* p; /* pointer to next byte in bytes */
|
|
|
758 int pincr; /* direction to move p */
|
|
|
759
|
|
|
760 assert(v != NULL && PyLong_Check(v));
|
|
|
761
|
|
|
762 if (Py_SIZE(v) < 0) {
|
|
|
763 ndigits = -(Py_SIZE(v));
|
|
|
764 if (!is_signed) {
|
|
|
765 PyErr_SetString(PyExc_OverflowError,
|
|
|
766 "can't convert negative int to unsigned");
|
|
|
767 return -1;
|
|
|
768 }
|
|
|
769 do_twos_comp = 1;
|
|
|
770 }
|
|
|
771 else {
|
|
|
772 ndigits = Py_SIZE(v);
|
|
|
773 do_twos_comp = 0;
|
|
|
774 }
|
|
|
775
|
|
|
776 if (little_endian) {
|
|
|
777 p = bytes;
|
|
|
778 pincr = 1;
|
|
|
779 }
|
|
|
780 else {
|
|
|
781 p = bytes + n - 1;
|
|
|
782 pincr = -1;
|
|
|
783 }
|
|
|
784
|
|
|
785 /* Copy over all the Python digits.
|
|
|
786 It's crucial that every Python digit except for the MSD contribute
|
|
|
787 exactly PyLong_SHIFT bits to the total, so first assert that the long is
|
|
|
788 normalized. */
|
|
|
789 assert(ndigits == 0 || v->ob_digit[ndigits - 1] != 0);
|
|
|
790 j = 0;
|
|
|
791 accum = 0;
|
|
|
792 accumbits = 0;
|
|
|
793 carry = do_twos_comp ? 1 : 0;
|
|
|
794 for (i = 0; i < ndigits; ++i) {
|
|
|
795 digit thisdigit = v->ob_digit[i];
|
|
|
796 if (do_twos_comp) {
|
|
|
797 thisdigit = (thisdigit ^ PyLong_MASK) + carry;
|
|
|
798 carry = thisdigit >> PyLong_SHIFT;
|
|
|
799 thisdigit &= PyLong_MASK;
|
|
|
800 }
|
|
|
801 /* Because we're going LSB to MSB, thisdigit is more
|
|
|
802 significant than what's already in accum, so needs to be
|
|
|
803 prepended to accum. */
|
|
|
804 accum |= (twodigits)thisdigit << accumbits;
|
|
|
805
|
|
|
806 /* The most-significant digit may be (probably is) at least
|
|
|
807 partly empty. */
|
|
|
808 if (i == ndigits - 1) {
|
|
|
809 /* Count # of sign bits -- they needn't be stored,
|
|
|
810 * although for signed conversion we need later to
|
|
|
811 * make sure at least one sign bit gets stored. */
|
|
|
812 digit s = do_twos_comp ? thisdigit ^ PyLong_MASK : thisdigit;
|
|
|
813 while (s != 0) {
|
|
|
814 s >>= 1;
|
|
|
815 accumbits++;
|
|
|
816 }
|
|
|
817 }
|
|
|
818 else
|
|
|
819 accumbits += PyLong_SHIFT;
|
|
|
820
|
|
|
821 /* Store as many bytes as possible. */
|
|
|
822 while (accumbits >= 8) {
|
|
|
823 if (j >= n)
|
|
|
824 goto Overflow;
|
|
|
825 ++j;
|
|
|
826 *p = (unsigned char)(accum & 0xff);
|
|
|
827 p += pincr;
|
|
|
828 accumbits -= 8;
|
|
|
829 accum >>= 8;
|
|
|
830 }
|
|
|
831 }
|
|
|
832
|
|
|
833 /* Store the straggler (if any). */
|
|
|
834 assert(accumbits < 8);
|
|
|
835 assert(carry == 0); /* else do_twos_comp and *every* digit was 0 */
|
|
|
836 if (accumbits > 0) {
|
|
|
837 if (j >= n)
|
|
|
838 goto Overflow;
|
|
|
839 ++j;
|
|
|
840 if (do_twos_comp) {
|
|
|
841 /* Fill leading bits of the byte with sign bits
|
|
|
842 (appropriately pretending that the long had an
|
|
|
843 infinite supply of sign bits). */
|
|
|
844 accum |= (~(twodigits)0) << accumbits;
|
|
|
845 }
|
|
|
846 *p = (unsigned char)(accum & 0xff);
|
|
|
847 p += pincr;
|
|
|
848 }
|
|
|
849 else if (j == n && n > 0 && is_signed) {
|
|
|
850 /* The main loop filled the byte array exactly, so the code
|
|
|
851 just above didn't get to ensure there's a sign bit, and the
|
|
|
852 loop below wouldn't add one either. Make sure a sign bit
|
|
|
853 exists. */
|
|
|
854 unsigned char msb = *(p - pincr);
|
|
|
855 int sign_bit_set = msb >= 0x80;
|
|
|
856 assert(accumbits == 0);
|
|
|
857 if (sign_bit_set == do_twos_comp)
|
|
|
858 return 0;
|
|
|
859 else
|
|
|
860 goto Overflow;
|
|
|
861 }
|
|
|
862
|
|
|
863 /* Fill remaining bytes with copies of the sign bit. */
|
|
|
864 {
|
|
|
865 unsigned char signbyte = do_twos_comp ? 0xffU : 0U;
|
|
|
866 for ( ; j < n; ++j, p += pincr)
|
|
|
867 *p = signbyte;
|
|
|
868 }
|
|
|
869
|
|
|
870 return 0;
|
|
|
871
|
|
|
872 Overflow:
|
|
|
873 PyErr_SetString(PyExc_OverflowError, "int too big to convert");
|
|
|
874 return -1;
|
|
|
875
|
|
|
876 }
|
|
|
877
|
|
|
878 /* Create a new long int object from a C pointer */
|
|
|
879
|
|
|
880 PyObject *
|
|
|
881 PyLong_FromVoidPtr(void *p)
|
|
|
882 {
|
|
|
883 #ifndef HAVE_LONG_LONG
|
|
|
884 # error "PyLong_FromVoidPtr: sizeof(void*) > sizeof(long), but no long long"
|
|
|
885 #endif
|
|
|
886 #if SIZEOF_LONG_LONG < SIZEOF_VOID_P
|
|
|
887 # error "PyLong_FromVoidPtr: sizeof(PY_LONG_LONG) < sizeof(void*)"
|
|
|
888 #endif
|
|
|
889 /* special-case null pointer */
|
|
|
890 if (!p)
|
|
|
891 return PyLong_FromLong(0);
|
|
|
892 return PyLong_FromUnsignedLongLong((unsigned PY_LONG_LONG)(Py_uintptr_t)p);
|
|
|
893
|
|
|
894 }
|
|
|
895
|
|
|
896 /* Get a C pointer from a long int object. */
|
|
|
897
|
|
|
898 void *
|
|
|
899 PyLong_AsVoidPtr(PyObject *vv)
|
|
|
900 {
|
|
|
901 #if SIZEOF_VOID_P <= SIZEOF_LONG
|
|
|
902 long x;
|
|
|
903
|
|
|
904 if (PyLong_Check(vv) && _PyLong_Sign(vv) < 0)
|
|
|
905 x = PyLong_AsLong(vv);
|
|
|
906 else
|
|
|
907 x = PyLong_AsUnsignedLong(vv);
|
|
|
908 #else
|
|
|
909
|
|
|
910 #ifndef HAVE_LONG_LONG
|
|
|
911 # error "PyLong_AsVoidPtr: sizeof(void*) > sizeof(long), but no long long"
|
|
|
912 #endif
|
|
|
913 #if SIZEOF_LONG_LONG < SIZEOF_VOID_P
|
|
|
914 # error "PyLong_AsVoidPtr: sizeof(PY_LONG_LONG) < sizeof(void*)"
|
|
|
915 #endif
|
|
|
916 PY_LONG_LONG x;
|
|
|
917
|
|
|
918 if (PyLong_Check(vv) && _PyLong_Sign(vv) < 0)
|
|
|
919 x = PyLong_AsLongLong(vv);
|
|
|
920 else
|
|
|
921 x = PyLong_AsUnsignedLongLong(vv);
|
|
|
922
|
|
|
923 #endif /* SIZEOF_VOID_P <= SIZEOF_LONG */
|
|
|
924
|
|
|
925 if (x == -1 && PyErr_Occurred())
|
|
|
926 return NULL;
|
|
|
927 return (void *)x;
|
|
|
928 }
|
|
|
929
|
|
|
930 #ifdef HAVE_LONG_LONG
|
|
|
931
|
|
|
932 /* Initial PY_LONG_LONG support by Chris Herborth (chrish@qnx.com), later
|
|
|
933 * rewritten to use the newer PyLong_{As,From}ByteArray API.
|
|
|
934 */
|
|
|
935
|
|
|
936 #define IS_LITTLE_ENDIAN (int)*(unsigned char*)&one
|
|
|
937 #define PY_ABS_LLONG_MIN (0-(unsigned PY_LONG_LONG)PY_LLONG_MIN)
|
|
|
938
|
|
|
939 /* Create a new long int object from a C PY_LONG_LONG int. */
|
|
|
940
|
|
|
941 PyObject *
|
|
|
942 PyLong_FromLongLong(PY_LONG_LONG ival)
|
|
|
943 {
|
|
|
944 PyLongObject *v;
|
|
|
945 unsigned PY_LONG_LONG abs_ival;
|
|
|
946 unsigned PY_LONG_LONG t; /* unsigned so >> doesn't propagate sign bit */
|
|
|
947 int ndigits = 0;
|
|
|
948 int negative = 0;
|
|
|
949
|
|
|
950 if (ival < 0) {
|
|
|
951 /* avoid signed overflow on negation; see comments
|
|
|
952 in PyLong_FromLong above. */
|
|
|
953 abs_ival = (unsigned PY_LONG_LONG)(-1-ival) + 1;
|
|
|
954 negative = 1;
|
|
|
955 }
|
|
|
956 else {
|
|
|
957 abs_ival = (unsigned PY_LONG_LONG)ival;
|
|
|
958 }
|
|
|
959
|
|
|
960 /* Count the number of Python digits.
|
|
|
961 We used to pick 5 ("big enough for anything"), but that's a
|
|
|
962 waste of time and space given that 5*15 = 75 bits are rarely
|
|
|
963 needed. */
|
|
|
964 t = abs_ival;
|
|
|
965 while (t) {
|
|
|
966 ++ndigits;
|
|
|
967 t >>= PyLong_SHIFT;
|
|
|
968 }
|
|
|
969 v = _PyLong_New(ndigits);
|
|
|
970 if (v != NULL) {
|
|
|
971 digit *p = v->ob_digit;
|
|
|
972 Py_SIZE(v) = negative ? -ndigits : ndigits;
|
|
|
973 t = abs_ival;
|
|
|
974 while (t) {
|
|
|
975 *p++ = (digit)(t & PyLong_MASK);
|
|
|
976 t >>= PyLong_SHIFT;
|
|
|
977 }
|
|
|
978 }
|
|
|
979 return (PyObject *)v;
|
|
|
980 }
|
|
|
981
|
|
|
982 /* Create a new long int object from a C unsigned PY_LONG_LONG int. */
|
|
|
983
|
|
|
984 PyObject *
|
|
|
985 PyLong_FromUnsignedLongLong(unsigned PY_LONG_LONG ival)
|
|
|
986 {
|
|
|
987 PyLongObject *v;
|
|
|
988 unsigned PY_LONG_LONG t;
|
|
|
989 int ndigits = 0;
|
|
|
990
|
|
|
991 if (ival < PyLong_BASE)
|
|
|
992 return PyLong_FromLong((long)ival);
|
|
|
993 /* Count the number of Python digits. */
|
|
|
994 t = (unsigned PY_LONG_LONG)ival;
|
|
|
995 while (t) {
|
|
|
996 ++ndigits;
|
|
|
997 t >>= PyLong_SHIFT;
|
|
|
998 }
|
|
|
999 v = _PyLong_New(ndigits);
|
|
|
1000 if (v != NULL) {
|
|
|
1001 digit *p = v->ob_digit;
|
|
|
1002 Py_SIZE(v) = ndigits;
|
|
|
1003 while (ival) {
|
|
|
1004 *p++ = (digit)(ival & PyLong_MASK);
|
|
|
1005 ival >>= PyLong_SHIFT;
|
|
|
1006 }
|
|
|
1007 }
|
|
|
1008 return (PyObject *)v;
|
|
|
1009 }
|
|
|
1010
|
|
|
1011 /* Create a new long int object from a C Py_ssize_t. */
|
|
|
1012
|
|
|
1013 PyObject *
|
|
|
1014 PyLong_FromSsize_t(Py_ssize_t ival)
|
|
|
1015 {
|
|
|
1016 PyLongObject *v;
|
|
|
1017 size_t abs_ival;
|
|
|
1018 size_t t; /* unsigned so >> doesn't propagate sign bit */
|
|
|
1019 int ndigits = 0;
|
|
|
1020 int negative = 0;
|
|
|
1021
|
|
|
1022 CHECK_SMALL_INT(ival);
|
|
|
1023 if (ival < 0) {
|
|
|
1024 /* avoid signed overflow when ival = SIZE_T_MIN */
|
|
|
1025 abs_ival = (size_t)(-1-ival)+1;
|
|
|
1026 negative = 1;
|
|
|
1027 }
|
|
|
1028 else {
|
|
|
1029 abs_ival = (size_t)ival;
|
|
|
1030 }
|
|
|
1031
|
|
|
1032 /* Count the number of Python digits. */
|
|
|
1033 t = abs_ival;
|
|
|
1034 while (t) {
|
|
|
1035 ++ndigits;
|
|
|
1036 t >>= PyLong_SHIFT;
|
|
|
1037 }
|
|
|
1038 v = _PyLong_New(ndigits);
|
|
|
1039 if (v != NULL) {
|
|
|
1040 digit *p = v->ob_digit;
|
|
|
1041 Py_SIZE(v) = negative ? -ndigits : ndigits;
|
|
|
1042 t = abs_ival;
|
|
|
1043 while (t) {
|
|
|
1044 *p++ = (digit)(t & PyLong_MASK);
|
|
|
1045 t >>= PyLong_SHIFT;
|
|
|
1046 }
|
|
|
1047 }
|
|
|
1048 return (PyObject *)v;
|
|
|
1049 }
|
|
|
1050
|
|
|
1051 /* Create a new long int object from a C size_t. */
|
|
|
1052
|
|
|
1053 PyObject *
|
|
|
1054 PyLong_FromSize_t(size_t ival)
|
|
|
1055 {
|
|
|
1056 PyLongObject *v;
|
|
|
1057 size_t t;
|
|
|
1058 int ndigits = 0;
|
|
|
1059
|
|
|
1060 if (ival < PyLong_BASE)
|
|
|
1061 return PyLong_FromLong((long)ival);
|
|
|
1062 /* Count the number of Python digits. */
|
|
|
1063 t = ival;
|
|
|
1064 while (t) {
|
|
|
1065 ++ndigits;
|
|
|
1066 t >>= PyLong_SHIFT;
|
|
|
1067 }
|
|
|
1068 v = _PyLong_New(ndigits);
|
|
|
1069 if (v != NULL) {
|
|
|
1070 digit *p = v->ob_digit;
|
|
|
1071 Py_SIZE(v) = ndigits;
|
|
|
1072 while (ival) {
|
|
|
1073 *p++ = (digit)(ival & PyLong_MASK);
|
|
|
1074 ival >>= PyLong_SHIFT;
|
|
|
1075 }
|
|
|
1076 }
|
|
|
1077 return (PyObject *)v;
|
|
|
1078 }
|
|
|
1079
|
|
|
1080 /* Get a C long long int from a long int object or any object that has an
|
|
|
1081 __int__ method. Return -1 and set an error if overflow occurs. */
|
|
|
1082
|
|
|
1083 PY_LONG_LONG
|
|
|
1084 PyLong_AsLongLong(PyObject *vv)
|
|
|
1085 {
|
|
|
1086 PyLongObject *v;
|
|
|
1087 PY_LONG_LONG bytes;
|
|
|
1088 int one = 1;
|
|
|
1089 int res;
|
|
|
1090
|
|
|
1091 if (vv == NULL) {
|
|
|
1092 PyErr_BadInternalCall();
|
|
|
1093 return -1;
|
|
|
1094 }
|
|
|
1095 if (!PyLong_Check(vv)) {
|
|
|
1096 PyNumberMethods *nb;
|
|
|
1097 PyObject *io;
|
|
|
1098 if ((nb = vv->ob_type->tp_as_number) == NULL ||
|
|
|
1099 nb->nb_int == NULL) {
|
|
|
1100 PyErr_SetString(PyExc_TypeError, "an integer is required");
|
|
|
1101 return -1;
|
|
|
1102 }
|
|
|
1103 io = (*nb->nb_int) (vv);
|
|
|
1104 if (io == NULL)
|
|
|
1105 return -1;
|
|
|
1106 if (PyLong_Check(io)) {
|
|
|
1107 bytes = PyLong_AsLongLong(io);
|
|
|
1108 Py_DECREF(io);
|
|
|
1109 return bytes;
|
|
|
1110 }
|
|
|
1111 Py_DECREF(io);
|
|
|
1112 PyErr_SetString(PyExc_TypeError, "integer conversion failed");
|
|
|
1113 return -1;
|
|
|
1114 }
|
|
|
1115
|
|
|
1116 v = (PyLongObject*)vv;
|
|
|
1117 switch(Py_SIZE(v)) {
|
|
|
1118 case -1: return -(sdigit)v->ob_digit[0];
|
|
|
1119 case 0: return 0;
|
|
|
1120 case 1: return v->ob_digit[0];
|
|
|
1121 }
|
|
|
1122 res = _PyLong_AsByteArray((PyLongObject *)vv, (unsigned char *)&bytes,
|
|
|
1123 SIZEOF_LONG_LONG, IS_LITTLE_ENDIAN, 1);
|
|
|
1124
|
|
|
1125 /* Plan 9 can't handle PY_LONG_LONG in ? : expressions */
|
|
|
1126 if (res < 0)
|
|
|
1127 return (PY_LONG_LONG)-1;
|
|
|
1128 else
|
|
|
1129 return bytes;
|
|
|
1130 }
|
|
|
1131
|
|
|
1132 /* Get a C unsigned PY_LONG_LONG int from a long int object.
|
|
|
1133 Return -1 and set an error if overflow occurs. */
|
|
|
1134
|
|
|
1135 unsigned PY_LONG_LONG
|
|
|
1136 PyLong_AsUnsignedLongLong(PyObject *vv)
|
|
|
1137 {
|
|
|
1138 PyLongObject *v;
|
|
|
1139 unsigned PY_LONG_LONG bytes;
|
|
|
1140 int one = 1;
|
|
|
1141 int res;
|
|
|
1142
|
|
|
1143 if (vv == NULL) {
|
|
|
1144 PyErr_BadInternalCall();
|
|
|
1145 return (unsigned PY_LONG_LONG)-1;
|
|
|
1146 }
|
|
|
1147 if (!PyLong_Check(vv)) {
|
|
|
1148 PyErr_SetString(PyExc_TypeError, "an integer is required");
|
|
|
1149 return (unsigned PY_LONG_LONG)-1;
|
|
|
1150 }
|
|
|
1151
|
|
|
1152 v = (PyLongObject*)vv;
|
|
|
1153 switch(Py_SIZE(v)) {
|
|
|
1154 case 0: return 0;
|
|
|
1155 case 1: return v->ob_digit[0];
|
|
|
1156 }
|
|
|
1157
|
|
|
1158 res = _PyLong_AsByteArray((PyLongObject *)vv, (unsigned char *)&bytes,
|
|
|
1159 SIZEOF_LONG_LONG, IS_LITTLE_ENDIAN, 0);
|
|
|
1160
|
|
|
1161 /* Plan 9 can't handle PY_LONG_LONG in ? : expressions */
|
|
|
1162 if (res < 0)
|
|
|
1163 return (unsigned PY_LONG_LONG)res;
|
|
|
1164 else
|
|
|
1165 return bytes;
|
|
|
1166 }
|
|
|
1167
|
|
|
1168 /* Get a C unsigned long int from a long int object, ignoring the high bits.
|
|
|
1169 Returns -1 and sets an error condition if an error occurs. */
|
|
|
1170
|
|
|
1171 static unsigned PY_LONG_LONG
|
|
|
1172 _PyLong_AsUnsignedLongLongMask(PyObject *vv)
|
|
|
1173 {
|
|
|
1174 register PyLongObject *v;
|
|
|
1175 unsigned PY_LONG_LONG x;
|
|
|
1176 Py_ssize_t i;
|
|
|
1177 int sign;
|
|
|
1178
|
|
|
1179 if (vv == NULL || !PyLong_Check(vv)) {
|
|
|
1180 PyErr_BadInternalCall();
|
|
|
1181 return (unsigned long) -1;
|
|
|
1182 }
|
|
|
1183 v = (PyLongObject *)vv;
|
|
|
1184 switch(Py_SIZE(v)) {
|
|
|
1185 case 0: return 0;
|
|
|
1186 case 1: return v->ob_digit[0];
|
|
|
1187 }
|
|
|
1188 i = Py_SIZE(v);
|
|
|
1189 sign = 1;
|
|
|
1190 x = 0;
|
|
|
1191 if (i < 0) {
|
|
|
1192 sign = -1;
|
|
|
1193 i = -i;
|
|
|
1194 }
|
|
|
1195 while (--i >= 0) {
|
|
|
1196 x = (x << PyLong_SHIFT) | v->ob_digit[i];
|
|
|
1197 }
|
|
|
1198 return x * sign;
|
|
|
1199 }
|
|
|
1200
|
|
|
1201 unsigned PY_LONG_LONG
|
|
|
1202 PyLong_AsUnsignedLongLongMask(register PyObject *op)
|
|
|
1203 {
|
|
|
1204 PyNumberMethods *nb;
|
|
|
1205 PyLongObject *lo;
|
|
|
1206 unsigned PY_LONG_LONG val;
|
|
|
1207
|
|
|
1208 if (op && PyLong_Check(op))
|
|
|
1209 return _PyLong_AsUnsignedLongLongMask(op);
|
|
|
1210
|
|
|
1211 if (op == NULL || (nb = op->ob_type->tp_as_number) == NULL ||
|
|
|
1212 nb->nb_int == NULL) {
|
|
|
1213 PyErr_SetString(PyExc_TypeError, "an integer is required");
|
|
|
1214 return (unsigned PY_LONG_LONG)-1;
|
|
|
1215 }
|
|
|
1216
|
|
|
1217 lo = (PyLongObject*) (*nb->nb_int) (op);
|
|
|
1218 if (lo == NULL)
|
|
|
1219 return (unsigned PY_LONG_LONG)-1;
|
|
|
1220 if (PyLong_Check(lo)) {
|
|
|
1221 val = _PyLong_AsUnsignedLongLongMask((PyObject *)lo);
|
|
|
1222 Py_DECREF(lo);
|
|
|
1223 if (PyErr_Occurred())
|
|
|
1224 return (unsigned PY_LONG_LONG)-1;
|
|
|
1225 return val;
|
|
|
1226 }
|
|
|
1227 else
|
|
|
1228 {
|
|
|
1229 Py_DECREF(lo);
|
|
|
1230 PyErr_SetString(PyExc_TypeError,
|
|
|
1231 "nb_int should return int object");
|
|
|
1232 return (unsigned PY_LONG_LONG)-1;
|
|
|
1233 }
|
|
|
1234 }
|
|
|
1235 #undef IS_LITTLE_ENDIAN
|
|
|
1236
|
|
|
1237 /* Get a C long long int from a long int object or any object that has an
|
|
|
1238 __int__ method.
|
|
|
1239
|
|
|
1240 On overflow, return -1 and set *overflow to 1 or -1 depending on the sign of
|
|
|
1241 the result. Otherwise *overflow is 0.
|
|
|
1242
|
|
|
1243 For other errors (e.g., TypeError), return -1 and set an error condition.
|
|
|
1244 In this case *overflow will be 0.
|
|
|
1245 */
|
|
|
1246
|
|
|
1247 PY_LONG_LONG
|
|
|
1248 PyLong_AsLongLongAndOverflow(PyObject *vv, int *overflow)
|
|
|
1249 {
|
|
|
1250 /* This version by Tim Peters */
|
|
|
1251 register PyLongObject *v;
|
|
|
1252 unsigned PY_LONG_LONG x, prev;
|
|
|
1253 PY_LONG_LONG res;
|
|
|
1254 Py_ssize_t i;
|
|
|
1255 int sign;
|
|
|
1256 int do_decref = 0; /* if nb_int was called */
|
|
|
1257
|
|
|
1258 *overflow = 0;
|
|
|
1259 if (vv == NULL) {
|
|
|
1260 PyErr_BadInternalCall();
|
|
|
1261 return -1;
|
|
|
1262 }
|
|
|
1263
|
|
|
1264 if (!PyLong_Check(vv)) {
|
|
|
1265 PyNumberMethods *nb;
|
|
|
1266 nb = vv->ob_type->tp_as_number;
|
|
|
1267 if (nb == NULL || nb->nb_int == NULL) {
|
|
|
1268 PyErr_SetString(PyExc_TypeError,
|
|
|
1269 "an integer is required");
|
|
|
1270 return -1;
|
|
|
1271 }
|
|
|
1272 vv = (*nb->nb_int) (vv);
|
|
|
1273 if (vv == NULL)
|
|
|
1274 return -1;
|
|
|
1275 do_decref = 1;
|
|
|
1276 if (!PyLong_Check(vv)) {
|
|
|
1277 Py_DECREF(vv);
|
|
|
1278 PyErr_SetString(PyExc_TypeError,
|
|
|
1279 "nb_int should return int object");
|
|
|
1280 return -1;
|
|
|
1281 }
|
|
|
1282 }
|
|
|
1283
|
|
|
1284 res = -1;
|
|
|
1285 v = (PyLongObject *)vv;
|
|
|
1286 i = Py_SIZE(v);
|
|
|
1287
|
|
|
1288 switch (i) {
|
|
|
1289 case -1:
|
|
|
1290 res = -(sdigit)v->ob_digit[0];
|
|
|
1291 break;
|
|
|
1292 case 0:
|
|
|
1293 res = 0;
|
|
|
1294 break;
|
|
|
1295 case 1:
|
|
|
1296 res = v->ob_digit[0];
|
|
|
1297 break;
|
|
|
1298 default:
|
|
|
1299 sign = 1;
|
|
|
1300 x = 0;
|
|
|
1301 if (i < 0) {
|
|
|
1302 sign = -1;
|
|
|
1303 i = -(i);
|
|
|
1304 }
|
|
|
1305 while (--i >= 0) {
|
|
|
1306 prev = x;
|
|
|
1307 x = (x << PyLong_SHIFT) + v->ob_digit[i];
|
|
|
1308 if ((x >> PyLong_SHIFT) != prev) {
|
|
|
1309 *overflow = sign;
|
|
|
1310 goto exit;
|
|
|
1311 }
|
|
|
1312 }
|
|
|
1313 /* Haven't lost any bits, but casting to long requires extra
|
|
|
1314 * care (see comment above).
|
|
|
1315 */
|
|
|
1316 if (x <= (unsigned PY_LONG_LONG)PY_LLONG_MAX) {
|
|
|
1317 res = (PY_LONG_LONG)x * sign;
|
|
|
1318 }
|
|
|
1319 else if (sign < 0 && x == PY_ABS_LLONG_MIN) {
|
|
|
1320 res = PY_LLONG_MIN;
|
|
|
1321 }
|
|
|
1322 else {
|
|
|
1323 *overflow = sign;
|
|
|
1324 /* res is already set to -1 */
|
|
|
1325 }
|
|
|
1326 }
|
|
|
1327 exit:
|
|
|
1328 if (do_decref) {
|
|
|
1329 Py_DECREF(vv);
|
|
|
1330 }
|
|
|
1331 return res;
|
|
|
1332 }
|
|
|
1333
|
|
|
1334 #endif /* HAVE_LONG_LONG */
|
|
|
1335
|
|
|
1336 #define CHECK_BINOP(v,w) \
|
|
|
1337 do { \
|
|
|
1338 if (!PyLong_Check(v) || !PyLong_Check(w)) \
|
|
|
1339 Py_RETURN_NOTIMPLEMENTED; \
|
|
|
1340 } while(0)
|
|
|
1341
|
|
|
1342 /* bits_in_digit(d) returns the unique integer k such that 2**(k-1) <= d <
|
|
|
1343 2**k if d is nonzero, else 0. */
|
|
|
1344
|
|
|
1345 static const unsigned char BitLengthTable[32] = {
|
|
|
1346 0, 1, 2, 2, 3, 3, 3, 3, 4, 4, 4, 4, 4, 4, 4, 4,
|
|
|
1347 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5
|
|
|
1348 };
|
|
|
1349
|
|
|
1350 static int
|
|
|
1351 bits_in_digit(digit d)
|
|
|
1352 {
|
|
|
1353 int d_bits = 0;
|
|
|
1354 while (d >= 32) {
|
|
|
1355 d_bits += 6;
|
|
|
1356 d >>= 6;
|
|
|
1357 }
|
|
|
1358 d_bits += (int)BitLengthTable[d];
|
|
|
1359 return d_bits;
|
|
|
1360 }
|
|
|
1361
|
|
|
1362 /* x[0:m] and y[0:n] are digit vectors, LSD first, m >= n required. x[0:n]
|
|
|
1363 * is modified in place, by adding y to it. Carries are propagated as far as
|
|
|
1364 * x[m-1], and the remaining carry (0 or 1) is returned.
|
|
|
1365 */
|
|
|
1366 static digit
|
|
|
1367 v_iadd(digit *x, Py_ssize_t m, digit *y, Py_ssize_t n)
|
|
|
1368 {
|
|
|
1369 Py_ssize_t i;
|
|
|
1370 digit carry = 0;
|
|
|
1371
|
|
|
1372 assert(m >= n);
|
|
|
1373 for (i = 0; i < n; ++i) {
|
|
|
1374 carry += x[i] + y[i];
|
|
|
1375 x[i] = carry & PyLong_MASK;
|
|
|
1376 carry >>= PyLong_SHIFT;
|
|
|
1377 assert((carry & 1) == carry);
|
|
|
1378 }
|
|
|
1379 for (; carry && i < m; ++i) {
|
|
|
1380 carry += x[i];
|
|
|
1381 x[i] = carry & PyLong_MASK;
|
|
|
1382 carry >>= PyLong_SHIFT;
|
|
|
1383 assert((carry & 1) == carry);
|
|
|
1384 }
|
|
|
1385 return carry;
|
|
|
1386 }
|
|
|
1387
|
|
|
1388 /* x[0:m] and y[0:n] are digit vectors, LSD first, m >= n required. x[0:n]
|
|
|
1389 * is modified in place, by subtracting y from it. Borrows are propagated as
|
|
|
1390 * far as x[m-1], and the remaining borrow (0 or 1) is returned.
|
|
|
1391 */
|
|
|
1392 static digit
|
|
|
1393 v_isub(digit *x, Py_ssize_t m, digit *y, Py_ssize_t n)
|
|
|
1394 {
|
|
|
1395 Py_ssize_t i;
|
|
|
1396 digit borrow = 0;
|
|
|
1397
|
|
|
1398 assert(m >= n);
|
|
|
1399 for (i = 0; i < n; ++i) {
|
|
|
1400 borrow = x[i] - y[i] - borrow;
|
|
|
1401 x[i] = borrow & PyLong_MASK;
|
|
|
1402 borrow >>= PyLong_SHIFT;
|
|
|
1403 borrow &= 1; /* keep only 1 sign bit */
|
|
|
1404 }
|
|
|
1405 for (; borrow && i < m; ++i) {
|
|
|
1406 borrow = x[i] - borrow;
|
|
|
1407 x[i] = borrow & PyLong_MASK;
|
|
|
1408 borrow >>= PyLong_SHIFT;
|
|
|
1409 borrow &= 1;
|
|
|
1410 }
|
|
|
1411 return borrow;
|
|
|
1412 }
|
|
|
1413
|
|
|
1414 /* Shift digit vector a[0:m] d bits left, with 0 <= d < PyLong_SHIFT. Put
|
|
|
1415 * result in z[0:m], and return the d bits shifted out of the top.
|
|
|
1416 */
|
|
|
1417 static digit
|
|
|
1418 v_lshift(digit *z, digit *a, Py_ssize_t m, int d)
|
|
|
1419 {
|
|
|
1420 Py_ssize_t i;
|
|
|
1421 digit carry = 0;
|
|
|
1422
|
|
|
1423 assert(0 <= d && d < PyLong_SHIFT);
|
|
|
1424 for (i=0; i < m; i++) {
|
|
|
1425 twodigits acc = (twodigits)a[i] << d | carry;
|
|
|
1426 z[i] = (digit)acc & PyLong_MASK;
|
|
|
1427 carry = (digit)(acc >> PyLong_SHIFT);
|
|
|
1428 }
|
|
|
1429 return carry;
|
|
|
1430 }
|
|
|
1431
|
|
|
1432 /* Shift digit vector a[0:m] d bits right, with 0 <= d < PyLong_SHIFT. Put
|
|
|
1433 * result in z[0:m], and return the d bits shifted out of the bottom.
|
|
|
1434 */
|
|
|
1435 static digit
|
|
|
1436 v_rshift(digit *z, digit *a, Py_ssize_t m, int d)
|
|
|
1437 {
|
|
|
1438 Py_ssize_t i;
|
|
|
1439 digit carry = 0;
|
|
|
1440 digit mask = ((digit)1 << d) - 1U;
|
|
|
1441
|
|
|
1442 assert(0 <= d && d < PyLong_SHIFT);
|
|
|
1443 for (i=m; i-- > 0;) {
|
|
|
1444 twodigits acc = (twodigits)carry << PyLong_SHIFT | a[i];
|
|
|
1445 carry = (digit)acc & mask;
|
|
|
1446 z[i] = (digit)(acc >> d);
|
|
|
1447 }
|
|
|
1448 return carry;
|
|
|
1449 }
|
|
|
1450
|
|
|
1451 /* Divide long pin, w/ size digits, by non-zero digit n, storing quotient
|
|
|
1452 in pout, and returning the remainder. pin and pout point at the LSD.
|
|
|
1453 It's OK for pin == pout on entry, which saves oodles of mallocs/frees in
|
|
|
1454 _PyLong_Format, but that should be done with great care since longs are
|
|
|
1455 immutable. */
|
|
|
1456
|
|
|
1457 static digit
|
|
|
1458 inplace_divrem1(digit *pout, digit *pin, Py_ssize_t size, digit n)
|
|
|
1459 {
|
|
|
1460 twodigits rem = 0;
|
|
|
1461
|
|
|
1462 assert(n > 0 && n <= PyLong_MASK);
|
|
|
1463 pin += size;
|
|
|
1464 pout += size;
|
|
|
1465 while (--size >= 0) {
|
|
|
1466 digit hi;
|
|
|
1467 rem = (rem << PyLong_SHIFT) | *--pin;
|
|
|
1468 *--pout = hi = (digit)(rem / n);
|
|
|
1469 rem -= (twodigits)hi * n;
|
|
|
1470 }
|
|
|
1471 return (digit)rem;
|
|
|
1472 }
|
|
|
1473
|
|
|
1474 /* Divide a long integer by a digit, returning both the quotient
|
|
|
1475 (as function result) and the remainder (through *prem).
|
|
|
1476 The sign of a is ignored; n should not be zero. */
|
|
|
1477
|
|
|
1478 static PyLongObject *
|
|
|
1479 divrem1(PyLongObject *a, digit n, digit *prem)
|
|
|
1480 {
|
|
|
1481 const Py_ssize_t size = ABS(Py_SIZE(a));
|
|
|
1482 PyLongObject *z;
|
|
|
1483
|
|
|
1484 assert(n > 0 && n <= PyLong_MASK);
|
|
|
1485 z = _PyLong_New(size);
|
|
|
1486 if (z == NULL)
|
|
|
1487 return NULL;
|
|
|
1488 *prem = inplace_divrem1(z->ob_digit, a->ob_digit, size, n);
|
|
|
1489 return long_normalize(z);
|
|
|
1490 }
|
|
|
1491
|
|
|
1492 /* Convert a long integer to a base 10 string. Returns a new non-shared
|
|
|
1493 string. (Return value is non-shared so that callers can modify the
|
|
|
1494 returned value if necessary.) */
|
|
|
1495
|
|
|
1496 static PyObject *
|
|
|
1497 long_to_decimal_string(PyObject *aa)
|
|
|
1498 {
|
|
|
1499 PyLongObject *scratch, *a;
|
|
|
1500 PyObject *str;
|
|
|
1501 Py_ssize_t size, strlen, size_a, i, j;
|
|
|
1502 digit *pout, *pin, rem, tenpow;
|
|
|
1503 unsigned char *p;
|
|
|
1504 int negative;
|
|
|
1505
|
|
|
1506 a = (PyLongObject *)aa;
|
|
|
1507 if (a == NULL || !PyLong_Check(a)) {
|
|
|
1508 PyErr_BadInternalCall();
|
|
|
1509 return NULL;
|
|
|
1510 }
|
|
|
1511 size_a = ABS(Py_SIZE(a));
|
|
|
1512 negative = Py_SIZE(a) < 0;
|
|
|
1513
|
|
|
1514 /* quick and dirty upper bound for the number of digits
|
|
|
1515 required to express a in base _PyLong_DECIMAL_BASE:
|
|
|
1516
|
|
|
1517 #digits = 1 + floor(log2(a) / log2(_PyLong_DECIMAL_BASE))
|
|
|
1518
|
|
|
1519 But log2(a) < size_a * PyLong_SHIFT, and
|
|
|
1520 log2(_PyLong_DECIMAL_BASE) = log2(10) * _PyLong_DECIMAL_SHIFT
|
|
|
1521 > 3 * _PyLong_DECIMAL_SHIFT
|
|
|
1522 */
|
|
|
1523 if (size_a > PY_SSIZE_T_MAX / PyLong_SHIFT) {
|
|
|
1524 PyErr_SetString(PyExc_OverflowError,
|
|
|
1525 "long is too large to format");
|
|
|
1526 return NULL;
|
|
|
1527 }
|
|
|
1528 /* the expression size_a * PyLong_SHIFT is now safe from overflow */
|
|
|
1529 size = 1 + size_a * PyLong_SHIFT / (3 * _PyLong_DECIMAL_SHIFT);
|
|
|
1530 scratch = _PyLong_New(size);
|
|
|
1531 if (scratch == NULL)
|
|
|
1532 return NULL;
|
|
|
1533
|
|
|
1534 /* convert array of base _PyLong_BASE digits in pin to an array of
|
|
|
1535 base _PyLong_DECIMAL_BASE digits in pout, following Knuth (TAOCP,
|
|
|
1536 Volume 2 (3rd edn), section 4.4, Method 1b). */
|
|
|
1537 pin = a->ob_digit;
|
|
|
1538 pout = scratch->ob_digit;
|
|
|
1539 size = 0;
|
|
|
1540 for (i = size_a; --i >= 0; ) {
|
|
|
1541 digit hi = pin[i];
|
|
|
1542 for (j = 0; j < size; j++) {
|
|
|
1543 twodigits z = (twodigits)pout[j] << PyLong_SHIFT | hi;
|
|
|
1544 hi = (digit)(z / _PyLong_DECIMAL_BASE);
|
|
|
1545 pout[j] = (digit)(z - (twodigits)hi *
|
|
|
1546 _PyLong_DECIMAL_BASE);
|
|
|
1547 }
|
|
|
1548 while (hi) {
|
|
|
1549 pout[size++] = hi % _PyLong_DECIMAL_BASE;
|
|
|
1550 hi /= _PyLong_DECIMAL_BASE;
|
|
|
1551 }
|
|
|
1552 /* check for keyboard interrupt */
|
|
|
1553 SIGCHECK({
|
|
|
1554 Py_DECREF(scratch);
|
|
|
1555 return NULL;
|
|
|
1556 });
|
|
|
1557 }
|
|
|
1558 /* pout should have at least one digit, so that the case when a = 0
|
|
|
1559 works correctly */
|
|
|
1560 if (size == 0)
|
|
|
1561 pout[size++] = 0;
|
|
|
1562
|
|
|
1563 /* calculate exact length of output string, and allocate */
|
|
|
1564 strlen = negative + 1 + (size - 1) * _PyLong_DECIMAL_SHIFT;
|
|
|
1565 tenpow = 10;
|
|
|
1566 rem = pout[size-1];
|
|
|
1567 while (rem >= tenpow) {
|
|
|
1568 tenpow *= 10;
|
|
|
1569 strlen++;
|
|
|
1570 }
|
|
|
1571 str = PyUnicode_New(strlen, '9');
|
|
|
1572 if (str == NULL) {
|
|
|
1573 Py_DECREF(scratch);
|
|
|
1574 return NULL;
|
|
|
1575 }
|
|
|
1576
|
|
|
1577 /* fill the string right-to-left */
|
|
|
1578 assert(PyUnicode_KIND(str) == PyUnicode_1BYTE_KIND);
|
|
|
1579 p = PyUnicode_1BYTE_DATA(str) + strlen;
|
|
|
1580 *p = '\0';
|
|
|
1581 /* pout[0] through pout[size-2] contribute exactly
|
|
|
1582 _PyLong_DECIMAL_SHIFT digits each */
|
|
|
1583 for (i=0; i < size - 1; i++) {
|
|
|
1584 rem = pout[i];
|
|
|
1585 for (j = 0; j < _PyLong_DECIMAL_SHIFT; j++) {
|
|
|
1586 *--p = '0' + rem % 10;
|
|
|
1587 rem /= 10;
|
|
|
1588 }
|
|
|
1589 }
|
|
|
1590 /* pout[size-1]: always produce at least one decimal digit */
|
|
|
1591 rem = pout[i];
|
|
|
1592 do {
|
|
|
1593 *--p = '0' + rem % 10;
|
|
|
1594 rem /= 10;
|
|
|
1595 } while (rem != 0);
|
|
|
1596
|
|
|
1597 /* and sign */
|
|
|
1598 if (negative)
|
|
|
1599 *--p = '-';
|
|
|
1600
|
|
|
1601 /* check we've counted correctly */
|
|
|
1602 assert(p == PyUnicode_1BYTE_DATA(str));
|
|
|
1603 Py_DECREF(scratch);
|
|
|
1604 return (PyObject *)str;
|
|
|
1605 }
|
|
|
1606
|
|
|
1607 /* Convert a long int object to a string, using a given conversion base,
|
|
|
1608 which should be one of 2, 8, 10 or 16. Return a string object.
|
|
|
1609 If base is 2, 8 or 16, add the proper prefix '0b', '0o' or '0x'. */
|
|
|
1610
|
|
|
1611 PyObject *
|
|
|
1612 _PyLong_Format(PyObject *aa, int base)
|
|
|
1613 {
|
|
|
1614 register PyLongObject *a = (PyLongObject *)aa;
|
|
|
1615 PyObject *v;
|
|
|
1616 Py_ssize_t i, sz;
|
|
|
1617 Py_ssize_t size_a;
|
|
|
1618 char *p;
|
|
|
1619 char sign = '\0';
|
|
|
1620 char *buffer;
|
|
|
1621 int bits;
|
|
|
1622
|
|
|
1623 assert(base == 2 || base == 8 || base == 10 || base == 16);
|
|
|
1624 if (base == 10)
|
|
|
1625 return long_to_decimal_string((PyObject *)a);
|
|
|
1626
|
|
|
1627 if (a == NULL || !PyLong_Check(a)) {
|
|
|
1628 PyErr_BadInternalCall();
|
|
|
1629 return NULL;
|
|
|
1630 }
|
|
|
1631 size_a = ABS(Py_SIZE(a));
|
|
|
1632
|
|
|
1633 /* Compute a rough upper bound for the length of the string */
|
|
|
1634 switch (base) {
|
|
|
1635 case 16:
|
|
|
1636 bits = 4;
|
|
|
1637 break;
|
|
|
1638 case 8:
|
|
|
1639 bits = 3;
|
|
|
1640 break;
|
|
|
1641 case 2:
|
|
|
1642 bits = 1;
|
|
|
1643 break;
|
|
|
1644 default:
|
|
|
1645 assert(0); /* shouldn't ever get here */
|
|
|
1646 bits = 0; /* to silence gcc warning */
|
|
|
1647 }
|
|
|
1648 /* compute length of output string: allow 2 characters for prefix and
|
|
|
1649 1 for possible '-' sign. */
|
|
|
1650 if (size_a > (PY_SSIZE_T_MAX - 3) / PyLong_SHIFT / sizeof(Py_UCS4)) {
|
|
|
1651 PyErr_SetString(PyExc_OverflowError,
|
|
|
1652 "int is too large to format");
|
|
|
1653 return NULL;
|
|
|
1654 }
|
|
|
1655 /* now size_a * PyLong_SHIFT + 3 <= PY_SSIZE_T_MAX, so the RHS below
|
|
|
1656 is safe from overflow */
|
|
|
1657 sz = 3 + (size_a * PyLong_SHIFT + (bits - 1)) / bits;
|
|
|
1658 assert(sz >= 0);
|
|
|
1659 buffer = PyMem_Malloc(sz);
|
|
|
1660 if (buffer == NULL) {
|
|
|
1661 PyErr_NoMemory();
|
|
|
1662 return NULL;
|
|
|
1663 }
|
|
|
1664 p = &buffer[sz];
|
|
|
1665 if (Py_SIZE(a) < 0)
|
|
|
1666 sign = '-';
|
|
|
1667
|
|
|
1668 if (Py_SIZE(a) == 0) {
|
|
|
1669 *--p = '0';
|
|
|
1670 }
|
|
|
1671 else {
|
|
|
1672 /* JRH: special case for power-of-2 bases */
|
|
|
1673 twodigits accum = 0;
|
|
|
1674 int accumbits = 0; /* # of bits in accum */
|
|
|
1675 for (i = 0; i < size_a; ++i) {
|
|
|
1676 accum |= (twodigits)a->ob_digit[i] << accumbits;
|
|
|
1677 accumbits += PyLong_SHIFT;
|
|
|
1678 assert(accumbits >= bits);
|
|
|
1679 do {
|
|
|
1680 char cdigit;
|
|
|
1681 cdigit = (char)(accum & (base - 1));
|
|
|
1682 cdigit += (cdigit < 10) ? '0' : 'a'-10;
|
|
|
1683 assert(p > buffer);
|
|
|
1684 *--p = cdigit;
|
|
|
1685 accumbits -= bits;
|
|
|
1686 accum >>= bits;
|
|
|
1687 } while (i < size_a-1 ? accumbits >= bits : accum > 0);
|
|
|
1688 }
|
|
|
1689 }
|
|
|
1690
|
|
|
1691 if (base == 16)
|
|
|
1692 *--p = 'x';
|
|
|
1693 else if (base == 8)
|
|
|
1694 *--p = 'o';
|
|
|
1695 else /* (base == 2) */
|
|
|
1696 *--p = 'b';
|
|
|
1697 *--p = '0';
|
|
|
1698 if (sign)
|
|
|
1699 *--p = sign;
|
|
|
1700 v = PyUnicode_DecodeASCII(p, &buffer[sz] - p, NULL);
|
|
|
1701 PyMem_Free(buffer);
|
|
|
1702 return v;
|
|
|
1703 }
|
|
|
1704
|
|
|
1705 /* Table of digit values for 8-bit string -> integer conversion.
|
|
|
1706 * '0' maps to 0, ..., '9' maps to 9.
|
|
|
1707 * 'a' and 'A' map to 10, ..., 'z' and 'Z' map to 35.
|
|
|
1708 * All other indices map to 37.
|
|
|
1709 * Note that when converting a base B string, a char c is a legitimate
|
|
|
1710 * base B digit iff _PyLong_DigitValue[Py_CHARPyLong_MASK(c)] < B.
|
|
|
1711 */
|
|
|
1712 unsigned char _PyLong_DigitValue[256] = {
|
|
|
1713 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37,
|
|
|
1714 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37,
|
|
|
1715 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37,
|
|
|
1716 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 37, 37, 37, 37, 37, 37,
|
|
|
1717 37, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24,
|
|
|
1718 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 37, 37, 37, 37, 37,
|
|
|
1719 37, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24,
|
|
|
1720 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 37, 37, 37, 37, 37,
|
|
|
1721 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37,
|
|
|
1722 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37,
|
|
|
1723 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37,
|
|
|
1724 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37,
|
|
|
1725 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37,
|
|
|
1726 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37,
|
|
|
1727 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37,
|
|
|
1728 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37,
|
|
|
1729 };
|
|
|
1730
|
|
|
1731 /* *str points to the first digit in a string of base `base` digits. base
|
|
|
1732 * is a power of 2 (2, 4, 8, 16, or 32). *str is set to point to the first
|
|
|
1733 * non-digit (which may be *str!). A normalized long is returned.
|
|
|
1734 * The point to this routine is that it takes time linear in the number of
|
|
|
1735 * string characters.
|
|
|
1736 */
|
|
|
1737 static PyLongObject *
|
|
|
1738 long_from_binary_base(char **str, int base)
|
|
|
1739 {
|
|
|
1740 char *p = *str;
|
|
|
1741 char *start = p;
|
|
|
1742 int bits_per_char;
|
|
|
1743 Py_ssize_t n;
|
|
|
1744 PyLongObject *z;
|
|
|
1745 twodigits accum;
|
|
|
1746 int bits_in_accum;
|
|
|
1747 digit *pdigit;
|
|
|
1748
|
|
|
1749 assert(base >= 2 && base <= 32 && (base & (base - 1)) == 0);
|
|
|
1750 n = base;
|
|
|
1751 for (bits_per_char = -1; n; ++bits_per_char)
|
|
|
1752 n >>= 1;
|
|
|
1753 /* n <- total # of bits needed, while setting p to end-of-string */
|
|
|
1754 while (_PyLong_DigitValue[Py_CHARMASK(*p)] < base)
|
|
|
1755 ++p;
|
|
|
1756 *str = p;
|
|
|
1757 /* n <- # of Python digits needed, = ceiling(n/PyLong_SHIFT). */
|
|
|
1758 n = (p - start) * bits_per_char + PyLong_SHIFT - 1;
|
|
|
1759 if (n / bits_per_char < p - start) {
|
|
|
1760 PyErr_SetString(PyExc_ValueError,
|
|
|
1761 "int string too large to convert");
|
|
|
1762 return NULL;
|
|
|
1763 }
|
|
|
1764 n = n / PyLong_SHIFT;
|
|
|
1765 z = _PyLong_New(n);
|
|
|
1766 if (z == NULL)
|
|
|
1767 return NULL;
|
|
|
1768 /* Read string from right, and fill in long from left; i.e.,
|
|
|
1769 * from least to most significant in both.
|
|
|
1770 */
|
|
|
1771 accum = 0;
|
|
|
1772 bits_in_accum = 0;
|
|
|
1773 pdigit = z->ob_digit;
|
|
|
1774 while (--p >= start) {
|
|
|
1775 int k = (int)_PyLong_DigitValue[Py_CHARMASK(*p)];
|
|
|
1776 assert(k >= 0 && k < base);
|
|
|
1777 accum |= (twodigits)k << bits_in_accum;
|
|
|
1778 bits_in_accum += bits_per_char;
|
|
|
1779 if (bits_in_accum >= PyLong_SHIFT) {
|
|
|
1780 *pdigit++ = (digit)(accum & PyLong_MASK);
|
|
|
1781 assert(pdigit - z->ob_digit <= n);
|
|
|
1782 accum >>= PyLong_SHIFT;
|
|
|
1783 bits_in_accum -= PyLong_SHIFT;
|
|
|
1784 assert(bits_in_accum < PyLong_SHIFT);
|
|
|
1785 }
|
|
|
1786 }
|
|
|
1787 if (bits_in_accum) {
|
|
|
1788 assert(bits_in_accum <= PyLong_SHIFT);
|
|
|
1789 *pdigit++ = (digit)accum;
|
|
|
1790 assert(pdigit - z->ob_digit <= n);
|
|
|
1791 }
|
|
|
1792 while (pdigit - z->ob_digit < n)
|
|
|
1793 *pdigit++ = 0;
|
|
|
1794 return long_normalize(z);
|
|
|
1795 }
|
|
|
1796
|
|
|
1797 PyObject *
|
|
|
1798 PyLong_FromString(char *str, char **pend, int base)
|
|
|
1799 {
|
|
|
1800 int sign = 1, error_if_nonzero = 0;
|
|
|
1801 char *start, *orig_str = str;
|
|
|
1802 PyLongObject *z = NULL;
|
|
|
1803 PyObject *strobj;
|
|
|
1804 Py_ssize_t slen;
|
|
|
1805
|
|
|
1806 if ((base != 0 && base < 2) || base > 36) {
|
|
|
1807 PyErr_SetString(PyExc_ValueError,
|
|
|
1808 "int() arg 2 must be >= 2 and <= 36");
|
|
|
1809 return NULL;
|
|
|
1810 }
|
|
|
1811 while (*str != '\0' && isspace(Py_CHARMASK(*str)))
|
|
|
1812 str++;
|
|
|
1813 if (*str == '+')
|
|
|
1814 ++str;
|
|
|
1815 else if (*str == '-') {
|
|
|
1816 ++str;
|
|
|
1817 sign = -1;
|
|
|
1818 }
|
|
|
1819 if (base == 0) {
|
|
|
1820 if (str[0] != '0')
|
|
|
1821 base = 10;
|
|
|
1822 else if (str[1] == 'x' || str[1] == 'X')
|
|
|
1823 base = 16;
|
|
|
1824 else if (str[1] == 'o' || str[1] == 'O')
|
|
|
1825 base = 8;
|
|
|
1826 else if (str[1] == 'b' || str[1] == 'B')
|
|
|
1827 base = 2;
|
|
|
1828 else {
|
|
|
1829 /* "old" (C-style) octal literal, now invalid.
|
|
|
1830 it might still be zero though */
|
|
|
1831 error_if_nonzero = 1;
|
|
|
1832 base = 10;
|
|
|
1833 }
|
|
|
1834 }
|
|
|
1835 if (str[0] == '0' &&
|
|
|
1836 ((base == 16 && (str[1] == 'x' || str[1] == 'X')) ||
|
|
|
1837 (base == 8 && (str[1] == 'o' || str[1] == 'O')) ||
|
|
|
1838 (base == 2 && (str[1] == 'b' || str[1] == 'B'))))
|
|
|
1839 str += 2;
|
|
|
1840
|
|
|
1841 start = str;
|
|
|
1842 if ((base & (base - 1)) == 0)
|
|
|
1843 z = long_from_binary_base(&str, base);
|
|
|
1844 else {
|
|
|
1845 /***
|
|
|
1846 Binary bases can be converted in time linear in the number of digits, because
|
|
|
1847 Python's representation base is binary. Other bases (including decimal!) use
|
|
|
1848 the simple quadratic-time algorithm below, complicated by some speed tricks.
|
|
|
1849
|
|
|
1850 First some math: the largest integer that can be expressed in N base-B digits
|
|
|
1851 is B**N-1. Consequently, if we have an N-digit input in base B, the worst-
|
|
|
1852 case number of Python digits needed to hold it is the smallest integer n s.t.
|
|
|
1853
|
|
|
1854 BASE**n-1 >= B**N-1 [or, adding 1 to both sides]
|
|
|
1855 BASE**n >= B**N [taking logs to base BASE]
|
|
|
1856 n >= log(B**N)/log(BASE) = N * log(B)/log(BASE)
|
|
|
1857
|
|
|
1858 The static array log_base_BASE[base] == log(base)/log(BASE) so we can compute
|
|
|
1859 this quickly. A Python long with that much space is reserved near the start,
|
|
|
1860 and the result is computed into it.
|
|
|
1861
|
|
|
1862 The input string is actually treated as being in base base**i (i.e., i digits
|
|
|
1863 are processed at a time), where two more static arrays hold:
|
|
|
1864
|
|
|
1865 convwidth_base[base] = the largest integer i such that base**i <= BASE
|
|
|
1866 convmultmax_base[base] = base ** convwidth_base[base]
|
|
|
1867
|
|
|
1868 The first of these is the largest i such that i consecutive input digits
|
|
|
1869 must fit in a single Python digit. The second is effectively the input
|
|
|
1870 base we're really using.
|
|
|
1871
|
|
|
1872 Viewing the input as a sequence <c0, c1, ..., c_n-1> of digits in base
|
|
|
1873 convmultmax_base[base], the result is "simply"
|
|
|
1874
|
|
|
1875 (((c0*B + c1)*B + c2)*B + c3)*B + ... ))) + c_n-1
|
|
|
1876
|
|
|
1877 where B = convmultmax_base[base].
|
|
|
1878
|
|
|
1879 Error analysis: as above, the number of Python digits `n` needed is worst-
|
|
|
1880 case
|
|
|
1881
|
|
|
1882 n >= N * log(B)/log(BASE)
|
|
|
1883
|
|
|
1884 where `N` is the number of input digits in base `B`. This is computed via
|
|
|
1885
|
|
|
1886 size_z = (Py_ssize_t)((scan - str) * log_base_BASE[base]) + 1;
|
|
|
1887
|
|
|
1888 below. Two numeric concerns are how much space this can waste, and whether
|
|
|
1889 the computed result can be too small. To be concrete, assume BASE = 2**15,
|
|
|
1890 which is the default (and it's unlikely anyone changes that).
|
|
|
1891
|
|
|
1892 Waste isn't a problem: provided the first input digit isn't 0, the difference
|
|
|
1893 between the worst-case input with N digits and the smallest input with N
|
|
|
1894 digits is about a factor of B, but B is small compared to BASE so at most
|
|
|
1895 one allocated Python digit can remain unused on that count. If
|
|
|
1896 N*log(B)/log(BASE) is mathematically an exact integer, then truncating that
|
|
|
1897 and adding 1 returns a result 1 larger than necessary. However, that can't
|
|
|
1898 happen: whenever B is a power of 2, long_from_binary_base() is called
|
|
|
1899 instead, and it's impossible for B**i to be an integer power of 2**15 when
|
|
|
1900 B is not a power of 2 (i.e., it's impossible for N*log(B)/log(BASE) to be
|
|
|
1901 an exact integer when B is not a power of 2, since B**i has a prime factor
|
|
|
1902 other than 2 in that case, but (2**15)**j's only prime factor is 2).
|
|
|
1903
|
|
|
1904 The computed result can be too small if the true value of N*log(B)/log(BASE)
|
|
|
1905 is a little bit larger than an exact integer, but due to roundoff errors (in
|
|
|
1906 computing log(B), log(BASE), their quotient, and/or multiplying that by N)
|
|
|
1907 yields a numeric result a little less than that integer. Unfortunately, "how
|
|
|
1908 close can a transcendental function get to an integer over some range?"
|
|
|
1909 questions are generally theoretically intractable. Computer analysis via
|
|
|
1910 continued fractions is practical: expand log(B)/log(BASE) via continued
|
|
|
1911 fractions, giving a sequence i/j of "the best" rational approximations. Then
|
|
|
1912 j*log(B)/log(BASE) is approximately equal to (the integer) i. This shows that
|
|
|
1913 we can get very close to being in trouble, but very rarely. For example,
|
|
|
1914 76573 is a denominator in one of the continued-fraction approximations to
|
|
|
1915 log(10)/log(2**15), and indeed:
|
|
|
1916
|
|
|
1917 >>> log(10)/log(2**15)*76573
|
|
|
1918 16958.000000654003
|
|
|
1919
|
|
|
1920 is very close to an integer. If we were working with IEEE single-precision,
|
|
|
1921 rounding errors could kill us. Finding worst cases in IEEE double-precision
|
|
|
1922 requires better-than-double-precision log() functions, and Tim didn't bother.
|
|
|
1923 Instead the code checks to see whether the allocated space is enough as each
|
|
|
1924 new Python digit is added, and copies the whole thing to a larger long if not.
|
|
|
1925 This should happen extremely rarely, and in fact I don't have a test case
|
|
|
1926 that triggers it(!). Instead the code was tested by artificially allocating
|
|
|
1927 just 1 digit at the start, so that the copying code was exercised for every
|
|
|
1928 digit beyond the first.
|
|
|
1929 ***/
|
|
|
1930 register twodigits c; /* current input character */
|
|
|
1931 Py_ssize_t size_z;
|
|
|
1932 int i;
|
|
|
1933 int convwidth;
|
|
|
1934 twodigits convmultmax, convmult;
|
|
|
1935 digit *pz, *pzstop;
|
|
|
1936 char* scan;
|
|
|
1937
|
|
|
1938 static double log_base_BASE[37] = {0.0e0,};
|
|
|
1939 static int convwidth_base[37] = {0,};
|
|
|
1940 static twodigits convmultmax_base[37] = {0,};
|
|
|
1941
|
|
|
1942 if (log_base_BASE[base] == 0.0) {
|
|
|
1943 twodigits convmax = base;
|
|
|
1944 int i = 1;
|
|
|
1945
|
|
|
1946 log_base_BASE[base] = (log((double)base) /
|
|
|
1947 log((double)PyLong_BASE));
|
|
|
1948 for (;;) {
|
|
|
1949 twodigits next = convmax * base;
|
|
|
1950 if (next > PyLong_BASE)
|
|
|
1951 break;
|
|
|
1952 convmax = next;
|
|
|
1953 ++i;
|
|
|
1954 }
|
|
|
1955 convmultmax_base[base] = convmax;
|
|
|
1956 assert(i > 0);
|
|
|
1957 convwidth_base[base] = i;
|
|
|
1958 }
|
|
|
1959
|
|
|
1960 /* Find length of the string of numeric characters. */
|
|
|
1961 scan = str;
|
|
|
1962 while (_PyLong_DigitValue[Py_CHARMASK(*scan)] < base)
|
|
|
1963 ++scan;
|
|
|
1964
|
|
|
1965 /* Create a long object that can contain the largest possible
|
|
|
1966 * integer with this base and length. Note that there's no
|
|
|
1967 * need to initialize z->ob_digit -- no slot is read up before
|
|
|
1968 * being stored into.
|
|
|
1969 */
|
|
|
1970 size_z = (Py_ssize_t)((scan - str) * log_base_BASE[base]) + 1;
|
|
|
1971 /* Uncomment next line to test exceedingly rare copy code */
|
|
|
1972 /* size_z = 1; */
|
|
|
1973 assert(size_z > 0);
|
|
|
1974 z = _PyLong_New(size_z);
|
|
|
1975 if (z == NULL)
|
|
|
1976 return NULL;
|
|
|
1977 Py_SIZE(z) = 0;
|
|
|
1978
|
|
|
1979 /* `convwidth` consecutive input digits are treated as a single
|
|
|
1980 * digit in base `convmultmax`.
|
|
|
1981 */
|
|
|
1982 convwidth = convwidth_base[base];
|
|
|
1983 convmultmax = convmultmax_base[base];
|
|
|
1984
|
|
|
1985 /* Work ;-) */
|
|
|
1986 while (str < scan) {
|
|
|
1987 /* grab up to convwidth digits from the input string */
|
|
|
1988 c = (digit)_PyLong_DigitValue[Py_CHARMASK(*str++)];
|
|
|
1989 for (i = 1; i < convwidth && str != scan; ++i, ++str) {
|
|
|
1990 c = (twodigits)(c * base +
|
|
|
1991 (int)_PyLong_DigitValue[Py_CHARMASK(*str)]);
|
|
|
1992 assert(c < PyLong_BASE);
|
|
|
1993 }
|
|
|
1994
|
|
|
1995 convmult = convmultmax;
|
|
|
1996 /* Calculate the shift only if we couldn't get
|
|
|
1997 * convwidth digits.
|
|
|
1998 */
|
|
|
1999 if (i != convwidth) {
|
|
|
2000 convmult = base;
|
|
|
2001 for ( ; i > 1; --i)
|
|
|
2002 convmult *= base;
|
|
|
2003 }
|
|
|
2004
|
|
|
2005 /* Multiply z by convmult, and add c. */
|
|
|
2006 pz = z->ob_digit;
|
|
|
2007 pzstop = pz + Py_SIZE(z);
|
|
|
2008 for (; pz < pzstop; ++pz) {
|
|
|
2009 c += (twodigits)*pz * convmult;
|
|
|
2010 *pz = (digit)(c & PyLong_MASK);
|
|
|
2011 c >>= PyLong_SHIFT;
|
|
|
2012 }
|
|
|
2013 /* carry off the current end? */
|
|
|
2014 if (c) {
|
|
|
2015 assert(c < PyLong_BASE);
|
|
|
2016 if (Py_SIZE(z) < size_z) {
|
|
|
2017 *pz = (digit)c;
|
|
|
2018 ++Py_SIZE(z);
|
|
|
2019 }
|
|
|
2020 else {
|
|
|
2021 PyLongObject *tmp;
|
|
|
2022 /* Extremely rare. Get more space. */
|
|
|
2023 assert(Py_SIZE(z) == size_z);
|
|
|
2024 tmp = _PyLong_New(size_z + 1);
|
|
|
2025 if (tmp == NULL) {
|
|
|
2026 Py_DECREF(z);
|
|
|
2027 return NULL;
|
|
|
2028 }
|
|
|
2029 memcpy(tmp->ob_digit,
|
|
|
2030 z->ob_digit,
|
|
|
2031 sizeof(digit) * size_z);
|
|
|
2032 Py_DECREF(z);
|
|
|
2033 z = tmp;
|
|
|
2034 z->ob_digit[size_z] = (digit)c;
|
|
|
2035 ++size_z;
|
|
|
2036 }
|
|
|
2037 }
|
|
|
2038 }
|
|
|
2039 }
|
|
|
2040 if (z == NULL)
|
|
|
2041 return NULL;
|
|
|
2042 if (error_if_nonzero) {
|
|
|
2043 /* reset the base to 0, else the exception message
|
|
|
2044 doesn't make too much sense */
|
|
|
2045 base = 0;
|
|
|
2046 if (Py_SIZE(z) != 0)
|
|
|
2047 goto onError;
|
|
|
2048 /* there might still be other problems, therefore base
|
|
|
2049 remains zero here for the same reason */
|
|
|
2050 }
|
|
|
2051 if (str == start)
|
|
|
2052 goto onError;
|
|
|
2053 if (sign < 0)
|
|
|
2054 Py_SIZE(z) = -(Py_SIZE(z));
|
|
|
2055 while (*str && isspace(Py_CHARMASK(*str)))
|
|
|
2056 str++;
|
|
|
2057 if (*str != '\0')
|
|
|
2058 goto onError;
|
|
|
2059 if (pend)
|
|
|
2060 *pend = str;
|
|
|
2061 long_normalize(z);
|
|
|
2062 return (PyObject *) maybe_small_long(z);
|
|
|
2063
|
|
|
2064 onError:
|
|
|
2065 Py_XDECREF(z);
|
|
|
2066 slen = strlen(orig_str) < 200 ? strlen(orig_str) : 200;
|
|
|
2067 strobj = PyUnicode_FromStringAndSize(orig_str, slen);
|
|
|
2068 if (strobj == NULL)
|
|
|
2069 return NULL;
|
|
|
2070 PyErr_Format(PyExc_ValueError,
|
|
|
2071 "invalid literal for int() with base %d: %R",
|
|
|
2072 base, strobj);
|
|
|
2073 Py_DECREF(strobj);
|
|
|
2074 return NULL;
|
|
|
2075 }
|
|
|
2076
|
|
|
2077 PyObject *
|
|
|
2078 PyLong_FromUnicode(Py_UNICODE *u, Py_ssize_t length, int base)
|
|
|
2079 {
|
|
|
2080 PyObject *v, *unicode = PyUnicode_FromUnicode(u, length);
|
|
|
2081 if (unicode == NULL)
|
|
|
2082 return NULL;
|
|
|
2083 v = PyLong_FromUnicodeObject(unicode, base);
|
|
|
2084 Py_DECREF(unicode);
|
|
|
2085 return v;
|
|
|
2086 }
|
|
|
2087
|
|
|
2088 PyObject *
|
|
|
2089 PyLong_FromUnicodeObject(PyObject *u, int base)
|
|
|
2090 {
|
|
|
2091 PyObject *result;
|
|
|
2092 PyObject *asciidig;
|
|
|
2093 char *buffer, *end;
|
|
|
2094 Py_ssize_t buflen;
|
|
|
2095
|
|
|
2096 asciidig = _PyUnicode_TransformDecimalAndSpaceToASCII(u);
|
|
|
2097 if (asciidig == NULL)
|
|
|
2098 return NULL;
|
|
|
2099 buffer = PyUnicode_AsUTF8AndSize(asciidig, &buflen);
|
|
|
2100 if (buffer == NULL) {
|
|
|
2101 Py_DECREF(asciidig);
|
|
|
2102 return NULL;
|
|
|
2103 }
|
|
|
2104 result = PyLong_FromString(buffer, &end, base);
|
|
|
2105 if (result != NULL && end != buffer + buflen) {
|
|
|
2106 PyErr_SetString(PyExc_ValueError,
|
|
|
2107 "null byte in argument for int()");
|
|
|
2108 Py_DECREF(result);
|
|
|
2109 result = NULL;
|
|
|
2110 }
|
|
|
2111 Py_DECREF(asciidig);
|
|
|
2112 return result;
|
|
|
2113 }
|
|
|
2114
|
|
|
2115 /* forward */
|
|
|
2116 static PyLongObject *x_divrem
|
|
|
2117 (PyLongObject *, PyLongObject *, PyLongObject **);
|
|
|
2118 static PyObject *long_long(PyObject *v);
|
|
|
2119
|
|
|
2120 /* Long division with remainder, top-level routine */
|
|
|
2121
|
|
|
2122 static int
|
|
|
2123 long_divrem(PyLongObject *a, PyLongObject *b,
|
|
|
2124 PyLongObject **pdiv, PyLongObject **prem)
|
|
|
2125 {
|
|
|
2126 Py_ssize_t size_a = ABS(Py_SIZE(a)), size_b = ABS(Py_SIZE(b));
|
|
|
2127 PyLongObject *z;
|
|
|
2128
|
|
|
2129 if (size_b == 0) {
|
|
|
2130 PyErr_SetString(PyExc_ZeroDivisionError,
|
|
|
2131 "integer division or modulo by zero");
|
|
|
2132 return -1;
|
|
|
2133 }
|
|
|
2134 if (size_a < size_b ||
|
|
|
2135 (size_a == size_b &&
|
|
|
2136 a->ob_digit[size_a-1] < b->ob_digit[size_b-1])) {
|
|
|
2137 /* |a| < |b|. */
|
|
|
2138 *pdiv = (PyLongObject*)PyLong_FromLong(0);
|
|
|
2139 if (*pdiv == NULL)
|
|
|
2140 return -1;
|
|
|
2141 Py_INCREF(a);
|
|
|
2142 *prem = (PyLongObject *) a;
|
|
|
2143 return 0;
|
|
|
2144 }
|
|
|
2145 if (size_b == 1) {
|
|
|
2146 digit rem = 0;
|
|
|
2147 z = divrem1(a, b->ob_digit[0], &rem);
|
|
|
2148 if (z == NULL)
|
|
|
2149 return -1;
|
|
|
2150 *prem = (PyLongObject *) PyLong_FromLong((long)rem);
|
|
|
2151 if (*prem == NULL) {
|
|
|
2152 Py_DECREF(z);
|
|
|
2153 return -1;
|
|
|
2154 }
|
|
|
2155 }
|
|
|
2156 else {
|
|
|
2157 z = x_divrem(a, b, prem);
|
|
|
2158 if (z == NULL)
|
|
|
2159 return -1;
|
|
|
2160 }
|
|
|
2161 /* Set the signs.
|
|
|
2162 The quotient z has the sign of a*b;
|
|
|
2163 the remainder r has the sign of a,
|
|
|
2164 so a = b*z + r. */
|
|
|
2165 if ((Py_SIZE(a) < 0) != (Py_SIZE(b) < 0))
|
|
|
2166 NEGATE(z);
|
|
|
2167 if (Py_SIZE(a) < 0 && Py_SIZE(*prem) != 0)
|
|
|
2168 NEGATE(*prem);
|
|
|
2169 *pdiv = maybe_small_long(z);
|
|
|
2170 return 0;
|
|
|
2171 }
|
|
|
2172
|
|
|
2173 /* Unsigned long division with remainder -- the algorithm. The arguments v1
|
|
|
2174 and w1 should satisfy 2 <= ABS(Py_SIZE(w1)) <= ABS(Py_SIZE(v1)). */
|
|
|
2175
|
|
|
2176 static PyLongObject *
|
|
|
2177 x_divrem(PyLongObject *v1, PyLongObject *w1, PyLongObject **prem)
|
|
|
2178 {
|
|
|
2179 PyLongObject *v, *w, *a;
|
|
|
2180 Py_ssize_t i, k, size_v, size_w;
|
|
|
2181 int d;
|
|
|
2182 digit wm1, wm2, carry, q, r, vtop, *v0, *vk, *w0, *ak;
|
|
|
2183 twodigits vv;
|
|
|
2184 sdigit zhi;
|
|
|
2185 stwodigits z;
|
|
|
2186
|
|
|
2187 /* We follow Knuth [The Art of Computer Programming, Vol. 2 (3rd
|
|
|
2188 edn.), section 4.3.1, Algorithm D], except that we don't explicitly
|
|
|
2189 handle the special case when the initial estimate q for a quotient
|
|
|
2190 digit is >= PyLong_BASE: the max value for q is PyLong_BASE+1, and
|
|
|
2191 that won't overflow a digit. */
|
|
|
2192
|
|
|
2193 /* allocate space; w will also be used to hold the final remainder */
|
|
|
2194 size_v = ABS(Py_SIZE(v1));
|
|
|
2195 size_w = ABS(Py_SIZE(w1));
|
|
|
2196 assert(size_v >= size_w && size_w >= 2); /* Assert checks by div() */
|
|
|
2197 v = _PyLong_New(size_v+1);
|
|
|
2198 if (v == NULL) {
|
|
|
2199 *prem = NULL;
|
|
|
2200 return NULL;
|
|
|
2201 }
|
|
|
2202 w = _PyLong_New(size_w);
|
|
|
2203 if (w == NULL) {
|
|
|
2204 Py_DECREF(v);
|
|
|
2205 *prem = NULL;
|
|
|
2206 return NULL;
|
|
|
2207 }
|
|
|
2208
|
|
|
2209 /* normalize: shift w1 left so that its top digit is >= PyLong_BASE/2.
|
|
|
2210 shift v1 left by the same amount. Results go into w and v. */
|
|
|
2211 d = PyLong_SHIFT - bits_in_digit(w1->ob_digit[size_w-1]);
|
|
|
2212 carry = v_lshift(w->ob_digit, w1->ob_digit, size_w, d);
|
|
|
2213 assert(carry == 0);
|
|
|
2214 carry = v_lshift(v->ob_digit, v1->ob_digit, size_v, d);
|
|
|
2215 if (carry != 0 || v->ob_digit[size_v-1] >= w->ob_digit[size_w-1]) {
|
|
|
2216 v->ob_digit[size_v] = carry;
|
|
|
2217 size_v++;
|
|
|
2218 }
|
|
|
2219
|
|
|
2220 /* Now v->ob_digit[size_v-1] < w->ob_digit[size_w-1], so quotient has
|
|
|
2221 at most (and usually exactly) k = size_v - size_w digits. */
|
|
|
2222 k = size_v - size_w;
|
|
|
2223 assert(k >= 0);
|
|
|
2224 a = _PyLong_New(k);
|
|
|
2225 if (a == NULL) {
|
|
|
2226 Py_DECREF(w);
|
|
|
2227 Py_DECREF(v);
|
|
|
2228 *prem = NULL;
|
|
|
2229 return NULL;
|
|
|
2230 }
|
|
|
2231 v0 = v->ob_digit;
|
|
|
2232 w0 = w->ob_digit;
|
|
|
2233 wm1 = w0[size_w-1];
|
|
|
2234 wm2 = w0[size_w-2];
|
|
|
2235 for (vk = v0+k, ak = a->ob_digit + k; vk-- > v0;) {
|
|
|
2236 /* inner loop: divide vk[0:size_w+1] by w0[0:size_w], giving
|
|
|
2237 single-digit quotient q, remainder in vk[0:size_w]. */
|
|
|
2238
|
|
|
2239 SIGCHECK({
|
|
|
2240 Py_DECREF(a);
|
|
|
2241 Py_DECREF(w);
|
|
|
2242 Py_DECREF(v);
|
|
|
2243 *prem = NULL;
|
|
|
2244 return NULL;
|
|
|
2245 });
|
|
|
2246
|
|
|
2247 /* estimate quotient digit q; may overestimate by 1 (rare) */
|
|
|
2248 vtop = vk[size_w];
|
|
|
2249 assert(vtop <= wm1);
|
|
|
2250 vv = ((twodigits)vtop << PyLong_SHIFT) | vk[size_w-1];
|
|
|
2251 q = (digit)(vv / wm1);
|
|
|
2252 r = (digit)(vv - (twodigits)wm1 * q); /* r = vv % wm1 */
|
|
|
2253 while ((twodigits)wm2 * q > (((twodigits)r << PyLong_SHIFT)
|
|
|
2254 | vk[size_w-2])) {
|
|
|
2255 --q;
|
|
|
2256 r += wm1;
|
|
|
2257 if (r >= PyLong_BASE)
|
|
|
2258 break;
|
|
|
2259 }
|
|
|
2260 assert(q <= PyLong_BASE);
|
|
|
2261
|
|
|
2262 /* subtract q*w0[0:size_w] from vk[0:size_w+1] */
|
|
|
2263 zhi = 0;
|
|
|
2264 for (i = 0; i < size_w; ++i) {
|
|
|
2265 /* invariants: -PyLong_BASE <= -q <= zhi <= 0;
|
|
|
2266 -PyLong_BASE * q <= z < PyLong_BASE */
|
|
|
2267 z = (sdigit)vk[i] + zhi -
|
|
|
2268 (stwodigits)q * (stwodigits)w0[i];
|
|
|
2269 vk[i] = (digit)z & PyLong_MASK;
|
|
|
2270 zhi = (sdigit)Py_ARITHMETIC_RIGHT_SHIFT(stwodigits,
|
|
|
2271 z, PyLong_SHIFT);
|
|
|
2272 }
|
|
|
2273
|
|
|
2274 /* add w back if q was too large (this branch taken rarely) */
|
|
|
2275 assert((sdigit)vtop + zhi == -1 || (sdigit)vtop + zhi == 0);
|
|
|
2276 if ((sdigit)vtop + zhi < 0) {
|
|
|
2277 carry = 0;
|
|
|
2278 for (i = 0; i < size_w; ++i) {
|
|
|
2279 carry += vk[i] + w0[i];
|
|
|
2280 vk[i] = carry & PyLong_MASK;
|
|
|
2281 carry >>= PyLong_SHIFT;
|
|
|
2282 }
|
|
|
2283 --q;
|
|
|
2284 }
|
|
|
2285
|
|
|
2286 /* store quotient digit */
|
|
|
2287 assert(q < PyLong_BASE);
|
|
|
2288 *--ak = q;
|
|
|
2289 }
|
|
|
2290
|
|
|
2291 /* unshift remainder; we reuse w to store the result */
|
|
|
2292 carry = v_rshift(w0, v0, size_w, d);
|
|
|
2293 assert(carry==0);
|
|
|
2294 Py_DECREF(v);
|
|
|
2295
|
|
|
2296 *prem = long_normalize(w);
|
|
|
2297 return long_normalize(a);
|
|
|
2298 }
|
|
|
2299
|
|
|
2300 /* For a nonzero PyLong a, express a in the form x * 2**e, with 0.5 <=
|
|
|
2301 abs(x) < 1.0 and e >= 0; return x and put e in *e. Here x is
|
|
|
2302 rounded to DBL_MANT_DIG significant bits using round-half-to-even.
|
|
|
2303 If a == 0, return 0.0 and set *e = 0. If the resulting exponent
|
|
|
2304 e is larger than PY_SSIZE_T_MAX, raise OverflowError and return
|
|
|
2305 -1.0. */
|
|
|
2306
|
|
|
2307 /* attempt to define 2.0**DBL_MANT_DIG as a compile-time constant */
|
|
|
2308 #if DBL_MANT_DIG == 53
|
|
|
2309 #define EXP2_DBL_MANT_DIG 9007199254740992.0
|
|
|
2310 #else
|
|
|
2311 #define EXP2_DBL_MANT_DIG (ldexp(1.0, DBL_MANT_DIG))
|
|
|
2312 #endif
|
|
|
2313
|
|
|
2314 double
|
|
|
2315 _PyLong_Frexp(PyLongObject *a, Py_ssize_t *e)
|
|
|
2316 {
|
|
|
2317 Py_ssize_t a_size, a_bits, shift_digits, shift_bits, x_size;
|
|
|
2318 /* See below for why x_digits is always large enough. */
|
|
|
2319 digit rem, x_digits[2 + (DBL_MANT_DIG + 1) / PyLong_SHIFT];
|
|
|
2320 double dx;
|
|
|
2321 /* Correction term for round-half-to-even rounding. For a digit x,
|
|
|
2322 "x + half_even_correction[x & 7]" gives x rounded to the nearest
|
|
|
2323 multiple of 4, rounding ties to a multiple of 8. */
|
|
|
2324 static const int half_even_correction[8] = {0, -1, -2, 1, 0, -1, 2, 1};
|
|
|
2325
|
|
|
2326 a_size = ABS(Py_SIZE(a));
|
|
|
2327 if (a_size == 0) {
|
|
|
2328 /* Special case for 0: significand 0.0, exponent 0. */
|
|
|
2329 *e = 0;
|
|
|
2330 return 0.0;
|
|
|
2331 }
|
|
|
2332 a_bits = bits_in_digit(a->ob_digit[a_size-1]);
|
|
|
2333 /* The following is an overflow-free version of the check
|
|
|
2334 "if ((a_size - 1) * PyLong_SHIFT + a_bits > PY_SSIZE_T_MAX) ..." */
|
|
|
2335 if (a_size >= (PY_SSIZE_T_MAX - 1) / PyLong_SHIFT + 1 &&
|
|
|
2336 (a_size > (PY_SSIZE_T_MAX - 1) / PyLong_SHIFT + 1 ||
|
|
|
2337 a_bits > (PY_SSIZE_T_MAX - 1) % PyLong_SHIFT + 1))
|
|
|
2338 goto overflow;
|
|
|
2339 a_bits = (a_size - 1) * PyLong_SHIFT + a_bits;
|
|
|
2340
|
|
|
2341 /* Shift the first DBL_MANT_DIG + 2 bits of a into x_digits[0:x_size]
|
|
|
2342 (shifting left if a_bits <= DBL_MANT_DIG + 2).
|
|
|
2343
|
|
|
2344 Number of digits needed for result: write // for floor division.
|
|
|
2345 Then if shifting left, we end up using
|
|
|
2346
|
|
|
2347 1 + a_size + (DBL_MANT_DIG + 2 - a_bits) // PyLong_SHIFT
|
|
|
2348
|
|
|
2349 digits. If shifting right, we use
|
|
|
2350
|
|
|
2351 a_size - (a_bits - DBL_MANT_DIG - 2) // PyLong_SHIFT
|
|
|
2352
|
|
|
2353 digits. Using a_size = 1 + (a_bits - 1) // PyLong_SHIFT along with
|
|
|
2354 the inequalities
|
|
|
2355
|
|
|
2356 m // PyLong_SHIFT + n // PyLong_SHIFT <= (m + n) // PyLong_SHIFT
|
|
|
2357 m // PyLong_SHIFT - n // PyLong_SHIFT <=
|
|
|
2358 1 + (m - n - 1) // PyLong_SHIFT,
|
|
|
2359
|
|
|
2360 valid for any integers m and n, we find that x_size satisfies
|
|
|
2361
|
|
|
2362 x_size <= 2 + (DBL_MANT_DIG + 1) // PyLong_SHIFT
|
|
|
2363
|
|
|
2364 in both cases.
|
|
|
2365 */
|
|
|
2366 if (a_bits <= DBL_MANT_DIG + 2) {
|
|
|
2367 shift_digits = (DBL_MANT_DIG + 2 - a_bits) / PyLong_SHIFT;
|
|
|
2368 shift_bits = (DBL_MANT_DIG + 2 - a_bits) % PyLong_SHIFT;
|
|
|
2369 x_size = 0;
|
|
|
2370 while (x_size < shift_digits)
|
|
|
2371 x_digits[x_size++] = 0;
|
|
|
2372 rem = v_lshift(x_digits + x_size, a->ob_digit, a_size,
|
|
|
2373 (int)shift_bits);
|
|
|
2374 x_size += a_size;
|
|
|
2375 x_digits[x_size++] = rem;
|
|
|
2376 }
|
|
|
2377 else {
|
|
|
2378 shift_digits = (a_bits - DBL_MANT_DIG - 2) / PyLong_SHIFT;
|
|
|
2379 shift_bits = (a_bits - DBL_MANT_DIG - 2) % PyLong_SHIFT;
|
|
|
2380 rem = v_rshift(x_digits, a->ob_digit + shift_digits,
|
|
|
2381 a_size - shift_digits, (int)shift_bits);
|
|
|
2382 x_size = a_size - shift_digits;
|
|
|
2383 /* For correct rounding below, we need the least significant
|
|
|
2384 bit of x to be 'sticky' for this shift: if any of the bits
|
|
|
2385 shifted out was nonzero, we set the least significant bit
|
|
|
2386 of x. */
|
|
|
2387 if (rem)
|
|
|
2388 x_digits[0] |= 1;
|
|
|
2389 else
|
|
|
2390 while (shift_digits > 0)
|
|
|
2391 if (a->ob_digit[--shift_digits]) {
|
|
|
2392 x_digits[0] |= 1;
|
|
|
2393 break;
|
|
|
2394 }
|
|
|
2395 }
|
|
|
2396 assert(1 <= x_size && x_size <= (Py_ssize_t)Py_ARRAY_LENGTH(x_digits));
|
|
|
2397
|
|
|
2398 /* Round, and convert to double. */
|
|
|
2399 x_digits[0] += half_even_correction[x_digits[0] & 7];
|
|
|
2400 dx = x_digits[--x_size];
|
|
|
2401 while (x_size > 0)
|
|
|
2402 dx = dx * PyLong_BASE + x_digits[--x_size];
|
|
|
2403
|
|
|
2404 /* Rescale; make correction if result is 1.0. */
|
|
|
2405 dx /= 4.0 * EXP2_DBL_MANT_DIG;
|
|
|
2406 if (dx == 1.0) {
|
|
|
2407 if (a_bits == PY_SSIZE_T_MAX)
|
|
|
2408 goto overflow;
|
|
|
2409 dx = 0.5;
|
|
|
2410 a_bits += 1;
|
|
|
2411 }
|
|
|
2412
|
|
|
2413 *e = a_bits;
|
|
|
2414 return Py_SIZE(a) < 0 ? -dx : dx;
|
|
|
2415
|
|
|
2416 overflow:
|
|
|
2417 /* exponent > PY_SSIZE_T_MAX */
|
|
|
2418 PyErr_SetString(PyExc_OverflowError,
|
|
|
2419 "huge integer: number of bits overflows a Py_ssize_t");
|
|
|
2420 *e = 0;
|
|
|
2421 return -1.0;
|
|
|
2422 }
|
|
|
2423
|
|
|
2424 /* Get a C double from a long int object. Rounds to the nearest double,
|
|
|
2425 using the round-half-to-even rule in the case of a tie. */
|
|
|
2426
|
|
|
2427 double
|
|
|
2428 PyLong_AsDouble(PyObject *v)
|
|
|
2429 {
|
|
|
2430 Py_ssize_t exponent;
|
|
|
2431 double x;
|
|
|
2432
|
|
|
2433 if (v == NULL) {
|
|
|
2434 PyErr_BadInternalCall();
|
|
|
2435 return -1.0;
|
|
|
2436 }
|
|
|
2437 if (!PyLong_Check(v)) {
|
|
|
2438 PyErr_SetString(PyExc_TypeError, "an integer is required");
|
|
|
2439 return -1.0;
|
|
|
2440 }
|
|
|
2441 x = _PyLong_Frexp((PyLongObject *)v, &exponent);
|
|
|
2442 if ((x == -1.0 && PyErr_Occurred()) || exponent > DBL_MAX_EXP) {
|
|
|
2443 PyErr_SetString(PyExc_OverflowError,
|
|
|
2444 "long int too large to convert to float");
|
|
|
2445 return -1.0;
|
|
|
2446 }
|
|
|
2447 return ldexp(x, (int)exponent);
|
|
|
2448 }
|
|
|
2449
|
|
|
2450 /* Methods */
|
|
|
2451
|
|
|
2452 static void
|
|
|
2453 long_dealloc(PyObject *v)
|
|
|
2454 {
|
|
|
2455 Py_TYPE(v)->tp_free(v);
|
|
|
2456 }
|
|
|
2457
|
|
|
2458 static int
|
|
|
2459 long_compare(PyLongObject *a, PyLongObject *b)
|
|
|
2460 {
|
|
|
2461 Py_ssize_t sign;
|
|
|
2462
|
|
|
2463 if (Py_SIZE(a) != Py_SIZE(b)) {
|
|
|
2464 sign = Py_SIZE(a) - Py_SIZE(b);
|
|
|
2465 }
|
|
|
2466 else {
|
|
|
2467 Py_ssize_t i = ABS(Py_SIZE(a));
|
|
|
2468 while (--i >= 0 && a->ob_digit[i] == b->ob_digit[i])
|
|
|
2469 ;
|
|
|
2470 if (i < 0)
|
|
|
2471 sign = 0;
|
|
|
2472 else {
|
|
|
2473 sign = (sdigit)a->ob_digit[i] - (sdigit)b->ob_digit[i];
|
|
|
2474 if (Py_SIZE(a) < 0)
|
|
|
2475 sign = -sign;
|
|
|
2476 }
|
|
|
2477 }
|
|
|
2478 return sign < 0 ? -1 : sign > 0 ? 1 : 0;
|
|
|
2479 }
|
|
|
2480
|
|
|
2481 #define TEST_COND(cond) \
|
|
|
2482 ((cond) ? Py_True : Py_False)
|
|
|
2483
|
|
|
2484 static PyObject *
|
|
|
2485 long_richcompare(PyObject *self, PyObject *other, int op)
|
|
|
2486 {
|
|
|
2487 int result;
|
|
|
2488 PyObject *v;
|
|
|
2489 CHECK_BINOP(self, other);
|
|
|
2490 if (self == other)
|
|
|
2491 result = 0;
|
|
|
2492 else
|
|
|
2493 result = long_compare((PyLongObject*)self, (PyLongObject*)other);
|
|
|
2494 /* Convert the return value to a Boolean */
|
|
|
2495 switch (op) {
|
|
|
2496 case Py_EQ:
|
|
|
2497 v = TEST_COND(result == 0);
|
|
|
2498 break;
|
|
|
2499 case Py_NE:
|
|
|
2500 v = TEST_COND(result != 0);
|
|
|
2501 break;
|
|
|
2502 case Py_LE:
|
|
|
2503 v = TEST_COND(result <= 0);
|
|
|
2504 break;
|
|
|
2505 case Py_GE:
|
|
|
2506 v = TEST_COND(result >= 0);
|
|
|
2507 break;
|
|
|
2508 case Py_LT:
|
|
|
2509 v = TEST_COND(result == -1);
|
|
|
2510 break;
|
|
|
2511 case Py_GT:
|
|
|
2512 v = TEST_COND(result == 1);
|
|
|
2513 break;
|
|
|
2514 default:
|
|
|
2515 PyErr_BadArgument();
|
|
|
2516 return NULL;
|
|
|
2517 }
|
|
|
2518 Py_INCREF(v);
|
|
|
2519 return v;
|
|
|
2520 }
|
|
|
2521
|
|
|
2522 static Py_hash_t
|
|
|
2523 long_hash(PyLongObject *v)
|
|
|
2524 {
|
|
|
2525 Py_uhash_t x;
|
|
|
2526 Py_ssize_t i;
|
|
|
2527 int sign;
|
|
|
2528
|
|
|
2529 i = Py_SIZE(v);
|
|
|
2530 switch(i) {
|
|
|
2531 case -1: return v->ob_digit[0]==1 ? -2 : -(sdigit)v->ob_digit[0];
|
|
|
2532 case 0: return 0;
|
|
|
2533 case 1: return v->ob_digit[0];
|
|
|
2534 }
|
|
|
2535 sign = 1;
|
|
|
2536 x = 0;
|
|
|
2537 if (i < 0) {
|
|
|
2538 sign = -1;
|
|
|
2539 i = -(i);
|
|
|
2540 }
|
|
|
2541 while (--i >= 0) {
|
|
|
2542 /* Here x is a quantity in the range [0, _PyHASH_MODULUS); we
|
|
|
2543 want to compute x * 2**PyLong_SHIFT + v->ob_digit[i] modulo
|
|
|
2544 _PyHASH_MODULUS.
|
|
|
2545
|
|
|
2546 The computation of x * 2**PyLong_SHIFT % _PyHASH_MODULUS
|
|
|
2547 amounts to a rotation of the bits of x. To see this, write
|
|
|
2548
|
|
|
2549 x * 2**PyLong_SHIFT = y * 2**_PyHASH_BITS + z
|
|
|
2550
|
|
|
2551 where y = x >> (_PyHASH_BITS - PyLong_SHIFT) gives the top
|
|
|
2552 PyLong_SHIFT bits of x (those that are shifted out of the
|
|
|
2553 original _PyHASH_BITS bits, and z = (x << PyLong_SHIFT) &
|
|
|
2554 _PyHASH_MODULUS gives the bottom _PyHASH_BITS - PyLong_SHIFT
|
|
|
2555 bits of x, shifted up. Then since 2**_PyHASH_BITS is
|
|
|
2556 congruent to 1 modulo _PyHASH_MODULUS, y*2**_PyHASH_BITS is
|
|
|
2557 congruent to y modulo _PyHASH_MODULUS. So
|
|
|
2558
|
|
|
2559 x * 2**PyLong_SHIFT = y + z (mod _PyHASH_MODULUS).
|
|
|
2560
|
|
|
2561 The right-hand side is just the result of rotating the
|
|
|
2562 _PyHASH_BITS bits of x left by PyLong_SHIFT places; since
|
|
|
2563 not all _PyHASH_BITS bits of x are 1s, the same is true
|
|
|
2564 after rotation, so 0 <= y+z < _PyHASH_MODULUS and y + z is
|
|
|
2565 the reduction of x*2**PyLong_SHIFT modulo
|
|
|
2566 _PyHASH_MODULUS. */
|
|
|
2567 x = ((x << PyLong_SHIFT) & _PyHASH_MODULUS) |
|
|
|
2568 (x >> (_PyHASH_BITS - PyLong_SHIFT));
|
|
|
2569 x += v->ob_digit[i];
|
|
|
2570 if (x >= _PyHASH_MODULUS)
|
|
|
2571 x -= _PyHASH_MODULUS;
|
|
|
2572 }
|
|
|
2573 x = x * sign;
|
|
|
2574 if (x == (Py_uhash_t)-1)
|
|
|
2575 x = (Py_uhash_t)-2;
|
|
|
2576 return (Py_hash_t)x;
|
|
|
2577 }
|
|
|
2578
|
|
|
2579
|
|
|
2580 /* Add the absolute values of two long integers. */
|
|
|
2581
|
|
|
2582 static PyLongObject *
|
|
|
2583 x_add(PyLongObject *a, PyLongObject *b)
|
|
|
2584 {
|
|
|
2585 Py_ssize_t size_a = ABS(Py_SIZE(a)), size_b = ABS(Py_SIZE(b));
|
|
|
2586 PyLongObject *z;
|
|
|
2587 Py_ssize_t i;
|
|
|
2588 digit carry = 0;
|
|
|
2589
|
|
|
2590 /* Ensure a is the larger of the two: */
|
|
|
2591 if (size_a < size_b) {
|
|
|
2592 { PyLongObject *temp = a; a = b; b = temp; }
|
|
|
2593 { Py_ssize_t size_temp = size_a;
|
|
|
2594 size_a = size_b;
|
|
|
2595 size_b = size_temp; }
|
|
|
2596 }
|
|
|
2597 z = _PyLong_New(size_a+1);
|
|
|
2598 if (z == NULL)
|
|
|
2599 return NULL;
|
|
|
2600 for (i = 0; i < size_b; ++i) {
|
|
|
2601 carry += a->ob_digit[i] + b->ob_digit[i];
|
|
|
2602 z->ob_digit[i] = carry & PyLong_MASK;
|
|
|
2603 carry >>= PyLong_SHIFT;
|
|
|
2604 }
|
|
|
2605 for (; i < size_a; ++i) {
|
|
|
2606 carry += a->ob_digit[i];
|
|
|
2607 z->ob_digit[i] = carry & PyLong_MASK;
|
|
|
2608 carry >>= PyLong_SHIFT;
|
|
|
2609 }
|
|
|
2610 z->ob_digit[i] = carry;
|
|
|
2611 return long_normalize(z);
|
|
|
2612 }
|
|
|
2613
|
|
|
2614 /* Subtract the absolute values of two integers. */
|
|
|
2615
|
|
|
2616 static PyLongObject *
|
|
|
2617 x_sub(PyLongObject *a, PyLongObject *b)
|
|
|
2618 {
|
|
|
2619 Py_ssize_t size_a = ABS(Py_SIZE(a)), size_b = ABS(Py_SIZE(b));
|
|
|
2620 PyLongObject *z;
|
|
|
2621 Py_ssize_t i;
|
|
|
2622 int sign = 1;
|
|
|
2623 digit borrow = 0;
|
|
|
2624
|
|
|
2625 /* Ensure a is the larger of the two: */
|
|
|
2626 if (size_a < size_b) {
|
|
|
2627 sign = -1;
|
|
|
2628 { PyLongObject *temp = a; a = b; b = temp; }
|
|
|
2629 { Py_ssize_t size_temp = size_a;
|
|
|
2630 size_a = size_b;
|
|
|
2631 size_b = size_temp; }
|
|
|
2632 }
|
|
|
2633 else if (size_a == size_b) {
|
|
|
2634 /* Find highest digit where a and b differ: */
|
|
|
2635 i = size_a;
|
|
|
2636 while (--i >= 0 && a->ob_digit[i] == b->ob_digit[i])
|
|
|
2637 ;
|
|
|
2638 if (i < 0)
|
|
|
2639 return (PyLongObject *)PyLong_FromLong(0);
|
|
|
2640 if (a->ob_digit[i] < b->ob_digit[i]) {
|
|
|
2641 sign = -1;
|
|
|
2642 { PyLongObject *temp = a; a = b; b = temp; }
|
|
|
2643 }
|
|
|
2644 size_a = size_b = i+1;
|
|
|
2645 }
|
|
|
2646 z = _PyLong_New(size_a);
|
|
|
2647 if (z == NULL)
|
|
|
2648 return NULL;
|
|
|
2649 for (i = 0; i < size_b; ++i) {
|
|
|
2650 /* The following assumes unsigned arithmetic
|
|
|
2651 works module 2**N for some N>PyLong_SHIFT. */
|
|
|
2652 borrow = a->ob_digit[i] - b->ob_digit[i] - borrow;
|
|
|
2653 z->ob_digit[i] = borrow & PyLong_MASK;
|
|
|
2654 borrow >>= PyLong_SHIFT;
|
|
|
2655 borrow &= 1; /* Keep only one sign bit */
|
|
|
2656 }
|
|
|
2657 for (; i < size_a; ++i) {
|
|
|
2658 borrow = a->ob_digit[i] - borrow;
|
|
|
2659 z->ob_digit[i] = borrow & PyLong_MASK;
|
|
|
2660 borrow >>= PyLong_SHIFT;
|
|
|
2661 borrow &= 1; /* Keep only one sign bit */
|
|
|
2662 }
|
|
|
2663 assert(borrow == 0);
|
|
|
2664 if (sign < 0)
|
|
|
2665 NEGATE(z);
|
|
|
2666 return long_normalize(z);
|
|
|
2667 }
|
|
|
2668
|
|
|
2669 static PyObject *
|
|
|
2670 long_add(PyLongObject *a, PyLongObject *b)
|
|
|
2671 {
|
|
|
2672 PyLongObject *z;
|
|
|
2673
|
|
|
2674 CHECK_BINOP(a, b);
|
|
|
2675
|
|
|
2676 if (ABS(Py_SIZE(a)) <= 1 && ABS(Py_SIZE(b)) <= 1) {
|
|
|
2677 PyObject *result = PyLong_FromLong(MEDIUM_VALUE(a) +
|
|
|
2678 MEDIUM_VALUE(b));
|
|
|
2679 return result;
|
|
|
2680 }
|
|
|
2681 if (Py_SIZE(a) < 0) {
|
|
|
2682 if (Py_SIZE(b) < 0) {
|
|
|
2683 z = x_add(a, b);
|
|
|
2684 if (z != NULL && Py_SIZE(z) != 0)
|
|
|
2685 Py_SIZE(z) = -(Py_SIZE(z));
|
|
|
2686 }
|
|
|
2687 else
|
|
|
2688 z = x_sub(b, a);
|
|
|
2689 }
|
|
|
2690 else {
|
|
|
2691 if (Py_SIZE(b) < 0)
|
|
|
2692 z = x_sub(a, b);
|
|
|
2693 else
|
|
|
2694 z = x_add(a, b);
|
|
|
2695 }
|
|
|
2696 return (PyObject *)z;
|
|
|
2697 }
|
|
|
2698
|
|
|
2699 static PyObject *
|
|
|
2700 long_sub(PyLongObject *a, PyLongObject *b)
|
|
|
2701 {
|
|
|
2702 PyLongObject *z;
|
|
|
2703
|
|
|
2704 CHECK_BINOP(a, b);
|
|
|
2705
|
|
|
2706 if (ABS(Py_SIZE(a)) <= 1 && ABS(Py_SIZE(b)) <= 1) {
|
|
|
2707 PyObject* r;
|
|
|
2708 r = PyLong_FromLong(MEDIUM_VALUE(a)-MEDIUM_VALUE(b));
|
|
|
2709 return r;
|
|
|
2710 }
|
|
|
2711 if (Py_SIZE(a) < 0) {
|
|
|
2712 if (Py_SIZE(b) < 0)
|
|
|
2713 z = x_sub(a, b);
|
|
|
2714 else
|
|
|
2715 z = x_add(a, b);
|
|
|
2716 if (z != NULL && Py_SIZE(z) != 0)
|
|
|
2717 Py_SIZE(z) = -(Py_SIZE(z));
|
|
|
2718 }
|
|
|
2719 else {
|
|
|
2720 if (Py_SIZE(b) < 0)
|
|
|
2721 z = x_add(a, b);
|
|
|
2722 else
|
|
|
2723 z = x_sub(a, b);
|
|
|
2724 }
|
|
|
2725 return (PyObject *)z;
|
|
|
2726 }
|
|
|
2727
|
|
|
2728 /* Grade school multiplication, ignoring the signs.
|
|
|
2729 * Returns the absolute value of the product, or NULL if error.
|
|
|
2730 */
|
|
|
2731 static PyLongObject *
|
|
|
2732 x_mul(PyLongObject *a, PyLongObject *b)
|
|
|
2733 {
|
|
|
2734 PyLongObject *z;
|
|
|
2735 Py_ssize_t size_a = ABS(Py_SIZE(a));
|
|
|
2736 Py_ssize_t size_b = ABS(Py_SIZE(b));
|
|
|
2737 Py_ssize_t i;
|
|
|
2738
|
|
|
2739 z = _PyLong_New(size_a + size_b);
|
|
|
2740 if (z == NULL)
|
|
|
2741 return NULL;
|
|
|
2742
|
|
|
2743 memset(z->ob_digit, 0, Py_SIZE(z) * sizeof(digit));
|
|
|
2744 if (a == b) {
|
|
|
2745 /* Efficient squaring per HAC, Algorithm 14.16:
|
|
|
2746 * http://www.cacr.math.uwaterloo.ca/hac/about/chap14.pdf
|
|
|
2747 * Gives slightly less than a 2x speedup when a == b,
|
|
|
2748 * via exploiting that each entry in the multiplication
|
|
|
2749 * pyramid appears twice (except for the size_a squares).
|
|
|
2750 */
|
|
|
2751 for (i = 0; i < size_a; ++i) {
|
|
|
2752 twodigits carry;
|
|
|
2753 twodigits f = a->ob_digit[i];
|
|
|
2754 digit *pz = z->ob_digit + (i << 1);
|
|
|
2755 digit *pa = a->ob_digit + i + 1;
|
|
|
2756 digit *paend = a->ob_digit + size_a;
|
|
|
2757
|
|
|
2758 SIGCHECK({
|
|
|
2759 Py_DECREF(z);
|
|
|
2760 return NULL;
|
|
|
2761 });
|
|
|
2762
|
|
|
2763 carry = *pz + f * f;
|
|
|
2764 *pz++ = (digit)(carry & PyLong_MASK);
|
|
|
2765 carry >>= PyLong_SHIFT;
|
|
|
2766 assert(carry <= PyLong_MASK);
|
|
|
2767
|
|
|
2768 /* Now f is added in twice in each column of the
|
|
|
2769 * pyramid it appears. Same as adding f<<1 once.
|
|
|
2770 */
|
|
|
2771 f <<= 1;
|
|
|
2772 while (pa < paend) {
|
|
|
2773 carry += *pz + *pa++ * f;
|
|
|
2774 *pz++ = (digit)(carry & PyLong_MASK);
|
|
|
2775 carry >>= PyLong_SHIFT;
|
|
|
2776 assert(carry <= (PyLong_MASK << 1));
|
|
|
2777 }
|
|
|
2778 if (carry) {
|
|
|
2779 carry += *pz;
|
|
|
2780 *pz++ = (digit)(carry & PyLong_MASK);
|
|
|
2781 carry >>= PyLong_SHIFT;
|
|
|
2782 }
|
|
|
2783 if (carry)
|
|
|
2784 *pz += (digit)(carry & PyLong_MASK);
|
|
|
2785 assert((carry >> PyLong_SHIFT) == 0);
|
|
|
2786 }
|
|
|
2787 }
|
|
|
2788 else { /* a is not the same as b -- gradeschool long mult */
|
|
|
2789 for (i = 0; i < size_a; ++i) {
|
|
|
2790 twodigits carry = 0;
|
|
|
2791 twodigits f = a->ob_digit[i];
|
|
|
2792 digit *pz = z->ob_digit + i;
|
|
|
2793 digit *pb = b->ob_digit;
|
|
|
2794 digit *pbend = b->ob_digit + size_b;
|
|
|
2795
|
|
|
2796 SIGCHECK({
|
|
|
2797 Py_DECREF(z);
|
|
|
2798 return NULL;
|
|
|
2799 });
|
|
|
2800
|
|
|
2801 while (pb < pbend) {
|
|
|
2802 carry += *pz + *pb++ * f;
|
|
|
2803 *pz++ = (digit)(carry & PyLong_MASK);
|
|
|
2804 carry >>= PyLong_SHIFT;
|
|
|
2805 assert(carry <= PyLong_MASK);
|
|
|
2806 }
|
|
|
2807 if (carry)
|
|
|
2808 *pz += (digit)(carry & PyLong_MASK);
|
|
|
2809 assert((carry >> PyLong_SHIFT) == 0);
|
|
|
2810 }
|
|
|
2811 }
|
|
|
2812 return long_normalize(z);
|
|
|
2813 }
|
|
|
2814
|
|
|
2815 /* A helper for Karatsuba multiplication (k_mul).
|
|
|
2816 Takes a long "n" and an integer "size" representing the place to
|
|
|
2817 split, and sets low and high such that abs(n) == (high << size) + low,
|
|
|
2818 viewing the shift as being by digits. The sign bit is ignored, and
|
|
|
2819 the return values are >= 0.
|
|
|
2820 Returns 0 on success, -1 on failure.
|
|
|
2821 */
|
|
|
2822 static int
|
|
|
2823 kmul_split(PyLongObject *n,
|
|
|
2824 Py_ssize_t size,
|
|
|
2825 PyLongObject **high,
|
|
|
2826 PyLongObject **low)
|
|
|
2827 {
|
|
|
2828 PyLongObject *hi, *lo;
|
|
|
2829 Py_ssize_t size_lo, size_hi;
|
|
|
2830 const Py_ssize_t size_n = ABS(Py_SIZE(n));
|
|
|
2831
|
|
|
2832 size_lo = MIN(size_n, size);
|
|
|
2833 size_hi = size_n - size_lo;
|
|
|
2834
|
|
|
2835 if ((hi = _PyLong_New(size_hi)) == NULL)
|
|
|
2836 return -1;
|
|
|
2837 if ((lo = _PyLong_New(size_lo)) == NULL) {
|
|
|
2838 Py_DECREF(hi);
|
|
|
2839 return -1;
|
|
|
2840 }
|
|
|
2841
|
|
|
2842 memcpy(lo->ob_digit, n->ob_digit, size_lo * sizeof(digit));
|
|
|
2843 memcpy(hi->ob_digit, n->ob_digit + size_lo, size_hi * sizeof(digit));
|
|
|
2844
|
|
|
2845 *high = long_normalize(hi);
|
|
|
2846 *low = long_normalize(lo);
|
|
|
2847 return 0;
|
|
|
2848 }
|
|
|
2849
|
|
|
2850 static PyLongObject *k_lopsided_mul(PyLongObject *a, PyLongObject *b);
|
|
|
2851
|
|
|
2852 /* Karatsuba multiplication. Ignores the input signs, and returns the
|
|
|
2853 * absolute value of the product (or NULL if error).
|
|
|
2854 * See Knuth Vol. 2 Chapter 4.3.3 (Pp. 294-295).
|
|
|
2855 */
|
|
|
2856 static PyLongObject *
|
|
|
2857 k_mul(PyLongObject *a, PyLongObject *b)
|
|
|
2858 {
|
|
|
2859 Py_ssize_t asize = ABS(Py_SIZE(a));
|
|
|
2860 Py_ssize_t bsize = ABS(Py_SIZE(b));
|
|
|
2861 PyLongObject *ah = NULL;
|
|
|
2862 PyLongObject *al = NULL;
|
|
|
2863 PyLongObject *bh = NULL;
|
|
|
2864 PyLongObject *bl = NULL;
|
|
|
2865 PyLongObject *ret = NULL;
|
|
|
2866 PyLongObject *t1, *t2, *t3;
|
|
|
2867 Py_ssize_t shift; /* the number of digits we split off */
|
|
|
2868 Py_ssize_t i;
|
|
|
2869
|
|
|
2870 /* (ah*X+al)(bh*X+bl) = ah*bh*X*X + (ah*bl + al*bh)*X + al*bl
|
|
|
2871 * Let k = (ah+al)*(bh+bl) = ah*bl + al*bh + ah*bh + al*bl
|
|
|
2872 * Then the original product is
|
|
|
2873 * ah*bh*X*X + (k - ah*bh - al*bl)*X + al*bl
|
|
|
2874 * By picking X to be a power of 2, "*X" is just shifting, and it's
|
|
|
2875 * been reduced to 3 multiplies on numbers half the size.
|
|
|
2876 */
|
|
|
2877
|
|
|
2878 /* We want to split based on the larger number; fiddle so that b
|
|
|
2879 * is largest.
|
|
|
2880 */
|
|
|
2881 if (asize > bsize) {
|
|
|
2882 t1 = a;
|
|
|
2883 a = b;
|
|
|
2884 b = t1;
|
|
|
2885
|
|
|
2886 i = asize;
|
|
|
2887 asize = bsize;
|
|
|
2888 bsize = i;
|
|
|
2889 }
|
|
|
2890
|
|
|
2891 /* Use gradeschool math when either number is too small. */
|
|
|
2892 i = a == b ? KARATSUBA_SQUARE_CUTOFF : KARATSUBA_CUTOFF;
|
|
|
2893 if (asize <= i) {
|
|
|
2894 if (asize == 0)
|
|
|
2895 return (PyLongObject *)PyLong_FromLong(0);
|
|
|
2896 else
|
|
|
2897 return x_mul(a, b);
|
|
|
2898 }
|
|
|
2899
|
|
|
2900 /* If a is small compared to b, splitting on b gives a degenerate
|
|
|
2901 * case with ah==0, and Karatsuba may be (even much) less efficient
|
|
|
2902 * than "grade school" then. However, we can still win, by viewing
|
|
|
2903 * b as a string of "big digits", each of width a->ob_size. That
|
|
|
2904 * leads to a sequence of balanced calls to k_mul.
|
|
|
2905 */
|
|
|
2906 if (2 * asize <= bsize)
|
|
|
2907 return k_lopsided_mul(a, b);
|
|
|
2908
|
|
|
2909 /* Split a & b into hi & lo pieces. */
|
|
|
2910 shift = bsize >> 1;
|
|
|
2911 if (kmul_split(a, shift, &ah, &al) < 0) goto fail;
|
|
|
2912 assert(Py_SIZE(ah) > 0); /* the split isn't degenerate */
|
|
|
2913
|
|
|
2914 if (a == b) {
|
|
|
2915 bh = ah;
|
|
|
2916 bl = al;
|
|
|
2917 Py_INCREF(bh);
|
|
|
2918 Py_INCREF(bl);
|
|
|
2919 }
|
|
|
2920 else if (kmul_split(b, shift, &bh, &bl) < 0) goto fail;
|
|
|
2921
|
|
|
2922 /* The plan:
|
|
|
2923 * 1. Allocate result space (asize + bsize digits: that's always
|
|
|
2924 * enough).
|
|
|
2925 * 2. Compute ah*bh, and copy into result at 2*shift.
|
|
|
2926 * 3. Compute al*bl, and copy into result at 0. Note that this
|
|
|
2927 * can't overlap with #2.
|
|
|
2928 * 4. Subtract al*bl from the result, starting at shift. This may
|
|
|
2929 * underflow (borrow out of the high digit), but we don't care:
|
|
|
2930 * we're effectively doing unsigned arithmetic mod
|
|
|
2931 * BASE**(sizea + sizeb), and so long as the *final* result fits,
|
|
|
2932 * borrows and carries out of the high digit can be ignored.
|
|
|
2933 * 5. Subtract ah*bh from the result, starting at shift.
|
|
|
2934 * 6. Compute (ah+al)*(bh+bl), and add it into the result starting
|
|
|
2935 * at shift.
|
|
|
2936 */
|
|
|
2937
|
|
|
2938 /* 1. Allocate result space. */
|
|
|
2939 ret = _PyLong_New(asize + bsize);
|
|
|
2940 if (ret == NULL) goto fail;
|
|
|
2941 #ifdef Py_DEBUG
|
|
|
2942 /* Fill with trash, to catch reference to uninitialized digits. */
|
|
|
2943 memset(ret->ob_digit, 0xDF, Py_SIZE(ret) * sizeof(digit));
|
|
|
2944 #endif
|
|
|
2945
|
|
|
2946 /* 2. t1 <- ah*bh, and copy into high digits of result. */
|
|
|
2947 if ((t1 = k_mul(ah, bh)) == NULL) goto fail;
|
|
|
2948 assert(Py_SIZE(t1) >= 0);
|
|
|
2949 assert(2*shift + Py_SIZE(t1) <= Py_SIZE(ret));
|
|
|
2950 memcpy(ret->ob_digit + 2*shift, t1->ob_digit,
|
|
|
2951 Py_SIZE(t1) * sizeof(digit));
|
|
|
2952
|
|
|
2953 /* Zero-out the digits higher than the ah*bh copy. */
|
|
|
2954 i = Py_SIZE(ret) - 2*shift - Py_SIZE(t1);
|
|
|
2955 if (i)
|
|
|
2956 memset(ret->ob_digit + 2*shift + Py_SIZE(t1), 0,
|
|
|
2957 i * sizeof(digit));
|
|
|
2958
|
|
|
2959 /* 3. t2 <- al*bl, and copy into the low digits. */
|
|
|
2960 if ((t2 = k_mul(al, bl)) == NULL) {
|
|
|
2961 Py_DECREF(t1);
|
|
|
2962 goto fail;
|
|
|
2963 }
|
|
|
2964 assert(Py_SIZE(t2) >= 0);
|
|
|
2965 assert(Py_SIZE(t2) <= 2*shift); /* no overlap with high digits */
|
|
|
2966 memcpy(ret->ob_digit, t2->ob_digit, Py_SIZE(t2) * sizeof(digit));
|
|
|
2967
|
|
|
2968 /* Zero out remaining digits. */
|
|
|
2969 i = 2*shift - Py_SIZE(t2); /* number of uninitialized digits */
|
|
|
2970 if (i)
|
|
|
2971 memset(ret->ob_digit + Py_SIZE(t2), 0, i * sizeof(digit));
|
|
|
2972
|
|
|
2973 /* 4 & 5. Subtract ah*bh (t1) and al*bl (t2). We do al*bl first
|
|
|
2974 * because it's fresher in cache.
|
|
|
2975 */
|
|
|
2976 i = Py_SIZE(ret) - shift; /* # digits after shift */
|
|
|
2977 (void)v_isub(ret->ob_digit + shift, i, t2->ob_digit, Py_SIZE(t2));
|
|
|
2978 Py_DECREF(t2);
|
|
|
2979
|
|
|
2980 (void)v_isub(ret->ob_digit + shift, i, t1->ob_digit, Py_SIZE(t1));
|
|
|
2981 Py_DECREF(t1);
|
|
|
2982
|
|
|
2983 /* 6. t3 <- (ah+al)(bh+bl), and add into result. */
|
|
|
2984 if ((t1 = x_add(ah, al)) == NULL) goto fail;
|
|
|
2985 Py_DECREF(ah);
|
|
|
2986 Py_DECREF(al);
|
|
|
2987 ah = al = NULL;
|
|
|
2988
|
|
|
2989 if (a == b) {
|
|
|
2990 t2 = t1;
|
|
|
2991 Py_INCREF(t2);
|
|
|
2992 }
|
|
|
2993 else if ((t2 = x_add(bh, bl)) == NULL) {
|
|
|
2994 Py_DECREF(t1);
|
|
|
2995 goto fail;
|
|
|
2996 }
|
|
|
2997 Py_DECREF(bh);
|
|
|
2998 Py_DECREF(bl);
|
|
|
2999 bh = bl = NULL;
|
|
|
3000
|
|
|
3001 t3 = k_mul(t1, t2);
|
|
|
3002 Py_DECREF(t1);
|
|
|
3003 Py_DECREF(t2);
|
|
|
3004 if (t3 == NULL) goto fail;
|
|
|
3005 assert(Py_SIZE(t3) >= 0);
|
|
|
3006
|
|
|
3007 /* Add t3. It's not obvious why we can't run out of room here.
|
|
|
3008 * See the (*) comment after this function.
|
|
|
3009 */
|
|
|
3010 (void)v_iadd(ret->ob_digit + shift, i, t3->ob_digit, Py_SIZE(t3));
|
|
|
3011 Py_DECREF(t3);
|
|
|
3012
|
|
|
3013 return long_normalize(ret);
|
|
|
3014
|
|
|
3015 fail:
|
|
|
3016 Py_XDECREF(ret);
|
|
|
3017 Py_XDECREF(ah);
|
|
|
3018 Py_XDECREF(al);
|
|
|
3019 Py_XDECREF(bh);
|
|
|
3020 Py_XDECREF(bl);
|
|
|
3021 return NULL;
|
|
|
3022 }
|
|
|
3023
|
|
|
3024 /* (*) Why adding t3 can't "run out of room" above.
|
|
|
3025
|
|
|
3026 Let f(x) mean the floor of x and c(x) mean the ceiling of x. Some facts
|
|
|
3027 to start with:
|
|
|
3028
|
|
|
3029 1. For any integer i, i = c(i/2) + f(i/2). In particular,
|
|
|
3030 bsize = c(bsize/2) + f(bsize/2).
|
|
|
3031 2. shift = f(bsize/2)
|
|
|
3032 3. asize <= bsize
|
|
|
3033 4. Since we call k_lopsided_mul if asize*2 <= bsize, asize*2 > bsize in this
|
|
|
3034 routine, so asize > bsize/2 >= f(bsize/2) in this routine.
|
|
|
3035
|
|
|
3036 We allocated asize + bsize result digits, and add t3 into them at an offset
|
|
|
3037 of shift. This leaves asize+bsize-shift allocated digit positions for t3
|
|
|
3038 to fit into, = (by #1 and #2) asize + f(bsize/2) + c(bsize/2) - f(bsize/2) =
|
|
|
3039 asize + c(bsize/2) available digit positions.
|
|
|
3040
|
|
|
3041 bh has c(bsize/2) digits, and bl at most f(size/2) digits. So bh+hl has
|
|
|
3042 at most c(bsize/2) digits + 1 bit.
|
|
|
3043
|
|
|
3044 If asize == bsize, ah has c(bsize/2) digits, else ah has at most f(bsize/2)
|
|
|
3045 digits, and al has at most f(bsize/2) digits in any case. So ah+al has at
|
|
|
3046 most (asize == bsize ? c(bsize/2) : f(bsize/2)) digits + 1 bit.
|
|
|
3047
|
|
|
3048 The product (ah+al)*(bh+bl) therefore has at most
|
|
|
3049
|
|
|
3050 c(bsize/2) + (asize == bsize ? c(bsize/2) : f(bsize/2)) digits + 2 bits
|
|
|
3051
|
|
|
3052 and we have asize + c(bsize/2) available digit positions. We need to show
|
|
|
3053 this is always enough. An instance of c(bsize/2) cancels out in both, so
|
|
|
3054 the question reduces to whether asize digits is enough to hold
|
|
|
3055 (asize == bsize ? c(bsize/2) : f(bsize/2)) digits + 2 bits. If asize < bsize,
|
|
|
3056 then we're asking whether asize digits >= f(bsize/2) digits + 2 bits. By #4,
|
|
|
3057 asize is at least f(bsize/2)+1 digits, so this in turn reduces to whether 1
|
|
|
3058 digit is enough to hold 2 bits. This is so since PyLong_SHIFT=15 >= 2. If
|
|
|
3059 asize == bsize, then we're asking whether bsize digits is enough to hold
|
|
|
3060 c(bsize/2) digits + 2 bits, or equivalently (by #1) whether f(bsize/2) digits
|
|
|
3061 is enough to hold 2 bits. This is so if bsize >= 2, which holds because
|
|
|
3062 bsize >= KARATSUBA_CUTOFF >= 2.
|
|
|
3063
|
|
|
3064 Note that since there's always enough room for (ah+al)*(bh+bl), and that's
|
|
|
3065 clearly >= each of ah*bh and al*bl, there's always enough room to subtract
|
|
|
3066 ah*bh and al*bl too.
|
|
|
3067 */
|
|
|
3068
|
|
|
3069 /* b has at least twice the digits of a, and a is big enough that Karatsuba
|
|
|
3070 * would pay off *if* the inputs had balanced sizes. View b as a sequence
|
|
|
3071 * of slices, each with a->ob_size digits, and multiply the slices by a,
|
|
|
3072 * one at a time. This gives k_mul balanced inputs to work with, and is
|
|
|
3073 * also cache-friendly (we compute one double-width slice of the result
|
|
|
3074 * at a time, then move on, never backtracking except for the helpful
|
|
|
3075 * single-width slice overlap between successive partial sums).
|
|
|
3076 */
|
|
|
3077 static PyLongObject *
|
|
|
3078 k_lopsided_mul(PyLongObject *a, PyLongObject *b)
|
|
|
3079 {
|
|
|
3080 const Py_ssize_t asize = ABS(Py_SIZE(a));
|
|
|
3081 Py_ssize_t bsize = ABS(Py_SIZE(b));
|
|
|
3082 Py_ssize_t nbdone; /* # of b digits already multiplied */
|
|
|
3083 PyLongObject *ret;
|
|
|
3084 PyLongObject *bslice = NULL;
|
|
|
3085
|
|
|
3086 assert(asize > KARATSUBA_CUTOFF);
|
|
|
3087 assert(2 * asize <= bsize);
|
|
|
3088
|
|
|
3089 /* Allocate result space, and zero it out. */
|
|
|
3090 ret = _PyLong_New(asize + bsize);
|
|
|
3091 if (ret == NULL)
|
|
|
3092 return NULL;
|
|
|
3093 memset(ret->ob_digit, 0, Py_SIZE(ret) * sizeof(digit));
|
|
|
3094
|
|
|
3095 /* Successive slices of b are copied into bslice. */
|
|
|
3096 bslice = _PyLong_New(asize);
|
|
|
3097 if (bslice == NULL)
|
|
|
3098 goto fail;
|
|
|
3099
|
|
|
3100 nbdone = 0;
|
|
|
3101 while (bsize > 0) {
|
|
|
3102 PyLongObject *product;
|
|
|
3103 const Py_ssize_t nbtouse = MIN(bsize, asize);
|
|
|
3104
|
|
|
3105 /* Multiply the next slice of b by a. */
|
|
|
3106 memcpy(bslice->ob_digit, b->ob_digit + nbdone,
|
|
|
3107 nbtouse * sizeof(digit));
|
|
|
3108 Py_SIZE(bslice) = nbtouse;
|
|
|
3109 product = k_mul(a, bslice);
|
|
|
3110 if (product == NULL)
|
|
|
3111 goto fail;
|
|
|
3112
|
|
|
3113 /* Add into result. */
|
|
|
3114 (void)v_iadd(ret->ob_digit + nbdone, Py_SIZE(ret) - nbdone,
|
|
|
3115 product->ob_digit, Py_SIZE(product));
|
|
|
3116 Py_DECREF(product);
|
|
|
3117
|
|
|
3118 bsize -= nbtouse;
|
|
|
3119 nbdone += nbtouse;
|
|
|
3120 }
|
|
|
3121
|
|
|
3122 Py_DECREF(bslice);
|
|
|
3123 return long_normalize(ret);
|
|
|
3124
|
|
|
3125 fail:
|
|
|
3126 Py_DECREF(ret);
|
|
|
3127 Py_XDECREF(bslice);
|
|
|
3128 return NULL;
|
|
|
3129 }
|
|
|
3130
|
|
|
3131 static PyObject *
|
|
|
3132 long_mul(PyLongObject *a, PyLongObject *b)
|
|
|
3133 {
|
|
|
3134 PyLongObject *z;
|
|
|
3135
|
|
|
3136 CHECK_BINOP(a, b);
|
|
|
3137
|
|
|
3138 /* fast path for single-digit multiplication */
|
|
|
3139 if (ABS(Py_SIZE(a)) <= 1 && ABS(Py_SIZE(b)) <= 1) {
|
|
|
3140 stwodigits v = (stwodigits)(MEDIUM_VALUE(a)) * MEDIUM_VALUE(b);
|
|
|
3141 #ifdef HAVE_LONG_LONG
|
|
|
3142 return PyLong_FromLongLong((PY_LONG_LONG)v);
|
|
|
3143 #else
|
|
|
3144 /* if we don't have long long then we're almost certainly
|
|
|
3145 using 15-bit digits, so v will fit in a long. In the
|
|
|
3146 unlikely event that we're using 30-bit digits on a platform
|
|
|
3147 without long long, a large v will just cause us to fall
|
|
|
3148 through to the general multiplication code below. */
|
|
|
3149 if (v >= LONG_MIN && v <= LONG_MAX)
|
|
|
3150 return PyLong_FromLong((long)v);
|
|
|
3151 #endif
|
|
|
3152 }
|
|
|
3153
|
|
|
3154 z = k_mul(a, b);
|
|
|
3155 /* Negate if exactly one of the inputs is negative. */
|
|
|
3156 if (((Py_SIZE(a) ^ Py_SIZE(b)) < 0) && z)
|
|
|
3157 NEGATE(z);
|
|
|
3158 return (PyObject *)z;
|
|
|
3159 }
|
|
|
3160
|
|
|
3161 /* The / and % operators are now defined in terms of divmod().
|
|
|
3162 The expression a mod b has the value a - b*floor(a/b).
|
|
|
3163 The long_divrem function gives the remainder after division of
|
|
|
3164 |a| by |b|, with the sign of a. This is also expressed
|
|
|
3165 as a - b*trunc(a/b), if trunc truncates towards zero.
|
|
|
3166 Some examples:
|
|
|
3167 a b a rem b a mod b
|
|
|
3168 13 10 3 3
|
|
|
3169 -13 10 -3 7
|
|
|
3170 13 -10 3 -7
|
|
|
3171 -13 -10 -3 -3
|
|
|
3172 So, to get from rem to mod, we have to add b if a and b
|
|
|
3173 have different signs. We then subtract one from the 'div'
|
|
|
3174 part of the outcome to keep the invariant intact. */
|
|
|
3175
|
|
|
3176 /* Compute
|
|
|
3177 * *pdiv, *pmod = divmod(v, w)
|
|
|
3178 * NULL can be passed for pdiv or pmod, in which case that part of
|
|
|
3179 * the result is simply thrown away. The caller owns a reference to
|
|
|
3180 * each of these it requests (does not pass NULL for).
|
|
|
3181 */
|
|
|
3182 static int
|
|
|
3183 l_divmod(PyLongObject *v, PyLongObject *w,
|
|
|
3184 PyLongObject **pdiv, PyLongObject **pmod)
|
|
|
3185 {
|
|
|
3186 PyLongObject *div, *mod;
|
|
|
3187
|
|
|
3188 if (long_divrem(v, w, &div, &mod) < 0)
|
|
|
3189 return -1;
|
|
|
3190 if ((Py_SIZE(mod) < 0 && Py_SIZE(w) > 0) ||
|
|
|
3191 (Py_SIZE(mod) > 0 && Py_SIZE(w) < 0)) {
|
|
|
3192 PyLongObject *temp;
|
|
|
3193 PyLongObject *one;
|
|
|
3194 temp = (PyLongObject *) long_add(mod, w);
|
|
|
3195 Py_DECREF(mod);
|
|
|
3196 mod = temp;
|
|
|
3197 if (mod == NULL) {
|
|
|
3198 Py_DECREF(div);
|
|
|
3199 return -1;
|
|
|
3200 }
|
|
|
3201 one = (PyLongObject *) PyLong_FromLong(1L);
|
|
|
3202 if (one == NULL ||
|
|
|
3203 (temp = (PyLongObject *) long_sub(div, one)) == NULL) {
|
|
|
3204 Py_DECREF(mod);
|
|
|
3205 Py_DECREF(div);
|
|
|
3206 Py_XDECREF(one);
|
|
|
3207 return -1;
|
|
|
3208 }
|
|
|
3209 Py_DECREF(one);
|
|
|
3210 Py_DECREF(div);
|
|
|
3211 div = temp;
|
|
|
3212 }
|
|
|
3213 if (pdiv != NULL)
|
|
|
3214 *pdiv = div;
|
|
|
3215 else
|
|
|
3216 Py_DECREF(div);
|
|
|
3217
|
|
|
3218 if (pmod != NULL)
|
|
|
3219 *pmod = mod;
|
|
|
3220 else
|
|
|
3221 Py_DECREF(mod);
|
|
|
3222
|
|
|
3223 return 0;
|
|
|
3224 }
|
|
|
3225
|
|
|
3226 static PyObject *
|
|
|
3227 long_div(PyObject *a, PyObject *b)
|
|
|
3228 {
|
|
|
3229 PyLongObject *div;
|
|
|
3230
|
|
|
3231 CHECK_BINOP(a, b);
|
|
|
3232 if (l_divmod((PyLongObject*)a, (PyLongObject*)b, &div, NULL) < 0)
|
|
|
3233 div = NULL;
|
|
|
3234 return (PyObject *)div;
|
|
|
3235 }
|
|
|
3236
|
|
|
3237 /* PyLong/PyLong -> float, with correctly rounded result. */
|
|
|
3238
|
|
|
3239 #define MANT_DIG_DIGITS (DBL_MANT_DIG / PyLong_SHIFT)
|
|
|
3240 #define MANT_DIG_BITS (DBL_MANT_DIG % PyLong_SHIFT)
|
|
|
3241
|
|
|
3242 static PyObject *
|
|
|
3243 long_true_divide(PyObject *v, PyObject *w)
|
|
|
3244 {
|
|
|
3245 PyLongObject *a, *b, *x;
|
|
|
3246 Py_ssize_t a_size, b_size, shift, extra_bits, diff, x_size, x_bits;
|
|
|
3247 digit mask, low;
|
|
|
3248 int inexact, negate, a_is_small, b_is_small;
|
|
|
3249 double dx, result;
|
|
|
3250
|
|
|
3251 CHECK_BINOP(v, w);
|
|
|
3252 a = (PyLongObject *)v;
|
|
|
3253 b = (PyLongObject *)w;
|
|
|
3254
|
|
|
3255 /*
|
|
|
3256 Method in a nutshell:
|
|
|
3257
|
|
|
3258 0. reduce to case a, b > 0; filter out obvious underflow/overflow
|
|
|
3259 1. choose a suitable integer 'shift'
|
|
|
3260 2. use integer arithmetic to compute x = floor(2**-shift*a/b)
|
|
|
3261 3. adjust x for correct rounding
|
|
|
3262 4. convert x to a double dx with the same value
|
|
|
3263 5. return ldexp(dx, shift).
|
|
|
3264
|
|
|
3265 In more detail:
|
|
|
3266
|
|
|
3267 0. For any a, a/0 raises ZeroDivisionError; for nonzero b, 0/b
|
|
|
3268 returns either 0.0 or -0.0, depending on the sign of b. For a and
|
|
|
3269 b both nonzero, ignore signs of a and b, and add the sign back in
|
|
|
3270 at the end. Now write a_bits and b_bits for the bit lengths of a
|
|
|
3271 and b respectively (that is, a_bits = 1 + floor(log_2(a)); likewise
|
|
|
3272 for b). Then
|
|
|
3273
|
|
|
3274 2**(a_bits - b_bits - 1) < a/b < 2**(a_bits - b_bits + 1).
|
|
|
3275
|
|
|
3276 So if a_bits - b_bits > DBL_MAX_EXP then a/b > 2**DBL_MAX_EXP and
|
|
|
3277 so overflows. Similarly, if a_bits - b_bits < DBL_MIN_EXP -
|
|
|
3278 DBL_MANT_DIG - 1 then a/b underflows to 0. With these cases out of
|
|
|
3279 the way, we can assume that
|
|
|
3280
|
|
|
3281 DBL_MIN_EXP - DBL_MANT_DIG - 1 <= a_bits - b_bits <= DBL_MAX_EXP.
|
|
|
3282
|
|
|
3283 1. The integer 'shift' is chosen so that x has the right number of
|
|
|
3284 bits for a double, plus two or three extra bits that will be used
|
|
|
3285 in the rounding decisions. Writing a_bits and b_bits for the
|
|
|
3286 number of significant bits in a and b respectively, a
|
|
|
3287 straightforward formula for shift is:
|
|
|
3288
|
|
|
3289 shift = a_bits - b_bits - DBL_MANT_DIG - 2
|
|
|
3290
|
|
|
3291 This is fine in the usual case, but if a/b is smaller than the
|
|
|
3292 smallest normal float then it can lead to double rounding on an
|
|
|
3293 IEEE 754 platform, giving incorrectly rounded results. So we
|
|
|
3294 adjust the formula slightly. The actual formula used is:
|
|
|
3295
|
|
|
3296 shift = MAX(a_bits - b_bits, DBL_MIN_EXP) - DBL_MANT_DIG - 2
|
|
|
3297
|
|
|
3298 2. The quantity x is computed by first shifting a (left -shift bits
|
|
|
3299 if shift <= 0, right shift bits if shift > 0) and then dividing by
|
|
|
3300 b. For both the shift and the division, we keep track of whether
|
|
|
3301 the result is inexact, in a flag 'inexact'; this information is
|
|
|
3302 needed at the rounding stage.
|
|
|
3303
|
|
|
3304 With the choice of shift above, together with our assumption that
|
|
|
3305 a_bits - b_bits >= DBL_MIN_EXP - DBL_MANT_DIG - 1, it follows
|
|
|
3306 that x >= 1.
|
|
|
3307
|
|
|
3308 3. Now x * 2**shift <= a/b < (x+1) * 2**shift. We want to replace
|
|
|
3309 this with an exactly representable float of the form
|
|
|
3310
|
|
|
3311 round(x/2**extra_bits) * 2**(extra_bits+shift).
|
|
|
3312
|
|
|
3313 For float representability, we need x/2**extra_bits <
|
|
|
3314 2**DBL_MANT_DIG and extra_bits + shift >= DBL_MIN_EXP -
|
|
|
3315 DBL_MANT_DIG. This translates to the condition:
|
|
|
3316
|
|
|
3317 extra_bits >= MAX(x_bits, DBL_MIN_EXP - shift) - DBL_MANT_DIG
|
|
|
3318
|
|
|
3319 To round, we just modify the bottom digit of x in-place; this can
|
|
|
3320 end up giving a digit with value > PyLONG_MASK, but that's not a
|
|
|
3321 problem since digits can hold values up to 2*PyLONG_MASK+1.
|
|
|
3322
|
|
|
3323 With the original choices for shift above, extra_bits will always
|
|
|
3324 be 2 or 3. Then rounding under the round-half-to-even rule, we
|
|
|
3325 round up iff the most significant of the extra bits is 1, and
|
|
|
3326 either: (a) the computation of x in step 2 had an inexact result,
|
|
|
3327 or (b) at least one other of the extra bits is 1, or (c) the least
|
|
|
3328 significant bit of x (above those to be rounded) is 1.
|
|
|
3329
|
|
|
3330 4. Conversion to a double is straightforward; all floating-point
|
|
|
3331 operations involved in the conversion are exact, so there's no
|
|
|
3332 danger of rounding errors.
|
|
|
3333
|
|
|
3334 5. Use ldexp(x, shift) to compute x*2**shift, the final result.
|
|
|
3335 The result will always be exactly representable as a double, except
|
|
|
3336 in the case that it overflows. To avoid dependence on the exact
|
|
|
3337 behaviour of ldexp on overflow, we check for overflow before
|
|
|
3338 applying ldexp. The result of ldexp is adjusted for sign before
|
|
|
3339 returning.
|
|
|
3340 */
|
|
|
3341
|
|
|
3342 /* Reduce to case where a and b are both positive. */
|
|
|
3343 a_size = ABS(Py_SIZE(a));
|
|
|
3344 b_size = ABS(Py_SIZE(b));
|
|
|
3345 negate = (Py_SIZE(a) < 0) ^ (Py_SIZE(b) < 0);
|
|
|
3346 if (b_size == 0) {
|
|
|
3347 PyErr_SetString(PyExc_ZeroDivisionError,
|
|
|
3348 "division by zero");
|
|
|
3349 goto error;
|
|
|
3350 }
|
|
|
3351 if (a_size == 0)
|
|
|
3352 goto underflow_or_zero;
|
|
|
3353
|
|
|
3354 /* Fast path for a and b small (exactly representable in a double).
|
|
|
3355 Relies on floating-point division being correctly rounded; results
|
|
|
3356 may be subject to double rounding on x86 machines that operate with
|
|
|
3357 the x87 FPU set to 64-bit precision. */
|
|
|
3358 a_is_small = a_size <= MANT_DIG_DIGITS ||
|
|
|
3359 (a_size == MANT_DIG_DIGITS+1 &&
|
|
|
3360 a->ob_digit[MANT_DIG_DIGITS] >> MANT_DIG_BITS == 0);
|
|
|
3361 b_is_small = b_size <= MANT_DIG_DIGITS ||
|
|
|
3362 (b_size == MANT_DIG_DIGITS+1 &&
|
|
|
3363 b->ob_digit[MANT_DIG_DIGITS] >> MANT_DIG_BITS == 0);
|
|
|
3364 if (a_is_small && b_is_small) {
|
|
|
3365 double da, db;
|
|
|
3366 da = a->ob_digit[--a_size];
|
|
|
3367 while (a_size > 0)
|
|
|
3368 da = da * PyLong_BASE + a->ob_digit[--a_size];
|
|
|
3369 db = b->ob_digit[--b_size];
|
|
|
3370 while (b_size > 0)
|
|
|
3371 db = db * PyLong_BASE + b->ob_digit[--b_size];
|
|
|
3372 result = da / db;
|
|
|
3373 goto success;
|
|
|
3374 }
|
|
|
3375
|
|
|
3376 /* Catch obvious cases of underflow and overflow */
|
|
|
3377 diff = a_size - b_size;
|
|
|
3378 if (diff > PY_SSIZE_T_MAX/PyLong_SHIFT - 1)
|
|
|
3379 /* Extreme overflow */
|
|
|
3380 goto overflow;
|
|
|
3381 else if (diff < 1 - PY_SSIZE_T_MAX/PyLong_SHIFT)
|
|
|
3382 /* Extreme underflow */
|
|
|
3383 goto underflow_or_zero;
|
|
|
3384 /* Next line is now safe from overflowing a Py_ssize_t */
|
|
|
3385 diff = diff * PyLong_SHIFT + bits_in_digit(a->ob_digit[a_size - 1]) -
|
|
|
3386 bits_in_digit(b->ob_digit[b_size - 1]);
|
|
|
3387 /* Now diff = a_bits - b_bits. */
|
|
|
3388 if (diff > DBL_MAX_EXP)
|
|
|
3389 goto overflow;
|
|
|
3390 else if (diff < DBL_MIN_EXP - DBL_MANT_DIG - 1)
|
|
|
3391 goto underflow_or_zero;
|
|
|
3392
|
|
|
3393 /* Choose value for shift; see comments for step 1 above. */
|
|
|
3394 shift = MAX(diff, DBL_MIN_EXP) - DBL_MANT_DIG - 2;
|
|
|
3395
|
|
|
3396 inexact = 0;
|
|
|
3397
|
|
|
3398 /* x = abs(a * 2**-shift) */
|
|
|
3399 if (shift <= 0) {
|
|
|
3400 Py_ssize_t i, shift_digits = -shift / PyLong_SHIFT;
|
|
|
3401 digit rem;
|
|
|
3402 /* x = a << -shift */
|
|
|
3403 if (a_size >= PY_SSIZE_T_MAX - 1 - shift_digits) {
|
|
|
3404 /* In practice, it's probably impossible to end up
|
|
|
3405 here. Both a and b would have to be enormous,
|
|
|
3406 using close to SIZE_T_MAX bytes of memory each. */
|
|
|
3407 PyErr_SetString(PyExc_OverflowError,
|
|
|
3408 "intermediate overflow during division");
|
|
|
3409 goto error;
|
|
|
3410 }
|
|
|
3411 x = _PyLong_New(a_size + shift_digits + 1);
|
|
|
3412 if (x == NULL)
|
|
|
3413 goto error;
|
|
|
3414 for (i = 0; i < shift_digits; i++)
|
|
|
3415 x->ob_digit[i] = 0;
|
|
|
3416 rem = v_lshift(x->ob_digit + shift_digits, a->ob_digit,
|
|
|
3417 a_size, -shift % PyLong_SHIFT);
|
|
|
3418 x->ob_digit[a_size + shift_digits] = rem;
|
|
|
3419 }
|
|
|
3420 else {
|
|
|
3421 Py_ssize_t shift_digits = shift / PyLong_SHIFT;
|
|
|
3422 digit rem;
|
|
|
3423 /* x = a >> shift */
|
|
|
3424 assert(a_size >= shift_digits);
|
|
|
3425 x = _PyLong_New(a_size - shift_digits);
|
|
|
3426 if (x == NULL)
|
|
|
3427 goto error;
|
|
|
3428 rem = v_rshift(x->ob_digit, a->ob_digit + shift_digits,
|
|
|
3429 a_size - shift_digits, shift % PyLong_SHIFT);
|
|
|
3430 /* set inexact if any of the bits shifted out is nonzero */
|
|
|
3431 if (rem)
|
|
|
3432 inexact = 1;
|
|
|
3433 while (!inexact && shift_digits > 0)
|
|
|
3434 if (a->ob_digit[--shift_digits])
|
|
|
3435 inexact = 1;
|
|
|
3436 }
|
|
|
3437 long_normalize(x);
|
|
|
3438 x_size = Py_SIZE(x);
|
|
|
3439
|
|
|
3440 /* x //= b. If the remainder is nonzero, set inexact. We own the only
|
|
|
3441 reference to x, so it's safe to modify it in-place. */
|
|
|
3442 if (b_size == 1) {
|
|
|
3443 digit rem = inplace_divrem1(x->ob_digit, x->ob_digit, x_size,
|
|
|
3444 b->ob_digit[0]);
|
|
|
3445 long_normalize(x);
|
|
|
3446 if (rem)
|
|
|
3447 inexact = 1;
|
|
|
3448 }
|
|
|
3449 else {
|
|
|
3450 PyLongObject *div, *rem;
|
|
|
3451 div = x_divrem(x, b, &rem);
|
|
|
3452 Py_DECREF(x);
|
|
|
3453 x = div;
|
|
|
3454 if (x == NULL)
|
|
|
3455 goto error;
|
|
|
3456 if (Py_SIZE(rem))
|
|
|
3457 inexact = 1;
|
|
|
3458 Py_DECREF(rem);
|
|
|
3459 }
|
|
|
3460 x_size = ABS(Py_SIZE(x));
|
|
|
3461 assert(x_size > 0); /* result of division is never zero */
|
|
|
3462 x_bits = (x_size-1)*PyLong_SHIFT+bits_in_digit(x->ob_digit[x_size-1]);
|
|
|
3463
|
|
|
3464 /* The number of extra bits that have to be rounded away. */
|
|
|
3465 extra_bits = MAX(x_bits, DBL_MIN_EXP - shift) - DBL_MANT_DIG;
|
|
|
3466 assert(extra_bits == 2 || extra_bits == 3);
|
|
|
3467
|
|
|
3468 /* Round by directly modifying the low digit of x. */
|
|
|
3469 mask = (digit)1 << (extra_bits - 1);
|
|
|
3470 low = x->ob_digit[0] | inexact;
|
|
|
3471 if (low & mask && low & (3*mask-1))
|
|
|
3472 low += mask;
|
|
|
3473 x->ob_digit[0] = low & ~(mask-1U);
|
|
|
3474
|
|
|
3475 /* Convert x to a double dx; the conversion is exact. */
|
|
|
3476 dx = x->ob_digit[--x_size];
|
|
|
3477 while (x_size > 0)
|
|
|
3478 dx = dx * PyLong_BASE + x->ob_digit[--x_size];
|
|
|
3479 Py_DECREF(x);
|
|
|
3480
|
|
|
3481 /* Check whether ldexp result will overflow a double. */
|
|
|
3482 if (shift + x_bits >= DBL_MAX_EXP &&
|
|
|
3483 (shift + x_bits > DBL_MAX_EXP || dx == ldexp(1.0, (int)x_bits)))
|
|
|
3484 goto overflow;
|
|
|
3485 result = ldexp(dx, (int)shift);
|
|
|
3486
|
|
|
3487 success:
|
|
|
3488 return PyFloat_FromDouble(negate ? -result : result);
|
|
|
3489
|
|
|
3490 underflow_or_zero:
|
|
|
3491 return PyFloat_FromDouble(negate ? -0.0 : 0.0);
|
|
|
3492
|
|
|
3493 overflow:
|
|
|
3494 PyErr_SetString(PyExc_OverflowError,
|
|
|
3495 "integer division result too large for a float");
|
|
|
3496 error:
|
|
|
3497 return NULL;
|
|
|
3498 }
|
|
|
3499
|
|
|
3500 static PyObject *
|
|
|
3501 long_mod(PyObject *a, PyObject *b)
|
|
|
3502 {
|
|
|
3503 PyLongObject *mod;
|
|
|
3504
|
|
|
3505 CHECK_BINOP(a, b);
|
|
|
3506
|
|
|
3507 if (l_divmod((PyLongObject*)a, (PyLongObject*)b, NULL, &mod) < 0)
|
|
|
3508 mod = NULL;
|
|
|
3509 return (PyObject *)mod;
|
|
|
3510 }
|
|
|
3511
|
|
|
3512 static PyObject *
|
|
|
3513 long_divmod(PyObject *a, PyObject *b)
|
|
|
3514 {
|
|
|
3515 PyLongObject *div, *mod;
|
|
|
3516 PyObject *z;
|
|
|
3517
|
|
|
3518 CHECK_BINOP(a, b);
|
|
|
3519
|
|
|
3520 if (l_divmod((PyLongObject*)a, (PyLongObject*)b, &div, &mod) < 0) {
|
|
|
3521 return NULL;
|
|
|
3522 }
|
|
|
3523 z = PyTuple_New(2);
|
|
|
3524 if (z != NULL) {
|
|
|
3525 PyTuple_SetItem(z, 0, (PyObject *) div);
|
|
|
3526 PyTuple_SetItem(z, 1, (PyObject *) mod);
|
|
|
3527 }
|
|
|
3528 else {
|
|
|
3529 Py_DECREF(div);
|
|
|
3530 Py_DECREF(mod);
|
|
|
3531 }
|
|
|
3532 return z;
|
|
|
3533 }
|
|
|
3534
|
|
|
3535 /* pow(v, w, x) */
|
|
|
3536 static PyObject *
|
|
|
3537 long_pow(PyObject *v, PyObject *w, PyObject *x)
|
|
|
3538 {
|
|
|
3539 PyLongObject *a, *b, *c; /* a,b,c = v,w,x */
|
|
|
3540 int negativeOutput = 0; /* if x<0 return negative output */
|
|
|
3541
|
|
|
3542 PyLongObject *z = NULL; /* accumulated result */
|
|
|
3543 Py_ssize_t i, j, k; /* counters */
|
|
|
3544 PyLongObject *temp = NULL;
|
|
|
3545
|
|
|
3546 /* 5-ary values. If the exponent is large enough, table is
|
|
|
3547 * precomputed so that table[i] == a**i % c for i in range(32).
|
|
|
3548 */
|
|
|
3549 PyLongObject *table[32] = {0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
|
|
|
3550 0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0};
|
|
|
3551
|
|
|
3552 /* a, b, c = v, w, x */
|
|
|
3553 CHECK_BINOP(v, w);
|
|
|
3554 a = (PyLongObject*)v; Py_INCREF(a);
|
|
|
3555 b = (PyLongObject*)w; Py_INCREF(b);
|
|
|
3556 if (PyLong_Check(x)) {
|
|
|
3557 c = (PyLongObject *)x;
|
|
|
3558 Py_INCREF(x);
|
|
|
3559 }
|
|
|
3560 else if (x == Py_None)
|
|
|
3561 c = NULL;
|
|
|
3562 else {
|
|
|
3563 Py_DECREF(a);
|
|
|
3564 Py_DECREF(b);
|
|
|
3565 Py_RETURN_NOTIMPLEMENTED;
|
|
|
3566 }
|
|
|
3567
|
|
|
3568 if (Py_SIZE(b) < 0) { /* if exponent is negative */
|
|
|
3569 if (c) {
|
|
|
3570 PyErr_SetString(PyExc_TypeError, "pow() 2nd argument "
|
|
|
3571 "cannot be negative when 3rd argument specified");
|
|
|
3572 goto Error;
|
|
|
3573 }
|
|
|
3574 else {
|
|
|
3575 /* else return a float. This works because we know
|
|
|
3576 that this calls float_pow() which converts its
|
|
|
3577 arguments to double. */
|
|
|
3578 Py_DECREF(a);
|
|
|
3579 Py_DECREF(b);
|
|
|
3580 return PyFloat_Type.tp_as_number->nb_power(v, w, x);
|
|
|
3581 }
|
|
|
3582 }
|
|
|
3583
|
|
|
3584 if (c) {
|
|
|
3585 /* if modulus == 0:
|
|
|
3586 raise ValueError() */
|
|
|
3587 if (Py_SIZE(c) == 0) {
|
|
|
3588 PyErr_SetString(PyExc_ValueError,
|
|
|
3589 "pow() 3rd argument cannot be 0");
|
|
|
3590 goto Error;
|
|
|
3591 }
|
|
|
3592
|
|
|
3593 /* if modulus < 0:
|
|
|
3594 negativeOutput = True
|
|
|
3595 modulus = -modulus */
|
|
|
3596 if (Py_SIZE(c) < 0) {
|
|
|
3597 negativeOutput = 1;
|
|
|
3598 temp = (PyLongObject *)_PyLong_Copy(c);
|
|
|
3599 if (temp == NULL)
|
|
|
3600 goto Error;
|
|
|
3601 Py_DECREF(c);
|
|
|
3602 c = temp;
|
|
|
3603 temp = NULL;
|
|
|
3604 NEGATE(c);
|
|
|
3605 }
|
|
|
3606
|
|
|
3607 /* if modulus == 1:
|
|
|
3608 return 0 */
|
|
|
3609 if ((Py_SIZE(c) == 1) && (c->ob_digit[0] == 1)) {
|
|
|
3610 z = (PyLongObject *)PyLong_FromLong(0L);
|
|
|
3611 goto Done;
|
|
|
3612 }
|
|
|
3613
|
|
|
3614 /* if base < 0:
|
|
|
3615 base = base % modulus
|
|
|
3616 Having the base positive just makes things easier. */
|
|
|
3617 if (Py_SIZE(a) < 0) {
|
|
|
3618 if (l_divmod(a, c, NULL, &temp) < 0)
|
|
|
3619 goto Error;
|
|
|
3620 Py_DECREF(a);
|
|
|
3621 a = temp;
|
|
|
3622 temp = NULL;
|
|
|
3623 }
|
|
|
3624 }
|
|
|
3625
|
|
|
3626 /* At this point a, b, and c are guaranteed non-negative UNLESS
|
|
|
3627 c is NULL, in which case a may be negative. */
|
|
|
3628
|
|
|
3629 z = (PyLongObject *)PyLong_FromLong(1L);
|
|
|
3630 if (z == NULL)
|
|
|
3631 goto Error;
|
|
|
3632
|
|
|
3633 /* Perform a modular reduction, X = X % c, but leave X alone if c
|
|
|
3634 * is NULL.
|
|
|
3635 */
|
|
|
3636 #define REDUCE(X) \
|
|
|
3637 do { \
|
|
|
3638 if (c != NULL) { \
|
|
|
3639 if (l_divmod(X, c, NULL, &temp) < 0) \
|
|
|
3640 goto Error; \
|
|
|
3641 Py_XDECREF(X); \
|
|
|
3642 X = temp; \
|
|
|
3643 temp = NULL; \
|
|
|
3644 } \
|
|
|
3645 } while(0)
|
|
|
3646
|
|
|
3647 /* Multiply two values, then reduce the result:
|
|
|
3648 result = X*Y % c. If c is NULL, skip the mod. */
|
|
|
3649 #define MULT(X, Y, result) \
|
|
|
3650 do { \
|
|
|
3651 temp = (PyLongObject *)long_mul(X, Y); \
|
|
|
3652 if (temp == NULL) \
|
|
|
3653 goto Error; \
|
|
|
3654 Py_XDECREF(result); \
|
|
|
3655 result = temp; \
|
|
|
3656 temp = NULL; \
|
|
|
3657 REDUCE(result); \
|
|
|
3658 } while(0)
|
|
|
3659
|
|
|
3660 if (Py_SIZE(b) <= FIVEARY_CUTOFF) {
|
|
|
3661 /* Left-to-right binary exponentiation (HAC Algorithm 14.79) */
|
|
|
3662 /* http://www.cacr.math.uwaterloo.ca/hac/about/chap14.pdf */
|
|
|
3663 for (i = Py_SIZE(b) - 1; i >= 0; --i) {
|
|
|
3664 digit bi = b->ob_digit[i];
|
|
|
3665
|
|
|
3666 for (j = (digit)1 << (PyLong_SHIFT-1); j != 0; j >>= 1) {
|
|
|
3667 MULT(z, z, z);
|
|
|
3668 if (bi & j)
|
|
|
3669 MULT(z, a, z);
|
|
|
3670 }
|
|
|
3671 }
|
|
|
3672 }
|
|
|
3673 else {
|
|
|
3674 /* Left-to-right 5-ary exponentiation (HAC Algorithm 14.82) */
|
|
|
3675 Py_INCREF(z); /* still holds 1L */
|
|
|
3676 table[0] = z;
|
|
|
3677 for (i = 1; i < 32; ++i)
|
|
|
3678 MULT(table[i-1], a, table[i]);
|
|
|
3679
|
|
|
3680 for (i = Py_SIZE(b) - 1; i >= 0; --i) {
|
|
|
3681 const digit bi = b->ob_digit[i];
|
|
|
3682
|
|
|
3683 for (j = PyLong_SHIFT - 5; j >= 0; j -= 5) {
|
|
|
3684 const int index = (bi >> j) & 0x1f;
|
|
|
3685 for (k = 0; k < 5; ++k)
|
|
|
3686 MULT(z, z, z);
|
|
|
3687 if (index)
|
|
|
3688 MULT(z, table[index], z);
|
|
|
3689 }
|
|
|
3690 }
|
|
|
3691 }
|
|
|
3692
|
|
|
3693 if (negativeOutput && (Py_SIZE(z) != 0)) {
|
|
|
3694 temp = (PyLongObject *)long_sub(z, c);
|
|
|
3695 if (temp == NULL)
|
|
|
3696 goto Error;
|
|
|
3697 Py_DECREF(z);
|
|
|
3698 z = temp;
|
|
|
3699 temp = NULL;
|
|
|
3700 }
|
|
|
3701 goto Done;
|
|
|
3702
|
|
|
3703 Error:
|
|
|
3704 if (z != NULL) {
|
|
|
3705 Py_DECREF(z);
|
|
|
3706 z = NULL;
|
|
|
3707 }
|
|
|
3708 /* fall through */
|
|
|
3709 Done:
|
|
|
3710 if (Py_SIZE(b) > FIVEARY_CUTOFF) {
|
|
|
3711 for (i = 0; i < 32; ++i)
|
|
|
3712 Py_XDECREF(table[i]);
|
|
|
3713 }
|
|
|
3714 Py_DECREF(a);
|
|
|
3715 Py_DECREF(b);
|
|
|
3716 Py_XDECREF(c);
|
|
|
3717 Py_XDECREF(temp);
|
|
|
3718 return (PyObject *)z;
|
|
|
3719 }
|
|
|
3720
|
|
|
3721 static PyObject *
|
|
|
3722 long_invert(PyLongObject *v)
|
|
|
3723 {
|
|
|
3724 /* Implement ~x as -(x+1) */
|
|
|
3725 PyLongObject *x;
|
|
|
3726 PyLongObject *w;
|
|
|
3727 if (ABS(Py_SIZE(v)) <=1)
|
|
|
3728 return PyLong_FromLong(-(MEDIUM_VALUE(v)+1));
|
|
|
3729 w = (PyLongObject *)PyLong_FromLong(1L);
|
|
|
3730 if (w == NULL)
|
|
|
3731 return NULL;
|
|
|
3732 x = (PyLongObject *) long_add(v, w);
|
|
|
3733 Py_DECREF(w);
|
|
|
3734 if (x == NULL)
|
|
|
3735 return NULL;
|
|
|
3736 Py_SIZE(x) = -(Py_SIZE(x));
|
|
|
3737 return (PyObject *)maybe_small_long(x);
|
|
|
3738 }
|
|
|
3739
|
|
|
3740 static PyObject *
|
|
|
3741 long_neg(PyLongObject *v)
|
|
|
3742 {
|
|
|
3743 PyLongObject *z;
|
|
|
3744 if (ABS(Py_SIZE(v)) <= 1)
|
|
|
3745 return PyLong_FromLong(-MEDIUM_VALUE(v));
|
|
|
3746 z = (PyLongObject *)_PyLong_Copy(v);
|
|
|
3747 if (z != NULL)
|
|
|
3748 Py_SIZE(z) = -(Py_SIZE(v));
|
|
|
3749 return (PyObject *)z;
|
|
|
3750 }
|
|
|
3751
|
|
|
3752 static PyObject *
|
|
|
3753 long_abs(PyLongObject *v)
|
|
|
3754 {
|
|
|
3755 if (Py_SIZE(v) < 0)
|
|
|
3756 return long_neg(v);
|
|
|
3757 else
|
|
|
3758 return long_long((PyObject *)v);
|
|
|
3759 }
|
|
|
3760
|
|
|
3761 static int
|
|
|
3762 long_bool(PyLongObject *v)
|
|
|
3763 {
|
|
|
3764 return Py_SIZE(v) != 0;
|
|
|
3765 }
|
|
|
3766
|
|
|
3767 static PyObject *
|
|
|
3768 long_rshift(PyLongObject *a, PyLongObject *b)
|
|
|
3769 {
|
|
|
3770 PyLongObject *z = NULL;
|
|
|
3771 Py_ssize_t shiftby, newsize, wordshift, loshift, hishift, i, j;
|
|
|
3772 digit lomask, himask;
|
|
|
3773
|
|
|
3774 CHECK_BINOP(a, b);
|
|
|
3775
|
|
|
3776 if (Py_SIZE(a) < 0) {
|
|
|
3777 /* Right shifting negative numbers is harder */
|
|
|
3778 PyLongObject *a1, *a2;
|
|
|
3779 a1 = (PyLongObject *) long_invert(a);
|
|
|
3780 if (a1 == NULL)
|
|
|
3781 goto rshift_error;
|
|
|
3782 a2 = (PyLongObject *) long_rshift(a1, b);
|
|
|
3783 Py_DECREF(a1);
|
|
|
3784 if (a2 == NULL)
|
|
|
3785 goto rshift_error;
|
|
|
3786 z = (PyLongObject *) long_invert(a2);
|
|
|
3787 Py_DECREF(a2);
|
|
|
3788 }
|
|
|
3789 else {
|
|
|
3790 shiftby = PyLong_AsSsize_t((PyObject *)b);
|
|
|
3791 if (shiftby == -1L && PyErr_Occurred())
|
|
|
3792 goto rshift_error;
|
|
|
3793 if (shiftby < 0) {
|
|
|
3794 PyErr_SetString(PyExc_ValueError,
|
|
|
3795 "negative shift count");
|
|
|
3796 goto rshift_error;
|
|
|
3797 }
|
|
|
3798 wordshift = shiftby / PyLong_SHIFT;
|
|
|
3799 newsize = ABS(Py_SIZE(a)) - wordshift;
|
|
|
3800 if (newsize <= 0)
|
|
|
3801 return PyLong_FromLong(0);
|
|
|
3802 loshift = shiftby % PyLong_SHIFT;
|
|
|
3803 hishift = PyLong_SHIFT - loshift;
|
|
|
3804 lomask = ((digit)1 << hishift) - 1;
|
|
|
3805 himask = PyLong_MASK ^ lomask;
|
|
|
3806 z = _PyLong_New(newsize);
|
|
|
3807 if (z == NULL)
|
|
|
3808 goto rshift_error;
|
|
|
3809 if (Py_SIZE(a) < 0)
|
|
|
3810 Py_SIZE(z) = -(Py_SIZE(z));
|
|
|
3811 for (i = 0, j = wordshift; i < newsize; i++, j++) {
|
|
|
3812 z->ob_digit[i] = (a->ob_digit[j] >> loshift) & lomask;
|
|
|
3813 if (i+1 < newsize)
|
|
|
3814 z->ob_digit[i] |= (a->ob_digit[j+1] << hishift) & himask;
|
|
|
3815 }
|
|
|
3816 z = long_normalize(z);
|
|
|
3817 }
|
|
|
3818 rshift_error:
|
|
|
3819 return (PyObject *) maybe_small_long(z);
|
|
|
3820
|
|
|
3821 }
|
|
|
3822
|
|
|
3823 static PyObject *
|
|
|
3824 long_lshift(PyObject *v, PyObject *w)
|
|
|
3825 {
|
|
|
3826 /* This version due to Tim Peters */
|
|
|
3827 PyLongObject *a = (PyLongObject*)v;
|
|
|
3828 PyLongObject *b = (PyLongObject*)w;
|
|
|
3829 PyLongObject *z = NULL;
|
|
|
3830 Py_ssize_t shiftby, oldsize, newsize, wordshift, remshift, i, j;
|
|
|
3831 twodigits accum;
|
|
|
3832
|
|
|
3833 CHECK_BINOP(a, b);
|
|
|
3834
|
|
|
3835 shiftby = PyLong_AsSsize_t((PyObject *)b);
|
|
|
3836 if (shiftby == -1L && PyErr_Occurred())
|
|
|
3837 goto lshift_error;
|
|
|
3838 if (shiftby < 0) {
|
|
|
3839 PyErr_SetString(PyExc_ValueError, "negative shift count");
|
|
|
3840 goto lshift_error;
|
|
|
3841 }
|
|
|
3842 /* wordshift, remshift = divmod(shiftby, PyLong_SHIFT) */
|
|
|
3843 wordshift = shiftby / PyLong_SHIFT;
|
|
|
3844 remshift = shiftby - wordshift * PyLong_SHIFT;
|
|
|
3845
|
|
|
3846 oldsize = ABS(Py_SIZE(a));
|
|
|
3847 newsize = oldsize + wordshift;
|
|
|
3848 if (remshift)
|
|
|
3849 ++newsize;
|
|
|
3850 z = _PyLong_New(newsize);
|
|
|
3851 if (z == NULL)
|
|
|
3852 goto lshift_error;
|
|
|
3853 if (Py_SIZE(a) < 0)
|
|
|
3854 NEGATE(z);
|
|
|
3855 for (i = 0; i < wordshift; i++)
|
|
|
3856 z->ob_digit[i] = 0;
|
|
|
3857 accum = 0;
|
|
|
3858 for (i = wordshift, j = 0; j < oldsize; i++, j++) {
|
|
|
3859 accum |= (twodigits)a->ob_digit[j] << remshift;
|
|
|
3860 z->ob_digit[i] = (digit)(accum & PyLong_MASK);
|
|
|
3861 accum >>= PyLong_SHIFT;
|
|
|
3862 }
|
|
|
3863 if (remshift)
|
|
|
3864 z->ob_digit[newsize-1] = (digit)accum;
|
|
|
3865 else
|
|
|
3866 assert(!accum);
|
|
|
3867 z = long_normalize(z);
|
|
|
3868 lshift_error:
|
|
|
3869 return (PyObject *) maybe_small_long(z);
|
|
|
3870 }
|
|
|
3871
|
|
|
3872 /* Compute two's complement of digit vector a[0:m], writing result to
|
|
|
3873 z[0:m]. The digit vector a need not be normalized, but should not
|
|
|
3874 be entirely zero. a and z may point to the same digit vector. */
|
|
|
3875
|
|
|
3876 static void
|
|
|
3877 v_complement(digit *z, digit *a, Py_ssize_t m)
|
|
|
3878 {
|
|
|
3879 Py_ssize_t i;
|
|
|
3880 digit carry = 1;
|
|
|
3881 for (i = 0; i < m; ++i) {
|
|
|
3882 carry += a[i] ^ PyLong_MASK;
|
|
|
3883 z[i] = carry & PyLong_MASK;
|
|
|
3884 carry >>= PyLong_SHIFT;
|
|
|
3885 }
|
|
|
3886 assert(carry == 0);
|
|
|
3887 }
|
|
|
3888
|
|
|
3889 /* Bitwise and/xor/or operations */
|
|
|
3890
|
|
|
3891 static PyObject *
|
|
|
3892 long_bitwise(PyLongObject *a,
|
|
|
3893 int op, /* '&', '|', '^' */
|
|
|
3894 PyLongObject *b)
|
|
|
3895 {
|
|
|
3896 int nega, negb, negz;
|
|
|
3897 Py_ssize_t size_a, size_b, size_z, i;
|
|
|
3898 PyLongObject *z;
|
|
|
3899
|
|
|
3900 /* Bitwise operations for negative numbers operate as though
|
|
|
3901 on a two's complement representation. So convert arguments
|
|
|
3902 from sign-magnitude to two's complement, and convert the
|
|
|
3903 result back to sign-magnitude at the end. */
|
|
|
3904
|
|
|
3905 /* If a is negative, replace it by its two's complement. */
|
|
|
3906 size_a = ABS(Py_SIZE(a));
|
|
|
3907 nega = Py_SIZE(a) < 0;
|
|
|
3908 if (nega) {
|
|
|
3909 z = _PyLong_New(size_a);
|
|
|
3910 if (z == NULL)
|
|
|
3911 return NULL;
|
|
|
3912 v_complement(z->ob_digit, a->ob_digit, size_a);
|
|
|
3913 a = z;
|
|
|
3914 }
|
|
|
3915 else
|
|
|
3916 /* Keep reference count consistent. */
|
|
|
3917 Py_INCREF(a);
|
|
|
3918
|
|
|
3919 /* Same for b. */
|
|
|
3920 size_b = ABS(Py_SIZE(b));
|
|
|
3921 negb = Py_SIZE(b) < 0;
|
|
|
3922 if (negb) {
|
|
|
3923 z = _PyLong_New(size_b);
|
|
|
3924 if (z == NULL) {
|
|
|
3925 Py_DECREF(a);
|
|
|
3926 return NULL;
|
|
|
3927 }
|
|
|
3928 v_complement(z->ob_digit, b->ob_digit, size_b);
|
|
|
3929 b = z;
|
|
|
3930 }
|
|
|
3931 else
|
|
|
3932 Py_INCREF(b);
|
|
|
3933
|
|
|
3934 /* Swap a and b if necessary to ensure size_a >= size_b. */
|
|
|
3935 if (size_a < size_b) {
|
|
|
3936 z = a; a = b; b = z;
|
|
|
3937 size_z = size_a; size_a = size_b; size_b = size_z;
|
|
|
3938 negz = nega; nega = negb; negb = negz;
|
|
|
3939 }
|
|
|
3940
|
|
|
3941 /* JRH: The original logic here was to allocate the result value (z)
|
|
|
3942 as the longer of the two operands. However, there are some cases
|
|
|
3943 where the result is guaranteed to be shorter than that: AND of two
|
|
|
3944 positives, OR of two negatives: use the shorter number. AND with
|
|
|
3945 mixed signs: use the positive number. OR with mixed signs: use the
|
|
|
3946 negative number.
|
|
|
3947 */
|
|
|
3948 switch (op) {
|
|
|
3949 case '^':
|
|
|
3950 negz = nega ^ negb;
|
|
|
3951 size_z = size_a;
|
|
|
3952 break;
|
|
|
3953 case '&':
|
|
|
3954 negz = nega & negb;
|
|
|
3955 size_z = negb ? size_a : size_b;
|
|
|
3956 break;
|
|
|
3957 case '|':
|
|
|
3958 negz = nega | negb;
|
|
|
3959 size_z = negb ? size_b : size_a;
|
|
|
3960 break;
|
|
|
3961 default:
|
|
|
3962 PyErr_BadArgument();
|
|
|
3963 return NULL;
|
|
|
3964 }
|
|
|
3965
|
|
|
3966 /* We allow an extra digit if z is negative, to make sure that
|
|
|
3967 the final two's complement of z doesn't overflow. */
|
|
|
3968 z = _PyLong_New(size_z + negz);
|
|
|
3969 if (z == NULL) {
|
|
|
3970 Py_DECREF(a);
|
|
|
3971 Py_DECREF(b);
|
|
|
3972 return NULL;
|
|
|
3973 }
|
|
|
3974
|
|
|
3975 /* Compute digits for overlap of a and b. */
|
|
|
3976 switch(op) {
|
|
|
3977 case '&':
|
|
|
3978 for (i = 0; i < size_b; ++i)
|
|
|
3979 z->ob_digit[i] = a->ob_digit[i] & b->ob_digit[i];
|
|
|
3980 break;
|
|
|
3981 case '|':
|
|
|
3982 for (i = 0; i < size_b; ++i)
|
|
|
3983 z->ob_digit[i] = a->ob_digit[i] | b->ob_digit[i];
|
|
|
3984 break;
|
|
|
3985 case '^':
|
|
|
3986 for (i = 0; i < size_b; ++i)
|
|
|
3987 z->ob_digit[i] = a->ob_digit[i] ^ b->ob_digit[i];
|
|
|
3988 break;
|
|
|
3989 default:
|
|
|
3990 PyErr_BadArgument();
|
|
|
3991 return NULL;
|
|
|
3992 }
|
|
|
3993
|
|
|
3994 /* Copy any remaining digits of a, inverting if necessary. */
|
|
|
3995 if (op == '^' && negb)
|
|
|
3996 for (; i < size_z; ++i)
|
|
|
3997 z->ob_digit[i] = a->ob_digit[i] ^ PyLong_MASK;
|
|
|
3998 else if (i < size_z)
|
|
|
3999 memcpy(&z->ob_digit[i], &a->ob_digit[i],
|
|
|
4000 (size_z-i)*sizeof(digit));
|
|
|
4001
|
|
|
4002 /* Complement result if negative. */
|
|
|
4003 if (negz) {
|
|
|
4004 Py_SIZE(z) = -(Py_SIZE(z));
|
|
|
4005 z->ob_digit[size_z] = PyLong_MASK;
|
|
|
4006 v_complement(z->ob_digit, z->ob_digit, size_z+1);
|
|
|
4007 }
|
|
|
4008
|
|
|
4009 Py_DECREF(a);
|
|
|
4010 Py_DECREF(b);
|
|
|
4011 return (PyObject *)maybe_small_long(long_normalize(z));
|
|
|
4012 }
|
|
|
4013
|
|
|
4014 static PyObject *
|
|
|
4015 long_and(PyObject *a, PyObject *b)
|
|
|
4016 {
|
|
|
4017 PyObject *c;
|
|
|
4018 CHECK_BINOP(a, b);
|
|
|
4019 c = long_bitwise((PyLongObject*)a, '&', (PyLongObject*)b);
|
|
|
4020 return c;
|
|
|
4021 }
|
|
|
4022
|
|
|
4023 static PyObject *
|
|
|
4024 long_xor(PyObject *a, PyObject *b)
|
|
|
4025 {
|
|
|
4026 PyObject *c;
|
|
|
4027 CHECK_BINOP(a, b);
|
|
|
4028 c = long_bitwise((PyLongObject*)a, '^', (PyLongObject*)b);
|
|
|
4029 return c;
|
|
|
4030 }
|
|
|
4031
|
|
|
4032 static PyObject *
|
|
|
4033 long_or(PyObject *a, PyObject *b)
|
|
|
4034 {
|
|
|
4035 PyObject *c;
|
|
|
4036 CHECK_BINOP(a, b);
|
|
|
4037 c = long_bitwise((PyLongObject*)a, '|', (PyLongObject*)b);
|
|
|
4038 return c;
|
|
|
4039 }
|
|
|
4040
|
|
|
4041 static PyObject *
|
|
|
4042 long_long(PyObject *v)
|
|
|
4043 {
|
|
|
4044 if (PyLong_CheckExact(v))
|
|
|
4045 Py_INCREF(v);
|
|
|
4046 else
|
|
|
4047 v = _PyLong_Copy((PyLongObject *)v);
|
|
|
4048 return v;
|
|
|
4049 }
|
|
|
4050
|
|
|
4051 static PyObject *
|
|
|
4052 long_float(PyObject *v)
|
|
|
4053 {
|
|
|
4054 double result;
|
|
|
4055 result = PyLong_AsDouble(v);
|
|
|
4056 if (result == -1.0 && PyErr_Occurred())
|
|
|
4057 return NULL;
|
|
|
4058 return PyFloat_FromDouble(result);
|
|
|
4059 }
|
|
|
4060
|
|
|
4061 static PyObject *
|
|
|
4062 long_subtype_new(PyTypeObject *type, PyObject *args, PyObject *kwds);
|
|
|
4063
|
|
|
4064 static PyObject *
|
|
|
4065 long_new(PyTypeObject *type, PyObject *args, PyObject *kwds)
|
|
|
4066 {
|
|
|
4067 PyObject *obase = NULL, *x = NULL;
|
|
|
4068 long base;
|
|
|
4069 int overflow;
|
|
|
4070 static char *kwlist[] = {"x", "base", 0};
|
|
|
4071
|
|
|
4072 if (type != &PyLong_Type)
|
|
|
4073 return long_subtype_new(type, args, kwds); /* Wimp out */
|
|
|
4074 if (!PyArg_ParseTupleAndKeywords(args, kwds, "|OO:int", kwlist,
|
|
|
4075 &x, &obase))
|
|
|
4076 return NULL;
|
|
|
4077 if (x == NULL)
|
|
|
4078 return PyLong_FromLong(0L);
|
|
|
4079 if (obase == NULL)
|
|
|
4080 return PyNumber_Long(x);
|
|
|
4081
|
|
|
4082 base = PyLong_AsLongAndOverflow(obase, &overflow);
|
|
|
4083 if (base == -1 && PyErr_Occurred())
|
|
|
4084 return NULL;
|
|
|
4085 if (overflow || (base != 0 && base < 2) || base > 36) {
|
|
|
4086 PyErr_SetString(PyExc_ValueError,
|
|
|
4087 "int() arg 2 must be >= 2 and <= 36");
|
|
|
4088 return NULL;
|
|
|
4089 }
|
|
|
4090
|
|
|
4091 if (PyUnicode_Check(x))
|
|
|
4092 return PyLong_FromUnicodeObject(x, (int)base);
|
|
|
4093 else if (PyByteArray_Check(x) || PyBytes_Check(x)) {
|
|
|
4094 /* Since PyLong_FromString doesn't have a length parameter,
|
|
|
4095 * check here for possible NULs in the string. */
|
|
|
4096 char *string;
|
|
|
4097 Py_ssize_t size = Py_SIZE(x);
|
|
|
4098 if (PyByteArray_Check(x))
|
|
|
4099 string = PyByteArray_AS_STRING(x);
|
|
|
4100 else
|
|
|
4101 string = PyBytes_AS_STRING(x);
|
|
|
4102 if (strlen(string) != (size_t)size) {
|
|
|
4103 /* We only see this if there's a null byte in x,
|
|
|
4104 x is a bytes or buffer, *and* a base is given. */
|
|
|
4105 PyErr_Format(PyExc_ValueError,
|
|
|
4106 "invalid literal for int() with base %d: %R",
|
|
|
4107 (int)base, x);
|
|
|
4108 return NULL;
|
|
|
4109 }
|
|
|
4110 return PyLong_FromString(string, NULL, (int)base);
|
|
|
4111 }
|
|
|
4112 else {
|
|
|
4113 PyErr_SetString(PyExc_TypeError,
|
|
|
4114 "int() can't convert non-string with explicit base");
|
|
|
4115 return NULL;
|
|
|
4116 }
|
|
|
4117 }
|
|
|
4118
|
|
|
4119 /* Wimpy, slow approach to tp_new calls for subtypes of long:
|
|
|
4120 first create a regular long from whatever arguments we got,
|
|
|
4121 then allocate a subtype instance and initialize it from
|
|
|
4122 the regular long. The regular long is then thrown away.
|
|
|
4123 */
|
|
|
4124 static PyObject *
|
|
|
4125 long_subtype_new(PyTypeObject *type, PyObject *args, PyObject *kwds)
|
|
|
4126 {
|
|
|
4127 PyLongObject *tmp, *newobj;
|
|
|
4128 Py_ssize_t i, n;
|
|
|
4129
|
|
|
4130 assert(PyType_IsSubtype(type, &PyLong_Type));
|
|
|
4131 tmp = (PyLongObject *)long_new(&PyLong_Type, args, kwds);
|
|
|
4132 if (tmp == NULL)
|
|
|
4133 return NULL;
|
|
|
4134 assert(PyLong_CheckExact(tmp));
|
|
|
4135 n = Py_SIZE(tmp);
|
|
|
4136 if (n < 0)
|
|
|
4137 n = -n;
|
|
|
4138 newobj = (PyLongObject *)type->tp_alloc(type, n);
|
|
|
4139 if (newobj == NULL) {
|
|
|
4140 Py_DECREF(tmp);
|
|
|
4141 return NULL;
|
|
|
4142 }
|
|
|
4143 assert(PyLong_Check(newobj));
|
|
|
4144 Py_SIZE(newobj) = Py_SIZE(tmp);
|
|
|
4145 for (i = 0; i < n; i++)
|
|
|
4146 newobj->ob_digit[i] = tmp->ob_digit[i];
|
|
|
4147 Py_DECREF(tmp);
|
|
|
4148 return (PyObject *)newobj;
|
|
|
4149 }
|
|
|
4150
|
|
|
4151 static PyObject *
|
|
|
4152 long_getnewargs(PyLongObject *v)
|
|
|
4153 {
|
|
|
4154 return Py_BuildValue("(N)", _PyLong_Copy(v));
|
|
|
4155 }
|
|
|
4156
|
|
|
4157 static PyObject *
|
|
|
4158 long_get0(PyLongObject *v, void *context) {
|
|
|
4159 return PyLong_FromLong(0L);
|
|
|
4160 }
|
|
|
4161
|
|
|
4162 static PyObject *
|
|
|
4163 long_get1(PyLongObject *v, void *context) {
|
|
|
4164 return PyLong_FromLong(1L);
|
|
|
4165 }
|
|
|
4166
|
|
|
4167 static PyObject *
|
|
|
4168 long__format__(PyObject *self, PyObject *args)
|
|
|
4169 {
|
|
|
4170 PyObject *format_spec;
|
|
|
4171
|
|
|
4172 if (!PyArg_ParseTuple(args, "U:__format__", &format_spec))
|
|
|
4173 return NULL;
|
|
|
4174 return _PyLong_FormatAdvanced(self, format_spec, 0,
|
|
|
4175 PyUnicode_GET_LENGTH(format_spec));
|
|
|
4176 }
|
|
|
4177
|
|
|
4178 /* Return a pair (q, r) such that a = b * q + r, and
|
|
|
4179 abs(r) <= abs(b)/2, with equality possible only if q is even.
|
|
|
4180 In other words, q == a / b, rounded to the nearest integer using
|
|
|
4181 round-half-to-even. */
|
|
|
4182
|
|
|
4183 PyObject *
|
|
|
4184 _PyLong_DivmodNear(PyObject *a, PyObject *b)
|
|
|
4185 {
|
|
|
4186 PyLongObject *quo = NULL, *rem = NULL;
|
|
|
4187 PyObject *one = NULL, *twice_rem, *result, *temp;
|
|
|
4188 int cmp, quo_is_odd, quo_is_neg;
|
|
|
4189
|
|
|
4190 /* Equivalent Python code:
|
|
|
4191
|
|
|
4192 def divmod_near(a, b):
|
|
|
4193 q, r = divmod(a, b)
|
|
|
4194 # round up if either r / b > 0.5, or r / b == 0.5 and q is odd.
|
|
|
4195 # The expression r / b > 0.5 is equivalent to 2 * r > b if b is
|
|
|
4196 # positive, 2 * r < b if b negative.
|
|
|
4197 greater_than_half = 2*r > b if b > 0 else 2*r < b
|
|
|
4198 exactly_half = 2*r == b
|
|
|
4199 if greater_than_half or exactly_half and q % 2 == 1:
|
|
|
4200 q += 1
|
|
|
4201 r -= b
|
|
|
4202 return q, r
|
|
|
4203
|
|
|
4204 */
|
|
|
4205 if (!PyLong_Check(a) || !PyLong_Check(b)) {
|
|
|
4206 PyErr_SetString(PyExc_TypeError,
|
|
|
4207 "non-integer arguments in division");
|
|
|
4208 return NULL;
|
|
|
4209 }
|
|
|
4210
|
|
|
4211 /* Do a and b have different signs? If so, quotient is negative. */
|
|
|
4212 quo_is_neg = (Py_SIZE(a) < 0) != (Py_SIZE(b) < 0);
|
|
|
4213
|
|
|
4214 one = PyLong_FromLong(1L);
|
|
|
4215 if (one == NULL)
|
|
|
4216 return NULL;
|
|
|
4217
|
|
|
4218 if (long_divrem((PyLongObject*)a, (PyLongObject*)b, &quo, &rem) < 0)
|
|
|
4219 goto error;
|
|
|
4220
|
|
|
4221 /* compare twice the remainder with the divisor, to see
|
|
|
4222 if we need to adjust the quotient and remainder */
|
|
|
4223 twice_rem = long_lshift((PyObject *)rem, one);
|
|
|
4224 if (twice_rem == NULL)
|
|
|
4225 goto error;
|
|
|
4226 if (quo_is_neg) {
|
|
|
4227 temp = long_neg((PyLongObject*)twice_rem);
|
|
|
4228 Py_DECREF(twice_rem);
|
|
|
4229 twice_rem = temp;
|
|
|
4230 if (twice_rem == NULL)
|
|
|
4231 goto error;
|
|
|
4232 }
|
|
|
4233 cmp = long_compare((PyLongObject *)twice_rem, (PyLongObject *)b);
|
|
|
4234 Py_DECREF(twice_rem);
|
|
|
4235
|
|
|
4236 quo_is_odd = Py_SIZE(quo) != 0 && ((quo->ob_digit[0] & 1) != 0);
|
|
|
4237 if ((Py_SIZE(b) < 0 ? cmp < 0 : cmp > 0) || (cmp == 0 && quo_is_odd)) {
|
|
|
4238 /* fix up quotient */
|
|
|
4239 if (quo_is_neg)
|
|
|
4240 temp = long_sub(quo, (PyLongObject *)one);
|
|
|
4241 else
|
|
|
4242 temp = long_add(quo, (PyLongObject *)one);
|
|
|
4243 Py_DECREF(quo);
|
|
|
4244 quo = (PyLongObject *)temp;
|
|
|
4245 if (quo == NULL)
|
|
|
4246 goto error;
|
|
|
4247 /* and remainder */
|
|
|
4248 if (quo_is_neg)
|
|
|
4249 temp = long_add(rem, (PyLongObject *)b);
|
|
|
4250 else
|
|
|
4251 temp = long_sub(rem, (PyLongObject *)b);
|
|
|
4252 Py_DECREF(rem);
|
|
|
4253 rem = (PyLongObject *)temp;
|
|
|
4254 if (rem == NULL)
|
|
|
4255 goto error;
|
|
|
4256 }
|
|
|
4257
|
|
|
4258 result = PyTuple_New(2);
|
|
|
4259 if (result == NULL)
|
|
|
4260 goto error;
|
|
|
4261
|
|
|
4262 /* PyTuple_SET_ITEM steals references */
|
|
|
4263 PyTuple_SET_ITEM(result, 0, (PyObject *)quo);
|
|
|
4264 PyTuple_SET_ITEM(result, 1, (PyObject *)rem);
|
|
|
4265 Py_DECREF(one);
|
|
|
4266 return result;
|
|
|
4267
|
|
|
4268 error:
|
|
|
4269 Py_XDECREF(quo);
|
|
|
4270 Py_XDECREF(rem);
|
|
|
4271 Py_XDECREF(one);
|
|
|
4272 return NULL;
|
|
|
4273 }
|
|
|
4274
|
|
|
4275 static PyObject *
|
|
|
4276 long_round(PyObject *self, PyObject *args)
|
|
|
4277 {
|
|
|
4278 PyObject *o_ndigits=NULL, *temp, *result, *ndigits;
|
|
|
4279
|
|
|
4280 /* To round an integer m to the nearest 10**n (n positive), we make use of
|
|
|
4281 * the divmod_near operation, defined by:
|
|
|
4282 *
|
|
|
4283 * divmod_near(a, b) = (q, r)
|
|
|
4284 *
|
|
|
4285 * where q is the nearest integer to the quotient a / b (the
|
|
|
4286 * nearest even integer in the case of a tie) and r == a - q * b.
|
|
|
4287 * Hence q * b = a - r is the nearest multiple of b to a,
|
|
|
4288 * preferring even multiples in the case of a tie.
|
|
|
4289 *
|
|
|
4290 * So the nearest multiple of 10**n to m is:
|
|
|
4291 *
|
|
|
4292 * m - divmod_near(m, 10**n)[1].
|
|
|
4293 */
|
|
|
4294 if (!PyArg_ParseTuple(args, "|O", &o_ndigits))
|
|
|
4295 return NULL;
|
|
|
4296 if (o_ndigits == NULL)
|
|
|
4297 return long_long(self);
|
|
|
4298
|
|
|
4299 ndigits = PyNumber_Index(o_ndigits);
|
|
|
4300 if (ndigits == NULL)
|
|
|
4301 return NULL;
|
|
|
4302
|
|
|
4303 /* if ndigits >= 0 then no rounding is necessary; return self unchanged */
|
|
|
4304 if (Py_SIZE(ndigits) >= 0) {
|
|
|
4305 Py_DECREF(ndigits);
|
|
|
4306 return long_long(self);
|
|
|
4307 }
|
|
|
4308
|
|
|
4309 /* result = self - divmod_near(self, 10 ** -ndigits)[1] */
|
|
|
4310 temp = long_neg((PyLongObject*)ndigits);
|
|
|
4311 Py_DECREF(ndigits);
|
|
|
4312 ndigits = temp;
|
|
|
4313 if (ndigits == NULL)
|
|
|
4314 return NULL;
|
|
|
4315
|
|
|
4316 result = PyLong_FromLong(10L);
|
|
|
4317 if (result == NULL) {
|
|
|
4318 Py_DECREF(ndigits);
|
|
|
4319 return NULL;
|
|
|
4320 }
|
|
|
4321
|
|
|
4322 temp = long_pow(result, ndigits, Py_None);
|
|
|
4323 Py_DECREF(ndigits);
|
|
|
4324 Py_DECREF(result);
|
|
|
4325 result = temp;
|
|
|
4326 if (result == NULL)
|
|
|
4327 return NULL;
|
|
|
4328
|
|
|
4329 temp = _PyLong_DivmodNear(self, result);
|
|
|
4330 Py_DECREF(result);
|
|
|
4331 result = temp;
|
|
|
4332 if (result == NULL)
|
|
|
4333 return NULL;
|
|
|
4334
|
|
|
4335 temp = long_sub((PyLongObject *)self,
|
|
|
4336 (PyLongObject *)PyTuple_GET_ITEM(result, 1));
|
|
|
4337 Py_DECREF(result);
|
|
|
4338 result = temp;
|
|
|
4339
|
|
|
4340 return result;
|
|
|
4341 }
|
|
|
4342
|
|
|
4343 static PyObject *
|
|
|
4344 long_sizeof(PyLongObject *v)
|
|
|
4345 {
|
|
|
4346 Py_ssize_t res;
|
|
|
4347
|
|
|
4348 res = offsetof(PyLongObject, ob_digit) + ABS(Py_SIZE(v))*sizeof(digit);
|
|
|
4349 return PyLong_FromSsize_t(res);
|
|
|
4350 }
|
|
|
4351
|
|
|
4352 static PyObject *
|
|
|
4353 long_bit_length(PyLongObject *v)
|
|
|
4354 {
|
|
|
4355 PyLongObject *result, *x, *y;
|
|
|
4356 Py_ssize_t ndigits, msd_bits = 0;
|
|
|
4357 digit msd;
|
|
|
4358
|
|
|
4359 assert(v != NULL);
|
|
|
4360 assert(PyLong_Check(v));
|
|
|
4361
|
|
|
4362 ndigits = ABS(Py_SIZE(v));
|
|
|
4363 if (ndigits == 0)
|
|
|
4364 return PyLong_FromLong(0);
|
|
|
4365
|
|
|
4366 msd = v->ob_digit[ndigits-1];
|
|
|
4367 while (msd >= 32) {
|
|
|
4368 msd_bits += 6;
|
|
|
4369 msd >>= 6;
|
|
|
4370 }
|
|
|
4371 msd_bits += (long)(BitLengthTable[msd]);
|
|
|
4372
|
|
|
4373 if (ndigits <= PY_SSIZE_T_MAX/PyLong_SHIFT)
|
|
|
4374 return PyLong_FromSsize_t((ndigits-1)*PyLong_SHIFT + msd_bits);
|
|
|
4375
|
|
|
4376 /* expression above may overflow; use Python integers instead */
|
|
|
4377 result = (PyLongObject *)PyLong_FromSsize_t(ndigits - 1);
|
|
|
4378 if (result == NULL)
|
|
|
4379 return NULL;
|
|
|
4380 x = (PyLongObject *)PyLong_FromLong(PyLong_SHIFT);
|
|
|
4381 if (x == NULL)
|
|
|
4382 goto error;
|
|
|
4383 y = (PyLongObject *)long_mul(result, x);
|
|
|
4384 Py_DECREF(x);
|
|
|
4385 if (y == NULL)
|
|
|
4386 goto error;
|
|
|
4387 Py_DECREF(result);
|
|
|
4388 result = y;
|
|
|
4389
|
|
|
4390 x = (PyLongObject *)PyLong_FromLong((long)msd_bits);
|
|
|
4391 if (x == NULL)
|
|
|
4392 goto error;
|
|
|
4393 y = (PyLongObject *)long_add(result, x);
|
|
|
4394 Py_DECREF(x);
|
|
|
4395 if (y == NULL)
|
|
|
4396 goto error;
|
|
|
4397 Py_DECREF(result);
|
|
|
4398 result = y;
|
|
|
4399
|
|
|
4400 return (PyObject *)result;
|
|
|
4401
|
|
|
4402 error:
|
|
|
4403 Py_DECREF(result);
|
|
|
4404 return NULL;
|
|
|
4405 }
|
|
|
4406
|
|
|
4407 PyDoc_STRVAR(long_bit_length_doc,
|
|
|
4408 "int.bit_length() -> int\n\
|
|
|
4409 \n\
|
|
|
4410 Number of bits necessary to represent self in binary.\n\
|
|
|
4411 >>> bin(37)\n\
|
|
|
4412 '0b100101'\n\
|
|
|
4413 >>> (37).bit_length()\n\
|
|
|
4414 6");
|
|
|
4415
|
|
|
4416 #if 0
|
|
|
4417 static PyObject *
|
|
|
4418 long_is_finite(PyObject *v)
|
|
|
4419 {
|
|
|
4420 Py_RETURN_TRUE;
|
|
|
4421 }
|
|
|
4422 #endif
|
|
|
4423
|
|
|
4424
|
|
|
4425 static PyObject *
|
|
|
4426 long_to_bytes(PyLongObject *v, PyObject *args, PyObject *kwds)
|
|
|
4427 {
|
|
|
4428 PyObject *byteorder_str;
|
|
|
4429 PyObject *is_signed_obj = NULL;
|
|
|
4430 Py_ssize_t length;
|
|
|
4431 int little_endian;
|
|
|
4432 int is_signed;
|
|
|
4433 PyObject *bytes;
|
|
|
4434 static char *kwlist[] = {"length", "byteorder", "signed", NULL};
|
|
|
4435
|
|
|
4436 if (!PyArg_ParseTupleAndKeywords(args, kwds, "nU|O:to_bytes", kwlist,
|
|
|
4437 &length, &byteorder_str,
|
|
|
4438 &is_signed_obj))
|
|
|
4439 return NULL;
|
|
|
4440
|
|
|
4441 if (args != NULL && Py_SIZE(args) > 2) {
|
|
|
4442 PyErr_SetString(PyExc_TypeError,
|
|
|
4443 "'signed' is a keyword-only argument");
|
|
|
4444 return NULL;
|
|
|
4445 }
|
|
|
4446
|
|
|
4447 if (!PyUnicode_CompareWithASCIIString(byteorder_str, "little"))
|
|
|
4448 little_endian = 1;
|
|
|
4449 else if (!PyUnicode_CompareWithASCIIString(byteorder_str, "big"))
|
|
|
4450 little_endian = 0;
|
|
|
4451 else {
|
|
|
4452 PyErr_SetString(PyExc_ValueError,
|
|
|
4453 "byteorder must be either 'little' or 'big'");
|
|
|
4454 return NULL;
|
|
|
4455 }
|
|
|
4456
|
|
|
4457 if (is_signed_obj != NULL) {
|
|
|
4458 int cmp = PyObject_IsTrue(is_signed_obj);
|
|
|
4459 if (cmp < 0)
|
|
|
4460 return NULL;
|
|
|
4461 is_signed = cmp ? 1 : 0;
|
|
|
4462 }
|
|
|
4463 else {
|
|
|
4464 /* If the signed argument was omitted, use False as the
|
|
|
4465 default. */
|
|
|
4466 is_signed = 0;
|
|
|
4467 }
|
|
|
4468
|
|
|
4469 if (length < 0) {
|
|
|
4470 PyErr_SetString(PyExc_ValueError,
|
|
|
4471 "length argument must be non-negative");
|
|
|
4472 return NULL;
|
|
|
4473 }
|
|
|
4474
|
|
|
4475 bytes = PyBytes_FromStringAndSize(NULL, length);
|
|
|
4476 if (bytes == NULL)
|
|
|
4477 return NULL;
|
|
|
4478
|
|
|
4479 if (_PyLong_AsByteArray(v, (unsigned char *)PyBytes_AS_STRING(bytes),
|
|
|
4480 length, little_endian, is_signed) < 0) {
|
|
|
4481 Py_DECREF(bytes);
|
|
|
4482 return NULL;
|
|
|
4483 }
|
|
|
4484
|
|
|
4485 return bytes;
|
|
|
4486 }
|
|
|
4487
|
|
|
4488 PyDoc_STRVAR(long_to_bytes_doc,
|
|
|
4489 "int.to_bytes(length, byteorder, *, signed=False) -> bytes\n\
|
|
|
4490 \n\
|
|
|
4491 Return an array of bytes representing an integer.\n\
|
|
|
4492 \n\
|
|
|
4493 The integer is represented using length bytes. An OverflowError is\n\
|
|
|
4494 raised if the integer is not representable with the given number of\n\
|
|
|
4495 bytes.\n\
|
|
|
4496 \n\
|
|
|
4497 The byteorder argument determines the byte order used to represent the\n\
|
|
|
4498 integer. If byteorder is 'big', the most significant byte is at the\n\
|
|
|
4499 beginning of the byte array. If byteorder is 'little', the most\n\
|
|
|
4500 significant byte is at the end of the byte array. To request the native\n\
|
|
|
4501 byte order of the host system, use `sys.byteorder' as the byte order value.\n\
|
|
|
4502 \n\
|
|
|
4503 The signed keyword-only argument determines whether two's complement is\n\
|
|
|
4504 used to represent the integer. If signed is False and a negative integer\n\
|
|
|
4505 is given, an OverflowError is raised.");
|
|
|
4506
|
|
|
4507 static PyObject *
|
|
|
4508 long_from_bytes(PyTypeObject *type, PyObject *args, PyObject *kwds)
|
|
|
4509 {
|
|
|
4510 PyObject *byteorder_str;
|
|
|
4511 PyObject *is_signed_obj = NULL;
|
|
|
4512 int little_endian;
|
|
|
4513 int is_signed;
|
|
|
4514 PyObject *obj;
|
|
|
4515 PyObject *bytes;
|
|
|
4516 PyObject *long_obj;
|
|
|
4517 static char *kwlist[] = {"bytes", "byteorder", "signed", NULL};
|
|
|
4518
|
|
|
4519 if (!PyArg_ParseTupleAndKeywords(args, kwds, "OU|O:from_bytes", kwlist,
|
|
|
4520 &obj, &byteorder_str,
|
|
|
4521 &is_signed_obj))
|
|
|
4522 return NULL;
|
|
|
4523
|
|
|
4524 if (args != NULL && Py_SIZE(args) > 2) {
|
|
|
4525 PyErr_SetString(PyExc_TypeError,
|
|
|
4526 "'signed' is a keyword-only argument");
|
|
|
4527 return NULL;
|
|
|
4528 }
|
|
|
4529
|
|
|
4530 if (!PyUnicode_CompareWithASCIIString(byteorder_str, "little"))
|
|
|
4531 little_endian = 1;
|
|
|
4532 else if (!PyUnicode_CompareWithASCIIString(byteorder_str, "big"))
|
|
|
4533 little_endian = 0;
|
|
|
4534 else {
|
|
|
4535 PyErr_SetString(PyExc_ValueError,
|
|
|
4536 "byteorder must be either 'little' or 'big'");
|
|
|
4537 return NULL;
|
|
|
4538 }
|
|
|
4539
|
|
|
4540 if (is_signed_obj != NULL) {
|
|
|
4541 int cmp = PyObject_IsTrue(is_signed_obj);
|
|
|
4542 if (cmp < 0)
|
|
|
4543 return NULL;
|
|
|
4544 is_signed = cmp ? 1 : 0;
|
|
|
4545 }
|
|
|
4546 else {
|
|
|
4547 /* If the signed argument was omitted, use False as the
|
|
|
4548 default. */
|
|
|
4549 is_signed = 0;
|
|
|
4550 }
|
|
|
4551
|
|
|
4552 bytes = PyObject_Bytes(obj);
|
|
|
4553 if (bytes == NULL)
|
|
|
4554 return NULL;
|
|
|
4555
|
|
|
4556 long_obj = _PyLong_FromByteArray(
|
|
|
4557 (unsigned char *)PyBytes_AS_STRING(bytes), Py_SIZE(bytes),
|
|
|
4558 little_endian, is_signed);
|
|
|
4559 Py_DECREF(bytes);
|
|
|
4560
|
|
|
4561 /* If from_bytes() was used on subclass, allocate new subclass
|
|
|
4562 * instance, initialize it with decoded long value and return it.
|
|
|
4563 */
|
|
|
4564 if (type != &PyLong_Type && PyType_IsSubtype(type, &PyLong_Type)) {
|
|
|
4565 PyLongObject *newobj;
|
|
|
4566 int i;
|
|
|
4567 Py_ssize_t n = ABS(Py_SIZE(long_obj));
|
|
|
4568
|
|
|
4569 newobj = (PyLongObject *)type->tp_alloc(type, n);
|
|
|
4570 if (newobj == NULL) {
|
|
|
4571 Py_DECREF(long_obj);
|
|
|
4572 return NULL;
|
|
|
4573 }
|
|
|
4574 assert(PyLong_Check(newobj));
|
|
|
4575 Py_SIZE(newobj) = Py_SIZE(long_obj);
|
|
|
4576 for (i = 0; i < n; i++) {
|
|
|
4577 newobj->ob_digit[i] =
|
|
|
4578 ((PyLongObject *)long_obj)->ob_digit[i];
|
|
|
4579 }
|
|
|
4580 Py_DECREF(long_obj);
|
|
|
4581 return (PyObject *)newobj;
|
|
|
4582 }
|
|
|
4583
|
|
|
4584 return long_obj;
|
|
|
4585 }
|
|
|
4586
|
|
|
4587 PyDoc_STRVAR(long_from_bytes_doc,
|
|
|
4588 "int.from_bytes(bytes, byteorder, *, signed=False) -> int\n\
|
|
|
4589 \n\
|
|
|
4590 Return the integer represented by the given array of bytes.\n\
|
|
|
4591 \n\
|
|
|
4592 The bytes argument must either support the buffer protocol or be an\n\
|
|
|
4593 iterable object producing bytes. Bytes and bytearray are examples of\n\
|
|
|
4594 built-in objects that support the buffer protocol.\n\
|
|
|
4595 \n\
|
|
|
4596 The byteorder argument determines the byte order used to represent the\n\
|
|
|
4597 integer. If byteorder is 'big', the most significant byte is at the\n\
|
|
|
4598 beginning of the byte array. If byteorder is 'little', the most\n\
|
|
|
4599 significant byte is at the end of the byte array. To request the native\n\
|
|
|
4600 byte order of the host system, use `sys.byteorder' as the byte order value.\n\
|
|
|
4601 \n\
|
|
|
4602 The signed keyword-only argument indicates whether two's complement is\n\
|
|
|
4603 used to represent the integer.");
|
|
|
4604
|
|
|
4605 static PyMethodDef long_methods[] = {
|
|
|
4606 {"conjugate", (PyCFunction)long_long, METH_NOARGS,
|
|
|
4607 "Returns self, the complex conjugate of any int."},
|
|
|
4608 {"bit_length", (PyCFunction)long_bit_length, METH_NOARGS,
|
|
|
4609 long_bit_length_doc},
|
|
|
4610 #if 0
|
|
|
4611 {"is_finite", (PyCFunction)long_is_finite, METH_NOARGS,
|
|
|
4612 "Returns always True."},
|
|
|
4613 #endif
|
|
|
4614 {"to_bytes", (PyCFunction)long_to_bytes,
|
|
|
4615 METH_VARARGS|METH_KEYWORDS, long_to_bytes_doc},
|
|
|
4616 {"from_bytes", (PyCFunction)long_from_bytes,
|
|
|
4617 METH_VARARGS|METH_KEYWORDS|METH_CLASS, long_from_bytes_doc},
|
|
|
4618 {"__trunc__", (PyCFunction)long_long, METH_NOARGS,
|
|
|
4619 "Truncating an Integral returns itself."},
|
|
|
4620 {"__floor__", (PyCFunction)long_long, METH_NOARGS,
|
|
|
4621 "Flooring an Integral returns itself."},
|
|
|
4622 {"__ceil__", (PyCFunction)long_long, METH_NOARGS,
|
|
|
4623 "Ceiling of an Integral returns itself."},
|
|
|
4624 {"__round__", (PyCFunction)long_round, METH_VARARGS,
|
|
|
4625 "Rounding an Integral returns itself.\n"
|
|
|
4626 "Rounding with an ndigits argument also returns an integer."},
|
|
|
4627 {"__getnewargs__", (PyCFunction)long_getnewargs, METH_NOARGS},
|
|
|
4628 {"__format__", (PyCFunction)long__format__, METH_VARARGS},
|
|
|
4629 {"__sizeof__", (PyCFunction)long_sizeof, METH_NOARGS,
|
|
|
4630 "Returns size in memory, in bytes"},
|
|
|
4631 {NULL, NULL} /* sentinel */
|
|
|
4632 };
|
|
|
4633
|
|
|
4634 static PyGetSetDef long_getset[] = {
|
|
|
4635 {"real",
|
|
|
4636 (getter)long_long, (setter)NULL,
|
|
|
4637 "the real part of a complex number",
|
|
|
4638 NULL},
|
|
|
4639 {"imag",
|
|
|
4640 (getter)long_get0, (setter)NULL,
|
|
|
4641 "the imaginary part of a complex number",
|
|
|
4642 NULL},
|
|
|
4643 {"numerator",
|
|
|
4644 (getter)long_long, (setter)NULL,
|
|
|
4645 "the numerator of a rational number in lowest terms",
|
|
|
4646 NULL},
|
|
|
4647 {"denominator",
|
|
|
4648 (getter)long_get1, (setter)NULL,
|
|
|
4649 "the denominator of a rational number in lowest terms",
|
|
|
4650 NULL},
|
|
|
4651 {NULL} /* Sentinel */
|
|
|
4652 };
|
|
|
4653
|
|
|
4654 PyDoc_STRVAR(long_doc,
|
|
|
4655 "int(x[, base]) -> integer\n\
|
|
|
4656 \n\
|
|
|
4657 Convert a string or number to an integer, if possible. A floating\n\
|
|
|
4658 point argument will be truncated towards zero (this does not include a\n\
|
|
|
4659 string representation of a floating point number!) When converting a\n\
|
|
|
4660 string, use the optional base. It is an error to supply a base when\n\
|
|
|
4661 converting a non-string.");
|
|
|
4662
|
|
|
4663 static PyNumberMethods long_as_number = {
|
|
|
4664 (binaryfunc)long_add, /*nb_add*/
|
|
|
4665 (binaryfunc)long_sub, /*nb_subtract*/
|
|
|
4666 (binaryfunc)long_mul, /*nb_multiply*/
|
|
|
4667 long_mod, /*nb_remainder*/
|
|
|
4668 long_divmod, /*nb_divmod*/
|
|
|
4669 long_pow, /*nb_power*/
|
|
|
4670 (unaryfunc)long_neg, /*nb_negative*/
|
|
|
4671 (unaryfunc)long_long, /*tp_positive*/
|
|
|
4672 (unaryfunc)long_abs, /*tp_absolute*/
|
|
|
4673 (inquiry)long_bool, /*tp_bool*/
|
|
|
4674 (unaryfunc)long_invert, /*nb_invert*/
|
|
|
4675 long_lshift, /*nb_lshift*/
|
|
|
4676 (binaryfunc)long_rshift, /*nb_rshift*/
|
|
|
4677 long_and, /*nb_and*/
|
|
|
4678 long_xor, /*nb_xor*/
|
|
|
4679 long_or, /*nb_or*/
|
|
|
4680 long_long, /*nb_int*/
|
|
|
4681 0, /*nb_reserved*/
|
|
|
4682 long_float, /*nb_float*/
|
|
|
4683 0, /* nb_inplace_add */
|
|
|
4684 0, /* nb_inplace_subtract */
|
|
|
4685 0, /* nb_inplace_multiply */
|
|
|
4686 0, /* nb_inplace_remainder */
|
|
|
4687 0, /* nb_inplace_power */
|
|
|
4688 0, /* nb_inplace_lshift */
|
|
|
4689 0, /* nb_inplace_rshift */
|
|
|
4690 0, /* nb_inplace_and */
|
|
|
4691 0, /* nb_inplace_xor */
|
|
|
4692 0, /* nb_inplace_or */
|
|
|
4693 long_div, /* nb_floor_divide */
|
|
|
4694 long_true_divide, /* nb_true_divide */
|
|
|
4695 0, /* nb_inplace_floor_divide */
|
|
|
4696 0, /* nb_inplace_true_divide */
|
|
|
4697 long_long, /* nb_index */
|
|
|
4698 };
|
|
|
4699
|
|
|
4700 PyTypeObject PyLong_Type = {
|
|
|
4701 PyVarObject_HEAD_INIT(&PyType_Type, 0)
|
|
|
4702 "int", /* tp_name */
|
|
|
4703 offsetof(PyLongObject, ob_digit), /* tp_basicsize */
|
|
|
4704 sizeof(digit), /* tp_itemsize */
|
|
|
4705 long_dealloc, /* tp_dealloc */
|
|
|
4706 0, /* tp_print */
|
|
|
4707 0, /* tp_getattr */
|
|
|
4708 0, /* tp_setattr */
|
|
|
4709 0, /* tp_reserved */
|
|
|
4710 long_to_decimal_string, /* tp_repr */
|
|
|
4711 &long_as_number, /* tp_as_number */
|
|
|
4712 0, /* tp_as_sequence */
|
|
|
4713 0, /* tp_as_mapping */
|
|
|
4714 (hashfunc)long_hash, /* tp_hash */
|
|
|
4715 0, /* tp_call */
|
|
|
4716 long_to_decimal_string, /* tp_str */
|
|
|
4717 PyObject_GenericGetAttr, /* tp_getattro */
|
|
|
4718 0, /* tp_setattro */
|
|
|
4719 0, /* tp_as_buffer */
|
|
|
4720 Py_TPFLAGS_DEFAULT | Py_TPFLAGS_BASETYPE |
|
|
|
4721 Py_TPFLAGS_LONG_SUBCLASS, /* tp_flags */
|
|
|
4722 long_doc, /* tp_doc */
|
|
|
4723 0, /* tp_traverse */
|
|
|
4724 0, /* tp_clear */
|
|
|
4725 long_richcompare, /* tp_richcompare */
|
|
|
4726 0, /* tp_weaklistoffset */
|
|
|
4727 0, /* tp_iter */
|
|
|
4728 0, /* tp_iternext */
|
|
|
4729 long_methods, /* tp_methods */
|
|
|
4730 0, /* tp_members */
|
|
|
4731 long_getset, /* tp_getset */
|
|
|
4732 0, /* tp_base */
|
|
|
4733 0, /* tp_dict */
|
|
|
4734 0, /* tp_descr_get */
|
|
|
4735 0, /* tp_descr_set */
|
|
|
4736 0, /* tp_dictoffset */
|
|
|
4737 0, /* tp_init */
|
|
|
4738 0, /* tp_alloc */
|
|
|
4739 long_new, /* tp_new */
|
|
|
4740 PyObject_Del, /* tp_free */
|
|
|
4741 };
|
|
|
4742
|
|
|
4743 static PyTypeObject Int_InfoType;
|
|
|
4744
|
|
|
4745 PyDoc_STRVAR(int_info__doc__,
|
|
|
4746 "sys.int_info\n\
|
|
|
4747 \n\
|
|
|
4748 A struct sequence that holds information about Python's\n\
|
|
|
4749 internal representation of integers. The attributes are read only.");
|
|
|
4750
|
|
|
4751 static PyStructSequence_Field int_info_fields[] = {
|
|
|
4752 {"bits_per_digit", "size of a digit in bits"},
|
|
|
4753 {"sizeof_digit", "size in bytes of the C type used to represent a digit"},
|
|
|
4754 {NULL, NULL}
|
|
|
4755 };
|
|
|
4756
|
|
|
4757 static PyStructSequence_Desc int_info_desc = {
|
|
|
4758 "sys.int_info", /* name */
|
|
|
4759 int_info__doc__, /* doc */
|
|
|
4760 int_info_fields, /* fields */
|
|
|
4761 2 /* number of fields */
|
|
|
4762 };
|
|
|
4763
|
|
|
4764 PyObject *
|
|
|
4765 PyLong_GetInfo(void)
|
|
|
4766 {
|
|
|
4767 PyObject* int_info;
|
|
|
4768 int field = 0;
|
|
|
4769 int_info = PyStructSequence_New(&Int_InfoType);
|
|
|
4770 if (int_info == NULL)
|
|
|
4771 return NULL;
|
|
|
4772 PyStructSequence_SET_ITEM(int_info, field++,
|
|
|
4773 PyLong_FromLong(PyLong_SHIFT));
|
|
|
4774 PyStructSequence_SET_ITEM(int_info, field++,
|
|
|
4775 PyLong_FromLong(sizeof(digit)));
|
|
|
4776 if (PyErr_Occurred()) {
|
|
|
4777 Py_CLEAR(int_info);
|
|
|
4778 return NULL;
|
|
|
4779 }
|
|
|
4780 return int_info;
|
|
|
4781 }
|
|
|
4782
|
|
|
4783 int
|
|
|
4784 _PyLong_Init(void)
|
|
|
4785 {
|
|
|
4786 #if NSMALLNEGINTS + NSMALLPOSINTS > 0
|
|
|
4787 int ival, size;
|
|
|
4788 PyLongObject *v = small_ints;
|
|
|
4789
|
|
|
4790 for (ival = -NSMALLNEGINTS; ival < NSMALLPOSINTS; ival++, v++) {
|
|
|
4791 size = (ival < 0) ? -1 : ((ival == 0) ? 0 : 1);
|
|
|
4792 if (Py_TYPE(v) == &PyLong_Type) {
|
|
|
4793 /* The element is already initialized, most likely
|
|
|
4794 * the Python interpreter was initialized before.
|
|
|
4795 */
|
|
|
4796 Py_ssize_t refcnt;
|
|
|
4797 PyObject* op = (PyObject*)v;
|
|
|
4798
|
|
|
4799 refcnt = Py_REFCNT(op) < 0 ? 0 : Py_REFCNT(op);
|
|
|
4800 _Py_NewReference(op);
|
|
|
4801 /* _Py_NewReference sets the ref count to 1 but
|
|
|
4802 * the ref count might be larger. Set the refcnt
|
|
|
4803 * to the original refcnt + 1 */
|
|
|
4804 Py_REFCNT(op) = refcnt + 1;
|
|
|
4805 assert(Py_SIZE(op) == size);
|
|
|
4806 assert(v->ob_digit[0] == abs(ival));
|
|
|
4807 }
|
|
|
4808 else {
|
|
|
4809 PyObject_INIT(v, &PyLong_Type);
|
|
|
4810 }
|
|
|
4811 Py_SIZE(v) = size;
|
|
|
4812 v->ob_digit[0] = abs(ival);
|
|
|
4813 }
|
|
|
4814 #endif
|
|
|
4815 /* initialize int_info */
|
|
|
4816 if (Int_InfoType.tp_name == 0)
|
|
|
4817 PyStructSequence_InitType(&Int_InfoType, &int_info_desc);
|
|
|
4818
|
|
|
4819 return 1;
|
|
|
4820 }
|
|
|
4821
|
|
|
4822 void
|
|
|
4823 PyLong_Fini(void)
|
|
|
4824 {
|
|
|
4825 /* Integers are currently statically allocated. Py_DECREF is not
|
|
|
4826 needed, but Python must forget about the reference or multiple
|
|
|
4827 reinitializations will fail. */
|
|
|
4828 #if NSMALLNEGINTS + NSMALLPOSINTS > 0
|
|
|
4829 int i;
|
|
|
4830 PyLongObject *v = small_ints;
|
|
|
4831 for (i = 0; i < NSMALLNEGINTS + NSMALLPOSINTS; i++, v++) {
|
|
|
4832 _Py_DEC_REFTOTAL;
|
|
|
4833 _Py_ForgetReference((PyObject*)v);
|
|
|
4834 }
|
|
|
4835 #endif
|
|
|
4836 }
|
