---
tags: linux2023
---
# [2023q1](http://wiki.csie.ncku.edu.tw/linux/schedule) 第 2 週測驗題
:::info
目的: 檢驗學員對 bitwise 的認知
:::
==[作答表單: 測驗 1-2](https://docs.google.com/forms/d/e/1FAIpQLSfza_L600byaQmJe4yDkg4oWl5_Frkp62ONP2Iht0TnEAKVEA/viewform)== (針對 Linux 核心「設計」課程)
==[作答表單: 測驗 3-4](https://docs.google.com/forms/d/e/1FAIpQLSdP5zzR0kphU2da-NdSQz3k6PaC6QfMB4fnziU6jjgy0H0igg/viewform)== (針對 Linux 核心「實作」課程)
### 測驗 `1`
參照 [你所不知道的 C 語言: bitwise 操作](https://hackmd.io/@sysprog/c-bitwise)，考慮 `next_pow2` 可針對給定無號 64 位元數值 `x`，找出最接近且大於等於 2 的冪的值，例如:
* `next_pow2(7)` = 8
* `next_pow2(13)` = 16
* `next_pow2(42)` = 64
以下是可能的實作方式:
```c
#include <stdint.h>
static inline uint64_t pow2(uint8_t e) { return ((uint64_t)1) << e; }
uint64_t next_pow2(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);
}
```
然而上述程式碼存在分支，於是我們可考慮建構以下「填補」位元表示中的 `1`:
```
x = 0010000000000000
x = 0011000000000000
x = 0011110000000000
x = 0011111111000000
x = 0011111111111111
```
最初 `x` 是 `0010000000000000`，經過一系列操作後，成為 `0011111111111111`，亦即設定 (set，即指派為 `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;
}
```
請補完程式碼，使其符合預期。作答規範:
* `AAAA` 和 `BBBB` 皆為數值，且 `AAAA` 小於 `BBBB`
* `CCCC` 為表示式
:::success
延伸問題:
1. 解釋上述程式碼原理，並用 [`__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.
2. 在 Linux 核心原始程式碼找出類似的使用案例並解釋
3. 當上述 `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)")
:::
---
### 測驗 `2`
LeetCode [1680. Concatenation of Consecutive Binary Numbers](https://leetcode.com/problems/concatenation-of-consecutive-binary-numbers/) 給定一整數 $n$ ，回傳將 1 到 $n$ 的二進位表示法依序串接在一起所得到的二進位字串，其所代表的十進位數字 mod $10 ^ 9 + 7$ 之值。
測試資料 1:
輸入： n = 1
輸出： 1
> "1" 於二進位中對應著十進位中 `1` 的值
測試資料 2:
輸入： n = 3
輸出： 27
> 二進位中，1 、 2 、 3 對應著 `1`, `10` 和 `11`。
> 將它們串接在一起，我們得到 `11011`，其對應著十進位數值 `27`
測試資料 3:
輸入： n = 12
輸出： 505379714
> 串接結果為 `1101110010111011110001001101010111100`
> 該十進位值為 `118505380540`
> mod $10 ^ 9 + 7$ 後，結果為 `505379714`
以下是可能的實作:
```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;
}
```
請補完程式碼，使其符合預期。作答規範:
* `DDDD` 和 `EEEE` 皆為表示式
:::success
延伸問題:
1. 解釋上述程式碼運作原理
2. 嘗試使用 [`__builtin_{clz,ctz,ffs}`](https://gcc.gnu.org/onlinedocs/gcc/Other-Builtins.html) 改寫，並改進 mod $10^9 + 7$ 的運算
:::
---
### 測驗 `3`
[SIMD within a register](https://en.wikipedia.org/wiki/SWAR) (SWAR) 是軟體最佳化技巧之一，以下展示 SWAR 運用於 64 位元微處理器架構，原本判斷 2 個 32 位元寬度的整數是否都是奇數 (odd)，可能會這樣撰寫:
```c
#include <stdint.h>
bool both_odd(uint32_t x, uint32_t y) {
return (x & 1) && (y & 1);
}
```
但我們可先組合 (compound) 2 個 32 位元寬度的整數為 1 個 64 位元整數，再運用特製的 bitmask，從而減少運算量:
```c
static uint64_t SWAR_ODD_MASK = (1L << 32) + 1;
bool both_odd_swar(uint64_t xy) {
return (xy & SWAR_ODD_MASK) == SWAR_ODD_MASK;
}
```
測試程式:
```c
static inline uint64_t bit_compound(uint32_t x, uint32_t y) {
return ((0L + x) << 32) | ((y + 0L) & (-1L >> 32));
}
int main()
{
int x = 12345678;
int y = 9012345;
uint64_t xy = bit_compound(x, y);
printf("%d, %d\n", both_odd(x, y), both_odd_swar(xy));
}
```
延伸閱讀: [SIMD and SWAR Techniques](https://www.chessprogramming.org/SIMD_and_SWAR_Techniques)
[UTF-8](https://en.wikipedia.org/wiki/UTF-8) 字元可由 1, 2, 3, 4 個位元組構成。其中單一位元組的 UTF-8 由 ASCII 字元構成，其 MSB 必為 `0`。
UTF-8 的多位元組字元是由一個首位元組和 1, 2 或 3 個後續位元組 (continuation byte(s)) 所構成。後續位元組的最高 2 個位元會設定為 `10`。對於首位元組，最高的 2 個位元始終為 `11`，下表展現多位元組字元的規則:
| ASCII | 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 |
若輸入的字串是一個有效的 UTF-8 序列，則計算其中的後續位元組數量，並將此數字從總字串長度中減去，即可確定字元數量。
將位元組轉換為 (以二補數表示) 有號整數的位元組，並與 "magic number" 進行比較，就足以確定它是否為後續位元組。對應的程式碼如下:
```c
#include <stddef.h>
#include <stdint.h>
size_t count_utf8(const char *buf, size_t len)
{
const int8_t *p = (const int8_t *) buf;
size_t counter = 0;
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++;
}
return counter;
}
```
SWAR 通常不易實作，因此，我們觀察它們的位元模式：(從最低位元起算) 第 7 位元為 1，且第 6 位元為 0。於是我們可採用以下表示式:
```
not bit6 and bit7
```
再計算 (使用 population count 指令) 有多少位元組裡頭的 `1` (即具有此屬性)。
> [`__builtin_popcount`](https://gcc.gnu.org/onlinedocs/gcc/Other-Builtins.html)
1. 輸入的位元組
```c
t0 = [00xx.xxxx|01xx.xxxx|10xx.xxxx|11xx.xxxx]
^^^^^^^^^
continuation byte
```
2. 反向運算 (``not bit6``)
```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 個位元的位置)
```
t3 = t2 + t2
t3 = [1000.0000|0000.0000|1000.0000|0000.0000]
```
5. 進行 ``not bit6 and bit7``
```
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. 以 population count 指令計算，即 `popcount(t4)`
SWAR 實作如下:
```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;
}
```
請補完程式碼，使其運作符合預期。作答規範:
* `AAAA`, `BBBB`, `CCCC`, `DDDD` 皆為常數
* 以最精簡的方式展現
延伸閱讀:
* [Optimized memchr() Implementation For The Linux Kernel Up To ~4x Faster](https://www.phoronix.com/news/Linux-Kernel-Faster-memchr)
* [在程式裡算 Emoji 字數的那些問題](https://medium.com/dcardlab/8e1a1170a499)
:::success
延伸問題:
1. 解釋上述程式碼運作原理，比較 SWAR 和原本的實作效能落差
2. 在 Linux 核心原始程式碼找出 UTF-8 和 Unicode 相關字串處理的程式碼，探討其原理，並指出可能的改進空間
:::
----
### 測驗 `4`
以下程式碼可判定 16 位元無號整數是否符合特定樣式 (pattern):
```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;
}
```
符合上述程式碼的樣式，如下:
```
pattern: 8000 (32768)
pattern: c000 (49152)
pattern: e000 (57344)
pattern: f000 (61440)
pattern: f800 (63488)
pattern: fc00 (64512)
pattern: fe00 (65024)
pattern: ff00 (65280)
pattern: ff80 (65408)
pattern: ffc0 (65472)
pattern: ffe0 (65504)
pattern: fff0 (65520)
pattern: fff8 (65528)
pattern: fffc (65532)
pattern: fffe (65534)
pattern: ffff (65535)
```
改寫上述程式碼，使其達到等價行為，但更精簡有效。
```c
bool is_pattern(uint16_t x)
{
const uint16_t n = EEEE;
return (n ^ x) < FFFF;
}
```
EEEE = ?
FFFF = ?
:::success
延伸問題:
1. 解釋上述程式碼運作原理
2. 在 Linux 核心原始程式碼找出上述 bitmask 及產生器，探討應用範疇
> 參見 [Data Structures in the Linux Kernel](https://0xax.gitbooks.io/linux-insides/content/DataStructures/linux-datastructures-3.html)
:::
---
Sign in with Wallet
Connect another wallet