# 2020q3 Homework6 (kcalc)
contributed by < `RainbowEye0486` >

## 作業要求
- 在 GitHub 上 fork kcalc-fixed，目標是擴充數值運算器的功能，例如新增 sqrt, Sigma (∑), Pi (Π) 等等，可從 math-expression-evaluator 的 “Supported symbols” 選出幾項來實作。過程中應一併完成以下:
- [ ] 擴充數值運算器的時候，應一併提供測試案例，且該儘量反映出有效的數值範圍
- [ ] 留意乘法和加法的 overflow、減法的 underflow 等處理機制，分析後予以強化
- [ ] 確保數值運算的 precision 和 accuracy，甚至要考慮 Kahan summation algorithm →你可以修改原有 fixed-point 的設計和實作方式
- [ ] 觀察原始程式碼的 expression.[ch] 裡頭 vec 相關的程式碼，提出對空間效率更好的實作。考慮到 kcalc-fixed 的使用情境往往是持續接受一系列字串輸入，應避免頻繁的記憶體配置和釋放
- [ ] 修正現有 kcalc-fixed 內部數值運算的錯誤，並留意到不合法的記憶體操作;
- [ ] 指出原本 fixed-point 實作的限制，觀察 Linux 核心所用的 fixed-point 運算程式碼，提出針對 kcalc 的改進方案
- [ ] 原有的測試程式不會檢驗輸出數值，應予以擴充，得以自動和預先輸入的期望數值進行比對;

## 程式碼解讀

在這份作業中給訂了一些 API 以及自訂的資料結構，因此我從第一份的 MathEx 開始看起。執行

$ make check

後跑出正確的輸出，觀察 /test-unit 程式碼：

***test-unt.c***
- **test vector():** 測試 vec_push 、 vec_pop 、 vec_len 、 vec_foreach 等功能運作，根據 vec 本身的結構，操作類似 stack
- **test var():** expr_var 結構中變數與值的對應關係
- **test_tokizer():** 對應 token 以及給定字串之間的比較
- **test_expr():** 比較用 MathEx 計算出的方法跟直接運算的值正確性，如果是 NaN 或是誤差超過 0.00001f 就算計算失敗，為什麼會是以誤差值作為判斷的標準而不是直接 `==` 的原因是

***expression.c***
- **expr_eval():** 在 struct expr 中有定義所屬的種類，透過上面 emun
後面則給出各種測資驗證 MathEx 規則的正確性。驗證方式是透過傳入 `expr` ，檢查運算元和運算子組合的計算是否合法，可能會分成兩種情形，第一種是如 `uniry` 一樣只有一個運算元;另一種則是如比較大小之類的需要兩個運算元計算。

### 理解 load average

負載在 linux 中可以理解成 process 的數量多寡，因為作業前半部提到諸如 FPU 暫存器洩漏、非法存取到其他 process 的暫存器等原因，在核心中禁止使用浮點數進行運算，因此將定點數的後 11 位元當作小數部份，剩餘的高位元當作整數部份，因此才會出現需要左移右移 FSHIFT (精度)的情形。 linux kernel 對負載的計算方式是每隔五秒當一次間隔，讀取當前的 process 長度並且存成 `active` 的定點數

### 移植到核心 --- kcalc
我們在 MathEx 得到的所有 expr 回傳值都是 float 的方式回傳，但是在核心當中我們不使用浮點數，而是使用自定義的定點數，用32 bit 紀錄整數部份，另外 32 bit 紀錄小數部份，表示方式如下：

typedef union __fixedp {
    struct {
        uint32_t frac;
        uint32_t inte;
    };
    uint64_t data;
} fixedp;

### 留意乘法和加法的 overflow、減法的 underflow 等處理機制

現有的加法處理僅僅只有 `return a + b;` 而已，必須處理 overflow 或是 underflow 的問題。

### 檢驗輸出數值