Fixed Point Math
Volume Number: 10
Issue Number: 3
Column Tag: Under The Hood
Fixed Point Math For Speed Freaks 
Fast fixed math and derived graphics utility routines
By Alexei Lebedev
Note: Source code files accompanying article are located on MacTech CD-ROM orsource code disks.
About the author
Several of the author’s free programs, Kubik, Fractal Artist, Tower of Hanoi, as
well as some other programs and patches can be downloaded from CompuServe.
Author’s e-mail address is 70534,404@compuserve.com. Kubik simulates Rubik’s
cube, and Fractal Artist draws some fractals like Mandelbrot Set and Julia Sets. Both
Kubik and Fractal Artist (which were built for speed) make use of fixed point
arithmetic techniques described here.
In this article we will explore several aspects of Mac programming: fixed point
arithmetic in assembly, 3-d transformations, perspective and parallel projections,
backplane elimination, offscreen bitmaps, and animation. We’ll discuss details of a set
of utility routines, the complete source of which is available in the source files on disk
or the online services (see page 2 for details about the online services).
Fixed Point Format
Let’s first build a small library of functions to do fixed point arithmetic. There
are several reasons to do this instead of using built-in functions like FixMul and
FixDiv. The first and most important is speed - Toolbox functions are slow. Just for
comparison, our function for multiplying two Fixed numbers is 3 instructions long
and computations are done in registers, whereas FixMul in my LC’s ROM has 47
instructions, and accesses memory many times. [This reasoning changes when it comes
to math and the PowerPC. See the Powering Up series to learn more about the new
common wisdom. - Ed. stb] The second reason is that we get to choose the precision of
the numbers, because we can distribute bit usage between fractional and integer parts
of a Fixed number in any way we like. Thus, if we were calculating a Mandelbrot set,
we would probably choose 4 bits for the integer part, and 28 for the fraction. For
graphics, on the other hand, it makes more sense to split the bits evenly between
integer and fractional parts. This lets us use numbers as large as
32767+65535/65536, and fractions as small as 1/65536.
A Fixed number is simply a real number (float) multiplied by a scale in order to
get rid of the fractional part. We will use 32-bit fixed point numbers, with the
integer part in the higher word, and the fractional part in the lower word. So in our
case (f) is scaled by 216 = 65536.
Fixed Point Arithmetic
Fixed numbers can be added (and subtracted) just like long integers. Why? Let n
and m be the two numbers we want to add. Then their Fixed equivalents are nf and mf,
where is f is, of course, 65536. Adding nf and mf we get (n+m)f, which is n+m
expressed in Fixed notation. Let’s apply the same logic to other operations. With
multiplication it’s a bit different (no pun intended), because nf*mf = (n*m)f2 has the
wrong units. The correct result is (n*m)f. To get it, we simply divide the expression
above by f. Note that this is not necessary when a Fixed number is being multiplied by
an integer, because nf*m = (n*m)f. This important fact has been omitted in Inside Mac
Volume I. As a result, some programmers write lines like fixnum = FixMul(fixnum,
FixRatio(5, 1)), when all that is needed is fixnum *= 5 or something similar.
We will now implement multiplication in assembly. We will be using the
68020’s signed multiply instruction muls.l, which has syntax muls.l dx, dy:dz. This
multiplies a long word in dx by a long word in dz, splitting the 64-bit result between
dy and dz. Note that the registers can overlap, which means that to square a number,
you would write muls.l dx,dy:dx.
/* 1 */
asm {
muls.l d0, d1:d2
move.w d1, d2 ; join high and low words of the result
swap d2 ; reorder words for correct result
}
The last two instructions divide d1:d2 by 65536, effectively shifting them down