summaryrefslogtreecommitdiffstats
path: root/Objects/longobject.c
diff options
context:
space:
mode:
Diffstat (limited to 'Objects/longobject.c')
-rw-r--r--Objects/longobject.c290
1 files changed, 246 insertions, 44 deletions
diff --git a/Objects/longobject.c b/Objects/longobject.c
index 7036c0e..40da0b1 100644
--- a/Objects/longobject.c
+++ b/Objects/longobject.c
@@ -21,7 +21,6 @@
Py_SIZE(x) < 0 ? -(sdigit)(x)->ob_digit[0] : \
(Py_SIZE(x) == 0 ? (sdigit)0 : \
(sdigit)(x)->ob_digit[0]))
-#define ABS(x) ((x) < 0 ? -(x) : (x))
#if NSMALLNEGINTS + NSMALLPOSINTS > 0
/* Small integers are preallocated in this array so that they
@@ -57,7 +56,7 @@ get_small_int(sdigit ival)
static PyLongObject *
maybe_small_long(PyLongObject *v)
{
- if (v && ABS(Py_SIZE(v)) <= 1) {
+ if (v && Py_ABS(Py_SIZE(v)) <= 1) {
sdigit ival = MEDIUM_VALUE(v);
if (-NSMALLNEGINTS <= ival && ival < NSMALLPOSINTS) {
Py_DECREF(v);
@@ -114,7 +113,7 @@ _PyLong_Negate(PyLongObject **x_p)
static PyLongObject *
long_normalize(PyLongObject *v)
{
- Py_ssize_t j = ABS(Py_SIZE(v));
+ Py_ssize_t j = Py_ABS(Py_SIZE(v));
Py_ssize_t i = j;
while (i > 0 && v->ob_digit[i-1] == 0)
@@ -718,7 +717,7 @@ _PyLong_NumBits(PyObject *vv)
assert(v != NULL);
assert(PyLong_Check(v));
- ndigits = ABS(Py_SIZE(v));
+ ndigits = Py_ABS(Py_SIZE(v));
assert(ndigits == 0 || v->ob_digit[ndigits - 1] != 0);
if (ndigits > 0) {
digit msd = v->ob_digit[ndigits - 1];
@@ -1565,7 +1564,7 @@ inplace_divrem1(digit *pout, digit *pin, Py_ssize_t size, digit n)
static PyLongObject *
divrem1(PyLongObject *a, digit n, digit *prem)
{
- const Py_ssize_t size = ABS(Py_SIZE(a));
+ const Py_ssize_t size = Py_ABS(Py_SIZE(a));
PyLongObject *z;
assert(n > 0 && n <= PyLong_MASK);
@@ -1597,7 +1596,7 @@ long_to_decimal_string_internal(PyObject *aa,
PyErr_BadInternalCall();
return -1;
}
- size_a = ABS(Py_SIZE(a));
+ size_a = Py_ABS(Py_SIZE(a));
negative = Py_SIZE(a) < 0;
/* quick and dirty upper bound for the number of digits
@@ -1766,7 +1765,7 @@ long_format_binary(PyObject *aa, int base, int alternate,
PyErr_BadInternalCall();
return -1;
}
- size_a = ABS(Py_SIZE(a));
+ size_a = Py_ABS(Py_SIZE(a));
negative = Py_SIZE(a) < 0;
/* Compute a rough upper bound for the length of the string */
@@ -2313,7 +2312,7 @@ _PyLong_FromBytes(const char *s, Py_ssize_t len, int base)
PyObject *result, *strobj;
char *end = NULL;
- result = PyLong_FromString((char*)s, &end, base);
+ result = PyLong_FromString(s, &end, base);
if (end == NULL || (result != NULL && end == s + len))
return result;
Py_XDECREF(result);
@@ -2380,7 +2379,7 @@ static int
long_divrem(PyLongObject *a, PyLongObject *b,
PyLongObject **pdiv, PyLongObject **prem)
{
- Py_ssize_t size_a = ABS(Py_SIZE(a)), size_b = ABS(Py_SIZE(b));
+ Py_ssize_t size_a = Py_ABS(Py_SIZE(a)), size_b = Py_ABS(Py_SIZE(b));
PyLongObject *z;
if (size_b == 0) {
@@ -2439,7 +2438,7 @@ long_divrem(PyLongObject *a, PyLongObject *b,
}
/* Unsigned int division with remainder -- the algorithm. The arguments v1
- and w1 should satisfy 2 <= ABS(Py_SIZE(w1)) <= ABS(Py_SIZE(v1)). */
+ and w1 should satisfy 2 <= Py_ABS(Py_SIZE(w1)) <= Py_ABS(Py_SIZE(v1)). */
static PyLongObject *
x_divrem(PyLongObject *v1, PyLongObject *w1, PyLongObject **prem)
@@ -2459,8 +2458,8 @@ x_divrem(PyLongObject *v1, PyLongObject *w1, PyLongObject **prem)
that won't overflow a digit. */
/* allocate space; w will also be used to hold the final remainder */
- size_v = ABS(Py_SIZE(v1));
- size_w = ABS(Py_SIZE(w1));
+ size_v = Py_ABS(Py_SIZE(v1));
+ size_w = Py_ABS(Py_SIZE(w1));
assert(size_v >= size_w && size_w >= 2); /* Assert checks by div() */
v = _PyLong_New(size_v+1);
if (v == NULL) {
@@ -2591,7 +2590,7 @@ _PyLong_Frexp(PyLongObject *a, Py_ssize_t *e)
multiple of 4, rounding ties to a multiple of 8. */
static const int half_even_correction[8] = {0, -1, -2, 1, 0, -1, 2, 1};
- a_size = ABS(Py_SIZE(a));
+ a_size = Py_ABS(Py_SIZE(a));
if (a_size == 0) {
/* Special case for 0: significand 0.0, exponent 0. */
*e = 0;
@@ -2732,7 +2731,7 @@ long_compare(PyLongObject *a, PyLongObject *b)
sign = Py_SIZE(a) - Py_SIZE(b);
}
else {
- Py_ssize_t i = ABS(Py_SIZE(a));
+ Py_ssize_t i = Py_ABS(Py_SIZE(a));
while (--i >= 0 && a->ob_digit[i] == b->ob_digit[i])
;
if (i < 0)
@@ -2850,7 +2849,7 @@ long_hash(PyLongObject *v)
static PyLongObject *
x_add(PyLongObject *a, PyLongObject *b)
{
- Py_ssize_t size_a = ABS(Py_SIZE(a)), size_b = ABS(Py_SIZE(b));
+ Py_ssize_t size_a = Py_ABS(Py_SIZE(a)), size_b = Py_ABS(Py_SIZE(b));
PyLongObject *z;
Py_ssize_t i;
digit carry = 0;
@@ -2884,7 +2883,7 @@ x_add(PyLongObject *a, PyLongObject *b)
static PyLongObject *
x_sub(PyLongObject *a, PyLongObject *b)
{
- Py_ssize_t size_a = ABS(Py_SIZE(a)), size_b = ABS(Py_SIZE(b));
+ Py_ssize_t size_a = Py_ABS(Py_SIZE(a)), size_b = Py_ABS(Py_SIZE(b));
PyLongObject *z;
Py_ssize_t i;
int sign = 1;
@@ -2944,7 +2943,7 @@ long_add(PyLongObject *a, PyLongObject *b)
CHECK_BINOP(a, b);
- if (ABS(Py_SIZE(a)) <= 1 && ABS(Py_SIZE(b)) <= 1) {
+ if (Py_ABS(Py_SIZE(a)) <= 1 && Py_ABS(Py_SIZE(b)) <= 1) {
PyObject *result = PyLong_FromLong(MEDIUM_VALUE(a) +
MEDIUM_VALUE(b));
return result;
@@ -2974,7 +2973,7 @@ long_sub(PyLongObject *a, PyLongObject *b)
CHECK_BINOP(a, b);
- if (ABS(Py_SIZE(a)) <= 1 && ABS(Py_SIZE(b)) <= 1) {
+ if (Py_ABS(Py_SIZE(a)) <= 1 && Py_ABS(Py_SIZE(b)) <= 1) {
PyObject* r;
r = PyLong_FromLong(MEDIUM_VALUE(a)-MEDIUM_VALUE(b));
return r;
@@ -3003,8 +3002,8 @@ static PyLongObject *
x_mul(PyLongObject *a, PyLongObject *b)
{
PyLongObject *z;
- Py_ssize_t size_a = ABS(Py_SIZE(a));
- Py_ssize_t size_b = ABS(Py_SIZE(b));
+ Py_ssize_t size_a = Py_ABS(Py_SIZE(a));
+ Py_ssize_t size_b = Py_ABS(Py_SIZE(b));
Py_ssize_t i;
z = _PyLong_New(size_a + size_b);
@@ -3098,7 +3097,7 @@ kmul_split(PyLongObject *n,
{
PyLongObject *hi, *lo;
Py_ssize_t size_lo, size_hi;
- const Py_ssize_t size_n = ABS(Py_SIZE(n));
+ const Py_ssize_t size_n = Py_ABS(Py_SIZE(n));
size_lo = Py_MIN(size_n, size);
size_hi = size_n - size_lo;
@@ -3127,8 +3126,8 @@ static PyLongObject *k_lopsided_mul(PyLongObject *a, PyLongObject *b);
static PyLongObject *
k_mul(PyLongObject *a, PyLongObject *b)
{
- Py_ssize_t asize = ABS(Py_SIZE(a));
- Py_ssize_t bsize = ABS(Py_SIZE(b));
+ Py_ssize_t asize = Py_ABS(Py_SIZE(a));
+ Py_ssize_t bsize = Py_ABS(Py_SIZE(b));
PyLongObject *ah = NULL;
PyLongObject *al = NULL;
PyLongObject *bh = NULL;
@@ -3348,8 +3347,8 @@ ah*bh and al*bl too.
static PyLongObject *
k_lopsided_mul(PyLongObject *a, PyLongObject *b)
{
- const Py_ssize_t asize = ABS(Py_SIZE(a));
- Py_ssize_t bsize = ABS(Py_SIZE(b));
+ const Py_ssize_t asize = Py_ABS(Py_SIZE(a));
+ Py_ssize_t bsize = Py_ABS(Py_SIZE(b));
Py_ssize_t nbdone; /* # of b digits already multiplied */
PyLongObject *ret;
PyLongObject *bslice = NULL;
@@ -3407,7 +3406,7 @@ long_mul(PyLongObject *a, PyLongObject *b)
CHECK_BINOP(a, b);
/* fast path for single-digit multiplication */
- if (ABS(Py_SIZE(a)) <= 1 && ABS(Py_SIZE(b)) <= 1) {
+ if (Py_ABS(Py_SIZE(a)) <= 1 && Py_ABS(Py_SIZE(b)) <= 1) {
stwodigits v = (stwodigits)(MEDIUM_VALUE(a)) * MEDIUM_VALUE(b);
#ifdef HAVE_LONG_LONG
return PyLong_FromLongLong((PY_LONG_LONG)v);
@@ -3614,8 +3613,8 @@ long_true_divide(PyObject *v, PyObject *w)
*/
/* Reduce to case where a and b are both positive. */
- a_size = ABS(Py_SIZE(a));
- b_size = ABS(Py_SIZE(b));
+ a_size = Py_ABS(Py_SIZE(a));
+ b_size = Py_ABS(Py_SIZE(b));
negate = (Py_SIZE(a) < 0) ^ (Py_SIZE(b) < 0);
if (b_size == 0) {
PyErr_SetString(PyExc_ZeroDivisionError,
@@ -3731,7 +3730,7 @@ long_true_divide(PyObject *v, PyObject *w)
inexact = 1;
Py_DECREF(rem);
}
- x_size = ABS(Py_SIZE(x));
+ x_size = Py_ABS(Py_SIZE(x));
assert(x_size > 0); /* result of division is never zero */
x_bits = (x_size-1)*PyLong_SHIFT+bits_in_digit(x->ob_digit[x_size-1]);
@@ -3841,7 +3840,7 @@ long_pow(PyObject *v, PyObject *w, PyObject *x)
if (Py_SIZE(b) < 0) { /* if exponent is negative */
if (c) {
- PyErr_SetString(PyExc_TypeError, "pow() 2nd argument "
+ PyErr_SetString(PyExc_ValueError, "pow() 2nd argument "
"cannot be negative when 3rd argument specified");
goto Error;
}
@@ -4003,7 +4002,7 @@ long_invert(PyLongObject *v)
/* Implement ~x as -(x+1) */
PyLongObject *x;
PyLongObject *w;
- if (ABS(Py_SIZE(v)) <=1)
+ if (Py_ABS(Py_SIZE(v)) <=1)
return PyLong_FromLong(-(MEDIUM_VALUE(v)+1));
w = (PyLongObject *)PyLong_FromLong(1L);
if (w == NULL)
@@ -4020,7 +4019,7 @@ static PyObject *
long_neg(PyLongObject *v)
{
PyLongObject *z;
- if (ABS(Py_SIZE(v)) <= 1)
+ if (Py_ABS(Py_SIZE(v)) <= 1)
return PyLong_FromLong(-MEDIUM_VALUE(v));
z = (PyLongObject *)_PyLong_Copy(v);
if (z != NULL)
@@ -4075,7 +4074,7 @@ long_rshift(PyLongObject *a, PyLongObject *b)
goto rshift_error;
}
wordshift = shiftby / PyLong_SHIFT;
- newsize = ABS(Py_SIZE(a)) - wordshift;
+ newsize = Py_ABS(Py_SIZE(a)) - wordshift;
if (newsize <= 0)
return PyLong_FromLong(0);
loshift = shiftby % PyLong_SHIFT;
@@ -4122,7 +4121,7 @@ long_lshift(PyObject *v, PyObject *w)
wordshift = shiftby / PyLong_SHIFT;
remshift = shiftby - wordshift * PyLong_SHIFT;
- oldsize = ABS(Py_SIZE(a));
+ oldsize = Py_ABS(Py_SIZE(a));
newsize = oldsize + wordshift;
if (remshift)
++newsize;
@@ -4183,7 +4182,7 @@ long_bitwise(PyLongObject *a,
result back to sign-magnitude at the end. */
/* If a is negative, replace it by its two's complement. */
- size_a = ABS(Py_SIZE(a));
+ size_a = Py_ABS(Py_SIZE(a));
nega = Py_SIZE(a) < 0;
if (nega) {
z = _PyLong_New(size_a);
@@ -4197,7 +4196,7 @@ long_bitwise(PyLongObject *a,
Py_INCREF(a);
/* Same for b. */
- size_b = ABS(Py_SIZE(b));
+ size_b = Py_ABS(Py_SIZE(b));
negb = Py_SIZE(b) < 0;
if (negb) {
z = _PyLong_New(size_b);
@@ -4328,6 +4327,211 @@ long_long(PyObject *v)
return v;
}
+PyObject *
+_PyLong_GCD(PyObject *aarg, PyObject *barg)
+{
+ PyLongObject *a, *b, *c = NULL, *d = NULL, *r;
+ stwodigits x, y, q, s, t, c_carry, d_carry;
+ stwodigits A, B, C, D, T;
+ int nbits, k;
+ Py_ssize_t size_a, size_b, alloc_a, alloc_b;
+ digit *a_digit, *b_digit, *c_digit, *d_digit, *a_end, *b_end;
+
+ a = (PyLongObject *)aarg;
+ b = (PyLongObject *)barg;
+ size_a = Py_SIZE(a);
+ size_b = Py_SIZE(b);
+ if (-2 <= size_a && size_a <= 2 && -2 <= size_b && size_b <= 2) {
+ Py_INCREF(a);
+ Py_INCREF(b);
+ goto simple;
+ }
+
+ /* Initial reduction: make sure that 0 <= b <= a. */
+ a = (PyLongObject *)long_abs(a);
+ if (a == NULL)
+ return NULL;
+ b = (PyLongObject *)long_abs(b);
+ if (b == NULL) {
+ Py_DECREF(a);
+ return NULL;
+ }
+ if (long_compare(a, b) < 0) {
+ r = a;
+ a = b;
+ b = r;
+ }
+ /* We now own references to a and b */
+
+ alloc_a = Py_SIZE(a);
+ alloc_b = Py_SIZE(b);
+ /* reduce until a fits into 2 digits */
+ while ((size_a = Py_SIZE(a)) > 2) {
+ nbits = bits_in_digit(a->ob_digit[size_a-1]);
+ /* extract top 2*PyLong_SHIFT bits of a into x, along with
+ corresponding bits of b into y */
+ size_b = Py_SIZE(b);
+ assert(size_b <= size_a);
+ if (size_b == 0) {
+ if (size_a < alloc_a) {
+ r = (PyLongObject *)_PyLong_Copy(a);
+ Py_DECREF(a);
+ }
+ else
+ r = a;
+ Py_DECREF(b);
+ Py_XDECREF(c);
+ Py_XDECREF(d);
+ return (PyObject *)r;
+ }
+ x = (((twodigits)a->ob_digit[size_a-1] << (2*PyLong_SHIFT-nbits)) |
+ ((twodigits)a->ob_digit[size_a-2] << (PyLong_SHIFT-nbits)) |
+ (a->ob_digit[size_a-3] >> nbits));
+
+ y = ((size_b >= size_a - 2 ? b->ob_digit[size_a-3] >> nbits : 0) |
+ (size_b >= size_a - 1 ? (twodigits)b->ob_digit[size_a-2] << (PyLong_SHIFT-nbits) : 0) |
+ (size_b >= size_a ? (twodigits)b->ob_digit[size_a-1] << (2*PyLong_SHIFT-nbits) : 0));
+
+ /* inner loop of Lehmer's algorithm; A, B, C, D never grow
+ larger than PyLong_MASK during the algorithm. */
+ A = 1; B = 0; C = 0; D = 1;
+ for (k=0;; k++) {
+ if (y-C == 0)
+ break;
+ q = (x+(A-1))/(y-C);
+ s = B+q*D;
+ t = x-q*y;
+ if (s > t)
+ break;
+ x = y; y = t;
+ t = A+q*C; A = D; B = C; C = s; D = t;
+ }
+
+ if (k == 0) {
+ /* no progress; do a Euclidean step */
+ if (l_divmod(a, b, NULL, &r) < 0)
+ goto error;
+ Py_DECREF(a);
+ a = b;
+ b = r;
+ alloc_a = alloc_b;
+ alloc_b = Py_SIZE(b);
+ continue;
+ }
+
+ /*
+ a, b = A*b-B*a, D*a-C*b if k is odd
+ a, b = A*a-B*b, D*b-C*a if k is even
+ */
+ if (k&1) {
+ T = -A; A = -B; B = T;
+ T = -C; C = -D; D = T;
+ }
+ if (c != NULL)
+ Py_SIZE(c) = size_a;
+ else if (Py_REFCNT(a) == 1) {
+ Py_INCREF(a);
+ c = a;
+ }
+ else {
+ alloc_a = size_a;
+ c = _PyLong_New(size_a);
+ if (c == NULL)
+ goto error;
+ }
+
+ if (d != NULL)
+ Py_SIZE(d) = size_a;
+ else if (Py_REFCNT(b) == 1 && size_a <= alloc_b) {
+ Py_INCREF(b);
+ d = b;
+ Py_SIZE(d) = size_a;
+ }
+ else {
+ alloc_b = size_a;
+ d = _PyLong_New(size_a);
+ if (d == NULL)
+ goto error;
+ }
+ a_end = a->ob_digit + size_a;
+ b_end = b->ob_digit + size_b;
+
+ /* compute new a and new b in parallel */
+ a_digit = a->ob_digit;
+ b_digit = b->ob_digit;
+ c_digit = c->ob_digit;
+ d_digit = d->ob_digit;
+ c_carry = 0;
+ d_carry = 0;
+ while (b_digit < b_end) {
+ c_carry += (A * *a_digit) - (B * *b_digit);
+ d_carry += (D * *b_digit++) - (C * *a_digit++);
+ *c_digit++ = (digit)(c_carry & PyLong_MASK);
+ *d_digit++ = (digit)(d_carry & PyLong_MASK);
+ c_carry >>= PyLong_SHIFT;
+ d_carry >>= PyLong_SHIFT;
+ }
+ while (a_digit < a_end) {
+ c_carry += A * *a_digit;
+ d_carry -= C * *a_digit++;
+ *c_digit++ = (digit)(c_carry & PyLong_MASK);
+ *d_digit++ = (digit)(d_carry & PyLong_MASK);
+ c_carry >>= PyLong_SHIFT;
+ d_carry >>= PyLong_SHIFT;
+ }
+ assert(c_carry == 0);
+ assert(d_carry == 0);
+
+ Py_INCREF(c);
+ Py_INCREF(d);
+ Py_DECREF(a);
+ Py_DECREF(b);
+ a = long_normalize(c);
+ b = long_normalize(d);
+ }
+ Py_XDECREF(c);
+ Py_XDECREF(d);
+
+simple:
+ assert(Py_REFCNT(a) > 0);
+ assert(Py_REFCNT(b) > 0);
+#if LONG_MAX >> 2*PyLong_SHIFT
+ /* a fits into a long, so b must too */
+ x = PyLong_AsLong((PyObject *)a);
+ y = PyLong_AsLong((PyObject *)b);
+#elif defined(PY_LONG_LONG) && PY_LLONG_MAX >> 2*PyLong_SHIFT
+ x = PyLong_AsLongLong((PyObject *)a);
+ y = PyLong_AsLongLong((PyObject *)b);
+#else
+# error "_PyLong_GCD"
+#endif
+ x = Py_ABS(x);
+ y = Py_ABS(y);
+ Py_DECREF(a);
+ Py_DECREF(b);
+
+ /* usual Euclidean algorithm for longs */
+ while (y != 0) {
+ t = y;
+ y = x % y;
+ x = t;
+ }
+#if LONG_MAX >> 2*PyLong_SHIFT
+ return PyLong_FromLong(x);
+#elif defined(PY_LONG_LONG) && PY_LLONG_MAX >> 2*PyLong_SHIFT
+ return PyLong_FromLongLong(x);
+#else
+# error "_PyLong_GCD"
+#endif
+
+error:
+ Py_DECREF(a);
+ Py_DECREF(b);
+ Py_XDECREF(c);
+ Py_XDECREF(d);
+ return NULL;
+}
+
static PyObject *
long_float(PyObject *v)
{
@@ -4630,7 +4834,7 @@ long_sizeof(PyLongObject *v)
{
Py_ssize_t res;
- res = offsetof(PyLongObject, ob_digit) + ABS(Py_SIZE(v))*sizeof(digit);
+ res = offsetof(PyLongObject, ob_digit) + Py_ABS(Py_SIZE(v))*sizeof(digit);
return PyLong_FromSsize_t(res);
}
@@ -4644,7 +4848,7 @@ long_bit_length(PyLongObject *v)
assert(v != NULL);
assert(PyLong_Check(v));
- ndigits = ABS(Py_SIZE(v));
+ ndigits = Py_ABS(Py_SIZE(v));
if (ndigits == 0)
return PyLong_FromLong(0);
@@ -4849,7 +5053,7 @@ long_from_bytes(PyTypeObject *type, PyObject *args, PyObject *kwds)
if (type != &PyLong_Type && PyType_IsSubtype(type, &PyLong_Type)) {
PyLongObject *newobj;
int i;
- Py_ssize_t n = ABS(Py_SIZE(long_obj));
+ Py_ssize_t n = Py_ABS(Py_SIZE(long_obj));
newobj = (PyLongObject *)type->tp_alloc(type, n);
if (newobj == NULL) {
@@ -4874,9 +5078,7 @@ PyDoc_STRVAR(long_from_bytes_doc,
\n\
Return the integer represented by the given array of bytes.\n\
\n\
-The bytes argument must either support the buffer protocol or be an\n\
-iterable object producing bytes. Bytes and bytearray are examples of\n\
-built-in objects that support the buffer protocol.\n\
+The bytes argument must be a bytes-like object (e.g. bytes or bytearray).\n\
\n\
The byteorder argument determines the byte order used to represent the\n\
integer. If byteorder is 'big', the most significant byte is at the\n\
@@ -5095,13 +5297,13 @@ _PyLong_Init(void)
* to the original refcnt + 1 */
Py_REFCNT(op) = refcnt + 1;
assert(Py_SIZE(op) == size);
- assert(v->ob_digit[0] == abs(ival));
+ assert(v->ob_digit[0] == (digit)abs(ival));
}
else {
(void)PyObject_INIT(v, &PyLong_Type);
}
Py_SIZE(v) = size;
- v->ob_digit[0] = abs(ival);
+ v->ob_digit[0] = (digit)abs(ival);
}
#endif
/* initialize int_info */
generated by cgit v0.12 at 2025-01-04 09:41:01 (GMT)