#====================================================================
# FILE		mult-div.s - Multipication and division algorithms.
# File type:	MIPS assembly source (runnable under SPIM)
#
# Description:
#	This program defines a "shamu" subroutine which performs a 
#	shift-add multiplication algorithm on 32-bit unsigned integers,
#	producing a 64-bit unsigned product, using an algorithm 
#	similar to that described in Parhami section 11.3.
#	It also defines a "myDivide" subroutine which divides any two 
#	32-bit unsigned integers, and includes a main routine which
#	tests both subroutines on sample inputs and prints the results
#	to the console under SPIM.
#
# Author:	Michael P. Frank
# Written:	October 27, 2005
# 		(Derived from divide.s written on March 29, 2005.)
#====================================================================

	.text		# Text segment
	.globl	main	# Make label "main" globally accessible
	
#--------------------------------------------------------------------
# SUBROUTINE	shamu - Shift-Add Multiplication algorithm.
#
#	This subroutine takes two unsigned integers (in $a0 and $a1)
#	and returns their 64-bit unsigned product in $v0 and $v1.
#	Uses the approach of adding the partial products into the
#	high word of the product, which is being shifted right.
#	The implementation is a slightly simplified version of 
#	Parhami's Example 11.4.
#
# Arguments:
#	$a0	Unsigned multiplicand.
#	$a1	Unsigned multiplier.
# Results:
#	$v0	High 32 bits of unsigned product.
#	$v1	Low 32 bits of unsigned product.
#
# Corresponding C language source:
#	
#    unsigned long shamu(unsigned int mcand, unsigned int mer) {
#       unsigned int Hi,Lo,carry,bit,counter;
#	Lo = Hi = 0; 	/* Initialize product registers to 0. */
#	counter = 32;	/* Initialize repetition counter to 32. */
#	do {
#	   carry = 0;	   /* Initialize carry-out bit to 0. */
#	   bit = mer & 1;  /* t1 := LSB of m'er. */
#	   mer >>= 1;	   /* Shift m'er right by 1. */
#	   if (bit) {
#	      Hi += mcand;   		/* Add mcand into Hi */
#	      carry = (Hi < mcand);	/* Carry out from add */
#          }
#	   bit = Hi & 1;			/* LSB of Hi */
#	   Hi = (carry << 31) & (Hi >> 1);	/* Shift carry into Hi */
#	   Lo = (bit << 31) & (Lo >> 1);	/* Shift into Lo */
#          counter--;			/* Decrement counter. */
#	} while (counter > 0);
#       return ((unsigned long)Hi)<<32 & Lo;	/* Return results. */
#
# Register mapping for C -> assembly translation:
#
#	Reg.	C variable	Description
#	---	----------	--------------------------------
#	a0	mcand		m'cand = Multiplicand
#	a1	mer		m'er   = Multiplier
#	v0	Hi		Most significant word of product.
#	v1	Lo		Least significant word of product.
#	t0	carry		Carry out of high word of product.
#	t1	bit		Bit being shifted out of a word.
#	t2	counter		Repetition counter for loop.
#
#--------------------------------------------------------------------
shamu:	move	$v0,$zero	# Initialize Hi to 0
	move	$v1,$zero	# Initialize Lo to 0
	addi	$t2,$zero,32	# Initialize repetition counter to 32.
mloop:	move	$t0,$zero	# Loop: Initialize carry to 0.
	andi	$t1,$a1,1	#    LSB of multiplier will be shifted out.
	srl	$a1,$a1,1	#    Shift the multiplier right.
	beqz	$t1,no_add	#    If bit shifted out was not 0, then
	addu	$v0,$v0,$a0	#	add multiplicand into Hi word,
	sltu	$t0,$v0,$a0	#	and remember the carry out.
