# 2017q3 Homework3 (simulator)
contributed by <`zhanyangch`>

## 分析 [full-stack-hello](https://github.com/sysprog21/full-stack-hello) 程式架構
driver 中負責讀取使用者的輸入，並呼叫對應的函式
* as.c 將虛擬機器的組合語言組譯成機器碼，並且提供寫入、讀取 elf 檔案
* elf.c 處理 elf 所需要的 header
* opcode.c 實做虛擬機器指令集(不包含 j type)
* vm.c 實做虛擬機器環境、j type 指令

### 觀察虛擬機器執行

driver.c 可以接受不同的參數，先不看跟 elf 有關的部份
case ASSEMBLE_AND_EVAL

   case ASSEMBLE_AND_EVAL: {
        vm_env *env = vm_new();
        assemble_from_fd(env, in_fd);
        hook_opcodes(env);
        vm_run(env);
        vm_free(env);
        break;
    }

* 首先先建立虛擬機器的環境

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;
};

* 觀察 vm_regs 可以發現此 sturct 主要紀錄程式的狀態，而一般運算的 register 則是在 temps 內。

 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;

* assemble_from_fd 此函式將指令的 operand 建立對應的 vm_inst 放入 env 的 insts 中，遇到常數時會呼叫 vm_add_const 將常數加入 env 的 cpool。
* hook_opcodes：將 opcode 的實做放入 env 的 impl
* vm_run：包含每個 opcode 對應的 label 利用 gcc 提供的 [Labels-as-Values](https://gcc.gnu.org/onlinedocs/gcc/Labels-as-Values.html)可以使用
`&&OP_CODE` 得到 label address，放入 dispatch table 中，在每一個 instruction 的結尾執行 DISPATCH
，此方式稱為 direct threaded code
* vm_free 釋放記憶體空間

### 指令形式
* 算術運算
- [ ] `add $40 $2 #1`
`$`: 常數
`#`: 暫存器(temps)
* conditional jump
- [ ] `jz #1 #14`
`#1`: 暫存器(temps)
`#14`: 條件成立時跳到第14個指令

## 接受 command line 參數
[參考st9007a的共筆](https://hackmd.io/s/Hkf6pkPAb)
接受"--input <value>"的參數將 #0 初始化成<value>
首先在 driver.c 中 加入讀取 --input，在這裡使用 strtol 而非 atoi，原因是 atoi 對於無法處理的字串會回傳 0，但無法區別 0 是因為輸入錯誤或是數字 0而產生，因此無法偵測到錯誤，使用 strtol *pEnd 會被設為讀取完數字後的下一個字元，在這裡 pEnd 若非 '\0'，則代表沒有成功讀取數字

else if (!strcmp(argv[i], "--input")) {
    char *pEnd;
    if (!argv[i + 1])
        FATAL(-1, "--input need a integer as argument, see -h\n");
    temp_init_val = strtol(argv[++i], &pEnd, 10);
    if (*pEnd)
        FATAL(-1, "--input need a integer as argument, see -h\n");
} 

>> 依據給定的 coding style，用 4-spaces 來排版上述程式碼
>> [name="jserv"][color=red]

在 vm.[ch] 中加入 vm_set_temp_value

inline void vm_set_temp_value(vm_env *env, int id, int val)
{
    env->temps[id].type = INT;
    env->temps[id].value.vint = val;
}

driver.c 中呼叫 vm_set_temp_value

    case ASSEMBLE_AND_EVAL: {
        vm_env *env = vm_new();
        vm_set_temp_value(env, 0, temp_init_val);
        assemble_from_fd(env, in_fd);
        hook_opcodes(env);
        vm_run(env);
        vm_free(env);
        break;
    }

## 實作 Fibonacci 數列
### iterative
目前採用 int 儲存計算結果，因此當輸入超過 46 時會產生 integer overflow
:::danger
需要指出目前採用的 [LP64](https://en.wikipedia.org/wiki/64-bit_computing#64-bit_data_models) 資料模型下，`int` 實質為 32-bit，而 fib(46) 尚在 32-bit 能表示的數值範圍內。

另外，除了給予輸入數值範圍的提示，也需要提出後續數值表示法的調整方案。

:notes: jserv
:::

jz #0 #11
jlt #0 #16    ;check #0 >= 0
sub $46 #0 #4
jlt #4 #16    ;check #0 <= 46

sub #0 $1 #0

or $0 $0 #1; #1=0
or $1 $0 #2; #2=1
;for
add #1 #2 #3 ; fib = # 1+ #2
or #2 $0 #1  ;#1 = #2
or #3 $0 #2  ;#2 = fib
sub #0 $1 #0
jgt #0 #7

print #3
halt
;if #0 = 0 ,  print 0
print #0
halt
;limit n:0~46
print "Please use 0~46 as an input value."
halt

### Recursive

jz #0 #10
jlt #0 #11 ;check #0 >= 0
sub $46 #0 #4
jlt #4 #11 ;check #0 <= 46

or $0 $0 #3 ;#3 for ans
call #12    ;call f(n)

print #3
halt
;if #0 = 0, print 0
print #0
halt
;limit n:0~46
print "Please use 0~46 as an input value."
halt

xor #0 $1 #5 ;check #0 == 1 
jz #5 #15    ;if true, do #3+=1
jmp #17      ;return
add #3 $1 #3 
ret

jz #0 #19 ;if true, return
jmp #20   ;call f(n-1), f(n-2)
ret 

sub #0 $1 #0
call #12
sub #0 $1 #0
call #12
add #0 $2 #0
ret

## 新增 label 的支援
* 觀察並修改 [Add label support](https://github.com/jserv/full-stack-hello/pull/30)

原本的跳躍指令只能接受跳到某個絕對位置，但在寫程式時，若要新增或刪除指令，則需要將跳躍指令的參數做大量修改，藉由新增對 label 的支援，可以由組譯器幫忙計算跳躍的位置。

組譯的實做方法如下：
1. 當遇到 jmp :<label> 時新增vm_operand * label_reference，使用指標紀錄該 operand 的位置、label 的名稱
- [ ] `as.c`

static inline vm_operand make_operand(vm_env *env, char *line, const char *data)
{
    /*...*/
    case ':':
    op.type = LABEL;
    op.label = rm_comment_strdup(data + 1);
    break;
    /*...*/
}

- [ ] `vm.c`

size_t vm_add_inst(vm_env *env, vm_inst inst)
{
    env->insts[env->insts_count] = inst;
    if (inst.op1.type == LABEL)
        vm_add_label_ref(env,&env->insts[env->insts_count].op1);
    if (inst.op2.type == LABEL)
        vm_add_label_ref(env,&env->insts[env->insts_count].op2);
    return env->insts_count++;
}

2. 當遇到 <label>: 時新增 vm_label labels，紀錄 label 的名稱、當下的 pc
- [ ] `vm.c`

size_t vm_add_label(vm_env *env, char *label) {
    if (vm_find_label(env, label) != -1)
        FATALX(1, "Label '%s' redefinition\n", label);
    env->labels[env->labels_count].label = strdup(label);
    env->labels[env->labels_count].next_pc = env->insts_count;
    return env->labels_count++;
}

:::danger
修正上述訊息的文法錯誤

:notes: jserv
:::

3. 當讀取完整份檔案後，將每一個 label_reference 找到對應的 vm_label，將其 value.id 改為 vm_label 內紀錄的 pc 值
- [ ] `vm.c`

void vm_register_label(vm_env *env)
{
   for (int i = 0; i < env->label_refcnt; ++i) {
        env->label_ref[i]->value.id = vm_find_label(env, env->label_ref[i]->label);
        if(env->label_ref[i]->value.id == -1)
            FATALX(1,"Label Register Error: Label \"%s\" not found\n", env->label_ref[i]->label);
    }
}