# 2019q3 Homework 2 (quiz2)
contributed by < `davinais` >
###### tags: `sysprog` `sysprog2019`
:::info
因為要做碩士推甄資料所以作業來不及做完，抱歉
:::
:::danger
請自己跟廣大的納稅人致歉和反省
:notes: jserv
:::
:::success
以下 code 除非有特別說明，否則都是已作答完的 code
:::
## 測驗 1
考慮下方檔案 `4thought.c` 是 ACM-ICPC 題目 [4 thought](https://open.kattis.com/problems/4thought) 的一個解法，假設程式的輸入符合 [4 thought](https://open.kattis.com/problems/4thought) 的描述，請補完程式碼:
```c=
#include <stdbool.h>
#include <stdio.h>
enum {
opType1 = 0x1 << 0, opType2 = 0x1 << 1,
opType3 = 0x1 << 4, opType4 = 0x1 << 5,
};
static int operate(int op, int a, int b) {
switch (op) {
case opType1: return a + b;
case opType2: return a - b;
case opType3: return a * b;
case opType4: return (int) a / b;
}
return 0;
}
static char op_to_char(int op) {
return "+-*/?"[op - 1];
}
static int op_to_prio(int op) {
return ((int[]){opType1, opType2, opType3, opType4, -1})[op - 1];
}
static int calc(int op1, int op2, int op3) {
op1 = op_to_prio(op1);
op2 = op_to_prio(op2);
op3 = op_to_prio(op3);
bool p1 = (op1 & 0x0F) == 0; // = 1 for * or /
bool p2 = (op2 & 0x0F) == 0; // else = 0
bool p3 = (op3 & 0x0F) == 0;
#define IF_XYZ(a, b, c) if(a(X) && b(Y) && c(Z))
#define X p1
#define Y p2
#define Z p3
// (4 + 4 + 4 + 4) or (4 / 4 / 4 / 4)
if ((p1 == p2) && (p2 == p3))
return operate(op3, operate(op2, operate(op1, 4, 4), 4), 4);
/* Write your code here */
else IF_XYZ(!,!,) {
return operate(op2, operate(op1, 4, 4), operate(op3, 4, 4));
}
else IF_XYZ(!,,!) {
return operate(op3, operate(op1, 4, operate(op2, 4, 4)), 4);
}
else IF_XYZ(,!,!) {
return operate(op3, operate(op2, operate(op1, 4, 4), 4), 4);
}
else IF_XYZ(,!,) {
return operate(op2, operate(op1, 4, 4), operate(op3, 4, 4));
}
else IF_XYZ(,,!) {
return operate(op3, operate(op2, operate(op1, 4, 4), 4), 4);
}
else IF_XYZ(!,,) {
return operate(op1, operate(op2, 4, 4), operate(op3, 4, 4));
}
#undef Z
#undef Y
#undef X
#undef IF_XYZ
return 0;
}
int main(void) {
int n;
scanf("%d", &n);
int sol[n];
for (int i = 0; i < n; i++)
scanf("%d", &sol[i]);
bool validSolution = false;
for (int i = 0; i < n; i++) {
for (int op1 = 4; op1 > 0; op1--) {
for (int op2 = 4; op2 > 0; op2--) {
for (int op3 = 4; op3 > 0; op3--) {
int sol_checked = calc(op1, op2, op3);
if (sol_checked == sol[i]) {
validSolution = true;
char op1char = op_to_char(op1);
char op2char = op_to_char(op2);
char op3char = op_to_char(op3);
printf("4 %c 4 %c 4 %c 4 = %d\n", op1char, op2char,
op3char, sol[i]);
op1 = -1; op2 = -1; op3 = -1;
break;
}
}
}
}
if (!validSolution)
printf("no solution\n");
validSolution = false;
}
return 0;
}
```
### 初步思考
這應該算是這份測驗裡面能夠直觀寫出答案的幾題之一了，雖然我考試的時候還是不小心寫錯了，只有換運算子順序，忘記運算子也會改變。
這題可以很直觀的直接列舉出所有情形，就像上面作答的那樣，將所有八種組合列出即可。
:::success
延伸問題:
1. 解釋程式運作的原理和推敲背後的思路;
2. 探討 [4 thought](https://open.kattis.com/problems/4thought) 組合出來的數值分佈，並且透過數論解釋;
3. 提出得以改善上述程式碼執行效率的方案，著手分析和實作;
:::
### 以數論來解釋 4 thought
稍微想了一下，原本完全沒有想法，不過後來想想，換成二進位是不是就比較容易思考了？(四進位應該也行，不過不太習慣就不用了)
先考慮 4 的二進位表示法： $4_{10} = 0100_2$ 。
再來考慮當 4 與 4 做四則運算時，在二進位下會發生的情況：
- 加： $4_{10} + 4_{10} = 0100_2 + 0100_2 = 8_{10} = 01000_2$。
- 減： $4_{10} - 4_{10} = 0100_2 - 0100_2 = 0_{10} = 00000_2$。
- 乘： $4_{10} \times 4_{10} = 0100_2 \times 0100_2 = 16_{10} = 010000_2$。
- 除： $4_{10} \div 4_{10} = 0100_2 \div 0100_2 = 1_{10} = 000001_2$。
先排除減法，我們可以發現單純對4運算完的結果只有一位是1，由於我們只使用了 4 個 4，因此**如果不考慮減法，超過 4 個 1 以上的二進位數字必定是不可能達成的**。更進一步考慮，雖然最大能容忍到 4 個 1，但是因為一開始都是 4，1 都在同一個位置，如果不經過運算的話是無法移動到其他位置的。因此**不考慮減法的情況下，理論上最多只能夠有兩個 1 ，而且如果是兩個 1 的情況下還不可能超過第 6 位，一個 1 的情況下不可能超過第 10 位**。
再考慮減法，由於減法我們可以想成二補數的加法，而 -1 又是全部都是 1 的數字，可以發現
## 測驗 2
考慮以下程式碼 (`fitbits.c`) 可檢驗輸入的整數 `x` 是否可用 `n` 個位元來表示，例如 (x = 4, n = 9) 要回傳 `true`, 當 (x = 4, n = 2) 回傳 `false`。
實作的程式碼不能有任何邏輯條件判斷 (如 `if`, `else`, `?`) 或迴圈 (如 `for`, `while`, `goto`, `switch`, `case`, `break`, `continue`)，可用的運算子是 `>>`, `<<`, `-`, `+`, `!`, `~`, `&`, `|`
```c
#include <stdbool.h>
bool fit_bits(int x, int n) {
/* Write your code here */
int mask = ~((1 << n) - 1);
x &= mask;
return (bool) x;
}
```
:::success
延伸問題: 在重視資訊安全的專案中，找出類似用法的程式碼，予以解說並進行相關 information leaks 的實驗
:::
## 測驗 3
考慮以下程式碼 (`is-less-equal.c`) 可檢驗輸入的整數 `x` 和 `y`，是否存在 $x <= y$ 的關係。例如 (x = 4, n = 4) 要回傳 `true`, 當 (x = 14, n = 9) 回傳 `false`。
實作的程式碼不能有任何邏輯條件判斷 (如 `if`, `else`, `?`) 或迴圈 (如 `for`, `while`, `goto`, `switch`, `case`, `break`, `continue`)，當然也不能用 `>=`, `>`, `<`, `<=`, `-` 等運算子。可用的運算子是 `>>`, `<<`, `+`, `~`
```cpp
#include <stdbool.h>
bool is_leq(int x, int y) {
int s;
/* Write your code here */
return (bool) s;
}
```
:::success
延伸問題: 在重視資訊安全的專案中，找出類似用法的程式碼，予以解說並進行相關 information leaks 的實驗
:::
## 測驗 4
考慮一種針對短字串的最佳化操作，假設字串總是小於等於 8 bytes，標的硬體是像 x86_64 這樣的 64-bit 架構而且是 [little endian](https://en.wikipedia.org/wiki/Endianness)，於是我們可實作類似以下的程式碼 (`ministr.c`):
```cpp
#include <stdint.h>
#include <stdio.h>
#include <string.h>
typedef union {
uint64_t integer;
char array[8];
} mini_str;
static unsigned BitScanReverse(uint64_t x) {
return 63 - __builtin_clzll(x);
}
/**
* Find the length of the given mini_str.
* @param str string to find length of
* @return length of the given string
*/
unsigned mini_strlen(mini_str str) {
// Special case for empty string.
if (str.integer == 0) return 0;
// Otherwise find first non-zero bit (which will be in the first non-zero
// byte), and find which byte it is in.
// FIXME: Assumes little-endian.
unsigned msb = BitScanReverse(str.integer);
return msb / 8 + 1;
}
/**
* Create a new mini_str with length 0.
* @return newly created mini_str
*/
mini_str mini_str_new(void) {
// Create string of all null bytes.
mini_str str = {.integer = 0};
return str;
}
/**
* Append str2 to the end of str1 and return the reult.
* @param str1 first string
* @param str2 second string
* @return combined string
*/
mini_str mini_strcat(mini_str str1, mini_str str2) {
// Shift str2 along by str1Len characters to move it into position.
unsigned str1Len = mini_strlen(str1);
str2.integer <<= str1Len * 8; // FIXME: Assumes little-endian.
/* Write your code here */
str1.integer |= str2.integer; // str1 has trailing zero, we can just 'OR' to concat str2
return str1;
}
#define mini_str_to_c(mini_str) ((const char *) (mini_str).array)
#define mini_str_to_cNoConst(mini_str) ((char *) (mini_str).array)
/**
* Create a mini_str from a standard C character array.
* @param cstr Null-terminated C-string to use as input
* @return newly created mini_str
*/
mini_str mini_str_from_c(const char *cstr) {
// Create empty string.
mini_str mini_str = mini_str_new();
// Copy string.
strncpy(mini_str_to_cNoConst(mini_str), cstr, 7);
return mini_str;
}
int main(int argc, char **argv) {
mini_str all = mini_str_from_c("All ");
mini_str red = mini_str_from_c("red");
mini_str cat = mini_strcat(all, red);
printf("%s\n", mini_str_to_c(cat));
return 0;
}
```
這裡的 `__builtin_clzll` 是 [GCC builtin function](https://gcc.gnu.org/onlinedocs/gcc/Other-Builtins.html)，作用是 [bit scan](https://www.chessprogramming.org/BitScan)，程式預期輸出為:
```
All red
```
你應該要實作 `calc` 函式中標註 `/* Write your code here */` 之後的程式碼。除了撰寫程式，你應該提供對應的程式碼註解。
注意: 實作的程式碼不能有任何邏輯條件判斷 (如 `if`, `else`, `?`) 或迴圈 (如 `for`, `while`, `goto`, `switch`, `case`, `break`, `continue`)，也不能用 `>=`, `>`, `<`, `<=`, `-` 等運算子。
:::success
延伸問題:
1. 指出這樣針對短字串的最佳化效益，並嘗試量化;
2. 什麼樣的情境會出現大量的短字串？請舉例並分析;
3. 程式碼該如何修改，才能適用 big/little-endian 呢？
4. 考慮到現代的處理器架構支援 [SIMD](https://en.wikipedia.org/wiki/SIMD)，得以一次處理 128-bit, 256-bit, 甚至是 512-bit，請評估這樣最佳化策略的可用性，應當有對應的實驗;
:::
## 測驗 5
[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 整數。
GCC 提供對應的 builtin function:
${\_\_builtin\_popcount}(x)$: `x` 總共有幾個 `1`。使用示範:
```cpp
int x = 5328; // 00000000000000000001010011010000
printf("%d\n", __builtin_popcount(x)); // 5
```
以下是個存在實作缺陷的版本:
```cpp
int popcnt_naive(int n) {
int count = 0;
while (n) {
if (n & 1)
++count;
n = n >> 1;
}
return count;
}
```
呼叫 `popcnt_naive(-1)` 時，會造成無窮迴圈，請指出錯誤所在，並且重寫為正確的版本。
```cpp
int popcnt_naive(unsigned int n) {
int count = 0;
while (n) {
if (n & 1)
++count;
n = n >> 1;
}
return count;
}
```
## 測驗 6
延伸測驗 `5`，實作 branchless 的 `popcnt` 並附上對應的程式原理解說。
:::success
延伸問題:
1. 指出 `popcnt` 的應用場景;
2. 在 Linux 核心程式碼找出具體用法並解析;
:::
沒錯，剛好在[上一次的review](https://hackmd.io/WOBdZoluRXG33_-lDbtLbA?both#%E4%BB%A5-const-time-%E5%AF%A6%E4%BD%9C-popcount)已經有寫過了！
這裡運用平行加法的技巧來實現：
```c=
#define POW2(c) (1u<<(c))
#define MASK(c) (((unsigned int)(-1))/(POW2(POW2(c))+1u))
#define COUNT(x,c) ((x)&MASK(c)) + (((x)>>(POW2(c)))&MASK(c))
int parallel_popcnt(unsigned int n)
{
n=COUNT(n,0);
n=COUNT(n,1);
n=COUNT(n,2);
n=COUNT(n,3);
n=COUNT(n,4);
/* n=COUNT(n,5); for 64-bit integers */
return n ;
}
```
由2位1組開始，分別取出每組的高位與低位並且相加，再將1的個數直接存放在該組的位置。隨後合併相鄰的兩組繼續進行迭代，直到完成為止。
以下作為示範，假設原本有 8 位元數字 $10110101$，這裡以 $\hat x$表示高位， $\check x$ 表示低位：
1. 先兩兩分組： $\hat1\check0|\hat1\check1|\hat0\check1|\hat0\check1$
2. 以遮罩取出高位以及低位： $1|1|0|0$ 與 $0|1|1|1$
3. 兩者相加，代表該組 1 的個數： $01|10|01|01$
4. 重新迭代，四四分組： $\hat0\hat1\check1\check0|\hat0\hat1\check0\check1$
5. 以遮罩取出高位以及低位： $01|01$ 與 $10|01$
6. 兩者相加，代表該組 1 的個數： $0011|0010$
7. 再次迭代，八八分組： $\hat0\hat0\hat1\hat1\check0\check0\check1\check0$
8. 以遮罩取出高位以及低位： $0011$ 與 $0010$
9. 相加，代表該組 1 的個數： $00000101$
10. 迭代完成，因此 $10110101$ 總共有 $00000101_2=5_{10}$ 個 1
若數字是 $2^k$ 位元，則只需要 $k$ 次迭代必定可完成。
## 測驗 7
考慮到以下程式 (`alloc.c`) 是 [aligned_alloc](https://linux.die.net/man/3/posix_memalign) 的一種簡易實作:
```cpp
#include <stdlib.h>
// Number of bytes used for storing the aligned pointer offset.
// up to 64KB alignment, a size which is already unlikely to be
// used for alignment.
typedef uint16_t offset_t;
#define PTR_OFFSET_SIZE sizeof(offset_t)
#define align_up(num, align) \
(((num) + ((align) - 1)) & ~((align) - 1))
void *aligned_malloc(size_t align, size_t size) {
void *ptr = NULL;
// size must be a power of two.
if (!((align & (align - 1)) == 0))
return ptr;
if (align && size) {
// allocate extra bytes to meet the alignment
uint32_t header_size = PTR_OFFSET_SIZE + (align - 1);
void *p = malloc(size + header_size);
/* Write your code here */
}
return ptr;
}
```
其作用是配置針對 `align` 個 bytes 對齊的記憶體空間，可對照閱讀 [Introduction & Allocators](http://stevenlr.com/posts/handmade-rust-1-allocators/) 以掌握原理。你應該要實作 `aligned_malloc` 函式中標註 `/* Write your code here */` 之後的程式碼。除了撰寫程式，你應該提供對應的程式碼註解。
注意: 輸入的 `align` 應該要是 2^N^ (power of 2)，否則就回傳 `NULL`。
:::success
延伸問題:
1. 解釋程式運作的原理和推敲背後的思路;
2. 在開放原始碼的專案中，找尋類似的程式碼，解說並量化具體效益;
:::
## 測驗 8
延伸測驗 `7`，實作 `aligned_free`，其原型宣告如下:
```cpp
void aligned_free(void *ptr);
```
除了撰寫程式，你應該提供對應的程式碼註解。
## 測驗 9
考慮以下 64-bit GCD (greatest common divisor, 最大公因數) 求值函式:
```cpp
#include <stdint.h>
uint64_t gcd64(uint64_t u, uint64_t v) {
if (!u || !v) return u | v;
while (v) {
uint64_t t = v;
v = u % v;
u = t;
}
return u;
}
```
改寫為以下等價實作:
```cpp
#include <stdint.h>
uint64_t gcd64(uint64_t u, uint64_t v) {
if (!u || !v) return u | v;
int shift;
for (shift = 0; !((u | v) & 1); shift++) {
u /= 2, v /= 2;
}
while (!(u & 1))
u /= 2;
do {
while (!(v & 1))
v /= 2;
if (u < v) {
v -= u;
} else {
uint64_t t = u - v;
u = v;
v = t;
}
//} while (/* Write your code here */);
} while (u != v);
//return /* Write your code here */;
return ((1 << shift) * u);
}
```
補完以上程式碼，即標注 `/* Write your code here */` 的部分，需要抄寫 `while` 和 `return` 所在的程式碼。
答案已附在改寫程式碼中。這裡我們將公因數做二階段運算，第一階段是取出2指數的部分，如同上方的 `for` 迴圈部分，而第二階段則是對剩下的數字做輾轉相除法，因此條件為直到 `v == 0` 為止（此處採用 `u != v` 作為 condition，可以少做一次迴圈）
最後要運算公因數，將2指數的公因數反運算回去（左移），並且再乘上第二階段輾轉相除法找出來的公因數即可。
## 測驗 10
承測驗 `9`, 透過 gcc 內建的 [\_\_builtin_ctz](https://gcc.gnu.org/onlinedocs/gcc/Other-Builtins.html) (Returns the number of trailing 0-bits in x, starting at the least significant bit position) 改寫程式碼如下:
```clike
#include <stdint.h>
uint64_t gcd64(uint64_t u, uint64_t v) {
if (!u || !v) return u | v;
// int shift = __builtin_ctzll(/* Write your code here */);
int shift = __builtin_ctzll(u | v);
u >>= __builtin_ctzll(u);
while (v) {
v >>= __builtin_ctzll(v);
if (u < v) {
/* Write your code here */
v -= u;
} else {
uint64_t t = u - v;
u = v, v = t;
}
}
//return /* Write your code here */;
return ((1 << shift) * u);
}
```
請補完程式碼，作答時需要一併包含原本函式內容。除了撰寫程式，你應該提供對應的程式碼註解。
:::success
延伸問題: 解釋上述程式程式運作原理，以及在 x86_64 上透過 [\_\_builtin_ctz](https://gcc.gnu.org/onlinedocs/gcc/Other-Builtins.html) 改寫 GCD 對效能的提升
:::
答案已附在改寫程式碼中。這裡同測驗`9`，將公因數做二階段運算。
## 測驗 11
考慮到 [memcmp](http://man7.org/linux/man-pages/man3/memcmp.3.html) 一種實作如下: (行為和 ISO C90 有出入)
```cpp
#include <stdint.h>
#include <stddef.h>
int memcmp(const uint8_t *m1, const uint8_t *m1, size_t n) {
for (size_t i = 0; i < n; ++i ) {
int diff = m1[i] - m2[i];
if (diff != 0) return (diff < 0) ? -1 : +1;
}
return 0;
}
```
我們可能因此承受 [information leakage](https://en.wikipedia.org/wiki/Information_leakage) 的風險，於是著手避免使用 conditional branching 一類的指令，從而避免 [side-channel attack](https://en.wikipedia.org/wiki/Side-channel_attack)。
為了避免 conditional branch 指令的出現，我們可將 `(res > 0) - (res < 0)` 替換為 `((res - 1) >> 8) + (res >> 8) + 1`。隨後我們實作下方功能等價但避免 branch 的 ` cst_memcmp`:
```cpp
#include <stdint.h>
#include <stddef.h>
int cst_memcmp(const void *m1, const void *m2, size_t n) {
const uint8_t *pm1 = (const uint8_t *) m1 + n;
const uint8_t *pm2 = (const uint8_t *) m2 + n;
int res = 0;
if (n) {
do {
int diff = *--pm1 - *--pm2;
/* Write your code here */
} while (pm1 != m1);
}
return ((res - 1) >> 8) + (res >> 8) + 1;
}
```
注意: 在 Linux 核心內部的實作方式可見:
* [[PATCH] crypto_memcmp: add constant-time memcmp](https://www.spinics.net/lists/linux-crypto/msg09542.html)
* [Re: [PATCH] crypto_memcmp: add constant-time memcmp](https://www.spinics.net/lists/linux-crypto/msg09551.html)
請補完程式碼，作答時需要一併包含原本函式內容。除了撰寫程式，你應該提供對應的程式碼註解。
注意: 在 `/* Write your code here */` 所在的程式碼作用區域 (scope) 中，不得存任何邏輯條件判斷 (如 `if`, `else`, `?`) 或迴圈 (如 `for`, `while`, `goto`, `switch`, `case`, `break`, `continue`)
:::success
延伸問題:
1. 解釋上述程式的原理，需要從機率統計的觀點分析;
* 為何不能用事先計算好的表格呢？ (提示: cache 的影響)
* 如何驗證程式正確以及 constant-time 呢？
2. 在 Linux 核心找到這類 constant-time 的操作程式碼，予以解說和設計實驗;
:::
Sign in with Wallet
Connect another wallet