# SPIM S20 MIPS simulator.
#
# Modified trap handler for COOL runtime.
#
# 2/01/95 Carleton Miyamoto
# 8/19/94 Manuel Fahndrich
#
# $Log: trap.handler,v $
# Revision 1.9  2004/04/21 02:13:53  bec
# Merged-in changes to print the class of the exception
#
# Revision 1.8  2004/04/20 03:04:02  bec
# Merged-in handler for exceptions.  This will not affect code generators
# that do not implement exceptions.
#
# Revision 1.7  2004/01/22 03:06:34  jcondit
# merged matth's changes (gc init msgs) from sp03
#
# Revision 1.6  2003/07/20 18:52:58  matth
# fixed a bug in the comments of Object.copy: t3 and t4 are clobberred
#
# Revision 1.5  2003/04/12 02:36:54  matth
# updated trap.handler for Spim 6.5.  (Don't use andi with 32-bit immediates)
#
# Revision 1.4  2001/04/23 09:47:32  smcpeak
# fixed an off-by-1 bug in stack tracing code
#
# Revision 1.3  2001/03/23 07:30:53  smcpeak
# fixed _GenGC_Assign so it doesn't clobber $a0
#
# Revision 1.2  1996/10/12 18:54:35  darcy
# AFter Merge versions.
#
# Revision 1.1.1.1.4.1  1996/09/17 08:21:39  aiken
# new Makefile, new results
#
#
#
# - updated instructions
# - cleanup of Makefile + new parameters
# - new VERSION file
#
# cleanup of Makefile; removed -static
#
# fixed a bug in PA2 assignment skeleton
#
# paramaterization
#
# updated skeletons to pass ostreams by ref
# paramaterized makefile
#
#
# pass ostreams by ref in SKEL
# parameterized Makefile
#
# new parameters
#
# new parameters
#
# just copied, not actually updated
#
# Revision 1.1.1.1  1996/07/12 06:48:08  aiken
# Imported sources
#
# Revision 2.3  1996/05/31 17:55:22  aiken
# added copyright notice
#
# Revision 2.2  1996/05/28 22:02:38  aiken
# fixed spelling errors,
# brought comments up to date
#
# Revision 2.1  1995/11/08 01:14:41  dgay
# Add a _MemMgr_Test function that calls the garbage collector if the
# global _MemMgr_TEST is non-zero (this global is generated by coolc
# when the -t option is used).
# _MemMgr_Test is called on every memory allocation, i.e. in Object.copy,
# String.concat, String.substr, IO.in_string, IO.in_int
#
# Revision 2.0  1995/09/26 01:26:13  dgay
# - Merged changes between revisions 1.12 and 1.13 of trap handler into
#   trap handler for GC from miyamoto.
# - Fixed bug in generational GC: didn't handle assignments properly
#   (registers were trashed)
# - Changed method of identifying pointers on stack:
#   no tags pushed, simply checks that values are even and are in the
#   correct address range. Aborts if eyecatcher missing.
# - Added _gc_check primitive to check the presence of an eyecatcher
#   on an object.
# - Removed the Stop & Copy GC.
#
#   Revision 2.2  1995/05/17  20:15:41  miyamoto
#   - The "NoGC" garbage collector.  This collector does nothing but
#     expand the heap when more memory is required.
#   - support for multiple garbage collectors added.
#   - "_MemMgr_*" functions give an consistent view of the garbage
#     collectors.  It uses the addresses stored in "_MemMgr_INITIALIZER"
#     and "_MemMgr_COLLECTOR" to run the correct garbage collector.
#   - "_MemMgr_INITIALIZER" holds the address of the initialization
#     function for the garbage collector.  This is defined in the
#     program file (*.s).
#   - "_MemMgr_COLLECTOR" holds the address of the garbage collection
#     function.  This is defined in the program file (*.s).
#   - MemMgr_REG_MASK is used to determine which registers get auto-
#     updated.
#   - "_*GC_*Alloc" functions were removed.
#   - "*_REG_MASK" variables removed.
#
#   Revision 2.1  1995/03/13  15:58:32  miyamoto
#   - GenGC "Generational" garbage collector
#   - Converted all calls to "_SncGC_*" to their equivalent "_GenGC_*"
#   - Created constants:
#     GenGC_HDR*: Information in the GenGC header
#     GenGC_REG_MASK: Register mask for auto update
#     GenGC_ARU_MASK: All possible registers that can be auto updated
#     GenGC_HEAPEXPGRAN: Granularity of any heap expansion, heap is
#       always expanded in multiples of 2^GenGC_HEAPEXPGRAN
#     GenGC_OLDRATIO: Ratio of size of the old area to usable heap size
#   - Created GenGC error messages in the data seg (_GenGC_*)
#   - Object.copy: displays error message on an invalid object size
#
#   Revision 2.0  1995/02/16  17:32:38  miyamoto
#   - SncGC "Stop and Copy" garbage collector
#   - Created some constants:
#     obj_eyecatch: offset from object pointer to the eyecatcher
#     obj_disp: offset from object pointer to the dispatch table
#     obj_attr: offset from object pointer to the attributes
#     str_maxsize: the maximum length of a string
#     SncGC_REG_MASK: Register mask for auto update
#     SncGC_ARU_MASK: All possible registers that can be auto updated
#     SncGC_EXPANDSIZE: Size to expand heap when necessary (bytes)
#     SncGC_INFOSIZE: Size of SncGC header in the heap (bytes)
#   - Created some SncGC error messages in the data seg (_SncGC_*)
#   - Renamed labels in equality_test to contain a leading underscore
#     to avoid any conflicts which may arise
#   - Functions changed to accomodate SncGC:
#     __start: pushs Main object on the stack and calls "_SncGC_Init"
#     Object.copy: calls "_SncGC_Alloc" to allocate memory
#     IO.in_string, String.concat, String.substr:
#       uses "_SncGC_QAlloc" to verify allocation of memory
#   - Functions changed to accomodate stack flags:
#     Object.copy, IO.out_string, IO.out_int, IO.in_int, IO.in_string
#     String.concat, String.substr
#   - __start now sets $s0 to the self pointer of the Main object
#
#   *****
#   Warning (no changes made): String.substr trashes regs $t3 $t4
#   *****
#
#   Revision 1.12  1994/11/15  03:33:34  manuel
#   substr method didn't allow taking the empty substr at the end of a
#   string
#
#   Revision 1.11  1994/11/14  21:41:23  manuel
#   Comment for equality_test contained a type: arguments are in $t1 and
#   $t2
#
#   Revision 1.10  1994/10/26  02:31:50  manuel
#   Added more comments.
#
#   Revision 1.9  1994/08/31  02:04:31  manuel
#   Fixed an error in the in_string code: Reading from EOF, the system
#   returns 0 characters. We test for this and return a single '\n'. The
#   code can therefore recognize EOF.
#   The last line of a file must be terminated by a newline, otherwise
#   spim gets confused and returns the entire buffer!
#
#   Revision 1.8  1994/08/28  02:21:46  manuel
#   - Fixed typo in system message
#
#   Revision 1.7  1994/08/27  08:53:35  manuel
#   - Added an .align at end of data segment to be safe. Cgen should emit
#     one.
#
#   Revision 1.6  1994/08/27  08:37:49  manuel
#   - Added string primitives
#
#   Revision 1.5  1994/08/27  04:42:25  manuel
#   - Adapted code to handle String Class containing an Int object slot
#     for the string size.
#
#   Revision 1.4  1994/08/27  02:01:43  manuel
#   - Fixed typos
#
#   Revision 1.2  1994/08/27  00:41:01  manuel
#   - Changed string object representation to two slots. The first is a 32
#     bit slot indicating the string length, the second is a variable
#     sized slot containing the actual null terminated string.
#   - Fixed a bug in the in_string function which set obj_size to
#     4*obj_size
#   - Added constants for field offsets
#
#
# 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.
#
# Define the exception handling code.  This must go first!

	.kdata
__m1_:	.asciiz "  Exception "
__m2_:	.asciiz " Execution aborted\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/Division by 0] "
__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 $at $k1	# 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
	li $v0 4
	la $a0 __m2_
	syscall
	li $v0 10	# Exit upon all exceptions
	syscall		# syscall 10 (exit)
ret:	lw $v0 s1
	lw $a0 s2
	mfc0 $k0 $14	# EPC
	.set noat
	move $k1 $at	# Restore $at
	.set at
	rfe		# Return from exception handler
	addiu $k0 $k0 4 # Return to next instruction
	jr $k0

#
#  The code above this line is from spim.  Below this line are
#  the MIPS assembly routines implementing the Cool runtime system.
#  This code is Copyright (c) 1995,1996 The Regents of the University 
#  of California. All rights reserved.  See copyright.h for 
#  limitation of liability and disclaimer of warranty provisions.
#

#
# Functions that return to the cool caller, should preserve $s0-$s7
#
# $s7 is reserved as the limit pointer.
# $gp is the heap pointer (points to the next unused word)
#	should never be handled by the generated code!!!
# $sp is the stack pointer
# $ra contains the return address
#
# $v0, $v1, $t0, $t1, $t2, $a0, $a1, $a2 are scratch registers
#  (i.e. caller cannot assume that they remain unchanged)
#

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

_abort_msg:	.asciiz "Abort called from class "
_colon_msg:	.asciiz ":"
_dispatch_msg:  .asciiz ": Dispatch to void.\n"
_cabort_msg:	.asciiz "No match in case statement for Class "
_cabort_msg2:   .asciiz "Match on void in case statement.\n"
_nl:		.asciiz "\n"
_term_msg:	.asciiz "COOL program successfully executed\n"
_sabort_msg1:	.asciiz	"Index to substr is negative\n"
_sabort_msg2:	.asciiz	"Index to substr is too big\n"
_sabort_msg3:	.asciiz	"Length to substr too long\n"
_sabort_msg4:	.asciiz	"Length to substr is negative\n"
_sabort_msg:	.asciiz "Execution aborted.\n"
_objcopy_msg:	.asciiz "Object.copy: Invalid object size.\n"
_gc_abort_msg:	.asciiz "GC bug!\n"

# Exception Handler Message:
_uncaught_msg1: .asciiz "Uncaught Exception of Class "
_uncaught_msg2: .asciiz " thrown. COOL program aborted.\n"
_exception_handler:
	.word	__exception

# Stack overflow handler message:
_stack_overflow_msg: .asciiz " Stack overflow detected, COOL program aborted\n"


#
# Messages for the GenGC garbage collector
#

_GenGC_INITERROR:	.asciiz "GenGC: Unable to initialize the garbage collector.\n"
_GenGC_COLLECT:		.asciiz "Garbage collecting ...\n"
_GenGC_Major:		.asciiz "Major ...\n"
_GenGC_Minor:		.asciiz "Minor ...\n"
#_GenGC_COLLECT:		.asciiz ""
_GenGC_MINORERROR:	.asciiz "GenGC: Error during minor garbage collection.\n"
_GenGC_MAJORERROR:	.asciiz "GenGC: Error during major garbage collection.\n"
_GenGC_Init_test_msg:   .asciiz "GenGC initialized in test mode.\n"
_GenGC_Init_msg:        .asciiz "GenGC initialized.\n"

#
# Messages for the NoGC garabge collector
#

_NoGC_COLLECT:		.asciiz "Increasing heap...\n"
#_NoGC_COLLECT:		.asciiz ""

	.align 2

#
# Define some constants
#

obj_eyecatch=-4	# Unique id to verify any object
obj_tag=0
obj_size=4
obj_disp=8
obj_attr=12
int_slot=12
bool_slot=12
str_size=12	# This is a pointer to an Int object!!!
str_field=16	# The beginning of the ascii sequence
str_maxsize=1026	# the maximum string length

#
# The REG mask tells the garbage collector which register(s) it
# should automatically update on a garbage collection.  Note that
# this is (ANDed) with the ARU mask before the garbage collector
# reads it.  Only the registers specified in the garbage collector's
# ARU mask can be automatically updated.
#
# BITS----------------------------
# 3 2         1         0
# 10987654321098765432109876543210
# --------------------------------
#
# 00000000011111110000000000000000  <-  initial Register (REG) mask
# +--++--++--++--++--++--++--++--+      $s0-$s6
#    0   0   7   F   0   0   0   0     ($16-$22)
#

