# 2023q1 Homework2 (quiz2)
contributed by < [cin-cout](https://github.com/cin-cout) >
[題目](https://hackmd.io/@sysprog/linux2023-quiz2)

## 測驗一
### 延伸問題:

1. 解釋上述程式碼原理，並用 __builtin_clzl 改寫
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”)

### Question

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

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;
}

要找出最接近且大於等於 2 的冪的值，意思即為其最高位後全部填一後再加一(即進一位)。

以測驗中的例子為例：

x = 0010000000000000
x = 0011000000000000
x = 0011110000000000
x = 0011111111000000
x = 0011111111111111

最後再將 x + 1 ，使其進一位其找出最接近且大於等於 2 的冪的值。
#### AAAA

因為在 AAAA 之前已經右移過 7 次，加上原本就存在的最高位，可以理解為最高位後的 7 位都已經置換為 1 ，加上原本的最高位，最高 8 位已經都為 1 。

接下來就是持續將低位數值換為 1 ，因為已經確定最高 8 位為 1 ，我們可以直接右移 8 位，使 9~16 位為 1 ，最後再將其跟原本的 x or ，使最高位元(含)後 16 位皆為 1 。

故 AAAA 為 8。

#### BBBB

BBBB 也是同樣道理，在 BBBB 之前已經將最高位元(含)後 32 位都改為 1 了。

接下來就是持續將低位數值換為 1 ，因為已經確定最高 32 位為 1 ，我們可以直接右移 32 位，使 33~64 位為 1 ，最後再將其跟原本的 x or ，使最高位元(含)後 64 位皆為 1 ，若最高位後少於 64 位，則會因為右移後，則是將剩餘位元數全改為1，不會對結果產生影響。

故 BBBB 為 32。

#### CCCC

如同前面前面範例所述，此法的最終結果須 + 1 才是正確答案。

故 CCCC 為 x + 1。

### 補充

因為在第一次位移一位時就可以確保數值最高非0位數的後，兩位(含)為 1 了，所以在下次位移可以直接右移 2，以此類推。

故題目程式可改進如下。

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;
}

### Answer
:::success
AAAAA = `8`
BBBB = `32`
CCCC = `x + 1`
:::

## 測驗二
### 延伸問題:
1. 解釋上述程式碼運作原理
2. 嘗試使用 __builtin_{clz,ctz,ffs} 改寫，並改進 mod $10^9+7$的運算

### Question
給定一整數 n ，回傳將 1 到 n 的二進位表示法依序串接在一起所得到的二進位字串，其所代表的十進位數字 mod $10^9+7$ 之值。

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;
}

#### 程式碼解說
整體的邏輯為 1 到 n 一項一項的確認，若數值 2 進位的位數增加了即更新 len，最後在將其接在原本 ans 的後面。

一開始的 for 迴圈為從 1 到 n 一個數字一個數字處理。
##### DDDD
if 是在判斷數值的 2 進位位數是否增加了，位數增加的時機即為數值為 2 冪次的數值。

若 i & (i - 1) == 0 則代表其為 2 冪次，原因如下：
以 4 為例
i = 100
i-1 = 011
i & (i - 1) == 0

可以想像成因為 2 冪次的數值只會有一個 1 ，所以當你減 1 時，結果即為其 1 後面所以位數皆為 1 ，但原本 1 的位變為 0。與原本的 i 做 & 後自然為 0。

題目中註解也是在描述一樣的道理，只是用不同方式切入， i & (i - 1) 本身可以看做將最右邊的 1 後(含)全部換為 0 的運算。

題目在 DDDD 前有個 !，所以就不需要增加 == 0 的條件了。
故 DDDD = i & (i - 1)。

##### EEEE
EEEE 此行的功用只在於把每個數字的結果 1 個 1 個接起來而已，所以即是把 ans<<len 因為要空出新的數值長度的位置，再用 | 將 i 給放入空出來的位置。

EEEE = ans<<len。

### Answer
:::success
DDDD = `i & (i - 1)`
EEEE = `ans<<len`
:::

## 測驗三
### 延伸問題:
1. 解釋上述程式碼運作原理，比較 SWAR 和原本的實作效能落差
2. 在 Linux 核心原始程式碼找出 UTF-8 和 Unicode 相關字串處理的程式碼，探討其原理，並指出可能的改進空間

### Question
SWAR 實作如下:

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;
}