no_add:	andi	$t1,$v0,1	#    LSB of Hi word will be shifted out.
	srl	$v0,$v0,1	#    Shift Hi word of product right.
	sll	$t0,$t0,31	#    Shift carry left to position 31.
	or	$v0,$t0,$v0	#    OR the carry into the Hi word.
	srl	$v1,$v1,1	#    Shift Lo word of product right.
	sll	$t1,$t1,31	#    Shift bit left to position 31.
	or	$v1,$t1,$v1	#    OR the bit into the Lo word.
	addi	$t2,$t2,-1	#    Decrement loop counter.
	bnez	$t2,mloop	#    Continue while counter is nonzero.
	jr	$ra		# Return product=($v0,$v1) to caller.
	
#----------------------------------------------------------------------------
# myDivide: Given a 32-bit unsigned dividend (in $a0) and a 32-bit unsigned
# divisor in ($a1), compute and return the 32-bit unsigned integer quotient 
# and also return (in the location pointed to by $a2) the 32-bit unsigned 
# integer remainder.
# 
# Equivalent C++ source code:
#
# unsigned int myDivide
# (unsigned int dividend,            // Argument 0: Number to be divided.
#  unsigned int divisor,             // Argument 1: Number to divide it by.
#  unsigned int &remainder)          // Argument 2: Place to put remainder.
# {unsigned int quotient = 0;        // Quotient: Initially zero.
#  int position = 0;                 // Bit position: Initially zero.
#  while (!(divisor & 0x80000000)) { // While divisor is not shifted all the way to the left,
#    position++;		     //   Increment bit position,
#    divisor <<= 1; }		     //   and shift divisor one place left.
#  do {                              // Repeat the following:
#    quotient <<= 1;                 //   Make room for a new bit of quotient.
#    if (dividend >= divisor) {      //   If we can do a subtraction here,
#      dividend -= divisor;	     //     Then do it.
#      quotient |= 1; }              //      and set this bit of the quotient to 1.
#    divisor >>= 1; }                //   Shift divisor right to a new position.
#  while (--position >= 0);	     // Decrement bit position and continue while it's non-negative.
#  remainder = dividend;             // Return remainder.
#  return quotient;                  // Return quotient and end.
# }
#
# Hand-assembled MIPS code follows.
#
# Register map:
#	$ra - return address
#	$a0 - dividend argument, then working remainder
#	$a1 - divisor argument, then shifted version of it
#	$a2 - address of location to store the final remainder
#	$v0 - quotient (to return)
#	$t0 - bit position to which we have left-shifted the divisor
#	$t1 - misc. temporary register
		
myDivide:	move	$v0, $zero		# quotient := 0;
		move	$t0, $zero		# position := 0;
leftShift:	and	$t1, $a1, 0x80000000	# while (divisor & 0x80000000
		bne	$t1, $zero, doTop	#        != 0) {
		addi	$t0, $t0, 1		#   position++;
		sll	$a1, $a1, 1		#   divisor <<= 1;
		b	leftShift		# }
doTop:		sll	$v0, $v0, 1		# do { quotient <<= 1;
		sltu	$t1, $a0, $a1		#   $t4 := (dividend < divisor)
		bne	$t1, $zero, endIf	#   if ($t4 == 0) {          // If dividend >= divisor
		subu	$a0, $a0, $a1		#     dividend -= divisor;
		or	$v0, $v0, 1		#     quotient |= 1; }
endIf:		srl	$a1, $a1, 1		#   divisor >>= 1;
		addi	$t0, $t0, -1		#   position--;
		bgez	$t0, doTop		# } while (position >= 0);
endFor:		sw	$a0, 0($a2)		# rem := remainder;
		jr	$ra			# return.

#-------------------------------------------------------
# main() - This routine, called automatically when
#  SPIM starts, does whatever our program needs to do.
#  In our case, we simply perform a test division using
#  the myDivide subroutine and then print the results.
#-------------------------------------------------------

