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.

Beginners > Fixed point math help

#35518 - ymalik - Sun Feb 06, 2005 12:40 am

Hello,
I need help on fixed point math. I don't know if this belongs here, and I couldn't find another topic regarding this. The fixed-point number is in 18.14 format.

I have the following program:
Code:

#include <string.h>

#define FIX_SCALEF 16384.0f
#define FIX_FRAC_PART(n) ((n)&0x3fff)
#define FIX_INT_PART(n) (n>>14)
typedef int FIXED;

int main()
{
 float num = -130.1234;

 FIXED fixed = num*FIX_SCALEF;
 int int_part, frac_part;

 frac_part = FIX_FRAC_PART(fixed);
 int_part = FIX_INT_PART(fixed);

 printf("floating point: %f\n", num);
 printf("fixed point: %i\n", fixed);
 printf("int part: %i\n", int_part);
 printf("frac part: %i\n", frac_part);

 return 0;
}

But it outputs the following:
floating point: -130.123398
fixed point: -2131941
int part: -131
frac part: 14363

And I notice that the integer part is always one more than the original integer part, and the fractional part is always messed up.

Thanks,
Yasir

#35520 - tepples - Sun Feb 06, 2005 1:30 am

You're dealing with negative numbers. Your way of taking the integer part of a fixed-point number is precisely equivalent to floor(n) of a floating-point number, and your fractional part is n-floor(n). Try taking 16384 minus the fractional part and seeing if it looks any better.
_________________
-- Where is he?
-- Who?
-- You know, the human.
-- I think he moved to Tilwick.

#35521 - ymalik - Sun Feb 06, 2005 2:11 am

tepples wrote:
Your way of taking the integer part of a fixed-point number is precisely equivalent to floor(n) of a floating-point number, and your fractional part is n-floor(n).


What is your way? I'm following Cearn's fixed point math tutorial. Also, (16384 - ((n)&0x3fff)) does not give me the right value for the fractional part.

Thanks,
Yasir

#35524 - tepples - Sun Feb 06, 2005 2:45 am

ymalik wrote:
tepples wrote:
Your way of taking the integer part of a fixed-point number is precisely equivalent to floor(n) of a floating-point number, and your fractional part is n-floor(n).


What is your way?

The / operator rounds toward zero; to take frac(n), do n / 16384. In most cases, division is dog-slow, but GCC recognizes division by a power of 0 and optimizes it. But if you're not displaying a number, you usually want floor(n) or round(n), which is floor(n + float_to_fix(0.5)).

Quote:
Also, (16384 - ((n)&0x3fff)) does not give me the right value for the fractional part.

It did for me in Windows 2000's calculator. The fractional part of your number is -0.1234; when I pasted (14363-16384)/16384.0= into calculator I got -0.12335205078125 which is close enough.
_________________
-- Where is he?
-- Who?
-- You know, the human.
-- I think he moved to Tilwick.

#35531 - Cearn - Sun Feb 06, 2005 1:43 pm

Funny thing about divisions and shifts is that division always rounds towards zero, but shifts always rounds to the integer below it. For positive values this will be the same, but for negative values there can be a difference. (-1)/2 is 0, while (-1)>>1 = -1.

Here are the .14 fixed point values of 130.123398 and -130.123398 in detail:
Code:

130.1234 * 16384 = 2131941.79
002087E5                                 // hex
0000 0000 0010 0000 1000 0111 1110 0101  // binary
0000 0000 1000 0010 : 00 0111 1110 0101  // redistribute to  .14 fixed point
0082 : 07E5                              // hex integer vs 'fraction'
130  : 2021                              // decimal integer vs 'fraction'
divide 'fraction' by 16384
130 + 0.1234


-130.1234 * 16384 = -2131941.79
FFDF781B                                 // hex
1111 1111 1101 1111 0111 1000 0001 1011  // binary
1111 1111 0111 1101 : 11 1000 0001 1011  // redistribute to  .14 fixed point
FF72 : 381B                              // hex integer vs 'fraction'
-131 : 14363                             // decimal integer vs 'fraction'
divide 'fraction' by 16384
-131 + 0.8766

