From: Daniel Karbach <daniel.karbach@localhorst.tv>
Date: Thu, 27 Dec 2012 11:23:51 +0000 (+0100)
Subject: added fixed point number type
X-Git-Url: http://git.localhorst.tv/?p=l2e.git;a=commitdiff_plain;h=06db9f596cd1c5aa4c0832b387882f7c74c1b4c0

added fixed point number type
---

diff --git a/l2e.cbp b/l2e.cbp
index 7329d8a..d072ddd 100644
--- a/l2e.cbp
+++ b/l2e.cbp
@@ -192,8 +192,10 @@
 		<Unit filename="src\map\Trigger.cpp" />
 		<Unit filename="src\map\Trigger.h" />
 		<Unit filename="src\map\fwd.h" />
+		<Unit filename="src\math\Fixed.h" />
 		<Unit filename="src\math\Vector.h" />
 		<Unit filename="src\math\fwd.h" />
+		<Unit filename="src\math\utility.h" />
 		<Unit filename="src\menu\CapsuleChangeMenu.cpp" />
 		<Unit filename="src\menu\CapsuleChangeMenu.h" />
 		<Unit filename="src\menu\CapsuleFeedMenu.cpp" />
diff --git a/src/math/Fixed.h b/src/math/Fixed.h
new file mode 100644
index 0000000..a398275
--- /dev/null
+++ b/src/math/Fixed.h
@@ -0,0 +1,363 @@
+#ifndef MATH_FIXED_H_
+#define MATH_FIXED_H_
+
+#include "utility.h"
+
+#include <cmath>
+#include <limits>
+#include <ostream>
+#include <SDL.h>
+
+
+namespace math {
+
+/// Fixed point number type.
+/// The first bit is used for the sign (0 = positive, 1 = negative), the last
+/// fracBits bits are used for the fractional part and the remaining middle
+/// bits represent the integer value.
+/// The sign bit of zero is undefined.
+template<Uint8 fracBits>
+class Fixed {
+
+template<Uint8>
+friend class Fixed;
+
+public:
+	/// Create a fixed point decimal representing i/f .
+	Fixed(Sint32 i = 0, Uint32 f = 1)
+	: rep(((i < 0 ? (i * -1) : i) << IntShift()) & IntMask()) {
+		rep /= f;
+		if (i < 0) {
+			rep |= SignMask();
+		}
+	}
+	explicit Fixed(double d)
+	: rep(0) {
+		rep = std::abs(d) * (1 << IntShift());
+		if (d < 0) {
+			rep |= SignMask();
+		}
+	}
+	template<Uint8 otherFrac>
+	explicit Fixed(const Fixed<otherFrac> &other)
+	: rep(0) {
+		Uint32 otherInt = other.RawInt();
+		rep = DistanceShift(otherInt, fracBits, otherFrac);
+		if (other.Sigma() < 0) {
+			rep |= SignMask();
+		}
+	}
+
+public:
+	int Int() const { return IntPart() * Sigma(); }
+	int Sigma() const {
+		if (IntPart() == 0 && FracPart() == 0) {
+			return 0;
+		} else if (SignPart() == 0) {
+			return 1;
+		} else {
+			return -1;
+		}
+	}
+	double Double() const { return double(SignedInt()) / (1 << IntShift()); }
+
+public:
+	bool operator ==(const Fixed &other) const {
+		return rep == other.rep;
+	}
+	bool operator !=(const Fixed &other) const {
+		return rep != other.rep;
+	}
+	bool operator <(const Fixed &other) const {
+		return SignedInt() < other.SignedInt();
+	}
+	bool operator <=(const Fixed &other) const {
+		return SignedInt() <= other.SignedInt();
+	}
+	bool operator >(const Fixed &other) const {
+		return SignedInt() > other.SignedInt();
+	}
+	bool operator >=(const Fixed &other) const {
+		return SignedInt() >= other.SignedInt();
+	}
+
+	Fixed operator -() const {
+		Fixed neg;
+		neg.rep = rep ^ SignMask();
+		return neg;
+	}
+
+	Fixed &operator +=(const Fixed &other) {
+		Sint32 temp = SignedInt() + other.SignedInt();
+		if (temp < 0) {
+			rep = (temp * -1) | SignMask();
+		} else {
+			rep = temp;
+		}
+		return *this;
+	}
+	Fixed &operator +=(int i) {
+		Sint32 temp = SignedInt() + (i << IntShift());
+		if (temp < 0) {
+			rep = (temp * -1) | SignMask();
+		} else {
+			rep = temp;
+		}
+		return *this;
+	}
+	Fixed &operator -=(const Fixed &other) {
+		Sint32 temp = SignedInt() - other.SignedInt();
+		if (temp < 0) {
+			rep = (temp * -1) | SignMask();
+		} else {
+			rep = temp;
+		}
+		return *this;
+	}
+	Fixed &operator -=(int i) {
+		Sint32 temp = SignedInt() - (i << IntShift());
+		if (temp < 0) {
+			rep = (temp * -1) | SignMask();
+		} else {
+			rep = temp;
+		}
+		return *this;
+	}
+	Fixed &operator *=(const Fixed &other) {
+		Sint64 temp = SignedInt();
+		temp *= other.SignedInt();
+		temp /= (1 << IntShift());
+		if (temp < 0) {
+			rep = (temp * -1) | SignMask();
+		} else {
+			rep = temp;
+		}
+		return *this;
+	}
+	Fixed &operator *=(int i) {
+		Sint32 temp = SignedInt() * i;
+		if (temp < 0) {
+			rep = (temp * -1) | SignMask();
+		} else {
+			rep = temp;
+		}
+		return *this;
+	}
+	Fixed &operator /=(const Fixed &other) {
+		Sint64 temp = SignedInt();
+		temp *= (1 << IntShift());
+		temp /= other.SignedInt();
+		if (temp < 0) {
+			rep = (temp * -1) | SignMask();
+		} else {
+			rep = temp;
+		}
+		return *this;
+	}
+	Fixed &operator /=(int i) {
+		Sint32 temp = SignedInt() / i;
+		if (temp < 0) {
+			rep = (temp * -1) | SignMask();
+		} else {
+			rep = temp;
+		}
+		return *this;
+	}
+	Fixed &operator %=(const Fixed &other) {
+		const Uint32 myRaw = RawInt();
+		const Uint32 otherRaw = other.RawInt();
+		const Uint32 intQuotient = myRaw / otherRaw;
+		rep = (myRaw - (otherRaw  * intQuotient)) | (rep & SignMask());
+		return *this;
+	}
+	Fixed &operator %=(int i) {
+		const Uint32 myRaw = RawInt();
+		const Uint32 otherRaw = (i << IntShift());
+		const Uint32 intQuotient = myRaw / otherRaw;
+		rep = (myRaw - (otherRaw  * intQuotient)) | (rep & SignMask());
+		return *this;
+	}
+
+private:
+	int SignBits() const { return 1; }
+	int IntBits() const { return 32 - SignBits() - FracBits(); }
+	int FracBits() const { return fracBits; }
+
+	int SignShift() const { return 31; }
+	int IntShift() const { return fracBits; }
+	int FracShift() const { return 0; }
+
+	Uint32 SignMask() const { return 1 << SignShift(); }
+	Uint32 IntMask() const { return ~(SignMask() | FracMask()); }
+	Uint32 FracMask() const { return (1 << IntShift()) - 1; }
+
+	int SignPart() const { return (rep & SignMask()) >> SignShift(); }
+	int IntPart() const { return (rep & IntMask()) >> IntShift(); }
+	int FracPart() const { return (rep & FracMask()) >> FracShift(); }
+
+	Sint32 SignedInt() const { return Sigma() * RawInt(); }
+	Uint32 RawInt() const { return rep & (~SignMask()); }
+
+private:
+	Uint32 rep;
+
+};
+
+
+template<Uint8 T, Uint8 U>
+inline bool operator ==(const Fixed<T> &lhs, const Fixed<U> &rhs) {
+	if (T < U) {
+		return lhs == Fixed<T>(rhs);
+	} else {
+		return Fixed<U>(lhs) == rhs;
+	}
+}
+
+template<Uint8 T, Uint8 U>
+inline bool operator !=(const Fixed<T> &lhs, const Fixed<U> &rhs) {
+	return !(lhs == rhs);
+}
+
+template<Uint8 T, Uint8 U>
+inline bool operator <(const Fixed<T> &lhs, const Fixed<U> &rhs) {
+	if (T < U) {
+		return lhs < Fixed<T>(rhs);
+	} else {
+		return Fixed<U>(lhs) < rhs;
+	}
+}
+
+template<Uint8 T, Uint8 U>
+inline bool operator <=(const Fixed<T> &lhs, const Fixed<U> &rhs) {
+	if (T < U) {
+		return lhs <= Fixed<T>(rhs);
+	} else {
+		return Fixed<U>(lhs) <= rhs;
+	}
+}
+
+template<Uint8 T, Uint8 U>
+inline bool operator >(const Fixed<T> &lhs, const Fixed<U> &rhs) {
+	return !(lhs <= rhs);
+}
+
+template<Uint8 T, Uint8 U>
+inline bool operator >=(const Fixed<T> &lhs, const Fixed<U> &rhs) {
+	return !(lhs < rhs);
+}
+
+template<Uint8 T, Uint8 U>
+inline Fixed<T> operator +(const Fixed<T> &lhs, const Fixed<U> &rhs) {
+	Fixed<T> temp(lhs);
+	return temp += rhs;
+}
+template<Uint8 T, class Other>
+inline Fixed<T> operator +(const Fixed<T> &lhs, const Other &rhs) {
+	Fixed<T> temp(lhs);
+	return temp += rhs;
+}
+template<Uint8 T, class Other>
+inline Fixed<T> operator +(const Other &lhs, const Fixed<T> &rhs) {
+	return rhs + lhs;
+}
+
+template<Uint8 T, Uint8 U>
+inline Fixed<T> operator -(const Fixed<T> &lhs, const Fixed<U> &rhs) {
+	Fixed<T> temp(lhs);
+	return temp -= rhs;
+}
+template<Uint8 T, class Other>
+inline Fixed<T> operator -(const Fixed<T> &lhs, const Other &rhs) {
+	Fixed<T> temp(lhs);
+	return temp -= rhs;
+}
+template<Uint8 T, class Other>
+inline Fixed<T> operator -(const Other &lhs, const Fixed<T> &rhs) {
+	return lhs + -rhs;
+}
+
+template<Uint8 T, Uint8 U>
+inline Fixed<T> operator *(const Fixed<T> &lhs, const Fixed<U> &rhs) {
+	Fixed<T> temp(lhs);
+	return temp *= rhs;
+}
+template<Uint8 T, class Other>
+inline Fixed<T> operator *(const Fixed<T> &lhs, const Other &rhs) {
+	Fixed<T> temp(lhs);
+	return temp *= rhs;
+}
+template<Uint8 T, class Other>
+inline Fixed<T> operator *(const Other &lhs, const Fixed<T> &rhs) {
+	return rhs * lhs;
+}
+
+template<Uint8 T, Uint8 U>
+inline Fixed<T> operator /(const Fixed<T> &lhs, const Fixed<U> &rhs) {
+	Fixed<T> temp(lhs);
+	return temp /= rhs;
+}
+template<Uint8 T, class Other>
+inline Fixed<T> operator /(const Fixed<T> &lhs, const Other &rhs) {
+	Fixed<T> temp(lhs);
+	return temp /= rhs;
+}
+
+template<Uint8 T, Uint8 U>
+inline Fixed<T> operator %(const Fixed<T> &lhs, const Fixed<U> &rhs) {
+	Fixed<T> temp(lhs);
+	return temp %= rhs;
+}
+template<Uint8 T, class Other>
+inline Fixed<T> operator %(const Fixed<T> &lhs, const Other &rhs) {
+	Fixed<T> temp(lhs);
+	return temp %= rhs;
+}
+
+
+template<Uint8 T>
+inline std::ostream &operator <<(std::ostream &out, const Fixed<T> &f) {
+	return out << f.Double();
+}
+
+}
+
+
+namespace std {
+
+template <Uint8 fracBits>
+class numeric_limits<math::Fixed<fracBits> > {
+
+public:
+	static const bool is_specialized = true;
+	static math::Fixed<fracBits> min() throw() {
+		return max() * -1;
+	}
+	static math::Fixed<fracBits> max() throw() {
+		return math::Fixed<fracBits>(1 << (digits - fracBits) - 1)
+				+ math::Fixed<fracBits>((1 << fracBits) - 2, (1 << fracBits) - 1);
+	}
+	static const int digits = 31;
+	static const int digits10 = 10;
+	static const bool is_signed = true;
+	static const bool is_integer = false;
+	static const bool is_exact = true;
+	static const int radix = 2;
+	static math::Fixed<fracBits> epsilon() throw() {
+		return math::Fixed<fracBits>(1, 1 << (digits - fracBits) - 1);
+	}
+	static math::Fixed<fracBits> round_error() throw() {
+		return epsilon();
+	}
+
+	static const bool is_iec559 = false;
+	static const bool is_bounded = true;
+	static const bool is_modulo = false;
+
+	static const bool traps = false;
+	static const bool tinyness_before = false;
+	static const float_round_style round_style = round_toward_zero;
+};
+
+}
+
+#endif
diff --git a/src/math/Vector.h b/src/math/Vector.h
index fb07d33..6cb9ba3 100644
--- a/src/math/Vector.h
+++ b/src/math/Vector.h
@@ -1,6 +1,8 @@
 #ifndef MATH_VECTOR_H_
 #define MATH_VECTOR_H_
 
