# 2022q1 Homework2 (quiz2)

contributed by < [Build-A-Moat](https://github.com/Build-A-Moat/lab0-c) >
###### tags: `linux2022`

### 測驗 `1`
考慮以下對二個無號整數取平均值的程式碼:

#include <stdint.h>
uint32_t average(uint32_t a, uint32_t b)
{
    return (a + b) / 2;
}

我們可改寫為以下等價的實作:

#include <stdint.h>
uint32_t average(uint32_t a, uint32_t b)
{
    return (a >> 1) + (b >> 1) + (EXP1);
}

| a | b | (a + b) / 2 | (a + b) >> 1 | (a >> 1) + (b >> 1) |
|:---:|:---:|:-----------:|:------------:|:-------------------:|
| 0 | 0 | 0 | 0 | 0 |
| 0 | 1 | 0 | 0 | 0 |
| 1 | 0 | 0 | 0 | 0 |
| 1 | 1 | 1 | 1 | **0** |

* 從真值表中得知 `(a + b) / 2` 等價於 `(a + b) >> 1` ，而與 `(a >> 1) + (b >> 1)` 不等價，所以 `>>` 沒有分配律。
* 數值被 `>>` 作用時最低位元會被捨去，所以若 `a` 和 `b` 最低位元相加的結果，
只影響到最低位元，則`(a + b) >> 1` 與 `(a >> 1) + (b >> 1)` 等價，而其中當 `a` 和 `b` 的最低位元皆為 `1` 時，會產生進位
* `(EXP1)` 就是進位的部份，即 `(a & b & 1)` ， `& 1`代表取 `a` 與 `b` 的最低位元。

再次改寫為以下等價的實作:

uint32_t average(uint32_t a, uint32_t b)
{
    return (EXP2) + ((EXP3) >> 1);
}

* 從<[你所不知道的 C 語言：數值系統篇](https://hackmd.io/@sysprog/c-numerics)> ，我們可以知道
`(x + y) / 2`
= `(x + y) >> 1`
= `(x ^ y + (x & y) << 1) >> 1`
= `(x & y) + ((x ^ y) >> 1)`

* `EXP2` 即為 `a & b` ， `EXP3` 即為 `a ^ b`
* 但是剛剛上面才說 `>>` 沒有分配律，為何在此處卻成立，

| x | y | (x ^ y + (x & y) << 1) >> 1 | (x & y) + ((x ^ y) >> 1) |
|:---:|:---:|:---------------------------:|:------------------------:|
| 0 | 0 | 0 | 0 |
| 0 | 1 | 0 | 0 |
| 1 | 0 | 0 | 0 |
| 1 | 1 | 1 | 1 |

* 從真值表中的確可以看出結果相等，
* 由上面兩個例子可以推斷，當 `(a + b) >> 1` 中的 `a + b` 若會產生進位，則不可以將 `>>` 分別運算於 `a` 和 `b`
* 以 `(a ^ b + a ^ b) >> 1` 驗證猜測是否正確

| a | b | (a ^ b + a ^ b) >> 1 | (a ^ b) >> 1 + (a ^ b) >> 1 |
|:---:|:---:|:--------------------:|:---------------------------:|
| 0 | 0 | 0 | 0 |
| 0 | 1 | 1 | **0** |
| 1 | 0 | 1 | **0** |
| 1 | 1 | 0 | 0 |

* 猜測正確

先用 `gcc -O3 -c average.c` 編譯，再用 `objdump -d average.o` 來看。

0000000000000000 <average>:
   0:	f3 0f 1e fa          	endbr64 
   4:	8d 04 37             	lea    (%rdi,%rsi,1),%eax
   7:	d1 e8                	shr    %eax
   9:	c3                   	retq   

0000000000000000 <average>:
   0:	f3 0f 1e fa          	endbr64 
   4:	89 f8                	mov    %edi,%eax
   6:	89 f2                	mov    %esi,%edx
   8:	21 f7                	and    %esi,%edi
   a:	d1 e8                	shr    %eax
   c:	d1 ea                	shr    %edx
   e:	83 e7 01             	and    $0x1,%edi
  11:	01 d0                	add    %edx,%eax
  13:	01 f8                	add    %edi,%eax
  15:	c3                   	retq

0000000000000000 <average>:
   0:	f3 0f 1e fa          	endbr64 
   4:	89 f8                	mov    %edi,%eax
   6:	21 f0                	and    %esi,%eax
   8:	31 f7                	xor    %esi,%edi
   a:	d1 ef                	shr    %edi
   c:	01 f8                	add    %edi,%eax
   e:	c3                   	retq

- [ ] 比較上述實作在編譯器最佳化開啟的狀況，對應的組合語言輸出，並嘗試解讀 (可研讀 CS:APP 第 3 章)
- [ ] 研讀 Linux 核心原始程式碼 include/linux/average.h，探討其 Exponentially weighted moving average (EWMA) 實作，以及在 Linux 核心的應用

---

### 測驗 `2`
改寫[〈解讀計算機編碼〉](https://hackmd.io/@sysprog/binary-representation) 一文的「不需要分支的設計」一節提供的程式碼 `min`，我們得到以下實作 (`max`):

#include <stdint.h>
uint32_t max(uint32_t a, uint32_t b)
{
    return a ^ ((EXP4) & -(EXP5));
}

* 考慮以下兩種狀況
* *Case 1* : a > b, `return a ^ 0`，`EXP5` 需要為 `0`，則 `EXP5` 為 `a < b` 或 `a <= b`，當 `a == b` 時，return `a` 即可，所以選擇 `a < b`
* *Case 2* : a < b, `return a ^ (a ^ b)`，`EXP4` 為 `a ^ b`

- [ ] 對 32 位元無號/有號整數，撰寫同樣 branchless 的實作
- [ ] Linux 核心也有若干 branchless / branch-free 的實作，例如 lib/sort.c: 請在 Linux 核心原始程式碼中，找出更多類似的實作手法。請善用 git log 檢索。

---

### 測驗 `3`
考慮以下 64 位元 GCD ([greatest common divisor](https://en.wikipedia.org/wiki/Greatest_common_divisor), 最大公因數) 求值函式:

#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;
}

改寫為以下等價實作:

#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 (COND);
    return RET;
}

GCD 演算法
> 1. If both x and y are 0, gcd is zero gcd(0,0)=0.
> 2. gcd(x,0)=x and gcd(0,y)=y because everything divides 0.

`if (!u || !v) return u | v;` 可以表達1與2

> 3. If x and y are both even, gcd(x,y)=2∗gcd(x2,y2) because 2 is a common divisor. Multiplication with 2 can be done with bitwise shift operator.

for (shift = 0; !((u | v) & 1); shift++) {
        u /= 2, v /= 2;
    }

只要 `u` or `v` 可以同時被 `2` 整除，那就表達成 gcd(u,v)=$2^{shift}$∗gcd($\dfrac{u}{2^{shift}}$,$\dfrac{v}{2^{shift}}$)
> 4. If x is even and y is odd, gcd(x,y)=gcd(x2,y).
> 5. On similar lines, if x is odd and y is even, then gcd(x,y)=gcd(x,y2). It is because 2 is not a common divisor.

while (!(u & 1))
    u /= 2;
while (!(v & 1))
    v /= 2;

當 `u` 或 `v` 為一基數與一偶數時，`2` 不會再是公因數，所以可以直接除`2`

if (u < v) {
    v -= u;
} else {
    uint64_t t = u - v;
    u = v;
    v = t;
}

最後的部份就是在做輾轉相除法，可以看出當 `v` 為 `0` 時，就是結束，因此 `COND` 為 `v`，而 `RET` 就是 `u << shift`

- [ ] 在 x86_64 上透過 __builtin_ctz 改寫 GCD，分析對效能的提升;
- [ ] Linux 核心中也內建 GCD (而且還不只一種實作)，例如 lib/math/gcd.c，請解釋其實作手法和探討在核心內的應用場景。

---

### 測驗 `4`
在影像處理中，bit array (也稱 bitset) 廣泛使用，考慮以下程式碼:

#include <stddef.h>
size_t naive(uint64_t *bitmap, size_t bitmapsize, uint32_t *out)
{
    size_t pos = 0;
    for (size_t k = 0; k < bitmapsize; ++k) {
        uint64_t bitset = bitmap[k];
        size_t p = k * 64;
        for (int i = 0; i < 64; i++) {
            if ((bitset >> i) & 0x1)
                out[pos++] = p + i;
        }
    }
    return pos;
}

考慮 GNU extension 的 `__builtin_ctzll` 的行為是回傳由低位往高位遇上連續多少個 `0` 才碰到 `1`。
用以改寫的程式碼如下:

#include <stddef.h>
size_t improved(uint64_t *bitmap, size_t bitmapsize, uint32_t *out)
{
    size_t pos = 0;
    uint64_t bitset;
    for (size_t k = 0; k < bitmapsize; ++k) {
        bitset = bitmap[k];
        while (bitset != 0) {
            uint64_t t = EXP6;
            int r = __builtin_ctzll(bitset);
            out[pos++] = k * 64 + r;
            bitset ^= t;                           
        }
    }
    return pos;
}

* 第一反應是 `0x1 << r` 這樣就能做出最低位 `1` 的mask，但 `r` 的宣告在 `t` 之後，所以這不是答案。
* 想到 `__builtin_ctzll` 也是需要找到同樣的mask才能去算出return的值，於是去看了 `__builtin_ctzl` 的實做，如下：

int __builtin_ctzl(unsigned long x) {
    int r = 63;
    x &= ~x + 1;
    if (x & 0x00000000FFFFFFFF) r -= 32;
    if (x & 0x0000FFFF0000FFFF) r -= 16;
    if (x & 0x00FF00FF00FF00FF) r -= 8;
    if (x & 0x0F0F0F0F0F0F0F0F) r -= 4;
    if (x & 0x3333333333333333) r -= 2;
    if (x & 0x5555555555555555) r -= 1;
    return r;
}

`x &= ~x + 1` 可以得到mask，而 `~x + 1` 即是 `-x`，因此 `EXP6` 是 `bitwise & -bitwise`

- [ ] 解釋上述程式運作原理，並舉出這樣的程式碼用在哪些真實案例中;
- [ ] 設計實驗，檢驗 ctz/clz 改寫的程式碼相較原本的實作有多少改進？應考慮到不同的 bitmap density;
- [ ] 思考進一步的改進空間;
- [ ] 閱讀 Data Structures in the Linux Kernel 並舉出 Linux 核心使用 bitmap 的案例;

---

### 測驗 `5`
以下是 [LeetCode 166. Fraction to Recurring](https://leetcode.com/problems/fraction-to-recurring-decimal/) Decimal 的可能實作:

#include <stdbool.h>                       
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include "list.h"
    
struct rem_node {
    int key;
    int index;
    struct list_head link;
};  
    
static int find(struct list_head *heads, int size, int key)
{
    struct rem_node *node;
    int hash = key % size;
    list_for_each_entry (node, &heads[hash], link) {
        if (key == node->key)
            return node->index;
    }
    return -1;
}

char *fractionToDecimal(int numerator, int denominator)
{
    int size = 1024;
    char *result = malloc(size);
    char *p = result;

    if (denominator == 0) {
        result[0] = '\0';
        return result;
    }

    if (numerator == 0) {
        result[0] = '0';
        result[1] = '\0';
        return result;
    }

    /* using long long type make sure there has no integer overflow */
    long long n = numerator;
    long long d = denominator;

    /* deal with negtive cases */
    if (n < 0)
        n = -n;
    if (d < 0)
        d = -d;

    bool sign = (float) numerator / denominator >= 0;
    if (!sign)
        *p++ = '-';

    long long remainder = n % d;
    long long division = n / d;

    sprintf(p, "%ld", division > 0 ? (long) division : (long) -division);
    if (remainder == 0)
        return result;

    p = result + strlen(result);
    *p++ = '.';

    /* Using a map to record all of reminders and their position.
     * if the reminder appeared before, which means the repeated loop begin,
     */
    char *decimal = malloc(size);
    memset(decimal, 0, size);
    char *q = decimal;

    size = 1333;
    struct list_head *heads = malloc(size * sizeof(*heads));
    for (int i = 0; i < size; i++)
        INIT_LIST_HEAD(&heads[i]);

    for (int i = 0; remainder; i++) {
        int pos = find(heads, size, remainder);
        if (pos >= 0) {
            while (PPP > 0)
                *p++ = *decimal++;
            *p++ = '(';
            while (*decimal != '\0')
                *p++ = *decimal++;
            *p++ = ')';
            *p = '\0';
            return result;
        }
        struct rem_node *node = malloc(sizeof(*node));
        node->key = remainder;
        node->index = i;

        MMM(&node->link, EEE);

        *q++ = (remainder * 10) / d + '0';
        remainder = (remainder * 10) % d;
    }

    strcpy(p, decimal);
    return result;
}

* 第13-22行，將 remainder 經過 hash function 後，找尋是否已經存在 `head[hash]`，若有則是代表小數部份已經開始循環，回傳值 pos 是開始循環小數的位置，若無則回傳-1。
* 第51-60行，將結果的正負號串到 `p`，並將結果分為 `remainder` 與 `division`，但最後一行的 `division > 0 ? (long) division : (long) -division` 有點問題，因為 `n` 與 `d` 都是正數，不會出現 `division` 為負的情況，所以要改為 `sprintf(p, "%ld", (long) division)`。
* 第73-75行，將要儲存 hash table 的 array 用 `INIT_LIST_HEAD` 初始化。
* 第79-88行，若 `pos >= 0` 代表已經找到開始重複小數的位置，要先印出沒有重複的部份，`pos` 以前的數字都代表不重複的，`PPP` 是 `pos--`。
* 第89-93行，要將還沒出現在 `heads` 內的點串上去對應的 heads[hash]，所以 `MMM` 是 `list_add`，`EEE` 是 `&heads[remainder % size]`。

為了測試 `edge case`，我採用`numerator = 2147483646, remainder = 2147483647`，將參數輸入後執行程式，發現會觸發 `Segmentation fault`，使用GDB debug時發現，有node的位址無法存取，但如果是 `malloc` 失敗，`node->key` 時就會觸發 `Segmentation fault`，有串上list代表執行當下是成功的，但要存取時卻無法存取，還需要再研究。

Breakpoint 1, find (heads=0x555555559ac0, size=1333, key=1171491056)
    at fractionToDecimal.c:16
16	    int hash = key % size;
(gdb) next
17	    list_for_each_entry (node, &heads[hash], link) {
(gdb) p hash
$7 = 2
(gdb) heads[2]
Undefined command: "heads".  Try "help".
(gdb) p heads[2]
$8 = {prev = 0x3937383439363536, next = 0x3234303032343638}
(gdb) p heads[2]->next 
$9 = (struct list_head *) 0x3234303032343638
(gdb) p heads[2]->next->next 
Cannot access memory at address 0x3234303032343640
(gdb) p heads[2]->prev 
$10 = (struct list_head *) 0x3937383439363536
(gdb) p heads[2]->prev->prev 
Cannot access memory at address 0x3937383439363536

- [ ] 解釋上述程式碼運作原理，指出其中不足，並予以改進
- [ ] 在 Linux 核心原始程式碼的 mm/ 目錄 (即記憶體管理) 中，找到特定整數比值 (即 fraction) 和 bitwise 操作的程式碼案例，予以探討和解說其應用場景

---

### 測驗 `6`
[__alignof__](https://gcc.gnu.org/onlinedocs/gcc/Alignment.html) 是 GNU extension，以下是其可能的實作方式:

/*
 * ALIGNOF - get the alignment of a type
 * @t: the type to test
 *
 * This returns a safe alignment for the given type.
 */
#define ALIGNOF(t) \
    ((char *)(&((struct { char c; t _h; } *)0)->M) - (char *)X)

- [ ]在 Linux 核心原始程式碼中找出 __alignof__ 的使用案例 2 則，並針對其場景進行解說
- [ ]在 Linux 核心源使程式碼找出 ALIGN, ALIGN_DOWN, ALIGN_UP 等巨集，探討其實作機制和用途，並舉例探討 (可和上述第二點的案例重複)。思索能否對 Linux 核心提交貢獻，儘量共用相同的巨集

### 測驗 `7`