####################################
# CSE 341 Project 1
# Scott Laufer
# Fall 2013

# BUGS/ISSUES
#
# - bug:	string entry ignores unwanted chars without error, will accept - (negative) anywhere in number, except as the last char in the string.
#   fix:	about a billion lines of string parsing code, low priority
#
# - bug:	mean is incorrect if the sum of the array is greater than 2^32
#   fix:	writing multi-word integer arithmetic procedures, or using the FPU (using the FPU to do a continuous mean is the only long-term solution)
#
# - bug:	store/save locations should be passed as arguments, not assumed to be constant
#   fix:	reorganize procedure calls
#
# - bug:	if the user just presses "enter" when prompted for a string, this will convert to an array containing only "0"
#   fix:    also a billion lines of string parsing code, low priority


.globl endbrk

.data
	.asciiz " r " # 0x10000000 (len 2)
	.asciiz ", " # 0x10000004 (len 2)
	.asciiz "\n" # 0x10000007 (len 2)
	# 0x10000009
	.asciiz "1. Enter a New String\n2. Convert\n3. Mean\n4. Median\n5. Display String\n6. Display Array\n7. Exit\n\nEnter a menu number and press <return>: "
	# 0x10000091
	.asciiz "Enter comma-separated integers (max. 255 chars): "
	# 0x100000C3
	.asciiz "Saved string: "
	# 0x100000D2
	.asciiz "Saved array: "
	# 0x100000E0
	.asciiz "Median: "
	# 0x100000E9
	.asciiz "Mean: "

	.word 0
	.space 0xFC
	.word 0
	.space 0xFC

.text

main:
	add $s7, $0, $0 # using $s7 as a constant 0x10000000
	lui $s7, 0x1000 # this eliminates a lot of uses of lui

	menu_start:	
	addi $v0, $0, 4 # set syscall 4 (print_string)
	addi $a0, $s7, 0x9 # set string ptr to menu string 0x10000009
	syscall # print menu
	
	addi $v0, $0, 5 # set syscall 5 (read_int)
	syscall # read menu selection
	add $s1, $v0, $0 # copy menu selection into saved register

	# make sure the user's entry isn't negative
	sll $s1, $s1, 1 # shift off MSB (sign bit)
	srl $s1, $s1, 1 # shift back into place
	
	addi $s1, $s1, -2 # decrement menu input
	
	bltzal $s1, read_string  # if selection < 0 now, it was 1 
	or $0, $0, $0
	bltz $s1, menu_start # return to menu
	addi $s1, $s1, -1 # decrement menu input
	
	bltzal $s1, convert # user entered 2
	or $0, $0, $0
	bltz $s1, menu_start # return to menu
	addi $s1, $s1, -1 # decrement menu input

	bltzal $s1, mean # user entered 3
	or $0, $0, $0
	bltz $s1, menu_start # return to menu
	addi $s1, $s1, -1 # decrement menu input

	bltzal $s1, median # user entered 4
	or $0, $0, $0
	bltz $s1, menu_start # return to menu
	addi $s1, $s1, -1 # decrement menu input
	
	bltzal $s1, display_string # user entered 5
	or $0, $0, $0
	bltz $s1, menu_start # return to menu
	addi $s1, $s1, -1 # decrement menu input

	bltzal $s1, display_array # user entered 6
	or $0, $0, $0
	bltz $s1, menu_start # return to menu
	addi $s1, $s1, -1 # decrement menu input

	bltz $s1, endbrk # user entered 7
	or $0, $0, $0
	
	j menu_start # user entered something invalid

	endbrk:
	addi $v0, $0, 10 # ready up for exit
	syscall # end of the program

	jr $ra
	or $0, $0, $0

####################
# read input string
read_string:
	addi $v0, $0, 4 # set syscall 4 print_string
	addi $a0, $s7, 0x91 # set string ptr to 0x10000090
	syscall # print prompt string

	addi $v0, $0, 8 # set syscall 8 read_string
	addi $a0, $s7, 0x100 # set buffer to 0x10000100
	addi $a1, $0, 0x100 # set len to 0x100 (256)
	syscall # read input string
	
	jr $ra
	or $0, $0, $0