main:	# Push our return address $ra onto the stack.

	addi	$sp, $sp, -4
	sw	$ra, 0($sp)
	
	# Perform test multiplication using shamu subroutine.
	
	la	$t0, multiplicand	# $t0 := &multiplicand;
	lw	$a0, 0($t0)		# $a0 := *$t0 = multiplicand;
	la	$t0, multiplier		# $t0 := &multiplier;
	lw	$a1, 0($t0)		# $a1 := *$t0 = multiplier;
	jal	shamu			# ($v0, $v1) := shamu($a0, $a1)
	la	$t0, product_msw	# $t0 := &product_msw;
	sw	$v0, 0($t0)		# product_msw = $v0;
	sw	$v1, 4($t0)		# product_lsw = $v1;
	
	# Print the multiplicand.
	
	la	$a0, mcand_str		# "Multiplicand" string
	jal	print_str		# Print it.
	la	$t0, multiplicand	# $t0 = &multiplicand;
	lw	$a0, 0($t0)		# $a0 = multiplicand;
	jal	print_uint		# Print it.
	jal	print_cr		# End line.
	
	# Print the multiplier.
	
	la	$a0, mer_str		# "Multiplier" string
	jal	print_str		# Print it.
	la	$t0, multiplier		# $t0 = &multiplier;
	lw	$a0, 0($t0)		# $a0 = multiplier;
	jal	print_uint		# Print it.
	jal	print_cr		# End line.
	
	# Print the high word of the product.
	
	la	$a0, prod_hi_str	# "Product high" string
	jal	print_str		# Print it.
	la	$t0, product_msw	# $t0 = &product_msw;
	lw	$a0, 0($t0)		# $a0 = product_msw;
	jal	print_uint		# Print it.
	jal	print_cr		# End line.
	
	# Print the low word of the product.
	
	la	$a0, prod_lo_str	# "Product low" string
	jal	print_str		# Print it.
	la	$t0, product_lsw	# $t0 = &product_lsw;
	lw	$a0, 0($t0)		# $a0 = product_lsw;
	jal	print_uint		# Print it.
	jal	print_cr		# End line.
	
	# Print a blank line to separate multiplication & division output.
	jal	print_cr		# Print a blank line.
	
	# Perform test division using myDivide subroutine.

	la	$t0, dividend		# $t0 := &dividend;
	lw	$a0, 0($t0)		# $a0 := *$t0 = dividend;
	la	$t0, divisor		# $t0 := &divisor;
	lw	$a1, 0($t0)		# $a1 := *$t0 = divisor;
	la	$a2, remainder		# $a2 := &remainder;
	jal	myDivide		# ($v0, *$a2) := myDivide($a0, $a1, $a2)
	la	$t0, quotient		# $t0 := &quotient;
	sw	$v0, 0($t0)		# quotient := $v0;
	
	# Print the dividend.
	
	la	$a0, dividend_str	# "Dividend" string.
	jal	print_str		# Print it.
	la	$t0, dividend		# $t0 = &dividend;
	lw	$a0, 0($t0)		# $a0 = dividend;
	jal	print_uint		# Print it.
	jal	print_cr		# End line.
	
	# Print the divisor.
	
	la	$a0, divisor_str	# "Divisor" string.
	jal	print_str		# Print it.
	la	$t0, divisor		# $t0 = &dividend;
	lw	$a0, 0($t0)		# $a0 = dividend;
	jal	print_uint		# Print it.
	jal	print_cr		# End line.
	
	# Print the quotient.
	
	la	$a0, quotient_str	# "Quotient" string.
	jal	print_str		# Print it.
	la	$t0, quotient		# $t0 = &quotient;
	lw	$a0, 0($t0)		# $a0 = quotient;
	jal	print_uint		# Print it.
	jal	print_cr		# End line.
	
	# Print the remainder.
	
	la	$a0, remainder_str	# "Remainder" string.
	jal	print_str		# Print it.
	la	$t0, remainder		# $t0 = &remainder;
	lw	$a0, 0($t0)		# $a0 = remainder;
	jal	print_uint		# Print it.
	jal	print_cr		# End line.
	
	# Prepare to return from main(): Pop our return address $ra off the stack
	
	lw	$ra, 0($sp)
	addi	$sp, $sp, 4
	
	# Return to caller of main() - I.e., to runtime environment.
	
	jr	$ra
	
