#
# Student Name:
# Student ID:
# Section:
# TA:
#

##############################################################################
#
# CS 61C, Spring 2008, Project 2, Part 1
# MIPS testing code for evaluating expression strings
#
# File Version 0.04
#
# Changes from version 0.03:
#   Fixed a bug with stack management in the "main" function. The change 
#    is below the "mn_arg_setup_end" label, and is clearly marked by comments.
#    The change is to simply move a line up by a few lines.
#
# Changes from version 0.02:
#   Declared create_tree and eval_tree to be global.
#   Changed code in main that would cause create_tree to ignore tokens if
#    the total number of tokens was less than three (this was an error).
#   Added some clarifying comments above create_tree that spell out what you 
#    can/can't change.
#
# Written by Keaton Mowery and Omar Akkawi
#
##############################################################################

# Declare the student's functions to be global. This will allow the use of a 
#  second testing file to call those functions for grading.

	.globl create_tree
	.globl eval_tree

	.data
input:	.asciiz "+ * 5 2 - 3 2" 		#Decimal only, please. Also ensure that 
		.align 2			# Ensure that the tokens are word aligned.

tokens: .space 0x400			# Enough space for 100 tokens.


	.text
# Engage!
j main

###############################################################################
# main
#  Runs the test cases and then quits.
###############################################################################
main:
	la 		$a0 input
	la		$a1 tokens
	jal 		parse_expression	# Parse the expression string into the 
						#  token format

	addu		$s0 $v0 $0		# Save the number of tokens processed

	# Uncomment these lines to print how many tokens the parse_expression 
	#  function processed
	#addi		$a0 $v0 0		# Print the number of tokens parsed
	#li		$v0 1
	#syscall

	# Prepare the arguments to create_tree
	addu		$a0 $s0 $0		# Set the token count

	# Prepare the arguments that can fit into registers. Note that we can have three 
	#  cases: 0 tokens, 1 token, or 3+ tokens.

	# NOTE: If the token count is 0, $a1-$a3 are garbage. If the token count is 1,
	#  then $a2-$a3 are garbage.

	# If the token count is 0, we don't need to do anything else
	beq		$a0 $0 mn_arg_setup_end

	sltiu		$t1 $a0 2		# Check for only one token.
	beq		$t1 $0 mn_enough_tokens

	# Handle the case of only one token. Note that we would hit this code 
	#  if the token count was two, but that would mean that the input string 
	#  was invalid, and we will not have to deal with invalid input strings, 
	#  so we won't handle it here.
	la		$t0 tokens		# Load the one token into the register
	lw		$a1 0($t0)

	j		mn_arg_setup_end

mn_enough_tokens:
	la		$t0 tokens		# Load the first three tokens into the 
	lw		$a1 0($t0)		#  argument registers
	lw		$a2 4($t0)
	lw		$a3 8($t0)

	addiu		$t0 $t0 12		# Set $t0 to point to the next token
	addiu		$t1 $s0 -3		# Set $t1 to be a count of the remaining 
						#  tokens

	sll		$t2 $t1 2		# Set $t2 to be the number of bytes needed 
						#  on the stack
	addu		$s1 $t2 $0		# Save the size of the stack frame

	not		$t2 $t2		# Negate the size of the stack frame so that
	addiu		$t2 $t2 1		#  we can use it to change the $sp

	addu		$sp $sp $t2		# Create the stack frame

	addu		$t3 $sp $0		# Set $t3 to point to the destination

mn_arg_setup_loop:
	slti		$t5 $t1 1		# If there are zero remaining tokens, end 
	beq		$t5 $0 mp_continue_loop	#  the loop

	j 		mn_arg_setup_end

mp_continue_loop:
	lw		$t4 0($t0)		# Load the next token
	sw		$t4 0($t3)		# Store the token on the stack

	addiu		$t3 $t3 4		# Advance the destination
	addiu		$t0 $t0 4		# Advance the source

	addiu		$t1 $t1 -1		# Decrement the remaining tokens
	
	j		mn_arg_setup_loop

mn_arg_setup_end:

	jal		create_tree		# Call your function to create the expression tree

	# CHANGE: Version 0.04 - The line directly below this comment moved up to this 
	#  position.
	addu		$sp $sp $s1		# Clear the reserved stack space for extra args

	addu		$a0 $v0 $0		# Prepare to call eval_tree on the created tree

	jal		eval_tree		# Evaluate the value of the expression tree

	# Print the result
	# NOTE: Until you put something in the create_tree and eval_tree functions, 
	#  this will just print the return value from parse_expression
	addu		$a0 $v0 $0		# Set the value to print
	li		$v0 1			# Set the syscal function to print an int
	syscall

	#addu		$sp $sp $s1		# THIS LINE MOVED ABOVE File Version 0.04
	
	li 		$v0, 10		# exit
	syscall



###############################################################################
# atoi_dec
# Return values:
# v0: value of number
# v1: pointer to the end of the number
###############################################################################
atoi_dec:
	addi 		$v0 $0 0
	addi		$t7 $0 10

  atoi_digit:
	lbu		$t0	0($a0)	# load the byte
	addi		$t0 $t0 -48 	# t -= '0'

	slti 		$t1 $t0 0		# probably should use is_digit here, but this is 
	slti 		$t2 $t0 10 		#   already written and works...
	xor		$t3 $t1 $t2		# ensure that the number is >= 0 _and_ <10
	beq		$t3 $0 atoi_end
	
	mul 		$v0	$v0	$t7
	add		$v0 $v0 $t0

	addi		$a0 $a0 1		# increment the pointer
	j 		atoi_digit

  atoi_end:
	addi 		$v1 $a0 0
	jr 		$ra