#############	
# convert
convert:
	#######################################
	# convert ascii string to integer array

	add $t0, $s7, 0x0FF # set $t0 to input ptr - 1 (because it's incremented at the start of the loop to avoid unnecessary jumps)
	add $t1, $s7, 0x202 # set $t1 to output ptr
	add $t5, $0, $0 # $t5 counts how many numbers we've parsed

	convert0: # jump here when we're starting a new number
	add $t2, $0, $0 # $t2 is current number
	add $t6, $0, $0 # $t6 is the negative flag

	convert1: # jump here if we're starting a new char, but not a new number
		lb $t3, 1($t0) # load next char into $t3
		addi $t0, $t0, 1 # increment input ptr (lds)

		slti $t4, $t3, 48 # if $t3 is less than 48 it's not an ascii number
		bne $t4, $0, convert2 # so jump past the number mangling section
		slti $t4, $t3, 58 # now, if $t3 isn't less than 58 (lds)
		beq $t4, $t3, convert2 # it's not a number, so jump 
			
			# multiply t2 by 10 using shifts
			add $t4, $t2, $0 # copy t2 into t4 (lds)
			sll $t2, $t2, 3 # shift left 3 to mult by 8
			add $t2, $t2, $t4 # add old value (t4) twice
			add $t2, $t2, $t4

			addi $t3, $t3, -48 # subtract 48 to turn char into integer
			add $t2, $t2, $t3 # add new digit to number
			
			j convert1 # done with this char, jump to next iteration
			or $0, $0, $0

		convert2:
		add $t4, $0, 44 # ascii comma
		bne $t3, $t4, convert3 # jump if this isn't an ascii commma
		or $0, $0, $0
			beq $t6, $0, convert7 # branch if the negative flag isn't set
			addi $t5, $t5, 1 # increment counter
				sub $t2, $0, $t2 # do arithmetic negation on number (x = 0 - x)
			convert7:

			sh $t2, ($t1) # comma means this number is finished, so store it
			addi $t1, $t1, 2 # increment output ptr
			j convert0 # done with this char and this number, jump to next iteration
			or $0, $0, $0

		convert3:
		bne $t3, $0, convert4 # jump if this isn't a null terminator
		or $0, $0, $0
			# the following lines are duplicate code from the prior section; unfortunately this is the least ugly way to do this
			beq $t6, $0, convert14 # branch if the negative flag isn't set
			addi $t5, $t5, 1 # increment counter
				sub $t2, $0, $t2 # do arithmetic negation on number (x = 0 - x)
			convert14:

			sh $t2, ($t1) # null terminator means this number is finished, so store it
			j convert6 # done parsing string, jump out of loop

		convert4:
		add $t4, $0, 45 # ascii minus (lds)
		bne $t3, $t4, convert5 # jump if this isn't an ascii minus
		or $0, $0, $0
			addi $t6, $0, 1 # this is negative, set the negative flag
			j convert1 # done with this char, jump to next iteration

		convert5:

	j convert1
	or $0, $0, $0

	convert6:


	slti $t4, $t5, 2 # check to see if the array count is at least 2
	bne $t4, $0, convert13 # if not, we can jump to the end right now

	#############
	# sort values

	# $t5 = current array count
	# $t1 = ptr to last array value (array top ptr)

	addi $t0, $s7, 0x202 # $t0 is array bottom ptr
	add $t6, $t1, $0 # make a copy of array top ptr, so we can use it later

	convert8: # two labels here to make the loops more coherent
		convert9:
			lh $t2, ($t0) # load value under bottom ptr into $t2
			lh $t3, 2($t0) # load next value above bottom ptr into $t3
			or $0, $0, $0 # (lds)

			slt $t4, $t3, $t2 # see if the values are out of order, store result in $t4
			beq $t4, $0, convert10 # skip swap step if they are in order
			or $0, $0, $0 # (lds)
				sh $t2, 2($t0) # store values in opposite locations
				sh $t3, ($t0) # " "
			convert10:
			
			addi $t0, $t0, 2 # increment bottom ptr
		bne $t0, $t1, convert9 # if ptrs haven't collided at the top, continue inner loop
		or $0, $0, $0

		addi $t0, $s7, 0x202 # reset bottom ptr
		addi $t1, $t1, -2 # decrement top ptr
	bne $t0, $t1, convert8 # if ptrs haven't collided at the bottom, continue outer loop
	or $0, $0, $0
	

	######################
	# eliminate duplicates

	# $t5 = array count
	# $t6 = array top ptr

	addi $t0, $s7, 0x204 # $t0 is array dest ptr (inc at start of loop)
	addi $t1, $s7, 0x204 # $t1 is array src ptr (inc at start of loop)
	addi $t6, $t6, 2 # $t6 is now array bound ptr (last element + 2)

	lh $t2, -2($t0) # $t2 is previous value

	convert11:
		lh $t3, ($t1) # load current value from src ptr
		addi $t1, $t1, 2 # increment src ptr (lds)

		beq $t2, $t3, convert12 # don't copy if current value = previous value
		or $0, $0, $0           # if ($t2 == $t3) continue;
		
		# TODO: check if src and dest are the same before copying?
		# may not be worthwhile, since just one duplicate renders this comparison redundant
		# although this could be avoided after one cycle at the cost of code size by jumping
		# into a different loop. probably not worthwhile at this sample size
		sh $t3, ($t0) # copy current value to dest ptr - 2
		addi $t0, $t0, 2 # increment dest ptr
		addi $t2, $t3, 0 # move current value into previous value

		convert12:		
	bne $t1, $t6, convert11 # continue loop if that wasn't the last slot
	or $0, $0, $0

	# calculate new array count
	sub $t1, $t1, $t0 # subtract dest ptr from src ptr
	srl $t1, $t1, 1 # shift value right (this is now the number of deleted values)
	sub $t5, $t5, $t1 # subtract this from previous count

	convert13:

	# store array count
	addi $t2, $s7, 0x200 # create ptr to array start
	sh $t5, ($t2) # write count to temp array

	jr $ra
	or $0, $0, $0
	
