Fix integer math overflows in the preprocessor
Evaluating integer expressions in the ESSL preprocessor may result in
overflowing the signed integer range. Implement wrapping overflow for
preprocessor expressions in a way that doesn't hit any undefined
behavior. In the ESSL spec, preprocessor expressions are defined to
have mostly the same semantics as in C++. Since C++ doesn't define
what happens on signed integer overflow, we choose to make most of the
operators wrap on overflow for backward compatibility and consistency
with the rest of the ESSL spec.
We reuse the existing wrapping overflow helpers that are
used for constant folding. To be able to do this, the type used in the
preprocessor expression parser is changed from 64-bit to 32-bit.
Shifting negative numbers is implemented as a logical shift. This
cannot be disallowed since dEQP requires shaders shifting negative
numbers to pass compilation.
Undefined bitwise shifts where the offset is greater than 31 will now
result in a compile-time error.
A couple of test cases are now covered by the preprocessor tests
rather than full compilation tests. This isolates the tests better and
they run faster.
BUG=chromium:652223
TEST=angle_unittests
Change-Id: I84be40d404c10ecd0846c5d477e626a94a2a8587
Reviewed-on: https://chromium-review.googlesource.com/392146
Commit-Queue: Olli Etuaho <oetuaho@nvidia.com>
Reviewed-by: Jamie Madill <jmadill@chromium.org>
diff --git a/src/compiler/preprocessor/ExpressionParser.cpp b/src/compiler/preprocessor/ExpressionParser.cpp
index ddf810c..f737a2e 100644
--- a/src/compiler/preprocessor/ExpressionParser.cpp
+++ b/src/compiler/preprocessor/ExpressionParser.cpp
@@ -99,17 +99,15 @@
#include <cassert>
#include <sstream>
+#include <stdint.h>
#include "DiagnosticsBase.h"
#include "Lexer.h"
#include "Token.h"
+#include "common/mathutil.h"
-#if defined(_MSC_VER)
-typedef __int64 YYSTYPE;
-#else
-#include <stdint.h>
-typedef intmax_t YYSTYPE;
-#endif // _MSC_VER
+typedef int32_t YYSTYPE;
+typedef uint32_t UNSIGNED_TYPE;
#define YYENABLE_NLS 0
#define YYLTYPE_IS_TRIVIAL 1
@@ -500,9 +498,9 @@
/* YYRLINE[YYN] -- Source line where rule number YYN was defined. */
static const yytype_uint16 yyrline[] =
{
- 0, 110, 110, 117, 118, 129, 129, 150, 150, 171,
- 174, 177, 180, 183, 186, 189, 192, 195, 198, 218,
- 238, 241, 244, 264, 284, 287, 290, 293, 296, 299
+ 0, 108, 108, 115, 116, 127, 127, 148, 148, 169,
+ 172, 175, 178, 181, 184, 187, 190, 193, 196, 221,
+ 246, 249, 252, 272, 299, 302, 305, 308, 320, 323
};
#endif
@@ -1495,7 +1493,7 @@
case 18:
{
- if ((yyvsp[-1]) < 0 || (yyvsp[0]) < 0)
+ if ((yyvsp[0]) < 0 || (yyvsp[0]) > 31)
{
if (!context->isIgnoringErrors())
{
@@ -1509,6 +1507,11 @@
}
(yyval) = static_cast<YYSTYPE>(0);
}
+ else if ((yyvsp[-2]) < 0)
+ {
+ // Logical shift right.
+ (yyval) = static_cast<YYSTYPE>(static_cast<UNSIGNED_TYPE>((yyvsp[-2])) >> (yyvsp[0]));
+ }
else
{
(yyval) = (yyvsp[-2]) >> (yyvsp[0]);
@@ -1520,7 +1523,7 @@
case 19:
{
- if ((yyvsp[-1]) < 0 || (yyvsp[0]) < 0)
+ if ((yyvsp[0]) < 0 || (yyvsp[0]) > 31)
{
if (!context->isIgnoringErrors())
{
@@ -1534,6 +1537,11 @@
}
(yyval) = static_cast<YYSTYPE>(0);
}
+ else if ((yyvsp[-2]) < 0)
+ {
+ // Logical shift left.
+ (yyval) = static_cast<YYSTYPE>(static_cast<UNSIGNED_TYPE>((yyvsp[-2])) << (yyvsp[0]));
+ }
else
{
(yyval) = (yyvsp[-2]) << (yyvsp[0]);
@@ -1545,7 +1553,7 @@
case 20:
{
- (yyval) = (yyvsp[-2]) - (yyvsp[0]);
+ (yyval) = gl::WrappingDiff<YYSTYPE>((yyvsp[-2]), (yyvsp[0]));
}
break;
@@ -1553,7 +1561,7 @@
case 21:
{
- (yyval) = (yyvsp[-2]) + (yyvsp[0]);
+ (yyval) = gl::WrappingSum<YYSTYPE>((yyvsp[-2]), (yyvsp[0]));
}
break;
@@ -1600,6 +1608,13 @@
}
(yyval) = static_cast<YYSTYPE>(0);
}
+ else if ((yyvsp[-2]) == std::numeric_limits<YYSTYPE>::min() && (yyvsp[0]) == -1)
+ {
+ // Check for the special case where the minimum representable number is
+ // divided by -1. If left alone this leads to integer overflow in C++, which
+ // has undefined results.
+ (yyval) = std::numeric_limits<YYSTYPE>::max();
+ }
else
{
(yyval) = (yyvsp[-2]) / (yyvsp[0]);
@@ -1611,7 +1626,7 @@
case 24:
{
- (yyval) = (yyvsp[-2]) * (yyvsp[0]);
+ (yyval) = gl::WrappingMul((yyvsp[-2]), (yyvsp[0]));
}
break;
@@ -1635,7 +1650,16 @@
case 27:
{
- (yyval) = - (yyvsp[0]);
+ // Check for negation of minimum representable integer to prevent undefined signed int
+ // overflow.
+ if ((yyvsp[0]) == std::numeric_limits<YYSTYPE>::min())
+ {
+ (yyval) = std::numeric_limits<YYSTYPE>::min();
+ }
+ else
+ {
+ (yyval) = -(yyvsp[0]);
+ }
}
break;
diff --git a/src/compiler/preprocessor/ExpressionParser.y b/src/compiler/preprocessor/ExpressionParser.y
index 3f7fc62..a98638a 100644
--- a/src/compiler/preprocessor/ExpressionParser.y
+++ b/src/compiler/preprocessor/ExpressionParser.y
@@ -41,17 +41,15 @@
#include <cassert>
#include <sstream>
+#include <stdint.h>
#include "DiagnosticsBase.h"
#include "Lexer.h"
#include "Token.h"
+#include "common/mathutil.h"
-#if defined(_MSC_VER)
-typedef __int64 YYSTYPE;
-#else
-#include <stdint.h>
-typedef intmax_t YYSTYPE;
-#endif // _MSC_VER
+typedef int32_t YYSTYPE;
+typedef uint32_t UNSIGNED_TYPE;
#define YYENABLE_NLS 0
#define YYLTYPE_IS_TRIVIAL 1
@@ -196,7 +194,7 @@
$$ = $1 < $3;
}
| expression TOK_OP_RIGHT expression {
- if ($2 < 0 || $3 < 0)
+ if ($3 < 0 || $3 > 31)
{
if (!context->isIgnoringErrors())
{
@@ -210,13 +208,18 @@
}
$$ = static_cast<YYSTYPE>(0);
}
+ else if ($1 < 0)
+ {
+ // Logical shift right.
+ $$ = static_cast<YYSTYPE>(static_cast<UNSIGNED_TYPE>($1) >> $3);
+ }
else
{
$$ = $1 >> $3;
}
}
| expression TOK_OP_LEFT expression {
- if ($2 < 0 || $3 < 0)
+ if ($3 < 0 || $3 > 31)
{
if (!context->isIgnoringErrors())
{
@@ -230,16 +233,21 @@
}
$$ = static_cast<YYSTYPE>(0);
}
+ else if ($1 < 0)
+ {
+ // Logical shift left.
+ $$ = static_cast<YYSTYPE>(static_cast<UNSIGNED_TYPE>($1) << $3);
+ }
else
{
$$ = $1 << $3;
}
}
| expression '-' expression {
- $$ = $1 - $3;
+ $$ = gl::WrappingDiff<YYSTYPE>($1, $3);
}
| expression '+' expression {
- $$ = $1 + $3;
+ $$ = gl::WrappingSum<YYSTYPE>($1, $3);
}
| expression '%' expression {
if ($3 == 0)
@@ -276,13 +284,20 @@
}
$$ = static_cast<YYSTYPE>(0);
}
+ else if ($1 == std::numeric_limits<YYSTYPE>::min() && $3 == -1)
+ {
+ // Check for the special case where the minimum representable number is
+ // divided by -1. If left alone this leads to integer overflow in C++, which
+ // has undefined results.
+ $$ = std::numeric_limits<YYSTYPE>::max();
+ }
else
{
$$ = $1 / $3;
}
}
| expression '*' expression {
- $$ = $1 * $3;
+ $$ = gl::WrappingMul($1, $3);
}
| '!' expression %prec TOK_UNARY {
$$ = ! $2;
@@ -291,7 +306,16 @@
$$ = ~ $2;
}
| '-' expression %prec TOK_UNARY {
- $$ = - $2;
+ // Check for negation of minimum representable integer to prevent undefined signed int
+ // overflow.
+ if ($2 == std::numeric_limits<YYSTYPE>::min())
+ {
+ $$ = std::numeric_limits<YYSTYPE>::min();
+ }
+ else
+ {
+ $$ = -$2;
+ }
}
| '+' expression %prec TOK_UNARY {
$$ = + $2;
diff --git a/src/compiler/translator/ConstantUnion.cpp b/src/compiler/translator/ConstantUnion.cpp
index 90a0042..10a70f3 100644
--- a/src/compiler/translator/ConstantUnion.cpp
+++ b/src/compiler/translator/ConstantUnion.cpp
@@ -8,6 +8,7 @@
#include "compiler/translator/ConstantUnion.h"
#include "base/numerics/safe_math.h"
+#include "common/mathutil.h"
#include "compiler/translator/Diagnostics.h"
namespace
@@ -61,38 +62,6 @@
return result.ValueOrDefault(0);
}
-// Unsigned types are defined to do arithmetic modulo 2^n in C++. For signed types, overflow
-// behavior is undefined.
-
-template <typename T>
-T WrappingSum(T lhs, T rhs)
-{
- uint32_t lhsUnsigned = static_cast<uint32_t>(lhs);
- uint32_t rhsUnsigned = static_cast<uint32_t>(rhs);
- return static_cast<T>(lhsUnsigned + rhsUnsigned);
-}
-
-template <typename T>
-T WrappingDiff(T lhs, T rhs)
-{
- uint32_t lhsUnsigned = static_cast<uint32_t>(lhs);
- uint32_t rhsUnsigned = static_cast<uint32_t>(rhs);
- return static_cast<T>(lhsUnsigned - rhsUnsigned);
-}
-
-int32_t WrappingMul(int32_t lhs, int32_t rhs)
-{
- int64_t lhsWide = static_cast<int64_t>(lhs);
- int64_t rhsWide = static_cast<int64_t>(rhs);
- // The multiplication is guaranteed not to overflow.
- int64_t resultWide = lhsWide * rhsWide;
- // Implement the desired wrapping behavior by masking out the high-order 32 bits.
- resultWide = resultWide & 0xffffffffll;
- // Casting to a narrower signed type is fine since the casted value is representable in the
- // narrower type.
- return static_cast<int32_t>(resultWide);
-}
-
} // anonymous namespace
TConstantUnion::TConstantUnion()
@@ -315,10 +284,10 @@
switch (lhs.type)
{
case EbtInt:
- returnValue.setIConst(WrappingSum<int>(lhs.iConst, rhs.iConst));
+ returnValue.setIConst(gl::WrappingSum<int>(lhs.iConst, rhs.iConst));
break;
case EbtUInt:
- returnValue.setUConst(WrappingSum<unsigned int>(lhs.uConst, rhs.uConst));
+ returnValue.setUConst(gl::WrappingSum<unsigned int>(lhs.uConst, rhs.uConst));
break;
case EbtFloat:
returnValue.setFConst(CheckedSum<float>(lhs.fConst, rhs.fConst, diag, line));
@@ -341,10 +310,10 @@
switch (lhs.type)
{
case EbtInt:
- returnValue.setIConst(WrappingDiff<int>(lhs.iConst, rhs.iConst));
+ returnValue.setIConst(gl::WrappingDiff<int>(lhs.iConst, rhs.iConst));
break;
case EbtUInt:
- returnValue.setUConst(WrappingDiff<unsigned int>(lhs.uConst, rhs.uConst));
+ returnValue.setUConst(gl::WrappingDiff<unsigned int>(lhs.uConst, rhs.uConst));
break;
case EbtFloat:
returnValue.setFConst(CheckedDiff<float>(lhs.fConst, rhs.fConst, diag, line));
@@ -367,7 +336,7 @@
switch (lhs.type)
{
case EbtInt:
- returnValue.setIConst(WrappingMul(lhs.iConst, rhs.iConst));
+ returnValue.setIConst(gl::WrappingMul(lhs.iConst, rhs.iConst));
break;
case EbtUInt:
// Unsigned integer math in C++ is defined to be done in modulo 2^n, so we rely on that