MemMgr_REG_MASK=0x007F0000

	.text

	.globl __exception
# Exception Message
__exception:			# $a0 contains case expression obj.
	move	$s0 $a0		# save the expression object
	la	$a0 _uncaught_msg1
	li	$v0 4
	syscall			# print message
	la	$t1 class_nameTab
	lw	$v0 obj_tag($s0)	# Get object tag
	sll	$v0 $v0 2	# *4
	addu	$t1 $t1 $v0
	lw	$t1 0($t1)	# Load class name string obj.
	addiu	$a0 $t1 str_field # Adjust to beginning of str
	li	$v0 4		# print_str
	syscall
	la	$a0 _uncaught_msg2
	li	$v0 4		# print_str
	syscall
	li	$v0 10
	syscall			# Exit


	.globl _stack_overflow_abort
# Stack Overflow Message
_stack_overflow_abort:
	la	$a0 _stack_overflow_msg
	li	$v0 4
	syscall			# print message
	li	$v0 10
	syscall			# Exit

	.globl __start
__start:
	li	$v0 9
	move	$a0 $zero
	syscall				# sbrk
	move	$a0 $sp			# initialize the garbage collector
	li	$a1 MemMgr_REG_MASK
	move	$a2 $v0
	jal	_MemMgr_Init		# sets $gp and $s7 (limit)

	la    	$t9 _exception_handler	# Exception: Set uncaught Exception Address

	la	$a0 Main_protObj	# create the Main object
	jal	Object.copy		# Call copy
	addiu	$sp $sp -4
	sw	$a0 4($sp)		# save the Main object on the stack
	move	$s0 $a0			# set $s0 to point to self
	jal	Main_init		# initialize the Main object
	jal	Main.main		# Invoke main method
	.globl __main_return
__main_return: # where we return after the call to Main.main
	addiu	$sp $sp 4		# restore the stack
	la	$a0 _term_msg		# show terminal message
	li	$v0 4
	syscall
	li $v0 10
	syscall				# syscall 10 (exit)

#
#  Polymorphic equality testing function:
#  Two objects are equal if they are
#    - identical (pointer equality, inlined in code)
#    - have same tag and are of type BOOL,STRING,INT and contain the
#      same data
#
#  INPUT: The two objects are passed in $t1 and $t2
#  OUTPUT: Initial value of $a0, if the objects are equal
#          Initial value of $a1, otherwise
#
#  The tags for Int,Bool,String are found in the global locations
#  _int_tag, _bool_tag, _string_tag, which are initialized by the
#  data part of the generated code. This removes a consistency problem
#  between this file and the generated code.
#

	.globl	equality_test
equality_test:			# ops in $t1 $t2
				# true in A0, false in A1
				# assume $t1, $t2 are not equal
	beq	$t1 $zero _eq_false # $t2 can't also be void   
	beq     $t2 $zero _eq_false # $t1 can't also be void   
	lw	$v0 obj_tag($t1)	# get tags
	lw	$v1 obj_tag($t2)
	bne	$v1 $v0 _eq_false	# compare tags
	lw	$a2 _int_tag	# load int tag
	beq	$v1 $a2 _eq_int	# Integers
	lw	$a2 _bool_tag	# load bool tag
	beq	$v1 $a2 _eq_int	# Booleans
	lw	$a2 _string_tag # load string tag
	bne	$v1 $a2 _eq_false  # Not a primitive type
_eq_str: # handle strings
	lw	$v0, str_size($t1)	# get string size objs
	lw	$v1, str_size($t2)
	lw	$v0, int_slot($v0)	# get string sizes
	lw	$v1, int_slot($v1)
	bne	$v1 $v0 _eq_false
	beqz	$v1 _eq_true		# 0 length strings are equal
	add	$t1 str_field		# Point to start of string
	add	$t2 str_field
	move	$t0 $v0		# Keep string length as counter
_eq_l1:
	lbu	$v0,0($t1)	# get char
	add	$t1 1
	lbu	$v1,0($t2)
	add	$t2 1
	bne	$v1 $v0 _eq_false
	addiu	$t0 $t0 -1	# Decrement counter
	bnez	$t0 _eq_l1
	b	_eq_true		# end of strings
		
_eq_int:	# handles booleans and ints
	lw	$v0,int_slot($t1)	# load values
	lw	$v1,int_slot($t2)
	bne	$v1 $v0 _eq_false
_eq_true:
	jr	$ra		# return true
_eq_false:
	move	$a0 $a1		# move false into accumulator
	jr	$ra

#
#  _dispatch_abort
#
#      filename in $a0
#      line number in $t1
#  
#  Prints error message and exits.
#  Called on dispatch to void.
#
	.globl	_dispatch_abort
_dispatch_abort:		 
        sw      $t1 0($sp)       # save line number
        addiu   $sp $sp -4
	addiu   $a0 $a0 str_field # adjust to beginning of string
	li      $v0 4
	syscall                  # print file name
	la      $a0 _colon_msg
	li	$v0 4
	syscall                  # print ":"
	lw      $a0 4($sp)       # 
	li	$v0 1
	syscall			 # print line number
	li 	$v0 4
	la	$a0 _dispatch_msg
	syscall			 # print dispatch-to-void message
	li   	$v0 10
        syscall			 # exit


#
#  _case_abort2
#
#      filename in $a0
#      line number in $t1
#  
#  Prints error message and exits.
#  Called on case on void.
#
	.globl	_case_abort2
_case_abort2:		 
        sw      $t1 0($sp)       # save line number
        addiu   $sp $sp -4
	addiu   $a0 $a0 str_field # adjust to beginning of string
	li      $v0 4
	syscall                  # print file name
	la      $a0 _colon_msg
	li	$v0 4
	syscall                  # print ":"
	lw      $a0 4($sp)       # 
	li	$v0 1
	syscall			 # print line number
	li 	$v0 4
	la	$a0 _cabort_msg2
	syscall			 # print case-on-void message
	li   	$v0 10
        syscall			 # exit
	
#
#
#  _case_abort
#		Is called when a case statement has no match
#
#   INPUT:	$a0 contains the object on which the case was
#		performed
#
#   Does not return!
#
	.globl	_case_abort
_case_abort:			# $a0 contains case expression obj.
	move	$s0 $a0		# save the expression object
	la	$a0 _cabort_msg
	li	$v0 4
	syscall			# print_str
	la	$t1 class_nameTab
	lw	$v0 obj_tag($s0)	# Get object tag
	sll	$v0 $v0 2	# *4
	addu	$t1 $t1 $v0
	lw	$t1 0($t1)	# Load class name string obj.
	addiu	$a0 $t1 str_field # Adjust to beginning of str
	li	$v0 4		# print_str
	syscall
	la	$a0 _nl
	li	$v0 4		# print_str
	syscall
	li	$v0 10
	syscall			# Exit
	

#
# Copy method
#
#   Copies an object and returns a pointer to a new object in
#   the heap.  Note that to increase performance, the stack frame
#   is not set up unless it is absolutely needed.  As a result,
#   the frame is setup just before the call to "_MemMgr_Alloc" and
#   is destroyed just after it.  The increase in performance
#   occurs becuase the calls to "_MemMgr_Alloc" happen very
#   infrequently when the heap needs to be garbage collected.
#
#   INPUT:	$a0: object to be copied to free space in heap
#
#   OUTPUT:	$a0: points to the newly created copy.
#
#   Registers modified:
#	$t0, $t1, $t2, $t3, $t4, $v0, $v1, $a0, $a1, $a2, $gp, $s7
#

	.globl	Object.copy
Object.copy:
	addiu	$sp $sp -8			# create stack frame
	sw	$ra 8($sp)
	sw	$a0 4($sp)

	jal	_MemMgr_Test			# test GC area

	lw	$a0 4($sp)			# get object size
	lw	$a0 obj_size($a0)
	blez	$a0 _objcopy_error		# check for invalid size
	sll	$a0 $a0 2			# convert words to bytes
	addiu	$a0 $a0 4			# account for eyecatcher
	jal	_MemMgr_Alloc			# allocate storage
	addiu	$a1 $a0 4			# pointer to new object

	lw	$a0 4($sp)			# the self object
	lw	$ra 8($sp)			# restore return address
	addiu	$sp $sp 8			# remove frame
	lw	$t0 obj_size($a0)		# get size of object
	sll	$t0 $t0 2			# convert words to bytes
	b	_objcopy_allocated		# get on with the copy

# A faster version of Object.copy, for internal use (does not call
# _MemMgr_Test, and if possible not _MemMgr_Alloc)

_quick_copy:
	lw	$t0 obj_size($a0)		# get size of object to copy
	blez	$t0 _objcopy_error		# check for invalid size
	sll	$t0 $t0 2			# convert words to bytes
	addiu	$t1 $t0 4			# account for eyecatcher
	add	$gp $gp $t1			# allocate memory
	sub	$a1 $gp $t0			# pointer to new object
	blt	$gp $s7 _objcopy_allocated	# check allocation
_objcopy_allocate:
	sub	$gp $a1 4			# restore the original $gp
	addiu	$sp $sp -8			# frame size
	sw	$ra 8($sp)			# save return address
	sw	$a0 4($sp)			# save self
	move	$a0 $t1				# put bytes to allocate in $a0
	jal	_MemMgr_Alloc			# allocate storage
	addiu	$a1 $a0 4			# pointer to new object
	lw	$a0 4($sp)			# the self object
	lw	$ra 8($sp)			# restore return address
	addiu	$sp $sp 8			# remove frame
	lw	$t0 obj_size($a0)		# get size of object
	sll	$t0 $t0 2			# convert words to bytes
_objcopy_allocated:
	addiu	$t1 $0 -1
	sw	$t1 obj_eyecatch($a1)		# store eyecatcher
	add	$t0 $t0 $a0			# find limit of copy
	move	$t1 $a1				# save source
_objcopy_loop:
	lw	$v0 0($a0)			# copy word
	sw	$v0 0($t1)
	addiu	$a0 $a0 4			# update source
	addiu	$t1 $t1 4			# update destination
	bne	$a0 $t0 _objcopy_loop		# loop
_objcopy_end:
	move	$a0 $a1				# put new object in $a0
	jr	$ra				# return
_objcopy_error:
	la	$a0 _objcopy_msg		# show error message
	li	$v0 4
	syscall
	li	$v0 10				# exit
	syscall

#
#
# Object.abort
#
#	The abort method for the object class (usually inherited by
#	all other classes)
#
#   INPUT:	$a0 contains the object on which abort() was dispatched.
#

	.globl	Object.abort
Object.abort:
	move	$s0 $a0		# save self
	li	$v0 4
	la	$a0 _abort_msg
	syscall			# print_str
	la	$t1 class_nameTab
	lw	$v0 obj_tag($s0)	# Get object tag
	sll	$v0 $v0 2	# *4
	addu	$t1 $t1 $v0
	lw	$t1 0($t1)	# Load class name string obj.
	addiu	$a0 $t1 str_field	# Adjust to beginning of str
	li	$v0 4		# print_str
	syscall
	la	$a0 _nl
	li	$v0 4
	syscall			# print new line
	li	$v0 10
	syscall			# Exit

#
#
# Object.type_name	
#
#   	INPUT:	$a0 object who's class name is desired
#	OUTPUT:	$a0 reference to class name string object
#

	.globl	Object.type_name
Object.type_name:
	la	$t1 class_nameTab
	lw	$v0 obj_tag($a0)	# Get object tag
	sll	$v0 $v0 2	# *4
	addu	$t1 $t1 $v0	# index table
	lw	$a0 0($t1)	# Load class name string obj.
	jr	$ra

#
#
# IO.out_string
#
#	Prints out the contents of a string object argument
#	which is on top of the stack.
#
#	$a0 is preserved!
#

	.globl	IO.out_string
IO.out_string:
	addiu	$sp $sp -4
	sw	$a0 4($sp)	# save self
	lw	$a0 8($sp)	# get arg
	addiu	$a0 $a0 str_field	# Adjust to beginning of str
	li	$v0 4		# print_str
	syscall
	lw	$a0 4($sp)	# return self
	addiu	$sp $sp 8	# pop argument
	jr	$ra

