# 第 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 次做出來的執行時間趨勢
最後一個 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)
Sign in with Wallet
Connect another wallet