Fixed-Point Fixation

Learn or Teach General Knowledge Related to Coding or Hacking

Moderators: g3nuin3, SpeedWing, WhiteHat, mezzo

Fixed-Point Fixation

Postby L. Spiro » Mon Oct 26, 2009 8:26 am

Every played a game where all of the integer values were multiplied by some constant number in the game?
For example, some Flash games multiply their in-house numbers by 8 internally. So if the value you see on your screen is 100 (HP or so), the value in the game RAM is actually 800, and you would have to search for this number.

What kind of madness is this?? Is this meant to confuse us? Is this some kind of anti-hack?


Welcome to the world of fixed-point math.


Forms of Points

Before explaining the details of fixed-point, you should have a global scope of the types of points there are. Luckily there are only 3.
#1: Integer. What you see is what you get. If you see a 3 on your screen, you search for 3 using MHS.
There is no decimal point here, and only whole numbers can be expressed.
1, 800, 16000, etc., are examples of integer numbers.


#2: Floating-point. You have all worked with these. Floating-points have decimal points, and the decimal moves up and down the number as it grows and shrinks in size.
For example:
123456789.1
1.234567891 (decimal has “floated” to the front)
Think of it as an integer value (1234567891) with a decimal point thrown in. Since the point can move around within the number, it is a “floating”-point number.

#3: Fixed-point. Some processors, especially old ones and embedded (ones in mobile devices) ones, have little or no support for floating-point values. Nintendo DS, for example, has support, but it is extremely slow. So slow that using only about 500-1,000 floating-point multiplies per frame is enough to slow down the frame rate visibly.
Fixed-point values simply use integer values in such a way that a fractional part is created.


The Idea

As a basic example that is easy to understand, what if you had a health bar that goes from 0 to 1 but you have no fixed-point values available.
If you use DWORD, INT, SHORT, BYTE, etc., then there are only 2 values you can use for the health bar: 0 and 1.
For your game to work properly, you need to be able to have 0.5 health, 0.25 health, etc.

Then you realize that you can scale your integer value up to raise its “detail” or precision over a certain range.
If you need 100 units from 0 to 1, you can simply keep an integer that ranges from 0 to 100. Your health bar still reports a range from 0 to 1. How?
Since you scaled up by 100 to store the number, you need to scale back down by 100 to print the number.
000 / 100 = 0
100 / 100 = 1
050 / 100 = 0.5

It becomes easy to see that scaling your internal number up by 100 has given you 100 units of precision from 0 to 1.
This same sentence applies to all scales.
Think back to when you had a regular integer from 0 to 1 (without scaling). That is the same thing as scaling your internal number up by 1, giving you 1 unit of precision from 0 to 1 (0 = 0, 1 = 1).
Scaling your number up by 2 gives you 2 units of precision from 0 to 1 (0 = 0, 1 = 0.5, 2 = 1).
Scaling your number up by 4 gives you 4 units of precision from 0 to 1 (0 = 0, 1 = 0.25, 2 = 0.5, 3 = 0.75, 4 = 1).
Scaling your number up by 50 gives you 50 units of precision from 0 to 1.

Ultimately, you (and the games you hack) could decide on any scale for the fixed-point numbers. But once you decide on it, the decimal number moves. That is, if you decide to scale your numbers up by 100, you always scale up and down by the same amount as you convert to and from your internal number to the printed number. This is why it is called fixed-point. The decimal point is fixed in place.


The Advanced

These numbers are meant to be used for math. Math needs to be as fast as possible.
Consider this example of multiplying 2 fixed-point values together. Here, the decimal is fixed at 2 digits, giving us 100 units from 0 to 100. This is the same as scaling by 100.

The real numbers I want to multiply are 1 and 1. The result should be 1.
To get my numbers into fixed-point I multiple by 100. So the actual numbers I have in RAM are 100 and 100. The imaginary decimal point would make the numbers look like 1.00 (decimal fixed at 2 digits to its right).
First let us see what happens when multiplying the actual numbers I have in RAM.
100 * 100 = 10000.
Let’s do the same thing but with the imaginary decimals shown.
1.00 * 1.00 = 100.00 (Remember, 1.00 here is not the actual number 1. It is 100 (the number we use internally) with the decimal drawn in where we imagined it to be.)
Let’s do the same thing, but with the real numbers we were using.
1 * 1 = 1

