################################################################################
##
## LSU EE 4720 Spring 2026 Homework 1 -- SOLUTION
##
##
 # Assignment https://www.ece.lsu.edu/ee4720/2026/hw01.pdf

################################################################################
## Problem 1
#
#  Instructions: https://www.ece.lsu.edu/ee4720/2026/hw01.pdf
#

reverse_lists:

        ## Register Usage
        #
        #  CALL VALUES
        #   $a0:  Address of string to read.
        #   $a1:  Address of string to write.
        #   $a2:  Address of scratch storage.
        #
        #  RETURN VALUES
        #   No return registers.
        #   Instead write memory starting at $a1 with string at $a0
        #   with its lists reversed.
        #
        ## Helpful Information
        #
        # Useful ASCII Characters (In Decimal)
        #    0  Null. Marks the end of the string.
        #   40  '(', Opening parenthesis.
        #   41  ')', Closing parenthesis.
        #   44  ',', A comma.
        #
        # Complete ASCII table: https://en.cppreference.com/w/cpp/language/ascii
        #
        ## Solution Checklist
        #
        # [✓] Reverse lists as described in the handout.
        # [✓] There should be no x's in testbench output Err lines.
        # [✓] Don't assume a maximum element length.
        # [✓] Don't assume a maximum list length.
        #
        # [✓] The fewer instructions executed, the better.
        # [✓] Write code clearly, comment for an expert MIPS programmer.
        # [✓] Do not use pseudoinstructions except for nop.
        # [✓] Don't forget that MIPS branches have delay slots.
        # [✓] Remove unneeded code.

        # Helpful Starter Code
        #
        ori $t3, $0, 40    # Open paren.
        ori $t4, $0, 41    # Close paren.
        ori $t5, $0, 44    # Comma

        ## SOLUTION
        #
        # Plan:
        #
        #  Use an approach that scans the input list just twice, once
        #  to find item start addresses, and once to copy the items.
        #
        #  Use the table to store the start address of each item. The
        #  last element of the table is the address of the character
        #  after the last parenthesis.
        #
        #  Identify where the code spends most of its time and take
        #  care to reduce the number of instructions in those places.
        #  Search for "important" to find these places.
        #
        #  Achieve performance by filling delay slots, creatively if
        #  necessary. Also avoid unnecessary code such as maintaining
        #  an item length counter, when addresses can be used for the
        #  same purpose.
        #  
        #
        # Code Outline:
        #
        #  First, copy input to output until a open paren found.
        #  -- See label find_next_open_paren.
        #
        #  Scan until a close paren is found. While scanning store
        #  the address of the start of each item in the table.
        #  -- See label find_item_end.
        #
        #  When the closing paren is found, write the address of the
        #  character after the close paren in the table.
        #
        #  Iterate over the table backward:
        #
        #    Retrieve two adjacent table elements, the first is an
        #    item start address, the second (the start of the *next*
        #    item) is used to compute the item's end address.
        #    -- See label copy_item_start.
        #
        #    Using these values copy the element from the input to the
        #    output.
        #    -- See label copy_item.
        #

find_next_open_paren_prep:
        # Copy start address of scratch storage to t6.
        ori $t6, $a2, 0    # Scratch storage.

find_next_open_paren:
        # Copy input to output until an open parenthesis is found.
        #
        # This loop is important, so it uses as few instructions as is
        # reasonably possible.
        #
        lb $t0, 0($a0)
        sb $t0, 0($a1)
        beq $t0, $t3, found_next_open_paren
        addi $a0, $a0, 1
        bne $t0, $0, find_next_open_paren
        addi $a1, $a1, 1
        #
        # Time: 6 insn / char.

        # The input string has been completely copied. Time
        # to return.

        jr $ra
        nop

found_next_open_paren:
        addi $a1, $a1, 1   # Increment output string address.
found_comma:
        sw $a0, 0($t6)     # Store element start address in table.
        addi $t6, $t6, 4

find_item_end_start:
        lb $t0, 0($a0)

find_item_end:
        # Find the end of the current item.
        #
        # This loop is also important. It's reduced to four
        # instructions by putting the lb at the end, rather than as
        # the first instruction of the loop. (That's way there's a lb
        # instruction, at find_item_end_start, *before* the loop is
        # entered.)
        #
        beq $t0, $t5, found_comma
        addi $a0, $a0, 1
        bne $t0, $t4, find_item_end
        lb $t0, 0($a0)
        #
        # Time: 4 insn / char

        # Found closing parenthesis. Write the table with the address
        # of character after the parenthesis. Note that all other
        # entries in the table are the start address of items.
        #
        sw $a0, 0($t6)

copy_item_start:
        # Prepare for copying an item by retrieving its start address
        # and the next item's start address (or the end-of-list address).
        #
        lw $t1, -4($t6)    # This item's start address.
        lw $t2, 0($t6)     # Start address of next item or end of list.

        addi $t2, $t2, -1  # Compute the address at which to stop copying.
        beq $t1, $t2, item_copied  # Check whether there's nothing to do.
        addi $t6, $t6, -4  # Get ready for the next item.