#
#
# IO.out_int
#
#	Prints out the contents of an integer object on top of the
#	stack.
#
#	$a0 is preserved!
#

	.globl	IO.out_int
IO.out_int:
	addiu	$sp $sp -4
	sw	$a0 4($sp)	# save self
	lw	$a0 8($sp)	# get arg
	lw	$a0 int_slot($a0)	# Fetch int
	li	$v0 1		# print_int
	syscall	
	lw	$a0 4($sp)	# return self
	addiu	$sp $sp 8	# pop argument
	jr	$ra

#
#
# IO.in_int
#
#	Returns an integer object read from the terminal in $a0
#

	.globl	IO.in_int
IO.in_int:
	addiu	$sp $sp -4
	sw	$ra 4($sp)	# save return address

        la      $a0 Int_protObj
        jal     _quick_copy	# Call copy
        jal     Int_init

	addiu	$sp $sp -4
	sw	$a0 4($sp)	# save new object

	li	$v0, 5		# read int
	syscall

	lw	$a0 4($sp)
	addiu	$sp $sp 4


	sw	$v0 int_slot($a0)	# store int read into obj
	lw	$ra 4($sp)
	addiu	$sp $sp 4
	jr	$ra

#
#
# IO.in_string
#
#	Returns a string object read from the terminal, removing the
#	'\n'
#
#	OUTPUT:	$a0 the read string object
#

	.globl	IO.in_string
IO.in_string:
	addiu	$sp $sp -8
	sw	$ra 8($sp)			# save return address
	sw	$0 4($sp)			# init GC area

	jal	_MemMgr_Test			# test GC area

	la	$a0 Int_protObj			# Int object for string size
	jal	_quick_copy
	jal	Int_init
	sw	$a0 4($sp)			# save it

	li	$a0 str_field			# size of string obj. header
	addiu	$a0 $a0 str_maxsize		# max size of string data
	jal	_MemMgr_QAlloc			# make sure enough room

	la	$a0 String_protObj		# make string object
	jal	_quick_copy
	jal	String_init
	lw	$t0 4($sp)			# get size object
	sw	$t0 str_size($a0)		# store size object in string
	sw	$a0 4($sp)			# save string object

	addiu	$gp $gp -4			# overwrite last word

_instr_ok:
	li	$a1 str_maxsize			# largest string to read
	move	$a0 $gp	
	li	$v0, 8				# read string
	syscall

	move	$t0 $gp				# t0 to beginning of string
_instr_find_end:
	lb	$v0 0($gp)
	addiu	$gp $gp 1
	bnez	$v0 _instr_find_end

	# $gp points just after the null byte
	lb	$v0 0($t0)			# is first byte '\0'?
	bnez	$v0 _instr_noteof

	# we read nothing. Return '\n' (we don't have '\0'!!!)
	add	$v0 $zero 10			# load '\n' into $v0
	sb	$v0 -1($gp)
	sb	$zero 0($gp)			# terminate
	addiu	$gp $gp 1
	b	_instr_nonl

_instr_noteof:
	# Check if there really is a '\n'
	lb	$v0 -2($gp)
	bne	$v0 10 _instr_nonl

	# Write '\0' over '\n'
	sb	$zero -2($gp)			# Set end of string where '\n' was
	addiu	$gp $gp -1			# adjust for '\n'

_instr_nonl:
	lw	$a0 4($sp)			# get pointer to new str obj
	lw	$t1 str_size($a0)		# get pointer to int obj

	sub	$t0 $gp $a0
	subu	$t0 str_field			# calc actual str size
	addiu	$t0  -1				# adjust for '\0'
	sw	$t0 int_slot($t1)		# store string size in int obj
	addi	$gp $gp 3			# was already 1 past '\0'
	la	$t0 0xfffffffc
	and	$gp $gp $t0			# word align $gp

	sub	$t0 $gp $a0			# calc length
	srl	$t0 $t0 2			# divide by 4
	sw	$t0 obj_size($a0)		# set size field of obj

	lw	$ra 8($sp)			# restore return address
	addiu	$sp $sp 8
	jr	$ra				# return

#
#
# String.length
#		Returns Int Obj with string length of self
#
#	INPUT:	$a0 the string object
#	OUTPUT:	$a0 the int object which is the size of the string
#

	.globl	String.length
String.length:
	lw	$a0 str_size($a0)	# fetch attr
	jr	$ra	# Return

#
# String.concat
#
#   Concatenates arg1 onto the end of self and returns a pointer
#   to the new object.
#
#	INPUT:	$a0: the first string object (self)
#		Top of stack: the second string object (arg1)
#
#	OUTPUT:	$a0 the new string object
#

	.globl	String.concat
String.concat:

	addiu	$sp $sp -16
	sw	$ra 16($sp)			# save return address
	sw	$a0 12($sp)			# save self arg.
	sw	$0 8($sp)			# init GC area
	sw	$0 4($sp)			# init GC area

	jal	_MemMgr_Test			# test GC area

	lw	$a0 12($sp)
	lw	$a0 str_size($a0)
	jal     _quick_copy			# Call copy
	sw	$a0 8($sp)			# save new size object

	lw	$t1 20($sp)			# load arg object
	lw	$t1 str_size($t1)		# get size object
	lw	$t1 int_slot($t1)		# arg string size
	blez	$t1 _strcat_argempty		# nothing to add
	lw	$t0 12($sp)			# load self object
	lw	$t0 str_size($t0)		# get size object
	lw	$t0 int_slot($t0)		# self string size
	addu	$t0 $t0 $t1			# new size
	sw	$t0 int_slot($a0)		# store new size

	addiu	$a0 $t0 str_field		# size to allocate
	addiu	$a0 $a0 4			# include '\0', +3 to align
	la	$t2 0xfffffffc
	and	$a0 $a0 $t2			# align on word boundary
	addiu   $a0 $a0 1                       # make size odd for GC <-|
	sw	$a0 4($sp)			# save size in bytes     |
	addiu	$a0 $a0 3			# include eyecatcher(4) -1
	jal	_MemMgr_QAlloc			# check memory

	lw	$a0 12($sp)			# copy self
	jal	_quick_copy			# Call copy
	lw	$t0 8($sp)			# get the Int object
	sw	$t0 str_size($a0)		# store it in the str obj.

	sub	$t1 $gp $a0			# bytes allocated by _quick_copy
	lw	$t0 4($sp)			# get size in bytes (no eyecatcher)
	sub     $t0 $t0 1                       # Remove extra 1 (was for GC)
	sub	$t1 $t0 $t1			# more memory needed
	addu	$gp $gp $t1			# allocate rest
	srl	$t0 $t0 2			# convert to words
	sw	$t0 obj_size($a0)		# save new object size

	lw	$t0 12($sp)			# get original self object
	lw	$t0 str_size($t0)		# get size object
	lw	$t0 int_slot($t0)		# self string size
	addiu	$t1 $a0 str_field		# points to start of string data
	addu	$t1 $t1 $t0			# points to end: '\0'
	lw	$t0 20($sp)			# load arg object
	addiu	$t2 $t0 str_field		# points to start of arg data
	lw	$t0 str_size($t0)		# get arg size
	lw	$t0 int_slot($t0)
	addu	$t0 $t0 $t2			# find limit of copy

_strcat_copy:
	lb	$v0 0($t2)			# load from source
	sb	$v0 0($t1)			# save in destination
	addiu	$t2 $t2 1			# advance each index
	addiu	$t1 $t1 1
	bne	$t2 $t0 _strcat_copy		# check limit
	sb	$0 0($t1)			# add '\0'

	lw	$ra 16($sp)			# restore return address
	addiu	$sp $sp 20			# pop argument
	jr	$ra				# return

_strcat_argempty:
	lw	$a0 12($sp)			# load original self
	lw	$ra 16($sp)			# restore return address
	addiu	$sp $sp 20			# pop argument
	jr	$ra				# return

#
#
# String.substr(i,l)
#		Returns the sub string of self from i with length l
#		Offset starts at 0.
#
#	INPUT:	$a0 the string
#		length int object on top of stack (-4)
#		index int object below length on stack (-8)
#	OUTPUT:	The substring object in $a0
#

	.globl	String.substr
String.substr:
	addiu	$sp $sp -12		# frame
	sw	$ra 4($sp)		# save return
	sw	$a0 12($sp)		# save self
	sw	$0 8($sp)		# init GC area

	jal	_MemMgr_Test		# test GC area

	lw	$a0 12($sp)
	lw	$v0 obj_size($a0)
        la      $a0 Int_protObj		# ask if enough room to allocate
	lw	$a0 obj_size($a0)	#   a string object, an int object,
	add	$a0 $a0 $v0		#   and the string data
	addiu	$a0 $a0 2		# include 2 eyecatchers
	sll	$a0 $a0 2
	addi	$a0 $a0 str_maxsize
	jal	_MemMgr_QAlloc

_ss_ok:
	la	$a0 Int_protObj
	jal	_quick_copy
	jal	Int_init
	sw	$a0 8($sp)	# save new length obj
	la	$a0 String_protObj
	jal	_quick_copy
	jal	String_init	# new obj ptr in $a0
	move	$a2 $a0		# use a2 to make copy
	addiu	$gp $gp -4	# backup alloc ptr
	lw	$a1 12($sp)	# load orig
	lw	$t1 20($sp)	# index obj
	lw	$t2 16($sp)	# length obj
	lw	$t0 str_size($a1)
	lw	$v1 int_slot($t1) # index
	lw	$v0 int_slot($t0) # size of orig
	bltz	$v1 _ss_abort1	# index is smaller than 0
	bgt	$v1 $v0 _ss_abort2	# index > orig
	lw	$t3 int_slot($t2) # sub length
	add	$v1 $v1 $t3	# index+sublength
	bgt	$v1 $v0 _ss_abort3
	bltz	$t3 _ss_abort4
	lw	$t4 8($sp)	# load new length obj
	sw	$t3 int_slot($t4) # save new size
	sw	$t4 str_size($a0) # store size in string
	lw	$v1 int_slot($t1) # index
	addiu	$a1 $a1 str_field # advance src to str
	add	$a1 $a1 $v1	  # advance to indexed char
	addiu	$a2 $a2 str_field # advance dst to str
	beqz	$t3 _ss_end	  # empty length
_ss_loop:
	lb	$v0 0($a1)
	addiu	$a1 $a1 1	# inc src
	sb	$v0 0($a2)
	addiu	$a2 $a2 1	# inc dst
	addiu	$t3 $t3 -1	# dec ctr
	bnez	$t3 _ss_loop
_ss_end:
	sb	$zero 0($a2)	# null terminate
	move	$gp $a2
	addiu	$gp $gp 4	# realign the heap ptr
	la	$t0 0xfffffffc
	and	$gp $gp $t0	# word align $gp

	sub	$t0 $gp $a0	# calc object size
	srl	$t0 $t0 2	# div by 4
	sw	$t0 obj_size($a0)

	lw	$ra 4($sp)
	addiu	$sp $sp 20	# pop arguments
	jr	$ra

_ss_abort1:
	la	$a0 _sabort_msg1
	b	_ss_abort
_ss_abort2:
	la	$a0 _sabort_msg2
	b	_ss_abort
_ss_abort3:
	la	$a0 _sabort_msg3
	b	_ss_abort
_ss_abort4:
	la	$a0 _sabort_msg4
_ss_abort:
	li	$v0 4
	syscall
	la	$a0 _sabort_msg
	li	$v0 4
	syscall
	li	$v0 10		# exit
	syscall

#
# MemMgr Memory Manager
#
#   The MemMgr functions give a consistent view of the garbage collectors.
#   This allows multiple collectors to exist in one file and the easy
#   selection of different collectors.  It includes functions to initialize
#   the collector and to reserve memory and query its status.
#
#   The following assumptions are made:
#
#     1) The allocation of memory involves incrementing the $gp pointer.
#        The $s7 pointer serves as a limit.  The collector function is
#        called before $s7 is exceeded by $gp.
#
#     2) The initialization functions all take the same arguments as
#        defined in "_MemMgr_Init".
#
#     3) The garbage collector functions all take the arguments.  "$a0"
#        contains the end of the stack to check for pointers.  "$a1"
#        contains the size in bytes needed by the program and must be
#        preserved across the function call.
#

