---
# System prepended metadata

title: 'Lab1:RV32I Simulator'
tags: [RISC-V, 2022 Computer Architecture]

---

# Lab1:RV32I Simulator
###### tags: `RISC-V` `2022 Computer Architecture`


##  Length of last word ([leetcode 58](https://leetcode.com/problems/length-of-last-word/))
### describe:
Given a string s consisting of words and spaces, return the length of the last word in the string.

A word is a maximal substring consisting of non-space characters only.

Example : 
```
Input: s = "   fly me   to   the moon  "
Output: 4
Explanation: The last word is "moon" with length 4.
```
Constraints : 
```
* 1 <= s.length <= 10^4
* s consists of only English letters and spaces ' '.
* There will be at least one word in s.
```

## C code
```c
#include <stdio.h>
#include <string.h>

int lengthOfLastWord(char *s){
	int j = strlen(s)-1;
	int length = 0;
	s = s+j;
	
	while(*s == ' '){
	s--;
	}
	while(*s != ' '){
	s--;
	length++;
	}
	printf("length of last word is %d.", length);
}

int main(){
	char *str = "I am a student ";
	lengthOfLastWord(str);
	
	return 0;
}
```

:::warning
:warning: Instead of comparing a byte at one time, can you use efficient word-by-word comparisons?
:notes: jserv
:::

:::info
hello prof. jserv ,  sorry that  I can't understand the warning.  Do you mean that I shouldn't use the char to calculate the length of the word? 
:::

:::danger
Where is your RISC-V Assembly listing?
:notes: jserv
:::

:::info
I already done, but I am still working on the part of checking my data automatically.
:::

## Assembly code ver1
```risc=
.data
str1:    .string "Hello World"
str2:    .string "I  am   a student   "
str3:    .string " abc "
str:     .string "length of last word is "  
space:   .string " "


.text
# s1 = str1 address
# s2 = space
# s3 = length

main:
        #function:lengthOfLastWord(char * s)
        la          s1, str1
        lb          s2, space
        add         s3, x0, x0        #initialize length
        #find the position of the last letter is not space
        jal         ra, strlen        #strlen()
        
        #print result
        la          a0, str1
        addi        a7, x0, 4
        ecall
        li          a0, 13            #CR
        li          a7, 11
        ecall
        la          a0, str          #length of last word is
        addi        a7, x0, 4
        ecall
        add         a0, s3, x0        #length
        li          a7, 1
        ecall
        li          a7, 10            #end
        ecall 
        
strlen:
        addi        s1, s1, 1         #find the last position of the string
        lb          t0, 0(s1)
        bne         t0, x0, strlen
        addi        s1, s1, -1
        lb          t0, 0(s1)
        bne         t0, s2, loop2
loop1:                                #my first while
        addi        s1, s1, -1        #s--
        lb          t0, 0(s1)         #t0=s[i], i=length(s)-1
        beq         t0, s2, loop1     #while(char[i]==" ")
loop2:                                #my second while
        addi        s1, s1, -1        #s--
        lb          t0, 0(s1)         #t0=s[i], i=last word
        addi        s3, s3, 1         #length++
        bne         t0, s2, loop2     #while(char[i]!=" ")
        ret
```
### code explain
I use two loop to calculate the length of last word.
#### loop1:
    if the last part of the string has space, I decrease the position until I find the position which isn't a space.
    Then I branch to loop2
#### loop2:
    I start to count the length of the word, once I decrease the position, I increase the length, until I encounter a space. If I meet the space, I return the value of length.
