#
# RPN calculator, bsy@play, 11/97.  Took about 1.75 hours to type in and
# debug.
#
# This version uses function pointers for every operation.  The stack is
# an explicit global data structure, accessed using push / pop functions.
# All normal calculator functions are necessarily non-leaf functions (except
# for "off", which does not use the stack at all).
#
# The equivalent C code is:
#
# #define NELT	4
# int	calc_stack[NELT];
# int	cur_base;
# char	buf[34];
#
# int	pop(void)
# {
#	int	val, *sp;
#
#	val = calc_stack[0];
#	for (sp = calc_stack; sp < calc_stack + NELT - 1; sp++) {
#		sp[0] = sp[1];
#	}
#	return val;
# }
#
# void	push(int val)
# {
#	int	*sp;
#
#	for (sp = calc_stack + NELT - 2; sp >= calc_stack; --sp) {
#		sp[1] = sp[0];
#	}
#	calc_stack[0] = val;
# }
#
# void	f_print_all(char *buf)
# {
#	int	*sp;
#
#	for (sp = calc_stack + NELT - 1; sp >= calc_stack; --sp) {
#		putnum_nl(*sp);
#	}
# }
#
# void	f_print_top(char	*buf)
# {
#	int	val = pop();
#	putnum_nl(val);
#	push(val);
# }
#
# void	f_times(char *buf)
# {
#	push(pop() * pop());
# }
#
# [ ... ]
#
# void (*ftbl[])(char *) = {
#  f_times, [ ... ] , f_print_top,
# };
#
# void main(void)
# {
#	void	(*fptr)(char *);
#
#	for (;;) {
#		read_str(buf,34);
#		if ('*' <= buf[0] && buf[0] <= 'p')
#			fptr = ftbl[buf[0]-'*'];
#		else
#			fptr = f_bad;
#		(*fptr)(buf);
#	}
# }
#
		.data
calc_stack:	.word	0,0,0,0
calc_stack_end:	.word	0	# sentinel
cur_base:	.word	10

		.text
		#
		# leaf:  int pop(void) returns topmost element of the
		# calculator stack, shifting everything down.
		#
pop:		lw $v0,calc_stack
		la $t0,calc_stack
		la $t1,calc_stack_end - 4
		b pop_loop_test
pop_loop:	lw $t2,4($t0)
		sw $t2,0($t0)
		add $t0,$t0,4
pop_loop_test:	bne $t0,$t1,pop_loop
		jr $ra
		#
		# leaf:  void push(int) pushes value into the calculator
		# stack
		#
push:		la $t0,calc_stack
		la $t1,calc_stack_end - 8
		b push_loop_test
push_loop:	lw $t2,0($t1)
		sw $t2,4($t1)
		sub $t1,$t1,4
push_loop_test:	ble $t0,$t1,push_loop
		sw $a0,0($t0)
		jr $ra

		#
		# this function must know about the stack
		#
		# frame: s0,s1,a0,a1,ra,fp
		#
f_print_all:	sub $sp,$sp,24
		sw $fp,4($sp)
		add $fp,$sp,24
		sw $ra,-16($fp)
		sw $s0,0($fp)
		sw $s1,-4($fp)
		sw $a0,-8($fp)
		sw $a1,-12($fp)

		la $s0,calc_stack
		la $s1,calc_stack_end - 4
		lw $a1,cur_base
		b print_loop_test
print_loop:	lw $a0,0($s1)
		jal putnum_nl
		sub $s1,$s1,4
print_loop_test:
		ble $s0,$s1,print_loop

		lw $s0,0($fp)
		lw $s1,-4($fp)
		lw $a0,-8($fp)
		lw $a1,-12($fp)
		lw $ra,-16($fp)
		lw $fp,-20($fp)
		add $sp,$sp,24
		jr $ra

		#
		# We omit knowledge of the stack implementation here by
		# incurring the expense of doing push(pop())
		#
		# frame:  a0, a1, ra, fp
		#
f_print_top:	sub $sp,$sp,16
		sw $fp,4($sp)
		add $fp,$sp,16
		sw $ra,-8($fp)
		sw $a0,0($fp)
		sw $a1,-4($fp)

		jal pop
		move $a0,$v0
		lw $a1,cur_base
		jal putnum_nl
		jal push

		lw $a0,0($fp)
		lw $a1,-4($fp)
		lw $ra,-8($fp)
		lw $fp,-12($fp)
		add $sp,$sp,16
		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.
