# 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
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]
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]
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
126.     li a7, 1
127.     ecall
128.
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
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