# Assignment1: RISC-V Assembly and Instruction Pipeline
contributed by < [OliveLake](https://github.com/OliveLake) >
###### tags: `RISC-V`
###### tags: `computer architure 2021`

## [Leetcode 389. Find the Difference](https://leetcode.com/problems/find-the-difference/)

Given two strings s and t. String t is generated by random shuffling string s and then add one more letter at a random position. Return the letter that was added to t.

#### Example
Input: s = "ae", t = "aae"
Output: "a"
## C code

char findTheDifference(char *s, char *t){
        int originalCount = 0;
        int newCount = 0;
        for (int i=0; i<strlen(s); i++) {
            originalCount+=(int)s[i];    //casting
        }
        for (int j=0; j<strlen(t); j++) {
            newCount += (int)t[j];
        }
        return (char)(newCount - originalCount);
}

## RISC-V assembly code

.data
arr1: .word 97, 101			# s[2] = {a, e}
arr2: .word 97, 97, 101		# t[3] = {a, a, e}
str:  .string "the added letter is  "

main:
		la s0, arr1	#s0 store the address of arr1
		la s1, arr2	#s1 store the address of arr1
		addi s2, s2, 2	#s2 always equal to 2
		addi s3, s3, 3	#s3 alwaly equal to 3
		add s4, x0, x0
		add s5, x0, x0
		add s6, x0, x0
		add t0, x0, x0
		jal ra, loop1
		add t0, x0, x0
		jal ra, loop2
		j end
		

loop1:
		lw s4, 0(s0)
		add s5, s5, s4
		addi s0, s0, 4
		addi t0, t0, 1
		blt t0, s2, loop1
		ret	
loop2:
		lw s4, 0(s1)
		add s6, s6, s4
		addi s1, s1, 4
		addi t0, t0, 1
		blt t0, s3, loop2
		ret
end:
		la a0, str
		li a7, 4
		ecall
		sub a0, s6, s5
		li a7, 1
		ecall

## Analysis
Using [Ripes](https://github.com/mortbopet/Ripes) simulator to test the assembly code.

### Pseudo Instruction
While load assembly code into Ripes, it translates the original source code into machine readable form, and modifies name of registers from ABI name to sequencial one.

00000000 <main>:
	0:		10000417		auipc x8 0x10000
	4:		00040413		addi x8 x8 0
	8:		10000497		auipc x9 0x10000
	c:		00048493		addi x9 x9 0
	10:		00290913		addi x18 x18 2
	14:		00398993		addi x19 x19 3
	18:		00000a33		add x20 x0 x0
	1c:		00000ab3		add x21 x0 x0
	20:		00000b33		add x22 x0 x0
	24:		000002b3		add x5 x0 x0
	28:		010000ef		jal x1 16 <loop1>
	2c:		000002b3		add x5 x0 x0
	30:		020000ef		jal x1 32 <loop2>
	34:		0340006f		jal x0 52 <end>

00000038 <loop1>:
	38:		00042a03		lw x20 0 x8
	3c:		014a8ab3		add x21 x21 x20
	40:		00440413		addi x8 x8 4
	44:		00128293		addi x5 x5 1
	48:		ff22c8e3		blt x5 x18 -16 <loop1>
	4c:		00008067		jalr x0 x1 0

00000050 <loop2>:
	50:		0004aa03		lw x20 0 x9
	54:		014b0b33		add x22 x22 x20
	58:		00448493		addi x9 x9 4
	5c:		00128293		addi x5 x5 1
	60:		ff32c8e3		blt x5 x19 -16 <loop2>
	64:		00008067		jalr x0 x1 0

00000068 <end>:
	68:		10000517		auipc x10 0x10000
	6c:		fac50513		addi x10 x10 -84
	70:		00400893		addi x17 x0 4
	74:		00000073		ecall
	78:		415b0533		sub x10 x22 x21
	7c:		00100893		addi x17 x0 1
	80:		00000073		ecall

### 5-stage pipelined processor

### Pipeline Hazard
There three types of data hazard
1. Data Hazard
Occurs when instructions exhibit data dependence modify data in different stages of a pipeline. There are three condictions in which a data hazard orrurs
* RAW
* WAR
* WAW
3. Structure Hazard
Occurs when two instructions that are already in pipeline need the same source.

3. Control Hazard
Occurs when pipeline makes wrong decisions which brings instructions into the pipeline that must subsequently be discarded.

## Reference
* [Ripes](https://github.com/mortbopet/Ripes)
* [RISCV pipeline and hazards](https://robotics.shanghaitech.edu.cn/courses/ca/19s/notes/Discussion8_2.pdf)