# 2023q1 Homework2 (quiz2)
contributed by < `yanjiew1` >
[作業說明](https://hackmd.io/@sysprog/H143OpNCo)
## 實驗環境
```bash
$ gcc --version
gcc (Ubuntu 11.3.0-1ubuntu1~22.04) 11.3.0
$ lscpu
Architecture: x86_64
CPU op-mode(s): 32-bit, 64-bit
Address sizes: 39 bits physical, 48 bits virtual
Byte Order: Little Endian
CPU(s): 8
On-line CPU(s) list: 0-7
Vendor ID: GenuineIntel
Model name: Intel(R) Core(TM) i5-8250U CPU @ 1.60GHz
CPU family: 6
Model: 142
Thread(s) per core: 2
Core(s) per socket: 4
Socket(s): 1
Stepping: 10
CPU max MHz: 3400.0000
CPU min MHz: 400.0000
BogoMIPS: 3600.00
```
## 測驗 1
### 程式說明
一開始 `x |= x >> 1;` 中在此程式出現 7 次。即這段 64 bits 數值中，每一個 1 向右擴展 7 個 1 。
```
00...01000000000...000
|
v
00...01111111100...000
```
`x |= x >> 8;` ，因為前面的 `x |= x >> 1;` ，至此 `x` 裡的 1 已向右擴展 7 個，故有 8 個連續的 1，透過再跟 `x >> 8` 進行 or 運算，會把這些連續的 1 ，再向右擴展 8 個 1。 `AAAA` 填入 `8`
`x |= x >> 16;` 會把 16 個連續的 1 再向右擴展 16 個，會讓 `x` 變成有至少 32 個連續的 1 。
`x |= x >> 32;` 會把 32 個連續的 1 再向右擴展至 64 個，會讓 `x` 變成有至少 64 個連續的 1 。 `BBBB` 填入 `32` 。
最後會讓 `x` 中最高位的 `1` 擴展至最低位，變成 `00...01111111111...111` 。
因為這個函式的目的是要找下一個 2 的冪 。只要再加上 1 ，即會讓這些 1 進位，變成下一個 2 的冪。故最後 `return x + 1;`。 `CCCC` 填入 `x + 1`
另外這個函式其實不完全正確。題目說「考慮 next_pow2 可針對給定無號 64 位元數值 x，找出最接近且**大於等於** 2 的冪的值」，故應該要在函式的開頭加入 `x--;` ，先把 `x` 減去 1 ，這樣才能讓原本就是 2 的冪的數值維持一致。
另外此作法，可簡化為：
```c
uint64_t next_pow2(uint64_t x)
{
x--;
x |= x >> 1;
x |= x >> 2;
x |= x >> 4;
x |= x >> 8;
x |= x >> 16;
x |= x >> 32;
return x + 1;
}
```
### 用 `__builtin_clzll` 改寫
特別注意的是 `__builtin_clzll` 傳入的值若為 `0` ，則為未定義行為，會產生不可預期的結果。故一開始的 `if` 條件判斷式即排除此狀況。
```c
uint64_t next_pow2(uint64_t x)
{
if (x <= 1)
return 1;
return 1 << (64 - __builtin_clzll(x - 1));
}
```
用 Compiler Explorer 來實驗，[連結在此](https://godbolt.org/z/bWGnvPvEh) ，的確有出現 `bsrq` 指令。
```
next_pow2:
movl $1, %eax
cmpq $1, %rdi
jbe .L1
subq $1, %rdi
movl $64, %ecx
bsrq %rdi, %rdi
xorq $63, %rdi
subl %edi, %ecx
sall %cl, %eax
cltq
.L1:
ret
```
### Linux 核心範例
Linux 有關 2 的冪相關的程式在這裡 [linux/include/linux/log2.h](https://github.com/torvalds/linux/blob/master/include/linux/log2.h) 。最接近上述的是 `__roundup_pow_of_two` 這個函式。但跟測驗的 `next_pow2` 不太一樣是，測驗是找「下一個 2 的冪」，也就是 4 的下一個 2 的冪會是 8 ，但 Linux kernel 裡的 `__roundup_pow_of_two` 是直接取大於等於輸入值且最接近輸入值的 2 的冪。
在 [elixir.bootlin.com](https://elixir.bootlin.com/) 這個網站裡搜尋使用到 [`__roundup_pow_of_two`](https://elixir.bootlin.com/linux/latest/A/ident/__roundup_pow_of_two) 的程式碼發現在許多的裝置驅動程式內用到。
```
Defined in 2 files as a function:
include/linux/log2.h, line 55 (as a function)
tools/include/linux/log2.h, line 47 (as a function)
Referenced in 16 files:
drivers/clk/clk-divider.c
line 226
line 244
line 282
drivers/clk/sunxi/clk-sunxi.c, line 314
drivers/clk/zynqmp/divider.c, line 59
drivers/infiniband/hw/hfi1/chip.c
line 14321
line 14324
drivers/infiniband/hw/hfi1/init.c, line 433
drivers/iommu/intel/dmar.c, line 1544
drivers/iommu/intel/iommu.c, line 1505
drivers/iommu/intel/irq_remapping.c, line 118
drivers/iommu/intel/svm.c, line 201
drivers/net/ipa/gsi_trans.c, line 150
drivers/pci/msi/msi.c, line 303
include/linux/log2.h, line 180
net/mac80211/cfg.c, line 1155
net/sunrpc/xprtrdma/verbs.c, line 857
tools/include/linux/log2.h, line 157
tools/perf/builtin-sched.c
line 1904
line 2290
```
## 測驗 2
### 程式說明
在這個 `for` 迴圈中，要串接由 1 到 n 的二進位數值至 `ans` 。其中 `len` 為目前 `i` 二進位數值所需要的位元數量。
```c
for (int i = 1; i <= n; i++) {
/* removing the rightmost set bit
* e.g. 100100 -> 100000
* 000001 -> 000000
* 000000 -> 000000
* after removal, if it is 0, then it means it is power of 2
* as all power of 2 only contains 1 set bit
* if it is power of 2, we increase the bit length
*/
if (!(DDDD))
len++;
ans = (i | (EEEE)) % M;
}
```
其中，每次 `i` 進位時，即 `i` 為 2 的冪時，長度會多一個位元 ，故可用 `i & (i - 1)` 來判斷是否為 2 冪。
- 若 `i` 為 2 的冪，`i` 只會有一個位元是 1 ，而 `i - 1` 會讓這個位元變為 0 ，在這個位元的右邊變成全為 1 ，此時 `i & (i - 1)` 為 0
- 若 `i` 不為 2 的冪，則 `i` 會有多個 bit 是 1 ，那麼 `i - 1` 只會讓最右邊是 1 的位元變為 0 ，並讓此位元的右邊其他的位元變為 1 ， `i & (i - 1)` 就會讓 `i` 最右邊是 1 的位元變成 0 。
`ans = (i | (EEEE)) % M;` ，會把現有的 `ans` 先左移 `len` 個位元空出空間後，再把 `i` 串加上去。故可用 `ans << len` 來進行左移。
`ans` 雖然是模 M 後的結果，但仍不影響操作。因為 `<< len` 實際上是乘上 $2^{\text{len}}$ ，而 `|` 雖然為 or 運算，但因為 `ans` 左移後空下來的位置位元是 0 ，故在這裡其作用是加法。而對 `ans` 先乘加後再取餘數與先對 `ans` 取餘數再乘加，結果是一樣的。
### 使用 `__builtin_clz` 改寫
可以直接使用 `32 - __builtin_clz(n)` 來算出 `i` 需要幾個位元。
```c
int concatenatedBinary(int n)
{
const int M = 1e9 + 7;
/* use long here as it potentially could overflow for int */
long ans = 0;
for (int i = 1; i <= n; i++) {
int len = 32 - __builtin_clz(i);
ans = (i | (ans << len)) % M;
}
return ans;
}
```
目前還沒想到怎麼改進 `% (1e9 + 7)` ，但應該可以透過減去某二個數字相乘來達到同樣的效果
## 測驗 3
此題介紹了 SWAR 軟體最佳化的技巧，以及它如何運用在計算 UTF-8 字串中，字的數目。詳細 bitwise 的操作可以看 [quiz2 題目說明](https://hackmd.io/@sysprog/linux2023-quiz2)
此題 `swar_count_utf8` 函式，在 `for` 迴圈內，每次讀進 8 個位元組。透過 bitwise 操作，讓整個 64bit 的無號整數，值為 1 的位元數量等同於此 8 個位元組中，屬於 UTF-8 中後續位元組 (continuation byte(s)) 的數量。
```c
size_t count = 0;
for (; qword != end; qword++) {
const uint64_t t0 = *qword;
const uint64_t t1 = ~t0;
const uint64_t t2 = t1 & 0x04040404040404040llu;
const uint64_t t3 = t2 + t2;
const uint64_t t4 = t0 & t3;
count += __builtin_popcountll(t4);
}
```
故迴圈執行完畢後， `count` 會存放字串中， `(len & ~7)` 後續位元組 (continuation byte(s)) 的數量。
接下來就是直接把 `(len & ~7)` 減去 `count` ，則得到了前 `(len & ~7)` 中， UTF-8 中字元的個數。故這裡 `AAAA` 可填入 `3` 。
```c
count = (1 << AAAA) * (len / 8) - count;
```
再來要處理最後的 `(len & 7)` 個位元組。最後一行判斷 `(len & 7)` 是否還有位元組未處理，若還有則呼叫 `count_utf8` 來處理。故這裡 `BBBB` 和 `CCCC` 可填入 7
```c
count += (len & BBBB) ? count_utf8((const char *) end, len & CCCC) : DDDD;
```
### 效能比較
[測試程式](https://github.com/yanjiew1/linux23q1-quiz2/blob/main/utf-8.c)
我把二種實作放進我的測試程式中，用下列命令來編譯
```bash
$ gcc -O2 utf-8.c
```
測得結果為：
| 實作 | 花費時間 (cycles) |
|:--------------- | -----------------:|
| count_utf8 | 54378.65 |
| swar_count_utf8 | 30444.72 |
`swar_count_utf8` 可得到較高的效能。
若用 `gcc -O3 utf-8.c` 來編譯，則 `count_utf8` 會比較快。[此為](https://godbolt.org/z/3KMj5j7b6)編譯後的組合語言 `count_utf8` ，用到很多 SIMD 指令且 `swar_count_utf8` 沒有利用 SIMD 指令(可能太複雜讓 GCC 不好進行最佳化)，這或許就是 `count_utf8` 比較快的關鍵。
### Linux 核心的 UTF-8 和 Unicode
簡單搜尋了 Linux UTF-8 的實作，有以下位置
- [`fs/nls/nls_base.c`](https://github.com/torvalds/linux/blob/master/fs/nls/nls_base.c)
- [`fs/nls/nls_utf8.c`](https://github.com/torvalds/linux/blob/master/fs/nls/nls_utf8.c)
- [`fs/unicode`](https://github.com/torvalds/linux/tree/master/fs/unicode)
不過沒有看到核心有用到計算 UTF-8 中 Unicode 字元數量的部份。比較接近的是在 [`fs/unicode/utf8-norm.c`](https://github.com/torvalds/linux/blob/master/fs/unicode/utf8-norm.c) 中的 `utf8nlen` ，但功能仍然不同 。
## 測驗 4
觀察題目 pattern ，可以知道原始程式功能是判斷 16 bits 無號整數，其位元的組成是否符合正規表示式 `1+0*` 。
先觀察 `-x ^ x` 的特性。 `-x` 是取 2 的補數，即 `~x + 1` 。 當我們對一個數字取 2 的補數時，可以觀察到，此動作會把原本數字最右邊為 1 的位元其左邊所有位元反轉，例如：
```
1011001100
=> 0100110100
```
又從 xor 真值表可知，若二位元相異，則其值為 1 反之為 0 。故 `-x ^ x` 中， 輸出值中， `x` 最右邊為 1 的位元其所有左邊位元會是 1 ，其餘為 0 ，即：
```
1011001100
=> 1111111000
```
接下來考慮二個 case ：
- 當 `x` 符合正規表示式 `1+0*` 時， `-x ^ x` 會恰好讓開頭 1 的位元數少一個，即 `11110000 => 11100000` ，即 `-x ^ x < x` 。
- 當 `x` 不符合 `1+0*` 時，雖然輸出值中，對應回 `x` 中最右邊為 1 的位元所在位置變成 0 ，但是最右邊 1 的所有左邊位元都變成 1 ，例 `1010100 => 1111000` 故 `-x ^ x > x` 。
回到此題，跟據上面的觀察，我們可以填入 EEEE = `-x` ， FFFF = `x` 。
```c
bool is_pattern(uint16_t x)
{
const uint16_t n = EEEE;
return (n ^ x) < FFFF;
}
```
### Linux 核心的應用
Sign in with Wallet
Connect another wallet