# Shawn Olson
# Class: C SC 252
# Instructor: Patrick Homer
#
# **prog7.s**
#
# Purpose: Create a recursive subroutine reverseWords that takes in a string and prints the words
# in the string in reverse order

.data
 
mainNumStrings:
        .word 4
mainStrings:
        .word mainStr1
        .word mainStr3
        .word mainStr4
        .word mainStr5
 
mainStr1:   .asciiz "One here With some CapitALS"
mainStr3:   .asciiz "AND ONE THAT IS ALL CAPS"
mainStr4:   .asciiz "and one that is all lower"
mainStr5:   .asciiz ";298stuff297that9872surrounds9782words!!@#$here(*&"
 
mainNewline:
            .asciiz "\n"
 
.text
main:
        # Function prologue -- even main has one
        subu  $sp, $sp, 24       # allocate stack space -- default of 24 here
        sw    $fp, 0($sp)        # save caller's frame pointer
        sw    $ra, 4($sp)        # save return address
        addiu $fp, $sp, 24       # setup main's frame pointer
 
# for (i = 0; i < mainNumStrings; i++ )
#    load address of string into $a0
#    call reverseWords
 
        # $s0 = i
        addi  $s0, $zero, 0
        # $s1 = mainNumStrings
        la    $t0, mainNumStrings
        lw    $s1, 0($t0)
        # $s2 = address of mainStrings
        la    $s2, mainStrings
        
MainLoopBegin:
        slt   $t0, $s0, $s1      # $t0 = $s0 < $s1
        beq   $t0, $zero, MainLoopEnd
        
        # print the string
        lw    $a0, 0($s2)        # $a0 = addr of a string
        li    $v0, 4
        syscall
        la    $a0, mainNewline
        li    $v0, 4
        syscall
        
        # call reverseWords to get the words printed in reverse order
        lw    $a0, 0($s2)
        jal   reverseWords
        la    $a0, mainNewline
        la    $v0, 4
        syscall
        addi  $s0, $s0, 1        # i++
        addi  $s2, $s2, 4        # $s2 += 4, to get addr of next string
        j     MainLoopBegin
 
MainLoopEnd:
 
MainDone:
        # Epilogue for main -- restore stack & frame pointers and return
        lw    $ra, 4($sp)        # get return address from stack
        lw    $fp, 0($sp)        # restore the caller's frame pointer
        addiu $sp, $sp, 24       # restore the caller's stack pointer
        jr    $ra                # return to caller
 
isLetter:
        # Function prologue
        subu  $sp, $sp, 24       # allocate stack space -- default of 24 here
        sw    $fp, 0($sp)        # save caller's frame pointer
        sw    $ra, 4($sp)        # save return address
        sw    $a0, 8($sp)        # preserve $a0
        addiu $fp, $sp, 24       # setup isLetter's frame pointer
 
        addi  $t0, $zero, 0x41   # $t2 = 'A'
        addi  $t1, $zero, 0x5a   # $t3 = 'Z'
        addi  $t2, $zero, 0x61   # $t2 = 'a'
        addi  $t3, $zero, 0x7a   # $t3 = 'z'
 
        addi  $v0, $zero, 0      # $v0 = 0 -- assume char is not a letter
 
        # check upper-case first
        # is the character < 'A'
        slt   $t4, $a0, $t0      # $t4 = $a0 < $t0, $t4 = char < 'A'
        bne   $t4, $zero, isLetterDone
        # is the character > 'Z'
        slt   $t4, $t1, $a0      # $t4 = $t1 < $a0, $t4 = 'Z' < char
        bne   $t4, $zero, isLetterCheckLower
        addi  $v0, $zero, 1      # return 1, since char is upper-case
        j     isLetterDone
 
isLetterCheckLower:
        # check lower-case
        # is the character < 'a'
        slt   $t4, $a0, $t2      # $t4 = $a0 < $t2, $t4 = char < 'a'
        bne   $t4, $zero, isLetterDone
        # is the character > 'z'
        slt   $t4, $t3, $a0      # $t4 = $t3 < $a0, $t4 = 'z' < char
        bne   $t4, $zero, isLetterDone
        addi  $v0, $zero, 1      # return 1, since char is lower-case
 
isLetterDone:
        # Epilogue for isLetter -- restore stack & frame pointers and return
        lw    $a0, 8($sp)        # restore $a0
        lw    $ra, 4($sp)        # get return address from stack
        lw    $fp, 0($sp)        # restore the caller's frame pointer
        addiu $sp, $sp, 24       # restore the caller's stack pointer
        jr    $ra                # return to caller

# Your code goes below this line
.data
ReverseWordsNewLine:        .asciiz  "\n"

.text
reverseWords:

        # prologue
        subu  $sp, $sp, 24       # allocate stack space -- default of 24 here
        sw    $fp, 0($sp)        # save caller's frame pointer
        sw    $ra, 4($sp)        # save return address
        sw    $a0, 8($sp)        # preserve $a0
        addiu $fp, $sp, 24       # setup reverseWords' frame pointer
        subu  $sp, $sp, 40       # allocate space for storing a word

        # $t5 = $sp's location (stores the word)
	add   $t5, $zero, $sp

        # $t6 = read through $a0 as reverseWords checks through the line

	# store $a0 into $t7
	add   $t7, $zero, $a0

	# load the first byte into $t6
	lb    $t6, 0($t7)

	# 1: check the first character in the line until a letter is found
	# 2: once a letter is found, keep adding letters to $t5 until a non-letter is found
	# 3: keep word on stack and call reverseWords again
	# 4: base case: when character == \0, print out the word in $t5

ReverseWordsLoopBegin:

	# if not \0, then check if $t6 is not a letter
	add   $a0, $t6, $zero

	subu  $sp, $sp, 16
	sw    $t5, 8($sp)
	sw    $t6, 4($sp)
	sw    $t7, 0($sp)

	jal   isLetter

	lw    $t7, 0($sp)
	lw    $t6, 4($sp)
	lw    $t5, 8($sp)
	addu  $sp, $sp, 16

	# if it is not a letter, branch to the end of the loop
	beq   $v0, $zero, ReverseWordsEndOfString

	# must be a letter, preserve onto stack allocation and set $t4 to 1
	add   $t4, $zero, 1
	sb    $t6, 0($t5)
	add   $t5, $t5, 1

ReverseWordsLoopBottom:
	# get the next character ready
	add  $t7, $t7, 1
	lb   $t6, 0($t7)

ReverseWordsLoopAgain:
	j ReverseWordsLoopBegin

ReverseWordsEndOfString:

	sb $zero, 0($t5)

	# if $t6 = 0, skip the recursive call
	beq  $t6, $zero, ReverseWordsPrintWord
	add  $a0, $t7, $zero
	jal reverseWords
	
ReverseWordsPrintWord:
	# print out what's on the stack
	add   $a0, $sp, $zero
	li    $v0, 4
	syscall

	la    $a0, ReverseWordsNewLine
	li    $v0, 4
	syscall

	# Epilogue for reverseWords -- restore stack & frame pointers and return
	addu  $sp, $sp, 40       # get back to original $sp starting point
        lw    $a0, 8($sp)        # restore $a0
        lw    $ra, 4($sp)        # get return address from stack
        lw    $fp, 0($sp)        # restore the caller's frame pointer
        addiu $sp, $sp, 24       # restore the caller's stack pointer
        jr    $ra                # return to caller