Fix remaining overflow checks.
authorMario de Sousa <msousa@fe.up.pt>
Sun, 10 Jun 2012 15:38:24 +0100
changeset 574 d291a942899b
parent 573 e28b47911c19
child 575 a1b63f776535
Fix remaining overflow checks.
stage3/constant_folding.cc
--- a/stage3/constant_folding.cc	Sat Jun 09 22:58:43 2012 +0100
+++ b/stage3/constant_folding.cc	Sun Jun 10 15:38:24 2012 +0100
@@ -31,10 +31,6 @@
  */
 
 
-/* NOTE:
- *   Most of the conditions to detect overflows on signed (but not unsigned) integer operations were adapted from
- *   https://www.securecoding.cert.org/confluence/display/seccode/INT32-C.+Ensure+that+operations+on+signed+integers+do+not+result+in+overflow?showComments=false
- */
 
 
 
@@ -126,10 +122,10 @@
 #include <stdlib.h> /* required for malloc() */
 
 #if 1
-#define INT64_MAX (std::numeric_limits< int64_t >::max())
-#define INT64_MIN (std::numeric_limits< int64_t >::min()) 
+#define UINT64_MAX (std::numeric_limits< uint64_t >::max())
+#define  INT64_MAX (std::numeric_limits<  int64_t >::max())
+#define  INT64_MIN (std::numeric_limits<  int64_t >::min()) 
 #else
-/* An alternative is to use the std::numeric_limits< uint64_t >::min() / max()  methods already defined in #include <limits> */
 #define __STDC_LIMIT_MACROS /* required for UINT64_MAX, INT64_MAX, INT64_MIN, ... */
 #include <stdint.h>         /* required for UINT64_MAX, INT64_MAX, INT64_MIN, ... */
 #endif
@@ -181,7 +177,7 @@
     /* The following test is correct in the presence of a NULL pointer, as the logical evaluation will be suspended as soon as the first condition is false! */
 #define VALID_CVALUE(dtype, symbol)           ((NULL != (symbol)->const_value_##dtype) && (symbol_c::cs_const_value == (symbol)->const_value_##dtype->status))
 #define ISZERO_CVALUE(dtype, symbol)          ((VALID_CVALUE(dtype, symbol)) && (GET_CVALUE(dtype, symbol) == 0))
