#
# RPN calculator, bsy@play, 11/97.
#
# 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).
#
# CHANGE LOG:
#
# Updated for model 200 to add 32-deep stack mode code, and to add the
# 't' tower-of-hanoi function.
#
# The equivalent C code is:
#
# #define NELT	32
# int	calc_stack[NELT], *calc_stack_end = &calc_stack[4];
# int	cur_base;
# char	buf[34];
#
# int	pop(void)
# {
#	int	val, *sp;
#
#	val = calc_stack[0];
#	for (sp = calc_stack + 1; sp < calc_stack_end; sp++) {
#		sp[-1] = sp[0];
#	}
#	return val;
# }
#
# void	push(int val)
# {
#	int	*sp;
#
#	for (sp = calc_stack_end - 2; sp >= calc_stack; --sp) {
#		sp[1] = sp[0];
#	}
#	calc_stack[0] = val;
# }
#
# int	get_top(void)
# {
#	return calc_stack[0];
# }
#
# void	set_top(int	x)
# {
#	calc_stack[0] = x;
# }
#
# void	f_print_all(char *buf)
# {
#	int	*sp;
#
#	for (sp = calc_stack_end - 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)
# {
#	int	x = pop();
#	set_top(get_top() * x());
# }
#
# void	f_div(char *buf)
# {
#	int	x = get_top();
#
#	if (x == 0) {
#		fputs("Division by zero!\n",stdout);
#	} else {
#		set_top(get_top() / x);
#	}
# }
#
# [ ... ]
#
# 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, 0,0,0,0, 0,0,0,0, 0,0,0,0	# 16
		.word	0,0,0,0, 0,0,0,0, 0,0,0,0, 0,0,0,0	# 32
calc_stack_end:	.word	0	# calc_stack + 16
cur_base:	.word	10
mode:		.word	0

		.text
		#
		# leaf:  int pop(void) returns topmost element of the
		# calculator stack, shifting everything down.
		#
pop:		lw $v0,calc_stack	# val = calc_stack[0]
		la $t0,calc_stack	# sp = calc_stack + 1
		add $t0,$t0,4
		lw $t1,calc_stack_end	# t1 = calc_stack_end for loop test
		b pop_loop_test
pop_loop:	lw $t2,0($t0)
		sw $t2,-4($t0)
		add $t0,$t0,4
pop_loop_test:	blt $t0,$t1,pop_loop
		jr $ra
		#
		# leaf:  void push(int) pushes value into the calculator
		# stack
		#
push:		la $t0,calc_stack		# for loop test
		lw $t1,calc_stack_end		# sp = calc_stack_end - 2
		sub $t1,$t1,8
		b push_loop_test
push_loop:	lw $t2,0($t1)
		sw $t2,4($t1)
		sub $t1,$t1,4
push_loop_test:	bge $t1,$t0,push_loop
		sw $a0,0($t0)
		jr $ra

# inline expanded
# get_top:	lw $v0,calc_stack
#		jr $ra
# set_top:	sw $a0,calc_stack
#		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	# for testing
		lw $s1,calc_stack_end	# sp = calc_stack_end - 1
		sub $s1,$s1,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:
		bge $s1,$s0,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)

		lw $a0,calc_stack
		lw $a1,cur_base
		jal putnum_nl

		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
		sw $v0,cur_base
		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

f_mode:		sub $sp,$sp,8
		sw $ra,4($sp)
		jal pop
		beq $v0,0,f_mode_compat
		beq $v0,1,f_mode_extended
		sw $a0,8($sp)
		move $a0,$v0
		jal push
		.data
bad_mode_str:	.asciiz "Illegal mode\n"
		.text
		li $v0,4
		la $a0,bad_mode_str
		syscall
		b f_mode_done
f_mode_compat:	sw $v0,mode
		la $v0,calc_stack
		add $v0,$v0,16		# 4 deep stack
		sw $v0,calc_stack_end
		b f_mode_done
f_mode_extended:
		sw $v0,mode
		la $v0,calc_stack
		add $v0,$v0,128		# 32 deep stack
		sw $v0,calc_stack_end
f_mode_done:	
		lw $a0,8($sp)
		lw $ra,4($sp)
		add $sp,$sp,8
		jr $ra

tower:		sub $sp,$sp,8		# ra, a0
		sw $ra,4($sp)
		sw $a0,8($sp)
		bne $a0,$zero,tower_complex
		li $v0,0
		b tower_done
tower_complex:	sub $a0,$a0,1
		jal tower
		add $v0,$v0,$v0
		add $v0,$v0,1
tower_done:	lw $a0,8($sp)
		lw $ra,4($sp)
		add $sp,$sp,8
		jr $ra

f_tower:	sub $sp,$sp,8
		sw $ra,4($sp)
		sw $a0,8($sp)
		jal pop
		bge $v0,$zero,f_tower_okay
		.data
f_tower_bad_str:
		.asciiz "Illegal number of disks\n"
		.text
		move $a0,$v0
		jal push
		la $a0,f_tower_bad_str
		li $v0,4
		syscall
		b f_tower_done
f_tower_okay:	move $a0,$v0
		jal tower
		move $a0,$v0
		jal push
f_tower_done:	lw $a0,8($sp)
		lw $ra,4($sp)
		jr $ra

f_change_sign:	sub $sp,$sp,8
		sw $ra,4($sp)
		sw $a0,8($sp)
		jal pop
		sub $a0,$zero,$v0
		jal push
		lw $a0,8($sp)
		lw $ra,4($sp)
		jr $ra

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

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)
		la $t0,calc_stack
		add $t0,$t0,16
		sw $t0,calc_stack_end
mloop:		la $a0,buf
		li $a1,34
		li $v0,8
		syscall
		la $a0,buf
		lb $a1,0($a0)
		subu $a1,$a1,0x2a
		bltu $a1,0x4b,okay_tbl	# 0x4b = 0x75 - 0x2a
		la $a1,f_bad
		b do_cmd
okay_tbl:
		sll $a1,$a1,3
		lw $t0,ftbl+4($a1)	# cmd requires this mode
		lw $a1,ftbl($a1)
		lw $t1,mode
		bge $t1,$t0,do_cmd
		la $a1,f_bad
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
