Maths: Multiply8x8

       Name: Multiply8x8                                             [Show more]
       Type: Subroutine
   Category: Maths
    Summary: Multiply two unsigned 8-bit numbers
  Deep dive: Times tables and nibble arithmetic
    Context: See this subroutine in context in the source code
 References: This subroutine is called as follows:
             * DivideScaled calls Multiply8x8
             * Multiply16x16 calls Multiply8x8
             * Multiply8x16 calls Multiply8x8
             * Sine16Bit calls Multiply8x8


 This routine multiplies two unsigned 8-bit numbers, as follows:

   (A V) = X * Y

 It uses the following algorithm:

   X * Y = %XXXXxxxx * %YYYYyyyy

         = (%XXXX0000 + %0000xxxx) * (%YYYY0000 + %0000yyyy)

         = (%XXXX0000 * %YYYY0000) + (%XXXX0000 * %0000yyyy)
                                   + (%0000xxxx * %YYYY0000)
                                   + (%0000xxxx * %0000yyyy)

         = (%YYYY * %XXXX) << 8    + (%XXXX * %yyyy << 4)
                                   + (%xxxx * %YYYY << 4)
                                   + (%xxxx * %yyyy)

         = (%YYYY * %XXXX) << 8    + ((%XXXX * %yyyy) + (%xxxx * %YYYY)) << 4
                                   + (%xxxx * %yyyy)


 Arguments:

   X                    An unsigned 8-bit value (0 to 255)

   Y                    An unsigned 8-bit value (0 to 255)


 Returns:

   (A V)                X * Y


.Multiply8x8

                        \ We start with X = %XXXXxxxx and Y = %YYYYyyyy

 LDA lowNibble,X        \ Set T = (X AND %00001111) OR (Y AND %11110000)
 ORA highNibble,Y       \       = %0000xxxx OR %YYYY0000
 STA T                  \       = %YYYYxxxx

 AND #%11110000         \ Set U = (A AND %11110000) OR (X >> 4)
 ORA shift4Right,X      \       = %YYYY0000 OR %0000XXXX
 STA U                  \       = %YYYYXXXX

 AND #%00001111         \ Set Y = (A AND %00001111) OR (Y << 4)
 ORA shift4Left,Y       \       = %0000XXXX OR %yyyy0000
 TAY                    \       = %yyyyXXXX

 AND #%11110000         \ Set X = (A AND %11110000) OR (X AND %00001111)
 ORA lowNibble,X        \       = %yyyy0000 OR %0000xxxx
 TAX                    \       = %yyyyxxxx

 LDA timesTable,X       \ Set V = %yyyy * %xxxx
 STA V

 LDX T                  \ Set X = T = %YYYYxxxx

 LDA timesTable,X       \ Set A = (%YYYY * %xxxx) + (%yyyy * XXXX)
 CLC                    \
 ADC timesTable,Y       \ Call this %AAAAaaaa with carry C

 ROR A                  \ Set T = A rotated right by 4 places
 ROR A                  \       = %aaaCAAAA
 ROR A                  \
 ROR A                  \ and set the C flag to bit 3 of A
 STA T

 ROR A                  \ Set A = %aaaaCAAA

 AND #%11110000         \ Set A = %aaaa0000

 CLC                    \ Set V = V + A
 ADC V                  \       = V + %aaaa0000
 STA V                  \       = (%yyyy * %xxxx) + %aaaa0000

 LDA T                  \ Set A = T AND %00011111
 AND #%00011111         \       = %aaaCAAAA AND %00011111
                        \       = %000CAAAA

 LDX U                  \ Set A = A + %YYYY * %XXXX
 ADC timesTable,X       \       = %000CAAAA + (%YYYY * %XXXX)

                        \ So we now have:
                        \
                        \   (A V) = A << 8 + V
                        \
                        \         =   (%000CAAAA + (%YYYY * %XXXX)) << 8
                        \           + (%yyyy * %xxxx) + %aaaa0000
                        \
                        \         =   %000CAAAA << 8
                        \           + (%YYYY * %XXXX) << 8
                        \           + (%yyyy * %xxxx)
                        \           + %aaaa0000
                        \
                        \         =   (%YYYY * %XXXX) << 8
                        \           + %000CAAAAaaaa0000
                        \           + (%yyyy * %xxxx)
                        \
                        \ We also have the following:
                        \
                        \   %CAAAAaaaa = (%YYYY * %xxxx) + (%yyyy * XXXX)
                        \
                        \ and:
                        \
                        \   %000CAAAAaaaa0000 = %CAAAAaaaa << 4
                        \
                        \ so combining them all, we get:
                        \
                        \   (A V) =   (%YYYY * %XXXX) << 8
                        \           + %CAAAAaaaa << 4
                        \           + (%yyyy * %xxxx)
                        \
                        \         =   (%YYYY * %XXXX) << 8
                        \             ((%YYYY * %xxxx) + (%yyyy * XXXX)) << 4
                        \           + (%yyyy * %xxxx)
                        \
                        \ which is the result we want

 RTS                    \ Return from the subroutine