The final number is still correct, but the fraction is counted from the lower integer (-131), rather than the integer closest to zero (-130).

#35592 - ymalik - Mon Feb 07, 2005 8:08 pm

I'm having issues with the accuracy in fixed point. The following program should output a value around 801, but it is outputting 874. I need to use 18.14 format because I need to have up to 4 decimal places of accuracy.
Code:

typedef int FIXED;
#define TO_FIXED(n) ((n)*16384.0f) 

int main()
{
 float x = -74.1814, bound_x = -74.5018;
 FIXED xf = TO_FIXED(x), bound_xf = TO_FIXED(bound_x);       
 FIXED shifted_x = xf - bound_xf;
 FIXED dx = TO_FIXED(0.0004);         
 FIXED new_x = (shifted_x << 14) / dx;
 int pixel = new_x >> 14;
 
 printf("pixel: %i\n", pixel);
 
 return 0;
}


Is there anyway to get around this? Using 0.004 for dx works fine, though.

Thanks,
Yasir

#35627 - Cearn - Tue Feb 08, 2005 3:27 pm

ymalik wrote:

Code:

typedef int FIXED;
#define TO_FIXED(n) ((n)*16384.0f) 

int main()
{
  float x = -74.1814, bound_x = -74.5018;
  FIXED xf = TO_FIXED(x);                 // -1215388 (-0.something)
  FIXED bound_xf = TO_FIXED(bound_x);     // -12206637 (-0.something)
  FIXED shifted_x = xf - bound_xf;        // 5249 (1481h)
  FIXED dx = TO_FIXED(0.0004);            // 6 (+0.5536)
  FIXED new_x = (shifted_x << 14) / dx;   // 5204000h/6 = DAB555h
  int pixel = new_x >> 14;                // = 874 (+0.8333)
}

The main problem here is the definition of dx. It's a single digit, meaning that ever calculation you do with it will have just one digit of accuracy at best!! No amount of shifting the numerator is going to fix this. In fact, you could have just used shifted_x/ dx, which is 874(+0.8333) as well.
On the other hand, it divide beforehand (dx = 1.0/0.0004 = 2500), you have 4 digits of accuracy. 5249*2500 = 13122500 = (800 + 0.934)*16384, which I think is more to your liking.

The order of evaluation often matters in fixed point math, my mode7c demo shows that quite nicely. Unfortunately, the most accurate order depends very much on what kind of numbers you're dealing with, so there is no one-size-fits-all answer to give. Trace the code, check the numbers at every step and go from there.

I also found this site with more details about fixed point rounding that might be informative: http://www.bookofhook.com/Article/GameDevelopment/AnIntroductiontoFixedPoin.html

#35633 - stuleelight - Tue Feb 08, 2005 5:07 pm

What application could be used for floating point number systems as opposed to plain int's?
_________________
^o^

#35637 - ymalik - Tue Feb 08, 2005 6:44 pm

We are making a GPS device for the GBA. We are thinking about having the ability to display ESRI shapefiles, and all the vertices are stored as doubles.

#35642 - Miked0801 - Tue Feb 08, 2005 8:17 pm

Heck, world positions of characters should have sub-pixel accuracy in games - else sub-pixel velocities become impossible to handle. Long live fixed point!

#35682 - ymalik - Wed Feb 09, 2005 3:40 pm

The GBA is not properly reading the fixed point values I have stored in a seperate .c file linked into my program.
I have the following types defined:
Code:

typedef int FIXED;

typedef struct Point_t
{
 FIXED x;
 FIXED y;
} Point;

typedef struct Boundary_t
{
 Point min;
 Point max;
} Boundary;


I have an structure defined in a .c file as Boundary file_bounds = { {-1220637, 668801}, {-1214173, 675083} };
However, when I print out the values of the structure in GDB, I get { {-1214457, 668920}, {-1214452, 668925} }.
And it's like that for every structure I use. Why is this happening? This is really messing up my calculations.
[edit]It is also like that for simple arrays. For example, I have array called offsets that begins with {2, 2}, but when I print out offsets[0], I get 30732, but -19 for offsets[1].[/edit]