# End of main routine.

#================================================================================
# Global variables.
#================================================================================

	.data			# Locate the following in data segment.

# Global variables for numbers we're working with.

multiplicand:	.word	4000000000	# Multiplier:   4,123,456,789
multiplier:	.word	3000000000	# Multiplicand: 4,231,098,765
#multiplicand:	.word	4123456789	# Multiplier:   4,123,456,789
#multiplier:	.word	4231098765	# Multiplicand: 4,231,098,765
product_msw:	.word	0		# Placeholder for high word of product.
product_lsw:	.word	0		# Placeholder for low word of product.
# Note: product_lsw must immediately follow product_msw.

dividend:	.word 	4000000000	# Number to divide: 4 billion
divisor: 	.word	65000		# Number to divide by: 65 thousand.
quotient:	.word	0		# Placeholder for quotient.
remainder:	.word	0		# Placeholder for remainder.

# Strings for use in output.

mcand_str:	.asciiz	"Multiplicand:         "
mer_str:	.asciiz "Multiplier:           "
prod_hi_str:	.asciiz "High word of product: "
prod_lo_str:	.asciiz "Low word of product:  "

dividend_str:	.asciiz "Dividend:  "	# zero-terminated string to print.
divisor_str:	.asciiz	"Divisor:   "	
quotient_str:	.asciiz "Quotient:  "
remainder_str:  .asciiz "Remainder: "

#================================================================================
# Utility subroutines.
#================================================================================

	.text	# Back to text segment.
#----------------------------------------------------
# print_str: This subroutine takes a pointer to a 
# zero-terminated string in $a0, and prints
# it to the console using the SPIM system services.
# Side effect: Trashes $v0.
#----------------------------------------------------
print_str:
	li	$v0, 4		# Select code for "print_string" service
	syscall			# Call the operating system (SPIM) service
	jr	$ra		# Return from print_str

#---------------------------------------------------
# Prints single character $a0 to console using SPIM.
#---------------------------------------------------
print_char:
	li	$v0, 11
	syscall
	jr	$ra

#--------------------------------------------------------
# Print a carriage return character to the SPIM console.
#--------------------------------------------------------
print_cr:
	addi	$sp, $sp, -4
	sw	$ra, 0($sp)
	li	$a0, 13		# ASCII Carriage Return character
	jal	print_char
	lw	$ra, 0($sp)
	addi	$sp, $sp, 4
	jr	$ra

#-------------------------------------------------------------
# Print string at $a0 to console followed by a CR using SPIM.
#-------------------------------------------------------------
print_str_cr:
	addi	$sp, $sp, -4
	sw	$ra, 0($sp)
	jal	print_str	# Print the string.
	li	$a0, 13		# ASCII CR
	jal	print_char	# Print that.
	lw	$ra, 0($sp)
	addi	$sp, $sp, 4
	jr	$ra

#----------------------------------------------------
# print_int: Prints an integer contained in $a0.
#----------------------------------------------------
print_int:
	li	$v0, 1		# Select code for "print_int" service
	syscall			# Call the operating system (SPIM) service
	jr	$ra		# Return from print_int

#-----------------------------------------------------
# print_digit: Given a number 0-9 in $a0, prints the
# ASCII character for the corresponding decimal digit.
#-----------------------------------------------------
print_digit:
	addi	$a0, $a0, 48	# Add code for ASCII '0' character to number
	j	print_char	# Print the character with the resulting code.

