---
tags: Computer architecture 2022
---
# Assignment2: RISC-V Toolchain
contributed by < [`qwe661234`](https://github.com/qwe661234) >
## Problem description:
* This problem is based on [Leetcode 925. Long Pressed Name](https://leetcode.com/problems/long-pressed-name/) from [潘鴻福](https://hackmd.io/@kaminto-1999/long-pressed-name).
* Motivation: My homework 1 implement singly-linked list in rsic-v, but it did't cover the array in rsic-v. Therefore, I want to be familiar with the array in rsic-v by this homework.
## Long Pressed Name ([LeetCode 925](https://leetcode.com/problems/long-pressed-name/))
This is one of the "Easy" questions on LeetCode as requested in the assignment. The question is as follows.
Problem:
>Your friend is typing his **name** into a keyboard. Sometimes, when typing a character c, the key might get *long pressed*, and the character will be typed *1 or more times*.
>You examine the typed characters of the keyboard. Return **True** if it is possible that it was your friends name, with some characters (possibly none) being long pressed.
Example 1:
>Input: name = "alex", typed = "aaleex"
>Output: true
>Explanation: 'a' and 'e' in 'alex' were long pressed.
Example 2:
>Input: name = "saeed", typed = "ssaaedd"
>Output: false
>Explanation: 'e' must have been pressed twice, but it was not in the typed output.
## C code
```c
bool isLongPressedName(char *name, char *typed){
int i = 0, j = 0;
if (name[0] != typed[0]) return false;
while (i < strlen(name))
{
if(name[i] == typed[j]){
j++; i++;
}
else{
if(typed[j] == name[i-1])/* long typing */
j++;
else
return false;
}
}
while (j < strlen(typed))
{
if (typed[j++] != name[strlen(name)-1])
return false;
}
return true;
}
int main()
{
char name[] ="alex";
char typed0[]="aalexx";
char typed1[]="aalleexx";
char typed2[]="aalewx";
bool a;
if (isLongPressedName(name,typed0))
printf("PASS\n");
else
printf("FAIL\n");
if (isLongPressedName(name,typed1))
printf("PASS\n");
else
printf("FAIL\n");
if (isLongPressedName(name,typed2))
printf("PASS\n");
else
printf("FAIL\n");
}
```
## Rewrite assembly code (from [潘鴻福](https://hackmd.io/@kaminto-1999/long-pressed-name)) for using rv32emu
```c
.org 0
# Provide program starting address to linker
.global main
/* newlib system calls */
.set SYSEXIT, 93
.set SYSWRITE, 64
.data
addr_name: .string "alex"
addr_typed0: .string "aaleex"
addr_typed1: .string "aalleexx"
addr_typed2: .string "aalewx"
SuccessResult: .string "PASS\n"
.set success_result_size, .-SuccessResult
FailResult: .string "FAIL\n"
.set fail_result_size, .-FailResult
.text
main:
la t0, addr_name #Load "name" 1st address
la t1, addr_typed0 #Load "typed" 1st address
jal ra, isLongPressed #1st test-case
la t1, addr_typed1 #Load "typed" 1st address
jal ra, isLongPressed #2nd test-case
la t1, addr_typed2 #Load "typed" 1st address
jal ra, isLongPressed #3rd test-case
j End
isLongPressed:
addi sp, sp, -8 #Use 2 byte for saving register
sw ra, 0(sp) #1st byte is ra
sw t0, 4(sp) #2nd byte is t0
lb t2, 0(t0) #1st character of name
lb t3, 0(t1) #1st character of typed
bne t2, t3, Fail #1st character must the same
addi t0, t0, 1 #i++
addi t1, t1, 1 #j++
jal Loop #Call Loop
lw ra, 0(sp) #Recall ra
lw t0, 4(sp) #Recall t0
addi sp,sp, 8
ret
Loop: #1st while loop
lb t2, 0(t0) #Load name[i]
lb t3, 0(t1) #Load typed[j]
beq t2, x0, checkLastCharacter #If name[i]= NULL
If:
bne t2, t3, Else #If name[i]!=typed[j]
addi t0, t0, 1 #i++
addi t1, t1, 1 #j++
j Loop
Else:
lb t2, -1(t0) # Load name[i-1]
bne t2, t3,Fail # If typed[j] != name[i-1] then Fail
addi t1, t1, 1 # j++
j Loop
checkLastCharacter: #2nd while loop
lb t2, -1(t0) # Load last character of name
if2:
beq t3, x0, Pass # If typed[j] = NULL, then passed
bne t2, t3,Fail # If typed[j] != name[last] then Fail
addi t1, t1, 1 # j++
lb t3, 0(t1) # Load next character of typed
j if2
Pass:
li a7, SYSWRITE # "write" syscall
li a0, 1 # 1 = standard output (stdout)
la a1, SuccessResult # load address of hello string
li a2, success_result_size # length of hello string
ecall # invoke syscall to print the string
ret
Fail:
li a7, SYSWRITE # "write" syscall
li a0, 1 # 1 = standard output (stdout)
la a1, FailResult # load address of hello string
li a2, fail_result_size # length of hello string
ecall # invoke syscall to print the string
ret
End:
li a0, 0
li a7, SYSEXIT
ecall
```
### Result
```
$ make && ../../build/rv32emu longStr.elf
../../mk/toolchain.mk:25: GNU Toolchain for RISC-V is required. Please check package installation
riscv-none-elf-as -R -march=rv32i -mabi=ilp32 -o longStr.o longStr.S
riscv-none-elf-ld -o longStr.elf -T longStr.ld --oformat=elf32-littleriscv longStr.o
PASS
PASS
FAIL
inferior exit code 0
```
## Observe elf file
> $ riscv-none-elf-objdump -d longStr.elf
```
longStr.elf: file format elf32-littleriscv
Disassembly of section .text:
00000000 <main>:
0: 00000297 auipc t0,0x0
4: 0ec28293 addi t0,t0,236 # ec <addr_name>
8: 00000317 auipc t1,0x0
c: 0e930313 addi t1,t1,233 # f1 <addr_typed0>
10: 020000ef jal ra,30 <isLongPressed>
14: 00000317 auipc t1,0x0
18: 0e430313 addi t1,t1,228 # f8 <addr_typed1>
1c: 014000ef jal ra,30 <isLongPressed>
20: 00000317 auipc t1,0x0
24: 0e130313 addi t1,t1,225 # 101 <addr_typed2>
28: 008000ef jal ra,30 <isLongPressed>
2c: 0b40006f j e0 <End>
00000030 <isLongPressed>:
30: ff810113 addi sp,sp,-8
34: 00112023 sw ra,0(sp)
38: 00512223 sw t0,4(sp)
3c: 00028383 lb t2,0(t0)
40: 00030e03 lb t3,0(t1)
44: 09c39063 bne t2,t3,c4 <Fail>
48: 00128293 addi t0,t0,1
4c: 00130313 addi t1,t1,1
50: 014000ef jal ra,64 <Loop>
54: 00012083 lw ra,0(sp)
58: 00412283 lw t0,4(sp)
5c: 00810113 addi sp,sp,8
60: 00008067 ret
00000064 <Loop>:
64: 00028383 lb t2,0(t0)
68: 00030e03 lb t3,0(t1)
6c: 02038263 beqz t2,90 <checkLastCharacter>
00000070 <If>:
70: 01c39863 bne t2,t3,80 <Else>
74: 00128293 addi t0,t0,1
78: 00130313 addi t1,t1,1
7c: fe9ff06f j 64 <Loop>
00000080 <Else>:
80: fff28383 lb t2,-1(t0)
84: 05c39063 bne t2,t3,c4 <Fail>
88: 00130313 addi t1,t1,1
8c: fd9ff06f j 64 <Loop>
00000090 <checkLastCharacter>:
90: fff28383 lb t2,-1(t0)
00000094 <if2>:
94: 000e0a63 beqz t3,a8 <Pass>
98: 03c39663 bne t2,t3,c4 <Fail>
9c: 00130313 addi t1,t1,1
a0: 00030e03 lb t3,0(t1)
a4: ff1ff06f j 94 <if2>
000000a8 <Pass>:
a8: 04000893 li a7,64
ac: 00100513 li a0,1
b0: 00000597 auipc a1,0x0
b4: 05858593 addi a1,a1,88 # 108 <SuccessResult>
b8: 00600613 li a2,6
bc: 00000073 ecall
c0: 00008067 ret
000000c4 <Fail>:
c4: 04000893 li a7,64
c8: 00100513 li a0,1
cc: 00000597 auipc a1,0x0
d0: 04258593 addi a1,a1,66 # 10e <FailResult>
d4: 00600613 li a2,6
d8: 00000073 ecall
dc: 00008067 ret
000000e0 <End>:
e0: 00000513 li a0,0
e4: 05d00893 li a7,93
e8: 00000073 ecall
000000ec <addr_name>:
ec: 78656c61 .word 0x78656c61
...
000000f1 <addr_typed0>:
f1: 656c6161 .word 0x656c6161
f5: Address 0x00000000000000f5 is out of bounds.
000000f8 <addr_typed1>:
f8: 6c6c6161 .word 0x6c6c6161
fc: 78786565 .word 0x78786565
...
00000101 <addr_typed2>:
101: 656c6161 .word 0x656c6161
105: Address 0x0000000000000105 is out of bounds.
00000108 <SuccessResult>:
108: 53534150 .word 0x53534150
10c: Address 0x000000000000010c is out of bounds.
0000010e <FailResult>:
10e: 4c494146 .word 0x4c494146
112: 000a .short 0x000a
```
- Observation
- Register Used: 6
- sx register: None
- tx register: None
- ax register: a0 a1 a2 a3 a4 a5
- other: None
- Stack used(bytes): None
- lw/sw count: 1
Sign in with Wallet
Connect another wallet