#----------------------------------------------------------------------------------
#        This program contains 2 procedures:
#
#		mult32: Perform multiplication
#
#		main: Test the multiplication for different numbers
#
#
#
#----------------------------------------------------------------------------------

		.text

#----------------------------------------------------------------------------------
#       Procedure Name: Main
#
#       Description: Performs the following tests to mult
#				71 			*	2
#				12345 		* 	0x00008000
#				999 		* 	1
#				542371 		*	0
#				0			*	744671
#				0xffffffff	*	71
#				0x7fffffff	*	0xffffffff
#				0xffffffff	*	0xffffffff
#
#
#       Register Allocation:
#				$4: Multiplicand
#				$5: Multiplier
#				$6: pointer to ProductH
#				$7: Pointer to ProductL
#				$11: Misc temp register
#				$12: Array pointer (i)
#				$20: Address of start of Candtest
#				$21: Address of start of Ertest
#
#----------------------------------------------------------------------------------

	.globl main

main:	addi $12, $0, 0			#Sets up the array pointer. Start at 0
		la	$6, ProductH		#Saves the address of productH in $6
		la $7, ProductL			#Saves the address of productL in $7

		la $20,Candtest			#Loads the start address of Candtest in $4
		la $21, Ertest			#Loads the address of start of Ertest in $5

main1:	add $11, $12, $20		#Adds array offset to start address
		lw $4, 0($11)			#Loads Candtest[i] in $4 (Multiplicand)
	    add $11, $12, $21		#Adds array offset to start address
		lw $5, 0($11)			#Loads Ertest[i] in $5 (Multiplier)

#-----------------------------------------------------------------------------------#
#																					#
#	The following loop will perform the	division for all our test cases				#
#	and print out the result in 0x.													#
# 																					#
#	The decimal values of ProductH amd ProductL will also be printed				#
#																					#
#	C Source Code																	#
#																					#
#  	for (i = 0; i < test; ++i)														#
#  		{																			#
#    		printf("%lu (0x%lx) multiplied by %lu (0x%lx)",							#
#			Candtest[i], Candtest[i], Ertest[i], Ertest[i]);						#
#																					#
#			mult32 (Candtest[i], Ertest[i], &ProductH, &ProductL);					#
#																					#
#	     	printf("is 0x%lx%lx  \n(ProductH=%lu, ProductL=%lu\n\n", 				#
#			ProductH, ProductL, ProductH, ProductL);								#
#		}																			#
#!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!#
#	The print output will be slightley different. Since we can't print in hex		#
#	multiplicand 0x and multiplier 0x will not appear. Same thing appies for 		#
#	the result. Only ProductH/L	will appear in decimal 2s complement. That will 	#
#	mess up any value > 0x70000000, but what else can you do...						#
#-----------------------------------------------------------------------------------#


main10:	addi $2, $0, 1			#Code for printing integers
		#Our multiplicand is already in $4
		syscall					#Prints Candtest[i]

		addi $2, $0, 4			#Code for printing strings
		la $4, Multby			#Loads the string " Multiplied by "
		syscall					#Prints "multiplied by"

		addi $2, $0, 1			#Code for printing integers
		add $4, $5, $0			#Multiplier is already in $5, moving it to $4 for printing
		syscall					#Prints ErTest[i]

		lw $4, Candtest($12)	#Loads Candtest[i] in $4 (Multiplicand)

#-------------------------------------------------------#
#		Now to pass variables to mult32					#
#		Copied from question 2							#
#-------------------------------------------------------#
		addi $29, $29, -16		#Decrements stack pointer by 16
		sw $7, 12($29)			#Stacks pointer to ProductL
		sw $6, 8($29)			#Stacks pointer to ProductH
		sw $5, 4($29)			#Stacks Multiplier
		sw $4, 0($29)			#Stacks Multiplicand on top of it all

		jal mult32				#Jumps to mult32

		addi $2, $0, 4			#Code for printing strings
		la $4, Is				#Gets the string "Is" ready to print
		syscall					#Prints out " is:\n ProductH = "

		addi $2 $0, 1			#Code for printing integers
		lw $4, 0($6)			#Puts the value of ProductH in $4
		syscall					#Prints out producth

#-----------------------------------------------------------------------#
#		Since the vlaue of ProductH is stored in unsigned 32 bit		#
#		but expressed in 2s complement, its a good ides  to warn user	#
#-----------------------------------------------------------------------#

		slt $11, $4, $0			#If MSB=1, $11=1
		beq $11, $0, main20		#If MSB=0, skip the next part
		addi $2, $0, 4			#Code for printing strings
		la $4, Twos				#Loads adress of string Twos in $4
		syscall					#Prints out warning about (-)

