#
# 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).
#
# 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:	lbu $t0,0($a1)		# lbu needed, since otherwise
					# we might fall off the front of
					# the decode table
		add $a1,$a1,1		# walk through string

		.data
decode_tbl:	.byte	0xfe,0xff,0xff,0xff,0xff,0xff,0xff,0xff, # nul - bel
		.byte	0xff,0xff,0xfe,0xff,0xff,0xff,0xff,0xff, # bs - si
		.byte	0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff, # dle - etb
		.byte	0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff, # can - us

		.byte	0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff, # sp - '
		.byte	0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff, # ( - /
		.byte	 0x0, 0x1, 0x2, 0x3, 0x4, 0x5, 0x6, 0x7, # 0 - 7
		.byte	 0x8, 0x9,0xff,0xff,0xff,0xff,0xff,0xff, # 8 - ?

		.byte	0xff, 0xa, 0xb, 0xc, 0xd, 0xe, 0xf,0x10, # @ - F
		.byte	0x11,0x12,0x13,0x14,0x15,0x16,0x17,0x18, # G - O
		.byte	0x19,0x1a,0x1b,0x1c,0x1d,0x1e,0x1f,0x20, # P - W
		.byte	0x21,0x22,0x23,0xff,0xff,0xff,0xff,0xff, # X - _

		.byte	0xff, 0xa, 0xb, 0xc, 0xd, 0xe, 0xf,0x10, # ` - f
		.byte	0x11,0x12,0x13,0x14,0x15,0x16,0x17,0x18, # g - o
		.byte	0x19,0x1a,0x1b,0x1c,0x1d,0x1e,0x1f,0x20, # p - w
		.byte	0x21,0x22,0x23,0xff,0xff,0xff,0xff,0xff, # x - del

		.byte	0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff, # 
		.byte	0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff, # 
		.byte	0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff, # 
		.byte	0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff, # 

		.byte	0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff, # 
		.byte	0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff, # 
		.byte	0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff, # 
		.byte	0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff, # 

		.byte	0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff, # 
		.byte	0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff, # 
		.byte	0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff, # 
		.byte	0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff, # 

		.byte	0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff, # 
		.byte	0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff, # 
		.byte	0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff, # 
		.byte	0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff, # 

		.text

		lb $t0,decode_tbl($t0)
		beq $t0,-2,decode_done

		bgeu $t0,$a0,decode_quit	# -1 as unsigned is UINT_MAX.
		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