#
# Initialize the Memory Manager
#
#   Call the initialization routine for the garbage collector.
#
#   INPUT:
#	$a0: start of stack
#	$a1: initial Register mask
#	$a2: end of heap
#	heap_start: start of the heap
#
#   OUTPUT:
#	$gp: lower bound of the work area
#	$s7: upper bound of the work area
#
#   Registers modified:
#	$t0, initializer function
#

	.globl _MemMgr_Init
_MemMgr_Init:
	addiu	$sp $sp -4
	sw	$ra 4($sp)			# save return address
	la	$t0 _MemMgr_INITIALIZER		# pointer to initialization
	lw	$t0 0($t0)
	jalr	$t0				# initialize
	lw	$ra 4($sp)			# restore return address
	addiu	$sp $sp 4
	jr	$ra				# return

#
# Memory Allocation
#
#   Allocates the requested amount of memory and returns a pointer
#   to the start of the block.
#
#   INPUT:
#	$a0: size of allocation in bytes
#	$s7: limit pointer of the work area
#	$gp: current allocation pointer
#	heap_start: start of heap
#
#   OUTPUT:
#	$a0: pointer to new memory block
#
#   Registers modified:
#	$t0, $a1, collector function
#

	.globl _MemMgr_Alloc
_MemMgr_Alloc:
	add	$gp $gp $a0			# attempt to allocate storage
	blt	$gp $s7 _MemMgr_Alloc_end	# check allocation
	sub	$gp $gp $a0			# restore $gp
	addiu	$sp $sp -4
	sw	$ra 4($sp)			# save return address
	move	$a1 $a0				# size
	addiu	$a0 $sp 4			# end of stack to collect
	la	$t0 _MemMgr_COLLECTOR		# pointer to collector function
	lw	$t0 0($t0)
	jalr	$t0				# garbage collect
	lw	$ra 4($sp)			# restore return address
	addiu	$sp $sp 4
	move	$a0 $a1				# put size into $a0
	add	$gp $gp $a0			# allocate storage
_MemMgr_Alloc_end:
	sub	$a0 $gp $a0
	jr	$ra				# return

#
# Query Memory Allocation
#
#   Verifies that the requested amount of memory can be allocated
#   within the work area.
#
#   INPUT:
#	$a0: size of allocation in bytes
#	$s7: limit pointer of the work area
#	$gp: current allocation pointer
#	heap_start: start of heap
#
#   OUTPUT:
#	$a0: size of allocation in bytes (unchanged)
#
#   Registers modified:
#	$t0, $a1, collector function
#

	.globl _MemMgr_QAlloc
_MemMgr_QAlloc:
	add	$t0 $gp $a0			# attempt to allocate storage
	blt	$t0 $s7 _MemMgr_QAlloc_end	# check allocation
	addiu	$sp $sp -4
	sw	$ra 4($sp)			# save return address
	move	$a1 $a0				# size
	addiu	$a0 $sp 4			# end of stack to collect
	la	$t0 _MemMgr_COLLECTOR		# pointer to collector function
	lw	$t0 0($t0)
	jalr	$t0				# garbage collect
	lw	$ra 4($sp)			# restore return address
	addiu	$sp $sp 4
	move	$a0 $a1				# put size into $a0
_MemMgr_QAlloc_end:
	jr	$ra				# return

#
# Test heap consistency
#
#   Runs the garbage collector in the hope that this will help detect
#   garbage collection bugs earlier.
#
#   INPUT: (the usual GC stuff)
#	$s7: limit pointer of the work area
#	$gp: current allocation pointer
#	heap_start: start of heap
#
#   OUTPUT:
#	none
#
#   Registers modified:
#	$t0, $a1, collector function

	.globl	_MemMgr_Test
_MemMgr_Test:
	la	$t0 _MemMgr_TEST		# Check if testing enabled
	lw	$t0 0($t0)
	beqz	$t0 _MemMgr_Test_end

# Allocate 0 bytes
	addiu	$sp $sp -4			# Save return address
	sw	$ra 4($sp)
	li	$a1 0				# size = 0
	addiu	$a0 $sp 4			# end of stack to collect
	la	$t0 _MemMgr_COLLECTOR		# pointer to collector function
	lw	$t0 0($t0)
	jalr	$t0				# garbage collect
	lw	$ra 4($sp)			# restore return address
	addiu	$sp $sp 4

_MemMgr_Test_end:
	jr	$ra

#
# GenGC Generational Garbage Collector
#
#   This is an implementation of a generational garbage collector
#   as described in "Simple Generational Garbage Collection and Fast
#   Allocation" by Andrew W. Appel [Princeton University, March 1988].
#   This is a two generation scheme which uses an assignment table
#   to handle root pointers located in the older generation objects.
#
#   When the work area is filled, a minor garbage collection takes place
#   which moves all live objects into the reserve area.  These objects
#   are then incorporated into the old area.  New reserve and work areas
#   are setup and allocation can continue in the work area.  If a break-
#   point is reached in the size of the old area just after a minor
#   collection, a major collection then takes place.  All live objects in
#   the old area are then copied into the new area, expanding the heap if
#   necessary.  The X and new areas are then block copied back L1-L0
#   bytes to form the next old area.
#
#   The assignment table is implemented as a stack growing towards the
#   allocation pointer ($gp) in the work area.  If they cross, a minor
#   collection is then carried out.  This allows the garbage collector to
#   to have to keep a fixed table of assignments.  As a result, programs
#   with many assignments will tend not to be bogged down with extra
#   garbage collections.
#
#   The unused area was implemented to help keep the garbage collector
#   from continually expanding the heap.  This buffer zone allows major
#   garbage collections to happen earlier, reducing the risk of expansions
#   due to too many live objects in the old area.  The histories kept by
#   the garbage collector in MAJOR0, MAJOR1, MINOR0, and MINOR1 also help
#   to prevent unnecessary expansions of the heap.  If many live objects
#   were recently collected, the garbage collections will start to occur
#   sooner.
#
#   Note that during a minor collection, the work area is guaranteed to
#   fit within the reserve area.  However, during a major collection, the
#   old area will not necessarily fit in the new area.  If the latter occurs,
#   "_GenGC_OfsCopy" will detect this and expand the heap.
#
#   The heap is expanded on two different occasions:
#
#     1) After a major collection, the old area is set to be at most
#        1/(2^GenGC_OLDRATIO) of the usable heap (L0 to L3).  Note that
#        first L4 is checked to see if any of the unused memory between L3
#        and L4 is enough to satisfy this requirement.  If not, then the
#        heap will be expanded.  If it is, the appropriate amount will be
#        transfered from the unused area to the work/reserve area.
#
#     2) During a major collection, if the live objects in the old area
#        do not fit within the new area, the heap is expanded and $s7
#        is updated to reflact this.  This value later gets stored back
#        into L4.
#
#   During a normal allocation and minor collections, the heap has the
#   following form:
#
#      Header
#       |
#       |   Older generation objects
#       |    |
#       |    |             Minor garbage collection area
#       |    |              |
#       |    |              |                Allocation area
#       |    |              |                 |
#       |    |              |                 |           Assignment table
#       |    |              |                 |            |
#       |    |              |                 |            |   Unused
#       |    |              |                 |            |    |
#       v    v              v                 v            v    v
#     +----+--------------+-----------------+-------------+---+---------+
#     |XXXX| Old Area     | Reserve Area    | Work Area   |XXX| Unused  |
#     +----+--------------+-----------------+-------------+---+---------+
#      ^    ^              ^                 ^    ^        ^   ^         ^
#      |    |              |                 |    |-->  <--|   |         |
#      |    L0             L1                L2  $gp      $s7  L3        L4
#      |
#     heap_start
#
#     $gp (allocation pointer): points to the next free word in the work
#         area during normal allocation.  During a minor garbage collection,
#         it points to the next free work in the reserve area.
#
#     $s7 (limit pointer): points to the limit that $gp can traverse.  Between
#         it and L3 sits the assignment table which grows towards $gp.
#
#   During a Major collection, the heap has the following form:
#
#      Header
#       |
#       |   Older generation objects
#       |    |
#       |    |                 Objects surviving last minor garbage collection
#       |    |                  |
#       |    |                  |         Major garbage collection area
#       |    |                  |          |
#       v    v                  v          v
#     +----+------------------+----------+------------------------------+
#     |XXXX| Old Area         | X        | New Area                     |
#     +----+------------------+----------+------------------------------+
#      ^    ^                  ^      ^   ^      ^                       ^
#      |    |                  |      |   |      |-->                    |
#      |    L0                 L1     |   L2    $gp                   L4, $s7
#      |                              |
#     heap_start                     breakpoint
#
#     $gp (allocation pointer): During a major collection, this points
#         into the next free word in the new area.
#
#     $s7 (limit pointer): During a major collection, the points to the
#         limit of heap memory.  $gp is not allowed to pass this value.
#         If the objects in the live old area cannot fit in the new area,
#         more memory is allocated and $s7 is adjusted accordingly.
#
#     breakpoint: Point where a major collection will occur.  It is
#         calculated by the following formula:
#
#         breakpoint = MIN(L3-MAX(MAJOR0,MAJOR1)-MAX(MINOR0,MINOR1),
#                          L3-(L3-L0)/2)
#
#         where (variables stored in the header):
#           MAJOR0 = total size of objects in the new area after last major
#                    collection.
#           MAJOR1 = (MAJOR0+MAJOR1)/2
#           MINOR0 = total size of objects in the reserve area after last
#                    minor collection.
#           MINOR1 = (MINOR0+MINOR1)/2
#
#   The following assumptions are made in the garbage collection
#   process:
#
#     1) Pointers on the Stack:
#        Every word on the stack that ends in 0 (i.e., is even) and is
#	 a valid address in the heap is assumed to point to an object
#        in the heap.  Even heap addresses on the stack that are actually
#	 something else (e.g., raw integers) will probably cause an
#        garbage collection error.
#
#     2) Object Layout:
#        Besides the Int, String, and Bool objects (which are handled
#        separately), the garbage collector assumes that each attribute
#        in an object is a pointer to another object.  It, however,
#        still does as much as possible to verify this before actually
#        updating any fields.
#
#     3) Pointer tests:
#        In order to be verified as an object, a pointer must undergo
#        certain tests:
#
#          a) The pointer must point within the correct storage area.
#          b) The word before the pointer (obj_eyecatch) must be the
#             word 0xFFFF FFFF
#          c) The word at the pointer must not be 0xFFFF FFFF (i.e.
#             -1 cannot be a class tag)
#
#        These tests are performed whenever any data could be a pointer
#        to keep any non-pointers from being updated accidentally.  The
#        functions "_GenGC_ChkCopy" and "_GenGC_OfsCopy" are responsible
#        for these checks.
#
#     4) The size stored in the object does not include the word required
#        to store the eyecatcher for the object in the heap.  This allows
#        the prototype objects to not require its own eyecatcher.  Also,
#        a size of 0 is invalid because it is used as a flag by the garbage
#        collector to indicate a forwarding pointer in the "obj_disp" field.
#
#     5) Roots are contained in the following areas: the stack, registers
#        specified in the REG mask, and the assignment table.
#

#
# Constants
#

#
# GenGC header offsets from "heap_start"
#

GenGC_HDRSIZE=44				# size of GenGC header
GenGC_HDRL0=0					# pointers to GenGC areas
GenGC_HDRL1=4
GenGC_HDRL2=8
GenGC_HDRL3=12
GenGC_HDRL4=16
GenGC_HDRMAJOR0=20				# history of major collections
GenGC_HDRMAJOR1=24
GenGC_HDRMINOR0=28				# history of minor collections
GenGC_HDRMINOR1=32
GenGC_HDRSTK=36					# start of stack
GenGC_HDRREG=40					# current REG mask

#
# Granularity of heap expansion
#
#   The heap is always expanded in multiples of 2^k, where
#   k is the granularity.
#

