Fixed-Point Maths

The processors in 8-bit computers and consoles could add, subtract and shift whole numbers, and that was all. A sprite that should move one and a half pixels a frame, a ball slowing under friction or a cube turning in 3D all need fractions. Fixed-point arithmetic supplies them without any new instructions: the program agrees where the binary point sits inside an ordinary integer and keeps to it. The processor never knows. It adds the bytes as it always does, and the fraction comes along for free.

The idea

Take a 16-bit number and treat the high byte as the whole part and the low byte as 256ths. Gunnar ‘Krill’ Ruthenberg put it plainly in GO64! in 2000: “what if we interprete the high byte as a number to the left- and the low byte as number to the right of a decimal point? Then we have a fixed point number with a precision of 1/256.”

8.8 format:   WWWWWWWW . FFFFFFFF
              whole      fraction (n/256)

$0180  =  1 + $80/256  =  1.5
$3200  =  50.0

The two numbers either side of the dot name the format: 8.8 has eight whole bits and eight fraction bits. Other splits suit other jobs.

A signed value in two’s complement halves the positive range and adds the same span below zero. In 8.8, -1.5 is $FE80: the high byte $FE is -2, and $80 adds back a half.

Adding is free

Addition and subtraction need nothing new. This routine moves a position by a velocity of 1.5 pixels a frame, and uses only the whole part for the screen:

; Velocity 1.5 = $0180, position starts at 50.0 = $3200
velocity_hi:  .byte $01
velocity_lo:  .byte $80
position_hi:  .byte $32
position_lo:  .byte $00

update_position:
    clc
    lda position_lo
    adc velocity_lo     ; fractions first; any carry...
    sta position_lo
    lda position_hi
    adc velocity_hi     ; ...goes into the whole part
    sta position_hi
    sta sprite_x        ; the whole part is the screen position
    rts

Two calls take the position from 50.0 to 51.5 to 53.0, so the sprite moves one pixel, then two, then one: an average of 1.5. Gravity is the same idea one level up. Add a small constant such as $0040 (a quarter of a pixel) to the velocity each frame, then add the velocity to the position, and an object falls faster and faster in a smooth curve.

Krill’s own example was timing rather than movement. An animation should play at 45 frames a second on a 60 Hz NTSC machine. Adding $0100 a frame would step one image per refresh, 60 a second; $0080 would give 30. So he added $00C0. The counter runs $00C0, $0180, $0240, $0300, and its high byte, the image number, “becomes $00, $00, $01, $02, $03, $03, $04 and so on. The speed of the animation is thus set to 45 FPS.”

Shifts multiply and divide by two

Shifting the whole 16-bit value one place doubles or halves it, fraction and all, as long as the bit that crosses the byte boundary is carried through:

; double an unsigned 8.8 value
    asl pos_lo
    rol pos_hi

; halve an unsigned 8.8 value
    lsr pos_hi
    ror pos_lo

For a signed value the halving has to keep the sign. LSR shifts a zero into the top bit, which turns a negative number into a large positive one. Krill’s first article shows the fix: CMP #$80 copies the sign bit into the carry, and a rotate puts it back.

; halve a signed 8.8 value: -1.5 ($FE80) becomes -0.75 ($FF40)
    lda pos_hi
    cmp #$80        ; carry = sign bit
    ror pos_hi      ; sign goes back in at the top
    ror pos_lo

Multiplying

Multiplying two fixed-point numbers multiplies their scale factors too. Two 8.8 values make a 16.16 product, and the middle 16 bits are the 8.8 answer. The 6502 has no multiply instruction, so the classic answer is shift-and-add: one step per bit of the multiplier.

; 8 x 8 -> 16 unsigned multiply
; in:  f1, f2 (zero page)
; out: A = high byte of the product, f1 = low byte
mul8:
    lda #0
    ldx #8
    lsr f1          ; first multiplier bit into carry
@loop:
    bcc @noadd
    clc
    adc f2          ; add the multiplicand if the bit was 1
@noadd:
    ror a           ; shift the product right; the next
    ror f1          ; multiplier bit drops into carry
    dex
    bne @loop
    rts

Read with a fixed-point eye, this routine scales by a fraction. Put a whole value in f1 and a fraction n/256 in f2, and the high byte of the product is the scaled whole value: 200 times $C0 (0.75) leaves 150 in A. That is how a game can apply friction to a speed, or squash a coordinate for perspective, without a divide. Where speed matters more than memory, a table of squares replaces the loop; see lookup tables.

Choosing the scale

Stephen Judd and George Taylor’s 1994 article on 3D graphics in C= Hacking shows the choice being made. They wanted speed, so they chose 8-bit signed numbers, and sines and cosines “range between negative one and one”:

To represent these floating point numbers as 8-bit signed integers the idea will be to multiply all floating point numbers by a fixed amount. That is, instead of dealing with the number 0.2, we use the number 64*0.2 = 12.8 = 13, and divide the end result by 64.

The factor had to be a power of two to keep the final division to shifts: “128 is too big. 32 doesn’t give us much accuracy.” They also met the trap every fixed-point programmer meets. With a = b = 64, both inside the range, “(a+b)/2 will not give the same answer as a/2 + b/2”. The sum, 128, does not fit in a signed byte, so the order of operations decides whether the answer is right.

Sine values usually come from a table rather than a calculation. One common layout stores (sin + 1) × 127, which turns the range -1 to 1 into the unsigned bytes 0 to 254, with 127 standing for zero:

; 256 entries, one per 1/256 of a turn
; entry = round((sin(angle * 2π / 256) + 1) * 127)
sine_table:
    .byte 127, 130, 133, 136, 139, 143, 146, 149   ; angles 0-7
    .byte 152, 155, 158, 161, 164, 167, 170, 173   ; angles 8-15
    ; ... 240 more

Why not floating point?

Some of these machines had floating point, in software. Commodore BASIC keeps two floating-point accumulators in the C64’s zero page, at $61-$66 and $69-$6E, and machine code can call the same ROM routines. Demo coders did not. Krill’s articles, republished on the Codebase64 wiki, give the reason: the 6510’s “command set … supplies all powerful operations - addition, subtraction, shift and rotate, and that’s it”, the ROM’s floating-point routines “are far from what we call fast and optimized”, and “fixed point arithmetic routines are fast and accurate enough”, with the programmer choosing “the amount of fraction bits” and the range.

Machine by machine

Commodore 64 and NES (6502 family). There are no 16-bit registers, so fixed-point values live in memory, and the cheapest memory is zero page. MOS’s programming manual introduced zero-page addressing for exactly this: it saves a byte and a cycle on every access, “particularly when dealing with working registers and intermediate values”. LDA from zero page takes 3 cycles against 4 for an absolute address, and an 8.8 update touches four bytes.

ZX Spectrum (Z80). The Z80’s register pairs make 8.8 values natural. ADD HL,DE adds two of them in 11 T-states. The index registers are convenient for keeping an object’s fields together, but costly: LD A,(IX+d) takes 19 T-states against 7 for LD A,(HL).

Amiga (68000). Every data register is 32 bits wide, so a 16.16 value fits in one, and ADD.L between two registers takes 8 clock periods. The 68000 also multiplies: MULS and MULU take two 16-bit values to a 32-bit product in at most 70 clock periods, so an 8.8 by 8.8 product needs one instruction and a shift. That is slow next to an add, but it is far faster than a software loop.

See also

• Lookup tables
• Game loop
• Sprite animation
• 6502, Z80 and 68000