GP2X Fixed Point Class

[synkro]

Any optimizations, comment and criticism are welcome!

#ifndef _FIXED_H_
#define _FIXED_H_
/*
** Fixed Point Class 16.16
**
** TODO
** - calculate limits for range check
**
** REV1
** - MULS and DIVS now with range check and intermediate long long
** - easier to use and read than macros
** - overloaded cast operators
** - only slooow math function (double conversion)
**
** Greets and shouts to the guys and gals @ gp32x.de
**
** ----------------------------------------------------------------------------
** "THE BEER-WARE LICENSE" (Revision 42):
** <synkro@gmx.net> wrote this file. As long as you retain this notice you
** can do whatever you want with this stuff. If we meet some day, and you think
** this stuff is worth it, you can buy me a beer in return			   SYNKRO
** ----------------------------------------------------------------------------
*/
 
#include <iostream>
#include <cmath>
 
using namespace std;
 
#define PI		3.1415926535
#define	PRECISION		16
#define DOUBLE_FACTOR	65536.0
 
class Fixed
{
public:
	Fixed(void)			{ fix = 0;}
	Fixed(int n)		{ fix = n << PRECISION;}
	Fixed(double f)		{ fix = (int) (f * DOUBLE_FACTOR);}
 
// cast operators
	operator int()				{ return fix >> PRECISION; }
	operator unsigned int()		{ return fix >> PRECISION; }
	operator char()				{ return fix >> PRECISION; }
	operator unsigned char()	{ return fix >> PRECISION; }
	operator double()			{ return fix / DOUBLE_FACTOR; }
 
	friend bool operator==(const Fixed a, const Fixed b) {return a.fix == b.fix;}
	friend bool operator<(const Fixed a, const Fixed b) {return a.fix < b.fix;}
	friend bool operator>(const Fixed a, const Fixed b) {return a.fix > b.fix;}
 
// math functions
	int floor(void)		{ return (fix >> PRECISION); }
	int ceil(void)		{ return (fix >> PRECISION)+1; }
 
	Fixed sqrt(void) {Fixed t( std::sqrt(this->toDouble()) ); return t;}
 
	Fixed sin(void) {Fixed t( std::sin(this->toDouble()) ); return t;}
	Fixed cos(void) {Fixed t( std::cos(this->toDouble()) ); return t;}
	Fixed tan(void) {Fixed t( std::tan(this->toDouble()) ); return t;}
 
	Fixed abs(void) {Fixed t( std::abs(this->toDouble()) ); return t;}
 
// Addition
	Fixed& operator+=(const Fixed a)	{ fix += a.fix; return *this; }
	Fixed& operator+=(int n)	{ fix += (n << PRECISION); return *this; }
	Fixed& operator+=(double d)	{ fix += (int) (d * DOUBLE_FACTOR); return *this; }
 
	friend Fixed operator+(const Fixed a, const Fixed b) { Fixed t = a; return t += b; }
	friend Fixed operator+(const int a, const Fixed b) { Fixed t = b; return t += a; }
	friend Fixed operator+(const Fixed a, const int b) { Fixed t = a; return t += b; }
	friend Fixed operator+(const double a, const Fixed b) { Fixed t = b; return t += a; }
	friend Fixed operator+(const Fixed a, const double b) { Fixed t = a; return t += b; }
 
 
// Substraktion
	Fixed& operator-=(Fixed a)	{ fix -= a.fix; return *this; }
	Fixed& operator-=(int n)	{ fix -= (n << PRECISION); return *this; }
	Fixed& operator-=(double d) { fix -= (int) (d * DOUBLE_FACTOR); return *this; }
 
	friend Fixed operator-(const Fixed a, const Fixed b) { Fixed t = a; return t -= b; }
	friend Fixed operator-(int a, Fixed b) { Fixed t(a); return t-=b; }
	friend Fixed operator-(const Fixed a, const int b) { Fixed t = a; return t -= b; }
	friend Fixed operator-(const double a, const Fixed b) { Fixed t(a); return t -= b; }
	friend Fixed operator-(const Fixed a, const double b) { Fixed t = a; return t -= b; }
 
 
// Mult
	inline Fixed& operator*=(Fixed a);
	inline Fixed& operator*=(int n);
	inline Fixed& operator*=(double d);
 