#---------------------------------------------------------------------------
# print_uint:  Prints the standard ASCII decimal representation of an
# unsigned 32-bit integer contained in $a0.  Uses myDivide internally.  
# (divu can't be used because its remainder is unspecified on inputs that 
# have bit 31 set.)
#---------------------------------------------------------------------------
# Registers:
#   $a0 = Argument: number. (Number to print.)  Later, digit. (Digit to print.)
#   $a1 = Divisor to pass to myDivide.
#   $a2 = Address of remainder variable, to pass to myDivide.
#   $s0 = residue.  (Remaining residue to convert.)
#   $s1 = base.  (Constant 10, because we want to print the value in decimal.)
#   $s2 = digit.  (Digit value 0-9 to print.)
#   $s3 = posVal.  (Value of present digit position, ranges from 1000000000 down to 1.)
#   $s4 = Boolean variable anyYet = Have we printed any nonzero digits yet?
#   $v0 = Quotient returned by myDivide.

print_uint:
	# Save $ra and $s0-s4 on stack.  Also reserve a word on stack for remainder from myDivide.
	
	addi	$sp, $sp, -28	# Room for 7 words (6 saved registers + 1 stack-allocated local variable)
	sw	$ra, 0($sp)	# Save our return address.
	sw	$s0, 4($sp)	# Save various $s registers that we'll be using.
	sw	$s1, 8($sp)
	sw	$s2, 12($sp)
	sw	$s3, 16($sp)
	sw	$s4, 20($sp)
	
	# Initialize local variables.
	
	move	$s0, $a0	  # residue := number.  Residue = Number to be printed.
	li	$s3, 1000000000	  # posVal := 10^9.  Initial position value.  1 billion = Largest power of 10 less than 2^32.
	li	$s1, 10		  # ten := 10.  Constant 10, we'll divide the position value by this each time.
	move	$s4, $zero	  # anyYet := false. (No nonzero digits have been printed yet.)
	
	# If position value is less than 10, then this is the last digit.
	
loop:	sltu	$t0, $s3, $s1		# $t0 := (posVal < base).
	bne	$t0, $zero, lastDigit	# if ($t0 != 0) goto lastDigit.  (Break out of loop.)
	
	# The following code extracts a digit as follows:
	#   digit($a0) := residue($s0) / posVal($s3) (quotient of this division)
	#   residue := residue % posVal (remainder of this division)
	
	move	$a0, $s0	# Argument 0: dividend := residue.
	move	$a1, $s3	# Argument 1: divisor := posVal. (Position value.)
	la	$a2, 24($sp)	# Argument 2: Reference to remainder, on stack.
	jal	myDivide	# quotient($v0) := dividend($a0)/divisor($a1); remainder := dividend % divisor.
	lw      $s0, 24($sp)	# residue := remainder
	move	$a0, $v0	# digit := quotient
	
	bne	$s4, $zero, printIt	# if (!anyYet) goto printIt;  // Saw a nonzero digit earlier?  Print the digit
	beq	$a0, $zero, after	# if (digit == 0) goto after; // Still looking at leading zeros?  Skip it.
	addi	$s4, $s4, 1		# anyYet := 1;                // First nonzero digit.  Remember!

printIt:
	jal	print_digit	# Print the digit we got from the quotient.
after:
	# Divide the value of the present digit position by the base, to go to the next position.
	
	divu	$s3, $s1	# LO := posVal($s3) / base($s1)
	mflo	$s3		# posVal := LO
	
	j	loop		# Continue printing more digits.
	
	# Print the last digit, still contained in $s0.
lastDigit:
	move	$a0, $s0	# digit := residue.
	jal	print_digit	# Print it.
	
	# Restore saved registers.
	lw	$ra, 0($sp)
	lw	$s0, 4($sp)
	lw	$s1, 8($sp)
	lw	$s2, 12($sp)
	lw	$s3, 16($sp)
	lw	$s4, 20($sp)
	addi	$sp, $sp, 28	# Restore stack pointer.
	
	jr	$ra		# Return from print_uint.