---
# System prepended metadata

title: 2023q1 Homework2 (quiz2)
tags: [Linux核心實作]

---

---
title: 2023q1 Homework2 (quiz2)
tags: Linux核心實作
---

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

## [你所不知道的 C 語言: bitwise 操作](https://hackmd.io/@sysprog/c-bitwise) ( 隨記 )

一個字元 1 byte (位元組)

### [數值系統](https://hackmd.io/@sysprog/c-numerics)
* 數值系統的設計導致不同程式語言都會出現一些計算上的誤差
  例如：0.1-0.01=0.09000000000000001 (python 2.7)

#### 運用 bit-wise operator
* 大小寫轉換
    * 將字元轉成小寫: 免除使用分支
    ('a' | '` `') // 得到 'a'
    ('A' | '` `') // 得到 'a'
    * 將字元轉為大寫: 免除使用分支
    ('a' & '`_`') // 得到 'A'
    ('A' & '`_`') // 得到 'A'
    * 大小寫互轉: 避免使用分支
    ('a' ^ '` `') // 得到 'A'
    ('A' ^ '` `') // 得到 'a'
    ```
    'a' 的二進位表示 1100001
    'A' 的二進位表示 1000001
    ' ' 的二進位表示  100000
    '_' 的二進位表示 1011111
    ```

#### 交換兩個記憶體空間內的數值，可完全不用額外的記憶體來實作
> 在 boot manager 或 boot loader 資源有限
> 主記憶體可能不能用

```c
void xorSwap(int *x, int *y) {
    *x ^= *y;
    *y ^= *x;
    *x ^= *y;
}
```
#### 位移運算子
* 未定義狀況
1. 左移超過變數長度
    ```c
    int i=0xFFFFFFFF;
    i = i << 32; // 此結果未定義
    ```
    輸出：
    ```
    main.c:14:11: warning: left shift count >= width of type [-Wshift-count-overflow]
       14 |     i = i << 32; // 此結果未定義
          |           ^~
    ffffffff
    ```
2. 右移一個負數時，可能是邏輯位移(左側補 0 )或是算術位移(補上號數)

#### signed 和 unsigned 之間的關係
* 無窮迴圈
```c
int n = 10; 
for  i = n - 1 ; i - sizeof(char) >= 0; i--)
    printf("i: 0x%x\n",i);
```
`sizeof` 不是 function 是 operator (運算子)
=> 回傳型態：unsigned interger
整數型態和 unsigned interger 做運算時，會整個變成 unsigned interger

## quiz 2

### 測驗 1
考慮 next_pow2 可針對給定無號 64 位元數值 x，找出最接近且大於等於 2 的冪的值，例如:

* next_pow2(7) = 8
* next_pow2(13) = 16
* next_pow2(42) = 64

```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+1;
}
```
上述程式碼將 x 和自己右移的值做 bitwise or 運算，目的是希望將比 x 的 MSB 低位的數字都變成 1，因此總共右移了 63 個位元，如此再 +1 進位後就會是想找的 2 的冪的值

:::info
疑惑點：
題目描述要找「最接近且大於等於 2 的冪的值」指的應該是最接近 x 且大於等於 x 的 2 的冪的值，但若是 x 本身就是 2 的冪，例如 1000₂ ，做完運算後會得到 10000₂ ，但依照題目敘述應該求的是 1000₂
:::

#### 1. 以 [__builtin_clzl](https://gcc.gnu.org/onlinedocs/gcc/Other-Builtins.html) 改寫

int __builtin_clzl (unsigned long) 會回傳前導 0 的位數，例如 input 為 9 (1001₂) 時，回傳 64 - 4 = 60

則可以知道最高有效位在最低位往高位數第 4 位，可知想求的值為 1 左移四個位數，即為 10000₂
```c
uint64_t next_pow2(uint64_t x)
{
    int len = 64 - __builtin_clzl(x);
    return 1 << len;
}
```
經同學提醒，才想到 return 那邊若直接寫 1 會預設是 int ，因此若輸入超過 32 位元的值會溢位，需要特別標示型別為 `uint64_t`。
```c
uint64_t next_pow2(uint64_t x)
{
    int len = 64 - __builtin_clzl(x);
    return (uint64_t)1 << len;
}
```

#### 2. 在 Linux 核心原始程式碼找出類似的使用案例並解釋


#### 3. 當上述 clz 內建函式已運用時，編譯器能否產生對應的 x86 指令？
> 提示: 可執行 cc -O2 -std=c99 -S next_pow2.c 並觀察產生的 next_pow2.s 檔案，確認 bsrq 指令 (表示 “Bit Scan Reverse”)
```
	.file	"next_pow2.c"
	.text
	.p2align 4
	.globl	next_pow2
	.type	next_pow2, @function
next_pow2:
.LFB13:
	.cfi_startproc
	endbr64
	bsrq	%rdi, %rdi
	movl	$64, %ecx
	movl	$1, %eax
	xorq	$63, %rdi
	subl	%edi, %ecx
	sall	%cl, %eax
	cltq
	ret
	.cfi_endproc
    
    ...
    
    main:
.LFB14:
	.cfi_startproc
	endbr64
	subq	$24, %rsp
	.cfi_def_cfa_offset 32
	leaq	.LC0(%rip), %rdi
	movq	%fs:40, %rax
	movq	%rax, 8(%rsp)
	xorl	%eax, %eax
	movq	%rsp, %rsi
	call	__isoc99_scanf@PLT
	bsrq	(%rsp), %rax
    ...
```

