# Linux 核心專題: 重作第 7 週測驗題
> 執行人: 56han
> [專題解說影片](https://youtu.be/zNOGMaRL8SI)
### Reviewed by `ssheep773`
當我們計算 (p << 64) / b 時，目的是得到一個非常大的數字，使得在後續的除法操作中結果更準確。直接計算 (p << 64) / b 可能會因為整數除法而產生誤差。
這部分中非常大的數字實際大小是多少 ?並會產生多大的誤差 ?
### Reviewed by `LindaTing0106`
在 TODO: 第 7 週測驗第二題中提到 __builtin_expect 的使用是為了進行更佳的分支預測及優化，那麼可以展示一下有使用與未使用在效能上面的差異嗎？
### Reviewed by `Lccgth`
> SWAR 技術則是通過在寄存器內部同時處理多個較小的資料單元來提高計算效率。
:::danger
注意用語：
寄存器 -> 暫存器
> 已修正表達方式
:::
### Reviewed by `yuyuan0625`
下文解釋乘法運算比除法運算在 CPU 上執行更快的引用可以補上來源網址
### Reviewed by `yy214123`
```c
static inline uint64_t bit_compound(uint32_t x, uint32_t y)
{
return ((0L + x) << 32) | ((y + 0L) & (-1L >> 32));
}
```
這部分的程式會將兩個 32 位元合併為 64 位元，我的想法是：
```c
return ((0L + x) << 32) | ((y + 0L)
```
我的想法是如此已經完成合併，那為何還需要：
```c
& (-1L >> 32)
```
又或者這個步驟有其特殊目的但我沒發覺？
### Reviewed by `david965154`
> 比較 Linux 核心原本的實作和 memchr_opt，設計實驗來觀察隨著字串長度和特定 pattern 變化的效能影響
這裡測試 Linux 核心原本的 `memchr` 是軟體實作版本還是硬體實作版本 ? 我自己實測下來與軟體實作版本相比， opt 結果是好上不少的，但是與硬體實作版本相比也是會表現較差。
## 任務簡介
重作[第 7 週測驗題](https://hackmd.io/@sysprog/linux2024-quiz7)和延伸問題，探究 bitops 在 Linux 核心的應用。
## TODO: [第 7 週測驗](https://hackmd.io/@sysprog/linux2024-quiz7)第一題
> 包含延伸問題
### 合併 2 個 32 位元寬度的整數
Question: 為什麼 x 和 y 都要加 0L，再進行位移？
Answer: 因為 x 和 y 的位元寬是 32 位元 (`uint32_t`) ，左移 32 <s>位</s> 個位元會超出它的位元寬，會出現 **warning: left shift count >= width of type**。long 是 64 位元，左移 32 個位元在這種情況下是合法的，不會引發警告。
`(-1L >> 32)` 計算出的值是`1111 1111 1111 1111 1111 1111 1111 1111 1111 1111 1111 1111 1111 1111 1111 1111`。
```c
static inline uint64_t bit_compound(uint32_t x, uint32_t y)
{
return ((0L + x) << 32) | ((y + 0L) & (-1L >> 32));
}
```
### SIMD within a register (SWAR)
延伸閱讀: [SIMD and SWAR Techniques](https://www.chessprogramming.org/SIMD_and_SWAR_Techniques)
SIMD 單指令流多資料流（Single Instruction Multiple Data，SIMD）：是一種採用一個控制器來控制多個處理器，同時對一組資料中的每一個分別執行相同的操作，從而實現空間上平行的技術。
:::danger
什麼「並列性」？
使用精準且明確的術語。
>「並列性」一詞是參考[維基百科網站](https://zh.wikipedia.org/zh-tw/%E5%8D%95%E6%8C%87%E4%BB%A4%E6%B5%81%E5%A4%9A%E6%95%B0%E6%8D%AE%E6%B5%81)，但經過閱讀[並行程式設計:概念](https://hackmd.io/@sysprog/concurrency/%2F%40sysprog%2Fconcurrency-concepts)，我認為「平行」一詞更加合適。
>Concurrency 指程式架構，將程式拆開成多個可獨立運作的工作，像是驅動程式都可獨立運作，但不需要平行化。Parallelism 則指程式執行，同時執行多個程式。Concurrency 可能會用到 Parallelism，但不一定要用 Parallelism 才能達成 Concurrency。
:::
SWAR (SIMD within a register)：在一個暫存器上進行單指令多資料流操作。它是一種跨 CPU 暫存器各部分應用 SIMD 平行處理的處理模型，在 SIMD（單指令多資料）並行處理模型中，這些 byte-entities（即小於一個字串的資料單位）經常被用來在一個 CPU <s>寄存器</s> 暫存器的不同部分上進行並行計算。
### SWAR 技術在加法運算中的差異和優勢
#### 一般加法
這樣的加法操作會直接對整個 64 <s>位</s> 的<s>數字</s> 數值 進行運算，包括進位。
```c
uint64_t z = x + y;
```
#### SWAR 加法
SWAR 技術則是通過在暫存器內部同時處理多個較小的資料單元來提高計算效率。例如，對於 64 位暫存器，我們可以將其視為包含了 8 個 8 位的 byte，並對每個 byte 進行獨立的加法運算。使用 SWAR 技術，我們可以在一個指令中並行地對所有 byte 進行加法運算。具體的 SWAR <s>技術</s> 技巧加法公式如下：
```c
z = ((x &~H) + (y &~H)) ^ ((x ^ y) & H)
```
其中，`x &~H` 和 `y &~H` 去掉了每個 byte 的最高位，以避免在進行無進位加法時受到影響，再透過 `(x ^ y) & H` 找出每個 byte 中的進位情況。
如此一來，在一次操作中就能對所有的 byte 進行加法計算，而不需要逐個處理進位，這大大提高了運算效率。
:::danger
你宣稱的「大大提高了運算效率」是多少呢？能量化嗎？你檢驗過了嗎？若沒有，不就淪為人云亦云嗎？
:::
#### 優勢
:::danger
via 和 through 不該翻譯為「通過」，否則無法區分 "pass" 的翻譯。改說「經由」或「藉由」
:::
1. 高效並行計算：SWAR 技術利用並行計算的特性，使得對每個 byte 的加法運算可以同時進行，大大提高了計算速度。
2. 簡化進位處理：傳統的逐字串加法需要逐個處理進位，而 SWAR 技巧 <s>通過</s> 位元操作巧妙地合併了無進位加法結果和進位結果，簡化了進位處理的過程。
3. 減少迭代次數：傳統方法需要多次迭代來處理每個 byte 的加法，而 SWAR 技術在一個指令中完成所有 byte 的加法運算，減少了迭代次數。
### SWAR Arithmetic
For bytewise (rankwise) math inside a 64-bit register, `H` is `0x8080808080808080` and `L` is `0x0101010101010101`.
#### z = x + y
```c
z = ((x &~H) + (y &~H)) ^ ((x ^ y) & H)
```
詳細步驟：
1. 計算非進位和：
`x &~H` 和 `y &~H` 去除了每個 byte 的最高位（sign bit），留下其餘 7 位來進行無進位加法。
```c
(x &~H) + (y &~H)
```
2. 處理進位：
`x ^ y` 會找出 `x` 和 `y` 在每個 byte 中不相同的位元（即可能產生進位的位置）。然後與 `H` 進行 AND 操作來確保只保留最高位，透過這個操作，我們只保留了那些可能進位的位置。：
```c
(x ^ y) & H
```
3. 最終結果合併：
最後一步是用 XOR 把去掉最高位進行加法的結果和進位進行合併。XOR 用來處理進位的效果：如果沒有進位，原結果保持不變；如果有進位，則原結果的該位會翻轉。
```c
((x &~H) + (y &~H)) ^ ((x ^ y) & H)
```
#### 加法例題 x + y = ?
`H` = `1000 0000`
`x` = `0000 0001`
`y` = `1111 1110`
1. 計算非進位和：
`~H` = `0111 1111`
`x &~H` = `0000 0001`
`y &~H` = `0111 1110`
`(x &~H) + (y &~H)` = `0111 1111`
2. 處理進位：
`x^y` = `1111 1111`
`(x^y) & H` = `1000 0000`
3. 最終結果合併：
`((x &~H) + (y &~H)) ^ ((x ^ y) & H)` = `1111 1111`
### 解釋上述程式碼運作原理
本程式預期可以在一段 string 中找到一個字元，並印出該字元後的 string。
```c
int main()
{
const char str[] = "https://wiki.csie.ncku.edu.tw";
const char ch = '.';
char *ret = memchr_opt(str, ch, strlen(str));
printf("String after |%c| is - |%s|\n", ch, ret);
return 0;
}
```
預期執行結果：
```text
String after |.| is - |.csie.ncku.edu.tw|
```
1. 檢查記憶體對齊
檢查指標 `X` 是否與 `long` 的邊界對齊。如果 `X` 沒有對齊，則返回非零值。
```c
#define UNALIGNED(X) ((long) X & (sizeof(long) - 1))
```
為什麼要檢查記憶體是否對齊？
* 提高記憶體存取效率：大多數現代處理器在處理對齊的記憶體存取時效率更高，因為對齊的地址允許處理器在一次操作中存取整個記憶體單元。
* 減少記憶體存取錯誤：一些處理器在遇到未對齊的記憶體存取時會引發異常 (exception) 或陷阱 (trap)，這會導致程式崩潰。透過檢查對齊，可以避免這些潛在的錯誤。
* <s>優化</s> 低層記憶體操作：在進行底層記憶體操作（如 `memcpy`、`memset` 等）時，處理對齊問題可以使這些操作更加高效。
:::danger
避免濫用「優化」ㄧ詞，務必詳閱 https://hackmd.io/@sysprog/it-vocabulary
:::
2. 定義每次迭代載入的位元組數
定義每次迭代載入的 `long` 型別的大小（通常為 4 或 8 Byte）。
```c
#define LBLOCKSIZE (sizeof(long))
```
3. 定義過小的長度
檢查長度是否小於一個 `long` 型別的大小。
```c
#define TOO_SMALL(LEN) ((LEN) < LBLOCKSIZE)
```
4. 檢測空位元組
根據不同的 long 型別大小，定義檢測空字串的巨集。
```c
#if LONG_MAX == 2147483647L
#define DETECT_NULL(X) (((X) - (0x01010101)) & ~(X) & (0x80808080))
#else
#if LONG_MAX == 9223372036854775807L
#define DETECT_NULL(X) \
(((X) - (0x0101010101010101)) & ~(X) & (0x8080808080808080))
#else
#error long int is not a 32bit or 64bit type.
#endif
#endif
```
一開始不明白為何可以運用 `0x0101010101010101` 和 `0x8080808080808080` 的邏輯運算，進而判斷是否 DETECT NULL。
直到我看到[你所不知道的 C 語言：數值系統篇](https://hackmd.io/@sysprog/c-numerics)，
由已知的計算方式來逆推作者可能的思考流程。
首先先將計算再簡化一點點，將他從 `(((X) - 0x01010101) & ~(X) & 0x80808080)` 變成
```
((X) - 0x01) & ~(X) & 0x80
```
將以前學過的笛摩根定理套用上去，於是這個式子就變成了
```
~( ~(X - 0x01) | X ) & 0x80
```
再稍微調整一下順序
```
~( X | ~(X - 0x01) ) & 0x80
```
所以就可以進行分析
* `X | ~(X - 0x01)` => 取得最低位元是否為 0，並將其他位元設為 1
* `X` = `0000 0011` => `1111 1111`
* `X` = `0000 0010` => `1111 1110`
* `0x80` 是什麼? `0x80` 是 `1000 0000` ，也就是 1-byte 的最高位元
上面這兩組組合起來，我們可以得到以下結果
* `X` = 0 => `1000 0000` => 0x80
* `X` = 1 => `0000 0000` => 0
* `X` = 2 => `0000 0000` => 0
* …
* `X` = 255 => `0000 0000` => 0
於是我們得知原來這樣的運算，如果一個 byte 是 0，那經由這個運算得到的結果會是 `0x80`，反之為 0。
再將這個想法擴展到 32 位元，在 32 位元的情況下，0 會得到 `0x80808080`。
5. 檢測特定位元組
檢測 `X` 是否包含指定的字串，利用 XOR 操作，目的是將 `X` 中所有與 `mask` **相同**的位元組變為 0。
```c
#define DETECT_CHAR(X, mask) DETECT_NULL((X) ^ (mask)) //AAAA
```
6. 處理未對齊部分
在字串未對齊的情況下逐個字串檢查，直到對齊或長度為零。
```c
const unsigned char *src = (const unsigned char *) str;
unsigned char d = c;
while (UNALIGNED(src)) {
if (!len--)
return NULL;
if (*src == d)
return (void *) src;
src++;
}
```
7. 處理長度對齊的部分
如果長度足夠大且已對齊，則按 `long` 型別大小逐塊處理：建立 `mask`，將 `d` 字串複製到 `long` 的每個位元組中。
```clike=
if (!TOO_SMALL(len)) {
unsigned long *asrc = (unsigned long *) src;
unsigned long mask = d << 8 | d;
mask |= mask << 16;
for (unsigned int i = 32; i < LBLOCKSIZE * 8; i <<= 1)
mask |= mask << i; //BBBB
```
第三行的 `mask` = `0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0010 1110 0010 1110`
第四行的 `mask` = `0000 0000 0000 0000 0000 0000 0000 0000 0010 1110 0010 1110 0010 1110 0010 1110`
第六行的 `mask` = `0010 1110 0010 1110 0010 1110 0010 1110 0010 1110 0010 1110 0010 1110 0010 1110`
`LBLOCKSIZE` 通常是 8，因此 `LBLOCKSIZE * 8` 為 64。所以迴圈實際上只執行了一次，我認為這裡不需要使用 `for` 迴圈也可以達到一樣的效果。事實上在進入 `for` 迴圈前 `d` 字串 已經完成複製至後 32 位元的 `mask` 中了，僅需寫一行 `mask |= mask << 32;` 即可。但是 `for` 迴圈設計為能夠靈活應對不同的 `LBLOCKSIZE` 或其他位寬度環境。
:::danger
設計實驗並分析產生的組合語言指令序列。
:::
8. 快速搜尋
檢測是否包含目標字串。如果找到，則退出循環。
:::danger
不用抄寫題目，也就是 AAAA, BBBB, CCC 這些填空應予以消除，專注在程式碼本身。
:::
```c
while (len >= LBLOCKSIZE) {
if (DETECT_CHAR(*asrc, mask)) //CCCC
break;
asrc++;
len -= LBLOCKSIZE;
}
```
9. 進一步尋找剩餘字串中符合的字元
```c
src = (unsigned char *) asrc;
}
while (len--) {
if (*src == d)
return (void *) src;
src++;
}
```
### 比較 Linux 核心原本的實作和 `memchr_opt`，設計實驗來觀察隨著字串長度和特定 pattern 變化的效能影響
#### 實驗設計
1. 字串長度變化：測試不同長度的字串，例如 1KB、10KB、100KB、1MB、10MB 等。
2. 特定模式變化：在字串中不同位置放置目標字元，例如開頭、中間、結尾，以及不存在的情況。
3. 多次運行：為了減少隨機誤差，每個測試情況下運行多次，取平均值。
4. 記錄時間：使用高解析度計時器（`clock_gettime`）記錄每次函數運行的時間。
#### 解釋
`measure_memchr` 和 `measure_memchr_opt`：分別測量 `memchr` 和 `memchr_opt` 的執行時間。
`run_experiment`：測試不同長度的字串，並在不同位置測試字母的存在。使用多次運行來獲取平均執行時間。其中 `void * memset ( void * str , int c , size_t n )` 函式將指定的值 `c` 複製到 `str` 所指向的記憶體區域的前 `n` 個位元組中，這可以用於將記憶體區塊清除或設定為特定值。
:::danger
注意書寫規範：
* 使用 lab0 規範的程式碼書寫風格，務必用 clang-format 確認一致
* 注意看[程式碼規範](https://hackmd.io/@sysprog/linux2024-lab0-a)的「clang-format 工具和一致的程式撰寫風格」，筆記列出的程式碼依循指定的風格。
:::
```c
void run_experiment(size_t length) {
char *str = malloc(length);
if (!str) {
perror("malloc");
exit(EXIT_FAILURE);
}
// Initialize the string with some pattern, e.g., 'a'
memset(str, 'a', length);
// Positions to test: start, middle, end, not present
size_t positions[] = {0, length / 2, length - 1, length + 1};
for (int i = 0; i < 4; i++) {
size_t pos = positions[i];
char c = (pos < length) ? 'b' : 'z';
if (pos < length) str[pos] = c;
double memchr_time = 0, memchr_opt_time = 0;
int iterations = 10;
for (int j = 0; j < iterations; j++) {
memchr_time += measure_memchr(str, c, length);
memchr_opt_time += measure_memchr_opt(str, c, length);
}
memchr_time /= iterations;
memchr_opt_time /= iterations;
printf("Length: %zu, Position: %zu, memchr: %f, memchr_opt: %f\n",
length, pos, memchr_time, memchr_opt_time);
if (pos < length) str[pos] = 'a'; // Reset character
}
free(str);
}
```
`main`：呼叫 `run_experiment`，測試不同的字串長度。
```c
int main() {
size_t lengths[] = {1 * KB, 10 * KB, 100 * KB, 1 * MB, 10 * MB};
for (int i = 0; i < 5; i++) {
run_experiment(lengths[i]);
}
return 0;
}
```
#### 分析結果
輸出：
```text
Length: 1024, Position: 0, memchr: 25.400000, memchr_opt: 42.30
Length: 1024, Position: 512, memchr: 18.100000, memchr_opt: 186.80
Length: 1024, Position: 1023, memchr: 22.700000, memchr_opt: 353.40
Length: 1024, Position: 1025, memchr: 26.400000, memchr_opt: 321.10
Length: 10240, Position: 0, memchr: 16.900000, memchr_opt: 35.00
Length: 10240, Position: 5120, memchr: 22.000000, memchr_opt: 1377.00
Length: 10240, Position: 10239, memchr: 13.400000, memchr_opt: 2315.40
Length: 10240, Position: 10241, memchr: 13.500000, memchr_opt: 2301.70
Length: 102400, Position: 0, memchr: 13.400000, memchr_opt: 28.20
Length: 102400, Position: 51200, memchr: 13.600000, memchr_opt: 11468.70
Length: 102400, Position: 102399, memchr: 13.500000, memchr_opt: 22922.40
Length: 102400, Position: 102401, memchr: 13.700000, memchr_opt: 24046.20
Length: 1048576, Position: 0, memchr: 14.000000, memchr_opt: 23.80
Length: 1048576, Position: 524288, memchr: 17.100000, memchr_opt: 146928.40
Length: 1048576, Position: 1048575, memchr: 14.700000, memchr_opt: 242553.50
Length: 1048576, Position: 1048577, memchr: 16.000000, memchr_opt: 237409.20
Length: 10485760, Position: 0, memchr: 19.900000, memchr_opt: 43.60
Length: 10485760, Position: 5242880, memchr: 13.400000, memchr_opt: 1238596.00
Length: 10485760, Position: 10485759, memchr: 13.500000, memchr_opt: 2516725.30
Length: 10485760, Position: 10485761, memchr: 13.600000, memchr_opt: 2506135.20
```
:::danger
使用 gnuplot 製圖
>已補上，但是時間（y 軸）相差太大，待修改。
:::
從結果中可以看到，大部分情況下，`memchr` 的運行時間比 `memchr_opt` 短，這可能是由於以下幾個原因：
1. 函數呼叫開銷：
`memchr_opt` 在開始時進行了額外的對齊檢查和預處理步驟，這增加了開銷。
2. 對齊檢查：
`memchr_opt` 進行了對齊檢查，這會導致在字串長度較小或未對齊時，額外的開銷可能超過了任何潛在的優化收益。當字串較短時，對齊檢查和其他操作可能反而降低了效能。
3. 分支預測失敗：
`memchr_opt` 中的條件分支較多，例如對齊檢查和字串長度檢查，可能會導致分支預測失敗，這會影響效能。
4. 記憶體存取模式：
當處理較大資料塊時，`memchr_opt` 利用了 SIMD 技術進行批量處理，這可能在更大資料塊下顯示出優勢，但在較小資料塊下，這些優化的開銷可能反而導致性能下降。
---
### 研讀 [2022 年學生報告](https://hackmd.io/@arthur-chang/linux2022-quiz8)，在 Linux 核心原始程式碼找出 x86_64 或 arm64 對應的最佳化實作，跟上述程式碼比較，並嘗試舉出其中的策略和分析
Linux 核心原始程式碼找出 x86 對應的最佳化實作：[arch/x86/lib/string_32.c](https://github.com/torvalds/linux/blob/master/arch/x86/lib/string_32.c)
```c
void *memchr(const void *cs, int c, size_t count)
{
int d0;
void *res;
if (!count)
return NULL;
asm volatile("repne\n\t"
"scasb\n\t"
"je 1f\n\t"
"movl $1,%0\n"
"1:\tdecl %0"
: "=D" (res), "=&c" (d0)
: "a" (c), "0" (cs), "1" (count)
: "memory");
return res;
}
```
:::danger
注意上方程式碼距離「最佳化」還很遠，你應該解釋其可改進之處。
:::
#### x86 最佳化實作策略
1. 利用 x86 指令集中的 `repne scasb` 指令進行快速字串掃描。
2. 透過使用 inline assembly，程式碼量減少且更加高效。
#### `memchr_opt` 實作策略
1. 檢查記憶體地址是否對齊，對齊後進行後續處理。
2. 使用多字串（例如 `unsigned long` ）進行處理，以加快速度。
3. 設置比對遮罩，使用 `DETECT_CHAR` 巨集進行高效比對。
4. 在多字串處理失敗時，回退到單字串處理。
#### 整體分析
x86 最佳化實作：利用了 x86 指令集的特性，通過 inline assembly 直接操作 CPU 指令來提高效能，適合 x86 平台，簡單高效。
`memchr_opt` 實作：使用通用的 C 語言進行<s>優化</s> ，具有跨平台的可移植性，但在特定平台上的性能可能不如專門針對該平台進行優化的實作。
## TODO: [第 7 週測驗](https://hackmd.io/@sysprog/linux2024-quiz7)第二題
> 包含延伸問題
:::danger
注意用語。
:::
<s>優化</s> 64 位元除法的效能，尤其是當除數是常數時。透過在編譯時進行倒數計算，這些巨集和函式能夠顯著減少運行時的計算負擔，從而提升效能。
### 解釋上述程式碼運作原理
1. `likely` 巨集
在許多原始碼 linux 核心都可以看到這個巨集。使用 `!!` 將 x 轉換為布林值，並使用 GCC 的內建函數 `__builtin_expect`，告訴編譯器 `x` 的值很可能為真，以便進行更好的分支預測和<s>優化</s> 。
```c
#define likely(x) __builtin_expect(!!(x), 1)
```
為什麼要使用 `__builtin_expect` <s>函數</s>？它究竟有什麼作用呢？
* 現在處理器都是管線的，系統可以提前取多條指令進行並行處理，但遇到跳轉時，則需要重新取指令，跳轉指令打亂了 CPU 管線。因此，跳轉次數少的程式擁有較高的執行效率。
* 在 C 語言程式設計時，會不可避免地使用 if-else 分支語句，if-else 編譯後，一個分支的編譯程式碼緊接著前面的程式碼，而另一個分支的編譯程式碼需要使用 JMP 指令才能存取。很明顯透過 JMP 存取需要更多的時間，在複雜的程式中，有很多的 if-else 句型，又或者是一個有 if-else 句型的函數庫函數，每秒被呼叫幾萬次，通常程式設計師在分支預測方面做得很糟，編譯器又不能精準的預測每一個分支，這時 JMP 產生的時間浪費就會很大。
* 因此，引入 `__builtin_expect` 函數來增加條件分支預測的準確性，CPU 會提前裝載後面的指令，遇到條件轉移指令時會提前預測並裝載某個分支的指令。編譯器會產生對應的程式碼來優化 CPU 執行效率。
2. 檢查一個數是否為 2 的冪
如果 `n` 是 2 的冪，則它的二進位表示中只有一個位為 1，n & (n - 1) 應該等於 0。
```c
static inline bool is_power_of_2(unsigned long n)
{
return (n != 0 && ((n & (n - 1)) == 0));
}
```
3. 計算 32 / 64 位元整數 `x` 的二的對數
使用內建函式 `__builtin_clz` 計算前導零的數量，再根據位元數進行轉換。
```c
static inline int __ilog2_u32(uint32_t x)
{
return x ? sizeof(x) * 8 - __builtin_clz(x) - 1 : 0;
}
static inline int __ilog2_u64(uint64_t x)
{
uint32_t h = x >> 32;
if (h)
return sizeof(h) * 8 - __builtin_clz(h) + 31;
return x ? sizeof(x) * 8 - __builtin_clz(x) - 1 : 0;
}
```
`__builtin_clz` 這個函數作用是傳回輸入數二進位表示：從最高位元開始 ( 左起 ) 連續的 0 的個數；如果傳入 0 則行為未定義。
```c
int __builtin_clz ( unsigned int x)
int __builtin_clzl ( unsigned long )
int __builtin_clzll ( unsigned long long )
```
三個不同的<s>函數</s> 分別用於 unsigned int 、 unsigned long 以及 unsigned long long。
來源： [Other Built-in Functions Provided by GCC](https://gcc.gnu.org/onlinedocs/gcc-8.3.0/gcc/Other-Builtins.html)
4. 計算任意整數 n 的二的對數
其中 `__builtin_constant_p` 是編譯器 GCC 內建函數，判斷 n 在 compiler time 是否為常數，是的話就 return `1` 並使用 `(n) < 2 ? 0 : 63 - __builtin_clzll(n)` ，否則 return `0` 並使用 `(sizeof(n) <= 4) ? __ilog2_u32(n) : __ilog2_u64(n)` ，但根據 [GCC 手冊](https://gcc.gnu.org/onlinedocs/gcc/Other-Builtins.html)，**這不代表 `n` 不是常數，只是 GCC 無法證明它是在活躍的優化選項集限制內的常數。**
> The function returns the integer 1 if the argument is known to be a compile-time constant and 0 if it is not known to be a compile-time constant. A return of 0 does not indicate that the value is not a constant, but merely that GCC cannot prove it is a constant within the constraints of the active set of optimization options.
```c
#define ilog2(n) \
(__builtin_constant_p(n) ? ((n) < 2 ? 0 : 63 - __builtin_clzll(n)) \
: (sizeof(n) <= 4) ? __ilog2_u32(n) \
: __ilog2_u64(n))
```
**在活躍的優化選項集限制內的常數** ( a constant within the constraints of the active set of optimization options ) 是什麼？
:::danger
使用本課程教材規範的術語。
:::
* <s>優化</s> 選項的影響
不同的優化選項會影響編譯器如何判斷一個值是否可以被視為常數。例如，某些優化選項可能允許編譯器進行更積極的 constant folding，這是一種在編譯期間計算表達式結果，並用該結果替換表達式的技術。
* 利用 gcc `__builtin_constant_p` 協助於編譯時期進行 Constant folding (propagation)，於[你所不知道的 C 語言：編譯器和最佳化原理篇](https://hackmd.io/@sysprog/c-compiler-optimization?type=view#%E4%BD%A0%E6%89%80%E4%B8%8D%E7%9F%A5%E9%81%93%E7%9A%84-C-%E8%AA%9E%E8%A8%80%EF%BC%9A%E7%B7%A8%E8%AD%AF%E5%99%A8%E5%92%8C%E6%9C%80%E4%BD%B3%E5%8C%96%E5%8E%9F%E7%90%86%E7%AF%87)介紹過其觀念。表示當 `__builtin_constant_p` 用於 macro 或 inline function 時，傳入的參數為 常數數值，當開啟編譯器最佳化 `-O` 選項後即會進行 constant folding。
5. 64 位整數除以 32 位整數的操作
>This approach multiplies by the reciprocal of b: to divide n by b, we multiply n by ( p / b ) and then divide by p.
$\dfrac{n}{b}$ = n $\times$ $\dfrac{p}{b}$ $\times$ $\dfrac{1}{p}$
因為**乘法運算**比除法運算**在 CPU 上執行更快**，它需要更少的 CPU 週期和更少的指令數量。透過事先計算除數的倒數，使得除法轉換為乘法，從而提高運算效率。
:::danger
用第一手材料來說明上方陳述，避免人云亦云。
:::
>The efficiency comes from the compiler's ability to optimize much of this code during compile time through constant propagation, leaving behind only a few multiplication operations. This is why we use this large macro, as a static inline function does not consistently achieve the same optimization.
編譯器在編譯期間能夠透過 constant propagation 來優化這段程式碼，最終只留下少量的乘法操作，因此提高運算效率。constant propagation：一種編譯器優化技術，編譯器會分析程式碼中的常數，並將這些常數值直接替換到程式碼中的變數，從而減少運行時的計算量。
為什麼巨集可以達到更好的 constant propagation 效果？而 inline function 不行？
<!-- :::danger
務必使用本課程指定教材的術語。
preprocessor 是「前置處理器」: https://hackmd.io/@sysprog/c-preprocessor
為何捨近求遠？
>已補上資料來源
::: -->
>As the C preprocessor can be invoked separately from the compiler with which it is supplied, it can be used separately, on different languages.
Notable examples include its use in the now-deprecated imake system and for preprocessing Fortran.
原來 C preprocessor 以獨立程式的形式存在，所以當我們用 gcc 或 cl (Microsoft 開發工具裡頭的 C 編譯器) 編譯給定的 C 程式時，會呼叫 cpp (伴隨在 gcc 專案的 C preprocessor) 一類的程式，先行展開巨集 (macro) 或施加條件編譯等操作，再來 才會出動真正的 C 語言編譯器 (在 gcc 中叫做 cc1)。
主要原因是巨集在階段進行文本替換，使得編譯器能夠更早、更靈活地對展開的程式碼進行優化。而 inline function 仍然保留了函數的特性和約束，優化效果可能受到限制。因此，在需要充分利用 constant propagation 進行優化的情況下，巨集通常比 inline function 更有效。
#### 計算 `___p`
`___p` ：`___b` 的最高有效位。
```c
uint32_t ___p = 1 << ilog2(___b);
```
#### 計算 `___m`，使其接近 `((p << 64) + b - 1) / b` 的值
想法：
* `(p << 64) / b`：將 p $\times$ 2^64^ 除以 `b`。
* `(p << 64 / b) + (b - 1) / b`：為了進一步調整結果，使得 `m` 更接近 `(p << 64) / b`。這樣可以確保在進行後續的計算時，誤差最小化。
實際寫法：
* `~0ULL` ： `0xffffffffffffffff`，是一個全為 1 的 64 位元無符號整數，接近 2^64^。
* `___m = (~0ULL / ___b) * ___p`：可視為 (2^64^ / b) $\times$ p，將 `p` 調換位置到最前面就可得 (p $\times$ 2^64^) / b = `(p << 64) / b`。
```c
___m = (~0ULL / ___b) * ___p;
```
* 當我們計算 `(p << 64) / b` 時，目的是得到一個非常大的數字，使得在後續的除法操作中結果更準確。直接計算 `(p << 64) / b` 可能會因為整數除法而產生誤差。
* 只要再加上 `(b - 1) / b` 的部分，就可以達到接近 `((p << 64) + b - 1) / b` 的值。
* 但除此之外又補上了 `(~0ULL % ___b + 1) * ___p)`，目的是增加精度，這樣除以 `___b` 時結果更加接近實際值。
```c
___m += (((~0ULL % ___b + 1) * ___p) + ___b - 1) / ___b;
```
數學證明：
註解想表達的是：$m =\frac{(p \times 2^{64} + b - 1)}{b}=\frac{(p \times 2^{64})}{b}+\frac{b-1}{b}$
但是程式碼硬生生多出了 `(~0ULL % ___b + 1) * ___p)` ，看似不必要的片段，所以我們可以透過除法公式分析。
> 根據除法公式：
> $a=bq+r$
> 其中 $a$ 為被除數、$b$ 為除數、$q$ 為商數、$r$為餘數。
> 兩邊同時加一 $\therefore a+1=bq+(r+1)$
>
> 令：
> $2^{64} - 1 = q \times b + r$
> $2^{64} =q \times b + r+1$
>
> 根據註解可知：
> $m =\frac{(p \times 2^{64} + b - 1)}{b}=\frac{(p \times(q \times b + r+1)+b-1)}{b}$
>
> 展開可得：
> $m =\frac{pqb+pr+p+b-1}{b}=\frac{pqb}{b}+\frac{(r+1)p+b-1}{b}$
>
> 最後通分：
> $m= pq +\frac{(r+1)p+b-1}{b}$
> 其中：
> $q$ = ~0ULL / $b$
> $r$ = ~0ULL % $b$
透過觀摩 [yy214123 同學的期末專題](https://hackmd.io/@sysprog/rkt-cdRrC#TODO-%E7%AC%AC-7-%E9%80%B1%E6%B8%AC%E9%A9%97%E9%A1%8C%E6%B8%AC%E9%A9%97-2)，才了解這一段程式碼的意義。
<!-- :::danger
提供數學證明。
>已補上數學證明。
::: -->
#### 得到最大結果的被除數減 1
```c
/* one less than the dividend with highest result */
___x = ~0ULL / ___b * ___b - 1;
```
透過計算最大無符號整數 (`~0ULL`) 可以整除 `___b` 的最大值，然後減去 1，得到一個略小於最大無符號整數，且能夠使除法運算結果最大化的被除數。
目的：在進行大數除法時，可以用來檢查和處理極限情況。
>$x$ = $qb$ - 1
#### 利用 `res = m * x / (p << 64)` 檢查 `___m` 是否在數學上正確表達了近似值 `(p << 64) / b`
計算 `___m` 和 `___x`，模擬 64 位數字相乘的低位部分。
計算 `___m` 的低 32 位和 `___x` 的高 32 位相乘，並加到 `___res` 中，更新 `___res` 的值，同時將這個中間結果保存到 `___t` 中。
```c
___res = ((___m & 0xffffffff) * (___x & 0xffffffff)) >> 32;
___t = ___res += (___m & 0xffffffff) * (___x >> 32);
```
計算 `___x` 的低 32 位和 `___m` 的高 32 位相乘，並加到 `___res` 中，進一步更新 `___res` 的值。
檢查 `___res` 是否小於 `___t`，如果是，代表有溢出情況，則 `___t` 設置為 `1ULL << 32`，否則設置為 `0`。附註：因為 `___res` 越加越小是不合理的，所以 `___res` < `___t` 一定是有溢出情況。
```c
___res += (___x & 0xffffffff) * (___m >> 32);
___t = (___res < ___t) ? (1ULL << 32) : 0;
```
`___res` 右移 32 位，並加上 `___t`，這樣可以得到乘法結果的高 32 位部分。
計算 `___m` 和 `___x` 的高 32 位相乘，並加到 `___res` 中，得到整個 64 位乘法結果的最終值。最後將 `___res` 除以 `___p`，得到最終的結果。
```c
___res = (___res >> 32) + ___t;
___res += (___m >> 32) * (___x >> 32);
___res /= ___p;
```
#### 清理並提高當前實現的效率 - 特殊情況的處理
`if (~0ULL % (___b / (___b & -___b)) == 0)`：檢查 `___b` 是否為 2 的冪。
:::info
`___b & -___b`：用來找出 `___b` 的最低有效位（LSB）。
* `-___b` 等價於 `(~___b + 1)`，即將 `___b` 取反後再加 1。
* `___b = 6`，其二進位表示為 `0000 0110`。
* `-___b = 1111 1010`。
* `___b & -___b = 0000 0010`，即 `2`。
:::
當 `___b` 是 2 的冪時，`___b` 只有一個位元為 1，其餘位元全為 0。例如：
* 2 的二進位是 0000 0010
* 4 的二進位是 0000 0100
* 8 的二進位是 0000 1000
這時，`___b & -___b` 會等於 `___b` 本身。假設 `___b = 8`：
* `___b = 0000 1000`
* `-___b = 1111 1000`（取反加 1）
* `___b & -___b = 0000 1000`
所以 `___b & -___b = 8`，`___b / (___b & -___b) = 8 / 8 = 1`。如果 `___b` 是 2 的冪，則 `___b / (___b & -___b)` 的結果是 1，然後 `~0ULL % 1 == 0`。這是因為任何數對 1 取餘數都等於 0。
```c
if (~0ULL % (___b / (___b & -___b)) == 0) {
/* special case, can be simplified to ... */
___n /= (___b & -___b);
___m = ~0ULL / (___b / (___b & -___b));
___p = 1;
___bias = true;
}
```
由於 `___b & -___b` 會等於 `___b` 本身且 `___b / (___b & -___b)` 的結果是 1，因此上面的程式碼中的變數可轉換為：
```c
...
___n = ___n / ___b;
___m = ~0ULL;
...
```
這裡我不理解，因為 `if (~0ULL % (___b / (___b & -___b)) == 0)` 這個情況只發生在 `___b` 是 2 的冪時成立，但是如果`___b` 是 2 的冪並不會進入此巨集。
`if (~0ULL % (___b / (___b & -___b)) == 0)` 有可能在其他情況下成立嗎？
<!-- :::danger
不懂就說不懂，不要說「不太懂」，後者不會讓你過得比較快樂。
你作過哪些實驗呢？不要「舉燭」。
::: -->
#### 清理並提高現有程式碼的效率 - 偏差修正
`else if (___res != ___x / ___b)`，說明在透過乘法和位移運算來近似除法的過程中，出現了由於有限精度和位截斷引起的誤差。
>It is necessary to introduce a bias to counteract errors caused by bit truncation.
位元截斷就是當我們處理浮點數或大數進行除法、乘法等運算時，計算結果可能超出變數類型所能表示的範圍。為了解決這個問題，我們通常會截斷多餘的位元，這可能導致數值誤差。為了減少這些誤差，需要引入一個偏差這個偏差是一個額外的數值，用來調整計算結果，使其更接近真實值。
>Without this bias, an extra bit would be required to accurately represent the variable 'm', which would exceed the capacity of a 64-bit variable. To manage this, the solution involves setting 'm' equal to 'p' divided by 'b', and 'n' divided by 'b' as equal to (n * m + m) / p. This approach is taken because avoiding the bias is not feasible due to the limitations imposed by bit truncation errors and the 64-bit variable size constraint.
如果沒有引入偏差，我們需要額外的位元來表示計算過程中的變數 `m`。
解決方案：將變數 `m` 設定為 $\dfrac{p}{b}$，這樣可以確保 `m` 的值在 64 位元變數的範圍內。同時，我們將變數 $\dfrac{n}{b}$ 設為 $\dfrac{(n * m + m)}{p}$，這樣的設置能夠在計算過程中保持結果的準確性。
$\dfrac{(n * m + m)}{p}$ = m $\times$ $\dfrac{(n + 1)}{p}$ = $\dfrac{p}{b}$ $\times$ $\dfrac{(n + 1)}{p}$ = $\dfrac{n + 1}{b}$
Question: 目前不理解為什麼在變數 `m` 、 `p` 、 `b` 沒有改變的情況下，這裡需要再計算一次變數 `m` ？ 使`m = (p << 64) / b` 。
原本計算過一次 `(m = ((p << 64) + b - 1) / b)`，差異是 `(b - 1)`。
原本：
```c
___m = (~0ULL / ___b) * ___p;
___m += (((~0ULL % ___b + 1) * ___p) + ___b - 1) / ___b;
```
現在：
```c
___bias = true;
___m = (~0ULL / ___b) * ___p;
___m += ((~0ULL % ___b + 1) * ___p) / ___b;
```
Answer: 重新計算 `___m` 的必要性在於如果 `___res` 和 `___x / ___b` 不相等，說明前面的近似計算存在較大的誤差，必須重新計算 `___m` 以提高精度。
:::danger
上方答覆過於武斷，要用數學分析！
>TODO：帶入數值分析
:::
#### 清理並提高當前實現的效率 - 一般情況的處理
在一般情況下，減少 `m` 和 `p` ，並嘗試清除 `m` 的第 31 位，否則需要額外的溢出處理。
`___m & -___m` 會得到 `___m` 中最低位的 1。對此值取負數，會將這個最低位的 1 變為最高位的 1，其他位為 0。例如，如果 `___m = 0000 1000`，則 `___m & -___m = 0000 0000 0000 1000`，取負後為 `1111 1111 1110 0000`。
```c
___bits = -(___m & -___m)
```
透過將 `___m` 右移32位，得到 `___m` 的高 32 位，再與 `___bits` 進行 or，將高 32 位加入到 `___bits`。
```c
___bits |= ___m >> 32
```
透過取反操作，得到的結果是 `___bits` 中所有 0 變 1，1 變 0，這使得高位為 0 而低位為 1。左移一位將最低位變為最高位，表示可以應用的最佳減少量。
```c
___bits = (~___bits) << 1
```
`~___bits`：對 `___bits` 取反。例如，對於 `1111 1111 1110 0000`，這會產生` 0000 0000 0001 1111`。
`<< 1`：將結果左移一位。例如，對於 `0000 0000 0001 1111`，這會產生 `0000 0000 0011 1110`。
**最佳減少量**
* 將 `~___bits` 左移一位後，我們得到了一個包含 1 的數字，這些 1 位表示我們可以安全地減少的位數。
* 這樣的設置確保我們找到一個最佳減少量，而不會溢出或錯誤。
**目的**
* 計算出一個最佳的減少量來減少 `___m` 和 `___p`，從而避免溢出並提高計算效率。
* 當 `___bits` 為 0 時，我們無法避免設置第 31 位，在這種情況下，我們應用最大可能的減少量。
* 如果 `___bits` 為 0
`___m` 的第 31 位為 1。在這種情況下，直接將 `___m` 和 `___p` 除以 `___m` 中最低有效位的 1，以最大可能地減少 `___m` 和 `___p`。
* 如果 `___bits` 不為 0
根據 `___bits` 的 MSB，決定應用多少位的減少量。使用 `ilog2(___bits)` 計算 `___bits` 中最高有效位的位數。
```c
if (!___bits) {
___p /= (___m & -___m);
___m /= (___m & -___m);
} else {
___p >>= ilog2(___bits);
___m >>= ilog2(___bits);
}
/* No bias needed. */
___bias = false;
```
#### 兩個條件的組合
>Now we have a combination of 2 conditions:
Condition 1 : whether or not we need to apply a bias.
Condition 2 : whether or not there might be an overflow in the cross product determined by `(___m & ((1 << 63) | (1 << 31)))`.
Select the best way to do `(m_bias + m * n) / (1 << 64)`.
From now on there will be actual runtime code generated.
* 條件 1：是否需要偏差
* `__xprod_64` 函式中判斷是否需要偏差來抵消因位元截斷造成的誤差。
* 條件 2：交叉乘積是否會發生溢位
* 透過呼叫 `__xprod_64` 函式檢查 `(___m & ((1 << 63) | (1 << 31)))` 來確定是否會發生溢位。
* `1 << 63` 和 `1 << 31` 分別是第 63 位和第 31 位。
* 如果 `___m` 的第 63 位和第 31 位被設置，可能會導致乘法運算中的溢位問題。
根據這兩個條件，選擇最佳的計算方法來進行 `(m_bias + m * n) / (1 << 64)` 的運算。這裡 `m_bias` 是偏差，`m` 是乘數，`n` 是被除數的一部分。
`__xprod_64` 會根據是否應用偏差來決定如何進行運算，以避免溢位並保證結果的準確性。
`___p` 為 2 的冪，用於將結果進一步調整到正確的範圍內。
```c
___res = __xprod_64(___m, ___n, ___bias);
___res /= ___p;
```
```c
#define __div64_const32(n, ___b) \
({ \
uint64_t ___res, ___x, ___t, ___m, ___n = (n); \
bool ___bias; \
\
/* determine MSB of b */ \
uint32_t ___p = 1 << ilog2(___b); \
\
/* compute m = ((p << 64) + b - 1) / b */ \
___m = (~0ULL / ___b) * ___p; \
___m += (((~0ULL % ___b + 1) * ___p) + ___b - 1) / ___b; \
\
/* one less than the dividend with highest result */ \
___x = ~0ULL / ___b * ___b - 1; \
\
/* test our ___m with res = m * x / (p << 64) */ \
___res = ((___m & 0xffffffff) * (___x & 0xffffffff)) >> 32; \
___t = ___res += (___m & 0xffffffff) * (___x >> 32); \
___res += (___x & 0xffffffff) * (___m >> 32); \
___t = (___res < ___t) ? (1ULL << 32) : 0; \
___res = (___res >> 32) + ___t; \
___res += (___m >> 32) * (___x >> 32); \
___res /= ___p; \
\
if (~0ULL % (___b / (___b & -___b)) == 0) { \
/* special case, can be simplified to ... */ \
___n /= (___b & -___b); \
___m = ~0ULL / (___b / (___b & -___b)); \
___p = 1; \
___bias = true; \
} else if (___res != ___x / ___b) { \
___bias = true; \
/* Compute m = (p << 64) / b */ \
___m = (~0ULL / ___b) * ___p; \
___m += ((~0ULL % ___b + 1) * ___p) / ___b; \ //AAAA
} else { \
uint32_t ___bits = -(___m & -___m); \
___bits |= ___m >> 32; \
___bits = (~___bits) << 1; \
if (!___bits) { \
___p /= (___m & -___m); \
___m /= (___m & -___m); \
} else { \
___p >>= ilog2(___bits); \ //BBBB
___m >>= ilog2(___bits); \ //CCCC
} \
/* No bias needed. */ \
___bias = false; \
} \
\
___res = __xprod_64(___m, ___n, ___bias); \
\
___res /= ___p; \
})
```
6. `__xprod_64` 計算乘積
計算一個 128 位元的乘積，並縮放到 64 位元，考慮是否需要偏差來處理乘法運算中的溢位問題。
#### 計算乘積的低位
`retval = ((bias ? m : 0) + m * n) >> 64` 根據是否應用偏差進行條件判斷：
Case 1：不需要偏差。
Case 2：需要偏差，不會發生溢位。
Case 3：需要偏差，可能會發生溢位。
```c
if (!bias) {
res = ((uint64_t) m_lo * n_lo) >> 32;
} else if (!(m & ((1ULL << 63) | (1ULL << 31)))) {
/* it is impossible for an overflow to occur in this case */
res = (m + (uint64_t) m_lo * n_lo) >> 32;
} else {
res = m + (uint64_t) m_lo * n_lo;
res_lo = res >> 32;
res_hi = (res_lo < m_hi);
res = res_lo | ((uint64_t) res_hi << 32);
}
```
#### 計算乘積的高位部分
計算 `m_lo * n_hi` 和 `m_hi * n_lo`，並將結果右移 32 位。
Case 1：不會發生溢位。
Case 2：可能會發生溢位。
加上 `m_hi * n_hi` 的乘積，最終結果存儲在 `res` 中並返回。
```c
if (!(m & ((1ULL << 63) | (1ULL << 31)))) {
res += (uint64_t) m_lo * n_hi;
res += (uint64_t) m_hi * n_lo;
res >>= 32;
} else {
res += (uint64_t) m_lo * n_hi;
uint32_t tmp = res >> 32;
res += (uint64_t) m_hi * n_lo;
res_lo = res >> 32;
res_hi = (res_lo < tmp);
res = res_lo | ((uint64_t) res_hi << 32);
}
res += (uint64_t) m_hi * n_hi;
```
7. 除法運算
進行 64 位元數字除以 32 位元整數的除法運算，返回餘數。
透過初步減少高位元和減法迭代操作，避免使用硬體除法指令，非常適合在**不支持硬體除法**的情況下使用。
```c
static inline uint32_t __div64_32(uint64_t *n, uint32_t base)
{
uint64_t rem = *n;
uint64_t b = base;
uint64_t res, d = 1;
uint32_t high = rem >> 32;
/* Reduce the thing a bit first */
res = 0;
if (high >= base) {
high /= base;
res = (uint64_t) high << 32;
rem -= (uint64_t) (high * base) << 32;
}
while ((int64_t) b > 0 && b < rem) {
b = b + b;
d = d + d;
}
do {
if (rem >= b) {
rem -= b;
res += d;
}
b >>= 1;
d >>= 1;
} while (d);
*n = res;
return rem;
}
```
8. 64 位元除法
進行 64 位元數字除法，根據除數是否為 2 的冪、是否為常數等情況選擇不同的計算方法，分成以下四個 case，並返回餘數 `__rem`。
把除數是否為常數拿出來討論的原因是，如果除數不是常數，編譯器在編譯時無法進行優化，因此必須在運行時執行更通用的除法操作。
case 1：如果 `__base` 是常數且是 2 的冪。
case 2：如果 `__base` 是常數且不為 0。
case 3：`__base` 不是編譯時常數，並且 `n` 小於 2^32^。
case 4：`__base` 不是編譯時常數，並且 `n` 大於 2^32^ 。
:::info
補充：`__builtin_constant_p(__base)` 會是 false 的情況
1. 變數是一個在運行時返回值的函數
```c
uint32_t base = get_base_value(); // Assume get_base_value() is a function that returns a value at runtime
uint64_t n = 5;
uint32_t rem = div64(n, base);
```
2. 變數是透過參數傳遞
```c
void my_function(uint32_t base) {
uint64_t n = 5;
uint32_t rem = div64(n, base);
}
```
3. 變數是透過變數賦予
```c
uint32_t base;
scanf("%u", &base); // Get value from standard input
uint64_t n = 5;
uint32_t rem = div64(n, base);
```
:::
```c
#define div64(n, base) \
({ \
uint32_t __base = (base); \
uint32_t __rem; \
if (__builtin_constant_p(__base) && is_power_of_2(__base)) { \
__rem = (n) & (__base - 1); \
(n) >>= ilog2(__base); \ //DDDD
} else if (__builtin_constant_p(__base) && __base != 0) { \
uint32_t __res_lo, __n_lo = (n); \
(n) = __div64_const32(n, __base); \
/* the remainder can be computed with 32-bit regs */ \
__res_lo = (n); \
__rem = __n_lo - __res_lo * __base; \
} else if (likely(((n) >> 32) == 0)) { \
__rem = (uint32_t) (n) % __base; \
(n) = (uint32_t) (n) / __base; \
} else { \
__rem = __div64_32(&(n), __base); \
} \
__rem; \
})
```
9. 使用 div64 對 `res` 進行除法運算，並輸出商數。
如果想得到餘數，則使用一變數接住巨集回傳的值，即 `uint64_t r = div64(res, 3);` ，則 `r` 為餘數。
**`argc` 的值**
`argc` 是命令行參數的數量。當執行程式時，命令行的每一個參數都會被計算在內，包括程式的名稱。
例如，如果在命令行中輸入 `./program arg1 arg2`，則 `argc` 的值為 3（包括程式名和兩個參數）。因此，`argc` 的值取決於**如何執行程式**，它不是每次都固定的。
如果以 `./program `執行程式（即沒有額外的參數），`argc` 是 1。
```c
int main(int argc, char *argv[])
{
uint64_t res;
res = argc + 5;
div64(res, 3);
printf("%lu\n", res);
}
```
### 在 Linux 核心原始程式碼找到相關的程式碼並設計實驗 (使用 Linux 核心模組) 探討程式碼的效益和限制
Linux 核心原始程式碼：[include/asm-generic/div64.h](https://github.com/torvalds/linux/blob/master/include/asm-generic/div64.h)
#### 實驗目的
探討 `do_div()` 巨集在不同除數情境下的表現。
:::danger
搭配閱讀: https://hackmd.io/@sysprog/linux-intdiv
:::
#### 實驗步驟
步驟1：撰寫測試模組
撰寫一個 Linux 核心模組，實現以下功能：
* 設計多個除法測試情境，包括常數除數和非常數除數。
* 已知 `BITS_PER_LONG == 32`，可以分成以下四個情境討論。
* 記錄每個測試情境下 `do_div()` 的執行時間和結果。
<!-- :::danger
注意書寫規範：
* 使用 lab0 規範的程式碼書寫風格，務必用 clang-format 確認一致
>已使用 clang-format 確認書寫風格一致
::: -->
>**使用 clang-format 確認書寫風格一致**
>在這次作業內新增一個檔名為 .clang-format 的文件，複製 lab0 檔案中的 .clang-format 文件內容並貼上。使用指令 `clang-format -i *.[ch]` 即可調整作業程式要求的風格。
```c
#include <asm-generic/div64.h>
#include <linux/delay.h>
#include <linux/init.h>
#include <linux/kernel.h>
#include <linux/module.h>
#include <linux/timekeeping.h>
#include <linux/types.h>
MODULE_LICENSE("GPL");
MODULE_AUTHOR("Yi-Han Wan");
MODULE_DESCRIPTION("A test module for do_div macro.");
MODULE_VERSION("0.1");
static uint64_t test_division(uint64_t n, uint32_t base)
{
uint64_t start, end;
uint32_t remainder;
start = ktime_get_ns();
remainder = do_div(n, base);
end = ktime_get_ns();
printk(KERN_INFO
"n: %llu, base: %u, remainder: %u, quotient: %llu, time: %llu ns\n",
n, base, remainder, n, end - start);
return end - start;
}
static int __init div_test_init(void)
{
printk(KERN_INFO "Loading do_div test module...\n");
// Test scenario 1: __base is a constant and power of 2
test_division(123456789012345ULL, 8);
// Test scenario 2: __base is a constant and not power of 2
test_division(123456789012345ULL, 12345);
// Test scenario 3: n's high 32 bits are 0 and __base is not a constant
uint32_t dynamic_base = jiffies % 100 + 1;
test_division(12345ULL, dynamic_base);
// Test scenario 4: General case where n's high 32 bits are non-zero and
dynamic_base = jiffies % 10000 + 1;
test_division(98765432109876ULL, dynamic_base);
return 0;
}
static void __exit div_test_exit(void)
{
printk(KERN_INFO "Unloading do_div test module...\n");
}
module_init(div_test_init);
module_exit(div_test_exit);
```
<s>
Jiffies 是什麼？
Jiffies 為 Linux 核心變數( 32 位元變數，unsigned long)，它被用來紀錄系統自開機以來，已經過多少的 tick。每發生一次 timer interrupt，Jiffies 變數會被加一。值得注意的是，Jiffies 於系統開機時，並非初始化成零，而是被設為 -300 HZ (arch/i386/kernel/time.c)，即代表系統於開機五分鐘後，jiffies 便會溢位。那溢位怎麼辦？事實上，Linux 核心定義幾個巨集(timer_after, time_after_eq, time_before 與 time_before_eq)，即便是溢位，也能藉由這幾個巨集正確地取得 jiffies 的內容。
</s>
:::danger
參照本學期的課程教材！不要捨近求遠。
為何不看？
:::
步驟2：編譯並載入模組
編寫 Makefile 以編譯模組：
```shell
obj-m += div_test.o
all:
make -C /lib/modules/$(shell uname -r)/build M=$(PWD) modules
clean:
make -C /lib/modules/$(shell uname -r)/build M=$(PWD) clean
```
編譯模組：
```shell
make
```
載入模組：
```shell
sudo insmod div_test.ko
```
查看核心訊息以獲取測試結果：
```shell
sudo dmesg | grep "do_div test"
```
#### 效能評估
* 比較不同情境下 `do_div()` 的執行時間
```
[98608.114361] Loading do_div test module...
[98608.114364] n: 15432098626543, base: 8, remainder: 1, quotient: 15432098626543, time: 18 ns
[98608.114366] n: 10000549940, base: 12345, remainder: 3045, quotient: 10000549940, time: 18 ns
[98608.114367] n: 1234, base: 10, remainder: 5, quotient: 1234, time: 21 ns
[98608.114369] n: 29838499126, base: 3310, remainder: 2816, quotient: 29838499126, time: 33 ns
```
* 分析常數除數和非常數除數對效能的影響
<!-- :::danger
power of 2 是「2 的冪」，參閱: https://hackmd.io/@sysprog/it-vocabulary
>已修正表達方式
::: -->
當除數是常數：對於 2 的冪的除數，編譯器可以使用右移操作來代替除法操作（例如 `n >> 3` 來代替 `n / 8`），這比實際的除法運算要快得多。case 2 中，雖然除數不是 2 的冪，但由於除數是常數，編譯器可以進行一些數學優化，使得除法運算更高效。
當除數不是常數：
無法使用位元運算或乘法反元素等編譯時期優化技術，必須在運行時進行實際的除法運算，導致運行時間較長。當 `n` 的值較大且 `base` 不是常數時，除法運算需要進行完整的 64 位整數除法，這是一個相對複雜且耗時的運算過程，因此運行時間最長。
#### 實驗結果分析
*在不同 case 下的效益和限制*
case 1：常數除數且為 2 的冪
效能：右移運算比標準除法運算快很多，因為位運算在硬體上直接支持且執行速度快。
限制：僅適用於除數為 2 的次方的情況，其他除數不適用。
case 2：常數除數但不是 2 的冪
效能：編譯期可以進行一些優化，例如使用乘法和位移來模擬除法，從而提升運行速度。
限制：僅在除數為常數的情況下有效，變量除數無法應用這種優化。
case 3：除數不是編譯時常數，且被除數小於 2^32^
效能：直接使用 32 位的除法運算，效率相對較高。
限制：僅適用於 `n` 可以用 32 位表示的情況，對於更大的數值無法應用。
case 4：除數不是編譯時常數，且被除數大於 2^32^
效能：需要進行 64 位的除法運算，並且在運行時動態計算，速度較慢。
限制：無法進行編譯時期優化，完全依賴於運行時的計算，效能較低。
### 針對其他學員 (含授課教師和社會人士) 在開發紀錄頁面提出的問題或建議
[Linux 核心專題：位元運算的應用](https://hackmd.io/QGMPoEQZQy2Y2RW-uimBHw?view)
[Linux 核心專題：重作第四次作業](https://hackmd.io/Ofs7wljLQ66Yyi2O7vTm3A?view)
[Linux 核心專題：位元操作的應用](https://hackmd.io/DpLiCIV1Sii9wLeG0hdhEg?view)
[Linux 核心專題：評估位元操作的效益](https://hackmd.io/2IycoloCRiW0WcYNDPUGcg?view)
[Linux 核心專題：workqueue 研究](https://hackmd.io/16KnSCAFRCSH6r7WQ_3XWg?view)
Sign in with Wallet
Connect another wallet