You are to write a (commented) C subroutine the multiplies two signed integers using Booth's algorithm. The parameters passed to your subroutine will be two ints (which are 32 bit twos complement integers), but you may assume that these numbers are in the range -128 to +127 (could fit in an 8 bit signed int). This restriction on the range of values means that the loop in your implementation of Booth's algorithm should iterate 8 times. The prototype for the subroutine must look like this:

int booth(int x, int y);

The return value should be the product of x and y. Since you can assume that x and y are both 8 bit integers, the product will always fit in a C int.

Your subroutine must compute the product using Booth's algorithm! This will require some bit manipulation and shifting operations. If you have never done this before in C, some examples of these operations are included below.

NOTE: You do NOT have to mimic the hardware implementation described in the book. This means you can use seperate C variables to store the multiplier and partial product, you do not need to squeeze them in to a single 32 bit int. Your algorithm must treat the multiplier as a collection of sequences of 1s, and do a single subtraction at the beginning of each sequence of 1s and an addition at the end of each sequence of 1s (this is Booth's algorithm).

C Logical Operations

AND and OR

In C the & operator is a bitwise logical AND operation (just like the MIPS and instruction). The | operator computes a bitwise logical OR. Here are a few examples of using the & operator to isolate the value of some bits in a C int:

int a,b,c;

a = 0;   /* a is now 00000000000000000000000000000000 */
b = 5;   /* b is now 00000000000000000000000000000101 */
c = -1;  /* c is now 11111111111111111111111111111111 */

/* We can check the value of a single bit in an int by
   ANDing the int with a constant that has only the bit
   in question set to 1. If the result of the AND is 
   true, this means the bit was a 1. If the result of the
   AND is false, this means all the bits in the result are
   0 including the one bit in question.

   This example tests to see if the LS bit is a 1 by ANDing
   the int b with the value 00000....00001
*/   
   if ( b & 1 ) 
      printf("The LS bit is a 1\n");
   else
      printf("The LS bit is a 0\n");

/* We can also use AND to isolate more than 1 bit at a time,
   for example the following checks the LS 2 bits of c 
   by ANDing with 000...0011 and comparing the result to 000...0010 */

   if ((c & 3) == 2)
      printf("The LS 2 bits are 10\n");
   else if ((c & 3) == 1)
      printf("The LS 2 bits are 01\n");

Using the | (OR) operator is similar.

Shifting in C

The C << operator means "shift left". The operand on the left of the << operator is the value to shift, and the operand to the right is the number of bits to shift. This operator always shifts in 0s on the right side. For example the C expression:

x = y << 1;

means that x should get the value that results from shifting y one bit to the left (and shifting in a 0). If x and y are integers, this is equivalent to saying x = y*2 (we know that shifting an int left is just like multiplying by 2). Note that you can do this:

 
x = x << 1;

The C >> operator means "shift right". If the int being shifted is declared as unsigned int the resulting shift right will be a logical shift, but if the C variable is declared as an int the shift will be an arithmetic shift. Here is code that uses >>:

int x,y;
...

x = x >> 1;   /* shift x one bit to the right. Sign is extended since
               x is an int (arithmetic shift) */

y = x >> 5;   /*  shift x 5 bits to the right and store the result in y */

Testing your function

For this first part of the homework you do not need to include your test code (you will need to write a main() that calls booth to test it) in your submission. You should put just the function definition for the booth function in a file named booth.c and include this file in your submission.

You should use a C compiler to generate an 80x86 assembly language program for your booth function. If you have access to a PC running Linux or BSD you can use the command line gcc -S booth.c to generate the assembly language code for your function. The file you compile should have only your booth() function, you don't need any test code or any #includes. The compiler will generate the file booth.s which will contain the assembly language code for your function.

Your job is to comment the 80x86 assembly language code generated by the compiler. Since the 80x86 instruction set is very different than the MIPS instruction set, you will need to learn about the 80x86 instruction set (and a little about 80x86 assembly language). Chapter 3 includes a brief discussion of the 80x86 instruction set, and the following hyperlinks provide additional details:

• x86 Assembly Language FAQ
• Instruction Set Manual (from Intel)
• A handy reference

If you don't have access to a C compiler running on an 80x86 machine, you can submit your C code to a web based compiler I have running at monte.cs.rpi.edu/~hollingd/comporg/servx86/. You will need to paste your C subroutine in to a form and submit the form. You will get back any compiler messages generated and (if there are no errors) you get a copy of the resulting assembly language program. Send email to hollingd@cs.rpi.edu if you have any problems with the web based system.

Once you have a 80x86 assembly language code for your booth function you should comment the code and include the commented code in a file with your submission. You don't need to worry about commenting (or understanding) assembler directives, but you should comment the actual assembly language instructions. Comments like "shift the multiplier one bit to the right" are good, comments like "shift right register AX" are not what I'm looking for...

You also need to write a MIPS version of the booth subroutine. We will run your booth subroutine with our test program, so you need to make sure you are adhering to the MIPS assembly language subroutine calling convention. Specifically, your subroutine should be written so that:

• The two numbers to multiply are passed to your subroutine in $a0 and $a1.
• Your subroutine returns the product in $v0.
• Your subroutine does not change any of the s registers ($s0, $s1, ...). This doesn't mean you can't use these registers, it just means that if you use them you must save the values on the stack and restore them before returning from the subroutine.

You also must write a subroutine named testbooth that will be used to test your booth subroutine. The testbooth subroutine will receive as parameters the addresses of three arrays (of 32 bit integers) and an integer indicating the length of all three arrays. I'll call the arrays x, y and z and the integer length n in order to describe the function of your subroutine. Your subroutine should compute the product of x[0] * y[0] and put the result in z[0]. Your subroutine should do this n times, that is, do this for the first n elements of the arrays. In C this subroutine would look something like this:

void testbooth( int *x, int *y, int *z, int n) {
   int i;
   
   for (i=0;i<n;i++) 
       z[i] = booth(x[i],y[i]);
}

Your testbooth function will be passed the following parameters:

• The address of the first element of the array x will be in $a0.
• The address of the first element of the array y will be in $a1.
• The address of the first element of the array z will be in $a2.
• The number of elements (n) in each array will be in $a3.

The testbooth MIPS assembly language subroutine should be in the same file as your MIPS booth function when you submit your code.

Below is some MIPS assembly language that might be useful for testing your subroutines, including a main that calls testbooth and then prints out the results.

        .data
space:	.asciiz " "
xis:	.asciiz "\nX = "
yis:	.asciiz "\nY = "
zis:	.asciiz "\nZ = "

# Test data - used by main to test the testbooth subroutine
# (which tests the booth subroutine)
	
x:	.word   10,11,12,13,14,15,16,17,18,19
y:	.word   -19,18,-17,16,-15,14,-13,12,-11,10
z:	.word	0,0,0,0,0,0,0,0,0,0

# ========================================================
	.text		# this is program code
	.align 2	# instructions must be on word boundaries
	.globl main	# main is a global label
	
main:	
	la $a0,x	# load up arg registers with addresses
	la $a1,y
	la $a2,z
	li $a3,10	# and array size 10
	jal testbooth	# go multiply arrays

	li $v0,4	# print out "X ="
	la $a0,xis
	syscall
	
	la $a0,x	# print out x array
	li $a1,10
	jal parray

	li $v0,4	# print out "Y = "
	la $a0,yis
	syscall
	
	la $a0,y	# print out y array
	li $a1,10
	jal parray

	li $v0,4	# print out "Z = " 
	la $a0,zis
	syscall
	
	la $a0,z	# print out z array
	li $a1,10
	jal parray

	li $v0,10	# exit
	syscall

# ========================================================
# print out an array (on one line)
# $a0 is pointer to the array
# $a1 is the size of the array
	
parray:	
	sub $sp,$sp,12	# save ra, s0 and s1
	sw $ra,0($sp)
	sw $s0,4($sp)
	sw $s1,8($sp)

	move $s0,$a0	# move args in to s registers
	move $s1,$a1	# s0 is the pointer, s1 is the count.

pa_loop:
	beq $s1,$zero,pa_bot	# if no more elements - done
	
	# print the next array element (an integer)
	lw $a0,0($s0)		# load element in to $a0
	li $v0,1
	syscall			# print an int

	la $a0,space		# print a space
	li $v0,4
	syscall


	add $s0,$s0,4		# update pointer to point to next element
	sub $s1,$s1,1		# update counter (decrement)
	j pa_loop		# go to top of loop
	
pa_bot:		
	lw $ra,0($sp)		# restore registers
	lw $s0,4($sp)
	lw $s1,8($sp)
	add $sp,$sp,12
	jr $ra			# return