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

################################################################################
## Problem 1 -- SOLUTION
#
        .text
aadd1:  ## Note: Not called by testbench.
        ## Register Usage
        #
        # CALL VALUES
        #  $a0: Address of the output buffer in which to write the result.
        #  $a1: Address of operand 1, an ASCII string.
        #  $a2: Address of operand 2, an ASCII string.
        #  $a3: Length of operands:
        #       Operand 1 length: bits 31:16
        #       Operand 2 length: bits 15:0
        #
        # RETURN VALUE
        #  $v0: Address of start of the result. Must be within output buffer.
        #
        # [✔] Can only modify these registers: $t0-$t9, $a0-$a3,  $v0,$v1
        # [✔] The fewer instructions executed, the better. But not a priority.
        # [✔] Write code clearly, comment for an expert MIPS programmer.
        # [✔] Do not use pseudoinstructions except for nop.

        srl $t8, $a3, 16         # Length of operand 1
        andi $t9, $a3, 0xffff    # Length of operand 2

        ## Problem 1 -- SOLUTION
        #
        #  This code just copies operand 1 into the output buffer.
        #  It does not perform addition. See the Problem 2 solutions
        #  for code that adds to two operands together.

        addi $v0, $a0, 0  # Put address of copied operand (the result) in v0.

TRY_LOOP:
        lb $t0, 0($a1)         # Load a character from operand 1 ..
        sb $t0, 0($a0)         # .. and write it into the output buffer.
        addi $a0, $a0, 1       # Increment output buffer address.
        bne $t0, $0, TRY_LOOP  # Check whether operand 1 ends.
        addi $a1, $a1, 1       # Increment operand 1 address.
        #
        # Note that the addi $a1 above executes whether or not bne is taken.

        jr $ra
        nop


################################################################################
## Problem 2 -- SOLUTION -- Simple
#
        .text
aadd:   ## ASCII Add
        ## Register Usage
        #
        # CALL VALUES
        #  $a0: Address of the output buffer in which to write the result.
        #  $a1: Address of operand 1, an ASCII string.
        #  $a2: Address of operand 2, an ASCII string.
        #  $a3: Length of operands:
        #       Operand 1 length: bits 31:16
        #       Operand 2 length: bits 15:0
        #
        # RETURN VALUE
        #  $v0: Address of start of the result. Must be within output buffer.
        #
        # [✔] Write memory at a0 with string holding sum of a1 and a2 ..
        #     .. all are decimal integers in ASCII string representation.
        # [✔] Do not convert operands 1 and 2 to integer values ..
        #     .. operate on them as ASCII strings.
        #
        # [✔] Testbench should show zero errors.
        # [✔] Can only modify these registers: $t0-$t9, $a0-$a3,  $v0,$v1
        # [ ] The fewer instructions executed, the better. But not a priority.
        # [✔] Write code clearly, comment for an expert MIPS programmer.
        # [✔] Do not use pseudoinstructions except for nop.

        srl $t8, $a3, 16         # t8: Length of operand 1
        andi $t9, $a3, 0xffff    # t9: Length of operand 2

        ## SOLUTION -- Simple
        #
        # This solution was written to be easy to understand rather
        # than to be fast. It is kept simple by having one main loop
        # and by not tossing instructions far from their natural place
        # just for the sake of filling a delay slot. A fast solution
        # (which does toss instructions around) follows this simple
        # one.
        
        ## Performance Comparison
        #
        ## This (Simple) Solution
        #
        # Num Insn:    33  Correct:  1 + 1 = 2 
        # Num Insn:    53  Correct:  45 + 55 = 100 
        # Num Insn:   110  Correct:  999999 + 1 = 1000000 
        # Num Insn:   154  Correct:  765432 + 12345678 = 13111110 
        # Num Insn:   295  Correct:  184737252196092 + 8383352872579977 = 8568090124776069
        #
        ## Fast Solution (Further Below)
        #
        # Num Insn:    30  Correct:  1 + 1 = 2 
        # Num Insn:    45  Correct:  45 + 55 = 100 
        # Num Insn:    62  Correct:  999999 + 1 = 1000000 
        # Num Insn:   113  Correct:  765432 + 12345678 = 13111110 
        # Num Insn:   217  Correct:  184737252196092 + 8383352872579977 = 856809

        ## SOLUTION -- Simple

        # Write LSD of sum near the end of the output buffer. Assume
        # output buffer size is 20 characters.
        #
        addi $v0, $a0, 20    # v0: Pointer into output buffer. Start at end.

        # Write null terminator into output buffer.
        #
        addi $v0, $v0, -1
        sb $0, 0($v0)        # Write sum's null terminator.

        # Compute the address of the null terminator of operands 1 and 2.
        #
        add $t1, $a1, $t8    # t1: Operand 1 pointer.  Set to null pointer addr.
        add $t2, $a2, $t9    # t2: Operand 2 pointer.  Set to null pointer addr.

        # Initialize a carry register and a handy constant.
        #
        addi $t5, $0, 0      # t5: The carry register. Initialize to zero.
        addi $v1, $0, 57     # v1: A handy constant: the ASCII character '9'

        ## Main Loop
        #
        # Each iteration of the main loop adds a digit of operand 1
        # (if any remain) to a digit of operand 2 (if any remain) plus
        # the carry from the previous iteration (carried by t5).
        # 
        # Example values are shown in comments prefixed with Eg. In
        # particular they show the operand 1 digit as '4', the operand
        # 2 digit as '7', and a carry in (t5 is 1).
