diff options
Diffstat (limited to 'Objects/longobject.c')
| -rw-r--r-- | Objects/longobject.c | 542 |
1 files changed, 393 insertions, 149 deletions
diff --git a/Objects/longobject.c b/Objects/longobject.c index 8510e90648..ad239ce84e 100644 --- a/Objects/longobject.c +++ b/Objects/longobject.c @@ -722,7 +722,7 @@ _PyLong_NumBits(PyObject *vv) assert(ndigits == 0 || v->ob_digit[ndigits - 1] != 0); if (ndigits > 0) { digit msd = v->ob_digit[ndigits - 1]; - if ((size_t)(ndigits - 1) > PY_SIZE_MAX / (size_t)PyLong_SHIFT) + if ((size_t)(ndigits - 1) > SIZE_MAX / (size_t)PyLong_SHIFT) goto Overflow; result = (size_t)(ndigits - 1) * (size_t)PyLong_SHIFT; do { @@ -990,16 +990,13 @@ PyObject * PyLong_FromVoidPtr(void *p) { #if SIZEOF_VOID_P <= SIZEOF_LONG - return PyLong_FromUnsignedLong((unsigned long)(Py_uintptr_t)p); + return PyLong_FromUnsignedLong((unsigned long)(uintptr_t)p); #else -#ifndef HAVE_LONG_LONG -# error "PyLong_FromVoidPtr: sizeof(void*) > sizeof(long), but no long long" -#endif #if SIZEOF_LONG_LONG < SIZEOF_VOID_P -# error "PyLong_FromVoidPtr: sizeof(PY_LONG_LONG) < sizeof(void*)" +# error "PyLong_FromVoidPtr: sizeof(long long) < sizeof(void*)" #endif - return PyLong_FromUnsignedLongLong((unsigned PY_LONG_LONG)(Py_uintptr_t)p); + return PyLong_FromUnsignedLongLong((unsigned long long)(uintptr_t)p); #endif /* SIZEOF_VOID_P <= SIZEOF_LONG */ } @@ -1018,13 +1015,10 @@ PyLong_AsVoidPtr(PyObject *vv) x = PyLong_AsUnsignedLong(vv); #else -#ifndef HAVE_LONG_LONG -# error "PyLong_AsVoidPtr: sizeof(void*) > sizeof(long), but no long long" -#endif #if SIZEOF_LONG_LONG < SIZEOF_VOID_P -# error "PyLong_AsVoidPtr: sizeof(PY_LONG_LONG) < sizeof(void*)" +# error "PyLong_AsVoidPtr: sizeof(long long) < sizeof(void*)" #endif - PY_LONG_LONG x; + long long x; if (PyLong_Check(vv) && _PyLong_Sign(vv) < 0) x = PyLong_AsLongLong(vv); @@ -1038,22 +1032,20 @@ PyLong_AsVoidPtr(PyObject *vv) return (void *)x; } -#ifdef HAVE_LONG_LONG - -/* Initial PY_LONG_LONG support by Chris Herborth (chrish@qnx.com), later +/* Initial long long support by Chris Herborth (chrish@qnx.com), later * rewritten to use the newer PyLong_{As,From}ByteArray API. */ -#define PY_ABS_LLONG_MIN (0-(unsigned PY_LONG_LONG)PY_LLONG_MIN) +#define PY_ABS_LLONG_MIN (0-(unsigned long long)PY_LLONG_MIN) -/* Create a new int object from a C PY_LONG_LONG int. */ +/* Create a new int object from a C long long int. */ PyObject * -PyLong_FromLongLong(PY_LONG_LONG ival) +PyLong_FromLongLong(long long ival) { PyLongObject *v; - unsigned PY_LONG_LONG abs_ival; - unsigned PY_LONG_LONG t; /* unsigned so >> doesn't propagate sign bit */ + unsigned long long abs_ival; + unsigned long long t; /* unsigned so >> doesn't propagate sign bit */ int ndigits = 0; int negative = 0; @@ -1061,11 +1053,11 @@ PyLong_FromLongLong(PY_LONG_LONG ival) if (ival < 0) { /* avoid signed overflow on negation; see comments in PyLong_FromLong above. */ - abs_ival = (unsigned PY_LONG_LONG)(-1-ival) + 1; + abs_ival = (unsigned long long)(-1-ival) + 1; negative = 1; } else { - abs_ival = (unsigned PY_LONG_LONG)ival; + abs_ival = (unsigned long long)ival; } /* Count the number of Python digits. @@ -1090,19 +1082,19 @@ PyLong_FromLongLong(PY_LONG_LONG ival) return (PyObject *)v; } -/* Create a new int object from a C unsigned PY_LONG_LONG int. */ +/* Create a new int object from a C unsigned long long int. */ PyObject * -PyLong_FromUnsignedLongLong(unsigned PY_LONG_LONG ival) +PyLong_FromUnsignedLongLong(unsigned long long ival) { PyLongObject *v; - unsigned PY_LONG_LONG t; + unsigned long long t; int ndigits = 0; if (ival < PyLong_BASE) return PyLong_FromLong((long)ival); /* Count the number of Python digits. */ - t = (unsigned PY_LONG_LONG)ival; + t = (unsigned long long)ival; while (t) { ++ndigits; t >>= PyLong_SHIFT; @@ -1191,11 +1183,11 @@ PyLong_FromSize_t(size_t ival) /* Get a C long long int from an int object or any object that has an __int__ method. Return -1 and set an error if overflow occurs. */ -PY_LONG_LONG +long long PyLong_AsLongLong(PyObject *vv) { PyLongObject *v; - PY_LONG_LONG bytes; + long long bytes; int res; int do_decref = 0; /* if nb_int was called */ @@ -1233,30 +1225,30 @@ PyLong_AsLongLong(PyObject *vv) Py_DECREF(v); } - /* Plan 9 can't handle PY_LONG_LONG in ? : expressions */ + /* Plan 9 can't handle long long in ? : expressions */ if (res < 0) - return (PY_LONG_LONG)-1; + return (long long)-1; else return bytes; } -/* Get a C unsigned PY_LONG_LONG int from an int object. +/* Get a C unsigned long long int from an int object. Return -1 and set an error if overflow occurs. */ -unsigned PY_LONG_LONG +unsigned long long PyLong_AsUnsignedLongLong(PyObject *vv) { PyLongObject *v; - unsigned PY_LONG_LONG bytes; + unsigned long long bytes; int res; if (vv == NULL) { PyErr_BadInternalCall(); - return (unsigned PY_LONG_LONG)-1; + return (unsigned long long)-1; } if (!PyLong_Check(vv)) { PyErr_SetString(PyExc_TypeError, "an integer is required"); - return (unsigned PY_LONG_LONG)-1; + return (unsigned long long)-1; } v = (PyLongObject*)vv; @@ -1268,9 +1260,9 @@ PyLong_AsUnsignedLongLong(PyObject *vv) res = _PyLong_AsByteArray((PyLongObject *)vv, (unsigned char *)&bytes, SIZEOF_LONG_LONG, PY_LITTLE_ENDIAN, 0); - /* Plan 9 can't handle PY_LONG_LONG in ? : expressions */ + /* Plan 9 can't handle long long in ? : expressions */ if (res < 0) - return (unsigned PY_LONG_LONG)res; + return (unsigned long long)res; else return bytes; } @@ -1278,11 +1270,11 @@ PyLong_AsUnsignedLongLong(PyObject *vv) /* Get a C unsigned long int from an int object, ignoring the high bits. Returns -1 and sets an error condition if an error occurs. */ -static unsigned PY_LONG_LONG +static unsigned long long _PyLong_AsUnsignedLongLongMask(PyObject *vv) { PyLongObject *v; - unsigned PY_LONG_LONG x; + unsigned long long x; Py_ssize_t i; int sign; @@ -1308,11 +1300,11 @@ _PyLong_AsUnsignedLongLongMask(PyObject *vv) return x * sign; } -unsigned PY_LONG_LONG +unsigned long long PyLong_AsUnsignedLongLongMask(PyObject *op) { PyLongObject *lo; - unsigned PY_LONG_LONG val; + unsigned long long val; if (op == NULL) { PyErr_BadInternalCall(); @@ -1325,7 +1317,7 @@ PyLong_AsUnsignedLongLongMask(PyObject *op) lo = _PyLong_FromNbInt(op); if (lo == NULL) - return (unsigned PY_LONG_LONG)-1; + return (unsigned long long)-1; val = _PyLong_AsUnsignedLongLongMask((PyObject *)lo); Py_DECREF(lo); @@ -1342,13 +1334,13 @@ PyLong_AsUnsignedLongLongMask(PyObject *op) In this case *overflow will be 0. */ -PY_LONG_LONG +long long PyLong_AsLongLongAndOverflow(PyObject *vv, int *overflow) { /* This version by Tim Peters */ PyLongObject *v; - unsigned PY_LONG_LONG x, prev; - PY_LONG_LONG res; + unsigned long long x, prev; + long long res; Py_ssize_t i; int sign; int do_decref = 0; /* if nb_int was called */ @@ -1400,8 +1392,8 @@ PyLong_AsLongLongAndOverflow(PyObject *vv, int *overflow) /* Haven't lost any bits, but casting to long requires extra * care (see comment above). */ - if (x <= (unsigned PY_LONG_LONG)PY_LLONG_MAX) { - res = (PY_LONG_LONG)x * sign; + if (x <= (unsigned long long)PY_LLONG_MAX) { + res = (long long)x * sign; } else if (sign < 0 && x == PY_ABS_LLONG_MIN) { res = PY_LLONG_MIN; @@ -1418,8 +1410,6 @@ PyLong_AsLongLongAndOverflow(PyObject *vv, int *overflow) return res; } -#endif /* HAVE_LONG_LONG */ - #define CHECK_BINOP(v,w) \ do { \ if (!PyLong_Check(v) || !PyLong_Check(w)) \ @@ -1583,13 +1573,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; @@ -1607,15 +1600,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; @@ -1663,7 +1658,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'); @@ -1674,13 +1675,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++) { \ @@ -1700,6 +1696,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) \ @@ -1709,25 +1715,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; @@ -1739,7 +1754,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; } @@ -1751,10 +1766,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; @@ -1811,7 +1827,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'); @@ -1820,13 +1840,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'; \ } \ @@ -1861,30 +1876,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; @@ -1898,9 +1933,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; @@ -1912,9 +1947,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, + 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 - return long_format_binary(obj, base, alternate, NULL, writer); + 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. @@ -1948,12 +2005,18 @@ unsigned char _PyLong_DigitValue[256] = { * non-digit (which may be *str!). A normalized int is returned. * The point to this routine is that it takes time linear in the number of * string characters. + * + * Return values: + * -1 on syntax error (exception needs to be set, *res is untouched) + * 0 else (exception may be set, in that case *res is set to NULL) */ -static PyLongObject * -long_from_binary_base(const char **str, int base) +static int +long_from_binary_base(const char **str, int base, PyLongObject **res) { const char *p = *str; const char *start = p; + char prev = 0; + int digits = 0; int bits_per_char; Py_ssize_t n; PyLongObject *z; @@ -1963,23 +2026,43 @@ long_from_binary_base(const char **str, int base) assert(base >= 2 && base <= 32 && (base & (base - 1)) == 0); n = base; - for (bits_per_char = -1; n; ++bits_per_char) + for (bits_per_char = -1; n; ++bits_per_char) { n >>= 1; - /* n <- total # of bits needed, while setting p to end-of-string */ - while (_PyLong_DigitValue[Py_CHARMASK(*p)] < base) + } + /* count digits and set p to end-of-string */ + while (_PyLong_DigitValue[Py_CHARMASK(*p)] < base || *p == '_') { + if (*p == '_') { + if (prev == '_') { + *str = p - 1; + return -1; + } + } else { + ++digits; + } + prev = *p; ++p; + } + if (prev == '_') { + /* Trailing underscore not allowed. */ + *str = p - 1; + return -1; + } + *str = p; /* n <- # of Python digits needed, = ceiling(n/PyLong_SHIFT). */ - n = (p - start) * bits_per_char + PyLong_SHIFT - 1; + n = digits * bits_per_char + PyLong_SHIFT - 1; if (n / bits_per_char < p - start) { PyErr_SetString(PyExc_ValueError, "int string too large to convert"); - return NULL; + *res = NULL; + return 0; } n = n / PyLong_SHIFT; z = _PyLong_New(n); - if (z == NULL) - return NULL; + if (z == NULL) { + *res = NULL; + return 0; + } /* Read string from right, and fill in int from left; i.e., * from least to most significant in both. */ @@ -1987,7 +2070,11 @@ long_from_binary_base(const char **str, int base) bits_in_accum = 0; pdigit = z->ob_digit; while (--p >= start) { - int k = (int)_PyLong_DigitValue[Py_CHARMASK(*p)]; + int k; + if (*p == '_') { + continue; + } + k = (int)_PyLong_DigitValue[Py_CHARMASK(*p)]; assert(k >= 0 && k < base); accum |= (twodigits)k << bits_in_accum; bits_in_accum += bits_per_char; @@ -2006,7 +2093,8 @@ long_from_binary_base(const char **str, int base) } while (pdigit - z->ob_digit < n) *pdigit++ = 0; - return long_normalize(z); + *res = long_normalize(z); + return 0; } /* Parses an int from a bytestring. Leading and trailing whitespace will be @@ -2031,23 +2119,29 @@ PyLong_FromString(const char *str, char **pend, int base) "int() arg 2 must be >= 2 and <= 36"); return NULL; } - while (*str != '\0' && Py_ISSPACE(Py_CHARMASK(*str))) + while (*str != '\0' && Py_ISSPACE(Py_CHARMASK(*str))) { str++; - if (*str == '+') + } + if (*str == '+') { ++str; + } else if (*str == '-') { ++str; sign = -1; } if (base == 0) { - if (str[0] != '0') + if (str[0] != '0') { base = 10; - else if (str[1] == 'x' || str[1] == 'X') + } + else if (str[1] == 'x' || str[1] == 'X') { base = 16; - else if (str[1] == 'o' || str[1] == 'O') + } + else if (str[1] == 'o' || str[1] == 'O') { base = 8; - else if (str[1] == 'b' || str[1] == 'B') + } + else if (str[1] == 'b' || str[1] == 'B') { base = 2; + } else { /* "old" (C-style) octal literal, now invalid. it might still be zero though */ @@ -2058,12 +2152,26 @@ PyLong_FromString(const char *str, char **pend, int base) if (str[0] == '0' && ((base == 16 && (str[1] == 'x' || str[1] == 'X')) || (base == 8 && (str[1] == 'o' || str[1] == 'O')) || - (base == 2 && (str[1] == 'b' || str[1] == 'B')))) + (base == 2 && (str[1] == 'b' || str[1] == 'B')))) { str += 2; + /* One underscore allowed here. */ + if (*str == '_') { + ++str; + } + } + if (str[0] == '_') { + /* May not start with underscores. */ + goto onError; + } start = str; - if ((base & (base - 1)) == 0) - z = long_from_binary_base(&str, base); + if ((base & (base - 1)) == 0) { + int res = long_from_binary_base(&str, base, &z); + if (res < 0) { + /* Syntax error. */ + goto onError; + } + } else { /*** Binary bases can be converted in time linear in the number of digits, because @@ -2152,11 +2260,13 @@ digit beyond the first. ***/ twodigits c; /* current input character */ Py_ssize_t size_z; + int digits = 0; int i; int convwidth; twodigits convmultmax, convmult; digit *pz, *pzstop; - const char* scan; + const char *scan, *lastdigit; + char prev = 0; static double log_base_BASE[37] = {0.0e0,}; static int convwidth_base[37] = {0,}; @@ -2170,8 +2280,9 @@ digit beyond the first. log((double)PyLong_BASE)); for (;;) { twodigits next = convmax * base; - if (next > PyLong_BASE) + if (next > PyLong_BASE) { break; + } convmax = next; ++i; } @@ -2182,21 +2293,43 @@ digit beyond the first. /* Find length of the string of numeric characters. */ scan = str; - while (_PyLong_DigitValue[Py_CHARMASK(*scan)] < base) + lastdigit = str; + + while (_PyLong_DigitValue[Py_CHARMASK(*scan)] < base || *scan == '_') { + if (*scan == '_') { + if (prev == '_') { + /* Only one underscore allowed. */ + str = lastdigit + 1; + goto onError; + } + } + else { + ++digits; + lastdigit = scan; + } + prev = *scan; ++scan; + } + if (prev == '_') { + /* Trailing underscore not allowed. */ + /* Set error pointer to first underscore. */ + str = lastdigit + 1; + goto onError; + } /* Create an int object that can contain the largest possible * integer with this base and length. Note that there's no * need to initialize z->ob_digit -- no slot is read up before * being stored into. */ - size_z = (Py_ssize_t)((scan - str) * log_base_BASE[base]) + 1; + size_z = (Py_ssize_t)(digits * log_base_BASE[base]) + 1; /* Uncomment next line to test exceedingly rare copy code */ /* size_z = 1; */ assert(size_z > 0); z = _PyLong_New(size_z); - if (z == NULL) + if (z == NULL) { return NULL; + } Py_SIZE(z) = 0; /* `convwidth` consecutive input digits are treated as a single @@ -2207,9 +2340,17 @@ digit beyond the first. /* Work ;-) */ while (str < scan) { + if (*str == '_') { + str++; + continue; + } /* grab up to convwidth digits from the input string */ c = (digit)_PyLong_DigitValue[Py_CHARMASK(*str++)]; - for (i = 1; i < convwidth && str != scan; ++i, ++str) { + for (i = 1; i < convwidth && str != scan; ++str) { + if (*str == '_') { + continue; + } + i++; c = (twodigits)(c * base + (int)_PyLong_DigitValue[Py_CHARMASK(*str)]); assert(c < PyLong_BASE); @@ -2221,8 +2362,9 @@ digit beyond the first. */ if (i != convwidth) { convmult = base; - for ( ; i > 1; --i) + for ( ; i > 1; --i) { convmult *= base; + } } /* Multiply z by convmult, and add c. */ @@ -2260,41 +2402,51 @@ digit beyond the first. } } } - if (z == NULL) + if (z == NULL) { return NULL; + } if (error_if_nonzero) { /* reset the base to 0, else the exception message doesn't make too much sense */ base = 0; - if (Py_SIZE(z) != 0) + if (Py_SIZE(z) != 0) { goto onError; + } /* there might still be other problems, therefore base remains zero here for the same reason */ } - if (str == start) + if (str == start) { goto onError; - if (sign < 0) + } + if (sign < 0) { Py_SIZE(z) = -(Py_SIZE(z)); - while (*str && Py_ISSPACE(Py_CHARMASK(*str))) + } + while (*str && Py_ISSPACE(Py_CHARMASK(*str))) { str++; - if (*str != '\0') + } + if (*str != '\0') { goto onError; + } long_normalize(z); z = maybe_small_long(z); - if (z == NULL) + if (z == NULL) { return NULL; - if (pend != NULL) + } + if (pend != NULL) { *pend = (char *)str; + } return (PyObject *) z; onError: - if (pend != NULL) + if (pend != NULL) { *pend = (char *)str; + } Py_XDECREF(z); slen = strlen(orig_str) < 200 ? strlen(orig_str) : 200; strobj = PyUnicode_FromStringAndSize(orig_str, slen); - if (strobj == NULL) + if (strobj == NULL) { return NULL; + } PyErr_Format(PyExc_ValueError, "invalid literal for int() with base %d: %.200R", base, strobj); @@ -2395,8 +2547,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) { @@ -2706,6 +2861,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, @@ -2930,9 +3092,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); } @@ -2952,8 +3112,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); @@ -2984,8 +3150,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) @@ -3409,17 +3577,7 @@ long_mul(PyLongObject *a, PyLongObject *b) /* fast path for single-digit multiplication */ 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); -#else - /* if we don't have long long then we're almost certainly - using 15-bit digits, so v will fit in a long. In the - unlikely event that we're using 30-bit digits on a platform - without long long, a large v will just cause us to fall - through to the general multiplication code below. */ - if (v >= LONG_MIN && v <= LONG_MAX) - return PyLong_FromLong((long)v); -#endif + return PyLong_FromLongLong((long long)v); } z = k_mul(a, b); @@ -3432,6 +3590,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 @@ -3459,6 +3663,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) || @@ -3503,6 +3731,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; @@ -3742,9 +3975,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]; @@ -3778,6 +4011,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; @@ -4012,8 +4249,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 * @@ -4118,6 +4357,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; @@ -4502,7 +4746,7 @@ simple: /* 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 >> PyLong_SHIFT >> PyLong_SHIFT +#elif PY_LLONG_MAX >> PyLong_SHIFT >> PyLong_SHIFT x = PyLong_AsLongLong((PyObject *)a); y = PyLong_AsLongLong((PyObject *)b); #else @@ -4521,7 +4765,7 @@ simple: } #if LONG_MAX >> PyLong_SHIFT >> PyLong_SHIFT return PyLong_FromLong(x); -#elif defined(PY_LONG_LONG) && PY_LLONG_MAX >> PyLong_SHIFT >> PyLong_SHIFT +#elif PY_LLONG_MAX >> PyLong_SHIFT >> PyLong_SHIFT return PyLong_FromLongLong(x); #else # error "_PyLong_GCD" |