	friend Fixed operator*(const Fixed a, const Fixed b) { Fixed t = a; return t *=b; }
	friend Fixed operator*(const int a, const Fixed b) { Fixed t = b; return t *=a; }
	friend Fixed operator*(const Fixed a, const int b) { Fixed t = a; return t *=b; }
	friend Fixed operator*(const Fixed a, const double b) { Fixed t = a; return t *=b; }
	friend Fixed operator*(const double a, const Fixed b) { Fixed t = b; return t *=a; }
 
// DIV
	inline Fixed& operator/=(Fixed a);
	inline Fixed& operator/=(int n);
	inline Fixed& operator/=(double d);
 
	friend Fixed operator/(const Fixed a, const Fixed b) { Fixed t = a; return t /=b; }
	friend Fixed operator/(const int a, const Fixed b) { Fixed t(a); return t /=b; }
	friend Fixed operator/(const Fixed a, const int b) { Fixed t = a; return t /=b; }
	friend Fixed operator/(const double a, const Fixed b) { Fixed t(a); return t /=b; }
	friend Fixed operator/(const Fixed a, const double b) { Fixed t = a; return t /=b; }
 
 
// stream output
	friend ostream& operator<<(ostream &os, Fixed &obj);
 
private:
	int fix;
	int toInt(void)		{ return (fix >> PRECISION);}
	float toDouble(void) { return fix/DOUBLE_FACTOR; }
};
 
 
/*
** FIXMUL with range check
** TODO: calculate range for variable precisions
*/
inline Fixed& Fixed::operator*=(Fixed a)
{
	const long long a_long = a.fix;
	const long long b_long = fix;
	const long long result = b_long * a_long;
 
	// check range
	if(result > 0x7FFFFFFF0000LL)
	{
		fix = 0x7FFFFFFFL;
	}
	else if(result < -0x7FFFFFFF0000LL)
	{
		fix = 0x80000000L;
	}
	else
	{
		fix = result >> PRECISION;
	}
	return *this;
}
inline Fixed& Fixed::operator*=(int n)
{
	Fixed a(n);
	const long long a_long = a.fix;
	const long long b_long = fix;
	const long long result = b_long * a_long;
 
	// check range
	if(result > 0x7FFFFFFF0000LL)

	{
		fix = 0x7FFFFFFFL;
	}
	else if(result < -0x7FFFFFFF0000LL)
	{
		fix = 0x80000000L;
	}
	else
	{
		fix = result >> PRECISION;
	}
	return *this;
}
inline Fixed& Fixed::operator*=(double d)
{
	Fixed a(d);
	const long long a_long = a.fix;
	const long long b_long = fix;
	const long long result = b_long * a_long;
 
	// check range
	if(result > 0x7FFFFFFF0000LL)
	{
		fix = 0x7FFFFFFFL;
	}
	else if(result < -0x7FFFFFFFL)
	{
		fix = 0x80000000;
	}
	else
	{
		fix = result >> PRECISION;
	}
	return *this;
}
 
/*
** FIXDIV with simple checks
*/
inline Fixed& Fixed::operator/=(Fixed a)
{
	// division by zero!
	if(a.fix == 0)
	{
		if(fix < 0) fix = 0x80000000L;
		if(fix > 0) fix = 0x7FFFFFFFL;
		return *this;
	}
 
	const long long a_long = a.fix;
	const long long b_long = fix;
	const long long result = (b_long << PRECISION) / a_long;
 
	// check range
	if(result > 0x7FFFFFFF0000LL)
	{
		fix = 0x7FFFFFFFL;
	}
	else if(result < -0x7FFFFFFF0000LL)
	{
		fix = 0x80000000L;
	}
	else
	{
		fix = result;
	}
	return *this;
}
inline Fixed& Fixed::operator/=(int n)
{
	Fixed a(n);
		// division by zero!
	if(a.fix == 0)
	{
		if(fix < 0) fix = 0x80000000L;
		if(fix > 0) fix = 0x7FFFFFFFL;
		return *this;
	}
 
	const long long a_long = a.fix;
	const long long b_long = fix;
	const long long result = (b_long << PRECISION) / a_long;
 
	// check range
	if(result > 0x7FFFFFFF0000LL)
	{
		fix = 0x7FFFFFFFL;
	}
	else if(result < -0x7FFFFFFF0000LL)
	{
		fix = 0x80000000L;
	}
	else
	{
		fix = result;
	}
	return *this;
}
inline Fixed& Fixed::operator/=(double d)
{
	Fixed a(d);
	// division by zero!
	if(a.fix == 0)
	{
		if(fix < 0) fix = 0x80000000L;
		if(fix > 0) fix = 0x7FFFFFFFL;
		return *this;
	}
 
	const long long a_long = a.fix;
	const long long b_long = fix;
	const long long result = (b_long << PRECISION) / a_long;
 
	// check range
	if(result > 0x7FFFFFFF0000LL)
	{
		fix = 0x7FFFFFFFL;
	}
	else if(result < -0x7FFFFFFF0000LL)
	{
		fix = 0x80000000L;
	}
	else
	{
		fix = result;
	}
	return *this;
 
}
 