LOOP:
        beq $t1, $a1, OP2_CHECK  # If no more digits of op 1, check operand 2.
        addi $t3, $0, 48     # Put ASCII '0' in t3. Used only if beq taken.
        addi $t1, $t1, -1    # Decrement operand 1 pointer.
        lb $t3, 0($t1)       # Load the next ASCII digit of operand 1
                             # Eg: t3 <- 52  or  '4' (ASCII)
OP2_CHECK:
        beq $t2, $a2, DIGITS_ADD  # If no more digits of op 2, start adding.
        addi $t4, $0, 0      # Put value 0 in t4. Used only if beq taken.
        addi $t2, $t2, -1    # Decrement operand 2 pointer
        lb $t4, 0($t2)       # Load the next ASCII digit of operand 2
                             # Eg: t4 <- 55  or  '7' (ASCII)
        addi $t4, $t4, -48   # Convert operand 2 from ASCII to an integer.
                             # Eg: t4 <- 55 - 48 = 7 (integer)
DIGITS_ADD:
        add $t3, $t3, $t4    # Add operand 1 (ASCII) to operand 2 (integer).
                             # Eg: t3 <- 52 + 7 = 59  or  '4' + 7 = ';'
        add $t3, $t3, $t5    # Add carry to ASCII digit.
                             # Eg: t3 <- 59 + 1 = 60  or  ';' + 1 = '<'
        slt $t5, $v1, $t3    # Check whether ASCII digit >9 (whether carried)
                             # Eg: t5 <- 57 < 60 = 1 (true)  or  '9' < '<' = 1
        beq $t5, $0, No_CAR  # If so, skip digit adjustment.
        nop                  # Oh my, an unfilled delay slot.
        addi $t3, $t3, -10   # Subtract 10, t5 will carry it to next iteration.
                             # Eg: t3 <- 60 - 10 = 50  or  ';' - 10 = '2'
No_CAR:
        addi $v0, $v0, -1    # Decrement output buffer pointer ..
        bne $t1, $a1, LOOP   # If still more of operand 1, loop.
        sb $t3, 0($v0)       # .. but don't forget to store digit of sum!

        bne $t2, $a2, OP2_CHECK  # If still more of operand 2, loop.
        addi $t3, $0, 48     # Put ASCII '0' in t3. Ignored if not taken

        # At this point all digits of operand 1 and 2 have been
        # examined. Just need to check if there is a final carry out.

        beq $t5, $0, DONE
        addi $t0, $0, 49     # ASCII '1'.  Ignored if taken.

        addi $v0, $v0, -1    # Decrement pointer ..
        jr $ra
        sb $t0, 0($v0)       # .. and write ASCII '1' just as we are returning!