### 測驗 2
LeetCode 1680. Concatenation of Consecutive Binary Numbers 給定一整數 n ，回傳將 1 到 n 的二進位表示法依序串接在一起所得到的二進位字串，其所代表的十進位數字 $mod\ {10^9}+7$ 之值。
```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;
}
```

#### 1. 解釋上述程式碼運作原理

此程式碼將 1 到 n 依序串接進 ans，若 `i & (i-1)` 為 0，表示 i 為 2 的冪，則 i 比 i - 1 的位數多一位，ans 在左移準備串接 i 時，要比串接 i - 1 時多左移一位，因此將記錄左移位數的 len + 1。
再利用左移足夠位數後填補的 0 的部分，與要串接的數字做 bitwise or 達到二進位制相加的效果。

例如當 n 為 4 時：
```
i = 1 時，1＆0 為 0，len + 1，len = 1，ans = 1
i = 2 時，1＆0 為 0，len + 1，len = 2，ans = 110
i = 3 時，1＆0 非 0，len + 1，len = 2，ans = 11011
i = 4 時，1＆0 為 0，len + 1，len = 3，ans = 11011110
```
#### 2. 嘗試使用 __builtin_{clz,ctz,ffs} 改寫，並改進 $mod\ {10^9}+7$ 的運算
```
clz：回傳 leading 0-bits
ctz：回傳 trailing 0-bits
ffs：回傳最低有效位索引值 + 1
```

```c
int concatenatedBinary(int n)
{
    const int M = 1e9 + 7;
    int len = 0;
    long ans = 0;
    for (int i = 1; i <= n; i++) {
        len = 32 - __builtin_clz (i);
        ans = (i | (ans << len)) % M;
    }
    return ans;
}
```


### 測驗 3
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 << 3) * (len / 8)  - count;
    count += (len & 7) ? count_utf8((const char *) end, len & 7) : 0;

    return count;
}
```
首先把字串轉為 uint64_t 的形式存在 *qword
接著 len >> 3 即為 len / 8，長度除以 8 (無條件捨去到整數位) 可知該字串有幾個 8 bytes(64 bits) 一組，加上 qword 可得最後一組的位址

題目中提到：
`若輸入的字串是一個有效的 UTF-8 序列，則計算其中的後續位元組數量，並將此數字從總字串長度中減去，即可確定字元數量。`
後續位元組的位原模式如題目所述為 `not bit6 and bit7`

因此接著跑 for 迴圈一次處理 64 個位元，計算想求的後續位元組數量：(如測驗題目說明)
1. 輸入的位元組
1. 反向運算 (not bit6)
1. 隔離反向的第 6 個位元
1. 對第 6 個位元，向左位移 1 個位元 (移至第 7 個位元的位置)
1. 進行 not bit6 and bit7
1. 以 population count 指令計算，即 popcount(t4)

再來將算出來的數字 count 用總字串長度減去
而須注意的是目前只做了可以 64 bits 一組處理的部分，也就是這裡的總長度不應該用原本字串的總長度，而是要先用　len / 8 計算做了幾組，再乘 8 (1 << 3)，算出目前已計算的總長度，再減去 count

最後計算有沒有多出來不能 64 bits 一組一起算的部分，以 len & 7 判斷，也就是 len % 8，若有的話再用 count_utf8 計算並加進 count，其長度為 len & 7，也就是以 8 bytes 為一組剩餘的長度；若沒有的話就加 0。


### 測驗 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) => 1000 0000 0000 0000
pattern: c000 (49152) => 1100 0000 0000 0000
pattern: e000 (57344) => 1110 0000 0000 0000
pattern: f000 (61440) => 1111 0000 0000 0000
pattern: f800 (63488) => 1111 1000 0000 0000
pattern: fc00 (64512) => 1111 1100 0000 0000
pattern: fe00 (65024) => 1111 1110 0000 0000
pattern: ff00 (65280) => 1111 1111 0000 0000
pattern: ff80 (65408) => 1111 1111 1000 0000
pattern: ffc0 (65472) => 1111 1111 1100 0000
pattern: ffe0 (65504) => 1111 1111 1110 0000
pattern: fff0 (65520) => 1111 1111 1111 0000
pattern: fff8 (65528) => 1111 1111 1111 1000
pattern: fffc (65532) => 1111 1111 1111 1100
pattern: fffe (65534) => 1111 1111 1111 1110
pattern: ffff (65535) => 1111 1111 1111 1111
```
可觀察到從最左邊開始為連續的 1 ，接著是連續的 0

更精簡的程式碼：
```c
bool is_pattern(uint16_t x)
{
    const uint16_t n = ~x + 1;
    return (n ^ x) < x;
}
```
這種樣式下將 x 做 bitwise not 會將原本的 1 變成 0、0 變成 1，例如：`1111 0000 0000 0000` 變成 `0000 1111 1111 1111`，加一後變成 `0001 0000 0000 0000`，與 x 做 bitwise xor 後會將 x 最低位的 1 去掉，得到比 x 小的值。

而若非此樣式的，例如 `1101 0000 0000 0000`，非連續 1 接上 0，bitwise not 後會變成 `0010 1111 1111 1111`，加 1 後變成 `0011 0000 0000 0000`，會有兩個位數是 1 ，再做 bitwise xor 會變成 `1110 0000 0000 0000` 反而會進位。

而 1 接上非連續 0 的情況，例如 `1111 0001 0000 0000`，bitwise not 再加一後會變成 `0000 1111 0000 0000`，也會有不只一個位數是 0，做 bitwise 後會變成 `1111 1110 0000 0000`，數值也會比較大。

可知只有連續 1 接連續 0 的情況下作這些操作後可去掉最低位的 1 ，得到比原本更小的數值。