# SPIM S20 MIPS simulator.
# The default trap handler for spim.
#
# Copyright (C) 1990-2000 James Larus, larus@cs.wisc.edu.
# ALL RIGHTS RESERVED.
#
# SPIM is distributed under the following conditions:
#
# You may make copies of SPIM for your own use and modify those copies.
#
# All copies of SPIM must retain my name and copyright notice.
#
# You may not sell SPIM or distributed SPIM in conjunction with a commerical
# product or service without the expressed written consent of James Larus.
#
# THIS SOFTWARE IS PROVIDED ``AS IS'' AND WITHOUT ANY EXPRESS OR
# IMPLIED WARRANTIES, INCLUDING, WITHOUT LIMITATION, THE IMPLIED
# WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
# PURPOSE.
#

# $Header: $


# Define the exception handling code.  This must go first!

	.kdata
__m1_:	.asciiz "  Exception "
__m2_:	.asciiz " occurred and ignored\n"
__e0_:	.asciiz "  [Interrupt] "
__e1_:	.asciiz	""
__e2_:	.asciiz	""
__e3_:	.asciiz	""
__e4_:	.asciiz	"  [Unaligned address in inst/data fetch] "
__e5_:	.asciiz	"  [Unaligned address in store] "
__e6_:	.asciiz	"  [Bad address in text read] "
__e7_:	.asciiz	"  [Bad address in data/stack read] "
__e8_:	.asciiz	"  [Error in syscall] "
__e9_:	.asciiz	"  [Breakpoint] "
__e10_:	.asciiz	"  [Reserved instruction] "
__e11_:	.asciiz	""
__e12_:	.asciiz	"  [Arithmetic overflow] "
__e13_:	.asciiz	"  [Inexact floating point result] "
__e14_:	.asciiz	"  [Invalid floating point result] "
__e15_:	.asciiz	"  [Divide by 0] "
__e16_:	.asciiz	"  [Floating point overflow] "
__e17_:	.asciiz	"  [Floating point underflow] "
__excp:	.word __e0_,__e1_,__e2_,__e3_,__e4_,__e5_,__e6_,__e7_,__e8_,__e9_
	.word __e10_,__e11_,__e12_,__e13_,__e14_,__e15_,__e16_,__e17_
s1:	.word 0
s2:	.word 0

	.ktext 0x80000080
	.set noat
	# Because we are running in the kernel, we can use $k0/$k1 without
	# saving their old values.
	move $k1 $at	# Save $at
	.set at
	sw $v0 s1	# Not re-entrent and we can't trust $sp
	sw $a0 s2
	mfc0 $k0 $13	# Cause
        sgt $v0 $k0 0x44 # ignore interrupt exceptions
        bgtz $v0 ret
        addu $0 $0 0
	li $v0 4	# syscall 4 (print_str)
	la $a0 __m1_
	syscall
	li $v0 1	# syscall 1 (print_int)
        srl $a0 $k0 2	# shift Cause reg
	syscall
	li $v0 4	# syscall 4 (print_str)
	lw $a0 __excp($k0)
	syscall
	bne $k0 0x18 ok_pc # Bad PC requires special checks
	mfc0 $a0, $14	# EPC
	and $a0, $a0, 0x3 # Is EPC word-aligned?
	beq $a0, 0, ok_pc
	li $v0 10	# Exit on really bad PC (out of text)
	syscall

ok_pc:
	li $v0 10
	syscall		# Exit even on okay PC (for grading)

	li $v0 4	# syscall 4 (print_str)
	la $a0 __m2_
	syscall
	mtc0 $0, $13	# Clear Cause register
ret:	lw $v0 s1
	lw $a0 s2
	mfc0 $k0 $14	# EPC
	.set noat
	move $at $k1	# Restore $at
	.set at
	rfe		# Return from exception handler
	addiu $k0 $k0 4 # Return to next instruction
	jr $k0


# Standard startup code.  Invoke the routine main with no arguments.

	.text
	.globl __start
__start: 
	lw $a0, 0($sp)	# argc
	addiu $a1, $sp, 4 # argv
	addiu $a2, $a1, 4 # envp
	sll $v0, $a0, 2
	addu $a2, $a2, $v0
	jal main
	li $v0 10
	syscall		# syscall 10 (exit)



