# 2019q3 Homework1 (review)
contributed by < `xl86305955` >
###### tags:`sysprog2019` `Homework1` `Review`
## 2019q3 第 1 週測驗題
### 測驗 `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`
==作答區==
`K` = ?
* `(a)` `(-3)`
* `(b)` `(-2)`
* `(c)` `(-1)`
* `(d)` `(0)`
* `(e)` `(1)`
* `(f)` `(2)`
* `(g)` `(3)`
:::success
延伸題目: 在 Linux 核心原始程式碼找出類似的 alignment 巨集並解釋其作用
:::
----
#### 解答
* 想法
* -4要幹嘛
* 為何是&
* K值為何
##### -4要幹嘛
<s>額，完全沒有頭緒</s>...讓我們先將-4轉為二的補數的表示式看看
:::danger
不要裝可愛，沒有人會同情弱者
:notes: jserv
:::
$-4_{10}$ =$0_xfffc$ =$1111 1111 1111 1100_2$
最後兩 bits 為 0 ， 記憶體位置為 4 的倍數，用二進位表示結尾皆為 00 ！
##### 為何是&
* And 運算具有
* 自己與 0 作用會清成 0
* 自己與 1 作用會得到自己
| x | y | and |
| -------- | -------- | -------- |
| x | 0 | 0 |
| x | 1 | 1 |
```clike=
#define align4(x)(((x) + K) & (-4))
```
在 (x + K) `& (-4)` 中即是扮演著前 14 bits 保持不動，並將最後兩 bits 清除成 0
##### K值為何
本題關鍵，K值到底為何？觀察以下運算：
$4n+1$ , $4n+2$ , $4n+3$ 的第 3 個 bit 會與 $4(n+1)$ 相同。因此：
若 Input 為四的倍數，則 round up 後仍是自己。若 input 不為四的倍數，則 $4n+1$ , $4n+2$ , $4n+3$ 皆會 round up 到同一個位置
綜合上述兩點，$-4$ 與 $&$ 作用，可推敲得知 `K = 3`
#### 延伸題目
:::success
在 Linux 核心原始程式碼找出類似的 alignment 巨集並解釋其作用
:::
知名 linux 開發者 Rusty Russel 於 2007 年在 [LKML.ORG](https://lkml.org/) (Linux Kernel Mailing-List ) 中以 ["Use more gcc extensions in the Linux headers"](https://lkml.org/lkml/2007/3/9/10) 為標題發表 ，以下為內容節錄：
```cpp
diff -r f0ff8138f993 include/linux/kernel.h
--- a/include/linux/kernel.h Fri Mar 09 16:40:25 2007 +1100
+++ b/include/linux/kernel.h Fri Mar 09 16:44:04 2007 +1100
@@ -35,7 +35,9 @@ extern const char linux_proc_banner[];
#define ALIGN(x,a) __ALIGN_MASK(x,(typeof(x))(a)-1)
#define __ALIGN_MASK(x,mask) (((x)+(mask))&~(mask))
-#define ARRAY_SIZE(x) (sizeof(x) / sizeof((x)[0]))
+#define ARRAY_SIZE(arr) (sizeof(arr) / sizeof((arr)[0]) \
+ + sizeof(typeof(int[1 - 2*!!__builtin_types_compatible_p(typeof(arr), \
+ typeof(&arr[0]))]))*0)
#define FIELD_SIZEOF(t, f) (sizeof(((t*)0)->f))
#define DIV_ROUND_UP(n,d) (((n) + (d) - 1) / (d))
#define roundup(x, y) ((((x) + ((y) - 1)) / (y)) * (y)
```
節錄有關 `Alignment` 部分:
```cpp
#define ALIGN(x,a) __ALIGN_MASK(x,(typeof(x))(a)-1)
#define __ALIGN_MASK(x,mask) (((x)+(mask))&~(mask))
```
上面的程式看起來較為複雜，讓我們稍加簡化一下。當呼叫 `ALIGN( x, a )` 時，`ALIGN( x, a )` 要做 `__ALIGN_MASK(x,(typeof(x))(a)-1)` 的動作，其中 `typeof(x)` 將 `a` 強制轉型成與 `x` 同型態。接著不考慮轉換的型態將 `a - 1` 代入 `__ALIGN_MASK(x,mask) (((x)+(mask))&~(mask))` 的 `mask` 中，可得：
```cpp
#define ALIGN( x, a ) ((x + (a) - 1) &~ (a - 1))
```
實測：
```clike
#include <stdio.h>
#define ALIGN(x,a) (((x)+(a)-1)&~((a)-1))
#define SIZE 4
int main(void)
{
for (int i = 0; i <= 10; i++) {
printf("align(%d,%d) = %d\n", i, SIZE, ALIGN(i, SIZE));
}
return 0;
}
```
以 `4` 為單位對齊，編譯並執行：
```
$gcc -o align align.c
$./align
align(0,4) = 0
align(1,4) = 4
align(2,4) = 4
align(3,4) = 4
align(4,4) = 4
align(5,4) = 8
align(6,4) = 8
align(7,4) = 8
align(8,4) = 8
align(9,4) = 12
align(10,4) = 12
```
題外話， Linus Torvalds 稱讚這篇為 `Work of Art` ^ W ^ W ^ W ^ W ^ W ^ W ^ :
```
On Fri, 9 Mar 2007, Rusty Russell wrote:
>
> __builtin_types_compatible_p() has been around since gcc 2.95, and we
> don't use it anywhere. This patch quietly fixes that.
Whee.
Rusty, that's a work of art.
However, I would suggest that you never show it to anybody ever again. I'm
sure that in fifty years, it will be worth much more. So please keep it
tightly under wraps, to keep people from gouging their eyes out^W^W^W^W^W^W^W
make a killing in the art market.
Please.
Linus
```
* 延伸閱讀：[藝術與核心](http://blog.linux.org.tw/~jserv/archives/001888.html)
---
### 測驗 `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))
```
* 參考資訊: [Memory access and alignment](https://lwn.net/Articles/260832/)
==作答區==
`X` = ?
* `(a)` `(-3)`
* `(b)` `(-2)`
* `(c)` `(-1)`
* `(d)` `(0)`
* `(e)` `(1)`
* `(f)` `(2)`
* `(g)` `(3)`
`Y` = ?
* `(a)` `(-3)`
* `(b)` `(-2)`
* `(c)` `(-1)`
* `(d)` `(0)`
* `(e)` `(1)`
* `(f)` `(2)`
* `(g)` `(3)`
:::success
延伸題目: 解釋運作原理並在 GitHub 找出實際應用的程式碼
:::
---
#### 解答
根據上題的洗禮，這題與上題大同小異
```clike=
#include <stdint.h>
#define INT_SIZE_OF(n) \
((sizeof(n) + sizeof(int) + X) & ~(sizeof(int) + Y))
```
讓我們從 `&` 後的 `~(sizeof(int) + Y)`開始。觀察下圖：
首先`sizeof(int)` 為 4 byte 。運用上一題觀念，若要對齊四的倍數，則可與 `-4` 做 $and$ 運算。而 `3` 與 `-4` 正是成互補關係，因此`3`在取$not$後即得`-4`。因次`~(sizeof(int) + Y) = -4 `，`Y = -1 ` 。
`sizeof(n)` 可想成是一個 memory 的位置，接著考慮`sizeof(int) + X`，依據上題經驗，$4n + 1$，$4n + 2$，$4n + 3$皆會 round up 對齊 $4(n +1)$位置， 可得知`sizeof(int) + X = 3`，則 `X = -1`。
---
### 測驗 `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);
}
```
請補完程式。
==作答區==
`Z` = ?
* `(a)` `(-3)`
* `(b)` `(-2)`
* `(c)` `(-1)`
* `(d)` `(0)`
* `(e)` `(1)`
* `(f)` `(2)`
* `(g)` `(3)`
:::success
延伸題目: 舉出 abs 以外，透過 bitwise 操作將原有運算改為 const-time 實作的案例，應當解釋並探討應用場景。
:::
---
#### 解答
```clike=
#include <stdbool.h>
bool func(unsigned int x) {
return x && ((x & (~x + 1)) == x);
}
```
利用 for 迴圈觀察第一段程式碼之 output:
```
當i=0 得 0
當i=1 得 1
當i=2 得 1
當i=3 得 0
當i=4 得 1
當i=5 得 0
當i=6 得 0
當i=7 得 0
當i=8 得 1
當i=9 得 0
當i=10 得 0
Program ended with exit code: 0
```
當 input 等於 `2` 的冪次方時，輸出為 `1`
一頭霧水不知道為什麼，<s>硬爆試試看</s>
:::danger
用精準的詞彙書寫，拒絕成為 Ptt 鄉民口中的「文組」
:notes: jserv
:::
|Operation | 0 |1 |2 |3 |4 |5 |6 |7 |
|-------- | -------- | -------- |-------- |-------- |-------- |-------- |--------|--------|
|x | 0000 | 0001 |0010 |0011 |0100 |0101 |0110 |0111 |
|~x | 1111 | 1110 |1101 |1100 |1011 |1010 |1001 |1000 |
|~x + 1 | 1110 | 1111 |1110 |1101 |1100 |1011 |1010 |1001 |
|x & ( ~x + 1 ) | 0000 | 0001 |0010 |0001 |0100 |0001 |0010 |0001 |
|(x &( ~x + 1)) == x| true | true |true |false |true |false |false |false |
|Operation | 8 |9 |10 |11 |12 |13 |14 |15 |
|-------- | -------- | -------- |-------- |-------- |-------- |-------- |--------|--------|
|x | 1000 | 1001 |1010 |1011 |1100 |1101 |1110 |1111 |
|~x | 0111 | 0110 |0101 |0100 |0011 |0010 |0001 |0000 |
|~x + 1 | 1000 | 0111 |0110 |0101 |0100 |0011 |0010 |0001 |
|x & ( ~x + 1 ) | 1000 | 0001 |0010 |0001 |0100 |0001 |0010 |0001 |
|(x &( ~x + 1)) == x| true | false |false |false |true |false |false |false |
觀察 `x & (~x + 1)` 這行，發現：
* 若為奇數，則輸出為 `1`
* 若為偶數，則輸出 $2^k$ ，其中 $2^k$ 為 `x` 做質因數分解中的最大偶數項
為什麼會出現此現象？我們再將二的次方抓出來看：
| Operation | 1 | 2 | 4 | 8 |
| -------- | -------- | -------- | -------- | -------- |
| x | 0001 | 0010 | 0100 | 1000 |
| ~x | 1110 | 1101 | 1011 | 0111 |
| ~x + 1 | 1111 | 1110 | 1100 | 1000 |
| x & ( ~x + 1 ) | 0001 | 0010 | 0100 | 1000 |
若為二的次方，整個 bit 組中只會有一個 `1` ，其他位元皆為 `0` ，第一個 function 正是抓準這個特性，取 $not$ 再加 `1` 製造出以原先 `1` 作為分界，使得右邊為 `0` ，左邊為 `1` 。再做 $and$ 運算回到原先 input 。因為這個特性，使得輸出可以獲得質因數分解中的最大偶數項 $2^k$ 。
:::danger
用 GraphViz 改寫示意圖
:notes: jserv
:::
了解了第一段程式碼用途後，可以開始解答第二段程式碼：
```clike=
bool func(unsigned int x) {
unsigned int unknown = 0;
while (x && unknown <= 1) {
if ((x & Z) == 1)
unknown++;
x >>= 1;
}
return (unknown == 1);
}
```
由第一段程式碼，已了解二的冪次方在二進位表示法的特性，尤其在首個 `1` 出現前位元值皆為 `0` 。這個特性讓我們可以解答 `Z` 值為何。我們逐行拆解：
* line 3: `while (x && unknown <= 1)`
* 控制 while 迴圈的變數有 `x` 與 `unknown`
* 當 x = 0 時，跳出迴圈
* 當 unknown > 1 時跳出迴圈
* line 4:`if ((x & Z) == 1) unknown++`
* 由上一段程式碼得分析，由於只有二的冪次方才具有首個 `1` 出現前位元值皆為 `0` ，因此在這邊我們每次 loop 只要知道最後一個位元的狀況，並將 unknown 當成一個 counter ，若出現一個以上的 `1` 即可知道輸入並不是二的冪次方。由此可推斷 `Z = 1`
* line 6:`x >>= 1`
* 若 `x` 為二的冪次方，因為在第一個 `1` 出現前皆是 `0` ， `x` 能夠右 shift 許多次且 `unknown` 值不增加
* 若 `x` 不為二的冪次方，則 unknown 值會增加至跳出迴圈
* line 8:`return (unknown == 1)`
* 若 `x` 為二的冪次方，最後會 shift 至第一個 `1` 出現之位置，跳出迴圈並回傳 true
* 若 `x` 不為二的冪次方， unknown 值會增加至大於 `1` ，回傳 false 。若 `x = 0` 則會直接回傳 false
#### 延伸題目
:::success
延伸題目: 舉出 abs 以外，透過 bitwise 操作將原有運算改為 const-time 實作的案例，應當解釋並探討應用場景。
:::
在這份資料 [Bit Twiddling Hacks](http://graphics.stanford.edu/~seander/bithacks.html) 中提及許多 bitwise operation 的使用，像是 [bit inverse](https://hackmd.io/@sysprog/ByzoiggIb?type=view) 、 abs 等等。在此想針對 `Number of 1 bits` 說明分析。在計算 `Number of 1 bits` 又被稱為 [Hamming weight](https://en.wikipedia.org/wiki/Hamming_weight) 、 population count 、 sideways addition 。 在 C 語言中也提供相對應的函式庫計算 popcount ，如表所示：
| Language | Compiler | Function |
| -------- | -------- | -------- |
| C | [Visual Studio ](https://docs.microsoft.com/zh-tw/cpp/intrinsics/popcnt16-popcnt-popcnt64?view=vs-2019) | _popcnt16() |
| | | _popcnt() |
| | | _popcnt64() |
| | GCC | __builtin_popcount() |
| | | __builtin_popcountl() |
| | | __builtin_popcountll() |
以下將以 bitwise operation 實現 32 bits 之 popcnt 又被稱作 `A SWAR Algoritm`，其中 `SWAR` 代表 `SIMD Within a Register` ，此演算法也被記載在 [AMD Software Optimization Guide for AMD64 Processors](https://www.amd.com/system/files/TechDocs/25112.PDF) p.195 - p.196 中。:
```clike
unsigned int v; // count bits set in this (32-bit value)
unsigned int c; // store the total here
static const int S[] = {1, 2, 4, 8, 16}; // Magic Binary Numbers
static const int B[] = {0x55555555, 0x33333333, 0x0F0F0F0F, 0x00FF00FF, 0x0000FFFF};
c = v - ((v >> 1) & B[0]);
c = ((c >> S[1]) & B[1]) + (c & B[1]);
c = ((c >> S[2]) + c) & B[2];
c = ((c >> S[3]) + c) & B[3];
c = ((c >> S[4]) + c) & B[4];
```
在 K&R 中描述的 population count function：
```clike
int popcount(unsigned x)
{
int c;
for (c = 0; x != 0; x >>= 1)
if (x & 1)
c++;
return c;
}
```
SWAR Algo 與 loop 版本之 cycle 比較 ([references](https://bits.stephan-brumme.com/countBits.html))：
```
+ Intel® Pentium™ D:
• countBits: ≈ 23 cycles per number, constant time, data independent
• countBitsLoop: ≈ 68 cycles per number (average)
• countBitsLoop(0): ≈ 4 cycles per number when 0 bits are set (0% are set)
• countBitsLoop(16): ≈ 54 cycles per number when 16 bits are set (50% are set)
• countBitsLoop(32): ≈ 145 cycles per number when 32 bits are set (100% are set)
• simple (unrolled for-loop): ≈ 60 cycles per number, constant time, data independent
+ Intel® Core™ 2:
• countBits: ≈ 16.5 cycles per number, constant time, data independent
• countBitsLoop: ≈ 37.5 cycles per number (average)
• countBitsLoop(0): ≈ 2.5 cycles per number when 0 bits are set (0% are set)
• countBitsLoop(16): ≈ 37 cycles per number when 16 bits are set (50% are set)
• countBitsLoop(32): ≈ 70 cycles per number when 32 bits are set (100% are set)
• simple (unrolled for-loop): ≈ 77 cycles per number, constant time, data independent
+ Intel® Core™ i7:
• countBits: ≈ 16 cycles per number, constant time, data independent
• countBitsLoop: ≈ 38 cycles per number (average)
• countBitsLoop(0): ≈ 2.5 cycles per number when 0 bits are set (0% are set)
• countBitsLoop(16): ≈ 37 cycles per number when 16 bits are set (50% are set)
• countBitsLoop(32): ≈ 70 cycles per number when 32 bits are set (100% are set)
• simple (unrolled for-loop): ≈ 67 cycles per number, constant time, data independent
```
:::danger
應該解讀上圖背後的意義，特別是從處理器架構著手
:notes: jserv
:::
利用 for 迴圈簡單測試十六筆資料，結果如下：
```
$gcc -o popcnt popcnt.c
$./popcnt
popcnt(0xffffffff) = 32
popcnt(0xfffffffe) = 31
popcnt(0xfffffffd) = 31
popcnt(0xfffffffc) = 30
popcnt(0xfffffffb) = 31
popcnt(0xfffffffa) = 30
popcnt(0xfffffff9) = 30
popcnt(0xfffffff8) = 29
popcnt(0xfffffff7) = 31
popcnt(0xfffffff6) = 30
popcnt(0xfffffff5) = 30
popcnt(0xfffffff4) = 29
popcnt(0xfffffff3) = 30
popcnt(0xfffffff2) = 29
popcnt(0xfffffff1) = 29
popcnt(0xfffffff0) = 28
```
結果正確，開始探討其中原理，讓我們看看視覺上較為簡單版本:
```clike
x = (x & 0x55555555) + ((x >> 1) & 0x55555555); // line 1
x = (x & 0x33333333) + ((x >> 2) & 0x33333333); // line 2
x = (x & 0x0f0f0f0f) + ((x >> 4) & 0x0f0f0f0f); // line 3
x = (x & 0x00ff00ff) + ((x >> 8) & 0x00ff00ff); // line 4
x = (x & 0x0000ffff) + ((x >> 16) &0x0000ffff); // line 5
```
將程式中的 "Magic Number" 寫成二進位表示法：
```
0x55555555 = 0101 0101 0101 0101 0101 0101 0101 0101
0x33333333 = 0011 0011 0011 0011 0011 0011 0011 0011
0x0f0f0f0f = 0000 1111 0000 1111 0000 1111 0000 1111
0x00ff00ff = 0000 0000 1111 1111 0000 0000 1111 1111
0x0000ffff = 0000 0000 0000 0000 1111 1111 1111 1111
```
觀察之後發現，使用 Divide and Conquer 方法，其中兩個 bits 的數量可以用 `0b00`、`0b01`、`0b10` ( 兩個 bits 最多就兩個 1 )表示，利用每次合併計算該單位中 `1` 之個數，以下為步驟：
* step 1:以 shift amount 為單位做切割，並計算其中 1 之個數
* step 2:以 shift amount 為單位兩兩相加，形成新的輸出
* step 3:重複直到合併成一串
e.g.`x = 0x12345678`:
```shell
|0|0|0|1|0|0|1|0|0|0|1|1|0|1|0|0|1|0|0|1|1|0|1|0|1|0|1|1|1|0|0|0| <-x
|0 0|0 1|0 0|0 1|0|0|1 0|0 1|0 0|0 1|0|1|0 1|0 1|0 1|1 0|0 1|0 0| <-0x11245564
|0 0 0 1|0 0 0 1|0 0 1 0|0 0 0 1|0 0 1 0|0 0 1 0|0 0 1 1|0 0 0 1| <-0x11212231
|0 0 0 0 0 0 1 0|0 0 0 0 0 0 1 1|0 0 0 0 0 1 0 0|0 0 0 0 0 1 0 0| <-0x2030404
|0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1|0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0| <-0x50008
|0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 0 1| <-0xd
```
----
Sign in with Wallet
Connect another wallet