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