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

:::danger
注意作答規範！
:notes: jserv
:::

## 第一題
### 解釋上述程式碼原理，並用 `__builtin_clzl` 改寫
`pow2(uint8_t e) { return ((uint64_t)1) << e; }`
接收一個 uint8_t 格式的參數 e，回傳 2 的 e 次方的結果，以 uint64_t 格式儲存。
將整數 1 轉換為 uint64_t 格式，
並且位移 e 位，即為2^e。

接下來這段程式透過二分查找法，來找出比 x 大的最小的 2 的次方數。
分為以下幾個步驟:
1.lo = 0 ， hi = 63 ，表示我們的範圍是[0:63]，
2.使用 while 進行搜索，使得 lo == hi
3.每次回圈之中，計算 test 為 lo 和 hi 的平均值，用來檢查 x 是否介於 2^test 和 2^(test+1) 之間。如果是，則回傳 2^test；如果 x 小於 2^test，則更新 hi 為 test；如果 x 大於 2^test，則更新 lo 為 test+1。
4.如果二分查找仍然沒有找到，回傳 2^lo。

### 我的作法:使用 `__builtin_clz()` 來改寫:
首先，我來解釋一下 `__builtin_clz()` 的用法，
假如說我們的輸入值為 11 而且為 32 位元，
我們會獲得`0000 0000 0000 0000 0000 0000 0000 1011`
所得的數值為 28，我們便獲取 $32 - 28 = 4$，而我們的需求為 5，
由此可知我們的實作需要如下:

64 - __builtin_clz() + 1 = ans

uint64_t next_pow2(uint64_t x)
{
    uint8_t stable = 64;
    if (!x)
        return NULL;
    uint8_t input = __builtin_clz(x);
    uint8_t t = stable - input;
    t = t++;
    return 1 << t;
}

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

:::danger
改進漢語書寫！
:notes: jserv
:::

因為我對 RISC-V 很有興趣，因此我想要探究相關的東西，
我查看了虛擬記憶體相關的代碼，
因為他們需要對整數進行操作，
因此使用 `__builtin_clz()` 函式可以幫助計算整數的位數。
我們看到 `arch/riscv/mm/pgtable.c` 之中的一些案例，
如 `pgd_index(), pmd_index(), pte_index()` 等，
都使用了 `__builtin_clz()` 函式來計算整數的位數。

pte_t *pte_alloc_one_kernel(struct mm_struct *mm, unsigned long address)
{
    pte_t *pte = NULL;

    if (!pmd_alloc_one_kernel(mm, address))
        return NULL;

    pte = (pte_t *)__get_free_page(GFP_KERNEL | __GFP_ZERO);
    if (!pte)
        goto out_free_pmd;

    return pte;

out_free_pmd:
    pmd_free_one_kernel(mm, address);
    return NULL;
}

而之所以適合這樣應用，是因為 RISC-V 有一道 CLZ 指令（Count Leading Zeros），我們可以很輕鬆的用來實作 `__builtin_clz()`。
這也是他在 RISC-V 上面特有的優勢，可以提高系統的性能和效率。
這段程式碼呼叫 `pmd_alloc_one_kernel()` 函式以配置頁中介目錄（PMD）和 `__get_free_page()` 函式來配置一個頁框（page frame）來實現的。
如果配置失敗，則會在必要時釋放之前配置的資源，然後返回NULL以表示失敗。

:::danger
註明在哪個 RISC-V extension 存在此指令，並說明其行為。
:notes: jserv
:::

而我在 RISC-V 的平台測試之後，發現了一個很有趣的現象。
當我們在 RISC-V 平台輸入 `__builtin_clz(0)` 時呢，我發現我會獲得 -1 作為 return。
<s>原因我會理解後補充。</s>

## 當上述 clz 內建函式已運用時，編譯器能否產生對應的 x86 指令？
可以，再經由我使用 X86 的 BSR 指令(相當於上述所言的 clz 指令)，