DONE:
        jr $ra
        nop



################################################################################
## Problem 2 -- SOLUTION -- Fast
#
#
        .text
faadd:  ## ASCII Add
        ## Register Usage
        #
        # CALL VALUES
        #  $a0: Address of the output buffer in which to write the result.
        #  $a1: Address of operand 1, an ASCII string.
        #  $a2: Address of operand 2, an ASCII string.
        #  $a3: Length of operands:
        #       Operand 1 length: bits 31:16
        #       Operand 2 length: bits 15:0
        #
        # RETURN VALUE
        #  $v0: Address of start of the result. Must be within output buffer.
        #
        # [✔] Write memory at a0 with string holding sum of a1 and a2 ..
        #     .. all are decimal integers in ASCII string representation.
        # [✔] Do not convert operands 1 and 2 to integer values ..
        #     .. operate on them as ASCII strings.
        #
        # [✔] Testbench should show zero errors.
        # [✔] Can only modify these registers: $t0-$t9, $a0-$a3,  $v0,$v1
        # [✔] The fewer instructions executed, the better. But not a priority.
        # [✔] Write code clearly, comment for an expert MIPS programmer.
        # [✔] Do not use pseudoinstructions except for nop.

        srl $t8, $a3, 16         # t8: Length of operand 1
        andi $t9, $a3, 0xffff    # t9: Length of operand 2

        ## SOLUTION -- Fast
        #
        # This solution was written to be fast. The key to making the
        # code fast is the use of three specialized loops. Each
        # specialized loop uses fewer instructions than the
        # all-purpose loop in the simple solution. The first
        # specialized loop is used as long as both operands have
        # digits remaining, and it only checks for the end of operand
        # 2. So if operand 1 is shorter than operand 2 the operands
        # are swapped before entering the first loop. The second
        # specialized loop handles the remaining digits of operand 1
        # until there is no carry. The third specialized loop handles
        # the remaining digits of operand 1 when there is no carry:
        # all it does is copy digits from operand 1 to the output
        # buffer.
        #
        # In addition to the three specialized loops, performance is
        # increased by filling more delay slots.
        #
        # Note that for this assignment, and this assignment ONLY,
        # performance is synonymous with the number of executed
        # instructions.
        
        ## Performance Comparison
        #
        ## Simple Solution (Further Above)
        #
        # Num Insn:    33  Correct:  1 + 1 = 2 
        # Num Insn:    53  Correct:  45 + 55 = 100 
        # Num Insn:   110  Correct:  999999 + 1 = 1000000 
        # Num Insn:   154  Correct:  765432 + 12345678 = 13111110 
        # Num Insn:   295  Correct:  184737252196092 + 8383352872579977 = 8568090124776069
        #
        ## This (Fast) Solution
        #
        # Num Insn:    30  Correct:  1 + 1 = 2 
        # Num Insn:    45  Correct:  45 + 55 = 100 
        # Num Insn:    62  Correct:  999999 + 1 = 1000000 
        # Num Insn:   113  Correct:  765432 + 12345678 = 13111110 
        # Num Insn:   217  Correct:  184737252196092 + 8383352872579977 = 8568090124776069 

        ## Insure that Operand 2 Length is Shorter or Same as Operand 1

        slt $t0, $t8, $t9    # Check whether operand 1 shorter than 1
        beq $t0, $0, OP1_LARGER
        addi $v1, $0, 57     # v1: A handy constant. ASCII character '9'

        # Operand 2 length is *longer* than operand 1 ..
        # .. so the code below will swap them.
        #
        addi $t0, $a1, 0
        addi $a1, $a2, 0         # a1: Address of start of longer operand.
        addi $a2, $t0, 0         # a2: Address of start of shorter operand.
        andi $t8, $a3, 0xffff    # t8: Length of longer operand.
        srl $t9, $a3, 16         # t9: Length of shorter operand.
        #
        # The swap took five instructions. It would only take two
        # instructions if MIPS had a swap instruction.