#
# frame: a0,tmp,ra,fp
#
putnum:		sub $sp,$sp,16
		sw $fp,4($sp)
		add $fp,$sp,16
		sw $ra,-8($fp)
		sw $a0,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 $a0,0($fp)
		lw $ra,-8($fp)
		lw $fp,-12($fp)
		add $sp,$sp,16
		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)
		sw $a0,8($sp)
		bge $a0,$zero,putnum_positive
		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 $a0,8($sp)
		lw $ra,4($sp)
		add $sp,$sp,8
		jr $ra


		#
		# f_plus, f_minus, f_times, f_div, f_exp are all leaf
		# functions; they ignore their sole argument.
		#

f_plus:		sub $sp,$sp,16
		sw $fp,4($sp)
		add $fp,$sp,16
		sw $ra,-8($fp)
		sw $a0,-4($fp)
		jal pop
		sw $v0,0($fp)
		jal pop
		lw $t1,0($fp)
		add $a0,$v0,$t1
		jal push
		lw $a0,-4($fp)
		lw $ra,-8($fp)
		move $t0,$fp
		lw $fp,-12($fp)
		move $sp,$t0
		jr $ra

f_minus:	sub $sp,$sp,16
		sw $fp,4($sp)
		add $fp,$sp,16
		sw $ra,-8($fp)
		sw $a0,-4($fp)
		jal pop
		sw $v0,0($fp)
		jal pop
		lw $t1,0($fp)
		sub $a0,$v0,$t1
		jal push
		lw $a0,-4($fp)
		lw $ra,-8($fp)
		move $t0,$fp
		lw $fp,-12($fp)
		move $sp,$t0
		jr $ra

f_times:	sub $sp,$sp,16
		sw $fp,4($sp)
		add $fp,$sp,16
		sw $ra,-8($fp)
		sw $a0,-4($fp)
		jal pop
		sw $v0,0($fp)
		jal pop
		lw $t1,0($fp)
		mul $a0,$v0,$t1
		jal push
		lw $a0,-4($fp)
		lw $ra,-8($fp)
		move $t0,$fp
		lw $fp,-12($fp)
		move $sp,$t0
		jr $ra

f_div:		sub $sp,$sp,16
		sw $fp,4($sp)
		add $fp,$sp,16
		sw $ra,-8($fp)
		sw $a0,-4($fp)
		jal pop
		bne $v0,$zero,f_div_okay
		move $a0,$v0
		jal push
		.data
f_div_err_msg:	.asciiz	"Division by zero\n"
		.text
		la $a0,f_div_err_msg
		li $v0,4
		syscall
		b f_div_done
f_div_okay:	sw $v0,0($fp)
		jal pop
		lw $t1,0($fp)
		div $a0,$v0,$t1
		jal push
f_div_done:
		lw $a0,-4($fp)
		lw $ra,-8($fp)
		move $t0,$fp
		lw $fp,-12($fp)
		move $sp,$t0
		jr $ra

f_exp:		sub $sp,$sp,16
		sw $fp,4($sp)
		add $fp,$sp,16
		sw $ra,-8($fp)
		sw $a0,-4($fp)
		jal pop
		bge $v0,$zero,f_exp_okay
		move $a0,$v0
		jal push
		.data
f_exp_err_msg:	.asciiz	"Negative exponent\n"
		.text
		la $a0,f_exp_err_msg
		li $v0,4
		syscall
		b f_exp_done
f_exp_okay:	sw $v0,0($fp)
		jal pop
		lw $t0,0($fp)
		move $t1,$v0
		li $v0,1
		b f_exp_loop_test
f_exp_loop:	andi $t2,$t0,1
		beq $t2,$zero,f_exp_bit_not_set
		mul $v0,$v0,$t1
f_exp_bit_not_set:
		mul $t1,$t1,$t1
		srl $t0,$t0,1
f_exp_loop_test:
		bne $t0,$zero,f_exp_loop
		move $a0,$v0
		jal push
f_exp_done:	
		lw $a0,-4($fp)
		lw $ra,-8($fp)
		move $t0,$fp
		lw $fp,-12($fp)
		move $sp,$t0
		jr $ra

		#
		# leaf:  int decode(int base,char *str,int *num)
		# returns success if no illegal digit
		#
		# uses $t0,$t1.
		#
decode:		li $v0,0		# initial value
		move $t0,$a1
dloop:		lb $t1,0($t0)		# walk through string
		add $t0,$t0,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

		#
		# f_num(char	*buf) pushes converted number onto the
		# stack if conversion succeeds.
		#
		# frame contains: a0,a1,a2,num,$ra,$fp
		#
f_num:		sub $sp,$sp,24
		sw $fp,4($sp)
		add $fp,$sp,24
		sw $ra,-16($fp)

		sw $a0,0($fp)
		sw $a1,-4($fp)
		sw $a2,-8($fp)
		move $a1,$a0			# str
		lw $a0,cur_base
		sub $a2,$fp,12
		jal decode
		beq $v0,1,okay_num
		# handle special A case.
		lw $t0,0($fp)
		lb $t1,($t0)
		bne $t1,0x41,bad_num		# A special case
		lb $t1,1($t0)
		bne $t1,0xa,bad_num
		# is "A" "newline"
		li $a0,10
		jal push
		b f_num_done
		.data
