#
# This program satisfies the problem specification for homework assignment 4.
# It differs from the C example program, in that it does not generate any
# error messages when given illegal characters etc; the program just returns.
# 
# The code which does value input (getnum in the C example) has been inlined
# into the main procedure.  Because the input/output base number entry is
# always done in base 10, these were done using the read_int syscall directly
# instead of via a call to getnum.  Thus, there were only one call to getnum,
# making it an obvious target for inlining (no code-size vs run-time tradeoff).
#
# The putnum function remains recursive.  It is coded in the straightforward
# stack-frame-building style.  Because it does not call any external
# functions, this code can be optimized to use a simpler frame representation.
#
		.data
pibase:		.asciiz	"input base: "
pvalue:		.asciiz "value: "
opb10:		.asciiz "value in base 10: "
pobase:		.asciiz "output base: "
opval:		.asciiz "value in that base: "
buf:		.space	34	# max length needed, base 2, 32 characters
				# plus newline and null termination

		.text
main:		sub $sp,$sp,8
		sw $fp,4($sp)
		add $fp,$sp,8
		sw $ra,0($fp)
		# Local variables base and value are not on the stack frame,
		# since we can keep them in registers.
again:		# prompt for input base
		la $a0,pibase
		li $v0,4
		syscall
		li $v0,5
		syscall
		bltu $v0,2,quit
		move $s0,$v0		# base in $s0
		# prompt for value
		la $a0,pvalue
		li $v0,4
		syscall
		la $a0,buf
		li $a1,34
		li $v0,8
		syscall
		li $s1,0		# s1 is running value
		la $t0,buf
# Let n be the input number in base b, where
#	n = sum_{i=0}{k} a_i b^i
# we read in one digit at a time (a_j), and what we
# compute is the sequence of values:
#  n_0 = a_k
#  n_1 = n_0 b + a_{k-1} = a_k b + a_{k-1}
#  n_2 = n_1 b + a_{k-2} = a_k b^2 + a_{k-1} b + a_{k-2}
#   ...
#  n_k = n_{k-1} b + a_0 = n.
#
decode:		lb $t1,0($t0)		# walk through string
		add $t0,$t0,1
		beq $t1,0,decode_done
		beq $t1,0xa,decode_done
		blt $t1,0x30,not_digit
		bgt $t1,0x39,not_digit
		#
		# The conversion from ascii character to digit
		# values may be made faster by using a table
		# lookup as well, at the expense of a little
		# more memory (256 bytes).
		#
		sub $t1,$t1,0x30	# $t1 has digit value
		j got_new_digit
not_digit:	blt $t1,0x41,not_cap
		bgt $t1,0x5a,not_cap
		sub $t1,$t1,0x37	# -0x41+a = -0x37
		j got_new_digit
not_cap:	blt $t1,0x61,quit
		bgt $t1,0x7a,quit
		sub $t1,$t1,0x57	# -0x51+a = -0x47
got_new_digit:	bge $t1,$s0,quit
		mul $s1,$s1,$s0
		add $s1,$s1,$t1
		j decode
decode_done:	la $a0,opb10
		li $v0,4
		syscall
		move $a0,$s1
		li $a1,10
		jal putnum
		jal newline
		la $a0,pobase		# prompt for output base
		li $v0,4
		syscall
		li $v0,5
		syscall
		bltu $v0,2,quit
		move $s2,$v0		# $s2 has obase
		la $a0,pvalue
		li $v0,4
		syscall
		move $a0,$s1		# value in $a0
		move $a1,$s2		# obase in $a1
		jal putnum
		jal newline
		j again
quit:		lw $ra,0($fp)
		lw $fp,4($sp)
		add $sp,$sp,8
		li $v0,0		# main returns 0 as exit status
		jr $ra

		.data
nl:		.asciiz "\n"
		.text
newline:	la $a0,nl
		li $v0,4
		syscall
		jr $ra

#
# recursive putnum.  Input $a0 is the value, $a1 is the base.
# output is the digit string in base $a1 of the value $a0.
#
# base case: it works for $a0 < $a1.
#  divu $a0,$a1 gives $lo == 0 when $a0 < $a1, so we branch to no_recurse.
#  output is by table lookup, so the output is the correct digit string.
# inductive step:  assume it works for $a0 < $a1^k
#  we prove that it works for $a1^k <= $a0 < $a1^{k+1}
#  with $a0 in that range, the divu $a0,$a1 gives d_0 in $hi, where
#  $a0 = sum_{i=0}^{k} d_i $a1^i, and gives floor($a0/$a1) in $lo.
#  $lo = sum_{i=0}{k-1} d_{i+1} $a1^i, so it is less than $a1^k,
#  and we can recursively output the digits d_{k}...d_1 using a recursive
#  call to putnum, with $lo as the new $a0, and we need only output the
#  remainder $hi as before to complete the output digit sequence.
#
putnum:		sub $sp,$sp,12
		sw $fp,4($sp)
		add $fp,$sp,12
		sw $ra,0($fp)

		divu $a0,$a1
		mflo $t0		# result of division
		mfhi $t1		# remainder
		beq $t0,$zero,no_recurse
		sw $t1,-4($fp)		# save remainder on stack frame

		move $a0,$t0
		jal putnum		# call putnum(floor($a0/$a1),$a1)

		lw $t1,-4($fp)
		.data
digit_table:	.ascii "0123456789abcdefghijklmnopqrstuvwxyz"
dbuf:		.asciiz "1"
		.text
no_recurse:	lb $t1,digit_table($t1)	# simple table lookup for digit
		sb $t1,dbuf

		la $a0,dbuf		# output the digit
		li $v0,4
		syscall

		lw $ra,0($fp)
		lw $fp,4($sp)
		add $sp,$sp,12
		jr $ra
