2019q1 Homework3 (review)
===
contributed by < `Laurora` >
## 第一週測驗 `2`
**[題目](https://hackmd.io/s/SyrZMGYr4)**
```clike
#include <stdint.h>
#define ALIGN_uint32(x, a) __ALIGN_MASK(x, ((uint32_t)(a)) - 1)
#define __ALIGN_MASK(x, mask) (((x) + (mask)) & ~(mask))
```
這是 data alignment 的巨集，data alignment 的意思是，data 的 address 扣除 base address 後 (也就是 offset) 可被 1, 2, 4, 8 等等這些數字整除，從這些數字可以發現他們都是 2N (N 為從 0 開始的整數)。換句話說，這些 data object 可以用 1, 2, 4, 8 byte 去 alignment
考慮 4-byte boundary，當 x 是 `0x1006`, a 是 `4`, 那麼 `ALIGN(x, a)` 會得到什麼數值？
### 原理
當 x 是 `0x1006`, a 是 `4`, 根據定義將 `ALIGN_uint32(x, a)` 展開可得到
```
((0x1006) + (3)) & ~(3)
```
改成 2 進位
```
(0x1006) + (3) ((0x1006) + (3)) & ~(3)
0001 0000 0000 0110 0001 0000 0000 1001
+0000 0000 0000 0011 &1111 1111 1111 1100 <--- (~a) = (~3)
--------------------- ---------------------
0001 0000 0000 1001 0001 0000 0000 1000 <--- 0x1008
```
從 bitwise 可以很清楚的看到
* `(uint32_t)(a) - 1` 的作用是選出要 mask (alignment) 的位數
* `(x) + (mask)` 的作用是讓現在的數值加到下一個要對齊的單位
* `((x) + (mask)) & ~(mask)` 則是將多餘的位數 mask 以對齊
同樣的原理更改 `a` 可以對齊 1, 2, 4, 8 byte
### 為什麼需要 alignment ?
* 變數的宣告，會配置其所需的記憶體。每種變數所需的大小不一樣。例如： char 需 1 byte，int 需 4 bytes ， double 需 8 bytes。
* 在 32 bits 的架構上，一次的資料存取也就是 32 bits (4 bytes)。每次存取便是以 4 bytes 為單位，不管需要的是其中那個byte，就存取資料所在的那 4 個 bytes。例如：第0，4，8 ，12....等，而不會是從3，7，9開始抓4個bytes。
## 第二週測驗 `2`
**[題目](https://hackmd.io/s/H1Pik8M8E#%E6%B8%AC%E9%A9%97-2)**
[population count](https://en.wikichip.org/wiki/population_count) 簡稱 popcount 或叫 sideways sum，是計算數值的二進位表示中，有多少位元是 `1`，在一些場合下很有用，例如計算 0-1 稀疏矩陣 (sparse matrix)或 bit array 中非 `0` 元素個數、計算兩個字串的 [Hamming distance](https://en.wikipedia.org/wiki/Hamming_weight)。Intel 在 2008 年 11 月 Nehalem 架構的處理器 Core i7 引入 SSE4.2 指令集，其中就有 `CRC32` 和 `POPCNT` 指令，`POPCNT` 可處理 16-bit, 32-bit, 64-bit 整數。
對應到 C 程式的實作:
```clike
unsigned popcnt_naive(unsigned v) {
unsigned n = 0;
while (v)
v &= (v - 1), n = -(~n);
return n;
}
```
可改寫為以下常數時間的實作:
```clike
unsigned popcnt(unsigned v)
{
unsigned n;
n = (v >> 1) & 0x77777777;
v -= n;
n = (n >> 1) & 0x77777777;
v -= n;
n = (n >> 1) & 0x77777777;
v -= n;
v = (v + (v >> X)) & Y;
v *= 0x01010101;
return v >> 24;
}
```
### 原理
#### `popcnt_native()`
```clike
unsigned popcnt_naive(unsigned v) {
unsigned n = 0;
while (v)
v &= (v - 1), n = -(~n);
return n;
}
```
* [comma operator](https://en.wikipedia.org/wiki/Comma_operator)
```clike
v &= (v - 1), n = -(~n);
```
相當於
```clike
v &= v-1;
n = -(~n);
```
* `v &= v-1;` 可以找到最靠近低位的 `1` ， `v-1` 將最靠近低位的 `1` 及以下的 `0` 得到相當於 1's complement 運算的結果； `v & v-1` 可以對剛剛操作的結果 mask ，即完成一次 count 1
* `n = -(~n);` 是先對 `n` 取 1's complement 再取 2's complement ，相當於 `n = n + 1;`
了解原理之後來看看改寫的版本
>HAKMEM algorithm
#### `popcnt()`
```clike
unsigned popcnt(unsigned v)
{
unsigned n;
n = (v >> 1) & 0x77777777;
v -= n;
n = (n >> 1) & 0x77777777;
v -= n;
n = (n >> 1) & 0x77777777;
v -= n;
v = (v + (v >> 4)) & 0x0F0F0F0F;
v *= 0x01010101;
return v >> 24;
}
```
先來看這個部份
```clike
n = (v >> 1) & 0x77777777;
v -= n;
n = (n >> 1) & 0x77777777;
v -= n;
n = (n >> 1) & 0x77777777;
v -= n;
```
大致可以看出來是將數字拆成 $A_0\sim A_7$，每 4 bits ($a_0\sim a_3$)為單位比較
* `n = (v >> 1) & 0x77777777;` 這邊是將拆出來的每 4 bits 中的最低位 ($a_0$) 捨去
* `v -= n;` 是原本的 $v$ 減去 $\lfloor \frac v 2 \rfloor$
先單獨看其中一個單位的 4 bit $a_3 a_2 a_1 a_0$ ，上述程式碼的部份可以表示成以下數學式
$(a_3\times2^3+a_2\times2^2+a_1\times2^1+a_0)-(a_3\times2^2+a_2\times2^1+a_1)-(a_3\times2^1+a_2)-a_3$
$= a_3+a_2+a_1+a_0$
最後算出來的 `v` 就是以 4 bits 為單位，有 1 的 bit 數總和，分別表示在每 4 bits 中。
若能理解上面的算式，下面就是再對分散於各個單位的 count 做處理。
```clike
v = (v + (v >> 4)) & 0x0F0F0F0F;
v *= 0x01010101;
return v >> 24;
```
* `v = (v + (v >> 4)) & 0x0F0F0F0F;` 分別相加 $A_7、A_6$，$A_5、A_4$，$A_3、A_2$，$A_1、A_0$，存入 $A_6, A_4, A_2, A_0$ 中，原來的 $A_7, A_5, A_3, A_1$ mask 成 `0`
>1 的個數最多 8 個 ( b1000 )，不會 overflow
* `v *= 0x01010101;` 寫成直式如下
```
0 A6 0 A4 0 A2 0 A0
x 0 1 0 1 0 1 0 1
---------------------------------------------------
0 A6 0 A4 0 A2 0 A0
0 A6 0 A4 0 A2 0 A0 0
0 A6 0 A4 0 A2 0 A0 0
0 A6 0 A4 0 A2 0 A0 0
---------------------------------------------------
↑_______________________A6+A4+A2+A0
```
發現我們要的答案就在原本 $A_6$ 的位置 ( $2^7$ )
因此將 `v` 右移 24 bits 即為所求，剩下的位數會 overflow ，右移後不影響結果。
### 時間分析
分別測量 `popcnt_native()` 和 `popcnt()` 隨「輸入數字」增加對「時間」的趨勢，可以看出 `popcnt()` 所需時間較 `popcnt_native()` 略短一些
分別測量 `popcnt_native()` 和 `popcnt()` 「 1 的個數」增加對「時間」的趨勢，可以看出 `popcnt_native()` 和 `popcnt()` 趨勢皆是呈現常態分佈。
### Time Attack
* [timing attack](https://en.wikipedia.org/wiki/Timing_attack) 是一種 [side channel attack](https://en.wikipedia.org/wiki/Side-channel_attack)
* side channel attack: 是利用計算機系統在執行過程中產生的資訊進行的攻擊，而不是去猜測系統算法的缺失（例如，密碼分析或 bug ）
* 時間訊息、功耗、磁漏甚至聲音都可以提供 side channel attack 所需的資訊。
* timing attack 主要利用電腦加解密運算時之時間特徵，推導出私密金鑰的一種攻擊方法。
* 計算機中的每個邏輯運算都需要時間來執行，時間會因為不同的 input 而不同，通過精確測量每個運算的時間，攻擊者可以回推 input 。
## 第二週測驗 `3`
**[題目](https://hackmd.io/s/H1Pik8M8E#%E6%B8%AC%E9%A9%97-3)**
考慮以下程式碼:
```clike
#include <stdio.h>
#define cons(x, y) E
struct llist { int val; struct llist *next; };
int main() {
struct llist *list = cons(9, cons(5, cons(4, cons(7, NULL))));
struct llist *p = list;
for (; p; p = p->next)
printf("%d", p->val);
printf("\n");
return 0; }
```
預期執行時期輸出 `9547`，補完 `E`。
E = `(struct llist[]){x, y}`
### 原理
* `#define cons(x, y) (struct llist[]){x, y}`
* 利用 ==compound literal== 建立 static linked list
* 可針對未知大小的 array/struct 初始化，也可以直接對特定位置的 array 或 struct 的內容賦值
* compound literal 可以做 lvalue ，可以傳特定型別或自己定義的 struct
>C99 [6.5.2.5] ***Compound literals***
>* The type name shall specify an object type or an array of unknown size, but not a variable length array type.
>* A postfix expression that consists of a parenthesized type name followed by a braceenclosed list of initializers is a compound literal. It provides an unnamed object whose value is given by the initializer list.
>* If the type name specifies an array of unknown size, the size is determined by the initializer list as specified in 6.7.8, and the type of the compound literal is that of the completed array type. Otherwise (when the type name specifies an object type), the type of the compound literal is that specified by the type name. In either case, the result is an lvalue.
* 將題目的 `cons(9, cons(5, cons(4, cons(7, NULL))))` 展開如下
```clike
//展開 cons(9, cons(5, cons(4, cons(7, NULL))))
llist.val = 9;
llist.next = &cons(5, cons(4, cons(7, NULL)));
//展開 cons(5, cons(4, cons(7, NULL)))
llist.val = 5;
llist.next = &cons(4, cons(7, NULL))
//展開 cons(4, cons(7, NULL))
llist.val = 4;
llist.next = &cons(7, NULL);
//展開 cons(7, NULL)
llist.val = 7;
llist.next = NULL;
```
便會得到如下的 linked list
```
+------+------+ +------+------+ +------+------+ +------+------+
| | | | | | | | | | | |
| 9 | next +---->| 5 | next +---->| 4 | next +---->| 7 | NULL |
| | | | | | | | | | | |
+------+------+ +------+------+ +------+------+ +------+------+
^
|
head
```
>從 `cons(7, NULL)` 往外面拆開會比較容易理解 pointer 的指向
所以 print 出來的結果會是 `9547`
### 應用於 linux 核心
在 `linux/list.h` 中定義了這兩個 macro ，用來初始化 doubly linked list
```clike
#define LIST_HEAD_INIT(name) { &(name), &(name) }
#define LIST_HEAD(name) \
struct list_head name = LIST_HEAD_INIT(name)
```
其中 `list_head` 的結構如下
```clike
struct list_head {
struct list_head *next, *prev;
};
```
若在程式中使用 `LIST_HEAD(example)` ，透過上面的 macro 可以將之展開如下
```clike
struct list_head example = { &(example) , &(example)}
```
這樣就成功初始化一個 doubly linked list ， 其 `next` 和 `prev` 指標都指向自己的 head
等效於下面的程式
```clike
struct list_head example;
example.next = &example;
example.prev = &example;
```
Sign in with Wallet
Connect another wallet