A typical implementation
Booth's algorithm can be implemented by repeatedly adding (with ordinary unsigned binary addition) one of two predetermined values A and S to a product P, then performing a rightward arithmetic shift on P. Let m and r be the multiplicand and multiplier, respectively; and let x and y represent the number of bits in m and r.
Determine the values of A and S, and the initial value of P. All of these numbers should have a length equal to (x + y + 1).
A: Fill the most significant (leftmost) bits with the value of m. Fill the remaining (y + 1) bits with zeros.
S: Fill the most significant bits with the value of (−m) in two's complement notation. Fill the remaining (y + 1) bits with zeros.
P: Fill the most significant x bits with zeros. To the right of this, append the value of r. Fill the least significant (rightmost) bit with a zero.
Determine the two least significant (rightmost) bits of P.
If they are 01, find the value of P + A. Ignore any overflow.
If they are 10, find the value of P + S. Ignore any overflow.
If they are 00, do nothing. Use P directly in the next step.
If they are 11, do nothing. Use P directly in the next step.
Arithmetically shift the value obtained in the 2nd step by a single place to the right. Let P now equal this new value.
Repeat steps 2 and 3 until they have been done y times.
Drop the least significant (rightmost) bit from P. This is the product of m and r.
For more details about Booth algorithm,refer to here
######################################################################################################
# Program: Booth Multiplication Algorithm
# Language: MIPS Assembly (32-bit)
# Arguments:
# $2 stores multiplicand (m)
# $3 stores multiplier (r)
# $5 stores the number of bits of each element
# $6 stores high 32-bit of result
# $7 stores low 32-bit of result
# Author: brant-ruan
# Date: 2016-03-11
# IDE: MARS 4.5
######################################################################################################
.text
add $2, $0, -8 # multiplicand (m)
add $3, $0, 3 # multiplier (r)
xor $4, $4, $4 # i = 0
add $5, $0, 32 # max_iteration times
xor $6, $6, $6 # high 32-bit of P
add $7, $0, $3 # low 32-bit of P
xor $9, $9, $9 # store the rightmost bit of P
begin:
sll $10, $7, 1 # $10 = $7 << 1
or $9, $9, $10 #
and $9, $9, 3 # generate the 2 rightmost bits of P
beq $9, 0, shift # 0 then goto shift
beq $9, 3, shift # 3 then goto shift
beq $9, 2, case_2 # 2 then goto case_2
case_1: # P(high 32-bit) = P(high 32-bit) + m
add $6, $6, $2
j shift
case_2: # P(high 32-bit) = P(high 32-bit) - m
sub $6, $6, $2
shift:
and $8, $6, 1 # $8 stores the rightmost bit of high 32-bit of P
sra $6, $6, 1 # high 32-bit >> 1
sll $8, $8, 31 #
and $9, $7, 1 # $9 stores the rightmost bit of P
srl $7, $7, 1 # logical shift ! Not sra !
or $7, $8, $7 # rightmost of high 32-bit becomes the leftmost of low 32-bit
add $4, $4, 1 # i++
bne $4, $5, begin # if i != 32, back to begin
end: