# 2017q3 Homework3 (simulator)
contributed by < `changyuanhua` >
## 閱讀筆記
### 現代處理器設計
- [ ] 閱讀 [現代處理器設計](http://hackfoldr.org/cpu) 教材和觀看裡頭所有錄影，記錄你的心得和疑惑
#### 原理和關鍵特徵
#### Cache 原理和實際影響
#### 虛擬機器設計與實作
### 你所不知道的 C 語言：編譯器和最佳化原理篇
- [ ] 對照研讀 [你所不知道的 C 語言：編譯器和最佳化原理篇](https://hackmd.io/s/Hy72937Me) 教材和觀看直播錄影，以得知編譯器運作原理
### 你所不知道的C語言：遞迴呼叫篇
- [ ] 閱讀 [你所不知道的C語言：遞迴呼叫篇](https://hackmd.io/s/rJ8BOjGGl) 和觀看對應講座錄影
- [ ] 用 [full-stack-hello](https://github.com/sysprog21/full-stack-hello) 的指令實作 Fibonacci 數列
- [x] 需要包含 recursive 和 non-recursive 實作，分別置於檔案 `tests/fib-recursive.s` 和 `tests/fib-iterative.s`
- [x] 修改 `vm.c` (和對應的原始程式碼)，允許執行時期由使用者 (和 `Makefile`) 帶入參數，如 `--input`，這數值應該透過暫存器作為上述 Fibonacci 數列程式的 `Fib(N)`
- [ ] 研究現有 [full-stack-hello](https://github.com/sysprog21/full-stack-hello) 的自動測試程式，整合上述兩種 Fibonacci 程式實作，並且比較效能 (需要包含 vm 內部的 cycle count)
- [ ] 考慮以下 Fibonacci 數列的實作方式，並善用 GNU plot 製圖和解讀
- [x] Tail recursion
- [ ] Q-Matrix
- [ ] Fast doubling
## 開發環境
```
Architecture: x86_64
CPU 作業模式： 32-bit, 64-bit
Byte Order: Little Endian
CPU(s): 4
On-line CPU(s) list: 0-3
每核心執行緒數：1
每通訊端核心數：4
Socket(s): 1
NUMA 節點： 1
供應商識別號： GenuineIntel
CPU 家族： 6
型號： 94
Model name: Intel(R) Core(TM) i5-6300HQ CPU @ 2.30GHz
製程： 3
CPU MHz： 799.890
CPU max MHz: 3200.0000
CPU min MHz: 800.0000
BogoMIPS: 4608.00
虛擬： VT-x
L1d 快取： 32K
L1i 快取： 32K
L2 快取： 256K
L3 快取： 6144K
NUMA node0 CPU(s): 0-3
```
## 解析程式架構
以 `driver.c` 為主要程式，其他程式作為輔助，提供相關的函式，下面分別簡單概述每個程式的主要功能：
* opcode：自訂指令集，以及相關實作，實作主要用於虛擬機器
* as：組譯器，用於組譯自訂指令集，產生對應的 object file
* elf：提供產生 object file 相關的函式
* vm：虛擬機器，內涵虛擬機器的架構, 運作
## 接受輸入參數
在 `vm.h` 和 `vm.c` 加入一個可以設定 temps 的值的函式 `vm_set_temp_value(vm_env *env, int pos, int val)` ： 接收輸入參數，並將輸入參數存入 vm 中的 #0 位置
```clike=
inline void vm_set_temp_value(vm_env *env, int pos, int val)
{
vm_value v = {.type = INT};
v.value.vint = val;
env->temps[pos] = v;
}
```
接著在 `driver.c` 中 `argv` 的部份加入 --input 的判斷，並以 `input` 紀錄輸入的值
```clike=
int input = 0;
...
else if (!strcmp(argv[i], "--input")) {
if (!argv[i + 1])
FATAL(-1, "Missing argument\n");
input = atoi(argv[++i]);
}
...
```
接著在 `driver.c` 中初始化 vm 的下一行都強制設定 **#0**
```clike=
vm_env *env = vm_new();
vm_set_temp_value(env, 0, input);
```
最後在 `Makefile` 內新增 Fibonacci 相關的操作
```cmake=
TEMP ?= 10
FIB_ITERATIVE ?= ./tests/fib-iterative.s
FIB_RECURSIVE ?= ./tests/fib-recursive.s
fib: $(EXEC)
@./$(EXEC) --input $(TEMP) $(FIB_ITERATIVE)
@./$(EXEC) --input $(TEMP) $(FIB_RECURSIVE)
```
reference: [st9007a 共筆](https://hackmd.io/s/Hkf6pkPAb)
## 實作 Fibonacci 數列
### iteration
c code:
```clike=
int iterative(int x) {
int first = 0 , second = 1 , result = 0;
if (x == 0)
return n;
if (x == 1)
return n;
int i = x - 1;
while(i > 0) {
i--;
result = first + second;
first = second;
second = result;
}
return result;
}
```
組合語言：
```clike=
; #0: x
; if (x == 0) return x
jz #0 #15
; if (x == 1) return x
sub #0 $1 #4
jz #4 #15
or $0 #4 #0
; #1: first = 0
; #2: second = 1
; #3: result = 0
or $0 $0 #1
or $0 $1 #2
or $0 $0 #3
; iteration
jz #0 #13
sub #0 $1 #0
add #1 #2 #3
or $0 #2 #1
or $0 #3 #2
call #7
print #3
halt
print #0
halt
```
### recursive
c code:
```clike=
int recursive(int x) {
if (x == 0) return 0;
if (x == 1) return 1;
return recursive(x - 1) + recursive(x - 2);
}
```
組合語言：
```clike=
; #0: x
; #1: result = 0
or $0 $0 #1
call #4
print #1
halt
; if (x == 0) return 0;
or $0 #0 #2
jz #2 #12
jnz #2 #8
ret
; if (x == 1) return 1;
sub #0 $1 #2
jz #2 #11
jnz #2 #13
add #1 $1 #1
ret
; fib_ecursive(n-1)
sub #0 $1 #0
call #4
; fib_recursive(n-2)
sub #0 $1 #0
call #4
add #0 $2 #0
ret
```
### tail recursive
c code:
```clike=
int tail_recursive(int x, int a = 0, int b = 1)
{
if (x == 0)
return a;
if (x == 1)
return b;
return tail_recursive(x-1, b, a+b);
}
```
組合語言：
```clike=
; #0: x
; #1: a = 0
; #2: b = 1
; #3: result = 0
or $0 $0 #1
or $0 $1 #2
or $0 $0 #3
call #6
print #3
halt
; if (x == 0) return a
or #0 $0 #4
jz #4 #9
jnz #4 #11
or $0 #1 #3
ret
; if (x == 1) return b
sub #0 $1 #4
jz #4 #14
jnz #4 #16
or $0 #2 #3
ret
; tail_recursive(x-1, b, a+b)
sub #0 $1 #0
or $0 #1 #4
or $0 #2 #1
add #2 #4 #2
call #6
ret
```
### Q-Matrix
The Fibonacci Q-matrix 的定義為下方式子：
$Q=\left [
\begin{array}{cc}
F_2 & F_1 \\
F_1 & F_0
\end{array}
\right ]=\left[
\begin{array}{cc}
1 & 1 \\
1 & 0
\end{array}
\right ]$ ，其中 $F_n$ 是斐波納契數。
$Q$ 的n次方： $Q^n=\left [
\begin{array}{cc}
F_{n+1} & F_n \\
F_n & F_{n-1}
\end{array}
\right ]$
而得知 $Det（A^n）= Det（A）^n$ ，因此得到下列性質：
$Det（Q^n）= Det（-1）^n$
又因此結合上述式子，可以得到：
$Q^{n}Q^{1}=Q^{n+1}$，
$Det（Q^n）= F_{n-1}F_{n+1}-F_n^2 = （-1）^n$
然後就能得知下列式子：
$Q^{n+1}=\left[
\begin{array}{cc}
F_{n+1} & F_n \\
F_n & F_{n-1}
\end{array}
\right ]$$\left[
\begin{array}{cc}
F_{2} & F_{1} \\
F_{1} & F_{0}
\end{array}
\right ]=\left[
\begin{array}{cc}
F_{n+2} & F_{n+1} \\
F_{n+1} & F_{n}
\end{array}
\right ]$
也就是說，每次做矩陣乘法，$F_n$ 會被 $F_{n+1}$ 取代
組合語言
```clike=
; #0: n
; #1: F0 = 0
; #2: F1 = 1
; #3; F2 = 1
; #4; result = 0
or $0 $0 #1
or $0 $1 #2
or $0 $1 #3
or $0 $0 #4
; if (n == 0) return 0
jz #0 #25
; if (n == 1) return 1
sub #0 $1 #5
jz #5 #25
or $0 #5 #0
sub #0 $1 #0
jz #0 #23
; F2 = 1*F2 + 1*F1
mul $1 #3 #4
mul $1 #2 #5
add #4 #5 #4
; F1 = 1*F2 + 0*F1
mul $1 #3 #5
mul $0 #2 #6
add #5 #6 #5
; F0 = 1*F1 + 0*F0
mul $1 #2 #6
mul $0 #1 #7
add #6 #7 #6
or $0 #4 #3
or $0 #5 #2
or $0 #6 #1
call #8
print #4
halt
print #0
halt
```
### Fast doubling
Sign in with Wallet
Connect another wallet