		#
		# Test driver for Conway's Life code.  When San Diego Software
		# Design releases its screensaver that runs full screen Life,
		# the grid will be large.  This code will be used for displays
		# of various widths/heights, as well as for non-full-screen
		# applications (e.g., running Life in a dynamically sized
		# window).
		#
		# Release 0.4, 11/30/1997.  bsy@play, created.
		#

GRID_WIDTH	= 79
GRID_HEIGHT	= 23
X_WIDTH		= 81			# GRID_WIDTH + 2
ROW_SIZE	= 3			# X_WIDTH + 31 / 32
X_HEIGHT	= 25			# GRID_HEIGHT + 2
GRID_WORDS	= 75			# ROW_SIZE * X_HEIGHT
GRID_MEM	= 300			# GRID_WORDS * sizeof(unsigned int)

		.data
		.globl	width
width:		.word	GRID_WIDTH
		.globl	height
height:		.word	GRID_HEIGHT
main_nl:	.asciiz	"\n"
xterm_stuff:	.word	1

		.text
		# leaf function, omit frame.  See C code.
		.globl grid_words
grid_words:	add $v0,$a0,33
		sra $v0,$v0,5
		add $v1,$a1,2
		mul $v0,$v0,$v1
		jr $ra

		.globl word_index
word_index:	lw $v0, width
		addu $v0,$v0,33
		sra $v0,$v0,5
		addu $v1,$a0,1
		mul $v0,$v0,$v1
		addu $v1,$a1,1
		sra $v1,$v1,5
		addu $v0,$v0,$v1
		jr $ra

		.globl word_mask
word_mask:	addu $v1,$a1,1
		and $v1,$v1,0x1f
		li $v0,1
		sll $v0,$v0,$v1
		jr $ra

		.globl cell_alive
cell_alive:	subu $sp,$sp,16
		sw $ra,4($sp)
		sw $a0,8($sp)
		sw $a1,12($sp)
		move $a0,$a1
		move $a1,$a2

# hacks for constant time computation
# Note that set_cell is not constant time, but we don't expect that a good
# implementation to use it anyway; the uses within the startup is the same
# for every run with that seed, so it doesn't matter.
#		jal word_mask
#		sw $v0,16($sp)

		jal word_index
		sll $v0,$v0,2
		lw $v1,8($sp)
		addu $v1,$v0,$v1
		lw $v0,0($v1)

#		lw $v1,16($sp)
#		and $v1,$v0,$v1
#		li $v0,0
#		beq $v1,$zero,cell_alive_not
#		li $v0,1
#cell_alive_not:

		add $v1,$a1,1
		and $v1,$v1,0x1f
		srl $v0,$v0,$v1
		and $v0,$v0,1

		lw $a1,12($sp)
		lw $a0,8($sp)
		lw $ra,4($sp)
		addu $sp,$sp,16
		jr $ra

		.globl set_cell
set_cell:	subu $sp,$sp,16
		sw $ra,4($sp)
		sw $a0,8($sp)
		sw $a1,12($sp)
		move $a0,$a1
		move $a1,$a2
		jal word_mask		# word_mask(r,c)
		sw $v0,16($sp)		# save mask
		jal word_index		# word_index(r,c)
		sll $t0,$v0,2
		lw $v1,8($sp)		# grid
		addu $t0,$v1,$t0	# $t0 has &grid[word_index(r,c)]
		lw $v0,($t0)
		lw $v1,16($sp)
		beq $a3,$zero,set_cell_clear
		or $v0,$v0,$v1		# set the bit
		b set_cell_cont
set_cell_clear:	not $v1,$v1		# clear the bit
		and $v0,$v0,$v1
set_cell_cont:	sw $v0,($t0)		# store back into memory
		lw $a1,12($sp)
		lw $a0,8($sp)
		lw $ra,4($sp)
		addu $sp,$sp,16
		jr $ra

		.data
show_grid_buf:	.space	4097		# spim wants null terminated strings
show_grid_count:.word	0
		.text
show_grid_putchar:
		subu $sp,$sp,4
		sw $ra,4($sp)
		lw $t4,show_grid_count
		sb $a0,show_grid_buf($t4)
		add $t4,$t4,1
		sw $t4,show_grid_count
		bne $t4,4096,show_grid_no_flush
		jal show_grid_flush
