# [Assignment1: RISC-V Assembly and Instruction Pipeline](https://hackmd.io/@sysprog/2022-arch-homework1)
contributed by < `tseng0201` >
## Problem
[Leetcode 242 Valid Anagram](https://leetcode.com/problems/valid-anagram/)
Given two strings s and t, return true if t is an anagram of s, and false otherwise.
An Anagram is a word or phrase formed by rearranging the letters of a different word or phrase, typically using all the original letters exactly once.
Example 1:
```
Input: s = "anagram", t = "nagaram"
Output: true
```
Example 2:
```
Input: s = "rat", t = "car"
Output: false
```
Constraints:
* 1 <= s.length, t.length <= 50000
* s and t consist of lowercase English letters.
## Solution
### Concept
First, we can calculate frequency of every letter in s and t, and than store it.
Second, we campare frequency of every letter of s and t wether they are same.
if both frequency is same we get true as output, else we get false.
### Expalain
take Example 1 as example
string s = "anagram", string t = "nagaram".
1. culatelate frequency of every letter of s and t, and store it in a map{key = letter: value = frequency of letter}.
every letter of frequency of s => frequency_s = {a:3, g:1, m:1, n:1, r:1}.
every letter of frequency of t => frequency_t = {a:3, g:1, m:1, n:1, r:1}.
2. we compare every letter in frequency_s and frequency_t, if the key and value are same we say t is an anagram of s return true, else if not t is not an anagram of s return false
## C Code
```c
#include<stdio.h>
#include<stdlib.h>
#include <stdbool.h>
bool isAnagram(char * s, char * t)
{
int letter_freq[26] = {0}; //store frequency of every letter
// calculate frequency of every letter of s
for (int i = 0; s[i]; i++) {
letter_freq[s[i] - 'a']++;
}
// calculate frequency of every letter of t
for (int i = 0; t[i]; i++) {
letter_freq[t[i] - 'a']--;
}
// if letter_freq[i] != 0, it mean in letter char(i + 'a') frequency of letter of s and t are not same.
for (int i = 0; i < 26; i++) {
if (letter_freq[i])
return false;
}
return true; // all of letter of frequency are same
}
int main() {
char *test_1_s = "anagram";
char *test_1_t = "nagaram";
char *test_2_s = "rat";
char *test_2_t = "car";
char *test_3_s = "tseng";
char *test_3_t = "gnest";
/*
printf("test_1 ans is true, got %s \n", isAnagram(test_1_s, test_1_t) ? "true" : "false");
printf("test_2 ans is false, got %s \n", isAnagram(test_2_s, test_2_t) ? "true" : "false");
printf("test_3 ans is true, got %s \n", isAnagram(test_3_s, test_3_t) ? "true" : "false");
*/
if ( 1 == isAnagram(test_1_s, test_1_t)) {
printf("test_1: correct");
} else {
printf("test_1: not_correct");
}
if ( 0 == isAnagram(test_2_s, test_2_t)) {
printf("test_2: correct");
} else {
printf("test_2: not_correct");
}
if ( 1 == isAnagram(test_3_s, test_3_t)) {
printf("test_2: correct");
} else {
printf("test_2: not_correct");
}
}
```
## assemble_code
### isAnagram
```c=
isAnagram: # a0 = s, a1 = t
addi sp, sp, -104 # get sapce for store int letter_freq[26]
addi t0, sp, 0 # t0 = letter_freq[0]
addi t1, x0, 0 # t1 = i = 0
li t2, 26
LOOP1: # int letter_freq[26] = {0};
beq t1, t2 GET_FREQ_s # if i < 26
sw x0, 0(t0) # letter_freq[i] = 0;
addi, t1, t1, 1 # i++;
addi, t0, t0, 4 #
j LOOP1
GET_FREQ_s:
addi, t0, sp, 0 # t0 = letter_freq[0]
addi, t1, a0, 0 # t1 = s
addi, t2, x0, 0 # t2 = i = 0
LOOP2: # for( ;s[i] ;i++ )
add t3, t1, t2 # get address of s[index] from s[0] +
lb t5, (0)t3 # t5 = s[i]
beq, t5, x0, GET_FREQ_F # if s[i] ==0 break the loop
addi t5, t5 -97 # t5 = s[i] - 'a'
slli t5, t5, 2 # get offset form letter_freq[0] to letter_freq[s[i] - 'a']
add t5, t5, t0 # get address of letter_freq[s[i] - 'a']
lw t3, 0(t5) # t3 = [freq[s[i] - 'a']]
addi t3, t3, 1 # t3 = [freq[s[i] - 'a']] + 1
sw t3, 0(t5) # [freq[s[i] - 'a']] = ([freq[s[i] - 'a']] + 1)
addi t2, t2, 1 # i++
j LOOP2
GET_FREQ_F:
addi, t0, sp, 0 # t0 = freq[]
addi, t1, a1, 0 # t1 = t
addi, t2, x0, 0 # t2 = i = 0
LOOP3: # for( ;s[i] ;i++ )
add t3, t1, t2 # get address of t[index]
lb t5, (0)t3 # t5 = t[i]
beq, t5, x0, CHECK # if t[i] == 0 break the loop
addi t5, t5 -97 # t5 = t[i] - 'a'
slli t5, t5, 2 # get offset form letter_freq[0] to letter_freq[t[i] - 'a']
add t5, t5, t0
lw t3, 0(t5) # t5 = [freq[t[i] - 'a']]
addi t3, t3, -1 # t3 = [freq[t[i] - 'a']] - 1
sw t3, 0(t5) # [freq[t[i] - 'a']] = ([freq[t[i] - 'a']] - 1)
addi t2, t2, 1 # i++
j LOOP3
CHECK:
addi t0, sp, 0 # t0 = address freq[0]
addi t1, x0, 0 # t1 = i = 0
li t2, 26
LOOP4: # for (int i = 0; i < 26; i++)
beq t1, t2 TRUE # i < 26
lw t3, 0(t0) # t3 = freq[i];
bne t3, x0, FALSE # if freq[i] != 0 break
addi, t1, t1, 1 # i++;
addi, t0, t0, 4 # freq + 1
j LOOP4
FALSE:
addi a0, x0, 0 # if flase return false
j END_F
TRUE:
addi a0, x0, 01 # if pass check return true
END_F:
jr ra # return, a0 = return value = true or false
```
### main
```c=
.data
test_1_s: .string "anagram"
test_1_t: .string "nagaram"
test_2_s: .string "rat"
test_2_t: .string "anagram"
test_3_s: .string "tseng"
test_3_t: .string "gnest"
correct_1: .string "test_1: correct"
not_correct_1: .string "test_1: not correct"
correct_2: .string "test_2: correct"
not_correct_2: .string "test_2: not correct"
correct_3: .string "test_3: correct"
not_correct_3: .string "test_3: not correct"
.text
main:
addi a7, x0, 4
la a0, test_1_s # s(a0) = test_1_s
la a1, test_1_t # t(a1) = test_1_t
jal ra, isAnagram # call isAnagram(s(a0), t(a1))
bne a0, x0 TRUE_1 # if isAnagram(s(a0), t(a1)) == 1 correct
la a0, not_correct_1 # not correct print error
ecall
TEST_2:
la a0, test_2_s # s(a0) = test_2_s
la a1, test_2_t # t(a1) = test_2_t
jal ra isAnagram # call isAnagram(s(a0), t(a1))
beq a0, x0 TRUE_2 # if isAnagram(s(a0), t(a1)) == 0 correct
la a0, not_correct_2 # not correct print error
ecall
TEST_3:
la a0, test_3_s # s(a0) = test_3_s
la a1, test_3_t # t(a1) = test_3_t
jal ra isAnagram # call isAnagram(s(a0), t(a1))
bne a0, x0 TRUE_3 # if isAnagram(s(a0), t(a1)) == 0 correct
la a0, not_correct_3 # not correct print error
j END
ecall
TRUE_1:
la a0, correct_1 # correct print correct
ecall
j TEST_2 # go to example2
TRUE_2:
la a0, correct_2 # correct print correct
ecall
j TEST_3 # go to example3
TRUE_3:
la a0, correct_3 # correct print correct
ecall
END:
addi a7, x0, 10
ecall
```
how to use ecall: refence to [Assignment1: RISC-V Assembly and Instruction Pipeline, contributed by < tobychui >](https://hackmd.io/@wIVnCcUaTouAktrkMVLEMA/ryqv60zHK#Result-Outputs)
:::danger
Show me the RISC-V Assembly listing.
:notes: jserv
:::
## Pseudo instruction from Ripes
1.each instruction address has difference by 4
2.using 'auipc' relpcae Pseudo instruction 'la' to get address of label
```
000000a8 <isAnagram>:
a8: f9810113 addi x2 x2 -104
ac: 00010293 addi x5 x2 0
b0: 00000313 addi x6 x0 0
b4: 01a00393 addi x7 x0 26
000000b8 <LOOP1>:
b8: 00730a63 beq x6 x7 20 <GET_FREQ_s>
bc: 0002a023 sw x0 0 x5
c0: 00130313 addi x6 x6 1
c4: 00428293 addi x5 x5 4
c8: ff1ff06f jal x0 -16 <LOOP1>
000000cc <GET_FREQ_s>:
cc: 00010293 addi x5 x2 0
d0: 00050313 addi x6 x10 0
d4: 00000393 addi x7 x0 0
000000d8 <LOOP2>:
d8: 00730e33 add x28 x6 x7
dc: 000e0f03 lb x30 0 x28
e0: 020f0263 beq x30 x0 36 <GET_FREQ_F>
e4: f9ff0f13 addi x30 x30 -97
e8: 002f1f13 slli x30 x30 2
ec: 005f0f33 add x30 x30 x5
f0: 000f2e03 lw x28 0 x30
f4: 001e0e13 addi x28 x28 1
f8: 01cf2023 sw x28 0 x30
fc: 00138393 addi x7 x7 1
100: fd9ff06f jal x0 -40 <LOOP2>
00000104 <GET_FREQ_F>:
104: 00010293 addi x5 x2 0
108: 00058313 addi x6 x11 0
10c: 00000393 addi x7 x0 0
00000110 <LOOP3>:
110: 00730e33 add x28 x6 x7
114: 000e0f03 lb x30 0 x28
118: 020f0263 beq x30 x0 36 <CHECK>
11c: f9ff0f13 addi x30 x30 -97
120: 002f1f13 slli x30 x30 2
124: 005f0f33 add x30 x30 x5
128: 000f2e03 lw x28 0 x30
12c: fffe0e13 addi x28 x28 -1
130: 01cf2023 sw x28 0 x30
134: 00138393 addi x7 x7 1
138: fd9ff06f jal x0 -40 <LOOP3>
0000013c <CHECK>:
13c: 00010293 addi x5 x2 0
140: 00000313 addi x6 x0 0
144: 01a00393 addi x7 x0 26
00000148 <LOOP4>:
148: 02730063 beq x6 x7 32 <TRUE>
14c: 0002ae03 lw x28 0 x5
150: 000e1863 bne x28 x0 16 <FALSE>
154: 00130313 addi x6 x6 1
158: 00428293 addi x5 x5 4
15c: fedff06f jal x0 -20 <LOOP4>
00000160 <FALSE>:
160: 00000513 addi x10 x0 0
164: 0080006f jal x0 8 <END_F>
00000168 <TRUE>:
168: 00100513 addi x10 x0 1
0000016c <END_F>:
16c: 00008067 jalr x0 x1 0
```
## pipline with Ripes simulator
when instruction be executed, it will be split to five stage, IF, ID, IE, MEM, WB. ideally we can execute five stage which different successive instruction in same time.
below picture show five successive instruction execute in same time but in different stage
### Instructioin Fetch(IF)
determine which instruction will be execute. it read pc register to get address of instruction, and then get instruction from instr memory by this address.
* Normally, the pc register will +4 for next instruction
* for instruction like jal pc +4 will be calculate
picture below show the pc register will +4 for get next instruction
picture blow show how to get pc + 4
### Instructioin Decode(ID)
determine how to implement this instruction.
* First we take 7 bit opcode at [6:0] to know the format, and then we will now how to interpret this instruction.
* RISC-V has 6 format, R-type,I-type,S-type,SB-type,U-type,UJ-type.
picture below show we need decode to know these value is immediate value or register index
picture below show RISC-V has 6 format. (picture source: [cs61c-lec08](https://inst.eecs.berkeley.edu/~cs61c/su20/pdfs/lectures/lec08.pdf)))
### Instructioin Execute(IE)
Execute instructioin we expected(add, sub, jal......).
* when the result will change pc register(branch, jal instruction),it will write immediately without state MEM, WB.
* If we want to jump to another label, we must discard instruction in stage IF, ID and fetch instruction from address store in pc register
picture blow show when execute jal instruction the res from ALU will immediately to change pc register
picture blow show when execute jal, processor will discard instruction in stage IF, ID
### Memory(MEM)
store/load value to/from memory
### write back(WB)
take the result form stage IE to dst register
* When instruction like 'jal, ra, label', the (pc + 4) will store to ra register at stage WB
picture blow show when stage WB pc + 4 will store into ra register
Sign in with Wallet
Connect another wallet