GP32 Something I Learned


Daz_Genetic

Certified Guru
Joined
Oct 26, 2003
Messages
424
Age
42
Location
Maine, USA
Website
www.dazos.com
I'm not a very good coder, but I came across something today that I thought I should share.

I have been doing my maths with 32bit(16:16) fixed point numbers, but in certain cases my multiply and divide macros would return 0. I'm guessing that the numbers got shifted too far. If I changed my type to a 64bit int, everything would be fine. But this was very noticably slower.

My solution. I kept the 32bit fixed point numbers, but created a second 64bit type and a secondary macro for my multiplies and divides.

typedef long long int fxd64;

#define fxd_mul64(x,y) (((fxd64)(x)*(y))>>16)
#define fxd_div64(x,y) (((fxd64)(x)<<16)/(y))

In cases where 32bit operations don't work, I call fxd_mul64/fxd_div64 instead. All these do is cast the first number to a 64bit int, then carry out the operation on that. Of course that is slower, but I don't use it everywhere, only the places that really need it. Everything else is carried out on 32bit ints, so there is less data being passed around. And since I am mostly using incremental maths, most of my inner loops are filled with 32bit +'s and -'s. The slower mul's and div's are carried out in the function's initialisation.

By changing my fixed type back to 32bit, My program actually runs just about twice as quick. That is pretty major, so it is important to avoid 64bit operations as much as you avoid using floating point ones.

I am still trying to make the whole thing a little more elegant, so if anyone has any advice that would make the above redundant, please feel free to help.
 

Robster

Dodgy hardware mod maker
Joined
Jul 8, 2003
Messages
439
Location
New Zealand
Website
www.cobbleware.com
Hey Daz_Genetic,

That's a pretty good solution you've got there. I think it can be improved (although I'm not sure) with:
Code:
typedef long long int fxd64;

#define fxd_mul64(x,y) ( (int)( ( ( (fxd64)x) * ( (fxd64)y) ) >> 16 ) )
#define fxd_div64(x,y) ( (int)( ( ( (fxd64)x) << 16 ) / y) )
The reason it gets sped up is that the CPU has a built-in, fast, 32bit * 32bit -> 64bit multiply instruction, and the compiler knows about it. If the compiler can see that the values being multiplied are 32 bits (or are 64 bits but the upper 32 bits are zero), the intermediate value is 64 bit, and the final value is 32 bit, then it can use the built-in instruction. If those conditions aren't satisfied, then the compiler must take the safe option and call a (slow) library function to do the multiply. I think you should be OK using fxd_mul64 for pretty much all of your multiplies without slowing down.

Divides are always slow, so best try to avoid them completely if possible :)
 

Daz_Genetic

Certified Guru
Joined
Oct 26, 2003
Messages
424
Age
42
Location
Maine, USA
Website
www.dazos.com
That is totally awesome. I never knew about that instruction. I need to learn more about the hardware, but at the moment, I'm just happy getting my game to run at a decent framerate :)
 

Daz_Genetic

Certified Guru
Joined
Oct 26, 2003
Messages
424
Age
42
Location
Maine, USA
Website
www.dazos.com
Only when dividing/multiplying by a power of two can you use shifts instead of a normal operation..

Here is a useful bit of code I wrote. It checks if a number is a power of two and then returns the appropriate power.

Code:
Uint8 get_Pow( int n ){
  if ( ( n & n-1 ) == 0 ){ // Check if the number really is a power of two
    int shift = 0;
    while( 1 ){
      shift ++;
      if ( n >> shift & 0x01 ){ // Check if current shift is correct
        return shift;
      }
    }
  } else {
    return 0;
  }
}
 

Robster

Dodgy hardware mod maker
Joined
Jul 8, 2003
Messages
439
Location
New Zealand
Website
www.cobbleware.com
TeDaDeS: if the multiplication and division are done in software, then yes the methods are similar and they will take a similar time. However, CPUs have hardware features to speed them up. The ARM9 CPU in the GP32 has a hardware multiplier, but not a hardware divider. So multiply can be made into a fast CPU instruction, while divides are always a slow library function call.

Daz_Genetic: that's an interesting bit of code- especially the "n & n-1" check, which I've never seen before. Just for the sake of arguing :), I would make the inner loop something like
Code:
int shift = 1;
while (shift) {
    if (shift == n)
       return shift;
    shift <<= 1;
    }
This avoids having to calculate "1<<n" every pass through the loop. shift becomes zero when the 1 is shifted out of bit 31.
 

Daz_Genetic

Certified Guru
Joined
Oct 26, 2003
Messages
424
Age
42
Location
Maine, USA
Website
www.dazos.com
:), you're on form today.. I wasn't using that code in realtime, but It's a good optimization anyway.

I actually learned that "n & n-1" check from an old programmer friend. I beleive he got it from one of those "graphics gems" books. I also have some quite nice Dithering code I picked up from one of those books too. They are very useful.

