# Assignment1: RISC-V Assembly and Instruction Pipeline
###### tags: `RISC-V` `Computer Architecture`
contribute by <[`mingjii`](https://github.com/mingjii)>

## Hamming Distance
(The problem is based on [LeetCode 461](https://leetcode.com/problems/hamming-distance/).)

#### Description:
The Hamming distance between two integers is the number of positions at which the corresponding bits are different.

Given two integers **x** and **y**, return the Hamming distance between them.

#### Constraints:
$$
0 <= x, y <= 2^{32-1}
$$
#### Example:

### C code
Test example: `x` = 1, `y` = 4
Output: 4

#include <stdio.h>

int hammingDistance(int x, int y)
{
    // XOR operation will output 1 if two bit are different.
    int cmpResult = x ^ y;

    // Counting the bits of the compared result.
    int dis = 0;
    while (cmpResult)
    {
        if (cmpResult & 1)
        {
            ++dis; // If the right most bit is 1, result value + 1
        }
        cmpResult >>= 1; // Shift right one bit on every loop.
    }
    return dis;
}

int main()
{
    // Take x = 1, y = 4 for example
    int x = 1, y = 4;
    // Print the result
    printf("The Hamming Distance is %d\n", hammingDistance(x, y));
    return 0;
}

### Assembly code

.data
str: .string "The Hamming Distance is "

.text
# main funciton
main:
        addi    sp, sp, -12     # prologue
        sw      ra, 8(sp)       # prologue
        sw      s0, 4(sp)       # prologue
        sw      s1, 0(sp)       # prologue
        addi    s0, zero, 1     # s0 = 1, x
        addi    s1, zero, 4     # s1 = 4, y
        mv      a0, s0          # set argument, a0 = x
        mv      a1, s1          # set argument, a1 = y
        jal     ra, hammingDistance
        jal     ra, printResult
        lw      s0, 0(s0)       # epilodue
        lw      s1, 4(sp)       # epilodue
        lw      ra, 8(sp)       # epilodue
        addi    sp, sp, 12      # epilodue
        li      a7, 10          # exit the program
        ecall

# print function
printResult:
        addi    sp, sp, -4      # prologue
        sw      ra, 0(sp)       # prologue
        mv      t0, a0          # save variable dis to t0
        la      a0, str         # load string
        li      a7, 4           # print string
        ecall
        mv      a0, t0          # load variable dis from t0
        li      a7, 1           # print integer
        ecall
        lw      ra, 0(sp)       # epilodue
        addi    sp, sp, 4       # epilodue
        ret                     # return

# hammingDistance function
hammingDistance:
        addi    sp, sp, -12     # prologue
        sw      ra, 8(sp)       # prologue
        sw      s0, 4(sp)       # prologue
        sw      s1, 0(sp)       # prologue
        xor     s0, a0, a1      # s0 = x ^ y, cmpResult
        mv      s1, zero        # s1 = 0, dis
while:
        beq     s0, zero, exitFunc
isOdd:
        andi    t0, s0, 1       # t0 = cmpResult & 1
        beq     t0, zero, shiftRightOne # if t0 is false, then shift
        addi    s1, s1, 1       # ++dis
shiftRightOne:
        srai    s0, s0, 1       # athemtic shfit right one bit to s0
        j       while           # continue while loop
exitFunc:
        mv      a0, a1          # put the return value to a0
        lw      s0, 0(s0)       # epilodue
        lw      s1, 4(sp)       # epilodue
        lw      ra, 8(sp)       # epilodue
        addi    sp, sp, 12      # epilodue
        ret                     # return

#### Output on Ripes

## 5-stage pipelined processor
The **5-stage** means this processor using five-stage pipeline to parallelize instructions. The stages are:

1. **Instruction fetch (IF**):
- the instruction is being read out of instruction memory
- at the same time a calculation is done to determine the next PC
2. **Instruction decode and register fetch (ID**):
- decode instruction
- the indexes of these two registers are identified within the instruction
- the indexes are presented to the register memory, as the address
- Thus the two registers named are read from the register file
- If the instruction decoded is a branch or jump, the target address of the branch or jump is computed in parallel with reading the register file (branch condition is computed in the following cycle)
3. **Execute (EX**):
- this stage consists of an ALU, and also a bit shifter
- Register-Register Operation (Single-cycle latency): Add, subtract, compare, and logical operations.
- Memory Reference (Two-cycle latency): added the two arguments (a register and a constant offset) to produce a virtual address
- Multi-cycle Instructions (Many cycle latency): Integer multiply and divide and all floating-point operations.
4. **Memory access (MEM**):　if data memory needs to be accessed, it is done in this stage
5. **Register write back (WB**): during this stage, both single cycle and two cycle instructions write their results into the register file

## Reference
[Classic RISC pipeline](https://en.wikipedia.org/wiki/Classic_RISC_pipeline)