# 2023q1 Homework2 (quiz2)
###### tags: `linux2023`
contributed by < `Paintako` >

## 測驗一

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

原始程式碼是使用了 `binary search` 的概念去找出最接近且大於等於 2 的冪的值

而改寫後的版本：
首先，給的數值範圍是 `64 bit, 且 unsigned`
只要把給的數值的 `MSB` 右邊全部補 1，再 + 1 ，　這樣即可得出最接近且大於等於 2 的冪的值

例如：
數值為 `00001001`，MSB 之後補 1 後變成 `00001111`，最後 + 1 得 `00010000`
但是，如果情況變成原本的數值等於 2 的冪的值，則會得到比正確答案還大的數值
例如：
數值為 `00001000`，MSB 之後補 1 後變成 `00001111`，最後 + 1 得 `00010000`

所以針對以上情況，要結束前需要對原本的數值作 `XOR` 確保原本數值是 2 的冪的值的情形
例如：
數值為 `00001000`，MSB 之後補 1 後變成 `00001111`
和原本的數值做 `XOR`， ` 00001000 ^ 00001111` 所以答案變成 `00000111`，故 +1 仍然是正確答案！
經 [paulpeng](https://hackmd.io/@normal) 提醒後，仍然需要一個 `if` 來判斷原本數值是否 2 的冪的值的情形，依舊會有一個 branch 的 overhead

程式碼應該改寫成：

uint64_t next_pow2(uint64_t x)
{
    uint64_t y = x;
    y |= y >> 1;
    y |= y >> 1;
    y |= y >> 1;
    y |= y >> 1;
    y |= y >> 1;
    y |= y >> 1;
    y |= y >> 1;
    y |= y >> 8;
    y |= y >> 16;
    y |= y >> 32;
    return x%y==0?y+1:(y^x)+1; // if x%y==0 return y+1, else return (y^x)+1
}

為了解決這個 branch 的 overhead，可以把原本數值 -1 使得原本等於 2 的冪的數值不等於 2 的冪，解決了這個不必要的 branch

uint64_t next_pow2(uint64_t x)
{
    uint64_t y = x-1;
    y |= y >> 1;
    y |= y >> 1;
    y |= y >> 1;
    y |= y >> 1;
    y |= y >> 1;
    y |= y >> 1;
    y |= y >> 1;
    y |= y >> 8;
    y |= y >> 16;
    y |= y >> 32;
    return y + 1 ;
}

延伸問題：

使用 ` __builtin_clzl ` 改寫
此函式返回 `leading 0-bits in x` ， 得知 `leading 0` 的數量後, 將 `64 - leading 0-bits數` 算出後再對1做算數位移，即可得此數最接近且大於等於 2 的冪的值

但同樣需要考慮此數原本就是 2 的冪的情況，如果算出的大於等於 2 的冪的值 % 原本的值 ＝0 的話代表此數原本就是 2 的冪

uint64_t func(uint64_t x)
{
    int lead_zero = __builtin_clz(x);
    int cmp = 1<<(64-lead_zero); 
    
    if ((cmp%x) != 0 ) 
        return cmp;
    return x;
} 

在 Linux 核心原始程式碼找出類似的使用案例並解釋
使用 `$ grep -r "<<" ./include/linux/ ` 來找出相似程式碼

有一個看起來也是跟數字處理相關的案例 `./include/linux/log2.h`

[#define const_ilog2(n)](https://github.com/torvalds/linux/blob/master/include/linux/log2.h#L77)

:::warning
這是一個定義了常數log2的C程式碼的巨集(macro)。對於給定的正整數 n，該 define 返回最大的 k，使得 2^k ≤ n，即 2 的 k 次冪不超過 n。

這個 define 使用了GCC inline function __builtin_constant_p(n) ，該函數在編譯時會計算是否為常數，如果是，則返回 true，否則返回 false。 如果 n 是一個常量，那麼 define 使用二進制運算來快速找到最大的 k。 如果 n 不是常量，則使用逐位檢查的方法來找到 k。

From Chatgpt
:::

## 測驗二
原本的程式碼中已經有提示了，如果這個數字是 2 的冪的話，則 `len++`, 此 len 表示 `ans` 的位移量

例如：
| n| 2 的冪 | len | rst |
| ----- | ------ | --- | --- |
|1 | yes | 1 | 1 |
|2 | yes | 2 | 101 |
|3 | no | 2 | 10111 |
|4 | yes | 3 | 101110100 |

開發過程中，原本的程式碼如下：

if (!(i & (i-1)))
            len++;
        ans = (i | (ans<<(len)+1)) % M;

其中 `i & (i-1）` 用於判斷此數是否是 2 的冪
但是這是錯的！ 因為忘記了其實 1 也是 2 的冪（$2^0$)，原本的寫法中忘記了這點才 + 1 的，故正確的版本如下

if (!(i & (i-1)))
            len++;
        ans = (i | (ans<<(len))) % M;

嘗試使用 `__builtin_{clz,ctz,ffs}` 改寫
把 `(i & (i-1)` 改成 `(__builtin_ffs(i) == (64 - __builtin_clzl(i))` 即可

但是這樣改寫後會變得比較快嗎？ Todo: 使用 perf 來判斷 cycle數的增減情況

## 測驗三
SIMD: `Single Instruction Multi Data`
指在同個 `clock cycle` 中，同時處理多個向量
例如：

沒有支援 SIMD 執行 $B*=2$, 其中 B 是 1*n 的向量

| Vector B | Clock Cycle 1 | Clock Cycle 2 | Clock Cycle 3 |
| --------- | ------------- | ------------- | ------------- |
| [1,2,3,4] | [2,2,3,4] | [2,4,3,4] | [2,4,6,4] |

有支援 SIMD:

| Vector B | Clock Cycle 1 |
| -------- | ------------- |
| [1,2,3,4] | [2,4,6,8] |

而 SWAR 表示在 `同一個 Register 中做 SIMD`

---

在筆記中的程式碼中，發現了一些可能是白作工的部份

static inline uint64_t bit_compound(uint32_t x, uint32_t y) {
    return ((0L + x) << 32) | ((y + 0L) & (-1L >> 32));
}

這裡的 `(y + 0L) & (-1L >> 32)`
`y + 0L` 還算好理解，要把 y 擴充成 64 bit
但是 `-1L >> 32` 這裡就匪夷所思了，即便 -1L 寫成二進位是 64個 1，對這 64 個 1 做 32次算數位移仍然是 64個 1，而且跟 `y + 0L` 做 and 也是白做工，因為擴充完 32 bit 的 `y+0L` 前半部份也全部都是 0， 0 跟任何東西做 and 都是 0 ，所以應該可以把程式碼改寫成：

static inline uint64_t bit_compound(uint32_t x, uint32_t y) {
    return ((0L + x) << 32) | (y + 0L);
}

---

參考以下程式：

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

這段程式在做的事情是： 找出一個字串中所有合法的 `UTF-8` 字元組
其中， `magic number` 為何是 -65?
因為對應到 ASCII 的規則， 除了首位元組外，後續位元組皆是以 `10xx xxxx` 的形式存在
故只要某一個數字大於 `1011 1111` 的話，那此數必不會是後續位元組，~~而是一個新的 ASCII !~~ （ 不是新的 ASCII， ASCII 的 MSB 皆是 0)