main20:	addi $2, $0, 4			#Code for printing strings
		la $4, And				#Gets the string "And" ready to print
		syscall					#Prints out " and ProductL = "

		addi $2 $0, 1			#Code for printing integers
		lw $4, 0($7)			#Puts the value of ProductL in $4
		syscall					#Prints out productL

#-----------------------------------------------------------------------#
#		Since the vlaue of ProductL is stored in unsigned 32 bit		#
#		but expressed in 2s complement, its a good ides  to warn user	#
#-----------------------------------------------------------------------#

		slt $11, $4, $0			#If MSB=1, $11=1
		beq $11, $0, main30		#If MSB=0, skip the next part
		addi $2, $0, 4			#Code for printing strings
		la $4, Twos				#Loads adress of string Twos in $4
		syscall					#Prints out warning about (-)

main30:	li $2, 4				#Code for printing strings
		la $4, Enter			#String label enter
		syscall					#Changer line

#-------------------------------------------------------------------------------#
#		All thats left to do is increment array pointer ($12) and branch 		#
#		back to top if nescessary												#
#																				#
#		Source C code															#
#				for (i = 0; i < test; ++i)										#
#		(test=10)																#
#-------------------------------------------------------------------------------#

		addi $12, $12, 4		#Increments i++
		slti $11, $12, 40		#As long as we havent done 10 tests, $11=1
		bne $11, $0, main1		#Branches back to start

		li $2, 10				#Exit code
		syscall					#Done




#-------------------------------------------------------------------------------#
#																				#
#																				#
#		Mult32(): Will multiply the 32 bit integers and store the result		#
#			in memory at ProductH and ProductL									#
#																				#
#		Input variables (in stack)												#
#				- ProductL address	(Bottom @ $sp-12)							#
#				- ProductH address	(@ $sp-8)									#
#				- Multiplier		(@ $sp-4)									#
#				- Multiplicand		(@ $sp)										#
#																				#
#		Register allocations													#
#				$5 = Multiplier													#
#				$6 = pointer to ProductH										#
#				$7 = pointer to ProductL										#
#				$8 = Multiplicand												#
#				$10 = Overflow flag												#
#				$11 = Misc temp register										#
#				$12 = counter (i)												#
#				$16 = Temporary ProductH										#
#				$17 = Temporary ProductL										#
#				$23 = One more temp register									#
#-------------------------------------------------------------------------------#

#First, save the content of registers that will be used

mult32:	addi $29, $29, -44		#Decrements stack pointer
		sw $30, 40($29)			#Stores register values to stack
		sw $23, 36($29)
		sw $17, 32($29)
		sw $16, 28($29)
		sw $12, 24($29)
		sw $11, 20($29)
		sw $10, 16($29)
		sw $8, 12($29)
		sw $7, 8($29)
		sw $6, 4($29)
		sw $5, 0($29)

#Now we can set our frame pointer

		addi $30, $29, 44		#Sets $fp = $sp @start of mult32

#-----------------------------------------------------------#
#		And now the function can start. We beguin by 		#
#		gathering nescessary data from stack				#
#															#
#		We will use the same registers as in main() to		#
#		simplify understanding, except for $4 because		#
#		it is often used by syscall							#
#-----------------------------------------------------------#

		lw $7, 12($30)			#$7 = pointer to ProductL
		lw $6, 8($30)			#$6 = pointer to ProductH
		lw $5, 4($30)			#$5 = Multiplier
		lw $8, 0($30)			#$8 = Multiplicand

#-----------------------------------------------------------#
#		Step 1: Initialisation								#
#			Upper 32 bits are cleared						#
#			Multiplier is stored in lower 32 bits			#
#															#
#		Source c code:										#
#			*ProductL = Multiplier;							#
#			*ProductH = 0;									#
#-----------------------------------------------------------#

		addu $17, $0, $5			#ProductL = multiplier
		add $16, $0, $0			#ProductH = 0

#-----------------------------------------------------------#
#		Step 2: Test, add, shift							#
#		Step will be repeated 32 times						#
#			If least Significant bit = 1					#
#			Add multiplier to upper 32 bits					#
#			Else, add 0										#
#															#
#			Shift right (32 times, couted by $12)			#
#			Account for addition overflow after shift		#
#-----------------------------------------------------------#
#		C source code										#
#															#
#		for (i = 0; i < 32; i++){							#
#		int i, overflow;									#
#															#
#-----------------------------------------------------------#

		addi $12, $0, 32		#Sets downcounter to 32

#-----------------------------------------------------------#
#		Test and Addition, if needed						#
#															#
#		C source code										#
#															#
#			overflow = 0;									#
#			if (*ProductL & 0x00000001)						#
#			{												#
#															#
#			if ((*ProductH + Multiplicand)<*ProductH)		#
#				{overflow = 0x80000000;}					#
#															#
#			*ProductH += Multiplicand;}						#
#-----------------------------------------------------------#

