Advertisement
audreych

Untitled

May 27th, 2022
648
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. # This example demonstrates an implementation of LCS's algorithm for finding longest common subsequences.
  2. # We provided two strings in global for simplfy.
  3. # Reference link : https://www.geeksforgeeks.org/longest-common-subsequence-dp-4/
  4. # The ouput of test pattern 1 should be =>  Found LCS length : 8
  5. # The ouput of test pattern 2 should be =>  Found LCS length : 13
  6.  
  7. .data
  8. .align 4
  9. # test pattern 1
  10. SequenceA: .string "ACGTTCGCGACA"
  11. SequenceB: .string "ATCGATGCGC"
  12. SASize: .word 12
  13. SBSize: .word 10
  14. # test pattern 2
  15. # SequenceA: .string "ACGTTTGTAACGACA"
  16. # SequenceB: .string "ACGTCTGTAACGTCCACGCTC"
  17. # SASize: .word 15
  18. # SBSize: .word 21
  19. str: .string "Found LCS length : "
  20. newline: .string "\n"
  21. .text
  22. .global _start
  23. # Start your coding below, don't change anything upper.
  24.  
  25. _start:
  26.   # initialize value in register
  27.   la a0, SequenceA
  28.   la a1, SequenceB
  29.   lw a2, SASize
  30.   lw a3, SBSize
  31.  
  32.   # Do lcs
  33.   jal lcs
  34.  
  35.   j end
  36.  
  37. lcs:
  38.  
  39.   li t0, 1 # allocate space to store the return address
  40.   addi t1, a2, 1 # SASize + 1
  41.   addi t2, a3, 1 # SBSize + 1
  42.   mul t3, t1, t2 # t3 <- (SASize + 1)(SBSize + 1) is the size we should allocate to the sp
  43.   add t0, t0, t3 # add the total space to allocate to stack
  44.   slli t0, t0, 2 # 4 * size (for memory allocation)
  45.  
  46.   addi t5, t0, 0 # store the value of t0 into t5 to be used to deallocate the stack
  47.   li t3, -1
  48.   mul t0, t0, t3 # stack pointer is add a negative number
  49.  
  50.   # allocate the stack pointer this much
  51.   add sp, sp, t0
  52.  
  53.   sw ra, 0(sp) # store return address
  54.  
  55.   add t0, sp, 4 # store the initial address for the dp array
  56.  
  57.   #addi t1, t3, zero # SASize + 2, loop i end when i < SASize + 2
  58.   #addi t2, t4, zero # SBSize + 2, loop j end when j < SBSize + 2
  59.  
  60.   addi t3, zero, 0 # i = 0 initialize for first loop
  61.  
  62.   L1:
  63.     addi t4, zero, 0 # j = 0 initialize for second loop
  64.  
  65.   L2:
  66.     mul t6, t3, t1 # t6 = i * size of first loop
  67.     add t6, t6, t4 # t6 = i * (size of first loop) + j
  68.     slli t6, t6, 2 # t6 = byte offset of [i][j]
  69.     add t6, t0, t6 # t6 = address of of dp[i][j]
  70.  
  71.     beq t3, zero, B1 # go to branch B1 i == 0
  72.     beq t4, zero, B1 # also go to branch B1 j == 0
  73.  
  74.     addi s2, t3, -1 # temp = i - 1
  75.     addi s3, t4, -1 # temp2 = j - 1
  76.     slli s4, s2, 2 # byte offset of [i - 1]
  77.     slli s5, s3, 2 # byte offset of [j - 1]
  78.     add s4, a0, s4 # s4 = address of sequenceA[i - 1]
  79.     add s5, a1, s5 # s5 = address of sequenceB[j - 1]
  80.  
  81.     lw s4, 0(s4) # value A[i - 1]
  82.     lw s5, 0(s5) # value B[i - 1]
  83.     beq s4, s5, B2 # if A[i - 1] == B[i - 1]
  84.  
  85.     # branch else
  86.     # t3 = i, t4 = j, s2, i - 1, s3 = j - 1, t0 = dp address
  87.     mul s4, s2, t1 # s4 = (i - 1) * size of first loop
  88.     add s4, s4, t4 # s4 = (i - 1) * size of first loop + j
  89.     slli s4, s4, 2 # byte offset of dp[i - 1][j]
  90.     add s4, t0, s4 # address of dp[i - 1][j]
  91.     lw s4, 0(s4) # value of dp[i - 1][j]
  92.  
  93.     mul s5, t3, t1 # s4 = (i) * size of first loop
  94.     add s5, s5, s3 # s4 = (i) * size of first loop + (j - 1)
  95.     slli s5, s5, 2 # byte offset of dp[i][j - 1]
  96.     add s5, t0, s5 # address of of dp[i][j - 1]
  97.     lw s5, 0(s5) # value of dp[i][j - 1]
  98.  
  99.     # max start from here
  100.     bge s4, s5, B3 # s4 >= s5 go to B4:
  101.     addi s4, s5, 0 # else max is dp[i][j - 1]
  102.  
  103.   Bmax:
  104.     sw s4, 0(t6)
  105.  
  106.   BDone:
  107.     addi t4, t4, 1 # j = j + 1
  108.     blt t4, t2, L2 # go to L2 if j < (SBSize + 1)
  109.     addi t3, t3, 1 # i = i + 1
  110.     blt t3, t1, L1 # go to L1 if i < (SASize + 1)
  111.  
  112.     # finish loop
  113.     mul t3, a2, t1 # t3 = SASize * size of first loop
  114.     add t3, t3, a3 # t3 = SASize * size of first loop + SBSize
  115.     slli t3, t3, 2 # byte offset of dp[SASize][SBSize]
  116.     add t3, t0, t3 # address of dp[SASize][SBSize]
  117.     lw t3, 0(t3) # value of dp[SASize][SBSize]
  118.  
  119.     # Print delimiter string (pointer in a0) by setting ecall argument to 4
  120.     la a0, str
  121.     li a7, 4
  122.     ecall
  123.  
  124.     # Print real value (in a0) by setting ecall argument to 1
  125.     addi a0, t3, 1
  126.     li a7, 1
  127.     ecall
  128.  
  129.     lw ra, 0(sp) # Reload return address from stack
  130.     add sp, sp, t5 # Restore stack pointer
  131.  
  132.     jr ra # back to main
  133.  
  134.   B1:
  135.  
  136.     sw zero, 0(t6) # dp[i][j] = 0
  137.     j BDone # jump to L2
  138.  
  139.   B2:
  140.  
  141.     mul s2, s2, t1 # s2 = (i - 1) * size of first loop
  142.     add s2, s2, s3 # s2 = (i - 1) * (size of loop i) + (j - 1)
  143.     slli s2, s2, 2 # s2 = byte offset of [i - 1][j - 1]
  144.     add s2, t0, s2 # s2 = address of of dp[i - 1][j - 1]
  145.     lw s3, 0(s2) # load value of dp[i - 1][j - 1]
  146.     addi s3, s3, 1 # temp = dp[i - 1][j - 1] + 1
  147.     sw s3, 0(t6) # dp[i][j] = dp[i - 1][j - 1] + 1
  148.     j BDone # jump to L2
  149.  
  150.   B3:
  151.     addi s4, s4, 0 # max is L[i - 1][j]
  152.     j Bmax # jump to branch Bmax
  153.  
  154. end:nop
  155.  
Advertisement
RAW Paste Data Copied
Advertisement