mult6.a

; mult6.a
; from eurorusty: https://everything2.com/user/eurorusty/writeups/Fast+6502+multiplication
;
; 8 bit x 8 bit unsigned multiply, 16 bit result
; Average cycles: 137.21
; 620 bytes


; multiplies var_a * var_b
; result stored in var_r and var_s
; code is compatible with http://skilldrick.github.io/easy6502/
var_a = $80
var_b = $81
var_m = $82
var_n = $83
var_r = $84
var_s = $85

* = $0200

; align tables to page boundary for speed
sqr_lo
    !byte 0, 1, 4, 9, 16, 25, 36, 49, 64, 81, 100, 121, 144, 169, 196, 225
    !byte 0, 33, 68, 105, 144, 185, 228, 17, 64, 113, 164, 217, 16, 73, 132, 193
    !byte 0, 65, 132, 201, 16, 89, 164, 241, 64, 145, 228, 57, 144, 233, 68, 161
    !byte 0, 97, 196, 41, 144, 249, 100, 209, 64, 177, 36, 153, 16, 137, 4, 129
    !byte 0, 129, 4, 137, 16, 153, 36, 177, 64, 209, 100, 249, 144, 41, 196, 97
    !byte 0, 161, 68, 233, 144, 57, 228, 145, 64, 241, 164, 89, 16, 201, 132, 65
    !byte 0, 193, 132, 73, 16, 217, 164, 113, 64, 17, 228, 185, 144, 105, 68, 33
    !byte 0, 225, 196, 169, 144, 121, 100, 81, 64, 49, 36, 25, 16, 9, 4, 1
    !byte 0, 1, 4, 9, 16, 25, 36, 49, 64, 81, 100, 121, 144, 169, 196, 225
    !byte 0, 33, 68, 105, 144, 185, 228, 17, 64, 113, 164, 217, 16, 73, 132, 193
    !byte 0, 65, 132, 201, 16, 89, 164, 241, 64, 145, 228, 57, 144, 233, 68, 161
    !byte 0, 97, 196, 41, 144, 249, 100, 209, 64, 177, 36, 153, 16, 137, 4, 129
    !byte 0, 129, 4, 137, 16, 153, 36, 177, 64, 209, 100, 249, 144, 41, 196, 97
    !byte 0, 161, 68, 233, 144, 57, 228, 145, 64, 241, 164, 89, 16, 201, 132, 65
    !byte 0, 193, 132, 73, 16, 217, 164, 113, 64, 17, 228, 185, 144, 105, 68, 33
    !byte 0, 225, 196, 169, 144, 121, 100, 81, 64, 49, 36, 25, 16, 9, 4, 1

sqr_hi
    !byte 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0
    !byte 1, 1, 1, 1, 1, 1, 1, 2, 2, 2, 2, 2, 3, 3, 3, 3
    !byte 4, 4, 4, 4, 5, 5, 5, 5, 6, 6, 6, 7, 7, 7, 8, 8
    !byte 9, 9, 9, 10, 10, 10, 11, 11, 12, 12, 13, 13, 14, 14, 15, 15
    !byte 16, 16, 17, 17, 18, 18, 19, 19, 20, 20, 21, 21, 22, 23, 23, 24
    !byte 25, 25, 26, 26, 27, 28, 28, 29, 30, 30, 31, 32, 33, 33, 34, 35
    !byte 36, 36, 37, 38, 39, 39, 40, 41, 42, 43, 43, 44, 45, 46, 47, 48
    !byte 49, 49, 50, 51, 52, 53, 54, 55, 56, 57, 58, 59, 60, 61, 62, 63
    !byte 64, 65, 66, 67, 68, 69, 70, 71, 72, 73, 74, 75, 76, 77, 78, 79
    !byte 81, 82, 83, 84, 85, 86, 87, 89, 90, 91, 92, 93, 95, 96, 97, 98
    !byte 100, 101, 102, 103, 105, 106, 107, 108, 110, 111, 112, 114, 115, 116, 118, 119
    !byte 121, 122, 123, 125, 126, 127, 129, 130, 132, 133, 135, 136, 138, 139, 141, 142
    !byte 144, 145, 147, 148, 150, 151, 153, 154, 156, 157, 159, 160, 162, 164, 165, 167
    !byte 169, 170, 172, 173, 175, 177, 178, 180, 182, 183, 185, 187, 189, 190, 192, 194
    !byte 196, 197, 199, 201, 203, 204, 206, 208, 210, 212, 213, 215, 217, 219, 221, 223
    !byte 225, 226, 228, 230, 232, 234, 236, 238, 240, 242, 244, 246, 248, 250, 252, 254

mult
    ;if a & b are odd, r = -1, else r = 0
    LDA var_a
    AND var_b
    AND #1
    BEQ _1
    LDA #255

_1
    STA var_r
    STA var_s

    ;m = a / 2
    LDA var_a
    LSR
    STA var_m
    BCC _2

    ;a is odd, r += b
    CLC
    LDA var_r
    ADC var_b
    STA var_r
    LDA var_s
    ADC #0
    STA var_s

_2
    ;n = b / 2
    LDA var_b
    LSR
    STA var_n
    BCC _3

    ;b is odd, r += a
    CLC
    LDA var_r
    ADC var_a
    STA var_r
    LDA var_s
    ADC #0
    STA var_s

_3
    ;normalize so that m >= n
    LDA var_m
    CMP var_n
    BCS _4

    ;n > m, swap m and n
    TAY
    LDA var_n
    STA var_m
    STY var_n

_4
    ;r += (m + n)^2
    CLC
    LDA var_m
    ADC var_n
    TAY
    LDA var_r
    ADC sqr_lo,Y
    STA var_r
    LDA var_s
    ADC sqr_hi,Y
    STA var_s

    ;r -= (m - n)^2
    SEC
    LDA var_m
    SBC var_n
    TAY
    LDA var_r
    SBC sqr_lo,Y
    STA var_r
    LDA var_s
    SBC sqr_hi,Y
    STA var_s

    ;done!
    RTS