gbadev.org forum archive

This is a read-only mirror of the content originally found on forum.gbadev.org (now offline), salvaged from Wayback machine copies. A new forum can be found here.

DS development > Fixpoint 20:12 overflow mulf32

#139549 - a128 - Fri Sep 07, 2007 11:55 am

While working on a 3d title.....implementing some collision detection.....wondering why this works with float but not with my fixpoint class....I soon dicovered (and just forgot about it..that this could happen)

that the mulf32(a,b) could have overflow

Any cool idea for overflow checks (before the mulf32(a,b) command)?

I would include this for DEBUG purposes.

Overflow happens
Code:

     
   Fixed fDet   = abs(fA00 * fA11 - fA01 * fA01);

   Fixed u1=(fA01 * fB1); /!!!!overflows
/*
FA01 and fB1 could have larger values

because i.e. fA01=x*x+y*y+z*z

I check for a very big triangle...because I want to reduce my triangle count for collsion mesh
*/


BTW here is my fixpoint class

http://a128.atspace.com/fixpoint.tgz

#139550 - simonjhall - Fri Sep 07, 2007 12:07 pm

I do the majority of my fixed point multiplies with long longs since I'm not really in control of the data that's coming in (so can't prescale it down).
So, like this:
Code:
fixed_point a, b;   //in 19:13 format
fixed_point result = (int)(((long long)a * (long long)) >> 13);

Not as fast as it could be, but I never get overflows.
_________________
Big thanks to everyone who donated for Quake2

#139551 - a128 - Fri Sep 07, 2007 12:12 pm

simonjhall wrote:
I do the majority of my fixed point multiplies with long longs since I'm not really in control of the data that's coming in (so can't prescale it down).
So, like this:
Code:
fixed_point a, b;   //in 19:13 format
fixed_point result = (int)(((long long)a * (long long)) >> 13);

Not as fast as it could be, but I never get overflows.


In my code example

a*b means mulf32(a,b)....

Why you are using 19:13 format? OK, you have more precision on the fraction part..I guess

But llosing one bit in the integer part...means you must have sooner overflows then using 20:12

maybe using 24:8 would be cool. but 8 bits for fractions?!

Quote:

from http://inkbattle.marctenbosch.com/postmortem.html
However using fixed point meant that any algorithm used had to contain additional overflow checks, as the maximum number that a 20-12 fixed point number can hold is around 722^2, which is quite an inconvenience when checking for squared distances in pixels between characters for example.


Last edited by a128 on Fri Sep 07, 2007 12:25 pm; edited 2 times in total

#139553 - simonjhall - Fri Sep 07, 2007 12:24 pm

The reason I use long longs is because you can never be sure how large the two numbers you want to multiply are. You could reduce it to a 31:1 format, but you could still get overflows which you wouldn't get when using floats natively. Hence using larger types, then shifting them down.

The reason I use 19:13 was because that seemed like a good trade off. This was the point at which stuff stopped going wrong :-)
20:12 or 18:14 would have done equally well, but (for example) 25:7 wasn't enough.
_________________
Big thanks to everyone who donated for Quake2

#139554 - a128 - Fri Sep 07, 2007 12:27 pm

simonjhall wrote:
The reason I use long longs is because you can never be sure how large the two numbers you want to multiply are.


Maybe I miss somethink...

but I also use long long in that mulf32(a,b) code

#139556 - simonjhall - Fri Sep 07, 2007 1:04 pm

Ok, with a 20:12 fixed-point format, the largest multiply you can do is 16.0 * 16.0 (or equivalent eg 256.0 * 1.0) since any larger numbers will overflow the multiply.

Here's why:
16.0 in 20:12 is 16 << 12, which is 65536. Now 65536 * 65536 is 4294967296 - the top end of a 32-bit int.
To get the result of the multiply you've then got to right-shift that value by the number of bits you've left shifted by (ie 12 here).
So 4294967296 >> 12 = 1048576, which is 256.0 in your 20:12 fixed-point format - the correct answer, with no overflow.

Now if you do a sum which gives a value greater than 256.0 you'd gonna get overflow. Since you may not know the range of values coming into your multiply function, you may overflow.

To check for this you could take the significand of the two numbers, muliply them together and check to see if they're greater than ~256. If they are, you could use a less precise fixed-point type for the computation (eg 25:7).
Or, to maintain the precision of 20:12 at the expense of a bit of speed you can promote the numbers in the multiplication to 64-bit int types.

So if you want to do 32.0 * 32.0 you'd do this:
32.0 in 20:12 fixed-point is 131072
131072 * 131072 = 17179869184 - overflow! This is larger than the 32-bit int type can handle.

So, do this (long long)131072 * (long long)131072 = 17179869184 (now with no overflow)
Then shift it back down,
(long long)17179869184 >> 12 = 4194304 - small enough for the 32-bit int type used by your fixed-point class.

Finally,
fixed_point result = 4194304, which is 1024.0 in 20:12, the correct answer to 32.0 * 32.0.

Does this make any sense or does this look like a mess? ;-)
_________________
Big thanks to everyone who donated for Quake2

#139557 - a128 - Fri Sep 07, 2007 1:19 pm

Thanks a lot

Now I know what I did wrong

when I did this

class Fixed{

public: int32 value;

};

Fixed = a*a+b*b+c*c

I called the *-operatoor with mulf32() ..which is a waste of scaling
for every a*a ..it did ((long long)a*(long long)a ) >>12

now I do

value= (int32) ( (long long)a.value+(long long)a.value +.....+(long long)c.value*(long long)c.value ) >>12