GenGC_HEAPEXPGRAN=14				# 2^14=16K

#
# Old to usable heap size ratio
#
#   After a major collection, the ratio of size of old area to the usable
#   size of the heap is at most 1/(2^k) where k is the value provided.
#

GenGC_OLDRATIO=2				# 1/(2^2)=.25=25%

#
# Mask to speficy which registers can be automatically updated
# when a garbage collection occurs.  The Automatic Register Update
# (ARU) mask has a bit set for all possible registers the
# garbage collector is able to handle.  The Register (REG) mask
# determines which register(s) are actually updated.
#
# BITS----------------------------
# 3 2         1         0
# 10987654321098765432109876543210
# --------------------------------
#
# 11000011011111110000000000000000  <-  Auto Register Update (ARU) mask
# +--++--++--++--++--++--++--++--+      $s0-$s6, $t8-$t9, $s8, $ra
#    C   3   7   F   0   0   0   0     ($16-$22, $24-$25, $30, $31)
#

GenGC_ARU_MASK=0xC37F0000

#
# Functions
#

#
# Initialization
#
#   Sets up the header information block for the garbage collector.
#   This block is located at the start of the heap ("heap_start")
#   and includes information needed by the garbage collector.  It
#   also calculates the barrier for the reserve and work areas and
#   sets the L2 pointer accordingly, rounding off in favor of the
#   reserve area.
#
#   INPUT:
#	$a0: start of stack
#	$a1: initial Register mask
#	$a2: end of heap
#	heap_start: start of the heap
#
#   OUTPUT:
#	$gp: lower bound of the work area
#	$s7: upper bound of the work area
#
#   Registers modified:
#	$t0, $t1, $v0, $a0
#

	.globl _GenGC_Init
_GenGC_Init:
	la	$t0 heap_start
	addiu	$t1 $t0 GenGC_HDRSIZE
	sw	$t1 GenGC_HDRL0($t0)		# save start of old area
	sw	$t1 GenGC_HDRL1($t0)		# save start of reserve area
	sub	$t1 $a2 $t1			# find reserve/work area barrier
	srl	$t1 $t1 1
	la	$v0 0xfffffffc
	and	$t1 $t1 $v0
	blez	$t1 _GenGC_Init_error		# heap initially to small
	sub	$gp $a2 $t1
	sw	$gp GenGC_HDRL2($t0)		# save start of work area	
	sw	$a2 GenGC_HDRL3($t0)		# save end of work area
	move	$s7 $a2				# set limit pointer
	sw	$0 GenGC_HDRMAJOR0($t0)		# clear histories
	sw	$0 GenGC_HDRMAJOR1($t0)
	sw	$0 GenGC_HDRMINOR0($t0)
	sw	$0 GenGC_HDRMINOR1($t0)
	sw	$a0 GenGC_HDRSTK($t0)		# save stack start
	sw	$a1 GenGC_HDRREG($t0)		# save register mask
	li	$v0 9				# get heap end
	move	$a0 $zero
	syscall					# sbrk
	sw	$v0 GenGC_HDRL4($t0)		# save heap limit
        la      $t0 _MemMgr_TEST                # Check if testing enabled
        lw      $t0 0($t0)
        beqz    $t0 _MemMgr_Test_false
        la      $a0 _GenGC_Init_test_msg        # tell user GC is in test mode
        li      $v0 4
        syscall
        j       _GenGC_Init_end
_MemMgr_Test_false:
        la      $a0 _GenGC_Init_msg             # tell user GC NOT in test mode
        li      $v0 4
        syscall
_GenGC_Init_end:
	jr	$ra				# return

_GenGC_Init_error:
	la	$a0 _GenGC_INITERROR		# show error message
	li	$v0 4
	syscall
	li	$v0 10				# exit
	syscall

#
# Record Assignment
#
#   Records an assignment in the assignment table.  Note that because
#   $s7 is always greater than $gp, an assignment can always be
#   recorded.
#
#   INPUT:
#	$a1: pointer to the pointer being modified
#	$s7: limit pointer of the work area
#	$gp: current allocation pointer
#	heap_start: start of heap
#
#   Registers modified:
#	$t0, $t1, $t2, $v0, $v1, $a1, $a2, $gp, $s7
#
#   sm: $a0 is explicitly saved in the GC case so that in the normal
#   case the caller need not save/restore $a0
#
#   sm: Apparently _GenGC_Collect wants $a0 to be the last+1 word
#   of the stack, rather than the last word; I've therefore changed
#     addiu   $a0 $sp 4
#   to
#     addiu   $a0 $sp 0     (i.e. move $a0 $sp)
#   Just in case this isn't exactly right, I've also put 0 into that 
#   last spot so it will definitely be safely ignored.
#

	.globl _GenGC_Assign
_GenGC_Assign:
	addiu	$s7 $s7 -4
	sw	$a1 0($s7)			# save pointer to assignment
	bgt	$s7 $gp _GenGC_Assign_done
	addiu	$sp $sp -8
	sw	$ra 8($sp)			# save return address
	sw	$a0 4($sp)			# sm: save $a0
	move    $a1 $0				# size
	addiu	$a0 $sp 0			# end of stack to collect
	sw      $0 0($sp)                       # play it safe with off-by-1
	jal	_GenGC_Collect
	lw	$ra 8($sp)			# restore return address
	lw	$a0 4($sp)			# restore $a0
	addiu	$sp $sp 8
_GenGC_Assign_done:
	jr	$ra				# return

	.globl	_gc_check
_gc_check:
	beqz	$a1, _gc_ok			# void is ok
	lw	$a2 obj_eyecatch($a1)		# and check if it is valid
	addiu	$a2 $a2 1
	bnez	$a2 _gc_abort
_gc_ok:
	jr	$ra

_gc_abort:		 
	la      $a0 _gc_abort_msg
	li	$v0 4
	syscall                  # print gc message
	li   	$v0 10
        syscall			 # exit


#
# Generational Garbage Collection
#
#   This function implements the generational garbage collection.
#   It first calls the minor collector, "_GenGC_MinorC", and then
#   updates its history in the header.  The breakpoint is then
#   calculated.  If the breakpoint is reached or there is still not
#   enough room to allocate the requested size, a major garbage
#   collection then takes place by calling "_GenGC_MajorC".  After
#   the major collection, the size of the old area is analyzed.  If
#   it is greater than 1/(2^GenGC_OLDRATIO) of the total usable heap
#   size (L0 to L3), the heap is expanded.  Also, if there is still not
#   enough room to allocate the requested size, the heap is expanded
#   further to make sure that the specified amount of memory can be
#   allocated. If there is enough room in the unused area (L3 to L4),
#   this memory is used and the heap is not expanded.  The $s7 and $gp
#   pointers are then set as well as the L2 pointer.  If a major collection
#   is not done, the X area is incorporated into the old area
#   (i.e. the L2 pointer is moved into L1) and $s7, $gp, and L2 are
#   then set.
#
#   INPUT:
#	$a0: end of stack
#	$a1: size will need to allocate in bytes
#	$s7: limit pointer of thw work area
#	$gp: current allocation pointer
#	heap_start: start of heap
#
#   OUTPUT:
#	$a1: size will need to allocate in bytes (unchanged)
#
#   Registers modified:
#	$t0, $t1, $t2, $t3, $t4, $v0, $v1, $a0, $a2, $gp, $s7
#

	.globl _GenGC_Collect
_GenGC_Collect:
	addiu	$sp $sp -12
	sw	$ra 12($sp)			# save return address
	sw	$a0 8($sp)			# save stack end
	sw	$a1 4($sp)			# save size
	la	$a0 _GenGC_COLLECT		# print collection message
	li	$v0 4
	syscall
	lw	$a0 8($sp)			# restore stack end
	jal	_GenGC_MinorC			# minor collection
	la	$a1 heap_start
	lw	$t1 GenGC_HDRMINOR1($a1)
	addu	$t1 $t1 $a0
	srl	$t1 $t1 1
	sw	$t1 GenGC_HDRMINOR1($a1)	# update histories
	sw	$a0 GenGC_HDRMINOR0($a1)
	move	$t0 $t1				# set $t0 to max of minor
	bgt	$t1 $a0 _GenGC_Collect_maxmaj
	move	$t0 $a0
_GenGC_Collect_maxmaj:
	lw	$t1 GenGC_HDRMAJOR0($a1)	# set $t1 to max of major
	lw	$t2 GenGC_HDRMAJOR1($a1)
	bgt	$t1 $t2 _GenGC_Collect_maxdef
	move	$t1 $t2
_GenGC_Collect_maxdef:
	lw	$t2 GenGC_HDRL3($a1)
	sub	$t0 $t2 $t0			# set $t0 to L3-$t0-$t1
	sub	$t0 $t0 $t1
	lw	$t1 GenGC_HDRL0($a1)		# set $t1 to L3-(L3-L0)/2
	sub	$t1 $t2 $t1
	srl	$t1 $t1 1
	sub	$t1 $t2 $t1
	blt	$t0 $t1 _GenGC_Collect_breakpt	# set $t0 to minimum of above
	move	$t0 $t1
_GenGC_Collect_breakpt:
	lw	$t1 GenGC_HDRL1($a1)		# get end of old area
	bge	$t1 $t0 _GenGC_Collect_major
	lw	$t0 GenGC_HDRL2($a1)
	lw	$t1 GenGC_HDRL3($a1)
	lw	$t2 4($sp)			# load requested size into $t2
	sub	$t0 $t1 $t0			# find reserve/work area barrier
	srl	$t0 $t0 1
	la	$t3 0xfffffffc
	and	$t0 $t0 $t3
	sub	$t0 $t1 $t0			# reserve/work barrier
	addu	$t2 $t0 $t2			# test allocation
	bge	$t2 $t1 _GenGC_Collect_major	# check if work area too small
_GenGC_Collect_nomajor:
	lw	$t1 GenGC_HDRL2($a1)
	sw	$t1 GenGC_HDRL1($a1)		# expand old area
	sw	$t0 GenGC_HDRL2($a1)		# set new reserve/work barrier
	move	$gp $t0				# set $gp
	lw	$s7 GenGC_HDRL3($a1)		# load limit into $s7
	b	_GenGC_Collect_done
_GenGC_Collect_major:
	la	$a0 _GenGC_Major		# print collection message
	li	$v0 4
	syscall
	lw	$a0 8($sp)			# restore stack end
	jal	_GenGC_MajorC			# major collection
	la	$a1 heap_start
	lw	$t1 GenGC_HDRMAJOR1($a1)
	addu	$t1 $t1 $a0
	srl	$t1 $t1 1
	sw	$t1 GenGC_HDRMAJOR1($a1)	# update histories
	sw	$a0 GenGC_HDRMAJOR0($a1)
	lw	$t1 GenGC_HDRL3($a1)		# find ratio of the old area
	lw	$t0 GenGC_HDRL0($a1)
	sub	$t1 $t1 $t0
	srl	$t1 $t1 GenGC_OLDRATIO
	addu	$t1 $t0 $t1
	lw	$t0 GenGC_HDRL1($a1)
	sub	$t0 $t0 $t1
	sll	$t0 $t0 GenGC_OLDRATIO		# amount to expand in $t0
	lw	$t1 GenGC_HDRL3($a1)		# load L3
	lw	$t2 GenGC_HDRL1($a1)		# load L1
	sub	$t2 $t1 $t2
	srl	$t2 $t2 1
	la	$t3 0xfffffffc
	and	$t2 $t2 $t3
	sub	$t1 $t1 $t2			# reserve/work barrier
	lw	$t2 4($sp)			# restore size
	addu	$t1 $t1 $t2
	lw	$t2 GenGC_HDRL3($a1)		# load L3
	sub	$t1 $t1 $t2			# test allocation
	addiu	$t1 $t1 4			# adjust for round off errors
	sll	$t1 $t1 1			# need to allocate $t1 memory
	blt	$t1 $t0 _GenGC_Collect_enough	# put max of $t0, $t1 in $t0
	move	$t0 $t1
