no way to compare when less than two revisions

Differences

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

@@ 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
+                ; <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
+</code>