unsigned int clz(unsigned int x) {
    unsigned int leading_zero_count;
    __asm__("bsr %1, %0\n\t"
            "cmpl $31, %0\n\t"
            "je 1f\n\t"
            "xorl $31, %0\n\t"
            "subl %0, $31\n\t"
            "jmp 2f\n\t"
            "1:xorl %0, %0\n\t"
            "2:"
            : "=r" (leading_zero_count)
            : "r" (x)
            : "cc");
    return leading_zero_count;
}

接下來解釋這段程式碼：使用 `bsr` 指令，尋找最高位元的位置，再用 `cmpl` 尋找目標與 31 的大小關係:
* 若相等，則表示該數為 0，跳躍到標號 `1` 所在的指令，將前導 0 的數量設定 32
* 若該位置小於 31，則用 `xorl` 和 `subl` 指令計算前導 0 的數量，並跳躍到標號 2 所在的指令，隨後返回
* 若該位置為 31，則用 xorl 指令將前導 0 的數量設定為 0，並跳躍到標號 2 所在的指令，隨後返回結果

指定使用輸出約束 `"=r" (leading_zero_count)` 和輸入約束 `"r" (x)`，將輸出和輸入參數傳遞給組合語言區塊，同時使用 `"cc"` 約束。

:::danger
注意作答規範：中英文間用一個半形空白字元區隔，使用繁體中文用語。
> 參見 [資訊科技詞彙翻譯](https://hackmd.io/@sysprog/it-vocabulary)
:notes: jserv
:::

---

## 第二題
### 解釋上述程式碼運作原理

看到這個程式碼，
首先，去掉 i 的二進位表示中最右邊的1，
接下來，如果去掉 1 之後等於0，表示 i 是 2 的冪 <s>次方</s>，
由於 2 的冪 <s>次方</s>在二進位系統下只有一位是 1，所以可以增加位移的位數。

if (!(i & (i - 1))) 
    len++;

上面這段是將i和答案進行位移和二進位的或運算，
可以將i的二進位表示接到答案的二進位表示的末尾。

`ans << len` 是把已經處理過的整數的二進位表示向左位移 len 位元，因為在前面的整數中加入了 len 位元二進位位。
`i | (ans << len)` 是把當前的整數 i 的二進位表示，按位或上已經處理完的整數的二進位表示的末尾，這樣可以把當前整數的二進位表示接在已處理完的整數的二進位表示的末尾。
`% M `是防止最終的二進位結果太大而溢位。

### 嘗試使用 `__builtin_{clz,ctz,ffs}` 改寫

int concatenatedBinary(int n)
{
    const int MOD = 1e9 + 7;
    long ans = 1;
    int stable = 64;
    for (int i = 1; i <= n; i++){
        int leading_zeros = __builtin_clz(i + 1);//探索我們要位移多少位元給下個數值
        int mov = stable - leading_zeros;//64-下一個數字的最高位元 = 我們需要留的空間
        ans = ans << mov;
        ans = (i | ans) % MOD;
    }
    return ans;
}

:::warning
改進 `% (1e9 + 7)` 的運算，避免使用 modulo
:notes: jserv
:::

---

## 第三題
### 解釋上述程式碼運作原理，比較 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 << 3) * (len / 8)  - count;
    count += (len & 7) ? count_utf8((const char *) end, len & 7) : 0;

    return count;
}

` const uint64_t *qword = (const uint64_t *) buf;`
將 qword 訂為 buf 的 uint64_t 指標類型，
並且將我們的 len 除以8 (右移3位)因為每次我們可以處理 64 bit，
其餘不完整的部分，我們會進行一次額外的處理
迴圈之中:
從 qword 開始到 end 結束。在每一次迴圈中，首先讀取 qword 指標所指向的 uint64_t 變數，並指定其內含值到 `t0`。
:::warning
注意 "assign" 的翻譯和用法。
:notes: jserv
:::

