################################################################################
##
## LSU EE 4720 Fall 2019 Homework 1
##
##
 ## SOLUTION

 # Assignment https://www.ece.lsu.edu/ee4720/2019/hw01.pdf

################################################################################
## Problem 1

        .text

get_index:
        ## Register Usage
        #
        # CALL VALUES:
        #  $a0: Address word to lookup. Word will be at least 3 chars.
        #  $a1: Address of start of word table.
        #  $a2: Address of end of word table.
        #  $a3: Address of storage for hash table.
        #
        # RETURN:
        #  $v0: If found, word position (first is 1, second is 2, etc.);
        #       if not found, 0;
        #  $v1: If not in hash table, hash index;
        #       if in hash table, 0x100 + hash index.
        #
        # Note:
        #  Can modify $t0-$t9, $a0-$a3

        # [✔] Code should be correct.
        # [✔] Code should be reasonably efficient.
        # [✔] Do not use pseudoinstructions except for nop and la.

        ## SOLUTION

        addi $t6, $ra, 0  # Save return address.
        addi $t5, $a1, 0  # Save start address of word table.

        # Compute hash.
        lb $t0, 0($a0)
        lb $t1, 1($a0)
        sra $t2, $t1, 2
        xor $t0, $t0, $t2
        sll $t2, $t1, 6
        xor $t0, $t0, $t2
        lb $t1, 2($a0)
        sra $t2, $t1, 4
        xor $t0, $t0, $t2
        sll $t2, $t1, 4
        xor $t0, $t0, $t2

        andi $v1, $t0, 0xff
        sll $t0, $v1, 2
        add $t3, $a3, $t0

        lhu $v0, 2($t3)
        beq $v0, $0,  NOT_IN_HASH
        lhu $t2, 0($t3)

        jal streq
        add $a1, $t5, $t2
        add $ra, $t6, $0

        beq $v0, $0, NOT_IN_HASH
        addi $a1, $t5, 0

        lhu $v0, 2($t3)

        jr $ra
        ori $v1, $v1, 0x100
        

NOT_IN_HASH:
        addi $t2, $0, 1

LOOP:
        jal streq
        sub $t4, $a1, $t5

        beq $v0, $0,  MISMATCH
        nop

        # Match
        sh $t4, 0($t3)
        sh $t2, 2($t3)
        
        jr $t6
        addi $v0, $t2, 0


MISMATCH:
        # Scan to next null.
        lbu $t1, 0($a1)
        bne $t1, $0 MISMATCH
        addi $a1, $a1, 1

        slt $t1, $a1, $a2
        bne $t1, $0, LOOP
        addi $t2, $t2, 1

DONE:
        jr $t6
        addi $v0, $0, 0


streq:
        ## Register Usage
        #
        # CALL VALUES:
        #  $a0: Address of string 1.
        #  $a1: Address of string 2.
        #
        # RETURN:
        #  $v0: If strings match, 1; otherwise, 0;
        #  $a1: At null or first mismatched character.

        add $t8, $0, $a0

SE_LOOP:
        lbu $t7, 0($t8)
        lbu $t9, 0($a1)
        bne $t7, $t9, SE_MISMATCH
        addi $t8, $t8, 1
        bne $t7, $0, SE_LOOP
        addi $a1, $a1, 1
        
        jr $ra
        addi $v0, $0, 1


SE_MISMATCH:
        jr $ra
        addi $v0, $0, 0





################################################################################
## Testbench Routine
#
# 

.data
word_list_start:
	.asciiz "aardvark"
	.asciiz "ark"
	.asciiz "bark"
	.asciiz "barkeeper"
	.asciiz "persevere"
	.asciiz "bird"
	.asciiz "box"
	.asciiz "sox"
	.asciiz "lox"
	.asciiz "soy"
	.asciiz "sax"
	.asciiz "brain"
