Merged revisions 69634 via svnmerge from
svn+ssh://pythondev@svn.python.org/python/trunk
........
r69634 | mark.dickinson | 2009-02-15 10:13:41 +0000 (Sun, 15 Feb 2009) | 6 lines
Issue #5260: Various portability and standards compliance fixes, optimizations
and cleanups in Objects/longobject.c. The most significant change is that
longs now use less memory: average savings are 2 bytes per long on 32-bit
systems and 6 bytes per long on 64-bit systems. (This memory saving already
exists in py3k.)
........
diff --git a/Objects/longobject.c b/Objects/longobject.c
index e2ab078..4ab60a1 100644
--- a/Objects/longobject.c
+++ b/Objects/longobject.c
@@ -6,6 +6,7 @@
#include "longintrepr.h"
#include <ctype.h>
+#include <stddef.h>
#ifndef NSMALLPOSINTS
#define NSMALLPOSINTS 257
@@ -90,12 +91,6 @@
#define MAX(x, y) ((x) < (y) ? (y) : (x))
#define MIN(x, y) ((x) > (y) ? (y) : (x))
-/* Forward */
-static PyLongObject *long_normalize(PyLongObject *);
-static PyLongObject *mul1(PyLongObject *, wdigit);
-static PyLongObject *muladd1(PyLongObject *, wdigit, wdigit);
-static PyLongObject *divrem1(PyLongObject *, digit, digit *);
-
#define SIGCHECK(PyTryBlock) \
if (--_Py_Ticker < 0) { \
_Py_Ticker = _Py_CheckInterval; \
@@ -122,25 +117,29 @@
/* Allocate a new long int object with size digits.
Return NULL and set exception if we run out of memory. */
+#define MAX_LONG_DIGITS \
+ ((PY_SSIZE_T_MAX - offsetof(PyLongObject, ob_digit))/sizeof(digit))
+
PyLongObject *
_PyLong_New(Py_ssize_t size)
{
PyLongObject *result;
- /* Can't use sizeof(PyLongObject) here, since the
- compiler takes padding at the end into account.
- As the consequence, this would waste 2 bytes on
- a 32-bit system, and 6 bytes on a 64-bit system.
- This computation would be incorrect on systems
- which have padding before the digits; with 16-bit
- digits this should not happen. */
- result = PyObject_MALLOC(sizeof(PyVarObject) +
+ /* Number of bytes needed is: offsetof(PyLongObject, ob_digit) +
+ sizeof(digit)*size. Previous incarnations of this code used
+ sizeof(PyVarObject) instead of the offsetof, but this risks being
+ incorrect in the presence of padding between the PyVarObject header
+ and the digits. */
+ if (size > MAX_LONG_DIGITS) {
+ PyErr_SetString(PyExc_OverflowError,
+ "too many digits in integer");
+ return NULL;
+ }
+ result = PyObject_MALLOC(offsetof(PyLongObject, ob_digit) +
size*sizeof(digit));
if (!result) {
PyErr_NoMemory();
return NULL;
}
- /* XXX(nnorwitz): This can overflow --
- PyObject_NEW_VAR / _PyObject_VAR_SIZE need to detect overflow */
return (PyLongObject*)PyObject_INIT_VAR(result, &PyLong_Type, size);
}
@@ -297,8 +296,8 @@
return NULL;
frac = ldexp(frac, (expo-1) % PyLong_SHIFT + 1);
for (i = ndig; --i >= 0; ) {
- long bits = (long)frac;
- v->ob_digit[i] = (digit) bits;
+ digit bits = (digit)frac;
+ v->ob_digit[i] = bits;
frac = frac - (double)bits;
frac = ldexp(frac, PyLong_SHIFT);
}
@@ -667,9 +666,9 @@
int incr; /* direction to move pstartbyte */
const unsigned char* pendbyte; /* MSB of bytes */
size_t numsignificantbytes; /* number of bytes that matter */
- size_t ndigits; /* number of Python long digits */
+ Py_ssize_t ndigits; /* number of Python long digits */
PyLongObject* v; /* result */
- int idigit = 0; /* next free index in v->ob_digit */
+ Py_ssize_t idigit = 0; /* next free index in v->ob_digit */
if (n == 0)
return PyLong_FromLong(0L);
@@ -712,12 +711,16 @@
}
/* How many Python long digits do we need? We have
- 8*numsignificantbytes bits, and each Python long digit has PyLong_SHIFT
- bits, so it's the ceiling of the quotient. */
+ 8*numsignificantbytes bits, and each Python long digit has
+ PyLong_SHIFT bits, so it's the ceiling of the quotient. */
+ /* catch overflow before it happens */
+ if (numsignificantbytes > (PY_SSIZE_T_MAX - PyLong_SHIFT) / 8) {
+ PyErr_SetString(PyExc_OverflowError,
+ "byte array too long to convert to int");
+ return NULL;
+ }
ndigits = (numsignificantbytes * 8 + PyLong_SHIFT - 1) / PyLong_SHIFT;
- if (ndigits > (size_t)INT_MAX)
- return PyErr_NoMemory();
- v = _PyLong_New((int)ndigits);
+ v = _PyLong_New(ndigits);
if (v == NULL)
return NULL;
@@ -746,8 +749,9 @@
accumbits += 8;
if (accumbits >= PyLong_SHIFT) {
/* There's enough to fill a Python digit. */
- assert(idigit < (int)ndigits);
- v->ob_digit[idigit] = (digit)(accum & PyLong_MASK);
+ assert(idigit < ndigits);
+ v->ob_digit[idigit] = (digit)(accum &
+ PyLong_MASK);
++idigit;
accum >>= PyLong_SHIFT;
accumbits -= PyLong_SHIFT;
@@ -756,7 +760,7 @@
}
assert(accumbits < PyLong_SHIFT);
if (accumbits) {
- assert(idigit < (int)ndigits);
+ assert(idigit < ndigits);
v->ob_digit[idigit] = (digit)accum;
++idigit;
}
@@ -1409,19 +1413,11 @@
/* Multiply by a single digit, ignoring the sign. */
static PyLongObject *
-mul1(PyLongObject *a, wdigit n)
-{
- return muladd1(a, n, (digit)0);
-}
-
-/* Multiply by a single digit and add a single digit, ignoring the sign. */
-
-static PyLongObject *
-muladd1(PyLongObject *a, wdigit n, wdigit extra)
+mul1(PyLongObject *a, digit n)
{
Py_ssize_t size_a = ABS(Py_SIZE(a));
PyLongObject *z = _PyLong_New(size_a+1);
- twodigits carry = extra;
+ twodigits carry = 0;
Py_ssize_t i;
if (z == NULL)
@@ -2034,8 +2030,6 @@
static PyLongObject *x_divrem
(PyLongObject *, PyLongObject *, PyLongObject **);
static PyObject *long_long(PyObject *v);
-static int long_divrem(PyLongObject *, PyLongObject *,
- PyLongObject **, PyLongObject **);
/* Long division with remainder, top-level routine */
@@ -2293,14 +2287,12 @@
sign = -1;
i = -(i);
}
-#define LONG_BIT_PyLong_SHIFT (8*sizeof(long) - PyLong_SHIFT)
/* The following loop produces a C unsigned long x such that x is
congruent to the absolute value of v modulo ULONG_MAX. The
resulting x is nonzero if and only if v is. */
while (--i >= 0) {
/* Force a native long #-bits (32 or 64) circular shift */
- x = ((x << PyLong_SHIFT) & ~PyLong_MASK) |
- ((x >> LONG_BIT_PyLong_SHIFT) & PyLong_MASK);
+ x = (x >> (8*SIZEOF_LONG-PyLong_SHIFT)) | (x << PyLong_SHIFT);
x += v->ob_digit[i];
/* If the addition above overflowed we compensate by
incrementing. This preserves the value modulo
@@ -2308,11 +2300,10 @@
if (x < v->ob_digit[i])
x++;
}
-#undef LONG_BIT_PyLong_SHIFT
x = x * sign;
- if (x == -1)
- x = -2;
- return x;
+ if (x == (unsigned long)-1)
+ x = (unsigned long)-2;
+ return (long)x;
}
@@ -3566,12 +3557,12 @@
/* Since PyLong_FromString doesn't have a length parameter,
* check here for possible NULs in the string. */
char *string;
- int size = Py_SIZE(x);
+ Py_ssize_t size = Py_SIZE(x);
if (PyByteArray_Check(x))
string = PyByteArray_AS_STRING(x);
else
string = PyBytes_AS_STRING(x);
- if (strlen(string) != size) {
+ if (strlen(string) != (size_t)size) {
/* We only see this if there's a null byte in x,
x is a bytes or buffer, *and* a base is given. */
PyErr_Format(PyExc_ValueError,
@@ -3784,7 +3775,7 @@
{
Py_ssize_t res;
- res = sizeof(PyVarObject) + abs(Py_SIZE(v))*sizeof(digit);
+ res = offsetof(PyLongObject, ob_digit) + ABS(Py_SIZE(v))*sizeof(digit);
return PyLong_FromSsize_t(res);
}
@@ -3959,9 +3950,7 @@
PyTypeObject PyLong_Type = {
PyVarObject_HEAD_INIT(&PyType_Type, 0)
"int", /* tp_name */
- /* See _PyLong_New for why this isn't
- sizeof(PyLongObject) - sizeof(digit) */
- sizeof(PyVarObject), /* tp_basicsize */
+ offsetof(PyLongObject, ob_digit), /* tp_basicsize */
sizeof(digit), /* tp_itemsize */
long_dealloc, /* tp_dealloc */
0, /* tp_print */
@@ -3973,8 +3962,8 @@
0, /* tp_as_sequence */
0, /* tp_as_mapping */
(hashfunc)long_hash, /* tp_hash */
- 0, /* tp_call */
- long_repr, /* tp_str */
+ 0, /* tp_call */
+ long_repr, /* tp_str */
PyObject_GenericGetAttr, /* tp_getattro */
0, /* tp_setattro */
0, /* tp_as_buffer */
@@ -3998,7 +3987,7 @@
0, /* tp_init */
0, /* tp_alloc */
long_new, /* tp_new */
- PyObject_Del, /* tp_free */
+ PyObject_Del, /* tp_free */
};
int