+#include "Fixed.h"
+
 #include <cmath>
 #include <limits>
 #include <ostream>
@@ -16,7 +18,7 @@ public:
 	Vector() : x(0), y(0) { }
 	Vector(Scalar x, Scalar y) : x(x), y(y) { }
 	template<class T>
-	Vector(const Vector<T> &other) : x(other.X()), y(other.Y()) { };
+	Vector(const Vector<T> &other) : x(other.X()), y(other.Y()) { }
 	template<class T>
 	Vector(T x, T y) : x(x), y(y) { }
 
@@ -85,8 +87,8 @@ template<class T>
 inline Vector<T> operator *(const Vector<T> &v1, const Vector<T> &v2) {
 	return Vector<T>(v1.X() * v2.X(), v1.Y() * v2.Y());
 }
-template<class T>
-inline Vector<T> operator *(const Vector<T> &v, T s) {
+template<class T, class U>
+inline Vector<T> operator *(const Vector<T> &v, U s) {
 	return Vector<T>(v.X() * s, v.Y() * s);
 }
 template<class T>
@@ -176,6 +178,16 @@ void Vector<Scalar>::Lock(const Vector<Scalar> &to) {
 }
 
 
+template<Uint8 i>
+Vector<int> ToInt(const Vector<Fixed<i> > &v) {
+	return Vector<int>(v.X().Int(), v.Y().Int());
+}
+template<Uint8 i>
+Vector<Fixed<i> > ToFixed(const Vector<int> &v) {
+	return Vector<Fixed<i> >(v.X(), v.Y());
+}
+
+
 }
 