### Pseudo Instruction
```
00000000 <main>:
    0:        10000497        auipc x9 0x10000
    4:        02448493        addi x9 x9 36
    8:        10000917        auipc x18 0x10000
    c:        03790903        lb x18 55 x18
    10:        000009b3        add x19 x0 x0
    14:        044000ef        jal x1 68 <strlen>
    18:        10000517        auipc x10 0x10000
    1c:        00c50513        addi x10 x10 12
    20:        00400893        addi x17 x0 4
    24:        00000073        ecall
    28:        00d00513        addi x10 x0 13
    2c:        00b00893        addi x17 x0 11
    30:        00000073        ecall
    34:        10000517        auipc x10 0x10000
    38:        fd850513        addi x10 x10 -40
    3c:        00400893        addi x17 x0 4
    40:        00000073        ecall
    44:        00098533        add x10 x19 x0
    48:        00100893        addi x17 x0 1
    4c:        00000073        ecall
    50:        00a00893        addi x17 x0 10
    54:        00000073        ecall

00000058 <strlen>:
    58:        00148493        addi x9 x9 1
    5c:        00048283        lb x5 0 x9
    60:        fe029ce3        bne x5 x0 -8 <strlen>
    64:        fff48493        addi x9 x9 -1
    68:        00048283        lb x5 0 x9
    6c:        00148493        addi x9 x9 1
    70:        01229863        bne x5 x18 16 <loop2>

00000074 <loop1>:
    74:        fff48493        addi x9 x9 -1
    78:        00048283        lb x5 0 x9
    7c:        ff228ce3        beq x5 x18 -8 <loop1>

00000080 <loop2>:
    80:        fff48493        addi x9 x9 -1
    84:        00048283        lb x5 0 x9
    88:        00198993        addi x19 x19 1
    8c:        ff229ae3        bne x5 x18 -12 <loop2>
    90:        00008067        jalr x0 x1 0

```

## Assembly code ver2
```RISC
.data
str1:    .string "Hello World"
str2:    .string "i am a student  "
str3:    .string "a"
str:     .string "length of last word is "  
space:   .string " "


.text
# s1 = str1 address
# s2 = space
# s3 = length
# s4 = filter

main:
        #function:lengthOfLastWord(char * s)
        la          s1, str3
        lb          s2, space
        addi         s3, x0, 1        #initialize length = 1
        #find the position of the last letter is not space
        jal         ra, strlen        #strlen()
        
        #print result
        la          a0, str3
        addi        a7, x0, 4
        ecall
        li          a0, 13            #CR
        li          a7, 11
        ecall
        la          a0, str           #length of last word is
        addi        a7, x0, 4
        ecall
        add         a0, s3, x0        #length
        li          a7, 1
        ecall
        li          a7, 10            #end
        ecall 
        
strlen:
        addi        s1, s1, 1         #find the last position of the string
        addi        s4, s4, 1
        lb          t0, 0(s1)
        bne         t0, x0, strlen
loop1:                             
        addi        s1, s1, -1        #s--
        addi        s4, s4, -1        #the last position is not space
        lb          t0, 0(s1)         #t0=s[i]
        lb          t1, 0(s1)
        beq         t0, s2, loop1     #while(char[i]==" ")
        la          s1, str1
loop2:  
        beq         s4, x0, return    #if encounter the last position, return
        addi        s4, s4, -1        
        addi        s1, s1, 1         #s++
        lb          t0, 0(s1)         #t0=s[i]
        addi        s3, s3, 1         #length++
        bne         t0, s2, loop2     
        addi        s3, x0, 0         #if encounter a space, length = 0
        j           loop2
return:    
        ret
```
### code explain
If the last position has space, I recognized the last position which is not space.Then I start to count the length, if I encounter a space, I reset the length. When I reach the last position which is not space, I return the length.
#### loop1
starting from last position, decrease until I find the position which is not space.