Thanks,
Yasir

#35774 - Miked0801 - Thu Feb 10, 2005 7:38 pm

Weird. Can you show us how your array is being defined - perhaps it's a 2D array and you're somehow getting a pointer value? Or your printf is broken. Strange

#35795 - ymalik - Thu Feb 10, 2005 11:20 pm

Here is what data.c looks like:
Code:

#include "types.h"

Boundary file_bounds = { {-1220637, 668801}, {-1214173, 675068} };

short offsets[] = {
2,
2,
4,
3,
3,
2,
...
}

Boundary bounds[] = {
{ {-1215388, 671377}, {-1215388, 671378} },
{ {-1215389, 671378}, {-1215388, 671380} },
{ {-1218907, 674629}, {-1218886, 674661} },
{ {-1218979, 674527}, {-1218964, 674555} },
{ {-1218979, 674429}, {-1218971, 674445} },
{ {-1218972, 674435}, {-1218938, 674445} },
{ {-1218972, 674445}, {-1218966, 674455} },
{ {-1218966, 674444}, {-1218928, 674455} },
...
}

Point vertices[] = {
{-1215388, 671377},
{-1215388, 671378},

{-1215388, 671378},
{-1215389, 671380},

{-1218907, 674629},
{-1218891, 674642},
{-1218889, 674645},
{-1218886, 674661},

{-1218964, 674555},
{-1218968, 674549},
{-1218979, 674527},
...
}


The file is compiled and linked to my program. Here is how I refer to them in the program. They are global variables:
Code:

extern Boundary file_bounds;
extern short offsets[];
extern Boundary bounds[];
extern Point vertices[];


I am not using printf; I'm using GDB. Here are some example values of the variables:
Code:

file_bounds =  {min = {x = -1214457, y = 668920}, max = {x = -1214452, y = 668925}}
offsets[0] = 30732
bounds[0] = {min = {x = -1214463, y = 669697}, max = {x = -1214475, y = 669692}}
vertices[0] = {x = -1218831, y = 673536}


The strange thing is that when I try to print out some of the variables in the debugger, I get message saying the symbol doesn't exist in the current context, but I have them there.

#35812 - Miked0801 - Fri Feb 11, 2005 1:21 am

Try throwing a const in front of the structures - perhaps the copy to RAM is screwing with things (or something is wiping RAM on you.)

#35857 - ymalik - Fri Feb 11, 2005 3:16 pm

Ok, thanks, that did the trick. But isn't the structure read from ROM and not brought into RAM?
Also, GDB does not recognize some of the variables I have in program--variables that are crucial to my calculations. It says that they not in the current context, even though I know they are since they are within the same scope as my other variables. This could be the reason why calculations are so far off.

#35865 - tepples - Fri Feb 11, 2005 5:31 pm

ymalik wrote:
Ok, thanks, that did the trick. But isn't the structure read from ROM and not brought into RAM?

Structures are read directly from ROM only if they're declared const.

Quote:
Also, GDB does not recognize some of the variables I have in program--variables that are crucial to my calculations.

If they're inner-loop variables, then perhaps they've been optimized out. GCC likes to do that; use -O0 (dash oh zero) to disable optimizations until you've finished stepping through the function.
_________________
-- Where is he?
-- Who?
-- You know, the human.
-- I think he moved to Tilwick.

#35896 - ymalik - Sat Feb 12, 2005 2:03 am

Thanks, you're great.
Is this a bug in GCC? Here's what I had:
Code:

int main()
{
 FIXED pixel_length = TO_FIXED(0.004);
 ...
 [loop]
 prev_x = swi_div((vertices[vertex_pointer].x - xmin) << 14, pixel_length);

And pixel_length was being taken out. So this was a critical value.
I'm going to change the operation to use multiplication, though.