---

使用 `SWAR` 改寫程式碼：
參考小考中的提示，如果某個 byte 可以寫成 `10xx xxxx` 的形式，那此 byte 必是某 ASCII 的後續位元組，並且可以將這種表達方式寫成 `not bit6 and bit7`，也就是第七個 bit 必 1，第六個 bit 必 0，找出所有這種特殊 pattern 的位元組

只保留把每一個 byte 中的 6、7 bit ， 其餘 bit 全部設為 0 ， 再使用 `__builtin_popcount` 即可得答案

也可參考老師上課的說法，"找到 `10` 交接處"

上述方式用 `SWAR` 的方式呈現出來
首先， `qwords` 代表一次讀取的 byte 數，這裡指定 `uint64`，代表一次讀取 `8 byte`，用意是配合 64 bit 系統，當 pointer ++ 時，移動的步伐等於 64 bit，也就是每一次比較的 Byte 數為 8
:::warning
Note: 即便使用者的系統是 32 bit 的系統 ， 仍存在 64 bit 的操作 （ 例如乘法 ）
:::
這邊 `len` 沒有更詳細的說明，只能用推測的，因為是改寫自原本的題目，從下面程式碼來推測，是整個字串的字元組（ Bytes ) 大小

len >> 3 的目的在於把無法湊到 8 個 byte的去除掉（因為無法對它做 64 bit 的運算），故減去，所以 `*end` 代表了傳入的字串有多少的 Byte!

const uint64_t *end = qword + len >> 3;

以上程式碼，根據 C語言規格書 （ from ChatGpt )，得知符號的結合律優先度，故會先做 `加法` 再做 `>>`

`>> 3` 代表以 8 個 byte為單位


每一次都對 64 bit 做 SWAR，結束後統計 1 的個數即可得知這 8 Byte 中包含幾個後續位元組
當傳入的字串長度不是 Byte 的倍數時 （ i.e. 字串 / 8 != 0 )，則需要考慮剩餘的 Byte 中是否含後續位元組

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

首先， `len/8` 代表 "可以完整湊出 8 Bytes的個數"，乘上 8 bit 即可得完整的位元組數，再減去 `continuation byte` 即可得目前合法的 `UTF-8` 數

count += (len & 7) ? count_utf8((const char *) end, len & 7) : 0;

這段 `len & 7` 很好理解，原本剩下的 Byte 數量不足 8，所以跟 7 做 ＆，可以得到剩餘的 Byte數
而後面的 `if/ else` 也很好理解，將剩下的範圍丟入 `count_utf8` 可得後續位元組數量

## 測驗四

:::warning
Note:
x <<= 1 可以寫成 x = x<<1
:::

參考： [TimChen731](https://hackmd.io/@TimChen731/quiz2)

程式碼要的是： 給定一個 pattern ，不斷向右移的過程中如果有符合該 pattern 就 return true
該 pattern 是只有MSB是 1 其餘皆是 0

字串要符合該 pattern ，並且不斷向左移動時不跳出 for 迴圈的話，那此字串必須符合:
MSB是1 且 1 後續不能有 0

先對 x 做 `not`，再 +1 的話，則跟原本的字串做 `xor` 後原本字串中最右邊的 1 會消失
例如：

| 原本 | 11111000 |
| ---------------- | -------- |
| not | 00000111 |
| not+1 | 00001000 |
| 原本 xor (not+1) | 11110000 |

在和原本的字串做比較，如果比較小的話代表它符合此 pattern

| 原本 | 11111010 |
| ---------------- | -------- |
| not | 00000101 |
| not+1 | 00001010 |
| 原本 xor (not+1) | 11110010 |

在和原本的字串做比較，如果比較大的話代表它不符合此 pattern