SF bug 705836: struct.pack of floats in non-native endian order

pack_float, pack_double, save_float:  All the routines for creating
IEEE-format packed representations of floats and doubles simply ignored
that rounding can (in rare cases) propagate out of a long string of
1 bits.  At worst, the end-off carry can (by mistake) interfere with
the exponent value, and then unpacking yields a result wrong by a factor
of 2.  In less severe cases, it can end up losing more low-order bits
than intended, or fail to catch overflow *caused* by rounding.

Bugfix candidate, but I already backported this to 2.2.

In 2.3, this code remains in severe need of refactoring.

4 files changed, 115 insertions, 18 deletions

diff --git a/Lib/test/test_struct.py b/Lib/test/test_struct.py
index bc0ace8..1e1092d 100644
--- a/Lib/test/test_struct.py
+++ b/Lib/test/test_struct.py
@@ -390,3 +390,49 @@ def test_p_code():
                              (code, input, got, expectedback))
 
 test_p_code()
+
+
+###########################################################################
+# SF bug 705836.  "<f" and ">f" had a severe rounding bug, where a carry
+# from the low-order discarded bits could propagate into the exponent
+# field, causing the result to be wrong by a factor of 2.
+
+def test_705836():
+    import math
+
+    for base in range(1, 33):
+        # smaller <- largest representable float less than base.
+        delta = 0.5
+        while base - delta / 2.0 != base:
+            delta /= 2.0
+        smaller = base - delta
+        # Packing this rounds away a solid string of trailing 1 bits.
+        packed = struct.pack("<f", smaller)
+        unpacked = struct.unpack("<f", packed)[0]
+        # This failed at base = 2, 4, and 32, with unpacked = 1, 2, and
+        # 16, respectively.
+        verify(base == unpacked)
+        bigpacked = struct.pack(">f", smaller)
+        verify(bigpacked == string_reverse(packed),
+               ">f pack should be byte-reversal of <f pack")
+        unpacked = struct.unpack(">f", bigpacked)[0]
+        verify(base == unpacked)
+
+    # Largest finite IEEE single.
+    big = (1 << 24) - 1
+    big = math.ldexp(big, 127 - 23)
+    packed = struct.pack(">f", big)
+    unpacked = struct.unpack(">f", packed)[0]
+    verify(big == unpacked)
+
+    # The same, but tack on a 1 bit so it rounds up to infinity.
+    big = (1 << 25) - 1
+    big = math.ldexp(big, 127 - 24)
+    try:
+        packed = struct.pack(">f", big)
+    except OverflowError:
+        pass
+    else:
+        TestFailed("expected OverflowError")
+
+test_705836()
diff --git a/Misc/NEWS b/Misc/NEWS
index baa3da3..3fb44c1 100644
--- a/Misc/NEWS
+++ b/Misc/NEWS
@@ -37,6 +37,14 @@ Core and builtins
 Extension modules
 -----------------
 
+- The platform-independent routines for packing floats in IEEE formats
+  (struct.pack's <f, >f, <d, and >d codes; pickle and cPickle's protocol 1
+  pickling of floats) ignored that rounding can cause a carry to
+  propagate.  The worst consequence was that, in rare cases, <f and >f
+  could produce strings that, when unpacked again, were a factor of 2
+  away from the original float.  This has been fixed.  See SF bug
+  #705836.
+
 - New function time.tzset() provides access to the C library tzet()
   function, if supported.  (SF patch #675422.)
 
diff --git a/Modules/cPickle.c b/Modules/cPickle.c
index 88f2fc1..964fc63 100644
--- a/Modules/cPickle.c
+++ b/Modules/cPickle.c
@@ -1156,12 +1156,8 @@ save_float(Picklerobject *self, PyObject *args)
 			return -1;
 		}
 
