# 2023q1 Homework2 (quiz2)
contributed by < `gaberplaysgame` >
## 測驗 1
### 原理
```c
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;
}
```
以上程式碼取得比 64 位元的無號整數更大的 2 的冪次，舉例若 `x = 0x7F0E`, 則回傳的值會是 `0x8000` = $2^{15}$。
當 x 右移後產生的值與原本的 `x` 進行 OR 運算並重複 63 次後，可以把第一個 1 以後的 0 皆設為 1，如上面的例子，`x` 會變成 `0x7FFF`。再對 x 進行遞增的動作後由於進位，即可得到 `0x8000` 的數值。
### 利用 `__builtin_clzl` 改寫
> Returns the number of trailing 0-bits in x, starting at the least significant bit position. If x is 0, the result is undefined.
>
> Similar to `__builtin_ctz`, except the argument type is **unsigned long**.
這邊要注意的是 `__builtin_ctzl` 只支援 `unsigned long`，但 `uint_64_t` 為 `unsigned long long`，顯然這裡需要進行處理。利用兩個 32 位元無號整數 `head` 與 `tail` 存入 `x` 的兩部分，並對 `head` 進行比較。
- 若 `head` 非零則對進行 `__builtin_ctzl(head)`
- 若 `head` 為零則進行 `__builtin_ctzl(tail) + 32`
這邊若 head 為零不能直接進行 `__builtin_ctzl` 操作，此函數對零的操作並未定義。若使用 gcc 編譯後執行會得出 31 ，顯然與預期結果 32 不符。
```c
uint64_t next_pow2_32(uint64_t x)
{
uint32_t head = (uint32_t)(x >> 32), tail = (uint32_t)x;
int leading_zero = head ? __builtin_clzl(head) : 32 + __builtin_clzl(tail);
return pow2((uint8_t)(64 - leading_zero));
}
```
另外用 `__builtin_clz` 其實有變體支援 `unsign long long`，以下是由 `__builtin_ctzll` 寫成的版本：
```c
uint64_t next_pow2_64(uint64_t x)
{
return pow2((uint8_t)(64 - __builtin_clzll(x)));
}
```
### `__builtin_clz` 在 Linux 核心的應用案例
閱讀 [<asm/compiler.h>](https://elixir.bootlin.com/linux/latest/source/arch/alpha/include/uapi/asm/compiler.h#L55)，可以看到此內建函式在 Linux 核心內被定義為 `__kernel_ctlz(x)`，它被應用在 `fls` 、 `fls64` 、 `fls_long` 等函式上，實際案例在 [<linux/bitop.h>](https://elixir.bootlin.com/linux/latest/source/include/linux/bitops.h#L228) 與 [<linux/log2.h>](https://elixir.bootlin.com/linux/latest/source/include/linux/log2.h#L57) 可見。
```c
static inline unsigned fls_long(unsigned long l)
{
if (sizeof(l) == 4)
return fls(l);
return fls64(l);
}
```
### 當上述 clz 內建函式已運用時，編譯器能否產生對應的 x86 指令？
執行 `gcc -O2 -std=c99 -S .\question_1.c` 後產生的組合語言檔案，可以看到 bsrl 有被產生，可證明編譯器有產生對應的 x86 指令。
```
_next_pow2_32:
LFB20:
.cfi_startproc
pushl %edi
.cfi_def_cfa_offset 8
.cfi_offset 7, -8
pushl %esi
.cfi_def_cfa_offset 12
.cfi_offset 6, -12
pushl %ebx
.cfi_def_cfa_offset 16
.cfi_offset 3, -16
subl $16, %esp
.cfi_def_cfa_offset 32
movl 36(%esp), %esi
movl 32(%esp), %edi
movl $LC0, (%esp)
movl %edi, 4(%esp)
movl %esi, 8(%esp)
call _printf
testl %esi, %esi
jne L34
bsrl %edi, %ebx
xorl $31, %ebx
addl $32, %ebx
```
## 測驗 2
### 原理
```c
int concatenatedBinary(int n)
{
const int M = 1e9 + 7;
int len = 0; /* the bit length to be shifted */
/* use long here as it potentially could overflow for int */
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;
}
```
可以看到 `DDDD` 的數值應填入 `i & (i - 1)`， `EEEE` 為 `ans << len`。
整數 len 在每次迴圈都會用 `i & (i - 1)` 判斷是否應該增加，這數值代表每次迴圈 ans 會進行的移位數。
- 若 `i = 4`，則 `4 & 3 = 0`，這是因為 2 的冪次只有一個位元為 1，且 `i - 1` 的同個位元在 `i` 為 2 的冪次的條件下一定為 0 的原因。
- 相反，若 `i = 3`，則 `3 & 2 = 0`，由於 3 並非 2 的冪次，與 `i - 1` 進行 AND 運算後並不會得到 0 。
### 利用 `__builtin_{clz,ctz,ffs}` 改寫，並改進 mod $10^9 + 7$ 的運算
在我的 linux 電腦上代入 `n = 12` 得到 361394469 並非預期結果 505379714 ，仔細調查發現我的 long 是 32 位元，最大值為 2147483647 ，而模數為 1000000007 ，約是最大值的一半。把式子 `(i | (ans << len)) % M` 以數學表示可得$ans\times2^{len} + i \pmod M$，若 `ans` 小於並足夠大的情況下，直接乘上 `2^len` ，在 `len > 2` 的情況下會導致整數溢出，進而產生錯誤值。因此把 `ans` 設為 long long。
- 以第 11 次迴圈舉例， `ans = 406586234`。
- $2^{len} = 2^4 = 16$，$406586234\times16 = 6,505,379,744\approx6.5\times10^{9}$ > $2^{32}$，在此運算步驟會導致溢出。
再利用上一大題的 `__builtin_clz` 取代 `len` 的計算，可得以下程式碼：
```diff
- long ans = 0;
+ long long ans = 0;
...
for (int i = 1; i <= n; i++) {
- if (!(i & (i - 1)))
- len++;
- ans = (i | (ans << len)) % M ;
+ ans = (i | (ans << (32 - __builtin_clz(i)))) % M;
}
```
## 測驗 3
### 原理
```c=
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); // 這邊要括號，C 語言內加法的優先度高於右移
size_t count = 0;
for (; qword != end; qword+=1) {
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;
}
```
- count_uf8: 將 `str[0~len-1]` 依序進行檢驗。
- swar_count_uf8: 將 `str` 內的每八項（如 `str[0]~str[7]`）塞入 qword 內一次進行檢驗，若有多餘項（如 `str[8]`）則利用原本的 `count_uf8` 檢驗。
在第 16 行會對於產出的 `count` 進行進行調整，在 13 行所產出的 `count` 所代表的是 continuation bytes （後續位元組），要將字串長度減去後續位元組數量後才會得出字元數。
另第 17 行則是對塞不滿 qword 內的位元組進行檢驗，這裡的 `len & 7` 相當於 `len % 8` 。
### 在 Linux 核心原始程式碼找出 UTF-8 和 Unicode 相關字串處理的程式碼
翻閱 [<include/linux/unicode.h>](https://elixir.bootlin.com/linux/latest/source/include/linux/unicode.h) 可以看到以下函式被定義，並在 [<fs/unicode/utf8-core.c>](https://elixir.bootlin.com/linux/latest/source/fs/unicode/utf8-core.c#L12) 中實作，用來判斷是否為合法的 UTF-8 字元。
```c
int utf8_validate(const struct unicode_map *um, const struct qstr *str);
```
```c
int utf8_validate(const struct unicode_map *um, const struct qstr *str)
{
if (utf8nlen(um, UTF8_NFDI, str->name, str->len) < 0)
return -1;
return 0;
}
EXPORT_SYMBOL(utf8_validate);
```
其他有應用到的檔案如 [<fs/unicode/utf8n.h>](https://elixir.bootlin.com/linux/latest/source/fs/unicode/utf8n.h) 也有相關函式的實作，這裡就不列舉。
## 測驗 4
### 原理
```c
bool is_pattern(uint16_t x)
{
const uint16_t n = ~x + 1;
return (n ^ x) < x;
}
```
針對 16 位元無號整數 `x`，若 `x` 的位元排列符合 `11...10...0` 的圖樣，則回傳 `true` 。故將 `n` 設為 `x` 位元反轉後加上 `1`，若 `x` 符合上述樣式則新的 `n` 會是 `0...010...0` 的圖樣。當 `n XOR x` 後會產出比 `x` 少一個 `1` 的數值，因此會比 `x` 還小。
- 若 `x = 11111000`，則 `n = 00001000` ， `x ^ n = 11110000 < x`。
- 若 `x = 11101000`，則 `n = 00011000` ， `x ^ n = 11110000 > x`。
- 若 `x = 11001000`，則 `n = 00111000` ， `x ^ n = 11110000 > x`。
從上面的兩個例子可以看到若 `x` 最右邊的 `1` 在從左數來**第 5 位元**時，不論 `x` 樣式， `x ^ n` 的值一定為 `11110000`，故也只有 `11111000` 可以比 `x ^ n` 大，因此有獨一性。這個情況不論最右邊的 `1` 在從左數來第幾位元都會成立。
### Linux 核心的 bitmask 及產生器
根據文件 [Data Structures in the Linux Kernel](https://0xax.gitbooks.io/linux-insides/content/DataStructures/linux-datastructures-3.html) 可以看到應用在 [<linux/bitop.h>](https://github.com/torvalds/linux/blob/16f73eb02d7e1765ccab3d2018e0bd98eb93d973/arch/x86/include/asm/bitops.h)。其中以下函式有用到遮罩，會根據 nr 在編譯時間是否為常數來分別進行不同的測試位元函數。
```c
#define test_bit(nr, addr) \
(__builtin_constant_p((nr)) \
? constant_test_bit((nr), (addr)) \
: variable_test_bit((nr), (addr)))
static __always_inline bool constant_test_bit(long nr, const volatile unsigned long *addr)
{
return ((1UL << (nr & (BITS_PER_LONG-1))) &
(addr[nr >> _BITOPS_LONG_SHIFT])) != 0;
}
static inline int variable_test_bit(long nr, volatile const unsigned long *addr)
{
int oldbit;
asm volatile("bt %2,%1\n\t"
"sbb %0,%0"
: "=r" (oldbit)
: "m" (*(unsigned long *)addr), "Ir" (nr));
return oldbit;
}
```
Sign in with Wallet
Connect another wallet