[postgis-tickets] r15950 - Fix undefined behaviour in zigzag with negative inputs (2.4 branch)
Paul Ramsey
pramsey at cleverelephant.ca
Tue Oct 10 09:59:11 PDT 2017
Author: pramsey
Date: 2017-10-10 09:59:11 -0700 (Tue, 10 Oct 2017)
New Revision: 15950
Modified:
branches/2.2/NEWS
branches/2.2/liblwgeom/cunit/cu_varint.c
branches/2.2/liblwgeom/varint.c
branches/2.2/liblwgeom/varint.h
Log:
Fix undefined behaviour in zigzag with negative inputs (2.4 branch)
(References #3882)
Modified: branches/2.2/NEWS
===================================================================
--- branches/2.2/NEWS 2017-10-10 16:59:04 UTC (rev 15949)
+++ branches/2.2/NEWS 2017-10-10 16:59:11 UTC (rev 15950)
@@ -14,6 +14,7 @@
- #3880, Undefined behaviour in TYPMOD_GET_SRID
- #3875, Fix undefined behaviour in shift operation
- #3874, lw_dist2d_pt_arc division by zero
+ - #3882, undefined behaviour in zigzag with negative inputs
PostGIS 2.2.5
Modified: branches/2.2/liblwgeom/cunit/cu_varint.c
===================================================================
--- branches/2.2/liblwgeom/cunit/cu_varint.c 2017-10-10 16:59:04 UTC (rev 15949)
+++ branches/2.2/liblwgeom/cunit/cu_varint.c 2017-10-10 16:59:11 UTC (rev 15950)
@@ -36,16 +36,16 @@
int size;
char *hex;
uint8_t buf[16];
-
+
size = varint_u32_encode_buf(nr, buf);
if ( size != expected_size )
printf("Expected: %d\nObtained: %d\n", expected_size, size);
CU_ASSERT_EQUAL(size, expected_size);
-
+
hex = hexbytes_from_bytes(buf, size);
- ASSERT_STRING_EQUAL(hex, expected_res);
- lwfree(hex);
+ ASSERT_STRING_EQUAL(hex, expected_res);
+ lwfree(hex);
}
static void do_test_s32_varint(int32_t nr,int expected_size, char* expected_res)
@@ -53,7 +53,7 @@
uint8_t buf[16];
int size;
char *hex;
-
+
size = varint_s32_encode_buf(nr, buf);
if ( size != expected_size )
{
@@ -62,7 +62,7 @@
CU_ASSERT_EQUAL(size,expected_size);
hex = hexbytes_from_bytes(buf, size);
- ASSERT_STRING_EQUAL(hex, expected_res);
+ ASSERT_STRING_EQUAL(hex, expected_res);
lwfree(hex);
}
@@ -71,7 +71,7 @@
uint8_t buf[16];
int size;
char *hex;
-
+
size = varint_u64_encode_buf(nr, buf);
if ( size != expected_size )
{
@@ -89,16 +89,16 @@
uint8_t buf[16];
int size;
char *hex;
-
+
size = varint_s64_encode_buf(nr, buf);
if ( size != expected_size )
{
printf("Expected: %d\nObtained: %d\n", expected_size, size);
}
CU_ASSERT_EQUAL(size,expected_size);
-
+
hex = hexbytes_from_bytes(buf,size);
- ASSERT_STRING_EQUAL(hex, expected_res);
+ ASSERT_STRING_EQUAL(hex, expected_res);
lwfree(hex);
}
@@ -217,13 +217,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.2/liblwgeom/varint.c
===================================================================
--- branches/2.2/liblwgeom/varint.c 2017-10-10 16:59:04 UTC (rev 15949)
+++ branches/2.2/liblwgeom/varint.c 2017-10-10 16:59:11 UTC (rev 15950)
@@ -25,7 +25,7 @@
static size_t
_varint_u64_encode_buf(uint64_t val, uint8_t *buf)
{
- uint8_t grp;
+ uint8_t grp;
uint64_t q = val;
uint8_t *ptr = buf;
while (1)
@@ -35,7 +35,7 @@
/* We rightshift our input value 7 bits */
/* which means that the 7 next least significant bits */
/* becomes the 7 least significant */
- q = q >> 7;
+ q = q >> 7;
/* Check if, after our rightshifting, we still have */
/* anything to read in our input value. */
if ( q > 0 )
@@ -92,7 +92,7 @@
/* Read from signed 64bit varint */
int64_t
varint_s64_decode(const uint8_t *the_start, const uint8_t *the_end, size_t *size)
-{
+{
return unzigzag64(varint_u64_decode(the_start, the_end, size));
}
@@ -159,41 +159,42 @@
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.2/liblwgeom/varint.h
===================================================================
--- branches/2.2/liblwgeom/varint.h 2017-10-10 16:59:04 UTC (rev 15949)
+++ branches/2.2/liblwgeom/varint.h 2017-10-10 16:59:11 UTC (rev 15950)
@@ -34,6 +34,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);
More information about the postgis-tickets
mailing list