############
# mean

mean:
	addi $sp, $sp, -4 # decrement stack ptr
	sw $ra, ($sp) # store return address

	lh $t0, 0x200($s7) # load array count

	add $a0, $0, $0 # $a0 is array sum
	add $a1, $0, $t0 # copy array count into $a1
	add $t1, $s7, 0x202 # create array ptr

	mean1:
	beq $t0, $0, mean2 # don't loop if count has reached zero
		addi $t0, $t0, -1 # decrement count (lds)
		lh $t2, ($t1) # load current value into $t2
		addi $t1, $t1, 2 # increment array ptr (lds)

		add $a0, $a0, $t2 # add current value into sum
		
	j mean1 # jump to start of loop
	or $0, $0, $0

	mean2:

	jal spdiv # call pdiv ($a0 = dividend, $a1 = divisor, $v0 = quotient)
	or $0, $0, $0

	# copy results so we can change $v0 for syscalls
	add $t0, $v0, $0

	addi $v0, $0, 4 # load print_string syscall
	addi $a0, $s7, 0xE9 # load median label string address
	syscall # print string

	add $a0, $t0, $0
	addi $v0, $0, 1 # load print_int syscall
	syscall # print this value

	addi $v0, $0, 4 # load print_string syscall
	addi $a0, $s7, 0x7 # load newline string ptr
	syscall # print newline

	lw $ra, ($sp) # load return address
	addi $sp, $sp, 4 # increment stack ptr

	jr $ra
	or $0, $0, $0
	