Something seems wrong here. The result of 1 * 1 should be the same number.
We actually got a number 100 times too large!
Naturally, 100 * 100 is 10000, but we wanted 100.
The problem is that multiplying fixed-point numbers gives you the result scaled up by the fixed-point.
To get the final number we have to scale it back down. 10000 / 100 = 100. Thus:
(100 * 100) / 100 = 100.
(1.00 * 1.00) / 1.00 = 1.00.
(1 * 1) / 1 = 1.

Using numbers that are not all the same, but using a 100-unit scaling as before:
2 * 7 = 14 (No scale.)
(2 * 7) / 1 = 14 (Scale = 1.)
(200 * 700) / 100 = 1400 (Scale = 100.)



Now you can see that a simple multiplication operation actually requires both a multiply and a divide.
Divides are extremely slow, making this not only twice as slow as a single multiply, but more like 5 or 6 times, maybe more depending on the processor.


So what should we do?
If you recall, shift operators >> and << simply move the bits left and right, which multiplies or divides a number by a power of 2.
For example, (1 << 1) multiples by 2 (results is 2).
1 << 1 = 1 * 2
1 << 2 = 1 * 4
1 << 3 = 1 * 8
1 << 4 = 1 * 16
1 << 5 = 1 * 32
1 << 6 = 1 * 64
1 << 7 = 1 * 128

Etc.


<< is equal to multiplication whereas >> is equal to division. Except that these operations are much much faster than either * or /.
And remember, your numeric scale can be any number you want. It does not have to be 100. It could be 101. It could be 548. Whatever. All scales give you that many numbers between 0 and 1.


What You See in Games

Games are always concerned about speed.
Therefore you will never see a fixed-point value in a game that is not a scale of a power of 2. Games use << and >> to convert/scale their numbers because it is many times faster than * and /.

What you see in Flash games is not “multiply by 8”. It is actually “shift left by 3”.

Fixed-point values are expressed as WHOLE.FRACTION in terms of bits. That is, in Flash, a 4-byte integer with this shift-by-3 scheme would be represented as 29.3. There are 29 bits to the left of the decimal and 3 bits to the right.

Other common fixed-point types are:
20.12 (Nintendo DS.)
16.16 (OpenGL ES.)
24.8 (General.)


In Conclusion

From now on, when you encounter fixed-point values in games, you will know how to find them, how to understand them, how to do math with them, how express them to others, and how to derive them (that is, not through multiplication, but through shifting).

From now on, you no longer need to say that Flash games multiply by 8. You can proudly hold your enlightened head high as you shift left by 3.


L. Spiro
Our songs remind you of songs you’ve never heard.
User avatar
L. Spiro
L. Spiro
 
Posts: 3129
Joined: Mon Jul 17, 2006 10:14 pm
Location: Tokyo, Japan

Postby trialusert » Mon Oct 26, 2009 9:18 am

Joey had 10 apples. 2 of them were given to his brother. The rest shifted left by 3.

How many apples does Joey have now?

Very interesting and knowledgeable article. You made it fun to learn!
User avatar
trialusert
NULL
 
Posts: 155
Joined: Tue May 20, 2008 6:19 pm

Postby CoMPMStR » Mon Oct 26, 2009 1:32 pm

trialusert wrote:Joey had 10 apples. 2 of them were given to his brother. The rest shifted left by 3.

How many apples does Joey have now?


(10 - 2) << 3 = 64 :P
Image

______________________________________________________
My Utilities:
CT <-> LSSAVE Converter
LSS Visual Dialog Designer
.NET Trainer Helper Library

~Whether you think you can or you think you can't, you're right.

L. Spiro wrote:In my left hand is a red pill. If you take it I will show you the truth. I lost my right hand in the war, so I’m afraid you’re stuck with the red pill.
User avatar
CoMPMStR
(P)ot (I)n (M)y (P)ipe
 
Posts: 451
Joined: Thu Mar 06, 2008 7:50 am
Location: Best Place


Return to Knowledge Base

Who is online

Users browsing this forum: No registered users and 0 guests