display | more...

Here is an fast unsigned 8-bit in / 16-bit out multiplication routine using 512 bytes of lookup in 116-119 cycles and 4 zero page registers.

It basically works like long multiplication with nibbles.

In:
a0 = first factor
a1 = second factor
Out:
r0 = product low
r1 = product high

a0 * a1 = { r0, r1 }

It is calculated in 4 stages:

A: { r1_l, r0_h } = a0_l * a1_h
B: { r1_l, r0_h } = a0_h * a1_l
C: { r0_h, r0_l } = a0_l * a1_l
D: { r1_h, r1_l } = a0_h * a1_l

r0_h means r0 high nibble, and r0_l means r0 low nibble.

This example runs in the skilldrick 6502 compiler.

define a0 $00
define a1 $01

define r0 $20
define r1 $21

jmp start

mul:
    ; --- A (21 cycles)
    ldx a0
    txa
    eor a1
    and #$f0
    eor a1
    tay
    lda table_mul, y
    sta r1
    ; --- B (47 cycles)
    txa
    eor a1
    and #$f
    eor a1
    tay
    lda table_mul, y
    clc
    adc r1
    tay
    lda table_flip, y
    tay
    and #$f
    bcc mul_1
    ; add carry to high nibble
    ora #$10
    clc
mul_1:
    sta r1
    tya
    and #$f0
    sta r0
    ; --- C (26 cycles)
    lda table_flip, x
    eor a1
    tax
    and #$f0
    eor a1
    tay
    lda table_mul, y
    adc r0
    sta r0
    ; --- D (19 cycles)
    txa
    and #$f
    eor a1
    tay
    lda table_mul, y
    adc r1
    sta r1
    rts ; mul(a,b)

start:
    lda #8
    sta a0
    lda #8
    sta a1
    jsr mul
    brk ; start()

table_mul:
dcb 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0
dcb 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15
dcb 0, 2, 4, 6, 8, 10, 12, 14, 16, 18, 20, 22, 24, 26, 28, 30
dcb 0, 3, 6, 9, 12, 15, 18, 21, 24, 27, 30, 33, 36, 39, 42, 45
dcb 0, 4, 8, 12, 16, 20, 24, 28, 32, 36, 40, 44, 48, 52, 56, 60
dcb 0, 5, 10, 15, 20, 25, 30, 35, 40, 45, 50, 55, 60, 65, 70, 75
dcb 0, 6, 12, 18, 24, 30, 36, 42, 48, 54, 60, 66, 72, 78, 84, 90
dcb 0, 7, 14, 21, 28, 35, 42, 49, 56, 63, 70, 77, 84, 91, 98, 105
dcb 0, 8, 16, 24, 32, 40, 48, 56, 64, 72, 80, 88, 96, 104, 112, 120
dcb 0, 9, 18, 27, 36, 45, 54, 63, 72, 81, 90, 99, 108, 117, 126, 135
dcb 0, 10, 20, 30, 40, 50, 60, 70, 80, 90, 100, 110, 120, 130, 140, 150
dcb 0, 11, 22, 33, 44, 55, 66, 77, 88, 99, 110, 121, 132, 143, 154, 165
dcb 0, 12, 24, 36, 48, 60, 72, 84, 96, 108, 120, 132, 144, 156, 168, 180
dcb 0, 13, 26, 39, 52, 65, 78, 91, 104, 117, 130, 143, 156, 169, 182, 195
dcb 0, 14, 28, 42, 56, 70, 84, 98, 112, 126, 140, 154, 168, 182, 196, 210
dcb 0, 15, 30, 45, 60, 75, 90, 105, 120, 135, 150, 165, 180, 195, 210, 225
table_flip:
dcb 0, 16, 32, 48, 64, 80, 96, 112, 128, 144, 160, 176, 192, 208, 224, 240
dcb 1, 17, 33, 49, 65, 81, 97, 113, 129, 145, 161, 177, 193, 209, 225, 241
dcb 2, 18, 34, 50, 66, 82, 98, 114, 130, 146, 162, 178, 194, 210, 226, 242
dcb 3, 19, 35, 51, 67, 83, 99, 115, 131, 147, 163, 179, 195, 211, 227, 243
dcb 4, 20, 36, 52, 68, 84, 100, 116, 132, 148, 164, 180, 196, 212, 228, 244
dcb 5, 21, 37, 53, 69, 85, 101, 117, 133, 149, 165, 181, 197, 213, 229, 245
dcb 6, 22, 38, 54, 70, 86, 102, 118, 134, 150, 166, 182, 198, 214, 230, 246
dcb 7, 23, 39, 55, 71, 87, 103, 119, 135, 151, 167, 183, 199, 215, 231, 247
dcb 8, 24, 40, 56, 72, 88, 104, 120, 136, 152, 168, 184, 200, 216, 232, 248
dcb 9, 25, 41, 57, 73, 89, 105, 121, 137, 153, 169, 185, 201, 217, 233, 249
dcb 10, 26, 42, 58, 74, 90, 106, 122, 138, 154, 170, 186, 202, 218, 234, 250
dcb 11, 27, 43, 59, 75, 91, 107, 123, 139, 155, 171, 187, 203, 219, 235, 251
dcb 12, 28, 44, 60, 76, 92, 108, 124, 140, 156, 172, 188, 204, 220, 236, 252
dcb 13, 29, 45, 61, 77, 93, 109, 125, 141, 157, 173, 189, 205, 221, 237, 253
dcb 14, 30, 46, 62, 78, 94, 110, 126, 142, 158, 174, 190, 206, 222, 238, 254
dcb 15, 31, 47, 63, 79, 95, 111, 127, 143, 159, 175, 191, 207, 223, 239, 255