###########
# median
median:
	lh $t0, 0x200($s7) # load array count

	addi $v0, $0, 4 # load print_string syscall (lds)
	addi $a0, $s7, 0xE0 # load median label string address
	syscall # print string

	# next 3 lines: subtract 1 if count is odd, subtract 2 if count is even
	addi $t0, $t0, -1 
	srl $t0, $t0, 1
	sll $t0, $t0, 1
	add $t0, $t0, $s7 # add upper half of heap address
	addi $t0, $t0, 0x202 # add array offset within heap

	lh $a0, ($t0) # load median into $a0
	addi $v0, $0, 1 # load print_int syscall
	syscall # print number
	
	addi $v0, $0, 4 # load print_string syscall
	addi $a0, $s7, 0x7 # load newline string address
	syscall # print string

	jr $ra
	or $0, $0, $0

#################
# display_string

display_string:
	addi $v0, $0, 4 # load print_string syscall
	
	addi $a0, $s7, 0xC3 # load output label string ptr 0x100000C3
	syscall # print string
	
	addi $a0, $s7, 0x100 # load input string ptr 0x10000100
	syscall # print string
	
	addi $a0, $s7, 0x7 # load newline string ptr 0x10000007
	syscall # print string

	jr $ra
	or $0, $0, $0

####################
# display_array

display_array:

	addi $v0, $0, 4 # load print_string syscall
	add $a0, $s7, 0xD2 # set label string ptr 0x100000DA
	syscall # print prompt

	lh $t1, 0x200($s7) # load array count 
	addi $t0, $s7, 0x202 # set array ptr (lds)

	beq $t1, $0, display_array2 # jump to the end if count is 0

	display_array1:
		lh $a0, ($t0) # load next array element
		addi $v0, $0, 1 # load print_int syscall (lds)
		syscall # print array element
		
		addi $a0, $s7, 0x4 # load comma string ptr 0x10000004
		addi $v0, $0, 4 # load print_string syscall
		syscall # print string

		addi $t0, $t0, 2 # increment array ptr
		addi $t1, $t1, -1 # decrement array count

	bne $t1, $0, display_array1 # keep going if we still have elements to print

	display_array2:

	addi $v0, $0, 4
	addi $a0, $s7, 0x7 # load newline string ptr (lds)
	syscall # print newline

	jr $ra
	or $0, $0, $0

################
# spdiv - a signed wrapper for pdiv
# THIS WRAPPER ROUNDS THE QUOTIENT AND DISCARDS THE REMAINDER
# if you do not want to round, use ipdiv (which i probably didn't
# include in this file)

spdiv:
	addi $sp, $sp, -12 # decrement stack counter
	sw $ra, -8($sp) # store return address in stack
	sw $s0, -4($sp) # store $s0 in stack
	sw $s1, ($sp) # store $s1 in stack

	add $t0, $0, 1 # set $t0 to 1
	sll $t0, $t0, 31 # shift over so only MSB is set

	and $s0, $t0, $a0 # see if MSB is set in dividend $a0
	beq $s0, $0, spdiv1 # branch if MSB (sign bit) wasn't set in dividend
	or $0, $0, $0
		sub $a0, $0, $a0 # negate dividend $a0
	spdiv1:

	and $s1, $t0, $a1 # see if MSB (sign bit) is set in divisor $a1
	beq $s1, $0, spdiv2 # branch if MSB (sign bit) wasn't set in divisor
	or $0, $0, $0
		sub $a1, $0, $a1 # negate divisor $a1
	spdiv2:

	jal pdiv # call pdiv
	or $0, $0, $0

	sll $v1, $v1, 1	# multiply remainder by 2
	slt $t0, $v1, $a1 # see if 2 * remainder >= divisor
	bne $t0, $0, spdiv6 # branch if it isn't
	or $0, $0, $0
		addi $v0, $v0, 1 # round quotient up
	spdiv6:

		
	beq $s0, $0, spdiv4 # branch if MSB (sign bit) wasn't set in dividend
	or $0, $0, $0
		sub $a0, $0, $a0 # negate dividend $a0
	spdiv4:

	beq $s1, $0, spdiv5 # branch if MSB (sign bit) wasn't set in divisor
	or $0, $0, $0
		sub $a1, $0, $a1 # negate divisor $a1
	spdiv5:

	beq $s0, $s1, spdiv3 # see if divisor and dividend had the same sign
	or $0, $0, $0
		sub $v0, $0, $v0 # if not, negate the quotient
	spdiv3:

	lw $s1, ($sp) # load $s1 from stack
	lw $s0, -4($sp) # load $s0 from stack
	lw $ra, -8($sp) # load return address from stack
	addi $sp, $sp, 12 # increment stack counter

	jr $ra
	or $0, $0, $0


