ยปCore Development>Code coverage>Objects/longobject.c

Python code coverage for Objects/longobject.c

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