[issue4258] Use 30-bit digits instead of 15-bit digits for Python integers.

Python/marshal.c

 
 /* Write Python objects to files and read them back.
    This is intended for writing and reading compiled Python code only;
    a true persistent storage facility would be much harder, since
    it would have to take circular links and sharing into account. */
 
 #define PY_SSIZE_T_CLEAN
 
 #include "Python.h"
 #include "longintrepr.h"
 #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.
  * On Windows debug builds, reduce this value.
  */
 #if defined(MS_WINDOWS) && defined(_DEBUG)
 #define MAX_MARSHAL_STACK_DEPTH 1500
 #else
 #define MAX_MARSHAL_STACK_DEPTH 2000
 #endif
@@ skipping 91 matching lines @@
 
 #if SIZEOF_LONG > 4
 static void
 w_long64(long x, WFILE *p)
 {
         w_long(x, p);
         w_long(x>>32, 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);

[Martin v. Löwis, 2009/02/17 22:39:18]

This needs to deal with overflow (sizeof(size_t) > sizeof(long))

[dickinsm, 2009/02/18 17:06:33]

Hmm.  It looks as though there are many places in this file,
particularly in w_object, that do "w_long((long)n, p), where
n has type Py_ssize_t.  Presumably all of these should
be fixed.

[Martin v. Löwis, 2009/02/18 21:27:04]

Ok, so I'd waive this for this patch; please do create a separate report.

[dickinsm, 2009/02/19 09:42:15]

Done.

http://bugs.python.org/issue5308

+
+        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)
 {
         Py_ssize_t i, n;
 
         p->depth++;
 
         if (p->depth > MAX_MARSHAL_STACK_DEPTH) {
                 p->error = 2;
         }
@@ skipping 13 matching lines @@
                 w_byte(TYPE_FALSE, p);
         }
         else if (v == Py_True) {
                 w_byte(TYPE_TRUE, p);
         }
         else if (PyLong_CheckExact(v)) {
                 long x = PyLong_AsLong(v);
                 if ((x == -1)  && PyErr_Occurred()) {
                         PyLongObject *ob = (PyLongObject *)v;
                         PyErr_Clear();
-                        w_byte(TYPE_LONG, p);
-                        n = Py_SIZE(ob);
-                        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 SIZEOF_LONG > 4
                         long y = Py_ARITHMETIC_RIGHT_SHIFT(long, x, 31);
                         if (y && y != -1) {
                                 w_byte(TYPE_INT64, p);
                                 w_long64(x, p);
                         }
                         else
 #endif
                         {
@@ skipping 298 matching lines @@
         }
         else {
                 memcpy(buf, &hi4, 4);
                 memcpy(buf+4, &lo4, 4);
         }
         return _PyLong_FromByteArray(buf, 8, is_little_endian, 1);
 #endif
 }
 
 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)

[Martin v. Löwis, 2009/02/17 22:39:18]

I think this is obsolete now; longs can have up to ssize_t_max digits.

[dickinsm, 2009/02/18 17:06:33]

Agreed. Again, this needs to be fixed throughout marshal.c (many
occurrences in r_object).

+                goto bad_data;
+
+        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) {
+                                Py_DECREF(ob);
+                                goto bad_data;
+                        }
+                        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) {
+                        Py_DECREF(ob);
+                        goto bad_data;
+                }
+                d += (digit)md << (j*PyLong_MARSHAL_SHIFT);
+        }
+        ob->ob_digit[size-1] = d;
+        return (PyObject *)ob;
+  bad_data:
+        PyErr_SetString(PyExc_ValueError, "bad marshal data");
+        return NULL;
+}
+
+
+static PyObject *
 r_object(RFILE *p)
 {
         /* NULL is a valid return value, it does not necessarily means that
            an exception is set. */
         PyObject *v, *v2;
         long i, n;
         int type = r_byte(p);
         PyObject *retval;
 
         p->depth++;
@@ skipping 43 matching lines @@
 
         case TYPE_INT:
                 retval = PyLong_FromLong(r_long(p));
                 break;
 
         case TYPE_INT64:
                 retval = r_long64(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");
-                                retval = NULL;
-                                break;
-                        }
-                        size = n<0 ? -n : n;
-                        ob = _PyLong_New(size);
-                        if (ob == NULL) {
-                                retval = NULL;
-                                break;
-                        }
-                        Py_SIZE(ob) = 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");
-                                        ob = NULL;
-                                        break;
-                                }
-                                if (ob != NULL)
-                                        ob->ob_digit[i] = digit;
-                        }
-                        retval = (PyObject *)ob;
-                        break;
-                }
+                retval = r_PyLong(p);
+                break;
 
         case TYPE_FLOAT:
                 {
                         char buf[256];
                         double dx;
                         n = r_byte(p);
                         if (n == EOF || r_string(buf, (int)n, p) != n) {
                                 PyErr_SetString(PyExc_EOFError,
                                         "EOF read where object expected");
                                 retval = NULL;
@@ skipping 622 matching lines @@
 
 PyMODINIT_FUNC
 PyMarshal_Init(void)
 {
         PyObject *mod = PyModule_Create(&marshalmodule);
         if (mod == NULL)
                 return NULL;
         PyModule_AddIntConstant(mod, "version", Py_MARSHAL_VERSION);
         return mod;
 }