OP1_LARGER:
        # Operand 1 is now longer, perhaps because we swapped them.

        # Write LSD of sum near the end of the output buffer. Assume
        # output buffer size is 20 characters.
        #
        addi $t7, $a0, 19    # t7: Output buffer pointer. Init to LSD address.
        sb $0, 1($t7)        # Write sum's null terminator.

        # Compute the address of the null terminator of operands 1 and 2.
        #
        add $t1, $a1, $t8    # t1: Operand 1 pointer.  Set to null pointer addr.
        add $t2, $a2, $t9    # t2: Operand 2 pointer.  Set to null pointer addr.

        # Initialize a carry register.
        #
        addi $t5, $0, 0      # t5: The carry register. Initialize to zero.

        ## Main Loop
        #
        # Each iteration of the main loop adds a digit of operand 1 to
        # a digit of operand 2. The number of iterations of the main
        # loop is equal to the length of operand 2 (which can't be
        # longer than operand 1).
        #
        # Comments prefixed with Eg: show example values. In
        # particular they show the operand 1 digit as '4', the operand 2
        # digit as '7', and a carry in (t5 is 1).
MLOOP:
        addi $t1, $t1, -1    # Decrement operand 1 pointer.
        addi $t2, $t2, -1    # Decrement operand 2 pointer
        lb $t3, 0($t1)       # Load next ASCII digit of operand 1
                             # Eg: t3 <- 52  or  '4' (ASCII)
        lb $t4, 0($t2)       # Load next ASCII digit of operand 2
                             # Eg: t4 <- 55  or  '7' (ASCII)
        addi $t4, $t4, -48   # Convert operand 2 from ASCII to an integer.
                             # Eg: t4 <- 7
        add $t3, $t3, $t4    # Add operand 1 (ASCII) to operand 2 (integer).
                             # Eg: t3 <- 52 + 7 = 59  or  '4' + 7 = ';'
        add $t3, $t3, $t5    # Add carry to ASCII digit.
                             # Eg: t3 <- 59 + 1 = 60  or  ';' + 1 = '<'
        slt $t5, $v1, $t3    # Check whether ASCII digit >9 (whether carried)
                             # Eg: t5 <- 57 < 60 = 1 (true)  or  '9' < '<' = 1
        beq $t5, $0, NO_CAR  # If no carry, skip digit adjustment.
        addi $t7, $t7, -1    # Either way, decrement output buffer pointer.
        addi $t3, $t3, -10   # Digit adjustment: remove carried 10.
                             # Eg: t3 <- 60 - 10 = 50  or  ';' - 10 = '2'
NO_CAR:
        bne $t2, $a2, MLOOP  # If still more of operand 2, loop.
        sb $t3, 1($t7)       # Either way, store digit of sum.
        #
        # Notice that the offset in "sb $t3, 1($t7)" is 1. That's
        # because t7 is decremented *before* the sb is executed but we
        # want to use the value in t7 before the decrement. To get
        # that we add 1 (undoing the decrement).

        ## No More Operand 2 Digits

        # If there is no carry out, jump to code that copies the
        # remainder of operand 1 (if any) to the output buffer.
        #
        beq $t5, $0, OP1_COPY_ITER_TEST  # Jump to middle of loop.
        addi $t0, $0, 48     # t0: Prepare ASCII '0'. Not needed if taken.

        # If there are no more operand 1 digits, jump to the code that
        # writes the final carry out digit (a '1').
        # 
        beq $t1, $a1, ULTIMATE_CARRY
        addi $t1, $t1, -1    # Decrement operand pointer. Not needed if taken.


        ## Operand 1 Carry Loop
        #
        # We're past the end of operand 2 and we know there is a carry
        # in. Each iteration of the Operand 1 Carry Loop adds the
        # carry to a digit of operand 1 and writes the sum to the
        # output buffer. The loop ends when there is no carry or we
        # reach the MSD of operand 1, whichever happens first.
        #
