Issue #4258: Use 30-bit digits for Python longs, on 64-bit platforms.

Backport of r70459.

3 files changed, 112 insertions, 39 deletions

diff --git a/Python/marshal.c b/Python/marshal.c
index 3460bc3..16cfc20 100644
--- a/Python/marshal.c
+++ b/Python/marshal.c
@@ -11,6 +11,8 @@
 #include "code.h"
 #include "marshal.h"
 
+#define ABS(x) ((x) < 0 ? -(x) : (x))
+
 /* High water mark to determine when the marshalled object is dangerously deep
  * and risks coring the interpreter.  When the object stack gets this deep,
  * raise an exception instead of continuing.
@@ -119,6 +121,56 @@ w_long64(long x, WFILE *p)
 }
 #endif
 
+/* We assume that Python longs are stored internally in base some power of
+   2**15; for the sake of portability we'll always read and write them in base
+   exactly 2**15. */
+
+#define PyLong_MARSHAL_SHIFT 15
+#define PyLong_MARSHAL_BASE ((short)1 << PyLong_MARSHAL_SHIFT)
+#define PyLong_MARSHAL_MASK (PyLong_MARSHAL_BASE - 1)
+#if PyLong_SHIFT % PyLong_MARSHAL_SHIFT != 0
+#error "PyLong_SHIFT must be a multiple of PyLong_MARSHAL_SHIFT"
+#endif
+#define PyLong_MARSHAL_RATIO (PyLong_SHIFT / PyLong_MARSHAL_SHIFT)
+
+static void
+w_PyLong(const PyLongObject *ob, WFILE *p)
+{
+	Py_ssize_t i, j, n, l;
+	digit d;
+
+	w_byte(TYPE_LONG, p);
+	if (Py_SIZE(ob) == 0) {
+		w_long((long)0, p);
+		return;
+	}
+
+	/* set l to number of base PyLong_MARSHAL_BASE digits */
+	n = ABS(Py_SIZE(ob));
+	l = (n-1) * PyLong_MARSHAL_RATIO;
+	d = ob->ob_digit[n-1];
+	assert(d != 0); /* a PyLong is always normalized */
+	do {
+		d >>= PyLong_MARSHAL_SHIFT;
+		l++;
+	} while (d != 0);
+	w_long((long)(Py_SIZE(ob) > 0 ? l : -l), p);
+
+	for (i=0; i < n-1; i++) {
+		d = ob->ob_digit[i];
+		for (j=0; j < PyLong_MARSHAL_RATIO; j++) {
+			w_short(d & PyLong_MARSHAL_MASK, p);
+			d >>= PyLong_MARSHAL_SHIFT;
+		}
+		assert (d == 0);
+	}
+	d = ob->ob_digit[n-1];
+	do {
+		w_short(d & PyLong_MARSHAL_MASK, p);
+		d >>= PyLong_MARSHAL_SHIFT;
+	} while (d != 0);
+}
+
 static void
 w_object(PyObject *v, WFILE *p)
 {
@@ -164,13 +216,7 @@ w_object(PyObject *v, WFILE *p)
 	}
 	else if (PyLong_CheckExact(v)) {
 		PyLongObject *ob = (PyLongObject *)v;
-		w_byte(TYPE_LONG, p);
-		n = ob->ob_size;
-		w_long((long)n, p);
-		if (n < 0)
-			n = -n;
-		for (i = 0; i < n; i++)
-			w_short(ob->ob_digit[i], p);
+		w_PyLong(ob, p);
 	}
 	else if (PyFloat_CheckExact(v)) {
 		if (p->version > 1) {
@@ -507,6 +553,56 @@ r_long64(RFILE *p)
 }
 
 static PyObject *
+r_PyLong(RFILE *p)
+{
+	PyLongObject *ob;
+	int size, i, j, md;
+	long n;
+	digit d;
+
+	n = r_long(p);
+	if (n == 0)
+		return (PyObject *)_PyLong_New(0);
+	if (n < -INT_MAX || n > INT_MAX) {
+		PyErr_SetString(PyExc_ValueError,
+			       "bad marshal data (long size out of range)");
+		return NULL;
+	}
+
+	size = 1 + (ABS(n)-1) / PyLong_MARSHAL_RATIO;
+	ob = _PyLong_New(size);
+	if (ob == NULL)
+		return NULL;
+	Py_SIZE(ob) = n > 0 ? size : -size;
+
+	for (i = 0; i < size-1; i++) {
+		d = 0;
+		for (j=0; j < PyLong_MARSHAL_RATIO; j++) {
+			md = r_short(p);
+			if (md < 0 || md > PyLong_MARSHAL_BASE)
+				goto bad_digit;
+			d += (digit)md << j*PyLong_MARSHAL_SHIFT;
+		}
+		ob->ob_digit[i] = d;
+	}
+	d = 0;
+	for (j=0; j < (ABS(n)-1)%PyLong_MARSHAL_RATIO + 1; j++) {
+		md = r_short(p);
+		if (md < 0 || md > PyLong_MARSHAL_BASE)
+			goto bad_digit;
+		d += (digit)md << j*PyLong_MARSHAL_SHIFT;
+	}
+	ob->ob_digit[size-1] = d;
+	return (PyObject *)ob;
+  bad_digit:
+	Py_DECREF(ob);
+	PyErr_SetString(PyExc_ValueError,
+			"bad marshal data (digit out of range in long)");
+	return NULL;
+}
+
+
+static PyObject *
 r_object(RFILE *p)
 {
 	/* NULL is a valid return value, it does not necessarily means that
@@ -570,38 +666,8 @@ r_object(RFILE *p)
 		break;
 
 	case TYPE_LONG:
-		{
-			int size;
-			PyLongObject *ob;
-			n = r_long(p);
-			if (n < -INT_MAX || n > INT_MAX) {
-				PyErr_SetString(PyExc_ValueError,
-						"bad marshal data (long size out of range)");
-				retval = NULL;
-				break;
-			}
-			size = n<0 ? -n : n;
-			ob = _PyLong_New(size);
-			if (ob == NULL) {
-				retval = NULL;
-				break;
-			}
-			ob->ob_size = n;
-			for (i = 0; i < size; i++) {
-				int digit = r_short(p);
-				if (digit < 0) {
-					Py_DECREF(ob);
-					PyErr_SetString(PyExc_ValueError,
-							"bad marshal data (negative digit in long)");
-					ob = NULL;
-					break;
-				}
-				if (ob != NULL)
-					ob->ob_digit[i] = digit;
-			}
-			retval = (PyObject *)ob;
-			break;
-		}
+		retval = r_PyLong(p);
+		break;
 
 	case TYPE_FLOAT:
 		{
diff --git a/Python/pythonrun.c b/Python/pythonrun.c
index f2cd819..d0c5b2b 100644
--- a/Python/pythonrun.c
+++ b/Python/pythonrun.c
@@ -182,6 +182,9 @@ Py_InitializeEx(int install_sigs)
 	if (!_PyInt_Init())
 		Py_FatalError("Py_Initialize: can't init ints");
 
+	if (!_PyLong_Init())
+		Py_FatalError("Py_Initialize: can't init longs");
+
 	if (!PyByteArray_Init())
 		Py_FatalError("Py_Initialize: can't init bytearray");
 
diff --git a/Python/sysmodule.c b/Python/sysmodule.c
index 91f947d..4e52282 100644
--- a/Python/sysmodule.c
+++ b/Python/sysmodule.c
@@ -1043,6 +1043,8 @@ PyDoc_STR(
 "\n\
 Static objects:\n\
 \n\
+float_info -- a dict with information about the float inplementation.\n\
+long_info -- a struct sequence with information about the long implementation.\n\
 maxint -- the largest supported integer (the smallest is -maxint-1)\n\
 maxsize -- the largest supported length of containers.\n\
 maxunicode -- the largest supported character\n\
@@ -1443,6 +1445,8 @@ _PySys_Init(void)
 			    PyBool_FromLong(Py_Py3kWarningFlag));
 	SET_SYS_FROM_STRING("float_info",
 			    PyFloat_GetInfo());
+	SET_SYS_FROM_STRING("long_info",
+			    PyLong_GetInfo());
 #ifdef Py_USING_UNICODE
 	SET_SYS_FROM_STRING("maxunicode",
 			    PyInt_FromLong(PyUnicode_GetMax()));