# 2023q1 Homework2 (quiz2)
contributed by <`ctfish7063`>
### 測驗`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`: 8
`BBBB`: 32
`CCCC`: x+1
#### 延伸問題
1. 解釋上述程式碼原理，並用 `__builtin_clzl` 改寫
原理是將最前面的 set bit 後的每個 bit 都 set，將其加上 1 之後就可以將第一個 set bit 的前一個bit set，並把剩下的 unset。
使用`__builtin_clzl` 取得第一個 set bit 之前 unset bit 的數量，計算出第一個 set bit 的位置後將 1 左移那個位置 +1 ，非常直觀。
```c
uint64_t next_pow2(uint64_t x)
{
return 1 << 64 - __builtin_clz(x);
}
```
2. 在 Linux 核心原始程式碼找出類似的使用案例並解釋
::: success
TODO
:::
3. 當上述 clz 內建函式已運用時，編譯器能否產生對應的 x86 指令？
執行 `cc -O2 -std=c99 -S test.c` 來查看assembly code
```shell=
$ cat test.s
.file "test.c"
.text
.p2align 4
.globl next_pow2
.type next_pow2, @function
next_pow2:
.LFB13:
.cfi_startproc
endbr64
bsrl %edi, %edi
movl $64, %ecx
movl $1, %eax
xorl $31, %edi
subl %edi, %ecx
sall %cl, %eax
ret
.cfi_endproc
.LFE13:
.size next_pow2, .-next_pow2
.section .rodata.str1.1,"aMS",@progbits,1
.LC0:
.string "Hello world"
.LC1:
.string "\npow2:%i"
.section .text.startup,"ax",@progbits
.p2align 4
.globl main
.type main, @function
```
第 11 行可以看到 bsrl，表示 bit scan reverse (BSR)，而 edi 是所使用的 register
### 測驗`2`
參考 [1680. Concatenation of Consecutive Binary Numbers](https://leetcode.com/problems/concatenation-of-consecutive-binary-numbers/)
```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`: i >> len == 0
`EEEE`: ans << len
#### 延伸問題
1. 解釋上述程式碼運作原理
在 for (1~n) 迴圈中，使用 `DDDD` 的判斷式來判斷是否更新 bit 的長度(len)，並在每迭代過一個數字後將 ans 的數字右移(`EEEE`)以產生長度 len 的 unset bit 來儲存此次的數值（和 ans 做 or 運算）。
2. 嘗試使用 `__builtin_{clz,ctz,ffs}` 改寫，並改進 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++) {
if (len < 32 - __builtin_clz(i)) len++;
ans = (i | (ans << len)) % M;
}
return ans;
}
```
可以將第8行原本 `DDDD` 的判斷條件改為由 32- leading zero的數量判斷
:::success
TODO: mod 優化部份
:::
### 測驗`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;
}
```
`AAAA`: 3
`BBBB`: 7
`CCCC`: 7
`DDDD`: 0
#### 延伸問題
1. 解釋上述程式碼運作原理，比較 SWAR 和原本的實作效能落差
SWAR 版首先將 8 個 byte 放入 64 bit 的空間，之後計算此 64 bits 中後續位元組(continuation byte(s)) 的數量。由於 utf-8 中的後續位元組皆有 `1 0` 前綴，我們可以藉由計算符合`not 6th bit and 7th bit` 的 byte 數量後將總 byte 數減去該數量來得到總字元數，剩餘湊不滿 8 個得 byte 的再以前述 `count_utf8` 計算。此方法一次將可以計算 64 bit ，相較於 `count_utf8` 一次計算 8 個 bit(一個 char 的大小)快上不少。
由上面的運作原理看來，經過 swar 最佳化的版本可以比原本的版本快上8倍。我利用 `clock()`函數做了個實驗，測試程式如下，將檔案路徑傳入後即可計算檔案中的檔案中字數和比較兩種方法所耗費的時間
```clike
#define max = 1000000
float clockit(size_t (*func)(const char *, size_t),
const char *buf, size_t len, size_t *ans)
{
clock_t start = clock();
*ans = func(buf, len);
clock_t end = clock();
return ((float) (end - start));
}
int main(int argc, char **argv)
{
if (argc < 2) {
printf("input file name\n");
return -1;
}
FILE *fp = fopen(argv[1], "r");
if (!fp) {
printf("file not found\n");
return -1;
} else {
char buf[max];
fgets(buf, max, fp);
int len = strlen(buf) + 1;
size_t ans_c, ans_s;
float time_c = clockit(count_utf8, buf, len, &ans_c);
float time_s = clockit(swar_count_utf8, buf, len, &ans_s);
printf("Word Count\noriginal:%li,swar:%li\n", ans_c, ans_s);
printf("Time Taken (sec)\noriginal: %f, swar: %f\n",
time_c / CLOCKS_PER_SEC, time_s / CLOCKS_PER_SEC);
printf("swar is %f times faster than original\n", time_c / time_s);
fclose(fp);
}
return 0;
}
```
這裡我使用了兩種輸入，分別是夏目漱石的 [《こころ》](https://www.aozora.gr.jp/cards/000148/files/773_14560.html) 的其中一段以及泰戈爾的[《生如夏花》](https://dianeher.pixnet.net/blog/post/298555576-%E3%80%90%E4%BD%BF%E7%94%9F%E5%A6%82%E5%A4%8F%E8%8A%B1%E4%B9%8B%E7%B5%A2%E7%88%9B%EF%BC%8C%E6%AD%BB%E5%A6%82%E7%A7%8B%E8%91%89%E4%B9%8B%E9%9D%9C%E7%BE%8E%E3%80%91%EF%BD%9E%E6%B3%B0)中的中英對照名句，以下是參考輸出：
```shell
$ ./count kokoro.txt
Word Count
original:1501,swar:1501
Time Taken (sec)
original: 0.000021, swar: 0.000004
swar is 6.000000 times faster than original
$ ./count summerflower.txt
Word Count
original:2566,swar:2566
Time Taken (sec)
original: 0.000019, swar: 0.000003
swar is 6.333333 times faster than original
```
由輸出可以發現實際上並沒有接近 8，而經過實驗後發現每次執行時時間比例也會不同，推測可能的原因在於衡量速度的方式太過粗糙，在 perf 工具中應有更好的衡量方式。
::: success
使用pref進行實驗
:::
2. 在 Linux 核心原始程式碼找出 UTF-8 和 Unicode 相關字串處理的程式碼，探討其原理，並指出可能的改進空間
:::success
TODO
:::
### 測驗`4`
```clike
#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;
}
```
觀察上方函式可以發現輸入 x 只有在變為0時才可以跳出迴圈(x 為 unsigned int)，而 bitmask `0x8000` 代表著 `1000000000000000`， 表示若 x 的 MSB 為 0 會回傳 false，因此符合 pattern 的數字只有從 MSB 開始皆為 set bit 的數字，如下：
```
1000000000000000
1100000000000000
1110000000000000
1111000000000000
.
.
.
1111111111111111
```
#### 改良函式
```clike
bool is_pattern(uint16_t x)
{
const uint16_t n = EEEE;
return (n ^ x) < FFFF;
}
```
`EEEE`: ~x + 1 or -x
`FFFF`: x
#### 延伸問題
1. 解釋上述程式碼運作原理
首先看到上面的數字可以發現一個特點：已最右邊的 set bit (以下稱為 bound) 為界，左邊都是 set bit，右邊則都是 unset bit 。透過 `n = ~x + 1` 可以在進位的 bit 找到 bound
```c
x = 10101100
^ bound
~x = 01010011
^
~x + 1 = 01010100
^
```
而再透過 xor 運算可以發現另一個特點：在 bound 以外的 bit 皆會因為 xor 運算而被 set ，而 bound 則會被 unset:
```c
x = 10101100
^ bound
n = 01010100
^
n ^ x = 11111011
^
```
若是符合上一段所說的 pattern ，經過計算應會比原 `x` 小 1; 否則會比 `x` 來的大，分為兩種情形：
* MSB 並非 set bit -> MSB 經計算後變為 set bit, `n ^ x > x`
* bound 以左不全為 set bit -> 經計算後該 bit 變為 set bit， `n ^ x > x`
因此這段程式碼可以計算同樣的 pattern ，也不會因為 bit 數量而增加迴圈次數減少效能。
另外與 `<yihsuan1011>` 同學討論後發現若 `x` 符合上段所題的 pattern , 則 `n` 會只有一個 set bit， 也就是 `n` 是 2 的冪，所以透過判斷 `n = ~x + 1` 是否是 2 的冪也能夠判斷 `x` 是否符合 pattern 。
```c
x = 11110000
n = 00010000 //n is power of 2
```
若 `n` 為 2 的冪， 則 `n & (n - 1) == 0`，即 `-x & ~x == 0` ，我們可以將函式修改為:
```c
bool is_pattern(uint16_t x)
{
return !(-x & ~x);
}
```
3. 在 Linux 核心原始程式碼找出上述 bitmask 及產生器，探討應用範疇
:::success
TODO
:::
Sign in with Wallet
Connect another wallet