接下來，將 t0 按位取反值，並將結果給 t1。
將 t1 和一個十六進位常數 `0x04040404040404040llu` 進行按位與運算，並將結果指派到 t2。
將 t2 乘以 2，並將結果給 t3。
最後將 t0 和 t3 進行 bitwise-AND 運算，並將結果指派到 t4。
呼叫 `__builtin_popcountll` 內建函式來計算 t4 中有多少個位是 1 ，並將結果加到 count 中。
最後我們來計算計算 `(1 << 3) * (len / 8) - count`
`(1 << 3) * (len / 8)` 計算出來的結果就是 len 位元組數中完整的 UTF-8 字元數量，
最終我們得到不完整的字數，`(len & 7)` 計算出來的是 len 位元組數中不足一個 UTF-8 字元的剩餘位元組數。
最終的 count 即是這個字串中的 UTF-8 字數。

### 在 Linux 核心原始程式碼找出 UTF-8 和 Unicode 相關字串處理的程式碼，探討其原理，並指出可能的改進空間
[utf8-core.c](https://github.com/torvalds/linux/blob/master/fs/unicode/utf8-core.c)

static int udf_uni2char_utf8(wchar_t uni,
			     unsigned char *out,
			     int boundlen)
{
	int u_len = 0;

	if (boundlen <= 0)
		return -ENAMETOOLONG;

	if (uni < 0x80) {
		out[u_len++] = (unsigned char)uni;
	} else if (uni < 0x800) {
		if (boundlen < 2)
			return -ENAMETOOLONG;
		out[u_len++] = (unsigned char)(0xc0 | (uni >> 6));
		out[u_len++] = (unsigned char)(0x80 | (uni & 0x3f));
	} else {
		if (boundlen < 3)
			return -ENAMETOOLONG;
		out[u_len++] = (unsigned char)(0xe0 | (uni >> 12));
		out[u_len++] = (unsigned char)(0x80 | ((uni >> 6) & 0x3f));
		out[u_len++] = (unsigned char)(0x80 | (uni & 0x3f));
	}
	return u_len;
}

我想研究這一段
這是一個用於將Unicode轉換為UTF-8編碼的函數。
<s>我在思考如何改寫他()</s>
以下是我的改寫，我使用了三元運算子來代替 if/else 的部分(我想討論的事情是，如果我們使用 if/else，在我們將 C 語言轉譯為組合語言時，一定會用到 branch，這樣是否會浪費我們的 cycles 去做預測，以致必定會沖刷掉一些 cycle?)

static int udf_uni2char_utf8(wchar_t uni,
			     unsigned char *out,
			     int boundlen)
{
    int u_len = 0;  
    int need_bits = (uni < 0x80) ? 1 : ((uni < 0x800) ? 2 : 3);
    int en = (boundlen == 0 || (boundlen < 1 && need_bits == 1) || (need_bits == 3 && boundlen < 3) || (need_bits == 2 && boundlen < 2)) ? 0 : 1; 
    int t = need_bits * en;//我在此的想法是，只要 en 不允許就可以直接 return -ENAMETOOLONG
      switch(t){
        case(0):
            return -ENAMETOOLONG;
            break;
        case(1):
            out[u_len++] = (unsigned char)uni;
            break;
        case(2):
            out[u_len++] = (unsigned char)(0xc0 | (uni >> 6));
		    out[u_len++] = (unsigned char)(0x80 | (uni & 0x3f));
            break;
        case(3):
            out[u_len++] = (unsigned char)(0xe0 | (uni >> 12));
		    out[u_len++] = (unsigned char)(0x80 | ((uni >> 6) & 0x3f));
		    out[u_len++] = (unsigned char)(0x80 | (uni & 0x3f));
            break;
      }
      return u_len;
}

:::warning
用 `gcc -S` 觀察上方程式碼對應的組合語言輸出，推測其效益。
:notes: jserv
:::

---

## 第四題
### 解釋上述程式碼運作原理
這段程式在判斷
如果 x 為 `1000000000000000`為 false，
而 x = `1110000000000000` 時，則為TRUE
要進行填補下面程式的空缺時
我們要判斷一個輸入數字的最高位元以及至少下一個位元皆為1，且到最低位元之中，不得有任何一個0，
我一開始想到的方法，是利用上述的幾個 `__builtin`函式來解決問題，
直到我在看到下方的程式碼時，才開始思考要如何利用 x 本身來進行判斷，
我開始想到的是利用類似全為1的16位元作為 MASK ，但是我試了很久，還是沒有成功，
因此我想了，如果我們先做NOT運算，便會得到一個完全相反的數字，我們先預設 x 的輸入是符合的，因此，如果做 NOT x ，我們可以透過尾端的連續0所轉換出來的1，只要將其 + 1，便可還原出原本的樣子，並且利用連續的 1 所轉換出來的 0 ，
因為不斷的進位直至遇到0，便可還原出，最低的位元的1，
這時只要進行 XOR，我們便可以保留前面連續的 1，
並且去除最後的 1，以達到小一位的數字，
但是!
如果出現不符合的情況，中斷出來的0，會因為沒有被還原到( + 1 是為了還原尾巴上的 0 )，
進而將原本的 0 改為 1，
足以將處理後的數字不符合 < x 的條件(因為中斷的0被改為1了，雖然犧牲了一個末尾，但是我們填上了其他空缺的位置)。
回傳 false。
也就是說，這個程式碼最重要的觀念在於，利用進未來還原一些原本的數字!
這樣給了我一個啟發，他是否可以用來填補一些缺失的 0 ，或是用來銷毀一些數據(?
畢竟他強制還原了很多 1 。

bool is_pattern(uint16_t x)
{
    const uint16_t n = ~x + 1;
    return (n ^ x) < x;
}

### 在 Linux 核心原始程式碼找出上述 bitmask 及產生器，探討應用範疇
在` arch/riscv/kernel/traps.c` 中，`is_trap()` 和 `is_interrupt()` 函式使用位元遮罩來解析 CPU 異常和中斷的編號。

static inline bool is_trap(int cause, int sig)
{
    /*
     * Synchronous exceptions (with error codes) and interrupts (without)
     * have different code assignments.  In addition, interrupt numbers
     * overlap the low-numbered synchronous exceptions.
     *
     * |Interrupt | Exception | Name             |
     * |----------|-----------|-----------------|
     * | 0        |           | user software   |
     * | 1        |           | supervisor SW   |
     * | 2        | 0         | machine timer   |
     * | 3        | 1         | machine software|
     * | 4        | 2         | machine external|
     * | 5        | 3         | instruction page|
     * | 6        | 4         | load page       |
     * | 7        | 5         | store page      |
     * |          | 6         | illegal insn    |
     * |          | 7         | breakpoint      |
     * |          | 8         | misaligned insn |
     * |          | 9         | load access     |
     * |          | 10        | store access    |
     */

    switch (cause) {
    case CAUSE_MISALIGNED_FETCH:
    case CAUSE_FETCH_ACCESS:
    case CAUSE_ILLEGAL_INSTRUCTION:
    case CAUSE_BREAKPOINT:
    case CAUSE_MISALIGNED_LOAD:
    case CAUSE_LOAD_ACCESS:
    case CAUSE_MISALIGNED_STORE:
    case CAUSE_STORE_ACCESS:
        return (cause == (sig << 1));

    case CAUSE_USER_ECALL:
    case CAUSE_SUPERVISOR_ECALL:
        return (cause == (sig << 1) + 1);

    default:
        return false;
    }
}

在這個程式碼中，cause 是 CPU 異常的編號，sig 則是異常或中斷的種類。
程式碼使用位元遮罩將 cause 的低位右移 1 位元（等同除以 2），
然後比較結果是否等於 sig，來判斷異常或中斷的種類是否符合。