OP1_CARRY_LOOP:
        lb $t3, 0($t1)       # Load next digit from operand 1.
        # If digit is not '9' (v1) then prepare to enter operand 1 copy loop.
        bne $t3, $v1, OP1_COPY_PROLOGUE
        addi $t7, $t7, -1
        sb $t0, 1($t7)       # Write digit '0' (t0).
        bne $t1, $a1, OP1_CARRY_LOOP  # Check whether there's more of operand 1.
        addi $t1, $t1, -1

ULTIMATE_CARRY:              # One final carry out to write.
        addi $t0, $0, 49     # ASCII '1'
        sb $t0, 0($t7)       # Write ASCII '1'.
        jr $ra
        addi $v0, $t7, 0

        # We can arrive at this loop from the OP1_CARRY_LOOP. Before
        # entering the OP1_COPY_LOOP we need to store a leftover sum
        # digit from the carry loop.
        #
OP1_COPY_PROLOGUE:
        addi $t3, $t3, 1     # Add carry on to digit.
        sb $t3, 1($t7)       # Store that leftover digit from the carry loop.
        addi $t7, $t7, -1
        bne $t1, $a1, OP1_COPY_LOOP  # Enter copy loop if there is more to copy.
        addi $t1, $t1, -1

        jr $ra
        addi $v0, $t7, 2

        ## Operand 1 Copy Loop
        #
        # At this point there is no carry in, and so there can't be a
        # carry out so just copy the remainder of operand 1 to the
        # output buffer.
OP1_COPY_LOOP:
        lb $t3, 0($t1)
        sb $t3, 1($t7)
OP1_COPY_ITER_TEST:
        addi $t7, $t7, -1
        bne $t1, $a1, OP1_COPY_LOOP
        addi $t1, $t1, -1

        jr $ra
        addi $v0, $t7, 2




##############################################################################
#
 ## Test Code
#
#  The code below calls the lookup routine.

.text

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

strnext:
        ## Not written for general use.
        # CALL VALUE
        #  $s4: Address of a string.
        # RETURN VALUE
        #  $s4: One plus the address of the null terminator.
SN_LOOP:
        lb $t0, 0($s4)
        bne $t0, $0, SN_LOOP
        addi $s4, $s4, 1
        jr $ra
        nop


        .data

.globl table_numbers
table_numbers:
        .asciiz "12321", "0", "12321"
        .asciiz "1", "1", "2"
        .asciiz "45", "55", "100"
        .asciiz "9007", "2", "9009"
        .asciiz "5107", "8", "5115"
        .asciiz "3", "9002",  "9005"
        .asciiz "789", "67", "856"
        .asciiz "67", "789", "856"
        .asciiz "999999", "1", "1000000"
        .asciiz "765432", "12345678", "13111110"
        .asciiz "184737252196092", "8383352872579977", "8568090124776069"
table_numbers_end:
        .byte 0,0,0

        .align 4
buffer_result:
        .space 20
buffer_result_end:
        .space 4

text_v0_too_low:
        .asciiz "** $v0 too low **"
text_v0_too_high:
        .asciiz "** $v0 too high **"
text_correct:
        .asciiz "Correct"
text_wrong:
        .asciiz "Wrong  "

msg_result:
        .asciiz "Num Insn: %/s3/5d  %/t0/s:  %/s1/s + %/s2/s = %/s0/s \n"
msg_end:
        .asciiz "TOTALS:   Correct: %/s6/3d    Wrong: %/s5/2d\n"

aadd_name:
        .asciiz "Routine aadd - Simple"
faadd_name:
        .asciiz "Routine faadd - Fast"
msg_routine:
        .asciiz "\n** Running %/t3/s **\n"

rut_data: # Routine Under Test
        .word aadd
        .word aadd_name
        .word faadd
        .word faadd_name
        .word 0
        .word 0

        .align 4
rut_pos:
        .word rut_data

        .align 4
stack:
        .space 256
