---
# System prepended metadata

title: 第 1 週測驗題

---

#  第 1 週測驗題
contributed by < `colinyoyo26` >

### 測驗 `1`

考慮以下 C 程式的 `align4` 巨集的作用是，針對 4-byte alignment，找到給定地址的 round up alignment address。
```cpp=
#include <stdio.h>
#define align4(x) (((x) + K) & (-4))
int main(void) {
    int p = 0x1997;
    printf("align4(p) is %08x\n", align4(p));
    return 0;
}
```
預期程式輸出 `align4(p) is 00001998`

-4 的 16 進位表示為 0xFFFFFFFC (32 bit) 所以 (((x) + K) & (-4)) 剛好可以把 x + K 最後面兩個 bit 去掉

接著考慮以下兩種情況：

    1. x % 4 == 0
     則 (x + 3) & -4 == x   
    2. x % 4 != 0
     則 (x + 3) & -4 == x + (4 - x % 4)
    
經過以上討論可以看出 x + 3 剛好把沒有對齊 4-byte 的數 round up
所以 K = 3
:::success
延伸題目: 在 Linux 核心原始程式碼找出類似的 alignment 巨集並解釋其作用
:::
在[ linux/include/linux/kernel.h ](https://github.com/torvalds/linux/blob/fa121bb3fed6313b1f0af23952301e06cf6d32ed/include/linux/kernel.h)找到以下 macro
```clike
/* @a is a power of 2 value */
#define ALIGN(x, a)		__ALIGN_KERNEL((x), (a))
#define ALIGN_DOWN(x, a)	__ALIGN_KERNEL((x) - ((a) - 1), (a))
```

而 __ALIGN_KERNEL 和 __ALIGN_KERNEL_MASK 定義在 [linux/include/uapi/linux/kernel.h](https://github.com/torvalds/linux/blob/6f0d349d922ba44e4348a17a78ea51b7135965b1/include/uapi/linux/kernel.h)
```clike
#define __ALIGN_KERNEL(x, a)		__ALIGN_KERNEL_MASK(x, (typeof(x))(a) - 1)
#define __ALIGN_KERNEL_MASK(x, mask) (((x) + (mask)) & ~(mask))
```

ALIGN 巨集和測試題目一樣是 round up , a 可以帶入任何 power of 2 的數字

ALIGN_DOWN 先把 x - ((a) - 1) 但是會在 __ALIGN_KERNEL_MASK 加回來，所以等於是直接和 ~(a-1) 做 and 直接 round down



---

### 測驗 `2`

考慮以下 C 程式可取得以 `sizeof(int)` 為 alignment 基礎的整數空間，也就是說，當 `sizeof(int)` 為 `4` 的時候:
* 給定 `char arr[13];`，`INT_SIZE_OF(arr)` 要得到 `16`;
* 給定 `short int s;`，`INT_SIZE_OF(s)` 要得到 `4`

```cpp
#include <stdint.h>
#define INT_SIZE_OF(n) \
    ((sizeof(n) + sizeof(int) + X) & ~(sizeof(int) + Y))
```

了解第一題之後，這題就沒有困難了，後面 and 的地方同理是要把餘數部份去掉， 注意到 mask 的部份第一題的 -4 可以和這題一樣寫成 ~(4 + Y) 的形式
可經由簡單的推導驗證： 
```
    -4 == -(4 - 1) - 1 == ~(4 - 1) + 1 -1 = ~(4 - 1)   
```
而第一題因為要對齊 4-byte 所以把原數字加三，而這題因為要對齊 sizeof(int)-byte 所以要把 sizeof(n) + (sizeof(int) - 1) 進行 round up 的動作

一樣考慮以下兩種情況：

    1. sizeof(n) % sizeof(int) == 0
     則 (sizeof(n) + (sizeof(int) - 1)) & ~(sizeof(int) - 1) == sizeof(n)   
    2. sizeof(n) % sizeof(int) != 0
     則 (sizeof(n) + (sizeof(int) - 1)) & ~(sizeof(int) - 1) == sizeof(n) + (sizeof(int) - sizeof(n) % sizeof(int))   
     
可以得出 X = Y = -1
:::success
延伸題目: 解釋運作原理並在 GitHub 找出實際應用的程式碼
:::
在 [linux/drivers/usb/gadget/u_f.h](https://github.com/torvalds/linux/blob/f90d64483ebd394958841f67f8794ab203b319a7/drivers/usb/gadget/u_f.h) 找到以下 macro 對齊的原理和測驗題一樣
```clike
#define vla_item(groupname, type, name, n) \
	size_t groupname##_##name##__offset = ({			       \
		size_t align_mask = __alignof__(type) - 1;		       \
		size_t offset = (groupname##__next + align_mask) & ~align_mask;\
		size_t size = (n) * sizeof(type);			       \
		groupname##__next = offset + size;			       \
		offset;							       \
})
```

---

### 測驗 `3`

考慮以下 C 程式碼:
```cpp=
#include <stdbool.h>
bool func(unsigned int x) {
    return x && ((x & (~x + 1)) == x);       
}
```

可改寫為以下等價的程式碼:
```cpp=
bool func(unsigned int x) {
    unsigned int unknown = 0;
    while (x && unknown <= 1) {
        if ((x & Z) == 1)
            unknown++;
        x >>= 1;
   }
   return (unknown == 1);
}
```
其中第一部份程式碼的第 3 行可改為以下等價程式碼
```clike
return x && ((x & (-x)) == x); 
```

這樣看就比較直觀了， x 和自己的二補數做 and 運算等於自己只會有「只有一個 bit 是 1」這種可能

接著在看迴圈版本的程式碼
我們直接把 Z 代入 1 ，很明顯當 x 只有一個 bit 是 1 的時候會 return ture ，接著分成兩個 case 討論:

    1. x 超過一個 bit 是 1
        因為 unknown > 1 跳出迴圈，然後 return false
    2. x == 0
        不會進入迴圈 unknown == 0 return false
        
經由以上討論可以得到 Z = 1
:::success
延伸題目: 舉出 abs 以外，透過 bitwise 操作將原有運算改為 const-time 實作的案例，應當解釋並探討應用場景。
:::
population count 簡稱 popcnt

在編碼領域廣泛用到像是計算字串間的 hamming distance 或是 parity code 而編碼用來確保資訊的正確 (e.g. 可以用較少的空間增加 RAID 的 reliability)
:::danger
補上參考資訊和延伸閱讀材料，並且摘要
:notes: jserv
:::

實做方式可以在網路上找到很多種版本，在此針對問題，以最直觀的迴圈版本和其中一個 bitwise 版本比較

首先是 迴圈版本
```cpp
unsigned int countBitsLoop(unsigned int x)
{
    unsigned int result = 0;
    // strip one set bit per iteration
    while (x != 0) {
        x &= x - 1;
        result++;
    }
    return result;
}
```
很明顯有幾個 1 就會跑幾個 iteration <s>感覺起來效能不優</s>，而且隨著數字不同，執行時間也會受影響
:::danger
工程人員不該在推理時憑「感覺」，for iteration 的問題不在於特定輸入的效能不佳，而是對整個有效輸入的操作時間分佈無法收斂
:notes: jserv
:::

再來是 bitwise 版本
```cpp=
unsigned int countBits(unsigned int x)
{
    // count bits of each 2-bit chunk
    x  = x - ((x >> 1) & 0x55555555);
    // count bits of each 4-bit chunk
    x  = (x & 0x33333333) + ((x >> 2) & 0x33333333);
    // count bits of each 8-bit chunk
    x  = x + (x >> 4);
    // mask out junk
    x &= 0xF0F0F0F;
    // add all four 8-bit chunks
    return (x * 0x01010101) >> 24;
}
```
先看到第 4 行，我們先把 32 bits 的資料拆成 16 個 2 bits （以下記作 A）來看，該行運算等同於是 A - A >> 1 因為 0x5 == 0101b （以下就不對 mask 部份贅述了）
可以分成以下四種 case:

    1. A = 00b
        A - A >> 1 = 00b
    2. A = 01b
        A - A >> 1 = 01b
    3. A = 10b
        A - A >> 1 = 01b
    4. A = 11b
        A - A >> 1 = 10b
可以看出計算結果剛好是對每個 A 的 popcnt
這部份可以改為直接相加，<s>個人覺得</s>比較直觀一些（如下）
:::danger
避免用「個人覺得」，你可以說程式碼較短、符合上述分類方式等等。你不會希望 Apple 和 Google 的工程師平常就「憑感覺」做事吧？這樣產生的手機軟體，你敢用嗎？
:notes: jserv
:::
```clike
 x  = (x & 0x55555555) + ((x >> 1) & 0x55555555;
```

再來看到第 6 行，現在把 32 bits 的資料拆成 8 個 4 bits (再分成左右各 2 bits 分別記作 B1 B2)
可以發現該行運算的結果是 B1 + B2 剛好把剛剛第四行的結果相加，所以現在 32 bits 的資料變成 8 個 4 bits 一組的 popcnt

繼續看第 8 行把第 i 堆加到第 i - 1 堆 for all i > 1 (這裡一樣 4 個 bits 一堆)

再來第 10 行做完 and 後第 j 堆的數字剛好是第 j / 2 + 1 byte 的 popcnt for all j belong to odd （共四堆）

最後第 12 行做完乘法，剛好可以把四堆相加的結果存在第 25 個 bit 開始的地方，然後再向右 shift 得到結果

以下是從 1 個 bit 到 32 bits 各跑 50 次做出來的執行時間趨勢
![](https://i.imgur.com/xXyMH59.png)

最後一個 iteration 目前不知為何出現驟降趨勢，若之後發現問題再補上
:::danger
1. 修改 gnuplot，縱軸加上 `ns` 單位;
2. 注意到 for iteration 中的數值分佈，跟中央處理器的 branch prediction 行為的關聯
:notes: jserv
:::
-    先更正一下原本的說法，該圖的趨勢是第 31 個 iteration 突然上升才對，其為 0x7FFFFFFF
-    branch predict 行為關聯還在查證中，先用 perf 比對和第 30 以及 32 個 iteration 比對 branch-misses 和 cycle 數的關聯如下
```
# $ perf stat --repeat 1000 -e branch-misses,cycles

# iteration 31 0x7FFFFFFF
             2,478      branch-misses                                                 ( +-  0.45% )
           529,837      cycles                                                        ( +-  0.47% )
           
# iteration 32 0xFFFFFFFF
             2,398      branch-misses                                                 ( +-  0.36% )
           519,505      cycles                                                        ( +-  0.32% )

# iteration 30 0x3FFFFFFF
             2,364      branch-misses                                                 ( +-  0.36% )
           508,282      cycles                                                        ( +-  0.26% )

```

###     參考資料

[Count bits set in parallel a.k.a. Population Count ](https://bits.stephan-brumme.com/countBits.html)
[C99規格書](http://www.open-std.org/jtc1/sc22/WG14/www/docs/n1256.pdf)
[GNU/Linux 開發工具共筆](https://hackmd.io/@sysprog/rJKbX1pFZ/https%3A%2F%2Fhackmd.io%2Fs%2Fr1Psrf0KW?type=book)