How to work with fixed point math

Some sonic hackers may be unaware of how sonic gets his variable speed the answer is fixed point math that allows for decimals on the sega genesis without an expensive (at the time FPU floating point processor)


The way it works is much simpler than floats and fixed point does not have rounding errors unless there is not enough bits to store the number.The way fixed point math works is very simple


If you have a varible (usually on the genesis it would a 2byte variable refereed to as a word) you divide it up into 2 parts the fractional part and the whole number part lets say you want the both the fractional part and the whole number part of the word to be 8 bits so what you do in your calculate is enter 2 to the power of how many fractional bits there are in this case do 28 which is 256 you will need that latter. So lets say we want to have .5 in fixed point math you would simply multiply .5 by 256


which is 128 now lets say we want to do add .5 all you have to do use the add instruction it is the same. see 128+128=256 which is one now to convert to a non-fixed point integer you simply bitshift to the right by the number of fractional bits there are in this case 8 to do this in asm do

Code:

lsr.w #8,d0;shift to the right by a factor of 8

the same is for subtraction just use the same instructions nothing special has to happen However for multiplication and division it is different

if you are doing fixed point math and multiply or divided by an integer (not fixed point) it works

here is an example see how an integer times a fixed point number needs no special handling.

Code:

move.w #128,d1 ;.5 in fixed point 8.8

mulu.w #5,d1 ;warning the mul instruction is slow!!! this is just an example this muliplyies .5 by 5 and stores it into d1

;d1 now hold 640 640/256=2.5

;if we wish to convert it to an integer we bitshift to the right by 8 since there are 8 fractional bits

lsr.w #8,d1 ;d1 now contains 2

Now if we want to round the number instead of truncating the fractional part when converting to integer we simply add 128 before bitshifting to the right

but if you wish to do fixed point with another fixed point you must for multiplication bitshift to the right by 8 to get a proper fixed point result.

Code:

move.w #64,d0;0.25

mulu.w #832,d0;multiply 3.25 by 0.25

;d0 now hold the value of 53,248 that is not right

lsr.l #8,d0 ; Must be lsr.l not lsr.w this does NOT convert to integer

;d0 now hold a proper 208 which is 0.8125 and 3.25*0.25 is also 0.8125

Now for division order maters 1/2 is not the same is 2/1 which but 1*2 and 2*1 are of course the same

If you look at http://68k.hax.com/DIVU

you will see the that the DIV instruction works like this

divu.w A,B

that means B/A

So if we want to divided .5 by 2 we would do this

Code:

move.w #2,d0

divu.w #128,d0

;64 is now stored in d0

But for fixed point/fixed point

we need to something like this

a = (b << 8) / c

so we need to muliply what we normally use to muliply the number (256) by it's self to get 65,536

So to divided .5 by .5 we would do

Code:

move.l #32768,d0

divu.w #128,d0

;256 is now in d0 which is one that is correct

If you have any questions feel free to post them

 

I will state that my question might be redundant, but what is the point of the post exactly? What does this help out? Is it just affiliated with Sonic's variable speed, or what?

 

In computer science, fixed point maths is the method of taking a memory space, and breaking it up into two sections, one section (the most significant section) will be the quotient, and the other section (the least significant section) will be the divisor, for example, d0 contains 00000000 (a 32-bit memory space (4 bytes)), this is one whole number, programmers could "pretend" that the left 16 bits of the register is the whole number (the quotient) while the right 16 bits of the register is the divisor (i.e. the fractions).


You basically end up turning d0's 00000000 into 0000.0000, thus giving it a decimal place, and with this method, you can give the illusion of moving say an object or a scanline, or virtually anything graphical/audial, in small fractions, for example, Sonic cannot move half a pixel each frame to the right, however, you can make it move at the speed of half a pixel, by increasing the quotient and divisor by 0000.8000 (0.8 being half of 1.0 in hexadecimal), then using ONLY the quotient as the position (keeping the divisor stored away somewhere), you can essentially cause a pattern of slow movement:

Code:

0000.0000

0000.8000

0001.0000

0001.8000

0002.0000

0002.8000

0003.0000

0003.8000

etc

You give Sonic's position ONLY the quotient, and his movement will become:

Code:

0000

0000

0001

0001

0002

0002

0003

0003

etc

The pixels can never be at 0001.8000, so this effectively rounds it down to 0001.0000, as long as you have the divisor preserved, and are ensuring that only the quotient is being read as the direct pixel position, you can cause all sorts of smooth illusional effects, for example, it is used in scrolling (deformation) quite a lot, GHZ's water is an example, each scanline needs to move at its own speed of smooth rate, therefore a divisor is needed.


One thing not to forget though, this is completely illusional, there is no actual quotient and no actual divisor, and the numbers are never in decimal, it is always binary, so it's all part of "perceptional art", this is why people can often become confused.


I do also feel that using decimal as an example here (although understandable to the common individual) will confuse the relationship between decimal and hexadecimal/binary, perhaps a few hexadecimal examples?

 

There are so many usages for non-integer math (decimals) they are everywhere in video games pretty much any thing that accelerates in a video game uses fixed or on new video games floating point math. The usage for fixed math on the genesis are almost unlimited there is so much math that needs decimals this is not just limited to the sega genesis alot of micocontrollers do not have an FPU so you need to use fixed point math just like on the Sega Genesis. Fixed point math is good for pixel manipulation because fixed point math does not have the rounding errors that floating point does and fixed point math uses less ram than a float another use for fixed point is in audio resampling and the list of fixed point usage goes on and on and on..... However in modern days people use float which is ok but there are rounding errors and on some processes a float based for loop will get stuck

Code:

float x;

for (x=0.0f;x==2.0f;x++;)

{

//do something

}

there is a chance that x will never equal 2.0 instead x=1.9999999(the 9 never ends)....


with fixed point math all processors will have the same result. This is due to different accuracy of the FPU built in the CPU.