-#define DO_BIN_OPER(dtype, oper)\
+#define DO_BINARY_OPER(dtype, oper)\
 	if (VALID_CVALUE(dtype, symbol->r_exp) && VALID_CVALUE(dtype, symbol->l_exp)) {                                \
 		NEW_CVALUE(dtype, symbol);                                                                             \
 		SET_CVALUE(dtype, symbol, GET_CVALUE(dtype, symbol->l_exp) oper GET_CVALUE(dtype, symbol->r_exp));     \
@@ -194,94 +190,126 @@
 
 
 
-
-
+/* NOTE:
+ *   Most of the conditions to detect overflows on signed and unsigned integer operations were adapted from
+ *   https://www.securecoding.cert.org/confluence/display/seccode/INT32-C.+Ensure+that+operations+on+signed+integers+do+not+result+in+overflow?showComments=false
+ *   https://www.securecoding.cert.org/confluence/display/seccode/INT30-C.+Ensure+that+unsigned+integer+operations+do+not+wrap
+ */
+
+/* NOTE: If at all possible, all overflow tests are done by pre-condition tests, i.e. tests that 
+ *       can be run _before_ the operation is executed, and therefore without accessing the result!
+ *
+ *       The exception is for real/floating point values, that simply test if the result is NaN (not a number).
+ */
 
 /* res = a + b */
 static void CHECK_OVERFLOW_uint64_SUM(symbol_c *res, symbol_c *a, symbol_c *b) {
-	if (VALID_CVALUE(uint64, res))
-		/* If sum is smaller than either operand => overflow! */
-		if (GET_CVALUE(uint64, res) < GET_CVALUE(uint64, a))
-			SET_OVFLOW(uint64, res);
-}
+	if (!VALID_CVALUE(uint64, res))
+		return;
+	/* Test by post-condition: If sum is smaller than either operand => overflow! */
+	// if (GET_CVALUE(uint64, res) < GET_CVALUE(uint64, a))
+	/* Test by pre-condition: If (UINT64_MAX - a) < b => overflow! */
+	if ((UINT64_MAX - GET_CVALUE(uint64, a)) < GET_CVALUE(uint64, b))
+		SET_OVFLOW(uint64, res);
+}
+
 
 /* res = a - b */
 static void CHECK_OVERFLOW_uint64_SUB(symbol_c *res, symbol_c *a, symbol_c *b) {
-	if (VALID_CVALUE(uint64, res))
-		/* If diference is larger than a => overflow! */
-		if (GET_CVALUE(uint64, res) > GET_CVALUE(uint64, a))
-			SET_OVFLOW(uint64, res);
-}
+	if (!VALID_CVALUE(uint64, res))
+		return;
+	/* Test by post-condition: If diference is larger than a => overflow! */
+	// if (GET_CVALUE(uint64, res) > GET_CVALUE(uint64, a))
+	/* Test by pre-condition: if b > a => overflow! */
+	if (GET_CVALUE(uint64, b) > GET_CVALUE(uint64, a))
+		SET_OVFLOW(uint64, res);
+}
+
 
 /* res = a * b */
 static void CHECK_OVERFLOW_uint64_MUL(symbol_c *res, symbol_c *a, symbol_c *b) {
-	if (VALID_CVALUE(uint64, res))
-		if (false /* TODO */)
-			SET_OVFLOW(uint64, res);
-}
+	if (!VALID_CVALUE(uint64, res))
+		return;
+	/* Test by pre-condition: If (UINT64_MAX / a) < b => overflow! */
+	if ((UINT64_MAX / GET_CVALUE(uint64, a)) < GET_CVALUE(uint64, b))
+		SET_OVFLOW(uint64, res);
+}
+
 
 /* res = a / b */
 static void CHECK_OVERFLOW_uint64_DIV(symbol_c *res, symbol_c *a, symbol_c *b) {
-	if (VALID_CVALUE(uint64, res))
-		if (false /* TODO */)
-			SET_OVFLOW(uint64, res);
-}
+	if (!VALID_CVALUE(uint64, res))
+		return;
+	if (GET_CVALUE(uint64, b) == 0) /* division by zero! */
+		SET_OVFLOW(uint64, res);
+}
+
 
 /* res = a MOD b */
 static void CHECK_OVERFLOW_uint64_MOD(symbol_c *res, symbol_c *a, symbol_c *b) {
-	if (VALID_CVALUE(uint64, res))
-		if (false /* TODO */)
-			SET_OVFLOW(uint64, res);
-}
+	if (!VALID_CVALUE(uint64, res))
+		return;
+	/* no overflow condition exists, including division by zero, which IEC 61131-3 considers legal for MOD operation! */
+	if (false) 
+		SET_OVFLOW(uint64, res);
+}
+
 
 /* res = a + b */
 static void CHECK_OVERFLOW_int64_SUM(symbol_c *res, symbol_c *a_ptr, symbol_c *b_ptr) {
+	if (!VALID_CVALUE(int64, res))
+		return;
 	int64_t a = GET_CVALUE(int64, a_ptr);
 	int64_t b = GET_CVALUE(int64, b_ptr);
-	if (VALID_CVALUE(int64, res))
-		/* The following test is valid no matter what representation is being used (e.g. two's complement, etc...) */
-		if (((b > 0) && (a > (INT64_MAX - b)))
-		 || ((b < 0) && (a < (INT64_MIN - b))))
-			SET_OVFLOW(int64, res);
-}
+	/* The following test is valid no matter what representation is being used (e.g. two's complement, etc...) */
+	if (((b > 0) && (a > (INT64_MAX - b)))
+	 || ((b < 0) && (a < (INT64_MIN - b))))
+		SET_OVFLOW(int64, res);
+}
+
 
 /* res = a - b */
 static void CHECK_OVERFLOW_int64_SUB(symbol_c *res, symbol_c *a_ptr, symbol_c *b_ptr) {
+	if (!VALID_CVALUE(int64, res))
+		return;
 	int64_t a = GET_CVALUE(int64, a_ptr);
 	int64_t b = GET_CVALUE(int64, b_ptr);
-	if (VALID_CVALUE(int64, res))
-		/* The following test is valid no matter what representation is being used (e.g. two's complement, etc...) */
-		if (((b > 0) && (a < (INT64_MIN + b)))
-		 || ((b < 0) && (a > (INT64_MAX + b))))
-			SET_OVFLOW(int64, res);
+	/* The following test is valid no matter what representation is being used (e.g. two's complement, etc...) */
+	if (((b > 0) && (a < (INT64_MIN + b)))
+	 || ((b < 0) && (a > (INT64_MAX + b))))
+		SET_OVFLOW(int64, res);
 }
 
 
 /* res = a * b */
 static void CHECK_OVERFLOW_int64_MUL(symbol_c *res, symbol_c *a_ptr, symbol_c *b_ptr) {
+	if (!VALID_CVALUE(int64, res))
+		return;
 	int64_t a = GET_CVALUE(int64, a_ptr);
 	int64_t b = GET_CVALUE(int64, b_ptr);
-	if (VALID_CVALUE(int64, res))
-		if (   ( (a > 0) &&  (b > 0) &&             (a > (INT64_MAX / b))) 
-		    || ( (a > 0) && !(b > 0) &&             (b < (INT64_MIN / a))) 
-		    || (!(a > 0) &&  (b > 0) &&             (a < (INT64_MIN / b))) 
-		    || (!(a > 0) && !(b > 0) && (a != 0) && (b < (INT64_MAX / a))))
-			SET_OVFLOW(int64, res);
+	if (   ( (a > 0) &&  (b > 0) &&             (a > (INT64_MAX / b))) 
+	    || ( (a > 0) && !(b > 0) &&             (b < (INT64_MIN / a))) 
+	    || (!(a > 0) &&  (b > 0) &&             (a < (INT64_MIN / b))) 
+	    || (!(a > 0) && !(b > 0) && (a != 0) && (b < (INT64_MAX / a))))
+		SET_OVFLOW(int64, res);
 }
 
 
 /* res = a / b */
 static void CHECK_OVERFLOW_int64_DIV(symbol_c *res, symbol_c *a_ptr, symbol_c *b_ptr) {
+	if (!VALID_CVALUE(int64, res))
+		return;
 	int64_t a = GET_CVALUE(int64, a_ptr);
 	int64_t b = GET_CVALUE(int64, b_ptr);
-	if (VALID_CVALUE(int64, res))
-		if ((b == 0) || ((a == INT64_MIN) && (b == -1)))
-			SET_OVFLOW(int64, res);
+	if ((b == 0) || ((a == INT64_MIN) && (b == -1)))
+		SET_OVFLOW(int64, res);
 }
 
 
 /* res = a MOD b */
 static void CHECK_OVERFLOW_int64_MOD(symbol_c *res, symbol_c *a_ptr, symbol_c *b_ptr) {
+	if (!VALID_CVALUE(int64, res))
+		return;
 	int64_t a = GET_CVALUE(int64, a_ptr);
 	int64_t b = GET_CVALUE(int64, b_ptr);
 	/* IEC 61131-3 standard says IN1 MOD IN2 must be equivalent to
@@ -292,27 +320,28 @@
 	 *
 	 * On the other hand, division by 0 is OK!!
 	 */
-	if (VALID_CVALUE(int64, res))
-		if ((a == INT64_MIN) && (b == -1))
-			SET_OVFLOW(int64, res);
+	if ((a == INT64_MIN) && (b == -1))
+		SET_OVFLOW(int64, res);
 }
 
 
 /* res = - a */
 static void CHECK_OVERFLOW_int64_NEG(symbol_c *res, symbol_c *a_ptr) {
+	if (!VALID_CVALUE(int64, res))
+		return;
 	int64_t a = GET_CVALUE(int64, a_ptr);
-	if (VALID_CVALUE(int64, res))
-		if (a == INT64_MIN)
-			SET_OVFLOW(int64, res);
+	if (a == INT64_MIN)
+		SET_OVFLOW(int64, res);
 }
 
 
 
 static void CHECK_OVERFLOW_real64(symbol_c *res) {
-	if (VALID_CVALUE(real64, res))
-        	/* NaN => underflow, overflow, number is a higher precision format, is a complex number (IEEE standard) */
-		 if (isnan(GET_CVALUE(real64, res)))
-			SET_OVFLOW(real64, res);
+	if (!VALID_CVALUE(real64, res))
+		return;
+       	/* NaN => underflow, overflow, number is a higher precision format, is a complex number (IEEE standard) */
+	if (isnan(GET_CVALUE(real64, res)))
+		SET_OVFLOW(real64, res);
 }
 
 