mul10:	andi $11, $17, 1 		#If LSB of ProductL=1, $11=1
		li $10, 0				#Resets overflow flag to 0 if we skipp addition
		beq, $11, $0, mul20		#If LSB of ProductL=0, skip addition

		addu $11, $16, $8		#Add ProductH+Multiplicand, put result in $11
		sltu $10, $11, $16 		#Sets $10 if ProductH+Multiplicand<ProductH
		bne $10, 0, mul16		#if we flaged an overflow, skip next step so we dont overwrite $10

		sltu $10, $11, $8		#Sets $10 if ProductH+Multiplicand<Multiplicand

mul16:	addu $16, $16, $8		#ProductH'=ProductH+Multiplicand

#-----------------------------------------------------------#
#		Shift, and transfer bit if nescessary				#
#															#
#		C Source code:										#
#															#
#			*ProductL = *ProductL >> 1;						#
#															#
#			if (*ProductH & 0x00000001)						#
#				{											#
#					*ProductL = (*ProductL | 0x80000000);	#
#				}											#
#			*ProductH = *ProductH >> 1;						#
#-----------------------------------------------------------#

mul20:	srl $17, $17, 1			#ProductL >>1

		andi $11, $16, 1		#If LSB of ProductH=1, $11=1
		beq $11, $0, mul30		#If LSB of ProductH=0, skip next step
		lui $11, 0x8000			#Loads 0x8000 0000 in $11
		addu $17, $17, $11		#Sets MSB of ProductL=1

mul30:	srl $16, $16, 1			#ProductH >>1


#-----------------------------------------------------------------------#
#		At this point, we need to account for overflow in				#
#		Earlier addition. If overflow occured, $10=1. If there 			#
#		was no overflow, $10=0. 										#
#																		#
#		C source code:													#
#			*ProductH = *ProductH | overflow;//(=0x8000000)				#
#-----------------------------------------------------------------------#

		beq $10, $0, mul40		#Skip next step if there was no overflow
		lui $11, 0x8000			#Loads 0x8000 0000 in $11
		addu $16, $16, $11		#Sets MSB of ProductH=1 ($11=0x8000 00000)


#-----------------------------------------------------------------------#
#		All threr is left to do here is decrement counter (i=$12)		#
#		and branch back to top if nescessary. Otherwise, store			#
#		ProductH/L in memory, restore registers and jump back to main	#
#-----------------------------------------------------------------------#

mul40:	addi $12, $12, -1		#Decrements counter by 1
		bne $12, $0, mul10		#Keep branching until counter reaches 0

		sw $16, 0($6)			#Stores temporary ProductH($16) @ address of ProductH($6)
		sw $17, 0($7)			#Stores temporary ProductL($17) @ address of productL($7)

		lw $30, 40($29)			#restores register values to stack
		lw $23, 36($29)
		lw $17, 32($29)
		lw $16, 28($29)
		lw $12, 24($29)
		lw $11, 20($29)
		lw $10, 16($29)
		lw $8, 12($29)
		lw $7, 8($29)
		lw $6, 4($29)
		addi $29, $29, 44		#increments stack pointer

		jr $31					#Jumps back to main function

#-----------------------------------------------------------------------------------


	.data
#---------------#
#	Strings		#
#---------------#

Multby: 	.asciiz 	" multiplied by "
Is:			.asciiz		" is: ProductH = "
And:		.asciiz		" and ProductL = "
Enter:		.asciiz		"\n\n"
Twos:		.asciiz		"\n(Expressed in 2s complement, but represent an unsigned integer. Convert manually)\n"


#-----------------------------------------------------------------------#
#	Memory allocation for passing variable address via stack			#
#																		#
#		C Source code:													#
#			unsigned long ProductH = 0, ProductL = 0;					#
#-----------------------------------------------------------------------#

ProductH:	.word		0
ProductL:	.word		0

#-----------------------------------------------------------------------#
#	Static Variables for mult() testing									#
#																		#
#	C Source code:														#
#																		#
#	unsigned long Candtest[test] =										#
#  	{0x12345678,  	0x87654321, 	0, 			0xfffffff,	0,			#
#	0xabcdef00, 	0x8fffffff, 	0xffffffff, 0xf4444419, 0xffffffff};#
#																		#
#  	unsigned long Ertest[test] =										#
#  	{0x10000000,  	0, 		 		0x1234567, 	0, 			1,			#
#	1, 				1, 				0x744671, 	0xffffffff, 0xffffffff};#
#-----------------------------------------------------------------------#

Candtest: 	.word 		0x12345678, 0x87654321, 0, 0xfffffff, 0, 0xabcdef00, 0x8fffffff, 0xffffffff, 0xf4444419, 0xffffffff
Ertest: 	.word 		0x10000000, 0, 0x1234567, 0, 1,	1, 1, 0x744671, 0xffffffff, 0xffffffff


