GB101:Fixed point math

GB101 Class Notes
	Sections Home Installing Gameboy Development Tools Introduction to the Gameboy Advance Hello Background Working with Palettes Tiles and Background Maps Sprites Scrolling Backgrounds Collision Detection Fixed point math Affine Sprites Sound Where do I go from here?

Introduction

Even today many embedded processors lack the luxury of a floating point unit. You can still do math with floats, but it will be very slow. The common alternative is to use fixed point math, where you dedicate some number of bits of an int to act as your float. Floating point numbers are usually referred to by a n.m notation, where n is the number if bits used for whole numbers and m is the number of bits used for fractions. An 16.8 fixed point number has 16 bits for whole numbers and 8 bits for fractions. In a 16.8 fixed point number the fraction is m/256, so 1 == 1/256, 256 == 1, and 257 == 1 1/256. The nice thing about this approach is that addition and subtraction work normally, the bits just automatically overflow into whole numbers as they would for any other int.

Creating fixed point numbers

Making a fixed point number is easy, just shift-left by the number of bits you would like to use. Get get the whole number back, shift-right the same number of bits.

typedef s32 FIXED;

#define FIX_SHIFT		8
#define FIX_SCALE		(1<<FIX_SHIFT)
#define INT_TO_FIXED(i)		((i)<<FIX_SHIFT)
#define FRAC_TO_FIXED(i,j) 	((i)<<FIX_SHIFT/j) 
#define FIXED_TO_DOUBLE(i) 	(((double)i)/256.0)
#define FIXED_TO_INT(i) 	((i)>>FIX_SHIFT)
#define DOUBLE_TO_FIXED(i) 	((int)(i * 256.0 + 0.5))

Wait, I thought you said don't use floats, what's with the double? True, but remember these are macros, so if you're using these to define constants like PI then the compiler will be nice enough to do the math for us ahead of time.

Fixed point math

Arithmetic

Addition and subtraction are easy, just go ahead and do them as normal. Multiplication and division are a little more involved.

// Add two fixed point values
INLINE FIXED fxadd(FIXED fa, FIXED fb) {
    return fa + fb;
}

// Subtract two fixed point values
INLINE FIXED fxsub(FIXED fa, FIXED fb) {
    return fa - fb;
}

// Multiply two fixed point values
INLINE FIXED fxmul(FIXED fa, FIXED fb) {
    return (fa*fb)>>FIX_SHIFT;
}

// Divide two fixed point values.
INLINE FIXED fxdiv(FIXED fa, FIXED fb) {
    return ((fa)*FIX_SCALE)/(fb);
}

Square Root

At some point you'll probably need the sqrt() function. Here's an algorithm I've shamelessly poached off the internet.

FIXED fxsqrt(FIXED n) {
    int s = (n + 65536) >> 1;
    int i;

    for (i = 0; i < 8; i++) {
        s = (s + fxdiv(n, s)) >> 1;
    }
	
    return s;
}

Trigonometry

Sine and Cosine

The sin(r) and cos(r) are handy too. We'll need them for the next section on affine sprites and backgrounds. The easiest way to get these is to simply have a lookup table or lut. A set of luts are included with the tonc library. Here's a quick C routine that you can run to generate your own.

#include <stdio.h>

typedef s32 FIXED;

#define FIX_SHIFT		8
#define FIX_SCALE		(1<<FIX_SHIFT)
#define INT_TO_FIXED(i)		((i)<<FIX_SHIFT)
#define FRAC_TO_FIXED(i,j) 	((i)<<FIX_SHIFT/j) 
#define FIXED_TO_DOUBLE(i) 	(((double)i)/256.0)
#define FIXED_TO_INT(i) 	((i)>>FIX_SHIFT)
#define DOUBLE_TO_FIXED(i) 	((int)(i * 256.0 + 0.5))
#define FIXED_PI		DOUBLE_TO_FIXED(3.14)
#define FIXED_2PI		DOUBLE_TO_FIXED(2*3.14)
#define FIXED_3PIOVER4		DOUBLE_TO_FIXED(3*3.14/4)
#define FIXED_PIOVER4		DOUBLE_TO_FIXED(3.14/4)

int main() {
    int i;
    printf("const int sin_lut[%d] = {\n",FIXED_2PI);
    for (i=0; i<FIXED_2PI; i++) {
        printf("%4d",DOUBLE_TO_FIXED(sin(FIXED248_TO_DOUBLE(i))));
        if (i<FIXED_2PI-1) { 
            printf(", "); 
        }
        if (i % 8 == 7) {
            printf("\n");
        }
    }
    printf("};\n\n");

    printf("const int cos_lut[%d] = {\n",FIXED_2PI);
    for (i=0; i<FIXED_2PI; i++) {
        printf("%4d",DOUBLE_TO_FIXED(cos(FIXED_TO_DOUBLE(i))));
        if (i<FIXED248_2PI-1) { 
            printf(", "); 
        }
        if (i % 8 == 7) {
            printf("\n");
        }
    }
    printf("};\n");

    return 0;
}

Arctangent

atan2(y,x) is also useful. Let's shamelessly pull from the internet once more..

FIXED fxatan2(FIXED y, FIXED x) {
    FIXED coeff_1 = FIXED_PIOVER4;
    FIXED coeff_2 = FIXED_3PIOVER4;
    FIXED abs_y = y;
    FIXED r;
    FIXED angle;

    if (abs_y<0) {
        abs_y = -abs_y;  // abs
    } 
    else if (abs_y==0) {
        abs_y=1;	// prevent div/0
    }
	    
    if (x>=0) {
        r = fixdiv(x-abs_y, x+abs_y);
        angle = coeff_1 - fixmul(coeff_1, r);
    }
    else {
        r = fixdiv(x + abs_y, abs_y - x);
        angle = coeff_2 - fixmul(coeff_1,r);
    }

    if (y < 0)
        return(-angle);     // negate if in quad III or IV
    else
        return(angle);
}

Converting degrees to radians

8-bits isn't a whole lot of precision, so when converting to radians from a constant it's good to use a macro.

// Note that i is an int, not a FIXED
#define FIXED_IDEG_TO_RAD(i)	DOUBLE_TO_FIXED(((double)i)*(3.14159263/180.0))

// Convert degrees to radians.  Dividing by 180 doesn't leave a lot of precision, use FIXED_IDEG_TO_RAD for initializing
FIXED fxdeg2rad(FIXED deg) {

    return fxmul(deg,fixdiv(FIXED_PI,INT_TO_FIXED(180)));
}

// Convert radians to degress.
FIXED fxrad2deg(FIXED rad) {
    return fxmul(rad,fixdiv(INT_TO_FIXED(180),FIXED_PI));
}

Just look at the difference between the macro and the function:

FIXED_TO_DOUBLE(fxrad2deg(FIXED_IDEG_TO_RAD(360))) = 359.992188
FIXED_TO_DOUBLE(fxrad2deg(fxdeg2rad(INT_TO_FIXED(360)))) = 322.382812

Vectors and Physics

With all this math it should be possible to create a vector and physics library. There's a set of vector functions included with tonclib but they're intended for linear algebra. I've started work on a more traditional angle-magnitude library and physics library. It's not complete, but the latest version is included with this kit.