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