_GenGC_Collect_enough:
	blez	$t0 _GenGC_Collect_setL2	# no need to expand
	addiu	$t1 $0 1			# put 1 in $t1
	sll	$t1 $t1 GenGC_HEAPEXPGRAN	# get granularity of expansion
	addiu	$t1 $t1 -1			# align to granularity
	addu	$t0 $t0 $t1
	nor	$t1 $t1 $t1
	and	$t0 $t0 $t1			# total memory needed
	lw	$t1 GenGC_HDRL3($a1)		# load L3
	lw	$t2 GenGC_HDRL4($a1)		# load L4
	sub	$t1 $t2 $t1
	sub	$t2 $t0 $t1			# actual amount to allocate
	bgtz	$t2 _GenGC_Collect_getmem	# check if really need to allocate
_GenGC_Collect_xfermem:
	lw	$s7 GenGC_HDRL3($a1)		# load L3
	addu	$s7 $s7 $t0			# expand by $t0, set $s7
	sw	$s7 GenGC_HDRL3($a1)		# save L3
	b	_GenGC_Collect_findL2
_GenGC_Collect_getmem:
	li	$v0 9				# sbrk
	move	$a0 $t2				# set the size to expand the heap
	syscall
	li	$v0 9
	move	$a0 $zero
	syscall					# get new end of heap in $v0
	sw	$v0 GenGC_HDRL4($a1)		# save L4
	sw	$v0 GenGC_HDRL3($a1)		# save L3
	move	$s7 $v0				# set $s7
	b	_GenGC_Collect_findL2
_GenGC_Collect_setL2:
	lw	$s7 GenGC_HDRL3($a1)		# load L3
_GenGC_Collect_findL2:
	lw	$t1 GenGC_HDRL1($a1)		# load L1
	sub	$t1 $s7 $t1
	srl	$t1 $t1 1
	la	$t0 0xfffffffc
	and	$t1 $t1 $t0
	sub	$gp $s7 $t1			# reserve/work barrier
	sw	$gp GenGC_HDRL2($a1)		# save L2
_GenGC_Collect_done:

# Clear new generation to catch missing pointers
	move	$t0 $gp
_GenGC_Clear_loop:
	sw	$zero 0($t0)
	addiu	$t0 $t0 4
	blt	$t0 $s7 _GenGC_Clear_loop

	lw	$a1 4($sp)			# restore size
	lw	$ra 12($sp)			# restore return address
	addiu	$sp $sp 12
	jr	$ra				# return

#
# Check and Copy an Object
#
#   Checks that the input pointer points to an object is a heap
#   object.  If so, it then checks for a forwarding pointer by
#   checking for an object size of 0.  If found, the forwarding
#   pointer is returned.  If not found, the object is copied to $gp
#   and a pointer to it is returned.  The following tests are done to
#   determine if the object is a heap object:
#
#     1) The pointer is within the specified limits
#     2) The pointer is even
#     3) The word before the pointer is the eye catcher 0xFFFF FFFF
#     4) The word at the pointer is a valid tag (i.e. not equal to
#        0xFFFF FFFF)
#
#   INPUT:
#	$a0: pointer to check and copy
#	$a1: lower bound object should be within.
#	$a2: upper bound object should be within.
#	$gp: current allocation pointer
#
#   OUTPUT:
#	$a0: if input points to a heap object then it is set to the
#            new location of object.  If not, it is unchanged.
#	$a1: lower bound object should be within. (unchanged)
#	$a2: upper bound object should be within. (unchanged)
#
#   Registers modified:
#	$t0, $t1, $t2, $v0, $a0, $gp
#

	.globl _GenGC_ChkCopy
_GenGC_ChkCopy:
	blt	$a0 $a1 _GenGC_ChkCopy_done	# check bounds
	bge	$a0 $a2 _GenGC_ChkCopy_done
	andi	$t2 $a0 1			# check if odd
	bnez	$t2 _GenGC_ChkCopy_done
	addiu	$t2 $0 -1
	lw	$t1 obj_eyecatch($a0)		# check eyecatcher
	bne	$t2 $t1 _gc_abort
	lw	$t1 obj_tag($a0)		# check object tag
	beq	$t2 $t1 _GenGC_ChkCopy_done
	lw	$t1 obj_size($a0)		# get size of object
	beqz	$t1 _GenGC_ChkCopy_forward	# if size = 0, get forwarding pointer
	move	$t0 $a0				# save pointer to old object in $t0
	addiu	$gp $gp 4			# allocate memory for eyecatcher
	move	$a0 $gp				# get address of new object
	sw	$t2 obj_eyecatch($a0)		# save eye catcher
	sll	$t1 $t1 2			# convert words to bytes
	addu	$t1 $t0 $t1			# set $t1 to limit of copy
	move	$t2 $t0				# set $t2 to old object
_GenGC_ChkCopy_loop:
	lw	$v0 0($t0)			# copy
	sw	$v0 0($gp)
	addiu	$t0 $t0 4			# update each index
	addiu	$gp $gp 4
	bne	$t0 $t1 _GenGC_ChkCopy_loop	# check for limit of copy
	sw	$0 obj_size($t2)		# set size to 0
	sw	$a0 obj_disp($t2)		# save forwarding pointer
_GenGC_ChkCopy_done:
	jr	$ra				# return
_GenGC_ChkCopy_forward:
	lw	$a0 obj_disp($a0)		# get forwarding pointer
	jr	$ra				# return


#
# Minor Garbage Collection
#
#   This garbage collector is run when ever the space in the work
#   area is used up by objects and the assignment table.  The live
#   objects are found and copied to the reserve area.  The L2 pointer
#   is then set to the end of the live objects.  The collector consists
#   of six phases:
#
#     1) Set $gp into the reserve area and set the inputs for ChkCopy
#
#     2) Scan the stack for root pointers into the heap.  The beginning
#        of the stack is in the header and the end is an input to this
#        function.  Look for the appropriate stack flags and act
#        accordingly.  Use "_GenGC_ChkCopy" to validate the pointer and
#        get the new pointer, and then update the stack entry.
#
#     3) Check the registers specified in the Register (REG) mask to
#        automatically update.  This mask is stored in the header.  If
#        bit #n in the mask is set, register #n will be passed to
#        "_GenGC_ChkCopy" and updated with its result.  "_GenGC_SetRegMask"
#        can be used to update this mask.
#
#     4) The assignemnt table is now checked.  $s7 is moved from its
#        current position until it hits the L3 pointer.  Each entry is a
#        pointer to the pointer that must be checked.  Again,
#        "_GenGC_ChkCopy" is used and the pointer updated.
#
#     5) At this point, all root objects are in the reserve area.  This
#        area is now traversed object by object (from L1 to $gp).  It
#        results in a breadth first search of the live objects collected.
#        All attributes of objects are treated as pointers except the
#        "Int", "Bool", and "String" objects.  The first two are skipped
#        completely, and the first attribute of the string object is
#        analyzed (should be a pointer to an "Int" object).
#
#     6) At this point, L2 is set to the end of the live objects in the
#        reserve area.  This is in preparation for a major collection.
#        The size of all the live objects collected is then computed and
#        returned.
#
#   INPUT:
#	$a0: end of stack
#	$s7: limit pointer of this area of storage
#	$gp: current allocation pointer
#	heap_start: start of heap
#
#   OUTPUT:
#	$a0: size of all live objects collected
#
#   Registers modified:
#	$t0, $t1, $t2, $t3, $t4, $v0, $v1, $a0, $a1, $a2, $gp, $s7
#

	.globl _GenGC_MinorC
_GenGC_MinorC:
	addiu	$sp $sp -20
	sw	$ra 20($sp)			# save return address
	la	$t0 heap_start
	lw	$a1 GenGC_HDRL2($t0)		# set lower bound to work area
	move	$a2 $s7				# set upper bound for ChkCopy
	lw	$gp GenGC_HDRL1($t0)		# set $gp into reserve area
	sw	$a0 16($sp)			# save stack end
	lw	$t0 GenGC_HDRSTK($t0)		# set $t0 to stack start
	move	$t1 $a0				# set $t1 to stack end
	ble	$t0 $t1 _GenGC_MinorC_stackend	# check for empty stack
_GenGC_MinorC_stackloop: 			# $t1 stack end, $t0 index
	addiu	$t0 $t0 -4			# update index
	sw	$t0 12($sp)			# save stack index
	lw	$a0 4($t0)			# get stack item
	jal	_GenGC_ChkCopy			# check and copy
	lw	$t0 12($sp)			# load stack index
	sw	$a0 4($t0)
	lw	$t1 16($sp)			# restore stack end
	bgt	$t0 $t1 _GenGC_MinorC_stackloop	# loop
_GenGC_MinorC_stackend:
	la	$t0 heap_start
	lw	$t0 GenGC_HDRREG($t0)		# get Register mask
	sw	$t0 16($sp)			# save Register mask
_GenGC_MinorC_reg16:
	srl	$t0 $t0 16			# shift to proper bit
	andi	$t1 $t0 1
	beq	$t1 $0 _GenGC_MinorC_reg17	# check if set
	move	$a0 $16				# set test pointer
	jal	_GenGC_ChkCopy			# check and copy
	move	$16 $a0				# update register
_GenGC_MinorC_reg17:
	lw	$t0 16($sp)			# restore mask
	srl	$t0 $t0 17			# shift to proper bit
	andi	$t1 $t0 1
	beq	$t1 $0 _GenGC_MinorC_reg18	# check if set
	move	$a0 $17				# set test pointer
	jal	_GenGC_ChkCopy			# check and copy
	move	$17 $a0				# update register
_GenGC_MinorC_reg18:
	lw	$t0 16($sp)			# restore mask
	srl	$t0 $t0 18			# shift to proper bit
	andi	$t1 $t0 1
	beq	$t1 $0 _GenGC_MinorC_reg19	# check if set
	move	$a0 $18				# set test pointer
	jal	_GenGC_ChkCopy			# check and copy
	move	$18 $a0				# update register
_GenGC_MinorC_reg19:
	lw	$t0 16($sp)			# restore mask
	srl	$t0 $t0 19			# shift to proper bit
	andi	$t1 $t0 1
	beq	$t1 $0 _GenGC_MinorC_reg20	# check if set
	move	$a0 $19				# set test pointer
	jal	_GenGC_ChkCopy			# check and copy
	move	$19 $a0				# update register
_GenGC_MinorC_reg20:
	lw	$t0 16($sp)			# restore mask
	srl	$t0 $t0 20			# shift to proper bit
	andi	$t1 $t0 1
	beq	$t1 $0 _GenGC_MinorC_reg21	# check if set
	move	$a0 $20				# set test pointer
	jal	_GenGC_ChkCopy			# check and copy
	move	$20 $a0				# update register
_GenGC_MinorC_reg21:
	lw	$t0 16($sp)			# restore mask
	srl	$t0 $t0 21			# shift to proper bit
	andi	$t1 $t0 1
	beq	$t1 $0 _GenGC_MinorC_reg22	# check if set
	move	$a0 $21				# set test pointer
	jal	_GenGC_ChkCopy			# check and copy
	move	$21 $a0				# update register
_GenGC_MinorC_reg22:
	lw	$t0 16($sp)			# restore mask
	srl	$t0 $t0 22			# shift to proper bit
	andi	$t1 $t0 1
	beq	$t1 $0 _GenGC_MinorC_reg24	# check if set
	move	$a0 $22				# set test pointer
	jal	_GenGC_ChkCopy			# check and copy
	move	$22 $a0				# update register
_GenGC_MinorC_reg24:
	lw	$t0 16($sp)			# restore mask
	srl	$t0 $t0 24			# shift to proper bit
	andi	$t1 $t0 1
	beq	$t1 $0 _GenGC_MinorC_reg25	# check if set
	move	$a0 $24				# set test pointer
	jal	_GenGC_ChkCopy			# check and copy
	move	$24 $a0				# update register
_GenGC_MinorC_reg25:
	lw	$t0 16($sp)			# restore mask
	srl	$t0 $t0 25			# shift to proper bit
	andi	$t1 $t0 1
	beq	$t1 $0 _GenGC_MinorC_reg30	# check if set
	move	$a0 $25				# set test pointer
	jal	_GenGC_ChkCopy			# check and copy
	move	$25 $a0				# update register
