Try   HackMD

2017q3 Homework3 (simulator)

contributed by < maskashura >

預期目標

搭配 現代處理器設計，實際練習系統軟體開發
思考函式呼叫和掌握遞迴程式開發技巧
擴充給定的指令集 (ISA) 模擬器

執行環境

$lscpu

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

根據高德納（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開始，之後的費波那契系數就是由之前的兩數相加而得出
可用數學式表示為:

F0 = 0
F1 = 1
Fn=
Fn−1 +
Fn−2 , n >= 2

e.g.
0, 1, 1, 2, 3, 5, 8, 13, 21, 34, …

可以有 recursive 及 iterative 兩種寫法

RECURSIVE 版本

recursive 寫法易讀且精簡(近似於數學表示式), 但在遞迴時由於不斷呼叫而需要用到大量的 stack 空間及區域暫存空間來記錄,執行上較無效率且費時,其時間複雜度為O(

2n)












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同學共筆 )
    指令資料格式
    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 組語版本可寫成




























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)


















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























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表示需要輸入
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

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

/* 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 指令條件

#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 輸入參數

參考資料

Last changed by 
 
Bruce Ke
0
611
Published on HackMD