################################################################################ ## ## LSU EE 4720 Spring 2023 Homework 1 -- SOLUTION ## ## # Assignment https://www.ece.lsu.edu/ee4720/2023/hw01.pdf ################################################################################ ## Problem 1 # # Instructions: https://www.ece.lsu.edu/ee4720/2023/hw01.pdf # .text lookup: ## Register Usage # # CALL VALUES # $a0: Word to look up. # $a1: Start of word table. # $a2: Start of length table. # # RETURN VALUE # $v0: Index of word (at $a0), or -1 if word is not in table. # # [✔] Testbench should show zero errors. # [✔] Can only modify these registers: $t0-$t9, $a0-$a3, $v0,$v1 # [ ] The fewer instructions executed, the better. # [✔] Write code clearly, comment for an expert MIPS programmer. # [✔] Do not use pseudoinstructions except for nop. # [✔] There is no storage that can be used between calls. addi $t3, $a1, 0 # Word table location. addi $t2, $a2, 0 # Length table. ## Determine the size of the lookup word. # addi $t0, $a0, 0 SIZE_LOOP: lb $t1, 1($t0) bne $t1, $0, SIZE_LOOP addi $t0, $t0, 1 # sub $t8, $t0, $a0 # t8: Length of lookup word. WORD_LOOP: ## Check Next Word in Word Table # lb $t0, 0($t2) # Length of current word-table word # Check whether loop has reached the end of the word table. beq $t0, $0, WORD_NOT_FOUND addi $t2, $t2, 1 addi $t5, $t3, 0 # First character in table word to use now. # Compare length of table word (t0) to length of lookup word (t8) # bne $t0, $t8, WORD_LOOP add $t3, $t3, $t0 # First character in table word to use later. # The lengths match, so need to check the words character by # character. addi $t4, $a0, 0 # First character of lookup word. ## Compare lookup word and table word. # CHAR_LOOP: beq $t5, $t3, CASE_TABLE_WORD_END lb $t7, 0($t4) # Lookup word lb $t6, 0($t5) # Table word addi $t5, $t5, 1 beq $t6, $t7, CHAR_LOOP addi $t4, $t4, 1 # Characters don't match. Check whether current position in # word table alphabetically precedes the lookup word. If so # move on to the next word. # slt $t6, $t6, $t7 bne $t6, $0, WORD_LOOP nop WORD_NOT_FOUND: # Here word hasn't been and won't be found. jr $ra addi $v0, $0, -1 CASE_TABLE_WORD_END: # Check whether lookup word has ended, if not no match yet. bne $t7, $0, WORD_LOOP sub $v0, $t2, $a2 # Found a match! jr $ra addi $v0, $v0, -1 ############################################################################## # ## Test Code # # The code below calls the lookup routine. .data ## Word Table table_words: # Total size 532 characters. .ascii "aah" # Index 0 Length 3 .ascii "aardvark" # Index 1 Length 8 .ascii "able" # Index 2 Length 4 .ascii "accoutering" # Index 3 Length 11 .ascii "accouterments" # Index 4 Length 13 .ascii "altarpieces" # Index 5 Length 11 .ascii "altars" # Index 6 Length 6 .ascii "alter" # Index 7 Length 5 .ascii "alterable" # Index 8 Length 9 .ascii "alteration" # Index 9 Length 10 .ascii "as" # Index 10 Length 2 .ascii "asbestos" # Index 11 Length 8 .ascii "bibliographic" # Index 12 Length 13 .ascii "bibliographical" # Index 13 Length 15 .ascii "bibliographically" # Index 14 Length 17 .ascii "blur" # Index 15 Length 4 .ascii "blurb" # Index 16 Length 5 .ascii "blurbs" # Index 17 Length 6 .ascii "counselors" # Index 18 Length 10 .ascii "counsels" # Index 19 Length 8 .ascii "count" # Index 20 Length 5 .ascii "countable" # Index 21 Length 9 .ascii "countably" # Index 22 Length 9 .ascii "countdown" # Index 23 Length 9 .ascii "cross" # Index 24 Length 5 .ascii "crystalline" # Index 25 Length 11 .ascii "crystallization" # Index 26 Length 15 .ascii "diagrammatic" # Index 27 Length 12 .ascii "diagrammatically" # Index 28 Length 16 .ascii "diagrammed" # Index 29 Length 10 .ascii "electroencephalogram" # Index 30 Length 20 .ascii "electromagnetically" # Index 31 Length 19 .ascii "elucidations" # Index 32 Length 12 .ascii "elude" # Index 33 Length 5 .ascii "eluded" # Index 34 Length 6 .ascii "fishwives" # Index 35 Length 9 .ascii "fishy" # Index 36 Length 5 .ascii "fissile" # Index 37 Length 7 .ascii "fission" # Index 38 Length 7 .ascii "fissionable" # Index 39 Length 11 .ascii "fissure" # Index 40 Length 7 .ascii "i" # Index 41 Length 1 .ascii "mucky" # Index 42 Length 5 .ascii "mucous" # Index 43 Length 6 .ascii "mucus" # Index 44 Length 5 .ascii "mud" # Index 45 Length 3 .ascii "oversimple" # Index 46 Length 10 .ascii "oversimplification" # Index 47 Length 18 .ascii "oversimplifications" # Index 48 Length 19 .ascii "oversimplified" # Index 49 Length 14 .ascii "weightlessly" # Index 50 Length 12 .ascii "weightlessness" # Index 51 Length 14 .ascii "weightlifter" # Index 52 Length 12 .ascii "zucchinis" # Index 53 Length 9 .ascii "zwieback" # Index 54 Length 8 .ascii "zydeco" # Index 55 Length 6 .ascii "zygote" # Index 56 Length 6 .ascii "zygotes" # Index 57 Length 7 # Combined Lengths 532 .byte 0 ## Word Length Table table_word_lengths: .byte 3 # Index 0 aah .byte 8 # Index 1 aardvark .byte 4 # Index 2 able .byte 11 # Index 3 accoutering .byte 13 # Index 4 accouterments .byte 11 # Index 5 altarpieces .byte 6 # Index 6 altars .byte 5 # Index 7 alter .byte 9 # Index 8 alterable .byte 10 # Index 9 alteration .byte 2 # Index 10 as .byte 8 # Index 11 asbestos .byte 13 # Index 12 bibliographic .byte 15 # Index 13 bibliographical .byte 17 # Index 14 bibliographically .byte 4 # Index 15 blur .byte 5 # Index 16 blurb .byte 6 # Index 17 blurbs .byte 10 # Index 18 counselors .byte 8 # Index 19 counsels .byte 5 # Index 20 count .byte 9 # Index 21 countable .byte 9 # Index 22 countably .byte 9 # Index 23 countdown .byte 5 # Index 24 cross .byte 11 # Index 25 crystalline .byte 15 # Index 26 crystallization .byte 12 # Index 27 diagrammatic .byte 16 # Index 28 diagrammatically .byte 10 # Index 29 diagrammed .byte 20 # Index 30 electroencephalogram .byte 19 # Index 31 electromagnetically .byte 12 # Index 32 elucidations .byte 5 # Index 33 elude .byte 6 # Index 34 eluded .byte 9 # Index 35 fishwives .byte 5 # Index 36 fishy .byte 7 # Index 37 fissile .byte 7 # Index 38 fission .byte 11 # Index 39 fissionable .byte 7 # Index 40 fissure .byte 1 # Index 41 i .byte 5 # Index 42 mucky .byte 6 # Index 43 mucous .byte 5 # Index 44 mucus .byte 3 # Index 45 mud .byte 10 # Index 46 oversimple .byte 18 # Index 47 oversimplification .byte 19 # Index 48 oversimplifications .byte 14 # Index 49 oversimplified .byte 12 # Index 50 weightlessly .byte 14 # Index 51 weightlessness .byte 12 # Index 52 weightlifter .byte 9 # Index 53 zucchinis .byte 8 # Index 54 zwieback .byte 6 # Index 55 zydeco .byte 6 # Index 56 zygote .byte 7 # Index 57 zygotes ## Lookup Words test_words: .asciiz "a" # Index -1 .asciiz "aah" # Index 0 .asciiz "able" # Index 2 .asciiz "i" # Index 41 .asciiz "blank" # Index -1 .asciiz "counselor" # Index -1 .asciiz "county" # Index -1 .asciiz "fish" # Index -1 .asciiz "gram" # Index -1 .asciiz "palindromic" # Index -1 .asciiz "zymurgy" # Index -1 .asciiz "bibliographical" # Index 13 .asciiz "bibliographically" # Index 14 .asciiz "cross" # Index 24 .asciiz "zydeco" # Index 55 .asciiz "zygotes" # Index 57 .align 4 test_data: .half 0, -1 # a .half 2, 0 # aah .half 6, 2 # able .half 11, 41 # i .half 13, -1 # blank .half 19, -1 # counselor .half 29, -1 # county .half 36, -1 # fish .half 41, -1 # gram .half 46, -1 # palindromic .half 58, -1 # zymurgy .half 66, 13 # bibliographical .half 82, 14 # bibliographically .half 100, 24 # cross .half 106, 55 # zydeco .half 113, 57 # zygotes test_data_end: msg_correct: .asciiz "%/s0/-17s Num Insn: %/t1/5d Index: %/v1/3d -- Correct\n" msg_incorrect: .asciiz "%/s0/-17s Num Insn: %/t1/5d Index: %/v1/3d Er SHOULD BE %/t2/d\n" end_msg: .asciiz "TOTALS: Num Insn: %/k0/5d Tests: %/k1/3d Errors: %/s1/2d\n" .text .globl __start __start: mtc0 $0, $22 # Pause tracing. # s0: Address of test word. addi $s1, $0, 0 # Number of incorrect indices. la $s2, test_data_end # Holds same value. # s5: Number of instructions before. la $s6, test_words # Holds same value. la $s7, test_data # Incremented each iteration. addi $k0, $0, 0 # Total number of instructions. addi $k1, $0, 0 # Total number of lookup words. # Number correct. TB_LOOP: lh $t0, 0($s7) # Offset in word table. addi $k1, $k1, 1 add $s0, $s6, $t0 add $a0, $s0, $0 la $a1, table_words la $a2, table_word_lengths addi $v0, $0, -1 mtc0 $v0, $22 # Resume tracing. (No effect if not stepping.) jal lookup mfc0 $s5, $9 # Copy current instruction count. (Before.) mfc0 $t0, $9 # Copy current instruction count. (After.) mtc0 $0, $22 # Pause tracing. addi $v1, $v0, 0 sub $t1, $t0, $s5 add $k0, $k0, $t1 lh $t2, 2($s7) # Correct index. la $a0, msg_correct beq $t2, $v1, TB_SKIP nop addi $s1, $s1, 1 la $a0, msg_incorrect TB_SKIP: addi $v0, $0, 11 syscall addi $s7, $s7, 4 bne $s7, $s2, TB_LOOP nop la $a0, end_msg addi $v0, $0, 11 syscall addi $v0, $0, 10 syscall nop