-		if (e >= 1024) {
-			/* XXX 1024 itself is reserved for Inf/NaN */
-			PyErr_SetString(PyExc_OverflowError,
-					"float too large to pack with d format");
-			return -1;
-		}
+		if (e >= 1024)
+			goto Overflow;
 		else if (e < -1022) {
 			/* Gradual underflow */
 			f = ldexp(f, 1022 + e);
@@ -1176,9 +1172,26 @@ save_float(Picklerobject *self, PyObject *args)
 		   flo the low 24 bits (== 52 bits) */
 		f *= 268435456.0; /* 2**28 */
 		fhi = (long) floor(f); /* Truncate */
+		assert(fhi < 268435456);
+
 		f -= (double)fhi;
 		f *= 16777216.0; /* 2**24 */
 		flo = (long) floor(f + 0.5); /* Round */
+		assert(flo <= 16777216);
+		if (flo >> 24) {
+			/* The carry propagated out of a string of 24 1 bits. */
+			flo = 0;
+			++fhi;
+			if (fhi >> 28) {
+				/* And it also progagated out of the next
+				 * 28 bits.
+				 */
+				fhi = 0;
+				++e;
+				if (e >= 2047)
+					goto Overflow;
+			}
+		}
 
 		/* First byte */
 		*p = (s<<7) | (e>>4);
@@ -1224,6 +1237,11 @@ save_float(Picklerobject *self, PyObject *args)
 	}
 
 	return 0;
+
+ Overflow:
+	PyErr_SetString(PyExc_OverflowError,
+			"float too large to pack with d format");
+	return -1;
 }
 
 
diff --git a/Modules/structmodule.c b/Modules/structmodule.c
index d4f8d86..2210c33 100644
--- a/Modules/structmodule.c
+++ b/Modules/structmodule.c
@@ -224,12 +224,8 @@ pack_float(double x, /* The number to pack */
 		return -1;
 	}
 
-	if (e >= 128) {
-		/* XXX 128 itself is reserved for Inf/NaN */
-		PyErr_SetString(PyExc_OverflowError,
-				"float too large to pack with f format");
-		return -1;
-	}
+	if (e >= 128)
+		goto Overflow;
 	else if (e < -126) {
 		/* Gradual underflow */
 		f = ldexp(f, 126 + e);
@@ -242,6 +238,14 @@ pack_float(double x, /* The number to pack */
 
 	f *= 8388608.0; /* 2**23 */
 	fbits = (long) floor(f + 0.5); /* Round */
+	assert(fbits <= 8388608);
+	if (fbits >> 23) {
+		/* The carry propagated out of a string of 23 1 bits. */
+		fbits = 0;
+		++e;
+		if (e >= 255)
+			goto Overflow;
+	}
 
 	/* First byte */
 	*p = (s<<7) | (e>>1);
@@ -260,6 +264,11 @@ pack_float(double x, /* The number to pack */
 
 	/* Done */
 	return 0;
+
+ Overflow:
+	PyErr_SetString(PyExc_OverflowError,
+			"float too large to pack with f format");
+	return -1;
 }
 
 static int
@@ -295,12 +304,8 @@ pack_double(double x, /* The number to pack */
 		return -1;
 	}
 
-	if (e >= 1024) {
-		/* XXX 1024 itself is reserved for Inf/NaN */
-		PyErr_SetString(PyExc_OverflowError,
-				"float too large to pack with d format");
-		return -1;
-	}
+	if (e >= 1024)
+		goto Overflow;
 	else if (e < -1022) {
 		/* Gradual underflow */
 		f = ldexp(f, 1022 + e);
@@ -314,9 +319,24 @@ pack_double(double x, /* The number to pack */
 	/* fhi receives the high 28 bits; flo the low 24 bits (== 52 bits) */
 	f *= 268435456.0; /* 2**28 */
 	fhi = (long) floor(f); /* Truncate */
+	assert(fhi < 268435456);
+
 	f -= (double)fhi;
 	f *= 16777216.0; /* 2**24 */
 	flo = (long) floor(f + 0.5); /* Round */
+	assert(flo <= 16777216);
+	if (flo >> 24) {
+		/* The carry propagated out of a string of 24 1 bits. */
+		flo = 0;
+		++fhi;
+		if (fhi >> 28) {
+			/* And it also progagated out of the next 28 bits. */
+			fhi = 0;
+			++e;
+			if (e >= 2047)
+				goto Overflow;
+		}
+	}
 
 	/* First byte */
 	*p = (s<<7) | (e>>4);
@@ -352,6 +372,11 @@ pack_double(double x, /* The number to pack */
 
 	/* Done */
 	return 0;
+
+ Overflow:
+	PyErr_SetString(PyExc_OverflowError,
+			"float too large to pack with d format");
+	return -1;
 }
 
 static PyObject *