From 97bfd60e61991be9ed6686d6eb70370a901d4371 Mon Sep 17 00:00:00 2001
From: Max Horn
Date: Wed, 9 Feb 2011 00:12:02 +0000
Subject: COMMON: Reduce overflow risk in Common::Rational += and -= operators

svn-id: r55839
---
 common/rational.cpp    | 26 +++++++++++++++++++-------
 test/common/rational.h | 16 ++++++++++++++++
 2 files changed, 35 insertions(+), 7 deletions(-)

diff --git a/common/rational.cpp b/common/rational.cpp
index f55c2dcfe3..af38dd9144 100644
--- a/common/rational.cpp
+++ b/common/rational.cpp
@@ -57,7 +57,7 @@ void Rational::cancel() {
 	// Cancel the fraction by dividing both the num and the denom
 	// by their greatest common divisor.
 
-	int gcd = Common::gcd(_num, _denom);
+	const int gcd = Common::gcd(_num, _denom);
 
 	_num   /= gcd;
 	_denom /= gcd;
@@ -78,8 +78,14 @@ Rational &Rational::operator=(int right) {
 }
 
 Rational &Rational::operator+=(const Rational &right) {
-	_num   = _num * right._denom + right._num * _denom;
-	_denom = _denom * right._denom;
+	// Cancel common factors to avoid unnecessary overflow.
+	// Note that the result is *not* always normalized.
+	const int gcd = Common::gcd(_denom, right._denom);
+
+	_num    = _num * (right._denom / gcd);
+	_denom  = _denom / gcd;
+	_num   += right._num * _denom;
+	_denom *= right._denom;
 
 	cancel();
 
@@ -87,8 +93,14 @@ Rational &Rational::operator+=(const Rational &right) {
 }
 
 Rational &Rational::operator-=(const Rational &right) {
-	_num   = _num * right._denom - right._num * _denom;
-	_denom = _denom * right._denom;
+	// Cancel common factors to avoid unnecessary overflow.
+	// Note that the result is *not* always normalized.
+	const int gcd = Common::gcd(_denom, right._denom);
+
+	_num    = _num * (right._denom / gcd);
+	_denom  = _denom / gcd;
+	_num   -= right._num * _denom;
+	_denom *= right._denom;
 
 	cancel();
 
@@ -98,8 +110,8 @@ Rational &Rational::operator-=(const Rational &right) {
 Rational &Rational::operator*=(const Rational &right) {
 	// Cross-cancel to avoid unnecessary overflow;
 	// the result then is automatically normalized
-	int gcd1 = Common::gcd(_num, right._denom);
-	int gcd2 = Common::gcd(right._num, _denom);
+	const int gcd1 = Common::gcd(_num, right._denom);
+	const int gcd2 = Common::gcd(right._num, _denom);
 
 	_num   = (_num    / gcd1) * (right._num    / gcd2);
 	_denom = (_denom  / gcd2) * (right._denom  / gcd1);
diff --git a/test/common/rational.h b/test/common/rational.h
index 21b84a8a41..46dfc278c7 100644
--- a/test/common/rational.h
+++ b/test/common/rational.h
@@ -86,6 +86,22 @@ public:
 		TS_ASSERT_EQUALS(r1 - 1, Common::Rational(-1, 2));
 	}
 
+	void test_add_sub2() {
+		// Make sure cancelation works correctly
+		const Common::Rational r0(4, 15);	// = 8 / 30
+		const Common::Rational r1(1, 6);	// = 5 / 30
+
+		TS_ASSERT_EQUALS(r0 + r1, Common::Rational(13, 30));
+		TS_ASSERT_EQUALS(r1 + r0, Common::Rational(13, 30));
+		TS_ASSERT_EQUALS(r0 - r1, Common::Rational(1, 10));
+		TS_ASSERT_EQUALS(r1 - r0, Common::Rational(-1, 10));
+
+		TS_ASSERT_EQUALS(1 + r1, Common::Rational(7, 6));
+		TS_ASSERT_EQUALS(r1 + 1, Common::Rational(7, 6));
+		TS_ASSERT_EQUALS(1 - r1, Common::Rational(5, 6));
+		TS_ASSERT_EQUALS(r1 - 1, Common::Rational(-5, 6));
+	}
+
 	void test_mul() {
 		const Common::Rational r0(6, 3);
 		const Common::Rational r1(1, 2);
-- 
cgit v1.2.3