_GenGC_MinorC_reg30:
	lw	$t0 16($sp)			# restore mask
	srl	$t0 $t0 30			# shift to proper bit
	andi	$t1 $t0 1
	beq	$t1 $0 _GenGC_MinorC_reg31	# check if set
	move	$a0 $30				# set test pointer
	jal	_GenGC_ChkCopy			# check and copy
	move	$30 $a0				# update register
_GenGC_MinorC_reg31:
	lw	$t0 16($sp)			# restore mask
	srl	$t0 $t0 31			# shift to proper bit
	andi	$t1 $t0 1
	beq	$t1 $0 _GenGC_MinorC_regend	# check if set
	move	$a0 $31				# set test pointer
	jal	_GenGC_ChkCopy			# check and copy
	move	$31 $a0				# update register
_GenGC_MinorC_regend:
	la	$t0 heap_start
	lw	$t3 GenGC_HDRL0($t0)		# lower limit of old area
	lw	$t4 GenGC_HDRL1($t0)		# upper limit of old area
	lw	$t0 GenGC_HDRL3($t0)		# get L3
	sw	$t0 16($sp)			# save index limit
	bge	$s7 $t0 _GenGC_MinorC_assnend	# check for no assignments
_GenGC_MinorC_assnloop:				# $s7 index, $t0 limit
	lw	$a0 0($s7)			# get table entry
	blt	$a0 $t3 _GenGC_MinorC_assnnext	# must point into old area
	bge	$a0 $t4 _GenGC_MinorC_assnnext
	lw	$a0 0($a0)			# get pointer to check
	jal	_GenGC_ChkCopy			# check and copy
	lw	$t0 0($s7)
	sw	$a0 0($t0)			# update pointer
	lw	$t0 16($sp)			# restore index limit
_GenGC_MinorC_assnnext:
	addiu	$s7 $s7 4			# update index
	blt	$s7 $t0 _GenGC_MinorC_assnloop	# loop
_GenGC_MinorC_assnend:
	la	$t0 heap_start
	lw	$t0 GenGC_HDRL1($t0)		# start of reserve area
	bge	$t0 $gp _GenGC_MinorC_heapend	# check for no objects
_GenGC_MinorC_heaploop:				# $t0: index, $gp: limit
	addiu	$t0 $t0 4			# skip over eyecatcher
	addiu	$t1 $0 -1			# check for eyecatcher
	lw	$t2 obj_eyecatch($t0)
	bne	$t1 $t2 _GenGC_MinorC_error	# eyecatcher not found
	lw	$a0 obj_size($t0)		# get object size
	sll	$a0 $a0 2			# words to bytes
	lw	$t1 obj_tag($t0)		# get the object's tag
	lw	$t2 _int_tag			# test for int object
	beq	$t1 $t2 _GenGC_MinorC_int
	lw	$t2 _bool_tag			# test for bool object
	beq	$t1 $t2 _GenGC_MinorC_bool
	lw	$t2 _string_tag			# test for string object
	beq	$t1 $t2 _GenGC_MinorC_string
_GenGC_MinorC_other:
	addi	$t1 $t0 obj_attr		# start at first attribute
	add	$t2 $t0 $a0			# limit of attributes
	bge	$t1 $t2 _GenGC_MinorC_nextobj	# check for no attributes
	sw	$t0 16($sp)			# save pointer to object
	sw	$a0 12($sp)			# save object size
	sw	$t2 4($sp)			# save limit
_GenGC_MinorC_objloop:				# $t1: index, $t2: limit
	sw	$t1 8($sp)			# save index
	lw	$a0 0($t1)			# set pointer to check
	jal	_GenGC_ChkCopy			# check and copy
	lw	$t1 8($sp)			# restore index
	sw	$a0 0($t1)			# update object pointer
	lw	$t2 4($sp)			# restore limit
	addiu	$t1 $t1 4
	blt	$t1 $t2 _GenGC_MinorC_objloop	# loop
_GenGC_MinorC_objend:
	lw	$t0 16($sp)			# restore pointer to object
	lw	$a0 12($sp)			# restore object size
	b	_GenGC_MinorC_nextobj		# next object
_GenGC_MinorC_string:
	sw	$t0 16($sp)			# save pointer to object
	sw	$a0 12($sp)			# save object size
	lw	$a0 str_size($t0)		# set test pointer
	jal	_GenGC_ChkCopy			# check and copy
	lw	$t0 16($sp)			# restore pointer to object
	sw	$a0 str_size($t0)		# update size pointer
	lw	$a0 12($sp)			# restore object size
_GenGC_MinorC_int:
_GenGC_MinorC_bool:
_GenGC_MinorC_nextobj:
	add	$t0 $t0 $a0			# find next object
	blt	$t0 $gp _GenGC_MinorC_heaploop	# loop
_GenGC_MinorC_heapend:
	la	$t0 heap_start
	sw	$gp GenGC_HDRL2($t0)		# set L2 to $gp
	lw	$a0 GenGC_HDRL1($t0)
	sub	$a0 $gp $a0			# find size after collection
	lw	$ra 20($sp)			# restore return address
	addiu	$sp $sp 20
	jr	$ra				# return
_GenGC_MinorC_error:
	la	$a0 _GenGC_MINORERROR		# show error message
	li	$v0 4
	syscall
	li	$v0 10				# exit
	syscall

#
# Check and Copy an Object with an Offset
#
#   Checks that the input pointer points to an object is a heap object.
#   If so, the pointer is checked to be in one of two areas.  If the
#   pointer is in the X area, L0-L1 is added to the pointer, and the
#   new pointer is returned.  If the pointer points within the old area,
#   it then checks for a forwarding pointer by checking for an object
#   size of 0.  If found, the forwarding pointer is returned.  If not
#   found, the heap is then analyzed to make sure the object can be
#   copied.  It then expands the heap if necessary (updating only $s7),
#   and the copies the object to the $gp pointer.  It takes the new
#   pointer, adds L0-L1 to it, then saves this modified new pointer in
#   the forwarding (obj_disp) field and sets the flag (obj_size to 0).
#   Finally, it returns this pointer.  Note that this pointer does not
#   actually point to the object at this time.  This entire area will
#   later be block copied.  After that, this pointer will be valid.
#   The same tests are done here as in "_GenGC_ChkCopy" to verify that
#   this is a heap object.
#
#   INPUT:
#	$a0: pointer to check and copy with an offset
#	$a1: L0 pointer
#	$a2: L1 pointer
#	$v1: L2 pointer
#	$gp: current allocation pointer
#	$s7: L4 pointer
#
#   OUTPUT:
#	$a0: if input points to a heap object then it is set to the
#            new location of object.  If not, it is unchanged.
#	$a1: L0 pointer (unchanged)
#	$a2: L1 pointer (unchanged)
#	$v1: L2 pointer (unchanged)
#
#   Registers modified:
#	$t0, $t1, $t2, $v0, $a0, $gp, $s7
#

	.globl _GenGC_OfsCopy
_GenGC_OfsCopy:
	blt	$a0 $a1 _GenGC_OfsCopy_done	# check lower bound
	bge	$a0 $v1 _GenGC_OfsCopy_done	# check upper bound
	andi	$t2 $a0 1			# check if odd
	bnez	$t2 _GenGC_OfsCopy_done
	addiu	$t2 $0 -1
	lw	$t1 obj_eyecatch($a0)		# check eyecatcher
	bne	$t2 $t1 _gc_abort
	lw	$t1 obj_tag($a0)		# check object tag
	beq	$t2 $t1 _GenGC_OfsCopy_done
	blt	$a0 $a2 _GenGC_OfsCopy_old	# check if old, X object
	sub	$v0 $a1 $a2			# compute offset
	add	$a0 $a0 $v0			# apply pointer offset
	jr	$ra				# return
_GenGC_OfsCopy_old:
	lw	$t1 obj_size($a0)		# get size of object
	sll	$t1 $t1 2			# convert words to bytes
	beqz	$t1 _GenGC_OfsCopy_forward	# if size = 0, get forwarding pointer
	move	$t0 $a0				# save pointer to old object in $t0
	addu	$v0 $gp $t1			# test allocation
	addiu	$v0 $v0 4
	blt	$v0 $s7 _GenGC_OfsCopy_memok	# check if enoguh room for object
	sub	$a0 $v0 $s7			# amount to expand minus 1
	addiu	$v0 $0 1
	sll	$v0 $v0 GenGC_HEAPEXPGRAN
	add	$a0 $a0 $v0
	addiu	$v0 $v0 -1
	nor	$v0 $v0 $v0			# get grain mask
	and	$a0 $a0 $v0			# align to grain size
	li	$v0 9
	syscall					# expand heap
	li	$v0 9
	move	$a0 $0
	syscall					# get end of heap in $v0
	move	$s7 $v0				# save heap end in $s7
	move	$a0 $t0				# restore pointer to old object in $a0
_GenGC_OfsCopy_memok:
	addiu	$gp $gp 4			# allocate memory for eyecatcher
	move	$a0 $gp				# get address of new object
	sw	$t2 obj_eyecatch($a0)		# save eye catcher
	addu	$t1 $t0 $t1			# set $t1 to limit of copy
	move	$t2 $t0				# set $t2 to old object
_GenGC_OfsCopy_loop:
	lw	$v0 0($t0)			# copy
	sw	$v0 0($gp)
	addiu	$t0 $t0 4			# update each index
	addiu	$gp $gp 4
	bne	$t0 $t1 _GenGC_OfsCopy_loop	# check for limit of copy
	sw	$0 obj_size($t2)		# set size to 0
	sub	$v0 $a1 $a2			# compute offset
	add	$a0 $a0 $v0			# apply pointer offset
	sw	$a0 obj_disp($t2)		# save forwarding pointer
_GenGC_OfsCopy_done:
	jr	$ra				# return
_GenGC_OfsCopy_forward:
	lw	$a0 obj_disp($a0)		# get forwarding pointer
	jr	$ra				# return

#
# Major Garbage Collection
#
#   This collection occurs when ever the old area grows beyond a specified
#   point.  The minor collector sets up the Old, X, and New areas for
#   this collector.  It then collects all the live objects in the old
#   area (L0 to L1) into the new area (L2 to L3).  This collection consists
#   of five phases:
#
#     1) Set $gp into the new area (L2), and $s7 to L4.  Also set the
#        inputs for "_GenGC_OfsCopy".
#
#     2) Traverse the stack (see the minor collector) using "_GenGC_OfsCopy".
#
#     3) Check the registers (see the minor collector) using "_GenGC_OfsCopy".
#
#     4) Traverse the heap from L1 to $gp using "_GenGC_OfsCopy".  Note
#        that this includes the X area.  (see the minor collector)
#
#     5) Block copy the region L1 to $gp back L1-L0 bytes to create the
#        next old area.  Save the end in L1.  Calculate the size of the
#        live objects collected from the old area and return this value.
#
#   Note that the pointers returned by "_GenGC_OfsCopy" are not valid
#   until the block copy is done.
#
#   INPUT:
#	$a0: end of stack
#	heap_start: start of heap
#
#   OUTPUT:
#	$a0: size of all live objects collected
#
#   Registers modified:
#	$t0, $t1, $t2, $v0, $v1, $a0, $a1, $a2, $gp, $s7
#

	.globl _GenGC_MajorC
_GenGC_MajorC:
	addiu	$sp $sp -20
	sw	$ra 20($sp)			# save return address
	la	$t0 heap_start
	lw	$s7 GenGC_HDRL4($t0)		# limit pointer for collection
	lw	$gp GenGC_HDRL2($t0)		# allocation pointer for collection
	lw	$a1 GenGC_HDRL0($t0)		# set inputs for OfsCopy
	lw	$a2 GenGC_HDRL1($t0)
	lw	$v1 GenGC_HDRL2($t0)
	sw	$a0 16($sp)			# save stack end
	lw	$t0 GenGC_HDRSTK($t0)		# set $t0 to stack start
	move	$t1 $a0				# set $t1 to stack end
	ble	$t0 $t1 _GenGC_MajorC_stackend	# check for empty stack