@@ -390,7 +419,7 @@
 		NEW_CVALUE( int64, symbol);
 		SET_CVALUE( int64, symbol, - GET_CVALUE( int64, symbol->exp));
 	}
-       	CHECK_OVERFLOW_int64_NEG(symbol, symbol->exp);
+	CHECK_OVERFLOW_int64_NEG(symbol, symbol->exp);
 	return NULL;
 }
 
@@ -484,8 +513,8 @@
 void *constant_folding_c::visit(or_expression_c *symbol) {
 	symbol->l_exp->accept(*this);
 	symbol->r_exp->accept(*this);
-	DO_BIN_OPER(bool,   ||);
-	DO_BIN_OPER(uint64, | );
+	DO_BINARY_OPER(bool,   ||);
+	DO_BINARY_OPER(uint64, | );
 	return NULL;
 }
 
@@ -493,8 +522,8 @@
 void *constant_folding_c::visit(xor_expression_c *symbol) {
 	symbol->l_exp->accept(*this);
 	symbol->r_exp->accept(*this);
-	DO_BIN_OPER(bool,   ^);
-	DO_BIN_OPER(uint64, ^);
+	DO_BINARY_OPER(bool,   ^);
+	DO_BINARY_OPER(uint64, ^);
 	return NULL;
 }
 
