# This example demonstrates an implementation of LCS's algorithm for finding longest common subsequences.
# We provided two strings in global for simplfy.
# Reference link : https://www.geeksforgeeks.org/longest-common-subsequence-dp-4/
# The ouput of test pattern 1 should be =>  Found LCS length : 8
# The ouput of test pattern 2 should be =>  Found LCS length : 13

.data
.align 4
# test pattern 1
SequenceA: .string "ACGTTCGCGACA"
SequenceB: .string "ATCGATGCGC"
SASize: .word 12
SBSize: .word 10
# test pattern 2
# SequenceA: .string "ACGTTTGTAACGACA"
# SequenceB: .string "ACGTCTGTAACGTCCACGCTC"
# SASize: .word 15
# SBSize: .word 21
str: .string "Found LCS length : "
newline: .string "\n"
.text
.global _start
# Start your coding below, don't change anything upper.

_start:
  # initialize value in register
  la a0, SequenceA
  la a1, SequenceB
  lw a2, SASize
  lw a3, SBSize

  # Do lcs
  jal lcs

  j end

lcs:

  li t0, 1 # allocate space to store the return address
  addi t1, a2, 1 # SASize + 1
  addi t2, a3, 1 # SBSize + 1
  mul t3, t1, t2 # t3 <- (SASize + 1)(SBSize + 1) is the size we should allocate to the sp
  add t0, t0, t3 # add the total space to allocate to stack
  slli t0, t0, 2 # 4 * size (for memory allocation)

  addi t5, t0, 0 # store the value of t0 into t5 to be used to deallocate the stack
  li t3, -1
  mul t0, t0, t3 # stack pointer is add a negative number

  # allocate the stack pointer this much
  add sp, sp, t0

  sw ra, 0(sp) # store return address

  add t0, sp, 4 # store the initial address for the dp array

  #addi t1, t3, zero # SASize + 2, loop i end when i < SASize + 2
  #addi t2, t4, zero # SBSize + 2, loop j end when j < SBSize + 2

  addi t3, zero, 0 # i = 0 initialize for first loop

  L1:
    addi t4, zero, 0 # j = 0 initialize for second loop

  L2:
    mul t6, t3, t1 # t6 = i * size of first loop
    add t6, t6, t4 # t6 = i * (size of first loop) + j
    slli t6, t6, 2 # t6 = byte offset of [i][j]
    add t6, t0, t6 # t6 = address of of dp[i][j]

    beq t3, zero, B1 # go to branch B1 i == 0
    beq t4, zero, B1 # also go to branch B1 j == 0

    addi s2, t3, -1 # temp = i - 1
    addi s3, t4, -1 # temp2 = j - 1
    slli s4, s2, 2 # byte offset of [i - 1]
    slli s5, s3, 2 # byte offset of [j - 1]
    add s4, a0, s4 # s4 = address of sequenceA[i - 1]
    add s5, a1, s5 # s5 = address of sequenceB[j - 1]

    lw s4, 0(s4) # value A[i - 1]
    lw s5, 0(s5) # value B[i - 1]
    beq s4, s5, B2 # if A[i - 1] == B[i - 1]

    # branch else
    # t3 = i, t4 = j, s2, i - 1, s3 = j - 1, t0 = dp address
    mul s4, s2, t1 # s4 = (i - 1) * size of first loop
    add s4, s4, t4 # s4 = (i - 1) * size of first loop + j
    slli s4, s4, 2 # byte offset of dp[i - 1][j]
    add s4, t0, s4 # address of dp[i - 1][j]
    lw s4, 0(s4) # value of dp[i - 1][j]

    mul s5, t3, t1 # s4 = (i) * size of first loop
    add s5, s5, s3 # s4 = (i) * size of first loop + (j - 1)
    slli s5, s5, 2 # byte offset of dp[i][j - 1]
    add s5, t0, s5 # address of of dp[i][j - 1]
    lw s5, 0(s5) # value of dp[i][j - 1]

    # max start from here
    bge s4, s5, B3 # s4 >= s5 go to B4:
    addi s4, s5, 0 # else max is dp[i][j - 1]

  Bmax:
    sw s4, 0(t6)

  BDone:
    addi t4, t4, 1 # j = j + 1
    blt t4, t2, L2 # go to L2 if j < (SBSize + 1)
    addi t3, t3, 1 # i = i + 1
    blt t3, t1, L1 # go to L1 if i < (SASize + 1)

    # finish loop
    mul t3, a2, t1 # t3 = SASize * size of first loop
    add t3, t3, a3 # t3 = SASize * size of first loop + SBSize
    slli t3, t3, 2 # byte offset of dp[SASize][SBSize]
    add t3, t0, t3 # address of dp[SASize][SBSize]
    lw t3, 0(t3) # value of dp[SASize][SBSize]

    # Print delimiter string (pointer in a0) by setting ecall argument to 4
    la a0, str
    li a7, 4
    ecall

    # Print real value (in a0) by setting ecall argument to 1
    addi a0, t3, 1
    li a7, 1
    ecall

    lw ra, 0(sp) # Reload return address from stack
    add sp, sp, t5 # Restore stack pointer

    jr ra # back to main

  B1:

    sw zero, 0(t6) # dp[i][j] = 0
    j BDone # jump to L2

  B2:

    mul s2, s2, t1 # s2 = (i - 1) * size of first loop
    add s2, s2, s3 # s2 = (i - 1) * (size of loop i) + (j - 1)
    slli s2, s2, 2 # s2 = byte offset of [i - 1][j - 1]
    add s2, t0, s2 # s2 = address of of dp[i - 1][j - 1]
    lw s3, 0(s2) # load value of dp[i - 1][j - 1]
    addi s3, s3, 1 # temp = dp[i - 1][j - 1] + 1
    sw s3, 0(t6) # dp[i][j] = dp[i - 1][j - 1] + 1
    j BDone # jump to L2

  B3:
    addi s4, s4, 0 # max is L[i - 1][j]
    j Bmax # jump to branch Bmax

end:nop