5 files changed, 486 insertions, 16 deletions

diff --git a/common/algorithm.h b/common/algorithm.h
index 3a66efedba..06f2a279af 100644
--- a/common/algorithm.h
+++ b/common/algorithm.h
@@ -222,6 +222,19 @@ void sort(T first, T last) {
 	sort(first, last, Common::Less<typename T::ValueType>());
 }
 
+/**
+ * Euclid's algorithm to compute the greatest common divisor.
+ */
+template<class T>
+T gcd(T a, T b) {
+	while (a > 0) {
+		T tmp = a;
+		a = b % a;
+		b = tmp;
+	}
+	return b;
+}
+
 } // End of namespace Common
 #endif
 
diff --git a/common/module.mk b/common/module.mk
index 2bbb1eda76..83d30f0a9b 100644
--- a/common/module.mk
+++ b/common/module.mk
@@ -16,6 +16,7 @@ MODULE_OBJS := \
 	md5.o \
 	mutex.o \
 	random.o \
+	rational.o \
 	str.o \
 	stream.o \
 	system.o \
diff --git a/common/rational.cpp b/common/rational.cpp
new file mode 100644
index 0000000000..e27e880a04
--- /dev/null
+++ b/common/rational.cpp
@@ -0,0 +1,353 @@
+/* ScummVM - Graphic Adventure Engine
+ *
+ * ScummVM is the legal property of its developers, whose names
+ * are too numerous to list here. Please refer to the COPYRIGHT
+ * file distributed with this source distribution.
+ *
+ * This program is free software; you can redistribute it and/or
+ * modify it under the terms of the GNU General Public License
+ * as published by the Free Software Foundation; either version 2
+ * of the License, or (at your option) any later version.
+ *
+ * This program is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+ * GNU General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License
+ * along with this program; if not, write to the Free Software
+ * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.
+ *
+ * $URL$
+ * $Id$
+ */
+
+#include "common/rational.h"
+#include "common/util.h"
+#include "common/algorithm.h"
+
+namespace Common {
+
+Rational::Rational() {
+	_num   = 1;
+	_denom = 1;
+}
+
+Rational::Rational(int num) {
+	_num   = num;
+	_denom = 1;
+}
+
+Rational::Rational(int num, int denom) {
+	assert(denom != 0);
+
+	_num   = num;
+	_denom = denom;
+
+	normalize();
+}
+
+void Rational::cancel() {
+	// Cancel the fraction by dividing both the num and the denom
+	// by their greatest common denom.
+
+	int gcd = Common::gcd(_num, _denom);
+
+	_num   /= gcd;
+	_denom /= gcd;
+}
+
+void Rational::normalize() {
+	// Is the fraction negative?
+	bool negative = !((!(_num < 0)) == (!(_denom < 0)));
+
+	// Make both integers positive
+	_num   = ABS(_num);
+	_denom = ABS(_denom);
+
+	// Cancel the fraction
+	cancel();
+
+	// If the fraction is supposed to be negative, make the num negative
+	if (negative)
+		_num = -_num;
+}
+
+Rational &Rational::operator=(const Rational &right) {
+	_num   = right._num;
+	_denom = right._denom;
+
+	return *this;
+}
+
+Rational &Rational::operator=(int right) {
+	_num   = right;
+	_denom = 1;
+
+	return *this;
+}
+
+Rational &Rational::operator+=(const Rational &right) {
+	_num   = _num * right._denom + right._num * _denom;
+	_denom = _denom * right._denom;
+
+	normalize();
+
+	return *this;
+}
+
+Rational &Rational::operator-=(const Rational &right) {
+	_num   = _num * right._denom - right._num * _denom;
+	_denom = _denom * right._denom;
+
+	normalize();
+
+	return *this;
+}
+
+Rational &Rational::operator*=(const Rational &right) {
+	// Try to cross-cancel first, to avoid unnecessary overflow
+	int gcd1 = Common::gcd(_num, right._denom);
+	int gcd2 = Common::gcd(right._num, _denom);
+
+	_num   = (_num    / gcd1) * (right._num    / gcd2);
+	_denom = (_denom  / gcd2) * (right._denom  / gcd1);
+
+	normalize();
+
+	return *this;
+}
+
+Rational &Rational::operator/=(const Rational &right) {
+	return *this *= Rational(right._denom, right._num);
+}
+
+Rational &Rational::operator+=(int right) {
+	return *this += Rational(right);
+}
+
+Rational &Rational::operator-=(int right) {
+	return *this -= Rational(right);
+}
+
+Rational &Rational::operator*=(int right) {
+	return *this *= Rational(right);
+}
+
+Rational &Rational::operator/=(int right) {
+	return *this /= Rational(right);
+}
+
+const Rational Rational::operator-() const {
+	return Rational(-_num, _denom);
+}
+
+const Rational Rational::operator+(const Rational &right) const {
+	Rational tmp = *this;
+
+	tmp += right;
+
+	return tmp;
+}
+
+const Rational Rational::operator-(const Rational &right) const {
+	Rational tmp = *this;
+
+	tmp -= right;
+
+	return tmp;
+}
+
+const Rational Rational::operator*(const Rational &right) const {
+	Rational tmp = *this;
+
+	tmp *= right;
+
+	return tmp;
+}
+
+const Rational Rational::operator/(const Rational &right) const {
+	Rational tmp = *this;
+
+	tmp /= right;
+
+	return tmp;
+}
+
+const Rational Rational::operator+(int right) const {
+	Rational tmp = *this;
+
+	tmp += right;
+
+	return tmp;
+}
+
+const Rational Rational::operator-(int right) const {
+	Rational tmp = *this;
+
+	tmp -= right;
+
+	return tmp;
+}
+
+const Rational Rational::operator*(int right) const {
+	Rational tmp = *this;
+
+	tmp *= right;
+
+	return tmp;
+}
+
+const Rational Rational::operator/(int right) const {
+	Rational tmp = *this;
+
+	tmp /= right;
+
+	return tmp;
+}
+
+bool Rational::operator==(const Rational &right) const {
+	return (_num == right._num) && (_denom == right._denom);
+}
+
+bool Rational::operator!=(const Rational &right) const {
+	return (_num != right._num) || (_denom != right._denom);
+}
+
+bool Rational::operator>(const Rational &right) const {
+	return (_num * right._denom) > (right._num * _denom);
+}
+
+bool Rational::operator<(const Rational &right) const {
+	return (_num * right._denom) < (right._num * _denom);
+}
+
+bool Rational::operator>=(const Rational &right) const {
+	return (_num * right._denom) >= (right._num * _denom);
+}
+
+bool Rational::operator<=(const Rational &right) const {
+	return (_num * right._denom) <= (right._num * _denom);
+}
+
+bool Rational::operator==(int right) const {
+	return (_denom == 1) && (_num == right);
+}
+
+bool Rational::operator!=(int right) const {
+	return (_denom == 1) && (_num != right);
+}
+
+bool Rational::operator>(int right) const {
+	return *this > Rational(right, 1);
+}
+
+bool Rational::operator<(int right) const {
+	return *this < Rational(right, 1);
+}
+
+bool Rational::operator>=(int right) const {
+	return *this >= Rational(right, 1);
+}
+
+bool Rational::operator<=(int right) const {
+	return *this <= Rational(right, 1);
+}
+
+void Rational::invert() {
+	assert(_num != 0);
+
+	SWAP(_num, _denom);
+
+	normalize();
+}
+
+Rational Rational::getInverse() const {
+	Rational inverse = *this;
+
+	inverse.invert();
+
+	return inverse;
+}
+
+int Rational::toInt() const {
+	assert(_denom != 0);
+
+	return _num / _denom;
+}
+
+double Rational::toDouble() const {
+	assert(_denom != 0);
+
+	return ((double) _num) / ((double) _denom);
+}
+
+frac_t Rational::toFrac() const {
+	return (_num * FRAC_ONE) / _denom;
+}
+
+Rational::operator int() const {
+	return toInt();
+}
+
+Rational::operator double() const {
+	return toDouble();
+}
+
+const Rational operator+(int left, const Rational &right) {
+	Rational tmp = right;
+
+	tmp += left;
+
+	return tmp;
+}
+
+const Rational operator-(int left, const Rational &right) {
+	Rational tmp = right;
+
+	tmp -= left;
+
+	return tmp;
+}
+
+const Rational operator*(int left, const Rational &right) {
+	Rational tmp = right;
+
+	tmp *= left;
+
+	return tmp;
+}
+
+const Rational operator/(int left, const Rational &right) {
+	Rational tmp = right;
+
+	tmp /= left;
+
+	return tmp;
+}
+
+bool operator==(int left, const Rational &right) {
+	return right == left;
+}
+
+bool operator!=(int left, const Rational &right) {
+	return right != left;
+}
+
+bool operator>(int left, const Rational &right) {
+	return right < left;
+}
+
+bool operator<(int left, const Rational &right) {
+	return right > left;
+}
+
+bool operator>=(int left, const Rational &right) {
+	return right <= left;
+}
+
+bool operator<=(int left, const Rational &right) {
+	return right >= left;
+}
+
+} // End of namespace Common
diff --git a/common/rational.h b/common/rational.h
new file mode 100644
index 0000000000..1ad33de8a6
--- /dev/null
+++ b/common/rational.h
@@ -0,0 +1,111 @@
+/* ScummVM - Graphic Adventure Engine
+ *
+ * ScummVM is the legal property of its developers, whose names
+ * are too numerous to list here. Please refer to the COPYRIGHT
+ * file distributed with this source distribution.
+ *
+ * This program is free software; you can redistribute it and/or
+ * modify it under the terms of the GNU General Public License
+ * as published by the Free Software Foundation; either version 2
+ * of the License, or (at your option) any later version.
+ *
+ * This program is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+ * GNU General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License
+ * along with this program; if not, write to the Free Software
+ * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.
+ *
+ * $URL$
+ * $Id$
+ */
+
+#ifndef COMMON_RATIONAL_H
+#define COMMON_RATIONAL_H
+
+#include "common/scummsys.h"
+#include "common/frac.h"
+
+namespace Common {
+
+/** A simple rational class that holds fractions. */
+class Rational {
+public:
+	Rational();
+	Rational(int num);
+	Rational(int num, int denom);
+
+	Rational &operator=(const Rational &right);
+	Rational &operator=(int right);
+
+	Rational &operator+=(const Rational &right);
+	Rational &operator-=(const Rational &right);
+	Rational &operator*=(const Rational &right);
+	Rational &operator/=(const Rational &right);
+
+	Rational &operator+=(int right);
+	Rational &operator-=(int right);
+	Rational &operator*=(int right);
+	Rational &operator/=(int right);
+
+	const Rational operator-() const;
+
+	const Rational operator+(const Rational &right) const;
+	const Rational operator-(const Rational &right) const;
+	const Rational operator*(const Rational &right) const;
+	const Rational operator/(const Rational &right) const;
+
+	const Rational operator+(int right) const;
+	const Rational operator-(int right) const;
+	const Rational operator*(int right) const;
+	const Rational operator/(int right) const;
+
+	bool operator==(const Rational &right) const;
+	bool operator!=(const Rational &right) const;
+	bool operator>(const Rational &right) const;
+	bool operator<(const Rational &right) const;
+	bool operator>=(const Rational &right) const;
+	bool operator<=(const Rational &right) const;
+
+	bool operator==(int right) const;
+	bool operator!=(int right) const;
+	bool operator>(int right) const;
+	bool operator<(int right) const;
+	bool operator>=(int right) const;
+	bool operator<=(int right) const;
+
+	operator int() const;
+	operator double() const;
+
+	void invert();
+	Rational getInverse() const;
+
+	int toInt() const;
+	double toDouble() const;
+	frac_t toFrac() const;
+
+private:
+	int _num;
+	int _denom;
+
+	void cancel();
+	void normalize();
+};
+
+const Rational operator+(int left, const Rational &right);
+const Rational operator-(int left, const Rational &right);
+const Rational operator*(int left, const Rational &right);
+const Rational operator/(int left, const Rational &right);
+
+bool operator==(int left, const Rational &right);
+bool operator!=(int left, const Rational &right);
+bool operator>(int left, const Rational &right);
+bool operator<(int left, const Rational &right);
+bool operator>=(int left, const Rational &right);
+bool operator<=(int left, const Rational &right);
+
+} // End of namespace Common
+
+#endif
diff --git a/sound/timestamp.cpp b/sound/timestamp.cpp
index f705ff4521..1eb5483fc2 100644
--- a/sound/timestamp.cpp
+++ b/sound/timestamp.cpp
@@ -24,23 +24,15 @@
  */
 
 #include "sound/timestamp.h"