Edit: I spotted a problem. You're code returns the actual number as opposed to the power of 2. The reason my code returns the power is so you can use that number as a shift, to multiply/divide.
 

Saotome

Still Fresh
Joined
Oct 1, 2003
Messages
29
Robster posted on Apr 19 2004 at 12:23 AM said:
...The ARM9 CPU in the GP32 has a hardware multiplier, but not a hardware divider. So multiply can be made into a fast CPU instruction, while divides are always a slow library function call...
:blink: whoa, i didnt know that the arm9 has no divide instruction (i thought that all/most processors have), but just checked it in the arm-documentation and its true. but actually i just wanted to say that divides are really much slower than multiplies even in hardware.
i found some interesting code to normalize vectors recently.
a good example how you can save some divide-instructions. its for floating point calculations but maybe you can also use it for fixed point:

_d = 1 / w; //w = length of vector
nx = x * _d;
ny = y * _d;
nz = z * _d;

instead of:

nx = x / w;
ny = y / w;
nz = z / w;

it really speeds up the code significantly (+50% - already tested it - not on GP but on my PC but the results should be similar)
 
Last edited by a moderator:

Daz_Genetic

Certified Guru
Joined
Oct 26, 2003
Messages
424
Age
42
Location
Maine, USA
Website
www.dazos.com
Yes, 1/number is referred to as the reciprocal of the number. If you plan on dividing by a number more than once, it's always beneficial to find the reciprocal and then use multiply instead.

This thread is turning out to be full of interesting tips. Let's keep it going! :)
 

Robster

Dodgy hardware mod maker
Joined
Jul 8, 2003
Messages
439
Location
New Zealand
Website
www.cobbleware.com
Daz_Genetic: well spotted with my error up there, my excuse is that I wasn't testing it as I was writing ;) You could get the bit number by having a separate counter, and it would probably still be faster than the original code that did a "1<<n" inside the loop.

Now here's an error in your code: if the value of n is 1, get_Pow should return 0 (because 1 is 2^0). If you call the function with n=1, then your get_Pow will loop endlessly :( because n & n-1 does equal 0, but shift effectively starts at 1 so n >> shift will always be zero.

Also, get_Pow doesn't have a return value that means "this number was not a power of 2". Perhaps it should? If we make 255 mean that, then your function could be
Code:
Uint8 get_Pow( int n ){
 if ( ( n & n-1 ) == 0 ){ // Check if the number really is a power of two
   int shift = 0;
   while( 1 ){
     if ( n >> shift & 0x01 ){ // Check if current shift is correct
       return shift;
     shift ++;
     }
   }
 } else {
   return 255;
 }
}
 

Robster

Dodgy hardware mod maker
Joined
Jul 8, 2003
Messages
439
Location
New Zealand
Website
www.cobbleware.com
OK, more on finding the bit number: a general speedup tool for "finding" things like this is to use a binary search. Note that with my first code, if the number is 1, the loop will be executed once, but if the number is 1<<31, then the loop will be executed 31 times. That means that the loop can be slow, and also that the time to execute it varies quite a lot which can also be a problem.

One answer is to start looking in the centre of the range, and then alter the comparison value starting with large steps and making the steps smaller with each iteration until you converge on the solution. This means that although the loop is a little more complicated (although it's still very simple), the number of times through the loop will never be greater than 5.
Code:
unsigned char get_Pow (int n)
{
   int mask=0x10000;
   unsigned char count = 16;
   unsigned char step = 16;

   if (n==1)
      return 0;

   if ((n)&(n-1))
   {
      while (step)
      {
         step>>=1;
         if (mask==n)
            return count;
         if (n>mask)
         {
            mask<<=step;
            count+=step;
         }
         else
         {
            mask>>=step;
            count -= step;
         }
      }
   }

   return 255;
}
 

Daz_Genetic

Certified Guru
Joined
Oct 26, 2003
Messages
424
Age
42
Location
Maine, USA
Website
www.dazos.com
Yeah, I kinda knew about the issue when n=1 but I never got round to fixing it since I never needed it to detect 1. Thanks for fixing that for me anyway. The code you have written seems to look very good and fast. I will certainly implement it. Will that second branch for n=1 slow it down much. I could comment it out if I don't need it, but will probably leave it in if you feel there would be no speed decrease.

These are the great things that come from people bashing their heads together. I so wish I could develop in a team environment. Sometimes coding is a very lonely pastime. :)

Also, I believe on ARM that comparisons against 0 are for free, so I think that since I won't be needing n=1, I should pass 0 back as "not a power of two". That would save a cycle i think ;).
 

Robster

Dodgy hardware mod maker
Joined
Jul 8, 2003
Messages
439
Location
New Zealand
Website
www.cobbleware.com
Without the test for n==1 at the start, the binary search won't work (it will return 1, which is the proper return value when n==2). The reason for this is that it will search 8+4+2+1 = 15 bits either side of the starting point. The starting point is 16, so it will search bits 31 to 1, and bit 0 is missed out.

I don't think the special check for n==1 will slow things down too much :)
 
Top