ÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄ


                       ÄÄÄ FPU: magic numbers ÄÄÄ

                              a small guide
                                   by
                             franky@scene.at
 
                done in the week of my written a-level exams
                        improved, english version
                          published in hugi #16


  : introduction :
  -------------------

        what are magic numbers ?

        magic numbers are special floating point numbers which
        can be added by FPU to another floating point number so
        that the result can be treated like an integer.

        you can think of it like a weird version for "frndint".

        advantage is, by only one "fadd" you can convert your
        number into integer and at the same time multiply it
        by 2^+/-n like "shl" and "shr"/"sar" would do for CPU.

        additionally, you can also add a constant to your
        FPU number. thus by only single "fadd" you can
        multiply, add *and* convert to integer.

        another advantage is, by using "fadd" and "fst"
        instead of "fist" your code might be more pairable,
        but this depends pretty much on the imlpementation.

        unfortunately, there is also a big disadvantage:
        magic numbers only work for converting/multiplying
	positive floating point values.


  : basics about floating point numbers :
  ------------------------------------------

        before you can understand how magic numbers work, you need
        to know how the FPU stores its values and how it performs
        calculations.

        the x86 FPU stores its numbers using sign, exponent and fraction.

        to get the value, you have to do

                value = -1^sign * 1.fraction * 2^exponent

        sign is one single bit used as an exponent for -1.
	as the informed reader knows:	-1^0 =  1  and
				        -1^1 = -1

        fraction has to be prefixed with a binary 1, since the
        FPU automatically changes fraction & exponent using
        the following "algorithm":

        it takes the fraction, shifts it left until it finds a one.
        a one. - meanwhile, the exponent is adjusted so that the
        actual value still stays the same.

        after the first binary 1 is found, it is deleted,
        and the result is then a valid "normalized" value.

        this is done because this way the FPU always uses the
        best matching accuracy for storing a floating point
        number. - by killing the first 1 of the fraction
        it gets an extra bit of accuracy "for free".

        this way you couldn't store a 0.0 for example,
        but therefore the FPU has a reserved exponent value.
        the same is done for storing -inf and +inf.

        the exponent itself is a signed number. this is
        needed because a positive exponent will be used to
        define very large positive values, and a small
        exponent will define very small values.


  : what the FPU "fadd" does :
  -------------------------------

        if you want to understand why and how magic numbers work,
        you need to understand what the FPU "fadd" performs,
        because the trick lies within this process.

        if you perform a "fadd", the FPU looks for the number
        with the bigger exponent. this is needed because for
        adding two exponential numbers, you first have to
        equal both exponents. this is also called "aligning".

                                .------ equalizes exponents
                                |
                                v
          x + y  =  (S_x * 2^(E_x-E_y) + S_y) * 2^(E_y)    ( E_x <= E_y )
          x - y  =  (S_x * 2^(E_x-E_y) - S_y) * 2^(E_y)    ( E_x <= E_y )
                    \_______________________/
                         add or subtract

        and this is exactly the trick that magic numbers use.

        if you choose a number whose exponent is always bigger,
        the result will always be aligned to that big exponent.

        and if the number is big enough and also has a proper
        exponent, you can "shift" fraction around as you want.

        you also have to care about the "normalisation" that
        the FPU does, so beside the big exponent we'll need
        a proper fraction so the FPU doesn't do anything
        unexpected.

        we do not have to care about the 1 which "got lost"
        during the process of normalisation because the FPU
        has - of course - to add it while changing the
        exponent of the number we're adding to.


  : choosing proper magic numbers :
  ------------------------------------

	something we have to care about when creating
	magic numbers is, that there are different kinds
	of floating point numbers which might be of
	potential use for magic numbers:

		name:		size:
	----------------------------------------------
		float	-	dword ( 4 bytes )
		double	-	qword ( 8 bytes )

	if you only want to convert and maybe multiply
	by 2^+/-n, the type "float" is enough. - if you
	also want to add a constant, you'll need "double".

	here're the number of bits for floating points,
	that are used in "float" and "double":

	float:
	----------------------------------------------
          sign    :     bit       31
          exponent:     bits 23 - 30
          fraction:     bits  0 - 22

        double:
        ----------------------------------------------
          sign    :     bit       63
          exponent:     bits 52 - 62
          fraction:     bits  0 - 51


ÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