@@ -502,8 +531,8 @@
 void *constant_folding_c::visit(and_expression_c *symbol) {
 	symbol->l_exp->accept(*this);
 	symbol->r_exp->accept(*this);
-	DO_BIN_OPER(bool,   &&);
-	DO_BIN_OPER(uint64, & );
+	DO_BINARY_OPER(bool,   &&);
+	DO_BINARY_OPER(uint64, & );
 	return NULL;
 }
 
@@ -511,10 +540,10 @@
 void *constant_folding_c::visit(equ_expression_c *symbol) {
 	symbol->l_exp->accept(*this);
 	symbol->r_exp->accept(*this);
-	DO_BIN_OPER(bool,   ==);
-	DO_BIN_OPER(uint64, ==);
-	DO_BIN_OPER( int64, ==);
-	DO_BIN_OPER(real64, ==);
+	DO_BINARY_OPER(bool,   ==);
+	DO_BINARY_OPER(uint64, ==);
+	DO_BINARY_OPER( int64, ==);
+	DO_BINARY_OPER(real64, ==);
 	return NULL;
 }
 
@@ -522,10 +551,10 @@
 void *constant_folding_c::visit(notequ_expression_c *symbol) {
 	symbol->l_exp->accept(*this);
 	symbol->r_exp->accept(*this);
-	DO_BIN_OPER(bool,   !=);
-	DO_BIN_OPER(uint64, !=);
-	DO_BIN_OPER( int64, !=);
-	DO_BIN_OPER(real64, !=);
+	DO_BINARY_OPER(bool,   !=);
+	DO_BINARY_OPER(uint64, !=);
+	DO_BINARY_OPER( int64, !=);
+	DO_BINARY_OPER(real64, !=);
 	return NULL;
 }
 
@@ -533,10 +562,10 @@
 void *constant_folding_c::visit(lt_expression_c *symbol) {
 	symbol->l_exp->accept(*this);
 	symbol->r_exp->accept(*this);
-	DO_BIN_OPER(bool,   <);
-	DO_BIN_OPER(uint64, <);
-	DO_BIN_OPER( int64, <);
-	DO_BIN_OPER(real64, <);
+	DO_BINARY_OPER(bool,   <);
+	DO_BINARY_OPER(uint64, <);
+	DO_BINARY_OPER( int64, <);
+	DO_BINARY_OPER(real64, <);
 	return NULL;
 }
 
@@ -544,10 +573,10 @@
 void *constant_folding_c::visit(gt_expression_c *symbol) {
 	symbol->l_exp->accept(*this);
 	symbol->r_exp->accept(*this);
-	DO_BIN_OPER(bool,   >);
-	DO_BIN_OPER(uint64, >);
-	DO_BIN_OPER( int64, >);
-	DO_BIN_OPER(real64, >);
+	DO_BINARY_OPER(bool,   >);
+	DO_BINARY_OPER(uint64, >);
+	DO_BINARY_OPER( int64, >);
+	DO_BINARY_OPER(real64, >);
 	return NULL;
 }
 
