[postgis-tickets] r15948 - Fix undefined behaviour in zigzag with negative inputs (2.4 branch)

[Paul Ramsey]

Author: pramsey
Date: 2017-10-10 09:58:57 -0700 (Tue, 10 Oct 2017)
New Revision: 15948

Modified:
   branches/2.4/NEWS
   branches/2.4/liblwgeom/cunit/cu_varint.c
   branches/2.4/liblwgeom/varint.c
   branches/2.4/liblwgeom/varint.h
Log:
Fix undefined behaviour in zigzag with negative inputs (2.4 branch)
(References #3882)



Modified: branches/2.4/NEWS
===================================================================
--- branches/2.4/NEWS	2017-10-10 16:37:32 UTC (rev 15947)
+++ branches/2.4/NEWS	2017-10-10 16:58:57 UTC (rev 15948)
@@ -12,6 +12,7 @@
   - #3875, Fix undefined behaviour in shift operation
   - #3864, Performance improvements for b-tree geometry sorts
   - #3874, lw_dist2d_pt_arc division by zero
+  - #3882, undefined behaviour in zigzag with negative inputs
 
 
 PostGIS 2.4.0

Modified: branches/2.4/liblwgeom/cunit/cu_varint.c
===================================================================
--- branches/2.4/liblwgeom/cunit/cu_varint.c	2017-10-10 16:37:32 UTC (rev 15947)
+++ branches/2.4/liblwgeom/cunit/cu_varint.c	2017-10-10 16:58:57 UTC (rev 15948)
@@ -220,13 +220,27 @@
 	{
 		a = b = i;
 		CU_ASSERT_EQUAL(a, unzigzag64(zigzag64(a)));
-		CU_ASSERT_EQUAL(b, unzigzag32(zigzag64(b)));
+		CU_ASSERT_EQUAL(b, unzigzag32(zigzag32(b)));
 
 		a = b = -1 * i;
 		CU_ASSERT_EQUAL(a, unzigzag64(zigzag64(a)));
-		CU_ASSERT_EQUAL(b, unzigzag32(zigzag64(b)));
+		CU_ASSERT_EQUAL(b, unzigzag32(zigzag32(b)));
 	}
 
+	//8
+	CU_ASSERT_EQUAL(-INT8_MAX, unzigzag8(zigzag8(-INT8_MAX)));
+	CU_ASSERT_EQUAL(INT8_MAX, unzigzag8(zigzag8(INT8_MAX)));
+	CU_ASSERT_EQUAL(0, unzigzag8(zigzag8(0)));
+
+	//32
+	CU_ASSERT_EQUAL(-INT32_MAX, unzigzag32(zigzag32(-INT32_MAX)));
+	CU_ASSERT_EQUAL(INT32_MAX, unzigzag32(zigzag32(INT32_MAX)));
+	CU_ASSERT_EQUAL(0, unzigzag32(zigzag32(0)));
+
+	//64
+	CU_ASSERT_EQUAL(-INT64_MAX, unzigzag64(zigzag64(-INT64_MAX)));
+	CU_ASSERT_EQUAL(INT64_MAX, unzigzag64(zigzag64(INT64_MAX)));
+	CU_ASSERT_EQUAL(0, unzigzag64(zigzag64(0)));
 }
 
 

Modified: branches/2.4/liblwgeom/varint.c
===================================================================
--- branches/2.4/liblwgeom/varint.c	2017-10-10 16:37:32 UTC (rev 15947)
+++ branches/2.4/liblwgeom/varint.c	2017-10-10 16:58:57 UTC (rev 15948)
@@ -167,41 +167,44 @@
 
 uint64_t zigzag64(int64_t val)
 {
-	return (val << 1) ^ (val >> 63);
+	return val >= 0 ?
+		((uint64_t)val) << 1 :
+		((((uint64_t)(-1 - val)) << 1) | 0x01);
 }
 
 uint32_t zigzag32(int32_t val)
 {
-	return (val << 1) ^ (val >> 31);
+	return val >= 0 ?
+		((uint32_t)val) << 1 :
+		((((uint32_t)(-1 - val)) << 1) | 0x01);
 }
 
 uint8_t zigzag8(int8_t val)
 {
-	return (val << 1) ^ (val >> 7);
+	return val >= 0 ?
+		((uint8_t)val) << 1 :
+		((((uint8_t)(-1 - val)) << 1) | 0x01);
 }
 
 int64_t unzigzag64(uint64_t val)
 {
-        if ( val & 0x01 )
-            return -1 * (int64_t)((val+1) >> 1);
-        else
-            return (int64_t)(val >> 1);
+	return !(val & 0x01) ?
+		((int64_t)(val >> 1)) :
+		(-1 * (int64_t)((val+1) >> 1));
 }
 
 int32_t unzigzag32(uint32_t val)
 {
-        if ( val & 0x01 )
-            return -1 * (int32_t)((val+1) >> 1);
-        else
-            return (int32_t)(val >> 1);
+	return !(val & 0x01) ?
+		((int32_t)(val >> 1)) :
+		(-1 * (int32_t)((val+1) >> 1));
 }
 
 int8_t unzigzag8(uint8_t val)
 {
-        if ( val & 0x01 )
-            return -1 * (int8_t)((val+1) >> 1);
-        else
-            return (int8_t)(val >> 1);
+	return !(val & 0x01) ?
+		((int8_t)(val >> 1)) :
+		(-1 * (int8_t)((val+1) >> 1));
 }
 
 

Modified: branches/2.4/liblwgeom/varint.h
===================================================================
--- branches/2.4/liblwgeom/varint.h	2017-10-10 16:37:32 UTC (rev 15947)
+++ branches/2.4/liblwgeom/varint.h	2017-10-10 16:58:57 UTC (rev 15948)
@@ -42,6 +42,8 @@
 
 size_t varint_size(const uint8_t *the_start, const uint8_t *the_end);
 
+/* Support from -INT{8,32,64}_MAX to INT{8,32,64}_MAX),
+ * e.g INT8_MIN is not supported in zigzag8 */
 uint64_t zigzag64(int64_t val);
 uint32_t zigzag32(int32_t val);
 uint8_t zigzag8(int8_t val);