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