#
# RPN Calculator.  bsy@play, 10/97.  Took about 45 minutes to type in
# and debug.  Another 20 minutes to add comments.
#
# The specifications ask for a 4-deep stack RPN calculator which
# implements: +, -, *, /, ^ binary operators, b (set-base), p (print
# top of stack), a (print all of stack) commands, with functions for
# each of these calculator operations.  The set-base operation
# consumes the top of the stack, setting the current input/output base
# for all numbers.  If [xyzw] is the stack, with x being the top
# element, then the results of the operations are defined as:
#
#	+  [(y+x)zww]
#	-  [(y-x)zww]
#	*  [(y*x)zww]
#	/  [(y/x)zww]
#	^  [(y^x)zww]
#	b  [yzww]
#	A valid number entry (call it n) causes the stack to become [nxyz]
#
# Invalid digit(s) for the current base causes an error message.
# Division by zero causes an error message.  Raising to a negative
# exponent causes an error message.
#
# The equivalent C code is:
#
# main()
# {
#	int	base = 10, s0 = 0, s1 = 0, s2 = 0, s3 = 0, val, v0;
#
#	for (;;) {
#		read_str(buf,34);
#		if (('0' <= buf[0] && buf[0] <= '9') ||
#		     'A' <= buf[0] && buf[0] <= 'Z')) {
#			if (decode(buf,base,&val)) {
#				s3 = s2; s2 = s1; s1 = s0; s0 = val;
#			} else {
#				if (buf[0] == 'A' && buf[1] == '\n') {
#					s3 = s2; s2 = s1; s1 = s0; s0 = 10;
#				} else {
#					put_str("Illegal character input number\n");
#				}
#			}
#		} else if (buf[0] == '+') {
#			v0 = f_add(s0,s1);
#			s0 = v0; s1 = s2; s2 = s3;
#		} else if (buf[0] == '-') {
#			v0 = f_minus(s0,s1);
#			s0 = v0; s1 = s2; s2 = s3;
#		} else if (buf[0] == '*') {
#			if (s0 == 0) {
#				put_str("Division by zero\n");
#			} else {
#				v0 = f_times(s0,s1);
#				s0 = v0; s1 = s2; s2 = s3;
#			}
#		} else if (buf[0] == '/') {
#			v0 = f_div(s0,s1);
#			s0 = v0; s1 = s2; s2 = s3;
#		} else if (buf[0] == '^') {
#			if (s0 < 0) {
#				put_str("Negative exponent!\n");
#			} else {
#				v0 = f_exp(s0,s1);
#				s0 = v0; s1 = s2; s2 = s3;
#			}
#		} else if (buf[0] == 'p') {
#			putnum_nl(s0,base);
#		} else if (buf[0] == 'a') {
#			putnum_nl(s3,base);
#			putnum_nl(s2,base);
#			putnum_nl(s1,base);
#			putnum_nl(s0,base);
#		} else if (buf[0] == 'b') {
#			if (s0 >= 2 && s0 < 37) {
#				base = s0; s0 = s1; s1 = s2;
#			} else {
#				put_str("Illegal base\n");
#			}
#		} else if (buf[0] == 'q')
#		} else {
#			put_str("Illegal command\n");
#		}
#	}
# }
#
# The calculator stack is kept in registers s0 through s3, with s0 the top (x).
# The current base is in s4.  val is on the stack.
#
		.data
buf:		.space	34	# max length needed, base 2, 32 characters
				# plus newline and null termination

		.text
main:		sub $sp,$sp,32
		sw $fp,4($sp)
		add $fp,$sp,32
		sw $ra,0($fp)
		sw $s0,-4($fp)
		sw $s1,-8($fp)
		sw $s2,-12($fp)
		sw $s3,-16($fp)
		sw $s4,-20($fp)
		# val  -24($fp) == 8($sp)
		# fp   -28($fp) == 4($sp)

		move $s0,$zero
		move $s1,$zero
		move $s2,$zero
		move $s3,$zero
		li $s4,10
mloop:		# read in a line -- either a number or a command.
		la $a0,buf
		li $a1,34
		li $v0,8
		syscall
		la $t0,buf
		lb $t1,($t0)
		.data
		.align 4
