#
# 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