################################################################################
##
## LSU EE 3755 Fall 2012 Homework 4
##
##
 ## SOLUTION

 # See http://www.ece.lsu.edu/ee3755/2012f/hw04.pdf for the assignment.

.data
name:
        .asciiz "Solution"  # Put your name between the quotes.


################################################################################
## Main Routine

# This routine runs the test code for the first problem.  It does not
# have to be modified (other than comments), but it can be if it would
# help.  For example, you might comment out a test for one of the
# problems when working on the other.  If you're thinking of improving
# your grade by deleting the test cases which your code gets wrong
# you'll need to come up with a better plan.


        .data
who_are_you:
        .asciiz "Please insert your name at the top of the file where indicated."
doi:
        .asciiz "One two THREE f_o$ur"
        .byte 4
        .asciiz "The quick brown fox jumps over the lazy dog"
        .byte 9
        .asciiz "o"
        .byte 1
        .asciiz " o"
        .byte 1
        .asciiz "o "
        .byte 1
        .asciiz "123 infinity"
        .byte 1
        .asciiz ""
        .byte 0
        .asciiz "0"
        .byte 0
        .byte 255

word_chars:
        .asciiz "ABCDEFGHIJKLMNOPQRSTUVWXYZ$_abcdefghijklmnopqrstuvwxyz"

char_class:
        .space 256

msg:
        .ascii  "String: \"%/s7/s\"\n"
        .asciiz "         Words %/s6/d  Correct Words %/t0/d  %/t1/s\n";
msg_cor_error:
        .asciiz ""
        .asciiz "** Error **"

        .align 4

        .text
        .globl __start
__start:
        la $s0, name
        lb $s0, ($s0)
        bne $s0, $0,  DOTESTS
        la $a0, who_are_you
        addi $v0, $0, 11
        syscall
        addi $v0, $0, 10
        syscall
DOTESTS:
        la $a0, word_chars
        la $a1, char_class
        la $s3, msg_cor_error
        jal char_table_init
        nop
        la $s5, doi
        la $a1, char_class
T_NEXT:
        addi $s7, $s5, 0
        jal word_count
        addi $a0, $s5, 0
        addi $s6, $v0, 0;
T_LOOP:
        lb $t0, 0($s5)
        bne $t0, $0, T_LOOP
        addi $s5, $s5, 1
        lb $t0, 0($s5)
        beq $t0, $s6, T_CORRECT
        addi $t1, $s3, 0
        addi $t1, $t1, 1
T_CORRECT:
        la $a0, msg
        addi $v0, $0, 11
        syscall
        addi $s5, $s5, 1
        lbu $t0, 0($s5)
        addi $t0, $t0, -255
        bne $t0, $0, T_NEXT
        nop

        addi $v0, $0, 10
        syscall


################################################################################
## Problem 1
##
## Initialize Character Table

# Comment this code for a competent MIPS programmer.


char_table_init:
        ## Register Usage
        #
        # Call:   $a0  String containing word characters.
        #         $a1  Location of character classification array.
        # Return: $v0  Number of characters.
        #

        ## SOLUTION
        #  (The comments are the solution.)

        addi $t1, $0, 1        # Use t1 to hold the constant 1.
        addi $t2, $a0, 0       # Make copy of the string's address, used later.
WV_LOOP:
        lbu $t0, 0($a0)        # Load character of word-character string.
        beq $t0, $0, WV_DONE   # Exit the loop if at end of input string.
        add $t0, $t0, $a1      # Compute Character Table address for this char.
        sb $t1, 0($t0)         # Store a 1 in Character Table.
        j WV_LOOP
        addi $a0, $a0, 1       # Advance to next "word" character.
WV_DONE:
        jr $ra
        sub $v0, $a0, $t2      # Compute length of input string.


################################################################################
## Problem 2
##
## word_count: Count words in string.

# Complete the routine below.

word_count:
        ## Register Usage
        #
        # Call:   $a0  String to analyze.
        #         $a1  Character Class Table.
        # Return: $v0  Number of words

        # [x] Use the character table to determine if a char is part of a word.
        # [x] Can modify registers $a0-$a3, $t0-$t9 and $v0 only.
        # [x] Do not modify $s0-$s7, $sp, $fp, or $ra
        # [x] Fill as many delay slots as possible.

        ## SOLUTION

        # Description of Solution
        #
        # The code for iterating over characters in the string and
        # loading their classification from the Character Class Table
        # is straightforward, see the comments to the right of the
        # assembler code.
        #
        # The technique used to actually count words, in particular,
        # to detect the start of words, merits some explanation. A
        # character is at the start of a word if its classification is
        # 1 (is a word character) and the classification of the
        # previous character is 0 (is not a word character). A
        # less-than comparison can be used to detect this: if the
        # classification of the previous character is strictly less
        # than (<) the classification of the current character then we
        # are at the start of a word. One can easily verify that the
        # other three cases (previous 0, current 0; previous 1,
        # current 0 or 1) do not correspond to a word start and also
        # do not satisfy the < condition.
        #
        # Register t3 is assigned the classification of the current
        # character (the one loaded in the current loop iteration),
        # and register t2 holds the classification of the character
        # from the previous iteration (or 0 for the first
        # iteration). The instruction "slt $t4, $t2, $t3" will set $t4
        # to 1 if $t2 < $t3, otherwise $t4 is set to 0. So all we need
        # to do is add $t4 to the word count, kept in register $v0.

        addi $v0, $0, 0       # Initialize the word count register (v0).
        addi $t2, $0, 0       # Initialize the previous-char-class reg (t2).
LOOP:
        lbu $t0, 0($a0)       # Load next character from string.
        beq $t0, $0, DONE     # Exit if string has ended.
        add $t1, $a1, $t0     # Compute Character Table address for this char.
        lb $t3, 0($t1)        # Load the classification from the table.
        slt $t4, $t2, $t3     # Check for start of new word (prev=0, curr=1).
        add $v0, $v0, $t4     # Add to word count.
        addi $t2, $t3, 0      # Set previous char class (t2) to curr class (t3)
        j LOOP
        addi $a0, $a0, 1      # Point to next character.

DONE:
        jr $ra
        nop