#
# 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 getnum function uses the polynomial evaluation algorithm to convert
# a string of digits into a number.
#
# 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

		li $a0,10
		jal getnum

		bltu $v0,2,quit
		move $s0,$v0		# base in $s0
		# prompt for value
		la $a0,pvalue
		li $v0,4
		syscall

		move $a0,$s0
		jal getnum

		bltz $v0,quit
		move $s1,$v0

		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
		li $a0,10
		jal getnum

		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

#
# getnum:  read in a string of digits and decode as a particular base.
#
# scratch register used: $t0, $t1
#
# This relies on decode not disturbing $t1.
#

getnum:		move $t1,$ra
		move $t0,$a0
		la $a0,buf
		li $a1,34
		li $v0,8
		syscall
		move $a0,$t0	# $t0 is no longer live at this point,
				# so decode may trash it.
		la $a1,buf
		jal decode
		jr $t1

#
# decode a string of digits (at some base $a0) into
# a number (in $v0).
#
# Empty string is decoded as zero.  Illegal characters cause
# the value -1 to be returned.
#
# This is a leaf function, and so we do not set up
# a stack frame.
#
# scratch register used: $t0.
#
#
# Algorithm:
#
# 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.
#
# So, we initialize $v0 with 0, and whenever we get
# a new a_i, we set $v0 = $v0 * b + a_i.  When we are done,
# we return $v0.
#

decode:		li $v0,0		# v0 is running value
decode_nxt:	lb $t0,0($a1)		# walk through string
		add $a1,$a1,1
		beq $t0,0,decode_done
		beq $t0,0xa,decode_done
		blt $t0,0x30,not_digit
		bgt $t0,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 $t0,$t0,0x30	# $t0 has digit value
		j got_new_digit
not_digit:	blt $t0,0x41,not_cap
		bgt $t0,0x5a,not_cap
		sub $t0,$t0,0x37	# -0x41+a = -0x37
		j got_new_digit
not_cap:	blt $t0,0x61,decode_quit
		bgt $t0,0x7a,decode_quit
		sub $t0,$t0,0x57	# -0x51+a = -0x47
got_new_digit:	bge $t0,$a0,decode_quit
		mul $v0,$v0,$a0
		add $v0,$v0,$t0
		j decode_nxt
decode_quit:	li $v0,-1
decode_done:	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