_GenGC_MajorC_stackloop: 			# $t1 stack end, $t0 index
	addiu	$t0 $t0 -4			# update index
	sw	$t0 12($sp)			# save stack index
	lw	$a0 4($t0)			# get stack item
	jal	_GenGC_OfsCopy			# check and copy
	lw	$t0 12($sp)			# load stack index
	sw	$a0 4($t0)
	lw	$t1 16($sp)			# restore stack end
	bgt	$t0 $t1 _GenGC_MajorC_stackloop	# loop
_GenGC_MajorC_stackend:
	la	$t0 heap_start
	lw	$t0 GenGC_HDRREG($t0)		# get Register mask
	sw	$t0 16($sp)			# save Register mask
_GenGC_MajorC_reg16:
	srl	$t0 $t0 16			# shift to proper bit
	andi	$t1 $t0 1
	beq	$t1 $0 _GenGC_MajorC_reg17	# check if set
	move	$a0 $16				# set test pointer
	jal	_GenGC_OfsCopy			# check and copy
	move	$16 $a0				# update register
_GenGC_MajorC_reg17:
	lw	$t0 16($sp)			# restore mask
	srl	$t0 $t0 17			# shift to proper bit
	andi	$t1 $t0 1
	beq	$t1 $0 _GenGC_MajorC_reg18	# check if set
	move	$a0 $17				# set test pointer
	jal	_GenGC_OfsCopy			# check and copy
	move	$17 $a0				# update register
_GenGC_MajorC_reg18:
	lw	$t0 16($sp)			# restore mask
	srl	$t0 $t0 18			# shift to proper bit
	andi	$t1 $t0 1
	beq	$t1 $0 _GenGC_MajorC_reg19	# check if set
	move	$a0 $18				# set test pointer
	jal	_GenGC_OfsCopy			# check and copy
	move	$18 $a0				# update register
_GenGC_MajorC_reg19:
	lw	$t0 16($sp)			# restore mask
	srl	$t0 $t0 19			# shift to proper bit
	andi	$t1 $t0 1
	beq	$t1 $0 _GenGC_MajorC_reg20	# check if set
	move	$a0 $19				# set test pointer
	jal	_GenGC_OfsCopy			# check and copy
	move	$19 $a0				# update register
_GenGC_MajorC_reg20:
	lw	$t0 16($sp)			# restore mask
	srl	$t0 $t0 20			# shift to proper bit
	andi	$t1 $t0 1
	beq	$t1 $0 _GenGC_MajorC_reg21	# check if set
	move	$a0 $20				# set test pointer
	jal	_GenGC_OfsCopy			# check and copy
	move	$20 $a0				# update register
_GenGC_MajorC_reg21:
	lw	$t0 16($sp)			# restore mask
	srl	$t0 $t0 21			# shift to proper bit
	andi	$t1 $t0 1
	beq	$t1 $0 _GenGC_MajorC_reg22	# check if set
	move	$a0 $21				# set test pointer
	jal	_GenGC_OfsCopy			# check and copy
	move	$21 $a0				# update register
_GenGC_MajorC_reg22:
	lw	$t0 16($sp)			# restore mask
	srl	$t0 $t0 22			# shift to proper bit
	andi	$t1 $t0 1
	beq	$t1 $0 _GenGC_MajorC_reg24	# check if set
	move	$a0 $22				# set test pointer
	jal	_GenGC_OfsCopy			# check and copy
	move	$22 $a0				# update register
_GenGC_MajorC_reg24:
	lw	$t0 16($sp)			# restore mask
	srl	$t0 $t0 24			# shift to proper bit
	andi	$t1 $t0 1
	beq	$t1 $0 _GenGC_MajorC_reg25	# check if set
	move	$a0 $24				# set test pointer
	jal	_GenGC_OfsCopy			# check and copy
	move	$24 $a0				# update register
_GenGC_MajorC_reg25:
	lw	$t0 16($sp)			# restore mask
	srl	$t0 $t0 25			# shift to proper bit
	andi	$t1 $t0 1
	beq	$t1 $0 _GenGC_MajorC_reg30	# check if set
	move	$a0 $25				# set test pointer
	jal	_GenGC_OfsCopy			# check and copy
	move	$25 $a0				# update register
_GenGC_MajorC_reg30:
	lw	$t0 16($sp)			# restore mask
	srl	$t0 $t0 30			# shift to proper bit
	andi	$t1 $t0 1
	beq	$t1 $0 _GenGC_MajorC_reg31	# check if set
	move	$a0 $30				# set test pointer
	jal	_GenGC_OfsCopy			# check and copy
	move	$30 $a0				# update register
_GenGC_MajorC_reg31:
	lw	$t0 16($sp)			# restore mask
	srl	$t0 $t0 31			# shift to proper bit
	andi	$t1 $t0 1
	beq	$t1 $0 _GenGC_MajorC_regend	# check if set
	move	$a0 $31				# set test pointer
	jal	_GenGC_OfsCopy			# check and copy
	move	$31 $a0				# update register
_GenGC_MajorC_regend:
	la	$t0 heap_start
	lw	$t0 GenGC_HDRL1($t0)		# start of X area
	bge	$t0 $gp _GenGC_MajorC_heapend	# check for no objects
_GenGC_MajorC_heaploop:				# $t0: index, $gp: limit
	addiu	$t0 $t0 4			# skip over eyecatcher
	addiu	$t1 $0 -1			# check for eyecatcher
	lw	$t2 obj_eyecatch($t0)
	bne	$t1 $t2 _GenGC_MajorC_error	# eyecatcher not found
	lw	$a0 obj_size($t0)		# get object size
	sll	$a0 $a0 2			# words to bytes
	lw	$t1 obj_tag($t0)		# get the object's tag
	lw	$t2 _int_tag			# test for int object
	beq	$t1 $t2 _GenGC_MajorC_int
	lw	$t2 _bool_tag			# test for bool object
	beq	$t1 $t2 _GenGC_MajorC_bool
	lw	$t2 _string_tag			# test for string object
	beq	$t1 $t2 _GenGC_MajorC_string
_GenGC_MajorC_other:
	addi	$t1 $t0 obj_attr		# start at first attribute
	add	$t2 $t0 $a0			# limit of attributes
	bge	$t1 $t2 _GenGC_MajorC_nextobj	# check for no attributes
	sw	$t0 16($sp)			# save pointer to object
	sw	$a0 12($sp)			# save object size
	sw	$t2 4($sp)			# save limit
_GenGC_MajorC_objloop:				# $t1: index, $t2: limit
	sw	$t1 8($sp)			# save index
	lw	$a0 0($t1)			# set pointer to check
	jal	_GenGC_OfsCopy			# check and copy
	lw	$t1 8($sp)			# restore index
	sw	$a0 0($t1)			# update object pointer
	lw	$t2 4($sp)			# restore limit
	addiu	$t1 $t1 4
	blt	$t1 $t2 _GenGC_MajorC_objloop	# loop
_GenGC_MajorC_objend:
	lw	$t0 16($sp)			# restore pointer to object
	lw	$a0 12($sp)			# restore object size
	b	_GenGC_MajorC_nextobj		# next object
_GenGC_MajorC_string:
	sw	$t0 16($sp)			# save pointer to object
	sw	$a0 12($sp)			# save object size
	lw	$a0 str_size($t0)		# set test pointer
	jal	_GenGC_OfsCopy			# check and copy
	lw	$t0 16($sp)			# restore pointer to object
	sw	$a0 str_size($t0)		# update size pointer
	lw	$a0 12($sp)			# restore object size
_GenGC_MajorC_int:
_GenGC_MajorC_bool:
_GenGC_MajorC_nextobj:
	add	$t0 $t0 $a0			# find next object
	blt	$t0 $gp _GenGC_MajorC_heaploop	# loop
_GenGC_MajorC_heapend:
	la	$t0 heap_start
	lw	$a0 GenGC_HDRL2($t0)		# get end of collection
	sub	$a0 $gp $a0			# get length after collection
	lw	$t1 GenGC_HDRL0($t0)		# get L0
	lw	$t2 GenGC_HDRL1($t0)		# get L1
	bge	$t2 $gp _GenGC_MajorC_bcpyend	# test for empty copy
_GenGC_MajorC_bcpyloop:				# $t2 index, $gp limit, $t1 dest
	lw	$v0 0($t2)			# copy
	sw	$v0 0($t1)
	addiu	$t2 $t2 4			# update each index
	addiu	$t1 $t1 4
	bne	$t2 $gp _GenGC_MajorC_bcpyloop	# loop
_GenGC_MajorC_bcpyend:
	sw	$s7 GenGC_HDRL4($t0)		# save end of heap
	lw	$t1 GenGC_HDRL0($t0)		# get L0
	lw	$t2 GenGC_HDRL1($t0)		# get L1
	sub	$t1 $t2 $t1			# find offset of block copy
	sub	$gp $gp $t1			# find end of old area
	sw	$gp GenGC_HDRL1($t0)		# save end of old area
	lw	$ra 20($sp)			# restore return address
	addiu	$sp $sp 20
	jr	$ra				# return
_GenGC_MajorC_error:
	la	$a0 _GenGC_MAJORERROR		# show error message
	li	$v0 4
	syscall
	li	$v0 10				# exit
	syscall

#
# Set the Register (REG) mask
#
#   If bit #n is set in the Register mask, register #n will be
#   automatically updated by the garbage collector.  Note that
#   this mask is masked (ANDed) with the ARU mask.  Only those
#   registers in the ARU mask can be updated automatically.
#
#   INPUT:
#	$a0: new Register (REG) mask
#	heap_start: start of the heap
#
#   Registers modified:
#	$t0
#

	.globl	_GenGC_SetRegMask
_GenGC_SetRegMask:
	li	$t0 GenGC_ARU_MASK		# apply Automatic Register Mask (ARU)
	and	$a0 $a0 $t0
	la	$t0 heap_start			# set $t0 to the start of the heap
	sw	$a0 GenGC_HDRREG($t0)		# save the Register mask
	jr	$ra				# return

#
# Query the Register (REG) mask
#
#   INPUT:
#	heap_start: start of the heap
#
#   OUTPUT:
#	$a0: current Register (REG) mask
#
#   Registers modified:
#	none
#

	.globl	_GenGC_QRegMask
_GenGC_QRegMask:
	la	$a0 heap_start			# set $a0 to the start of the heap
	lw	$a0 GenGC_HDRREG($a0)		# get the Register mask
	jr	$ra				# return


#
# NoGC Garbage Collector
#
#   NoGC does not attempt to do any garbage collection.
#   It simply expands the heap if more memory is needed.
#

#
# Some constants
#

NoGC_EXPANDSIZE=0x10000				# size to expand heap

#
# Initialization
#
#   INPUT:
#	none
#
#   OUTPUT:
#	$gp: lower bound of the work area
#	$s7: upper bound of the work area
#
#   Registers modified:
#	$a0, $v0
#
	.globl _NoGC_Init
_NoGC_Init:
	la	$gp heap_start			# set $gp to the start of the heap
	li	$v0 9				# get heap end
	move	$a0 $zero
	syscall					# sbrk
	move	$s7 $v0				# set limit pointer
	jr	$ra

#
# Collection
#
#   Expand the heap as necessary.
#
#   INPUT:
#	$a1: size will need to allocate in bytes
#	$s7: limit pointer of thw work area
#	$gp: current allocation pointer
#
#   OUTPUT:
#	$a1: size will need to allocate in bytes (unchanged)
#
#   Registers modified:
#	$t0, $a0, $v0, $gp, $s7
#

	.globl _NoGC_Collect
_NoGC_Collect:
	la	$a0 _NoGC_COLLECT		# show collection message
	li	$v0 4
	syscall
_NoGC_Collect_loop:
	add	$t0 $gp $a1			# test allocation
	blt	$t0 $s7 _NoGC_Collect_ok	# stop if enough
	li	$v0 9				# expand heap
	li	$a0 NoGC_EXPANDSIZE		# set the size to expand the heap
	syscall					# sbrk
	li	$v0 9				# get heap end
	move	$a0 $zero
	syscall					# sbrk
	move	$s7 $v0				# set limit pointer
	b	_NoGC_Collect_loop		# loop
_NoGC_Collect_ok:
	jr	$ra				# return