---
# System prepended metadata

title: 2023q1 Homework2 (quiz2)
tags: [Linux Kernel]

---

---
tags: Linux Kernel
---

# 2023q1 Homework2 (quiz2)
contributed by < [`chun61205`](https://github.com/chun61205) >

> [第 2 週測驗題](https://hackmd.io/@sysprog/linux2023-quiz2)

## 測驗 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 >> AAAA;
    x |= x >> 16;
    x |= x >> BBBB;
    return CCCC;
}
```
### 解釋程式碼原理，並用 `__builtin_clzl` 改寫
#### 解釋程式碼原理
該程式碼可以找出最近且大於 `x` 的 $2$ 的冪的值。
簡單來說，此程式碼透過將 `x` 最大位數之後的位數全部都設成 $1$ 最後只需要再加上 $1$ 就可以得到最近且大於 `x` 的 $2$ 的冪的值。
我們可以已最大情況為例，假設 `x=0b01XXXXXX` ，其中 `X` 代表值可以是 `0` 也可以是 `1` 。
```c
x |= x >> 1;        // x = 0b011XXXXX
x |= x >> 1;        // x = 0b0111XXXX
x |= x >> 1;        // x = 0b01111XXX
x |= x >> 1;        // x = 0b011111XX
x |= x >> 1;        // x = 0b0111111X
x |= x >> 1;        // x = 0b01111111
x |= x >> 1;        
x |= x >> AAAA;     
x |= x >> 16;       
x |= x >> BBBB;     
```

因此可以判斷 `AAAA` 為 `1` ， `BBBB` 為 `32` ， `CCCC` 為 `x+1` 。
且程式碼可以簡化為
```c
uint64_t next_pow2(uint64_t x)
{
    x |= x >> 1;
    x |= x >> 2;
    x |= x >> 4;
    x |= x >> 8;
    x |= x >> 16;
    x |= x >> 32;
    return x + 1;
}
```
#### 用 `__builtin_clzl` 改寫
> `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.

```c
uint64_t next_pow2(uint64_t x)
{
    int n = __builtin_clz(x);
    return 0x8000000000000000 >> (n - 1);
}
```

---

## 測驗 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 (!(DDDD))
            len++;
        ans = (i | (EEEE)) % M;
    }
    return ans;
}
```
### 解釋程式碼運作原理
該函式的的功能在於，給定一整數 $n$ ，回傳將 $1$ 到 $n$ 的二進位表示法依序串接在一起所得的二進位字串，其所代表的十進位數字 $mod 10^9+7$ 之值。
該函式透過 `for` 迴圈尋訪 $1$ 到 $n$ 的整數，並透過 `len` 來判斷目前尋訪到的整數 `i` 的二進位表示法的位元數，只要 `i` 為`2` 的冪的值，則需長度會多 $1$ ，因此 `DDDD` 為 `x & (x - 1) == 0` ，最後，將 `i` 串接到 `ans` 最後面， 因此 `EEEE` 為 `ans<<len` 。

---

## 測驗 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;

    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 << AAAA) * (len / 8)  - count;
    count += (len & BBBB) ? count_utf8((const char *) end, len & CCCC) : DDDD;

    return count;
}
```
### 解釋程式碼運作原理
該程式碼的功用在於使用 SWAR 來一次比較 $8$ 個位元，以判斷 `buf` 需要使用幾個 bytes 表示。

程式碼的前兩行在設定迴圈的終點：
```c
const uint64_t *qword = (const uint64_t *) buf;
const uint64_t *end = qword + len >> 3;
```
透過 `len >> 3` 也就是 `len / 8` 來表示 `buf` 有幾個 $8$ bytes。
接著，利用 for 迴圈來一次取 $8$ bytes 檢查：
```c
for (; qword != end; qword++)
```
並透過以下一系列的操作以確認第 6 個位元組是否為 `1`

1. 輸入的位元組
    ```c
    t0 = [00xx.xxxx|01xx.xxxx|10xx.xxxx|11xx.xxxx]
                              ^^^^^^^^^
                              continuation byte
    ```
2. 反向運算
    ```c
    t1 = ~t0
    t1 = [11xx.xxxx|10xx.xxxx|01xx.xxxx|00xx.xxxx]   
    ```
3. 隔離反向的第 6 個位元
    ```c
    t2 = t1 & 0x40404040
    t2 = [0100.0000|0000.0000|0100.0000|0000.0000]
    ```
4. 對第 6 個位元，向左位移 $1$ 個位元 (移至第 7 個位元的位置)
    ```c
    t3 = t2 + t2
    t3 = [1000.0000|0000.0000|1000.0000|0000.0000]
    ```
5. 進行 `~bit6 && bit7`
    ```c
    t4 = t0 & t3
    t4 = [00xx.xxxx|01xx.xxxx|10xx.xxxx|11xx.xxxx] &
         [1000.0000|0000.0000|1000.0000|0000.0000]
       = [0000.0000|0000.0000|1000.0000|0000.0000]
                              ^^^^^^^^^
                              the only non-zero byte
    ```
6. 以 `__builtin_popcount` 計算有多少 `1`

最後再確認未能被 $8$ 整除的部分有多少 continuation bytes。
```c
count = (1 << AAAA) * (len / 8)  - count;
count += (len & BBBB) ? count_utf8((const char *) end, len & CCCC) : DDDD;
```
需要將 `len` 最右側的 $3$ 個 bits 設為 `0` 並減去 continuation bytes 數量，再將無法被整除的部分，使用 `count_utf8` 得到去除 continuation bytes 後的字元數，最後將其相加得到結果。
因此可以判斷 `AAAA` 為 `3` ， `BBBB` 為 `7` ， `CCCC` 為 `7` ， `DDDD` 為 `0` 。
:::warning
能否改寫程式碼、使其行為相同？
:notes: jserv
:::

---

## 測驗 4
```c
#include <stdint.h>
#include <stdbool.h>

bool is_pattern(uint16_t x)
{
    const uint16_t n = EEEE;
    return (n ^ x) < FFFF;
}
```
### 解釋程式碼運作原理
只要將 pattern 換成二進位，便可得知 pattern 的規則：
```
1000000000000000
1100000000000000
1110000000000000
...
1111111111111111
```
如此一來只要以以下思路進行運算：
1. `~x + 1`
    ```
    1000000000000000
    0100000000000000
    0010000000000000
    ...
    0000000000000001
    ```
2. `(~x + 1) ^ x` ，也就是去掉最右邊的 `1`
    ```
    0000000000000000
    1000000000000000
    1100000000000000
    ...
    1111111111111110
    ```
    
3. 最後得出來的值，因為最右邊的 `1` 被去掉，必定會小於 `x`

因此可以得知， `EEEE` 為 `~x + 1` ， `FFFF` 為 `x` 。
另外，值得注意的是，若 `x` 不為 pattern 則 `(~x + 1) ^ x` 並不會小於 `x` ：
1. 高位元並非從最高位元開始連續的 `1`
    ```
       0100000000000000
    -> 1100000000000000
    -> 1000000000000000
    ```
2. 低位元並非從最低位元開始連續的 `0`
    ```
       1100000000001000
    -> 0011111111111000
    -> 1111111111110000
    ```