@@ -555,10 +584,10 @@
 void *constant_folding_c::visit(le_expression_c *symbol) {
 	symbol->l_exp->accept(*this);
 	symbol->r_exp->accept(*this);
-	DO_BIN_OPER(bool,   <=);
-	DO_BIN_OPER(uint64, <=);
-	DO_BIN_OPER( int64, <=);
-	DO_BIN_OPER(real64, <=);
+	DO_BINARY_OPER(bool,   <=);
+	DO_BINARY_OPER(uint64, <=);
+	DO_BINARY_OPER( int64, <=);
+	DO_BINARY_OPER(real64, <=);
 	return NULL;
 }
 
@@ -566,10 +595,10 @@
 void *constant_folding_c::visit(ge_expression_c *symbol) {
 	symbol->l_exp->accept(*this);
 	symbol->r_exp->accept(*this);
-	DO_BIN_OPER(bool,   >=);
-	DO_BIN_OPER(uint64, >=);
-	DO_BIN_OPER( int64, >=);
-	DO_BIN_OPER(real64, >=);
+	DO_BINARY_OPER(bool,   >=);
+	DO_BINARY_OPER(uint64, >=);
+	DO_BINARY_OPER( int64, >=);
+	DO_BINARY_OPER(real64, >=);
 	return NULL;
 }
 
@@ -577,9 +606,9 @@
 void *constant_folding_c::visit(add_expression_c *symbol) {
 	symbol->l_exp->accept(*this);
 	symbol->r_exp->accept(*this);
-	DO_BIN_OPER(uint64, +);   CHECK_OVERFLOW_uint64_SUM(symbol, symbol->l_exp, symbol->r_exp);
-	DO_BIN_OPER( int64, +);   CHECK_OVERFLOW_int64_SUM (symbol, symbol->l_exp, symbol->r_exp);
-	DO_BIN_OPER(real64, +);   CHECK_OVERFLOW_real64    (symbol);
+	DO_BINARY_OPER(uint64, +);   CHECK_OVERFLOW_uint64_SUM(symbol, symbol->l_exp, symbol->r_exp);
+	DO_BINARY_OPER( int64, +);   CHECK_OVERFLOW_int64_SUM (symbol, symbol->l_exp, symbol->r_exp);
+	DO_BINARY_OPER(real64, +);   CHECK_OVERFLOW_real64    (symbol);
 	return NULL;
 }
 
@@ -587,9 +616,9 @@
 void *constant_folding_c::visit(sub_expression_c *symbol) {
 	symbol->l_exp->accept(*this);
 	symbol->r_exp->accept(*this);
-	DO_BIN_OPER(uint64, -);   CHECK_OVERFLOW_uint64_SUB(symbol, symbol->l_exp, symbol->r_exp);
-	DO_BIN_OPER( int64, -);   CHECK_OVERFLOW_int64_SUB (symbol, symbol->l_exp, symbol->r_exp);
-	DO_BIN_OPER(real64, -);   CHECK_OVERFLOW_real64    (symbol);
+	DO_BINARY_OPER(uint64, -);   CHECK_OVERFLOW_uint64_SUB(symbol, symbol->l_exp, symbol->r_exp);
+	DO_BINARY_OPER( int64, -);   CHECK_OVERFLOW_int64_SUB (symbol, symbol->l_exp, symbol->r_exp);
+	DO_BINARY_OPER(real64, -);   CHECK_OVERFLOW_real64    (symbol);
 	return NULL;
 }
 
