# ### Site Tools

base:seriously_fast_multiplication

# Differences

This shows you the differences between two versions of the page.

 — base:seriously_fast_multiplication [2015-04-17 04:33] (current) Line 1: Line 1: + ====== 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 [[magazines:chacking16#d_graphics_for_the_masseslib3d_and_cool_world|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 + ; T2 = BBbb + ; >T1 * 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_hi * 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 + + + 