# 2017q3 Homework3 (simulator)
contributed by < `maskashura` >
## 預期目標
搭配 現代處理器設計，實際練習系統軟體開發
思考函式呼叫和掌握遞迴程式開發技巧
擴充給定的指令集 (ISA) 模擬器
----
## 執行環境
$`lscpu`
```shell
Architecture: x86_64
CPU op-mode(s): 32-bit, 64-bit
Byte Order: Little Endian
CPU(s): 4
On-line CPU(s) list: 0-3
Thread(s) per core: 2
Core(s) per socket: 2
Socket(s): 1
NUMA node(s): 1
Vendor ID: GenuineIntel
CPU family: 6
Model: 142
Model name: Intel(R) Core(TM) i5-7300U CPU @ 2.60GHz
Stepping: 9
CPU MHz: 795.465
CPU max MHz: 3500.0000
CPU min MHz: 400.0000
BogoMIPS: 5424.00
Virtualization: VT-x
L1d cache: 32K
L1i cache: 32K
L2 cache: 256K
L3 cache: 3072K
NUMA node0 CPU(s): 0-3
```
----
## Fibonacci 數列 (費氏數列)
參考自[wikipedia](https://zh.wikipedia.org/wiki/%E6%96%90%E6%B3%A2%E9%82%A3%E5%A5%91%E6%95%B0%E5%88%97)
> 根據高德納（Donald Ervin Knuth）的《計算機程式設計藝術》（The Art of Computer Programming），150年印度數學家Gopala和金月在研究箱子包裝物件長寬剛好為1和2的可行方法數目時，首先描述這個數列。在西方，最先研究這個數列的人是比薩的李奧納多（義大利人斐波那契Leonardo Fibonacci），他描述兔子生長的數目時用上了這數列:
> * 第一個月初有一對剛誕生的兔子
> * 第二個月之後（第三個月初）牠們可以生育
> * 每月每對可生育的兔子會誕生下一對新兔子
> * 兔子永不死去
>
> 假設在n月有兔子總共a對，n+1月總共有b對。在n+2月必定總共有a+b對：因為在n+2月的時候，前一月（n+1月）的b對兔子可以存留至第n+2月（在當月屬於
> 新誕生的兔子尚不能生育）。而新生育出的兔子對數等於所有在n月就已存在的a對
Fibonacci 數列由0和1開始，之後的費波那契系數就是由==之前的兩數相加而得出==
可用數學式表示為:
$F_0$ = 0
$F_1$ = 1
$F_n$=$F_{n-1}$ + $F_{n-2}$ , n >= 2
`e.g.`
0, 1, 1, 2, 3, 5, 8, 13, 21, 34, ...
可以有 recursive 及 iterative 兩種寫法
#### RECURSIVE 版本
recursive 寫法易讀且精簡(近似於數學表示式), 但在遞迴時由於不斷呼叫而需要用到大量的 stack 空間及區域暫存空間來記錄,執行上較無效率且費時,其時間複雜度為O($2^n$)
```clike=
int Fibo(int n){
if(n == 0){
return 0;
}else if(n == 1){
return 1;
}else{
return Fibo(n-1)+Fibo(n-2);
}
}
```
* vm組語版本: (參考[`st9007a`同學共筆](https://hackmd.io/s/Hkf6pkPAb) )
指令資料格式
==name, opcode, has_op1, has_op2, has_result==
參數值: $
變數位址空間: #
==call #10== 則會jmup到第10+1行去執行
由於原生 vm 中沒有 mov 指令,可使用 or 及 xor 指令代替 mov
e.g.
*or $1 $0 #1*
把1存入#1的變數空間
*xor #0 #2 #1*
把#2內容存入#1的變數空間
故 recursion 組語版本可寫成
```clike=
or $0 $0 #3 ; init result(#3)=0
or $0 $0 #1 ; f0(#1) = 0
or $1 $0 #2 ; f1(#2) = 1
call #6 ; call recursion function
print #3 ; print result(#3)
halt
;[addr #6] (recursion function)
xor #0 #2 #5 ; mov f1(#2) to #5
jz #5 #9 ;if #5=0 then goto #9
jnz #5 #11 ;if #5!=0 then goto #11
add #3 #2 #3 ;[addr #9] n(#3)=n(#3)+f1(#2)
ret
;[addr #11]
xor #0 #1 #5 ;mov f0(#1) to #5
jz #5 #14 ;if #5=0 then goto #14
jnz #5 #15 ;[addr #14]if #5!=0 then goto #15
ret
;[addr #15]
sub #0 $1 #0 ;#0=#0-1
call #6
sub #0 $1 #0 ;#0=#0-1
call #6
add #0 $2 #0 ;#0=#0+2
ret
```
#### ITERATIVE 版本
不需 stack 空間做像遞迴呼叫時的位置存取, 執行上較有效率, 其時間複雜度為O(n)
```clike=
int Fibo(int n){
if(n == 0){
return 0;
}else if(n == 1){
return 1;
}else{
int a = 0;
int b = 1;
int i, c;
for(i = 1; i < n; i++){
c = a + b;
a = b;
b = c;
}
return c;
}
}
```
* vm組語版本:(參考[`st9007a`同學共筆](https://hackmd.io/s/Hkf6pkPAb) )
```clike=
xor #0 $0 #1 ;mov #0 to #1
jz #1 #13 ;if #1=0 then goto #13
sub #0 $1 #0 ;#0=#0-1
or $0 $0 #1 ; f0(#1) = 0
or $1 $0 #2 ; f1(#2) = 1
;[addr #5] iteration
add #1 #2 #3 ;#3=#2+#1
or $0 #2 #1 ;move #2 to #1
or $0 #3 #2 ;move #3 to #2
sub #0 $1 #0 ;#0=#0-1
jz #0 #11 ;if #5=0 then goto #11
jgt #0 #5 [addr #14]if #5 > 0 then goto #5
;[addr #11] print result
print #3
halt
;[addr #13] if #0 = 0, just print 0
print $0
halt
```
----
## 程式解析
* `driver.c`為vm程式的主程式,用以做各個功能傳遞
* `as.c`
* `elf.c`
* `opcode.c` 定義了指令的實作,而在`opcode.h`中, 有定義支援的 operator 指令, 參數部份0表示支不需要輸入,而1表示需要輸入
```clike
static const struct instruction instrs[] = {
{"halt", OP_HALT, 0, 0, 0},
{"add", OP_ADD, 1, 1, 1},
{"sub", OP_SUB, 1, 1, 1},
{"print", OP_PRINT, 1, 0, 0},
{"jlt", OP_JLT, 1, 1, 0},
{"jle", OP_JLE, 1, 1, 0},
{"jz", OP_JZ, 1, 1, 0},
{"jge", OP_JGE, 1, 1, 0},
{"jgt", OP_JGT, 1, 1, 0},
{"jnz", OP_JNZ, 1, 1, 0},
{"jmp", OP_JMP, 1, 0, 0},
{"mul", OP_MUL, 1, 1, 1},
{"div", OP_DIV, 1, 1, 1},
{"mod", OP_MOD, 1, 1, 1},
{"call", OP_CALL, 1, 0, 0},
{"ret", OP_RET, 0, 0, 0},
{"and", OP_AND, 1, 1, 1},
{"or", OP_OR, 1, 1, 1},
{"not", OP_NOT, 1, 1, 0},
{"xor", OP_XOR, 1, 1, 1},
{"lsl", OP_LSL, 1, 1, 1},
{"lsr", OP_LSR, 1, 1, 1},
{"asr", OP_ASR, 1, 1, 1},
{NULL, 0}
};
```
指令資料格式
==name, opcode, has_op1, has_op2, has_result==
* `vm.c`中定義了 virtual machine 的架構，`vm_regs` 和 `vm_env` 分別定義了vm中暫存器和環境變數
`vm_regs`
```clike
typedef struct {
size_t pc; // program counter.
size_t sp; // stack runs from the end of 'temps' region.
size_t from; // the immediate PC before last branch/return.
size_t to; // the immediate PC after last branch/return.
} vm_regs;
```
`vm_env`
```clike
/* Constant pool max size */
#define CPOOL_MAX_SIZE 100
/* Instruction max size */
#define INSTS_MAX_SIZE 200
/* Temporary storage max size */
#define TEMPS_MAX_SIZE 150
/* OPCODE impl max size */
#define OPCODE_IMPL_MAX_SIZE 256
struct __vm_env {
vm_inst insts[INSTS_MAX_SIZE]; /* Program instructions */
vm_value cpool[CPOOL_MAX_SIZE]; /* Constant pool */
vm_value temps[TEMPS_MAX_SIZE]; /* Temporary storage */
vm_opcode_impl impl[OPCODE_IMPL_MAX_SIZE]; /* OPCODE impl */
vm_regs r;
int insts_count;
int cpool_count;
int temps_count;
};
```
其中也定義了各種 jump 指令條件
```clike
#define VM_JLT() VM_J_TYPE_INST(<)
#define VM_JLE() VM_J_TYPE_INST(<=)
#define VM_JZ() VM_J_TYPE_INST(==)
#define VM_JGE() VM_J_TYPE_INST(>=)
#define VM_JGT() VM_J_TYPE_INST(>)
#define VM_JNZ() VM_J_TYPE_INST(!=)
```
修改接受 --input 輸入參數
----
### 參考資料
* [Fibonacci_number, From wikipedia](https://en.wikipedia.org/wiki/Fibonacci_number)
* [Fibonacci Sequence](https://www.mathsisfun.com/numbers/fibonacci-sequence.html)
* [遞迴-recursive-介紹與經典題型](https://hellolynn.hpd.io/2017/08/19/%E9%81%9E%E8%BF%B4-recursive-%E4%BB%8B%E7%B4%B9%E8%88%87%E7%B6%93%E5%85%B8%E9%A1%8C%E5%9E%8B/)
* [`st9007a`同學共筆](https://hackmd.io/s/Hkf6pkPAb)
Sign in with Wallet
Connect another wallet