show_grid_no_flush:
		lw $ra,4($sp)
		addu $sp,$sp,4
		jr $ra
show_grid_flush:
		subu $sp,$sp,8
		sw $a0,4($sp)
		lw $a0,show_grid_count
		sb $zero,show_grid_buf($a0)
		la $a0,show_grid_buf
		li $v0,4
		syscall
		sw $zero,show_grid_count
		lw $a0,4($sp)
		addu $sp,$sp,8
		jr $ra
		#
		# xspim does not use a real terminal emulator,
		# but if this code is run under spim inside an
		# xterm, the animation should work
		#
		.globl show_grid
show_grid:	subu $sp,$sp,20
		sw $ra,4($sp)
		sw $a0,8($sp)
		sw $a1,12($sp)
		sw $a2,16($sp)
		lw $v0,xterm_stuff
		beqz $v0,show_grid_no_home
		.data
show_grid_xterm_home_str:
		.byte 0x1b
		.asciiz "[H"
		.text
		la $a1,show_grid_xterm_home_str
show_grid_home_again:
		lb $a0,0($a1)
		beq $a0,0,show_grid_no_home
		jal show_grid_putchar		
		addu $a1,$a1,1
		b show_grid_home_again
show_grid_no_home:
		li $a1,0		# r = 0
		b show_grid_r_test
show_grid_r_loop:
		li $a2,0		# c = 0
		b show_grid_c_loop
show_grid_c_loop:
		lw $a0,8($sp)
		jal cell_alive
		sw $a0,20($sp)
		.data
show_grid_state:
		.asciiz " *"
		.text
		lbu $a0,show_grid_state($v0)
		jal show_grid_putchar

		lw $a0,20($sp)
show_grid_c_next:
		addu $a2,$a2,1
show_grid_c_test:
		lw $t0,width
		blt $a2,$t0,show_grid_c_loop
		sw $a0,20($sp)
		li $a0,'\n'
		jal show_grid_putchar
		lw $a0,20($sp)
		addu $a1,$a1,1
show_grid_r_test:
		lw $t0,height
		blt $a1,$t0,show_grid_r_loop
		jal show_grid_flush
		lw $a2,16($sp)
		lw $a1,12($sp)
		lw $a0,8($sp)
		lw $ra 4($sp)
		addu $sp,$sp,20
		jr $ra

		#
		# cheesy linear congruential generator
		#
		.data
rstate:		.word 1
		.text
srandgen:	sw $a0,rstate
		jr $ra
randgen:	lw $v0,rstate
		mul $v0,$v0,5	
		#
		# these are NOT the same -- SPIM's addu puts the 16-bit value
		# in the 16-bit immediate field, which is sign extended at
		# runtime.
		#
#		addu $v0,$v0,65521	# large 16 bit prime
		#
		li $v1,65521
		addu $v0,$v0,$v1
		sw $v0,rstate
		remu $v0,$v0,65537
		jr $ra

		#
		# main uses alloca
		#
		# unlike the C code which has getopt for command line
		# arguments, we prompt for them.
		#
		# on frame: fp,ra,a0,a1,a2,a3,rep_count,show_all,grid,grid2,i
		#	    0  -4 -8-12-16-20-24       -28      -32  -36   -40
		#
		.globl main
main:		subu $sp,$sp,44
		sw $fp,44($sp)
		addu $fp,$sp,44
		sw $ra,-4($fp)
		sw $a0,-8($fp)
		sw $a1,-12($fp)
		sw $a2,-16($fp)
		sw $a3,-20($fp)
		li $v0,1024
		sw $v0,-24($fp)		# rep_count = 1024
		.data
main_instr:	.asciiz "Enter numbers, <= 0 to use default\n"
main_wprompt:	.asciiz "Width? "
main_hprompt:	.asciiz "Height? "
main_xprompt:	.asciiz "Xterm control sequences? (0/1) "
main_sprompt:	.asciiz "Show intermediate states? (0/1) "
main_Sprompt:	.asciiz "Seed? "
main_rprompt:	.asciiz "Rep? "
		.text
		li $v0,4
		la $a0,main_instr
		syscall
		la $a0,main_wprompt
		syscall
		li $v0,5
		syscall
		ble $v0,0,main_wdefault
		sw $v0,width