+#include "common/algorithm.h"
 
 namespace Audio {
 
-static uint gcd(uint a, uint b) {
-	while (a > 0) {
-		int tmp = a;
-		a = b % a;
-		b = tmp;
-	}
-	return b;
-}
-
 Timestamp::Timestamp(uint ms, uint fr) {
 	assert(fr > 0);
 
 	_secs = ms / 1000;
-	_framerateFactor = 1000 / gcd(1000, fr);
+	_framerateFactor = 1000 / Common::gcd<uint>(1000, fr);
 	_framerate = fr * _framerateFactor;
 
 	// Note that _framerate is always divisible by 1000.
@@ -51,7 +43,7 @@ Timestamp::Timestamp(uint s, uint frames, uint fr) {
 	assert(fr > 0);
 
 	_secs = s;
-	_framerateFactor = 1000 / gcd(1000, fr);
+	_framerateFactor = 1000 / Common::gcd<uint>(1000, fr);
 	_framerate = fr * _framerateFactor;
 	_numFrames = frames * _framerateFactor;
 
@@ -62,10 +54,10 @@ Timestamp Timestamp::convertToFramerate(uint newFramerate) const {
 	Timestamp ts(*this);
 
 	if (ts.framerate() != newFramerate) {
-		ts._framerateFactor = 1000 / gcd(1000, newFramerate);
+		ts._framerateFactor = 1000 / Common::gcd<uint>(1000, newFramerate);
 		ts._framerate = newFramerate * ts._framerateFactor;
 
-		const uint g = gcd(_framerate, ts._framerate);
+		const uint g = Common::gcd(_framerate, ts._framerate);
 		const uint p = _framerate / g;
 		const uint q = ts._framerate / g;
 
@@ -122,7 +114,7 @@ bool Timestamp::operator>=(const Timestamp &ts) const {
 int Timestamp::cmp(const Timestamp &ts) const {
 	int delta = _secs - ts._secs;
 	if (!delta) {
-		const uint g = gcd(_framerate, ts._framerate);
+		const uint g = Common::gcd(_framerate, ts._framerate);
 		const uint p = _framerate / g;
 		const uint q = ts._framerate / g;
 
@@ -164,7 +156,7 @@ void Timestamp::addIntern(const Timestamp &ts) {
 		// We need to multiply by the quotient of the two framerates.
 		// We cancel the GCD in this fraction to reduce the risk of
 		// overflows.
-		const uint g = gcd(_framerate, ts._framerate);
+		const uint g = Common::gcd(_framerate, ts._framerate);
 		const uint p = _framerate / g;
 		const uint q = ts._framerate / g;
 
@@ -227,7 +219,7 @@ int Timestamp::frameDiff(const Timestamp &ts) const {
 		// We need to multiply by the quotient of the two framerates.
 		// We cancel the GCD in this fraction to reduce the risk of
 		// overflows.
-		const uint g = gcd(_framerate, ts._framerate);
+		const uint g = Common::gcd(_framerate, ts._framerate);
 		const uint p = _framerate / g;
 		const uint q = ts._framerate / g;