# 2023q1 Homework2 (quiz2)
contributed by < `SPFishcool` >
## 測驗一
### 運作原理
程式裡 `next_pow2(x)` 要找出最接近且大於等於 `x` 的 2 的冪次方的值。
在改寫程式裡，有著幾行類似下方的程式碼。
```c
x |= x >> 1;
```
這會讓 `x` 右移一位並將 1 set 到原本的 `x` 上，例如： `00100000` 變成 `00110000`、 `00100110` 變成 `00110111`。
既然我們要找下一個 2 的冪次方的數值，那我們可以確保把第一個 1 後面都變成 1 再將 `x+1` 就能夠找到答案。
```c=
x |= x >> 1;
x |= x >> 1;
x |= x >> 1;
x |= x >> 1;
x |= x >> 1;
x |= x >> 1;
x |= x >> 1;
x |= x >> AAAA;
x |= x >> 16;
x |= x >> BBBB;
return CCCC;
```
我們可以考慮最差情況 `0x8000` 我們要 set 63 個位元 ，1 ~ 7 行已經 set 7 個 1 了，第九行又一次 set 16 個 1，因此 `AAAA` 應為 `8`，最後 `BBBB` 再 將剩下的 32 個位元 set ，因此為 `32`，最後 `CCCC` 就會是 `x+1`。
### 引入 `__builtin_clzl`
參考[6.59 Other Built-in Functions Provided by GCC](https://gcc.gnu.org/onlinedocs/gcc/Other-Builtins.html) 內容對 `__builtin_clz` 的描述
```
Built-in Function: int __builtin_ctz (unsigned int x)
Returns the number of trailing 0-bits in x, starting at the least significant bit position. If x is 0, the result is undefined.
```
:::danger
參照 GCC Manual 這樣的第一手材料！
:notes: jserv
> 收到！學生會嘗試參照這些資訊
:::
得知這是一個系列的內建函式，`__builtin_clz` 是回傳從左左邊起第一個 1 之前 0 的個數，而 `__builtin_clzl` 最後的 `l` 代表輸入是 `long` 型態的整數。
因此，運用 `bit = 64 - __builtin_clzl(x)` 可以知道這個數值的最高位元數是多少，再回傳 `1ULL << bit` 即可。
```c
uint64_t next_pow2(uint64_t x) {
int bit = 64 - __builtin_clzl(x);
return (1ULL << (bit));
}
```
除了實作 `next_pow2` ，另外還讓使用者在執行程式時必定要輸入一個整數。
```c
int main(int argc, char *argv[]){
if (argc != 2){
printf("%s need 1 argument.\n", argv[0]);
return 0;
}
```
確保使用者數入的是一個整數，使用 `isdigit` 確認數入的是否是一個整數
```c
char *cvalue = argv[1];
while(*cvalue){
if (!isdigit(*cvalue)){
printf("%s is not an integer.\n", argv[1]);
return 0;
}
cvalue++;
}
```
`isdigit` 在編譯時出現
```bash
next_pow.c:16:10: warning: implicit declaration of function ‘isdigit’ [-Wimplicit-function-declaration]
16 | if (!isdigit(argv[1])){
| ^~~~~~~
next_pow.c:4:1: note: include ‘<ctype.h>’ or provide a declaration of ‘isdigit’
```
這是沒有 `#include` 到必要的函式庫出現的警訊，寫上 `#include<ctype.h>` 就不會出現了。
最後確定為整數就可以使用 `atoll` 將字串轉為 `long long`
```c
uint64_t input = atoll(argv[1]);
```
:::warning
在實作時注意題目的資料型態，此題的型態為 `uint64_t`( `unsigned long` )
:::
### 在 linux 核心原始程式碼中的相似案例
### 觀察 x86 指令
在經過執行以下指令編譯後
```bash
cc -O2 -std=c99 -S next_pow.c
```
觀察到有產生以下 x86 組合語言
```x86=
bsrq %rdi, %rdi
movl $64, %ecx
movl $1, %eax
xorq $63, %rdi
subl %edi, %ecx
salq %cl, %rax
```
第 1 行：`brsq` 能夠將 `%rdi` 的最高位元位置存入 `%rdi`，接下來將 `%edi`
第 4 行：`xorq` 再將 63 與 `%rdi` 做 `xor` 運算，在無號數相當於 63 - `％rdi`
這兩行相當於 `__builtin_clzl` 函式，編譯器的做法就是找出最高位元再與 63 相減得出「出現 1 的最高位元前面 0 的個數」。
## 測驗二
### 運作原理
詳細題目請見 LeetCode [1680. Concatenation of Consecutive Binary Numbers ](https://leetcode.com/problems/concatenation-of-consecutive-binary-numbers/)
此程式只有一個 for 迴圈，內部執行兩個指令
```c=
for (int i = 1; i <= n; i++) {
if (!(DDDD))
len++;
ans = (i | (EEEE)) % M;
}
```
`len` 一開始為 `0`，代表著 `i` 這個數字的 2 進位長度，所以我們可以看 2、3 行， `len++` 的時機點應該就是 2 進位長度增加的時候，也就是 $2^n$，依照 [quiz2 題目](https://hackmd.io/@sysprog/linux2023-quiz2)要求，要判斷 $2^n$ ，`DDDD` 可以填 `i & (i - 1)`。
最後第 4 行會將 `i` 存入 `ans` ，因此在存入之前需要將 `ans` 左移到可以將 `i` 放入的量，`EEEE` 就會是 `ans << len`。
### 使用 GNU 內建函式
若使用 GNU 內建的 `__buitin_clz` 可以省去判斷是否為 $2^n$ ，且 `__buitin_clz` 時間複雜度為 $O(1)$，也同時可以省去使用 if 判斷式的 branch 。
```c
for (int i = 1; i <= n; i++)
ans = (i | (ans << (32 - __builtin_clz(i)))) % M;
```
## 測驗三
### 運作原理
此題為運算出 [utf-8](https://en.wikipedia.org/wiki/UTF-8) 字元數量，原理為只要判斷出首位元組和後續位元組就可以得出 utf-8 字元數量。而後續位元組都有一個共通點：最高的兩個位元為 `10`，
| **ASCII** | Bytes 1 | Bytes 2 | Bytes 3 | Bytes 4 |
|------------|---------|---------|---------|---------|
| 1 Bytes | 0xxx xxxx |
| 2 Bytes | 110x xxxx | 10xx xxxx |
| 3 Bytes | 1110 xxxx | 10xx xxxx | 10xx xxxx |
| 4 Bytes | 1111 0xxx | 10xx xxxx | 10xx xxxx | 10xx xxxx|
```c
for (size_t i = 0; i < len; i++) {
/* -65 is 0b10111111, anything larger in two-complement's should start
* new code point.
*/
if (p[i] > -65)
counter++;
}
```
上述程式碼是把每組位元組當作一個 8 bits 表示的有號整數，其 `-65` (`0b10111111`) 為判斷門檻，一旦小於 `-65` 的值其 2 的補數必為 `10` 開頭。
而 SWAR 版本的程式碼將 8 個位元組（8x8 bits）組合在一起並運用特殊的 Mask 來計算後續位元組的數量。
而原本 `len` 為位元組數量，經過 `len >> 3` 就變成 `uint64_t *` 的陣列長度。
```c
const uint64_t *qword = (const uint64_t *) buf;
const uint64_t *end = qword + len >> 3;
```
迴圈內就是一系列的操作，其操作會使 `10xx xxxx` 的位元組第 7 個位元為 1 ，其餘都為 0，最後再使用 `__builtin_popcountll(t4)` 計算 1 的數量就是後續位元組的數量。
```c=
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);
}
```
操作原理如下：
第 3 行：將 64 位元取 1's 補數
第 4 行：`0x04040404040404040llu` 只會將每一位元組的第 6 位元保留下來，其他都會 clear 成 0。
第 5 行：會將第 4 行的結果進一位。
第 6 行：會將 `t0` 與 `t3` 進行比較。
在最後 `__builtin_popcountll(t4)` 算出後續位元組的數量，再將總長度 - 算出來的數量。
```c
count = (1 << AAAA) * (len / 8) - count;
```
在這段程式碼其實故意寫得較為冗長，`(1 << AAAA) * (len / 8)` 其實就是總長度 `len`。所以 `AAAA` 應是 `3`。
最後位元組數量可能不整除 8 ，所以最後可能會有不滿 8 個的位元組。
最後使用一般策略的 `count_utf8()` 來計算這些字元數量。
```c
count += (len & BBBB) ? count_utf8((const char *) end, len & CCCC) : DDDD
```
`(len & BBBB) ?` 是要取出後半段不滿 8 個的位元組，所以 `BBBB` 應是 `7`(`0b111`)，如果 true，就叫算接下來的部分，因此 `count_utf8()` 裡面 `end` 已經指向尚未處理完的第一個位元組，`len & CCCC` 是還沒處理的長度，因此 `CCCC` 也是 `7`。
如果 false，就不用做任何事了，因此 `DDDD` 為 `0`。
## 測驗四
### 運作原理
可以由符合原本的程式碼來看，符合特定樣式的 1-bit 都是從最高位元由高到低連續排列，只要中間有 0 就不是我們要的樣式。
改寫過的程式碼先將 `n` 設為 `-x`，依照 2's component `x` 從 LSB 算起遇到第一個 `1` 接下來才要做 NOT 運算，例如： `11110000` 2's component is `00010000`，接下來 return 一個邏輯判斷式，`n ^ x` 的結果會少一個 `1`，例如：`11110000 ^ 00010000 = 11100000`，這時候如果 `1` 的中間有任何一個 `0` 便會小於此數，不然都會大於此數（多一個 `1`）。
```c
const uint16_t n = EEEE;
return (n ^ x) < FFFF;
```
所以 `EEEE` 為 `-x`，`FFFF` 為 `x`。
Sign in with Wallet
Connect another wallet