# 2023q1 Homework2 (quiz2)
contributed by < `fewletter` >
## 測驗一
### 解釋上述程式碼原理，並用 `__builtin_clzl` 改寫
首先先看此程式碼的目的是什麼
* `next_pow2(7) = 8`
* `next_pow2(13) = 16`
* `next_pow2(42) = 64`
由上面可知道此程式碼在給定一個數字後會回傳大於等於此數字 2 的冪的值。 而由下面的程式碼可以看出 `x` 先利用 `>>` 將 1 往右邊移一位 0 ，再利用 `|` 保留前一位的1，目的是讓右邊的 0 全部變成 1 ，最後再加上 1 全部進位後就可以得到剛好大於此數字的 2 的冪的值。
```cpp
uint64_t next_pow2(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);
}
```
舉 `next_pow2(13) = 16` 為例：
* 13 的二進位為 `0...00 1101`
* 進行 `x |= x >> 1` 四次後就可以得到 `0...00 1111`
* 將 `0...00 1111 + 1` 後就可以得到 `0...01 0000` ，最後可以得到十進位數值 16
利用 `__builtin_clzl` 改寫
```diff
uint64_t next_pow2(uint64_t x)
{
- uint64_t left = __builtin_clzl(x);
- return x == 0 ? 1:1 << (64-left);
+ return x == 0 ? 1:1 << (64-__builtin_clzl(x-1));
}
```
* 利用 `__builtin_clzl` 可以找出此數字最高次左邊有多少的 0
* 接著將 1 往左邊位移總位元數剪掉左邊 0 的數量就是剛好大於此數字的 2 的冪的值
* 此方法在 `x = 0` 會產生分支，所以 `x = 0` 的時候直接回傳 1
在測試時發現如果輸入 2 的冪會發生問題，比如說輸入 8， 此程式碼會輸出 16， 原因在於 `__builtin_clzl` 會計算 1 左邊有多少 0 位元，而 `(64-__builtin_clzl(x - 1))` 會讓 2 的冪在二進位中進位，也就會出現此錯誤。
解決辦法就是讓輸入的值減 1，讓每個數值在比較時在二進位會退一位如下表，就不會造成上面那種錯誤。
| x | (x-1)的二進位 | __builtin_clzl(x - 1) |
|:---:|:-------------:|:---------------------:|
| 1 | 0000 | 64 |
| 2 | 0001 | 63 |
| 3 | 0010 | 62 |
| 4 | 0011 | 62 |
| 5 | 0100 | 61 |
| 6 | 0101 | 61 |
| 7 | 0110 | 61 |
| 8 | 0111 | 61 |
### 在 Linux 核心原始程式碼找出類似的使用案例並解釋
參考[位元旋轉實作和 Linux 核心案例](https://hackmd.io/@sysprog/bitwise-rotation)和[ linux/bitops.h ](https://github.com/torvalds/linux/blob/master/include/linux/bitops.h)
位元旋轉相較於移動位元不同的地方是當移動位元到位元數無法表達的地方時，移動位元會直接捨棄數值，但是位元旋轉的數值則會在另一端顯示。
假設下面是一個 4 位元的數字
```graphviz
graph{
node[shape=box];
1 [label="0"]
2 [label="0"]
3 [label="0"]
4 [label="1"]
rankdir=LR
1 -- 2 -- 3 -- 4
}
```
此數字向右位元旋轉 1 個位置，在最右邊的 1 會出現在最左邊
```graphviz
graph{
node[shape=box];
1 [label="1"]
2 [label="0"]
3 [label="0"]
4 [label="0"]
rankdir=LR
1 -- 2 -- 3 -- 4
}
```
Linux 核心有對不同位元做位元旋轉的程式碼，下面舉例的是對 8 位元做位元旋轉的程式碼
```cpp
static inline __u8 rol8(__u8 word, unsigned int shift)
{
return (word << (shift & 7)) | (word >> ((-shift) & 7));
}
static inline __u8 ror8(__u8 word, unsigned int shift)
{
return (word >> (shift & 7)) | (word << ((-shift) & 7));
}
```
首先先從最簡單的兩個運算式解釋 `(shift & 7)` 和 `((-shift) & 7)`，對 7 做 `&` 運算是對 8 取餘數，7 的二進位是 `0111` ，最高位為 0 而不管是 1 還是 0 對 0 做 `&` 運算皆為 0 ，所以這個運算式是將移動的位元數限制在 7 個以內。
:::info
對於任何給定的數字 x，x & 7 的結果都會是小於等於 7 的非負整數，這是因為在二進位下，7 的最低三位都是 1，其它位都是 0。當 x 和 7 做 & 運算時，只有 x 的最低三位會對結果有貢獻，其它位都會被清零。因此，x & 7 的結果就是 x 對 8 取餘數所得到的值。
當我們對一個負數 x 取 & 7 時，(-x) & 7 的結果和 x & 7 的結果是不同的。這是因為在二進位下，負數的表示方式是採用二補數表示法，即將正數的每個位取反再加 1 所得到的值。因此，(-x) 的二進位表示方式是將 x 的每個位取反再加 1。例如，如果 x = 3，則 x 的二進位表示方式為 00000011，(-x) 的二進位表示方式為 11111101。當 (-x) & 7 時，只有 (-x) 的最低三位會對結果有貢獻，其它位都會被清零。因此，(-x) & 7 的結果就是 (-x) 對 8 取餘數所得到的值。
總結一下，(shift & 7) 的結果是 shift 對 8 取餘數所得到的值；((-shift) & 7) 的結果是 shift 的相反數對 8 取餘數所得到的值。這兩個運算式的作用都是將 shift 限制在 0 到 7 之間，可以用來實現循環移位的功能。
> ChatGPT
:::
但是就算我們將移動的位元數限制在 7 個以內，有時還是會超出 8 個位元的限制，比如下面這段程式碼
```cpp
rotr8(4, 7) //0000 0010 向右移動7個位元
```
此時 `word >> (shift & 7)` 會變成 `0000 0000` ， `word << ((-shift) & 7)` 則會變成 `0000 0100` ， 最後再進行 `|` 運算就會得到 `0000 0100` ，就會看到位元旋轉的特性，往右移動 7 個位元等於往左移 1 個位元。
### 當上述 clz 內建函式已運用時，編譯器能否產生對應的 x86 指令？
從 `test1.s` 可以看到有產生 `bsrq` 這項指令。
```
next_pow2:
.LFB14:
.cfi_startproc
endbr64
movl $1, %eax
testq %rdi, %rdi
je .L1
bsrq %rdi, %rdi
movl $64, %ecx
xorq $63, %rdi
subl %edi, %ecx
sall %cl, %eax
cltq
```
---
## 測驗二
### 解釋上述程式碼運作原理
本測驗最重要的是理解下面迴圈的中的程式碼
```cpp
for (int i = 1; i <= n; i++) {
if (!(i & (i - 1)))
len++;
ans = (i | (ans << len)) % M;
}
```
從註解中我們可以理解 `!(i & (i - 1))` 用來檢查一個整數 i 是否為 2 的冪。當一個整數為 2 的冪時，其二進位表示法中只有一位是 1，而其他位都是 0。因此，當我們減去 1 時，這個二進位表示法中原本的那個 1 會變成 0，而低位的所有 0 會變成 1。因此，當我們將原數與減一後的數進行 `&` 運算時，結果應該是 0。
:::danger
power of 2 的翻譯是「2 的冪」，不要提「次」
:notes: jserv
:::
舉例：
> 8 = 0000 1000, 7 = 0000 0111 $\to$ 8 & 7 = 0000 0000
但問題是我們為什麼要檢查整數 i 是否為 2 的冪，我們可以從下面的表格看到，只要此次迭代次數為 2 的冪，佔的位元就會多一個，也就是說需要往左多移一個。
| i | 是否為 2 的冪 | 二進位佔幾個位元 | 二進位 |
|:---:|:---------------:|:----------------:|:----------:|
| 1 | 否 | 1 | 1 |
| 2 | 是 | 2 | 10 |
| 3 | 否 | 2 | 11 |
| 4 | 是 | 3 | 100 |
| 5 | 否 | 3 | 101 |
| 6 | 否 | 3 | 110 |
| 7 | 否 | 3 | 111 |
| 8 | 是 | 4 | 1000 |
這段程式碼的作用只是將上一個迭代的結果 `ans` 往左位移 `len` 位，然後將當前的數字 `i` 接在 `ans` 的右邊。
```cpp
ans = (i | (ans << len)) % M;
```
### 嘗試使用 `__builtin_{clz,ctz,ffs} `改寫，並改進 mod $10^9+7$ 的運算
使用 `__builtin_ffs` 來判斷低位第一個不是 0 的位置，跟原本的方法相像，都是用來檢查整數 i 是否為 2 的冪，只要是 2 的冪， `len` 加一，也就是多佔一個位元。
| i | `__builtin_ffs(i)-1` | len |
| --- |:------------------:|:---:|
| 1 | 0 | 0 |
| 2 | 1 | 1 |
| 3 | 0 | 1 |
| 4 | 2 | 2 |
| 5 | 0 | 2 |
| 6 | 1 | 2 |
| 7 | 0 | 2 |
| 8 | 3 | 3 |
```cpp
for (int i = 1; i <= n; i++) {
if (len == __builtin_ffs(i)-1)
len++;
ans = (i | (ans << len)) % M;
}
```
---
## 測驗三
### 解釋上述程式碼運作原理
要了解此程式碼的目的首先要先了解 UTF-8 和 ASCII 兩者編碼的區別，而 UTF-8 又會因為 byte 的不同而有不同的表示法。
| ASCII | 0xxxxxxx |
|:-------------:|:-----------------------------------:|
| UTF-8 2 bytes | 110xxxxx 10xxxxxx |
| UTF-8 3 bytes | 1110xxxx 10xxxxxx 10xxxxxx |
| UTF-8 4 bytes | 11110xxx 10xxxxxx 10xxxxxx 10xxxxxx |
`swar_count_utf8` 程式碼主要可以分三個部分解釋，第一部分為
```cpp
const uint64_t *qword = (const uint64_t *) buf;
const uint64_t *end = qword + (len >> 3);
```
`len` 為 `buf` 的總 bytes 數，`(len >> 3)` 將整個 `buf` 分成 8 的倍數。
第二部份則是檢查 `qword` 這 8 個 bytes 是否為 UTF-8 的表示式，此程式碼原理是利用 UTF-8 的特性檢查 6 和 7 bit 是否為 10
```cpp
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);
}
```
下面的舉例為使用上述程式碼檢查 2 個 2 bytes 的 UTF-8
```cpp
t0 = [110xxxxx 10xxxxxx 110xxxxx 10xxxxxx
010xxxxx 010xxxxx 010xxxxx 010xxxxx]
```
`t1 = ~t0` ，將 0 和 1 全部轉換
```cpp
t1 = [001xxxxx 01xxxxxx 001xxxxx 01xxxxxx
101xxxxx 101xxxxx 101xxxxx 101xxxxx]
```
`t2 = t1 & 0x4040404040`，檢查 8 bit 中第 6 bit 是不是 1
```cpp
t2 = [001xxxxx 01xxxxxx 001xxxxx 01xxxxxx
101xxxxx 101xxxxx 101xxxxx 101xxxxx] &
[01000000 01000000 01000000 01000000
01000000 01000000 01000000 01000000]
= [000xxxxx 010xxxxx 000xxxxx 010xxxxx
000xxxxx 000xxxxx 000xxxxx 000xxxxx]
```
`t3 = t2 + t2`
```cpp
t3 = [000xxxxx 100xxxxx 000xxxxx 100xxxxx
000xxxxx 000xxxxx 000xxxxx 000xxxxx]
```
`t4 = t0 & t3`，檢查 UTF-8 中的 `continuation byte`
```cpp
t4 = [110xxxxx 10xxxxxx 110xxxxx 10xxxxxx
010xxxxx 010xxxxx 010xxxxx 010xxxxx]&
[000xxxxx 100xxxxx 000xxxxx 100xxxxx
000xxxxx 000xxxxx 000xxxxx 000xxxxx]
= [000xxxxx 10xxxxxx 000xxxxx 10xxxxxx
^^^^^^^^ ^^^^^^^^ => continuation byte
000xxxxx 000xxxxx 000xxxxx 000xxxxx]
```
從 `t4` 中可以觀察到檢查到不是 0 的位元是原本 UTF-8 中的 `continuation byte` 所在的位置，最後再藉由 `__builtin_popcountll(t4)` 將所有 `continuation byte` 的數量剪掉。
第三部份的程式碼則是針對不是 8 的倍數的長度的數值
```cpp
count = (1 << 3) * (len / 8) - count;
count += (len & 7) ? count_utf8((const char *) end, len & 7) : 0;
```
此程式碼最重要的是 `len & 7` 如果長度並非 8 的倍數，那 `len & 7` 就不會等於 0，然後就需要再多經歷一次 `count_utf8`，將剩下的長度檢查一次。
---
## 測驗四
### 解釋上述程式碼運作原理
首先先從一開始的程式碼推測出此程式碼的目標，重要的部份如下：
```cpp
for (; x > 0; x <<= 1) {
if (!(x & 0x8000))
return false;
}
return true;
}
```
先看 `for` 迴圈的停止條件有二，一是 `x <= 0`，二是 `x & 0x8000 = 0`，第一個條件為 `x <= 0` 搭配著 `x <<= 1` 代表著 `x` 將 1 往左移，一直移到全部為 0 然後中止迴圈，第二個條件 `x & 0x8000` 則是檢查在位移過程中最高位是不是一直是 1，只要不是 1 就中止迴圈並回傳 0。
> 101110...00 & 0x8000 = 10...00
> x <<= 1
> 01110...00 & 0x8000 = 00...00
> return false
所以從以上規則可以歸納出此程式碼要的輸入是類似 `11110...0` 的數值，只要不符合規則就會回傳 false。
改寫後的程式碼則如下：
```cpp
const uint16_t n = ~x + 1;
return (n ^ x) < x;
```
改寫後的程式碼的原理也是比較高位的 1，再加上 `^` 運算會將兩個輸入 1 轉成 0，所以如果輸入為 `11110...0` 的數值去相比經過 `(~x + 1) ^ x` 後的數值一定會小於原本的 `x`。
**^ (XOR)** 運算子
| input 1 | input 2 | output |
| ------- | ------- |:------:|
| 0 | 0 | 0 |
| 0 | 1 | 1 |
| 1 | 0 | 1 |
| 1 | 1 | 0 |
```
1101
n = ~x + 1 = 0011
1101 ^ 0011 = 1110
1101 < 1110
return 0
```
從上面的例子可以看到，在利用補數作為 bitmask 運算後，只要原本的數值高位並沒有全部都是 1，經過 `^` 運算後，就會在 0 的地方出現 1，經過 `^` 運算後，數值中 1 又比原本數值的 1 還要高位，就會形成 `(n ^ x) > x`。
### 在 Linux 核心原始程式碼的應用
參考 [bitops.h](https://github.com/torvalds/linux/blob/16f73eb02d7e1765ccab3d2018e0bd98eb93d973/arch/x86/include/asm/bitops.h) 和 [Data Structures in the Linux Kernel](https://0xax.gitbooks.io/linux-insides/content/DataStructures/linux-datastructures-3.html)
bitmask 在 linux 核心的應用可以由以上的參考資料中找到，從標題 **Architecture-specific bit operations** 可以知道其中的程式碼是對不同架構的硬體去運作的位元運算。
其中運用到 bitmask 的是下面此項巨集
```cpp
#define test_bit(nr, addr) \
(__builtin_constant_p((nr)) \
? constant_test_bit((nr), (addr)) \
: variable_test_bit((nr), (addr)))
```
__builtin_constant_p((nr))可以在[ GCC編譯器提供的函式 ](https://gcc.gnu.org/onlinedocs/gcc/Other-Builtins.html)找到其定義，其目的在於檢查一個值在編譯時是不是常數，以下是舉例：
```cpp
int a = 0 + 1;
```
在編譯時 `a = 1` ，不須其他計算 `a` 永遠都是 1。
```cpp
int add(int x)
{
return x + 1;
}
```
上面程式碼在編譯時不知道最終會回傳什麼值，所以不是常數。
:::danger
查閱 GCC Manual !
:notes: jserv
:::
從巨集 `test_bit(nr, addr)` 中可以看到如果 `(__builtin_constant_p((nr))` 成立時，會執行下面的函式
```cpp
static __always_inline int constant_test_bit(long nr, const volatile unsigned long *addr)
{
return ((1UL << (nr & (BITS_PER_LONG-1))) &
(addr[nr >> _BITOPS_LONG_SHIFT])) != 0;
}
```
其中 `BITS_PER_LONG` 和 `_BITOPS_LONG_SHIFT` 定義如下
```cpp
#if BITS_PER_LONG == 32
# define _BITOPS_LONG_SHIFT 5
#elif BITS_PER_LONG == 64
# define _BITOPS_LONG_SHIFT 6
```
此函式的目的在於測試在編譯時如果 `nr` 為常數，記憶體地址會不會設置了某位元，此作法可以優化程式碼的執行速度。其中 `(nr & (BITS_PER_LONG-1))` 為將最高位的數字捨去，留下 `<=(BITS_PER_LONG-1)` 的數字，並且通過位移 `(1UL << (nr & (BITS_PER_LONG-1))` 並且比較此時地址的位元偏移後 `addr[nr >> _BITOPS_LONG_SHIFT])` 是否為 1 ，是的話代表此位元已經被設置。
上述程式碼可以利用在快速的操作位元組中，同時提高找尋位元的速度，下面則是 ChatGPT 給的實際應用
:::danger
改進用語，並確認上述是否正確。注意：程式碼解析不正確。
:notes: jserv
:::
除了上面的例子，此段程式碼多為被利用在標記某個記憶體或處理器的狀態，由於其可以被快速操作，代表可以快速瀏覽過整個環境中的每個處理器的狀態，進而去對標記的記憶體或處理器進行操作。
Sign in with Wallet
Connect another wallet