################################################################
# pdiv: an unsigned division procedure
# TODO: - write a wrapper for signed division
#       - change MSB scan into a binary search
# WARNING: returns without doing anything if you attempt to
# divide by zero
# mangles $v0, $v1, $t0, $t1, $t2
# input: $a0 as dividend, $a1 as divisor
# output: $v0 as quotient, $v1 as remainde

pdiv:
	add $v0, $0, $0 # clear output registers
	add $v1, $0, $0

	beq $a1, $0, pdiv2 # make sure divisor isn't 0
	or $0, $0, $0

	slt $t1, $a0, $a1 # check to see if dividend < divisor
	beq $t1, $0, pdiv1 # run this only if dividend < divisor
	or $0, $0, $0
		add $v0, $0, $0 # zero out quotient
		add $v1, $a0, $0 # copy dividend to remainder
		j pdiv2 # jump to end of procedure
		or $0, $0, $0
	pdiv1:

	add $t0, $0, 0x1 # set up bit mask

	add $t2, $0, $0 # zero out dividend high bit counter
	add $t3, $0, $0 # zero out divisor high bit counter
	addi $t4, $0, 1 # cycle counter

	pdiv3: # begin hi bit scan loop
		and $t1, $t0, $a0 # see if this bit is set in dividend
		beq $t1, $0, pdiv4 # run this clause only if bit is set
		or $0, $0, $0
			add $t2, $t4, $0 # update dividend high bit
		pdiv4:
		
		and $t1, $t0, $a1 # see if this bit is set in divisor
		beq $t1, $0, pdiv5 # run this clause only if bit is set
		or $0, $0, $0
			add $t3, $t4, $0 # update divisor high bit
		pdiv5:

		addi $t4, $t4, 1 # increment cycle counter
		sll $t0, $t0, 1 # shift bit mask left
	bne $0, $t0, pdiv3 # loop until mask zeroes out
	or $0, $0, $0

	sub $t1, $t2, $t3 # find the difference between hi bit positions

	###########################################
	# shift the divisor over and start dividing

	addi $t0, $0, 1 # create bit mask
	sllv $t0, $t0, $t1 # shift bit mask over to match dividend
	
	add $t2, $a0, $0 # copy dividend into $t2
	add $t3, $a1, $0 # copy divisor into $t3
	sllv $t3, $t3, $t1 # shift divisor over to match dividend

	pdiv6:
		sltu $t1, $t2, $t3 # check if cur. dividend < cur. divisor
		bne $t1, $0, pdiv7 # run this clause only if cur. dividend >= cur. divisor
		or $0, $0, $0
			sub $t2, $t2, $t3 # subtract divisor from dividend
			or $v0, $v0, $t0 # set relevant bit in quotient
		pdiv7: 


		srl $t0, $t0, 1 # shift bit mask right
		srl $t3, $t3, 1 # shift bit mask right
	bne $0, $t0, pdiv6 # loop until mask zeroes out
	or $0, $0, $0

	add $v1, $t2, $0 # copy remaining dividend into the remainder

	pdiv2:
	jr $ra # return to caller
	or $0, $0, $0