#51397 - jarobi - Fri Aug 19, 2005 4:34 am
Hi all!
I have created a new way to handle fixed point numbers after researching them a bit more and noticing flaws in my previous fixed point code. The following code is meant to be used exclusively for the GBA, but could be modified for other uses:
| Code: |
//Header File
typedef struct
{
s16 integer:8;
u16 fraction:8;
} Fixed_S;
typedef struct
{
u32 filler:4;
s32 integer:20;
u32 fraction:8;
} Fixed_L;
//...
#define FIXED_SC 256f
#define FLOAT_SC 0.0039f //(1/256)
#define floatToFixed_S(n) (Fixed_S)(n*FIXED_SC)
#define floatToFixed_L(n) (Fixed_L)(n*FIXED_SC)
#define fixedToFloat(n) (((float)n)*FLOAT_SC)
#define fixedFract(n) (n&0xff) //isolates the fractional part of a fixed point number
#define fixedInt_S(n) ((n&0xff00)>>8) //isolates the integer part of a fixed point number for Fixed_S
#define fixedInt_L(n) ((n&0xfffff00)>>8) //isolates the integer part of a fixed point number for Fixed_L
#define newFixed(i, f) ((i<<8)|(f&0xff)) //i = integer part (signed), f = fraction part (unsigned)
#define fixedNeg(n) (0-n)
Fixed_S fixedMult_S(Fixed_S, Fixed_S);
Fixed_L fixedMult_L(Fixed_L, Fixed_L);
Fixed_S fixedDiv_S(Fixed_S, Fixed_S);
Fixed_L fixedDiv_L(Fixed_L, Fixed_L);
Fixed_S fixedAbs_S(Fixed_S);
Fixed_L fixedAbs_L(Fixed_L);
//...
//Source File
Fixed_S fixedMult_S(Fixed_S a, Fixed_S b)
{
s32 temp, la, lb;
Fixed_S product;
la = ((s32)(a.integer)<<8)+(u32)(a.fraction);
lb = ((s32)(b.integer)<<8)+(u32)(b.fraction);
temp = la * lb;
temp /= 256; //using division instead of bit shifting to preserve sign
product.integer = fixedInt_S(temp);
product.fraction = fixedFract(temp);
return product;
}
Fixed_L fixedMult_L(Fixed_L a, Fixed_L b)
{
s64 temp, la, lb;
Fixed_L product;
la = ((s64)(a.integer)<<8)+(u64)(a.fraction);
lb = ((s64)(b.integer)<<8)+(u64)(b.fraction);
temp = la * lb;
temp /= (s64)256; //using division instead of bit shifting to preserve sign
product.integer = fixedInt_L(temp);
product.fraction = fixedFract(temp);
return product;
}
Fixed_S fixedDiv_S(Fixed_S n, Fixed_S d)
{
s32 temp, ln, ld;
Fixed_S quotient;
ln = ((s32)(n.integer)<<8)+(u32)(n.fraction);
ld = ((s32)(d.integer)<<8)+(u32)(d.fraction);
temp = ln<<8;
temp /= ld;
quotient.integer = fixedInt_S(temp);
quotient.fraction = fixedFract(temp);
return quotient;
}
Fixed_L fixedDiv_L(Fixed_L n, Fixed_L d)
{
s64 temp, ln, ld;
Fixed_S quotient;
ln = ((s64)(n.integer)<<8)+(u64)(n.fraction);
ld = ((s64)(d.integer)<<8)+(u64)(d.fraction);
temp = ln<<8;
temp /= ld;
quotient.integer = fixedInt_L(temp);
quotient.fraction = fixedFract(temp);
return quotient;
}
Fixed_S fixedAbs(Fixed_S num)
{
return (num < 0) ? -num : num;
}
Fixed_L fixedAbs(Fixed_L num)
{
s32 temp;
Fixed_L abs;
temp = ((s32)(num.integer)<<8)+(s32)(num.fraction);
temp = (temp < 0) ? -temp : temp;
abs.integer = fixedInt_L(temp);
abs.fraction = fixedFract(temp);
return abs;
}
|
If anyone notices any flaws with this system or anything that can be improved upon, please let me know. Thanks in advance!
_________________
Nihongo o hanasemasen!
#51399 - sajiimori - Fri Aug 19, 2005 4:44 am
That won't even compile. Why are you trying to compare a Fixed_S struct using the < operator? Why are you wasting the high 4 bits of your 32 bit fixed format? Why is fixedAbs(Fixed_L) so complicated when the regular integer abs would work fine? Why use structs at all?
#51404 - jarobi - Fri Aug 19, 2005 5:56 am
I now realize my error with comparing the Fixed_S struct using the < operator; I probably should have casted it first. However, I wasted the 4 top bits in the 32 bit fixed format because I read in the cowbite specs that they are not used in the rotation and scaling registers.
http://www.cs.rit.edu/~tjh8300/CowBite/CowBiteSpec.htm#Background%20Rotation/Scaling%20Regi
I did this so that I would not run into issues with the sign bit, but please let me know whether this is really necessary or not. I'm not entirely sure if this is how "32 bit" fixed point numbers are represented on hardware; I'm placing a lot of faith on the cowbite specs.
My reason for using structs is so that I can easily isolate the integer and fraction parts and not have to deal so much with shifting, etc.
The reason why the 32 bit fixed point abs is so complex is because I do not know what is in the first 4 bits and I do not want unexpected results by just negating the number. But when I think of it now, the only time this is an issue is when there is overflow, and it wouldn't make sense to want overflow for a scaling/rotation value. I must have been really tired when I wrote this code :). Maybe what I should do instead is define a minimum and maximum value for fixed point numbers instead...
I think you may be right about the structs to begin with too; now that I think of it, why was I using them to begin with? My main motivation for creating this system is to be able to work with fixed point numbers almost as easily as regular ints, because fixed point numbers are kind of a pain.
Thanks for your input sajimori! You really helped me think critically about my code which is what I wanted to begin with. If anyone has any neat tricks I can use for messing around with fixed point numbers please let me know.
P.S. I have not even tried to compile my code yet, I'm not that masochistic :)
_________________
Nihongo o hanasemasen!
#51405 - sajiimori - Fri Aug 19, 2005 6:17 am
I don't know what the format of the registers are off the top of my head. The reason I don't know is that there's no need for me to think about it. I wouldn't design my whole fixed point system around the format a couple registers happen to use.
The best trick for making fixed point values as easy to work with as ints is to write a fixed point class that uses operator overloading.
#51406 - poslundc - Fri Aug 19, 2005 6:40 am
| sajiimori wrote: |
| The best trick for making fixed point values as easy to work with as ints is to write a fixed point class that uses operator overloading. |
Or, failing that, just do the math yourself. One of the reasons fixed-point math is so popular is that it's easy, and nearly all of the normal mathematical operations are the same or only slightly changed from their int counterparts.
A good wrapper class may help reduce your programmer error, and spare you from having to document your code exhaustively. But calling macros or functions everywhere when all you want to do is shift or multiply or something does little more than serve to obfuscate code, I find.
On the other hand, I've written large pieces of code where the only data type is int, and I simply make consistent comments every time the precision changes. It lets me have as much versatility with precision as I want, and the code is easy to read and understand for anyone who understands fixed-point mathematics.
Dan.
#51407 - sajiimori - Fri Aug 19, 2005 7:13 am
| Quote: |
| Or, failing that, just do the math yourself. |
Well, I've got this computer in front of me... I just figured its job was to like, compute stuff for me. ;)
| Quote: |
| But calling macros or functions everywhere when all you want to do is shift or multiply or something does little more than serve to obfuscate code, I find. |
That's what operator overloading is for. Have you seen the Fixed template? | Code: |
Fx32 a = 5.2; // Floats? Not in the output!
Fx32 b = 125.7;
f(a * b + 2); |
| Quote: |
| On the other hand, I've written large pieces of code where the only data type is int, and I simply make consistent comments every time the precision changes. |
That's good, your readers will need them. I'd rather build those facts directly into typesafe code. Did I mention that Fx32 is a typedef? | Code: |
Fixed<short, 4> a = 55.2; // 12 integer bits, 4 fractional.
Fixed<int, 16> b = a; // 16 integer bits, 16 fractional, safe conversion. |
Oh, and debugging! | Code: |
Fx32 val = 5823.784;
cout << val.toFloat(); // Wouldn't do it in production code, of course. |
#51410 - poslundc - Fri Aug 19, 2005 7:53 am
I have no problem with the Fixed template, and I've no doubt as to its utility in the kind of environment we work in.
But there are tradeoffs as well. How much code do you suppose is written in our studio using 20.12 just because it is typedefed, when say, 16.16 would be in the acceptable range and provide a tangibly better level of accuracy? How many cycles do you suppose we lose by automatically using generic division routines instead of compiler-optimized inverse multiplication? Or by not knowing when 64-bit multiplication is necessary/warranted? How about the ability to dynamically adjust precision without either instantiating new objects or invalidating the substance of the class?
Don't get me wrong; I appreciate both the encapsulation and elegance of the Fixed class. But there are plenty of advantages to working in the literal domain as well.
Dan.
#51449 - sajiimori - Fri Aug 19, 2005 6:52 pm
As I see it, there are only psychological trade-offs, and no real ones.
If someone chooses to use the Fx32 typedef because it is the easier thing to do, you cannot blame the fact that it was made easy, especially considering that other typedefs could be made as desired. I'd be inclined to blame the programmers if they are using something inappropriate.
(As a side note, having 19 bits of integer actually mattered for us in some cases, particularly when dealing with squared lengths and some of our larger side-scrolling levels. A few more fractional bits might have helped for normals or time values in the range 0-1, but it worked out anyway.)
If you want to use unusual division or multiplication methods, you can define your own operations (or unwrap the value and do it by hand). I've never had occasion to do it, myself. My optimization efforts were always better spent elsewhere.
Dynamically adjusting precision sounds like floating point. I'd be enormously confused if the same raw integer variable represented different precisions at different times. At least the fixed class would require explicit casts, but the whole thing sounds fishy to me.
#85426 - wintermute - Tue May 30, 2006 3:59 am
| sajiimori wrote: |
As I see it, there are only psychological trade-offs, and no real ones.
|
The trade offs are very real. As psolundc has pointed out fixed point doesn't have to be 16.16 or indeed any particular combination of integer and fractional part. If you write a class or a set of macros to deal with one particular precision you're basically stuck with it.
| Quote: |
Dynamically adjusting precision sounds like floating point. I'd be enormously confused if the same raw integer variable represented different precisions at different times. At least the fixed class would require explicit casts, but the whole thing sounds fishy to me. |
Dynamic precision adjustment is actually quite common in code where the programmer is doing it by hand. In places where you know the integer part is quite small you can increase the fractional part for increased accuracy ( in trig tables for instance ).
If I'm writing fixed point code from scratch I'll tend to handle precision dynamically as required. On the other hand, fixed point encapsulation classes would be very useful for porting float heavy code. Both have their uses.
_________________
devkitPro - professional toolchains at amateur prices
devkitPro IRC support
Personal Blog
#85437 - keldon - Tue May 30, 2006 10:40 am
I was thinking of doing something similar to my texture mapping code because 1/z is very innacurate in 16:16
#85471 - Cearn - Tue May 30, 2006 6:10 pm
| sajimori wrote: |
| jarobi wrote: | | The reason why the 32 bit fixed point abs is so complex is because I do not know what is in the first 4 bits and I do not want unexpected results by just negating the number. But when I think of it now, the only time this is an issue is when there is overflow, and it wouldn't make sense to want overflow for a scaling/rotation value. |
I don't know what the format of the registers are off the top of my head. The reason I don't know is that there's no need for me to think about it. I wouldn't design my whole fixed point system around the format a couple registers happen to use. |
And there's more to it than this. The affine registers are only the last stop; all the actual mathematical operations should be completely oblivious to the hardware formats. In fact, they can't be anything but oblivious, at least for backgrounds, because BG affine registers are write-only. The fixed point math should be done in as many bits as you can or as many as is convenient. That means 32 or maybe 64 bits. Cutting off the top 4 bits or even the top 16 bits in the Fixed_S struct serves no purpose and only makes things more difficult for yourself, slower and probably less accurate as well. If there is going to be overflow when you out things in the registers, you can't stop that. There's no need to make it worse by forcing all the intermediary calculations to have overflow problems too.
| jarobi wrote: |
My reason for using structs is so that I can easily isolate the integer and fraction parts and not have to deal so much with shifting, etc.
|
But there is rarely a need for to get the fractional part, and in the mean time you're making everything else ? all the things that you do use a lot ? more complicated. Because you've split the number into two parts, addition, subtraction, multiplication and division all need a lot of extra code now. They used to be one operation, two for mul/div. Now they're well over 20 (bitfields are compiled to shifts and masks, a lot of them. You may not see them, but they're there.)
Fixed points aren't divided into an integer and fractional part, they are fractions. The numerators of fractions to be precise, the denominators are determined by the fixed-point position. Because of how fraction math works add and sub are still simple, but mul and div need extra attention because the resultant denominator changes as well. While this can be annoying, the fixed point numbers still form one single integer.
Aside from that, you still can't easily isolate the integer and fractional parts easily, because they won't be correct for negative numbers. Take the 8-point fixed version of -1.25, for example. This is -0x140= FFFFFE.C0. This would resolve to an integer part of -2, and a fractional part of +192. While this is technically correct, these are not the int and fractional parts that you might have expected.
EDIT: 0xC0 is 192, not 64.
@ sajimori: I think I saw that Fixed template once, but can't find it anymore. Linky?
#85565 - crossraleigh - Wed May 31, 2006 7:32 pm
In case sajiimori isn't allowed to post their template, I thought I'd show one I made. I've not tested it very rigorously but it has worked OK so far and I think it's fairly complete. It seems to be more or less compatible with the examples he posted.
| Code: |
#include <ostream>
template<class T, int fractionBits> struct Fixed {
T value;
Fixed() {}
Fixed(double d) : value(static_cast<T>(d * (1 << fractionBits) + 0.5)) {}
template<class oldT, int oldFractionBits>
Fixed(const Fixed<oldT, oldFractionBits>& f)
{
int shift = fractionBits - oldFractionBits;
value = (shift > 0) ? f.value << shift : f.value >> -shift;
}
const Fixed& operator += (const Fixed& rhs) { value += rhs.value; return *this; }
const Fixed& operator -= (const Fixed& rhs) { value -= rhs.value; return *this; }
const Fixed& operator *= (const Fixed& rhs) { value *= rhs.value; value >>= fractionBits; return *this; }
const Fixed& operator /= (const Fixed& rhs) { value <<= fractionBits; value /= rhs.value; return *this; }
const Fixed operator + (const Fixed& rhs) const { return Fixed(*this) += rhs; }
const Fixed operator - (const Fixed& rhs) const { return Fixed(*this) -= rhs; }
const Fixed operator * (const Fixed& rhs) const { return Fixed(*this) *= rhs; }
const Fixed operator / (const Fixed& rhs) const { return Fixed(*this) /= rhs; }
const Fixed& operator + () const { return *this; }
const Fixed operator - () const { Fixed f; f.value = -value; return f; }
bool operator == (const Fixed& rhs) const { return value == rhs.value; }
bool operator != (const Fixed& rhs) const { return value != rhs.value; }
bool operator <= (const Fixed& rhs) const { return value <= rhs.value; }
bool operator >= (const Fixed& rhs) const { return value >= rhs.value; }
bool operator < (const Fixed& rhs) const { return value < rhs.value; }
bool operator > (const Fixed& rhs) const { return value > rhs.value; }
friend std::ostream& operator << (std::ostream& lhs, const Fixed& rhs)
{
lhs << static_cast<double>(rhs.value) / (1 << fractionBits);
return lhs;
}
}; |
Notice that you have to be careful when using operators across different precisions.
| Code: |
typedef Fixed<int, 12> F32;
typedef Fixed<short, 4> T16;
F32 a = 1.61803399; // Becomes approx 1.61792.
T16 b = 2.71828183; // Becomes 2.6875.
std::cout << a << " * " << b << " = " << a * b << "\n"; // F32::operator*(F32(T16)).
std::cout << b << " * " << a << " = " << b * a << "\n"; // T16::operator*(T16(F32)) is less accurate.
b = a;
std::cout << a << ((a == b) ? " == " : " != ") << b << "\n"; // Not equal as F32s.
std::cout << b << ((b == a) ? " == " : " != ") << a << "\n"; // Equal as T16s. |
#85575 - sajiimori - Wed May 31, 2006 9:42 pm
wintermute,
A templatized class like the one crossraleigh just posted keeps you from being locked into a particular format.
Your example of trig tables does not sound like an instance of dynamically adjusting precision. That sounds like statically determining precision, but choosing different precisions for different cases, which I agree is perfectly normal.
crossraleigh,
That's very much like the class we use here. I'd probably make the conversion constructor explicit. You might want to specialize the multiply to use a double-sized workspace for common types (like 16.16 or 20.12) to avoid overflow (since it's very easy to overflow a 32x32 multiplication when using a 32 bit workspace). Also, the divide could be specialized to use the coprocessor.
#85581 - wintermute - Thu Jun 01, 2006 12:07 am
| sajiimori wrote: |
wintermute,
A templatized class like the one crossraleigh just posted keeps you from being locked into a particular format.
|
but doesn't it automatically adjust the precision of the values as they're calculated?
| Quote: |
Your example of trig tables does not sound like an instance of dynamically adjusting precision. That sounds like statically determining precision, but choosing different precisions for different cases, which I agree is perfectly normal.
|
but dealing with different precisions leads to yet more different precisions when you're performing calculations on them. Admittedly addition and subtraction requires the values to be normalised to the same precision but multiplication does not. It can be extremely useful to retain the increased fractional accuracy of these calculations as long as possible.
_________________
devkitPro - professional toolchains at amateur prices
devkitPro IRC support
Personal Blog
#85586 - sajiimori - Thu Jun 01, 2006 1:50 am
I don't know what you mean by automatically adjusting precision.
About retaining precision after multiplies, I assume you mean using a larger data type. Here's one example of that:
| Code: |
typedef Fixed<int, 16> Fx32;
typedef Fixed<long long, 32> Fx64;
Fx32 a = ...;
Fx32 b = ...;
Fx64 c = Fx64(a) * Fx64(b);
|
However, since operator*() should be written to work well in the general case, it would use a 128 bit temporary workspace to perform that multiplication. If I was having speed problems, I'd use a separate function that multiplies two Fx32s and returns a Fx64.
In any case, these decisions are made statically.
#85709 - tepples - Thu Jun 01, 2006 11:13 pm
| wintermute wrote: |
| sajiimori wrote: | wintermute,
A templatized class like the one crossraleigh just posted keeps you from being locked into a particular format. |
but doesn't it automatically adjust the precision of the values as they're calculated? |
No, because that'd be called "floating point" ;-)
_________________
-- Where is he?
-- Who?
-- You know, the human.
-- I think he moved to Tilwick.
#85792 - wintermute - Fri Jun 02, 2006 11:15 am
| tepples wrote: |
| wintermute wrote: | | sajiimori wrote: | wintermute,
A templatized class like the one crossraleigh just posted keeps you from being locked into a particular format. |
but doesn't it automatically adjust the precision of the values as they're calculated? |
No, because that'd be called "floating point" ;-) |
You're missing the point completely :P
when you multiply and divide, the point moves. When I say "adjust the precision" I'm talking about renormalising back to where you've decided the point should be.
_________________
devkitPro - professional toolchains at amateur prices
devkitPro IRC support
Personal Blog
#85861 - sajiimori - Fri Jun 02, 2006 7:12 pm
Alright, then I already explained how it's easy to avoid unwanted precision loss from normalization.