stack_end:

        .text
        .globl __start

        # s0: result str to show in output.
        # s1: first operand
        # s2: second operand
        # s3: insn count before call
        # s4: pointer into table_numbers
        # s5: n errs
        # s6: n corr
        # s7: aadd output

__start:
        mtc0 $0, $22            # Pause tracing.

RUT_LOOP:
        la $t0, rut_pos
        lw $t1, 0($t0)
        lw $t2, 0($t1)
        beq $t2, $0, RUT_EXIT
        lw $t3, 4($t1)
        sw $t2, 16($sp)

        addi $t1, $t1, 8
        sw $t1, 0($t0)

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

        la $s4, table_numbers
        addi $s5, $0, 0         # Number of errors.
        addi $s6, $0, 0        # Number correct.

TB_LOOP:
        # Put address of next operands in $a1 and $a2
        jal strnext
        addi $s1, $s4, 0
        addi $s2, $s4, 0

        # Write output buffer with X's.
        #
        la $t3, buffer_result
        la $t4, buffer_result_end
        lui $t1, 0x5858       # Two upper-case Xs.
        ori $t1, $t1, 0x5858  # Two upper-case Xs.
TB_ZLOOP:
        sw $t1, 0($t3)
        bne $t3, $t4, TB_ZLOOP
        addi $t3, $t3, 4
        sw $0, -4($t3)

        # Compute length of operands.
        jal tb_strlen
        addi $a0, $s1, 0
        sll $a3, $v0, 16  # Length of first operand in upper 16 bits.
        jal tb_strlen
        addi $a0, $s2, 0
        or $a3, $a3, $v0  # Length of second operand.

        la $a0, buffer_result
        addi $a1, $s1, 0
        addi $a2, $s2, 0
        lw $t0, 16($sp)
        addi $v0, $0, -1
        mtc0 $v0, $22           # Resume tracing. (No effect if not stepping.)
        jalr $t0
        mfc0 $s3, $9            # Copy current instruction count. (Before.)
        mfc0 $t0, $9            # Copy current instruction count. (After.)
        mtc0 $0, $22            # Pause tracing.
        sub $s3, $t0, $s3
        addi $s7, $v0, 0        # Make a copy of the result starting point.

        # Get address of correct result. (Will be in $s4)
        #
        jal strnext
        nop

        la $t1, buffer_result
        sub $t0, $s7, $t1
        bgez $t0, TB_V0_LOW_OK
        nop

        la $s0, text_v0_too_low
        j TB_FOUND_ERR
        nop

TB_V0_LOW_OK:
        la $t1, buffer_result_end
        sub $t0, $t1, $s7
        bgez $t0, TB_V0_HIGH_OK
        nop

        la $s0, text_v0_too_high
        j TB_FOUND_ERR
        nop

TB_V0_HIGH_OK:
        addi $s0, $s7, 0
        # Check result.
        addi $t0, $s4, 0  # Correct value from table.
        addi $a0, $s7, 0  # Value of v0 returned by aad.
TB_CHLOOP:
        lb $t1, 0($t0)  # From table of correct results.
        lb $t2, 0($a0)  # Written by aadd
        bne $t1, $t2, TB_FOUND_ERR
        addi $t0, $t0, 1
        bne $t1, $0, TB_CHLOOP
        addi $a0, $a0, 1

        # Result is correct!
        la $t0, text_correct
        j TB_REPORT_RESULT
        addi $s6, $s6, 1

TB_FOUND_ERR:
        la $t0, text_wrong
        addi $s5, $s5, 1

TB_REPORT_RESULT:
        la $a0, msg_result
        addi $v0, $0, 11
        syscall

        # Move to first operand of next problem.
        jal strnext
        nop

        la $t1, table_numbers_end
        slt $t0, $s4, $t1
        bne $t0, $0, TB_LOOP
        nop

        # Report final results
        #
        la $a0, msg_end
        addi $v0, $0, 11
        syscall

        j RUT_LOOP
        nop

RUT_EXIT:
        addi $v0, $0, 10
        syscall
        nop