jtbl:		.word	c_times		# * 0x2a
		.word	c_plus		# +
		.word	c_bad		# ,
		.word	c_minus		# -
		.word	c_bad		# .
		.word	c_div		# /
		.word	c_num		# 0 0x30
		.word	c_num		# 1
		.word	c_num		# 2
		.word	c_num		# 3
		.word	c_num		# 4
		.word	c_num		# 5
		.word	c_num		# 6
		.word	c_num		# 7
		.word	c_num		# 8 0x38
		.word	c_num		# 9
		.word	c_bad		# :
		.word	c_bad		# ;
		.word	c_bad		# <
		.word	c_bad		# =
		.word	c_bad		# >
		.word	c_bad		# ?
		.word	c_bad		# @ 0x40
		.word	c_num		# A
		.word	c_num		# B
		.word	c_num		# C
		.word	c_num		# D
		.word	c_num		# E
		.word	c_num		# F
		.word	c_num		# G
		.word	c_num		# H 0x48
		.word	c_num		# I
		.word	c_num		# J
		.word	c_num		# K
		.word	c_num		# L
		.word	c_num		# M
		.word	c_num		# N
		.word	c_num		# O
		.word	c_num		# P 0x50
		.word	c_num		# Q
		.word	c_num		# R
		.word	c_num		# S
		.word	c_num		# T
		.word	c_num		# U
		.word	c_num		# V
		.word	c_num		# W
		.word	c_num		# X 0x58
		.word	c_num		# Y
		.word	c_num		# Z
		.word	c_bad		# [
		.word	c_bad		# \ 
		.word	c_bad		# ]
		.word	c_exp		# ^
		.word	c_bad		# _
		.word	c_bad		# ' 0x60
		.word	c_print_all	# a
		.word	c_set_base	# b
		.word	c_bad		# c
		.word	c_bad		# d
		.word	c_bad		# e
		.word	c_bad		# f
		.word	c_bad		# g
		.word	c_bad		# h 0x68
		.word	c_bad		# i
		.word	c_bad		# j
		.word	c_bad		# k
		.word	c_bad		# l
		.word	c_bad		# m
		.word	c_bad		# n
		.word	c_off		# o
		.word	c_print_top	# p 0x70

		.text
		subu $t1,$t1,0x2a	# base of jump table is * or 0x2a
		bgeu $t1,0x47,c_bad	# 0x71 - 0x2a
		sll $t1,$t1,2
		lw $t1,jtbl($t1)
		jr $t1

c_num:
		sub $a2,$fp,24
		move $a1,$t0			# str
		move $a0,$s4			# base
		jal decode
		beq $v0,1,okay_num
		# handle special A case.
		la $t0,buf
		lb $t1,($t0)
		bne $t1,0x41,bad_num		# A special case
		lb $t1,1($t0)
		bne $t1,0xa,bad_num
		# is "A" "newline"
		move $s3,$s2
		move $s2,$s1
		move $s1,$s0
		li $s0,10
		# break out of case gets to bottom of loop, and we eliminate
		# double jumps
		b mloop
		.data
bad_num_str:	.asciiz "Illegal character in input number\n"
		.text
bad_num:	la $a0,bad_num_str
		li $v0,4
		syscall
		b mloop
okay_num:	move $s3,$s2
		move $s2,$s1
		move $s1,$s0
		lw $s0,8($sp)
		b mloop
c_plus:
		move $a0,$s0
		move $a1,$s1
		jal f_plus
		move $s0,$v0
		move $s1,$s2
		move $s2,$s3
		b mloop
c_minus:
		move $a0,$s0
		move $a1,$s1
		jal f_minus
		move $s0,$v0
		move $s1,$s2
		move $s2,$s3
		b mloop
c_times:
		move $a0,$s0
		move $a1,$s1
		jal f_times
		move $s0,$v0
		move $s1,$s2
		move $s2,$s3
		b mloop
c_div:
		bne $s0,$zero,okay_div
		.data
div_zero:	.asciiz "Division by zero\n"
		.text
		la $a0,div_zero
		li $v0,4
		syscall
		b mloop
okay_div:	move $a0,$s0
		move $a1,$s1
		jal f_div
		move $s0,$v0
		move $s1,$s2
		move $s2,$s3
		b mloop
c_exp:
		bge $s0,$zero,do_exp
		.data
neg_exp:	.asciiz "Negative exponent!\n"
		.text
		la $a0,neg_exp
		li $v0,4
		syscall
		b mloop
do_exp:		move $a0,$s0
		move $a1,$s1
		jal f_exp
		move $s0,$v0
		move $s1,$s2
		move $s2,$s3
		b mloop