/*
** output stream fixed
** TODO: input stream
*/
inline ostream& operator<<(ostream &os, Fixed &obj)
{
	double f = obj.toDouble();
	os << f << "fix";
	return os;
}
 
#endif

 

[PokeParadox]

My only recommendation is to basically inline everything, since they are all short functions.

 

[synkro]

uhm.. I thought when I implement the methods inside the class definition then they are inlined by default...

 

[Parkydr]

uhm.. I thought when I implement the methods inside the class definition then they are inlined by default...

You are right

 

[slygamer]

#define PRECISION	 8
#define DOUBLE_FACTOR ((double)(1 << PRECISION))

For all those places where you hard-coded 256. Replace with DOUBLE_FACTOR and if you change the precision later, it all just works.

  operator int()		{ return fix >> PRECISION; }
  operator double()	 { return fix / DOUBLE_FACTOR; }

// Math functions
  Fixed sqrt()		  { Fixed t(::sqrt((double)*this)); return t; }

  Fixed sin()		   { Fixed t(::sin((double)*this)); return t; }
  Fixed cos()		   { Fixed t(::cos((double)*this)); return t; }
  Fixed tan()		   { Fixed t(::tan((double)*this)); return t; }

  Fixed abs()		   { Fixed t(::abs((double)*this)); return t; }

You can overload the int and double operator instead of creating conversion functions.

 

[rixed]

1) All math functions convert values to double. There have to be fixed point versions of these.

2) For div and mul, use a larger integer type or you are severelly limiting the useable range.

 

[PokeParadox]

uhm.. I thought when I implement the methods inside the class definition then they are inlined by default...

You are right

Ah my bad, something I didn't know...

 

[spoyser]

All the const parameters could be references, although it doesn't really matter for this class given that all it contains is an int but it is good practise to pass by reference in order to prevent unnecessary copying.

 

[synkro]

#define PRECISION	 8
#define DOUBLE_FACTOR ((double)(1 << PRECISION))

For all those places where you hard-coded 256. Replace with DOUBLE_FACTOR and if you change the precision later, it all just works.

Ah, thank you!

1) All math functions convert values to double. There have to be fixed point versions of these.
2) For div and mul, use a larger integer type or you are severelly limiting the useable range.

to 1): hmmm.. for sin/cos I could use a LUT, but many others like sqrt() I would have to do myself
to 2): like this?

muil(fix a, fix B)

long aa = a, long bb = b;
long cc = aa * bb;
cc >> PRECISION;
cc &= 0xFFFFFFFF;
fix result = cc;

All the const parameters could be references, although it doesn't really matter for this class given that all it contains is an int but it is good practise to pass by reference in order to prevent unnecessary copying.

True, but this way it behaves like an int etc.

 

[Parkydr]

All the const parameters could be references, although it doesn't really matter for this class given that all it contains is an int but it is good practise to pass by reference in order to prevent unnecessary copying.

True, but this way it behaves like an int etc.

I can't see anything that will work any differently if you use const references. As it stands, every time you call a method a copy of Fixed will be made.

In this case it does matter, the point of using this class is performance. Every time you call a function you are doing an unnecessary copy or two if for operators like +

 

[slygamer]

muil(fix a, fix B)

long aa = a, long bb = b;
long cc = aa * bb;
cc >> PRECISION;
cc &= 0xFFFFFFFF;
fix result = cc;

A long is the same size as an int. What you need is a long long, or an int64, for the intermediate result.

Something like:

long long result = a * b;
return (int)(result >> PRECISION);

 

[rixed]

hmmm.. for sin/cos I could use a LUT, but many others like sqrt() I would have to do myself

Here is what I use. The sqrt was taken from a newsgroup and were posted by Dijkstra. The sin/cos LUT are mine.

#define iter1(N) \
try = root + (1 << (N)); \
if (n >= try << (N)) { \
n -= try << (N); \
root |= 2 << (N); \
}

