---
title: Lab1 RV32I
tags: RISCV
---
# [268. Missing Number](https://leetcode.com/problems/missing-number/description/)
## Description
Given an array nums containing n distinct numbers in the range [0, n], return the only number in the range that is missing from the array.
## Code

/**
 * 268. Missing Number
 * Given an array nums containing n distinct numbers in the range [0, n], 
 * return the only number in the range that is missing from the array.
 * Return the minimum number of patches required.
 * 
 * Thought:
 * 1. Because we know that nums array contains n numbers and that it is missing exactly one number on the range [0..n−1].
 * 2. we know that n definitely replaces the missing number in nums. 
 * 3. Therefore, if we initialize an integer to n and XOR it with every index and value, we will be left with the missing number.
 */

#include<stdio.h>

int missingNumber(const int*, const int);

int main()
{
    const int nums[] = {3, 0, 1};
    const int numsSize = 3;
    printf("%d\n", missingNumber(nums, numsSize));
    return 0;
}

int missingNumber(const int* nums, const int numsSize)
{
    int ans = numsSize;
    for (int i = 0; i < numsSize; ++i) {
        ans ^= i ^ nums[i];
    }
    return ans;
}

## Assembly Code

.data
nums:    .word 3, 0, 1
numsSize:    .word 3

.text
#include<stdio.h>
#
#int missingNumber(const int*, const int);
#
#int main()
#{
#    const int nums[] = {3, 0, 1};
#    const int numsSize = 3;
#    printf("%d\n", missingNumber(nums, numsSize));
#    return 0;
#}
#
#int missingNumber(const int* nums, const int numsSize)
#{
#    int ans = numsSize;
#    for (int i = 0; i < numsSize; ++i) {
#        ans ^= i ^ nums[i];
#    }
#    return ans;
#}

main:
    la     a0, nums         # a0 = nums[];  // array
    lw     a1, numsSize     # a1 = numsSize;     // length of the array
    jal    ra, missingNumber   # Function call

    # a0 is the return value and also the value we want to print
    li     a7, 1            # print a0
    ecall
    li     a0, 0            # return 0
    li     a7, 10           # Exit code
    ecall                   
    
missingNumber:
    addi   s0, a1, 0        # s0 = ans
    addi   s1, x0, 0        # s1 = i
    bgeu   s1, a1, exit     # i < numsSize
    loop:
        slli   t0, s1, 2    # t0 = i*4
        add    t0, a0, t0   # t0 = nums + i*4
        lw     t0, (0)t0    # t0 = nums[i]
        #nop
        xor    t0, t0, s1   # t0 = i XOR num[i]
        xor    s0, s0, t0   # ans = ans XOR t0
        addi   s1, s1, 1    # ++i
        bgeu   s1, a1, exit # i < numsSize
        j      loop
exit:
    mv     a0, s0           # return value = ans
    ret

## Analysis
### IF
* PC 從 0x0 開始
* 其對應的值為
* machine code 為
### ID
* 在 ID 階段，cpu 會 decoded 從 IF 階段過來的指令(0x00058413)，以 ```addi x8 x10 0``` 為例，addi 會把 x10 暫存器的值與 0 相加後再放回 x8 暫存器
* ID 階段最後可以看到 reg1 輸出 x11 暫存器的值 0x3

### EXE
* 在 EXE 階段，指令會被執行，這邊可以看到在存取 x10 暫存器的值時會有 ==Read-after-write hazard== 的問題，所以要從 MEM/EB 暫存器取值(黃色線)
### MEM
* 這邊會負責處理需要 data memory 的部分像是 LW、SW 等指令，但由於現在指令是 addi 不需要 memory，所以會跳過
### WB
* 最後 WB 階段再把結果存回指定的暫存器
### Control hazard
* branch 的結果尚未產生時，後續的指令就已經進入 pipeline，如果決定要 branch 到別的位置便會發生錯誤
* 這邊透過把指令 flush 掉來避免