# File:        p5-soln.asm
# Written by:  Larry Merkle, Dec. 5, 2002
#
# This file contains a MIPS assembly language program that uses only the instructions
# introduced in P02-1.asm, P02-2.asm, P02-3.asm, and P03-1.asm, plus the following:
#
#   beq rs, rt, label	- Conditionally branch to label if register rs equals rt.
#   j label		- Unconditionally jump to label. 
#   sll rd, rt, shamt	- Shift register rt left by the distance indicated by 
#			  immediate shamt and put the result in register rd.
#			  Note:  this is an efficient way to multiply by a power of 2.
#			  In this program this instruction is used to multiply by 4.
#
# It finds the largest element of a zero-based array of non-negative integers, as well as its index.
#
# It is intended to help CS232 students familiarize themselves with MIPS and SPIM.
# After simulating and understanding this program, students are asked to modify it
# so that it swaps the largest element with the last element.  They are then asked
# to modify it so that it finds the second largest element and swaps it with the 
# penultimate (next to last) element.
#
# Register usage
#
# $t0 - two uses:
#       1) the address of N
#       2) the value of N
# $t1 - the constant 1
# $t2 - i (the counter)
# $t3 - unused
# $t4 - the base address of A
# $t5 - two uses:
#       1) the address of A[i]
#       2) the value of A[i]
# $t6 - max (the maximum known element)
# $t7 - maxindex (the index of max)
# $t8 - flag (set to 1 if max < A[i], otherwise 0)

	.text			# Text section of the program (as opposed to data).
	.globl main		# Make MAIN globl so you can refer to it in SPIM.

main:				# Program starts at MAIN.
#
# Initialization
#
        la	$t0, N		# Set $t0 to the address of N
	lw	$t0, 0($t0)		# Set $t0 to the value of N
	li	$t1, 1		# Set $t1 to 1
	li	$t2, 0		# Set $t2 (hereafter called i) to 0
	la	$t4, A		# Set $t4 to the address of A[i]
	# $t5 is assigned in the loop before it is used
	li	$t6, -1		# Set $t6 (hereafter called max) to -1
	# $t7 and $t8 are assigned in the loop before they are used

	beq	$t0, $t2, quit   	# If N = 0, then quit
	
loop:
	beq	$t2, $t0, exit	# Continue loop if i < N. 
				

	# Load the next element
	sll	$t5, $t2, 2		# Set $t5 to i*4
	add	$t5, $t5, $t4	# Set $t5 to address of A[i]
	lw	$t5, 0($t5)		# Set $t5 to A[i]
					# This is one way to access an element of an array

	# Update max and maxindex if necessary
	slt	$t8, $t6, $t5	# Set flag to 1 if max < A[i], and 0 otherwise
	beq	$t8, $0, ok	# Skip update if flag is 0
	add	$t6, $t5, $0	# Set max to A[i]
	add	$t7, $t2, $0	# Set maxindex to i
	
ok:
	add	$t2, $t2, $t1	# Increment i
	j	loop			# Continue loop

      # Swap the last element with the largest element 
exit:
	addi    $t0, $t0, -1    # Compute N-1 and store in $t0
	sll	$t3, $t0, 2    	 # Set $t3 = (N - 1) * 4
	lw 	$t9, A($t3)     	# Load A[N-1] to $t9
				   	 # This is another way to access an element of an array

	sw	$t6, A($t3)     	# Store $t6 (largest value) to A[N-1]
   	sll	$t7, $t7, 2		# Set $t7 to $t7 * 4
	sw      $t9, A($t7)     # Store $t9 (last value) to A[maxIndex]
	
quit:
	li	$v0, 10		# Prepare to exit
	syscall			#   ... Exit.

	.data			# Data section of the program.

A:	.word 4, 5, 16, 3, 6
N:	.word 5