main_wdefault:	li $v0,4
		la $a0,main_hprompt
		syscall
		li $v0,5
		syscall
		ble $v0,0,main_hdefault
		sw $v0,height
main_hdefault:	li $v0,4
		la $a0,main_xprompt
		syscall
		li $v0,5
		syscall
		sw $v0,xterm_stuff
		li $v0,4
		la $a0,main_sprompt
		syscall
		li $v0,5
		syscall
		sw $v0,-28($fp)		# show_all
		li $v0,4
		la $a0,main_Sprompt
		syscall
		li $v0,5
		syscall
		ble $v0,0,main_Sdefault
		move $a0,$v0
		jal srandgen
main_Sdefault:	li $v0,4
		la $a0,main_rprompt
		syscall
		li $v0,5
		syscall
		ble $v0,0,main_rdefault
		sw $v0,-24($fp)
main_rdefault:	lw $a0,width
		lw $a1,height
		jal grid_words
		sll $v0,$v0,2		# we know it is mult of 4, wordsize
		subu $sp,$sp,$v0	# alloca instead of malloc
		addu $a0,$sp,4
		sw $a0,-32($fp)		# grid
		subu $sp,$sp,$v0
		addu $v1,$sp,4
		sw $v1,-36($fp)		# grid2

		li $a1,0		# r
		b main_init_r_loop_test
main_init_r_loop:
		li $a2,0		# c
		b main_init_c_loop_test
main_init_c_loop:
		jal randgen
		and $v0,$v0,1
		move $a3,$v0
		jal set_cell
		addu $a2,$a2,1
main_init_c_loop_test:
		lw $t0,width
		blt $a2,$t0,main_init_c_loop
		addu $a1,$a1,1
main_init_r_loop_test:
		lw $t0,height
		blt $a1,$t0,main_init_r_loop

		li $a3,0
		li $a1,-1		# r loop
		b main_r_edge_loop_test
main_r_edge_loop:
		lw $a0,-32($fp)		# grid
		li $a2,-1
		jal set_cell
		lw $a2,width
		jal set_cell
		lw $a0,-36($fp)		# grid2
		jal set_cell
		li $a2,-1
		jal set_cell
		addu $a1,$a1,1
main_r_edge_loop_test:
		lw $t0,height
		ble $a1,$t0,main_r_edge_loop

		li $a2,-1		# c loop
		b main_c_edge_loop_test
main_c_edge_loop:
		lw $a0,-32($fp)		# grid
		li $a1,-1
		jal set_cell
		lw $a1,height
		jal set_cell
		lw $a0,-36($fp)		# grid2
		jal set_cell
		li $a1,-1
		jal set_cell
		addu $a2,$a2,1
main_c_edge_loop_test:
		lw $t0,width
		ble $a2,$t0,main_c_edge_loop

		lw $t0,xterm_stuff
		beq $t0,0,main_no_xterm_home
		.data
main_xterm_home_str:
		.byte 0x1b
		.ascii "[H"
		.byte 0x1b
		.asciiz "[2J"
		.text
		la $a0,main_xterm_home_str
		li $v0,4
		syscall
main_no_xterm_home:
		lw $t0,-28($fp)
		beq $t0,0,main_no_show_grid_L1
		lw $a0,-32($fp)			# grid
		jal show_grid
main_no_show_grid_L1:

		li $t0,0
		lw $a0,-32($fp)
		lw $a1,-36($fp)
		b main_loop_test
main_loop:	sw $t0,-40($fp)

		jal life_xform

		move $t0,$a0		# swap grid and grid2
		move $a0,$a1		# no need to store back into frame,
		move $a1,$t0		# since we never use grid/grid2 again.

		lw $t0,-28($fp)
		beq $t0,0,main_loop_no_show
		jal show_grid

main_loop_no_show:
		lw $t0,-40($fp)

		addu $t0,$t0,1
main_loop_test:	lw $t1,-24($fp)
		blt $t0,$t1,main_loop
		# bug:	grid is in $a0 already, and the frame slot is out
		#       of date 		lw $a0,-32($fp)
		jal show_grid

		li $v0,0

		lw $a3,-20($fp)
		lw $a2,-16($fp)
		lw $a1,-12($fp)
		lw $a0,-8($fp)
		lw $ra,-4($fp)
		move $t0,$fp
		lw $fp,0($fp)
		move $sp,$t0
		jr $ra
