Homework #5 - MIPS Assembly language implementation of Booths Algorithm

Assignment

You must provide a MIPS subroutine that implements Booth's Algorithm for multiplication of two 8-bit signed numbers. Your subroutine cannot use any mult instructions, and it must implement Booth's algorithm (multiplication via simple repeated addition is not Booth's algorithm!).

Your subroutine must be named booth and will be passed two 32-bit, signed integers, one in each of $a0 and $a1. Your subroutine can assume that the numbers are in the range -128 to +127 (you only need to do 8 bit multiplication). You must return two values:

• $v0: return the product (as a 32 bit signed integer).
• $v1: return the number of addition or subtraction operations that were necessary to compute the product. These should only include the addition or subtraction operations that operate on the multiplicand and partial product (don't include any adds or subtracts you use for loop control).

Your subroutine may not change any of the S registers ($S0, $S1, ...). Of course you may use these, the idea is that when your subroutine returns, the original values must be restored...

Some things you will need to know

• The MIPS instruction set, including the pseudoinstructions supported by SPIM. Appendix A of the text includes a reference.

• Booth's Algorithm. Check out the course text and/or lecture notes.

• How to write a MIPS subroutine. Your booth code must be in a subroutine for us to test it.

What to turn in, and how to submit

What you need to submit

You should submit your subroutine in a file by itself, do not submit a main or any other test code! We will add our own main (and it will test all possible combinations of inputs!) - all you need to supply is a file that contains your booth subroutine. Important!: Name your file booth.asm

How to submit

Email your submission to comporg-submit@cs.rpi.edu with the subject line "HW5".

Grading

Assembly language is very hard to read! Make sure you provide lots of comments to help us.

Grades will be determine by:

• Works correctly: 80%
• Code readability: 20%

Notes and Hints

• Here is some code you can use to test your subroutine. Paste your booth subroutine at the bottom of this file and run it using SPIM.

  .data promptx: .asciiz "\nX = " prompty: .asciiz "\nY = " prod: .asciiz "\nX*Y= " ops: .asciiz "\nNumber of ops was " # ======================================================== .text # this is program code .align 2 # instructions must be on word boundaries .globl main # main is a global label main: add $sp,$sp,-4 # Save $ra so main can return sw $ra,0($sp) li $v0,4 # Prompt for first number la $a0,promptx syscall li $v0,5 # read an int syscall # get X, save in $t0 move $t0,$v0 li $v0,4 # Prompt for second number la $a0,prompty syscall li $v0,5 # read an int syscall # get Y, save in $a1 move $a1,$v0 move $a0,$t0 # put X back in $a0 so we can call booth jal booth # multiply using booth subroutine move $t0,$v0 # save the product move $t1,$v1 # and number of add/sub ops li $v0,4 # print "x*y =" la $a0,prod syscall li $v0,1 # print the product move $a0,$t0 syscall li $v0,4 # print "Number of ops" la $a0,ops syscall li $v0,1 # print the number of ops move $a0,$t1 syscall lw $ra,0($sp) # restore $ra add $sp,$sp,4 jr $ra # return

  Here is what the above program looks like when run (twice):