Lookup Tables

The 6502 in a Commodore 64 or an Apple II cannot multiply. It can add, subtract and shift a byte one bit left or right, and everything else is built from those. Multiplying two bytes the schoolbook way, with shifts and adds, takes 144 cycles on average even in Damon Slye’s well-known fast routine of 1983, and a sine built from multiplications takes many times longer. A game that rotates a dozen points each frame cannot spend its time like that.

So programmers did the sums in advance. A lookup table holds the answer for every input a program will ask about, and a single indexed read fetches it: on the 6502, LDA table,X takes four cycles. The cost moves from time to memory, and the 1980s programmer’s question was always how much memory an answer was worth.

Commodore printed a lookup table in the C64’s own manual. Appendix E of the Programmer’s Reference Guide lists, for eight octaves of notes, “the values to be POKEd into the HI FREQ and LOW FREQ registers of the sound chip”: 268 for the lowest C, split into a high byte of 1 and a low byte of 12. Music routines kept a table like it, indexed by note number. Commodore’s figures were worked out for the American machine’s clock; on a European PAL C64, whose clock runs about 4% slower, the same values play a little over half a semitone flat, so programmers there needed a PAL table of their own.

Fast facts

• The idea: compute once, store the results, and replace a calculation with an indexed read.
• Cost on the 6502: LDA table,X takes 4 cycles, plus 1 if the index carries the address into the next 256-byte page.
• Typical tables: sines and cosines, squares for multiplication, note frequencies, the start address of each screen row, bytes with their bits reversed.
• Price: memory. A sine table of 256 angles is 256 bytes. The quarter-square multiply below needs 2K. A table of every product of two bytes would need 128K, twice the C64’s whole memory.

A sine table

The simplest useful table divides the circle into 256 steps, so that an angle fits in one byte and wraps round by itself when it overflows. Each entry holds sin of that angle, scaled and shifted to fit a byte. This version stores round((sin + 1) × 127), so the wave runs from 0 to 254 with 127 in the middle. A program that wants signed values can store them in two’s complement instead, as Judd and Taylor’s 3D routines did.

The assembler can generate the table itself (ACME syntax):

        !align 255, 0           ; start the table on a page boundary
sine    !for i, 0, 255 { !byte int(127.5 + 127 * sin(float(i) * 2 * 3.14159265 / 256)) }

The first entries come out as 127, 130, 133, 136, 139, 143, 146, 149, and reading one costs a single instruction:

        lda sine,x              ; A = sine of the angle in X: 4 cycles

Cosine needs no table of its own: it is the same wave a quarter of a circle later, so cos(a) is sine at a + 64.

Multiplying with squares

A table of every product of two bytes would need 65,536 entries of two bytes each. The quarter-square method needs far less. It rests on an identity:

a × b = (a + b)² / 4 − (a − b)² / 4

Write f(n) for n² / 4, rounded down. Because a + b and a − b are always both odd or both even, the rounding cancels, and a × b = f(a + b) − f(a − b) exactly. A table of f for 0 to 510 turns a multiplication into two lookups and a subtraction. Stephen Judd’s 1998 C=Hacking article on 3D graphics called it “the fast multiply”, and noticed that by letting the processor’s indexed addressing do the addition, “we let the CPU add A and Y together”.

The routine below multiplies A by X. It writes A into the low byte of its own lookup addresses (self-modifying code), so that sqr_lo,X reads entry A + X. For the difference it uses a second copy of the table, shifted by 255, and writes the complement of A, so that neg_lo,X reads entry X − A + 255, which holds f(X − A).

; f(n) = n*n/4, rounded down; neg holds the same values shifted by 255
        !align 255, 0
sqr_lo  !for i, 0, 511 { !byte <((i * i) >> 2) }
sqr_hi  !for i, 0, 511 { !byte >((i * i) >> 2) }
neg_lo  !for i, 0, 511 { !byte <(((i - 255) * (i - 255)) >> 2) }
neg_hi  !for i, 0, 511 { !byte >(((i - 255) * (i - 255)) >> 2) }

prod    = $fd                   ; two zero-page bytes for the result

; Multiply A by X (both 0-255). The 16-bit product goes to prod, prod+1.
mul8    sta sm1+1               ; aim the first pair of lookups at f(X + A)
        sta sm3+1
        eor #$ff                ; and the second pair at f(X - A),
        sta sm2+1               ; using the tables shifted by 255
        sta sm4+1
        sec
sm1     lda sqr_lo,x
sm2     sbc neg_lo,x
        sta prod
sm3     lda sqr_hi,x
sm4     sbc neg_hi,x
        sta prod+1
        rts

The tables start on page boundaries because the routine replaces only the low byte of each address. The four tables take 2K, and the routine runs in 48 to 52 cycles including its RTS, about a third of the 144 of Slye’s shift-and-add. The same tables build bigger multiplications: Repose’s 16-by-16-bit routine on Codebase64, which uses them, takes about 199 cycles.

Tables in place of address arithmetic

Screen memory is another place where the same sum is done over and over. The C64’s text screen starts at $0400 and each row is 40 bytes long, so finding a row means multiplying by 40. Two small tables, one for the low byte of each row’s address and one for the high byte, replace the multiplication:

ptr     = $fb                   ; two zero-page bytes for the pointer

row_lo  !for r, 0, 24 { !byte <($0400 + r * 40) }
row_hi  !for r, 0, 24 { !byte >($0400 + r * 40) }

; Put the screen code in A at column Y of row X.
plot    pha
        lda row_lo,x
        sta ptr
        lda row_hi,x
        sta ptr+1
        pla
        sta (ptr),y
        rts

Splitting a table of 16-bit values into two tables of bytes is a habit of 6502 code, because the processor’s index registers count in bytes. Richard Mansfield’s The Second Book of Machine Language (1984) used the same arrangement in his assembler’s tables: with tables that run “parallel” to one another, one index register can “quickly pull out the values in any table which is parallel to the primary lookup table”.

On the ZX Spectrum the need is greater. Its screen does not store pixel lines in order: the bitmap fills the top third of the screen first, then the middle, then the bottom, and within each third the lines are interleaved, so the address of the line below is not a fixed distance away. A table of 192 line addresses, two bytes each, removes the bit-shuffling. The Bitmap Addressing pattern shows both ways of doing it.

Tables in games

Tables saved memory as well as time. Mike Lamb, writing about his Spectrum version of Renegade for Sinclair User in November 1987, explained that he stored only the right-facing frames of his characters. “When a left facing graphic is required, it can be generated from the same data using a look-up table in which every number from 0-255 has its bit-reflection stored. This cuts the memory required for graphics in half.”

The demo scene used tables everywhere, and wrote about them. Stephen Judd and George Taylor’s 1994 C=Hacking article on 3D graphics asks “how do we take the sine of a number and make it fast? The answer of course is to use a table.” They generated theirs with a BASIC program, stored the values already scaled and halved so that the rotation did not have to keep dividing by two, and replaced the division in perspective projection with a table indexed by depth: “As long as we’re using a table, why not incorporate the d into it?” Pasi Ojala’s article on stretched sprites, written in 1991 and published in C=Hacking in 1993, prints a routine from the demo Megademo92 whose tables are marked “(LSB of the address must be 0)”, that is, page-aligned. Not every sine came from a sine. The Codebase64 programmer White Flame records “a long-standing tradition in games & demos that sine waves can be approximated by parabolas”, a little boxier and about 6% out, “but generally work for doing quick and dirty trig”.

Choosing a table

See also

• Fixed-Point Math
• Self-Modifying Code
• 6502
• Z80
• Sprite Multiplexing