# Assignment1: RISC-V Assembly and Instruction Pipeline
contributed by < [`kaminto-1999`](https://github.com/kaminto-1999) >

###### tags: `RISC-V`, `array`,`c-code`
## 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.
## Implementaion

You can find the source code [here]().

### C code
Firstly, take a look at C code for an overview of the above idea.

>*isLongPressedName()* fucntion:

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;
}

Idea for solving this problem is simple: Searching and compare each element in **name** and **typed**. First byte (character) of both strings must be the same. Otherwise, it is failed. If `name[i] = typed[j]`, then `i++` and `j++`; else check if `name[i] = typed[j++]`. Here, if `name[i] = name[j++]` (long pressed) increase `i` and `j`, otherwise `return 0`.
When reaching to the end of **name** string, we check if `typed[j]==0` (end of **typed** string). If correct then `return 1`; if no then check `name[last_character]==typed[j]`.
Keep checking until the end of typed string (return 0) or having a character from typed which is different from` name[last_character]` which result in `return 0`
>*main()* function

int main()
{    
    char name[] ="alex";
    char typed0[]="aalexx";
    char typed1[]="aalleexx";
    char typed2[]="aalewx";
    bool a;
    a= isLongPressedName(name,typed0);
    printf("a is %d \n",a);
    a= isLongPressedName(name,typed1);
    printf("a is %d \n",a);
    a= isLongPressedName(name,typed2);
    printf("a is %d \n",a);
}

### Assembly code
Each character is 1 byte and follow the ASCII.

>**name** is a string that hold the true name; starting address is *address_name*.
>**type** is a string that hold the typed name; starting address is *address_typed*; typing name might or might not has long pressed characters.

>Instead of loading all elements into registers, I will load and compare each character of **name** and **typed** string.

.data
addr_name:    .string "alex"
addr_typed0:  .string "aaleex"
addr_typed1:  .string "aalleexx"
addr_typed2:  .string "aalewx"
str1:         .string "a0 is "
str2:         .string "\n"   

End of a string is a NULL so that the last byte in *addr_name* and *addr_typed* is 0x00


Main function

.data
addr_name:    .string "alex"
addr_typed0:  .string "aaleex"
addr_typed1:  .string "aalleexx"
addr_typed2:  .string "aalewx"
str1:         .string "a0 is "
str2:         .string "\n"   

.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
    jal   printResult    #Call printResult
    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:
    addi  a0, x0, 1      # Return a0 =1
    ret
Fail:
    addi  a0, x0, 0      # Return a0 =0
    ret
End:
    li a7, 10
    ecall
printResult:
        mv t4, a0
        la a0, str1      #Print str1
        li a7, 4
        ecall
        mv a0, t4        #Print a0
        li a7, 1
        ecall
        la a0, str2      #Print str2
        li a7, 4
        ecall
        ret

Memory mapping: 248 byte for code and 37 byte for testing data

## Analysis
Using RIPES with 5 stage and extended layout (Having Forwarding Unit and Hazard Unit)

### IF
In IF stage, CPU simply fetch instruction form instruction memory according to program counter (PC).

In this picture, current PC value is zero and the corresponding value at that address is 0x10000517.
* machine code:
### ID

In ID stage, CPU will decode the instruction fetched by previous stage. The value of instruction is 0x10000517, which can be decoded into "auipc x5 0x10000". And decoder will based on this result select two register to become input for next stage.

The immediate value 0x10000 will shift left by 12 bits to fit in upper 20 bits, so it becomes 0x10000000 after decode.
### EX
In EXE stage, the instruction will be executed. There are four multiplexer to decide input value of ALU. And the control of these four multiplexer is done by hazard detection unit and decoded information from previous stage.
At this stage, value in Register file still not be updated. And this will lasting until WB stage
>Value of x5 is still 0.
### MEM
In MEM stage, instruction that modify main memory such as load word and save word will be done.

In this kind of instruction, the target memory address is the computation result of last stage.

There is a control signal to decide whether the value stored in memory could be changed. If the instruction is load type instruction, this control signal will be triggered.
### WB

In WB stage, the result get from EXE stage or MEM stage should be writed back to register file.

There is a multiplexer to decide what value should be writed back. And a write enable signal will decide whether the value stored in register could be writed or not.

* the result of x5 = 0x10000000 should be writed into x5
### Hazard
When executing instruction, some time we might encounter with hazard, which is a phenomena only occur on pipeline CPU.

When insturction is done one after another, there is no nay problem, but when pipelined, a instruction might use result another instruction as an input, which not yet be executed entirely. So the result will become unpredictable.

There are some way to deal with this problem, including forwarding or insert some nop (no operation) or flush.
#### Read-after-write hazard
A raw (read-after-write) hazard means a subsequent instruction read value from a register which sould be written by the calculation result of previous instruction, but because of pipelineing issue haven't. We use a skill known as forwarding to solve this problem. That is, directely read result from previous instruction rather than register file.
The value stored in x10 is 0x00000000, while we expect 0x10000000. So we use forwarding to directly get ther result of previous instruction "auipc x10 0x10000"
#### Load instruction hazard
Load instruction hazard means a subsequent instruction read value from a register which sould be written by the memory value read from previous instruction, but because of pipelineing issue haven't. This problem can not be solved by forwading data. The best solution here is to add a stall.

#### Control hazard

Control hazard means when a branch or jump instruction decide to go to another address in instruction memory, CUP had bring some instruction must be discarded into pipeline.

Because we decide whether to branch in EXE stage, all the instruction in prior stages should be discared.

We use flush to discard instruction in pipline.
>Before JAL instruction go into EX stage

>And after JAL

#### RIPES Result
I use the same testcase as C-code and get the exact result.
This time, only 3 value is validated but in the following version it might contains an automatic validate fuction.
>CPI is 1.56 which is not good because my program contain a lot of Branch and Jump instruction. They will add 2 stalls into the piline (0 if Branch not taken).