# 2023q1 Homework2 (quiz2)
contributed by < [ctc2324](https://github.com/ctc2324) >
## 測驗 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 >> 1;
x |= x >> 16;
x |= x >> 32;
return (x+1);
}
```
### 延伸問題
1. 解釋上述程式碼原理，並用 `__builtin_clzl` 改寫
1. 在 Linux 核心原始程式碼找出類似的使用案例並解釋
1. 當上述 `clz` 內建函式已運用時，編譯器能否產生對應的 `x86` 指令？
#### 1. 解釋上述程式碼原理，並用 `__builtin_clzl` 改寫
##### 程式碼原理
以上程式目標為針對給定的無號64位元數值 `x` ，找出最接近且大於等於 `2` 的冪的值。
因此我們只要將此數最大位元之後的位元全數填滿 `1` ，再將最後 `return` 值加上1，就可以得到最接近 `x` 的冪值。
此程式透過將 `x` 位元移動，並與 `x` 做 OR 運算，來將後面位元填滿 1 。
因此可以知道在64位元的清況下，最多只需要操作63次即可達成。已知每次操作都會以 2 的倍數成長，因此可以將程式碼優化為：
```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);
}
```
也可以達成一樣的效果。
以下舉例 `x` 為 `0x30000000` ，其在二進位表示下為 `0011 0000 0000 0000 0000 0000 0000 0000`
```c
uint64_t next_pow2(uint64_t x)
{
// x = 0011 0000 0000 0000 0000 0000 0000 0000
x |= x >> 1; // x = 0011 1100 0000 0000 0000 0000 0000 0000
x |= x >> 2; // x = 0011 1111 0000 0000 0000 0000 0000 0000
x |= x >> 4; // x = 0011 1111 1111 0000 0000 0000 0000 0000
x |= x >> 8; // x = 0011 1111 1111 1111 1111 0000 0000 0000
x |= x >> 16; // x = 0011 1111 1111 1111 1111 1111 1111 1111
x |= x >> 32; // x = 0011 1111 1111 1111 1111 1111 1111 1111
return (x+1); // x = 0100 0000 0000 0000 0000 0000 0000 0000
}
```
輸出為 `0100 0000 0000 0000 0000 0000 0000 0000` 即十進位的 `1073741824`。
##### 用 `__builtin_clzl` 改寫
`__builtin_clzl` 函式定義為傳回輸入數 `x` 最高位開始連續的 0 的個數。以上面的 `0x30000000` 為例：
:::info
x = 0011 0000 0000 0000 0000 0000 0000 0000
最高位數字為從左邊數來的第35位元，因此 `__builtin_clzl` 函式會回傳34，表示在最高位元左邊有連續34個0。
:::
了解 `__builtin_clzl` 函式的作用後，我們便可以將程式改寫成：
```c
uint64_t next_pow2(uint64_t x)
{
if(x==0)
return 1;
int clz;
clz = __builtin_clzl(x);
return 1 << (64-clz);
}
```
此處須注意在 `__builtin_clzl` 中提及若傳入值為 0 是未定義的情況，因此若傳入值為 0 則直接回傳 1 。
#### 3.當上述 `clz` 內建函式已運用時，編譯器能否產生對應的 `x86` 指令？
在linux系統編輯 `test.c` 透過gcc確定可編譯後，執行 `cc -O2 -std=c99 -S test.c` ，此時會產生出test.s檔，打開便可看到對應的 x86 指令如下：
```
next_pow2:
.LFB13:
.cfi_startproc
endbr64
movl $1, %eax
testq %rdi, %rdi
je .L1
bsrq %rdi, %rdi
movl $64, %ecx
xorq $63, %rdi
subl %edi, %ecx
sall %cl, %eax
cltq
```
:::warning
1. 在 Linux 核心原始程式碼找出類似的使用案例並解釋
:::
## 測驗 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;
}
```
### 延伸問題
1. 解釋上述程式碼運作原理
1. 嘗試使用 `__builtin_{clz,ctz,ffs}` 改寫，並改進 mod $10^9+7$ 的運算
#### 1.解釋上述程式碼運作原理
本程式碼目標為給定一整數 $n$ ，回傳將 1 到 $n$ 的二進位表示法依序串接在一起所得到的二進位字串，其所代表的十進位數字 mod $10^9+7$ 之值。
使用 `len` 紀錄數字的長度，由於若遇到 2 的冪值，2進位的數字長度會加 1 ，因此此處判斷 `i` 及 `i-1` 經過 `AND` 運算的值是否等於0。例如：
:::info
該數非2的冪值：
5 -> 0101
4 -> 0100
`AND`運算後為0100 並非為0，則 5 非 2 的冪值。
該數為2的冪值：
4 -> 0100
4 -> 0011
`AND`運算後為0000 為0，則 4 為 2 的冪值。
:::
因此若是 `AND` 運算後為0，此數即為 2 的冪值，將 `len` 值+1。
最後再將 `ans` 向左位移 `len` 數的位元並與 `i` 做 `OR` 運算，實現將數字的二進位串接在一起的功能。每次進行 `OR` 運算後再mod $10^9+7$。最後回傳 `ans` 值。
#### 2.嘗試使用 `__builtin_{clz,ctz,ffs}` 改寫，並改進 mod $10^9+7$ 的運算
```c
int concatenatedBinary(int n)
{
const int M = 1e9 + 7;
int len = 0;
long ans = 0;
for (int i = 1; i <= n; i++) {
len = 64 - __builtin_clzl(i);
ans = (i | (ans << len)) % M;
}
return ans;
}
```
使用第一題使用過的 `__builtin_clzl` 函式來獲得輸入值 `n` 的二進位最高位元位置，代表整串二進位長度，其他與題目程式碼無異。
:::warning
改進 mod $10^9+7$ 的運算
:::
## 測驗 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 << 3) * (len / 8) - count;
count += (len & 7) ? count_utf8((const char *) end, len & 7) : 0;
return count;
}
```
### 延伸問題
1. 解釋上述程式碼運作原理，比較 SWAR 和原本的實作效能落差
1. 在 Linux 核心原始程式碼找出 UTF-8 和 Unicode 相關字串處理的程式碼，探討其原理，並指出可能的改進空間
#### 1.解釋上述程式碼運作原理，比較 SWAR 和原本的實作效能落差
本程式透過 SWAR 技巧來計算輸入一 UTF-8 字串中的Unicode數量。
首先將傳入的 `buf` 轉換成 `uint64_t` 的形式，並且設變數 `end` 指向 64 bits 中的最後一位數，以便接下來的迴圈有終止點。
接下來設定迴圈，一次8個 bytes 來做檢查。目標為找出最高2個位元設定為 `10` 的**後續位元組**。
```c
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);
}
```
1.此處與原題目相同，假設 `t0` 為：
```c
t0 = [00xx.xxxx|01xx.xxxx|10xx.xxxx|11xx.xxxx]
^^^^^^^^^
*continuation bytes*
```
2.反轉位元：
```c
t1 = ~t0;
t0 = [00xx.xxxx|01xx.xxxx|10xx.xxxx|11xx.xxxx]
t1 = [11xx.xxxx|10xx.xxxx|01xx.xxxx|00xx.xxxx]
```
3.透過與 0x40404040 進行 `AND` 運算來隔離反向的第六個位元。
```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.進行 `not bit6 and bit7`
```c
t4 = t0 & t3;
t4 = [0000.0000|0000.0000|1000.0000|0000.0000]
```
此時可以發現，只剩下第三個位元組有數字。
6.使用函式 `__builtin_popcountll` 來計算1的數量。
```c
count += __builtin_popcountll(t4);
count = 1;
```
此時計數器 count 即為後續位元組的數量。
## 測驗 4
### 題目程式碼
```c
bool is_pattern(uint16_t x)
{
const uint16_t n = -x;
return (n ^ x) < x;
}
```
### 延伸問題
1. 解釋上述程式碼運作原理
1. 在 Linux 核心原始程式碼找出上述 bitmask 及產生器，探討應用範疇
#### 1.解釋上述程式碼運作原理
此程式碼目標為判別目標數在二進位下是否符合某些條件。
```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;
}
```
從題目第一個程式碼中可以推測出，條件為判斷此二進位是否符合 "從LSB 到RSB 中間是否都為 1"
舉例來說：
:::info
十六進位 -> 二進位
符合：
8000 -> 1000000000000000(從 LSB 至 RSB 皆為 1)
FFF0 -> 1111111111110000(從 LSB 至 RSB 皆為 1)
不符合：
8001 -> 1000000000000001
:::
因此精簡後的程式先設16位元變數 `n` 等於 `-x` ，也就是對 `x` 取負值，並且透過與原 `x` 進行 `XOR` 運算，若此數滿足以上條件，則其與原 `x` 做 `XOR` 運算其值必小於 `x` 。
舉例來說：
以 FFF0 (16進位)為例， `x = 1111111111110000` 取負號後即對二進位每個位元反轉後加一， `n = 0000000000010000` ，此數與原 `x` 進行 `XOR` 運算後為 `1111111111100000` ，此數比原本的 `x` 小，故 FFF0 為符合規定的數。
再舉 FFF1 (16進位)為例，`x = 1111111111110001` 取負號後即對二進位每個位元反轉後加一，`n = 0000000000001111` ，此數與原 `x` 進行 `XOR` 運算後為 `1111111111111110` ，此數比原本的 `x` 大，故 FFF1 為不符合規定的數。
#### 在 Linux 核心原始程式碼找出上述 bitmask 及產生器，探討應用範疇
Sign in with Wallet
Connect another wallet