diff options
Diffstat (limited to 'Objects/longobject.c')
-rw-r--r-- | Objects/longobject.c | 271 |
1 files changed, 220 insertions, 51 deletions
diff --git a/Objects/longobject.c b/Objects/longobject.c index cd04e361d4c..4ace778530d 100644 --- a/Objects/longobject.c +++ b/Objects/longobject.c @@ -368,7 +368,7 @@ PyLong_FromDouble(double dval) /* Checking for overflow in PyLong_AsLong is a PITA since C doesn't define * anything about what happens when a signed integer operation overflows, * and some compilers think they're doing you a favor by being "clever" - * then. The bit pattern for the largest postive signed long is + * then. The bit pattern for the largest positive signed long is * (unsigned long)LONG_MAX, and for the smallest negative signed long * it is abs(LONG_MIN), which we could write -(unsigned long)LONG_MIN. * However, some other compilers warn about applying unary minus to an @@ -1582,13 +1582,16 @@ divrem1(PyLongObject *a, digit n, digit *prem) static int long_to_decimal_string_internal(PyObject *aa, PyObject **p_output, - _PyUnicodeWriter *writer) + _PyUnicodeWriter *writer, + _PyBytesWriter *bytes_writer, + char **bytes_str) { PyLongObject *scratch, *a; - PyObject *str; + PyObject *str = NULL; Py_ssize_t size, strlen, size_a, i, j; digit *pout, *pin, rem, tenpow; int negative; + int d; enum PyUnicode_Kind kind; a = (PyLongObject *)aa; @@ -1606,15 +1609,17 @@ long_to_decimal_string_internal(PyObject *aa, But log2(a) < size_a * PyLong_SHIFT, and log2(_PyLong_DECIMAL_BASE) = log2(10) * _PyLong_DECIMAL_SHIFT - > 3 * _PyLong_DECIMAL_SHIFT + > 3.3 * _PyLong_DECIMAL_SHIFT + + size_a * PyLong_SHIFT / (3.3 * _PyLong_DECIMAL_SHIFT) = + size_a + size_a / d < size_a + size_a / floor(d), + where d = (3.3 * _PyLong_DECIMAL_SHIFT) / + (PyLong_SHIFT - 3.3 * _PyLong_DECIMAL_SHIFT) */ - if (size_a > PY_SSIZE_T_MAX / PyLong_SHIFT) { - PyErr_SetString(PyExc_OverflowError, - "int too large to format"); - return -1; - } - /* the expression size_a * PyLong_SHIFT is now safe from overflow */ - size = 1 + size_a * PyLong_SHIFT / (3 * _PyLong_DECIMAL_SHIFT); + d = (33 * _PyLong_DECIMAL_SHIFT) / + (10 * PyLong_SHIFT - 33 * _PyLong_DECIMAL_SHIFT); + assert(size_a < PY_SSIZE_T_MAX/2); + size = 1 + size_a + size_a / d; scratch = _PyLong_New(size); if (scratch == NULL) return -1; @@ -1662,7 +1667,13 @@ long_to_decimal_string_internal(PyObject *aa, return -1; } kind = writer->kind; - str = NULL; + } + else if (bytes_writer) { + *bytes_str = _PyBytesWriter_Prepare(bytes_writer, *bytes_str, strlen); + if (*bytes_str == NULL) { + Py_DECREF(scratch); + return -1; + } } else { str = PyUnicode_New(strlen, '9'); @@ -1673,13 +1684,8 @@ long_to_decimal_string_internal(PyObject *aa, kind = PyUnicode_KIND(str); } -#define WRITE_DIGITS(TYPE) \ +#define WRITE_DIGITS(p) \ do { \ - if (writer) \ - p = (TYPE*)PyUnicode_DATA(writer->buffer) + writer->pos + strlen; \ - else \ - p = (TYPE*)PyUnicode_DATA(str) + strlen; \ - \ /* pout[0] through pout[size-2] contribute exactly \ _PyLong_DECIMAL_SHIFT digits each */ \ for (i=0; i < size - 1; i++) { \ @@ -1699,6 +1705,16 @@ long_to_decimal_string_internal(PyObject *aa, /* and sign */ \ if (negative) \ *--p = '-'; \ + } while (0) + +#define WRITE_UNICODE_DIGITS(TYPE) \ + do { \ + if (writer) \ + p = (TYPE*)PyUnicode_DATA(writer->buffer) + writer->pos + strlen; \ + else \ + p = (TYPE*)PyUnicode_DATA(str) + strlen; \ + \ + WRITE_DIGITS(p); \ \ /* check we've counted correctly */ \ if (writer) \ @@ -1708,25 +1724,34 @@ long_to_decimal_string_internal(PyObject *aa, } while (0) /* fill the string right-to-left */ - if (kind == PyUnicode_1BYTE_KIND) { + if (bytes_writer) { + char *p = *bytes_str + strlen; + WRITE_DIGITS(p); + assert(p == *bytes_str); + } + else if (kind == PyUnicode_1BYTE_KIND) { Py_UCS1 *p; - WRITE_DIGITS(Py_UCS1); + WRITE_UNICODE_DIGITS(Py_UCS1); } else if (kind == PyUnicode_2BYTE_KIND) { Py_UCS2 *p; - WRITE_DIGITS(Py_UCS2); + WRITE_UNICODE_DIGITS(Py_UCS2); } else { Py_UCS4 *p; assert (kind == PyUnicode_4BYTE_KIND); - WRITE_DIGITS(Py_UCS4); + WRITE_UNICODE_DIGITS(Py_UCS4); } #undef WRITE_DIGITS +#undef WRITE_UNICODE_DIGITS Py_DECREF(scratch); if (writer) { writer->pos += strlen; } + else if (bytes_writer) { + (*bytes_str) += strlen; + } else { assert(_PyUnicode_CheckConsistency(str, 1)); *p_output = (PyObject *)str; @@ -1738,7 +1763,7 @@ static PyObject * long_to_decimal_string(PyObject *aa) { PyObject *v; - if (long_to_decimal_string_internal(aa, &v, NULL) == -1) + if (long_to_decimal_string_internal(aa, &v, NULL, NULL, NULL) == -1) return NULL; return v; } @@ -1750,10 +1775,11 @@ long_to_decimal_string(PyObject *aa) static int long_format_binary(PyObject *aa, int base, int alternate, - PyObject **p_output, _PyUnicodeWriter *writer) + PyObject **p_output, _PyUnicodeWriter *writer, + _PyBytesWriter *bytes_writer, char **bytes_str) { PyLongObject *a = (PyLongObject *)aa; - PyObject *v; + PyObject *v = NULL; Py_ssize_t sz; Py_ssize_t size_a; enum PyUnicode_Kind kind; @@ -1810,7 +1836,11 @@ long_format_binary(PyObject *aa, int base, int alternate, if (_PyUnicodeWriter_Prepare(writer, sz, 'x') == -1) return -1; kind = writer->kind; - v = NULL; + } + else if (bytes_writer) { + *bytes_str = _PyBytesWriter_Prepare(bytes_writer, *bytes_str, sz); + if (*bytes_str == NULL) + return -1; } else { v = PyUnicode_New(sz, 'x'); @@ -1819,13 +1849,8 @@ long_format_binary(PyObject *aa, int base, int alternate, kind = PyUnicode_KIND(v); } -#define WRITE_DIGITS(TYPE) \ +#define WRITE_DIGITS(p) \ do { \ - if (writer) \ - p = (TYPE*)PyUnicode_DATA(writer->buffer) + writer->pos + sz; \ - else \ - p = (TYPE*)PyUnicode_DATA(v) + sz; \ - \ if (size_a == 0) { \ *--p = '0'; \ } \ @@ -1860,30 +1885,50 @@ long_format_binary(PyObject *aa, int base, int alternate, } \ if (negative) \ *--p = '-'; \ + } while (0) + +#define WRITE_UNICODE_DIGITS(TYPE) \ + do { \ + if (writer) \ + p = (TYPE*)PyUnicode_DATA(writer->buffer) + writer->pos + sz; \ + else \ + p = (TYPE*)PyUnicode_DATA(v) + sz; \ + \ + WRITE_DIGITS(p); \ + \ if (writer) \ assert(p == ((TYPE*)PyUnicode_DATA(writer->buffer) + writer->pos)); \ else \ assert(p == (TYPE*)PyUnicode_DATA(v)); \ } while (0) - if (kind == PyUnicode_1BYTE_KIND) { + if (bytes_writer) { + char *p = *bytes_str + sz; + WRITE_DIGITS(p); + assert(p == *bytes_str); + } + else if (kind == PyUnicode_1BYTE_KIND) { Py_UCS1 *p; - WRITE_DIGITS(Py_UCS1); + WRITE_UNICODE_DIGITS(Py_UCS1); } else if (kind == PyUnicode_2BYTE_KIND) { Py_UCS2 *p; - WRITE_DIGITS(Py_UCS2); + WRITE_UNICODE_DIGITS(Py_UCS2); } else { Py_UCS4 *p; assert (kind == PyUnicode_4BYTE_KIND); - WRITE_DIGITS(Py_UCS4); + WRITE_UNICODE_DIGITS(Py_UCS4); } #undef WRITE_DIGITS +#undef WRITE_UNICODE_DIGITS if (writer) { writer->pos += sz; } + else if (bytes_writer) { + (*bytes_str) += sz; + } else { assert(_PyUnicode_CheckConsistency(v, 1)); *p_output = v; @@ -1897,9 +1942,9 @@ _PyLong_Format(PyObject *obj, int base) PyObject *str; int err; if (base == 10) - err = long_to_decimal_string_internal(obj, &str, NULL); + err = long_to_decimal_string_internal(obj, &str, NULL, NULL, NULL); else - err = long_format_binary(obj, base, 1, &str, NULL); + err = long_format_binary(obj, base, 1, &str, NULL, NULL, NULL); if (err == -1) return NULL; return str; @@ -1911,9 +1956,31 @@ _PyLong_FormatWriter(_PyUnicodeWriter *writer, int base, int alternate) { if (base == 10) - return long_to_decimal_string_internal(obj, NULL, writer); + return long_to_decimal_string_internal(obj, NULL, writer, + NULL, NULL); else - return long_format_binary(obj, base, alternate, NULL, writer); + return long_format_binary(obj, base, alternate, NULL, writer, + NULL, NULL); +} + +char* +_PyLong_FormatBytesWriter(_PyBytesWriter *writer, char *str, + PyObject *obj, + int base, int alternate) +{ + char *str2; + int res; + str2 = str; + if (base == 10) + res = long_to_decimal_string_internal(obj, NULL, NULL, + writer, &str2); + else + res = long_format_binary(obj, base, alternate, NULL, NULL, + writer, &str2); + if (res < 0) + return NULL; + assert(str2 != NULL); + return str2; } /* Table of digit values for 8-bit string -> integer conversion. @@ -2394,8 +2461,11 @@ long_divrem(PyLongObject *a, PyLongObject *b, *pdiv = (PyLongObject*)PyLong_FromLong(0); if (*pdiv == NULL) return -1; - Py_INCREF(a); - *prem = (PyLongObject *) a; + *prem = (PyLongObject *)long_long((PyObject *)a); + if (*prem == NULL) { + Py_CLEAR(*pdiv); + return -1; + } return 0; } if (size_b == 1) { @@ -2705,6 +2775,13 @@ PyLong_AsDouble(PyObject *v) PyErr_SetString(PyExc_TypeError, "an integer is required"); return -1.0; } + if (Py_ABS(Py_SIZE(v)) <= 1) { + /* Fast path; single digit long (31 bits) will cast safely + to double. This improves performance of FP/long operations + by 20%. + */ + return (double)MEDIUM_VALUE((PyLongObject *)v); + } x = _PyLong_Frexp((PyLongObject *)v, &exponent); if ((x == -1.0 && PyErr_Occurred()) || exponent > DBL_MAX_EXP) { PyErr_SetString(PyExc_OverflowError, @@ -2929,9 +3006,7 @@ x_sub(PyLongObject *a, PyLongObject *b) } assert(borrow == 0); if (sign < 0) { - _PyLong_Negate(&z); - if (z == NULL) - return NULL; + Py_SIZE(z) = -Py_SIZE(z); } return long_normalize(z); } @@ -2951,8 +3026,14 @@ long_add(PyLongObject *a, PyLongObject *b) if (Py_SIZE(a) < 0) { if (Py_SIZE(b) < 0) { z = x_add(a, b); - if (z != NULL && Py_SIZE(z) != 0) + if (z != NULL) { + /* x_add received at least one multiple-digit int, + and thus z must be a multiple-digit int. + That also means z is not an element of + small_ints, so negating it in-place is safe. */ + assert(Py_REFCNT(z) == 1); Py_SIZE(z) = -(Py_SIZE(z)); + } } else z = x_sub(b, a); @@ -2983,8 +3064,10 @@ long_sub(PyLongObject *a, PyLongObject *b) z = x_sub(a, b); else z = x_add(a, b); - if (z != NULL && Py_SIZE(z) != 0) + if (z != NULL) { + assert(Py_SIZE(z) == 0 || Py_REFCNT(z) == 1); Py_SIZE(z) = -(Py_SIZE(z)); + } } else { if (Py_SIZE(b) < 0) @@ -3431,6 +3514,52 @@ long_mul(PyLongObject *a, PyLongObject *b) return (PyObject *)z; } +/* Fast modulo division for single-digit longs. */ +static PyObject * +fast_mod(PyLongObject *a, PyLongObject *b) +{ + sdigit left = a->ob_digit[0]; + sdigit right = b->ob_digit[0]; + sdigit mod; + + assert(Py_ABS(Py_SIZE(a)) == 1); + assert(Py_ABS(Py_SIZE(b)) == 1); + + if (Py_SIZE(a) == Py_SIZE(b)) { + /* 'a' and 'b' have the same sign. */ + mod = left % right; + } + else { + /* Either 'a' or 'b' is negative. */ + mod = right - 1 - (left - 1) % right; + } + + return PyLong_FromLong(mod * (sdigit)Py_SIZE(b)); +} + +/* Fast floor division for single-digit longs. */ +static PyObject * +fast_floor_div(PyLongObject *a, PyLongObject *b) +{ + sdigit left = a->ob_digit[0]; + sdigit right = b->ob_digit[0]; + sdigit div; + + assert(Py_ABS(Py_SIZE(a)) == 1); + assert(Py_ABS(Py_SIZE(b)) == 1); + + if (Py_SIZE(a) == Py_SIZE(b)) { + /* 'a' and 'b' have the same sign. */ + div = left / right; + } + else { + /* Either 'a' or 'b' is negative. */ + div = -1 - (left - 1) / right; + } + + return PyLong_FromLong(div); +} + /* The / and % operators are now defined in terms of divmod(). The expression a mod b has the value a - b*floor(a/b). The long_divrem function gives the remainder after division of @@ -3458,6 +3587,30 @@ l_divmod(PyLongObject *v, PyLongObject *w, { PyLongObject *div, *mod; + if (Py_ABS(Py_SIZE(v)) == 1 && Py_ABS(Py_SIZE(w)) == 1) { + /* Fast path for single-digit longs */ + div = NULL; + if (pdiv != NULL) { + div = (PyLongObject *)fast_floor_div(v, w); + if (div == NULL) { + return -1; + } + } + if (pmod != NULL) { + mod = (PyLongObject *)fast_mod(v, w); + if (mod == NULL) { + Py_XDECREF(div); + return -1; + } + *pmod = mod; + } + if (pdiv != NULL) { + /* We only want to set `*pdiv` when `*pmod` is + set successfully. */ + *pdiv = div; + } + return 0; + } if (long_divrem(v, w, &div, &mod) < 0) return -1; if ((Py_SIZE(mod) < 0 && Py_SIZE(w) > 0) || @@ -3502,6 +3655,11 @@ long_div(PyObject *a, PyObject *b) PyLongObject *div; CHECK_BINOP(a, b); + + if (Py_ABS(Py_SIZE(a)) == 1 && Py_ABS(Py_SIZE(b)) == 1) { + return fast_floor_div((PyLongObject*)a, (PyLongObject*)b); + } + if (l_divmod((PyLongObject*)a, (PyLongObject*)b, &div, NULL) < 0) div = NULL; return (PyObject *)div; @@ -3741,9 +3899,9 @@ long_true_divide(PyObject *v, PyObject *w) /* Round by directly modifying the low digit of x. */ mask = (digit)1 << (extra_bits - 1); low = x->ob_digit[0] | inexact; - if (low & mask && low & (3*mask-1)) + if ((low & mask) && (low & (3U*mask-1U))) low += mask; - x->ob_digit[0] = low & ~(mask-1U); + x->ob_digit[0] = low & ~(2U*mask-1U); /* Convert x to a double dx; the conversion is exact. */ dx = x->ob_digit[--x_size]; @@ -3777,6 +3935,10 @@ long_mod(PyObject *a, PyObject *b) CHECK_BINOP(a, b); + if (Py_ABS(Py_SIZE(a)) == 1 && Py_ABS(Py_SIZE(b)) == 1) { + return fast_mod((PyLongObject*)a, (PyLongObject*)b); + } + if (l_divmod((PyLongObject*)a, (PyLongObject*)b, NULL, &mod) < 0) mod = NULL; return (PyObject *)mod; @@ -4011,8 +4173,10 @@ long_invert(PyLongObject *v) Py_DECREF(w); if (x == NULL) return NULL; - Py_SIZE(x) = -(Py_SIZE(x)); - return (PyObject *)maybe_small_long(x); + _PyLong_Negate(&x); + /* No need for maybe_small_long here, since any small + longs will have been caught in the Py_SIZE <= 1 fast path. */ + return (PyObject *)x; } static PyObject * @@ -4117,6 +4281,11 @@ long_lshift(PyObject *v, PyObject *w) PyErr_SetString(PyExc_ValueError, "negative shift count"); return NULL; } + + if (Py_SIZE(a) == 0) { + return PyLong_FromLong(0); + } + /* wordshift, remshift = divmod(shiftby, PyLong_SHIFT) */ wordshift = shiftby / PyLong_SHIFT; remshift = shiftby - wordshift * PyLong_SHIFT; |