```################################################################################
##
## 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.);
#  \$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

# 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

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

jal streq

beq \$v0, \$0, NOT_IN_HASH

lhu \$v0, 2(\$t3)

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

NOT_IN_HASH:

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

beq \$v0, \$0,  MISMATCH
nop

# Match
sh \$t4, 0(\$t3)
sh \$t2, 2(\$t3)

jr \$t6

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

slt \$t1, \$a1, \$a2
bne \$t1, \$0, LOOP

DONE:
jr \$t6

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.

SE_LOOP:
lbu \$t7, 0(\$t8)
lbu \$t9, 0(\$a1)
bne \$t7, \$t9, SE_MISMATCH
bne \$t7, \$0, SE_LOOP

jr \$ra

SE_MISMATCH:
jr \$ra

################################################################################
## 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:
la \$a1, word_list_start
la \$a2, word_list_end
la \$a3, hash_table
jal get_index

lw \$t0, 0(\$s6) # Word Position
beq \$t0, \$v0, TB_DONE_POS_CHECK
addi \$t5, \$0, 95  # '_'
addi \$t5, \$0, 88  # 'X'
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'
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'
TB_DONE_HASH_IDX_CHECK:

la \$a0, msg
syscall

TB_CHAR_LOOP:
lbu \$t0, 0(\$s0)
bne \$t0, \$0, TB_CHAR_LOOP

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

la \$a0, msg_at_end