#### loop2
starting from head of the string, continuously adding the value of length. If I meet a space, reset the value of length. 
If I reach the position I got from loop1, return length value.
### Pseudo Instruction
```

00000000 <main>:
    0:        10000497        auipc x9 0x10000
    4:        01d48493        addi x9 x9 29
    8:        10000917        auipc x18 0x10000
    c:        02f90903        lb x18 47 x18
    10:        00100993        addi x19 x0 1
    14:        044000ef        jal x1 68 <strlen>
    18:        10000517        auipc x10 0x10000
    1c:        00550513        addi x10 x10 5
    20:        00400893        addi x17 x0 4
    24:        00000073        ecall
    28:        00d00513        addi x10 x0 13
    2c:        00b00893        addi x17 x0 11
    30:        00000073        ecall
    34:        10000517        auipc x10 0x10000
    38:        feb50513        addi x10 x10 -21
    3c:        00400893        addi x17 x0 4
    40:        00000073        ecall
    44:        00098533        add x10 x19 x0
    48:        00100893        addi x17 x0 1
    4c:        00000073        ecall
    50:        00a00893        addi x17 x0 10
    54:        00000073        ecall

00000058 <strlen>:
    58:        00148493        addi x9 x9 1
    5c:        001a0a13        addi x20 x20 1
    60:        00048283        lb x5 0 x9
    64:        fe029ae3        bne x5 x0 -12 <strlen>

00000068 <loop1>:
    68:        fff48493        addi x9 x9 -1
    6c:        fffa0a13        addi x20 x20 -1
    70:        00048283        lb x5 0 x9
    74:        00048303        lb x6 0 x9
    78:        ff2288e3        beq x5 x18 -16 <loop1>
    7c:        10000497        auipc x9 0x10000
    80:        f8448493        addi x9 x9 -124

00000084 <loop2>:
    84:        020a0063        beq x20 x0 32 <return>
    88:        fffa0a13        addi x20 x20 -1
    8c:        00148493        addi x9 x9 1
    90:        00048283        lb x5 0 x9
    94:        00198993        addi x19 x19 1
    98:        ff2296e3        bne x5 x18 -20 <loop2>
    9c:        00000993        addi x19 x0 0
    a0:        fe5ff06f        jal x0 -28 <loop2>

000000a4 <return>:
    a4:        00008067        jalr x0 x1 0

```

## Ripes
### 5 stage pipeline
#### overview
1. IF (Instruction Fetch): Read an instruction from memory.
2. ID (Instruction Decode): Read source operands from the register file.
3. EX (Execute Stage): Perform ALU operation.
4. MEM (Memory Access): Access data memory.
5. WB (Register Write Back): Update register file.

![](https://i.imgur.com/MY6LWKK.png)

whole block diagram of Ripes RISC-V simulator
![](https://i.imgur.com/deygoNU.jpg)


#### IF
Read an instruction from memory
* Use the program counter (PC) to index into the IMemory
* Compute NPC by incrementing current PC
Update pipeline registers
* Write the instruction into the pipeline registers
![](https://i.imgur.com/gCnqSu7.jpg)

#### ID
Generate control signals for the opcode bits
Read source operands from the register file.
* Use the specifiers for indexing RF
Update pipeline registers
* Send the operand and immediate values to next stage
* Pass control signals and NPC to next stage
![](https://i.imgur.com/B4ru51R.jpg)


#### ES
Perform ALU operation.
* Compute the result of ALU
* Compute branch target
![](https://i.imgur.com/rBZRQ29.jpg)

#### MEM
Access data memory.
* Load/store address: ALU outcome
* Control signals determine read or write access
Update pipeline registers
* ALU results from execute
* Loaded data from D-Memory
* Destination register
![](https://i.imgur.com/4xB5sN1.jpg)

#### WB
Update register file.

## Reference
[2022 Computer Architecture](http://wiki.csie.ncku.edu.tw/arch/schedule)
[PIPELINING: 5-STAGE PIPELINE  Mahdi Nazm Bojnordi](http://www.cs.utah.edu/~bojnordi/classes/6810/f19/slides/05-pipelining.pdf)
[The RISC-V Instruction Set Manual Volume I: Unprivileged ISA](https://riscv.org/wp-content/uploads/2019/06/riscv-spec.pdf)