2025q1 Homework3 (kxo)

contributed by < Hlunlun >

作業書寫規範:

無論標題和內文中，中文和英文字元之間要有空白字元 (對排版和文字搜尋有利)
文字訊息 (尤其是程式執行結果) 請避免用圖片來表示，否則不好搜尋和分類
共筆書寫請考慮到日後協作，避免過多的個人色彩，用詞儘量中性
不要在筆記內加入 [TOC] : 筆記左上方已有 Table of Contents (TOC) 功能，不需要畫蛇添足
不要變更預設的 CSS 也不要加入任何佈景主題: 這是「開發紀錄」，用於評分和接受同儕的檢閱
當在筆記中貼入程式碼時，避免非必要的行號，也就是該手動將 c= 或 cpp= 變更為 c 或 cpp。行號只在後續討論明確需要行號時，才要出現，否則維持精簡的展現。可留意「你所不知道的 C 語言: linked list 和非連續記憶體」裡頭程式碼展現的方式
HackMD 不是讓你張貼完整程式碼的地方，GitHub 才是！因此你在開發紀錄只該列出關鍵程式碼 (善用 diff 標示)，可附上對應 GitHub commit 的超連結，列出程式碼是為了「檢討」和「便於他人參與討論」
留意科技詞彙的使用，請參見「資訊科技詞彙翻譯」及「詞彙對照表」
不要濫用 :::info, :::success, :::warning 等標示，儘量用清晰的文字書寫。:::danger 則僅限授課教師作為批注使用
避免過多的中英文混用，已有明確翻譯詞彙者，例如「鏈結串列」(linked list) 和「佇列」(queue)，就使用該中文詞彙，英文則留給變數名稱、人名，或者缺乏通用翻譯詞彙的場景
在中文敘述中，使用全形標點符號，例如該用「，」，而非 ","。注意書名號的使用，即 〈 和 〉，非「小於」和「大於」符號
避免使用不必要的 emoji 字元

開發中遇到的問題

沒辦法把 module 放到 linux kernel 中
```
lun@lun-OMEN:~/linux2025/hw3/kxo$ sudo insmod kxo.ko
[sudo] password for lun: 
insmod: ERROR: could not insert module kxo.ko: Key was rejected by service
```
- 分析：一開始以為是 make 後警告訊息的原因，然後就在更改 linux-headers 和 linux-image 的版本，結果完全不是，是因為有啟動 UEFI Secure Boot，這個安全標準會造成 kernel 模組需要簽名的安全金鑰才可以放到 kernel 中執行 (以下參考 The Linux Kernel Module Programming Guide 第 1.7 章)
  
  SecureBoot. Numerous modern computers arrive pre-configured with UEFI SecureBoot enabled—an essential security standard ensuring booting exclusively through trusted software endorsed by the original equipment manufacturer. Certain Linux distributions even ship with the default Linux kernel configured to support SecureBoot. In these cases, the kernel module necessitates a signed security key.
- 解決：我是直接進去 Machine Owner Key (MOK) 的界面把 Secure Boot 禁用了，這樣最快
  1. 以下指令是管理 UEFI Secure Boot 的命令，可以請求禁用 UEFI Secure Boot 的模組簽名驗證功能，它會叫你設置一組密碼，等等進入 MOK 會用到
```
sudo mokutil --disable-validation
```
  2. 然後重啟電腦
```
sudo reboot
```
  3. 會進入一個藍色的畫面，這就是 MOK，選擇 "Change Secure Boot state"
  4. 然後選擇禁用 Secure Boot 驗證
  5. 然後會要求你輸入剛才設置的密碼：是用問你密碼第幾個字元是什麼的方式教你輸入

閱讀作業說明

Linux 核心的浮點數運算

kernel 中沒有浮點數的運算，所以要手動紀錄並在之後恢復，這在 kernel space 和 user space 轉換之間要注意

Monte Carlo Tree Search 理解

閱讀教材

你所不知道的 C 語言：數值系統篇

balanced ternary
- 不用像二進位數考慮 unsigned 和 signed
- 小數點的運算會更簡單
- IOTA：過度效率 over engineering？

數值表達

空集合是否屬於空集合？

單精度浮點運算: 為什麼最後一個不是 NaN ?

#include<stdio.h>
int main(){
    printf("%f\n", 1e20*1e20*1e20);
    printf("%f\n", 1e20*(1e20*1e-20));
    printf("%f\n", 1e20*(1e20-1e20));
    printf("%f\n", 1e20*1e20-1e20*1e20);
}
//9999999999999949387135297074018866963645011013410073083904.000000
//100000000000000000000.000000
//0.000000
//0.000000

為什麼要考慮浮點數符不符合結合律？
浮點數不具結合性

$\to$ 所以要思考電腦有多少位元可以承載這些數值：如波音 787 造成 overflow 的案例

$\to$ 若是沒有考慮到這層會造成在不同電腦上有不同的答案

Integer Overflow
- int 是否唯有號數取決於編譯器與硬體
- 潛在被攻擊的可能
計算機編碼
- ARM 中的 char 是 unsigned，char 就是一種 integer
- 補數的出現
  $\to$ 不用考慮正負號和絕對值，只要找到補數就可將加法便減法，但會有循環進位的問題
- 1960 發生了很多事，發展了一補數(ones')、Linus 出生，ARPAnet(網路前身)也在那時使用了一補數編碼
- 二補數(two's)：是封閉阿爾貝群
- side channel attack: 利用加解密的時間差（就是 Dude, is my code constant time? 提及的 timing leakage? ）

你所不知道的 C 語言: bitwise 操作

bloader: 只有相當小的資源，所以希望不要占用到太多記憶體的資源
XOR swap 就是一個很好的方式，可以不用用到額外的記憶體空間就可以交換兩個數

假設: x=5, y=3

x ^= y
 1001 x
^0011 y
-----
 1010 -> x
 
y ^= x
 0011 y
^1010 x
-----
 1001 -> y

x ^= y
 1010 x
^1001 y
-----
 0011 -> x
 
最後: x=3, y=5

位移運算
- 左移超過變數長度時
```
int i= 0xFFFFFFFF;
i = i<<32;
```
- 右移一個負數時，可能是算術位移或是邏輯位移?
  
  ?
sizeof 是 operator，回傳 unsigned 的數值
做中學，不用背
- Set bit: 將 x 的第 n 個位元設為 1，和第 n 個位元為 1 的值做 logical or
- Clear bit: 將 x 的第 n 個位元設為 0，和第 n 個位元為 0 其他位元為 1 的值做 logcial and
- Toggle bit: 將 x 的第 n 個位元若為 0 就改為 1 、若為 1 就改為 0，和第 n 個位元為 1 的值做 exclusize or
- Test bit: 看 x 的第 n 個位元有沒有值，和第 n 個位元為 1 的值做 logcial and，結果是否大於 0 就是第 n 個位元有沒有值
- The right/left most byte:
- Sign bit: 跟最高位元是 1 的值做 logical and
NEON

2025q1 Homework3 (kxo)

開發中遇到的問題

閱讀作業說明

Linux 核心的浮點數運算

Monte Carlo Tree Search 理解

閱讀教材

你所不知道的 C 語言：數值系統篇

你所不知道的 C 語言: bitwise 操作

NEON

Read more

`.venv` 虛擬環境

2025q1 Homework5 (assessment)

2025q1 Homework1 (ideas)

2025q1 Homework1 (lab0)