word_list_end:
test_words_start:
	.asciiz "ark"
	.asciiz "box"
	.asciiz "sox"
	.asciiz "soy"
	.asciiz "sax"
	.asciiz "sod"
	.asciiz "barkeeper"
	.asciiz "bark"
	.asciiz "woof"
	.asciiz "bar"
	.asciiz "ark"
	.asciiz "bar"
	.asciiz "bark"
	.asciiz "barkeeper"
	.asciiz "arkansas"
	.asciiz "lox"
	.asciiz "box"
	.asciiz "sox"
	.asciiz "sax"
	.asciiz "soy"
	.asciiz "aardvark"
	.asciiz "persevere"
test_words_end:
        .byte 0 0 0 0
        .align 4
results_start:
	.word   2  0x4b  # ark
	.word   7  0x3e  # box
	.word   8  0x2f  # sox
	.word  10  0x3f  # soy
	.word  11  0xac  # sax
	.word   0  0xee  # sod
	.word   4  0x1d  # barkeeper
	.word   3  0x1d  # bark
	.word   0  0x5a  # woof
	.word   0  0x1d  # bar
	.word   2 0x14b  # ark
	.word   0  0x1d  # bar
	.word   3 0x11d  # bark
	.word   4  0x1d  # barkeeper
	.word   0  0x4b  # arkansas
	.word   9  0x30  # lox
	.word   7 0x13e  # box
	.word   8 0x12f  # sox
	.word  11 0x1ac  # sax
	.word  10 0x13f  # soy
	.word   1  0x1e  # aardvark
	.word   5   0xe  # persevere

hash_table:
        .space 1024

msg:
        .asciiz "Pos: %/s1/3d %/t5/1c  Hash 0x%/v1/3x %/t3/1c%/t4/1c  Word: %/s0/s\n"

msg_at_end:
        .asciiz "Done with tests: Errors: %/s3/d pos, %/s5/d hash found, %/s4/d hash idx\n"

        .text
        .globl __start

__start:

        la $s0, test_words_start
        la $s2, test_words_end
        addi $s3, $0, 0  # Word position error count.
        addi $s4, $0, 0  # Hash index error count.
        addi $s5, $0, 0  # Hash found error count.
        la $s6, results_start

TB_WORD_LOOP:
        addi $a0, $s0, 0
        la $a1, word_list_start
        la $a2, word_list_end
        la $a3, hash_table
        jal get_index
        addi $v0, $0, -2

        lw $t0, 0($s6) # Word Position
        beq $t0, $v0, TB_DONE_POS_CHECK
        addi $t5, $0, 95  # '_'
        addi $t5, $0, 88  # 'X'
        addi $s3, $s3, 1
TB_DONE_POS_CHECK:
        lw $t0, 4($s6) # Hash
        andi $t1, $t0, 0x100
        andi $t2, $v1, 0x100
        beq $t1, $t2, TB_DONE_HASH_FOUND_CHECK
        addi $t3, $0, 95  # '_' 
        addi $t3, $0, 88  # 'X' 
        addi $s5, $s5, 1
TB_DONE_HASH_FOUND_CHECK:
        andi $t1, $t0, 0xff
        andi $t2, $v1, 0xff
        beq $t1, $t2, TB_DONE_HASH_IDX_CHECK
        addi $t4, $0, 95  # '_' 
        addi $t4, $0, 88  # 'X' 
        addi $s4, $s4, 1
TB_DONE_HASH_IDX_CHECK:
        addi $s6, $s6, 8
        
        addi $s1, $v0, 0
        la $a0, msg
        addi $v0, $0, 11
        syscall

TB_CHAR_LOOP:
        lbu $t0, 0($s0)
        bne $t0, $0, TB_CHAR_LOOP
        addi $s0, $s0, 1

        slt $t0, $s0, $s2
        bne $t0, $0, TB_WORD_LOOP
        nop

        la $a0, msg_at_end
        addi $v0, $0, 11
        syscall

        addi $v0, $0, 10
        syscall
        nop