c_print_top:
		move $a0,$s0
		move $a1,$s4
		jal putnum_nl
		b mloop
c_print_all:
		move $a0,$s3
		move $a1,$s4
		jal putnum_nl
		move $a0,$s2
		move $a1,$s4
		jal putnum_nl
		move $a0,$s1
		move $a1,$s4
		jal putnum_nl
		move $a0,$s0
		move $a1,$s4
		jal putnum_nl
		b mloop
c_set_base:
		blt $s0,2,bad_base
		blt $s0,37,okay_base
		.data
bad_base_msg:	.asciiz "Illegal base\n"
		.text
bad_base:	la $a0,bad_base_msg
		li $v0,4
		syscall
		b mloop
okay_base:	
		move $s4,$s0
		move $s0,$s1
		move $s1,$s2
		move $s2,$s3
		b mloop
		.data
bad_cmd:	.asciiz "Illegal command\n"
		.text
c_bad:
		la $a0,bad_cmd
		li $v0,4
		syscall 
		b mloop

c_off:
		lw $ra,0($fp)
		lw $s0,-4($fp)
		lw $s1,-8($fp)
		lw $s2,-12($fp)
		lw $s3,-16($fp)
		lw $s4,-20($fp)
		lw $fp,4($sp)
		add $sp,$sp,32
		li $v0,0		# main returns 0 as exit status
		jr $ra
		
	# 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.
	#
	# int decode(int base,char *str,int *ip) -- returns 1 to mean success
	# with the decoded number stored in *ip.
	#
	# uses scratch registers t0, t1.
decode:		li $v0,0		# initial value
dloop:		lb $t1,0($a1)		# walk through string
		add $a1,$a1,1
		beq $t1,0xa,decode_done
		beq $t1,0,decode_done
		blt $t1,0x30,bad_char
		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		# 0...9: $t1 has digit value
		j got_new_digit
not_digit:	blt $t1,0x41,bad_char	# capital A
		bgt $t1,0x5a,bad_char	# through Z
		sub $t1,$t1,0x37	# -0x41+a = -0x37
got_new_digit:	bge $t1,$a0,bad_char
		mul $v0,$v0,$a0
		add $v0,$v0,$t1
		j dloop
bad_char:	li $v0,0		# error indication
		jr $ra
decode_done:	sw $v0,0($a2)
		li $v0,1
		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.
# Uses scratch registers t0 and t1.  Treats numbers as unsigned.
#
# 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

f_plus:		addu $v0,$a1,$a0
		jr $ra
f_minus:	subu $v0,$a1,$a0
		jr $ra
f_times:	mul $v0,$a1,$a0
		jr $ra
f_div:		divu $v0,$a1,$a0
		jr $ra

		# precondition:	 a0 >= 0
		#
		# v0 = a1^a0
		#
		# f_exp(int a0,int a1) /* a0 >= 0 */
		# {
		#	int v0;
		#	for (v0 = 0; a0; a0 >>= 1) {
		#		if (a0 & 1) v0 = v0 * a1;
		#		a1 = a1 * a1;
		#	}
		#	return v0;
		# }
f_exp:
		li $v0,1
		j f_exp_test
f_exp_loop:	and $t0,$a0,1			# if (a0 & 1) {
		beq $t0,$zero,f_exp_square	#
		mul $v0,$v0,$a1			#	v0 = v0 * a1
						# }
f_exp_square:	mul $a1,$a1,$a1			# a1 = a1 * a1;
		srl $a0,$a0,1			# a0 >>= 1
f_exp_test:	bne $a0,$zero,f_exp_loop
		jr $ra

#
# putnum_nl -- instead of unsigned, we print a signed number:  we test
# to see if it is negative, if so print the negative sign.  Then we
# take the absolute value of the number as an unsigned value, and call
# putnum.  We follow with a newline, so numbers are on a line by themselves.
#
		.data
nl:		.asciiz "\n"
minus_sign:	.asciiz "-"
		.text
putnum_nl:	sub $sp,$sp,8
		sw $ra,4($sp)
		bge $a0,$zero,putnum_positive
		sw $a0,8($sp)
		la $a0,minus_sign
		li $v0,4
		syscall
		lw $a0,8($sp)
		subu $a0,$zero,$a0
putnum_positive:	
		jal putnum
		la $a0,nl
		li $v0,4
		syscall
putnum_done:	lw $ra,4($sp)
		add $sp,$sp,8
		jr $ra