Index: ps/trunk/source/maths/Fixed.h =================================================================== --- ps/trunk/source/maths/Fixed.h (revision 7495) +++ ps/trunk/source/maths/Fixed.h (revision 7496) @@ -1,184 +1,272 @@ /* Copyright (C) 2010 Wildfire Games. * This file is part of 0 A.D. * * 0 A.D. 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. * * 0 A.D. 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 0 A.D. If not, see . */ #ifndef INCLUDED_FIXED #define INCLUDED_FIXED #include "lib/types.h" #include "maths/Sqrt.h" +#ifndef NDEBUG +#define USE_FIXED_OVERFLOW_CHECKS +#endif // NDEBUG + +//define overflow macros +#ifndef USE_FIXED_OVERFLOW_CHECKS + +#define CheckSignedSubtractionOverflow(type, left, right, overflowWarning, underflowWarning) +#define CheckSignedAdditionOverflow(type, left, right, overflowWarning, underflowWarning) +#define CheckCastOverflow(var, targetType, overflowWarning, underflowWarning) +#define CheckU32CastOverflow(var, targetType, overflowWarning) +#define CheckUnsignedAdditionOverflow(result, operand, overflowWarning) +#define CheckUnsignedSubtractionOverflow(result, operand, overflowWarning) +#define CheckNegationOverflow(var, type, overflowWarning) +#define CheckMultiplicationOverflow(type, left, right, overflowWarning, underflowWarning) +#define CheckDivisionOverflow(type, left, right, overflowWarning) + +#else // USE_FIXED_OVERFLOW_CHECKS + +#define CheckSignedSubtractionOverflow(type, left, right, overflowWarning, underflowWarning) \ + if(left > 0 && right < 0 && left > std::numeric_limits::max() + right) \ + debug_warn(overflowWarning); \ + else if(left < 0 && right > 0 && left < std::numeric_limits::min() + right) \ + debug_warn(underflowWarning); + +#define CheckSignedAdditionOverflow(type, left, right, overflowWarning, underflowWarning) \ + if(left > 0 && right > 0 && std::numeric_limits::max() - left < right) \ + debug_warn(overflowWarning); \ + else if(left < 0 && right < 0 && std::numeric_limits::min() - left > right) \ + debug_warn(underflowWarning); + +#define CheckCastOverflow(var, targetType, overflowWarning, underflowWarning) \ + if(var > std::numeric_limits::max()) \ + debug_warn(overflowWarning); \ + else if(var < std::numeric_limits::min()) \ + debug_warn(underflowWarning); + +#define CheckU32CastOverflow(var, targetType, overflowWarning) \ + if(var > (u32)std::numeric_limits::max()) \ + debug_warn(overflowWarning); + +#define CheckUnsignedAdditionOverflow(result, operand, overflowWarning) \ + if(result < operand) \ + debug_warn(overflowWarning); + +#define CheckUnsignedSubtractionOverflow(result, left, overflowWarning) \ + if(result > left) \ + debug_warn(overflowWarning); + +#define CheckNegationOverflow(var, type, overflowWarning) \ + if(value == std::numeric_limits::min()) \ + debug_warn(overflowWarning); + +#define CheckMultiplicationOverflow(type, left, right, overflowWarning, underflowWarning) \ + i64 res##left = (i64)left * (i64)right; \ + CheckCastOverflow(res##left, type, overflowWarning, underflowWarning) + +#define CheckDivisionOverflow(type, left, right, overflowWarning) \ + if(right == -1) { CheckNegationOverflow(left, type, overflowWarning) } + +#endif // USE_FIXED_OVERFLOW_CHECKS + template inline T round_away_from_zero(float value) { return (T)(value >= 0 ? value + 0.5f : value - 0.5f); } /** * A simple fixed-point number class, with no fancy features * like overflow checking or anything. (It has very few basic * features too, and needs to be substantially improved before * it'll be of much use.) * * Use CFixed_23_8 rather than using this class directly. */ template class CFixed { private: T value; explicit CFixed(T v) : value(v) { } public: enum { fract_bits = fract_bits_ }; CFixed() : value(0) { } static CFixed Zero() { return CFixed(0); } static CFixed Pi(); T GetInternalValue() const { return value; } void SetInternalValue(T n) { value = n; } // Conversion to/from primitive types: static CFixed FromInt(int n) { return CFixed(n << fract_bits); } static CFixed FromFloat(float n) { if (!isfinite(n)) return CFixed(0); float scaled = n * fract_pow2; return CFixed(round_away_from_zero(scaled)); } static CFixed FromDouble(double n) { if (!isfinite(n)) return CFixed(0); double scaled = n * fract_pow2; return CFixed(round_away_from_zero(scaled)); } float ToFloat() const { return value / (float)fract_pow2; } double ToDouble() const { return value / (double)fract_pow2; } int ToInt_RoundToZero() const { if (value > 0) return value >> fract_bits; else return (value + fract_pow2 - 1) >> fract_bits; } /// Returns true if the number is precisely 0. bool IsZero() const { return value == 0; } /// Equality. bool operator==(CFixed n) const { return (value == n.value); } /// Inequality. bool operator!=(CFixed n) const { return (value != n.value); } /// Numeric comparison. bool operator<=(CFixed n) const { return (value <= n.value); } /// Numeric comparison. bool operator<(CFixed n) const { return (value < n.value); } /// Numeric comparison. bool operator>=(CFixed n) const { return (value >= n.value); } /// Numeric comparison. bool operator>(CFixed n) const { return (value > n.value); } // Basic arithmetic: /// Add a CFixed. Might overflow. - CFixed operator+(CFixed n) const { return CFixed(value + n.value); } + CFixed operator+(CFixed n) const + { + CheckSignedAdditionOverflow(T, value, n.value, L"Overflow in CFixed::operator+(CFixed n)", L"Underflow in CFixed::operator+(CFixed n)") + return CFixed(value + n.value); + } /// Subtract a CFixed. Might overflow. - CFixed operator-(CFixed n) const { return CFixed(value - n.value); } + CFixed operator-(CFixed n) const + { + CheckSignedSubtractionOverflow(T, value, n.value, L"Overflow in CFixed::operator-(CFixed n)", L"Underflow in CFixed::operator-(CFixed n)") + return CFixed(value - n.value); + } /// Add a CFixed. Might overflow. - CFixed& operator+=(CFixed n) { value += n.value; return *this; } + CFixed& operator+=(CFixed n) { *this = *this + n; return *this; } /// Subtract a CFixed. Might overflow. - CFixed& operator-=(CFixed n) { value -= n.value; return *this; } + CFixed& operator-=(CFixed n) { *this = *this - n; return *this; } /// Negate a CFixed. - CFixed operator-() const { return CFixed(-value); } + CFixed operator-() const + { + CheckNegationOverflow(value, T, L"Overflow in CFixed::operator-()") + return CFixed(-value); + } /// Divide by a CFixed. Must not have n.IsZero(). Might overflow. CFixed operator/(CFixed n) const { i64 t = (i64)value << fract_bits; - return CFixed((T)(t / (i64)n.value)); + i64 result = t / (i64)n.value; + + CheckCastOverflow(result, T, L"Overflow in CFixed::operator/(CFixed n)", L"Underflow in CFixed::operator/(CFixed n)") + return CFixed((T)result); } /// Multiply by an integer. Might overflow. - CFixed operator*(int n) const { return CFixed(value * n); } + CFixed operator*(int n) const + { + CheckMultiplicationOverflow(T, value, n, L"Overflow in CFixed::operator*(int n)", L"Underflow in CFixed::operator*(int n)") + return CFixed(value * n); + } /// Divide by an integer. Must not have n == 0. Cannot overflow. - CFixed operator/(int n) const { return CFixed(value / n); } + CFixed operator/(int n) const + { + CheckDivisionOverflow(T, value, n, L"Overflow in CFixed::operator/(int n)") + return CFixed(value / n); + } CFixed Absolute() const { return CFixed(abs(value)); } /** * Multiply by a CFixed. Likely to overflow if both numbers are large, * so we use an ugly name instead of operator* to make it obvious. */ CFixed Multiply(CFixed n) const { i64 t = (i64)value * (i64)n.value; - return CFixed((T)(t >> fract_bits)); + t >>= fract_bits; + + CheckCastOverflow(t, T, L"Overflow in CFixed::Multiply(CFixed n)", L"Underflow in CFixed::Multiply(CFixed n)") + return CFixed((T)t); } CFixed Sqrt() const { if (value <= 0) return CFixed(0); u32 s = isqrt64(value); return CFixed((u64)s << (fract_bits / 2)); } private: // Prevent dangerous accidental implicit conversions of floats to ints in certain operations CFixed operator*(float n) const; CFixed operator/(float n) const; }; /** * A fixed-point number class with 1-bit sign, 23-bit integral part, 8-bit fractional part. */ typedef CFixed CFixed_23_8; /** * Inaccurate approximation of atan2 over fixed-point numbers. * Maximum error is almost 0.08 radians (4.5 degrees). */ CFixed_23_8 atan2_approx(CFixed_23_8 y, CFixed_23_8 x); void sincos_approx(CFixed_23_8 a, CFixed_23_8& sin_out, CFixed_23_8& cos_out); #endif // INCLUDED_FIXED Index: ps/trunk/source/maths/FixedVector2D.h =================================================================== --- ps/trunk/source/maths/FixedVector2D.h (revision 7495) +++ ps/trunk/source/maths/FixedVector2D.h (revision 7496) @@ -1,173 +1,183 @@ /* Copyright (C) 2010 Wildfire Games. * This file is part of 0 A.D. * * 0 A.D. 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. * * 0 A.D. 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 0 A.D. If not, see . */ #ifndef INCLUDED_FIXED_VECTOR2D #define INCLUDED_FIXED_VECTOR2D #include "maths/Fixed.h" #include "maths/Sqrt.h" class CFixedVector2D { private: typedef CFixed_23_8 fixed; public: fixed X, Y; CFixedVector2D() { } CFixedVector2D(fixed X, fixed Y) : X(X), Y(Y) { } /// Vector equality bool operator==(const CFixedVector2D& v) const { return (X == v.X && Y == v.Y); } /// Vector inequality bool operator!=(const CFixedVector2D& v) const { return (X != v.X || Y != v.Y); } /// Vector addition CFixedVector2D operator+(const CFixedVector2D& v) const { return CFixedVector2D(X + v.X, Y + v.Y); } /// Vector subtraction CFixedVector2D operator-(const CFixedVector2D& v) const { return CFixedVector2D(X - v.X, Y - v.Y); } /// Negation CFixedVector2D operator-() const { return CFixedVector2D(-X, -Y); } /// Vector addition CFixedVector2D& operator+=(const CFixedVector2D& v) { *this = *this + v; return *this; } /// Vector subtraction CFixedVector2D& operator-=(const CFixedVector2D& v) { *this = *this - v; return *this; } /// Scalar multiplication by an integer CFixedVector2D operator*(int n) const { return CFixedVector2D(X*n, Y*n); } /** * Multiply by a CFixed. Likely to overflow if both numbers are large, * so we use an ugly name instead of operator* to make it obvious. */ CFixedVector2D Multiply(fixed n) const { return CFixedVector2D(X.Multiply(n), Y.Multiply(n)); } /** * Returns the length of the vector. * Will not overflow if the result can be represented as type 'fixed'. */ fixed Length() const { // Do intermediate calculations with 64-bit ints to avoid overflows i64 x = (i64)X.GetInternalValue(); i64 y = (i64)Y.GetInternalValue(); - u64 d2 = (u64)(x * x + y * y); + u64 xx = (u64)(x * x); + u64 yy = (u64)(y * y); + u64 d2 = xx + yy; + CheckUnsignedAdditionOverflow(d2, xx, L"Overflow in CFixedVector2D::Length() part 1") + u32 d = isqrt64(d2); + + CheckU32CastOverflow(d, i32, L"Overflow in CFixedVector2D::Length() part 2") fixed r; r.SetInternalValue((i32)d); return r; } bool IsZero() const { return (X.IsZero() && Y.IsZero()); } /** * Normalize the vector so that length is close to 1. * If length is 0, does nothing. * WARNING: The fixed-point numbers only have 8-bit fractional parts, so * a normalized vector will be very imprecise. */ void Normalize() { if (!IsZero()) { fixed l = Length(); X = X / l; Y = Y / l; } } /** * Normalize the vector so that length is close to n. * If length is 0, does nothing. */ void Normalize(fixed n) { if (n.IsZero()) { X = Y = fixed::FromInt(0); return; } fixed l = Length(); // TODO: work out whether this is giving decent precision fixed d = l / n; if (!d.IsZero()) { X = X / d; Y = Y / d; } } /** * Compute the dot product of this vector with another. */ fixed Dot(const CFixedVector2D& v) { i64 x = (i64)X.GetInternalValue() * (i64)v.X.GetInternalValue(); i64 y = (i64)Y.GetInternalValue() * (i64)v.Y.GetInternalValue(); + CheckSignedAdditionOverflow(i64, x, y, L"Overflow in CFixedVector2D::Dot() part 1", L"Underflow in CFixedVector2D::Dot() part 1") i64 sum = x + y; + sum >>= fixed::fract_bits; + + CheckCastOverflow(sum, i32, L"Overflow in CFixedVector2D::Dot() part 2", L"Underflow in CFixedVector2D::Dot() part 2") fixed ret; - ret.SetInternalValue((i32)(sum >> fixed::fract_bits)); + ret.SetInternalValue((i32)sum); return ret; } CFixedVector2D Perpendicular() { return CFixedVector2D(Y, -X); } }; #endif // INCLUDED_FIXED_VECTOR2D Index: ps/trunk/source/maths/FixedVector3D.h =================================================================== --- ps/trunk/source/maths/FixedVector3D.h (revision 7495) +++ ps/trunk/source/maths/FixedVector3D.h (revision 7496) @@ -1,162 +1,197 @@ /* Copyright (C) 2010 Wildfire Games. * This file is part of 0 A.D. * * 0 A.D. 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. * * 0 A.D. 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 0 A.D. If not, see . */ #ifndef INCLUDED_FIXED_VECTOR3D #define INCLUDED_FIXED_VECTOR3D #include "maths/Fixed.h" #include "maths/Sqrt.h" class CFixedVector3D { private: typedef CFixed_23_8 fixed; public: fixed X, Y, Z; CFixedVector3D() { } CFixedVector3D(fixed X, fixed Y, fixed Z) : X(X), Y(Y), Z(Z) { } /// Vector equality bool operator==(const CFixedVector3D& v) const { return (X == v.X && Y == v.Y && Z == v.Z); } /// Vector addition CFixedVector3D operator+(const CFixedVector3D& v) const { return CFixedVector3D(X + v.X, Y + v.Y, Z + v.Z); } /// Vector subtraction CFixedVector3D operator-(const CFixedVector3D& v) const { return CFixedVector3D(X - v.X, Y - v.Y, Z - v.Z); } /// Negation CFixedVector3D operator-() const { return CFixedVector3D(-X, -Y, -Z); } /// Vector addition CFixedVector3D& operator+=(const CFixedVector3D& v) { *this = *this + v; return *this; } /// Vector subtraction CFixedVector3D& operator-=(const CFixedVector3D& v) { *this = *this - v; return *this; } /** * Returns the length of the vector. * Will not overflow if the result can be represented as type 'fixed'. */ fixed Length() const { // Do intermediate calculations with 64-bit ints to avoid overflows i64 x = (i64)X.GetInternalValue(); i64 y = (i64)Y.GetInternalValue(); i64 z = (i64)Z.GetInternalValue(); - u64 d2 = (u64)(x * x + y * y + z * z); + u64 xx = (u64)(x * x); + u64 yy = (u64)(y * y); + u64 zz = (u64)(z * z); + u64 t = xx + yy; + CheckUnsignedAdditionOverflow(t, xx, L"Overflow in CFixedVector3D::Length() part 1") + + u64 d2 = t + zz; + CheckUnsignedAdditionOverflow(d2, t, L"Overflow in CFixedVector3D::Length() part 2") + u32 d = isqrt64(d2); + + CheckU32CastOverflow(d, i32, L"Overflow in CFixedVector3D::Length() part 3") fixed r; r.SetInternalValue((i32)d); return r; } /** * Normalize the vector so that length is close to 1. * If length is 0, does nothing. * WARNING: The fixed-point numbers only have 8-bit fractional parts, so * a normalized vector will be very imprecise. */ void Normalize() { fixed l = Length(); if (!l.IsZero()) { X = X / l; Y = Y / l; Z = Z / l; } } /** * Normalize the vector so that length is close to n. * If length is 0, does nothing. */ void Normalize(fixed n) { if (n.IsZero()) { X = Y = Z = fixed::FromInt(0); return; } fixed l = Length(); // TODO: work out whether this is giving decent precision fixed d = l / n; if (!d.IsZero()) { X = X / d; Y = Y / d; Z = Z / d; } } /** * Compute the cross product of this vector with another. */ CFixedVector3D Cross(const CFixedVector3D& v) { - i64 x = ((i64)Y.GetInternalValue() * (i64)v.Z.GetInternalValue()) - ((i64)Z.GetInternalValue() * (i64)v.Y.GetInternalValue()); - i64 y = ((i64)Z.GetInternalValue() * (i64)v.X.GetInternalValue()) - ((i64)X.GetInternalValue() * (i64)v.Z.GetInternalValue()); - i64 z = ((i64)X.GetInternalValue() * (i64)v.Y.GetInternalValue()) - ((i64)Y.GetInternalValue() * (i64)v.X.GetInternalValue()); + i64 y_vz = (i64)Y.GetInternalValue() * (i64)v.Z.GetInternalValue(); + i64 z_vy = (i64)Z.GetInternalValue() * (i64)v.Y.GetInternalValue(); + CheckSignedSubtractionOverflow(i64, y_vz, z_vy, L"Overflow in CFixedVector3D::Cross() part 1", L"Underflow in CFixedVector3D::Cross() part 1") + i64 x = y_vz - z_vy; + x >>= fixed::fract_bits; + + i64 z_vx = (i64)Z.GetInternalValue() * (i64)v.X.GetInternalValue(); + i64 x_vz = (i64)X.GetInternalValue() * (i64)v.Z.GetInternalValue(); + CheckSignedSubtractionOverflow(i64, z_vx, x_vz, L"Overflow in CFixedVector3D::Cross() part 2", L"Underflow in CFixedVector3D::Cross() part 2") + i64 y = z_vx - x_vz; + y >>= fixed::fract_bits; + + i64 x_vy = (i64)X.GetInternalValue() * (i64)v.Y.GetInternalValue(); + i64 y_vx = (i64)Y.GetInternalValue() * (i64)v.X.GetInternalValue(); + CheckSignedSubtractionOverflow(i64, x_vy, y_vx, L"Overflow in CFixedVector3D::Cross() part 3", L"Underflow in CFixedVector3D::Cross() part 3") + i64 z = x_vy - y_vx; + z >>= fixed::fract_bits; + + CheckCastOverflow(x, i32, L"Overflow in CFixedVector3D::Cross() part 4", L"Underflow in CFixedVector3D::Cross() part 4") + CheckCastOverflow(y, i32, L"Overflow in CFixedVector3D::Cross() part 5", L"Underflow in CFixedVector3D::Cross() part 5") + CheckCastOverflow(z, i32, L"Overflow in CFixedVector3D::Cross() part 6", L"Underflow in CFixedVector3D::Cross() part 6") CFixedVector3D ret; - ret.X.SetInternalValue((i32)(x >> fixed::fract_bits)); - ret.Y.SetInternalValue((i32)(y >> fixed::fract_bits)); - ret.Z.SetInternalValue((i32)(z >> fixed::fract_bits)); + ret.X.SetInternalValue((i32)x); + ret.Y.SetInternalValue((i32)y); + ret.Z.SetInternalValue((i32)z); return ret; } /** * Compute the dot product of this vector with another. */ fixed Dot(const CFixedVector3D& v) { i64 x = (i64)X.GetInternalValue() * (i64)v.X.GetInternalValue(); i64 y = (i64)Y.GetInternalValue() * (i64)v.Y.GetInternalValue(); i64 z = (i64)Z.GetInternalValue() * (i64)v.Z.GetInternalValue(); - i64 sum = x + y + z; + CheckSignedAdditionOverflow(i64, x, y, L"Overflow in CFixedVector3D::Dot() part 1", L"Underflow in CFixedVector3D::Dot() part 1") + i64 t = x + y; + + CheckSignedAdditionOverflow(i64, t, z, L"Overflow in CFixedVector3D::Dot() part 2", L"Underflow in CFixedVector3D::Dot() part 2") + i64 sum = t + z; + sum >>= fixed::fract_bits; + CheckCastOverflow(sum, i32, L"Overflow in CFixedVector3D::Dot() part 3", L"Underflow in CFixedVector3D::Dot() part 3") + fixed ret; - ret.SetInternalValue((i32)(sum >> fixed::fract_bits)); + ret.SetInternalValue((i32)sum); return ret; } }; #endif // INCLUDED_FIXED_VECTOR3D