int32_t my_sqrt(int32_t n) {
int32_t root = 0, try;
iter1(15); iter1(14); iter1(13); iter1(12);
iter1(11); iter1(10); iter1( 9); iter1( 8);
iter1( 7); iter1( 6); iter1( 5); iter1( 4);
iter1( 3); iter1( 2); iter1( 1); iter1( 0);
return root >> 1;
}

#define FIXED_PI 32768 // 2*PI is 1<<16 for these functions
#define NB_STEPS 65536 // must be a power of 4
static int32_t sincos[NB_STEPS+NB_STEPS/4];

void Fix_trig_init(void) {
unsigned n;
# define BITS_PREC 30
int64_t c=1<<BITS_PREC;
int64_t s=0;
int64_t ku1 = 1073741819;
int64_t ku2 = 102944;
for (n=0; n<NB_STEPS+NB_STEPS/4; n++) {
sincos[n] = c>>(BITS_PREC-16);
int64_t new_c = (Fix_mul64x64(c,ku1) - Fix_mul64x64(s,ku2))>>BITS_PREC;
s = (Fix_mul64x64(s,ku1) + Fix_mul64x64(c,ku2))>>BITS_PREC;
c = new_c;
}
# undef BITS_PREC
}

int32_t Fix_cos(int32_t ang) {
return sincos[ang&(NB_STEPS-1)];
}
int32_t Fix_sin(int32_t ang) {
return sincos[NB_STEPS/4 + (ang&(NB_STEPS-1))];
}

I can't see anything that will work any differently if you use const references. As it stands, every time you call a method a copy of Fixed will be made.

Seriously, compilers are that bad ?? :-o

 

[Parkydr]

I can't see anything that will work any differently if you use const references. As it stands, every time you call a method a copy of Fixed will be made.

Seriously, compilers are that bad ?? :-o

In what way? That it wont work or that the assembler produced will be more inefficient than copying

 

[PokeParadox]

ompilers are certainly more efficient in detecting what they can optimise these days. As to how efficient... well that's debatable. It doesn't hurt if you know what to optimise before a compile to make those optimisations. But I do thin kthe compilers are quite decent and probably better than most people give them credit for.

 

[spoyser]

All the const parameters could be references, although it doesn't really matter for this class given that all it contains is an int but it is good practise to pass by reference in order to prevent unnecessary copying.

True, but this way it behaves like an int etc.

I can't see anything that will work any differently if you use const references. As it stands, every time you call a method a copy of Fixed will be made.

In this case it does matter, the point of using this class is performance. Every time you call a function you are doing an unnecessary copy or two if for operators like +

That was my point, if you use a const reference then a copy of Fixed will not be made, the original variables memory address will be passed into the method. Since Fixed just contains an int then copying it is neglible however if the class was to be expanded that you definately wouldn't want to copying it for no reason.

 

[Parkydr]

That was my point, if you use a const reference then a copy of Fixed will not be made, the original variables memory address will be passed into the method. Since Fixed just contains an int then copying it is neglible however if the class was to be expanded that you definately wouldn't want to copying it for no reason.

I was agreeing with you, except I think it should be done "neglible" is still > 0.

What I was taking issue with was -

True, but this way it behaves like an int etc.

 

[spoyser]

That was my point, if you use a const reference then a copy of Fixed will not be made, the original variables memory address will be passed into the method. Since Fixed just contains an int then copying it is neglible however if the class was to be expanded that you definately wouldn't want to copying it for no reason.

I was agreeing with you, except I think it should be done "neglible" is still > 0.

What I was taking issue with was -

True, but this way it behaves like an int etc.

Yes but given that all the class contains is an int, it will just as quick to copy the int as it would be to copy the memory address of the object itself, given that the memory address will be also an int. Hence > 0 but not any quicker. Still very bad practise though to pass as a copy though!

 

[rabidcow]

I would say don't bother making it pass by reference. If you do, check the compiled code to see if it actually passes the address rather than a copy. Copying is cheaper for an object this small. (I'm not convinced that the compiler can safely make this optimization) sizeof(Fixed) == sizeof(Fixed*), and if you pass by reference it needs to dereference the address on the inside. Not to mention that you can't take the address of a register, and the entire object will fit...

 

[rixed]

I would say don't bother making it pass by reference. If you do, check the compiled code to see if it actually passes the address rather than a copy.

You'd better check that the compiler don't actually code a function call at all...

 

[Parkydr]

Thank you, I understand your reasoning now. I may have a look at the compiled code