copy_item:
        # Copy item from input to output.
        #
        # This loop is also important.
        #
        lb $t0, 0($t1)
        sb $t0, 0($a1)
        addi $t1, $t1, 1
        bne $t1, $t2, copy_item
        addi $a1, $a1, 1
        #
        # Time: 5 insn / char

item_copied:
        sb $t5, 0($a1)     # Provisionally write comma. Needed if bne taken.
        bne $t6, $a2 copy_item_start
        addi $a1, $a1, 1

        j find_next_open_paren_prep
        sb $t4, -1($a1)    # Write closing parenthesis.
        



##############################################################################
#
## Test (Testbench) Code
#

        .data
test_string:
        .asciiz "This string has no lists to reverse."

        .ascii  "Total ice between a (lite,glaze), (locally,higher,amounts)"
        .asciiz " possible."

        .asciiz "Corner cases: (), (one), (a,,see), (,b,) (,d,e,)."

        .asciiz "(1,two,three,four,five,six,seven,eight,nine,ten)"
test_string_end:
        .byte 0


correct_string_start:
        .asciiz "This string has no lists to reverse."
        .asciiz "Total ice between a (glaze,lite), (amounts,higher,locally) possible."
        .asciiz "Corner cases: (), (one), (see,,a), (,b,) (,e,d,)."
        .asciiz "(ten,nine,eight,seven,six,five,four,three,two,1)"

error_mask_string:
        .space 256

output_string:
        .space 256

        .align 4
scratch_storage:
        .space 1024

msg_in:
        .ascii "---- Input number %/s6/i, length %/f0/.0f characters.\n"
        .asciiz "In : %/s7/s\n"
msg_out:
        .ascii "Out: %/s1/s\n"
#        .ascii "        .asciiz \"%/s1/s\"\n" # Used to print correct str.
        .ascii "Err: %/t0/s\n"
        .asciiz "---- Computed with %/s4/d instructions at %/f6/.3f char/insn or %/f8/.1f insn/char.\n\n"

        .text


tb_strlen:
        ## Register Usage
        #
        # $a0: Address of first character of string.
        # $v0: Return value, the length of the string.
        # $a0: Return value, address after string.
        #
        addi $v0, $a0, 1        # Set aside a copy of the string start + 1.
TB_STRLEN_LOOP:
        lbu $t0, 0($a0)           # Load next character in string into $t0
        bne $t0, $0, TB_STRLEN_LOOP  # If it's not zero, continue
        addi $a0, $a0, 1          # Increment address. (Note: Delay slot insn.)

        jr $ra
        sub $v0, $a0, $v0


        .globl __start
__start:

        mtc0 $0, $22            # Pause tracing.
        addi $s6, $0, 0         # Input number.
        la $s7, test_string     # Address of next string to use.

tb_next_input:

        # Display a message showing input number, text length, and text.
        #
        addi $s6, $s6, 1
        ori $a0, $s7, 0
        jal tb_strlen
        nop
        mtc1 $v0, $f0
        cvt.d.w $f0, $f0         # Convert length to FP now, used later.
        la $a0, msg_in
        addi $v0, $0, 11
        syscall
        nop

        # Call reverse_lists
        #
        ori $a0, $s7, 0
        la $a1, output_string
        la $a2, scratch_storage
        mtc0 $v0, $22           # Resume tracing. (No effect if not stepping.)
        jal reverse_lists
        mfc0 $s5, $9            # Copy current instruction count. (Before.)
        mfc0 $s4, $9            # Copy current instruction count. (After.)
        mtc0 $0, $22            # Pause tracing.
        sub $s4, $s4, $s5       # Compute number of instructions executed ..
        addi $s4, $s4, -1       # .. correcting for the post-return instruction.

        mtc1 $s4, $f4           # Move number of instructions to FP regs and ..
        cvt.d.w $f4, $f4        # .. convert to FP double and then
        div.d $f6, $f0, $f4     # .. compute execution rate in char / insn ..
        div.d $f8, $f4, $f0     # .. and compute insn / char.

        # Compute string showing positions containing errors.
        #
        la $s1, output_string
        la $t0, correct_string_start
        la $t1, test_string
        sub $t1, $s7, $t1           # Offset of current string.
        add $t0, $t0, $t1           # Address of correct string.
        la $t2, error_mask_string
        ori $t5, $0, 32   # ASCII space
        ori $t6, $0, 120  # ASCII x (lower-case ex)
tb_mask_loop:
        lb $t3, 0($s1)
        lb $t4, 0($t0)
        beq $t3, $t4, tb_okay
        sb $t5, 0($t2)
        sb $t6, 0($t2)
tb_okay:
        addi $s1, $s1, 1
        addi $t0, $t0, 1
        bne $t4, $0, tb_mask_loop
        addi $t2, $t2, 1

        sb $0, 0($t2)

        # Show reverse_lists output, error string, and performance numbers.
        #
        la $t0, error_mask_string
        la $s1, output_string
        la $a0, msg_out
        
        addi $v0, $0, 11
        syscall
        nop

        # Move to next test string
        #
        ori $a0, $s7, 0
        jal tb_strlen
        nop
        ori $s7, $a0, 0
        la $t0, test_string_end
        sub $t0, $t0, $s7
        bgtz $t0, tb_next_input
        nop

        ori $v0, $0, 10
        syscall
        nop