# 2023q1 Homework2 (quiz2)
contributed by < `joshyue` >
## 測驗 `1`
>參照 [你所不知道的 C 語言: bitwise 操作](https://hackmd.io/@sysprog/c-bitwise)，考慮 next_pow2 可針對給定無號 64 位元數值 x，找出最接近且大於等於 2 的冪的值
```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;
}
```
* 64位元之數值`x`，在此以`x = 0b0100 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000`為例。
* 經過7次`x |= x >> 1`運算，可保證原先最高位的1後面會有6個1，即`x = 0b0111 1111 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000`。
* 再經過`x |= x >> 8`、`x |= x >> 32`、`x |= x >> 64`，則`x = 0b0111 1111 1111 1111 1111 1111 1111 1111 1111 1111 1111 1111 1111 1111 1111 1111`，如此便能使一開始最高位的1右邊所有位元皆指派為1。
* 此時`x + 1`才為2的冪，因此最後要`return x + 1`，即能得到`next_pow2`所求。
### 用 __builtin_clzl 改寫
>[__builtin_clzl](https://gcc.gnu.org/onlinedocs/gcc/Other-Builtins.html) : 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)
{
if (！x)
return 1;
int clz = __builtin_clzl(x);
return (1 << (64 - clz));
}
```
* 當`x`不為`0`時，`__builtin_clzl(x)`會回傳最高位開始連續0的個數的功能，假設`x=1024`時，則`clz = 53`。
* 則可以透過求得的`clz`，回傳`(1 << (64 - clz))`，即得題目所求。
### 在 Linux 核心原始程式碼找出類似的使用案例並解釋
* 在<[include/asm-generic/bitops/builtin-fls.h](https://elixir.bootlin.com/linux/latest/source/include/asm-generic/bitops/builtin-fls.h)>中的`fls`函式，有使用到`__builtin_clz`的功能。
```c
static __always_inline int fls(unsigned int x)
{
return x ? sizeof(x) * 8 - __builtin_clz(x) : 0;
}
```
>fls - find last (most-significant) bit set
>
透過`sizeof(x) * 8`可得到`x`的位元數量，再減去最高位開始連續0的個數，則可以得到`fls`函式所求，即最高位元的1的bit index + 1。
### 上述 clz 內建函式已運用時，編譯器產生之對應x86指令
* 執行`cc -O2 -std=c99 -S next_pow2.c`，觀察所得`next_pow2.s`
```c
movl $1, %eax
testq %rdi, %rdi
je .L1
bsrq %rdi, %rdi
movl $64, %ecx
xorq $63, %rdi
subl %edi, %ecx
sall %cl, %eax
cltq
```
* 觀察`__builtin_clzl(x)`所對應的x86指令，其中 `bsrq %rdi, %rdi` 會將最高位的1之bit index儲存於rdi暫存器。
* 而後的 `xorq $63, %rdi` 則是對`63`與最高位的1之bit index作`Exclusive OR`，則等同於`63 - 1之bit index`，因此得到所求，即最高位開始連續0的個數。
---
## 測驗 `2`
>LeetCode [1680. Concatenation of Consecutive Binary Numbers](https://leetcode.com/problems/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;
}
```
* 若要判斷`i`是否為2的冪，現假設`i = 8`，則二進位表示`0b1000`，`i - 1`的二進位表示則為`0b0111`，可觀察到兩者依序對應的bit皆相異，因此當`i`為2的冪時，`i & (i - 1)`必等於0。
* 並且題目所述1 到 n 的二進位表示法依序串接，於是我們可以將目前的字串（`ans`）向左shift所需串接的i之位元長度（`len`）後，再與i作`bitwise OR`，最後再mod $10^9+7$，即為題目所求。
### 使用__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 */
long ans = 0;
for (int i = 1; i <= n; i++) {
int ffs = __builtin_ffsl(i);
if (!(i >> (ffs)))
len++;
ans = (i | (ans << len)) % M;
}
}
```
>[__builtin_ffsl](https://gcc.gnu.org/onlinedocs/gcc/Other-Builtins.html) : Returns one plus the index of the least significant 1-bit of x, or if x is zero, returns zero.
* 原先使用以上的程式碼，以`__builtin_ffsl`來取得最低位開始第一個1的bit index + 1，`i >> (ffs)`若為0，則表示`i`為2的冪，而後發現此程式碼仍可改進，改進如下。
```c
int concatenatedBinary(int n)
{
const int M = 1e9 + 7;
int len = 0; /* the bit length to be shifted */
long ans = 0;
for (int i = 1; i <= n; i++){
ans = (i | (ans << (64 - __builtin_clzl(i)))) % M;
}
}
```
* 以`__builtin_clzl`得到最高位開始連續0個數後，將i往左shift `64 -
__builtin_clzl(i)`(其等同先前的程式碼向左shift `len` )，這樣的改進能省去`if`的分支，不用判斷`i`是否為2的冪，使程式碼更加精簡。
---
## 測驗 `3`
>[SIMD within a register](https://en.wikipedia.org/wiki/SWAR) (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;
}
```
### 比較 SWAR 和原本的實作效能落差
> [__builtin_popcountll](https://gcc.gnu.org/onlinedocs/gcc/Other-Builtins.html) : Returns the number of 1-bits in x.
* 第13行 : 透過`__builtin_popcountll`求得位元組內1的總數，`conut`即代表題目所述continuation bytes（後續位元組）的個數。
* 第16行 : 因為我們在處理一個qword時，qword大小為8byte，`(len / 8)`即表示完整處理的次數(因後續要判斷剩餘未滿1個qword的狀況)，`(1 << 3) * (len / 8)`表示完整處理的次數再乘以8，即已處理字串的長度，並且題目有提到字串長度減去後續位元組，即可確定字元數量，因此我們要再減去第13行得到的`count`，得到字元數量。
* 第17行 : `(len & 7)`等同於`len % 7`，若`len & 7`不為0，表示我們仍有未處理的字元，則呼叫原先的函式`count_utf8`，回傳剩餘的字元數量。
### 在 Linux 核心原始程式碼找出 UTF-8 和 Unicode相關字串處理的程式碼，探討其原理
* 在<[fs/unicode/utf8-core.c](https://elixir.bootlin.com/linux/latest/source/fs/unicode/utf8-core.c#L20)>中，有提供`utf8_strncmp`函式。
* 如果返回值 = 1，則表明兩字串不相等
如果返回值 = 0，則表明兩字串相等
```c
int utf8_strncmp(const struct unicode_map *um,
const struct qstr *s1, const struct qstr *s2)
{
struct utf8cursor cur1, cur2;
int c1, c2;
if (utf8ncursor(&cur1, um, UTF8_NFDI, s1->name, s1->len) < 0)
return -EINVAL;
if (utf8ncursor(&cur2, um, UTF8_NFDI, s2->name, s2->len) < 0)
return -EINVAL;
do {
c1 = utf8byte(&cur1);
c2 = utf8byte(&cur2);
if (c1 < 0 || c2 < 0)
return -EINVAL;
if (c1 != c2)
return 1;
} while (c1);
return 0;
```
* `utf8ncursor`結構表示字串處理的進度，分別透過`c1`及`c2`獲取目前處理字串位置的一個位元組，並轉換此位元組的型態為`unsigned char`，因此若`c1`或`c2`小於0，則表示程式無效，回傳`-EINVAL`，反之的話就是繼續判斷兩個字元是否相等。
---
## 測驗 `4`
>以下程式碼可判定 16 位元無號整數是否符合以下特定樣式 (pattern):
```c
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 = -x;
return (n ^ x) < x;
}
```
* 透過`x`觀察是否符合程式碼的樣式(pattern)可發現，只要`x`在二進位下符合最高位開始為1的條件，後面依序接著連續的1(可為0個)與連續的0(可為0個)，則符合上述的樣式。
* 上述程式碼的`-x`表示`x`的二補數，以下方圖表為例，若x符合樣式，則`(n ^ x)`必定小於`x`，因此回傳`True`。
| x | n = -x | n ^ x |
| -------- | -------- | -------- |
| (1111 0000 0000 0000)~2~ | (0001 0000 0000 0000)~2~ | (1110 0000 0000 0000)~2~ |
| (1111 0100 0000 0000)~2~ | (0000 1100 0000 0000)~2~ | (1111 1000 0000 0000)~2~ |
| (1111 0000 0000 0001)~2~ | (0000 1111 1111 1111)~2~ | (1111 1111 1111 1110)~2~ |
### 在 Linux 核心原始程式碼找出上述 bitmask 及產生器，探討應用範疇
Sign in with Wallet
Connect another wallet