@@ -597,9 +626,9 @@
 void *constant_folding_c::visit(mul_expression_c *symbol) {
 	symbol->l_exp->accept(*this);
 	symbol->r_exp->accept(*this);
-	DO_BIN_OPER(uint64, *);   CHECK_OVERFLOW_uint64_MUL(symbol, symbol->l_exp, symbol->r_exp);
-	DO_BIN_OPER( int64, *);   CHECK_OVERFLOW_int64_MUL (symbol, symbol->l_exp, symbol->r_exp);
-	DO_BIN_OPER(real64, *);   CHECK_OVERFLOW_real64    (symbol);
+	DO_BINARY_OPER(uint64, *);   CHECK_OVERFLOW_uint64_MUL(symbol, symbol->l_exp, symbol->r_exp);
+	DO_BINARY_OPER( int64, *);   CHECK_OVERFLOW_int64_MUL (symbol, symbol->l_exp, symbol->r_exp);
+	DO_BINARY_OPER(real64, *);   CHECK_OVERFLOW_real64    (symbol);
 	return NULL;
 }
 
@@ -608,9 +637,9 @@
 void *constant_folding_c::visit(div_expression_c *symbol) {
 	symbol->l_exp->accept(*this);
 	symbol->r_exp->accept(*this);
-	if (ISZERO_CVALUE(uint64, symbol->r_exp))  {NEW_CVALUE(uint64, symbol); SET_OVFLOW(uint64, symbol);} else {DO_BIN_OPER(uint64, /); CHECK_OVERFLOW_uint64_DIV(symbol, symbol->l_exp, symbol->r_exp);};
-	if (ISZERO_CVALUE( int64, symbol->r_exp))  {NEW_CVALUE( int64, symbol); SET_OVFLOW( int64, symbol);} else {DO_BIN_OPER( int64, /); CHECK_OVERFLOW_int64_DIV(symbol, symbol->l_exp, symbol->r_exp);};
-	if (ISZERO_CVALUE(real64, symbol->r_exp))  {NEW_CVALUE(real64, symbol); SET_OVFLOW(real64, symbol);} else {DO_BIN_OPER(real64, /); CHECK_OVERFLOW_real64(symbol);};
+	if (ISZERO_CVALUE(uint64, symbol->r_exp))  {NEW_CVALUE(uint64, symbol); SET_OVFLOW(uint64, symbol);} else {DO_BINARY_OPER(uint64, /); CHECK_OVERFLOW_uint64_DIV(symbol, symbol->l_exp, symbol->r_exp);};
+	if (ISZERO_CVALUE( int64, symbol->r_exp))  {NEW_CVALUE( int64, symbol); SET_OVFLOW( int64, symbol);} else {DO_BINARY_OPER( int64, /); CHECK_OVERFLOW_int64_DIV(symbol, symbol->l_exp, symbol->r_exp);};
+	if (ISZERO_CVALUE(real64, symbol->r_exp))  {NEW_CVALUE(real64, symbol); SET_OVFLOW(real64, symbol);} else {DO_BINARY_OPER(real64, /); CHECK_OVERFLOW_real64(symbol);};
 	return NULL;
 }
 
@@ -624,8 +653,8 @@
 	 * Note that, when IN1 = INT64_MIN, and IN2 = -1, an overflow occurs in the division,
 	 * so although the MOD operation should be OK, acording to the above definition, we actually have an overflow!!
 	 */
-	if (ISZERO_CVALUE(uint64, symbol->r_exp))  {NEW_CVALUE(uint64, symbol); SET_CVALUE(uint64, symbol, 0);} else {DO_BIN_OPER(uint64, %); CHECK_OVERFLOW_uint64_MOD(symbol, symbol->l_exp, symbol->r_exp);};
-	if (ISZERO_CVALUE( int64, symbol->r_exp))  {NEW_CVALUE( int64, symbol); SET_CVALUE( int64, symbol, 0);} else {DO_BIN_OPER( int64, %); CHECK_OVERFLOW_int64_MOD(symbol, symbol->l_exp, symbol->r_exp);};
+	if (ISZERO_CVALUE(uint64, symbol->r_exp))  {NEW_CVALUE(uint64, symbol); SET_CVALUE(uint64, symbol, 0);} else {DO_BINARY_OPER(uint64, %); CHECK_OVERFLOW_uint64_MOD(symbol, symbol->l_exp, symbol->r_exp);};
+	if (ISZERO_CVALUE( int64, symbol->r_exp))  {NEW_CVALUE( int64, symbol); SET_CVALUE( int64, symbol, 0);} else {DO_BINARY_OPER( int64, %); CHECK_OVERFLOW_int64_MOD(symbol, symbol->l_exp, symbol->r_exp);};
 	return NULL;
 }