請補完程式碼，使其運作符合預期。

#### 程式碼解說
先儲存 buf 中的前 8 bytes ，而 end 則是用來紀錄最後剩下無法被分成 8 bytes 的頭。算法為 qword + 總共有幾個 8 bytes ， 將 len >> 3 就是除8的意思。

    const uint64_t *qword = (const uint64_t *) buf;
    const uint64_t *end = qword + len >> 3;

for 迴圈就是一個 8 bytes 一個 8 bytes 的做，直到最後剩下的 bytes ，意及剩下無法被分成 8 bytes 的 bytes。

而 for 迴圈中的內容是老師[上課講義](https://hackmd.io/@sysprog/linux2023-quiz2)中的 not 6 and 7 的運算，處理過後總共有幾個 1 就代表有幾個 continuation bytes。

    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_utf8 來計算剩下的 bytes 的非 continuation bytes 數量。

    count = (1 << AAAA) * (len / 8)  - count;
    count += (len & BBBB) ? count_utf8((const char *) end, len & CCCC) : DDDD;

補：count_utf8 函式用來計算剩下的 bytes 的非 continuation bytes 數量，詳細解釋見[上課講義](https://hackmd.io/@sysprog/linux2023-quiz2)。

#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;
}

##### AAAA
因原本的結果為紀錄 continuation bytes 數量，我們要求的是非 continuation bytes 的數量，所以要先將 count 轉換，轉換方法為 `已經計算過的 bytes - continuation bytes 的數量 = 非 continuation bytes 的數量。`

已經計算過的 bytes = 8 * (len / 8)
因為 c 的 len/8 會取 floor ，所以即代表有幾個 8 bytes，最後 x8 就可以知道有幾個 bytes。

count = (1 << AAAA) * (len / 8)  - count;

故 AAAA 為 3。

##### BBBB CCCC DDDD
最後則是將剩下無法分成 8 bytes 的 bytes 做處理，若(len & 0b111)為則代表 len 為 0 ，直接將 count +0 即可。

故 BBBB 為 7 、 DDDD 為 0。

若 len 不為 0，則用原本實做的函式計算剩餘的非 continuation bytes 數量， count_utf8 第二個參數為 bytes 數量，故為 len % 8，意及 len & 0b111。

故 CCCC 為 0。

count += (len & BBBB) ? count_utf8((const char *) end, len & CCCC) : DDDD;

### Answer
:::success
AAAA = `3`
BBBB = `7`
CCCC = `7`
DDDD = `0`
:::

## 測驗四
### 延伸問題:

1. 解釋上述程式碼運作原理
1. 在 Linux 核心原始程式碼找出上述 bitmask 及產生器，探討應用範疇參見 Data Structures in the Linux Kernel

### Question

以下程式碼可判定 16 位元無號整數是否符合特定樣式 (pattern):

#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;
}

改寫上述程式碼，使其達到等價行為，但更精簡有效。

bool is_pattern(uint16_t x)
{
    const uint16_t n = EEEE;
    return (n ^ x) < FFFF;
}

#### 程式碼解說
對於原本的程式碼，符合的結果如下：

1000000000000000
1100000000000000
1110000000000000
.
.
.
1111111111111111

##### EEEE

EEEE 結果為 ~x + 1 原因如下：

~x 會將 0 轉換為 1，1 轉換為 0。
在符合的狀況中，會有以下的結果：
~x 必定為 $0^+1^+$ 的狀態。
~x + 1 會使 1 的部分進位。
~x + 1 必定只會有一個 1 且為原本 x 的 LSB。

在 false 的狀況中，~x + 1 的 LSB 一樣會是 1 ， LSB 之上的 bit 即為原本的 ~x。

##### FFFF

FFFF 結果為 x 原因如下：

(~x + 1 ^ x) 在 true 的狀況中即為 x 將 LSB set 為 0，所以一定會比原本的 x 小，故結果為 true。

而反之在 false 的情況中 (x 的 LSB 之上一定會有 0 )， (~x + 1 ^ x) 的結果同樣會將 x 的 LSB set 為 0，但是因為 ~x + 1 與 x 在 LSB 之上的 bits 會完全相反，所以會全部被 set 為 1 ，所以一定會比原 x 大，故結果為 false 。
### Answer
:::success
EEEE = `~x + 1`
FFFF = `x`
:::