User Tools

Site Tools


base:seriously_fast_multiplication

Differences

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

Link to this comparison view

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 ​                                            
 +                ; <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>​
 +
  
base/seriously_fast_multiplication.txt ยท Last modified: 2015-04-17 04:33 (external edit)