bad_num_str:	.asciiz "Illegal character in input number\n"
		.text
bad_num:	la $a0,bad_num_str
		li $v0,4
		syscall
		b f_num_done
okay_num:	lw $a0,-12($fp)
		jal push
f_num_done:	lw $a0,0($fp)
		lw $a1,-4($fp)
		lw $a2,-8($fp)
		lw $ra,-16($fp)
		lw $fp,-20($fp)
		add $sp,$sp,24
		jr $ra

f_set_base:	sub $sp,$sp,4
		sw $ra,4($sp)
		jal pop
		blt $v0,2,f_set_base_bad
		blt $v0,37,f_set_base_okay
		.data
f_set_base_errmsg:
		.asciiz "Illegal base\n"
		.text
f_set_base_bad:	move $a0,$v0
		jal push
		li $v0,4
		la $a0,f_set_base_errmsg
		syscall
		b f_set_base_done
f_set_base_okay:
		sw $v0,cur_base
f_set_base_done:
		lw $ra,4($sp)
		add $sp,$sp,4
		jr $ra

		.data
bad_cmd_str:	.asciiz "Illegal command\n"
		.text
f_bad:		la $a0,bad_cmd_str
		li $v0,4
		syscall
		jr $ra
		
f_off:		li $v0,10
		syscall

		#
		# Function table.  All functions take string buf as argument.
		#
		.data
ftbl:		.word	f_times		# * 0x2a
		.word	f_plus		# +
		.word	f_bad		# ,
		.word	f_minus		# -
		.word	f_bad		# .
		.word	f_div		# /
		.word	f_num		# 0 0x30
		.word	f_num		# 1
		.word	f_num		# 2
		.word	f_num		# 3
		.word	f_num		# 4
		.word	f_num		# 5
		.word	f_num		# 6
		.word	f_num		# 7
		.word	f_num		# 8 0x38
		.word	f_num		# 9
		.word	f_bad		# :
		.word	f_bad		# ;
		.word	f_bad		# <
		.word	f_bad		# =
		.word	f_bad		# >
		.word	f_bad		# ?
		.word	f_bad		# @ 0x40
		.word	f_num		# A
		.word	f_num		# B
		.word	f_num		# C
		.word	f_num		# D
		.word	f_num		# E
		.word	f_num		# F
		.word	f_num		# G
		.word	f_num		# H 0x48
		.word	f_num		# I
		.word	f_num		# J
		.word	f_num		# K
		.word	f_num		# L
		.word	f_num		# M
		.word	f_num		# N
		.word	f_num		# O
		.word	f_num		# P 0x50
		.word	f_num		# Q
		.word	f_num		# R
		.word	f_num		# S
		.word	f_num		# T
		.word	f_num		# U
		.word	f_num		# V
		.word	f_num		# W
		.word	f_num		# X 0x58
		.word	f_num		# Y
		.word	f_num		# Z
		.word	f_bad		# [
		.word	f_bad		# \ 
		.word	f_bad		# ]
		.word	f_exp		# ^
		.word	f_bad		# _
		.word	f_bad		# ' 0x60
		.word	f_print_all	# a
		.word	f_set_base	# b
		.word	f_bad		# c
		.word	f_bad		# d
		.word	f_bad		# e
		.word	f_bad		# f
		.word	f_bad		# g
		.word	f_bad		# h 0x68
		.word	f_bad		# i
		.word	f_bad		# j
		.word	f_bad		# k
		.word	f_bad		# l
		.word	f_bad		# m
		.word	f_bad		# n
		.word	f_off		# o
		.word	f_print_top	# p 0x70

buf:		.space	34

		.text
main:		sub $sp,$sp,16
		sw $fp,4($sp)
		add $fp,$sp,16
		sw $ra,-8($fp)
		sw $a0,0($fp)
		sw $a1,-4($fp)
mloop:		la $a0,buf
		li $a1,34
		li $v0,8
		syscall
		la $a0,buf
		lb $a1,0($a0)
		subu $a1,$a1,0x2a
		bltu $a1,0x47,okay_tbl
		la $a1,f_bad
		b do_cmd
okay_tbl:
		sll $a1,$a1,2
		lw $a1,ftbl($a1)
do_cmd:		jalr $a1
		b mloop
		lw $a1,-4($fp)
		lw $a0,0($fp)
		lw $ra,-8($fp)
		lw $fp,-12($fp)
		add $sp,$sp,16
		jr $ra