# ### 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: + + <​code>​ + ; 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 + + ​ + 