#
# Library routines for HW3, Spring, 2001
# Author:  		Susan Eggers
# Last update:		4/10/01
# Please Note:
# You are on your own if you choose to make your own private copy
# of this code.  It will be your responsibility to make sure that 
# you have an updated copy, if we make bug fixes, enhancements, etc.
#


	.data

seed:		.word	0

	.text

# -----------------------------------------------------------------------
# initSeed
#  arguments:	$a0	seed for number generator
#  return val:	none
# Seed should be non-negative.
# Initializes random number generator.
# -----------------------------------------------------------------------

.globl initSeed
initSeed:
	rem	$a0, $a0, 2147483647
	ble	$a0, 0, initSeedLTZero
	sw	$a0, seed
	jr	$ra
initSeedLTZero:
	li	$t0, 1
	sw	$t0, seed
	jr	$ra

# -----------------------------------------------------------------------
# nextRand
#  arguments:	none
#  return val:	random number in interval (0,2147483647)
#  Implements a prime modulus multiplicative linear congruential
#  generator, with the following constants:
#
#  max		2147483647
#  multiplier	16807
#  quot		127773
#  remainder	2836
# -----------------------------------------------------------------------
 
.globl nextRand
nextRand:
	lw	$t1, seed
	rem	$t2, $t1, 127773
	mul	$t2, $t2, 16807
	div	$t3, $t1, 127773
	mul	$t3, $t3, 2836
	subu	$t3, $t2, $t3
	bgt	$t3, 0, nextRandGTZero
	addu	$t3, $t3, 2147483647
nextRandGTZero:
	sw	$t3, seed
	move	$v0, $t3
	jr	$ra
	
# -----------------------------------------------------------------------
# initRandomArray
#  arguments:	$a0	base address of array of words
#		$a1	length of array (integer)
#		$a2	seed for random number generator (integer)
#  return val:	none
#  Fill in the specified number of words starting at the memory location
#  given in $a0.  Behavior is unspecified for non-positive size
#  arrays.
# -----------------------------------------------------------------------

.globl initRandArray
initRandArray:
	addiu	$sp, $sp, -12		# push stack frame
	sw	$ra, 0($sp)		#  and save $ra
	sw	$s0, 4($sp)		#  and save $s0
	sw	$s1, 8($sp)		#  and save $s1
	ble	$a1, $0, initRABottom	# punt for length <= 0
	move	$s0, $a0		# s0 will hold base ptr A
	mul	$a1, $a1, 4		# s1 will hold end of array ptr
	add	$s1, $a0, $a1	
	addiu	$s1, $s1, -4		# decrement it.
	move 	$a0, $a2		# call initSeed
	jal	initSeed
initRandArrayTop:
	jal	nextRand		# get a random number
	sw	$v0, 0($s1)		# store random number
	addiu	$s1, $s1, -4		# decrement end of array ptr
	ble	$s0, $s1, initRandArrayTop 	# check if finished
initRABottom:
	lw	$s0, 4($sp)		# finished: restore regs
	lw	$s1, 8($sp)		
	lw	$ra, 0($sp)
	addiu	$sp, $sp, 12		# pop stack frame
	jr	$ra			#  and return
		
# -----------------------------------------------------------------------
# isSorted
#  arguments:	$a0	base address of array of words
#		$a1	length of array (integer)
#  return val:	1 if sorted; 0 if otherwise
#  Check if given array is sorted in non-decreasing order.
#  By default, arrays of length <= 1 are "sorted."  
# -----------------------------------------------------------------------

.globl isSorted
isSorted:
	addiu	$sp, $sp, -4		# push stack frame
	sw	$ra, 0($sp)		#  and save $ra
	li	$v0, 0			# $v0 is set to unsorted to begin
	bgt	$a1, 1, isSortedTop	# arrays of length <= 1 are sorted
	li	$v0, 1			# by default
	j	isSortedExit
isSortedTop:
	lw	$t0, 0($a0)		# load *A
	lw	$t1, 4($a0)		# load *(A+1)
	bgt	$t0, $t1, isSortedExit	# if A[i] > A[i+1] exit
	addu	$a0, $a0, 4		# increment A ptr
	subu	$a1, $a1, 1		# decrement counter
	bgt	$a1, 1, isSortedTop	# goto top if more than 1 to go
	li	$v0, 1			#  else it must be sorted
isSortedExit:	
	lw	$ra, 0($sp)		# restore $ra
	addu	$sp, $sp, 4		# pop stack frame
	jr	$ra			#  and return