base:seriously_fast_multiplication
Seriously fast multiplication (8-bit and 16-bit)
By Jackasser
Without further explanation here's the code for really fast multiplications. They require 2k of tables which can be generated using table_generator_routine_for_fast_8_bit_mul_table. The article from C=Hacking 16 which is mentioned in the source is available here.
Here are four routines, signed/unsigned 8/16-bit multiplication with 16/32-bit result:
; Description: Unsigned 8-bit multiplication with unsigned 16-bit result.
;
; Input: 8-bit unsigned value in T1
; 8-bit unsigned value in T2
; Carry=0: Re-use T1 from previous multiplication (faster)
; Carry=1: Set T1 (slower)
;
; Output: 16-bit unsigned value in PRODUCT
;
; Clobbered: PRODUCT, X, A, C
;
; Allocation setup: T1,T2 and PRODUCT preferably on Zero-page.
; square1_lo, square1_hi, square2_lo, square2_hi must be
; page aligned. Each table are 512 bytes. Total 2kb.
;
; Table generation: I:0..511
; square1_lo = <((I*I)/4)
; square1_hi = >((I*I)/4)
; square2_lo = <(((I-255)*(I-255))/4)
; square2_hi = >(((I-255)*(I-255))/4)
.proc multiply_8bit_unsigned
bcc :+
lda T1
sta sm1+1
sta sm3+1
eor #$ff
sta sm2+1
sta sm4+1
:
ldx T2
sec
sm1: lda square1_lo,x
sm2: sbc square2_lo,x
sta PRODUCT+0
sm3: lda square1_hi,x
sm4: sbc square2_hi,x
sta PRODUCT+1
rts
.endproc
; Description: Signed 8-bit multiplication with signed 16-bit result.
;
; Input: 8-bit signed value in T1
; 8-bit signed value in T2
; Carry=0: Re-use T1 from previous multiplication (faster)
; Carry=1: Set T1 (slower)
;
; Output: 16-bit signed value in PRODUCT
;
; Clobbered: PRODUCT, X, A, C
.proc multiply_8bit_signed
jsr multiply_8bit_unsigned
; Apply sign (See C=Hacking16 for details).
lda T1
bpl :+
sec
lda PRODUCT+1
sbc T2
sta PRODUCT+1
:
lda T2
bpl :+
sec
lda PRODUCT+1
sbc T1
sta PRODUCT+1
:
rts
.endproc
; Description: Unsigned 16-bit multiplication with unsigned 32-bit result.
;
; Input: 16-bit unsigned value in T1
; 16-bit unsigned value in T2
; Carry=0: Re-use T1 from previous multiplication (faster)
; Carry=1: Set T1 (slower)
;
; Output: 32-bit unsigned value in PRODUCT
;
; Clobbered: PRODUCT, X, A, C
;
; Allocation setup: T1,T2 and PRODUCT preferably on Zero-page.
; square1_lo, square1_hi, square2_lo, square2_hi must be
; page aligned. Each table are 512 bytes. Total 2kb.
;
; Table generation: I:0..511
; square1_lo = <((I*I)/4)
; square1_hi = >((I*I)/4)
; square2_lo = <(((I-255)*(I-255))/4)
; square2_hi = >(((I-255)*(I-255))/4)
.proc multiply_16bit_unsigned
; <T1 * <T2 = AAaa
; <T1 * >T2 = BBbb
; >T1 * <T2 = CCcc
; >T1 * >T2 = DDdd
;
; AAaa
; BBbb
; CCcc
; + DDdd
; ----------
; PRODUCT!
; Setup T1 if changed
bcc :+
lda T1+0
sta sm1a+1
sta sm3a+1
sta sm5a+1
sta sm7a+1
eor #$ff
sta sm2a+1
sta sm4a+1
sta sm6a+1
sta sm8a+1
lda T1+1
sta sm1b+1
sta sm3b+1
sta sm5b+1
sta sm7b+1
eor #$ff
sta sm2b+1
sta sm4b+1
sta sm6b+1
sta sm8b+1
:
; Perform <T1 * <T2 = AAaa
ldx T2+0
sec
sm1a: lda square1_lo,x
sm2a: sbc square2_lo,x
sta PRODUCT+0
sm3a: lda square1_hi,x
sm4a: sbc square2_hi,x
sta _AA+1
; Perform >T1_hi * <T2 = CCcc
sec
sm1b: lda square1_lo,x
sm2b: sbc square2_lo,x
sta _cc+1
sm3b: lda square1_hi,x
sm4b: sbc square2_hi,x
sta _CC+1
; Perform <T1 * >T2 = BBbb
ldx T2+1
sec
sm5a: lda square1_lo,x
sm6a: sbc square2_lo,x
sta _bb+1
sm7a: lda square1_hi,x
sm8a: sbc square2_hi,x
sta _BB+1
; Perform >T1 * >T2 = DDdd
sec
sm5b: lda square1_lo,x
sm6b: sbc square2_lo,x
sta _dd+1
sm7b: lda square1_hi,x
sm8b: sbc square2_hi,x
sta PRODUCT+3
; Add the separate multiplications together
clc
_AA: lda #0
_bb: adc #0
sta PRODUCT+1
_BB: lda #0
_CC: adc #0
sta PRODUCT+2
bcc :+
inc PRODUCT+3
clc
:
_cc: lda #0
adc PRODUCT+1
sta PRODUCT+1
_dd: lda #0
adc PRODUCT+2
sta PRODUCT+2
bcc :+
inc PRODUCT+3
:
rts
.endproc
; Description: Signed 16-bit multiplication with signed 32-bit result.
;
; Input: 16-bit signed value in T1
; 16-bit signed value in T2
; Carry=0: Re-use T1 from previous multiplication (faster)
; Carry=1: Set T1 (slower)
;
; Output: 32-bit signed value in PRODUCT
;
; Clobbered: PRODUCT, X, A, C
.proc multiply_16bit_signed
jsr multiply_16bit_unsigned
; Apply sign (See C=Hacking16 for details).
lda T1+1
bpl :+
sec
lda PRODUCT+2
sbc T2+0
sta PRODUCT+2
lda PRODUCT+3
sbc T2+1
sta PRODUCT+3
:
lda T2+1
bpl :+
sec
lda PRODUCT+2
sbc T1+0
sta PRODUCT+2
lda PRODUCT+3
sbc T1+1
sta PRODUCT+3
:
rts
.endproc
base/seriously_fast_multiplication.txt · Last modified: 2015-04-17 04:33 by 127.0.0.1