---
tags: linux2023
---
# 2023q1 Homework2 (quiz2)
contributed by < [chiangkd](https://github.com/chiangkd) >
## 開發環境
```shell
$ gcc --version
gcc (Ubuntu 11.3.0-1ubuntu1~22.04) 11.3.0
Copyright (C) 2021 Free Software Foundation, Inc.
This is free software; see the source for copying conditions. There is NO
warranty; not even for MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.
$ 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) i7-7700HQ CPU @ 2.80GHz
CPU family: 6
Model: 158
Thread(s) per core: 2
Core(s) per socket: 4
Socket(s): 1
Stepping: 9
CPU max MHz: 3800.0000
CPU min MHz: 800.0000
BogoMIPS: 5599.85
```
## 測驗一
**延伸問題**
- [x] 解釋程式碼原理，並用 [`__builtin_clzl`](https://gcc.gnu.org/onlinedocs/gcc/Other-Builtins.html) 改寫
>`int __builtin_clz (unsigned int x)`
>Returns the number of leading 0-bits in x, starting at the most significant bit position. If x is 0, the result is undefined.
>`int __builtin_clzl (unsigned long)`
>Similar to __builtin_clz, except the argument type is unsigned long.
- [ ] 在 Linux 核心原始程式碼找出類似的使用案例並解釋
- [x] 當上述 clz 內建函式已運用時，編譯器能否產生對應的 x86 指令？
>提示: 可執行 `cc -O2 -std=c99 -S next_pow2.c` 並觀察產生的 next_pow2.s 檔案，確認 `bsrq` 指令 (表示 “[Bit Scan Reverse](https://c9x.me/x86/html/file_module_x86_id_20.html)”)
在原程式的實作方式中，透過 binary search 的方式，與輸入值做比較，直到找到符合輸入值的 2 的冪
```c
#include <stdint.h>
static inline uint64_t pow2(uint8_t e) { return ((uint64_t)1) << e; }
uint64_t next_pow2_m1(uint64_t x)
{
uint8_t lo = 0, hi = 63;
while (lo < hi) {
uint8_t test = (lo + hi)/2;
if (x < pow2(test)) { hi = test; }
else if (pow2(test) < x) { lo = test+1; }
else { return pow2(test); }
}
return pow2(lo);
}
```
以輸入 `x = 7` 舉例，`lo` 和 `hi` 會經過以下迭代
| lo | hi | test |
| --- | --- | ---- |
| 0 | 63 | 31 |
| 0 | 31 | 15 |
| 0 | 15 | 7 |
| 0 | 7 | 3 |
| 0 | 3 | 1 |
| 2 | 3 | 2 |
然後觸發 `else if` 條件
```c
else if (pow2(test) < x) { lo = test+1; }
```
並回傳 `pow2(lo) = 8`，上述程式碼具有分支，以下是沒有分支的版本
```c
uint64_t next_pow2_m2(uint64_t x)
{
x |= x >> 1;
x |= x >> 1;
x |= x >> 1;
x |= x >> 1;
x |= x >> 1;
x |= x >> 1;
x |= x >> 1;
x |= x >> 8;
x |= x >> 16;
x |= x >> 32;
return x + 1;
}
```
考慮到題目敘述給定 64 位元數值，故上述程式碼必須將 將最高位是 1 的後面都填充為 1 ，在前 7 個 `x |= x >> 1` 操作中已將包含最高位的頭 8 個 bit 填補為 1，考慮函數功能， `AAAA` 為 `8`， `BBBB` 為 `32` 即可填補完成。
但上述沒有分支的實作中在遇到 2 的冪次方輸入時，會產生錯誤，假設輸入 `8(0b1000)`，經過上述運算過後將會回傳 `15(0b1111)+1 = 16`，而預期輸出為 `8`，故我對程式碼稍做修改，新增一個 logical and (`&&`) 判斷輸入是否為 `0` 並對修正 2 的冪次方輸入所造成的問題。
```c
uint64_t next_pow2_m2(uint64_t x)
{
x -= x && 1; /* if x != 0, x = x-1, for 2^k,it will borrow 1 bit from the top */
x |= x >> 1;
x |= x >> 1;
x |= x >> 1;
x |= x >> 1;
x |= x >> 1;
x |= x >> 1;
x |= x >> 1;
x |= x >> 8;
x |= x >> 16;
x |= x >> 32;
return x + 1;
}
```
### 用 `builtin_clzl` 改寫
[`__builtin_clzl`](https://gcc.gnu.org/onlinedocs/gcc/Other-Builtins.html) 回傳有幾個 leading 0，當輸入為 0 時，輸出 undefined。
有幾個 leading 0 代表有值第一個 1 出現在 `64 - __builting_clzl(x)`，也就是說最接近的大於等於 2 的冪的值為 `1 << (64 - __builting_clzl(x))`
將上述的 branch less 用此函式可改寫為
```c
uint64_t next_pow2_m3(uint64_t x)
{
x -= x && 1;
return 1 << (64 - __builtin_clzl(x));
}
```
同樣的考慮到上述提到的輸入為 2 的冪次方以及輸入為 0 的問題，不過當前版本在輸入 `x` 為 0 或 1 時會造成 `__builtin_clzl(0)` ，為 `undefined` ，且預期輸出應為 `1`，故可將函式改寫為
```c
uint64_t next_pow2_m3(uint64_t x)
{
x -= x && 1;
return x ? 1 << (64 - __builtin_clzl(x)) : 1;
}
```
### 編譯器能否產生對應的 x86 指令
```shell
gcc -O2 -std=c99 -S next_pow2.c
```
函式名稱為 `next_pow2_m3`，產生的對應 `x86` 指令
```shell
next_pow2_m3:
.LFB16:
.cfi_startproc
endbr64
cmpq $1, %rdi
movl $1, %eax
adcq $-1, %rdi
testq %rdi, %rdi
je .L10
bsrq %rdi, %rdi
movl $64, %ecx
xorq $63, %rdi
subl %edi, %ecx
sall %cl, %eax
cltq
.L10:
ret
.cfi_endproc
```
有產生對應的 `bsr` 指令，其中後綴可以為 `b`、`w`、`l`、`q` 分別代表 8 位，16 位，32 位，64 位。因本函式處理 `uint64_t` ，所以會看到大量的 `q` 後綴
## 在 Linux 核心原始程式碼找出類似的使用案例並解釋
>TODO
---
## 測驗二
**延伸問題**
- [x] 解釋程式碼運作原理
- [ ] 嘗試使用 [`__builtin_{clz,ctz,ffs}`](https://gcc.gnu.org/onlinedocs/gcc/Other-Builtins.html) 改寫，並改進 $10^9+7$ 的運算
```c
int concatenatedBinary(int n){
const int M = 1e9 + 7;
int len = 0; /* bit length to be shift */
long ans = 0;
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(!(i & (i - 1)))
len++;
ans = (i | (ans << len)) % M;
}
return ans;
}
```
首先考慮題目要求回傳輸入 1 ~ n 轉換程 binary 表示後的串接，先用 `n=4` 推演看看
```shell
value binary
n = 1 -> 1
n = 2 -> 10
n = 3 -> 11
n = 4 -> 100
concatenated -> 11011100 = 220
```
接著搭配題目註解分析，將 rightmost 的 set bit 移除後即為 2 的冪次方，且遇到 2 的冪次時，要增加 bit 的長度，對應上述，在遇到 `n=2` 時，二進位值由 `1` 變為 `10` ，也就是在二進制下**進位**，所以這裡才會需要增加 bit 的長度，同理遇到 `n=4` 時也一樣，故 `DDDD` 就必須處理移除 rightmost set bit 這件事情，也就是 `i & (i-1)` ，這裡如果 `i` 為 2 的冪次時，若減一則會向 leftmost set bit 借位，此時取 bitwise and 若為 0 ，代表 set bit 僅有 leftmost set bit 一位，即代表 `i` 屬於 2 的冪次，需增加 `bit` 長度。
接著 `EEEE` 為將二進位資料串接的過程，故 `EEEE` 為 `ans << len`，用同樣的例子推演一次
```shell
value binary
n = 1 -> 1
n = 2 -> 10
n = 3 -> 11
n = 4 -> 100
/* iteration */
ans = 0b00000000 (len = 1)
ans = 0b00000001 (len = 1)
ans = 0b00000110 (len = 2)
ans = 0b00011011 (len = 2)
ans = 0b11011100 (len = 3)
```
### 嘗試使用 `__builtin_{clz,ctz,ffs}` 改寫並改進 $10^{9}+7$ 運算
- `__builtin_clz`: 回傳 leading 0 的數量
- `__builtin_ctz`: 回傳 trailing 0 的數量
- `__builtin_ffs`: 回傳從右邊數起第一個 1 的位置
在原方法中的 `len` 是根據是否有進位來判斷 left shift 的長度為多少，在這裡可以直接用 `32 - __builtin_clz(i)` 來判斷 left shift 長度，可改寫如下
```c
int concatenatedBinary_m2(int n){
long ans = 0;
const int M = 1e9 + 7;
for(int i = 1; i <= n; i++)
ans = (i | ans << (32 - __builtin_clz(i))) % M;
return ans;
```
- 一樣可以通過 [leetcode 1680](https://leetcode.com/problems/concatenation-of-consecutive-binary-numbers/submissions/910890142/)
文章 [Modulo 10^9+7 (1000000007)](https://www.geeksforgeeks.org/modulo-1097-1000000007/) 提到為何要進行 mod 運算。
:::warning
TODO:
暫時還沒想到 mod 該怎麼優化，感覺可以從 [modulo](https://en.wikipedia.org/wiki/Modulo) 的等價性 (identities) 下手
:::
---
## 測驗三
**延伸問題**
- [x] 解釋程式碼運作原理，比較 SWAR 和原本的實作效能落差
- [ ] 在 Linux 核心原始程式碼找出 UTF-8 和 Unicode 相關字串處理的程式碼，探討其原理，並指出可能的改進空間
```diff
size_t swar_count_utf8(const char *buf, size_t len)
{
const uint64_t *qword = (const uint64_t *) buf;
- const uint64_t *end = qword + len >> 3;
+ const uint64_t *end = qword + (len >> 3);
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 = (1 << 3) * (len / 8) - count;
count += (len & 7) ? count_utf8((const char *) end, len & 7) : 0;
return count;
}
```
- 編譯時發現錯誤，根據 [Precedence table](https://en.cppreference.com/w/c/language/operator_precedence) ，`+` 的優先權高於 `>>` ，根據函式功能應該要加個括號才合理。
透過 8 bytes 長度的 `qword` 將原先 1 byte 的 `char` 放進去計算，根據編碼規則， UTF-8 對於首位元組最高的兩個位元始終為 `11`，而後續位元組的最高兩個位元設定為 `10`
| ASCII | 0xxx.xxxx |
| ------- | -------------------------------------- |
| 2 bytes | 110x.xxxx 10xx.xxxx |
| 3 bytes | 1110.xxxx 10xx.xxxx 10xx.xxxx |
| 4 bytes | 111.0xxx 10xx.xxxx 10xx.xxxx 10xx.xxxx |
透過[題目](https://hackmd.io/@sysprog/linux2023-quiz2#%E6%B8%AC%E9%A9%97-3)說明的規則將特定 pattern (`not bit6 and bit7`) 提取出來後利用 `__builtin_popcount` 計算有多少 `1` (也就是符合規則的部份)
在 `for` 迴圈中處理超過 $N * 8$ bytes 的部份 (即可以放滿 `uint64_t` 的部份)，後續迴圈外的部份為處理剩下的 7 bytes
在迴圈外的 `(1 << 3) * (len / 8) - count;` 是為了計算出字元的數量，將總字串長度撿到 continuation bytes (符合 pattern 部份) 數量即可拿到 8 bytes 整數倍部份的字元總數。
最後再來處理不為 8 bytes 整數倍的部份，在前一行透過 `len / 8` 取出整數倍部份， 此行則透過 `len & 7` 取出不為整數倍的部份，若不為 `0`， 則直接透過 `count_utf8` 計算並加入結果之中。
### 效能測試
引入 [cpucycles.h](https://github.com/sysprog21/lab0-c/blob/master/dudect/cpucycles.h)
測試 buffer size 為 10000，20000，50000，100000 下的 ticks
- [test code](https://github.com/chiangkd/NCKU-Linux-Kernel-Quiz/commit/f727bf0bac535f78423ac8017946e71686cce532)
| Buffer Size | w/o SWAR | w/ SWAR |
| ----------- | -------- | ------- |
| 10000 | 257978 | 39937 |
| 20000 | 515033 | 76065 |
| 50000 | 1124807 | 169976 |
| 100000 | 2323698 | 361673 |
可以看到有使用 SWAR 的明顯較佳。
---
## 測驗四
**延伸問題**
- [x] 解釋程式碼運作原理
- [ ] 在 Linux 核心原始程式碼找出上述 bitmask 及產生器，探討應用範疇
參見 [Data Structures in the Linux Kernel](https://0xax.gitbooks.io/linux-insides/content/DataStructures/linux-datastructures-3.html)
題目要求要找到的 pattern 為從 MSB 開始有 1 個或以上連續的 `1` ，接著剩餘的位數都是 `0` ，符合條件的 pattern 包含
```shell
pattern: 8000 (32768) 0b1000 0000 0000 0000
pattern: c000 (49152) 0b1100 0000 0000 0000
pattern: e000 (57344) 0b1110 0000 0000 0000
pattern: f000 (61440) 0b1111 0000 0000 0000
pattern: f800 (63488) 0b1111 1000 0000 0000
pattern: fc00 (64512) 0b1111 1100 0000 0000
pattern: fe00 (65024) 0b1111 1110 0000 0000
pattern: ff00 (65280) 0b1111 1111 0000 0000
pattern: ff80 (65408) 0b1111 1111 1000 0000
pattern: ffc0 (65472) 0b1111 1111 1100 0000
pattern: ffe0 (65504) 0b1111 1111 1110 0000
pattern: fff0 (65520) 0b1111 1111 1111 0000
pattern: fff8 (65528) 0b1111 1111 1111 1000
pattern: fffc (65532) 0b1111 1111 1111 1100
pattern: fffe (65534) 0b1111 1111 1111 1110
pattern: ffff (65535) 0b1111 1111 1111 1111
```
```c
#include <stdint.h>
#include <stdbool.h>
bool is_pattern(uint16_t x)
{
if (!x)
return 0;
for (; x > 0; x <<= 1) {
if (!(x & 0x8000))
return false;
}
return true;
}
```
原方法在 `x > 0` 的情況下 (迴圈中)，若檢測到 `x & 0x8000`(MSB) 為 `0` ，則不滿足 pattern，即檢查若符合條件，最高位元為 `0` 的情況只有在大家都為 `0`，即代表 `x=0`
```c
bool is_pattern(uint16_t x)
{
const uint16_t n = EEEE;
return (n ^ x) < FFFF;
}
```
此處回傳值為 `n ^ x < FFFF`，代表判斷是否符合 pattern 是透過比較大小，而符合 pattern 的值正好就是符合 pattern 的相同數量 `1` 中的最大值，考慮到若符合 pattern ，則其二補數為保留最靠近 LSB 的 `1`，其餘為 `0`，若不符合 pattern ，其二補數一樣會保留最靠近 LSB 的 `1` ，但在這個 `1` 的左側 bit 會進行翻轉。
若符合 pattern ，取二補數後在和本身取 `xor` 必小於原本的值，因為最靠近 LSB 的 `1` 被消除了，若不符合 pattern ，則取二補數和本身取 `xor` 必大於原本的值，因為
```shell
x = 11110111
-x = 00001001
-x ^ x = 11111110
--------------------
x = 01101111
-x = 10010001
-x ^ x = 11111110
--------------------
x = 01010101
-x = 10101011
-x ^ x = 11111110
```
最靠近 LSB 的 `1` 的左側會被 `1` 填滿，且 這個 `1` 本身會被 `xor` 成 `0`
- `EEEE` 可為 `-x` or `~x + 1`
- `FFFF` 為 `x`
Sign in with Wallet
Connect another wallet