###############################################################################
# is_digit
# returns 1 in $v0 if the character in $a0 is an ASCII digit, 0 if not.
###############################################################################
is_digit:
	addi		$a0 $a0 -48 	# t -= '0'

	slti 		$t0 $a0 0
	slti 		$t1 $a0 10 
	xor		$v0 $t0 $t1		# ensure that the number is >= 0 _and_ <10

	jr 		$ra


###############################################################################
# parse_expression
# parses a simple space-delimited math expression into project format.
# Arguments: $a0 - char* - string to parse.  Does not have to be word aligned.
#			$a1 - void* - buffer in which to store tokens in project format.  
#							Must be word aligned.
# Returns: $v0 - number of written tokens
# TODO: Check that non-digits are valid mathematical symbols (+, -, *, /, &, |)
#		Actually write out project format.
# Notes: This will _not_ check that the string is properly formatted (i.e.
#			a binary-operator math expression in prefix format).
###############################################################################
parse_expression:
	addi		$sp $sp -20
	sw		$ra 4($sp)
	sw		$s0 8($sp)
	sw		$s1 12($sp)
	sw		$s2 16($sp)
	# Reserving 0($sp) for scratch space...

	addi		$s0	$a0 0			# Save the string pointer
	addi		$s1 	$a1 0			# Save the output pointer
	add		$s2	$0 $0			# initialize counter

  pe_loop:
	lbu 		$t0 0($s0)			#load the next character
	beq		$t0 $0 pe_loop_end	# quit when we see '\0'

	#skip any spaces
	li		$t7, ' '
	bne		$t0 $t7 pe_no_spaces	# if char != ' ', keep going
	addi		$s0 $s0 1			# otherwise, increment $s0 and retry

	j 		pe_loop

  pe_no_spaces:
	sw		$t0 0($sp)			# save this character for later
	addi		$a0 $t0 0			# if ( isdigit(char) )
	jal 		is_digit

	beq		$v0 $0 pe_nondigit
  
  pe_digit:
	addi		$a0 $s0 0
	jal 		atoi_dec			# convert to decimal
	andi		$v0 $v0 0x00ffffff	# take out higher order bits
	addi		$s0 $v1 0			# $s0 = new position in string
	j		pe_loop_cleanup
  
  pe_nondigit:
	lw		$t0 0($sp)			# reload the character

	li		$t1 '-'			# Check if the character is a minus sign
	bne		$t0 $t1 pe_nonminus

  pe_minussign:
	# If this is a minus sign, then we need see if it is a number, or a subtraction 
	#  operator. If it is a number then call atoi on the number, then negate it. 
	#  Otherwise create the operation token.
	lbu		$t0 1($s0)
	addi		$a0 $t0 0			# if ( isdigit(char) )
	jal 		is_digit

	beq		$v0 $0 pe_nonminus	# If the character after the minus sign is
							#  not a digit, then we treat the minus 
							#  sign as an operator

	# The following character was a digit, so get the number and negate it
      addi		$a0 $s0 1			# Call atoi starting at the next character
      jal		atoi_dec
	
	not		$v0 $v0			# Take the two's complement of the number
	addiu		$v0 $v0 1

	andi		$v0 $v0 0x00ffffff	# Take out the higher order bits
	addi		$s0 $v1 0			# $s0 = new position in string
	j		pe_loop_cleanup

  pe_nonminus:
	lw		$t0 0($sp)			# reload the character
	sll		$v0 $t0 24			# move the operator into the higher order bits
	addi		$s0 $s0 1			# increment position in string

  pe_loop_cleanup:
	addi		$s2	$s2 1			# increment counter
	sw		$v0 0($s1)			# save to buffer
	addi		$s1 $s1 4			# increment buffer counter

	#addi		$a0 $v0 0			# print the result
	#li		$v0 1				# TODO: put in result buffer
	#syscall
	#li		$a0,'\n'
	#li		$v0,11
	#syscall

	j 		pe_loop

 pe_loop_end:
	addi		$v0 $s2 0

	lw		$s2 16($sp)
	lw		$s1 12($sp)
	lw 		$s0 8($sp)
	lw		$ra 4($sp)
	addi		$sp $sp 20
	jr 		$ra


###############################################################################
#
# Write the functions below! You may write as many helper functions as you 
#  need, but eval_tree MUST be recursive. You should not create any global 
#  variables, change anything above this portion of the file, or add anything 
#  that is not called (directly or indirectly) by create_tree or eval_tree.
#
###############################################################################

###############################################################################
# create_tree:
#   Takes all of the tokens and creates an expression tree.
# arguments:
#   $a0 - The count of tokens. Can be zero.
#   $a1 - The first token (optional).
#   $a2 - The second token (optional).
#   $a3 - The third token (optional).
#   0($sp)-x($sp) - The remaining tokens, in order starting at 0($sp) and in
#                    increasing values of x.
# return values:
#   $v0 - The address of the root node. Should be NULL (zero) if $a0 contains
#          zero.
###############################################################################
create_tree:

	jr		$ra


###############################################################################
# eval_tree:
#   Takes in a pointer to an expression tree and recursively calculates the
#    value of the expression.
# arguments:
#   $a0 - The address of the root node of a valid expression tree.
# return values:
#   $v0 - The 32-bit two's complement signed integer resulting from performing 
#          all of the computations. Should be zero if $a0 is NULL (zero).
###############################################################################
eval_tree:

	jr		$ra