-#endif /* GEOMETRY_VECTOR_H_ */
+#endif
diff --git a/src/math/fwd.h b/src/math/fwd.h
index 9e143fd..618c8cc 100644
--- a/src/math/fwd.h
+++ b/src/math/fwd.h
@@ -1,8 +1,12 @@
 #ifndef MATH_FWD_H_
 #define MATH_FWD_H_
 
+#include <SDL.h>
+
 namespace math {
 
+template<Uint8 fracBits>
+class Fixed;
 template<class Scalar>
 class Vector;
 
diff --git a/src/math/utility.h b/src/math/utility.h
new file mode 100644
index 0000000..2111df0
--- /dev/null
+++ b/src/math/utility.h
@@ -0,0 +1,18 @@
+#ifndef MATH_UTILITY_H_
+#define MATH_UTILITY_H_
+
+
+namespace math {
+
+template<class Int>
+Int DistanceShift(Int what, int lhs, int rhs) {
+	if (lhs < rhs) {
+		return what >> (rhs - lhs);
+	} else {
+		return what << (lhs - rhs);
+	}
+}
+
+}
+
+#endif
diff --git a/tests/math/FixedTest.cpp b/tests/math/FixedTest.cpp
new file mode 100644
index 0000000..a81534b
--- /dev/null
+++ b/tests/math/FixedTest.cpp
@@ -0,0 +1,117 @@
+#include "FixedTest.h"
+
+CPPUNIT_TEST_SUITE_REGISTRATION(test_math::FixedTest);
+
+typedef math::Fixed<16> Fixed;
+typedef math::Fixed<8> LowerFixed;
+typedef math::Fixed<24> HigherFixed;
+
+
+namespace test_math {
+
+void FixedTest::setUp() {
+
+}
+
+void FixedTest::tearDown() {
+
+}
+
+
+void FixedTest::testConversion() {
+	CPPUNIT_ASSERT_EQUAL(1, Fixed(3, 2).Int());
+	CPPUNIT_ASSERT_DOUBLES_EQUAL(0.75, Fixed(3, 4).Double(), std::numeric_limits<double>::epsilon());
+
+	CPPUNIT_ASSERT_EQUAL(-1, Fixed(-3, 2).Int());
+	CPPUNIT_ASSERT_DOUBLES_EQUAL(-1.25, Fixed(-5, 4).Double(), std::numeric_limits<double>::epsilon());
+
+	CPPUNIT_ASSERT_EQUAL(Fixed(3, 2), Fixed(1.5));
+	CPPUNIT_ASSERT_EQUAL(Fixed(-4, 10), Fixed(-0.4));
+
+	CPPUNIT_ASSERT_EQUAL(Fixed(3, 2), Fixed(HigherFixed(3, 2)));
+	CPPUNIT_ASSERT_EQUAL(Fixed(3, 2), Fixed(LowerFixed(3, 2)));
+}
+
+void FixedTest::testComparison() {
+	CPPUNIT_ASSERT_EQUAL(Fixed(), Fixed());
+	CPPUNIT_ASSERT_EQUAL(Fixed(1), Fixed(1));
+	CPPUNIT_ASSERT_EQUAL(Fixed(-1), Fixed(-1));
+
+	CPPUNIT_ASSERT_EQUAL(Fixed(1, 2), Fixed(2, 4));
+
+	CPPUNIT_ASSERT(Fixed(0) != Fixed(1));
+	CPPUNIT_ASSERT(Fixed(0) != Fixed(-1));
+	CPPUNIT_ASSERT(Fixed(1, 2) != Fixed(-1, 2));
+
+	CPPUNIT_ASSERT(Fixed(0) < Fixed(1));
+	CPPUNIT_ASSERT(Fixed(1, 2) <= Fixed(1));
+	CPPUNIT_ASSERT(Fixed(0) > Fixed(-1));
+	CPPUNIT_ASSERT(Fixed(1) >= Fixed(-1, 2));
+
+	CPPUNIT_ASSERT(Fixed() == LowerFixed());
+	CPPUNIT_ASSERT(Fixed() == HigherFixed());
+	CPPUNIT_ASSERT(Fixed(1) == LowerFixed(1));
+	CPPUNIT_ASSERT(Fixed(1) == HigherFixed(1));
+	CPPUNIT_ASSERT(Fixed(-1) == LowerFixed(-1));
+	CPPUNIT_ASSERT(Fixed(-1) == HigherFixed(-1));
+
+	CPPUNIT_ASSERT(Fixed(1, 2) == LowerFixed(2, 4));
+	CPPUNIT_ASSERT(Fixed(1, 2) == HigherFixed(2, 4));
+
+	CPPUNIT_ASSERT(Fixed(0) != LowerFixed(1));
+	CPPUNIT_ASSERT(Fixed(0) != HigherFixed(1));
+	CPPUNIT_ASSERT(Fixed(0) != LowerFixed(-1));
+	CPPUNIT_ASSERT(Fixed(0) != HigherFixed(-1));
+	CPPUNIT_ASSERT(Fixed(1, 2) != LowerFixed(-1, 2));
+	CPPUNIT_ASSERT(Fixed(1, 2) != HigherFixed(-1, 2));
+
+	CPPUNIT_ASSERT(Fixed(0) < LowerFixed(1));
+	CPPUNIT_ASSERT(Fixed(0) < HigherFixed(1));
+	CPPUNIT_ASSERT(Fixed(1, 2) <= LowerFixed(1));
+	CPPUNIT_ASSERT(Fixed(1, 2) <= HigherFixed(1));
+	CPPUNIT_ASSERT(Fixed(0) > LowerFixed(-1));
+	CPPUNIT_ASSERT(Fixed(0) > HigherFixed(-1));
+	CPPUNIT_ASSERT(Fixed(1) >= LowerFixed(-1, 2));
+	CPPUNIT_ASSERT(Fixed(1) >= HigherFixed(-1, 2));
+}
+
+void FixedTest::testSum() {
+	CPPUNIT_ASSERT_EQUAL(
+			Fixed(3, 4),
+			Fixed(1, 4) + Fixed(1, 2));
+	CPPUNIT_ASSERT_EQUAL(
+				Fixed(6, 4),
+				Fixed(2) - Fixed(0.5));
+}
+
+void FixedTest::testProduct() {
+	CPPUNIT_ASSERT_EQUAL(
+			Fixed(5),
+			Fixed(2) * Fixed(2.5));
+	CPPUNIT_ASSERT_EQUAL(
+			Fixed(-1.7499999999),
+			Fixed(3, 4) * Fixed(-7, 3));
+	CPPUNIT_ASSERT_EQUAL(
+			Fixed(4),
+			Fixed(2) / Fixed(0.5));
+	CPPUNIT_ASSERT_EQUAL(
+			Fixed(3),
+			Fixed(15) / Fixed(5));
+}
+
+void FixedTest::testModulo() {
+	CPPUNIT_ASSERT_EQUAL(
+			Fixed(5),
+			Fixed(5) % 6);
+	CPPUNIT_ASSERT_EQUAL(
+			Fixed(5),
+			Fixed(11) % Fixed(6));
+	CPPUNIT_ASSERT_EQUAL(
+			Fixed(2.5),
+			Fixed(7.5) % 5);
+	CPPUNIT_ASSERT_EQUAL(
+			Fixed(0.5),
+			Fixed(8) % Fixed(7.5));
+}
+
+}
diff --git a/tests/math/FixedTest.h b/tests/math/FixedTest.h
new file mode 100644
index 0000000..8b0c8bb
--- /dev/null
+++ b/tests/math/FixedTest.h
@@ -0,0 +1,38 @@
+#ifndef TEST_MATH_FIXEDTEST_H_
+#define TEST_MATH_FIXEDTEST_H_
+
+#include "../../src/math/Fixed.h"
+
+#include <cmath>
+#include <limits>
+#include <cppunit/extensions/HelperMacros.h>
+
+
+namespace test_math {
+
+class FixedTest
+: public CppUnit::TestFixture {
+
+CPPUNIT_TEST_SUITE(FixedTest);
+CPPUNIT_TEST(testConversion);
+CPPUNIT_TEST(testComparison);
+CPPUNIT_TEST(testSum);
+CPPUNIT_TEST(testProduct);
+CPPUNIT_TEST(testModulo);
+CPPUNIT_TEST_SUITE_END();
+
+public:
+	void setUp();
+	void tearDown();
+
+	void testConversion();
+	void testComparison();
+	void testSum();
+	void testProduct();
+	void testModulo();
+
+};
+
+}
+
+#endif